Process Scheduling
| On path: OS Topics | 1: Concepts • 2: Cache • 3: Context • 4: Processor Privilege • 5: Process Scheduling • 6: Exceptions • 7: Interrupts • 8: Direct Memory Access (DMA) • 9: Virtualisation • 10: Hypervisor |
|---|
| On path: Processes | 1: Processes • 2: Context • 3: Process Control Block (PCB) • 4: Multi Threading • 5: Threads • 6: Interprocess Communication • 7: Process Scheduling • 8: Scheduler • 9: Process States • 10: Process Priority |
|---|
| Depends on | Processes • Virtualisation • Concepts • Resources |
|---|
In a multi-tasking operating system not all the processes (tasks) are really running simultaneously; at most the maximum number of running processes equals the number of processor ‘cores’ available (‘traditionally’ one, but nowadays liable to be a few more than that). Any illusion of many simultaneous processes is maintained by switching attention amongst them rapidly (by human standards).
The scheduler is the part of an operating system which decides which process(es) to run at any given time. The algorithm(s) used by a scheduler to pick the ‘next’ process are many and varied and can depend on the particular circumstances. Only a few examples are mentioned here and, if you want more, you should consult the literature to a depth you feel is appropriate.
The approach to scheduling usually varies according to the purpose of the computer system – sometimes referred to as a “processing mode”.
Interactive processing
This will be a familiar mode where the user constantly interacts with the computer which, nevertheless, occasionally has some time-consuming tasks: think of editing and then compiling a big program. Scheduling is arranged to give reasonable responsiveness to various jobs as the user changes focus – plus there may be some background processing which is not as apparent.
In interactive systems a common approach is “round robin” scheduling. This is an attempt to give all processes equal ‘turns’ by taking the next process from the front of a FIFO queue whilst appending a de-scheduled process to the back. This is most obviously applicable when time-slicing, (or cooperative ‘yielding’) when a running process is de-scheduled without being blocked. The scheduler needs to try to be ‘fair’ to avoid starving any process of a share of processor time, although the details might be influenced by the process’ priority.
Example: the browser you’re using right now.
Real-time processing
Real-time computing requires a guaranteed response with a certain, maximum latency. Contrary to some opinions, this does not make it fast: in fact it is essential that the processor is regularly becoming idle because if it is not it means it hasn’t completed everything it needed to do in time.
Real-time schedulers typically rely heavily on priority, with some processes being identified as more urgent than others (i.e. low latency is required); these will typically be run in preference to lower priority (but still time-constrained) jobs.
Real-time tasks are sometimes (somewhat arbitrarily) divided between “hard” and “soft” constraints:
- A hard real-time task is one where failure to meet a constraint leads to a system failure.
- Example: car’s braking system.
- A soft real-time task could be summarised as one where undue delay leads to annoyance.
- Example: bank’s cash dispenser.
Real-time example: an aircraft control system may need to react to control inputs within (say) 10 ms whereas updating the pilot’s radar display may require more work but is okay as long as it’s done once per second.
Batch processing
Batch scheduling picks a particular job and completes that before proceeding to the next. It is therefore not responsive to interactions but is efficient at processing. It is often appropriate for big data processing jobs.
A common approach in batch jobs is ‘shortest job first’. A simple analysis will show that this finishes more jobs, sooner. For example, if job A takes 1 hour and job B takes two hours, A then B gives an overall latency of 1 + (1+2) = 4 hours (average = 2 hours) whereas B then A gives an overall latency of 2 + (2+1) = 5 (average = 2.5 hours). This is worth remembering when scheduling your own, personal tasks!
Batch processing is probably less familiar to you than some other processing modes, but is useful in (for example) supercomputer/mainframe applications where a process has a lot of data distributed across many processing elements. (The usual example is “processing the payroll” although ‘ordinary’ computers can probably manage that fairly quickly, these days.)
| Also refer to: | Operating System Concepts, 10th Edition: Chapter 3.2, pages 110-116 |
|---|
