1. 进程调度算法1——FCFS、SJF、HNNR
进程的调度方式有两种： 非剥夺调度方式（非抢占式）和剥夺调度方式（抢占方式）。
非抢占式：只允许进程主动放弃处理机。如进程运行结束、异常结束或主动请求I/O阻塞。在运行的过程中即使有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
抢占式：当一个进程正在处理机上执行时，如果有一个更重要更紧迫的进程需要处理机，则立即暂停正在执行的进程，将处理机分配给更重要更紧迫的那个进程。
下面介绍适用于早期操作系统几种进程调度的算法
先来先服务（FCFS）：按照到达的先后顺序调度，事实上就是等待时间越久的越优先得到服务。
下面表示按照先来先服务算法的执行顺序
计算进程的几个衡量指标：
短作业优先算法是非抢占式的算法，但是也有抢占式的版本—— 最短剩余时间优先算法（STRN,Shortest Remaining Time Next） 。
用于进程的调度算法称为短进程优先调度算法（SPF,Shortest Process First）。
短作业/进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业/进程.。
因为进程1最先达到，此时没有其他线程，所以进程1先被服务。当进程1运行完后，进程2和3已经到达，此时进程3需要的运行时间比进程2少，所以进程3先被服务…
计算进程的几个衡量指标：
最短剩余时间优先算法：每当有进程 加入就绪队列改变时就需要调度 ，如果新到达的进程的所需的运行时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。此外，当一个 进程完成时也需要调度 。
通过比较上面三组的平均周转时间、平均带权周转时间和平均等待时间可以看出，短作业优先算法可以减少进程的等待时间，对短作业有利。
高响应比优先算法： 非抢占式的调度算法 ，只有当前运行的进程主动放弃CPU时（正常/异常完成、或主动阻塞），才需要进行调度，调度时计算所有就绪进程的相应比，选响应比最高的进程上处理机。
响应比 = （等待时间 + 运行时间）/ 运行时间
上面的三种调度算法一般适用于 早期的批处理系统 ，没有考虑响应时间也不区分任务的紧急程度。因此对用户来说交互性差。
如发现错误，请指正！！！
2. 如何理解先来先服务fcfs和短作业优先sjf进程调度算法
先来先服务FCFS和短作业优先 和短作业优先SJF进程调度算法 先来先服务 和短作业优先 进程调度算法 1、实验目的 通过这次实验，加深对进程概念的理解，进一步掌握进程状态的 转变、进程调度的策略及对系统性能的评价方法。 2、需求分析 (1) 输入的形式和输入值的范围 输入值：进程个数Num 依次输入Num个进程的到达时间 依次输入Num个进程的服务时间 范围：0<Num<=100 范围： 范围： 输入要使用的算法（1-FCFS，2-SJF） 范围：1或者2 输出的形式（ 表示变量） (2) 输出的形式（X表示变量） 时刻X：进程X开始运行。 其完成时间：X 周转时间：X 带权周转时 间：X …（省略（Num-1）个） 平均周转时间：X 平均带权周转时间：X (3) 程序所能达到的功能 输入进程个数Num，每个进程到达时间ArrivalTime[i]，服务时间 ServiceTime[i]。采用先来先服务FCFS或者短作业优先SJF进程调度算 法进行调度，计算每个进程的完成时间、周转时间和带权周转时间， 并且统计Num个进程的平均周转时间和平均带权周转时间。 3、概要设计 说明本程序中用到的所有抽象数据类型的定义、 主程序的流程以 及各程序模块之间的层次(调用)关系。 4、详细设计 5、调试分析 (1)调试过程中遇到的问题以及解决方法， (1)调试过程中遇到的问题以及解决方法，设计与实现的回顾讨 调试过程中遇到的问题以及解决方法 论和分析 1 ○ 开始的时候没有判断进程是否到达， 导致短进程优先算法运 开始的时候没有判断进程是否到达， 行结果错误，后来加上了判断语句后就解决了改问题。 行结果错误，后来加上了判断语句后就解决了改问题。 2 ○ 基本完成的设计所要实现的功能， 总的来说， FCFS编写容易， 基本完成的设计所要实现的功能， 总的来说， FCFS编写容易， 编写容易 SJF 需要先找到已经到达的进程， 需要先找到已经到达的进程， 再从已经到达的进程里找到进程服务时 间最短的进程，再进行计算。 间最短的进程，再进行计算。 (2)算 (2)算法的改进设想 改进： 改进：即使用户输入的进程到达时间没有先后顺序也能准确 的计算出结果。（就是再加个循环，判断各个进程的到达时间先后， 的计算出结果。（就是再加个循环，判断各个进程的到达时间先后， 。（就是再加个循环 组成一个有序的序列） 组成一个有序的序列） (3)经验和体会 (3)经验和体会 通过本次实验， 通过本次实验，深入理解了先来先服务和短进程优先进程调 度算法的思想，培养了自己的动手能力，通过实践加深了记忆。 度算法的思想，培养了自己的动手能力，通过实践加深了记忆。
3. 作业调度算法一道题的解析——FCFS算法
10.1时，①装入主存，主存：15k，85k空闲，计算：①，等待队列：空
10.3时，②装入主存，主存：15k，60k，25k空闲，计算：①，等待队列：②
10.4时，①完成计算，主存：15k空闲，60k，25k空闲，计算：②，等待队列：空
10.5时，③要装入主存，但由于内存不足，等待
10.6时，④装入主存，主存：10k，5k空闲，60k，25k空闲，计算：②，等待队列：④
10.7时，⑤装入主存，主存：10k，5k空闲，60k，20k，5k空闲，计算：②，等待队列：④，⑤
10.9时，②完成计算，主存：10k，65k空闲，20k，5k空闲，计算：④，等待队列：⑤
10.9时，③由于存在超过50k的空间，装入主存，主存：10k，50k，15k空闲，20k，5k空闲
计算：④，等待：⑤，③（此时按照先来先服务调度，⑤为先来的作业）
10.13时，④完成计算，主存：10k空闲，50k，15k空闲，20k，5k空闲，计算：⑤，等待队列：③
10.15时，⑤完成计算，主存：15k空闲，60k，25k空闲，计算：②，等待队列：空
10.19时，③完成计算，主存：100k空闲，计算：空，等待队列：空
因此，顺序为①②④⑤③
4. 进程调度算法
调度算指:根据系统资源配策略所规定资源配算
、先先服务短作业(进程)优先调度算
1.
先先服务调度算先先服务(FCFS)调度算种简单调度算该算既用于作业调度
用于进程调度FCFS算比较利于作业(进程)利于短作业(进程)由知本算适合于CPU繁忙型作业
利于I/O繁忙型作业(进程)
2.
短作业(进程)优先调度算短作业(进程)优先调度算(SJ/PF)指短作业或短进程优先调度算该算既用于作业调度
用于进程调度其作业利;能保证紧迫性作业(进程)及处理;作业短估算
二、高优先权优先调度算
1.
优先权调度算类型照顾紧迫性作业使进入系统便获优先处理引入高优先权优先(FPF)调度算
算用批处理系统作作业调度算作种操作系统进程调度用于实系统其用于作业调度
备队列若干优先权高作业装入内存其用于进程调度处理机配给绪队列优先权高进程
进步该算两种:
1)非抢占式优先权算
2)抢占式优先权调度算(高性能计算机操作系统)
2.
优先权类型
于高优先权优先调度算其核于:使用静态优先权态优先权
及何确定进程优先权
3.
高响应比优先调度算
弥补短作业优先算足我引入态优先权使作业优先等级随着等待间增加速率a提高
该优先权变化规律描述:优先权=(等待间+要求服务间)/要求服务间;即
=(响应间)/要求服务间
三、基于间片轮转调度算
1.
间片轮转间片轮转般用于进程调度每调度CPU配队首进程并令其执行间片
执行间片用完由记器发钟断请求该进程停止并送往绪队列末尾;依循环
2.
级反馈队列调度算
级反馈队列调度算级反馈队列调度算必事先知道各种进程所需要执行间目前公认种较进程调度算
其实施程:
1)
设置绪队列并各队列赋予同优先级优先权越高队列
每进程所规定执行间片越
2)
新进程进入内存首先放入第队列末尾按FCFS原则排队等候调度
能间片完便撤离;未完转入第二队列末尾同等待调度……
作业(进程)第队列依第n队列(队列)便按第n队列间片轮转运行
3)
仅第队列空闲调度程序才调度第二队列进程运行;仅第1第(i-1)队列空
才调度第i队列进程运行并执行相应间片轮转
4)
处理机处理第i队列某进程新进程进入优先权较高队列
则新队列抢占运行处理机并运行进程放第i队列队尾
5. 常见的调度算法总结
一、FCFS——先来先服务和短作业（进程）优先调度算法
1. 先来先服务调度算法。
先来先服务（FCFS）调度算法是一种最简单的调度算法，该算法既可用于作业调度， 也可用于进程调度。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。由此可知，本算法适合于CPU繁忙型作业， 而不利于I/O繁忙型的作业（进程）。
2. 短作业（进程）优先调度算法。
短作业（进程）优先调度算法（SJ/PF）是指对短作业或短进程优先调度的算法，该算法既可用于作业调度， 也可用于进程调度。但其对长作业不利；不能保证紧迫性作业（进程）被及时处理；作业的长短只是被估算出来的。
二、FPF高优先权优先调度算法
1. 优先权调度算法的类型。
为了照顾紧迫性作业，使之进入系统后便获得优先处理，引入了最高优先权优先（FPF）调度算法。 此算法常被用在批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度，还可以用于实时系统中。当其用于作业调度， 将后备队列中若干个优先权最高的作业装入内存。当其用于进程调度时，把处理机分配给就绪队列中优先权最高的进程，此时， 又可以进一步把该算法分成以下两种：
1)非抢占式优先权算法
2)抢占式优先权调度算法（高性能计算机操作系统）
2. 优先权类型 。
对于最高优先权优先调度算法，其核心在于：它是使用静态优先权还是动态优先权， 以及如何确定进程的优先权。
3.动态优先权
高响应比优先调度算法为了弥补短作业优先算法的不足，我们引入动态优先权，使作业的优先等级随着等待时间的增加而以速率a提高。 该优先权变化规律可描述为：优先权=（等待时间+要求服务时间）/要求服务时间；即 =（响应时间）/要求服务时间
三、基于时间片的轮转调度算法
1.时间片轮转法。
时间片轮转法一般用于进程调度，每次调度，把CPU分配队首进程，并令其执行一个时间片。 当执行的时间片用完时，由一个记时器发出一个时钟中断请求，该进程被停止，并被送往就绪队列末尾；依次循环。
2. 多级反馈队列调度算法
多级反馈队列调度算法多级反馈队列调度算法，不必事先知道各种进程所需要执行的时间，它是目前被公认的一种较好的进程调度算法。 其实施过程如下：
1) 设置多个就绪队列，并为各个队列赋予不同的优先级。在优先权越高的队列中， 为每个进程所规定的执行时间片就越小。
2) 当一个新进程进入内存后，首先放入第一队列的末尾，按FCFS原则排队等候调度。 如果他能在一个时间片中完成，便可撤离；如果未完成，就转入第二队列的末尾，在同样等待调度…… 如此下去，当一个长作业（进程）从第一队列依次将到第n队列（最后队列）后，便按第n队列时间片轮转运行。
3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；
仅当第1到第（ i-1 ）队列空时， 才会调度第i队列中的进程运行，并执行相应的时间片轮转。
4) 如果处理机正在处理第i队列中某进程，又有新进程进入优先权较高的队列， 则此新队列抢占正在运行的处理机，并把正在运行的进程放在第i队列的队尾。
6. 电梯调度算法...
不管你是在北上广还是在港澳台，甚至三四线城市，凡是有规模的地区，高楼比比皆是。不管是写字楼，还是大型商城，让你最头痛的就是乘电梯，尤其是在赶时间的时候。
每天早上，那些差5分钟就迟到的程序员，在等电梯时，一般会做两件事：
前者可能是写字楼里上班族惯有的精神类疾病，但后者肯定是程序员的职业病。本文对“骂电梯”不给予任何指导性建议。
但说起电梯调度算法，我觉得还是可以给大家科普一下，好为大家在等电梯之余，打发时间而做出一点贡献。
（电梯调度算法可以参考各种硬盘换道算法，下面内容整理自网络）
先来先服务（FCFS-First Come First Serve）算法，是一种随即服务算法，它不仅仅没有对寻找楼层进行优化，也没有实时性的特征，它是一种最简单的电梯调度算法。
它根据乘客请求乘坐电梯的先后次序进行调度。此算法的 优点是公平、简单，且每个乘客的请求都能依次地得到处理，不会出现某一乘客的请求长期得不到满足的情况 。
这种方法在载荷较轻松的环境下，性能尚可接受，但是在载荷较大的情况下，这种算法的性能就会严重下降，甚至恶化。
人们之所以研究这种在载荷较大的情况下几乎不可用的算法，有两个原因：
最短寻找楼层时间优先（SSTF-Shortest Seek Time First）算法，它注重电梯寻找楼层的优化。最短寻找楼层时间优先算法选择下一个服务对象的原则是 最短寻找楼层的时间。
这样请求队列中距当前能够最先到达的楼层的请求信号就是下一个服务对象。
在重载荷的情况下，最短寻找楼层时间优先算法的平均响应时间较短，但响应时间的方差较大 ，原因是队列中的某些请求可能长时间得不到响应，出现所谓的“ 饿死”现象 。
扫描算法（SCAN） 是一种按照楼层顺序依次服务请求，它让电梯在最底层和最顶层之间连续往返运行，在运行过程中响应处在于电梯运行方向相同的各楼层上的请求。
它进行寻找楼层的优化，效率比较高，但它是一个 非实时算法 。扫描算法较好地解决了电梯移动的问题，在这个算法中，每个电梯响应乘客请求使乘客获得服务的次序是由其发出请求的乘客的位置与当前电梯位置之间的距离来决定的。
所有的与电梯运行方向相同的乘客的请求在一次电向上运行或向下运行的过程中完成， 免去了电梯频繁的来回移动 。
扫描算法的平均响应时间比最短寻找楼层时间优先算法长，但是响应时间方差比最短寻找楼层时间优先算法小， 从统计学角度来讲，扫描算法要比最短寻找楼层时间优先算法稳定 。
LOOK 算法是扫描算法（SCAN）的一种改进。对LOOK算法而言，电梯同样在最底层和最顶层之间运行。
但 当 LOOK 算法发现电梯所移动的方向上不再有请求时立即改变运行方向 ，而扫描算法则需要移动到最底层或者最顶层时才改变运行方向。
SATF（Shortest Access Time First）算法与 SSTF 算法的思想类似，唯一的区别就是 SATF 算法将 SSTF 算法中的寻找楼层时间改成了访问时间。
这是因为电梯技术发展到今天，寻找楼层的时间已经有了很大地改进， 但是电梯的运行当中等待乘客上梯时间却不是人为可以控制 。
SATF 算法考虑到了电梯运行过程中乘客上梯时间的影响 。
最早截止期优先（EDF-Earliest Deadline First）调度算法是最简单的实时电梯调度算法，它的 缺点就是造成电梯任意地寻找楼层，导致极低的电梯吞吐率。
它与 FCFS 调度算法类似，EDF 算法是电梯实时调度算法中最简单的调度算法。 它响应请求队列中时限最早的请求，是其它实时电梯调度算法性能衡量的基准和特例。
SCAN-EDF 算法是 SCAN 算法和 EDF 算法相结合的产物。SCAN-EDF 算法先按照 EDF 算法选择请求列队中哪一个是下一个服务对象，而对于具有相同时限的请求，则按照 SCAN 算法服务每一个请求。它的效率取决于有相同 deadline 的数目，因而效率是有限的。
PI（Priority Inversion）算法将请求队列中的请求分成两个优先级，它首先保证高优先级队列中的请求得到及时响应，再搞优先级队列为空的情况下在相应地优先级队列中的请求。
FD-SCAN（Feasible Deadline SCAN）算法首先从请求队列中找出时限最早、从当前位置开始移动又可以买足其时限要求的请求，作为下一次 SCAN 的方向。
并在电梯所在楼层向该请求信号运行的过程中响应处在与电梯运行方向相同且电梯可以经过的请求信号。
这种算法忽略了用 SCAN 算法相应其它请求的开销，因此并不能确保服务对象时限最终得到满足。
以上两结介绍了几种简单的电梯调度算法。
但是并不是说目前电梯调度只发展到这个层次。目前电梯的控制技术已经进入了电梯群控的时代。
随着微机在电梯系统中的应用和人工智能技术的发展，智能群控技术得以迅速发展起来。
由此，电梯的群控方面陆续发展出了一批新方法，包括：基于专家系统的电梯群控方法、基于模糊逻辑的电梯群控方法、基于遗产算法的电梯群控方法、基于胜景网络的电梯群控方法和基于模糊神经网络的电梯群控方法。
本人设置的电梯的初始状态，是对住宅楼的电梯的设置。
(1)建筑共有21层，其中含有地下一层（地下一层为停车场）。
(2)建筑内部设有两部电梯，编号分别为A梯、B梯。
(3)电梯内部有23个按钮，其中包括开门按钮、关门按钮和楼层按钮，编号为-1，1，2，3，4……20。
(4)电梯外部含有两个按钮，即向上运行按钮和向下运行按钮。建筑顶层与地下一层例外，建筑顶层只设置有向下运行按钮，地下一层只设置有向上运行按钮。
(5)电梯开关门完成时间设定为1秒。电梯到达每层后上下人的时间设定为8秒。电梯从静止开始运行到下一层的时间设置为2秒，而运行中通过一层的时间为1秒。
(6)在凌晨2：00——4：30之间，如若没有请求信号，A梯自动停在14层，B梯自动停在6层。
(7)当电梯下到-1层后，如果没有请求信号，电梯自动回到1层。
每一架电梯都有一个编号，以方便监控与维修。每一架电梯都有一实时监控器，负责监控电梯上下，向电梯升降盒发送启动、制动、加速、减速、开关电梯门的信号。若电梯发生故障，还应向相应的电梯负责人发送求救信号。
电梯内部的楼层按钮：
这样就表示乘客将要去往此层，电梯将开往相应层。当电梯到达该层后，按钮恢复可以使用状态。
电梯内部开门按钮：
如若电梯到了乘客曾经按下的楼层，但是无乘客按开门按钮，电梯将自动在停稳后1秒后自动开门。
电梯内部关门按钮：
电梯外部向上按钮：
电梯外部向下按钮：
你肯能意识到 哪个算法都不是一个最佳方案，只是它确实解决了一定情况的问题 。但是对一个优秀的程序员而言，研究各种算法是无比快乐的。也许你下一次面试，就有关于调度算法的问题。
7. 先来先服务调度算法的思想是什么
先来先服务(FCFS: first come first service)总是把当前处于就绪队列之首的那个进程调度到运行状态。也就说，它只考虑进程进入就绪队列的先后，而不考虑它的下一个CPU周期的长短及其他因素。FCFS算法简单易行，但性能却不大好。
8. 作业调度算法的先来先服务
先来先服务（FCFS,
First
Come
First
Serve）是最简单的调度算法，按先后顺序进行调度。
按照作业提交或进程变为就绪状态的先后次序，分派CPU；
当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。
在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。
比较有利于长作业，而不利于短作业。
有利于CPU繁忙的作业，而不利于I/O繁忙的作业。
9. 先来先服务(FCFS)调度算法 工作原理 优缺点
进程按到来的时间先后顺序依次被CPU处理。
优点：就是俗话说的“先来后到”。
缺点：如果先来的进程需要很长的处理时间，而后来的进程却很重要的。需要抢占CUP的时候，此调度算法就适用了。
10. 什么是短作业优先的作业调度算法
1.先来先服务调度算法（FCFS）:就是按照各个作业进入系统的自然次序来调度作业。这种调度算法的优点是实现简单，公平。其缺点是没有考虑到系统中各种资源的综合使用情况，往往使短作业的用户不满意，因为短作业等待处理的时间可能比实际运行时间长得多。
2.短作业优先调度算法(SPF): 就是优先调度并处理短作业，所谓短是指作业的运行时间短。而在作业未投入运行时，并不能知道它实际的运行时间的长短，因此需要用户在提交作业时同时提交作业运行时间的估计值。
3.最高响应比优先算法(HRN)：FCFS可能造成短作业用户不满，SPF可能使得长作业用户不满，于是提出HRN，选择响应比最高的作业运行。响应比=1+作业等待时间/作业处理时间。
4. 基于优先数调度算法(HPF)：每一个作业规定一个表示该作业优先级别的整数，当需要将新的作业由输入井调入内存处理时，优先选择优先数最高的作业。
5.均衡调度算法，即多级队列调度算法
基本概念：
作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)
作业平均周转时间(T)＝周转时间/作业个数
作业带权周转时间（Wi）＝周转时间/运行时间
响应比＝（等待时间＋运行时间）/运行时间