74第二章习题

假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行登记，而且每次只允许一人进行登记操作，请用记录型信号量机制实现上述问题的同步。定义信号量sum,mutex，初值分别为100，1。（3分）则第i个读者的活动描述为：procedurePi(i=1,2,3……)beginwait(sum);wait(mutex);登记；signal(mutex);进入阅览室；阅读;wait(mutex);登记；signal(mutex);离开阅览室；signal(sum);end请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。将独木桥的两个方向分别标记为A和B；并用整形变量countA和countB分别表示A、B方向上已在独木桥上的行人数，初值为0；再设置三个初值都1的互斥信号量：SA用来实现对countA的互斥访问，SB用来实现对countB的互斥访问，mutex用来实现两个方向的行人对独木桥的互斥使用。则具体描述如下：VarSA,SB,mutex:semaphore:=1,1,1;CountA,countB:integer:=0,0:beginparbeginprocessA:beginwait(SA);if(countA=0)thenwait(mutex);countA:=countA+1;signal(SA);过独木桥；wait(SA);countA:=countA-1;if(countA=0)thensignal(mutex);signa(SA);endprocessB:beginwait(SB);if(countB=0)thenwait(mutex);countB:=countB+1;signal(SB);过独木桥；wait(SB);countB:=countB-1;if(countB=0)thensignal(mutex);signa(SB);endparendend设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆；正常行车；到站停车；售票员的活动：关车门；售票；开车门；请用记录型信号量机制实现上述问题的同步。Vars1,s2:semaphore:=0,0;/*s1表示是否允许司机启动汽车，s2表示是否允许售票员开门*/beginparbegindriver:beginrepeatwait(s1);启动车辆；正常行车；到站停车；signal(s2);untilfalse;endbusman:beginrepeat关车门；signal(s1);售票；wait(s2);开车门；上下乘客；untilfalse;endparendend有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。解释P、V操作的含义，并用P、V操作来保证文件的正确打印。（1）P、V操作是两条原语，定义如下：P操作：P操作记为P(S)，其中S为一信号量，它执行时主要完成下述动作：S=S-1若S=0，则进程继续运行。若S0，则该进程被阻塞，并将它插入该信号量的等待队列中。V操作：V操作记为V(S)，其中S为一信号量，它执行时主要完成下述动作：S=S+1若S0，则进程继续运行。若S=0，则从信号量的等待队列中移出队首进程。使其变为就绪状态。（2）描述如下：Varempty1,empty2,full1,full2:semaphore:=1,1,0,0;beginparbeginprocess1:beginrepeat从磁盘读一个记录；P(empty1);将记录存入缓冲区1V(full1);untilfalse;endprocess2:beginrepeatP(full1);从缓冲区1取出纪录；V(empty1);P(empty2);将记录存入缓冲区2V(full2);untilfalse;endprocess3:beginrepeatP(full2);从缓冲区2V(empty2);untilfalse;endparend假如一个程序的段表如下，其中存在位为1表示段在内存，对于下面指令，在执行时会产生什么样的结果。R40500004R80800013E200300012R30100011W10050000存取控制段长内存始址存在位段号R40500004R80800013E200300012R30100011W10050000存取控制段长内存始址存在位段号(1)STORER1,[0,70](2)STORER1,[1,20](3)LOADR1,[3,50](4)LOADR1,[3,100](5)JMP[2,150](1)由于第0段的存在位为0，表示该段未装入内存，因此产生缺段中断。(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:12345341678789789545421111555555888888888882222222111111999999999333333666666666555554444447777777774444√√√√√√√√√√√√√LRU12345341678789789545421111222534111666678889222345341666789789995334534167878978954544534167878978954542√√√√√√√√√√√√√OPT12345341678789789545421111111166888888888882222555555555555555555333333377777777744444444444444999999999√√√√√√√√√√√FIFO共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个磁道,其编号为0~199,当前位于第143道，假设系统当前I/O请求队列如下:86,147,91,177,94,150,102,175,130试对以下的磁盘I/O调度算法而言,满足以上请求队列,磁头寻道顺序如何?寻道总长度是多少？(1)先来先服务算法(FCFS)(2)最短寻道时间优先调度(SSTF)(3)扫描算法(SCAN)(4)循环扫描算法(CSCAN)有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。解释P、V操作的含义，并用P、V操作来保证文件的正确打印。2．在一个请求分页系统中，假如一个作业的页面走向---为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1当分配给该作业的物理块数为3时，分别采用LRU、OPT页面置换算法时，试计算访问过程中所发生的中断次数。3．设作业Ａ的页面映象表如下图所示：（一页=一块=1024字节）页号块号中断位访问位修改位辅存地址０８１１１１０００１５１００３０００２７１１０５０００３０００８０００问：①指出页表中中断位、访问位、修改位、辅存地址的含义？②当执行到１０００单元的指令“ＬＯＡＤ１，１８００”时，系统是怎样进行地址变换（即１８００在主存的哪个单元中）③当执行到１５００单元指令（ＬＯＡＤ１，３６００）时，会发生什么现象？4．在两道环境下有四个作业，已知它们进入系统的时间、估计运行时间，系统分别采用短作业优先作业调度算法（可抢占式）和最高响应比优先调度算法（可抢占式），分别给出这四个作业的执行时间序列，并计算出平均周转时间及带权平均周转时间。假设有4道作业，它们提交的时刻及执行时间由下表给出，计算在单道程序环境下，采用先来先服务调度算法、最短作业优先算法、最高响应比优先算法的平均周转时间和平均带权周转时间，并指出它们的调度顺序。先来先服务调度算法作业提交时间运行时间开始时间完成时间周转时间带权周转时间18.02.08.010.02.01.028.50.510.010.52.04.039.00.110.510.61.616.049.50.210.610.81.36.5T=1.725W=6.875作业提交时间运行时间18.02.028.50.539.00.149.50.2最短作业优先算法作业提交时间运行时间开始时间完成时间周转时间带权周转时间18.02.08.010.02128.50.510.310.82.34.639.00.110.010.11.11149.50.210.110.30.84T=1.55W=5.15最高响应比优先算法响应比Rp＝作业响应时间／运行时间＝作业等待时间＋作业运行时间＝１＋作业等待时间／作业运行时间T=1.625W=5.675有3个进程P1、P2和P3并发执行。进程P1需使用资源r3和r1，进程P2需使用资源r1和r2，进程P3需使用资源r2和r3。⑴若对资源分配不加限制，会发生什么情况，为什么？⑵为保证进程能执行到结束，应采用怎样的资源分配策略？（1）会发生死锁。因为，如果进程P1获得资源r1，等待r3，进程P2获得资源r2，等待r1，进程P3获得资源r3，等待r2，这样三个进程将相互等待，发生死锁。（2）应该采用“静态分配法”，一次性地要么把进程所需资源全部分配给进程，要么就一个资源也不分配，或者采用“有序分配法”，摒弃产生死锁的“环路等待”条件，或每次分配资源的时候用“银行家算法”看这次分配会不会使系统进入不安全状态，如果不会再分配。作业提交时间运行时间开始时间完成时间Rp周转时间带权周转时间18.02.08.010.012128.50.510.110.63.22.14.239.00.110.010.1101.11149.50.210.610.85.51.36.5