哈工大李治军老师讲操作系统 --（二）进程与线程

这份笔记，是我看哈尔滨工业大学李治军老师讲《操作系统》这门课所记的第二部分，进程与线程。关于这份笔记的说明，可查看前面一篇（一）操作系统基础的前言部分。

L8 CPU管理的直观想法

多进程图谱是操作系统的核心图像。明白了它以后，操作系统就明白了一大部分，能编写操作系统也就指日可待了。CPU 是计算机中最核心的硬件。在管理 CPU 的时候，引出了多进程图谱。当使用多进程图谱，管理明白了 CPU 后，别的硬件自然而然就跟着一起带动起来了。所以才说，多进程图谱是操作系统的核心图像。

只有先让 CPU 运行起来了，才能谈得上管理 CPU。让 CPU 运行得更加高效，也就是管理好了 CPU。

首先，CPU 从某一内存地址中，取出指令，接着在 CPU 中，解释执行这条指令。所以 CPU 是怎么工作的呢？它是自动地取指、执行（一旦给了 PC 第一个地址，后面的地址是自动累加的）。

管理 CPU，使用 CPU 最直观的方法，就是设好 PC 的初值。把 PC 的初值设置为一段程序的开始地址后，CPU 就开始工作。

实际上如果不讲，大家要是自己能提出这样的问题，那就非常好！将来如果大家能自己提出问题，并且自己能解决问题，我们说过，那你就能做出很多、很多事情。

当然，这里我们是讲课。所以，在这里老师只是提一句醒，希望大家以后留一个弦，每看到一个问题，每看到一件事情的时候，能不能想一想，有没有什么问题？还能怎么做？

I/O 指令相对于计算指令来说，执行起来的速度非常慢。

CPU 的利用率问题。举例了一个生活中用壶烧开水的例子，人们用壶接好水，再把壶放到火上后，是不会在那干等着水烧开。

CPU 在执行程序的过程中，遇到等待的情况，就应切换到另一个程序去执行。在之前程序的等待结束后，某一时刻再切回来继续执行。这样，CPU 在来回切换执行时，就忙碌起来了，CPU 的利用率也就提高了。

这就形成了多个程序在内存中的情形。

多道程序，交替执行。

这个图就是 CPU 应该工作的样子，交替执行多个程序——并发。

让 CPU 执行程序，CPU 就工作起来了。而让 CPU 并发地执行程序，CPU 就可以很好地工作。管理 CPU 就从这个故事开始。

当 CPU 要切换到另一个程序去执行时，需要记录当前执行的这个程序的信息。这样，在之后 CPU 切换回来执行时，才能够恢复到之前切出去时的模样。

运行的程序和静态的程序不一样了，那么，就需要引入一个概念，来描述这个不一样。

把运行的程序叫做进程（进行中的程序，执行的程序），它们和放在磁盘上的静态程序不一样。用一个数据结构（PCB）将所有的不一样都存放起来。进程的概念是一个非常重要的概念，而这也就产生了多进程。所以，从现在开始，多进程的图像在头脑中就慢慢形成了。

那么，将这一节讲的内容前后贯穿在一起，总结一下：

我们这一节讲的话题来自哪里呢？操作系统要管理 CPU。首先，我们讲的是什么呢？操作系统要使用 CPU。怎么使用 CPU 呢？给一段程序让 CPU 去执行。如果只执行一个程序的话，CPU 的利用率会非常低。为了提高 CPU 的利用率，需要让 CPU 交替地执行多个程序。
为了完成程序间的切换，就需要记录程序执行时的样子（记录相关信息）。由于执行起来的程序和静态程序不一样了，这个时候我们就引入了进程的概念。
把前后总结在一起，可以用进程反过头来，再去描述 CPU 的管理。CPU 的管理是什么呢？CPU 的使用是什么呢？就是让程序执行起来。所以，就是启动一个进程，让 CPU 去执行这个进程，那么，CPU 就工作起来了。而为了让 CPU 更好地工作，操作系统需要启动多个进程给 CPU 去执行。那么，CPU 的利用率就上来了。所以，让多个进程向前跑的样子，就应该是管理 CPU 的样子，这就是多进程图谱。

L9 多进程图像

上一节课，我们讲的是为什么会有多进程图像？操作系统要管理 CPU，而CPU 是按取指、执行的方式进行工作的硬件。要管理 CPU 得让 CPU 先工作起来。让程序执行起来，CPU 也就开始工作了。

执行起来的程序和静态程序有很大的差别，所以我们面临的一个概念就是进程。为了让 CPU 更加高效地工作，仅仅跑一个进程是不行的，必须是跑多个进程，交替执行。那么，这种交替执行的多个进程样子，就是多进程图谱（图像）。

所以，上节课我们给出了多进程图像的基本的样子，以及为什么会有多进程图像。那么从今天开始，我们来看看操作系统是怎么支持多进程图像的。这里面主要包括两个部分：第一，什么是多进程图像？第二，操作系统为了实现多进程图像，应该做些什么事情？

后面的很多内容，都是围绕怎么支持多进程图像来展开、详细讲解。今天我们把这个话题引出来，做个铺垫，做一个宏观的论述。

多个进程使用 CPU 的图像。

操作系统最后让你使用这个计算机，怎么让你使用呢？创建一个进程、启动一个shell ，去执行吧。Windows 是创建一个进程，启动一个桌面，去执行吧。接下来，你是在 shell 、桌面中去执行。

操作系统要让用户使用计算机，就是创建一个初始化的进程，然后再开始干活吧。初始化进程执行 shell，shell 要干什么事呢？用户输入一个命令，根据这个命令再创建一个进程。用户执行一个任务，也是创建一个进程。创建的这个进程完成你要完成的任务。

计算机干什么呢？解决实际问题。怎么解决实际问题呢？执行一个任务。怎么执行一个任务呢？落到操作系统里面就是要启动一个进程。所以，启动一个进程，执行一个任务，解决一个问题。解决我们要解决的问题，计算机不就使用起来的吗？由此可以看到，多进程图像、进程对于计算机的使用是多么的重要。

用户使用计算机，就是启动了一堆进程。用户管理计算机，就是管理这一堆进程。如果能够形成这个概念，那么操作系统最核心的那部分，就算揭开了，钢琴中最复杂的那部分、最核心的灵魂，就算揭开了。我是希望大家建立这样的认识。

好了，第一部分内容就讲完了。也就是说，操作系统的多进程图像是个什么东西？我们能不能看得见、摸得着？可以。第二部分，操作系统为了支持多进程图像，应该要解决哪些事情？这个部分的内容，后面我们会详细地讲，但今天我们先把问题引出来。

因为操作系统里面有多个进程，那么，这多个进程是如何组织的、怎么存放的，必须要弄清楚。

用 PCB 形成一些数据结构，来进行组织多进程。为什么说这多进程必须要组织呢？因为操作系统只有组织好多个进程，才能够合理地推进多个进程。

多个进程如何组织呢？多个进程所对应的 PCB，分别放在不同的地方，操作系统都知道，有就绪队列、等待队列等。

进程根据状态，可以区分开来。操作系统根据进程的状态图，让进程实行状态的转换来推进进程，这是操作系统对进程的组织与管理。

刚才我们说了多个进程如何组织：用 PCB 放在不同的队列中，用状态来推进这多个进程，进行状态的转换。

接下来，第二个问题是，多进程如何交替？交替切换是实现多进程图像的灵魂。刚才只讲了，怎么组织多个进程、怎么找到这多个进程、怎么推进这多个进程。而现在是，怎么具体地切换这多个进程。这个部分非常重要，后面我们会用 3-4 讲，来讲清楚它是如何交替、如何切换，其背后的代码非常复杂。

schedule() 这个函数大家必须要记住，我会无数次地说这个函数，明白了这个函数，这个切换就明白了。

进程怎么调度呢？就绪队列中有一堆进程，那调度哪个合适呢？这个话题其实很深刻，但是本课程不去讲特别深刻、理论性的东西，我们这个课程主要讲一个基本的操作系统，是怎样运转起来的。

如果深入讲进程的调度，那可能要专门开一门课。因为进程调度有很多方法，而且当前（操作系统的国际会议）仍不断在研究进程的调度。所以这是一个很深刻的话题，但我们讲一个最基本的调度，知道一个调度通常是怎么做的，大概就可以了。

进程切换时，物理 CPU 上被切换出去进程的执行现场，需要保存起来。怎么保存呢？就把物理 CPU 上的信息，保存在 PCB 里（把 CPU 寄存器里的一些信息保存在 PCB 里）。

switch_to() 函数里，由于进程现场的保存和恢复需要精细的控制（对 CPU 寄存器的精准操作），因此，需要编写汇编代码来实现。

刚才讲的，就是操作系统支持多进程图像，需要做到的第二件事。第一件事，操作系统如何组织多个进程？就是根据 PCB 和进程的状态，形成不同的队列，放在不同的位置。第二件事，操作系统如何完成进程的切换？核心就是进程的调度，得到要切换到的进程的 PCB，来给 CPU 中的寄存器进行赋值，恢复进程当初切换出去时的状态。

第三个问题是，多个进程交替执行时，会相互影响。为什么会相互影响呢？因为这多个进程都放在了内存中（只有放在内存中，CPU 才能取指、执行）。

例如，进程 1 对内存地址 100 进行赋值，而内存地址 100 可能存放进程 2 的代码。把进程 2 的代码这样修改后，会造成进程 2 的出错或奔溃。（这时不能采用 DPL 来进行权限限定，DPL、CPL 是用来保护操作系统程序的一种机制，这个时候，进程 1 和进程 2 都是用户态的程序，DPL、CPL都是 3。）这时要限制对地址 100 的读写。

基本思想是，通过映射表来限制对内存地址 100 的读写。实际上这部分是内存管理的内容。我们会在后面再详细学习内存管理，但是这个也是多进程图像必须要做到的一件事。

多进程图像要完成内存的这种限制，通过映射表来实现地址的分离。因为多个进程都在内存中，都在内存中就必须要分离，如果不分离就会相互干扰影响。

实际上，这个映射表是操作系统内存管理的核心。从这个地方也能再一次看出，为什么多进程图像是操作系统的核心？因为内存管理也在为多进程图像服务。

不同的进程访问地址时，通过各自的映射表，映射到内存的物理地址时，就完全分开了。这样，多个进程就能在内存中，很好地共存。

多进程如何合作？

假设进程 1、进程 2 都往位置 7 放各自的打印文件，因为进程是交替执行的，可能进程 1 还没放完时，进程 2 也往位置 7 放。那么，将来 7 这个位置就乱了。打印出来的内容，可能是由进程 1 和进程 2 的打印文件混合的内容。但如果进程是顺序执行，就不存在这个问题了。

生产者-消费者实例

在生产者进程中，用 counter 变量来判断缓冲区是否满了。即，如果 counter 等于 BUFFER_SIZE，就死循环。

要想生成者进程和消费者进程合作得好，counter 必须含义要对。如果内存的缓冲区已满，但是 counter 不等于 BUFFER_SIZE，那就出错了。

如果多个进程都放在内存中交替执行的话，counter 又会出现问题。这里老师说一句题外话，我们在思考问题的时候，要具体地去跑一跑例子，而不是想当然地认为，应该是那个样子。

多个进程交替执行，完全有可能会出现这样的一个执行序列。初始 counter = 5，按这个顺序执行完后 counter = 4，这时 counter 语义就出现了错误。那么接下来进程间的合作，就更谈不上了。

进程同步（合理的推进顺序，而不是在不同进程之间切换时，想切换就切换的任意推进顺序）

要想实现进程的同步，多个进程放到内存中，操作系统负责推进这多个进程。但是不是随意地推进，必须合理地推进。这也是操作系统为了支持多进程图像，必须要做到的事情。

我们最后简单地总结一下：

这节课一开篇，我们就说了，多进程图像是个什么样？那么操作系统怎么感知这多个进程呢？通过 PCB 来做到。
第二部分我们讲了，操作系统要想支持多进程图像，必须要做到的一些事情。我们讲了，如何完成切换、如何调度、如何地址映射、如何进行进程同步与合作，这些内容对应的讲解课程，后面我们会一一展开。到时候展开的时候，我们会详细地、一段一段地去描述，一点一点地去深入到内部，描述它们具体的过程。
而这一节呢，我们把这些问题、样子给大家提出来，在头脑中留下个印象。这也是老师上课的一个风格，我们首先模模糊糊，不太清楚，不太具体，有个大概的样子，然后我们进入到里面，一点一点把这个样子做细、做实。

L10 用户级线程

这节我们要讲的是，多个进程如何切换？操作系统做些什么事，可以让多个进程能够切换起来。

看到这个标题，大家可能会有点奇怪，既然是讲进程的切换，那为什么要讲线程呢？而且要讲用户级线程。什么是线程呢？线程又和切换有什么关系呢？为什么这里讲的是用户级线程呢？带着这些问题，我们开始讲解。首先，我们回答第一个问题，为什么讲进程的切换，这里要讲线程呢？

一个进程执行一堆指令。进程间的切换，也就是从一个执行指令序列，切换到另外一个执行指令序列上。可以把一个进程的执行指令序列，看做是一个函数。当从一个正在执行的 A 函数，切换到 B 函数去执行时，我们只切换这个指令，不切换这个表（映射表）可不可以？这就是一个话题，实际上这个话题引出来的就是线程。

在切换时，我们可不可以只是执行的指令发生变化，而资源（映射表，内存）不发生变化。也就是说，将资源和指令的执行，分开来可不可以。采用这种方式切换，切换速度会变快。

既有多段程序交替执行，又切起来快；既保留了并发的特点，又避免了切换起来代价特别大。这就引出了线程。在进程里面，可以启动多个指令序列，这些指令序列看起来比较轻巧，取个名字就叫线程（thread）。

我们为什么讲切换要先讲线程，而不是直接讲进程的切换？因为我们把进程的切换分成两个部分，一个是指令的切换，一个是映射表（资源）的切换。今天我们讲的是指令的切换，而后面再讲映射表（内存）的切换。

这样把这两个分开来，有什么好处呢？分治的思想，有利于我们认识问题。我们今天要学习指令是怎么切换，而不管映射表（资源）是怎么切的，这就是讲线程的切换。后面我们会再讲，为什么是用户级的线程？

接下来我们看看，线程的切换有没有价值？在实际中有没有用？因为只有在实际中有用的东西，我们就要好好地学习，操作系统本身也是非常有用的。

一个例子，用浏览器打开一个网页的过程。线程共享内存（资源），在浏览器打开一个网页时，浏览器中一个线程从服务器下载数据，显示文本、显示图片的线程等分别使用这些数据。而不同进程间的内存（资源）是分离的。

线程的切换只是比进程的切换少了一部分，它只是涉及指令序列的切换，而没涉及资源的切换。线程间切换时，指令序列的切换，也是将来讲进程间切换时，非常重要的组成部分。所以我们这节课，就以线程为单位来讲，怎么进行指令序列的切换。

如何实现线程的切换，不得靠写程序吗？所以，如果我们能通过一个例子，把线程切换的程序写出来，那么我们不就明白了，操作系统在这块是怎么做的吗？因此，我们就通过例子、通过代码、通过核心的骨干代码，来看线程是怎么实现切换的？

给出 URL 地址，申请了共享的缓冲区，然后创建了几个线程，每个线程执行一个函数（GetData 函数从服务器上，下载数据放到缓冲区里；Show 函数从缓冲区里，取出内容显示到显示器上）。总体的核心框架就是，要启动这多个线程，每个线程执行相应的函数。

我们调用 Yield 函数让线程进行切换，交替执行。调用 Create 函数可以产生多个线程，让多个线程同时出发。如果把这两个函数实现好了，不就可以实现同时出发、交替执行的多线程了吗？这就是我们讲这一部分的核心内容。

因此，对 Create，Yield 这两个函数到底是怎么写出来的？要详细讲解。

实现 Yield 目的就是要能完成切换。要完成切换就必须要了解、在头脑中形成，切换时要长成什么样子？只有切换时这个样子明白了，我们再写程序把这个样子做出来，这个程序不就有了吗？

这也是在我们这个课程中，大家写操作系统这种较复杂的代码时，可能有时感到无从下手，因为它太过于复杂。但是，无论多么复杂的程序都是一样的，在你的头脑中，如果能形成这个样子，你剩下的就是用 C 语言或汇编，把它表达出来。写任何程序都是这样，写 Yield 线程的切换也不例外。

要想切换，必须要长成什么样子呢？我们就以这个例子来学习。大家不要凭空想，把实际的代码跑一跑，把自己的头脑变成一台计算机，实际地跑一跑，理解了这个过程，那么你就知道它是怎么切的了。

从这个点开始大家要集中注意力，两个执行序列的切换在操作系统里面是最难的、最繁琐的，也是最不好理解的一点东西。这个东西是操作系统真正的核心。紧接着我们就会说，这是整个操作系统能运转起来的发动机。

两个执行序列与一个栈。两个线程共用一个栈可能发生问题。

从一个栈到两个栈。

线程切换时，栈也要切回去。这就引出了一个数据结构 TCB，TCB 和栈相互配合。

这里说句题外话，操作系统对 C 语言、对汇编、对编译、对计算机、对程序、对算法有一定的要求，是一个综合性的学科，会把这些知识综合在一起。

大家可以看到，就这两页的 PPT ，这两页的内容，就完成了线程的切换。用到的是栈，是从一个栈到两个栈，用 Yield() 配合着栈，实现栈的切换，而把返回的地址（返回的 PC ）压到栈中。所以栈切换，再一弹栈， PC 一切换，非常漂亮，非常简单。

Create 的核心就是用程序做出这三样东西。

栈和 TCB 关联。当线程切换时首先找到 TCB 中的 esp，把 TCB 中的 esp 值赋给 CPU 的 esp 寄存器，然后再去执行这时弹出的栈中，100 地址处指令。所以大家可以看到，Create 讲清楚了，Yield 也讲清楚了，这两个都讲清楚了，那么线程就可以完成它的工作方式。

首先创建多个线程，然后把线程的起始地址放入栈中，把 TCB 和栈进行关联。Create 以后，这两个函数（GetData、Show）就做成了可以执行的样子，就相当于多个程序同时出现在了内存中。然后让它们执行，在程序执行的过程中，调用 Yield，首先切换栈，切换栈以后再弹栈，实现切换到另外一个线程，在另外一个线程中继续执行。

把所有的这些东西合在一起，做一个应用程序，这相当于一个主程序。主程序里面用 Create 创建一堆线程，每个线程有自己的函数，然后在线程中调用 Yield 来释放 CPU，让 CPU 在多个线程（指令序列之间）进行切换。把这些函数都实现了，然后把它们统一编译在一起，出来的东西不就是刚才的那个浏览器吗？这就是用户级线程完整的样子。

我们再回过头来回答那个问题，我们为什么讲用户级线程、分治的方法。我们下节课就要进入到内核，这个用户级线程切换，实际上是内核级线程切换的子部分。所以我们首先讲清楚这个子部分，而且这个子部分是可以单独使用的，把多线程浏览器中的函数都写完，跟操作系统没有任何关系，这是个应用程序。

为了下次课做准备，我们引出什么是核心级线程。

什么是用户级线程呢？它的执行完全不用到内核里，这些线程都是在用户态切来切去，操作系统完全感知不到它们的存在。

用户级线程也有着它的毛病，比如 GetData 线程访问网卡 IO（访问硬件必须要经过操作系统），进入内核后可能网卡比较慢，出现阻塞，这个时候内核就要切换到别的进程去执行，这个时候这个浏览器仍会是一片空白。

从这个例子中也可以解释一个现象，比如浏览器，如果网特别卡的时候，搜狗浏览器打开一堆标签，每打开一个标签都是一个线程，而且很多都是用户级线程，一旦一个用户级线程卡了，在内核中卡了，那么别的标签也动不了了。因为一旦卡了，就切到别的进程去执行了。切到别的进程去执行后，那么浏览器的这个进程就不再执行，你按什么都不好使了。

这就造成了这样一个效果，虽然通过用户级线程启动了多个任务序列，但一旦在内核中阻塞，那么这多个序列启动的并发现象，没有任何效果。如果系统中没有别的其它进程，那么 CPU 只能在这里空转。

而核心级线程就不一样，Create 是系统调用，要创建线程的时候，就要进入到内核，所以 TCB 在内核中。内核级线程的并发性要更好一些（例如 GetData 在内核中阻塞了，但是缓冲区里已经下载了部分数据，那么这时就可以切换到 ShowText 线程中去）。

这一节我们讲了，从一个栈到两个栈来支持线程的切换，但是这一个栈、两个栈完全是用户栈，根本没有进入到内核。核心级线程的切换，调用函数叫 Schedule，而用户级的线程切换，调用的函数叫 Yield。Schedule 具有调度的特性，内核接管这些线程，要调度线程；而 Yield 呢，完全是用户的主动释放。

这两个英语单词本身的含义也有差别。Schedule 对用户来说完全不可见，是由操作系统决定的。所以核心级线程完全是由操作系统、完全是在内核中去做的，这就比用户级线程要复杂。虽然复杂些，但用户级线程是核心级线程的基础，学会了用户级线程对核心级线程的理解，起到非常重要的帮助作用。

L11 内核级线程

上一讲我们讲了用户级线程，我们看到用户级线程是如何切换的，以及是如何创建的。用户级线程切换的核心，就是从一个栈变成两个栈，每个线程有自己的栈，有自己的 TCB ，切换的时候首先切换 TCB，再切换栈。

创建的时候，就是将要切换的那个 PC 指针放到自己的栈中，然后再创建好 TCB。将来在切换的时候，首先通过 TCB 一切换，再切换到相应的栈，从栈中弹出地址（ PC 指针）去执行。

这节课我们要讲，核心级线程是怎么做到的？核心级线程怎么做？实际上我们讲了，为什么要讲线程呢？本来要讲进程的切换，但是我们将进程的切换变成两个部分，切换指令流和切换资源。切换资源的内容，将会在后面的内存管理中讲。而切换指令流呢，实际上就是切换线程。因为进程是在内核中，没有用户级进程这一说法。

实际上，切换进程真正的是切换内核级线程，而不是切换用户级线程。但是我们说了，切换用户级线程对切换内核级线程的理解，是非常重要的，而且用户级线程的切换是内核级线程切换的一个部分。

大家可能会问，为什么没有用户级进程呢？也就是为什么进程必须在内核中？因为进程要分配资源，要访问内存，可能还要访问文件等。这些东西都是计算机硬件、系统的资源，那么在用户态是不行的，必须要在内核态才能访问、控制这些资源。

接下来我们就开始学习如何切换内核级线程。

上一讲最后我们说过，核心级线程有它自己的优点、特点。所以，一个系统往往有用户级线程、核心级线程和进程，这三样东西都有。这样的话，系统才能足够灵活，操作系统才能发挥它的价值。为什么会有核心级线程呢？它有什么优点呢？实际上有很多，大家吃透一个，弄懂一个就可以了。

如果一个系统不支持核心级线程，多核实际上是没用的。多核要想充分发挥它的作用，必须要支持核心级线程。

多核和多处理器的区别：看是否每个 CPU 有自己的缓存、MMU（内存映射）。多核用的是同一个 MMU ，所以用的是一套映射。

那么大家想想，一套映射，多个执行序列用一套映射，这不就是线程吗？只有到内核以后，才能把任务分配到物理设备上（CPU 上），多个线程可以执行在多个核上，而且用的是同一套 MMU。所以，多个线程可以使用多个核，利用多核可以并行处理任务（注意和并发的区别，并发只有一个计算资源，且交替执行）。

为什么不是用户级线程呢？如果是用户级线程的话，操作系统是看不到的。操作系统看不到的话，那么自然就不能给它分配硬件。

核是由操作系统管理的，如果仅仅在上层的进程里的线程，切来切去，那是没法使用多核的。所以，多进程也不能发挥多核的价值（每个进程有自己独立的 MMU），用户级线程也不能发挥多核的价值。因此，核心级线程是有它的优点的。

这也体现了操作系统较为繁琐的特点。而为了充分利用多核的特点，应该支持核心级线程。现在大家用的都是多核机，有必要好好学习一下核心级线程。

那么接下来我们看看核心级线程是怎么做出来的，我们这个课程讲的就是，操作系统是怎么做出来的。

我们从用户级线程引申出来。用户级线程从一个栈到两个栈，而核心级线程是一套栈到两套栈。

核心级线程在用户态执行的时候，要用用户栈（会发生函数调用）。而到内核的时候，要用内核栈（在内核也会发生函数调用）。所以，核心级线程既要在用户态跑，也要在内核态跑。因此，这个时候就不是一个栈，而是一套栈。

用户级线程和核心级线程有什么本质区别呢？用户级线程用的是两个栈，而核心级线程用的是两套栈。在用户级线程中，一个栈关联一个 TCB，TCB 的切换引起栈的切换。而核心级线程中，一个 TCB 关联一套栈（用户栈和内核栈）。当然，这个 TCB 在内核里面，在内核里面切换 TCB 时，要切换两套栈。

我们接下来实际上就要看看，这两套栈是什么东西？什么时候会出内核栈呢？进入内核，在内核中跑的时候（在内核中会调用其它函数）。什么时候进入内核呢？在前面我们讲系统接口时讲过，进入内核的唯一方法就是中断（当然不一定是 INT 指令，也有可能是按下鼠标、键盘的硬件中断或时钟中断等，虽然 INT 指令也是一种中断）。只要中断了以后，就要到内核栈。Intel 采用硬件来做，只要一有中断，就启用内核栈。

在下堂课我们讲代码的时候，我们会看一下怎么找到内核栈呢？这里我们只是画出来每个线程都对应一套栈。在用户态执行的时候，就用用户栈。一旦 INT 指令出发的时候，操作系统就通过一些硬件的寄存器，找到这个线程对应的内核栈。找到内核栈以后，还要压一些东西（源 SS，源 SP，它们就是用户态下的栈，还要压源 CS 和源 PC，也就是压，在用户态执行时，执行到的位置）。

因此，一旦 INT 以后就启用了内核栈，并且和用户栈相关联（通过指针，像拉了一条线上去）。理解这幅图是理解这套栈的基础。

IRET 就是返回，把这 5 个寄存器的值往回弹，根据指针找到相应的用户栈。所以 INT 和 IRET 就通过内核栈，分别压入、弹出这 5 个东西，实现了这一套栈的思想。

有了这个基本思想，就知道一套栈长什么样子。接下来我们还采用原来的套路，仍然找一个具体的例子，我们来做一下、看一看，带着中断进入核心级线程，看它会怎么切换。

认真体会从内核返回（中断返回）时的样子。

call sys_read; 执行完后，紧接着就会执行 1000 地址处的程序，在内核中移动执行。

在内核中执行的时候，sys_read() 启动磁盘读，这时将自己变为阻塞，一阻塞就会引起调度。

核心级线程切换的思路和用户级线程切换的思路非常相似。用户级线程切换，是找到 TCB，切换 TCB，切换用户栈；而核心级线程切换，是找到 TCB，切换内核栈。当然，这时找到 TCB 需要进入内核，才能找到 TCB。

所以，首先需要进入到内核，用的是中断。在 TCB 完成切换后，就要根据新 TCB，完成内核栈的切换。内核栈切换完以后，再用 IRET 指令把相应的用户栈切过来。所以是从一套栈切换到另一套栈，这样两套栈之间的切换。

但切换的具体步骤，是先进入到内核，找到 TCB，切换 TCB，切换内核栈，然后根据中断返回，切换用户栈。它不是一段代码，而是分布在不同部分。这就是我们要讲的，内核级线程切换的五段论。

内核级线程的切换，原理就是这个图，两套栈之间的切换。虽然画起来是这样，但是具体实现起来，却是蕴含在操作系统很多地方。下节课我们会把这些代码再详细展开来看 Linux 0.11 这个小内核，它里面是具体怎么做到的？实际上，光听一听、看一看，你是肯定学不会，我敢断言。

关于这段 PPT 还有用户栈的切换，尤其是这个核心栈的切换，大家这段录像至少翻来覆去要看几遍，你才能明白它大概是什么样子。

这种明白还没有到位。前面我们讲了，实验一是做系统启动，在屏幕上打印出自己的 LOGO。实验二是增加系统调用 whoami()，实验三我们下堂课会说，实验三比较简单。这一节，这部分内容对应的是实验四。

实验四就是在 Linux 0.11 上实现这套切换。Linux 0.11 现在用的切换机制和它不太一样，但很类似。要是把这套东西，这套完全基于内核栈的切换、这套想法、这套思想，如果在 Linux 0.11 上、在那个小内核上能做出来，你这一部分就真的明白了。

大家认真去阅读那个实验指导书，去把它做出来。做不出来，那么听这一部分、听完了也没什么用。操作系统就有这样的特点，如果只是听我讲一讲，在纸上画一画，那么这样学操作系统没有什么价值，除了考考试。虽然我们这个课程绝对可以让你复习考研，但是，我们讲的内容要远远超过考研。我们是真正地让大家明白，一个实际的操作系统是怎么运转起来的？你怎么才能把它做出来？

所以大家一定要认真去做那些实验，做关于这一节的第四个实验。这个课程配套有八个实验，实际上，我给我们哈工大的学生上课的时候，我们安排的一共是十二个实验。其中，前八个实验和这个在线课程的八个实验是一样的，后面四个是大型实验。做完这十二个实验，我敢断言，操作系统你是真学会了。

当然，这里面除了这五段，还有一个附加段是关于进程切换。而在这节中，我们讲的都是线程切换。进程切换还要切换映射表，而映射表怎么切换，到时候会在内存管理中讲。但是别忘了，如果是进程切换，另外将内存（映射表）一切换，也就过去了、完事了。

那么，内核级线程切换的样子就搞明白了。能完成切换后，在初始化创建一个线程的时候，就创建成能切换的样子。要创建成能切换的样子要干什么呢？无非就是有用户栈、有内核栈、有 TCB，完成用户栈和内核栈的关联，完成 TCB 和内核栈的关联。

首先，申请一段内存作为 TCB。然后再申请一段内存作为内核栈，并对内核栈进行初始化。之后再申请一段用户态的内存，置好用户栈。最后 TCB 关联内核栈。

所以大家可以看到，一旦要是明白了栈是怎么切换的？用户级线程是怎么切换的？怎么通过 TCB 切换内核栈？怎么通过内核栈切换用户栈？那么，创建一个线程的 Create 函数，就变得很简单了。

到现在为止，用户级线程和核心级线程的切换和创建，都已经讲清楚了，原理都已经讲清楚了。下次课我们将要讲，核心级线程它的代码到底是怎么写出来的。实际上我们要讲 Linux 0.11 那部分关于进程的代码，因为 Linux 0.11 是不支持核心级线程。但是我们说核心级线程和进程非常像，只是核心级线程没有资源（映射表），如果加上映射表的话，核心级线程就是一个进程。

所以，我们通过对 Linux 0.11 的进程进行剖析，来讲核心级线程到底是怎么做出来。最后在这里，我们把用户级线程和核心级线程做一个对比，也算是结束、梳理这一节。

大家可以看到，用户级线程、核心级线程以及把用户级线程和核心级线程合在一起，在操作系统里面都很有价值。可以看到，如果使用用户级线程和核心级线程的组合，那么它的优点非常大。

我们这一部分就讲到这里。这一部分完成了一件工作，即要明白进程是怎么切换的。

实际上这里我们用线程的切换，来讲进程是怎么切换的，即两个执行的指令序列是怎么切换的。这个切换是操作系统的核心图像。多进程图像的核心，就是能切换、能交替执行。

我们在这里用线程的观点，用户级线程、核心级线程，用户栈、内核栈、一套栈、TCB 等等，用这些概念讲清楚了怎么进行切换。然后附带讲了，什么是用户级线程，什么是核心级线程，什么时候用用户级线程，什么时候用核心级线程。

我们的操作系统，既可以支持进程，也可以支持线程。所以学完了这一部分，大家应该能够在不支持线程的操作系统上，实现出支持用户级线程、支持核心级线程，能够写出支持线程的代码。

实际上，前面我们说过有八个小实验，四个大实验。这四个大实验其中的第一个实验，就是在 Linux 0.11 上，这个不支持线程的操作系统上，实现核心级线程。

不过要把它做到真正核心级线程的样子，还是非常困难。老师带了很多年，大概带了六、七年的本科生操作系统课，真正实现核心级线程，完全由 TCB、完全用栈来进行切换、完全实现这个机制的，往往一届也就那么一两个。所以总共大概有十个人左右，这些人都非常厉害，我认为它们是真正学会操作系统的人。

L12 内核级线程实现

这节课我们要讲，核心级线程到底是怎么做出来的？实际上就要讲核心级线程代码的实现。

前面我们讲了，用户级线程和核心级线程分别是如何进行切换的，以及要想进行切换，它们具有的样子，应该是怎么样的。也就是说，用户级线程和核心级线程的切换，在纸上的样子，即它们的原理是什么样的。

这节课我们要讲的是代码的实现。为什么这里主要强调，核心级线程代码的实现呢？因为进程实际上由两部分组成，一部分是资源，另一部分就是执行序列。而里面的执行序列，实际上就是线程。而进程又必须进入到内核，所以，进程里面的执行序列，就是核心级线程。

所以，学会了核心级线程它的代码实现，那么进程的代码实现，就是再加上另一部分，即资源。对进程的资源的管理，主要是内存管理。通过后面要讲的内存那一部分，那么进程就可以用代码在内核中、在操作系统中实现。

一旦完成了进程在操作系统中的实现，那么，距离一个完整的操作系统就不远了。当然，为了实现完整的操作系统，一个能完整运行的操作系统，你可以不支持核心级线程，可以不支持用户级线程，但必须要支持进程。因为只有支持了进程，操作系统就管理好了 CPU。如果操作系统没有管理好 CPU，那么，这个操作系统就不能叫一个操作系统。

把这些话整理一下就是，我们必须要学会核心级线程代码是如何进行实现的，再加上后面要讲的内存管理那一部分中，关于进程那部分代码的实现，把这两个部分合在一起，进程就可以实现。这个操作系统，这架钢琴中最核心的那部分就有了。

我们一开始说过，我们要实践、要做一个操作系统出来，就是具备能编写基本操作系统的能力。所以，这一部分是必不可少的。接下来我们看看，核心级线程要想用代码实现，它必须要写哪些关键性代码。

首先，我们再具体回顾一下，核心级线程要想实现，那么它应该在纸上是什么样子？核心级线程的实现，关键在于两套栈之间的切换。整个过程就是从用户栈到了内核栈，从内核栈到了 TCB，然后 TCB 完成切换，TCB 切了后，内核栈也就切了，再通过 IRET，实现用户栈的切换。

当然，从用户的角度来说，内核中的内容对用户来说都是隐藏的。因此，核心级线程切换时，从用户的角度来说，就是从一个用户栈，切换到另一个用户栈（指令执行序列 PC 指针也切过去了）。但是，中间进行了 5 段过程。

这就是我们所说的五段论，我翻来覆去讲了很多次，这个图我希望大家留在脑子里。也就是说，只有这幅图像在头脑中形成了，那么后面的代码你才能看懂，才能顺理成章。

因为这一节我们主要讲代码，那么接下来就开始看代码。从 fork() 这个系统调用引起的中断开始。

为什么选择 fork() 呢？因为它不仅仅是，进入到内核，有可能引起切换（比如时间片到了，不应该让你再执行了，操作系统就会开始切换），而且它本身是创建进程的系统调用。

对于进程我们说过，是由资源和执行序列两部分组成。因此也要创建资源和创建执行序列，而创建执行序列，实际上就是创建线程。fork() 里面对应的这部分代码，实际上就是创建线程的代码。

因此，我们从这个点切入，就可以看清楚两件事：第一件事是怎么切换？切换的五段论是怎么具体实现的？第二件事就是一个核心级线程要想创建，需要做哪些事情，是不是我们前面所说的，只要制造成能够切换的样子就可以？所以，我们这里选择 fork() 。接下来我们就详细展开代码。

一旦开始执行 INT 指令时，CPU 马上就会做这样一件事情，找到当前的内核栈，在内核栈中压入 SS、SP（表示用户栈的内容）等。在 INT 指令执行的时候，还没有进入到内核，执行完以后才进入到内核。

内核栈长这个样子必须非常清楚，后面我们还会再说，这个很重要。分析到内核栈中 ret=??，接下来要干什么？刚才我们从 fork() 开始讲这个故事，为什么从 fork() 开始呢？因为我们要进入内核，进入内核就是要从中断开始，我们选择了 fork() 这个中断来开始。

我们前面也一直强调过，我们这个课，大家学习操作系统的时候，要自己会思考，自己会寻找答案。大家在做操作系统的时候，哪怕在做一个模块的时候，你会遇到各种错误，而这种错误一味着等着别人去告诉你，那么我告诉你，你永远也做不出一个模块来。

因为操作系统里面的东西，实在太复杂，必须自己有清楚的认识，有个清晰的思维过程，就是我知道接下来我应该考虑什么。这就是人的思考过程，我们前讲什么寻找答案，寻找答案就是有个清楚的思考过程。

现在这个思考过程不乱，也不是说很难，大家只要捋着这条线一定会弄明白。捋着什么线呢？就是你在头脑中形成一个计算机，你去执行。那么接下来问题到哪了？就要执行 INT 0x80 指令。接下来要执行什么，就要看 INT 0x80 的中断处理函数是什么，前面我们讲过，就是 system_call，所以接下来要执行 system_call。

system_call 要干什么呢？还要进行压栈。大家想想，这个时候这些寄存器是用户态还是核心态的？因为刚一进入核心态，那个时候的 CPU 的寄存器肯定是用户态的。所以，仍然是把用户态的一堆东西记录下来。这个大家就可以看出，这就是把刚才用户态执行的样子，执行现场在内核栈中保存起来。

这不很显然吗？你要在用户态执行的时候，跳到内核态、进入内核栈。将来在返回来的时候，还要用这些现场、还要用这些内容。所以，将来再弹回去，这也就看起来很简单、直观。

接下来执行 sys_fork，通过调用这张表进入到内核中，具体去处理 sys_fork，具体去做 sys_fork 这件事。所以，接下来要在内核中执行系统调用，也就是这个中断最后产生的真正效果（即 sys_fork）。

那么再回顾一下，前面我们说过，切换有五段论。第一段是中断入口，实际上是建立用户栈和内核栈之间的关联，这里已经建好了。那么接下来就要进入内核，在内核中执行。在执行的过程中，可能会遇到阻塞，这时就会发生切换。当发生切换时，就是核心级线程切换五段论中的中间三段，对于这中间三段我们先不看。

刚才说了这么多话，实际上就是希望大家在这里能够分析出来，在执行 sys_fork 的时候，可能会发生切换。那么在引起切换时，具体是怎么切的呢？接下来再看看代码就明白了。

接下来把 _current 置给 %eax，然后判断一下 state(%eax) 。这个汇编实际上是 state 加上 %eax，也就是 state 再加 _current，而 _current 是 PCB。所以，接下来就是要看 PCB 中的 state 是不是等于 0，如果不是，那就要调度。

所以这种做法是，你在内核中执行一个东西，然后把状态置成非 0，接着跳到 schedule 去执行。执行完 schedule 以后，schedule 就要完成这个栈的切换，即完成切换五段论中的中间三段。这中间三段待会儿来看，实际上也非常简单，我们先来看五段论中第五段，即最后一段。

在 cmpl $0, state(%eax) 、 cmpl $0, counter(%eax) 中，如果这两处判断为阻塞情况的话，都会跳到 reschedule 去执行。而 reschedule 里面执行的就是 schedule 函数，就是调度，完成中间的切换。一旦切换完成后，又会回到 ret_from_sys_call 这个函数，即实现从中断返回，这里是从系统调用返回，接下来就要执行中断返回函数。

所以大家可以看到，整个故事它在代码实现的时候，是通过中断进入了内核，然后中间在适当的时候调用了 schedule。schedule 执行完以后进入中断返回，在中断返回的时候，要进行从内核栈到用户栈的切换，IRET，就是这样的一个过程。

接下来我们就来看下这个中断出口，这是五段论中的最后一段。我们的讲法是先讲第一段，再讲最后一段，然后再讲中间的三段。

最后一段，在 ret_from_sys_call 中干了什么呢？一堆的 pop；而入口是一堆 push，相互对应。在 pop 完事以后，开始执行 iret。即把放在内核栈中用户栈的内容，pop 出去，它 pop 出去以后，切换出来就是下一个核心级线程、实际上也是下一个进程执行起来的那个用户栈，这就完成切换了。

大家可以看到，实际上这个代码也不难。INT 指令值自动有的（它自动执行一些 push），然后紧接着 push 一大堆（记住你要 push 哪些值），中间调用了一些内容（按照他的这个套路做就可以了），调用完以后再调用 schedule，schedule 返回后就去执行 ret_from_sys_call。这个函数里面包含一堆 pop（和最开始的 push 对应），pop 完以后再 iret，这就完事了。

这个代码之所以复杂，就是因为这切换五段论，这五段代码包含在、遍布在操作系统的多个地方。如果我不这么讲，大家不这么学，你可能完全懵。但是，如果这么讲完了，这么学完了，你会发现这个在头脑中，已经明白它是怎么一个逻辑关系，那么这个实际上也很清晰。

明白这个逻辑关系后，在实验四中就真正地用内核栈完成 Linux 0.11 的进程切换。做完这件事，你也就深刻地明白，我刚才讲的这一段内容。所以，入口和出口这两段我们讲完了，中间这三段，即 schedule 引发的东西，实际上也很简单。

schedule 第一个引发的东西，就是调度。找下一个进程或核心级线程，怎么具体去找呢？后面我们讲调度的时候，会拿出两讲来讲调度算法。在调度完以后就要完成切换，这个时候 next 已经是下一个进程的 PCB 或下一个核心级线程的 TCB 。

在下一个线程的 TCB 找到后，接下来就要进行 switch_to（既然下一个线程的 TCB 已经找到了，那么 TCB 的切换就很简单，直接修改一下就完事。）。这里核心是要根据 TCB，完成内核栈的切换，以及包括通过内核栈，完成在内核中执行序列的变化。不光内核栈要切，PC 也要跟着切。

那么，接下来我们就要看这个 switch_to。switch_to 是怎么做到完成切换的呢？如果这个时候真的是用内核栈来完成这个切换，那么也就没有大家的实验四了。

这里面（Linux 0.11）它用的是 TSS（Task State Segment）来进行切换。我们待会稍微说说，这种切换是什么含义。关于这个东西的详细介绍，在实验四中有。实际上是基于 TSS 的切换，而变到基于内核栈（Kernel Stack）的切换。也就是 Linux 0.11 的切换，是基于 TSS 的切换，而我们实验四的目的，就是要把它变成基于内核栈的切换。

那么，基于 TSS 的切换是个什么样子呢？实际上它的指令写起来更简单，但它执行效率比较慢，这也是改造它的原因。

现在的操作系统，除了小 Linux ，像 Linux 0.11这种小 Linux，Linux 2.6 以及 Windows 用的都是基于内核栈的切换。虽然基于 TSS 切换的 Intel 结构给做出来了，做出来以后，它的切换实际上只需要一句指令 ljmp %0\n\t ，这样的一句长跳转指令就可以做到。但是，这句指令执行起来特别慢。

接下来就看看这个 TSS 是怎么切换的？它是通过长跳转指令做到这件事的。实际上这个长跳转指令是跳转什么呢？别忘了 TSS 全称中的 Segment，所以实际上跳转的是 Segment 。它这个是什么样的思想呢，这里就要说了，既然是 Segment，Segment 是一个段，每个段都有一个段描述符，所以段描述符就是一个指向段的指针。

而有段描述符就有选择子，这个选择子是 TR。TR 是操作系统的一个固有寄存器（和 CS 是一样的），这个 TR 就是用来找到这个段的。所以用 TR 这个选择子，找到段描述符，再根据段描述符，找到相应的段。而那个长跳转指令，就是段与段之间的跳转。段与段之间的跳转，实际上就是段寄存器的变化。所以，实际上就是接下来再找一个段寄存器。

新的 TR 就是 TSS(n)，n 表示的是 next，TSS(n) 就是下一个进程对应的那个 “CS“。所以，下一个进程有一个 TSS(n)，这个 TSS(n) 就像 “CS”，表示下一个 TR，TSS(n) 指向的是新的 TSS 段。长跳转指令就是更改 TR 的值把 TSS(n) 赋给它，TR 变了以后，就会找到新的 TSS 段。

TR 表示当前 CPU 里面对应的 TSS 段，而要是当前 CPU 的TSS 段一变，那么新的 TSS 段的内容就要载入到 CPU 里。TSS 段里包含 CPU 里所有的寄存器，一旦 TR 指向的段描述符改变以后，就表示用新的 TSS 了，而这个新的 TSS 里包含的 CPU 寄存器的值会复制到 CPU 的寄存器里。不过在更新 CPU 寄存器的值之前，还需把更新前的所有寄存器的值保存到先前那个 TSS 里。

根据刚才的说法，我们再来捋一捋。

ljmp %0\n\t 这个长跳转指令怎么解释执行呢？把当前 CPU 的所有寄存器的值，放在当前 TR 指向的 TSS 中，这是跳转前的准备工作。

在找到 TSS(n) 后，把 TSS(n) 置给 TR ，不过在置给 TR 之前根据 TSS(n) 找到新的 TSS。把这个新的 TSS 里包含的所有 CPU 寄存器的值，赋值给 CPU 的寄存器。那么，之后 CPU 再执行的时候，就完全用新的东西了。

当然，这里面你可能会说，老师你不是要完成栈的切换吗？CPU 的寄存器里有 ESP，EBP 等寄存器，那么，直接通过 TSS 置换的话，栈也就切换过来了。

这个 TSS，实际上就是 TCB 中的一个子段。后面大家会看到，实际上在这里，它就是 PCB 中的一个部分。所以，这也是根据 PCB 找到 TSS，根据 TSS 再对 CPU 的寄存器的值进行切换。这也能完成切换五段论中的中间三段，效果是一样的。

但是，这种方法慢。因为它更新 CPU 里面所有寄存器的值，而且是用一条指令来完成。因此，这条指令会做得非常复杂，并且一条指令也不能进行指令流水（这是一种硬件设计），所以这条指令执行的速度就慢，不能充分利用现在 CPU 硬件的一些加速的方法。因此，后来把这条指令都改成基于栈的做法，我们的实验四也是在做这件事。

好了，中间的这三段我们就不再说了，已经讲完了。这三段完成了栈的切换以及 eip 的切换。那么将来在中断返回时，通过 iret 再完成用户栈的切换，那么五段切换就全有了。所以，第一个故事用代码就讲完了。大家可以看到，实际上核心就几句代码，就三句，第一句 INT，第二句是 switch_to 中的 ljmp，第三句是 iret。再加上其它代码把它们包裹起来，所以，总共加起来不会超过二三十句，操作系统最核心的发动机也就这二三十句。

当然，如果把它改成关于栈的切换的话，也不会超过一百句。大家认真去做实验四，就会明白这个道理。

接下来是第二个故事，就是 fork、Create。实际上把切换弄完以后，后面的就好讲多了，代码也好写多了。我们说过，创建一个核心级线程，就是要做出能切换的样子。大家可以看到，刚才切换时完全靠 TSS。所以，采用这种方式去切换的话，只要把 TSS 设置好，其它的东西就容易多了。

根据这一点大家可以想象得到，接下来创建的核心是把 TSS 做好。当然，TSS 要想做好的话，首先得有 TCB (PCB)，有了 TCB 以后需要内核栈，然后再把 TSS 做好，做好了将来就可以进行切换。我们来看看是不是这样的代码。

_sys_fork 里会调用 _copy_process，为什么叫 _copy_process？这也体现了 fork 的含义，fork 就是一个叉子，调用 fork 的父进程在创建子进程时，采用 copy，即拷贝自己的东西。待会儿你会详细地看到，它真的拷贝自己的东西，所以父子进程就像叉子前端的两股，很像。

跳到 copy_process 处执行时，这个函数传递了一堆参数，但是调用 _copy_process 时没有给它传参。实际上这些参数都在内核栈里，因为父进程要进入内核，执行 fork 的时候，在内核栈里压了一堆的东西，这些东西主要是父进程在用户态执行时的样子。这些样子需要传递给 copy_process，不然怎么能做出和父进程一样的东西呢？

因此，需要把它们传递给 copy_process 才能做出一样的。（汇编调 C 函数的时候，实际上 C 的核心是一样的，一个 C 函数执行的时候，它的参数是从栈中取出来，当然，这个时候是在内核中执行，因此就是内核栈。所以，这里面利用内核栈的内容，来做成 copy_process 的参数。有了这些参数，就会知道父进程长什么样。在这个 copy_process 里面，就能做出和父进程基本一样的叉子。实际上完全一样，只有一个地方有点小差别，待会儿一说就明白。）

在 C 中用栈来取参数时，函数声明的参数中越定义在前面的越在栈底（大家可以看到操作系统不好编吧，是不好编，要求大家对 C 语言非常熟悉）。

接下来就要进行 copy_process 的工作了。大家可以看到获得了一页内存（get_free_page()），什么叫一页内存呢？怎么获得呢？实际上后面我们在内存管理中会讲。这个时候为什么不能用 malloc 呢，因为 malloc 是一段用户态的代码，现在在内核中，必须要用内核态代码，get_free_page() 是内核态代码。对 get_free_page() 返回的地址做了强制转换，申请的这一页内存就来做 PCB 。

有了这个 PCB 以后，接下来做了些什么事呢？大家可以看到，这不就是典型的设置 TSS 吗？esp0 就是内核栈，esp 就是用户栈，这是硬性规定好的，就不详细展开了。

父进程和由它创建出来的子进程的用户栈是一样的，但内核栈不一样。如果内核栈也一样，那就没法区分了。因为你既然是一个线程嘛，你就必须得有自己的 TCB。在这里是进程，你就得有自己的 PCB，有自己的内核栈，在内核中分开。

但是，我们可以共用一套用户的东西。由于内核栈分开了，在操作系统中认为它们是两个东西。在用户态，可以指向同一个东西，可以执行同样的代码，用同样的栈。但是，在内核中是分开的，所以是两股叉。

这就是核心级线程创建的过程，在这 5 句指令中，最核心的就是这 3 句指令。这 3 句指令完成什么事呢？创建 TCB，创建内核栈，创建用户栈，关联栈和 TCB。

我们前面讲过。要想创建一个核心级线程，它核心的工作就是创建 TCB，创建用户栈，创建内核栈，关联栈和 TCB，初始化两个栈（用户栈、内核栈）。

现在大家可以看到，就这么 3 句指令，创建核心级线程的 5 个部分中 4 个部分已经做了。接下来是填写这两个栈。实际上，填写这两个栈都没有必要。因为现在完全是靠 TSS 进行切换的。而我们说过，实际上填写这两个栈的目的，主要是把什么压到这两个栈呢？把 eip 压入栈。

而现在完全用 TSS 来做，因此不需要再填写这两个栈。所以，创建核心级线程的基本工作全完成。接下来再用 TSS 一初始化就完事。

在 TSS 初始化中，把 eip 放进去，而这个 eip 也是从 copy_process 函数声明的参数中传进来的。这个 eip，正好也就是父进程的 eip，这个 eip 是什么呢？正好就是 INT 指令执行完后的下一句指令的地址。

一旦子进程创建好后开始执行，那它会怎么做呢？eip 指向 mov res,%eax （PPT 第 3 页）这条指令。因为用的肯定是和父进程一样的用户代码，所以 eip 等于它。

而刚才 TSS 初始化时 eax=0 ，因此子进程一上来执行这句话时，会把 eax 置给 res ，即 res=0 。

在调用 fork 时，有个经典的结构 if(!fork()){...} 。在父进程调用 fork，中断返回后执行什么呢？也执行 mov res,%eax 这句指令。不过父进程在执行这条指令时，eax 不为 0 ，至于为什么，这个我不讲了，大家去看代码，去剖析去吧，也不难。

父进程的 eax 不为 0，那么 if(!fork()) 中的条件判断为 false，也就不会去执行条件判断成立时的指令。而子进程由于 TSS 初始化时 eax=0 ，这个值置给 res，再一返回 res，if(!fork()) 中一判断，条件成立，所以子进程就执行 if(!fork()){...} 中的代码。

把前面讲的整理起来大家可以看到，一个子进程创建好了，而且还能分开子进程、父进程，靠的是 TSS 初始化好了，TSS 初始化好了就可以完成切换。

子进程的用户栈和父进程用同样的栈，紧接着创建子进程自己的核心栈、TCB，并且用几句指令把它们关联好。好了，第二个故事，核心级线程（进程）创建的故事就完事了。

我们前面讲过，调用函数创建一个线程时，还要给它传递一个函数作为参数。那么，这个 A 怎么执行的呢？怎么把函数 A 弄进去呢？我们这里不讲这个概念，因为 Linux 0.11 是不支持创建线程，它支持进程，而一个进程执行起来的时候，可以是执行自己的代码，自己的代码不就相当于自己的 A 函数吗？

我们讲这个代码，这就是典型的 shell：

int main(int argc,char* argv[]) {
  while(1) {
    scanf("%s",cmd);
    if(!fork()) {exec(cmd);} 
    wait(0);
  }
}

shell 的时候创建了一个子进程，如果是子进程，那么 if(!fork()) 条件判断成立，会去执行 exec(cmd); 。假设 cmd 为 ls ，那不就执行命令了吗？所以子进程就要执行自己的函数，不再执行和父进程一样的函数、代码。

因为如果执行父进程的代码，不就相当于又执行 shell 了吗？那这个是不对的。所以子进程用了父进程给它创建的壳子，在这个壳子里面它要继续执行自己的程序 ls。

我前面讲过，在给哈工大学生上这门课时，总共有 12 个实验，前 8 个实验是这个在线课程大家要做的。如果对后 4 个实验感兴趣的话，我哪一天在大家做实验时会留下一个链接，大家可以根据这个链接，登录到我们的实验平台上。

登录到这个实验平台后，你们会看到后 4 个实验，其中一个实验就是创建核心级线程。而创建核心级线程就要用到这些东西，这个功能必须要用，如果大家感兴趣要做的话，可以仿照这个来写。这部分代码、这个故事，我们主要讲 exec(cmd); 是怎么做出来的。那么，exec 是怎么做的呢？这就要看 exec 是怎么进去执行的。

exec 是怎么进去的这个故事，需要从 exec 这个系统调用开始。执行 exec 的这个系统调用时，会调用 sys_execve 函数。现在我们要到内核里去执行。exec 是个系统调用，这个系统调用要进入到内核。进入内核在 exec 未执行实际工作之前，子进程会执行什么代码呢？fork 做成了一个叉子，这个叉子父进程和子进程执行同样的东西。那么， exec 相当于替换这个由父进程创建的这个壳子里的内容。在未替换之前，子进程和父进程执行的应该是同样的代码。

那么，一旦子进程用 sys_execve 进去以后，在执行的时候，将来一旦从内核态退回来时，子进程就要执行新的代码，比如说 ls 的第一句代码（一段程序的第一段代码一般都叫 entry，即入口）。在子进程的函数进入之前，子进程和父进程执行同样的代码。一调用 exec 进入到内核态，在内核态一顿折腾以后，从内核态返回后，执行的就不再是和父进程一样的代码，执行的就是 ls 的入口，这个东西怎么做到的呢？

大家想想，在中断返回后要执行什么？中断返回时要执行 iret 指令。iret 指令是怎么工作的呢？不就是从内核栈中，找出用户栈的这 5 个部分的内容，然后把 ret 里存放 eip 的值，置给 CPU 的 eip 寄存器。而 CPU 的 eip 寄存器的值表示的就是 PC，我们刚才也说了，要让 PC 指向 ls 的入口。

我说了这么多了，大家能不能把它联系起来。如果能把 ls 入口的地址找到，并且赋给 ret ，将来在执行 iret 的时候一弹出来，赋给 PC ，那么 PC 不就指向 ls 的入口了吗？一旦 PC 指向 ls 的入口地址，那么接下来执行的，不就是 ls 了吗？就是这样的思想，非常 easy。

在 _sys_execve 中要执行 _do_execve 函数，执行 _do_execve 函数前，对 %eax 进行压栈，为什么压这个栈呢？因为 _do_execve 函数需要传入参数 eip，而这个参数是什么呢？是 esp（当前栈指针）和 EIP（一个地址偏移）相加后赋给 %eax 的值。其中 EIP=0x1c ，0x1c 的十进制值为 28，所以 esp+EIP 正好是 ret 的地址，由于 ret 地址存放的是 eip 的值，因此正好把 eip 压入栈中。

而 eip[0] = ex.a_entry; 就是把要执行程序的入口地址置给 eip 。而 ex.a_entry 的值从哪来呢？可以读文件。ls 是一个可执行命令，这个程序 hello 是一个可执行文件，是命令。这个 hello 对应的是可执行程序，这个程序在磁盘上有，从磁盘上把这个程序读进来，读进来的时候就有个文件头。

可执行程序都有个文件头，文件头中就有相应的 entry 入口。大家再说说，这个东西从哪来的啊？编译的时候写进去的。编译过程中，做成可执行文件时写进去的。实际上是链接，链接做成可执行文件时写进去的。这个文件写进去后，就给 ex.a_entry。

在读文件时，把它读出来再置到内核栈中。在内核栈切换完中断返回时，执行 iret 后就弹回去了，开始执行 hello 这个程序的第一句话。

大家可以看到，这就是操作系统，它蕴含了好多内容。大家想想在这里蕴含了什么内容？要读写文件吧，要知道链接吧，要知道可执行文件的格式吧，然后要知道系统调用、内核栈长什么样吧，要知道内核栈的位置吧，要把文件头赋给内核栈的相应位置吧，要知道 iret 吧，其它的老师就不再举例了。

所以大家想想，一个操作系统要想变成系统，大家要想做出这样的系统，那么在头脑中得有多少内容，多少知识。大家必须要清楚，要有非常清晰的一个认识。

最后，我们用这个图来总结一下。前面讲的一些核心代码，什么创建啦、切换啦、switch_to 啦，这些前面都说过，它们最终实现的样子，都是这样子：从用户栈到内核栈，内核栈找到 TCB，TCB 通过 switch_to 完成 TCB 的切换，然后完成内核栈的切换，用 iret 再完成用户栈的切换，就是这样一幅图。

这幅图一定要留在脑子里，不要忘掉。明白了这幅图后，剩下来的就是写代码。而且写的核心代码也就那么三五十句，最核心的代码可能只有十句左右。把那几句核心的代码搞定，写出来后，把其它的东西丰富、完成，大家就能写出操作系统最核心的这些东西了。当这些核心的东西一旦写出来，其它的东西再不断地往上添加，操作系统慢慢、慢慢就出来了。

L13 操作系统之“树”

我们前面讲了 CPU 是怎么管理的，讲了让程序顺序执行时 CPU 效率低下，讲了处理的办法就是让多个程序执行起来，讲了进程，又引出了多进程图像，讲了实现多进程图像操作系统所需要的准备，讲了其中核心的准备就是交替执行。接着又讲了用户级线程是如何交替执行的、如何实现的，核心级线程是如何实现、如何交替执行的，还讲了很多源码。

那么也就是说，到目前为止我们讲了很多内容。每年到这个时候，我看到有很多同学就感觉操作系统真是理解起来非常吃力，它的确是，因为操作系统是一个人们创造出来的，最复杂的系统之一。而这个操作系统中最核心的 kernel，它的核心，肯定就是复杂的。

我们都知道，实际上是惯例，将 CPU 管理，即进程管理，和内存管理这两个部分合在一起叫做操作系统的 kernel。而 CPU 管理和内存管理的核心，那肯定是 CPU 管理，也就是进程管理。而进程管理的核心，就在于多进程切换这样一个结构。所以，我们前面讲的这些内容，是整个操作系统中最核心的核心。

那么，既然是最核心的核心，它的难度可想而知。因为操作系统本身就是一个复杂的系统，所以到这个地方大家感觉到吃力，是可以理解的。为了解决这个事，为了激励大家，又没有别的办法，所以每年讲到这个地方我都引入这样一堂课，就是讲操作系统的那棵 “树” 。

带着大家去整理前面的内容，带着大家也去训练好这样的思考能力。实际上就是训练好这样的思维过程，我需要带着大家去训练这样的思维过程，如何做出像操作系统这样的复杂系统。要有这样的一个过程，而且要有这样的决心，这就是我们这堂课的内容。

这棵树是 Linus 在 Linux 论坛上画出来的，当然，这棵树还在不断地变化，画的是目前为止 Linux 核心源码所形成的一种结构。大家可以看到，是非常复杂的一种树结构。这棵树再复杂，也是从一棵小树一点点出来的。我们接下来实际要讲的就是，操作系统这课小树是怎么在头脑中，从种子一点点酝酿，到后来长大、形成。

为什么要加入这堂课：

第一是希望激励大家；
第二，大家将来会面对很多复杂系统，霍金说了一段非常著名的话，他对 21 世纪这一百年整个科学的一个发展，总结了一下说：“在新的科学时代下，复杂系统、复杂的东西，将会成为核心。” 实际上这个不难理解，比如像大家见到的操作系统、互联网、人大脑工作的网络、一台设计非常豪华的汽车、一个非常大型的石油管道等这些系统，都是非常复杂的系统。而大家都知道，现在大家如果接触一下的话，做这些方面研究的人也非常多，非常热闹，比如做脑科学，大脑是怎么工作的？这是典型的复杂系统。所以，这一百年有人预计人类将会认清楚复杂系统。

无论多复杂的系统，它的想法，开始的想法，就像一棵大树一样，开始的想法都是那么一棵小树，一个小点，操作系统也不例外。这是第二个话题，希望大家通过这一讲，大家对复杂系统，大家能建立研究复杂系统或者建立能做出复杂系统的决心，以及能够有这个能力，从一个小点开始，不断地往外扩，从而形成一个复杂的系统。大家应该形成这样的能力，将来才能用计算机做出一些复杂的系统。因为，这个时代可能是一个复杂系统成为主体的一个时代。
第三个点，老师嘛，不仅仅是要教会大家操作系统是什么，就是说不仅仅在于授业，也在于传道。我希望通过这一讲，来树立大家去克服困难，从一个具体的点进去，逐渐扩大自己的思维过程，最后能够认识复杂系统，能够建立这样一个思维的能力、思维的过程，也形成这样的决心。我想这大概是，老师自己觉得操作系统这门课，带给我们的那个道、那个背后的精神，实际上这个精神对于很多情况都是适用的。

这个引用自一句非常著名的话，这个话很早就已经说过，很多年前一个哲学家就说过，大家可以去网上查一查它的来源。“The mind is not a vessel that needs filling, but wood that needs igniting!” 人的头脑不是一个盛水的器皿，也就是说，如果我们学习总是告诉你是什么，大家记住吧，找一个碗，大家脑子就像一个碗，老师说一点内容就往里面填，然后一层一层地这样记住，这是很多人学习的一个套路，尤其是我们国家，就是只学会了应付考试，为了考试，造成了这样的一个效果。

实际上这种学习，为了考试，形成知识的记忆还可以。但是，不能把知识转化为思考问题的能力，不能把知识转化为解决问题的能力，那么，这样的知识实际上是没有用的。它不是一个 vessel，而是一团需要被点燃的火。那也就是说，一团火嘛，需要根据一个点，从一个点开始不断地往外燃烧，那就是不断地向外思考，解决问题，求解问题。操作系统这棵树就是这样的，从一个点开始，不断地往外阔，不断地思维，不断地递进，只有这样你才能做出操作系统，你才能从一棵小树变成一棵大树。

接下来就开始我们递进的过程。我真是希望大家把自己的头脑变成一团火，而不像传统那样总是等着别人去灌输。而变成一团火、扩大这团火的核心就在于思考，就在于你的想法、你的思考。

所以思考、思索、探索答案，这是我们这个课程想要给大家传达的 “传道授业” 中的道，也是我希望大家形成这样一种意识。对大家来说，我认为会受益终身。

因为这个地方前面的内容都讲过，所以我们不再重复。我们只是体会一下操作系统这棵树长大的过程，算是一个整理就可以了。前面说过，我们要管理 CPU，使用 CPU，怎么使用呢？将 PC 置一下初值，那么它就可以取指、执行，取指、执行，CPU 就运转起来了，这是一个最初的想法，一个小点，一个种子。

然后紧接着思维开始递进，种子就开始发芽、要长大。

就形成多个程序切换的样子。

那么接下来马上就要想，多个程序怎么切换呢？用什么方式来做到的呢？既然是切换的话，不就是一种跳转吗？PC 的跳转，因此我们说过，用栈来做。

采用栈来进行跳转的话，那么就开始做一下吧。所以大家面对一个系统的时候，不是说一个一个模块把它做出来，然后堆在一起，缝在一起，那不可能。这种创造性的东西那肯定是做一做，想一想，把思维扩散开来。我先做一做，然后出现了问题，解决问题，再往前做一做。没有人告诉你第一段是什么，第二段是什么。

这种思维的递进过程非常重要，这样才让你的头脑真正成为一团火，而不再是那种一个注水的容器，那样你不会有任何价值，你的真正创造性和创新性是没有的。

Yield 不就是一种跳转吗，跳转完就去执行，看看它会产生什么效果。在执行的时候发现，没有顺利地切换回来，本应该在自己的栈内去执行，但又跳到另一个栈。所以，用一个栈来进行切换时，造成了混乱。

怎么做呢？自然而然的一种想法就是用两个栈来做。Yield() 的时候，要完成切换的时候，就是要切换两个栈。有了这幅图像，用户的多个执行序列间的切换，就可以实现了，但现在只能用用户态来做。

不能一直在用户态下执行，因此引出了内核栈的切换。内核栈来切的话，根据刚才的思维过程，既然这个指令执行的切换，就是栈的切换，到了内核，那也有栈。

那么是不是内核栈的切换呢？那么来思考，从用户栈到内核栈，内核栈再到 TCB，接着 TCB 之间进行切换，TCB 切换完以后，再完成内核栈的切换，内核栈切换完后，再完成用户栈的切换。

那么根据这个样子，两套栈的切换方式就有了。这个是自然而然想出来的，是人们想出来的，是思维一点点递进下去的，而不是有人直接告诉你答案的。

前面所说的全是 idea，要实现这些想法，那么接下来我们就在具体的计算机上做一下这种切换，看看怎么样。

刚才都是在纸上画出来，接下来需要实现 idea。那么我就要找一个系统，找一个机器，看看能不能实现这样的切换，如果能了，这棵小树就可以拿出来去培育，去让它长大。

每到这个时候，都会从一个简单、清晰、明确的目标开始。大家要做到一件事，一旦头脑中有个 idea，形成了 idea，就要把它在实际中形成一棵树来。接下来就让这棵小树不断地去长大。

那么，要实现这个 idea 怎么做呢？我们设定一个什么样的目标呢？在屏幕上交替地打出 A 和 B 。

怎么交替地打出 A 和 B 呢？我们的想法就是创建两个进程，这两个进程每个进程都执行死循环，一个循环地打出 A，另一个循环地打出 B，我们看它具体怎么做的。

我们首先在头脑中明确它整个做的过程，一旦在头脑中明确它做的过程以后，在头脑中明确整个的思路，你把它用别的代码去实现，比如说用别的语言或加一些想法去实现，这不就开始做出你的操作系统的那棵小树了吗？

进入到内核以后，INT 0x80 对应 system_call，执行 system_call 就要执行 sys_fork，执行 sys_fork 就要跳转到 copy_process。而我们前面说过，copy_process 就是在内核中做出这样一套东西，做出一套什么样的东西呢？在内核中做出新的一个 PCB 来。

然后紧接着父进程就要开始退回来，执行完 copy_process() 了，父进程就要往回返了。父进程返回的时候，就要进行调度，因为只有调度了，才能让屏幕上打印出 A 来，即让打印 A 的程序去执行。

现在是打印 A 的进程可以执行，但是还没有执行，要让它执行，要进行 schedule。所以，在适当的时候加上 schedule。这里在哪里做的呢？就是在中断返回的时候加上 schedule，它做了这样一件事。你也可以类似的做这样一套机制，中断返回的时候进行 schedule。

main 中执行完一个 fork 后，再继续执行。现在执行一个 fork 后，并不调用 schedule ，假定当前的时间片还没用完。一个父进程做出一个子进程来，做好了它的 PCB，做好了它的 TSS，做出进程的那个样子。做完子进程的样子后，假定时间片还没用完（时间片有一定的持续时间），同时也没有阻塞，所以父进程继续执行。

父进程继续执行的话，执行什么代码呢？还是刚才 main() 中的代码，继续创建一个打印 B 的进程。所以现在返回继续执行，又一次 fork，int 0x80，然后又在内核中做出一个子进程。当然，要想在屏幕上打印出 A 和 B 来，就要在内核中去做出这样的两个结构，去调用两次。

父进程在执行两个 fork 后，开始执行 wait，把自己的状态变成阻塞态，开始等待。

核心的结构就是由一个进程产生出两个子进程，创建的子进程里面分别是打印 A 和打印 B 的函数，然后父进程阻塞，调用 schedule，然后 schedule 就选择当前就绪队列中的进程进行执行。

读硬件手册，发现 TSS 可以支持完成这样的切换。

当你看到这个地方，如果这套东西都是你自己做的，当你现在看到屏幕上出现 A 了，你会感觉到非常高兴，这真是一种创造的快乐。但是，现在在屏幕上打印出 A 了，高兴一会儿马上发现，不对啊，现在屏幕上只能打印出 A 来，那怎么才能让它打印出 B 来呢？

比如说爱迪生发明电灯的时候，首先用一种材料作为灯丝，接着发现这种灯丝不行，然后再用另一种来做灯丝，… ，这部分思维还是属于直线思维。但后来爱迪生发现，根本不是灯丝的问题，而是空气的问题，是真空的问题。从灯丝的问题到真空的问题，这个可以说真是一种思维的完全飞跃，这种飞跃就来自右边的这张图。

有人也做过这样的实验，越是发明创造能力强的人，他的这种思维能力就越强。当遇到问题的时候，向四周不断地扩散来找答案。一个小孩的思维就是这样，他的思维非常发散，越到成年人越僵化，所以小孩的创造能力很强。但是有些教育，实际上小孩的这种创造能力被完全抹杀了。老师认为这种是非常不好的，那么应该保留孩子的这种能力，成年人都应该训练这种能力。

怎样才能调度到 B 呢？现在在用户态打印 A，那么怎样才能打印出 B 呢？必须要调度 B。而要想调度，必须要调用 schedule。shcedule 是在哪呢？是在内核中的一段代码，所以就必须要进入到内核。进入到内核靠的是什么呢？中断，靠的是中断。

时钟中断。

counter 减到 0 后，就开始调用 schedule。这也就是说，让 A 打印一会儿，接下来跳到 B 去打印，让 B 打印一会儿，再跳到 A 去打印。那么屏幕上就能交替地打印出 A 和 B 。

进程 A 和进程 B 的时间片在用完后，操作系统会进行调度，屏幕上会交替打印出 A 和 B。

把前面的所有内容全部串在一起，在头脑中就形成了，怎么从一点点，从idea 怎么诞生，到这个 idea 怎么通过程序一点点把它写出来。在头脑中形成这个东西，能把它写成一个程序，自己能写成一个程序。我们可以不看这个视频、不看这个 PPT、不看源码，自己在计算机上把进程调度的这个过程一点一点地写出来，写个代码出来，那么，你的操作系统的 0.01 版就出来了，你的操作系统最小的那棵小树，你的那个种子就发芽了。

有了那棵小树后，再慢慢、慢慢长大，总有一天你会做出你自己的操作系统。如果你不感兴趣，不想做这样的操作系统，但理解这个过程、这个过程背后所蕴含的思维的过程，对于大家做任何系统，做任何东西都是有用的。

从一个 idea 开始，把它想明白了、想具体了，把这个 idea 从一开始一个小点往里做，越做越大、越做越大，直到做成一棵树来。这棵树再越长越大、越长越大，直到形成一个真正的系统。就这样的一个过程，这就是老师这堂课背后所表达的深刻的思想。

L14 CPU调度策略

CPU 调度就是将 CPU 分配给哪个进程。这一节我们主要是讲一些策略性的东西，也就是说大概是怎么做的。我们集中在讲一个基本的操作系统，它上面的调度算法大概是个什么样子，需要折中考虑哪些问题。

CPU 调度本身是一个很复杂的话题，比如说，如果这个操作系统是安装在卫星上、导弹上等要求实时性很强的系统，那么，它里面的调度策略必须是实时调度。但我们这个课程不做这种设计，我们只讲一个基本的操作系统上，一个常见的、基本的调度策略，以及这些调度策略它考虑了哪些内容。

所以，这一节不是穷尽了 CPU 所有的调度方法，也不可能穷尽，我们只是拿出一个点来讲，至于其它点呢？我希望大家能通过这个点来触类旁通。

操作系统做 CPU 调度的时候，关键在于折中和综合。

响应时间小，后台任务周转的时间就要受到影响。

操作系统是 system，所谓 system，系统嘛，它就要为很多东西服务，所以就需要综合，折中。

调度时，如果对 I/O 约束型任务和 CPU 约束型任务设置优先级的话，哪一个的优先级应该更高一些呢？I/O 约束型任务的优先级应该更高一些。因为如果 I/O 约束型任务优先级高的话，它会被先调用执行，但它执行的时间很短，它稍微执行一下后就会调转。这时，如果调转去执行 CPU 约束型任务的话，那么这两个任务就并发执行起来了（如果 CPU 约束型任务的优先级较高的话，它先被调用执行，由于它要执行一段较长的时间，那么 I/O 约束型任务就容易处在饥饿的状态）。

实际上这里面蕴含着一些有趣的东西。大家想想，I/O 约束型的任务，实际上它就是那些前台任务，前台嘛，和用户交互的，I/O 嘛，输入输出，对应的那不就是用户嘛。而前台任务的优先级，就应该设置的高一些嘛，这是对用户的一种反应，反正后台在计算，用户也不太关心。

在系统中有各种类型的任务，每个任务的关注点不同，特点不同，目标也不同。目标不同可能会导致在调度这些任务的时候，会出现一些矛盾。所以折中、综合就让操作系统变得复杂，这是我们这个话题中，讲的主要一个主题。

然后我们在下一讲的时候（这一讲我们主要讲一些常见的策略），下一讲我们看一个实际的调度算法，看这个算法是怎么综合、折中这些目标的，做的还是挺漂亮的。

不光是折中、综合，而且它的调度算法还很简单，这个也是必须的。比方说，我设计出了一个非常漂亮的算法（很好地进行折中），但是这个调度算法要想执行起来，每次需要执行的时间，比如要半个小时，这个时候由于进程切换的过程耗费太长时间，导致系统的内耗很大，那么这个系统就没什么价值了。

接下来我们就看看，常见的有哪些调度算法。无论是怎么实时、还是面对什么场合怎么折中，你想要设计出满足特定要求的调度算法，那么肯定是这些基本的调度算法的一个糅合。所以，首先应该学习一下基本的调度算法。我们这里主要学习三种基本的调度算法。

首先是先来先服务的调度算法。

短作业优先，这实际上是我们讲的第一种调度算法。先来先服务的那种算法太简单了，就没什么，它不能算是一种，太简单了，太基本了。在短作业优先的调度算法中，将短作业往前提。

先来先服务算法保证了线程调度时的公平，这也是一个很好的想法。所以，先来先服务的这个思想和短作业优先的这个思想，将来要折中糅合的时候应该体会、体现这些思想。

好了，这是第一种调度算法，短作业优先，主要说的是短作业优先，接下来的话马上递进下去。

刚才讲的是周转时间，那么响应时间会怎么样的呢？比如这个 P2 要执行的话，虽然它在 0 时刻就来了，但必须要等着前面的任务全部完事才能执行，这个响应时间根本受不了，因为前面可能有好多任务。

所以，这种方法是不行的，响应时间没法保证。怎么做呢？这个实际上前面也说过，为了保证响应时间，使用了时间片来轮转调度。

好了，这就是第二种调度方法，第一种方法我们留在脑子里，短作业优先；第二个方法，轮转调度，保证响应时间。

第三种方法，应该设置优先级。当然，短作业实际上也是一种优先级，主要是用作业的长度作为优先级。

前台任务优先级定得高，后台任务优先级定得低。所谓优先级调度，就是只要优先就一定会先调度。

优先级是个很好的思路，但是固定地、死板地执行这种优先级调度，就会造成后台任务饥饿，得不到执行。因为系统中前台任务可能不断地出现。

前后台任务都得有时间片。为了保证响应时间，系统中所有的任务都得有时间片。但是，如果要是单纯的只有时间片的话，就又退化成轮转调度（RR），也就没有优先级的概念在里面。

所以既要以轮转调度为核心，因为它保证用户的响应时间（总有前台任务），又要在轮转调度的基础上增加一些优先级，而这优先级既要考虑到短作业应该先做，又要考虑到前台的任务应该先做。

那么大家可以看到，这就造成了这个折中会非常麻烦。下次课我们要讲的那个调度算法，它就比较好地解决了这个问题，而且写得代码还不多，并比较漂亮。

那么当然，还有很多其它任务，其它问题。

所以，也就是说，要做一个算法，这个算法还要简单，要考虑前台任务，要考虑各种任务的特点，要学习出来它是前台任务还是后台任务，还要能根据任务的变化也做出相应的变化。也就是说能够不断地调整，调整优先级，从而达到操作系统对所有任务的折中、综合，而且这个算法还要显得简单。

那么下一讲的时候，我们就来看看是怎么做出这个算法的。稍微整理一下的话，这一部分我们讲了调度的含义，从就绪队列中找一个进程来执行。那么就要写一个算法，这个算法要考虑到时间（周转时间，响应时间），要考虑到任务的特点、优先级等等。

那么要综合这些特点，因为一个系统中有各种各样的任务。那怎么综合这些特点呢？我们已经介绍了几个基本的算法（3 种基本的算法），那么需要在这 3 种基本算法的基础上，综合、糅合，写一个简单的程序来折中应对多个任务存在的情况。

而这个算法是短作业应该优先一些，这样的话任务的周转时间就比较好；然后应该是轮转调度为核心，因为总有前台任务要进行响应；还要考虑优先级，要适当地、巧妙地设计用户的优先级来反映这些特点。

L15 一个实际的schedule函数

我们主要讲的是在一个普通机器上的调度，比如说 PC 机。在 PC 机上，既有前台任务，又有后台任务；既有 I/O 约束型的任务，又有 CPU 约束型的任务；既要考虑响应时间，又要考虑周转时间。

在这种情况下，一个实际的操作系统的调度算法应该怎么做？应该考虑哪些内容？哪些因素？怎么进行折中、权衡？这是我们上节课讲的内容。这节课我们要看一个实际的函数，看一个实际的 schedule 函数是怎么做的。通过这个函数，我们来体会一下一个实际的系统是如何实现这种折中？如何用一些简单的代码，来实现把多个调度算法糅合在一起，既考虑 I/O 约束型，又考虑 CPU 约束型任务、前台任务、后台任务等等。

我们看的这个代码，就是 Linux 0.11 上的调度函数 schedule() 。在 Linux 0.11 的源码中就有，大家可以去找来看一看。它的这个代码核心的目标就是要找到 next，最后 switch_to(next) 。

把 p 设成了最后一个地址值（在 Linux 0.11 中，将所有进程的 PCB 用一个数组来管理），所以 p 指向数组的末尾。从数组的末尾从后往前移， --i ，检查 PCB 的状态是否是就绪的（所有进程的 PCB 都放在这个数组里，比如阻塞的，也放在这个数组里）。

在找到最大 counter 的进程后，（如果 counter 等于 0 ）对 PCB 数组中所有的 counter 值进行修改（如果 counter 不为 0，跳出循环去执行 switch_to(next) ）。

所以，这段算法的核心是优先级的方法，找到 counter 比较大的。实际上，这里 counter 表示的是时间片。所以，这个算法用一个 counter 既用来做优先级的调度（并且 counter 本身作为一个时间片），又用来进行轮转调度。

因此，这个算法的核心是两个，一个是基于 counter 的优先级，一个是基于 counter 的时间片轮转。而且这两个方面用的是同一个变量，这样操作起来、维护起来都非常简单。

在 for 语句对 counter 值进行操作时，做些什么事呢？把 counter 的值设为当前 counter 除以2 加上 counter 的初值。对于阻塞态的进程，在执行完这些语句后 counter 值（counter >= 0）会变大。所以，那些因 I/O 阻塞的进程，在变为就绪态时，它的 counter 值会变大。而 counter 作为优先级的衡量，因此，这些阻塞的进程变为就绪态后，优先级会上来（阻塞得越久，counter 值变得越大）。

既然 counter 是时间片，那么 counter 还在一个地方要修改，那就是在时钟中断。在时钟中断中，每次 counter 都减一，当等于 0 时就开始调度。

counter 还承担了优先级的作用。

对于 I/O 约束型的，你 I/O 执行得越长（经过 I/O 进程会阻塞），就认为你现在具有前台进程的特征，这是一种学习、一种学习机制。这时，你的优先级会比只执行计算任务的进程优先级高，即比那些后台进程的优先级高。而且执行 I/O 的时间越长，在阻塞队列待的时间就越长，优先级提升地也越高。

所以大家可以看到，就用一个 counter，整个这个算法就这么几句话就完事儿。用这个 counter，既承担时间片的作用，又承担优先级的作用。而且代码也非常精简，同时也很好地综合了时间片轮转、前台进程优先、优先级动态调整等这些思想。

在进程阻塞时，调整进程的优先级 counter 值的计算中，除以 2（右移一位）不是随意除的，是有讲究的（除以 3 或 4 等其它数字也行，级数都会收敛。但是，如果把式子中的 + 改为 - 的话，那么就不行了，级数不会收敛了。并且除以 2 的话，代码实现的方式是采用右移一位来计算，计算机对右移运算的速度是非常快的）。

我们前面说过 3 种算法，这里基于时间片轮转的调度保证了响应时间，基于优先级优先照顾了前台进程。那么，对于周转时间，SJF（短作业优先）有没有体现了呢？也有体现，后台的进程一直按照 counter 轮转，后台进程是 CPU 约束型的，后台进程单独按照时间片轮转的话，近似 SJF 调度（后台进程不断地轮转执行，短作业的进程肯定比长作业的先完事儿）。

如果大家将来有要求、有需要去写，在操作系统中写一个进程调度函数，那么你一定要折中考虑多个任务的特点，既要把程序写得简单，又要设计精巧的变量去调整调度。

（一个疑问？counter = 0 后怎么办？如何变为大于 0 的值呢？）

L16 进程同步与信号量

多进程图像除了要切换调度，让多进程图像向前推进以外，多个进程放在内存中，就会存在多进程合作的情况。这种合作应该是合理有序的，所以这部分讲的内容是进程同步，就是让多进程之间的合作变得合理、有序。

那么，怎么来实现同步，怎么来实现这个合理有序呢？就要靠信号量。所以这节课我们要讲清楚，为什么会有信号量？如何依靠信号量来实现多个进程合理有序地推进，也就是同步。

司机这个进程在启动车辆前，需要等售票员的一个信号（比如 “我已经卖完票了，可以走了” ）。也就是说，“启动车辆” 的这个指令不是随便执行的，必须要等待一个东西，我们通常把这个东西叫做信号。售票员这边把门关上以后，就会发一个这样的信号。

这堂课的核心是信号和同步，还有合作、等待这些词。这堂课的核心任务是从信号变成信号量，这是一个伟大的创举。从信号到进程同步，提出信号，这是比较自然的。但是，从信号到信号量，这是一个比较大的进步。

生产者-消费者实例。

进程合理有序地推进，主要表现为一个进程不是随意能往前执行，执行到一定程度它一定会阻塞，等着其它进程的一件事后，才能继续往下执行，这样才能合作好。所以核心就在这里，要进行等待、要进行阻塞，所以等待是进程同步的核心。

多个进程往前推进的时候，其中有些进程为了合作，为了共同完成一个任务，为了能够很好地、正确地完成一个任务，那么必须在执行到一定程度的时候，要阻塞、要等待一个信号。当别的进程执行到一定程度的时候，产生这个条件，会给等待的进程发一个信号过去，这就是进程同步的基本结构。这个基本结构非常重要，理解了这个东西，剩下的内容都好理解。

什么是进程同步呢？也就是通过让进程走走停停（停是关键）。

只发信号还不能解决全部问题，所以要引出信号量。那么，一旦把信号量引出来了，这次课程也就完事了。信号表达的信息还是太少了，信号嘛，只表示有还是没有。那么，我们要用信号量，来表达更丰富的信息。

消费者 C 再执行 1 次循环，P2 不能被唤醒（因为这时 counter == BUFFER_SIZE - 2，唤醒进程的条件不成立）。按照 counter 来判断的话，只发一次信号，只能唤醒 P1。很显然，在这个例子中应该发两次信号。

所以也就是说，应该用另外一个量来决定，到底要不要发信号，而不是根据 counter，来决定要不要发信号。因为我们要产生另外一个量，根据那个量来决定是不是发信号，而不是根据 counter。所以那个量就叫信号量，要根据信号量来决定要不要发信号。

信号量能记录一些信息。

通过信号量，可以知道有多少个进程睡眠。那我不就可以根据信号量，来决定怎么进行唤醒吗？所以，根据信号量来进行唤醒，而不是根据表示信号的 counter。从信号到信号量，表达了更丰富的含义，来面对更复杂的环境。信号只能表示 0、1，要不就走，要不就停，所以它只能起到类似红绿灯的作用。

接下来的内容是信号量的一种实现，刚才讲原理已经讲得非常清楚了。

大家学完这个部分，可以去做一下我们这个课程对应的实验 5 ，实验 5 就是要实现信号量。在 Linux 0.11 这个系统里面，它没有提供信号量。要实现时，P() 和 V() 要做成系统调用，然后上层应用程序可以调用这两个系统调用，来使用信号量。为什么叫 P、V 呢？因为是荷兰学者 Dijkstra 给出来的。

刚才我们讲了信号量的结构、讲了信号量对应的 P、V 操作。那么接下来我们就可以利用信号量，去解决生产者-消费者问题。一旦解决了它，这部分不就完事了吗？也就是说，我们的确用信号量来解决了进程之间的同步问题。这一讲的内容，不就是用信号量去解决同步问题吗？解决进程间的合作吗？我们一起来看一下。

信号量的核心，关键在于对 0 的处理。到 0 了，再往下减就要停了。

只有一个进程进去修改共享缓冲区，那么就不会引起缓冲区的错误。什么时候会发生等待呢？当有一个进程在共享缓冲区里操作的时候，其它进程就会发生等待。所以，定义一个信号量 mutex = 1 ，只要有一个进程进去，其它想要进入的进程就发生阻塞。而一旦这个进入的进程离开了，它就用 V(mutex) 释放进入共享缓冲区的权限。

这就是我们用信号量，来解决了进程间的同步问题。通过信号量、通过数值、通过根据数值的语义，来判断是不是要睡眠，是不是要唤醒其它进程，来实现了生产者-消费者的进程在往前推进时，合理有序。实现了同步、实现了合作。

L17 信号量临界区保护

上一讲，我们讲了用信号量来实现进程的同步。但是，单独的信号量，没有这一节要讲的临界区的保护，它还是不能正常工作的。也就是说，它的完整故事应该是：靠临界区来保护信号量，靠信号量来实现进程之间的同步。

这个地方我们要讲两个主题，第一个，为什么要保护信号量？以及为什么会引出临界区的概念？第二个，在实际中，我们是采用什么方法来保护信号量、来实现临界区的？

首先，我们讲的第一个话题是为什么要保护信号量？

信号量的值，比如上一节讲到的 empty 的值，一定要是对的。一旦出错，就不能实现多进程的有序推进了。当生产者 P1 还没把信号量、共享的这个 empty 变量修改完成，P2 就切进来修改，那么就会造成 empty 的语义错误，含义不对。

信号量的值和信号量所表达的含义不对，将来就会引发问题，这就是信号量为什么需要保护的原因。当然，不只是信号量，只要是这种共享数据，在内核中如果不做保护，都会引发这种错误，因为你不知道操作系统具体会怎么调度。

竞争条件：和调度有关的共享数据语义错误。它不是一种编程造成的错误，而是由于共享数据没有保护造成的一种竞争错误。

要想保证在内核中，修改共享的全局变量不出差错，那么就必须要用临界区保护。

读写信号量的代码一定是临界区，修改信号量的那段代码是进程中的临界区代码，这段代码必须要加以保护。进入临界区的时候，要写一段进入区的代码，而退出临界区的时候，也要写一段退出区的代码。

临界区代码的保护原则：

互斥进入是基本原则，必须要达到；
有空让进和有限等待是两个好的临界区保护原则。

那么，准备工作都做好了，接下来我们就来看怎么做到这件事情。

第一种方法，实际上在现实生活中也非常常见，它就是轮换法，也叫值日法。

不满足有空让进的原则。

借鉴在日常生活中，看到冰箱里没有牛奶而去买牛奶的例子。

实现信号量的第二种方法，标记法。

此时P0和P1的进入请求会无限等待

非对称标记

进入临界区的 Peterson 算法

Peterson 算法的正确性

面包店算法（个人注释：PPT 中代码格式较乱，可跳过，暂时知道这个算法是干嘛的就行了）

面包店算法的正确性

看了这些代码分析后，可能大家都 “只缘身在此山中”，迷失方向了。大家思路一定要清晰，讲了这么大变天，这个地方（进程 Pi 线框中的代码）到底要干啥呢？要保护信号量。就是信号量会修改的这些地方，就用面包店算法，把这些修改信号量的地方给包住。

能不能做出一些更简单的算法来实现？实现的第一种方法叫软件方法，比如面包店算法。我们总共讲 3 个方法，第 2 个方法和第 3 个方法都比较简单，采用硬件来做。

大家可以看到，为什么叫软件方法？因为不用任何硬件支持。所以在操作系统中，有些东西纯用软件来做，比较复杂，因此操作系统应该要求硬件给它提供一些东西。所以实际上大家也就明白了，为什么会强调一个主题——软硬件协同设计？做软件，当然，做上层应用软件的时候，你从来不会体会到这个层次，什么软硬件协同设计。但是，在做一些底层系统的时候，比如说路由器，在确定了要实现的路由算法后，如果有相应的硬件支持的话，那么可以实现得更好。

因为要想调度，必须要中断。所以，如果阻止中断，那么就不会产生调度了。

中断是怎么工作的？实际上在 CPU 上有一个寄存器叫 INTR（中断寄存器），每条指令执行完了（在汇编中叫指令，在 C 语言中叫语句），都要看 INTR 寄存器上是不是有 1。如果有的话，就要中断，就要进入中断处理程序。一旦 cli() ，那么 CPU 就不看 INTR 寄存器了，就不会再产生中断了。

多 CPU 不好使（你只能控制单 CPU 上每个核都不产生调度，但是不能控制其它 CPU 当前执行的进程进入临界区，去修改信号量）。而我们知道，现在的计算机多 CPU 、多核都非常常见。所以，这种开关中断只在于小系统，就是我们做实验的那个 Linux 0.11 上好使。因为当时那些计算机都是单 CPU 的，所以这种方法看起来比软件方法简单得多，但是它使用的范围是有限的，多 CPU 不好使。

实验五就是在 Linux 0.11 上实现信号量。那么在做实验五的时候，可以用这种方法，而且鼓励大家用这种方法。我们那个模拟器，模拟出来的计算机就是单 CPU。

还有一种方法就是硬件原子指令法。

实际上锁这个概念，就是一个整数，它的概念和信号量是完全一样的，它就是个信号量（实际上等于 1 的信号量，就是锁的信号量）。但是，如果用信号量去实现这个锁，那就不对了。怎么不对呢？因为要用信号量去实现这个锁，那么修改 mutex（信号量的值）是不是也得保护啊，你这个地方是修改 empty（信号量的值）需要保护，那修改 mutex 也需要保护，这样的话不就麻烦了吗？（会造成没完没了的现象，修改一个信号量，需要另一个信号量去保护它，无限循环。）

做一种硬件原子指令，使得修改 mutex 的执行是原子的。实际上，硬件原子指令就是通过这种原子指令，实现一个类似 1 的这种锁信号量。也就是说，要用硬件原子指令修改一个整型变量，然后根据这个变量大家再来判断，要不要进入临界区。但是，在修改这个变量的时候，必须要一步完成。

接下来大家就可以分析一下，是否满足互斥进入、有限等待以及 CPU 是什么情况等等，看看这个硬件原子指令适合于什么情况，是不是适合于多 CPU 的情况等等。这个内容我们留作练习吧，大家回去查查资料，好好去想想，琢磨一下，学习也需要自己好好琢磨一下。

那么，我们再总结一下这部分讲的内容。我们把上一讲和这节课的内容组合在一起，实际上大家可以看到，总结的结论是什么呢？需要用临界区来保护信号量。临界区保护的方法可以用面包店的方法，可以用开关中断，可以用硬件原子指令。

一旦用临界区保护住了这个信号量，信号量在执行的过程中，表示的语义就一定会正确。而信号量的语义正确以后，根据这个语义，就可以实现在多个进程中，哪些进程什么时候该被阻塞，什么时候该被唤醒。这就实现了对进程在适当的时候阻塞，在适当的时候推进，也就实现了多个进程合理推进。

所以，结论就是用临界区去保护信号量，用信号量实现同步。这就是关于进程同步、进程合作的完整故事。

L18 信号量的代码实现

在上两讲，我们讲了什么是信号量，怎么用信号量来实现进程之间的同步，以及信号量需要保护，用临界区来保护信号量。这一讲，我们来看一看信号量是如何用代码来实现的。

大家会发现，信号量的代码实现比较简单。所以，信号量是一个原理比较复杂，但代码比较简单的这么一个东西。但这个东西非常重要，信号量非常重要，可以实现多个进程（执行序列）之间的同步，互相等待，交替执行，合理有序地推进。这种推进不仅仅在上层应用中需要，也就是生产者-消费者那层需要；实际上，在操作系统内部也有大量的这种同步。

学完这个部分，大家有两个收获（完成任务）：

第一个，可以写用户态的代码。也就是说，大家可以用信号量的系统调用，来实现上层应用间的同步。比如说，一个操作系统如果没有这样的系统调用，那就可以扩充，比如我们配套实验中的实验五，就是这样安排的。而且，通过这一节的代码实现，大家对信号量的认识就更加深刻。
第二个，学习这个代码也会明白，在操作系统内部，也要增加大量的这样代码，来实现多个像这种执行序列间的同步。只有这种同步做好了，操作系统才能合理有序地向前执行。所以做操作系统，实际上就是要解决大量的同步问题。那个时候用的也是信号量，后面会看到。

接下来我们就开始，从纸上到实际，我们来看看它是怎么做的。

还是那个典型的生产者-消费者，P (empty)、V (full)。左边是纸上写的伪代码（轮廓），右边是我们写的、对应的实际程序。这个程序实际上就是实验五的核心程序。

首先，我们要申请信号量，因为信号量是在操作系统内部的。我们说过，信号量里面包括一个值 value ，还包括一个队列（ PCB 的队列）。信号量的这个数据结构在内核里。

什么叫信号量？不就是这样工作的嘛：多个进程共同看到一个整数，根据这个整数决定要怎么工作，是否要阻塞？是否要唤醒别的进程？

也就是说，整个写的程序非常简单，write(fd,&i,4); 。那么，我们接下来说第二个意图，我们来看在操作系统（Linux 0.11）内部有没有这样的同步。当然有，一个任务（进程）在用户态执行的时候发出 read 系统调用，就要进入到内核，在内核中最后执行的是 system_read，system_read 最后执行的是 bread，bread 就是到磁盘上去读一个磁盘块。

所谓睡眠、所谓阻塞，就是把自己放入阻塞队列上，然后把自己的状态变成阻塞态，然后再 schedule。

Linux 0.11 中 sleep_on 形成的队列

磁盘中断会唤醒之前阻塞的进程。执行磁盘中断 read_intr 的时候，会执行 end_request，end_request 会执行 unlock_buffer。

大家可以看到，这是一种什么机制呢？由中断的 wake_up 唤醒等待队列上的队首进程，然后由队首进程执行的时候，挨个去唤醒。因为调度是任意发生的，那么就会产生出这种调度情况：一个中断把队首唤醒了，队首执行一下，把前一个唤醒，前一个执行，马上又把它的前一个唤醒 …，所以，这种机制实际上是将阻塞队列中的进程全部唤醒的机制。而 PPT 第 2 页中的 if 是将阻塞队列中，第一个唤醒的机制。所以，这就引出了在 PPT 第 3 页中，为什么用 while。

为什么要把所有的阻塞队列全唤醒？应该让优先级最高的进程来执行，不能因为它晚来了，排在阻塞队列的后面就不让它先执行。因此要把阻塞队列中的进程全部唤醒，然后由 schedule 来决定。

优先级最高的进程被唤醒后，由于在 while 循环里，所以它还要再判断一下 while 循环的条件。在跳出循环后，把 bh->b_lock 置为 1（代码片段在第 3 页 PPT 中），而其它被唤醒的进程，再对 while 循环的条件语句进行判断时，由于 bh->b_lock 已被锁上，不能跳出循环，所以继续执行 while 里面的语句，继续睡眠。

因此这就造成这样的效果：队列中所有阻塞的进程全部被唤醒，高优先级的进程被调度执行，它执行后把 bh->b_lock 置为 1，而其它的进程被唤醒后，仍需继续判断 while 循环的条件。

所以，这也就是为什么不用 if 来判断。如果是 if 的话，所有被唤醒的进程不会再去执行判断语句，直接会往后执行语句。那么，所有的进程被唤醒后就全进入，这是不对的。

当然，大家在实现实验五的时候，完全可以用这种机制来做。那这种机制和前面讲的信号量有什么区别呢？它不会有负数。为什么不会有负数啊？因为它不需要记录在等待队列中有多少进程在等待。为什么呢？因为它每次将阻塞队列中的进程都唤醒。当然，没进程的就拉倒（ if(p && *p) 中条件判断为 false ），不唤醒。

无论阻塞队列中有多少进程，也不需要记录，把它们全唤醒，让它们再去竞争就完事。所以，这个时候信号量不需要有负值。当然，采用这种方法写的程序，比使用 if 的那种方法不怎么直观一些。但是它带来的优点是，在阻塞队列中，优先级高的进程会优先执行，由 schedule 来决定。

这次讲的这个知识啊，我推荐大家首先用直观的想法，if 那种信号量的版本，即有负数的信号量版本，来实现下实验五。实验五非常难，在每年我们给自己本科生上课的时候，实验五都难倒一大批人，往往都需要很久来调。之后也可以改成 while 这种版本来实现一下。总之一句话，大家回去要是不做一遍实验五，你对信号量的理解永远都停留在纸上。