狀态機
有限狀态機(Finite State Machine 或 Finite State Automata)是軟體領域中一種重要的工具。
狀态機允許一個對象在其内部狀态改變時改變它的行為。對象内部狀态決定行為方式,對象狀态改變行為方式改變,這裡強調内部狀态。
Command 模式是将指令請求封裝成一個為對象,将不同的請求對象參數化以達到同樣的調用執行不同的指令;
State 模式是将對象的狀态封裝成一個對象,是在不同的狀态下同樣的調用執行不同的操作。
疊代器是一個典型的狀态機例子,後續會講解。
狀态機的幾種實作方式
- switch
class Object StateMachine{
int state;
void work(data){
switch(state){
case 0:
do state 0;// may change state or not
break;
case 1:
do state 1;// may change state or not
break;
default;
throw;
}
}
}
優點:簡單直覺,比較常用
缺點:如果狀态較多難以維護
- 通過容器
class Object StateMachine{
int state;
static readonly method[] methods={StateMachine:workOnState0,workOnState1};//下标代表狀态,值代表處理函數
workOnState0(data){
//do
}
workOnState1(date){
//do
}
void work(data){
//check state
method = methods[state];
method.call(data);
}
}
優點:代碼簡單了些,隻需要維護狀态容器和處理函數
缺點:需要容器,占用記憶體,狀态必須為整型。
- 還有其他實作方式,最常用的應該是 swich 方式了。
狀态機應用:疊代器
現在多數開發語言都支援疊代器。
可以直接用 foreach 周遊的對象都是可疊代對象 Iterable,疊代開始時會自動生成疊代器 Iterator。
在 java 中疊代器有 reset() 接口,但大部分都不支援此接口,通用起見,以下讨論都假設疊代器不支援此接口。
- Java
for(Item item:Iterable){
//do something
}
在編譯時編輯器自動轉換為以下代碼。
Iterator iter = Iterable.Iterator();
while(iter.hasNext()){
Item item=iter.next();
//do something.
}
- C#
在 C# 中可疊代對象為 IEnumerable 疊代器為 IEnumerator(比 Java 多實作了 IDisposable 等同于 Java 的 Closeable 或 AutoCloseable)
foreach(Item item in IEnumerator){
//do something
}
using(IEnumerator enumerator = IEnumerable.GetEnumerator())
{
while(enumerator.MoveNext()){
Item item=iter.Current;
//do something.
}
}//釋放資源 using 等同于 java 的 try use resource。
- python
python 的疊代器實作方式比較特别。 隻有一個 next() 沒有判斷是否結束的函數。當結束時抛出 StopIteration 異常。
for i in iterable:
//do something.
等同于
iterator = iter(iterable)
try:
item = next(iterator)
# do something.
except StopIteration:
pass
通過以上幾個疊代器的例子我們可以推斷出:
- 可疊代對象之是以能被 foreach 周遊,都是疊代器的功勞。 foreach 疊代一個元素就是狀态機往前步進一次,如此循環,直到符合停止條件。
- 可疊代對象可以擷取疊代器,每次周遊需要 new 一個疊代器。
- 疊代器可以執行疊代,每個執行個體隻能被單向周遊一遍,不能重複使用。
Java 和 .net 的疊代器在實作方式上有所不同。
Java 的 疊代移動在 next() 函數中,.net 的 在 MoveNext() 中。 比較兩種方式,Java 的需要在 hasNext() 和 next() 分别處理邏輯。而 .net 的 隻要在 MoveNext() 處理兩種邏輯,而 Current 屬性隻是傳回已經取到的元素。對于疊代操作而言 這種在一個函數中取出元素又傳回是否存在的方法能減少很多代碼量。對于實作 linq 而言 hasNext() next() 的方式就回略顯複雜。
兩種方式能夠互相轉換
hastNext() next() 轉為 moveNext() current() close()
// 疊代器
class IEnumerator {
int state;
Object current;
Iterator iterator;
boolean moveNext() {
switch (this.state) {
case 0:
if (this.iterator.hasNext()) {
this.current = this.iterator.next();
return true;
}
this.close();
return false;
default:
return false;
}
}
Object current(){
return this.current;
}
void close(){
this.current = null;
this.state = -1;
}
}
moveNext() current() 轉為 hastNext() next()
// 疊代器
class Iterator {
boolean checkedNext;
boolean hasNext;
IEnumerator enumerator;
public boolean hasNext() {
if (!this.checkedNext) {
this.hasNext = this.enumerator.moveNext();
this.checkedNext = true;
}
return this.hasNext;
}
public TSource next() {
if (this.hasNext()) {
this.checkedNext = false;
return this.enumerator.current();
}
throw Errors.noSuchElement();
}
}
通過代碼可以看出,.net 的疊代器是個标準的狀态機,而 java 的應該算不上是狀态機了。但這點并不影響我們對疊代器的使用。
為何要用疊代器,疊代器有什麼好處
- 懶加載 例如 給定一些檔案名,需要将這些檔案批量上傳到伺服器,要求上傳過程中能報告進度,并封裝成一個方法。
普通方式
public static int batchUpload(String[] fileNames){
for(String fileName : fileNames){
upload(fileName);
}
return fileNames.length;
}
//調用
void main(){
String[] fileNames = {"a.txt","b.txt"};
int count = batchUpload(fileNames);
System.out.println("uploaded "+ count + "files.");
}
-- out
uploaded 2 files.
疊代器
public class Uploader implements IEnumerator<Integer> {
private String[] fileNames;
private int index;
public Uploader(String[] fileNames){
this.fileNames = fileNames;
}
@Override
public boolean moveNext(){
switch (this.state){
case 0:
this.index = -1;
this.state = 1;
case 1:
this.index++;
if(this.index >= this.fileNames.length){
this.close();
return false;
}
upload(this.fileNames[this.index]);
this.current = this.index + 1;
return true;
default:
return false;
}
}
}
//調用
void main(){
String[] fileNames = {"a.txt","b.txt"};
Uploader uploader = new Uploader(fileNames);
for(int i : uploader){
System.out.println("uploaded "+ count + "files.");
}
}
-- out
uploaded 1 files.
uploaded 2 files.
結論: 對比發現,普通的方式隻有全部執行後才傳回。而疊代器,每疊代一次就傳回一個元素,這種特性叫延遲執行(隻有在周遊的時候才執行)。 以後的所有擴充将充分根據此特性展開。
疊代器應用:linq
項目位址:https://github.com/timandy/linq
簡介
- LINQ,語言內建查詢(Language Integrated Query)最早由微軟提出并在 .net 平台實作。
- 它允許編寫程式代碼以查詢資料庫相同的方式操作記憶體資料。
- 操作記憶體資料的隻能算是 Linq to Objects。同時微軟提出了 Linq to Anything 的概念。隻要編寫響應的驅動可以用 Linq 查詢任何類型的資料。例如:Linq to Xml 可以用 Linq 查詢 Xml 文檔。Linq to Sql 可以查詢 SqlServer 資料庫。開源庫中也有人開發了響應的其他資料庫的驅動。以及現在的 EntityFramework 都是 Linq to Anything 的實作。
- 此處我們隻讨論簡單的 Linq to Objects 中的同步實作,這已經足夠大大提高我們操作集合的效率。
另外完整的 Linq 應包含更多的内容。比如:
- 表達式樹(資料庫查詢就是應用的表達式樹将 linq 翻譯為 sql)。
- 并行 Linq。
- 匿名類型。
- 等等
時代在發展科技在進步,于是 Oracle 終于在 Java8 中引入了 Lambda 和 stream api。
其實 stream api 就是 linq,其實作了同步和并行 linq。
雖然 stream 很優秀,但還是有一些不足。
- stream api 沒有基于 iterable 實作,而是另起爐竈基于 Stream 接口。
- 最大的缺陷就是不能 foreach 周遊,而通過forEach 函數 又不能随時終止周遊。而先轉換為 List 再 foreach 仍然需要周遊一遍才能轉換為 List。
- 并且有些 api 并沒有實作,例如 join,union,intersect等。
- 而有的又設計的比較難用,例如 排序不提供預設比較器,toList 需要傳入 Collector 等。
發現了痛點就要去解決。
我們的目标
- 由于無法修改 iterable 源代碼,并且有些正常的序列(數組,集合,清單,可疊代對象 我們統稱為序列)并且有些序列也沒有實作 iterable。是以我們需要一類函數,将序列轉換為擁有 linq api 的疊代對象(IEnumerable)。
- 對 IEnumerable 擴充實作 linq api。
實作方法
擴充疊代器
public interface IEnumerator<T> extends Iterator<T>, AutoCloseable {
boolean moveNext();//更容易一次處理是否有下一個和擷取下一個元素的邏輯
T current();//從字段取下一個元素,可重複調用
boolean hasNext();
T next();
void reset();//不支援該方法
void close();//釋放資源方法
}
擴充可疊代對象
public interface IEnumerable<TSource> extends Iterable<TSource> {
IEnumerator<TSource> enumerator();
default Iterator<TSource> iterator() {
return this.enumerator();
}
}
實作 IEnumerable 接口
//可疊代對象
public final class IterableEnumerable<TElement> implements IEnumerable<TElement> {
private final Iterable<TElement> source;
public IterableEnumerable(Iterable<TElement> source) {
this.source = source;
}
@Override
public IEnumerator<TElement> enumerator() {
return new IterableEnumerator<>(this.source);
}
}
//配套的疊代器
public abstract class IterableEnumerator<TSource> implements IEnumerator<TSource> {
protected int state;
protected TSource current;
private boolean checkedNext;
private boolean hasNext;
//
private final Iterable<TSource> source;
private Iterator<TSource> iterator;
public IterableEnumerator(Iterable<TSource> source) {
this.source = source;
}
@Override
public boolean moveNext() {
switch (this.state) {
case 0:
this.iterator = this.source.iterator();
this.state = 1;
case 1:
if (this.iterator.hasNext()) {
this.current = this.iterator.next();
return true;
}
this.close();
return false;
default:
return false;
}
}
@Override
public void close() {
this.iterator = null;
super.close();
}
@Override
public boolean hasNext() {
return this.iterator.hasNext();
}
@Override
public TSource next() {
return this.iterator.next();
}
<!--@Override-->
<!--public boolean hasNext() {-->
<!-- if (!this.checkedNext) {-->
<!-- this.hasNext = this.moveNext();-->
<!-- this.checkedNext = true;-->
<!-- }-->
<!-- return this.hasNext;-->
<!--}-->
<!--@Override-->
<!--public TSource next() {-->
<!-- if (this.hasNext()) {-->
<!-- this.checkedNext = false;-->
<!-- return this.current();-->
<!-- }-->
<!-- throw Errors.noSuchElement();-->
<!--}-->
@Override
public void reset() {
throw Errors.notSupported();
}
@Override
public void close() {
this.current = null;
this.state = -1;
}
}
實作序列轉 IEnumerable 方法
public interface IEnumerable<TSource> extends Iterable<TSource> {
IEnumerator<TSource> enumerator();
default Iterator<TSource> iterator() {
return this.enumerator();
}
public static <TSource> IEnumerable<TSource> asEnumerable(Iterable<TSource> source) {
if (source == null) throw Errors.argumentNull("source");
return new IterableEnumerable<>(source);
}
}
擴充 IEnumerable 添加一個預設方法
default IEnumerable<TSource> where(Func1<TSource, Boolean> predicate) {
if (source == null) throw Errors.argumentNull("source");
if (predicate == null) throw Errors.argumentNull("predicate");
return new WhereEnumerable<>(source, predicate);
}
//Func 1 是一個 函數式接口
@FunctionalInterface
public interface Func1<T, TResult> {
TResult apply(T arg);
}
實作 WhereEnumerable
class WhereEnumerable<TSource> implements IEnumerable<TSource> {
private final IEnumerable<TSource> source;
private final Func1<TSource, Boolean> predicate;
private IEnumerator<TSource> enumerator;
public WhereEnumerableIterator(IEnumerable<TSource> source, Func1<TSource, Boolean> predicate) {
this.source = source;
this.predicate = predicate;
}
public IEnumerator<TSource> enumerator(){
return new WhereEnumerator(this.source, this.predicate);
}
...
}
實作 WhereEnumerator
class WhereEnumerator<TSource> implements IEnumerator<TSource> {
private final IEnumerable<TSource> source;
private final Func1<TSource, Boolean> predicate;
private IEnumerator<TSource> enumerator;
private int state;
private TSource current;
public WhereEnumerator(IEnumerable<TSource> source, Func1<TSource, Boolean> predicate) {
this.source = source;
this.predicate = predicate;
}
@Override
public boolean moveNext() {
switch (this.state) {
case 0:
this.enumerator = this.source.enumerator();
this.state = 1;
case 1:
while (this.enumerator.moveNext()) {
TSource item = this.enumerator.current();
if (this.predicate.apply(item)) {
this.current = item;
return true;
}
}
this.close();
return false;
default:
return false;
}
}
@Override
public void close() {
this.state=-1;
this.current=null;
if(this.enumerator!=null){
this.enumerator.close();
this.enumerator=null;
}
}
...
}
調用
@Test
void call(){
List<String> stringList = Arrays.asList("a", "bc", "def");
IEnumerable<String> enumerable = IEnumerable.asEnumerable(stringList).where(str->str.length() > 1);
enumerable.forEach(System.out::println);
}
----
bc
def
懶加載,延遲加載或叫延遲執行特性,得益于狀态機
注意上述例子中
IEnumerable<String> enumerable = IEnumerable.asEnumerable(stringList).where(str->str.length() > 1);
asEnumerable() 方法傳回了一個 new IterableEnumerable(), where() 方法傳回了一個 new WhereEnumerable(); 其中并沒有執行循環.此時仍然可以對 enumerable 進行其他操作,仍然不會執行循環(有些特殊指令除外);
當執行 foreach 循環或執行 forEach() 方法時,Iterable 會建立 Iterator 導緻 WhereEnumerable 建立 WhereEnumerator。 疊代第一個元素時會導緻 IterableEnumerable 建立 IterableEnumerator,每疊代一個元素,會引起疊代器鍊式反應,執行疊代,此時才是真正的執行。
優點(為什麼使用懶加載):
- 執行串行 api 時,無需每調用一次 api 執行一遍循環,可以大大提高性能。
- foreach 時,可在一定的條件下終止循環。如果不使用延遲執行,則會浪費很多 cpu 時間。而該特性是 stream api 不具有的。
缺點(可以避免)
- 如果要對篩選結果進行多次随機通路 或 周遊多次等操作,注意是多次,不要直接在 IEnumerable 上 重複執行。因為懶加載特性,每次執行都會導緻所有的篩選操作重新執行一遍。
- 解決方式就是将 IEnumerable 強制執行。調用 toArray(),或 toList() 回立即執行疊代将結果存儲在容器中。然後再對容器進行随機通路。
- 與原始代碼比較性能會略有損失,但對比提升開發效率和降低編碼錯誤率而言,優點大于缺點。
編譯器代碼 yield。
部分語言支援 yield X 文法糖,可簡化 IEnumerable 建立,注意是文法糖,編譯時最終将會被編譯為狀态機。 例如
static <TSource> IEnumerable<TSource> where(IEnumerable<TSource> source, Func1<TSource, Boolean> predicate){
if (source == null) throw Errors.argumentNull("source");
if (predicate == null) throw Errors.argumentNull("predicate");
for(TSource item : source){
if(predicate.apply(item))
yield return item;
}
}
上述方法編譯後,生成的代碼就跟 WhereEnumerable 的邏輯完全一樣。 當然,現階段 java 還不支援 yield 關鍵字。 如果 JCP 委員會不再固執己見的話将來可能會支援,否則将會遙遙無期。 不過 github 上有個 lombok-pg 實作了這個文法糖,但是需要插件與 IDE 結合,效果并不好,而且生成的代碼正确性得不到保證。
好在,我們用最原始的方法實作了 LINQ to Objects 庫,包含了多數常用的集合操作。
位址:https://github.com/timandy/linq
Linq 應用舉例
- 操作符分類見 Linq to Objects.png
部門
public final class Department {
public final String name;
public final Integer deptno;
public final List<Employee> employees;
public Department(String name, Integer deptno, List<Employee> employees) {
this.name = name;
this.deptno = deptno;
this.employees = employees;
}
public String toString() {
return String.format("Department(name: %s, deptno:%d, employees: %s)", this.name, this.deptno, this.employees);
}
}
人員
public final class Employee {
public final int empno;
public final String name;
public final Integer deptno;
public Employee(int empno, String name, Integer deptno) {
this.empno = empno;
this.name = name;
this.deptno = deptno;
}
public String toString() {
return String.format("Employee(name: %s, deptno:%d)", this.name, this.deptno);
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + (this.deptno == null ? 0 : this.deptno.hashCode());
result = prime * result + this.empno;
result = prime * result + ((this.name == null) ? 0 : this.name.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (this.getClass() != obj.getClass()) {
return false;
}
Employee other = (Employee) obj;
if (!Objects.equals(this.deptno, other.deptno)) {
return false;
}
if (this.empno != other.empno) {
return false;
}
if (this.name == null) {
if (other.name != null) {
return false;
}
} else if (!this.name.equals(other.name)) {
return false;
}
return true;
}
}
資料
private static final Employee[] badEmps = {
new Employee(140, "Cedric", 40),
new Employee(150, "Gates", null)};
private static final Department[] badDepts = {
new Department("Manager", null, Collections.emptyList())};
private static final Employee[] emps = {
new Employee(100, "Fred", 10),
new Employee(110, "Bill", 30),
new Employee(120, "Eric", 10),
new Employee(130, "Janet", 10)};
private static final Department[] depts = {
new Department("Sales", 10, Arrays.asList(emps[0], emps[2], emps[3])),
new Department("HR", 20, Collections.emptyList()),
new Department("Marketing", 30, Collections.singletonList(emps[1]))};
過濾操作符
Linq.asEnumerable(emps).where(employee -> employee.deptno < 15);//等同于 stream api 的 filter
投影操作符
Linq.asEnumerable(emps).select(emp -> emp.name);//等同于 stream api 的 map
排序操作符
Linq.asEnumerable(emps)
.orderBy(emp -> emp.deptno)
.thenBy(emp -> emp.name);//先按部門号,再按姓名排序
連接配接操作符
Linq.asEnumerable(emps)
.join(Linq.asEnumerable(depts),
emp -> emp.deptno,
dept -> dept.deptno,
(emp, dept) -> String.format("%s works in %s", emp.name, dept.name))
分組操作符
Linq.asEnumerable(emps).groupBy(emp -> emp.deptno);//按指定鍵分組
量詞操作符
Linq.asEnumerable(emps).contains(emps[0]);//序列是否包含指定元素
分區操作符
Linq.asEnumerable(emps).skip(1).take(2);//跳過1個,取兩個元素.可用于分頁
生成操作符
Linq.range(0, 100);//生成 [0, 99] 共100個數,延遲執行
Linq.repeat(0,100);//生成 100 個 0 的序列,延遲執行
Linq.empty();//生成有 0 個元素的序列,延遲執行
轉換操作符
Linq.range(0, 100).toList();//立即執行
合計操作符
Linq.range(0, 100).sum();//求和
元素操作符
Linq.range(0,100).last();//最後一個
集合操作符
Linq.asEnumerable(emps).concat(Linq.asEnumerable(badEmps));
組合應用示例
//條件:給定員工和部門,員工和部門通過部門編号關聯.
//要求:按部門分組,組按部門編号排序,組内員工按姓名排序.按順序列印部門編号、名稱和員工編号、姓名
IEnumerable<Employee> allEmps = Linq.asEnumerable(emps).concat(Linq.asEnumerable(badEmps));
IEnumerable<Department> allDepts = Linq.asEnumerable(depts).concat(Linq.asEnumerable(badDepts));
allEmps.join(allDepts, emp -> emp.deptno, dept -> dept.deptno, (emp, dept) -> Tuple.create(emp, dept))//Tuple::create
.groupBy(tup -> tup.getItem2())//按部門分組 Tuple2::getItem2
.orderBy(g -> g.getKey().deptno)//組 按部門編号排序
.forEach(g -> {
System.out.println(String.format("========deptno:%s deptname:%s========", g.getKey().deptno, g.getKey().name));
g.orderBy(tup -> tup.getItem1().name)
.forEach(tup -> System.out.println(String.format("empno:%s empname:%s", tup.getItem1().empno, tup.getItem1().name)));
});
//不列印,生成 List<Map<Department,List<Emplee>>>
List lst = allEmps.join(allDepts, emp -> emp.deptno, dept -> dept.deptno, (emp, dept) -> Tuple.create(emp, dept))//Tuple::create
.groupBy(tup -> tup.getItem2())//按部門分組 Tuple2::getItem2
.orderBy(g -> g.getKey().deptno)//組 按部門編号排序
.select(g -> {
Map<Department, List<Employee>> map = new HashMap<>();
map.put(g.getKey(), g.select(tup -> tup.getItem1()).orderBy(emp -> emp.name).toList());
return map;
})
.toList();
- 延伸閱讀-LINQ 标準查詢操作概述
疊代器應用:協程
程序和線程的定義:
一、程序是具有一定獨立功能的程式關于某個資料集合上的一次運作活動,是系統進行資源配置設定和排程的一個獨立機關。
二、線程是程序的一個實體,是CPU排程和分派的基本機關,他是比程序更小的能獨立運作的基本機關,線程自己基本上不擁有系統資源,隻擁有一點在運作中必不可少的資源(如程式計數器,一組寄存器和棧),一個線程可以建立和撤銷另一個線程;
程序和線程的關系:
(1)一個線程隻能屬于一個程序,而一個程序可以有多個線程,但至少有一個線程。
(2)資源配置設定給程序,同一程序的所有線程共享該程序的所有資源。
(3)線程在執行過程中,需要協作同步。不同程序的線程間要利用消息通信的辦法實作同步。
(4)處理機分給線程,即真正在處理機上運作的是線程。
(5)線程是指程序内的一個執行單元,也是程序内的可排程實體。
線程與程序的差別:
(1)排程:線程作為排程和配置設定的基本機關,程序作為擁有資源的基本機關。
(2)并發性:不僅程序之間可以并發執行,同一個程序的多個線程之間也可以并發執行。
(3)擁有資源:程序是擁有資源的一個獨立機關,線程不擁有系統資源,但可以通路隸屬于程序的資源。
(4)系統開銷:在建立或撤銷程序的時候,由于系統都要為之配置設定和回收資源,導緻系統的明顯大于建立或撤銷線程時的開銷。但程序有獨立的位址空間,程序崩潰後,在保護模式下不會對其他的程序産生影響,而線程隻是一個程序中的不同的執行路徑。線程有自己的堆棧和局部變量,但線程之間沒有單獨的位址空間,一個線程死掉就等于整個程序死掉,是以多程序的程式要比多線程的程式健壯,但是在程序切換時,耗費的資源較大,效率要差些。 線程的劃分尺度小于程序,使得多線程程式的并發性高。
另外,程序在執行過程中擁有獨立的記憶體單元,而多個線程共享記憶體,進而極大的提高了程式運作效率。 線程在執行過程中,每個獨立的線程有一個程式運作的入口,順序執行序列和程式的出口。但是線程不能夠獨立執行,必須依存在應用程式中,有應用程式提供多個線程執行控制。 從邏輯角度看,多線程的意義子啊與一個應用程式中,有多個執行部分可以同時執行。但作業系統并沒有将多個線程看做多個獨立的應用,來實作程序的排程和管理以及資源配置設定。這就是程序和線程的重要差別。
協程
定義
coroutine 協程全稱被稱作協同式多線程(collaborative multithreading)。每個coroutine有一個獨立的運作線路。然而和多線程不同的地方就是,coroutine隻有在顯式調用yield函數後才被挂起,同一時間内隻有一個協程正在運作。
演進
- 一開始大家想要同一時間執行那麼三五個程式,大家能一塊跑一跑。特别是UI什麼的,别一上計算量比較大的玩意就跟當機一樣。于是就有了并發,從程式員的角度可以看成是多個獨立的邏輯流。内部可以是多cpu并行,也可以是單cpu時間分片,能快速的切換邏輯流,看起來像是大家一塊跑的就行。
- 但是一塊跑就有問題了。我計算到一半,剛把多次方程解到最後一步,你突然插進來,我的中間狀态咋辦,我用來儲存的記憶體被你覆寫了咋辦?是以跑在一個cpu裡面的并發都需要處理上下文切換的問題。程序就是這樣抽象出來個一個概念,搭配虛拟記憶體、程序表之類的東西,用來管理獨立的程式運作、切換。
- 後來一電腦上有了好幾個cpu,好咧,大家都别閑着,一人跑一程序。就是所謂的并行。
- 因為程式的使用涉及大量的計算機資源配置,把這活随意的交給使用者程式,非常容易讓整個系統分分鐘被搞跪,資源配置設定也很難做到相對的公平。是以核心的操作需要陷入核心(kernel),切換到作業系統,讓老大幫你來做。
- 有的時候碰着I/O通路,阻塞了後面所有的計算。空着也是空着,老大就直接把CPU切換到其他程序,讓人家先用着。當然除了I\O阻塞,還有時鐘阻塞等等。一開始大家都這樣弄,後來發現不成,太慢了。為啥呀,一切換程序得反複進入核心,置換掉一大堆狀态。程序數一高,大部分系統資源就被程序切換給吃掉了。後來搞出線程的概念,大緻意思就是,這個地方阻塞了,但我還有其他地方的邏輯流可以計算,這些邏輯流是共享一個位址空間的,不用特别麻煩的切換頁表、重新整理TLB,隻要把寄存器重新整理一遍就行,能比切換程序開銷少點。
- 如果連時鐘阻塞、 線程切換這些功能我們都不需要了,自己在程序裡面寫一個邏輯流排程的東西。那麼我們即可以利用到并發優勢,又可以避免反複系統調用,還有程序切換造成的開銷,分分鐘給你上幾千個邏輯流不費力。這就是使用者态線程。
- 從上面可以看到,實作一個使用者态線程有兩個必須要處理的問題:一是碰着阻塞式I\O會導緻整個程序被挂起;二是由于缺乏時鐘阻塞,程序需要自己擁有排程線程的能力。如果一種實作使得每個線程需要自己通過調用某個方法,主動交出控制權。那麼我們就稱這種使用者态線程是協作式的,即是協程。
優點
通過應用環境看出協程的優點就是高并發.實際上這個高并發并非實際上的高并發.而是模拟出的高并發.實際意義上除了多核處理器上目前運作的線程為實際意義上的并發.其他的通過線程切換和程序切換實作的并發都是模拟并發.
應用
單核 cpu 的情況下要實作高并發(不包含 io),一般選擇協程. 多核 cpu 的情況下要實作高并發(不包含 io),一般選擇 多線程+協程 或者 多程序+協程.
- io的處理 在協程中如果遇到 i/o 一般将 目前運作的協程挂起,讓io 操作異步執行.程式自動切換到别的協程繼續運作.
實作
多數語言協程的實作都是通過yield 關鍵字挂起目前協程,程式自動切換到其他協程.而 yield 文法糖 基本都被翻譯成了狀态機.
示例
位址:https://github.com/timandy/coroutine