Disk scheduling
catalogue
1, Experiment content
Simulation of elevator scheduling algorithm to achieve disk scheduling.
2, Experimental purpose
Disk is a high-speed, large number of rotating, directly accessible storage device. As the auxiliary memory of the computer system, it bears heavy input and output tasks. In the multi-channel programming system, there are often several input and output requests for access to the disk waiting to be processed. The system can adopt a strategy to execute the input and output requests that require access to the disk in the best order. This is called disk scheduling. The algorithm used is called disk scheduling algorithm. Disk scheduling can reduce the total time required to service several I / O requests, thereby improving system efficiency. This experiment requires students to simulate the design of a disk scheduler and observe the dynamic running process of the disk scheduler.
3, Experimental principle
Simulation of elevator scheduling algorithm, disk scheduling.
Disk is a storage device to be shared by multiple processes, but a disk can only serve one process at a time.
When a process accesses a disk, other processes that want to access the disk must wait until the disk finishes working.
When multiple processes put forward input and output requests and are in a waiting state, the elevator scheduling algorithm can be used to select a process from several waiting visitors and let it access the disk. When the access arm only needs to move to the requested cylinder farthest in one direction, if there is no access request, the access arm will change the direction.
Assuming that the disk has 200 tracks, use the C language random function to randomly generate a track request sequence (no less than 15) and put it into the simulated disk request queue. Assume that the current head is on Track 100 and moves in the direction of increasing the track number. Please give the order of satisfying the requests when scheduling the disk according to the elevator scheduling algorithm, and calculate their average seek length.
IV code implementation
#include<stdio.h> #include<time.h> #pragma warning(disable: 4996) void TraReq(int* arr,int size) { srand(time(NULL)); for (int i = 0; i < size; ++i) { arr[i] = rand() % 201; } } int Max(int* arr, int size) { int max = arr[0]; for (int i = 1; i < size; ++i) { max = max > arr[i] ? max : arr[i]; } return max; } int Min(int* arr, int size) { int min = arr[0]; for (int i = 1; i < size; ++i) { min = min > arr[i] ? arr[i] : min; } return min; } int print(int* arr, int size) { printf("The track number in the track request sequence is:>\n"); for (int i = 1; i < size + 1; ++i) { printf("%4d ", arr[i - 1]); if (i % 5 == 0) { printf("\n"); } } return 0; } void Init(int* pos) { printf("Please enter the initial position of the head:> "); scanf("%d", pos); } //sort int sort(int* arr, int size) { for (int i = 0; i < size - 1; ++i) { for (int j = (i + 1); j < size; ++j) { if (arr[i] > arr[j]) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } return 0; } int func(int* arr, int size, int (*pfun)(int*, int)) { return (*pfun)(arr, size); } int SimulateAllocation(int* arr, int size,int pos, int max, int min) { //First, the elements of the track application sequence are sorted according to the size of their own track number func(arr, size, sort); //Track number subscript with track number greater than initialization position found in track request sequence int index = 0; for (int i = 0; i < size; ++i) { if (arr[i] >= pos && arr[i - 1] < pos) { index = i; break; } } //Analog seek process 1 (the head moves in the direction of track number increase) int order = 1; for (int i = index; i < size; ++i) { printf("Section%2d The track numbers of the accessed tracks are:> %d\n", order++, arr[i]); } //Analog seek process 2 (when the magnetic head has reached the maximum track number, the magnetic head moves in the direction of decreasing the track number) for (int i = index - 1; i >= 0; --i) { printf("Section%2d The track numbers of the accessed tracks are:> %d\n", order++, arr[i]); } //Calculate average seek length int avg =(max - pos + (max - min))/size; return avg; } void main() { //Create track request sequence int TrackRequest[20];//Generate 20 track requests at the same time int size = sizeof(TrackRequest) / sizeof(TrackRequest[0]); //Assign a value to a track request TraReq(TrackRequest, size); //Obtain the maximum value in both directions of the track request sequence at this time int max = func(TrackRequest, size, Max); int min = func(TrackRequest, size, Min); //Print the track number of the track request column at this time func(TrackRequest, size, print); //Simulated elevator scheduling algorithm //Initialize head position int pos; Init(&pos); //Perform disk simulation scheduling and calculate the average seek length at the same time int avg = SimulateAllocation(TrackRequest, size, pos, max, min); printf("The average seek length for this process is:> %d", avg); }