SCAN and C-SCAN algorithm

Efficient disk scheduling is necessary to customize the performance of an operating system, especially when handling several I/O requests. In various algorithms designed to reduce the discovery of discs, scans and C-scans are two popular strategies. The purpose of both is to improve efficiency by organizing how the disc arm runs-or by scan in the back and forth (scan) or a circular speed (C-scan). This article shows how these algorithms work, their benefits, shortcomings and when to use each.

What is Disk Scheduling?

The disc scheduling is a process used by an operating system that is to decide the order in which the disk I/O (input/output) requests are serving. When many processes request access to the hard disk, the disc scheduling algorithm determines the most efficient sequence to handle these requests.

Since it takes time to transfer the reed/right head of the disc, the main goal of disc scheduling is to reduce time, improve throughput and maximize overall system performance.

Why is disc scheduling important?

• I/o reduces waiting time for requests
• Reaction for users and applications improves in time
• Increases disk usage by organizing the head movement efficiently
• Prevents lower-priority or starvation of distant requests (in fair algorithms)

SCAN Algorithm

The SCAN operates all the requests on the way by moving the reed/right head of the disk in one direction (either high or low-number-number), serving all the requests on the way. Once it reaches the final request at the end of that direction or disc, the head reverses the direction and continues the remaining requests on the way back. It is a constant movement that the scan is also known as a lift algorithm.

It is also called as Elevator Algorithm. In this algorithm, the disk arm moves into a particular direction till the end, satisfying all the requests coming in its path,and then it turns backand moves in the reverse direction satisfying requests coming in its path.

It works in the way an elevator works, elevator moves in a direction completely till the last floor of that direction and then turns back.

How SCAN Works?

The scan disc scheduling algorithm operates by moving the reed/right head of the disc in a certain direction, serving all arrears I/O which lies with its path. Once the head reaches the end of the disc or the final request in that direction, it reverse its course and starts servicing the requests in the opposite direction. This method continues repeatedly, makes a back and forth speed that is similar to the work of a lift-hence the surname, lift algorithm.

In the beginning, the current status of the disc head and the direction of movement are determined. The head moves gradually on cylinders in the current direction (either high-number or lower-numbered track), examines and servicing any request matching the current cylinder. This sweep continues until there is no other request in that direction or the head does not reach the outer track.

When the head has completed its movement in one direction, it does not stop. Instead, it reverses the direction and starts moving in the opposite direction, again as it cures them on the way as servicing requests. This reverse sweep continues until it reaches the other end, after which the process is repeated.

Because scan services request in both directions, ensure that all areas of the disc are regularly attracted attention, reducing the possibility of starvation. However, the requests that come immediately after going near the head may have to wait longer for the head to return to the next sweep. Despite this, the scan performs better than simple algorithms such as the first-come-first-serve (FCFs) in the system with high I/O load, which provides a good balance between fairness and performance.

Example

Consider the following disk request sequence for a disk with 100 tracks

98, 137, 122, 183, 14, 133, 65, 78

Head pointer starting at 54 and moving in left direction. Find the number of head movements in cylinders using SCAN scheduling.

Number of Cylinders = 40 + 14 + 65 + 13 + 20 + 24 + 11 + 4 + 46 = 237

Advantages of SCAN

1. Looking for less time

The scan reduces the total head movement by serving the requests of services in one direction until the end reaches, then turns upside down. This reduces unnecessary back-and-forth movement, which reduces the average time compared to FCF.

2. Impartiality

Each request will eventually be served as the head scans the entire disc. This ensures that any request does not wait indefinitely, prevents starvation.

3. Estimated performance

Regular scanning patterns make the scan more approximate. Since the requests are handled in order along the path of the head, it is easy to estimate the response time for pending operations.

4. Better for heavy load

The scan more efficiently handles a high amount of requests more efficiently than the simple algorithm. Its systematic movement still helps maintain stable performance when the queue changes long or continuously.

Disadvantages of SCAN

1. Long wait for some requests

The requests that come immediately after the head approached should wait until the head reverses the direction. This can cause delays, especially for requests near the edges of the disc.

2. Uneven response time

The scan provides better performance than FCF, but the response time may still vary. The requests close to the ends of the disc may experience long waiting time than near the center.

3. Ruined movement at ends

Even if there is no request on the extreme ends of the disc, the head still travels there in all ways before reversing. This may lead to unnecessary head movement and slightly less efficiency.

4. Real time is not ideal for systems

Due to the potential delay for some requests, scans are not the best option for real -time systems where consistent and immediate response time are important.

C-SCAN algorithm

C-scan (circular scan) algorithm scan is a variation of disc scheduling method. Like the scan, it moves the disc head to the service requests in one direction, but instead of reversing the direction at the end of the disc, it jumps back back and starts servicing in the same direction. This ensures that all requests are controlled in an uniform and cyclical manner, which provides more consistent response time.

The C-scan works by scanning from the current head position towards the end of the disc (usually up to the lowest cylinder), serves all pending requests on the way. Once the head reaches the final cylinder, it does not serve any request on the way back. Instead, it immediately returns to the start of the disc and starts scanning again in the same direction.

In C-SCAN algorithm, the arm of the disk moves in a particular direction servicing requests until it reaches the last cylinder, then it jumps to the last cylinder of the opposite direction without servicing any request then it turns back and start moving in that direction servicing the remaining requests.

This algorithm considers the disc as a circular list of cylinders, which helps maintain a uniform waiting time. The requests are always controlled in one direction, reducing the variation in the reaction time that can occur in the scan when the head is reversed.

The C-scan is particularly useful in a system with heavy discs, as it provides better fairness and more predicated performance, especially when the request queue is constantly changing. However, the return movement of the disc head adds in total search from end to beginning as it makes no request during that phase.

How C-SCAN Works?

The C-scan (circular scan) algorithm works equally to scan, but with a significant difference on how it handles the end of the disc. Instead of reversing the direction, when the head reaches the last track, the C-Scan Jumps back at the beginning of the disc and resumes servicing requests in the same original direction.

Initially, the head moves in a certain direction-usually from lower number of tracks from high numbers. As it travels, it serves all pending requests along its path. Once it reaches the highest track number, it does not serve any request on the return trip. Instead, the head quickly goes back to the lowest track without stopping for any request during this movement.

After returning in the beginning, the head begins another forward sweep, requesting in the same direction as before. This process continues like a loop or in a circular manner, which is why the algorithm is called a circular scan.

Always scanning in one direction, the C-scan ensures more uniform waiting time. Unlike the scan, which may be in favor of requests based on the direction of movement, the C-scan provides a more consistent and appropriate experience for all requests, whether they are on the disc.

Example

Consider the following disk request sequence for a disk with 100 tracks

98, 137, 122, 183, 14, 133, 65, 78

Head pointer starting at 54 and moving in left direction. Find the number of head movements in cylinders using C-SCAN scheduling.

No. of cylinders crossed = 40 + 14 + 199 + 16 + 46 + 4 + 11 + 24 + 20 + 13 = 387

Advantages of C-SCAN

1. Uniform waiting time

C-scan provides more consistent response time for all requests. Since the disc head always moves in one direction and considers the disc as circular, no part of the disc is favored on the other.

2. Impartiality

All requests are treated equally regardless of their position. Most of each request disk wait for a complete sweep, prevents starvation and reducing the response time imbalance.

3. Better for high load systems

I/o in the atmosphere with a high number of requests, the C-scan maintains efficiency by avoiding unnecessary boxing. Its one-way scanning pattern helps manage long queues more estimated.

4. Estimated performance

Because the head movement is always in the same direction, it is easy to guess when a request will be served. This prediction is useful for time-sensitive applications.

Disadvantages of C-SCAN

1. Wasted movement

One of the main shortcomings of the C-Scan is that the return movement from the end of the disc does not serve any request. This is the result in additional head movement that adds in total time.

2. Longer Average Seek Time

Compared to the scan, the C-scan can look for a little more average time as it always jumps back at the beginning, even if there are pending requests behind the position of the current head.

3. Not ideal for low load

In the system with a mild or uneven load of disc requests, the overhead to return to the beginning can overtake the same waiting time, making the C-scan less efficient.

4. Slightly more complex

Applying C-scan can be slightly more complicated than a scan, as it requires logic to handle circular jump and maintain a consistent sweep in only one direction.

SCAN vs. C-SCAN

1. Head movement

The scan moves the disc head forward in both directions while moving towards the end of the disc - the first time servicing requests, then reverses the requests of coming back on the way and servicing.

On the other hand, the C-scan takes the head in only one direction. After reaching the end, it jumps back to the beginning without serving any request during return.

2. Reaction time

Scan can give rise to uneven reaction time because the requests close to the ends of the disc may wait for a long time, especially after the head is reversed.

The C-scan provides more uniform waiting time, as all requests are treated in a circular and coherent manner, improving fairness.

3. Efficiency

The scan is slightly more efficient in terms of total head movement as it requests in both directions.

The C-scan can result in slightly more head movement due to unnatural return to start from the end, but it provides better prediction and fairness.

4. Use cases

The scan is well suited for systems where I/O requests are quite balanced and performing is more important than performance uniformity.

C-scan is preferred in high-load or time-sensitive systems where the approximate and fair response time is required.

5. Starvation

Both algorithms prevent starvation, but C-scan does a better job of ensuring frequent service for all requests regardless of their disc space.

Frequently Asked Questions

Q1: What is the main difference between scan and C-scan?

The main difference is towards the movement of the head. Scan services request in both directions (forward and reverse), while C-scan only requests services in one direction and jumps back to the beginning to resume.

Q2: Why is the scan called "elevator algorithm"?

The scan is named the "elevator algorithm" because the disc head goes beyond the disk like an elevator - serve services in both directions as it goes up and down.

Q3: Which algorithm provides more uniform waiting time?

The C-scan provides more uniform and predictable waiting time as it considers the disc as a circular list and always fulfills the requests of services in the same direction.

Q4: Can scan or C-scan cause starvation of any request?

No, both scans and C-scans are designed to prevent starvation. Each request will eventually be served as scanning continues in the head disc.

Q5: Which algorithm has a better average time?

The scan usually has a slightly better average time because it requests in both directions, reduces unnecessary head movement. However, the C-scan is better for fairness and prediction.