【文档说明】计算机操作系统第三版第2章课件.ppt，共(119)页，644.291 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-76767.html

以下为本文档部分文字说明：

计算机操作系统第三版第2章2.1进程的基本概念2.1.1程序的顺序执行及其特征1.程序的顺序执行仅当前一操作(程序段)执行完后，才能执行后继操作。例如，在进行计算时，总须先输入用户的程序和数据，然后进行计算，最后才能打印计算结果。S1:

a∶=x+y;S2:b∶=a-5;S3:c∶=b+1;•图2-1程序的顺序执行(a)程序的顺序执行(b)三条语句的顺序执行I1C1P1I2C2P2S1S2S3•2.程序顺序执行时的特征(1)顺序性：(2)(2)封闭性：(3)(3)可再现性：•2.1.2

前趋图前趋图(PrecedenceGraph)是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。图中的每个结点可用于描述一个程序段或进程，乃至一条

语句；结点间的有向边则用于表示两个结点之间存在的偏序(PartialOrder)或前趋关系(PrecedenceRelation)“→”。→={(Pi,Pj)|PimustcompletebeforePjmaystart},如果(Pi,Pj)∈→,

可写成Pi→Pj，称Pi是Pj的直接前趋，而称Pj是Pi的直接后继。在前趋图中，把没有前趋的结点称为初始结点(InitialNode)，把没有后继的结点称为终止结点(FinalNode)。•每个结点还具有一个重量(Weight)，用于表示该结点

所含有的程序量或结点的执行时间。Ii→Ci→Pi和S1→S2→S3图2-2前趋图P1P3P8P9P4P2P5P6P7S1S2S3(a)具有九个结点的前趋图(b)具有循环的前趋图•对于图2-2(a)所示的前趋图，存在下述前趋关系：P1→P2,P1→P3,P1→P4,P2

→P5,P3→P5,P4→P6,P4→P7,P5→P8,P6→P8,P7→P9,P8→P9P={P1,P2,P3,P4,P5,P6,P7,P8,P9}→={(P1,P2),(P1,P3),(P1,P4),(P

2,P5),(P3,P5),(P4,P6),(P4,P7),(P5,P8),(P6,P8),(P7,P9),(P8,P9)}应当注意，前趋图中必须不存在循环，但在图2-2(b)中却有着S2→S3,S3→S2•2.1.3程序的并发执行及其特征1.程序的并发

执行图2-3并发执行时的前趋图P1P2P3P4I1I2I3I4C1C2C3C4•Ii→Ci，Ii→Ii+1,Ci→Pi,Ci→Ci+1，Pi→Pi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+

1之间，可以并发执行。S1:a∶=x+2S2:b∶=y+4S3:c∶=a+bS4:d∶=c+b•图2-4四条语句的前趋关系S1S2S3S4•2.程序并发执行时的特征1)间断性2)2)失去封闭性3)3)不可再现性例如，有两个循环程序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,0。(2)N∶

=N+1在Print(N)和N∶=0之后，此时得到的N值分别为n,0,1。(3)N∶=N+1在Print(N)和N∶=0之间，此时得到的N值分别为n,n+1,0。•2.1.4进程的特征与状态1.进程的特征和定义1)结构特征2)2)动态性:生命周期3)3)并

发性4)4)5)5)异步性：不可预知•(1)进程是程序的一次执行。(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。(3)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。在引入了进程实体的概念后，

我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。•2.进程的三种基本状态1)就绪(Ready)状态2)2)3)3)阻塞状态•图2-5进程的三种基本状态及其转换就绪阻塞执行时间片完进程调度I/O完

成I/O请求•3.1)引入挂起状态的原因(1)终端用户的请求。(2)(2)父进程请求。(3)(3)负荷调节的需要。(4)(4)操作系统的需要。•2)进程状态的转换(1)活动就绪→静止就绪。(2)(2)活动阻塞→静止阻塞。

(3)(3)静止就绪→活动就绪。(4)(4)静止阻塞→活动阻塞。•图2-6具有挂起状态的进程状态图活动就绪静止就绪执行挂起激活释放挂起活动阻塞静止阻塞挂起激活释放请求I/O•2.1.5进程控制块1.进程控制块的作用进程控制块的作用是使一

个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。•2.进程控制块中的信息1)进程标识符

用于惟一地标识一个进程。一个进程通常(1)内部标识符。在所有的操作系统中，都为每一个进程赋予一个惟一的数字标识符，它通常是一个进程的序号。设置内部标识符主要是为了方便系统使用。(2)外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(

进程)在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。•2)处理机状态信息主要是由处理机的各种寄存器中的内容组成的。①通用寄存

器，又称为用户可视寄存器，它们是用户程序可以访问的，用于暂存信息，在大多数处理机中，有8~32个通用寄存器，在RISC结构的计算机中可超过100个；②指令计数器，其中存放了要访问的下一条指令的地址；③程序状态字P

SW，其中含有状态信息，如条件码、执行方式、中断屏蔽标志等；④用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过程和系统调用参数及调用地址。栈指针指向该栈的栈顶。•3)在PCB中还存放一些与进程调度和进程对换有关的信息，包括：①

进程状态，指明进程的当前状态，作为进程调度和对换时的依据；②进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；③进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；

④事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。•4)进程控制信息包括：①程序和数据的地址，是指进程的程序和数据所在的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；②进程同步和通信机制，指实现进程同步和进程通信时必需的机制，如消息队列指针、

信号量等，它们可能全部或部分地放在PCB中；③资源清单，是一张列出了除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单；④链接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。•3.进程控制块的组织方式1)链接方式图2-7PCB链接队列示意图P

CB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901执行指针就绪队列指针阻塞队列指针空闲队列指针…•2)索引方式图2-8按索引方式组织PCB执行指针就绪索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就绪表指针阻塞表指

针•2.2进程控制2.2.1进程的创建1.进程图(ProcessGraph)图2-9进程树DEFGHBCIJKLMA•2.引起创建进程的事件(1)用户登录。(2)(2)作业调度。(3)(3)提供服务。(4)(4)应用请求。•3.进程的创建(CreationofProgr

ess)(1)申请空白PCB。(2)为新进程分配资源。(3)初始化进程控制块。(4)将新进程插入就绪队列，如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列。•2.2.2进程的终止1.引起进程终止(TerminationofProcess)1)在任何计算机系统中，都应有一个用

于表示进程已经运行完成的指示。例如，在批处理系统中，通常在程序的最后安排一条Holt指令或终止的系统调用。当程序运行到Holt指令时，将产生一个中断，去通知OS本进程已经完成。在分时系统中，用户可利用Logsoff去表示进

程运行完毕，此时同样可产生一个中断，去通知OS进程已运行完毕。•2)在进程运行期间，由于出现某些错误和故障而迫使进程终止。这类异常事件很多，常见的有：①越界错误。这是指程序所访问的存储区，已越出该进程的区域；②保护错。进程试图去访问一个不允许访问的

资源或文件，或者以不适当的方式进行访问，例如，进程试图去写一个只读文件；③非法指令。程序试图去执行一条不存在的指令。出现该错误的原因，可能是程序错误地转移到数据区，把数据当成了指令；④特权指令错。用户进程试图去执行一条只允许OS执行的指令；⑤运行超时。进程的执行时间超过了指定的最大值；

⑥等待超时。进程等待某事件的时间，超过了规定的最大值；⑦算术运算错。进程试图去执行一个被禁止的运算，例如，被0除；⑧I/O故障。这是指在I/O过程中发生了错误等。•3)外界干预并非指在本进程运行中出现了异常事件，而是指进程应外界的请求而终

止运行。这些干预有：①操作员或操作系统干预。由于某种原因，例如，发生了死锁，由操作员或操作系统终止该进程；②父进程请求。由于父进程具有终止自己的任何子孙进程的权利，因而当父进程提出请求时，系统将终止该进程；③父进程终止。当父进

程终止时，OS也将他的所有子孙进程终止。•2.(1)根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。(2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新

进行调度。(3)若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。(4)将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。(5)将被终止进程(它的PCB)从所在队列(或链

表)中移出，等待其他程序来搜集信息。•2.2.3进程的阻塞与唤醒1.引起进程阻塞和唤醒的事件1)请求系统服务：服务未满足2)2)启动某种操作：典型I/O操作3)3)4)4)•2.正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。可见，进

程的阻塞是进程自身的一种主动行为。进入block过程后，由于此时该进程还处于执行状态，所以应先立即停止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则

应将本进程插入到具有相同事件的阻塞(等待)队列。最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。•3.当被阻塞进程所期待的事件出现时，如I/O完成或

其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup()，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中

的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。•2.2.4进程的挂起与激活1.当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起，系统将利用挂起原语suspend()将指定进程或处于阻塞状态的进程挂起。挂起原语的执

行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最

后，若被挂起的进程正在执行，则转向调度程序重新调度。•2.进程的激活过程当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静

止就绪状态的进程换入内存。这时，系统将利用激活原语active()将指定进程激活。激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重

新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。•2.3进程同步2.3.1进程同步的基本概念1.两种形式的制约关系(1)间接相互制约关系：共享(2)(2)直接相互制

约关系：合作完成•2.临界资源(CriticalResouce)生产者-消费者(producer-consumer)问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进

程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步

，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。•我们可利用一个数组来表示上述的具有n个(0，1，…，n-1)缓冲区的缓冲池。用输入指针in来指示下一个可投放产品的缓冲区，每当生产者

进程生产并投放一个产品后，输入指针加1；用一个输出指针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1。由于这里的缓冲池是组织成循环缓冲的，故应把输入指针加1表示成in∶=(in+1)modn；输出指针加1表示成out∶=(out+1)modn。当(in

+1)modn=out时表示缓冲池满；而in=out则表示缓冲池空。此外，还引入了一个整型变量counter,其初始值为0。每当生产者进程向缓冲池中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时，使coun

ter减1。生产者和消费者两进程共享下面的变量：•Varn,integer;typeitem=…;varbuffer:array［0,1,…,n-1］ofitem;in,out:0,1,…,n-1;counter:0,1,…,n;指针i

n和out初始化为1。在生产者和消费者进程的描述中，no-op是一条空操作指令，whileconditiondono-op语句表示重复的测试条件(condication)，重复测试应进行到该条件变为false(假)，即到该条件不成立时为止。在生产者进程中使

用一局部变量nextp，用于暂时存放每次刚生产出来的产品；而在消费者进程中，则使用一个局部变量nextc,用于存放每次要消费的产品。•producer:repeat…produceaniteminnextp;…whilecounter=ndono-op;buffer［in∶=nextp;

in∶=in+1modn;counter∶=counter+1;untilfalse;consumer:repeatwhilecounter=0dono-op;nextc∶=buffer［out］;out∶=(out+1)m

odn;counter∶=counter-1;consumertheiteminnextc;untilfalse;•虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行时其结果也会是正确的，但若并发执行时，就会出现差

错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：register1∶=counter;register2∶=counter

;register1∶=register1+1;register2∶=register2-1;counter∶=register1;counter∶=register2;•假设：counter的当前值是5。如果生产者进程先执行左列的三条机器语言语句，然后消费者进程再执行右列的三条语

句，则最后共享变量counter的值仍为5；反之，如果让消费者进程先执行右列的三条语句，然后再让生产者进程执行左列的三条语句，counter值也还是5，但是，如果按下述顺序执行：register1∶=counter

;(register1=5)register1∶=register1+1;(register1=6)register2∶=counter;(register2=5)register2∶=register2-1;(register2=4)counter∶=regi

ster1;(counter=6)counter∶=register2;(counter=4)•3.临界区(criticalsection)repeatcriticalsection;remaindersec

tion;untilfalse;entrysectionexitsection•4.同步机制应遵循的规则(1)空闲让进。(2)(2)忙则等待。(3)(3)有限等待：有限时间(4)(4)让权等待：不能忙等•2.3.2信号量机制1.最初由Dijkstra把整型信号量定义为一个整型量

，除初始化外，仅能通过两个标准的原子操作(AtomicOperation)wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。wait和signalwait(S):whileS≤0dono-opS∶=S-

1;signal(S):S∶=S+1;•2.记录型信号量在整型信号量机制中的wait操作，只要是信号量S≤0，就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是使进程处于“忙等”的状态。记录型信号量机制，则是一种不存在“忙等”现象的进程同步机制。但在采取了“

让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表L，用于链接上述的所有等待进程。记录型信号量是由于它采用了记录型的数据结构而得名的

。它所包含的上述两个数据项可描述为：•typesemaphore=recordvalue:integer;L:listofprocess;end相应地，wait(S)和signal(S)procedurewait(S)varS:semaphore;beginS.value∶=S

.value-1;ifS.value＜0thenblock(S.L)endproceduresignal(S)varS:semaphore;beginS.value∶=S.value+1;ifS.value≤0thenwakeup(S.L);end•在记录型信号量机制中，S.val

ue的初值表示系统中某类资源的数目，因而又称为资源信号量，对它的每次wait操作，意味着进程请求一个单位的该类资源，因此描述为S.value∶=S.value-1；当S.value＜0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插

入到信号量链表S.L中。可见，该机制遵循了“让权等待”准则。此时S.value的绝对值表示在该信号量链表中已阻塞进程的数目。对信号量的每次signal操作，表示执行进程释放一个单位资源，故S.value∶=S.value+1操作表示资源数目加1。若加1后仍是S.value≤0，则表示在该信

号量链表中，仍有等待该资源的进程被阻塞，故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒。如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。•3.AND型信号量在两个进程中都要包含两个对Dmutex和Emutex的操作，

即processA:processB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);若进程A和B按下述次序交替执行waitprocessA:wait(Dmutex);于是Dmutex=0pro

cessB:wait(Emutex);于是Emutex=0processA:wait(Emutex);于是Emutex=-1AprocessB:wait(Dmutex);于是Dmutex=-1B阻塞•AND同步机制的基本思想是：将进程在整个

运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要

么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。为此，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait(Simultaneouswait)定义如下：•Swait(S1,S2,…,Sn)

ifSi≥1and…andSn≥1thenfori∶=1tondoSi∶=Si-1;endforelseplacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwi

thSi＜1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendifSsignal(S1,S2,…,Sn)fori∶=1tondoSi=Si+1;Removeallthe

processwaitinginthequeueassociatedwithSiintothereadyqueue.endfor;•4.信号量集Swait(S1,t1,d1,…,Sn,tn,dn)ifSi≥t1and…andSn≥tnthenfori∶=1tondoS

i∶=Si-di;endforelsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi＜tiandsetitsprogramcountertothebeginningofthe

SwaitOperation.endifsignal(S1,d1,…,Sn,dn)fori∶=1tondoSi∶=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintotheread

yqueueendfor;•一般“信号量集”(1)Swait(S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。(2)Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S＞1时)或互斥信号

量(S=1时)。(3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S≥1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。•2.3.3信号量的应用1.利用信号量实现进程互斥Varmute

x:semaphore∶=1;beginparbeginprocess1:beginrepeatwait(mutex);criticalsectionsignal(mutex);remainderseetionuntilfalse;•endprocess2:beginrepeatwait

(mutex);criticalsectionsignal(mutex);remaindersectionuntilfalse;endparend•2.利用信号量实现前趋关系图2-10前趋图举例S4S5S3S1S6S2•Vara,b,c,d

,e,f,g;semaphore∶=0,0,0,0,0,0,0;beginparbeginbeginS1;signal(a);signal(b);end;beginwait(a);S2;signal(c);signal(d);end;beginwait(b);S

3;signal(e);end;beginwait(c);S4;signal(f);end;beginwait(d);S5;signal(g);end;beginwait(e);wait(f);wait(g);S6;end;parend

end•2.3.4管程机制2.4.1管程的基本概念1.管程的定义管程由三部分组成：①局部于管程的共享变量说明；②对该数据结构进行操作的一组过程；③对局部于管程的数据设置初始值的语句。此外，还须为管程赋予一个名字。•图2-11管程的示意图共享数据…一组操作过程初

始化代码进入队列条件(不忙)队列•typemonitor-name=monitorvariabledeclarationsprocedureentryP1(…);begin…end;procedureentryP2(…);begin…end;…procedureentryPn(…);begi

n…end;begininitializationcode;end•2.条件变量管程中对每个条件变量，都须予以说明，其形式为：Varx,y:condition。该变量应置于wait和signal之前，即可表

示为X.wait和X.signal。例如，由于共享数据被占用而使调用进程等待，该条件变量的形式为：nonbusy:condition。此时，wait原语应改为nonbusy.wait，相应地，sign

al应改为nonbusy.signal。应当指出，X.signal操作的作用，是重新启动一个被阻塞的进程，但如果没有被阻塞的进程，则X.signal操作不产生任何后果。这与信号量机制中的signal操作不同。因为，后者总是要执行s∶=s+1操作，因而总会改变信号量的状态

。•如果有进程Q处于阻塞状态，当进程P执行了X.signal操作后，怎样决定由哪个进行执行，哪个等待，可采用(1)P等待，直至Q离开管程或等待另一条件。(2)Q等待，直至P离开管程或等待另一条件。采用哪种处理方式，当然是各执

一词。但是Hansan却采用了第一种处理方式。•2.4经典进程的同步问题2.4.1生产者—前面我们已经对生产者—消费者问题(Theproceducer-consumerproblem)做了一些描述，但未考虑进程的互斥与同步问题，因而造成了数据Counter的不定性。由于生产者—消费者问题

是相互合作的进程关系的一种抽象，例如，在输入时，输入进程是生产者，计算进程是消费者；而在输出时，则计算进程是生产者，而打印进程是消费者，因此，该问题有很大的代表性及实用价值。•1.利用记录型信号量解决生产者—消费者问题假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，这时可利用互斥

信号量mutex实现诸进程对缓冲池的互斥使用；利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。对生产者—消费者问题可描述如下：•Varmut

ex,empty,full:semaphore∶=1,n,0;buffer:array［0,…,n-1］ofitem;in,out:integer∶=0,0;beginparbeginproceducer:beginrepeat…producerani

temnextp;…wait(empty);wait(mutex);buffer(in)∶=nextp;in∶=(in+1)modn;signal(mutex);signal(full);untilfalse;end•consumer:beginrepeatwait(full);wait(mu

tex);nextc∶=buffer(out);out∶=(out+1)modn;signal(mutex);signal(empty);consumertheiteminnextc;untilfalse;endparendend•在生产者—消费者问题中应注意：首先，在每个程序中用于实现互斥

的wait(mutex)和signal(mutex)必须成对地出现；其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。例如，wait(empty)在计算进程中，而signal(empty)则

在打印进程中，计算进程若因执行wait(empty)而阻塞，则以后将由打印进程将它唤醒；最后，在每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wa

it操作，否则可能引起进程死锁。•2.利用AND信号量解决生产者—消费者问题armutex,empty,full:semaphore∶=1,n,0;buffer:array［0,…,n-1］ofitem;inout:integer∶=0,0;beginparbeginproducer:be

ginrepeat…produceaniteminnextp;…Swait(empty,mutex);buffer(in)∶=nextp;in∶=(in+1)modn;Ssignal(mutex,full);untilfalse;end•consumer:beginrepeatS

wait(full,mutex);nextc∶=buffer(out);out∶=(out+1)modn;Ssignal(mutex,empty);consumertheiteminnextc;untilfalse;endpa

rendend•2.4.2哲学家进餐问题1.经分析可知，放在桌子上的筷子是临界资源，在一段时间内只允许一位哲学家使用。为了实现对筷子的互斥使用，可以用一个信号量表示一只筷子，由这五个信号量构成信号量数组。Varchopstick:array

［0,…,4］ofsemaphore;•所有信号量均被初始化为1，第i位哲学家的活动可描述为：repeatwait(chopstick［i］);wait(chopstick［(i+1)mod5］);…eat;…signal(chopstic

k［i］);signal(chopstick［(i+1)mod5］);…think;untilfalse;•死锁产生后，(1)至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在

用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。(2)仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。(3)规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相

反。按此规定，将是1、2号哲学家竞争1号筷子；3、4号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。•2.利用AND信号量机制解决哲学家进

餐问题在哲学家进餐问题中，要求每个哲学家先获得两个临界资源(筷子)后方能进餐，这在本质上就是前面所介绍的AND同步问题，故用AND信号量机制可获得最简洁的解法。Varchopsiickarray［0,…,4］ofsemaphore∶=(1,1,1,1,1);processirepeatthink;

Sswait(chopstick［(i+1)mod5］,chopstick［i］);eat;Ssignat(chopstick［(i+1)mod5］,chopstick［i］);untilfalse;•2.4.3读者-写者问题1

.利用记录型信号量解决读者-写者问题为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。另外，再设置一个整型变量Readcount表示正在读的进程数目。由于只要有一个Reader进程在读，便不允许Writer进程去写。因此，仅当Re

adcount=0,表示尚无Reader进程在读时，Reader进程才需要执行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader进程便可去读，相应地，做Readcount+1操作。同理，仅当Reader进程在执行了Readcoun

t减1操作后其值为0时，才须执行signal(Wmutex)操作，以便让Writer进程写。又因为Readcount是一个可被多个Reader进程访问的临界资源，因此，应该为它设置一个互斥信号量rmutex。•读者-Varrmutex,wmutex:semapho

re∶=1,1;Readcount:integer∶=0;beginparbeginReader:beginrepeatwait(rmutex);ifreadcount=0thenwait(wmutex);Read

count∶=Readcount+1;signal(rmutex);…performreadoperation;…•wait(rmutex);readcount∶=readcount-1;ifreadcount=0thensignal(wmu

tex);signal(rmutex);untilfalse;endwriter:beginrepeatwait(wmutex);performwriteoperation;signal(wmutex);untilfalse;endparendend•2.利用信号量集机制解决

读者-写者问题VarRNinteger;L,mx:semaphore∶=RN,1;beginparbeginreader:beginrepeatSwait(L,1,1);Swait(mx,1,0);…p

erformreadoperation;…•Ssignal(L,1);untilfalse;endwriter:beginrepeatSwait(mx,1,1;L,RN,0);performwriteope

ration;Ssignal(mx,1);untilfalse;endparendend•2.5进程通信2.5.1进程通信的类型1.共享存储器系统(Shared-MemorySystem)(1)基于共享数据结构的通信方式。(2)(2)基于共享存储区的通信方式。•

2.消息传递系统(Messagepassingsystem)不论是单机系统、多机系统，还是计算机网络，消息传递机制都是用得最广泛的一种进程间通信的机制。在消息传递系统中，进程间的数据交换，是以格式化的消

息(message)为单位的；在计算机网络中，又把message称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。操作系统隐藏了通信的实现细节，大大减化了通信程序编制的复杂性，而获得广泛的应用。消息传递系统的通信方式属于高级通信方式。又因其实现方式的不同而进一步分成直接通信方式和

间接通信方式两种。•3.管道(Pipe)所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)，以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)，则从管道中接收(读)数据。由

于发送进程和接收进程是利用管道进行通信的，故又称为管道通信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到许多其它操作系统中。•为了协调双方的通信，管道机制必须提供以下三方面的协调能

力：①互斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。②同步，指当写(输入)进程把一定数量(如4KB)的数据写入pipe，便去睡眠等待，直到读(输出)进程取走数据后，再把他唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。③确定对

方是否存在，只有确定了对方已存在时，才能进行通信。•2.5.2消息传递通信的实现方法1.这是指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。通常，系统提供下述两条通信命令(原语)Send(Receiver,mes

sage);发送一个消息给接收进程；Receive(Sender,message);接收Sender例如，原语Send(P2,m1)表示将消息m1发送给接收进程P2;而原语Receive(P1，m1)则表示接收由P1发来的消息m1

。•在某些情况下，接收进程可与多个发送进程通信，因此，它不可能事先指定发送进程。例如，用于提供打印服务的进程，它可以接收来自任何一个进程的“打印请求”消息。对于这样的应用，在接收进程接收消息的原语中的源进程参数，是完成通信后的返回值，接收原语可表示为：Rec

eive(id,message);•我们还可以利用直接通信原语，来解决生产者-消费者问题。当生产者生产出一个产品(消息)后，便用Send原语将消息发送给消费者进程；而消费者进程则利用Receive原语来得到一个消息。如果消息尚未生产出来

，消费者必须等待，直至生产者进程将消息发送过来。生产者-消费者的通信过程可分别描述如下：repeat…produceaniteminnextp;…send(consumer,nextp);untilfalse;repeatreceive(producer,

nextc);…consumetheiteminnextc;untilfalse;•2.间接通信方式(1)信箱的创建和撤消。进程可利用信箱创建原语来建立一个新信箱。创建者进程应给出信箱名字、信箱属性(公用、私用或共享)

；对于共享信箱，还应给出共享者的名字。当进程不再需要读信箱时，可用信箱撤消原语将之撤消。(2)消息的发送和接收。当进程之间要利用信箱进行通信时，必须使用共享信箱，并利用系统提供的下述通信原语进行通信。Send(mailbox,message);Receive(mailbox,

message);从指定信箱中接收一个消息；•信箱可由操作系统创建，也可由用户进程创建，创建者是信箱的拥有者。据此，可把信箱分为以下三类。1)用户进程可为自己建立一个新信箱，并作为该进程的一部分。信箱的拥有者有权从信箱中读取消息，其

他用户则只能将自己构成的消息发送到该信箱中。这种私用信箱可采用单向通信链路的信箱来实现。当拥有该信箱的进程结束时，信箱也随之消失。•2)它由操作系统创建，并提供给系统中的所有核准进程使用。核准进程既可把消息发送到该信箱中，也可从信箱中读取发送给自己的消息。显然，公用信箱应采

用双向通信链路的信箱来实现。通常，公用信箱在系统运行期间始终存在。3)它由某进程创建，在创建时或创建后，指明它是可共享的，同时须指出共享进程(用户)的名字。信箱的拥有者和共享者，都有权从信箱中取走发送给自己的消息。•在利用信箱通信时，在发送进程和接收进程之间，存在以(1)

一对一关系。这时可为发送进程和接收进程建立一条两者专用的通信链路，使两者之间的交互不受其他进程的干扰。(2)多对一关系。允许提供服务的进程与多个用户进程之间进行交互，也称为客户/服务器交互(client/serverinteraction)。(3)一对多关系。

允许一个发送进程与多个接收进程进行交互，使发送进程可用广播方式，向接收者(多个)发送消息。(4)多对多关系。允许建立一个公用信箱，让多个进程都能向信箱中投递消息；也可从信箱中取走属于自己的消息。•2.5.3消息传递系统实现中的若干问题1.通信链路(communic

ationlink)为使在发送进程和接收进程之间能进行通信，必须在两者之间建立一条通信链路。有两种方式建立通信链路。第一种方式是：由发送进程在通信之前，用显式的“建立连接”命令(原语)请求系统为之建立一条通信链路；在链路使用完后，也用显式方式拆

除链路。这种方式主要用于计算机网络中。第二种方式是发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令(原语)，系统会自动地为之建立一条链路。这种方式主要用于单机系统中。•根据通信链路的连接方法，又可把通

信链路分为两类：①点—点连接通信链路，这时的一条链路只连接两个结点(进程)；②多点连接链路，指用一条链路连接多个(n＞2)结点(进程)。而根据通信方式的不同，则又可把链路分成两种：①单向通信链路，只允许发送进程向接收进程发送消息；②双向链

路，既允许由进程A向进程B发送消息，也允许进程B同时向进程A发送消息。•2.消息的格式在某些OS中，消息是采用比较短的定长消息格式，这减少了对消息的处理和存储开销。这种方式可用于办公自动化系统中，为用户提供快速的便笺式通信；但这对要发送较长消息的用户是不方便的。在有的OS中，

采用另一种变长的消息格式，即进程所发送消息的长度是可变的。系统在处理和存储变长消息时，须付出更多的开销，但方便了用户。这两种消息格式各有其优缺点，故在很多系统(包括计算机网络)中，是同时都用的。•3.进程同步方式(1)发送进程阻塞

、接收进程阻塞。(2)(2)发送进程不阻塞、接收进程阻塞。(3)(3)发送进程和接收进程均不阻塞。•2.5.4消息缓冲队列通信机制(本地进程之间）1.消息缓冲队列通信机制中的数据结构(1)消息缓冲区。在消息缓冲队列通信

方式中，主要利用的数据结构是消息缓冲区。typemessagebuffer=recordsender;size;text;next;end•(2)PCB中有关通信的数据项。在利用消息缓冲队列通信机制时，在设置消息缓冲队列的同时，还应增加用于对消息队

列进行操作和实现同步的信号量，并将它们置入进程的PCB中。在PCBtypeprocesscontrolblock=record…mq;mutex;sm;…end•2.发送进程在利用发送原语发送消息之前，应先在自己的内存空间，设置一发送区a，见图2-12所示，把待发送的消息正文

、发送进程标识符、消息长度等信息填入其中，然后调用发送原语，把消息发送给目标(接收)进程。发送原语首先根据发送区a中所设置的消息长度a.size来申请一缓冲区i，接着，把发送区a中的信息复制到缓冲区i中。为了能将i挂在接收进

程的消息队列mq上，应先获得接收进程的内部标识符j，然后将i挂在j.mq上。由于该队列属于临界资源，故在执行insert操作的前后，都要执行wait和signal操作。•图2-12消息缓冲通信sender:Asize:5text:H

ellomqmutexsmsender:Asize:5text:Hellonext:0send(B,a)第一消息缓冲区sender:Asize:5text:Helloreceive(b)a发送区ab接收区b进程BPCB(B)进程A•proceduresend(

receiver,a)begingetbuf(a.size,i);根据a.sizei.sender∶=a.sender;将发送区a中的信息复制到消息缓冲区之中；i.size∶=a.size;i.text∶=a.text;i.next∶=0;getid(PCBset,rec

eiver.j);获得接收进程内部标识符；wait(j.mutex);insert(j.mq,i);signal(j.mutex);signal(j.sm);end•3.接收原语procedurereceive(b)beginj∶

=internalname;jwait(j.sm);wait(j.mutex);remove(j.mq,i);signal(j.mutex);b.sender∶=i.sender;将消息缓冲区i中的信息复制到接收区b;b.size∶=i.size;b.text∶

=i.text;end•2.7线程2.7.1线程的基本概念为使程序能并发执行，系统还必须进行以下的一系列操作。1)创建进程2)撤消进程3)•2.线程的属性(1)轻型实体。(2)(2)独立调度和分派的基本单位。(3)(3)可并发执行。(4)(4)共享进程资源。•3.(1)状态参数。在OS中的

每一个线程都可以利用线程标识符和一组状态参数进行描述。状态参数通常有这样几项：①寄存器状态，它包括程序计数器PC和堆栈指针中的内容；②堆栈，在堆栈中通常保存有局部变量和返回地址；③线程运行状态，用于描述

线程正处于何种运行状态；④优先级，描述线程执行的优先程度；⑤线程专有存储器，用于保存线程自己的局部变量拷贝；⑥信号屏蔽，即对某些信号加以屏蔽。•(2)线程运行状态。如同传统的进程一样，在各线程之间也存在着共享资源和相互合作的制

约关系，致使线程在运行时也具有间断性。相应地，线程在运行时，也具有下述三种基本状态：①执行状态，表示线程正获得处理机而运行；②就绪状态，指线程已具备了各种执行条件，一旦获得CPU便可执行的状态；③阻塞状态，指线程在

执行中因某事件而受阻，处于暂停执行时的状态。•4.在多线程OS环境下，应用程序在启动时，通常仅有一个线程在执行，该线程被人们称为“初始化线程”。它可根据需要再去创建若干个线程。在创建新线程时，需要利用一个线程创建函数(或系统调用)，并提供相应的参数，如指

向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。在线程创建函数执行完后，将返回一个线程标识符供以后使用。终止线程的方式有两种：一种是在线程完成了自己的工作后自愿退出；另一种是线程在运行中出现错误或由于某种原因而被其它线程强行终止。•5.多线程OS中的

进程在多线程OS中，进程是作为拥有系统资源的基本单位，通常的进程都包含多个线程并为它们提供资源，但此时的进程就不再作为一个执行的实体。多线程OS中的进程有以下属性：(1)作为系统资源分配的单位。(2)可包括多个线程。(3)进程不是一个可执

行的实体。•2.7.2线程间的同步和通信1.互斥锁(mutex)互斥锁是一种比较简单的、用于实现进程间对资源互斥访问的机制。由于操作互斥锁的时间和空间开锁都较低，因而较适合于高频度使用的关键共享数据和程序段。互斥锁可以有两种状态，即开锁(unlock)和关锁(lo

ck)状态。相应地，可用两条命令(函数)对互斥锁进行操作。其中的关锁lock操作用于将mutex关上，开锁操作unlock则用于打开mutex。•2.条件变量每一个条件变量通常都与一个互斥锁一起使用，亦即，在创建一个互斥锁时便联系着一个条件变量。单纯的互斥锁用于短期

锁定，主要是用来保证对临界区的互斥进入。而条件变量则用于线程的长期等待，直至所等待的资源成为可用的。线程首先对mutex执行关锁操作，若成功便进入临界区，然后查找用于描述资源状态的数据结构，以了解资源的情况。只要发现所需资源R正处于忙碌状态，线程便转为等待状态，并对mut

ex执行开锁操作后，等待该资源被释放；若资源处于空闲状态，表明线程可以使用该资源，于是将该资源设置为忙碌状态，再对mutex执行开锁操作。•下面给出了对上述资源的申请(左半部分)和释放(右半部分)操作的描述。L

ockmutexLockmutexcheckdatastructures;markresourceasfree;while(resourcebusy);unlockmutex;wait(conditionvariable);wakeup(c

onditionvariable);markresourceasbusy;unlockmutex;•3.信号量机制(1)私用信号量(privatesamephore)。当某线程需利用信号量来实现同一进程中各线程之间的同步

时，可调用创建信号量的命令来创建一私用信号量，其数据结构是存放在应用程序的地址空间中。私用信号量属于特定的进程所有，OS并不知道私用信号量的存在，因此，一旦发生私用信号量的占用者异常结束或正常结束，但并未释放该信号量所占有空间的情况时，系统将无法使

它恢复为0(空)，也不能将它传送给下一个请求它的线程。•(2)公用信号量(publicsemaphort)。公用信号量是为实现不同进程间或不同进程中各线程之间的同步而设置的。由于它有着一个公开的名字供所有的进程使用，故而把它称为公用信号量。其数据结构是存放在受保护的系统

存储区中，由OS为它分配空间并进行管理，故也称为系统信号量。如果信号量的占有者在结束时未释放该公用信号量，则OS会自动将该信号量空间回收，并通知下一进程。可见，公用信号量是一种比较安全的同步机制。•2.7.3内核支持线程和用户级线程1.内核支持线程这里所谓的内核支持线程，也都同样

是在内核的支持下运行的，即无论是用户进程中的线程，还是系统进程中的线程，他们的创建、撤消和切换等，也是依靠内核实现的。此外，在内核空间还为每一个内核支持线程设置了一个线程控制块，内核是根据该控制块而感知某线程的存在的，并对其加以控制。•2.用户级线程仅存在于用户空间中。对于这种线

程的创建、撤消、线程之间的同步与通信等功能，都无须利用系统调用来实现。对于用户级线程的切换，通常是发生在一个应用进程的诸多线程之间，这时，也同样无须内核的支持。由于切换的规则远比进程调度和切换的规则简单，因而使线程的切换速度特别快。可见，这种线程是与内核无关的。•2.7.4线程控制1.

内核支持线程的实现图2-13任务数据区空间PTDA进程资源TCB#1TCB#2TCB#3•2.用户级线程的实现1)运行时系统(RuntimeSystem)所谓“运行时系统”，实质上是用于管理和控制线程的函数(过程)的集合，其中包括用于创建和撤消线程的函

数、线程同步和通信的函数以及实现线程调度的函数等。正因为有这些函数，才能使用户级线程与内核无关。运行时系统中的所有函数都驻留在用户空间，并作为用户级线程与内核之间的接口。•2)这种线程又称为轻型进程LWP(LightWeightPro

cess)。每一个进程都可拥有多个LWP，同用户级线程一样，每个LWP都有自己的数据结构(如TCB)，其中包括线程标识符、优先级、状态，另外还有栈和局部存储区等。它们也可以共享进程所拥有的资源。LWP可通过系统

调用来获得内核提供的服务，这样，当一个用户级线程运行时，只要将它连接到一个LWP上，此时它便具有了内核支持线程的所有属性。•图2-14利用轻型进程作为中间系统用户级线程轻型进程内核CPU任务1任务2任务3内核线程•感谢聆听