Virtual Memory

 Background
 Demand Paging
 Process Creation
 Page Replacement
 Allocation of Frames
 Thrashing
 Demand Segmentation
 Operating System Examples

Operating System Concepts 1

 Background
 Virtual memory – separation of user logical memory from
physical memory.
 Only part of the program needs to be in memory for execution.
 Logical address space can therefore be much larger than physical
address space.
 Allows address spaces to be shared by several processes.
 Allows for more efficient process creation.

 Virtual memory can be implemented via:

 Demand paging
 Demand segmentation

Operating System Concepts 2

 Virtual Memory That is Larger Than Physical Memory

Operating System Concepts 3

 Virtual-address Space

Operating System Concepts 4

 Virtual Memory has Many Uses
 It can enable processes to share memory
 System libraries mapped into a virtual address space by different
processes
 Shared memory is considered part of the virtual address space by
different processes
 Sharing pages during process creation with fork() system call
speeds up process creation

Operating System Concepts 5

 Shared Library Using Virtual Memory

Operating System Concepts 6

 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

Operating System Concepts 7

 Transfer of a Paged Memory to Contiguous Disk Space

Operating System Concepts 8

 Valid-Invalid Bit
 With each page table entry a valid–invalid bit is associated
(1  in-memory, 0  not-in-memory)
 Initially valid–invalid but is set to 0 on all entries Frame # valid-invalid bit

 Example of a page table snapshot: 1

1
1
1
0


0
0
page table
 During address translation, if valid–invalid bit in page table entry is
0  page fault

Operating System Concepts 9

 Page Table When Some Pages Are Not in Main Memory

Operating System Concepts 10

 Page Fault
 If there is ever a reference to a page, first reference will trap to
OS  page fault
 OS looks at another table to decide:
 Invalid reference  abort.
 Just not in memory.
 Get empty frame.
 Swap page into frame.
 Reset tables, validation bit = 1.
 Restart instruction: Least Recently Used
 block move

 auto increment/decrement location

Operating System Concepts 11

 Steps in Handling a Page Fault

Operating System Concepts 12

 What happens if there is no free frame?
 Page replacement – find some page in memory, but not really in
use, swap it out
 algorithm
 performance – want an algorithm which will result in minimum
number of page faults
 Same page may be brought into memory several times

Operating System Concepts 13

 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 14

 Demand Paging Example
 Memory access time = 200 ns

 Page fault service time = 8 ms = 8,000,000 ns

 EAT = (1 – p) x 200 + p x 8,000,000

= 200 + 7,999,800 x p ns
 If p = 1/1000 = 0.001, EAT = 8.2 microseconds = 40 x (200 ns)
that is, slow down factor = 40
 If we want less than 10% degradation, we need

220 > 200 + 7,999,800 x p

20 > 7,999,800 x p
p < 0.0000025 = 1 / 399,990

Operating System Concepts 15

 Page Replacement
 Prevent over-allocation of memory by modifying page-fault
service routine to include page replacement

 Use modify (dirty) bit to reduce overhead of page transfers –

only modified pages are written to disk

 Page replacement completes separation between logical

memory and physical memory – large virtual memory can be
provided on a smaller physical memory

Operating System Concepts 16

 Need For Page Replacement

Operating System Concepts 17

 Basic Page Replacement
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. Read the desired page into the (newly) free frame. Update the
page and frame tables.

4. Restart the process

Operating System Concepts 18

 Page Replacement

Operating System Concepts 19

 Page Replacement Algorithms
 Want lowest page-fault rate
 Evaluate algorithm by running it on a particular string of memory
references (reference string) and computing the number of page
faults on that string
 In all our examples, the reference string is

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Operating System Concepts 20

 Graph of Page Faults Versus The Number of Frames

Operating System Concepts 21

 First-In-First-Out (FIFO) Algorithm
 Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
 3 frames (3 pages can be in memory at a time per process)

1 1 4 5
2 2 1 3 9 page faults
 4 frames
3 3 2 4

1 1 5 4
2 2 1 5 10 page faults
 FIFO Replacement – Belady’s Anomaly
3 3 2
 more frames  more page faults

4 4 3

Operating System Concepts 22

 FIFO Page Replacement

Operating System Concepts 23

 Optimal Algorithm
 Replace page that will not be used for longest period of time
 4 frames example

1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

1 4
2 6 page faults
3

4 5

 How do you know this?

 Used for measuring how well your algorithm performs

Operating System Concepts 24

 Optimal Page Replacement

Operating System Concepts 25

 Least Recently Used (LRU) Algorithm
 Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

1 5
2

3 5 4
4 3

 Counter implementation
 Every page entry has a counter; every time page is referenced
through this entry, copy the clock into the counter
 When a page needs to be changed, look at the counters to
determine which are to change

Operating System Concepts 26

 LRU Page Replacement

Operating System Concepts 27

 LRU Algorithm (Cont.)
 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 28

 Use Of A Stack to Record The Most Recent Page References

Operating System Concepts 29

 LRU Approximation Algorithms
 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.
 Second chance
 Need reference bit
 Clock replacement
 If page to be replaced (in clock order) has reference bit = 1 then:
 set reference bit 0
 leave page in memory
 replace next page (in clock order), subject to same rules

Operating System Concepts 30

 Second-Chance (clock) Page-Replacement Algorithm

Operating System Concepts 31

 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 32