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

《操作系统十大算法具体内容ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

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

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

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

8、那些马上要用到的页。其余的页在需要时再加载。基本原理页式主存空间的分配与回收用户需求：需要多少块？内存空闲块的管理：位示图。位示图：在内存中划出一片区域，用一位代表一个块，该位的值表示所