Scheduling

Whether scheduling is based on processes or threads depends on whether the OS is multi-threading capable: Given a group of ready processes or threads, which process/thread to run?

When to schedule?

• When a process is created

• When a process exits

• When a process blocks

• When an I/O interrupt occurs

Categories of Scheduling Algorithms

• Interactive: preemption is essential, preemption is a means ofr the OS to take away the CPU from a currently running process/thread

• Batch:

  • No user impatiently waiting

  • mostly non-preemptive, or preemptive with long period for each process

• Real-time: deadlines

Scheduling Algorithms: Goals and Measures

• Turn Around Time (Batch)

• Throughput (e.g. Jobs per second)

• Response Time (Interactive)

• Average wait times (how long waiting in ready queue)

CPU / IO Burst

CPU Burst: a sequence of instructions a process runs without requesting I/O. Mostly dependent on the program behavior.

IO "Burst": time required to satisfy an IO request while the Process can not run any code. Mostly dependent on system behavior (how many other IOs, speed of device, etc.)

Scheduling Algorithms Goals

All systems

• Fairness: giving each process a fair share of the CPU

• Policy enforcement: seeing that stated policy is carried out

• Balance: keeping all parts of the system busy

Batch systems

• Throughput: maximize jobs per hour

• Turnaround time: minimize time between submission and termination

• CPU utilization: keep the CPU busy all the time

Interactive systems

• Response time: respond to requests quickly

• Proportionality: meet users'expectations

Real-time systems

• Meeting deadlines: avoid losing data

• Predictability: avoid quality degradation in multimedia systems

Process State Transition

Almost ALL scheduling algorithms can be described by the following process state transition diagram or a derivative of it (we covered some more sophisticated one in prior lecture)

Process State Transition

Scheduling Algorithms

First Come First Serve (FIFO / FCFS)

Non-preemptive (run till I/O or exit). Processes ordered as queue: A new process is added to the end of the queue. A blocked process that becomes ready added to the end of the queue

Main disadvantage: Can hurt I/O bound processes or processes with frequent I/O

Shortest Job First

Non-preemptive. Assumes runtime is known in advance. Is only optimal when all the jobs are available simultaneously.

Shortest Remaining Time First/Next (SRTF)

Scheduler always chooses the process whose remaining time is the shortest. Runtime has to be known in advance. Preemptive or non-preemptive (wait till block or done)

This typically reduces average turnaround time.

Round Robin

Each process is assigned a time interval referred to as quantum. After the quantum, the CPU is given to another process (i.e. CPU is removed from the process/thread aka preemption).

RR = FIFO + preemption/quantum

Length of the quantum

• If too short, too many context switches will result in lower CPU efficiency

• If too long, will cause poor response to short interactive

• quantum longer than CPU burst is good

Priority Scheduling

Each process is assigned a priority. Runnable process with the highest priority is allowed to run. Priorities are assigned statically or dynamically.

Must not allow a process to run forever:

• Can decrease the priority of the currently running process

• Use time quantum for each process

Multiple Level Queuing (MLQ)

Multiple levels of priority (MLQ) plus each level is run round-robin.

Issue: starvation if higher priorities have ALWAYS something to run

Multi-Level Feedback Queueing (MLFQ)

Aka priority decay scheduler. If process has to be preempted, moves to (dynamic_priority--).

When it reaches "-1", dynamic priority is reset to (static_priority-1): This creates some issues when high prio is reset before low prio is executing.

When a process is made ready (from blocked): its dynamic priority is reset to (static_priority-1).

What kind of process should be in bottom queue?

• Higher priority for IO-Bound tasks

• Lower priority for CPU-Bound tasks

Comparisons

Algorithm	Advantages	Disadvantages
First Come First Serve (FCFS)	FCFS algorithm doesn't include any complex logic, it just puts the process requests in a queue and executes it one by one. Hence, FCFS is pretty simple and easy to implement. Eventually, every process will get a chance to run, so starvation doesn't occur.	There is no option for pre-emption of a process. If a process is started, then CPU executes the process until it ends. Because there is no pre-emption, if a process executes for a long time, the processes in the back of the queue will have to wait for a long time before they get a chance to be executed.
Shortest Job First (SJF)	Each process is served by the CPU for a fixed time quantum, so all processes are given the same priority. Starvation doesn't occur because for each round robin cycle, every process is given a fixed time to execute. No process is left behind.	The throughput in RR largely depends on the choice of the length of the time quantum. If time quantum is longer than needed, it tends to exhibit the same behavior as FCFS. If time quantum is shorter than needed, the number of times that CPU switches from one process to another process, increases. This leads to decrease in CPU efficiency.
Priority based Scheduling	The priority of a process can be selected based on memory requirement, time requirement or user preference. For example, a high end game will have better graphics, that means the process which updates the screen in a game will have higher priority so as to achieve better graphics performance.	A second scheduling algorithm is required to schedule the processes which have same priority. In preemptive priority scheduling, a higher priority process can execute ahead of an already executing lower priority process. If lower priority process keeps waiting for higher priority processes, starvation occurs.

Usage of Scheduling Algorithms in Different Situations

Situation 1: The incoming processes are short and there is no need for the

processes to execute in a specific order.

In this case, FCFS works best when compared to SJF and RR because the processes are short which means that no process will wait for a longer time. When each process is executed one by one, every process will be executed eventually.

Situation 2: The processes are a mix of long and short processes and the task

will only be completed if all the processes are executed successfully in a given time.

Round Robin scheduling works efficiently here because it does not cause starvation and also gives equal time quantum for each process.

Situation 3: The processes are a mix of user based and kernel based processes.

Priority based scheduling works efficiently in this case because generally kernel based processes have higher priority when compared to user based processes.

For example, the scheduler itself is a kernel based process, it should run first so that it can schedule other processes.

Load Balancing (LB)

Occasionally or when no process is runnable, scheduler[i] looks to steal work elsewhere.

Each scheduler maintains a load average and history to determine stability of its load. LB typically done in a hierarchy.

Frequency of neighbor check:

• Level in hierarchy: cost to migrate

• Make "small" changes by pulling work from other cpu