|
幾個(gè)月前我曾大致分析過(guò) C# 2.0 中 iterator block 機(jī)制的實(shí)現(xiàn)原理，《C# 2.0 中Iterators的改進(jìn)與實(shí)現(xiàn)原理淺析》，文中簡(jiǎn)要介紹了 C# 2.0 是如何在不修改 CLR 的前提下由編譯器，通過(guò)有限狀態(tài)機(jī)來(lái)實(shí)現(xiàn) iterator block 中 yield 關(guān)鍵字。
實(shí)際上，這一機(jī)制的最終目的是提供一個(gè)代碼協(xié)同執(zhí)行的支持機(jī)制。
以下內(nèi)容為程序代碼:
using System.Collections.Generic;
public class Tokens : IEnumerable<string>
{
public IEnumerator<string> GetEnumerator()
{
for(int i = 0; i<elements.Length; i++)
yield elements[i];
}
...
}
foreach (string item in new Tokens())
{
Console.WriteLine(item);
}
在這段代碼執(zhí)行過(guò)程中，foreach 的循環(huán)體和 GetEnumerator 函數(shù)體實(shí)際上是在同一個(gè)線程中交替執(zhí)行的。這是一種介于線程和順序執(zhí)行之間的協(xié)同執(zhí)行模式，之所以稱(chēng)之為協(xié)同（Coroutine），是因?yàn)橥瑫r(shí)執(zhí)行的多個(gè)代碼塊之間的調(diào)度是由邏輯隱式協(xié)同完成的。順序執(zhí)行無(wú)所謂并行性，而線程往往是由系統(tǒng)調(diào)度程序強(qiáng)制性搶先切換，相對(duì)來(lái)說(shuō)Win3.x 中的獨(dú)占式多任務(wù)倒是與協(xié)同模型比較類(lèi)似。
就協(xié)同執(zhí)行而言，從功能上可以分為行為、控制兩部分，控制又可進(jìn)一步細(xì)分為控制邏輯和控制狀態(tài)。行為對(duì)應(yīng)著如何處理目標(biāo)對(duì)象，如上述代碼中：行為就是將目標(biāo)對(duì)象打印到控制臺(tái)；控制則是如何遍歷這個(gè) elements 數(shù)組，可進(jìn)一步細(xì)分為控制邏輯（順序遍歷）和控制狀態(tài)（當(dāng)前遍歷到哪個(gè)元素）。下面將按照這個(gè)邏輯介紹不同語(yǔ)言中如何實(shí)現(xiàn)和模擬這些邏輯。
Spark Gray 在其 blog 上有一個(gè)系列文章介紹了協(xié)同執(zhí)行的一些概念。
Iterators in Ruby (Part - 1)
Warming up to using Iterators (Part 2)
文章第 1, 2 部分以 Ruby 語(yǔ)言（語(yǔ)法類(lèi)似 Python）介紹了 Iterator 機(jī)制是如何簡(jiǎn)化遍歷操作的代碼。實(shí)際上中心思想就是將行為與控制分離，由語(yǔ)言層面的支持來(lái)降低控制代碼的薄記工作。
以下內(nèi)容為程序代碼:
def textfiles(dir)
Dir.chdir(dir)
Dir["*"].each do |entry|
yield dir+"\"+entry if /^.*.txt$/ =~ entry
if FileTest.directory?(entry)
textfiles(entry){|file| yield dir+"\"+file}
end
end
Dir.chdir(".."[img]/images/wink.gif[/img]
end
textfiles(“c:\”){|file|
puts file
}
例如上面這段 Ruby 的遞歸目錄處理代碼中，就采用了與 C# 2.0 中完全類(lèi)似的語(yǔ)法實(shí)現(xiàn)協(xié)同執(zhí)行支持。
對(duì) C# 1.0 和 C++ 這類(lèi)不支持協(xié)同執(zhí)行的語(yǔ)言，協(xié)同執(zhí)行過(guò)程中的狀態(tài)遷移或者說(shuō)執(zhí)行緒的調(diào)度工作，需要由庫(kù)和使用者自行實(shí)現(xiàn)，例如 STL 中的迭代器 (iterator) 自身必須保存了與遍歷容器相關(guān)的位置信息。例如在 STL 中實(shí)現(xiàn)協(xié)同執(zhí)行：
以下內(nèi)容為程序代碼:
#include <vector>
#include <algorithm>
#include <iostream>
// The function object multiplies an element by a Factor
template <class Type>
class MultValue
{
private:
Type Factor; // The value to multiply by
public:
// Constructor initializes the value to multiply by
MultValue ( const Type& _Val [img]/images/wink.gif[/img] : Factor ( _Val [img]/images/wink.gif[/img] {
}
// The function call for the element to be multiplied
void operator ( [img]/images/wink.gif[/img] ( Type& elem [img]/images/wink.gif[/img] const
{
elem *= Factor;
}
};
int main( [img]/images/wink.gif[/img]
{
using namespace std;
vector <int> v1;
//...
// Using for_each to multiply each element by a Factor
for_each ( v1.begin ( [img]/images/wink.gif[/img] , v1.end ( [img]/images/wink.gif[/img] , MultValue<int> ( -2 [img]/images/wink.gif[/img] [img]/images/wink.gif[/img];
}
雖然 STL 較為成功的通過(guò)迭代器、算法和謂詞，將此協(xié)同執(zhí)行邏輯中的行為和控制分離，謂詞表現(xiàn)行為(MultValue<int>、迭代器(v1.being(), v1.end())表現(xiàn)控制狀態(tài)、算法表現(xiàn)控制邏輯(for_each)，但仍然存在編寫(xiě)復(fù)雜，使用麻煩，并且語(yǔ)義不連冠的問(wèn)題。
一個(gè)緩解的方法是將謂詞的定義與控制部分合并到一起，就是類(lèi)似 boost::Lambda 的實(shí)現(xiàn)思路：
以下內(nèi)容為程序代碼:
for_each(v.begin(), v.end(), _1 = 1);
for_each(vp.begin(), vp.end(), cout << *_1 << ' ');
通過(guò)神奇的模板和宏，可以一定程度降低編寫(xiě)?yīng)毩⒅^詞來(lái)定義行為的復(fù)雜度。但控制部分的狀態(tài)和邏輯還是需要單獨(dú)實(shí)現(xiàn)。
而 C# 1.0 中就干脆沒(méi)有自帶支持，必須通過(guò)《C# 2.0 中Iterators的改進(jìn)與實(shí)現(xiàn)原理淺析》一文中所舉例子那樣笨拙的方式完成。
以下內(nèi)容為程序代碼:
public class Tokens : IEnumerable
{
public string[] elements;
Tokens(string source, char[] delimiters)
{
// Parse the string into tokens:
elements = source.Split(delimiters);
}
public IEnumerator GetEnumerator()
{
return new TokenEnumerator(this);
}
// Inner class implements IEnumerator interface:
private class TokenEnumerator : IEnumerator
{
private int position = -1;
private Tokens t;
public TokenEnumerator(Tokens t)
{
this.t = t;
}
// Declare the MoveNext method required by IEnumerator:
public bool MoveNext()
{
if (position < t.elements.Length - 1)
{
position++;
return true;
}
else
{
return false;
}
}
// Declare the Reset method required by IEnumerator:
public void Reset()
{
position = -1;
}
// Declare the Current property required by IEnumerator:
public object Current
{
get // get_Current函數(shù)
{
return t.elements[position];
}
}
}
...
}
這種笨拙的 IEnumerable 接口實(shí)現(xiàn)方法，實(shí)際上是將 STL 中提供控制狀態(tài)的 iterator 完全自行實(shí)現(xiàn)，而且控制邏輯還限定于編寫(xiě) IEnumerable 接口實(shí)現(xiàn)時(shí)的定義。就算可以通過(guò)策略 (Strategy) 模式提供一定程度的定制，但其代碼邏輯過(guò)于分散，要理解一個(gè)簡(jiǎn)單調(diào)用必須查看四五處分散的代碼。
好在牛人總是不缺的，呵呵。
Ajai Shankar 在 MSDN 上一篇非常出色的文章，COROUTINES Implementing Coroutines for .NET by Wrapping the Unmanaged Fiber API，里面通過(guò) Win32 API 的纖程 (Fiber) 支持和 CLR 幾個(gè)底層 API 的支持，完整的實(shí)現(xiàn)了一套可用的協(xié)同執(zhí)行支持機(jī)制。
Spark Gray 的第 4 篇文章中就詳細(xì)討論了這種實(shí)現(xiàn)方式的利弊：
SICP, Fiber api and ITERATORS !(Part 4)
纖程 Fiber 是 Win32 子系統(tǒng)為了移植 Unix 下偽線程環(huán)境下的程序方便，而提供的一套輕量級(jí)并行執(zhí)行機(jī)制，由程序代碼自行控制調(diào)度流程。
其使用方法很簡(jiǎn)單，在某個(gè)線程中調(diào)用 ConvertThreadToFiber(Ex) 初始化纖程支持，然后調(diào)用 CreateFiber(Ex) 建立多個(gè)不同纖程，對(duì)新建的纖程和轉(zhuǎn)換時(shí)當(dāng)前線程缺省纖程，都可以通過(guò) SwitchToFiber 顯式進(jìn)行調(diào)度。
以下內(nèi)容為程序代碼:
static int array[3] = { 0, 1, 2 };
static int cur = 0;
VOID CALLBACK FiberProc(PVOID lpParameter)
{
for(int i=0; i<sizeof(array)/sizeof(array[0]); i++)
{
cur = array[i];
SwitchToFiber(lpParameter);
}
}
LPVOID fiberMain = ConvertThreadToFiber(NULL);
LPVOID fiberFor = CreateFiber(0, FiberProc, fiberMain);
while(cur >= 0)
{
std::cout << cur << std::endl;
SwitchToFiber(fiberFor);
}
DeleteFiber(fiberFor);
上述偽代碼是纖程使用的一個(gè)大概流程，可以看出實(shí)際上纖程跟上面 Ruby 和 C# 2.0 中的協(xié)同執(zhí)行所需功能是非常符合的。而在實(shí)現(xiàn)上，纖程實(shí)際上是通過(guò)在同一線程堆棧中構(gòu)造出不同的區(qū)域(ConvertThreadToFiber/CreateFiber)，在 SwitchToFiber 函數(shù)中切換到指定區(qū)域，以此區(qū)域(纖程)的代碼和寄存器等環(huán)境執(zhí)行，有點(diǎn)類(lèi)似于 C 代碼庫(kù)中 longjmp 的概念。Netscape 提供的狀態(tài)線程庫(kù) State Threads library 就是通過(guò) longjmp 等機(jī)制模擬的類(lèi)似功能。
而在 .NET 1.0/1.1 中要使用纖程，則還需要考慮對(duì)每個(gè)纖程的 Managed 環(huán)境構(gòu)造，以及切換調(diào)度時(shí)的狀態(tài)管理等等。有興趣的朋友可以仔細(xì)閱讀上述兩篇精彩文章。
以下內(nèi)容為程序代碼:
class CorIter : Fiber {
protected override void Run() {
object[] array = new object[] {1, 2, 3, 4};
for(int ndx = 0; true; ++ndx)
Yield(arr[ndx]);
}
}
Coroutine next = new CorIter();
Object o = next();
可以看到這個(gè)代碼已經(jīng)非常類(lèi)似 C# 2.0 中的語(yǔ)法了，只是要受到一些細(xì)節(jié)上的限制。
而 C# 2.0 中，大概是為了保障移植性，使用了將控制邏輯編譯成狀態(tài)機(jī)的方式實(shí)現(xiàn)，并由狀態(tài)機(jī)自動(dòng)管理控制狀態(tài)。其原理我在《C# 2.0 中Iterators的改進(jìn)與實(shí)現(xiàn)原理淺析》一文中已經(jīng)大概分析過(guò)了，有興趣的朋友可以進(jìn)一步閱讀 Spark Gray 的第 5 篇文章中的詳細(xì)分析。
Implementation of Iterators in C# 2.0 (Part 5)
以及 Matt Pietrek 的關(guān)于 Iterator 狀態(tài)機(jī)的分析文章
Fun with Iterators and state machines
而為了將行為與控制更緊密地綁定到一起，C# 2.0 也提供了類(lèi)似 C++ 中 boost::lambda 機(jī)制的匿名方法支持。簡(jiǎn)要的分析可以參考我以前的一篇文章《CLR 中匿名函數(shù)的實(shí)現(xiàn)原理淺析》，或者Spark Gray 的第 6 篇文章。
Implementation of Closures (Anonymous Methods) in C# 2.0 (Part 6)
|
