湖南大学操作系统作业 (5)

1、操作系统第五次作业第八章8.1 Explain the difference between internal and external fragmentation.简述内部碎片和外部碎片的区别答： 内部碎片存在于块的内部，如内存块大小为512k，而某逻辑内存要求一个200k大小的块，此时操作系统会分配给它一个大小为512k的块（由于块是内存分配的最小单元），所以会造成了312k大小的内存碎片，这部分碎片即使是空的也无法使用，称作内部碎片。减少内部碎片可以通过减小块的大小来解决。 外部碎片是指在连续内存分配的进程装入和移出内存的过程中，空闲的内存空间被分成了较多小片段，这些小片段不连续，所以无

2、法被连续分配，这样会造成即使碎片大小之和大于新进程所需内存，但是也无法给新进程分配的情况，这就是外部碎片。外部碎片可以通过紧缩来解决。8.3 Given five memory partitions of 100 KB, 500 KB, 200 KB,300 KB, and 600KB (in order), how would each of the first-fit,best-fit, and worst-fit algorithms place processes of 212 KB,417 KB, 112 KB, and 426 KB (in order)? Which algori

3、thm makes the most efficient use of memory?给出100kb，500kB，200kB，300kB，600kB大小的内存空间（按顺序），对于首次适应，最佳适应和最差适应算法，要按顺序放置212kB，417kB，112kB和426kB大小的进程会是怎样安排的？哪个算法的内存利用率最高？答：首次适应是每次从头开始找，直到找到第一个比当前要放置的内存大小要大的内存空间时，放置该内存。最佳适应是每次遍历内存空间一次，找大于当前要放置的内存块大小要大的中间的最小者，放置该内存。最差适应则相反，是取大于当前内存大小中的最大者。下面给出三种存储分配方式的最终分配结果：首

4、次适应：对于212kB的进程，选择第一个大于它大小的内存空间，为500kB，并分配给它相应大小的空间，该部分剩余大小500-212=288KB对于417kB的进程，选择第一个大于它的大小的内存空间，为600kB，分配给它相应大小的空间，该部分剩余大小为600-417=183KB对于112kB的进程，选择第一个大于它大小的内存空间，为288kB，分配给它相应大小的空间，该部分剩余大小288-112=176KB对于426kB的进程，找不到比他大的内存空间，无法分配，只能等待其他进程释放空间才能为它分配空间。内存利用率为 （212+417+112）/（100+500+200+300+600） *10

5、0%=43.6%最佳适应：对于212kB的进程，选择大于它大小的内存空间中的最小者，为300kB，并分配给它相应大小的空间，该部分剩余大小300-212=88KB对于417kB的进程，选择大于它大小的内存空间中的最小者，为500kB，分配给它相应大小的空间，该部分剩余大小为500-418=83kB对于112kB的进程，选择大于它大小的内存空间中的最小者，为200kB，分配给它相应大小的空间，该部分剩余大小200-112=88kB对于426kB的进程，选择大于它大小的内存空间中的最小者，为600kB，分配相应大小的空间，该部分生育大小为600-426=174kB内存利用率为 （212+417+1

6、12+426）/（100+500+200+300+600） *100%=68.6%最差适应：对于212kB的进程，选择大于它大小的内存空间中的最大者，为600kB，并分配给它相应大小的空间，该部分剩余大小600-212=388kB对于417kB的进程，选择大于它大小的内存空间中的最大者，为500kB，分配给它相应大小的空间，该部分剩余大小为500-417=83kB对于112kB的进程，选择大于它大小的内存空间中的最大者，为388kB，分配给它相应大小的空间，该部分剩余大小388-112=276kB对于426kB的进程，找不到比他大的内存空间，无法分配，只能等待其他进程释放空间才能为它分配空间。

7、内存利用率为（212+417+112）/（100+500+200+300+600） *100%=43.6%综上所述，本例中最佳适应的内存利用率最高，为68.6%8.9 Consider a paging system with the page table stored in memory.a. If a memory reference takes 200 nanoseconds, how long does a paged memory reference take?b. If we add associative registers, and 75 percent of all page

8、-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.)考虑一个分页系统将页表存在内存中A 如果一个内存访问占用200ns，那么一个页面内存查询占用多少时间？B 如果添加相关寄存器，且所有页表中的75%的访问可以在寄存器中找到，那么

9、有效内存访问时间为多少？（假设寻找页表条目不花时间）答：A 首先访问内存中的页表项，耗时200ns，然后在页表项中查询对应的物理地址（0ns），然后根据对应物理地址去访问内存，耗时200ns，一共耗时为400ns。B （书上翻译associative registers是TLB，感觉不是很恰当，但是只能当作TLB来理解）首先去查找TLB表，如果命中（75%的概率），就直接得到了物理地址，此时可以直接访问物理地址，耗时200ns。如果TLB不命中（25%的概率），此时要按照A中的步骤先访问页表再访问主存，耗时400ns。所以耗时期望E（t）=200*0.75+400*0.25=250ns8.12

10、 Consider the following segment table:Segment Base Length0 219 6001 2300 142 90 1003 1327 5804 1952 96What are the physical addresses for the following logical addresses?a. 0,430 b. 1,10 c. 2,500 d. 3,400 e. 4,112考虑下面的段表，要求对应逻辑地址的物理地址是多少答：A 0，430 先查询段号为0的基地址为219，然后判断是否在段内，由于430<600，所以在段内，对应物理地址为2

11、19+430=649B 1，10，首先查找段号为1的基地址2300，然后判断是否在段内，由于10<14,所以在段内，对应物理地址为2300+10=2310C 2,500,首先查找段号为2的基地址90，然后判断是否在段内，由于500>100，所以不在段内，访问非法D 3，400，首先查找段号为3的基地址1327，然后判断是否在段内，由于400<580,所以在段内，对应物理地址为1327+400=1727E 4,112，首先查找段号为4的基地址1952，然后判断是否在段内，由于112>96，所以不在段内，访问非法第九章9.4 A certain computer provi

12、des its users with a virtual-memory space of 2 32 bytes. The computer has 2 18 bytes of physical memory. The virtual memory is implemented by paging, and the page size is 4096 bytes. A user process generates the virtual address 11123456. Explain how the system establishes the corresponding physical

13、location. Distinguish between software and hardware operations.某电脑提供给虚拟存储一个232b大小的空间，电脑只有218b大小的物理存储，虚拟存储以分页存储，页面大小4096b，一个用户进程产生虚拟地址11123456，解释系统如果建立对应的物理地址，区分硬件和软件的操作。答：11123456化成二进制表示为0001 0001 0001 0010 0011 0100 0101 0110 由于虚存有32位地址，页面大小为212b，所以页偏移就有12位，取虚拟地址的后12位为页偏移，这也是物理地址上的偏移，而虚拟地址剩余的20位则是页

14、号，物理地址剩余的6位是物理页号在查询11123456时，操作系统先根据前20位0001 0001 0001 0010 0011查询页表，查找到对应的物理页号，这是软件操作；然后找到物理页号后计算出对应的物理地址，这也属于软件操作。而在查询页表时，如果发生缺页，此时对页面的调度则是硬件操作。9.13 A page-replacement algorithm should minimize the number of page faults. We can do this minimization by distributing heavily used pages evenly over al

15、l of memory, rather than having them compete for a small number of page frames. We can associate with each page frame a counter of the number of pages that are associated with that frame. Then,to replace a page, we search for the page frame with the smallest counter.页面调度算法应该最小化页面错误，我们可以通过分配常被使用的页面给其

16、他内存来做最小化操作，而不是让他们竞争一小片内存。可以给每个页帧设置一个计数器来记录和他相关的页数，然后，为了调换页面，在所有页帧中选择计数值最小的那个。A Define a page-replacement algorithm using this basic idea. Specifically address the problems of (1) what the initial value of the counters is, (2) when counters are increased, (3) when counters are decreased, and (4) how

17、the page to be replaced is selected.设计一个页面调换算法使用这个基础思想；特别要注意的问题是：1 计数器的初值，2 何时计数器增加，3 何时计数器减少，4 页面应该怎么被替换和选择b. How many page faults occur for your algorithm for the following reference string, for four page frames?1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2.在你的算法用4个页帧里调度以下顺序的页面会

18、出多少错？c. What is the minimum number of page faults for an optimal page-replacement strategy for the reference string in part b with four page frames?最优置换算法中用4个页帧调度上述顺序会出现多少个页面错误？答：A 考虑这样一个页面调度算法，初始化各页帧counter值均为0，每个页帧每一次调入一个新的页时，counter+1，这个值在调入的页面不会再次出现时还原，即counter-1，每次有新的页面需要调入页帧时，先对所有页帧进行判断，选择当前co

19、unter值最小的页帧作为置换页，如果有多个相同counter值的页帧，则选取最先进入页帧的页面作为置换页。B 1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2.以A中的调度算法来调度这些页面，调度顺序如下：（表中M代表Miss，即出现页面错误，H代表Hit，即页面命中）初始状态下，页帧全空，此时对于按顺序的访问1、2、3、4均缺页，需要调入页面：页帧11(M)页帧22(M)页帧33(M)页帧44(M)在调入页面5的时刻，由于页帧1-4的counter值全为1，故选择最先进入的页帧1进行置换，随后来的页面3和4的访

20、问，由于仍存在页帧中，故均命中：页帧11(M)5(M)页帧22(M)页帧33(M)3(H)页帧44(M)4(H)由于完成了3的访问后，页面3不会再次出现，故此时页帧3的counter值已经为0，是当前页帧中的最小值，故此时对页面1的调度会优先选择页帧3进行置换。由于完成了页面1的访问后，页面1不会再次出现，所以页帧1的counter值此时为1，页帧3的counter值此时为0。页帧11(M)5(M)页帧22(M)页帧33(M)3(H)1(M)页帧44(M)4(H)同理，按此顺序进行上述的调度，下表给出4个页帧所对应的调度顺序。页帧11(M)5(M)5(H)5(H)2(M)页帧22(M)8(M)

21、8(H)8(H)页帧33(M)3(H)1(M)6(M)7(M)7(H)7(H)4(M)4(H)页帧44(M)4(H)9(M)9(H)统计上表可以得到总页面错误次数为：12次C 基于最优置换的调度页面最优置换算法会调度所有页帧，置换最长时间不会使用的页。使用最优置换算法得到的示意图如下：页帧11(M)1(H)6(M)8(M)8(H)8(H)4(M)4(H)2(M)页帧22(M)5(M)5(H)5(H)页帧33(M)3(H)7(M)7(H)7(H)页帧44(M)4(H)9(M)9(H)共出现11次页面错误。9.14Consider a demand-paging system with a pag

22、ing disk that has an average access and transfer time of 20 milliseconds. Addresses are translated through a page table inmain memory, with an access time of 1 microsecond per memory access. Thus, each memory reference through the page table takes two accesses. To improve this time, we have added an

23、 associative memory that reduces access time to one memory reference, if the page-table entry is in the associative memory.Assume that 80 percent of the accesses are in the associative memory and that, of the remaining, 10 percent (or 2 percent of the total) cause page faults. What is the effective memory access time?假设一个请求调页系统具有一个平均访问和传输时间为 20ms 的分页磁盘。 地址转换是通过在主存中的页表来运行的，每次内存访问时间为 1µs。 返样，每个通过页表进行的内存引用都要访问内存两次。为了提高性能，加入一个相关内存，当页表项在相关内存中时，可以减少内存引用的访问次数。假设 80%的访问发生在相关内存中，而且剩下中的 10%（总量的 2%）会导致页错误。内存的有效访问时间是多少？答：80%可以在相关内存中访问页表；2%出现页错误，需要触发请求调页系统，待调页请求调度完成后才能重新