南通大学操作系统课程设计报告书 计算机专业

南通大学计算机科学与技术学院操作系统课程设计报告书班级_计091_姓名_庄林祥_指导教师戴树贵目录设计要求3设计实现3主界面3A作业调度的三个算法3B银行家算法4C页面调度算法5D驱动调度算法6实现原理8A作业调度的三个算法8一、任务8二、要求8三、原理8四、数据结构8五、实现方法11六、运行结果16B银行家算法16一、任务16二、要求16三、原理16四、数据结构17五、实现方法18六、运行结果19C页面调度算法22一、任务22二、要求22三、原理22四、数据结构22五、实现方法25六、运行结果28D驱动调度算法31一、任务31二、要求31三、原理31四、数据结构32五、实现方法33六、运行结果34心得35设计要求将本学期的四次实验集成实现A实验一为作业调度的三个算法B实验二为银行家算法C实验三为页面替换的三个算法D实验三为驱动调度的三个算法设计实现主功能界面，如图1图1A作业调度的三个算法点击作业调度算法，如图11图11点击预定义，如图111图111点击自定义，如图112图112B银行家算法点击银行家算法，如图21图21点击预定义，如图211图211点击自定义，如图212图212C实验三为页面替换的三个算法点击页面替换算法，如图31图31点击预定义，如图311图311点击自定义，如图312图312D实验三为驱动调度的三个算法点击驱动调度算法，如图41图41点击预定义，如图411图411点击自定义，如图412图412实现原理A作业调度的三个算法一、任务实现作业调度的三个算法A先来先服务算法（FCFS）。B最短作业优先算法（SJF）。C响应比最高优先者优先算法（HRRF）。二、要求1实现对三种算法的模拟实现。2分别计算出三种算法的平均作业周转时间、平均带权作业周转时间。三、原理A先来先服务算法（FCFS）按作业到达CPU时间先后顺序进行非剥夺式调度，先到达CPU的作业先被执行。B最短作业优先算法（SJF）忽视作业的等待时间，按作业所需要的CPU运行时间长短进行非剥夺式调度，CPU运行时间短的作业先被执行。C响应比最高优先者优先算法（HRRF）介乎FCFS算法和SJF算法之间的折中的非剥夺式算法，既考虑作业的等待时间，又作业的处理时间。按如下计算方法得出每轮各作业响应比响应比作业周转时间/作业处理时间1作业等待时间/作业处理时间从中选出响应比最大的作业执行，再进行下一轮剩下未被执行的作业响应比计算，直到剩余最后一个作业完止。四、数据结构CLASSJOBPUBLICCHARJOBNAME/JOBNAME/作业名INTID/ORDERTOEXECUTE/执行序号FLOATARRIVETIME/到达CPU时间FLOATCPUTIME/作业处理时间FLOATRESPONSERATIO/响应比（执行HRRF算法时起作用）JOBNEXT/指向下一个创建的作业（不代表到达/CPU时间）JOBORDERNEXT/指向下一个最近的到达CPU的作业JOB/对象创建时作业初始化，全部置0或置空JOBNAMENULLID0ARRIVETIME0CPUTIME0RESPONSERATIO0NEXTNULLORDERNEXTNULL结构图原始链表（NEXT指针按创建先后顺序排列）五、实现方法将进程中的作业按到达CPU时间从小到大排列，重新链接作业。新链表（ORDERNEXT指针按到达CPU时间从小到大排列）以下用到的作业顺序皆指新链表中的作业顺序A先来先服务算法（FCFS）新链表中作业已经按作业按到达CPU时间从小到大排列，只需从第一个作业（头结点）依次调度至最后一个作业（尾结点）。过程示意图IDJOBNAMEARRIVETIMECPUTIMERESPONSERATIONEXT指针ORDERNEXT指针NULLNULL作业作业作业作业作业作业NULL执行第一个作业执行到了最后一个作业B最短作业优先算法（SJF）S1执行一轮查找，筛选出小于已执行作业累加总CPU时间（第一个作业之前累加CPU时间认为是0）的作业列。S2从S1中筛选出的作业列中选出CPU时间（CPUTIME）最小的作业送去CPU执行，完毕后将此作业累加到总CPU时间。S3重复上述步骤，直至作业全部执行完毕。过程示意图第一轮查找，只有第一个作业符合，取出执行第二轮查找，筛选出小于已执行作业累加总CPU时间，找出CPU时间最小的作业，取出执行第N轮查找，筛选出小于已执行作业累加总CPU时间，找出CPU时间最小的作业，取出执行最后一轮查找，筛选出小于已执行作业累加总CPU时间，找出CPU时间最小的作业，取出执行C响应比最高优先者优先算法（HRRF）S1执行第一个作业，完毕后计算剩下的各作业响应比。S2执行S1中响应比最大的作业，完毕后计算剩下的各作业响应比。S3重复上述步骤，直至剩余一个作业。S4执行最后一个作业。作业作业作业作业作业作业NULL作业作业作业作业作业作业NULL作业作业作业作业作业作业NULL作业作业作业作业作业作业NULL作业过程示意图先执行第一个作业，完毕后计算剩下的各作业响应执行响应比最大的作业，完毕后计算剩下的各作业响应比执行响应比最大的作业，完毕后计算剩下的各作业响应比重复步骤，执行作业，计算响应比执行剩的下最后一个作业六、运行结果1第一组测试数据，如图11图11执行FCFS算法，如图12图12作业作业作业作业作业作业作业NULL作业作业作业作业作业作业NULL作业作业作业作业作业作业NULL执行SJF算法，如图13图13筛选出符合条件的作业，执行CPU时间最小的作业，如图14图14执行HRRF算法，如图15图15执行预选作业，计算剩余作业响应比，如图16图162第二组测试数据，如图21图21执行FCFS算法，如图22图22执行SJF算法，如图23图23筛选出符合条件的作业，执行CPU时间最小的作业，如图24，图25图24图25执行HRRF算法，如图26图26执行预选作业，计算剩余作业响应比，如图27，图28图27图28B银行家算法一、任务编程实现实现银行家算法二、要求实现银行家算法模拟实现。三、原理银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。要解释银行家算法，必须先解释操作系统安全状态和不安全状态。安全序列是指一个进程序列P1，PN是安全的，如果对于每一个进程PI1IN），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程PJJI当前占有资源量之和。安全状态如果存在一个由系统中所有进程构成的安全序列P1，PN，则系统处于安全状态。安全状态一定是没有死锁发生。不安全状态不存在一个安全序列。不安全状态不一定导致死锁。我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。为保证资金的安全，银行家规定1当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；2顾客可以分期贷款，但贷款的总数不能超过最大需求量；3当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；4当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。四、数据结构1在程序中使用的资源基本结构及基本方法SOURCE结构图2每个进程的构成PROCESS结构图3程序中使用到的所有数据集合DATA结构图SOURCEALLOCATIONSOURCECLAIMSOURCECLAIM_ALLOCATIONSOURCECURRENTAVAILINTR2INTR1INTR3VOIDSETSOURCEVOIDADDVOIDSUBBOOLLOWERSOURCESUMPROCESSPSOURCEAVAILABLESOURCEASKINTPLENGTHINTRULERVOIDCLEARPROCESS4初始化或设置数据方法集合DATAINIT结构图5显示方法集合DISPLAY结构图6FINDSAFELIST结构图五、实现方法在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。设进程PI提出请求ASKR1,R2,R3，则银行家算法按如下规则进行判断。1如果PI的ASKR1,R2,R3PICLAIMR1,R2,R3ALLOCATIONR1,R2,R3，则转（2；否则，出错。2如果PI的ASKR1,R2,R3AVAILABLER1,R2,R3，则转（3；否则，出错。VOIDSETASKVOIDINITLENGTHVOIDINITSUMVOIDINITAVAILVOIDINITPROCESSVOIDDISPLAYAVAILABLEVOIDDISPLAYSOURCEVOIDDISPLAYPROCESSVOIDDISPLAYSAFELISTVOIDDISPLAYRESULTBOOLEXSITSAFELISTBOOLCHECKLISTINTFINDSAFELIST3系统试探分配资源，修改相关数据AVAILABLER1,R2,R3ASKR1,R2,R3PIALLOCATIONR1,R2,R3ASKR1,R2,R3PICLAIMR1,R2,R3ALLOCATIONR1,R2,R3ASKR1,R2,R34系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。六、运行结果测试数据，如图11图11执行进程P1请求资源ASK1,0,2，如图12图12查看一个安全序列详情，如图13图13不查看一个安全序列，如图14图14执行进程P4请求资源ASK3,3,0，如图15图15执行进程P0请求资源ASK0,2,0，如图16图16不请求资源输入N，退出C页面调度算法一、任务A最优替换算法OPTB先进先出调度算法FIFOC最近最少调度算法LRU二、要求1实现对页面替换算法的模拟实现2计算缺页次数和缺页中断率三、原理目前有许多页面调度算法，本实验主要涉及先进先出调度算法、最近最少调度算法、最近最不常用调度算法。本实验使用页面调度算法时作如下假设，进程在创建时由操作系统为之分配一个固定数目物理页，执行过程中物理页的数目和位置不会改变。也即进程进行页面调度时只能在分到的几个物理页中进行。下面对各调度算法的思想作一介绍。A最优替换算法OPT选择将来最久不被访问的页面作为被替换的页面它就是一种比较好的页面替换算法。B先进先出调度算法FIFO先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。C最近最少调度算法LRU先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。缺页调度次数和缺页中断率计算缺页中断次数是缺页时发出缺页中断的次数缺页中断率缺页中断次数/总的页面引用次数100四、数据结构1页框结构PAGEFRAME结构图2页结构PROCESS结构图3程序中使用到的所有数据集合DATA结构图4初始化或设置数据方法集合SETBASEINFO结构图INTIDINTPAGEIDINTIDINTVISITEDCOUNTINTUNVISITEDCOUNTBOOLREPLACEINTSTAYTIMEINTNEXTSITEINTPFLENGTHPAGEFRAMEPFPAGEPINTPLENGTHINTPLENGTHINTPFLOGICRULERINTPAGELACKCOUNTVOIDSETPAGEVOIDSETPAGEFRAME5METHOD结构图OPT,FIFO,LRU结构如下列图6OPT，FIFO，LRU结构图7CONTROL结构图8显示方法集合DISPLAY结构图VOIDDISPLAYLOGICRULERVOIDDISPLAYPAGELISTVOIDDISPLAYPAGELACKVOIDDISPLAYPAGEFRAMETVOIDDISPLAYRESULTINTREPLACEBOOLFINDPAGEINTLONGESTTIMEINTMOSTUNVISITEDVOIDSETPFLOGICRULERINTGETDIEPFVOIDSETPFLOGICRULER（）/方法重写继承METHODFIFOFIFOOPTOPTLRULRU五、实现方法A最优替换算法OPTY有页面请求吗结束找到了吗执行该页修改该页框内页面下一次在序列中位置NEXTSITE调入当前页面请求在页框中查找该页选出页框页面下一次位置最大的页框，淘汰，替换进当前页面请求YN开始NB先进先出调度算法FIFOY有页面请求吗结束找到了吗执行该页，页框驻留时间加1调入当前页面请求在页框中查找该页YN开始N选出页框页面驻留时间最大页框,淘汰,替换进当前请求页面,页框驻留时间STAYTIME归1执行该页，页框驻留时间STAYTIME加1其他页框驻留时间STAYTIME加1C最近最少调度算法LRUY有页面请求吗结束找到了吗执行该页，页框驻留时间加1调入当前页面请求在页框中查找该页YN开始N其它页框未访问时间UNVISITEDCOUNT加1选出页框页面未访问时间最大页框,淘汰,替换进当前页面请求，页框未访问时间UNVISITEDCOUNT归1执行该页，页框未访问时间UNVISITEDCOUNT归1六、运行结果测试数据，如图11图11选择最佳页面替换算法，如图12图12选择先进先出页面替换算法，如图13图13最近最少调度算法，如图14图14输入0，退出D驱动调度算法一、任务实现驱动调度的三个算法A先入先出算法（FIFO）B电梯调度算法（ELEVATORALGORITHM）C扫描算法（SCANALGORITHM）二、要求1实现对三种算法的模拟实现。2分别计算出三种算法的经过磁道数。三、原理磁盘驱动调度对磁盘的效率有重要影响。磁盘驱动调度算法的好坏直接影响辅助存储器的效率，从而影响计算机系统的整体效率。A先入先出算法（FIFO）总是严格按时间顺序对磁盘请求予以处理。算法实现简单、易于理解并且相对公平，不会发生进程饿死现象。但该算法可能会移动的柱面数较多并且会经常更换移动方向，效率有待提高B电梯调度算法（ELEVATORALGORITHM）总是将一个方向上的请求全部处理完后，才改变方向继续处理其他请求。C扫描算法（SCANALGORITHM）总是从最外向最里（或最里向最外）进行扫描，然后在从最里向最外（或最外向最里）扫描。该算法与电梯调度算法的区别是电梯调度在没有最外或最里的请求时不会移动到最外或最里柱面。四、数据结构1在程序中使用的