Operating Systems

Memory Management: Fragmentation, Swapping, Buddy System, and Paging

Published: 2026-08-15

Level: undergraduate

Audience: Undergraduate students in Operating Systems

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Memory management fundamentals — covered in Lecture 1 (bringing programs into memory; tracking, allocating, and deallocating)
Processes and process states — covered in Lecture 3
Swapping and the medium-term scheduler — covered in Lecture 3
Threads and multithreading — covered in Lecture 4
FCFS scheduling and the convoy effect — covered in Lecture 5
Priority scheduling — covered in Lecture 5 (drives which process is swapped out)
Round robin scheduling — covered in Lecture 6 (used in the critical section demo)

This lecture does two things. It walks through the CPU OS Simulator (a downloadable teaching tool) with two full demos — one on FCFS scheduling, one on a critical section gone wrong — and then returns to theory, completing the memory management unit: fixed and dynamic partitioning, the two kinds of fragmentation, compaction, swapping, the buddy system, and the first half of paging, including two fully worked problems on address bits and page-number/offset splitting.

The thread that ties the two halves together is memory: the simulator demos show what happens when processes and threads share a machine without protection, and the theory half explains the schemes the operating system uses to place, protect, move, and swap processes in main memory. Each scheme exists to answer one question — where do I put this process, and what do I do when there is no room? — and each scheme pays a different price for its answer, in wasted space, in processor time, or in hardware complexity. By the end of the lecture you should be able to say, for any given allocation technique, what it wastes, what it fixes, and when it breaks.

12.1 The CPU OS Simulator: From Source Code to Running Processes

Real-world: the CPU OS Simulator is a downloadable tool that shows how an operating system actually schedules and runs processes. Most of the class had already worked with it in a previous semester, so the session treated it as a refresher plus a guided demo.

Why watch a simulator at all? A real operating system hides its work behind hardware and drivers; you can never slow it down, pause it, or open up its ready queue to peek inside. The simulator gives you exactly that superpower: you can freeze a running system mid-execution, inspect every queue and register, and watch FCFS, SJF, and round robin scheduling happen tick by tick. Everything you will do in the simulator-based assignment is this same loop: set up a run, watch it, take a snapshot, and explain what the snapshot shows.

12.1.1 Compiling and Loading a Program

The workflow starts in the compiler view. You click the compiler button, paste your source code into the editor (you can copy it from a notepad file, a Word document, or anywhere else; there is a button to clear the editor, and you can also load from a file on your drive), and click compile. If everything is fine you get a success message; if there is an error it is reported right there and you go fix the source. After a successful compile you can inspect the equivalent assembly-language instructions for your program on the side, and with another click you can see the equivalent binary code — the compiled or object code. Neither of those is the point of this course, though; the point is what the operating system simulator does with the program.

Q: Have any of you studied compiler design, where the different phases of a compiler (and things like assemblers from system programming) are covered? A: No one in the class had taken it yet. The discussion notes that compiler design is expected to come as an elective course in the upcoming semesters, part of an advanced operating systems row, offered only if enough students select it. For now it does not matter: we only need to compile so that we can get to the OS simulator view. The compiler, the assembler, and the linker are just the pipeline that turns source code into something the simulator can load — they are tools here, not the subject.

Next you load the program into memory. Before loading you can change the starting address — for instance, start at address 100 instead of the default — and then click "load in memory". The instructions now sit in memory, and the registers (the program counter, the stack pointer, and the other registers) are shown initially with no values, updating later as execution proceeds. You can even load several programs at once and pick any one of them to run. The program name appears in the OS simulator's list only if the whole chain — compile and load — succeeded.

12.1.2 Creating Processes and Choosing a Scheduling Policy

In the OS simulator view you click "create process" and a process is created for the loaded program. There is a priority field you can change (priority scheduling was covered earlier), and the process lifetime is displayed — although in this version it is not updating, so you need not worry about reading burst times off the simulator; the questions give you the burst times explicitly.

The tool offers several scheduling policies. By default it is FCFS; you can switch to SJF or round robin depending on what the question asks. Round robin defaults to a time slice of 5 ticks (0.2 seconds), and you can change the quantum if you want.

Clicking "create process" again creates another process — how many times you click, that many processes are created — and all of them sit in the ready queue. The arrival delay field controls when a process shows up: with a delay of, say, 3 seconds (the default is 1), the next created process is not in the ready queue at all; it appears only after the delay elapses, and under FCFS it joins the ready queue at the end and runs last, after every process that arrived earlier. The assumption in the demo was that all the other processes arrived at the same time.

Scope: The arrival delay models a process that arrives late — like a student who joins a queue after everyone else is already waiting. Under FCFS the late arrival is served last, because FCFS serves strictly in arrival order. Under round robin the same late arrival would join the tail of the circular queue when it appears, not when the demo started. The scheduling policy decides what "arriving late" means for a process, so always read the question's policy before you reason about order.

12.1.3 The FCFS Demo, Step by Step

The demo ran five processes. The CPU speed control can be set to fast (maximum) or slow — at slow speed every process takes a long time, so the demo ran at maximum. In between, you can suspend execution to inspect the various views without the display racing past: the ready queue view shows how many processes are queued (at the moment of suspension three processes had completed, one was running, and the delayed fifth had just joined the ready queue after its arrival delay); the process list view shows which processes are running and which are ready; the process status view shows per-process information such as waiting time; and the resources view lists all the resources — something that will be genuinely useful later when you study deadlock. After inspecting, you resume ("go to the OS control, receive") and the remaining processes complete.

The FCFS demo, traced. Five processes were compiled and loaded, then created one after another; the fifth carried an arrival delay, so it was absent from the ready queue when the run began.

Run at maximum speed — at slow speed every process takes a long time, so the demo ran with the CPU speed control set to fast.
Suspend the run to freeze the system at a chosen instant. At the moment of suspension the views showed: three processes completed, one running, and the delayed fifth process just joining the ready queue after its arrival delay elapsed.
Read the views: the ready queue view counts the processes still waiting; the process list view separates running from ready; the process status view shows per-process details such as waiting time; the resources view lists every resource in the system.
Resume ("go to the OS control, receive") and the remaining processes complete.

Sense-check: the delayed fifth joined the tail of the FCFS queue and was still waiting while three processes had already finished — exactly what FCFS predicts for a late arrival. The snapshot is your evidence: it shows the delayed process in the ready queue and the other four ahead of it.

Exam note: questions based on this tool work the same way — compile, load, create processes, run under the stated policy, take snapshots of the relevant views, and explain what you observe. Reference PDF/Word documents will be provided for working with the tool, and the questions are drawn from those references with the code changed; each task needs its own snapshot, with a one-line explanation underneath when the snapshot is not self-explanatory.

12.2 The Critical Section Demo: Two Threads, One Shared Variable

The second demo shows what happens when two threads share a variable with no synchronization — a classic race condition, live on screen.

12.2.1 The Program

The source code contains a critical region: a global integer variable (call it G) that two threads both use. The main function starts thread one, then starts thread two, and before exiting it waits for both threads to complete. Each thread declares its own integer variable, updates G, prints the value, and exits — but the number of iterations each thread performs is different, so the value each thread computes for the same G is different. The critical section is exactly the code where G gets updated. The program has no synchronization at all, so we have no information about whether the value of G stays consistent; we cannot even know which thread updates it first.

What a critical section is. A critical section is the piece of code in which a process or thread accesses shared data — here, the single statement region where G is read, changed, and written back. The danger is that updating G is not one indivisible act: it is really read the old value, compute the new value, write the result back. If two threads interleave those three steps, one thread's update can be overwritten by the other's, and the final value of G depends on the exact interleaving — that is, on the timing of the scheduler. This read–compute–write sequence is why a plain shared variable can lose updates even when each single instruction is atomic. Mutual exclusion (coming up in the answer below) is the mechanism that keeps the whole sequence indivisible.

12.2.2 Running It with Round Robin

After compiling, the start address was set to 200 and the program was loaded into memory. The "input auto" button keeps the output console on top so you can watch results appear. In the OS view, round robin was selected this time — the reasoning: with round robin each thread gets a fair share of execution time. This demo creates only one process (with two threads inside it), so no extra processes were created; round robin's 5-tick quantum was left as is. After creating the process and starting, the output appears: both threads are created, the process waits for them to complete, and the symbol table view shows the G and N variables for the two threads side by side.

12.2.3 What the Output Shows

The run printed "thread created" for both threads and the process waited for both to finish. The striking result: even though thread one was called first, thread two completed first — it printed its value of G and exited — and then thread one printed its value and exited, and finally main exited. The two threads produced different final values for G, and nothing in the program says which one is right.

The run, traced. One process with two threads inside it; round robin with a 5-tick quantum; start address 200.

Both threads are created — the console prints "thread created" twice.
The process waits for both threads to complete before main can exit.
Thread two finishes first — even though thread one was started first, thread two prints its value of G and exits.
Thread one finishes second — it prints its own value of G and exits; then main exits.
The two values differ — thread one and thread two each computed a different final G, and the program contains nothing that says which value is correct (in this run, we cannot even tell whether G = 12 or G = 20 is the right result).

Sense-check: with no synchronization, the two threads interleaved their updates to G; whichever thread completed its last write last decided the final value, and that thread need not be the one that started first. The output order reflects completion order, not call order.

Q: Why did thread two finish first, when we called thread one first? And why are the values different? A: Because there is no synchronization and no permission mechanism on the critical section. Any one of the threads can enter the critical section, so both threads run in parallel, and whichever thread completes first is the one that prints first. The order is not guaranteed by the order of the calls. A student's answer — "any one of the threads can enter the critical section" — was exactly the right instinct: the moment any thread may enter freely, the outcome is decided by timing, not by program order.

Q: So what would make the value of G consistent? A: The threads must have proper permission to enter and leave the critical section. In the reference material the code uses keywords like enter and leave, and synchronize to mark the two threads as synchronized: if you use synchronize for two threads, both will be synchronized — you still do not know the order, but only one thread can be inside the critical section at a time, which is what mutual exclusion means. Without those keywords both threads run in parallel and the shared value is inconsistent — in this run we do not even know whether G = 12 or G = 20 is the correct result. That is the problem, and explaining why the values differ is exactly what the assignment asks you to reason out in your own words.

A few assignment logistics were settled right after this demo, in a cluster of questions:

Q: Does it make any difference in marks if we work individually or in a group? A: Yes — the marks depend on the contribution of each member. The front page of your PDF states who the members are and what each contributed. If both contributed equally, write 50-50; if it is 75-25, the 75-percent contributor gets more marks. If nothing is stated, 50-50 is assumed. A member who contributed nothing gets zero. If you plan to work alone, mention that in the sheet being shared.

Q: Do we need to make a separate report, or only submit one PDF? A: Only one PDF. Its front page carries the assignment name, then the members and their contributions; a single-person assignment just lists the name and roll number, with no contribution needed.

Q: It would really help if the questions said which ones need results from the CPU simulator and which ones do not. A: The questions will carry a keyword — something like "use the CPU simulator" — so it will be clear when the simulator is required and when plain paperwork is enough. One example already shown did not carry the keyword, but the instructor agreed to make sure the keyword appears.

Exam note: a question of this type — what happens to a shared value when two threads update it without synchronization — is a likely assignment question, and the explanation must include the synchronization keyword (enter/leave/synchronize) and the idea of mutual exclusion. Another expected question asks you to define a semaphore and a mutex and explain how they differ.

12.3 Memory Management Requirements (Recap)

Before moving to new material, the class recapped what any memory management scheme must provide. The four requirements are relocation, protection, sharing, and logical organization, plus a fifth consideration, physical organization.

12.3.1 The Four Requirements

Relocation — a program must be able to run when loaded at different places in memory, so addresses must be adjustable at run time. Because processes get swapped out and back in (and because the operating system cannot know in advance which other programs will be resident), a process cannot be tied to one fixed spot: it may start at address 1000 on one run and address 8000 on the next, and its memory references must still work.
Protection — one process must not be able to read or corrupt another process's memory. This must be checked by the processor hardware at the moment of every memory reference, because the operating system cannot predict every address a program will generate.
Sharing — when more than one process needs the same code, they must be able to share it safely. Protection and sharing must work together: several processes may read the same program text, but none may scribble on another's data.
Logical organization — memory is laid out linearly, and programs are written and compiled as modules; the operating system must handle how those modules are placed. Not all processes can share all modules, so shared modules are given a protection mode — read-only or execute-only. Segmentation, which comes later in the course, is what makes this kind of logical organization practical.

The fifth consideration: physical organization. Main memory and secondary memory are the two levels of a physical memory system, and the operating system is responsible for the flow of information between them. A program that does not fit in main memory — or a set of programs that together exceed it — cannot simply be abandoned to the programmer, so the system keeps parts of programs in secondary storage and brings them in when needed. Every technique in the rest of this lecture (partitioning, swapping, buddy allocation, paging) is a different answer to the question how does the system move information between these two levels.

12.3.2 Base and Limit Registers

The hardware support for protection is a pair of registers. Every address generated while a process runs is checked against the base value: if it is within the process's range — at or above the base address and within the limit — it is accepted, and the limit (the extent of the process) is applied to it before it is sent on to the memory unit. Any illegal address, one that falls outside the range, is trapped to the operating system.

The precise rule. The base register holds the smallest legal physical address of the process; the limit register holds the size of the process's range, not its end address. When the CPU generates a logical address, the hardware checks the limit first:

$logical address \geq limit \Rightarrow trap to the operating system (illegal access)$

and only if the check passes does it form the physical address by adding the base:

$physical address = base + logical address$

So a process whose base is 300040 and whose limit is 120900 may legally touch the range $300040 \leq physical < 300040 + 120900 = 420940$ . The rule keeps a user program from reaching the operating system's memory or another process's memory: any reference that would land outside the base-plus-limit range is rejected by the comparator hardware, and an interrupt is raised to the operating system, which treats it as a fatal error for the offending process. Only the operating system, running in kernel mode with privileged instructions, can load or change the base and limit registers — a user program can never widen its own cage.

Base and limit in action. Suppose a process has base = 1000 and limit = 2000, so its legal physical range is $1000 \leq physical < 3000$ .

The CPU generates logical address 1500. Check: $1500 < 2000$ — inside the limit. Physical address: $1000 + 1500 = 2500$ . The access proceeds.
The CPU generates logical address 2100. Check: $2100 \geq 2000$ — outside the limit. The access is trapped and the operating system ends the process; the address 3100 would have landed beyond the process's block.

Sense-check: the limit check happens before the base is added, so the trap fires on the process's own address, not on the physical result — which is exactly why the base and limit pair can both relocate a process (move it anywhere) and protect everyone else from it.

12.3.3 Logical and Physical Organization

The physical memory system has two tiers. Main memory is very fast but volatile, smaller in capacity, and high in cost; secondary memory is slower, cheaper, and non-volatile. You cannot keep everything in main memory, so parts of programs live in secondary storage and are brought in when needed.

12.3.4 Logical vs Physical Addresses and Dynamic Relocation

The address generated by the CPU is called the logical address or the virtual address — the two names describe the same thing. Because the process is being relocated dynamically, that address is added to the value in the relocation register to produce the physical address, which is the address actually used in memory. Every address the CPU generates must be translated this way before it can be executed. This is the key point to remember: dynamic relocation means adding the relocation register (the base) to the logical address to get the physical address.

Two names, one address. The CPU produces logical addresses (also called virtual addresses); the memory unit receives physical addresses. The user program never sees the physical numbers — it thinks it runs at addresses 0 to max, and only at the moment a reference is executed does the memory-management hardware map it: $physical = base + logical$ . This mapping is what makes dynamic relocation possible: the same program can be moved to a new base mid-execution, and every subsequent reference automatically lands in the new home. It is also what makes compaction possible, which we will use in the next section — a scheme that can move processes while they run cannot work with compile-time or load-time binding.

Recap: memory management must relocate, protect, and share, and it must organize both logical modules and the two-tier physical memory. The hardware pair that delivers all of this is the base and limit registers: limit first (trap on overflow), then base (relocate). The relocation register version of the base register — add it to every logical address — is the mechanism behind dynamic relocation, and it is the key that unlocks every technique that follows: swapping, compaction, and paging all rely on being able to move a process after it has started.

12.4 Fixed Partitioning

The memory management techniques on the syllabus are fixed partition, dynamic partitioning, simple paging, simple segmentation, virtual paging, and virtual memory segmentation; the class had already covered the first two in detail and used the buddy system as a bridge before starting paging.

The question every scheme answers. Picture main memory as a long shelf that must hold several processes at once. Fixed partitioning is the simplest answer: nail permanent dividers into the shelf at system generation time. Every process then goes into a box of the right size. The price of simplicity is waste, and the next several sections are a history of cleverer answers — variable-sized boxes (dynamic partitioning), boxes that can merge (the buddy system), and finally boxes so small that waste almost disappears (paging).

12.4.1 How It Works and Its Problems

Fixed partitioning divides memory into partitions of some fixed size. If a partition is bigger than the process placed in it, some of the space inside the partition is wasted — and that wasted space cannot be used efficiently by any other process, even though enough free space exists here and there across the whole memory. If a process is bigger than the largest partition, it cannot be allocated at all. Using unequal partition sizes provides some degree of flexibility, but a very large process still cannot fit.

Equal and unequal partitions. With equal-size partitions, any process at most the partition size fits anywhere, and the placement question disappears — every free partition is identical. The price is severe internal fragmentation: a 2 MB program occupies a full 8 MB partition, wasting 6 MB inside it. Unequal-size partitions (say 2, 4, 6, 8, 12, and 16 MB) reduce the waste by matching each process to the smallest partition it fits into, but they cannot solve it: the waste is just smaller. And in both variants, a process larger than the largest partition simply cannot be placed — the programmer would have to split it into overlays that swap pieces of themselves in and out of memory, a painful practice the operating system should be doing instead. The partition sizes also fix the maximum number of active processes at system generation time.

The fatal limit: a process bigger than the biggest fixed partition can never be allocated at all. No amount of clever queueing fixes this — if the largest partition is 16 MB and a job needs 20 MB, that job is unplaceable, even if the machine is otherwise empty. This one flaw is a major reason fixed partitioning has all but disappeared: an early IBM mainframe operating system, OS/MFT (Multiprogramming with a Fixed number of Tasks), was a successful user of the technique.

12.4.2 Queue Structures: One Queue per Partition vs a Single Queue

Two queue arrangements are possible. You can keep one queue per partition, so every process is placed in the queue of a matching partition. Or you can use a single queue that holds every incoming process — an 8 MB process and a 4 MB process both wait in the same queue — and then, based on the size of the process, send it to the corresponding partition in memory. The single queue is simpler to think about, but the overhead of maintaining these queues is the price you pay. Both arrangements share the fundamental flaw: a process that needs more than the biggest partition can never be placed.

Two queue designs, one trade-off.

	One queue per partition	Single queue
Placement	Each process waits in the queue of the smallest partition it fits	All processes wait together; the loader picks the partition at load time
Internal fragmentation	Minimized (smallest fitting partition always chosen)	A partition can sit idle while smaller processes wait — e.g., the 16 MB partition unused while a 4 MB process queues for a 4 MB slot
Overhead	Many queues to maintain	One queue, but a partition-selection decision on every load
When to pick	You want the smallest waste per process	You want the simplest mental model

With the single queue, the sensible rule is: when a process is to be loaded, pick the smallest available partition that will hold it — and if all partitions are occupied, decide which process to swap out (a scheduling decision, influenced by priority and by whether the candidate is blocked or ready). Both designs share the same hard ceiling, though: a process larger than the largest partition never fits, and the number of active processes is capped by the number of partitions.

Recap: fixed partitioning divides memory into permanent partitions — simple for the operating system, painful for the memory: wasted space inside every oversized partition (internal fragmentation) and a hard ceiling on process size. The single-queue arrangement fixes part of the utilization problem but not the ceiling. The next scheme, dynamic partitioning, attacks the first flaw by making partitions match processes exactly — and in doing so it creates a brand-new kind of waste.

12.5 Dynamic Partitioning

Dynamic partitioning removes the fixed sizes: whatever process arrives is allocated exactly the memory it needs, at whatever locations happen to be free.

Why dynamic beats fixed. Fixed partitioning forces a process into a preset box — a 7 MB process in an 8 MB box wastes 1 MB forever. Dynamic partitioning instead grows a partition to fit the process: a partition is created with exactly the size of the incoming process and dissolved when the process leaves. No process is ever forced into an oversized box, so the internal fragmentation of fixed partitioning disappears. The new price you pay is on the other side of the ledger: freed space is left behind in odd sizes and scattered locations — holes — and they accumulate.

12.5.1 Allocating on Demand: The 56 MB Walkthrough

The worked example: total memory of 56 MB. Process 1 arrives and is allocated; process 2 arrives and is allocated; process 3 arrives and is allocated — and only 4 MB is left. If another process arrives needing more than 4 MB, the operating system must find a process already in memory that is not used for a long time, or is not needed right now, swap it out, and place the new process in that space; the evicted process is brought back when it is needed for execution again. In the walkthrough, process 2 is swapped out and process 4 is brought in, leaving a 6 MB gap. Later, process 1 is swapped out — either because it completed or because a higher-priority process arrived (priority scheduling from the process-scheduling unit: when a higher-priority process needs the CPU, the scheduler must give it priority and put it in memory for execution) — and then process 2 comes back into play. The same pattern continues indefinitely.

The 56 MB walkthrough, worked. Suppose the first three processes are 22 MB, 16 MB, and 14 MB, and process 4 arrives needing 10 MB.

P1 (22 MB) is placed at the bottom of memory. Free: 34 MB.
P2 (16 MB) is placed above P1. Free: 18 MB.
P3 (14 MB) is placed above P2. Free: 4 MB — exactly the "only 4 MB is left" moment.
P4 (10 MB) arrives and needs more than the free 4 MB. The operating system swaps out a process that is not needed right now — P2 (16 MB) — freeing its block.
P4 (10 MB) is placed in the 16 MB block, leaving a 6 MB gap above it.
Later, P1 is swapped out (it completed, or a higher-priority process needs the memory) — a 22 MB hole opens at the bottom.
P2 comes back into the 22 MB hole, leaving a 6 MB gap above it.

The free space is now 6 + 6 + 4 = 16 MB in three separate pieces — enough total for a process of roughly that size, but no single piece can hold one.

Sense-check: every allocation used exactly the memory the process asked for — no internal fragmentation — and every swap-out left an odd-sized gap. The free space totals 16 MB, yet a single 16 MB request would be rejected because no hole is 16 MB; that is external fragmentation, and it is the cost dynamic partitioning pays.

12.5.2 Holes and External Fragmentation

The available memory blocks in dynamic partitioning are called holes, and they are scattered all over memory: a hole here, a hole there, a hole over there. In the example the free pieces added up to 16 MB — enough to allocate a process of roughly that size — but the space was not continuous, so no single request of that size could be satisfied. That scattered free space is external fragmentation.

Holes, defined. A hole is a block of free memory large enough to hold a new process — or a piece of one. Dynamic partitioning keeps a set of holes, and the steady rhythm of process arrivals, completions, and swaps turns one large free region into many small ones: every swap-out of a 16 MB process leaves a hole shaped like that process, and the next process rarely has the same shape. Over time memory becomes a jigsaw of allocated blocks and gaps. External fragmentation is exactly this situation: the total free memory is enough for a request, but the free memory is not contiguous, so the request cannot be served. Note the contrast that will matter in the paging sections: with dynamic partitioning, the wasted space is between processes, outside any partition — external to them.

12.5.3 Compaction

To overcome external fragmentation you can use compaction: shuffle the free holes to one side and the processes to the other side, which produces one big contiguous hole that can be allocated to a process. Compaction is not an easy job — it is time consuming and wastes processor time, so it is an expensive operation. It works only when relocation is dynamic, performed at execution time (which is why the relocation register discussion matters).

Compaction's price. Compaction is a moving operation: every process in memory is lifted and re-settled so that all the holes slide together into one big contiguous hole. The processor does nothing useful while the copies run, and the bigger the memory, the longer the move — which is why compaction is an expensive, occasional operation rather than a routine one. And it is only possible when relocation is dynamic: a process whose addresses were fixed at load time would be left pointing at the wrong memory after the shuffle. That constraint is why the base-and-limit relocation story matters — static allocation cannot be compacted.

12.5.4 Managing the Set of Holes

The operating system keeps a set of holes. When a process arrives it searches for a hole; if the chosen hole is very big, it is split into two — one part is allocated to the process and the other part is returned to the set of holes. When a process ends, its block is released and put back into the set of holes, and if the newly released block is adjacent to an already-free block, the two are merged into a larger one. If at some moment no block is large enough to hold a process, the OS simply waits until a block becomes available. Four allocation policies — first fit, best fit, next fit, and worst fit — were covered earlier, and problems on them were assumed solved.

Recap: dynamic partitioning allocates exactly the memory each process needs, which removes internal fragmentation but creates scattered holes — external fragmentation. The two remedies, each with a cost, are compaction (shuffle everything together, but it wastes processor time and needs dynamic relocation) and smart hole selection (first/best/next/worst fit, covered earlier). The hole set is maintained by splitting big holes on allocation and merging adjacent free blocks on release — and it is this split-and-merge rhythm, in powers of two, that the buddy system systematizes next.

12.6 Fragmentation: External vs Internal

There are two kinds of fragmentation, and it is worth keeping the definitions exactly straight.

12.6.1 Two Kinds of Waste

External fragmentation is the situation where the total free memory space is enough to satisfy a particular request, but the space is not contiguous — the 16 MB scattered across many holes example. Internal fragmentation is the situation where the memory allocated to a process is larger than the amount requested: the difference is space internal to the partition that is not being used. The in-class example: out of a 16 MB allocation, only 14 MB were used, leaving 2 MB free — slightly larger than what the process actually requested, so the leftover is wasted inside the partition. Small amounts of internal fragmentation happening here and there can, together, add up to a lot of wasted memory — the professor's phrasing was that scattered internal fragmentation collectively resembles external fragmentation.

The two kinds of waste, side by side.

	External fragmentation	Internal fragmentation
Where the waste lives	Between allocated blocks — free memory too scattered to use	Inside an allocated block — memory given to a process but not used by it
Who created it	The rhythm of allocations and swaps leaving odd-shaped holes	The allocator rounding up (a partition bigger than the process)
Fixed partitioning	Does not suffer it (partitions are preset)	Suffers it badly (every oversized partition)
Dynamic partitioning	Suffers it badly (scattered holes)	Does not suffer it (exact-size allocation)
Cure	Compaction (expensive, needs dynamic relocation)	Smaller, matched allocation units — the direction paging takes

The professor's warning deserves a careful restatement: small amounts of internal fragmentation, scattered across many partitions, can collectively add up to a lot of wasted memory — in the aggregate it looks like the same damage as external fragmentation. But the two remain distinct: external fragmentation is free space between allocations that cannot be used, while internal fragmentation is allocated space inside a block that is never used. One is a gap in the jigsaw; the other is a hole inside a puzzle piece.

The 16 MB allocation. A process requests 14 MB and is handed a 16 MB partition (say, because 16 MB is the next available block of the right shape).

Memory allocated: 16 MB.
Memory actually used: 14 MB.
Wasted inside the partition: 2 MB — this is internal fragmentation.

Sense-check: the 2 MB is unusable by any other process, because it is enclosed inside the allocated block. In the dynamic-partitioning walkthrough, by contrast, free space was external: 16 MB existed but in pieces of 6, 6, and 4 MB, so no single request of that size could be served. Both are waste; only the location differs.

12.6.2 Compaction Requires Dynamic Relocation

To reduce fragmentation you go for compaction — but compaction is time consuming, and it is possible only if relocation is dynamic and done at execution time. That constraint is why the whole relocation-register story matters: static allocation cannot be compacted.

Recap: keep the two definitions straight — external fragmentation is free space that is too scattered (total is enough, contiguity is not), internal fragmentation is allocated space that is too big (the block is enough, the process is not). Compaction cures external fragmentation but only when relocation is dynamic, and it costs processor time; internal fragmentation has no such cure — it is removed by allocating in smaller matched units, which is precisely what paging does.

12.7 Swapping

Swapping moves processes between memory and a secondary storage device called the backing store.

Why swap at all? Main memory is smaller than the total demand for it. When every process in memory is blocked — waiting on I/O, for instance — the processor idles, and the memory those blocked processes occupy is doing nothing. Swapping trades a slow I/O move for a busy processor: a blocked or low-priority process is written out to the backing store, and the freed memory is handed to a process that can actually run. The move itself is a memory-management decision made by the medium-term part of the scheduling function, and it is exactly the mechanism the dynamic-partitioning walkthrough used when process 2 was evicted to make room for process 4.

12.7.1 The Backing Store, Roll Out, and Roll In

When a process is not needed right now, it is swapped out of memory to the backing store; later, when it is needed for execution again, it is brought back. The backing store must be large enough to accommodate copies of all the process images (all the users' images, in the spoken phrasing). The specific swap between main memory and secondary storage is called roll out and roll in: the lower-priority process is rolled out, the higher-priority one is rolled in. Remember that a higher-priority process can always be loaded and executed while a lower-priority process is swapped out; whether this happens depends on the scheduling algorithms and on priority-based processes.

Backing store, roll out, roll in. The backing store is the disk space reserved for swapped process images — commonly a fast disk, and it must be large enough to hold copies of all the process images of all users at once. The process image is the whole snapshot of a process: its program, its data, its stack, and its process control information — everything needed to resume execution later. Roll out is the specific swap-out of a lower-priority process; roll in is the swap-in of a higher-priority one. This variant exists because priority scheduling creates the situation: a high-priority process arrives while memory is full, so the low-priority occupant is rolled out, the newcomer is rolled in and run, and the evicted process is rolled back in when it can execute again. The priority scheduling unit supplies the rule — when a higher-priority process needs the CPU, the scheduler must give it priority and put it in memory for execution.

12.7.2 The Cost of Swapping

Transfer time has to be taken into account: the total transfer time is directly proportional to the amount of memory being transferred, and memory is transferred in blocks, so the size of the image determines the cost of the swap.

How much a swap really costs. The reference treatment uses a concrete estimate: a 100 MB process image on a disk with a 50 MB/s transfer rate.

$transfer time = \frac{image size}{transfer rate} = \frac{100 MB}{50 MB/s} = 2 seconds$

Add an average disk latency of about 8 ms: each single transfer costs about 2008 ms. But a swap is a round trip — the process must be written out and later read back in — so the full swap costs about 4016 ms (roughly 4 seconds) per process.

Sense-check: the transfer dominates the latency by a factor of 250, so the total transfer time is directly proportional to the amount of memory transferred. A 3 GB process would take about 60 seconds — which is why swapping only the memory a process actually uses (not the memory it could use) is a major practical win, and why transfer time is the number to watch whenever a system starts swapping heavily.

When swapping gets dangerous. The context-switch time in a swapping system is high — seconds, as computed above — so a quantum or scheduling interval must be long enough to make the swap worthwhile. Worse, a process with pending I/O must not be swapped: if the I/O device writes asynchronously into buffers in the process's memory while another process is swapped into that same space, the wrong data lands in the wrong process. The two standard protections are to never swap a process with pending I/O, or to route I/O through operating-system buffers and copy to the process only while it is swapped in. Modern systems still carry the mechanism: Linux swaps (and the UNIX swapper is a dedicated kernel process that wakes when memory pressure passes a threshold), and Windows keeps a system-managed Swapfile.sys for the same purpose.

Real-world: swapping is not a textbook curiosity — it exists in many systems, everywhere; Linux and Windows both swap processes in and out of memory.

Recap: swapping moves whole process images between main memory and a backing store; the priority-driven version is roll out and roll in. The cost is dominated by transfer time, which is directly proportional to the image size — seconds per swap for a 100 MB process — and pending I/O makes a swap unsafe without care. The ideas that make swapping work — move a whole process out, bring it back later, resume it at a different location — are the same ideas that paging will carry to the level of individual pages next.

12.8 The Buddy System

Before paging, the class covered one more allocation technique: the buddy system, which is somewhat more efficient than the fixed and dynamic partitioning schemes seen so far.

12.8.1 Powers of Two and the Allocation Condition

The buddy system is a memory allocation and management algorithm that manages memory in terms of powers of two. Whenever a memory block is split, it is split into two equal halves, and every block size is a power of two. Allocation takes place only in whole power-of-two blocks: the request gets a block of the right power of two, and the remaining half is free and available for some other process. If a previously allocated block is freed and the block adjacent to it — the one it was split from — is also free, the two are merged back into a larger block. That merged pair is what makes the algorithm "buddy" based: blocks only ever recombine with their own buddy.

The allocation condition: for a request of size $x$ , check whether $2^{k - 1} < x \leq 2^{k}$ . Only if that condition holds can a block of size $2^{k}$ be allocated to this process. If the condition is not yet satisfied, you recursively divide the block equally and test again after each division; the moment the condition is satisfied, you allocate. So the procedure is: find a free block, halve it until the halves are just large enough for the request, then allocate one half — in powers of two only, the dividing takes place.

The allocation condition, precisely. A request of size $x$ may be given a block of size $2^{k}$ exactly when

$2^{k - 1} < x \leq 2^{k}$

Every symbol: $x$ is the size requested; $k$ is the chosen block-size exponent; $2^{k - 1}$ is the size of the next smaller block; $2^{k}$ is the block allocated. The upper bound is inclusive: a request of exactly $2^{k}$ gets a block of size $2^{k}$ . The lower bound is strict: a request of exactly $2^{k - 1}$ must NOT be given the larger block — it fits in the smaller one, and giving it the larger one would waste it.

Why powers of two? Because the system's bookkeeping is then trivial. The operating system keeps one list of free blocks for each size $2^{i}$ . To satisfy a request of size $x$ with $2^{k - 1} < x \leq 2^{k}$ : if a free $2^{k}$ block exists, take it. If not, find a free $2^{k + 1}$ block, split it into two equal $2^{k}$ halves, and take one. The two halves are buddies: each remembers the other as the block it was split from, and they are the only pair that may recombine. When a block is freed, the system checks its buddy: if the buddy is free, the pair coalesces into one $2^{k + 1}$ block, and that block's buddy is checked in turn — the cascade can rebuild an entire $2^{U}$ block from its pieces.

Think of it like a tournament bracket. The buddy system is a single-elimination bracket of memory: the 16K region is the final, two 8K blocks are the semifinals, four 4K blocks are the quarterfinals, and so on. Allocating splits a node into its two children; freeing lets two sibling children merge back into their parent. A team can only recombine with the team it faced in its own match — never with the team from the adjacent match, no matter how close they stand on the field.

12.8.2 Worked Example: 16K Memory, Seven Processes

The total memory block is 16K, and it starts by being equally divided into two 8K blocks. The processes and their needs:

Process	Need	Block allocated
A	3.5K	4K
B	1.2K	2K
C	3.1K	4K
D	1.9K	2K
E	3.2K	4K
F	1.6K	2K
G	1.8K	2K

The full trace. Check each request against the condition $2^{k - 1} < x \leq 2^{k}$ , split until the halves are just large enough, allocate one half, and leave the other free.

A (3.5K): the first 8K block is divided into 4K and 4K. Is 3.5K between 2K and 4K? Yes — if you divided further you would get 2K and 2K, and 3.5K is greater than 2K. So the whole 4K block is allocated to A, and the other 4K remains free.
B (1.2K): 1.2K is less than 2K (and $1 K < 1.2 K \leq 2 K$ ), so the free 4K is divided: the first 2K is allocated to B and the next 2K is free.
C (3.1K): the next available block large enough for this request is used; the second 8K block is split, and a 4K block is allocated for C, leaving its buddy 4K free. The leftover space inside the allocated block is internal fragmentation — the remaining space is always there, in this scheme, because blocks only come in powers of two.
D (1.9K): needs a 2K block, so the available 4K is equally divided again (4K into two, then the relevant 2K half); the resulting 2K satisfies D, and the remaining half is free.

Memory now, in the two 8K halves:

  | A(4K) | B(2K) | free(2K)  |  C(4K) | free(2K) | D(2K) |

Free C: C's space is freed (C completed, say), and a hole is created. The second half now shows two adjacent free blocks — the 4K hole and the free 2K — and the next section explains why they do NOT merge.
E (3.2K): the free 2K does not satisfy 3.2K — 3.2K is greater than 2K — so E checks the next available block, which is the right size under the condition: the free 4K left by C, allocated for E. Only small blocks are left free.
Free B: B's space is freed too; the two adjacent blocks — B's freed 2K and the 2K that was already free, which came from the same 4K split — are buddies. Since they are adjacent, they are merged into a larger 4K block that can be allocated to the next request.
F (1.6K): 1.6K checks against the merged block, which is far larger than needed; it checks the next available block, which matches the condition, and that 2K block is allocated for F.
G (1.8K): 1.8K is allocated right where the merged block is: the merged 4K is divided into 2K and 2K, and one 2K is allocated to G.

Final state of the 16K memory:

| A(4K) | G(2K) | free(2K)  |  E(4K) | F(2K) | D(2K) |

Sense-check: 4 + 2 + 2 + 4 + 2 + 2 = 16K exactly; every allocation is a power of two; every free block's buddy is either allocated or itself free. The follow-up questions from class: what is the state of memory after allocating the processes (the layout above), and what is the state of memory after freeing D — which simply creates a hole in that space, waiting to be merged with its buddy if that buddy is also free (here F holds D's buddy, so no merge happens).

12.8.3 Merging: Only Buddies Combine

The last follow-up question was the trap: after freeing process C, there are two holes that sit adjacent to each other — both free, side by side. Should we combine them? No. Here is why: the division took place between this 2K and this 2K — they are buddies from the same 4K split; these two blocks over here are not buddies. Only the pair that was already divided together — the pair that came from splitting one larger block — can be recombined. This 2K belongs with that one, and that 2K belongs with the 4K family it was split from. If the buddy is free you can merge; if it is not free, you cannot — even when another free block happens to sit right next to yours. The two adjacent holes stay as they are.

12.8.4 Student Questions and Answers

Q: After freeing C and B, we have two free blocks that are adjacent to each other. Should we combine them into a larger block? A: No — that is not correct. Even though they look adjacent, the division took place between different pairs. The 4K block was divided into two 2K blocks, and only those two can be recombined; the other 2K belongs to a different split. Whatever we have already divided — only those things can be combined. So we leave the two holes as they are.

Exam note: this exact scenario — knowing the state of memory after each allocation and free, and knowing which free blocks can be merged and which cannot — is the kind of buddy system question to expect. Work every split and every free with the allocation condition, draw the two 8K halves, and only ever merge a block with its own buddy.

12.9 Paging: An Introduction

Paging is the technique that overcomes the disadvantages of fixed-size partitioning and dynamic partitioning, and it eliminates external fragmentation completely. The core idea: the physical address space of a process is always non-contiguous — the first page is here, the second page is somewhere else entirely; it is not one block after another.

The leap that fixes fragmentation. Every scheme so far demanded contiguity: a process occupied one unbroken stretch of memory, so free memory had to be one unbroken stretch too. Paging abandons that demand. It cuts physical memory into many small equal boxes (frames) and cuts each process into equally sized pieces (pages) — and then it drops the pages into whatever frames happen to be free. A process no longer needs a single hole; it needs any N free frames. Since every frame is the same size, there are no "holes too small to use": a 2K free frame is exactly as good as any other 2K free frame. That single change removes external fragmentation, because the only thing that ever goes to waste is part of the last page of a process.

12.9.1 Frames and Pages

The whole physical memory is divided into many fixed-sized blocks called frames. The logical memory — the memory as the CPU sees it — is divided into blocks of the same size, called pages. With respect to physical memory we say frames; with respect to logical memory we say pages, but the sizes are identical, because only same-size pages fit into same-size frames. The size is a power of two. The operating system must keep track of all the free frames — how many frames are free in physical memory — allocate frames to each page, and load the program. For all of this we need a page table, whose job is translating logical addresses into physical addresses. The shared unit size, written $2^{n}$ , is the same for pages and frames.

Frames, pages, and the page table. A frame is a fixed-length block of main memory — the physical side of the bargain. A page is a fixed-length block of logical (virtual) memory — the process side — and the two sizes are identical, with both a power of two:

$page size = frame size = 2^{n}$

Only same-size pages fit into same-size frames, so the OS keeps a free-frame list (every frame not currently holding a page), allocates frames to the pages of each process, and loads the program. Because a process's pages may sit in widely separated frames, the system needs a page table: one entry per page of the process, where entry $p$ holds the number of the frame that currently contains page $p$ . The page table is the map that turns each logical address into the right physical location — the translation machinery is the subject of the next section. The professor's memory trick: pages belong to logical memory, frames belong to physical memory, and their sizes are identical — say it once and the terminology stops confusing you.

12.9.2 Worked Example: Allocating Pages to Frames

The setup: four processes, each with a known number of pages, and a main memory of 15 frames total (page and frame sizes are the same, remember). Process 1 needs 4 pages, so 4 frames are allocated to it. Process 2 needs 3 pages and is allocated the next available frames. Process 3 needs 4 pages and is allocated the next available frames. On the diagram it looks contiguous, but it need not be — the frames assigned to one process do not have to be adjacent. Process 4 needs 5 pages, but only 4 frames are left. So we swap out a process that is not needed right now — here, process B (3 pages) is swapped out, freeing 3 frames, and with the remaining free frame the total is enough. Because paging allows non-contiguous allocation, process D's first 3 pages are placed where B was, and its remaining 2 pages go into the next available space elsewhere. There is no requirement of contiguity, so the allocation simply works. That, in a nutshell, is why paging removes external fragmentation: there are no "holes" left that are too small — any free frame is a usable frame.

Four processes into 15 frames, traced. Frame sizes equal page sizes; frames are numbered 0–14.

Process A (4 pages) is loaded into frames 0, 1, 2, 3.
Process B (3 pages) is loaded into frames 4, 5, 6.
Process C (4 pages) is loaded into frames 7, 8, 9, 10.

   Frame:  0  1  2  3 | 4  5  6 | 7  8  9 10 | 11 12 13 14
               A  A  A  A | B  B  B | C  C  C  C | ·  ·  ·  ·

Process D (5 pages) arrives, but only frames 11, 12, 13, 14 are free — 4 frames for a 5-page process. There is no contiguous 5-frame region at all, yet paging does not need one.
Process B is swapped out (it is not needed right now), freeing frames 4, 5, 6; now 7 frames are free.
D's pages are placed non-contiguously: pages 0, 1, 2 go into frames 4, 5, 6 (where B was), and pages 3, 4 go into the next available frames 11, 12. Frames 13 and 14 stay free.

   Frame:  0  1  2  3 | 4  5  6 | 7  8  9 10 | 11 12 13 14
               A  A  A  A | D0 D1 D2 | C  C  C  C | D3 D4 ·  ·

Sense-check: D's five pages live in two separate regions (4–6 and 11–12) — no contiguity anywhere. The free frames 13 and 14 are fully usable by any future process of any size, so no free space is ever stranded as a too-small hole. External fragmentation is gone; the only waste left in paging is the unused tail of a process's last page, which is internal fragmentation.

Recap: paging splits physical memory into equal frames and each process into equal pages of the same power-of-two size; pages drop into any free frames, so a process's memory is non-contiguous and every free frame is usable — external fragmentation disappears. The price is bookkeeping: a free-frame list and a page table per process, the table being the map the next section uses to translate addresses.

12.10 Address Translation in Paging

12.10.1 The Logical Address Format

The address generated by the CPU is the logical address (or virtual address), and it has two parts: a page number $p$ and an offset $d$ . The page number indexes the page table; the offset tells how far from the base of the page the desired location is. If the logical address space is $2^{m}$ and the page size is $2^{n}$ , then the total address has $m$ bits, of which the first $m - n$ bits are the page number and the remaining $n$ bits are the offset. In short: $m = (m - n) + n$ — the page-number bits plus the offset bits make the whole address. Page sizes are not universal — they differ from system to system, and different page sizes are seen across different types of systems.

The two fields of a logical address. A logical address is just a number, but it is a number with structure. Written in binary, its $m$ bits split into two fields:

$page number m - n bits p offset n bits d$

Every symbol: $m$ is the number of bits in the logical address (so the logical address space holds $2^{m}$ addresses); $n$ is the number of offset bits (so the page size is $2^{n}$ bytes — a power of two, matching the frame size); $p$ is the page number, the more significant $m - n$ bits; $d$ is the offset, the less significant $n$ bits. The identity $m = (m - n) + n$ just says the two fields account for every bit of the address.

Why this exact split? Because the page size is a power of two, the offset field is exactly the low $n$ bits, and the page number is the high $m - n$ bits. The offset is the distance from the start of the page to the desired byte — remember the professor's phrasing: the offset tells how far from the base of the page the desired location is, exactly as the limit-and-base view from the relocation discussion described a position inside a process. Page sizes are not universal: systems choose different $n$ (for example, 1K pages are common, but 4K pages appear across many systems), so the field split changes from system to system — the structure is the same, the numbers differ.

12.10.2 The Translation Path

The translation architecture: the CPU generates the logical address, $m$ bits total, with $m - n$ bits for the page number and $n$ bits for the offset. The page number is used as an index into the page table; at that index we find the frame number. The frame number plus the offset gives the physical address, which is sent to physical memory. Formally: $P A = f \times 2^{n} + d$ , where $f$ is the frame number from the page table, $2^{n}$ is the frame size (equal to the page size), and $d$ is the offset. Remember: page size and frame size are the same, so we need the page number to look up the frame number in the page table, and then add the offset (the limit, in the base-plus-offset way of thinking from the relocation discussion) to get the physical address.

The translation rule. Given a logical address split into page number $p$ and offset $d$ , the hardware performs two lookups-and-one-add:

$P A = f \times 2^{n} + d$

Every symbol: $P A$ is the physical address sent to memory; $f$ is the frame number found at entry $p$ of the page table; $2^{n}$ is the frame size (equal to the page size); $d$ is the offset carried unchanged from the logical address. The steps in order:

Extract the page number $p$ from the high $m - n$ bits of the logical address.
Index the process's page table with $p$ to find the frame number $f$ .
Compute the physical address $f \times 2^{n} + d$ , or equivalently append the binary of $f$ in front of the $n$ offset bits — the physical address is exactly the frame number followed by the unchanged offset.

The offset never changes during translation: it is the same distance inside the page and inside the frame, because the sizes are identical. Only the high part changes, from "which page of the process" to "which frame of memory".

A full translation with numbers. Page size 1K ( $n = 10$ ), 16-bit logical addresses, so $m = 16$ and the page number field holds $m - n = 6$ bits — up to 64 pages. The logical address 1502 in binary is 0000010111011110.

Split: the low 10 bits are the offset: 0111011110₂ = 478. The high 6 bits are the page number: 000001₂ = 1. So the address means page 1, offset 478.
Look up: the page table says page 1 lives in frame 6 (binary 000110).
Build the physical address: frame number 6, offset 478 → 0001100111011110₂ = 6 × 1024 + 478 = 6622.

Sense-check: $6 \times 2^{10} = 6144$ , plus 478 gives 6622, and the binary form shows the frame bits (000110) simply glued in front of the unchanged offset bits — the offset was carried through translation untouched.

Recap: the logical address is $m$ bits split into $m - n$ bits of page number and $n$ bits of offset; the page number indexes the page table, the frame number comes out, and $P A = f \times 2^{n} + d$ — frame bits in front, offset bits unchanged. The offset answers "how far from the base of the page", and the frame number answers "where the page actually lives"; together they name one physical byte.

12.11 Worked Problems: Paging

12.11.1 Problem 1: How Many Bits in the Logical and Physical Addresses?

A logical address space has 64 pages; the page size is 1024; and the space is mapped into 32 frames. The questions: how many bits are there in the logical address, and how many bits are there in the physical address?

The method taught: always write everything in powers of two first, because that makes the arithmetic trivial. 64 pages is $2^{6}$ pages, and the page size $1024 = 2^{10}$ . The number of bits in the logical address is the number of pages bits plus the offset bits: $(m - n) + n = 6 + 10 = 16$ . The logical address space is so $2^{6} \times 2^{10} = 2^{16}$ , and the logical address has 16 bits.

For the physical address: page size equals frame size, so each frame is also $2^{10}$ . There are $2^{5}$ frames (32 frames), so the frame-number part contributes 5 bits; $5 + 10 = 15$ . The physical address has 15 bits.

Problem 1, worked. Write every number as a power of two first.

Logical side: 64 pages = $2^{6}$ pages, and page size 1024 = $2^{10}$ . The page number field needs $m - n = 6$ bits, the offset field needs $n = 10$ bits.
Logical address bits: $(m - n) + n = 6 + 10 = 16$ bits — the whole logical space is $2^{6} \times 2^{10} = 2^{16}$ addresses.
Physical side: the frame size equals the page size, so each frame is $2^{10}$ bytes; 32 frames = $2^{5}$ frames, so the frame number field needs 5 bits.
Physical address bits: frame bits + offset bits = $5 + 10 = 15$ bits.

Answers: the logical address has 16 bits; the physical address has 15 bits.

Sense-check: the physical space is smaller than the logical one (15 bits < 16 bits) because the logical address space holds 64 pages while physical memory holds only 32 frames — the process may be bigger than the memory it runs in, and that difference in bits is exactly why a page table is needed. The translation worked example of the previous section confirms the pattern: 16-bit logical addresses with 1K pages split into 6 page bits and 10 offset bits.

The in-class exchange made the reasoning explicit:

Q: We have $2^{6}$ pages and each page is $2^{10}$ . What is $m - n$ , and what is $n$ ? Which part is which? A: $n = 10$ is the number of offset bits — the offset is the least significant part of the address. $m - n = 6$ is the number of page-number bits — the page number is the more significant part. Adding them gives the total number of bits in the logical address: $6 + 10 = 16$ . And since frames have the same size as pages, the physical address is $5 + 10 = 15$ bits.

Keep that mapping in mind: pages belong to the logical address space, frames belong to the physical address space, and $m - n$ bits represent the page number while $n$ bits represent the offset.

12.11.2 Problem 2: Page Number and Offset for a Decimal Address

The page size is 1 KB, which we write as $2^{10}$ — the offset counting is in bytes, so 1 KB is 1024 bytes. For a set of addresses given in decimal, find the page number and the offset of each.

The procedure, shown on the first address, 3085:

Convert the decimal address to binary: $308 5_{10} = 11000000110 1_{2}$ (with leading zeros to fill the address width, in this case a 32-bit address, so the page-number field holds 22 bits).
Split the binary number into two parts: the last $n = 10$ bits are the offset, and the remaining $m - n$ bits are the page number.
Convert each part back to decimal.

Problem 2, worked: the decimal address 3085 with a 1 KB page size.

Method A — divide by the page size. The efficient equivalent, and the one to use in the exam:

$3085 \div 1024 = 3 remainder 13$

The quotient is the page number and the remainder is the offset: page number 3, offset 13.

Method B — binary split. Convert to binary: $308 5_{10} = 11000000110 1_{2}$ . In a 32-bit address the page-number field holds $32 - 10 = 22$ bits, so pad to 32 bits: 0000…000110000001101. The last 10 bits are the offset: $000000110 1_{2} = 1 3_{10}$ . The remaining bits hold the page number: $1 1_{2} = 3_{10}$ . Same result: page number 3, offset 13.

Sense-check: page 3 starts at byte $3 \times 1024 = 3072$ , and $3072 + 13 = 3085$ — the original address comes back exactly. Note on the class answer: the value stated in class for the offset — 30 — does not check out (3 × 1024 = 3072, and 3085 − 3072 = 13), so the correct split is page 3, offset 13; the method is what matters, and both routes above agree on it.

The remaining addresses were left as exercises, with one practical tip: if converting to binary by hand is difficult, you can look up the binary equivalent online and split it there.

Exam note: expect this exact pattern — given a decimal address and a page size, find the page number and the offset (divide by the page size: quotient is the page, remainder is the offset), and be ready to count bits in the logical and physical address (write every number as a power of two, then add the page bits and offset bits for the logical side, frame bits and offset bits for the physical side).

Exam Guidance Summary

The assignment and exam-style questions for this lecture follow fixed patterns. Reviewing them once, against the lecture content, is the fastest preparation:

Simulator questions follow a fixed pattern: compile the given code, load it into memory (you may change the starting address), create processes, run under the policy the question names (FCFS, SJF, or round robin), change the round robin quantum (default 5 ticks, 0.2 seconds) as asked, and take a snapshot of every relevant view — ready queue, process list, process status, resources — plus the final output. One or two demo questions were shown in class; the actual questions are built from the reference PDFs with the code changed, and each task needs its own snapshot, with a one-line explanation underneath when the snapshot is not self-explanatory.
Number of questions: expect around three or four questions per group or individual. Questions are assigned per group, so the exact set varies.
Scheduling questions (FCFS, SJF, round robin): write the program implementing the policy, then draw the Gantt chart for the given burst times, and from it compute the average waiting time and the average turnaround time — the simulator itself does not let you change burst times, so this part is hand computation. For round robin you also fill a table for the different time quanta, and then reason out which policy is better, using the waiting times you recorded.
Threads/critical section question: run the process, count how many processes and how many threads are created, and represent the process/thread hierarchy as a tree (snapshot it). Explain why the shared value differs between threads and why the output order is not the call order — the answer must use the synchronization keyword and the idea of permission to enter and leave the critical section.
Semaphore versus mutex question: define each and explain how they differ.
Deadlock: create separate programs (P1, P2, P3, P4, P5, P6), compile each one separately, load them at different starting addresses (change the address for each program), attach the snapshots, and run with different time quanta (5, 10, and 15 ticks) for different processes, showing the process status. Deadlock-type questions of this form do not need the simulator — straight paperwork, with the answer pasted into the PDF — and the banker's algorithm question, which was seen earlier, is writing work as well.
Not in the syllabus: disk scheduling was not taught in this course and will not be given; questions like that are not in the syllabus.
Submission: a single PDF. The front page carries the assignment name, then the members and their contributions; if contributions are not stated, a 50-50 split is assumed, so state them explicitly. Marks follow the stated contribution.
Course position: only a few classes remain for completing the syllabus; the remaining memory management topics will be finished in the next sessions.

Key Industry Applications

CPU OS Simulator: the named tool used throughout — it shows FCFS, SJF, and round robin scheduling, process and thread behavior, and deadlock scenarios, and it lets you watch the ready queue, process states, and resources live.
Swapping in real operating systems: swapping between main memory and a backing store is used by mainstream operating systems — Linux and Windows both do it, everywhere. Linux runs a swapper process that wakes under memory pressure, and Windows keeps system-managed swap space for the same purpose.
Real scheduling policies: the scheduling policies themselves — FCFS, SJF, and round robin — are the real policies that operating systems implement, and the simulator's default round robin quantum (5 ticks, 0.2 seconds) mirrors how real schedulers pick a time slice.
Synchronization primitives: the synchronization primitives at the heart of the critical section demo — semaphores and mutexes — are the same primitives used to protect shared data in real multi-threaded programs, from web servers to database engines.
Deadlock avoidance: the banker's algorithm, covered in the deadlock unit, is the classic safe-allocation check for avoiding deadlock.
Memory management in the wild: the partitioning schemes in this lecture survive in recognizable form in modern systems — the buddy system is the allocation engine behind kernel memory in Linux (and UNIX kernels generally), and paging, the technique the lecture ended on, is the foundation of virtual memory in every modern general-purpose operating system, including the Linux and Windows swap stories above.

OS Lecture 12 notes · Memory Management: Fragmentation, Swapping, Buddy System, and Paging

Operating Systems· undergraduate· 2026-08-15

Sections Breakdown

1The CPU OS Simulator: From Source Code to Running Processes

The CPU OS Simulator workflow from compiling source code to running processes under FCFS, SJF, or round robin, including the arrival-delay FCFS demo.

2The Critical Section Demo: Two Threads, One Shared Variable

Two threads updating a shared variable with no synchronization, and why mutual exclusion via permission to enter and leave the critical section is required.

3Memory Management Requirements (Recap)

The four memory management requirements, base and limit registers, and dynamic relocation of logical to physical addresses.

4Fixed Partitioning

Fixed partitions, internal fragmentation, the hard ceiling on process size, and the two queue structures.

5Dynamic Partitioning

Exact-size allocation, scattered holes, external fragmentation, compaction, and the split-and-merge management of holes.

6Fragmentation: External vs Internal

External fragmentation versus internal fragmentation, side by side, and which technique cures which.

7Swapping

Swapping whole process images between main memory and the backing store, roll out and roll in, and the cost of swapping.

8The Buddy System

Power-of-two allocation with the condition 2^(k-1) < x <= 2^k, the 16K worked example with processes A through G, and buddy-only merging.

9Paging: An Introduction

Frames and pages of equal power-of-two size, non-contiguous allocation, and why external fragmentation disappears.

10Address Translation in Paging

The page number and offset fields of a logical address, the page table lookup, and the physical address formula PA = f x 2^n + d.

11Worked Problems: Paging

Worked problems: counting logical and physical address bits, and splitting the decimal address 3085 into page number and offset.

12Exam Guidance Summary

Assignment and exam patterns: simulator snapshots, Gantt-chart computation, the synchronization-keyword explanation, and single-PDF submission rules.

13Key Industry Applications

The lecture's techniques in real systems: Linux and Windows swapping, the buddy system in kernel memory allocation, and paging as the basis of virtual memory.

Undergraduate students in Operating Systems

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

The CPU OS Simulator: From Source Code to Running Processes

Must-know: The simulator pattern is compile, load (optionally at a changed start address), create processes, run under the named policy, snapshot the relevant views, and explain each snapshot in one line.

⚠️ Top pitfall: Treating arrival order as execution order under FCFS without accounting for an arrival delay; the delayed process joins the tail and runs last.

Self-check: Under FCFS, where does a process with a 3-second arrival delay join the ready queue when the others arrived together?

The Critical Section Demo: Two Threads, One Shared Variable

Must-know: Without synchronization, two threads updating a shared variable run in parallel, the output order is completion order not call order, and the final value is unpredictable; the fix is mutual exclusion via permission to enter and leave the critical section (enter/leave/synchronize).

⚠️ Top pitfall: Believing the thread called first finishes first, or that one of the printed values must be correct; neither is guaranteed without synchronization.

Self-check: Why did thread two print before thread one, and what keyword pair would make the shared value consistent?

Memory Management Requirements (Recap)

Must-know: Dynamic relocation: physical address = base + logical address, with logical < limit enforced by hardware; logical address and virtual address are the same thing.

$physical address = base + logical address$

⚠️ Top pitfall: Reading the limit register as an end address instead of a range size; the comparison is logical address >= limit, and the trap fires on the logical address before the base is added.

Self-check: With base = 1000 and limit = 2000, what happens to logical address 2100, and what is the physical address of logical 1500?

Fixed Partitioning

Must-know: Fixed partitioning wastes space inside partitions (internal fragmentation) and cannot place any process larger than the biggest partition; unequal sizes reduce but do not remove the waste.

⚠️ Top pitfall: Assuming a process larger than the largest partition can be split across partitions — it cannot; fixed partitions are contiguous and capped.

Self-check: With partitions of 2, 4, 6, 8, 12, and 16 MB, what happens to a 20 MB process, and which partition gets a 3 MB process?

Dynamic Partitioning

Must-know: Dynamic partitioning removes internal fragmentation but produces external fragmentation: holes totaling enough memory that is not contiguous; compaction (shuffle holes to one side) fixes it but is expensive and requires dynamic relocation.

⚠️ Top pitfall: Believing that 16 MB of total free space can serve a 16 MB request; external fragmentation means no single hole is big enough.

Self-check: Why can compaction only work when relocation is dynamic, and what does it produce at the end?

Fragmentation: External vs Internal

Must-know: External fragmentation: total free memory is enough but not contiguous. Internal fragmentation: allocated block is larger than the request, and the leftover inside is wasted. Compaction fixes external fragmentation only under dynamic relocation.

⚠️ Top pitfall: Confusing the two: internal fragmentation lives inside an allocated block and is not free memory at all; external fragmentation is free memory that cannot be used together.

Self-check: A 14 MB request is given a 16 MB block; which kind of fragmentation is the 2 MB, and where does it sit?

Swapping

Must-know: Swapping moves processes between main memory and a backing store; roll out swaps out the lower-priority process and roll in swaps in the higher-priority one; total transfer time is directly proportional to the amount of memory transferred.

$transfer time = \frac{image size}{transfer rate}$

⚠️ Top pitfall: Ignoring that a swap is a round trip: the full swap costs the write-out plus the read-back, so a 100 MB image at 50 MB/s costs about 4 seconds, not 2.

Self-check: What is the total transfer time to swap a 100 MB process with a 50 MB/s backing store, including both directions?

The Buddy System

Must-know: Allocation condition 2^(k-1) < x <= 2^k; split the smallest larger block until the halves are just large enough; a freed block merges only with its buddy, never with an adjacent block from a different split.

$2^{k - 1} < x \leq 2^{k}$

⚠️ Top pitfall: Merging any two adjacent free blocks after a free; only the pair that was split from the same parent can be recombined.

Self-check: After freeing C and B in the 16K trace, which adjacent free blocks merge and which stay as holes, and why?

Paging: An Introduction

Must-know: Pages belong to logical memory and frames to physical memory, with identical power-of-two sizes; pages load into any free frames, non-contiguously, which eliminates external fragmentation; the page table translates logical to physical addresses.

$page size = frame size = 2^{n}$

⚠️ Top pitfall: Requiring a process's frames to be adjacent; paging has no contiguity requirement, and any free frame is usable regardless of position.

Self-check: With 15 frames and processes of 4, 3, and 4 pages loaded, how does a 5-page process get placed?

Address Translation in Paging

Must-know: Logical address = (m - n) page-number bits + n offset bits with page size 2^n; physical address = f * 2^n + d, built by appending the frame number in front of the unchanged offset.

$P A = f \times 2^{n} + d$

⚠️ Top pitfall: Adding the offset to the frame number arithmetically as if they were plain integers; the frame number multiplies the page size first (append bits, not add numbers).

Self-check: With 1K pages and 16-bit addresses, what are the page number and offset of 1502, and the physical address if the page sits in frame 6?

Worked Problems: Paging

Must-know: Write numbers as powers of two: logical address bits = page bits + offset bits; physical address bits = frame bits + offset bits; for a decimal address, divide by the page size — quotient is the page number, remainder is the offset.

$3085 \div 1024 = 3 remainder 13 \Rightarrow page 3, offset 13$

⚠️ Top pitfall: Misreading 1 KB as 1024 bits instead of 1024 bytes, and trusting a stated offset without checking it: 3 x 1024 = 3072, so 3085 must end in offset 13, not 30.

Self-check: A logical address space has 64 pages of 1024 bytes in 32 frames: how many bits in the logical and physical addresses?

Exam Guidance Summary

Must-know: Simulator tasks: compile, load, create processes, run under the named policy, snapshot the relevant views. Scheduling: Gantt chart plus average waiting and turnaround times by hand. Threads: explain the differing shared value using synchronization and mutual exclusion.

⚠️ Top pitfall: Forgetting the snapshot per task (with a one-line explanation when needed) or assuming the simulator shows burst times — it does not, and they are given explicitly in the questions.

Self-check: Which question types are pure paperwork and do not need the simulator?

Key Industry Applications

Must-know: The lecture's techniques are live in real systems: Linux and Windows swap, the buddy system allocates kernel memory (Linux), and paging underlies virtual memory everywhere.

Self-check: Where does the buddy system appear in a modern operating system?

Previous LectureLecture 11 · Memory Management

Next LectureLecture 13 · Memory Management: Paging, Virtual Memory, Page Replacement, Segmentation, and Thrashing

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

12.1 The CPU OS Simulator: From Source Code to Running Processes

12.1.1 Compiling and Loading a Program

12.1.2 Creating Processes and Choosing a Scheduling Policy

12.1.3 The FCFS Demo, Step by Step

12.2 The Critical Section Demo: Two Threads, One Shared Variable

12.2.1 The Program

12.2.2 Running It with Round Robin

12.2.3 What the Output Shows

12.3 Memory Management Requirements (Recap)

12.3.1 The Four Requirements

12.3.2 Base and Limit Registers

12.3.3 Logical and Physical Organization

12.3.4 Logical vs Physical Addresses and Dynamic Relocation

12.4 Fixed Partitioning

12.4.1 How It Works and Its Problems

12.4.2 Queue Structures: One Queue per Partition vs a Single Queue

12.5 Dynamic Partitioning

12.5.1 Allocating on Demand: The 56 MB Walkthrough

12.5.2 Holes and External Fragmentation

12.5.3 Compaction

12.5.4 Managing the Set of Holes

12.6 Fragmentation: External vs Internal

12.6.1 Two Kinds of Waste

12.6.2 Compaction Requires Dynamic Relocation

12.7 Swapping

12.7.1 The Backing Store, Roll Out, and Roll In

12.7.2 The Cost of Swapping

12.8 The Buddy System

12.8.1 Powers of Two and the Allocation Condition

12.8.2 Worked Example: 16K Memory, Seven Processes

12.8.3 Merging: Only Buddies Combine

12.8.4 Student Questions and Answers

12.9 Paging: An Introduction

12.9.1 Frames and Pages

12.9.2 Worked Example: Allocating Pages to Frames

12.10 Address Translation in Paging

12.10.1 The Logical Address Format

12.10.2 The Translation Path

12.11 Worked Problems: Paging

12.11.1 Problem 1: How Many Bits in the Logical and Physical Addresses?

12.11.2 Problem 2: Page Number and Offset for a Decimal Address

Exam Guidance Summary

Key Industry Applications

OS Lecture 12 notes · Memory Management: Fragmentation, Swapping, Buddy System, and Paging

Sections Breakdown

Exam Revision Notes

The CPU OS Simulator: From Source Code to Running Processes

The Critical Section Demo: Two Threads, One Shared Variable

Memory Management Requirements (Recap)

Fixed Partitioning

Dynamic Partitioning

Fragmentation: External vs Internal

Swapping

The Buddy System

Paging: An Introduction

Address Translation in Paging

Worked Problems: Paging

Exam Guidance Summary

Key Industry Applications

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Sign in to use AI Chat