Operating system 29 non preemptive scheduling

These scheduling mechanism do not force the process to be deallocated from CPU to release the resource as and when required.
The processes release the resources only when it has finished executing

1. Operating System 29 Non-preemptive Scheduling Prof Neeraj Bhargava Vaibhav Khanna Department of Computer Science School of Engineering and Systems Sciences Maharshi Dayanand Saraswati University Ajmer

2. Non-preemptive Scheduling These scheduling mechanism do not force the process to be deallocated from CPU to release the resource as and when required. The processes release the resources only when it has finished executing

3. First- Come, First-Served (FCFS) Scheduling The CPU, in this scheme, is scheduled to the processes in the order of arrival at the ready queue. This scheme can be easily implemented using a queue data structure. The processes are queued up by enqueuer (software component of operating system), in the order of their arrival at the tail of the queue. Whenever, the CPU is available, the dispatcher (software component of operating system), removes a process from the head of the queue and schedules it to the CPU.

4. First- Come, First-Served (FCFS) Scheduling Process Burst Time P 1 24 P 2 3 P 3 3 Suppose that the processes arrive in the order: P 1 , P 2 , P 3 The Gantt Chart for the schedule is: Waiting time for P 1 = 0; P 2 = 24; P 3 = 27 Average waiting time: (0 + 24 + 27)/3 = 17

5. FCFS Scheduling (Cont.) Suppose that the processes arrive in the order: P 2 , P 3 , P 1 The Gantt chart for the schedule is: Waiting time for P 1 = 6 ; P 2 = 0 ; P 3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 Much better than previous case Convoy effect - short process behind long process Consider one CPU-bound and many I/O-bound processes

6. Shortest-Job-First (SJF) Scheduling Associate with each process the length of its next CPU burst Use these lengths to schedule the process with the shortest time SJF is optimal – gives minimum average waiting time for a given set of processes The difficulty is knowing the length of the next CPU request Could ask the user

7. Shortest-Job-First (SJF) Scheduling This algorithm associates with each process the length of the number of CPU bursts needed by it for its execution. The process having the smallest next CPU burst is allocated the CPU whenever it is available next. In case there is a tie, FCFS scheme is employed to break the tie.

8. Example of SJF Process Arriva l Time Burst Time P 1 0.0 6 P 2 2.0 8 P 3 4.0 7 P 4 5.0 3 SJF scheduling chart Average waiting time = (3 + 16 + 9 + 0) / 4 = 7

9. Determining Length of Next CPU Burst Can only estimate the length – should be similar to the previous one Then pick process with shortest predicted next CPU burst Can be done by using the length of previous CPU bursts, using exponential averaging Commonly, α set to ½ Preemptive version called shortest-remaining-time-first

10. Prediction of the Length of the Next CPU Burst

11. Examples of Exponential Averaging  =0  n+1 =  n Recent history does not count  =1  n+1 =  t n Only the actual last CPU burst counts If we expand the formula, we get:  n +1 =  t n +(1 -  )  t n -1 + … +( 1 -  ) j  t n - j + … +( 1 -  ) n +1  Since both  and (1 - ) are less than or equal to 1, each successive term has less weight than its predecessor

12. Example of Shortest-remaining-time-first Now we add the concepts of varying arrival times and preemption to the analysis Process A arri Arrival Time T Burst Time P 1 8 P 2 1 4 P 3 2 9 P 4 3 5 Preemptive SJF Gantt Chart Average waiting time = [(10-1)+(1-1)+(17-2)+5-3)]/4 = 26/4 = 6.5 msec

13. Priority Scheduling A priority number (integer) is associated with each process The CPU is allocated to the process with the highest priority (smallest integer  highest priority) Preemptive Nonpreemptive SJF is priority scheduling where priority is the inverse of predicted next CPU burst time Problem  Starvation – low priority processes may never execute Solution  Aging – as time progresses increase the priority of the process

14. Priority Scheduling A more general schedule algorithm of which both FCSC and SJF is priority scheduling. This algorithm associates a priority with each process on some pre-determined basis. The CPU is allocated to the process having highest priority. If the priorities associated to processes are equal then the algorithm reduces to FCSC. SJF is a special case of priority scheduling with priorities associated according to the number of CPU burst required by the processes, the process with smallest CPU burst requirement having highest priority.

15. Example of Priority Scheduling Process A arri Burst Time T Priority P 1 1 3 P 2 1 1 P 3 2 4 P 4 1 5 P 5 5 2 Priority scheduling Gantt Chart Average waiting time = 8.2 msec

16. Assignment What do you understand by Non Preemptive Scheduling Explain First- Come, First-Served (FCFS) Scheduling Explain Shortest-Job-First (SJF) Scheduling Explain Priority Scheduling