412_notes

8/29 (Discussion)

int * const blah --> the pointer cannot be changed
const int *blah  --> the pointer is to a const int
            
consider:
	arr = {1,2,3,4,5}
	a = arr
	c = a
	
	++*a;        --> dereferences a and then increments that value
	*a++         --> dereferences a and then increments the pointer
	*c = (*a)++; --> adds dereferenced c and a, then increments a 

For macros, consider this:
    #define MULT(a,b) (a * b)
    	    --> This does NOT work with MULT(1+2,3+4) OOP
Try instead:
    #define MULT(a,b) ((a) * (b))

gcc -D SAMPLE --> defines the given macro SAMPLE

gcc -E --> will show code after preprocessing

8/30 (Lecture)

intro stuff

8/31 (Discussion)

vagrant up --> initialize vm
vagrant ssh --> get into vm
cd /vagrant is a shared file (really wherever you run VM from becomes the 
 vagrant directory)
 	 you should run vagrant ssh from the project folder
vagrant destroy (you might lose local changes WITHIN the vm not in shared dir)
vagrant halt --> will shutdown VM instance but not remove from disk
	Both use "vagrant up" to start back up
You can run GeekOS from both local machine and VM

kassert can be helpful for finding errors

gdb: watch variable tracks variable changes
     conditional breaks

9/6 (Lecture)

Project 1: Fork and exec

   After fork, we have 2 user processes (user address space)
      Each has a unique Kernel_Thread (KT)
         Each KT has its own Stack -> you must decide what Stack is inherited
            Each KT has a unique userContext (UC)
               Each has an individual set of file descriptors (FD)
	          Each FD points into the same File Descriptor Table (FDT)
      Global variables start out the same, but are updated separately
      EIP is copied into new process
      Spawn (maybe in user.c or userseg.c) has most of what we need	    
      In GEEKOS, no stdin, stdout, stderr

User Process vs. Kernel
   Process believes it has its own CPU
   Process essentially believes there is infinite memory
   Process believes there are "files" and "directories"
   Process believes there is "Wall" between it and other processes
   IPC - Inter-Process-Communication
      pipe, signal, shared memory, message passing, network sockets

Virtual Memory
   Any time the address in a register is different from the physical address
   Can be used to provide illusion of more space
   0xfffffff
   ________
   stack (grows down)
   ________
   heap (grows up)
   ________
   data
   ________
   txt
   ________

   ________
   0x00000000	

   segmentation allows >1 instances of the same program
   nm (executable) -> shows addresses of all symbols in executable
      first usable page starts at 0x1000 because we want 0 to be reserved
      for Null

Pointer Alignment
   (int *) -> should be 4-byte aligned
      should be a multiple of 4
   (char *) -> should be 1-byte aligned
      should be a multiple of 1
   consider:
      struct foo {int a; char b; int c;};
         sizeof(foo) = 12 bytes (not 9 due to int 4-byte alignment)

9/7 (Discussion)

   Project 0:
      Ensure that everything is appropriately freed in Close
         Try a test that repeatedly calls Pipe and Close

   Project 1:
      Mutex will probably be the way to go		
      Take a look at Spawn (in user.c)
         Spawn unsurprisingly Spawns a user process      
      Each process has a kernel_thread associated with it
         Each of these has a user_context
      Jump around k_thread struct and User_Context struct (user.h)
      Also Sys_Spawn -> look here also
      Mutex in sync.c (I think)

   gdb notes:
      run "make dbg run;make dbg"
      b "Sys_Spawn" --> breakpoing at Sys_Spawn function 
      s -> step into
      n -> step over
      c -> keep going till next breakpoint
      printx --> print variable in hex
      struct notation from c still works for print

9/8 (Lecture)

   Project 0: 
      Too much output being printed by students
         try :
            fn() {
      	       static int ive_complain;

	       if (!ive_complained) {
	          Print("waaa!");
	          ive_complained = 1;
	       }
	fixed size buffer:
	   allocate little buffers in a list
	   allocate a single buffer and shift/advance (I shift)
	      advance would probably be better, but I should check changes
	      for shift I should use memmove, not memcpy

   Process States:
      Running:
         to get to Waiting:
	    waiting for input(device)? child process to terminate? mutex?
	 to get to Runnable:
	    dispatcher (I think) can force an active process into the run queue
      Runnable:
         to get to Running:
	    piece of software (dispatcher) pops process off of run queue
      Waiting (Blocked):
         to get to Runnable:
	    when the thing we were waiting for happens
	    (unblocked/awakened from the wait queue)

      for all process in Runnable (on run queue):
         how do we decide which to run?
	 how do we manage the Run Queue?
	    - priorities on processes
	       * most complex last
	       * how long it's been waiting
	          - longer waits first, avoid starvation
	       * how much longer it will run
	          - longer run last, allow short jobs responsive
		  - can we do this? (external spec?, predicter?)
	       * how much resources it will use
	          - can be useful in event of conflict on resources
		  - possible justification to suspend process
	       * solving priority inversion
	          - priority inversion
		     * parent important, calls wait on child
		     * child not important (doesn't fit above criteria)
		     * high priority waiting on low priority
		  - possibly temporarily bump up a low priority process
	       * Avoiding starvation is particularly important
	       * Allowing short commands to be responsive is also important

      Scheduler (three levels):
         long-term scheduling:	
	    deciding which process to run (or really start) 
	       - associated with "batch"
	          * old-school approach when punch cards were a thing
		  * finish one process, move onto the next
		  * as opposed to time-sharing
		     - we start a job whenever we want (conventional for us)
	 medium-term scheduling
	    decide which processes to suspend
	       - frequently not done
	 short-term scheduling
	    decide which processes to give to the CPU next
	    a couple of milliseconds

	our job is to separate jobs between I/O bound and CPU-bound
	   I/0 Bound:
	      block frequently
	      don't use much CPU
	      should be scheduled quickly
	         ensures the CPU-bound jobs don't have to wait very long
              go to the "front" of the run queue
	   CPU-Bound
	      get pre-empted
	         make transistion from Running to Runnable
		 predictably use a lot of CPU
		 dont use other resources (significantly)
		 less likely to be interactive
		 they can stand to wait
                 go to the "end" of the run queue
       scheduling in Geekos:
          one queue, there are priorities but they are all the same

   How to create a new process?
      usulally via fork
         except to start "init"
	    first user process
	    attaches login prompts to the console
	    starts up daemons (servers)
	    reaps all orphan zombies
	       zombie is a process that is dead (no exit status)
	       orphan has no parent
         in GEEKOS, there is no "init", kernel starts shell
	    this is b/c Geekos sucks
      fork():
         return values:
	    0 - in the child
	    child_pid - in the parent
	    <0 - on error
	 prints before a fork CAN be printed by both child and parent
	    if buffer hasn't been flushed yet
	    buffer maintained in user space

   How do processes die?
      Exit()
         return from main is an example of this
      unhandled exception (i.e. SIGSEGV --> segfault, SIGPIPE)
         side note: SIGSEGV and SOME other signals can be handled
      signal from another process
         i.e. SIGKILL from shell
	 side note:
	    hierarchy of signals to use to kill a process:
	       kill -INT <proc> (same as ^C)
	       kill -HUP <proc> (tells process to try to end appropriately)
	       kill -TERM <proc> ("-TERM" is optional)
	       kill -9 <proc> (unhandleable DIE DIE DIE)

9/12 (Discussion)

   debugging:
      make "dbgrun" in one window
      make "dbg" in another
      repeats last command on "enter"
      "b file.c:LINE_NUM"
      "info threads"
      "thread apply 1 bt" (bt = backtrace)
      "thread apply all bt" (bt = backtrace)
      break on 90th iteration of loop?
         "b syscall.c:914 if count > 90"
      can't print MACROS in gdb :(
         you can create a variable to reference the MACRO if you want
      "print *struct_ptr" gives all things in struct 

9/13 (Lecture)

   the static keyword (in C)
      on a local variable: lives beyond the function's execution
      on a function defined in a header (.h) file:
         - avoids confusing the linker with multiple definitions in
	  different .o files
	 - putting a static prototype in a header is essentially useless
	 - this idea assumes the body of the function in in the header 
	 - Enable_Interrupts and Disable_Interrupts
      one a function defined in a C (.c) file:
         - avoids polluting the name space of functions (e.g. "index")
	 - asserts that a function cannot be called outside the file
	   (except via a function pointer)
	 - We can change a static keyword in GEEKOS, but be careful
	    * Don't copy and paste the code though, that's gross

   Project 1:
      What should be copied into the child process?
         two pieces of user context should change:
	    - set of pointers that define the memory space (base ptr, etc)
	       * look at userseg.c and maybe spawn.c?
	       * might be called "LDT"
	    - file descriptors should stay the same but ref count in each
	      file should change
	    - stack ptr IN user context (Neil doesn't think it's used)
	       * Maybe at the beginning, but we prob shouldn't worry
	 kthread needs a new stack, and then esp somewhere in that page 
      When a process exists, when should we free the memory?
         - we should keep the exit status
	 - it's up to us when it should actually get freed

   Inter-process communication (IPC):
     examples of IPC in use b/n processes on the same machine:
        - popen (child process) to get input
	- getting graphics to the window server
	- syslog (centralized logging service)
	   * syslog process has total control over the logs
	- process pool 
	   * coordination via shared memory
	- database
	- signals sent during shutdown or power failure

      Message passing vs. pipe:

      message passing:           	   pipe:
      message (one block)     		   byte-stream (|read| != |write|)
      per-message destination (usually)	   connected (just one other end)
      associated with microkernels	   not	   
      supposed to be very fast		   not?

      Why IPC and Processes instead of threads?
         - consider the examples of IPC list
	 - isolation
	    * if one dies the rest are fine (one can die alone)
	    * if a thread crashes it will kill everyone
	 - reuse
	    * the pager "less," other combinations from the shell
	 - different kernel-level "aspect"
	    * vary permisions/user
	    * different priorities (unsure of whether this is in threads)
	    * different set of file descriptors
	       - threads don't get their own file descriptors
	 - an idle process can be paged out (rarely used)
	 - migrate to multiple machines easily

      IPC (the ugly way):
         f = fopen("a_file.txt", "w");
	 fwrite(.....,f);
	 fclose(f);
	 ------------------------------------------------------------
	 while ((f=fopen("a_file.txt", "r"))==NULL) {
	     sleep(1);
	 }
	 fread(...); 

	 - essentially how compiler communicates with linker

      Shared memory approach:
         - not done in GEEKOS
	 - imagine two processes with independent virtual address spaces
	    * imagine they have unique stacks in physical memory
	    * they both have a shared code segment in physical memory
	 - they could have a shared memory region
	    * not necessarily at the same point in their individual
	      virtual address space
	    * both point to the same point in physical memory
	 - very fast, no communication through kernel necessary
	 - the shared code-segment is different
	    * mapping the same read-only page does not amount to 
	      "shared-memory" IPC
	 - if you fork, the top of the stack points to the same point
	   until one is attempted to be written to, at which point the
	   one written two will be allocated a new read-allowed page
	 - interface for this:
	    * shmget - may create
	    * shmctl - sets permissions
	    * shmat - "open"
	    * shmdt - "close"
	 - essentially we want a pipe like scheme for the shared memory
	 - how do we coordinate this shared memory?
	    * partition
	       - using software, decide which process should write which
	         part of the shared memory (set flags for read/write)
	    * sequence number
	       - define each message as having #, length, and body
	       - let's say 1 is writing, 2 is reading
	       - 2 keeps track of the last # read
	       - assuming they are sequential (or ordered in some way)
	         2 can appropriately know which to read
	       - 2 can have an int that allows 1 to know when the writer
	         can delete already read messages
	    * semaphore, mutex, condition variable, etc.

9/14 (Discussion)

   Project 1: Fork
      LDT (Local Descriptor Table):
         This should be handled by create_context
	 I don't think we need to worry about anything more than copying it over
      start_user_process vs. creating your own?
         probably use built-in over user-created, but it's really up to you
      user_context -> memory
         allocated by built-in functions I believe
	 you can copy this for forking, probably not for exec-ing though

      state pointer will point to beginning of "interrupt state" struct always
         esp not as reliable

      poke around in kthread.c
         create_thread and whatnot

      copying the kernel stack?
         maybe disable interrupts? not sure about that
         "copy" interrupt state
	    copy what you KNOW will still be there from the kernel stack
	 for exec, changing eip might be advised

      kernel thread also has a reference count
         initial reference count is 2 after fork (parent AND child)
	 be careful for non-waiting parents
	    i.e. children waiting count will be 1 if no waiting parent

      git notes:
         you should commit frequently, push less frequently
	 git status
	 git log
	 git branch "test_name"
	    git checkout "test_name"
	 git checkout "commit number"
	 git reset --hard "commit number" HEAD~n
	    completely deletes "n" most recent commits
	 git revert Head~n
	    revert previous "n" commits but keeps history

9/15 (lecture)

   Fork is not recursive
      - fork provides an interface to user code, but the child process starts as if new

   Make_Runnable -> sticks child on run queue

   To go to Running, Handle_Interrupt will do this (from Runnable)
      Handle_Interrupt always calls GetNextRunnable	 

   At the top of the kernel's (parent) stack:
      Interrupt_State (all the registers)

   kthreaad->esp should be set to state initially
      pretty much only valid for this purpose (doesn't necessarily get updated w/ actual
      esp)

   The address at the bottom of the stack page
      something like (0x00034000)
         3 zeros at end, a couple at beginning
      therefore, at all times 
         KASSERT((kthread->esp) & 0xFFFFF000 == kthread->stackPage)

   user_context vs. kthread stack?

   Sockets:
      Unix Sockets
         - on the same machine
	 - allows extra information and trust
	    * what user owns the other process?	 
	 - you can pass an open file through the socket
	 - on the same machine, this is probably more efficient
      IP Sockets
         - network communcation
	 - really can only know the address of the other endpoint

      Datagrams
         - messages
	 - packets (UDP: User Datagram Protocol)
	 - might not be "connected"
	    * you may specify the destination with every message (sendto())
      Bytestreams
         - sequence of bytes (TCP)
	 - connected
	 - similar to pipe

      socket() 
         - creates a socket
	 - returns a file descriptor
	 - tells the kernel the type you want (Unix, bytestream, etc.)

      SERVER SIDE:

      bind()
         - specifies the endpoint associated with a socket
	 - endpoint will probably be a path for Unix
	 - "	    	 	  "  a TCP Port for IP
	 - if the caller doesn't specificy the port, one will be allocated for you

      listen()
         - express a willingness to accept connections

      accept()
         - takes a file "listening" descriptor
	 - returns a new file descriptor for an incoming connection

      CLIENT SIDE:

      connect()
         - specifies a remote endpoint for the socket
	 - bytestream -> connection setup request
	 - datagram -> set the implicit destination

      OTHER SOCKET FUNCTIONS:
         read/recv/recvfrom
      	 write/send/sendto
      	 close
	 shutdown()
	    - I am done writing
	    - I am done reading
	    - I am done with both

      Threads:
         - shared address space
	 - own stack
	    * call pthread_create and what happens?
	       - malloc a new area beneath the first stack
	       - no virtual memory trickery
	    * what happens when a function from a pthread returns?
	       - return address to some routine that will keep EAX for later pthread_join
	 - threads are hard to debug because of shared address space

9/19 (Discussion)

   Project 1:
      you probably don't want to use a global lock for pipes
      don't worry about synchronization on other types of files (not pipes)
      Don't assume atomicity

9/20 (Lecture)

     Project 1:
          User process address space
	     stack at the end of user process address space
	     command line args must be put on the user stack
	        two parameters to main:
		   argc and argv
		argv pushed onto user stack frame, followed by argc pushed
		   after those, return address is pushed onto stack
		   after that, old ebp is pushed
		where do the strings that argv points to go?
		   doesn't really matter (we have a pointer)
		   however they are generaly put right above the stack

          Register Dump:
	     What to do with Exception 13?
	        Machine tried to look at pointer it shouldn't
	     Which registers matter?
	        eip:
		   if in range 0x1000-0x3000 -> likely valid user instruction address
		   if in range 0x10000-0x40000 -> likely valid kernel instruction address

		   How to figure out what eip really is?
		      in make dbg
		         can run "dis (eip)"
			    gives which function and what instruction
		      "sort -n build/geekos/kernel.syms"
		         gives you the function
			 
                 Interrupt number 6:
		    not really an instruction (or not one can be run in this privilege)
         in gdb:
	    x /100 0x000bfcda
	       command to examine amount of memory regardless of type
	    thread apply all bt
	       similar to single threaded "where"

   setjmp(buffer)
      creates an image of current context, sticks it into buffer
         includes register state, eip, etc.
      store current context (registers and such) into a buffer
      will return differnt value the first time   

   longjmp(buffer)
      jump back to state represented by buffer
      restor a stored context (jumping far)

   linked-list of runnable threads
      in each node is info about thread (start ptr, args, ret) and buffer
      
   we use setjmp to save current state and put it on thread queue
      then longjmp to new buffer for new thread

   User-Level Threads:
      kernel knows nothing about them
      advantages:
         user has control over scheduling and can avoid bad interactions
	 very fast creation/destruction of threads
      disadvantages:
         can't use multiple processors
	 complexity in avoiding blocking system calls

   How many kernel threads should you have?
      number of processors?
      expected number of blocked threads
         if large:
	    probably better to do something else
	    don't block

9/21 (Discussion)

   Project 1:
      run while(Fork()>=0);
         if you can return to shell and run stuff after this you're good
      kill unwaited-on child
         each kthread has a "parent" field?
	 add a field to kthread? (at bottom)
      you want a new ldt for child

   Project 2: Signals

9/21 (Personal Notes)

   Descriptor gives:
      base address
      limit address
      privilege
      type (read,write,etc)

   Selector gives:
      GDT vs. LDT
      Privilege Mode
      Index in G/LDT

9/22 (Lecture)

   Interrupts:
      lowlevel.asm --> Handle_Interrupt
         first Save_Registers saves state
         check that our pointer is to kernel data
	 (skip stuff that isn't immediately obvious)
	 kernel locking stuff (interrupts trylt disabled)
	 IMPORTANT:
	    get the address of the C handler function
	    interrupt table -> holds address of handler function
	       index in table is interrupt umber
	    then call handler
         Macro Push_Current_Thread_PTR:
	    add thread to run queue
         kthread->esp is reset to a vaild point in the stack
	    then Get_Next_Runnable is called
	 kthread->esp is set in lowlevel.asm
	    it gets used in this code when a process is put onto CPU
	    You must set esp in process creation so that this can use it
	 maybe also look at Switch_To_Thread()
	 when the registers are restored, actual esp moves up the stackpage
	    kthread->esp does nothing!
	 while a process is runnable:
	    kthread->esp has value
	 while a process is running:
	    kthread->esp refers to where the registers were stored the last
	    time it was interrupted
	 consider not messing with kthread->esp if possible

   Project 2: Signals
      Signals: IPC's that essentially act as interrupts for user code
      array of functions that can be invoked from "outside" a process	
      return address above the signal handler will be a system call
         we're now back in the kernel and can restore user context
      we stash the interrupt state in the user stack so that handler
      can reference this for system calls
         seems like a security vulnerability
      for signal table:
         default: default behaviour
	 ignore
	 function ptr to handler

9/26 (Lecture)

   Project 2:
      consider using git remote add some_name (url)
         within project 1 directory
      	 to push to new repo, git push some_name
      trampoline:
         Where do you return after signal is dealt with in user code
	 trampline is the return address in kernel space where things 
	 can be dealt with before return to user code
      No signals to non-user processes
      Sys_Signal
         signal handler
	 allows user to change signal handlers
      Sys_Kill
      SIG_DFL, SIG_IGN --> casting 1,2 to (signal_handler)
      signal handler does not exist in GEEKOS
         kthread struct probably a good idea
      Sys_RegDeliver
         Store the return for later
      Sys_ReturnSignal
         NOT EXPECTED TO RETURN
	 the function does return, but it doesn't return to anything that
	 expects a return value from THIS system call
      Sys_WaitNoPID
         Generic version of wait (no pid supplied)
      Complete_Handler
         might be useful for finishing a handling (clean up)
     	 not already called anywhere in GEEKOS
      Check_Pending_Signal
         Used by GEEKOS
	 Checks if there are any signals, doesn't do anything if there is
      Setup_Frame
         get process ready to run signal handler
	 remember current state
	 Sys_Signal will get a user address as a function pointer
      Also a signal.c in /libc
         Sig_Init
	    calls RegDeliver when a program starts up
	       registers a trampoline
      Return_Signal
         places 0x14 in eax
	 issues interrupt
	    number 14 system call gets you to Sys_ReturnSignal

   Semaphore review:
      semaphore {
         counter = Init #;
	 wait queue = ...
      }

      p, wait, down 
         decrement counter, if 0 or negative, 
	 it will put a process to sleep
      v, signal, up 
         increment counter, if 0 or negative, it will wake up
      watch synchronization videos (semaphore one)
      in linux, spinlock on things within semaphore

9/27 (Lecture)

   Scheduler Activations
      Idea:
         - allow user-lived code to choose which thread to run
	 - kernel decides when more or fewer (virtual) processors 
	   are available
	 - "upcalls" (like signalls with parameters) 
	   allow kernel to tell user code about events
      user-only: many user threads to one kernel thread
      kernel-only: one user thread to each kernel thread
      we want: many user threads: some kernel threads (enough to be good)
         - some is generally less than many

      User-level runnable threads (this queue not visible to kernel)
         - kernel will alert user level stuff of availability of processor
	 - user scheduled code will longjump to its chosen thread
	 - this idea is different than what we've talked about before
	    * allows for "better" optimization of scheduling (potentially)
	 - suspend(state) will push register "state" on the back of the
	   run queue

   Don't call these functions (especially in multi-threading):
      - strtok
         * mangles its input (if you pass it a string, it will destroy it)
	    - replaces specific delimeters with "\0"
	 * remembers where it left off
      - gethostbyname 
         * looks up an array of records associated with a URL
	 * returns a pointer to a shared buffer
	 * if it is called again, initial buffer is overwritten
      - gethostbyname_r
         * the "_r" tends to indicate this is no longer a problem

   Race Condition:
      - outcome of execution depends on what happens first

      example:
         volatile int counter = 0; // volatile means always keep in mem

         for (i=0;i<1000;i++) {
            counter++; (global, in two different threads)
	 }   	 		
	 - we will not get counter = 2000
	 - this is NOT an atomic instruction
	 - without volatile, we'd probably get counter = 1000
	    * compiler optimization will do ++ locally

   Critical Section Problem:
      - How do you provide synchronization on a real machine?
      - 4 goals
         a) Only one in the critical section at a time
	 b) Progress: a thread outside its CS can't block another that 
	    wants in
	 c) Bounded waiting: shouldn't wait forever
	 d) no assumptions about speed
      - Critical section refers to section containing a race condition
      - really only an issue in multi-processor environment
      - solutions:
         * Disable interrupts
	 * have a lock variable (not a great solution)
	    Enter() {
	       while (lock != 0);
	       lock = 1;
	    }
	    Exit() {
	       // unlock
	       lock = 0;
	    }
	    - this is okay but now lock variable needs to be protected (a)
	 * have threads take turns (consider just 2 processes)
	    - Thread A
	       Enter() {
	          while (turn != "A");
	       }
	       Exit() {
	          turn = "B";
	       }
	    - Thread B
	       Enter() {
	          while (turn != "B");
	       }
	       Exit() {
	          turn = "A";
	       }
	    - doesn't cause the problem with (a), but it does break (b)
	       * Thread A must allow B to run and vice versa
	 * Peterson's Solution
	    - consider 2 processes (0 & 1)
	       Enter() {
	          flag[id] = true;
		  turn = other_id;
		  while (turn == other_id && flag[other_id]);
	       }
	       Exit() {
	          flag[id] = false
	       }
	    - doesn't work for more than 2 threads
	    - solves a, b, c, and d for those 2 processes
	 * Bakery Algorithm
	    - "take a number" scheme
	       * wait until everyone with a lower number has finished
	       	  Enter() {
		     entering[id] = true;	
		     number[id] = 1 + MAX_OF_OTHER_NUMBERS;	
		     entering[id] = false;
		     // N is number of threads
		     for(j=1; j<=N; j++) {	
		        while (entering[j]);
		        while (number[j] != 0 && number[j] < number[i]);
		     }
		  }
		  Exit() {
		     number[id] = 0;
		  }
  	       * works in a scheme with basically no processor support
		        		 
9/28 (Discussion)

   Project 2:
      Depending on how you handle children, some of the tests may use spawn
         if you defined something in fork, probably do the same in spawn

10/3 (Discussion)

   Project 2:
      you do need to pop your arguments back off in Complete_Handler
      Enabling Interrupts?
         probably don't have to worry about it
	 race condition on signal send?

   Project 3:
      per-cpu variables
      per-cpu variable structure
         cpu number, current thread it's running, run queue, GDT
	 one for each cpu
	 no paging, so some things might change

10/4 (Lecture)

   Project 2: Signals
      - There is a sneaky test that involves invoking kill from within a signal handler
         * reset flag in setup process, not in completion handler

   Hardware lock intstructions: (lock the bus)
      1) TSL - test and set lock
         - tsl eax, [memory_location]
	    * puts *memory_location into eax
	    * puts 1 into memory_location
	    * done ATOMICALLY 
      2) xchg - exchange     
         - same as tsl exceptnew value at memory_location is old value of eax
	 - addditional feature useful for lock-free data structures, doesn't help locks

	 spinlock from xchg:
	    See: lowlevel.asm
	       lock_function:
	          mov eax, 1
	       loop:
	          xchg eax, [lock_variable]
		  test eax
		  jnz loop
		  ret
	       unlock_function:
	          move eax, 0
		  xchg eax, [lock_variable]
		  ret

   Producer/Consumer Bounded-Buffer problem:
      producer creates stuff
         - writes it to a buffer
      consumer reads from buffer

      * could be more than one consumer/producer

      producer should write only when there is space in the buffer	
         - should stop if buffer is full
      consumer should read only when there is data available
         - should stop if buffer is empty

      works well with semaphore and condition variables, not so much with mutexes

      Initial condition:
         - empty buffer
	    * consumer is blocked
	    * empty_buffers = N
	    * full_buffers = 0
      
      treat buffer as array of "something" (characters, integers, pages, who cares)

      semaphores:
         full_buffers
	 empty_buffers      	

      mutex:
         m --> guards access to shared state

      producer:
         i = produce_item()
	 wait(empty_buffers)
	 wait(m)
	 insert(i)
	 signal(m)
	 signal(full_buffers)
	 
      consumer:
         wait(full_buffers)
	 wait(m)
	 i = get_buffer()
	 signal(m)
	 signal(empty_buffers)
	 consume(i)

   Condition Variables:
      - often combined with monitors
         * monitors are kind of like automatic mutex acquired on function entry/exit
      - cv.wait()	  
         * will ALWAYS wait (unlike a semaphore)
	 * will "release" the mutex/monitor to wait
	 * inherit mutex back when awakened 
      - cv.signal()
         * if there's no one waiting, signal does nothing
	 * awakens at most one waiting thread
      - cv.signal_all()
         * awakens all (if any) waiting threads

   Producer with c.v.:
      i = produce_item()
      m.wait(mutex)
      while(count_full_buffers == N) 
         cv.wait(not_full_condition, Mutex)
      insert(i)
      // could add if (count_full_buffers == 1), not necessary
      cv.signal(not_empty)
      m.signal(mutex)

   * mutex = grand mutex
   * you shouldn't need while loop, second level of ensuring you should have mutex

   Dining Philosophers Problem:
      - Three states:
         * Talk
	 * Hungry
	 * Eat
      - Goes through in order, then loops back to top
      - we maintain an array of philosophers)
      
      test(philosopher_idx)
         if (philosopher_idx -1) is not eating
	    and (philosopher_idx + 1) is not eating	
	    and (philosopher_idx) is hungry
	 then	
	    philosopher_idx = eating
	 cv.signal(philosopher_idx)

      pickup(philosopher_idx)
         philosopher_idx = hungry
	 while(philosopher_idx != eating)
	    test(philosopher_idx)
	    if(philosopher_idx == hungry) 
	       cv.wait(philosopher_idx)
         
      putdown(philosopher_idx)
         philosopher_idx = talk
	 test(philosopher_idx - 1)
	 test(philosopher_idx + 1)

      * There is no "busy waiting" -> only one while loop that has a wait in it
      * anything we're doing in here that looks/changes a shared variable is 
        ALWAYS guarded by a mutex

   Implementation of a Barrier:
      - make all N threads wait until all reach the same point
      
      phase_1()
      barrier()
      phase_2()

      Initial Condition:
         N: # of threads
	 S: semaphore associated with being blocked (value 0)
	 mutex
	 threads_in_barrier: 0
	 
	 Barrier()
	    wait(mutex)
	    threads_in_barrier += 1
	    if (threads_in_barrier == N)
	       signal(s)
	    wait(mutex)
	    wait(s)
	    signal(s) 
	    
	    return

	 * the wait/signal at the end is called a "turnstile"

	 * if we signaled the mutex after the turnstile, we'd have problems

10/6 (Lecture)

   Let's get over how to get the current threads:
      - g_current_threads[cpu_id]
      - we can get the current cpu_id using some things (APEC or something)
      
      1) find out cpu_id
      2) then use it as an index
      - What happens if you get swapped inbetween steps 1 and 2?
      - CURRENT_THREAD must (currently) disable interrupts
      - other ideas to avoid this?
      - Think about these registers:
         * cs
	 * ds
	 * ss
	 * es
	 * fs
	 * gs
      - array of these registers with base of GDT
         * For each processor, we will have a unique array
	 * first n-1 elements are all the same
	 * last element points to a thing that tells you current thread
	   - other stuff too
	   - mov gs:offset -> eax
	      * this will get the current thread
	      * we can assume this instruction runs ATOMICALLY
	        - no more disable interrupts

   There are 2 types of registers:
      - caller-save
         * scratch registers - expected that the function will overwrite it
	    - eax (return value will overwrite this)
	    - edx (often overwritten by functions)
	    - must be stashed before function called
      - callee-save
         * NOT expected that the function will overwrite it
	    - ebx

10/13 (Lecture)

   Exam 1: Answer
      init:
         count = 1
	 cv =  new condition variable
      p
         count --
	 if (count <0) cv.wait()
      v
         count ++
	 cv.signal()

   ACID Properties
      - A: Atomicity
         * no one can observe a partially completed transaction
      - C: Concistency
         * enforcement of the rules of transactions
	 * NOT a property of the system, more of the application)
      - I: Isolation
         * each transaction operates as if it is the only transaction
	 * each transaction appears as if run alone, sequentially
	 * "serializability"
	    - typically accomplished with two-phase locking
	    - Two-Phase Locking
	       * growing phase: acquire locks
	       * shrinking phase: release the locks
	       * avoids all race conditions
	       * EX:
	          Transaction 1: a = read(x)
		  	      	 a++
				 write(x,a)
				 commit
		  Transaction 2: b = read(x)
		  	      	 b++
				 write(y,b)
				 commit
		  Consider the following sequence:
		     t1.read(x)
		     t2.read(x) <- implies read lock acquired
		     		   stops t1.write(x)
		     (If you do the first 2, this is the only way out)
		     t2.write(y)
		     t2.commit
		     t1.write(x)
		     t1.commit
		     
		  Consider the following sequence:
		     t1.read(x) <- acquire read lock
		     t1.write(x) <- "promote" it to a write lock
		     (If you do the first 2, this is the only way out)
		     commit
		     t2.read(x)
		     t2.write(y)
		     commit	
      - D: Durability
         * Once commited, the result is permanent
	 * If you crashed right now, it would still be there
	 * maintain a LOG
	    - contains records w/ before/after values for each modified
	      variable associated with a transaction id
	    - contains records indicating whether a transaction committed
	      or aborted
	    - checkpoint record: indicates how much of the log has been
	      processed
	    - transaction committed when the record is on disk
      - it is ok to ABORT
         * deadlock
	 * any other failure (disk failure, remote server crashes, etc.)
	 * there may be consequences
	    - rollback?

   Deadlock:
      - two processes prevents eachother from making progress
      - 4 conditions of deadlock (when can it happen):
         * Mutual Exclusion
	 * Hold and Wait
	    - acquire some subset of resources needed and wait for more
	 * No Preemption
	    - the resource I hold cannot be stolen from me
	 * Circular Wait
	    - cycle in the waits-for graph
	       * process are nodes, directed edge is p1 waits for p2
	    - basically p1 waits for p2, p2 waits fo p1
      - DEADLOCK PREVENTION:
         * breaking one of the conditions will break deadlock
	    - Mutual Exclusion
	       * can't really get rid of this
	    - Hold and Wait
	       * decide there is only resource
	       * grab all locks at once
	    - Preemption
	       * can't really get rid of this either
	    - Circular Wait
	       * enforcing a total order on resources that can be acquired
	          - i.e. acquire something before you want/(seemingly)need
      - DEADLOCK AVOIDANCE:
         * prevent unsafe states
	    - knowledge of what a process might want
	 * Banker's Algorithm (We will discuss this later)
      - DEADLOCK DETECTION:
         * identify a deadlocked process and kill it
	    - which one? -> interesting question

10/20 (Lecture)

Project 4: Paging 1
   - 4k is 12 bits
      * identifier for a page will end in 12 (binary) zeroes
      * We can use those 12 bits to keep track of permissions
   - Consider Dirty/Access bits (they are imporant)
      * Intel manual has helpful stuff
   - You will need code to handle a page fault
   - We are not expected to deal with fork
   - page eviction scheme:
      * Best scheme is called CLOCK
         - We have a linked list of all the pages 
	   (imagine they're in a circle)
	 - We have a "clock hand" that asks "Has it been accessed?"
	    * if A then A=0 else evict?
	       - evict = if dirty then schedule write; advance hand
	                 else definitely evict
         - Clock hand doesn't move until we've run out of room
	    * uh-oh, all the access bits are 1

10/25 (Lecture)

   Banker's Algorithm (Deadlock Avoidance):
      int Available[resource_id] --> resources of each type that are in the system
      int Max[process_id][resource_id] --> resources potentially required by process
      int Allocation[process_id][resource_id] --> what the OS has out
      Need = Max - Allocation --> what each process could possibly need to finish

   Is-Safe-State Subroutine
      Simulated_Available = Available
      foreach process_id = Finishable[process_id] = false
   loop:
      find pid s.t. !Finishable[pid] and Need[pid] <= Simulated_Available
      if pid was found:
         Simulated_Available += Allocation[pid]
	 Finishable[pid] = true
	 goto loop
      else:
         if all are finished: return true
	 else: return false

   One each request for a resource:
      1. ensure that Request + Allocation[pid] <= Max[pid]
         (else process lied to us)
      2. ensure Request < Available
      3. pretend allocated. if still Is-Safe-State: continue; else: wait

   Deadlock Detection and Recovery:
      - periodically, look for a cycle in the "waits-for" graph
         * essentially look for processes taht don't make progress
      - Constructing edges in the "waits for" graph
         * Consider a process asked for a mutex
	    - We know exactly WHO holds the mutex (Add the edge between the two)
	 * Consider blocked on reading from a pipe
	    - Add an edge to whoever holds the write end of that pipe
	 * Waiting for a child to complete
	    - edge from parent to child
	 * Blocked write on a pipe
	    - add an edge to whoever holds the read end of the pipe
      - Recovery:
         * kill a process in a cycle
	    - reclaim its resources
	    - should resolved deadlock
	 * Which one do we kill?
	    - separating policy (how it should be done) and mechanism (how you do it)
	       * mechanism - develop waits for graph
	       * policy - which do you kill
	          - there are many choices (not necessarily a right one)

   Memory:
      - Protection:
         * User processes cannot access memory from other user processes or the kernel
	    - unless we want them to
      - Address Space:
         * set of addresses a process can play with
	    - give each an illusion of its own individual address space
	       * this space appears as large as possible 
      - Logical Address:
         * considered a virtual address
	 * user process use/instruction reference this
      - Linear Address:
         * also considered a virtual address
	 * after segmentation adds a base address
      - Physical Address:
         * after paging, replaces the page number
      - Screwup fro Logical to Linear: int 13
      - Screwup fro Linear to Physical: int 14
      - Fragmentation:
         * Internal - you allocate a block and pieces of that block go unused
	 * External - parts between allocations are too small to use
	 * paging only has INTERNAL
	    - pages are uniform size
	 * segmentation has a bit of INTERNAL (space for stack and heap to grow)
	 * segmentation also has EXTERNAL
      - Overlays:
         * swap the entire process
	 * essentially having code that rewrites itself
	    - saves room
      - Contiguous Allocation
         * base and limit
	    - we must know limit at load time
	       * if it's to large, we get fragmentation
	       * if it's to small, the program might fail
	 * where should this allocation go? (policy NOT mechanism)
	    - first-fit
	    - best-fit
	    - worst-fit
	 * can contiguously-alocated process share memory?
	    - maybe?
	    - Yes (?)
	       * using another segment register (es, fs)
	          - compilers might no tlike this

10/27 (Lecture)

   Alternatives to hierarchical paging:
      - hashed page table
      - inverted page table
         * track which linear address is associated with a given physical
	   address (useful if physical is much smaller than virtual, 
	   ie. for 64-bit address)
	 * essentially goes physical -> linear
	 * Hot pages: TLB
	 * Pages in memory: "exhaustive" search is ok
	 * Pages on disk: who cares, it'll take forever anyway

   Project 4:
      typedef struct {
         uint_t present:1;
	 uint_t flags:4;
	 uint_t access:1;
	 ...
      } pte_t
      - flags has VM_USER (2nd bit), VM_WRITE (1), VM_NOCACHE (3), 
        VM_READ (0)
      pte *p
      ...
      p -> flags = VM_USER | VM_WRITE
      p -> flage &= ~VM_USER

      - user linear address start: 0x30000000
      - user logical stack pointer starts: 0x70000000
      	   - to avoid APIC at 0xfec -> ox7ec
      - page fault gives you LINEAR address, not logical

   Demand Paging:
      - expect page faults
         * use these faults to allocate

   Actors:
      "pager" - brings pages in from disk
      "swap daemon" - writes dirty pages out
      - these exectute asynchronously
      - maintain available clean pages

   State of a physical page:
      - unallocated, zeroed page (all bytes are zeroes)

                           Dirty                 Not Dirty

      referenced   	   
      (accessed)

      not referenced	   

      ^ Thats supposed to be a table. Below represents transitions in it

      (not referenced, not dirty) goes to (referenced, not dirty) on read
      (not referenced, not dirty) goes to (referenced, dirty) on write
      (not referenced, not dirty) cant go to (not referenced, not dirty) 
      (referenced, not dirty) goes to (not referenced, not dirty) 
         on OS (clock)
      (referenced, dirty) goes to (not referenced, dirty) on OS
      (not referenced, not dirty) goes to (referenced, not dirty) on r/w
      (referenced, dirty) goes to (referenced, not dirty) on 
         OS (clean/write to disk)
      (not referenced, dirty) goes to (not referenced, not dirty) on 
         OS (clean/write to disk)

   How to replace pages?:
      - FIFO: evict the oldest
      - OPT: look into the future (difficult/impossible to do)
         * provides best-case/lower-bound
      - LRU: Least-Recently Used
         * we only have access bits, makes this difficult
	 * we can try to finnegle ordering to mimic this
      - Clock: FIFO + second chance
      - LFU/MFU: kick out least/most frequently used
      - Working Set: establish a time over which you keep only things used
                     in the time period
      
11/1 (Lecture)

   Page Replacement:
      - Belady's Anomaly
         * Some replacement algorithms using larger memories will not hold
	   a superset of what they hold withsmaller memories

   Project 4a:
      - Kernel_Page_Dir()


11/3 (Lecture)

   Project 4b:
      - User Page Directory:
         * keeps the same page tables below 0x80000000
	 * keep apic/io
	 * map 0 as NULL for user
	 * memcpy Kernel Page Directory, then place appropriate new pages
      - When adding a page to the user space, make sure it's zeroed

11/8 (Lecture)

   Page out:
      - lock it / claim it
      - clean the page
         * write to paging
      - Zero the page OR REad the page off disk
      - Set it in the new pte
      
   Read and Write REQUIRE interrupts to be enabled
      - Try to keep "in balance"
      - Other stuff can happen while waiting for the disk

   Working-Set Model:
      - establish a time parameter t
      - anything accessed less than t seconds ago is in the "working set"
      - anything else isn't

   Where do paged-out pages go?
      - pagefile in disk
         * geekos: contiguous file
	 * windows, mac osx use this although not contiguous
      - Swap Partition:
         * linux: necessarily contiguous fraction of disk

   How much space do we have to page-out to?
      - Swap partition is constant size
         * What should we choose?
	    - We want more if we have too little memory
	    - However, we don't want to waste space AND
	      takes too long (fetching from disk is long)
	         * might rather kill the memory leak and then force
		   Garbage Collection	      
      - windows and mac osx might be able to expand on the fly?
   
   Memory Allocation in Kernel
      - large contiguous regions
      - efficient, because they are pinned
         * i.e. not pageable, devices are expecting physical addresses
      - may or may not be able to wait
      - aligned

   Buddy Allocator
      - start with one large contiguous block (1 MB)
      - maintain a table of free lists for different amounts of memory
          * amounts are powers of 2 (i.e. 32 bits, ..., 256K, 512K, 1M)
      - Free List
         * set of to-be-allocated blocks
      - we can use the bytes in the allocations to store next pointers
         * more efficient use of space
      - not great if allocations aren't powers of two in size

   Slab allocator
      - allocate a page
      - within that page, allocate things of the same type (i.e. kthread)
      - if we run out of room, just allocate another page
      - slab header keeps track of which entries are free

11/10 (Lecture)

   File - named array of bytes (plus metadata)
   Filesystem - provide file from an array of 512-byte blocks

   blocks store the file contents
      - i.e. syscall.c
         * imagine it takes up 3 blocks (2 fully)
	 * size of 1030 bytes (accounts for partial block)

   what must we store?
      - name (info to retrieve contents)
      - information about the filesystem
         * number of blocks
	 * which ones are available
	 * where are the special structures

   Hierarchical Directory Structure
      - try to use the "file" for everything
         * even free blocks set might be a file (allows r/w etc.)
      - a directory is just a specially formatted file

   Unix Directory File Format
      - dirent ("directory entry")
         * | Entry Length | Inode Number | Filename |
	 * then repeat this for every file in the directory
	 * inode number - unique ID for the file which is an array index
	   to a metadata structure called an inode
      - to find a particular file
         * determine the expected length
	 * if entry length matches, then strcmp filename 

   "hard link" - two names, same inode
      - consider /. vs. /..
   "soft link" - special file whose contents are a filename

   spinning platter (think of vinyl records)
      - moving the head
         * move and settle
	 * depends on distance

   avoid seeks
      - files should be continuous
   want seeks to be short
      - files that share a directory should be nearby
      - metadata should be close

   moore's?

   Disk operations in a queue:
      - while processing one disk request, good chance there will be more
      - reorder the queue to reduce number and distance of the seeks
         * use "elevator" approach
	    - elevator goes up, picking up anyone who wants to go up
	    - elevator goes down, picking up anyone who wants to go down
	    
   Superblock
      - all information about the filesystem
      - replicas in case file system is corrupted
      
   We want files of variable length
   We want to be able to append files

   linked allocation - essentially a linked list using bytes in the block
   	  	       to keep track of the next block

   FAT Filesystem:
      - similar to linked allocation, but all of the next block pointers
      	are stored in an array (File Allocation Table)
      - each file name is bound to the first block number
         * this means this offset is used as the index into the FAT
      - We want to store the FAT in memory

   indexed allocation:
      - record associated with each file (proto inode)
         * contains a list of the blocks inside the record
	 * forces a static allocation of max size for a file

   multi-level indexed allocation:   
      - to handle a few large files (but many small files):
      - store a block of block numbers
         * this is the "indirect block"
	 * allows for last block in record array to store a block of blocks
	   OR just a block depending on how big the file is
	 * you can have a doubly-indirect block...

11/15 (Lecture)

   Buffer Cache
      - every disk op is time-consuming
      - every flash write consumes lifespan
      - we want to avoid unnecessary writes
         * rewriting of a block
	 * updates to inodes (metadata)
	 * updates to directories
      
         int fd = open(filename, O_WRITE, 0666);
	 for (i = 0; i < 8; i++) {
	    write(fd, "boo!\n", 5);
	 }
	 close(fd); // We might flush here

      - Get_Block function
         * read off of disk if needed
	 * lock the block: (if it's ours)
	 * can wait for:
	    1) need to read off disk
	    2) another thread has the block
      - Mark_Dirty function
         * We changed the block -> will need to be "cleaned"
	    - done by writing to disk
      - Release function
         * unlock the buffer
      - Replacement Policy
         * Geekos: LRU
	 * clean pages to evict
      - Operation called "sync"
         * cleans all dirty buffers

   Early Unix Filesystem:
      - Directores -> concatenated dirents
         * dirent - length, inode number, length
	    - this is BAD for large directories
      - inodes - multi-level indexed allocation
         * fixed size array
	    - limit # of files or waste space
         * direct blocks (in the inode)
	 * indirect blocks (stored in the c block of block numbers)
	 * doubly-indirect blocks
	 * on outer-most cylinder
	    - this is BAD (inode far away from file data it points to)
	       * creates long seeks from separation of data from inode

   Fast File System:
      - cylinder group
         * partition space into cylinder groups
	 * put blocks and inodes in each cylinder group
	    - spatial locality of data with inode (fewer seeks)
      - fragment
         * use one block to store the end of several files

   EXT2:
      - 12 direct blocks
      - triply-indirect
      - preallocation
         * when appending to a file, claim the next few blocks before
	   they are needed
	    - avoids interleaving with other files
	    - promotes keeping files contiguous
      - block group (cylinder group) descriptor
         * keeps track of free inodes bitmap, free blocks bitmap
	 * superblock keeps track of block groups

   NTFS:
      - Master File Table
         * "oversized inodes" -> they also store data?
	 * directory is a B+ tree (only leaves, no internal nodes)
	    - looking through a block is "free" 
	    - fetching a block is NOT "free"
      - Block references are in "extents"
         * RLE (run length encoding) compressed block lists
	    - RLE means you keep track of how many consecutive blocks a 
	      given file takes up
	    - list of <start, length> 
	 * extents can also store extents
	    - we can store arbitrarily large files 

11/22 (Lecture)

   Project 5:
      - want qemu to act as if .img is a disk
      - addressable space made available by qemu is less than file size
      - superblock defines the filesystem size
         * contains block size, # blocks, # inodes, where inodes start
      - Filesystem block:
         * individually addressable file system units
	 * i.e. block numbers in inodes
      - Device "block device" block
         * 512 bytes
	 * SECTOR_SIZE
      - create buffer cache with FS block size
         * buffer cache takes care of the for loop
      - let's say you want an inode, say inode 1
         * simultaneously:
	    a) avoid deadlock issue
	       - buffer cache comes with a lock on it
	       - need to be careful to give it back
	    b) avoid inconsistent data
      - you can hold one inode buffer entry at a time
         * keep in mind this doesn't include data blocks
      - Dirents CAN span blocks	

11/29 (Lecture)

   Log-Structured File System:
      - Disk
         * bit density increases
     	 * rotation spped a bit faster
	 * seek time NOT decreasing
	 * starts to look like tape (not good)
      - Memory
         * getting so big that you never have to read from disk
	 * almost all traffic is writes to disk
	    - optimize the common case (in this case writes)
	       * don't need to arragne the data for reads
	          - doesn't need to be sequential
         * we want persistance at high throughput
      - Treat the disk like a log
         * No data has a home
	 * Every time we write data, the file will get a new block
	   in the log
	 * Update with a new indirect block and inode
	 * data in the log at a new location
	 * updated inodes in the log
	 * the current version of any inode can be anywhere
	    - requires an inode map to store its location
	       * inode map stored in a file called the "ifile"
	       * an array of segment numbers for each inode
	          - optionally also a time (access time)
		  - segments are 1 MB
		  - log will essentially be a linked list
      - Cleaner
         * take partially-filled segments
	    - might have obsolete data or unfilled in the first place
	    - combine them, write back out
	       * similar to generational garbage collection

12/1 (Lecture)

   add to a file:
      - size in inode
      - set of blocks
      - data blocks
      - altered free blocks bitmap

   on boot:
      - traverse all structures!

   Journaling File System:
      - Benefit:
         * we can make burst writes contiguous (no seeks)
	 * goal of write: persistence
      - Rule:
         * journal always contains metadata
	 * some implementations have the data itself
      - If not data:
         * do we ensure that the data is on disk FIRST
      - Journal contains operations
         * before state - allows undo
	 * after state - allows redo
	 * need to know whether the operation committed

12/6 (Lecture)

   Project 5c:
      KASSERT0(block_i_think_has_data >= start_of_data_on_disk,
               "so I don't whack the inodes")

   I/O (disk) scheduling:
      - many processes, one disk
      - one queue of disk requests
         * task: manage the queue
	 * goal: throughput and avoid starvation
	 * advantage: we have lots of time
	    - it takes a long time to fetch data form disk
	    - plenty of time to organize queue of disk requests
	    - this is different than CPU scheduling because of this time
	 * note: individual processes have localized accesses
      - Schemes for managing queue:
         * FIFO (First In First Out)
	    - easy but not very good
	 * Greedy schemes (SSTF/SATF/SPTF)
	    - at every step, find the block that requires minimum arm movement 
	      to access
	    - solves some problems of FIFO (interleaved requests on opposite sides 
	      of disk
	    - starvation could be a problem
	       * no guarentee we will leave a commonly accessed area of disk
	 * Scan/Elevator/Look
	    - sort the entire queue
	    - go left to right along disk, getting requests along the way
	    - elevator analogy: get everyone going up in order, going down in reverse
	 * C-Scan (unidirectional elevator)
	    - only serves requests going "up" and not "down"
	    - in other words, only serves requests going one direction
	    - throughput advantage of Scan w/ slightly more fairness
	    - has a bit of wasted movement
	 * Deadline:
	    - each request -> two queues
	       * C-Scan queue
	       * FIFO queue (of sorts)
	          - 0.5 seconds for read
		     * attempted upper bound on request latency for read
		  - 5 seconds for write
		     * attempted upper bound on request latency for write
		  - If our request has waited either of the above times depending
		    on read/write, we automatically jump to that place on disk and 
		    serve request
	       * You can still get starvation with C-Scan, which is why this exists
	          - constant writes to the same location could cause long waits
	       * was in Linux for a long time
         * Acticipatory Scheduler:
	    - after servicing a request, wait at that location
	    - wait until the application ask for the next (adjacent?) request
	    - this offers good performance improvement by causing delay!
	    - depends on close memory accesses
	    - could combine this with some other schemes (FIFO, Greedy, etc.)
         * CFQ
	    - many queues --> many processes
	       * round-robin the queues
	    - extreme fairness, gives all processes "equal" access to disk
	    - good for avoiding process starvation
	       * hurts processes with lots of memory accesses

   RAID:
      - Have more than one disk
      - Use more than one disk to solve problems of single disk
      - Levels: 0, 1, and 5 (There are others but they're not really used)
         * Level 0:
	    - Striping
	       * combine two disks into one volume, alternating
	          - put odd blocks on disk 0, even on disk 1 (for example)
 	    - This makes disk accesses appear faster
	    - Great idea for speed
	    - Terrible for reliability
	       * higher probability of data loss, no redundancy!
	 * Level 1:
	    - mirror: full copy on each disk
	    - writes require multiple writes to each disk
	    - small improvement potential on speed for reads
	    - mostly done for reliability purposes
	 * Level 2:
	    - error correcting codes
	       * recognize and fix corrupted bits
	    - one example of error correction scheme: 2D parity
	          1101|1 
		  1011|1
		  0110|0
		  1001|0
		  ____|
		  1001 0
	       * we can use this to identify 1-bit errors
	          - we can tell error is somewhere in column x, row y
	       * 2-bit failure would screw a bunch of stuff up
	          - no solution using this scheme
	       * if we lost a parity bit, we should be fine
	       * 3-bit errors could confuse again
	       * 4-bit errors might not even be detectable
	       * this is not frequently used
         * Level 3:
	    - disks know when they're wrong
	    - solves much of the difficulty of Level 2
	    - we now just need parity (essentially 1D vs. 2D parity)
	 * Level 4:
	    - block-level parity
	    - allocate one disk as "parity" disk
	    - similar to stripoing scheme
	    - On rewrite, you must both write the block and the associated parity disk
	      entry
	         * lots of write traffic to the parity disk
	 * Level 5:
	    - same as Level 4, but intersperses parity bits in with data
	       * this reduces high write load on parity disk
	    - specifically the parity bits should be rotated to avoid high write
	      traffic on one disk

12/8 (Lecture)

   NFS (Network File System):
      - RPC (Remote Procedure Call)
         * Interface for interaction with procedures/functions not
	   messages
      - XDR (Extended Data Representation)
         * intermediate data representation (i.e. little vs. big endian)
	 * everyone agrees on a single format for transmission
      - stateless
         * server does not know/care about "open" files or file positions
	 * client keeps track of file position, etc.
	 * clients can reboot (doesn't cause confusion)
      - authentication
         * whitelist of IP addresses of valid clients
	 * trusting the user-id reported by that client
	 * THIS IS NOT GOOD
	 * UID = 0 represents the super user
	 * root-squash: uid zero requests -> uid "nobody" requests
	    - optional configuration of the server
	    - prevents attempted root access

   How does a server know that you are you?
      - user/password
      - key pair
         * both of the top two lead to a user id
	 * user id is a numeric identifier for a user, 
	   associated with each process
	    - mapping of username to user id (and passwords) kept 
	      in /etc/passwd
	    - passwords later moved into /etc/shadow
	       * readable only by root (UID 0)
	    - shouldn't store passwords plain text
	    - salted hash of the passwords
	       * salted -> create a random value
	       * hash the password with the salt (SHA)
	       * hash password AND salt, one is not enough (ideally)
      - it doesn't
      - cookie/Openauth
      - Tenex password hack
         * plaintext passwords
	 * from a user account, break the system (get root)
	 * check_password(user, password)
	 * figure it out letter by letter
	    - do this by timing
	    - first letter of password on last byte of page
	    - make sure rest of password on paged out page
      - keypair
         - public key
            * do not care who has it
         - private key
            * kept secret
         - signature (message)
            * hash(message) encrypted with private key
         - certificate
            * message = public key and who owns that key
	    * signature(message)
	    * assumes that the issuer of the cetificate has
	      jurisdiction over good keys to use
         - server believes that a particular public key is associated with 
           a user
	 - must prevent replay
	    * authentication messages must be "fresh"
	    * server comes up with random number, asks for encrypted
	       - random "nonce"
	       - Kerberos scheme (synchronized clocks)