Suppose you have a operating system that uses pure segmentation on a computer with 1Mb of physical memory. A series of programs are executed on this computer, performing the following series of allocations and deallocations:
allocate Block A: 512kb
allocate Block B: 256kb
allocate Block C: 64kb
free Block B
allocate Block D: 186kb
allocate Block E: 190kb
To fit the blocks in memory, one of two algorithms are possible. The first-fit algorithm scans the holes in-order from the lowest to the highest address, and places the incoming block into the first hole big enough to accommodate it. The best-fit algorithm scans all the holes in memory, and places the incoming block in the smallest hole anywhere that is big enough to accommodate it. The intuition behind the best fit algorithm is to not reduce the size of large holes until absolutely necessary. In either strategy, when a hole is decided, the incoming block is placed at the top of the hole (the lowest address). [This two strategies are in syllabus, so please remember them.]
(a) What is the biggest hole size in physical memory at the end of the above sequence if first-fit is used?
(b) What is the biggest hole size in physical memory at the end of the above sequence if best-fit is used?
(c) What type of memory fragmentation does this computer suffer from: external or internal?
Now suppose that the operating system pages the segments so that each segment is comprised of 4kb pages. The allocations and deallocations work as before.
(d) In total, how much memory is being wasted by external fragmentation?
(e) In total, how much memory is being wasted by internal fragmentation?