Object-Oriented Programming
Operating Systems
Lecture 8a
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously
Memory management
Addressing and address spaces
Partitioning and segmentation
Virtual memory
Paging
1
Today
Memory management
Page replacement
2
Recap: Virtual memory
Objectives
Hide physical memory
Memory protection
Illusion of unbounded memory
Logical address space
Partitioning/segmentation
Problem: Limited size of processes/segments – overlays required
3
Solution: Paging – we load processes only partially into memory
Recap: Paging
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
4
Recap: Paging
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
5
Recap: Paging model
Example
32 bytes of memory
4 byte page size
6
Frames
Pages
Recap: Translation Look-Aside Buffer (TLB)
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
7
Recap: Translation Look-Aside Buffer (TLB) 8
Recap: Page Faults and Thrashing
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
9
Thrashing
Performance degradation when there
are a many page faults occurring,
i.e. when the resident set is too small
Page replacement
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
10
Page replacement policies
First-In-First-Out Policy (FIFO)
Remember time when page was loaded
Replace oldest page
11
Advantage: Easy to implement
Disadvantage: Poor performance
Page replacement policies
Optimal Page Replacement Policy (OPT)
Replace the page that won’t be used for
the longest period of time
12
Advantage:
Optimal, i.e. minimal number of page faults
Disadvantage: Not implementable
Page replacement policies
Least-Recently-Used Policy (LRU)
Remember time when page was used
Replace oldest page
13
Page replacement policies
Least-Recently-Used Policy (LRU)
14
Advantage:
Good approximation of OPT
Disadvantage:
Need stack to avoid search to determine
LRU page
Page replacement policies
Clock Policy
Reference bit indicates if a page was used
Circular queue of pages
Replace if reference bit not set;
otherwise clear bit and check next page
15
Similar to FIFO, but gives a
“second chance” to often used pages
Demand-paging vs Pre-paging
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
16
Locality of Memory Accesses 17
Working Set Model
W(k,t): k most recently accessed (referenced) pages at time t
18
Working Set Policy
For a given k replace a page that is not in working set at time t
Scan reference bits periodically:
19
We need to search all pages to
find one that is not in the
working set
Controlling Thrashing
Adaptively change k of a process
Simpler strategy based on page-fault rate
20
Controlling Thrashing
Adaptively change k of a process
Simpler strategy based on page-fault rate
21
Working Set Clock Policy (WSClock)
Current virtual time: 2204
22
Working Set Clock Policy (WSClock)
Current virtual time: 2204
23
No need to search all pages
Further Aspects
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
24
Kernel Memory Allocation
E.g. Buddy System
25
Problem: internal fragmentation
Slabs: Consider size of data structures
Memory in GPUs 26
Unified Virtual Memory
GPU memory mapped into virtual address space
No explicit programming of data transfers
27
Summary
Memory management
Memory allocation concepts
Partitioning
Segmentation
Paging – “virtual” memory implementation
Page table implementation
Page replacement algorithms
28
Aspects to consider
Access patterns: instructions, data
Buffering, caching
Relocation, dynamic linking
Protection, fragmentation, swapping, …
Read
Tanenbaum & Bos., Modern Operating Systems
Chapter 3
Silberschatz et al., Operating System Concepts
Chapter 8
29
Next Lecture
Introduction
Operating System Architectures
Processes
Threads – Programming
Process Scheduling – Evaluation
Process Synchronisation
30
Deadlocks
Memory Management
File Systems
Input / Output
Security and Virtualisation