Virtual memory notes

Paging

Frames are fixed-sized blocks of physical memory
Pages are fixed-sized blocks of logical memory

Process

When a process is to be executed, its pages are loaded into any available memory frames from their source (a file system or the backing store).
The logical address space is now totally separate from the physical address space, so a process can have a logical 64-bit address space even though the system has less than 2^64 bytes of physical memory

Hardware Support

Every address generated by the CPU is divided into two parts: a page number (p) and a page offset (d). The page number is used as an index into a page table. The page table contains the base address of each page in physical memory. This base address is combined with the page offset to define the physical memory address that is sent to the memory unit.
The page size (like the frame size) is defined by the hardware. The size of a page is a power of 2, varying between 512 bytes and 1 GB per page. If the size of the logical address space is 2^m, and a page size is 2^n bytes, then the high-order m-n bits of a logical address designate the page number and the n low-order bits designate the page offset.

Every logical address is bound by the paging hardware to some physical address. Using paging is similar to using a table of base registers, one for each frame of memory
When a process arrives in the system to be executed, its size, expressed in pages, is examined. Each page of the process needs at least one frame
- thus, if the process requires n pages, at least n frames must be available in memory. If n frames 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, its frame number is put onto the page table, and so on

frame table

data structure containing one entry for each physical page frame with the following information:

which frames are allocated of physical memory
- and to which page of which process
which frames are available
how many total frames there are
etc

translation look-aside buffer (TLB)

associative, high-speed memory. Each entry in the TLB consists of two parts:

a key (or tag)
- when the associative memory is presented with an item, the item is compared with all keys simultaneously
a value
- If the item is found, the corresponding value field is returned
The TLB only contains a few of the page-table entries. When a logical address id generated by the CPU, its page number is presented to the TLB
- If the page number is found, its frame number is immediately available and is used to access memory
- If the page number is not in the TLB (known as a TLB miss), a memory reference to the page table must be made
  - When the frame number is obtained, we can use it to access memory
  - In addition, we add the page number and frame number to the TLB, so that they will be found quickly on the next reference
- If the TLB is already full of entries, an existing entry must be selected for replacement.

Protection (valid/invalid bits)

these bits are kept in the page table - one can define a page to be read-write or read-only

Every reference to memory goes through the page table to find the correct frame number
Protection bits can be checked to ensure that no writes are being made to a read-only page
one such bit is the valid-invalid bit
- when this bit is set to valid, the associated page is in the process’s logical address space and is thus a legal (or valid) page
- when the bit is set to invalid, the page is not in the process’s logical address space
- the OS sets this bit for each page to allow or disallow access to the page

Replacement

If you overallocate memory, the OS must use a page replacement algorithm (process is requesting more than the available memory)

if no frame is free, we find one that is not currently being used and free it
we do this by changing the page table (and all other tables) to indicate that the page is no longer in memory
we can now use the freed frame to hold the page for which the process faulted

Find the location of the desired page on the disk
Find a free frame:
a. if there is a free frame, use it b. if there is no free frame, use a page-replacement algorithm to select a victim frame c. write the victim frame to the disk; change the page and frame tables accordingly
read the desired page into the newly freed frame; change the page and frame tables
continue the user process from where the page fault occurred

This process slows down when there are no free frames and two page transfers are required: so we can reduce this overhead by using a modify bit (or dirty bit)

each page or frame has a modify bit associated with it in the hardware
the modify bit for a page is set by the hardware whenever any byte in the page is written into, indicating that the page has been modified
when we select a page for replacement, we examine its modify bit
if the bit is set, we know that the page has been modified since it was read in from the disk
- in this case, we must write the page to the disk
if the bit is not set, the page has not been modified since it was read into memory.
- in this case, we need not write the memory page to the disk: it is already there

FIFO

associates the time when that page was brought into memory with each page
when a page must be replaced, the oldest page is chosen
implement: replace the page at the head of the queue each time. When a page is brought into memory, we insert it at the tail of the queue

LRU

last recently used algorithm - replace the page that has not been used for the longest period of time
associates with each page the time of that page’s last use
when a page must be replaced, LRU chooses the page that has not been used for the longest period of time
implement:
- associate with each page-table entry a time-of-use counter and increment for every memory reference. We replace the page with the smallest time value
- keep a stack of page numbers. Whenever a page is referenced, it is removed from the stack and put on the top. In this way, the most recently used page is always at the top of the stack and the least recently used page is always at the bottom -> modify 6 pointers at the worst case scenario

Second-chance (clock)

Basic algorithm is a FIFO replacement algorithm. When a page has been selected, however, we inspect its reference bit

if the bit is 0, we proceed to replace this page
if the bit is 1, we give the page a second chance and move on to select the next FIFO page
- when a page gets a second chance, its reference bit is cleared, and its arrival time is reset to the current time
- thus, a page that is given a second chance will not be replaced until all other pages have been replaced (or given second chances)
implement: a pointer indicates which page is to be replaced next. When a frame is needed, the pointer advances until it finds a page with a 0 reference bit. As it advances, it clears the reference bits
- once a victim page is found, the page is replaced, and the new page is inserted in the circular queue in that position
- if all bits are set, second-chance replacement degenerates to FIFO replacement

Page fault handler

When a process tries to access a page that was not brought into memory - access to a page marked invalid causes a page fault. The paging hardware will notice that the invalid bit is set, causing a trap in the OS. The procedure for handling this page fault is as follows:

We check an internal table for this process to determine whether the reference was a valid or an invalid memory access
If the reference was invalid, we terminate the process. If it was valid but we have not yet brought in the page, we now page it in
We find a free frame (by taking one from the free-frame list, for example)
We schedule a disk operation to read the desired page into the newly allocated frame
When the disk read is complete, we modify the internal table kept with the process and the page table to indicate that the page is now in memory