Operating System - Memory Management

What is memory management?

Memory management is the functionality of an operating system which handles or manages primary memory and moves processes back and forth between main memory and disk during execution.

Process Address Space

The process address space is the set of logical addresses that a process references in its code. The operating system (MMU - memory management unit) takes care of mapping the logical addresses to physical addresses at the time of memory allocation to the program.

1. Symbolic addresses: variable names, constants in code, etc.
2. Relative addresses: compiler converts symbolic addresses to logical addresses
3. Physical addresses: loader generates these addresses when program is loaded in main memory

   e.g. the value from base register is added to logical address generated by process to figure out physical address. Let's say base register value is 10000, logical address referred by program is 100, physical address will be 10100

Static vs Dynamic Loading

• This is decided during development time of the program
• Static loading: the whole program along with external dependencies is loaded during compilation time
• Dynamic loading: compiler loads whole program without dynamic routines in the program. The dynamic routines are loaded when needed during execution time.

  Example: Java reflection - dynamic class loading with example

Swapping

Swapping is a mechanism in which a process can be swapped temporarily out of main memory (or move) to secondary storage (disk) and make that memory available to other processes. At some later time, the system swaps back the process from the secondary storage to main memory.

Fragmentation

As processes are loaded and removed from memory, the free memory space is broken into little pieces. It happens after sometimes that processes cannot be allocated to memory blocks considering their small size and memory blocks remains unused. This problem is known as Fragmentation.

1. External fragmentation: have enough memory but not contiguous block so can't use it
2. Internal fragmentation: allocated bigger memory block to process and can't use the unused memory for others

Paging

A computer can address more memory than the amount physically installed on the system. This extra memory is actually called Virtual Memory and it is a section of a hard disk that's set up to emulate the computer's RAM.

• process is broken in blocks of same size called Pages
• main memory is divided in blocks of size of pages, called Frames

Address Translation

• Logical Address = Page number + page offset
• Physical Address = Frame number + page offset

Segmentation

• similar to paging but variable size Segments rather than pages

Virtual Memory

A computer can address more memory than the amount physically installed on the system. This extra memory is actually called virtual memory and it is a section of a hard disk that's set up to emulate the computer's RAM.

commonly implemented by demand paging or demand segmentation

Demand Paging

A demand paging system is quite similar to a paging system with swapping where processes reside in secondary memory and pages are loaded only on demand, not in advance.

When a context switch occurs, the operating system does not copy any of the old program’s pages out to the disk or any of the new program’s pages into the main memory Instead, it just begins executing the new program after loading the first page and fetches that program’s pages as they are referenced.

Page Fault: While executing a program, if the program references a page which is not available in the main memory because it was swapped out a little ago, the processor treats this invalid memory reference as a page fault and transfers control from the program to the operating system to demand the page back into the memory.

Page Replacement Algorithms

Page replacement algorithms are the techniques using which an Operating System decides which memory pages to swap out, write to disk when a page of memory needs to be allocated.

When the page that was selected for replacement and was paged out, is referenced again, it has to read in from disk, and this requires for I/O completion. This process determines the quality of the page replacement algorithm: the lesser the time waiting for page-ins, the better is the algorithm.

1. Reference String Algorithm

   • The string of memory references is called reference string. Reference strings are generated artificially or by tracing a given system and recording the address of each memory reference.
   • For a given page size, we need to consider only the page number, not the entire address.
   • If we have a reference to a page p, then any immediately following references to page p will never cause a page fault.
   • For example, consider the following sequence of addresses − 123,215,600,1234,76,96 If page size is 100, then the reference string is 1,2,6,12,0,0

2. First In First Out (FIFO) Algorithm

3. Optimal Page Algorithm

   • lowest page fault algorithm
   • this exists and is called OPT or MIN
   • replace a page that will not be used for longest of time. Use the time when page is to be used

4. Least Recently Used (LRU) Algorithm

5. Page Buffering Algorithm

   • To get a process start quickly, keep a pool of free frames.
   • On page fault, select a page to be replaced.
   • Write the new page in the frame of free pool, mark the page table and restart the process.
   • Now write the dirty page out of disk and place the frame holding replaced page in free pool.

6. Least Frequently Used (LFU) Algorithm

   • The page with the smallest count is the one which will be selected for replacement.
   • This algorithm suffers from the situation in which a page is used heavily during the initial phase of a process, but then is never used again.

7. Most Frequently Used (MFU) Algorithm

   • This algorithm is based on the argument that the page with the smallest count was probably just brought in and has yet to be used.

Image courtesy: https://www.tutorialspoint.com/operating_system/os_memory_management.htm