Scheduling

Scribe Notes for 10/20/13

Yufei Chen, Cunpu Bo, Xiaoyi Zhang

Class content

Mechanism
Policy
Metrics

Part 1: Mechanism

Start with a very simple scheduling algorithm:

All process will call

yield();

every now and then.

Example:

int main(void) {

int sum = 0;

for (int i = 0; i <10000000; i++) {

sum ^= i;

if (i % 65536 == 0)

yield();

}

return sum & 0xff;

}

Polling

Example:

while (!ready(d))

yield();

Busy waiting

while(!ready(d))

continue;

Blocking

The process will yield, but tell the OS, we are waiting for a particular device D to become ready.

waitfor(d) <----- disk controller

alarm clock

kernel scheduler records for each process what it is waiting for.

For polling, busy waiting and blocking, we are assuming cooperation. Sometimes you can’t assume this. For example, the program could have Loop with no syscalls. What then?

Change compiler, put in a yield() for each loop & label, for each function
Change the machine. Every (say) 10ms, machine insert a yield() syscall.

The second method is called timer interrupt. The process involves actual changes with the machine

motherboard sends signal via bus to CPU.
CPU traps.
enters kernel
kernel can just return, or can return to some other process.

This is called preemptive scheduling.

Pros:

no runaway process
no yield()s in code

Cons:

Complicates critical sections
Any pair of instructions can have arbitrary delay inserted

Preemptive scheduling does not solve infinite loop directly.

Example:

for(;;);

Solution: we can place some limit onto the CPU time allowed for a process

e.g. ulimit -t [.....]

+SIGXCPU

The mechanism fundamentally does not change when the system becomes more complicated

you can think of each thread to be in charge. Each CPU could have separate timer to prevent locking, but the fundamental does not change.

Part 2: Policy

Long term: which process will be admitted to the system in the first place?

The kernel could reject system calls such as fork()
in some shell, they would do the following:

for (int i = 0; i < 5; i++) {

p = fork ();

if (p < 0 && errno == EAGAIN) {

sleep(1 << i);

continue;

}

if (p >= 0)

break;

}

Medium term issue

Not enough memory to hold all the processes at once. Which processes’ memory images are in RAM, vs on secondary storage?

Short term

Number of runnable processes is greater than the number of CPUs, then which process gets the CPU resource?
We will need a dispatcher in this case

Real time scheduling

hard real time (e.g. car braking system, where deadline is life or death)

In this case, you cannot miss a deadline
predictability trumps performance, which avoid timer interrupts
use polling or evening busy waiting!
turns off the cache

Soft deadline (e.g. video playback, approach that linux takes)

Some deadlines could be missed.
There is a cost for missing
Algorithms for soft deadlines:

earliest deadline first. (Simply pick the one with the first deadline; but the one with the earliest deadline could take too much resource, therefore we need)

preemption
priorities

Rate monotonic scheduling. You have periodic takes, some need to run more frequently than the others.

You assign higher priorities to more frequent task.

The situation of scheduling is analogous to situation in real life. Think of yourself as a registrar. you have to decide:

Which student to admit, which student to take class: Long term
Who gets to talk in class: Medium term

etc.

Part 3: Scheduling metrics

How good is our scheduling algorithm?

Aggregate statistics for these time:

Average
Worse-case
Variance

(Customer point of view)

Wait time
Response time
Turnaround time
Context switch

There are a few metrics that we need to look out for as a scheduler

Utilization: % of factory time for useful works (factory owner’s point of view)

Throughput: # of jobs / second

Fairness - every admitted job will eventually finish. (This interpretation is a fairly simple version of fairness)

Some goals are competing. For example, fairness compete with utilization. Also, for system with hard deadline, worst-case time is sacrificed for average time.

Simple, fair example

First come first served

Example: four jobs, first come, first serve.

Jobs	A	B	C	D
Arrival time	0	1	2	3
Run time	5	2	9	4

Scheduler will do the following:

And here are the metrics, assuming context switch time is

Jobs	A	B	C	D
Wait	0	4 +	5 + 2	13 + 3
Turnaround	5	6 +	14 + 2	17 + 3

Shortest Job First

Pros

Average wait time is less

Cons

Runtime known in advance
Long jobs can starve - unfair!

Schedule:

Utilization: , same as first come first serve

First come first serve with preemption (round robin)

Schedule:

A B C D A B C D A C D A C D A C C C C C

Metrics:

Jobs	A	B	C	D
Wait	0		2	3
Turnaround	5	6 +	14 + 2	17 + 3

Pros:

Fair, great average wait time.

Cons:

Utilization goes down. From to
Average response time worse than first time first serve and shortest job first.

Unix time system often have interactive users, therefore they tend to use First Come First Serve + Preemption, and it tends to be a better match for any interactive system.

What often happens is that you have different job classes

Sysadmins
Faculty
Students

Once we have the job classes, we may want priority-based scheduling. The highest priority will be taken care of first. Within the same priority, you will have round robin.

Two kinds of priorities

External: Set by user or admins
Internal: Set by the scheduler itself

In Linux, there is an external priority called “niceness”. Greater niceness -> willing to wait.

Traditionally niceness ranges from -19 to 19. E.g. nice (+3). (you can only pass in nonnegative numbers)

Priority = (niceness + _______ )

In essence, all schedulers are different priority based scheduler

Appendix

Doc for nice: http://man7.org/linux/man-pages/man2/nice.2.html

Further readings for scheduling: Understanding the Linux Kernel By Daniel P. Bovet & Marco Cesati http://oreilly.com/catalog/linuxkernel/chapter/ch10.html