week 8 scheduling

Question 1

what is scheduling problem

Answer 1

Have processes competing for resources (eg CPU, disk other
devices)
Important OS function: define a schedule to manage access of
processes to these resources
Typically done by having queues of processes waiting for a
specific resource and selecting a process in the queue

Question 2

how is scheduling done?

Answer 2

Typically done by having queues of processes waiting for a
specific resource and selecting a process in the queue

Question 3

what are the type of scheduling queues:

Answer 3

Job queue
Ready queue
Device queues

Question 4

what is a job queue is scheduling:

Answer 4

• set of all processes in the system

Question 5

what is a ready queue is scheduling:

Answer 5

• set of all processes residing in main memory,
  ready and waiting to execute

Question 6

what is a device queue in scheduling:

Answer 6

• set of processes waiting for an I/O device
  Processes migrate among the various queues

Question 7

can processes move to different queues

Answer 7

yes! Processes migrate among the various queues

Question 8

what is a problem with cpu scheduling

Answer 8

Which process ready to execute commands gets the
CPU?
key function of a programming system.

Question 9

Prerequisites for successful scheduling: (2 things)

Answer 9

1.) CPU-I/O-Burst Cycle
Experience shows: I/O occurs after fixed amount of time in ≥ 90%
⇒ appropriate time for re-scheduling

2.) Preemptive Scheduling: Processes can be forced to relinquish
processor

Question 10

what is the scheduling criteria:

Answer 10

CPU utilisation
Throughput: Number of processes completed within a given
time
Turnaround time: Time it takes for each process to be
executed
Waiting time: Amount of time spent in the ready-queue
Response time: time between submission of request and
production of first response

Question 11

what is throughput

Answer 11

Number of processes completed within a given
time

Question 12

what is turnaround time

Answer 12

Time it takes for each process to be
executed

Question 13

what is waiting time

Answer 13

Amount of time spent in the ready-queue

Question 14

what is response time

Answer 14

time between submission of request and production of first response

Question 15

what are the two categories in processes

Answer 15

I/O-bound process
CPU-bound process

Question 16

I/O bound process

Answer 16

• spends more time doing I/O than computations, many short CPU bursts

Question 17

cpu bound process

Answer 17

spends more time doing computations;
few very long CPU bursts

Question 18

describe first come first serve algorithm (FCFS)

Answer 18

Jobs are put in a queue, and served according to arrival time
Easy to implement but CPU-intensive processes can cause long
waiting time.
FCFS with preemption is called Round-Robin
standard method in time sharing systems
Problem: get the time quantum (time before preemption) right.
- too short: too many context switches
- too long: Process can monopolise CPU

Question 19

benefit of fcfs

Answer 19

easy to implement

Question 20

what is round robin

Answer 20

FCFS with preemption
standard method in time sharing systems

Question 21

what is a problem with round robin

Answer 21

Problem: get the time quantum (time before preemption) right.
- too short: too many context switches
- too long: Process can monopolise CPU

Question 22

what happens if time before preemption in round robin is too short:

Answer 22

too short: too many context switches

Question 23

what happens if time before preemption in round robin is too long:

Answer 23

• too long: Process can monopolise CPU

Question 24

describe shortest job first

Answer 24

Next job is one with shortest CPU-burst time (shortest CPU-time
before next I/O-operation)
Not implementable, but this is algorithm with the smallest average
waiting time
⇒ Strategy against which to measure other ones
Approximation: Can we predict the burst-time?
Only hope is extrapolation from previous behaviour
done by weighting recent times more than older ones.
τn+1 = αtn + (1 − α)τn

Question 25

what is the shortest cpu burst time

Answer 25

(shortest CPU-time before next I/O-operation)

Question 26

what is a positive of shortest job first

Answer 26

algorithm with the smallest average waiting time

Question 27

disadvantage of shortest job first

Question 28

priority scheduling assumption

Answer 28

A priority is associated with each process CPU is allocated to process with highest priority Equal-priority processes scheduled according to FCFS

Question 29

how are Equal-priority processes scheduled

Answer 29

according to FCFS

Question 30

what are the two variations of priority scheduling

Answer 30

With preemption: newly-arrived process with higher priority may gain processor immediately if process with lower priority is running Without preemption: newly arrived process always waits

Question 31

what is priority scheduling with preemption

Answer 31

newly-arrived process with higher priority may gain processor immediately if process with lower priority is running

Question 32

what is priority scheduling without preemption

Answer 32

newly arrived process always waits

Question 33

why is preemption good in priority scheduling

Answer 33

Preemption good for ensuring quick response time for high-priority processes

Question 34

disadvantage of priority scheduling

Answer 34

Starvation of low-priority processes possible Solution: Increase priority of processes after a while (Ageing)

Question 35

Solution to Starvation of low-priority processes possible

Answer 35

Increase priority of processes after a while (Ageing)

Question 36

describe Multilevel Queue Scheduling

Answer 36

Applicable when processes can be partitioned into groups (eg interactive and batch processes): Split ready-queue into several separate queues, with separate scheduling algorithm Scheduling between queues usually implemented as pre-emptive priority scheduling

Question 37

what are the possible set ups of queues in describe Multilevel Queue Scheduling

Answer 37

System processes Interactive processes Interactive editing processes Batch processes

Question 38

what is another way of processing cpu queues

Answer 38

according to length of CPU-burst

Question 39

Scheduling for Multiprocessor Systems

Answer 39

CPU scheduling more complex when multiple CPU’s are available Most common case: Symmetric multiprocessing (SMP): all processors are identical, can be scheduled independently have separate ready-queue for each processor (Linux), or shared ready-queue

Question 40

what are the two types of process affinity

Answer 40

Process affinity for CPU on which it is currently running Soft Affinity: Hard Affinity:

Question 41

soft affinity in process affinity

Answer 41

current CPU only preferred when re-scheduled

Question 42

hard affinity in process affinity

Answer 42

Process may be bound to specific CPU Advantage: caches remain valid, avoiding time-consuming cache invalidation and recovery

Question 43

advantage of hard affinity in process affinity

Answer 43

Advantage: caches remain valid, avoiding time-consuming cache invalidation and recovery

Question 44

Linux Implementation for scheduling

Answer 44

Several schedulers may co-exist, assign fixed percentage of CPU-time to each scheduler Important schedulers: Round-robin scheduler with priorities (the default scheduler) Real-time scheduler (process needs to be assigned explicitly to this one) (typically FIFO)

Question 45

default scheduler in linux

Answer 45

Round-robin scheduler with priorities

Question 46

real time scheduler in linux

Answer 46

Real-time scheduler (process needs to be assigned explicitly to this one) (typically FIFO)

Question 47

how is round robin with priorities implemented

Answer 47

maintain tree of processed ordered by runtime allocated so far pick next process as one with least runtime allocated so far insert new process in ready queue at appropriate place in tree Priorities handled by giving weights to run-times