模拟电梯调度算法，对磁盘进行移臂和旋转调度。
二.实验题目
(1).“驱动调度”进程和“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信 号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断 处理和处理器调度选择的过程。因而，程序的结构可参考下图:
(2).“接收请求”进程建立一张“请求 I/O”表，指出访问磁盘的进程要求访问的物理 地址，表的格式为：
假定某个磁盘组共有 200 个柱面，由外向里顺序编号（0—199），每个柱面上有 20 个 磁道，编号为 0—19，每个磁道分成 8 个物理记录，编号 0—7。进程访问磁盘的物理地址 可以用键盘输入的方法模拟得到。下图 是“接收请求”进程的模拟算法。
三.代码实现
#include#include #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 默认向内为1 void 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(" 【扇区号】:%dn", 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(" 【扇区号】:%dn", 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"); } //更新current else //请求表不为空 { if (find_zhu(current.Zhu) != -1) //找到与current相同柱面的请求 { //更新current current.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还大的柱面号 { //更新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; //扇区号 } 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=1 if (YB_direct == 0)//移臂为0表示此时向外 { if (less_length != 0) //即存在比current还小的柱面号 { //更新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; //扇区号 } 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(" 【扇区号】:%dn", 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).电梯调度算法
