前言

在翻看《C语言接口与实现》的时候，笔者从书中的前言所得。前四章为必须看的，从第五章开始每章之间没有关系，可以单独翻阅。笔者注意到第二十章是讲述线程的，笔者粗略翻阅了一下，这一章讲述的是线程的实现原理，这引起了笔者的兴趣，早在以前，笔者虽然对于线程有一些理解，但实际上也仅限是理解为“执行流之间的切换”这样肤浅的理解。那么我们现在就一看究竟线程是如何实现的吧。书中线程实现稍微比较复杂，笔者尽量讲得清楚明白。线程的实现设计到各个平台的汇编代码，设计到这个部分时，笔者先不针对某个平台讲解汇编代码，将以i386平台为例子讲述大致的原理

书中讲述线程的同时,也讲述了信号量，通道和举了两个并行算法的例子，这一章我们先讲述线程这个模块，其余的我们后面有空再补充

对于线程的初步认识，笔者推荐各位对线程不了解的读者去最后面的参考阅读部分阅读文章《为什么每个线程都需要创建一个栈？》，本章需要一些编译原理或C语言的基础，如果阅读途中遇到此类问题，各位读者请自行学习。代码部分因为比较长这里先不贴出来，读者可以从网上下载

线程实现

这里的线程实现会基于linux系统的一些接口，请各位知悉

线程数据结构

线程结构体代码如下：

struct Thread_T {
    unsigned long *sp;                      /* must be first */
    struct Thread_T* link;
    struct Thread_T** inqueue;
    struct Thread_T* handle;
    Except_Frame *estack;
    int code;
    struct Thread_T* join;
    struct Thread_T* next;
    int alerted;
};

成员作用分别如下：

• sp：线程的堆栈指针，必须在最前面，我们后面再讲为什么
• link：指向队列中的下一个线程
• inqueue：指向线程所在队列，比如ready队列、join队列的队列头
• handle：用于确保当前线程是存在的
• estack：线程的异常栈帧
• code：线程的退出码
• join：线程的汇聚队列，下述
• next：当线程在freelist 队列时使用，指向队列中的下一个线程
• alerted：表示线程的警告-待决状态，笔者当前也未知起作用

全局变量

• root：根线程，全局必须要有一个根线程
• current：当前运行的线程
• 队列：下述
• nthreads：全局线程的数量
• critical：用于临界资源的处理

队列操作

线程有三种状态，分别为：运行、阻塞和死亡。

书中实现线程时，维护了 3 个全局队列，如下：

• ready：该队列而用于存放正在就绪态的线程，也就是未能运行但即将得到运行的线程
• freelist：该队列存放等待释放资源的线程结构体
• join0：该队列用于等待全部线程退出，该队列只能有一个线程
  
  ready队列

join0队列

freelist队列

除了以上 3 个队列，每个线程都有一个自己的join队列，对于单核的CPU来说，当前只有一个线程可以被执行，其他的线程只能在以上说到的几个队列中挂着，直到合适的时机被调度。

get

队列数据结构的出队操作，这里不讲述其过程，相信各位能够读懂。这里的 get 函数对 ready 队列有效。

static Thread_T get(Thread_T *q) {
    Thread_T t;
    assert(!isempty(*q));
    t = (*q)->link;
    if (t == *q)
        *q = NULL;
    else
        (*q)->link = t->link;
    assert(t->inqueue == q);
    t->link = NULL;//清空这2个成员以表示线程不在任何一个队列中
    t->inqueue = NULL;
    return t;
}

put

队列数据结构体的入队操作，同理也是对 ready 队列有效，后面的 *q ，一般都是传入 &ready 。

static void put(Thread_T t, Thread_T *q) {
    assert(t);
    assert(t->inqueue == NULL && t->link == NULL);
    if (*q) {
        t->link = (*q)->link;
        (*q)->link = t;
    } else
        t->link = t;
    *q = t;
    t->inqueue = q;
}

delete

这个是直接寻找队列中的指定线程，然后将线程删除

static void delete(Thread_T t, Thread_T *q) {
    Thread_T p;
    assert(t->link && t->inqueue == q);//
    assert(!isempty(*q));//确保队列非空
    for (p = *q; p->link != t; p = p->link)
        ;
    if (p == t)
        *q = NULL;
    else {
        p->link = t->link;
        if (*q == t)
            *q = p;
    }
    t->link = NULL;
    t->inqueue = NULL;
}

线程实现

对线程的调用必须是原子的，即不可被任何其余的操作打断。

初始化线程模块

书中的线程实现是基于应用的线程，所以在使用线程之前，我们需要对线程的一些必要的数据结构进行简单地初始化

代码

int Thread_init(int preempt, ...) {
    assert(preempt == 0 || preempt == 1);
    assert(current == NULL);
    root.handle = &root;
    current = &root;
    nthreads = 1;
    if (preempt) 
    {
        struct sigaction sa;
        memset(&sa, '\0', sizeof sa);
        sa.sa_handler = (void (*)())interrupt;
        if (sigaction(SIGVTALRM, &sa, NULL) < 0)
            return 0;
        struct itimerval it;
        it.it_value.tv_sec     =  0;
        it.it_value.tv_usec    = 50;
        it.it_interval.tv_sec  =  0;
        it.it_interval.tv_usec = 50;
        if (setitimer(ITIMER_VIRTUAL, &it, NULL) < 0)
            return 0;
        
    }
    return 1;
}

preempt 的作用是指定使用抢占模式还是非抢占模式。关于抢占，书中给的解释如下：
如果一个运行的线程能够主动放弃占用处理器，让其他线程运行，那么为非抢占。如果线程不能这么做，只能被调度运行，那么则是抢占。

对 handle 成员的赋值是代表该线程存在，如果 handle 被赋值为 NULL ，则说明线程已经不存在。这样做的目的可以判断线程的有效性

接着将根线程设置为当前线程，并设置nthreads。

根据 preempt 设置调度方式，如果为 1 ，则使用抢占调度方式，这样的话就需要使用定时中断函数来让每个线程都得到运行，中断定时函数我们后面讲述。如果为 0 的话，则让线程之间通过调用接口转让 CPU 的占用。

注意这里的抢占使用了linux的软件定时器来发送信号从而执行interrupt函数来进行调度，调度就是在函数interrupt中进行的，我们将在后面讲述这个函数。

线程获取本身句柄

Thread_T Thread_self(void) {
    assert(current);
    return current;
}

非常简单，线程调用这个函数时可以获取到本身的线程句柄，返回 current 全局变量

线程切换函数

static void run(void) {
    Thread_T t = current;//保存当前线程
    current = get(&ready);//从就绪队列中获取线程，并设置为当前线程
    t->estack = Except_stack;//保存线程的当前异常栈帧
    Except_stack = current->estack;//切换当前异常栈帧为即将运行线程的异常栈帧
    _swtch(t, current);//这里是汇编写的函数，这里理解为将运行t线程切换为运行current线程
}

这个函数在切换上下问的函数都会被用到。相对来说并不复杂，保存必要的数据成员然后切换运行的线程。_swtch 是一个切换线程运行的函数，他是在汇编层面切换寄存器的值从而切换线程运行。

这里我们需要说强调一下，当 ready 队列为空，但是我们调用了 run 函数时，这将发生死锁，因为我们没有可以运行的线程了。这是一个可以被检查出来的错误，对空队列调用 get 函数可以检测到死锁。

这个函数像setjmp一样，当线程调用该函数被切换时，那么线程也会在调用该函数的地方恢复并且执行，如下

切换run.jpg

线程暂停

void Thread_pause(void) {
    assert(current);
    put(current, &ready);
    run();//切换当前线程和ready队列中的线程
}

暂停函数也很简单，将当前线程入队，然后切换当前和ready队列中的线程

在书中的 318页 列举了一个线程之间切换的例子，因为例子比较长，书中解释得也比较详尽。这里不做赘述，有需要的读者可以阅读原著了解。

线程警报

在一小节需要结合线程汇合部分一起理解，这 2 部分耦合比较严重，请读者知悉

void Thread_alert(T t) {
    assert(current);
    assert(t && t->handle == t);
    t->alerted = 1;
    if (t->inqueue) { 
        delete(t, t->inqueue);
        put(t, &ready);
    }
}
static void testalert(void) {
    if (current->alerted) {
        current->alerted = 0;
        RAISE(Thread_Alerted);
    }
}

Thread_alert 可以对一个线程的alerted(警报-待决)标志位进行设置，如果他此时在ready队列中则将让该线程重新入队

如果线程调用 testalert ，如果当前线程的alerted标志被设置，则清空该标志位并引发Thread_Alerted 异常。

阻塞线程的alerted

书中所说：

当 线程t 阻塞的时候将使 线程t 变得可运行

笔者的理解是：线程t被阻塞应该是说 线程t 被添加入了其余的非ready队列，比如全局的join0，或者其他线程的join队列，或者信号量的队列(在信号部分讲述)，当线程t被添加到这些队列时，CPU会被切换到其他线程运行，所以该线程t阻塞了。

而下面这一句则是将线程从它当前所处的队列删除，并添加到ready队列，那这样的话线程就变得可运行了

delete(t, t->inqueue);
put(t, &ready);

书中所说：

在下一次运行的时候会引发Thread_Alerted异常

笔者的理解是：会阻塞线程的函数有join函数和sem_wait(后述)，仔细观察他们的代码，会发现在调用run都会调用testalert，而在testalert函数中则会引发Thread_Alerted异常，也就是说有其他线程对 线程t 调用Thread_alert时，阻塞中的线程t 会返回，但返回后马上引发异常。

而会引发异常的主要判断依据就是alerted标志，调用了Thread_alerted函数会设置为该标志

运行线程的alerted

书中所说：

Thread_alert会清除线程t的alerted标志清除并在 下一次调用Thread_join 或 可以导致阻塞通信 或 同步函数 时引发引发异常

注意上面说到的 3 种情况，这 3 种情况其实都是调用了能阻塞线程的函数。如上一小节所说，alerted标志被设置为 1 ，那么该线程在阻塞后返回会引发异常Thread_Alerted

• 下一次调用Thread_join
• 可以导致阻塞通信
• 同步函数

线程警报的作用

书中给的讲述是：

无法结束一个正在运行的线程，线程必须结束自身。结束线程自身可以通过调用Thread_exit或者响应Thread_Alerted异常。响应Thread_Alerted异常最常见的方式就是结束线程，一般通过下面的形式来完成，这些语句必须由线程本身执行

int applay(void* p)
{
    TRY
        ...
    EXCEPT(Thread_Alerted)
        Thread_exit();
    END_TRY;
    Thread_exit(EXIT_SUCCESS);
}

书中还列举了另外一种错误的情况，代码如下。各位读者有兴趣的话可以自己去查看，笔者尚未理解这个例子，所以不做解释

Thread_T t;
TRY
    t = Thread_new(...);
EXCEPT(Thread_Alerted)
    Thread_exit(...)
END_TRY
Thread_exit(...)

上述代码是错误，书中的讲述是

因为其中的TRY-EXCEPT应用到调用线程，而非新线程

笔者不甚求解，请明白的读者留言指教

线程汇合

这里不解释 join 的作用，有需要的组合自行查阅资料。大致就是调用该函数的线程会阻塞直到 线程t 退出

int Thread_join(Thread_T t) {
    assert(current && t != current);
    testalert();
    if (t) {
        if (t->handle == t) {
            put(current, &t->join);
            run();
            testalert();//
            return current->code;
        } else
            return -1;
    } else {
        assert(isempty(join0));
        if (nthreads > 1) {
            put(current, &join0);
            run();
            testalert();
        }
        return 0;
    }
}

1、当参数不为NULL时：

join 操作的原理大致上是将调用Thread_join 的线程(一般是当前线程current)加入线程t的join队列，然后切换线程。

要注意，这里因为加入的队列是 线程t 的 join 队列，所以当前线程的 inqueue 指向的是线程t的join队列头。

当线程t调用Thread_exit时，会有对join队列的处理。

当线程返回后会执行 testalert 函数来判断是否引发异常。

2、当参数为NULL时：

当参数为NULL 时，则是等待所有线程退出。而代码的操作其实就是把join队列换为全局的join0队列，其他类似。但是会判断当前的线程量是不是大于 1 。

另外要注意的就是join0只能有 1 个线程。原因是join0队列是用来等待所有其他线程结束的，至于如何理解的话需要靠各位读者集合后面的退出函数了

线程退出

在看退出函数前我们先看下面这个代码

static void release(void) {
    Thread_T t;
    do { 
        critical++;//进入临界区
        while ((t = freelist) != NULL) 
        {
            freelist = t->next;
            FREE(t);
        }
        critical--; //结束临界区
    } while (0);
}

critical是个全局变量，它简单的标志了临界区的代码。其次代码不断的查找freelist队列中的线程，并将它们释放，结束临界区的使用，退出函数

void Thread_exit(int code) {
    assert(current);
    release();
    if (current != &root) {
        current->next = freelist;
        freelist = current;
    }
    current->handle = NULL;
    while (!isempty(current->join)) {
        Thread_T t = get(&current->join);
        t->code = code;
        put(t, &ready);
    }
    if (!isempty(join0) && nthreads == 2) {
        assert(isempty(ready));
        put(get(&join0), &ready);
    }
    if (--nthreads == 0)
        exit(code);
    else
        run();
}

先调用一次release函数清空freelist队列中的所有线程。

根线程是静态定义的，无法被释放的。所以只有当前线程不是根线程时才会执行，先将当前线程加入freelist队列

清空handle成员表示线程已经不存在

然后查看当前线程的join队列，如果有线程A正在等待当前线程退出，线程A也就是被加入到当前线程join队列的线程，则将它从join队列中取出，然后设置参数退出码，再将其放入ready队列，这样线程A就能得到返回执行

如果当前只有两个线程，且其中一个在join0队列中，那么就可以恢复该线程的执行了，如果当前线程不止两个线程的话，则需要等待其他线程退出时检测该判断条件并在合适的时候恢复join0队列中的线程。

调用退出函数时发现ready线程必须为空才能执行下去，因为join0非空，而只有 2 个线程，那么ready必定为 0 。因为一个在join0，而一个在执行退出函数

如果线程量减 1 ，如果线程量为 0 ，则说明当前进程内的所有线程已经退出，那么执行exit来退出线程，笔者的理解是其实这里也可以换做其他操作，主要看想要实现的功能。

线程创建

这里的线程主要需要 2 个资源：16kb的栈和线程结构体

Thread_T Thread_new(int apply(void *), void *args,int nbytes, ...) 
{
        Thread_T t;
        assert(current);
        assert(apply);
        assert(args && nbytes >= 0 || args == NULL);
        if (args == NULL)
            nbytes = 0;
        int stacksize = (16*1024+sizeof (*t)+nbytes+15)&~15;
        release();
        do { 
            critical++;
              TRY
                    t = ALLOC(stacksize);
                    memset(t, '\0', sizeof *t);
              EXCEPT(Mem_Failed)
                    t = NULL;
              END_TRY;
              critical--; 
        } while (0);
        if (t == NULL)
                RAISE(Thread_Failed);
        t->sp = (void *)((char *)t + stacksize);
        while (((unsigned long)t->sp)&15)
                t->sp--;
        t->handle = t;
        if (nbytes > 0) {
                t->sp -= ((nbytes + 15U)&~15)/sizeof (*t->sp);//指针往前移动
                do{ 
                        critical++;
                        memcpy(t->sp, args, nbytes);//开始拷贝
                        critical--; 
                }while(0);
                args = t->sp;//保存参数args的地址，后面有用
        }
        extern void _thrstart(void);
        t->sp -= 4/4;
        *t->sp = (unsigned long)_thrstart;
        t->sp -= 16/4;
        t->sp[4/4]  = (unsigned long)apply;
        t->sp[8/4]  = (unsigned long)args;
        t->sp[12/4] = (unsigned long)t->sp + (4+16)/4; 
        nthreads++;
        put(t, &ready);
        return t;
}

参数 apply 是需要执行的函数，args和nbytes分别是参数和参数大小，后面的省略号是做可变参数功能的，可以忽略。

需要注意的是，这里的栈默认是向低地址处增长的

先进行一些常规的参数检测，接着是计算线程栈的大小，包括线程结构体、栈和参数变量的大小，这里计算的时候进行了16对齐，然后调用release函数释放空闲资源，为什么这里也需要使用这个函数呢？因为Thread_exit是调用了release后再将自己的线程结构体加入freelist队列的，而且它自身的栈依旧需要使用，所以它是没办法释放自身的。

进入临界区，为线程开辟空间，这里当然也使用了异常处理

将 sp 也就是栈指针往后移到最后一个字节，因为我们默认栈是向低地址增长的。代码在移动栈指针的时候使之对齐到 16 字节边界

赋值handle成员，表明线程存在

接下来涉及到线程堆栈的使用了，每个硬件平台都有自己不同的实现，这里按照i386平台为例子

一开始是将参数变量拷贝到栈的最低地址

_thrstart是一个汇编函数，他的作用是开始执行线程

拷贝完参数后，将_thrstart的地址压入栈，往前移动16个字节，然后分别将执行函数和参数的地址压入栈，最后压入栈指针+5的地址，按照笔者的计算和理解是指向参数args的地址。

拷贝完毕后如下：

堆栈内存分布

最底下的是args实际存放的内容，而上面的args仅仅是个地址而已，指向实际内容所在的地方。虽然args(地址) 和 _thrstart 在图中 2 个指向的地方不一样，但其实他们是一样的值的，仅仅是画图时方便观看所以将它们分开指向

最后就是将线程加入ready队列，然后线程量加 1

线程调度

前面讲了线程的种种功能实现，接下来我们来讲一下整个线程最核心的地方，也就是调度和汇编的切换实现，代码如下

static int interrupt(int sig, struct sigcontext_struct sc) {
    if (critical || 
        sc.eip >= (unsigned long)_MONITOR &&  
        sc.eip <=(unsigned long)_ENDMONITOR)
        return 0;
    put(current, &ready);
    do { 
        critical++;
        sigsetmask(sc.oldmask);
        critical--; 
    } while (0);
    run();
    return 0;
}

interrupt 是周期性执行的函数，它会对线程进行调度

_MONITOR 和 _ENDMONITOR 只是 2 个标定代码区域的地址，其中_MONITOR 在文件thread.c的最开头处定义的，也就是说标识着代码的开始地址，而_ENDMONITOR则是在汇编文件swtch.s的最末端定义的，标识着代码的结束地址。

按照笔者的理解，这里需要一点编译的知识，在链接文件的时候，编译器会将 swtch.s 链接在 thread.c 后面，这样才能实现 _ENDMONITOR 标识代码结束地址的功能。

首先判断 2 个条件，一个是 critical 是否为 1 ，如果为 1 则说明现在有代码需要临界资源，不能被打断，退出调度函数。第二个是判断打断的地址是否在线程模块代码区域内，如果在这个区域也要退出，因为任何Thread_xxx函数都不能被打断。

如果此时的执行函数可以被打断，那么将当前线程加入ready队列。

关于下面的代码，笔者也不甚理解，而书中所讲的原因是说重新启用SIGVTALRM信号

do { 
critical++;
sigsetmask(sc.oldmask);
critical--; 
} while (0);

最后就是调用run来切换线程，该函数前面已经讲过了，我们将一下这个函数中关键的swtch函数吧，笔者对于i386架构不熟悉，所以这里讲一下大概的原理，不具体讲解语句。有兴趣的笔者也可以从书中的另外一个例子去理解。

以下都是笔者粗浅的理解，可能出现一些错误，这里仅提供一个思路给读者参考，如果有读者理解的话还望留言指教

一般的调用形式如下：

_swtch(t, current);

.align  4
.globl  __swtch
.globl  _swtch
__swtch:
_swtch:
    //先将栈指针往前移动16个字节
    //然后将需要的寄存器值，包括返回地址，栈帧地址等压入栈
    subl    $16,%esp
    movl    %ebx,0(%esp)
    movl    %esi,4(%esp)
    movl    %edi,8(%esp)
    movl    %ebp,12(%esp)
    //将sp(栈指针)寄存器从t线程切换为current线程
    movl    20(%esp),%eax
    movl    %esp,0(%eax)
    movl    24(%esp),%eax
    movl    0(%eax),%esp
    //将在sp指针指向的栈中的参数、执行函数地址赋值给相关的寄存器，然后返回继续执行
    movl    0(%esp),%ebx
    movl    4(%esp),%esi//加载执行地址，如果是刚刚创建的线程，那么就是_thrstart
    movl    8(%esp),%edi
    movl    12(%esp),%ebp
    addl    $16, %esp
    ret//如果
.align  4
.globl  __thrstart
.globl  _thrstart
__thrstart:
_thrstart:
    pushl   %edi
    call    *%esi//调用apply，但笔者不清楚参数在哪里传递
    //因为eax此时的值会被用来存储exit的参数，也就是退出码，所以要压入栈中保存原来的值
    pushl   %eax
    //如果apply没有调用线程退出，那么返回的时候会自动调用退出函数
    call    Thread_exit
.globl  __ENDMONITOR
.globl  _ENDMONITOR
__ENDMONITOR:
_ENDMONITOR:

总结一下：在切换线程的时候，先将当前的运行环境保存到线程自己的栈中，然后再将 sp 栈指针寄存器赋值为切换后的线程的sp成员，然后将线程栈中的各个变量装载到寄存器中，返回执行

注意：这里有 2 个sp的概念，其中sp栈指针寄存器指的是芯片硬件平台的栈指针寄存器，而另外一个则是线程结构体中的sp成员，这个成员指向了线程的栈内存

后语

对于线程的讲述到了这里就结束了。书中讲述线程的这一章有很多的干货，但不知道是因为翻译原因还是一些语言描述上的问题，有些语句笔者不甚理解，需要花费一些精力和时间去理解，甚至有些到现在依旧不理解。这里做一个总结跟记录，有些内容是根据笔者自己的理解写下来的，所以未必正确，如果有错的地方，还望各位读者指出。

笔者推荐各位读者可以先去阅读书中的章节，因为书中在这一章中给了非常多的干货，如并行算法、信号量和一些线程的细节处理等。笔者这里因为是总结性质的文章，对在阅读过程中不懂的地方加以阐述和记录，通过这样的方式来加深理解，所以不对细节处做过多描述。希望本文也能够帮助那些跟笔者一样在阅读过程中遇到难题的读者

在最后的 _swtch 函数中会有一些关于汇编、芯片平台跟编译器的一些知识，笔者也很惭愧，对这一方面确实没有太多的知识来支撑理解，只能有一些肤浅的理解。关于这个方面需要好好的继续学习，以后再来攻克这一难关

参考阅读

为什么每个线程都需要创建一个栈？https://blog.csdn.net/qq_38038480/article/details/80437350