操作系统课程设计

1、 操作系统课程设计报 告 书 目 录设计要求.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五、

2、实现方法.33六、运行结果.34心得.35设计要求将本学期的四次实验集成实现a.实验一为作业调度的三个算法b.实验二为银行家算法c.实验三为页面替换的三个算法d.实验三为驱动调度的三个算法设计实现主功能界面，如图1图1a.作业调度的三个算法点击作业调度算法，如图1.1图1.1点击预定义，如图1.1.1图1.1.1点击自定义，如图1.1.2图1.1.2b.银行家算法点击银行家算法，如图2.1图2.1点击预定义，如图2.1.1图2.1.1点击自定义，如图2.1.2图2.1.2c.实验三为页面替换的三个算法点击页面替换算法，如图3.1图3.1点击预定义，如图3.1.1图3.1.1点击自定义，如图3.

3、1.2图3.1.2d.实验三为驱动调度的三个算法点击驱动调度算法，如图4.1图4.1点击预定义，如图4.1.1图4.1.1点击自定义，如图4.1.2图4.1.2实现原理a.作业调度的三个算法一、任务：实现作业调度的三个算法a.先来先服务算法（fcfs）。b.最短作业优先算法（sjf）。c.响应比最高优先者优先算法（hrrf）。二、要求：1.实现对三种算法的模拟实现。2.分别计算出三种算法的平均作业周转时间、平均带权作业周转时间。三、原理：a.先来先服务算法（fcfs）按作业到达cpu时间先后顺序进行非剥夺式调度，先到达cpu的作业先被执行。b.最短作业优先算法（sjf）忽视作业的等待时间，按作

4、业所需要的cpu运行时间长短进行非剥夺式调度，cpu运行时间短的作业先被执行。c.响应比最高优先者优先算法（hrrf）介乎fcfs算法和sjf算法之间的折中的非剥夺式算法，既考虑作业的等待时间，又作业的处理时间。按如下计算方法得出每轮各作业响应比：响应比 = 作业周转时间 / 作业处理时间 = 1 + 作业等待时间 / 作业处理时间从中选出响应比最大的作业执行，再进行下一轮剩下未被执行的作业响应比计算，直到剩余最后一个作业完止。四、数据结构：class jobpublic:char *jobname;/jobname/作业名int id;/ordertoexecute/执行序号float ar

5、rivetime;/到达cpu时间float cputime;/作业处理时间float responseratio;/响应比（执行hrrf算法时起作用）job * next;/指向下一个创建的作业（不代表到达/cpu时间）job *ordernext;/指向下一个最近的到达cpu的作业job ( )/对象创建时作业初始化，全部置0或置空jobname=null;id=0;arrivetime=0;cputime=0;responseratio=0;next=null;ordernext=null;结构图idjobnamearrivetimecputimeresponseratio*next 指

6、针*ordernext 指针原始链表（next 指针按创建先后顺序排列）null五、实现方法：将进程中的作业按到达cpu时间从小到大排列，重新链接作业。新链表（ordernext 指针 按到达cpu时间从小到大排列）null以下用到的作业顺序皆指新链表中的作业顺序a. 先来先服务算法（fcfs）新链表中作业已经按作业按到达cpu时间从小到大排列，只需从第一个作业（头结点）依次调度至最后一个作业（尾结点）。过程示意图：作业作业作业作业作业作业null执行第一个作业 作业作业作业作业作业作业null执行到了最后一个作业b. 最短作业优先算法（sjf）s1.执行一轮查找，筛选出小于已执行作业累加总c

7、pu时间（第一个作业之前累加cpu时间认为是0）的作业列。s2.从s1中筛选出的作业列中选出cpu时间（cputime）最小的作业送去cpu执行，完毕后将此作业累加到总cpu时间。s3.重复上述步骤，直至作业全部执行完毕。过程示意图：作业作业作业作业作业作业null第一轮查找，只有第一个作业符合，取出执行作业作业作业作业作业作业null第二轮查找，筛选出小于已执行作业累加总cpu时间，找出cpu时间最小的作业，取出执行作业作业作业作业作业作业null第 n 轮查找，筛选出小于已执行作业累加总cpu时间，找出cpu时间最小的作业，取出执行作业最后一轮查找，筛选出小于已执行作业累加总cpu时间，找

8、出cpu时间最小的作业，取出执行c. .响应比最高优先者优先算法（hrrf）s1.执行第一个作业，完毕后计算剩下的各作业响应比。s2.执行s1中响应比最大的作业，完毕后计算剩下的各作业响应比。s3.重复上述步骤，直至剩余一个作业。s4.执行最后一个作业。过程示意图：作业作业作业作业作业作业null先执行第一个作业，完毕后计算剩下的各作业响应作业作业作业作业作业作业null执行响应比最大的作业，完毕后计算剩下的各作业响应比作业作业作业作业作业作业null执行响应比最大的作业，完毕后计算剩下的各作业响应比重复步骤，执行作业，计算响应比 作业执行剩的下最后一个作业六、运行结果：1.第一组测试数据，如

9、图1-1图 1-1执行fcfs算法，如图1-2图1-2执行sjf算法，如图1-3图1-3筛选出符合条件的作业，执行cpu时间最小的作业，如图1-4图1-4执行hrrf算法，如图1-5图1-5执行预选作业，计算剩余作业响应比，如图1-6图1-62.第二组测试数据，如图2-1图2-1执行fcfs算法，如图2-2图2-2执行sjf算法，如图2-3图2-3筛选出符合条件的作业，执行cpu时间最小的作业，如图2-4，图2-5图2-4图2-5执行hrrf算法，如图2-6图2-6执行预选作业，计算剩余作业响应比，如图2-7，图2-8图2-7图2-8b.银行家算法一、任务：编程实现实现银行家算法二、要求：实现

10、银行家算法模拟实现。三、原理：银行家算法是一种最有代表性的避免死锁的算法。在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结构。 要解释银行家算法，必须先解释操作系统安全状态和不安全状态。 安全序列是指一个进程序列p1，pn是安全的，如果对于每一个进程pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程pj (j i )当前占有资源量之和。安全状态：如果存在一个由系统中所有进程构成的安全序列p1，pn，则系统处于安全状态。安全状态一定是没有

11、死锁发生。不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。 为保证资金的安全，银行家规定： (1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客； (2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量； (3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款； (4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金. 操作系统按照银行家制定的规则为进程分配资源，

12、当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源，否则也要推迟分配。四、数据结构：1.在程序中使用的资源基本结构及基本方法source结构图int r2int r1int r3void setsource( )void add( )void sub( ) bool lower( )2.每个进程的构成process结构图source allocationsource c

13、laimsource claim_allocationsource currentavail3.程序中使用到的所有数据集合data结构图source sumprocess *psource availablesource askint plengthint * rulervoid clearprocess( )4.初始化或设置数据方法集合datainit结构图void setask( )void initlength( )void initsum( )void initavail( )void initprocess( )5.显示方法集合display结构图void displayavaila

14、ble( )void displaysource( )void displayprocess( )void displaysafelist( )void displayresult( )6.findsafelist结构图bool exsitsafelist( )bool checklist( )int findsafelist( )五、实现方法：在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。 银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最

15、具有代表性的避免死锁的算法。 设进程pi提出请求ask(r1,r2,r3)，则银行家算法按如下规则进行判断。 (1)如果pi的ask (r1,r2,r3) = pi( claim(r1,r2,r3)-allocation(r1,r2,r3)，则转（2)；否则，出错。 (2)如果pi的ask (r1,r2,r3) = available(r1,r2,r3)，则转（3)；否则，出错。 (3)系统试探分配资源，修改相关数据： available(r1,r2,r3) - = ask (r1,r2,r3)pi(allocation(r1,r2,r3) + = ask (r1,r2,r3)pi( clai

16、m(r1,r2,r3)-allocation(r1,r2,r3) - = ask (r1,r2,r3)(4)系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。六、运行结果：测试数据，如图1-1图 1-1执行进程p1请求资源ask(1, 0, 2)，如图1-2图1-2查看一个安全序列详情，如图1-3图1-3不查看一个安全序列，如图1-4图1-4执行进程p4请求资源ask(3, 3, 0)，如图1-5图1-5执行进程p0请求资源ask(0,2, 0)，如图1-6图1-6不请求资源输入n，退出c.页面调度算法一、任务：a. 最优替换算法optb. 先进先出调度算法

17、fifoc. 最近最少调度算法lru二、要求：1.实现对页面替换算法的模拟实现2. 计算缺页次数和缺页中断率三、原理：目前有许多页面调度算法，本实验主要涉及先进先出调度算法、最近最少调度算法、最近最不常用调度算法。本实验使用页面调度算法时作如下假设，进程在创建时由操作系统为之分配一个固定数目物理页，执行过程中物理页的数目和位置不会改变。也即进程进行页面调度时只能在分到的几个物理页中进行。 下面对各调度算法的思想作一介绍。 a.最优替换算法opt选择将来最久不被访问的页面作为被替换的页面它就是一种比较好的页面替换算法。b. 先进先出调度算法fifo 先进先出调度算法根据页面进入内存的时间先后选择

18、淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。 c.最近最少调度算法 lru先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。缺页调度次数和缺页中断率计算缺页中断次数是缺页时发出缺页中断的次数 缺页中断率=缺页中断次数/总的页面引用次

19、数*100% 四、数据结构：1. 页框结构pageframe结构图int pageidint idint visitedcountint unvisitedcountbool replaceint staytimeint nextsite2.页结构process结构图int id3.程序中使用到的所有数据集合data结构图int pflengthpageframe *pfpage *pint plengthint plengthint *pflogicrulerint pagelackcount4.初始化或设置数据方法集合setbaseinfo结构图void setpage( )void se

20、tpageframe( )5. method结构图int replace ( )bool findpage ( )int longesttime ( )int mostunvisited( )void setpflogicruler( )int getdiepf()opt, fifo, lru结构如下列图6. opt， fifo，lru结构图void setpflogicruler（）/方法重写继承method7. control结构图fifo fifoopt optlru lru8.显示方法集合display结构图void displaylogicruler ( )void displayp

21、agelist( )void displaypagelack ( )void displaypageframe t( )void displayresult( )五、实现方法：a.最优替换算法opty有页面请求吗?结束找到了吗?执行该页修改该页框内页面下一次在序列中位置nextsite调入当前页面请求在页框中查找该页选出页框页面下一次位置最大的页框，淘汰，替换进当前页面请求yn开始nb. 先进先出调度算法fifo y有页面请求吗?结束找到了吗?执行该页，页框驻留时间加1调入当前页面请求在页框中查找该页yn开始n选出页框页面驻留时间最大页框,淘汰,替换进当前请求页面,页框驻留时间staytime

22、归1执行该页，页框驻留时间staytime加1其他页框驻留时间staytime加1c.最近最少调度算法 lruy有页面请求吗?结束找到了吗?执行该页，页框驻留时间加1调入当前页面请求在页框中查找该页yn开始n其它页框未访问时间unvisitedcount加1选出页框页面未访问时间最大页框,淘汰,替换进当前页面请求，页框未访问时间unvisitedcount归1执行该页，页框未访问时间unvisitedcount归1六、运行结果：测试数据，如图1-1图 1-1选择最佳页面替换算法，如图1-2图1-2选择先进先出页面替换算法，如图1-3图1-3最近最少调度算法，如图1-4 图1-4输入0，退出d.

23、驱动调度算法一、任务：实现驱动调度的三个算法a. 先入先出算法（fifo）b. 电梯调度算法（elevator algorithm）c. 扫描算法（scan algorithm）二、要求：1.实现对三种算法的模拟实现。2.分别计算出三种算法的经过磁道数。三、原理：磁盘驱动调度对磁盘的效率有重要影响。磁盘驱动调度算法的好坏直接影响辅助存储器的效率，从而影响计算机系统的整体效率。a. 先入先出算法（fifo）总是严格按时间顺序对磁盘请求予以处理。算法实现简单、易于理解并且相对公平，不会发生进程饿死现象。但该算法可能会移动的柱面数较多并且会经常更换移动方向，效率有待提高b. 电梯调度算法（elevator algorithm）总是将一个方向上的请求全部处理完后，才改变方向继续处理其他请求。c. 扫描算法（scan algorithm）总是从最外向最里（或最里向最外）进行扫描，然后在从最里向最外（或最外向最里）扫描。该算法与电梯调度算法的区别是电梯调度在没有最外或最里的请求时不会移动到最外或最里柱面。四、数据结构：1.在