Memory Abstraction

Memory Abstraction

1. Address Space

   • Is the set of addresses that a process can use to address memory.
   • Address space was invented to solve two problems if we allow multiple applications to be in memory at the same time without interfering with each other 1.Protection 2.Relocation

2. Base and Limit Register

   • When these registers are used, programs are loaded into consecutive memory locations wherever there is room and without relocation during loading.
   • When a process is run, the base register is loaded with the physical address where is the program begins in memory and the limit register is loaded with the length of the program.
   • Every time a process  references memory either to fetch an instruction or read or write a data word, the CPU hardware automatically adds the base value to the address generated by the process before sending the address out on the memory bus. Simultaneously, it checks whether the address offered is equal to or greater than the value in the limit register, in which case a fault is generated and the access is aborted.
   • A disadvantage of relocation using base and limit register is the need to perform an addition and a comparison on every memory reference. Comparisons can be done fast, but additions are slow due to carry-propagation time unless special addition circuits are used.

3. Memory Overload

   • Swapping
     • Consists of bringing in each process in its entirety, running it for a while, then putting it back on the disk. Idle processes are mostly stored on disk, they do not take up any memory when they are not running.
     • When a process brought back from disk to memory at a different location, addresses contained in it must be relocated, either by software when it is swapped in or by hardware during program execution.
     • Memory Compaction
       • When swapping creates multiple holes in memory, it is possible to combine them all into one big one by moving all the processes downward as far as possible.
       • It is usually not done because it requires a lot of CPU time.
       • Memory Allocation
         • If the processes are created with fixed size that never changes, then the allocation is simple, the operating system allocates exactly what is needed, no more and no less.
         • If the processes grows by dynamically allocating memory from a heap, a problem occurs whenever a process tries to grow. 1.If a hole is adjacent to the process, it can be allocated and the process is allowed to grow into the hole. 2.If it is adjacent to another process, the growing process will either have to be swapped out to create a large enough for it, or one or more processes will have to be swapped out to create a large enough hole. 3.If a process cannot grow in memory and the swap area on the disk is  full, the process will be suspended unit some space is freed up or killed.
         • If it is expected that most processes will grow as they run, it is probably a good idea to allocate a little extra memory whenever a process is swapped in or moved, to reduce the overhead associated with moving or swapping processes that no longer fit in their allocated memory.
     • Memory Management
       • Bitmap
         • With bitmap, memory is divided into allocation units as small as a few words and  large as several kilobytes. Corresponding to each allocation unit is a bit in the bitmap, which is 0 if the unit is free and 1 if it is occupied. The size of allocation unit is an important design issue.The smaller the allocation unit, the larger the bitmap.The bigger the allocation unit, the smaller the bitmap, but appreciable memory may be wasted in the last unit of the process if the process size is not an exact multiple of the allocation unit.
         • A bitmap provides a simple way to keep track of memory words in a fixed amount of memory because the size of the bitmap depends only on the size of the memory and the size to the allocation unit.
         • The main problem is that when it has been decided to bring a k-unit process in to memory, the memory manger must search the bitmap to find a run of k consecutive 0 bits in the map. Searching a bitmap for a run of a given length is a slow operation.
       • Free lists
         • first, next,, best and worst fit can be speeded up by maintaining separate lists for processes and holes. In this way, all of them devote their full energy to inspecting holes, not processes. The inevitable price that is paid for this speedup on allocation is the additional complexity and slowdown when deallocating memory, since freed segment has to be removed from the process list and inserted into the hole list.
         • first fit
         • next fit
         • worst fit
         • quick fit
           • Maintains separate lists for some of the more common sizes requested.
         • best fit
           • If distinct lists are maintained for processes and holes, the hole list may be kept sorted on size, to make best fit faster. When best fit searches a list of holes from smallest to largest, as soon as it finds a hole that fits, it knows that the hole is the smallest one that will do the job, hence the best fit, No further searching is needed, as it is with the single-list scheme. With a hole list sorted by size, first fit and best fit are equally fast, and next fit is pointless.
   • Virtual Memory
     • Allows programs to run even when they are only partially in main memory.
     • The basic idea behind virtual memory is that each program has its own address space, which is broken up into chunks called pages.
     • pages
       • Each page is contiguous range of addresses. These pages are mapped onto physical memory, but not all pages have to be in physical memory at the same time to run the program. 
       • When the program references a prat of its address space that is in physical memory, the hardware performs the necessary mapping on the fly. When the program references a part of it s address space that is not in physical memory, the operating system is altered to go get the missing piece and re-execute the instruction that failed.
       • Present/Absent bit keeps track of which pages are physically present in memory.
       • paging
         • The virtual address space consists of fixed-size units called pages. The corresponding units in the physical  memory are called page frame. The virtual pages and page frames are generally the same size.
         • Transfer between RAM and disk are always in whole pages.
         • MMU
           • ON computers without virtual memory, the virtual address is put directly onto the memory bus and causes the physical memory word with the same address to be read or written. When virtual memory is used, the virtual addresses do not go directly to the memory bus. Instead they go to an MMU that maps the virtual memory onto the physical memory.
           • page fault
             • When the MMU noticed the virtual page is not mapped to physical address to causes the CPU to trap to the OS. The operating system picks a little-used page frame and writes its contents to the disk if it modified.  It then fetches the page that was just referenced into the page frame just freed, changes the map, and restarts the trapped instruction. 
         • virtual pages
         • page frames
     • page tables
       • The virtual page number is used as an index into the page table to find the entry for that virtual page. From the page table entry, the page frame number is found. The page frame number is attached to the high-order end of the offset, replacing the virtual page number, to form a physical address that can be sent to the memory.
       • page table entry
         • Note that the disk address used to hold the page when it is not in memory is not part of the page table. The reason is simple. The page table holds only that information the hardware needs to translate a virtual address to a physical address. Information the OS needs to handle page fault is kept in software tables inside the OS. The hardware doesn't need it.
         • page frame
         • present/absent
         • protection
         • modified
           • This bit is of value when the operating system decides to reclaim a page frame. If the page in its has been modified (dirty), it must be written back to the disk. If it has not been modified (clean), it can just be abandoned since the disk copy is still valid.
         • referenced
           • This bit is set whenever a page is referenced, either for reading or writing. Its value is used to help the operating system choose a page to evict when a page fault occurs.
         • caching disabled
     • Speeding up paging
       • In any paging system, two issues must be faced: 1.The mapping from virtual address to physical address must be fast. 2.If the virtual address space is large, the page table will be large.
       • single page table
         • A single page table consisting of an array of fast hardware registers, with one entry for each virtual page, indexed by virtual page number. When a process is started up, the operating system loads the registers with the process' page table, taken from a copy kept in main memory. During process execution, no more memory references are needed for the page table.
         • Advantages: It is straightforward and requires no memory references during mapping.
         • Disadvantages: 1.It is unbearably expensive if the page table is large, it is just not practical most of the time. 2.Having to load the full page table at every context switch would completely kill performance.
         • At the other extreme, the page table con be entirely in main memory. All the hardware needs then is a single register that points to the start of the page table. This design allows the virtual-to-physical map to be changed at a context switch by memory references to read page table entries during the execution of each instruction, making it very slow.
       • TLB
         • Problem: Since page table is in memory, each instruction which needs one memory reference without paging will need two memory references which decreases the performance by half. Solution: The observation that most programs make a lot of references to small number of pages, not the other way around. Thus only a small fraction of the page table entries are heavily read; the rest are barely used at all. 
         • TLB is a small hardware device for mapping virtual addresses to physical addresses without going through the page table.
         • TLB function: 1- Hardware checks in parallel all the entries. 2. Found ? and no protection fault, the page frame is taken. 3. Not found, page table lookup. (page table walk) 4. Evict one TLB entry and replace it with the page table. 5.When an entry is purged from TLB, the modified bit is copied back into the page table entry in memory. The other values are already there.
         • In RISC, SPARC, MIPS and HP PA machines, the TLB handling is done by the OS (software).
         • To improve performance on machines that do TLB management in software, one approach attacks both reducing TLB misses and reducing the cost of a TLB miss when it does occur. To reduce TLB misses, sometimes the operating system can use its intution to figure out which pages are likely to be used next and to pre-load entries for them in the TLB.
         • soft miss
           • Occurs when the page referenced is not in the TLB, but is in memory. 
           • minor page fault
             • If the page is not in the process' page table but in another process page table.  In this case we don't need to access the disk again, but merely map the page appropriately in the page tables. 
         • hard miss
           • Occurs when the page itself is not  in memory.  (major page fault)
         • segmentation fault
           • The program simply accessed an invalid address and no mapping needs to be added in the TLB at all.
     • page tables for large memories
       • multilevel page tables
         • It is a virtual address that is partitioned into a PT1 field, PT2 field and Offset field.
         • The secret to the multilevel page table method is to avoid keeping all the page tables in memory all the time. In particular those that are not needed should not be kept around. 
         • When a virtual address is presented to the MMU, it first extracts the PT1 field and uses this value as an index into the top level page table.  The entry located by indexing into the top level page table yields the address or the page frame number of a second level page table.  The PT2 field is now used as an index into the selected second level page table to find the page frame number for the page itself. 
         • inverted page tables
           • In this design, there is one entry per page frame in real memory, rather than one entry per page of virtual address space.
           • Although inverted page tables save lots of space, at least when the virtual address space is much larger than the physical memory, they have a serious downside: virtual-to-physical translation becomes much harder.  When process n references virtual page p, the hardware can no longer find the physical page by using p as an index into the page table. Instead, it must search the entire inverted page table for an entry (n, p). Furthermore, this search must be done on every memory reference, not just on page faults. 
           • The way out of this dilemma is to make use of the TLB. If the TLB can hold all of the heavily used pages, translation can happen jsut as fast as with regular page tables.