Object-Oriented Programming
Operating Systems
Lecture 7b
Dr Ronald Grau School of Engineering and Informatics Spring term 2018
Previously
Memory management
Addressing and address spaces
Partitioning and segmentation
1
Today
Memory management
Virtual memory
Paging
2
Recap: Questions
1. What is a logical address?
2. What are the two main purposes of the memory management unit?
3. Why do we have to bind or translate addresses?
4. When is address-binding during run-time mandatory?
5. Which of the techniques we know performs non-contiguous memory allocation?
6. How is access to a process’ memory partition protected?
7. What is segmentation?
8. What is internal fragmentation and when does it occur?
9. What is external fragmentation and when does it occur?
3
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
4
Solution: Paging – we load processes only partially into memory
Paging
Principles
Physical memory divided in frames of equal size power of 2, e.g. 4096 bytes
Process image divided in pages of the same size
Pages loaded into frames
Secondary (swap) storage for pages that are not in memory
5
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
6
Paging 7
Paging 8
Page table
One page table per process
Indexed by page number
Present bit (loaded?)
Frame number (if present)
Modified bit (written since loaded?)
Control and access bits (read-write-execute, kernel/user, etc)
9
Page table
Effect of page size
Equal page size: Eliminates external fragmentation
Larger page size: Larger internal fragmentation
Smaller page size: Larger page tables
Example:
4KB page size, 48 bit logical address space
8 bytes per table entry
10
512 GB just for storing the page table
Multi-Level Paging
Page table itself is paged
E.g. four levels on many Intel architectures
11
Hashed Page Table
E.g. ARM
12
Hashed Page Table
Table size ~number of used frames
E.g. Solaris on SPARC
13
Inverted Page Table
One table for all processes
E.g. Power PC
14
Translation Look-Aside Buffer (TLB)
Page table in main memory
Each address translation requires at least two memory accesses
Translation Look-Aside Buffer
Cache in MMU for page table entries
Cache policy, e.g. most recently used
Associative access
Cleared on each context switch
15
Translation Look-Aside Buffer (TLB) 16
Cache Memory and Associativity 17
Cache Memory and Associativity 18
Page Faults and Thrashing
Resident set
Pages of a process that are currently assigned to frames
Page fault
Access to a page that is not resident
need to swap in page
Which page should be replaced?
page replacement
What to do on process start?
demand vs prepaging
19
Page Faults and Thrashing
Thrashing
Performance degradation by high number of page faults,
i.e. resident set is too small
How many pages should be loaded per process?
working set
20
Shared pages
Shared memory
Shared libraries
21
Summary
Memory management
Paging
Basis for modern virtual memory systems
Page table implementations
Page tables can be large
Clever implementations are essential
Hardware support in MMU
(e.g. Translation Look-Aside Buffer)
22
Read
Tanenbaum & Bos., Modern Operating Systems
Chapter 3
Silberschatz et al., Operating System Concepts
Chapter 8
23
Homework
Start reviewing the module content we have covered thus far.
Finish remaining question sheets and exercises, if you haven’t done so already.
24
Happy Easter!
Image source: spick.ch
Next Lecture
Introduction
Operating System Architectures
Processes
Threads – Programming
Process Scheduling – Evaluation
Process Synchronisation
25
Deadlocks
Memory Management (continued)
File Systems
Input / Output
Security and Virtualisation