第2章进程管理

第二部分

进程管理

南昌大学信息管理系

NanChangUniversityDepartmentofinformationmanager1２.1进程的基本概念22.1.1

程序的顺序执行及特征1、程序的顺序执行程序分若干程序段，各程序段之间必须按某种先后顺序执行，仅当前一操作（程序段）执行完后，才能执行后继操作。例如：S1:a:=x+y;

S2:b:=a-5;

S3:c:=b+1;S2必须在S1句后,S3必须在S2句.3又如:输入、计算、执行I1C1p1I2c2p2

I：输入操作，C：计算操作，P：打印操作

41、顺序性2、封闭性3、可再现性2、程序顺序执行时的特征52.1.2前趋图前趋图:

是一个有向无循环图DAG(DirectedAcyclicGraph)

，描述进程之间执行的前后关系。结点：描述一个程序段或进程或一条语句有向边：表示结点之间存在的前趋关系。记为“”6前趋关系表示:={(Pi,Pj

)|PimustcompletebeforePjmaystart如果(Pi,Pj),可写成PiPj称Pi是Pj的直接前趋,而称Pj是Pi的直接后继初始结点:

没有前趋的结点终止结点:没有后继的结点7存在前趋关系：P1→P2,P1→P3,P1→P4,P2→P5,P3→P5,P4→P6,P5→P7,P6→P7或P={P1,P2,P3,P4,P5,P6,P7}→={(P1,P2)(P1,P3)(

P1,P4)(P2,P5)(P3,P5)(P4,P6)(P5,P7)(P6,P7)}P7P1P3P4P5P6P282.1.3程序并发执行

1、程序并发执行

9I1I2I3I4C1C2C3C4P1P2P3P4相互合作资源共享IiCiIiIi+1CiPiCiCi+1PiPi+1Ii+1和Ci及Pi-1是重叠的。亦即Pi-1和CI以及Ii+1可以并发执行。101、间断性2、失去封闭性3、不可再现性2、程序并发执行时的特征11例如:两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N:=N+1操作；程序B则每执行一次时，都要执行Print（N）操作，然后再将N置成“0”，程序A和B以不同的速度运行。假定某时刻:N=n则:

12A程序在B程序之前执行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，0N值分别为n，0，1N值分别为n，n+1，0132.1.4进程的特征与状态

由于程序执行结果的不可再现性，使得程序不能参与并发执行。为使程序能并发执行，且为了对并发执行的程序加以描述，引入“进程”的概念。１.进程的特征与定义14进程的定义（1）进程是程序的一次执行；（2）

进程是可以和别的计算并发执行的计算；（3）

进程可定义为一个数据结构及能在其上进行操作的一个程序；（4）

进程是一个程序及其数据在处理机上顺序执行时所发生的活动；（5）

进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的一个独立单位。15进程的定义进程是进程实体的运行过程,是系统进行资源分配和调度的一个独立单位。16进程的特征结构特征：动态性：并发性：独立性：异步性：进程实体是由程序段、数据段及进程控制块三部分组成，有人把这三部分统称为“进程映像”。进程是程序的一次执行多个进程实体，同存在于内存中，轮流占有处理机和各种资源，走走停停交叉运行。进程是一个独立进行资源分配和调度运行的基本单位。这是指进程按各自独立的、不可预知的速度向前推进，或者说进程按异步方式运行17进程和程序的区别：（1）程序是为了完成某项工作时需要计算机执行的指令的集合，是静态的概念；而进程是程序的执行，是动态的概念。（2）程序是永远存在的，进程则有生存期，它的存在是暂时的。（3）进程是一个独立调度并能和其它进程并发运行的单位，而程序和程序段则不能作为一个独立调度运行的单位，也不能并发执行。182进程三种的基本状态

1)就绪状态:当进程已分配到除CPU以外的所有必要的资源后,只要再获得CPU便可立即执行.

多个就绪状态的进程排成一个队列称就绪队列2)执行状态:已获得CPU,正在执行.

单处理机系统–只要一个执行状态的进程,

多处理机系统–多个执行状态的进程192进程三种的基本状态

(续)3)阻塞状态，又称等待状态:正在执行的进程由于发生某事件而暂时无法继续执行,便放弃处理机,处于阻塞状态(等待状态).使进程阻塞的典型事件:请求I/O,申请缓冲空间.多个等待状态的进程排成一个队列称等待队列进程的三种基本状态及其转换P31图2-520就绪执行阻塞进程调度中断I/O中断或等待某事件I/O完成或事件发生进程状态213.进程的挂起状态1、终端用户的需求2、

父进程的需求3、

负荷调节的需要4、OS的需要1)、引入挂起状态的主要原因:由于进程的不断创建，系统的资源已经不能满足进程运行的要求，这个时候就必须把某些进程挂起（suspend），对换到磁盘镜像区中，暂时不参与进程调度，起到平滑系统操作负荷的目的

223.进程的挂起状态(续)

引入挂起状态后,则:就绪状态分为:活动就绪状态和静止就绪状态活动就绪(Readya)静止就绪(Readys)活动就绪(Readya):进程处于未被挂起的就绪状态静止就绪(Readys):调用挂起原语(Suspend)将进程挂起后,该进程便转变为的静止就绪状态.静止就绪(Readys)活动就绪(Readya)处于Readys状态的进程,若用激活原语(Active)激活后,该进程转变为Readya状态.233.进程的挂起状态(续)

同样:阻塞状态分为:活动阻塞状态和静止阻塞状态活动阻塞(Blockeda)静止阻塞(Blockeds)活动阻塞(Blockeda):进程处于未被挂起的阻塞状态静止阻塞(Blockeds):进程处于活动阻塞时,调用挂起原语(Suspend)将进程挂起后,该进程便转变为的静止阻塞状态.静止阻塞(Blockeds)活动阻塞(Blockeda)处于Blockeds状态的进程,若用激活原语(Active)激活后,该进程转变为Blockeda状态.243.进程的挂起状态(续)

静态就绪状态表明了进程具备运行条件,但目前在二级存储器中，只有当它被对换到主存才能被调度执行。静态等待状态则表明了进程正在等待某一个事件且在二级存储器中。

挂起的进程将不参与进程调度直到它们被对换进主存。具有如下特征：该进程不能立即被执行。挂起进程可能会等待一个事件，但所等待的事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件。进程进入挂起状态是由于操作系统、父进程或进程本身阻止它的运行。结束进程挂起状态的命令只能通过操作系统或父进程发出。

25具有挂起状态的进程状态转换图活动就绪执行静止就绪静止阻塞活动阻塞挂起激活挂起请求I/O挂起激活释放等待事件结束

262.1.5进程控制块(ProcessControlBlock)进程控制块是一个记录和刻划进程状态及有关信息的数据结构,是进程实体的一部分.使一个在多道环境下不能独立运行的程序成为一个能独立运行的基本单位.OS根据PCB来对并发执行的进程进行控制和管理.1、进程控制块的作用272、进程控制块中的信息

(1)进程标识符信息：用于唯一标识一个进程

外部标识符:用户使用内部标识符:系统使用28用于保留一个进程在运行时存放在处理器现场中的各种信息，任何一个进程在让出处理器时必须把此时的处理器现场信息保存到进程控制块中，而当该进程重新恢复运行时也应恢复处理器现场。常用的现场信息包括通用寄存器的内容、控制寄存器(如PSW寄存器)的内容、用户堆栈指针、系统堆栈指针等。(2)处理机状态信息29(3)进程调度信息进程的当前状态；进程的优先级；进程调度所需的其它信息；如进程已等待CPU的时间总和、进程已执行的时间总和等；事件；是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因30程序和数据的地址，是指进程的程序和数据所在的内存或外存地（首）址资，以便再调度到该进程执行时，能从PCB中找到其程序和数据；实现进程同步和通信相关信息，如消息队列指针、信号量；资源清单：包括进程所需全部资源、已经分得的资源。链接指针：给出了本进程PCB所在队列中的下一个进程的PCB首地址(4)进程控制信息313、PCB的组织方式

(1).链接方式

把具有相同状态的PCB，用其中的链接字，链接成一个队列。32Page33图2-7PCB链接队列示意图33(2).索引方式图2-834页342.2进程控制

进程图是用于描述进程家族关系的有向树。2.2.1进程的创建

1、进程图（ProcessGraph）35ABCDEFGHI子进程父进程祖父进程祖先进程362、引起创建进程的事件

(1)、

用户登录:分时系统中,有新的合法的登录命令(2)、作业调度:批处理系统中,作业调度时(3)、提供服务:运行中的用户程序提出某种请求时,系统专门创建一个进程来提供所需的服务,例如:p35(4)、应用请求

:用户进程根据需要创建子进程373、进程的创建

(1)

、申请空白PCB:申请获得唯一的数字标识符,并从PCB集合中索取一个空白PCB(2)

、为新进程分配资源:为新进程的程序和数据以及用户栈分配必要的内存空间.(3)

、初始化进程控制块:初始化标识符(填入PCB);初始化处理机,使程序计数器指向程序的入口地址,使栈指针指向栈顶;初始化进程控制信息,设置为“就绪状态”,设置优先级(通常缺省优先级).(4)

、将新进程插入就绪队列382.2.2进程的终止

(1).正常结束：如Windows的exit指令，logoff退出等(2).异常结束：错误和故障而被迫使进程终止(3).外界干预：操作系统干预或父进程干预1、引起进程终止的事件2、进程的终止过程

调用进程终止原语终止指定进程。392.2.2进程的终止(续)

2、进程的终止过程

OS调用进程终止原语终止指定进程。(1).根据进程标识符，检索PCB,读出进程状态(2)若执行状态，立即终止，并要重新调度(3)同时终止该进程的子进程。(4)释放该进程占有的资源(5)从所在的PCB队列中移出402.2.3进程的阻塞和唤醒

(1)、请求系统服务但不能满足

(2)、启动某种操作,如进程启动I/O操作,后,阻塞等待,在I/O完成后,由中断进程唤醒本进程(3)、新数据尚未到达,同步进程未完成(4)、无新工作可做时,某些进程自阻塞,等待其它进程来唤醒1、引起进程阻塞和唤醒的事件典型事件：I/O请求；等待输入。413、进程唤醒过程：2、进程阻塞过程：被阻塞的进程所期待的事件出现时,则由有关进程调用唤醒原语wakeup将等待该事件的进程唤醒.把被阻塞的进程从阻塞队列移出,改状态为就绪,插入到就绪中队列,实现进程从阻塞状态到就绪状态的转换。正在执行的进程,一旦发现引起阻塞的事件,就调用阻塞原语block阻塞自己.进程状态从执行状态改为阻塞状态。,并将PCB插入到阻塞队列.422.2.4进程的挂起与激活

1、挂起过程调用进程挂起原语suspend实现进程挂起检查挂起进程的状态,若活动就绪静止就绪若活动阻塞静止阻塞若正在执行静止就绪,转向调度程序重新调度432.2.4进程的挂起与激活(续)2、激活过程调用激活原语active将指定进程激活.激活原语先将进程从二级内存调入内存,检查进程状态:若静止就绪活动就绪(若为抢占式调度,则比较被激活进程与当前正在执行进程的优先级,决定是否需要重新调度,若不需要按优先级插入)若静止阻塞活动阻塞442.3进程同步

452.3.1进程同步的基本概念

1.两种形式的制约关系

(1).间接相互制约关系(互斥关系)

例如:有进程A和进程B，如果在进程A提出打印请求时，系统已将唯一的一台打印机分配给了进程B，则此时进程A只能阻塞，一旦进程B将打印机释放，才能使进程A由阻塞改变为就绪状态46(2).直接相互制约关系(合作关系)例如：有一进程A通过单向缓冲向进程B提供数据。当该缓冲空时，进程B因不能获得所需数据而阻塞，而当进程A把数据输入缓冲区后，便将进程B唤醒；反之，当缓冲区已满时，进程A因不能再向缓冲区投放数据而阻塞，当进程B将缓冲区数据取走后便可唤醒进程A

如：catch1ch2ch3|greptree47

系统中的某些资源如打印机、磁带机、卡片机，虽然它们可提供给多个进程使用，但在同一时间内却只允许一个进程访问这些资源。当一个进程还在使用该资源时，其它欲访问该资源的进程必须等待，仅当该进程访问完毕并释放资源后，才允许另一进程对该资源访问。这种同一时间内只允许一个进程访问的资源称临界资源，许多物理设备，以及数据都是临界资源，它们只能互斥地被共享。2.临界资源

48著名的生产者--消费者(Producer-ConsumerProblem)问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。解决好了生产者--消费者问题就解决好了一类并发进程的同步问题。49问题描述：一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为生产者进程和消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池。生产者进程将它所生产的产品放入缓冲池，消费者进程可以从缓冲池中取走产品去消费。只要缓冲区未满，生产者生产的产品就可投入缓冲池；类似地，只要缓冲池不空，消费者进程就可从缓冲池取走并消耗产品。50

用数组buffer表示n个（0，1，…，n-1）缓冲区的缓冲池，用输入指针in来指示下一个可投放消息的缓冲区，用输出指针out来指示下一个可获取消息的缓冲区。in=（in+1）modn；out=（out+1）modn；当（in+1）modn=out时，表示缓冲池满;当in=out表示缓冲池空。整型变量counter，初值为0；生产者投放一个消息counter+1；消费者进程从中取走一个消息时，counter-1。51Varn:integer;Typeitem=…;Varbuffer=array[0,1,…n-1]ofitem;In,out:0,1,…n-1;Counter:0,1,…n;52Producer:repeat┆ produceaniteminnextp; ┆ whilecounter=ndono-op; buffer[in]:=nextp; in:=in+1modn; counter:=counter+1;untilfalse;缓冲池满，空操作，测试局部变量，暂存刚生产出的消息生产者进程往缓冲区投放消息，输入指针加1生产者投放-消息53consumer:repeat whilecounter=odono-op;

nextc:=buffer[out]; out:=out+1modn; counter:=counter-1; consumetheiteminnextc;untilfalse;缓冲池空，空操作，测试局部变量存放要消费的消息消费一消息，输出指针加1消费者消费一消息54这两个进程共享变量counter，生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时常可用下面形式描述：register1:=counter;register1:=register1+1;counter:=register1;register2:=counter;register2:=register2-1;counter:=register2;55register1=5register1=6register2=5register2=4counter=6counter=4程序的执行不具有可再现性。解决问题的关键:把变量counter作为临界资源处理。register1:=counter;register1:=register1+1;register2:=counter;register2:=register2-1;counter:=register1;counter:=register2;563.临界区

(CriticalSection)我们把每个进程中访问临界资源的那段代码(一段程序)称为临界区。在进入临界区之前，对欲访问的临界资源进行检查，看它是否可以被访问，如果此刻该临界资源未被访问，进程便可进入该临界区对该资源进行访问，并设置它正被访问的标志；这段用于检查的代码称为进入区（entrysection)。而在临界区后用于将临界区正被访问的标志恢复为未被访问的标志的一段代码称为退出区(exitsection)57描述访问临界资源的循环进程：

repeatentrysection

criticalsection

exitsectionremaindersectionuntilfalse;进入区临界区退出区剩余区584、同步机制应遵循的准则

(1)、空闲让进(2)、忙则等待(3)、有限等待(4)、让权等待59假定两个进程Pi和Pj共享一个临界资源R。使Pi和Pj互斥访问资源R的一般性描述：Begin parentbegin

Pi;

Pj; parentendend２.3.2信号量机制

60

wait(s)：whileS≤0donoopP操作

S:=S-1;signal(s)：S:=S+1;V操作wait(s)和signal(s)是两个原子操作，因此它们在执行时是不可中断的。１、整型信号量

61在整型信号量机制中的wait操作，信号量S≤0，就会不断地测试，该机制并未遵循“让权等待”的准则，而是使该进程处于“忙等”的状态。622、记录型信号量机制

typesemaphore=record value:integer; L:listofprocess;ends.value资源信号量等待信号量链表S.L63Procedurewait(s)varS:Semaphore;begin s.value:=s.value-1;ifs.value<0thenblock(S.L)endProceduresignal(s)vars:semaphore;begins.value:=s.value+1;

ifs.value≤0thenwakeup(S,L);end64P.V操作讨论1)信号量的物理含义：S>0表示有S个资源可用S=0表示无资源可用S<0则|S|表示S等待队列中的进程个数P(S):表示申请一个资源V(S)表示释放一个资源。信号量的初值应该大于等于065

AND同步机制的基本思想是：对若干个临界资源的分配，采取原子操作方式，要么全部分配到进程，要么一个也不分配，这样可以避免死锁。在wait操作中增加了一个“AND”条件，故称为AND同步，或称为同时wait操作。3、AND型信号量机制

66procedureSwait(s1，．．．sn)beginifs1>=1&．．．&sn>=1thenfori:=1tondosi:=si-1;

endfor

elsebegin

进程进入第一个迂到的满足si<1条件的si信号量队列等待，同时将该进程的程序计数器地址回退，置为SP操作处。

end67Ssignal(S1,d1，…Sn，dn)fori:=1tondo Si:=Si+dI; Removealltheprocesswaitinginthequeue associatedwithSiintothereadyqueue.endfor;684、信号量集

在记录型和AND信号量机制中，P、V或SP、SV仅仅能对信号量施行增1或减1操作，每次只能获得或释放一个临界资源。当一请求n个资源时，便需要n次信号量操作，这样做效率很低。此外，在有些情况下，当资源数量小于一个下限时，便不预分配。为此，可以在分配之前，测试某资源的数量是否大于阀值t。对AND型信号量机制作扩充，便形成了一般型信号量机制。69Swait(S1，t1，d1，…Sn，tn，dn) ifS1≥t1and…andSn≥tnthen fori:=1tondo

Si:=Si-di;

endforelse PlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi<tiandsetitsprogramcountertothebeginningoftheSwaitOperation.

endif;70Ssingnal(S1,d1，…Sn，dn)fori:=1tondo Si:=Si+dI; Removealltheprocesswaitinginthequeue

ussociatedwithSiintothereadyqueue.endfor;71（1）Swait(S，t，d)（2）Swait(S，1，1)（3）Swait(S，1，0)“信号量集”的几种特殊情况：72２.3.３信号量的应用

73varmutex:semaphore:=1;beginparbegin

process1:begin repeat wait(mutex); criticalsection; signal(mutex);

remaindersection; untilfalse;endprocess2:beginrepeat wait(mutex);criticalseition;

signal(mutex);

remainderseetion

untilfalseend

parend

end1、利用信号量实现互斥

74

P1，P2是并发执行的进程，P1有语句S1，P2有语句S2，我们希望S1执行后再执行S2

。在P1中，用S1；signal(s)；在P2中，用wait(s)；S2；使P1和P2共享一个信号量S，其初值为0２、利用信号量来实现前趋关系

75S1S2S3S4S5S6abcdefg76vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;beginparbegin

beginS1;signal(a);signal(b);end; beginwait(a);S2;signal(c);signal(d);end; beginwait(b);S3;signal(e);end; beginwait(d);S5;signal(g);end; beginwait(e);wait(f);wait(g);S6;end;parend;end772.4经典进程的同步问题2.4.1生产者—消费者问题2.4.2

哲学家进餐问题2.4.3读者—写者问题782.4.1生产者—消费者问题互斥信号量mutex

:实现对缓冲池的互斥使用;

资源信号量empty:表示空缓冲区的数量;full:表示满缓冲区的数量。

1、利用记录型信号量解决生产者—消费者问题问题描述：同前79Varmutex,empty,full:semaphore:=1,n,0;

Buffer:array[0,…,n-1]ofitem;In,out:integer:=0,0;Beginparbegin

procedure:beginrepeat┇

procedureaniteminnextp;┇

wait(empty);//*wait(mutex);//*//以上两句改变顺序会死锁

buffer(in):=nextp;

in:=(in+1)modn;

signal(mutex);

signal(full);untilfalse;endconsumer:beginrepeat

wait(full);wait(mutex);

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

signal(mutex);signal(empty);

consumetheiteminnextc;untilfalse;endparendend80注意：(1)用于实现互斥的wait(mutex)和signal(mutex)必须成对出现。(2)对资源信号量empty和full的wait和signal操作，也需要成对出现，但是处于不同的程序中。(3)wait操作顺序不能颠倒，先执行对资源信号量的wait操作，再执行对互斥信号量的wait操作，否则会引起死锁。81wait(empty);wait(mutex);buffer(in):=nextp;

in:=(in+1)modn;signal(mutex);signal(full);

wait(mutex);wait(empty);//errorbuffer(in):=nextp;

in:=(in+1)modn;signal(mutex);signal(full);

wait(full);wait(mutex);

nextc:=buffer(out);out:=(out+1)modn;signal(mutex);signal(empty);

82错误1：wait(s)与signal(s)次序颠倒。

signal(mutex);

criticalsection

wait(mutex);

用mutex实现进程互斥时，若将wait(s)与signal(s)颠倒,会使多个进程同时进入临界区83错误2：实现进程互斥时，将signal(mutex)误写作wait(mutex)

wait(mutex)；

criticalsectionwait(mutex)；

出错的进程无法唤醒84错误3：实现进程互斥时，在程序中遗漏了wait(mutex)操作，会使多个进程活跃在临界区；而遗漏了signal(mutex)操作，则会使其它进程无法再进入临界区。

852、利用AND信号量解决生产者—消费者问题

Varmutex,empty,full:semaphore:=1,n,0;

Buffer:array[0,…,n-1]ofitem;In,out:integer:=0,0;Beginparbegin

procedure:beginrepeat┇

procedureaniteminnextp;┇

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

in:=(in+1)modn;

Ssignal(mutex,full);

untilfalse;endconsumer:beginrepeat

Swait(full,mutex);

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

Ssignal(mutex,empty);

consumetheiteminnextc;untilfalse;endparendend86有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子，每个哲学家的行为是思考，感到饥饿，然后吃通心粉，为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子。2.4.2

哲学家进餐问题

问题描述：87

哲学家用餐问题有益于模拟进程争夺有限资源—例如磁带驱动器或者别的I/0设备——的互斥性访问权。

这里筷子是临界资源，在一段时间内只允许一个哲学家使用。因此，可以用一个信号量表示一支筷子，由这五个信号量构成信号量数组。分析：88varchopstick;array[0,…,4]ofsemaphore=(1,1,1,1,1);/*所有信号量初始化为1repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);┇eat;┇signal(chopstick[i]);signal(chopstick[(i+1)mod5]);┇think;untilfalse;1.利用记录型信号量解决哲学家进餐问题

89以上解答有可能发生死锁!对于这样的死锁问题可采取以下几种解决方法：（1）至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能进餐，最终释放出他所使用过的两支筷子，从而可使更多的哲学家就餐。（2）仅当哲学家的左、右两支筷子均可用时，才允许他拿起筷子进餐。（3）奇数号哲学家先拿左边的筷子，再去拿右边的筷子，而偶数呢相反，最后总会有一个哲学家能获得两支筷子而进餐。902、利用AND信号量解决哲学家就餐问题varchopstick:array[0,…,4]ofsemaphore:=(1,1,1,1,1)

processirepeatthink;Swait(chopstick[(i+1)mod5],chopstick[i]);Eat;Ssignal(chopstick[(i+1)mod5],chopstick[i]);

untilfalse;//可以解决上种解法所存在的死锁问题!912.4.3读者—写者问题

有两组并发进程：读者和写者，共享一个文件F，要求：(1)允许多个读者同时执行读操作;(2)任一写者在完成写操作之前不允许其它读者或写者工作;(3)写者执行写操作前，应让已有的写者和读者全部退出。

问题描述：92分析：有读进程在读，写进程不能写有读进程在读，其他读进程可进入读有写进程在写，其他写进程和读进程无法进入写或读93互斥信号量Wmutex：实现reader进程与writer进程读或写时的互斥。整型变量readcount：表示正在读的进程数目。

互斥信号量Rmutex

：实现多个reader进程对readcount

的访问。

设：94VarRmutex,Wmutex:=semaphore:=1,1;readcount:integer:=0;beginparbegin

reader:beginrepeatwait(Rmutex);ifreadcount=0thenwait(Wmutex);readcount:=readcount+1;signal(Rmutex);┇performreadoperation;┇wait(Rmutex)readcount:=readcount-1;ifreadcount=0thensignal(Wmutex);signal(Rmutex);untilfalse;end

writer:beginrepeatwait(Wmutex);performwriteoperation;signal(Wmutex);untilfalseendparendend

1.利用记录型信号量解决读者—写者问题

95由于只要有一个reader进程在读，便不允许writer进程去写。因此，仅当readcount=0时，表示没有reader进程在读时，reader进程才需要执行wait(Wmutex)操作。

若readcount≠0，表示已有读进程去读，而读进程是允许多个同时读的。仅当reader进程在执行了readcount-1操作后，其值为0时，才需执行signal(Wmutex)以便让writer进程进程写。96Readcounter=0既无读进程又无写进程虽无读进程但有写进程临界资源Rmutex用于互斥97２.利用信号量集机制解决读者—写者问题增加了一条限制：最多允许RN个读者同时读。为此，又引入了一个信号量L，并赋予初值为RN，通过执行Swait(L,1,1)操作，来控制读者读者的数目。

98varRNinteger;L,mx:semaphore:=RN,1;beginparbegin

reader:beginrepeatSwait(L,1,1);Swait(mx,1,0);┇performreadoperation┇Ssignal(L,1);untilfalse;endwriter:beginrepeatSwait(mx,1,1;L,RN,0);performwriteoperationSsignal(mx,1);untilfalse;endparendendmx=1允许多个读进程进入；mx=0阻止任何读进程进入

L>=RN时，既无读进程也无写进程99缺点：（１）易读性差（２）不利于修改和维护

(３）正确性难以保证2.5管程机制

管程的提出:

采用PV同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中一种新的同步机制--管程1002.5.1管程的基本概念

1、管程的定义

一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。

管程

局部于管程的共享变量说明

对该数据结构进行操作的一组过程

对局部于管程的数据设置初始值的语句

管程名字101管程的语法为：

typemonitor-name=monitorvariabledeclarations共享变量说明

procedureentryP1(…);begin…end;procedureentryP2(…);begin…end;┇procedureentryPn(…);begin…end;begininitializationcode初始化代码

end

组过程102

管程的主要特性：（一）模块化，一个管程是一个基本程序单位，可以单独编译（二）抽象数据类型，管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码（三）管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量(四）为了保证管程共享变量的数据完整性，规定管程互斥进入1032、条件变量

为了区别等待的原因，又引入了条件变量condition。每个独立的条件变量是和进程可能等待的不同原因相联系的。

当定义了一个条件变量时，就建立了一个队列，等待该条件的进程被连到这个队列上。

104varx,y:condition

表示：

x.waitx.signal

nonbusy:conditionnonbusy.waitnonbusy.signal例如：1052.5.2利用管程解决生产者—消费者问题

procedure-consumer：（1）put(item)过程

（2）get(item)过程

106Typeprocedure-consumer=monitor

名字varin,out,count:integer;

共享变量buffer:array[0,…,,n-1]ofitem;notfull,notempty:condition;procedureentryput(item)

管程入口

beginifcount≥nthennotfull.wait;

//阻塞等待不满的进程

//并把它连到等待不满的队列上。

buffer(in):=nextp;

in:=(in+1)modn;count:=count+1;

ifnotempty.queuethennotempty.signal;//若有等待不空的进程里有，

//则唤醒队首进程;如果没有等待不空的进程，则不操作

end//。107Procedureentyget(item)管程入口

Beginifcount≤0thennotempty.wait

//阻塞等待不空的

//进程，并把它连接到等待不空的队列上

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

count:=count-1;

//若有等待不满的队列里有进程，

//唤醒队首进程

ifnotfull.queuethennotfull.signal;endbeginin:=out:=0;count:=0;end

初始化

108在利用管程解决生产者—消费者问题时，其中的生产者和消费者可描述为：procedure:beginrepeatproduceoninteminnextp;PC.put(item);untilfalse;endConsumer:beginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end

1092.6进程通信

进程间通信意味着在进程间传送数据，也就是说，在进程之间进行信息交换。

进程通信高级通信:如果要在进程间传递大量信息则要用Send/Receive原语（高级通讯原语）低级通信:

P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息1102.6.1进程通信的类型

共享存储器系统基于共享数据结构基于共享存储区消息传递系统直接通信方式间接通信方式管道通信互斥、同步、对方是否存在1112.6.2消息传递通信的实现方法

1、直接通信方式

发送进程发消息时要指定接收进程的名字，反过来，接收时要指明发送进程的名字Send(Receiver,message);Receive(Sender,message);*对称形式：一对一*非对称形式：多对一（顾客/服务员）Receive(id,message);112repeat:┇produceaniteminnextp;┇send(consumer,nextp);untilfalse;repeatreceive(producer,nextc);┇consumetheiteminnextc;untilfalse;

生产者、消费者的通信过程如下：1132、间接通信方式信箱头信箱体信箱发送进程发消息时不指定接收进程的名字，而是指定一个中间媒介，即信箱。进程间通过信箱实现通信114Receive(mailbox,message)从指定信箱中接收一个消息。

（1）信箱的创建和撤消。（2）消息的发送和接收。Send(mailbox,message)将一个消息，发送到指定信箱。115信箱分为三类：（1）私用信箱（2）公用信箱（3）共享信箱也称共享文件方式，基于文件系统，利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质3管道通信(Pipe)1162.6.3消息传递系统中的几个问题

1、通信链路2、消息的格式 消息头：控制信息。 消息正文：发送进程实际所发送的数据。3、进程同步方式

1、发送进程阻塞，接收进程阻塞

2、发送进程不阻塞、接收进程阻塞

3、发送进程和接收进程均不阻塞1172.6.4消息缓冲队列通信机制

1、消息缓冲队列通信机制中的数据结构

(1)、消息缓冲区，可描述为：typemessagebuffer=recordsender;发送者进程标识符

size;消息长度

text;消息正文

next;指向下一个消息缓冲区的指令针

end118(2)、PCB中有关通信的数据项进程标识符信息进程控制块的信息处理机状态信息进程调度信息进程控制信息

119

利用消息缓冲队列通信机制中，在PCB中应增加的数据项为：typeprocesscontrolblock=reeord

┇mg;消息队列队首指针

mutex;消息队列互斥信号量

sm;消息队列资源信号量┇

end1202、发送原语

Proceduresend(receiver,a)begingetbuf(a.size,i);i.sender:=a.sender;i.size:=a.size;i.text:=a.text;i.next:=0;

getid(PCBset,receiver,j);wait(j.mutex);

insert(j,mg,i);signal(j,mutex);signal(j.sm);end121procedurereceive(b)beginj:=internalname;wait(j.sm);wait(j.mutex);remove(j.mg,i);signal(j.mutex);b.sender:=i.sender;b.text:=i.text;end3、接收原语1222.7线程线程的引