Swapping

• if processes use more memory than is available => some processes are swapped to disk
• swap processes that is not currently running
• often dedicated swap area exists on disk

Managing Free Memory

Bitmaps

• Bitmap represents use of memory unit
  • 0: free
  • 1: occupied
  • optimisation: what unit size to choose
    • small: bitmap gets very large
    • big: waste space

Linked-List

• each element stores the base adress and length of the occupied memory block

Allocation Strategies

• First Fit: first segment large enough is selected | + simple & easy
• Next Fit: same as First Fit, but search continuouse where it previously left of
• Best Fit: select smallest large enough segment
  • slow
  • wastes memory because it creates many tiny useless segments
• Worst Fit: select largest segment | -> no tiny useless segments
• Quck Fit:
  • Maintains seperate List of segments of particular size
  • Finding segments of desired size very easy
  • compining segments after swapped out process very tedious

Paging vs. Swapping

• Swapping swaps the entire memory of a process
• in systems with virtual memory allocation, only single Pages are "swapped"
• only Pages the process actually needs ned to be "swapped" in

Page Fault

• happens when a process tries refer to a page that is unmapped in its page table
• Minor Page Fault: Page is in physical memory but not mapped to the process' addres space => update Page Table
• Major Page Fault: Page is not in physical memory => read page from disk
• Segmentation Fault: Page is invalid => process is killed by OS

Demand Paging

• no pages are pre-loaded into physical memory | also called lazy loading
• avoid having to load large number of potentially unnecessary pages

Page Replacement Algorithms

• Each Page Table has
  • present bit R: is page in physical memory
  • protection bits: read, write, execute
  • dirtly bit D: modified?
  • Referenced bit: page has been referenced
  • Caching disabled bit: page should not be cached | For memory mapped IO

Page Reference Bookkeeping

• R and D initially 0
• set to one if referenced or modified, respectively
• R set to 0 after each clock tick

Optimal Replacement Algorithm

• not possible | It cannot be know what pages are used in the future

Not Recently Used

• clock interrupt occurs, sort pages in classes:
  • 0: not referenced, not modified (R=0, M=0)
  • 1: not referenced, modified (R=0, M=1)
  • 2: referenced, not modified (R=1, M=0)
  • 3: referenced, modified (R=1, M=1)
• on page foult: evict a random page from lowest not empty class

FIFO

• evict page that has been the longest in memory

• easy

• no guarantee that old pages are not used heavily

Second-Chance

• FIFO but if oldes Page has R = 1
  1. set R to 0
  2. move that bage to the beginning, as if it just got loaded
  3. check for second oldes page

Clock

• clock hand advances each clock interrupt
• page fault occurs: evict Page clock hand points to if R = 0
  • otherwise: clear R and advance to next Page

Least Recently Used (LRU)

• evict page that has been unused for the longest time
• realised with linked list where most recently used page is in front

• list must be updatet at every memory reference! -> complicated, slow

Not Frequently Used (NFU)

• each page frame has a counter
• at each clock interrupt OS counter is incremented by R
• page foult: evict page with lowest counter

• in the past heavily used pages potentially never get evicted

Ageing

• each page frame has a counter
• at each clock interrupt, OS right shifts the counter value, inserts R bit on the left
• page fault. evict page with lowest counter

• Bit width of counter limits the number of clock ticks remembered

Working Set

• observation: process tends to refer to locally near subset of its memory pages => set of pages the process is currently using is called working set
• keep track of working set and always load it bevore process is run | also called prepaging

Determining Working Set

• time Bits must be added to page table, approximating last time page was referenced
• page fault:
  • for each page table with R = 1
    • R = 0 and time Bits = current time
  • for each page table with R = 0
    • time Bits > $\tau$ => page is not working set => evict
    • if time Bits > $\tau$ for no page table, evict oldest
  • if all pages tables R = 1: evict random page

WSClock

• Combination of Working Set and Clock approaches
• Page table entries organised in a circular ar list
• time Bits , R, & D needed
• page fault: page frame pointed to by the clock examined
  • R = 1: hand goes to next entry, set R to 0
  • R = 0: age is examined
    • age > $\tau \land D$ : schedule page write, hand advances
    • age > $\tau \land \neg D$ : evict page
• if a full round has been made without finding a page to evict
  • if at least one page write has been scheduled
    • advance hand further until finding page with R = 0 and D = 0
  • if no writes have been scheduled
    • select any clean page
    • if no clean page exist, write current page to disk and evict it

Thrashing

• the working set is larger than the number of page frames => very frequent page faults => slows down the process tremendously

Memory Allocation Policies

• Local page replacement: page to be evicted is selected only from the page frames of the current process
  • can result in thrashing if working set grows
  • can result in waste of memory if working set shrinks
• Global page replacement: page to be evicted is selected from all page frames
  • good if the working size varies a lot
• Periodic fixed allocation: each active process gets fixed fraction of all page frames
  • does not consider that processes can have different sizes
• Proportional allocation: page frames allocated in proportion to process size
• Adjusting based on Page Fault Frequency:
  • many page faults occur -> increase
  • few page faults occur -> decrease

Load Control

• if the system thrashes and there is no more memory availabe => swap out whole processes to disk