《操作系统十大算法具体内容ppt课件.ppt》由会员分享，可在线阅读，更多相关《操作系统十大算法具体内容ppt课件.ppt（73页珍藏版）》请在三一办公上搜索。
1、一、进程调度,如何从就绪队列中选择一个进程使其运行？从就绪队列中按一定的策略选择一个进程，使其占有处理机。进程调度的时机正在运行的进程运行完毕。正在执行的进程被阻塞，加入等待队列时间片到高优先级的进程进入就绪队列,进程调度的评价指标,进程的等待时间CPU的利用率系统资源的利用率响应时间周转时间一般用平均周转时间来衡量一个调度算法的好坏。,1、先来先服务法,根据进程到达就绪队列的次序，总是选择先到达的进程运行。优点：公平性；管理简单（队列）。看右边表格中的例子：由于进程到达的随机性，可能使系统中的短作业等待时间长。,2、时间片轮转法（RR）,时间片：系统允许进程一次使用处理机的最长时间。回忆：分
2、时系统的工作原理。工作原理：就绪队列中的进程，每次最多使用一个时间片。硬件支持：计时器。时间片到，发生“计时中断”。问题：时间片的大小如何确定？,时间片的长短,就绪队列长短：越长，时间片越短。响应时间的要求：计算机的性能进程切换的系统开销：一个进程让出处理机，另一个进程占有处理机。,3、进程调度算法-优先数调度法,总是从就绪队列中选择优先级最高的进程。问题1：优先数如何确定？进程类别：系统进程，用户进程，前台，后台等进程运行时间作业的优先级等,优先数调度法,问题2：当一个更高优先级的进程到达就绪队列时，如何处理？抢占式非抢占式：一旦分配CPU，就一直占用，直到主动放弃为止。问题3：如果一个低优
3、先级的进程在就绪队列中等待太长时间？动态优先数：进程的优先级随系统情况不断变化。,多级轮转调度法,时间片轮转与优先数结合。按优先级将作业排成不同的队列。先按优先级调度，优先级相同的，按时间片轮转。前台作业与后台作业交互式作业批处理作业,二、可变分区存储管理,原理在作业要求装入主存时，根据作业的大小从空闲内存区中“切出”一片连续的区域。 分区的大小和个数是不确定的 初始时，系统中只有一个连续的用户区域，随着作业的到达和撤消，用户区就被划分为若干个大小不等的区域。,内存,OS,作业A,作业B,作业C,可变分区存储管理的原理,空闲区的管理 空闲分区表 序号 起始地址 大小 状态 注意：这里的状态是指
4、该表目的状态，其值表示该表目是空闲还是已使用。 空闲分区链,空闲区大小；下一空闲区起始地址, ,1 、内存分配与回收,（1）最先适应分配算法 空闲分区表按地址从小到大排列，从第一个开始，找到第一个满足条件的分区，根据作业的大小切出一片连续的区域。,分配算法,内存分配与回收,作业请求L,P=1,是否越界？,Y,不能分配,状态为空闲？,N,P=P+1,长度L,N,Y,长度=L,状态置为“空表目”,Y,N,起始地址=起始地址+L长度=长度-L,最先适应分配算法,（2）最优适应分配算法 原理：将空闲区按大小从小到大排列，将满足需求的最小的空闲区分配给作业。 好处：为了更好地满足大作业的需求。 缺点：这
5、样切下的空闲区容易变成“碎片”。 算法流程与最先适配法相同。,分配算法,（3）最坏适配算法从满足需求的最大的空闲区中为作业分配空间。空闲分区表按大小从大到小排列。优点：切完后的空闲区仍能满足某个作业的需求，减少碎片的数量。缺点：但对大作业不利。其流程为：,分配算法,用户作业请求,取分区表的第一个表项,长度,起始地址起始地址长度长度,长度,状态置空表目,不能分配,如何判断待回收区是否与空闲区相连？ 地址+长度=下一空闲区首地址 空闲区的管理：为了便于空闲区的合并，采用链接结构。 按地址从小到大排序。 第一块和最后一块的情况。,注 意,回收算法,、待回收区：其起始地址为，长度为。、上空闲区和下空闲
6、区、可能的四种情况：（）上下都不空。（）上空，下不空。（）下空，上不空。（）上下都为空。,待回收区,作业区,作业区,上下都不空,待回收区,作业区,上空下不空,在空闲分区表中找一个空表目，将其内容填入。,上空闲区：大小大小,待回收区,作业区,待回收区,下空上不空下空闲区：起始地址=A大小=大小+L,上下都为空上空闲区：长度=长度+L+下空闲区起址不变。,注 意,如何判断待回收区是否与空闲区相连？ 地址+长度=下一空闲区首地址空闲区的管理：为了便于空闲区的合并，采用链接结构。按地址从小到大排序。第一块和最后一块的情况。,可变分区存在的问题及解决办法,碎片问题：一些很小的内存区域 。移动技术将离散的
7、碎片集合在一起。不是任何时候都可以移动。移动技术需要很大的系统开销。 保护问题界地址法：基址和长度寄存器。,三、 页式存储管理,“等分”内存 把内存划分为大小相同的“块” 把用户作业空间划分为大小相同的“页” 页和块的大小相同 在把作业加载到内存时，页和页之间不再连续。但页内连续。 也不必把所有的页都一次性加载内存，只需要加载那些马上要用到的页。其余的页在需要时再加载。,基本原理,页式主存空间的分配与回收, 用户需求：需要多少块？ 内存空闲块的管理：位示图。 位示图：在内存中划出一片区域，用一位代表一个块，该位的值表示所代表的块的状态： 0：空闲；1：已分配。,主存分配,块号与字号、字长的关系
8、：系统的字长一定，内存块从0开始编号，则有： 块号=字号*字长+位号 字号=块号/字长 （取整的意思） 位号=块号 MOD 字长,用户作业请求：块数B,扫描位示图，查找为0的位,空闲块数B,N,无法分配,计算块号,建立页表,页表,根据页号查页表，得到块号。根据块号和页内地址计算物理地址,1、页面调度,先进先出法（FIFO）：将最先调入内存的页调出内存 最近最久未使用算法（LRU：least recently used）：将最近一段时间内没有用过的页调出内存。实现这种算法的一种方法是在页表中为每一页增加一个引用位标志，记录该页面自上次被访问以来所经历的时间，每访问一次都应重新计时。当需要替换时，
9、检查每页的引用位，从中选出计时值最大的那一页调出。,四、页式虚拟存储技术,最近最不经常使用算法（LFU）：最近一段时间内使用次数最少的页调出内存。 为每一个在内存的页设置一个计数器，选择计数器中的值最小的调出。注意：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方法 将内存中的页按进
10、入的先后次序排队，后来的加入队尾，先来的先出去。,访问队列：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内 存 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。,FIFO方法,访问队列：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
11、 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次，页面替换的次序是：5 4 3 2 1 5 2 4,LRU 算法,五、磁盘空间的管理,1、空闲空间的管理 （1）位示图：用一个位来表示一个块。如果字长为32位，则字号、位号、块号之间的关系是： 块号=字号*字长+位号 字号=块号/字长 位号=块号 MOD 字长 （2）空闲空间链：在空闲块中利用几个字节，存放下一空闲块的块号。,2,成组链接法,假设初始化时系统已把专用块读入内存L单元开始的区域中，分配和回收的算法如下：（1）分配一个
12、空闲块 查L单元内容（即空闲块数）； 当空闲块数1时； i L空闲块数（把i作为主存地址）； 从i单元得到一空闲块号； 把该块分配给申请者； 空闲块数减1。 当空闲块数1 时 取出L1单元内容（一组的第一块块号 ）； 其值0，无空闲块，申请者等待； 不等于零把该块内容复制到专用块，并将该块分配给 申请者； 把专用块内容读到主存L开始的区域。,（2）归还一空闲块（即把归还的块号加到空闲块链中） 取L单元的空闲块数； 当空闲块数100 时 空闲块数加1； j L空闲块数（把j作为主存地址） ； 归还块号填入j单元。 当空闲块数100 时 把主存中登记的信息写入归还块中； 把归还块号填入L1单元；
13、将L单元置成1。,磁盘空间管理,（3）空闲空间表,必须连续分配。,七、磁盘调度,磁盘是共享设备，可以同时为多个进程服务。目前的磁盘都是活动磁头，因此读写时间包括：查找时间：磁头移动到正确的磁道的时间。延迟时间（等待时间）：磁头等待盘片旋转到正确的扇区下的时间。传输时间：数据从磁盘读到内存的时间。在上述三个时间中，查找时间、延迟时间可以通过调度策略来改善。移臂调度和旋转调度。,1、移臂调度,将移动臂移动到指定柱面的调度。影响寻找时间的长短。当有若干个设备读写请求时，应该先响应哪一个？原则：尽量避免移动臂频繁地来回移动。先来先服务最短查找时间优先电梯法,引例： 假定一个活动磁盘有200个磁道，编号
14、为0199。当前磁头正在54道上服务，并且刚刚完成了39道上的请求。现有如下的磁盘访问请求序列（磁道号）：86、147、91、173、95、148、101、26、169、80、129、22试给出采用下列移臂调度算法后移动臂移动的顺序和移动总量（总磁道数）。（1） 先来先服务法（2） 最短寻找时间优先（3） 电梯法,移臂调度的评价,寻找时间越短越好。寻找时间与移动臂移动的磁道数成正比。因此，我们用移动臂移动的磁道数来评价某一个移臂调度的策略的好坏。,移臂调度策略,先来先服务：根据请求的到达先后次序，响应请求。,173 169 148 147 129 101 95 91 86 80 54 26 2
15、2磁头移动的顺序为：86、147、91、173、95、148、101、26、169、80、129、22磁头的移动总量为：（86-54）+（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。直到所有访问请求响应完为止。17
16、3 169 148 147 129 101 95 91 86 80 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,电梯法,沿着当前磁头移动的方向，响应进程的请求。当该方向上无请求时，磁头就改变方向。因此，一定要知道当前磁头的移动方向。,从题意可知：磁头的移动方向为从外向内移动，也就是从
17、0向199的移动。根据电梯法的调度原理，磁头的移动如下图所示： 173 169 148 147 129 101 95 91 86 80 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,旋转调度,移动臂定位后，有多个访问者等待访问该柱面时。使延迟时间最短。根据延迟时间来决定调度次序的调度。
18、三种情况：（1）同一磁道上的不同扇区。（2）不同磁道上的不同扇区。（3）不同磁道上的具有相同编号的扇区。对（1）（2）总是对先到达磁头位置下的扇区进行信息传递；(3）因同时到达，则从中任意选择一个进行传递，其余等磁盘再次把扇区转到磁头位置时才有可能被选中。,信息的优化分布,例：某系统对磁盘初始化时把每个盘面分成8个扇区，今有8个逻辑记录被存放在同一个磁道上供处理程序使用，处理程序要求顺序处理这8个记录，每次请求从磁盘上读一个记录，然后对读出的记录要花5毫秒的时间处理，以后再读下一个记录进行处理，直到8个记录都处理结束。假定磁盘转速为20毫秒/周，则处理这8个记录所花费的时间是多少？,顺序存放,
19、始点,旋转方向,1,2,3,4,5,6,7,8,花费时间,读一个记录需要2.5毫秒。处理一个记录的时间为5毫秒。当处理完一个记录（5毫秒）后，读写磁头已旋转到第4个记录位置。为了处理第2个记录，必须等待磁盘把第2个记录旋转到读写磁头位置下面。需要15毫秒的延迟时间。因此，总时间为： 8（2.5+5）+7 15=165MS,优化分布,6,1,2,3,4,5,7,8,八、作业调度算法,先来先服务算法注意：不是先进入的一定先被选中，只有满足资源需求的作业才可能被选中。计算时间短的作业优先算法响应比高者优先算法：响应比=等待时间/运行时间优先数调度法均衡调度算法：根据作业对资源的要求进行分类，作业调度
20、轮流从不同类的作业中去挑选作业运行。,例：在一个单道批处理系统中，一组作业的提交时刻和运行时间如下表所示，试计算以下三种作业调度算法的平均周转时间。（1）先来先服务法。（2）短作业优先 （3）响应比高者优先。作业提交时间（小时）运行时间（小时） 1 8：00 1 2 8：50 0.5 3 9:00 0.2 4 9:10 0.1,（1）先来先服务算法：,8:00,9:00,9:30 9:42 9:48,1,2,3,4,60分钟,30分钟,12分钟,6分钟,（2）短作业优先算法：,8:00 8:50 9:00 9:10 9:12 9:18 9:48,1,2,3,3,60分,12分,4,46分,23
21、0分,（3）响应比高者优先：,2的响应比=10/303的响应比=0/12因此，作业2先调度运行,9:00 9:30,3的响应比=30/124的响应比=20/6因此，作业4先调度运行,9:30 9:36,最后，作业3调度运行：,9:36 9:48,1,2,4,3,作业调度算法例题,假设有一个多道程序设计系统，采用可变分区方式管理主存储器，且不能移动已在主存储器中的作业。若供用户使用的主存空间为200KB，系统配备5台磁带机。该系统对磁带机采用静态分配，忽略外设工作时间和系统调用所花的时间，有下列4个作业，采用计算时间最短者优先算法进行调度。,填充下表中的空白处:,解题思路,1、作业调度的时机：
22、（1）一个作业到达后备队列 （2）一个作业执行完毕2、先决条件：必须先满足作业的资源需求3、考虑调度的算法,答 案,九、银行家算法,思想：允许用户分批申请贷款，每次贷款之前，都要检查是否安全。数据结构：系统中总的资源进程运行所需资源（总数）已经分配的资源数 P还需要申请的资源数 R,银行家算法的算法过程,准备：计算系统中的剩余资源F；计算进程请求资源R（1）找到一个进程Pi，满足Ri=Ri，则说明系统不安全。（5）若所有进程都能够运行结束，则系统安全。,银行家算法的应用,现有三个进程P1、P2、P3，共享A、B、C三类资源，进程对资源的需求量和目前分配情况如下表： 进程 已占有资源数 最大需求
23、数 A B C A B C P1 2 6 3 2 6 5 P2 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运行结束，释放它
24、占有的资源（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陷入无限期等待，系统出现死锁。所以，系统不能为P2分配资源。,十、死锁检测,如果每次分
25、配资源，都需要做一次银行家算法，系统效率会非常低。假设：系统中发生死锁的可能性很小，因此，没有必要每次都检查系统是否安全，只需定期检查以下系统是否存在死锁就可以了。当进程请求资源时，若系统中有资源，就分配给进程。如何检测系统是否死锁？,死锁检测算法-1、资源状态图,原理：是否存在资源的循环等待？资源状态图：用有向图来表示进程对资源的占有情况。顶点：进程，资源边：如果一个进程已经占有了一份资源，则画一条指向进程的边。如果一个进程申请一份资源，则画一条指向资源的边。如果同一份资源有多个，则用顶点中的圆点数表示。, , ,P1,P2,P3,r1,r2,r3,r4,死锁判定法则,如果资源分配图中没有环
26、路，则系统没有死锁。如果资源分配图中出现了环路，则系统可能存在死锁。如果处于环路中的每个资源类中均包含一个资源实例，则意味着死锁的存在。如果处于环路中的每个资源类中包含的资源实例个数不全为1，则环路的存在是必要条件。,死锁检测算法-2、两张表格,设置两张表格来记录进程使用和等待资源的情况。例如，系统有5个资源r1,r2,r3,r4和r5，现有三个进程P1，P2和片，他们依次申请资源的要求为：P1依次申请r1,r5,r3P2依次申请r3,r4,r2P3依次申请r2,r5这三个进程并发执行时，可能P1在得到资源r1和r5后，就有P2申请r3，再有P3申请r2。按这样序列执行时，这些进程都得到所申请的资源。但以后继续执行时会发生：P1申请r3，不能满足而等待资源r3P2申请r4能满足，再申请r2不能满足而等待资源r2P3申请r5，不能满足而等待资源r5,两张表格的记录情况为：,死锁检测程序定时地检测这两张表格。如果发现有循环等待资源的进程，则就有死锁出现。,死锁解除,策略：重新启动系统（撤消所有进程）剥夺资源法逐一终止进程选择哪些进程剥夺资源或终止？-最小代价原则。,
