第二章习题65764

1、假定一个阅览室最多可容纳100 人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行登记，而且每次只允许一人进行登记操作，请用记录型信号量机制实现上述问题的同步。定义信号量sum,mutex,初值分别为100, 1。(3分)则第i个读者的活动描述为：procedure P i(i=1,2,3 )beginwait(sum);wait(mutex);登记；signal(mutex);进入阅览室；阅读 ;wait(mutex);登记；signal(mutex);离开阅览室； signal(sum); end请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向有人过桥

2、时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。将独木桥的两个方向分别标记为A和B;并用整形变量countA和countB分别表示 A B方向上已在独木桥上的行人数，初值为0;再设置三个初值都1的互斥信号量：SA用来实现对countA的互斥访问，SB用来实现对countB的互斥访问，mutex用来实现两个方向的行人 对独木桥的互斥使用。则具体描述如下：Var SA,SB,mutex:semaphore:=1,1,1;CountA,countB:integer:=0,0: begin parbeginprocess A: beginwait(SA);if(countA=

3、0) then wait(mutex);countA:=countA+1;signal(SA);过独木桥；wait(SA);countA:=countA-1;if (countA=0) then signal(mutex);signa(SA);endprocess B: beginwait(SB);if(countB=0) then wait(mutex); countB:=countB+1;signal(SB);过独木桥；wait(SB);countB:=countB-1;if (countB=0) then signal(mutex); signa(SB);endparendend设公共汽

4、车上，司机和售票员的活动分别是：司机的活动：启动车辆；正常行车；到站停车；售票员的活动：关车门；售票；开车门；请用记录型信号量机制实现上述问题的同步。s2 表示是否允许售票员开Var s1,s2:semaphore:=0,0; /*s1 表示是否允许司机启动汽车， 门 */beginparbegindriver: beginrepeat wait(s1); 启动车辆； 正常行车； 到站停车； signal(s2);until false;endbusman: beginrepeat关车门；signal(s1);曲蕈.口 ,wait(s2);精品开车门；上下乘客;until false;endp

5、arend end有三个进程PA PB和PC合作解决文件才T印问题：PA将文件记录从磁盘读入主存的缓冲区1,每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区 2,每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大 小等于一个记录大小。解释 P、V操作的含义，并用 P、V操作来保证文件的正确打印。(1) P、V操作是两条原语，定义如下：P操作：P操作记为P(S),其中S为一信号量，它执行时主要完成下述动作：S=S-1若S>=0,则进程继续运行。若S<0,则该进程被阻塞，并将它插入该信号量的等待队列中。V操作：V操作记为V(S),其中S为一信

6、号量，它执行时主要完成下述动作：S=S+1若S>0,则进程继续运行。若S<=0,则从信号量的等待队列中移出队首进程。使其变为就绪状态。(2)描述如下：Var empty1,empty2,full1,full2:semaphore:=1,1,0,0;beginparbeginprocess1: beginrepeat从磁盘读一个记录；P(empty1);将记录存入缓冲区1;V(full1);until false;endprocess 2: beginrepeatP(full1);从缓冲区1取出纪录;V(empty1);P(empty2);将记录存入缓冲区2;V(full2);unt

7、il false;endprocess 3: beginrepeatP(full2);从缓冲区2取出纪录;V(empty2);打印记录；until false;endparend假如一个程序的段表如下，其中存在位为1表示段在内存，对于下面指令，在执行时会产生什么样的结果。段号存在位内存始址段长存取控制00500100W11100030R213000200E31800080R40500040RSTORE R1,0,70(2)STORE R1,1,20(3)LOAD R1,3,50(4)LOAD R1,3,100(5)JMP 2,150(1)由于第0段的存在位为0,表示该段未装入内存，因此产生缺段

8、中断。(2)从段表第1项可看到，指令中逻辑地址合法，段也已经在内存，但存取控制字段不符， 故产生保护性中断信号。(3)逻辑地址合法，存取方式合法，形成物理地址 8050后，执行指定操作。(4)逻辑地址中段内地址超长，产生越界中断信号。(5)逻辑地址及访问方式合法，形成物理地址 3150,指令执行后，将条转到内存单元3150处继续执行。现有一请求分页的虚拟存储器，内存最多容纳4个页面，对于下面的引用串:1,2,3,4,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,5,4,2分别采用FIFO, LRU, OPT 页面替换算法，各将产生多少次缺页中断？3. FIFO:123453416

9、78789789545421111555555888888888882222222111111999999999333333666666666555554444447777777774444VVVVVVVVVVVVLRU12345341678789789545421111222534111666678889222345341666789789995334534167878978954544534167878978954542VVVVVVVVVVVVVOPT1234534167878978954542111111116688888888888222255555555555555555533333

10、3377777777744444444444444999999999VVVVVVVVVVVFIFO共13次缺页中断，LRU也要13次缺页中断，OPT要11次缺页中断。2 .已知某分页系统，主存容量为64K,页面大小为1K,对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。(1)将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。(2)以十进制的逻辑地址1023为例画出地址变换过程图。3 .假设一个可移动磁头的磁盘具有200个磁道，其编号为0199，当前位于第143道，假设系统当前I/O请求队列如下：86,147,91,177,94,150,102,

11、175,130试对以下的磁盘I/O调度算法而言，满足以上请求队列，磁头寻道顺序如何？寻道总长度 是多少？(1)先来先服务算法(FCFS)(2)最短寻道时间优先调度(SSTF)(3)扫描算法(SCAN)(4)循环扫描算法(CSCAN)有三个进程PA PB和PC合作解决文件才T印问题：PA将文件记录从磁盘读入主存的缓冲区1,每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区 2,每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大 小等于一个记录大小。解释P、V操作的含义，并用 P、V操作来保证文件的正确打印。2 .在一个请求分页系统中，假如一个作业的页面走

12、向-为7, 0, 1, 2, 0, 3, 0, 4,2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 当分配给该作业的物理块数为 3时，分别采用LRU OPT页面置换算法时，试计算访问过程中所发生的中断次数。3 .设作业A的页面映象表如下图所示：（一页=一块=1024字节）页号块号中断位访问位修改位辅存地址0811110 0 0151003 0 0 0271105 0 0 030008 0 0 0问：指出页表中 中断位、访问位、修改位、辅存地址的含义？当执行到1 0 0。单元的指令“LOAD 1, 1 8 0 0 ”时，系统是怎样进行地址变换（即1 8 0。在主存的哪个单元

13、中）当执行到1 5 0 0单元指令（LOAD 1, 3600）时，会发生什么现象？4 .在两道环境下有四个作业，已知它们进入系统的时间、估计运行时间，系统分别采用短作业优先作业调度算法（可抢占式）和最高响应比优先调度算法（可抢占式），分别给出这四个作业的执行时间序列，并计算出平均周转时间及带权平均周转时间。trik进入时间估说运行 时间 城JOB1L0： 003DJOB210； Of2QJOB3L0： 105JOB4L& 2010假设有4道作业，它们提交的时刻及执行时间由下表给出，计算在单道程序环境下, 采用先来先服务调度算法、最短作业优先算法、最高响应比优先算法的平均周转时间 和平均

14、带权周转时间，并指出它们的调度顺序。作业提交时间运行时间18.02.028.50.539.00.149.50.2先来先服务调度算法作业提交时间运行时间开始时间完成时间周转时间带权周转时间18.02.08.010.02.01.028.50.510.010.52.04.039.00.110.510.61.616.049.50.2i0.6i0.8i.36.5T=1.725 W=6.875最短作业优先算法作业提交时间运行时间开始时间完成时间周转时间带权周转时间i8.02.08.0i0.02i28.50.5i0.3i0.82.34.639.00.ii0.0i0.ii.iii49.50.2i0.ii0.3

15、0.84T=1.55 W=5.15最高响应比优先算法响应比Rp=作业响应时间/运行时间 =作业等待时间+作业运行时间=1+作业等待时间/作业运行时间作业提交时间运行时间开始时间完成时1可Rp周转时间带权周转时间i8.02.08.0i0.0i2i28.50.5i0.ii0.63.22.i4.239.00.ii0.0i0.ii0i.iii49.50.2i0.6i0.85.5i.36.5T=1.625W=5.675有3个进程P1、P2和P 3并发执行。进程 P1需使用资源r3和ri ,进程P2需使用资源ri和r2 ,进程P3需使用资源r2和r3。若对资源分配不加限制，会发生什么情况，为什么？为保证进程能执行到