Ⅰ 磁盘的电梯算法的寻道时间怎么算
先来先服务FCFS:公平，简单，每个进程的请求都能依次得到处理。没有对寻道优化，平均寻道时间长。最短时间优先调度算法SSTF:要求访问的磁道是当前磁头所在的磁道最近，每次寻道时间最短。可能导致一些请求无限期推延。电梯调度算法SCAN:不仅考虑当前磁道的距离，优先考虑在磁道前进方向的最短时间，排除磁头在盘面上的往复运动。电梯原理。N-SCAN:是SCAN的改良。磁头改变方向时，以到达请求服务的最短时间。对中间请求服务更有利。C-SCAN:磁头单项移动。消除N-SCAN对两端请求的不公平。
Ⅱ 电梯调度算法...
不管你是在北上广还是在港澳台，甚至三四线城市，凡是有规模的地区，高楼比比皆是。不管是写字楼，还是大型商城，让你最头痛的就是乘电梯，尤其是在赶时间的时候。
每天早上，那些差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秒后自动开门。
电梯内部关门按钮：
电梯外部向上按钮：
电梯外部向下按钮：
你肯能意识到 哪个算法都不是一个最佳方案，只是它确实解决了一定情况的问题 。但是对一个优秀的程序员而言，研究各种算法是无比快乐的。也许你下一次面试，就有关于调度算法的问题。
Ⅲ 操作系统模拟电梯调度算法C语言程序
这是数学建模的题目，太难了。
只能给点提示，希望有用。一，用到随机函数。二，调度算法为FIFO和电梯调度。参考操作系统。三，文件io用到#include
<fstream>头文件
Ⅳ java模拟实现两部电梯同时工作的高效算法
1. 各电梯控制：
a. 实现一个方法，返回本电梯到请求楼层上、下的时间（或者简单点的，层数）；
b. 任务接受：接受用户楼层上、下请求任务
2. 主控部分：
a. 当用户按下上、下请求时，通过调用两个电梯的上面所说的服务，进行比较决断最优时间电梯；
b. 给最最优电梯发送任务；
3. 主控与各电梯控制之间的通讯可以通过多种方式实现；
Ⅳ 如何将各种算法应用到实际的电梯调度中
说明 假设大厦有31层楼.电梯每经过1层(不论上下行)的时间是4秒.也就是说,电梯从1楼到31楼且中间不停则需要(31-1)*4=120秒.电梯每次需要停10秒,因此,如果电梯每层都停一次,就需要30*4+29*10=410秒.与此同时,员工步行一层楼(不论上下行)需要20秒,从1楼到31楼就需要30*20=600秒.明显,这个主意不好.因此,很多员工依赖电梯前往他们的办公室.现在我们需要设计一个方案，这个方案的设计目标是让最后一个到达办公室的员工花费最短的时间(也就是说,他并不保证每一位员工都能最快到达自己办公室).比如,如果员工想到达4,5和10层,则电梯的运行方案是在4和10层停止.因为电梯在第12秒到达4层,停止10秒,则电梯到达10层需要3*4+10+6*4=46秒.按此计划,住在4层的员工需要12秒,5层的员工需要12+20=32秒,10层的员工需要46秒.因此,最后到达办公室的员工需要46秒.对于大家来说,这是个不错的方案.
实现 下面就详细说一说我实现的具体方式，虽然花了我近2天的时间，但是其实并不是很复杂，这里我本着抛砖引玉的原则，下面就一起来看看吧：
我们将定义一个名叫Case的class用来存储一些要测试的数据，然后再定义一个叫CaseUtil的class用来实现我们的方案。
首先我说一下具体得思路：这里我只考虑从下到上的方案(从上到下其实是一样的，具体自己想吧)。举个例子，假设当前的楼层是【29 30 31】.3个。那么我们该如何做呢？
首先，不管怎么说，假设最后一层即31的到达时间为 （31-1）* 4 + （stopNums-1）*10 说明一下，这里为了简单起见我们就按照案例的数据进行分析，实际上4表示电梯经过每层所需时间，而10表示电梯每层停靠的时间。上面的stopNums是什么呢？就是电梯到达31层时所有的停靠次数，减去1是除去31层得停靠。而最后一层到达的人则很可能为最后一位到达的人，为什么不是一定呢，按照本例，上面举得例子就可以很简单的看出，在28、31停2次即可，此时最后一个到达的就是地30层的人了。当然在仅仅是在本例中，实际上会由于具体数值不一样而有不同。所以这里我用了可能，而它也和我们的最优解很接近了，而这给了我想法。虽然最后一层不一定是最后一位，但已经很接近了，而它所花费的时间，仅仅只和一个变量有关，即stopNums，即可以得出如下结论：
电梯的停靠次数越少，最后一层的时间也就越少，同样最佳时间也就越少。
假设我们有一个方法可以根据当前的停靠次数来计算最佳的停靠方案，那么我们该如何得到实际最佳方案呢？下面的一段代码很好的可以达到我们的目标。
Ⅵ 2018-06-09
一、常见的批处理作业调度算法
1.先来先服务调度算法（FCFS）:就是按照各个作业进入系统的自然次序来调度作业。这种调度算法的优点是实现简单，公平。其缺点是没有考虑到系统中各种资源的综合使用情况，往往使短作业的用户不满意，因为短作业等待处理的时间可能比实际运行时间长得多。
2.短作业优先调度算法(SPF): 就是优先调度并处理短作业，所谓短是指作业的运行时间短。而在作业未投入运行时，并不能知道它实际的运行时间的长短，因此需要用户在提交作业时同时提交作业运行时间的估计值。
3.最高响应比优先算法(HRN)：FCFS可能造成短作业用户不满，SPF可能使得长作业用户不满，于是提出HRN，选择响应比最高的作业运行。响应比=1+作业等待时间/作业处理时间。
4. 基于优先数调度算法(HPF)：每一个作业规定一个表示该作业优先级别的整数，当需要将新的作业由输入井调入内存处理时，优先选择优先数最高的作业。
5.均衡调度算法，即多级队列调度算法
基本概念：
作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)
作业平均周转时间(T)＝周转时间/作业个数
作业带权周转时间（Wi）＝周转时间/运行时间
响应比＝（等待时间＋运行时间）/运行时间
二、进程调度算法
1.先进先出算法(FIFO)：按照进程进入就绪队列的先后次序来选择。即每当进入进程调度，总是把就绪队列的队首进程投入运行。
2. 时间片轮转算法(RR)：分时系统的一种调度算法。轮转的基本思想是，将CPU的处理时间划分成一个个的时间片，就绪队列中的进程轮流运行一个时间片。当时间片结束时，就强迫进程让出CPU，该进程进入就绪队列，等待下一次调度，同时，进程调度又去选择就绪队列中的一个进程，分配给它一个时间片，以投入运行。
3. 最高优先级算法(HPF)：进程调度每次将处理机分配给具有最高优先级的就绪进程。最高优先级算法可与不同的CPU方式结合形成可抢占式最高优先级算法和不可抢占式最高优先级算法。
4. 多级队列反馈法：几种调度算法的结合形式多级队列方式。
三、空闲分区分配算法
\1. 首先适应算法：当接到内存申请时，查找分区说明表，找到第一个满足申请长度的空闲区，将其分割并分配。此算法简单，可以快速做出分配决定。
2. 最佳适应算法：当接到内存申请时，查找分区说明表，找到第一个能满足申请长度的最小空闲区，将其进行分割并分配。此算法最节约空间，因为它尽量不分割到大的空闲区，其缺点是可能会形成很多很小的空闲分区，称为“碎片”。
3. 最坏适应算法：当接到内存申请时，查找分区说明表，找到能满足申请要求的最大的空闲区。该算法的优点是避免形成碎片，而缺点是分割了大的空闲区后，在遇到较大的程序申请内存时，无法满足的可能性较大。
四、虚拟页式存储管理中的页面置换算法
1.理想页面置换算法(OPT)：这是一种理想的算法，在实际中不可能实现。该算法的思想是：发生缺页时，选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。
2.先进先出页面置换算法(FIFO)：选择最先进入内存的页面予以淘汰。
3. 最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。
4.最少使用算法（LFU）：选择到当前时间为止被访问次数最少的页转换。
三、磁盘调度
1.先来先服务（FCFS）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置
2.最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题
3.扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。
4.循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。
对一个进程来说,一个重要的指标是它执行所需要的时间. 从进程提交到进程完成的时间间隔为周转时间.也就是等待进入内存的时间,在就绪队列中等待的时间,在 CPU中执行的时间和I/O操作的时间的总和.
例1.设一个系统中有5个进程，它们的到达时间和服务时间如下，A的到达时间为0，服务时间为3；B的到达时间为2，服务时间为6；C的到达时间为4，服务时间为4；D的到达时间为6，服务时间为5；E的 到达时间为8，服务时间为2，忽略1/0以及其他开销时间，若分别按先来先服务（fFCFS）进行CPU调度，其平均周转时间为？
10.2
6.4
8.6
4.5
先来先服务调度算法
进程名 到达时间 服务时间 开始执行时间 完成时间 周转时间
A 0 3 0 3 3
B 2 6 3 9 7
C 4 4 9 13 9
D 6 5 13 18 12
E 8 2 18 20 12
周转时间 = 完成时间 - 到达时间
平均周转时间 = 所有进程周转时间 / 进程数 = （3+7+9+12+12）/ 5 = 8.6
单道批处理系统中有4个作业，J1的提交时间8.0，运行时间为2.0；J2的提交时间8.6，运行时间为0.6；J3提交时间8.8，运行时间为0.2；J4的提交时间9.0，运行时间为0.5。在采用响应比高者优先调度算法时，其平均周转时间为T为（）小时？
2.5
1.8
1.975
2.675
周转时间=作业完成时间-作业提交时间
响应比=（作业等待时间+作业执行时间）/作业执行时间
当提交J1时，只有J1作业，执行J1，J1的周转时间为2，此时时间为10.
J2、J3、J4提交时，由于正在执行J1，因此等待。
当J1执行完毕（此时时间为10），J2、J3、J4的等待时间分别为：1.4,1.2,1，
其响应比分别为：1.4/0.6+1=3.33 1.2/0.2+1=7 1/0.5+1=3，因此执行J3，J3的周转时间为1.2+0.2=1.4
当J3执行完毕（此时时间为10.2），J2和J4的等待时间分别为1.6,1.2，
其响应比分别为：1.6/0.6+1=3.66 1.2/0.5+1=3.4，因此执行J2，J2的周转时间为1.6+0.6=2.2
执行J2完毕后时间为10.8，接下来执行J4，执行完后时时间为11.3，J4的周转时间为2.3
于是平均周转时间为（2+1.4+2.2+2.3）/4=1.975
如果系统作业几乎同时到达，则使系统平均作业周转时间最短的算法是短作业优先。
例3、
现有4个同时到达的作业J1,J2,J3和J4,它们的执行时间分别是3小时,5小时,7小时,9小时系统按单道方式运行且采用短作业优先算法,则平均周转时间是()小时
12.5
24
19
6
作业到达时间执行时间开始时间完成时间周转时间
J103033
J20 5388
J30781515
J409152424
平均周转时间（3+8+15+24）/4=12.5
有4个进程A,B,C,D,设它们依次进入就绪队列，因相差时间很短可视为同时到达。4个进程按轮转法分别运行11,7,2,和4个时间单位，设时间片为1。四个进程的平均周转时间为 （）？
15.25
16.25
16.75
17.25
17.75
18.25
A:1 4 4 3 3 2 2 2 1 1 1 共24
B:2 4 4 3 3 2 2 共20
C:3 4 共7
D:4 4 3 3 共14
字母后面的数字为等待的时间加运行时间
平均周转时间为（24+20+7+14）/4=16.25
例5、假设系统按单值方式运行且采用最短作业优先算法，有J1,J2,J3,J4共4个作业同时到达，则以下哪几种情况下的平均周转时间为10分钟?
执行时间J1:1分钟 J2:5分钟 J3:9分钟 J4:13分钟
执行时间J1:1分钟 J2:4分钟 J3:7分钟 J4:10分钟
执行时间J1:2分钟 J2:4分钟 J3:6分钟 J4:8分钟
执行时间J1:3分钟 J2:6分钟 J3:9分钟 J4:12分钟
首先，短作业优先则短时间的作业利用资源，其余的作业等待
根据平均周转时间概念，将所有作业"等待时间"加上"运行时间"除以"作业数量"即可得到平均周转时间
A： (J1执行1分钟 + J2等待1分钟 + J2执行5分钟 + J3等待6分钟 + J3执行9分钟 + J4等待15分钟 + J4执行13分钟) / 4 = 50/4 = 12.5
B： (J1执行1分钟 + J2等待1分钟 + J2执行4分钟 + J3等待5分钟 + J3执行7分钟 + J4等待12分钟 + J4执行10分钟) / 4 = 40/4 = 10
C： (J1执行2分钟 + J2等待2分钟 + J2执行4分钟 + J3等待6分钟 + J3执行6分钟 + J4等待12分钟 + J4执行8分钟) / 4 = 40/4 = 10
D： (J1执行3分钟 + J2等待3分钟 + J2执行6分钟 + J3等待9分钟 + J3执行9分钟 + J4等待18分钟 + J4执行12分钟) / 4 = 50/4 = 12.5
例6、假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。 表1 进程到达和需要服务时间 进程 到达时间 服务时间 A 0 3 B 2 6 C 4 4 D 6 5 E 8 2
表2 进程的完成时间和周转时间
进程 A B C D E 平均
FCFS 完成时间 3 9 13 18 20
周转时间 3 7 9 12 12 8.6
带权周转时间 1.00 1.17 2.25 2.40 6.00 2.56
SPF(非抢占) 完成时间 3 9 15 20 11
周转时间 3 7 11 14 3 7.6
带权周转时间 1.00 1.17 1.75 2.80 1.50 1.84
SPF(抢占) 完成时间 3 15 8 20 10
周转时间 3 13 4 14 2 7.2
带权周转时间 1.00 2.16 1.00 2.80 1.00 1.59
例7、假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示： 作业 进入系统时间 估计运行时间/分钟 1 8:00 40 2 8:20 30 3 8:30 12 4 9:00 18
5 9:10 5
如果应用先来先服务和应用最短作业优先的作业调度算法，试将下面表格填写完整。
(1) 如果应用先来先服务的作业调度算法，试将下面表格填写完整。
作业 进入系统时间 估计运行时间/分钟 开始时间 结束时间 周转时间/分钟
1 8:00 40 8：00 8：40 40
2 8:20 30 8：40 9：10 50
3 8:30 12 9：10 9：22 52
4 9:00 18 9：22 9：40 40
5 9:10 5 9：40 9：45 35
作业平均周转时间T= 43.4 217
2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。 作业 进入系统时间 估计运行时间/分钟 开始时间 结束时间 周转时间/分钟 1 8:00 40 8：00 8：40 40 2 8:20 30 8：52 9：22 62 3 8:30 12 8：40 8：52 22 4 9:00 18 9：27 9：45 45 5 9:10 5 9：22 9：27 17作业平均周转时间T= 37.2 186
CPU和两台输入/输出设备(I1,I2)多道程序设计环境下,同时有三个作业J1,J2,J3进行,这三个作业
使用CPU和输入/输出设备的顺序和时间如下所示:
J1:I2(35ms);CPU(15ms);I1(35ms);CPU(15ms);I2(25ms)
J2:I1(25ms);CPU(30ms);I2(35ms)
J3:CPU(30ms);I1(25ms);CPU(15ms);I1(15ms);
假定CPU,I1,I2都能并行工作,J1的优先级最高,J2次之,J3优先级最低,优先级高的作业可以抢占优先级低的作业的CPU,但不能抢占I1,I2,作业从J3开始到完成需要多少时间?
Ⅶ 电梯调度算法
(1)电梯调度算法的处理次序为:
5
8
1
4
3
6
2
7
(2)最短寻找时间优先算法的处理次序为:
5
8
6
2
7
1
4
3