Question

Use the following list of cylinder requests in Exercises 54-56. They are listed in the order in which they were received. \(40,12,22,66,67,33,80\) List the order in which these requests are handled if the SCAN algorithm is used. Assume that the disk is positioned at cylinder 50 and the read/write heads are moving toward the higher cylinder numbers.

Short answer

Order of requests: 66, 67, 80, 40, 33, 22, 12.

Step-by-step solution

Identify the Initial Position and Direction

The initial position of the disk head is at cylinder 50. The read/write head is moving towards higher cylinder numbers.

Separate Requests by Direction

Categorize the cylinder requests into those that can be serviced going towards the higher numbers (greater than 50) and those that will be serviced after reversing direction (less than 50). These groups are: \[\text{Requests for higher numbers}: 66, 67, 80\] \[\text{Requests for lower numbers}: 40, 12, 22, 33\]

Handle Requests in Ascending Order (Higher Cylinders)

Service the requests in the direction of head movement in ascending order. Start from the current position 50 and move up through 66, 67, and finally 80.

Reverse Direction and Handle Lower Cylinders

After reaching the highest request in the initial direction (at cylinder 80), reverse direction and service the requests in the opposite direction. Handle them in ascending order: 40, 33, 22, and finally 12.

Key concepts

Cylinder requests

When dealing with the SCAN disk scheduling algorithm, understanding cylinder requests is crucial. These requests represent the specific disk locations, termed as cylinders, that the disk head must access to read or write data. In this context, a list of cylinder requests, such as \(40, 12, 22, 66, 67, 33, 80\), is given to a scheduling algorithm to determine the most efficient path for the disk head to follow.
The list is ordered by the time each request is received, but the SCAN algorithm rearranges them based on current disk head positioning and its traveling direction. This makes understanding the flow of requests within the algorithm essential for predicting disk performance.
By categorizing requests into those above and below a certain point (i.e., current position of the disk head), the SCAN algorithm can efficiently schedule its servicing strategy.

Disk head positioning

Disk head positioning is a fundamental aspect when working with disk scheduling algorithms like SCAN. Initially, the disk head must be positioned at a specific cylinder, as specified in our example, at cylinder 50.
The direction of movement influences how the requests will be serviced. Initially, the disk head moves towards higher cylinder numbers. This positional context allows the algorithm to sequence and service requests methodically, improving system efficiency and reducing time consumption.
Understanding the initial position and subsequent movement is vital, as it sets the structure for handling requests, ensuring that the servicing order is both logical and efficient.

Request servicing order

The request servicing order is the sequence in which the disk head accesses the requested cylinders. For the SCAN algorithm, this order plays a major role in optimizing movement.

• The algorithm starts by serving requests in the direction of the disk head's initial movement. In this example, once the disk head is at cylinder 50, it moves upwards, servicing requests at 66, 67, and 80.
• After dealing with these requests, the disk head changes direction upon reaching the last request in its current trajectory.
• It then services the remaining requests in reverse, starting from the highest point reached — in this case, from 80 down to the next batch located at lower numbers: 40, 33, 22, and finally 12.

This order reduces the total distance traveled by the disk head, thus optimizing the performance by minimizing seek time.

Ascending cylinder order

Once requests are filed based on their initial direction, the SCAN algorithm handles them in ascending cylinder order. This orderly processing ensures that requests are serviced in a logical, sequential manner.
The algorithm first sorts and processes the requests towards higher numbers, in up-order, following the current direction of the disk head. Requests \(66, 67,\) and \(80\) are serviced as the disk head moves up. After reaching the final request in the initial list, the algorithm reverses, descending cylinder order is used.
During the returning sweep, the requests previously queued are processed from lowest to highest within that opposite path strategy: starting with \(40\), then \(33\), followed by \(22\), and finally \(12\). By adhering to this systematic execution order, SCAN reduces unnecessary head movement and increases efficiency.