Ahmad Yoosofan
University of Kashan



Feature | Fixed | Dynamic |
Partition Size | Static | Dynamic |
Fragmentation | Internal | External |
Efficiency | Low | High |











Thanks to Gemini AI for helping to create this slide
A hybrid memory allocator that balances fixed and dynamic partitioning by dividing memory into partitions of base-2 sizes (powers of 2).
Yes, absolutely! The Buddy System is not just a theoretical academic concept; it is one of the most famous and widely implemented memory management algorithms in computing history.
Here is where it has been used in the real world:
1. The Linux Kernel This is the most prominent and important modern example. The Linux operating system relies on a binary buddy allocator as its primary physical memory manager (specifically, the "page allocator").
2. Early UNIX Systems Various forms of the buddy system were used in early UNIX distributions and other historical operating systems to manage dynamic memory efficiently before modern paging hardware became universally standard.
3. Modern Memory Allocators (`jemalloc`) While user-space programming functions (like calling malloc() in a C program) don't typically use a pure buddy system today, modern high-performance allocators like jemalloc (used by FreeBSD and Facebook) use concepts directly derived from it. They group memory into distinct "size classes" and split large blocks into smaller runs, mimicking the buddy system's efficiency.
Why it survived in the real world: It survived the jump from textbooks to production kernels precisely because of the bitwise XOR math trick. When an operating system kernel is managing raw hardware memory, it has to be lightning fast. The ability to find, split, and merge free memory in $O(1)$ time—meaning it takes the exact same amount of time regardless of how much memory is installed—makes the wasted space (internal fragmentation) a completely acceptable trade-off.
Bullet list ends without a blank line; unexpected unindent.
- Memory is allocated in sizes of powers of 2 (e.g., 2, 4, 8, 16... KB).
- If a request doesn't match a power of 2, the next larger size is used.
Block quote ends without a blank line; unexpected unindent.
Bullet list ends without a blank line; unexpected unindent.
- If a block of size \(2^k\) is needed and only a \(2^{k+1}\) block is available, the OS splits it into two equal "buddies".
- When a block is freed, the OS checks if its buddy is also free.
- If both are free, they coalesce back into the larger parent block.
Block quote ends without a blank line; unexpected unindent.
Bullet list ends without a blank line; unexpected unindent.
- Pros: Very fast coalescing (merging) compared to standard dynamic partitioning.
- Cons: Suffers from Internal Fragmentation (up to 50% per block).
Process Status

Process Control Block (PCB)









address binding, loader

address binding, linker







To give your students a rich historical perspective, you can explain that Overlays emerged in the late 1950s and 1960s, an era when hardware memory was built using primitive "magnetic cores" (literally tiny metal donuts strung on wires). Because core memory was incredibly expensive—costing upwards of $1 to $2 per byte—computers had microscopic amounts of RAM compared to their massive physical size.
The method was championed by the most dominant tech titans of the 20th century across two distinct eras: the Mainframe Era and the Personal Computer (PC) Era.
---
### 1. The Mainframe Era (1960s – 1970s)
In this era, computers filled entire rooms, cost millions of dollars, yet frequently had only 16KB to 64KB of main memory.
Bullet list ends without a blank line; unexpected unindent.
NASA's early flight computers had strict weight and power limits, meaning very little memory. The Space Shuttle Primary Avionics System Software (PASS) famously relied heavily on meticulously programmed overlays to manage navigation, liftoff, and landing sequences within strict hardware constraints.
---
### 2. The Microcomputer/PC Era (1980s – early 1990s)
History repeated itself two decades later when personal computers emerged. Although microprocessor memory was cheaper, early PC architectures introduced a new artificial bottleneck: The 640KB Barrier.
Bullet list ends without a blank line; unexpected unindent.
When the IBM PC was released in 1981 running Microsoft's MS-DOS, it used the Intel 8086/8088 processor. Because of how the system architecture was designed, standard user applications were strictly limited to 640KB of "Conventional Memory". As software grew more complex, companies hit a brick wall. * Lotus Development Corporation (Lotus 1-2-3): The killer app of the 1980s was Lotus 1-2-3, a massive spreadsheet program that businesses ran on IBM PCs. To allow users to build large spreadsheets without running out of the 640KB RAM, Lotus developers manually chopped their software into overlays. The core math engine stayed in memory, while graph drawing modules, printing tools, and file import functions were kept on floppy disks and loaded dynamically into an overlay buffer. * Borland (Turbo Pascal / Turbo C): Borland was famous for its programming tools. Because compilers require multiple distinct steps (Lexical Analysis $rightarrow$ Parsing $rightarrow$ Optimization $rightarrow$ Code Generation), Borland integrated Overlay Managers directly into their compilers. A programmer writing a massive program in Turbo Pascal could simply check a box, and the Borland compiler would automatically generate the overlay tree structure for them.
---
### The Extinction of Overlays
The decline of overlays is directly tied to an engineering debate at IBM in the late 1960s. An IBM researcher named David Sayre argued that automated Virtual Memory (Paging) handled by hardware and the OS could perform just as well as, or better than, a human programmer designing complex overlay structures.
By the mid-1970s for mainframes, and the mid-1990s for PCs (with the release of Windows 95 and Linux running in Intel "Protected Mode"), Virtual Memory became standard. The OS took over memory tracking entirely, relieving programmers of the massive burden of designing overlays.
> An Anecdote for Class: > You can tell your students that in the 1980s, being an "Overlay Architect" was a highly praised, highly paid specialty skill. A single mistake in tracking your code dependencies could cause a program to overwrite its own active loop, resulting in spectacular system crashes!
سلسله مراتب حافظه

سلسله مراتب حافظه جزئیتر

حافظهٔ نهان
حافظهٔ نهان دو سطحی در یک پردازندهٔ واقعی

الگوریتم خواندن و نوشتن از حافظهٔ نهان
اگر ضریب اصابت (یا نسبت اصابت) برای پردازندهای 0.95 باشد و سرعت دسترسی به حافظهٔ اصلی 100 میکرو ثانیه باشد و سرعت دسترسی حافظهٔ نهان 1 میکرو ثانیه باشد در این صورت زمان دسترسی مؤثر برابر خواهد بود با

| ms | μs | ns | action |
| 0.5 | CPU L1 dCACHE reference | ||
| 1 | speed-of-light (a photon) travel a 1 ft (30.5cm) distance | ||
| 5 | CPU L1 iCACHE Branch mispredict | ||
| 7 | CPU L2 CACHE reference | ||
| 71 | CPU cross-QPI/NUMA best case on XEON E5-46 | ||
| 100 | MUTEX lock/unlock | ||
| 100 | own DDR MEMORY reference | ||
| 20 | 000 | Send 2K bytes over 1 Gbps NETWORK | |
| 250 | 000 | Read 1 MB sequentially from MEMORY | |
| 10 | 000 | 000 | DISK seek |
| 10 | 000 | 000 | Read 1 MB sequentially from NETWORK |
| 30 | 000 | 000 | Read 1 MB sequentially from DISK |
| 150 | 000 | 000 | Send a NETWORK packet CA -> Netherlands |


Effects on current situations







END