操作系统算法——磁盘调度——最短路径优先、电梯调度

原创
2013/12/19 12:22
阅读数 2.4K

输入文件格式为

第一行是n,fangfa. 其中n表示当前任务队列的长度,fangfa表示采用哪种方法进行磁盘调度

第二行是n个整数,每个整数范围为:0--255。表示当前的n个请求

第三行是m

第四行开始每行两个整数,time,qiu。表示在time时间的时候,请求了qiu。并且保证time呈递增。

例子:

9 2
150 160 184 90 58 55 39 38 18
2
300 64



程序代码:

#include <vector>
#include <fstream>
#include <iostream>
#include <cmath>
using namespace std;
#define CHUSHI 100
/*上面的两个是请求队列的最大长度,
和,之后最多新添加的队列长度 
*/
struct hou_add
{
	int time;
	int qiu;
	int zhuangtai;
};
/*
	用于保存还没有添加到request队列的节点
*/
vector<int>request;
vector<hou_add> tianjia;
int xuanze(int fangxiang,int fangfa,int citou){
	/*本函数功能是从dui中按照fangfa的方法进行选择
	下一个要访问的磁盘地址,并且返回它在dui中的下标
	参数约定:
	fangxiang=1时候当前磁头向右访问
	fangxiang=-1时候向左访问 
	fangfa=1是 最短寻道优先
	fangfa=2是 电梯调度算法 
	*/
	int i=0,tmp,jin=256,shan=0,hou=0,fan=256;

	vector<int>::iterator it;
	if (fangfa==1){
		/*这里是采用最近原则,只需要在任务队列中
		找一个最近的节点,返回它的下标 
		*/
		for (it=request.begin();it!=request.end();it++){
			if (abs(*it-citou)<jin) {
				shan=i;
				jin=abs(*it-citou);
			}
			i++;
		}
		return shan;
	}else
	{
		/*这里使用电梯调度算法,首先初始化citou运动的
		最大距离,
		如果在当前运行方向有比当前运行距离短的,就更新
		更短的节点
		如果遍历之后相同方向没有比最大距离更短的,说明
		当前citou为边缘,就只找与现在磁头最短的就可以了 
		*/ 
		jin=256;
		for (it=request.begin();it!=request.end();it++){
			tmp=(*it-citou)*fangxiang;
			if (tmp>0){
			//tmp为正,说明当前方向有节点
				if (abs(*it-citou)<jin) {
					shan=i;
					jin=abs(*it-citou);
				}
			}
				else if (abs(*it-citou)<fan){
					hou=i;
					fan=abs(*it-citou);
				}
			i++;
			
		}
		if (jin<256)
		return shan;
		else return hou;
	}
}

int main(int argc,char * argv[]){
	ifstream cin("aaa.txt");   /*这里对于cin进行重定向
	输入数据直接使用cin进行数据输入 
	*/
	vector<int> alljuli;
	int tmp,n,m,shanchu,i,juli,fangfa,fangxiang=1;
	int usetime=0; //当前使用的时间 
	struct hou_add tt;
	tt.zhuangtai=1;
	int citou=CHUSHI;
	bool kong=false;
	//方向为1,向右 
	cin>>n>>fangfa;
	//读取requst,fangfa是调度算法的选择 1为最短调度 
	for (i=0;i<n;i++){
		cin>>tmp;
		request.push_back(tmp);
	}
	cin>>m;
	for (i=0;i<m;i++){
		cin>>tt.time>>tt.qiu;
		tianjia.push_back(tt);
	}
	for (vector<int>::iterator it=request.begin();it!=request.end();it++)
	    cout<<"request:	"<<*it<<endl;
	    cout<<endl;
	for (vector<hou_add>::iterator it2=tianjia.begin();it2!=tianjia.end();it2++)
	    cout<<"tianjia:	"<<(*it2).time<<"	"<<(*it2).qiu<<endl;
	while(!(request.empty() &&  kong)){
		/*当两个队列有不全为空时*/
		if (request.empty()){
			/*如果进入到这里说明当前
			请求队列已经空了,但是后续还有,
			所以此时的工作是从tianjia中读取任务
			添加到request中 
			*/
			int tmtime;
			vector<hou_add>::iterator it=tianjia.begin();	
			while (!(*it).zhuangtai) it++;	
			if (it!=tianjia.end()){
				request.push_back((*it).qiu);
if (usetime<(*it).time)  //这里应该进行判断。否则可能出现time比usetime小的情况。
				usetime=(*it).time;
				(*it).zhuangtai=0;
			}else kong=true;
		}
		vector<hou_add>::iterator it4=tianjia.begin();
		while (it4!=tianjia.end())
		{
			if ((*it4).zhuangtai && (*it4).time<=usetime){
				cout<<"tianjia  shanchu:  "<<(*it4).qiu<<endl;
				request.push_back((*it4).qiu);
				(*it4).zhuangtai=0;
			}
			it4++;
		}

		/*当程序运行到这里的时候request肯定不为空
		此时要做的工作时,从request中选择一个任务
		完成它,并且删除requst中的任务,计算后续内容
		最后计算时间,从tianjia中加入合适的任务添加到requst中 
		*/
		if (request.empty()) break;
		shanchu=xuanze(fangxiang,fangfa,citou);
			//最短路径优先
		juli=citou-request[shanchu];
		alljuli.push_back(abs(juli));
		usetime=usetime+abs(juli); //默认速度为1,计算当前时间
		citou=request[shanchu];  //更改磁头位置 
		request.erase(request.begin()+shanchu);  //删除requst中节点
		if (fangfa==2){
		//当时电梯调度算法时还需要处理
			if (juli>0) fangxiang=-1;
			else fangxiang=1;
		}
		cout<<juli<<" "<<usetime<<" "<<citou<<endl;
	}
	return 0;
}



应该说算法是很多简单的。一些处理比较麻烦

展开阅读全文
加载中

作者的其它热门文章

打赏
0
2 收藏
分享
打赏
0 评论
2 收藏
0
分享
返回顶部
顶部