第二章 进程的描述与控制
前趋图和程序执行
程序的顺序执行
单道程序设计 -> 程序的顺序执行
在程序顺序执行时，具有这样三个特征：
- 顺序性：处理机严格按照程序所规定的顺序执行，即每一操作必须在下一操作开始之前结束；
- 封闭性：程序在封闭的环境下运行，独占全机资源，资源的状态（除初始状态外）只有本程序才能改变，程序一旦开始执行其结果就不受外界影响；
- 可再现性：只要程序执行时的环境和初始条件相同，程序重复执行时就可以获得相同的结果。
程序的并发执行
多道程序设计 -> 程序的并发执行
程序并发执行时虽然提高了系统的吞吐量和资源利用率，但由于它们共享系统资源，以及它们为完成一项任务而相互合作，致使这些并发执行的程序之间形成互相制约的关系，给程序的并发执行带来新特征：
- 间断性：程序在并发执行时由于共享系统资源以及为完成同一项任务而相互合作，致使这些程序之间形成了相互制约的关系，相互制约导致并发程序具有“执行——暂停——执行”这种间断性的活动规律；
- 失去封闭性：当系统中存在多个并发执行的程序时，系统中的各种资源将为它们所共享，这些资源的状态也由这些程序来改变，致使其中任一程序在运行时其环境都会受到其它程序的影响；
- 不可再现性：程序在并发执行时由于失去了封闭性，其计算结果必将与并发程序的执行速度有关，也将导致其又失去可再现性。
进程的描述
进程的定义和特征
进程的定义
PCB：为了使参与并发执行的每个程序（含数据）都能独立运行，在操作系统中必须为之配置一个专门的数据结构，称为进程控制块（Process Control Block，PCB）。系统利用PCB来描述进程的基本情况和活动过程，进而管理和控制进程。
注意：PCB是进程存在的唯一定义。
进程实体：又称进程映像，由程序段、相关数据段和PCB三部分构成，一般情况下把进程实体简称为进程。
进程的定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
注意：严格来说进程实体和进程不同：进程实体是静态的，进程是动态的。如果不专门考察两者的区别就可以认为“进程实体就是进程”，也可以说：进程由程序段、数据段、PCB三部分组成。
进程的特征
- 结构性：每个进程都会配置一个PCB，进程具有程序所没有的PCB结构，进程由程序段、数据段、PCB三部分组成；
- 动态性：进程的实质是进程实体的执行过程，动态性是进程最基本的特征；
- 并发性：多个进程实体同时存在于内存中，且能在一段时间内同时运行；
- 独立性：进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位；
- 异步性：进程是按异步方式运行的，即按各自独立的、不可预知的速度向前推进。
进程的基本状态及其转换
进程的三种基本状态
- 就绪：进程已分配到除CPU以外的所有必要资源，只要再获得CPU便可立即执行；
- 执行：进程已经获得CPU，其程序正在执行；
- 阻塞：正在执行的进程由于发生某事件（如I/O请求、申请缓冲区失败等）暂时无法继续执行。
创建状态和终止状态
- 创建状态：进程正在被创建，操作系统为进程分配资源、初始化PCB；
- 终止状态：进程正在被撤销，操作系统会回收进程拥有的资源，撤销PCB。
基本状态的转换
挂起操作和进程状态的转换
挂起操作的引入
- 终端用户的需要：便于用户研究自己的程序的执行情况或对程序进行修改；
- 父进程请求：父进程希望暂停子进程，以便考察和修改该子进程或协调各子进程之间的活动；
- 负荷调节的需要：当实时系统中的工作负荷较重时可以把一些不重要的进程挂起，以保证系统的正常运行；
- 操作系统的需要：便于操作系统检查运行中的资源使用情况或进行记账。
引入挂起操作后进程状态的转换
- 创建->活动就绪：在当前系统的性能和内存容量均允许的状态下创建进程；
- 创建->静止就绪：不分配给新进程所需资源（主要是内存），进程被安置在外存不参与调度，进程的创建工作尚未完成；
- 活动就绪->静止就绪：进程处于未被挂起的就绪状态时被挂起，不参与调度；
- 静止就绪->活动就绪：静止就绪状态的进程被激活，参与调度；
- 活动阻塞->静止阻塞：进程处于未被挂起的阻塞状态时被挂起；
- 静止阻塞->静止就绪：静止阻塞的进程所期待的事件出现；
- 静止阻塞->活动阻塞：静止阻塞状态的进程被激活。
进程管理中的数据结构
操作系统中用于管理控制的数据结构
在计算机系统中，对于每个资源和每个进程都设置了一个数据结构，用于表征其实体，称为资源信息表或进程信息表。OS管理的这些数据结构一般分为内存表、设备表、文件表和用于进程管理的进程表，通常进程表又被称为进程控制块PCB。
PCB的作用
PCB的作用是使一个在多道程序环境下不能独立运行的程序（含数据）称为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。
- 作为独立运行的基本标志
- 能实现间断性运行方式
- 提供进程管理所需要的信息
- 提供进程调度所需要的信息
- 实现与其他进程的同步通信
PCB中的信息
- 进程描述信息：包括进程标识符（用于标志各个进程）和用户标识符（用于标志进程归属的用户，主要为共享和保护服务）；
- 进程控制和管理信息：包括进程的状态、进程优先级等；
- 资源分配清单：用于说明有关内存地址空间或虚拟空间的状况，所打开的文件列表和所使用的输入/输出设备信息；
- 处理机相关信息：主要是处理机中各种寄存器的值。
PCB的组织方式
- 线性方式：将所有的PCB都组织在一张线性表中，操作系统持有该线性表的首地址；
- 链接方式：按照进程状态将PCB分为多个队列，操作系统持有指向各队列的指针；
- 索引方式：按照进程状态的不同建立几张索引表，操作系统持有指向各个索引表的指针。
进程控制
进程控制一般是由操作系统的内核中的原语实现的。
操作系统内核
现代操作系统一般将OS划分为若干个层次，再将OS的不同功能分别设置在不同层次中。通常将一些与硬件紧密相关的模块（如中断处理程序等）、各种设备的驱动程序以及运行频率较高的模块（如时钟管理、进程调度和许多模块所公用的一些基本操作）都安排在紧靠硬件的软件层次中，将它们常驻内存，这些模块被称为内核。
通常将处理机的状态分为系统态和用户态两种：
- 系统态：又称为管态/内核态/核心态，具有较高的特权，能执行一切指令，访问所有的寄存器和存储区；
- 用户态：又称为目态，具有较低的特权，仅能执行规定的指令，访问规定的寄存器和存储区。
一般情况下，应用程序运行在用户态，操作系统内核程序运行在系统态。
不同类型和规模的OS的内核所包含的功能间存在一定的差异，但大多数OS内核都包含支撑功能和资源管理功能两大方面的功能。
支撑功能
- 中断处理：中断处理是内核最基本的功能，各种类型的系统调用、键盘命令的输入、进程调度、设备驱动等都依赖于中断。为减少处理机中断的时间，提高程序执行的并发性，内核在对中断进行“有限处理”后便转入相关进程，由这些进程完成后续处理工作；
- 时钟管理：时钟管理是内核的一项基本功能，时间片轮转调度、实时系统中的截止时间控制、批处理系统中的最长运行时间控制等都依赖于时钟管理功能；
- 原语操作：原语是由若干条指令组成的，用于完成一定功能的一个过程，是一个原子操作（不可分割的基本单位）。原语在系统态执行，常驻内存，在执行过程中不允许被中断。链表操作、进程同步、设备驱动、CPU切换等功能都可以被定义为原语。
资源管理功能
- 进程管理：进程状态管理、进程调度与分派、创建与撤销PCB等；
- 存储器管理：存储器空间的分配和回收、内存信息保护、代码对换程序等；
- 设备管理：缓冲区管理、设备的分配和回收等。
进程控制
父进程与子进程
在OS中，允许一个进程创建另一个进程，通常把创建者称为父进程，被创建者成为子进程。子进程可以继承父进程所拥有的资源（如父进程打开的文件、分配到的缓冲区等），当子进程被撤销时，应将其从父进程那里获得的资源归还给父进程。在撤销父进程时，必须同时撤销其所有的子进程。
进程的创建
引起进程创建的典型事件主要有：
- 用户登录：在分时系统中，用户登录成功后操作系统将为该用户创建一个进程并插入就绪队列中；
- 作业调度：在多道批处理系统中，当作业调度程序按一定的算法调度到某些作业时，便将它们装入内存，为它们创建进程，并将其插入就绪队列；
- 提供服务：当运行中的用户程序提某种请求后（如要求进行文件打印等），操作系统将专门创建一个进程提供用户所需要的服务；
- 应用请求：用户进程自己创建新进程，以便使新进程以同创建者进程并发运行的方式完成特定任务。
进程的创建过程（创建原语）如下：
- 申请空白PCB，为新进程创建一个唯一的进程标识号，并从PCB集合中索取一个空白PCB；
- 为新进程分配所需资源，为新进程的程序和数据及用户栈分配必要的内存空间（在PCB中体现）。注意：若资源不足，则并不是创建失败而是处于阻塞状态，等待所需资源；
- 初始化PCB，PCB的初始化过程主要包括：初始化标识信息、初始化处理机状态信息、初始化处理机控制信息、设置进程的优先级等；
- 如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。
进程的终止
引起进程终止的事件主要有：
- 正常结束：进程的任务已经完成并准备退出运行；
- 异常结束：程序在运行时发生了某种异常，使程序无法继续运行，如存储区越界、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错、I/O故障等；
- 外界干预：进程应外界的请求而终止运行，如操作员或操作系统干预、父进程请求、父进程终止等。
进程的终止过程（撤销原语）如下：
- 根据被终止的进程标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态；
- 若被终止的进程正处于执行状态则立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后重新进行进程调度；
- 若该进程还有子孙进程则将其所有子孙进程全部终止，以防它们成为不可控的进程；
- 将被终止的进程所拥有的全部资源归还给其父进程或者归还给系统；
- 将被终止的进程的PCB从所在队列或链表中移出，等待其他程序来搜集信息。
进程的阻塞与唤醒
引起进程阻塞的原因：
- 申请共享资源失败：进程向系统申请资源时，由于系统没有足够的资源分配给它而转变为阻塞状态；
- 等待某种操作的完成：当进程启动了某种操作后，若该进程必须在操作完成之后才能继续执行，则该进程变为阻塞状态等待操作完成；
- 新数据尚未到达：对于相互合作的进程，如果一个进程需要先获得另一进程提供的数据才能继续执行，如果所需数据尚未到达，进程就处于阻塞状态；
- 等待新任务的到达：在某些系统中（特别是网络环境下的OS），往往设置一些特定的系统进程，每当它们完成任务后就变为阻塞状态等待新任务的到来。
正在执行的进程如果发生了上述事件，进程便通过调用阻塞原语block将自己阻塞，由此可见阻塞是进程的一种主动行为。
进程的阻塞过程（阻塞原语block）如下：
- 找到将要被阻塞的进程的标识号所对应的PCB；
- 若该进程处于运行态，则保留其处理机状态，将其运行状态改为阻塞态并停止运行；
- 把该PCB插入相应事件的阻塞队列，将处理机资源调度给其他就绪进程并进行切换；
当被阻塞进程所期待的事件出现时，则由有关进程调用唤醒原语wakeup将等待该事件的进程唤醒。
进程的唤醒过程（唤醒原语wakeup）如下：
- 在该事件的阻塞队列中找到相应进程的PCB；
- 把该PCB从阻塞队列中移出，将其状态设置为就绪态；
- 把该PCB插入就绪队列中。
注意：block原语和wakeup原语是一对作用刚好相反的原语，必须成对使用；block原语是由被阻塞进程自我调用实现的，而wakeup原语则是由一个与被唤醒进程合作或其他相关进程的调用实现的。
进程的挂起与激活
进程的挂起过程（挂起原语suspend）如下：
- 检查被挂起进程的状态，若处于活动状态则置为静止就绪态，若处于阻塞态则置为静止阻塞态；
- 把该进程的PCB复制到某指定的内存区域，方便用户或父进程考查该进程的运行情况；
- 若被挂起的进程正在执行则重新进行进程调度。
进程的激活过程（激活原语active）如下：
- 将被激活的进程从外存调入内存，检查该进程的状态，若为静止就绪态则改为活动就绪态，若为静止阻塞态则改为活动阻塞态；
- 若采用抢占调度策略，则根据被激活的进程的优先级检查是否要重新进行进程调度；
- 若优先级低则不重新调度，否则将处理机分配给被激活的进程。
进程切换
进程切换指的是处理机从一个进程的运行转到另一个进程上运行，在这个过程中，进程的运行环境产生了实质性的变化。
进程切换的过程如下：
- 保存处理机上下文，包括程序计数器PC和其他寄存器；
- 更新PCB信息；
- 把进程的PCB移入相应的队列，如就绪队列和某事件的阻塞队列；
- 选择另一个进程执行，并更新其PCB；
- 更新内存管理的数据结构；
- 恢复处理机的上下文。
注意1：进程切换与处理机模式切换（用户态->内核态）不同，模式切换时处理机逻辑上可能还在统一进程中运行。若进程因中断或异常而进入核心态运行，执行完后又回到用户态刚刚被中断的程序运行，则OS只需要恢复进程进入内核时所保存的CPU现场，而无需改变当前进程的环境信息；若要切换进程，当前正在运行的进程发生了改变，则当前进程的环境信息也需要改变。
注意2：进程调度是决定处理机资源分配给哪个进程的行为，是一种决策行为；进程切换是指世纪分配处理机的行为，是一种执行行为。一般来说，先有资源的调度后有进程切换。
进程同步
进程同步的基本概念
进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能按照一定的规则（或时序）共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性。
两种形式的制约关系
- 直接相互制约关系：又称同步，是指为了完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。进程间的直接制约关系来源于它们的相互合作；
- 间接相互制约关系：又称互斥，当一个进程进入临界区访问资源时，另一个进程必须等待；当占用临界资源的进程退出临界区后，另一进程才允许访问此临界资源。
在多道程序环境下，由于存在上述两种相互制约的关系，进程在运行的过程中是否能获得处理机运行与以怎样的速度运行并不能由进程自身所控制，此即进程的异步性。由此会产生对共享变量或数据结构的不正确访问次序，从而造成进程每次执行的结果不一致。这种差错往往与时间有关，故称“与时间有关的错误”。为了杜绝这种差错，必须对进程的执行次序进行协调，保证进程能按顺序执行。
临界资源
虽然多个进程可以共享系统中的各种资源，但是许多硬件资源如打印机、磁带机等都属于临界资源；此外，还有许多变量、数据等都可以被若干进程共享，它们也属于临界资源。诸进程之间应采取互斥方式实现对这种资源的共享。
临界区
不论是硬件临界资源还是软件临界资源，多个进程必须互斥地对它们进行访问，每个进程中访问临界资源的那段代码称为临界区。
为了保证临界资源的正确使用，可以把临界资源的访问分为四个部分：
- 进入区：为了进入临界区使用临界资源，在进入区要检查可否进入临界区，若能进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区；
- 临界区：进程中访问临界资源的代码，又称临界段；
- 退出区：将正在访问临界区的标志清除；
- 剩余区：代码中的其余部分。
伪代码：
do {
entry section; // 进入区
critical section; // 临界区
exit section; // 退出区
remainder section; // 剩余区
} while (true)
同步机制应遵循的规则
所有同步机制都应遵循以下四种原则：
- 空闲让进：当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源；
- 忙则等待：当有进程已进入临界区时，表明临界资源正在被访问，其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问；
- 有限等待：对要求访问临界区的进程，应保证在有限时间内能进入自己的临界区，以避免陷入“死等”状态；
- 让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以避免进程陷入“忙等”状态。
软件实现方法
单标志法
基本思想：设置一个公用整型变量turn，用于指示被允许进入临界区的进程编号。
伪代码：
进程P0：
while (turn != 0); // 进入区
critical section; // 临界区
turn = 1; // 退出区
remainder section; // 剩余区
进程P1：
while (turn != 1); // 进入区
critical section; // 临界区
turn = 0; // 退出区
remainder section; // 剩余区
- 优点：可以保证每次只有一个进程进入临界区；
- 缺点：两个进程必须交替进入临界区；若某个进程不再进入临界区，则另一个进程也将无法进入临界区（违背“空闲让进”），容易造成资源利用不充分。
例如，若P0进入临界区并顺利离开，而P1不进入临界区，turn = 1就会一直成立，P0就无法再次进入临界区。
双标志法先检查
基本思想：在进程进入临界区之前先检查临界资源是否正在被访问，如果是，则该进程需等待；否则，该进程就可以进入自己的临界区。设置一个数据flag[i]，第i个元素为FALSE表示Pi进程没有进入临界区，否则表示Pi进程进入临界区。
伪代码：
进程Pi：
while (flag[j]); // (1)进入区，此时flag[i] = FALSE
flag[i] = TRUE; // (3)进入区
critical section; // 临界区
flag[i] = FALSE; // 退出区
remainder section; // 剩余区
进程Pj：
while (flag[i]); // (2)进入区，此时flag[j] = FALSE
flag[j] = TRUE; // (4)进入区
critical section; // 临界区
flag[j] = FALSE; // 退出区
remainder section; // 剩余区
- 优点：进程不需要交替进入临界区，可连续使用；
- 缺点：Pi和Pj可能同时进入临界区，若按(1)->(2)->(3)->(4)执行时二者就会同时进入临界区（违背“忙则等待”）。
双标志法后检查
基本思想：在“双标志法先检查”的基础上，进程先将自己的标志设置为TRUE，再检测对方的状态标志，若对方的标志为TRUE则等待，否则进入临界区。
伪代码：
进程Pi：
flag[i] = TRUE; // (1)进入区
while (flag[j]); // 进入区
critical section; // 临界区
flag[i] = FALSE; // 退出区
remainder section; // 剩余区
进程Pj：
flag[j] = TRUE; // (2)进入区
while (flag[i]); // 进入区
critical section; // 临界区
flag[j] = FALSE; // 退出区
remainder section; // 剩余区
- 优点：避免了“双标志法先检查”同时进入临界区的问题；
- 缺点：若(1)和(2)几乎同时执行时，两进程的标志都被置为
TRUE，双方检测对方状态（执行while语句）时都无法进入临界区，两进程无限期等待，造成“饥饿”现象；
Peterson's Algorithm
基本思想：在“双标志法后检查”的基础上重新设置变量turn，每个进程设置自己的标志后再设置turn标志，然后同时检测另一个进程的状态标志和turn标志，以保证只能有一个进程进入临界区。
伪代码：
进程Pi：
flag[i] = TRUE; turn = j; // 进入区
while (flag[j] && turn == j); // 进入区
critical section; // 临界区
flag[i] = FALSE; // 退出区
remainder section; // 剩余区
进程Pj：
flag[j] = TRUE; turn = i; // 进入区
while (flag[i] && turn == i); // 进入区
critical section; // 临界区
flag[j] = FALSE; // 退出区
remainder section; // 剩余区
- 优点：解决了“饥饿”问题。
硬件同步机制
通过硬件支持实现临界段问题的方法称为低级方法，或称元方法。
中断屏蔽方法
因为CPU只在发生中断时引起进程切换，所以关中断能保证当前运行的进程让临界区的代码顺利地执行完。其典型模式为：
关中断
临界区
开中断
这种方法降低了处理机交替执行程序的能力，因此执行的效率会明显降低。对内核来说，在它执行更新变量或列表的几条指令时关中断是很方便的，但是将关中断的权利交给用户则很不明智。
硬件指令方法
依靠TestAndSet和Swap两条由硬件直接实现的、不会被中断的指令完成。
TestAndSet指令的功能描述如下：
boolean TestAndSet(boolean *lock) {
boolean old;
old = *lock;
*lock = true;
return old;
}
可以为每个临界资源设置一个共享布尔变量lock，初值为false，该变量的值为true表示资源正在被占用。在进程访问临界资源前，利用TestAndSet指令检查和修改标志lock。伪代码如下：
while (TestAndSet(&lock));
critical section;
lock = false;
remainder section;
Swap指令的功能描述如下：
Swap(boolean *a, boolean *b) {
boolean temp;
temp = *a;
*a = *b;
*b = temp;
}
该指令的功能是交换两个字（字节）的内容。
应为每个临界资源设置一个共享布尔变量lock，初值为false，在每个进程中再设置一个局部变量key，初值为true，用于与lock交换信息。在进入临界区前，先利用Swap指令交换lock和key的内容，然后检查key的状态，有进程在临界区时，重复检查和交换过程，直到进程退出。伪代码如下：
key = true;
while (key != false) {
Swap(&lock, &key);
}
critical section;
lock = false;
remainder section;
硬件同步机制的优缺点
- 优点：
- 不管是单处理机还是多处理机，都适用于任意数目的进程；
- 简单、容易验证其正确性；
- 可以支持进程内有多个临界区，只需为每个临界区设置一个布尔变量。
- 缺点：
- 进程等待进入临界区时要耗费处理机时间，不能实现让权等待；
- 由于是从等待进程中随机选择一个进入临界区，有的进程可能一直得不到调度，从而导致“饥饿”现象；
信号量机制
信号量机制是一种功能较强的机制，可用来解决互斥与同步问题，它只能被两个标准的原语wait(S)和signal(S)访问，也可记为P操作和V操作。
原语是指完成某种功能且不可被分割、不能被中断的执行序列，可由硬件实现，在单处理机上可通过软件屏蔽中断的方法实现。
整型信号量
整型信号量被定义为一个表示资源数目的整型量S，wait和signal操作如下：
wait (S) {
while (S <= 0);
S -= 1;
}
signal (S) {
S += 1;
}
在wait操作中，只要信号量S <= 0，就会不断测试（while循环）。因此，该机制未遵循“让权等待”而是使进程处于“忙等”状态。
记录型信号量
记录型信号量除了需要一个用于代表资源数目的整型变量value外，还需要再增加一个进程链表L，用于链接所有等待该资源的进程。
记录型信号量可描述为：
typedef struct {
int value;
struct process *L;
} semaphore;
相应的wait、signal操作如下：
void wait(semaphore S) { // 相当于申请资源
S.value--;
if (S.value < 0) {
add this process to S.L;
block(S.L);
}
}
void signal(semaphore S) {
S.value++;
if (S.value <= 0) {
remove a process P from S.L;
wakeup(P);
}
}
wait操作：S.value--表示进程请求该类资源，当S.value < 0时表示该类资源已经分配完毕，此时进程调用block原语进行自我阻塞，放弃处理机，并加入该类资源的等待队列L。因此，该机制遵循了“让权等待”原则。
signal操作：进程释放了一个资源，S.value++表示系统中可供分配的资源数量加1，若加1后仍然是S.value <= 0，则表示S.L中还有等待该资源的进程被阻塞，因此还应调用wakeup原语，将S.L中一个等待该资源的进程唤醒。
可以理解为P操作是获取锁，V操作是释放锁。
利用信号量实现进程同步
设P2中的语句y需要使用进程P1中的语句x的运行结果（即语句y必须在语句x之后执行），利用信号量实现进程同步的算法如下：
semaphore S = 0; // 初始化信号量
P1() {
...
x; // 语句x
V(S); // 释放锁（告诉进程P2，x语句已完成）
...
}
P2() {
...
P(S); // 获取锁（检查语句x是否运行完成）
y; // 语句y
...
}
总结：前V后P
利用信号量实现进程互斥
只需要把临界区置于P(S)和V(S)之间，就可以实现两个进程对资源的互斥访问。算法如下：
semaphore S = 1; // 初始化信号量
P1() {
...
P(S); // 准备开始访问临界资源，加锁
进程P1的临界区;
V(S); // 访问结束，解锁
...
}
P2() {
...
P(S); // 加锁
进程P2的临界区;
V(S); // 解锁
...
}
总结：若某个行为要用到某种资源，要先对这种资源执行P操作；若某个行为会提供某种资源，需要先对这种资源执行V操作，即在临界区前后分别P、V
利用信号量实现前趋关系
设有如下前趋图：
其中S1，S2，...，S6都是最简单的程序段（只有一条语句）。为使各个程序段能正确执行，应设置若干个初始值为“0”的信号量。如为保证S1 -> S2, S1 -> S3的前趋关系，应分别设置信号量a、b；同样，为保证S2 -> S4, S2 -> S5, S3 -> S6, S4 -> S6, S5 -> S6的前趋关系，应设置信号量c、d、e、f、g。算法如下：
p1() {
S1;
signal(a);
signal(b);
}
p2() {
wait(a);
S2;
signal(c);
signal(d);
}
p3() {
wait(b);
S3;
signal(e);
}
p4() {
wait(c);
S4;
signal(f);
}
p5() {
wait(d);
S5;
signal(g);
}
p6() {
wait(e);
wait(f);
wait(g);
S6;
}
main() {
semaphore a, b, c, d, e, f, g;
a.value = b.value = c.value = 0;
d.value = e.value = 0;
f.value = g.value = 0;
cobegin
p1();
p2();
p3();
p4();
p5();
p6();
coend
}
管程
定义
系统中的各种硬件资源和软件资源均可利用数据结构抽象地描述其资源特性，即用少量信息和对该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。因此，可以利用共享数据结构抽象地表示系统中的共享资源，并且将对该共享数据结构实施的特定操作定义为一组过程（函数），进程对共享资源的申请、释放和其它操作必须通过这组过程间接地对共享数据结构实现操作。代表共享资源的数据结构及由对该共享数据结构实施操作的一组过程所组成的资源管理程序共同构成了一个操作系统的资源管理模块，称为管程。管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程改变管程中的数据。
管程由四部分组成：
- 管程的名称
- 局部于管程内部的共享数据结构说明；
- 对该数据结构进行操作的一组过程（或函数）；
- 对局部于管程的共享数据结构设置初值的语句。
管程的定义描述举例如下：
monitor Demo { // 定义一个名称为“Demo”的管程
// 定义共享数据结构，对应系统中的某些共享资源
共享数据结构S;
// 对共享数据结构的初始化的语句
init_code() {
S = 5; // 初始资源数等于5
}
// 过程1: 申请一个资源
take_away() {
对共享数据结构S的一系列处理；
S--; // 可用资源数-1
...
}
// 过程2: 归还一个资源
give_back() {
对共享数据结构S的一系列处理；
S++; // 可用资源数+1
...
}
}
实际上，管程包含了面向对象的思想：
- 管程把对共享资源的操作封装起来，管程内部的共享数据结构只能被管程的过程所访问，一个进程只有通过调用管程内的过程才能进入管程访问共享资源；
- 每次仅允许一个进程进入管程，从而实现进程互斥（由编译器实现）。
从语言的角度来看，管程主要有以下特征：
- 模块化：管程是一个基本的程序单位，可单独编译；
- 抽象数据类型：管程中不仅有数据，还有对数据的操作；
- 信息掩蔽：管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构和过程（函数）的具体实现外部不可见。
管程和进程的不同：
- 虽然二者都定义了数据结构，但进程定义是私有数据结构PCB，管程定义的是公共数据结构，如消息队列等；
- 二者都存在对各自数据结构上的操作，但进程是由顺序程序执行的有关操作，而管程主要是进行同步操作和初始化操作；
- 设置进程的目的在于实现系统的并发性，设置管程的目的是解决共享资源的互斥使用问题；
- 进程通过调用管程中的过程对共享数据结构实行操作，该过程就如通常的子程序一样被调用，因而管程为被动工作方式，进程为主动工作方式；
- 进程间能并发执行，而管程则不能与其调用者并发；
- 进程具有动态性，管程则是操作系统中的一个资源管理模块，供进程调用。
条件变量
当一个进程调用了管程，在管程中被阻塞或挂起，直到阻塞或挂起的原因解除。而在此期间，如果该进程不释放管程，则其他进程无法进入管程，被迫长时间等待。为了解决这个问题，引入了条件变量condition。通常，一个进程被阻塞或挂起的条件（原因）可有多个，因此在管程中设置了多个条件变量，对这些条件变量的访问只能在管程中进行。
管程中对每个条件变量都必须予以说明，其形式为：condition x, y;对条件变量的操作仅仅是wait和signal，因此条件变量也是一种抽象数据类型，每个条件变量保存了一个链表，用于记录因该条件变量而阻塞的所有进程，同时提供的两个操作可以表示为x.wait和x.signal。其含义为：
-
x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用
x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件变化。此时其他进程可以使用该管程。 -
x.signal：正在调用管程的进程发现x条件发生了变化，则调用
x.signal重新启动一个因x条件而被阻塞或挂起的进程，如果存在多个这样的进程，则选择其中的一个，如果没有，继续执行原进程，而不产生任何结果。
条件变量的定义和使用如下：
monitor Demo {
共享数据结构S;
condition x; // 定义一个条件变量x
init_code() {
...
}
take_away() {
if (S <= 0) {
x.wait(); // 资源不够，在条件变量x上阻塞等待
}
资源足够，分配资源，做一系列相应处理；
}
give_back() {
归还资源，做一系列相应处理；
if (有进程在等待) {
x.signal(); // 唤醒一个阻塞进程
}
}
}
条件变量与信号量的比较：
- 相似点：条件变量的wait/signal操作类似于信号量的P/V操作，可以实现进程的阻塞/唤醒；
- 不同点：条件变量是“没有值”的，仅实现了“排队等待”功能；信号量是“有值”的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。
经典进程的同步问题
进程同步PV操作题分析步骤：
- 关系分析：找出题目中各个进程，分析它们之间同步、互斥的关系；
- 整理思路：根据各进程的操作流程确定P、V操作的大致顺序；
- 信号量设置：设置需要的信号量，并根据题目确定信号量初值（互斥信号量初值一般为1，同步信号量初值要看系统中资源初始数目多少）。
生产者-消费者问题
问题描述
系统中有一组生产者进程和一组消费者进程共享一个公用缓冲池，缓冲池中具有n个缓冲区，只有缓冲池没满的时候，生产者进程才能把消息放入缓冲区，否则必须等待；只有缓冲池不空时，消费者才能从中取出消息，否则必须等待。由于缓冲池是临界资源，它只允许一个生产者放入消息或一个消费者从中取出消息。
代码
semaphore mutex = 1; // 互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n; // 同步信号量，表示空闲缓冲区的数量
semaphore full = 0; // 同步信号量，表示非空闲缓冲区的数量（消息的数量）
producer() { // 生产者进程的任务是：不断地生产产品，并放入缓冲区
while (1) {
生产一个消息;
P(empty); // 消费一个空闲缓冲区
P(mutex); // 进入临界区，获取缓冲池的锁（互斥信号量）
把消息放入缓冲区;
V(mutex); // 离开临界区，释放缓冲池的锁（互斥信号量）
V(full); // 释放一个满的缓冲区（释放一个消息）
}
}
consumer() {
while (1) { // 消费者进程的任务是：不断地取出缓冲区中的消息，然后消费掉
P(full); // 消费一个满缓冲区（消费一个消息）
P(mutex); // 进入临界区，获取缓冲池的锁
从缓冲区中取出一个消息;
V(mutex); // 离开临界区，释放缓冲池的锁
V(empty); // 释放一个空缓冲区
消费消息;
}
}
注意：生产者-消费者问题的易错点在于：在生产者-消费者问题中，实现互斥的P操作必须在实现同步的P操作之后，否则会出现死锁；因为V操作不会导致进程阻塞，所以V操作的顺序无所谓，先释放哪一个都可以。
注意2：如果缓冲区大小为1，有可能不需要设置互斥信号量mutex就可以实现互斥访问缓冲区的功能，但是需要具体问题具体分析（当然加上了也没有问题）。
读者-写者问题
读者-写者问题为解决复杂的互斥问题提供了一个参考思路：设置互斥访问的计数器变量count来记录当前正在访问文件的进程数，可以用count的值判断是第一个或最后一个读进程并做不同处理（加锁、解锁等）。如果对count变量的检查和赋值不能“一气呵成”会导致一些错误，就需要用到互斥信号量实现“一气呵成”。
问题描述
有读者和写者两组并发进程，共享一个文件。当两个以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：
- 允许多个读者可以同时对文件执行读操作；
- 只允许一个写者往文件中写信息；
- 任一写者完成写操作之前不允许其它读者或写者工作；
- 写者执行操作前，应让已有的读者和写者全部退出。
代码
- 读进程优先：只要有源源不断的读进程在读文件，写进程就需要一直阻塞等待，可能会导致写进程“饿死”的情况。
int count = 0; // 用于记录当前有几个读进程在访问文件
semaphore rw = 1; // 用于实现对共享文件的互斥访问
semaphore mutex = 1; // 用于实现对count变量的互斥访问，使得对count变量的检查和赋值可以“一气呵成”
writer() { // 写进程的工作很简单：开始写之前对共享文件加锁，写完后释放锁
while (1) {
P(rw); // 获取共享文件的锁
写文件;
V(rw); // 释放共享文件的锁
}
}
reader() { // 不同的读进程要负责加锁和解锁
while (1) {
P(mutex); // 获取count变量的锁
if (count == 0) { // 第一个读进程要负责加锁
P(rw); // 获取共享文件的锁
}
count++; // 加锁完成，读者计数器加1
V(mutex); // 释放count变量的锁
读文件;
P(mutex); // 获取count变量的锁
count--; // 读文件完成，读者计数器减1
if (count == 0) { // 最后一个读进程负责解锁
V(rw); // 释放共享文件的锁
}
V(mutex); // 释放count变量的锁
}
}
- 写进程优先/读写公平法：有写进程请求访问时，应禁止后续读进程的请求，且在无写进程的情况下才允许读进程再次运行。
int count = 0; // 用于记录当前有几个读进程在访问文件
semaphore rw = 1; // 用于实现对共享文件的互斥访问
semaphore mutex = 1; // 用于实现对count变量的互斥访问，使得对count变量的检查和赋值可以“一气呵成”
semaphore w = 1; // 用于实现“写优先”
writer() { // 写进程的工作很简单：开始写之前对共享文件加锁，写完后释放锁
while (1) {
P(w); // 获取写进程的锁
P(rw); // 获取共享文件的锁
写文件;
V(rw); // 释放共享文件的锁
V(w); // 释放写进程的锁
}
}
reader() { // 不同的读进程要负责加锁和解锁
while (1) {
P(w); // 获取写进程的锁
P(mutex); // 获取count变量的锁
if (count == 0) { // 第一个读进程要负责加锁
P(rw); // 获取共享文件的锁
}
count++; // 加锁完成，读者计数器加1
V(mutex); // 释放count变量的锁
V(w); // 释放写进程的锁，让其它读/写进程可以访问共享文件
读文件;
P(mutex); // 获取count变量的锁
count--; // 读文件完成，读者计数器减1
if (count == 0) { // 最后一个读进程负责解锁
V(rw); // 释放共享文件的锁
}
V(mutex); // 释放count变量的锁
}
}
注意：这种算法中写者不会“饥饿”，但也不是真正的“写优先”，而是相对公平的先来先服务原则。
哲学家进餐问题
哲学家进餐问题的关键在于解决进程死锁。这些进程之间存在互斥关系，但是与之前接触到的互斥关系不同的地方在于每个进程都需要同时持有两个临界资源，因此就有产生死锁的隐患。如果遇到了一个进程需要同时持有多个临界资源的情况，应该参考哲学家进餐问题的思想，分析进程中是否会发生循环等待（是否会发生死锁）。
问题描述
一张圆桌边上坐着五名哲学家，每两名哲学家之间的桌上摆上一根筷子，两根筷子中间是一碗米饭。哲学家们倾注毕生精力思考和进餐，哲学家在思考时，并不影响他人。只有当哲学家饥饿时，才试图拿起左、右两根筷子（一根一根地拿起）。若筷子已在他人手上，则需要等待。饥饿的哲学家只有同时拿到了两根筷子才可以开始进餐，进餐完毕后，放下筷子继续思考。
代码
哲学家按顺序编号为0～4，哲学家i左边的筷子编号为i，右边的筷子编号为(i + 1) % 5
- 可能产生死锁的情况：5名哲学家都想要进餐并分别拿起左边筷子时，再想要拿起右边筷子时就会被阻塞，产生了死锁。
semaphore chopstick[5] = {1, 1, 1, 1, 1};
Pi() { // i号哲学家的进程
do {
P(chopstick[i]); // 取左边筷子
P(chopstick[(i + 1) % 5]); // 取右边筷子
进餐;
V(chopstick[i]); // 放下左边筷子
V(chopstick[(i + 1) % 5]); // 放下右边筷子
思考;
} while (1);
}
- 不会产生死锁的情况
semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 1; // 互斥取筷子的信号量
Pi() {
do {
P(mutex); // 获得互斥量的锁
P(chopstick[i]); // 取左边筷子
P(chopstick[(i + 1) % 5]); // 取右边筷子
V(mutex); // 释放互斥量的锁
进餐;
V(chopstick[i]); // 放下左边筷子
V(chopstick[(i + 1) % 5]); // 放下右边筷子
思考;
} while (1);
}
吸烟者问题
吸烟者问题为解决“可以生产多个产品的单生产者”问题提供了一个思路。关键在于如何用整型变量i实现轮流操作（类似于循环队列中计算当前指针位置时模队列长度的操作）。若一个生产者要生产多种产品，那么各个V操作应该放在各自对应的“事件”发生之后的位置。
问题描述
假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但要卷起一支烟，抽烟者需要有三种材料：烟草、纸和胶水。三个抽烟者中，第一个拥有烟草，第二个拥有纸，第三个拥有胶水。供应者无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉已完成，此时供应者就会将另外两种材料放到桌上，如此重复（让三个抽烟者轮流地抽烟）。
代码
int i = 0; // 用于实现“三个抽烟者轮流抽烟”
semaphore offer1 = 0; // 桌上烟草和纸组合的数量
semaphore offer2 = 0; // 桌上烟草和胶水组合的数量
semaphore offer3 = 0; // 桌上纸和胶水组合的数量
semaphore finish = 0; // 抽烟是否完成
provider() { // 拥有烟草的抽烟者
while (1) {
i = (i + 1) % 3; // 实现循环提供三种组合，即“三个抽烟者轮流抽烟”
if (i == 0) {
V(offer1); // 提供烟草和纸
} else if (i == 1) {
V(offer2); // 提供烟草和胶水
} else if (i == 2) {
V(offer3); // 提供纸和胶水
}
把两种材料放在桌子上;
P(finish); // 等待抽烟者的完成信号
}
}
smoker1() { // 拥有烟草的抽烟者
while (1) {
P(offer3);
从桌子上拿走纸和胶水，卷成烟，抽掉；
V(finish);
}
}
smoker2() { // 拥有纸的抽烟者
while (1) {
P(offer2);
从桌子上拿走烟草和胶水，卷成烟，抽掉;
V(finish);
}
}
smoker3() { // 拥有胶水的抽烟者
while (1) {
P(offer1);
从桌子上拿走烟草和纸，卷成烟，抽掉;
V(finish);
}
}
进程通信
进程通信指的是进程之间的信息交换。
进程的互斥与同步只能称为低级通信，原因如下：
- 效率低：生产者每次只能向缓冲池投放一个产品（消息），消费者每次只能从缓冲区中取得一个消息；
- 通信对用户不透明：OS只为进程间的通信提供了共享存储器，关于进程之间通信所需的共享数据的设置、数据的传送、进程的互斥与同步都需要程序员自己实现。
在进程间需要传送大量数据时，应该使用高级通信方式，主要特点为：
- 使用方便：通信过程对用户是透明的；
- 高效地传送大量数据：用户可以直接利用高级通信命令（原语）高效地传送大量数据。
共享存储器系统
在共享存储器系统中，相互通信的进程共享某些数据结构或共享存储区，进程之间能通过这些空间进行通信。共享存储器系统分为两种类型：
- 基于共享数据结构的通信方式/低级方式：进程公用某些数据结构借以实现进程之间的信息交换。这种方式通信效率低下，属于低级通信；
- 基于共享存储区的通信方式/高级方式：在内存中划出一块共享存储区域，进程可通过对该共享区的读或写交换信息实现通信，OS只负责为通信进程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读/写指令完成。
管道通信系统
管道是用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。
向管道（共享文件）提供输入的发送进程（写进程）以字符流的方式将数据送入管道，接收管道输出的接收进程（读进程）则从管道中接收（读）数据。
为了协调上方的通信，管道机制必须提供以下三方面的协调能力：
- 互斥：当一个进程正在对管道进行读/写操作时另一进程必须等待；
- 同步：当写进程把一定数量的数据写入管道后便去等待，直到读进程取走数据后再唤醒；当读进程读空管道时也应等待，直到写进程将数据写入管道后再唤醒；
- 确定对方是否存在：只有确定对方已存在时才能进行通信。
注意：管道是半双工通信的，要事项全双工通信需要两个管道。
消息传递系统
在该机制中，进程不必借助任何共享存储区或数据结构，而是以格式化的消息为单位将通信的数据封装在消息中，并利用操作系统提供的一组通信命令（原语）在进程间进行消息传递，完成进程间的数据交换。
消息传递系统因实现方式不同可分为两类：
- 直接通信方式：发送进程利用OS所提供的发送原语直接把消息发送给目标进程；
- 间接通信方式：发送和接收进程都通过中间实体（邮箱）的方式进行消息的发送和接收。
线程（Threads）的基本概念
线程的引入
引入进程的目的是更好地使多道程序并发执行，提高资源利用率和系统吞吐量；引入线程的目的是减小程序在并发执行时所付出的时空开销，使OS具有更好的并发性。
由于线程拥有许多传统进程所具有的特征，所以又被称为“轻型进程”，它是一个基本的CPU执行单元，也是程序执行流的最小单元，是进程中的一个实体，是被系统独立调度和分派的基本单位。
- 线程自己不拥有系统资源，它与同属一个进程的其它线程共享自己拥有的全部资源；
- 一个线程可以创建和撤销另一个线程，同一个进程中的多个线程可以并发执行；
- 由于线程之间相互制约，线程在运行中也具有间断性；
- 线程也有就绪、运行、阻塞三种状态。
引入线程后，进程只作为除CPU外的系统资源的分配单元，线程作为处理机的分配单元。
线程与进程的比较
- 调度的基本单位：在传统的OS中，进程是作为独立调度和分派的基本单位，也是能独立运行的基本单位。引入线程后，线程是独立单独和分派的基本单位和能独立运行的基本单位，进程是拥有资源的基本单位。线程切换时仅需保存和设置少量寄存器内容，切换代价远低于进程；在同一进程中切换线程不会引起进程的切换，从一个进程的线程切换到另一个进程中的线程时会引起进程的切换；
- 并发性：在引入线程的OS中，不仅进程之间可以并发执行，线程之间也可以并发执行，这使得OS具有更好的并发性，从而能更加有效地提高系统资源的利用率和系统的吞吐量；
- 拥有资源：进程是拥有资源的基本单位，线程本身不拥有系统资源，而仅有一点必不可少的、能独立运行的资源，比如在每个线程中应具有一个线程控制块TCB、程序计数器、保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。线程除了拥有自己的少量资源外，还允许多个线程共享该进程所拥有的资源，如已打开的文件、定时器、信号量机构等的内存空间和进程申请到的I/O设备等；
- 独立性：在同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多。不同进程的地址空间相互独立，同一进程的不同线程共享进程的内存地址空间和资源，进程内的线程对其他进程不可见；进程间通信需要进程同步互斥手段来保证数据的一致性，而线程间可以直接读/写进程数据段（如全局变量）进行通信；
- 系统开销：在创建和撤销进程时，系统都要为之分配和回收PCB、内存空间和I/O设备等资源，因此OS为此所付出的开销明显大于线程创建和撤销时所付出的开销；此外，由于一个进程中的多个线程具有相同的地址空间，线程之间的同步和通信也比进程简单，在一些OS中，线程的切换、同步和通信都无需操作系统内核的干预；
- 支持多处理机系统：在多处理机系统中，对于传统的进程，不管有多少处理机，该进程都只能运行在一个处理机上；引入线程后，就可以将一个进程中的多个线程分配到多个处理机上，使它们并行执行，加快了进程的执行速度。
线程的属性
多线程操作系统把线程作为独立运行或调度的基本单位，此时进程已经不是一个基本的可执行实体，进程的“执行”状态实际上指的是进程中的线程正在执行。
线程的主要属性如下：
- 线程不拥有系统资源，每个线程拥有一个唯一的标识符和一个线程控制块TCB，线程控制块记录了线程执行的寄存器和栈现场等信息；
- 不同的线程可以执行相同的程序；
- 同一进程中的不同线程共享该进程所拥有的系统资源；
- 线程是处理机调度的基本单位，多个线程可以并发执行；
- 线程在生命周期内会经历就绪态、运行态、阻塞态等各种状态的变化。
线程的实现
线程有两种实现方式：用户级线程（ULT）和内核级线程（KLT）。内核级线程又称为内核支持的线程。
在用户级线程中，有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在，应用程序可以使用线程库设计成多线程程序。
在内核级线程中，线程的管理工作由内核完成，应用程序没有线程管理的代码，只有一个内核级线程的编程接口，内核为进程及其内部的每个线程维护上下文信息，调度也在内核基于线程架构的基础上完成。
有些系统中使用组合的方式的多线程实现，线程的创建在用户空间中完成，线程的调度与同步也在应用程序中进行，一个应用程序中的多个用户级线程被映射到一些内核级线程上。
多线程模型
多线程模型即用户级线程和内核级线程的连接方式。
- 多对一模型：将多个用户级线程映射到一个内核级线程上，线程的管理在用户空间完成。此模式中用户级线程对操作系统不可见。优点：线程管理是在用户空间进行的，效率较高；缺点：一个线程在使用内核服务时被阻塞会导致整个进程被阻塞，多个线程不能很好地运行在多处理机上；
- 一对一模型：每个用户级线程映射到一个内核级线程。优点：一个线程被阻塞后另一个线程可以继续执行，并发能力较强；缺点：每创建一个用户级线程都要创建一个内核级线程，创建线程的开销比较大，会对应用程序的性能造成影响；
- 多对多模型：将n个用户级线程映射到m个内核级线程上，m <= n。优点：既克服了多对一模型并发度不高的缺点，又克服了一对一模型创建进程开销较大的缺点，此外还拥有多对一模型和一对一模型的优点。
