CS - 604 Assignment 3 solution fall 2020 || 2021 CS604 Assignment No 3 Solution Fall 2020 || 2021

Download File

Scheduling Algorithms:

We will now discuss some of the commonly used short-term scheduling algorithms. Some of these algorithms are suited well for batch systems and others for time-sharing systems. Here are the algorithms we will discuss: 

§  First-Come-First-Served (FCFS) Scheduling 

§  Shorted Job First (SJF) Scheduling 

§  Shortest Remaining Time First (SRTF) Scheduling 

§  Priority Scheduling 

§  Round-Robin Scheduling 

§  Multilevel Queues Scheduling 

§  Multilevel Feedback Queues Scheduling 

§  UNIX System V Scheduling

First-Come, First-Served (FCFS) Scheduling:

The process that requests the CPU first (i.e., enters the ready queue first) is allocated the CPU first. The implementation of an FCFS policy is managed with a FIFO queue. When a process enters the ready queue, its PCB is linked onto the tail of the queue. When CPU is free, it is allocated to the process at the head of the queue. The running process is removed from the queue. The average waiting time under FCFS policy is not minimal and may vary substantially if the process CPU-burst times vary greatly. FCFS is a nonpreemptive scheduling algorithm. We use the following system state to demonstrate the working of this algorithm. For simplicity, we assume that processes are in the ready queue at time 0.        Process P1                24            P2       P3  Burst Time  24 3 3  Suppose that processes arrive into the system in the order: P1, P2, P3. Processes are served in the order: P1, P2, P3.The Gantt chart for the schedule is shown in Figure 14.3.

.3 Gantt chart showing execution of processes in the order P1, P2, P3 Here are the waiting times for the three processes and the average waiting time per process.  Waiting times P1 = 0; P2 = 24; P3 = 27  Average waiting time: (0+24+27)/3 = 17 

Suppose that processes arrive in the order: P2, P3, P1. The Gantt chart for the schedule is shown in Figure 14.4:

Figure 14.4 Gantt chart showing execution of processes in the order P2, P3, P1 

Here are the waiting times for the three processes and the average waiting time per process.  Waiting time for P1 = 6; P2 = 0; P3 = 3  Average waiting time: (6 + 0 + 3)/3 = 3 

When FCFS scheduling algorithm is used, the convoy effect occurs when short processes wait behind a long process to use the CPU and enter the ready queue in a convoy after completing their I/O. This results in lower CPU and device utilization than might be possible if shorter processes were allowed to go first. In the next lecture, we will discuss more scheduling algorithms.