Theory¶

FCFS¶

  • FCFS stands for First Come First Served.
  • As the name suggests, this algorithm entertains requests in the order they arrive in the disk queue.
  • It is the simplest disk scheduling algorithm.

Advantages¶

  • It is simple, easy to understand and implement.
  • It does not cause starvation to any request.

Disadvantages¶

  • It results in increased total seek time.
  • It is inefficient.

SSTF¶

  • SSTF stands for Shortest Seek Time First.
  • This algorithm services that request next which requires least number of head movements from its current position regardless of the direction.
  • It breaks the tie in the direction of head movement.

Advantages¶

  • It reduces the total seek time as compared to FCFS.
  • It provides increased throughput.
  • It provides less average response time and waiting time.

Disadvantages¶

  • There is an overhead of finding out the closest request.
  • The requests which are far from the head might starve for the CPU.
  • It provides high variance in response time and waiting time.
  • Switching the direction of head frequently slows down the algorithm.
In [1]:
currentTracks = [53, 50]
requestArrays = [[176, 79, 34, 60, 92, 11, 41, 114],
       [4, 34, 10, 7, 19, 73, 2, 15, 6, 20],
       [98, 183, 41, 122, 14, 124, 65, 67]]

Algorithm for FCFS¶

  1. Let Request array represents an array storing indexes of tracks that have been requested in ascending order of their time of arrival.
  2. head is the position of disk head.
  3. Let us one by one take the tracks in default order and calculate the absolute distance of the track from the head.
  4. Increment the total seek count with this distance.
  5. Currently serviced track position now becomes the new head position.
  6. Go to step 3 until all tracks in request array have not been serviced.
In [2]:
def fcfs(array: list, start: int, log = False) -> int:
    rotations = 0
    current = start
    for i in array:
        value = abs(i - current)
                
        # TODO: print log statements
        if log: print(f'|{i} - {current}| = {value}')
        current = i; rotations += value
    return rotations

Algorithm for SSTF¶

  1. Let the Request array represents an array storing indexes of tracks that have been requested.
  2. head is the position of the disk head.
  3. Find the positive distance of all tracks in the request array from the head.
  4. Find a track from the requested array which has not been accessed/serviced yet and has a minimum distance from the head.
  5. Increment the total seek count with this distance.
  6. Currently serviced track position now becomes the new head position.
  7. Go to step 3 until all tracks in the request array have not been serviced.
In [3]:
def sstf(array: list, start: int, isUpDirection = True, log = False) -> (int, list):
    rotations = 0
    current = start
    auxillaryArray = array[:]
    seekSequence = []

    new_current = current
    previousHeadMovement = isUpDirection # True = up, False = down (default)

    while len(auxillaryArray) > 0:
        min_rotations = float('inf')
        currentHeadMovement = previousHeadMovement

        for i in auxillaryArray:

            value = i - current
            
            if abs(value) < min_rotations:

                if value < 0: currentHeadMovement = True
                else: currentHeadMovement = False

                min_rotations = abs(value)
                new_current = i
            elif value == min_rotations:
                if currentHeadMovement == previousHeadMovement: new_current = i

        previousHeadMovement = currentHeadMovement

        # TODO: print log statements
        if log: print(f'|{new_current} - {current}| = {min_rotations}')
        
        current = new_current; rotations += min_rotations
        auxillaryArray.remove(current)
        seekSequence.append(current)
    return rotations, seekSequence

Questions¶

Q1. Consider a disk queue with requests for I/O to blocks on cylinders $\ 98, 183, 41, 122, 14, 124, 65, 67 \ $. The FCFS scheduling algorithm is used. The head is initially at cylinder number 53. The cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while servicing these requests is _______

In [4]:
print(f'Total number of head movements = {fcfs(requestArrays[2], currentTracks[0], log = True)}')

|98 - 53| = 45
|183 - 98| = 85
|41 - 183| = 142
|122 - 41| = 81
|14 - 122| = 108
|124 - 14| = 110
|65 - 124| = 59
|67 - 65| = 2
Total number of head movements = 632

Q2. Consider a disk queue with requests for I/O to blocks on cylinders $\ 98, 183, 41, 122, 14, 124, 65, 67\ $. The SSTF scheduling algorithm is used. The head is initially at cylinder number 53 moving towards larger cylinder numbers (UP direction) on its servicing pass. The cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while servicing these requests is _______

In [5]:
rotations, seek_sequence = sstf(requestArrays[2], currentTracks[0], log = True)
print(f"Total number of head movements = {rotations}\nSeek sequence: {', '.join(map(str, seek_sequence))}")

|65 - 53| = 12
|67 - 65| = 2
|41 - 67| = 26
|14 - 41| = 27
|98 - 14| = 84
|122 - 98| = 24
|124 - 122| = 2
|183 - 124| = 59
Total number of head movements = 236
Seek sequence: 65, 67, 41, 14, 98, 122, 124, 183

Q3. Consider a disk system with 100 cylinders. The requests to access the cylinders occur in following sequence-

$$4, 34, 10, 7, 19, 73, 2, 15, 6, 20$$

Assuming that the head is currently at cylinder 50, what is the time taken to satisfy all requests if it takes 1 ms to move from one cylinder to adjacent one and shortest seek time first policy is used?

  1. 95 ms
  2. 119 ms
  3. 233 ms
  4. 276 ms
In [6]:
rotations, seek_sequence = sstf(requestArrays[1], currentTracks[1], log = True)
print(f"Total number of head movements = {rotations}\nSeek sequence: {', '.join(map(str, seek_sequence))}")

|34 - 50| = 16
|20 - 34| = 14
|19 - 20| = 1
|15 - 19| = 4
|10 - 15| = 5
|7 - 10| = 3
|6 - 7| = 1
|4 - 6| = 2
|2 - 4| = 2
|73 - 2| = 71
Total number of head movements = 119
Seek sequence: 34, 20, 19, 15, 10, 7, 6, 4, 2, 73

$\therefore$ Time required for $119$ head movements $=119\times 1=\boxed{119\ ms}$

Q4. Consider a disk queue with requests for I/O to blocks on cylinders $\ 176, 79, 34, 60, 92, 11, 41, 114\ $. The SSTF scheduling algorithm is used. The head is initially at cylinder number 50 moving towards larger cylinder numbers (UP direction) on its servicing pass. The cylinders are numbered from 0 to 199. The total head movement (in number of cylinders) incurred while servicing these requests is _______

In [7]:
rotations, seek_sequence = sstf(requestArrays[0], currentTracks[1], log = True)
print(f"Total number of head movements = {rotations}\nSeek sequence: {', '.join(map(str, seek_sequence))}")

|41 - 50| = 9
|34 - 41| = 7
|11 - 34| = 23
|60 - 11| = 49
|79 - 60| = 19
|92 - 79| = 13
|114 - 92| = 22
|176 - 114| = 62
Total number of head movements = 204
Seek sequence: 41, 34, 11, 60, 79, 92, 114, 176