《2005操作系统第五章》由会员分享，可在线阅读，更多相关《2005操作系统第五章（84页珍藏版）》请在金锄头文库上搜索。
1、第五章 进程管理5.1、为什么要引入“进程”的概念5.1.1、从顺序程序设计谈起作业执行顺序作业 l作业 n作业 iI lC lP lP iC iI iP nC nI n程序的顺序执行具有如下特性：（1）处理机严格地顺序执行程序规定的动 作.（2）一个程序在机器中执行时,它独占全机 资源.（3）程序的执行结果与其执行速度无关. 程序的封闭性和可再现性.5.1.2、程序的并发执行和资源共享1、程序的并发执行I 1C2p4P3P2P1C4C3C1I 4I 3I 25.1.2、程序的并发执行和资源共享2、资源共享5.1.3、程序并发执行的特性1、失去了程序的封闭性begin count : inte
2、ger; count :=0;cobegin observer begin L1: observe next car; count := count +1 go to L1 endreporterbegin L2 : print count ; count := 0 go to L2 end coendend(1)count :=count +1 ; print count ; count:=0 ;(2)print count ; count:=0; count:=count+1;(3)print count ; count:= count +1 ; count:=0;执行序列(1)(2)(3
3、)打印的值n+1nn执行后的值010与时间有关的错误原因：由于并发进程执行处理序列的随机性（即相对速度事先无法控制）表现：结果不唯一（结果不正确、数据不一致）和永远等待（死锁）例：一飞机订票系统，两个终端，运行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、进程概念的引入 进程是程序的一次执行,该程序可以与其它程序并发执行 5.2、进程的表示和调度状态
4、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.原语的定义 由若干条机器指令构成的并用以完成特定功能的一段程序，而这段程序在执行期间是不可分割的。2
5、. 进程控制原语 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. 进程调度方式 （1）非剥夺方式 （2）剥夺方式3. 进程调度算法的选择 优先数法和时间片轮转法
6、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）动态性和静态性。 （2）从结构上看每个进程的实体都是由程序段和相应的数据段两部分构成的，这一特征与程序的含义相近。（3）一个
7、进程可以涉及到一个或几个程序的执行；反之一程序可以对应多个进程，即同一程序段可在不同数据集合上运行，可构成不同的进程 。（4）并发性。 （5）进程具有创建其他进程的功能。 （6）操作系统中的每一个程序都是在一个进程现场中运行的。 5.5 进程通讯5.5.1 进程间的同步和互斥1.进程间的同步 正常行车到站停车开车售票员司机售票开车门关车门司机和售票员的同步5.5.1 进程间的同步和互斥1.进程间的同步 进程p1计算func1(x)进程p2算完func2(y)y取出p2计算结果进程p2计算func2(y)置计算完标志终止2、进程的互斥进程A（1）请求资源R（3）释放资源RR分配进程B（2）请求资
8、源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、让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入无空等待：不允许两个以上的进程同时进入互斥区多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU3.实现临界区互斥的锁操作法 使用临界区的三要求：（1）一次至多一个进程能够在它的临界区（2）不能让一个进程无限地留在它的临界去内；（3）不能强迫一个进程无限地等待进入它的临界区。特别，进入临界区的任一进程不能妨碍正等待进入的其他进程的进展。lock和unlock大部分同步方案均采用某个物理实体（
10、如锁、信号灯等）实现大部分同步方案均采用某个物理实体（如锁、信号灯等）实现通信，进程通信原语中关锁（通信，进程通信原语中关锁（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信号
11、量和pv操作1 信号量及PV操作信号量的使用： 必须置一次且只能置一次初值 初值不能为负数 只能执行P、V操作P、V操作为原语操作原语：是由若干条机器指令构成的完成某种特定功能的一段程序，具有不可分割性（即原语的执行不允许被中断） P操作：Procedure p(var s:semaphore); begin s:=s-1; if s0 then W(s) end;pW(s)表示把调用过程的进程置为等待信号量s的状态。V操作Procedure v(var s:semaphore); begin s:=s+1; if s0表示有S个资源可用S=0表示无资源可用S0则表示有| S |个进程在等待P
12、(S):表示申请一个资源 V(S)表示释放一个资源。信号量的初值应该大于等于0P.V操作必须成对出现，有一个P操作就一定有一个V操作当为互斥操作时，它们同处于同一进程当为同步操作时，则不在同一进程中出现如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要, 先同步P操作再互斥P操作；而两个V操作无关紧要。P.V操作的优缺点优点：简单，而且表达能力强（用P.V操作可解决任何同步互斥问题）缺点：不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂 补充题:1.桌上有一空盘,允许存放一只水果。爸爸可向盘中放苹果,也可向盘中放桔子,儿子专等吃盘中桔子,女儿专等吃盘中苹果
13、。规定当盘空时一次只能放一个水果供吃者取用，请用P V原语实现爸爸 儿子 女儿三个并发进程的同步。 信号量s表示盘子是否为空，其初值为1；信号量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); 吃桔子；
14、 daughter( ) while(1) p(sa);从盘中取出苹果； v(s); 吃苹果； 补充题:2.桌上有一空盘,最多存放两个水果。每次只能放入或取出一个水果，爸爸专向盘中放苹果,妈妈专向盘中放桔子,两个儿子专等吃盘中桔子,两个女儿专等吃盘中苹果。请用P V原语实现爸爸 妈妈 儿子 女儿间的同步与互斥关系。信号量mutex控制对盘子的互斥访问，初值为1；信号量orange表示盘中桔子数，其初值为0；信号量apple表示盘中苹果数，其初值为0；盘子为互斥资源，可以放两个水果，因此设empty初值为2 。爸爸L1: P (empty) P (mutex) 放苹果 V (mutex) V (
15、apple) GOTO L1妈妈L2: P (empty) P (mutex) 放桔子 V (mutex) 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元，存钱与取钱的进程分别为：存钱m1amountm1m1+10amount m1取钱m2amountm2m2-10amount m2由于兄弟俩可能同时
16、存钱或取钱，因此两个进程是并发的，若哥哥先存了两次钱，但在第三次存钱的时候，弟弟正在取钱，请问最后存折上可能出现的值？如何用P V操作实现两并发进程的互斥执行？ 哥哥存两次钱后，amount=20，第3次存钱时，弟弟正在取钱，因没有对amount互斥操作，故可能会发生错误，amount上出现的值与两个进程相对执行速度有关：（1）若取钱进程先结束存钱进程才开始，则最后amount为20元（2）若存钱进程先结束取钱进程才开始，则最后amount为20元（3）若两进程交替执行时，关键在于最后被执行的语句是amount m1还是amount m2。 若先amount m1，后amount m2，则am
17、ount=10 若先amount m2，后amount m1，则amount=30 设置信号量S(初值为1）控制两进程时变量amount的互斥使用，进程为：存钱 P(s)m1amountm1m1+10amount m1 V(s)取钱 P(s)m2amountm2m2-10amount m2 V(s)补充题:4. A,B两个并发进程，它们共享一个临界区，其执行临界区的算法如下： A进程L1: 临界区 V(s1) P(s2) GOTO L1B进程L2: P(s1) 临界区 V(s2)GOTO L2 试判断算法是否有错？请说明理由，如有错，请改正。S1,S2的初值均为0。 A进程L1: P(mute
18、x) 临界区 V(mutex) GOTO L1B进程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 的作
19、用是什么？（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 ( )
20、 while (计算工作未完成） p(sf); 从缓冲区中取出数据； v(se); 进行数据计算； 1生产者与消费者问题 Dijkstra把广义同步问题抽象成一种“生产者与消费者问题”（Producer-consumer-relationship）的抽象模型。事实上，计算机系统中的许多问题都可归结为生产者与消费者问题，生产者与消费者可以通过一个环形缓冲池（见图3.8）联系起来，环形缓冲池由几个大小相等的缓冲块组成，每个缓冲块容纳一个产品。每个生产者可不断地每次往缓冲池中送一个生产产品，而每个消费者则可不断地每次从缓冲池中取出一个产品。 下一页下一页图图3.8 环形缓冲池环形缓冲池下一页下一页下
21、面给出基于环形缓冲区的生产者与消费者关系的形式描述，设：（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 produc
22、e a product; 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 prod
23、ucer； consumer； coend end下一页下一页进程的同步 经典的生产者消费者问题 生产者 消费者读者写者问题有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作第一类：读者优先如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待 信号量s：用于读者与写者之间或写者与写者之间的互斥， 初值为“1”。 变量 rc 表示当前正在读的读者个数。 信号量sr 用于互斥
24、访问变量 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 第二类读者
25、写者问题：写者优先条件：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 write
26、r 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工序的一个成品继续加工，并把加工后的一个成品出厂销售。为防止产品存入已经满的筐或从空筐中取产品、或重复取产品，如果将每个工序当作一个进
27、程试用PV操作实现他们之间的相互制约。分析：存在A和B的同步B和C的同步Begins1,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); B1r1:=产品； r1:=(r1+1) mod n ; V(s2); goto L1; end;s1表示B1筐中空闲的缓冲区个数,r1表示B1筐存放
28、产品后一个缓冲区的下标.s2表示B进程可消费的产品数. process B begin L2: P（s2); x:=B1t1 t1:=(t1+1) mod n ; V(s1); 加工产品； P（s3); B2r2:=x; r2:=(r2+1) mod m ; V(s4); goto L2; end;t1指向B进程要加工的B1缓冲区的产品位置.s3表示B2筐中空闲的缓冲区个数, r2表示B2筐存放产品后一个缓冲区的下标.s4表示C进程可消费的产品数.process C begin L3: P（s4); y:=B2t2 t2:=(t2+1) mod m ; V(s3); 销售 goto L3; e
29、nd;Coend;End.t2指向C进程要加工的B2缓冲区的产品位置.2、一个海底隧道只有一个车道，规定同一个方向的可以连续过隧道；某方向有列车过隧道时，另一个方向的列车就要等待，现在东岸和西岸都有列车要过隧道，如果把每个过隧道的列车看作一个进程，为保证安全，请用PV操作实现正确管理。分析：隧道是一共享资源，用一个信号量；计数器计数需两个；计数器是共享资源（临界区）Begin s,s1,s2:semaphore;rc1,rc2:integer;s:=1;s1:=1,s2:=1;rc1:=0;rc2:=0;Cobegin process (e-w)i (i=1,2,) begin p(s1); rc1:=rc1+1; if rc1=1 then p(s); v(s1); 过隧道； p(s1); rc1:=rc1-1; if rc1=0 then v(s); v(s1); End; s1为对rc1互斥访问的信号量,s为对隧道互斥访问的信号量.process (w-e)i (i=1,2,) begin p(s2); rc2:=rc2+1; if rc2=1 then p(s); v(s2); 过隧道； p(s2); rc2:=rc2-1; if rc2=0 then v(s); v(s2); End;Coend;End.s2为对rc2互斥访问的信号量,s为对隧道互斥访问的信号量.
