@TOC

操作系统的任务之一就是有效地使用硬件。


对磁盘驱动器，满足这一要求意味着要有较快的访问速度和较宽的磁盘宽带。


磁盘宽带是指所传递的总字节数除以从服务请求开始到最后传递结束时的总时间。

访问时间有寻道时间和旋转延迟两个主要部分。

• 寻道时间是磁臂将磁头移动到包含目标扇区的柱面的时间。
• 旋转延迟是磁盘需要将目标扇区转动到磁头下的时间。
  通常，最小寻道时间可以用最短寻道距离来表示。

一、最常用的磁盘调度算法

1)先来先服务（FCFS）算法：根据进程请求访问磁盘的先后次序进行调度。算法的实现简单、公平；缺点：效率不高，相临两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利。

2)最短寻道时间优先（SSTF）算法：优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先。优点：改善了磁盘平均服务时间；缺点：造成某些访问请求长期等待得不到服务。

3)扫描（SCAN）算法：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向。

4)循环扫描（C-SCAN）算法：总是从0号柱面开始向里扫描，按照各自所要访问的柱面位置的次序去选择访问者，移动臂到达最后一个柱面后，立即带动读写磁头快速返回到最小的需要访问的柱面，返回时不为任何的等待访问者服务，返回后可再次进行扫描。

二、调度算法的选择原则

1）SSTF较为普遍且很有吸引力。
2）SCAN和C-SCAN对磁盘负荷较大的系统会执行得更好，这是因为它不可能产生饥饿问题。
3）对于任何调度算法，性能依赖于请求的类型和数量。
4）磁盘服务请求很大程度上收文件分配方法所影响。
5）磁盘调度算法应作为一个操作系统的独立模块。因为，如果有必要，可以方便替换成另外一种不同的算法。
6）SSTF或SCAN是比较合理地默认算法。

三、实验问题及实现

1．现有8个进程先后提出的磁盘I/O请求 ：98 138 37 122 14 124 65 67，当前磁头位置为53号磁道，磁头向内移动。分别采用FCFS算法、SSTF算法、SCAN算法以及C-SCAN算法，画出磁头移动的轨迹，计算平均寻道长度。




2．打开“Microsoft Visual C++ 6.0”，输入相关代码，对程序行进编译运行。在与源程序在同一目录下新建一个“cidao.txt”文件，内容为上述8个进程先后提出的磁盘I/O请求 ：98 138 37 122 14 124 65 67。

运行界面如下：

下面我们根据提示信息分别测试三种算法的最短寻道时间（假设当前磁头位置为53号磁道，磁头向内移动）：

1）FCFS算法的测试结果是：

2)SSTF算法的测试结果是：

3)SCAN算法的测试结果是：

4．试模仿SCAN算法部分代码，在程序中再添加C-SCAN算法的实现，并对该算法进行测试。
（1）所添加的C-SCAN算法的代码：

#include<iostream>
#include<cmath>
using namespace std;
#define maxsize 100
//电梯调度算法
void CSCAN(int array[],int m){
	int sum=0,index=0,now,order;
	cout<<"请输入当前的的磁道号:";
	cin>>now;
	cout<<endl<<"请输入磁头移动的方向（0向左，1向右）";
	cin>>order;
	int arr[m];//新建一个arr数组复制array的所有元素 
	//先进行选择排序，元将素由大到小排列
	for(int i=0;i<m;i++){
		arr[i]=array[i];
	}
	for(int i=0;i<m;i++){ 
		int k=i;
		for(int j=i;j<m;j++){
			if(arr[j]<arr[k]){
				k=j;
			}
		}
		int temp=arr[i];
		arr[i]=arr[k];
		arr[k]=temp;
	} 
//	for(int i=0;i<m;i++){
//		cout<<array[i]<<"";
//	}
	//找到距离最近的磁道下标index,肯定与now相邻 
	int min=abs(now-arr[0]);
	for (int i=0;i<m;i++){
		if(abs(now-arr[i])<min){
			min=abs(now-arr[i]);
			index=i;
		}
	} 
	int left,right;
	if(arr[index]>now){
		right=index;
		left=index-1;
	}else{
		left=index;
		right=index+1;
	}
	cout<<endl<<"访问的磁道顺序为：";//换行 
	if(order==0){
		sum+=abs(now-arr[left]);
		for(int i=left;i>=0;i--){
			cout<<arr[i]<<" ";
		}
		//直接移动到最右端，然后才继续向左处理 
		for(int i=m-1;i>=right;i--){
			cout<<arr[i]<<" ";
		}
		sum+=abs(arr[left]-arr[0])+abs(arr[m-1]-arr[0])+abs(arr[m-1]-arr[right]);
	}else if(order==1){
		sum+=abs(now-arr[right]);
		for(int i=right;i<m;i++){
			cout<<arr[i]<<" ";
		}
	    for(int i=0;i<=left;i++){
			cout<<arr[i]<<" ";
		}
		sum+=abs(arr[m-1]-arr[right])+abs(arr[m-1]-arr[0])+abs(arr[left]-arr[0]);	
	}else{
		cout<<"输入磁头移动的方向有误"<<endl;
	}
	
	cout<<"移动的总道数: "<<sum<<endl;
}
int main(){
	FILE *fp;
	int cidao[maxsize];
	int i=0,count;
	fp=fopen("cidao.txt","r+");
	if(fp==NULL){
		cout<<"文件打不开!"<<endl;
		exit(0);
	}
	while(!feof(fp)){
		fscanf(fp,"%d",&cidao[i]);
		i++;
	}
	count=i;
	//count就是文件中待访问的磁道数 
	cout<<"磁盘I/O请求序列为：";
	for(i=0;i<count;i++){
		cout<<cidao[i]<<" ";
	}
	cout<<endl;
	while(1){
		cout<<"————————CSCAN算法系统————————"<<endl;
		CSCAN(cidao,count);
	}
	return 0;
}

（2）C-SCAN算法的测试结果是：

完整源代码如下：

#include<iostream>
#include<cmath> 
#include<vector>
using namespace std;
#define maxsize 100

//先来先服务调度算法
void FCFS(int array[],int m){
	int sum=0,i,now;
	cout<<"请输入当前的的磁道号:";
	cin>>now;
	cout<<endl<<"访问的磁道顺序为：";//换行 
	for(i=0;i<m;i++){
		cout<<array[i]<<' ';
		//计算访问每个磁道的绝对值 
		sum+=abs(now-array[i]);
		//更新当前磁道 
		now=array[i];
	}
	cout<<"移动的总道数: "<<sum<<endl;
}
//最短距离优先调度算法
void SSTF(int array[],int m){
	int sum=0,now;
	cout<<"请输入当前的的磁道号:";
	cin>>now;

	//定义进行操作的变长数组dic
	vector<int> dic;
	//定义保存数据的变长数组data 
	vector<int> data; 
	for(int i=0;i<m;i++){
		dic.push_back(array[i]);
	}
	//有多少磁道号执行多少次
	for(int i=0;i<m;i++){
		//先默认最短距离是now到第一个磁道
		int min=abs(now-dic[0]),index=0; 
		for(int j=0;j<dic.size();j++){
			if(abs(dic[j]-now)<min){
				//更新当前最短距离和下标 
				min=abs(dic[j]-now);
				index=j;
			}	
		} 
		sum+=min;//加上每次的移动距离 
		data.push_back(dic[index]);
		now=dic[index];
		dic.erase(dic.begin()+index);
		
	}
	cout<<endl<<"访问的磁道顺序为：";//换行 
	for(int i=0;i<data.size();i++){
		cout<<data[i]<<" ";
	}
	cout<<"移动的总道数: "<<sum<<endl;
}
//电梯调度算法
void SCAN(int array[],int m){
	int sum=0,index=0,now,order;
	cout<<"请输入当前的的磁道号:";
	cin>>now;
	cout<<endl<<"请输入磁头移动的方向（0向左，1向右）";
	cin>>order;
	int arr[m];//新建一个arr数组复制array的所有元素 
	//先进行选择排序，元将素由大到小排列
	for(int i=0;i<m;i++){
		arr[i]=array[i];
	}
	for(int i=0;i<m;i++){ 
		int k=i;
		for(int j=i;j<m;j++){
			if(arr[j]<arr[k]){
				k=j;
			}
		}
		int temp=arr[i];
		arr[i]=arr[k];
		arr[k]=temp;
	} 
//	for(int i=0;i<m;i++){
//		cout<<array[i]<<"";
//	}
	//找到距离最近的磁道下标index,肯定与now相邻 
	int min=abs(now-arr[0]);
	for (int i=0;i<m;i++){
		if(abs(now-arr[i])<min){
			min=abs(now-arr[i]);
			index=i;
		}
	} 
	int left,right;
	if(arr[index]>now){
		right=index;
		left=index-1;
	}else{
		left=index;
		right=index+1;
	}
	cout<<endl<<"访问的磁道顺序为：";//换行 
	if(order==0){
		sum+=abs(now-arr[left]);
		for(int i=left;i>=0;i--){
			cout<<arr[i]<<" ";
		}
		for(int i=right;i<m;i++){
			cout<<arr[i]<<" ";
		}
		sum+=abs(arr[m-1]-arr[0])+abs(arr[left]-arr[0]);
	}else if(order==1){
		sum+=abs(now-arr[right]);
		for(int i=right;i<m;i++){
			cout<<arr[i]<<" ";
		}
	    for(int i=left;i>=0;i--){
			cout<<arr[i]<<" ";
		}
		sum+=abs(arr[m-1]-arr[right])+abs(arr[m-1]-arr[0]);	
	}else{
		cout<<"输入磁头移动的方向有误"<<endl;
	}
	
	cout<<"移动的总道数: "<<sum<<endl;
}
int main(){
	int c,i=0,count;
	FILE *fp;
	int cidao[maxsize];
	fp=fopen("cidao.txt","r+");
	if(fp==NULL){
		cout<<"文件打不开!"<<endl;
		exit(0);
	}
	while(!feof(fp)){
		fscanf(fp,"%d",&cidao[i]);
		i++;
	}
	//count就是文件中待访问的磁道数 
	cout<<"磁盘I/O请求序列为：";
	count=i;
	for(i=0;i<count;i++){
		cout<<cidao[i]<<" ";
	}
	cout<<endl;
	while(1){
		cout<<endl<<"系统的菜单如下："<<endl;
		cout<<"1.先来先服务 2.最短寻道时间优先 \n3.电梯调度   4.退出"<<endl;
		cout<<"请选择服务：";
		cin>>c;
		if(c>3)
			break;
		switch(c){
			case 1:
				FCFS(cidao,count);
				break;
			case 2:
				SSTF(cidao,count);
				break;
			case 3:
				SCAN(cidao,count);
				break;
		}
	}
	return 0;
}