算法操作系统算法的都有哪些

操作系统算法的都有哪些

操作系统(英语 operating system缩写作OS)是管理计算机硬件与软件资源的计算机程序 同时也是计算机系统的内核与基石。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入设备与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。操作系统的类型非常多样不同机器安装的操作系统可从简单到复杂可从移动电话的嵌入式系统到超级计算机的大型操作系统。许多操作系统制造者对它涵盖范畴的定义也不尽一致例如有些操作系统集成了图形用户界面而有些仅使用命令行界面而将图形用户界面视为一种非必要的应用程序。下面是小编收集整理的操作系统算法的都有哪些范文欢迎借鉴参考。

操作系统算法的都有哪些(一)

在操作系统中存在多种调度算法其中有的调度算法适用于作业调度有的调度算法适用于进程调度有的调度算法两者都适用。下面介绍几种常用的调度算法。

先来先服务(FCFS)调度算法

FC FS调度算法是一种最简单的调度算法该调度算法既可以用于作业调度也可以用于进程调度。在作业调度中算法每次从后备作业队列中选择最先进入该队列的一个或几个作业将它们调入内存分配必要的资源创建进程并放入就绪队列。

在进程调度中 FC FS调度算法每次从就绪队列中选择最先进入该队列的进程将处理机分配给它使之投入运行直到完成或因某种原因而阻塞时才释放处理机。

下面通过一个实例来说明FC FS调度算法的性能。假设系统中有4个作业它们的提交时间分别是8、 8.4、 8.8、 9运行时间依次是2、 1 、 0.5、 0.2系统釆用FC FS调度算法这组作业的平均等待时间、平均周转时间和平均带权周转时间见表2-3。

平均等待时间t=(0+1 .6+2.2+2.5)/4=1 .575

平均周转时间T=(2+2.6+2.7+2.7)/4=2.5

平均带权周转时间W=(1+2.6+5.牡13.5)/4=5.625

FC FS调度算法属于不可剥夺算法。从表面上看它对所有作业都是公平的但若一个长作业先到达系统就会使后面许多短作业等待很长时间 因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略中使用。例如在

使用优先级作为调度策略的系统中往往对多个具有相同优先级的进程按FCFS原则处理。

FC FS调度算法的特点是算法简单但效率低;对长作业比较有利但对短作业不利(相对SJF和高响应比);有利于CPU繁忙型作业而不利于I/O繁忙型作业。

短作业优先(SJF)调度算法

短作业(进程)优先调度算法是指对短作业(进程)优先调度的算法。短作业优先(SJF)调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选择一个估计运行时间最短的进程将处理机分配给它使之立即执行直到完成或发生某事件而阻塞时才释放处理机。

例如考虑表2-3中给出的一组作业若系统釆用短作业优先调度算法其平均等待时间、平均周转时间和平均带权周转时间见表2-4。

平均等待时间t=(0+2.3+1 .4+1)/4=1 .175

平均周转时间T=(2+3.3+1 .9+1 .2)/4=2.1

平均带权周转时间W=(1+3.3+3.8+6)/4=3.525

SJF调度算法也存在不容忽视的缺点

该算法对长作业不利 由表2-3和表2-4可知 SJF调度算法中长作业的周转时间会增加。更严重的是如果有一长作业进入系统的后备队列 由于调度程序总是优先调度那些(即使是后进来的)短作业将导致长作业长期不被调度(“饥饿”现象注意区分“死锁”。后者是系统环形等待前者是调度策略问题)。

该算法完全未考虑作业的紧迫程度 因而不能保证紧迫性作业会被及时处理。

由于作业的长短只是根据用户所提供的估计执行时间而定的而用户又可能会有意或无意地缩短其作业的估计运行时间致使该算法不一定能真正做到短作业优先调度。

注意 SJF调度算法的平均等待时间、平均周转时间最少。

优先级调度算法

优先级调度算法又称优先权调度算法该算法既可以用于作业调度也可以用于进程调度该算法中的优先级用于描述作业运行的紧迫程度。

在作业调度中优先级调度算法每次从后备作业队列中选择优先级最髙的一个或几个作业将它们调入内存分配必要的资源创建进程并放入就绪队列。在进程调

度中优先级调度算法每次从就绪队列中选择优先级最高的进程将处理机分配给它使之投入运行。

根据新的更高优先级进程能否抢占正在执行的进程可将该调度算法分为

非剥夺式优先级调度算法。当某一个进程正在处理机上运行时 即使有某个更为重要或紧迫的进程进入就绪队列仍然让正在运行的进程继续运行直到由于其自身的原因而主动让出处理机时(任务完成或等待事件)才把处理机分配给更为重要或紧迫的进程。

剥夺式优先级调度算法。当一个进程正在处理机上运行时若有某个更为重要或紧迫的进程进入就绪队列则立即暂停正在运行的进程将处理机分配给更重要或紧迫的进程。

而根据进程创建后其优先级是否可以改变可以将进程优先级分为以下两种

静态优先级。优先级是在创建进程时确定的且在进程的整个运行期间保持不变。确定静态优先级的主要依据有进程类型、进程对资源的要求、用户要求。

动态优先级。在进程运行过程中根据进程情况的变化动态调整优先级。动态调整优先级的主要依据为进程占有CPU时间的长短、就绪进程等待CPU时间的长短。

高响应比优先调度算法

高响应比优先调度算法主要用于作业调度该算法是对FCFS调度算法和SJF调度算法的一种综合平衡 同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时先计算后备作业队列中每个作业的响应比从中选出响应比最高的作业投入运行。

根据公式可知

当作业的等待时间相同时则要求服务时间越短其响应比越高有利于短作业。

当要求服务时间相同时作业的响应比由其等待时间决定等待时间越长其响应比越高 因而它实现的是先来先服务。

对于长作业作业的响应比可以随等待时间的增加而提高 当其等待时间足够长时其响应比便可升到很高从而也可获得处理机。克服了饥饿状态兼顾了长作业。

时间片轮转调度算法

时间片轮转调度算法主要适用于分时系统。在这种算法中系统将所有就绪进程按到达时间的先后次序排成一个队列进程调度程序总是选择就绪队列中第一个进程执行 即先来先服务的原则但仅能运行一个时间片如100ms。在使用完一个时间

片后 即使进程并未完成其运行它也必须释放出(被剥夺)处理机给下一个就绪的进程而被剥夺的进程返回到就绪队列的末尾重新排队等候再次运行。

在时间片轮转调度算法中时间片的大小对系统性能的影响很大。如果时间片足够大 以至于所有进程都能在一个时间片内执行完毕则时间片轮转调度算法就退化为先来先服务调度算法。如果时间片很小那么处理机将在进程间过于频繁切换使处理机的开销增大而真正用于运行用户进程的时间将减少。因此时间片的大小应选择适当。

时间片的长短通常由以下因素确定系统的响应时间、就绪队列中的进程数目和系统的处理能力。

多级反馈队列调度算法(集合了前几种算法的优点)

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合和发展如图2-5所示。通过动态调整进程优先级和时间片大小多级反馈队列调度算法可以兼顾多方面的系统目标。例如为提高系统吞吐量和缩短平均周转时间而照顾短进程;为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程;同时也不必事先估计进程的执行时间。

多级反馈队列调度算法

多级反馈队列调度算法的实现思想如下

1 .应设置多个就绪队列并为各个队列赋予不同的优先级第1级队列的优先级最高第2级队列次之其余队列的优先级逐次降低。

2.赋予各个队列中进程执行时间片的大小也各不相同在优先级越高的队列中每个进程的运行时间片就越小。例如第2级队列的时间片要比第1级队列的时间片长一倍 ……第i+1级队列的时间片要比第i级队列的时间片长一倍。

3.当一个新进程进入内存后首先将它放入第1级队列的末尾按FC FS原则排队等待调度。当轮到该进程执行时如它能在该时间片内完成便可准备撤离系统;如果它在一个时间片结束时尚未完成调度程序便将该进程转入第2级队列的末尾再同样地按FCFS原则等待调度执行;如果它在第2级队列中运行一个时间片后仍未完成再以同样的方法放入第3级队列……如此下去 当一个长进程从第1级队列依次降到第n级队列后在第n级队列中便釆用时间片轮转的方式运行。

4.仅当第1级队列为空时调度程序才调度第2级队列中的进程运行;仅当第1~(i-1)级队列均为空时才会调度第i级队列中的进程运行。如果处理机正在执行第i级

队列中的某进程时又有新进程进入优先级较高的队列(第1 ~(i-1 )中的任何一个队列)则此时新进程将抢占正在运行进程的处理机 即由调度程序把正在运行的进程放回到第i级队列的末尾把处理机分配给新到的更高优先级的进程。

多级反馈队列的优势有

终端型作业用户短作业优先。

短批处理作业用户周转时间较短。

长批处理作业用户经过前面几个队列得到部分执行不会长期得不到处理。

操作系统算法的都有哪些(二)

学了半个学期的《操作系统》 是不是感觉“恍恍惚惚”?这周学的“银行家算法”是不是很多同学被绕晕了?作业也让人迷糊?那今天小编就给大家梳理梳理!

啥是银行家算法?

银行家算法是一种用来避免操作系统死锁出现的有效算法。为了让大家更好的理解我们在解释“银行家算法”之前先跟大家说说“死锁”的概念。

死锁?

是指两个或两个以上的进程在执行过程中 由于竞争资源或者由于彼此通信而造成的一种阻塞的现象若无外力作用它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁这些永远在互相等待的进程称为死锁进程。

死锁产生的四个必要条件

1)互斥条件在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源则请求者只能等待直至占有资源的进程用毕释放。

2)请求和保持条件指进程已经保持至少一个资源但又提出了新的资源请求而该资源已被其它进程占有此时请求进程阻塞但又对自己已获得的其它资源保持不放。

3)不抢占条件指进程已获得的资源在未使用完之前不能被剥夺只能在使用完时由自己释放。

4)循环等待条件指在发生死锁时必然存在一个进程——资源的环形链 即进程集合{P0 P1  P2 · · ·  Pn}中的P0正在等待一个P1占用的资源;P1正在等待P2占用的资源 …… Pn正在等待已被P0占用的资源。

为实现“银行家算法”系统必须设置若干数据结构。想更好解释“银行家算法”那就得先跟大家先解释操作系统安全状态和不安全状态 以及安全序列。

安全序列

是指一个进程序列{P1  … Pn}是安全的 即对于每一个进程Pi(1≤i≤n)它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。

安全状态

如果存在一个由系统中所有进程构成的安全序列P1  … Pn则系统处于安全状态。安全状态一定是没有死锁发生。

不安全状态

不存在一个安全序列。不安全状态不一定导致死锁。

接下来跟大家解释一下“银行家算法”的数据结构与两个向量!

数据结构

1)可利用资源向量Avai lable

是个含有m个元素的数组其中的每一个元素代表一类可利用的资源数目。如果Avai lable[j]=K则表示系统中现有Rj类资源K个。

2)最大需求矩阵Max

这是一个n×m的矩阵它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i ,j]=K则表示进程i需要Rj类资源的最大数目为K。

3)分配矩阵Al location

这也是一个n×m的矩阵它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Al location[i ,j]=K则表示进程i当前已分得Rj类资源的数目为K。

4)需求矩阵Need

这也是一个n×m的矩阵用以表示每一个进程尚需的各类资源数。如果

Need[i ,j]=K则表示进程i还需要Rj类资源K个方能完成其任务。

下面是三者之间的关系:

Need[i ,j]=Max[i ,j]-Al location[i ,j]

两个向量

1)工作向量Work表示系统可提供给进程继续运行所需的各类资源数目安全算法开始时Work:=Avai lable。

2)Finish[]表示系统是否有足够的资源分配给进程,使之运行完成。开始时先令Finish[i]:=false 当有足够资源分配给进程时再令Finish[i]:=true。

一些细小的知识点上面已经解释得差不多了!接下来开始跟大家解释“银行家算法”啦!

银行家算法

设Request(i)是进程Pi的请求向量如果Request(i)[j]=k表示进程Pi需要K个R(j)类型的资源。当Pi发现资源请求后系统将进行下列步骤

(1)如果Request(i)[j]<=Need[i ,j],边转向步骤2),否则认为出错 因为它所请求的资源数已超过它所宣布的最大值。

(2)如果Request(i)[j] <=Avai lable[i ,j] 便转向步骤3)否则表示尚无足够资源Pi需等待。

(3)系统试探着把资源分配给进程Pi 并需要修改下面数据结构中的数值;

Avai lable[j]=Avai lable[j] -Req uest(i)[j];

Al location[i ,j]=Al location[i ,j]+Request(i)[j];

Need[i ,j]=Need[i ,j] -Request(i)[j];

(4)系统执行安全性算法,检查此次资源分配后,系统是否处于安全状态。

所有关于“银行家算法”的概念都解释完毕啦!接下来让我们来“实践检验真理”!

操作系统算法的都有哪些(三)

磁盘调度在多道程序设计的计算机系统中各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。 由于有时候这些进程的发送请求的速度比磁盘响应的还要快因此我们有必要为每个磁盘设备建立一个等待队列常用的磁盘调度算法有以下四种

先来先服务算法(FCFS)

最短寻道时间优先算法(SSTF)

扫描算法(SCAN)

循环扫描算法(CSCAN)

例:假定某磁盘共有200个柱面编号为0-199如果在为访问143号柱面的请求者服务后 当前正在为访问125号柱面的请求服务 同时有若干请求者在等待服务它们每次要访问的柱面号为86 147 91  177 94  150 102 175 130

1 、先来先服务算法(FCFS)FirstCome First Service

这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单且每个进程的请求都能依次得到处理不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化在对磁盘的访

问请求比较多的情况下此算法将降低设备服务的吞吐量致使平均寻道时间可能较长但各进程得到服务的响应时间的变化幅度较小。

先来先服务(125)86.147.91 .177.94.150.102.175.130

2、最短寻道时间优先算法(SSTF)Shortest Seek Time First

该算法选择这样的进程其要求访问的磁道与当前磁头所在的磁道距离最近 以使每次的寻道时间最短该算法可以得到比较好的吞吐量但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的 因而导致响应时间的变化幅度很大。在服务请求很多的情况下对内外边缘磁道的请求将会无限期的被延迟有些请求的响应时间将不可预期。

最短寻道时间优先(125)130.147.150.175.177.102.94.91 .86

3、扫描算法(SCAN)电梯调度

扫描算法不仅考虑到欲访问的磁道与当前磁道的距离更优先考虑的是磁头的当前移动方向。例如 当磁头正在自里向外移动时扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外又是距离最近的。这样自里向外地访问直到再无更外的磁道需要访问才将磁臂换向 自外向里移动。这时 同样也是每次选择这样的进程来调度 即其要访问的磁道在当前磁道之内从而避免了饥饿现象的出现。 由于这种算法中磁头移动的规律颇似电梯的运行故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点而具有最短寻道时间优先算法的优点即吞吐量较大平均响应时间较小但由于是摆动式的扫描方法两侧磁道被访问的频率仍低于中间磁道。

电梯调度(125)102.94.91 .86.130.147.150.175.177

4、循环扫描算法(CSCAN)

循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的 当磁头到达磁盘的一端并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理而磁盘另一端的请求密度相当高且这些访问请求等待的时间较长为了解决这种情况循环扫描算法规定磁头单向移动。例如只自里向外移动 当磁头移到最外的被访问磁道时磁头立即返回到最里的欲访磁道 即将最小磁道号紧接着最大磁道号构成循环进行扫描。

循环扫描(125)130.147.150.175.177.86.91 .94.102

5、平均寻道距离

假设当前磁头在67号要求访问的磁道号顺序为98,25,63,97,56,51 ,55,55,6FIFO算法的服务序列是 98,25,63,97,56,51 ,55,55,6

磁头移动的总距离distance=

(98-67)+(98-25)+(63-25)+(97-63)+(97-56)+(56-51)+(55-51)+(55-55)+(55-6)SSTF算法的服务序列是:63,56,55,55,51 ,25,6,97,98

磁头移动的总距离distance=

(67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(97-6)+(98-97)SCAN算法的服务序列是 63,56,55,55,51 ,25,6,97,98

磁头移动的总距离distance=

(67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(97-6)+(98-97)我发现这里例子举的不好 SSTF和SCAN算法的服务序列竟是一样的尴尬!

C S CA N算法的服务序列是 63,56,55,55,51 ,25,6,98,97

磁头移动的总距离distance=

(67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(100-98)+(98-97)