Disk scheduling

catalogue

1, Experiment content

2, Experimental purpose

3, Experimental principle

IV code implementation

V experimental result

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);
}

V experimental result