week 8 scheduling Flashcards
to learn
what is scheduling problem
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
how is scheduling done?
Typically done by having queues of processes waiting for a
specific resource and selecting a process in the queue
what are the type of scheduling queues:
Job queue
Ready queue
Device queues
what is a job queue is scheduling:
- set of all processes in the system
what is a ready queue is scheduling:
- set of all processes residing in main memory,
ready and waiting to execute
what is a device queue in scheduling:
- set of processes waiting for an I/O device
Processes migrate among the various queues
can processes move to different queues
yes! Processes migrate among the various queues
what is a problem with cpu scheduling
Which process ready to execute commands gets the
CPU?
key function of a programming system.
Prerequisites for successful scheduling: (2 things)
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
what is the scheduling criteria:
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
what is throughput
Number of processes completed within a given
time
what is turnaround time
Time it takes for each process to be
executed
what is waiting time
Amount of time spent in the ready-queue
what is response time
time between submission of request and production of first response
what are the two categories in processes
I/O-bound process
CPU-bound process
I/O bound process
- spends more time doing I/O than computations, many short CPU bursts
cpu bound process
spends more time doing computations;
few very long CPU bursts
describe first come first serve algorithm (FCFS)
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
benefit of fcfs
easy to implement
what is round robin
FCFS with preemption
standard method in time sharing systems
what is a problem with round robin
Problem: get the time quantum (time before preemption) right.
- too short: too many context switches
- too long: Process can monopolise CPU
what happens if time before preemption in round robin is too short:
too short: too many context switches
what happens if time before preemption in round robin is too long:
- too long: Process can monopolise CPU
describe shortest job first
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
what is the shortest cpu burst time
(shortest CPU-time
before next I/O-operation)
what is a positive of shortest job first
algorithm with the smallest average
waiting time
disadvantage of shortest job first
priority scheduling assumption
A priority is associated with each process
CPU is allocated to process with highest priority
Equal-priority processes scheduled according to FCFS
how are Equal-priority processes scheduled
according to FCFS
what are the two variations of priority scheduling
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
what is priority scheduling with preemption
newly-arrived process with higher priority
may gain processor immediately if process with lower priority
is running
what is priority scheduling without preemption
newly arrived process always waits
why is preemption good in priority scheduling
Preemption good for ensuring quick response time for high-priority
processes
disadvantage of priority scheduling
Starvation of low-priority processes possible
Solution: Increase priority of processes after a while (Ageing)
Solution to Starvation of low-priority processes possible
Increase priority of processes after a while (Ageing)
describe Multilevel Queue Scheduling
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
what are the possible set ups of queues in describe Multilevel Queue Scheduling
System processes
Interactive processes
Interactive editing processes
Batch processes
what is another way of processing cpu queues
according to length of CPU-burst
Scheduling for Multiprocessor Systems
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
what are the two types of process affinity
Process affinity for CPU on which it is currently running
Soft Affinity:
Hard Affinity:
soft affinity in process affinity
current CPU only preferred when re-scheduled
hard affinity in process affinity
Process may be bound to specific CPU
Advantage: caches remain valid, avoiding time-consuming
cache invalidation and recovery
advantage of hard affinity in process affinity
Advantage: caches remain valid, avoiding time-consuming
cache invalidation and recovery
Linux Implementation for scheduling
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)
default scheduler in linux
Round-robin scheduler with priorities
real time scheduler in linux
Real-time scheduler (process needs to be assigned explicitly to
this one) (typically FIFO)
how is round robin with priorities implemented
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
