《操作系统原理》习题及参考答案.pdf 21页

'《操作系统原理》习题及参考答案１．操作系统的定义。操作系统的五大基本功能。网络操作系统相对单机操作系统还应具备什么功能？解：操作系统是计算机系统的一种系统软件，由它统一管理计算机系统中的软硬件资源，合理地组织工作流程，以便有效地为用户提供一个功能强大、使用方便的工作环境，从而在计算机与用户之间起到接口的作用。操作系统的五大基本功能是：处理机管理、存储器管理、设备管理、文件系统管理和用户接口。网络操作系统还应具备的功能：网络通信、资源共享、网络服务、网络用户接口。２．设有三个进程A、B、C，进程A需8毫秒处理时间，B需2毫秒处理时间，C需24毫秒处理时间，分别考虑在就绪队列中的顺序为ABC时及CBA时，用先来先服务算法进行调度时的平均等待时间。解：当顺序为ABC时：Wa=0Wb=8Wc=10Mw=(0+8+10)/3=6ms当顺序为CBA时：Wc=0Wb=24Wc=26Mw=(0+24+26)/3=17ms３．设在内存中有三道程序：A、B、C，并按照A、B、C的优先次序运行，其内部计算和I/O操作时间由下图给出。程序A程序B程序C计算30ms计算60ms计算20msI/O40msI/O30msI/O40ms计算10ms计算10ms计算20ms要求：（1）试画出按多道程序运行的时间关系图（调度程序的执行时间忽略不计）。完成这三道程序共花多少时间？比单道运行节省多少时间？（2）若处理机调度程序每次进行程序状态转换的时间为1ms，试画出在处理机调度程序管理下各程序状态转换的时间关系图。完成这三道程序共花多少时间？解：(1)在调度程序执行时间忽略不计的情况下，这三道程序的执行时间如下图所示：1 总的执行时间为180ms.如果单道执行这三个程序共需80+100+80=260ms.所以节约260－180ms.(2)若处理机调度程序每次进行程序状态转换的时间为1ms，这三道程序的执行时间如下图所示：总共花费180+6=186ms.４．系统调用（陷入）处理过程。解：系统调用（陷入）处理过程和中断处理过程是一样的，只是中断源是执行了访管指令（MSDOS的INT或UNIX的trap）。①CPU检查响应中断的条件是否满足。②如果CPU响应中断，则CPU关中断，使其进入不可再次响应中断的状态。③保存被中断的现场。④分析中断原因，调用中断处理子程序。⑤执行中断处理子程序。⑥退出中断，恢复被中断进程的现场或调度新进程占据处理器。⑦开中断，CPU继续执行。５．有5个中断源D1、D2、D3、D4和D5，它们的中断优先级从高到低依次是1-5级别。这些中断源的中断优先级、正常情况下的中断屏蔽码和改变后的中断屏蔽码如下表所示。每个中断源有5位中断屏蔽码，其中0表示该中断源开放，1表示该中断源被屏蔽。2 中中断正常的中断屏蔽码改变后的中断屏蔽码断优先源级D1D2D3D4D5D1D2D3D4D5D111111110000D220111111000D330011111100D440001111111D550000111101(1)当使用正常的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是什么？实际上中断处理的先后次序是什么？(2)当使用改变后的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是什么？实际上中断处理的先后次序是什么？(3)如果采用改变后的中断屏蔽码，D1、D2、D3、D4和D5同时请求中断时，画出处理器响应各中断源的中断请求和实际运行中断服务程序过程的示意图。解：(1)当使用正常的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是D1、D2、D3、D4、D5。实际上中断处理的先后次序是D1、D2、D3、D4、D5。(2)当使用改变后的中断屏蔽码时，处理器响应各中断源的中断请求的先后顺序是D1、D2、D3、D4、D5。实际上中断处理的先后次序是D4、D5、D3、D2、D1。(3)如果采用改变后的中断屏蔽码，D1、D2、D3、D4和D5同时请求中断时，处理器响应各中断源的中断请求和实际运行中断服务程序过程如下图所示：６．进程有哪几种基本状态？作业有哪几种基本状态？画出作业进程基本状态关系图。解：进程有三种基本状态：就绪态、运行态、等待态。作业有四种基本状态：输入态（提交态）、后备态（收容态）、执行态、完成态。3 ７．系统调用fork()工作过程。（1）为子进程在proc结构表中分配一个空项；（2）为子进程赋一个唯一的PID（3）复制父进程上下文的逻辑副本。（4）增加与父进程相关联的有关文件系统的进程引用技术。（5）对父进程返回子进程的PID，对子进程返回为0.语法：pid=fork();一个fork()系统调用程序实例#include#include#includemain(){pid_tval;printf("PIDbeforefork():%d",(int)getpid());val=fork();if(val!=0)printf("parentprocessPID:%dn",(int)getpid());elseprintf("childprocessPID:%dn",(int)getpid());}执行结果：PIDbeforefork():2000parentprocessPID:2000childprocessPID:2001８．什么是进程？简述进程与程序、线程的区别和联系。解：进程是一个具有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。进程与程序的区别和联系是：1)进程是一个动态概念，程序是一个静态概念。2)进程具有并行特征，程序没有并行特征。4 3)进程是竞争计算机系统资源的基本单位。4)不同的进程可以包含同一程序，只要该程序所对应的数据集不同。进程和线程的区别和联系是：1)线程是进程的一个组成部分。2)进程的多线程都在进程的地址空间活动。3)资源是分给进程的，而不是线程的。4)调度的基本单位是线程。5)线程在执行过程中，需要同步。９．常用的进程调度算法和作业调度算法有哪些？哪些适用于作业调度？哪些适用于进程调度？解：常用的作业调度算法有：先来先服务算法（FCFS）、最短作业优先算法（SJF）、最高响应比优先算法（HRRN）、优先级调度算法、均衡调度算法等。常用的进程调度算法有：先来先服务算法（FCFS）、优先级调度算法、时间片轮转调度算法（RR）、分级调度算法、多级反馈轮转算法（MultiLevelFeedbackQueue）等。１０．处理机调度的目的是什么？有哪几种类型？每种调度的主要任务是什么？解：处理机调度的目的是使处理机在满足系统要求的响应时间、吞吐量和处理机利用率的前提下及时地运行进程。调度有4种类型：长程调度：决定欲增加执行的进程池；中程调度：决定增加部分或全部位于内存中进程数；短程调度：决定哪个就绪进程被处理机执行；I/O调度：决定哪个进程未完成的I/O请求可被I/O设备处理。１１．对于下列三个作业，采用不可抢占的调度方式：先来先服务算法和短作业优先算法，当第一个作业进入系统后开始调度，填写下面的表格。先来先服务算法：作业号进入输入需运行时开始运行完成时间周转时间带权周转井时间间（小时）时间时间A8:006.4B8:243.2C9:001短作业优先算法：作业号进入输入需运行时开始运行完成时间周转时间带权周转井时间间（小时）时间时间A8:006.4B8:243.2C9:001解：先来先服务算法：作业号进入输入需运行时开始运行完成时间周转时间带权周转井时间间（小时）时间时间A8:00(8.0)6.48.014.46.41B8:24(8.4)3.214.417.69.22.9C9:00(9.0)117.618.69.69.6短作业优先算法：作业号进入输入需运行时开始运行完成时间周转时间带权周转井时间间（小时）时间时间A8:00(8.0)6.48.014.46.415 B8:24(8.4)3.215.418.610.23.2C9:00(9.0)114.415.46.46.4１２．什么是进程同步？解：进程同步是指并发进程之间存在一种直接制约关系，一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到达才被唤醒。１３．设有两个优先级相同的进程P1、P2如下。令信号量S1、S2的初值均为0，试问P1、P2并发执行结束后x=?y=?z=?写出并发执行的细节。（10分）进程P1进程P2x:=0;y:=1;x:=x+2;y:=y+2;P(S1);V(S1);x:=x+z;z:=2*y+1;V(S2);P(S2);z:=x+z;y:=z+y;解：①假设P1先执行，P2后执行：xyzS1S2P1x:=0000P1x:=x+22000P1P(S1)2-10P2y:=121-10P2y:=y+2230-10P2V(S1)23000P2z:=2*y+123700P2P(S2)2370-1P1x:=x+z9370-1P1V(S2)93700P1z:=x+z931600P2y:=z+y9191600所以x=9,y=19,z=16②假设P2先执行，P1后执行：xyzS1S2P2y:=1100P2y:=y+2300P2V(S1)310P2z:=2*y+13710P2P(S2)371-1P1x:=00371-1P1x:=x+22371-1P1P(S1)2370-1P1x:=x+z9370-1P1V(S2)93700P1z:=x+z931600P2y:=z+y9191600所以x=9,y=19,z=166 １４．利用PV操作，怎样才能保证进程Pi能按下面两图的次序正确执行，其中S表示开始，F表示结束。解：（1）设信号量S2:=0;S3:=0;S4:=0;P1:P2:P3:P4:……..P(S2)P(S3)P(S4)……..……..……..P(S4)V(S2)…….…….……..V(S3)V(S4)V(S4)…….（2）设信号量S3:=0;S4:=0;S5:=0;S6:=0;P1:P2:P3:P4:P5:P6:……..……..P(S3)P(S4)P(S5)P(S6)……..……..P(S3)…….…….…….……..…….……..……..……..……..V(S3)V(S3)V(S4)…….…….…….V(S5)V(S6)１５．设一个飞机航班售票系统有n个售票处，每个售票处通过终端访问系统的公共数据区。假定公共数据区中的一些单元Aj(j=1,2,3,…)分别存放某月某日某次航班的余票数。用P1,P2,…,Pn表示个售票处为旅客服务时的处理进程；R1,R2,R3…,Rn为各进程执行时所用的工作单元。用PV操作和信号量保证售票系统的正确并发执行。解：ò实现A、B进程间同步应设置2个信号量S1,S2.信号量S1表示缓冲区是否为空；信号量S2表示缓冲区是否为满。òS1的初值为1；S2的初值为0.ò同步算法Beginmutex:semaphore;Aj:integer;mutex:=1;S2:=0;Cobegin7 ProcessPi(i=1,2,3,…,n)Begin按旅客定票要求找到Aj;P(mutex);Ri=Aj;ifRi>=1thenRi=Ri-1;Aj=Ri;输出一张票；V(mutex);else输出“票已售完”；V(mutex);End;Coend;End.１６．设有两个进程A、B，它们是一对相互合作的进程，共用一个缓冲区。进程A负责从输入设备读一个记录送入缓冲区；进程B负责取走缓冲区中的记录并进行加工处理。问：（1）用信号量机制实现A和B进程间同步应设置几个信号量？（2）信号量的初值是什么？（3）写出实现两进程共享缓冲区的同步算法。解：ò实现A、B进程间同步应设置2个信号量S1,S2.信号量S1表示缓冲区是否为空；信号量S2表示缓冲区是否为满。òS1的初值为1；S2的初值为0.ò同步算法BeginS1,S2:semaphore;S1:=1;S2:=0;CobeginProcessPAProcessPBBL1:输入设备读一记录；L2:P(S2);P(S1);取走缓冲区中的记录；送入缓冲区；V(S1);V(S2);送入缓冲区；GotoL1;GotoL2;Coend;End.１７．什么是死锁？列出死锁的四个必要条件。解：若系统中存在一组进程（两个或多个进程），它们中的每一个进程都占用了某种资源而又在等待该组中的别的进程所占用的资源，在获得自己所需要的对方资源之前决不释放自己所占用的资源，这种等待永远不能结束的状态称为死锁。死锁的四个必要条件是：1)互斥使用资源2)占有且等待资源3)非抢占式分配4)循环等待资源8 １８．某系统有ABCD四类资源供5个进程共享，进程对资源的要求和分配情况如表所示，现在系统剩余资源A类1个，B类5个，C类2个，D类0个。根据银行家算法判定：现在系统是否处于安全状态？为什么？已占资源数最大需求数进程ABCDABCDP100120012P210001756P313542356P406320652P500140656解：银行家此时拥有的资源为(A,B,C,D)=(1,5,2,0);P1距离最大需求为：(0,0,1,2)-(0,0,1,2)=(0,0,0,0)P2距离最大需求为：(1,7,5,6)-(1,0,0,0)=(0,7,5,6)P3距离最大需求为：(2,3,5,6)-(1,3,5,4)=(1,0,0,2)P4距离最大需求为：(0,6,5,2)-(0,6,3,2)=(0,0,2,0)P5距离最大需求为：(0,6,5,6)-(0,0,1,4)=(0,6,4,2)根据银行家算法，如果按下面的顺序分配资源：(1,5,2,0)->P1->(1,5,2,0)+(0,0,1,2)=(1,5,3,2)->P3->(1,5,3,2)+(1,3,5,4)=(2,8,8,6)->P2->(2,8,8,6)+(1,0,0,0)=(3,8,8,6)->P4->(3,8,8,6)+(0,6,3,2)=(3,14,11,8)->P5->(3,14,11,8)+(0,0,1,4)=(3,14,12,12).可以回收全部资源。所以现在系统处于安全状态。１９．若系统中有同类资源37个，每个进程至多允许申请5个资源，问最多允许多少个进程并发执行而且确保必定不会发生死锁。解：9个。【更泛化的问题是：若系统中有同类资源m个，被n个进程共享（m>n>0），问每个进程至多允许申请多少个资源时必定不会发生死锁。思路：设每个进程申请资源的最大个数为x(1<=x<=m)。最坏情况下，每个进程都已经申请到(x-1)个资源，并正在申请最后一个资源，只要系统中至少还有1个资源就能使其中某个进程得到所需要的全部资源而执行完，然后就释放出x个资源供其它进程使用。如此链式反应，最终所有的进程均能执行完毕。因此只要满足不等式：n(x-1)+1<=m】存储管理２０．什么是地址重定位？它有哪两种基本方法。解：地址重定位就是将逻辑地址转换成物理地址的工作。分为静态重定位和动态重定位两种。２１．某系统采用页式存储管理策略。某进程的逻辑地址空间为32页，页的大小为2KB，物理地址空间的大小是4MB。（1）写出逻辑地址的格式。9 （2）该进程的页表有多少项？每项至少占多少位？（3）如果物理地址空间减少一半，页表的结构有何变化？解：（1）写出逻辑地址的格式。5由于该进程的逻辑地址空间为32页=2页，因此逻辑地址中的页号部分需要5位。由于11每页的大小为2KB=2B，因此逻辑地址中的页内偏移部分需要11位。这样逻辑地址格式如图所示：1511100页号页内偏移（2）该进程的页表有多少项？每项至少占多少位？由于该进程的逻辑地址空间为32页，因此该进程的页表项有32项。页表项中应存储为该虚页映射的物理块块号。因为该进程所拥有的4MB的物理地址空11间被分成4MB/2KB=2K=2个块，所以块号部分需要占11位。因此每个页表项至少占11位。（3）如果物理地址空间减少一半，页表的结构有何变化？即使该进程所拥有的物理地址空间减半，但由于其逻辑地址空间不变（仍为32页），所以该进程的页表项不变（仍有32项）。因为该进程所拥有的2MB的物理地址空间被分10成2MB/2KB=2K=2个块，所以块号部分需要占10位。因此每个页表项至少占10位。２２．某段式存储管理系统的段表如图所示。段号段大小段始址015KB40KB18KB80KB210KB100KB请将逻辑地址[0,137]、[1,9000]、[2,3600]、[3,230]转换成物理地址。解：（1）逻辑地址[0,137]：表示段号为0，段内偏移为137。根据段号查段表，得到该段0的起始地址为40KB，段长为15KB。由于段号0小于段表长度，故段号合法；段内偏移137小于段长15KB，故段内偏移合法。因此可得到映射到的物理地址为：40KB+137B=40960B+137B=41097B。（2）逻辑地址[1,9000]：表示段号为1，段内偏移为9000。根据段号查段表，得到该段1的起始地址为80KB，段长为8KB。由于段号0小于段表长度，故段号合法；段内偏移9000大于段长8KB（8192B），故段内偏移越界，产生越界中断。（3）逻辑地址[2,3600]：表示段号为2，段内偏移为3600。根据段号查段表，得到该段2的起始地址为100KB，段长为10KB。由于段号0小于段表长度，故段号合法；段内偏移3600小于段长10KB（10240B），故段内偏移合法。因此可得到映射到的物理地址为：100KB+3600B=102400B+3600B=106000B。（4）逻辑地址[3,2300]：表示段号为3，段内偏移为2300。根据段号查段表，发现段号3大于段表长度，故段号非法，因此产生越界中断。虚拟存储器10 ２３．内存扩充有哪几种方法？常用的内存管理方法有哪几种？哪些方法支持多道程序设计？哪些方法支持虚拟存储器？解：内存扩充的方法包括覆盖技术、交换技术和虚拟存储器技术。常用的内存管理方法有：单一连续区管理、分区管理（分为固定分区管理和可变分区管理）、页式管理、段式管理和段页式管理。其中分区管理（分为固定分区管理和可变分区管理）、页式管理、段式管理和段页式管理支持多道程序设计。只有页式管理、段式管理和段页式管理支持虚拟存储器。２４．在请求页面置换算法中，FIFO算法有时会出现BELADY现象。设某进程共有5页，访问顺序为1,2,3,4,1,2,5,1,2,3,4,5。问：①若在内存中分配了3个页面，则缺页中断次数为多少？换页次数是多少？②若在内存中分配4个页面，则缺页中断次数？换页次数是多少？③此时，是否出现了BELADY现象，并请说明理由。解：①若在内存中分配了3个页面访问页号123412512345Frame1111444555555Frame222211111333Frame33332222244缺页中断╳╳╳╳╳╳╳╳╳所以缺页中断次数为9，换页次数为6。②若在内存中分配了4个页面访问页号123412512345Frame1111111555544Frame222222211115Frame33333332222Frame4444444333缺页中断╳╳╳╳╳╳╳╳╳╳所以缺页中断次数为10，换页次数为6。③此时出现了Belay现象。因为随着分配给进程的页面数增多，缺页中断次数不但没有降低，反而有所增加的奇怪现象。２５．如果一个进程在执行过程中，访问的页号顺序如下：12342156212376321236进程固定占用3个页面。问：LRU置换法产生多少次缺页中断？并按顺序写出产生缺页中断时淘汰的页号。解：LRU算法过程访问页12342156212376321236号Frame11112134142435152531112137172732122212223Frame221222321222361626364313233313233333132Frame3313233111213212221222361626311121361缺页中╳╳╳╳╳╳╳╳╳╳╳╳╳╳╳断134215612761缺页中断次数为15.产生缺页中断时淘汰的页号依次是：13421561276111 ２６．某系统采用请求分页式存储管理方式，主存被划分为64个块，每块为1KB，每个进程只分配3块内存。若需调入新页而无空闲块时，按先进先出算法(FIFO)置换。现有进程A，其页表如下表所示。状态”0”表示页在内存，状态”1”表示页不在内存。页面调入顺序为：0，1，2。问：（1）将逻辑地址(0A5C)16转换成十六进制的物理地址是多少？（2）将逻辑地址(0E4A)16转换成十六进制的物理地址是多少？页号状态块号00210520831解：起始地址Frame号/Page号FC0063。。。…24009200081C0071800614005100040C003080020400100000可见逻辑地址(0A5C)16位于虚页2中（0800H<0A5CH<0C00H），根据页表，可知该页面已经调入内存，位置为物理块号8中。所以(0A5C)16在存储空间中的物理地址是：8×(0400H)+(0A5CH－0800H)=2000H+025CH=225CH亦可见逻辑地址(0E4A)16位于虚存页号3中（0C00H<0E4AH<1000H），根据页表，可知该页面尚未调入内存。由于当前进程已将三块物理块用完，所以需要换页。根据FIFO算法，将最先调入内存的虚页0淘汰，则物理块号2空闲，然后将虚页3调入物理块号2。所以(0E4A)16在存储空间中的物理地址是：2×(0400H)+(0E4AH－0C00H)=0800H+024AH=0A4AH２７．段页式存储管理的基本思想。解：因为段式管理和页式管理各有所长。段式管理为用户提供了一个二维的虚拟地址空间，反映了程序的逻辑结构，有利于段的动态增长以及共享和内存保护等，这极大地方便了用户。页式管理则有效地克服了内存碎片，提高了存储器的利用效率。从存储管理的目的来看，主要是方便了用户的程序设计和提高了内存的利用率。所以提出了将段式管理和页式管理结合起来让其取长补短的段页式管理。12 段页式管理时，一个进程仍然拥有一个自己的二维地址空间，这与段式管理相同。首先，一个进程中所包含的具有独立逻辑功能的程序或数据仍然被划分成段，并有各自的段号s，这反映和继承了段页式管理的段式管理的特征。其次，对于段s中的程序或数据，则按照一定的大小将其划分为不同的页。和页式管理一样，最后不足一页的部分仍占一页。这反映了段页式管理的页式特征。每个进程都拥有一张段表，段表中的每个段都拥有一张页表，通过它们来进行地址重定位。２８．在请求页式存储管理系统中，页面大小是100字节。有一个50×50的数组按行连续存放，每个元素为整数占2字节。有两个数组初始化程序A和B如下。程序A程序Binti,j;inti,j;inta[50][50];inta[50][50];for(inti=0;i<50;i++)for(intj=0;j<50;j++)for(intj=0;i<50;j++)for(inti=0;i<50;i++)a[i][j]=0;a[i][j]=0;若程序在执行过程中只有一个内存页面（Frame）来存放数组。试问：程序A和程序B在执行时产生的缺页中断次数分别是多少？解：由题目可知，数值a有50×50=2500个整数，每个整数占2字节，所以数组共需要虚存空间为2500×2=5000字节。由于每个页面的大小是100字节，所以数组占用的虚存空间为5000/100=50个page。由于数组是按行连续存放，所以各页的内容如下所示：Page0a[0][0]a[0][1]……a[0][48]a[0][49]1a[1][0]a[1][1]……a[1][48]a[1][49]…48a[48][0]a48][1]……a[48[48]a[48][49]49a[49][0]a[49][1]……a[49][48]a[49][49]对于程序A：由于数组的初始化是按行进行的，因此每当发生一次缺页中断，调入一页，可以对位于该页的一行数组元素进行初始化，然后再发生一次缺页中断…所以缺页中断次数为数组的行数50次。对于程序B：由于数组的初始化是按行进行的，因此每当发生一次缺页中断，调入一页，可以对位于该页的一个数组元素进行初始化，然后再发生一次缺页中断…所以缺页中断次数为数组的元素个数2500次。文件系统２９．文件的逻辑结构有哪两种？物理结构有哪几种？文件的存取方式有几种？哪种物理结构不支持随机存取？解：文件的逻辑结构有两种：无结构的流式文件和有结构的记录式文件。物理结构有三种：连续结构、链接结构和索引结构。（有的教材是四种：连续、链接、索引和混合）。文件的存取方式有两种：顺序存取和随机存取。链接结构文件不支持随机存取。13 无结构文件（流式文件）按逻辑连续结构结构分多重结构有结构文件（记录式文件）转置结构顺序结构连续文件按物理串联文件结构分索引文件３０．文件结构、文件存取方式与文件存储介质的关系存储介质磁带磁盘物理结构连续结构连续结构链接结构（串联结构）索引结构顺序顺序顺序存取方式顺序存取随机随机３１．假设物理块大小为512字节。目录文件有128个目录项，一个目录项占48个字节。查找一个文件的平均访盘次数是多少？如果将目录项分解为符号目录项和基本目录项：符号目录项占8字节（其中文件名6字节，文件号2字节），基本目录项占42字节（48字节-6字节）。那么查找一个文件的平均访盘次数又是多少？解：（1）分解前：一个物理块可容纳512/48=10个FCB。如果目录文件有128个FCB，则需占128/10=13个物理块。查找一个文件的平均访盘次数为(1+13)/2=7次。（2）分解后：一个物理块可容纳512/8=64个符号目录项或512/42=12个基本目录项。如果目录文件有128个FCB，则符号目录项占128/64=2个物理块，基本目录项占128/12=11个物理块。查找一个文件的平均访盘次数为(1+2)/2+1=2.5次。３２．某文件系统中，根目录常驻内存。目录文件采用链接结构，它指出下级文件名、文件类型及磁盘地址（共占10个字节）。如果下级文件是目录文件，则上级目录项指向该目录文件的第一个磁盘块地址；如果下级文件是普通文件，则上级目录项指向该文件的文件控制块的磁盘地址。每个目录文件磁盘块最后12个字节供链指针使用，并规定一个目录下最多存放180个下级文件。下级文件在上级目录文件中的次序在图中为从左至14 右。每个磁盘块为512字节。（1）若普通文件按顺序结构组织，要读文件O的第15块，最少启动磁盘多少次？最多启动磁盘多少次？（2）若普通文件按链接结构组织，要读文件L的第15块，最少启动磁盘多少次？最多启动磁盘多少次？（3）若要加快文件目录的检索，可采取什么解决方法？解：已知每个磁盘块为512字节，而每个目录文件磁盘块最后12个字节供链指针使用，所以每块可用于存放文件目录的空间为512-12=500字节。此外每个目录项占10个字节，且一个目录下最多存放180个下级文件，即180*10=1800字节，所占用的磁盘块为1800/500=4块。由于目录文件按链接结构组织，如果访问的文件目录在第一个磁盘块，则需启动磁盘1次；如果访问的文件在第四个磁盘块，则需启动磁盘4次。（1）若普通文件按顺序结构组织，要读文件O的第15块最少启动磁盘次数=1+1+1+1=4；最多启动磁盘次数=4+4+4+1=13。（最少启动磁盘次数为4的详细过程：由于根目录常驻内存，所以读取B的FCB不需要启动磁盘；根据B的FCB，第1次启动磁盘，读取B的内容的第一块；如果该块中包含了G的FCB，第2次启动磁盘，读取G的内容的第一块；如果该块中包含了K的FCB，第3次启动磁盘，读取K的内容的第一块；如果该块中包含了O的FCB，第4次启动磁盘，直接读取O的内容的第15块。）（2）若普通文件按链接结构组织，要读文件L的第15块最少启动磁盘次数=1+1+1+15=18；最多启动磁盘次数=4+4+4+15=27。（3）若要加快文件目录的检索，可采取什么解决方法？文件控制块分解法：FD=SFD+BFD15 ３３．某文件系统中，外存为硬盘，物理块大小为512字节。有文件A包含589个记录，每个记录占255个字节，每个物理块放2个记录。文件A所在的目录如图所示。文件目录采用树形目录结构。每个目录项占127字节，每个物理块放4个目录项。根目录的第一块常驻内存。下级文件在上级目录文件中的次序在图中为从左至右。（1）若文件为连续文件，则要读A的第487个记录至少要存取几次磁盘？（2）若文件的物理结构采用链式存储方式，链占2字节，那么要将文件A读入内存，至少要存取几次磁盘？（3）为减少读盘次数，一般可采用什么措施？此时可减少几次存取次数？解：由于589/2=294余1，所以文件A最多占295个磁盘块。（1）4+1＝5。若文件为连续文件，由于根目录第一块常驻内存，而usr的FCB不在第一块内，所以读取usr的FCB需要启动1次磁盘；故一共需4次读盘就可找到A的FCB，且通过计算只需一次读盘即可读出第487个记录。所以至少需5次读盘。（最少启动磁盘次数为5的详细过程：由于根目录第一块常驻内存，而usr的FCB不在第一块内，所以读取usr的FCB需要启动1次磁盘；根据usr的FCB，第2次启动磁盘，读取usr的内容的第一块；如果该块中包含了Mike的FCB，第3次启动磁盘，读取Mike的内容的第一块；如果该块中包含了Dir1的FCB，第4次启动磁盘，读取Dir1的内容的第一块；如果该块中包含了A的FCB，第5次启动磁盘，开始读取A的内容的第1块。）（2）4+295＝299。从根目录找到A的FCB需要4次读盘。而由255*2+2=512可知，一个物理块在链式存储结构下可放2个记录及下一个物理块的链指针。文件A共有598个记录，故读取A的所有记录需读盘的次数为589/2+1=295次。所以将A读到内存至少需读盘4+295=299次。（3）为了减少读盘次数可采用索引结点方法。若一个目录项占16字节，则一盘块可存512/16=32个目录项，与本题一盘块仅能放512/127=4个目录项相比，可使访盘次数减少为1/8。这样，就本题来说，查找目录时最少需启动4次磁盘。对查找文件中的记录而言，可用一个或多个盘块来存放该文件的所有盘块号。一个盘块可放512/2-1=255个盘块号，留下一个地址来指示下一个存储盘块号的磁盘块号。A最16 多占295个盘块，则查找文件A中所有记录时需两次才能取得所有盘块号；再启动两次磁盘即可把A中所有记录读入内存。所以，一共需4+2+2=8次访盘，这比原来减少了299-8=291次读盘操作。３４．在UNIX中，有一纯文本文件/usr/wang/source.txt。（1）如果用下面的命令序列$ln/usr/wang/source.txt/usr/zhang/new1.txt（建立硬链接文件）$rm/usr/wang/source.txt(删除原来的文件)$cat/usr/zhang/new1.txt(欲显示纯文本文件内容)问：能正确显示出原纯文本文件内容吗？请叙述其中原理。解：能。３５．假定某文件系统把文件存储到磁盘上时采用链接结构，磁盘分块大小为512字符，逻辑记录的大小为250个字符。现在有一名叫test的文件，共12个逻辑记录，回答下列问题：①怎样才能有效利用磁盘空间？②画出文件test在磁盘上的链接结构（磁盘块号自定）③若用户要求读包含第1338个字符的逻辑记录，写出主要工作步骤。（备注：记录编号从0开始，磁盘块编号也从0开始）解：①采用成组方式（将若干个逻辑记录合并成一组存入一块）的方法可以有效利用磁盘空间。在本题中，一个物理存储块可以存放的逻辑记录个数=[512/250]=2，所以test文件至少要占用12/2=6个物理存储块。②③主要工作步骤：1)计算出包含第1388个字符的逻辑记录在链接文件中的相对位置：因为[1388/250]=6所以包含第1388个字符的逻辑记录是记录5（从0开始编号）因为一个存储块中可放2个逻辑记录所以记录5在相对该文件的第3个物理存储块中（8块，如图）2)读出存放记录5的存储块中的信息：I)查文件目录，找出该链接文件的第1个存储块的地址，启动磁盘读第1块到主存缓冲区，II)取出指向第2个存储块的指针；启动磁盘读第2块到主存缓冲区，取出指向第3个存储块的指针；III)启动磁盘读第3块到主存缓冲区。3)找出记录5：假定主存缓冲区的起始地址为L那么记录5一定在缓冲区的第(L+250)单元开始的区域中。17 ３６．设某系统的磁盘空间共有250个盘块，系统中每字的字长为16位。试计算相应的位示图需要多少字来构造？并给出申请和释放一个盘块的工作流程图。（位示图某位为1表示相应的盘块已用；0表示空闲）解：①求位示图需要多少字来构造：250/16=15……10所以位示图需要用16个字来构造。②申请一个盘块的流程（见图a）释放一个盘块的流程（见图b）设备管理３７．设备通常分为哪两类？它们的特点是什么？解：设备通常分为独占式设备和共享式设备。独占式设备是：一个进程在整个执行期间都占用的设备，通常采用静态分配。共享式设备是：可让若干个进程同时使用的设备，通常采用动态分配。３８．什么是SPOOLing系统？它有哪些作用？解：SPOOLing（SimultaneousPeripheralOperationsOnlining，外围设备同时联机操作）是一种典型的虚拟设备技术，是多任务系统中对慢速独占I/O设备的一种共享方法。为了实现虚拟设备必须在磁盘上划出称为“井”的专用存储空间，用以存放作业的初始信息和作业的执行结果。“井”分成两部分：输入井和输出井。输入井中存放作业的初始信息，输出井中存放作业的执行结果。SPOOLing系统由三部分程序组成：①预输入程序。它的任务是把作业流中的每个作业的初始信息传送到输入井保存以备作业执行时使用。②井管理程序。它分成“井管理读程序”和“井管理写程序”两个功能。当作业请求从输入机上读文件信息时，井管理读程序负责从输入井读出信息供用户使用；当作业请求从打印机上输出结果时，井管理写程序负责把产生的结果保存到输出井中③缓输出程序。缓输出程序负责查看输出井中是否有待输出的结果信息，若有，则启动打印机把结果文件打印输出。18 SPOOLing系统的意义：①用户程序对慢速独占设备的独占时间大大缩短，从而提高了设备的利用率。②用户程序本身的执行时间大大缩短（不必等待慢速设备I/O），变不连续输出为连续输出，可以更快地释放它所占用的其它独占资源，从而提高了系统的吞吐量和所有资源的利用率。３９．请以阻塞read()系统调用为例，描述I/O请求的生命周期（从进程发出I/O请求，到硬件操作，直至I/O完成返回进程）。答：1)进程对已开的文件描述符调用阻塞read()系统调用。2)内核系统调用代码检查参数是否正确。如果请求读取的数据已在缓冲区中，则将该数据返回给进程并完成I/O请求。3)否则，就需要执行物理I/O请求。这是，该进程会从运行队列移到设备的等待队列上，并调度I/O请求。最后I/O子系统对设备驱动程序发出请求。根据操作系统的不同，该请求可能通过子程序调用或内核消息传递。4)调用驱动程序分配内核缓冲空间以接收数据，并调度I/O。最后，设备驱动程序通过写入设备控制寄存器来对设备控制器发送命令。5)设备控制器控制设备硬件以执行数据传输。6)驱动程序可以轮流检查状态和数据，或通过设置DMA将数据传入到内核内存。假定DMA控制器管理传输，当传输完成后会产生中断。7)合适的中断服务程序通过中断向量表收到中断，保存必要的数据，通知内核设备驱动程序，从中断返回。8)设备驱动程序接收信号，确定I/O请求是否完成，确定请求状态，并通知内核I/O子系统请求已完成。9)内核将数据或返回代码传递给请求进程的地址空间，将进程从等待队列移到就绪队列。10)将进程移到运行队列使该进程不再阻塞。当进程调度程序给该进程分配CPU时，该进程就继续在系统调用完成后执行。４０．假设一个活动头磁盘有200个柱面，编号从0-199，当前磁头正在140道上服务，并且刚刚完成了第126道的请求，现有如下访盘请求序列（磁道号）：88，148，90，178，95，152，102，175，130。请问：为完成上述请求，下列算法磁臂移动的顺序和移动总量（总磁道数）是多少。①FCFS②SSTF③SCAN④电梯算法解：①FCFS(先来先服务算法)140－>88－>148－>90－>178－>95－>152－>102－>175－>130总磁道数=566②SSTF(最短寻道时间优先算法)140－>148－>152－>130－>102－>95－>90－>88－>175－>17819 总磁道数=166③SCAN(扫描算法)140－>148－>152－>175－>178－>199－>130－>102－>95－>90－>88总磁道数=170④电梯算法140－>148－>152－>175－>178－>130－>102－>95－>90－>88总磁道数=128４１．旋转型存储设备上信息的优化分布能减少若干个输入输出服务的总时间。现有8个记录A，B，…，G，H，存放在某磁盘上的某个磁道上。假定这个磁道被划分为8块，每块存放一个记录，安排如下表所示。现要顺序处理这些记录，如果磁盘旋转速度为16ms/1周，处理程序每读出一个记录后要用4ms进行处理。试问处理完8个记录的总时间是多少？为了缩短处理时间，应如何安排这些记录实现优化分布，并计算处理的总时间。块号12345678记录号ABCDEFGH解：(1)因为磁盘旋转一周的时间为16ms，所以读取一个记录的时间为16ms/8=2ms处理一个记录的时间为4ms。设读写磁头指向A记录，由2ms+4ms=6ms可知读出并处理完A后，读写磁头已停在D记录的位置。要读B记录需要2ms*6=12ms延迟时间。有7个记录都需要延迟时间。因此处理完8个记录的总时间是：8*(2ms+4ms)+7*(2ms*6)=132ms或：6ms+7*(2ms*6+2ms+4ms)=132ms//2ms*6为等待时间；2ms为读取时间；4ms为处理时间。(2)若进行优化分布，则记录的安排如下表所示：块号12345678记录号ADGBEHCF当处理完A记录后，B记录停在磁头位置，无需延迟时间。因此处理完这8个记录的总时间是：8*(2ms+4ms)=48ms４２．假定某文件系统把文件存储到磁盘上时采用链接结构，磁盘分块大小为512字符，逻辑记录的大小为250个字符。现在有一名叫test的文件，共12个逻辑记录，回答下列问题：①怎样才能有效利用磁盘空间？②画出文件test在磁盘上的链接结构（磁盘块号自定）③若用户要求读包含第1338个字符的逻辑记录，写出主要工作步骤。（备注：记录编号从0开始，磁盘块编号也从0开始）解：①采用成组方式（将若干个逻辑记录合并成一组存入一块）的方法可以有效利用磁盘空间。在本题中，一个物理存储块可以存放的逻辑记录个数=[512/250]=2，所以test文件至少要占用12/2=6个物理存储块。②20 ③主要工作步骤：4)计算出包含第1388个字符的逻辑记录在链接文件中的相对位置：因为[1388/250]=6所以包含第1388个字符的逻辑记录是记录5（从0开始编号）因为一个存储块中可放2个逻辑记录所以记录5在相对该文件的第3个物理存储块中（8块，如图）5)读出存放记录5的存储块中的信息：I)查文件目录，找出该链接文件的第1个存储块的地址，启动磁盘读第1块到主存缓冲区，II)取出指向第2个存储块的指针；启动磁盘读第2块到主存缓冲区，取出指向第3个存储块的指针；III)启动磁盘读第3块到主存缓冲区。6)找出记录5：假定主存缓冲区的起始地址为L那么记录5一定在缓冲区的第(L+250)单元开始的区域中。４３．设某系统的磁盘空间共有250个盘块，系统中每字的字长为16位。试计算相应的位示图需要多少字来构造？并给出申请和释放一个盘块的工作流程图。（位示图某位为1表示相应的盘块已用；0表示空闲）解：③求位示图需要多少字来构造：250/16=15……10所以位示图需要用16个字来构造。④申请一个盘块的流程（见图a）释放一个盘块的流程（见图b）21'