Virtual Memory

 Background
 Demand Paging
 Process Creation
 Page Replacement
 Allocation of Frames
 Thrashing
 Memory-Mapped Files
 Allocating Kernel Memory
 Other Considerations
 Operating-System Examples

1
 Background
 Virtual memory is a technique that allows the execution of processes
that are not completely in memory
 The basic idea behind virtual memory is that the combined size of the
program, data, and stack may exceed the amount of physical memory
available for it. The operating system keeps those parts of the program
currently in use in main memory, and the rest on the disk.
 For example, a 16-MB program can run on a 4-MB machine by
carefully choosing which 4 MB to keep in memory at each instant, with
pieces of the program being swapped between disk and memory as
needed.
 Virtual memory can be implemented via:
◦ Demand paging
◦ Demand segmentation

2
Virtual Memory That is Larger Than Physical
Memory

3
 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

4
Transfer of a Paged Memory to Contiguous Disk
Space

Lazy swapper – never swaps a page into memory

unless page will be needed.

Swapper that deals with pages is a pager

5
 Valid-Invalid Bit
 With each page table entry a valid–invalid bit is associated.
 Valid - the associated page is both legal and in memory.
 Invalid-the page either is not valid (that is, not in the logical address
space of the process) or is valid but is currently on the disk.
 Initially valid–invalid bit is set to i on all entries.

 Access to a page marked invalid causes a page fault.

6
Page Table When Some Pages Are Not in Main
Memory

7
Steps in Handling a Page Fault

8
 Steps in Handling a Page Fault
1. We check an internal table (usually kept with the process control block)
for this process to determine whether the reference was a valid or an
invalid memory access.
2. If the reference was invalid, we terminate the process. If it was valid but
we have not yet brought in that page, we now page it in.
3. We find a free frame (by taking one from the free-frame list, for example).
4. We schedule a disk operation to read the desired page into the newly
allocated frame.
5. When the disk read is complete, we modify the internal table kept with
the process and the page table to indicate that the page is now in memory.
6. We restart the instruction that was interrupted by the trap. The process
can now access the page as though it had always been in memory.

9
 Performance of Demand Paging (Cont.)
 Three major activities
◦ Service the interrupt – careful coding means just several hundred
instructions needed
◦ Read the page – lots of time
◦ Restart the process – again just a small amount of time
 Page Fault Rate 0  p  1
◦ if p = 0 no page faults
◦ if p = 1, every reference is a fault
 Effective Access Time (EAT)
EAT = (1 – p) x memory access time
+ p (page fault overhead
+ swap page out
+ swap page in )
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!!
 Copy-on-Write
 Traditionally, fork() worked by creating a copy of the parent’s address
space for the child, duplicating the pages belonging to the parent.
 However, considering that many child processes invoke the exec() system
call immediately after creation, the copying of the parent’s address space
may be unnecessary.
 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.
 Operating systems typically allocate these pages using a technique known
as zero-fill-on-demand.
 Zero-fill-on-demand pages have been zeroed-out before being allocated,
thus erasing the previous contents.

12
Before Process 1 Modifies Page C
After Process 1 Modifies Page C
 What Happens if There is no Free Frame?

 Used up by process pages

 Also in demand from the kernel, I/O buffers, etc
 How much to allocate to each?
 Page replacement – find some page in memory, but not
really in use, page it out
◦ Algorithm – terminate? swap out? replace the page?
◦ Performance – want an algorithm which will result in
minimum number of page faults.
 Same page may be brought into memory several times.
 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.

16
Need For Page Replacement

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
- 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 – increasing EAT

18
Page Replacement

19
 Page and Frame Replacement Algorithms
 Frame-allocation algorithm determines
◦ How many frames to give each process.
◦ Which frames to replace
 Page-replacement algorithm
◦ Want lowest page-fault rate on both first access and re-access
 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
 In all our examples, the reference string of referenced page
numbers is
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
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
◦ Adding more frames can cause more page faults!
 Belady’s Anomaly
 How to track ages of pages?
◦ Just use a FIFO queue
 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

28
Use Of A Stack to Record The Most Recent Page References

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.

30
Second-Chance (clock) Page-Replacement Algorithm

31
LRU Approximation Algorithms
Enhanced Second-Chance Algorithm
 considering both the reference bit and the modify bit as an

ordered pair
1. (0,0) neither recently used nor modified-best page to replace
2. (0,l) not recently used but modified-not quite as good,
because the page will need to be written out before
replacement
3. (1,0) recently used but clean-it probably will be used again
soon
4. (1,l) recently used and modified-it probably will be used
again soon, and the page will be need to be written out to
disk before it can be replaced
32
 Counting Algorithms
 Keep a counter of the number of references that have
been made to each page.

 Least Frequently Used (LFU) Algorithm: replaces

page with smallest count.

 Most Frequently Used (MFU) Algorithm: based on the

argument that the page with the smallest count was
probably just brought in and has yet to be used.

33
Page-Buffering Algorithms
 Keep a pool of free frames, always
◦ Then frame available when needed, not found at fault time
◦ Read page into free frame and select victim to evict and
add to free pool
◦ When convenient, evict victim
 Possibly, keep list of modified pages
◦ When backing store otherwise idle, write pages there and
set to non-dirty
 Possibly, keep free frame contents intact and note
what is in them
◦ If referenced again before reused, no need to load contents
again from disk
◦ Generally useful to reduce penalty if wrong victim frame
selected
Applications and Page Replacement

 All of these algorithms have OS guessing about

future page access
 Some applications have better knowledge – i.e.
databases
 Memory intensive applications can cause double
buffering
◦ OS keeps copy of page in memory as I/O buffer
◦ Application keeps page in memory for its own work
 Operating system can given direct access to the disk,
getting out of the way of the applications
◦ Raw disk mode
 Bypasses buffering, locking, etc
 Allocation of Frames
 Each process needs minimum number of pages.
 Example: IBM 370 – 6 pages to handle SS MOVE

instruction:
◦ instruction is 6 bytes, might span 2 pages.
◦ 2 pages to handle from.
◦ 2 pages to handle to.
 Two major allocation schemes.
◦ fixed allocation
◦ priority allocation

36
 Fixed Allocation
 Equal Allocation – For example, if there are 100 frames (after
allocating frames for the OS) and 5 processes, give each process 20
frames
◦ Keep some as free frame buffer pool
 Proportional Allocation – Allocate according to the size of process.
 Consider a system with a 1-KB frame size. If a small student process of
10 KB and an interactive database of 127 KB are the only two processes
running in a system with 62 free frames, it does not make much sense to
give each process 31 frames.

si  size of process pi
S   si
m  total number of frames
s
ai  allocation for pi  i  m
S

37
 Priority Allocation
 Use a proportional allocation scheme using priorities
rather than size.

 If process Pi generates a page fault,

◦ select for replacement one of its frames.
◦ select for replacement a frame from a process with lower
priority number.

38
 Global vs. Local Allocation
 Global replacement – process selects a replacement frame from the set
of all frames; one process can take a frame from another.
◦ But then process execution time can vary greatly
◦ But greater throughput so more common

 Local replacement – each process selects from only its own set of
allocated frames.
◦ More consistent per-process performance
◦ But possibly underutilized memory

39
Non-Uniform Memory Access
 So far all memory accessed equally
 Many systems are NUMA – speed of access to memory varies
◦ Consider system boards containing CPUs and memory,
interconnected over a system bus
 Optimal performance comes from allocating memory “close to” the
CPU on which the thread is scheduled
◦ And modifying the scheduler to schedule the thread on the same
system board when possible
◦ Solved by Solaris by creating lgroups
 Structure to track CPU / Memory low latency groups
 Used my schedule and pager
 When possible schedule all threads of a process and allocate all
memory for that process within the lgroup
Thrashing
 If a process does not have “enough” pages, the page-
fault rate is very high. This leads to:
◦ low CPU utilization.
◦ operating system thinks 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.

41
Thrashing

42
Demand Paging and Thrashing
 Why does demand paging work?
Locality model
◦ The working-set strategy starts by looking at how many frames a
process is actually using. This approach defines the locality model of
process execution.
◦ The locality model states that, as a process executes, it moves from
locality to locality.
◦ A locality is a set of pages that are actively used together.
◦ A program is generally composed of several different localities, which
may overlap.
 Why does thrashing occur?
 size of locality > total memory size
◦ Limit effects by using local or priority page replacement

43
Locality In A Memory-Reference Pattern

44
Working-Set Model
 The working-set model is based on the assumption of locality.
 This model uses a parameter  to define the working-set window.
 The set of pages in the most recent page references is the working set
   working-set window  a fixed number of page references
Example: 10,000 instruction
 WSSi (working set of Process Pi) =
total number of pages referenced in the most recent  (varies in time)
◦ if  too small will not encompass entire locality.
◦ if  too large will encompass several localities.
◦ if  =   will encompass entire program.
 D =  WSSi  total demand frames
 if D > m  Thrashing
 Policy if D > m, then suspend one of the processes.

45
Working-set model

46
Keeping Track of the Working Set
 Approximate with interval timer + a reference bit
 Example:  = 10,000

◦ Timer interrupts after every 5000 time units.

◦ Keep in memory 2 bits for each page.
◦ Whenever a timer interrupts copy and sets the values of all
reference bits to 0.
◦ If one of the bits in memory = 1  page in working set.
 Why is this not completely accurate?
 Improvement = 10 bits and interrupt every 1000 time

units.

47
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.

48
Working Sets and Page Fault Rates
 Direct relationship between working set of a process and its
page-fault rate
 Working set changes over time
 Peaks and valleys over time
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
 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)
Memory Mapped Files
Shared Memory via Memory-Mapped I/O
Other Issues – TLB Reach
 TLB Reach - The amount of memory accessible from the
TLB
 TLB Reach = (TLB Size) X (Page Size)
 Ideally, the working set of each process is stored in the TLB
◦ Otherwise there is a high degree of page faults
 Increase the Page Size
◦ This may lead to an increase in fragmentation as not all applications
require a large page size
 Provide Multiple Page Sizes
◦ This allows applications that require larger page sizes the
opportunity to use them without an increase in fragmentation
 Other Issues – Program Structure
 Program structure
◦ int[128,128] data;
◦ Each row is stored in one page
◦ Program 1
for (j = 0; j <128; j++)
for (i = 0; i < 128; i++)
data[i,j] = 0;

128 x 128 = 16,384 page faults

◦ Program 2
for (i = 0; i < 128; i++)
for (j = 0; j < 128; j++)
data[i,j] = 0;

128 page faults

Other Issues – I/O interlock
 I/O Interlock – Pages must
sometimes be locked into memory
 Consider I/O - Pages that are used
for copying a file from a device
must be locked from being selected
for eviction by a page replacement
algorithm
 Pinning of pages to lock into
memory
Operating System Examples

 Windows

 Solaris
Windows
 Uses demand paging with clustering. Clustering brings in pages
surrounding the faulting page
 Processes are assigned working set minimum and working set
maximum
 Working set minimum is the minimum number of pages the
process is guaranteed to have in memory
 A process may be assigned as many pages up to its working set
maximum
 When the amount of free memory in the system falls below a
threshold, automatic working set trimming is performed to
restore the amount of free memory
 Working set trimming removes pages from processes that have
pages in excess of their working set minimum
Solaris
 Maintains a list of free pages to assign faulting processes
 Lotsfree – threshold parameter (amount of free memory) to begin
paging
 Desfree – threshold parameter to increasing paging
 Minfree – threshold parameter to being swapping
 Paging is performed by pageout process
 Pageout scans pages using modified clock algorithm
 Scanrate is the rate at which pages are scanned. This ranges from
slowscan to fastscan
 Pageout is called more frequently depending upon the amount of
free memory available
 Priority paging gives priority to process code pages
Solaris 2 Page Scanner