LOOK algorithm

LOOK is a disk scheduling algorithm used to determine the order in which new disk read and write requests are processed.

Description

The LOOK algorithm is the same as the SCAN algorithm in that it also honors requests on both sweep direction of the disk head, however, this algorithm "Looks" ahead to see if there are any requests pending in the direction of head movement. If no requests are pending in the direction of head movement, then the disk head traversal will be reversed to the opposite direction and requests on the other direction can be served. In LOOK scheduling, the arm goes only as far as final requests in each direction and then reverses direction without going all the way to the end. Consider an example, Given a disk with 200 cylinders (0-199), suppose we have 8 pending requests: 98, 183, 37, 122, 14, 124, 65, 67 and that the read/write head is currently at cylinder 53. In order to complete these requests, the arm will move in the increasing order first and then will move in decreasing order after reaching the end. So, the order in which it will execute is 65, 67, 98, 122, 124, 183, 37, 14.

LOOK behaves almost identically to Shortest seek time first (SSTF), but avoids the starvation problem of SSTF. This is because LOOK is biased against the area recently traversed, and heavily favors tracks clustered at the outermost and innermost edges of the platter. LOOK is also biased towards more recently arriving jobs (on average).

Variants

• C-LOOK (Circular LOOK)

One variant of LOOK is C-LOOK. It is an effort to remove the bias in LOOK for track clusters at the edges of the platter. C-LOOK basically only scans in one direction. Either you sweep from the inside out, or the outside in. When you reach the end, you just swing the head all the way back to the beginning. This actually takes advantage of the fact that many drives can move the read/write head at high speeds if it's moving across a large number of tracks (e.g. the seek time from the last track to track 0 is smaller than one would expect and usually considerably less than the time it would take to seek there one track at a time).The huge jump from one end request to the other is not considered as a head movement as the cylinders are treated as a circular list.

• N-LOOK and F-LOOK

N and F LOOK were designed to offset LOOK’s bias towards recent jobs. Both algorithms partition the request queue into smaller sub queues and process the sub queues in order (oldest first). N-LOOK is so-called because the request queue is divided into N sub queues. F-LOOK is a simplification where there are only 2 queues, but they are used in a double-buffered fashion. While F-LOOK is processing one queue, all new requests go into the other one. To explain these algorithms we’re going to use the example of a disk with 200 tracks, and the read/write head starts at track 100. The request queue, in order, contains requests for tracks: 55, 58, 18, 90, 160, 38, we assume that the request queue is split into two, with the oldest one containing the requests for tracks: 55, 58, 18, 90. In this instance, N-LOOK and F-LOOK behave the same. Also notice, that in this configuration, it doesn’t matter which direction the head was moving in, all requested tracks are less than 100 so it will only move in the direction of decreasing tracks.

Even through the average number of tracks traversed is the same as LOOK in the worst case, N and F LOOK are in some sense, more fair than plain old LOOK. The sub queue system caps the maximum latency a process can expect between a request and it being serviced (unlike SSTF that can starve processes for arbitrary lengths of time).

• S-LOOK

The Shortest LOOK (S-LOOK) algorithm is an extension of the LOOK algorithm to handle the cases where the disk head is located between the far-end requests. The algorithm is designed to make a decision of which direction should be served first instead of only continuing to seek in the same direction before the new requests have arrived. Since the seek time is directly proportional to the seek distance, our goal is to minimize the seek distance, and hence, reduce the seek time.

Performance

LOOK has slightly better average seek times than SCAN. C-LOOK has a slightly lower variance in seek time than LOOK since the worst case seek time is nearly cut in half.

==

Heading text

• Bulleted list item

==

See also

Other variations include:

• SCAN - Elevator algorithm
• FSCAN
• N-Step-SCAN

LOOK „ like SCAN but stops moving inwards (or outwards) when no more requests in that direction exist LOOK 23, 89, 132, 42, 187 11+47+19+109+55=241 Compared to SCAN, LOOK saves going from 23 to 0 and then back. Most efficient for this sequence LOOK: It is similar to the SCAN disk scheduling algorithm except the difference that the disk arm in spite of going to the end of the disk goes only to the last request to be serviced in front of the head and then reverses its direction from there only. Thus it prevents the extra delay which occurred due to unnecessary traversal to the end of the disk. CLOOK: As LOOK is similar to SCAN algorithm, in similar way, CLOOK is similar to CSCAN disk scheduling algorithm. In CLOOK, the disk arm inspite of going to the end goes only to the last request to be serviced in front of the head and then from there goes to the other end’s last request. Thus, it also prevents the extra delay which occurred due to unnecessary traversal to the end of the disk. Each algorithm is unique in its own way.Overall Performance depends on number and type of requests.

Exercise

1) Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests. (GATE CS 2014 (A) 1 (B) 2 (C) 3 (D) 4 See this for solution.

2) Consider an operating system capable of loading and executing a single sequential user process at a time. The disk head scheduling algorithm used is First Come First Served (FCFS). If FCFS is replaced by Shortest Seek Time First (SSTF), claimed by the vendor to give 50% better benchmark results, what is the expected improvement in the I/O performance of user programs? (GATE CS 2004) (A) 50% (B) 40% (C) 25% (D) 0% See this for solution.

3) Suppose the following disk request sequence (track numbers) for a disk with 100 tracks is given: 45, 20, 90, 10, 50, 60, 80, 25, 70. Assume that the initial position of the R/W head is on track 50. The additional distance that will be traversed by the R/W head when the Shortest Seek Time First (SSTF) algorithm is used compared to the SCAN (Elevator) algorithm (assuming that SCAN algorithm moves towards 100 when it starts execution) is _________ tracks (A) 8 (B) 9 (C) 10 (D) 11 See this for solution.

4) Consider a typical disk that rotates at 15000 rotations per minute (RPM) and has a transfer rate of 50 × 10^6 bytes/sec. If the average seek time of the disk is twice the average rotational delay and the controller’s transfer time is 10 times the disk transfer time, the average time (in milliseconds) to read or write a 512 byte sector of the disk is

ARTICLE EDIT BY:-AADESH KHOLA