UNISA Chatter – Operating System Concepts: Part 14 ... Scheduling Algorithm Analysis Revisited

  • Article

See UNISA – Summary of 2010 Posts for a list of related UNISA posts.

This is one of the final exam preparation posts and looks at some of the common scheduling algorithms and reviews the associated assignment from this year as an example. If you are not studying at UNISA, you should probably skip this post Smile

In the assignments we got a pseudo algorithm and were asked to investigate based on different settings. How do we unravel the hidden mysteries of such an algorithm … let’s have a peek.

Pseudo Algorithm

Do While (jobs in ready queue) // number of jobs in ready queue is n
     Start the job with the NUMERICALLY HIGHEST priority
     If end of quantum or request for I/O then
           Suspend the currently running job
           Add A to the priority of each waiting job
           Add B to the priority of the job that has just been running
     End_If
     Accept any new jobs into the ready queue with priority 0
End_Do

Analysis

Personally I found that firing up Excel and calculating the priorities based on a number of different values for A, B and n works best for me … if only we had Excel in the exam Disappointed smile

First, take a highlighter and make the key information visible:

  • A is added to waiting jobs
  • B is added to running job
  • n is the number of ready jobs
  • Priority with highest numerical value is highest and is processed first

… so let’s look at some hypothetical test settings we were given for the assignment. Note that I am not interested in the test case where n=0, as there would be no scheduling required.

What happens if 0 < B < A?

Assumed starting values: A=2, B=1

Using the starting values for A and B, we notice that the running process is incremented with a value less that the waiting processes. The result, as shown with the cells highlighted in red and with an asterix (*) behind the running process, we have a Round-Robin (RR) type behaviour.

What happens if A = 1 and B = (1-n)

As with the previous example, the running process is incremented with a value that is less than that of waiting processes, again resulting in a Round-Robin (RR) type behaviour.

What happens if A = (1-n) and B = A/(1+n)

We finally have a bit of a variation Smile 

  • When we have one waiting process (n=1), both the values for A and B are zero and we end up with a First-Come-First-Serve (FCFS) if priorities matter or a Round-Robin (RR) as shown if priorities do not vary.
  • When we have two waiting processes (n=2), we are met by a processor hogging algorithm. Unless new processes are queued, the currently running process will run until complete, as its priority is decremented less than that of waiting processes.

Hope this helps …