第六章作业(OS)答案

第六章作业1．存放在某个磁盘上的文件系统，采用混合索引分配方式，其FCB中共有13个地址项，第0~9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大小为512字节，若盘块号需要用3个字节来描述，而每个盘块最多存放170个盘块地址：(1)该文件系统允许文件的最大长度是多少？(2)将文件的字节偏移量5000、15000、150000转换为物理块号和块内偏移量。答：（1）该文件系统中一个文件的最大长度可达：10+170+170*170+170*170*170=4942080块=4942080*512字节=2471040KB（2）5000/512得到商为9，余数为392，即字节偏移量5000对应的逻辑块号为9，块内偏移量为392。由于910，故可直接从该文件的FCB的第9个地址项处得到物理盘块号，块内偏移量为392。15000/512得到商为29，余数为152，即字节偏移量15000对应的逻辑块号为29，块内偏移量为152。由于10≤2910+170，而29-10=19，故可从FCB的第10个地址项，即一次间址项中得到一次间址的地址；并从一次间址块的第19项（即该块的第57~59这3个字节）中获得对应的物理盘块号，块内偏移量为152。150000/512得到商为292，余数为496，即字节偏移量150000对应的逻辑块号为292，块内偏移量为496。由于10+170≤29210+170+170*170,而292-(10+170)=112，112/170得到商为0，余数为112，故可从FCB的第11个地址项，即二次间址项中得到二次间址块的地址，并从二次间址块的第0项中获得一个一次间址块的地址，再从该一次间址块的第112项中获得对应的物理盘块号，块内偏移量为496。（3）由于文件的FCB已在内存，为了访问文件中某个位置的内容，最少需要1次访问磁盘（即可通过直接地址直接读文件盘块），最多需要4次访问磁盘（第一次是读三次间址块，第二次是读二次间址块，第三次是读一次间址块，第四次是读文件盘块）。2.在某个文件系统中，每个盘块为512个字节，文件控制块占64个字节，其中文件名占8个字节。如果索引结点编号占2个字节，对于一个存放在磁盘上的256个目录项的目录，试比较引入索引结点前喉，为找到其中一个文件的FCB，平均启动磁盘的次数？答：在引入索引结点前，每个目录项中存放的是对应文件的FCB，故256个目录项的目录总共需要占用256*64/512=32个盘块。因此，在该项目录中检索到一个文件，平均启动磁盘的次数为（1+32）/2=16.5。在引入索引结点之后，每个目录项中只需存放文件名和索引结点的编号，因此256个目录项的目录总共需要占用256*(8+2)/512=5个盘块。因此，找到匹配的目录项平均需要启动(1+5)/2，即3次磁盘；而得到索引结点编号后，还需启动磁盘将对应文件的索引结点读入内存，故平均需要启动磁盘4次。可见，引入索引结点后，可大大减少启动磁盘的次数，从而有效地提高检索文件的速度。第五章作业1．有一移动臂磁盘，共100个磁道，每个磁道分8个扇区，磁盘转速为500r/s（转/秒），磁头每移动一个磁道需要10ms,有一用户请求访问第25磁道第3扇区，并立即被系统响应，假设磁头当时处于15道上，磁头到达第25道时正处于1扇区的开始位置，试计算该用户至少需要等待多长时间？2.若有磁盘共有200个柱面，其编号为０～199，假定磁头刚完成56号磁道的访问，磁头正在98号磁道上，并向磁道号增加的方向移动，现有一个请求队列在等待访问磁盘，访问的磁道号分别为190，97，90，45，150，32，162，108，112，80。请写出分别采用FCFS、SSTF、SCAN和CSCAN算法进行调度磁盘时的请求次序，并计算出它们的平均寻道长度。3．假定磁盘转速为20ms/圈，磁盘格式化时每个磁道被划分成10个扇区，今有10个逻辑记录（每个记录的大小刚好与扇区大小相等）存放在同一磁道上，处理程序每次从磁盘读出一个记录后要花费4ms进行处理，现要求顺序处理这10个记录，若磁头现在正处于首个逻辑记录的始点位置。请问：（1）按逆时针方向安排10个逻辑记录（磁盘顺时针方向转），处理程序处理完这10个记录所花费的时间是多少？（2）按最优化分布重新安排这10个逻辑记录，写出记录的安排，并计算出所需要处理的时间。1.某系统采用页式存储管理策略，拥有逻辑空间32页，每页2K，拥有物理空间1M。（1）请写出逻辑地址的格式。（2）若不考虑访问权限等，进程的页表有多少项？每项至少有多少位？（3）如果物理空间减少一半，页表结构应相应作怎样的改变？答：（1）该系统拥有逻辑空间32页，故逻辑地址中页号必须用5位来描述；而每页为2K，因此，页内地址必须用11位来描述，这样可得到它的逻辑地址格式如下：1511100（2）每个进程最多有32个页面，因此，进程的页表项最多为32项；若不考虑访问权限等，则页表项中只需给出页所对应的物理块号，1M的物理空间可分成29个内存块，故每个页表项至少有9位。（3）如果物理空间减少一半，则页表中页表项数仍不变，但每项的长度可减少1位。2.对一个将页表存放在内存中的分页系统：（1）如果访问内存需要0.2微秒，有效访问时间为多少？（2）如果加一快表，且假定在快表中找到页表项的几率高达90％，则有效访问时间是多少？（假定查找快表需花的时间是0）答：（1）有效访问时间为；2*0.2=0.4微秒(2)有效访问时间为：0.9*0.2+(1-0.9)*2*0.2=0.22微秒3．某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、1、2、3页分别被分配到主存的2、4、6、7块中。(1)将十进制的逻辑地址1023、2500、3500、4500转换为物理地址。(2)以十进制的逻辑地址1023为例画出地址变换过程图。答：（1）对上述逻辑地址，可先计算出它们的页号和页内地址（逻辑地址除以页页号页内地址面大小，得到的商为页号，余数为页内地址），然后通过页表转换成对应的物理地址。①逻辑地址1023:1023/1K，得到页号为0，页内地址为1023，查页表找到对应的物理块号为2，故物理地址为2*1K+1023=3071②逻辑地址2500:2500/1K，得到页号为2，页内地址为452，查页表找到对应的物理块号为6，故物理地址为6*1K+452=6596③逻辑地址3500:3500/1K，得到页号为3，页内地址为428，查页表找到对应的物理块号为7，故物理地址为7*1K+428=7596④逻辑地址为4500:4500/1K，得到页号为4，页内地址为404，因页号不小于页表长度故产生越界中断。4．某操作系统采用可变分区分配存储管理方法，用户区为512K且始址为0，用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的方案，且初始时用户区的512K空间空闲，对下述申请序列：申请300K，申请100K，释放300K，申请150K，申请30K，申请40K，申请60K，释放30K回答下列问题：(1)采用首次适应算法，空闲分区中有哪些空块？(2)采用最佳适应算法，空闲分区中有哪些空块？(3)如再申请100K，针对(1)和(2)各有什么结果？5．在一分页存储管理系统中，逻辑地址长度为16位，页面大小为4096字节，现有一逻辑地址为2F6AH，且第0、1、2页依次存放在物理块5、10、11中，问相应的物理地址为多少？答：由题目所给条件可知，该系统的逻辑地址为16位，其中高4位为页号。页面大小4096字节，共要占有二进制12位，低12位为页内地址；另外，由于题目中给出的逻辑地址是十六进制数，故可先将其转换成二进制数以直接获得页号和页内地址，再完成地址的转换2F6AH为0010111101101010，由此看出，逻辑地址（2F6A）16的页号为（0010）2，即2，故页号合法；从页表中找到对应的内存块号为11，即（1011）2；与页内地址（111101101010）2拼接形成物理地址（1011111101101010）2，即（BF6A）16。6.在一个段式存储管理系统中，其段表如图1段号内存起始地址段长02105001235020210090313505904193895图1试求图2逻辑地址对应的物理地址。段号段内位移0430110250034004112532图2答：（1）段号0小于段表长5，故段号合法；由段表的第0项可获得段的内存始址为210，段长为500;由于段内地址430，小于段长500，故段内地址也是合法的，因此可得出对应的物理地址为210+430=640。（2）段号1小于段表长5，故段号合法；由段表的第1项可获得段的内存始址为2350，段长为20;由于段内地址10，小于段长20，故段内地址也是合法的，因此可得出对应的物理地址为2350+10=2360。（3）段号2小于段表长5，故段号合法；由段表的第2项可获得段的内存始址为100，段长为90;由于段内地址500，超过段长90，故产生越界中断。（5）段号5等于段表长，故段号不合法，产生越界中断。7．在一采取局部置换策略的请求分页系统中，分配给某个作业的内存块数是4，其中存放的四个页面的情况如表所示。物理块虚页号装入时间最后一次访问时间访问位修改位0260157011116016110202615800332016311上面的所有数字均为十进制，所有时间都是从进程开始运行时从0开始计数的时钟数。请问，如果系统采用下列置换算法，将选择哪一页进行换出？（1）FIFO算法；（2）LRU算法；（3）改进的Clock算法。答：（1）FIFO算法选择的换出页是物理块3中的第3页。（2）LRU算法选择的换出页是物理块0中的第2页。（3）改进的Clock算法选择的换出页是物理块2中的第0页。8.在一个请求分页系统中，假如一个作业的页面走向为：4，3，2，1，4，3，5，4，3，2，1，5，目前它还没有任何页装入内存，当分配给该作业的物理块数目M分别为3和4时，请分别计算采用OPT、LRU和FIFO页面淘汰算法时访问过程中所发生的缺页数和缺页率，并比较所得的结果。M=3时，OPT算法页面走向432143543215以后最长时间不用√√√√√√√2111544/33/21/23334335444434435559.某页式虚拟存储管理系统的物理空间共3k，页面大小为1k，一进程按下列地址顺序引用内存单元：3635，3632，1140，3584，2892，3640，0040，2148，1700，2145，3290，0000，1102，1100。如果上述数字均为十进制数，而内存中尚未装入任何页。给出使用LRU算法时的缺页率，并与FIFO时的情况进行比较。答：（1）根据题意，分配给作业的内存块数为3，而页面的引用次序为3、3、1、3、2、3、0、2、1、2、3、0、1、1。因此，可以计算出，采用LRU算法时，缺页次数为8，采用FIFO算法时，缺页次数为6。LRU算法用最近的过去来作为预测最近的将来的依据，一般认为其有较好的性能，但实现时，要记录最近在内存的每个页面的使用情况，比FIFO困难，其开销也大。有时，因页面的过去和未来的走向之间并无必然的联系，如上面，LRU算法的性能就没想象中那么好。第三章作业1.假设有四个作业,它们提交、运行时间如下表所示。若采用先来先服务、短作业优先、响应比高者优先调度算法，试问平均周转时间和带权周转时间为多少？（时间单位：小时，以十进制进行计算。）2.假如有四道作业，它们的提交时间及运行时间如下表所示。作业号到达时间（时）运行时间（时）开始时间（时）完成时间（时）周转时间T（时）带权周转时间（时）18:002.028:500.539:000.149:500.2假设系统采用单道程序设计技术，请给出系统在分别采用FCFS（先来先服务）、SJT（短作业优先）和HRN（响应比高者优先）作业调度算法时它们的调度作业顺序、作业的平均周转