Scheduling

Scheduling

  • We have to choose a 'ready' process to run, efficiently.
  • We can just use a queue - add all processes onto it and work through them one by one, shuffling them to the end after their turn.
  • If we have threads waiting for something to be unblocked, we can have multiple queues per blocking item, and each unblocking event we release one.

scheduling%20queue.png

Processes are becoming IO bound because CPU is way faster than IO processing. Running a CPU bound process holds everything up, whilst running an IO bound process.

The aim of a scheduler is to be fair (give all processes a go), enforce the scheduling and make the system as efficient as possible. Depending on the system (as categorised below), there are other aims as well (e.g. meeting deadlines)

Batch Systems

No users directly waiting, can optimise for overall machine performance.

Interactive Systems

Users directly waiting for their results, can optimise for users perceived performance

Round Robin/ Round Robin with Priorities.

Stick processes into queues on a first-in-first-out basis. Give each process a time slice, and when that's done stick them back on the end of the queue. You can give processes a priority if you like, and do higher priority queues and then lower priority queues. Perhaps recalculate priority every second.
You might bump up priority if something yields voluntarily, or bump it down if it doesn't.

Realtime Systems

Jobs have deadlines, must schedule such that all jobs (mostly) meet their deadlines. Deadlines may be soft (99.9% meet deadlines e.g. telecommunications) or hard (100% deddlines e.g. air traffic control). They can be slow as long as it is predictable.

To schedule them, we have to know their deadline and the maximum run-time. (and of course the arrival time).

Periodic vs Sporadic

Period tasks are regular. They have a time-period to run in and usually arrive at the start and deadline at the end. Their max run time is the same each time.

Sporadic tasks arrive whenever, all details are arbitrary.

Static Table-Driven

Works for periodic tasks. We precompute a table offline. Requires entire schedule to be recomputed if we need to change the task set

Static Priority-Driven

Also used for periodic tasks. We calculate a priority for each task and use that for precomputation.

Rate Monotonic Scheduling

We assign tasks based on the period of each task. Short period = high priority. (Period = deadline-arrival time).
Only works with low CPU utilisation.

Earliest Deadline First Scheduling

Just put the one with the earliest deadline first. Interrupt a running task if a new earlier deadline arrives.

Dynamic

Works for any kind of task.

A new activity is only accepted if a schedule that fulfills all existing jobs AND the new activity, all on time, can be found. Else it says to fuck off to the new activity.