CPSC 3220 - DAY 10
OCTOBER 3, 2017

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

Mesa vs. Hoare semantics
------------------------
	
	-Mesa
		-Signal puts waiter on ready list
		-Signaler keeps lock and processor
		-Creates a condition variable for every waiter
		-Queue condition variables (in FIFO order)
		-Signal picks up the front of the queue
		
	-Hoare
		-Signal gives processor and lock to waiter
		-When waiter finishes, processor/lock given back to signaler
		-Nested signals possible.
		-For efficiency, lets the signal pass the lock.


Implementing Synchronization
----------------------------

On a uniprocessor:

	Lock::acquire() { 
		disableInterrupts(); 
    		if (value == BUSY) { 
        		waiting.add(myTCB);
        		myTCB->state = WAITING;
        		next = readyList.remove();
        		switch(myTCB, next);
        		myTCB->state = RUNNING;
    		} else { 
        		value = BUSY; 
    		}	 
    		enableInterrupts(); 
	}

	Lock::release() { 
    		disableInterrupts();
    		if (!waiting.Empty()) { 
        		next = waiting.remove();
        		next->state = READY;    
        		readyList.add(next); 
    		} else {
   value = FREE; 
    		} 
    		enableInterrupts(); 
	} 

On a multiprocessor:

	Read-modify-write instructions

		-Atomically read a value from memory, operate on it, and then
		write it back to memory.
		-Intervening instructions prevented in hardware.

	Examples
		-Test and set
		-Intel: xchgb, lock prefix
		-Compare and swap
	
	Any of these can be used for implementing locks and condition variables


Spinlocks
---------

A spinlock is a lock where the processor waits in a loop for the lock to become
free
	-Assumes lock will be held for a short time
	-Used to protect the CPU scheduler and to implement locks.

Thread scheduler needs to find the TCB of the currently running thread
	-To suspend and switch to a new thread
	-To check if the current thread holds a lock before acquiring or
	releasing it.

On a uniprocessor - use a global variable
On a multiprocessor:
	-Compiler dedicates a register
	-If hardware has specific per-processor register, use it
	-Fixed-size stacks: put a pointer to the TCB at the bottom of the stack

Semaphore
---------

Semaphore has a non-negative integer value
	-P() atomically waits for value to become > 0, then decrements
	-V() automically increments value

Semaphores are like integers except:
	-Only operations are P and V
	-Operations are atomic
		-If value is 1, two P's will result in value 0 and one waiter

These are useful for:
	-Unlocked wait: interrupt handler, fork/join