Transcript Week-14

Chapter 9: Virtual Memory
Operating System Concepts with Java – 8th Edition
9.1
Silberschatz, Galvin and Gagne ©2009
Chapter 9: Virtual Memory
 Background
 Demand Paging
 Copy-on-Write
 Page Replacement
 Allocation of Frames
 Thrashing
Operating System Concepts with Java – 8th Edition
9.2
Silberschatz, Galvin and Gagne ©2009
Objectives
 To describe the benefits of a virtual memory system
 To explain the concepts of demand paging, page-replacement
algorithms, and allocation of page frames
 To discuss the principle of the working-set model
Operating System Concepts with Java – 8th Edition
9.3
Silberschatz, Galvin and Gagne ©2009
Background
 Chapter 8 discussed separation of logical memory
from physical memory

Used page tables and TLBs for address translation

Assumption – Entire address space should be in main
memory before process can begin execution

Dynamic loading addressed this. But needed user to
manage the loading process
 Virtual memory takes this separation to its logical
conclusion
 Allows a program to be executed even when part of
process’s address space is in main memory
Operating System Concepts with Java – 8th Edition
9.4
Silberschatz, Galvin and Gagne ©2009
The Case for Virtual Memory
 Programs have code for error conditions that are
seldom used
 Programs have features that are seldom used
 Programmers allocate way too much memory than
needed

Create a 100X100 array when only 10X10 is needed
 Advantages of virtual memory

Program no longer constrained by physical memory size

More processes can be in physical memory thereby
increasing system performance

Less I/O for swapping

Makes programmers task easier
Operating System Concepts with Java – 8th Edition
9.5
Silberschatz, Galvin and Gagne ©2009
Virtual Memory That is Larger Than
Physical Memory
Operating System Concepts with Java – 8th Edition
9.6
Silberschatz, Galvin and Gagne ©2009
Virtual Address Space
 Virtual address space – Logical view of how process
is stored in main memory
 The virtual address space is again contiguous (recall
logical address space is always contiguous)
 Physical memory organized as frames
 Holes in virtual address spaces – the blank space
between stack and heap
 Physical memory allocated only if heap or stack
grows
 Virtual address space with holes referred to as
sparse spaces
Operating System Concepts with Java – 8th Edition
9.7
Silberschatz, Galvin and Gagne ©2009
Virtual-address Space
Operating System Concepts with Java – 8th Edition
9.8
Silberschatz, Galvin and Gagne ©2009
Advantages of Virtual Address Space
 Efficient process creation (less space is allocated at
the beginning)
 System libraries can be shared by mapping the
libraries to virtual address space
 Virtual memory also helps in sharing memory space
between processes

Shared memory is a mechanism for cooperating processes
to communicate
 Allows memory sharing when forking – efficient
process creation
Operating System Concepts with Java – 8th Edition
9.9
Silberschatz, Galvin and Gagne ©2009
Shared Library Using Virtual Memory
Operating System Concepts with Java – 8th Edition
9.10
Silberschatz, Galvin and Gagne ©2009
Demand Paging
 Bring a page into memory only when it is needed

Less I/O needed

Less memory needed

Faster response

More users
 Page is needed  reference to it

invalid reference  abort

not-in-memory  bring to memory
 Lazy swapper – never swaps a page into memory unless page will be
needed

Swapper that deals with pages is a pager
Operating System Concepts with Java – 8th Edition
9.11
Silberschatz, Galvin and Gagne ©2009
Demand Paging
 Virtual memory can be implemented via Demand Paging
or Demand Segmentation
 Bring a page into memory only when it is needed

Till then it resides in secondary memory

Pages that are never used (such as error handling code) never
brought into main memory
 Similar to swapping

Swapping operates at granularity of entire address spaces

On-demand paging operates at granularity of pages/frames
 Lazy swapper – never swaps a page until it is needed
 Swapper that operates at granularity of pages is called
Pager
Operating System Concepts with Java – 8th Edition
9.12
Silberschatz, Galvin and Gagne ©2009
Transfer of a Paged Memory to
Contiguous Disk Space
Operating System Concepts with Java – 8th Edition
9.13
Silberschatz, Galvin and Gagne ©2009
Basic Concepts
 At process swap-in time pager makes informed guess on
which pages will be used before process is swapped out
 Only those pages are brought into main memory

More efficient– reduces process swap time
 Other pages are obtained on demand
 We need a mechanism to check whether page is in main
memory or on disk

Done with hardware support
 Valid and invalid bits
Operating System Concepts with Java – 8th Edition
9.14
Silberschatz, Galvin and Gagne ©2009
Valid-Invalid Bit
 With each page table entry a valid–invalid bit is associated
(v  page is legal and in-memory, i  page is illegal or not inmemory)
Frame #
valid-invalid bit
v
v
v
v
i
….
i
i
page table
 During address translation, if valid–invalid bit in page table entry
is I page fault occurs
Operating System Concepts with Java – 8th Edition
9.15
Silberschatz, Galvin and Gagne ©2009
Page Table When Some Pages Are
Not in Main Memory
Operating System Concepts with Java – 8th Edition
9.16
Silberschatz, Galvin and Gagne ©2009
How to Handle Page Fault
 Page fault traps into OS
1. Operating system looks at another table to
decide:
- Invalid reference  abort
- Just not in memory
2. Get empty frame
3. Swap page into frame
4. Reset tables
5. Set validation bit = v
6. Restart the instruction that caused the page fault
Operating System Concepts with Java – 8th Edition
9.17
Silberschatz, Galvin and Gagne ©2009
Steps in Handling a Page Fault
Operating System Concepts with Java – 8th Edition
9.18
Silberschatz, Galvin and Gagne ©2009
Performance of Demand Paging
 Page Fault Rate 0  p  1.0

if p = 0 no page faults

if p = 1, every reference is a fault
 Effective Access Time (EAT)
EAT = (1 – p) x memory access
+ p (page fault overhead
+ swap page out
+ swap page in
+ restart overhead)
Operating System Concepts with Java – 8th Edition
9.19
Silberschatz, Galvin and Gagne ©2009
Demand Paging Example
 Memory access time = 200 nanoseconds
 Average page-fault service time = 8 milliseconds
 EAT = (1 – p) x 200 + p (8 milliseconds)
= (1 – p) x 200 + p x 8,000,000
= 200 + p x 7,999,800
 If one access out of 1,000 causes a page fault, then
EAT = 8.2 microseconds.
This is a slowdown by a factor of 40!!
Operating System Concepts with Java – 8th Edition
9.20
Silberschatz, Galvin and Gagne ©2009
Process Creation

Virtual memory allows other benefits during process creation:
- Copy-on-Write
- Memory-Mapped Files (later)
Operating System Concepts with Java – 8th Edition
9.21
Silberschatz, Galvin and Gagne ©2009
Copy-on-Write
 Mechanism for improving efficiency of process creation
via fork()
 Copy-on-Write (COW) allows both parent and child
processes to initially share the same pages in memory
 If either process modifies a shared page, only then is the
page copied
 COW allows more efficient process creation as only
modified pages are copied
 Free pages are allocated from a pool of zeroed-out
pages
 Vfork() – Does not use COW. Changes made by child
visible to parent
Operating System Concepts with Java – 8th Edition
9.22
Silberschatz, Galvin and Gagne ©2009
Before Process 1 Modifies Page C
Operating System Concepts with Java – 8th Edition
9.23
Silberschatz, Galvin and Gagne ©2009
After Process 1 Modifies Page C
Operating System Concepts with Java – 8th Edition
9.24
Silberschatz, Galvin and Gagne ©2009
What happens on Page Fault?
1. Find the location of the desired page on disk
2. Find a free frame:
- If there is a free frame, use it
- If there is no free frame, use a page
replacement algorithm to select a victim frame
3. Bring the desired page into the (newly) free frame;
update the page and frame tables
4. Restart the process
Operating System Concepts with Java – 8th Edition
9.25
Silberschatz, Galvin and Gagne ©2009
What happens if there is no free frame?
 Find some page in memory, but not really in use
and swap it out
 The page that is selected for swap-out is called the
victim
 Performance optimizations
 Avoid two page transfer costs by having a dirty bit

Only dirty pages are written back
 Reducing the need for swap-in/swap-out

Reduce the page-fault rate
Operating System Concepts with Java – 8th Edition
9.26
Silberschatz, Galvin and Gagne ©2009
Need For Page Replacement
Operating System Concepts with Java – 8th Edition
9.27
Silberschatz, Galvin and Gagne ©2009
When Does Page Faults Occur?
 First time a frame is used – Mandatory page fault

Little opportunity for optimization
 Page fault on subsequent accesses

Page was swapped out between accesses to make room
for an incoming page

Having smart victim selection schemes can help reduce
these faults
 Page replacement policy defines how the victim is
selected

Completes the separation between logical and physical
memories
Operating System Concepts with Java – 8th Edition
9.28
Silberschatz, Galvin and Gagne ©2009
Page Replacement
Operating System Concepts with Java – 8th Edition
9.29
Silberschatz, Galvin and Gagne ©2009
Page Replacement Algorithms
 Goal Minimize page-fault rate
 How to evaluate page replacement algorithms
 Simulation using memory access trace files
 Memory addressed can be translated to page
numbers – page access string
 In all our examples, the reference string is
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
Operating System Concepts with Java – 8th Edition
9.30
Silberschatz, Galvin and Gagne ©2009
Graph of Page Faults Versus
The Number of Frames
Operating System Concepts with Java – 8th Edition
9.31
Silberschatz, Galvin and Gagne ©2009
FIFO Page Replacement
 Replace the page that was swapped-in the earliest
Operating System Concepts with Java – 8th Edition
9.32
Silberschatz, Galvin and Gagne ©2009
FIFO
 Easy to implement
 Poor performance – high page fault rate
 FIFO also suffers from another problem called
Belady’s anamoly
 Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
 Page faults when # of frames is 3: 9
 Page faults when # of frames is 4: 10
 Belady’s Anomaly: More frames can actually
result in higher page faults for certain access
patters
Operating System Concepts with Java – 8th Edition
9.33
Silberschatz, Galvin and Gagne ©2009
FIFO Illustrating Belady’s Anomaly
Operating System Concepts with Java – 8th Edition
9.34
Silberschatz, Galvin and Gagne ©2009
Optimal Algorithm
 Replace page that will not be used for longest period of time
 4 frames example
 Provably optimal
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1
4
2
6 page faults
3
4
5
 Problem: How to know which page is not going to be used for
longest time?
 Used for as a baseline for measuring performance of other
algorithms
Operating System Concepts with Java – 8th Edition
9.35
Silberschatz, Galvin and Gagne ©2009
Optimal Page Replacement
Operating System Concepts with Java – 8th Edition
9.36
Silberschatz, Galvin and Gagne ©2009
Least Recently Used Algorithm
 Replaces the frame that has not been used for the
longest time
 Based on the assumption that page that has not been
used for longest time will not be used in the near
future
 Does not suffer from Belady’s anomaly
Operating System Concepts with Java – 8th Edition
9.37
Silberschatz, Galvin and Gagne ©2009
LRU Page Replacement
Operating System Concepts with Java – 8th Edition
9.38
Silberschatz, Galvin and Gagne ©2009
LRU Algorithm Implementation
 Counter implementation: Keep track of time the page
was last used (e.g., have additional field in page
table)
 Requires searching for finding the victim
 Stack implementation – keep a stack of page
numbers in a double link form:

Page referenced:
move
it to the top
requires

6 pointers to be changed
No search for replacement
Operating System Concepts with Java – 8th Edition
9.39
Silberschatz, Galvin and Gagne ©2009
Use Of A Stack to Record
the Most Recent Page References
Operating System Concepts with Java – 8th Edition
9.40
Silberschatz, Galvin and Gagne ©2009
LRU Approximation Algorithms
 Use reference bit associated with page table
 One-Reference bit



With each page associate a bit, initially = 0
When page is referenced bit set to 1
Replace the one which is 0 (if one exists)
 We do not know the order, however
 Additional reference bit algorithm



Keep a byte for ever entry in page table
Move the bit from page table to MSB of the
corresponding byte
Replace the page with smallest integer (there could
be many)
Operating System Concepts with Java – 8th Edition
9.41
Silberschatz, Galvin and Gagne ©2009
Second-Chance Algorithm
 Special case of Additional-reference bit algorithm
 Uses the reference bit in the page table
 Clock replacement – Maintain page references in a
circular queue
 Pointer or clock handle always points to the next page
that needs to be considered for replacement
 On page fault check the reference bit of the page
 If reference bit is zero, replace the page
 If reference bit is 1 then:
 Set reference bit 0
 Do not replace
 Move to the next page and apply the same rules
Operating System Concepts with Java – 8th Edition
9.42
Silberschatz, Galvin and Gagne ©2009
Second-Chance (clock)
Page-Replacement Algorithm
Operating System Concepts with Java – 8th Edition
9.43
Silberschatz, Galvin and Gagne ©2009
Counting Algorithms
 Keep a counter of the number of references that
have been made to each page
 LFU Algorithm: replaces page with smallest count
 MFU Algorithm: based on the argument that the
page with the smallest count was probably just
brought in and has yet to be used
Operating System Concepts with Java – 8th Edition
9.44
Silberschatz, Galvin and Gagne ©2009
Allocation of Frames
 How many frames to allocate to each process?
 Conditions:

Total # of allocated frames over all processes < # of
available frames

Each process needs minimum number of pages
 Recall that instruction that caused page fault will
have to be restarted
 Avoid multiple restarts of instruction
 Determined by instruction set

Number of memory location than can be accessed in the
instruction

Level of indirections allowed
Operating System Concepts with Java – 8th Edition
9.45
Silberschatz, Galvin and Gagne ©2009
Equal Allocation
 All processes get the same number of frames
 Easy to implement
 Poor performance – One process could be
wasting memory when another is short on
memory
Operating System Concepts with Java – 8th Edition
9.46
Silberschatz, Galvin and Gagne ©2009
Proportional Allocation
 Proportional allocation – Allocate according to the
size of process
si  size of process pi
S   si
m  total number of frames
s
ai  allocation for pi  i  m
S
m  64
si  10
s2  127
10
 64  5
137
127
a2 
 64  59
137
a1 
 Better performance
Operating System Concepts with Java – 8th Edition
9.47
Silberschatz, Galvin and Gagne ©2009
Global vs. Local Allocation
 Page replacement has an impact on page allocation
 Global replacement – process selects a
replacement frame from the set of all frames; one
process can take a frame from another

# of frames allocated to a process can change over time

Memory reference pattern of one process can affect
performance of another process
 Local replacement – each process selects from
only its own set of allocated frames

# of frames allocated to a process remains constant

Restricts opportunities for dynamic optimization
Operating System Concepts with Java – 8th Edition
9.48
Silberschatz, Galvin and Gagne ©2009
Thrashing
 If a process does not have sufficient number of
frames it constantly page faults
 High page fault rates leads to low performance
 High paging activity is called Thrashing
 A process that is thrashing spends more time
paging than actual execution
Operating System Concepts with Java – 8th Edition
9.49
Silberschatz, Galvin and Gagne ©2009
Self Perpetuating Phenomenon
 In early batch systems, if CPU utilization is too low
OS increases degree of multi-programming
 Global replacement is used – replaces page
without regard to the process to which it belongs
 One processes needs more frames
 It faults and takes sway frame from other
processes
 These other processes see increase faulting and
queue up at the pager
 CPU scheduler sees lower CPU utilization and
further increases degree of multi-programming
Operating System Concepts with Java – 8th Edition
9.50
Silberschatz, Galvin and Gagne ©2009
Thrashing (Cont.)
Operating System Concepts with Java – 8th Edition
9.51
Silberschatz, Galvin and Gagne ©2009
How to Avoid Thrashing?
 Use local replacement instead of global replacement

Prevents thrashing from spreading

Does not solve problem completely – increased
contention for paging device
 Provide processes with as many frames that it needs
 How many frames does a process need?
 Working-Set strategy – locality model

Locality – set of pages that are used together

Process moves from one locality to another

E.g. – Function call results in new locality
 Allocate enough frames to accommodate current locality
Operating System Concepts with Java – 8th Edition
9.52
Silberschatz, Galvin and Gagne ©2009
Locality In A Memory-Reference Pattern
Operating System Concepts with Java – 8th Edition
9.53
Silberschatz, Galvin and Gagne ©2009
Working-Set Model
 How do we compute locality?
   working-set window – Examine memory accesses
in the working set window
 Unique pages in the most recent working window
defines the current working set or locality
  is critical in correctly determining locality

if  too small will not encompass entire locality

if  too large will encompass several localities

if  =   will encompass entire program
Operating System Concepts with Java – 8th Edition
9.54
Silberschatz, Galvin and Gagne ©2009
Working-set model
Operating System Concepts with Java – 8th Edition
9.55
Silberschatz, Galvin and Gagne ©2009
Locality and Thrashing Mitigation
 WSSi denotes working set for process i
 D =  WSSi  total demand frames
 if D > m  Thrashing
 Thrashing Mitigation Scheme:

If D > m, then suspend one of the processes

Allocate its frame to other processes

Restart process later
Operating System Concepts with Java – 8th Edition
9.56
Silberschatz, Galvin and Gagne ©2009
Page-Fault Frequency Scheme
 Establish “acceptable” page-fault rate

If actual rate too low, process loses frame

If actual rate too high, process gains frame
Operating System Concepts with Java – 8th Edition
9.57
Silberschatz, Galvin and Gagne ©2009
Working Sets and Page Fault Rates
Operating System Concepts with Java – 8th Edition
9.58
Silberschatz, Galvin and Gagne ©2009
End of Chapter 9
Operating System Concepts with Java – 8th Edition
9.59
Silberschatz, Galvin and Gagne ©2009