Operating System Tutorial

What is Operating System Evolution of Operating System Types of Operating System Functions of Operating System What is Kernel and Types of Kernel Operating System Properties Operating System Services Components of Operating System Needs of the Operating System Linux Operating System Unix Operating System Ubuntu Operating System What is DOS Operating System Difference Between Multi-programming and Multitasking What is Thread and Types of Thread Process Management Process State What is Process Scheduler and Process Queue What is Context Switching What is CPU Scheduling Scheduling Algorithm FCFS (First-come-First-Serve) Scheduling SJF (Shortest Job First) Scheduling Round-Robin CPU Scheduling Priority Based Scheduling HRRN (Highest Response Ratio Next) Scheduling Process Synchronization Lock Variable Mechanism TSL Mechanism Turn Variable Mechanism Interested Variable Mechanism What is Producer-Consumer Problem What is Semaphore in Operating System Monitors in Operating System What is Deadlock Deadlock Avoidance Strategies for Handling Deadlock Deadlock Prevention Deadlock Detection and Recovery Resource Allocation Graph Banker’s Algorithm in Operating System Fixed Partitioning and Dynamic Partitioning Partitioning Algorithms What is Paging and Segmentation What is Demand Paging What is Virtual Memory Disk Scheduling Algorithms FCFS and SSTF Disk Scheduling Algorithm SCAN and C-SCAN Disk Scheduling Algorithm Look and C-Look Disk Scheduling Algorithm File in Operating System File Access Methods in Operating System File Allocation Method Directory Structure in Operating System Difference between C-LOOK and C-SCAN Difference between Rotational Latency and Disk Assess Time Trap vs Interrupt How to implement Monitors using Semaphores N-Step-SCAN Disk Scheduling Why is it critical for the Scheduler to distinguish between I/O-bound and CPU-bound programs Difference between C-SCAN and SSTF Difference between SCAN and FCFS Difference between Seek Time and Disk Access Time Difference between SSTF and LOOK

FCFS (First-Come-First-Serve) Disk Scheduling Algorithm

FCFS Disk Scheduling Algorithm

FCFS (First-Come-First-Serve) is the easiest disk scheduling algorithm among all the scheduling algorithms. In the FCFS disk scheduling algorithm, each input/output request is served in the order in which the requests arrive. In this algorithm, starvation does not occur because FCFS address each request.

Advantages of FCFS Disk scheduling Algorithm

The advantages of FCFS disk scheduling algorithm are:

  1. In FCFS disk scheduling, there is no indefinite delay.
  2. There is no starvation in FCFS disk scheduling because each request gets a fair chance.

Disadvantages of FCFS Disk Scheduling Algorithm

The disadvantages of FCFS disk scheduling algorithm are:

  1. FCFS scheduling is not offered as the best service.
  2. In FCFS, scheduling disk time is not optimized.

Example of FCFS Disk Scheduling Algorithm

Suppose a disk contains 200 tracks (0-199) and the request queue contains track no: 93, 176, 42, 148, 27, 14,180. The current position of the read/write head is 55. Now we have to calculate the total number of track movements of read/write head using FCFS scheduling.

Solution

As mentioned in the following example, the disk contains 200 tracks, so we take a track line between 0 to 199.

The current position of the read/write head is 55. So, we start from 55, then move read/write head in the FCFS order. When all the requests are addressed, then we calculate a total number of cylinders moved by the head.

FCFS Disk Scheduling Algorithm
Figure: FCFS Disk Scheduling

Total Number of cylinders moved by the head = (176-55) + (176-42) + (148-42) + (148-14) + (180-14)

                                                                     = 121+134+106+134+166

                                                                     =661   

SSTF (Shortest Seek Time First) Disk Scheduling Algorithm

SSTF is another type of scheduling algorithm. In this type of disk scheduling, the job which has less seek time will be executed first. So, in SSTF (shortest seek time first) scheduling, we have to calculate the seek time first. and after calculating the seek time, each request will be served on the basis of seek time. The request which is close to the disk arm will be first executed. There are some drawbacks in FCFS. To overcome the limitations that arise in the FCFS. SSTF scheduling is implemented.

Advantages of SSTF Disk Scheduling

The advantages of SSTF disk scheduling are:

  1. In SSTF disk scheduling, the average response time is decreased.
  2. Increased throughput.

Disadvantages of SSTF Disk Scheduling

The disadvantages of SSTF disk scheduling are:

  1. In SSTF, there may be a chance of starvation.
  2. SSTF is not an optimal algorithm.
  3. There are chances of overhead in SSTF disk scheduling because, in this algorithm, we have to calculate the seek time in advanced.
  4. The speed of this algorithm can be decreased because direction could be switched frequently.

Example of SSTF Disk Scheduling

Consider a disk that contains 200 tracks (0-199). The request queue includes track number 82, 170, 43, 140, 24, 16, 190, respectively. The current position of the read/write head is 50.

Solution

Before solving the above example, we have to know about the seek time.

Seek Time: -Seek time is the time required to move the desired track.

To find the seek time, we can use this simple formula.

                                            seek time = Destination – Source

                                             or

                                             = Source - Destination

 Now, we can solve the given example.

As mentioned in the following example, disk contains 200 tracks. So, we will take a track line between 0 to 199. The current position of the read/write head is 50. So, we start at 50.

SSTF Disk Scheduling Algorithm
Figure: SSTF Disk Scheduling

We can see in the following figure that the current or initial position of read/write head is 50. Now for further movement of read/write head, we calculate the seek time. 

Total Number of cylinders moved by the head = (50-16) + (190-16)

                                                                     = 208



ADVERTISEMENT
ADVERTISEMENT