队列调度

今天先讲队列，因为中间两个知识点会用到队列的知识。

上图的三种延迟：进程延迟（路由器处理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 满了之后，采取何种丢弃技术将后续的包丢弃。

调度也称服务策略，采用何种技术将包送入出接口的硬件队列。

注意：

注意：上图在分类这一步，并没有采取措施（比如使用ACL）。FCFS即First-Come First-serve 在加队这一步，只有一个Queue，当Queue满了之后，对后续来包采取尾部丢弃法则。

在调度这一步，采取“first come，first serve”方式。

先入先出队列FIFO（First-In First-Out Queueing）——无通信优先权以及分类的概念。使用FIFO 时，数据包从接口的发送顺序依赖于数据包抵达这个接口的顺序，此时报文的入队顺序和报文的出队顺序相同。

FIFO 提供了基本的存储转发能力

上图，因为serial口默认带宽为1.544Mbps，如果想在serial口启用FIFO队列调度模式，可以在接口模式下配置指令no fair-queue。

上图，Ethernet接口默认采取FIFO，队列中可容纳的包的个数为40.

上图可见，串口默认采取WRQ队列调度模式，入口缓存最多75个包，出口缓存最多40个包。

上图中的指令可用来修改FIFO队列中可容纳的包的个数，具体数量和设备的性能有关系。

in 和out两个方向的含义：如上图，路由器S0端口上的队列，可能是出口队列也可能是入口队列，虽然通常是在出口队列上执行调度。

上图指令修改接口的input queue和out queue最多分别可以缓存200和100个包。

注意：Starvation：饿死。Jitter：抖动。Monopolize：独占。例如：ftp流量可能独占link。

Pre-emptive：优先购买的，先发制人的。

优先权队列方式PQ（Priority Queueing）——PQ 方式可根据报文头中的多个域（报文长度、源地址/目的地址等）及数据流的入接口等灵活地指定报文进入哪个优先级队列（可分为4 个等级的队列，即High、Medium、Normal、Low ），属于高等级优先队列的数据包可比低等级低的数据包优先发送，它确保了最重要的数据能得到最快速地处理。

PQ默认的优先级队列为Normal。

当某一个Queue满了之后，对于后续到来的包，仍然采取尾部丢弃法则。

Insertion policy即（入）队列机制。

配置举例如下：

上图定义了telnet流量具有high优先级，1是编号。

注意上图，high后面并没有参数可以指定协议类型（如：ICMP协议的协议号是1，TCP的协议号是6），但是有参数list，即可以指定一条acl来匹配ICMP数据流。

配置如下：

R1（config）#priority-list 1 protocal ip low list 100

R1（config）#access-list 100 permit icmp any any

接下来配置“调度”，即将priority-list绑定到哪个接口上，注意Qos通常定义在“出接口”！

查看：show inter serial 0/1

上图的数值为四种优先级队列默认允许最大占包数，默认分别为20/40/60/80。

上图，priority-list 1的配置，将telnet放入high队列，将icmp放入low队列。

下面来测试一下，通过在R1上执行指令“debug priority”查看，如下：

在R1上ping 13.1.1.3，如下：

在R1上telnet 13.1.1.3，如下：

PQ缺点：

1.对单一子队列而言，会继承FIFO队列的所有缺点。

2.对低优先级的数据流而言，可能会被“饿死”，因为只有高优先级队列里有数据，PQ就不会服务低优先级队列。

3.需要在每一跳（沿途每一台路由器）上都手工的配置分类。

注意：上图配置在入接口上（基于接口配置PQ），即从该接口进入的数据流都分配high priority。其余未做分类的流进入默认的队列，默认进入normal队列。

上图，PQ的第一条缺点，PQ仅有四种优先级队列，对于所有的数据流来说，分类有些少，这样导致大部分流进入normal或low优先级队列中，而在单一队列中，又遵守先进先出原则。

PQ的第三条缺点，假如对于语音流配置High优先级，需要在每一台路由器上做同样的配置。

上图：CQ在16个队列中“轮询调度”，体现了公平原则，每个Queue默认容纳的包大小为1500字节（每个queue默认容纳的包数目为20），同样采取“尾部丢弃”法则。

其实是16+1个队列（0-16），其中，queue 0为系统队列，它拥有绝对的优先权，分给控制类报文，如ospf hello包。

CQ可以基于两个参数控制queue：1. 限制每个queue最多可容纳的包数（默认20）。2.限制每个queue最多可容纳的字节数（默认1500 Bytes）。

上图：在每一轮循环调度过程中，每一个队列只允许发送一定数量的字节数（可配）。

上图，如果进入队列的第一个包大小为1499字节，第二个经过调度后进入队列的包大小为1500字节，根据路由器的默认规定，依然可以传送这个1500字节大小的数据包。但是，如果此时有第三个包到来，则不允许进入队列。

上图，将telnet数据流调度进入队列2，将icmp数据流调度进入队列3.

Show inter s/1如下：

上图，因为CQ默认采用RR的调度算法，所以每一个队列的max值都相同，默认20（队列中允许存在的包的最大数目）。

注意：缺省使用队列为1。CQ使用了17个子队列(其中0子队列是PQ队列，优先级很高，留给系统使用)。

CQ可以基于两个参数控制queue：1. 限制每个queue最多可容纳的包数（默认20）。2.限制每个queue最多可容纳的字节数（默认1500 Bytes）。

R1(config)#queue-list 1 queue 2 limit 40

RR的改进版是WRR(Weighted Round-Robin)，WRR允许用户为每个队列分配一个权值，根据这个权值，每个队列都能获得一定的接口带宽。

在CQ 中，权值就是一次轮循中可以转发的字节数。如上图所示，队列2的权值更高。

CQ使用了17个子队列(其中0子队列是PQ队列，优先级很高，留给系统使用)，可以把CQ 看成是PQ+CQ。

即：0队列是PQ队列，实际上可以把其他队列也设置成PQ队列：可以通过以下命令来设置：

queue-list list-number lowest-custom queue-number

比如命令：queue-list 1 lowest-custom 3

说明：0，1，2都是PQ队列（0队列总是最优），3以及3以上编号的队列都是CQ队列，按照Round Robin轮询。

r2(config)#access-list 101 permit ip any any precedence 5

r2(config)#queue-list 16 protocol ip 1 list 101 //把ACL101定义的数据流映射到子队列1中// r2(config)#queue-list 16 queue 1 limit 40 //设置子队列1的队列深度为40个数据包//

r2(config)#queue-list 16 lowest-custom 2 //设置queue 0,1为优先级队列PQ，其余的为CQ// r2(config)#queue-list 16 interface s0/0 2 //把s0/0接口进入的流量映射到子队列2中//

r2(config)#queue-list 16 queue 2 byte-count 3000 //设置子队列2在一个轮循内可以传输

QoS的队列和拥塞控制

QoS的队列和拥塞控制 传统ip网受人诟病的要害一点是其QoS能力，其实经过众多厂商长时间的努力，IP技术的QoS已经有了长足的进步。 一、队列策略 队列调度策略是QOS中针对接收报文和发送报文，按一定优先级策略调度入队和发送， 从而保障特定内容的报文，按需发送的机制。它的特点是只在设备内部实现，没有互通性要 求，不同厂家的设备可能队列调度策略实现不同，但不存在互通问题。 有四种队列机制：FIFO、PQ、CQ、WFQ 1、FIFO是传统的先入先出队列，没有策略。 2、PQ PR eference Queue，优先级队列。共四个优先级：High、Medium、Normal、Low。接口上根据协议类型、报文大小、协议端口号等，划分不同优先级队列，当高优先级队列中有报文时，低优先级队列得不到调度。所以优先级队列适用于应用简单，对某些应用服务要求很高，而其他业务相对不高的应用。它的优势是配置简单，绝对保证高优先级应用的带宽；缺点是不能保证高优先级外的服务得到合理带宽，从而不能公平地保证各种应用的服务质量。

3、CQ Customized Queue，用户定制队列。接口上，根据用户预先的定义，最多可配置16个定制队列，加上1个系统队列，共17个队列。用户可根据协议类型、报文大小、协议端口号，以及相应的access List规则，配置各种队列以及分配相应带宽，各个队列按照预先设定的带宽调度发送。CQ的优点是能保证各种应用能分配到一定的带宽，适用于应用相对简单的场合（如金融等专网），并且调度算法相对简单，路由器转发效率较高；缺点是配置相对复杂，并且网络治理员必须事先知道该网络的具体应用，对于治理员要求较高，对于复杂应用网络，16个优先级似乎不够。 4、WFQ

轮询调度

RR（轮询调度） Round-Robin，轮询调度，通信中信道调度的一种策略，该调度策略使用户轮流使用共享资源，不会考虑瞬时信道条件。 中文名轮询调度 外文名RR 性质通信中信道调度的策略 其他最大载干比调度和（PF）调度 RR简介 Round-Robin，轮询调度，通信中信道调度的一种策略，该调度策略使用户轮流使用共享资源，不会考虑瞬时信道条件。从相同数量无线资源（相同调度时间段）被分配给每条通信链路的角度讲，轮询调度可以被视为公平调度。然而，从提供相同服务质量给所有通信链路的角度而言，轮询调度是不公平的，此时，必须为带有较差信道条件的通信链路分配更多无线资源（更多时间）。此外，由于轮询调度在调度过程中不考虑瞬时信道条件，因此它将导致较低的整体系统性能，但与最大载干比调度相比，在各通信链路间具有更为均衡的服务质量。 队列调度算法的公平性、分组排队时延等性能是影响路由设备QoS特性的中央因素。队列调度算法可用循环调度（RR，Round Robin）等算法。 传统的轮询算法对不同的分组业务流队列进行同样的无差别的循环调度服务，这样的调度方式对于等长业务流队列是公平的，但是互联网的业务流是由不定长分组流构成的，因此不同的队列就可能具有不同的分组长度，结果分组长度大的业务流队列将可能会比分组长度小的业务流队列接收更多的服务，是队列之间产生不公平的现象；而且，这种算法也无法事先对业务需要的时延保证。 RR分类 为了改进RR算法的时延特性和其在变长分组环境下的不公平性，人们又提出了一些改进算法，如加权轮询（WRR，Weight RR），差额轮询（DRR，Defict RR），紧急轮询（URR，Urgency-based RR）。这些算法都力图在尽量保持RR算法实现简单性的同时，从不同的方面改进RR算法的时延特性和其在可变长分组环境下的不公平性。 RRWRR WRR也是周而复始地轮询分组业务流队列，但不同的是WRR算法为每个业务流队列分配一个权值，当轮询到某个业务流队列时，将根据它所具有权值的大小决定其可转发分组

4.QoS队列调度算法概述

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队列提供了基本的存储转发功能，也是目前因特网中使用最广泛的一种方式，它采用默认的排队方法，不需要配置。其优点是实现简单，成本低，缺点是不能提供

任务调度机制

ucos:uc/os 任务调度机制 疯狂代码 https://www.wendangku.net/doc/cc14674030.html,/ ?: http:/https://www.wendangku.net/doc/cc14674030.html,/NetworkProgramming/Article33556.html uc/os 任务调度机制 by zhang9733 from https://www.wendangku.net/doc/cc14674030.html,/gd/dzbbs/ 内核核心任务是任务调度机制为了对uc/os进行分析我们从任务调度开始在uc/os中个任务通常是个无限循环具有如下结构后面我将解释为什么会有这种结构从下面结构可以看出个任务就像其他c样；而且既然任务是个无限循环我们可以想象到它定不会返回任何数据所以返回类型应该定义为void ： ------------------------------------------------------------ void mytask(void *pdata) { for (;;) { do something; waiting; do something; } } uc/os可以管理64个任务但目前版本系统占用了两个任务还保留了其他六个任务故用户可以使用56个任务每个任务必须赋予定优先级优先级数越高优先级越低所以0级优先级任务有最高优先级通过在os_cfg.h文件中定义宏os_lowest_prio可以决定系统任务个数系统目前占用两个任务为空闲任务idle task和统计任务stat task当没有其他任务进入就绪状态时空闲任务投入运行空闲任务什么也不做只是简单将计数器加1这个计数器可以用来统计cpu利用率 uc/os下每个任务可以有如下五种状态 休眠态(dormant)：指任务驻留在空间中还没有交给内核管理把任务交给内核是通过ostaskcreate( )或ostaskcreatext( )实现 就绪(ready)：当任务旦建立这个任务就处于就绪态准备运行任务可以动态被另个建立也可以在系统运行开始之前建立通过ostaskdel( )使任务返回到休眠态就绪态任务都放在就绪列表中在任务调度时指针ostcbhighrdy指向优先级最高就绪任务也就是立刻就要运行任务 运行(running)：准备就绪最高优先级任务获得cpu控制权从而处于运行态指针ostcbcur指向正在运行任务

LTE调度机制

LTE调度机制 1概述 LTE的无线资源调度功能位于eNodeB的MAC子层。无线资源调度时eNodeB 的一项核心功能，目的是决定哪些用户可以得到何种资源，即决定每个用户使用的时频资源、NCS、SISO/MIMO等。 无线资源调度由eNodeB中的动态资源调度器实现。动态资源调度器为下行共享信道（DL-SCH）和上行共享信道（UL-SCH）分配物理层资源。DL-SCH和UL-SCH 分别使用不同的调度器进行调度操作。 对UL-SCH上的传输进行授权时，其授权时针对每个UE的，而没有针对每个UE的每个RB的资源授权（Only "per UE" grants are used to grant the right to transmit on the UL-SCH. There are no "per UE per RB" grants）。 动态资源调度器需要根据上下行信道的无线链路状态来进行资源分配，而无限链路状态是根据eNodeB和UE上报的测量结果进行判定的。分配的无线资源包含物理资源块的数量、物理资源块的位置以及调制编码方案MCS。 2基本的调度操作 LTE可以实现时域、频域和码域资源的动态调度和分配。动态调度带来的一个重要变化是LTE不再使用3G CDMA系统中“专用信道”来传送数据，而代之以“共享信道”，即不再为特定用户长时间地保留固定的资源，而是将用户的数据都分割成小块，然后依赖高效的调度机制将来自多个用户的“数据块”复用在一个共享的大的数据信道中。因此，LTE的性能能否充分发挥，很大程度上取决于调度机制的效率。一方面要根据无线信道的特性进行灵活地调度，另一方面又不能大幅度增加系统的信令开销。 频域资源调度是LTE系统资源调度的重要方法。在频域资源调度中，eNodeB 上的调度器根据上下行信道的CQI（信道质量指示）、QoS参数和测量、eNodeB 缓存中等待调度的负载量、在队列中等待的重传任务、UE能力（Capability）、UE 睡眠周期和测量间隔/测量周期、系统参数（如系统带宽/干扰水平/干扰结构）等信息，动态地为UE选择适合的RB进行上下行传输，并通过下行控制信令指示给UE。在上述信息中，CQI是资源调度最重要的考虑因素之一。 由于LTE系统中资源调度和链路自适应完全由eNodeB控制，因此上行信道CQI的测量值可以由eNodeB直接获取并使用，也不需要标准化；而下行信道的CQI值需要在UE侧获取，并由UE反馈给eNodeB。

调度策略

Windows CNC多任务调度策略 一般对于单CPU 的CNC系统，系统软件结构采用前后台式。前台程序承担几乎全部实时功能，后台程序用来完成准备工作和管理工作，任务的调度机制采用优先抢占调度与时间片轮转相结合的机制。 （1）优先抢占调度机制 为了满足CNC 实时任务的要求，系统的调度机制必须具有能根据外界的实时信息以足够快的速度（在系统规定的时间内）进行任务调度的能力。优先抢占调度机制就是能满足上述要求的调度技术，它是一种基于实时中断技术的任务调度机制。 优先抢占调度机制，其功能有两个： 1优先调度。在CPU 空闲时，当同时有多个任务请求执行时，优先级高的任务将优先得以满足。 2抢占方式。在CPU 正在执行某任务时，若另一优先级更高的任务请求执行，CPU 将立即终止正在执行的任务，转而响应优先级高的任务的请求。 优先抢占调度机制是由硬件和软件共同实现的，硬件主要提供支持中断功能的芯片和电路，如中断管理芯片（8259或功能相同的芯片），定时器计数器（8263、8294 等）。软件主要完成对硬件的初始化，任务优先级的定义方式、任务切换处理（断点的保护与恢复、中断向量的保存与恢复等）。 （2）时间片轮转调度机制 任务就绪队列往往按任务到达的时间来排序。任务调度程序总是选择就绪队列中的第一个任务，也就是说按照先来先服务的原则调度，即根据任务进入就绪队列的先后次序来占有CPU，一旦一任务占有CPU，它就一直运行下去，直到该任务完成其工作或因等待某事件而不能继续运行时才释放CPU，但一旦任务占有CPU 仅使用一个时间片。在使用完一个时间片后，任务还没有完成其运行，它也必须释放出（被抢占）CPU 给下一个就绪的任务。而被抢占的任务返回到就绪队列的末尾重新排队等候再次运行。 时间片的大小对系统运行的影响很大。如果时间片很大，大到一个任务足以完成其全部运行工作所需的时间，那么时间片轮转策略将退化为先来先服务策略了。如果时间片很小，那么CPU 在任务间的转接工作过于频繁，CPU 真正用于运行任务的时间将会减小。 （3）调度策略 1、确定任务优先级，突发性实时任务具有最高优先级。 2、为其它各任务分配执行周期。如位控为4ms，插补为8ms，预处理为16ms，背景程序为55ms。即在55ms时间片内，最先执行位控任务，位控任务完成后，接着执行插补任务，如果4ms 时间到，则插补将被终止，又开始执行位控，当位控执行完后，从刚才中断处接着执行插补，插补执行完后接着执行预处理，以此类推。 3、在背景程序中，各任务分配相同的优先权，当一个任务执行完后，就绪队列中最前头的任务占据CPU运行，而先前运行任务失去对CPU的控制退至队列尾，直到循环使其达到队头时才重新获得控制权，即按先来先服务的原则调度。 4、当突发性实时任务发生，如故障中断、机床PLC中断及其它异常发生时，当前正在运行的任务将立刻终止执行，系统保存现场环境后，立刻去响应突发性实时中断信号，在执行完突发

简析Windows系统的调度机制_2015011224

简析Windows系统的调度机制 电子系无51班赵少靖学号：2015011224 Windows系统的调度的粒度为线程，首先Windows为每一个线程分配调度优先级。调度根据优先级采用抢占式的调度策略，具有最高优先级的总是最先被执行。每一个线程都分配了一定的时间片，系统通过改变线程的状态来进行线程调度。 Windows系统使用32个优先级来表示线程要求执行的紧迫性，优先级用0 ~ 31的数字来表示。其中0优先级为内存页清零线程保留，1 ~ 15为可变优先级，16 ~ 31为实时优先级别。在应用创建线程时用户可以用形象的优先级描述来设置优先级，当创建进程时可以，可以赋予实时、高、高于一般、一般、低于一般和空闲的优先级别，当创建线程时可以在进程优先级的基础上进一步赋予尽量实时、最高、高于一般、一般、低于一般、最低和空闲的优先级别。处理器调度时参考两个优先级设置，一个是从当前线程所在进程的基准优先级，另一个是线程的优先级。一般来说，应用线程运行在可变优先级别1 ~ 15范围内，如果需要进入实时优先级别16 ~ 31范围内来运行，必须取得更高的调度优先级特权。Windows 操作系统只有一个内存页清零线程具有最低的调度优先级级别0，以便系统利用空闲时间对内存页清零。 在处理器进行线程调度的过程中，系统通过改变线程的状态对多个线程进行有效的管理。可以用下图来表示一个线程在调度过程中的可能的状态变迁：

初始态是一个线程刚被创建时的内部状态。就绪态表示一个线程已经准备就绪，等待运行。调度器查找到线程库中处于就绪状态的线程，来决定下一个运行的线程。预备态表示一个线程已经被选择作为下一个运行的线程，如果条件满足，调度器会根据上下文环境切换到该线程。但处于预备态的线程也可能会被转换到就绪态继续等待。当调度器将上下文环境切换到一个进程，该线程就处于运行态。当分配给线程的时间片或者具有更高优先级的线程抢占CPU时，它会让出处理器。如果一个线程需要等待资源，它会进入等待态，直达所等待的资源就绪。如果一个线程已经准备就绪，但运行它所需要的核心都在外存，它就会进入就绪挂起态，等待核心栈调入内存。当一个线程执行完后就会进入终止态，对象管理器会释放相应的执行程序块资源。 系统中同时有多个线程存在，而处理器一次只能运行一个线程。Windows通过调度数据库来为每一个优先级的线程维护一个就绪等待队列，当处理器需要调入一个线程运行的时候，系统会从调度数据库中找到一个具有最高优先级的就绪线程，并给它分配时间。如果等待队列中有线程比正在运行的线程优先级高，运行的线程就会保存它的上下文环境并进入就绪队列，高优先级的线程恢复它的上下文环境，并进入运行状态。当一个线程进入运行状态时，它就获得了一个可以运行的时间配额。时间配额用完后，调度器会查找调度数据库看是否有就绪的线程在等待，如果有就会将等待的线程运行，而将当前的线程转入等待或者就绪

NS中事件调度机制

NS中事件调度机制 (2009-12-16 16:53:57) 转载 标签： 事件度 最近研究NS2仿真工具，在学习源代码的过程中查看了一下NS2中的事件调度相关内容，对其流程有了一些粗浅认识，特分享如下。本人新手，以下内容有错误和不足之处恳请指教：） 1. 事件调度相关类简介 类结构如图1所示： 图1 NS2事件调度相关类结构图 重要类简介： 1)Handler类： 定义位置：~\Common\Scheduler[.h .cc] 作用概述： NS2中用于执行对事件的处理动作（在handle()方法中实现）； 作为Event类的属性，所有的事件都会保存用于处理自己的Handler，以供分派（dispatch）时使用； 属性/方法概述：

public virtual void handle(Event * event); 2)Event类： 定义位置：~\Common\Scheduler[.h .cc] 作用概述： 作为NS2事件调度机制的重要组成，是所有事件的父类（例如Packet类就是其子类）； 属性/方法概述： public Event* next_; //用于生成事件链表 public Event* prev_; public Handler* handler_; //用于记录该事件的处理器，也就记录了处理方法 3)NSObject类： 定义位置：~\Common\Object[.h .cc] 作用概述： 继承自Handler类(应该同时继承Handler类和TCLObject类），因此其子类可以作为参数传递给 Scheduler::schedule()方法，以便之后处理事件时调用其handle方法； 各种Connector类通常继承自此类； 属性/方法概述： protected void handle(Event* e); protected void recv(Packet *p, const char*); //直接调用Packet::free(p)； （介绍了上面三个类，接着就可以看看它们是被什么类使用、如何被使用的了） 4)Scheduler类： 定义位置：~\Common\Scheduler[.h .cc] 作用概述： 一个以时间为触发条件的离散事件调度器，NS2事件调度机制的基础； 完成事件的出/入队列、维护、分发等； 具有三个具体实现的子类（NS2通常默认为CalendarScheduler）； 属性/方法概述： public void schedule(Handler*, Event*, double delay) //代码摘录如下 { ...//判断参数有效性 e->uid_ = uid_++; e->handler_ = h; double t = clock_ + delay;

多级反馈队列调度

[操作系统] 多级反馈队列的调度 实验目标 1.理解有关进程控制块，进程队列的概念。 2.掌握进程多级反馈队列的调度的处理逻辑。 3.设计进程控制块PCB的结构，分别适用于多级反馈队列的调度。 4.建立进程就绪队列。 5.编制多级反馈队列的调度算法。 实验要求 用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解。设计思路 多级反馈队列 多级反馈队列原理 多级反馈队列调度算法又称反馈循环队列或多队列策略，主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。 具体描叙如下： ①OS设置有多个就绪队列（用qReadyi, i=1,2, ... ,n表示），用于存放等待处理的进程，每个队列的优先权（priority）各不相同，从第一个到最后一个依次降低； ②各个队列中进程执行的时间片大小各不相同，优先级越高的队列时间片越小，各个队列的时间片可按下面的规定：每一个队列时间片都比前一个队列时间片长1倍； ③当一个进程进入内存后，先放入第一队列qReady1末尾，按先来先响应的原则排队等待处理。该进程执行时若在规定的时间片内完成，则处理完毕，可撤离系统，若第一个时间片结束时尚未完成，则该进程转入第二队列qReady2的末尾排队等待处理，依次下去，直至转到最后一个队列中。 ④仅当第i个队列qReadyi为空，才能调度第i+1队列qReady (i+1)中的进程运行。如果第qReadyi队列中某进程正在执行，又有新进程进入第qReady1至qReady(i-1)中任何队列，则此时正在运行的进程放回第i队列末尾，运行新进程。 ●每个进程在输入时，需描述下面的特征：

H3C-QOS队列调度

S12500和S9500E流量整形配合队列调度的配置 一、组网需求： Switch A为企业的广域网出口，使用H3C S12500或S9500E设备。Switch A从下游连接接入层交换机的多个10G接口收到A、B、C三类访问广域网的业务流量。A类业务流量的源地址为192.168.1.0/24；B类业务流量的源地址为 192.168.2.0/24；C类业务流量的源地址为192.168.3.0/24。由于去往广域网的出口链路只有10G带宽，当这三类业务在这条10G链路上发生流量拥塞时需要对三类业务实施调度策略，合理分配不同业务所使用的带宽。 对这三类业务的带宽使用具体要求如下： 1）B类和C类流量最多各占用2G带宽，当B类或C类业务的流量不足2G时，A 类业务最多可占用8G带宽； 2）当发生拥塞时，B类和C类业务各保障2G带宽，A类业务保障6G带宽。 二、组网图： 三、配置步骤： 适用设备和版本：适用于S12500和S9500E的所有版本。 根据组网，首先明确拥塞可能发生的位置在Switch A连接广域网的出口 GE9/0/1。首先分析第一点需求，在没有发生拥塞时要限制某业务所使用的带宽上限，S12500和S9500E可选择的技术有流量监管（CAR，Committed Access Rate）和流量整形（GTS，Generic Traffic Shaping）。两者的主要区别在于：CAR是基于流来定义监管动作，CAR对于所监管的流量可以采取多种预先定义的动作，例如丢弃超出限制的流量或对符合带宽要求的流量重新标记优先级等。CAR在丢弃超标流量时不采用队列缓冲技术，直接丢弃。而GTS是基于队列来对流量整形，对于流量的处理原则比较简单，即对超出带宽限制的流量放入缓冲区队列，并丢弃超出队列长度的流量。

队列调度

今天先讲队列，因为中间两个知识点会用到队列的知识。 上图的三种延迟：进程延迟（路由器处理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 满了之后，采取何种丢弃技术将后续的包丢弃。 调度也称服务策略，采用何种技术将包送入出接口的硬件队列。 注意：

多队列VC调度算法研究

多队列ＶＣ调度算法研究　 吴舜贤　刘衍珩　田明 吉林大学计算机科学与技术学院，吉林　长春　１３００１２　 E-mail：wushxian@https://www.wendangku.net/doc/cc14674030.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 -

2.队列调度机制简介

队列调度机制简介 作者：| 上传时间：2011-04-22 | 关键字：网络大爬虫4-QoS专题 文/史计达 1 简介 队列调度机制在QoS技术体系中属于拥塞管理的范畴。虽然企业和运营商想尽一切办法 去扩展自己的链路带宽，但是现实网络上各种应用对带宽的消耗速度远远超出企业和运营商带宽扩充能力，也就是说网络的拥塞是无法避免的，这也决定了拥塞管理这一技术的重要性。拥塞管理是指网络发生拥塞时，如何进行管理和控制，处理的方法是使用合适的队列技术来确保关键业务的优先保障。在出接口发生拥塞时，通过适当的队列调度机制，可以优先保证某种类型的报文的QoS参数，例如带宽、时延、抖动等。我们这里所说的队列是指出队列，其实就是指向指定缓存的一系列指针，其作用是在接口有能力发送报文之前先将报文在缓存中保留下来，直到接口可以继续发送报文，所以队列调度机制都是在出端口发生拥塞情况下产生作用，另外一个主要作用就是将报文重新排序（FIFO除外）。 队列是一个比较容易理解的概念，我们在日常生活中也用到类似技术。例如我们去电影院买票的时候，大家排成几队顺序买票，排在前面的先拿到票（FIFO）；有时突然冲出一个人跑到队伍的最前面拿出VIP证件马上就拿到了票（PQ），这类人属于特权阶级需要优先处理，后面的人只能等这类人买完票才能继续排队买票。 2 FIFO FIFO是队列机制中最简单的，每个接口上只有一个FIFO队列，表面上看FIFO队列并没有提供什么QoS保证，甚至很多人认为FIFO严格意义上不算做一种队列技术，实则不然，FIFO 是其它队列的基础，FIFO也会影响到衡量QoS的关键指标：报文的丢弃、延时、抖动。既然只有一个队列，自然不需要考虑如何对报文进行复杂的流量分类，也不用考虑下一个报文怎么拿、拿多少的问题，即FIFO无需流分类、调度机制，而且因为按顺序取报文，FIFO 无需对报文重新排序。简化了这些实现其实也就提高了对报文时延的保证。 FIFO关心的就是队列长度问题，队列长度会影响到时延、抖动、丢包率。因为队列长度是有限的，有可能被填满，这就涉及到该机制的丢弃原则，FIFO使用Tail Drop机制。如果定义了较长的队列长度，那么队列不容易填满，被丢弃的报文也就少了，但是队列长度太长了会出现时延的问题，一般情况下时延的增加会导致抖动也增加；如果定义了较短的队列，时延的问题可以得到解决，但是发生Tail Drop的报文就变多了。类似的问题其它排队方法也存在。 Tail Drop机制简单的说就是如果该队列如果已经满了，那么后续进入的报文被丢弃，而没有什么机制来保证后续的报文可以挤掉已经在队列内的报文。