操作系统实验 磁盘调度算法)

操作系统 实 验 报 告

哈尔滨工程大学 软件学院

第五讲 磁盘调度算法

一、实验概述 1. 实验名称 磁盘调度算法 2. 实验目的

（1）通过学习EOS实现磁盘调度算法的机制，掌握磁盘调度算法执行的条件和时机。

（2）观察EOS实现的FCFS、SSTF和 SCAN磁盘调度算法，了解常用的磁盘调度算法。

（3）编写CSCAN和N-Step-SCAN磁盘调度算法，加深对各种扫描算法的理解。

3. 实验类型（验证、设计） 验证+设计 4. 实验内容 （1）准备实验

（2）验证先来先服务（FCFS）磁盘调度算法 （3）验证最短寻道时间优先（SSTF）磁盘调度算法 （4）验证SSTF算法造成的线程“饥饿”现象 （5）1.验证扫描（SCAN）磁盘调度算法 2.验证SCAN 算法能够解决“饥饿”现象 （6）改写SCAN调度算法

二、实验环境

操作系统：Windows xp 实验环境：Oslab; 编程语言：C++ 三、实验过程

1.源程序并附上注释 PREQUEST IopDiskSchedule(

VOID

{

)

PLIST_ENTRY pListEntry; PREQUEST pRequest; LONG Offset;

ULONG InsideShortestDistance = 0xFFFFFFFF; ULONG OutsideShortestDistance = 0xFFFFFFFF; PREQUEST //

// 需要遍历请求队列一次或两次 //

for (pListEntry = RequestListHead.Next; // 请求队列中的第一个请求是

pNextRequest0

=

NULL,pNextRequest1=NULL,pNextRequest2=NULL;////

链表头指向的下一个请求。

pListEntry != &RequestListHead; // 遍历到请求队列头时结束循环。 pListEntry = pListEntry->Next) {

//

// 根据链表项获得请求的指针 // pRequest //

// 计算请求对应的线程所访问的磁道与当前磁头所在磁道的偏移 //

Offset = pRequest->Cylinder - CurrentCylinder; if (0 == Offset) {

//

// 如果线程要访问的磁道与当前磁头所在磁道相同，可立即返回。

= CONTAINING_RECORD(pListEntry, REQUEST,

ListEntry);

}

}

//

pNextRequest0 = pRequest; return pNextRequest0; //

// 记录向内移动距离最短的线程 //

if (Offset < InsideShortestDistance) { ///偏移小于向内最短距离 } //

// 记录向外移动距离最短的线程 //

if (-Offset < OutsideShortestDistance) { }

OutsideShortestDistance = -Offset; pNextRequest2= pRequest; InsideShortestDistance = Offset; pNextRequest1 = pRequest;

} if (Offset > 0) {

} if ( Offset < 0) {

if(ScanInside)//判断磁头是否有向内移动。如果是则执行下面指令 {

if(pNextRequest1)//判断是否有向内移动的线程。

{

return pNextRequest1;//有则返回向内移动距离最短的线程 } else {

ScanInside=!ScanInside;//改变磁头运动方向向外

return pNextRequest2;//没有则返回向外移动距离最短的线程 } }

2. 程序运行时的初值和运行结果：

（1）验证先来先服务（FCFS）磁盘调度算法 （2）验证最短寻道时间优先（SSTF）磁盘调度算法

}

else//如果否则执行下边的指令 {

if(pNextRequest2) //判断是否有向外移动的线程 {

return pNextRequest2; //有则返回向外移动距离最短的线程 } else {

ScanInside=!ScanInside;//并改变磁头运动方向向内

return pNextRequest1;//没有则返回向内移动距离最短的线程 } }

（3）验证SSTF算法造成的线程“饥饿”现象

（4）验证扫描（SCAN）磁盘调度算法

//先来先服务的磁柱调度算法

****** Disk schedule start working ****** Start Cylinder: 10

TID: 31 Cylinder: 8 Offset: 2 - TID: 32 Cylinder: 21 Offset: 13 + TID: 33 Cylinder: 9 Offset: 12 - TID: 34 Cylinder: 78 Offset: 69 + TID: 35 Cylinder: 0 Offset: 78 - TID: 36 Cylinder: 41 Offset: 41 + TID: 37 Cylinder: 10 Offset: 31 - TID: 38 Cylinder: 67 Offset: 57 + TID: 39 Cylinder: 12 Offset: 55 - TID: 40 Cylinder: 10 Offset: 2 -

Total offset: 360 Transfer times: 10 Average offset: 36 ****** Disk schedule stop working ******

//磁柱顺序未改变电梯调度结果

****** Disk schedule start working ****** Start Cylinder: 10

TID: 37 Cylinder: 10 Offset: 0 = TID: 40 Cylinder: 10 Offset: 0 = TID: 39 Cylinder: 12 Offset: 2 + TID: 32 Cylinder: 21 Offset: 9 + TID: 36 Cylinder: 41 Offset: 20 + TID: 38 Cylinder: 67 Offset: 26 + TID: 34 Cylinder: 78 Offset: 11 + TID: 33 Cylinder: 9 Offset: 69 - TID: 31 Cylinder: 8 Offset: 1 - TID: 35 Cylinder: 0 Offset: 8 -

Total offset: 146 Transfer times: 10 Average offset: 14 ****** Disk schedule stop working ******* //磁柱顺序未改变最邻近优先调度结果 ****** Disk schedule start working ****** Start Cylinder: 10

TID: 37 Cylinder: 10 Offset: 0 = TID: 40 Cylinder: 10 Offset: 0 = TID: 33 Cylinder: 9 Offset: 1 - TID: 31 Cylinder: 8 Offset: 1 - TID: 39 Cylinder: 12 Offset: 4 + TID: 32 Cylinder: 21 Offset: 9 + TID: 36 Cylinder: 41 Offset: 20 + TID: 38 Cylinder: 67 Offset: 26 + TID: 34 Cylinder: 78 Offset: 11 + TID: 35 Cylinder: 0 Offset: 78 -

Total offset: 150 Transfer times: 10 Average offset: 15 ****** Disk schedule stop working ******

//磁柱顺序改变后最邻近优先调度结果，78排在队列首，却在最后被调度，孩子被饿到了

****** Disk schedule start working ****** Start Cylinder: 10

TID: 37 Cylinder: 10 Offset: 0 = TID: 40 Cylinder: 10 Offset: 0 = TID: 33 Cylinder: 9 Offset: 1 - TID: 34 Cylinder: 8 Offset: 1 - TID: 35 Cylinder: 11 Offset: 3 + TID: 39 Cylinder: 12 Offset: 1 + TID: 32 Cylinder: 21 Offset: 9 + TID: 36 Cylinder: 41 Offset: 20 +

TID: 38 Cylinder: 67 Offset: 26 + TID: 31 Cylinder: 78 Offset: 11 +

Total offset: 72 Transfer times: 10 Average offset: 7 ****** Disk schedule stop working ******

//验证电梯调度解决最邻近优先的饥饿，78在调度队列首 ****** Disk schedule start working ****** Start Cylinder: 10

TID: 37 Cylinder: 10 Offset: 0 = TID: 40 Cylinder: 10 Offset: 0 = TID: 35 Cylinder: 11 Offset: 1 + TID: 39 Cylinder: 12 Offset: 1 + TID: 32 Cylinder: 21 Offset: 9 + TID: 36 Cylinder: 41 Offset: 20 + TID: 38 Cylinder: 67 Offset: 26 + TID: 31 Cylinder: 78 Offset: 11 + TID: 33 Cylinder: 9 Offset: 69 - TID: 34 Cylinder: 8 Offset: 1 -

Total offset: 138 Transfer times: 10 Average offset: 13 ****** Disk schedule sto …… 此处隐藏：2799字，全部文档内容请下载后查看。喜欢就下载吧 ……