基于linux的设备分配及磁盘调度算法说明书.doc
《基于linux的设备分配及磁盘调度算法说明书.doc》由会员分享，可在线阅读，更多相关《基于linux的设备分配及磁盘调度算法说明书.doc（66页珍藏版）》请在冰点文库上搜索。
中北大学软件学院实训说明书
中北大学软件学院
实训说明书
实训名称:
操作系统课程设计
基于Linux的设备分配
及磁盘调度算法
题目名称：
软件工程
专业：
班级：
12210A02
小组成员
学号：
姓名：
高田田成绩：
学号：
姓名：
王浩成绩：
学号：
姓名：
许嘉阳成绩：
学号：
姓名：
王晋英成绩：
薛海丽
指导教师：
2015年1月
非物质文化遗产是指各族人民世代传承的，与群众生活密切相关的各种传统文化表现形式和文化空间，包括民俗活动、表演艺术、传统知识和技能以及与之相关的器具、实物、手工制品等
任务分工情况说明
姓名
分工
组长
高田田
负责小组分工,资料查询,参与整体需求分析及概要设计，完成设备分配部分的详细设计及代码。
完成代码整合及主函数的编写。
完成小组说明书文档整理工作。
组员
王浩
资料查询,参与整体需求分析及概要设计，完成磁盘调度中先来先服务（FCFS）和循环扫描调度算法（CSCAN）部分的详细设计及代码，协助完成设备分配。
组员
许嘉阳
资料查询,参与整体需求分析及概要设计，完成磁盘调度中最短寻道时间优先算法（SSTF）和扫描调度算法（SCAN）部分的详细设计及代码代码，协助完成设备分配。
组员
王晋英
资料查询,参与整体需求分析及概要设计，完成进程控制部分的详细设计及代码编写。
第I页共1页
目录
1.绪论 1
2.需求分析 1
2.1.目的 1
2.2.内容 2
2.2.1.进程调度 2
2.2.2.设备分配 2
2.2.3.磁盘调度 3
3.概要设计 4
3.1.进程调度 4
3.1.1.功能模块图 4
3.1.2.相关函数 5
3.2.设备分配 5
3.2.1.功能模块图 6
3.2.1.相关函数 6
3.3.磁盘调度 7
3.2.1.功能模块图 7
3.2.1.相关函数 7
4.详细设计 7
4.1.进程调度 7
4.1.1进程创建 7
4.1.2进程切换 9
4.1.3进程阻塞 10
4.1.4进程唤醒 10
4.1.5进程结束 11
4.1.6进程显示 12
4.2.设备分配 13
4.2.1.设备分配 13
4.2.2.设备释放 16
4.2.3.设备添加 19
4.2.4.设备删除 21
4.2.5.设备显示 24
4.3.磁盘调度 26
4.3.1.先来先服务算法 26
4.3.2最短寻道时间优先算法 27
4.3.3扫描算法 28
4.3.4循环扫描算法 30
4.3.5调用四种算法比较 31
5.心得体会 32
6.参考文献 33
7.源代码 34
I
1.绪论
随着信息技术的发展,,Linux操作系统得到了前所未有的广泛应用。
Linux被应用到包括便携式电子设备、生物科技以及航天科技等各种领域。
显然不同应用领域对Linux系统的实时性、公平性和吞吐量等性能有着不同的要求,而进程调度算法对Linux系统性能起着至关重要的作用,用来创建进程,撤销进程,实现进程转换,它提供了可运行得进程之间复用CPU的方法，并为创建的进程在设备分配功能中提供所必要设备。
同时，Internet的飞速发展使数据增长，这给数据增长带来了很大的压力。
对数据的访问性能、数据传输性能、数据管理性能和存储扩展等方面都提出了比过去更高的要求。
这需要一个既能满足大容量信息存储、能适应将来容量扩充要求的存储器管理系统，又可以大大提高传输速率，还可以完成信息高速处理的计算机体系架构。
而随着技术的发展，设备管理技术和磁盘调度技术成为提高数据处理和数据传输的关键因素。
因此，研究海量管理系统中的分配管理技术和磁盘调度策略具有重要意义。
本次课程设计就这些问题展开了一些有意义的研究工作。
2.需求分析
2.1.目的
（1）通过本实验可以加深理解有关进程控制块（PCB）、进程队列的概念，体会并了解创建进程、切换进程、阻塞进程、唤醒进程、结束进程、显示进程的具体实施过程。
（2）完成设备管理功能的模拟，掌握包括通道和控制器的添加和删除，设备的添加、删除，设备的分配和回收。
（3）通过设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解。
2.2.内容
2.2.1.进程调度
2.2.2.1.功能分析
（1）每个进程有一个进程控制块（PCB）表示。
进程控制块包含如下信
息:
进程名、进程编号、进程的大小和进程的临接PCB的地址。
（2）每个进程的状态可以是就绪（ready）、执行（running）和阻塞
（block）三种状态之一。
（3）进程创建，由系统生成一个PCB结点，用进队函数放入就绪队列。
如果没有正在执行的进程，则将等待队列中就绪进程调入执行。
（4）进程切换，通过函数实现将运行队列中的执行进程调入就绪队列，
将等待队列中就绪进程调入执行。
（5）进程阻塞，通过函数实现将运行队列中的执行进程调入阻塞队
列，将等待队列中就绪进程调入执行。
（6）进程唤醒，通过函数实现将阻塞队列中的阻塞进程调入就绪队
列，将等待队列中就绪进程调入执行。
（7）进程结束，通过函数实现将就绪队列中的就绪进程抢占运行队
列。
（8）进程显示，根据队列进程的存储特性，顺序查找到每个进程并依
次输出每个进程的名称和大小。
（9）所创建进程将会在设备分配功能中为其提供所需必要设备。
2.2.2.1.数据结构
进程控制块（PCB）
2.2.2.设备分配
2.2.2.1.功能分析
（1）设备管理子系统涉及到通道控制表（CHCT）、控制器控制表（COCT）
和设备控制表（DCT）来体现输入输出系统。
（2）实现上述设备、控制器以及通道的层次关系，同时能够添加或删
除新的设备、控制器或通道。
（3）通过键盘命令模拟进程执行过程中提出的设备分配或释放请求，
并为此请求分配或释放设备。
分配设备成功后可将进程状态调整为阻塞，释
放设备后变为就绪状态。
（4）分配设备时应如果该设备已被其它进程占用，则设备分配失败，
请求进程进入阻塞状态，同时等待该设备的释放。
如果设备空闲，进程占用
设备的同时还应提出申请控制器请求，直到与设备相关的通道都已申请成功
为止。
（5）设备、控制器或通道的释放应引起对应节点的等待队列中的第一
个阻塞进程被唤醒。
如果被唤醒的进程还未完成申请操作，应继续执行上级
节点的申请操作。
2.2.2.2.数据结构
设备控制表（DCT）
控制器控制表（COCT）
通道控制表（CHCT）
2.2.3.磁盘调度
系统主界面可以灵活选择某种算法，算法包括：
先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）。
2.2.3.1先来先服务算法（FCFS）
这是一种比较简单的磁盘调度算法。
它根据进程请求访问磁盘的先后次序进行调度。
此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。
此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。
2.2.3.2最短寻道时间优先算法（SSTF）
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。
其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。
在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。
2.2.3.3扫描算法（SCAN）
扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。
例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。
这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。
这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。
由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。
此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。
2.2.3.4循环扫描算法（CSCAN）
循环扫描算法是对扫描算法的改进。
如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。
这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。
例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。
3.概要设计
3.1.进程调度
3.1.1.功能模块图
图3.1进程管理功能模块图
3.1.2.相关函数
voidenqueue（intid,char*name,intsize,structPCB*head）--进程进入队列（就绪队列、阻塞队列）
structPCB*dequeue（structPCB*head）--进程移出队列
voidcreateProcess（）--创建进程
voidswitchProcess（）--进程切换
voidblockProcess（）--阻塞进程
voidwakeupProcess（）--唤醒进程
voidterminateProcess（）--结束进程
voiddisplayProcessstatus（）--显示进程状态
3.2.设备分配
3.2.1.功能模块图
图3.2设备分配功能模块图
3.2.1.相关函数
structDCT*findDCT（charname[]）--用设备名查找设备
structCOCT*findController（charname[]）--用控制器名查找控制器
structCHCT*findChannel（charname[]）--用通道名查找通道
addProcesstoWaiting（*waiting,*p）--进入进程等待队列
add（*head,*node）--入队列
structPCB*getFirst（*head）--获得队列里的第一个进程
allocateCHCT（*chct,*p）--分配CHCT
allocateCOCT（*coct,*p）--分配COCT
allocateDCT（）--分配DCT
releaseCHCT（*name,*chct,*p）--释放通道
releaseCOCT（*name,*coct,*p）--释放控制器
releaseDCT（）--释放设备
addChannel（charname[]）--增加通道
addController（*name,*chct）--增加控制器
addDevice（*name,*coct）--增加设备
deleteDCT（charnameDCT[]）--删除设备
deleteCOCT（charnameCOCT[]）--删除控制器
deleteCHCT（charnameCHCT[]）--删除通道
displayDCT（）--显示设备
3.3.磁盘调度
3.2.1.功能模块图
图3.3磁盘调度功能模块图
3.2.1.相关函数
Sort（intArray[],intn）------冒泡排序算法,从小到大排序
Output（intTrack[],intNum）------输出磁道请求顺序
FCFS（intTrack[],intNum）------先来先服务调度算法
SSTF（intTrack[],intNum）------最短寻道时间优先调度算法
SCAN（intTrack[],intNum）------扫描调度算法
C_SCAN（intTrack[],intNum）------循环扫描调度算法
4.详细设计
4.1.进程调度
4.1.1进程创建
（1）核心代码
voidcreateProcess（）{
printf（"\nname:
"）;
scanf（"%s",name）;
printf（"size:
"）;
scanf（"%d",&size）;
printf（"\n"）;
enqueue（id++,name,size,ready）;//用进队函数将进程放入就绪队列if（running==0）{//如果没有正在执行的进程，则将等待队列中就绪进程调入执行
running=dequeue（ready）;
}
（2）测试结果
图4.1.1进程管理主界面
图4.1.2进程创建前图4.1.3进程创建后
4.1.2进程切换
（1）核心代码
voidswitchProcess（）{
if（running!
=0&&ready->next!
=0）
{
enqueue（running->id,running->name,running->size,ready）;//将正在执行的进程放入就绪队列
running=dequeue（ready）;//将就绪队列中第一个进程调入执行
}
else
printf（"没有可切换的进程\n"）;
}
（2）测试结果
图4.1.4进程切换前图4.1.5进程切换后
图4.1.6没有可切换的进程
4.1.3进程阻塞
（1）核心代码
voidblockProcess（）{
if（running==0）
printf（"没有可阻塞的进程\n"）;
else
{
enqueue（running->id,running->name,running->size,blocked）;//将正在执行的进程挂入阻塞队列
running=0;
if（ready->next==0）
printf（"没有可执行的进程\n"）;
else
running=dequeue（ready）;
}
}
（2）测试结果
图4.1.7进程阻塞前图4.1.8进程阻塞后
图4.1.9没有可阻塞的进程
4.1.4进程唤醒
（1）核心代码
voidwakeupProcess（）{
if（blocked->next==0）
printf（"没有可激活的进程"）;
else
{
enqueue（blocked->next->id,blocked->next->name,blocked->next->size,ready）;
dequeue（blocked）;
if（running==0）
running=dequeue（ready）;
}
}
（2）测试结果
图4.1.10进程唤醒前图4.1.11进程唤醒后
图4.1.12没有可唤醒的进程
4.1.5进程结束
（1）核心代码
voidterminateProcess（）{
if（running==0）{
printf（"没有需要结束的进程\n"）;
}
else{
running=dequeue（ready）;
}
}
（2）测试结果
图4.1.13进程结束前图4.1.14进程结束后
图4.1.15没有可结束的进程
4.1.6进程显示
（1）核心代码
voiddisplayProcessstatus（）{
printf（"--------就绪状态--------\n"）;
if（ready->next==0）
printf（"当前没有进程在该状态\n"）;
if（ready->next!
=0）
{
q=ready->next;
while（ready->next!
=0）
{
printf（"%s",ready->next->name）;
printf（"%d\n",ready->next->size）;
ready->next=ready->next->next;
}
ready->next=q;
}
printf（"--------执行状态--------\n"）;
if（running==0）printf（"当前没有进程在该状态\n"）;
if（running!
=0）
{
printf（"%s",running->name）;
printf（"%d\n",running->size）;
}
printf（"--------阻塞状态--------\n"）;
if（blocked->next==0）printf（"当前没有进程在该状态\n\n"）;
if（blocked->next!
=0）
{
p=blocked->next;
while（blocked->next!
=0）
{
printf（"%s",blocked->next->name）;
printf（"%d\n",blocked->next->size）;
blocked->next=blocked->next->next;
}
blocked->next=p;
}
}
（2）测试结果
图4.1.16进程显示结果
4.2.设备分配
4.2.1.设备分配
（1）核心代码
voidallocateCHCT（structCHCT*chct,structPCB*p）//分配CHCT
{
if（chct->occupied!
=0）//如果通道被占用
{
printf（"不能分配通道\n"）;
addProcesstoWaiting（chct->waiting,p）;//添加进程到通道等待队列
}
else
{
chct->occupied=p;
printf（"分配成功！
\n"）;
}
add（blocked,p）;
if（ready!
=0）
running=dequeue（ready）;
else
running=0;
}
//分配COCT
voidallocateCOCT（structCOCT*coct,structPCB*p）
{
if（coct->occupied!
=0）{
printf（"不能分配控制器\n"）;
addProcesstoWaiting（coct->waiting,p）;
add（blocked,p）;
if（ready!
=0）
running=dequeue（ready）;
else
running=0;
return;
}else{
coct->occupied=p;
allocateCHCT（coct->chct,p）;//已分配控制器请求分配通道
}
}
//分配DCT
voidallocateDCT（）{
charnameDCT[10];
printf（"请输入设备名称：
"）;
scanf（"%s",nameDCT）;
structDCT*dct=findDCT（nameDCT）;
structPCB*p=running;
if（dct!
=NULL&&p!
=NULL）
{
if（dct->occupied!
=0）{
printf（"不能分配设备\n"）;
addProcesstoWaiting（dct->waiting,p）;
add（blocked,p）;
if（ready!
=0）
running=dequeue（ready）;
else
running=0;
return;
}else{
dct->occupied=p;
allocateCOCT（dct->coct,p）;//设备分配成功请求分配控制器
}
}
elseprintf（"发生错误!
\n"）;
}
（2）测试结果
图4.2.1设备管理主界面
请求设备顺序为：
process1-->input1（成功）
升级会员 