Disk Scheduling

Disk Scheduling

AU: Dec.-17, 18, 19

• Disk scheduling algorithms are used to reduce the total seek time of any request. I/O request issues a system call to the operating system. If desired disk drive or controller is idle then the request is served immediately. If device is bust then the request for service will be placed in the queue of pending requests.

• When one request is completed, the operating system has to choose which pending request to service next.

• The processor is much faster than the disk, so it's highly likely that there will be multiple outstanding disk requests before the disk is ready to handle them. Because disks have non-uniform access times, re-ordering disk requests can greatly reduce the latency of disk requests.

• Multiple requests to disk will arrive while one is being serviced. Disk scheduling increases the disk's bandwidth.

• To service a request, a disk system requires that the head be moved to the desired track, then a wait for latency and finally the transfer of data. In the following section we will examine several scheduling algorithms.

1. FIFO   2. SSTF     3. SCAN    4. C-SCAN      5. LOOK    6. C-LOOK

First In First Out

• FIFO is also called first come first served method. Requests are processed in queue order. Fig. 5.4.1 shows FCFS algorithm. (Fig. 5.4.1 see on next page).

• FCFS has a fair policy in the sense that once a request has arrived, its place in the schedule is fixed irrespective of arrival of a higher priority request.

• The requested tracks in the order received are: 55, 58, 39, 18, 90, 160, 150, 38 and 184. Starting track at 100 and total number of track is 200. FCFS process the entire request in sequential order:

• FCFS would begin at track 100, move 45 tracks to 55, and move 3 tracks to 58 and so on. The Y-axis corresponds to the tracks on the disk. The X-axis corresponds to time or the number of tracks traversed.

• Starting at track 100.

Next accessed track is as below.

• FCFS is simple to implement. But it does not provide fast services. It can not take special action to minimize the overall seek time.

Advantages:

1. Simple and easy to implement.

2. Suitable for light loads.

Disadvantages:

1. FCFS does not provide fast services.

2. Do not maximize throughput.

3. May involve lots of unnecessary seek distance

Shortest Seek Time First

• SSTF select the next request at the one requiring the minimum seek time from the current position. Fig. 5.4.2 shows SSTF algorithm.

• In Shortest-Seek-Time-First (SSTF) scheduling priority is given to those processes which need the shortest seek, even if these requests are not the first ones in the queue.

• It means that all requests nearer to the current head positions are serviced together before moving head to distant tracks.

• Select the disk I/O request that requires the least movement of the disk arm from its current position and always choose the minimum seek time.

• The only tricky part is if there are two jobs with the same distance. In this case, some kind of tie-breaking needs to be employed to pick one. For instance, you could just use a random number to effectively flip a coin and pick one.

• SSTF does not ensure fairness and can lead to indefinite postponement because its seek pattern tends to be highly localized.

• Under heavy load, SSTF can prevent distant requests from ever being serviced. This phenomenon is known as starvation.

• SSTF scheduling is essentially a form of shortest job first scheduling. SSTF scheduling algorithm are not very popular because of two reasons.

1. Starvation possibly exists. 2. It increases higher overheads.

Advantages:

1. Throughput is better than FCFS.

2. SSTF minimize the response time.

3. Less number of head movements.

Disadvantages:

1. One major issue is STARVATION.

2. Localize under heavy load.

SCAN

• SCAN is also called elevator algorithm.

• The next request scheduled is closest to current request but in one particular direction. All requests in other direction are put at the end of the list.

• SCAN services tracks in only one direction i.e. either increasing or decreasing track number.

• When SCAN reaches the edge of the disk (or track 0), it reverses direction.

• If any request comes on its way it will be serviced immediately, while request arriving just behind the head will have to wait until disk head moves to the end of the disk, reverses direction and returns before being serviced.

• SCAN is called elevator because an elevator continues in one direction servicing requests before reversing direction.

• Consider the example in which the requested tracks in the order received are : 55, 58, 39, 18, 90, 160, 150, 38, and 184. Starting track at 100 and total number of track is 200. Head is moving towards increasing track number.

• Current head position = 100

• Head is moving towards increasing number of track. Fig. 5.4.3 shows SCAN algorithm. (Refer Fig. 5.4.3 on previous page.)

Disadvantages:

1. Increase overhead

2. Needs directional bit

Circular SCAN

• C-SCAN also moves the head in one direction, but it offers fairer service with more uniform waiting times.

• It moves the head from one end of the disk to the other end, servicing requests along the way. When the head reaches the other end, it immediately returns to the beginning of the disk, without servicing any requests on the return trip.

• C-SCAN treats the cylinders as a circular list that wraps around from the last cylinder to the first one. It scans in cycles, always increasing or decreasing order. Fig. 5.4.4 shows C-SCAN. Consider the example in which the requested tracks in the order received are: 55, 58, 39, 18, 90, 160, 150, 38 and 184. Starting track at 100 and total number of track is 200. Head is moving towards increasing track number.

LOOK Scheduling.

• Start the head moving in one direction. Satisfy the request for the closest track in that direction when there is no more request in the direction, the head is traveling, reverse direction and repeat.

• This algorithm is similar to SCAN, but unlike SCAN, the head does not unnecessarily travel to the innermost and outermost track on each circuit.

• Fig. 5.4.5 shows the look scheduling algorithm.

• For example, the disk request queue contains a set of references for blocks on tracks 76, 124, 17, 269, 201, 29, 137 and 12.

• Current head position= 76

C-LOOK

• C-LOOK is same as C-SCAN except the head stops after servicing the last requesting the preferred direction, then services the request to the cylinder nearest the opposite side of the disk.

• Example: Consider the example in which the requested tracks in the order received are 23, 89, 132, 42, 187. Starting track at 100 and there are 200 cylinders numbered from 0 - 199.

Solved Examples

Example 5.4.1 The requested tracks, in the order received are: 55, 58, 39, 18, 90, 160, 150, 38, 184. ApplBA the following disk scheduling algorithms. Starting track at 100.

1) FCFS 2) SSTF 3) SCAN 4) C-SCAN.

Solution :

1) FCFS

2) SSTF

3) SCAN

4) C-SCAN

Example 5.4.2 Consider a disk queue with requests for I/O to blocks on cylinders.

98, 183, 37, 122, 14, 124, 65, 67.

If the disk head is start at 53, then find out the total head movement with respect to FCFS, SSTF, SCAN, C-SCAN and LOOK scheduling.   AU May-19, Marks 13

Solution: Disk head is start at 53

Example 5.4.3 Suppose that a disk drive has 5000 cylinders, numbered 0 through 4999. The drive is serving a request at cylinder 143. The queue of pending requests, in FIFO order is 86, 1470, 913, 1774, 948, 1509, 1022, 1750, 130 Starting from the head position what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests for each of the following disk-scheduling algorithms ? FCFS, SSTF, SCAN, LOOK, C-SCAN C-LOOK. Explain the pros and cons of all disks scheduling algorithms.

Solution: Request at cylinder = 143

1) FCFS: 143 → 86 →1470 →913 →1774 → 948 →1509 →1022 → 1750 →130. The total seek distance is 7081.

2) SSTF: 143 → 130 → 86 → 913 → 948 → 1022 → 1470 → 1509 → 1750 →1774. The total seek distance is 1745.

3) SCAN: 143 → 913→ 948 → 1022  → 1470 → 1509 → 1750  →1774→ 4999 → 130 → 86. The total seek distance is 9769.

4) LOOK: 143 → 913 → 948 → 1022 → 1470 → 1509 → 1750 → 1774 → 130 → 86. The total seek distance is 3319.

5) C-SCAN: 143 → 913 → 948 → 1022 → 1470 → 1509 → 1750 → 1774 → 4999 → 0 → 86 → 130. The total seek distance is 9985.

6) C-LOOK: 143 → 913 → 948 → 1022 → 1470 → 1509 → 1750 → 1774 →  86 → 130. The total seek distance is 3363.

University Question

1. State and explain the FCFS, SSTF and SCAN disk scheduling with examples.