Scheduling

1. Scheduling

A process can have multiple states:

• New: the process is being created (Can be enabled to READY).
• Ready: runnable and waiting for processor (Can be dispatched to RUNNING).
• Running: executing on the processor (Can be preempted to READY, blocked to WAITING, or terminated to TERMINATED).
• Waiting: blocked (Can be enabled to READY).
• Terminated: process has finished.

A scheduler chooses which threads to preempt and dispatch to the processor. The scheduler is responsible for:

1. Ensuring fairness.
2. Avoiding starvation.
3. Enforce policies.
4. Maximize resource utilisation.
5. Minimize overhead.

Scheduling can be preemptive or non-preemptive:

• Non-preemptive: Let process run until it blocks or voluntarily releases the CPU.
• Preemptive: Let process run for a max time. Requires clock interrupt.

1.1 FCFS

First come first serve (Non preemptive). Every thread is added to the end of the queue. The first thread in the queue is the next to run.

Advantages:

• No indefinite postponement. All processes are eventually scheduled.
• Very easy to implement.

Disadvantages:

• Suffers from head-of-line (HOL) blocking. If a long process is at the front of the queue, all other processes must wait.

1.2 RR

Round robin (non-preemptive). Each thread is given a time slice to run. If the thread does not finish in the time slice, it is moved to the end of the queue.

• Fairness: Ready jobs get an equal share of the CPU.
• Response Time: Good for a small number of jobs
• Average Turnaround Time: Low when run-times differ, high when run-times similar.

A larger quantum means a smaller overhead but worse response time. A smaller quantum means a larger overhead but better response time.

A good quantum value should be much larger than the context switch time but provide a decent reponse time. This varies depending on the system:

• Linux uses ms.
• Windows client uses ms.
• Windows server uses ms.

1.3 SJR

Shortest Job First (non-preemptive). Each thread's run-times are known in advance. The shortest job is run first.

However, runtimes are usually not available in advance. We may compute CPU burst estimates based on heuristics, or by user-supplied estimates.

1.4 SRT

Shortest Remaining Time is the preemptive version of shortest job first. Choose process whose remaining time is shortest. When a new process arrives with an execution time less than the remaining time of the current process, preempt the current process. Allows new short jobs to get good service.

1.5 Fair-Share RR

Fair-share scheduling is a generalization of round-robin. Users are assigned some fraction of the CPU. Within each user, round-robin is used.

1.6 Priority

Jobs are run based on their priority. Always run the job with the highest priority. Priorities can be externally defined (by the user) or based on some process-specific metrics (e.g. their expected CPU burst).

Priorities can be static or dynamic:

• Static: Priority does not change.
• Dynamic: Priority changes based on the behavior of the process.

2. General Purpose Scheduling

We want to:

• Favour short and I/O bound jobs for good resource utilisation and short response times.
• Quickly tdetermine the nature of a job and adapt to changes.

2.1 Multilevel Feedback Queues

A multilevel feedback queue is form of priority scheduling. There is one queue for each priority level. Run job on highest non-empty priority queue. Each queue can use a different scheduling algorithm (usually round-robin).

• Need to determine current nature of the job. Job priorities recomputed periodically (e.g. exponentially weighted moving average).
• Need to worry about starvation of lower-priority jobs. Aging: increase priority of jobs in lower-priority queues.

MLFQS is bad for a few reasons:

• Not very flexible - Applications have little control, priorities make no guar=rantees.
• Does not react quickly to changes - often needs a warm-up period. Problem for real-time systems.
• Cheating is a concern - add meaningless IO to boost priority?
• Cannot donate priority.

2.2 Lottery Scheduling

Jobs recieve lottery tickets of various resources. At each scheduling decision, one ticket is chosen at random and the job holding that ticket wins. The more tickets a job has, the more likely it is to win.

• Number of lottery tickets is meaningful.
• Highly responsive.
• No starvation.
• Jobs can exchange tickets.
• Adding / removing jobs affects remaining jobs proportionally.
• Unpredictable response time.

3. Summary

Scheduling algorithms often need to balance conflicting goals. Different scheduling algorithms are appropriate in different ways.