Scheduling: round robin, first come first served, multi-level feedback queues, shortest job first and shortest remaining time

Question 1

Explain the purpose of scheduling

Answer 1

• Makes the most efficient use of the processor/resources
• Be fair to all users/applicants
• Provide a reasonable response time
• Prevent processes from failing to run/process starvation/deadlock

Question 2

What is meant by a pre-emptive scheduling algorithm?

Answer 2

Jobs are actively made to start and stop by the
operating system
- Multilevel Feedback Queues, Shortest Remaining Time, Round Robin

Question 3

What is meant by a non pre-emptive scheduling algorithm?

Answer 3

Once a job is started, it is left alone until it is completed
- First Come First Served, Shortest Job First

Question 4

State 5 different scheduling algorithms

Answer 4

• Round robin
• First come first served
• Shortest job first
• Shortest remaining time
• Multilevel feedback queues

Question 5

What is round robin?

Answer 5

• Each job is given a section of processor time - known as a time slice (allowed to execute)
• Once each job in the queue has used its first time slice, the operating system again grants each job an equal slice of processor time
• This continues until a job has been completed, at which point it is removed from the queue

Question 6

Advantages of round robin?

Answer 6

• Every process gets an equal share of the CPU

- RR is cyclic in nature, so there is no starvation

Question 7

Disadvantages of round robin?

Answer 7

• Longer jobs will take a much longer time for completion due to their
  execution being inefficiently split up into multiple cycles
• Does not take into account job priority

Question 8

What is first come first served?

Answer 8

Jobs are processed in chronological order by which they entered the queue

Question 9

Advantages of first come first served?

Answer 9

• Simple and easy to understand

- Straightforward to implement

Question 10

Disadvantages of first come first served?

Answer 10

• FCFS again does not allocate processor time based on priority
• The process with less execution time suffer i.e. waiting time is often quite long

Question 11

What is multilevel feedback queues?

Answer 11

This makes use of multiple queues, each which is ordered based on a different priority

Question 12

Advantages of multilevel feedback queues?

Answer 12

• It is more flexible
• It prevents starvation by moving a process that waits too long from the lower priority queue to the higher priority queue

Question 13

Disadvantages of multilevel feedback queues?

Answer 13

• Difficult to implement due to deciding which job to prioritise based on a combination of priorities
• Most complex algorithm

Question 14

What is shortest job first?

Answer 14

The queue storing jobs to be processed is ordered according to the time
required for completion, with the longest jobs being serviced at the end

Question 15

Advantages of shortest job first?

Answer 15

• It is suitable for the jobs running in batches, where run times are already known
• SJF is better than the First come first serve (FCFS) algorithm as it reduces the average waiting time

Question 16

Disadvantages of shortest job first?

Answer 16

• SJF may cause starvation if shorter processes keep coming, this problem is solved by ageing
• Requires the processor to know or calculate how long each job will take and this is not always possible

Question 17

What is shortest remaining time?

Answer 17

The queue storing jobs to be processed is ordered according to the time left for
completion, with the jobs with the least time till completion being serviced first

Question 18

Advantages of shortest remaining time?

Answer 18

• This scheduling is optimal in that it always produces the lowest mean response time.
• Processes with short CPU bursts are given priority and hence run quickly (are scheduled frequently)

Question 19

Disadvantages of shortest remaining time?

Answer 19

• Long-burst (CPU-intensive) processes are hurt with a long mean waiting time (long-burst ones may never get scheduled), starvation
• Effectiveness of meeting the scheduling criteria relies on the accuracy to estimate the length of the next CPU burst