|
2-LEVEL MAPPING
On the internet we observe two level mapping
all the time. if we click on a link ( URL), which is an address for
an object somewhere on the internet, we are taken directly to that
object. Actually a translation takes place before we are able to
view or bring the object to our local machine. First, the URL is
translated to what is called a handle and that handle is in turn
mapped to the object on the remote server. The owner of the object
is free to rename the object without worrying that future attempts
to access it will not result in a broken link. Another example is
e-mail. In our address books, we store the names of our friends and
relatives along with their e-mail addresses. For example if one had
a friend named Tom, and his e-mail address was Tom@gmu.edu, the
person could e-mail Tom by clicking on his name. Tom's friend
instead of storing Tom's name in the address book, could store his
nickname. Clicking on the nickname still would send the e-mail to
Tom.
Yet another example is a library. The title of a book is translated by the catalog to a physical location in the library. The catalog in this case acts as the mapper.
In actual computers, the mapper translates virtual addresses that are generated by the CPU to physical locations in memory. An address space of a program is a range of memory locations that are assigned only to that program. To
achieve efficient use of the processor, there may be more than one program residing in physical memory at any given time. Multiple programs or processes can share the main memory without reading or writing into each other's address space.
| An address space
of a program is a range of memory locations that are assigned
only to that program
|
This is enforced by virtual memory. Virtual memory also allows for sharing of data or code between programs by having two virtual addresses point to the same physical memory location. There are times when it is necessary for processes to
share memory. For example, if there are multiple processes in memory running the shell in UNIX, it would be a waste of space to have multiple copies of the shell in memory. Instead, it is better to have one copy of the shell reside in memory and
let all the processes that are running the shell share it.
When the CPU generates a virtual address, it goes to the memory management unit (MMU). MMU is the unit that maps virtual addresses to physical addresses. The virtual address space is divided into what are called pages to make mapping easier
and they correspond to physical page frames in main memory (RAM). The size of both of these pages are the same. The usual size for a page depends on the system but sizes of 4KB and 16KB are common in these days. For example, a computer that
generates 16 bit address in the range of 0 - 64K will have 16 virtual pages, if 4K page sizes are used. In this case there will be 8 page frames in physical memory. Only 8 virtual pages will be mapped to the 8 page frames.
Each process or program has its own page table where the virtual pages are stored. The purpose of the page table is to translate virtual pages onto physical pages in RAM. The page tables associated with each process or program can be quite
large. For example, with a 32-bit virtual address, 4K pages, and 4 bytes per page table entry, the page table could take as much as 4MB. If two programs were active in memory, their page tables would take up 8MB alone. There are various
techniques that reduce the amount of storage that is required for page tables so that most of the memory would not be tied up in page tables.
The virtual address consists of a virtual page number and an
offset. The virtual page number is used as an index into the page
table. The physical page number is obtained by attaching the offset
to the page frame number in the page table.
The location of the page table for a process is stored in hardware.
It is usually a register that points to the start of the page table for
that process. Each page table entry consists of a valid bit, the physical
page frame number, and access control information. The valid bit
indicates if the page is located in RAM or not. If it is 0, then
the page will not be found in physical memory and a page fault will
occur. When a page fault occurs, then the Operating System (OS) will
take control. The OS is responsible for finding the missing page in
the Hard Disk and bringing it into memory. The OS has to find a
page in memory to replace first. The OS uses various page
replacement algorithms to decide which page to evict from
memory. Some of the common algorithms are FIFO (First in First
Out), LRU (Least Recently Used). Access control information
describes how the page may be used. Some pages for example contain
executable code and it cannot be written to so a process trying to write
to that page would be denied access. In contrast, pages that
contain data, can be written to and read from but not executed.
In virtual memory systems, there is usually two techniques that are
used to manage memory. They are demand paging and swapping.
| To achieve
acceptable performance with virtual memory, the translation
from a virtual address to a physical address must be fast,
since the mapping has to be done on every memory
reference
|
Demand paging
involves storing only the virtual pages that are currently being used by
the executing program. If the executing program needs a page that
is not in memory at the time, the page fault handling routine in the
operating system would bring the missing page from secondary memory
(usually hard disk) and store it in a free physical page frame and an
entry for the virtual page frame number is added to the page table for
that process.
If a process needs to bring a missing page to physical memory and the
physical memory is full, then the operating system would have to replace
one of the existing pages in memory. If the page that is being
replaced was not modified during the execution of the program, than it
can be easily overwritten with the new page. However, if it has
been modified than its dirty bit would be set to tell the operating
system that it has been modified. The page cannot be just throw
away. To keep consistency, the mirror page in secondary storage must have
the same contentscontentsn be used at a later time. The operating
system stores these pages in a swap file to be used later. Access
to the swap file takes a long time compared to the speed of the CPU.
The algorithm used to decide which pages get replaced becomes very critical, because a condition called tthrashingcan occur. In this case not much real work gets done because the operating system is too busy reading from and writing to pages in the
hard disk.
A frequently used page would not be an ideal candidate for replacement bbecauseit is likely that it will be used again pretty soon. The set of pages that a program is working with is called its working set. A good replacement algorithm would
try to make sure that a process has its working set in memory.
THE CACHING PRINCIPLE
Now that we have discussed the basic
principles of virtual memory, what kind of improvements can we can
make to make it run faster? Imagine that you are sitting at a
table in a library writing a research paper. Let's say that
you need some information from a book. You would then proceed
to the shelf, open the book, get the information, close the book,
and finally return to your seat. As you can see, if you have a
bad memory or need to look up information frequently, this
process is very ineffective. But think-if there was only
enough room on your desk you could borrow the book from the shelf
and have it in front of you, then you would save a lot of time. This
is the basis of caching. Today's computers have a small high
speed storage area that keeps frequently accessed data.
The caching principle can also be used in virtual memory for
storing address translations. Consider this example: You're
back in the library doing another paper. However, the books
have been reordered using a complicated system and there is no way
to find the book you're looking for without using the card
catalog. When you need to get a book you go to the card
catalog and look up it's physical place in the library. You would then get the book, read
it and then place it back on the shelf. But, let's say
you were smarter than that and wrote down the call number from the
card catalog on a piece of paper. Chances are great that you will
be using the book again, so you wouldn't need to spend time
going to the card catalog. You could just look at the piece of paper
in front of you and go get the book. This would save a
precious amount of time. You're piece of paper would contain the mapping to the physical
location of the book.
This is exactly what we need.
Address
translation takes precious time and it is required for every memory
access. We cannot afford to do table lookups for every memory access.
Observe that when a translation for a
virtual page number is used, it will probably be needed again in
the near future. Therefore it would be helpful to have a
high speed table of recently used translations. This special address
translation cache, located inside the CPU, is traditionally referred
to as a translation look-aside buffer or TLB for short.
The TLB only contains page table mappings:
that is, the virtual memory address and the corresponding physical
page address. These high speed registers are expensive so only a few
of them are included on a chip. That may seem like a problem but it
turns out that 99% of the time the page we are looking for is in the
TLB. Let's follow the execution step by step. If the page we are
looking for is in the TLB, everything is ok. If it turns out that
the page is missing in the TLB, then we must determine whether it is
a page fault or merely a TLB miss. If the page exists in memory,
then the TLB miss indicates that only the translation is missing. In
that case the CPU can handle the miss by loading the translation
from the page table into the TLB and trying again. If the page is
NOT present in memory, then it is a true page fault. Because the TLB
has many fewer en tries than the number of pages in main memory, TLB
misses will be much more frequent than true page faults.
Historically, the TLB usually
holds translations for 8-32 virtual addresses.
NAME SPACES FOR JUST-IN-TIME SHARING AND PROTECTION
Virtual memory not only allows us to have an "unlimited" amount of fast memory, but it can easily be adapted to provide a great degree of protection. What do we mean by protection?
Each running process has its own piece of main memory, its own address space. We need to make sure that no renegade process can write or read into the address space of another user process or even the operating system. It would not be a good thing if
somebody's misbehaving computer game overwrote a program maintaining student grades.
Another advantage of walling of each process is for system reliability. If one process becomes unruly, it can only damage its own objects and not the whole system.
Many machines that can afford to allocate enough memory to hold a process's address space often use virtual memory because protection is so important. As you can see, unless we provide significant protection, sharing memory will be a mixed blessing.
|
