操作系统 第2章

1、 进程管理进程管理 I1C1P1I2C2P2 进程管理进程管理 P1 P2 P3 P4 进程管理进程管理 I1I2I3I4 C1C2C3C4 P1P2P3P4 t 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 就绪就绪 阻塞阻塞执行执行 时间片完时间片完 进程调度进程调度 I/O请求请求 I/O完成完成 图图25 进程的三种基本状态及其转换进程的三种基本状态及其转换 进程管理进程管理 进程管理进程管理 执行执行 活动活动 就绪就绪 静止静止 就绪就绪 活动活动 阻塞阻塞 静止静止 阻塞阻塞 激活激活 挂起挂起 激活激活 挂起挂起 释放释放 释放释放

2、挂起挂起 请求请求I/O 进程管理进程管理 v写一个程序描述进程状态迁移过程。写一个程序描述进程状态迁移过程。 v要求：要求： 提供导致进程状态变化的调用接口，包括创建、提供导致进程状态变化的调用接口，包括创建、 删除、调度、阻塞、时间到、挂起、激活等。删除、调度、阻塞、时间到、挂起、激活等。 实现进程列表显示的接口。实现进程列表显示的接口。 注：这里设计的进程是一个假设的对象实体，是注：这里设计的进程是一个假设的对象实体，是 由程序自己创建和删除，不是系统维护的进程。由程序自己创建和删除，不是系统维护的进程。 进程管理进程管理 pid 现场现场 进程状态进程状态 优先级优先级 阻塞原因阻塞原

3、因 程序地址程序地址 同步机制同步机制 资源清单资源清单 链接指针链接指针 进程管理进程管理 执行指针执行指针 就绪队列指针就绪队列指针 阻塞队列指针阻塞队列指针 空闲队列指针空闲队列指针 PCB14 PCB23 PCB30 PCB48 PCB5 PCB67 PCB79 PCB80 PCB91 进程管理进程管理 structstruct wait_queuewait_queue structstruct task_structtask_struct * * task; task; structstruct wait_queuewait_queue * * next; next; ; PCBPC

4、B PCB 进程管理进程管理 PCB1 PCB2 PCB3 PCB4 PCB5 PCB6 PCB7 执行指针执行指针 就绪表指针就绪表指针 阻塞表指针阻塞表指针 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 producer: repeat produce an item in nextp; while counter=n do no-op; bufferin:=nextp; in:=(in+1)mod n; counter:

5、=counter+1; until false; consumer: repeat while counter=0 do no-op; nextc:=bufferout; out:=(out+1) mod n; counter:=counter-1; consumer the item in nextc; until false; 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 Swait(s1,s2,sn) if s11 and and sn 1 then for i:=1 to

6、 n do si:=si-1; endfor else place the process in the waiting queue with the first si found with si1, and set the program count of this process to the beginning of swait operation end if Ssignal(s1,s2,sn) for i:=1 to n do si:=si+1; remove all the process waiting in the queue associated with si into t

7、he ready queue endfor 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 S1 S2 S3 S4 S5 S6 a b c d e g f 进程管理进程管理 进程管理进程管理 练习：已知一个求知公式 （A2+3B）/（B+5A），若A， B已赋值，试画出求值过程的前趋图，并用信号量描述前 驱关系。 进程管理进程管理 v练习：两位同学约好练习：两位同学约好 星期天去东湖，早上星期天去东湖，早上 8:00在校门口，不见在校门口，不见 不散。不散。当一个同学先当一个同学先 来到校门口，要等另一来到校门口，要等另一 个同学，到齐后一道打个同学，到齐后一道打 的去

8、东湖。请用用信号的去东湖。请用用信号 量知识实现同步。量知识实现同步。 南昌 航空 大学 进程管理进程管理 va,ba,b 两点间是一段东西向的单行车道，现要设计一两点间是一段东西向的单行车道，现要设计一 个自动管理系统，管理规则如下：当个自动管理系统，管理规则如下：当abab间有车辆在间有车辆在 行驶时同方向的车可以同时驶入行驶时同方向的车可以同时驶入abab段，但另一方向段，但另一方向 的车必须在的车必须在abab段外等待；当段外等待；当abab之间无车时，到达之间无车时，到达a a （或（或b b）的车辆可以进入）的车辆可以进入abab段，但不能从段，但不能从a a，b b点同点同 时驶

9、入；当某方向在时驶入；当某方向在abab段行驶的车辆使出了段行驶的车辆使出了abab段且段且 无车辆进入无车辆进入abab段时，应让另一方向等待的车辆进入段时，应让另一方向等待的车辆进入 abab段行驶。请用段行驶。请用wait,signalwait,signal工具对工具对abab段实现正确段实现正确 管理。管理。 进程管理进程管理 Semaphore s, mutexab,mutexba Pab： Wait(mutexab) Countab+ If countab=1 then wait(s); Signal(mutexab) . wait(mutexab) countab- -; if

10、countab=0 then signal(s) signal(mutexab); 进程管理进程管理 Pba: wait(mutexba) countba=countba+1; If countba=1 then wait(s) signal(mutexba) enter; wait(mutexba) countba-; if countba=0 then signal(s) signal(mutexba); 进程管理进程管理 v苹果桔子问题：桌上有一只盘子，最 多可以容纳两个水果，每次只能放入/ 取出一只水果；爸爸专向盘子中放苹 果(apple)，妈妈专向盘子中放桔子 (orange)，两个

11、儿子专等吃盘子中的桔 子，两个女儿专等吃盘子里的苹果。 请用P，V操作来实现爸爸、妈妈儿子 、女儿之间的同步和互斥。（南京大 学2000年） 进程管理进程管理 main()main() tpyedeftpyedef intint semaphore; ; semaphore emptyempty； / /* * 盘子里可以放几个水果盘子里可以放几个水果 * */ / semaphore orange; /orange; /* * 盘子里有桔子盘子里有桔子 * */ / semaphore apple; /apple; /* * 盘子里有苹果盘子里有苹果 * */ / semaphore mut

12、ex; / /* *不能同时对盘子操作的互不能同时对盘子操作的互 斥量斥量 empty = 2; /= 2; /* * 盘子里允许放一个水果盘子里允许放一个水果* */ / orange =0; /=0; /* * 盘子里没有桔子盘子里没有桔子 * */ / apple = 0; /= 0; /* * 盘子里没有苹果盘子里没有苹果* */ / mutexmutex=1=1 cobegin/*可并发的进程可并发的进程*/ father(); mother(); son(); daugher(); coend 进程管理进程管理 father()father() while( while(手中还有苹

13、果手中还有苹果) ) P(empty); P(mutex)； 向盘中放苹果向盘中放苹果； V(mutex)； V(apple); mother()mother() while( while(手中手中还有桔子还有桔子) ) P(empty); P(mutex)； 向盘中放桔子向盘中放桔子； V(mutex)； V(orange); 进程管理进程管理 soni()/isoni()/i=1=1，2 2 while(while(盘中还有苹果盘中还有苹果) ) P(apple); P(mutex)； 从盘中拿苹果从盘中拿苹果； V(mutex)； V(empty); daugheridaugheri()

14、 () /i=1，2 while( while(盘中还有桔子盘中还有桔子) ) P(orange); P(mutex)； 从盘中拿桔子从盘中拿桔子； V(mutex)； V(empty); 进程管理进程管理 进程管理进程管理 producer: begin repeat Produce an item in nextp; 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 练习练习 v 有4个进程共享同一程序段，且每次最多允许3个

15、进程进入该程序段，则信号量的变化范围是（ ）。 A3，2，1，0B3，2，1，0，-1 C4，3，2，1，0 D2，1，0，-1，-2 进程管理进程管理 v理发店里有一位理发师、一把理发椅子和五把供等 候理发的顾客坐的椅子。如果没有顾客，理发师便 在理发椅上睡觉。当一个顾客到来时，他必须先叫 醒理发师，如果理发师正在理发时又有顾客来到， 而如果有空椅子可坐，他们就坐下来等，如果没有 空椅子，他就离开。请为理发师和顾客各编写一段 程序来描述他们行为，并用wait和signal原语或p、v 操作实现其同步。 进程管理进程管理 #define CHAIRS 5 /*为等候的顾客准备椅子数为等候的顾客

16、准备椅子数*/ typedef int semaphore; /* 信号量类型信号量类型*/ semphore customers=0; /*等候服务的顾客数等候服务的顾客数*/ semaphore barbers=1 /*等候服务的理发师数等候服务的理发师数*/ semaphore mutex=1; /*用于互斥用于互斥*/ int waiting=0; /*还没理发的等候顾客还没理发的等候顾客*/ void barber (void) while(TRUE) wait(customers); /*如果顾客数是如果顾客数是0，则睡觉，则睡觉*/ wait(mutex); /*要求进程等候要求

17、进程等候*/ waiting=waiting-1; /*等候顾客数减等候顾客数减1*/ signal(mutex); /*释放等候释放等候*/ cut_hair(); /*理发（非临界区操作）理发（非临界区操作）*/ signal(barbers); /*一个理发师现在开始理发一个理发师现在开始理发*/ 进程管理进程管理 void customers (void) wait(mutex); if (waitingCHAIRS) waiting=waiting+1; signal(customers); signal(mutex); wait(barbers); else signal(mutex); 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 进程管理进程管理 mq mutex sm sender:A size:5 text:Hello send(B,a) sender :A size :5 text:hello next:0 发送区发送区Asender:A size:5 text:Hello receive(b) 接收区接收区B a b 进程进程A PCB(B