Transcript Slide 1

Virtual Memory
From novelty to essential
Copyright © 2005-2013 Curt Hill
Introduction
• A technique for isolating a program
from the limitations of real memory
• An unusual thing in that it requires
both hardware and operating system
support
– Without hardware support it is too slow to
be helpful
– The process is too complicated to only
involve the hardware and must involve the
loader and task manager
Copyright © 2005-2013 Curt Hill
Two Important Numbers
• The idea is that we have two important
numbers about memory:
• Address space
– Usually limited by word size or size of address
• Physical memory
– Just because we have an address space of 16M
(for example) does not mean that each machine
has that much
– It is usually the case that a particular machine
has less memory than is allowed by the address
space of the machine
Copyright © 2005-2013 Curt Hill
Examples:
• In the 360/370 machines the address
space was 16M
• When people started to be frustrated
by that IBM introduced the 3080 which
increased the address size from 24 to
32 bit, which increased the address
space from 16M to 4000M or so
– The 8080 had an address space of 64K (16
bit)
– The 8086 raised that to a (24 or 32 bit)
Copyright © 2005-2013 Curt Hill
Two Other Factors
• We have two other factors that need to
be reckoned with:
• There is never enough physical
memory
• The concept of locality allows some
optimization of memory
• The exploitation of these leads to
virtual memory
Copyright © 2005-2013 Curt Hill
Never Enough
• There is never enough physical memory
• If we have 2 M we will get a program that
takes 3 M
• This is complicated by the fact that on fast
machines we would like to do multi-tasking,
so that while one process is waiting for I/O
or whatever another can continue to print,
compute or whatever
• It is easier to exceed the physical memory
size, because now we have to consider the
sum of the memory requirements
Copyright © 2005-2013 Curt Hill
Locality Principle
• All programs demonstrate locality to some
degree
• In any given short period of time they will not
reference every memory address in the
program
– Instead a very small subset of the possible
memory
– The time period is much larger than a machine
length and much smaller than total program
length
• This is same fact that makes cache memory
work
– A program will use some parts of its code and
some parts of its data very intensively and ignore
the rest
Copyright © 2005-2013 Curt Hill
Locality Again
• Cut a program and data into pieces
– At any given small period of time the pieces used
are much smaller than the total size
• Working set
– That set of pieces that the program needs to run
in an short period of time
– The working set changes over time, but it always
is less than the total program size
Copyright © 2005-2013 Curt Hill
Virtual memory
• The means of exploiting the locality of
programs to over commit real memory
• There are two major subdivisions of
virtual memory
– Paging
– Segmentation
• Both have been used successfully
– Pentium supports both in hardware
Copyright © 2005-2013 Curt Hill
Briefly
• Paging subdivides programs into equal
sized pieces
– Eg. like the page of a book
• Segmentation subdivides programs
into sizes determined by the program
– Eg, like chapters or segments of a book
Copyright © 2005-2013 Curt Hill
Paging
• Paging is the most common virtual memory
• Consider two types of memory:
– Logical (or Virtual)
– Physical (or Real)
• Physical memory is chopped into uniform
sized pages
–
–
–
–
A page is 512, 1K, 2K, 4K, 8K
All pages in a system are one size
Yet from system to system the size may change
For our examples let us assume a 4K page size
Copyright © 2005-2013 Curt Hill
Memory Addresses
• Suppose a 32 bit address
• Each memory address can then be
partitioned into two pieces:
– The bottom 12 bits addresses in the page
– The top 20 bits selects the page
• Real memory consists of slots, where a
slot can contain a page
• We address a slot with that 20 bit
upper address
Copyright © 2005-2013 Curt Hill
Page table
• This table allows us to translate the top so
many bits into a different page
• The process is known as dynamic address
translation
• We take the upper 20 bits (the slot address)
and translate it into a potentially different
slot, without the program being aware of the
translation
• Pages can exist in two places:
– In a real slot, that is in memory
– On disk, aka paged out
Copyright © 2005-2013 Curt Hill
Generating an address
• When a program generates a virtual
address then the hardware intercepts
that address
• It does DAT to attempt to generate a
slot address
• In the process of DAT it will determine
if the page is in memory or on disk
• If in memory then translate a slot
address and let the operation proceed
• In not in memory, register a page fault
Copyright © 2005-2013 Curt Hill
Page Fault
• Action started when a virtual memory
page in on disk and not in memory
• The original process is then
suspended
• The needed page is requested from
disk
• When it arrives in the memory the page
table is updated to include that page
• The process is now ready to restart
Copyright © 2005-2013 Curt Hill
Recall Cache
• Like cache we also have a
replacement policy
• There is also a write policy but
multiprocessors do not complicate
things like in cache
• We may use the same algorithms as
cache
Copyright © 2005-2013 Curt Hill
Replacement Policy Again
• Unlike cache replacement policy does
not have to be completely
implemented in hardware
– The replacement policy is only needed
when we are committed to moving a page
– Thus may be much more complex than in
cache
• The way compilers group code can be
tailored to the replacement policy,
which will increase performance
Copyright © 2005-2013 Curt Hill
Pre-cleaning
• UNIX habit of writing pages that have
been changed but not referenced
recently to disk before the need to
remove the page
• When a page is needed the page is
now cleaned and easy to free
• Windows does this also with the
modified page writer
• This corresponds to the cache write
policy
Copyright © 2005-2013 Curt Hill
Paging Styles
• Demand paging – aka lazy
– Get the page from disk only when a page
fault occurs
• Anticipatory paging
– Attempt to predict which pages should be
loaded next
– Especially on initial loading of a program
Copyright © 2005-2013 Curt Hill
Characteristics
• The program and the programmer is
completely oblivious to the fact that an
instruction could be shot down in mid-cycle
and then restarted
• The idea has two important consequences:
• This mechanism can be used to allow large
programs to run in smaller space
• This can also be used to protect one user
from another, if each user has their own
page table
Copyright © 2005-2013 Curt Hill
Performance considerations
• To access the memory would normally take
two memory fetches: one to access the page
table and another for the real address
• This would impair performance
• The solution is the Translation Lookaside
Buffer
• This is a special cache device that does the
translation of most recently used addresses
• Often uses Content Associative Memory
• Reduces memory fetches
Copyright © 2005-2013 Curt Hill
Protection
• Early virtual memory systems used
partitioned memory
– Just made it bigger
– Virtual memory did nothing to help
• Most now make a process run alone in
an entire address space
– A program cannot interfere with another
since the other is in a completely different
address space
Copyright © 2005-2013 Curt Hill
Segmentation
• Was used effectively by Burroughs
computers
– At the time most companies were doing well to
allow overlay linkers to be easy enough to use
that did not require a PhD
• The idea is to not cut the memory but the
program
• Paging is transparent, invisible to the
programmer
• Segmentation is visible, the programmer
can exploit the process
Copyright © 2005-2013 Curt Hill
Segmentation
• Each procedure/function or data block
becomes a segment that can exist in
memory or on disk
• When the procedure is needed then load it
– If it is not present
• Each segment is independently relocatable
– This relocation should be quick and easy
• Each segment is of a different size
• Memory can become fragmented since each
segment may be of a different size
Copyright © 2005-2013 Curt Hill
Segmentation advantages
• Simplifies handling of data structures
– A complicated data structure gets its own
segment
– This can then be expanded or contracted by the
OS
• Each segment can be independently
compiled or assembled
– In paging the whole thing must be re-linked in
order to divide into pages
– Thus sharing is facilitated by segmentation
• Useful data can be available to any process
in the system
– Protection can also be handled
Copyright © 2005-2013 Curt Hill
Segementation Pictures
• Suppose we have two programs, A and
B, shown below
• Each as several units
– Code – Fn1, Fn2…
– Data – Data1, Data2…
• Each of these may be a different size
A
A-Fn1
B
B-Fn1
A-Fn2
B-Fn2
A-Fn3
B-Fn3
A-Data1
B-Fn4
A-Data2
B-Data1
Copyright © 2005-2013 Curt Hill
B-Data2
Segmentation
• Each unit of each program may go
anywhere there is space
Memory
B-Fn1
A-Fn3
B-Fn2
B-Data2
A-Data2
Free
Free B-Fn4
A-Data1
Free
Disk
A-Fn1
B-Fn1
A-Fn2
B-Fn2
A-Fn3
B-Fn3
A-Data1
B-Fn4
A-Data2
B-Data1
Copyright © 2005-2013 Curt Hill
B-Data2
Fragmentation
• Both types of virtual memory suffer
from fragmentation
• Paging has internal
• Segmentation has external
Copyright © 2005-2013 Curt Hill
Paging and Fragmentation
• Code and data does not usually fall into 4K
chunks
• In a 4K block there may be a mix of data and
instructions that are not related to each
other
• Both will be jerked in and out of memory
based on references to any of it
Copyright © 2005-2013 Curt Hill
Segmentation and Fragmentation
• Each item is a different size
• The memory can become fragmented
• There is plenty of memory available, but not
enough of it is contiguous to satisfy the
current request
• The Burroughs system could compact
memory when it was seriously fragmented
– It did so by suspending all running programs
during the process
Copyright © 2005-2013 Curt Hill
External Fragmentation
• What happens when we want to load BData1?
• No one spot is large enough.
Memory
B-Fn1
B-Fn2
A-Fn3
Free
A-Data2
B-Data2
Free B-Fn4
Free A-Data1
Free
Disk
A-Fn1
B-Fn1
A-Fn2
B-Fn2
A-Fn3
B-Fn3
A-Data1
B-Fn4
A-Data2
B-Data1
Copyright © 2005-2013 Curt Hill
B-Data2
Paging
• Take our same two programs and chop
into 4K blocks
– Interchangeable in terms of size
• Internal fragmentation now occurs
– A-Fn1 is in two pages
– Every time the second page is brought in
a piece a A-Fn2 is also brought in whether
we need it or not
– Also some waste at the end
A-Fn1
B-Fn1
A-Fn2
B-Fn2
A-Fn3
B-Fn3
A-Data1
B-Fn4
A-Data2
B-Data1
Copyright © 2005-2013 Curt Hill
B-Data2
Problems
• Virtual memory is not a cure all with no
downside
• It increases I/O traffic
• It increases the context switching time
• Slow execution
– Although it may increase throughput
• Increases complexity of both hardware
and software
Copyright © 2005-2013 Curt Hill
Thrashing
• An unstable state where the system
mostly does paging and no useful work
• The problem occurs when the sum of
working sets of current processes
exceeds available memory
• Most processes are waiting for a
virtual memory request
• Pages are continually being stolen so
that no process can run and get done
• Seqmentation systems are less prone
Copyright © 2005-2013 Curt Hill
Desperation Swapping
• When UNIX is thrashing or close it will
use this technique
• Swap out an entire user process to
disk
• This should provide enough free slots
to end thrashing
Copyright © 2005-2013 Curt Hill
Virtual Memory API
• There are a couple of things that would
be nice and systems often provide
them
• Fixing pages – forcing them to be in
memory and not disk
• Sharing pages between processes
Copyright © 2005-2013 Curt Hill
Fixing Pages
• Most OSs provide a system call that
fixes pages
• This is a potentially dangerous
operation
– Too many fixed pages could provoke
thrashing
• Windows provides a VirtualLock
function that fixes a range of pages
and VirtualUnlock that releases them
• UNIX uses mlock and munlock
Copyright © 2005-2013 Curt Hill
Uses
• Most operating systems which have
the hardware support use paging
systems
• OS/2 on the 80286 used segmentation
since the CPU had no support for
paging
Copyright © 2005-2013 Curt Hill
Pentium example
• Pentiums allow paging and
segmentation in any combination
• Unsegmented unpaged memory
– virtual address = real address
– Used in low complexity, high
performance, usually drivers and
controllers
– 4G bytes available
• Unsegmented paged memory
– Preferred by Berkeley UNIX
Copyright © 2005-2013 Curt Hill
Pentium Continued
• Segmented unpaged memory
– Protection to single byte
– Address translation tables are guaranteed
to be in CPU when segment is in memory
• Gives predictable access times
– 64Tera byte address space
• Segmented paged memory
– UNIX V prefers
– Segmentation for logical memory
partitions and paging within these
Copyright © 2005-2013 Curt Hill
Pentium and Protection
• Each segment has a protection code
–
–
–
–
Data has a classification (who can access)
Code has clearance level
0 is most privileged and 3 is least privileged
Code must have a clearance level less than or
equal to the classification of the data
– Some instructions cannot be executed except at
lower clearance levels
• In segmentation the logical address is
composed of 16 segment and a 32 bit offset
Copyright © 2005-2013 Curt Hill
History I
• 1959 – First virtual memory system
was the Atlas system at University of
Manchester
– Reportedly doubled or tripled
programmer productivity
• 1961 – IBM Stretch uses concept of
locality to pre-fetch instructions
• 1965 – Wilkes introduces cache
memory (then known as slave memory)
Copyright © 2005-2013 Curt Hill
History 2
• 1966 – Paper by Belady of IBM on
replacement algorithms shows usage
bits are important
• 1966 – Working set concept developed
by Peter Denning
• 1968 – Denning paper shows thrashing
results suddenly when memory
exceeds a threshhold
• 1969 – IBM researchers show that
programs demonstrating good locality
causes virtual memory systems to
perform well
Copyright © 2005-2013 Curt Hill
Commercialization
• RCA, GE, Burroughs and Univac all
have virtual memory systems by 1964
– These were subject to problems with
thrashing
• IBM spends lots of money researching
virtual memory and does not offer one
until 1972
– They discover that putting use bits in the
page table improves performance and
reduces thrashing
Copyright © 2005-2013 Curt Hill
Finally
• Virtual memory has traveled from
experimental novelty to required
feature
• No modern OS can be without this
• It frees the programmer from memory
worries
• Increases throughput
Copyright © 2005-2013 Curt Hill