8.1 Scheduling

Question 1

Scheduling

Answer 1

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

Question 2

Aim of scheduling

Answer 2

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

Question 3

Objectives of Scheduling

Answer 3

Share time fairly among processes 
Prevent starvation of a process
Use the processor efficiently
Have low overhead
Prioritise processes when necessary

Question 4

Long term scheduling

Answer 4

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

Question 5

Medium term scheduling

Answer 5

Part of swapping function

Swapping in decisions are based on the need to manage the degree of multiprogramming

Question 6

Short term scheduling

Answer 6

Known as the dispatcher
Executes most frequently
Invoked when an event occurs
-Clock interrupts
-I/O interrupts
-OS calls
-Signals

Question 7

Aim of short term scheduling

Answer 7

To allocate processor time to optimise certain aspects of system behaviour.
A set of criteria is needed to evaluate the scheduling policy.

Question 8

Short term scheduling criteria USER V SYSTEM

Answer 8

User oriented
-Response time
–Elapsed time between request submission until there is an output
System Oriented
-Effective and efficient utilisation of the processor

Question 9

Short term scheduling criteria PERFORMANCE

Answer 9

Performance related
- Quantitive, easily measured
-EG Response time & throughput
Non performance related
-Qualitative
-Hard to measure

Question 10

FORMULAS

Answer 10

Turn around time = Finish Time - Arrival Time
Waiting Time = Start Time - Arrival Time
Throughput = Processes Number / Total Time

Question 11

Priorities

Answer 11

Scheduler will always choose a process of higher priority over one of lower priority
Have multiple ready queues to represent each level of priority

Question 12

Starvation

Answer 12

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

Question 13

Selection Function

Answer 13

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

Question 14

Decision Mode

Answer 14

Specifies the instants in time at which the selection function is exercised
Two categories
-Non-Preemptive
-Preemptive

Question 15

Nonpreemptive vs Preemptive

Answer 15

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

Question 16

First come first served FCFS

Answer 16

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

Question 17

Round Robin RR

Answer 17

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

Question 18

Shortest Process Next SPS

Answer 18

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

Question 19

Shortest Remaining Time SRT

Answer 19

Preemptive version of shortest process next policy

Must estimate processing time and choose the shortest

Question 20

Highest response ratio next HRRN

Answer 20

Choose next process with the greatest ratio

Ratio = time spent waiting + expected service time / expected service time

Question 21

Scheduling Algorithms 1

Answer 21

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

Question 22

Scheduling Algorithms 2

Answer 22

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

Question 23

FCFS

Answer 23

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

Question 24

SJF Shortest Job First

Answer 24

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

Question 25

Round Robin 1 RR

Answer 25

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