8.1 Explain the difference between internal and external fragmentation.

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

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. 非法访问，段错误