《基于Linux的设备分配及磁盘调度算法说明书》由会员分享，可在线阅读，更多相关《基于Linux的设备分配及磁盘调度算法说明书（57页珍藏版）》请在金锄头文库上搜索。
1、基于Linux的设备分配及磁盘调度算法说明书中北大学软件学院实训说明书实训名称：操作系统课程设计基于Linux的设备分配题目名称：及磁盘调度算法专业：软件工程班级：12210A02小组成员学号：1221010516学号：1221010543学号：1221010618学号：1221010707指导教师：姓名：高田田成绩：姓名：王浩成绩：姓名：许嘉阳成绩:姓名：王晋英成绩:薛海丽中北大学软件学院实训说明书2015年1月任务分工情况说明姓名分工组长高田田负责小组分工，资料查询，参与整体需求分析及概要设计，完成设备分配部分的详细设计及代码。完成代码整合及主函数的编写。完成小组说明书文档整理工作0组员王
2、浩资料杳询，参与整体需求分析及概要设计，完成磁盘调度中先来先服务(FCFS)和循环扫描调度算法(CSCAN)部分的详细设计及代码，协助完成设备分配。组员许嘉阳资料查询，参与整体需求分析及概要设计，完成磁盘调度中最短寻道时间优先算法(SSTF)和扫描调度算法(SCAN)部分的详细设计及代码代码，协助完成设备分配。组员王晋英资料查询，参与整体需求分析及概要设计，完成进程控制部分的详细设计及代码编写。目录1 .绪论02 .需求分析02.1. 目的03 .2.内容13.1. 2.1.进程调度11.1 2.2.设备分配11.2 2.3.磁盘调度21.3 .概要设计32. 进程调度32.1 功能模块图32
3、.2 相关函数44.22.设备分配41 .22.1.功能模块图54 .2.1.相关函数53. 3磁盘调度62.功能模块图62.1. 相关函数6详细设计61 .进程调度61.1.1 进程创建61.1.2 进程切换84.1.3进程阻塞94进程唤醒105进程结束106进程显示115.2.设备分配134.32.1.设备分配134.32.2.设备释放164.32.3.设备添加194.2.4.设备删除214.2.5.设备显示244. 3.磁盘调度261. 3.1.先来先服务算法274. 3.2最短寻道时间优先算法285. 3.3扫描算法294.3.4 循环扫描算法304.3.5 调用四种算法比较3144心
4、得体会3245参考文献344.6.源代码34论随着信息技术的发展，Linux操作系统得到了前所未有的广泛应用。Linux被应用到包括便携式电子设备、生物科技以及航天科技等各种领域。显然不同应用领域对Linux系统的实时性、公平性和吞吐量等性能有着不同的要求，而进程调度算法对Lmux系统性能起着至关重要的作用，用来创建进程，撤销进程,实现进程转换，它提供了可运行得进程之间复用CPU的方法，并为创建的进程在设备分配功能中提供所必要设备。同时，Internet的飞速发展使数据增长，这给数据增长带来了很大的压力。对数据的访问性能、数据传输性能、数据管理性能和存储扩展等方面都提出了比过去更高的要求。这需
5、要一个既能满足大容量信息存储、能适应将来容量扩充要求的存储器管理系统，又可以大大提高传输速率，还可以完成信息高速处理的计算机体系架构。而随着技术的发展，设备管理技术和磁盘调度技术成为提高数据处理和数据传输的关键因素。因此，研究海量管理系统中的分配管理技术和磁盘调度策略具有重要意义。本次课程设计就这些问题展开了一些有意义的研究工作。求分析目的通过本实验可以加深理解有关进程控制块(PCB)、进程队列的概念，体会并解创建进程、切换进程、阻塞进程、唤醒进程、结束进程、显示进程的具体实施过程。完成设备管理功能的模拟，掌握包括通道和控制器的添加和删除，设备的添加、删除，设备的分配和回收。通过设计一个磁盘调
6、度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解。2.2.内容2.2.1.进程调度2.2.2.1.功能分析每个进程有一个进程控制块(PCB)表示。进程控制块包含如下信息:进程名、进程编号、进程的大小和进程的临接PCB的地址。每个进程的状态可以是就绪(ieady).执行(nnmiiig)和阻塞(block)三种状态之O进程创建，由系统生成一个PCB结点，用进队函数放入就绪队列。如果没有正在执行的进程，则将等待队列中就绪进程调入执行。进程切换，通过函数实现将运行队列
7、中的执行进程调入就绪队将等待队列列，中就绪进程调入执行。进程阻塞，通过函数实现将运行队列中的执行进程调入阻塞队列，将等待队列中就绪进程调入执行。进程唤醒，通过函数实现将阻塞队列中的阻塞进程调入就绪队列，将等待队列中就绪进程调入执行。进程结束，通过函数实现将就绪队列中的就绪进程抢占运行队列。进程显示，根据队列进程的存储特性，顺序查找到每个进程并依次输出每个进程的名称和大小。所创建进程将会在设备分配功能中为其提供所需必要设备。2.2.2.1.数据结构进程控制块(PCB)2.2.2设备分配2.2.2.功能分析第1员.共63页设备管理子系统涉及到通道控制表（CHCT）、控制器控制表（COCT）和设备控
8、制表（DCT）来体现输入输出系统。实现上述设备、控制器以及通道的层次关系，同时能够添加或删除新的设备、控制器或通道。（3）通过键盘命令模拟进程执行过程中提出的设备分配或释放请求，并为此请求分配或释放设备。分配设备成功后可将进程状态调整为阻塞，释放设备后变为就绪状态。（4）分配设备时应如果该设备己被其它进程占用，则设备分配失败，请求进程进入阻塞状态，同时等待该设备的释放。如果设备空闲，进程占用设备的同时还应提出申请控制器请求，直到与设备相关的通道都已申请成功为止。（5）设备、控制器或通道的释放应引起对应节点的等待队列中的第一个阻塞进程被唤醒。如果被唤醒的进程还未完成申请操作，应继续执行上节点的申
9、请操作。2.2.2.2.数据结构设备控制表（DCT）控制器控制表（COCT）通道控制表（CHCT）2.2.3.磁盘调度系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）。223.1先来先服务算法（FCFS）这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比校多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较
10、长，但各进程得到服务的响应时间的变化幅度较小。2.2.3.2最短寻道时间优先算法（SSTF）第#页共63页该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。2. 2.3.3扫描算法(SCAN)扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一
11、个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法,两侧磁道被访问的频率仍低于中间磁道。3. 2.3.4循环扫描算法(CSCAN)循环扫描算法是对扫描算法的改进。如果对磁道的
12、访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。要设计3.进程调度第3贞.共63页进程管理第#页共63页磁福度图3.1进程管理功能模块图3.12相关函数voidenqueue(mtid.cliar*name.mtsize,stmetPCB*head)进程进入队列(就绪队列、阻塞队列)stnic
13、tPCB*dequeue(stnictPCB*head)进程移出队列voidcreateProcess()创建进程voidswitcliProcess()一进程切换voidblockProcess()阻塞进程voidvvakeupProcess()唤醒进程voidtenninateProcess()结束进程voiddisplayProcessstatus()显示进程状态3.2.功能模块第页共63页8nffluSI添加设备分配图3-2设备分配功能模块图4. 2.1.相关函数stnictDCT*findDCT(charname)用设备名查找设备stnictCOCT*fiiidController(
14、charname)用控制器名查找控制器structCHCT*fiiidCliaiinel(chai-name)用通道名查找通道addProcesstoWainng(*waitmg,*p)进入进程等待队列add(*head,*node)入队歹stnictPCB*gjFust(*head)获得队列里的第一个进程allocateCHCT(*chct,*p)分配CHCTallocateCOCT(*coct,*p)分酉己COCT211(2闻0(?1()分配DCTreleaseCHCT(*name,*clict,*p)释放通道releaseCOCT(*iiame,*coct,*p)释放控制器releaseDCT()一释放设备addCliaimel(charname)增加通道addController(*naine,*chct)增加控制器addDevice(*nanie,*coct)增加设备deleteDCT(chaiuanieDCT口)删|除设备deleteCOCT(charnameCOCT)一删除控制器ddeteCHCT(chainameCHCTE)删除通道displayDCT()显示设备3.3.磁盘调度3.2.1.功能模块图81s (si)磁盘调度图3.3磁盘调度功能模块图3 .2.1.相关函数Sort(mtAiiay,mtn)冒泡排
