FUDAMENTALS OF OPERATING SYSTEMS - COMP355
Week 3b
FUDAMENTALS OF OPERATING SYSTEMS
References - Operating System Concepts – 9th Edition courtesy - Silberschatz, Galvin and Gagne
Chapter 3: CPU Scheduling – (cont)
Multilevel Queue
Ready queue is partitioned into separate queues, eg:
· foreground (interactive)
· background (batch)
Process permanently in a given queue
Each queue has its own scheduling algorithm:
· foreground – RR
· background – FCFS
Scheduling must be done between the queues:
· Fixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation.
· Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; i.e., 80% to foreground in RR.
· 20% to background in FCFS.
Multilevel Queue Scheduling
Multilevel Feedback Queue
A process can move between the various queues; aging can be implemented this way.
Multilevel-feedback-queue scheduler defined by the following parameters:
· number of queues
· scheduling algorithms for each queue
· method used to determine when to upgrade a process
· method used to determine when to demote a process
· method used to determine which queue a process will enter when that process needs service
Example of Multilevel Feedback Queue
Three queues:
· Q0 – RR with time quantum 8 milliseconds
· Q1 – RR time quantum 16 milliseconds
· Q2 – FCFS
Scheduling
· A new job enters queue Q0 which is served FCFS
o When it gains CPU, job receives 8 milliseconds
o If it does not finish in 8 milliseconds, job is moved to queue Q1
· At Q1 job is again served FCFS and receives 16 additional milliseconds
o If it still does not complete, it is preempted and moved to queue Q2
Multiple-Processor Scheduling
CPU scheduling more complex when multiple CPUs are available.
Homogeneous(uniform) processors within a multiprocessor.
Asymmetric multiprocessing - only one processor accesses the system data structures, alleviating the need for data sharing.
Symmetric multiprocessing (SMP) - each processor is self-scheduling, all processes in common ready queue, or each has its own private queue of ready processes.
· Currently, most common
Processor affinity - process has affinity(similarity) for processor on which it is currently running.
· soft affinity
· hard affinity
· Variations including processor sets
Multiple-Processor Scheduling – Load Balancing
If SMP, need to keep all CPUs loaded for efficiency.
Load balancing - attempts to keep workload evenly distributed.
Push migration - periodic task checks load on each processor, and if found pushes task from overloaded CPU to other CPU.
Pull migration - idle processors pulls waiting task from busy processor.
Operating System examples for using scheduling.
Linux scheduling - Preemptive, priority based scheduling.
Windows scheduling - Priority-based preemptive scheduling
Solaris scheduling - Priority-based scheduling
Algorithm Evaluation
How to select CPU-scheduling algorithm for an OS?
Determine criteria, then evaluate algorithms.
Deterministic modeling
· Type of analytic evaluation.
· Takes a particular predetermined workload and defines the performance of each algorithm for that workload.
Example - Consider 5 processes arriving at time 0, for Round Robin- QT=10.
Process / Burst TimeP1 / 10
P2 / 29
P3 / 3
P4 / 7
P5 / 12
Deterministic Evaluation
For each algorithm, calculate minimum average waiting time.
Simple and fast, but requires exact numbers for input, applies only to those inputs.
FCFS minimum average waiting time is 140/5 = 28ms.
Waiting time
P1=0
P2=10
P3=39
P4=42
p5=49
Non-preemptive SFJ minimum average waiting time is 65/5 =13ms.
Waiting time
P1=10
P2=32
P3=0
P4=3
p5=20
RR minimum average waiting time is 115/5= 23ms.
Waiting time
P1=0
P2=10+20+2 =32
P3=20
P4=23
p5=30+10=40
Example -
Consider the following set of processes, with the length of the CPU burst given in milliseconds.
Process / Burst Time / PriorityP1 / 10 / 3
P2 / 1 / 1
P3 / 2 / 3
P4 / 1 / 4
P5 / 5 / 2
The processes are assumed to have arrived in the order P1, P2, P3, P4, P5 all at time = 0.
a) Draw FOUR Gantt chart that illustrate the execution of these processes using the following scheduling algorithm :
· FCFS
· Shortest Job First (SJF)
· Non Preemptive Priority( a smaller priority number integer = Higher priority)
· Round Robin(RR) (Quantum = 1).
b) What is a turnaround time of each process for each scheduling algorithmin a part a ?.
c) What is the waiting time of each process for each scheduling algorithmin a part a ?.
d) Which of the scheduling algorithmin in part a results in the minimum average waiting time (over al processes)?.
Ans a)
FCFS
Process / Burst Time / Priority / CT / TAT / WTP1 / 10 / 3 / 10 / 10 / 0
P2 / 1 / 1 / 11 / 11 / 10
P3 / 2 / 3 / 13 / 13 / 11
P4 / 1 / 4 / 14 / 14 / 13
P5 / 5 / 2 / 19 / 19 / 14
19
TAT – all arrive at 0 so take total complete time direct.
TAT= CT – AT
WT= TAT – BT
FCFS - minimum Average Turnaround Time is 67/5 = 13.4ms.
FCFS - minimum Average Waiting Time is 48/5 = 9.6ms.
Shortest Job First (SJF)
Process / Burst Time / Priority / CT / TAT / WTP1 / 10 / 3 / 19 / 19 / 9
P2 / 1 / 1 / 0 / 1 / 0
P3 / 2 / 3 / 4 / 4 / 2
P4 / 1 / 4 / 2 / 2 / 1
P5 / 5 / 2 / 9 / 9 / 4
19
TAT – all arrive at 0 so take total complete time direct.
TAT= CT – AT
WT= TAT – BT
SJF - minimum Average Turnaround Time is 35/5 = 7ms.
SJF - minimum Average Waiting Time is 16/5 = 3.2ms.
Non Preemptive Priority( a smaller priority number integer = Higher priority)
Process / Burst Time / Priority / CT / TAT / WTP1 / 10 / 3 / 16 / 16 / 6
P2 / 1 / 1 (high) / 1 / 1 / 0
P3 / 2 / 3 / 18 / 18 / 16
P4 / 1 / 4(low) / 19 / 19 / 18
P5 / 5 / 2 / 6 / 6 / 1
19
TAT – all arrive at 0 so take total complete time direct.
TAT= CT – AT
WT= TAT – BT
Non Preemptive Priority - minimum Average Turnaround Time is 60/5 = 12ms.
Non Preemptive Priority - minimum Average Waiting Time is 41/5 = 8.2ms.
Round Robin(RR) (Quantum = 1)
Process / Burst Time / Priority / CT / TAT / WTP1 / 10 / 3 / 19 / 19 / 9
P2 / 1 / 1 / 2 / 2 / 1
P3 / 2 / 3 / 7 / 7 / 5
P4 / 1 / 4 / 4 / 4 / 3
P5 / 5 / 2 / 14 / 14 / 9
19
P1 / P2 / P3 / P4 / P5 / P1 / P3 / P5 / P1 / P5 / P1 / P5 / P1 / P5 / P1 / P1 / P1 / P1 / P10 / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10 / 11 / 12 / 13 / 14 / 15 / 16 / 17 / 18 / 19
TAT – all arrive at 0 so take total complete time direct.
TAT= CT – AT
WT= TAT – BT
Waiting time
P1=0 +(5-1) + (8-6) +(10-9)+(12-11)+(14-13)=0+4+2+1+1+1=9
P2=1
P3= 2+(6-3)=2+3=5
P4=3
P5=4+(7-5)+ (9-8)+ (11-10)+ (13-12)=4+2+1+1+1=9
Round Robin(RR) (Quantum = 1)- minimum Average Turnaround Time is 46/5 = 9.2ms.
Round Robin(RR) (Quantum = 1)- minimum Average Waiting Time is 27/5 = 5.4ms.
B ans)
Turnaround time
FCFS - minimum Average Turnaround Time is 67/5 = 13.4ms.
SJF - minimum Average Turnaround Time is 35/5 = 7ms.
Non Preemptive Priority - minimum Average Turnaround Time is 60/5 = 12ms.
Round Robin(RR) (Quantum = 1)- minimum Average Turnaround Time is 46/5 = 9.2ms.
Therefore - Turnaround time of SJF is Minimum. 7ms.
C ans)
Waiting time
FCFS - minimum Average Waiting Time is 48/5 = 9.6ms.
SJF - minimum Average Waiting Time is 16/5 = 3.2ms.
Non Preemptive Priority - minimum Average Waiting Time is 41/5 = 8.2ms.
Round Robin(RR) (Quantum = 1)- minimum Average Waiting Time is 27/5 = 5.4ms.
Therefore - Waiting time of SJF is Minimum = 3.2ms
D ans)
Waiting time of SJF is Minimum.
Therefore - SJF scheduling algorithmin in part a results in the minimum average waiting time.
Non Preemptive / PreemptiveFCFS / Round Robin
SJF / SRTF(SJF)
Priority / Priority
Context switch - a context switch is the process of storing and restoring the state (more specifically, the execution context) of a process or thread so that execution can be resumed from the same point at a later time.
Convoy effect- is slowing down of the wholeoperating systembecause of few slow processes.
CPU scheduling - is a process which allows one process to use the CPU while the execution of another process is on hold(in waiting state) due to unavailability of any resource like I/O etc, thereby making full use of CPU.
The aim of CPU scheduling is to make the system efficient, fast and fair.
Scheduling in operating system -
Scheduling is the method by which threads, processes or data flows are given access to system resources (e.g. processor time, communications bandwidth).
This is usually done to load balance and share system resources effectively or achieve a target quality of service.
Department of Computer Science, College of Art and Sciences, University of NIZWA