代写 data structure algorithm operating system security GPU Operating Systems Lecture 8a

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