操作系统磁盘调度算法(c++)

先来先服务这个没什么好说了，按顺序来就是了。将需要访问的磁道序列直接作为算法的访问序列，然后将每次移动的磁道数量记录下来。

最短寻道时间优先，每次执行完，看一下离自己最近的哪条磁道有任务，就移动过去执行。每次寻找下一次访问的磁道号时，都遍历磁道序列，找到最近的磁道，记下此磁道在磁道序列的位置，并换到前面(假设第i次寻找就换到i-1号)，循环直到算法访问序列全部算出。然后依照访问序列记录每次移动的磁道数量。

scan，扫描算法也叫电梯算法，从当前位置开始，指定某个方向移动，移动到该方向所有任务都执行完毕，调换反向继续搜索。将磁道序列升序排序，找到第一个磁道号大于等于当前磁道号的位置 pos，作为下一次访问的磁道。从该磁道往后将所有磁道遍历，然后从这里开始，继续往前遍历直到全部磁道都访问完。

cscan，循环扫描算法，和scan的区别在于往一个方向扫描完后，回到另一端的开始任务，继续循环。

先来先服务算法最简单，每个进程按到达时间先后进行服务，不会出现进程长时间等待，但是平均寻道的距离较长。最短寻道时间优先算法保证每一次找到移动距离最短的磁道开始服务，但是不能保证平均寻道时间最短，效率比先来先服务高。扫描算法即能获得较好的性能，也避免”饥饿”现象发生，但是需要先将磁道需要访问的序列进行排序，空间消耗较大。如果采用循环scan，例如scan向高磁道方向扫描完成后，回到最低的访问任务所在磁道，然后继续向高磁道方向扫描，那么可以使每一条磁道的平均访问比较均匀，而普通scan算法在靠近两端的磁道上的寻道时间有可能很长，虽然平均寻道时间更短

代码示例如下

#include<iostream>
#include<conio.h>
using namespace std;

#define TRACK_NUM  12	  //io时需要访问的磁道数量

int TRACK_SEQUENCE[TRACK_NUM] ;    //存放磁道访问序列的数组
int CURRENT_TRACK;             //当前磁头所在的磁道号
int move_num[TRACK_NUM];       //记录每次移动的磁道数
int FCFS_MOVE_SEQUENCE[TRACK_NUM];    //存放先来先服务算法的磁道访问序列
int SSTF_MOVE_SEQUENCE[TRACK_NUM];    //存放最短寻道时间优先算法的磁道访问序列
int SCAN_MOVE_SEQUENCE[TRACK_NUM];	//存放扫描算法的磁道访问序列
int CSCAN_MOVE_SEQUENCE[TRACK_NUM];	//存放循环扫描算法的磁道访问序列
int ASC_SEQUENCE[TRACK_NUM];        //存放磁道序列的升序排序结果

void init_move_sequence()
{
	for (int i = 0; i < TRACK_NUM; i++)
	{
		FCFS_MOVE_SEQUENCE[i] = TRACK_SEQUENCE[i];
		SSTF_MOVE_SEQUENCE[i] = TRACK_SEQUENCE[i];
		ASC_SEQUENCE[i] = TRACK_SEQUENCE[i];
	}
	
}

void input()
{
	TRACK_SEQUENCE[0] = 23;
	TRACK_SEQUENCE[1] = 376;
	TRACK_SEQUENCE[2] = 205;
	TRACK_SEQUENCE[3] = 132;
	TRACK_SEQUENCE[4] = 19;
	TRACK_SEQUENCE[5] = 61;
	TRACK_SEQUENCE[6] = 190;
	TRACK_SEQUENCE[7] = 398;
	TRACK_SEQUENCE[8] = 29;
	TRACK_SEQUENCE[9] = 4;
	TRACK_SEQUENCE[10] = 18;
	TRACK_SEQUENCE[11] = 40;
	

	CURRENT_TRACK = 100;

	init_move_sequence();
}

void show_result(int* move_sequence)
{
	int i,sum_move_num = 0;

	cout << "\n\n\n该算法的磁道访问序列为: ";
	for (i = 0; i < TRACK_NUM; i++)
		cout << move_sequence[i] << " ";

	cout << "\n每次移动的磁道数为: ";
	for (i = 0; i < TRACK_NUM; i++)
	{
		sum_move_num += move_num[i];
		cout << move_num[i] << " ";
	}

	cout << "\n平均寻道长度为: " << 1.0 * sum_move_num / TRACK_NUM;
	cout << "\n\n 请按任意键继续" << endl;
	_getch();
}

void FCFS()   //先来先服务
{
	int current_track = CURRENT_TRACK;
	for (int i = 0; i < TRACK_NUM; i++)
	{
		move_num[i] = abs(current_track - FCFS_MOVE_SEQUENCE[i]);
		current_track = FCFS_MOVE_SEQUENCE[i];
	}
	show_result(FCFS_MOVE_SEQUENCE);   //显示运行结果
}

void SSTF()   //最短寻道时间优先
{
	int current_track = CURRENT_TRACK;
	int next,temp,i,j;

	for (i = 0; i < TRACK_NUM-1; i++)   //每次选取最短距离的磁道形成寻道序列
	{
		next = i;
		for (j = i+1; j < TRACK_NUM; j++)
		{
			if (abs(current_track - SSTF_MOVE_SEQUENCE[next]) >
				abs(current_track - SSTF_MOVE_SEQUENCE[j]))
			{
				next = j;
			}
		}
		if (next != i)
		{
			temp = SSTF_MOVE_SEQUENCE[next];
			SSTF_MOVE_SEQUENCE[next] = SSTF_MOVE_SEQUENCE[i];
			SSTF_MOVE_SEQUENCE[i] = temp;
		}
		move_num[i] = abs(current_track - SSTF_MOVE_SEQUENCE[i]);
		current_track = SSTF_MOVE_SEQUENCE[i];

	}
	move_num[i] = abs(current_track - SSTF_MOVE_SEQUENCE[i]);
	
	show_result(SSTF_MOVE_SEQUENCE);   //显示运行结果
}

void sort()   //升序排序
{
	int temp;
	for (int i = 1; i < TRACK_NUM; i++)
	{
		for (int j = 0; j < TRACK_NUM - i; j++)
		{
			if (ASC_SEQUENCE[j] > ASC_SEQUENCE[j + 1])
			{
				temp = ASC_SEQUENCE[j];
				ASC_SEQUENCE[j] = ASC_SEQUENCE[j + 1];
				ASC_SEQUENCE[j + 1] = temp;
			}
		}
	}
}

void CSCAN()    //循环扫描算法（先往磁道号增加方向扫描）
{
	sort();   //磁道号按升序排序
	int i,j,pos=0;

	int current_track = CURRENT_TRACK;

	while (1)      //找到下一个要访问的磁道在数组中的序号
	{
		if (ASC_SEQUENCE[pos] >= current_track)
			break;
		pos++;
	}
	for (i = 0,j=pos; i < TRACK_NUM - pos; i++)
	{
		CSCAN_MOVE_SEQUENCE[i] = ASC_SEQUENCE[j++ ];
		move_num[i] = abs(current_track - CSCAN_MOVE_SEQUENCE[i]);
		current_track = CSCAN_MOVE_SEQUENCE[i];
	}
	for (j = 0; i < TRACK_NUM; i++)
	{
		CSCAN_MOVE_SEQUENCE[i] = ASC_SEQUENCE[j++];
		move_num[i] = abs(current_track - CSCAN_MOVE_SEQUENCE[i]);
		current_track = CSCAN_MOVE_SEQUENCE[i];
	}

	show_result(CSCAN_MOVE_SEQUENCE);
}

void SCAN()    //扫描算法（往磁道号增加方向扫描）
{
	sort();   //磁道号按升序排序
	int i, j, pos = 0;

	int current_track = CURRENT_TRACK;

	while (1)      //找到下一个要访问的磁道在数组中的序号
	{
		if (ASC_SEQUENCE[pos] >= current_track)
			break;
		pos++;
	}
	for (i = 0, j = pos; i < TRACK_NUM - pos; i++)
	{
		SCAN_MOVE_SEQUENCE[i] = ASC_SEQUENCE[j++];
		move_num[i] = abs(current_track - SCAN_MOVE_SEQUENCE[i]);
		current_track = SCAN_MOVE_SEQUENCE[i];
	}
	for (j = pos - 1; i < TRACK_NUM; i++)
	{
		SCAN_MOVE_SEQUENCE[i] = ASC_SEQUENCE[j--];
		move_num[i] = abs(current_track - SCAN_MOVE_SEQUENCE[i]);
		current_track = SCAN_MOVE_SEQUENCE[i];
	}

	show_result(SCAN_MOVE_SEQUENCE);
}

void show_message()
{
	cout << "io时需要访问的磁道数量为 : " << TRACK_NUM;
	cout << "\n需要访问的磁道序列为 : ";
	for (int i= 0; i < TRACK_NUM; i++)
		cout << TRACK_SEQUENCE[i] << " ";

	cout << "\n当前磁头所在的磁道号为 : " << CURRENT_TRACK;
	
}

void menu()
{
	char choice;
	while (1)
	{
		system("cls");
		show_message();
		cout << "\n\n\n请选择磁盘调度算法 :" << endl;
		cout << "\t1.先来先服务算法" << endl;
		cout << "\t2.最短寻道时间优先算法" << endl;
		cout << "\t3.扫描算法" << endl;
		cout << "\t4.循环扫描算法" << endl;
		cout << "\t5.离开 " << endl;

		choice = _getch();
		switch (choice) 
		{
			case '1' :
				FCFS();
				break;
			case '2' :
				SSTF();
				break;
			case '3' :
				SCAN();
				break;
			case '4':
				CSCAN();
				break;
			case '5' :
				exit(0);
			default :
			{
				cout << "\n\n输入有误，请按任意键继续" << endl;
				_getch();
			}
		}
	}
	

}

int main()
{
	input();
	menu();
	return 0;

}

当前情况如下

先来先服务

最短寻道时间优先

scan算法

cscan算法

文章出处登录后可见！

已经登录？立即刷新

操作系统磁盘调度算法(c++)

相关推荐