#  -*- mode: org -*-
#+STARTUP: indent
 
6.033 2011 Lecture 5: Operating System Organization

* Plan for next few lectures
** last lecture: enforcing modularity and naming
** just talked about one module per computer (c/s)
    more details on net-based c/s later in course
** now: modules within one computer
L5: o/s organization -- tools for enforced modularity
L6 + L7: managing multiple activities in one computer
L8: virtual machines

* O/S Goals
multiplexing: one computer, many programs
protection: enforced modularity, bugs, privacy
cooperation: help programs interact / communicate / share data
portability: one app runs on many h/w configs
performance: improve, and don't get in the way

* Key approaches to achieve those goals?
virtualization
abstraction

* Virtualization
** computer has h/w resources
a few CPUs, one mem system, one disk, one net i/f, one display
** but you want to run many programs (editor, compiler, browser, X, &c)
** idea: give each program a set of "virtual" resources
    as if it had its own computer
    works well w/ CPU, memory
** simplifies application programming (no need to consider other programs)

* Memory

** No virtualization:
diagram: NO MMU
indexed with "physical address"
let us say 32-bit addresses
could have up to 4 GB of DRAM
example: LD R4, 0x2020
problem: every program can write every memory location

** Virtual Addressing Idea
 diagram: MMU, two arrays of memory cells
 set of arrows from left to right
  "virtual addresses" (names) vs "physical addresses" (values)
    s/w ONLY loads/stores using virtual addresses
    phys addrs ONLY show up in the mapping table
  conceptually, translations for all 2^32  (lookup using table)
    some refer to physical memory
    some don't translate
  how to implement?
    if per-byte mappings, 16 GB!
    not practical to have a translation table with entry per byte addr

** Page tables
*** 6.004 introduced page tables to do better  (slide with x86 picture)
*** Example:
  page table:
    0: 3 (i.e. phys page 3)
    1: 0
    2: 4
    3: 5
  register R3 contains 0x2020
  LD R4, (R3)
  CPU sends (R3)=0x2020 to MMU
    virtual page number is 2
    offset is 0x20
    thus pa = 4*4096 + 0x20 = 0x4020
  MMU sends 0x4020 on wires to DRAM system
*** give each program its own address space by given it a separate page table
*** *physical* address of page table in page map register

** Naming view:
virtual address is name
physical address is value
lookup algorithm implemented by MMU using map
context: page map register
hiding: program cannot name values outside of its map!
sharing: same value can be mapped into different maps
level indirection enables other usages (demand paging, zero-fill, copy-on-write)

** Protecting page table register: "supervisor mode"
*** notice we're not directly protecting access to DRAM
  prog can r/w DRAM if phys addr mentioned in page table
  you could imagine separate mapping and protection
  combined for efficiency
  implication: program can't be allowed to modify its page table
*** add kernel/user flag in the CPU hardware
if set, sensitive instructions can execute instruction
if not set, sensitive instruction results in error
e.g., sensitive instruction:  mov add, page-table-register

* Kernel
** software than runs with kernel-flag enabled is call the "kernel"
** orderly transfer from user to kernel on interrupts:
  1. set supervisor flag
  2. jmp into kernel
  -> no uncontrolled user setting of supervisor flag
  -> no random user->kernel jumps
  -> can't trust user stack, syscall arguments, &c
** transfer explicit or implicit:
int instruction in user code -> transfer
interrupt/fault -> transfer
** from kernel to user: easy
kernel is trusted
it can setup the pmap register, etc.
invoke reti instruction to return to user mode

* Virtualization example: CPU
** enforcing multiplexing one CPU among n programs
so each program thinks it has a dedicated CPU
give the CPU to each in turn
** typical mechanism:
h/w timer that interrupts 100 times/second
interrupt transfers control to kernel
kernel saves registers of current program (CPU registers)
kernel loads previously-saved registers of another program
kernel calls reti
(save/load called a context switch)
** transparent to the programs!
** more to say about this in the next few lectures


* Abstraction
** virtualization good for memory, cpu, but not for other resources
** abstraction: new interface to underlying h/w resources
change interfaces to allow sharing, portability
** Abstraction examples:
disk -> file system 
display -> window system
DRAM -> heap w/ alloc, free
network cable -> pipes
** there is often a flavor of virtualization in the abstractions

* What does an abstraction look like?
** usually presented to programmer as set of "system calls"
looks like procedure, we'll see it's different internally
** major challenge: designing good abstractions
** example of good one: FS from UNIX paper see slide (l5.ppt)
 chdir asks the kernel to change dir
  rest of code reads a file

main() {
  int fd, n;
  char buf[512];

  chdir("/usr/rtm");

  fd = open("quiz.txt", 0);
  n = read(fd, buf, 512);
  write(1, buf, n);
  close(fd);
}

* How to manage / implement abstractions?
** as a library of convenient functions?
no: we want to enforce modularity!
e.g. want prog to use disk *only* via FS abstraction
** idea: kernel *enforces* abstractions
user program can invoke methods on abstraction only through system calls
systems calls are a special type of interrupt
interrupt number is the system call number
** kernel can access all memory, and hardware devices
the kernel better not have bugs!
** user program can *only* directly use own memory, nothing else
much more OK if user program has bugs, only hurts itself

* how does kernel get at user memory?
** very convenenient for kernel to use user pointers
  e.g. read(fd, buf, 512)
** kernel and current program typically live in same address space!
kernel in high addresses
user in low addresses
** each PTE has "S" bit
means virt. address only useable if supervisor mode

* how is the kernel arranged internally?
  example: UNIX / Linux
  one big C program, no hard internal divisions, but has structure
  complex: 10,000 source files, 300+ system calls

* how to avoid chaos?
  many internal simplifying interfaces -- OO style
  e.g., all storage devices look the same to the file system
    USB flash key, hard disk, dozens of others
  some modularity forced by desire to make most code optional
    loadable kernel modules
    can't depend on something that might not be present
  so not as complex as it looks

* kernel must enforce modularity between different programs
  some kernel subsystems control access by user ID
    each Linux program and file has a "user ID"
    my processes can look at each others' memory
    kill each other
    read and write each others' files
  I can grant r/w access to my files to other users
    FS code enforces this kind of access control
  kernel acts as a trusted server to control sharing

* this style of kernel often called "monolithic"
  kernel is a single huge program
  hard to reason about, hard to optimize
  a bug anywhere can cause malfuction or crash of entire machine
  there are other ways to organize a kernel!
  
* the microkernel vision
  goal: move services out of kernel into user-level server programs
    FS, net, windows/graphics
    applications send/recv messages -- "IPC"
  kernel supports only a few system calls
    send/recv IPC messages
    manipulate processes and memory

* why are microkernels attractive?
  enforced modularity between server programs
    a bug in network code won't crash file service
  elegant, small kernel
    fewer bugs in supervisor-mode code
    easier to optimize since only does a few things
  non-O/S software can also have client/server structure
  once all interaction via msgs, maybe easy to move services across net
    e.g. FS server machine

* where did microkernel idea go?
  huge enthusiasm when first proposed (late 1980s)
  implementations were slow around 1990 -- e.g. Mach
    many messages, esp if you have many servers
    messages MUCH slower than monolithic inter-"module" fn calls
  hard to fully exploit enforced modularity of O/S services
    crashed FS server may still wedge whole system
    maybe solvable but harder than it looked
  tended to end up with a few huge servers, so little modularity win
    painful to separate into lots of little servers
    also integration allowed better algorithms
      e.g. memory balance between file cache and process memory
  easy to add microkernel-style messaging, user-level servers
    X, sshd, DNS, apache, database, printer

* a third approach to enforced modularity: virtual machine monitors
  one machine, many virtual machines
  each VM strictly simulates a complete real computer
    and strictly separates the VMs
  we will cover this approach in the week after next

* Summary
  o/s virtualizes for sharing/multiplexing
  abstracts for portability and cooperation
  provides enforced modularity in two useful ways:
    program / kernel
    program / program
  next: specific techniques for client/server on single computer