6 July 2001 WORK IN PROGRESS!
ultitasking operating systems can run many programs at the same time, but these must be organized in some way. This is the task of the process scheduler, which must allow each process some time on the processor. A badly designed scheduler simply allows each of the processes the same period of time. Whereas a welldesigned scheduler allows for priority levels, and can make decisions on which processes should be run, at a given time. Typically system processes are more important than user programs, and need to be run at regular intervals, and will thus be given a higher priority over user programs. Two typical scheduling algorithms are roundrobin and shortestjobfirst.
RoundRobin (RR) is a firstcome, firstserved schedule with preemption, where each process is given a finite time slice on the processor. The queue is circular, thus when a process has been run, the queue pointer is moved to the next process, as illustrated in Figure 1. This is a relatively smooth schedule and gives all processes a share of the processor. As children we would typically be assigned to things in a roundrobin way, especially when there were too many demands on a certain resource, and we didn't get enough time on it. A good example is when children want to get access to a bouncy castle, and there's a limit on the number that can be on the castle at any one time. An example schedule might be to allow a child onto the castle for a minute, and then they must come off, and go back to the end of the queue. The next child in the queue can then take their place on the castle.
Figure 1: Round robin (© billatnapier)
This is one of the most efficient algorithms, and involves estimating the amount of time that a process will run for, and taking the process which will take the shortest time to complete. A problem for the scheduler is thus to determine the amount of time that the process will take to complete its task. This is not an easy task. For example, let's say that we've got four tasks to complete. Task 1 will take one hour, task two take two hours, task three will take three hours, and finally task four will take eight hours to complete. We could schedule the task to each get halfanhour of processing time. Once we have finished this time, we make a decision on what task to do next. Thus within four hours we would have the following:
ROUND ROBIN
Time slot (in half hour blocks)

Task (remaining time to completion)

1

Task 1 (0:30)

2

Task 2 (1:30)

3

Task 3 (2:30)

4

Task 4 (7:30)

5

Task 1 (complete)

6

Task 2 (1:00)

7

Task 3 (2:00)

8

Task 4 (7:00)

It can be seen that we have only completed one task, but if we were to take the shortestjob first, then:
SHORTESTJOBFIRST
Time slot (in half hour blocks)

Task (remaining time to completion)

1

Task 1 (0:30)

2

Task 1 (complete)

3

Task 2 (1:30)

4

Task 2 (1:00)

5

Task 2 (0:30)

6

Task 2 (complete)

7

Task 3 (2:30)

8

Task 3 (2:00)

We can see that we've now completed two tasks, and we're at the same point as the previous example with Task 3. From the user's pointofview this will be perceived as possibly the most satisfying as more tasks have actually been competed in a shorter time. From a computer system pointofview the user will perceive that the processes are running faster, as they are being completed at a perceived a faster time (although Task 4 is being starved on processing time, in order to achieve this). The only problem in that some of the processes will not make any progress until they are allowed access to the processor.
The time remain in each of the cases will be the same as the first scheme will require 10 hours to complete (Task 2 still requires 1 hours, Task 3 still requires 2 hours and Task 4 still requires 7 hours), and the shortjob first scheme still requires 10 hours (Task 3 still requires 2 hours and Task 4 still requires 8 hours). Thus the shortjobfirst is only perceived to be running tasks faster. Shortestjobfirst is very efficient on processor time with batch systems, as batch processes are less susceptible to process starvation. The roundrobin approach works in a much fairer way, but can suffer if there are large processes running on the system, as these will general slow down the completion of other processes.
Chapter 4, Mastering Computing, W.Buchanan, Palgrave.
Comments on this essay
If you've got any comments on this essay (no matter if you agree or
disagree with it), please send them to me using the form below.
Note your comments may be published to a comments pages, but none
of your details will be added to the comment, just the date that it
was sent. Thank you.
