先进先出调度算法

㈠ 进程调度算法的国内外研究现状有哪些

调度算法是指：根据系统的资源分配策略所规定的资源分配算法。常见的进程调度算法有：

1.先来先去服务

2.时间片轮转法

3.多级反馈队列算法

4.最短进程优先

5.最短剩余时间优先

6.最高响应比优先

7.多级反馈队列调度算法

一、先来先去服务

先来先去服务调度算法是一种最简单的调度算法，也称为先进先出或严格排队方案。当每个进程就绪后，它加入就绪队列。当前正运行的进程停止执行，选择在就绪队列中存在时间最长的进程运行。该算法既可以用于作业调度，也可以用于进程调度。先来先去服务比较适合于常作业（进程），而不利于段作业（进程）。

二、时间片轮转法

轮转法是基于适中的抢占策略的，以一个周期性间隔产生时钟中断，当中断发生后，当前正在运行的进程被置于就绪队列中，然后基于先来先去服务策略选择下一个就绪作业的运行。这种技术也称为时间片，因为每个进程再被抢占之前都给定一片时间。

三、最短进程优先

最短进程优先是一个非抢占策略，他的原则是下一次选择预计处理时间最短的进程，因此短进程将会越过长作业，跳至队列头。该算法即可用于作业调度，也可用于进程调度。但是他对长作业不利，不能保证紧迫性作业（进程）被及时处理，作业的长短只是被估算出来的。

四、最短剩余时间优先

最短剩余时间是针对最短进程优先增加了抢占机制的版本。在这种情况下，进程调度总是选择预期剩余时间最短的进程。当一个进程加入到就绪队列时，他可能比当前运行的进程具有更短的剩余时间，因此只要新进程就绪，调度程序就能可能抢占当前正在运行的进程。像最短进程优先一样，调度程序正在执行选择函数是必须有关于处理时间的估计，并且存在长进程饥饿的危险。

㈡ FIFO调度算法和LRU算法

FIFO：先进先出调度算法
LRU：最近最久未使用调度算法

两者都是缓存调度算法，经常用作内存的页面置换算法。

打一个比方，帮助你理解。

你有很多的书，比如说10000本。
由于你的书实在太多了，你只能放在地下室里面。
你看书的时候不会在地下室看书，而是在书房看书。
每次，你想看书都必须跑到地下室去找出来你想看的书，
然后抱回来放到书桌上，之后才开始看。
还有就是，有一些书你会反复的看，今天看了也许过几天又要看。
总之，你自己是不知道你哪天会需要看哪本书的。
你的老师每天下课的时候会给你布置一个书单，让你晚上回去去看哪本书。
（假设你老师让你看的书在你的地下室里面都有）

跑地下室当然是非常麻烦的，所以你希望你的经常看的那些书最好放在书桌上。
但是你的书房的书桌同时只能摆放10本书（这个是假设的啊）。
那么，问题来了。
到底把哪些说留在书桌上最好呢？
这里说的最好，就是说你尽量少的跑地下室去找书。

为了解决这个问题，人们发明了很多的算法。
其中，比较常见的就是上面这两种：FIFO算法和LRU算法。

FIFO算法
很简单，我把书桌上的10本书按照放置时间先后堆放成一堆。
这里的放置时间，就是说这本书在我的书桌上放了几天了。
每次要看书的时候，我先在书桌上找，找到就直接可以读了。
读完之后放回原来的位置就可以，不打乱顺序。
如果书桌上面没有我要读的书，就去地下室找。
找来之后，我就把书桌上放的时间最长的那本（也就是
书堆里面最下面的那本书）放回地下室。
然后把我今天需要看的这本书放在书堆的最上面。

LRU算法
也不难，我把书桌上的10本书按照阅读时间先后堆放成一堆。
这里的阅读时间，就是说我最近一次读这本书是几天之前。
每次要看书的时候，我先在书桌上找，找到就直接可以读了。
读完之后放在书堆的最上面。
如果书桌上面没有我要读的书，就去地下室找。
找来之后，我就把书桌上最久没有阅读的那本
（也就是书堆里面最下面的那本书）放回地下室。
然后把我今天需要看的这本书放在书堆的最上面。

上面这个比方，相信你可以看明白吧。
这里的地下室对应内存，书桌对应缓存，书对应页面。

㈢ 页面调度先进先出算法（FIFO） 用C语言描述 欢迎高手前来挑战

c语言实现的页面调度算法,用三种算法实现调度1.先进先出2.OPT3.LRU 2.页面序列从指定的文本文件（TXT文件）中取出3.输出：第一行：每次淘汰的页面号 第二行：显示缺页的总次数(上机已经运行通过!!)-pages scheling algorithm, a three-Scheling Algorithm 1. FIFO 2.OPT3.LRU 2. Pages from the designated sequence of text files (TXT) out of three. Output : the first line : each of the pages out of the second line : show na the total number of pages (on the plane had run through! !)

㈣ linux进程调度的三种策略是什么

linux内核的三种主要调度策略：
1，SCHED_OTHER 分时调度策略，
2，SCHED_FIFO实时调度策略，先到先服务
3，SCHED_RR实时调度策略，时间片轮转

实时进程将得到优先调用，实时进程根据实时优先级决定调度权值。分时进程则通过nice和counter值决定权值，nice越小，counter越大，被调度的概率越大，也就是曾经使用了cpu最少的进程将会得到优先调度。

SHCED_RR和SCHED_FIFO的不同：
当采用SHCED_RR策略的进程的时间片用完，系统将重新分配时间片，并置于就绪队列尾。放在队列尾保证了所有具有相同优先级的RR任务的调度公平。
SCHED_FIFO一旦占用cpu则一直运行。一直运行直到有更高优先级任务到达或自己放弃。
如果有相同优先级的实时进程（根据优先级计算的调度权值是一样的）已经准备好，FIFO时必须等待该进程主动放弃后才可以运行这个优先级相同的任务。而RR可以让每个任务都执行一段时间。

相同点：
RR和FIFO都只用于实时任务。
创建时优先级大于0(1-99)。
按照可抢占优先级调度算法进行。
就绪态的实时任务立即抢占非实时任务。

所有任务都采用linux分时调度策略时：
1，创建任务指定采用分时调度策略，并指定优先级nice值(-20~19)。
2，将根据每个任务的nice值确定在cpu上的执行时间(counter)。
3，如果没有等待资源，则将该任务加入到就绪队列中。
4，调度程序遍历就绪队列中的任务，通过对每个任务动态优先级的计算权值(counter+20-nice)结果，选择计算结果最大的一个去运行，当这个时间片用完后(counter减至0)或者主动放弃cpu时，该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。
5，此时调度程序重复上面计算过程，转到第4步。
6，当调度程序发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。

所有任务都采用FIFO时：
1，创建进程时指定采用FIFO，并设置实时优先级rt_priority(1-99)。
2，如果没有等待资源，则将该任务加入到就绪队列中。
3，调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu，该FIFO任务将一直占有cpu直到有优先级更高的任务就绪(即使优先级相同也不行)或者主动放弃(等待资源)。
4，调度程序发现有优先级更高的任务到达(高优先级任务可能被中断或定时器任务唤醒，再或被当前运行的任务唤醒，等等)，则调度程序立即在当前任务堆栈中保存当前cpu寄存器的所有数据，重新从高优先级任务的堆栈中加载寄存器数据到cpu，此时高优先级的任务开始运行。重复第3步。
5，如果当前任务因等待资源而主动放弃cpu使用权，则该任务将从就绪队列中删除，加入等待队列，此时重复第3步。

所有任务都采用RR调度策略时：
1，创建任务时指定调度参数为RR，并设置任务的实时优先级和nice值(nice值将会转换为该任务的时间片的长度)。
2，如果没有等待资源，则将该任务加入到就绪队列中。
3，调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu。
4，如果就绪队列中的RR任务时间片为0，则会根据nice值设置该任务的时间片，同时将该任务放入就绪队列的末尾。重复步骤3。
5，当前任务由于等待资源而主动退出cpu，则其加入等待队列中。重复步骤3。

系统中既有分时调度，又有时间片轮转调度和先进先出调度：
1，RR调度和FIFO调度的进程属于实时进程，以分时调度的进程是非实时进程。
2，当实时进程准备就绪后，如果当前cpu正在运行非实时进程，则实时进程立即抢占非实时进程。
3，RR进程和FIFO进程都采用实时优先级做为调度的权值标准，RR是FIFO的一个延伸。FIFO时，如果两个进程的优先级一样，则这两个优先级一样的进程具体执行哪一个是由其在队列中的未知决定的，这样导致一些不公正性(优先级是一样的，为什么要让你一直运行?),如果将两个优先级一样的任务的调度策略都设为RR,则保证了这两个任务可以循环执行，保证了公平。

Ingo Molnar-实时补丁
为了能并入主流内核，Ingo Molnar的实时补丁也采用了非常灵活的策略，它支持四种抢占模式：
1．No Forced Preemption (Server)，这种模式等同于没有使能抢占选项的标准内核，主要适用于科学计算等服务器环境。
2．Voluntary Kernel Preemption (Desktop)，这种模式使能了自愿抢占，但仍然失效抢占内核选项，它通过增加抢占点缩减了抢占延迟，因此适用于一些需要较好的响应性的环境，如桌面环境，当然这种好的响应性是以牺牲一些吞吐率为代价的。
3．Preemptible Kernel (Low-Latency Desktop)，这种模式既包含了自愿抢占，又使能了可抢占内核选项，因此有很好的响应延迟，实际上在一定程度上已经达到了软实时性。它主要适用于桌面和一些嵌入式系统，但是吞吐率比模式2更低。
4．Complete Preemption (Real-Time)，这种模式使能了所有实时功能，因此完全能够满足软实时需求，它适用于延迟要求为100微秒或稍低的实时系统。
实现实时是以牺牲系统的吞吐率为代价的，因此实时性越好，系统吞吐率就越低。

㈤ 虚拟存储器采用的页面调度算法是“先进先出”（FIFO）算法吗

虚拟存储器采用的页面调度算法是“先进先出”（FIFO）算法吗。常见的替换算法有4种。

①随机算法：用软件或硬件随机数产生器确定替换的页面。

②先进先出：先调入主存的页面先替换。

③近期最少使用算法（LRU，Least Recently Used）：替换最长时间不用的页面。

④最优算法：替换最长时间以后才使用的页面。这是理想化的算法，只能作为衡量其他各种算法优劣的标准。

虚拟存储器的效率是系统性能评价的重要内容，它与主存容量、页面大小、命中率，程序局部性和替换算法等因素有关。

(5)先进先出调度算法扩展阅读

虚拟存储器地址变换基本上有3种形虚拟存储器工作过程式：全联想变换、直接变换和组联想变换。任何逻辑空间页面能够变换到物理空间任何页面位置的方式称为全联想变换。每个逻辑空间页面只能变换到物理空间一个特定页面的方式称为直接变换。

组联想变换是指各组之间是直接变换，而组内各页间则是全联想变换。替换规则用来确定替换主存中哪一部分，以便腾空部分主存，存放来自辅存要调入的那部分内容。

在段式虚拟存储系统中，虚拟地址由段号和段内地址组成，虚拟地址到实存地址的变换通过段表来实现。每个程序设置一个段表，段表的每一个表项对应一个段，每个表项至少包括三个字段：有效位(指明该段是否已经调入主存)、段起址(该段在实存中的首地址)和段长(记录该段的实际长度)。

㈥ 操作系统先进先出(FIFO)和先来先服务(FCFS)有什么区别

1.先来先服务调度算法（FCFS）:就是按照各个作业进入系统的自然次序来调度作业。这种调度算法的优点是实现简单，公平。其缺点是没有考虑到系统中各种资源的综合使用情况，往往使短作业的用户不满意，因为短作业等待处理的时间可能比实际运行时间长得多。

2.先进先出算法(FIFO)：按照进程进入就绪队列的先后次序来选择。即每当进入进程调度，总是把就绪队列的队首进程投入运行。

㈦ 页面淘汰算法

LRU（2个块）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 3 3 2 2 5 5 2 2 2 2 7 7 3 3 1 1 3 3
2 2 4 4 1 1 6 6 1 1 3 3 6 6 2 2 2 2 6
缺页中断18次

LRU（4个块）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 1 1 6 6 6 6 6 6 6
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 5 5 5 5 5 3 3 3 3 3 3 3 3 3
4 4 4 4 6 6 6 6 6 7 7 7 7 1 1 1 1
缺页中断次数10次

FIFO（2个块）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 3 3 6 6 2 2 2 3 3
2 2 4 4 1 1 6 6 1 1 2 7 7 3 3 1 1 1 6
缺页中断次数18次

FIFO（4个块）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 5 5 5 5 5 3 3 3 3 3 1 1 1 1
2 2 2 2 2 2 6 6 6 6 6 7 7 7 7 7 7 3 7
3 3 3 3 3 3 2 2 2 2 2 6 6 6 6 6 6 6
4 4 4 4 4 4 1 1 1 1 1 1 2 2 2 2 2
缺页中断次数：14次

㈧ hrn算法调度顺序是怎样确定的

FIFO：即先进先出算法，就是先进去的页在位置不够时先淘汰。所以具体如下：
主存开始为空
访问1，1不在主存中，产生缺页中断，添加，主存里现在是：1
访问2，2不在主存中，产生缺页中断，添加，主存里现在是：1,2
以此类推，
1,2,3（缺页中断）
1,2,3,6（缺页中断）
访问4，4不在主存中，缺页中断，主存满了，最早的1淘汰，主存里现在是：2,3,6,4
然后3,6,4,7（缺页中断，2淘汰）
然后3，3在主存中，不产生中断
然后6,4,7,2（缺页中断，3淘汰）
4,7,2,1（缺页中断，6淘汰）
4在主存中，不中断
7在主存中，不中断
7,2,1,5（缺页中断，4淘汰）
2,1,5,6（缺页中断，7淘汰）
5在主存中，不中断
2在主存中，不中断
1在主存中，不中断
整个FIFO过程就是这样。

LRU是最近最久未使用的先淘汰，具体如下：
1（缺页中断）
1,2（缺页中断）
1,2,3（缺页中断）
1,2,3,6（缺页中断）
2,3,6,4（缺页中断，1最久没用过，淘汰）
3,6,4,7（缺页中断，2最久没用过，淘汰）
3在主存中，不中断，3最近使用过，主存中顺序调整为6,4,7,3
4,7,3,2（缺页中断，6最久没用过，淘汰）
7,3,2,1（缺页中断，4最久没用过，淘汰）
3,2,1,4（缺页中断，7最久没用过，淘汰）
2,1,4,7（缺页中断，3最久没用过，淘汰）
1,4,7,5（缺页中断，2最久没用过，淘汰）
4,7,5,6（缺页中断，1最久没用过，淘汰）
5在主存中，调整顺序为4,7,6,5
7,6,5,2（缺页中断，4最久没用过，淘汰）
6,5,2,1（缺页中断，7最久没用过，淘汰）
整个LRU过程就是这样。

全手打求采纳谢谢~！如有问题请追问~

㈨ 最佳页面淘汰算法是怎样计算的

<1> 先进先出调度算法
先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。
<2>最近最少调度算法
先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。
<3>最近最不常用调度算法
由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由硬件或操作系统自动定时清零。
（2）缺页调度次数和缺页中断率、缺页置换率计算
缺页中断次数是缺页时发出缺页中断的次数。
缺页中断率=缺页中断次数/总的页面引用次数*100%
缺页调度次数是调入新页时需要进行页面调度的次数
缺页置换率=缺页调度次数/总的页面引用次数*100%

㈩ 什么是进程调度常用的进程调度算法有哪些试比较他们之间的性能。 什么是进程调度

进程调度，用户进程数进程调度一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。无论是在批处理系统还是分时系统中，用户进程数 进程调度 一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。 进程调度的的分级 高级、中级和低级调度作业从提交开始直到完成，往往要经历下述三级调度： 高级调度：(High-Level Scheling)又称为作业调度，它决定把后备作业调入内存运行； 低级调度：(Low-Level Scheling)又称为进程调度，它决定把就绪队列的某进程获得CPU； 中级调度：(Intermediate-Level Scheling)又称为在虚拟存储器中引入，在内、外存对换区进行进程对换。先进先出算法 进程调度 算法总是把处理机分配给最先进入就绪队列的进程，一个进程一旦分得处理机，便一直执行下去，直到该进程完成或阻塞时，才释放处理机。 例如，有三个进程P1、P2和P3先后进入就绪队列，它们的执行期分别是21、6和3个单位时间， 执行情况如下图： 对于P1、P2、P3的周转时间为21、27、30，平均周转时间为26。 可见，FIFO算法服务质量不佳，容易引起作业用户不满，常作为一种辅助调度算法。 最短CPU运行期优先调度算法(SCBF--Shortest CPU Burst First) 该算法从就绪队列中选出“下一个CPU执行期”最短的进程，为之分配处理机。 例如，在就绪队列中有四个进程P1、P2、P3和P4，它们的下一个执行期分别是16、12、4和3个单位时间，执行情况如下图： P1、P2、P3和P4的周转时间分别为35、19、7、3，平均周转时间为16。 该算法虽可获得较好的调度性能，但难以准确地知道下一个CPU执行期，而只能根据每一个进程的执行历史来预测。 轮转法 前几种算法主要用于批处理系统中，不能作为分时系统中的主调度算法，在分时系统中，都采用时间片轮转法。 简单轮转法：系统将所有就绪进程按FIFO规则排队，按一定的时间间隔把处理机分配给队列中的进程。这样，就绪队列中所有进程均可获得一个时间片的处理机而运行。 多级队列方法：将系统中所有进程分成若干类，每类为一级。 多级反馈队列 多级反馈队列方式是在系统中设置多个就绪队列，并赋予各队列以不同的优先权