《操作系统十大算法具体内容.ppt

一、进程调度 如何从就绪队列中选择一个进程使其运行？ 从就绪队列中按一定的策略选择一个进程，使其占有处理机。 进程调度的时机 正在运行的进程运行完毕。 正在执行的进程被阻塞，加入等待队列 时间片到 高优先级的进程进入就绪队列 进程调度的评价指标 进程的等待时间 CPU的利用率 系统资源的利用率 响应时间 周转时间 一般用平均周转时间来衡量一个调度算法的好坏。 1、先来先服务法 根据进程到达就绪队列的次序，总是选择先到达的进程运行。 优点：公平性；管理简单（队列）。 看右边表格中的例子： 由于进程到达的随机性，可能使系统中的短作业等待时间长。 2、时间片轮转法（RR） 时间片：系统允许进程一次使用处理机的最长时间。 回忆：分时系统的工作原理。 工作原理：就绪队列中的进程，每次最多使用一个时间片。 硬件支持：计时器。时间片到，发生“计时中断”。 问题：时间片的大小如何确定？ 时间片的长短 就绪队列长短：越长，时间片越短。 响应时间的要求： 计算机的性能 进程切换的系统开销：一个进程让出处理机，另一个进程占有处理机。 3、进程调度算法-优先数调度法 总是从就绪队列中选择优先级最高的进程。 问题1：优先数如何确定？ 进程类别：系统进程，用户进程，前台，后台等 进程运行时间 作业的优先级等 优先数调度法 问题2：当一个更高优先级的进程到达就绪队列时，如何处理？ 抢占式 非抢占式：一旦分配CPU，就一直占用，直到主动放弃为止。 问题3：如果一个低优先级的进程在就绪队列中等待太长时间？ 动态优先数：进程的优先级随系统情况不断变化。 多级轮转调度法 时间片轮转与优先数结合。 按优先级将作业排成不同的队列。 先按优先级调度，优先级相同的，按时间片轮转。 前台作业与后台作业 交互式作业 批处理作业 二、可变分区存储管理 原理 在作业要求装入主存时，根据作业的大小从空闲内存区中“切出”一片连续的区域。 分区的大小和个数是不确定的 初始时，系统中只有一个连续的用户区域，随着作业的到达和撤消，用户区就被划分为若干个大小不等的区域。 空闲区的管理 ? 空闲分区表 序号 起始地址 大小 状态 注意：这里的状态是指该表目的状态，其值表示该表目是空闲还是已使用。 ? 空闲分区链 （1）最先适应分配算法 空闲分区表按地址从小到大排列，从第一个开始，找到第一个满足条件的分区，根据作业的大小切出一片连续的区域。 （2）最优适应分配算法 ? 原理：将空闲区按大小从小到大排列，将满足需求的最小的空闲区分配给作业。 ? 好处：为了更好地满足大作业的需求。 ? 缺点：这样切下的空闲区容易变成“碎片”。 算法流程与最先适配法相同。 （3）最坏适配算法 ?从满足需求的最大的空闲区中为作业分配空间。 ?空闲分区表按大小从大到小排列。 ?优点：切完后的空闲区仍能满足某个作业的需求，减少碎片的数量。 ?缺点：但对大作业不利。 　其流程为： 如何判断待回收区是否与空闲区相连？ 地址+长度=下一空闲区首地址 空闲区的管理：为了便于空闲区的合并，采用链接结构。 按地址从小到大排序。 第一块和最后一块的情况。 回收算法 １、待回收区： 　　其起始地址为Ａ，长度为Ｌ。 ２、上空闲区和下空闲区 ３、可能的四种情况： 　　（１）上下都不空。 　　（２）上空，下不空。 　　（３）下空，上不空。 　　（４）上下都为空。 注 意 如何判断待回收区是否与空闲区相连？ 地址+长度=下一空闲区首地址 空闲区的管理：为了便于空闲区的合并，采用链接结构。 按地址从小到大排序。 第一块和最后一块的情况。 可变分区存在的问题及解决办法 碎片问题：一些很小的内存区域 。 移动技术 将离散的碎片集合在一起。 不是任何时候都可以移动。 移动技术需要很大的系统开销。 保护问题 界地址法：基址和长度寄存器。 三、 页式存储管理 “等分”内存 把内存划分为大小相同的“块” 把用户作业空间划分为大小相同的“页” 页和块的大小相同 在把作业加载到内存时，页和页之间不再连续。但页内连续。 也不必把所有的页都一次性加载内存，只需要加载那些马上要用到的页。其余的页在需要时再加载。 页式主存空间的分配与回收 ? 用户需求：需要多少块？ ? 内存空闲块的管理：位示图。 ? 位示图：在内存中划出一片区域，用一位代表一个块，该位的值表示所代表的块的状态： 0：空闲；1：已分配。 1、页面调度 先进先出法（FIFO）：将最先调入内存的页调出内存 最近最久未使用算法（LRU：least recently used）：将最近一段时间内没有用过的页调出内存。 实现这种算法的一种方法