CPSC 3220 - DAY 13
OCTOBER 26, 2017

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

Levels of Scheduling
--------------------

Short term schduler - dispatcher
	-runs after every interrupt

Medium term scheduler - swapper
	-runs every few seconds
	-provide a mix of CPU bound and I/O bound ready tasks allocated in
	main memory.

Long term scheduler
	-batch job initiator

Priority Based Scheduling
-------------------------

Static priority
	-can lead to problems including deadlock

Dynamic priority
	-priority aging
		-thread's priority decreases as it runs
		-thread's priority increases as it waits

	-priority boosting
		-when signaled - e.g. I/O completion.

Spinlock-based Deadlock
-----------------------

Two threads - one has low priority and one has high priority

Spinlocks in each

low priority thread A			high priority thread
	
	spinlock.acquire()		spinlock.acquire()
	critical section		critical section
	spinlock.release()		spinlock.release()

Thread A starts with thread B waiting on some other event.

Priority inversion
------------------

Three locks - low, medium and high priority
Blocking locks used in low and high priority threads

Thread A starts with threads B and C waiting on events:

		A1 acquires lock
		A2 in CS

event wakes up C			->
					C1 blocks in call acquire
					<-
		A2 continues

event wakes up B			->
					B1 now runs

Priority Inheritance (Donation)
-------------------------------

	-Priority aging would eventually allow A to run and release lock - but
	not clear now long this would take

	-Is there a way to avoid B preempting A?
		-Priority inheritance - when a thread waits for a lock held by 
		a lower priority thread, the lock holder is temporarily 
		increased tot he waiter's priority until the lock is relesed.

Per-processor affinity scheduling
---------------------------------

	-Each processor has it's own ready list
		-Protected by a per-processor spinlock
	
	-Put threads back on the ready list where it had most recently run
		-Ex: when I/O completes, or on Condition-> signal
	
	-Idle processors can steal work from other processors