Part 7 of 7 · 3 min read
Exercises
Easy
Easy 1: First fit by hand (20 minutes)
Holes: 8, 14, 6, 20. Requests: 5, 12, 9. Place them by first fit and list the holes that remain.
Done when: a table with each request, the hole chosen and the holes left.
Hint
After each placement, update the hole size before the next request.
Easy 2: Name the waste (20 minutes)
For each case, say whether the waste is internal or external: (a) 3 free blocks of 100 bytes cannot serve a request of 250 bytes, (b) a request of 5,000 bytes takes two pages of 4,096 bytes.
Done when: (a) external, (b) internal, with the amounts.
Hint
Internal waste is inside a block, and external waste is between blocks.
Easy 3: Expected holes (20 minutes)
A system has 800 allocated blocks. How many holes does the 50-percent rule predict?
Done when: about 400.
Hint
Half of 800.
Medium
Medium 1: Compare the three rules (45 minutes)
With the holes 10, 4, 20, 7, 15, 5 and the requests 12, 10, 9, 11, place the requests by first fit, best fit and worst fit. Say which rules grant all four.
Done when: three traces and a list of which requests fail under each rule.
Hint
A request is granted only if some single hole is at least as large.
Medium 2: Internal waste (45 minutes)
Write a program that takes 100,000 random request sizes between 1 and 100,000 bytes, rounds each up to a multiple of a unit, and reports the average waste. Run it for units of 512, 4,096 and 65,536 bytes.
Done when: three averages close to half the unit each.
Hint
The waste of one request is (unit - size % unit) % unit.
Medium 3: Time a compaction (45 minutes)
Write a program that copies 512 MiB with memcpy three times and reports the speed. Say how long it would take to compact 2 GiB.
Done when: a measured speed, with the estimate and a note on the first, slower copy.
Hint
Do not count the first copy, since it includes page faults.
Hard
Hard 1: Write the allocator (90 minutes)
Write a simulation of a memory of 10,000 units with first fit, best fit and worst fit. Use random requests between 10 and 100 units, and keep the load near 85%. Run 100,000 steps and report the failure rate of each rule.
Done when: a table of three failure rates and a sentence on which rule was best.
Hint
Keep the holes in a list sorted by start address, and merge neighbours when a block is freed.
Hard 2: Check the 50-percent rule (60 minutes)
In your simulation, measure the ratio of holes to blocks after a long run. Run first fit with three different size ranges.
Done when: three ratios and a statement of whether they are close to 0.5.
Hint
Count holes and blocks at fixed intervals, in the second half of the run.
Hard 3: Add compaction (90 minutes)
Add a compaction step that runs when a request fails, and then retries the request. Count the compactions, and the total number of units moved.
Done when: counts of failures avoided and units moved, and a conclusion on whether compaction was worth it.
Hint
Moving a block costs its size in copied units.