处理机调度算法的实现
处理机调度算法的实现
1．设定系统中有五个进程，每一个进程用一个进程控制块表示。
2．输入每个进程的“优先数”和“要求运行时间”，
3．为了调度方便，将五个进程按给定的优先数从大到小连成就绪队列。用一单元指出队列首进程，用指针指出队列的连接情况。
4．处理机调度总是选队首进程运行。采用动态优先数算法，进程每运行一次优先数就减“1”，同时将运行时间减“1”。
5．若要求运行时间为零，则将其状态置为“结束”,且退出队列。
6．运行所设计程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。
#include
#include
struct PCB {
char name[10];
int priority,time;
struct PCB *next;
}*k;
struct LinkQueue {
PCB * front;
PCB * rear;
};
//队列初始化
LinkQueue init(){
LinkQueue Q;
PCB * p;
p=(PCB *)malloc(sizeof(PCB));
if(p) {
Q.front=Q.rear=p;
Q.front->next=NULL;
return Q;
}else{
printf("队列初始化失败，程序运行终止! \n");
exit(0);
}
}
//插入新进程，使优先数从大到小排列
LinkQueue sort(LinkQueue Q,PCB *p) {
PCB * temp1;
PCB * temp2;
if(Q.rear==Q.front) {
Q.front->next=p;
Q.rear=p;
} else {
temp1=Q.front;
temp2=temp1->next;
while(temp2->priority>=p->priority && temp2->next!=NULL) {
temp1=temp2;
temp2=temp1->next;
}
if(temp2->next==NULL && temp2->priority>=p->priority) {
temp2->next=p;
Q.rear=p;
} else {
p->next=temp1->next;
temp1->next=p;
}
}
return Q;
}
LinkQueue input(LinkQueue Q) /* 建立进程控制块函数*/
{
int i;
for(i=1;i<=5;i++)
{
printf("\n 进程号No.%d:\n",i);
k=(PCB *)malloc(sizeof(PCB));
printf("\n 输入进程名:");
scanf("%s",k->name);
printf("\n 输入进程优先数:");
scanf("%d",&k->priority);
printf("\n 输入进程运行时间:");
scanf("%d",&k->time);
printf("\n");
k->next=NULL;
Q=sort(Q,k); /* 调用sort函数*/
}
return Q;
}
LinkQueue running(LinkQueue Q) /* 建立进程就绪函数(进程运行时间到,置就绪状态*/ {
if(k->time==0) {
printf("运行后进程[%s] 已完成状态为\"结束\".\n",k->name);
free(k);
}else
{
(k->priority)--;
(k->time)--;
printf("运行后优先数:%d 需要运行时间:%d\n",k->priority,k->time);
Q=sort(Q,k); /*调用sort函数*/
}
return Q;
}
void check(LinkQueue Q) /* 建立进程查看函数*/
{ PCB *pr;
pr=(PCB *)malloc(sizeof(PCB));
pr=Q.front->next;
printf("\n **** 输入的五个过程为:\n");
while(pr!=NULL) {
printf("\n 进程名:%s 状态:就绪优先数:%d 需要运行时
间:%d\n",pr->name,pr->priority,pr->time);
pr=pr->next;
}
}
void main()
{
int h=0;
LinkQueue P;
P=init();
P=input(P);
check(P);
while((P.front->next)!=NULL) {
h++;
k=P.front->next;
P.front->next=k->next;
k->next=NULL;
printf("\n 第%d次运行,被选中进程是:%s ",h,k->name);
P=running(P);
}
printf("\n\n 进程已经完成.\n");
}
一、先来先服务算法 1．程序简介 先来先服务算法按照作业进入系统后备作业队列的先后次序挑选作业,先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后,移入就绪队列.这是一种非剥夺式调度算法,易于实现,但效率不高.只顾及作业的等候时间,未考虑作业要求服务时间的长短,不利于短作业而优待长作业,不利于I/O繁忙型作业而有利于CPU繁忙型作业.有时为了等待场作业执行结束,短作业的周转时间和带全周转时间将变得很大,从而若干作业的平均周转时间和平均带权周转时间也变得很大。 2．分析 1．先定义一个数组代表各作业运行的时间，再定义一个数组代表各作业到达系统的时间，注意到达系统的时间以第一个作业为0基础（注意：若各程序都同时到达系统，则到达系统时间都为0）。 2．输入作业数。 3．然后运用循环结构累积作业周转时间和带权周转时间。 4．最后，作业周转时间和带权周转时间分别除以作业数即可得到平均作业周转时间和平均带权周转时间。 3．详细设计 源程序如下： #include
课程设计报告 设计名称：模拟实现一种处理机调度算法 学生姓名： xxx 专业：计算机科学与技术 班别： xxxxxxxx 学号： xxxxxx 指导老师： xxxxx 日期： 2014 年 6 月 20 日
初始条件： 1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。 2．实践准备：掌握一种计算机高级语言的使用。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求） 1．模拟进程调度，能够处理以下的情形： ⑴能够选择不同的调度算法（要求中给出的调度算法）； ⑵能够输入进程的基本信息，如进程名、优先级、到达 时间和运行时间等； ⑶根据选择的调度算法显示进程调度队列； ⑷根据选择的调度算法计算平均周转时间和平均带权周 转时间。 2．设计报告内容应说明： ⑴需求分析； ⑵功能设计（数据结构及模块说明）； ⑶开发平台及源程序的主要部分； ⑷测试用例，运行结果与运行情况分析； ⑸自我评价与总结： i）你认为你完成的设计哪些地方做得比较好或比较出 色； ii）什么地方做得不太好，以后如何改正；
iii）从本设计得到的收获（在编写，调试，执行过程中 的经验和教训）； iv）完成本题是否有其他方法（如果有，简要说明该方 法）； 进程调度模拟设计——先来先服务、优先级法1、背景： 当计算机系统是多道程序设计系统时，通常会有多个进程或线程同时竞争CPU。只要有两个或更多的进程处于就绪状态，这种情形就会发生。如果只有一个CPU可用，那么就必须选择下一个要运行的进程。在操作系统中，完成选择工作的这一部分称为调度程序，该程序使用的算法成为调度算法。 进程调度的核心问题是采用什么样的算法把处理机分配给进程，好的算法将提高资源利用率，减少处理机的空闲时间，避免有些作业长期得不到相应的情况发生等，从而设计出受欢迎的操作系统。较常见的几种进程调度算法有：先来先服务调度算法；短作业优先调度算法；时间片轮转调度算法；优先级调度算法；高响应比优先算法和多级反馈队列调度算法等。 2.1设计目的 无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机
操作系统第三章总复习题 一、单选题 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 来模拟进程的一次运行。 提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。
实验报告 学院（系）名称：计算机与通信工程学院 姓名学号专业计算机科学与技术班级2009级3班实验项目实验一：处理机调度算法的实现 课程名称操作系统课程代码0668036 实验时间2011 年11月17日第3、4节 2011 年11月21日第7、8节 2011 年11月24日第3、4节 实验地点软件实验室7-216 批改意见成绩 教师签字： 实验内容： 1．设定系统中有五个进程，每一个进程用一个进程控制块表示。 2．输入每个进程的“优先数”和“要求运行时间”。 3．为了调度方便，将五个进程按给定的优先数从大到小连成就绪队列。用一单元指出队列首进程，用指针指出队列的连接情况。 4．处理机调度总是选队首进程运行。采用动态优先数算法，进程每运行一次优先数就减“1”，同时将运行时间减“1”。 5．若某进程运行时间为零，则将其状态置为“结束”,且退出队列。 6．运行所设计程序，显示或打印逐次被选中进程的进程名，以及进程控制块的动态变化过程。 实验要求： 1．详细描述实验设计思想、程序结构及各模块设计思路； 2．详细描述程序所用数据结构及算法； 3．明确给出测试用例和实验结果； 4．为增加程序可读性，在程序中进行适当注释说明； 5．认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等； 6．实验报告撰写要求结构清晰、描述准确逻辑性强； 7．实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。
【实验过程记录（源程序、测试用例、测试结果及心得体会等）】 程序运行代码如下： #include
操作系统之调度算法和死锁中的银行家算法习 题答案 集团文件发布号：（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 短作业优先： 作业顺序：
第三章处理机调度与死锁 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．程序源代码................................................ 错误!未定义书签。
第四章处理机调度 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．在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则
处理器调度习题
处理器调度 选择题 ?当CPU执行操作系统代码时，则处理机处于( )。 ?A．执行态 B．目态 C．管态 D．就绪态 ?( )是机器指令的扩充，是硬件的首次延伸，是加在硬件上的第一层软件。 ?A．系统调用 B．操作系统 C．内核 D．特权指令 ?操作系统提供给程序员的接口是( )。 ?A．进程 B．系统调用 C．库函数 D．B和C ?用户程序向系统提出使用外设的请求方式是( )。 ?A．作业申请 B．原语 C．系统调用 D．I／O指令 ?当作业正常完成进入完成状态时，操作系统( )。 ?A．将输出该作业的结果并删除内存中的作业 ?B．将收回该作业的所占资源并输出结果 ?C．将收回该作业的所占资源及输出结果，并删除该作业 ?D．将收回该作业的所占资源及输出结果，并将它的控制块从当前的队列中删除 ?下列选项是关于作业和进程关系的描述，其中哪一个是不正确的( )。 ?A．作业的概念主要用在批处理系统中，而进程的概念则用在几乎所有的OS中。 ?B．作业是比进程低一级的概念。 ?C．一个作业至少由一个进程组成。 ?D．作业是用户向计算机提交任务的实体，而进程是完成用户任务的执行实体以及向系统申请分配资源的基本单位。 ?作业从后备作业到被调度程序选中的时间称为( )。 ?周转时间B．响应时间C．等待调度时间D．运行时间 ?设有三个作业J1，J2，J3，它们同时到达，运行时间分别为T1，T2，T3，且T1≤T2≤T3，若它们在一台处理机上按单道运行，采用短作业优先算法，则平均周转时间为( )。 ?A．T1+T2+T3 B．1／3(T1+T2+T3) ?C．T1+2／3T2+1／3T3 D．T1+1／3T2+2／3T3 ?从作业提交给系统到作业完成的时间间隔称为作业的( )。 ?A．中断时间 B．等待时间 C．周转时间 D．响应时间 ?设有四个作业同时到达，每个作业执行时间均为2 h，它们在一台处理机上按单道方式运行，则平均周转时间为( )。 ?A．1 h B．5 h C．2．5 h D．8 h ?FCFS调度算法有利于( )。 ?A．长作业和CPU繁忙型作业 B．长作业和I／O繁忙型作业 ?C．短作业和CPU繁忙型作业 D．短作业和I／O繁忙型作业 ?下列哪种说法不是SJ(P)F调度算法的缺点( )。 ?A．对于长作业(进程)不利 ?B．未考虑作业(进程)的紧迫程度 ?C．不能有效降低作业(进程)的平均等待时间 ?D．由于根据的是用户提供的估计执行时间，因此不一定真正做到短而优先。 ?选择排队进程中等待时间最长的进程被优先调度，该调度算法是( )。 ?A．先来先服务调度算法B．短进程优先调度算法 ?C．优先权调度算法D．高响应比优先调度算法 ?在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。 ?A．先来先服务调度算法B．短进程优先调度算法
保证调度算法 基本思想:向用户做出明确的性能保证,然后去实现它.如你工作时有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
: 操作系统 课程设计报告 @ 学校：广州大学 学院：计算机科学与教育软件学院 班级：计算机127班 课题：处理机调度程序 任课老师：陶文正、陈文彬 姓名：黄俊鹏 { 学号：11
班内序号：27 成绩： 日期：2015年1月6日 一、设计目的 在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个。也就是说能运行的进程数大于处理机个数。为了使系统中的进程能有条不紊地工作，必须选用某种调度策略，选择一进程占用处理机。要求学生设计一个模拟处理机调度算法，以巩固和加深处理机调度的概念。 二、设计要求 1）进程调度算法包括：时间片轮转法，短作业优先算法，动态优先级算法。2）可选择进程数量 3）本程序包括三种算法，用C语言实现，执行时在主界面选择算法（可用函数实现）（进程数，运行时间，优先数由随机函数产生）执行，显示结果。 三、设计思路及算法思想 1.· 2.界面菜单选项 一级菜单提供2个选项： ①自动生成进程数量 ②手动输入所需进程数量 一级菜单选择完毕后进入二级菜单： ①重新生成进程 ②时间片轮转法 《 ③短作业优先算法 ④动态优先级算法 ⑤退出程序 3.调度算法
程序所用PCB结构体 ! 需要用到的进程结构体如上图所示 1)时间片轮转法 主要是设置一个当前时间变量，curTime和时间片roundTime。 遍历进程组的时候，每运行一个进程，就把curTime += roundTime。进程已运行时间加roundTime 2)短作业优先算法 遍历进程组，找到未运行完成并且运行时间最短的进程，让它一次运行完成，如此往复，直到所有进程都运行完成为止。 3)— 4)动态优先级算法 做法跟短作业优先算法类似，此处主要是比较进程的优先数，优先级高者，先执行。直到全部执行完毕。当一个进程运行完毕后，适当增减其余进程的优先数，以达到动态调成优先级的效果。 4.程序流程图
操作系统之调度算法和死锁中的银行家算法习题答案
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
操作系统上机测试作业调度算法算法 一、实验目的和要求（供参考） 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 #include PCB *cur,*p; p=head; cur=p->next; p->next =cur->next; cur->Level--; cur->Time--; cout<<"此次执行的进程信息（执行后）:进程名"; cout< 实验二处理机调度算法 （1）处理机调度的目的是什么？ 为提高内存利用率和系统吞吐量。 将那些暂时不能运行的进程调至外存，当内存不紧张时，将那些具备运行条件的就绪进程重新调入内存。 合理快速的处理计算机软件硬件资源，分配处理机，用以提高处理机的利用率及改善系统性能（吞吐量，响应时间）。 （2）处理机调度的算法有哪些，各自的优缺点是什么？ ①先来先服务算法：有利于长作业（进程），不利于短作业（进程）； ②短作业优先调度算法：有利于短作业（短进程），不利于长作业（长进程）； ③高优先权调度算法：静态缺点：可能导致低优先权进程长期得不到调度甚至饿死； 动态：优先权随进程等待时间增加或执行而变 ④高响应比优先调度算法 ⑤基于时间片轮转调度算法：时间片太小，会频繁发生中断，系统开销增大 时间片太大，响应进程慢。 ⑥多级反馈队列调度算法：具有较好的性能，能很好满足各类型用户的需求。 1．内存中作业运行的序列：A、B、D、C 2．A进入内存的时刻1，结束的时刻5 B进入内存的时刻5，结束的时刻8 D进入内存的时刻8，结束的时刻10 C进入内存的时刻10，结束的时刻15 3．平均周转时间：6 1．内存中作业运行的序列：B、C、A、D 2．B进入内存的时刻3，结束的时刻6 C进入内存的时刻6，结束的时刻11 A进入内存的时刻11，结束的时刻15 D进入内存的时刻15，结束的时刻17 3．平均周转时间：8.75 （4）画出处理机调度算法的程序流程图； （5）补全参考程序； void process(int currentTmp, int nextTmp) { int j; int s=nextTmp-currentTmp; while(memoryNum>0 && s>=memory[0].needtime){ totalTime=totalTime+memory[0].needtime; s=s-memory[0].needtime; printf("线程%c的开始时间是:%d,结束时间 是:%f\n",memory[0].id,memory[0].cputime,totalTime+1); allTime+=totalTime+1; memoryNum--; for(j = 1; j<=memoryNum; j++) memory[j-1] = memory[j]; if(waitNum>0 && s>0){ memory[memoryNum] = wait[0]; memoryNum++; waitNum--; for(j = 1; j<=waitNum; j++) wait[j-1] = wait[j]; sort(memory,memoryNum, 'P'); } } if(memoryNum>0 && s #include cout<<"请输入提出磁盘I/O申请的进程数:"; cin>>N; cout<<"请依次输入要访问的磁道号："; for(int i=0;i 中南大学 实验名称：处理机调度 课程名称：计算机操作系统 学生姓名盛希玲 学号 05 学院信息科学与工程学院 专业班级电子信息工程0602 完成时间 2008年10月12日 目录 一实验内容........................... 错误!未定义书签。二实验目的........................... 错误!未定义书签。三实验题目........................... 错误!未定义书签。四基本思想........................... 错误!未定义书签。五算法分析........................... 错误!未定义书签。六流程图............................. 错误!未定义书签。七算法描述........................... 错误!未定义书签。八运行输出结果....................... 错误!未定义书签。 一实验内容 选择一个调度算法，实现处理机调度。 二实验目的 多道系统中，当就绪进程数大于处理机数时，须按照某种策略决定哪些进程优先占用处理机。本实验模拟实现处理机调度，以加深了解处理机调度的工作。 三实验题目 设计一个按优先权调度和时间片轮转算法实现处理机调度的程序。 四基本思想 先选择时间片的个数和每个时间片需要的时间，正在运行的进程每运行一秒其优先权数目加一，即其优先权减小。每个时间片运行结束后，选择进入时间片进程优先权数目最小的进程，开始下一个时间片的运行。如果有进程运行结束，则离开，再在就绪队列中选择优先权数目最小的进程进入。在运行期间，如果有新的进程来到，按优先权大小放入就绪队列中。 五算法分析 定义一个结构体，此包含了PCB的信息： struct PCB { char PID[5]; /*进程名*/ int needtime; /*要求运行的时间*/ int cputime; /*已运行时间*/ int priority; /*优先权(越小越高)*/ int starttime; /*进入就绪队列的时间*/ int overtime; /*运行完成的时间*/ int state; /*状态:1就绪2运行3完成*/ struct PCB *next; }; 子函数struct PCB *create(int num,int n)用来建立一个按优先级大小排列的就绪进程链表和一个按时间先后循序排列的将进入就绪进程的链表。按优先数调度算法实现处理机调度C++程序代码
处理机调度算法实验报告
操作系统磁盘调度算法(C++)
计算机操作系统-处理机调度实验报告
相关主题
文本预览