CPSC 3220 - DAY 8
SEPTEMBER 21, 2017

================================================================================

Asynchronous I/O as an Alternative to Threads
---------------------------------------------

Event driven approach

	-Ousterhout description
		-one execution sequence; no concurrency
		-establish callbacks for events
		-event loop waits for an event and invokes handlers
		-no preemption of event handlers
		-event handlers are generally short-lived

	-But must add "continuation" data structures if event processing is
	complex and needs local state and tracking of next step.

Event driven tries to get the complexity down.

Chapter 5
---------

Locks

When threads concurrently read/write shared memory, program behavior is
undefined.

Thread schedule is non-deterministic.  Behavior can change when program is 
rerun.

multi-word operations are not atomic.

Why do compilers reorder instructions?
	-Efficient code generation requires analyzing control/data dependency
	-If variables can spontaneously change, most compiler optimiations
	become impossible.

Why do CPUs reorder instructions?
	-Write buffering: allow next instruction to execute while write is 
	being completed.

Fix: memory barrier
	-Instruction to compiler/ CPU
	-All ops before barrier complete before barrier returns
	-No ops after barrier starts until barrier returns.

Race condition: output of a concurrent program depends on the order of 
operations between threads.

Mutual exclusion: only one thread does a particular thing at a time.
	-Critical section: piece of code that only one thread can execute at
	once.

Lock: prevent someone from not doing something.
	-Lock before entering critical section, before accessing shared data.
	-Unlock when leaving, after done accessing shared data
	-Wait if locked (all synchronization involves waiting!)

Lock::acquire
	-wait until the lock is free, then take
Lock::release
	-release lock, waking up for anyone waiting for it.

1. At most one lock holder at a time (safety).
2. If no one holding, acquire gets lock (progress)
3. If all lock holders finish and no higher priority waiters, waiter eventually
gets lock (progress)

Lock is initially free

Always acquire before accessing shared data structure (AKA at the beginning of
the procedure)

Always release after finishing with shared data
	-End of procedure
	-Only the lock holder can release
	-Do not throw lock for someone else to release

Never access shared data without lock