Scheduling
Labs Sched_EG EXER Exer_Soln


Preparatory Lab Shell Scripting Vagrant and Sense HAT Assessment-Guides Linux Practice Exercises Home Network Scripting Exercises Vagrant and Virtualisation cpu Packet Sniffing using TShark NoBases IP Networking Boolean The Headless RPi Logic Presence Detector 1 BLE TCP-Sockets Lab Messaging Lab Labs Wia Lab Labs Labs Blynk

Operating Systems

Scheduling Examples

  • The first lab here goes through examples of some of the Scheduling techniques that are used in modern operating systems to complement the notes.

  • The next lab asks some questions for you to consider, having gone through and understood the purposes of and algorithms of the techniques in the notes.

  • There are some solutions to these problems in the following lab

Exercises

Exercises demonstrating different scheduling Techniques

FCFS Scheduling

  • Suppose that 3 processes arrive in the order: P1, P2, P3 and they have the following CPU burst times:

Using FCFS, the Gantt Chart for the schedule is:

  • Waiting Time for P1=0; P2=24; P3=27
  • Average waiting time = (0 + 24 + 27) / 3 = 17

  • Average turn-around time = (24+27+30)/3=27

  • Suppose the processes had arrived in the order P2, P3, P1. Then we would have the Gantt chart with FCFS:

  • Waiting Time for P1=6; P2=0; P3=3
  • Average waiting time = (6 + 0 + 3) / 3 = 3

  • Average turn-around time = (3+6+30)/3=13

  • The average waiting time is much less than in the first case, which demonstrates a classic convoy effect where all the other processes are waiting for one long process to finish using the CPU.

  • This results in lower CPU and device utilisation

  • Example #2 shows that higher utilisation might be possible if the shortest processes were allowed to run first.

SJN Scheduling

  • Suppose that 4 processes arrive as follows:

Using SJN, we would have the following Gantt chart:

  • Average waiting time = (0 + 3 + 6 + 7) / 4 = 4

SRT Scheduling

  • Suppose that 4 processes arrive as follows (same as SJN example):

Using SRT, we would have the following Gantt chart:

Average waiting time = (9 + 1 + 0 +2)/4 = 3

  • Note that this average wait time is better than with SJN.

Priority Scheduling

Round Robin Scheduling

Suppose that 4 processes arrive at time 0, with the following CPU burst times:

Using RR with a time quantum of 20, we would have the following Gantt chart:

  • Average waiting time = (81 + 20 + 94 + 97)/4 = 73

Typically there will be higher average turnaround time than SJN but better response time.

Multilevel Feedback Queue Scheduling

Let’s consider there are three queues Q1, Q2 and Q3.

Q1 Time quantum 9ms    
Q2 Time quantum 18ms        
Q3 FCFS

  • Any process entering the ready queue is put in Q1.
  • Then, a process in Q1 is given a time quantum of 9 milliseconds.
  • If it does not finish within time, it is moved to the tail of Q2.
  • If Q1 is empty, the process at the head of Q2 is given a quantum of 18 milliseconds.
  • If it does not complete, it is preempted and is put into Q3.

  • Processes in Q3 are run on an FCFS basis, only when Q1 and Q2 are empty.

  • A technique called Aging promotes lower priority process to the next higher priority queue after a suitable interval of time.

Scheduling Exercises

Which Scheduling Algorithm is best for the situations below?

Situation 1

The incoming processes are short and there is no need for the processes to execute in a specific order.

Situation 2

The processes are a mix of long and short processes and the task will only be completed if all the processes are executed successfully in a given time.

Situation 3

The processes are a mix of user based and kernel based processes.

Exercises

Which Scheduling Algorithm is best for the situations below?

Situation 1

The incoming processes are short and there is no need for the processes to execute in a specific order.

In this case, FCFS works best when compared to SJF and RR because the processes are short which means that no process will wait for a longer time. When each process is executed one by one, every process will be executed eventually.

Situation 2

The processes are a mix of long and short processes and the task will only be completed if all the processes are executed successfully in a given time.

Round Robin scheduling works efficiently here because it does not cause starvation and also gives equal time quantum for each process.

Situation 3

The processes are a mix of user based and kernel based processes.

Priority based scheduling works efficiently in this case because generally kernel based processes have higher priority when compared to user based processes.

For example, the scheduler itself is a kernel based process, it should run first so that it can schedule other processes


Powered by tutors-ts. Unless otherwise stated, this work is licensed under a Creative Commons Attribution 4.0 International License.