总结操作系统中各式各样的算法（一）

本文主要是介绍总结操作系统中各式各样的算法（一），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一.银行家算法

众所周知在操作系统中最重要的就是关注线程的执行状况，而并发的特性也导致了死锁概念的产生

非剥夺资源的竞争和进程的不恰当推进顺序会导致死锁。

有 3 种方式可以解决死锁问题：

• 预防死锁；
• 避免死锁；
• 死锁的检测和解除；

银行家算法就属于死锁避免。

银行家算法涉及到几种表示变量

1.可用资源向量 Available  表示系统中的可用资源

2.进程所需最大资源Max

3.系统分配资源Allocation

4.进程尚需各类资源数Need

不难推导出Need = Max - Allocation

现在咱们来分析一下进程申请资源的流程，首先进程发出request[A,k]请求(这里我定义为申请A类型资源K个)。发出请求后，系统首先判断这个k<need,如果不是那就认为出错，因为申请的超过了它所需最大的个数，然后接下来再进行判断这个k<Available(A)，如果不是就等待，如果是就分配。

但是这样分配的话就容易形成死锁，所以再分配之前我们想先让系统执行安全性算法，也就是我们说的银行家算法

初始时 安全序列 为空；
从 Need 矩阵中找到符合下面条件的行：该行对应的进程不在安全序列中，而且该行小于等于 Available 向量，找到后，把对应的进程加入 安全序列；若找不到，则执行步骤 4；
进程 P 进入 安全序列 后，可顺利执行，直至完成，并释放分配给它的资源，故应执行 Available = Available + Allocation[P]，其中 Allocation[P] 表示进程 P 在 Allocation 矩阵中对应的行，返回步骤 2 。
若此时安全序列中已有所有进程，则系统处于安全状态，否则处于不安全状态。

以上就是银行家算法的思想，其实是很好理解的，可以想象成我要用现有的资源去拿下你，拿下你之后你的资源就归并到我的资源里，我就可以去拿下更大的资源，如果到最后我没有拿下所有的资源我就GG，有点像大鱼吃小鱼了属于是。

CPU各种调度原理及调度算法

首先为了衡量CPU各种调度算法的优劣，我们需要一些衡量准则：

CPU使用率：指的是CPU处于忙状态的时间百分比

吞吐量：单位时间内完成的进程数量

周转时间：进程从初始化到结束（包括进程的等待时间）的总时间

等待时间：进程在就绪队列中的总时间

响应时间：从提交请求到产生响应所花费的总时间

调度算法大致是可以分成：批处理调度，交互式调度，实时调度

批处理调度

1.先来先服务（FCFS）

        使用队列数据结构先来先执行，就是最简单的一种调度算法，优点就是简单

缺点：

• 平均等待时间波动较大，短的进程可能排在长的进程后面得到执行
• I/O资源和CPU资源利用率较低，CPU密集型进程会导致I/O设备闲置，I/O密集型进程会导致CPU闲置

2.短进程优先（SPN）

        选择就绪队列中执行时间最短的进程占用CPU进行入运行状态，就绪队列按照预期的执行时间来排序（准确的进程云运行时间在未执行结束，不可知，只能通过预判断来获取大致运行时间，然后排序）

        SPN也分为可抢占式与非抢占式

        可抢占：又可称为Shortest-Remaining-Time(SPT)(最短剩余时间),它选择剩余运行时间最短的进程来调度执行，比如队列中来了一个执行时间为3的进程，CPU当前运行的进程剩余执行时间为8，则该调度算法会有限让新进的执行时间为3的进程先运行，因为该进程的剩余运行时间只有3，小于8

特点：最短进程优先算法具有最优的平均周转时间
最大的缺点就是长进程可能永远无法得到CPU进行处理

3.最高相应比优先算法

为每个线程计算相应比:

        R = w+s/s       w:等待时间       s:执行时间

它在短进程优先算法的基础之上改进，不可抢占，关注的是进程的等待时间，防止长进程的无限推迟

4.时间片轮转算法

时间片设计需要避免的两点：

• 时间片太大，等待的时间过长，极限的情况下退化成为FCFS算法
• 时间片太小，反应过于迅速，产生大量的上下文切换，会影响到系统的吞吐量

5.多级反馈队列算法

特征：进程就绪队列被划分成多个独立的子队列，每个队列都拥有自己的调度策略；队列间的调度是进程可以在不同队列间移动，也就是说某个进程在执行过程中优先级可能会发生改变；

注意点：

• 时间片的大小随着优先级的增加而增加
• 如果当前进程在时间片内没有执行完成、则降低到下一个优先级
• I/O密集型进程停留在高优先级，CPU密集型进程的优先级下降的很快

这篇关于总结操作系统中各式各样的算法（一）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！