操作系统算法总结

﹏ヽ暗。殇╰゛Y 2022-03-09 10:18 273阅读 0赞

## 作业调度算法 ##

1.  **FSFS(First-come First-served)先来先服务调度算法**  
    既可用于作业调度,也可用于进程调度  
    按照先后次序来进行作业调度,优先考虑在系统中等待时间最长的作业  
    等待时间越长,优先级越高  
    优点:有利于CPU繁忙,有利于长作业  
    缺点:不利于I/O繁忙
2.  **SJF(Short-job first)短作业调度算法**  
    按照作业长短来计算优先级,作业越短,优先级越高  
    优点:比FCFS算法有明显改善  
    缺点:  
    (1)必须预先知道作业的运行时间  
    (2)对长作业不利,长作业的运转周期会明显变长  
    (3)在采用SJF算法时,人-机无法实现交互  
    (4)该调度算法完全未考虑作业的紧迫程度,故不能保证紧迫性作业得到及时处理
3.  **PSA(priority-scheduling algotithm)优先级调度算法**  
    基于作业的紧迫程度,由外部赋予作业相应的优先级
4.  **HRRN(Highest Response Ratio Next, )高响应比优先调度算法**  
    优先级随着等待时间增长而增加,  
    1)如果等待时间相同,则要求服务的时间越短,其优先权越高,  
    2)当要求服务时间相同时,作业的优先权又决定于其等待时间,因而该算法又类似于FCFS算法,  
    3)对于长作业优先级,可以随着等待时间的增加而提高,当其等待时间足够长时,也可获得处理机
5.  **轮转调度算法**  
    时间片轮转(round robin)调度算法  
    优点:选择很小的时间片有利于短作业  
    缺点:时间偏小,增加系统开销
6.  非抢占式调度算法
7.  抢占式调度算法  
    1)发生时钟中断时,新来的优先级高的抢占处理机  
    2)一旦外部出现中断,只要当前任务未处于临界区,立即抢占
8.  **最早截止时间优先算法EDF(Earliest Deadline First)**  
    根据任务截止时间确定任务的优先级,任务截止时间越早,优先级越高
9.  **最低松弛度优先算法(Least Laxity First)**  
    根据任务的紧急(松弛)程度,任务紧急程度越高,优先级越高
10. **银行家算法**  
    设Requesti是进程Pi的请求向量,如果Requesti\[j\]=K,表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查  
    1)如果Requesti\[j\]<=Need\[i,j\],便转向步骤2),否则认为出错,因为他所需要的资源数已经超过他所宣布的最大值  
    2)如果Requesti\[j\]<=Available\[j\],便转向步骤3);否则表示尚无足够资源,Pi必须等待  
    3)系统试着把资源分给进程Pi,并修改下面数据结构中的数值

Available[j] = Available[j] - Request~i~[j]；  //剩余可分配资源
    Allocation[i,j] = Allocation[i,j] + Request~i~[j]; //已分配的资源总数
    Need[i,j] = Need[i,j] - Request~i~[j]; //剩余需要分配的资源数

4)系统执行安全性算法，检查此次分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi,已完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待  
11. **安全性算法**  
系统所执行的安全性算法可描述如下：  
1)设置两个向量：➀工作向量Work,他表示系统可提供给进程继续运行所需的资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;➁Finish:他表示系统是狗有足够的资源分配给进程，使之运行完成。开始时做Finish\[i\] = false;当有足够资源分配给进程时，再令Finish\[i\] = true  
2)从进程集合中找到能满足下述条件的进程：  
➀Finish\[i\] = false;  
➁Need\[i,j\]<=Work\[j\];  
若找到执行步骤3),否则执行步骤4)  
3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给他的资源，故应执行

Work[j] = Work[j] + Allocation[i,j];
    Finish[i] = true;
    go to step 2;

4)如果所有进程Finish\[i\]=true 都满足，则表示系统处于安全状态；否则系统处于不安全状态

<table> 
 <thead> 
  <tr> 
   <th>时间性能(自左向右逐渐增大)</th> 
   <th>顺序搜索算法</th> 
   <th>伙伴算法</th> 
   <th>快速适应</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><strong>空间性能</strong></td> 
   <td>快速适应算法</td> 
   <td>伙伴系统</td> 
   <td>顺序搜索法</td> 
  </tr> 
 </tbody> 
</table>

**基于顺序搜索的动态分区分配算法**\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*  
**首次适应算法,循环首次适应算法,最佳适应算法和最坏适应算法**

1.  **首次适应(First fit,FF)算法**  
    FF算法要求空闲分区链以**地址递增**的次序链接,  
    优先利用内存中低址部分的空闲分区,从而保留了高址部分的大空闲区
2.  **循环首次适应(next fit,NF)算法**  
    从上次找到的空闲分区开始查找
3.  **最佳适应(best fit,BF)算法**  
    把总能满足要求的空闲分区分配给作业,容量从小到大的顺序形成空闲分区链
4.  **最坏适应(worst fit,WF)算法**  
    从中找一个最大空闲区,从中割一部分存储空间给作业使用  
    优点:是剩下的空闲区不至于太小,产生碎片的可能性最小,对中小作业有利  
    其容量从大到小的顺序  
    **基于索引搜索的动态分区分配算法**\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*
5.  **快速适应(quick fit)算法**  
    根据其容量大小进行分类,对于每一类具有相同容量的所有空闲分区,单独设立空闲分区链表,这样的系统存在多个空闲分区链表  
    该算法进行空闲分区分配时,不会对任何分区分割,所以能保留大的分区,满足对大空间的要求,也不会产生内存碎片.优点是查找效率高  
    缺点:为了有效合并分区,在分区归还主存时的算法复杂,系统开销较大.此外,该算法在分配空闲区时,是以进程为单位的,一个分区只属于一个进程,因此在进程分配的一个分区中,或多或少存在一定的浪费,这是典型的以空间换时间的算法
6.  **伙伴(buddy system)系统**  
    对于具有相同大小的所有空闲区间,单独设立一个空闲分区双向链表
7.  **哈希算法**  
    哈希算法利用哈希快速查找的优点,以及空闲分区在可利用空闲区表的分布规律,建立哈希函数,构造一张以空闲分区大小为关键字的哈希表,该表的每一个表项纪录了一个对应的空闲分区链表表头指针

## 页面置换算法 ##

1.  **最佳(Optimal)置换算法**  
    其选择的淘汰页面是以后用不使用的,或许是最长时间内不再被访问的页面  
    优点:可以保证最低的缺页率  
    缺点:无法预估哪个是未来最长时间内不再被访问的页面
2.  **先进先出页面置换算法**  
    淘汰最先进入内存的页面
3.  **最近最久未使用算法(LRU Least Recently Used)**  
    选择最近最久未使用的页面进行淘汰(看的是**时间**)
4.  **最少使用置换算法(Least Frequently Used,LFU)**  
    淘汰最近时期使用最少的页面(看的是**次数**)
5.  **Clock置换算法**  
    简单的Clock算法  
    当某页被访问时,期房文位被置1,置换算法在选择一页淘汰时,只需检查页的访问位。如果是0，就选择将该页换出；若为1，则重新将它置0，暂不换出，再按照FIFO算法检查下一个页面  
    改进型Clock置换算法  
    1类(A=0,M=0),表示该页最近既未被访问,又未被修改,是最佳淘汰页  
    2类(A=0,M=1),表示该页最近未被访问,但已被修改,并不是很好的淘汰页  
    3类(A=1,M=0),表示该页最近已被访问,但未被修改,该页有可能再被访问  
    4类(A=1,M=1),表示该页最近已被访问且被修改,该页可能再被访问
6.  **页面缓冲算法PBA Page Buffering Algorithm**

## 早期磁盘调度算法 ##

1.  **先来先服务**  
    公平简单,平均寻道距离大,仅应用到磁盘I/O较少的场合
2.  **最短寻道时间优先**  
    性能比先来先服务好  
    不能保证平均寻道时间最短  
    可能会出现饥饿现象

## 基于扫描的磁盘调度算法 ##

1.  **扫描(SCAN)算法**  
    寻道性能好,避免出现饥饿现象  
    不利于远离磁头一端的访问请求
2.  **循环(CSCAN)扫描算法**  
    消除了对两端磁道访问的不公平
3.  **NStepSCAN调度算法**  
    N步SCAN算法是将磁盘请求队列分成若干个长度为N的子队列,磁盘调度将按**FCFS**算法依次处理这些子队列
4.  **FSCAN调度算法**  
    是N步SCAN算法的简化,只将请求队列分成两个队列,一个是有当前所请求磁盘I/O的进程形成的队列,由磁盘调度按SCAN算法进行处理.另一个是在扫描期间,将新出现的所有请求磁盘I/O的进程放入等待处理的请求队列,这样,所有的新请求都被推迟到下一次扫描时处理