OS-Seek Optimization

Most popular seek optimization strategies.

1) FCFS(First-Come-First Served) Scheduling:

In FCFS scheduling, the first request to arrive is the first one serviced. FCFS is fair in the same that once a request has arrived, its place in the schedule is fixed. A request cannot be displaced because of the arrival of a higher priority request. FCFS will actually do a lengthy seek to service a distant waiting request even though another request may have just arrived on the same cylinder to which the read-write head is currently positioned. It ignores the positional relationships among the pending requests in the queue. FCFS is acceptable when the load on a disk is light. FCFS tend to saturate the device and response times become large.

2) SSTF(Shortest-Seek-Time-First) Scheduling:

In SSTF Scheduling, the request that results in the shortest seek distance is serviced next, even if that request is not the first one in the queue. SSTF is a cylinder –oriented shceme SSTF seek patterns tend to be highly localized with the result that the innermost and outermost tracks can receive poor service compared with the mid-range tracks. 

SSTF results in better throughput rates than FCFS, and mean response times tend to be lower for moderate loads. One significant drawback is that higher variance occur on response times because of the discrimination against the outermost and innermost tracks. SSTF is useful in batch processing systems where throughput is the major consideration. But its high variance of response times (ie., its lack of predictability) makes it unacceptable in interactive systems.

3) SCAN Scheduling:

Denning developed the SCAN scheduling strategy to overcome the discrimination and high variance in response times of SSTF. SCAN operates like SSTF except that it chooses the request that results in the shortest seek distance in a preferred direction. If the preferred direction is currently outward, then the SCAN strategy chooses the shortest seek distance in the outward direction. SCAN does not change direction until it reaches the outermost cylinder or until there are no further requests pending in the preferred direction. It is sometimes called the elevator algorithm because an elevator normally continues in one direction until there are no more requests pending and then it reverses direction. 

SCAN behaves very much like SSTF in terms of improved throughput and improved mean response times, but it eliminates much of the discrimination inherent in SSTF schemes and offers much lower variance.

One interesting modification to the basic SCAN strategy is called N-STEP SCAN . In this strategy, the disk arm moves back and forth as in SCAN except that it services only those requests waiting when a particular sweep begins. Requests arriving during a sweep are grouped together and ordered for optimum service during the return sweep. N-STEP SCAN offers good performance in throughput and mean response time. N-STEP has a lower variance of response times than either SSTF or conventional SCAN scheduling. N-STEP SCAN avoids the possibility of indefinite postponement occurring if a large number of requests arrive for the current cylinder. It saves these requests for servicing on the return sweep. 

Another interesting modification to the basic SCAN strategy is called C-SCAN (for circular SCAN). In C-SCAN strategy, the arm moves from the outer cylinder to the inner cylinder, servicing requests on a shortest-seek basis. When the arm has completed its inward sweep, it jumps (without servicing requests) to the request nearer the outermost cylinder, and then resumes its inward sweep processing requests. Thus C-SCAN completely eliminates the discrimination against requests for the innermost or outermost cylinder. It has a very small variance in response times. At low loading, the SCAN policy is best. At medium to heavy loading, C-SCAN yields the best results.

Share this article :
Copyright © 2012. Best Online Tutorials | Source codes | Programming Languages - All Rights Reserved