Virtual Memory

Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne

 Memory

 Memory: A large array of word of bytes ,each

with its own address. Main memory and
registers are only storage CPU can access
directly
 CPU fetches instructions from memory
according to the value of a PC register.
 A typical instruction execution cycle: F, D, E, W
 The memory unit sees only a stream of memory
addresses

Operating System Concepts – 9th Edition 9.2 Silberschatz, Galvin and Gagne
 Basic Hardware

 Main memory and registers are only storages

that CPU can access directly.
 Register access is performed in one CPU clock
(or less).
 Main memory access can take many CPU clock
cycles.
 Processor normally needs to stall during
memory access, since it does not have the data
required to complete the instruction.
 Cache sits between main memory and CPU
registers for fast access

Operating System Concepts – 9th Edition 9.3 Silberschatz, Galvin and Gagne
 Base and Limit Registers
 A pair of base and limit registers define the logical
address space

Operating System Concepts – 9th Edition 9.4 Silberschatz, Galvin and Gagne
 Hardware Address Protection

Operating System Concepts – 9th Edition 9.5 Silberschatz, Galvin and Gagne
 Logical vs. Physical Address Space

 The concept of a logical address space that is

bound to a separate physical address space is
central to proper memory management
 Logical address – generated by the CPU; also
referred to as virtual address
 Physical address – identifies a physical location
of required data in a memory
 Logical address space is the set of all logical
addresses generated by a program
 Physical address space is the set of all physical
addresses generated by a program

Operating System Concepts – 9th Edition 9.6 Silberschatz, Galvin and Gagne
 Memory-Management Unit (MMU)
 Hardware device that at run time maps virtual to
physical address
 Many methods possible, covered in the rest of this
chapter
 To start, consider simple scheme where the value in
the relocation register is added to every address
generated by a user process at the time it is sent to
memory
 Base register now called relocation register
 MS-DOS on Intel 80x86 used 4 relocation registers
 The user program deals with logical addresses; it
never sees the real physical addresses
 Execution-time binding occurs when reference is
made to location in memory
 Logical address bound to physical addresses

Operating System Concepts – 9th Edition 9.7 Silberschatz, Galvin and Gagne
Operating System Concepts – 9th Edition 9.8 Silberschatz, Galvin and Gagne
 Dynamic relocation using a relocation register

Operating System Concepts – 9th Edition 9.9 Silberschatz, Galvin and Gagne
 Dynamic Loading
 Routine is not loaded until it is called
 by the All routines are kept on disk in a relocatable
load format
 The main program is loaded into memory and
executed
 When a routine needs to call another routine :
1. The calling routine first checks to see if the other
routine has been loaded
2. If not, the linking loader is called to load desired
routine into memory and update the program
address table to reflect this change
 Better memory space utilization: unused routine is
never loaded

Operating System Concepts – 9th Edition 9.10 Silberschatz, Galvin and Gagne
 Swapping
 A process can be swapped temporarily out of
memory to a backing store, and then brought back
into memory for continued execution
 Total physical memory space of processes can
exceed physical memory
 Backing store – fast disk large enough to
accommodate copies of all memory images for all
users; must provide direct access to these memory
images
 Roll out, roll in – swapping variant used for priority-
based scheduling algorithms; lower-priority process
is swapped out so higher-priority process can be
loaded and executed
 Major part of swap time is transferring time; total
transfer time is directly proportional to the amount
of memory swapped
 System maintains a ready queue of ready-to-run
processes which have memory images on disk

Operating System Concepts – 9th Edition 9.11 Silberschatz, Galvin and Gagne
 Schematic View of Swapping

Operating System Concepts – 9th Edition 9.12 Silberschatz, Galvin and Gagne
 Segmentation
 Memory-management scheme that supports user view of
memory
 A program is a collection of segments
 A segment is a logical unit such as:
main program
procedure
function
method
object
local variables, global variables
common block
stack
symbol table
arrays

Operating System Concepts – 9th Edition 9.13 Silberschatz, Galvin and Gagne
 Logical View of Segmentation

4
1

3 2
4

user space physical memory space

Operating System Concepts – 9th Edition 9.14 Silberschatz, Galvin and Gagne
 Paging
 Physical address space of a process can be
noncontiguous; process is allocated physical
memory whenever available
 Divide physical memory into fixed-sized blocks
called frames
 Divide logical memory into blocks of same size
called pages
 Keep track of all free frames
 To run a program of size N pages, need to find N free
frames and load program
 Set up a page table to translate logical to physical
addresses

Operating System Concepts – 9th Edition 9.15 Silberschatz, Galvin and Gagne
 Address Translation Scheme
 Address generated by CPU is divided into:
 Page number (p) – used as an index into a page
table which contains base address of each page in
physical memory
 Page offset (d) – combined with base address to
define the physical memory address that is sent to
the memory page
unitnumber page offset
p d
m -n n

 For given logical address space 2m and page size 2n

Operating System Concepts – 9th Edition 9.16 Silberschatz, Galvin and Gagne
 Paging Hardware

Operating System Concepts – 9th Edition 9.17 Silberschatz, Galvin and Gagne
 Page Table
 When a process arrives in the system to be
executed:
 Its size, expressed in pages, is examined.
 Each page of the process needs one frame.
 If the process requires n pages , at least n frames
must be available in memory.
 If n frame are available, they are allocated to this
arriving process.
 The first page of the process is loaded into one
of the allocated frames, and the frame number is
put in the page table for this process.
 The next page is loaded into another frame, and
its frame number is put in the page table, and so
on.

Operating System Concepts – 9th Edition 9.18 Silberschatz, Galvin and Gagne
 Paging Model of Logical and Physical Memory

Operating System Concepts – 9th Edition 9.19 Silberschatz, Galvin and Gagne
 Background
 The goal of memory management strategies : to
keep many processes in memory simultaneously to
allow multiprogramming.
 To execute any program, it should be in main
memory.
 Virtual memory is technique that allows the
execution of processes that may not be completely
in physical memory (only part of the program needs
to be in memory)
 This technique depends on get only those pages that
are demanded for program execution.
 This approach enables the OS to separate the logical
view of the memory (user view) from the physical
view(CPU view)

Operating System Concepts – 9th Edition 9.20 Silberschatz, Galvin and Gagne
 Background (Cont.)
 An examination of real programs shows that in many
cases, the entire program is not needed.
 Error code, unusual routines, large data structures
 Entire program code not needed at same time
 To execute a program that is only partially in
memory would confer many benefits:
 Program no longer constrained by limits of
physical memory
 Each program takes less memory while running ->
more programs run at the same time
 Increased CPU utilization and throughput with
no increase in response time or turnaround
time.

Operating System Concepts – 9th Edition 9.21 Silberschatz, Galvin and Gagne
 Virtual memory
 Virtual memory : is allocation scheme in which
secondary memory can be addresses as though it were
part of main memory. Program generated addresses are
translated automatically to the corresponding physical
addresses.
 Virtual address space – logical view of how
process is stored in memory
 Usually start at address 0, contiguous addresses
until end of space
 Meanwhile, physical memory organized in page
frames
 MMU must map logical to physical
 Virtual memory can be implemented via:
 Demand paging
 Demand segmentation

Operating System Concepts – 9th Edition 9.22 Silberschatz, Galvin and Gagne
 Virtual Memory That is Larger Than Physical Memory

Operating System Concepts – 9th Edition 9.23 Silberschatz, Galvin and Gagne
 Demand Paging
 Consider how an executable
program might be loaded from
disk into memory.
1. One option is to load the entire
program in physical memory at
program execution time .
2. An alternative strategy is to load
pages only as they are needed.
This technique is known as
demand paging.
 Rather than swapping the entire
process into memory, though,
we use a lazy swapper.
 Lazy swapper – never swaps a
page into memory unless page
will be needed
 Swapper that deals with
pages is a pager

Operating System Concepts – 9th Edition 9.24 Silberschatz, Galvin and Gagne
 Basic Concepts
 When a process is to be swapped in, the pager
guesses which pages will be used, instead of swapping
in the whole process, the pager brings only those
pages into memory.
 Thus, it avoid reading into memory pages that will not
be used anyway, decreasing the swap time and the
amount of physical memory needed.
 We need some form of hardware support to distinguish
between the pages that are in memory and the pages
that are on the disk.

Operating System Concepts – 9th Edition 9.25 Silberschatz, Galvin and Gagne
 Valid-Invalid Bit
 With each page table entry a valid–invalid bit is
associated
(v  in-memory – memory resident, i  not-in-memory)
 Initially valid–invalid bit is set to i on all entries
 Example of a page table snapshot:

 During MMU address translation, if valid–invalid bit in

page table entry is i  page fault
Operating System Concepts – 9th Edition 9.26 Silberschatz, Galvin and Gagne
 Page Table When Some Pages Are Not in Main Memory

Operating System Concepts – 9th Edition 9.27 Silberschatz, Galvin and Gagne
 Page Fault

 If there is a reference to a page, first reference to

that page will trap to operating system:
page fault
1. Operating system looks at another table to decide:
 Invalid reference  abort
 Just not in memory
2. Find free frame
3. Swap page into frame via scheduled disk operation
4. Reset tables to indicate page now in memory
Set validation bit = v
5. Restart the instruction that caused the page fault

Operating System Concepts – 9th Edition 9.28 Silberschatz, Galvin and Gagne
 Steps in Handling a Page Fault

Operating System Concepts – 9th Edition 9.29 Silberschatz, Galvin and Gagne
 What Happens if There is no Free Frame?

 The operating system has several options at this

point.
 It could terminate the user process.
 The operating system could instead swap out a
process, freeing all its frames and reducing the level
of multiprogramming
 The most common solution : page replacement

Operating System Concepts – 9th Edition 9.30 Silberschatz, Galvin and Gagne
 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

Operating System Concepts – 9th Edition 9.31 Silberschatz, Galvin and Gagne
 Page Replacement

Operating System Concepts – 9th Edition 9.32 Silberschatz, Galvin and Gagne
 Page and Frame Replacement Algorithms
 We must solve two major problems to implement demand
paging:
 We must develop a Frame-allocation algorithm and
 A Page-replacement algorithm
 That is, if we have multiple processes in memory, we must
decide how many frames to allocate to each process ?
 When page replacement is required, we must select the
frames that are to be replaced.
 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

Operating System Concepts – 9th Edition 9.33 Silberschatz, Galvin and Gagne
 Graph of Page Faults Versus The Number of Frames

Operating System Concepts – 9th Edition 9.34 Silberschatz, Galvin and Gagne
 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

 Try, reference string: 1,2,3,4,1,2,5,1,2,3,4,5

Operating System Concepts – 9th Edition 9.35 Silberschatz, Galvin and Gagne
 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.36 Silberschatz, Galvin and Gagne
 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.37 Silberschatz, Galvin and Gagne
 Learn and apply:
Virtual Memory

Operating System Concepts – 9th Edition 9.38 Silberschatz, Galvin and Gagne