Scheduling

Question 1

Why is scheduling relevant to the OS?

Answer 1

Kernel decides which process gets to run

Question 2

What is the job of the scheduler?

Answer 2

Maximise utilisation of the CPU by swapping processes when it stops doing useful work

Question 3

Why bother?

Answer 3

By interleaving execution when the process is idle, we can maximise CPU utilisation and reduce the time taken for jobs to finish.

Question 4

What is a CPU scheduler?

Answer 4

CPU becomes idle, choose process to execute from the ready queue

Question 5

What states can process be in?

Answer 5

Ready
Running
Blocked
Terminated

Question 6

What is nonpreemptive scheduling?

Answer 6

Processes give up the CPU voluntarily (Co-operative)

Question 7

What is preemptive scheduling?

Answer 7

Allows scheduling at any point

Question 8

Why is concurrency control needed when scheduling?

Answer 8

Accessed shared application state may be left inconsistent. Requires coordination of access to shared state

Question 9

When are processes preempted?

Answer 9

Only on IO block/after completion of system call as OS or Driver data structures may be left partially updated.

Question 10

How is scheduling evaluated?

Answer 10

CPU Utilisation

Throughput

Turnaround time

Waiting time

Response time

Question 11

Describe what is meant by CPU Utilisation.

Answer 11

Percentage of time for which CPU is busy.

Question 12

Describe what is meant by Throughput.

Answer 12

Number of processes completed in a given time.

Question 13

Describe what is meant by Turnaround time.

Answer 13

Time from submission of process to its completion

Question 14

Describe what is meant by Waiting time.

Answer 14

Total time in the ready queue

Question 15

Describe what is meant by Response time

Answer 15

Time from submission of process to time of first response.

Question 16

What does the dispatcher do?

Answer 16

Switches from one task to another.

Performs needed tasks:

• switch context
• switch to user mode
• jump to proper location

Question 17

What is FCFS?

Answer 17

First Come First Served.

FIFO ready queue. Ready processes added to the end of the queue., process at head allocated to CPU when available

Question 18

What determines the average wait time of a FCFS queue?

Answer 18

Arrival order.

Question 19

When is FCFS not good?

Answer 19

When there is overlap in execution of IO devices and CPU.

Question 20

What does the SJF algorithm do?

Answer 20

Assign CPU to process with shortest next burst (impossible to implement as can’t predict the future).

Make best approximation as to how long burst will be.

Question 21

How does priority scheduling work?

Answer 21

Assign a priority to each process, CPU is allocated to process with highest priority.

Potential problem of starvation of low priority processes, introduce ageing scheme

Question 22

How is the priority of a process determined?

Answer 22

Internal measures; Memory requirements, CPU/IO burst ratio, System vs. user process

External measures; User-set priority, which use is running it

Question 23

How is Round Robin scheduling implemented?

Answer 23

Set a time, quantum, as the maximum burst time. Use the FIFO queue and allow to run for the quantum

Question 24

What are multi-level queues?

Answer 24

Used when processes can be easily classified into groups.

Partition the ready queue into several separate queues and reassign processes into these queues.

Question 25

What is a multi-level feedback queue?

Answer 25

Extension of ML queue, allows processes to move between queues. Queues are separated according to CPU burst characteristics.

Question 26

What is the algorithm of a feedback queue?

Answer 26

High priority processes in top queue.

If process exceed its quantum, move to a lower queue.

CPU bound processes sink, IO-bound have priority.

If processes waits for a long time, move to a higher queue