Virtual Memory : Implementation

The Virtual memory is implemented using the hardware (MMU) and software (operating system). It abstracts from the real memory available on a system by introducing the concept of virtual address space, which allows each process thinking of physical memory as a contiguous address space (or collection of contiguous segments). The main goal of virtual memory is to map virtual memory addresses generated by an executing program into physical addresses in computer memory. This concerns two main aspects: Address translation (from virtual to physical) and Virtual address spaces management. The Address Translation is implemented on the CPU chip by a specific hardware element called Memory Management Unit or MMU. The Virtual address spaces management is provided by the operating system, which sets up virtual address spaces (i.e., either a single virtual space for all processes or one for each process) and actually assigns real memory to virtual memory. Furthermore, software within the operating system may provide a virtual address space that can exceed the actual capacity of main memory (i.e., using also secondary memory) and thus reference more memory than is physically present in the system.

The primary benefits of virtual memory include freeing applications (and programmers) from having to manage a shared memory space, increasing security due to memory isolation, and being able to conceptually use more memory than might be physically available, using the technique of paging. Almost every virtual memory implementations divide a virtual address space into blocks of contiguous virtual memory addresses, called pages, which are usually 4 KB in size.

In order to translate virtual addresses of a process into physical memory addresses used by the hardware to actually process instructions, the MMU makes use of page table. A page table is the data structure used by the Operating System to store the mappings between virtual addresses and physical addresses. The MMU stores a cache of recently used mappings out of those stored in the whole OS page table, which is called Translation Lookaside Buffer or TLB. The figure below describes the address translation task step by step :

Step 1 : When a virtual address needs to be translated into a physical address, the MMU first searches for it in the TLB cache.

Step 2 : If a match is found (TLB hit) then the physical address is returned and the computation simply goes on (in step 2).

Step 3 : Otherwise, if there is no match for the virtual address in the TLB cache (TLB miss), the MMU searches for a match on the whole page table, i.e., page walk.

Step 4 : If this match exists on the page table, this is accordingly written to the TLB cache (3.a.). Thus, the address translation is restarted from Step 1 and 2, so that the MMU is able find a match on the updated TLB .

Unfortunately, page table lookup may fail due to two reasons. The first one is when there is no valid translation for the specified virtual address (e.g., when the process tries to access an area of memory which it cannot ask for). Otherwise, it may happen if the requested page is not loaded in main memory at the moment (an apposite flag on the corresponding page table entry indicates this situation). In both cases, the control passes from the MMU (hardware) to the page supervisor. The page supervisor is part of the operating system creates and manages page tables. If the hardware raises a page fault exception, the paging supervisor accesses secondary storage, returns the page that has the virtual address that resulted in the page fault, updates the page tables to reflect the physical location of the virtual address and tells the translation mechanism to restart the request. In the first case, the page supervisor typically raises a segmentation fault exception.

Step 5 : In the second case, instead, a page fault occurs,  which means the requested page has to be retrieved from the secondary storage (i.e., disk) where it is currently stored. Thus, the page supervisor accesses the disk, re-stores in main memory the page corresponding to the virtual address that originated the page fault (Page swap at above Figure), updates the page table and the TLB with a new mapping between the virtual address and the physical address where the page has been stored (Step 4), and finally tells the MMU to start again the request so that a TLB hit will take place (1 & 2).

As it turns out, the task of above works until there is enough room in main memory to store pages back from disk. However, when all the physical memory is exhausted, the page supervisor must also free a page in main memory to allow the incoming page from disk to be stored. To fairly determine which page to move from main memory to disk, the paging supervisor may use several page replacement algorithms, such as Least Recently Used (LRU). Generally speaking, moving pages from/to secondary storage to/from main memory is referred to as swapping, and this is why page faults may occur.

Next Topic :

No comments:

Post a Comment