CS111 Scribe Notes

Lecture 7: Scheduling Algorithms

February 01, 2012

By: Austin Chen, Alex Keopong, Pavan Challagulla, and Andrew Inscore

An Operating System is considered a master control program, which manages devices, RAM, network, CPU, etc. If one program exists, then it gets the CPU. However, in this day and age an operating system consists of many programs. The problem arises as to who gets the CPU. One solution could be to have a CPU for each program, however that is not very efficient. We approach our solution with even-driven programming.

Event-Driven Programming

Event-Driven Programming is a method used to allow programs to respond to different events. Applications are divided into small chunks with callbacks each triggered by an event. These callbacks must work quickly and return; therefore, we should not be waiting for an input, for output. Callbacks can schedule requests, and evoke events.

    OS = for(;;) {
        wait for next event e;
        invoke callback for e;
        c(e,...);
    }
    

• Good programming for simple featuers (e.g. GUI)

• Error prone
• Assumption that callbacks are nice
• Complex and difficult to understand code
• Not thread safe

Threads

A thread is the smallest process an operating system can schedule. Most of the time, a thread is contained inside a process. So what exactly does a thread have? We can consider Thread = process - (file descriptor + memory + owner).

Cooperative Threads

There are two main form of threads, one is known as cooperative threads. In cooperative thread, each thread yields. (i.e. voluntarily releases control of CPU). Once a thread is given control, it will continue to run until it yields or is blocked.

    for(;;) {
        i++;
        yield();
        j++;
        yield();
        k = k*i*j;
    }
    

The disadvantage of such a method is that it is slow and ugly. As you can see, cooperative threading means we yield on every syscall. This can lead to some serious problems in terms of efficiency, and is very vulnerable to thread starvation.

A typical implementation of yield()
syscall => INT => trap => trap handler in kernel
                                           save registers into thread register
                                           choose some other thread that's ready to run
                                           restore Thread 2's register
                                           RETI (return instruction, new instruction)

Uncooperative Threads

The other form of threading is known as uncooperative thread or preemptive threading. The scheduler in this method determines when a thread's use of CPU time is too long. A timer is used to interrupt.

In the implementation, the motherboard sends a signal to CPU every 10ns. The CPU corresponds and traps when it gets signal. The kernel then takes control.

A common example would be a low priority thread is running. If a higher priority thread becomes able to run, the thread handler will eventually pause the low priority thread to allow the higher priority thread to run. This becomes more efficient that cooperative threading.

Mechanism vs Policy

Cooperative and uncooperative threading are two mechanisms that we use for deciding when, and under what terms, a thread will yield. Policy refers to the way in which we choose the next thread to run, once the current thread has yielded.

Scheduling Scale

To develop good policy, we must consider the lifetime of a particular job. We view the lifetime on three time scales:

• Long Term: Which jobs were admitted to the system in the first place? When will they be completed under our policy?
• Medium Term: Which processes reside in RAM?
• Short Term: Which threads get a CPU? This is the time scale on which we operate with scheduling algorithms.

Scheduling Metrics

• Wait time: How long one job waits after entering the queue before in begins execution. Ideally, we want to minimize this time as much as possible.
• Response time: The time it takes one job to produce output after entering the queue.
• Turn-around time/latency: The total amount of time from one job’s arrival into the queue to its completion.
• Context switching time: The time to switch from one process to another.

Scheduling Statistics

• Average (expected): The mean turn-around time
• Worst case: The longest turn-around time
• Utilization: The fraction of time the CPU is in use
• Throughput: The rate at which useful work is being done, ranging from 0.0 to 1.0
• Fairness: Are certain threads given priority over others
• Starvation: A situation in which a thread in queue never gets to run.

Scheduling Policy Examples

First-Come First-Served (FCFS)

Jobs are performed in order of their arrival into the queue.

• No starvation since every job waiting in the queue eventually runs. Therefore, FCFS is a fair policy.
• High throughput as a result of the CPU constantly doing useful work

• First-Come First-Served tends to favor long jobs over short jobs. Short jobs can end up having long wait times while a long job is running.
• As a result of the above con, FCFS can sometimes cause a convoy effect, that is, one process is busy while the rest are idle waiting for that process to finish.

Shortest Job First (SJF)

Jobs are performed in the order of their run time length, with a bias towards jobs with shorter run times.

• Average wait times can be less than those under FCFS.
• Average turnaround times are, in turn, also less than those under FCFS because of potentially shorter average wait times.

• Because of the preference to shorter jobs, SJF is unfair to longer jobs. If a long job is queued early and shorter jobs are queued after it, it may be possible that the long job never executes at all. This results in starvation.

Round Robin Scheduling

• Average wait time is less than in FCFS and SJF, since round robin moves into the next job after the quantum time, rather than after finishing the previous job.

• Average turnaround time is high because unfinished jobs must wait for the CPU after each quantum.

If an implementation of round robin places new process at the beginning of the queue, then starvation is a possibility if too many new processes arrive. To avoid starvation, new processes should be put at the end of the queue.

Priority Scheduling