PART 4 - SCHEDULING

Question 1

What are the two process behavior?

Compute bound & I/O bound

Answer 1

Almost all processes alternate bursts of computation with I/O requests and fall into two categories.

_ : time spend computing.
–:waiting for I/O.

1) Compute bound - most time spend computing

–______—______________—-___________——______

2) I/O bound - most time spend waiting for I/O

__——————-———–__———–__—————–_—–__–

You should prioritise I/O bound process, as they need less processor time.

The impact of a faster CPU is that more processes are I/O bound as the computational process will take less time.

Question 2

When to make scheduling decision?

Answer 2

It is REQUIRED to make scheduling decisions:

• When a process exits
• When a process blocks on I/O (or waiting for a resource)

and, normally:
- When a new process is created
- When an I/O interrupt occurs
- When a clock interrupt occurs
.decide if current process has run for long enough
.non-preemptive scheduling - pick process and let it run
until it blocks or voluntarily gives up processor
.preemptive scheduling - pick process and let it run for a
maximum time interval (specific time)

Question 3

What are the scheduling algorithm goals for different kinds of systems?
Hint: (All Systems, Batch Systems, Interactive Systems, Real-Time Systems)

Answer 3

All Systems
• Fairness
• Policy enforcement
– give priority to critical processes
• Balance – keep all parts of system busy

Batch Systems
• Maximise throughput (jobs/s)
• Minimise turnaround (average wait for output)
• Maximise utilisation – less important

Interactive Systems
• Optimise response time – favour foreground tasks
• Proportionality – attempt to meet user expectations of how long tasks should take

Real-time Systems
• Meet deadlines – avoid loosing time-critical data
• Predictability – avoid quality degradation (e.g. in RT video)

Question 4

Give one advantage and one disadvantage of First-come First served scheduling algorithm

Answer 4

Advantage:
1) Very simple and easy to program

Disadvantage:
1) Compute bound processes dominate - long jobs dominate turnaround time

Question 5

What is priority scheduling?

Answer 5

The basic idea of PRIORITY SCHEDULING is to give the CPU to the runnable process with the highest priority.
- Preempt current process if a higher priority process is
ready.

Problems:

• High-priority processes could run indefinitely
• If you do not prioritise I/O bound processes, they will idly consume memory waiting for both I/O and CPU

Question 6

What is Minix Scheduling & How is a priority level reduced?

Answer 6

• Scheduling is essentially Round Robin within each queue
– When a process uses its quantum, it is moved to the tail of its queue and given a new quantum
• Drivers and servers have longer quantums than users
• If process blocks, when it is ready again it is put to head
of its queue with a quantum equal to the remainder of its
quantum when it was blocked (adjustment to RR to allow
I/O bound processes to run again)

• Scheduling is simple
– Pick the process at the head of the highest priority queue – If all higher priority queues are empty, run IDLE process

• Priority level is reduced if process runs for two consecutive quanta or runs for too long without being preempted
– Prevents high priority processes from locking up the system

• A demoted process can earn its way back to higher priority queue
– If it has used all its quantum and is not preventing other processes from running