Operating System Scheduling
 

Hey Guys,

I'm working on figuring out process waiting time for 4 different operating system scheduling time.

The 4 different types are First Come, First Served, Shortest Job First, Non-preemptive and Round Robin.

I have 5 different Process

P1 takes 10 brust and are priority 3
P2 takes 1 burst and are priority 1
P3 takes 2 burst and are priority 3
P4 takes 1 burst and are priority 4
P5 takes 5 burst and are priority 2

FCFS
----------10-11--13-14-----19

Average wait time = (10+11+13+14)/5 = 9.6 millisecond

SJF
-1-2--4-----9----------19

Average wait time = (1+2+4+9)/5 = 3.2 millisecond

Nonpreemptive
-1-----6--8----------18-19

Average wait time = (1+6+8+18)/5 = 6.8 millisecond

RoundRobin Quantum = 1
-1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19

I believe I've got the first 3 right. But Round Robin is somewhat more difficult to understand. I understand that each process are allocated to 1 time quantum of CPU. But what I can't understand is how to calculate the average waiting time. It's not the same as calculating the average wait time as the other 3 since once process #2 and 4 are completed, they're not part of the average waiting time formula anymore.

Assuming each process starts at the exact same time then your average waiting time is going to be

(0+1+2+3+4)/5 or 2
process 1 starts immedatily wait time is 0
process 2 starts at quantum 1, wait time is 1
process 3 starts at quantum 2, wait time is 2.
.
.
.
etc


I think that's how it worked anyway.. Been a while since I took that class.

the average wait time will be the sum of each processes time on the ready queue divided by the total number of processes.

That is the process has information it wants to process but is waiting for another process on the run queue.

So if you have 5 processes that want to run then every time quantum you will gain 4 quantoms of wait time (then in the end divide by the number of processes).

Fascinating.. I just took an Operating Systems midterm today with that EXACT same problem on. Same burst times for each process and everything. Where did you get this problem from??

As for your question, I think that you need do this:
Everytime a process is not running, it is waiting. So you need to calculate the wait time for each process individually. It'll look something like this

So for each process you need to add all the slices where its not running, this will be the total wait time for each process. For the end slices, where only P1 is running, it will not be waiting. Then sum each process' wait time and divide by 5.

It's probably from the book "Operating System Concepts" by silberschatz galvin and gagne. This book seems to be used universally in all OS classes.

Now that you mention it, that IS the book we're using. I guess I'm just surprised my prof used a textbook problem on the midterm without modifying it at all.