一. 操作系统概述

计算机层次结构：裸机(指纯硬件，包含CPU、内存、硬盘和主板等)、操作系统、应用程序和用户。结构依次往上。

操作系统(Operating System，OS) 是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配；以提供给用户和其他软件方便的接口和环境；它是计算机系统中最基本的系统软件。

从上面定义可以得到操作系统以下特点：

1. 操作系统是系统资源的管理者。这里的系统资源包含硬件和软件资源。
2. 向上层提供方便易用的服务。上层即用户和应用程序。
3. 是最接近硬件的一层软件。

1. 操作系统提供的服务

这一门课主要学习的是操作系统是系统资源的管理者，即操作系统会提供：处理机(CPU)管理、存储器管理、文件管理和设备管理。

向上层提供方便易用的服务主要是用户和应用程序不需要直接对硬件进行繁琐复杂的操作，而是通过操作系统简化这些操作。这其实体现了封装思想，即操作系统把一些丑陋的硬件功能封装成简单易用的服务，使用户能更方便地使用计算机，用户无需关心底层硬件的原理，只需要对操作，系统发出命令即可。操作系统提供的易用服务有：

• GUI：图形化用户接口(Graphical User Interface)

  用户可以使用形象的图形界面进行操作，而不再需要记忆复杂的命令、参数。

  例子：在Windows操作系统中，删除-一个 文件只需要把文件“拖拽”到回收站即可。

• 命令接口

  1. 联机命令接口实例(cmd)。联机命令接口$=$$=$交互式命令接口

     联机命令接口就是一个指令对应一个执行。

  2. 脱机命令接口(bat文件)。脱机命令接口$=$$=$批处理命令接口

     批处理是提前预输入多个指令，让系统一次性全部执行。

• 程序接口

  可以在程序中进行系统调用来使用程序接口。普通用户不能直接使用程序接口，只能通过程序代码间接使用。

  如：写C语言"Hello world"程序时，在printf函数的底层就使用到了操作系统提供的显式相关的系统调用。

  系统调用类似于函数调用，是应用程序请求操作系统服务的唯一方式。有的教材中系统调用又称为广义指令。

这里的命令接口和程序接口也可以统称为用户接口。

所以上图用户和应用程序与操作系统之间的有接口，用户通过命令接口可以直接和操作系统进行交互。应用程序可以通过程序接口与操作系统进行交互。

最后操作系统作为最接近硬件的层次需要实现对硬件机器的拓展。如果一个计算机中没有任何软件支持的计算机成为裸机。在裸机上安装的操作系统，可以提供资源管理功能和方便用户的服务功能，将裸机改造成功能更强、使用更方便的机器。通常把覆盖了软件的机器称为扩充机器，又称之为虚拟机。

操作系统对硬件机器的拓展是将CPU、 内存、磁盘、显示器、键盘等硬件合理地组织起来，让各种硬件能够相互协调配合，实现更多更复杂的功能。

2. 操作系统特征

操作系统有并发、共享、虚拟和异步四个特征。其中共享和并发是两个最基本的特征，二者互为存在条件。

• 并发

  这里的并发：指两个或多个事件在同一时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。如指令流水线。

  而并行：指两个或多个事件在同一时刻同时发生。如双接口访存。

  操作系统的并发性指计算机系统中"同时"运行着多个程序，这些程序宏观上看是同时运行着的，而微观上看是交替运行的。

  操作系统出现就是为了支持"多道程序技术"。因此操作系统和并发是一起诞生的。

  注意(重要考点)：单核CPU同一时刻只能执行一个程序，各个程序只能并发地执行。多核CPU同一时刻可以同时执行多个程序，多个程序可以并行地执行。比如Intel的第八代i3处理器就是$4$$4$核CPU，意味着可以并行地执行$4$$4$个程序。即使是对于$4$$4$核CPU来说，只要有$4$$4$个以上的程序需要"同时"运行，那么并发性依然是必不可少的，因此并发性是操作系统一个最基本的特性。

• 共享

  共享即资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用。

  两种资源共享方式：互斥共享和同时共享。

  1. 互斥共享方式

     系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。

     如使用QQ和微信视频。同一时间段内摄像头只能分配给其中一个进程。

  2. 同时共享方式

     系统中的某些资源，允许一个时间段内由多个进积"同时"对它们进行访问。

     同时共享方式：使用QQ发送文件$A$$A$，同时使用微信发送文件$B$$B$。宏观上看，两边都在同时读取并发送文件说明两个进程都在访问硬盘资源，从中读取数据。微观上看，两个进程是交替着访问硬盘的。

  所谓的"同时"往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问的(即分时共享)。

并发和共享之间的关系：并发性指计算机系统中同时存在着多个运行着的程序。共享性是指系统中的资源可供内存中多个并发执行的进程共同使用。

还是通过上面发送文件例子来解释并发与共享的关系。使用QQ发送文件$A$$A$，同时使用微信发送文件$B$$B$。

1. 两个进程正在并发执行(并发性)

   如果失去并发性，则系统中只有一个程序正在运行，则共享性失去存在的意义。

2. 需要共享地访问硬盘资源(共享性)

   如果失去共享性，则QQ和微信不能同时访问硬盘资源，就无法实现同时发送文件，也就无法并发。

所以并发性和共享性是互为存在的关系。

• 虚拟

  虚拟是指把一个物理上的实体变为若千个逻辑上的对应物。物理实体(前者)是实际存在的，而逻辑上对应物(后者)是用户感受到的。

  如：GTA5需要$4$$4$GB的运行内存，QQ需要$256$$256$MB的内存，迅雷需要$256$$256$MB的内存，网易云音乐需要$256$$256$MB的内存等。假如电脑只有$4$$4$GB运行内存，这些程序同时运行的内存要远大于$4$$4$GB，但仍然可以在电脑上运行，这就是虚拟存储技术，实际只有$4$$4$GB的内存，在用户看来似乎远远大于$4$$4$GB。这就是虚拟技术中的"空分复用技术"。

  另外如果用户打开多个软件，但实际上只有一个单核的CPU，但这多个程序仍然可以运行。这是虚拟处理器技术。实际上只有一个单核CPU，在用户看来似乎有$6$$6$个CPU在同时为自己服务。这就是虚拟技术中的"时分复用技术"。微观上处理机在各个微小的时间段内交替着为各个进程服务。

  所以虚拟技术分为时分复用技术和空分复用技术。

显然，如果失去了并发性，则一个时间段内系统中只需运行一道程序，那么就失去了实现虚拟性的意义了。因此，没有并发性，就谈不上虚拟性。

• 异步

  异步是指，在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底的，而是走走停停，以不可预知的速度向前推进，这就是进程的异步性。

  由于并发运行的程序会争抢着使用系统资源，而系统中的资源有限，因此进程的执行不是一贯到底的，而是走走停停的，以不可预知的速度向前推进。

如果失去了并发性，即系统只能串行地运行各个程序，那么每个程序的执行会一贯到底。只有系统拥有并发性，才有可能导致异步性。

总结：并发和共享互为存在条件。没有并发和共享，就谈不上虚拟和异步，因此并发和共享是操作系统的两个最基本的特征。

3. 操作系统的发展与分类

主要讲述操作系统在各个阶段的主要解决的问题及各自的优缺点。

• 手工操作阶段

  程序员将代码写在纸带上，有孔的地方是$1$$1$，没有孔的地方表示$0$$0$。之后将写好后的纸带放到纸带机上，之后计算机从纸带机中读取要用到的程序，程序运行完毕后，将运行结果输出到纸带机上，最后程序员从纸带机上取走运行后的程序。

  

  这种运行方式主要慢在程序员将纸带放入纸带机及从纸带机中取走云心结果这几步。

  

  上面$J1,J2$$J1,J2$是两个程序，可以看出手工操作阶段主要缺点是：用户独占全机、人机速度矛盾导致资源利用率极低。计算机工作事件只有上面红色的一小段。

• 单道批处理系统

  为了解决上面手工阶段缺点，发明了单道批处理系统，在这个阶段引入脱机输入$/$$/$输出技术(用外围机$+$$+$磁带完成)，并由监督程序负责控制作业的输入、输出。

  各个程序员可以把自己的程序放入纸带机，之后会由外围机将多个纸带程序数据先放到磁带机上，之后计算机可以直接从这个磁带中读取数据。磁带读写速度比纸带机快很多。

  

  此时的计算机中会运行监督程序，由这个程序控制自动从磁带中输入输出数据。

  

  采用这种系统，计算机利用率提高很多

  

  主要优点：缓解了一定程度的人机速度矛盾，资源利用率有所提升。

  主要缺点：内存中仅能有一道程序运行，只有该程序运行结束之，后才能调入下一道程序。CPU有大量的时间是在空闲等待$I/O$$I/O$完成。资源利用率依然很低。

• 多道批处理系统

  为了解决上述问题，多道批处理系统诞生，在这个阶段操作系统正式出现。操作系统支持多道程序并发运行。

  在多道批处理系统中，每次可以往内存中读入多道程序，然后让这些程序并发运行。

  这个阶段计算机利用率大大提高

  

  主要优点：多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU和其他资源更能保持"忙碌"状态，系统吞吐量增大。

  主要缺点：用户响应时间长，没有人机交互功能(用户提交自己的作业之后就只能等待计算机处理完成，中间不能控制自己的作业执行。如：无法调试程序$/$$/$无法在程序运行过程中输入一些参数)

• 分时操作系统

  分时操作系统：计算机以时间片为单位轮流为各个用户$/$$/$作业服务，各个用户可通过终端与计算机进行交互。

  主要优点：用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台计算机，并且用户对计算机的操作相互独立，感受不到别人的存在。

  主要缺点：不能优先处理一些紧急任务。操作系统对各个用户$/$$/$作业都是完全公平的，循环地为每个用户$/$$/$作业服务一个时间片，不区分任务的紧急性。

• 实时操作系统

  为了能让用户处理一些紧急任务。有了实时操作系统。

  在实时操作系统的控制下，计算机系统接收到外部信号后及时进行处理，并且要在严格的时限内处理完事件。实时操作系统的主要特点是及时性和可靠性。而实时操作系统又可以细分为：

  1. 硬实时系统 必须在绝对严格的规定时间内完成处理。如导弹控制系统和自动驾驶系统。
  2. 软实时系统 能接受偶尔违反时间规定

  主要优点：能够优先响应--些紧急任务，某些紧急任务不需时间片排队。如火车订票系统。

• 其他操作系统

  1. 网络操作系统：是伴随着计算机网络的发展而诞生的，能把网络中各个计算机有机地结合起来，实现数据传送等功能，实现网络中各种资源的共享( 如文件共享)和各台计算机之间的通信。( 如: Windows NT就是一种典型的网络操作系统，网站服务器就可以使用)。
  2. 分布式操作系统：主要特点是分布性和并行性。系统中的各台计算机地位相同，任何工作都可以分布在这些计算机上，由它们并行、协同完成这个任务。
  3. 个人计算机操作系统：如Windows XP、MacOS，方便个人使用。

4. 操作系统的运行机制

由程序员编写的程序是应用程序。而操作系统内核是由一个一个内核程序组成的，所以操作系统内核简称内核。内核是操作系统最核心的部分，也是最接近硬件的部分。甚至可以说，一个操作系统只需要内核就足够了，如Docker技术就仅需要Linux内核。而操作系统的功能也未必都在内核中，如GUI。

操作系统内核作为"管理者"，有时会让CPU执行一些特权指令，如：内存清零指令。这些指令影响重大，只允许"管理者"，即操作系统内核来使用。

普通的应用程序只能使用"非特权指令"，如：加法指令、减法指令等。

在CPU设计和生产的时候就划分了特权指令和非特权指令，因此CPU执行一条指令前就能判断出其类型。但CPU无法区分特权指令是应用程序的指令还是内核程序的指令。为了能让CPU区分CPU会分为两种状态：内核态(管态或核心态)和用户态(目态)。

• 处于内核态时，说明此时正在运行的是内核程序，此时可以执行特权指令
• 处于用户态时，说明此时正在运行的是应用程序，此时只能执行非特权指令

CPU中有一个寄存器叫程序状态字寄存器(PSW)，其中有个二进制位，$1$$1$表示内核态，$0$$0$表示用户态。

内核态与用户态的切换：

1. 刚开始时，CPU为内核态，操作系统内核程序先在CPU上运行。
2. 开机完成后，如果操作系统上运行应用程序，此时内核程序会执行一条特权指令，这个特权指令会把PSW标志位从内核态转换为用户态。这样就完成了CPU状态切换
3. 接着操作系统内核会让出CPU使用权，让应用程序在CPU上运行。
4. 假如当前应用程序中有一条特权指令，CPU可以识别出这个特权指令，但此时CPU处于用户态。所以会引发一个中断信号。
5. 处于用户态的CPU会接受中断信号，之后会立即变为核心态，并停止运行当前应用程序，转而运行处理中断信号的内核程序。
6. 这个中断使操作系统再次夺回CPU控制权。
7. 之后操作系统会对引发中断的事件进行处理，处理完了再把CPU使用权交给别的应用程序。

所以内核态转换为用户态：执行一条特权指令，即修改PSW的标志位为"用户态"，这个动作意味着操作系统将主动让出CPU使用权

而用户态转换为内核态：由"中断"引发，硬件自动完成变态过程，触发中断信号意味着操作系统将强行夺回CPU的使用权

除了非法使用特权指令之外，还有很多事件会触发中断信号。一个共性是，但凡需要操作系统介入的地方，都会触发中断信号

5. 中断和异常

CPU上会运行两种程序，一种是操作系统内核程序，一种是应用程序。内核是整个系统管理者，在合适的情况下，操作系统内核会把CPU的使用权主动让给应用程序，这个应用程序运行过程中会发生中断，中断是让操作系统内核夺回CPU使用权的唯一途径。结合上一节内容这里不难理解中断重要性。

中断作用：让操作系统内核强行夺回CPU的控制权。使CPU从用户态变为内核态。

中断分为两种类型：内中断和外中断。

5.1 内中断

内中断产生和当前执行的指令有关，中断的信号来源于CPU内部。

如上面提到的例子，一个应用程序应用在用户态，假如这个应用程序有一个特权指令，CPU执行这条特权指令时发现此时正在处于用户态。于是这个非法的事件会触发一个中断信号，CPU会拒绝执行这条指令。接着CPU会自动切换到内核态开始处理中断信号相关的内核程序。

有时候即使用户执行的是非特权指令也会发生中断。如执行除法指令时发现除数为$0$$0$。

另一个例子，一个应用程序运行在用户态，有时候应用程序想请求操作系统内核的服务，此时会执行一条特殊的指令，即陷入指令，该指令会引发一个内部中断信号。接着CPU会转向处理中断信号的内核程序。所以可以看出当一个应用程序执行陷入指令时，就意味着这个应用程序主动把CPU使用权还给操作系统内核，想让操作系统内核为其提供一些服务。之前提到的系统调用就是通过陷入指令完成的。

需要强调的是陷入指令是一个特殊指令，不是特权指令。

5.2 外中断

外中断产生和当前执行的指令无关，中断信号来源于CPU外部。

典型的例子是时钟中断，即由硬件时钟部件发送来的中断信号。这个部件会每隔一段时间给CPU发送一个时钟中断信号，通过时钟中断信号就可以实现多道程序并发运行了。

假设此时系统当中想要并发运行两个应用程序。而时钟部件每个$50$$50$ms给CPU发送一个时钟中断信号。

• 首先应用程序$1$$1$运行在用户态。当CPU执行两条应用程序$1$$1$指令后，时钟部件发现已经过了$50$$50$ms，此时会给CPU发送一个中断信号。这个中断信号来自于CPU外部。
• 之后CPU会切换到内核态，转而处理中断内核程序。当执行这个内核程序时候，CPU会知道应用程序$1$$1$已经执行了$50$$50$ms
• 接着内核程序会把CPU使用权给应用程序$2$$2$。之后CPU切换为用户态执行应用程序$2$$2$。
• 之后再过$50$$50$ms时钟部件会再次给CPU发送中断信号。重复上述过程就完成两个程序并发运行。

除了由时钟部件发出的中断信号，有时候也会由$I/O$$I/O$设备发出中断信号。根据之前学习的计算机组成原理可以直到CPU在每个执行周期末尾都会检查有没有外部中断信号。

5.3 中断分类

有的教材会称内中断为异常或例外。外中断叫中断。

异常可以分为三类：陷阱(陷入)、故障、终止

1. 陷阱

   由陷入指令引发，是应用程序故意引发的，即当一个应用程序想要操作系统提供服务时候，就会故意引发这个异常。其实这也是系统调用的原理。

2. 故障

   是一种由错误条件引起的，可能被内核程序修复。内核程序修复故障后会把CPU使用权还给应用程序，让它继续执行下去。 如：整数除$0$$0$、缺页故障。

3. 终止

   由致命错误引起，内核程序无法修复该错误，因此一般不再将CPU使用权还给引发终止的应用程序，而是直接终止该应用程序。如：非法使用特权指令。

5.4 中断机制的基本原理

不同的中断信号，需要用不同的中断处理程序来处理。当CPU检测到中断信号后，会根据中断信号的类型去查询"中断向量表"，以此来找到相应的中断处理程序在内存中的存放位置。

显然这里的中断处理程序就是一种内核程序，需要运行在内核态。

总结：

6. 系统调用

操作系统作为用户和计算机硬件之间的接口，需要向上提供一些简单易用的服务。主要包括命令接口和程序接口。其中，程序接口由一组系统调用组成。

所以"系统调用"是操作系统提供给应用程序(程序员$/$$/$编程人员)使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以通过系统调用来请求获得操作系统内核的服务。

这个平时编程时使用的函数调用其实是很类似的。但还是有区别，系统调用是比高级语言提供的库函数更为底层的一个接口。

另外一些库函数不涉及系统调用，如取绝对值函数。设计系统调用有创建一个新文件函数等。

有一种情况，当打印时，如果两个进程可以随意地、并发地共享打印机资源这样会得到错误的打印内容。所以系统调用是必须的。即解决方法是由操作系统内核对共享资源进行统一的管理， 并向上提供"系统调用"，用户进程想要使用打印机这种共享资源，只能通过系统调用向操作系统内核发出请求。内核会对各个请求进行协调处理。

系统调用分类：

应用程序通过系统调用请求操作系统的服务。而系统中的各种共享资源都由操作系统内核统一掌管， 因此凡是与共享资源有关的操作(如存储分配、$I/O$$I/O$操作、文件管理等)，都必须通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作。

假设一个应用程序想要进行系统调用，这个调用过程如下：

• 首先这个应用程序的指令会被处于用户态的CPU一个一个执行。当这个应用程序需要用到系统调用时，需要用传参数指令，给CPU寄存器中传递必要的参数。如在某一个寄存器中存放参数$1$$1$。这个参数$1$$1$指明了系统调用类型，如fork。传递参数过程有多条，主要要看系统调用需要传递几个参数。操作系统会根据应用程序提供的参数来判断想要的服务是哪种。

  

• 当这些参数都放入寄存器之后，应用程序就会执行一条特殊的指令，即陷入指令。这个陷入指令的执行会引发一个内中断。CPU检测到这个内部中断信号后发现是由trap(陷阱)指令引起的，于是CPU就会暂停运行这个应用程序转而去处理陷入指令的应用程序。这个程序就是系统调用入口程序。

  

• 显然这个系统调用入口程序属于内核程序，因此CPU会切换为内核态。这个中断程序会检查CPU寄存器中的参数，通过第一个参数会知道应用程序需要的是哪种类型的系统调用服务。接着入口程序就会调用与之对应的处理程序。让处理程序在CPU上运行。

  

• 当系统调用处理完成后，CPU会再转回到用户态。接着执行之前的应用程序。

  

总的来说系统调用过程是：传递系统调用参数$\to$$\rightarrow$执行陷入指令$/$$/$trap指令$/$$/$访管指令(用户态)$\to$$\rightarrow$执行相应的内请求核程序处理系统调用(核心态)$\to$$\rightarrow$返回应用程序

注意:

1. 陷入指令是在用户态执行的，执行陷入指令之后立即引发一个内中断，使CPU进入核心态
2. 发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行。

7. 操作系统体系结构

经过之前的学习计算机系统结构如下：

操作系统的内部可以进一步进行划分：一部分是内核功能(如时钟管理，中断处理)，另一部分是非内核功能(如GUI)。

这里的时钟管理就是利用时钟中断实现的计时功能。原语是一种特殊的程序，具有原子性。也就是说，这段程序的运行必须一气呵成，不可被"中断"。Ubuntu、CentOS 的开发团队，其主要工作是实现非内核功能，而内核都是用了Linux内核。

7.1 大内核与微内核

总之内核是操作系统最基本、最核心的部分。实现操作系统内核功能的那些程序就是内核程序。还有一种划分方式由于对进程管理、存储器管理、设备管理等功能属于对数据结构的操作，不会直接涉及硬件，所以这些不属于内核。按照这样思路划分如下：

上面这种划分方式会对系统性能造成一定的影响。

假设现在有个应用程序想要请求操作系统的服务，这个服务的处理同时涉及到进程管理、存储管理、设备管理。

• 采用大内核体系结构，应用程序向操作系统提出服务请求，这个时候CPU会从用户态切换为内核态开始运行这一些列的内核程序
• 而如果采用是微内核体系结构，应用程序向操作系统提出服务请求，如果使用到进程管理、存储管理、设备管理相关的功能这些管理也需要得到内核的支持，所以会切换为内核态，在得到内核支持后再次转为用户态。因此每一个模块都需要请求内核服务，每次请求都会涉及到CPU状态转换的过程。

因此采用大内核结构只需要两次变态即可。如果采用微内核体系结构整个过程就需要六次变态。而需要注意的是变态的过程是有成本的，要消耗不少时间，频繁地变态会降低系统性能。

操作系统体系结构总结：

7.2 其他结构体系

操作系统体系结构还有分层结构、模块化结构和外核结构。

• 分层结构操作系统

  内核分为多层，每层可以单向调用更低一层提供的接口。

  

  最底层是硬件，最高层是用户接口，每层可调用更低一层，如第二层只能调用第一层为其提供的接口。

  优点：

  1. 便于调试和验证，自底向上逐层调试验证。
  2. 易扩充和易维护，各层之间调用接口清晰固定。由于层与层之间的接口是固定的，所以两层之间再添加一层也很简单。

  缺点：

  1. 仅可调用相邻低层，难以合理定义各层的边界。如进程需要使用到内存管理，而内存管理相关的功能有时候又需要使用到进程管理。这种相互调用关系很难定义其层次。
  2. 效率低，不可跨层调用，系统调用执行时间长。如果用户需要用到底层提供功能只能一层一层向下传递调用，所以效率低。

• 模块化结构

  一种很经典的程序设计思想，将内核分为多个模块，各模块之间相互协作。其内核$=$$=$主模块$+$$+$可加载内核模块。

  主模块：只负责核心功能，如进程调度、内存管理。

  可加载内核模块：可以动态加载新模块到内核，而无需重新编译整个内核，如驱动程序。

  

  优点：

  1. 模块间逻辑清晰易于维护，确定模块间接口后即可多模块同时开发。如进程管理需要对外暴露多个功能接口，只要规定好这三个功能接口的参数，函数名，返回值。多个模块之间就能并行开发。
  2. 支持动态加载新的内核模块(如：安装设备驱动程序、安装新的文件系统模块到内核)，增强OS适应性
  3. 任何模块都可以直接调用其他模块，无需采用消息传递进行通信，效率高

  缺点：

  1. 模块间的接口定义未必合理、实用
  2. 模块间相互依赖，更难调试和验证

• 外核

  内核负责进程调度、进程通信等功能， 外核负责为用户进程分配未经抽象的硬件资源(如磁盘存储空间)，且由外核负责保证资源使用安全。

  

  再普通的操作系统中，用户进程申请使用一片内存空间，操作系统分配这块内存空间是经过抽象的，经过虚拟化的，对于用户进程来说这些空间似乎拥有一整片连续的空间，但事实上这只是虚拟的地址空间，操作系统会将虚拟的地址空间映射到实际的物理物理空间当中。这些物理页框在实际中通常是离散的，类似于计算机组成原理中的虚拟存储技术。这里未经抽象资源指的是操作系统分配的空间在实际存储空间中是连续存放的。也就是说如果用户进程知道某些数据要被频繁的访问到，此时就可以向外核申请分配一整片连续的磁盘块。之后访问这些磁盘中的数据时，磁盘磁头移动距离会变小，性能会提升。这是外存的分配。同理内存分配也一样。

  而且外核还要保证资源使用安全，如进程$A$$A$在内存中分配了一整片连续存储空间用于存放数据。那么另一个进程$B$$B$想要访问这一片区域，外核就需要发现并制止，同时进程$A$$A$要访问除这一片连续存储空间之外的空间也应该被禁止。

  优点：

  1. 外核可直接给用户进程分配"不虚拟、不抽象"的硬件资源，使用户进程可以更灵活的使用硬件资源
  2. 减少了虚拟硬件资源的"映射层"，提升效率。

  缺点：

  1. 降低了系统一致性
  2. 使系统变得更复杂

  系统中有的进程会申请虚拟的地址空间，这种申请还需要映射。而有的会申请物理真实空间。这种情况后序管理需要考虑各种情况，所以降低了系统一致性，导致系统变得复杂。

• 大内核(宏内核)与微内核

  大内核：所有的系统功能都放在内核里(大内核结构的OS通常也采用了"模块化"的设计思想)

  微内核：只把中断、原语、进程通信等最核心的功能放入内核。进程管理、文件管理、设备管理等功能以用户进程的形式运行在用户态

  

  大内核中各个功能也是可以相互调用的，就和函数一样。

  而微内核就只会将与硬件最紧密的功能放在内核中，大多数的功能会被放到微内核之外，在这种情况下功能与功能之间的调用就不太方便了，两个管理功能之间调用就需要通过消息传递方式来进行。如进程管理模块调用存储管理模块，需要先向微内核发送消息，消息中参数就指明要调用谁，调用的参数等信息。之后会由微内核的进程通信功能把该消息传递给被调用者存储管理模块。当存储管理模块接收到进程管理消息后才会处理调用的请求。同时存储管理模块要返回调用结果，也需要通过消息传递方式让微内核协助各个模块间的调用和返回。

  大内核优点：性能高，内核内部各种功能都可以直接相互调用

  大内核缺点：

  1. 内核庞大功能复杂，难以维护
  2. 大内核中某个功能模块出错，就可能导致整个系统崩溃

  微内核优点：

  1. 内核小功能少、易于维护，内核可靠性高
  2. 内核外的某个功能模块出错不会导致整个系统崩溃

  微内核缺点：

  1. 性能低，需要频繁的切换用户态$/$$/$核心态。
  2. 用户态下的各功能模块不可以直接相互调用，只能通过内核的"消息传递"来间接通信。

8. 操作系统引导

当新硬盘安装好操作系统后，磁盘分区如下：

可以看到磁盘开头会留出一片区域，用于存储主引导记录(MBR)。其中包含两个重要部分，一部分是磁盘引导程序，另一部分是分区表。

分区表其实就是一个数据结构，这个数据结构说明了磁盘每个分区分别占多大空间，以及每个分区的地址范围。这些分区里最重要的是C盘。C盘是磁盘活动分区，其中安装了操作系统。C盘内部结构如下：

可以看到除了根目录还有一个引导记录(PBR)，这个引导记录负责找到启动管理器。

启动过程是主板上的BIOS自举程序(本质上属于主存)，会将磁盘的主引导记录读入内存。主引导记录包含磁盘引导程序，之后主存会执行磁盘引导程序，这个引导程序会根据分区表找到C盘所处位置。接着读入C盘中的引导记录，这个引导记录本质上也是一个程序，之后CPU执行引导记录程序知道启动管理器。这个启动管理器本质上也是一个程序，存放在C盘根目录下的某个位置。在根目录找到启动管理器后会放入主存，最后CPU再执行启动管理程序，完成一系列的初始化工作。

操作系统引导开机总结：

1. CPU从一个特定主存地址开始，取指令，执行ROM中的引导程序(先进行硬件自检，再开机)
2. 将磁盘的第一块主引导记录读入内存，执行磁盘引导程序，扫描分区表
3. 从活动分区( 又称主分区，即安装了操作系统的分区)读入分区引导记录，执行其中的程序
4. 从根目录下找到完整的操作系统初始化程序(即启动管理器)并执行，完成"开机"的一系列动作

9. 虚拟机

虚拟机：使用虚拟化技术，将一台物理机器虚拟化为多台虚拟机器(Virtual Machine, VM)，每个虚拟机器都可以独立运行一个操作系统。

同义术语：虚拟机管理程序$/$$/$虚拟机监控程序$/$$/$NVirtual Machine Monitor$/$$/$Hypervisor

虚拟机管理程序分为两类：直接运行在硬件上、运行在宿主操作系统上。

• 直接运行在硬件上

  类似于传统的操作系统，会负责直接管理硬件资源，并且分配这些硬件资源。

  

  这类VMM会直接运行在硬件上，由虚拟机管理程序将一台物理机器，虚拟化为多台虚拟机器。会把总的硬件资源划分为多个部分，分别给多个虚拟机使用。而每个虚拟机上可以安装各自的操作系统。

  CPU资源分配通过时间片划分实现。一个虚拟机分配若干个时间片，这样在上层操作系统看来，似乎就是一个独立的CPU在为自己工作。磁盘喝内存也是类似按照空间分配给不同虚拟机。

  值得一提的是只有虚拟机管理程序是运行在内核态的，可以使用特权最高的指令。而上层操作系统和应用程序实际上是运行在用户态的。如果上层操作系统需要用到特权指令，这个行为动作会被虚拟管理程序检测到。此时虚拟机管理程序会将特权转化模拟出对应的特权指令执行结果反馈给上层操作系统。

• 运行在宿主操作系统上

  并不是运行在硬件之上，而是运行在 宿主操作系统之上的一类虚拟机管理软件。

  

  这一类的虚拟机管理程序不是直接运行在硬件上的，而是运行在宿主操作系统上的。可以在操作系统上安装第二类虚拟机管理程序。如：VMware和VirtualBox。这类第二类虚拟管理程序上可以安装其他操作系统。

由于两个操作系统实现方式各不相同，会造成一些特性上的差异。

上面提到指令的特权级，实际上在CPU中特权指令是有分级的

上图Ring3最低权限的指令，而Ring0是最高权限的指令。这样划分为更多级别是有好处的，如第一类VMM当上层操作系统使用低一级别的特权指令虚拟机管理程序不需要做中断处理。除非要使用少数最高权限的指令，虚拟机管理程序才会介入。

二. 进程管理

要了解进程之前先看看程序的概念：程序是静态的，就是个存放在磁盘里的可执行文件，就是一系列的指令集合。

进程：进程是动态的，是程序的一次执行过程。而同一个程序多次执行会对应多个进程。

当这些进程被创建的时候，操作系统会给该进程分配一个分配一个唯一的、不重复的"身份证号"PID (Process ID，进程ID)。而操作系统不止要记录这个程序对应的进程PID，进程所属用户(UID)等；还要为了实现操作系统对资源的管理，要记录给进程分配了哪些资源(如：分配了多少内存、正在使用哪些$I/O$$I/O$设备、正在使用哪些文件)以及为了实现实现操作系统对进程的控制、调度，还要记录进程的运行情况(如：CPU使用时间、磁盘使用情况、网络流量使用情况等)。

这些信息都被保存在一个数据结构PCB ( Process Control Block)中，即进程控制块。操作系统需要对各个并发运行的进程进行管理，但凡管理时所需要的信息，都会被放在PCB中。

所以操作系统的进程控制块很重要，因为PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB。PCB要保存内容如下：

除了PCB之外进程还有两个很重要组成部分：程序段和数据段。

PCB是给操作系统用的。而程序段、数据段是给进程自己用的。

当系统执行可执行文件(如exe)时，会先将这个可执行文件中保存的指令序列读入内存中，并且操作系统会建立一个与之相对应的进程，也就是要创建相对应的PCB。除了PCB这个可执行程序的一些列指令序列也要读入内存当中。而这一系列的指令序列被称为程序段。执行过程就是CPU从程序段中一条一条读入指令并执行。可执行程序中处理有指令之外，还有可能存在数据(如变量)，这些变量的内容也需要放到内存当中，存放数据的区域就叫做数据段。

所以一个进程实体(进程映像)由PCB、程序段、数据段组成。进程是动态的，而进程实体(进程映像)是静态的。可以把进程实体理解为进程在动态执行过程当中某一时刻的快照。进程实体能够反映其在某一个时刻的状态(如：x++后，x=2)。所以更准确的说应该是进程实体是由PCB、程序段和数据段组成。

引入进程实体的概念后，可把进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

上面的调度就是指操作系统决定让哪个进程上CPU运行。假如同时挂三个QQ号，会对应三个QQ进程，它们的PCB、数据段各不相同，但程序段的内容都是相同的(都是运行着相同的QQ程序)

程序是静态的，进程是动态的，相比于程序，进程拥有以下特征：

1. 动态性(最基本的特征)：进程是程序的一次执行过程，是动态地产生、变化和消亡的
2. 并发性：内存中有多个进程实体，各进程可并发执行
3. 独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位
4. 异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供"进程同步机制"来解决异步问题
5. 结构性：每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB组成

1. 进程的状态与转换

进程的状态有：创建状态、就绪状态、运行状态、阻塞状态、终止状态

• 创建状态

  当可执行文件调入内存后，操作系统会为其建立一个PCB，即建立相应的进程。进程正在被创建时，它的状态是"创建态"，在这个阶段操作系统会为进程分配资源、初始化PCB。

• 就绪状态

  当进程创建完成后，便进入"就绪态"，处于就绪态的进程已经具备运行条件，但由于没有空闲CPU，就暂时不能运行。

  一个操作系统中可能会有很多进程处于就绪态，当CPU空闲时，操作系统就会选择一个就绪进程，让它上CPU运行。

• 运行状态

  如果一个进程此时在CPU上运行，那么这个进程处于"运行态"。运行态CPU会执行该进程对应的程序(执行指令序列)。

• 阻塞状态

  在进程运行的过程中，可能会请求等待某个事件的发生(如等待某种系统资源的分配，或者等待其他进程的响应)在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入"阻塞态"。

  假如CPU上运行的某个进程中指令要使用到打印设备，但是打印设备正在为其他进程服务，那么这个程序在获得，所需资源之前，进程无法再往下执行。此时操作系统会剥夺这个进程对CPU使用权，并让这个进程处于阻塞状态。此时CPU空闲，又会选择另一个"就绪态"的进程上CPU运行。

• 终止状态

  一个进程可以执行exit系统调用，请求操作系统终止该进程。此时该进程会进入"终止态"，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB。

  当终止进程的工作完成之后，这个进程就彻底消失了。

1.1 进程状态切换

综上所述，如果一个进程正在被创建，此时就会处于创建态。当进程被创建后就具备让CPU执行的条件，这个时候进程就进入就绪态。如果处于就绪态的进程被操作系统调度，那这个进程就可以在CPU上运行，当进程在CPU上运行时，就处于运行态。而有的时候正在运行的进程会请求等待某些事件的发生，在这个事件发生之前，这个进程是没法继续执行的，这种情况下该进程会进入阻塞态。如果处于阻塞态的进程等待的事件发生了，这个进程就可以重新回到就绪态。而当进程进程运行结束，或运行过程中遇到不可修复的错误，就会处于终止态。

运行态到阻塞态的转换是一种进程自身做出的主动行为。而阻塞态到就绪态的转换并不是进程自身能够控制的，是一种被动行为。

注意：不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态(因为进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求)。

有的时候进程可以直接从运行态转换为就绪态。如操作系统给进程分配的时间片用完，进程就会从运行态转化就绪态。

进程的整个生命周期中，大部分时间都处于运行态、就绪态、阻塞态三种基本状态。单核CPU情况下，同一时刻只会有一个进程处于运行态，多核CPU情况下，可能有多个进程处于运行态。

操作系统记录这些状态方法是在进程PCB中，会有一个变量state来表示进程的当前状态。如：$1$$1$表示创建态、$2$$2$表示就绪态、$3$$3$表示运行态。另外为了对同一个状态下的各个进程进行统一的管理， 操作系统会将各个进程的PCB组织起来。

1.2 进程的组织

PCB组织也称进程组织，其组织方式有两种：链接方式和索引方式。

• 链式方式

  是指操作系统会管理一系列的队列，每个队列都会指向相应状态的PCB。

  

  就绪队列指针会指向就绪态的进程。为了方便CPU执行，会把优先级高的进程放在队头。

  很多操作系统还会根据阻塞原因不同再将阻塞队列分为多个：

  

• 索引方式

  操作系统会给各种状态的进程建立相应的索引表，每一个索引表的表项又会指向相应的PCD

  

大部分操作系统使用链式方式。

1.3 进程的控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

进程控制简单理解就是要实现进程状态转换。进程控制实现需要用到"原语"。原语是一种特殊的程序，它的执行具有原子性。也就是说，这段程序的运行必须一气呵成，不可中断。

假设PCB中的变量state表示进程当前所处状态，1表示就绪态，2表示阻塞态。如果一个进程处于就绪态state$=1$$=1$，那么这个进程的PCB需要挂在就绪队列中。而如果state$=2$$=2$，这个进程就应该被挂在阻塞队列中。

假设当前进程处于阻塞，而等待事件发生，则操作系统中，就需要将该进程从阻塞态转换为就绪态。负责进程控制的内核程序至少需要做这样两件事才能完成转换：

1. 将PCB的state值改为$1$$1$
2. 将PCB从阻塞队列放到就绪队列

上面两步转换需要有原子性。假如现在将一个处于阻塞进程$PCB2$$PCB2$的PCB的state值修改为$1$$1$，之后CPU突然检测到一个中断信号，需要对中断进行处理。而这个时候，PCB2的state值是$1$$1$代表就绪态，但此时所处的队列仍是阻塞队列，这就导致state变量和所处队列产生了不一致问题。所以这个转换步骤不能一气呵成就会出现这种问题。

上面提到过原语具有原子性的特征，其可以使用关中断和开中断这两个特权指令实现原子性。CPU执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。这样，关中断与开中断之间的这些指令序列就是不可被中断信号中断的，从而就实现了"原子性"。

所以进程状态转换必须要一气呵成。可以用原语实现，原语的实现又需要开中断和关中断指令来配合完成。

创建原语

如果一个进程需要创建就需要用到创建原语。过程是要先申请一个空白的PCB，另外再给新进程分配所需资源(如内存空间等)。之后对PCB内容进行初始化工作。最后将PCB插入到就绪队列。

引起创建原语事件有：

1. 用户登录

   分时系统中，用户登录成功，系统会建立为其建立一个新的进程

2. 作业调度

   多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程。这里的作业指的是此时还放在外存中还没有投入运行的程序。

3. 提供服务

   用户向操作系统提出某些请求时，会新建一个进程处理该请求

4. 应用请求

   由用户进程主动请求创建一个子进程

撤销原语

终止一个进程时使用。使用撤销原语会让进程从某一个状态转换为终止态，最终进程从系统中消失。

撤销过程是：

1. 从PCB集合中找到终止进程的PRCB
2. 若进程正在运行，立即剥夺CPU，将CPU分配给其他进程
3. 同时会终止其所有子进程。进程间的关系是树形结构所以有父进程和子进程。
4. 将该进程拥有的所有资源归还给父进程或操作系统
5. 删除该进程的PCB

引起进程终止事件：

1. 正常结束

   一进程自己请求终止 (exit系统调用)

2. 异常结束 整数除以0、非法使用特权指令，然后被操作系统强行杀掉

3. 外界干预 Ctrl+Alt+delete，用户选择杀掉进程

阻塞原语

有的时候一个进程会从运行态转换为阻塞态。这情况下操作系统会执行阻塞原语实现这个切换。

阻塞过程：

1. 找到要阻塞的进程对应的PCB
2. 保护进程运行现场，将PCB状态信息设置为"阻塞态"，暂时停止进程运行
3. 将PCB插入相应事件的等待队列

引起进程阻塞事件：

1. 需要等待系统分配某种资源
2. 需要等待相互合作的其他进程完成工作

唤醒原语

如果一个阻塞进程等待的事件发生后，操作系统会让这个阻塞进程从阻塞态转换为就绪态。

唤醒过程：

1. 在事件等待队列中找到PCB
2. 将PCB从等待队列移除，设置进程为就绪态
3. 将PCB插入就绪队列，等待被调度

引起唤醒事件是阻塞进程等待的事件发生。要注意的是一个进程因何事阻塞，就应由何事唤醒。

所以阻塞原语和唤醒原语必须成对使用。

切换原语

会让处于运行态的进程切换为就绪态，接着再让让处于就绪态的原语切换为运行态。所以会改变两个进程状态。

切换执行过程：

1. 将运行环境信息存入PCB
2. PCB移入相应队列
3. 选择另一个进程执行，并更新其PCB
4. 同时根据PCB恢复新进程所需的运行环境

这里运行环境是指当程序在运行时会将数据保存在寄存器中，此时如果另一个程序用到寄存器则会覆盖原来程序存在寄存器中的数据。所以解决办法是在进程切换时先在PCB中保存这个进程的运行环境(只保存一些必要的寄存器信息)。当原来的进程再次投入运行时，可以通过PCB恢复它的运行环境。

总之运行环境就是进程运行过程中寄存器存放的数据。当一个进程下处理机时需要把该线程的运行环境存入PCB中，而当一个进程需要重新回到处理机运行时，就可以从PCB中恢复之间的运行环境。所以保存进程的运行环境和恢复进程的运行环境是实现进程并发执行很关键的技术。

引起进程切换事件：

1. 当前进程时间片到.
2. 有更高优先级的进程到达
3. 当前进程主动阻塞
4. 当前进程终止

无论哪个进程控制原语，要做的无非三类事情：

1. 更新PCB中的信息。主要是修改进程状态(state)或者是往PCB中保存$/$$/$恢复运行环境
2. 将PCB插入合适的队列
3. 进程创建和终止时，还要分配$/$$/$回收资源

2. 进程通信

进程间通信(Inter-Process Communication，IPC)是指两个进程之间产生数据交互。

进程之间的通信需要操作系统内核的支持。原因如下：

进程是分配系统资源的单位(包括内存地址空间)，因此各进程拥有的内存地址空间相互独立。

如上图进程P不能访问进程Q地址空间。这样的规定是处于安全考虑，因此两个进程之间的通信需要操作系统的支持。

通信方式有：共享存储、消息传递和管道通信。

2.1 共享存储

各个进程虽然只能访问自己的存储空间。但是如果操作系统支持共享存储方式，那么一个进程可以申请一片共享存储区。

上图进程P与进程Q可以通过共享存储区进行通信。Linux实现共享内存方式如下：

1
int shm_e();    //通过shm_open 系统调用， 申请一片共享内存区
2
void * mmap();  //通过mmap系统调用，将共享内存区映射到进程自己的地址空间

可以通过"增加页表项$/$$/$段表项"即可将同一片共享内存区映射到各个进程的地址空间中(第三章内容)

为避免出错，各个进程对共享空间的访问应该是互斥的。即共享存储区一次只能供一个进程进行访问。各个进程可使用操作系统内核提供的同步互斥工具(如P、V操作)。

上面共享存储方式是基于存储区的共享：操作系统在内存中划出一块共享存储区，数据的形式、存放位置都由通信进程控制，而不是操作系统。这种共享方式速度很快，是一种高级通信方式。

还有一种存储共享方式是基于数据结构的共享：比如共享空间里只能放一个长度为$10$$10$的数组。这种共享方式速度慢、限制多，是一种低级通信方式。

2.2 消息传递

进程间的数据交换以格式化的消息(Message) 为单位。进程通过操作系统提供的"发送消息$/$$/$接收消息"两个原语进行数据交换。

格式化的消息由两个部分组成：消息头$+$$+$消息体。其中消息头包括：发送进程ID、接受进程ID、消息长度等格式化的信息。

这种消息传递方式又可以详细划分为：直接通信方式和间接通信方式。

• 直接通信方式：消息发送进程要指明接收进程的ID

  

  假如进程P要给进程Q发送消息，在操作系统的内核区域会管理各个进程的PCB，在各个进程的PCB中包含了一个PCB队列即进程消息队列。如进程Q的PCB中就包含了进程Q消息队列，其他进程要发送给进程Q的消息都放在消息队列中。所以进程P要先在自己的进程地址空间中来格式化消息。接着进程P会使用发送原语send(Q,msg)，指明msg消息要发送给进程Q。这个原语会将消息挂在进程Q的消息队列中。之后进程Q可以使用接受原语receive(P,&msg)，来接收进程P发来的消息。使用接收原语后，操作系统内核会检查进程Q消息队列中是否有进程P发来的消息。队列中找到消息后，操作系统会将这个消息体的数据复制到进程Q的地址空间内。

  

  所谓的直接通信方式就是要点名道姓的消息传递。

• 间接通信方式：通过"信箱"间接地通信。因此又称"信箱通信方式"

  

  当前进程P要和进程Q进行通信，进程P可以通过系统调用在操作系统内核中申请一个或多个邮箱。接着进程P会在自己的地址空间来完善消息体msg的内容。之后进程P可以用发送原语send(A,msg)，来指明要发送到哪个信箱和要发送的是哪个消息体。注意这里是指明哪个信箱而不是进程。

  

  接着进程Q会使用接受原语receive(A,&msg)，指明从信箱A中接受一个消息体msg。之后信箱A消息msg就会被操作系统复制到进程Q地址空间中。

  

  可以多个进程往同一个信箱send消息，也可以多个进程从同一个信箱中receive消息。

2.3 管道通信

可以从管道一端写入数据，另一端读数据。这个管道的数据流向只能是单向的。

站在操作系统的层面，这里提到的管道是一个特殊的共享文件，又名pipe文件。其实就是在内存中开辟一个大小固定的内存缓冲区。

如果两个进程之间要用管道通信进程进程通信，首先需要通过某个进程进行系统调用的方式来申请一个管道文件。操作系统会新建这个管道文件，其实就是在内存中开辟了一个大小固定的内存缓冲区。然后两个进程可以往这个管道中写数据或者读数据。数据的读写具有先进先出(FIFO)特性。

这种方式与共享传递区别在于在共享传递中，两个进程开辟的共享空间可以在共享空间的内部任意位置写入或读出数据，没有任何限制。但是管道通信的方式其本质是一个循环队列，一端写入数据后另一端读出数据必须从队头开始读取，写入数据也必须从队头开始依次往后添加。

管道通信特点：

1. 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置两个管道。

   

2. 各进程要互斥的访问管道(由操作系统实现)

3. 当管道写满时，写进程将阻塞，直到读进程将管道中的数据取走，即可唤醒写进程。

4. 当管道读空时，读进程将阻塞，直到写进程往管道中写入数据，即可唤醒读进程。

5. 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。对此，通常有两种解决方案：

   ①一个管道允许多个写进程，一个读进程(2014年408真题高教社官方答案) ; ②允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据(Linux的方案)。

写进程往管道写数据，即便管道没被写满，只要管道没空，读进程就可以从管道读数据

读进程从管道读数据，即便管道没被读空，只要管道没满，写进程就可以往管道写数据

进程通信总结

3. 线程

操作系统在引入了进程之后可以实现多个程序并发运行。进程是程序的一次执行。但如QQ视频、文字聊天、文件传送等功能显然不可能是由一个程序顺序处理就能实现的。所以引入线程，来增加并发度。

在传统的进程机制当中，CPU会轮流为各个进程进行服务，那么这些进程就可以并发进行。所以在传统的进程机制当中，进程是程序执行流的最小单位。

之后为了满足这种"同时"运行很多程序，又引入线程机制，用来增加系统的并发度。引入了线程机制后，CPU的服务对象不再是进程而是进程当中的一个一个线程。每个进程当中可能包含多个线程，CPU经过算法处理会轮流为这些线程进行服务。这样同一个进程被分为多个线程，像QQ视频和文件传送这两个事情，如果想要并发执行，就可以把这两件事情对应的处理程序放到两个不同的线程下，这两个不容的线程可以并发地执行，自然这两件事也可以并发完成。

所以再引入线程机制之后，线程就成了程序执行流的最小单位。在没有引入线程之前，一个进程就对应一份代码，这些代码只能顺序地依次往下执行。但是在引入线程之后，每一个进程可以有多个线程，并且这些线程可以有各自功能，这些功能可以相同，并且都会被CPU并发处理掉。所以线程可以理解为一种轻量级进程。

总之线程是一个基本的CPU执行单元，也是程序执行流的最小单位。在引入线程之后，不仅是进程之，间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务(如QQ视频、文字聊天、传文件)。

引入线程后，进程只作为除CPU之外的系统资源的分配单元(如打印机、内存地址空间等都是分配给进程的而不是线程)。

引入线程后带来的变化：

• 资源分配、调度

  传统进程机制中，进程是资源分配、调度的基本单位

  引入线程后，进程是资源分配的基本单位，线程是调度的基本单位

• 并发性

  传统进程机制中，只能进程间并发

  引入线程后，各线程间也能并发，提升了并发度

• 系统开销

  传统的进程间并发，需要切换进程的运行环境，系统开销很大

  线程间并发，如果是同一进程内的线程切换，则不需要切换进程环境，系统开销小

  引入线程后，并发所带来的系统开销减小

线程属性如下：

1. 线程是处理机调度的单位
2. 多核CPU计算机中，各个线程可占用不同的CPU
3. 每个线程都有一个线程ID、线程控制块(TCB)
4. 线程也有就绪、阻塞、运行三种基本状态
5. 线程几乎不拥有系统资源，系统资源都在进程。
6. 同一进程的不同线程间共享进程的资源
7. 由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
8. 同一进程中的线程切换，不会引起进程切换
9. 不同进程中的线程切换，会引起进程切换
10. 切换同进程内的线程，系统开销很小
11. 切换不同进程中的线程，系统开销较大

3.1 线程的实现方式及多线程模型

线程的实现方式分为：用户级线程和内核级线程。

多线程模型：一对一模型、多对一模型、多对多模型。

线程的实现方式

• 用户级线程

  早期的操作系统(如：早期Unix)只支持进程，不支持线程。当时的"线程"是由线程库实现的。

  这个时代操作系统视角也只有进程，但是程序员写的应用程序当中可以使用线程库来实现多个线程并发运行。

  

  同样使用QQ视频、文字聊天和传送文件的例子，在不支持线程的系统中，可以分别建立三个进程，这三个进程分别是处理其中的某一个任务。

  

  三个代码写入一个程序：

  xxxxxxxxxx
  9
  1
  int main() {
  2
      int i=0;
  3
      while (true) {
  4
          if (i==0){处理视频聊天的代码; }
  5
          if (i==1){处理文字聊天的代码; }
  6
          if (i==2){处理文件传输的代码; }
  7
          i= (i+1)%3; //i的值为 0,1,2,0,1,2...
  8
      }
  9
  }
  

  从代码的角度看，线程其实就是一段代码逻辑。上述三段代码逻辑上可以看作三个线程while循环就是一个最弱智的线程库，线程库完成了对线程的管理工作( 如调度)。很多编程语言提供了强大的线程库，可以实现线程的创建、销毁、调度等功能。

  

  可以看出操作系统只能看到进程，而线程其实是开发人员自己创建了一个逻辑上的线程。即上面的用户级线程。

  这些用户级的线程的管理是由应用程序通过线程库完成的，并不是操作系统负责的。而线程的切换是由线程库即应用程序自己完成的，在用户态下就可以完成线程的切换工作，并不需要操作系统的介入。并且操作系统也并不能意识到用户级线程的存，只有用户才能感知到用户级线程的存在。因此这也是这种方式叫用户级线程的原因。

  用户级线程优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。

  缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

  另外用用户级方式实现这种情况下CPU的调度单位依然是进程，操作系统是给进程分配调用时间的，所以即便电脑是多核处理机器，但是由于当前方式进程才是CPU调度的基本单位，因此一个进程只能分配一个核心，所以这些线程并不能并行运行。

• 内核级线程

  又称内核支持的线程。这种内核级线程就是操作系统视角也可以看得到线程。大多数现代操作系统都实现了内核级线程，如：Windows、Linux

  

  在引入内核级线程后，线程管理工作是由操作系统完成。既然内核级线程由操作系统管理那线程的切换就需要操作系统介入，因此线程的切换需要CPU从内核态转换为用户态。同时操作系统也能认识到内核级线程的存在。

  内核级线程优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。这种情况下内核级线程是CPU分配的基本单位，这种情况下即便其中某一个线程阻塞，其他的线程依然可以继续执行。

  缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

多线程模型

在支持内核级线程的操作系统中再引入线程库，就可以实现把若干个用户级线程映射到某一个内核级线程。那么根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型：

• 一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。

  

  优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。

  缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

• 多对一模型：多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程。

  

  这种模型就退化为了之前用户级线程。

  优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高。

  缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

  注意：操作系统只"看得见"内核级线程，因此只有内核级线程才是处理机分配的单位。

• 多对多模型：$n$$n$用户及线程映射到$m$$m$个内核级线程($n\ge m$$n\ge m$)。每个用户进程对应$m$$m$个内核级线程。

  

  克服了多对一模型并发度不高的缺点(一个阻塞全体阻塞)，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。

再区分一下用户级线程和内核级线程：用户级线程是"代码逻辑"的载体。内核级线程是"运行机会"的载体，因此操作系统在分配处理机资源时，是以内核级线程为单位的。所以一段"代码逻辑"只有获得了"运行机会"才能被CPU执行。这种情况下内核级线程才是处理机分配的单位。例如：多核CPU环境下，上图这个进程最多能被分配两个核心。

内核级线程中可以运行任意一个有映射关系的用户级线程代码，只有两个内核级线程中正在运行的代码逻辑都阻塞时，这个进程才会阻塞

3.2 线程的状态与转换

线程的状态与转换与进程的几乎一样。

线程的状态转换最核心的是就绪态、运行态和阻塞态之间的转换。它们之间的转换和进程之间的转换完全一致。

而线程的组织与控制也与进程相似。对于进程来说，每个进程会建立一个与之对应的PCB模块，而进程也是一样，会建立TCB(线程控制模块)。每个TCB中包含的内容有：

有了TCB之后每一个TCB就可以表示一个线程，多个线程的TCB组织起来就是一个线程表。组织方式根据不同系统会有不同的策略。

4. 调度

调度是指当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是"调度"研究的问题。

程序发生调度情况，情况可以分为三个层次：高级调度(作业调度)、中级调度(内存调度)、低级调度(进程调度)。

• 高级调度(作业调度)

  高级调度(作业调度)：按一定的原则从外存的作业后备队列中挑选一个作业调入内存， 并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。

  

  这里需要补充"作业"概念，所谓的作业其实就是指某一个具体的任务。用户向系统提交一个作业可以理解为用户让操作系统启动一个程序(来处理一个具体的任务)。

  而这个程序需要从外存调入内存，而内存空间有限，有时无法将用户提交的作业全部放入内存。为了解决好几个程序需要启动，但内存资源有限先启动哪一个问题。这里计算机采用高级调度(作业调度)。

• 低级调度(进程调度)

  低级调度(进程调度$/$$/$处理机调度)：按照某种策略从就绪队列中选取一个进程，将处理机分配给它。

  

  内存中会有很多进程，而CPU处理资源有限。所以操作系统也需要按照某种策略从就绪队列中选取一个进程，将处理机分配给它。

  进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。并且进程调度的频率很高，一般几十毫秒一次。

• 中级调度(内存调度)

  中级调度(内存调度)：按照某种策略决定将哪个处于挂起状态的进程重新调入内存。

  内存不够时，可将某些进程的数据调出外存。等内存空闲或者进程需要运行时再重新调入内存。暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列，类似与之前的阻塞队列。

  

  如果当前内存有空间，就要按照某种策略决定将哪个处于挂起状态的进程重新调入内存。一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

  这里补充一个与挂起状态相关的七状态模型：暂时调到外存等待的进程状态为挂起状态(挂起态，suspend)。挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态。之前学过五状态模型：

  

  在引入就绪挂起和阻塞挂起两种状态之后就成了七状态模型。如果当前内存不够用，操作系统可能会将一个处于就绪态的进程暂时放到外存中，这个被放入外存的进程就进入就绪挂起状态。一直到内存空间足够或者进程需要继续执行，这个进程会被激活，进程相对应的数据会再次调入内存，这样一个就绪挂起态进程有回到就绪态。

  同时一个处于阻塞态的进程也会被挂起，也可以激活重新回到阻塞态。

  

  而有的操作系统也可以使一个处于阻塞挂起进程当等待时间出现后这个进程就会转换为就绪挂起态。之后当重新调入内存时，会直接进入就绪态而不是阻塞态。

  

  而有的时候，一个进程处于运行态结束后，会被放入外存中处于就绪挂起状态。有的时候当一个进程创建完PCB后有可能出现内存空间不够情况，这种情况下会先进入就绪挂起态。

  

  注意"挂起"和"阻塞"的区别，两种状态都是暂时不能获得CPU的服务，但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。

  有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。

三层调度的联系、对比：

4.1 进程调度的时机、切换与过程、方式

进程调度(低级调度)，就是按照某种算法从就绪队列中选择一个进程为其分配处理机。

进程调度时机

需要进行进程调度与切换的情况：

• 当前运行的进程主动放弃处理机

  如：进程正常终止、运行过程中发生异常而终止、进程主动请求阻塞(如等待$I/O$$I/O$)

• 当前运行的进程被动放弃处理机

  如：分给进程的时间片用完、有更紧急的事需要处理(如$I/O$$I/O$中断)、有更高优先级的进程进入就绪队列

而进程调度也不是随时都可以进行的，一下情况不能进行调度：

1. 在处理中断的过程中。中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
2. 进程在操作系统内核程序临界区中。但是进程在普通临界区中是可以进行调度、切换的。
3. 在原子操作过程中(原语)。原子操作不可中断，要一气呵成(如之前讲过的修改PCB中进程状态标志，并把PCB放到相应队列)

补充：进程在操作系统内核程序临界区中不能进行调度与切换这是正确的表述。进程处于临界区时不能进行处理机调度是错误的表述。

先来简单看一下临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。所以内核程序临界区和临界区含义如下：

• 内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列(由各就绪进程的PCB组成)
• 临界区是指访问临界资源的那段代码。

当一个进程此时处于内核程序临界区，并且临界区是要访问就绪队列的情况下，在访问之前会将就绪队列上锁。如果进程还没退出临界区 (还没解锁)就进行进程调度，但是进程调度相关的程序也需要访问就绪队列，但此时就绪队列被锁住了，因此又无法顺利进行进程调度。所以内核程序临界区访问的临界资源(种内核数据结构)如果不尽快释放的话，极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度与切换。

另一种情况当一个进程要访问打印机(外部设备)，在打印机打印完成之前，进程一直处于临界区内，临界资源不会解锁。但打印机又是慢速设备，此时如果一直不允许进程调度的话就会导致CPU一直空闲。所以进程在访问普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行调度与切换。

进程调度的方式

有的系统中，进程可以主动放弃处理机，当有更紧急的任务需要处理时，也会强行剥夺处理机(被动放弃)。所以根据当前运行的进程是否可以被强行剥夺处理及资源这个问题可以引出进程调度方式。

进程调度方式可以分为两种：

• 非剥夺调度方式

  非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。

  这种方式实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统。

• 剥夺调度方式

  剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

  这种方式可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能(通过时钟中断)。适合于分时操作系统、实时操作系统。

进程的切换与过程

既然选择一个进程要为其分配处理机，进程与进程切换的过程中会发生以下情况。

首先看看"狭义的进程调度"与"进程切换"的区别：

1. 狭义的进程调度指的是从就绪队列中选中一个要运行的进程。(这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换)
2. 进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

广义的进程调度包含了选择一个进程和进程切换两个步骤。

而进程切换过程主要是以下两步骤：

1. 对原来运行进程各种数据(运行环境)的保存。将环境保存到PCB中。

2. 对新的进程各种数据(运行环境)的恢复。从进程PCB中读出环境数据。

   如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在PCB中

注意：进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

总结：

4.2 调度器和闲逛进程

调度程序是操作系统内核重要程序模块。一个程序会在就绪、运行和阻塞三个状态切换。

上面②③之间状态的转换就是由调度程序决定的。操作系统要决定下面两件事情：

1. 让谁运行?

   具体看调度算法

2. 运行多长时间？

   具体看时间片大小

什么事件会触发调度程序(调度时机)：

• 创建新进程。调度程序会检查是否让新进程直接上处理机运行。
• 进程退出。一个进程执行完毕后，调度程序会让新的进程上处理机运行。
• 运行进程阻塞。
• $I/O$$I/O$中断发生(可能唤醒某些阻塞进程)。当某些阻塞进程以内$I/O$$I/O$中断被唤醒进入就绪态，调度程序仍会检查就绪态进程是否能上处理机运行。
• 非抢占式调度策略，只有运行进程阻塞或退出才触发调度程序工作
• 抢占式调度策略，每个时钟中断或每$k$$k$个时钟中断会触发调度程序工作

上面的是进程，如果一个操作系统支持的不仅是进程，还支持线程，那么调度程序调度对象就是线程。

闲逛进程：如果就绪队列中没有其他就绪进程时，调度程序就会选中闲逛进程上处理机运行。

闲逛进程的特性：

1. 优先级最低
2. 可以是$0$$0$地址指令，占一个完整的指令周期(指令周期末尾例行检查中断)
3. 能耗低

末尾理性检查中断会周期性唤醒调度程序，调度程序会检查当前是否有就绪进程，如果有就会让闲逛程序下处理机，就绪进程上处理机。

4.3 调度算法评价指标

调度算法评价指标主要从CPU利用率、系统吞吐量、周转时间、等待时间和响应时间五个方面评价。

由于早期的CPU造价极其昂贵，因此人们会希望让CPU尽可能多地工作。

• CPU利用率：指CPU"忙碌"的时间占总时间的比例。

  $$\text{利}\text{用}\text{率}=\frac{\text{忙}\text{碌}\text{的}\text{时}\text{间}}{\text{总}\text{时}\text{间}}$$

  有的题目还会要求计算某种设备的利用率。

  例题：某计算机只支持单道程序，某个作业刚开始需要在CPU上运行$5$$5$秒，再用打印机打印输出$5$$5$秒，之后再执行$5$$5$秒，才能结束。在此过程中，CPU利用率、打印机利用率分别是多少？

  $$\begin{array}{rl}& CPU\text{利}\text{用}\text{率}=\frac{5+5}{5+5+5}=66.66\mathrm{\%}\\ \\ & \text{打}\text{印}\text{机}\text{利}\text{用}\text{率}=\frac{5}{15}=33.33\mathrm{\%}\end{array}$$

  通常会考察多道程序并发执行的情况，可以用"甘特图"来辅助计算。

• 系统吞吐量

  对于计算机来说，希望能用尽可能少的时间处理完尽可能多的作业。

  系统吞吐量：单位时间内完成作业的数量

  $$\text{系}\text{统}\text{吞}\text{吐}\text{量}=\frac{\text{总}\text{共}\text{完}\text{成}\text{了}\text{多}\text{少}\text{道}\text{作}\text{业}}{\text{总}\text{共}\text{花}\text{了}\text{多}\text{少}\text{时}\text{间}}$$

  例题：某计算机系统处理完$10$$10$道作业，共花费$100$$100$秒，在系统吞吐量为？

  $$\frac{10}{100}=0.1\text{道}/\text{秒}$$

• 周转时间

  对于计算机的用户来说，他很关心自己的作业从提交到完成花了多少时间。

  周转时间，是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。

  它包括四个部分：作业在外存后备队列上等待作业调度(高级调度)的时间、进程在就绪队列上等待进程调度(低级调度)的时间、进程在CPU上执行的时间、进程等待$I/O$$I/O$操作完成的时间。后三项在一个作业的整个处理过程中，可能发生多次。

  $$\begin{array}{rl}& (\text{作}\text{业})\text{周}\text{转}\text{时}\text{间}=\text{作}\text{业}\text{完}\text{成}\text{时}\text{间}-\text{作}\text{业}\text{提}\text{交}\text{时}\text{间}\\ \\ & \text{平}\text{均}\text{周}\text{转}\text{时}\text{间}=\frac{\text{各}\text{作}\text{业}\text{周}\text{转}\text{时}\text{间}\text{之}\text{和}}{\text{作}\text{业}\text{数}}\end{array}$$

  有的作业运行时间短，有的作业运行时间长，因此在周转时间相同的情况下，运行时间不同的作业，给用户的感觉肯定是不一样的。如：排队上厕所，本来只用一分钟，但排队等待需要十分钟。而另一个人使用厕所十分钟，排队只用一分钟。因此又提出另一种指标：

  $$\text{带}\text{权}\text{周}\text{转}\text{时}\text{间}=\frac{\text{作}\text{业}\text{周}\text{转}\text{时}\text{间}}{\text{作}\text{业}\text{实}\text{际}\text{运}\text{行}\text{的}\text{时}\text{间}}=\frac{\text{作}\text{业}\text{完}\text{成}\text{时}\text{间}-\text{作}\text{业}\text{提}\text{交}\text{时}\text{间}}{\text{作}\text{业}\text{实}\text{际}\text{运}\text{行}\text{的}\text{时}\text{间}}$$

  因此对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被服务的时间更多，带权周转时间更小，用户满意度更高。

  而对于实际运行时间相同的两个作业，周转时间短的带权周转时间更小，用户满意度更高

  相应的也有一个平均带权时间

  $$\text{平}\text{均}\text{带}\text{权}\text{周}\text{转}\text{时}\text{间}=\frac{\text{各}\text{作}\text{业}\text{带}\text{权}\text{周}\text{转}\text{时}\text{间}\text{之}\text{和}}{\text{作}\text{业}\text{数}}$$

• 等待时间

  计算机的用户希望自己的作业尽可能少的等待处理机。

  所以等待时间，指进程$/$$/$作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

  

  当一个作业刚开始提交的时候是放在外存中的作业后备队列当中，作业在后备队列当中需要被服务(调度)，当调度之后作业就会放到内存当中，并且建立起相应的进程，当进程建立后会被CPU或$I/O$$I/O$设备服务，当然也会有等待被服务的时候。

  对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待$I/O$$I/O$完成的期间其实进程也是在被服务的，所以不计入等待时间。

  另外对于对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

  一个作业总共需要被CPU服务多久，被$I/O$$I/O$设备服务多久一般是确定不变的，因此调度算法其实只会影响作业$/$$/$进程的等待时间。当然，与前面指标类似，也有"平均等待时间"来评价整体性能。

  这里的平均等待时间就是将所有进程或者作业的等待时间加和，再除以作业的数量即可。

• 响应时间

  对于计算机用户来说，会希望自己的提交的请求(比如通过键盘输入了一个调试命令)尽早地开始被系统服务、回应。

  响应时间，指从用户提交请求到首次产生响应所用的时间。

调度算法评价指标总结：

4.4 调度算法

调度算法有先来先服务(FCFS)、短作业优先(SJF)、高响应比优先(HRRN)、时间片轮转(RR)、优先级调度、多级反馈队列

先来先服务(FCFS)

算法思想：主要从"公平"的角度考虑(类似于我们生活中排队买东西的例子)

算法规则：按照作业$/$$/$进程到达的先后顺序进行服务，事实上就是等待时间越久的越优先得到服务。

用于作业$/$$/$进程调度：用于作业调度时，考虑的是哪个作业先到达后备队列；用于进程调度时，考虑的是哪个进程先到达就绪队列。

这种先来先服务算法一般是非抢占式算法，也就是说对于当前正在占用处理机的进程(作业)，之有这个进程主动放弃处理机时，才会进行调度，才会用调度算法规则选择下一个上处理机运行的进程。

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用先来先服务调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

上图可知，调度顺序为: P1$\to$$\rightarrow$P2$\to$$\rightarrow$P3$\to$$\rightarrow$P4。各个进程运行时间如下：

1. 周转时间$=$$=$完成时间$-$$-$到达时间

   故P1$=7-0=7$$=7-0=7$；P2$=11-2=9$$=11-2=9$；P3$=12-4=8$$=12-4=8$；P4$=16-5=11$$=16-5=11$

2. 带权周转时间$=$$=$周转时间$/$$/$运行时间

   故P1$=7/7=1$$=7/7=1$；P2$=9/4=2.25$$=9/4=2.25$；P3$=8/1=8$$=8/1=8$；P4$=11/4=2.75$$=11/4=2.75$

3. 等待时间$=$$=$周转时间$-$$-$运行时间

   P1$=7-7=0$$=7-7=0$；P2$=9-4=5$$=9-4=5$；P3$=8-1=7$$=8-1=7$；P4$=11-4=7$$=11-4=7$

   注意：本例中的进程都是纯计算型的进程，一个进程到达后要么在等待，要么在运行。如果是又有计算、又有$I/O$$I/O$操作的进程，其等待时间就是周转时间$-$$-$运行时间$-I/O$$-I/O$操作的时间$t$$t$。

4. 平均周转时间$=(7+9+8+11)/4=8.75$$=(7+9+8+11)/4=8.75$

   平均带权周转时间$=(1+2.25+8+2.75)/4=3.5$$=(1+2.25+8+2.75)/4=3.5$

   平均等待时间$=(0+5+7+7)/4=4.75$$=(0+5+7+7)/4=4.75$

可以看到上面P3的周转时间比运行时间多了$8$$8$倍。

算法优点：公平、算法实现简单

缺点：排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。即，FCFS算法对长作业有利，对短作业不利(如：排队买奶茶你只买一杯，但前面有个人买$20$$20$杯)

如果某个进程$/$$/$作业长期得不到服务，则称为"饥饿"。显然先来先服务算法不会导致饥饿。因为前面的进程给总会被处理完毕。

短作业优先(SJF)

可以看出FCFS对于带权周转时间、平均等待时间这些指标不算优秀，为了追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间提出了短作业优先(SJF)算法。

算法规则：最短的作业$/$$/$进程优先得到服务(所谓"最短"，是指要求服务时间最短)。

该算法即可用于作业调度，也可用于进程调度。用于进程调度时称为"短进程优先(SPF, Shortest Process First)算法"。

SJF和SPF是非抢占式的算法。但是也有抢占式的版本：最短剩余时间优先算法(SRTEN, Shortest Remaining Time Next)

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用短作业优先调度算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

上图可知，当P1进程到达时会直接运行，运行时间为$7$$7$，则P1进程运行结束时，P2、P3、P4进程都会到达，则按照运行时间最短及运行时间相同按先到先服务原则，调度顺序为: P1$\to$$\rightarrow$P3$\to$$\rightarrow$P2$\to$$\rightarrow$P4。各个进程运行时间如下：

1. 周转时间$=$$=$完成时间$-$$-$到达时间

   故P1$=7-0=7$$=7-0=7$；P3$=8-4=4$$=8-4=4$；P2$=12-2=10$$=12-2=10$；P4$=16-5=11$$=16-5=11$

2. 带权周转时间$=$$=$周转时间$/$$/$运行时间

   故P1$=7/7=1$$=7/7=1$；P3$=4/1=4$$=4/1=4$；P2$=10/4=2.5$$=10/4=2.5$；P4$=11/4=2.75$$=11/4=2.75$

3. 等待时间$=$$=$周转时间$-$$-$运行时间

   P1$=7-7=0$$=7-7=0$；P3$=4-1=3$$=4-1=3$；P2$=10-4=6$$=10-4=6$；P4$=11-4=7$$=11-4=7$

4. 平均周转时间$=(7+4+10+11)/4=8$$=(7+4+10+11)/4=8$

   平均带权周转时间$=(1+4+2.5+2.75)/4=2.56$$=(1+4+2.5+2.75)/4=2.56$

   平均等待时间$=(0+3+6+7)/4=4$$=(0+3+6+7)/4=4$

对比FCFS算法的结果，显然SPF算法的平均等待$/$$/$周转$/$$/$带权周转时间都要更低

当上题改为用最短剩余时间优先算法(SRTEN, Shortest Remaining Time Next)，每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度。

故需要注意的是，当有新进程到达时就绪队列就会改变，就要按照上述规则进行检查。各个时刻的情况如下：

$0$$0$时刻(P1到达)：P1(7)

$2$$2$时刻(P2到达)：P1(5)、P2(4)

$4$$4$时刻(P3到达)：P1(5)、P2(2)、P3(1)

$5$$5$时刻(P3完成且P4刚好到达)：P1(5)、P2(2) 、P4(4)

$7$$7$时刻(P2完成) : P1 (5)、P4(4)

$11$$11$时刻(P4完成) : P1(5)

1. 周转时间$=$$=$完成时间$-$$-$到达时间

   故P1$=16-0=16$$=16-0=16$；P2$=7-2=5$$=7-2=5$；P3$=5-4=1$$=5-4=1$；P4$=11-5=6$$=11-5=6$

2. 带权周转时间$=$$=$周转时间$/$$/$运行时间

   故P1$=16/7=2.28$$=16/7=2.28$；P2$=5/4=1.25$$=5/4=1.25$；P3$=1/1=1$$=1/1=1$；P4$=6/4=1.5$$=6/4=1.5$

3. 等待时间$=$$=$周转时间$-$$-$运行时间

   P1$=16-7=9$$=16-7=9$；P2$=5-4=1$$=5-4=1$；P3$=1-1=0$$=1-1=0$；P4$=6-4=2$$=6-4=2$

4. 平均周转时间$=(16+5+1+6)/4=7$$=(16+5+1+6)/4=7$

   平均带权周转时间$=(2.28+1.25+1+1.5)/4=1.50$$=(2.28+1.25+1+1.5)/4=1.50$

   平均等待时间$=(9+1+0+2)/4=3$$=(9+1+0+2)/4=3$

对比非抢占式的短作业优先算法，显然抢占式的这几个指标又要更低。

注意：

1. 如果题目中未特别说明，所提到的"短作业$/$$/$进程优先算法"默认是非抢占式的

2. 很多书上都会说"SJF调度算法的平均等待时间、平均周转时间最少"。

   严格来说，这个表述是错误的，不严谨的。之前的例子表明，最短剩余时间优先算法得到的平均等待时间、平均周转时间还要更少。所以应该加上一个条件"在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最少"；或者说"在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少"。

   如果不加上述前提条件，则应该说"抢占式的短作业$/$$/$进程优先调度算法(最短剩余时间优先，SRNT算法)的平均等待时间、平均周转时间最少"。

3. 虽然严格意义来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法(如FCFS)，SJF依然可以获得较少的平均等待时间、平均周转时间。

短作业优先算法优点："最短的"平均等待时间、平均周转时间。

缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业$/$$/$进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先。

所以这种算法会产生"饥饿"。即如果源源不断地有短作业$/$$/$进程到来，可能使长作业$/$$/$进程长时间得不到服务，产生"饥饿"现象。如果一直得不到服务，则称为"饿死"。

高响应比优先(HRRN)

FCFS算法是在每次调度的时候选择一个等待时间最长的作业(进程)为其服务。但是没有考虑到作业的运行时间，因此导致了对短作业不友好的问题。

SJF算法是选择-一个执行时间最短的作业为其服务。但是又完全不考虑各个作业的等待时间，因此导致了对长作业不友好的问题，甚至还会造成饥饿问题。

而高响应比优先(HRRN)算法，即考虑到各个作业的等待时间，也能兼顾运行时间。

算法思想：要综合考虑作业$/$$/$进程的等待时间和要求服务的时间

算法规则：在每次调度时先计算各个作业$/$$/$进程的响应比，选择响应比最高的作业$/$$/$进程为其服务。响应比计算公式如下：

该算法即可用于作业调度，也可用于进程调度。并且是非抢占式的算法。因此只有当前运行的作业$/$$/$进程主动放弃处理机时(正常$/$$/$异常完成，或主动阻塞)，才需要调度，才需要计算响应比。

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用高响应比优先(HRRN)算法，计算各进程的等待时间、平均等待时间、周转时间、平均周转时间、带权周转时间、平均带权周转时间。

各个时刻的情况如下：

$0$$0$时刻：只有P1到达就绪队列，P1 上处理机。

$7$$7$时刻(P1主动放弃CPU)：就绪队列中有P2响应比$=(5+4)/4=2.25$$=(5+4)/4=2.25$、P3$=(3+1)/1=4$$=(3+1)/1=4$、P4$=(2+4)/4=1.5$$=(2+4)/4=1.5$

$8$$8$时刻(P3完成)：P2(2.5)、 P4(1.75)

$12$$12$时刻(P2完成)：就绪队列中只剩下P4

高响应比优先算法优点：

1. 综合考虑了等待时间和运行时间(要求服务时间)
2. 等待时间相同时，要求服务时间短的优先(SJF的优点)
3. 要求服务时间相同时，等待时间长的优先(FCFS的优点)

对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。

三个调度算法总结：

注：这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心"响应时间"，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法一般适合用于早期的批处理系统，当然，FCFS 算法也常结合其他的算法使用，在现在也扮演着很重要的角色。而适合用于交互式系统的调度算法将在下面介绍。

时间片轮转(RR)

算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应。

算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。

这种算法是用于进程调度的(只有作业放入内存建立了相应的进程后，才能被分配处理机时间片)

若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片轮转调度算法属于抢占式的算法。由时钟装置发出时钟中断来通知CPU时间片已到。

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用时间片轮转调度算法，分析时间片大小分别是$2$$2$时的进程运行情况。

注意：常用于分时操作系统，更注重"响应时间"，因而此处不计算周转时间。

各个时刻的情况如下：

• $0$$0$时刻(P1(5))：$0$$0$时刻只有P1到达就绪队列，让P1上处理机运行一个时间片

• $2$$2$时刻(P2(4)$\to$$\rightarrow$P1(3))：$2$$2$时刻P2到达就绪队列，P1运行完一个时间片，被剥夺处理机，重新放到队尾。此时P2排在队头，因此让P2上处理机。(注意：$2$$2$时刻， P1下处理机，同一时刻新进程P2到达，如果在题目中遇到这种情况，默认新到达的进程先进入就绪队列)

  

• $4$$4$时刻(P1(3)$\to$$\rightarrow$P3(1)$\to$$\rightarrow$P2(2))，此时P3到达，先插到就绪队尾，紧接着，P2下处理机也插到队尾

  

  队头P1上处理机运行

• $5$$5$时刻(P3(1)$\to$$\rightarrow$P2(2)$\to$$\rightarrow$P4(6))：$5$$5$时刻，P4到达插到就绪队尾(注意：由于P1的时间片还没用完，因此暂时不调度。另外，此时P1处于运行态，并不在就绪队列中)

  

• $6$$6$时刻(P3(1)$\to$$\rightarrow$P2(2)$\to$$\rightarrow$P4(6)$\to$$\rightarrow$P1(1)：$6$$6$时刻，P1时间片用完，下处理机，重新放回就绪队尾，发生调度

  

  此时队头P3上处理机运行

• $7$$7$时刻(P2(2)$\to$$\rightarrow$P4(6)$\to$$\rightarrow$P1(1))：虽然P3的时间片没用完，但是由于P3只需运行$1$$1$个单位的时间，运行完了会主动放弃处理机，因此也会发生调度。

  

  队头进程P2上处理机。

• $9$$9$时刻(P4(6)$\to$$\rightarrow$P1(1))：进程P2时间片用完，并刚好运行完，发生调度。

  

  P4上处理机

• $11$$11$时刻(P1(1)$\to$$\rightarrow$P4(4))：P4时间片用完，重新回到就绪队列。

  

  P1上处理机

• $12$$12$时刻(P4(4))：P1运行完，主动放弃处理机，此时就绪队列中只剩P4，P4上处理机。

• $14$$14$时刻()：就绪队列为空，因此让P4接着运行一个时间片。

• $16$$16$时刻：所有进程运行结束

如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。

时间片太大太小影响：

上面"增大进程响应时间"：假如系统中有$10$$10$个进程在并发执行，如果时间片为1秒，则一个进程被响应可能需要等$9$$9$秒。也就是说，如果用户在自已进程的时间片外通过键盘发出调试命令，可能需要等待$9$$9$秒才能被系统响应。

另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

一般来说，设计时间片时要让切换进程的开销占比不超过$1\mathrm{\%}$$1\%$。

时间片轮转算法优点：公平、响应快，适用于分时操作系统。

缺点：由于高频率的进程切换，因此有一定开销；且不区分任务的紧急程度。

这种算法不会导致饥饿出现。

优先级调度算法

算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序

算法规则：每个作业$/$$/$进程有各自的优先级，调度时选择优先级最高的作业$/$$/$进程。

这种算法既可用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的$I/O$$I/O$调度中。

优先级调度算法抢占式和非抢占式都有。做题时的区别在于：非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占。

例题：各进程到达就绪队列的时间、需要的运行时间、进程优先数如下表所示。使用非抢占式的优先级调度算法，分析进程运行情况。(注: 优先数越大，优先级越高)

非抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。

各个时刻的情况如下：

• $0$$0$时刻(P1)：只有P1到达， P1上处理机。
• $7$$7$时刻(P2、 P3、 P4)：P1运行完成主动放弃处理机，其余进程都已到达，P3优先级最高，P3上处理机。
• $8$$8$时刻(P2、P4 )：P3完成，P2、 P4优先级相同，由于P2先到达，因此P2优先上处理机
• $12$$12$时刻(P4)：P2完成，就绪队列只剩P4，P4上处理机。
• 16时刻：P4完成，所有进程都结束。

如果采用抢占式的优先级调度算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。另外，当就绪队列发生改变时也需要检查是会发生抢占。各个时刻的情况如下：

• $0$$0$时刻(P1)：只有P1到达，P1上处理机。
• $2$$2$时刻(P2)：P2到达就绪队列，优先级比P1更高，发生抢占。P1回到就绪队列，P2上处理机。
• $4$$4$时刻(P1、P3)：P3到达，优先级比P2更高，P2回到就绪队列，P3抢占处理机。
• $5$$5$时刻(P1、P2、P4)：P3完成，主动释放处理机，同时，P4也到达，由于P2比P4更先进入就绪队列，因此选择P2上处理机
• $7$$7$时刻(P1、P4)：P2完成， 就绪队列只剩P1、P4、P4上处理机。
• $11$$11$时刻(P1)：P4完成，P1上处理机
• $16$$16$时刻：P1完成，所有进程均完成

补充：就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置。根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种：

1. 静态优先级：创建进程时确定，之后一直不变。
2. 动态优先级：例建进程时有一个初始值，之后会根据情况动态地调整优先级。

设置各类进程优先级原则：系统进程优先级高于用户进程、前台进程优先级高于后台进程、操作系统更偏好$I/O$$I/O$型进程(或称$I/O$$I/O$繁忙型进程)。这里偏好$I/O$$I/O$型进程的原因是$I/O$$I/O$设备和CPU可以并行工作。如果优先让$I/O$$I/O$繁忙型进程优先运行的话，则越有可能让$I/O$$I/O$设备尽早地投入工作，则资源利用率、系统吞吐量都会得到提升。

注意：与$I/O$$I/O$型进程相对的是计算型进程(或称CPU繁忙型进程)。

当采用动态优先级策略时，调整情况可以从追求公平、提升资源利用率等角度考虑。比如某进程在就绪队列中等待了很长时间，则可以适当提升其优先级。如果某进程占用处理机运行了很长时间， 则可适当降低其他先级。另外比如发现一个进程频繁地进行$I/O$$I/O$操作， 则可适当提升其优先级。

优先级调度算法优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。

缺点：若源源不断地有高优先级进程到来，则可能导致饥饿。

多级反馈队列

之前的FCFS算法的优点是公平、SJF算法的优点是能尽快处理完短作业，平均等待$/$$/$周转时间等参数很优秀、而时间片轮转调度算法可以让各个进程得到及时的响应。而刚刚介绍的优先级调度算法可以灵活调整各种进程被服务的机会。而本次要介绍的多级反馈队列调度算法是对以上算法的折中。

算法思想：对其他调度算法的折中权衡。

算法规则：

1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
2. 新进程到达时先进入第$1$$1$级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾。
3. 只有第$k$$k$级队列为空时，才会为$k+1$$k+1$级队头的进程分配时间片

该算法主要用于进程调度，而且是抢占式算法在$k$$k$级队列的进程运行过程中，若更上级的队列$(1\sim k-1\text{级})$$(1\sim k-1级)$中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回$k$$k$级队列队尾。

例题：各进程到达就绪队列的时间、需要的运行时间如下表所示。使用多级反馈队列调度算法，分析进程运行的过程。

首先会设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。

新进程到达时先进入第$1$$1$级队列，按FCFS 原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾。

只有第$k$$k$级队列为空时，才会为$k+1$$k+1$级队头的进程分配时间片

另外被抢占处理机的进程重新放回原队列队尾。上题各个时刻的情况如下：

• $0$$0$时刻：首先进程P1进入第一级队列，由于此时没有别的进程P1会在处理机上运行$1$$1$时间片。

  

• $1$$1$时刻：当P1执行完$1$$1$个时间片后，会被放到第二级队列中，此时P2也会到达，所以由于当前更高队列还有进程没有处理，暂时就不会处理更低一级别的进程。因此当前会选择P2上处理机运行。

  

• $2$$2$时刻：P2执行完$1$$1$个时间片后下处理机，由于第一级队列没有进程，所以对第二级队列进行调度。P1上处理机，且由于第二级队列时间片大小是$2$$2$，所以P1会执行两个时间片。

  

• $4$$4$时刻，P1运行时间没有结束，所以会被放到下一级队列中。当前P2上处理机运行

  

• $5$$5$时刻：当P2在处理机上运行$1$$1$个时间片后，到$5$$5$时刻，P3到达第一级队列。由于此时有一个更高优先级的进程到达，所以会发生抢占处理机的情况。即P2下处理机放回原队列，P3上处理机，由于是第一级队列所以只用执行一个时间片。

  

• $6$$6$时刻：P3运行完毕，调出内存。P2继续上处理机运行，由于P2已经运行$2$$2$个单位时间，所以这次在处理机上运行$2$$2$个单位时间后就执行完成调出内存。

  

• $8$$8$时刻：上面队列全空，最低级的三级队列中的P1上处理机运行，时间片大小为$4$$4$。当$4$$4$个单位时间结束后，P1总共运行$7$$7$个单位时间，但P1要运行$8$$8$个单位时间。且P1已经在下面一级队列中，所以此时P1仍然会被放回到第三级原队列。再次上次处理机运行。

  

多级反馈队列优点：对各类型进程相对公平(FCFS的优点)。每个新到达的进程都可以很快就得到响应(RR的优点)。短进程只用较少的时间就可完成(SPF的优点)。不必实现估计进程的运行时间(避免用户作假)可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、$I/O$$I/O$密集型进程(拓展：可以将因$I/O$$I/O$而阻塞的进程重新放回原队列，这样$I/O$$I/O$型进程就可以保持较高优先级)。

这种算法会导致饥饿出现。因为如果有源源不断地新进程到达，更低级队列的进程就有可能长期得不到服务(饥饿)。

多级调度算法在计算机中的应用：系统中按进程类型设置多个级别队列，进程创建成功后插入某个队列。

队列之间可采取固定优先级，或时间片划分固定优先级：高优先级空时低优先级进程才能被调度。时间片划分：如$100ms$$100ms$的时间三个队列分配时间$50\mathrm{\%}、40\mathrm{\%}、10\mathrm{\%}$$50\%、40\%、10\%$。

各个队列可采用不同的调度策略，如：系统进程队列采用优先级调度、交互式队列采用RR、批处理队列采用FCFS。

三种交互式调度算法总结：

注：比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统(包括分时操作系统、实时操作系统等)更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。(比如UNIX使用的就是多级反馈队列调度算法)

5.进程同步和进程互斥

进程同步：

之间介绍过进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。

而异步性会出现很多问题，如有时候一个变量必须等待用户进行$I/O$$I/O$输入之后，才能进行读取，必须按照$\text{写}\text{数}\text{据}\to \text{读}\text{数}\text{据}$$写数据\rightarrow 读数据$方式。即必须要保证各个进程之间的推进次序必须是合理次序。这就是进程同步问题。而操作系统需要提供这种进程同步的机制。

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

进程同步又被称为进程间的直接制约关系。即进程之间是有直接合作的。

进程互斥：

在之前的学习中可以知道进程的"并发"需要"共享"的支持。各个并发执行的进程不可避免的需要共享一些系统资源(比如内存，又比如打印机、摄像头这样的$I/O$$I/O$设备)。

之前介绍过两种资源共享方式：互斥共享方式和同时共享方式。其中互斥共享指的是系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。同时共享方式是指系统中的某些资源，允许一个时间段内由多个进程"同时"对它们进行访问。

把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)都属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。

对临界资源的互斥访问，可以在逻辑上分为如下四个部分：

xxxxxxxxxx
6
1
do {
2
    entry section;      //进入区
3
    critical section;   //临界区
4
    exit section;       //退出区
5
    remainder section;  //剩余区
6
} while (true)

• 进入区

  负资检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志(可以理解为"上锁")。以阻止其他进星同时进入临界区。

• 临界区

  访问临界资源的那段代码。如通过打印机打印输出，对打印机进行写操作的代码就会放到临界区中。

• 退出区

  负责解除正在访问临界资源的标志(可以理解为"解锁")。

• 剩余区

  可以做其他处理。

注意：临界区是进程中访问临界资源的代码段。进入区和退出区是负责实现互斥的代码段。临界区也可称为"临界段"。

为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则：

1. 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
2. 忙则等待。当已有进程进入临界区时，其他试图进入临界区的进程必须等待。
3. 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)。
4. 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

进程互斥又被称为进程间的间接制约关系。因为进程之间并没有直接的合作关系，只是想要互斥的使用某种系统临界资源。

5.1 进程互斥软件实现

如果一个系统中没有进程互斥，假设进程A、进程B在系统中并发地运行：

先调度A上处理机运行当A在使用打印机的过程中，分配给它的时间片用完了，接下来操作系统调度B让它上处理机运行，进程B也使用到打印机。所以由于A进程打印机使用到一半时，B进程也开始使用，结果会导致A，B两个进程的内容会打印在一起混淆。

如果两个进程可以互斥访问打印机，即只有A进程使用完打印机后，B才可以接着访问打印机。这种情况下就不会出现上面的问题。

可以用软件来实现互斥。

单标志法

算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另-一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予。

首先设置一个变量turn，这个变量表示当前允许进入临界区的进程号。如turn=0表示当前允许进程$0$$0$进入临界区。

两个进程对临界区访问代码如上图。

每个进程都会在进入区(while)判断此时是不是允许自己进入，即把turn值和自己的编号进行对比。如果turn的值不等于自己的编号，那么此时只允许另一个进程访问临界区。

上面代码种turn的初值为$0$$0$，即刚开始只允许$0$$0$号进程进入临界区。若P1先上处理机运行，则会一直卡在⑤。直到P1的时间片用完，发生调度，切换P0上处理机运行。代码①不会卡住P0，P0可以正常访问临界区，在P0访问临界区期间即时切换回P1，P1依然会卡在⑤。只有P0在退出区将turn改为1后，P1才能进入临界区。

因此，该算法可以实现"同一时刻最多只允许一个进程访问临界区"。

可以看出这个算法只能按P0$\to$$\rightarrow$P1$\to$$\rightarrow$P0$\to$$\rightarrow$P1$\dots$$\dots$这样轮流访问。这种必须"轮流访问"带来的问题是，如果此时允许进入临界区的进程是P0，而P0一直不访问临界区，那么虽然此时临界区空闲，但是并不允许P1访问。因此，单标志法存在的主要问题是违背"空闲让进"的原则。

双标志先检查法

算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如flag[0]=ture意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。

在并发运行的环境下若按照$\mathrm{①}\mathrm{⑤}\mathrm{②}\mathrm{⑥}\mathrm{③}\cdots$$①⑤②⑥③\cdots$的顺序执行，P0和P1将会同时访问临界区。因此，双标志先检查法的主要问题是违反"忙则等待"原则。而发生这种情况原因在于，进入区的"检查①"和"上锁②"两个处理不是一气呵成的。"检查"后，"上锁"前可能发生进程切换。

双标志后检查法

算法思想：双标志先检查法的改版。前一个算法的问题是先"检查"后"上锁"，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先"上锁"后"检查"的方法，来避免上述问题。

在并发运行的环境下若按照$\mathrm{①}\mathrm{⑤}\mathrm{②}\mathrm{⑥}\mathrm{③}\cdots$$①⑤②⑥③\cdots$的顺序执行，P0和P1将会无法访问临界区。因此，双标志后检查法虽然解决了"忙则等待"的问题，但是又违背了"空闲让进"和"有限等待"原则，会因各进程都长期无法访问临界资源而产生"饥饿"现象。

Peterson算法

算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试谦让。做一个有礼貌的进程。

可以看到上面代码按照$\mathrm{①}\mathrm{⑥}\mathrm{②}\mathrm{⑦}\mathrm{⑧}\cdots$$①⑥②⑦⑧\cdots$的顺序执行不会违背任何原则。

Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则，因为没有进入临界区的进程会一直卡在while循环处，不能释放处理机资源。

5.2 进程互斥的硬件实现

之前的四种软件实现互斥的方法中，双标志先检查法只要配合硬件完成"检查"和"上锁"一气呵成就可以完美解决这个问题。

中断屏蔽法

利用"开$/$$/$关中断指令"实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况)。

这种方法优点：简单、高效、逻辑清晰。

缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程(因为开$/$$/$关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险)。

TestAndSet指令

简称TS指令，也有地方称为TestAndSetLock指令，或TSL指令。

TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑

​x
1
//布尔型共享变量lock 表示当前临界区是否被加锁
2
//true表示已加锁，false 表示未加锁
3
bool TestAndSet (bool *lock){
4
    bool old;
5
    old = *lock;    //old用来存放Zock原来的值
6
    *lock = true;   //无论之前是否已加锁，都将lock设为true
7
    return old;     //返回lock原来的值
8
}
9

10
//以下是使用TSL指令实现互斥的算法逻辑
11
int main(){
12
    while (TestAndSet (&lock)); //"上锁"并"检查"
13
    临界区代码段...
14
    lock = false;               //"解锁”
15
    剩余区代码段...   
16
}

指令实现的逻辑是当前进程在main函数中的循环会检查有没有上锁，如果上锁，即TestAndSet返回true，会一直循环，一直到某个使用临界区的进程在使用完后将lock修改为false，此时循环就会结束，进而执行当前进程的临界区代码。

相比软件实现方法，TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境。

缺点：不满足"让权等待"原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致"忙等"。

Swap指令

有的地方也叫Exchange指令，或简称XCHG指令。

Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑

xxxxxxxxxx
15
1
//Swap指令的作用是交换两个变的值
2
Swap (bool *a，bool *b) {
3
    bool temp;
4
    temp = *a;
5
    *a = *b;
6
    *b = temp;
7
}
8

9
//以下是用Swap指令实现互斥的算法逻辑
10
//lock表示当前临界区是否被加锁
11
bool old = true;
12
while (old == true) Swap (&lock, &old);
13
临界区代码段. ..
14
Lock = false;
15
剩余区代码段...

逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁(记录在old变量上)，再将上锁标记lock设置为true，最后检查old，如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境。

缺点：不满足"让权等待"原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致"忙等"。

5.3 互斥锁

锁是一种实现的互斥的方法。而解决临界区最简单的工具就是互斥锁(mutexlock)。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数acquire()获得锁，而函数release()释放锁。

每个互斥锁有一个布尔变量available，表示锁是否可用。如果锁是可用的，调用acqiure()会成功，且锁不再可用。当一个进程试图获取不可用的锁时，会被阻塞(进入while循环)，直到锁被释放。

xxxxxxxxxx
7
1
acquire ()
2
    while(!available);      //忙等待
3
    available = false;      //获得锁
4
}
5
release () {
6
    available = true;       //释放锁
7
}

acquire()或release()的执行必须是原子操作，因此互斥锁通常采用硬件机制来实现。

互斥锁的主要缺点是忙等待，当有一个进程在临界区中，任何其他进程在进入临界区时必须连续循环调用acquire()。当多个进程共享同一CPU时，就浪费了CPU周期。因此，互斥锁通常用于多处理器系统，一个线程可以在一个处理器上等待，不影响其他线程的执行。

需要连续循环忙等的互斥锁，都可称为自旋锁(spinlock) ，如TSL指令、 swap指令、单标志法

互斥锁特性：

1. 需忙等，等待过程，进程时间片用完依然会下处理机，违反"让权等待"。
2. 优点：等待期间不用切换进程上下文，多处理器系统中，若上锁的时间短，则自旋等待代价很低
3. 常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
4. 不太适用于单处理机系统，忙等的过程中不可能解锁

5.4 信号量机制

信号量机制会介绍两种：整型信号量和记录型信号量。

之前学习过进程互斥的四种软件实现方式(单标志法、双标志先检查、双标志后检查、Peterson算法)和进程互斥的三种硬件实现方式(中断屏蔽方法、TS/TSL指令、Swap/XCHG指令)。

单标志法、双标志先检查、双标志后检查存在问题较大，并且在双标志先检查法中，进入区的"检查"、"上锁"操作无法一气呵成，从而导致了两个进程有可能同时进入临界区的问题。而剩下的四种方法问题较小但都无法实现"让权等待"的问题。

为了解决上面两问题，在1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法：信号量机制。

信号量机制：用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。

信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为$1$$1$的信号量。

上面的一对原语：指wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的倍号量$S$$S$其实就是函数调用时传入的一个参数。wait(S)原语和signal(S)原语两个操作也可以简称为P(S)和V(S)操作。

由于信号量是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，所以信号量机制可以分为整型信号量和记录型信号量。

整型信号量

即用一个整数型的变量作为信号量，用来表示系统中某种资源的数量。

不同于普通的整型变量，对信号量的操作只有三种：即初始化、P操作、V操作。

假如某计算机系统中有一台打印机，有$n$$n$个进程需要用到打印机

由于只有一个打印机，所以整型信号量$S=1$$S=1$，代码如下：

xxxxxxxxxx
8
1
int S = 1;          //初始化整型信号量s，表示当前系统中可用的打印机资源数
2
void wait(int S){   //wait 原语，相当于“进入区”
3
    while (S <= 0); //如果资源数不够，就一直循环等待
4
    S=S-1;          //如果资源数够，则占用一个资源
5
}
6
void signal(int S){ //signal原语，相当于“退出区”
7
    S=S+1;          //使用完资源后，在退出区释放资源
8
}

当进程P0调用wait函数时，如果当前信号量S<=即打印机处于上锁状态就会一直进入循环，其他进程也一样。假设这里打印机处于空闲状态，P0进程会使用打印机资源。其他进程进入等待，当P0使用完资源后执行signal函数会把S信号量恢复，接下来的一个进程就可以跳出循环使用打印机。

由于使用原语所以上面的"检查"和"上锁"一气呵成，避免了并发、异步导致的问题。

但是这个方法还是会出现"忙等"现象，不满足"让权等待"原则。因为剩下进程会一wait函数的循环中。

记录型信号量

为了解决上面"让权等待"原则，提出记录型信号量。即用记录型数据结构表示信号量。

xxxxxxxxxx
5
1
/*记录型信号的定义*/
2
typedef struct {
3
    int value;          //剩余资源数
4
    struct process *L;  //等待队列
5
}semaphore;

对应的wait和signal函数原语如下：

xxxxxxxxxx
14
1
/*某进程需要使用资源时，通过wait原语申请*/
2
void wait (semaphore S) {
3
    S.value--;
4
    if(S.valut<0){
5
        block(S.L);
6
    }
7
}
8
/*进程使用完资源后，通过signal 原语释放*/
9
void signal ( semaphore S) {
10
    s.value++;
11
    if (S.value <= 0) {
12
        wakeup(S.L);
13
    }
14
}

wait函数中如果剩余资源数不够S.valut<0，使用block原语使进程从运行态进入阻塞态，并把当前进程挂到信号量S的等待队列(即阻塞队列)*L中。

signal函数中释放资源后s.value++，若还有别的进程在等待(阻塞队列中有进程)这种资源S.value<=0，则使用wakeup原语唤醒等待队列中的一个进程，该进程从阻塞态转换为就绪态。

例子：某计算机系统中有$2$$2$台打印机，则可在初始化信号量S时将S.value的值设为$2$$2$，队列S.L设置为空。假设当前有四个进程：

如果当前先执行的是P0进程，wait函数的S.value减为$1$$1$，所以会把其中一个打印机分配给P0。之后切换到P1进程同样会分配一个打印机，此时S.value=0，没有处于空闲的打印机了。接着CPU再为P2进程服务，P2同样要使用打印机，所以调用wait函数后value值同样会减一变为-1，此时block(S.L);函数会将P2进程挂到阻塞队列*L中。S.value=-1表明当前有一个进程在等待队列。接着CPU为P3进程服务，和P2一样，S.value=-2，将P3放入阻塞队列*L当中。

接着再为P0服务，当前P0正好使用完打印机执行signal原语，此时S.value++=-1，小于$0$$0$，则signal原语会主动执行wakeup原语，唤醒等待队列中的一个进程，这里是队头进程P2，此时P2会从阻塞队列转换为就绪队列，之后打印机会分配给P2进程。同样P3一样。

总结：在考研题目中wait(S)、signal(S)也可以记为P(S)、V(S)，这对原语可用于实现系统资源的"申请"和"释放"。

S.value的初值表示系统中某种资源的数目。对信号量S的一次P操作意味着进程请求一个单位的该类资源，因此需要执行S.value--，表示资源数减$1$$1$，当S.value<0时表示该类资源已分配完毕，因此进程应调用block原语进行自我阻塞(当前运行的进程从运行态转换为阻塞态)，主动放弃处理机，并插入该类资源的等待队列S.L中。可见，该机制遵循了"让权等待"原则，不会出现"忙等"现象。

对信号量S的一次V操作意味着进程释放一个单位的该类资源，因此需要执行S.value++，表示资源数加$1$$1$，若加$1$$1$后仍是S.value<=0，表示依然有进程在等待该类资源，因此应调用wakeup原语唤醒等待队列中的第一个进程(被唤醒进程从阻塞态转换为就绪态)。

5.5 信号量机制实现进程同步和互斥

信号量的值$=$$=$这种资源的剩余数量(信号量的值如果小于$0$$0$，说明此时有进程在等待这种资源)

P(S)：即申请一个资源S，如果资源不够就阻塞等待。

V(S)：释放一个资源S，如果有进程在等待该资源，则唤醒一个进程。

可以使用信号量机制实现进程的同步和互斥。

信号量机制实现进程互斥

系统当中的某一些资源必须进程互斥，而访问互斥资源的代码叫做临界区。这样就表明头一时刻只能有一个进程进入临界区代码。

所以首先要做的是分析并发进程的关键活动，划定临界区(如：对临界资源打印机的访问就应放在临界区)。另外还要设置互斥信号量mutex， 初值为$1$$1$。mutex表示可以进入临界区的进程名额。

信号机制实现互斥代码如下：

xxxxxxxxxx
21
1
/*记录型信号的定义*/
2
typedef struct {
3
    int value;          //剩余资源数
4
    struct process *L;  //等待队列
5
}semaphore;
6

7
/*信号量机制实现互斥*/
8
semaphore mutex=1;//初始化信号量
9
P1(){
10
    ...
11
    P(mutex);//使用临界资源前需要加锁
12
    临界区代码段...
13
    V(mutex);//使用临界资源后需要解锁
14
}
15
P2(){
16
    ...
17
    P(mutex) ;
18
    临界区代码段...
19
    V(mutex);
20
    ...
21
}

这里的semaphore mutex=1;实际上不能这么赋值，但要会自己定义记录型(semaphore)信号量，但如果题目中没特别说明，可以把信号量的声明简写成这种形式semaphore mutex=1。

如果多个进程访问的临界资源不同，则要给不同临界区设置不同的信号量。

另外需要注意的是P、V操作必须成对出现。缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不被释放，等待进程永不被唤醒。

信号量机制实现进程同步

进程同步值得是要让各并发进程按要求有序地推进。

比如，P1、P2 并发执行，由于存在异步性，因此二者交替推进的次序是不确定的。

若P2的"代码4"要基于P1的"代码1"和"代码2"的运行结果才能执行，那么我们就必须保证"代码4"一定是在"代码2"之后才会执行。这就是进程同步问题，让本来异步并发的进程互相配合，有序推进。

用信号量实现进程同步：

1. 分析什么地方需要实现"同步关系"，即必须保证"一前一后"执行的两个操作(或两句代码)
2. 设置同步信号量S，初始为$0$$0$

假如有以下两个进程：先初始化同步信号量，初始值为$0$$0$，semaphore S=0;

若先执行到V(S)操作，则S++后$S=1$$S=1$。之后当执行到P(S)操作时，由于S=1，表示有可用资源，会执行S--， S的值变回0，P2进程不会执行block原语，而是继续往下执行代码4。

若先执行到P(S)操作，由于S=0，S--后S=-1，表示此时没有可用资源，因此P操作中会执行block原语，主动请求阻塞。之后当执行完代码2，继而执行V(S)操作，S++，使S变回0，由于此时有进程在该信号量对应的阻塞队列中，因此会在V操作中执行wakeup原语，唤醒P2进程。这样P2就可以继续执行代码4了。

这里保证了代码4一定是在代码2之后执行。

更简单的理解此时的信号量S代表"某种资源"，刚开始是没有这种资源的。P2需要使用这种资源，而又只能由P1产生这种资源。

例题：进程P1中有句代码S1，P2 中有句代码S2，P3中有句代码S3$\cdots$$\cdots$P6中有句代码S6。这些代码要求按如下前驱图所示的顺序来执行：

步骤：

• 要为每一对前驱关系各设置一个同步信号量。

  这里用$a,b,c\dots$$a,b,c\dots$表示：

  

• 在"前操作"之后对相应的同步信号量执行V操作

• 在"后操作"之前对相应的同步信号量执行P操作

以上两个操作统称为"前V后P"，即S2执行需要S1执行完毕，则在S1执行最后设置V操作，在S2执行代码的开头执行P操作。结果如下：

假如CPU先执行P5，执行P(d)后P5进程进入阻塞队列。接着假如执行P2，执行P(a)后P2进程进入阻塞队列。CPU接着执行P1，当P1中的S1执行完毕后执行V(a)，此时会唤醒P2进程，当P2执行V(d)后又会唤醒P5进程。其他进程执行过程分析原理类似。

信号量机制实现同步互斥总结：

最后的进程前驱关系实际上就是上面的例题。这里除了互斥、同步问题外，还会考察有多个资源的问题：有多少资源就把信号量初值设为多少。申请资源时进行P操作，释放资源时进行V操作即可。

5.6 经典进程同步互斥问题

会上面介绍的信号量机制处理一些经典的进程同步互斥问题。

生产者消费者问题

问题描述：系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。(注: 这里的产品理解为某种数据)。生产者、消费者共享一个初始为空、大小为$n$$n$的缓冲区。只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待(缓冲区没满$\to$$\rightarrow$生产者生产)。

当缓冲区满时，生产者必须等待。只有缓冲区不空时，消费者才能从中取出产品，否则必须等待(缓冲区没空$\to$$\rightarrow$消费者消费)。

缓冲区是临界资源，各进程必须互斥地访问(互斥关系)。因为假如有两个生产者进程，都同时往缓冲区的同一块内存写数据，则会出现覆盖。

PV操作题目分析步骤：

1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。

   根据题目，只有当缓冲区有产品，消费者进程才可以消费。另外只有缓冲区没满，生产者进程才可以生产，所以这样一前一后的关系就需要设置一个同步信号量，并且在前面动作完成之后需要执行V操作，后面动过开始之前执行P操作。

   

3. 设置信号量。并根据题目条件确定信号量初值。(互斥信 号量初值一般为$1$$1$，同步信号量的初始值要看对应资源的初始值是多少)

   消费者进程在消费之前需要消耗的是产品，所以P操作是在申请一个产品(数据)。所以full信号量对应的是非空缓冲区的数据。且由题中信息可知，缓冲区初始化时是空的。而这种进程只有生产者生产了商品之后才能接着往下执行。

   对于同步信号量empty，生产者进程每生产一个进程，就需要消耗一个空闲的缓冲区，因此这个信号量对应的是就是缓冲区的数量。当一个消费者进程取走了产品，就可以释放一个空闲缓冲区(empty)。且由题可知空闲缓冲区的初始值是$n$$n$。

   各个信号量初始状态如下：

   xxxxxxxxxx
   3
   1
   semaphore mutex = 1;    //互斥信号量，实现对缓冲区的互斥访问
   2
   semaphore empty = n;    //同步信号量，表示空闲缓冲区的数量
   3
   semaphore full=0;       //同步信号量，表示产品的数量，也即非空缓冲区的数量
   

通过上面分析可以知道生产者进程在把产品放入缓冲区之前，需要申请一个空闲的缓冲区，因此在放入之前需要对empty这个信号量进行P操作，之后再对缓冲区资源量+1。

xxxxxxxxxx
8
1
producer(){
2
    while(1){
3
        生产一个产品;
4
        P(empty);   //消耗一个空闲缓冲区
5
        把产品放入缓冲区;
6
        V(full);    //增加一个产品
7
    }
8
}

消费者进程分析也类似，当消费者从缓冲区取走一个产品之前，需要对full进程P操作。也就是要申请消耗一个产品资源。而当取走一个产品之后，空闲缓冲区的数量会$+1$$+1$。即进行一个V操作增加一个缓冲区。

xxxxxxxxxx
8
1
consumer() {
2
    while (1) {
3
        P(full);    //消耗一个产品(非空缓冲区)
4
        从缓冲区取出一个产品;
5
        V(empty);   //增加一个空闲缓冲区
6
        使用产品;
7
    }
8
}

由于缓冲区是邻接资源，所以还需要对产品的取出和放入进行P和V操作。

xxxxxxxxxx
21
1
producer(){
2
    while(1){
3
        生产一个产品;
4
        P(empty);   //消耗一个空闲缓冲区
5
        P(mutex);
6
        把产品放入缓冲区;
7
        V(mutex);
8
        V(full);    //增加一个产品
9
    }
10
}
11

12
consumer() {
13
    while (1) {
14
        P(full);    //消耗一个产品(非空缓冲区)
15
        P(mutex);
16
        从缓冲区取出一个产品;
17
        V(mutex);
18
        V(empty);   //增加一个空闲缓冲区
19
        使用产品;
20
    }
21
}

上面代码不能改变相邻P、V的操作顺序，假如改变：

若此时缓冲区内已经放满产品，则empty=0，full=n。

则生产者进程执行$\mathrm{①}$$①$使mutex变为$0$$0$，再执行$\mathrm{②}$$②$，由于已没有空闲缓冲区，因此生产者被阻塞。由于生产者阻塞，因此切换回消费者进程。消费者进程执行$\mathrm{③}$$③$，由于mutex为$0$$0$，即生产者还没释放对临界资源的"锁"，因此消费者也被阻塞。这就造成了生产者等待消费者释放空闲缓冲区，而消费者又等待生产者释放临界区的情况，生产者和消费者循环等待被对方唤醒，出现"死锁"。

同样的，若缓冲区中没有产品，即full=0，empty=n。 按$\mathrm{③}\mathrm{④}\mathrm{①}$$③④①$的顺序执行就会发生死锁。因此，实现互斥的P操作一定要在实现同步的P操作之后。

而V操作不会导致进程阻塞，因此两个V操作顺序可以交换。并且还要保证临界区代码足够短。所以上面的生产一个产品和使用产品不能放在临界区中。

多生产者多消费者问题

桌子上有一只盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等着吃盘子中的橘子，女儿专等着吃盘子中的苹果。只有盘子空时，爸爸或妈妈才可向盘子中放一个水果。仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出水果。用PV操作实现上述过程。

上节的问题生产者和消费者都是同一种东西，而这里的问题是生产者们和消费者们生产和消费的东西是不一样。

分析步骤：

1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

   互斥关系：对于缓冲区(盘子)的访问要互斥的进行。

   同步关系：父亲将苹果放入盘子后，女儿才能取苹果。母亲将橘子放入盘子后，儿子才能取橘子。并且只有盘子为空时，父亲或母亲才能放入水果。而"盘子为空"这个事件可以由儿子或女儿触发，事件发生后才允许父亲或母亲放水果。

2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。

   

3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为$1$$1$，同步信号量的初始值要看对应资源的初始值是多少)

   父亲进程需要把苹果放入盘子，女儿才能取到苹果，所以需要一个同步信号量apple=0用来实现这个同步关系。并且刚开始盘子中没有苹果所以初始值为$0$$0$。

   同样的对于母亲进程，也需要设置一个同步信号量orange=0。

   另外当盘子为空的时候父亲和母亲进程才能往盘子中放水果。然而刚开始盘子本来都是空的，所以两个进程在刚开始就可以将水果放入盘子。所以需要一个plate=1的同步信号量用来表示此时盘子是否为空。代码声明如下：

   xxxxxxxxxx
   4
   1
   semaphore mutex =1; //实现互斥访问盘子(缓冲区)
   2
   semaphore apple =0; //盘子中有几个苹果
   3
   semaphore orange =0;//盘子中有几个橘子
   4
   semaphore plate =1; //盘子中还可以放多少个水果
   

父亲和母亲进程在准备好水果后，需要检查盘子中是否为空进行P(plate)操作。如果水果已经放入进程，那么需要对水果进行V操作告诉女儿和儿子此时盘子中已经有了水果。同时两个进程在实现访问盘子时需要进行互斥操作。

xxxxxxxxxx
21
1
dad () {
2
    while (1) {
3
        准备一个苹果;
4
        P(plate);
5
        P(mutex);
6
        把苹果放入盘子;
7
        V(mutex);
8
        V(apple);
9
    }
10
}
11

12
mom() {
13
    while(1){
14
        准备一个橘子;
15
        P(plate);
16
        P(mutex);
17
        把橘子放入盘子;
18
        V(mutex);
19
        V(orange);
20
    }
21
}

女儿进程和儿子进程，在取出自己喜欢的水果之前分别需要检查此时盘子中是否已经有自己喜欢的水果，所以先进行P操作。之后要进行V操作告诉父进程和母进程已经盘子已经为空。同时两个进程在实现访问盘子时需要进行互斥操作。

xxxxxxxxxx
21
1
daughter(){
2
    while(1){
3
        P(apple);
4
        P(mutex);
5
        从盘中取出苹果;
6
        V(mutex);
7
        V(plate);
8
        吃掉苹果;
9
    }
10
}
11

12
son() {
13
    while(1){
14
        P(orange);
15
        P(mutex);
16
        从盘中取出橘子;
17
        V(mutex);
18
        V(plate);
19
        吃掉橘子;
20
    }
21
}

假如这里不用互斥信号：

分析：刚开始，儿子、女儿进程即使上处理机运行也会被阻塞。如果刚开始是父亲进程先上处理机运行，则父亲P(plate)，可以访问盘子，母亲P(plate)，阻塞等待盘子。而父亲放入苹果V(apple)，女儿进程被唤醒，其他进程即使运行也都会阻塞，暂时不可能访问临界资源(盘子)，之后女儿P(apple)，访问盘子V(plate)。等待盘子的母亲进程被唤醒，母亲进程访问盘子(其他进程暂时都无法进入临界区)之后会重复唤醒儿子进程。

所以可以得出一个结论：即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象。原因在于本题中的缓冲区大小为$1$$1$，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是$1$$1$。因此在任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。而当缓冲区的大小为$2$$2$时，没有互斥信号就会产生数据覆盖现象。所以如果缓冲区大小大于$1$$1$，就必须专门设置一个互斥信号量mutex来保证互斥访问缓冲区。

建议：在考试中如果来不及仔细分析，可以加，上互斥信号量，保证各进程一定会互斥地访问缓冲区。但需要注意的是，实现互斥的P操作一定要在实现同步的P操作之后，否则可能引起"死锁"。

在分析同步问题(一前一后问题)的时候不能从单个进程行为的角度来分析，要把"一前一后"发生的事看做是两种"事件"的前后关系。

如：盘子变空事件导致放入水果事件。"盘子变空事件"既可由儿子引发，也可由女儿引发。"放水果事件"既可能是父亲执行，也可能是母亲执行。这样的话，就可以用一个同步信号量解决问题了。

吸烟者问题

假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草、第二个拥有纸、第三个拥有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它， 并给供应者进程一个信号告诉完成了，供应者就会放另外两种材料再桌上，这个过程一直重复 (让三个抽烟者轮流地抽烟)。

本质上这题也属于"生产者和消费者"问题，更详细的说应该是"可生产多种产品的单生产者和多消费者"。

1. 关系分析。找出题目中描述的各个进程，分析它们之间的同步、互斥关系。

   互斥关系：

   这里供应者提供的材料会有三种组合：$\mathrm{①}$$①$纸$+$$+$胶水。$\mathrm{②}$$②$烟草$+$$+$胶水。$\mathrm{③}$$③$烟草$+$$+$纸

   每次供应者会将一种组合放到桌子上。所以桌子可以抽象为容量为$1$$1$的缓冲区，要互斥访问

   同步关系：

   桌上有组合导致第一个抽烟者取走东西 桌上有组合导致第二个抽烟者取走东西 桌上有组合导致第三个抽烟者取走东西

   对于这三种以前一后关系需要设置三个同步信号量。另外题目还指出"拥有剩下那种材料的抽烟者卷一根烟并抽掉它， 并给供应者进程一个信号告诉完成了"。所以发出完成信号会导致供应者将下一个组合放到桌上。

2. 整理思路。根据各进程的操作流程确定P、V操作的大致顺序。

3. 设置信号量。设置需要的信号量，并根据题目条件确定信号量初值。(互斥信号量初值一般为$1$$1$，同步信号量的初始值要看对应资源的初始值是多少)

   桌子上有组合一，是第一个抽烟者取走东西之前发生，所以设置同步信号量offer1=0。第二个和第三个关系一样。

   

   发出完成信号这个时间要发生在，供应者将组合放到桌子上之前，而发出完成信号这个事件可以由三个吸烟者当中任何一个产生。所以设置同步信号量finish=0

   

   代码定义如下：

   xxxxxxxxxx
   3
   1
   semaphore offer1 = 0;   //桌上组合一的数量
   2
   semaphore offer2 = 0;   //桌上组合二的数量
   3
   semaphore offer3=0;     //桌上组合三的数量 
   

   不用设置互斥信号量是因为容器的容量为$1$$1$。

首先供应者需要提供三种组合，并且没提供一种组合要执行V操作，通知吸烟者。最后还要进行P操作等待吸烟者拿走材料。

xxxxxxxxxx
16
1
provider () {
2
    while (1) {
3
        if (i==0) {
4
            将组合一放桌上;
5
            V(offer1);
6
        } else if(i==1) {
7
            将组合二放桌上;
8
            V(offer2);
9
        } else if(i==2) {
10
            将组合三放桌上;
11
            V(offer3);
12
        }
13
        i=(i+1)%3;
14
        P(finish);
15
    }
16
}

各个吸烟者从桌子上拿走材料之前，需要检查是不是自己所需要的材料。当拿走材料之后还需要通知供应者可以放下一个材料。

xxxxxxxxxx
23
1
smoker1() {
2
    while(1){
3
        P(offer1);
4
        从桌上拿走组合一;卷烟;抽掉;
5
        V(finish);
6
    }
7
}
8

9
smoker2() {
10
    while(1){
11
        P(offer2);
12
        从桌上拿走组合二;卷烟;抽掉;
13
        V(finish);
14
    }
15
}
16

17
smoker3() {
18
    while(1){
19
        P(offer3);
20
        从桌上拿走组合三;卷烟;抽掉;
21
        V(finish);
22
    }
23
}