CSE Roadmap

Core tier · about 5 hours · 7 parts

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.