用户态并发：基本框架

前述关于线程的栈大小问题，其实栈是可以动态增长的，只不过为了效率问题，一般都是固定的，这是一个实现相关，并非线程的原罪；不过说的第二点，线程调度需要陷入内核，这个的确非常影响效率。而协程没有这两个问题，首先所有协程本质是可以在一个线程里面执行，一个协程切换的时候是暂时返回，执行栈都是复用的，随便开个比较大的空间就行了，协程的状态在堆上申请，可以按需申请，因此协程可以开很多很多，百万级都没问题；另一点，协程的切换不需要进入内核，算法可以实现得非常简单。但是也如上一篇说的，直接使用协程写代码不是很方便，无论语法怎么改善，至少我们要自己控制yield，光这点就让人不爽，再者大量的yield有时候还可能让代码变得不是那么好读，还不如自己用class写自动机对象，然后事件驱动和回调注册（twisted之类的框架就这么干的）

为了结合两者的优点，需要在语言实现上下功夫，具体地说，就是在写源语言的时候，可以像很多流行的语言一样创建线程，使用方式也一样，但源语言的线程并不对应宿主环境的真线程，宿主环境可以自始至终单线程执行，在执行时对源语言的逻辑线程进行调度，具体实现跟协程和线程都有相似的地方，简单说就是在虚拟机实现一个简化版的小型操作系统，只不过这个os主要作用是调度，其他细节如硬件驱动和内存管理则直接使用宿主环境了。因此本文讨论的是在虚拟机环境下的用户态线程并发，跟宿主环境的真实线程没有关系，可以叫伪线程，下述代码和描述中的Thread和线程都是指伪线程。另外，简单起见我们忽略异常机制等细枝末节的实现

这个虚拟机仿照操作系统相关部分来做，跟前面讲过的一个例子一样，虚拟机中所有线程都是对等的，即main线程也需要创建，虚拟机入口是一个调度主循环：

... //必要的初始化工作   
Thread main_thread = new Thread(code.main_func); //建立主线程，只是个对象而已   
env.thread_table.add(main_thread); //主线程加入线程列表   
env.running_queue.add(main_thread); //主线程可以立即开始执行   
while (env.thread_table.size() > 0) //开始调度   
{   
    ... //这里需要检查各种注册的事件是否ready，下篇再说   
    Thread t = env.running_queue.pop_front();   
    t.run(); //执行线程   
    switch (t.stat) //检查线程状态   
    {   
        case Thread.STAT_FINISH:   
        {   
            //通知正在join它的线程   
            for joining_t in t.wait_join_list   
            {   
                joining_t.event_value = t.result; //告知返回值   
                env.running_queue.add(joining_t); //加入running队列   
            }   
            thread_table.erase(t); //线程结束，去掉它   
        }   
        case Thread.STAT_YIELD:   
        {   
            continue; //线程主动放弃执行，切换   
        }   
        ... //可能还有其他情况，不过一般来说线程返回只有上面两种了，跟协程一个道理   
    }   
}   
//执行结束，虚拟机退出

在这里，每一个Thread是一个自动机，在主循环中的事情非常简单，找到一个当前可以执行的线程t，调用t.run()，在run中会从t的当前状态（也就是上次run返回时的状态）开始执行，直到线程结束或需要切换，run返回后，主循环判断线程返回状态，若线程是主动放弃（yield），则切换下一个t执行，若是线程结束，则处理善后工作

若不考虑阻塞（比如所有线程都是计算密集型代码，且互不相关），则只需要一个running队列即可，每个线程执行一段时间，执行标准调度返回STAT_YIELD，切换到另一个，反复如此直到所有线程都执行完毕，这是非常简单的，或者我们可以干脆不考虑标准调度，则各个线程是串行执行的，执行main_thread的run的时候创建的线程都只是加入thread_table和running队列，在main执行结束后挨个进行。显然，我们使用线程不是为了串行计算

回想下os对线程的调度方式，每个线程有自己的栈空间，栈的内容可以看做是它的主要状态之一，在切换上下文的时候，保持当前栈不变，修改寄存器环境，直接jmp到另一个线程的指令处，和上篇说的协程用goto自由跳转实现一样

在上面的虚拟机模型中，情况也是类似，使用t.run()来代替直接jmp，而每个线程的栈则保存在Thread对象内部，这意味着无论我们是否通过递归调用execute来实现函数调用，execute内部不能再保存任何和状态相关的数据了（局部变量，指令索引，运算栈等），统统都需要放在Thread对象里面，实际上execute里只能有一些虚拟机内部使用的临时变量。Thread对象中保存的线程栈可以用链表，用多少申请多少，动态增减，这样就解决了前述os级线程地址空间占用的问题，当然会造成一些性能损耗，但是可以通过用户态调度弥补回来

实现线程状态和代码分离，只需要将字节码解释的execute放在Thread类中，或将当前线程t作为参数传给execute。函数调用的栈帧用Frame类：

class Frame   
{   
    LocalVarTable local_var_table; //局部变量表   
    Stack stk; //当前函数运算栈   
    int idx; //执行到的指令   
};   
Thread中则使用LIFO的数据结构存Frame层次关系，比如用vector（链表也行）：   
Vector<Frame> frame_stk;

从使用上来说，run执行的时候分两种情况，第一次执行和继续上次断点执行，但是由于初始状态也是一种断点，因此就不做区分了，在run方法中只是简单调用execute：

void run()   
{   
    this.stat = STAT_RUNNING; //先设置状态   
    assert this.frame_stk.size() > 0; //这个assert失败说明有bug   
    this.execute(0); //参数是frame_stk的索引   
    //execute正常退出时不会更改this.stat   
    if (this.stat == STAT_RUNNING)   
    {   
        //最外层execute正常执行完毕，获取结果，清理状态   
        assert this.frame_stk.size() == 1;   
        this.result = this.frame_stk[0].result;   
        this.frame_stk.pop();   
        this.stat = STAT_FINISH;   
    }   
    else   
    {   
        //这里this.stat == STAT_YIELD   
    }   
}

考虑一下，一个线程yield的时候，断点可能在一个比较深的函数调用，虽然frame_stk把数据和执行点保存下来了，但由于使用的宿主语言不支持直接jmp，而是先设置this.stat，然后逐层返回，最后直到run返回，那么反过来，从断点开始继续执行时，要恢复宿主语言原先的调用栈，因此这个地方需要对字节码CODE_CALL_FUNC做特殊处理： 首先约定execute的传入参数是current_frame_idx，然后：

Frame current_frame = this.frame_stk[current_frame_idx];   
接着是CODE_CALL_FUNC的实现： 
[plain] view plaincopy
case CODE_CALL_FUNC:   
{   
    if (this.frame_stk.size() > current_frame_idx + 1)   
    {   
        //当前栈帧并非最后栈帧，表示处于断点恢复过程   
        //这里啥都不用做   
    }   
    else   
    {   
        //正常执行到这个位置，非断点恢复   
        //新建栈帧并将参数从当前运算栈拷贝参数到新栈帧，作为局部变量   
        Frame next_frame = new Frame(current_frame.stk, inst.arg);   
        this.frame_stk.push_back(next_frame); //新栈帧压栈   
    }   
    //无论是恢复还是正常调用，在这里的状态都一致了   
    this.execute(current_frame_idx + 1); //进入下一个调用栈   
    //调用结束或中断，检查   
    if (this.stat == STAT_RUNNING)   
    {   
        //正常结束   
        current_frame.stk.push(this.frame_stk[current_frame_idx + 1]); //返回值入运算栈   
        this.frame_stk.pop(); //清理栈帧   
        continue; //继续运算当前函数调用   
    }   
    //走到这里说明yield了   
    -- current_frame.idx; //根据前面几篇代码的约定，idx这时候指向下一条指令，恢复到当前指令   
    return; //直接返回   
}  
最后还需要稍稍改一下CODE_RETURN： 
[plain] view plaincopy
case CODE_RETURN:   
{   
    //栈顶是需要返回的值   
    current_frame.result = stk.pop();   
    return;   
}

这段伪代码如果正确实现，完成功能应该是没问题的，不过我写完了发现有个槽点，判断是否处于断点恢复状态的代码其实可以在execute执行一开头就做了，这样CODE_CALL_FUNC的代码能更清晰些，而且不用恢复idx，不过这点懒得改了；但另一点，由于这里的实现还是用宿主语言的execute递归来实现源语言的函数调用，因此每次yield和恢复都会有消耗（如果调用栈比较深），更好的做法我觉得是改进编译器，将CODE_CALL_FUNC和CODE_RETURN都通过压栈和CODE_JMP来实现（就像汇编那样），这样一来宿主语言的run只需要调用一层execute

P.S.还有一个可能有改进空间的细节，这里我们把运算栈放在栈帧中，而事实上如果虚拟机没有bug，则所有调用可共用一个运算栈，手工模拟下就知道这是没有问题的（还觉得不保险可以加个特殊的分界元素）；另外，局部变量和运算栈也分开了，这个也是可以合并的

这里因为不考虑异常机制等细节，execute返回只有两种情况，finish和yield，其中finish时的处理上面写得很清楚了，返回值存在当前栈帧后直接return，由调用者负责销毁被调用者的栈帧，yield的情况则更简单：

this.stat = STAT_YIELD;   
return;

只要当前栈帧的状态没有错，下次就可以恢复了

在这个框架下，标准调度很容易实现，就不啰嗦了