总结操作系统中各式各样的算法(一)

2021/10/4 20:42:47

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

一.银行家算法

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

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

有 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密集型进程的优先级下降的很快



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


扫一扫关注最新编程教程