ScanInside不会被重置,因此输出的结果会不一样。只需在for循环结束后添加如下代码,就能确保调度的顺序一致。
图 3.3.6
(6)尝试在 io/block.c 文件中定义一个全局的函数指针变量 DiskScheduleFunc,该函数指针初始指向实现了 FCFS 算法的 IopDiskSchedule 函数。修改 io/block.c 文件中的 IopProcessNextRequest 函数,在该函数中不再直接调用 IopDiskSchedule 函数,而是调用函数指针 DiskScheduleFunc 指向的磁盘调度算法函数;ke/sysproc.c 文件中的 ConsoleCmdDiskSchedule 函数中也不再直接调用IopDiskSchedule函数,也要修改为调用函数指针DiskScheduleFunc指向的磁盘调度算法函数。最后,添加一个控制台命令“sstf”,该命令使函数指针 DiskScheduleFunc 指向实现了 SSTF 算法的函数。这样,在 EOS启动后默认会执行FCFS 算法,执行控制台命令“sstf”后,会执行SSTF算法。按照这种方式依次实现“fcfs”、“scan”、“cscan”和“nstepscan”命令。说明这种在EOS运行时动态切换磁盘调度算法的好处。
答:首先在block.c 中定义一个全局的函数指针变量 DiskScheduleFunc。
图 3.3.7
修改IopProcessNextRequest 函数和ConsoleCmdDiskSchedule 函数,使其不再直接调用 IopDiskSchedule 函数而是调用函数指针DiskScheduleFunc指向的磁盘调度算法函数。
图 3.3.8
调用函数前先声明。
10
图 3.3.9
添加一个控制台命令“sstf”,该命令使函数指针 DiskScheduleFunc 指向实现了 SSTF 算法的函数。
图 3.3.10
验证结果如下图所示。
图 3.3.11
11
图 3.3.12
(7)分析已经实现的各种磁盘调度算法的优缺点,尝试实现更多其它的磁盘调度算法。
答:先来先服务算法是一种比较简单的磁盘调度算法,它根据进程请求访问磁盘的先后次序进行调度,此算法的优点是公平、简单,且每个进程的请求都能依次得到处理,不会出现某一进程的请求长期得不到满足的情况,在对磁盘的访问请求比较多的情况下,致使平均寻道时间可能较长;最短寻道时间优先算法选择这样的进程,其要求访问的磁道与当前磁头所在的磁道距离最近,以使每次的寻道时间最短,该算法可以得到比较好的吞吐量,但却不能保证平均寻道时间最短,其缺点是在服务请求很多的情况下,对内外边缘磁道的请求将会无限期的被延迟;扫描算法不仅考虑到欲访问的磁道与当前磁道的距离,更优先考虑的是磁头的当前移动方向,此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点,而具有最短寻道时间优先算法的优点即吞吐量较大,平均响应时间较小,但由于是摆动式的扫描方法,两侧磁道被访问的频率仍低于中间磁道;循环扫描算法是对扫描算法的改进,如果对磁道的访问请求是均匀分布的,当磁头到达磁盘的一端,并反向运动时落在磁头之后的访问请求相对较少;N-Step-SCAN算法是扫描算法和先来先服务算法的一个综合算法,将请求队列分成若干个长度为 N 的子队列,调度程序按照 FCFS原则依次处理
12
这些子队列,而每处理一个子队列时,又是按照SCAN算法,所以它是一种性能比较平均的算法。
(6)EOS 在块设备层实现了磁盘调度算法后,由于请求队列中的请求一定是被逐个处理的,所以并发的多个线程已经可以互斥的访问磁盘上的数据,那为什么在 IopReadWriteSector 函数中还要使用磁盘设备的互斥信号量进行互斥呢?(提示:如果一个线程只是要获取磁盘设备的状态而不是要访问磁盘上的数据,是否需要对该线程进行磁盘调度?该线程是否要与其它并发访问磁盘设备的线程进行互斥?)
答:如果一个线程只是要获取磁盘设备的状态而不是要访问磁盘上的数据,那这个线程是不需要进行磁盘调度的,所以不会进入请求队列,但该线程同样需要与其它并发访问磁盘设备的线程进行互斥,这时就需要使用磁盘设备的互斥信号量进行互斥。
4. 源程序并附上注释 (1)改写SCAN算法
BOOL ScanInside = TRUE;
PREQUEST
IopDiskSchedule( VOID ) { PLIST_ENTRY pListEntry; PREQUEST pRequest; PREQUEST INpNextRequest = NULL; PREQUEST OUTpNextRequest = NULL; LONG Offset; ULONG InsideShortestDistance = 0xFFFFFFFF; ULONG OutsideShortestDistance = 0xFFFFFFFF; PREQUEST pNextRequest = NULL; // 需要遍历请求队列一次或两次
for (pListEntry = RequestListHead.Next; // 请求队列中的第一个请求是链表头指
//向的下一个请求。
pListEntry != &RequestListHead; // 遍历到请求队列头时结束循环。
13
pListEntry = pListEntry->Next) { // 根据链表项获得请求的指针 pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);
// 计算请求对应的线程所访问的磁道与当前磁头所在磁道的偏移(方向由正负表示) Offset = pRequest->Cylinder - CurrentCylinder; if (0 == Offset) { // 如果线程要访问的磁道与当前磁头所在磁道相同,可立即返回。 pNextRequest = pRequest; goto RETURN; } else if ( Offset > 0 && Offset < InsideShortestDistance ) { // 记录向内移动距离最短的线程 InsideShortestDistance = Offset; INpNextRequest = pRequest; } else if ( Offset < 0 && -Offset < OutsideShortestDistance ) { // 记录向外移动距离最短的线程 OutsideShortestDistance = -Offset; OUTpNextRequest = pRequest; } } //判断磁头移动方向,若向内移动 if( ScanInside) { //判断是否有向内移动的线程 if(INpNextRequest) { //有则选择该线程 return INpNextRequest; } else { //没有则修改磁头方向,选择向外移动距离最短的线程 ScanInside = !ScanInside; return OUTpNextRequest; } } //如果向外移动 else {
14
操作系统实验 第五讲 磁盘调度算法
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)