Operating Systems 2015F Lecture 13

Video

The video for the lecture given on October 21, 2015 is now available.

Notes

----------

Project
 - know what you are curious about
 - digging into the kernel

Interview
 - purpose: are you hacking the kernel
 - test of how bloody are your knuckles
 - don't talk to me until you've spent at least 10 hours on your own looking at code (outside of tutorial)
 - for example, what code runs when I press a key?
 - pass/fail (100 or 0) - and you can come back
 - you can come in starting NOW
 - I am available Wednesday and Friday during the break
 - email to make an appointment, giving at least 3 times you can come in for 15-30 minutes.
 - after, Mondays and Tuesdays are best
 

Virtual Memory
 - TLB stores a cache of virtual to physical address mappings
   - cache of WHAT
 - need a data structure that maps an entire address space (2^32 or 2^64) memory locations.
    - virtual and physical address space may be different
    - generally you have less physical memory than virtual memory,
      so can use fewer bits in physical addresses
      - for 64 bit systems, physical addresses are like 48 bits
        or a few more
    - but sometimes you get physical addresses that are larger that virtual addresses
  - apple 2's had an 8 bit processor with 16 bit addresses
     - to address more than 64K, you did "bank switching",
       one set of 16K addresses were mapped onto arbitrary banks of upper memory, using a "selector" address.
  - for 32 bit addresses, that's 4G of RAM
     - intel makes processors with extensions to access more ram (PAE)
     - each process is limited to 4G, but kernel deals with mess of extra RAM


  - mapping memory is expensive, do it in chunks
    - should the chunks be variable or fixed sized?
    - variable sized chunks are too hard to pack
        (segments, with a base address and a bound address)
	segments are still used in executable file formats
	and for setting permissions on ranges of memory
	(sometimes)
    - fixed sized chunks of memory are pages
       4K or 8K
       sometimes really big (2M), for mapping video memory
    - pages are loaded into memory frames in RAM

  - map pages to frames (equal size)
  - mapping data structure needs to be sparse
     - not use memory for unallocated areas
  - must store data structure in a set of pages
  - this is a page table
     - but it is really a tree

  - leaves are data pages
  - nodes are pages
  - each internal node is an array of page table entries (PTEs)
    - evenly fit into page of course

  - with 32 bit addresses and a 4K page
     - [ virt page # ][ offset #] = virtual address
     - offset is used to index into actual page
     - virt page # is used to walk page table
     - how many bits?  12 bits for offset, 20 for virt page #

     - page table has to map 2^20 => 2^20
     - physical address = [ frame # ][ offset #]
       - to translate, map page to frame number and copy offset
     - PTE = [ frame # ][ metadata ]
       - frame # is 20 bits, 12 bits of metadata
       - takes up 32 bits
     - how many PTEs in a page?  4096 bytes per page/
                                 4 bytes per PTE
				 = 1024 PTEs in a page
     - tree has 2 levels.  Top node and middle nodes
       - top node has 1024 "pointers" (PTEs)
       - middle nodes each have 1024 PTEs, each referring to data
         or code pages
       - note any PTE may be marked as "not present"
     - So for a 4K of address space, you need 3 pages (12K)
       - 1 top, 1 middle, and 1 data

  - why care?
    - page tables are managed by the kernel
      - specifically, every process has its own page table
        (virtual memory mapping)

  - what metadata is stored in a PTE
    - permissions (read, write, exec)
    - valid?  (allocated memory?)
    - present? (in RAM?)
    - dirty? (has it been modified since loaded)