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

1、一、进程调度 如何从就绪队列中选择一个进程使其运行？ 从就绪队列中按一定的策略选择一个进程，使其占有处理机。 进程调度的时机 正在运行的进程运行完毕。 正在执行的进程被阻塞，加入等待队列 时间片到 高优先级的进程进入就绪队列进程调度的评价指标 进程的等待时间 CPU的利用率 系统资源的利用率 响应时间 周转时间一般用平均周转时间来衡量一个调度算法的好坏。1、先来先服务法、先来先服务法 根据进程到达就绪队列的次序，总是选择先到达的进程运行。 优点：公平性；管理简单（队列）。 看右边表格中的例子： 由于进程到达的随机性，可能使系统中的短作业等待时间长。作业CPU时间156224352、时间片轮转法

2、（、时间片轮转法（RR） 时间片：系统允许进程一次使用处理机的最长时间。 回忆：分时系统的工作原理。 工作原理：就绪队列中的进程，每次最多使用一个时间片。 硬件支持：计时器。时间片到，发生“计时中断”。 问题：时间片的大小如何确定？时间片的长短 就绪队列长短：越长，时间片越短。 响应时间的要求： 计算机的性能 进程切换的系统开销：一个进程让出处理机，另一个进程占有处理机。3、进程调度算法-优先数调度法 总是从就绪队列中选择优先级最高的进程。 问题1：优先数如何确定？ 进程类别：系统进程，用户进程，前台，后台等 进程运行时间 作业的优先级等优先数调度法 问题2：当一个更高优先级的进程到达就绪队列

3、时，如何处理？ 抢占式 非抢占式：一旦分配CPU，就一直占用，直到主动放弃为止。 问题3：如果一个低优先级的进程在就绪队列中等待太长时间？ 动态优先数动态优先数：进程的优先级随系统情况不断变化。多级轮转调度法 时间片轮转与优先数结合。 按优先级将作业排成不同的队列。 先按优先级调度，优先级相同的，按时间片轮转。 前台作业与后台作业 交互式作业 批处理作业二、可变分区存储管理原理在作业要求装入主存时，根据作业的大小从空闲内存区中“切出”一片连续的区域。 分区的大小和个数是不确定的 初始时，系统中只有一个连续的用户区域，随着作业的到达和撤消，用户区就被划分为若干个大小不等的区域。内存内存OS作业A

4、作业B作业C可变分区存储管理的原理 空闲区的管理空闲区的管理 空闲分区表空闲分区表 序号 起始地址 大小 状态 注意注意：这里的状态是指该表目的状态，其值表示该表目是空闲还是已使用。 空闲分区链空闲分区链空闲区大小；下一空闲区起始地址 1 、内存分配与回收 （1 1）最先适应分配算法）最先适应分配算法 空闲分区表按地址地址从小小到大大排列，从第一个开始，找到第一个满足条件的分区，根据作业的大小切出一片连续的区域。 分配算法内存分配与回收作业请求LP=1是否越界？Y不能分配状态为空闲？NP=P+1长度LNY长度=L状态置为“空表目”YN起始地址=起始地址+L长度=长度-L最先适应分配算法 （2）

5、最优适应分配算法最优适应分配算法 原理：原理：将空闲区按大小大小从小到大排列，将满足需求的最小的空闲区分配给作业。 好处：好处：为了更好地满足大作业的需求。 缺点：缺点：这样切下的空闲区容易变成“碎碎片片”。 算法流程与最先适配法相同。 分配算法 （3 3）最坏适配算法）最坏适配算法 从满足需求的最大最大的空闲区中为作业分配空间。 空闲分区表按大小大小从大大到小小排列。 优点：切完后的空闲区仍能满足某个作业的需求，减少碎片的数量。 缺点：但对大作业不利。 其流程为： 分配算法用户作业请求取分区表的第一个表项长度起始地址起始地址长度长度长度状态置空表目不能分配 如何判断待回收区是否与空闲区相连？

6、 地址+长度=下一空闲区首地址 空闲区的管理：为了便于空闲区的合并，采用链链接结构接结构。 按地址从小到大排序。 第一块和最后一块的情况。注 意回收算法回收算法、待回收区：其起始地址为，长度为。、上空闲区和下空闲区、可能的四种情况：（）上下都不空。（）上空，下不空。（）下空，上不空。（）上下都为空。待回收区作业区作业区上下都不空上下都不空待回收区作业区上空下不空上空下不空在空闲分区表中找一个空表目，将其内容填入。上空闲区：大小大小待回收区作业区待回收区下空上不空下空上不空下空闲区：起始地址=A大小=大小+L上下都为空上下都为空上空闲区：长度=长度+L+下空闲区起址不变。注注 意意 如何判断待回

7、收区是否与空闲区相连？ 地址+长度=下一空闲区首地址 空闲区的管理：为了便于空闲区的合并，采用链接结构。 按地址从小到大排序。 第一块和最后一块的情况。可变分区存在的问题及解决办法 碎片问题：一些很小的内存区域 。 移动技术 将离散的碎片集合在一起。 不是任何时候都可以移动。 移动技术需要很大的系统开销。 保护问题 界地址法：基址和长度寄存器。三、 页式存储管理 “等分”内存 把内存划分为大小相同的“块” 把用户作业空间划分为大小相同的“页” 页和块的大小相同 在把作业加载到内存时，页和页之间不再连续。但页内连续。 也不必把所有的页都一次性加载内存，只需要加载那些马上要用到的页。其余的页在需要

8、时再加载。基本原理页式主存空间的分配与回收 用户需求：用户需求：需要多少块？ 内存空闲块的管理：内存空闲块的管理：位示图位示图。 位示图：位示图：在内存中划出一片区域，用一位代表一个块，该位的值表示所代表的块的状态： 0：空闲；1：已分配。 主存分配主存分配 块号与字号、字长的关系：系统的字长一定，内存块从0开始编号，则有： 块号=字号*字长+位号 字号=块号/字长 （取整的意思） 位号=块号 MOD 字长 用户作业请求：块数B扫描位示图，查找为0的位空闲块数BN无法分配计算块号建立页表页号块号071122321页表根据页号查页表，得到块号。根据块号和页内地址计算物理地址1、页面调度 先进先出

9、法（先进先出法（FIFOFIFO）：）：将最先调入内存的页调出内存 最近最久未使用算法（最近最久未使用算法（LRULRU：least recently usedleast recently used）：将最近一段时间内没有用过的页调出内存。实现这种算法的一种方法是在页表中为每一页增加一个引用位标志，记录该页面自上次被访问以来所经历的时间，每访问一次都应重新计时。当需要替换时，检查每页的引用位，从中选出计时值最大的那一页调出。四、页式虚拟存储技术 最近最不经常使用算法（最近最不经常使用算法（LFULFU）：）：最近一段时间内使用次数最少的页调出内存。 为每一个在内存的页设置一个计数器，选择计数器

10、中的值最小的调出。 注意：注意：LRU、LFU之间的区别。 例题例题 有一个分页式虚拟存储管理系统，每个进程在内存有3页数据区、1页程序区，刚开始时数据区为空。现有一个进程有以下访问序列： 1，5，4，1，2，3，2，1，5，4，2，4，3，5，1若系统采用：（1）最近最少使用（LRU）淘汰算法（2）先进先出（FIFO）淘汰算法请计算缺页次数和发生缺页中断后的淘汰页号。 分析分析 （1）采用FIFO方法 将内存中的页按进入的先后次序排队，后来的加入队尾，先来的先出去。访问队列：1 5 4 1 2 3 2 1 5 4 2 4 3 5 1 1 5 4 4 2 3 3 1 5 4 2 2 3 5 1

11、内 存 1 5 5 4 2 2 3 1 5 4 4 2 3 5 1 1 5 4 4 2 3 1 5 5 4 2 3缺页中断 页面替换 1 5 4 2 3 1 5 4 3答案：缺页中断的次数为12次，页面替换的次序是：1 5 4 2 3 1 5 4 3。FIFOFIFO方法方法访问队列：1 5 4 1 2 3 2 1 5 4 2 4 3 5 1 1 5 4 4 2 3 3 3 5 4 2 2 3 5 1内 存 1 5 5 1 2 2 2 1 5 4 4 2 3 5 1 1 4 1 1 1 2 1 5 5 4 4 3缺页中断 页面替换 5 4 3 2 1 5 2 4答案：缺页中断的次数为11次，页

12、面替换的次序是：5 4 3 2 1 5 2 4LRU LRU 算法算法五、磁盘空间的管理1、空闲空间的管理 （1）位示图：用一个位来表示一个块。如果字长为32位，则字号、位号、块号之间的关系是： 块号=字号*字长+位号 字号=块号/字长 位号=块号 MOD 字长 （2）空闲空间链：在空闲块中利用几个字节，存放下一空闲块的块号。2成组链接法假设初始化时系统已把专用块读入内存L单元开始的区域中，分配和回收的算法如下：（1）分配一个空闲块 查L单元内容（即空闲块数）； 当空闲块数1时； i L空闲块数（把i作为主存地址）； 从i单元得到一空闲块号； 把该块分配给申请者； 空闲块数减1。 当空闲块数1

13、 时 取出L1单元内容（一组的第一块块号 ）； 其值0，无空闲块，申请者等待； 不等于零把该块内容复制到专用块，并将该块分配给 申请者； 把专用块内容读到主存L开始的区域。（2）归还一空闲块（即把归还的块号加到空闲块链中） 取L单元的空闲块数； 当空闲块数100 时 空闲块数加1； j L空闲块数（把j作为主存地址） ； 归还块号填入j单元。 当空闲块数100 时 把主存中登记的信息写入归还块中； 把归还块号填入L1单元； 将L单元置成1。磁盘空间管理（3）空闲空间表首块号长度必须连续分配。七、磁盘调度七、磁盘调度 磁盘是共享设备，可以同时为多个进程服务。 目前的磁盘都是活动磁头，因此读写时间

14、包括： 查找时间：磁头移动到正确的磁道的时间。 延迟时间（等待时间）：磁头等待盘片旋转到正确的扇区下的时间。 传输时间：数据从磁盘读到内存的时间。 在上述三个时间中，查找时间、延迟时间可以通过调度策略来改善。 移臂调度和旋转调度。1、移臂调度 将移动臂移动到指定柱面的调度。 影响寻找时间的长短。 当有若干个设备读写请求时，应该先响应哪一个？ 原则：尽量避免移动臂频繁地来回移动。 先来先服务 最短查找时间优先 电梯法引例：引例： 假定一个活动磁盘有200个磁道，编号为0199。当前磁头正在54道上服务，并且刚刚完成了39道上的请求。现有如下的磁盘访问请求序列（磁道号）：86、147、91、173

15、、95、148、101、26、169、80、129、22试给出采用下列移臂调度算法后移动臂移动的顺序和移动总量（总磁道数）。（1） 先来先服务法（2） 最短寻找时间优先（3） 电梯法移臂调度的评价 寻找时间越短越好。 寻找时间与移动臂移动的磁道数成正比。 因此，我们用移动臂移动的磁道数来评价某一个移臂调度的策略的好坏。移臂调度策略 先来先服务：根据请求的到达先后次序，响应请求。 173 169 148 147 129 101 95 91 86 80 54 26 22磁头移动的顺序为：86、147、91、173、95、148、101、26、169、80、129、22磁头的移动总量为：（86-54

16、）+（147-86）+（147-91）+（173-91）+（173-95）+（148-95）+（148-101）+（101-26）+（169-26）+（169-80）+（129-80）+（129-22）=872最短查找时间优先 从当前位置开始，响应磁头移动距离最短的请求。 也就是离当前位置最近的请求。 注意：它不考虑移动臂移动的方向。首先从访问队列中找离54磁道最近的访问请求，结果是80，再从剩下的访问请求中找离80最近的，是86。直到所有访问请求响应完为止。173 169 148 147 129 101 95 91 86 80 54 26 22磁头移动次序为：80、86、91、95、101、

17、129、147、148、169、173、26、22磁头移动的总磁道数为：（80-54）+（86-80）+（91-86）+（95-91）+（101-95）+（129-101）+（147-129）+（148-147）+（169-148）+（173-169）+（173-26）+（26-22）=270 电梯法 沿着当前磁头移动的方向，响应进程的请求。当该方向上无请求时，磁头就改变方向。 因此，一定要知道当前磁头的移动方向。从题意可知：磁头的移动方向为从外向内移动，也就是从0向199的移动。根据电梯法的调度原理，磁头的移动如下图所示： 173 169 148 147 129 101 95 91 86 8

18、0 54 26 22磁头移动次序为：80、86、91、95、101、129、147、148、169、173、26、22磁头移动的总磁道数为：（80-54）+（86-80）+（91-86）+（95-91）+（101-95）+（129-101）+（147-129）+（148-147）+（169-148）+（173-169）+（173-26）+（26-22）=270 旋转调度 移动臂定位后，有多个访问者等待访问该柱面时。 使延迟时间最短。 根据延迟时间来决定调度次序的调度。 三种情况： （1）同一磁道上的不同扇区。 （2）不同磁道上的不同扇区。 （3）不同磁道上的具有相同编号的扇区。 对（1）（2）

19、总是对先到达磁头位置下的扇区进行信息传递；(3）因同时到达，则从中任意选择一个进行传递，其余等磁盘再次把扇区转到磁头位置时才有可能被选中。信息的优化分布例：例：某系统对磁盘初始化时把每个盘面分成8个扇区，今有8个逻辑记录被存放在同一个磁道上供处理程序使用，处理程序要求顺序处理这8个记录，每次请求从磁盘上读一个记录，然后对读出的记录要花5毫秒的时间处理，以后再读下一个记录进行处理，直到8个记录都处理结束。假定磁盘转速为20毫秒/周，则处理这8个记录所花费的时间是多少？顺序存放始点旋转方向12345678花费时间 读一个记录需要2.5毫秒。 处理一个记录的时间为5毫秒。 当处理完一个记录（5毫秒）

20、后，读写磁头已旋转到第4个记录位置。 为了处理第2个记录，必须等待磁盘把第2个记录旋转到读写磁头位置下面。 需要15毫秒的延迟时间。 因此，总时间为： 8（2.5+5）+7 15=165MS优化分布61234578八、作业调度算法 先来先服务算法 注意：不是先进入的一定先被选中，只有满足资源需求的作业才可能被选中。 计算时间短的作业优先算法 响应比高者优先算法：响应比响应比=等待时间/运行时间 优先数调度法 均衡调度算法：根据作业对资源的要求进行分类，作业调度轮流从不同类的作业中去挑选作业运行。例例：在一个单道批处理系统中，一组作业的提交时刻和运行时间如下表所示，试计算以下三种作业调度算法的平

21、均周转时间。（1）先来先服务法。（2）短作业优先 （3）响应比高者优先。作业 提交时间（小时）运行时间（小时） 1 8：00 1 2 8：50 0.5 3 9:00 0.2 4 9:10 0.1（1）先来先服务算法：）先来先服务算法：8:009:009:30 9:42 9:48123460分钟分钟30分钟分钟12分钟分钟6分钟分钟（2）短作业优先算法：）短作业优先算法：8:00 8:50 9:00 9:10 9:12 9:18 9:48 123360分分12分分446分分230分分（3）响应比高者优先：）响应比高者优先：2的响应比的响应比=10/303的响应比的响应比=0/12因此，作业因此，

22、作业2先调度运行先调度运行9:00 9:303的响应比的响应比=30/124的响应比的响应比=20/6因此，作业因此，作业4先调度运行先调度运行9:30 9:36最后，作业最后，作业3调度运行：调度运行：9:36 9:481243作业调度算法例题 假设有一个多道程序设计系统，采用可变分区方式管理主存储器，且不能移动已在主存储器中的作业。若供用户使用的主存空间为200KB，系统配备5台磁带机。该系统对磁带机采用静态分配，忽略外设工作时间和系统调用所花的时间，有下列4个作业，采用计算时间最短者优先算法进行调度。 填充下表中的空白处:作业进输入井时间 要求计算时间 需要主存量申请磁带机数开始执行时间

23、 完成时间周转时间A8:30 24分 30KB 2B8:40 33分 50KB 2C8:50 12分 110KB 3D9:00 42分 40KB 2解题思路 1、作业调度的时机： （1）一个作业到达后备队列 （2）一个作业执行完毕 2、先决条件：必须先满足作业的资源需求 3、考虑调度的算法答 案作业进输入井时间 要求计算时间 需要主存量申请磁带机数装入主存时间开始执行时间完成时间周转时间A8:30 24分 30KB 28:30 8:308:5424B8:40 33分 50KB 28:40 8:549:2646C8:50 12分 110KB 38:54 9:269:3848D9:00 42分 4

24、0KB 29:26 9:3810:2080九、银行家算法 思想：允许用户分批申请贷款，每次贷款之前，都要检查是否安全。 数据结构： 系统中总的资源 进程运行所需资源（总数） 已经分配的资源数 P 还需要申请的资源数 R银行家算法的算法过程 准备：计算系统中的剩余资源F；计算进程请求资源R （1）找到一个进程Pi，满足Ri=Ri，则说明系统不安全。 （5）若所有进程都能够运行结束，则系统安全。银行家算法的应用 现有三个进程P1、P2、P3，共享A、B、C三类资源，进程对资源的需求量和目前分配情况如下表： 进程 已占有资源数 最大需求数 A B C A B C P1 2 6 3 2 6 5 P2

25、2 0 1 2 0 1 P3 2 1 0 2 8 5 若系统还有剩余资源分别为：A类2个，B类6个，C类2个。请回答下列问题：（1）目前系统是否处于安全状态？（2）如果进程P3提出申请（0，5，2）个资源，系统是否能为它分配资源？ （1） 系统当前的空闲资源为：（2，6，2）进程要运行结束，还需请求的资源为： 进 程 A B C P1 0 0 2 P2 0 0 0 P3 0 7 5由于P2不需要申请更多的资源，可以运行结束，释放它占有的资源（2，0，1），空闲资源变为：（4，6，3）。空闲资源满足P1的资源要求，P1运行结束，释放它占有的资源（2，6，3），空闲资源变为：（6，12，6）。空闲资源满足P3的资源请求，P3可以运行结束。系统中的进程能在有限时间内全部运行结束，所以系统是安全的。（2） 假设可以为进程P3分配它申请的资源（0，5，2），则系统当前状况是：空闲资源为：（2，1，0）进程要运行结束，还需请求的资源为：进进 程程 A B C P1 0 0 2 P2 0 0 0 P3 0 2 3进程P2运行，释放它所占有的资源（2，0，1），系统空闲资源变为：（4，1，1）。由于空闲资源不能满足系统中任一进程的资源请求，进程P1和P3陷入无限期等待，系统出现死锁。所以，系统不