4. Parallel Computing 14. Introduction

14.3  Scheduling

In the UNIX® example above, there could well be more processes than there are

processors to execute those processes. In this case, the states of non-running processes

are saved in a pool and executed when a processor becomes available. This happens, for

example, when a process terminates. But it also happens when a process waits for i/o.

This notion of multiprocessing is one of the key ways of keeping a processor busy when

processes do i/o requests.

In the absence of any priority discipline, a process is taken from the pool whenever a

processor becomes idle. To provide an analogy with the field-plowing problem, work

apportionment is simplified in the following way: Instead of dividing the field into one

segment per tractor, divide it into many small parcels. When a tractor is done plowing its

current parcel, it finds another unplowed parcel and does that. This scheme, sometimes

---

588

Parallel Computing

called self-scheduling, has the advantage that the tractors stay busy even if some run at

much different rates than others. The opposite of self-scheduling, where the work is

divided up in advance, will be called a priori scheduling.