25-Comp-A5 Operating Systems · December 2013

Question 4 of 7: Fragmentation and Memory Allocation Policies

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Question 4: Fragmentation and Memory Allocation Policies (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

(a) Internal fragmentation is wasted space INSIDE an allocated block — the OS hands a process a block at least as large as it asked for (e.g. rounded up to the next fixed-size unit), and the unused remainder inside that block is wasted but unusable by anyone else. External fragmentation is wasted space OUTSIDE any allocated block — many small, scattered free holes exist, and their sum may be large, but no single hole is big enough to satisfy a new request, so the space is wasted even though it is technically free. A single technique that controls both is paging with a well-chosen page size: because every block of memory (page frame) is exactly one fixed size, there is never a "leftover odd-sized hole" between allocations — external fragmentation is eliminated completely. Internal fragmentation is not eliminated by paging but IS controlled by the same technique through the choice of page size: a process's last partial page wastes, on average, half a page, so choosing a smaller page size directly bounds the internal-fragmentation loss (at the cost of a larger page table and more page-fault/TLB overhead) — a system administrator therefore controls both fragmentation types through the single parameter of page size, trading one concern against the other rather than needing two separate techniques.

Given. Free list (in list order): 202K, 143K, 305K, 380K, 170K, 191K, 225K, 250K. Jobs arrive strictly in sequence and are allocated one at a time before the next arrives: Job 1 (222K), Job 2 (205K), Job 3 (303K), Job 4 (190K). Allocating from a hole leaves the (possibly nonzero) remainder in the free list at the same position (standard convention, flagged below).

Find. Which hole is allocated to each job under (i) best fit and (ii) first fit, in arrival order.

Approach. First fit scans the list in the given order and takes the FIRST hole large enough; best fit scans the ENTIRE list and takes the SMALLEST hole that is still large enough (minimizing the leftover fragment). Re-scan the (updated) list before each new job.

1. (i) Best fit. Job 1 (222K): holes $\ge222$K are $\{305,380,225,250\}$; the smallest is $225$K $\to$ allocate from the 225K hole, leaving $225-222=3$K. Job 2 (205K): remaining eligible holes $\{305,380,250\}$ ($225$K is now only 3K, no longer eligible); smallest is $250$K $\to$ allocate, leaving $250-205=45$K. Job 3 (303K): eligible $\{305,380\}$; smallest is $305$K $\to$ allocate, leaving $305-303=2$K. Job 4 (190K): holes now $\{202,143,2,380,170,191,3,45\}$; eligible ($\ge190$K) $\{202,380,191\}$; smallest is $191$K $\to$ allocate, leaving $191-190=1$K. $$\boxed{\text{Best fit: Job1}\to225\text{K},\ \text{Job2}\to250\text{K},\ \text{Job3}\to305\text{K},\ \text{Job4}\to191\text{K} \;-\; \text{ALL FOUR jobs placed}}$$
2. (ii) First fit. Job 1 (222K): scanning in list order, $202$K and $143$K are too small; $305$K is the first hole $\ge222$K $\to$ allocate, leaving $83$K in place. Job 2 (205K): list is now $[202,143,83,380,170,191,225,250]$; scanning, $202,143,83$ are too small, $380$K is the first fit $\to$ allocate, leaving $175$K. Job 3 (303K): list is now $[202,143,83,175,170,191,225,250]$; the LARGEST remaining hole is only $250$K $<303$K, so NO hole satisfies the request — Job 3 must wait (blocked) even though the total free memory ($1866-222-205=1439$K at this point) vastly exceeds 303K, because it is fragmented across holes none of which is individually big enough. Job 4 (190K): scanning the same list, $202$K is the first hole $\ge190$K $\to$ allocate, leaving $12$K. $$\boxed{\text{First fit: Job1}\to305\text{K},\ \text{Job2}\to380\text{K},\ \text{Job3}\to\text{BLOCKED (no fit)},\ \text{Job4}\to202\text{K}}$$