os课件第二章进程管理2.4-2

1、第二章 进程管理 Process Management 在传统的操作系统中，作为资源分配和独立运行的基本单位是进程。OS所具有的四大特征也都是基于进程而形成的。 本章主要内容 进程的基本概念 进程控制 进程同步 经典进程同步问题 管程机制 进程通信 线程2.4 经典进程同步问题 Classical process synchronization problem一、生产者-消费者问题(producer and consumer problem)1 问题描述：若干进程通过有限的共享缓冲区（缓冲池）交换数据。“生产者”进程不断将信息放入缓冲区;“消费者”进程不断从缓冲区中取出信息；共享缓冲区共有N个

2、；任何时刻只能有一个进程可对共享缓冲区进行操作。设缓冲池为循环存储结构供应方向使用方向主要考虑的问题： 缓冲区满或空； 竞争条件。注 意： 1）缓冲池不满就可放入，不空就可取出； 2）不允许消费者到空缓冲中取消息（判空，则阻塞）； 3）不允许生产者向满缓冲中放消息（判满，则阻塞）； 4）对缓冲池的操作要求互斥。 (2)(3)要求同步，需设置私有信号量: empty生产者进程的私用信号量（初值为n)； full消费者进程的私用信号量（初值为0） (4)要求互斥，设置公用信号量 mutex保证生产者进程和消费者进程之间的互斥（初值为1）。 2 执行过程：生产者消费者动画演示（1）生产者消费者动画演

3、示（2）生产者消费者动画演示（3）生产者消费者动画演示（4）produce(data)；Begin wait(empty); wait(mutex); 送数据入缓冲区单元 Signal(mutex)； Signal(full);End；consume(data)；Begin wait(full); Wait(mutex); 消费； signal(mutex); Signal(empty)；End；各生产者进程使用的过程produce (data)各消费者使用的过程consume (data)可描述如下：注：一般说来：singal原语是释放资源的，可以任意顺序出现，wait原语不然，如果次序混乱

4、将造成死锁。设有n个缓冲区，为实现对缓冲池的互斥操作：互斥信号量mutex；资源信号量empty表示空缓冲的个数，full表示满缓冲的个数； 定义数组buffer 表示缓冲区。 输入指针in指示下一个可放消息的缓冲区；输出指针out指示下一个可取消息的缓冲区。var mutex,empty,full：semaphore ：1，n，0； buffer：array0，n-1 of item; in , out : integer：=0，0；3 生产者消费者问题完整描述：parbegin producer:begin repeat producer an item in nextp; wait(em

5、pty); wait(mutex) ; buffer(in):=nextp; in:=(in+1) mod n; signal(mutex); signal(full) ; until false; endconsumer: begin repeat wait(full) ; wait(mutex); nextc:=buffer(out); out:=(out+1) mod n; signal(mutex); signal(empty); until false; endParend1）wait(mutex)和signal(mutex)必成对出现2）empty和full的wait和signal

6、操作也必成对出现，但是在不同的进程中。3）wait原语顺序不能颠倒，signal原语顺序可任意。思考： P82习题23、24 注 意：4 利用AND信号量解决parbegin producer:begin repeat producer an item in nextp; Swait(empty,mutex); buffer(in):=nextp; in:=(in+1) mod n; Ssignal(mutex,full);until false; endconsumer: begin repeat Swait(full,mutex) ; nextc:=buffer(out); out:=(o

7、ut+1) mod n; Ssignal(mutex,empty); until false; endParend1 问题描述二、哲学家进餐问题（Dining Philosopher Problem）？准备进餐进餐准备进餐进餐 五个哲学家，共用一张圆桌，五支筷子。 哲学家有两种状态：“思考”和“进餐”。 进餐时只能取靠近他的左右的筷子，而且拿到两支时才可进餐。完后，放下筷子继续思考。 基本工作：思考，进餐。 同步？ 互斥？ 临界资源为筷子。一只筷子(编号为i) 一个互斥信号量 可定义一个信号量数组来描述五支筷子。 var chopstick:array0.4 of semaphore 所有信号

8、量初值为1， 2 利用记录型信号量解决无有:=1, 1, 1, 1, 1;Var chopstick: array 0.4 of semaphore:=1, 1, 1, 1, 1; Begin Parbegin process i ( i=0, 1, 2, 3, 4): begin Repeat until false; end parendend哲学家进餐活动可描述为： Think； wait(chopsticki)； wait(chopsticki+1 mod 5)； eat ； signal(chopsticki； signal(chopsticki+1 mod 5)；此算法有无问题？“

9、Dead-Lock” 1) 规定在拿到左筷子后，先检查右筷子是否可用。若不可 用，则先放下左筷子，等一段时间再重复整个过程。 但该方法可能出现“饥饿”现象哲学家进餐“死锁”问题解决方法 2）至多允许四个人同时进餐，保证至少一个能进餐。 设一个信号量v，初值为4。 3）规定奇数号人先拿左筷子，后拿右筷子；偶数号人先拿右筷子，后拿左筷子。五个哲学家都先竞争奇数号筷子，获得后再竞争偶数号筷子。最后总有一个哲学家能获得两只筷子。0123401234 4）用AND信号量机制可获得最简洁解法。var chopstick:array 0,4 of semaphore:=(1,1,1,1,1);process

10、 i repeat think; Swait(chopstick(i+1) mod 5,chopsticki); eat; Ssignal(chopstick(i+1) mod 5,chopsticki); until false; 哲学家问题对于多个竞争进程互斥地访问有限资源(如I/O设备)这一类问题的建模十分有用。 3 用AND信号量机制解决1 问题描述： 一个数据对象被多个进程共享。其中有些进程要求读，另一些进程要求写或修改。要求读的进程称为“reader进程”；其它的称为“writer进程”。允许多个reader进程同时执行；不允许一个writer进程和其它reader进程或write

11、r进程同时访问共享对象。 a、多个reader可同时访问这组共享数据并发； b、多个writer不可同时访问这组共享数据互斥； c、reader与writer不可同时访问这组共享数据互斥 它为数据库访问建立了一个模型。 三、读者-写者问题（Reader/Writer Problem）r1r2rnwRreadcount信号量设置 Wmutex：W/R和W/W的互斥。 Rmutex：读者对readcount的互斥操作。控制变量设置：Readcount 记录读的个数。来一个读者：2 操作过程：申请Rmutex若readcount=0申请Wmutexreadcount+1 读操作释放Rmutex走一个

12、读者：申请Rmutexreadcount1若readcount=0释放Wmutex释放Rmutexvar rmutex,wmutex:semaphore:=1,1 readcount:integer:=0;Parbegin reader: begin wait(rmutex) if readcount=0 then wait(wmutex) readcount:=readcount+1 signal(rmutex) 读操作 wait(rmutex) readcount:=readcount-1 if readcount=0 then signal(wmutex) signal(rmutex)e

13、ndwriter:begin wait(wmutex) 写操作 signal(wmutex) EndParend 读者写者问题描述问？若一个Writer进程正在写，则Reader进程和其他Writer进程的状态和所执行到的位置？本算法为读者优先算法，即当读者进行读时，写者必须等待，直到所有读者均离开，写者才能进入。存在的问题是什么？写者优先：如果一个读者申请进行读操作时已有另一写者在等待访问共享资源，则该读者必须等到没有写者处于等待状态后才能开始读操作。存在的问题是什么？公平策略：规则1：在一个读序列中，若有写者等待，则不允许新来读者开始执行。2：一个写操作结束时，所有等待读者应比下一写者有更

14、高优先权。问：对于该公平策略，应如何予以解决呢？var RN integer; L,mx:semaphore:=RN,1; begin parbegin reader: begin repeat Swait(L,1,1)； Swait(mx,1,0); perform read operation Ssignal(L,1); until false; endwriter:begin repeat Swait(mx,1,1;L,RN,0);perform write operation Ssignal(mx,1);until false;endparendend 信号量集机制解决读者写者问题四、

15、打瞌睡的理发师问题 理发店里有一位理发师，一把理发椅和N把供等候理发的顾客坐的椅子； 理发师为理发椅上的顾客理发，没有顾客就在理发椅上睡觉； 第一个顾客到来，他必须先唤醒理发师； 如果顾客来时理发师正在忙，若有空椅子，则坐下来等；否则离开。1 问题描述：说 明：理发师和每位顾客都分别是一个进程。理发师：看是否有顾客，若没有，在理发椅上睡觉；否则，为等待最久的顾客服务，等待人数减1。顾客：先看有无空座位(等候的顾客数是否少于椅子数)，若有则等，等待人数加1；若理发师正瞌睡，则将其唤醒；否则，离开。理发师和顾客的关系？变量waiting，用于记录等候的顾客数，初值为0。由于它不是信号量，因此可对其

16、进行增减等操作。设顾客座椅数（chairs）为常量5。同 步# define CHAIRS 5 /*为等待的顾客准备的椅子数*/semaphore customers=0; /*等待服务的顾客数*/ semaphore barbers=0; /*等待顾客的理发师数*/ semaphore mutex=1; /*用于互斥*/ int waiting=0; /*等待的顾客(还没理发的)*/ 三个信号量Customers：用来记录等候理发的顾客数(不包括正在理发的顾客)，初值为0；Barbers：等候顾客的理发师数，初值为0；Mutex：用于对waiting 变量的互斥。信号量设置和变量定义Void

17、 customers(void) wait(mutex); /*互斥进入临界区*/ If(waiting0 表示有S个资源可用S=0 表示无资源可用S0 则| S |表示S等待队列中的进程个数P(S): 表示申请一个资源 V(S)： 表示释放一个资源。信号量的初值应该大于等于01 信号量的物理含义：当为互斥操作时，它们同处于同一进程;当为同步操作时，则不在同一进程中出现;如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前；而两个V操作的顺序无关紧要。2 P.V操作必须成对出现:优点： 简单，而且表达能力强（用P.V

18、操作可解决任何同步互斥问题）。缺点： 不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂。3 P.V操作的优缺点2.5 管程机制 Monitor Mechanism 集中管理分散在进程中的临界段。 1971年，Dijkstra提出，为每一临界资源设置一个“秘书”进程。访问该临界资源的进程都需先报告“秘书”，由“秘书”实现诸进程的同步。Hoare(1974)和Hansen(1975)，根据抽象数据类型的原理发展为管程（Monitors）。 把并发进程间的共享资源和操作，集中于相应的管程中。 管程与信号量机制功能等价，且更容易控制。一、管程的定义（The definition

19、of monitor）1 定义：Hansan “代表共享资源的数据结构及并发进程在其上执行的一组操作就构成管程。这组操作能同步进程和改变管程中的数据”。2.5.1 管程的基本概念The basic concepts of monitor 2 基本思想：把共享资源以及针对共享资源的所有操作集中在一个模块中，可以函数库的形式实现。被请求和释放资源的进程所调用。 1) 管程名称； 2) 局部于管程的共享变量说明(临界资源描述)； 3) 对该数据结构进行操作的一组过程（即对临界资源进行操作的部分)； 4) 对局部于管程的数据设置初始值的语句。二、 管程的组成（The Composition of Mo

20、nitor）The Grammar of Monitortype monitor-name=monitor variable declarations define ; use ； procedure P1(); beginend; procedure Pn(); beginend; begin initialization code end 1）安全性。管程的局部变量仅能由此管程的过程访问；反之，局部于管程的过程也仅能访问管程内的数据结构。 2）封装性。任意时刻，共享资源的进程可以通过调用管程内的一个过程进入管程，因此管程有很好的封装性。 3）互斥性。任意时刻，管程中只能有一个活跃的进程，其

21、他调用者必须等待直至管程可用。即，进程互斥的调用管程中的过程。 4）模块性。管程是一个基本程序单位，可以单独编译。三、管程的特性（ The peculiarity of monitor） 管程实现互斥调用是通过编译器自动实现的。当管程被编译器编译时，在进程的程序中加上测试信号量的P、V操作实现。 P操作位置就是调用管程中某个过程的语句前面。 V操作的位置是在调用语句结束时。程序员设计进程的程序时，不需要在进程的程序中显式加入。四、管程实现互斥和同步1、 互斥 管程的第三个特性，使他们能有效的完成互斥。2 同步管程实现同步，需设置： 条件变量x，表示等待原因，可根据需要设置多个。 利用wait和

22、signal操作表示因等待原因出现而等待、唤醒一个某原因而等待的进程。 管程提供了一种实现互斥的简便途径，但这还不够。需要一种办法使得进程在无法继续运行时被阻塞。 如在生产者消费者问题中，当生产者发现缓冲区满的时候如何阻塞呢？ 设var x:condition，则可有 wait(x)因等待x而阻塞，直至其他进程执行signal(x)。 signal(x)唤醒一个因等待x而阻塞的进程。 如果x等待队列中无进程阻塞，该操作不产生任何作用。（与信号量的signal不同） 如：因共享资源忙而进程等待，条件变量可定义为：nobusy：condiction。 则wait为：wait(nobusy)，sig

23、nal 为：signal(nobusy)条件变量和相关操作Type SSU=monitor var busy : boolean; nobusy : condition; define require, return; use wait, signal；procedure require; begin if busy then wait(nobusy); /*调用进程加入等待队列*/ busy := ture； end;procedure return; begin busy := false； signal(nobusy); /*从等待队列中释放进程*/end;begin /*管程变量初始化

24、*/ busy := false；end;例 如当已进入管程的一个进程（P）唤醒另一个进程(Q)时，为了避免管程中同时有两个活跃进程，P进程在signal之后该怎么办？Hoare采用Hansen建议问 题？处理方法有三种：等待，继续，直到等待或退出。等待，继续，直到退出或等待。规定P的signal操作只能作为管程的最后一条语句。两者必须有一个退出或停止使用管程Java图211管程示意图EntranceQueue ofEnteringProcessesMonitior Waiting Area Condition c1C1.wait.condition cn.Cn.waitUrgent Queu

25、ecsignal ExitM0NITOR Local DataCondition VariablesProcedure 1Procedure kInitialization Code一、定义管程 首先建立管程名为PC，并定义其包含的两个过程：1）put(item)为生产者放消息过程。count表示已有的消息数目。countn，表缓冲池已满。生产者需等待。2）get(item)为消费者取消息过程。 count0，表缓冲池已空，消费者等待。PC管程的描述为：Type producer-consumer =monitor var in,out,count:integer; buffer:array0

26、,n-1 of item; notfull,notempty:condition; 2.5.2 利用管程解决生产者消费者问题procedure entry put(item) begin if countn then wait(notfull) bufferin:=nextp in:=(in+1) mod n count:=count+1 if notempty.quene then signal(notempty) endprocedure entry get(item) begin if count0 then wait(notempty) nextc:=bufferout out:=(o

27、ut+1) mod n count:=count-1 if notfull.queue then signal(notfull) endbegin in:=out:=0; count:=0; endproducer:begin repeat produce an item in nextp PC.put(nextp) until falseend consumer:begin repeat PC.get(item) consume the item in nextc until falseend二、进程调用管程PC : producer-consumer ; /*管程实例化*/通过互斥自动化，

28、管程比信号量更容易保证进程执行的正确性。但管程是一个编程语言概念，编译器必须要识别管程并用某种方式对其互斥做出安排。C、Pascal以及多数其他语言都没有管程，所以这些编译器不能遵守互斥规则。语言中增加信号量较容易。向库里加入两段小的汇编代码，以执行wait和signal系统调用。编译器可以不知道它们的存在，只要操作系统知道信号量存在，或有一个基于信号量的操作系统，用户仍可使用C/C+编写用户程序，但是如果使用管程，读者就需要一种带有管程的语言。管程和信号量区别管程和信号量区别另外，管程和信号量机制都是设计用来解决访问公共内存的一个或多个CPU上的互斥问题。通过将信号量放在共享内存中，用TSL

29、或XCHG指令来避免竞争。如果一个分布式系统具有多个CPU，且每个CPU拥有自己的私有内存，通过一个局域网相连，那么这些原语将失效。结论：信号量太低级了，而管程在少数几种编程语言之外又无法使用，并且，这些原语均未提供机器间的信息交换方法。所以还需要其他的方法。 信号量设置sp:semaphore； /* 盘子里可以放几个水果 */sg1:semaphore； /* 盘子里有桔子 */sg2:semaphore； /* 盘子里有苹果 */信号量初值 sp := 1; /* 盘子里允许放一个水果*/ sg1 := 0; /* 盘子里没有桔子 */ sg2 := 0; /* 盘子里没有苹果*/voi

30、d reader() while(1)wait(queue);wait(Rmutex); if(0 = readcount)wait(mutex); readcount = readcount + 1;signal(rdcntmutex);signal(queue); read . wait(Rmutex); readcount = readcount - 1; if(0 = readcount)signal(mutex);signal(Rmutex); void writer() while(1)wait(Wmutex); if(0 =writecount)wait(queue); writ

31、ecount = writecount + 1;signal(Wmutex); wait(mutex); write .signal(mutex);wait(Wmutex); writecount = writecount - 1; if(0 = writecount)signal(queue); signal(Wmutex); semaphore mutex=1, Rmutex=1, Wmutex=1, queue=1;int readcount = 0, writecount = 0;Readers-Writers Problem: Writer FirstReaders-Writers

32、Problem: Writer FirstShared variable: semaphore rsem, wsem = 1; semaphore x,y,z = 1; int readcount, writecount = 0; while(1) wait(z); /用来保证写者优先 wait(rsem); /判断有没有写进程在临界区，有则等待，否则拒绝新的写进程进来 wait(x); /开始对readcount的互斥访问 readcount+; /更新读进程数量 if (readcount=1) wait(wsem); /第一个读进程需要判断是否有写进程在进行写操作，有的话需要等待，没有的

33、话不让写进程进行新写操作 signal(x); /结束对readcount的互斥访问 signal(rsem); /归还锁，让写进程可以进临界区 signal(z); Void reader () Readers-Writers Problem: Writer First R doReading(); wait(x); /开始对readcount的互斥访问 readcount-; /更新读进程数量 if (readcount=0) signal(wsem); /最后一个离开临界区的读进程需要归还锁，让写进程可以进行写操作 signal(x); /结束对readcount的互斥访问 Reader

34、s-Writers Problem: Writer First RReaders-Writers Problem: Writer First: Wvoid writer() while(1) wait(y); /开始对writecount的互斥访问 writecount+; /更新写进程数量 if (writecount=1) wait(rsem); /第一个写进程需要判断是否有读进程在临界区，有的话需要等待，没有的话不让新的读进程进来 signal(y); /结束对writecount的互斥访问 wait(wsem); /限制同一时刻只能有一个写进程进行写操作 doWriting(); si

35、gnal(wsem); /结束对写操作的限制 wait(y); /开始对writecount的互斥访问 writecount-; /更新写进程数量 if (writecount=0) signal(rsem); /最后一个离开临界区的写进程需要归还锁，让读进程可以进临界区 signal(y); /结束对writecount的互斥访问 Readers-Writers Problem: Writer First: W2.6 进程通信Process Communication概念：进程间的信息交换。实例：信号量机制（低级通信）缺点：（1）效率低；（2）通信对用户不透明。高级通信特点：效率高；用户利用

36、OS提供的通信命令进行数据的传输；通信实现细节对用户透明。高级通信机制可归结为三大类： 共享存储器系统 (Shared-Memory System) 消息传递系统（Message Passing System) 管道通信（Pipe Communication)2.6.1 进程通信的类型The type of process communication一、共享存储器系统(Shared-Memory System)1.基于共享数据结构的通信方式producer-consumer中的缓冲区，低效，传递少量数据，不透明。低级通信2.基于共享存储区的通信方式（UNIX中速度最高的）系统提供：在进程通信软

37、件包IPC中。通信过程：（1）向系统申请一个或多个内存存储区（2）获得分区获后即可读/写.特点：高效，速度快。 单机、多机系统、网络中的主要进程通信方式，进程间的数据交换以消息（message）( “报文”)为单位。通过内存中开设的缓冲区，进行消息的传递。 用户利用一组通信命令实现通信。根据实现方式的不同，可分为直接通信和间接通信。 直接通信方式（direct Communication way） 一般在一台机器的多进程间，直接以接收者进程的内部标识为目的标识发送消息。通常，系统提供下述两条通信原语： Send(Receiver,message) ； .发送原语 Receive(Sender,

38、message) ； .接收原语二、消息传递系统（Message Passing System)直接通信实例消息缓冲队列通信机制 图示repeat produce an item in nextp; send(consumer, nextp); until false; repeat receive( producer, nextc); consumer the item in nextc; until false;例：消息传递方式解决生产消费问题。1间接通信： 建立一个通信参与者共享的逻辑实体信箱，发送者向信箱发送消息；接收者到信箱取消息。用于联系不十分紧密的进程之间。 间接通信方式（Ind

39、irect Communication way）优点：信箱可实现“实时”或“非实时”通信。在读/写时间上具有随机性。共享的逻辑实体可以是操作系统在核心空间提供的一组数据结构，也可以磁盘上的文件为基础，其特点是不只属于通信中的任意一方，而是一个中间实体。ABCDESendReceive2信箱：包含有多个消息的队列。系统为信箱通信提供若干条原语，实现对信箱的管理。1）信箱的创建和撤消 进程利用信箱创建原语建立一个新信箱。信箱头和信箱体2）消息的发送与接收 Send(mailbox,message) Receive(mailbox,message)信箱头（信箱名、口令）信格信格信格信格信格 信箱头：

40、描述邮箱名、属性、大小及拥有该邮箱的进程名； 信箱体：存放消息。私用信箱(private mailbox) ：由用户进程自己创建，并作为该进程的一部分。拥有者可从中读，其它进程只能向其中发送。拥有者进程结束，信箱消失。 公用信箱(public mailbox) ：由OS创建，允许系统中所有核准用户读、放。 共享信箱(shared mailbox) ：由某进程创建，指明共享属性及共享进程名。创建者和共享者有权从信箱中取走消息。3）信箱分类 发送者进程和接收者进程之间的关系存在以下几种。一对一：专用的通信链路，两个进程间建立私用的通信连接，不受其他进程的干扰和影响。多对一：允许提供服务的进程与多个

41、用户进程交互，多个向一个发信息。用于现代操作系统 （客户/服务器）一对多：一个发送者和多个接收者的通信关系。发送进程可利用广播形式，向接收者发送消息。多对多：如公用信箱，允许多个进程都能象信箱中投递消息，也可从信箱中取走属于自己的消息。3间接通信的灵活性1 通信链路(communication link)：在发送进程和接收进程之间为信息传送而建立的一条通路。1）建立方式 显示建立：由发送进程利用建立命令建立，用完后用删除命令拆除。（网络中） 隐式建立：利用发送命令（原语），系统自动建立。（单机中）消息传递中的几个问题2）连接方式 点点连接：一条链路只有两个结点。 多点连接：一条链路连接多个结点

42、。3）通信方向 单向：发送进程 接收进程。 双向：进程 进程4）链路的容量无容量：链路上没有缓冲区，不能暂存信息。有容量：链路上有缓冲区，能暂存信息。2 消息的格式 字符流：发送方发送的数据没有一定的格式，接收方不需要保留各次发送之间的分界 报文： 是网络环境下采用的消息格式。 报头(header) ：包括数据传输时所需的控制信息。如发送进程名，报文长度、数据类型、发送时间等。 正文( text)：消息内容。分为定长和变长两种。3 进程同步方式 根据收发进程在进行收发操作时是否等待，同步方式分为两种：阻塞方式和非阻塞方式。2接收进程执行完Receive命令后怎么办？（1）阻塞自己直到收到发送进

43、程的消息。称为阻塞接收。（2）不要求进程等待，当需要信件时，去查找并接收信件，需要时再发送回答信件。称为非阻塞接收。3. 常用的进程间通信模式： 非阻塞发送、阻塞接收（应用最广泛的进程同步方式） 非阻塞发送、非阻塞接收（较常见的方式。如具有缓冲队列的生产者-消费者同步） 阻塞发送，阻塞接收（发送进程和接收进程间无缓冲）1发送进程执行完Send命令后怎么办？ （1）阻塞自己等接收者回信后才继续向前执行，称为阻塞发送。 （2）发送完消息后不等回信继续执行，称为不阻塞发送。 管道：利用一个打开的共享文件，连接两个相互通信的进程。进程通过两个命令利用该共享文件通信。一个命令向该文件中写入数据，另一个命

44、令从文件中读出数据。共享文件称pipe文件。它以字符流方式进行数据传送。发送进程接收进程字符流方式写入有个读出先进先出顺序三、管道通信（Pipe Communication) unix系统中1）互斥：管道可看作是临界资源。对管道的操作是互斥的。2）同步：当写进程把一定数量数据写入pipe后,便去等待，直到读出进程取走数据后，把它唤醒。反之亦然。3）对方是否存在：只有确定对方存在时，才可通信。管道通信机制应能提供三方面的协调功能： 2、操作 write(fd1,buf,size) 功能：把buf中的长度为size字符的消息送入管道入口fd1 fd1pipe入口 read(fd0,buf,size

45、) fd0Pipe的出口功能：从pipe出口fd0读出size字符的消息置入 buf中。1、定义#include intpipe(intfd2)；参数filedis返回两个文件描述符：fd0为读而打开，fd1为写而打开。fd1的输出是fd0的输入。Pipe文件的定义和操作 首先由Hansan提出，并在RC4000系统上实现。在一个消息定长的简单直接通信消息系统中，进程间通过两个基本操作进行通信。 Send(A,a)：发送者用以发送消息。A为接收者标识符,a为消息的发送区始址。 Receive(b)：接收者用以接收当前已到达的消息。b为消息的接收区始址。若当前无消息到达，则接收者进入等待状态直到

46、到达一个消息。2.6.2 消息缓冲队列通信机制message buffer queue communication mechanism发送不阻塞，接收阻塞1）消息缓冲区： Type message buffer =record sender : 发送者进程标识符 size : 消息长度 text :消息正文 next : 指向下一个消息缓冲区的指针 end一、 数据结构 为保证消息缓冲队列的互斥，协调发送进程和接收进程的同步，在接收进程的PCB中增加的有关数据项。 Type process control block =record mq : 消息队列队首指针 mutex : 消息队列互斥信号

47、量，初值为1 sm : 消息队列私有信号量，记录消息个数，初值为0； end2）PCB中有关通信的数据项 互斥使用缓冲队列，即发送进程把消息写入缓冲区、把缓冲区挂入消息队列时，应禁止其他进程对该缓冲队列的访问，同理，当接收进程正从消息队列中取消息时，应禁止其他进程对该队列的访问。应设mutex-互斥信号量 消息缓冲队列是按接收进程排列，每个接收进程拥有自己的消息队列。因此同一时间存在多个消息队列；且这些队列长度不固定。 当缓冲队列无消息时，接收进程不能接收到任何消息。Sm为接收进程的私用信号量(初值为0)说 明A的PCB.Send(B, a).Sender:ASIZE:消息长度TEXT:消息正

48、文B的PCB. mq Mutex sm.Receive(b).Sender:ASIZE:消息长度TEXT:消息正文.发送区a:接收区b发送进程 A消息消息.Sender:ASIZE:消息长度TEXT:消息正文接收进程 BSend(receiver，m) Begin 向系统申请一个消息缓冲区； 把m送入新申请的消息缓冲区， wait(mutex); 把消息缓冲区挂入接收进程的消息队列。 signal(mutex); signal(Sm);End;Receive(n) Begin wait(Sm); Wait(mutex); 摘下消息队列中的消息n， Signal(mutex); 将消息n从缓冲区

49、复制到接收区； 释放缓冲区；End; 发送进程是否可以发送消息，则取决于是否申请到缓冲区。具体见课本P70二、发送原语procedure send(receiver,a) begin getbuf(a.size,i) i.sender:=a.sender i.size:=a.size i.text:=a.text i.next:=0 getid(PCB.receiver.j) wait(j.mutex) insert(j.mq.I) signal(j.mutex) signal(j.sm) enda为发送进程在自己的内存空间中设置的一发送区。把消息正文、发送进程标识符、消息长度等信息填入a中。

50、根据a.size申请一缓冲区i，把a中信息复制到i中，获得接收进程的内部标识符j，将i挂在j.mq上。因为消息队列为临界资源，对其操作要求互斥。三、 接收原语procedure receive(b) begin j:=internal name wait(j.sm) wait(j.mutex) remove(j.mq.i) signal(j.mutex) b.sender:=i.sender b.size:=i.size b.text:=i.text end接收进程调用接收原语，在自己的消息缓冲队列mq中，摘下第一个消息缓冲区（如i），将其复制到以b为首址的指定消息接收区内。2.7 线 程 (

51、 Thread)一、线程的引入 (the introduction of thread) 进程的两个基本属性：是构成进程并发执行的基础。 资源的拥有者：每个进程分配PCB，保存进程映像，控制一些资源，状态、优先级等。 调度/执行：进程是一个执行轨迹，在一个时刻只能有一个执行控制流。 2.7.1 线程的基本概念(The Basic Concept of Thread)创建进程：分配整套资源。(分配PCB，分配除CPU之外的其他所需资源)撤消进程：释放整套资源。（回收资源，撤销PCB）进程切换：切换整套资源。（保留当前进程的PCB环境，设置新选中进程的CPU环境）时间空间开销大，限制并发度。 进程

52、操作存在的问题： 缺点： 将原来进程的两个属性（资源分配单位和运行调度单位）分开处理。 资源拥有单元称为进程（或任务）； 调度的单位称为线程。 线程定义：轻型进程（LWP） 解决方案：引入线程 是进程中的一个运行实体，是CPU调度的基本单位。为了减少时空开销，提高并发度，引入线程。 轻型实体。只拥有少量运行中必不可省的资源。TCB、描述处理器工作情况的一组寄存器（程序计数器、状态寄存器、通用寄存器等）、堆栈（核心栈和用户栈）； 独立调度的基本单位。线程的切换开销小，速度快。 共享进程资源。进程只是资源的拥有者，进程创建线程，一个进程可包含多个线程，它们共享进程拥有的资源。一个线程可创建和撤销另

53、一个线程。 并发执行。多个线程可并发执行。 具有就绪、阻塞和执行三种基本状态。运行中也呈现间断性。二、线程属性（The Attribute of thread）三、进程和线程的比较1 线程与进程的关系一个进程可以有多个线程，线程只能在一个进程的地址空间内活动。资源分配给进程。同一进程的所有线程共享该进程的所有资源。处理机分配给线程。真正在处理机上运行的是线程。进程的“执行”状态实际是进程中某线程的执行状态。线程在执行过程中需要协作同步，不同进程的线程要利用消息通信的办法实现同步。UserStackKernelStackUserAddressSpaceProcessControlBlockSin

54、gle-ThreadedProcess ModelUserStackThreadControlBlockKernelStackThreadMultithreaded Process ModelUserAddressSpaceProcessControlBlockThreadControlBlockUserStackKernelStackThreadThreadControlBlockUserStackKernelStackThread单线程和多线程进程模型多线程模型中线程为保持自己的控制流而独有寄存器和堆栈，但三个线程同属一个进程，共享一个地址空间。进程和线程关系表2、线程与进程的比较 线程具

55、有许多传统进程所具有的特征，故又称轻型进程（Light-Weight-Process）或进程元； 而把传统的进程称为重型进程（Heavy-Weight-Process），它相当于只有一个线程的任务。 从调度、并发性、拥有资源和系统开销四个方面比较进程和线程。传统操作系统引入线程的操作系统调度 基本单位是进程 进程切换要OS内核干预 基本单位是线程； 同一进程中线程切换不会引起进程的切换； 进程内线程切换无需OS内核干预.并发性进程间并发 进程间可并发； 进程中多个线程也可并发拥有资源基本单位是进程基本单位是进程系统开销进程的创建、切换、撤消时的开销较大线程创建、切换、撤消时的开销较小。进程和线

56、程比较表2.7.2 线程间的同步和通信 Synchronization and comm. between threads 为使系统中的多线程能有条不紊地运行，在系统中必须提供用于线程间同步和通信的机制。在多线程OS中通常提供多种同步机制： 互斥锁 条件变量 计数信号量 多读、写锁一、 互斥锁(mutex) mutual exclusive lock互斥锁是一种较简单、对资源实现互斥访问的机制。互斥锁有两种状态，即开锁(unlock)和关锁(lock)状态。相应地，可用两条命令（函数）对互斥锁进行操作，即 lock(mutex)和unlock(mutex)。同步方式： lock(mutex); 读写共享数据段； unlock(mutex); 为减少线程被阻塞的机会，在有的系统中还提供了一种用于mutex上的操作命令Trylock。 一个线程利用Trylock命令访问mutex时，若mutex处于开锁状态， Trylock返回成功状态码，反之，Tr