Transcript part2

What Happens if There is no Free Frame?
 Page replacement – find some page in memory, but not really in
use, page it out

Performance – want an algorithm which will result in minimum
number of page faults

Use modify (dirty) bit to reduce overhead of page transfers –
only modified pages are written to disk
Operating System Concepts – 9th Edition
9.1
Silberschatz, Galvin and Gagne ©2013
Need For Page Replacement
Operating System Concepts – 9th Edition
9.2
Silberschatz, Galvin and Gagne ©2013
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
- Write victim frame to disk if dirty
3.
Bring the desired page into the (newly) free frame; update the page
and frame tables
4.
Continue the process by restarting the instruction that caused the trap
Note now potentially 2 page transfers for page fault
Operating System Concepts – 9th Edition
9.3
Silberschatz, Galvin and Gagne ©2013
Page Replacement
Operating System Concepts – 9th Edition
9.4
Silberschatz, Galvin and Gagne ©2013
Page Replacement Algorithms
 Evaluate algorithm by running it on a particular string of memory
references (reference string) and computing the number of page
faults on that string

String is just page numbers, not full addresses

Repeated access to the same page does not cause a page fault

Results depend on number of frames available
Operating System Concepts – 9th Edition
9.5
Silberschatz, Galvin and Gagne ©2013
Graph of Page Faults Versus The Number of Frames
Operating System Concepts – 9th Edition
9.6
Silberschatz, Galvin and Gagne ©2013
First-In-First-Out (FIFO) Algorithm
 Reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
 3 frames (3 pages can be in memory at a time per process)
15 page faults
 Can vary by reference string: consider 1,2,3,4,1,2,5,1,2,3,4,5
Operating System Concepts – 9th Edition
9.7
Silberschatz, Galvin and Gagne ©2013
Optimal Algorithm
 Replace page that will not be used for longest period of time

9 is optimal for the example
 How do you know this?

Can’t read the future
 Used for measuring how well your algorithm performs
Operating System Concepts – 9th Edition
9.8
Silberschatz, Galvin and Gagne ©2013
Least Recently Used (LRU) Algorithm
 Use past knowledge rather than future
 Replace page that has not been used in the most amount of time
 Associate time of last use with each page
 12 faults – better than FIFO but worse than OPT
 Generally good algorithm and frequently used
Operating System Concepts – 9th Edition
9.9
Silberschatz, Galvin and Gagne ©2013
Thrashing
 If a process does not have “enough” pages, the page-fault rate is
very high

Page fault to get page

Replace existing frame

But quickly need replaced frame back

This leads to:

Low CPU utilization

Operating system thinking that it needs to increase the
degree of multiprogramming

Another process added to the system
 Thrashing  a process is busy swapping pages in and out
Operating System Concepts – 9th Edition
9.10
Silberschatz, Galvin and Gagne ©2013
Thrashing (Cont.)
Operating System Concepts – 9th Edition
9.11
Silberschatz, Galvin and Gagne ©2013
Memory-Mapped Files
 Memory-mapped file I/O allows file I/O to be treated as routine
memory access by mapping a disk block to a page in memory
 A file is initially read using demand paging

A page-sized portion of the file is read from the file system into
a physical page

Subsequent reads/writes to/from the file are treated as
ordinary memory accesses
 Simplifies and speeds file access by driving file I/O through
memory rather than read() and write() system calls
 Also allows several processes to map the same file allowing the
pages in memory to be shared
 But when does written data make it to disk?

Periodically and / or at file close() time

For example, when the pager scans for dirty pages
Operating System Concepts – 9th Edition
9.12
Silberschatz, Galvin and Gagne ©2013
Memory-Mapped File Technique for all I/O
 Some OSes uses memory mapped files for standard I/O
 Process can explicitly request memory mapping a file via mmap()
system call

Now file mapped into process address space
 For standard I/O (open(), read(), write(), close()), mmap
anyway

But map file into kernel address space

Process still does read() and write()


Copies data to and from kernel space and user space
Uses efficient memory management subsystem

Avoids needing separate subsystem
 COW can be used for read/write non-shared pages
 Memory mapped files can be used for shared memory (although
again via separate system calls)
Operating System Concepts – 9th Edition
9.13
Silberschatz, Galvin and Gagne ©2013
Memory Mapped Files
Operating System Concepts – 9th Edition
9.14
Silberschatz, Galvin and Gagne ©2013
Shared Memory via Memory-Mapped I/O
Operating System Concepts – 9th Edition
9.15
Silberschatz, Galvin and Gagne ©2013