循环队列存储空间传统扩充与动态扩充之优劣

循环队列在定义时总是事先规定一个最大值MAXSIZE来确定队列的最大存储空间,在使用中若初始值MAXSIZE太小会造成存储空间不够用的问题。一般的做法是停止程序的执行,修改MAXSIZE的值。若MAXSIZE太大则会造成存储空间的浪费,不能实现动态扩充的目的。在此提出了一种新的实现循环队列存储空间动态扩充的方法,解决了存储空间不够用的问题,同时也成功地避免了循环队列中存储空间的浪费问题。最后比较了此方法与传统方法的优劣。     

Hadoop平台的多队列作业调度优化方法研究

对Hadoop平台的作业调度算法进行了研究, 提出了支持作业类型区分的多队列调度优化算法。优化算法支持根据节点当前的负载情况分配不同类型的作业, 以提高节点的资源利用率; 允许作业队列的资源在闲置时被其他作业队列占用; 在原作业队列需要时可以被即时回收, 即回收过程支持任务抢占; 采用共享队列列表和非共享队列列表的逻辑划分来防止乒乓效应。Hadoop平台的性能测试结果表明, 优化算法相比系统默认算法在作业调度的执行效率、执行平稳性等方面都有了显著的提升。     

动态增长型循环队列的实现

循环队列是为克服顺序队列“假上溢”现象，充分利用向量空间而提出并广泛应用。动态增长型循环队列是为反驳数据结构教材（严蔚敏著）中“在C语言中不能用动态分配的一维数组来实现循环队列”的论述而提出的。文中给出了一种具体实现方案并附以结果。     

uC/OS-Ⅲ外建消息队列及任务内建消息队列深度解析

在uC/OS-Ⅱ的基础上,uC/OS-Ⅲ对消息队列做了较大的改进,并新增一项特有的功能:任务内建消息队列。任务内建消息队列不仅可以降低消息队列占用的存储空间、提高消息与任务间的通信效率,还能实现消息与任务的相互一一对应,从而保证了系统的健壮性。     

基于队列计数的固态存储器热数据识别方法*

目前较常用的热数据识别方法主要关注于数据的访问频繁度,却没有有效地体现出访问次数随时间的变化关系,从而造成了较高的错误识别率。针对这种不足,设计了基于队列计数的热数据识别方法,通过使用先进先出规则淘汰过时的数据,并赋予队列中每个位置所存放元素不同的权值来表示不同时刻各数据的热状态;同时结合Flash读写等特性,引入了热区域概念,使其所需存储空间大大降低。通过理论分析以及实验证明,此方法在热数据识别和均衡效果方面达到了较好的性能,从而提高了垃圾回收的效率以及延长了存储器的使用寿命。     

循环队列中入队算法的研究

讨论了数据结构中循环队列入队算法的设计思想并提出了解决队列满时的可行方法,解决了数据结构教材中没有解决的问题。     

基于任务负载监测的高性能集群节点启停机制*

对高性能计算集群在运行过程中如何通过关闭闲置节点来实现有效节能的问题进行了研究和探讨,设计和实现了基于任务负载量统计监测的节点启停机制.根据对系统中作业运行和排队情况的记录和分析,通过参数估计设计了反映队列任务情况的负载因子,并围绕负载因子制定具体策略,结合作业系统的队列设置和资源分配规则,对集群中的空闲节点进行自动启停控制.模拟实验表明,基于任务负载监测的节点启停机制能够有效地自动启停系统中闲置的节点,从而降低系统功耗,并且对系统中作业的整体完成时间基本不造成影响.     

基于多队列自适应的DTN传染路由算法

传染路由是DTN中一类较简单的基本路由算法.针对DTN网络环境易变的特点及传染路由的不足提出多队列自适应传染路由,采用多队列方式管理存储空间,利用效用函数对队列内信息进行排序,针对不同队列及网络情况采用相异的转发机制,从而降低网络负载率、提高传输率并降低传输时延,同时可提供简单的QoS.仿真证明本算法优于路由算法Spray andw ait和MaxProp.     

栈与队列考题分析

栈和队列可以看作线性表的特例,它们都具有和线性表相同的存储方式,顺序存储和链式存储。栈有顺序栈和链式栈,队列有顺序队列和链式队列。基本知识(1)栈是受限的线性表,表现在它的插入和删除(进栈,出栈)操作只能在一端进行,因此它具有后进先出的特点(如图1所示);队列也是一种受限的线性表,它的插入(入队)操作在一端进行,而它的删除(出队)操作在必须在另一端进行,因此它具有先进先出的特点。(2)为了充分利用存储空间,产生了一种循环队列,也叫做环形队列。它的特点就是队列的首尾相连,分别有指向队首和队尾的指针,且它们由始至终只朝一个方向…     

对循环队列空与满条件的探讨

本文主要是讨论了计算机领域中的非常重要的学科《数据结构》中的线性结构—循环队列空与满条件。首先给出了线性结构中队列判断队列空和队列满的条件存在的问题,之后提出了相应的两种不同的方法:设立一个计数器或在循环队列中少用一个数据元素的空间,并约定对头指针在队尾指针的下一个位置上作为满的标志,这样就解决了前面所存在的问题。最后又讨论了第二种方法中队满和对空成立的条件有一个重要的前提,那就是初始化一个队列时的条件一定是:Q.front=Q.rear=0。     

嵌入式Linux实时性能设计与实现

提出在快速自愈路由协议与试验系统中使用的嵌人式实时操作系统的设计方案是采用修改内核的方法,将低延迟方案与抢占方案结合共同提高Linux内核抢占性能,并对调度进行了改进,将原Linux系统中只有一个可运行队列的方式改为对每一个实时优先级给出一个可运行进程队列,每一个运行队列有一个标志,表明该队列是否为空,系统中还有一个变量,变量的值为当前可运行进程的最高优先级,进程调度时,取优先级最高的可运行队列。     

基于事件空间划分的高效发布订阅路由算法*

传统的逆向路径转发的路由效率是O(N),基于事件空间划分的贪婪路由技术将效率提高到O(N1/d).在此基础上,采用祖先队列的路由数据结构,建立虚拟层叠网络中不同路由域之间的相邻关系,并通过祖先队列记录域间代理的相邻关系,实现了分层分路由域的代理之间的分级跨跳路由,称为Spanhop路由.通过性能分析表明,使用该路由算法,路由的平均路径减少到O(ln N),同时取消了事件空间维度d对路由效率的影响.这种方法通过增加少量的存储代价,提高了在大规模的面向广域网的发布订阅系统当中的路由效率.     

共享缓冲器在ATM交换中的应用

队列管理的设计是共享缓冲器ATM交换结构设计的关键，该文具体研究了共享缓冲器交换结构的队列管理，提出了循环队列管理，它能有效地实现共享缓冲器ATM交换列表操作。RQM减少了外部FIFO，需要的存储单元比传统的队列管理少而能实现相同的功能。利用连接列表的独立信元/地址内存实施方案，可去除气泡效应，充分利用缓冲器内存空间。     

Smart priority queue algorithms for self-optimizing event storage

Low run-time overhead, self-adapting storage policies for priority queues called smart priority queue (SPQ) techniques are developed and evaluated. The proposed SPQ policies employ a low-complexity linear queue for near-head activities and a rapid-indexing variable bin-width calendar queue for distant events. The SPQ configuration is determined by monitoring queue access behavior using cost-scoring factors and then applying heuristics to adjust the organization of the underlying data structures. To illustrate and evaluate the method, an SPQ-based scheduler for discrete event simulation has been implemented and was used to assess the resulting efficiency, components of access time, and queue usage distributions of the existing and proposed algorithms. Results indicate that optimizing storage to the spatial distribution of queue access can decrease HOLD operation cost between 25% and 250% over existing algorithms such as calendar queues.     

基于算子的栈序列生成算法与实现

提出一种使用算子解决堆栈问题的新算法。对出栈序列的产生和序列个数的统计做了探讨分析。新算法采用队列结构的存储方式取代了传统的栈存储方式来进行输出，比较有效地提高了栈序列生成的时间和空间复杂性。     

深空DTN多属性决策拥塞控制的研究

针对深空时延容忍网络(DTN)因节点存储空间有限造成的拥塞问题,提出了一种改进的多属性决策选择下一跳节点的策略。其基本思想是根据节点的存储空间占用率将节点状态划分成普通、半拥塞和拥塞三个状态,结合节点接收数据包的历史记录,在此基础上采用多属性决策理论选择最优的下一跳节点,从而达到预防拥塞的目的。仿真结果表明,与原策略相比,提出的策略在单个节点队列长度、平均队列长度、数据包接收率和数据包平均分发时间上有明显的改善,有效地缓解了网络拥塞。     

Just-in-time connectivity for large spiking networks

The scale of large neuronal network simulations is memory limited due to the need to store connectivity information: connectivity storage grows as the square of neuron number up to anatomically relevant limits. Using the NEURON simulator as a discrete-event simulator (no integration), we explored the consequences of avoiding the space costs of connectivity through regenerating connectivity parameters when needed: just in time after a presynaptic cell fires. We explored various strategies for automated generation of one or more of the basic static connectivity parameters: delays, postsynaptic cell identities, and weights, as well as run-time connectivity state: the event queue. Comparison of the JitCon implementation to NEURON's standard NetCon connectivity method showed substantial space savings, with associated run-time penalty. Although JitCon saved space by eliminating connectivity parameters, larger simulations were still memory limited due to growth of the synaptic event queue. We therefore designed a JitEvent algorithm that added items to the queue only when required: instead of alerting multiple postsynaptic cells, a spiking presynaptic cell posted a callback event at the shortest synaptic delay time. At the time of the callback, this same presynaptic cell directly notified the first postsynaptic cell and generated another self-callback for the next delay time. The JitEvent implementation yielded substantial additional time and space savings. We conclude that just-in-time strategies are necessary for very large network simulations but that a variety of alternative strategies should be considered whose optimality will depend on the characteristics of the simulation to be run.     

Evaluating disk idle behavior by leveraging disk schedulers

Disk idle behavior has a significant impact on the energy efficiency of disk storage systems. For example, accurately predicting or extending the idle length experienced by disks can generate more potential opportunities to save energy. This paper employs a trace driven simulation to evaluate the impacts of different disk schedulers and queue length thresholds on the disk idle behavior. Experimental results give three implications: (1) Position based schedulers and long queue length thresholds can significantly reduce the maximal queue length and the average queue length. (2) Position based schedulers and long queue length thresholds can generate more idle periods which are shorter than 1 s, but they do not affect those long idle periods contained in the modern server workloads. (3) Disk idle periods demonstrate both self-similarity and weak long-range dependence, and the disk schedulers and queue length thresholds do impact the Hurst parameter and the correlation behavior of the workloads. The analysis results in this paper provide useful insights for designing and implementing energy efficient policies for the disk drive based storage systems.