一:实验内容
模拟电梯调度算法,对磁盘进行移臂和旋转调度。
二.实验题目
(1).“驱动调度”进程和“接收请求”进程能否占有处理器运行,取决于磁盘的结束中断信 号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序,以代替中断 处理和处理器调度选择的过程。因而,程序的结构可参考下图:
(2).“接收请求”进程建立一张“请求 I/O”表,指出访问磁盘的进程要求访问的物理 地址,表的格式为:
假定某个磁盘组共有 200 个柱面,由外向里顺序编号(0—199),每个柱面上有 20 个 磁道,编号为 0—19,每个磁道分成 8 个物理记录,编号 0—7。进程访问磁盘的物理地址 可以用键盘输入的方法模拟得到。下图是“接收请求”进程的模拟算法。
三.代码实现
#include<stdio.h>#include<stdlib.h>#define IOnum 10 //模拟IO表最大长度struct IO_table{char Pname; //进程名int Zhu; //柱面号int Ci; //磁头号int Sha; //扇区号(物理记录)}IO_table[IOnum],current; //current用于存储每次调度前的上一次访问磁盘的位置int more_current[IOnum] = {-1}; //存储柱面号大于当前柱面号的数组int more_length = 0;//more数组有效长度int less_current[IOnum] = {-1}; //存储柱面号小于当前柱面号的数组int less_length = 0; //less数组有效长度int processNum = 0; //存储当前IO表中进程总数int YB_direct = 1; //移臂方向标识符 1表示向内up 0表示向外down 默认向内为1void IO_table_init() //IO请求表初始化{int i = 0; for (i; i < IOnum; i++)//初始化未使用时表内各项数据均为-1{IO_table[i].Pname = '-1';IO_table[i].Zhu = -1;IO_table[i].Ci = -1;IO_table[i].Sha = -1;more_current[i] = -1;less_current[i] = -1;}//模拟预装入8条请求,顺序任意IO_table[0].Pname = 'A'; IO_table[0].Zhu = 58; IO_table[0].Ci = 2; IO_table[0].Sha = 1;//第一个请求IO_table[1].Pname = 'B'; IO_table[1].Zhu = 55; IO_table[1].Ci = 3; IO_table[1].Sha = 2;//第二个请求IO_table[2].Pname = 'C'; IO_table[2].Zhu = 39; IO_table[2].Ci = 4; IO_table[2].Sha = 3;//第三个请求IO_table[3].Pname = 'D'; IO_table[3].Zhu = 38; IO_table[3].Ci = 5; IO_table[3].Sha = 4;//第四个请求IO_table[4].Pname = 'E'; IO_table[4].Zhu = 18; IO_table[4].Ci = 6; IO_table[4].Sha = 5;//第五个请求IO_table[5].Pname = 'F'; IO_table[5].Zhu = 160; IO_table[5].Ci = 7; IO_table[5].Sha = 6;//第六个请求IO_table[6].Pname = 'G'; IO_table[6].Zhu = 150; IO_table[6].Ci = 8; IO_table[6].Sha = 7;//第七个请求IO_table[7].Pname = 'H'; IO_table[7].Zhu = 184; IO_table[7].Ci = 9; IO_table[7].Sha = 0;//第八个请求//模拟预设置 current的值current.Pname = '-1'; current.Zhu = 100; current.Ci = 1; current.Sha = 0;}void show_IO_table() //打印当前请求IO表{printf("----------------------[I/O请求表]------------------------\n");int i = 0;for (i; i < IOnum; i++){if (IO_table[i].Sha != -1) //打印非空项{printf("【进程名】:%c", IO_table[i].Pname);printf(" 【柱面号】:%3d", IO_table[i].Zhu);printf(" 【磁头号】:%d", IO_table[i].Ci);printf(" 【扇区号】:%d\n", IO_table[i].Sha);}}printf("----------------------[I/O请求表]------------------------\n");}int find_inLocation() //寻找当前IO表中第一个空闲位置,未找到则返回-1{ int flag = -1;int i = 0;for (i; i < IOnum; i++){if (IO_table[i].Zhu == -1) //找到IO表中第一个空下标保存并退出{flag = i;break;}}return flag;}void show_current() //打印选中的current进程,模拟其访问磁盘{printf("【提示】当前选中进程:");printf("【进程名】:%c", current.Pname);printf(" 【柱面号】:%3d", current.Zhu);printf(" 【磁头号】:%d", current.Ci);printf(" 【扇区号】:%d\n", current.Sha);}void show_updown()//打印方向{if (YB_direct == 1)printf("【方向】:up(内)\n");if(YB_direct==0)printf("【方向】:down(外)\n");}void add_IO_request() //添加新请求{int flag = -1; //用于标识插入IO表位置flag = find_inLocation();if (flag != -1){printf("【提示】请依次输入【进程名】-【柱面号】-【磁头号】-【扇区号】:\n");scanf("%s%d%d%d", &IO_table[flag].Pname, &IO_table[flag].Zhu, &IO_table[flag].Ci, &IO_table[flag].Sha);}else{printf("【提示】IO表已满");}show_IO_table();//打印修改后的IO表}int find_zhu(int X) //寻找是否有与X相同的柱面 找到返回其在IO表下标,未找到返回-1{int flag = -1;int i = 0;for (i; i < IOnum; i++){if (IO_table[i].Zhu ==X) //两柱面相同{flag = i; //找到符合条件的第一个即返回下标break;}}return flag;}void sort(int a[],int count)// 直接插入排序 count为数组有效长度,排序为从小到大{int i, j, temp;for (i = 1; i < count; i++){temp = a[i];j = i - 1;while (a[j] > temp && j >= 0){a[j + 1] = a[j];j--;}if (j != (i - 1))a[j + 1] = temp;}}void divide_IO_table() //将IO表按current大小一分为二{int i = 0, j = 0,t=0;for (t; t < processNum; t++) //当t小于IO表有效长度时{if (IO_table[t].Zhu > current.Zhu) //找到柱面号大于current的保存{more_current[i] = IO_table[t].Zhu; //添加i++;}if (IO_table[t].Zhu < current.Zhu) //找到柱面号小于current的保存{less_current[j] = IO_table[t].Zhu;j++;}}more_length = i;//保存more有效长度less_length = j ;//保存less有效长度}void update_IO_table() //更新IO表信息{int flag = find_zhu(current.Zhu);//用于标识删除位置int i = 0;if (flag == IOnum - 1) //若删除的是最后一个{IO_table[flag].Pname = '-1'; IO_table[flag].Zhu = -1; IO_table[flag].Ci = -1; IO_table[flag].Sha = -1;}else{for (i = flag; i < IOnum - 1; i++) //删除非最后一个,数组整体前移{IO_table[i].Pname = IO_table[i + 1].Pname;IO_table[i].Zhu = IO_table[i + 1].Zhu;IO_table[i].Ci = IO_table[i + 1].Ci;IO_table[i].Sha = IO_table[i + 1].Sha;}}}void reset_para()//重置各项工作参数{more_length = 0; less_length = 0;int i = 0;for (i; i < IOnum; i++){more_current[i] = -1;less_current[i] = -1;}}void scheduling() //调度程序{int i = 0;//先检查此时IO表中请求总数processNum = find_inLocation();if (processNum == 0) //请求表为空{printf("【提示】此时IO表中无等待进程,已退出\n");}//更新currentelse //请求表不为空{if (find_zhu(current.Zhu) != -1) //找到与current相同柱面的请求{//更新currentcurrent.Pname = IO_table[find_zhu(current.Zhu)].Pname; //进程名current.Ci = IO_table[find_zhu(current.Zhu)].Ci; //磁头号current.Sha = IO_table[find_zhu(current.Zhu)].Sha; //扇区号}else //未找到相同柱面,采用电梯算法寻找一个合理请求{divide_IO_table();//以current为基准划分IO表,且保存more_current/less_current可作为端点判断//将划分的两个数组进行排序sort(more_current, more_length);sort(less_current, less_length);if (YB_direct == 1) //移臂为1表示此时向内{if (more_length != 0) //即存在比current还大的柱面号{//更新currentcurrent.Pname = IO_table[find_zhu(more_current[0])].Pname;//进程名current.Zhu = IO_table[find_zhu(more_current[0])].Zhu; //柱面号current.Ci = IO_table[find_zhu(more_current[0])].Ci; //磁头号current.Sha= IO_table[find_zhu(more_current[0])].Sha; //扇区号}else //不存在比current还大的柱面号,需变向{YB_direct = 0;//移臂方向改为向外//按YB=1的方式更新current 模拟变向current.Pname = IO_table[find_zhu(less_current[less_length - 1])].Pname; //进程名current.Zhu = IO_table[find_zhu(less_current[less_length-1])].Zhu; //柱面号current.Ci = IO_table[find_zhu(less_current[less_length-1])].Ci; //磁头号current.Sha = IO_table[find_zhu(less_current[less_length-1])].Sha; //扇区号}}//YB=1if (YB_direct == 0)//移臂为0表示此时向外{if (less_length != 0) //即存在比current还小的柱面号{//更新currentcurrent.Pname = IO_table[find_zhu(less_current[less_length - 1])].Pname;//进程名current.Zhu = IO_table[find_zhu(less_current[less_length - 1])].Zhu; //柱面号current.Ci = IO_table[find_zhu(less_current[less_length - 1])].Ci; //磁头号current.Sha = IO_table[find_zhu(less_current[less_length - 1])].Sha; //扇区号}else //不存在比current还小的柱面号,需变向{YB_direct = 1;//移臂方向改为向内//按YB=0的方式更新current 模拟变向current.Pname = IO_table[find_zhu(more_current[0])].Pname; //进程名current.Zhu = IO_table[find_zhu(more_current[0])].Zhu; //柱面号current.Ci = IO_table[find_zhu(more_current[0])].Ci; //磁头号current.Sha = IO_table[find_zhu(more_current[0])].Sha; //扇区号}}//YB=0}//打印方向show_updown();//current已更新完-模拟访问磁盘show_current();//打印current//更新IO表,即删除此次访问项update_IO_table();//重置各项辅助参数reset_para();//打印本次执行后IO表show_IO_table();}}void main(){IO_table_init(); //初始化show_IO_table(); //打印初始IO请求表int select = -1; //选择标识符printf("【提示】请选择要执行的操作:(0->驱动调度:1->接收进程)");scanf("%d", &select);while (1){ printf("【提示】当前磁盘位置:");printf("【进程名】:%c", current.Pname);printf(" 【柱面号】:%3d", current.Zhu);printf(" 【磁头号】:%d", current.Ci);printf(" 【扇区号】:%d\n", current.Sha);if(select==0)scheduling(); //调用驱动程序if (select == 1)add_IO_request();//接受进程printf("【提示】请选择要执行的操作:(0->驱动调度:1->接收进程)");scanf("%d", &select);}system("pause");}
四.运行结果
【初始化IO表并打印】
【进行一次驱动调度】当前current.Zhu=100
可发现“选中进程”已从IO请求表中移除。
【进行一次驱动调度】当前current.Zhu=150
观察可发现“选中进程”已从IO请求表中移除
【进行一次接受进程】当前current.Zhu=160
可发现模拟新请求已插入到请求表中
五.流程图
(1.)scheduling()调度函数
(2).电梯调度算法