Scheduler

Scheduler is responsible for scheduling many processes. This is called scheduling. Who gets to use the Processor at any given moment? Different processes will have different priorities. There are also properties enforced by system policies that affect the decision. It is usually implemented in C, unlike the Dispatcher which is usually in Assembly

Context Switch

Context Switch

• Grab attention of processor
  • Preemptive: external interrupt, like timer
  • Nonpreemptive: system call (trap), I/O request, process exit
• Save the state of current process
  • Dump PC and registers of current process (at the start of the ready queue) into PCB
• Select new process to run
  • Short Term Scheduler scheduling algorithm result → select a PCB to “dispatch”
• Dispatch the selected process
  • Call Dispatcher for the closest PCB in the Ready Queue, load state of the selected PCB into processor registers (PC, Register File)

The scheduler does not call any process to run. Instead it rearranges the PCB queues and then returns to the first out of the queue.

TLB

Context Switching

• Kernels can have page maps, but the kernel page map doesn’t change when we do a Context Switch. Hence the user/kernel flag.
• When we do a Context Switch, the PTBR changes, and consequently the page table we have access to changes to that of the new proccess.
  • Each process owns its own user space. Therefore, we must purge all of the cached user entries in the TLB after a Context Switch because they still point to the memory space of the previous process. Whatever user entries the old process cached in the TLB are useless to the new process, because the two process don’t share their memory.
  • Cached kernel entries do not need to be purged because the kernel space is shared by all processes.

• The Dispatcher is responsible for performing this purge

Link to original

Link to original

Loader

Loader

An OS Subroutine responsible for loading user programs from disk to Memory

Link to original

Dispatcher

Dispatcher

An OS Subroutine that populates the Processor registers with the state of the Process selected for running by the Short Term Scheduler

• Usually written in Assembly
• Responsible for TLB user cache purging

Link to original

Long Term Scheduler

Determine whether a Program should be turned into a Process. “Do I have the resources to finish you?”

Medium Term Scheduler

Deals with processes that already exist. “Can I let you run efficiently? Should I put you on the backburner to let other more efficient processes finish first?” Concerned with orchestrating Memory Pressure & Goldilocks Multiprogramming Avoids Thrashing and constant Page Faulting, i.e. ideal CPU utilization, minimal bottlenecking

Short Term Scheduler

We already know we have enough resources to go around. “Who gets to run next?” The scheduler’s job is to order the ready queue.

CPU Burst

Continuous CPU Activity by a process before requiring an I/O operation

I/O Burst

Activity initiated by the CPU on an I/O device

Ready Queue

Queue of PCBs that represent the set of memory resident processes that are ready to run on the CPU

I/O Queue

Queue of PCBs that represent the set of memory resident processes that are waiting for some I/O operation either to be initiated or completed

Thrashing

A phenomenon wherin the dynamic memory usage of the processes current in the Ready Queue exceed the total memory capacity of the system. The system’s resources have been overcommitted. The Medium Term Scheduler would get involved and evict some PCBs out of the Ready Queue. See Goldilocks Multiprogramming, Page Fault

Scheduling Algorithms

Scheduling Algorithm

An Algorithm used by the Scheduler

Name	Property	Scheduling criterion	Pros	Cons
FCFS	Intrinsically non-preemptive; could accommodate preemption at time of I/O completion events	Arrival time (intrinsic property)	Fair; no starvation	High variance in response time; convoy effect
SJF	Intrinsically non-preemptive; could accommodate preemption at time of new job arrival and/or I/O completion events	Expected execution time of jobs (intrinsic property)	Preference for short jobs; provably optimal for response time; low variance in response times	Potential for starvation; bias against long running computations
Priority	Could be either non-preemptive or preemptive	Priority assigned to jobs (extrinsic property)	Highly flexible since priority is not an intrinsic property; its assignment to jobs could be chosen commensurate with the needs of the scheduling environment	Potential for starvation (ameliorated by dynamically increasing priority in proportion to waiting time)
SRTF	Similar to SJF but uses preemption	Expected remaining execution time of jobs (intrinsic)	Similar to SJF	Similar to SJF
Round robin	Preemptive allowing equal share of the processor for all jobs	Time quantum (extrinsic)	Equal opportunity for all jobs	Overhead for context switching among jobs

Preemptive

Algorithm that forcible takes the Processor away from the current scheduled Process in response to an external event (e.g. I/O completion Interrupt, timer interrupt)

Shortest Remaining Time First

Round Robin

Priority

Round Robin

• Round Robin is a Preemptive Scheduling Algorithm
• Requires a timer interrupt
• When a processes starts, it is given a time quantum (time slice) which limits the continuous CPU time it may use
• When a process is dispatched, the timer is set to interrupt at the end of the remaining time quantum
• If a processes uses up its remaining time quantum
  • The process is interrupted
  • The scheduler is called to put the process at the end of the ready list
  • The process’ remaining time quantum is reset
• If an interrupt other that the timer occurs, the process’ remaining time quantum is reduced by the amount of time it has used prior to the interrupt

Link to original

Nonpreemptive

An algorithm that allows the current scheduled process on the CPU to voluntarily reliquish the processor (either by terminating or making an I/O system call)

Intrinsic

First Come First Serve

Shortest Job First

Extrinsic

Priority

Transclude of Linux#linux-scheduler

Link to original

Metrics

where are respectively the Wait Time, Execution Time, and Turnaround Time (elapsed time) for a job

Throughput

Jobs per second

Execution Time

How long did this job stay on the CPU during its execution?

Turnaround Time

How long did this job take to complete after being requested?

Average Turnaround Time

Average the turnaround times

Wait Time

How long did this job remain idle after being requested?

Average Wait Time

Average the wait times

Response Time

The turnaround time, but from a user centric perspective.

CPU Utilization

Percentage of time the CPU is busy

Starvation

User-centric metric that signfies denial of service to a particular process or set of processes due to some intrinsic property of the scheduler. E.g. I put in a long job, and all my friends are spamming short jobs; Shortest Job First

Convoy Effect

User-centric metric that results in a detrimental effect to some set of processes due to some intrinc property of the scheduler. E.g. I put in a long job, and all of my friends with short jobs have to wait; First Come First Serve

Environments

Domains	Environment	Workload characteristics	Types of schedulers
Desktop	Timeshared, interactive, multiprogrammed	I/O bound	Medium-term, short-term, dispatcher
Servers	Timeshared, multiprogrammed	Computation bound	Medium-term, short-term, dispatcher
Business	Batch-oriented, timeshared, multiprogrammed	I/O bound	Long-term, Medium-term, short-term, dispatcher
HPC	Batch-oriented, timeshared, multiprogrammed	Computation bound	Long-term, Medium-term, short-term, dispatcher
Cloud/grid	Batch-oriented, timeshared, multiprogrammed	Computation bound	Long-term, Medium-term, short-term, dispatcher
Embedded	Timeshared, interactive, multiprogrammed	I/O bounds	Medium-term, short-term, dispatcher
Pervasive	Timeshared, interactive, multiprogrammed	Combination of I/O bound and computation bound	Medium-term, short-term, dispatcher