处理器调度之动态优先数调度算法
1 处理机调度
实验内容及要求
实验内容：按优先数调度算法实现处理器调度。
实验要求：能接受键盘输入的进程数、进程标识、进程优先数及要求运行时间，能显示每次进程调度的情况：运行进程、就绪进程和就绪进程的排列情况。
实验目的
本实验模拟在单处理器环境下的处理器调度，加深了解处理器调度工作。
实验环境
本实验的设计基于Windows7操作系统DevC++环境，用C语言实现编程。
实验思路
(1) 每个进程用一个PCB来代表。PCB的结构为：
进程名——作为进程标识。
优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。
要求运行时间——假设进程需要运行的单位时间数。
状态——假设两种状态：就绪和结束，用R表示就绪，用E表示结束。
初始状态都为就绪状态。
指针——按优先数的大小把5个进程连成队列，用指针指出下一个进程PCB的首地址。
(2) 开始运行之前，为每个进程确定它的“优先数”和“要求运行时间”。通过键盘输入这些参数。
(3) 处理器总是选择队首进程运行。采用动态改变优先数的办法，进程每运
行1次，优先数减1，要求运行时间减1。
(4) 进程运行一次后，若要求运行时间不等于0，则将它加入就绪队列，否则，将状态改为“结束”，退出就绪队列。
(5) 若就绪队列为空，结束，否则转到(3)重复。
数据结构与全局变量
typedef struct pcb{
int pname;
.\n", >pname);
printf("%s ends after %d slice(s).", >pname, >runTime);
}
else
while!=NULL)
{
sortProcess();
printProcessInfo();
printProcessLink();
runProcess();
}
return 0;
}
void createProcess()
{
PCB *p, *prior;
printf("How many process do you want to run:");
scanf("%d", &num);
while(num<=0)
{
printf("Number is invalid. Input again:\n");
scanf("%d", &num);
}
p = (PCB*)malloc(sizeof(PCB));
prior = &readyHead;
prior->next=p;
for (int i = 0; i < num; i++)
{
printf("Input NO.%2d process name:", i+1);
scanf("%s", p->pname);
printf(" priority:");
scanf("%d", &(p->priority));
printf(" runTime:");
scanf("%d", &(p->runTime));
p->state = 'R';
p->next = (PCB*)malloc(sizeof(PCB));
prior=p;
p=p->next;
}
free(p);
p = NULL;
prior->next=NULL;
readyEnd=prior;
printf("\n");
}
void sortProcess()
{
char name[N];
int i,j, priorityNum, timeNum;
PCB *p, *rear;
for(p=; p!=NULL; p=p->next)
for(rear=p->next; rear!=NULL; rear=rear->next) if(p->priority
{
strcpy(name, p->pname);
priorityNum=p->priority;
timeNum=p->runTime;
strcpy(p->pname, rear->pname);
p->priority=rear->priority;
p->runTime=rear->runTime;
strcpy(rear->pname, name);
rear->priority=priorityNum;
rear->runTime=timeNum;
}
}
void printProcessLink()
{
PCB *p=;
printf("process link: \n");
while(p!=NULL)
{
printf("%s",p->pname);
p=p->next;
if(p!=NULL) printf("->");
}
printf("\n");
}
void printProcessInfo()
{
PCB *p=;
printf("process information before running:\n");
printf("=================================================\n");
printf("NAME PRIORITY RUNTIME STATUS NEXT\n");
printf("=================================================\n");
while(p!=NULL)
{
printf("%-16s %-8d %-8d %-8s %s\n",p->pname, p->priority, p->runTime, (p->state=='R')"ready":"end", p->next->pname);
p=p->next;
}
}
void runProcess()
{
PCB *p=;
printf("process run:\n");
printf("%s\n",p->pname);
p->priority--;
p->runTime--;
=p->next;
if(p->runTime==0)
{
p->state='E';
printf("%s is terminated\n", p->pname);
free(p);
}
else
{
readyEnd->next=p;
p->next=NULL;
readyEnd=p;
}
printf("\n");
}
短作业优先调度算法
青岛理工大学 操作系统课程设计报告 院（系）：计算机工程学院 专业：计算机科学与技术专业 学生姓名: 班级：＿＿学号: 题目：短作业优先调度算法的进程调度程序＿ 起迄日期:＿＿＿＿＿＿＿＿ 设计地点: 指导教师: 2011—2012年度第 1 学期 完成日期: 2012 年 1 月日
一、课程设计目的 进行操作系统课程设计主要是在学习操作系统课程的基础上，在完成操作系统各部分实验的基础上，对操作系统的整体进行一个模拟，通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之间的联系，最后达到对完整系统的理解。同时，可以提高运用操作系统知识解决实际问题的能力；锻炼实际的编程能力、开发软件的能力；还能提高调查研究、查阅技术文献、资料以及编写软件设计文档的能力。 二、课程设计内容与要求 设计目的：在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个，且进程之间也存在着同步与互斥的关系，要求采用指定的调度策略，使系统中的进程有条不紊地工作，通过观察诸进程的运行过程，以巩固和加深处理机调度的概念。 2、设计要求（多道、单处理机）： 1)每一个进程有一个PCB，其内容可以根据具体情况设定。 2)可以在界面设定的互斥资源（包括两种：输入设备与输出设备）的数目 3)进程数、进入内存时间、要求服务时间可以在界面上进行设定 4)进程之间存在一定的同步与互斥关系，可以通过界面进行设定，其表示方法如下： 进程的服务时间由三段组成：I2C10O5（表示进程的服务时间由2个时间片的输入，10个时间片的计算，5个时间片的输出） 进程间的同步关系用一个段表示：W2，表示该进程先要等待P2进程执行结束后才可以运行 因此，进程间的同步与互斥关系、服务时间可以统一用四段表示为：I2C10O5W2 5)可以在运行中显示各进程的状态：就绪、阻塞、执行 6)采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相 应的阻塞队列 7)具有一定的数据容错性 三、系统分析与设计 1、系统分析 本系统主要是采用短作业优先算法进程的进程调度过程。短作业优先调度算法，是指对短作业或短进程优先调度的算法。他们可以分别用于作业调度和进程调度，短作业优先的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将他们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给他，，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再度重新调度。本程序采用了非抢占式短作业优先调度。而非抢占式这种方式，一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。因此，在要求比较严格的实时系统中，不宜采用这种调度方式本系统的主要是在满足要求多道单处理机的情况下进行短作业的优先调度。 本系统在测试时输入了五个进程，按实验要求如I2C10O5（表示进程的服务时间由2个时间片的输入，10个时间片的计算，5个时间片的输出，5个时间片的计算组成）的方式输入，各进程的信息如下：（0 0 1 1 1 ）（1 2 1 2 2 ）（2 4 1 1 1 ）
按优先数调度算法实现处理器调度的模拟设计与实现
实验1 处理器调度 一、实验内容 选择一个调度算法，实现处理器调度。 二、实验目的 在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实验模拟在单处理器情况下的处理器调度，帮助学生加深了解处理器调度的工作。 三、实验题目 按优先数调度算法实现处理器调度的模拟设计与实现。 四、源程序 #include
else//找到插入 { break; } } } pr->next=p;//插入 q->next=pr; ++root->state;//进程个数加一 } //创建进程 _proc Creat(char name[],int priority,int run_time) { _proc pr; strcpy(https://www.sodocs.net/doc/e112293483.html,,name); pr.priority=priority; pr.run_time=run_time; pr.state=0; pr.next=NULL; return pr; } //删除就绪队列中对首进程 _proc* Delete() { _proc* pr=root->next; root->next=root->next->next; --root->state; return pr; } //对就绪队列排序,按照降序 void Sort() { if(root->next->run_time==0)//要执行时间为时，从就绪队列中删除该进程{ Delete(); root->next->state=1;
操作系统实验报告(进程调度算法)
操作系统实验报告(进程调度算法)
实验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)假定系统有5个进程，每个进程用一个PCB来代表。PCB的格式为： 进程名、指针、要求运行时间、优先数、状态。 进程名——P1~P5。 指针——按优先数的大小把5个进程连成队列，用指针指出下一个进程PCB的首地址。 要求运行时间——假设进程需要运行的单位时间数。 优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。 状态——假设两种状态，就绪，用R表示，和结束，用E表示。初始状态都为就绪状态。 (2) 每次运行之前，为每个进程任意确定它的“优先数”和“要求运行时间”。 (3) 处理器总是选队首进程运行。采用动态改变优先数的办法，进程每运行1次，优先 数减1，要求运行时间减1。 (4) 进程运行一次后，若要求运行时间不等于0，则将它加入队列，否则，将状态改为“结 束”，退出队列。 (5) 若就绪队列为空，结束，否则，重复(3)。 2．程序中使用的数据结构及符号说明： #define num 5//假定系统中进程个数为5 struct PCB{ char ID;//进程名 int runtime;//要求运行时间 int pri;//优先数 char state; //状态，R-就绪，F-结束 }; struct PCB pcblist[num];//定义进程控制块数组 3．流程图： (1)主程序流程图： (2)子程序init()流程图：
(3) 子程序max_pri_process()流程图：
(4)子程序show()流程图：
(5)子程序run()流程图：
优先级调度算法实验报告
优 先 级 调 度 算 法 实 验 报 告 院系:****************学院班级:*********** 姓名:*** 学号:************
一、实验题目：优先级调度算法 二、实验目的 进程调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解优先级算法的具体实施办法。 三、实验内容 1.设计进程控制块PCB的结构，通常应包括如下信息： 进程名、进程优先数（或轮转时间片数）、进程已占用的CPU时间、进程到完成还需要的时间、进程的状态、当前队列指针等。 2.编写优先级调度算法程序 3.按要求输出结果。 四、实验要求 每个进程可有三种状态；执行状态（RUN）、就绪状态（READY,包括等待状态）和完成状态（FINISH），并假定初始状态为就绪状态。（一）进程控制块结构如下： NAME——进程标示符 PRIO/ROUND——进程优先数 NEEDTIME——进程到完成还需要的时间片数 STATE——进程状态 NEXT——链指针 注： 1.为了便于处理，程序中进程的的运行时间以时间片为单位进行
计算； 2.各进程的优先数或，以及进程运行时间片数的初值，均由用户在程序运行时给定。 （二）进程的就绪态和等待态均为链表结构，共有四个指针如下：RUN——当前运行进程指针 READY——就需队列头指针 TAIL——就需队列尾指针 FINISH——完成队列头指针 五、实验结果：
六、实验总结： 首先这次实验的难度不小，它必须在熟悉掌握数据结构的链表和队列的前提下才能完成，这次实验中用了三个队列，就绪队列，执行队列和完成队列，就绪队列中的优先级数是有序插入的，当进行进程调度的时候，需要先把就绪队列的队首节点（优先级数最大的节点）移入执行队列中，当执行进程结束后，判断该进程是否已经完成，如果已经完成则移入完成队列，如果没有完成，重新有序插入就绪队列中，这就是这次实验算法的思想。 附录（算法代码）：
先来先服务和短作业优先调度算法
《操作系统》实验一实验报告 【实验题目】：先来先服务FCFS和短作业优先SJF进程调度算法【实验目的】 通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。 【实验内容】 问题描述： 设计程序模拟进程的先来先服务FCFS和短作业优先SJF调度过程。假设有n个进程分别在T1, …,T n时刻到达系统，它们需要的服务时间分别为S1, … ,S n。分别采用先来先服务FCFS和短作业优先SJF 进程调度算法进行调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。 程序要求如下： 1）进程个数n；每个进程的到达时间T1, …,T n和服务时间S1, … ,S n；选择算法1-FCFS，2-SJF。 2）要求采用先来先服务FCFS和短作业优先SJF分别调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间； 3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等； 4）输出：要求输出计算出来的每个进程的周转时间，带权周转时间，
所有进程的平均周转时间，带权平均周转时间。【实验过程】 #include
时间片轮转算法和优先级调度算法 C语言模拟实现
一、目得与要求?进程调度就是处理机管理得核心内容。本实验要求用高级语言编写模拟进程调度程序,以便加深理解有关进程控制快、进程队列等概念，并体会与了解优先数算法与时间片轮转算法得具体实施办法。 二、实验内容 1、设计进程控制块PCB得结构,通常应包括如下信息: 进程名、进程优先数(或轮转时间片数）、进程已占用得CPＵ时间、进程到完成还需要得时间、进程得状态、当前队列指针等。 2、编写两种调度算法程序: 优先数调度算法程序?循环轮转调度算法程序 3、按要求输出结果。?三、提示与说明 分别用两种调度算法对伍个进程进行调度。每个进程可有三种状态;执行状态(ＲUN)、就绪状态(ＲEＡDY,包括等待状态)与完成状态(ＦＩＮＩSH）,并假定初始状态为就绪状态。?(一）进程控制块结构如下：?ＮAＭE——进程标示符ＰRIO／ＲＯＵNＤ——进程优先数／进程每次轮转得时间片数（设为常数2)? CPUTIME——进程累计占用CPU得时间片数? NEEDTＩME——进程到完成还需要得时间片数 SＴＡTE——进程状态?ＮEXT——链指针?注: １、为了便于处理，程序中进程得得运行时间以时间片为单位进行计算; 2、各进程得优先数或轮转时间片数,以及进程运行时间片数得初值,均由用户在程序运行时给定。?(二)进程得就绪态与等待态均为链表结构，共有四个指针如下:? RUＮ——当前运行进程指针 RＥADY——就需队列头指针 TAIＬ——就需队列尾指针 FINISＨ——完成队列头指针 1、在优先数算法中,进程优先数得初值设为： (三)程序说明? 50－NEEDＴIME?每执行一次,优先数减1，CＰU时间片数加１,进程还需要得时间片数减1。 在轮转法中,采用固定时间片单位（两个时间片为一个单位),进程每轮转一次,CP
短作业优先算法
短作业（进程）优先调度算法 1.短作业（进程）优先调度算法SJ（P）F，是指对短作业或 短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。SJ(P)F 调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。该算法对长作业不利，完全未考虑作业的紧迫程度。 2.流程图 3.代码
#include<> #include<> #include<> struct sjf{ char name[10]; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; }; sjf a[100]; void input(sjf *p,int N) { int i; printf("intput the process's name & arrivetime & servicetime:\nfor exmple: a 0 100\n"); for(i=0;i<=N-1;i++) { printf("input the %dth process's information:\n",i+1); scanf("%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetim e);
按优先数调度算法实现处理机调度C++程序代码
#include
PCB *cur,*p; p=head; cur=p->next; p->next =cur->next; cur->Level--; cur->Time--; cout<<"此次执行的进程信息（执行后）:进程名"; cout< 1 处理机调度 1.1 实验内容及要求 实验内容：按优先数调度算法实现处理器调度。 实验要求：能接受键盘输入的进程数、进程标识、进程优先数及要求运行时间，能显示每次进程调度的情况：运行进程、就绪进程和就绪进程的排列情况。 1.2 实验目的 本实验模拟在单处理器环境下的处理器调度，加深了解处理器调度工作。 1.3 实验环境 本实验的设计基于Windows7操作系统DevC++5.11环境，用C语言实现编程。 1.4 实验思路 (1) 每个进程用一个PCB来代表。PCB的结构为： 进程名——作为进程标识。 优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。 要求运行时间——假设进程需要运行的单位时间数。 状态——假设两种状态：就绪和结束，用R表示就绪，用E表示结束。 初始状态都为就绪状态。 指针——按优先数的大小把5个进程连成队列，用指针指出下一个进程PCB的首地址。 (2) 开始运行之前，为每个进程确定它的“优先数”和“要求运行时间”。通过键盘输入这些参数。 (3) 处理器总是选择队首进程运行。采用动态改变优先数的办法，进程每运 行1次，优先数减1，要求运行时间减1。 (4) 进程运行一次后，若要求运行时间不等于0，则将它加入就绪队列，否则，将状态改为“结束”，退出就绪队列。 (5) 若就绪队列为空，结束，否则转到(3)重复。 1.5 数据结构与全局变量 typedef struct pcb{ int pname;//进程名 int priority;//优先级 int runTime;//所需时间 int state;//状态 struct pcb* next;//下一个进程控制块 }PCB; //进程控制块 int num;//存储进程数 PCB readyHead;//头结点，不存储进程 PCB *readyEnd;//指向尾结点的指针 1.6 函数说明 （1）主函数main() 输入进程数并调createProcess()初始化进程；若有进程，则依次调用sortProcess()、runProcess()、printProcessLink()和printProcessInfo()。（2）进程创建函数createProcess() 输入进程标识、优先级和运行时间进行初始化。 （3）进程排序函数sortProcess() 用冒泡排序算法根据进程的优先级进行降序排序，每次排序之后优先级最高的进程放在就绪队列首。 （4）进程运行函数runProcess() 将数组首的进程优先级和所需时间减1； 若剩余所需时间为0，则PCB状态标记为E（结束）。 课程设计 采用短作业优先调度算法调度程序 学号： 姓名： 专业： 指导老师： 日期： 目录 一、实验题目 (3) 二、课程设计的目的 (3) 三、设计内容 (3) 四、设计要求 (3) 五、主要数据结构及其说明 (4) 六、程序运行结果 (5) 七、流程图 (7) 八、源程序文件 (9) 九、实验体会 (13) 十、参考文献 (13) 摘要 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。 一、实验题目 采用短作业优先算法的的进程调度程序 二、课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三、设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 四、设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间同步关系，故只有两种状态） 5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列 余蓝涛1 (天津大学精密仪器与光电子工程学院天津 300072 ) 摘要： 嵌入式系统对强大实时处理能力的需求和相对紧张的内存及内核资源的现实，对嵌入式操作系统任务调度提出了较高的要求。因此任务调度的算法的分析，实现和优化，对实现嵌入式系统的实时性有着重大的意义。从算法提出的理论基础出发，深入分析了经典的单调速率调度算法的思想，特点，具体实现并重点评价了该算法的优点和局限性。 关键词：单调速率调度算法实时嵌入式系统 Abstract： The zest for powerful real-time processing of embedded system and the reality of relatively scare memory and kernel resource pave way for the high request for task scheduling. Therefore, the analysis, implementation and optimization of task scheduling algorithm have a vast meaning for the real-time system. Based on theoretical basis of classic rate-monotonic scheduling algorithm, this paper not only analyzes fundamental thought, characteristics, practical implementation of this classic algorithm in depth, but also rate its advantages and disadvantages. Key words: Rate-monotonic Scheduling, Algorithm, Real-time, Embedded System 一，引言 现在嵌入式系统得到高速的发展。它的发展为几乎所有的电子产品注入了新的活力。它在国民经济各领域和我们日常生活中发挥了越来越重要的作用。 嵌入式系统在航天、军事、工控以及家电等方面得到了广泛应用。囿于体积，能耗，价格等方面的约束，嵌入式系统处理器速度比较慢，存储器容量也有限。而传统的操作系统为了取得较高的性能，要求硬件设备具有强大的处理能力，大容量的存储能力以及对网络的支持功能，这使得传统的操作系统难以简单地移植到嵌入式系统中。 这就导致了嵌入式操作系统由于受到系统的限制，往往内存资源都非常的有限，要求操作系统的内核都非常的精炼，对于系统中的资源操作系统内核需要进行统一的分配和调度。 嵌入式操作系统调度策略一直以来都是嵌入式操作系统的研究 中的一个热点。任务调度是嵌入式操作系统内核的关键部分，如何进行任务调度，使得各个任务能在其截止期限内得以完成是嵌入式操作系统的一个重要的研究领域。 二，嵌入式实时操作系统 绝大部分嵌入式系统都是实时系统，而且多是实时多任务系统。所谓“实时”,是指系统的正确性不仅仅依赖于计算的逻辑结果而且依赖于结果产生的时间[1][6]。结果产生的时间就是通常所说的截止期限(deadline),描述系统实时性的指标主要有： a,对紧急事件可预见性的快速响应； 1作者简介：余蓝涛（1991-）江西省人天津大学精密仪器与光电子工程学院测控技术与仪器本科生学号：79 短作业优先调度算法 学院计算机科学与技术 专业 学号 学生姓名 指导教师姓名 2014-3-18目录 九参考文献……………………………………………………………………………………………………… 实验题目 采用短作业优先算法的进程调度程序 课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间同步关系，故只有两种状态） 5. 具有一定的数据容错性 主要数据结构及其说明 算法的简要说明：短作业（进程）优先调度算法SJ（P）F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。优点是SJ(P)F调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。缺点是该算法对长作业不利；完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）长期不被调度；由于作业（进程）的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业游戏那调度。 该程序定义了一个进程数据块(struct spf)，该数据块有进程名(name)、到达时间(arrivetime)、服务时间(servicetime)、开始执行时间(starttime)、完成时间 (finishtime)、周转时间(zztime)、带权周转时间(dqzztime)。用到的公式有：完成时间=到达时间+服务时间；周转时间=完成时间-到达时间；带权周转时间=周转时间/服务时间；(第一次执行的进程的完成时间=该进程的到达时间；下一个进程的开始执行时间=上一个进程的完成时间)。运行进程的顺序需要对进程的到达时间和服务时间进行比较。如果某一进程是从0时刻到达的，那么首先执行该进程；之后就比较进程的服务时间，谁的服务时间短就先执行谁（如果服务时间相同则看它们的到达时间，到达时间短的先执行）；如果到达时间和服务时间相同，则按先来先服务算法执行。 一、目的和要求 进程调度是处理机管理的核心容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解优先数算法和时间片轮转算法的具体实施办法。 二、实验容 1.设计进程控制块PCB的结构，通常应包括如下信息： 进程名、进程优先数（或轮转时间片数）、进程已占用的CPU时间、进程到完成还需要的时间、进程的状态、当前队列指针等。 2.编写两种调度算法程序： 优先数调度算法程序 循环轮转调度算法程序 3.按要求输出结果。 三、提示和说明 分别用两种调度算法对伍个进程进行调度。每个进程可有三种状态；执行状态（R UN）、就绪状态（READY,包括等待状态）和完成状态（FINISH），并假定初始状态为就绪状态。 （一）进程控制块结构如下： NAME——进程标示符 PRIO/ROUND——进程优先数/进程每次轮转的时间片数（设为常数2） CPUTIME——进程累计占用CPU的时间片数 NEEDTIME——进程到完成还需要的时间片数 STATE——进程状态 NEXT——链指针 注： 1.为了便于处理，程序中进程的的运行时间以时间片为单位进行计算； 2.各进程的优先数或轮转时间片数，以及进程运行时间片数的初值，均由用户在程序运行时给定。 （二）进程的就绪态和等待态均为链表结构，共有四个指针如下： RUN——当前运行进程指针 READY——就需队列头指针 TAIL——就需队列尾指针 FINISH——完成队列头指针 （三）程序说明 1. 在优先数算法中，进程优先数的初值设为： 50-NEEDTIME 每执行一次，优先数减1，CPU时间片数加1，进程还需要的时间片数减1。 在轮转法中，采用固定时间片单位（两个时间片为一个单位），进程每轮转一次，CPU时间片数加2，进程还需要的时间片数减2，并退出CPU，排到就绪队列尾，等待下一次调度。 2. 程序的模块结构提示如下： 整个程序可由主程序和如下7个过程组成： （1）INSERT1——在优先数算法中，将尚未完成的PCB按优先数顺序插入到就绪队列中； （2）INSERT2——在轮转法中，将执行了一个时间片单位（为2），但尚未完成的进程的PCB，插到就绪队列的队尾； （3）FIRSTIN——调度就绪队列的第一个进程投入运行； （4）PRINT——显示每执行一次后所有进程的状态及有关信息。 （5）CREATE——创建新进程，并将它的PCB插入就绪队列； （6）PRISCH——按优先数算法调度进程； （7）ROUNDSCH——按时间片轮转法调度进程。 主程序定义PCB结构和其他有关变量。 （四）运行和显示 程序开始运行后，首先提示：请用户选择算法，输入进程名和相应的NEEDTIM E值。 每次显示结果均为如下5个字段： name cputime needtime priority state 注： 动态优先级调度算法的特点与实现 本文从实时操作系统的调度功能入手，简单介绍了实时调度算法的分类和种类，并主要讨论动态优先级调度算法的特点和实现。接下来本文介绍了两类动态优先级调度算法：截止时间优先调度算法和最短空闲时间优先调度算法的定义及实现方式。然后将静态调度与动态调度进行比较，突出动态优先级调度的特点，同时指出其可能导致的优先级反转、死锁等不良后果。然后具体介绍了优先级反转的定义以及解决该问题的两种方案：采用优先级继承协议与采用优先级天花板协议。 在嵌入式的实时操作系统中，调度是一个非常重要的功能，用来确定多任务环境下任务执行的顺序和在获得CPU资源后能够执行的时间长度。 操作系统通过一个调度程序（Scheduler）来实现调度功能。调度程序以函数的形式存在，用来实现操作系统的调度算法。调度程序本身并不是一个任务，而是一个函数调用，可在内核的各个部分进行调用。调度程序是影响系统性能（如吞吐率、延迟时间等）的重要部分。在设计调度程序是、时，通常要综合考虑如下因素： ●CPU的使用率（CUP utilization）； ●输入/输出设备的吞吐率； ●响应时间（responsive time）； ●公平性； ●截止时间。 这些因素之间具有一定的冲突性。比如可通过让更多的任务处于就绪状态来提高CPU 的使用率，但这显然会降低系统的响应时间。因此，调度程序的设计需要优先考虑最重要的需求，然后在各种因素之间进行折中处理。 可以把一个调度算法（Scheduling Algorithms）描述为是在一个特定时刻用来确定将要运行的任务的一组规则。从1973年Liu和Layland开始关于实时调度算法的研究工作以来 O S短作业优先调度算 法C语言 采用短作业优先调度算法调度程序 学号： 姓名： 专业： 指导老师： 日期： 目录 一、实验题目 (3) 二、课程设计的目的 (3) 三、设计内容 (3) 四、设计要求 (3) 五、主要数据结构及其说明 (4) 六、程序运行结果 (5) 七、流程图 (7) 八、源程序文件 (9) 九、实验体会 (13) 十、参考文献 (14) 摘要 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。 一、实验题目 采用短作业优先算法的的进程调度程序 二、课程设计的目的 ●操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既 动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 ●进一步巩固和复习操作系统的基础知识。 ●培养学生结构化程序、模块化程序设计的方法和能力。 ●提高学生调试程序的技巧和软件设计的能力。 ●提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三、设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 四、设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 时间片轮转算法和优先级调度算法C语言模拟实现收藏 一、目的和要求 进程调度是处理机管理的核心内容。本实验要求用高级语言编写模拟进程调度程序，以便加深理解有关进程控制快、进程队列等概念，并体会和了解优先数算法和时间片轮转算法的具体实施办法。 二、实验内容 1.设计进程控制块PCB的结构，通常应包括如下信息： 进程名、进程优先数（或轮转时间片数）、进程已占用的CPU时间、进程到完成还需要的时间、进程的状态、当前队列指针等。 2.编写两种调度算法程序： 优先数调度算法程序 循环轮转调度算法程序 3.按要求输出结果。 三、提示和说明 分别用两种调度算法对伍个进程进行调度。每个进程可有三种状态；执行状态（R UN）、就绪状态（READY,包括等待状态）和完成状态（FINISH），并假定初始状态为就绪状态。 （一）进程控制块结构如下： NAME——进程标示符 PRIO/ROUND——进程优先数/进程每次轮转的时间片数（设为常数2） CPUTIME——进程累计占用CPU的时间片数 NEEDTIME——进程到完成还需要的时间片数 STATE——进程状态 NEXT——链指针 注： 1.为了便于处理，程序中进程的的运行时间以时间片为单位进行计算； 2.各进程的优先数或轮转时间片数，以及进程运行时间片数的初值，均由用户在程序运行时给定。 （二）进程的就绪态和等待态均为链表结构，共有四个指针如下： RUN——当前运行进程指针 READY——就需队列头指针 TAIL——就需队列尾指针 FINISH——完成队列头指针 （三）程序说明 1. 在优先数算法中，进程优先数的初值设为： 50-NEEDTIME 每执行一次，优先数减1，CPU时间片数加1，进程还需要的时间片数减1。 在轮转法中，采用固定时间片单位（两个时间片为一个单位），进程每轮转一次，CPU时间片数加2，进程还需要的时间片数减2，并退出CPU，排到就绪队列尾，等待下一次调度。 2. 程序的模块结构提示如下： 整个程序可由主程序和如下7个过程组成： （1）INSERT1——在优先数算法中，将尚未完成的PCB按优先数顺序插入到就绪队列中； （2）INSERT2——在轮转法中，将执行了一个时间片单位（为2），但尚未完成的进程的PCB，插到就绪队列的队尾； （3）FIRSTIN——调度就绪队列的第一个进程投入运行； （4）PRINT——显示每执行一次后所有进程的状态及有关信息。 （5）CREATE——创建新进程，并将它的PCB插入就绪队列； （6）PRISCH——按优先数算法调度进程； （7）ROUNDSCH——按时间片轮转法调度进程。 主程序定义PCB结构和其他有关变量。 （四）运行和显示 程序开始运行后，首先提示：请用户选择算法，输入进程名和相应的NEEDTIM E值。 每次显示结果均为如下5个字段： name cputime needtime priority state 注： 优先级调度算法 1、调度算法 考虑到紧迫型作业进入系统后能得到优先处理，引入了高优先级优先调度算法。 优先级调度的含义： （1）当该算法用于作业调度时，系统从后背作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行；（2）当该算法用于进程调度时，将把处理机分配给就绪进行队列中优先级最高的进程。 2、调度算法的两种方式 非抢占式优先级算法：在这种调度方式下，系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程就能一直执行下去，直至完成；或因等待某事件的发生使该进程不得不放弃处理机时，系统才能将处理机分配给另一个优先级高的就绪队列。 抢占式优先级调度算法：在这种调度方式下，进程调度程序把处理机分配给当时优先级最高的就绪进程，使之执行。一旦出现了另一个优先级更高的就绪进程时，进程调度程序就停止正在执行的进程，将处理机分配给新出现的优先级最高的就绪进程。常用于实时要求比较严格的实时系统中，以及对实时性能要求高的分时系统。 3、优先级的类型 进程的优先级可采用静态优先级和动态优先级两种，优先级可由用户自定或由系统确定。 静态优先级调度算法 含义：静态优先级是在创建进程时确定进程的优先级，并且规定它在进程的整个运行期间保持不变。 确定优先级的依据： 1）进程的类型。 2）进程对资源的需求。 3）根据用户的要求。 优点：简单易行；系统开销小。 缺点：不太灵活，很可能出现低优先级的作业，长期得不到调度而等待的情况；静态优先级法仅适合于实时要求不太高的系统。 动态优先级调度算法 含义：动态优先级是创建进程时赋予该进程一个初始优先级，然后其优先级随着进程的执行情况的变化而改变，以便获得更好的调度性能。 优点：使相应的优先级调度算法比较灵活、科学，可防止有些进程一直得不到调度，也可防止有些进程长期垄断处理机。 缺点：需要花费相当多的执行程序时间，因而花费的系统开销比较大。 4、实时调度算法 由于在任何一个实时系统中毒存在着若干个实时进程或任务，用来反应或控制相应的外部事件，并往往具有某种程度的紧迫性，所以对实时系统中的调度算法提出了某些特殊要求。 对实时系统的要求处理器调度之动态优先数调度算法
操作系统短作业优先调度算法
单调速率调度算法RMS
短作业优先调度算法 (1)
时间片轮转算法和优先级调度算法-C语言模拟实现-收藏
动态优先级调度算法的特点与实现
OS短作业优先调度算法C语言知识分享
时间片轮转算法和优先级调度算法 C语言模拟实现 收藏精编版
优先级调度算法
相关文档
- 设计一个按优先数调度算法实现处理器调度的程序
- 处理器调度之动态优先数调度算法
- 时间片轮转算法和优先级调度算法-C语言模拟实现-收藏
- 按优先数调度算法实现处理器调度的模拟设计与实现
- 处理器调度之动态优先数调度算法
- 优先级调度算法
- 采用优先数算法模拟进程调度程序
- 优先级调度算法
- 举出生活中调度的例子 说明其对应的调度算法
- 按优先数调度算法实现处理机调度C++程序代码
- 非抢占式高优先级调度算法
- 非抢占式高优先级调度算法
- 时间片轮转算法和优先级调度算法 C语言模拟实现 收藏
- 优先级调度算法
- 设计一个按优先数调度算法实现处理器调度的程序(可以输入进程的数量)
- 设计一个按优先数调度算法实现处理器调度的程序(可以输入进程的数量)
- 优先级调度算法
- 优先级调度算法
- 设计一个按优先数调度算法实现处理器调度的程序
- 时间片轮转算法和优先级调度算法 C语言模拟实现