}
//判断是否有向外移动的线程 if(OUTpNextRequest) { //有则选择该线程 return OUTpNextRequest; } else { //没有则修改词头方向，选择向内移动距离最短的线程 ScanInside = !ScanInside; return INpNextRequest; } } RETURN:
return pNextRequest;
（2）编写循环扫描（CSCAN）磁盘调度算法
PREQUEST
IopDiskSchedule( VOID ) { PLIST_ENTRY pListEntry; PREQUEST pRequest; PREQUEST INpNextRequest = NULL; PREQUEST OUTpNextRequest = NULL; LONG Offset; ULONG InsideShortestDistance = 0xFFFFFFFF; ULONG OutsideShortestDistance = 0x00000000; PREQUEST pNextRequest = NULL; // 需要遍历请求队列一次或两次 for (pListEntry = RequestListHead.Next; // 请求队列中的第一个请求是链表头指 //向的下一个请求。 pListEntry != &RequestListHead; // 遍历到请求队列头时结束循环。 pListEntry = pListEntry->Next) { // 根据链表项获得请求的指针 pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);
15
// 计算请求对应的线程所访问的磁道与当前磁头所在磁道的偏移（方向由正负表示） 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( INpNextRequest ) { //存在则返回向内移动的请求 return INpNextRequest; } else { //否则返回向外移动的请求 return OUTpNextRequest; } RETURN: return pNextRequest;
}
（3）编写N-Step-SCAN磁盘调度算法
// N-Step-SCAN 磁盘调度算法使用的子队列长度N #define SUB_QUEUE_LENGTH 6
// 记录N-Step-SCAN 磁盘调度算法第一个子队列剩余的长度。
// 子队列初始长度为N，每执行一次磁盘调度算法会从子队列中移除一个请求，子队列 // 长度就要减少1，待长度变为0 时，再将长度重新变为N，开始处理下一个子队列。
16
ULONG SubQueueRemainLength = SUB_QUEUE_LENGTH;
// 扫描算法中磁头移动的方向。操作系统启动时初始化为磁头向内移动。 // TRUE，磁头向内移动，磁道号增加。 // FALSE，磁头向外移动，磁道号减少。 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; ULONG counter; // // 需要遍历请求队列一次或两次 // //计数器记录一个子队列剩余的长度 counter = SubQueueRemainLength; //没调度一次子队列剩余的长度减 SubQueueRemainLength--; //如果子队列剩余的长度为，则重置为子队列原长度 if(SubQueueRemainLength == 0) SubQueueRemainLength = SUB_QUEUE_LENGTH;
for (pListEntry = RequestListHead.Next; // 请求队列中的第一个请求是链表头指
//向的下一个请求。
pListEntry != &RequestListHead && counter>0; // 遍历到请求队列头时结
//束循环或子队列结束。
pListEntry = pListEntry->Next) { // 根据链表项获得请求的指针 pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry); // 计算请求对应的线程所访问的磁道与当前磁头所在磁道的偏移（方向由正负表示） Offset = pRequest->Cylinder - CurrentCylinder; if (0 == Offset) { // 如果线程要访问的磁道与当前磁头所在磁道相同，可立即返回。
17
}
pNextRequest = pRequest; return pNextRequest;
} else if ( Offset > 0 && Offset < InsideShortestDistance ) { // 记录向内移动距离最短的线程 InsideShortestDistance = Offset; INpNextRequest = pRequest;
} else if ( Offset < 0 && -Offset < OutsideShortestDistance ) { // 记录向外移动距离最短的线程 OutsideShortestDistance = -Offset; OUTpNextRequest = pRequest; }
counter--; }
if( ScanInside ) { if(INpNextRequest) { return INpNextRequest; } else { ScanInside = !ScanInside; return OUTpNextRequest; } } else { if(OUTpNextRequest) { return OUTpNextRequest; } else { ScanInside = !ScanInside; return INpNextRequest; } }
5. 程序运行时的初值和运行结果
18
（1）验证先来先服务（FCFS）磁盘调度算法
新建一个 EOS Kernel项目，双击ke文件夹中的sysproc.c文件，阅读函数ConsoleCmdDiskSchedule，目前该函数使磁头初始停留在磁道10，其它被阻塞的线程依次访问磁道8、21、9、78、0、41、10、67、12、10。
按F5调试项目，待 EOS启动完毕，在EOS控制台中输入命令“ds”后按回车。控制台和输出窗口显示内容如下图所示。
图 3.5.2
19
操作系统实验 第五讲 磁盘调度算法
