操作系统原理-磁盘管理实验

广州大学学生实验报告开课学院及实验室：计算机科学与工程实验室 2014年12月13日学院计算机科学与教育软件学院年级/专业/班姓名学号实验课程名称操作系统实验成绩实验项目名称磁盘管理实验指导老师张艳玲一、实验目的了解操作系磁盘调度策略的特点及几种寻道优化策略的优缺点。二、实验器材1、计算机一台。2、MacOSX三、实验内容要求模拟先来先服务法（First-Come,First-Served，FCFS），最短寻道时间优先法（ShortestSeekTimeFirst，SSTF），电梯法三种磁盘调度算法，输入为一组请求访问磁道序列，输出为每种调度算法的磁头移动轨迹和移动的总磁道数。四、实验步骤、记录和结果实验并没要求使用何种语言实现，于是我使用了我较擅长的语言Objective-C，并在实现算法的基础上，实现了可视化的效果，通过iphone显示磁头路径轨迹，可以很清晰看出该算法的特性和验证是否正确。程序运行截图如下：默认启动是采用书本上的队列数据，使用FCFS：SSTFLOOK（电梯）由上图可见，根据算法计算的结果和显示的路径都跟书本的一致，证明正确无误。分析：FCFSFCFS算法虽然保证了公平性，但是通常来说响应时间是最长的，由上图可见，移动的总磁道数相比SSTF相差高达640-236=404。是SSTF的2.7倍。SSTF：SSTF算法关键在于寻找离读写磁头的当前柱面最近的请求（从而使寻道时间最短），因此代码实现关键在于计算起点到其他点的最短距离。部分关键代码片段：while(i>=0||j<sort.count){if(i>=0&&j>=sort.count){//剩下前半部分[resultaddObject:sort[i]];i--;continue;}if(j<sort.count&&i<0){//剩下后半部分[resultaddObject:sort[j]];j++;continue;}intn1=[sort[i]intValue];intn2=[sort[j]intValue];if(abs(n1-num)>abs(n2-num)){//将距离最小的插入队列[resultaddObject:sort[j]];num=[sort[j]intValue];j++;}else{[resultaddObject:sort[i]];num=[sort[i]intValue];i--;}}SSTF实现了比FCFS更高的吞吐量和更短的寻道时间。但是缺点也是很明显的，SSTF并不能像FCFS一样保证公平性。根据算法的特性可推知，它的寻道模式往往是高度局部化的，如果新到达的请求聚集在中央柱面附近，那么磁道两端则会需要极大的响应时间，远离读写磁头的请求可能出现饥饿现象。随机生成请求队列，可见当如下情况的时候，SSTF的两端会出现较为极端的响应时间。LOOK（电梯）LOOK算法的表现虽然很像SSTF，但是很好地避免了SSTF会产生的饥饿现象。通常能够具有较短的寻道时间。下图使用的数据跟上图SSTF中的一样，经对比可见，采用LOOK能少移动55磁道数。根据LOOK的特性：当前方向的请求完成后，立马折回完成新方向的请求。则算法实现方面关健点主要集中在磁头方向的折回。部分关键代码片段：//产生随机方向BOOLisToLeft=arc4random()%2;NSComparisonResultorder=isToLeft?NSOrderedAscending:NSOrderedDescending;//找到起点位置intloc=0;for(NSNumber*numinsort){if([numisEqual:source[0]])break;loc++;}//复制一份排序后的结果到resultresult=[NSMutableArrayarrayWithArray:sort];for(inti=loc-1;i>=0;i--){[resultaddObject:result[i]];//把起点前一位的磁道加到最后[resultremoveObjectAtIndex:i];//移除该位置数据}心得体会