操作系统应用题解答.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；从B2中取出信息进行打印V(B2emptyP(B1fullP(B2empty取B1送入B2V(B1emptyV(B2fullP(B1empty输入信息写入B1V(B1fullp1EanqFDPw2、现有一个作业，在段式存储管理的系统中已为其主存分配，建立的段表内容如下：段号主存起始地址段基址）段长度012040176030248020337020计算逻辑地址2，15），0，60），3，18）的绝对地址是多少？注：括号中第一个元素为段号，第二个元素为段内地址。解：段式存储管理的地址转换过程为：1）根据逻辑地址中的段号查段表的相应栏目；2）根据段内地址段长度，检查地址是否越界；3）若不越界，则绝对地址=该段的主存起始地址+段内地址。逻辑地址2，15）查段表得段长度为20，段内地址1520，地址不越界，段号2查表得段首地址为480，于是绝对地址为480+15=495。逻辑地址40，地址越界，系统发出“地址越界”中断。逻辑地址3，18）查段表得段长度为20，段内地址1820，地址不越界，段号3查表得段首地址为370，于是绝对地址=370+18=388。DXDiTa9E3d3若干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。 RTCrpUDGiT1）先来先服务算法； 2）最短寻找时间优先算法。解1）3毫秒292=876毫秒 2）3毫秒120=360毫秒 注：各算法使移动臂的移动次序和移动的柱面数如下： 1）40 20 44 40 4 80 12 76 20） 24）4） 36） 76）68） 64） 共移动292柱面 2）40 44 20 12 4 76 80 4） 24）8） 8） 72） begin P(Sr rc:=rc+1。 if rc=1 then P(S。 V(Sr。 read file。 P(Sr。 rc:=rc-1 if rc=0 thenV(S。 V(Sr。 end 。 PROCESS Writer j (j=1,2 begin P(S。 Write file。 V(Send。 coend 。 end。 请回答：1）信号量 Sr的作用；2）程序中什么语句用于读写互斥，写写互斥；3）若规定仅允许5个进程同时读怎样修改程序？xHAQX74J0X解1）Sr用于读者计数rc的互斥信号量； 2）if rc=1 then PS）中的PS）用于读写互斥，写者进程中的PS）用于写写互斥，读写互斥。LDAYtRyKfE3）程序中增加一个信号量S5，初值为5，PS5）语句加在读者进程PSr）之前，VS5）语句加在读者进程第2个V V(S 从Q读出信息注：信号量S的初值为0解：这个算法不对。因为A、B两进程共用一个缓冲区Q，如果A先运行，且信息数量足够多，那么缓冲区Q中的信息就会发生后面的冲掉前面的，造成信息丢失，B就不能从Q中读出完整的信息。dvzfvkwMI1进行改正：A、 B两进程要同步使用缓冲区Q。为此，设立两个信号量： empty表示缓冲区Q为空，初值为1； full表示缓冲区Q为满，初值为0。算法框图如图所示。 A进程 B进程P(empty P(full向Q写入信息从Q中读出信息 V(full V(empty7.有三个用户进程A、B和C，在运行过程中都要使用系统中的一台打印机输出计算结果。(1) 试说明A、B、C进程之间存在什么样的制约关系？(2) 为保证这三个进程能正确地打印出各自的结果，请用信号量和P、V操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。rqyn14ZNXI解： (1 A、B、C三个进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一个进程使用完之后另一个进程才能使用。EmxvxOtOco P(mutex P(mutex申请打印机申请打印机申请打印机使用打印机使用打印机使用打印机 V(mutex V(mutex V(mutex 8. 假定在某移动臂磁盘上，刚刚处理了访问75号柱面的请求，目前正在80号柱面读信息，并且有下述请求序列等待访问磁盘：SixE2yXPq5请求序列：1 2 3 4 5 6 7 8欲访问柱面号：160 40190 188 905832102试用：(1电梯调度算法 (2最短寻找时间优先算法分别列出实际处理上述请求的次序。解(1电梯调度算法:由”刚刚处理了访问75号柱面的请求，目前正在80号柱面读信息”可知:初始磁头前进的方向是:”从小到大”6ewMyirQFL所以:处理次序为：5814362790102160188190584032(2最短寻找时间优先算法:处理次序为：5862714390102 584032160 1881909. 有三个进程P1，P2和P3并发工作。进程P1需用资源S3和S1；进程P2需用资源S1和S2；进程P3需用资源S2和S3。回答：kavU42VRUs(1若对资源分配不加限制，会发生什么情况?为什么?(2为保证进程正确工作，应采用怎样的资源分配策略?为什么?解：(1可能会发生死锁例如：进程P1，P2和P3分别获得资源S3，S1和S2后再继续申请资源时都要等待，这是循环等待。(或进程在等待新源时均不释放已占资源(2可有几种答案：A.采用静态分配由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象。y6v3ALoS89或B.采用按序分配不会出现循环等待资源现象。或C.采用银行家算法因为在分配时，保证了系统处于安全状态。10.某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：M2ub6vSTnP(1用PV操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。(2根据所定义的信号量，把应执行的PV操作填入下述方框中，以保证进程能够正确地并发执行。COBEGINPROCESSPI(I=1，2， begin；进入售票厅；购票；退出；end；COEND(3若欲购票者最多为n个人，写出信号量可能的变化范围(最大值和最小值。解(1定义一信号量S，初始值为20。意义：S0S的值表示可继续进入售票厅的人数S=0表示售票厅中已有20名顾客(购票者S上框为P(S 下框为V(S(3S的最大值为20 S的最小值为20n注：信号量的符号可不同(如写成t，但使用时应一致(即上述的s全应改成t。11 有两个进程P1和P2，它们执行的过程如下：P1: 10秒CPU操作、20秒I/O操作设备1）、5秒CPU操作、10秒I/O操作设备2）、5秒CPU操作、结束0YujCfmUCwP1: 15秒I/O操作设备1）、10秒CPU操作、15秒I/O操作设备2）、10秒CPU操作、结束eUts8ZQVRd（1） 如果进程P1和P2顺序执行，请画出进程P1和P2执行情况图；（2） 如果进程P1和P2并发执行，请画出进程P1和P2执行情况图；（3） 分别计算在1）和P1和P2顺序执行P1:CPUI/O(DEV2CPUI/O(DEV1CPU0 10 30 35 45 50sQsAEJkW5TP2:CPUI/O(DEV2CPUI/O(DEV150 65 75 90 100GMsIasNXkA(2P1和P2并发执行CPU(P1CPU(P11CPU(P2CPU(P2CPU(P1I/O(DEV1(P1I/O(DEV1(P2I/O(DEV2I/O(DEV2(P20 10 15 25 35 40 50 55TIrRGchYzg(3 在情况1）下，CPU的利用率=40/100=40%设备1的利用率=35/100=35%设备2的利用率=25/100=25%在情况，若下级文件为目录文件，则上级目录指向该目录文件的第一块，否则指向普通文件的文件控制块。普通文件采用二级索引形式，文件控制块中给出12个磁盘块地址，前10个磁盘块地址指出前10页的物理地址，第11个磁盘块地址指向一级索引表，一级索引表给出256个磁盘块地址，即指出该文件第10页至第256页的地址，第12个磁盘块地址指向二级索引表，二级索引表中指出256个一级索引表的地址。(1 该文件系统中的普通文件最大可有多少页?7EqZcWLZNX(2 若要读文件/A/D/K/Q中的某一页, 最少要启动磁盘几次? 最多要启动磁盘几次?答：1）一个文件的所有块可以通过下面三种途径找到：直接通过FCB找到前10块，通过一级索引找到256块，通过二级索引找到256*256块，所以一个文件最大可以有10+256+2562块lzq7IGf02E最坏情况是：每次读取目录描述信息的时候都在最后一个块找到下级的目录或文件，所以要找到Q文件的FCB至少要读取A的第一块，D、G、二个目录项的所有四个块，再读取Q的FCB，总共要1+4*2+110次启动硬盘。找到FCB后再读取该文件页所在的块，如果这一块在前10块之列，那么在启动一次硬盘就可以找到这一块，如果这一块在最后一块，则可能需要通过二级索引找到这一块，这总共需要读取二级索引和最后一块共2+1次读取硬盘。zvpgeqJ1hk14.一个系统中存在某类资源m个，被n个进程共享。资源的分配和释放必须一个一个进行，请证明在以下两个条件下不会发生死锁：NrpoJac3v1l 每个进程需要资源的最大数在1m之间；l 所有进程需要的资源总数小于m+n；证明：假设进程Pi(0i需要的资源数为Ri，则 R1+R2+.+Rn 1 = Ri 假设进程已经分配到的资源为Ai(0i，则Ai=Ri假设当前发生了死锁，则 A1+A2+.+An=m AiRi (0i也就是 Ai+1=Ri 则 A1+A2+.+An+n=R1+R2+.+Rn 即 m+n=R1+R2+.+Rn和1）矛盾，死锁不成立。15一个请求式分页存储系统，页表存放在内存：l 访问一次内存需要100nsl 如果仅调入一个页面，需要花费8ms内存有空页面，或需要进行页面置换，单被置换的页面没有修改过）；l 如果调入一个页面同时需要进行被置换页面的写出，则需要20ms。l 假设页面被修改的比例是60%。请问，缺页率必须控制在多少以下，才能使得EAT*100+f_rate*(40%*8000+60%*20000如EAT*100+f_rate*(40%*8000+60%*20000200100-100*f_rate+15200*f_rate200151*f_rate1f_rate1/151即缺页率小于0.66%。16一个文件有100个磁盘块，假设文件控制块在内存，索引表也在内存）。在下列情况下，请计算在contiguous, linked, indexed(single-level三种分配方式下，分别需要多少次磁盘I/O操作？1nowfTG4KI假设在contiguous分配方式下，文件头部无空闲的磁盘块，但文件尾部有空闲的磁盘块。假设要增加的块信息存放在内存中。fjnFLDa5Zol 在文件开始处添加一个磁盘块；l 在文件结尾处添加一个磁盘块；l 在文件中间删除第50块磁盘块；假设磁盘块编号从099）l 在文件第50块前添加一个磁盘块；表示第i个进程的最大资源需求量，need(i表示第i个进程还需要的资源量，alloc(i表示第i个进程已分配的资源量。由题中所给条件可知：max(1+max(20=(need(1+need(20+(alloc(1+alloc(2050HbmVN777sL如果在这个系统中发生了死锁，那么一方面30个资源R应该全部分配出去，即+alloc(20=30V7l4jRB8Hs另一方面所有进程将陷入无限等待状态。由上述两式可得：need(1+need(2020=0，即它已获得了所需要的全部资源