OUC 操作系统 第二章 进程管理

1、1第二章第二章 进程管理进程管理第一节第一节 进程的基本概念进程的基本概念第二节第二节 进程控制进程控制第三节第三节 进程同步进程同步第四节第四节经典进程同步问题经典进程同步问题第五节第五节管程管程第六节第六节进程通信进程通信第七节第七节线程线程重点第一节第一节进程的基本概念进程的基本概念程序的顺序执行及特征程序的顺序执行及特征前趋图前趋图程序的并发执行及特征程序的并发执行及特征进程的特征与状态进程的特征与状态进程控制块进程控制块2在单道系统中，程序的执行是顺序的即必须在一个程序执行完后，才允许另一个程序执行在多道程序环境下，允许多个程序并发执行。即允许暂停一个程序的执行，而转去执行另一个程序

2、程序的这两种执行方式间有着显著的不同3 在多道程序设计环境下，内存中允许有多个程序存在，它们轮流地使用着CPU。4不同环境下程序的执行特性不同环境下程序的执行特性1 1、程序顺序执行的特征程序顺序执行的特征程序顺序执行的特征：程序顺序执行的特征：顺序性顺序性每一个操作必须在下一个操作开始之前结束每一个操作必须在下一个操作开始之前结束封闭性封闭性程序运行时独占全机资源，资源的状态只有本程程序运行时独占全机资源，资源的状态只有本程序才能改变序才能改变可再现性可再现性只要初始条件和运行环境相同，当程序重复执行只要初始条件和运行环境相同，当程序重复执行时，都将获得相同的结果。时，都将获得相同的结果。5

3、2、前趋图、前趋图前趋图：有向无环图前趋图：有向无环图(DAG)作用：作用：用于描述程序段或进程间执行的前后用于描述程序段或进程间执行的前后顺序。顺序。结点：结点：表示程序段或进程，或一条语句表示程序段或进程，或一条语句有向边：有向边：表示结点之间的偏序表示结点之间的偏序(前驱前驱)关系关系6 X前驱图的例子： S1：a = x + 2; S2: b = y + 4; S3：c = a + b; S4：d = c + b;73、程序的并发执行、程序的并发执行8I1C1P1I2I3C2P2C3P3n并发执行时的前趋图并发执行时的前趋图u有三个程序：I=输入，C=计算, P=打印9并发执行时的特征

4、并发执行时的特征l间断性间断性“停停走走停停走走”l失去封闭性失去封闭性原因：多个程序共享资源原因：多个程序共享资源l不可再现性不可再现性例如例如:有两个循环程序有两个循环程序A和和B，共享一个变量，共享一个变量n。程序。程序A每执行一次时，都要做每执行一次时，都要做n=n+1;程序程序B每执行一次时，都每执行一次时，都要执行要执行Print(n)；然后将；然后将n置成置成0。程序。程序A和和B并发执行时，并发执行时，可能出现的情况如下：可能出现的情况如下：1、n=n+1在在print(n)和和n=0之前，得到的之前，得到的n值为值为n+1,n+1,02、n=n+1在在print(n)和和n=

5、0之后，得到的之后，得到的n值为值为n,0,13、n=n+1在在print(n)和和n=0之间，得到的之间，得到的n值为值为n,n+1,0顺序程序与并发程序的比较顺序程序与并发程序的比较 顺序程序顺序程序 并发程序并发程序 执行过程执行过程 顺序执行交替执行封闭性封闭性 独占资源具有封闭性共享资源不具有封闭性可再现性可再现性x程序间关系程序间关系 x间接制约或直接制约10在多道程序下，程序并发执行，因此失去封闭性，致使程序出现不可再现性，这样程序执行就失去意义。所以通常意义下的程序不能参与并发执行。为使程序能并发运行，且对并发程序进行描述和控制。在OS中，以“程序”为基础，又引入了“进程”这一

6、新的概念。114、进程的特征与状态、进程的特征与状态进程的定义与特征进程的定义与特征进程的基本状态进程的基本状态进程的挂起状态进程的挂起状态12为什么引入进程？为什么引入进程？刻画系统的动态性，发挥系统的并发性，提高资刻画系统的动态性，发挥系统的并发性，提高资源利用率。源利用率。解决共享性，正确描述程序的执行状态。解决共享性，正确描述程序的执行状态。特征：特征：结构性结构性(PCB)动态性动态性并发性并发性独立性独立性异步性异步性13进程的定义与特征进程的定义与特征结构特征 进程实体 = 程序 + 进程控制块(PCB)14Windows 中的进程1516进程A进程B进程进程A A执行完后寄存器

7、的状态进程进程B B执行完后寄存器的状态恢复进程进程A A上次执行完时寄存器的状态进程进程A的的PCB暂存进程进程A A执行完时寄存器的状态进程进程B的的PCB动态性动态性进程实质是进程实体的一次执行过程体现在 “由创建而生，由调度而执行，由撤销而亡”并发性并发性多个进程实体同存于内存中，并发执行程序(没建立PCB)是无法并发执行的。17独立性独立性进程实体是一个独立运行、独立分配资源、独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立单位参与运行。异步性异步性进程按各自独立的、不可预知的速度执行(即按异步方式运行)。18进程进程是一个动态的概念是一个动态的概念程序的一次执行。一个

8、程序及其数据在处理机上顺序执行时所发生的活动。程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。进程的定义进程的定义进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。通常，也把“进程实体”简称为“进程”19进程和程序的区别与联系进程和程序的区别与联系n区别区别 进程是动态概念，强调的是执行，有创建、有撤销，存在是暂时的； 程序是一静态概念，程序是指令的有序集合，“永远”存在；进程具有并发性，而程序没有；进程是接受计算机资源的基本单位，程序不是。n联系联系n进程是程序在数据集上的一次执行；n一个程序可对应多个进程，一个进程可包括多个程序。20小结：对小结：对

9、“进程进程”这一概念如何理解这一概念如何理解动态的组成n给程序附加上PCB，形成了进程实体PCB的作用n保存执行过程中的一些信息，再次执行时恢复这些信息，以保证执行的正确性。也可用于OS控制和描述进程的执行。21进程的基本状态进程的基本状态就绪状态（就绪状态（ReadyReady）得到了除得到了除CPUCPU以外的所有必要资源以外的所有必要资源执行状态（执行状态（RunningRunning）已获得处理机，程序正在被执行已获得处理机，程序正在被执行阻塞状态（阻塞状态（BlockedBlocked）因等待某事件发生而暂时无法继续执行，从因等待某事件发生而暂时无法继续执行，从而放弃处理机，使程序执

10、行处于暂停状态而放弃处理机，使程序执行处于暂停状态中断中断接纳接纳完成完成进程调度进程调度事件发生事件发生等待某事件等待某事件新进程新进程结束结束就绪就绪执行执行阻塞阻塞22进程的挂起状态进程的挂起状态挂起状态的引入挂起状态的引入父进程考查和修改、协调子进程间的活动父进程考查和修改、协调子进程间的活动操作系统协调资源使用或进行记账操作系统协调资源使用或进行记账终端用户的请求终端用户的请求负荷调节的需要，如实时紧急任务负荷调节的需要，如实时紧急任务激活激活挂起挂起调度调度挂起挂起I/O释放释放I/O释放释放I/O请求请求激活激活挂起挂起静止静止就绪就绪静止静止阻塞阻塞活动活动就绪就绪执行执行活动

11、活动阻塞阻塞235、进程控制块、进程控制块PCB(ProcessControlBlock)PCB中记录了操作系统所需的、用于描述进程的中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。当前情况以及控制进程运行的全部信息。是进程是进程存在的唯一标志。存在的唯一标志。作用：作用：是使一个在多道程序环境下不能独立运行是使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，一个的程序，成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。能与其他进程并发执行的进程。位置：位置：PCB存放在存放在OS中专门开辟的中专门开辟的PCB区内区内2425PCB中

12、的信息中的信息l进程标识符进程标识符：唯一的标识一个进程：唯一的标识一个进程 内部标识（内部标识（OS） 外部标识（由创建者提供，由字母数字组成）外部标识（由创建者提供，由字母数字组成）Unix/Linux下的进程标识符是什么样的？ps ef26kill -9 12189Windows下的进程标识符是什么样的？27外部标识符外部标识符使用使用“内部标识符内部标识符”控制控制处理机状态处理机状态： 由由CPUCPU的各种寄存器中的内容组成。的各种寄存器中的内容组成。 通用通用R R 指令计数器指令计数器PC PC 程序状态字程序状态字PSW PSW 用户栈指针用户栈指针2829l进程调度信息进程

13、调度信息： 进程状态进程状态 进程优先级进程优先级 其它信息其它信息 等待事件（阻塞原因）等待事件（阻塞原因）l进程控制信息进程控制信息： 程序和数据的地址程序和数据的地址 同步和通信机制同步和通信机制 资源清单资源清单 链接指针链接指针进程控制块的组织方式进程控制块的组织方式PCBPCB数目数目一个系统中的一个系统中的PCBPCB数目可为数十个、数百个甚至数千个数目可为数十个、数百个甚至数千个链接方式链接方式把具有同一状态的把具有同一状态的PCBPCB，链接成一个队列，链接成一个队列就绪队列、若干个阻塞队列、空队列就绪队列、若干个阻塞队列、空队列索引方式索引方式系统根据所有进程的状态建立相应

14、的索引表系统根据所有进程的状态建立相应的索引表就绪索引表、阻塞索引表等，索引表在内存的首地址记就绪索引表、阻塞索引表等，索引表在内存的首地址记录在内存的一些专用单元中。录在内存的一些专用单元中。3031执行指针执行指针就绪队列指针就绪队列指针阻塞队列指针阻塞队列指针空闲队列指针空闲队列指针执行指针执行指针就绪队列指针就绪队列指针阻塞队列指针阻塞队列指针PCB链接队列示意图链接队列示意图按索引方式组织按索引方式组织PCB第二节第二节 进程的控制进程的控制进程创建进程创建进程撤消进程撤消进程阻塞进程阻塞进程唤醒进程唤醒进程挂起与激活进程挂起与激活32进程控制是进程管理最基本的功能：进程控制是进程管

15、理最基本的功能： (1) (1) 用于创建新进程用于创建新进程 (2) (2) 终止一个已完成的进程终止一个已完成的进程 (3) (3) 终止一个无法运行下去的进程终止一个无法运行下去的进程 (Kill)(Kill) (4) (4) 负责进程的状态转换负责进程的状态转换 ( (就绪就绪执行执行) )33进程图进程图 描述一个进程家族关系的有向树有向树子进程可以继承继承父进程的所有资源所有资源(打开的文件、分配的缓冲区等)撤销子进程时，把它从父进程那里获得的资源还给父进程撤销父进程时，要同时撤销它所有的子进程34ABCDEF父进程子进程在在PCB中设置中设置家族关系表项：家族关系表项：记录父进程

16、，及记录父进程，及所有的子进程所有的子进程1、进程创建、进程创建35引起创建进程的事件引起创建进程的事件l用户登录用户登录l用户从终端登录，为其建立进程(分时系统)l作业调度作业调度l把作业装入内存 (批处理系统)l提供服务提供服务l为某个请求创建专门的进程。例如用户打印时，创建打印进程l应用请求应用请求l建子进程，以并发完成工作，加速任务 (由应用程序创建)36申请空的申请空的PCB请求创建进程请求创建进程为新进程分配资源为新进程分配资源初始化初始化PCB插入到就绪队列插入到就绪队列就绪队列就绪队列(申请唯一的标识符，从PCB集合中取空白项)(将所需信息填入PCB：标识符、处理机状态、进程状

17、态、优先级等等)(如果就绪队列能容纳新进程的话)l进程的创建流程进程的创建流程(分配内存，OS要知道新进程的大小)2、进程撤消、进程撤消引起进程终止的事件引起进程终止的事件正常结束：执行到最后的结束指令、中断正常结束：执行到最后的结束指令、中断异常结束：出现错误或因故障而被迫终止异常结束：出现错误或因故障而被迫终止外界干扰：进程应外界的请求而终止运行外界干扰：进程应外界的请求而终止运行进程撤消的过程进程撤消的过程一个进程可以向其父进程申请撤消自己；一个进程可以向其父进程申请撤消自己；也可以因父进程的被撤销而被同时撤消。也可以因父进程的被撤销而被同时撤消。37l进程终止的流程38从从PCB集合中

18、找到集合中找到相应进程的相应进程的PCB,读出其状态读出其状态停止执行，停止执行，置调度标志为置调度标志为true进程正在执行？进程正在执行？YN终止所有子进程终止所有子进程有子进程？有子进程？YN归还所占的资源归还所占的资源(给父进程或给父进程或OS)把把PCB从队列中从队列中移走移走39PDPBPEPCPFPAPIPHPGPJPKPLPMPN3、进程阻塞、进程阻塞引起阻塞的事件引起阻塞的事件请求系统服务请求系统服务OS不能立即满足(打印机被别人使用)启动某种操作启动某种操作I/O操作后才能继续执行数据尚未到达数据尚未到达进程合作时，只有新数据到达才能继续执行无新工作可做无新工作可做一些具有

19、特定功能的系统进程系统进程，完成任务后就把自己阻塞起来，等待新任务到来(如发送数据进程)40l进程的阻塞流程 (进程自己阻塞自己进程自己阻塞自己)41立即停止执行立即停止执行改变状态为改变状态为“阻塞阻塞”插入到阻塞队列插入到阻塞队列就绪队列选择新的就绪进程CPU4、进程唤醒、进程唤醒引起唤醒的事件引起唤醒的事件与引起阻塞的事件相对应与引起阻塞的事件相对应进程唤醒的过程进程唤醒的过程阻塞进程所期待的事件出现，有关的进程调用唤醒阻塞进程所期待的事件出现，有关的进程调用唤醒原语，将等待该事件的进程唤醒原语，将等待该事件的进程唤醒将将PCB从阻塞队列中移出，修改从阻塞队列中移出，修改PCB中的状态信

20、息，中的状态信息，再将其插入到就绪进程队列中再将其插入到就绪进程队列中阻塞与唤醒要匹配使用，以免造成阻塞与唤醒要匹配使用，以免造成“永久阻塞永久阻塞”425、进程挂起与激活、进程挂起与激活进程挂起进程挂起检查被挂进程的状态，改为相应的挂起状态检查被挂进程的状态，改为相应的挂起状态把进程的把进程的PCB复制到指定的区域复制到指定的区域最后，转向调度程序重新调度最后，转向调度程序重新调度进程激活进程激活先将进程从外存调入内存先将进程从外存调入内存检查该进程的现行状态，改为相应的活动状态检查该进程的现行状态，改为相应的活动状态根据优先级确定是否需要重新调度根据优先级确定是否需要重新调度(抢占调度？抢

21、占调度？)阻塞、唤醒一般由阻塞、唤醒一般由OS实现，而挂起与激活可由用户实现，而挂起与激活可由用户干预干预43第三节第三节进程互斥与同步进程互斥与同步基本概念基本概念临界区（临界段）临界区（临界段）信号量机制信号量机制信号量的应用信号量的应用44进程同步的主要任务进程同步的主要任务使并发执行的诸进程之间有效地共享资源和相互合作，从而使程序的执行具有可再现性。451、基本概念、基本概念两种形式的制约关系两种形式的制约关系直接相互制约：源于进程间的合作直接相互制约：源于进程间的合作间接相互制约：源于进程对资源的共享间接相互制约：源于进程对资源的共享进程同步进程同步合作完成同一个任务的多个进程，在执

22、行速度或某合作完成同一个任务的多个进程，在执行速度或某些时序点上必须相互协调的合作关系。些时序点上必须相互协调的合作关系。进程互斥进程互斥一个进程正在访问一个进程正在访问临界资源临界资源，另一个要访问该资源，另一个要访问该资源的进程必须等待。的进程必须等待。462、临界区（临界段）、临界区（临界段）临界资源临界资源一段时间内只允许一个进程访问的资源访问时，必须采用“互斥”方式47进程同步著名例子：生产者消费者问题48AB缓冲区要求：要求：不允许生产者A向已经满满的缓冲区放产品放产品不允许消费者B从空空的缓冲区拿产品拿产品模拟方法：缓冲区：数组 0,1,n-1，循环队列下一个产品应该放在什么位置

23、：in=0, ,n-1下一个产品应该从什么位置拿：out=0, ,n-1缓冲区里还有多少产品： counter=0, ,n49放一个新产品：in := (in + 1) mod n;拿走一个产品：out := (out + 1) mod n;什么时候缓冲区满了：counter = n什么时候缓冲区空了：counter = 050inout51上面的过程在并发执行时会出错上面的过程在并发执行时会出错原因：两者共享变量原因：两者共享变量counter机器语言描述：机器语言描述： mov ax, counter mov ax, counter mov bx, countermov bx, count

24、er inc ax inc ax dec bxdec bx mov counter, ax mov counter, ax movmov counter, bxcounter, bxcounter = 5counter = 5 生产者、消费者顺序执行一次，生产者、消费者顺序执行一次， 结果是结果是5 5交替执行时的情况：交替执行时的情况： mov ax, counter (ax = 5) mov ax, counter (ax = 5) inc ax (ax = 6)inc ax (ax = 6) mov bx, counter (bx = 5)mov bx, counter (bx = 5)

25、 dec bx (bx = 4) dec bx (bx = 4) mov counter, ax (counter = 6) mov counter, ax (counter = 6) movmov counter, bx (counter = 4) counter, bx (counter = 4) 结果是结果是4 452刚才的例子说明什么问题？刚才的例子说明什么问题？程序执行失去了再现性：结果可能是4或5或6解决思路解决思路把counter当作临界资源处理令两个程序互斥访问它53临界区临界区每个进程中访问临界资源的代码段如何实现互斥地访问临界资源：如何实现互斥地访问临界资源：保证各进程互斥

26、地进入（执行）自己的临界区，便可实现对临界资源的互斥访问。54上厕所问题临界资源的访问55解决方法解决方法进入临界区前，检查临界资源是否正在被使用/访问。两个步骤两个步骤没被使用，则设置“使用”标志，然后使用使用完了，设置“未用”标志，让别人可以使用56criticalsection;/临界区临界区repeatuntilfalse;entrysection /进入区进入区exitsection/退出区退出区remaindersection;/剩余区剩余区设变量S，标志counter是否正在被使用。生产者：生产者： 消费者：消费者： . . . . . .57while S=0 do no-op

27、;S := S - 1;while S=0 do no-op;S := S - 1;counter = counter + 1;counter = counter - 1;. . .S := S + 1;. . . . .S := S + 1;. . .并发执行的时候会出新问题！并发执行的时候会出新问题！由上可见，在程序中设置一个变量，用来标志另一个变量或资源是否被使用是行不通的。所以，OS需要提供一个专门的进程同步机制，来解决这个问题。58同步应遵循的规则同步应遵循的规则空闲让进空闲让进忙则等待忙则等待有限等待有限等待避免“死等”让权等待让权等待不能进入临界区时，立即释放处理机，避免“忙等”

28、。593、信号量机制、信号量机制卓有成效的进程同步工具提出提出1965. 荷兰 Dijkstra60Dijkstra经典语录编程的艺术就是处理复杂性的艺术。 简单是可靠的先决条件。1972年图灵奖演讲：优秀的程序员很清楚自己的能力是有限的，所以他对待编程任务的态度是完全谦卑的，特别是，他们会象逃避瘟疫那样逃避 “聪明的技巧”。计算机科学是应用数学最难的一个分支，所以如果你是一个蹩脚的数学家，最好留在原地，继续当你的数学家。1.实际上如果一个程序员先学了BASIC，那就很难教会他好的编程技术了：作为一个可能的程序员，他们的神经已经错乱了，而且无法康复。61(19302002)信号量的发展信号量的

29、发展整型信号量 记录型信号量 AND型信号量 信号量集基本思想基本思想使用信号量标记临界资源是否被使用注意注意检查和释放信号量的任务由OS完成应用程序中可调用相应的原语，以完成对信号量的检查和释放621 1、整型信号量、整型信号量基本思想基本思想改变整型变量S的值，以标记临界资源的使用情况信号量的值只能用wait(S)和signal(S)来访问S的初始值为1或更大。wait(S)、signal(S)是原子操作，执行时不可中断。原子操作，执行时不可中断。( (又被称作又被称作P P、V V操作操作) )63整型信号量机制的缺点整型信号量机制的缺点只要信号量S=0，就会不停地测试。因此，未遵循“让

30、权等待让权等待”准则“忙等忙等”。故而，引入故而，引入“记录型信号量机制记录型信号量机制”，避免，避免 “忙等忙等”现象。现象。642 2、记录型信号量、记录型信号量基本思想基本思想用一个整型变量value表示资源的数目，还用一个链表L将等待访问该资源的进程组成阻塞队列数据结构定义数据结构定义 type semaphore = record value : integer; /资源数目(资源信号量) L : List of process; /等待进程队列 end65l wait(S)wait(S)操作：操作： var S: semaphore; begin S.value := S.valu

31、e 1; / / 如果资源分配完毕，如果资源分配完毕， / / 自我阻塞自我阻塞, , 并进入并进入队列队列 / S.L/ S.L进行等待进行等待 if S.value0 then block(S.L); end;66lsignal (S)操作：操作： var S: semaphore; begin S.value := S.value + 1; /如果如果S.value=0, /表示仍有等待的进程，表示仍有等待的进程， /则唤醒一个则唤醒一个 if S.value=0 then wakeup(S.L); end;注意注意： S.value=1 and and Sn=1 then for i:

32、= 1 to n do Si := Si 1; end for else 将进程阻塞，放入第一个发现si=ti and and if Si=ti and and sn=tn thensn=tn then for i:=1 to n for i:=1 to n dodo Si := Si Si := Si di;di; end for; end for; else else 将进程阻塞，放入第一个发现si1)或互斥信号量(S=1)Swait(S,1,0) n特殊且有用的信号量功能类似于“开关”。nS=1时，允许多个进程执行某特定的代码。置S=0后，阻止任何程序执行该段代码。75信号量机制的用途一

33、般有两种信号量机制的用途一般有两种用于用于“互斥互斥”：多个进程互斥地访问共享资源：多个进程互斥地访问共享资源用于用于“协调协调”：协调进程间的执行次序：协调进程间的执行次序 （实现进程间的协调，即实现前驱关系）（实现进程间的协调，即实现前驱关系）764、信号量的应用、信号量的应用1 1、利用信号量实现进程互斥、利用信号量实现进程互斥如何让多个进程互斥访问一个临界资源？方法方法设一个信号量mutex ，令其初始值为1(互斥信号量) ，用它控制进程的访问。将各进程访问临界资源的代码放入wait(mutex)和signal(mutex)之间。7778wait(mutex);signal(mutex

34、);临界区：使用临界区：使用/访问临界访问临界资源资源(共享变量共享变量)的代码的代码Var mutex:semaphore := 1; /定义信号量定义信号量 repeatUntil false;repeatwait(mutex);signal(mutex);临界区：使用临界区：使用/访问临界访问临界资源资源(共享变量共享变量)的代码的代码Until false;注意：注意：利用信号量实现进程互斥时，wait、signal 一般要成对出现缺少缺少wait：导致系统混乱。缺少缺少signal：使阻塞进程无法被唤醒。2 2、利用信号量实现进程访问有限数量的共享资源、利用信号量实现进程访问有限数量

35、的共享资源如果共享资源的数量有限（设1），如何控制多个进程对它们的访问？方法方法设一个信号量mutex ，令其初始值等于共享资源的数量 ，用它控制进程的访问。将各进程访问共享资源的代码放入wait(mutex)和signal(mutex)之间。7980wait(mutex);signal(mutex);使用使用/访问共享访问共享资源资源(共享变量共享变量)的代码的代码Var mutex:semaphore := 资源数量资源数量; /定义信号量定义信号量 repeatUntil false;repeatwait(mutex);signal(mutex);使用使用/访问共享访问共享资源资源(共享

36、变量共享变量)的代码的代码Until false; 注意事项与使用互斥信号量时相同注意事项与使用互斥信号量时相同3 3、利用信号量实现前趋关系、利用信号量实现前趋关系n例例1 1：设并发执行的两个进程：设并发执行的两个进程P1P1、P2P2 P1：S1; P2：S2; 要求：要求：S1在S2之前执行 81 P1：S1; P2：wait(mutex); signal(mutex); S2;82S1S2方法：方法：设置信号量 mutex=0 (why?)前驱图：前驱图：mutexn例例2 2：利用信号量实现语句间的前趋关系：利用信号量实现语句间的前趋关系83S1S3S2S4S5S6abcdfgeV

37、ar a,b,c,d,e,f,g:semaphore := 0,0,0,0,0,0,0;begin S1; signal(a); signal(b); end;begin wait(a); S2; signal(c); signal(d); end;begin wait(b); S3; signal(e); end;begin wait(c);S4; signal(f); end;begin wait(d); S5; signal(g); end;begin wait(e); wait(f); wait(g); S6; end;信号量小结信号量小结信号量分类：信号量分类：互斥的信号量：它的互斥

38、的信号量：它的wait、signal在在同一同一个进程中个进程中同步的信号量：它的同步的信号量：它的wait、signal在在不同不同的进程中的进程中信号量的意义：信号量的意义：S0：S表示可用资源的个数表示可用资源的个数S=0：S表示无资源，无等待进程表示无资源，无等待进程S=1，说明还允许新读者，则将L减1，并继续执行下一步否则，说明已有RN个读者在读，则阻塞并等待Var L,mxVar L,mx：semaphoresemaphore：=RN,1;=RN,1;读者进程：读者进程：beginbegin repeat repeat swait (L,1,1); swait (L,1,1); s

39、wait (mx,1,swait (mx,1,0 0); ); 读操作读操作; ; ssignal (L,1); ssignal (L,1); until false; until false;end;end;如果已有一个写者在写，则有mx=0如果已有至少一个读者在读，则有LRN存在以上两种情况之一时，本写者阻塞并等待否则表示，没有其他写者在写，并且没有读者在读，则置mx=0，并继续下一步注：该句只检查是否有读者在读，并不修改L的值103写者进程：写者进程：begin repeat swait (mx,1,1,L,RN,0); 写操作写操作; ssignal (mx,1); until fal

40、se;end; 检查是否有写者在写 (只检查,不修改mx的值)第五节第五节 管程机制管程机制 管程的基本概念管程的基本概念 管程应用分析管程应用分析1041、管程的基本概念、管程的基本概念采用信号量同步机制编写并发程序，对于信号量的采用信号量同步机制编写并发程序，对于信号量的操作将被分散于各个进程中。操作将被分散于各个进程中。缺点：缺点：易读性差，不利于修改和维护，正确性难以易读性差，不利于修改和维护，正确性难以保证保证管程的产生管程的产生1971，Dijkstra：“秘书秘书”进程进程1973，Hansan：管程：管程105管程定义管程定义一个数据结构数据结构和能被并发进程所执行的一一组操作

41、组操作(操作这些数据结构)，这组操作能使进程同步进程同步，还可改变管程中的数据改变管程中的数据管程的基本思想管程的基本思想封装 (类似面向对象)管程的组成管程的组成管程里的共享变量对该共享变量进行操作的过程(函数)数据初始化106107l 管程的特点管程的特点封装性封装性内部的共享变量在管程外不可见内部的共享变量在管程外不可见内部过程内部过程(函数函数)只能访问内部的共享变量只能访问内部的共享变量互斥互斥各进程必须互斥进入管程各进程必须互斥进入管程阻塞队列阻塞队列内部设有阻塞队列，以及相应的阻塞和唤醒内部设有阻塞队列，以及相应的阻塞和唤醒操作操作为实现进程同步,管程中使用wait、signal

42、为区分阻塞原因，管程中使用“条件变量”条件变量条件变量是一种特殊的数据类型是一种特殊的数据类型使用时类似如下的定义方法：使用时类似如下的定义方法： var c: condition var c: condition；对于条件变量可以执行对于条件变量可以执行waitwait和和signalsignal操作操作108109c.wait 将被阻塞的进程放入与条件变量将被阻塞的进程放入与条件变量c关联的阻塞队关联的阻塞队列中列中c.signal 唤醒与条件变量唤醒与条件变量c关联的阻塞队列中的第一个进关联的阻塞队列中的第一个进程，如果没有被阻塞的，它不做任何操作程，如果没有被阻塞的，它不做任何操作注：

43、这与信号量机制中的注：这与信号量机制中的wait和和signal有所不同有所不同条件变量的使用条件变量的使用1102、管程应用分析、管程应用分析生产者生产者-消费者问题消费者问题l在管程里定义两个过程(函数)put(item) l生产者利用它向缓冲区放一个产品get(item) l消费者利用它从缓冲区取一个产品l利用整型变量count标记缓冲区中产品的数量lcount=n时，生产者需等待定义管程如下定义管程如下type pc = monitor var in,out,count:integer; buffer:array0,n-1 of item; notfull,notempty : con

44、dition; procedure put(item) begin if count=n then notfull.wait; bufferin:=item; in :=(in + 1) mod n; count := count + 1; if notempty.queue then notempty.signal; end;111l缓冲区已满，缓冲区已满，把进程阻塞到把进程阻塞到“等待投放产品等待投放产品”的的阻塞阻塞队列队列中中l如果如果“等待消等待消费费”队列中还有队列中还有被阻塞的进程，被阻塞的进程，就从中唤醒一个就从中唤醒一个l定义两个条件定义两个条件变量变量lnotfull：表示

45、：表示“缓冲区不满缓冲区不满”，即可以投，即可以投放产品的条件放产品的条件lnotempty：表：表示示“缓冲区不缓冲区不空空”，即可以，即可以取产品的条件取产品的条件 procedure get(item) begin if count=0 then notempty.wait; item := bufferout; out := (out + 1) mod n; count := count 1; if notfull.queue then notfull.signal; end; begin in := out := 0; count:=0; end;end type;112 初始化数据

46、l生产者生产者 begin repeat 生产一个item; pc.put (item); until false; end;l消费者消费者 begin repeat pc.get(item); 消费掉产品item; until false; end;113第六节第六节进程通信进程通信进程通信的概念进程通信的概念进程通信的类型进程通信的类型消息传递通信的实现方法消息传递通信的实现方法消息传递系统实现中的若干问题消息传递系统实现中的若干问题消息缓冲队列通信机制消息缓冲队列通信机制1141、进程通信的概念、进程通信的概念进程通信进程通信，是指进程之间的信息交换，是指进程之间的信息交换低级通信低级通

47、信（互斥、同步）（互斥、同步）利用信号量机制实现进程间的数据传递利用信号量机制实现进程间的数据传递缺点：效率低；对用户不透明缺点：效率低；对用户不透明高级通信高级通信（进程通信）（进程通信）进程之间利用进程之间利用OS提供的一组通信命令，高效地提供的一组通信命令，高效地传送大量数据的信息交换方式传送大量数据的信息交换方式优点：高效，方便，简化了通信程序的设计优点：高效，方便，简化了通信程序的设计1152、进程通信的类型、进程通信的类型116高级通信机制的类型高级通信机制的类型共享存储器系统共享存储器系统管道通信系统管道通信系统消息传递系统消息传递系统共享存储器系统基于共享数据结构的通信方式进程

48、共享某些数据结构(如队列) 程序员必须负责同步管理所以低效低效，只适合传输少量数据传输少量数据基于共享存储区的通信方式属于高级通信方式划出一块共享存储区划出一块共享存储区，进程通过对存储区中数据的读写来通信117管道通信系统首创于UNIX系统管道是一个共享文件（pipe文件），用于连结一个发送进程和一个接收进程，以实现通信发送进程和接收进程利用管道进程通信管道机制还提供三个方面的协调能力互斥一个进程读/写管道，其他进程必须等待同步发送进程写入一定数量的数据后便阻塞，接收进程取走后再唤醒接收进程遇到空管道时，也阻塞确定对方都存在后，才进行通信118消息传递系统进程间交换的数据是有格式的，称为me

49、ssage（网络通信中，称为报文）OS提供了相应的通信命令有两种方式直接通信方式间接通信方式1193、消息传递通信的实现方法、消息传递通信的实现方法直接通信方式直接通信方式发送进程利用发送进程利用OS提供的发送原语，直接把消息发提供的发送原语，直接把消息发送给目标进程送给目标进程Send(Receiver,message)、Receive(Sender,message)利用直接通信原语，解决生产者消费者问题：利用直接通信原语，解决生产者消费者问题：生产者生产者消费者消费者120repeatproduceaniteminnextp;send(consumer,nextp);untilfalse;

50、repeatreceive(producer,nextc);consumeaniteminnextc;untilfalse;121间接通信方式间接通信方式l进程之间通过共享数据结构进程之间通过共享数据结构信箱信箱，以消息暂存，以消息暂存方式实现的通信方式实现的通信l操作原语操作原语l信箱的创建、撤消；消息的发送、接收信箱的创建、撤消；消息的发送、接收l信箱的创建和拥有者信箱的创建和拥有者lOS或用户（通信）进程或用户（通信）进程l信箱的种类信箱的种类l私用信箱、公用信箱、共享信箱私用信箱、公用信箱、共享信箱l利用信箱通信时，发送和接收进程之间的关系利用信箱通信时，发送和接收进程之间的关系l一对

51、一、多对一、一对多、多对多一对一、多对一、一对多、多对多4、消息缓冲队列通信机制、消息缓冲队列通信机制提出者：提出者：Hansan通过内存中的公用通过内存中的公用消息缓冲区消息缓冲区进行进程通信进行进程通信广泛应用于本地进程间通信发送原语发送原语send(receiver,a)a：发送区的地址：发送区的地址接收原语接收原语receive(b)b：接收区的地址：接收区的地址122123（1）消息缓冲区中的数据结构：）消息缓冲区中的数据结构：typemessagebuffer=recordsender；发送进程标识符发送进程标识符size；消息长度消息长度text；消息正文消息正文next；指向下

52、一个消息缓冲区的指针指向下一个消息缓冲区的指针end（2）PCB中有关通信的数据项：中有关通信的数据项：typePCB=recordmq；消息队列首指针消息队列首指针mutex；消息队列互斥信号量；消息队列互斥信号量sm；消息队列资源信号量消息队列资源信号量end124进程进程ASend(B，a)Sender=ASize=5Text=Hello发送区a进程进程BReceive(b)Sender=ASize=5Text=Hello接收区bmqmutexsmPCB(B)Sender=ASize=5Text=HelloNext=0第七节第七节 线程的基本概念线程的基本概念线程的基本概念线程的基本概念

53、线程间的同步和通信线程间的同步和通信内核支持线程和用户级线程内核支持线程和用户级线程线程控制线程控制1251、线程的引入、线程的引入进程（进程（6060年代）年代）目的目的使多个程序并发执行，提高资源利用率和系统吞吐量使多个程序并发执行，提高资源利用率和系统吞吐量定义定义在在OSOS中能中能拥有资源拥有资源和和独立运行独立运行的基本单位的基本单位局限性局限性创建、撤消与切换时空开销大，限制了并发程度的提高创建、撤消与切换时空开销大，限制了并发程度的提高线程（线程（8080年代）年代）目的目的减少并发时付出的时空开销，使系统具有更好的并发性减少并发时付出的时空开销，使系统具有更好的并发性基本思想

54、基本思想“轻装上阵轻装上阵”将进程的两个属性分离将进程的两个属性分离线程线程独立调度的基本单位，进程独立调度的基本单位，进程拥有资源的单位拥有资源的单位126127轻型实体轻型实体线程几乎不占资源线程几乎不占资源(TCB等等)独立调度的基本单位独立调度的基本单位切换迅速且开销小切换迅速且开销小可并发执行可并发执行共享进程的资源共享进程的资源同一进程内的线程共享进程的资源同一进程内的线程共享进程的资源可以创建、撤销另一个线程可以创建、撤销另一个线程2、线程的属性、线程的属性FlashGetFlashGet中的线程中的线程1283、线程的状态、线程的状态每个线程都利用每个线程都利用TCB和一组状态

55、参数进行描述和一组状态参数进行描述状态参数状态参数寄存器状态、堆栈、运行状态、优先级寄存器状态、堆栈、运行状态、优先级运行状态运行状态就绪状态、执行状态、阻塞状态就绪状态、执行状态、阻塞状态1291304、线程的创建和终止、线程的创建和终止l 在多线程在多线程OS环境下，应用程序启动后，通常仅环境下，应用程序启动后，通常仅有一个线程在执行，称为有一个线程在执行，称为“初始化线程初始化线程”，它可，它可创建新线程。创建新线程。l 终止线程的方式有两种终止线程的方式有两种 线程完成自己的工作后主动退出线程完成自己的工作后主动退出 运行中出现错误，或由于某种原因，而被其它运行中出现错误，或由于某种原

56、因，而被其它线程强行终止线程强行终止1315、多线程、多线程OS中的进程中的进程l 多线程多线程OS中的中的进程进程有以下属性有以下属性进程不是一个可执行的实体，而是作为资进程不是一个可执行的实体，而是作为资源分配的单位源分配的单位可包括多个线程可包括多个线程互斥锁功能类似互斥信号量条件变量通常与互斥锁一起使用，以防止单纯使用互斥锁时产生死锁信号量机制私用信号量同一进程内线程同步公用信号量不同进程间或不同进程中线程的同步1326、线程间的同步、线程间的同步线程和进程的区别与联系线程和进程的区别与联系调度调度线程是调度的基本单位线程是调度的基本单位进程是资源拥有的基本单位进程是资源拥有的基本单位

57、拥有资源拥有资源线程不拥有系统资源，但可以访问其隶属进程的系统资源，从而获得线程不拥有系统资源，但可以访问其隶属进程的系统资源，从而获得系统资源系统资源并发性并发性支持多线程的支持多线程的OS中，不仅不同进程的线程之间可以并发，同一进程内中，不仅不同进程的线程之间可以并发，同一进程内的线程之间也可并发的线程之间也可并发系统开销系统开销进程切换时的时空开销大进程切换时的时空开销大线程切换时，只需保存和设置少量信息，因此开销很小线程切换时，只需保存和设置少量信息，因此开销很小1331347、内核支持线程和用户级线程、内核支持线程和用户级线程l 不同的不同的OS实现线程的方式不同实现线程的方式不同内

58、核支持线程内核支持线程线程的控制由内核完成，内核设立线程的控制由内核完成，内核设立TCB以控制线程以控制线程线程是调度的单位线程是调度的单位注：分时系统中，包含线程多的进程，运行的时间相对注：分时系统中，包含线程多的进程，运行的时间相对多多用户级线程用户级线程仅存在用户空间中，仅存在用户空间中，不需内核直接参与不需内核直接参与控制，切换更快控制，切换更快进程仍是调度的单位进程仍是调度的单位注：分时系统中，包含线程多的进程，每个线程运行的注：分时系统中，包含线程多的进程，每个线程运行的时间相对少时间相对少135用户级线程的实现用户级线程的实现运行时系统运行时系统(RuntimeSystem)用于

59、管理和控制线程的函数用于管理和控制线程的函数(过程过程)的集合的集合包括创建和撤消线程的函数、包括创建和撤消线程的函数、线程同步和通信的函数、线程同步和通信的函数、实现线程调度的函数等实现线程调度的函数等所有函数都驻留在用户空间，并作为用户级线程与内所有函数都驻留在用户空间，并作为用户级线程与内核之间的接口核之间的接口正因为有这些函数，才能使用户级线程与内核无关正因为有这些函数，才能使用户级线程与内核无关136内核控制线程内核控制线程又称为又称为LWP（轻型进程）（轻型进程）有自己的数据结构，如线程标识符、优先级、有自己的数据结构，如线程标识符、优先级、状态等状态等每个进程可拥有多个每个进程可

60、拥有多个LWP，它们共享进程所拥有的资，它们共享进程所拥有的资源源可通过系统调用获得内核提供的服务可通过系统调用获得内核提供的服务只要将用户级线程连接到一个只要将用户级线程连接到一个LWP上，该线程便具有上，该线程便具有了内核支持线程的所有属性了内核支持线程的所有属性137利用利用LWP作为中间系统作为中间系统任务任务1任务任务2任务任务3用户级线程LWP内核线程CPU小结(1)进程的概念和定义前驱图如何画前驱图如何画进程的特征进程的基本状态及转换进程的基本状态及转换PCBPCB的作用的作用进程、程序的联系与区别进程、程序的联系与区别138小结(2)进程的创建、撤销、终止进程同步、信号量、临界