操作系统十大算法具体内容资料课件.pptVIP

一、进程调度?如何从就绪队列中选择一个进程使其运行？?从就绪队列中按一定的策略选择一个进程，使其占有处理机。?进程调度的时机–正在运行的进程运行完毕。–正在执行的进程被阻塞，加入等待队列–时间片到–高优先级的进程进入就绪队列

进程调度的评价指标?进程的等待时间?CPU的利用率?系统资源的利用率?响应时间?周转时间一般用平均周转时间来衡量一个调度算法的好坏。

1、先来先服务法?根据进程到达就绪队列的次序，总是选择先到达的进程运行。作业CPU时间156?优点：公平性；管理简单（队列）。224?看右边表格中的例子：35?由于进程到达的随机性，可能使系统中的短作业等待时间长。

2、时间片轮转法（RR）?时间片：系统允许进程一次使用处理机的最长时间。?回忆：分时系统的工作原理。?工作原理：就绪队列中的进程，每次最多使用一个时间片。?硬件支持：计时器。时间片到，发生“计时中断”。?问题：时间片的大小如何确定？

时间片的长短?就绪队列长短：越长，时间片越短。?响应时间的要求：?计算机的性能?进程切换的系统开销：一个进程让出处理机，另一个进程占有处理机。

3、进程调度算法-优先数调度法?总是从就绪队列中选择优先级最高的进程。?问题1：优先数如何确定？–进程类别：系统进程，用户进程，前台，后台等–进程运行时间–作业的优先级等

优先数调度法?问题2：当一个更高优先级的进程到达就绪队列时，如何处理？–抢占式–非抢占式：一旦分配CPU，就一直占用，直到主动放弃为止。?问题3：如果一个低优先级的进程在就绪队列中等待太长时间？–动态优先数：进程的优先级随系统情况不断变化。

多级轮转调度法?时间片轮转与优先数结合。?按优先级将作业排成不同的队列。?先按优先级调度，优先级相同的，按时间片轮转。?前台作业与后台作业–交互式作业–批处理作业

二、可变分区存储管理原理在作业要求装入主存时，根据作业的大小从空闲内存区中“切出”一片连续的区域。分区的大小和个数是不确定的?初始时，系统中只有一个连续的用户区域，随着作业的到达和撤消，用户区就被划分为若干个大小不等的区域。

可变分区存储管理的原理OS作业A作业C作业B内存

1、内存分配与回收空闲区的管理??空闲分区表序号?起始地址大小状态?注意：这里的状态是指该表目的状态，其值表示该表目是空闲还是已使用。??空闲分区链……空闲区大小；下一空闲区起始地址

内存分配与回收分配算法?（1）最先适应分配算法?空闲分区表按地址从小到大排列，从第一个开始，找到第一个满足条件的分区，根据作业的大小切出一片连续的区域。

最先适应分配算法作业请求LP=1Y不能分配是否越界？P=P+1N状态为空闲？N长度≥LYYN起始地址=起始地址+L长度=长度-L状态置为“空表目”长度=L

分配算法?（2）最优适应分配算法??原理：将空闲区按大小从小到大排列，将满足需求的最小的空闲区分配给作业。??好处：为了更好地满足大作业的需求。??缺点：这样切下的空闲区容易变成“碎片”。?算法流程与最先适配法相同。

分配算法?（3）最坏适配算法??从满足需求的最大的空闲区中为作业分配空间。??空闲分区表按大小从大到小排列。??优点：切完后的空闲区仍能满足某个作业的需求，减少碎片的数量。??缺点：但对大作业不利。?其流程为：

用户作业请求Ｌ取分区表的第一个表项长度≥Ｌ不能分配ＹＹ状态置空表目长度＝ＬＮ起始地址＝起始地址＋Ｌ长度＝长度－Ｌ

注意如何判断待回收区是否与空闲区相连？–地址+长度=下一空闲区首地址空闲区的管理：为了便于空闲区的合并，采用链接结构。?按地址从小到大排序。?第一块和最后一块的情况。

回收算法１、待回收区：其起始地址为Ａ，长度为Ｌ。２、上空闲区和下空闲区３、可能的四种情况：（１）上下都不空。（２）上空，下不空。（３）下空，上不空。（４）上下都为空。

作业区作业区待回收区待回收区待回收区待回收区作业区作业区上下都不空上空下不空下空上不空上下都为空在空闲分区表中找一个空表目，将其内容填入。上空闲区：下空闲区：起始地址=A长度=长度上空闲区：大小＝大小＋Ｌ大小=大小+L+下空闲+L区起址不变。

注意?如何判断待回收区是否与空闲区相连？地址+长度=下一空闲区首地址?空闲区的管理：为了便于空闲区的合并，采用链接结构。?按地址从小到大排序。?第一块和最后一块的情况。

可变分区存在的问题及解决办法?碎片问题：一些很小的内存区域。?移动技术–将离散的碎片集合在一起。–不是任何时候都可以移动。–移动技术需要很大的系统开销。?保护问题–界地址法：基址和长度寄存器。

三、页式