This is part 3 of 3 in the operating systems series. Part 1 covered understanding computers, kernels, and processes. Part 2 covered context switching, threads, mutual exclusion, and deadlocks.
Memory Management
In multi-programming systems, what was considered a large memory size five years ago is obsolete today, and what is considered large today will be obsolete in five years. There's never going to be "enough memory." Hence, to optimally use the memory space available, we need memory management.
The operating system allocates memory for running multiple programs, and needs to move data between main memory and secondary memory.
Memory Management Requirements from an OS
- Relocation — the OS is responsible for loading a process into any location in main memory, and should be able to relocate the process to a completely different section of main memory during its lifetime.
- Protection — the operating system should be the only entity allowed to access all of main memory; a process cannot access memory outside its allocation.
- Sharing — some processes may use the same code or data.
- Logical Organization — having a pre-existing set of modules, shared objects, and dynamically linked libraries should be allowed to save memory.
- Physical Organization — the OS should be able to seamlessly map logical memory to physical memory.
Logical vs. Physical Memory
The CPU's hardware memory management unit is responsible for converting a logical address to a physical address during runtime, using an offset.
Partitioning Strategies
1. Fixed Partitioning
Main memory is divided into a static number of parts. Each process is allocated one part with a size greater than or equal to what it needs.
Problems:
- Internal fragmentation (the extra, unused space left inside a partition is wasted)
- A limit on the number of processes
- In the case of unequal partitioning, which partition to use?
2. Dynamic Partitioning
Partitions are created for exactly as much memory as a process requires.
Problems:
- External fragmentation (the space left between allocations is wasted)
- Dynamic partitioning requires compact storage, which is an expensive solution
How does the OS fit the partitions?
- Best Fit — finds the partition closest in size to what's needed and allocates it. This method causes internal fragmentation.
- First Fit — allocates the first partition that fulfills the memory requirements (note: scans from the beginning of memory for every allocation). This method minimizes CPU time.
- Next Fit — allocates the next partition that fulfills the memory requirements (note: scanning starts from the previously allocated partition).
3. Buddy System
The buddy system is a compromise between fixed and dynamic partitioning. The remaining memory is divided by two in each iteration, until a best/least fit is found. This strategy makes the OS's structure much simpler, and is used by Linux.
Problem: this method causes both external and internal fragmentation.
4. Paging
In paging, memory is broken down into small, equal-sized frames, like video reels. The OS takes advantage of the fact that RAM has an access time of O(1) for any memory location.
First, the program is divided into pages, which are stored in the non-contiguous frames created. The operating system then records the frame number for each page in a page map table, which is in turn stored in the PCB.
The hardware's MMU (Memory Management Unit) needs to be able to query the page map table, so the format of the page map table has to be agreed upon beforehand.
Benefits of paging:
- No external fragmentation
- Very minimal internal fragmentation
- Easy protection
- Easy relocation
- Easy sharing
Problems with paging:
- Converting logical to physical addresses
- Dealing with very large processes
To calculate the PAGE, the standard method is to use bit shifts, since pages are always a multiple of 2. To calculate the OFFSET, the standard method is to use XOR.
PhysicalAddress = lookupInPMT(logicalAddress / pageSize) * pageSize + (logicalAddress % pageSize)
5. Segmentation
Segmentation is very similar to paging, except that in segmentation, the frames created are of unequal sizes. This makes the process less prone to fragmentation, even though converting logical to physical addresses becomes more complex.
Virtual Memory
Virtual memory always assumes paging/segmentation is valid on the system. For an application to run, all of its memory doesn't always need to be in main memory — so we swap pages of the process onto the hard drive to free up extra space.
Any running program has two types of memory sets:
- Resident Set — the parts of the process in main memory
- Working Set — the part of the process actually in use at the time
The working set is a subset of the resident set. Page faults occur when the process from the working set differs from the process in the resident set.
Benefits of page faults:
- Creates an illusion of having more memory than exists
- Can remove unused pages (flashed screens, cached memory)
- More processes can run in the system, leading to better performance
This was part 3 of a 3-part series on operating systems. Part 1 covered understanding computers, the OS, kernels, and processes. Part 2 covered context switching, threads, mutual exclusion, semaphores, and deadlocks.