Scheduling

The scheduler can be invoked either explicitly with yield , e.g., yield(), or implicitly by a signal (e.g., internal timer). A program can be viewed as a collection of tasks that can be executed sequentially or in parallel. The scheduler’s job is to compute an assignment of tasks to processing elements (e.g., CPUs) and resources in order to optimize some performance measures (e.g., throughput). This problem of task scheduling is difficult in parallel and distributed systems, and is know to be NP-complete. With removal of some real-world considerations, such as interprocess communications, a polynomial-time scheduling algorithm can be found when either 1) task graph is a tree; 2) the task graph is in interval-order; and 3) there are only two processors. For the general case, however, schedulers are written using heuristics--while such ad hoc rules do not produce an optimal solution, they find an acceptable solution (e.g., near optimal). Often intuition is employed to find heuristic rules for a scheduler.

Taxonomy

Deterministic (static)--all task info is known a priori

Non-deterministic--task info is not known, e.g., task graph or communications info.

	Static--the program’s task graph is estimated prior to execution
	Dynamic -- schedule on-the-fly (e.g., load-balancing or adaptive scheduler that can response to system feedback.)
	Hybrid -- a mix of static and dynamic scheduling

Methodologies

Non-preemptive

	First-Come-First-Serve (a.k.a., FIFO for non-preemption)
	Shortest Job First (SJN)
	Priority Scheduling

Preemptive and Cooperative multitasking

	Round Robin (RR)
	Multi-level feedback queues
	First-Come-First-Serve
	Shortest-time-remaining (SRT)--good for time sharing, preempts on time remaining
	Quantum: foreground and background
	Highest-Response-Ratio-Next (HRN)—priority = (time waiting + service time)/service time
	Priority versus Quantum preemption

Preemptive

The system will signal control away from a process, this can occur before or at the end of any instruction cycle. This is transparent to

single-thread of control process
Processes that don't share memory
code that is reentrant.

Cooperative multitasking

A program must explicitly give its control; for example, Windows 3.1. This is done either via the yield() API or through a return to the OS' scheduler from the callback function.

Reentrant code

Suppose a process calls a function call printf(), and in the middle of printing, another process calls printf(). If printf() simply consisted of do-work, then all the work for the previous call would be lost. To retain pass information, the printf() API is fitted with calls that save its current environment (i.e., push all), this way when any new call interrupts a current execution, the new caller must retain the present state by pushing it onto the system's stack. When any caller completes printf(), it will re-instate the previous caller's information via "pop all."

[return]

Push All Registers

do work

Pop All Registers