操作系统应用题2(解答).doc

1. 设有一台计算机，有两条I/O通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区B1中，加工处理后在搬到缓冲区B2中，并在打印机上印出，问：系统要设几个进程来完成这个任务？各自的工作是什么？这些进程间有什么样的相互制约关系？用P、V操作写出这些进程的同步算法。 解： 系统可设三个进程来完成这个任务：R进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1中；C进程负责从缓冲区B1中取出信息，进行加工处理，之后将结果送到缓冲区B2中；P进程负责从缓冲区B2中取出信息，并在打印机上印出。R进程受C进程影响，B1放满信息后R进程要等待等C进程将其中信息全部取走，才能继续读入信息；C进程受R进程和P进程的约束：B1中信息放满后C进程才可从中取出它们，且B2被取空后C进程才可将加工结果送入其中；P进程受C进程的约束：B2中信息放满后P进程才可从中取出它们,进行打印。信号量含义及初值：B1full 缓冲区B1满，初值为0；（B1full1表示B1满）B1empty缓冲区B1空，初值为1；（B1empty1表示B1空）B2full 缓冲区B2满，初值为0；（B2full1表示B21满）B2empty缓冲区B2空，初值为1；（B2empty1表示B2空） R进程 C进程 P进程P(B2full)从B2中取出信息进行打印V(B2empty)P(B1full)P(B2empty)取B1送入B2V(B1empty)V(B2full)P(B1empty)输入信息写入B1V(B1full)2、现有一个作业，在段式存储管理的系统中已为其主存分配，建立的段表内容如下：段号主存起始地址（段基址）段长度012040176030248020337020计算逻辑地址（2，15），（0，60），（3，18）的绝对地址是多少？注：括号中第一个元素为段号，第二个元素为段内地址。解：段式存储管理的地址转换过程为：（1）根据逻辑地址中的段号查段表的相应栏目；（2）根据段内地址段长度，检查地址是否越界；（3）若不越界，则绝对地址=该段的主存起始地址+段内地址。逻辑地址（2，15）查段表得段长度为20，段内地址1540，地址越界，系统发出“地址越界”中断。逻辑地址（3，18）查段表得段长度为20，段内地址180S的值表示可继续进入售票厅的人数S=0表示售票厅中已有20名顾客(购票者)S0|S|的值为等待进入售票厅的人数(2)上框为P(S) 下框为V(S)(3)S的最大值为20 S的最小值为20n注：信号量的符号可不同(如写成t)，但使用时应一致(即上述的s全应改成t)。11 有两个进程P1和P2，它们执行的过程如下：P1: 10秒CPU操作、20秒I/O操作（设备1）、5秒CPU操作、10秒I/O操作（设备2）、5秒CPU操作、结束P1: 15秒I/O操作（设备1）、10秒CPU操作、15秒I/O操作（设备2）、10秒CPU操作、结束（1） 如果进程P1和P2顺序执行，请画出进程P1和P2执行情况图；（2） 如果进程P1和P2并发执行，请画出进程P1和P2执行情况图；（3） 分别计算在（1）和（2）情况下，CPU的利用率、设备1和设备2的利用率。解：(1) P1和P2顺序执行P1:CPUI/O(DEV2)CPUI/O(DEV1)CPU0 10 30 35 45 50P2:CPUI/O(DEV2)CPUI/O(DEV1)50 65 75 90 100(2) P1和P2并发执行 CPU(P1)CPU(P1)1)CPU(P2)CPU(P2)CPU(P1)I/O(DEV1)(P1)I/O(DEV1)(P2)I/O(DEV2)I/O(DEV2)(P2)0 10 15 25 35 40 50 55(3) 在情况（1）下，CPU的利用率=40/100=40%设备1的利用率=35/100=35%设备2的利用率=25/100=25%在情况（2）下，CPU的利用率=40/55=73%设备1的利用率=35/55=64%设备2的利用率=25/55=45%12一个程序P的用户空间为16K,存储管理采用请求式分页系统，每个页面大小为2K，存在以下的页表：页框号有效位121310100211510081其中，有效位1表示页面在内存；0表示页面不在内存。请将虚地址0x060C，0x1502，0x1d71，0x2c27，0x4000转换为物理地址。答：用户地址空间共用14bit表示.范围为:0x00000x3FFF.超过这个范围即为”越界”0x060C：1548+12*2048=0x660C0x1502：0x65020x1d71：缺页0x2c27：0x14270x4000：越界13有一个文件系统，根目录常驻内存，目录文件采用链接式，每个磁盘块存放10个下级文件的描述，最多存放40个下级文件(最多涉及到4个盘块)，若下级文件为目录文件，则上级目录指向该目录文件的第一块，否则指向普通文件的文件控制块。普通文件采用二级索引形式，文件控制块中给出12个磁盘块地址，前10个磁盘块地址指出前10页的物理地址，第11个磁盘块地址指向一级索引表，一级索引表给出256个磁盘块地址，即指出该文件第10页至第256页的地址，第12个磁盘块地址指向二级索引表，二级索引表中指出256个一级索引表的地址。(1) 该文件系统中的普通文件最大可有多少页?(2) 若要读文件/A/D/K/Q中的某一页, 最少要启动磁盘几次? 最多要启动磁盘几次?答：（1）一个文件的所有块可以通过下面三种途径找到：直接通过FCB找到前10块，通过一级索引找到256块，通过二级索引找到256*256块，所以一个文件最大可以有10+256+2562块最坏情况是：每次读取目录描述信息的时候都在最后一个块找到下级的目录或文件，所以要找到Q文件的FCB至少要读取A的第一块，D、G、二个目录项的所有四个块，再读取Q的FCB，总共要1+4*2+110次启动硬盘。找到FCB后再读取该文件页所在的块，如果这一块在前10块之列，那么在启动一次硬盘就可以找到这一块，如果这一块在最后一块，则可能需要通过二级索引找到这一块，这总共需要读取二级索引和最后一块共2+1次读取硬盘。14.一个系统中存在某类资源m个，被n个进程共享。资源的分配和释放必须一个一个进行，请证明在以下两个条件下不会发生死锁：l 每个进程需要资源的最大数在1m之间；l 所有进程需要的资源总数小于m+n；证明：假设进程Pi(0in+1)需要的资源数为Ri，则 R1+R2+.+Rnm+n (1) 1 = Ri = m (2) 假设进程已经分配到的资源为Ai(0in+1)，则Ai=Ri假设当前发生了死锁，则 A1+A2+.+An=m AiRi (0in+1)也就是 Ai+1=Ri 则 A1+A2+.+An+n=R1+R2+.+Rn 即 m+n=R1+R2+.+Rn和（1）矛盾，死锁不成立。15一个请求式分页存储系统，页表存放在内存：l 访问一次内存需要100nsl 如果仅调入一个页面，需要花费8ms（内存有空页面，或需要进行页面置换，单被置换的页面没有修改过）；l 如果调入一个页面同时需要进行被置换页面的写出，则需要20ms;l 假设页面被修改的比例是60%;请问，缺页率必须控制在多少以下，才能使得EAT200ns?解： 假设缺页率为f_rate,则，EAT=(1-f_rate)*100+f_rate*(40%*8000+60%*20000)如EAT200,则，(1- f_rate)*100+f_rate*(40%*8000+60%*20000)200100-100*f_rate+15200*f_rate200151*f_rate1f_rate1/151即缺页率小于0.66%。16一个文件有100个磁盘块，假设文件控制块在内存（如果文件采用索引分配(indexed allocation)，索引表也在内存）。在下列情况下，请计算在contiguous, linked, indexed(single-level)三种分配方式下，分别需要多少次磁盘I/O操作？（每读出或写入一个磁盘块都需要一次磁盘I/O操作）(10%)假设在contiguous分配方式下，文件头部无空闲的磁盘块，但文件尾部有空闲的磁盘块。假设要增加的块信息存放在内存中。l 在文件开始处添加一个磁盘块；l 在文件结尾处添加一个磁盘块；l 在文件中间删除第50块磁盘块；（假设磁盘块编号从099）l 在文件第50块前添加一个磁盘块；（假设磁盘块编号从099）解：l 在文件开始处添加一个磁盘块：连续：201/链接：1/索引：1l 在文件结尾处添加一个磁盘块：连续：1/链接：101/索引：1l 在文件中间删除一个磁盘块：连续：48*211=98/链接：52/索引：0l 在文件中间添加一个磁盘块：连续：101/链接：52/索引：117.一个操作系统有20个进程，竞争使用30个同类资源，申请方式是逐个进行，一旦某个进程获得了它的全部资源，就马上归还所有的资源，每个进程最多使用30，最少使用一个资源。20个进程需要的资源总数小于50。如果仅考虑这类资源，系统会产生死锁吗？请说明理由。 答：设max(i)表示第i个进程的最大资源需求量，need(i)表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知：max(1)+max(20)=(need(1)+need(20)+(alloc(1)+alloc(20)50如果在这个系统中发生了死锁，那么一方面30个资源R应该全部分配出去，即（反证法）alloc(1)+alloc(20)=30另一方面所有进程将陷入无限等待状态。由上述两式可得：need(1)+need(20)20（关键）上式表示死锁发生后，20个进程还需要的资源量之和小于20，这意味着此刻至少存在一个进程i，need(i)=0，即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。18. 一个分页存储系统，页表存放在内存：l 如果访问一次内存需要200ns，则访问一个内存单元需要多少时间？l 如果系统采用三级页表，则访问一个内存单元需要多少时间？l 如果系统引入联想寄存器，90的页表项可以在快表中命中，则访问一个内存单元需要多少时间？（假设访问一次快表需要10ns）解：1、 400 ns(200ns+200ns)(访问页表访问具体内存单元)2、 800 ns（3200ns+200ns）(访问3级页表访问具体内存单元)3、 229 ns（90%10+10%200）+200ns (访问页表的平均时间访问具体内存单元) 18. 设某文件的物理存储方式采用链接方式，该文件由5个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均为512字节，并依次存放在