Addresses and contiguous allocation: fits and fragmentation

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. How many units make deadlock impossible for needs k₁ … kₙ? from Lesson 4.1.3
2. Name the four parts of a process in memory. from Lesson 1.1.1
3. How many address bits are needed for 64 KB of byte-addressable memory? from Lesson 0.1.1

1 · The Hook

A car park has spaces of different lengths left between parked cars. A new car arrives: do you take the first space it fits in, the tightest one, or the biggest one? After a while, the car park is full of small useless gaps even though, added up, there is room for a bus. That is memory allocation, and those useless gaps are fragmentation. GATE asks you to place a list of requests by first, best and worst fit and to spot which one fails.

3 · Core Concept

Predict First — the answer

The 350 KB hole (150 is too small, 350 is the first that fits).

In plain words

A program uses addresses starting from 0 as if it had memory to itself (logical addresses). The hardware adds where the program really sits in RAM to get the physical address. In the simplest scheme each process gets one unbroken block of RAM, and the OS must choose which free gap ("hole") to put it in.

1. Logical vs physical addresses

• Logical (virtual) address: generated by the CPU while running the program.
• Physical address: the actual location in RAM.
• The MMU (memory-management unit) hardware translates every logical address on the fly.

2. Base (relocation) and limit registers

The OS loads two registers when it dispatches a process:

• limit = size of the process's block; base = where the block starts.
• For each logical address L: if L < limit, physical = base + L; otherwise trap (addressing error), so a process can't touch others' memory.

Example: base 3000, limit 1200. L = 500 → 3500. L = 1300 → trap.

3. Contiguous allocation

• Fixed partitions: memory is cut into blocks in advance; a process gets a whole block. Unused space inside a block is internal fragmentation.
• Variable partitions: each process gets exactly what it asks for; free memory becomes scattered holes. Enough total free space that is not in one piece is external fragmentation.
• Compaction: slide processes together to merge holes (costly; needs relocation at run time).
• With first fit, statistics show that for N allocated blocks about 0.5N more are lost to fragmentation (the 50% rule): up to one third of memory may be unusable.

4. Placement strategies (variable partitions)

5. Worked example

Holes (in memory order): 150, 350, 200, 500, 100 KB. Requests, in order: 180, 90, 320, 240 KB.

Here first fit (and next fit) fail, while best and worst fit place everything. No strategy is always best.

4 · Visual

Base and limit check

 CPU --L--> [ L < limit ? ] --yes--> [ + base ] --> physical address --> RAM
                  |
                  no
                  v
           trap: addressing error

 base 3000, limit 1200:   L = 500  -> 3500      L = 1300 -> trap

5 · Worked Examples

Example 1 Easy

Base 4000, limit 600. Translate logical addresses 250 and 600.

Solution

250 < 600 → 4250. 600 is not < 600 → trap.

Example 2 Medium

Memory has fixed partitions of 200 KB. Processes of 120, 180 and 50 KB are loaded, one per partition. Total internal fragmentation?

Solution

(200 − 120) + (200 − 180) + (200 − 50) = 80 + 20 + 150 = 250 KB.

Example 3 GATE

In the worked example, with best fit, how much free memory is left in the 500 KB hole at the end?

Solution

Only the last request (240) uses it: 260 KB.

6 · GATE Traps

• The limit check is L < limit (logical address), done before adding the base.
• Internal fragmentation: waste inside an allocated block. External: free memory split into pieces.
• First fit is not "smallest" and best fit is not "first"; read which hole each picks.
• Next fit continues from the last allocation, not from the start.

7 · Memory Hook

"First = earliest, Best = tightest, Worst = biggest. Inside waste = internal, gaps between = external."

8 · Connect the Dots

External fragmentation comes from needing one unbroken block per process. The next lesson removes that need: paging cuts both the program and memory into equal small pieces, so any free piece can be used.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 1 mark(s) — Relocation

Base register 2500, limit register 800. A process issues logical address 640. Physical address?

Numerical answer: ________

Q2 · MCQ · 1 mark(s) — Limit

Base 2500, limit 800. Logical address 800 is issued. What happens?

1. (A) The limit is increased
2. (B) Physical address 800
3. (C) Physical address 3300
4. (D) Trap: addressing error

Q3 · NAT · 2 mark(s) — Best fit

Holes 150, 350, 200, 500, 100 KB; requests 180, 90, 320, 240 KB placed by best fit. Total size of the leftover pieces of the holes that were used?

Numerical answer: ________

Q4 · MCQ · 2 mark(s) — First fit

Same holes and requests with first fit. Which request cannot be placed?

1. (A) 90
2. (B) 240
3. (C) 320
4. (D) 180

Q5 · MCQ · 1 mark(s) — Fragmentation

Fixed-size partitions mainly cause:

1. (A) no fragmentation
2. (B) external fragmentation
3. (C) thrashing
4. (D) internal fragmentation

10 · Rule Card

• Logical address from the CPU; MMU makes the physical address.
• Base/limit: if L < limit then physical = base + L, else trap.
• Fixed partitions → internal fragmentation; variable → external; compaction merges holes.
• First fit (first big enough), next fit (continue from last), best fit (smallest big enough), worst fit (largest).
• 50% rule: N blocks allocated → about 0.5N lost (one third).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

logical addressphysical addressMMUbase (relocation) registerlimit registercontiguous allocationfixed partitionsvariable partitionsholesinternal fragmentationexternal fragmentationcompactionfirst fitnext fitbest fitworst fit50% rule