Transcript COSC 243

NETW3005
Virtual Memory
Reading
• For this lecture, you should have read
Chapter 9 (Sections 1-7).
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
2
Last lecture: Memory management
• Context
– primary, secondary storage
– memory access by processes
•
•
•
•
Logical and physical addresses
Memory allocation & fragmentation
Paging
Segmentation
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
3
This lecture: Virtual memory
•
•
•
•
Demand paging
Page replacement algorithms
Frame allocation
Thrashing
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
4
Swapping: A recap
• In the last lecture we introduced the
idea of swapping processes in and out
of main memory, in synchrony with CPU
scheduling.
• Swapping allows more processes to
multitask at any given time.
• Runtime binding makes swapping
easier.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
5
Partially loaded processes
• Advantages of allowing programs to
execute without being fully in memory.
– Dynamic loading/linking: sharing of common
language library routines, ease of upgrading etc.
– It should be possible to increase the number
of processes being multitasked.
– It will be quicker to swap processes in and
out of memory during multitasking.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
6
The Virtual Memory concept
• The paradigm of Virtual Memory (VM)
takes the idea that a process doesn’t
need to be fully in memory in order to
run to its logical conclusion.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
7
VM techniques
• Provide ways of automating the loading
of processes while they execute.
• The programmer deals with a logical
memory just as in paging scheme.
• The memory manager is not only in
charge of mapping logical addresses to
physical addresses, but also of actually
loading physical addresses into main
memory from the backing store.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
8
Demand paging
page0
page1
CPU
page2
page3
0
1
2
3
1
4
3
6
v
v
v
v
page table
0
1
2
3
4
5
6
page0
page2
page1
page3
memory
You can go further – only load a page
when the CPU references it.
You can easily use a paging scheme to
implement swapping.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
9
Implementing Demand Paging
• Page table entries typically contain
additional information.
– Valid/invalid bit: used to indicate whether
the page number referred to by a process is
inside its allocated number of pages.
– Protection bit: e.g. read-write / read only.
• The valid/invalid bit is often used to
specify whether a page has been loaded.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
10
An example of Demand Paging
A
B
C
D
logical
memory
NETW3005 (Operating Systems)
0
0 4 v
i
1
2 6 v
i
3
i
4
i
5
page table
1
2
3
4 A
A
B
C
D
5
6 C
physical
memory
Lecture 08 - Virtual Memory
backing
store
11
Note
• There are now two reasons for the invalid
bit.
• There is duplication of data in the system,
e.g. A is represented in two places.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
12
Page Faults
• Accessing an invalid page in the table
results in a trap to the operating system.
• The operating system determines the
cause of the trap:
– Invalid memory access? Terminate.
– Page not loaded? Page fault.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
13
Dealing with a page fault
• Find a free frame in main memory.
• Schedule a disk operation to read the
desired page into this frame.
• Modify the page table appropriately.
• Restart the instruction. (It’s crucial that
the process is restarted in exactly the
state that generated the fault).
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
14
Performance of Demand Paging
• On average, how long does it take to
access a memory location in a demand
paging system?
• What are the relevant factors?
– memory access time (ta);
– page fault time (tf)
– probability of a page fault (p)
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
15
Effective access time
(1-p) x ta + p x tf
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
16
Acceptable page fault rates
• Total page fault time (including
hardware and software processes) is
typically around 25 milliseconds.
• Memory access time is typically
between 10 and 200 nanoseconds.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
17
Exercise
• What is the effective access time for a
machine with a page fault probability of
1%, memory access time (ta) of 100
nanoseconds, and a page fault (tf) time
of 25 milliseconds?
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
18
Answer
= (1-p) x ta + p x tf
= (0.99 x 100 + (0.01 x 25,000,000)
= 250,000 ns
Compared to the access time assuming no
paging (100 ns), this rate of paging slows the
system down by a factor of 2500!
Lesson: for efficient paging, faults need to be
very rare.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
19
Page replacement algorithms
• If main memory is full when a page fault
is generated, one of the pages currently
being held needs to be replaced.
• This means an extra step in the
operating system’s page-servicing
routine.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
20
Find a free frame of memory.
• If there’s a free frame in memory, use it.
• Otherwise:
– Select a frame to swap out.
– Save it to the backing store (why?)
– Proceed as before.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
21
Page replacement algorithms
• There are various methods for deciding
which page to swap out.
• These are usually evaluated with respect
to a reference string of page requests and
a memory consisting of a small number of
frames (we will use three).
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
22
FIFO page replacement
• Ok, so how does this work?
7
0
1
2
0
3
0
4
2
3
7
7
0
7
0
1
2
0
1
2
0
1
2
3
1
2
3
0
4
3
0
4
2
0
4
2
3
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
23
Advantages and disadvantages
• Advantages
– simple to understand and implement.
• Disadvantages
– maybe the first page to be referenced is
referenced often
– Note also Belady’s anomaly — increasing
the allocation may increase the number of
page faults.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
24
Optimal Page Replacement
• What would this algorithm be?
• Replace the page that will not be used
for the longest amount of time.
7
0
1
2
0
3
0
4
2
3
7
7
0
7
0
1
2
0
1
2
0
1
2
0
3
2
0
3
2
4
3
2
4
3
2
4
3
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
25
Advantages / disadvantages
• Advantages?
– Obvious – the algorithm is optimal.
• Disadvantage?
– Similar to SJF scheduling – you can’t
predict the future reference string (just as
you can’t predict future CPU burst times).
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
26
LRU Page Replacement
• What would this algorithm be?
• Replace the page that has not been
used for the longest period of time.
7
0
1
2
0
3
0
4
2
3
7
7
0
7
0
1
2
0
1
2
0
1
2
0
3
2
0
3
4
0
3
4
0
2
4
3
2
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
27
Advantages / disadvantages
• Advantage
– It’s optimal if you look backward in time,
rather than forward.
• Disadvantage
– It’s time-consuming to keep a record of last
use for each page.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
28
What assumption are we making?
• That future memory references are
going to be resemble past ones. Again,
note similarity with SJF.
• However note the logical independence
of CPU burst times and memory
reference patterns.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
29
LRU Approximation Hardware (1)
• How to keep a record of the leastrecently used page?
– Provide a ‘time-used’ field in the page
table.
– Keep a queue of page numbers, and move
a page to the back of the queue each time
it’s referenced.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
30
LRU Approximation Hardware (2)
• How to keep a record of the leastrecently used page?
– Associate several reference bits with each
page.
– Associate one reference bit with each page.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
31
Frame allocation algorithms
• It makes sense not to allocate a very
small number of frames to a process.
• In fact, for any given machine there is a
minimum number of frames that must
be allocated to a process — the
maximum number of memory locations
that can be accessed in a single
instruction.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
32
Frame distribution algorithms
• Equal allocation
• Proportional allocation
• Local vs global replacement schemes
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
33
Thrashing
• A process is thrashing if it’s spending
more time paging than executing.
• Thrashing occurs when a process has
not been allocated sufficient frames.
– A page fault occurs, requiring a page to be
replaced.
– The replaced page is itself needed shortly
thereafter.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
34
Thrashing in more detail
1. There are too many processes sharing the
CPU.
2. The processes all start to thrash.
3. The CPU becomes relatively idle.
4. The scheduler detects this, and increases
the degree of multiprogramming.
5. Whoops. . .
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
35
The locality model of execution
• Keep track of which and how many
frames a process is currently using.
• It is possible to identify particular groups
of pages which are used together.
• A locality is defined e.g. by a subroutine
that regularly refers to a particular set of
variables.
• Localities can overlap with one another.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
36
The Working Set model
• We define a parameter ∆ representing
the working set window – the most
recent ∆ page references.
• The working set is the set of pages
referenced within the working set window.
• The idea is to ensure that each process is
allocated enough frames to store its
current working set.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
37
When do you load pages?
• Pure demand paging. None of a
process’ pages are loaded until
referenced.
• Disadvantages of this scheme?
– You get loads of page-faults at the start of
a process’ execution.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
38
When do you load pages?
• Prepaging
– When a process is suspended, we remember
its current working set.
– When it is restarted, we bring all the pages in
its working set back into memory straight
away.
– This is only a win if a reasonable proportion
of these pages are subsequently referenced.
NETW3005 (Operating Systems)
Lecture 08 - Virtual Memory
39
Next Lecture
File System Interface
Chapter 10 (Sections 1-5)
Chapter 11 (Sections 1-4)