Loading learning content...
Every process requires a minimum number of frames simply to execute a single instruction. This isn't a recommendation or a guideline—it's an absolute architectural constraint. Give a process fewer frames than this minimum, and it cannot make progress. Not slow progress. Zero progress.
This minimum is perhaps the most critical concept in frame allocation because it defines the boundary between a functioning system and a completely stuck one. A system that allocates even one frame fewer than the minimum to any process will experience a peculiar and devastating failure: the process will repeatedly attempt instructions, fault, and restart—forever cycling without completing any work.
Understanding where this minimum comes from, how to calculate it for different architectures, and why it must be absolutely guaranteed is essential for anyone designing or debugging memory management systems.
By the end of this page, you will understand exactly what determines minimum frame requirements, be able to calculate minimums for different instruction set architectures, and deeply comprehend why this minimum is inviolable.
To understand minimum frames, we must think carefully about what happens during instruction execution.
The instruction execution cycle:
Each of these stages may access different memory locations, potentially on different pages:
If any of these pages is missing from physical memory, a page fault occurs. The processor traps to the operating system, which must locate the page on disk and load it into a physical frame. Only then can the instruction be restarted.
The problem:
If loading the required page evicts another page that the same instruction also needs, the instruction still cannot complete. It will fault again on the evicted page, potentially evicting the page just loaded. This creates a livelock—the process is running (consuming CPU for fault handling) but making zero forward progress.
Deadlock is when processes are stuck waiting for each other. Livelock is worse in a sense—processes are actively running, consuming resources, but getting nothing done. A process with insufficient frames exhibits livelock: constantly faulting, loading, evicting, and faulting again without ever completing an instruction.
The key insight:
The minimum frames requirement ensures that all pages needed simultaneously by the most demanding instruction can be resident at the same time. This is not about how many pages a process uses over its lifetime—it's about how many pages must be in memory at the same instant for any single instruction to complete.
The minimum is determined by:
The minimum frame requirement is fundamentally determined by the Instruction Set Architecture (ISA). Different design choices lead to vastly different minimums.
Factor 1: Instruction length
Some architectures have variable-length instructions that can span page boundaries:
Variable-length instructions may require two pages just for the instruction fetch.
Factor 2: Number of operands
More operands mean more potential pages:
Factor 3: Addressing modes
Complex addressing modes add page requirements:
| Feature | Simple (RISC) | Complex (CISC) | Impact |
|---|---|---|---|
| Instruction length | Fixed (4 bytes) | Variable (1-15 bytes) | +0-1 pages |
| Memory operands | 1 max per instruction | 2+ per instruction | +0-2 pages |
| Indirect levels | 1 level | Multiple levels | +0-4 pages |
| String instructions | None | REP prefix | +0-4 pages |
| Stack operations | Explicit | Implicit (CALL/RET) | +1 page |
| Typical minimum | 2-3 frames | 6-8 frames |
Factor 4: Special instructions
Some instructions are particularly demanding:
Factor 5: Interrupt handling
During any instruction, an interrupt may occur. The processor must:
Even if the main instruction needs only 2 pages, interrupt handling may need additional frames to be reserved.
RISC architectures deliberately simplified their instruction sets in part to reduce minimum frame requirements. Simpler instructions mean fewer simultaneous page needs, which improves virtual memory efficiency. CISC architectures trade this for programmer convenience and code density.
Let's work through the calculation of minimum frames for several architectures, building up from the simplest to the most complex cases.
Case 1: Simple RISC (ARM, RISC-V)
Consider a typical load instruction: LD R1, [R2]
Minimum: 2 frames
Case 2: Memory-to-Memory CISC
Consider: MOV [dest], [source]
Minimum: 4-6 frames
Case 3: x86 REP MOVSB (worst case)
This instruction copies a block of memory. Consider copying 8KB (2 pages) where both source and destination span page boundaries:
Minimum: 6 frames
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
/* * Minimum Frame Calculation for Different Architectures * * This analyzes the worst-case instruction in each architecture * to determine the minimum frame requirement. */ #include <stdio.h> typedef struct { const char *arch_name; int instruction_pages; // Pages for instruction fetch int source_operand_pages; // Pages for reading source int dest_operand_pages; // Pages for writing destination int indirect_pages; // Pages for address resolution int additional_pages; // Stack, PCB, etc. const char *worst_case_instr;} ArchMinimum; ArchMinimum architectures[] = { { .arch_name = "ARM (32-bit, ARM mode)", .instruction_pages = 1, // Fixed 4-byte instructions .source_operand_pages = 1, // LDM can load multiple, but from contiguous .dest_operand_pages = 0, // Usually register destination .indirect_pages = 0, // Limited indirect modes .additional_pages = 1, // Stack for exceptions .worst_case_instr = "LDM (load multiple)" }, { .arch_name = "RISC-V (RV64)", .instruction_pages = 1, // Fixed 4-byte (2-byte compressed) .source_operand_pages = 1, // Single memory operand .dest_operand_pages = 0, // Register destination .indirect_pages = 0, // No indirect addressing .additional_pages = 1, // Stack for exceptions .worst_case_instr = "LD (load doubleword)" }, { .arch_name = "MIPS (32-bit)", .instruction_pages = 1, // Fixed 4-byte instructions .source_operand_pages = 1, // Load/Store architecture .dest_operand_pages = 0, // Register destination .indirect_pages = 0, // No indirect modes .additional_pages = 1, // Stack .worst_case_instr = "LW (load word)" }, { .arch_name = "x86 (32-bit)", .instruction_pages = 2, // Variable length, can span .source_operand_pages = 2, // Memory operand + possible span .dest_operand_pages = 2, // Memory destination + span .indirect_pages = 1, // One level indirect .additional_pages = 1, // Stack for exceptions .worst_case_instr = "REP MOVS (block copy)" }, { .arch_name = "x86-64 (64-bit)", .instruction_pages = 2, // Variable length (prefixes add length) .source_operand_pages = 2, // Memory operand + span .dest_operand_pages = 2, // Memory destination + span .indirect_pages = 0, // RIP-relative, simpler .additional_pages = 1, // Stack (but 16 bytes now) .worst_case_instr = "REP MOVSQ (block copy)" }, { .arch_name = "VAX (historical)", .instruction_pages = 2, // Very long instructions possible .source_operand_pages = 2, // Memory operand .dest_operand_pages = 2, // Memory operand .indirect_pages = 4, // Deferred addressing (multi-level) .additional_pages = 1, // Stack .worst_case_instr = "MOVC3 with deferred operands" },}; void calculate_minimums() { int n = sizeof(architectures) / sizeof(architectures[0]); printf("Architecture Minimum Frame Analysis\n"); printf("====================================\n\n"); for (int i = 0; i < n; i++) { ArchMinimum *a = &architectures[i]; int total = a->instruction_pages + a->source_operand_pages + a->dest_operand_pages + a->indirect_pages + a->additional_pages; printf("%s:\n", a->arch_name); printf(" Worst-case instruction: %s\n", a->worst_case_instr); printf(" Breakdown:\n"); printf(" Instruction fetch: %d page(s)\n", a->instruction_pages); printf(" Source operand: %d page(s)\n", a->source_operand_pages); printf(" Destination operand: %d page(s)\n", a->dest_operand_pages); printf(" Indirect addressing: %d page(s)\n", a->indirect_pages); printf(" Exception handling: %d page(s)\n", a->additional_pages); printf(" --------------------------------\n"); printf(" MINIMUM FRAMES: %d\n\n", total); }} /* * Key insight: * * The minimum is determined by analysis of the ISA, not * observation of running programs. Even if no program ever * uses the worst-case instruction, the OS must allocate * enough frames to handle it if it occurs. * * This is a hard architectural constraint, not a tunable * parameter. */Operating systems typically add a safety margin above the theoretical minimum. If the VAX analysis suggests 11 frames, the OS might require 12 or 13 per process. This provides robustness against edge cases in the analysis.
A critical aspect of minimum frames is the instruction restart mechanism. When a page fault occurs mid-instruction, the processor must be able to restart the instruction cleanly after the page is loaded.
Requirements for restartability:
Problem: Destructive overlap
Consider an x86 REP MOVSB instruction where the source and destination regions overlap:
Source: [A][B][C][D][E][F]
↓
Destination: [X][Y][Z][A][B][C] (shifts by 3)
If a fault occurs mid-copy, some bytes have already been moved. Restarting from the beginning would copy the already-moved bytes again, corrupting the result.
Solution: Microarchitectural state
The processor maintains hidden state to enable restart:
When the instruction restarts, it resumes from where it left off, not from the beginning.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758
; Instruction Restart Example: REP MOVSB;; This demonstrates how x86 handles restartable block operations.; The instruction can be interrupted by page faults and resumed. section .text ; Copy 8KB from source to destination; ESI = source address, EDI = destination address, ECX = countcopy_block: mov esi, source_buffer mov edi, dest_buffer mov ecx, 8192 ; 8KB = 2 pages ; REP MOVSB copies ECX bytes from [ESI] to [EDI] ; After each byte: ESI++, EDI++, ECX-- ; ; If a page fault occurs: ; 1. CPU traps to OS with current ESI, EDI, ECX values ; 2. OS loads the missing page ; 3. OS restores context and re-executes the REP MOVSB ; 4. CPU sees ECX != 0, continues from current ESI/EDI ; ; The instruction "restarts" but actually continues rep movsb ret ; Problematic case: What if both pages are needed simultaneously?;; Scenario:; - source_buffer starts at page boundary - 100 bytes; - dest_buffer starts at page boundary - 50 bytes; - We're copying 200 bytes;; During copy:; - First 50 bytes: both source page 1 and dest page 1 needed; - Bytes 50-100: source page 1, dest page 2 needed; - Bytes 100-200: source page 2, dest page 2 needed;; At byte 75:; - Need: source page 1, dest page 2; - If we have only 2 frames and previously had source1 + dest1; - Loading dest page 2 might evict source page 1; - Next byte access faults on source page 1; - Loading source page 1 might evict dest page 2; - We oscillate forever!;; This is why minimum frames for REP MOVSB is 4+:; - Both source pages must be resident; - Both dest pages must be resident; - Plus instruction page; - Plus stack for exception handling section .bss source_buffer: resb 8192 dest_buffer: resb 8192From the programmer's perspective, a single instruction appears atomic. In reality, complex instructions may execute over many cycles and can be interrupted mid-execution. The processor and OS cooperate to maintain the illusion of atomicity by ensuring restartability. This requires sufficient frames.
Understanding the minimum has several practical implications for operating system design and system administration.
1. Maximum multiprogramming degree
If the system has F frames available and each process needs M minimum frames, the maximum number of concurrent processes is:
Max_Processes = F / M
For a system with 4096 frames and minimum 4 frames per process:
2. Admission control
The OS must refuse to start a new process if doing so would push existing processes below their minimum. This is a hard constraint:
if (available_frames < minimum_per_process):
deny_new_process()
3. Swap-out granularity
When reclaiming memory, the OS can swap out processes entirely but cannot reduce a running process below its minimum. This creates a binary choice—a process is either running with minimum+ frames or fully swapped out.
4. Priority and minimum
Even low-priority processes must have minimum frames when running. Priority determines which processes run, not whether running processes get sufficient frames.
The minimum is necessary but not sufficient:
Meeting the minimum ensures the process can run. It says nothing about how well it runs. A process with exactly the minimum frames will likely fault on nearly every instruction sequence, experiencing perhaps 1000x slowdown compared to adequate allocation. The minimum prevents livelock, not thrashing.
This distinction is crucial: the minimum is an architectural constraint that must never be violated, while optimal allocation is a performance goal that we strive toward.
In practice, Linux on x86-64 doesn't explicitly track minimum frames per process. Instead, it ensures processes have at least 3-4 mapped pages (instruction, stack, one data) through the vm.min_free_kbytes and watermark mechanisms. The OOM killer activates well before processes hit architectural minimums.
The challenge of minimum frames featured prominently in early virtual memory systems. Historical examples illuminate the principles.
The IBM System/360 Model 67 (1966)
One of the first commercial virtual memory systems. The 360 architecture had complex instructions that could require 8+ pages simultaneously:
IBM initially underestimated the minimum, leading to livelock situations. They revised the system to require 8 frames minimum per process.
The DEC VAX (1977)
VAX had notoriously complex instructions:
VAX required 12+ frames per process. The complexity motivated DEC's later RISC designs (Alpha).
Intel x86 (1978-present)
The x86 REP prefix instructions (MOVSB, CMPSB, SCASB, etc.) create high minimum frame requirements:
Intel documented the minimum as 6 frames for 32-bit x86.
| System | Year | Min Frames | Problematic Instructions |
|---|---|---|---|
| IBM S/360 Model 67 | 1966 | 8 | MVC, CLC, MVN |
| Multics (GE-645) | 1965 | 4 | EIS (Extended Instruction Set) |
| DEC VAX-11 | 1977 | 12+ | MOVC3, deferred addressing |
| Intel 8086/80286 | 1978 | 6 | REP prefix instructions |
| MC68000 | 1979 | 4 | MOVEM (move multiple) |
| Intel i386 | 1985 | 6 | REP MOVS, string ops |
| DEC Alpha | 1992 | 2 | RISC design, load/store only |
| ARM (32-bit) | 1985 | 3 | LDM/STM (load/store multiple) |
The RISC movement of the 1980s explicitly considered virtual memory efficiency. Simpler instructions with fixed formats and load/store architecture reduce minimum frame requirements. This was a deliberate design goal, not an accident.
While the principle of minimum frames remains unchanged, modern systems have evolved in ways that affect how we think about this constraint.
Larger pages reduce the problem
With huge pages (2 MB or 1 GB instead of 4 KB), fewer pages are needed for the same instruction:
Memory abundance changes the calculus
With gigabytes of RAM:
Virtualization adds a layer
With hypervisors and nested page tables:
Containers share frames
Containers share the kernel's page tables:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106
/* * Modern Minimum Frame Context * * This illustrates how minimum frames relate to modern * memory management features. */ #include <stdio.h>#include <stdint.h> #define PAGE_4KB 4096#define PAGE_2MB (2 * 1024 * 1024)#define PAGE_1GB (1024UL * 1024 * 1024) /* * Minimum frames with different page sizes */void analyze_page_size_impact() { printf("Impact of Page Size on Minimum Frames\n"); printf("=====================================\n\n"); // Scenario: REP MOVSB copying 16KB across page boundaries // Worst case: 6 pages needed with 4KB pages int copy_size = 16 * 1024; // 16KB printf("Copying %d bytes (worst case alignment):\n\n", copy_size); // 4KB pages int pages_4kb = (copy_size / PAGE_4KB) + 2; // Source + dest regions pages_4kb = pages_4kb * 2; // Double for source and dest pages_4kb += 2; // Instruction and stack printf(" 4KB pages: Need ~%d pages (6 minimum architectural)\n", pages_4kb); // 2MB pages // 16KB fits within a single 2MB page printf(" 2MB pages: Need 2-3 pages (source, dest, instruction likely same page)\n"); // 1GB pages printf(" 1GB pages: Need 2 pages (everything likely in same page)\n"); printf("\nConclusion: Larger pages reduce effective minimum frames.\n");} /* * Minimum frames in virtualization */void analyze_virtualization() { printf("\nMinimum Frames with Virtualization\n"); printf("===================================\n\n"); printf("Layer 1: Guest Application\n"); printf(" Sees: Guest virtual addresses\n"); printf(" Minimum: 3-6 frames (architectural)\n\n"); printf("Layer 2: Guest OS\n"); printf(" Manages: Guest physical frames\n"); printf(" Must provide: Guest's minimum\n\n"); printf("Layer 3: Hypervisor\n"); printf(" Manages: Host physical frames\n"); printf(" Sees: Guest physical = Host virtual\n"); printf(" Must provide: Guest's pages in host frames\n\n"); printf("Nested fault scenario:\n"); printf(" 1. Guest app accesses virtual address\n"); printf(" 2. Not in guest page table -> Guest OS handles\n"); printf(" 3. Guest OS loads from 'disk' (actually host memory)\n"); printf(" 4. Host memory location not mapped -> Hypervisor handles\n"); printf(" 5. Hypervisor loads actual physical page\n"); printf(" 6. Control returns up the chain\n\n"); printf("Each layer must maintain minimum for the layer above.\n");} /* * Why minimum frames rarely matter today */void modern_perspective() { printf("\nWhy Minimum Frames Rarely Limit Modern Systems\n"); printf("================================================\n\n"); // Typical modern system uint64_t ram_gb = 32; uint64_t total_pages = (ram_gb << 30) / PAGE_4KB; int min_per_process = 6; int typical_wss = 10000; // 40MB typical working set printf("System: %lu GB RAM = %lu pages (4KB)\n\n", ram_gb, total_pages); printf("Architectural minimum: %d frames/process\n", min_per_process); printf("Typical working set: %d frames/process (%.1f MB)\n\n", typical_wss, (double)typical_wss * PAGE_4KB / (1024*1024)); printf("If we allocated only minimum:\n"); printf(" Max processes: %lu (but all thrashing)\n\n", total_pages / min_per_process); printf("Practical process count (reasonable WSS):\n"); printf(" Processes: %lu (each with enough memory)\n\n", total_pages / typical_wss); printf("The minimum is so far below typical allocation\n"); printf("that it's never the limiting factor in practice.\n"); printf("Working set size dominates all allocation decisions.\n");}While understanding minimum frames is essential for OS theory and design, in practice, systems never operate near this limit. The working set size (thousands to millions of frames) dominates allocation decisions. The minimum matters for correctness proofs and extreme edge cases, but not for everyday tuning.
We've explored the concept of minimum frames in depth—the absolute lower bound below which a process cannot execute even a single instruction. This fundamental constraint shapes operating system design and proves essential for understanding virtual memory correctness.
What's next:
With minimum frames understood, we now explore the strategies for distributing frames above this minimum. The next page covers allocation strategies—equal, proportional, and priority-based approaches to dividing the frame pool among competing processes.
You now deeply understand minimum frame requirements—their architectural origin, calculation methods, and implications. This knowledge forms the foundation for understanding why certain allocation decisions are mandatory rather than optional.