8.1 Explain the difference between internal and external fragmentation.

内部碎片

操作系统可以决定虚存的页面大小。当页面比较大的时候,平均的情况下, 最后一个页面中有一半是空的。 多余的空间就被浪费掉了, 这种浪费称为内部碎片(internal fragmentation) 。假设进程平均大小是 s 个字节, 页面大小是 p 个字节, 每个页表项需要 e 个字节。 那么每个进程需要的页数大约是 s/p, 占用了 se/p 个字节的页表空间。 内部碎片在最后一页浪费的内存是 p/2。 (《现代操作系统》P267)

内部碎片是已经被进程使用的,因此叫 “内部”。

除了内存,磁盘分块也会出现类似的情况,当下一帧填不满当前磁盘块的时候, 则磁盘块剩余的部分就保持空闲状态。 同样称为内部碎片。

外部碎片

在系统运行一段时间后内存被划分为许多块, 一些块包含着段, 一些则成了空闲区, 这种现象称为棋盘形碎片或外部碎片(external fragmentation) 。 (《现代操作系统》P289)

外部碎片是尚未使用,但是因为太小无法被分配的。所以称为 “外部”。

8.3 Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (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 algorithm makes the most efficient use of memory?

100 500 200 300 600

212 KB, 417 KB, 112 KB, and 426 KB

  • first-fit
free list: 100 500 200 300 600 alloc 212
---------->100 212x 288 200 300 600 alloc 417
---------->100 212x 288 200 300 417x 183 alloc 112
---------->100 212x 112x 176 200 300 417x 183 alloc 426
内存不足
  • best-fit
free list: 100 500 200 300 600 alloc 212
---------->100 500 200 212x 88 600 alloc 417
---------->100 417x 83 288 200 212x 88 600 alloc 112
---------->100 417x 83 288 112x 88 212x 88 600 alloc 426 
---------->100 417x 83 288 112x 88 212x 88 426x 174 alloc 426 
分配完毕
  • worst-fit
free list: 100 500 200 300 600 alloc 212
---------->100 500 200 300 212x 388 alloc 417
---------->100 417x 83 200 300 212x 388 alloc 112
---------->100 417x 83 200 300 212x 112 276x 388 alloc 426
内存不足

best-fit 最佳。

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-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. 由于页表存放在内存,所以访存速度和访问页表速度一致,大约需要两次访存, 使用 400ns

b. 由于页表 75% 被缓存,数学期望为 0.25 * 400 + 0.75 * 200 = 250ns

8.10 Why are segmentation and paging sometimes combined into one scheme?

分段一方面可以起到隔离进程的保护作用,另一方面可以将虚拟空间的连续地址映射到物理空间的不同地址。如果只有分段,那么空间利用率是很低的,因为必须连续分配一个段。而分页可以确保在段很大的时候,将一个段分别映射到不同的物理空间,从而提高了利用率。

8.12 Consider the following segment table:

Segment Base Length
0 219 600
1 2300 14
2 90 100
3 1327 580
4 1952 96

What 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. 219 + 430 = 649

b. 2300 + 10 = 2310

c. 非法访问,段错误

d. 1327 + 400 = 1727

e. 非法访问,段错误