操作系统OS02进程管理课件

1第二章进程管理重点：进程的定义、进程控制的基本概念。进程PCB的基本结构，作用及进程的状态转换。进程同步与互斥的基本概念和解决方法。几个经典的进程同步与互斥问题及算法。线程的基本概念及状态。难点：进程的同步与互斥1第二章进程管理重点：2第二章进程管理主要内容：2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.5管程机制2.6进程通信2.7线程2第二章进程管理主要内容：32.1.进程的基本概念2.1.1程序的顺序执行及其特征2.1.2前趋图2.1.3程序的并发执行及其特征2.1.4进程的特征与状态2.1.5进程控制块32.1.进程的基本概念2.1.1程序的顺序执行及其特征42.1.1

程序的顺序执行及特征1、程序的顺序执行

例1：数据计算时要经过I:输入操作C:计算操作P:打印操作:

例2：如下三条语句的执行

S1:a:=x+y;S2:b:=a-5;S3:c:=b+1;2、特征顺序性、封闭性、可再现性I1C1P1I2C2P2语句S1语句S2语句S342.1.1程序的顺序执行及特征1、程序的顺序执行I1C152.1.2

前趋图1、前趋图(PrecedenceGraph)一个有向无循环图描述进程之间执行的前后关系2、前趋关系“”={(Pi,Pj)|PimustcompletebeforePjmaystart}如果：(Pi,Pj)∈

，也可以写成：PiPj则称：Pi是Pj的直接前趋,Pj是Pi的直接后继初始结点：没有前趋终止结点：没有后继每个结点还具有一个权或重量(Weight)，表示该结点的程序量或执行时间。P1P2P3P1P2P3√×52.1.2前趋图1、前趋图(PrecedenceGra6其前趋关系表示为：P={P1，P2，P3，P4，P5，P6，P7}→={（P1,P2）,（P1,P3）,（P1,P4）,（P2,P5）,（P3,P5）,（P4,P6）,（P5,P7）,（P6,P7）}P1P4P3P2P6P5P7具有7个结点的前驱图6其前趋关系表示为：P1P4P3P2P6P5P7具有7个结点72.1.3

程序的并发执行及其特征I1C1P1I2C2P2I3C3P3I4C4P4输入程序计算程序打印程序1、在对一批程序进行处理时，可以并发执行。例1：输入、计算、打印三个程序对一批作业进行处理时存在前趋关系：前驱关系：Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+172.1.3程序的并发执行及其特征I1C1P1I2C2P282.1.3程序的并发执行及其特征例2：对于下述四条语句的程序段：S1：a:=x+2;S2：b:=y+4;S3：c:=a+b;S4：d:=c+b;S2S1S3S4前驱关系82.1.3程序的并发执行及其特征例2：对于下述四条语句的9又如：三个程序的执行顺序如图：

P1：a:=1P2：x:=a+1P3：y:=a+1

2.1.3程序的并发执行及其特征P1P2P3前驱关系9又如：三个程序的执行顺序如图：2.1.3程序的并发执行及10程序并发执行条件（Bernstein条件）将任一语句划分为两个变量的集合R(Si)和W(Si):

读集R(Si)={a1，a2，……，am}

写集W(Si)={b1，b2，……，bn}如对语句S1和S2有：

R(S1)∩W(S2)={Ф} W(S1)∩R(S2)={Φ} W(S1)∩W(S2)={Φ}成立，则语句S1和S2可并发执行。10程序并发执行条件（Bernstein条件）将任一语句划分11程序并发执行条件（Bernstein条件）例1．

语句c=a–b和w=c+1 R（c=a–b）={a,b} W（c=a–b）={c} R（w=c+1）={c} W（w=c+1）={w} R（w=c+1）∩W（c=a–b）={c}语句c=a–b和w=c+1不能并发执行。11程序并发执行条件（Bernstein条件）例1．

语句122、程序并发执行时的特征间断(异步)性：“执行—暂停—执行”，一个程序可能走到中途停下来，失去原有的时序关系。失去封闭性：共享资源，受其他程序的控制逻辑的影响。如：一个程序写到存储器中的数据可能被另一个程序修改，失去原有的不变特征。不可再现性：失去封闭性－>失去可再现性；外界环境在程序的两次执行期间发生变化，失去原有的可重复特征。122、程序并发执行时的特征间断(异步)性：“执行—暂停—执13程序并发执行时的不可再现性

例如:有两个循环程序A和B，共享一个变量N。程序A每执行一次时，都要做N:=N+1;程序B每执行一次时，都要执行print(N),然后将N置成0。程序A和B以不同的速度运行。可能出现的情况如下(某时刻变量N的值为n)：1、N:=N+1在print(N)和N:=0之前，2、N:=N+1在print(N)和N:=0之后，3、N:=N+1在print(N)和N:=0之间，得到的N值为n+1,n+1,0得到的N值为n,0,1得到的N值为n,n+1,013程序并发执行时的不可再现性例如:有两个循环程序A142.1.4进程的特征与状态进程的特征与定义进程的三种基本状态挂起状态创建状态和终止状态142.1.4进程的特征与状态进程的特征与定义15进程特征结构特性(PCB-ProcessControlBlock)进程实体＝程序段＋相关的数据段＋PCB动态性由创建而产生，由调度而执行，由撤销而消亡并发性独立性独立运行、独立分配资源、独立接受调度异步性15进程特征结构特性(PCB-ProcessControl16进程定义进程的典型定义：（1）进程是程序的一次执行（2）进程是一个程序及其数据在处理机上顺序执行时所发生的活动（3）进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。传统OS中进程定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。16进程定义进程的典型定义：17进程与程序的区别：（如同“演出”与“剧本”）进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。进程更能真实地描述并发执行，可以揭示OS的内部特征，而程序不能。进程是暂时的，程序是永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）；程序仅是代码的有序集合。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可涉及到多个程序的执行。进程具有创建其他进程的功能，父进程创建子进程而形成进程树，而程序不能。17进程与程序的区别：（如同“演出”与“剧本”）进程是动态的18进程的基本状态三种基本状态：就绪状态执行状态阻塞状态进程状态转换

阻塞状态就绪状态

执行状态调度I/O请求进程唤醒时间片到18进程的基本状态三种基本状态：进程状态转换阻塞就绪执行191920挂起状态引入挂起状态的原因：终端用户请求父进程请求:考查、修改或协调各子进程时；负荷调节的需要：缓和内存紧张的情况；操作系统的需要：改善系统运行性能，调节负荷；增加的状态：挂起状态（静止状态）非挂起状态（活动状态）20挂起状态引入挂起状态的原因：21具有挂起状态的进程状态图活动阻塞执行状态活动就绪静止就绪静止阻塞调度唤醒I/O请求激活激活挂起挂起挂起唤醒21具有挂起状态的进程状态图执行活动静止静止调度唤醒I/O请22创建状态和终止状态创建状态创建一个进程过程：为一个新进程创建PCB，并填写必要的管理信息把该进程转入就绪状态并插入就绪队列之中引入创建状态，为了保证进程的调度必须在创建工作完成后进行，以确保对进程控制块操作的完整性。

22创建状态和终止状态创建状态23创建状态和终止状态终止状态进程终止过程首先，等待操作系统进行善后处理然后，将其PCB清零，并将PCB空间返还系统当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其它有终止权的进程所终结，它将进入终止状态。23创建状态和终止状态终止状态24创建状态和终止状态时间片完许可释放进程调度I/O完成I/O请求创建终止就绪执行阻塞进程的五种基本状态及转换24创建状态和终止状态时间片完创建终止就绪执行阻塞进程的五种25创建状态和终止状态（续）激活许可挂起调度挂起释放释放I/O请求激活挂起静止就绪静止阻塞活动就绪执行活动阻塞创建终止许可具有创建、终止和挂起状态的进程状态图25创建状态和终止状态（续）262.1.5进程控制块（PCB）PCB的作用PCB中的信息PCB的组织方式262.1.5进程控制块（PCB）PCB的作用271.PCB的作用PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。是进程存在的唯一标志。作用：使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。PCB常驻内存，系统将所有的PCB组成若干链表或队列，存放在OS中专门开辟的PCB区内271.PCB的作用PCB中记录了操作系统所需的、用于描述进28

2.PCB中的信息进程标识符：唯一的标识一个进程内部标识（方便系统使用）外部标识（由创建者提供，由字母数字组成）处理机状态：由CPU的各种寄存器中的内容组成通用寄存器；指令计数器

；程序状态字PSW；用户栈指针进程控制信息pidstatusschedualcontrol处理机状态信息进程标识符进程调度信息282.PCB中的信息进程控制信息pidstatu29进程调度信息：

进程状态；进程优先级；其它信息；等待事件（阻塞原因）进程控制信息：

程序和数据的地址；同步和通信机制；资源清单；链接指针；进程控制信息pidstatusschedualcontrol处理机状态信息进程标识符进程调度信息2.PCB中的信息29进程调度信息：303.PCB的组织方式PCB数目一个系统中的PCB数目可为数十个、数百个甚至数千个链接方式把具有同一状态的PCB，用其链接字链接成一个队列就绪队列、若干个阻塞队列、空队列索引方式系统根据所有进程的状态建立相应的索引表就绪索引表、阻塞索引表等，索引表在内存的首地址记录在内存的一些专用单元中。303.PCB的组织方式PCB数目313、PCB的组织方式（续）执行指针就绪队列指针阻塞队列指针空闲队列指针PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB911……PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9……执行指针就绪队列指针阻塞队列指针3572496PCB链接队列示意图按索引方式组织PCB就绪索引表阻塞索引表313、PCB的组织方式（续）执行指针就绪队列指针阻塞队列32思考题1．如果系统中有N个进程，运行的进程最多几个，最少几个；就绪进程最多几个最少几个；等待进程最多几个，最少几个？[解答]：在单处理机系统中，处于运行状态的进程最多为1个，最少为0个；处于就绪进程最多为N-1个，最少为0个；处于等待的进程最多为N个，最少为0个。32思考题1．如果系统中有N个进程，运行的进程最多几个，最少33思考题2.有没有这样的状态转换，为什么？ 等待—运行；就绪—等待33思考题2.有没有这样的状态转换，为什么？342.2

进程控制主要内容：进程创建进程撤消进程阻塞进程唤醒进程挂起与激活342.2

进程控制主要内容：352.2

进程控制进程控制是对系统中所有进程从产生、存在到消亡的全过程实行有效的管理和控制。

进程控制一般是由操作系统的内核来实现，内核在执行操作时，往往是通过执行各种原语操作来实现的。

无——有——消亡

运行——等待就绪———等待等待唤醒创建撤消状态转换352.2

进程控制进程控制是对系统中所有进程从产生、存在36内核：加在硬件上的第一层软件，通过执行各种原语操作来实现各种控制和管理功能，具有创建进程、撤消进程、进程通信、资源管理的功能。原语(primitive)：由若干条指令构成的“原子操作(atomicoperation)”过程，作为一个整体而不可分割，要么全都完成，要么全都不做。原子操作在管态下执行，常驻内存。原语的作用：实现进程的通信和控制，系统对进程的控制如不使用原语，就会造成其状态的不确定性，从而达不到进程控制的目的。36内核：加在硬件上的第一层软件，通过执行各种原语操作来实现37处理机运行时的两种状态用户态（目态）时不可直接访问受保护的OS代码。核心态（管态）时执行OS代码，可以访问全部进程空间。裸机（硬件）内核客户进程客户进程进程服务器存储器服务器文件服务器请求应答核心态用户态37处理机运行时的两种状态用户态（目态）时不可直接访问受保护38进程树PDPBPEPCPFPAPIPHPGPJPKPLPMPN2.2.1进程的创建1、进程图是用于描述一个进程的家族关系的有向树。结点代表进程有向边代表父子关系进程之间的关系：父、子进程与祖先进程：PCB中设置家族关系表项继承归还资源：“父”创建“子”、“父”撤消“子”38进程树PDPBPEPCPFPAPIPHPGPJ392、引起创建（create）进程的事件用户登录（分时系统）作业调度（批处理系统）提供服务（操作系统提供服务）应用请求（由现有进程派生）392、引起创建（create）进程的事件用户登录（分时系统403、进程的创建(Creat()原语)过程：申请空白PCB、为新进程分配资源、初始化PCB、插入就绪进程队列HD就绪队列指针PCB15PCB2PCB3PCB4PCB513PCB60PCB7PCB89PCB912PCB10PCB11PCB1225PCB136……空PCB队列指针RAM程序+数据PCB80PCB68403、进程的创建(Creat()原语)过程：申请空白PCB412.2.2进程的终止1、引起进程终止事件正常结束（Holt指令，Logsoff）异常结束越界错误、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错、I/O故障外界干预操作员或操作系统干预父进程请求父进程终止412.2.2进程的终止1、引起进程终止事件422、进程的终止过程根据被终止的进程的标识符，检索出该进程的PCB，读出该进程的状态。若该进程处于执行状态，立即终止其执行，置调度方式为真，指示该进程终止后应重新进行调度。若该进程有子孙进程，终止其所有子孙进程。将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。将被终止进程的PCB从所在队列中删除。422、进程的终止过程根据被终止的进程的标识符，检索出该进程432.2.3进程的阻塞与唤醒1、引起进程阻塞和唤醒的事件请求系统服务启动某种操作新数据尚未到达无新工作可做432.2.3进程的阻塞与唤醒1、引起进程阻塞和唤醒的事件442、进程阻塞的过程进程调用阻塞原语block()把自己阻塞，阻塞是进程自身的一种主动性为。先停止进程的执行，将PCB中的现行状态由执行改为阻塞。并将其PCB插入具有相同事件的阻塞队列。转调度程序进行重新调度，将处理机分配给另一就绪进程，保留被阻塞进程的处理机状态。442、进程阻塞的过程进程调用阻塞原语block()把自己阻453、进程唤醒的过程期待事件出现，相关进程调用唤醒原语wakeup()把被阻塞的进程从等待该事件的阻塞队列中移出。将其PCB中的现行状态由阻塞改为就绪。将该PCB插入就绪队列。阻塞与唤醒要匹配使用，以免造成“永久阻塞”block()和wakeup()要成对出现453、进程唤醒的过程期待事件出现，相关进程调用唤醒原语wa462.2.4进程的挂起与激活调用挂起原语suspend()检查被挂起进程的状态，处于活动就绪，便改为静止就绪；处于活动阻塞，便改为静止阻塞；若进程正在执行，则转向调度程序。调用激活原语active()若进程在外存则将其调入内存，检查进程的状态，处于静止就绪，便改为活动就绪；处于静止阻塞，便改为活动阻塞。462.2.4进程的挂起与激活调用挂起原语suspend(472.3进程同步进程同步的主要任务：对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。主要内容：2.3.1进程同步的基本概念2.3.2信号量机制2.3.3信号量的应用472.3进程同步进程同步的主要任务：对多个相关进程在执行482.3.1进程同步的基本概念1、两种形式的制约关系：间接相互制约关系进程互斥：一个进程正在访问临界资源，另一个要访问该资源的进程必须等待。直接相互制约关系进程同步：合作完成同一个任务的多个进程，在执行速度或某些时序点上必须相互协调的合作关系。前进示例示例482.3.1进程同步的基本概念1、两种形式的制约关系：前49民航售票系统主机A窗口B窗口C窗口D窗口每个进程执行的操作：设x表示某航班的票数。

……ifx>0thenx:=x-1;……在某时刻x=1，有a、b两人分别去A、B窗口买票，分析售票情况：时间片到ab49民航售票系统主机A窗口B窗口C窗口D窗口每个进程执行的操50进程同步举例：司机－售票员司机：P1while(true){

启动车辆；正常运行；到站停车；

}售票员：P2while(true){

关门；售票；开门；

}正确运行过程While(true){（司机）启动车辆；（售票员）关门；（司机）正常运行；（售票员）售票；（司机）到站停车；（售票员）开门；}50进程同步举例：司机：P1售票员：P2正确运行过程512、临界资源临界资源：一次仅允许一个进程访问的资源称为临界资源（互斥资源或共享变量）。物理设备：打印机，扫描仪例1：两个进程A、B共享一台打印机，若不加以控制，两个进程的输出结果可能交织在一起，很难区分。软件资源：全局变量，队列等例2：飞机订票问题设：x代表某航班机座号，p1和p2两个售票进程，售票工作是对全局变量x加1。512、临界资源临界资源：一次仅允许一个进程访问的资源称为临52两个进程共享一个变量x时，两种可能的执行次序：

A：p1：r1:=x；r1:=r1+1；x:=r1；p2：

r2:=x；r2:=r2+1；x:=r2；B：P1：r1:=x;r1:=r1+1；x:=r1；p2：

r2:=x;r2:=r2+1;x:=r2；设x的初值为10，两种情况下的执行结果：情况A：

x=10+2

情况B：x=10+152两个进程共享一个变量x时，两种可能的执行次序53例3：生产者-消费者问题产品outin01n-1缓冲池in:=(in+1)modnout:=(out+1)modn53例3：生产者-消费者问题产品outin01n-1缓冲池i54例3：生产者-消费者问题缓冲池满：(in+1)modn=out缓冲池空：in=out引入整型变量：counter初值：0生产：counter

+1；消费：counter

-1。54例3：生产者-消费者问题缓冲池满：(in+1)mod55例3：生产者-消费者问题生产者消费者进程共享下面的变量：varn:integer;typeitem=…;varbuffer:array［0,1,…,n-1］ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;55例3：生产者-消费者问题生产者消费者进程共享下面的变量：56例3：生产者-消费者程序：producer:repeat…produceaniteminnextp;…whilecounter=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;untilfalse;consumer:repeatwhilecounter=0dono-op;nextc:=buffer[out];out:=(out+1)modn;counter:=counter-1;consumertheiteminnextc;untilfalse;56例3：生产者-消费者程序：producer:consu57例3：生产者-消费者程序机器语言实现：生产者：register1:=counter;register1:=register1+1;counter:=register1;假设counter的当前值为5；并发执行时按如下顺序执行：register1:=counter;register1:=register1+1;register2:=counter;register2:=register2-1;counter:=register1;counter:=register2;消费者：register2:=counter;register2:=register2-1;counter:=register2;(register1=5)(register1=6)(register2=5)(register2=4)(counter=6)(counter=4)程序的执行失去了再现性！思考：如何解决这个问题？57例3：生产者-消费者程序机器语言实现：生产者：假设cou58repeatuntilfalse临界区剩余区剩余区3、临界区（criticalsection）临界区：进程中访问临界资源的一段代码。进入区：在进入临界区之前，检查可否进入临界区的一段代码。如果可以进入临界区，设置相应“正在访问临界区”标志。退出区：用于将“正在访问临界区”标志清除。剩余区：代码中的其余部分。进入区退出区循环进程58repeatuntilfalse临界区剩余区剩余区3、593、临界区（续）

P1：

a:=a+1print(a)互斥P2：a:=a-1print(a)互斥P3：ifa<0thena:=a+1elsea:=a-1互斥程序中的临界区593、临界区（续）P1：互斥P2：a:=a-1互斥604、同步机制应遵循的规则为实现进程互斥地进入临界区，可用软件或专门的同步机构实来现同步机制。所有同步机制都应遵循四条准则：空闲让进：无进程处于临界区。忙则等待：已有进程处于其临界区。有限等待：等待进入临界区的进程不能“死等”。让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）。604、同步机制应遵循的规则为实现进程互斥地进入临界区，可用612.3.2信号量机制1965年，荷兰人Dijkstra首先提出信号量机制信号量（Semaphores）仅能被两个原语操作wait(S)-signal(S)修改的整型变量，表示一类资源的物理实体。信号量的值表示资源数量，只能由wait(S)和signal(S)原子操作改变。612.3.2信号量机制1965年，荷兰人Dijkstra622.3.2信号量机制信号量分类：互斥的信号量：它的wait(S)-signal(S)在同一个进程中同步的信号量：它的wait(S)-signal(S)在不同的进程中信号量机制包括：整型、记录型、AND型、信号量集机制。622.3.2信号量机制信号量分类：631.整型信号量S是一个整型量，除初始化外仅能通过2个原子操作wait(S)和signal(S)来访问。wait(S)和signal(S)长时间以来被称为P、V操作-荷兰语的proberen(test)和verhogen(increment)631.整型信号量S是一个整型量，除初始化外仅能通过2个原子641.整型信号量（续）P，V操作描述如下：VarS:int;procedure

P(S) whileS<=0dono-op；

S--; procedureV(S) S++; 缺点：若S<=0,则P操作会不断测试，不满足“让权等待”,即“忙等”。P操作，意味着请求分配一个单位资源Semaphore定义V操作，意味着释放一个单位资源641.整型信号量（续）P，V操作描述如下：P操作，意味着652.记录型信号量遵循“让权等待”准则。信号量包括一个代表资源数目的整型变量和一个进程链表。记录型可描述如下：typesemaphore=recordvalue:integer;L:listofprocess;end资源数目进程链表指针，链接所有等待进程652.记录型信号量遵循“让权等待”准则。信号量包括一个代662.记录型信号量（续）P，V操作描述如下：procedureP(S)varS:semaphore;beginS.value:=S.value-1;ifS.value<0thenblock(S.L)endprocedureV(S)varS:semaphore;beginS.value:=S.value+1;ifS.value<=0thenwakeup(S.L)end唤醒相应等待链表S.L中等待的第一个进程；改变其状态为就绪状态；并将其插入到就绪队列将该进程状态置为等待状态；并将该进程的PCB插入相应的等待链表S.L的末尾;662.记录型信号量（续）P，V操作描述如下：唤醒相应等待672.记录型信号量（小结）信号量S.value的物理意义：

S.value>0：S.value表示可用资源的个数S.value=0：表示无资源可用

S.value<0：|S.value|表示等待链表中进程的个数信号量的使用：必须置一次且只能置一次初值；初值不能为负数；只能执行PV操作。思考：信号量S.value初值为1，情况如何？672.记录型信号量（小结）信号量S.value的物理意义：683.AND型信号量问题：一个进程需要同时获取两个或多个临界资源，各进程分别获得部分临界资源，然后等待其余的临界资源，“各不相让”，产生死锁。适用于：同时需要多种资源且每种占用一个的信号量操作。基本思想：将进程在整个运行过程中需要的所有资源，一次性全部的分配给进程，待进程使用完后再一起释放。AND型信号量中P原语：SwaitAND型信号量中V原语：Ssignal683.AND型信号量问题：一个进程需要同时获取两个或多个693.AND型信号量（续）P，V操作描述如下：Swait(S1,S2,…,Sn)

if(S1>=1andS2>=1and…andSn>=1)thenfori:=1tondoSi:=Si-1;

endforelse将该进程放入第一个Si<1的Si等待队列，阻塞该进程;endif693.AND型信号量（续）P，V操作描述如下：703.AND型信号量（续）Ssignal(S1,S2,…,Sn)

fori:=1tondoSi:=Si+1; 从Si等待队列中取出所有进程，放入就绪队列;endfor703.AND型信号量（续）Ssignal(S1,S2,714.信号量集问题：一次需要N个某类临界资源时，就要进行N次P操作，低效又可能死锁。适用于：同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的处理。基本思想：在AND型信号量机制的基础上进行扩充，进程对信号量Si设下限值为ti（用于信号量的判断，即需满足Si>=ti，表示资源数量低于ti时，便不予分配），需求值为di（用于信号量的增减，即Si=Si–di或Si=Si+di）。714.信号量集问题：一次需要N个某类临界资源时，就要进行724.信号量集（续）P，V操作如下：Swait(S1,t1,d1,…,Sn,tn,dn)

if(S1>=t1and…andSn>=tn)thenfori:=1;tondo

Si:=Si-di; endforelse将该进程放入第一个Si<ti的Si等待队列，阻塞该进程;endifSsignal(S1,d1,…,Sn,dn)

fori:=1;tondo

Si:=Si+di;

从Si等待队列中取出所有进程，放入就绪队列;endfor724.信号量集（续）P，V操作如下：734.信号量集（小结）一般“信号量集”的几种特殊情况：Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配。Swait(S,1,1)表示一般的记录型信号量或互斥信号量。Swait(S,1,0)作为一个可控开关当S>=1时，允许多个进程进入临界区。当S=0时，禁止任何进程进入临界区。734.信号量集（小结）一般“信号量集”的几种特殊情况：74信号量机制总结：类型需求资源特点实现特点P:对于信号量S，当S<t时，不分配，否则一次分配d个资源；其中t为下限值；V:一次释放d个资源。AND型信号量机制的扩充多个某类资源，多类多个不同类资源，每类1个1个1个P:当S>0,S=S-1V:S=S+1忙等让权等待typesemaphore=recordvalue:integer;L:listofprocess;end将进程在整个运行过程中需要的所有资源，一次性全部地分配给进城，待进程使用完后再一起释放。防止产生死锁信号量集AND型信号量整型信号量记录型信号量74信号量机制总结：类型需求资源特点实现特点P:对于信号量S752.3.3信号量的应用1.利用信号量实现进程互斥例如：两个进程都使用一台打印机可描述如下：Varmutex:semaphore:=1;//定义信号量beginparbegin

process1;//进程1

process2;//进程2parendend752.3.3信号量的应用1.利用信号量实现进程互斥76例如：两个进程都使用一台打印机进程1：process1:begin repeat

wait(mutex);

使用打印机；

signal(mutex); remaindersectionuntilfalse;end//临界区//进入区//退出区返回76例如：两个进程都使用一台打印机process1:be77process2:beginrepeat

wait(mutex);

使用打印机；

signal(mutex);remaindersectionuntilfalse;end1.利用信号量实现进程互斥（续2）例如：两个进程都使用一台打印机进程2如下：//临界区//进入区//退出区返回77process2:begin1.利用信号量实现进程782.利用信号量实现前趋关系设有两个并发执行的进程P1，P2。P1中有语句S1，P2中有语句S2。要求在S1后执行S2。即：S1S2为实现这种前趋关系，使进程P1和P2一个共享的信号量S，初值S＝0。

PV描述：

在P1中：

在P2中：

S1；

wait(S)；

signal(S)；

S2；782.利用信号量实现前趋关系设有两个并发执行的进程P1，P79S2S1S3S4S5S6S1;

signal(a);signal(b);

wait(a);

S2;signal(c);signal(d);

wait(b);

S3;signal(e);wait(c);

S4;signal(f);wait(d);

S5;signal(g);wait(e);wait(f);wait(g);S6;

abcdefg每一对前趋关系用一个共享信号量表示，并赋初值0，设初值a,b,c,d,e,f,g:=0,0,0,0,0,0,0;语句执行顺序如下：S1S2S3S5S4S679S2S1S3S4S5S6S1;wait(a);wai80每一对前趋关系用一个共享信号量表示，并赋初值0，设初值a,b,c,d,e,f,g:=0,0,0,0,0,0,0;完整的程序如下：Vara,b,c,d,e,f,g:semaphore=0,0,0,0,0,0,0;begin parbegin beginS1；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;

parendend80每一对前趋关系用一个共享信号量表示，并赋初值0，设初值812.4经典进程的同步问题2.4.1生产者－消费者问题2.4.2哲学家进餐问题2.4.3读者－写者问题812.4经典进程的同步问题2.4.1生产者－消费者问题822.4.1生产者－消费者问题1.利用记录型信号量解决生产者－消费者问题公用信号量mutex：初值为1，用于实现临界区互斥。生产者私用信号量empty：初值为n，指示空缓冲块数目。消费者私用信号量full：初值为0，指示满缓冲块数目。整型量in和out初值均为0，in指示首空缓冲块序号，out指示首满缓冲块序号。822.4.1生产者－消费者问题1.利用记录型信号量解决生831.利用记录型信号量解决生产者－消费者问题Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,n-1]ofitem;in,out:integer:=0,0;begin parbegin

producer；

consumer；

parendendnext831.利用记录型信号量解决生产者－消费者问题Varmut841.利用记录型信号量解决生产者－消费者问题（生产者进程）producer:begin repeat produceanitemnextp;

wait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1)modn;

signal(mutex);signal(full);untilfalse;end顺序不能颠倒，否则死锁！return841.利用记录型信号量解决生产者－消费者问题（生产者进程）851.利用记录型信号量解决生产者－消费者问题（消费者进程）consumer:beginrepeat

wait(full); wait(mutex);

nextc:＝buffer(out);out:=(out+1)modn;

signal(mutex); signal(empty);consumetheiteminnextc;untilfalse;end顺序不能颠倒，否则死锁！return851.利用记录型信号量解决生产者－消费者问题（消费者进程）862.4.1生产者－消费者问题利用AND信号量解决生产者－消费者问题用SP(empty,mutex)来代替P(empty)和P(mutex)用SV(mutex,full)来代替V(mutex)和V(full)用SP(full,mutex)来代替P(full)和P(mutex)用SV(mutex,empty)来代替V(mutex)和V(empty)862.4.1生产者－消费者问题利用AND信号量解决生产者872.利用AND信号量解决生产者－消费者问题Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,n-1]ofitem;in,out:integer:=0,0;beginparbegin

producer；

consumer；parendendnext872.利用AND信号量解决生产者－消费者问题Varmut882.利用AND信号量解决生产者－消费者问题(生产者进程)producer:begin repeat produceanitemnextp;

Swait(empty,mutex); buffer(in):=nextp; in:=(in+1)modn;

Ssignal(mutex,full);untilfalse;endreturn882.利用AND信号量解决生产者－消费者问题(生产者进程)892.利用AND信号量解决生产者－消费者问题(消费者进程）consumer:begin;repeat

Swait(full,mutex);nextc:＝buffer(out);out:=(out+1)modn;

Ssignal(mutex,empty);consumetheiteminnextc;untilfalse;endreturn892.利用AND信号量解决生产者－消费者问题(消费者进程）902.4.2哲学家进餐问题问题描述有五位哲学家围坐一张圆桌进餐，圆桌上有五个盘子和五只筷子.哲学家的生活方式：交替的进行进餐和思考。进餐条件：拿取靠近他的左、右两只筷子方能进餐。902.4.2哲学家进餐问题问题描述911.利用记录型信号量解决哲学家进餐问题分析：筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。Varchopstick:array[0,…,4]ofsemaphore;911.利用记录型信号量解决哲学家进餐问题分析：筷子是临界资92所有的信号量初始化为1，第i位哲学家的活动描述为：repeat

P(chopstick[i]);

P(chopstick[(i+1)mod5]);eat;

V(chopstick[i]);

V(chopstick[(i+1)mod5]);think;untilfalse;分析：可能存在什么问题？92所有的信号量初始化为1，第i位哲学家的活动描述为：931.利用记录型信号量解决哲学家进餐问题五位哲学家同时拿起左边的筷子将会引起死锁。几种解决办法：至多只允许四位哲学家同时去拿左边的筷子。仅当哲学家的左右两只筷子均可用时，才允许拿起筷子进餐。规定奇数号的哲学家先拿左边的筷子，偶数的哲学家先拿右边的筷子。（作业）931.利用记录型信号量解决哲学家进餐问题五位哲学家同时拿起94至多只允许四位哲学家同时去拿左边的筷子第i位哲学家的活动描述：

while(true){

P(Sm)

P(chopstick[i]);

P(chopstick[(i+1)%5]); …… eating; ……

V(chopstick[i]);

V(chopstick[(i+1)%5]);

V(Sm) …… thinking;}//Sm限制同时进餐的人数，初值4，且Sm<=494至多只允许四位哲学家同时去拿左边的筷子第i位哲学家的活动952.利用AND信号量解决哲学家进餐问题要求每个哲学家同时获得两只筷子后才能进餐Varchopstick:array[0,…,4]ofsemaphore:=(1,1,1,1,1);processi//第i位哲学家的活动描述为：repeatthink;SP(chopstick[(i+1)mod5],chopstick[i]);eat;SV(chopstick[(i+1)mod5],chopstick[i]);untilfalse;952.利用AND信号量解决哲学家进餐问题要求每个哲学家同时962.4.3读者—写者问题有两组并发进程：读者、写者，共享一组数据区要求：允许多个读者同时执行读操作不允许读者、写者同时操作（读写互斥）不允许多个写者同时操作（只能一人写）962.4.3读者—写者问题有两组并发进程：读者、写者，共971.利用记录型信号量解决读者－写者问题实现写和读进程或者多个写进程互斥的信号量wmutex。正在读的进程数目readcount，初始化为0。readcount是可被多个读进程访问的临界资源，设置互斥信号量rmutex。971.利用记录型信号量解决读者－写者问题实现写和读进程或者981.利用记录型信号量解决读者－写者问题Varrmutex,wmutex:semaphore:=1,1;readcount:integer:=0;beginparbegin

Writer:begin

//写进程 …

end

Reader:begin//读进程 …

endparendend981.利用记录型信号量解决读者－写者问题Varrmute991.利用记录型信号量解决读者－写者问题Reader:begin//读进程repeat

readcount:=readcount+1;

reading;

readcount:=readcount-1

untilfalse;endP(rmutex);V(rmutex);P(rmutex);V(rmutex);ifreadcount=0then P(wmutex);ifreadcount=0then V(wmutex);991.利用记录型信号量解决读者－写者问题Reader:b1001.利用记录型信号量解决读者－写者问题

//写进程Writer:beginrepeatP(wmutex);writing;V(wmutex);untilfalse;end1001.利用记录型信号量解决读者－写者问题//写进程1012.利用信号量集机制解决读者－写者问题增加限制，只允许RN个读者同时读，引入一个信号量L，并赋初值RN。写互斥信号量mx。VarRNinteger;L,mx:semaphore:=RN,1;beginparbegin reader://读进程

writer://写进程parendend1012.利用信号量集机制解决读者－写者问题增加限制，只允许1022.利用信号量集机制解决读者－写者问题//读进程reader:beginrepeatSP(L,1,1);SP(mx,1,0);reading;SV(L,1);untilfalse;end1022.利用信号量集机制解决读者－写者问题//读进程1032.利用信号量集机制解决读者－写者问题//写进程writer:beginrepeatSP(mx,1,1;L,RN,0);writing;SV(mx,1);untilfalse;end1032.利用信号量集机制解决读者－写者问题//写进程104例1：进程同步问题有一个信箱只能存放一封信，只要信箱为空，进程A就不断产生信件并送入信箱，只要信箱中有信件，进程B就不断从信箱中取出信进行处理。初始时，信箱为空。试用P、V操作表达进程A、B之间的关系。分析：共享资源：信箱（状态：full/empty）；信号量：full，empty；初值：0，1。104例1：进程同步问题有一个信箱只能存放一封信，只要信箱为105例1：进程同步问题Varempty,full:semaphore=1,0;begin A:begin repeat

P(empty);

放一封信;

V(full); untilfalse;end

B:begin repeat

P(full);

取一封信; V(empty); untilfalse;endend105例1：进程同步问题Varempty,full:sem106例2：进程同步问题一个铁笼子，每次只能放入一个动物，猎人向笼子放入老虎，农民向笼子放入猪；动物园等待取笼中的老虎，饭店等待取笼中的猪。请用P、V操作写出能同步执行的程序。分析：进程：puttiger,putpig,gettiger,getpig;共享资源：笼子、老虎、猪；信号量：cage，tiger，pig；初值分别为：1，0，0。106例2：进程同步问题一个铁笼子，每次只能放入一个动物，猎107例2：进程同步问题Varcage,tiger,pig:semaphore=1,0,0;beginputtiger:begin//放老虎repeat

P(cage);

将老虎放入笼中;

V(tiger);untilfalse;endputpig:begin//放猪repeat

P(cage);

将猪放入笼中;

V(pig);untilfalse;end107例2：进程同步问题Varcage,tiger,pig108例2：进程同步问题(续)gettiger:begin//取老虎repeat

P(tiger);

从笼中取出老虎;

V(cage);untilfalse;end

getpig:begin//取猪repeat

P(pig);

从笼中取出猪;

V(cage);untilfalse;endend

108例2：进程同步问题(续)gettiger:begi1092.3.4管程机制管程的提出采用PV同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中。给系统管理带来麻烦，而且还会因同步操作的使用不当导致系统死锁。1092.3.4管程机制管程的提出110管程机制利用共享数据结构抽象地表示系统中的共享资源，而把对该共享数据实施的操作定义为一组过程，如资源的请求(request)和释放(release)过程。进程对共享资源的申请、释放和其他操作，都是通过这组过程对共享的数据结构的操作来实现的，这组过程还可以根据资源的情况，或接受或阻塞进程的访问，确保每次仅有一个进程使用共享资源，这样就可以统一管理对共享资源的所有访问，实现进程互斥。代表共享资源的数据结构，以及由该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块，我们称之为管程。110管程机制利用共享数据结构抽象地表示系统中的共享资源，而111管程的定义一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作,这组操作能同步进程和改变管程中的数据。这些数据及操作对进程是透明的，局部于管程的数据结构只能被该管程的过程访问。111管程的定义一个管程定义了一个数据结构和能为并发进程所执1121.管程的定义管程由四部分组成管程的名称。局限于管程的共享变量说明。对该数据结构进行操作的一组过程。对局部于管程的数据设置初始值的语句。variabledeclarationsprocedureinitializationcodemonitor注意：任何进程访问共享资源，只能通过调用管程中的过程（管程名.过程名）,而管程每次只允许一个进程进入管程，从而实现进程互斥1121.管程的定义管程由四部分组成variabledec113管程的语法描述：typemonitor-name=MONITOR；//名称<共享变量说明>；//共享变量define<(能被其他模块引用的)过程名列表>use<(要调用的本模块外定义的)过程名列表>

procedure<过程名>(<形式参数列表>);begin …. end; …一组过程function<函数名>(<形式参数列表>):值类型;begin … end;…begininitializationcode;变量初始化end