8.1 Scheduling Flashcards
Scheduling
An OS must allocate resources among competing processes
The resource provided by a processor is execution time
- The resource is allocated by means of a schedule
Aim of scheduling
To assign processes to be executed by the processor over time
- In a way that meets system objectives, such as response time, throughput and processor efficiency
Objectives of Scheduling
Share time fairly among processes Prevent starvation of a process Use the processor efficiently Have low overhead Prioritise processes when necessary
Long term scheduling
Determines which programs are admitted to the system for processing
-May be first come first served
-Or according to priority
Controls degree of multiprogramming
More processes, smaller percentage of time each process is executed
Medium term scheduling
Part of swapping function
Swapping in decisions are based on the need to manage the degree of multiprogramming
Short term scheduling
Known as the dispatcher Executes most frequently Invoked when an event occurs -Clock interrupts -I/O interrupts -OS calls -Signals
Aim of short term scheduling
To allocate processor time to optimise certain aspects of system behaviour.
A set of criteria is needed to evaluate the scheduling policy.
Short term scheduling criteria USER V SYSTEM
User oriented
-Response time
–Elapsed time between request submission until there is an output
System Oriented
-Effective and efficient utilisation of the processor
Short term scheduling criteria PERFORMANCE
Performance related - Quantitive, easily measured -EG Response time & throughput Non performance related -Qualitative -Hard to measure
FORMULAS
Turn around time = Finish Time - Arrival Time
Waiting Time = Start Time - Arrival Time
Throughput = Processes Number / Total Time
Priorities
Scheduler will always choose a process of higher priority over one of lower priority
Have multiple ready queues to represent each level of priority
Starvation
Problem
-Lower priority may suffer starvation if there is a steady supply of high priority processes
Solution
-Allow a process to change its priority based on its age or execution history
Selection Function
Determines which process is selected for execution
If based on execution characteristics then important quantities are
-W = time spent in system so far, Waiting
-E = time spent in Execution so far
-S = total Service time required by the process, including E
Decision Mode
Specifies the instants in time at which the selection function is exercised
Two categories
-Non-Preemptive
-Preemptive
Nonpreemptive vs Preemptive
Nonpreemptive
-Once a process is in the running state, it will continue until it terminates or blocks itself for I/O
Preemptive
-Currently running process may be interrupted and moved to ready state by the OS
-Preemption may occur when new process arrives, on an interrupt, or periodically
First come first served FCFS
Each process joins the ready queue
When the current process ceases to execute, the longest process in the ready queue is selected
A short process may have to wait a very long time before it can execute
Favors CPU-Bound processes
-I/O processes have to wait until CPU bound process completes
Round Robin RR
Uses preemption based on a clock
-Also known as time slicing, because each process is given a slice of time before being preempted
Clock interrupt is generated at periodic intervals
When an interrupt occurs, the currently running process is placed in the ready queue
-Next ready job is selected
Shortest Process Next SPS
Nonpreemptive
Process with shortest expected processing time selected next
Short process jumps ahead of longer processes
Predictability of longer processes is reduced
If estimated time for process not correct, the OS may abort it
Possibility of starvation for longer processes
Shortest Remaining Time SRT
Preemptive version of shortest process next policy
Must estimate processing time and choose the shortest
Highest response ratio next HRRN
Choose next process with the greatest ratio
Ratio = time spent waiting + expected service time / expected service time
Scheduling Algorithms 1
The performance of a system as perceived by the user depends on many factors, including user expectations
Two common measures are
-Mean turnaround time: average time in the system
-Mean waiting time: average time spent in ready or blocked state
Scheduling Algorithms 2
Consider a system with 3 processes in the READY state
- The scheduler is about to select one of these to become the RUNNING PROCESS
- Each process is expected to use different CPU times
- A = 6 units
- B = 4 units
- C = 2 units
- The following slides show the behaviour of the system with different algorithms
FCFS
The processes are placed in the READY queue where the first process becomes the RUNNING process
No priority, so
-Short, important processes may have to wait for long and unimportant processes to finish
SJF Shortest Job First
Processes taken from the queue in order of their estimated CPU burst time
The shortest process becomes the running process (C-B-A here)
Priority is given to short tasks
CPU burst times are difficult to estimate
Results may not be as predictable in practice as they are in theory
Round Robin 1 RR
RR scheduling uses QUANTUM as a period of time
Processes are taken from the queue in some order
The process is allowed to run for a max time (quantum)
If the task does not finish in this time, it is returned to queue
Good for multi-user interactive systems
Length of quantum chosen affects performance
