广东工业大学大13年操作系统复习大题

1、 .DOC资料. 四、综合应用题(每题10分，共40分).（p 、v操作）1、请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。答：将独木桥的两个方向分别标记为A和B；并用整形变量countA和countB分别表示A、B方向上已在独木桥上的行人数，初值为0；再设置三个初值都1的互斥信号量：SA用来实现对countA的互斥访问，SB用来实现对countB的互斥访问，mutex用来实现两个方向的行人对独木桥的互斥使用。则具体描述如下：Var SA,SB,mutex:semaphore:=1,1

2、,1; CountA,countB:integer:=0,0: begin parbegin process A: begin wait(SA);if(countA=0) then wait(mutex);countA:=countA+1;signal(SA);过独木桥；wait(SA); countA:=countA-1; if (countA=0) then signal(mutex);signa(SA); endprocess B: begin wait(SB);if(countB=0) then wait(mutex);countB:=countB+1;signal(SB);过独木桥；

3、wait(SB); countB:=countB-1; if (countB=0) then signal(mutex);signa(SB); endparend end2. 有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。解释P、V操作的含义，并用P、V操作来保证文件的正确打印。（1）P、V操作是两条原语，定义如下： P操作：P操作记为P(S)，其中S为一信号量，它执行时主要完成下述动作：

4、 S=S-1若S=0，则进程继续运行。若S0，则进程继续运行。若S=0，则从信号量的等待队列中移出队首进程。使其变为就绪状态。（2）描述如下：Var empty1,empty2,full1,full2:semaphore:=1,1,0,0; begin parbegin process1: begin repeat 从磁盘读一个记录； P(empty1); 将记录存入缓冲区1； V(full1); until false; end process 2: begin repeat P(full1); 从缓冲区1取出纪录； V(empty1); P(empty2); 将记录存入缓冲区2； V(fu

5、ll2); until false; endprocess 3: begin repeat P(full2); 从缓冲区2取出纪录； V(empty2); 打印记录； until false;end parend 3. 设某台机挂有两个I/O通道：分别挂一台输入机和一台打印机。卡片机上有一叠数据卡片，现在要把这些数据逐一输入到缓冲区buffe1，然后再复制到缓冲区buffe2，并在打印机上打印出来。系统可设哪些进程来完成这个任务？用P-V原语写这些进程的同步算法。 由上图可见，系统可设3个进程：输入进程、复制进程、打印进程；分别用进程R、进程C、进程P来表示。 这些进程之间的相互制约关系： R

6、受C的约束；C受R、P的约束；P受C的约束。 设4个信号量：S1=1，S2=0，S3=1，S4=0 （有几个制约设几个信号量，信号量的初值根据资源是否可以用设置） 同步算法如下：4.假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行登记，而且每次只允许一人进行登记操作，请用记录型信号量机制实现上述问题的同步。 Var sum,mutex:semaphore:=100,1; begin parbegin 进入: begin wait(sum);wait(mutex);登记；signal(mutex);进入阅览室； End离开: begin wait(mu

7、tex);登记；signal(mutex);离开阅览室；signal(sum); endparendEnd（进程调度）1、在两道环境下有四个作业，已知它们进入系统的时间、估计运行时间，系统分别采用短作业优先作业调度算法（可抢占式）和最高响应比优先调度算法（可抢占式），分别给出这四个作业的执行时间序列，并计算出平均周转时间及带权平均周转时间。1、答：系统采用短作业优先调度：作业进入时间估计运行时间（分钟）开始时间结束时间周转时间（分钟）带权周转时间JOB110：003010：0011：05652.167JOB210：052010：0510：25201JOB310：20510：2510：30204

8、JOB410：301010：3010：40202作业的周转时间：31.25 带权周转时间：2.291259.167系统采用高响应比作业优先调度：作业进入时间估计运行时间（分钟）开始时间结束时间周转时间（分钟）带权周转时间JOB110：003010：0010：30301JOB210：052010：3510：55502.5JOB310：20510：3010：35255JOB410：301010：5511：05353.5作业的周转时间：35 带权周转时间：3140122假设有 4 道作业，它们提交的时刻及执行时间由下表给出，计算在单道程序环境下，采用先来先服务调度算法、最短作业优先算法、最高响应比优

9、先算法的平均周转时间和平均带权周转时间，并指出它们的调度顺序。 作业提交时间运行时间18.02.028.50.539.00.149.50.22、答：先来先服务调度算法作业提交时间运行时间开始时间完成时间周转时间带权周转时间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.08.010.02128.50.510.310.82.34.639.00.110.010.11.1

10、1149.50.210.110.30.84T=1.55W=5.15最高响应比优先算法 响应比Rp作业响应时间运行时间作业等待时间作业运行时间 作业等待时间作业运行时间作业提交时间运行时间开始时间完成时间Rp周转时间带权周转时间18.02.08.010.012128.50.510.110.63.22.14.239.00.110.010.1101.11149.50.210.610.85.51.36.5T=1.625W=5.6753、假设进程到达时间和要求服务时间如下表：。进程名ABCDEF到达时间012345服务时间435624(1)计算采用FCFS和SJF调度算法各进程的周转时间和带权周转时间。

11、(2)基于时间片的轮转调度算法中，时间片分别为1和4时，计算各进程的周转时间和带权周转时间。答：进程名ABCDEF平均到达时间012345服务时间435624FCFS完成时间4712182024周转时间461015161911.67带权周转时间1222.584.752.85SJF完成时间491824613周转时间481621289.8带权周转时间12.673.23.5122.23 ( )4. 一个具有两道作业并发能力的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，如下表的作业序列（表中所有作业优先数即为进程优先数，数值越小优先级越高）。作业名到达时间

12、估计运算时间优先数A10：0040分5B10：2030分3C10：3050分4D10：5020分61)列出所有作业进入内存时间2)在CPU时间轴上依次列出各进程被调度执行的次序和起始时间3)计算平均周转时间和平均带权周转时间（1）进入内存时间如下：A10:00，B10:20，C11:10，D10:50（2）（3）作业到达时间完成时间周转时间（分钟）带权周转时间A 10:00 11:10 70 1.75 B 10:20 10:50 30 1C 10:30 12:00 90 1.8D 10:50 12:20 90 4.5平均周转时间70分钟平均带权周转时间2.26 （地址转换）1.已知某分页系统，

13、主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。（1）将十进制的逻辑地址1023、2500、3500、4500转换成物理地址。（2）以十进制的逻辑地址1023为例画出地址变换过程图。答：(1)逻辑地址1023：1023/1024，得页号0，页内地址1023，查页表的相应块号2，故物理地址为2*1024+1023=3071逻辑地址2500： 2500/1024，得页号2，页内地址452，查页表的相应块号6，故物理地址为6*1024+452=6596逻辑地址3500： 3500/1024，得页号3，页内地址428，查页表的相应块号7，故

14、物理地址为7*1024+428=7596逻辑地址4500： 4500/1024，得页号4，页内地址404，因页号大于页表长度产生越界中断。(2)略。( )2.假如一个程序的段表如下，其中存在位为1表示段在内存，对于下面指令，在执行时会产生什么样的结果。(1)STORE 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，表示该段未装入内存，因此产生缺段中断。（2分）(2)从段表第1项可看到，指令中逻辑地址合法，段也已经在内存，但存取控制字段不符，故产生保护性中断信号。（2分）(

15、3)逻辑地址合法，存取方式合法，形成物理地址8050后，执行指定操作。（2分）(4)逻辑地址中段内地址超长，产生越界中断信号。（2分）(5)逻辑地址及访问方式合法，形成物理地址3150，指令执行后，将条转到内存单元3150处继续执行。（2分）3某虚拟存储器的用户空间共有32个页面，每页1K，主存16K。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7。而该用户作业的长度为6页，试将十六进制的虚拟地址0A5C、103C、1A5C转换成物理地址。答：该系统逻辑地址有15位，其中高5位为页号，低10位为页内地址；物理地址有14位，其中高4位为块号，低10位为块内地址。故：(0

16、A5C)16的页号为2，页号合法，页表中对应块号为4，即物理地址为(125C)16。(103C)16的页号为4，页号合法，但该页未装入内存，故产生缺页中断。(1A5C)16的页号为6，为非法页号，故产生越界中断。4. 假设一个可移动磁头的磁盘具有200个磁道,其编号为0199,当它刚结束了125道的存取,正在处理143道的服务请求,假设系统当前I/O请求队列如下: 86,147,91,177,94,150,102,175,130 试对以下的磁盘I/O调度算法而言,满足以上请求队列,磁头寻道顺序如何? 寻道总长度是多少 ？(1) 先来先服务算法(FCFS) (2) 最短寻道时间优先调度(SSTF

17、) (3) 扫描算法(SCAN) (4) 循环扫描算法 (CSCAN) 答：当前位于143道，则FCFSSSTFSCANCSAN被访问的下一磁道号移动的磁道数被访问的下一磁道号移动的磁道数被访问的下一磁道号移动的磁道数被访问的下一磁道号移动的磁道数8657147414741474147901503150315039111302017525175251771761022817721772948294813047869115068913102289151023486594894317514117589913102813011177286513028寻道总长度：660寻道总长度：162寻道总长度：1

18、25寻道总长度：169（页面替换）1. 现有一请求分页的虚拟存储器 , 内存最多容纳 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 页面替换算法 , 各将产生多少次缺页中断 ? 1.答：FIFO:12345341678789789545421111555555888888888882222222111111999999999333333666666666555554444447777777774444LRU123453416787897895454211112225341116

19、66678889222345341666789789995334534167878978954544534167878978954542OPT12345341678789789545421111111166888888888882222555555555555555555333333377777777744444444444444999999999FIFO共13次缺页中断，LRU也要13次缺页中断，OPT要11次缺页中断。2在一个请求分页系统中，假如一个作业的页面走向-为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1当分配给该作业的物理块数为3时，分别采用LRU

20、、OPT 页面置换算法时，试计算访问过程中所发生的中断次数。2答：OPT（最佳置换算法）所选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面。利用最佳页面置换算法时的置换图如下图所示：缺页中断次数为9 LRU（最近最久未使用）选择最后一次访问时间距离当前时间最长的一页并淘汰之。即淘汰没有使用的时间最长的页。LRU页面置换算法时的置换图如下图所示：缺页中断次数为122在一个请求分页系统中，假如一个作业的页面走向-为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1当分配给该作业的物理块数为3时，分别采用LRU、OPT、FIFO页面置换算法时，试计算访问过程中所发生的缺页中断次数和缺页率。、OPT（最佳置换算法）所选择的被淘汰页面，将是以后永不使用的， 或许是在最长(未来)时间内不再被访问的页面。利用最佳页