第四章作业参考复习资料.docx

2 答：多道程序在单CPU上并发运行与多道程序在多CPU上并行在本质上是不同的,在单CPU上，操作系统利用时间片轮转算法在一段时间内依次调度执行多个程序，宏观上多道程序并发运行、微观上仍是串行执行；在多CPU上，同一时刻可有多个程序分别在多个CPU上并行执行，而某个程序也可能同时在多个CPU上并行执行。前者实现时应考虑的因素： 在多道程序环境下如何向用户提供服务； 在并发程序之间如可正确传递消息（通信）； 如何对CPU进行调度，保证每个用户相对公平地得到CPU；（CPU是一个只可调度，不可分配的资源）后者实现时应考虑的因素： 在执行多道程序时应如何分配程序给CPU 多CPU之间的通信问题 在多CPU上并行执行一个程序时如何调度与分配CPU9说明下列活动时属于哪种至于关系？（1）若干同学去图书馆借书；（2）两队进行篮球比赛；（3）流水线生产中的各道工序；（4）商品生产与社会消费；答：（1）互斥关系（2）互斥关系（3）同步关系（4）同步关系11设有一台计算机，有两条I/O通道，分别接一台卡片输入机与一台打印机。卡片机把一叠卡片逐一输入到缓冲区B1中，加工处理后再搬到缓冲区B2中，并在打印机上印出。问：（1）系统要设几个进程来完成这个任务？各自的工作是什么？（2）这些进程间有什么样的相互制约关系？（3）用PV操作写出这些进程的同步算法。（4）设系统中只有上述几个过程，用图表示出各自状态变迁情况及原因。答：（1）系统要设3个进程来完成这个任务； 第一个进程：从卡片机把一叠卡片逐一输入到缓冲区B1中； 第二个进程：加工处理后再搬到缓冲区B2中； 第三个进程：从缓冲区B2读出，打印机印出。（2）第一个进程从卡片机把一叠卡片逐一输入到缓冲区B1中，第二个进程加工处理B1中的数据。如果B1为空，则第二个进程无法进行；如果B1满了，第一个进程不能再进行。 第二个进程加工处理B1中的数据并搬到B2中，第三个进程从B2读出。如果B2为空，则第三个进程无法进行；如果B2满了，第二个进程无法进行。（3）P:不能往满的B1送数据，设信号量S1，初值为k（k为缓冲区B1的大小）while(true)读一张卡片;P(S1);数据送到缓冲区B1;V(S2);Q:不能从空的B1读数据，设信号量S2，初值为0；不能往满的B2送数据，设信号量S3，初值为l（l为缓冲区B2的大小）while(true)P(S2);从缓冲区B1读数据;加工数据;V(S1);P(S3)加工的数据写入缓冲区B2;V(S4);R:不能从空的B2读数据，设信号量S4，初值为0；while(true)P(S4);从缓冲区B2读数据;V(S3)打印;（4）卡片打印机B1B2B1未满B2未满B1非空B2非空进程一：运行就绪等待jklmjB1满kB1未满l卡片全部读完m新的一批卡片作业进程二：运行就绪等待jklmjB2满kB2未满lB1空mB1非空进程三：运行就绪等待jklj无条件k B2空l B2非空13假定一个阅览室最多可容纳100人，读者进入与离开阅览室时都必须在阅览室门口的一个登记表上标志（进入时登记，离开时去掉登记项），而且每次只允许一人登记或去掉登记，问：（1） 应编写几个程序完成此项工作，程序的主要动作是些什么？应设置几个进程？进程及程序间的对应关系如何？（2） 用P、V操作写出这些进程的同步通信关系。答：（1） 应该编写四个程序完成工作，分别执行：管理等待登入队列，登入并分配资源，管理等待离开队列，登出并回收资源。应设置2个进程，分别负责管理登入与负责管理登出。（2） 设置readercount=100，控制可进入的读者数设置mutex=1，控制操作登记表登入进程：P(mutex)P(readercount）分配阅览室资源V(mutex)登出进程：P(mutex)回收阅览室资源V(readercount)V(mutex)17假设一个系统的磁盘大小为2kB，一个块的平均访问时间是20毫秒，一个有40kB的进程由于资源请求此从运行状态变为阻塞态。要确保将该进程换出，它必须保持阻塞多长时间？解：阻塞时间：T = 40/2 * 20 =400 (毫秒)18.假使A、B两个火车站之间是单轨线，许多列车可以同时到达A站，然后经A站到B站，又列车从A到B的行驶时间是t，列车到B站后的停留时间是t/2。试问在该问题模型中，什么是临界资源？什么是临界区？答：因为许多列车可以同时到达A站，所以A站不是互斥资源，而A、B之间的单轨线每次只能允许一辆列车发出以后另一辆才能发出。因为列车行驶时间为t，B的停留时间为t/2，所以只要在前一辆列车走完前1/2路程后再发车，到达B站时前一辆车也已离开B站。（1）A、B间单轨线的前半段是临界资源。 （2）临界区：列车在单轨线前半段上行驶21题 （测验的最后一题，类似，更简单）由于有m个发送者，n个接收者，k大小的缓冲区；从单个的问题出发，发送者要么等待在第x缓冲区（条件是缓冲区x未被清空，而发送者采用递增环状方式使用缓冲区）要么发送到x，发送完后需要唤醒所有接收进程。接收进程不停的轮询缓冲区,也采用递增环状方式，如果缓冲区有内容，则收取，并把此缓冲区的未接收数减一，如果减至0，则置缓冲区为空。综上所述，需要对每个缓冲区单位设置空，满，互斥量，未收取数（empty，full，mutex，count）其中full是一个数组，记录每个接收者的情况，防止重复接收，mutex主要用来做count的互斥访问。此外，还要设置全局的互斥变量mutex。Type BufferType = Recordmsg:MessageType;count:integer;mutex:semaphore; 初值为1empty: semaphore; 初值为1full: array 1.n of semaphore； 初值全为0EndVar mutex: semaphore; 初值为1s: integer; 初值为0buff: array 0.k-1 of BufferType; k是缓冲区大小； n是接收进程个数 m是发送进程个数，通过 s 进行“写互斥” Procedure Sender_i(i:integer); i 为发送进程的标号Vars0, j: integer;Begin Repeat P(mutex); s0:=s; s:=(s+1) mod k; V(mutex); P(buffs0.empty)； 在buffs0.msg中写信息； P(buffs0.mutex)； buffs0.count:=n; V(buffs0.mutex); For (j:=1 to n do) V(buffs0.fullj); Until false;EndProcedure Recvr(i:integer); i 为接收进程的标号Varj: integer;Begin j:=0; Repeat P(buffj.fulli); 从buffj.msg中读信息； P(buffj.mutex)； buffj.count:= buffj.count-1; If (buffj.count=0) Then V(buffj.empty)； V(buffj.mutex); j:=(j+1) mod kUntil false;End22.<1>.信号量说明：mutex，初值为，记录可进入临界区的进程数;互斥算法；P(mutex); 进入临界区；V(mutex); 结束； <2>.信号量说明：mutex，初值为m，记录可进入临界区的进程数; 互斥算法；P(mutex); 进入临界区；V(mutex);结束；25.一家快餐店招有4种雇员：（1）开票者，取顾客的订单；（2）厨师，准备饭菜；（3）包装员，把食物撞进袋中；（4）出纳，一手收钱一手交货。每位雇员可以看作一个在通信的顺序进程。他们采用的是什么方式的进程间通信？ 答：开票者与厨师之间是管道通信。开票者源源不断的把订单给厨师，一次可能给一张也可能给多张，厨师一次可能拿走一张订单去做也可能拿走多张去做。厨师与包装员之间是信箱通信，他们之间有个信箱，可能就是一个小平台，厨师做好就把菜放上去，相当于放进信箱 ，而包装员可以在任何时候取走那个菜。包装员与出纳之间是消息缓冲通信，包装员包号了就给出纳发消息，出纳得到消息就取走包好的饭菜然后出售。 29计算系统CPU利用率。答：1）Q等于无穷时，算法退化为FIFO，这时CPU利用率为T/（S+T）2）Q>T时，进程在用完时间片之前已被堵塞，因此CPU利用率仍为T/（S+T）3）S<Q<T时，进程在I/O堵塞之前需使用INT(T/Q) + 1个时间片，因此CPU利用率为T /（INT(T/Q) + 1）* S）+ T）4）Q = S时，当S远小于T时，CPU在调度与运行进程的时间近似相等，CPU利用率为1/25）Q趋于零时，几乎所有的时间都花在调度上，因此CPU利用率也趋于零。 34巴拿马运河建在太平洋与大西洋之间。由于太平洋与大西洋水面高度不同，有巨大落差，所以运河中修建有T(T>=2)级船闸，并且只能允许单向通行。船闸依次编号为1、2、T。由大西洋来的船需经由船闸T、T-1、1通过运河到太平洋；由太平洋来的船需经由船闸1、2、T通过运河到大西洋。试用P、V操作正确解决大西洋与太平洋的船只通航问题答：来自不同方向的船只对船闸要互斥使用。但如过有同方向的船只正在通行，则不用等待。对一个船闸设以下变量：PtoAcount 整型，记录此船闸正由太平洋往大西洋航行的船只 初值0。AtoPcount 整型，记录此船闸正由大西洋往太平洋航行的船只 初值0。Mutex 信号量，对PtoAcount互斥 初值1Mutex1 信号量，对AtoPcount互斥 初值1Pass 信号量 初值1太平洋到大西洋的船：P(mutex);PtoAcount:=PtoAcount+1;if PtoAcount = 1then P(pass);V(mutex);过P(mutex)PtoAcount:=PtoAcount-1;if PtoAcount = 0;then V(pass);V(mutex);大西洋到太平洋的船:P(mutex1);AtoPcount:=AtoPcount+1;if AtoPcount = 1;then P(pass);V(mutex1);过P(mutex1)AtoPcount:=AtoPcount-1;if AtoPcount = 0;then V(pass);V(mutex1);32题：有5个带运行的作业，它们的估计运行时间分别是9，6，3，5与x。采用那种次序的运行各种作业将得到最短的平均响应时间。解：采用最短作业优先法运行作业将得到最短平均相应时间。具体执行顺序是（依赖x） ：1） x<=3时 ，x à 3 à 5 à 6 à 92） 3<x<=5时，3 à x à 5 à 6 à 93） 5<x<=6时，3 à 5 à x à 6 à 94） 6<x<=9时，3 à 5 à 6 à x à 95） 9<x 时，3 à 5 à 6 à 9 à x 35答：设有n个柜台需要考虑等待人数如果没有顾客 则柜台需要等待 设置 empty = 0如果顾客太多 则顾客需要等待 设置 Customer = 0int CUSTOMER_NUM = 1;int COUNTER_NUM = 1;Customer/取号码P(MUTEX_CUSTOMER_NUM);int X = CUSTOMER_NUM;CUSTOMER_NUM+;V(MUTEX_CUSTOMER_NUM);/等待叫号V(COUNTER);P(CUSTOMER);ACTION_CUSTOMER(X);Counterint X;REPEAT/叫号P(COUNTER);V(CUSTOMER);P(MUTEX_COUNTER_NUM);int X = COUNTER_NUM;V(MUTEX_COUNTER_NUM);ACTION_COUNTER(X);UNTIL false;P(s): s:=s-1; If s<0 Then 将本进程插入相应队列末尾等待；V(s)： s:=s+1; If s<=0 Then 从等待队列队尾取一个进程唤醒，插入就绪队列 问题：（实现4个进程使用某一个需互斥使用的资源）1）这样定义P、V操作是否有问题？不合理：先进后出；可能“无限等待”2）先考虑用这样的P、V操作实现N个进程竞争使用某一共享变量的互斥机制。思路：令等待队列中始终只有一个进程。将 “栈” 变成 “队列”Var S:array 1.n-1 of semaphore; n为进程数目；Si初值为i；Sn-1到S1的作用好象是 n-1 层筛子 Procedure Pi;Var i:integer;BeginRepeat Pre_Do_it();For i:=n-1 Downto 1 Do P(Si);Do_It_In_Critical_Section;For i:=1 To n-1 Do V(Si); Post_Do_it();Until false;End3）对于2）的解法，有无效率更高的方法。如有，试问降低了多少复杂性？上述解法每次都需要做2(n-1)次P/V操作，性能低下。采用二叉树的思想，改进如下：设有4个进程P1.P4，Var S1, S2, S3: semaphore; 初值为1Procedure P1; P2 is the sameBegin Repeat P(S1);P(S3);Do_It();V(S3);V(S1);Until false;End;Procedure P3; P4 is the sameBegin Repeat P(S2);P(S3);Do_It();V(S3);V(S2);Until false;End;假设共有2N个进程争用临界区；时间复杂性： 2N -1 vsN；空间复杂性： 2N-1 vs 2N-138 用进程通讯的办法解决生产者消费者问题问题（设有N个缓冲区）生产者：Void producer (void) int item; Message m; While (TRUE) produce_item (&item); Receive (consumer, &m); Build_message (&m, item); Send (consumer, &m); 消费者：Void consumer (void); int item, I; Message m; For (i=0;i<N; i+) send (producer, &m); /发N条空消息 While (TRUE) Receive ( producer ,&m)； Extract_item( &m, &item); Send (producer ,&m); Consumer_item(item); 39.用管程实现哲学家就餐问题解法思想如下： 一个想用餐的哲学家首先拿他（她）的左边叉子，拿到后若他（她）的右边的叉子时空闲的则拿起它开始用餐，否则，他（她）放下左边的叉子并重复这个过程。 该解法是非构造性的，即假设管程已经实现。FUNCTION test_and_pick_up(i:0.4):boolean;BEGIN IF fork i=used THEN test_and_pick_up=false ELSE BEGIN fork i:=used; test_and_pick_up:=true ENDEND;PROCEDURE put_down(i:0.4); 放下 BEGIN fork i=free; signal (queue i); END; PROCEDURE initialize; 初始化 VAR i:0.4 BEGIN FOR i:=0 TO 4 DO BEGIN fork i:=free; END END; BEGIN initialize END; 每个哲学家内部定义一个局部变量： VAR with_two_gorks: Boolean;i号哲学家（i=0,.4,)的活动是这样的： REPEAT THINKING； with_two_fork:=false; REPEAT dining_philosophers.pick_up (i); IF dining_philosophers.test_and_pick_up(i+1) MOD 5) THEN with_two_fork:=true ELSE dining_philosophers.put_down(i); UNTIL with_two_forks; EATING; dining_philosophers.put_down(i); dining_philosophers.put_down(i=1) MOD 5); UNTIL false;补充题:写者优先问题：reader   Repeat                                               P(s);                                                             P(mutex);   RC:=RC+1;   if RC=1  then P(w);   V(mutex);   V(s);   reading;   P(mutex);   RC:=RC-1;   if RC=0 then V(w);   V(mutex); Until false;                                 writer :Repeat   P(k);   WC:=WC+1;   if WC=1 then P(s);   V(k);   P(w);   writing;   V(w);   P(k);   WC:=WC-1;   if WC=0 then V(s);   V(k); Until false;