第三章 进程管理B.ppt

1、第三章 进程管理,进程的引入和定义 进程状态及转换 进程的产生和终止 进程的描述 进程控制 进程互斥与同步 进程间通信 管道（pipe） 线程（Thread）,3.6 进程互斥与同步,1 进程互斥 为提高资源利用率采取了程序并发执行的办法。由于多个并发进程间对有限资源的争夺和共享而可能导致程序执行结果失去封闭性。 1. 临界资源和临界区（critical section） 临界资源（critical resource） 一次只允许一个进程使用 临界区（critical section） 进程中访问临界资源的那段代码 。若在一组并发进程的各自临界区中都使用了相同的共享变量，则称这组临界区为相关临

2、界区。,例如：一个联网的航空售票系统,航空售票系统有n个终端分布在各地，通过网络连接到中心服务器。顾客通过在各地的终端购买飞机票。每个终端登录到服务器，服务器为每个终端建立一个售票进程，售票进程在卖票之前先检查总的飞机票数t是否大于或等于顾客所需飞机票数m，如果tm说明没有足量的飞机票可以卖给顾客；否则有票可以出售给顾客，每次卖飞机票给顾客后就把总的飞机票数t减去m。 /售票进程用伪码可以描述如下： sell(m) begin read（t）； if (tm) then begin 售出m张飞机票给顾客； t：=t-m； end； else write（飞机票不足）； end,考虑这种情形,并

3、发进程互斥执行的准则,并发的多个进程间在竞争资源时，如果能够避免对临界资源使用的冲突，就能保证并发进程执行结果的一致性和封闭性。即为保证执行结果的封闭性，多个并发进程共享临界区内的公有资源，但不允许并发进程同时进入临界区。 间接制约：这种由共享公有资源而造成的对并发进程执行速度的相互制约。 进程互斥：由进程间间接制约的关系导致的多个并发进程不能同时访问同一临界区 。,进程互斥执行必须满足的四个准则,（1）每次至多允许一个进程处于临界区内； （2）进程在有限时间内能够进入其临界区； （3）在其临界区之外停止的进程不应当阻塞别的进程； （4）对于有关的进程速度或者CPU数不作任何假定。 实现进程互

4、斥的方法有硬件方法，如禁止中断，特殊的机器指令等；更多的是软件方法，如P、V原语，监控程序等。,2 互斥与同步机制,1. 禁止中断（Disabling Interrupts） 是最简单的方法，让每个进程在即将进入临界区之前关中断，在执行完对共享资源的操作的那一段程序之后又开中断。 两个弊端 赋予用户进程禁止中断的权力是很危险的事，因为如果用户关闭中断后就不再打开会导致系统停止。 执行效率也会明显降低，因为操作系统不能随时切换进程。 利用禁止中断实现进程互斥 ： repeat /禁止中断 /临界区 /开中断 until false,2. TS硬件指令（Test and Set） 专门的硬件指令，

5、允许我们在一个存贮周期去测试和修改一个字的内容，或者交换两个字的内容。 function TS (var lock:Boolean)：boolean； begin TS：=lock ； lock：=true ； end 利用TS指令实现进程互斥 ： repeat while TS (lock) do skip; critical section; lock:= false; until false,使用TS指令实现互斥有几个优点： （1）可用于任意数量进程的单处理机系统或共享主存的多处理机系统； （2）实现简单，易于验证； （3）支持多个临界区，每个临界区用自己的布尔变量lock标志。 TS指

6、令的方法也存在严重缺陷： （1）由于采用的是忙等待策略，要不停地循环检测Lock值，浪费处理器资源，效率很低； （2）有可能有多个进程同时等待进入临界区，而选择哪一个进程进入临界区是随意的，这样就有可能导致某些进程长时间得不到临界区的访问权； （3）在单机系统中， 可能出现死锁。,信号量,3. 信号量和P、V原语 信号量：一个仅能由同步原语进行操作的整型变量，用来实现进程之间的互斥和同步。1965年由荷兰著名计算机科学家E.W.Dijkstra提出 。 分为 二元信号量：它仅允许取值0和1，主要用作互斥变量； 一般信号量：它允许取任意整数值，主要用于进程之间的同步。 信号量值为0时，说明没有资

7、源可用，为正整数n表示有n个同类资源可用，为负整数m则表示有|m|个进程被堵塞在该临界资源外。 操作系统利用信号量对进程和资源进行控制和管理，信号量的值仅能由P、V操作来改变。,P、V原语,P、V原语是不可中断的过程，它们在屏蔽中断的情况下连续执行。可来实现并发进程对临界区的互斥访问。 假设信号量sem的值只能由P、V操作来改变，操作系统利用它的状态对进程和资源进行管理。 P、V操作分别定义为P(sem)和V(sem) 。,P(sem)执行的动作步骤： （1）semsem1； （2）if sem0 then block ( sem ) ； /若sem0，则阻塞当前进程，将其插入等待 sem的队

8、列，调度另一进程运行。 （3）否则，返回当前进程继续执行,V(sem)执行的动作步骤： （1）semsem1； （2）if sem 0 then active (sem) / 从该信号量的等待队列中唤醒一等待进程，使之从阻塞态变成就绪态，插入就绪队列，然后再 返回当前进程继续执行或转进程调度。 （3）否则，返回当前进程继续执行,P、V操作实现两个并发进程PA、PB的互斥的例子： cobegin process PA begin P (sem)； 临界区代码SA； V (sem)； end,process PB begin P (sem)； 临界区代码 SB； V (sem)； end coen

9、d,进程同步,3 进程同步 同步一般是指两个事件的发生有着某种时序上的关系，进程同步是指系统中的几个进程为共同完成一个任务而产生的相互合作、协同运行关系。例如：,并发进程间的直接制约一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程。 进程间的同步把一组并发进程因直接制约而互相发送消息、互相合作、互相等待，使得各进程按一定的速度执行的过程。,同步例子,例如，假设有5个进程P1、P2、P3、P4、P5，它们的关系为：P1执行完成后，P2、P4才能执行，P2执行完成后，P3才能执行，P3和P4都完成后，P5才能执行。如右图所示。 使用P、V操作实现这样的流

10、程！,三个经典的同步/互斥问题,1生产者-消费者问题（producer-consumer problems） 有一个可放n件产品的缓冲区，m个生产者（producer）P1，P2，Pm和k个消费者C1，C2，Ck。每个生产者每次生产一件产品放入缓冲区，每个消费者每次从缓冲区取一件产品去消费。 其中缓冲区是生产者和消费者的共享资源，生产者和消费者对缓冲区的访问必须满足：生产者要往缓冲区中放产品时，缓冲区至少还有一个空单元可放产品；消费者要从缓冲区中取产品了消费时，缓冲区中至少还有一个产品可供消费。可以看出这是一个典型的同步问题。,生产者消费者进程描述,求解 环形缓冲区,生产者与消费者关系的形式描

11、述，设： 公用信号量 mutex ：初值为1，用于实现临界区的互斥； 生产者私用信号量empty：初值为n，指示空缓冲块数目； 消费者私用信号量full：初值为0，指示满缓冲块数目； 整型量in和out：初值均为0，in 指示空缓冲块序号头指针，out指示满缓冲块序号头指针。,process consumer j ( j=1,2, , n ) begin repeat P ( full ); P ( mutex ); P：= buffer out； Out：= (out+1) mod n ； V ( mutex )； V (empty )； until false end,process pr

12、oducer i ( i=1,2, , m ) begin repeat produce a product ； P (empty) ； P (mutex) ； Buffer in：=product ； in：= (in+1) mod n ； V (mutex) ； V (full) ； until false end；,begin mutex, empty, full：semaphore； buffer：array 0n-1 of integer； in,out：intege； in：=out：=0 ； mutex：=1； empty：=n； full：=0； begin cobegin p

13、rocess producer i ( i=1,2, , m ) process consumer j ( j=1,2, , n ) coend ； end； end,2读者-写者（reader-writer）问题 进程共享一个数据区，数据区可以是一个文件、一块内存空间、或一组寄存器。其中有些进程只能读数据区中的数据，而另外一些进程只能写数据区。把只能读数据区的进程叫做“读者（reader）”，只能写数据区的进程叫做“写者（writer）”。而且reader和writer要满足：多个reader可同时读数据区；任一时刻只能有一个writer可以写数据区；reader和writer不能同时对数据

14、区进行操作。 读者和读者之间是可以同时访问数据区的，不存在制约关系。一次只能有一个写者在写数据区，写者与写者之间是互斥的制约关系。读者和写者之间也是存在互斥的制约关系。,一个写者在写数据区时，只有它一个进程能访问数据区，可以用一个信号量来阻塞其它想访问数据区的进程。为了使得读者能够同时读数据区，引入一个计数变量readcount来记录同时读数据区的进程数。readcount是读者之间的共享变量，所以对它的存取也要互斥进程。 设：变量readcount 记录当前正在访问该对象的读者个数； 互斥信号量mut 用来互斥对readcounnt的修改； 互斥信号量wmut 用于互斥写者，它也可由当前第一

15、个要求访问该对象的读者和最后一个退出访问的读者使用，但它不被中间的那些读者使用。,var mut, wmut：semaphore； mut,：=1；wmut：=1； readcount：integer； readcount：=0； begin cobegin process reader i (i=1,2, m) process writer j (j=1,2, n) coend； end,process reader i (i=1,2, m) begin repeat P (mut )； if readcount=0 then P ( wmut )； readcount：=readcount

16、+1； V ( mut )； Perform read operation； /实行读操作/ P ( mut )； Readcount：=readcount-1； if readcount=0 then V (wmut)； V ( mut )； until false； end；,process writer j (j=1,2, n) begin repeat P (wmut)； Perform write operation； /实行写操作/ V (wmu)； until false; end；,哲学家就餐问题,3哲学家就餐问题（The Dining Philosophers Problem

17、） 五个哲学家在一起思考和用餐。这些哲学家共用一张圆桌，周围放有五把椅子，每人座一张，在圆桌上有五个碗和五支筷子。当一个哲学家思考问题时，他不与同事交谈，饥饿时，便去试图取用其左右最靠近他的两支筷子，但他可能一支都拿不到，只有当他拿到两支筷子时才能用餐，用餐完毕，又将筷子放回原处，又继续思考。如何使这五个哲学家保持同步：既能进行思考又不至于饿死。,3. 7 进程间通信,进程间通信:进程间的信息交换（InterProcess Communication,IPC） 低级通信 交换少量控制信息 ， 例如：进程互斥与同步 。 高级通信 交换大量数据信息。 共享存储器 消息传递,1 共享存储器（shar

18、ed memory）,共享存储器方式 把需要交换的信息发送到某一约定的存储区域，接收进程从该区域读取信息，从而实现两个或两个以上进程间的通信的这种通信方式 。 （1）基于共享数据结构的通信方式 这里的数据结构是系统为保证进程正常运行而设置的专门机制，它可以是一个寄存器、一组寄存器、一个数组、一个链表、一个记录等等。进程由共享数据结构中取得数据，共享数据结构的设置由程序员负责。这种通信方式效率低，适用于交换数据量不大的通信。 （2）基于共享存储区的通信方式 在主存中划定一块专门的区域来作为进程共享的存储区。进程通过对共享存储区的数据进行读或写来实现通信。,虚存的共享区虚地址既出现在进程A有出现在

19、进程B中，因此，A，B都可以访问共享区，但访问地址又被影射成主存地址。A进程把消息放入共享区，B进程从共享区读取消息，实现两个进程的通信。如果共享区地址出现在另外的进程空间，则这个进程也就参与了A，B进程的通信。,例如：UNIX系统中共享存储区的通信,2 消息传递（message passing）,消息就是这样一组数据，它除了表示进程间所交换的大量信息之外，还具有两相互通信的进程地位平等的意思。消息一般由4个部分组成：发送进程名、接收进程名、数据及有关数据的操作。 消息传递按其实现方式不同又可分为直接通信和间接通信,直接通信方式发送进程直接将消息发送给接收进程，并将它挂在接收进程的消息缓冲队列

20、上。接收进程从自己的消息缓冲队列中取得消息。消息缓冲就是一种直接通信方式。 间接通信方式发送进程将消息发送到某种中间实体，接收进程再从中间实体中取得消息。这种中间实体一般称为信箱（mailbox），故这种通信方式也称为信箱方式。,消息缓冲:基本思想是：由系统管理一组用于通信的消息缓冲存储区，即利用内存中设立的一个大的缓冲区作为公用消息缓冲池实现进程之间的信息交换。,消息队列属于临界资源，对临界资源的访问需要互斥进行。为此在PCB中设置了一个用于互斥的信号量mutex，每当进程要进入临界区时在信号量mutex上执行P操作，退出临界区时在信号量mutex上执行V操作。 为了实现进程间的通信，系统提

21、供了发送原语和接收原语。发送原语“send”和接收原语“receive”的格式如下： send（destination，ms） 其中，destination是接收消息的进程名，ms是发送区的内存地址； receive（source，mr） 其中，source是发送者的进程名，mr是接收区的内存地址。 若m表示要发送或接收的消息，则发送原语send（destination，ms）和接收原语receive（source，mr）表示：,send (destination,ms) begin 向系统申请一个消息缓冲区； P (mut )； 将发送区ms处的消息送入新申请的消息缓冲区； 把消息缓冲区挂入

22、接收进程的消息队列； V (mut)； V (Sn)； end,receive (source,mr) begin P (Sn)； P (mut )； 摘下消息队列中的消息； 将消息从缓冲区复制到接收区的mr 处； 释放缓冲区； V (mut)； end,信箱通信,信箱通信由发送进程建立一个与接收进程链接的信箱。信箱作为通信得中间实体，发送进程把消息发往信箱，接收进程从信箱取出消息，从而完成信息交换。如：,信箱通信,信箱通信中发送进程和接收进程要满足如下条件： 发送进程发送消息时，信箱中至少要有一个空的格子供存放消息； 接收进程接收消息时，信箱中至少要有一个格子有消息。可以看出，发送进程和接收

23、进程之间需要进行同步。,send begin P (avail ); 把信件放入position标记的空闲格子中； positionpostion1； V (full )； end,receive begin P (full )； 取走第一个格子中的信件； 把后面格子中的信件往前顺次移动； positionpostion1； V (avail)； end,3. 8 管道（pipe）,前面进程之间的通信方式和同步机构（P、V操作和消息通信等），不能满足大量的数据信息传递，使用的同步机制是低级的，用它们很难表示更为复杂的并发性问题。并且使用消息通信需要占用较多的存储资源和花费较多的管理代价，在内存

24、中由于各进程对数据访问的随意性，需要靠其他的机构实施进程间的同步与互斥。,管道实质上是一个文件。在逻辑上被看作是管道文件，在物理上则由文件系统的高速缓冲区构成。管道文件的最大长度为10个存储块。逻辑上构成了一个线性空间。,pipe 文件每次最多只能提供4KB缓冲，但一组协同进程之间利用pipe 传送数据时，数据的长度往往大于4KB。解决此问题的基本思路是在写pipe 的程序中，将数据进行分割，每次最多写4KB, 写完后该进程睡眠等待，直到读进程把pipe 文件中的数据取完后，判明有写进程等待时，就将写进程唤醒，使它继续写下一批数据。当读进程无数据可读时，也要睡眠等待。写进程写完一批数据后，判明

25、有读进程等待时，就将读进程唤醒，使它继续读下一批数据。如此同步，直到把所有数据传送完毕。 读进程和写进程之间，存在着互斥与同步问题。这里的互斥是指，在任何一时刻只允许一个进程访问管道。而同步是指写进程和读进程的读、写速度应当协调。,3.9 线程（Thread）,进程实际上包括两种不同的独立概念： 一是与资源的所有权有关， 二是与执行有关， 由此提出了比进程更小的能独立运行的基本单位线程。这种区别的发现导致了操作系统结构的发展，出现了线程这种形式的结构单元。 引入进程的目的，是为了使多个任务并发，以改善资源利用率和提高系统的吞吐量； 引入线程的目的，主要是为了提高系统的执行效率，减少处理机空转时

26、间和调度切换时间以及便于系统管理，使操作系统具有更好的并发性。,线程进程内一个相对独立的并具有可调度特性的执行单元。 线程自己基本不拥有系统资源，只拥有一些在运行过程中必不可少的资源，如：程序计数器、寄存器和栈。线程可与它同属一个进程和其他线程共享进程所拥有的全部资源。 线程的概念最突出的作用是其在单进程内多线程的组织中的作用，提供了对单个进程中多条控制线索的支持。,（1）进程与进程之间的关系 在一个任务下的两个进程都是拥有资源的，各自为一个独立单位，两个进程间的关系比较疏远，各自的进程是在自己独有的地址空间执行，不但寄存器和堆栈是独有的，静态数据、动态堆和程序代码也相互独立。 （2）线程与线

27、程之间的关系 两线程从属同一进程，它们共享同一地址空间，静态数据、动态堆以及程序代码为各线程共享，只保持自己的控制流而独有寄存器和堆栈。 （3）进程和线程的关系 进程作为独立的实体，它为线程提供运行的资源并构成静态环境。线程是处理机调度的基本单位。,线程的5个属性： （1）每一个线程有一个唯一的标识符和一张线程描述表，线程描述表相当于进程的PCB，其中记录了线程执行时的寄存器和堆栈等现场状况。 （2）不同的线程可以共享相同的程序代码。 （3）同一进程内的各个线程共享进程的地址空间。 （4）线程是处理器的独立调度单位，多个线程可以并发执行。 （5）线程也有它的生命周期，从建立经过运行直到消亡。线

28、程同样有就绪、运行和等待等几个基本状态的转换。,2 进程与线程,线程具有进程的许多的特征，所以又称线程为轻型进程，而把传统的进程称为重型进程。下面我们从资源的分配、调度、并发和系统的开销等方面来比较进程和线程。 （1）进程是资源分配单位和拥有单位，线程自己不拥有系统资源，但它可以访问其隶属进程的资源。比如，一个进程的代码段，数据以及系统资源，如已打开的文件、I/O设备等，可供同一进程下的所有线程使用,（2）进程是资源的拥有单位，线程是作为调度和分配的基本单位，即处理机是分配给线程，在同一进程中，线程的切换不会引起进程的切换，在由一个进程中的线程切换到另一个进程中的线程时才会引起进程的切换。 （