Scan Scheduling vs. C-Scan Scheduling in OSs

Abstract

Silberschatz and Galvin (2009) explained that one of the important responsibilities of the operating system is to use the hardware efficiently, and as such; hardware such as the disk drives enabling such requirements with fast access and large disk bandwidth. With such disk drives performance, the access time has two major components:

 

  • Seek Time – Which is the time required for the disk arm to move the heads to the cylinder containing the desire sector. There is an additional time required to rotate the desire sector to the disk head (Called rotational latency).
  • Bandwidth – Which is the total number of bytes transferred, divided by the total time between the first request for service, and time used for the last transfer.

Silberschatz and Galvin (2009) explained that to improve the above components (Access Time & Bandwidth) it’s imperative for the operating system to manage the order in which disk I/O requests are serviced. When a process requires I/O from the disk, it issues a system call to the operating system. If the desired disk and its controller are available, the request can be serviced immediately. However, if they’re busy, any new requests are placed in the disk queue. When one request is completed, the operating system chooses which pending request to service next via one of the following algorithms:

 

  • Scan scheduling – with such algorithm, the arm starts from one end of the disk and moves toward the other end, and it reaches each cylinder to the other end of the disk’s servicing requests.

 

  • C-Scan scheduling – with such algorithm the head of the disk moves from one end of the disk to the other end, servicing requests along the way. It immediately returns to the beginning of the disk without servicing any requests during the returning trip.

Scan Scheduling vs. C-Scan Scheduling

Silberschatz and Galvin (2009) explained that the scan algorithm is also called the elevator algorithm since the disk arm behaves like an elevator in a building, first servicing all the requests going up and then servicing all requests as it is going down. One the other hand the C-Scan scheduling algorithm treats the disk cylinder as a circular list.

Roth (2005) explained that for each I/O request that required a disk access, the head of such disk move over the destination track where the disk rotates toward the position of desired sector, and the read/write operation is performed. There are two required objects for the disk scheduling algorithm to achieve the best performance:

 

  • Minimize the average number of requests satisfied per time unit (throughput).
  • Maximize the response time by minimizing the average time required for a request must to wait before it is satisfied.

In the scan algorithm, and with the scenario where the requests are in one end of the disk and the head on the other end, the time consumed is high for the head to stratify the requests in such scenario. On the other hand with the above scenario, the C-Scan algorithm will be a good solution where once the edge of the disk is reached, the head returns to the opposite edge without dealing with any requests. Such algorithm will speed up the time required to satisfy the requests in such scenario over the scan algorithm (Bonyadi and Moghaddam, 2009).

Bonyadi and Moghaddam (2009) explained that speeding up both algorithms can be done by avoiding travelling to the other edge of the cylinders if there is no data near the edges. By applying algorithms such as Look and C-Look which act just like Scan and C-Scan Algorithms except that they stop if there are no requests waiting on the other edge. One of the advantages of the C-Scan over the Scan algorithm is that C-Scan provides more of a uniform waiting time for servicing the requests over the Scan algorithm.

Look algorithm provides the optimal solution over the Scan algorithm where the disk arm doesn’t reach the inner or outer track if there are no outstanding requests in either ends. On the other hand, C-Look moves the head toward one direction as C-Scan, however, in C-Look after servicing the last request in the current direction, it reverse direction to the first request on the other end without servicing any request on the return trip (Bonyadi and Moghaddam, 2009).

Conclusion

Disk scheduling is an operating system process that satisfies the disk requests. Disk scheduling algorithm are used to optimize and minimize the number of head seeks that represent the slowest operations in the modern computing systems. In the Scan algorithm (also known as elevator); where the arm moves in one direction to another (i.e. right to left and then left to right) after servicing all the requests in this direction. Another algorithm used to optimize the disk I/O is the circular scan (C-Scan) where it works in the same way as scan algorithm, however, C-Scan servicing requests in one direction (Bonyadi and Moghaddam, 2009).

Look and C-Look algorithms represent better solutions over the Scan and C-Scan algorithms where seek time is saved by using a direct access mechanism to the direction and the location in the sector where service is requested (Roth, 2005).

References

Bonyadi, M. & Moghaddam, M. (2009) ‘A genetic based disk scheduling method to decrease makespan and missed tasks’’, The 2010 InfoSecurity Virtual Conference, pp. 791-803, Sciverse Journal [Online]. Available from: http://www.sciencedirect.com.ezproxy.liv.ac.uk/science?_ob=ArticleURL&_udi=B6V0G-4YYGH6D1&_user=822084&_coverDate=11%2F30%2F2010&_rdoc=1&_fmt=high&_orig=search&_origin=search&_sort=d&_docanchor=&view=c&_acct=C000044499&_version=1&_urlVersion=0&_userid=822084&md5=853f6d1cd019352b42ff1711147023c4&searchtype=a (Accessed: 9 September 2010).

Roth, A. (2005) Power Aware Disk Scheduling Algorithms for Real-Time Systems [Online]. Available from: http://www.eng.auburn.edu/~xqin/theses/MS-Roth-pastorage.pdf (Accessed: 9 September 2010).

Silberschatz, A. & Galvin, P. (2009) Operating System Concepts. 8th ed. NJ: John Wiley & Sons, Inc.

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: