Operating System Concept,” 8th edition, Silberschatz, Galvin, Gagne: Wiley, 2008.
1. Textbook page 352, problem 8.11 (memory holes)
Available partitions (holes): 100, 500, 200, 300, 600
(underlined numbers represent the partition being used to fit the request)
First-fit algorithm
212 100, 288, 200, 300, 600
417 100, 288, 200, 300, 183
112 100, 176, 200, 300, 183
426 100, 176, 200, 300, 183 (can’t fit it in)
Best-fit algorithm
212 100, 500, 200, 88, 600
417 100, 83, 200, 88, 600
112 100, 83, 88, 88, 600
426 100, 83, 88, 88, 174
Worst-fit algorithm
212 100, 500, 200, 300, 388
417 100, 83, 200, 300, 388
112 100, 83, 200, 300, 276
426 100, 83, 200, 300, 276 (can’t fit it in)
The best-fit algorithm makes the most efficient use of memory in this instance because it is the only method allowing all new processes inserted. Interestingly though, the left-over partitions in the best-fit algorithm is rather fragmented. For example, it can only insert 2 more 100KB processes. But each of the first-fit algorithm and the worst-fit algorithm can allow 8 more 100KB processes to be inserted. This is a good gain even considering the extra space left because the 426KB process was not inserted.
2. Textbook page 353, problem 8.20 (paging delays)
a) A paged memory reference would take 200+200=400 nanoseconds (200 to access the page table and frame number and 200 to access the desired byte in memory)
b) With chance of 0.75, the access time is 200 nanoseconds. With chance of 1-0.75=0.25, the access time is 400 nanoseconds. Therefore,
Effective Access Time (EAT) = 0.75*200 + 0.25*400 = 250 nanoseconds.
3. Textbook page 353, problem 8.23 (segmentation)
a) 219+430 = 649
b) 2300+10 = 2310
c) OS trap (offset larger than limit)
d) 1327+400 = 1727
e) OS trap (offset larger than limit)
4. Textbook page 353, problem 8.24 (hierarchical paging)
As the memory size of modern computer systems grew larger and larger, page tables could become very large. Allocating contiguous memory for these page tables is inefficient. Therefore, the page table can be divided into small pieces, in a way similar to regular programs being paged.
