Module 3 - CPU scheduling

Question 1

What is the overall purpose of the the short-term scheduler (aka CPU scheduler)?

Answer 1

The Short-term scheduler (STS), aka CPU scheduler, selects which process in the in memory ready queue that should be executed next and allocates CPU.

Question 2

What is the overall purpose of the long-term scheduler?

Answer 2

The Long-term scheduler (LTS) (aka job
scheduler) decides whether a new process should be brought into the ready queue in main memory or delayed.

When a process is ready to execute, it is added to the job pool (on disk).

When RAM is sufficiently free, some processes are brought from the job pool to the ready queue (in RAM).

Question 3

What is the overall purpose of the medium-term
scheduler?

Answer 3

The medium-term scheduler (MTS) temporarily removes processes from
main memory and places them in secondary storage and vice versa,
which is commonly referred to as “swapping in” and “swapping out”.

Question 4

Define the following scheduling criteria: CPU utilization, throughput, turnaround time, waiting time and response time.

For each metric, state whether the goal is to minimize or maximize the metric.

Answer 4

CPU utilization - The % of time the CPU is executing user level process code.
Goal = Maximize.

Throughput - Number of processes that complete their execution per time unit.
Goal = Maximize.

Turnaroud time - Amount of time to execute a particular process.
Goal = Minimize.

Waiting time - Amount of time a process has been waiting in the ready queue.
Goal = Minimize.

Response time - Amount of time it takes from when a request was submitted until the first response is produced.
Goal = Minimize.

Question 5

What is meant by CPU burst? What is meant by I/O burst?

Answer 5

CPU burst - When the process is being executed in the CPU.

I/O burst - When the CPU is waiting for I/O for further execution.

Question 6

What characterizes a CPU bound process? What characterizes an I/O bound process?

Answer 6

CPU bound process - A CPU-bound process spends more time doing computations and
is characterised by few very long CPU bursts.

I/O bound process - An I/O-bound process spends more time doing I/O than computations and is characterised by many short CPU bursts.

Question 7

What would happen if there was a large majority of CPU bound processes in the ready queue?

Answer 7

If all processes are CPU bound, the I/O waiting queue will almost always be empty, devices will go unused, and the system will be unbalanced.

Question 8

What would happen if there was a large majority of I/O bound processes in the ready queue?

Answer 8

The ready queue will almost always be empty and the short-term scheduler will have little to do.

Question 9

How can a good balance between CPU bound processes and I/O bound processes in the ready queue be maintained?

Answer 9

In theory, the medium-term scheduler (MTS) can be used to maintain a good balance between I/O bound and CPU bound processes in the ready queue.

Question 10

What characterizes an interactive process?

Answer 10

Interactive processes interact constantly with their human users.

Spend a lot of time waiting for keypresses
and mouse operations.

When input is received, the process must be woken up quickly, or the user will find the system to be unresponsive.

Typically, the average delay must fall
between 50 and 150 ms. The variance of
such delay must also be bounded, or the user will find the system to be erratic.

Typical examples:
Command shells and interpreters, text
editors, graphical applications and games.

Question 11

What requirements on CPU scheduling does interactive processes impose?

Answer 11

– Maximize CPU utilization & throughput.
– Let another process run when the current one is waiting on I/O.

Question 12

What characterizes a batch process?

Answer 12

Batch processes do not interact with
human users.

‣ Do not need to be responsive.
‣ Often run in the background.
‣ Often penalised by the scheduler.

Typical examples:
‣ Compilers, database search
engines, and scientific computations.

Question 13

What is meant by scheduler dispatch?

Answer 13

Its the module that gives control of the CPU to the process selected by the short-term scheduler.

Question 14

What actions are taken during a scheduler dispatch?

Answer 14

The CPU scheduler selects one process from among the processes in memory that are READY to execute.

The scheduler dispatcher then gives the selected process control of the CPU. This action is called scheduler dispatch (SD).

Question 15

Define dispatch latency.

Answer 15

It is the time taken by the dispatcher in context switching of a process from run state and putting another process in the run state.

Or in simpler terms, it is the time takes for the dispatcher to stop one process and start another running.

Question 16

Scheduler dispatch can be preemptive and nonpreemptive, define these terms.

Answer 16

A preemptive dispatch is caused by an event external to the running running process.

A nonpreemptive dispatch is caused by the running process itself.

Question 17

Draw a diagram showing which process state transitions causes a preemptive respectively a nonpreemptive scheduler dispatch.

Answer 17

Draw it.

Question 18

Explain the FCFS scheduling algorithm.

Answer 18

The first come, first served (commonly called FIFO ‒ first in, first out) process scheduling algorithm is the simplest
process scheduling algorithm. Processes are executed on the CPU in the same order they arrive to the ready queue.

Question 19

Explain the convoy effect.

Answer 19

When using FCFS scheduling, if I/O bound (short CPU burst) processes are scheduled after CPU bound (long CPU burst) processes, the average waiting time increases.

Question 20

Explain the SJF scheduling algorithm.

Answer 20

Shortest Job First (SJF) scheduling assigns the process estimated to complete fastest, i.e, the process with shortest (estimated) CPU burst, to the CPU as soon as CPU time is available.

Question 21

In what way is SJF optimal?

Answer 21

It gives minimum average waiting time for
a given set of processes.

Question 22

Explain the PSJF scheduling algorithm.

Answer 22

An extension of SJF where the currently running process is preempted if the CPU burst of a process arriving to the ready
queue is shorter than the remaining CPU burst of the currently running process.

Question 23

Explain the RR scheduling algorithm.

Answer 23

Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.

If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once.

Question 24

In general, what can be said about turnaround time and response time when comparing RR and SJF?

Answer 24

Round Robin typically have higher average turnaround times than SJF, but better average response time.

Question 25

In CPU scheduling, what is meant by starvation and ageing?

Answer 25

Starvation – low priority processes may never execute.

Ageing – ensure that jobs with lower priority will eventually complete their execution. Ageing can be implemented by increasing the priority of a process as time progresses.

Question 26

What is the overall purpose of multilevel queue scheduling?

Answer 26

A multi-level queue scheduling algorithm is used in scenarios where the processes can be classified into groups based on properties like process type, CPU time, IO access, memory size, etc

Question 27

In a ready queue for foreground processes, which algorithm of FCFS, SJF and RR would you choose.

Justify your answer.

Answer 27

Foreground processes tend to be I/O bound, which in turn means that the best algo would be SJF.

Because we usually want minimal average waiting time when dealing with processes that are I/O bound.

Question 28

What are the design objective of multilevel feedback queue scheduling?

Answer 28

‣ Give preference to short CPU bursts.
‣ Give preference to I/O bound processes.
‣ Dynamically separate processes into
categories based on their need for the CPU.

Question 29

Explain how multilevel feedback queue scheduling works and how this relates to the design objectives.

Answer 29

1) A new job enters queue Q0 which is served FCFS. Each job gets at most 8
milliseconds of CPU time.

2) If it does not finish in 8 milliseconds, the job is moved to queue Q1.

3) If it still does not complete, it is preempted and moved to queue Q2.

4) At Q1 the job is again served FCFS and receives 16 additional milliseconds.

5) Once in Q2, processes are scheduled using FCFS but are run only when Q0 and
Q1 are empty.

Question 30

Explain how the Solaris dispatch table is used to dynamically change the priority and time quantum (time slice) for a process.

Question 31

Explain how a bitmap makes it possible for the Linux O(1) scheduler to find the highest priority process in constant time, independent of the the number of active tasks.

Question 32

The Linux Completely Fair Scheduler uses a red-black tree to keep track the processes in the ready queue. What is the time complexity of selecting the next process to run? What is the time complexity of inserting process (task) into the red-black-tree?

Question 33

Question 33 is in the module-3.pdf

Question 34

Question 34 is in the module-3.pdf