Operating System Experiment 4: Disk Scheduling (simulate various disk scheduling algorithms)
Download: https://download.csdn.net/download/fufuyfu/85511492?spm=1001.2014.3001.5503
1. Experimental content
Understand the basic algorithm and performance of disk scheduling
2. Experimental requirements
A series of disk requests (10) are generated by the system, respectively giving the first-come-first-served algorithm, the shortest seek time priority algorithm, the scanning (SCAN) algorithm and the cyclic scanning (CSCAN) algorithm when the head moves and calculates the average moving track of the head number. (Assume the head just moved from track 80 to track 100)
3. Algorithm process
3.1 Header files and data structures
#include <stdio.h> #include <stdlib.h> #define START 100 // Disk range [0,end] int end; // Storage randomly generates 10 track requests int request[15]; // Store the head movement order of each algorithm int order[15]; // Flags -- visited: 1, not visited: 0, all 0 at this time int sign[15]; // Track distance int dis[15];
3.2 Function declaration
// function declaration // menu void menu(); // Randomly generate 10 track requests void create(); // First come first serve algorithm void FCFS(); // shortest seek time first algorithm void SSTF(); // Scanning algorithm void SCAN(); // Cyclic Scanning Algorithm void CSCAN(); // Determine the direction of head movement int direction(); // Demonstrate algorithmic seek order and average number of moving tracks void show();
3.3 Main function
int main(){
printf("\n ---------------------The current track of the head:%d---------------------\n",START);
// Randomly generate 10 track requests
create();
// menu
menu();
}
3.4 Randomly generate 10 track requests
// Randomly generate 10 track requests
void create(){
// Generate disk seek range
printf("\n\t The disk seek range starts from 0 and cannot exceed 200");
printf("\n\t Since the current head is at 100, the disk seek range should be greater than or equal to 100");
printf("\n\t Please enter the disk seek range for symbolic conditions:");
// int end;
scanf("%d",&end);
while(end < 100 || end > 200){
printf("\n\t The disk seek range you entered does not meet the criteria");
printf("\n\t Please re-enter the disk seek range for the symbol condition:");
scanf("%d",&end);
}
printf("\n\t The disk seek range is determined successfully!\n");
// Randomly generate 10 track requests
for(int i = 1;i <= 10;++i){
request[i] = rand()%(end+1);
// Exclude generating duplicate track requests
for(int j = i-1;j >= 1;--j){
if(request[i] == request[j]){
--i;
break;
}
}
}
printf("\n\t 10 track requests have been randomly generated!\n\n");
printf("\t Track request:");
for(int i = 1;i <= 10;++i){
printf("%d ",request[i]);
}
printf("\n\n----------------------------------------------------------------\n");
}
3.5 Menu
// menu
void menu(){
while(true){
printf("\n\t Please choose which disk scheduling algorithm to use:\n\n");
printf("\t\t1.First come first serve algorithm(FCFS)\n");
printf("\t\t2.Short seek time priority algorithm(SSTF)\n");
printf("\t\t3.Scanning algorithm(SCAN)\n");
printf("\t\t4.Cyclic Scanning Algorithm(CSCAN)\n");
printf("\t\t5.quit\n\n");
printf("\t Please enter a valid action number:");
int option;
scanf("%d",&option);
printf("\n");
// Perform corresponding operations according to the input operation number
switch(option){
case 1:
// First come first serve algorithm
FCFS();
show();
break;
case 2:
// shortest seek time first algorithm
SSTF();
show();
break;
case 3:
// Scanning algorithm
SCAN();
show();
break;
case 4:
// Cyclic Scanning Algorithm
CSCAN();
show();
break;
case 5:
printf("---------------------------exit successfully!---------------------------\n");
return;
break;
default:
printf("-------------The operation number entered is incorrect, please enter a valid operation number!-------------\n");
break;
}
}
}
3.6 First Come First Served Algorithm
// First come first serve algorithm
void FCFS(){
// The request order of the tracks is the movement order of the heads
for(int i = 1;i <= 10;++i){
order[i] = request[i];
if(i == 1){
dis[i] = abs(START - request[i]);
}else{
dis[i] = abs(request[i-1] - request[i]);
}
}
}
3.7 Shortest Seek Time First Algorithm
// shortest seek time first algorithm
void SSTF(){
// Locate the subscript to which the current track belongs
int nowIndex = 0;
// Locate the subscript to which the next track belongs
int nextIndex = 1;
// Store the shortest distance
int s;
// Find the track corresponding to the shortest distance between the current track and the next track
for(int i = 1;i <= 10;++i){
s = 200;
if(i == 1){
for(int j = 1;j <= 10;++j){
// When the distance from the starting head to the track is less than the minimum distance
if(abs(START - request[j]) < s){
s = abs(START - request[j]);
nextIndex = j;
}
}
}else{
for(int j = 1;j <= 10;++j){
// When the track has not been accessed and the distance of the current head to the track is less than the minimum distance
if(sign[j] == 0 && abs(request[nowIndex]-request[j]) < s){
s = abs(request[nowIndex] - request[j]);
nextIndex = j;
}
}
}
// Update track access order array
order[i] = request[nextIndex];
// update distance array
dis[i] = s;
// set the track as visited
sign[nextIndex] = 1;
// moving head
nowIndex = nextIndex;
}
}
3.8 Scanning Algorithm
// Scanning algorithm
void SCAN(){
// The head moves back and forth on the disk, starting from the START from the outside to the inside
// the track where the head starts
int start;
// Determine where to change the order array
int index = 1;
// The head moves from outside to inside, starting from 80 to 100
// The inside of the track is large and the outside is small, and the outermost is track 0
for(start = START;start <= end;++start){
// Iterate over the request array
// All tracks of the requested array are compared each time
// If equal add it to the order array and change the tag
for(int i = 1;i <= 10 && index <= 10;i++){
if(request[i] == start && sign[i] == 0){
order[index] = request[i];
sign[i] = 1;
// update distance array
if(index == 1){
dis[index] = abs(START - order[index]);
}else{
dis[index] = abs(order[index-1] - order[index]);
}
if(start != end){
index++;
}
}
}
}
bool change = true;
// Head movement direction is changed from inside to outside
for(start = end;start >= 0;--start){
// Iterate over the request array
// All tracks of the requested array are compared each time
// If equal add it to the order array and change the tag
for(int i = 1;i <= 10 && index <= 10;i++){
if(request[i] == start && sign[i] == 0){
order[index] = request[i];
sign[i] = 1;
// update distance array
if(change){
dis[index] = 2*end - order[index-1] - order[index];
change = false;
}else{
dis[index] = abs(order[index-1] - order[index]);
}
index++;
}
}
}
}
3.9 Cyclic scanning algorithm
// Cyclic Scanning Algorithm
void CSCAN(){
// The head moves back and forth on the disk, starting from the START from the outside to the inside
// the track where the head starts
int start;
// Determine where to change the order array
int index = 1;
// The head moves from outside to inside, starting from 80 to 100
// The inside of the track is large and the outside is small, and the outermost is track 0
for(start = START;start <= end;++start){
// Iterate over the request array
// All tracks of the requested array are compared each time
// If equal add it to the order array and change the tag
for(int i = 1;i <= 10 && index <= 10;i++){
if(request[i] == start && sign[i] == 0){
order[index] = request[i];
sign[i] = 1;
// update distance array
if(index == 1){
dis[index] = abs(START - order[index]);
}else{
dis[index] = abs(order[index-1] - order[index]);
}
if(start != end){
index++;
}
}
}
}
bool change = true;
// The moving direction of the magnetic head is still from the outside to the inside, and the scanning is restarted from track 0
for(start = 0;start <= START - 1;++start){
// Iterate over the request array
// All tracks of the requested array are compared each time
// If equal add it to the order array and change the tag
for(int i = 1;i <= 10 && index <= 10;i++){
if(request[i] == start && sign[i] == 0){
order[index] = request[i];
sign[i] = 1;
// update distance array
if(change){
dis[index] = order[index];
change = false;
}else{
dis[index] = abs(order[index-1] - order[index]);
}
index++;
}
}
}
}
3.10 Demonstrate algorithm seek order and average number of moving tracks
// Demonstrate algorithmic seek order and average number of moving tracks
void show(){
// Total moving tracks
int sum_dis = 0;
printf("\t Beginning track:%d\n",START);
printf("\t next track accessed\t The distance the head needs to move\n");
for(int i = 1;i <= 10;++i){
printf("\t\t%4d\t\t",order[i]);
printf("%8d\n",dis[i]);
sum_dis += dis[i];
}
printf("\n\t The average number of moving tracks of the head under this disk scheduling algorithm:%0.2f\n\n",(float)sum_dis/10);
printf("----------------------------------------------------------------\n");
// Set the tag array to all 0
for(int i = 1;i <= 10;++i){
sign[i] = 0;
}
}
4. Experimental results
Code comments have been exhaustive, run the screenshots by yourself
5. Analysis
Through the above four disk scheduling algorithms to process the same group of randomly generated 10 track access requests and the comparison of the average number of moving tracks of the magnetic head under each algorithm, it can be seen that the four algorithms have their own advantages and disadvantages.
5.1 First Come First Served Algorithm (FCFS)
This algorithm is a relatively simple disk scheduling algorithm. It schedules according to the order in which processes request access to disk. The advantages of this algorithm are that it is fair and simple, and the requests of each process can be processed in turn, and there will be no situation where the requests of a certain process cannot be satisfied for a long time. However, since the algorithm is not optimized for seek, the average seek time may be longer when there are many access requests to the disk. In this experiment, the average number of moving tracks of the magnetic head under this algorithm is 47.70, which is much larger than the other three algorithms. But at the same time, the response time for each process to get service varies less.
5.2 Shortest Seek Time First Algorithm (SSTF)
The algorithm responds to the track access request according to the distance between the track required to be accessed and the track where the current head is located, so as to minimize the seek time each time. The algorithm can obtain better throughput, but it cannot guarantee the shortest average seek time. In this experiment, the average moving track number of the magnetic head under this algorithm is 23.90, which is far less than FCFS, but still larger than the better SCAN and CSCAN. The obvious disadvantage of this algorithm is that the response opportunities to the user's service request are not equal, resulting in a large variation of the response time. In the case of a large number of service requests, requests to the inner and outer edge tracks will be delayed indefinitely, and the response time of some requests will be unpredictable.
5.3 Scanning Algorithm (SCAN)
The scanning algorithm not only considers the distance between the track to be accessed and the current track, but also the current moving direction of the magnetic head. This algorithm basically overcomes the shortcomings that the service of the shortest seek time first algorithm is concentrated in the middle track and the response time varies greatly, but has the advantages of the shortest seek time first algorithm that the throughput is large and the average response time is small. In this experiment, the average number of moving tracks of the magnetic head under this algorithm is 19.8, which is indeed optimized. However, due to the wobble scanning method, the frequency of the access of the two tracks is still lower than that of the middle track.
5.4 Cyclic Scanning Algorithm (CSCAN)
The cyclic scan algorithm is an improvement on the scan algorithm. If the access requests to the tracks are evenly distributed, relatively few access requests fall behind the head when it reaches one end of the disk and moves in the opposite direction. This is because these tracks have just been processed, and the request density on the other end of the disk is quite high, and these access requests wait for a long time. In order to solve this situation, the circular scanning algorithm stipulates that the magnetic head moves in one direction to form a circular scan. The response efficiency is greatly improved. In this experiment, the average moving track number of the magnetic head under this algorithm is 12.70, which is the minimum value among the four algorithms, which shows the effectiveness of the algorithm.