Memory Management

11.1 Memory Management: Module Overview

11.1.1 The Three Levels of Memory

Memory exists at three broad levels, each further from the processor and each with a different price:

1. Main memory — the working space where processes run. It is fast, but it is also expensive and small, and it is volatile: everything in it disappears when the power goes off.
2. Secondary storage (for example, a hard disk) — the parking lot that holds the programs that are waiting. It is cheap, non-volatile, and large, but much slower than main memory.
3. Tertiary storage — sits even further down the hierarchy (for example, magnetic tape or optical media). It is the slowest and cheapest level, used for archiving rather than for running programs.

The whole memory management module asks one central question: with a main memory and a secondary storage available, how do we place processes into memory?

The answer is rarely "load everything and leave it there". Memory is finite, and the set of processes that want to run at any moment usually outgrows it:

• If the memory is not enough to store everything, we have to swap the excess to the secondary storage — the process's image is written out to the disk while it waits.
• When a process is needed again, it is brought back into the main memory.

All of this — the placement of processes into memory, the swapping out of idle ones, the bringing back of needed ones — is managed by the operating system, not by the programmer. The programmer writes the program and starts it; the operating system silently decides where in memory it actually sits.

Real-world: the three levels you meet here are the coarse-grained view of a whole memory hierarchy. Real systems add even faster layers on top (registers inside the CPU, cache memory between the CPU and main memory) precisely because main memory is already too slow for the processor. Modern operating systems automate the main-memory ↔ secondary-storage traffic with a mechanism called virtual memory — the direct descendant of the swapping idea described above, and the destination this module is heading toward.

11.1.2 What the Operating System Must Provide

Managing memory is not a one-off job. Before we can say memory is being managed well, the operating system has to satisfy several requirements at once — the professor listed five, and each one gets its own treatment below:

1. Relocation — the ability to place and run a process at different locations in memory at different times.
2. Protection — keeping each process safe from the others while it resides in memory.
3. Sharing — allowing several processes to access the same portion of memory when that is wanted.
4. Logical organization — structuring how the program's modules are arranged in memory.
5. Physical organization — deciding how the program is placed into the actual physical memory hardware.

Each of these is very, very important for memory management. They are also connected: relocation and protection together build the base-and-limit-register mechanism of the next sections, sharing ties memory management back to process synchronization, and logical and physical organization define the two address spaces that the memory management unit works with.

11.2 The Five Requirements of Memory Management

11.2.1 The List of Requirements

The five requirements that memory management has to satisfy are:

1. Relocation — the ability to place and run a process at different locations in memory at different times. The location is not fixed forever: a process may be loaded, swapped out, and later reloaded somewhere else, and it must still run correctly.
2. Protection — keeping each process safe from the others while it resides in memory. One process must not be able to read or overwrite another process's memory — or the operating system's own memory.
3. Sharing — allowing several processes to access the same portion of memory when that is wanted. Protection and sharing sound contradictory, but both are needed: some regions are private, and some (shared code, shared data) are deliberately accessible to several processes at once.
4. Logical organization — structuring how the program's modules are arranged in memory. Programs are not one flat blob; they are built from separately written and separately compiled modules, and memory management must respect that structure.
5. Physical organization — deciding how the program is placed into the actual physical memory hardware. The memory hardware has its own layout, and the system has to decide how program pieces map onto it.

11.2.2 Why the List Matters

These five are not separate exam points to memorize in isolation — they interact, and the professor presented them in the order the rest of the module follows:

• Relocation and protection together give us the base and limit register mechanism. Relocation asks "where may the process sit, and how do we keep its addresses working when it moves?"; protection asks "how do we stop it from touching anything outside its region?" The answer to both fits in two registers, as the next section shows.
• Sharing connects memory management to process synchronization, which was studied earlier. The synchronization module already dealt with variables and files accessed by multiple processes; here the memory side of that story is completed — the memory manager must make the shared portion simultaneously accessible to the processes.
• Logical and physical organization set up the address spaces that the memory management unit works with. Logical organization produces the addresses the program sees; physical organization decides what those addresses mean on the real hardware. Bridging the two is the memory management unit (MMU).

11.3 Relocation and Address Binding

11.3.1 What Relocation Means

A program sitting in secondary storage has to be brought into main memory before it can be executed. There may be many processes waiting on the disk to be brought in, and the operating system has to manage both the order in which they come and the placement — where each one lands in memory. The programmer does not know any of this: the programmer simply writes the program, stores it, and later starts executing it without worrying about where it physically sits or when it is loaded.

Here is the key situation the professor built up:

1. A process P1 is brought from the hard disk into main memory and starts running.
2. If P1 is idle for some time, it is swapped back to secondary storage — moved out to make room or simply because it is not needed right now.
3. Later, when P1 is required again, it is brought back into main memory — but not necessarily at the same location. The location differs from the first load.

That is called relocation: the system loads the program or process at a different location in memory and executes it from there.

Because the location is not fixed, no one — including the operating system — knows in advance where the process will sit. When a process is brought in, the operating system first has to locate the process, then take its address and translate it into a physical memory address — the actual memory location where the process will be placed. Only then can execution continue.

11.3.2 Address Binding: Mapping One Address Space to Another

This translation from one address space to another address space is called address binding. Bringing a process from the disk into main memory is one example of the mapping; the same idea applies to data as well, since data may also reside at different places and has to be brought in for execution.

The standard reference treatment describes the journey of an address in three steps (Silberschatz, Operating System Concepts, Ch. 8):

• In the source program, addresses are purely symbolic (names like count).
• The compiler binds these symbolic addresses to relocatable addresses (for example, "14 bytes from the beginning of this module").
• The linkage editor or loader binds the relocatable addresses to absolute addresses (such as 74014).

Every one of these bindings is a mapping from one address space to another — exactly the professor's definition. The professor then notes that address binding takes place at three different stages: compile time, load time, or execution time. Compile time and execution time are terms you would have come across while doing any programming language work.

11.3.3 Compile-Time Binding

At compile time, everything about the program is known in advance. The memory location where the code will sit is also known, so the compiler generates absolute code — code with fixed, absolute addresses baked in.

The problem: if you make changes to the existing code, you have to compile it again (the professor's phrase was "decompile", meaning recompile), and the location of the code changes. Suppose the code originally started at address 1000. After the change and the recompile, it may start at a different location, say 2000. So compile-time binding produces code that is fixed to one specific place in memory — moving it would break every absolute address inside it.

11.3.4 Load-Time Binding

At load time, the compiler generates relocatable code instead of absolute code. Relocatable means the code is flexible — it can be placed anywhere in memory when it is executed. The final binding of the address is not done at compile time; the code stays in relocatable form so that the starting address may change whenever the program is reloaded into memory for execution. The actual fixing-up of the addresses happens at load time, when the loader places the code at some chosen starting address and patches the addresses accordingly.

Load time sits in between compile time and execution time. If the starting address changes between two runs, you only need to reload the code with the new start address — no recompilation is needed, unlike compile-time binding.

11.3.5 Execution-Time Binding

At execution time, the binding is delayed even further — it waits until the process is actually being executed. The process is moved into memory and executes, and the binding is done only during that execution. This is the most flexible stage: the process can even be moved from one memory segment to another while it is running, and every address still works, because the translation happens at the moment of each memory reference.

This stage needs hardware support to perform the mapping, because the base address and the limit registers can change at any moment. The base and limit registers will be examined in detail next — they are the hardware that makes execution-time binding possible.

Real-world: execution-time binding is not just a textbook idea. Modern systems randomize where a process is loaded on every run (address space layout randomization, ASLR) so that attacks cannot predict code locations — a modern security feature that is nothing but relocation in action. Dynamic linkers, which resolve shared-library addresses at load time, are load-time binding; the base/limit register machinery below is the execution-time binding mechanism.

11.4 Protection with Base and Limit Registers

11.4.1 The Idea: Every Process Must Be Safe

Protection is the second requirement of memory management. A program or process, wherever it is present in memory, should be safe — it should not get corrupted (the professor's phrasing was "it should not get corrected", meaning modified or overwritten by another process). Every process gets a separate space in memory, and the point of that separation is only safety and security.

Protection is provided with the help of two registers: the base register and the limit register. For each and every process, the system must know its base and its limit. When the operating system switches to a process, it loads that process's two values into the registers; every memory reference the process makes is then checked against them by hardware.

11.4.2 Base, Limit, and the Size of the Process

The base register always holds the starting address of the process. It is the smallest legal physical memory address for that process — and it is called the smallest precisely because it is the starting address; anything below the base belongs to another process (or to the operating system). The limit register specifies the size of the process's address range. If we add the limit to the existing base, we get the extent of the address range the process occupies — the professor writes it as the size of the process:

$$\text{size of the process}=\text{base}+\text{limit}$$

The base can change at any time because of the different types of binding we saw with relocation, so the system always checks what base plus limit is currently giving. If the process is relocated (moved), only the base value changes in the register — the limit stays the same, because the process did not change size.

11.4.3 The Address-Checking Flow

The CPU generates an address; this is called a logical address, because it is the address as seen from the user's point of view — whatever the CPU generates is a logical address. This address is fed to the hardware and checked against the base: it should not be less than the base. Only if that condition is satisfied does the check move to the next step. Otherwise, a trap is made to the system so the error can be found out.

Next, the address is checked against base plus limit: the address must stay within this limit, it should not go beyond it. If that also passes, the physical address is formed and given to the memory, where the process is placed for execution. So the legal range for an address is:

$$\text{base}\le \text{logical address}\le \text{base}+\text{limit}$$

This is exactly the mechanism in the reference text (§8.1.1): the base register holds the smallest legal physical memory address, the limit register specifies the size of the range, and the CPU hardware compares every address generated in user mode with the registers. Any attempt to access operating-system memory or another user's memory results in a trap to the operating system, which treats the attempt as a fatal error.

The professor's summary of the mechanism: "if that is the case, the space plus limit forms the physical address". Working out that phrase with the relocation-register idea from the Physical Organization section: the process's logical space starts at 0, so the physical address is formed by adding the base (the "space" start, which the professor also calls the relocatable address R) to the logical address:

$$\text{physical address}=\text{base}+\text{logical address}$$

The physical address is then handed to the memory for execution.

11.4.4 Hardware Support and Privileged Instructions

Relocation and the limit checks need hardware support — the comparisons happen on every single memory reference, so they cannot be done by software after the fact. Certain instructions are privileged instructions — they exist only to load and read the base and limit registers, and only the operating system can execute them. The reference text confirms: the base and limit registers can be loaded only by the operating system, using a special privileged instruction; since privileged instructions can be executed only in kernel mode, and only the operating system executes in kernel mode, user programs can never change the registers' contents.

The operating system has access to both the system space and the user space: the operating system space cannot be used by user programs, but the operating system can use the system space and also touch the user space when needed — it must load user programs into user memory, dump them on error, and pass parameters to system calls.

Real-world: base-and-limit protection was the classic hardware protection scheme of early operating systems, and the same idea survives in modern hardware in disguise — Intel x86 segmentation registers bound a program to a region of memory, and every modern memory management unit (MMU) enforces the same "legal range per process" idea at much finer granularity. The check flow above is also the conceptual ancestor of the bounds checks that make modern sandboxes and web browsers safe.

11.5 Sharing Memory Between Processes

11.5.1 The Requirement

The name says it: sharing means several processes try to access the same portion of memory. We already met this idea in process synchronization, where a particular variable, or a particular code, or a file is shared by multiple processes. The synchronization itself is handled separately — that was the synchronization module. But managing the memory so that such sharing is possible is one of the requirements of memory management: it allows several processes to access the same portion of memory.

There are problems when several processes access the same portion, as we saw in synchronization — two processes reading and writing the same variable can interleave in harmful ways. One simple-looking escape is to give every process a separate copy of the shared data. But a separate copy is an overhead: it occupies extra space in memory, and that space is not free. If instead we go for sharing, we have to follow some protocols to keep it safe (the locks, semaphores, and monitors of the synchronization module). Both costs are real, and the choice between them is exactly what the memory manager has to reason about.

11.5.2 Student Questions and Answers: How Sharing Actually Works

A student raised the practical doubt that sharing between threads is easy to imagine, but sharing between whole processes is harder to picture:

The misconception hiding behind this question: "processes are isolated, so sharing cannot really happen". The resolution: isolation is the default, not an absolute law. The shared portion itself must be resident in main memory, and the process carries only a reference to it. The isolation fence (base/limit protection) is deliberately widened to admit that one shared region; the memory manager sets this up when the process is loaded.

This second question is a different confusion point, and the professor's answer completes the picture: the user never moves bytes around by hand. The program declares what it wants to share; the operating system and the memory management unit arrange the physical placement and the address translation. "The reference alone is enough" — the process points at the shared region and the MMU resolves the pointing at execution time.

Real-world: this is precisely how threads in a real program share global variables (one copy of the data in the process's memory, every thread referencing it), and how memory-mapped files let different processes read the same file region without copying it. It is also exactly how shared libraries work: one copy of a DLL or a .so file sits in main memory, and dozens of processes map their references onto that single copy — saving the memory that separate copies would waste.

11.6 Logical Organization of Memory

11.6.1 Programs as Modules

Memory can be organized either logically or physically. Logical organization starts from how programs are actually written. A program is usually written as different modules, and each module is written and compiled separately, then integrated into the whole. That is a real advantage when you think of a very large program that runs in an organization or an enterprise — not a small program, but the kind of system where teams build modules and compile them independently.

Each module is self-contained enough to be compiled on its own, and the pieces are combined later. This separates the work: team A compiles the payroll module while team B compiles the inventory module, and neither waits for the other's code to exist.

11.6.2 Protection Modes and Sharing of Modules

All modules do not have to be executable by everyone. Some modules get protection in the form of modes: read only, or execute only. The protection modes are a natural extension of the base-and-limit idea: not only where a module lives in memory, but also what may be done with it — a read-only module cannot be corrupted by a misbehaving process, an execute-only module cannot be copied out as data.

Some modules might be shared among different processes. When modules are shared among processes, or when a program is divided into modules, we need segmentation: the whole program is divided into different segments, each segment is checked to see whether it is within its limit, and then execution takes place. Segmentation is a separate topic of its own that is covered later. The checks are also done against secondary storage, since segments may live there when not in use.

The reference treatment (Operating Systems: Internals and Design Principles, Ch. 7) describes the same picture: segmentation divides a program into pieces that need not all be contiguous in memory, allows each segment to be protected independently (read-only, execute-only, shared), and keeps segments on secondary storage when they are not in use — a first step toward the virtual memory ideas that come later in the course.

Real-world: every large enterprise software system is built this way — independent modules compiled separately and linked into one product, with shared libraries holding common code that all processes may read but not modify. The read-only protection on shared libraries is exactly the "read-only module" idea above, enforced by the operating system on every modern platform.

11.7 Physical Organization and Address Spaces

11.7.1 Main Memory versus Secondary Storage

Physically we have two types of memory: main memory and secondary storage. The professor lined up their differences:

• Main memory is much faster than secondary storage, but the cost is high, it is highly volatile (its contents vanish with the power), and its capacity is small.
• Secondary storage is not costly, it is non-volatile, and its capacity is large — but it is far slower.

Why go to secondary storage at all? Because some processes are not needed at all times. Those processes live in secondary memory and are later brought into main memory for execution. The programmer never deals with this memory management — it is done by the memory management unit (MMU) of the operating system. So we have to know what different address spaces exist and how the mapping between them takes place, and that leads into virtual memory.

11.7.2 Logical (Virtual) and Physical Addresses

There are two address spaces:

• The address generated by the CPU is the logical address, otherwise called the virtual address. This is the address the program thinks in terms of — the reference text notes that in the execution-time binding scheme, logical and virtual are used interchangeably.
• The physical address is the one present in the memory unit, the address seen by the memory unit itself — the address sitting in the memory address register (MAR).

The mapping between the virtual address and the physical address is done with the help of hardware — the memory management unit (MMU). The user program always deals with the logical address and never sees the real physical address. The professor's intuition, worth keeping: the user sees only logical addresses; the memory management unit does the mapping. The program can even create a pointer to location 346, store it, and manipulate it — all as the number 346 — and only when the pointer is actually used as a memory address does the hardware relocate it.

11.7.3 The Relocation Register and Dynamic Relocation

The user thinks of the process as running at locations zero to maximum: logical addresses form a range from zero up to some maximum value. For the system, the actual range starts at a base address R, the relocatable address, so the physical range given to a particular process runs from R + 0 up to R + max:

$$\text{physical address}=\text{logical address}+R$$

$$\text{logical range: }0\le \text{address}\le \text{max}\text{physical range: }R+0\le \text{address}\le R+\text{max}$$

This is the exact formulation of the reference text (§8.1.3): "We now have two different types of addresses: logical addresses (in the range 0 to max) and physical addresses (in the range R + 0 to R + max for a base value R)." The user program generates only logical addresses and thinks the process runs in locations 0 to max; these logical addresses must be mapped to physical addresses before they are used. The base register of the protection scheme is renamed in this context: it is now called the relocation register, and the scheme is called dynamic relocation.

Every time a logical address is generated, the value in the relocation register (R) is added to it, and the result is sent to memory for execution. That addition is done by the memory management unit. This is called dynamic relocation. Whenever a logical address is converted to a physical address, this type of relocation must be done; only then is the process executed in memory.

11.7.4 Worked Example: Adding the Relocation Register

Visual intuition: picture a memory strip. The relocation register R pins the process's starting point (14000) on the strip. Every logical address is a distance measured from that pin — the process "thinks" it lives at 0, 1, 2, ..., but the MMU re-anchors every reference to R + 0, R + 1, R + 2, ... . The shape is a simple linear shift: the process's image slides along the memory strip as R changes, without its internal distances changing at all.

Real-world: the logical-address view is what lets modern operating systems promise each process "you own the whole address space" while the hardware secretly places the process anywhere. Every desktop and server CPU ships an MMU that performs this addition (and much more) on every memory reference; virtual memory, the topic this module is building toward, is the generalization of exactly this two-address-space picture.

11.8 Fixed Partitioning

11.8.1 The Basic Idea

The first memory management technique is fixed partitioning. The main memory is divided into a fixed number of partitions — static partitions — and that division is generated once, when the system is formed. Whenever a process is brought into main memory, it is placed in one of the partitions. The partition's size may be the same as the process's size, or bigger, or smaller; we will see what happens in each case.

Fixed partitioning is very simple. Depending on the number of partitions, the degree of multiprogramming is set: the degree of multiprogramming means how many programs reside in memory at the same time. If ten partitions exist, at most ten programs can be in memory at a time — the reference text states this limit directly: the degree of multiprogramming is bound by the number of partitions.

Real-world: this exact scheme was used in the IBM OS 360 — multiprogramming with a fixed number of tasks. The reference text names the system: the fixed-partition method was originally used by the IBM OS/360 operating system (called MFT — multiprogramming with a fixed number of tasks); its variable-size relative, MVT, came later. Fixed partitioning is no longer in use today, but it is the right first technique to study because everything after it is a response to its weaknesses.

11.8.2 Worked Example: 8 MB Partitions and a 4 MB Process

The reference text adds the historical context: with equal-size partitions, a program too big for a partition forces the programmer to design it with overlays so that only a portion of the program need be in main memory at any one time — the programmer's manual technique that memory management later absorbed as a system responsibility.

11.8.3 Internal Fragmentation

What is internal fragmentation? When a space is allocated to a process and some part of that allocated space is left unused, the leftover is internal fragmentation. Example: a process occupies some memory and a 3 MB piece is left out within the allocated space. That 3 MB is internal fragmentation — within the allocated memory, some space is left out, and it cannot be used efficiently.

The textbook definition matches: "This phenomenon, in which there is wasted space internal to a partition due to the fact that the block of data loaded is smaller than the partition, is referred to as internal fragmentation." Note the word internal: the waste happens inside a partition that has been allocated to a process — the space is committed to that process but the process does not use it, and no other process may use it either.

11.8.4 Unequal Partitions and Queues

Equal partitions are not mandatory. With unequal partitions there is more flexibility — you can take whatever space you want. But then processes must be assigned to partitions, and we need a way to do that. Two options were discussed:

• One queue per partition. For each and every partition, form a separate queue. Whenever a small process comes, it is placed in that partition's queue; the next small process goes into the same queue. This is easy: a 2 MB process is automatically sent to the partition that fits it, and we need not worry about other spaces. But maintaining so many queues is an overhead — if processes come in many different sizes, the number of queues also becomes large. One queue per partition is not an optimal solution. Its one advantage: internal fragmentation does not arise, because each process lands in a partition matched to its size.
• A single queue. One queue is used by all processes — a 2 MB process or a 4 MB process, everything waits in the same queue, and the memory management unit takes the responsibility of finding the exact space for each process. This is the optimal solution on the queue side, but the system now has to search for the appropriate space every time.

The reference text draws the same contrast (Fig. 7.3): with one queue per partition each queue holds the processes destined for that partition, and processes are always assigned to minimize wasted memory; with a single queue, the smallest available partition that will hold the process is selected when it is time to load.

In both cases, a deeper limit remains: the number of partitions specified at system time limits the number of active processes present in the system — active meaning currently running. If ten partitions were fixed at system generation time, no more than ten processes can ever be active, no matter how much memory is actually free or how small the processes are. That limit pushes us to the next technique, dynamic partitioning.

Real-world: IBM OS/360's MFT variant is the classic commercial deployment of fixed partitioning (multiprogramming with a fixed number of tasks). The lesson survives in modern systems wherever resources are pre-partitioned — for example, cloud virtual machines sized at creation time, where an instance smaller than its allocated size still pays for (and is bounded by) the whole allocation.

11.9 Dynamic Partitioning

11.9.1 The Basic Idea

Dynamic partitioning means the partitions are of variable sizes and lengths. The exact location of each partition can be found out, and the process is placed there. The memory is carved up exactly as needed, on demand. When a process arrives, the system measures the process and cuts a partition to fit — no internal fragmentation, because the allocation matches the process.

The reference text (Operating Systems: Internals and Design Principles, §7.2) describes the technique and its history: "With dynamic partitioning, the partitions are of variable length and number. When a process is brought into main memory, it is allocated exactly as much memory as it requires and no more." The important IBM system that used it was OS/MVT (multiprogramming with a variable number of tasks).

11.9.2 Worked Example: A 56 MB Memory

11.9.3 External Fragmentation versus Internal Fragmentation

External fragmentation: within the whole memory space, the remaining free spaces are scattered as small holes, so a request whose total size could fit cannot be satisfied because no single contiguous block is big enough. In the example above: 16 MB total free, but a 14 MB request still cannot be placed — the free space exists but is chopped into 6 + 6 + 4 MB pieces.

Internal fragmentation, by contrast, happens inside a single allocated space: after the process has occupied most of a partition, a small space like 1 MB or 2 MB is left out within the requested memory. Internal fragmentation is inside the allocated block; external fragmentation is between blocks, in the free space.

11.9.4 Compaction

To overcome external fragmentation we use compaction. Compaction shuffles the spaces to any one side: move the processes toward one side of memory and bring the free spaces together on the other side, so that a large hole is formed — large enough for the incoming process. The professor's picture: move this 6 MB down, move that one up, bring this down, like a shuffle. The reference text's description is the same: "the OS shifts the processes so they are contiguous and all of the free memory is together in one block", and in the example, compaction of the 6 + 6 + 4 MB holes produces one 16 MB block — sufficient for the 14 MB process that could not fit before.

Compaction is not an easy job. It is a complex, time-consuming process — time is wasted while the memory is being reorganized. Every moved process must have its relocation register (its base address) updated to its new position, and all that copying occupies the processor. The system also has to maintain two things: the spaces already allocated (the occupied partitions) and the free partitions, which we call holes. Because of the shuffling cost, dynamic partitioning is not a very best choice for memory management, and it is one reason the course moves on to paging later.

11.9.5 Maintaining the Hole List

Whenever a process needs memory, the system searches for a hole large enough. If the hole is large enough, one part of the hole is allocated to the arriving process and the rest of the hole is returned to the set of holes — the leftover keeps its status as free memory, ready for the next request. The set of holes — the free partitions — has to be maintained by the operating system. When a process terminates, its block of memory becomes free and is also returned to the free partitions. If a returned block sits next to an already-free partition, the two can be combined into one big hole for the next process. The reference text states this merging rule explicitly: "If the new hole is adjacent to other holes, these adjacent holes are merged to form one larger hole."

Real-world: dynamic partitioning with compaction was IBM OS/MVT's technique, used primarily in batch environments. The "shuffle" still exists in modern disguise: memory compacters and heap defragmenters in managed runtimes (Java's garbage-collecting compactors, for example) move live objects together to re-create large free regions — the same trade of copying cost against fragmentation that the professor described on the board.

11.10 Dynamic Storage Allocation Schemes: First Fit, Best Fit, Next Fit, Worst Fit

11.10.1 The Four Schemes

The dynamic storage allocation can be done with one of four schemes:

1. First fit. Scan the holes from the start; allocate whichever hole is the first one big enough. Remember that "hole" is another name for a free partition. Searching can stop as soon as a large-enough free hole is found — the reference text adds that the search can start at the beginning, or at the location where the previous search ended.
2. Best fit. Search the entire list of holes; allocate the smallest hole that is big enough for the particular process. Unless the list is ordered by size, the whole list must be searched. This strategy produces the smallest leftover hole.
3. Next fit. Start scanning from the location of the last allocation; allocate the next available block, moving around the memory from there. It avoids re-scanning the front of memory on every request, the way first fit does.
4. Worst fit. Search the entire list; allocate the largest leftover hole. This strategy produces the largest leftover hole, which may be more useful than the small leftover from best fit.

We will see which one is better with an example.

11.10.2 Terminology: Holes Are Free Partitions

The word "hole" is the professor's working vocabulary for the free list: a block of memory that is not allocated to any process and is large enough to receive one. The operating system maintains the set of holes — when a process terminates, its block returns to the set, and adjacent holes merge into one larger hole, as described in the dynamic partitioning section.

11.10.3 Worked Example: Requests of 40 MB, 20 MB, and 10 MB

The professor paused during the best-fit trace to answer a student's doubt about the very first allocation:

11.10.4 Homework Problem

For practice, the professor gave a homework problem: there are six partitions, given in a fixed order, and processes of given sizes to place in the same order, using first fit, best fit, and worst fit. Try to place each process in one of the blocks under each scheme, and discuss the results in the next session.

Real-world: every memory allocator in a real system is one of these policies in disguise. The C malloc library and operating-system allocators historically used first fit or best fit; Linux's slab and buddy allocators and Java's heap managers implement sized variants of these ideas. Understanding which leftover each policy leaves behind is exactly what allocation-policy engineers reason about when they tune a memory allocator for a specific workload.

11.11 Fragmentation in General and Compaction

11.11.1 What Fragmentation Is

Fragmentation is the phenomenon in which the storage space is not used efficiently — we are not using the space properly. Because of fragmentation, the capacity of the system is reduced, and so is its performance. The professor then separated the two faces of the phenomenon:

• External fragmentation: the total memory space is enough to satisfy a request, but the space is not contiguous, so the request cannot be placed. The free memory exists, but only as scattered small holes — the 56 MB example of dynamic partitioning ended with 16 MB free and a 14 MB request still unplaceable.
• Internal fragmentation: the allocated memory is slightly larger than the requested memory; the difference in size is internal to the partition and is never used. The 4 MB process in the 8 MB fixed partition of section 11.8 wasted 4 MB this way.

The reference text quantifies how bad external fragmentation can get: statistical analysis of first fit shows that, given N allocated blocks, another 0.5N blocks are lost to fragmentation — meaning roughly one-third of memory may be unusable. This result is known as the 50-percent rule. So fragmentation is not a cosmetic problem; it can silently waste a large fraction of the machine's memory.

11.11.2 When Compaction Is Possible

To reduce external fragmentation, go for compaction: shuffle the contents, place all the allocated contents on one side and the free memory together on the other side. The simplest compaction algorithm is to move all processes toward one end of memory; all holes move in the other direction, producing one large hole of available memory.

But compaction is possible only if the relocation is dynamic — that is, if binding happens at execution time. If the binding is static — for example compile-time binding, where the code has absolute addresses — compaction is not possible, because moving the process would break its absolute addresses. Recall the three bindings from section 11.3: compile-time binding bakes absolute addresses into the binary, so shifting the process invalidates every reference; load-time binding is fixed at load and also cannot survive a move. Only execution-time binding, where the base/relocation register holds the current starting address, can track a moved process — after the move, the system simply loads the new base into the register and every address still resolves correctly.

The reference text confirms the same condition and adds the cost side: "If relocation is static and is done at assembly or load time, compaction cannot be done; compaction is possible only if relocation is dynamic and is done at execution time... This scheme can be expensive." When compaction is possible, its cost must be weighed: every moved byte is copied, every moved process's base register must be updated, and the processor is busy reorganizing memory instead of running processes — which is exactly why the course moves on to paging, where no such reorganization is ever needed.

This discussion of fragmentation leads directly into the extra topic of paging, covered in the next session.

Real-world: external fragmentation is the reason modern file systems and databases allocate space in fixed-size blocks rather than variable extents, and why virtual memory exists at all: paging lets every process's memory be non-contiguous, so free space never has to be contiguous to be useful. The 50-percent rule is also why allocators aggressively merge adjacent free regions (like the hole-merging rule of the previous section) before a compaction pass.

11.12 Assignment Workflow: The CPUOS Simulator

11.12.1 Assignment Logistics

The assignment is scheduled to start on 19 April, as per the handout. The professor plans to give a demo of the tool in the next session and will upload all references and the questions to the portal afterwards; the questions can be handed out only once the number of groups is known, so students were asked to confirm in their batch groups how many groups will do the assignment together and who will work alone.

11.12.2 What the CPUOS Simulator Is

The assignment runs on a tool called the CPUOS simulator. It occupies only a small space on your system, so it can be downloaded easily. It is called CPUOS because you can visualize the working of the CPU and the working of the operating system in parallel, side by side: the CPU side shows the instructions being executed, and the OS side shows the processes, queues, and memory structures that the instructions wake up.

11.12.3 The Working Steps

The workflow:

1. Place and compile. The source code for the question is placed in the simulator and compiled. If the code is proper, the next step happens correctly.
2. Load into memory. Loading it into memory is a button click. The load step places the compiled program, ready to run.
3. Create processes. As an example, take FCFS scheduling: create four processes, and once they are created they are placed in the queue, which can be visualized with the simulator. With the help of the boards, you can create three or four different processes; all of them appear, and each one can be clicked and inspected.
4. Observe the states. Once placed, a process sits in the ready queue. If it arrives late, it waits there; when running, the process is shown in the running state. The observations are the point of the assignment: seeing the arrival-delay effect — a process that arrives two or three seconds after the start — you can watch it wait and then move to the ready queue for execution.
5. Choose the scheduling type. The simulator offers three: FCFS, Round Robin (for which you select the time slice), and Priority scheduling (for which you fix the priority). You can also set the lifetime of a process, how many number of ticks it runs, and a delay.
6. Inspect the views. The views available in the simulator cover utilization, process states, memory, resources, and libraries, plus the process list. You can suspend the execution to see how the system looks and then continue it — so you can pause at the interesting moment and capture the screenshot.

11.12.4 Beyond Scheduling: Synchronization, Deadlocks, and the Virtual Lab

The same simulator covers not only scheduling but also synchronization and deadlocks. The lab sheet was downloaded from the platform; a reference walkthrough is available (the professor opened the deadlock example, which shows the step-by-step process), and the same procedure is used for questions on threads, synchronization, or deadlocks — only the code changes. Whatever code the assignment question gives, you enter it, compile it, and load it.

Real-world: tools like this simulator show what happens inside the CPU and OS when a program runs, which is exactly the kind of visualization used in real systems courses and in teaching operating systems in industry training — the same panels (process states, queues, utilization) that production monitoring dashboards show for real machines.

The assignment deliverable: you take screenshots of all the steps from the simulator and paste them into a PDF. For the FCFS question, the program itself is not given — you write your own small program, using the available codes as reference; the aim is only to show how FCFS works, with the burst time changed per process. For the critical-section-style questions, the code uses one variable G shared by two threads — one thread loops 5 times, the other 15 times — and the question asks whether there is a difference in the values of A and B and what the reason is, which you answer based on the concepts studied. If there is no symbol table requirement, it is not needed.

11.13 Makeup Exam Walkthrough: Scheduling and Synchronization Review

The session ended with a discussion of the makeup exam paper — the paper the student had just written — which doubled as a review of scheduling and synchronization. The professor went question by question, and each question below is a review point plus a marking lesson.

11.13.1 The Scheduling Question (Seven Marks)

The scheduling problem asked for the average waiting time, turnaround time, and waiting time, computed for a set of processes. The professor's marking rule: if everything is correct, you get the marks; if even one thing is wrong, everything is wrong — all or nothing. So the presentation matters: show the time chart (Gantt chart) and put the results in a table. Some students ran the processes separately and never showed the time chart; those answers were not credited. Two or three others appeared to follow the identical procedure, process by process — writing the first two processes, then three, then four — and were marked accordingly.

11.13.2 The Three-Mark Difference Question

A three-mark question asked for a difference between two concepts. The marking: two marks for the difference itself and one mark for examples. You should be able to give at least minimum three points plus some examples — the examples earn the third mark.

11.13.3 True or False with Justification

For the true-or-false questions, the rule is strict: writing just "true" or "false" earns nothing, and an improper justification also loses the marks. Only the first and the last statements were true — the first being that the layered approach is better, and the last concerning process states (that more than one process may be in the new state at the same time). The other statements were false, and the statements themselves made that clear. The professor went through them:

The deadlock point is worth restating: one process holds a resource, another process (or set of processes) is using a resource and waiting for the resource held by the first — circular wait — and the system grinds to a halt. This is the classic deadlock situation from the synchronization module.

11.13.4 Kernel Mode and User Mode

11.13.5 CPU Utilization: The 23% Computation

The utilization problem asked for the percentage of time the CPU is busy. The accepted answer was 23 percent. The common mistake: everyone simply added all the numbers and divided by the total — but the denominator has to be taken per process.

11.13.6 The Robust Synchronization Tool (Five Marks)

A five-mark question asked to identify the robust (strongest) synchronization tool, take an example, and explain it. The marking: one mark for identifying the tool, some two marks for the explanation, and the rest for the usage with an example; without the usage or example, at most one or two marks. One student wrote mutex and explained the log/lock times, which earned partial credit.

The review answer: among all the tools, semaphore is the preferred one. The historical line of tools: first the lock (the mutex), then hardware-based synchronization support, then the semaphore, and then the monitors — monitors are programming-based, built on an abstract data structure. Even though the semaphore cannot avoid deadlocks either, it is the simple one and it is the best among them all.

11.13.7 Process Creation and Termination (Four Marks)

The last question asked for the possible reasons for process creation and termination, worth four marks: two points plus explanation each (the professor's phrasing: "at least some two points, and then they should have explained").

Reasons for creation: the fork command, so that a child process is created; two processes that have to run concurrently; creating a duplicate of a process; or creating a new program and loading it. Reasons for termination: the process has exceeded its usage of resources; it is no longer required; or the parent exits, in which case the child also exits.

The reference text frames the same reasons: a process is created when a new batch job is submitted, when a user logs in interactively, when an OS process creates one to provide a service, or when an existing process spawns a child (in UNIX, via fork — the child is a duplicate of the parent; exec then loads a new program into the child). A process terminates when it finishes executing (normal exit), when it hits a fatal error, when it is killed by another process, or when its parent terminates.

Exam Guidance Summary

• Module weight: Memory management is a very important module. The problems connected with the techniques will be solved in the next session, after the techniques themselves.
• Scheduling questions: expect to compute average waiting time, turnaround time, and waiting time. Draw the time chart (Gantt chart) and present the results in a table — the marking is all-or-nothing: one wrong value can lose the entire seven marks. Students who ran the processes separately without showing the time chart were not credited.
• Difference questions (3 marks): give at least three points plus examples; two marks for the difference, one mark for the examples.
• True or false: always write the justification; "true"/"false" alone earns no marks. In the makeup paper only the first (layered approach is better) and the last (more than one process in the new state) were true; the statements about synchronization tools never causing deadlock, FCFS being good for interactive processes, and processor-specific queues increasing efficiency were all false.
• Utilization questions: the denominator must be taken per process — apply the per-process fraction (8 ms over the period) to every process and sum the fractions; the accepted answer was 23%. Simply adding everything and dividing once loses the marks.
• Synchronization tool questions (5 marks): the marks split as one for naming the tool, two for explanation, and two for usage with an example. The preferred tool is the semaphore; know the sequence lock (mutex) → hardware support → semaphore → monitor, and remember that even the semaphore cannot avoid deadlock.
• Process creation/termination (4 marks): two points plus explanation for each. Creation: fork command → child; concurrent execution of two processes; duplicate of a process; create a new program and load it. Termination: exceeded resource usage; no longer required; parent exits → child exits.
• Kernel vs user mode: kernel mode is executed on behalf of the system, user mode on behalf of the user.
• Homework: six partitions in a fixed order; place processes of given sizes using first fit, best fit, and worst fit; results are discussed next session.
• Assignment: starts 19 April per the handout; demo next session; questions depend on the number of groups; use the CPUOS simulator, take screenshots, paste them into a PDF; references will be uploaded on the portal and in the group.

Key Industry Applications

• IBM OS 360: the classic example of multiprogramming with a fixed number of tasks — fixed partitioning in a real commercial operating system (MFT; its variable-size relative MVT used dynamic partitioning).
• Base and limit registers / MMU: the hardware mechanism for relocation and protection is present in real CPUs; every modern system translates logical to physical addresses with a memory management unit — the same addition of a relocation register happens on every memory reference, now generalized far beyond one register.
• Shared memory: threads sharing global variables and memory-mapped files between processes work exactly as described — the shared portion must be resident in main memory and the process carries only references.
• Segmentation: large enterprise programs written as modules, compiled separately, with read-only and execute-only protections, map directly onto segmented memory models.
• CPUOS simulator: the assignment tool that visualizes CPU and operating system working in parallel — scheduling (FCFS, Round Robin with time slice, Priority), synchronization, and deadlock, with views for utilization, process states, memory, resources, libraries, and process list.
• Platify virtual lab: the online lab platform used alongside the simulator, which students had already used in the microprocessors course.
• Synchronization tools: Peterson solution, locks, semaphores, and monitors as the standard toolset used to manage shared memory access in real concurrent programs — including the warning that no tool, not even the semaphore, prevents deadlock by itself.