Virtual Memory
Much of this subject straddles the areas of architecture and operating
systems. Must understand both to get it right.
Problems:
-- Physical memory is too small.
(Smaller than the address space of the machine,
for example, 32-bit address = 4K Mbytes, or 4 Gbytes,
but main memory is only 16 Mbytes.)
We want to have just parts of a program in memory, not the
entire (potentially very large) program
-- Want ability to have multiple processes somewhere in their
execution. Want to increase throughput of computer by allowing
multiprogramming, multitasking.
The programs (processes) need to SHARE main memory.
need RELOCATION, OS-controlled SWAPPING
-- Large, inexpensive memory (disk) is slow.
Solution:
Make main memory a cache for the larger disk.
Give OS some "hooks" to ease its job.
Introduce notion of an ADDRESS SPACE.
Address Space
-------------
Associated with every program (process) is a set of addresses
that it may reference.
PROCESS -- a program, together with some processor state.
For a 32-bit address machine, want 32 bits of address space available
to the program. And, every process wants access to the full
address space.
To do this, introduce the notion of a VIRTUAL ADDRESS SPACE.
virtual address easily generated by SW
|
|
\ /
translation
|
|
\ /
physical address used by HW to access memory
(also called a real address)
TO REMEMBER: need the translation to be fast, since it must
be done for every memory access.
That means that it must be done by HW.
Base and Bounds
---------------
Give 2 HW registers, can implement virtual memory.
base -- base address for a process -- a physical (real) address
bounds -- last valid virtual address process may access
virtual addresses generated by process are offsets from the base
-- for each reference, must check if the address is within bounds.
-- each process has its own space
-- each process must be allocated contiguously in memory
-- cheap to implement in HW. Addition and comparison can be
done in parallel.
Problems:
-- impossible to share code between 2 programs (while keeping
other code/data private to a program). This is because there
is only 1 segment for each process.
Segmentation
------------
Permit portions of process to be split into more than 1 area of
memory (SEGMENTS)
one for code
another for heap
another for stack
Use separate base and bounds for each segment.
Could add some sort of protection bit for each segment, to allow
sharing.
Problems:
-- Need table for segments/base/bounds info. Could get big.
-- External fragmentation of memory.
Paging
------
break up main memory into evenly sized PAGES.
PAGE TABLE give address of either
1) base of physical page in main memory
or 2) address of page on disk
each entry also has PRESENT bit (called VALID bit in book,
to draw an analogy to cache's valid bit). Present bit
identifies whether physical page is resident in main memory
or not.
Have one page table for each process. Its base address is kept in
a register in the CPU.
Placement of pages in memory is easy. OS keeps a free list, and
just take one from list.
Problems:
-- It takes 2 memory accesses to get one piece of data.
One to access the page table entry.
One to get the data.
Solution:
TLB (Translation Lookaside Buffer) as a cache for page table.
-- For reasonable size memory, page table is huge.
Solutions:
Keep base/bounds for page table, so only have pages needed
in table
-- Internal fragmentation. (Page size is aways wrong for some
processes.
PAGING AND SEGMENTATION
-----------------------
To reduce table sizes, use 2 levels of mapping.
Each segment contains an integral number of pages. The number of
pages can vary for each segment.
Keep a page table for each segment.
Both external and internal fragmentation are kept at bay.
Problems:
-- If tables are in memory, can take more than one memory access
to get at a piece of data.
Solution: TLB
TLB (Translation Lookaside Buffer)
-----
A process typically accesses only a few of its pages at time, and
accesses them repetitively. (Showing both spacial and temporal
locality.)
TLB conatins a mapping of virtual page number (the TAG) to a
physical page number.
Also included,
Present bit
Referenced bit(s) - To help know chose victim if no free pages.
Protection - to facilitate sharing
Dirty bit - done at page level, not cache level.
Process ID - sometimes added so that the TLB does not have
to be flushed at each context switch.
TLB typically contains 98% or more of the pages accessed.
Typical size is 64-128 entries. Small TLB can be made
fully associative.
There is a difference between miss in the TLB and a page fault.
PAGE FAULTS
-----------
What happens if the page is not resident in main memory.
- In translation, present bit is off.
- Many machines trap (take an exception).
- OS invoked to allocate free physical page from free list,
or choose a "victim," the physical page to be thrown out
of main memory to make room for faulted page. Have to
write current victim page to disk if dirty.
- OS initiates disk access (really slow, 1msec or more),
brings page into memory, updates page table and TLB,
sets present bit
- Instruction that cause page fault is restarted.
Note that restarting instructions can be a tricky business.
IBM 370 ran "long" instructions twice,
First time just to access each memory location (read),
to generate any potential page faults.
Second time to do the actual instruction, guaranteed not
to page fault.
Z8000 solution, have 2 processors, one just for handling page
faults.