Transcript Virtual Memory

Virtual Memory
Virtual Memory is created to solve difficult memory
management problems

Data fragmentation in physical memory: Reuses
blocks of memory that would otherwise be unused
when programs free up data.

Physical memory size constraints are also solved by
using alternate forms of data storage to act like
memory.


Implemented via Paging or Segmentation

Problem: Thrashing reduces preformance
Virtual Memory
Overview
Techniques used to give
an application program
logical access to
contiguous working
memory

In reality the data is
fragmented in primary and
secondary memory.

Virtual Memory




Memory Fragmentation
Not just using disk space
to extend the physical
memory.
Uses real physical
memory more efficiently.
Tricks programs into
thinking they are using
large blocks of
contiguous addresses.
Reuses fragments in
memory.
Virtual Memory: A History
1950s: Primary memory
Magnetic Core Memory
(non-volatile)
Virtual Memory: A History
1950s: Secondary memory
Drum Memory (non-volatile)
(BSD Unix: /dev/drum is default name for swap)
Virtual Memory
Overlays



Before virtual memory, programs that were
too big for the size of physical memory
used Overlays
Overlays still popular in embedded
systems that require cheap hardware
Overlays require the programmer to
manage memory for each program.
Virtual Memory
Overlays



Program manually divided into self-contained
code blocks called Overlays
Size of Overlay limited by memory constraints
(different for different systems)
Programmer had to use specific programming
languages or assembly language to have
control over the size of the program and the
size of the overlay.
Virtual Memory
A history



Virtual memory was developed in
approximately 1959–1962, at the
University of Manchester for the Atlas
Computer, completed in 1962.
In 1961, Burroughs released the
B5000, the first commercial computer
with virtual memory. It used
segmentation rather than paging.
Virtual Memory was controversial and
required many theories, models, and
experiments before it was adopted.
"the machine that
everyone loves, and
nobody buys"
- Brian Randell
Virtual Memory
A history



Dynamic address translation required a
specialized, expensive, and hard to build
hardware
Worries that new system-wide algorithms of
utilizing secondary storage would be far less
effective than application-specific ones.
In 1969 an IBM research team led by David
Sayre showed that the virtual memory overlay
system consistently worked better than the best
manually controlled systems.
Virtual Memory
Pages




Virtual memory address space is divided into pages.
A page is a block of contiguous virtual memory
addresses that are at least 4096 bytes in size.
Pages are managed by Page Tables.
Page Tables are kept in memory and translate virtual
addresses into physical addresses for use by the
hardware.

A Page Directory manages Page Tables.

There is one page directory per operating system.
Visualization of Paging System in Windows NT (32 bit)
Page Directory
Entry Offset (Per
Process)
Page Table Entry
Offset (Table +
Frame)
Memory byte
offset (4096 bytes
in frame)
Virtual Memory
Paging



“Swapping” is the act of swapping data from
physical memory into the virtual memory
portion of the hard drive.
“Paging” is the act of reading data from the
hard drive (not the virtual memory portion)
and writing data permanently back to the hard
drive.
Some Operating Systems use “Paging” to
describe both (Windows and its “pagefile” vs
Unix and its “swap”)
Virtual Memory
Page Fault

A Page Fault occurs when a program attempts to
access a page that is not current in main memory.

The operating system takes over and does the following:

1. Determines the location of the data in secondary storage.

2. Creates an empty page frame in main memory.

3. Loads the data into the empty page frame.

4. Updates the Page Table to show the new data.

5. Return control to the program, retrying the last instruction
which caused the page fault.
Virtual Memory
Page Fault




If main memory is full in step 2: Swap out page in
memory using an algorithm (most commonly used is
discarding based on Least Recently Used)
A Page is “Dirty” if it has been modified since it was
read from secondary storage.
If Page is “Dirty”, the OS writes the changes back to
secondary storage. Else, the OS just discards the
page.
When Page Fault swapping occurs, OS attempts to
predict which pages will be used later and load
those at the same time.
Virtual Memory
Paging Strategies

Demand Paging: No pages are loaded into
RAM unless specifically requested by the
program. Program starts with NO pages
loaded into RAM. Pages of program of the
program that are not run will never be loaded.
Virtual Memory
Paging Strategies

Loader Paging: Attempts to predict which
parts of the program will be loaded. If
possible, every page of the program will be
loaded into memory at the start of execution.
Virtual Memory
Paging Strategies

Anticipatory Paging: Uses the locality of
reference to pre-load pages from the program
that are most likely to be executed. The goal
is to minimize the number of page faults.
Virtual Memory
Paging Strategies



Swap Prefetch: A type of anticipatory paging
which specifically pre-loads pages
Pre-loads pages from program that caused
last pagefault.
Pre-loads pages that have been swapped out
back into memory when a large program
releases it's memory in anticipation of the
user needing to use the other programs
instead.
Virtual Memory
Paging Strategies


Pre-cleaning: Writes “Dirty” pages back into
secondary storage periodically as a syncing
mechanism, before page needs to be
swapped out.
Makes starting a new program much faster as
pages that were “Dirty” and would have to be
written back to secondary storage are now
clean and are just discarded.
Virtual Memory
Paging Replacement Algorithms

Theoretical Optimal Paging Algorithm

First In, First Out

Second Chance (Special case of FIFO)

Clock (Similar to Second Chance)

Least Recently Used

Not Frequently Used

Aging (Combines LRU with NFU)

Random
Virtual Memory


Thrashing
Thrashing is when the
Operating System spends
more and more time
swapping pages to and
from virtual memory on
the hard drive than
running the program
Occurs when the sum of
localities from running
processes cannot all fit
into main memory.
When a computer is using more
and more resources for a
decreasing amount of work done,
it is said to be thrashing.
Virtual Memory
Thrashing

Solutions for Thrashing:

Increase size of main memory


Reduce number of concurrent processes
running
Reduce the size of concurrent processes
running