操作系统课设报告磁盘
调度算法
公司内部编号:(GOOD-TMMT-MMUT-UUPTY-UUYY-DTTI-
课程设计报告课程名称: 操作系统课程设计
课题名称: 磁盘调度算法
学院: 软件学院
班级:
学生姓名:
学号:
指导教师:
磁盘调度算法
一、系统需求分析
磁盘存储器不仅容量大,存取速度快,而且可以实现随机存取,是当前存放大量程序和数据的理想设备。
所以在现代计算机中都配备了磁盘存储器,以他为主存放文件,这样对文件的读、写操作都涉及到了对磁盘存储器的访问。磁盘I/O速度的高低和磁盘系统的可靠性,都直接影响到系统的性能。因此改善磁盘系统的性能成为现代操作系统的重要任务之一。
磁盘性能有数据的组织、磁盘的类型和访问时间等。可以通过选择好的磁盘调度算法,以减少磁盘的寻道时间。
为了减少对文件的访问时间,应采用一种最佳的磁盘调度算法,以使各进程对磁盘的平均访问时间最少。由于在访问磁盘的时间中主要是寻道时间,因此,磁盘调度的目标是使磁盘的寻道时间最少。
所以本课程设计对各个算法进行模拟,进而比较分析了解。
二、实验内容和目的
2.1.实验内容
模拟电梯调度算法,实现对磁盘的驱动调度。
设计要求:编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度;要求设计主界面可以灵活选择某算法,且以下算法都要实现
1、先来先服务算法(FCFS)
2、最短寻道时间优先算法(SSTF)
3、扫描算法(SCAN)
4、循环扫描算法(CSCAN)
2.2.实验原理
模拟电梯调度算法,对磁盘调度。
磁盘是要供多个进程共享的存储设备,但一个磁盘每个时刻只能为一个进程服务。
当有进程在访问某个磁盘时,其他想访问该磁盘的进程必须等待,直到磁盘一次工作结束。
当有多个进程提出输入输出请求处于等待状态,可用电梯调度算法从若干个等待访问者中选择一个进程,让它访问磁盘。当存取臂仅需移到一个方向最远的所请求的柱面后,如果没有访问请求了,存取臂就改变方向。
三、总体设计及分类简介
3.1算法介绍
磁盘调度中常用的有四种算法,功能分别如下:
1.先来先服务(FCFS)算法。
即先来的请求先被响应。FCFS策略看起来似乎是相当"公平"的,但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。FCFS策略为我们建立起一个随机访问机制的模型,但是假如用这个策略反复响应从里到外的请求,那么将会消耗大量的时间。为了尽量降低寻道时间,看来我们需要对等待着的请求进行适当的排序,而不是简单的使用FCFS策略。这个过程就叫做磁盘调度管理。有时候FCFS也被看作是最简单的磁盘调度算法。
2.最短寻道时间优先(SSTF)算法。
要求访问的磁道,与当前磁头所在的磁道距离最近,以使每次的寻道时间最短。
3.扫描调度(SCAN)算法。
该算法不仅考虑到欲访问的磁道与当前磁道间的距离,更优先考虑的是磁头当前的移动方向。例如,当磁头正在自里向外移动时,SCAN算法所考虑的下一个访问对象,应是其欲访问的磁道,既在当前磁道之外,又是距离最近的。这样自里向外的访问,直至再无更外的磁道需要访问时,才将磁道换向自外向里移动。这时,同样也是每次选择这样的进程来调度,也就是要访问的当前位置内距离最近者,这样,磁头又逐步地从外向里移动,直至再无更里面的磁道要访问,从而避免了出现“饥饿”现像。
4.循环扫描(C-SCAN)算法。
当磁头刚从里向外移动而越过了某一磁道时,恰好又有一进程请求访问此磁道,这时,该里程就必须等待,为了减少这种延迟,CSCAN算法规定磁头单向移动,而本实验过程中我们所设计的是磁头从里向外移动,而从外向里移动时只须改方向而已,本实验未实现。但本实验已完全能演示循环扫描的全过程。
3.2 详细设计
(1)先来先服务算法(FCFS)
3.3 环境要求
软件要求:Microsoft Visual Stdio
四、程序运行测试
首先输入九个磁道名称以及要访问的磁道号和当前磁道号
选择要执行的算法:
2.先来先服务算法(FCFS)
3.最短寻道时间优先算法(SSTF)
继续调度其他算法,选择是1,选择扫描算法(SCAN)2
4.扫描算法(SCAN)
5.循环扫描算法(CSCAN)
附:代码
#include"stdafx.h"
#include
#include
#define process_Num 9
using namespace std;
struct Track {
int current_Tracknum = 0; //当前磁道号
int next_Track=0; //被访问的下一个磁道号
int move_Distance=0; //移动距离
char process_Name; };
Track track[process_Num];
float track_aveLength=0; //平均寻道长度
int now_Tracknum=0; //最初开始磁道号
int select_num = 0;
int count_Num=0; //调度算法次数
void Scanf_data(){
printf("请输入要访问磁盘的进程:\n");
for (int i = 0; i < process_Num; i++){ cin >>
track[i].process_Name; }
printf("请输入当前的磁道号:");
scanf_s("%d", &now_Tracknum);
printf("请输入进程要访问的磁道号:\n");
for (int i = 0; i < process_Num; i++){ scanf_s("%d",
&track[i].next_Track); }
}
void Select(){
printf("请选择磁盘调度算法:\n");
printf("1.先来先服务算法(FCFS)\n");
printf("2.最短寻道时间优先算法(SSTF)\n");
printf("3.扫描算法(SCAN)\n");
printf("4.循环算法(CSCAN)\n");
scanf_s("%d", &select_num);
}
void Print(){ //打印访问磁盘顺序
printf("进程访问磁盘的先后顺序:");
for (int i = 0; i < process_Num; i++){ printf("%c",
track[i].process_Name); }
printf("\n");
for (int i = 0; i < process_Num; i++){ printf("%d,",
track[i].next_Track); }
printf("\n");
}
void Print_Data(){
printf("打印表格\n");
printf("\t\t从%d#磁道开始\n", now_Tracknum);
printf("\t磁道名\t磁道号\t 移动距离\n");
for (int i = 0; i < process_Num; i++){
printf(" \t%c\t %d\t %d\n", track[i].process_Name, track[i].next_Track, track[i].move_Distance);
}
printf("\n");
printf(" \t平均寻道长度为:%.2f\n", track_aveLength); printf(" \n");
}
void Count_data(){
int nownum = 0; //当前计算次数
for (int i = 0; i < process_Num; i++){
if (nownum == 0){
track[i].move_Distance = abs(now_Tracknum -
track[i].next_Track);
track[i].current_Tracknum = track[i].next_Track;
nownum++;
}
else{
track[i].move_Distance = abs(track[i].next_Track -
track[i - 1].current_Tracknum);
track[i].current_Tracknum = track[i].next_Track;
} }
int sum = 0; //计算平均寻道长度时需要的总和
printf("每次磁头移动距离为:");
for (int i = 0; i < process_Num; i++){
// printf("%d,", track[i].move_Distance);
cout << track[i].move_Distance << " ";
}
for (int i = 0; i < process_Num; i++){
sum = sum + track[i].move_Distance;
}
printf("\n");
track_aveLength = (float)sum / process_Num;
printf("平均寻道长度为:%.2f,", track_aveLength);
printf("\n");
}
void FCFS(){
count_Num++;
printf("按进程提出请求的先后次序进行排队\n"); Print();
Count_data(); printf("\n");
Print_Data();
}
void SSTF(){
count_Num++;
int nownum = 0; //当前计算次数
int x[10];
int xtemp = 0;
int tempint; //冒泡排序时需要的临时int型变量(对进程访问磁道号进行排序)
int tempchar; //冒泡排序时需要的临时char型变量(对进
程名进行排序)
printf("按进程访问磁道与当前磁头所在的磁道距离进行排队\n");
for (int i = 0; i < process_Num; i++){ x[i] =
now_Tracknum - track[i].next_Track; }
for (int i = 0; i < process_Num - 1; i++){
for (int j = 0; j < process_Num - 1 - i; j++){
if (((x[j]>0) && (x[j + 1]>0) && (x[j]>x[j + 1])) || (x[j] < 0 && x[j + 1] > 0)){
xtemp = x[j];
x[j] = x[j + 1];
x[j + 1] = xtemp;
tempint = track[j].next_Track;
track[j].next_Track = track[j +
1].next_Track;
track[j + 1].next_Track = tempint;
tempchar = track[j].process_Name;
track[j].process_Name = track[j +
1].process_Name;
track[j + 1].process_Name = tempchar;
}
if (x[j] < 0 && x[j + 1] < 0){
int x1 = abs(x[j]);
int x2 = abs(x[j + 1]);
if (x1>x2){
xtemp = x[j];
x[j] = x[j + 1];
x[j + 1] = xtemp;
tempint = track[j].next_Track;
track[j].next_Track = track[j + 1].next_Track;
track[j + 1].next_Track = tempint;
tempchar = track[j].process_Name;
track[j].process_Name = track[j + 1].process_Name;
track[j + 1].process_Name = tempchar;
} }
else continue; } }
Print(); Count_data(); printf("\n");
Print_Data();
}
void SCAN(){
count_Num++;
int nownum = 0; //当前计算次数
int x[10];
int xtemp = 0;
int tempint; //冒泡排序时需要的临时int型变量(对进程访问磁道号进行排序)
int tempchar; //冒泡排序时需要的临时char型变量(对进程名进行排序)
printf("SCAN算法按磁头当前的移动方向和进程访问磁道与当前磁头所在的磁道距离进行排队\n");
for (int i = 0; i < process_Num; i++){ x[i] = now_Tracknum - track[i].next_Track; }
for (int i = 0; i < process_Num - 1; i++){
for (int j = 0; j < process_Num - 1 - i; j++){
if (((x[j]>0) && (x[j + 1]>0) && (x[j]>x[j + 1])) || (x[j] > 0 && x[j + 1] < 0)){
xtemp = x[j];
x[j] = x[j + 1];
x[j + 1] = xtemp;
tempint = track[j].next_Track;
track[j].next_Track = track[j + 1].next_Track;
track[j + 1].next_Track = tempint;
tempchar = track[j].process_Name;
track[j].process_Name = track[j +
1].process_Name;
track[j + 1].process_Name = tempchar;
}
if (x[j] < 0 && x[j + 1] < 0){
int x1 = abs(x[j]); int x2 = abs(x[j + 1]);
if (x1>x2){
xtemp = x[j];
x[j] = x[j + 1];
x[j + 1] = xtemp;
tempint = track[j].next_Track;
track[j].next_Track = track[j +
1].next_Track;
track[j + 1].next_Track = tempint;
tempchar = track[j].process_Name;
track[j].process_Name = track[j +
1].process_Name;
track[j + 1].process_Name = tempchar;
} }
else continue; } }
Print(); C ount_data(); printf("\n"); Print_Data();
}
void CSCAN(){
count_Num++;
int nownum = 0; //当前计算次数
int x[10];
int xtemp = 0;
int tempint; //冒泡排序时需要的临时int型变量(对进程访问磁道号进行排序)
int tempchar; //冒泡排序时需要的临时char型变量(对进程名进行排序)
printf("SCAN算法按磁头当前的移动方向和进程访问磁道与当前磁头所在的磁道距离进行排队\n");
for (int i = 0; i < process_Num; i++) { x[i] = now_Tracknum - track[i].next_Track; }
for (int i = 0; i < process_Num - 1; i++) {
for (int j = 0; j < process_Num - 1 - i; j++){
if (((x[j]>0) && (x[j + 1]>0) && (x[j]
xtemp = x[j];
x[j] = x[j + 1];
x[j + 1] = xtemp;
tempint = track[j].next_Track;
track[j].next_Track = track[j + 1].next_Track;
track[j + 1].next_Track = tempint;
tempchar = track[j].process_Name;
track[j].process_Name = track[j +
1].process_Name;
track[j + 1].process_Name = tempchar;
}
if (x[j] < 0 && x[j + 1] < 0){
int x1 = abs(x[j]);
int x2 = abs(x[j + 1]);
if (x1>x2){
xtemp = x[j];
x[j] = x[j + 1];
x[j + 1] = xtemp;
tempint = track[j].next_Track;
track[j].next_Track = track[j +
1].next_Track;
track[j + 1].next_Track = tempint;
tempchar = track[j].process_Name;
track[j].process_Name = track[j +
1].process_Name;
track[j + 1].process_Name = tempchar;
} }
else continue;
} }
Print(); Count_data(); printf("\n"); Print_Data(); }
void Select_num(){ //选择算法
if (select_num == 1){ FCFS(); }
if (select_num == 2){ SSTF(); }
if (select_num == 3){ SCAN(); }
if (select_num == 4){ CSCAN(); } }
int_tmain(int argc, _TCHAR* argv[])
{
Scanf_data();
Select();
Select_num();
int a;
printf(" \n");
while (count_Num > 0 && count_Num < 4){
printf("是否继续调度其他算法
是 1 否 2");
scanf_s("%d", &a);
if (a == 1){
Select();
if (select_num == 1){
FCFS();
}
if (select_num == 2){
SSTF();
}
if (select_num == 3){
SCAN();
}
if (select_num == 4){
CSCAN();
}
}
else exit(0);
}
printf("四种算法已全部执行完毕!\n"); return 0; }