1. 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开始到完成需要多少时间?
2. 操作系统磁盘调度算法wenti
SCAN调度算法就是电梯调度算法，顾名思义就是如果开始时磁头往外就一直要到最外面，然后再返回向里（磁头编号一般是最外面为0号往里增加），就像电梯若往下则一直要下到最底层才会再上升一样。这里的从左端开始是什么意思呢？一般是题目中会给出此时磁头指向里或是指向外的。向外则向比它小的方向扫描，向里则向比它大的方向扫描，而若求寻道时间还要知道每移动一个磁道所需的时间t,寻道时间T1={（53-37）+（37-14）+（14-0）+（65-0）+（67-65）+（98-67）+（122-98）+（124-122）+（183-124）+（199-183）}*t=(53+199)*t=252t.
CSCAN循环扫描调度算法是先找出最靠近磁头位置的下一个，或是按题中规定的方向，反正就是只能是单向扫描。例如题中65距53最近，于是最先到65然后继续朝增加的方向，直到最大，然后又立即回到最小的0号开始，计算时返回的那段距离也必需计算在内。T2={(199-53)+（199-0）+(37-0)}*t=382t.
显然此时SCAN算法更省时。
3. fifo sstf scan cscan 哪个效率最高
这是一种先进先出置换算法(first in first out-fifo)，该算法总是淘汰最先进入主存的页面，即选择主存中驻留时间最久的页面给予淘汰。
4. 请教关于磁盘调度的问题，到底按照哪种方法来啊
嗯，是问的这个问题我看的答案是大纲后面的答案，2010年第45题，为方便大家看，我把部分题目写在下面某计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间记录16384个磁盘块的空闲状态，某单面磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。在某时刻，磁头位于100号磁道处，并沿着磁道增大的方向移动，磁道号请求队列是50，90，30，120答案给出的磁道移动时间是170ms（没给过程），那就应该是按照100->120->30->50->90的顺序来移动的了说明CSCAN算法 不移动到头，移动到请求的磁道即可，并且返回到最小的磁道时的移动时间也要计算但是我在有的辅导书上看到的是说，不计算返回时间刚翻了下课本，汤小丹的操作系统第三版196页，根据叙述和例子，意思是说不用移动到头，只到请求的最大磁道，并且返回到请求的最小磁道的时间需要计算而关于SCAN算法，课本上也是说只移动到请求的最大磁道而我在文×都的辅导书上看到的，关于SCAN算法还特地强调了要移动到头，甚至根据磁盘扇区的数目和每磁道的扇区数计算出总磁道数再计算移动时间，真是纠结啊
5. scan与cscan有什么异同
CSCAN美国Horner公司开发的一种通信网络，采用Controller Area Network技术。
循环扫描CSCAN（Circular SCAN）
为了减少SCAN算法造成的某些进程的请求被严重推迟，CSCAN算法规定磁头单向移动。
6. 目前常用的磁盘调度算法有哪几种每种算法优先考虑的问题是什么
(1)先来先服务(FCFS，First-Come First-Served)
此算法根据进程请求访问磁盘的先后次序进行调度。
(2)最短寻道时间优先(SSTF ，ShortestSeekTimeFirst)
该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。
(3)扫描(SCAN)算法
SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。
(4)循环扫描(CSCAN)算法
CSCAN算法规定磁头单向移动，避免了扫描算法导致的某些进程磁盘请求的严重延迟。
(5) N-Step-SCAN和FSCAN调度算法
1) N-Step-SCAN算法。为克服前述SSTF、SCAN、CSCAN等调度算法都可能出现的磁臂停留在某处不动的情况即磁臂粘着现象，将磁盘请求队列分成若干个长度为N的子队列，按先来先服务算法依次处理这些子队列，而各队列分别以扫描算法进行处理。
2) FSCAN算法
FSCAN算法实质上是N步SCAN算法的简化。它只将磁盘请求访问队列分成两个子队列。一是当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。另一个队列则是在 扫描期间，新出现的所有请求磁盘I/O进程的队列，放入另一等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。
7. 计算机试卷求解
假设磁头当前位于第105道,正在向磁道序号增加的方向移动,现有一个磁道访问请求序列为35,45,12,68,110,180,170,195,采用SCAN调度(电梯调度)算得到的
8. 磁盘调度 算法
(1)FCFS(先来先服务):
143-86=57
147-86=61
147-91=56
177-91=86
177-94=97
150-94=56
150-102=48
175-102=73
175-130=45
57+61+56+86+97+56+48+73+45=579
(2)SSTF(最短寻道时间优先)：
寻道顺序：143（当前），147，150，130，102，94，91，86，175，177；
4+3+20+28+8+3+5+89+2=162
(3)SCAN：
当前方向：从143#向磁道号增加的方向
依次访问：143（当前），147，150，175，177
再从递减方向：130，102，94，91，86
4+3+25+2+47+28+8+3+5=125
(4)LOOK:(即SCAN，电梯调度算法)
(5)CSCAN:
当前方向：从143#向磁道号增加的方向
依次访问：143（当前），147，150，175，177
再从0开始增加方向：86,91,94,102,130
4+3+25+2+91+5+3+8+28=169
9. 常见的磁盘调度算法有哪些，有什么优缺点
1.先来先服务（FCFS）
2.最短寻道时间优先（SSTF）
3.扫描（scan）算法
4循环扫描（CSCAN）算法
5.NStep和FSCAN调度算法
10. 请帮我把这个C语言小程序改为C++的，通过了追加分70+20一定给
#include <stdio.h>
void main()
{
char algorithm;
float l,m;
int a[100];
int direct,begin,i,j,t,k,n=0;
printf("请输入要调度序列的个数：\n");
scanf("%d",&n);
printf("请输入要调度的序列：\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("\n");
for(i=0;i<n-2;i++)
{
for(j=n-1;j>=1;j--)
{
if(a[j]<a[j-1])
{
t=a[j];
a[j]=a[j-1];
a[j-1]=t;
}
}
}
/* for(i=0;i<n;i++)
cout<<a[i]<<endl;*/
printf("请选择磁盘调度算法,其中s代表scan算法，c代表cscan算法:\n");
//cin>>algorithm;
scanf("%c",&algorithm);
//以下为scan算法实现磁盘调度
if(algorithm=='s')
{
printf("请输入开始的磁盘序列号：\n");
scanf("%d",&begin);
printf("\n");
for(i=0;i<n;i++)
{
if(a[i]==begin)
k=i;
}
printf("请输入访问方向,其中1为增大方向，0为减小方向：\n");
scanf("%d",&direct);
printf("\n");
m=float(n)-1;
if(direct==1)
{
for(i=k;i<n;i++)
//cout<<a[i]<<" ";
printf("%d ",a[i]);
for(i=k-1;i>=0;i--)
//cout<<a[i]<<" ";
printf("%d ",a[i]);
//cout<<endl;
printf("\n");
l=((a[n-1]-a[k])+(a[n-1]-a[0]))/m;
//cout<<"平均寻道长度为："<<l<<endl;
printf("平均寻道长度为：%d\n",l);
}
else
{
for(i=k;i>=0;i--)
//cout<<a[i]<<" ";
printf("%d ",a[i]);
for(i=k+1;i<n;i++)
printf("%d ",a[i]);
printf("\n");
l=((a[k]-a[0])+(a[n-1]-a[0]))/m;
printf("平均寻道长度为：%d\n",l);
}
}
//以下为cscan算法实现调度
else
{
//cout<<"请输入开始的磁盘序列号："<<endl;
printf("请输入开始的磁盘序列号：\n");
//cin>>begin;
// cout<<endl;
scanf("%d",&begin);
printf("\n");
for(i=0;i<n;i++)
{
if(a[i]==begin)
k=i;
}
//cout<<"请输入访问方向,其中1为增大方向，0为减小方向："<<endl;
printf("请输入访问方向,其中1为增大方向，0为减小方向：\n");
//cin>>direct;
//cout<<endl;
scanf("%d",&direct);
printf("\n");
m=float(n)-1;
if(direct==1)
{
for(i=k;i<n;i++)
printf("%d ",a[i]);
for(i=0;i<k;i++)
printf("%d ",a[i]);
printf("\n");
l=((a[n-1]-a[k])+(a[n-1]-a[0])+(a[k-1]-a[0]))/m;
printf("平均寻道长度为：%d\n",l);
}
else
{
for(i=k;i>=0;i--)
printf("%d ",a[i]);
for(i=n-1;i>k;i--)
printf("%d ",a[i]);
printf("\n");
l=((a[k]-a[0])+(a[n-1]-a[0])+(a[n-1]-a[k+1]))/m;
printf("平均寻道长度为：%d\n",l);
}
}
}