With the following samples compute the average waiting time

With the following samples, compute the average waiting time and the average turnaround time for

• FCFS scheduling

• Preemptive SJF scheduling

• Non-preemptive priority scheduling

• Round Robin Scheduling with time quantum of 4 Process Arrival time Priority CPU burst time

P1 0 5 10

P2 2 2 6

P3 3 1 1

P4 4 2 4

Solution

• FCFS scheduling :-

First Come First Serve is a CPU scheduling algorithm. In this algorithm, Jobs are executed on First Come First Serve basis.That is, the job that comes first, executes first. Although this algorithm is easy to understand and easy to implement, it gives poor performance as Average Waiting Time is high.It does not care about any priority.

Given Example:-

Average Tourn Around Time = 13.75

Average Waiting Time = 8.5

Gantt Chart :-

0 10 16 17 21

• Preemptive SJF scheduling  :-

The Shortest Job First Scheduling Algorithm executes the processes having the least burst time or execution time from the Ready Queue. The processes are, therefore, compared with each other and arranged based on their execution times. The processes which have the largest execution time executes at the last.

Since this SJF Scheduling Algorithm is a Preemptive Scheduling algorithm, the CPU can, therefore, leave a process and switch to another process. This technique, therefore, reduces the overall Response Time of the processes and increases the system performance.

Gantt Chart :-

P1

0 2 3 4 08 13 21

Explanation :

Shortest Brust Time process P3 but it enter into queue after 3 seconds the shortest brust time process with 0 arrival time P1 while it is executing the another short brust time process enter into queue after 2 seconds then P1 going to the waiting state P2 enter into execution after 3 seconds the process P3 enter into queue it have shortest brust time then P2 then it comple it\'s execution then P4 enter into queue after 4th second the P4 has shortest burst time then P1 ans P2 then it complete it\'s execution then the waiting process P2 enter into execution it complete it\'s remaining work the same happend to the P1 also.

Average Waiting Time: 4.5
Average Turnaround Time: 9.250000

• Non-preemptive priority scheduling :-

In priority scheduling algorithm each process has a priority associated with it and as each process hits the queue, it is stored in based on its priority so that process with higher priority are dealt with first. It should be noted that equal priority processes are scheduled in FCFS order.

Gantt Chart :-

P1

0 2 3 4 09 13 21   

Explanation :- Refer SJF.

Average Waiting Time: 4.75
Average Turnaround Time: 9.5

Note :- In table processes are exequting accoring to it\'s priority P3,P2,P4,P1;

and P1 waited 13 seconds because it was complete it\'s 2 seconds in first it wait 13 seconds for complete next 8 seconds.

Round Robin Scheduling (with time quantum of 4 ) :-

1. The queue structure in ready queue is of First In First Out (FIFO) type.

2. A fixed time is allotted to every process that arrives in the queue. This fixed time is known as time slice or time quantum.

3. The first process that arrives is selected and sent to the processor for execution. If it is not able to complete its execution within the time quantum provided, then an interrupt is generated using an automated timer.

4. The process is then stopped and is sent back at the end of the queue. However, the state is saved and context is thereby stored in memory. This helps the process to resume from the point where it was interrupted.

5. The scheduler selects another process from the ready queue and dispatches it to the processor for its execution. It is executed until the time Quantum does not exceed.

6. The same steps are repeated until all the process are finished.

Gantt Chart :-

0 4 8 9 13 17 19 21

Process | ArrivalTime BrustTime FinishTime Turnaround time| waiting time

P[3] | 3 1 9 6 | 5
P[4] | 4 4 13 9 | 5
P[2] | 2 6 19 17 | 11
P[1] | 0 10 21 21 | 11

Avg sum_wait = 8.000000
Avg sum_turnaround = 13.250000

The above solution was give clear clarification for all shedulling alogorithms with it\' Gantt Charts entire process tables and it\'s definition and process explanations.