操作系统课件 第三章 处理器管理

姓名：邓红霞学院：计算机科学与技术学院学校：太原理工大学第三章处理器管理进程通信进程间的制约关系进程与线程1处理器调度主要内容23死锁453.1.1进程的引入3.1.2进程的概念3.1.3进程控制3.1.4进程调度3.1.5线程3.1进程与线程

为了提高资源利用率和系统吞吐量，通常会采用多道程序设计技术将多个程序同时装入内存，使他们并发执行。采用一个什么样的概念，来描述计算机程序的执行过程和作为资源分配的基本单位才能充分反映操作系统的执行并发、资源共享及用户随机的特点呢？这个概念就是进程。3.1进程与线程程序的执行分为顺序执行和并发执行。程序的顺序执行具有如下特点：（1）执行的顺序性（2）封闭性程序运行时独占全机资源，只有程序本身才能改变资源的状态（除初始状态外），程序一旦开始执行，其执行结果不受外界因素的影响。（3）结果的可再现性。只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果。3.1.1进程的引入在多道程序设计环境下，内存中允许有多个程序存在，它们轮流地使用CPU。多道程序设计环境下，程序并发执行具有如下特点：（1）执行的并发性一在逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始的执行方式。3.1.1进程的引入在多道程序设计环境下，内存中允许有多个程序存在，它们轮流地使用CPU。多道程序设计环境下，程序并发执行具有如下特点：（2）“封闭性”被打破多道程序共享内存，并发交替占用处理机运行，程序运行不再具有“封闭性”。（3）“结果的可再现性”被打破在

多道程序设计环境中，各个程序的执行不再具有可能完全依照自己的执行次序执行了，程序运行结果不再具有可再现性。3.1.1进程的引入（3）“结果的可再现性”被打破【例3-1】设程序A和程序B是两个并发执行的循环程序，它们共享一个公用变量N。程序A每执行一次循环都对变量N做加1操作，程序B每隔一定时间打印共享变量N中的值，然后将N重新设置为“0”。程序描述如下所述，其中cobegin和coend是并行语句，表示它们之间的程序是可以并发执行的。3.1.1进程的引入（3）“结果的可再现性”被打破3.1.1进程的引入程序的执行有可能出现3种不同情况：（1）…；N++；printf(N)；N=0；…。打印的N值为a+1，循环结束后的N值为0。（2）…；printf(N)；N=0；N++；…。打印的N值为a，循环结束后的N值为1。（3）…；printf(N)；N++；N=0；…。打印的N值为a，循环结束后的N值为0。

上例说明，程序在并发执行时，由于失去了封闭性，其计算结果与并发程序间的执行速度有关，从而使程序的执行失去了可再现性。

程序并发执行时，若共享了公共变量，给定相同的初始条件，若不加以控制，也可能得到不同的结果，称此为与时间有关的错误。3.1.1进程的引入（3）“结果的可再现性”被打破

由于程序在顺序执行时具有顺序性、封闭性和可再现性，使程序和其执行过程之间具有一一对应关系，因此程序这个静态概念完全可以用来代替程序执行过程这个动态概念。

但是，程序的并发执行破坏了程序顺序执行的特点，并产生了一些新的特点，使程序这个静态概念不足以描述程序的执行过程。因此，需要引入一个新的概念来描述程序的并发执行过程，这个新的概念就是“进程”。3.1.1进程的引入人们对进程下过许多的定义。

进程是可以并行执行的计算部分。

进程是一个独立的可以调度的活动。

进程是一抽象实体，当它执行某个任务时，将要分配和释放各种资源。

行为的规则称为程序，程序在处理机上执行时的活动称为进程。以上进程的定义，尽管各有侧重，但在本质上是相同的，即主要注重进程是一个动态的执行过程这一概念。3.1.2进程的概念进程的定义1978年，在庐山召开的国内操作系统讨论会上给出的进程定义如下：进程是具有一定独立功能的程序关于一个数据集合的一次运行活动。进程是程序的运行过程，是系统进行资源分配和调度的一个独立单位。3.1.2进程的概念进程和程序是两个既有联系又有区别的概念，它们的区别和关系可简述如下：

进程是程序的一次执行，属于动态概念；而程序仅是指令的有序集合，属于静态概念。

进程有一个生命周期，它的存在是暂时的，它动态地被创建，被调度执行后消亡；而程序的存在则是永久的。

进程具有并行特征，而程序没有。由进程的定义可知，进程具有并行特征的两个方面，即独立性和异步性。也就是说，在不考虑资源共享的情况下，各进程的执行是独立的，执行速度是异步的。显然，由于程序不反映执行过程，所以不具有并行特征。

一个进程可执行一个或几个程序，一个程序可产生多个进程。3.1.2进程的概念进程的特征（1）动态性。进程是程序的一次执行。（2）并发性。指多个进程同存于内存中，能在一段时间内同时运行。（3）独立性。指进程是一个能独立运行、独立获得资源和独立接受调度的基本单位。凡未建立PCB的程序，都不能作为一个独立的单位参与运行。（4）异步性。由于进程的相互制约，使得进程按各自独立的、不可预知的速度向前推进。异步性会导致执行结果的不可再现性，为此在操作系统中必须配置相应的进程同步机制。3.1.2进程的概念进程的状态及状态转换进程在其生存期内可能处于以下3种基本状态之一。（1）就绪态（Ready）：一个进程已经具备运行条件，但由于无CPU暂时不能运行的状态。当调度给其CPU时，立即可以运行。处于就绪态的进程位于“就绪队列”中。（2）运行态（Running）：进程占用了包括CPU在内的全部资源，并在CPU上运行。（3）等待态（Blocked）：阻塞态、挂起态、封锁态、冻结态、睡眠态。指进程因等待某种事件的发生而暂时不能运行的状态（即使CPU空闲，该进程也不可运行）。处于等待态的进程位于等待队列中。

3.1.2进程的概念进程的状态及状态转换进程3个基本状态之间是可以相互转换的。3.1.2进程的概念进程的状态及状态转换就绪、执行、等待是进程最基本的3种状态，对于一个具体的系统来说，为了实现某种设计目标，进程状态的数量可能多于3个。创建状态：一个进程正在初创时期，操作系统还没有把它列入可执行的进程队列中。终止状态：一个进程或正常结束，或因某种原因被强制结束。这时，系统正在为其进行善后处理。挂起状态：把一个进程从内存转到外存。

3.1.2进程的概念进程的状态及状态转换3.1.2进程的概念就绪/挂起状态：进程在外存。只要被激活，进程就可以进入内存，如果获得CPU，就可以投入运行。等待/挂起状态：进程在外存等待事件的发生。若等待事件发生了，就成为就绪/挂起状态进程的组成系统应该具有一个能够描述进程存在和能够反映进程变化的物理实体，该实体就是进程控制块（ProgramCortrolBlock，PCB）。从系统管理的角度看，进程由3部分组成：进程控制块、有关程序段和该程序段对其进行操作的数据结构集。进程的程序部分描述进程所要完成的功能，数据结构集是程序在执行时必不可少的工作区和操作对象。这两部分是进程完成所需功能的物质基础。3.1.2进程的概念进程控制块PCB作为进程实体的一个组成部分，它包含了有关进程的描述信息、控制信息以及资源信息，是系统对进程实施管理的唯一依据和系统能够感知到进程存在的唯一标识。进程控制块和进程之间存在一一对应关系。3.1.2进程的概念进程控制块一般来说，根据操作系统的要求不同，进程的PCB所包含的内容会多少有所不同。其基本内容由描述信息、控制信息、资源管理信息、CPU现场信息4部分组成3.1.2进程的概念

进程和处理器管理的一个重要任务是进程控制。进程控制是系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。3.1.3进程控制3.1.3进程控制系统在创建、撤销一个进程以及要改变进程的状态时，都要调用相应的程序段来完成这些功能。在操作系统中，通常把进程控制用程序段做成原语。原语，是指在执行过程中不可中断的、实现某种独立功能的、可被其他程序调用的程序。用于进程控制的原语有：创建原语、撤销原语、阻塞原语、唤醒原语等。用于进程控制的原语有：创建原语、撤销原语、阻塞原语、唤醒原语等。3.1.3进程控制原语的特点如下:1)处于操作系统的最低层，是最接近硬件的部分。2)这些程序的运行具有原子性，其操作只能气呵成(主要从系统安全性和便于管理考虑)。3)这些程序的运行时间都较短，而且调用频繁。系统中的设备驱动、CPU切换、进程通信等功能中的部分操作都可以定义为原语，使它们成为内核的组成部分。调用原语的直接方法是关中断，让其所有动作不可分割地完成后在打开中断。3.1.3进程控制进程创建原语进程创建是实现进程从无到有的过程。调用进程创建原语者有可能是系统程序模块（即系统创建方式），也有可能是某个用户进程（即为新建进程的父进程）。由系统统一创建的进程之间的关系是平等的，它们之间一般不存在资源继承关系。而在父进程创建的进程之间则存在隶属关系，属于某个家族的一个进程可以继承其父进程所拥有的资源。在操作系统中，终端用户登录系统、作业调度、系统提供服务、用户程序的应用请求等都引起进程的创建。3.1.3进程控制进程创建原语

进程创建原语流程3.1.3进程控制进程撤销原语进程撤销是进程消亡的过程，以下几种情况都将导致进程被撤销。

该进程已完成所要求的功能而正常终止。

由于某种错误导致该进程非正常终止。

祖先进程要求撤销某个子进程。无论哪一种情况导致进程被撤销，进程必须释放它占用的各种资源和PCB本身，以利于资源回收利用。3.1.3进程控制进程阻塞原语在进程运行过程中，如果期待的某种条件（如键盘输入数据、写盘、其他进程发来的数据等）没有发生，则该进程就由自己调用阻塞原语而进入等待状态。阻塞原语在阻塞一个进程时，由于该进程正处于执行状态，故应先中断处理器和保存该进程的CPU现场。然后，将被阻塞进程置“阻塞”状态后插入等待队列中，再转进程调度程序选择新的就绪进程投入运行。3.1.3进程控制进程唤醒原语如果在进程的运行过程中，释放了某种资源者使某种条件具备，这意味着等待该资源或条件而被阻塞进入等待队列的进程将被唤醒，即重新回到就绪状态。显然，一个处于等待状态的进程不可能自己唤醒自己，唤醒原语可以被系统进程调用，也可以被事件发生进程调用。3.1.3进程控制进程唤醒原语调用唤醒原语的进程称为唤醒进程。唤醒原语首先将被唤醒进程从相应的等待队列中取出，将被唤醒进程置为就绪状态之后，送入就绪队列。在把被唤醒进程送入就绪队列之后，唤醒原语既可以返回原调用程序，也可以转向进程调度，以便让调度程序有机会选择一个合适的进程执行。3.1.3进程控制进程调度原语一个进程运行完分配给它的CPU时间片，或者因为申请某一种条件得不到满足时，就需要放弃CPU。这时，操作系统就要从就绪队列中选择一个新的进程来占有CPU而运行，这就是进程调度原语要做的工作。进程调度原语从就绪队列的头指针开始，按照某种调度算法（在后续内容中予以详细介绍）选出一个进程，将该进程PCB结构中的状态改为运行状态，然后使其退出就绪队列，恢复该进程的现场参数，该进程就占有了CPU时间而进入了运行状态。3.1.4进程调度进程调度的时机运行进程执行完毕运行进程因某种原因被阻塞运行进程时间片用完或者在CPU可剥夺方式下，就绪队列中有优先级高于当前运行进程优先级的进程出现3.1.4进程调度进程调度的实现（1）记录系统中所有进程的执行情况（2）选择占有处理器的进程（3）进程间的切换3.1.4进程调度进程调度算法调度算法既要体现多个就绪进程之间的公平性、进程的优先程度；又要考虑到用户对系统响应时间的要求；还要有利于系统资源的均衡和高效率使用，尽可能地提高系统的吞吐量。当然，这些设计原则有些是相互矛盾的，在一个实际系统中不可能使每项原则都很好地体现。例如，要提高系统资源利用率就无法保障很短的响应时间，要提高系统的吞吐量就难保证对每个就绪进程都公平。因此，实际系统中往往还要根据操作系统的设计和使用目标来确定选择策略。常用的进程调度算法有先来先服务法、时间片轮转法、多级反馈轮转法和优先级法等。3.1.4进程调度进程调度算法（1）先来先服务法就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务（firstcomefirstserve，FCFS）的方式进行调度处理。【例3-2】就绪队列中依次有三个进程A、B、C，A进程需要运行24ms，B和C进程各需要运行3ms。按照FCFS的顺序，进程A先占用处理器，然后是B，最后是C。

按照这种调度顺序，它们的平均等待时间是（0+24+27）/3=17ms。

假定调度顺序换成B、C、A，则它们的平均等待时间是：(0+3+6)/3=3ms。在实际操作系统中，很少单独使用FCFS算法，该算法总是和其他一些算法配合使用。例如，基于优先级的调度算法就是对具有同样优先级的作业或进程采用的FCFS方式。3.1.4进程调度进程调度算法（2）时间片轮转法所有的就绪进程按到达的先后顺序排队，并将CPU的处理时间分成固定大小的时间片。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程时间片轮转法中，时间片长度的选取非常重要，它会直接影响系统开销和响应时间。3.1.4进程调度进程调度算法（2）时间片轮转法【例3-3】有一个分时系统，允许10个终端用户同时工作，时间片设置为100ms。若对用户的每一个请求，CPU将耗费200ms的时间进行处理。试问终端用户提出两次请求的时间间隔最少是多少？因为时间片长度是100ms，有10个终端用户同时工作，所以轮流一次需要花费100ms×10=1s。就是说，在1s内，一个用户可以获得100ms的CPU时间。又因为终端用户的每一次请求需要耗费200ms的时间进行处理，于是终端用户需要获取2个时间片才能等待系统将其请求处理完毕。每1s终端用户获得一次时间片，所以终端用户提出两次请求的时间间隔最少是2s。3.1.4进程调度进程调度算法（3）优先级法对于用户而言，时间片轮转法是一种绝对公平的算法，但对于系统而言，这种算法还没有考虑到系统资源的利用率以及不同用户级别的差别。优先级调度算法为进程设置不同的优先级，就绪队列按进程优先级的不同而排列，每次总是从就绪队列中选取优先级最高的进程运行（在相同优先级的进程中通常是按FCFS的原则选取）。3.1.4进程调度进程调度算法（3）优先级法①静态优先级：指在进程创建时确定其优先级，一旦开始执行其优先级就不能改变。•根据进程的性质、类型和对资源的要求来决定优先级。系统进程比用户进程优先级高；对于用户进程，给予I/O繁忙的进程较高的优先级，充分发挥CPU和外围设备之间的并行能力；给予使用资源如CPU时间短或内存容量少的进程较高的优先级，可以提高系统吞吐率；对于系统进程，也可按功能划分为调度进程、I/O进程、中断处理进程和存储管理进程等而赋予不同的优先级。•根据进程执行任务的重要性和用户请求来决定。例如，系统中处理紧急情况的报警进程让其立即占有处理器投入运行；根据用户请求，给予进程较高的优先级，做“加急”处理。3.1.4进程调度进程调度算法（3）优先级法②动态优先级。基于静态优先级的调度算法实现简单，系统开销小，但系统效率较低，调度性能不高。现在的操作系统中，如果使用优先级调度，则大多采用动态优先级的调度策略。•一个进程已经占有CPU的时间越长，则在被阻塞之后再次获得调度的优先级就越低，反之，其获得调度的可能性就会越大。•一个就绪进程在就绪队列中等待的时间越长，则其获得调度选中的优先级就越高。3.1.4进程调度进程调度算法（3）优先级法②动态优先级。【例3-4】早期UNIX操作系统中，为动态改变一个进程的优先级，采取了设置和系统计算并用的方法。设置用于一个进程变为阻塞时，系统会根据不同的阻塞原因，赋予阻塞进程不同的优先数。这个优先级将在进程被唤醒后发挥作用。计算进程优先级的公式为：p_pri=min{127，(p_cpu/16+PUSER+p_nice)}其含义是在127和(p_cpu/16+PUSER+p_nice两个数之间取最小值。其中，PUSER是一个常数；p_nice是用户为自己的进程设置的优先级，反映该用户进程工作任务的轻重缓急程度；p_cpu是进程使用处理器的时间。3.1.4进程调度进程调度算法（4）多级反馈轮转法多级反馈轮转法（roundrobinwithmultiplefeedback）是一种综合的调度算法，在CPU时间片的选择上，引用了时间片轮转法中的多值时间片策略；而在进程优先级的确定上，又采取了动态优先级的策略。也就是说，多级反馈轮转法综合考虑了进程到达的先后顺序、进程预期的运行时间、进程使用的资源种类等诸多因素。3.1.4进程调度进程调度算法（4）多级反馈轮转法①多级反馈队列。队列的优先级依次降低，时间片依次增长。②调度算法：多级反馈轮转法每次总是选择优先级最高的队列，如果该队列为空，则指针移到下一个优先级队列，直到找到不为空的队列。3.1.4进程调度进程调度算法（4）多级反馈轮转法①多级反馈队列。队列的优先级依次降低，时间片依次增长。②调度算法：多级反馈轮转法每次总是选择优先级最高的队列，如果该队列为空，则指针移到下一个优先级队列，直到找到不为空的队列。新创建的进程，直接进入最高优先级就绪队列的尾部；给定的时间片用完而放弃CPU，在运行前所处队列的基础上，下降一个优先级后再进入所对应优先级就绪队列的末尾；如果进程在运行过程中由于I/O中断或所需资源的不满足而阻塞进入等待队列，则不改变该进程的优先级，在该进程被唤时仍按其中断前的优先级插入相应优先级就绪队列的末尾。3.1.4进程调度进程调度算法（4）多级反馈轮转法③算法特点：•较快的响应速度和短作业优先。•输入/输出进程优先。•运算型进程有较长的时间片。•采用了动态优先级，可变时间片，以适应不同进程对时间的要求。总之，多级反馈轮转算法不仅体现了进程间的公平性、进程的优先程度，而且兼顾了用户对响应时间的要求，还考虑到了系统资源的均衡和高效率使用，提高了系统的吞吐能力。3.1.5线程线程的引入如果说在操作系统中引入进程的目的，是为了使多个程序并发执行，以改善资源利用率及提高系统的吞吐量；那么，在操作系统中再引入线程则是为了减少程序并发执行时所付出的时空开销，使操作系统具有更好的并发性。3.1.5线程线程的引入进程之所以可以独立运行，是因为：①进程是一个可拥有资源的独立单位；②进程是一个可独立调度和分派的基本单位。由于进程是一个资源拥有者，因而在进程的创建、撤销和切换中，系统必须为之付出较大的时空开销。也正因为如此，在系统中所设置的进程数目不宜过多，切换的频率也不宜太高，这也限制了并发程度的进一步提高。如何能使多个程序更好地并发执行，同时又尽量减少系统的开销，已成为设计操作系统时所追求的重要目标。

把处理器调度和其他资源的分配针对不同的活动实体进行，以使其轻装运行；而对拥有资源的基本单位，又不频繁地对其进行切换。正是在这种思想的指导下，产生了线程。3.1.5线程线程的定义

在引入线程的操作系统中，线程是进程中的一个实体，是被系统独立调度和分配的基本单位。

线程基本上不拥有系统资源，只拥有一些在运行中必不可少的资源（如程序计数器、一组寄存器和栈等），但它可与同属一个进程的其他线程共享进程所拥有的全部资源。

一个线程可以创建和撤销另一个线程；同一进程中的多个线程之间可以并发执行。线程也同样有就绪、阻塞和执行三种基本状态，有的系统中线程还有终止状态。线程控制块（TCB）是标志线程存在的数据结构。3.1.5线程线程与进程的比较（1）调度在传统的操作系统中，拥有资源的基本单位、独立调度和分配的基本单位都是进程。而在引入线程的操作系统中，则把线程作为调度和分配的基本单位，而把进程作为拥有资源的基本单位，使传统进程的两个属性分开，显著提高了系统的并发程度。

在同一进程中，线程的切换不会引起进程的切换，在由一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换。3.1.5线程线程与进程的比较（2）并发性在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间，亦可并发执行，使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。（3）拥有资源线程自己不拥有系统资源（只有一些必不可少的资源，线程控制块记录了线程执行的寄存器和栈等现场状态），但它可以访问其隶属进程的资源。3.1.5线程线程与进程的比较（4）系统开销在创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等；在进行进程切换时，涉及当前进程整个CPU环境的保存以及新被调度运行的进程的CPU环境的设置；线程切换只需要保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作。

因此，进程创建、撤销、切换的开销也远大于线程大的开销。3.1.5线程线程与进程的比较（5）独立性每个进程都拥有独立的地址空间和资源，除了共享全局变量，不允许其他进程访问。某个进程中的线程对其他进程不可见。同一进程中的不同线程是为了提高并发性及进行相互之间的合作而创建的，它们共享进程的地址空间和资源。（6）支持多处理器系统对于传统单线程进程，不管有多少个CPU，进程只能运行在一个CPU上。对于多线程进程，可将进程中的多个线程分配到多个CPU上执行。3.1.5线程线程控制块与进程类似，系统也为每个线程配置一个线程控制块，用于记录控制和管理线程的信息。

3.1.5线程线程控制块与进程类似，系统也为每个线程配置一个线程控制块，用于记录控制和管理线程的信息。同一进程中的所有线程都完全共享进程的地址空间和全局变量。各个线程都可以访问进程地址空间的每个单元，所以一个线程可以读、写或甚至清除另一个线程的堆栈。

3.1.5线程线程的实现

线程的实现可以分为两类：用户级线程（userlevelthread，ULT）和内核级线程（kermel-levelthread，KLT）。内核级线程又称内核支持的线程。（1）用户级线程用户级线程就是“从用户视角能看到的线程”，是在用户空间中实现的。在用户级线程中，有关线程创建、撤销和切换等所有工作都由应用程序在用户空间内（用户态）完成。这些线程的线程控制块都设置在用户空间，线程所执行的操作也无需内核支持，内核只关心对常规进程进行管理，内核意识不到ULT的存在。3.1.5线程线程的实现

用户级线程（userlevelthread，ULT）使用ULT方式的优点：①线程切换不需要转换到内核空间，节省了模式切换的开销。②调度算法可以是进程专用的。在不干扰OS调度的情况下，不同的进程可以根据自身需要选择不同的调度算法，以对自己的线程进行管理和调度，而与OS的低级调度算法无关。③用户级线程的实现与OS平台无关，因为面向线程管理的代码属于用户程序的一部分，所有的应用程序都可以共享这段代码。因此，ULT甚至可以在不支持线程机制的OS平台上实现。3.1.5线程线程的实现

用户级线程（userlevelthread，ULT）使用ULT方式的主要缺点：①系统调用的阻塞问题。当线程执行一个系统调用时，不仅该线程会被阻塞，而且进程内的所有线程均会被阻塞。而在KLT方式下，进程中的其他线程仍然可以运行。②不能发挥多CPU的优势，内核每次分配给一个进程的仅有一个CPU，因此，进程中仅有一个线程能执行，在该线程放弃CPU之前，其他线程只能等待。3.1.5线程线程的实现

线程的实现可以分为两类：用户级线程（userlevelthread，ULT）和内核级线程（kermel-levelthread，KLT）。内核级线程又称内核支持的线程。（2）内核级线程内核级线程在内核的支持下运行，它们的创建、阻塞、撤销和切换等也都是在内核空间实现的。为了对内核支持线程进行控制和管理，在内核空间也为每个内核支持线程设置了一个TCB，内核根据该TCB来感知某线程的存在，并对其加以控制。3.1.5线程线程的实现

内核级线程（kermel-levelthread，KLT）这种实现方式的优点：①内核支持线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小；②内核调度以线程为单位，如果进程中的一个线程被阻塞，则内核可以调度该进程中的其他线程来占用CPU，也可运行其他进程中的线程；③在多处理器系统中，内核能够同时调度同一进程中的多个线程并行运行，能发挥多CPU的优势；④内核本身也可以采用多线程技术，可以提高系统的执行速度和效率。3.1.5线程线程的实现

内核级线程（kermel-levelthread，KLT）内核级线程的主要缺点：对于用户的线程切换而言，其模式切换的开销较大。这是因为，在同一个进程中，从一个线程切换到另一个线程时需要从用户态转到内核态进行，用户进程的线程在用户态运行，而线程调度和管理是在内核中实现的。3.1.5线程多线程模型有些系统同时支持用户级线程和内核级线程，把ULT和KLT两种线程进行组合，提供了组合方式的ULT/KLT线程。

（1）多对一模型将多个用户级线程映射到一个内核级线程上。优点：线程管理是在用户空间进行的，无须切换到核心态，因而效率比较高。缺点：一个线程在使用内核服务时被阻塞，则整个进程都会被阻寒；在任一时刻，只有一个线程能够访问内核，多个线程不能同时在多个CPU上运行。3.1.5线程多线程模型（2）一对一模型将每个用户级线程映射到一个内核级线程。优点：当一个线程被阻塞后，允许另一个线程继续执行，所以并发能力较强。缺点：每创建一个用户级线程都需要创建一个内核级线程与其对应，开销较大，因此需要限制整个系统的线程数。Linux和Windows操作系统都实现了一对一模型。（3）多对多模型将n个用户级线程映射到m个内核级线程上，要求m≤n。

特点：是多对一模型和一对一模型的折中，既克服了多对一模型并发度不高的缺点，又客服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点。此外，还拥有多对一模型和一对多模型各自的优点，可谓集两者之所长。3.1.5线程线程的应用在实际应用中，并不是在所有的计算机系统中线程都是适用的。事实上在那些很少进行进程调度和切换的实时系统、个人数字助理系统中，由于任务的单一性，设置线程相反会占用更多的内存空间和寄存器。几种典型的应用如下：（1）服务器中的文件管理或通信控制（2）前后台处理（3）异步处理（4）某些单处理器系统中的用户程序3.2进程间的制约关系并发执行的多个进程，看起来好像是异步前进的，彼此之间都可以互不相关的速度向前推进，而实际上每一个进程在运行过程中并非相互隔绝。一方面它们相互协作以达到运行用户作业所预期的目的，另一方面它们又相互竞争使用系统中的有限资源。所以，它们总是存在着某种直接或间接的制约关系。3.2.1进程互斥和同步的概念临界资源在计算机中有许多资源一次只能允许一个进程使用，如果有多个进程同时使用这类资源，则会引起激烈的竞争，即互斥。通常把那些某段时间内只允许一个进程使用的资源称为临界资源。例如打印机、磁带机等硬件设备和变量、队列等数据结构。3.2.1进程互斥和同步的概念临界区一组进程共享某一临界资源，这组进程中的每一个进程对应的程序中都包含了一个访问该临界资源的程序段。在每个进程中，访问该临界资源的程序段称为临界区或临界段。3.2.1进程互斥和同步的概念临界区分析可知，进程p1执行程序段1时会访问变量x，进程p2执行程序段2时也会访问变量x，x为进程p1和p2的共享变量。为了不发生错误，对于变量x在一段时间内只允许p1或p2一个进程使用，即当进程p1进入程序段1执行时，不允许p2进入程序段2执行。由前面的定义可知，这里共享变量x即为临界资源，程序段1和程序段2即为关于临界资源x的临界区。3.2.1进程互斥和同步的概念互斥为保证与一个临界资源（共享变量）交往的多个进程各自运行的正确性，其中一个进程正在对该临界资源（共享变量）进行操作时，绝不允许其他进程同时对它进行操作。进程间的这种对公有资源的竞争而引起的间接制约关系称为“互斥”。也就是说，不允许两个以上的共享该资源的并发进程同时进入临界区。引起资源不可同时共享的原因：一是资源的物理特性决定的，如打印机等；二是某些资源如果同时被几个进程使用，则一个进程的动作可能会干扰其他进程的动作，共享资源如数据、队列、缓冲区、表格和变量等。3.2.1进程互斥和同步的概念同步当两个进程配合起来完成同一个计算任务时，经常出现这种情况，即当一个进程执行到某一步时，必须等待另一个进程发来的信息（例如必要的数据，或某个事件已发生）才能继续运行下去。有时，还需要两个进程相互交换信息后才能共同执行下去。通常把进程间的这种必须互相合作的协同工作关系、有前后次序的等待关系称为进程同步。3.2.1进程互斥和同步的概念临界区问题可把临界资源的访问过程分成四部分：①进入区：位于临界区前面，用于检查能否进入临界区的那段代码。②临界区：访问该临界资源的程序段。③退出区：位于临界区后面，将“正在访问”临界区的标志清除的那段代码。④剩余区：进程中除进入区、临界区、退出区的剩余代码。3.2.1进程互斥和同步的概念临界区问题为实现进程互斥地进入自己的临界区，可使用软件方法，在系统中设置专门的同步机构来协调各进程间的运行。解决临界区问题的同步机制应遵循以下四条准则：①空闲让进②忙则等待③有限等待④让权等待（非必须）3.2.2进程互斥的实现软件实现方法——Peterson算法Peterson算法是一个经典的基于软件的临界区问题解决方案。基本思想：在进入区设置并检查一些标志来标明是否有进程在临界区中，若已有进程在临界区，则在进入区通过循环检查进行等待，进程离开临界区后则在退出区修改标志。具体做法：（1）设置一个公用整型变量turn,用于指示被允许进入临界区的进程编号,当turn=0时,表示允许P0进程进入临界区；当turn=1时,表示允许P1进程进入临界区。（2）设置一个布尔型数组flag[i],用来标记各个进程想进入临界区的意愿,flag[i]=turn表示Pi进程想要进入临界区。（3）在每个进程进入临界区之前,先设置自己的flag标志,再设置允许进入turn标志；之后再同时检测对方的flag和turn标志，以保证双方同时要求进入临界区时,只允许一个进程进入。3.2.2进程互斥的实现软件实现方法——Peterson算法算法描述：为进入临界区,先将flag[i]置为true,并将turn置为j,表示Pi

进程想进入临界区但优先让对方Pj进入临界区。若双方试图同时进入,则turn几乎同时被置为i和j,但只有一条赋值语句的结果会保持,另一条也会执行,但会被立即重写。变量turn的最终值决定了哪个进程被允许先进入临界区,若turn的值为I,则Pi进入临界区。当Pi退出临界区时，将flag［i］置为false，以允许Pj进入临界区，则Pj在Pi退出临界区后很快就进入临界区。3.2.2进程互斥的实现软件实现方法——Peterson算法由此可见，Peterson算法很好地遵循了“空闲让进”“忙则等待”“有限等待”三个准则，但未遵循“让权等待”准则。需要说明的是，尽管前面提到了解决临界区问题的同步机制需要遵循四个准则，但此处只须满足前三个。这是因为第四个准则“让权等待”属于较高要求，在早期的解决方案中均未对此做出要求。因为该做法虽然会影响系统效率，但不影响临界区问题的解决。3.2.2进程互斥的实现硬件实现方法——关中断当一个进程正在执行它的临界区代码时，防止其他进程进入其临界区的最简单方法是关中断关中断。缺点：①滥用关中断权力可能导致严重后果。对内核来说，在它执行更新变量的几条指令期间，关中断是很方便的，但将关中断的权限交给用户则很不明智，若一个进程关中断后不再开中断，则系统可能会因此终止。②关中断时间过长会影响系统效率，进而会限制CPU交叉执行程序的能力。③关中断方法不适用于多CPU系统，因为在一个CPU上进行关中断并不能防止进程在其他CPU上执行相同的临界区代码。3.2.2进程互斥的实现硬件实现方法——上锁和开锁在锁同步机构中，对应于每一个共享的临界资源（如数据块或设备）都要有一个单独的锁位。常用锁位值为“0”表示资源可用，“1”表示资源已被占用。设w代表锁位，进程使用临界资源必须做如下三个不可分割的操作。①检测w的值。w=1时，表示资源正在使用，于是返回继续进行检查；w=0时，表示资源可以使用，则置w为1（关锁）。②进入临界区，访问资源。③临界资源使用完毕，将置w为0（开锁）。3.2.2进程互斥的实现硬件实现方法——上锁和开锁

算法描述：注意：在检查w的值和置w为1（关锁）这两步之间（test-and-set），w值不能被其他进程所改变。3.2.2进程互斥的实现硬件实现方法——Swap指令算法描述：用Swap指令管理临界区时，为每个临界资源设置一个共享布尔变量lock，初值为false；在每个进程中再设置一个局部布尔变量key，初值为true，用于与lock交换信息。从逻辑上看，Swap指令和TS（test-and-set锁）指令实现互斥的方法并无太大区别，都先记录此时临界区是否已加锁（记录在变量key中），再将锁标志lock置为true，最后检查key，若key为false，则说明之前没有其他进程对临界区加锁，于是跳出循环，进入临界区。3.2.2进程互斥的实现硬件实现方法硬件指令方法实现互斥的优点：①简单、容易验证其正确性；②适用于任意数目的进程，支持多处理器系统；③支持系统中有多个临界区，只需要为每个临界区设立一个布尔变量。缺点：①等待进入临界区的进程会占用CPU执行while循环，不能实现“让权等待”；②从等待进程中随机选择一个进程进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。3.2.2进程互斥的实现信号量和PV操作（1）信号量：信号量的概念和P、V原语是荷兰学者迪杰斯特拉E.W.Dijkstra提出来的。信号灯是交通管理中的一种常用设备，交通管理人员利用信号灯颜色的变化来实现交通管理。在操作系统中，信号量正是从交通管理中引用过来的一个实体。信号量S是一整数。S≥0时，代表可供并发进程使用的资源实体数，S<0时，S的绝对值表示正在等待使用临界区的进程数。建立一个信号量必须说明所建信号量所代表的意义、赋初值，以及建立相应的数据结构，以便指向那些等待使用该临界区的进程。3.2.2进程互斥的实现信号量和PV操作（2）P、V原语

信号量的数值仅能由P、V原语操作改变。当一个进程执行P操作原语P(S)时，应顺序执行下述两个动作：①S:=S-1。②如果S≥0，则表示有资源，该进程继续执行；如果S<0，则表示已无资源，执行原语的进程被置成阻塞状态，并使其在S信号量的队列中等待，直至其他进程在S上执行V操作释放它为止。当一个进程执行V操作原语V(S)时，应顺序执行下述两个动作：①S:=S+1。②如果S＞0，则该进程继续执行；如果S≤0，则释放S信号量队列的排头等待者并清除其阻塞状态，即从阻塞状态转变到就绪状态，执行V(S)者继续执行。3.2.2进程互斥的实现信号量和PV操作（2）P、V原语

信号量的数值仅能由P、V原语操作改变。需要注意的是，P、V操作在执行过程中各个动作都是不可分割的。这就是说，一个正在执行P、V操作的进程，不允许任何其他进程中断它的操作，这样就保证了同时只能有一个进程对信号量S实行P操作或V操作。由P操作中的S:=S-1可知请求的进程获得了一个资源，P操作是申请资源操作。由V操作中的S:=S+1可知请求的进程释放了一个资源，V操作是释放资源操作。进程互斥执行时，可供并发进程使用的资源实体只有1个，所以用于实现互斥机制的信号量的初值设置为1。3.2.2进程互斥的实现用P、V原语实现进程互斥这里的互斥信号量sem有3个值：sem=1，表示没有进程进入临界区；sem=0，表示有一个进程进入临界区；sem=-1，表示有一个进程进入临界区，另一个进程等待进入。用信号量实现两并发进程PA、PB互斥的方法如下：①设sem为互斥信号量，赋初值为1，表示初始时该信号量代表的临界资源未被占用。②将进入临界区的操作置于P(sem)和V(sem)之间，即可实现进程互斥。3.2.2进程互斥的实现用P、V原语实现进程互斥由算法3-5可以看出，在用信号量机制和P、V操作解决互斥问题时，当有一个进程占用临界资源时，其他进程必须等待。只有当占用临界资源的进程释放了资源并唤醒等待进程时，被唤醒的等待进程才有机会占用临界资源，进入临界区。所以，互斥是同步的特例。【提示】①对不同的临界资源需要设置不同的互斥信号量。②P（S）和V（S）必须成对出现，缺少P（S）就不能保证对临界资源的互斥访问；缺少V（S）会使临界资源永远不被释放，从而使因等待该资源而阻塞的进程永远不能被唤醒。③考试还会考查多个资源的问题，有多少资源就将信号量初值设为多少，申请资源时执行P操作，释放资源时执行V操作。3.2.2进程互斥的实现小结：用P、V操作原语实现进程的互斥用P、V操作原语实现进程的互斥所用信号量的初值设为1，表示临界资源未被占用在相关临界区的前后分别施以P操作和V操作，即在相关进程的程序里由P操作和V操作原语紧夹着临界区，保证这些进程互斥地进入各自的临界区用P、V操作原语实现进程互斥的效率更高，因为P操作中引入了阻塞机制，消除了“CPU忙等”现象，符合“等则放权”的原则。P(S)V(S)P(S)V(S)P(S)V(S)P1P2P3临界区3.2.3进程同步的实现使用信号量和P、V原语操作实现进程间的同步。其方法分为三步：①为各并发进程设置私用信号量（把各进程之间发送的消息作为信号量看待，这里的信号量只与制约进程及被制约进程有关而不是与整组并发进程有关，称该信号量为私用信号量。相对应，互斥时使用的信号量是公用信号量。一个进程Pi的私用信号量Semi是从制约进程发送来的进程Pi的执行条件所需要的消息）。②为私用信号量赋初值。③最后利用P、V原语和私用信号量规定各进程的执行顺序。3.2.3进程同步的实现若干进程为了完成一个共同任务而并发执行。合作进程的执行次序3.2.3进程同步的实现共享缓冲区的合作进程的同步【例3-6】设进程Pa和Pb通过缓冲区队列传递数据。Pa为发送进程，Pb为接收进程。Pa发送数据时调用发送过程deposit(data)，Pb接收数据时调用过程remove(data)，且数据的发送和接收过程满足如下条件：•在Pa至少送一块数据入一个缓冲区之前，Pb不可能从缓冲区中取出数据（假定数据块长等于缓冲区长度）。•Pa往缓冲队列发送数据时，至少有一个缓冲区是空的。•由Pa发送的数据块在缓冲队列中按先进先出（FIFO）方式排列。描述发送过程deposit(data)和接收过程remove(data)。3.2.3进程同步的实现共享缓冲区的合作进程的同步按以下三步描述过程deposit(data)和remove(data)。①设Bufempty为进程Pa的私用信号量，Buffull为进程Pb的私用信号量。②令Bufempty的初始值为n（n为缓冲队列的缓冲区个数），Buffull的初始值为0。③实现过程如下：3.2.3进程同步的实现共享缓冲区的合作进程的同步【思考】在该题中需要考虑互斥吗？为什么？如果每次只允许一个进程对缓冲区队列进行操作怎么办？【提示】①P(S)、V(S)总是配对出现：互斥时，配对出现在同一进程中；同步时，配对常出现在不同的进程中，发送消息用V(S)，接收消息用P(S)。②在使用多个信号量时，注意P(S)操作的顺序。3.2.4用P、V原语解决经典的同步/互斥问题生产者-消费者问题

生产者-消费者问题是对多个合作进程之间关系的一种抽象。

例如，对于输入进程和计算进程之间的关系，输入进程是生产者，而计算进程是消费者；对于计算进程和输出进程，计算进程是生产者，输出进程是消费者。再如，计算机系统中，每个进程都申请使用和释放各种不同类型的资源，这些资源既可以是外设、内存及缓冲区等硬件资源，也可以是临界区、数据等软件资源。把系统中使用某一类资源的进程称为该资源的消费者，而把释放同类资源的进程称为该资源的生产者。3.2.4用P、V原语解决经典的同步/互斥问题生产者-消费者问题生产者-消费者问题的结构如图3-18所示。该图中，P1，P2，…，Pm是一群生产者进程，C1，C2，…，Ck是一群消费者进程，它们共享一个长度为n（n＞0）的有界缓冲区。设生产者进程和消费者进程是互相等效的，它们具有同步关系：只有当缓冲区未满时，才允许生产者进程往缓冲区中放入产品；类似地，只有当缓冲区未空时，才允许消费者进程从缓冲区中取走产品。另外，由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程之间必须互斥执行。3.2.4用P、V原语解决经典的同步/互斥问题生产者-消费者问题生产者-消费者问题的结构如图3-18所示。该图中，P1，P2，…，Pm是一群生产者进程，C1，C2，…，Ck是一群消费者进程，它们共享一个长度为n（n＞0）的有界缓冲区。为解决生产者-消费者问题，应该设置两个同步信号量：一个表示有界缓冲区中的空单元数，用empty表示，其初值为有界缓冲区的大小n；另一个表示有界缓冲区中非空单元数，用full表示，其初值为0。设公用信号量mutex保证生产者进程和消费者进程之间的互斥，表示可用有界缓冲区的个数，初值为1。3.2.4用P、V原语解决经典的同步/互斥问题生产者-消费者问题用信号量机制解决生产者—消费者问题的算法：

生产者i

生产出一产品；

P（empty）；

P（mutex）；

将该产品放入缓冲区；

V（mutex）；

V（full）；

消费者j

P（full）；P（mutex）；

从缓冲区取出一产品；

V（mutex）；V（empty）；

消费该产品；

生产者i

生产出一产品；

P（empty）；

P（mutex）；

将该产品放入缓冲区；

V（mutex）；

V（full）；

消费者j

P（full）；P（mutex）；

从缓冲区取出一产品；

V（mutex）；V（empty）；

消费该产品；讨论：P、V不成对以及P的顺序不正确

桌子上有个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果:仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。练习：3)信号量设置。首先将信号量plate设置互斥信号量，表示是否允许向盘子放入水果，初值为1表示允许放入，且只允许放入一个。信号量apple表示盘子中是否有苹果，初值为0表示盘子为空，不许取，apple=1表示可以取。信号量orange表示盘子中是否有橘子，初值为0表示盘子为空，不许取，orange=1表示可以取。1)关系分析。这里的关系要稍复杂些。由每次只能向其中放入一只水果可知，爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行，不可能并发。2)整理思路。这里有4个进程，实际上可抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上。semaphoreplate=1,apple=0,orange=0;

dad(){while(1){prepareanapple;P(plate);puttheappleontheplate;V(apple);}}//父亲进程

//互斥向盘中取、放水果//向盘中放苹果//允许取苹果mom(){while(I){prepareanorange;P(plate);puttheorangeontheplate;V(orange);}}

//母亲进程

//互斥向盘中取、放水果//向盘中放橘子//允许取橘子son(){while(1){P(orange);takeanorangefromtheplate;V(plate);eattheorange;}}//儿子进程

//互斥向盘中取橘子

//允许向盘中取、放水果

daughter(){while(1){P(apple);takeanapplefromtheplate;V(plate);eattheapple;}}

//女儿进程

//互斥向盘中取苹果

//允许向盘中取、放水果

3.2.4用P、V原语解决经典的同步/互斥问题读者-写者问题一个数据对象（如一个文件或记录）若被多个并发进程所共享，且其中一些进程只要求读该数据对象的内容，而另一些进程则要求修改它，对此，可把那些只想读的进程称之为“读者”，而把要求修改的进程称为“写者”。显然，允许多个读者同时读一个共享对象，但绝不允许一个写者和其他读者或多个写者同时访问一个共享对象，也禁止多个写者访问一个共享对象，否则会产生混乱。可见，读者-写者问题实际上是一个保证一个写者进程必须与其他写进程或读进程互斥访问同一共享对象的同步问题。3.2.4用P、V原语解决经典的同步/互斥问题读者-写者问题读者-写者问题是另一个典型的进程同步机制，还是按照前面所说的步骤进行分析：1、分析各进程之间的制约关系；2、设置信号量，给出信号量物理含义，以及信号量初值3、写出利用信号量进行控制的各进程的流程/算法相互的制约关系1、写者和写者是互斥的；2、读者和写者是互斥的；读者必须等待写者写完后，才能访问；写者必须等待所有读者全部出来以后，才能访问。3、读者和读者是共享的：一个读者在里面，另一个读者也可以进去；3.2.4用P、V原语解决经典的同步/互斥问题读者-写者问题需要设置一个整型变量和两个互斥信号量：①读者和写者互斥，写者与写者互斥。②共享的数据对象是临界资源。可以设置一个互斥信号量w_mutex：用于实现一个写者与其他读者或写者对共享数据对象的互斥访问，由第一个进入和最后一个离开共享数据对象的读者以及所有写者共同使用，初值为1。③读者可以共享读，实际上，只有第一个进入读者需要和写者互斥。这里定义一个整型变量read_count：一个计数器，用来记录当前正在读此共享数据对象的读者进程个数，初值为0，进一个加1，走一个减1。④读者-读者之间新增的互斥关系。读者需要互斥地访问read_count，故需要再设一个初值为1的互斥r_mutex：用于实现所有读者进程对计数器read-count访问的互斥，供所有读者进程使用。3.2.4用P、V原语解决经典的同步/互斥问题读者-写者问题3.2.4用P、V原语解决经典的同步/互斥问题读者-写者问题在上面的算法中，读进程是优先的，即当存在读进程时，写操作将被延迟，且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式会导致写进程可能长时间等待，且存在写进程“饿死”的情况。若希望写进程优先，即当有读进程正在读共享文件时，有写进程请求访问，这时应禁止后续读进程的请求，等到已在共享文件的读进程执行完毕，立即让写进程执行，只有在无写进程执行的情况下才允许读进程再次运行。为此，增加一个信号量并在上面程序的writer()和reader()函数中各增加一对PV操作，就可以得到写进程优先的解决算法。有些书上把这个算法称为读/写公平法，即读/写进程具有一样的优先级。3.2.4用P、V原语解决经典的同步/互斥问题读者-写者问题3.2.4用P、V原语解决经典的同步/互斥问题哲学家就餐问题有5位哲学家，共享一张放有5把椅子的桌子，每人分得一把椅子，他们的生活方式是交替地进行思考和进餐。但是，桌子上总共只有5支筷子，在每人两边分开各放一支。哲学家们在肚子饥饿的时候才试图分两次从两边拾起筷子就餐。条件如下：①只有拿到两支筷子时，哲学家才能吃饭。②如果筷子已在他人手上，则该哲学家必须等到他人吃完之后才能拿到筷子。③任一哲学家在自己未拿到两支筷子吃饭之前，决不会放下自己手中的筷子。针对哲学家就餐，请解决如下两个问题：①试描述一个保证不会出现两个邻座同时要求吃饭的通信算法。②描述一个既没有两邻座同时吃饭，又没有人饿死（永远拿不到筷子）的算法。在什么情况下，5位哲学家全部吃不上饭？3.2.4用P、V原语解决经典的同步/互斥问题哲学家就餐问题假定食物足够，筷子就成了哲学家进餐需要竞争的临界资源，并且每根筷子都是一个临界资源，都需要一个互斥信号量来描述，为此，可设置信号量c[0]～c[4]，初始值均为1，分别表示i号筷子被拿（i=0，1，2，3，4），开始时5根筷子均可被申请使用。这样，第i个哲学家要吃饭，可描述如下：虽然上述过程能保证两邻座不同时吃饭，但会出现5位哲学家一人拿一支筷子，谁也吃不上饭的死锁情况。3.2.4用P、V原语解决经典的同步/互斥问题哲学家就餐问题解决这种死锁现象的方法有以下几种：①至多只允许4位哲学家同时拿起自己左边的筷子，以保证至少有一位哲学家可以进餐。当该哲学家用餐完毕放下筷子后，就可以使更多的哲学家进餐。②让奇数号的哲学家先取右手边的筷子，让偶数号的哲学家先取左手边的筷子。这样，总会有一个哲学家能获得两根筷子而进餐。③仅当哲学家左、右两根筷子均可用时，才允许他拿起筷子进餐，即左右两个筷子一起申请，而不是分两次申请，以预防死锁的发生。3.2.4用P、V原语解决经典的同步/互斥问题哲学家就餐问题如果按照第一种方法，需要增设一个互斥信号量，如count，初值是4。每个想拿起左边筷子的哲学家必须先对count执行一个P操作，这就限制了同时拿到左边筷子的人数。其程序描述如下：3.2.4用P、V原语解决经典的同步/互斥问题哲学家就餐问题第二种方法的程序描述如下：3.2.5结构化的同步/互斥机制—管程前面介绍的信号量及P、V操作属于分散式同步机制，由于对临界区的执行分散在各进程中，这样不便于系统对临界资源的控制和管理，也很难发现和纠正分散在用户程序中的对同步原语的错误使用等问题。为此，应把分散的各同类临界区集中起来，并为每个可共享资源设立一个专门的管程来统一管理各进程对该资源的访问。这样既便于系统管理共享资源，又能保证互斥访问。3.2.5结构化的同步/互斥机制—管程管程的定义系统中的各种硬件资源和软件资源，均可用数据结构抽象地描述其资源特性。用少量信息和对资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。利用共享数据结构抽象地表示系统中的共享资源，而把对该数据结构实施的操作定义为一组过程。进程对共享资源的申请、释放等操作，都通过这组过程来实现，这组过程还可以根据资源情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。这个代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程（monitor）。3.2.5结构化的同步/互斥机制—管程管程的定义管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。Hansen在并发Pascal语言中首先引入了管程，将它作为语言中的一个并发数据结构类型。由上述定义可知，管程由四部分组成：①管程的名称。②局部于管程内部的共享结构数据说明；③对该数据结构进行操作的一组过程（或函数）；④对局部于管程内部的共享数据设置初始值的语句。3.2.5结构化的同步/互斥机制—管程管程的定义由此可看出，管程有两个重点：①局部于该管程的共享数据，这些数据表示了相应资源的状态。②局部于该管程的若干过程，每个过程完成关于上述数据的某种规定操作。局部于管程内的数据结构只能被管程内的过程所访问；反之，局部于管程内的过程只能访问该管程内的数据结构。3.2.5结构化的同步/互斥机制—管程管程的定义管程的定义举例如下：3.2.5结构化的同步/互斥机制—管程共享变量因为管程是互斥进入的，所以当一个进程试图进入一个已经被占用的管程时，它应当在管程入口处等待。因而在管程入口处应当有一个进程等待队列，称为入口等待队列。当一进程进入管程执行管程的某个过程时，如果因某原因而被阻塞，应立即退出该管程，否则就会阻挡其他进程进入该管程，而它自己又不能往下执行，这就有可能造成死锁。为此，引入了条件（condition）变量及其操作的概念。每个独立的条件变量是和进程需要等待的某种原因（或说条件）相联系的，定义一个条件变量时，系统就建立一个相应的等待队列。3.2.5结构化的同步/互斥机制—管程共享变量因为管程是互斥进入的，所以当一个进程试图进入一个已经被占用的管程时，它应当在管程入口处等待。因而在管程入口处应当有一个进程等待队列，称为入口等待队列。当一进程进入管程执行管程的某个过程时，如果因某原因而被阻塞，应立即退出该管程，否则就会阻挡其他进程进入该管程，而它自己又不能往下执行，这就有可能造成死锁。为此，引入了条件（condition）变量及其操作的概念。每个独立的条件变量是和进程需要等待的某种原因（或说条件）相联系的，定义一个条件变量时，系统就建立一个相应的等待队列。3.2.5结构化的同步/互斥机制—管程共享变量条件变量有两种操作：wait(x)和signal(x)，其中x为条件变量。wait把调用者进程挂在与x相应的等待队列上，signal唤醒相应等待队列上的一个进程。在管程内部，由于执行唤醒操作，可能出现多个等待队列，因而在管程内部需要有一个进程等待队列，这个等待队列称为紧急等待队列，它的优先级应当高于入口等待队列优先级。一个管程中的进程等待或离开管程时，如果紧急等待队列非空，则唤醒该队列头部的进程；如果紧急等待队列为空，则释放管程的互斥权，即准许入口等待队列的一个进程进入该管程。3.2.5结构化的同步/互斥机制—管程共享变量条件变量和信号量的比较：①相似点：条件变量的wait/signal操作类似于信号量的P/V操作，可以实现进程的阻塞/唤醒。②不同点：条件变量是“没有值”的，仅实现了“排队等待”功能；而信号量是“有值”的，信号量的值反映了剩余资源数。而在管程中，剩余资源数用共享数据结构记录。3.2.5结构化的同步/互斥机制—管程管程的应用前面曾给出了利用信号量及其P、V操作实现的生产者-消费者问题，这里再以生产者-消费者共享环形缓冲池为例，给出环形缓冲池的管程结构。3.2.5结构化的同步/互斥机制—管程管程的应用管程ringbuffer包含两个局部过程：

过程put负责执行将数据写入某个缓冲块的操作；

过程get负责执行从某个缓冲块读取数据的操作。empty和full被定义为条件变量，对应缓冲池满和缓冲池空条件等待队列。

任一进程都必须通过调用管程ringbuffer来使用环形缓冲池，生产者进程调用其中的put过程，消费者进程调用get过程。在利用管程解决生产者-消费者问题时，其中的生产者-消费者可描述为：3.3进程通信进程通信意味着在进程之间交换信息。根据进程间交换的信息量，可将进程通信分为低级通信方式和高级通信方式两种。低级通信方式，即进程之间交换的仅是控制信息，而不是大批量数据，例如，进程的互斥和同步。高级通信方式，即进程之间进行大批量数据的传送。本节所讨论的进程通信主要是指进程的高级通信方式。进程通信主要有三种方式：共享存储器、消息传递和管道通信。3.3.1进程通信的类型进程通信主要有三种方式：共享存储器、消息传递和管道通信。共享存储器在共享存储器方式中，相互通信的进程共享某些数据结构或存储区，进程之间能够通过这些空间进行通信。据此，又可把它们分成以下两种类型：（1）基于共享数据结构的通信方式例如，在生产者-消费者问题中的有界缓冲区。这种通信方式仅适用于传送相对较少量的数据，通信效率低下，属于低级进程通信。（2）基于共享存储区的通信方式为了传送大量数据，在内存中划出了一块共享存储区，各进程可通过对该共享存储区的读/写来交换信息、实现通信，数据的形式和位置（甚至访问）均由进程负责控制，而非OS。这种通信方式属于高级进程通信。3.3.1进程通信的类型消息传递在消息传递系统中，进程间的数据交换，是以格式化的消息（message）为单位的；在计算机网络中，把消息称为报文。程序开