CIS 25 - Notes 0005

CPU scheduling is the basics of multiprogramming. By switching the CPU among several processes the operating systems can make the computer more productive.

The objective of multiprogramming is to have some process running at all times, in order to maximize CPU utilization. On systems with 1 processor, only one process may run at a time; any other processes must wait until CPU is free to be rescheduled.

In multiprogramming, a process executes until it must wait (either interrupted, or doing IO), at which point, the CPU is assigned to another process, which again, executes until it must wait, at which point another process gets the CPU, and so on...

Processes generally execute a CPU burst, followed by an IO burst, followed by the CPU burst, followed by the CPU burst, etc. This cycle is central to all processes. Every process must have CPU bursts, and every process must do some IO.

The operating system maintains what is known as a ready-queue. Processes on this queue are ready to be executed. Whenever a currently executing process needs to wait (does IO, is interrupted, etc.) the operating system picks a process from the ready queue and assigns the CPU to that process. The cycle then continues.

When CPU Scheduling Occurs:

The system will do a context switch (changing currently executing process) when:

1. When a process switches from a running state to a waiting state. This will happen either with an IO request, or an explicit wait/sleep system call.

2. When a process switches from the running state to a ready state (when an interrupt occurs).

3. When a process witches from waiting state to a ready state (when IO completes).

4. When a process terminates.

Under circumstances 1 and 4, there is not much choice in terms of scheduling. Next process is picked from the ready queue and given the CPU. There is a choice under 2 and 3 however.

When scheduling happens only under conditions in 1 and 4, we say that scheduling is non-preemptive; otherwise we say it's preemptive.

In 1 and 4, we notice that the process will hold on to the CPU until it decides to free it (by doing IO) or terminating. If there is a problem with the process, it is quite likely not to allow any other process to execute. (This is what Windows 3.1 used.)

A preemptive scheduler will schedule timer interrupts to interrupt a process after some time period, in order to allow other processes to execute (this is what happens under 2 above). No process can hold on to the CPU indefinitely, because it will be interrupted. A preemptive system will also interrupt the current process if some other process finishes its IO.

Preemptive Problems

Preemptive systems sound so much more superior to the non-preemptive ones (no single process can take over the system, etc.), but there is a cost. A process does not control when it is interrupted. It could be interrupted when it is performing some critical task. If several processes are communicating with each other (via shared memory for example), there need to be safeguards to prevent data corruption.

Dispatcher

Dispatcher is a component involved in CPU scheduling. It is the code that does the context switch, switching to user mode, and giving control to the process.

It has to be as quick and as efficient as possible, since the time it spends is non-productive to the user (productive time to the user is time spent running user processes, everything else has to be designed to make sure that happens a vast majority of the time).

Scheduling Criteria

There are many scheduling algorithms, and many various criteria to judge their performance. Different algorithms may favor different types of processes. A few criteria are:

* CPU Utilization: We must make sure that the CPU is as busy as possible (executing user processes; not operating system code).

* Throughput: How much work the CPU is performing, or more precisely, how many processes complete in some timeframe.

* Turnaround time: From the view of any particular process, how much time does it take for the process to complete. (from the time it was submitted to the system, to the time it completes).

* Waiting time: Amount of time the process spends in the ready queue. The system cannot help the amount of time the process spends doing IO, but it can try to minimize the time it spends in the ready queue waiting to execute.

* Response time: How quickly does the system allow processes to respond? From the time you press a key, to the time the system allows the process to do IO, to the time the system allows the process to process your key press, to the time it allows the process to do IO to respond.

Some of these criteria are optimized differently. For some, its best to minimize the average time, for time, minimizing the maximum time, for others, minimizing the variance, etc.

Scheduling Algorithms

There are many algorithms, ranging in complexity and robustness.

First-Come, First-Serve Scheduling (section 6.3.1 in dinosaur book, page 157)

This algorithm treats the ready queue as a plain queue. No priority is assigned to any process. Processes are executed in the order in which they were put on the queue.

The algorithm is non-preemptive (when a process gets the CPU, it keeps it until it is done using it - the system doesn't kick it out to let another process in).

This algorithm has pretty bad average waiting time (since large processes can go in front of the short ones).

Shortest-Job-First Scheduling

This algorithm implements a priority queue based on the next CPU burst length. The next process to execute will always have the shortest CPU burst.

This algorithm is provably optimal in reducing average waiting time. The problem in this algorithm lies in the inability to know the exact burst time of a process. A process does not come into a system saying "I need 5 microseconds to execute." It just executes however long it takes. It's impossible to know the exact bust time until the process finishes its burst time.

So, while we have a perfect scheduling algorithm, it is not practical unless you know exactly the lengths of jobs to execute, which in reality, you almost never have.

There are estimates that you can apply to guess what the next CPU burst will likely to be. There is an exponential average formula on page 159 of your book that describes the estimation process.

Shortest Job First can be either preemptive or non-preemptive. The preemptive version is sometimes referred to as shortest-remaining-time-first, implying that as soon as some process attains the smallest burst size (because another process was executing), the CPU is interrupted to let the shortest CPU burst process to execute.

Priority Scheduling

Shortest Job First is just a special case of a class of scheduling algorithms called Priority Scheduling. They assign priority to tasks, and scheduler works with processes according to those priorities.

For example, a priority scheduling algorithm may let a critical system process execute more often than a non-critical user process.

A problem with all priority scheduling algorithm is infinite-blocking or starvation, where a process gets such a low priority, that it sits in the ready queue forever, waiting to execute.

Round-Robin Scheduling

The Round-Robin scheduling algorithm has a queue, similar to the First Come, First Serve algorithm. It is preemptive.

It allocates the CPU in time slices known as time quantum. A quantum is a fixed time period (say 10 microseconds, etc.), the CPU then allocates these quantum to processes. After a process spends its quantum executing on the CPU, it is preempted, and moved to the back of the queue, another quantum is assigned to the next process on the queue.

If the process releases the CPU before its quantum is up, it gets put on the ready queue, and the next process gets a time quantum to execute.

The performance of Round Robin algorithm is largely dependent on the size of the time quantum. If the size is too large, the system essentially turns into a First Come-First Serve, if the quantum size is too small; the system spends too much time doing context switching.

Multilevel Queue Scheduling

You can combine several algorithms into one. You can even have several queues, with various priorities, etc. Read section 6.3 in the dinosaur book for a detailed view of such setups.

Algorithm Evaluation

There isn't a great way to evaluate scheduling algorithms. One way that's guaranteed to work is to implement the algorithm and stick it into a real operating system. That's usually too expensive.

Deterministic Modeling

One way to evaluate an algorithm is to do deterministic modeling. You obtain (or generate) process burst times, and run them through the algorithm, and see how it performs in comparison to other algorithms running the same numbers.

This doesn't provide a real life view, since real process burst times are not known beforehand. SJF (Shortest Job First) is optimal when burst times are known.

Queuing Models

This analysis concentrates on the relationships among various queues and their sizes. It studies the differences between time spend in the CPU and time spent doing IO.

Simulations

A more accurate analysis is a simulation. A system is built to imitate the real system, and is tested. Various algorithms can then be plugged in and analyzed.