CS 111 Scribe Notes: Lecture 14

Beayna Grigorian & Saro Meguerdichian

• Hire better programmers! (only a partial solution).
  
  
• Formal verification (program proving) → needs work.
  
  
• Runtime checking (e.g. rewrite C code in Java) for subscript-out-of-bounds errors, etc.
  e.g. a[i] → if (!(i < (unsigned) N)) abort();
  
  
• Add hardware support for base + bounds registers.
  e.g. RAM
  
  
  
  • Partial solution: prevents 1 process from messing up whole system.
    
    
  • Downsides:
    
    
    • Doesn't catch individual errors.
      e.g. errors within accessible memory
      
      
    • Suppose a process sets base = 0 & bounds = infinity.
      (solutions make these priviledged registers)
      
      
    • Shared memory doesn't work well.
      
      
      
      
      * Can still cause errors in shared memory & stomp on each other's shared data!
      
      
    • Hard to grow amount of memory given to a process.
      
      
    • Worry about relinking code each time you load it.
      (most common solution: prohibit code from containing absolute addresses i.e. require relocatable code)
      
      

Idea: allow multiple base-bounds pairs (1 per region -- say 8). + For each pair, have permission bits.    useful permissions: r - - r w - r w x r - x - - x (?) + Can share text region to save RAM. - Doesn't scale well to dynamic linking. - 8 is an arbitrary limit, need more! (use segmented memory). Shared memory can be anywhere and there can be many shared memory regions.

• Segmented Memory: N base-bounds pairs in a table in RAM.
  * Critical problem: heap can't easily grow!
  
  
• Idea: don't force segments to be contiguous.
  
  
  
  
  • Normally done with fixed-size pages.
    
    
  • This makes segments unnecessary, to some extent!
    
    

• v != p (usually).
  
  
• p = f(v)
  This must be fast! It's done in hardware (don't usually need to go the other way, unless for garbage collection, etc.)
  
  
• Making "p = f(v)" efficient:
  * Note: any fixed function that you come up with (using the idea that it can be calculated very efficiently) will only work for a limited # of processes.
  
  
  • Simplest approach → linear page table
    i.e. int f(v) { return tab[v]; }
    
    Page table located in RAM & it uses itself to keep processes from modifying its own page table.
    
    To signify that a page table entry is invalid (i.e. page doesn't exist), you can have holes in the page table (e.g. if tab[v] == FAULT then page isn't there) or compress the page table and use base-bounds registers.
    
    
    
    
  • 2-level page table (pmap implemented in hardware)

    
    size_t pmap (size_t vpn) {
    	size_t hi = vpn >> 10;
    	size_t lo = vpn & ((1 << 10) - 1);
    	size_t *lopage = PAGETABLE[hi];
    	if (lopage == FAULT)
    		return FAULT;
    	return lopage[lo];
    }
    

    * If this returns FAULT, hardware traps, enters kernel, kernel is told pc address that faulted. Kernel can:
    
    
    1. Terminate the program.
       
       
    2. Alter the page table, then retry instruction. For:
       
       
       1. Lazy allocation of RAM.
          
          
       2. Support programs with greater RAM than machine has.
          
          
          • Works only if RAM is NOT accessed randomly.
            
            
          • Runs at disk speed!
            
            
          • RAM is a "cache for disk."
            
            
          • Some other functions to implement:

            
            off_t swapmap (proc, vpn) {
            	return disk address or FAULT;
            }
            

            
            void pfault (va     ) {
            	if (swapmap(current process, va) == FAULT)
            		kill(current process);
            	else {
            		(p, va') = removal_policy();
            		pa = p->pmap(va');
            		write pa to disk at swapmap(p, va');
            		pa->pmap(va') = FAULT;
            		read pa from disk at swapmap(currentprocess, va);
            		current process->pmap(va) = pa;
            	}
            }
            

            Gets pid & va for a process that doesn't need to be cached (some pages like the page holding pfault cannot be swapped out!)