搜档网
当前位置:搜档网 › 操作系统处理器调度算法C++程序

操作系统处理器调度算法C++程序

操作系统处理器调度算法C++程序
操作系统处理器调度算法C++程序

一、先来先服务算法

1.程序简介

先来先服务算法按照作业进入系统后备作业队列的先后次序挑选作业,先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后,移入就绪队列.这是一种非剥夺式调度算法,易于实现,但效率不高.只顾及作业的等候时间,未考虑作业要求服务时间的长短,不利于短作业而优待长作业,不利于I/O繁忙型作业而有利于CPU繁忙型作业.有时为了等待场作业执行结束,短作业的周转时间和带全周转时间将变得很大,从而若干作业的平均周转时间和平均带权周转时间也变得很大。

2.分析

1.先定义一个数组代表各作业运行的时间,再定义一个数组代表各作业到达系统的时间,注意到达系统的时间以第一个作业为0基础(注意:若各程序都同时到达系统,则到达系统时间都为0)。

2.输入作业数。

3.然后运用循环结构累积作业周转时间和带权周转时间。

4.最后,作业周转时间和带权周转时间分别除以作业数即可得到平均作业周转时间和平均带权周转时间。

3.详细设计

源程序如下:

#include

#include

using namespace std;

int main()

{

int n,a[100],b[100];

double s[100],m[100],T=0,W=0;

cout<<"请输入作业数:"<

cin>>n;

cout<<"请分别输入各作业到达系统的时间:"<

for(int i=0;i

{

cin>>b[i];

}

cout<<"请分别输入各作业所运行的时间:"<

for(i=0;i

{

cin>>a[i];s[0]=0;

s[i+1]=s[i]+a[i];

m[i+1]=(s[i+1]-b[i])/a[i];

T=T+s[i+1]-b[i];

W=W+m[i+1];

}

cout<<"平均周转时间为:"<

cout<<"平均带权周转时间为:"<

return 0;

}

4.运行与测试

1.运行程序,输入作业数,如A.1所示。

A1 启动界面

2.输入各作业到达系统的时间,如A.2所示。

A2 输入各作业到达系统的时间

3.输入各作业所运行的时间,如A.3所示。

A3 输入各作业运行的时间

二、最短作业优先算法

1. 程序简介

最短作业优先算法以进入系统的作业所要求的CPU运行时间的长短为标准,总是选取预计计算时间最短的作业投入运行。这是一种非剥夺式调度算法,能克服FCFS算法偏爱长作业的缺点,易于实现,但执行效率也不高。

2. 分析

1. 分两种情况来介绍这种算法,一是各作业到达系统的时间都相同,二是各作业到达系统的时间不同,且以第一个作业到达系统的时间为0作基础。

2. 到达系统时间都相同的情况只要累积CPU运行的时间,最后加一个排序函数即可。

3. 到达系统时间不相同的情况则是要在前面FCFS的基础上加一个排序函数即可。

4. 注意本程序认为第一个作业完成后,其它作业都已经到达系统了。

3. 详细设计

源程序如下:

//SJF(到达系统时间都相同的情况)

#include

using namespace std;

void B(float a[],int size)

{

float t;

for(int i=1;i

{

for(int j=0;j

if(a[j]>a[j+1])

{

t=a[j];a[j]=a[j+1];a[j+1]=t;}

}

}

int main(void)

{

float n,a[100];

double s[100],m[100],T=0,W=0;

cout<<"请输入作业数:"<

cin>>n;

cout<<"请分别输入各作业所运行的时间:"<

for(int i=0;i

cin>>a[i];

B(a,n);

cout<<"作业调度顺序为:"<

for(i=0;i

{

cout<

s[0]=0;

s[i+1]=s[i]+a[i];

m[i+1]=s[i+1]/a[i];

T=T+s[i+1];

W=W+m[i+1];

}cout<

cout<<"平均周转时间为:"<

cout<<"平均带权周转时间为:"<

return 0;

}

//SJF(到达系统时间不相同的情况)

#include

using namespace std;

void B(float a[],int size)

{

float t;

for(int i=2;i

{

for(int j=1;j

if(a[j]>a[j+1])

{

t=a[j];a[j]=a[j+1];a[j+1]=t;}

}

}

int main(void)

{

float n,a[100],b[100];

double s[100],m[100],T=0,W=0;

cout<<"请输入作业数:"<

cin>>n;

cout<<"请分别输入各作业所运行的时间:"<

for(int i=0;i

cin>>a[i];

B(a,n);

cout<<"作业调度顺序为:"<

for(i=0;i

{

cout<

}cout<

cout<<"请分别输入各作业到达系统的时间:"<

for(i=0;i

{

cin>>b[i];

}

for(i=0;i

{

s[0]=0;

s[i+1]=s[i]+a[i];

m[i+1]=(s[i+1]-b[i])/a[i];

T=T+s[i+1]-b[i];

W=W+m[i+1];

}

cout<<"平均周转时间为:"<

cout<<"平均带权周转时间为:"<

return 0;

}

4.运行与测试

//SJF(到达系统时间都相同的情况)

1. 运行程序,输入作业数,如A.1所示。

A1 启动界面

2. 输入各作业所运行的时间,如A.2所示。

A2 输入各作业所运行的时间

//SJF(到达系统时间不相同的情况)

1. 运行程序,输入作业数,如A.1所示。

A1 启动界面

2. 输入各作业所运行的时间,如A.2所示。

A2 输入各作业所运行的时间

3. 输入各作业到达系统的时间,如A.3所示。

A3 输入各作业到达系统的时间

三、优先级调度算法

1.程序简介

优先级调度算法根据确定的优先级来选取进程/线程,总是选择就绪队列中的优先级最高者投入运行。本实验介绍的是非剥夺式优先级调度算法,如果在就绪队列中出现优先级更高的就让当前进程/线程继续运行,直到它结束或出现等待事件而主动让出处理器,再调度另一个优先级高的进程/线程运行。

2. 分析

1. 先定义一个二维数组a[i][0]代表各作业的优先级,a[i][1]代表各作业运行的时间。

2. 输入作业数。

3. 根据排序函数得出作业调度顺序。

4. 最后,累积得作业周转时间和带权周转时间后分别除以作业数即可得到平均作业周转时间和平均带权周转时间。

3. 详细设计

源程序如下:

#include

using namespace std;

void B(float a[][2],int size)

{

float t,p;

for(int i=0;i

{

for(int j=0;j

if(a[j][0]>a[j+1][0])

{

t=a[j][0];a[j][0]=a[j+1][0];a[j+1][0]=t;

p=a[j][1];a[j][1]=a[j+1][1];a[j+1][1]=p;

}

}

}

int main(void)

{

float n,a[100][2];

double s[100][2],m[100][2],T=0,W=0;

cout<<"请输入作业数:"<

cin>>n;

cout<<"请分别输入各作业优先级和所运行的时间:"<

for(int i=0;i

{

cin>>a[i][0]>>a[i][1];

}B(a,n);

cout<<"作业调度顺序为:"<

for(i=0;i

{

cout<

s[0][1]=0;

s[i+1][1]=s[i][1]+a[i][1];

m[i+1][1]=s[i+1][1]/a[i][1];

T=T+s[i+1][1];

W=W+m[i+1][1];

}cout<

cout<<"平均周转时间为:"<

cout<<"平均带权周转时间为:"<

return 0;

}

4. 运行与测试

1. 运行程序,输入作业数,如A.1所示。

A1 启动界面

2.输入各作业优先级和所运行的时间,如A.2所示。

A2 输入各作业的优先级和所运行的时间

四、响应比最高者优先算法

1. 程序简介

响应比最高者优先算法是介乎这两种算法之间的一种折中的非剥夺式算法,既考虑作业的等待时间,又考虑作业的处理时间,这样既照顾短作业又不会使长作业的等待时间过长,有效地改进调度的性能。HRRF算法的缺点是每次计算各道作业的响应比会导致一定时间的开销,其性能比SJF算法略差。

2. 分析

1. 先定义一个二维数组a[i][0]代表各作业的等待时间,a[i][1]代表各作业运行的时间,a[i][2]代表响应比-1。

2. 输入作业数。

3. 根据排序函数得出作业调度顺序。

4. 最后,累积得作业周转时间和带权周转时间后分别除以作业数即可得到平均作业周转时间和平均带权周转时间。

3. 详细设计

源程序如下:

#include

using namespace std;

void B(double a[][3],int size)

{

double t,p,s;

for(int i=2;i

{

for(int j=1;j

if(a[j][2]

{

s=a[j][2];a[j][2]=a[j+1][2];a[j+1][2]=s;

t=a[j][0];a[j][0]=a[j+1][0];a[j+1][0]=t;

p=a[j][1];a[j][1]=a[j+1][1];a[j+1][1]=p;

}

}

}

int main(void)

{

double n,a[100][3],s[100][3],m[100][3],T=0,W=0;

cout<<"请输入作业数:"<

cin>>n;

cout<<"请分别输入各作业等待时间和所运行的时间:"<

for(int i=0;i

{

cin>>a[i][0]>>a[i][1];

}

for(i=1;i

{

a[i][2]=(a[0][1]-a[i][0])/a[i][1];

}

B(a,n);

cout<<"作业调度顺序为:"<

for(i=0;i

{

cout<

s[0][1]=0;

s[i+1][1]=s[i][1]+a[i][1];

m[i+1][1]=(s[i+1][1]-a[i][0])/a[i][1];

T=T+s[i+1][1]-a[i][0];

W=W+m[i+1][1];

}cout<

cout<<"平均周转时间为:"<

cout<<"平均带权周转时间为:"<

return 0;

}

4. 运行与测试

1. 运行程序,输入作业数,如A.1所示。

A1 启动界面

3.输入各作业等待时间和所运行的时间,如A.2所示。

A2 输入各作业等待时间和所运行的时间

操作系统之调度算法和死锁中的银行家算法习题答案

操作系统之调度算法和死锁中的银行家算法习 题答案 集团文件发布号:(9816-UATWW-MWUB-WUNN-INNUL-DQQTY-

1. 有三个批处理作业,第一个作业 10:00 到达,需要执行 2 小时;第二个作业在10:10到达,需要执行 1 小时;第三个作业在 10:25 到达,需要执行 25 分钟。分别采用先来先服 务,短作业优先和最高响应比优先三种调度算法,各自的平均周转时间是多少?解: 先来先服务: (结束时间=上一个作业的结束时间+执行时间 周转时间=结束时间-到达时间=等待时间+执行时间) 按到达先后,执行顺序:1->2->3 短作业优先: 1)初始只有作业1,所以先执行作业1,结束时间是12:00,此时有作业2和3; 2)作业3需要时间短,所以先执行; 3)最后执行作业2 最高响应比优先:

高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间,综合了先来先服务和最短作业优先两种算法的特点。 1)10:00只有作业1到达,所以先执行作业1; 2)12:00时有作业2和3, 作业2:等待时间=12:00-10:10=110m;响应比=1+110/60=2.8; 作业3:等待时间=12:00-10:25=95m,响应比=1+95/25=4.8; 所以先执行作业3 3)执行作业2 2. 在一单道批处理系统中,一组作业的提交时刻和运行时间如下表所示。试计算一下三种 作业调度算法的平均周转时间 T 和平均带权周转时间 W。 ( 1)先来先服务;( 2)短作业优先( 3)高响应比优先 解: 先来先服务: 作业顺序:1,2,3,4 短作业优先: 作业顺序:

操作系统处理器调度算法C++程序

一、先来先服务算法 1.程序简介 先来先服务算法按照作业进入系统后备作业队列的先后次序挑选作业,先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后,移入就绪队列.这是一种非剥夺式调度算法,易于实现,但效率不高.只顾及作业的等候时间,未考虑作业要求服务时间的长短,不利于短作业而优待长作业,不利于I/O繁忙型作业而有利于CPU繁忙型作业.有时为了等待场作业执行结束,短作业的周转时间和带全周转时间将变得很大,从而若干作业的平均周转时间和平均带权周转时间也变得很大。 2.分析 1.先定义一个数组代表各作业运行的时间,再定义一个数组代表各作业到达系统的时间,注意到达系统的时间以第一个作业为0基础(注意:若各程序都同时到达系统,则到达系统时间都为0)。 2.输入作业数。 3.然后运用循环结构累积作业周转时间和带权周转时间。 4.最后,作业周转时间和带权周转时间分别除以作业数即可得到平均作业周转时间和平均带权周转时间。 3.详细设计 源程序如下: #include #include using namespace std; int main() { int n,a[100],b[100]; double s[100],m[100],T=0,W=0; cout<<"请输入作业数:"<>n; cout<<"请分别输入各作业到达系统的时间:"<>b[i]; } cout<<"请分别输入各作业所运行的时间:"<>a[i];s[0]=0; s[i+1]=s[i]+a[i]; m[i+1]=(s[i+1]-b[i])/a[i]; T=T+s[i+1]-b[i]; W=W+m[i+1]; }

第三版操作系统第3章习题

操作系统第三章总复习题 一、单选题 1、进程调度又称低级调度,其主要功能是( D )。 A.选择一个作业调入内存B.选择一个主存中的进程调出到外存 C.选择一个外存中的进程调入到主存D.将一个就绪的进程投入到运行 2、若进程P 一旦被唤醒就能够投入运行,系统可能为( D )。 A.分时系统,进程P 的优先级最高 B.抢占调度方式,就绪队列上的所有进程的优先级皆比P 的低 C.就绪队列为空队列 D.抢占调度方式,P 的优先级高于当期运行的进程。 3、一个进程P 被唤醒后,( D )。 A.P 就占有了CPU。B.P 的PCB 被移到就绪队列的队首。 C.P 的优先级肯定最高D.P 的状态变成就绪 4、若当前运行进程()后,系统将会执行进程调度原语。 A 执行了一个转移指令 B 要求增加主存空间,经系统调用银行家算法进行测算认为是安全的。 C 执行了一条I/O 指令要求输入数据。 D 执行程序期间发生了I/O 完成中断。 5、当系统中()时,系统将不会执行进程调度原语。 A.一个新进程被创建B.当前进程执行了P 操作。C.在非抢占调度中,进程A 正在运行而进程B 恰好被唤醒。D.分时系统中时间片用完。 6、在分时系统中,若当期运行的进程连续获得了两个时间片,原因可能是()。 A 该进程的优先级最高 B 就绪队列为空 C 该进程最早进入就绪队列 D 该进程是一个短进程 7、实时系统中采用的调度算法可以有如下几种: 1、非抢占优先权调度算法 2、立即抢占优先权调度算法 3、时间片轮转调度算法 4、基于时钟中断抢占的优先权调度算法 按实时要求的严格程度由低到高的顺序()。 A 1-3-2-4 B 3-1-4-2 C 3-1-2-4 D 1-3-4-2 8、三种主要类型的OS 中都必须配置的调度()。 A 作业调度 B 中级调度 C 低级调度 D I/O 调度 9、设系统中n 个进程并发,共同竞争资源X,且每个进程都需要m 个X 资源,为使该系统不会发生死锁,资源X 最少要有( C )个。 A m*n+1 B n*m+n C n*m+1-n D 无法预计 10、死锁的预防方法中,不太可能的一种方法使()。

操作系统实验报告(进程调度算法)

操作系统实验报告(进程调度算法)

实验1 进程调度算法 一、实验内容 按优先数调度算法实现处理器调度。 二、实验目的 在采用多道程序设计的系统中,往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时,就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的处理器调度,帮助学生加深了解处理器调度的工作。 三、实验原理 设计一个按优先数调度算法实现处理器调度的程序。 (1) 假定系统有五个进程,每一个进程用一个进程控制块PCB来代表,进程控制块的格式为: 进程名 指针 要求运行时 间 优先数

状态 其中,进程名——作为进程的标识,假设五个进程的进程名分别为P1,P2,P3,P4,P5。 指针——按优先数的大小把五个进程连成队列,用指针指出下一个进程的进程控制块的首地址,最后一个进程中的指针为“0”。 要求运行时间——假设进程需要运行的单位时间数。 优先数——赋予进程的优先数,调度时总是选取优先数大的进程先执行。 状态——可假设有两种状态,“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”,用“R”表示,当一个进程运行结束后,它的状态为“结束”,用“E”表示。 (2) 在每次运行你所设计的处理器调度程序之前,为每个进程任意确定它的“优先数”和“要求运行时间”。 (3) 为了调度方便,把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程,用指针指出队列的连接情况。例: 队首标志 K2

1P1 K 2 P2 K 3 P3 K 4 P4 K 5 P5 0 K4K5K3K1 2 3 1 2 4 1 5 3 4 2 R R R R R PC B1 PC B2 PC B3 PC B4 PC B5 (4) 处理器调度总是选队首进程运行。采用动态改变优先数的办法,进程每运行一次优先数就减“1”。由于本实验是模拟处理器调度,所以,对被选中的进程并不实际的启动运行,而是执行: 优先数-1 要求运行时间-1 来模拟进程的一次运行。 提醒注意的是:在实际的系统中,当一个进程被选中运行时,必须恢复进程的现场,让它占有处理器运行,直到出现等待事件或运行结束。在这里省去了这些工作。

操作系统作业二

1 填空题 1 若采用短作业优先调度策略,作业单道串行运行时的调度次序为J1,J3,J2 ,平均周转时间= 8 。 2.进程间通信的类型有:基于内存通信、基于文件通信、基于网络通信和基于报文传递通信。 3.在响应比最高者优先的作业调度算法中,当各个作业等待时间相同时,运行时间短作业将得到优先调度;当各个作业要求运行的时间相同时,等待时间长得到优先调度。 4.有三个同时到达的作业J1,J2和J3,它们的执行时间分别是T1,T2和T3,且T1

计算机操作系统课后习题答案第三章(第四版)

第三章处理机调度与死锁 1,高级调度与低级调度的主要任务是什么?为什么要引入中级调度? 【解】(1)高级调度主要任务是用于决定把外存上处于后备队列中的那些作业调入内存,并为它们创建进程,分配必要的资源,然后再将新创建的进程排在就绪队列上,准备执行。(2)低级调度主要任务是决定就绪队列中的哪个进程将获得处理机,然后由分派程序执行把处理机分配给该进程的操作。(3)引入中级调度的主要目的是为了提高内存的利用率和系统吞吐量。为此,应使那些暂时不能运行的进程不再占用宝贵的内存空间,而将它们调至外存上去等待,称此时的进程状态为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件,且内存又稍有空闲时,由中级调度决定,将外存上的那些重又具备运行条件的就绪进程重新调入内存,并修改其状态为就绪状态,挂在就绪队列上,等待进程调度。 3、何谓作业、作业步和作业流? 【解】作业包含通常的程序和数据,还配有作业说明书。系统根据该说明书对程序的运行进行控制。批处理系统中是以作业为基本单位从外存调入内存。作业步是指每个作业运行期间都必须经过若干个相对独立相互关联的顺序加工的步骤。 作业流是指若干个作业进入系统后依次存放在外存上形成的输入作业流;在操作系统的控制下,逐个作业进程处理,于是形成了处理作业流。 4、在什么情冴下需要使用作业控制块JCB?其中包含了哪些内容? 【解】每当作业进入系统时,系统便为每个作业建立一个作业控制块JCB,根据作业类型将它插入到相应的后备队列中。 JCB 包含的内容通常有:1) 作业标识2)用户名称3)用户账户4)作业类型(CPU 繁忙型、I/O芳名型、批量型、终端型)5)作业状态6)调度信息(优先级、作业已运行)7)资源要求8)进入系统时间9) 开始处理时间10) 作业完成时间11) 作业退出时间12) 资源使用情况等 5.在作业调度中应如何确定接纳多少个作业和接纳哪些作业? 【解】作业调度每次接纳进入内存的作业数,取决于多道程序度。应将哪些作业从外存调入内存,取决于采用的调度算法。最简单的是先来服务调度算法,较常用的是短作业优先调度算法和基于作业优先级的调度算法。 7.试说明低级调度的主要功能。 【解】(1)保存处理机的现场信息(2)按某种算法选取进程(3)把处理机分配给进程。 8、在抢占调度方式中,抢占的原则是什么? 【解】剥夺原则有:(1)时间片原则各进程按时间片运行,当一个时间片用完后,便停止该进程的执行而重新进行调度。这种原则适用于分时系统、大多数实时系统,以及要求较高的批处理系统。(2)优先权原则通常是对一些重要的和紧急的作业赋予较高的优先权。当这种作业到达时,如果其优先权比正在执行进程的优先权高,便停止正在执行的进程,将处理机分配给优先权高的进程,使之执行。(3)短作业(进程)优先原则当新到达的作业(进程)比正在执行的作业(进程)明显地短时,将剥夺长作业(进程)的执行,将处理机分配给短作业(进程),使之优先执行。 9、选择调度方式和调度算法时,应遵循的准则是什么? 【解】应遵循的准则有(1)面向用户的准则:周转时间短,响应时间快,截止时间的保证,优先权准则。(2)面向系统的准则:系统吞吐量高,处理机利用率好,各类资源的平衡利用。 10、在批处理系统、分时系统和实时系统中,各采用哪几种进程(作业)调度算法? 【解】 批处理系统:FCFS算法、最小优先数优先算法、抢占式最小优先数优先算法 2 分时系统:可剥夺调度、轮转调度 实时系统:时间片轮转调度算法、非抢占优先权调度算法、基于时钟中断抢占的优先权调度算法、立即抢占的优先权调度。 11、何谓静态和动态优先权?确定静态优先权的依据是什么? 【解】静态优先权是在创建进程时确定的,且在进程的整个运行期间保持不变。动态优先权是指,在创建进程时所赋予的优先权,是可以随进程的推进或随其等待时间的增加而改变的,以便获得更好的调度性能。确定静态优先权的依据是:(1)进程类型,通常系统进程的优先权高于一般用户进程的优先权。(2)进程对资源的需要。(3)用户要求,用户进程的紧迫程度及用户所付费用的多少来确定优先权的。 12、试比较FCFS和SPF两种进程调度算法。 【解】FCFS算法按照作业提交或进程变为就绪状态的先后次序,分派CPU。当前作业或进程占有CPU,直到执行完或阻塞,才让出CPU。在作业或进程唤醒后,并不立即恢复执行,通常等到当前作业或进程让出CPU。FCFS比较有利于长作业,而不利于短作业;有利于CPU繁忙的作业,而不利于I/O繁忙的作业。SPF有利于短进程调度,是从就绪队列中选出一估计运行时间最短的进

操作系统+磁盘调度算法

目录 目录 ........................................................ 错误!未定义书签。1.课程设计目的.............................................. 错误!未定义书签。 编写目的................................................. 错误!未定义书签。2.课程设计内容.............................................. 错误!未定义书签。 设计内容................................................. 错误!未定义书签。3.课程设计方案.............................................. 错误!未定义书签。 模块划分................................................. 错误!未定义书签。 模块调用关系图........................................... 错误!未定义书签。 子模块程序流程图......................................... 错误!未定义书签。4.测试数据和结果............................................ 错误!未定义书签。 测试数据................................................. 错误!未定义书签。 测试结果................................................. 错误!未定义书签。 测试抓图................................................. 错误!未定义书签。5.参考文献.................................................. 错误!未定义书签。6.总结...................................................... 错误!未定义书签。 设计体会................................................. 错误!未定义书签。 结束语................................................... 错误!未定义书签。7.程序使用说明书............................................ 错误!未定义书签。8.程序源代码................................................ 错误!未定义书签。

操作系统短作业优先调度算法

课程设计 采用短作业优先调度算法调度程序 学号: 姓名: 专业: 指导老师: 日期:

目录 一、实验题目 (3) 二、课程设计的目的 (3) 三、设计内容 (3) 四、设计要求 (3) 五、主要数据结构及其说明 (4) 六、程序运行结果 (5) 七、流程图 (7) 八、源程序文件 (9) 九、实验体会 (13) 十、参考文献 (13)

摘要 在多道程序环境下,主存中有着多个进程,其数目往往多于处理机数目。这就要求系统能按某种算法,动态地把处理机分配给就绪队列中的一个进程,使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源,提高处理机的利用率及改善系统性能(吞吐量、响应时间),在很大程度上取决于处理机调度性能的好坏,因而,处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中,一个作业被提交后必须经过处理机调度后,方能获得处理机执行。对于批量型作业而言,通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业,根据作业控制块的信息,按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的,短作业优先(SJF)便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。

一、实验题目 采用短作业优先算法的的进程调度程序 二、课程设计的目的 操作系统课程设计是计算机专业重要的教学环节,它为学生提供了一个既动手又动脑,将课本上的理论知识和实际有机的结合一起,独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三、设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 四、设计要求 1. 每一个进程有一个PCB,其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据(要求存放在外部文件中)进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态:就绪、执行(由于不要求设置互斥资源与进程间同步关系,故只有两种状态) 5. 采用可视化界面,可在进程调度过程中随时暂停调度,查看当前进程的状态以及相应的阻塞队列

几种操作系统调度算法

保证调度算法 基本思想:向用户做出明确的性能保证,然后去实现它.如你工作时有n个用户的登录,则你将获得cpu处理能力的1/n 算法实现:跟踪计算各个进程已经使用的cpu时间和应该获得的cpu时间,调度将转向两者之比最低的进程 五,保证调度算法 思想:向用户做出明确的性能保证,然后去实现它. 算法:容易实现的一种保证是:当工作时己有n个用户登录在系统,则将获得CPU处理能力的1/n.类似的,如果在一个有n个进程运行的用户系统中,每个进程将获得CPU处理能力的1/n. 实现方法:OS应记录及计算,各个进程在一定时间段内,已经使用的CPU时间和应该得到的CPU时间,二者之比小者优先级高. 5. 保证调度 一种完全不同的调度算法是向用户作出明确的性能保证,然后去实现它。一种很实际并很容易实现的保证是:若用户工作时有n个用户登录,则用户将获得CPU处理能力的1/n。类似地,在一个有n个进程运行的单用户系统中,若所有的进程都等价,则每个进程将获得1/n的CPU时间。看上去足够公平了。 为了实现所做的保证,系统必须跟踪各个进程自创建以来已使用了多少CPU时间。然后它计算各个进程应获得的CPU时间,即自创建以来的时间除以n。由于各个进程实际获得的CPU时间是已知的,所以很容易计算出真正获得的CPU时间和应获得的CPU时间之比。比率为0.5说明一个进程只获得了应得时间的一半,而比率为2.0则说明它获得了应得时间的2倍。于是该算法随后转向比率最低的进程,直到该进程的比率超过它的最接近竞争者为止。 彩票调度算法 基本思想:为进程发放针对系统各种资源(如cpu时间)的彩票;当调度程序需要做出决策时,随机选择一张彩票,持有该彩票的进程将获得系统资源 合作进程之间的彩票交换 六,彩票调度算法 彩票调度算法: 为进程发放针对各种资源(如CPU时间)的彩票.调度程序随机选择一张彩票,持有该彩票的进程获得系统资源. 彩票调度算法的特点: 平等且体现优先级:进程都是平等的,有相同的运行机会.如果某些进程需要更多的机会,可被给予更多彩票,增加其中奖机会. 易计算CPU的占有几率:某进程占用CPU的几率,与所持有的彩票数成正比例.该算法可实现各进程占用CPU的几率. 响应迅速 各个进程可以合作,相互交换彩票. 容易实现按比例分配如图象传输率,10帧/s,15帧/s,25帧/s

操作系统第2阶段练习题

江南大学现代远程教育第二阶段练习题 考试科目:《操作系统》第5章至第7章(总分100分) ______________学习中心(教学点)批次:层次: 专业:学号:身份证号: 姓名:得分: 一、名词解释(12分) 1、死锁 2、逻辑地址 3、物理地址 4、地址重定位 二、试举例说明死锁?(6分) 三、采用静态资源分配预防死锁时,有哪些缺点?(6分) 四、有序资源分配法破坏的是产生死锁必要条件中的什么条件?(5分) 五、作业调度和进程调度的任务各是什么?(6分) 六、进程调度的时机有哪几种?(5分) 七、为什么要进行逻辑地址到物理地址的转换?(6分) 八、某系统的进程状态变迁图如图所示(该系统的进程调度方式为非剥夺方式),请说明: (20分) (1)一个进程发生变迁3的原因是什么?发生变迁2、变迁4的原因又是什么? (2)下述因果变迁是否会发生,如果有可能的话,在什么情况下发生? (3)(a)2→1;(b)3→2;(c)4→5;(d)4→2;(e)3→5 (4)根据此状态变迁图叙述该系统的调度策略、调度效果。 九、在单道批处理系统中,有下列三个作业用先来先服务调度算法和最短作业优先调度算法 进行调度,哪一种算法调度性能好些?请完成下表中未填写的各项。(8分)

十、 分区分配方法中的主要缺点是什么?如何克服这一缺点?(6分) 十一、 如图,主存中有两个空白区,现有这样一个作业序列: 作业1 要求50KB 作业2 要求60KB 作业3 要求70KB 若用首次适应算法和最佳适应算法来处理这个作业序列,试问哪一种算法可以分配得下,为什么?(10分) 十二、 选择填空题(10分) 1、死锁的四个必要条件是__________、不剥夺条件、__________和环路条件。 2、在分区存储管理中,最佳适应算法要求对空闲区表项按( )进行排列。 A.地址从大到小 B.地址从小到大 C.尺寸从大到小 D.尺寸从小到大 3、进程调度又称为( ) A 、线程 B 、宏观 C 、微观 D 、作业 4、段式存储管理中的地址格式是( )地址。 A .线性 B .一维 C .二维 D .三维 参考答案 一、 名词解释 015KB 25KB

操作系统之调度算法和死锁中的银行家算法

操作系统之调度算法和死锁中的银行家算法习题答案

1. 有三个批处理作业,第一个作业 10:00 到达,需要执行 2 小时;第二个作业在 10:10 到达,需要执行 1 小时;第三个作业在 10:25 到达,需要执行 25 分钟。分别采用先来先服务,短作业优先和最高响应比优先三种调度算法,各自的平均周转时间是多少? 解: 先来先服务: (结束时间=上一个作业的结束时间+执行时间周转时间=结束时间-到达时间=等待时间+执行时间) 按到达先后,执行顺序:1->2->3 作业到达 时间 结束 时间 等待 时间 执行 时间 周转 时间 平均周 转时间 1 10:00 12:00 0m 120m 120m 156.7m 2 10:10 13:00 110m 60m 170m 3 10:25 13:25 155m 25m 180m 短作业优先: 1)初始只有作业1,所以先执行作业1,结束时 间是12:00,此时有作业2和3; 2)作业3需要时间短,所以先执行;

3)最后执行作业2 作业到达 时间 结束 时间 等待 时间 执行 时间 周转 时间 平均周 转时间 1 10:00 12:00 0m 120m 120m 145m 3 10:25 12:25 95m 25m 120m 2 10:10 13:25 135m 60m 195m 最高响应比优先: 高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间,综合了先来先服务和最短作业优先两种算法的特点。 1)10:00只有作业1到达,所以先执行作业1; 2)12:00时有作业2和3, 作业2:等待时间=12:00-10:10=110m;响应比=1+110/60=2.8; 作业3:等待时间=12:00-10:25=95m,响应比=1+95/25=4.8; 所以先执行作业3 3)执行作业2 作业到达 时间 结束 时间 等待 时间 执行 时间 周转 时间 平均周 转时间 1 10:00 12:00 0m 120m 120m

操作系统原理第四章 处理机调度习题

第四章处理机调度 4.3 习题 4.3.1 选择最合适的答案 1.某系统采用了银行家算法,则下列叙述正确的是()。 A.系统处于不安全状态时一定会发生死锁 B.系统处于不安全状态时可能会发生死锁 C.系统处于安全状态时可能会发生死锁 D.系统处于安全状态时一定会发生死锁 2.银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need,下列选项正确的是()。 A.Max[i,j]=Allocation[i,j]+Need[i,j] B.Need[i,j]= Allocation[i,j]+ Max[i,j] C.Max[i,j]= Available[i,j]+Need[i,j] D.Need[i,j]= Available[i,j]+ Max[i,j] 3.下列进程调度算法中,()可能会出现进程长期得不到调度的情况。 A.非抢占式静态优先权法 B.抢占式静态优先权法 C.时间片轮转调度算法 D.非抢占式动态优先权法 4.在下列选项中,属于预防死锁的方法是()。 A.剥夺资源法 B.资源分配图简化法 C.资源随意分配 D.银行家算法 5.在下列选项中,属于检测死锁的方法是()。 A.银行家算法 B.消进程法 C.资源静态分配法 D.资源分配图简化法 6.在下列选项中,属于解除死锁的方法是()。 A.剥夺资源法 B.资源分配图简化法 C.银行家算法 D.资源静态分配法 7.为了照顾紧迫型作业,应采用()。 A.先来服务调度算法 B.短作业优先调度算法 C.时间片轮转调度算法 D.优先权调度算法 8.在采用动态优先权的优先权调度算法中,如果所有进程都具有相同优先权初值,则

操作系统磁盘调度算法

操作系统课程设计任务书 题目: 磁盘调度算法 院系: 专业: 班级: 姓名: 学号: 指导教师: 设计时间:2018.1.1-2018.1.5 指导教师评语

目录 1、需求分析?4 1.1课题描述 (4) 1.2课题目的 (4) 1.3理论依据?7 2、概要设计?8 2.1设计方法 ............................................................................................... 82.2技术?8 2.3运行环境?8 3、详细设计?9 3.1流程图 (11) 3.2程序主要代码? 13 14 4、运行结果及分析? 4.1运行结果? 15 4.2结果详细分析?6 1 16 5、总结和心得? 7 1 6、参考文献? 2 7、附录:程序源代码? 3

1、需求分析 1.1课题描述 这次课程设计我研究的题目是:磁盘调度算法。具体包括三种算法分别是:先来先服务算法(FCFS)、最短寻道时间优先算法(SSTF)、扫描算法(电梯调度算法)(SCAN)。 1.2课题目的 通过这次实验,加深对磁盘调度算法的理解,进一步掌握先来先服务FCFS,最短寻道时间优先SSTF,扫描SCAN算法的实现方法。 1.3理论依据 设备的动态分配算法与进程调度相似,也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中,低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中,对磁盘的访问要求来自多方面,常常需要排队。这时,对众多的访问要求按一定的次序响应,会直接影响磁盘的工作效率,进而影响系统的性能。访问磁盘的时间因子由3部分构成,它们是查找(查找磁道)时间、等待(旋转等待扇区)时间和数据传输时间,其中查找时间是决定因素。因此,磁盘调度算法先考虑优化查找策略,需要时再优化旋转等待策略。 平均寻道长度(L)为所有磁道所需移动距离之和除以总的所需访问的磁道数(N),即:L=(M1+M2+……+Mi+……+MN)/N

操作系统作业调度算法

操作系统上机测试作业调度算法算法 一、实验目的和要求(供参考) 1.掌握作业调度功能和调度程序常用算法。 2.掌握利用C语言设计实现不同调度策略的作业调度算法。 3.验证不同作业调度算法对性能的影响。 二、实验环境(供参考) 1.知识准备:学过进程管理、作业管理、处理机调度等章节的内容。 2.开发环境与工具: 硬件平台——个人计算机。 软件平台——C语言开发环境。 三、实验内容 用“先来先服务(FCFS)”算法和“最短作业优先(SJF)”算法模拟作业调度。 要求:按作业的到达顺序输入各作业需要的运行时间,按算法调度输出平均周转时间。 例如(FCFS),输入:8(到达时间0),5(到达时间2),7(到达时间3),1(到达时间6)J1 J2 J3 J4 0 8 13 20 21 输出:aver=(8+(13-2)+(20-3)+(21-6))/4=51/4 例如(SJF),输入:8(到达时间0),5(到达时间2),7(到达时间3),1(到达时间6)J1 J4 J2 J3 0 8 9 14 21 输出:aver=(8+(9-6)+(14-2)+(21-3))/4=42/4 注:输入的格式任意,只要输出平均周转时间即可。

四、代码(带注释) 1、先来先服务 实验结果(截图呈现) 代码: #include using namespace std; class Fcfs { private: int num[10]; //作业编号 double arriveTime[10]; //到达时间 double startTime[10]; //开始时间,进内存时间 double workTime[10]; //工作时间 double finishTime[10]; //完成时间 double cirTime[10]; //存放每一个作业的周转时间 //double freeTime[10]; //上一个作业已结束,但下一个作业还未到,存放这一段空闲时间 public: Fcfs(int n) //n为作业数目 { cout<<"默认第一个作业的到达时间为0。"<

操作系统实验 第五讲 磁盘调度算法

操作系统 实验报告 哈尔滨工程大学 计算机科学与技术学院

第六讲磁盘调度算法 一、实验概述 1. 实验名称 磁盘调度算法 2. 实验目的 (1)通过学习EOS 实现磁盘调度算法的机制,掌握磁盘调度算法执行的条件和时机; (2)观察EOS 实现的FCFS、SSTF和SCAN磁盘调度算法,了解常用的磁盘调度算法; (3)编写CSCAN和N-Step-SCAN磁盘调度算法,加深对各种扫描算法的理解。 3. 实验类型 验证性+设计性实验 4. 实验内容 (1)验证先来先服务(FCFS)磁盘调度算法; (2)验证最短寻道时间优先(SSTF)磁盘调度算法; (3)验证SSTF算法造成的线程“饥饿”现象; (4)验证扫描(SCAN)磁盘调度算法; (5)改写SCAN算法。 二、实验环境 在OS Lab实验环境的基础上,利用EOS操作系统,由汇编语言及C语言编写代码,对需要的项目进行生成、调试、查看和修改,并通过EOS应用程序使内核从源代码变为可以在虚拟机上使用。 三、实验过程 1. 设计思路和流程图 (1)改写SCAN算法 在已有SCAN 算法源代码的基础上进行改写,要求不再使用双重循环,而是只遍历一次请求队列中的请求,就可以选中下一个要处理的请求。算法流程图如下图所示。

图 3.1.1 SCAN算法IopDiskSchedule函数流程图 (2)编写循环扫描(CSCAN)磁盘调度算法 在已经完成的SCAN算法源代码的基础上进行改写,不再使用全局变量ScanInside确定磁头移动的方向,而是规定磁头只能从外向内移动。当磁头移动到最内的被访问磁道时,磁头立即移动到最外的被访问磁道,即将最大磁道号紧接着最小磁道号构成循环,进行扫描。算法流程图如下图所示。 图 3.1.2 CSCAN算法IopDiskSchedule函数流程图 (3)编写N-Step-SCAN磁盘调度算法 在已经完成的SCAN 算法源代码的基础上进行改写,将请求队列分成若干个长度为N 的子队列,调度程序按照FCFS原则依次处理这些子队列,而每处理一个子队列时,又是按照SCAN算法。算法流程图如下图所示。

操作系统磁盘调度算法(C++)

#include #include #include using namespace std; const int MaxNumber=100; int TrackOrder[MaxNumber]; int MoveDistance[MaxNumber]; //----移动距离; int FindOrder[MaxNumber]; //-----寻好序列。 double AverageDistance; //-----平均寻道长度 bool direction; //-----方向true时为向外,false为向里 int BeginNum; //----开始磁道号。 int M; //----磁道数。 int N; //-----提出磁盘I/O申请的进程数 int SortOrder[MaxNumber]; //----排序后的序列 bool Finished[MaxNumber]; void Inith() { cout<<"请输入磁道数:"; cin>>M;

cout<<"请输入提出磁盘I/O申请的进程数:"; cin>>N; cout<<"请依次输入要访问的磁道号:"; for(int i=0;i>TrackOrder[i]; for(int j=0;j>BeginNum; for(int k=0;k=0;i--) for(int j=0;j

操作系统:调度算法

操作系统:调度算法 例题:四个作业进入系统,分别用FCFS、SJF、HRRF算法求:平均周转时间,带权平均周转时间。 作业到达时间运行时间 A 8:00 120 B 8:50 50 C 9:00 10 D 9:50 20 周转时间:从作业提交算起,直到执行完毕这段时间 带权周转时间:作业的周转时间与系统为其提供服务的服务时间之比1、先来先服务算法:(FCFS) 作业到达时间运行时间开始时间结束时间周转时间 A 8:00 120 8:00 10:00 120 B 8:50 50 10:00 10:50 120 C 9:00 10 10:50 11:00 120 D 9:50 20 11:00 11:20 90 平均周转时间=(120+120+120+90)/4=112.5 带权平均周转时间=(120/120+120/50+120/10+90/20)/4=4.975 2、最短作业优先调度算法:(SJF) 作业到达时间运行时间开始时间结束时间周转时间 A 8:00 120 8:00 10:00 120 B 8:50 50 10:30 11:20 150 C 9:00 10 10:00 10:10 70 D 9:50 20 10:10 10:30 40 平均周转时间=(120+150+70+40)/4=95 带权平均周转时间=(120/120+150/50+70/10+40/20)/4=3.25 3、最高相应比优先算法(HRRF)

作业到达时间运行时间开始时间结束时间周转时间 A 8:00 120 8:00 10:00 120 B 8:50 50 10:10 11:00 130 C 9:00 10 10:00 10:10 70 D 9:50 20 11:00 11:20 70 平均周转时间=(120+130+70+70)/4=97.5 带权平均周转时间=(120/120+130/50+70/10+70/20)/4=3.525 习题: 设有四道作业,他们到达的时间和运行时间如图: 作业到达时间运行时间 A 8:00 80 B 8:30 35 C 9:00 20 D 9:20 25 假设一次调一个作业运行,使用最短作业优先调度算法,求其平均周转时间和平均带权周转时间(以分钟为单位) 作业到达时间运行时间开始时间结束时间周转时间 A 8:00 80 8:00 9:20 80 B 8:30 35 10:05 10:40 130 C 9:00 20 9:20 9:40 40 D 9:20 25 9:40 10:05 45 平均周转时间=(80+130+40+45)/4=73.75 带权平均周转时间=(80/80+130/35+40/20+45/25)/4=2.129 许可 2015.6.7

操作系统实验-FCFS和短作业优先SJF调度算法模拟

题目先来先服务FCFS和短作业优先SJF进程调度算法 姓名: 学号: 专业: 学院: 指导教师:林若宁 二零一八年十一月

一、实验目的 模拟单处理器系统的进程调度,分别采用短作业优先和先来先服务的进程调度算法作为进程设计算法,以加深对进程的概念及进程调度算法的理解. 二、实验内容 1. 短作业优先调度算法原理 短作业优先调度算法,是指对短作业或断进程优先调度的算法。它们可以分别可以用于作业调度和进程调度。短作业优先调度算法,是从后备队列中选择一个或若干个运行时间最短的作业,将它们调入内存运行。短进程优先调度算法,是从就绪队列中选出一个估计运行时间最短的进程,将处理机分配给它使它立即执行并一直执行到完成,或发生某事件而被阻塞放弃处理机时再重新调度。 2. 先来先服务调度算法原理 先来先服务(FCFS)调度算法是一种最简单的调度算法,该算法既可用于作业调度,也可用于进程调度。当在作业调度中采用该算法时,每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业,将它们调入内存,为它们分配资源、创建进程,然后放入就绪队列。在进程调度中采用FCFS算法时,则每次调度是从就绪队列中选择一个最先进入该队列的进程,为之分配处理机,使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。 三、程序设计 1.概要设计 程序包括主函数、FCFS算法函数、SJF算法函数、输出函数;主函数流程:输入文件中的数据—显示各进程数据—选择算法—调用相应算法的函数—输出结果 2.算法流程

SJF算法流程图:

3.详细设计 (1)定义一个结构体 typedef struct PCB { char job_id[10]; //作业ID float Arr_time; //到达时刻 float Fun_time; //估计运行时间 float Wait_time; //等待时间 float Start_time; //开始时刻 float Fin_time; //完成时刻 float Tur_time; //周转时间 float WTur_time; //带权周转时间 int Order; //优先标记 }list; (2)先来先服务算法函数 void fcfs(list *p,int count) //先来先服务算法 { list temp; //临时结构体变量int i; int j;

操作系统之调度算法和死锁中的银行家算法习题答案

1. 有三个批处理作业,第一个作业 10:00 到达,需要执行 2 小时;第二个作业在 10:10 到 达,需要执行 1 小时;第三个作业在 10:25 到达,需要执行 25 分钟。分别采用先来先服务,短作业优先和最高响应比优先三种调度算法,各自的平均周转时间是多少? 解: 先来先服务: (结束时间=上一个作业的结束时间+执行时间 周转时间=结束时间-到达时间=等待时间+执行时间) 按到达先后,执行顺序:1->2->3 短作业优先: 1)初始只有作业1,所以先执行作业1,结束时间是12:00,此时有作业2和3; 2)作业3需要时间短,所以先执行; 最高响应比优先: 高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间,综合了先来先服务和最短作业优先两种算法的特点。 1)10:00只有作业1到达,所以先执行作业1; 2)12:00时有作业2和3, 作业2:等待时间=12:00-10:10=110m;响应比=1+110/60=2.8; 作业3:等待时间=12:00-10:25=95m,响应比=1+95/25=4.8; 所以先执行作业3 3)执行作业2 2. 在一单道批处理系统中,一组作业的提交时刻和运行时间如下表所示。试计算一下三种作业调度算法的平均周转时间 T 和平均带权周转时间 W。 ( 1)先来先服务;( 2)短作业优先( 3)高响应比优先

解: 先来先服务: 短作业优先: 作业顺序: 1)8:00只有作业1,所以执行作业1; 2)9:00有作业2和3,作业3短,所以先执行3; 3)9:12有作业2和4,作业4短,所以先执行4; 高响应比优先: 作业顺序: 1)8:00只有作业1,所以执行作业1; 2)9:00有作业2和3 作业2等待时间=9:00-8:30=30m,响应比=1+30/30=2; 作业3等待时间=9:00-9:00=0m,响应比=1+0/12=1; 所以执行作业2; 3)9:30有作业3和4 作业3等待时间=9:30-9:00=30m,响应比=1+30/12=3.5; 作业4等待时间=9:30-9:06=24m,响应比=1+24/6=5;

相关主题