The most crucial piece of software that runs on a computer is the operating system. It controls the memory, operations, software, and hardware of the computer. You can communicate with the computer using this method even if you don't understand its language. Without an operating system, a computer cannot function.
Before studying the C-Scan disk scheduling algorithm, we must know what the Disk Scheduling Algorithm is.
Disk Scheduling: The Operating System performs a Disc scheduling process to schedule I/O requests that arrive at the disc. Disc scheduling is important since-
Many I/O requests may arrive from different processes, and the disc controller can only serve one I/O request at a time. As a result, other I/O requests need to wait in the waiting queue and get scheduled.
The operating system needs to manage the hardware efficiently.
To reduce seek time.
In this article, we will study the C-SCAN Scheduling Algorithm.
What is C-SCAN Disk Scheduling Algorithm?
The C-scan is a disk scheduling algorithm that handles requests from the memory management unit. It takes into account the direction, moving either towards larger or smaller values. This method progresses towards the end of disk requests to fulfill them.
C-Scan (Circular Scan) disk scheduling algorithm is a variant of the SCAN scheduling algorithm designed to provide a more uniform wait time.
Note: The disc arm advances from one end of the disc to the other end in the Scan algorithm, completing requests as it hits each cylinder until it reaches the other end of the disc.
C-Scan operates similarly to Scan in which the head moves from one end of the disc to the other while responding to queries. However, without fulfilling any requests on the way back, the head returns to the start of the disc as soon as it reaches the other end. The cylinders are viewed by the C-Scan scheduling method as a circular list that wraps around from the last cylinder to the first.
To understand the C-Scan Algorithm, let us assume a disc queue with requests for I/O. ‘head’ is the initial position of the disk head. We will now apply the C-Scan algorithm-
Arrange all the I/O requests in ascending order.
The head will start moving in the right direction, i.e., from 0 to the size of the block.
As soon as a request is encountered, head movement is calculated as the current request - the previous request.
This process is repeated until the head reaches the end of the disk and the head movements are added.
As the end is reached, the head will go from right to left without processing any requests.
As the head reaches the beginning of the disc, i.e., 0, the head again starts moving in the right direction, and head movement keeps on adding.
This process is completed as soon as all the requests are processed, and we get total head movement.
The waiting period for the cylinders that the head has just visited is shorter than it would be with the Scan Algorithm.
It provides a better response time.
It provides a uniform waiting time.
Disadvantages of C-Scan Algorithm
The disadvantages of the C-Scan Algorithm are-
Even when there are no requests to be handled, it forces the head to move all the way to the end of the disc.
It causes more seek movements than the Scan Algorithm.
Example of C-Scan Algorithm
To understand more about C-Scan algorithms. We will consider various examples covering different aspects of the C-Scan Algorithm.
Example 1
Consider a disc queue with initial requests for Input/Ouput to blocks on cylinders with numbers 98, 183, 37, 122, 14, 124, 65, and 67. The head is initially at cylinder with the number 53, moving towards a larger number of cylinders. We will now use the C-Scan algorithm to serve these I/O requests.
Direction - towards the larger number of cylinders.
Output:
Arranging all the requests in ascending order, we get - { 14, 37, 65, 67, 98, 122, 124, 183 }.
The head starts moving in the right direction. So, the head will move from 53 (current position) and will stop at 65 (next request). Head movement = 65 - 53 = 12.
Then the head moves from 65 to 67, and head movement becomes 12 + (67 - 65) = 14.
Similarly, the head will go from 67 to 98, and head movement becomes 14 + (98 - 67) = 45.
Similarly, the head will go from 98 to 122 and head movement becomes 45 + (122 - 98) = 69.
Similarly, the head will go from 122 to 124, and head movement becomes 69 + (124 - 122) = 71.
Similarly, the head will go from 124 to 183, and head movement becomes 71 + (183 - 124) = 130.
Similarly, the head will go from 183 to 199 (end of the disc), and head movement becomes 130 + (199 - 183) = 146.
Now the head will go to 0 (beginning of disc) without serving any request. But the head movement will become 146 + (199 - 0) = 345.
Now, the head will go from 0 to 14 and head movement becomes 345 + (14 - 0) = 359.
Similarly, the head will go from 14 to 37, and head movement becomes 359 + (37 - 14) = 382.
Since 37 was the last request, the process will stop. We get the total head movement as 382.
The following chart shows the proper sequence in which requests are served using C-Scan.
Thus, the order in which requests are served is- 65, 67, 98, 122, 124, 183, 199, 0, 14, 37 with a total head movement of 382.
Now, let us consider one more example.
Example 2
Consider a disc queue with requests for I/O to blocks on cylinders 95, 180, 34, 119, 11, 123, 62, 64. The head is initially at cylinder number 50, moving towards a larger number of cylinders. We will now use the C-Scan algorithm to serve these I/O requests.
The following chart shows the proper sequence in which requests are served using C-Scan.
Thus, the order in which requests are served is- 62, 64, 95, 119, 123, 180, 199, 0, 11, 34, with a total head movement of 379.
Let us consider one more example.
Example 3
Consider a disc queue with requests for I/O to blocks on cylinders 19, 80, 134, 11, 110, 23, 162, 64. The head is initially at cylinder number 50, moving towards a larger number of cylinders. We will now use the C-Scan algorithm to serve these I/O requests.
Direction - towards the larger number of cylinders.
Output:
Arranging all the requests in ascending order, we get - { 11, 19, 23, 64, 80, 110, 134, 162 }.
The head will start moving from 50 and will process the requests in the right direction in the sequence - 64, 80, 110, 134, 162, 199 (end of the disc).
Now the head will go from 199 to 0 i.e., the end of the disc to the beginning of the disc.
Now the head will again process the requests in the right direction in the sequence - 0, 11, 19, 23.
The following chart shows the proper sequence in which requests are served using C-Scan.
Thus, the order in which requests are served is- 64, 80, 110, 134, 162, 199, 0, 11, 19, 23 with a total head movement of 371.
Implementation in C++
C++
C++
#include <iostream> #include <vector> #include <algorithm> using namespace std;
// Size of the disk const int size_disk = 200;
// C-SCAN algorithm void c_scan_algorithm(vector <int>& arr, int N, int initial){
// Sorting the inital array of requests sort(arr.begin(), arr.end());
// Stores the order in which requests are processed vector <int> order;
// Stores the total head movement int total = 0;
/* Extract the first request with a value greater Than or equal to the head and calculating the requests */ int fi = N, last = initial; for(int i = 0; i < N; i++){
if(arr[i] >= initial){
total += (arr[i] - last); order.push_back(arr[i]); last = arr[i]; } }
// Reaching the end of the disc total += (size_disk - last - 1); order.push_back(size_disk - 1);
// Reaching the starting of the disc total += (size_disk-1 - 0); order.push_back(0);
/* Extract the requests with a value less Than or equal to the head and calculate the requests */ last = 0; for(int i = 0; i < N; i++){
if(arr[i] < initial){
total += (arr[i] - last); order.push_back(arr[i]); last = arr[i]; } // Already processed requests else{ break; } }
// Printing the order of requests cout<<"The order in which requests are processed\n"; for(int i: order){ cout<<i<<" "; } cout<<"\n\n";
// Printing the total head movement cout<<"Total head movement = "<<total; }
Disk scheduling algorithm -SCAN (Circular SCAN) scans the disk in a circle, processing requests in one direction until the end, and then going back to the start.
What is ScanDisk scheduling in OS?
A disk's file system problems can be checked for and fixed using the utility application known as ScanDisk in the operating system. Improved data integrity is achieved by scanning the disk for defects and fixing them.
What is the difference between Scan and C-Scan Disk scheduling algorithms?
Scan scheduling algorithms serve requests in both directions while C-scan algorithms serve requests in one direction. Scan scheduling algorithms have longer waiting times while C-scan algorithms have uniform waiting times.
What is the difference between C-Scan and SSTF(Shortest seek time first) scheduling algorithms?
SSTF scheduling algorithms serve requests in both directions while C-scan algorithms serve requests in one direction. C-Scan algorithms never cause starvation, on the other hand, SSTF algorithms cause starvation.
Conclusion
The most crucial piece of software that runs on a computer is the operating system. It controls the memory, operations, software, and hardware of the computer. You can communicate with the computer using this method even if you don't understand its language. Without an operating system, a computer cannot function. The operating system is asked about in various interviews and is a very important topic from the placement point of view.
In this blog, we discussed the topic of the C-Scan Disk Scheduling Algorithm and various examples of it along with its advantages and disadvantages.
117+ registered 