学生实习报告 课程名称_ 数据结构与数据处理应用训练 题目名称多级反馈队列调度算法的实现 学生学院计算机与计算科学 专业班级 学号 学生姓名 指导教师 2012年 2月 16 日 多级反馈队列调度算法的实现 【摘要】 多级反馈队列调度算法是操作系统中CPU处理机调度算法之一，该算法既能使高优先级的进程（任务）得到响应又能使短进程（任务）迅速完成。UNIX操作系统便采取这种算法，而本次试验就是试用C语言模拟某多级反馈队列调度算法。本次试验中前三级就绪队列采用时间片轮转法，时间片大小分别为2、4和8，最后一级就绪队列采用FIFO调度，将任务进入多级队列进行模拟，任务从优先级高的队列到优先级地的队列的顺序逐一进入，还用了算法支持抢占式，最后完成模拟，得到各个任务先后完成的顺序，还有得到各个任务的响应时间、离开时间、周转时间。 【关键词】队列优先级任务时间 1 内容与要求 【内容】 多级反馈队列调度算法是操作系统中CPU处理机调度算法之一，该算法既能使高优先级的进程（任务）得到响应又能使短进程（任务）迅速完成。UNIX操作系统便采取这种算法，本次试验就是试用C语言模拟某多级反馈队列调度算法，通过输入任务号、到达时间、运行时间，求出任务完成的先后顺序以及各个任务
的响应时间、离开时间、周转时间。 【要求】 多级反馈队列调度算法描述： 1、该调度算法设置四级就绪队列：前三级就绪队列采用时间片轮转法，时间片大小分别为 2、4和8；最后一级就绪队列采用FIFO调度。 2、任务在进入待调度的队列等待时，首先进入优先级最高的队列等待。 3、首先调度优先级高的队列中的任务。若高优先级中队列中已没有调度的任务，则调度次优先级队列中的任务，依次类推。 4、对于同一个队列中的各个任务，按照队列指定调度方法调度。每次任务调度执行后，若没有完成任务，就被降到下一个低优先级队列中。 5、在低优先级的队列中的任务在运行时，又有新到达的任务，CPU马上分配给新到达的任务。（注：与原来的题目不同，原题是在低优先级的队列中的任务在运行时，又有新到达的任务时，要在运行完这个时间片后，CPU马上分配给新到达的任务，而本题不需要在运行完这个时间片，即正在进行的任务立刻停止，CPU 马上分配给新到达的任务） 6、为方便实现，时间以1为单位，用整数数据表示；且每个时间点，最多只有一个任务请求服务（即输入）。 2 总体设计 算法总体思路： 这是建立在一个时间轴上的，即时刻，一个一个时刻（时间点）进行。 2.1.1 主函数思路：
2008年2月 February 2008 —28— 计 算 机 工 程Computer Engineering 第34卷 第4期 Vol.34 No.4 ·博士论文· 文章编号：1000—3428(2008)04—0028—03 文献标识码：A 中图分类号：TP391 一种新的加权公平队列调度算法 尹德斌，谢剑英 (上海交通大学自动化系，上海 200240) 摘 要：传统公平队列调度算法(WFQ 、WRR 等)普遍存在基于数据包的权重参数计算问题，由此产生的高复杂度使其难以获得广泛应用。该文提出一种新的加权公平队列调度算法，使用服务概率和随机数实现加权公平调度，显著降低了算法的复杂度。同时使用自适应服务概率计算解决了数据包变长度带来的不公平性。通过队列管理技术有效地提高了交换机的缓冲区利用率，并减小了排队延迟抖动。仿真结果证明了算法的有效性和实用性。 关键词: 队列调度；加权公平排队；自适应队列管理；分组交换网络 New Weighted Fair Queue Scheduling Algorithm YIN De-bin, XIE Jian-ying (Department of Automation, Shanghai Jiaotong University, Shanghai 200240) 【Abstract 】Traditional weighted fair queue algorithms have the main drawback: the calculation of the weight parameters according to each packet.The paper proposes a new weighted fair queueing algorithm(SPFQ), which uses service probability to schedule packets and a random number to decide which packet to be served next. In addition, a novel adaptive service probability parameter calculation method is used to solve the unfair problem induced by the variable packet length and an adaptive queue management technology to improve the utilization of the server's queue buffer and reduce the delay burstiness. Simulation results demonstrate the validity and practicability of SPFQ. 【Key words 】queue scheduling; weighted fair queueing; adaptive queue management; packet switching network 1 概述 队列调度是当前互联网技术领域的一个研究热点。其中，加权公平队列调度算法由于能够根据各业务流的权重进行区分服务而受到广大研究者的广泛关注[1-9]。其中最著名的是加权公平WFQ [1]和加权轮询WRR [6]两类算法。WFQ 及其改进算法[3,5,7]都基于通用处理机共享模型[2]，使用虚时间(virtual time)进行数据包转发。WFQ 算法在业务流受漏斗约束的情况下可以提供精确的带宽保证和最大时延上限，并且数据包的转发不受其他业务流特性影响。但是它的计算复杂度太高。WRR [2,6]是另一类复杂度相对较低的常用加权队列调度算法；各业务流在一次轮询中所允许发送的数据包个数由队列权重决定。DRR [4]引入了差额计数器(dificit conter)，记录由数据包长度不同引起的服务量差。轮询类算法复杂度较低，但无法提供确定的带宽保证和时延上限。 国内的研究者近年来也提出了许多队列调度算法。文 献[8]针对SS 和BF 两种业务流，提出了一种对数自适应调度算法，但该算法对类内各业务流之间如何调度并没有说明，且不能提供公平服务和隔离特性。文献[9]提出了一种用于区分服务网络的虚时钟核心无状态队列调度算法，各数据包自身携带虚时钟状态信息，中心服务器根据虚时钟进行转发，但需要根据虚时钟将入队列数据包插入到转发队列中，这无疑是一项沉重的计算负担。另外，该算法并未考虑虚时钟清零问题。本文提出了一种新的加权队列调度算法SPFQ 。由于采用了指数移动平均算法和阀值触发的平均数据包长度更新，使得服务概率计算频度大大降低，从而显著降低了算法的复杂度。 2 SPFQ 队列调度算法 2.1 SPFQ 的基本原理 SPFQ 算法依据各业务流的平均数据包长度将它们的权重转换成归一化服务概率，通过该参数实现加权服务。为了降低算法的复杂度，系统采用事件触发方式计算队列的平均长度。在算法实现中，使用单独模块计算服务概率，以减轻调度器的负荷。 2.2 SPFQ 的结构 数据包分类器图1 SPFQ 算法结构 基金项目：国家自然科学基金资助项目(60572157)；国家“863”计划基金资助项目(2003AA123310) 作者简介：尹德斌(1978－)，男，博士，主研方向：包交换网络的队列调度和管理；谢剑英，教授、博士生导师 收稿日期：2007-03-10 E-mail ：yin_db@https://www.doczj.com/doc/8c27221.html,
#include
void input() {int i; printf("请输入进程数："); scanf("%d",&J); for(i=0;i
在多道程序环境下，主存中有着多个进程，其数目往往多过于处理机数目。这就要求系统能按某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行。 在OS中的调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法，目前存在的多种调度算法中，有的算法适用于作业电镀，有的算法适用于进程调度；但也有些调度算法即可用于作业调度，也可用于进程调度。 多级反馈队列调度算法是一种CPU处理机调度算法，它不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。 多级反馈队列调度算法的思想 设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片；第一个队列的优先级最高，进程所执行时间片最小。 新创建的进程挂到第一优先级的队列后，然后按FCFS 原则排队等待调度。当轮到其执行时，如它能在时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列后，……； 仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推……；新进程可抢占低级进程的处理机。 多级(假设为N级)反馈队列调度算法可以如下原理： 1、设有N个队列（Q1,Q2....QN），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一
样的。一般来说，优先级Priority(Q1) > Priority(Q2) > ... > Priority(QN)。怎么讲，位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高（也就是说，Q1中的作业一定要比Q2中的作业先被处理机调度），依次类推其它的队列。 2、对于某个特定的队列来说，里面是遵循时间片轮转法。也就是说，位于队列Q2中有N个作业，它们的运行时间是通过Q2这个队列所设定的时间片来确定的（为了便于理解，我们也可以认为特定队列中的作业的优先级是按照FCFS来调度的）。 3、各个队列的时间片是一样的吗？不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大(不需要考虑这个 问题)。 多级反馈队列调度算法描述： 1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。 2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。 3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1 队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。 4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。 我们来看一下该算法是如何运作的： 假设系统中有3个反馈队列Q1,Q2,Q3，时间片分别为2，4，8。 现在有3个作业J1,J2,J3分别在时间 0 ，1，3时刻到达。而它们所需要的CPU时间分别是3，2，1个时间片。 1、时刻0 J1到达。于是进入到队列1 ，运行1个时间片，时间片还未到，此时J2到达。 2、时刻1 J2到达。由于时间片仍然由J1掌控，于是等待。 J1在运行了1个时间片后，已经完成了在Q1中的 2个时间片的限制，于是J1置于Q2等待被调度。现在处理机分配给 J2。 3、时刻2 J1进入Q2等待调度，J2获得CPU开始运行。 4、时刻3 J3到达，由于J2的时间片未到，故J3在Q1等待调度，J1也在Q2等待调度。
实验名称：多级反馈队列调度 09091201丁奎荣 一、实验目的： 1、综合应用下列知识点设计并实现操作系统的进程调度，进程状态转换，多组级反馈队列进程调度算法。 2、加深理解操作系统进程调度的过程。 3、加深理解多级反馈队列进程调度算法。 二、实验内容： 1、采用一种熟悉的语言，编制程序，最好采用C/C++，界面设计可采用其它自己喜欢的语言。 2、采用多级反馈队列进程调度算法进行进程调度。 3、每个进程对应一个PCB。在PCB中包括进程标识符pid、进程的状态标志status、进程优先级priority、进程的队列指针next和表示进程生命周期的数据项life（在实际系统中不包括该项）。 4、创建进程时即创建一个PCB，各个进程的pid都是唯一的，pid时在1到100范围的一个整数。可以创建一个下标为1到100的布尔数组，“真”表示下标对应的进程号是空闲的，“假”表示下标对应的进程号已分配给某个进程。 5、进程状态status的取值为“就绪ready”或“运行run”，刚创建时，状态为“ready”。被进程调度程序选中后变为“run”。 6、进程优先级priority是0到49范围内的一个随机整数。 7、生命周期life是1到5范围内的一个随机整数。 8、初始化时，创建一个邻接表，包含50各就绪队列，各就绪队列的进程优先级priority分别是0到49。 9、为了模拟用户动态提交任务的过程，要求动态创建进程。进入进程调度循环后，每次按ctrl+f即动态创建一个过程，然后将该PCB插入就绪队列中。按ctrl+q 退出进程调度循环。 10、在进程调度循环中，每次选择优先级最大的就绪进程来执行。将其状态从就绪变为运行，通过延时一段时间来模拟该进程执行一个时间片的过程，然后优先级减半，生命周期减一。设计图形用户界面GUI，在窗口中显示该进程和其他所
第三章 作业讲解 1、有5个作业进入就绪队列等待运行，预计它们的运行时间分别为9、6、3、5与X ，它们以什么样的调度顺序运行时会取得最小的响应时间？（答案与X 值有关） 答：短作业优先调度算法是使响应时间最小的调度算法： 0 < X ≤ 3时，调度顺序为： X 、3、5、6、9 3 < X ≤ 5时，调度顺序为： 3、X 、5、6、9 5 < X ≤ 6时，调度顺序为： 3、5、X 、6、9 6 < X ≤ 9时，调度顺序为： 3、5、6、X 、9 X > 9时，调度顺序为： 3、5、6、9、X 2、假设一个系统中有4个进程，它们的到达时间和服务时间如表所示，忽略I/O 以及其他开销时间，若分别按先来先服务（FCFS ）、非抢占及抢占的短进程优先（SPF ）、高响应比优先（HRRN ）、时间片轮转（RR ，时间片=1）、多级反馈队列调度算法（FB ，第i 级队列的时间片=2i-1）进行CPU 调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。 算法 时间 进程 平均时间 A B C D FCFS 完成时间 周转时间 带权周转时间 5 5 1 7 6 3 16 13 1.44 23 1 7 2.43 10.25 1.97 SPF （非抢占） 完成时间 周转时间 带权周转时间 5 5 1 7 6 3 23 20 2.22 14 8 1.14 9.75 1.835 SPF （抢占） 完成时间 周转时间 带权周转时间 7 7 1.4 3 2 1 23 20 2.22 14 8 1.14 9.25 1.435 HRRN 完成时间 周转时间 带权周转时间 5 5 1 7 6 3 16 13 1.44 23 17 2.43 10.25 1.97 RR （q=1） 完成时间 周转时间 带权周转时间 12 12 2.4 4 3 1.5 23 20 2.22 22 16 2.29 12.75 2.1 FB （q=2i-1） 完成时间 周转时间 带权周转时间 13 13 2.6 6 5 2.5 23 20 2.22 21 15 2.14 13.25 2.365 3、若有4个周期性任务，任务A 要求每30ms 执行一次，执行时间为15ms ；任务B 要求每50ms 执行一次，执行时间为5ms ；任务C 要求每50ms 执行一次，执行时间为15ms ；任务D 要求每100ms 执行一次，执行时间为10ms ，应如何按最低松弛度优先算法对它们进行CPU 调试？ （要求画出0-150ms 时段的调度时序图，并列出每次切换时每个任务的松弛度） 进程 到达时间 服务时间 A 0 5 B 1 2 C 3 9 D 6 7
操作系统原理 上 机 报 告 院系：计算机学院 [ 班级： 191094—16 姓名：熊金莲 学号： 768 二 O 一一年六月
— 一：银行家算法 实验目的： 1、了解并掌握银行家算法的思想； 2、通过编程实现银行家算法； 实验步骤： 1、安全状态：系统按照某种序列为多个进程分配资源直到最大需求，如果 能够保证所有进程全部顺利执行完毕，则称系统是安全的。 2、采取的数据结构 （1）可利用资源量Available （2）最大需求矩阵Max （3）分配矩阵Allocation[i] （4）需求矩阵Need[i] ￥ （5）请求矩阵Request[i] 3、银行家算法 设request：是Pi进程的请求向量，当Pi发了资源请求后，系统按下述步骤检查： （1）如果Request[i]<= Need[i]，则转向步骤（2）； （2）若Request[i] <=Available，则转向步骤（3）； （3）系统试探性地把要求的资源分配给进程Pi，并修改以下数据结构的值：Available=Available-Request[i]； Allocation[i]= Allocation[i]+ Request[i]； Need[i]= Need[i]- Request[i]； （4）系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态，若安全，才正式将资源分配给Pi进程，完成本次分配；否则，试探性分配作废，恢复原来的资源分配状态，Pi进程进入等待状态。 4、安全性算法 ？ （1）设置两个向量：工作向量work，它表示系统可提供给进程继续运行所需的各类资源数目，执行安全性算法开始时，work初值=Available；finish表示系统是否有足够的资源分配给里程，使之运行完成，开始时，finish[i]=false；当有足够资源分配给进程时，令finish[i]=true； （2）从进程集合中找到满足下述条件的进程： finish[i]= false； Need[i] <= work；若找到执行（3），否则执行（4）； （3）当进程Pi获得资源后，顺序执行直到完成，并释放它的资源，执行：work= work+ Allocation[i]； finish[i]= true； go to step(2); （4）若所有进程的finish[i]= true，则系统处于安全状态，否则，处于不安
一、实验目的 多道程序系统中，当就绪进程数大于处理机数时，须按照某种策略决定哪些进程优先占用处理机。本实验模拟实现进程调度，以加深对进程概念和不同进程调度算法的理解。 二、实验环境 1．PC微机。 2．Windows 操作系统。 3．C/C++/VB等开发集成环境。 三、实验内容与步骤 编程实现如下进程调度算法： 1)时间片轮转调度算法：时间片长度在运行时可从键盘输入。 2)多级反馈队列调度算法：至少要有三个队列，第i+1队列进程运行的时间片是第i 队列的2倍。 3)高响应比优先调度算法：当调度响应比高的进程运行时，仍然是运行一个时间片， 而不是完全结束，刚运行的进程，其以前的等待时间清零。 实现提示： （1）PCB数据结构（参考） PCB 至少包括：进程标识符、进程名、到达时间、服务时间、等待时间、完成时间、响应比等（可根据不同的算法增减）。假设多个PCB 利用链接方式进行组织。 （2）主要功能模块（参考） ●进程初始化； ●显示初始化后进程的基本信息； ●时间片轮转调度算法； ●多级反馈队列调度算法； ●高响应比优先调度算法； 输入要求：可将进程初始化信息事先存入文件中，程序运行从文件中读取信息，避免从键盘输入速度慢且易出错。 输出要求：每种调度算法每次调度后应直观显示，进程调度的依据、各进程的各项参数。每种调度算法运行结束后，输出各个进程对应的完成时间、周转时间和带权周转时间，以及整体的平均带权周转时间。 四、实验结果与分析
（1）程序的框架说明 （2）各调度算法的设计思想 1、时间片轮转算法 该算法采取了非常公平的方式，即让就绪队列上的每个进程每次仅运行一个时间片。如果就绪队列上有N个进程，则每个进程每次大约都可获得1/N的处理机时间。时间片的大小对于系统性能有很大的影响。若选择很小的时间片，将有利于短作业，但意味着会频繁地执行进程调度和进程上下文的切换，这无疑会增加系统的开销。反之，若时间片选择得太长，且为使每个进程都能在一个时间片内完成，RR算法便退化为FCFS算法，无法满足短作业和交互式用户的需求。进程的切换时机体现出RR算法的特点。若一个进程在时间片还没结束时就已完成，此时立即激活调度程序，将它从执行队列中删除。若一个进程在时间片结束时还未运行完毕，则调度程序将把它送往就绪队列的末尾，等待下一次执行。 2、多级反馈队列调度算法 1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。 2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。 3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。 4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。 3、高响应比优先调度算法
QoS队列调度算法概述 作者：上传时间：2011-04-22 关键字：网络大爬虫4-QoS专题 文常慧锋 【摘要】本文概述了常用队列调度算法的实现机制，并在此基础上对比了基于理想流模型的WFQ队列算法与其他队列调度算法的公平性能。 【关键字】服务质量队列调度通用处理器共享加权公平队列 1. 引言 队列调度算法是实现网络QoS(Quality of Service，服务质量)控制的核心机制之一，是网络资源管理的重要内容，通过控制不同类型的分组对链路带宽的使用，使不同的数据流得到不同等级的服务。 通常调度算法的工作模式可以分为两种：工作保留模式(work-conserving)和非工作保留模式(non-work-conserving)。如果队列中有数据包等待发送服务器就工作的调度算法称为工作保留调度算法；如果队列中有数据包等待发送但服务器仍然处于空闲状态的调度算法称为非工作保留调度算法，例如，即使服务器处于空闲状态同时队列中有数据包等待发送，但是为了等待下一个高优先级的数据包服务器也会推迟当前数据包的传输，这种调度算法就属于非工作保留调度算法。当数据包的传输时间很短时，非工作保留调度算法几乎是不公平的。 调度算法的另一种分类方法是根据调度算法的内部结构来划分的，主要有两种：基于优先级分类的调度算法和基于帧结构的调度算法。在基于优先级的调度算法中有一个称为虚拟时间(virtual time)的全局变量。调度算法根据该变量为每个数据包计算一个时间戳，然后根据时间戳对数据包排序和调度。虚拟时钟，加权公平队列都属于这种结构。基于优先级的调度算法的实现复杂度取决于两个因素：更新优先级列表算法和选择最高优先级数据包算法的复杂度(至少是，其中是共享输出链路的队列数)和计算时间戳算法的复杂度(这主要取决于所采用的调度算法，加权公平队列(WFQ)的时间戳的计算复杂度为，虚拟时钟的计算复杂度只为O(1))。 在基于帧结构的调度算法中，时间被分为固定长度或可变长度的帧。每个数据流所能使用的带宽资源就是每一帧中所允许传输业务量的最大值。存储转发队列是帧长度固定的基于帧结构的调度算法，在这种结构中，如果一帧中数据流的业务量小于预留带宽，服务器就会空闲。加权循环队列，差额循环队列允许帧长度可变，同时，如果一个数据流的业务量小于预留带宽时，下一个数据流就可以提前被调度。基于帧结构的调度算法最大的优点是实现简单，成本低，最大的缺点是缺乏灵活性和扩展性。 2. 典型的调度算法简介 2.1先进先出队列(FIFO) FIFO队列是最简单的基于优先级的调度算法。在FIFO队列中数据包的时间戳就是数据包的到达时间。FIFO队列提供了基本的存储转发功能，也是目前因特网中使用最广泛的一种方式，它采用默认的排队方法，不需要配置。其优点是实现简单，成本低，缺点是不能提供
多级反馈队列调度算法C语言模拟实现 多级反馈队列调度算法： 1、设置多个就绪队列，并给队列赋予不同的优先级数，第一个最高，依次递减。 2、赋予各个队列中进程执行时间片的大小，优先级越高的队列，时间片越小。 3、当一个新进程进入内存后，首先将其放入一个对列末尾，如果在一个时间片 结束时尚未完成，将其转入第二队列末尾。 4、当一个进程从一个对列移至第n个队列后，便在第n个队列中采用时间片轮转执行完。 5、仅当时间片空闲时，才调度第二个队列中的进程。 (1~i-1)空闲时，才调度i，如果处理机正在第i队列中运行，又有新进程进入优先权较高 队列，则新进程抢占处理机，将正在运行的进程放入第i队列队尾，将处理机分给新进程。view plaincopy to clipboardprint? #include
多级反馈队列-实验-操作系统 以下是为大家整理的多级反馈队列-实验-操作系统的相关范文，本文关键词为多级,反馈,队列,实验,操作系统,实验,名称,多级,反馈,队，您可以从右上方搜索框检索更多相关文章，如果您觉得有用，请继续关注我们并推荐给您的好友，您可以在教育文库中查看更多范文。 实验名称：多级反馈队列调度09091201丁奎荣 一、实验目的： 1、综合应用下列知识点设计并实现操作系统的进程调度，进程
状态转换，多组级反馈队列进程调度算法。 2、加深理解操作系统进程调度的过程。 3、加深理解多级反馈队列进程调度算法。二、实验内容： 1、采用一种熟悉的语言，编制程序，最好采用c/c++，界面设计可采用其它自己喜欢的语言。 2、采用多级反馈队列进程调度算法进行进程调度。 3、每个进程对应一个pcb。在pcb中包括进程标识符pid、进程的状态标志status、进程优先级priority、进程的队列指针next和表示进程生命周期的数据项life（在实际系统中不包括该项）。 4、创建进程时即创建一个pcb，各个进程的pid都是唯一的，pid 时在1到100范围的一个整数。可以创建一个下标为1到100的布尔数组，“真”表示下标对应的进程号是空闲的，“假”表示下标对应的进程号已分配给某个进程。 5、进程状态status的取值为“就绪ready”或“运行run”，刚创建时，状态为“ready”。被进程调度程序选中后变为“run”。 6、进程优先级priority是0到49范围内的一个随机整数。 7、生命周期life是1到5范围内的一个随机整数。 8、初始化时，创建一个邻接表，包含50各就绪队列，各就绪队列的进程优先级priority分别是0到49。 9、为了模拟用户动态提交任务的过程，要求动态创建进程。进入进程调度循环后，每次按ctrl+f即动态创建一个过程，然后将该pcb 插入就绪队列中。按ctrl+q退出进程调度循环。
QoS能力 队列管理机制：队列管理控制机制通常指路由器拥塞管理机制以及队列调度算法。常见的方法有RED、WRED、WRR、DRR、WFQ、WF2Q等。 端口硬件队列数：通常路由器中所支持的优先级由端口硬件队列来保证。每个队列中的优先级由队列调度算法控制。QoS分类方式指路由器可以区分QoS所依据的信息。最简单的QoS分类可以基于端口。同样路由器也可以依据链路层优先级（802.1Q中规定）、上层内容（TOS字段、源地址、目的地址、源端口、目的端口等信息）来区分包优先级。 分类业务带宽保证 体现路由器是否能对各种业务等级作带宽保证。该指标可以由队列调度算法等方式实现。 RSVP ：RSVP是资源预留协议，用于端到端路径上资源的预留。使用软状态刷新，是流驱动工作方式。该协议一般不能在大规模全国范围网络上运行。但是通常路由器支持该协议，一些著名厂商使用该协议用于MPLS。 IP Diff Serv ：区分服务是对IP服务质量分级，是对QoS的一种简化。 CAR支持：CAR是指承诺接入速率，是一种接入控制。按照与用户签订的协议，对超出承诺速率的数据包做不同处理：丢弃或标记；又称为标记颜色。 PQ与WRR 当网络拥塞时，必须解决多个报文同时竞争使用资源的问题，通常采用队列调度加以解决。一般的情况下交换机会实现严格优先级（Strict-Priority Queue，简称PQ）调度、加权轮循（Weighted Round Robin，简称WRR）调度。 在队列调度时，PQ严格按照优先级从高到低的次序优先发送较高优先级队列中的分组，当较高优先级队列为空时，再发送较低优先级队列中的分组。PQ特别适合于对延迟、延迟抖动敏感的应用，采用优先级模式进行队列调度，可以让关键业务比如ERP、视频业务的报文进入最高优先级队列，保证在拥塞时总是优先获得转发服务。 WRR（Weighted Round Robin）队列调度将每个端口分为多个输出队列，队列之间轮流调度，保证每个队列都得到一定的服务时间，WRR可为每个队列配置一个加权值（依次为w3、w2、w1、w0），加权值
无线资源管理主要包括切换控制、功率控制、接入控制、负荷控制以及分组调度等方面的内容。 无线资源管理是3G系统无线网络控制器（RNC）的重要组成部分，其主要作用是负责空中接口资源的分配和使用，确保用户业务的服务质量、系统规划的覆盖区域以及提高系统容量。在3G的演进过程中，标准化组织3GPP和3GPP2也在不断完善和增强相关技术。对于分组调度算法，一方面要考虑到算法实现的复杂度，另一方面需要注意对系统性能指标的影响，如公平性、时延、业务的服务质量（QoS）等。目前采用比较多的调度算法主要有轮循调度、最大载干比调度、比例公平调度三种类型。 在分组通信中，为了获得统计复用增益，需要多个业务流共享带宽。因此，当多个用户争用资源时，就需要有一种机制来确定服务次序，有效地分配无线资源，这就是分组调度。由于无线信道时变特性、带宽资源有限和移动台功率受限等因素的影响，无线网络中的分组调度算法有别于有线网络。 调度器首先根据信道状态监视/预测模块提供的信道信息和用户的队列状态，依据一定的调度算法，计算出每个用户的优先级，然后根据优先级对用户数据排队，并分配无线资源，最后送到发射机。 1．Round Robin 轮叫调度（Round-Robin Scheduling） 狭义解释： 时间片轮转算法的基本思想是，系统将所有的就绪进程按先来先服务算法的原则，排成一个队列，每次调度时，系统把处理机分配给队列首进程，并让其执行一个时间片。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序根据这个请求停止该进程的运行，将它送到就绪队列的末尾，再把处理机分给就绪队列中新的队首进程，同时让它也执行一个时间片。 广义解释： 时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法是时间片调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，则CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，则CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，，当进程用完它的时间片后，它被移到队列的末尾。 时间片轮转调度中唯一有趣的一点是时间片的长度。从一个进程切换到另一个进程是需要一定时间的--保存和装入寄存器值及内存映像，更新各种表格和队列等。假如进程切换(process switch) - 有时称为上下文切换(context switch)，需要5毫秒，再假设时间片设为20毫秒，则在做完20毫秒有用的工作之后，CPU将花费5毫秒来进行进程切换。CPU 时间的20%被浪费在了管理开销上。 为了提高CPU效率，我们可以将时间片设为500毫秒。这时浪费的时间只有1%。但考虑在一个分时系统中，如果有十个交互用户几乎同时按下回车键，将发生什么情况？假设所有其他进程都用足它们的时间片的话，最后一个不幸的进程不得不等待5秒钟才获得运行机会。多数用户无法忍受一条简短命令要5秒钟才能做出响应。同样的问题在一台支持多道程序的个人计算机上也会发生。 结论可以归结如下：时间片设得太短会导致过多的进程切换，降低了CPU效率；而设得太长又可能引起对短的交互请求的响应变差。将时间片设为100毫秒通常是一个比较合理的折衷。 一,基本原理 在早期的时间片轮转法中,系统将所有的就绪进程按先来先服务的原则,排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片.时间片的大小从几ms到
今天先讲队列，因为中间两个知识点会用到队列的知识。 上图的三种延迟：进程延迟（路由器处理IP包、查找路由表）、队列延迟、传输延迟（与传输线路有关）。 思科路由器转发数据包的三种方式：Process Switching(进程交换)、Fash Switching（快速交换，也叫cache交换）、CEF(Cisco Express Forwarding)。 对于网络单元，当数据包到达的速度大于该接口传送数据包的速度时，在该接口处就会产生拥塞。如果没有足够的存储空间来保存这些数据包，它们其中的一部分就会丢失。数据包的丢失又可能会导致发送该数据包的主机或路由器因超时而重传此数据包，这将导致恶性循环。 对拥塞的管理，一般采用队列机制。当拥塞发生时，报文在路由器出口处按一定的策略入队；在调度时，再按照一定的策略决定报文出队发送的次序。 以下两张图是出现congestion的两种情况举例：
Transient：临时的；短暂的。Persistent：持续的。
在思科路由器上有软件队列和硬件队列之分。一个队列调度器调度下一个被转发的包的时候
不是直接移到出接口，而是把包从软件Q移到另外一个更小的FIFO队列中去，思科称为transimit Q（TX Q）或者transimit ring（TX Ring），这个更小的FIFO队列叫做hardware queue 硬件队列满的时候，有一些队列在软件Q中。此时硬件Q长度为4，不能被队列工具所控制。而软件Q中有之后的5、6、7个包，这三个包是可以被队列调度的，也就是我们通常说的软件队列调度机制是我们最经常操控的，而硬件Q不能被操控，即硬件队列先进先出。 加队也称插入，完成两项工作：1. 决定Queue能容纳多少包（即停车位容量）；2. Queue 满了之后，采取何种丢弃技术将后续的包丢弃。 调度也称服务策略，采用何种技术将包送入出接口的硬件队列。 注意：
调度算法总结 例：在下表中给出进程的到达时间、执行时间和优先级，请给出三种调度算法的进程执行次序和三种调度算法的平均周转时间。这三种调度算法是：短作业优先调度算法、优先级高者优先调度算法和简单轮转法调度算法(简单轮转法中的时间片为2个单位)。 一、先来先服务 先来先服务：按照进程进入就绪队列的先后次序进行选择。是最简单的调度方法。 1.进程运行顺序：P1→P2 →P3 →P4 →P5 2.进程平均运行时间： {（10-0）+（11-2）+（13-3）+（14-5）+（19-5）}/5=10.4 因为P1、P2、P3的到达时间依次递增，所以按照P1、P2、P3
的顺序依次执行；P4、P5的到达时间相同，但是P4的优先级比P5的高，所以先执行P4。 进程运行的分析图： 二、非剥夺的优先级调度算法 非剥夺的优先级调度算法：一旦某个高优先级的进程占有了处理机，就一直运行下去，直到由于自身的原因而主动让出处理机时（任务完成或等待事件）才让另一高优先级进程运行。 1.进程运行顺序：P1→P4 →P5 →P3→P2 2.进程平均运行时间： {（10-0）+（19-2）+（18-3）+（11-5）+（16-5）}/5=11.8 因为P1的到达时间是0s，所以P1占有了处理机，然后剩下的按照优先级的大小依次执行，它的顺序是：P4、P5、P3、P2.
三、可剥夺的优先级调度算法 可剥夺的优先级调度算法：任何时刻都严格按照高优先级进程在处理机上运行的原则进行进程的调度，或者说，在处理机上运行的进程永远是就绪进程队列中优先级最高的进程。 1.进程运行顺序：P1→P4→P1→P5→P3→P2 2.进程平均运行时间： {（11-0）+（19-2）+（18-3）+（6-5）+（16-5）}/5=11 因为P1到达时间是0s，所以先执行P1，经过2s后，P2到达，但是由于P2的优先级低于P1，所以仍由P1继续执行，同理P3也一样；但经过5s后，P4、P5到达，由于P4、P5优先级均高于P1，且P4优先级高于P5，所以先执行P4,等P4执行完以后，再执行P1，然后按照优先级顺序依次执行P5、P3、P2。
多队列ＶＣ调度算法研究 吴舜贤 刘衍珩 田明 吉林大学计算机科学与技术学院，吉林 长春 １３００１２ E-mail：wushxian@https://www.doczj.com/doc/8c27221.html, 摘 要 本文首先分析了ＶＣ和ＧＰＳ／ＰＧＰＳ分组调度算法的优点和缺点，在此基础上提出了一种具有ＧＰＳ调度算法特性的多队列ＶＣ调度算法ＭＱＶＣ。完整阐述了ＭＱＶＣ的设计目标、改进措施，并给出了ＭＱＶＣ算法模型和算法描述，通过定理和引理证明了该模型比单队列ＶＣ 和ＰＧＰＳ调度算法模型在实现复杂度、系统调度性能和包的丢失等方面的明显改善。网络仿真结果显示该算法具有良好的服务质量性能。 关键词 调度算法，虚拟时钟，ＭＱＶＣ，ＧＰＳ，服务质量。 中图分类号：TP393.02 文献标识码：A １引言 在高速路由器技术研究中，核心部分之一是路由器中分组调度算法研究[1]。通过对调度算法的综合比较[2]发现集成服务网络分组调度算法中，VC (Virtual Clock) [3，4]和GPS （Generalized Processor Sharing）/PGPS（Packet-by-packet Generalized Processor Sharing）[5]是两种比较典型的调度模型。 ＶＣ算法是一种基于ＴＤＭ的统计时分的服务模型。文献［６］认为ＶＣ调度算法是 “不公平”的，但文献［３，４，７，８］从理论和仿真结果表明它的有效性、可行性和优越性，认为ＶＣ算法是一种能够有效满足一定的服务速率保证、时延保证和流隔离监视的调度算法。相对于本文提出的算法模型，称原来的ＶＣ 算法为单队列ＶＣ调度算法。GPS调度算法是一种理想的绝对的基于流的公平队列算法，在现实条件下是不可实现的，对GPS的模拟演化出一系列调度算法，如WFQ[1]、PGPS[5]、WF2Q[9]、WF2Q+[10]、SFQ[11]等，其最大差异在于虚拟时间定义和调度条件选定。PGPS是GPS的一种较好的逼近模拟。当前对VC算法主要的改进研究有前跳虚拟时钟[12]、核心无状态虚拟时钟［１３］及基于虚拟时钟的接纳控制技术［１４］等。 本文针对VC及PGPS存在的缺点和不足，从改进算法效率和资源使用率角度对ＶＣ进行了改进，提出一种称为多队列的VC算法MQVC(Multi-Queued Virtual Clock)。 ２ VC 和GPS/PGPS调度算法分析 ＶＣ 算法和ＧＰＳ／ＰＧＰＳ算法在服务保证、系统效率等方面有许多相似，但又存在差异。 ＶＣ算法具有ＴＤＭ的优点和统计时分的灵活性，它以为每个流预留资源的形式在速率保证、时延保证和流之间的隔离上具有优越性能。但研究发现，ＶＣ调度算法也具有诸多不足：（１）ＶＣ算法只有一个分组缓存，缓存所有增序排列的数据分组。当有突发流时，突发分组会在短时间内占满所有缓存，使得其他流的分组具有较大延迟，甚至丢失；（２）对优 项目基金：吉林省自然科学技术基金(20030522-2) - 1 -