Operating Systems Lecture 8a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously 1 Memory management
Addressing and address spaces Partitioning and segmentation Virtual memory
Paging
Today 2
Memory management Page replacement
Recap: Virtual memory 3 Objectives
Hide physical memory
Memory protection
Illusion of unbounded memory
Logical address space
Partitioning/segmentation
Problem: Limited size of processes/segments – overlays required
Solution: Paging – we load processes only partially into memory
Recap: Paging 4 Principles
Physical memory divided in frames of equal size
Process image divided in pages of the same size
Pages loaded into frames
Secondary (swap) storage for pages that are not in memory
Recap: Paging 5 Properties
Non-contiguous allocation
Process image can be larger than available main memory Many processes can reside (partially) in memory
Invisible to user (unlike segmentation or overlays)
Data structures: Page table for each process Current frame number for each page
Free frame list
Recap: Paging model
6
Example
32 bytes of memory 4 byte page size
Pages
Frames
Recap: Translation Look-Aside Buffer (TLB) 7 Page table in main memory
Each address translation requires at least two memory accesses Translation Look-Aside Buffer
Caches page table entries
Manages entries according to a cache policy, e.g. most- or least-recently used
Recap: Translation Look-Aside Buffer (TLB) 8
Recap: Page Faults and Thrashing 9 Resident set
Pages of a process that are currently assigned to frames
Page faults
Access to a page that is currently not resident
We need to swap / “page in” that page
Thrashing
Performance degradation when there are a many page faults occurring,
i.e. when the resident set is too small
Page replacement 10 What happens on a page fault when there are no free frames?
Select a resident page to replace (evict)
Check whether it has been modified. If so, save it to secondary storage
Load page into frame
Update page table and replace
TLB entry
Objective of page replacement policies: Minimise number of page faults
Page replacement policies 11 First-In-First-Out Policy (FIFO)
Advantage: Easy to implement Replace oldest page Disadvantage: Poor performance
Remember time when page was loaded
Page replacement policies 12 Optimal Page Replacement Policy (OPT)
Replace the page that won’t be used for the longest period of time
Advantage:
Optimal, i.e. minimal number of page faults
Disadvantage: Not implementable
Page replacement policies 13 Least-Recently-Used Policy (LRU)
Remember time when page was used Replace oldest page
Page replacement policies 14 Least-Recently-Used Policy (LRU)
Advantage:
Good approximation of OPT
Disadvantage:
Need stack to avoid search to determine LRU page
Page replacement policies 15
Clock Policy
Reference bit indicates if a page was used
Circular queue of pages
Replaceifreferencebitnotset;
otherwise clear bit and check next page
Similar to FIFO, but gives a
“second chance” to often used pages
Demand-paging vs Pre-paging 16 Demand-paging
Load page when needed
Many page faults when starting a process
Pre-paging
Load potentially required pages ahead of time May load pages that are not needed
Locality of Memory Accesses 17
Working Set Model 18 W(k,t): k most recently accessed (referenced) pages at time t
Working Set Policy 19 For a given k replace a page that is not in working set at time t
Scan reference bits periodically:
We need to search all pages to find one that is not in the working set
Controlling Thrashing 20
Adaptively change k of a process
Simpler strategy based on page-fault rate
Controlling Thrashing 21
Adaptively change k of a process
Simpler strategy based on page-fault rate
Working Set Clock Policy (WSClock) 22 Current virtual time: 2204
Working Set Clock Policy (WSClock) 23 Current virtual time: 2204
No need to search all pages
Further Aspects 24
Local vs Global
Consider only frames allocated to process Consider all frames
Instructions vs Data
Different access patterns
Caching, Memory-Mapped Files and I/O No caching for I/O pages
Kernel Memory Allocation 25 E.g. Buddy System
Problem: internal fragmentation Slabs: Consider size of data structures
Memory in GPUs 26
Unified Virtual Memory 27
GPU memory mapped into virtual address space No explicit programming of data transfers
Summary
28
Memory management
Memory allocation concepts Partitioning
Segmentation
Paging – “virtual” memory implementation Page table implementation
Page replacement algorithms
Aspects to consider
Access patterns: instructions, data
Buffering, caching
Relocation, dynamic linking
Protection, fragmentation, swapping, …
Read 29 Tanenbaum & Bos., Modern Operating Systems
Chapter 3
Silberschatz et al., Operating System Concepts Chapter 8
Next Lecture
30
Introduction
Operating System Architectures Processes
Threads – Programming
Process Scheduling – Evaluation Process Synchronisation
Deadlocks
Memory Management
File Systems
Input / Output
Security and Virtualisation