Virtual Memory

Disclaimer:
    All information furnished here is my understanding of VM. It might be wrong. If u r misled by this article by any chance, i dont take any responsibility. Thats up to you.

Contents:
               By defn, VM is to allow an application see more memory than installed on the system. Unix semantics define VM as "RAM is a cache for disk". Demand loading, mmap services, swapping are all coz of VM. The onus of implementing the VM is shared by the operating system and the hardware. In this small article, I'd like to discuss issues involved in implementing VM. I defer the swapping issue to sometime later. Probably, one day i'd write about it. 
        An OS which supports Virtual Memory, has to support multiple address spaces which should co-exist with one another. The address space size is limited by the number of address lines the processor supports. On a 32-bit machine, the address space is 4Giga bytes. On a processor with 36 address lines, it is 64 Gigabytes. A typical "C" program accesses its address space as "Pointers". A typical assembly program can access it's address space as "segment:offset" addressing (x86 specific).Typically, memory need of applications are not as big as Gigs. Nonetheless such sparse address spaces are not a problem. Each process thrives on its address space. The address space holds all text, data of the owner. The owner of an address space may typically be a process. A typical application in a Virtual memory system, plays only in the vitual domain. It never sees anything physical. Populating a virtual address space may cause page-faults which should be suitable handled by the operating system. The below figure depicts the typical senario..

An address space is an abstract entity. It assumes significance when it is assosiated with a process. So "process" is at a higher abstraction than the address space. Processes encompass so many other things other than just an address space. Nonetheless, address space is indispensable for a process. Processes need not worry about the nuances of mapping. Thats taken care by the OS.

The operating system has the following responsibility in order to support various address spaces.
    1. OS should maintain data structures describing the areas of the address space which are mapped and which are free. A virtual address may not necessarily be always mapped to physical memory. Unix like systems, give Pointer access to file system objects via the "mmap" system call. In such a case the OS should know which virtual addresses of the process's address space, are mapped to the file. In case of a page-fault in such an address, the OS brings pages from disk to primary memory and sets up the mapping between the faulted-va and the physical address. Thus there should be enough information for the page-fault handler to fix a fault.  Fine, how do they do it ?
                    Here comes the concept of "segments". A segment is a range of virtual addresses in an address space. Typically a segment is created for a particular purpose. For exp, a segment of kernel virtual address space may be used for kernel memory allocation,  a segment in user address space may map a file, etc. When there is a page-fault in the system, the handler identifies the host address space, and localises the faulted-address to a segment in the address space. Then it calls an appropriate segment specific handler to handle the fault. The segment specific handler knows what to do when a page-fault occurs. For this, the segment may need to maintain private information. like, what this segment is meant for. For exp, In "SVR4", most of the segments are "segvn" segments. "segvn" stands for "Vnode Segments". In SVR4 semantics, "Vnode" is a generic abstraction of a file. Thus "segvn" segments are those that have originated from a file.i.e. They have one-to-one correspondence with a file in the disk. All of the "TEXT" segments ( TEXT , means executable code) of a process are "segvn" segments. Thus the private information for such a segment could be a pointer to a "vnode". When the segment-specific-pagefault handler is called, he at once knows that he has to bring data from a file in the disk by calling a Vnode Read Operation. Lets say a "segvn" segment starts at virtual address "x" in a process's address space and its length = "len" bytes. Let it represent the begining of a file "xxx.txt". Thus private data of this segment would typically be a "vnode" ptr and an offset 0. When a page-fault occurs at virtual address "x + 10000" where 10000 <=  len, the page-fault handler knows that the user is trying to access 10000th byte in the file. Immediately he gets the data from the file into primary memory and maps the faulted-va to the physical memory containing the data. Thus the " handler + private data " of the segment forms the heart of a segment. Apart from page-fault handler there can be so many operations that can be performed on a segment. Thus naturally, segments can be viewed as a set of functions acting on a private data. i.e. a segment is an object in an address space. An address space contains group of such objects.
    2. Apart from maintaining segments, the OS has to maintain information about the mapping of the address space. Mathematically the problem can be expressed as,

  f1 (as,va) = pa. ( This is a many to one function ). The mapping is done by page-tables and the way it's done is processor dependent.

  f2(pa) =  The set of all {as,va} such that f1 (as,va) = pa. (This is a 1 to Many function ) Literally it means, all the virtual addresses in different address spaces which own ( map ) the physical page. Why is this needed ? Consider the following situation. While swapping a physical page to disk, the OS needs to know about all the mappings to the physical page. It has to invalidate all the mappings to the physical address before swapping the contents of the physical page to disk.

Moreover, if we consider the "address space" as an entity, the segments and the mapping elements assosiated with the address space become the heart of the entity. All these can be clubbed together and an "address space" can be described as a functional unit. There are lot of functionality this entity can provide. For exp, the pith of the "fork" system call in UNIX is "DUPLICATION" of an address space. Another yet functionality is SWAPOUT. An entire address can be swapped out. Another functionality is LOCKING of  an address space into memory. Another could be a "DESTRUCTION" of an address space. Yet another could be a COMMUNICATION between address-spaces. Thats called IPC. However Unix like systems dont implement IPC this way. But i think WinNT does it this way. And there are lot more functionalities which can be offered by an address space. These functionalities are ofcourse acheived by manipulating the underlying segments and mapping elements.( I use the term mapping elements in a broad sense. PageDirectories and PageTables as in I386, SPARC has it's own mapping elements and so on). The job of the VM manager is to manage address spaces. For this, he might need to co-operate with physical memory manager  to get memory for maintaining data structures and may be also with the SWAP sub-system.

                                                                                                                               Sarnath.K 
                                                                                                                               (12/APRIL/2001)

Thursday, April 12, 2001