Single-programming operating systems: can only run one program at a time (and generally have to memory protection). Multi-programming operating systems: can run multiple programs concurrently

Multiprogramming without memory abstraction is possible if entire program is saved on nonvolatile storage.

Volatile: memory lost when computer is powered off Non-volatile: permanent storage to preserve data

Contiguous memory #

Segmentation allocates a contiguous memory space for each process -> leads to fragmentation


  • Best fit: finds smallest free segment where segment size >= process size
  • Worst fit: largest segment >= process size. The remaining part can be used by another process hence the probability of wasting memory is less.
  • First fit: first segment which is large enough to fit the process. This saves OS from keeping ordered list of free segments
  • Next fit first fit, but keeps track of last place were it found hole and continues there

Compaction: the memory segments are shifted to merge free slots

Fixed memory blocks #

Memory is divided into blocks/pages which solves fragmentation. However we need to translate addresses now.

The memory segments of a process are divided into blocks Each block has access permissions: read, write & execute

A list of blocks for each blocks is stored in the Block Info Table.

Paging #

The memory is divided into equally sized page frames which can be filled with memory blocks called pages. Each page as a page number and page size which can be chosen by the operating system.

Logical address: location of an instruction/variable located by its page number and offset e.g. page 4 and 100 bytes offset [ 4, 100 ] (generated by the CPU)

Physical address: addresses that refer to the actual memory

Page table: table of the page number with assigned page frames and access permission for each process. A reference to it is stored inside the PCB.

Choosing a good page size is important, too big page size creates internal fragmentation were most space in pages is wasted by not being used.

Address translation: translating from logical to physical addresses

Inverted page table: one entry per page frame in real memory rather than one per virtual address space. Save lots of space since virtual memory >> real memory (especially on 64bit systems). Entires = size of RAM / page size. Looup with index does not work, TLB and hash tables are used to make the inverse lookup fast.

Virtual memory #

Virtual memory separates logical and physical memory

(Virtual) address space: a set of addresses that a process can use, each proces has its own addresses space

Page fault: when a page is referred to which is not in the memory, then it must be loaded from the disk If no page frame is free, a page must be replaced. The MMU traps the operating system to replace a page.

MMU (Memory Management Unit): Hardware that translates virtual memory addresses into physical memory addresses.

TLB (Translation Look-aside Buffers): special hardware that quickly looks up frame numbers of pages (often part of the MMU)

EAT (Effective Access Time): hit ratio * (TLB access + memory) + 1-hit-ration * (TLB access 2 * memory access). On a cache miss, 2 memory references are needed because the in-memory page table has to be read

Page replacement algorithms #

Occurs when out of frames, page must be loaded from disk.

Place replacement algorithms criteria:

  • Minimize the page faults
  • Minimize I/O operations

Page table has 3 bits:

  • P(resent) bit (or V(valid) bit) - page is in RAM (otherwise page fault)
  • M(odified) bit - page in RAM has been modified
  • R(eference) bit - page referenced since last time

Reference string: list of page numbers to evaluate performance

  • Optimal (OPT): replace page that will not be used for the longest, not possible in practise but used for measuring performance
  • Not Recently Used (NRU): R(ead) and M(odified) status bits are contained in each page table entry and periodically the R bit cleared, algorithms removes a page at random from the lowest class (classes go from not referenced, not modified to referenced, modified)
  • First-In First-Out (FIFO): pages are stored in a queue and the oldest is replaced (inefficient because old pages might still be very important)
  • Second Chance: modification of FIFO that inspects oldest page. If R is set of the last page it is moved to the front instead (given a second chance). It goes on until it finds a page, if all pages have the R bit set then the last page is removed anyways.
  • Clock: more efficient than second chance, has a hand pointer that points to oldest page in a circular list to avoid moving pages around. If the R bit is set to the pointed page is is cleared and the hand moves to the next page until a page is found with R = 0.
  • Least Recently Used (LRU): good approximation of optimal algorithm, replace page that is unused for the longest. Problem: list must be updated on every reference, special hardware required to make it fast
  • Not Frequently Used (NFU): approximation of LRU, each page as a counter associated with it and on every clock interrupt the R bit is added to. it. Now the counters roughly represent how often each page is referenced. The page with the lowest counter is chosen for replacement. Problem: never forgets anything.
  • Aging: modification to NFU, counters are shifted right 1 bit before R is added and R is added to the leftmost bit

Demand paging: pages are loaded on demand i.e. pages are only loaded when a address inside them is referenced

Working set: the set of pages that a process is currently using

Locality of reference: process reference only a small fraction of its pages during a execution phase

Trashing: when a program causes page faults every few instructions

Segmentation #

Provides multiple address spaces called segments In a 1D address space tables might "bump" into each other.

Segments do not have a fixed size leading to checkerboarding / external fragmentation where memory space is wasted in the holes between the segments. This problem can be solved using compaction.

Compaction (defragmentation): memory segments are shifted to merge free slots

Memory hierarchy #

The memory contains different levels that trade off speed vs. capacity:

  • L1 cache: fastest but smallest cache, always inside every CPU core
  • L2 cache: may be shared between all cores or each core might have its own cache
  • Random Access Memory (RAM): main memory, is lost after power off
  • Read Only Memory (ROM): cannot be changed, preset in factory
  • Persistent Memory
  • Solid State Drive (SSD): store data in (Flash) memory, much faster than hard drives but still more expensive than HDDs
  • Hard disk drive (HDD): consists of spinning disks