Concurrency -- more than one thing happening at the same time
  - useful programming paradigm
    - GUIs (event-based programming)
    - networking (one thread per connection)
  
  - may or may not use "threads"
  
First, single-threaded concurrency
  1) register for events (button clicks, timer events, etc.)
  2) sit back and wait
  
- Event dispatch loops
  - importance that event handlers run "fast"
    - chaos if event handler wants to block (e.g., do a network thing)
  - pure event-based systems (e.g., Motif widget system) force you
    to do I/O in weird ways (register event handler for activity
    on a file descriptor)

- Event compression
  - screen only refreshes 60-80Hz
    - for some intense graphics apps, you're lucky if you get 10Hz
  - mouse generates motion events 150+Hz
    - redraw on every mouse motion event gives huge lag

- But, single-threaded concurrency has benefits
  - Data structure consistency
  - Easy for beginning programmers
    - (FYI, Netscape 1.0 had a fancy event dispatch mechanism)

- What about multi-threaded programming?
  - What is a thread?
    - Many different models.  For today, a simple fork/join model.
      - fork() -- returns true/false (child/parent thread)
      - join() -- waits for both threads to come together
      
  - When concurrency goes bad
    - Issue 1: concurrent readers and writers
      - Example, simple linked-list, insertion in sorted order
      - In parallel with query
      - Issue: data structure consistency
    
  - Two models: pre-emptive and non-pre-emptive
    - Non-pre-emptive -- explicit yield() command
      - How early Macintoshes (before System 7?) worked
      - Solves the data structure consistency problem (issue 1)
      - Dealing with producer/consumer is feasible, but ugly
        - add a loop to yield() and test in store() and get()
      - Can't take advantage of multi-proessor
      - If you don't yield(), other threads can't run
        - Long-running computational threads must add explicit
	  yield() calls to let short-running GUI threads get
	  useful work done and have your program feel responsive
	  
    - Pre-emptive -- after a timer goes off, the next thread
      gets to run
      - Good: No more yield() calls
      - Good: Works with multiprocessors (speed up your program!)
        - Footnote: ugly issues about write propagation
      - Bad:  No more guarantees about data structure consistency
      - Requires new features to solve issues 1 & 2
      
Pre-emptive threads, dealing with concurrency
  - Solution 0: Locks
    - Two methods: acquire() and release()
    - Linked-list: put a lock "around" the list
    
  - Solution 1: Semaphores (Dijkstra)
    - Two methods: up() and down()
    - Internal integer i, starts at one
      - down() -> if i>1, i-- else block
      - up()   -> i++
        - up() is guaranteed to wake up somebody who called down() and blocked
    - Can be used as locks
    
Issue 2: producer / consumer
  class Buffer {
      Object thing;
      void store(Object thing) {
	  // what if something is already there?
	  this.thing = thing;
      }
      Object get(Object thing) {
	  // what if nothing is there?
	  Object tmp=thing;
	  thing=null;
	  return tmp;
      }
  }
  - Issue: how to wait until another thread does a store() or get()
  
  - Pre-emptive: you need semaphores
  - Non-pre-emptive: you can use yield()

	
Dining Philosopher's Problem
  - The Deadlock Problem
    - Possible solution #1: one big lock around the whole table
    - Possible solution #2: strict ordering on the locks
  - Aside: deadlock detection
    - if the lock dependency graph has cycles, you have deadlock
      - graph algorithms to the rescue!
	
How to implement locks / semaphores on real processors
  - disable interrupts (only available to OS kernel, pure user-level threads)
    - also, doesn't work on multiprocessor
    
    lock.acquire() {
      disable_interrupts();
      if(busy) {
	  lock.queue.add(currentThread);
	  sleep currentThread && enable_interrupts();// need to happen together
      } else {
	  busy=true;
	  enable_interrupts();
      }
    }
    
  - atomic test-and-set instruction
    - works on multiprocessor
    - test-and-set address, old-value, new-value
      if(*address == old-value) { *address == new-value; return true; }
      else { return false; }
      
      Then, if lock is busy, thread needs to wait until it's free
      lock.acquire() {
	while (!test-and-set()) {
	  lock.queue.add(currentThread);  // note: queue needs its own lock
	  currentThread.sleep();
	}
      }
      
      lock.release() {
	// assume you've already got the lock

	Thread t = lock.queue.remove(); // may return null
	t.wakeUp();
      }
      
- Conclusions
  - single-thread event dispatch systems
    - let you think about concurrency
    - none of the issues with simultaneous access to a data structure
      that happen in pre-emptive multithreading
      
- Next time
  - Threads in Java
  - Consistency issues with real multi-processors