《操作系统设计应用题解答》由会员分享，可在线阅读，更多相关《操作系统设计应用题解答（8页珍藏版）》请在金锄头文库上搜索。
1、. .1.设有一台计算机，有两条I/O 通道，分别接一台卡片输入机和一台打印机。卡片机把一叠卡片逐一输入到缓冲区 B1 中，加工处理后在搬到缓冲区B2 中，并在打印机上印出，问：系统要设几个进程来完成这个任务？各自的工作是什么？这些进程间有什么样的相互制约关系？用 P、V 操作写出这些进程的同步算法。解：系统可设三个进程来完成这个任务：R 进程负责从卡片输入机上读入卡片信息，输入到缓冲区B1 中；C 进程负责从缓冲区 B1 中取出信息，进展加工处理，之后将结果送到缓冲区B2 中；P 进程负责从缓冲区 B2 中取出信息，并在打印机上印出。R 进程受 C 进程影响，B1 放满信息后 R 进程要等待
2、等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；P(输入信息写入 B1V(B1full段号0123P(B
3、1fullP(B2fullP(B2empty从 B2 中取出信2、现有一个作业，在段式存储管理的系统中已为其主存分配，建立的段表容如下：取 B1 送入 B2息进展打印V(B2emptyV(B1empty12040760480370302020计算逻辑地址2，15，0，60，3，18的绝对地址是多少？注：括号中第一个元素为段号，第二个元素为段地址。解：段式存储管理的地址转换过程为：1根据逻辑地址中的段号查段表的相应栏目；2根据段地址段长度，检查地址是否越界；3假设不越界，那么绝对地址=该段的主存起始地址+段地址。逻辑地址2，15查段表得段长度为 20，段地址 1520，地址不越界，段号2 查表得
4、段首地址为 480，于是绝对地址为 480+15=495。逻辑地址40，地址越界，系统发出“地址越界中断。逻辑地址3，18查段表得段长度为 20，段地址 1820，地址不越界，段号3 查表得段首地址为 370，于是绝对地址=370+18=388。3假设干个等待访问磁盘者依次要访问的柱面为20，44，40，4，80，12，76，假设每移动一个柱面需要3 毫秒时间，移动臂当前位于40 号柱面，请按以下算法分别计算为完成上述各次访问总共花费的寻找时间。1先来先效劳算法；2最短寻找时间优先算法。. -可修编. .解13 毫秒292=876 毫秒 23 毫秒120=360 毫秒注：各算法使移动臂的移动次
5、序和移动的柱面数如下：140 20 44 40 4 80 12 7620 244 36 7668 64 共移动 292 柱面240 44 20 12 4 76 804 248 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假设规定
6、仅允许5 个进程同时读怎样修改程序？解1Sr 用于读者计数 rc 的互斥信号量；2if rc=1 then PS中的 PS用于读写互斥，写者进程中的PS用于写写互斥，读写互斥。3程序中增加一个信号量S5，初值为 5，PS5语句加在读者进程PSr之前，VS5语句加在读者进程第 2 个 V V(S从 Q 读出信息注：信号量 S 的初值为 0. -可修编. .解：这个算法不对。因为 A、B 两进程共用一个缓冲区Q，如果 A 先运行，且信息数量足够多，那么缓冲区Q 中的信息就会发生后面的冲掉前面的，造成信息丧失，B 就不能从 Q 中读出完整的信息。进展改正：A、 B 两进程要同步使用缓冲区Q。为此，设
7、立两个信号量： 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 进程之间存在什么样的制约关系？为保证这三个进程能正确地打印出各自的结果，请用信号量和 P、V 操作写出各自的有关申请、使用打印机的代码。要求给出信号量的含义和初值。解： (1 A、B、C 三个进程之间存在互斥的制约关系。因为打印机属于临界资源，必须一
8、个进程使用完之后另一个进程才能使用。 P(mutex P(mutex申请打印机申请打印机申请打印机使用打印机使用打印机使用打印机 V(mutex V(mutex V(mutex8. 假定在某移动臂磁盘上，刚刚处理了访问75 号柱面的请求，目前正在80 号柱面读信息，并且有下述请求序列等待访问磁盘：请求序列：1234 5 678欲访问柱面号：16040190 188 905832102试用：(1电梯调度算法 (2最短寻找时间优先算法分别列出实际处理上述请求的次序。解(1电梯调度算法:由刚刚处理了访问 75 号柱面的请求，目前正在80 号柱面读信息可知:初始磁头前进的方向是:从小到大. -可修编.
9、 .所以:处理次序为：5814362790 102160188190(2最短寻找时间优先算法:584032处理次序为：5862714390 102 58 4032160 1881909. 有三个进程 P1，P2 和 P3 并发工作。进程 P1 需用资源 S3 和 S1；进程 P2 需用资源 S1 和 S2；进程 P3 需用资源 S2 和 S3。答复：(1假设对资源分配不加限制，会发生什么情况?为什么?(2为保证进程正确工作，应采用怎样的资源分配策略?为什么?解：(1可能会发生死锁例如：进程 P1，P2 和 P3 分别获得资源 S3，S1 和 S2 后再继续申请资源时都要等待，这是循环等待。(或
10、进程在等待新源时均不释放已占资源(2可有几种答案：A.采用静态分配由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象(或不会出现循环等待资源现象。或 B.采用按序分配不会出现循环等待资源现象。或 C.采用银行家算法因为在分配时，保证了系统处于平安状态。10.某车站售票厅，任何时刻最多可容纳20 名购票者进入，当售票厅中少于20 名购票者时，那么厅外的购票者可立即进入，否那么需在外面等待。假设把一个购票者看作一个进程，请答复以下问题：(1用 PV 操作管理这些并发进程时，应怎样定义信号量，写出信号量的初值以及信号量各种取值的含义。(2根据所定义的信号量，把应执行的PV 操作填
11、入下述方框中，以保证进程能够正确地并发执行。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 秒 CP
12、U 操作、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和P1 和 P2 顺序执行P1:CPUI/O(DEV1CPUI/O(DEV2CPU0 10 30 35 45 50P2:I/O(DEV1CPUI/O(DEV2CPU50 65
13、75 90 100(2P1 和 P2 并发执行CPU(P1CPU(P2CPU(P1CPU(P2CPU(P1I/O(DEV1(P2I/O(DEV1(P1I/O(DEV2(P2I/O(DEV20 10 15 25 35 40 50 55(3 在情况1下，CPU 的利用率=40/100=40%设备 1 的利用率=35/100=35%设备 2 的利用率=25/100=25%在情况，假设下级文件为目录文件，那么上级目录指向该目录文件的第一块，否那么指向普通文件的文件控制块。普通文件采用二级索引形式，文件控制块中给出 12 个磁盘块地址，前 10 个磁盘块地址指出前 10 页的物理地址，第 11 个磁盘块
14、地址指向一级索引表，一级索引表给出 256 个磁盘块地址，即指出该文件第 10 页至第 256 页的地址，第 12 个磁盘块地址指向二级索引表，二级索引表中指出 256 个一级索引表的地址。(1 该文件系统中的普通文件最大可有多少页?(2 假设要读文件/A/D/K/Q 中的某一页, 最少要启动磁盘几次? 最多要启动磁盘几次?答：11一个文件的所有块可以通过下面三种途径找到：直接通过一个文件的所有块可以通过下面三种途径找到：直接通过 FCBFCB 找到前找到前 1010 块，通过一级索引找到块，通过一级索引找到 2562562 2块，通过二级索引找到块，通过二级索引找到 256*256256*2
15、56 块，所以一个文件最大可以有块，所以一个文件最大可以有 10+256+25610+256+256 块块最坏情况是：每次读取目录描述信息的时候都在最后一个块找到下级的目录或文件最坏情况是：每次读取目录描述信息的时候都在最后一个块找到下级的目录或文件，所以要找到所以要找到 Q Q 文件的文件的FCBFCB 至少要读取至少要读取 A A 的第一块，的第一块，D D、G G、二个目录项的所有四个块，再读取、二个目录项的所有四个块，再读取 Q Q 的的 FCBFCB，总共要，总共要 1+4*2+11+4*2+11010 次启动次启动硬盘。找到硬盘。找到 FCBFCB 后再读取该文件页所在的块，如果这
16、一块在前后再读取该文件页所在的块，如果这一块在前 1010 块之列，那么在启动一次硬盘就可以找到这块之列，那么在启动一次硬盘就可以找到这一块，如果这一块在最后一块，那么可能需要通过二级索引找到这一块，这总共需要读取二级索引和最后一块一块，如果这一块在最后一块，那么可能需要通过二级索引找到这一块，这总共需要读取二级索引和最后一块共共 2+12+1 次读取硬盘。次读取硬盘。14.一个系统中存在某类资源m 个，被 n 个进程共享。资源的分配和释放必须一个一个进展，请证明在以下两个条件下不会发生死锁：每个进程需要资源的最大数在1m 之间；所有进程需要的资源总数小于m+n；证明：假设进程 Pi(0i需要
17、的资源数为 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一个请求式分页存储系统，页表存放在存：访问一次存需要 100ns如果仅调入一个页面，需要花费8ms存有空页面，或需要进展页面置换，单被置换的页面没有修改正；如果调入一个页面同时需要进展被置换页面的写出，那么需要20ms。假设页面被修改的比例是60%。请问，缺页率必须控
18、制在多少以下，才能使得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 操作？假设在 contiguous 分配方式下，文件头部无空闲的磁盘块，但文件尾部有空闲
19、的磁盘块。假设要增加的块信息存放在存中。在文件开场处添加一个磁盘块；在文件结尾处添加一个磁盘块；在文件中间删除第 50 块磁盘块；假设磁盘块编号从 099在文件第 50 块前添加一个磁盘块；表示第 i 个进程的最大资源需求量，need(i表示第 i 个进程还需要的资源量，. -可修编. .alloc(i表示第 i 个进程已分配的资源量。由题中所给条件可知：max(1+max(20=(need(1+need(20+(alloc(1+alloc(2050如果在这个系统中发生了死锁，那么一方面30 个资源 R 应该全局部配出去，即+alloc(20=30另一方面所有进程将陷入无限等待状态。由上述两式
20、可得：need(1+need(2020=0，即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。18. 一个分页存储系统，页表存放在存：如果访问一次存需要 200ns，那么访问一个存单元需要多少时间？如果系统采用三级页表，那么访问一个存单元需要多少时间？如果系统引入联想存放器，90的页表项可以在快表中命中，那么访问一个存单元需要多少时间？(400 ns(200ns+200ns(访问页表访问具体存单元访问页表访问具体存单元 2 2、 800 ns3800 ns 3229 ns90%229
21、 ns 18. 设某文件的物理存储方式采用方式，该文件由5 个逻辑记录组成，每个逻辑记录的大小与磁盘块大小相等，均为 512 字节，并依次存放在 50、121、75、80、63 号磁盘块上。10 分文件的第 1569 逻辑字节的信息存放在哪一个磁盘块上？要访问第 1569 逻辑字节的信息，需要访问多少个磁盘块？假设该文件的 FCB 在存答：因为：1569=5123+33所以要访问字节的逻辑记录号为3，对应的物理磁盘块号为80。故应访问第 80 号磁盘块。由于采用方式，所以要访问第 3 个逻辑记录的信息，必须访问逻辑记录第 0、1、2 后，才能访问第 3 个逻辑记录，所以要访问第 1569 逻辑字节的信息，需要访问4 个磁盘块。申明：所有资料为本人收集整理，仅限个人学习使用，勿做商业用途。. -可修编.
