Scheduling - A Nightmare!!! on CPU street

• Not that different ... supermarkets, your tutorials and labs, TV programs, aircrafts and trains etc
• Multiple processes running on a machine, competing for resources
• Usually the number of processes are much more than processors
• It is an NP hard problem - i.e. optimal allocation cannot be guaranteed - however, a set of heuristics possible
• The scheduler (just like your lab and tutorial scheduling) is trying to satisfy a number of different (often conflicting) criteria
• Processes are unique and unpredictable (file I/O, computation etc)

Types :

• Preemptive vs Non-preemptive : Is the execution of a process(es) interruptible
• Static vs Dynamic : Is scheduling done once, or adjusted during execution
• Priority (static or dynamic) assignment ... numerous methods

What criteria is the scheduler balancing ?

• Fairness : Share CPU among various users in some equitable way
• Efficiency : Keep the CPU(s) as busy as possible - ideally 100
• Response Time : Minimise response time for interactive users
• Turnaround : Minimise the time to obtain an output from the system
• Throughput : Maximise the number of jobs processed per a unit of time
• Predictable : Minimise load variation effect on execution
• Priorities : In addition to all of the above, also take process priorities into consideration
• ... and others - can you think of any ?

There are three - so called - scheduling levels :

• High-level scheduling : job scheduling or program scheduling - each made of groups of processes
• Intermediate level scheduling : Which processes should compete for the CPU. Meeting some overall systemwide objectives - over a longer term
• Low level scheduling : which ready processes will be assigned the CPU, achieves the dispatching of processes to CPU. Performed by the dispatcher.

Scheduling assumptions : Lots of them !!

Bunch of algorithms for CPU scheduling - big area of research in the 70s. Assume :

• One program per user
• one process (thread) per program
• programs are independent

Unrealistic!!!! - however need to simply to solve.