内存管理习题讲解.doc

8.1解释内部碎片和外部碎片的区别？
讲解及解答
要搞清楚内部碎片与外部碎片的区别首先要明白分页与分段
为了有效的利用内存，使内存产生更少的碎片，要对内存分页，内存以页为单位来使用，最后一页往往装不满，于是形成了内部碎片。 为了共享要分段，在段的换入换出时形成外部碎片，比如5K的段换出后，有一个4k的段进来放到原来5k的地方，于是形成1k的外部碎片。

内部碎片是某一区域或某一页中，未被占据其位置的作业所使用的区域。直到作业完成，释放页或区域，这个空间才能被系统所利用。

在内存管理中，内部碎片是已经被分配出去的的内存空间大于请求所需的内存空间。（分了，但没占满）
外部碎片是指还没有分配出去，但是由于太小而无法分配给申请空间的新进程的内存空间空闲块。（不够大，所以没分）

固定分区存在内部碎片，可变式分区分配会存在外部碎片；
页式虚拟存储系统存在内部碎片；段式虚拟存储系统，存在外部碎片
8.3按顺序给出5个部分的内存，分别是100KB,500KB,200KB,300KB和600KB，用 first-fit,best-fit和worst-fit算法，能够怎样按顺序分配进程212KB,417KB,112KB,426KB和426KB？哪个算法充分利用了内存空间？
讲解及解答
First-fit:
1. 212K is put in 500K partition （余下288K）
2. 417K is put in 600K partition (余下183K)
3. 112K is put in 288K partition (new partition 288K = 500K − 212K) (余下100K)
4. 426K must wait
Best-fit:
1. 212K is put in 300K partition （剩余88K）
2. 417K is put in 500K partition (剩余83K)
3. 112K is put in 200K partition (剩余88K)
4. 426K is put in 600K partition (剩余174K)
Worst-fit:
1. 212K is put in 600K partition （剩余388K）
2. 417K is put in 500K partition (剩余83K)
3. 112K is put in 388K partition (剩余276K)
4. 426K must wait
Best-fit算法充分利用了内存空间。
8.9考虑一个分页系统在内存中存储着一张页表。
a.如果内存的查询需要200毫秒，那么一个分页内存的查询需要多长时间？
b.如果我们加上相关联的寄存器，75%的页表查询可以在相关联的寄存器中找到，那么有效的查询时间是多少？（假设如果入口存在的话，在相关的寄存器中找到页表入口不花费时间）

讲解及解答
a.分为两步，需要访问两次内存，第一次查页表，第二次查内容。
400毫秒：200毫秒进入页表，200毫秒进入内存中的字。

b.寄存器中的页表查询不花费时间，进入内存中的字需要访问一次内存，即0毫秒+200毫秒，内存中的页表需要访问两次内存，即400毫秒。
有效查询时间=0.75*200毫秒+0.25*400毫秒=250毫秒
3. In a page virtual storage system, each process has 4 memory allocation memory block.When the process begins executing ,data area is empty. If now it calls the pages in the program with this sequence:
5 , 3 , 6 , 4 , 3 , 5 , 1 , 4 , 2 , 5 , 6 , 4 , 2 , 5 , 1
Write down the number of page faults when using the following page-replacement algorithms and draw the Page trend graph.
(1) FIFO page-replacement algorithm
(2) LRU page-replacement algorithm
(3) OPT page-replacement algorithm

(1) 系统采用先进先出淘汰算法，总共缺页10次
5 3 6 4 3 5 1 4 2 5 6 4 2 5 1
5 3 6 4 4 4 1 1 2 5 6 4 4 4 1
5 3 6 6 6 4 4 1 2 5 6 6 6 4
5 3 3 3 6 6 4 1 2 5 5 5 6
5 5 5 3 3 6 4 1 2 2 2 5
f f f f f f f f f f
(2) 系统采用LRU(最少使用)淘汰算法，总共缺页8次
5 3 6 4 3 5 1 4 2 5 6 4 2 5 1
5 3 6 4 3 5 1 4 2 5 6 4 2 5 1
5 3 6 4 3 5 1 4 2 5 6 4 2 5
5 3 6 4 3 5 1 4 2 5 6 4 2
5 5 6 4 3 5 1 4 2 5 6 4
f f f f f f f f
(3) 系统采用OPT淘汰算法，总共缺页7次
5 3 6 4 3 5 1 4 2 5 6 4 2 5 1
5 3 6 4 4 4 4 4 4 4 4 4 4 4 4
5 3 6 6 6 6 6 6 6 6 6 6 6 1
5 3 3 3 1 1 2 2 2 2 2 2 2
5 5 5 5 5 5 5 5 5 5 5 5
f f f f f f f