Discuss the concept of SJF and SRTN scheduling algorithms with suitable example.

Question

Bipin Tiwari · Accepted Answer

Shortest Job First (SJF) Scheduling Till now, we were scheduling the processes according to their arrival time (in FCFS scheduling). However, the SJF scheduling algorithm schedules the processes according to their burst time. In SJF scheduling, the process with the lowest burst time, among the list of available processes in the ready queue, is going to be scheduled next. However, it is very difficult to predict the burst time needed for a process hence this algorithm is very difficult to implement in the system. Advantages of SJF: Maximum throughput Minimum average waiting and turnaround time Disadvantages of SJF: May suffer from the problem of starvation It is not implementable because the exact Burst time for a process can't be known in advance. Example: In the following example, there are five jobs named as P1, P2, P3, P4, and P5. Their arrival time and burst time are given in the table below. PID Arrival Time Burst Time Completion Time Turn Around Time Waiting Time 1 1 7 8 7 0 2 3 3 13 10 7 3 6 2 10 4 2 4 7 10 31 24 14 5 9 8 21 12 4 Since No Process arrives at time 0 hence; there will be an empty slot in the Gantt chart from time 0 to 1 (the time at which the first process arrives). According to the algorithm, the OS schedules the process which is having the lowest burst time among the available processes in the ready queue. Till now, we have only one process in the ready queue hence the scheduler will schedule this to the processor no matter what is its burst time. This will be executed for 8 units of time. Till then we have three more processes arrived in the ready queue hence the scheduler will choose the process with the lowest burst time. Among the processes given in the table, P3 will be executed next since it is having the lowest burst time among all the available processes. So that's how the procedure will go on in the shortest job first (SJF) scheduling algorithm. Avg Waiting Time = 27/5 Shortest Remaining Time First (SRTF) Scheduling Algorithm: This Algorithm is the preemptive version of SJF scheduling. In SRTF, the execution of the process can be stopped after a certain amount of time. At the arrival of every process, the short-term scheduler schedules the process with the least remaining burst time among the list of available processes and the running process. Once all the processes are available in the ready queue, No preemption will be done and the algorithm will work as SJF scheduling. The context of the process is saved in the Process Control Block when the process is removed from the execution and the next process is scheduled. This PCB is accessed on the next execution of this process. Example: In this example, there are five jobs P1, P2, P3, P4, P5, and P6. Their arrival time and burst time are given below in the table. Process ID Arrival Time Burst Time Completion Time Turn Around Time Waiting Time Response Time 1 0 8 20 20 12 0 2 1 4 10 9 5 1 3 2 2 4 2 0 2 4 3 1 5 2 1 4 5 4 3 13 9 6 10 6 5 2 7 2 0 5 Avg Waiting Time = 24/6 The Gantt chart is prepared according to the arrival and burst time given in the table. Since, at time 0, the only available process in P1 with CPU burst time 8. This is the only available process on the list therefore it is scheduled. The next process arrives at time unit 1. Since the algorithm we are using is SRTF which is a preemptive one, the current execution is stopped, and the scheduler checks for the process with the least burst time. Till now, there are two processes available in the ready queue. The OS has executed P1 for one unit of time till now; the remaining burst time of P1 is 7 units. The burst time of Process P2 is 4 units. Hence Process P2 is scheduled on the CPU according to the algorithm. The next process P3 arrives at time unit 2. At this time, the execution of process P3 is stopped and the process with the least remaining burst time is searched. Since the process P3 has 2 units of burst time hence it will be given priority over others. The Next Process P4 arrives at time unit 3. At this arrival, the scheduler will stop the execution of P4 and check which process is having the least burst time among the available processes (P1, P2, P3, and P4). P1 and P2 are having the remaining burst time of 7 units and 3 units respectively. P3 and P4 are having the remaining burst time 1 unit each. Since both are equal hence the scheduling will be done according to their arrival time. P3 arrives earlier than P4 and therefore it will be scheduled again. The Next Process P5 arrives at time unit 4. Till this time, Process P3 has completed its execution and it is no more on the list. The scheduler will compare the remaining burst time of all the available processes. Since the burst time of the process, P4 is 1 which is the least among all hence this will be scheduled. The Next Process P6 arrives at time unit 5, till this time, Process P4 has completed its execution. We have 4 available processes now, that are P1 (7), P2 (3), P5 (3), and P6 (2). The Burst time of P6 is the least among all hence P6 is scheduled. Since, now, all the processes are available hence the algorithm will now work the same as SJF. P6 will be executed till its completion and then the process with the least remaining time will be scheduled. Once all the processes arrive, No preemption is done and the algorithm will work as SJF.

Discuss the concept of SJF and SRTN scheduling algorithms with suitable example.

Leave your Answer:

Hits Counter

Question

Discuss the concept of SJF and SRTN scheduling algorithms with suitable example.

Leave your Answer: