一、先来先服务算法
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 输入各作业等待时间和所运行的时间 一、先来先服务算法 1．程序简介 先来先服务算法按照作业进入系统后备作业队列的先后次序挑选作业,先进入系统的作业将优先被挑选进入主存,创建用户进程,分配所需资源,然后,移入就绪队列.这是一种非剥夺式调度算法,易于实现,但效率不高.只顾及作业的等候时间,未考虑作业要求服务时间的长短,不利于短作业而优待长作业,不利于I/O繁忙型作业而有利于CPU繁忙型作业.有时为了等待场作业执行结束,短作业的周转时间和带全周转时间将变得很大,从而若干作业的平均周转时间和平均带权周转时间也变得很大。 2．分析 1．先定义一个数组代表各作业运行的时间，再定义一个数组代表各作业到达系统的时间，注意到达系统的时间以第一个作业为0基础（注意：若各程序都同时到达系统，则到达系统时间都为0）。 2．输入作业数。 3．然后运用循环结构累积作业周转时间和带权周转时间。 4．最后，作业周转时间和带权周转时间分别除以作业数即可得到平均作业周转时间和平均带权周转时间。 3．详细设计 源程序如下： #include 《操作系统原理》实验报告 实验名称：Linux随机进程调度算法实现 班级： 学号： 姓名： 日期： 2012/12/31 一、实验名称 Linux随机进程调度算法实现 二、所属课程名称 《操作系统原理》 三、实验原理 linux 0.11内核目录linux/kernel中的sched.c函数是内核中进程调度管理的程序，其中schedule()函数负责选择系统中下一个要运行的进程。 schedule()函数首先对所有任务（进程）进行检测，唤醒任何一个已经得到信号的进程。具体方法是任务数组中的每个进程，检查其报警定时值alarm。如果进程的alarm时间已经过期（alarm NR_TASKS：系统能容纳的最大进程数(64个)； task[]：任务（进程）数组； 更改代码如下：（linux 0.11内核目录下linux/kernel/sched.c 源文件的scheduling（）函数while（1）循环）while (1) { //定义c用来判断系统中是否可运行的任务（进程）存在; c=-1; //c初值设为-1，默认不存在可运行进程; next = 0;//next记录下一个即将运行的进程; i=jiffies % NR_TASKS+1; //i的值是随机产生的; p=&task[i];//p指向在task表中下标为i的进程； while (--i) { //遍历task[]； if(!*--p)continue; //如果task[i]不包含进程，跳过； //如果task[i]包含进程且该进程处于就绪状态，记录 //该任务（进程）序号，跳出无限循环while(1),转向 //switch_to()函数执行该任务（进程）； if ((*p)->state == TASK_RUNNING) { next = i; c=i; break; } } if (c) break;//如果没有任何任务(进程)要执行，则跳出， //转向switch_to()，执行0号进程(idle)。 } 进程调度算法实验报告 篇一：操作系统进程调度算法模拟实验报告 进程调度算法模拟 专业：XXXXX 学号：XXXXX 姓名：XXX 实验日期：20XX年XX月XX日 一、实验目的 通过对进程调度算法的模拟加深对进程概念和进程调度算法的理解。 二、实验要求 编写程序实现对5个进程的调度模拟，要求至少采用两种不同的调度算 法分别进行模拟调度。 三、实验方法内容 1. 算法设计思路 将每个进程抽象成一个控制块PCB， PCB用一个结构体描述。 构建一个进程调度类。将进程调度的各种算法分装在一个类中。类中存 在三个容器，一个保存正在或未进入就绪队列的进程，一个保存就绪的进程，另一个保存已完成的进程。还有一个PCB实例。主要保存正在运行的进程。类中其他方法都是围绕这三个容器可以这个运行中的PCB展开。 主要用到的技术是STL中的vector以维护和保存进程容器、就绪容器、 完成容器。 当程序启动时，用户可以选择不同的调度算法。然后用户从控制台输入 各个进程的信息，这些信息保存到进程容器中。进程信息输入完毕后，就开始了进程调度，每调度一次判断就绪队列是否为空，若为空则系统时间加一个时间片。判断进程容器中是否有新的进程可以加入就绪队列。 2. 算法流程图主程序的框架： ();//先来先服务 ();//最短进程优先调度//简单时间片轮转//最高优先数优先//输入进程信息 ();.m_WaitQueue.empty()||.m_ProcessQueue.empt() (); (); 进程调度过程： ; 3. 算法中用到的数据结构 struct fcfs{//先来先服务算法从这里开始char name[10];float arrivetime;float servicetime;float starttime;float finishtime;float zztime;float 处理器调度 选择题 当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．高响应比优先调度算法 在采用动态优先权的优先权调度算法中，如果所有进程都具有相同优先权初值，则此时的优先权调度算法实际上和( )相同。 操作系统实验报告(进程调度算法) 实验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.PC机。 2.Windows； 3.CodeBlocks 四、实验基本原理 1.本实验设计一个可指定作业个数的作业调度系统。可以输出先来先服务，最短作业优先，最高响应比三种作业调度算法的结果。 2.先来先服务就是按照各个作业进入系统的自然次序进行调度。最短作业优先就是优先调度并且处理短作业。最高响应比优先就是根据在程序运行过程中的最高响应比对应的作业先进行调度处理。 3.在设计程序过程中，将time相关的内容封装到类中，重载了加减乘除和输入输出以及比较运算符，方便12:00这种形式的数据的加减乘除运算和比较运算， 五、数据结构设计 1.时间类 class time { public: time(int x = 0, int y = 0) { time::hour = x; time::minute = y; } time& operator = (const time &t1) { this->hour=t1.hour; this->minute=t1.minute; return *this; } time operator + (time t2) { intminutes,hours; minutes = (minute + t2.minute) % 60; hours=hour+t2.hour+ (minute + t2.minute) /60; return time(hours,minutes); } time operator -(time t2) { intminutes,hours; minutes =minute - t2.minute; if (minute<0) { minutes += 60; hour--; } 操作系统实验报告（二） 实验题目：进程调度算法 实验环境：C++ 实验目的：编程模拟实现几种常见的进程调度算法，通过对几组进程分别使用不同的调度算法，计算进程的平均周转时间和平均带权周转时间，比较 各种算法的性能优劣。 实验内容：编程实现如下算法： 1.先来先服务算法； 2.短进程优先算法； 3.时间片轮转调度算法。 设计分析： 程序流程图： 1.先来先服务算法 开始 初始化PCB，输入进程信息 各进程按先来先到的顺序进入就绪队列 结束 就绪队列？ 运行 运行进程所需CPU时间 取消该进程 2.短进程优先算法 3.时间片轮转调度算法 实验代码： 1.先来先服务算法 #include int atime; //进程到达时间 int runtime; //进程运行时间 }fcs; void main() { int amount,i,j,diao,huan; fcs f[n]; cout<<"请输入进程个数:"< 目录 目录 ........................................................ 错误!未定义书签。1．课程设计目的.............................................. 错误!未定义书签。 编写目的................................................. 错误!未定义书签。2．课程设计内容.............................................. 错误!未定义书签。 设计内容................................................. 错误!未定义书签。3．课程设计方案.............................................. 错误!未定义书签。 模块划分................................................. 错误!未定义书签。 模块调用关系图........................................... 错误!未定义书签。 子模块程序流程图......................................... 错误!未定义书签。4．测试数据和结果............................................ 错误!未定义书签。 测试数据................................................. 错误!未定义书签。 测试结果................................................. 错误!未定义书签。 测试抓图................................................. 错误!未定义书签。5．参考文献.................................................. 错误!未定义书签。6．总结...................................................... 错误!未定义书签。 设计体会................................................. 错误!未定义书签。 结束语................................................... 错误!未定义书签。7．程序使用说明书............................................ 错误!未定义书签。8．程序源代码................................................ 错误!未定义书签。 一．课程概述 1.1.设计构想 程序能够完成以下操作：创建进程：先输入进程的数目，再一次输入每个进程的进程名、运行总时间和优先级，先到达的先输入；进程调度：进程创建完成后就选择进程调度算法，并单步执行，每次执行的结果都从屏幕上输出来。 1.2.需求分析 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目，要使这多个进程能够并发地执行，这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统必（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。本次实验在VC++6.0环境下实现先来先服务调度算法，短作业优先调度算法，高优先权调度算法，时间片轮转调度算法和多级反馈队列调度算法。 1.3.理论依据 为了描述和管制进程的运行，系统为每个进程定义了一个数据结构——进程控制块PCB(Process Control Block),PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息，系统总是通过PCB对进程进行控制，亦即，系统是根据进程的PCB 而不是任何别的什么而感知进程的存在的，PCB是进程存在的惟一标志。本次课程设计用结构体Process代替PCB的功能。 1.4.课程任务 一、用C语言（或C++）编程实现操作模拟操作系统进程调度子系统的基本功能；运用多 种算法实现对进程的模拟调度。 二、通过编写程序实现进程或作业先来先服务、高优先权、按时间片轮转、短作业优先、多 级反馈队列调度算法，使学生进一步掌握进程调度的概念和算法，加深对处理机分配的理解。 三、实现用户界面的开发 保证调度算法 基本思想:向用户做出明确的性能保证,然后去实现它.如你工作时有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 进程调度算法（附录）#include void display(pcb *p) { cout<<"name"<<" "<<"cputime"<<" "<<"needtime"<<" "<<"priority"<<" "<<"state"< 操作系统之调度算法和死锁中的银行家算法习题答案 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 #include 操作系统上机测试作业调度算法算法 一、实验目的和要求（供参考） 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 操作系统 ——项目文档报告 进程调度算法 专业： 班级： 指导教师： 姓名： 学号： 一、核心算法思想 1.先来先服务调度算法 先来先服务调度算法是一种最简单的调度算法，该算法既可以用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将他们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。 2.短作业（进程）优先调度算法 短作业（进程）优先调度算法SJ（P）F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。SJ(P)F调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。该算法对长作业不利，完全未考虑作业的紧迫程度。 3.高响应比优先调度算法 在批处理系统中，短作业优先算法是一种比较好的算法，其主要不足之处是长作业的运行得不到保证。如果我们能为每个作业引人动态优先权，并使作业的优先级随着等待时间的增加而以速率a提高，则长作业在等待一定的时间后，必然有机会分配到处理机。该优先权的变化规律可描述为: 优先权=（等待时间+要求服务时间）/要求服务时间 即优先权=响应时间/要求服务时间 如果作业的等待时间相同，则要求服务的时间越短，其优先权越高，因而该算法有利于短作业。 当要球服务的时间相同时，作业的优先权决定于其等待时间，等待时间越长，优先权越高，因而它实现的是先来先服务 对于长作业，作业的优先级可以随着等待时间的增加而提高，当其等待时间足够长时，其优先级便可以升到很高，从而也可获得处理机。 4.时间片轮转算法 在时间片轮转算法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，由一个计数器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。 二、核心算法流程图 #include cout<<"请输入提出磁盘I/O申请的进程数:"; cin>>N; cout<<"请依次输入要访问的磁道号："; for(int i=0;i 一、目得与要求?进程调度就是处理机管理得核心内容。本实验要求用高级语言编写模拟进程调度程序,以便加深理解有关进程控制快、进程队列等概念，并体会与了解优先数算法与时间片轮转算法得具体实施办法。 二、实验内容 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. 实验名称 磁盘调度算法 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函数流程图 题目操作系统课程设计 实验一：进程调度算法 1.实验目的 通过优先权法和轮转算法的模拟加深对进程概念和进程调度过程的理解，掌握进程状态之间的切换，同时掌握进程调度算法的实现方法和技巧。2.实验内容 1）用C语言或C++语言来实现对n个进程采用优先权算法以及轮转算法的进程调度。 2）每个用来标识进程的进程控制块PCB用结构来描述，包括以下字段：（1）进程标识ID，其中0为闲逛进程，用户进程标识数为1，2，3…。 （2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，标识数越大，优先级越高。 （3）进程占用CPU时间CPUtime，进程每运行一次，累计值等于4. （4）进程总共需要运行时间Alltime，利用随机函数产生。 （5）进程状态，0-就绪态；1-运行态；2-阻塞态。 （6）队列指针next，用来将多个进程控制块PCB链接为队列。 3）优先数改变的原则 （1）进程在就绪队列中每呆一个时间片，优先数增加1。 （2）进程每运行一个时间片，优先数减3. 4）在调度前，系统中拥有的进程数PCB_number由键盘输入，经初始化后，所有的进程控制块PCB链接成就绪队列。 3.实验步骤 a)画出程序流程图 a)动态优先权的进程调度算法模拟流程 b)轮转法进程调度算法模拟流程 b)程序算法如下： #include "stdafx.h" #define NULL 0 #include 操作系统处理器调度算法C++程序
随机进程调度算法
进程调度算法实验报告
处理器调度习题
操作系统实验报告(进程调度算法)
进程调度算法实验报告
进程调度算法实验报告
操作系统+磁盘调度算法
进程模拟调度算法课程设计
几种操作系统调度算法
进程调度算法1
操作系统之调度算法和死锁中的银行家算法
进程调度C语言实现
操作系统作业调度算法
操作系统模拟进程调度算法
操作系统磁盘调度算法(C++)
时间片轮转算法和优先级调度算法 C语言模拟实现
操作系统实验第五讲磁盘调度算法
进程调度算法论文优先级调度~
相关主题
文本预览