操作系统课程设计报告_13.docVIP

南通大学 操作系统课程设计报告 学院：计算机科学与技术学院 班级： 学号 姓名： 指导老师 课设时间：2013.7.3~2013.7.5 实验目的 操作系统是计算机系统的一个重要系统软件。我们在本课程的实验过程中，了解实际操作系统的工作过程，在实践中加深对操作系统原理的理解，在模拟计算机操作系统的基础上，利用代码实现操作系统的处理机调度算法，页面替换算法，磁盘移动臂算法，银行家算法最终的集成，在界面上进行各算法的实现。 概要设计 在多道程序运行环境下，进程数目一般多于处理机数目，使得进程要通过竞争来使用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之运行，分配处理机的任务是由进程调度程序完成的。一个进程被创建后，系统为了便于对进程进行管理，将系统中的所有进程按其状态，将其组织成不同的进程队列。于是系统中有运行进程队列、就绪队列和各种事件的进程等待队列。进程调度的功能就是从就绪队列中挑选一个进程到处理机上运行。进程调度的算法有多种，常用的有优先级调度算法、先来先服务算法、时间片轮转算法。这里我们主要实现的是先来先服务算法和优先级调度算法。 处理机调度算法 设计一个结构体，用于抽象进程的各种属性，其中包括进程标志符，进程优先级，cpu时间统计，运行所需时间，进程状态。 再设计一个结构体，用于模拟就绪队列，其具体方法采用链表形式。 对于先到先服务算法，判断就绪队列中每个进程的进程号，根据进程号的顺序依次给进程分配CPU，直到所有进程执行完毕为止 对于优先度调度算法，首先根据所有进程的有限度，依次按照其优先度的大小按照降序排序的方式依次插入就绪队列，每当一个进程获得CPU并执行时，优先级降低2，每运行一次 CPU时间增加4，当所获得的CPU时间大于或者等于其所需的CPU时间时，进程执行完毕，否则变换就绪队列中进程顺序，使之保持进程优先级按降序排序。 每个进程获得CPU时间并执行完毕之后，打印出进程队列中的信息，以便查看就绪队列中的进程信息。 2.页面替换算法 (1)在进程运行过程中，若其所访问的页面不存在内存而需要把它们调入内存，但内存已无空闲时，为了保证该进程能够正常运行，系统必须从内存中调出一页程序或数据送磁盘的对换区中。但应调出哪个页面，需根据一定的算法来确定，算法的好坏，直接影响到系统的性能。? (2) 一个好的页面置换算法，应该有较低的页面更换频率。?? 假设分给一作业的物理块数为3?，页面数为20个。?页面号为(20个)：? 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1?? 先进先出(FIFO)置换算法的思路 该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序连接成一个队列，并设置一个替换指针，使它总指向最老的页面。?? 最近久未使用(LRU)置换算法的思路 最近久未使用置换算法的替换规则，是根据页面调入内存后的使用情况来进行决策的。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间，当需淘汰一个页面的时候选择现有页面中其时间值最大的进?行淘汰。? ? 最佳（OPT）置换算法的思路 其所选择的被淘汰的页面，奖是以后不使用的，或者是在未来时间内不再被访问的页面， 采用最佳算法，通常可保证获得最低的缺页率。 3.移动臂算法 磁盘调度的目标是使磁盘的平均寻道时间最少。也正因为这样，我们有必要对各算法进行模拟，进而比较、分析、了解。 本实验设计的目的是通过设计一个磁盘调度模拟系统，以加深对最短寻道时间优先（SSTF）、先来先服务（FCFS）等磁盘调度算法的理解。让我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强动手能力。 4.银行家算法 当某个进程提出资源请求时，假定先分配给它，之后调用系统安全性检查算法，进行系统安全性检查。若系统安全，假分配变为真分配。否则作废假分配，让进程等待 （1）如果Requesti＜or =Need,则转向步骤(2)；否则，认为出错，因为它所需要的资源数已超过它所宣布的最大值。 （2）如果Request＜or=Available,则转向步骤（3）；否则，表示系统中尚无足够的资源，进程必须等待。 （3）系统试探把要求的资源分配给进程Pi,并修改下面数据结构中的数值： ???Available=Available-Request[i]; ????Allocation=Allocation+Request; Need=Need-Request; (4)系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。 三.详细设计 1处理机调度 进程的数据结构如下： struct PCB {ch