2005操作系统第五章

1、第五章 进程管理,5.1、为什么要引入“进程”的概念 5.1.1、从顺序程序设计谈起,作业执行顺序,作业 l,作业 n,作业 i,I l,C l,P l,P i,C i,I i,P n,C n,I n,程序的顺序执行具有如下特性： （1）处理机严格地顺序执行程序规定的动 作. （2）一个程序在机器中执行时,它独占全机 资源. （3）程序的执行结果与其执行速度无关. 程序的封闭性和可再现性.,5.1.2、程序的并发执行和资源共享 1、程序的并发执行,I 1,C2,p4,P3,P2,P1,C4,C3,C1,I 4,I 3,I 2,5.1.2、程序的并发执行和资源共享 2、资源共享,5.1.3、程序

2、并发执行的特性 1、失去了程序的封闭性 begin count : integer; count :=0; cobegin observer begin L1: observe next car; count := count +1 go to L1 end,reporter begin L2 : print count ; count := 0 go to L2 end coend end,count :=count +1 ; print count ; count:=0 ; print count ; count:=0; count:=count+1; print count ; coun

3、t:= count +1 ; count:=0;,与时间有关的错误 原因：由于并发进程执行处理序列的随机性（即相对速度事先无法控制） 表现：结果不唯一（结果不正确、数据不一致）和永远等待（死锁）,例：一飞机订票系统，两个终端，运行T1、T2进程 T1 : T2: . . Read(x); Read(x); if x=1 then if x=1 then x:=x-1; x:=x-1; write(x); write(x);,2. 程序和机器执行程序的活动不再一一对应 3. 并发程序间的相互制约 直接制约关系 间接制约关系,5.1.4、进程概念的引入 进程是程序的一次执行,该程序可以与其它程序并

4、发执行,5.2、进程的表示和调度状态 5.2.1 进程的表示 1. 进程的组成 程序 数据集合 进程控制块,5.2.1 进程的表示 2. 进程控制块 (1) 进程标识名或标识数 (2)位置信息 (3)状态信息 (4)进程的优先级 (5)进程现场保护区 (6)资源清单 (7)队列指针或链接字,5.2.2 进程的调度状态 1. 进程的基本调度状态 (1)运行状态 (2)就绪状态 (3)阻塞状态,就绪,运行,阻塞,调度,时间片到,I/O完成,I/O请求,5.2.2 进程的调度状态 2. 细分的进程调度状态,5.3 进程的控制 5.3.1 进程的控制机构 1.原语的定义 由若干条机器指令构成的并用以完

5、成特定功能的一段程序，而这段程序在执行期间是不可分割的。 2. 进程控制原语,5.3 进程的控制 5.3.2 进程控制原语 1. 进程的建立 2. 状态转换原语 （1）挂起原语 （2）激活原语 （3）阻塞原语和唤醒原语 3. 进程的撤消,5.4 进程调度 5.4.1 交通控制程序和进程调度程序 1. 交通控制程序 2. 进程调度程序 3. 进程调度程序的功能 （1）记住系统中所有进程的状态、优先数和资源需求情况。 （2）确定调度算法，决定把处理机分配给哪个进程和分配多长时间。 （3）分配处理机给进程。,5.4 进程调度 5.4.2 进程调度算法的设计 1. 引进进程调度的时机 2. 进程调度方

6、式 （1）非剥夺方式 （2）剥夺方式 3. 进程调度算法的选择 优先数法和时间片轮转法 4. 进程队列的组织 （1）线性表 （2）链接表或进程队列,5.4 进程调度 5.4.3 常用的进程调度算法 1 .静态优先级法 （1）按进程类型确定 （2）按作业的资源要求确定 （3）按作业到达时间确定 （4）按用户类型和要求确定 2. 动态优先级法 3. 时间片轮转法 （1）简单轮转法 （2）可变时间片轮转法 （3）多队列轮转法,5.4 进程调度 5.4.4 作业 进程和程序之间的区别和联系 1.用户作业 进程和程序之间的联系 2. 进程和程序的区别,进程与程序的区别和相互关系 ：（1）动态性和静态性。

7、 （2）从结构上看每个进程的实体都是由程序段和相应的数据段两部分构成的，这一特征与程序的含义相近。（3）一个进程可以涉及到一个或几个程序的执行；反之一程序可以对应多个进程，即同一程序段可在不同数据集合上运行，可构成不同的进程 。（4）并发性。 （5）进程具有创建其他进程的功能。 （6）操作系统中的每一个程序都是在一个进程现场中运行的。,5.5 进程通讯 5.5.1 进程间的同步和互斥 1.进程间的同步,正常行车,到站停车,开车,售票员,司机,售票,开车门,关车门,司机和售票员的同步,5.5.1 进程间的同步和互斥 1.进程间的同步,进程p1,计算func1(x),进程p2算 完func2(y)

8、,y,取出p2计算结果,进程p2,计算func2(y),置计算完标志,终止,2、进程的互斥,进程A,（1）请求资源R,（3）释放资源R,R,分配,进程B,（2）请求资源R,（4）释放资源R,拒绝,2、进程的互斥,P1: r1:=count; P2: r2 :=count; r1:= r1+1; r2 :=r2+1; count := r1; count :=r2; P1: r1 :=count; P2: r2 :=count; P1: r1 :=r1+1; count :=r1; P2: r2 :=r2+1; count :=r2;,2、进程的互斥,由于各进程要求共享资源，而有些资源需要互斥使

9、用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥 临界资源：系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量,互斥和临界区：,使用互斥区的原则： 有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入 无空等待：不允许两个以上的进程同时进入互斥区 多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待 有限等待：任何进入互斥区的要求应在有限的时间内得到满足 让权等待：处于等待状态的进程应放弃占用CPU,3.实现临界区互斥的锁操作法 使用临界区的三要求：,（1）一次至多一个进程能够在它的临界区 （

10、2）不能让一个进程无限地留在它的临界去内； （3）不能强迫一个进程无限地等待进入它的临界区。特别，进入临界区的任一进程不能妨碍正等待进入的其他进程的进展。,lock和unlock 大部分同步方案均采用某个物理实体（如锁、信号灯等）实现通信，进程通信原语中关锁（lock）和开锁（unlock）是最简单的原语。在这两个原语中设置一个公共变量x代表某个临界资源的状态。如：x=0，表示资源可用，x=1，表示资源正在使用。 关锁原语1ock（x）： L：if x1 then goto L else x：=1； 开锁原语unlock（x）： x：=0；,开锁和关锁程序流程图,5.5.2信号量和pv操作,1

11、 信号量及PV操作 信号量的使用： 必须置一次且只能置一次初值 初值不能为负数 只能执行P、V操作,P、V操作为原语操作 原语：是由若干条机器指令构成的完成某种特定功能的一段程序，具有不可分割性（即原语的执行不允许被中断）,P操作：,Procedure p(var s:semaphore); begin s:=s-1; if s0 then W(s) end;p W(s)表示把调用过程的进程置为等待信号量s的状态。,V操作,Procedure v(var s:semaphore); begin s:=s+1; if s=0 then R(s) end;v V(s)表示释放一个等待信号量s的进程

12、。,s:semaphore; end; s:=1; Cobegin coend; procedure pi begin p(s); 临界区； v(s);,2.利用信号量实现进程的互斥 例1 对共享变量count的访问 begin count:integer; s:semaphore; count:=0; s:=1;,例1 对共享变量count的访问,Cobegin process p1 R1:register; begin p(s) R1:=count; R1:=R1+1; count:=R1 v(s) end;,process p2 R2:register; begin p(s) R2:=c

13、ount; R2:=R2+1; count:=R2 v(s) end; coend; end;,例2 飞机售票系统,begin s:semaphore s:=1 Cobegin process pi(i=1,2,n) Begin 按旅客订票要求找到Xk; p(s) Ri:=Xk;,if Ri1 then begin Ri:=Ri-1; Xk:=Ri v(s) 输出一张票 end else begin v(s); 输出票已售完 end end; coend; end;,2.利用信号量实现进程的同步 例1,正常行车,到站停车,离站开车,售票员,司机,售票,开车门,关车门,司机和售票员的同步,V(s

14、2) P(s1),P(s2),V(s1),2.利用信号量实现进程的同步 例2,启动读卡机,读卡片送入缓冲区,进程B,进程A,从缓冲区取卡片信息,加工卡片信息,信号量s1表示缓冲区是否有卡片信息, 信号量s2表示缓冲区信息是否被取走,其初值均为0 。,V(s1) P(s2),P(s1),V(s2),PV操作实现同步：,P.V操作讨论 1) 信号量的物理含义： S0表示有S个资源可用 S=0表示无资源可用 S0则表示有| S |个进程在等待 P(S):表示申请一个资源 V(S)表示释放一个资源。信号量的初值应该大于等于0,P.V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们

15、同处于同一进程 当为同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要, 先同步P操作再互斥P操作；而两个V操作无关紧要。,P.V操作的优缺点,优点： 简单，而且表达能力强（用P.V操作可解决任何同步互斥问题） 缺点： 不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂,补充题: 1.桌上有一空盘,允许存放一只水果。爸爸可向盘中放苹果,也可向盘中放桔子,儿子专等吃盘中桔子,女儿专等吃盘中苹果。规定当盘空时一次只能放一个水果供吃者取用，请用P V原语实现爸爸 儿子 女儿三个并发进程的同步。,信号量s表示盘子是否为空，其初值为1

16、； 信号量so表示盘中是否有桔子，其初值为0； 信号量sa表示盘中是否有苹果，其初值为0； int s=1; int so=0; int sa=0;,main( ) cobegin father( ); son( ); daughter( ); coend ,father( ) while(1) p(s); 将水果放入盘中； if（放入的是桔子） v(so); else v(sa); ,son( ) while(1) p(so); 从盘中取出桔子； v(s); 吃桔子； ,daughter( ) while(1) p(sa); 从盘中取出苹果； v(s); 吃苹果； ,补充题: 2.桌上有一空

17、盘,最多存放两个水果。每次只能放入或取出一个水果，爸爸专向盘中放苹果,妈妈专向盘中放桔子,两个儿子专等吃盘中桔子,两个女儿专等吃盘中苹果。请用P V原语实现爸爸 妈妈 儿子 女儿间的同步与互斥关系。,信号量mutex控制对盘子的互斥访问，初值为1； 信号量orange表示盘中桔子数，其初值为0； 信号量apple表示盘中苹果数，其初值为0； 盘子为互斥资源，可以放两个水果，因此设empty初值为2 。,爸爸 L1: P (empty) P (mutex) 放苹果 V (mutex) V (apple) GOTO L1,妈妈 L2: P (empty) P (mutex) 放桔子 V (mute

18、x) V (orange) GOTO L2,女儿 L3: P (apple) P (mutex) 取苹果 V (mutex) V (empty) GOTO L3,儿子 L4: P (orange) P (mutex) 取桔子 V (mutex) V (empty) GOTO L4,补充题: 3. 兄弟俩共同使用一个存折amount初值为0，每次限存或取10元，存钱与取钱的进程分别为：,存钱 m1amount m1m1+10 amount m1,取钱 m2amount m2m2-10 amount m2,由于兄弟俩可能同时存钱或取钱，因此两个进程是并发的， 若哥哥先存了两次钱，但在第三次存钱的时

19、候，弟弟正在取钱，请问最后存折上可能出现的值？如何用P V操作实现两并发进程的互斥执行？,哥哥存两次钱后，amount=20，第3次存钱时，弟弟正在取钱，因没有对amount互斥操作，故可能会发生错误，amount上出现的值与两个进程相对执行速度有关： （1）若取钱进程先结束存钱进程才开始，则最后amount为20元 （2）若存钱进程先结束取钱进程才开始，则最后amount为20元 （3）若两进程交替执行时，关键在于最后被执行的语句是amount m1还是amount m2。 若先amount m1，后amount m2，则amount=10 若先amount m2，后amount m1，则a

20、mount=30,设置信号量S(初值为1）控制两进程时变量amount的互斥使用，进程为：,存钱 P(s) m1amount m1m1+10 amount m1 V(s),取钱 P(s) m2amount m2m2-10 amount m2 V(s),补充题: 4. A,B两个并发进程，它们共享一个临界区，其执行临界 区的算法如下：,A进程 L1: 临界区 V(s1) P(s2) GOTO L1,B进程 L2: P(s1) 临界区 V(s2) GOTO L2,试判断算法是否有错？请说明理由，如有错，请改正。 S1,S2的初值均为0。,A进程 L1: P(mutex) 临界区 V(mutex)

21、GOTO L1,B进程 L2: P(mutex) 临界区 V(mutex ) GOTO L2,主要是因为在这里使用的是同步控制，应该为互斥控制， 如下: (mutex初值为1),补充题: 5. 用PV操作处理生产者和消费者问题如下： mutex初值为1；empty初值为n； full初值为0,生产者 L1: 生产产品 P(empty) P(mutex) 产品装入缓冲区 V(full) V(mutex) GOTO L1,消费者 L2: P(full) P(mutex) 取出产品 V(empty) V(mutex) GOTO L2,（1）信号量mutex, empty, full 的作用是什么？

22、（2）为什么P操作的顺序不能调换？,补充题: 6. 在测量控制系统中，数据采集任务把所采集的数据送入一单缓冲区；计算任务从该单缓冲区中取出数据进行计算。试写出利用信号量机制实现两者共享单缓冲区的同步算法。,信号量sf：表示缓冲区中是否有可供打印的计算结果， 其初值为0； 信号量se：表示缓冲区有无空位置存放新的信息，其 初值为1； int se=1; int sf=0; main( ) cobegin get( ); compute( ); coend ,get ( ) while (采集工作未完成） 采集一个数据； p(se); 将数据送入缓冲区中； v(sf); ,compute ( )

23、while (计算工作未完成） p(sf); 从缓冲区中取出数据； v(se); 进行数据计算； ,1生产者与消费者问题,Dijkstra把广义同步问题抽象成一种“生产者与消费者问题”（Producer-consumer-relationship）的抽象模型。事实上，计算机系统中的许多问题都可归结为生产者与消费者问题，生产者与消费者可以通过一个环形缓冲池（见图3.8）联系起来，环形缓冲池由几个大小相等的缓冲块组成，每个缓冲块容纳一个产品。每个生产者可不断地每次往缓冲池中送一个生产产品，而每个消费者则可不断地每次从缓冲池中取出一个产品。,下一页,图3.8 环形缓冲池,下一页,下面给出基于环形缓冲

24、区的生产者与消费者关系的形式描述，设： （1）公用信号量mutex：初值为1，用于实现临界区互斥。 （2）生产者私用信号量empty：初值为n，指示空缓冲块数目。 （3）消费者私用信号量full：初值为0，指示满缓冲块数目。 （4）整型量i和j初值均为0，i指示首空缓冲块序号，j指示首满缓冲块序号。 模块 设计如下：,下一页,Var mutex，empty，full：semaphore; i,j:integer；buffer：array 0n一1 of item； Procedure producer; 生产者进程 begin while true do begin produce a pro

25、duct; P(empty);,下一页,P(mutex); Buffer (i)：Product; i：(i+1) mod n； V(mutex); V(full) end end; procedure consumer; 消费者进程,下一页,begin While true do begin P(full)； P(mutex) goods：buffer(j); j：(j+1) mod n; V(mutex); V(empty); Consume a product; end,下一页,end; begin seminitial ; i:j:0; cobegin producer； consum

26、er； coend end,下一页,进程的同步,经典的生产者消费者问题 生产者 消费者,读者写者问题,有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作,第一类：读者优先,如果读者来： 1）无读者、写者，新读者可以读 2）有写者等，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等 如果写者来： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待,信号量s：用于读者与写者之间或写者与写者之间的互斥， 初值为“1”。 变量 rc 表示当前正在读的读者个数。 信号量sr 用于互斥访问

27、变量 rc 。 Begin s, sr :semaphore; rc: integer; s := sr :=1; rc :=0;,cobegin process reader i ( i=1,2,3,m) begin p(sr); rc := rc+1; if rc =1 then p(s); v(sr) read file F; p(sr); rc :=rc-1; if rc=0 then v(s); v(sr) end;,process writer j ( j=1,2,3,k) begin p(s); writer file F; v(s); end; coend; end,第二类读者

28、写者问题：,写者优先 条件： 1）多个读者可以同时进行读 2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行） 3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）,信号量s：用于读者与写者之间或写者与写者之间的互斥， 初值为“1”。 信号量sn: 表示系统中最多有n个进程可同时进行读操作， 初值为n。 Begin s, sn :semaphore; s := 1; sn :=n;,cobegin process reader i ( i=1,2,3,n) begin p(s); p(sn); v(s) read file F; v(sn) end;,process

29、 writer j ( j=1,2,3,k) begin p(s); for i:= 1 to n do p(sn); writer file F; for i:= 1 to n do v(sn); v(s); end; coend; end,课堂练习：,1、某产品的加工有三道工序A、B、C，有两个物品筐，A工序每次生产一个成品放到B1筐中，B1最多放n个成品。B工序从B1筐中拿A工序的一个成品继续加工，并把加工后的一个成品放到B2筐中，B2最多放m个成品。C工序从B2筐中拿B工序的一个成品继续加工，并把加工后的一个成品出厂销售。为防止产品存入已经满的筐或从空筐中取产品、或重复取产品，如果将每个工序当作一个进程试用PV操作实现他们之间的相互制约。,分析： 存在A和B的同步 B和C的同步 Begin s1,s2,s3,s4:semaphore; r1,r2,t1,t2:integer; s1:=n;s2:=0;s3:=m;s4:=0; r1:=0;r2:=0;t1:=0;t2:=0; B1:array 0.n-1 of integer; B2:array 0.m-1 of integer;,Cobegin process A begin L1:生产一件产品； P（s1); B