程序代写代做代考 data structure GPU cache file system algorithm Object-Oriented Programming

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