Stable Scheduling Policies for Maximizing Throughput in Generalized Constrained Queueing Systems

We consider a class of queueing networks referred to as "generalized constrained queueing networks" which form the basis of several different communication networks and information systems. These networks consist of a collection of queues such that only certain sets of queues can be concurrently served. Whenever a queue is served, the system receives a certain reward. Different rewards are obtained for serving different queues, and furthermore, the reward obtained for serving a queue depends on the set of concurrently served queues. We demonstrate that the dependence of the rewards on the schedules alter fundamental relations between performance metrics like throughput and stability. Specifically, maximizing the throughput is no longer equivalent to maximizing the stability region; we therefore need to maximize one subject to certain constraints on the other. Since stability is critical for bounding packet delays and buffer overflow, we focus on maximizing the throughput subject to stabilizing the system. We design provably optimal scheduling strategies that attain this goal by scheduling the queues for service based on the queue lengths and the rewards provided by different selections. The proposed scheduling strategies are however computationally complex. We subsequently develop techniques to reduce the complexity and yet attain the same throughput and stability region. We demonstrate that our framework is general enough to accommodate random rewards and random scheduling constraints.     

基于时间Petri网模型的缓冲优先调度策略稳定性分析

描述了一种时间Petri网模型和方法,它能对具有缓冲优先调度可重入生产线系统进 行稳定性分析.基于系统模型标识的动态变化,以缓冲界限概念作为稳定性分析判据.这种方法 可用于具有固定优先次序调度策略的稳定性分析.推导了基本时间Petri网结构的稳定特性以 及具有正反馈环系统稳定的充分条件.这些研究结果可以用于多种实际系统的稳定性分析.     

可重入生产系统的QBD型模型

考虑可重入生产系统除第一个外均为有限缓冲区的情形,建立了两种两站四缓冲区的 拟生灭过程(QBD)型模型.系统在随机调度策略下状态集是不可约的,而在最后一个缓冲区先 加工(LBFS)的策略下状态集是可约的.将可约的状态集化成不可约的吸收集和可约状态集的 和.求出了系统状态的稳态分布,给出了系统稳定的充要条件.     

三值光学计算机中运算请求调度

三值光学计算机具有很多数据位资源使得它能并行处理多个运算请求,因此运算请求的调度就成了三值光学计算机监控系统中不可避免的问题。定义了三值光学计算机中运算请求的四种不同状态,给出了其转换关系;讨论了动态表调度技术,提出了适合三值光学计算机监控系统的运算请求调度策略,如立即调度策略、定时调度策略和基于优先级的先到先服务策略。在此基础上提出了定时调度算法,分析了其特点。在监控系统中实现了该调度算法,并进行了相关实验。实验结果表明该调度算法可行且正确。     

时间轴法在操作系统作业调度算法教学中的应用

针对操作系统中的作业调度算法在教学过程中存在的模糊性、难理解性等问题,引入时间轴法,以“先来先服 务算法”和“计算时间短的作业优先算法”为例,对“时间轴法”在作业调度教学中的应用作了介绍,以时间演进顺序分析了何时 存在资源竞争、需要采用调度算法进行资源分配,在教学实践中取得了显著的效果。     

Opportunistic scheduling for streaming multimedia users in high-speed downlink packet access (HSDPA)

High-speed downlink packet access (HSDPA) achieves high data rates and high spectral efficiency by using adaptive modulation and coding schemes and employing multicode CDMA. In this paper, we present opportunistic algorithms for scheduling HSDPA users and selecting modulation/coding and multicode schemes that exploit channel and buffer variations to increase the probability of uninterrupted media play-out. First, we introduce a stochastic discrete event model for a HSDPA system. By employing the discrete event model, we transform the scheduling problem of providing uninterrupted play-out to a feasibility problem that considers two sets of stochastic quality-of-service (QoS) constraints: stability constraints and robustness constraints. A methodology for obtaining a feasible solution is then proposed by starting with a so-called stable algorithm that satisfies the stability QoS constraints. Next, we present stochastic approximation algorithms that adapt the parameters of the stable algorithm in a way that a feasible point for the robustness QoS is reached within the feasibility region of the stability QoS.     

I/O issues in a multimedia system

In future computer system design, I/O systems will have to support continuous media such as video and audio, whose system demands are different from those of data such as text. Multimedia computing requires us to focus on designing I/O systems that can handle real-time demands. Video- and audio-stream playback and teleconferencing are real-time applications with different I/O demands. We primarily consider playback applications which require guaranteed real-time I/O throughput. In a multimedia server, different service phases of a real-time request are disk, small computer systems interface (SCSI) bus, and processor scheduling. Additional service might be needed if the request must be satisfied across a local area network. We restrict ourselves to the support provided at the server, with special emphasis on two service phases: disk scheduling and SCSI bus contention. When requests have to be satisfied within deadlines, traditional real-time systems use scheduling algorithms such as earliest deadline first (EDF) and least slack time first. However, EDF makes the assumption that disks are preemptable, and the seek-time overheads of its strict real-time scheduling result in poor disk utilization. We can provide the constant data rate necessary for real-time requests in various ways that require trade-offs. We analyze how trade-offs that involve buffer space affect the performance of scheduling policies. We also show that deferred deadlines, which increase buffer requirements, improve system performance significantly     

Stability and performance of distributed production control methodsbased on continuous-flow models

Investigates the stability and performance of a two-level production control method for part release, routing, and machine scheduling in manufacturing systems. At the first level (off line), a continuous-flow (fluid) approximation of the production control problem is formulated and solved as a linear program. At the second level (on line), simple distributed control policies are used to track the solution of the continuous-flow model of level one. A major research issue concerns the potential instability of decentralized tracking policies due to the discreteness of the decision space (caused by the sequential nature of operations and their discrete processing times). The author considers a broad class of distributed tracking policies, which is called nonidling-nonexceeding (NINE) and finds a sufficient condition for their stability. The results show the NINE policies potential instability for nonacyclic systems due to machine starvation, which is caused by tracking delays induced by the discrete nature of operations. The sufficient stability condition takes a familiar form, namely that, the largest eigenvalue of a matrix-which captures the dynamics of tracking delays in the system-must be less than one. It ensures the contraction of tracking delays in the feedback loops of material flow in the system. When this condition is met, an upper bound on the performance of the policy is readily obtained. It is further shown that any nonidling dispatching policy can be considered as a special NINE policy, and thus the same stability and performance results apply to the class of all nonidling policies. The author also investigates NINE policies with buffer priorities and shows that a NINE policy with certain buffer priority ordering is always stable. Simulation experiments show that near-zero work-in-process and finished-parts' inventory can be achieved with the method even for demands that are very close to the production capacity of the system     

并行视频服务器调度算法研究

从服务器缓冲要求，客户端缓冲要求，系统响应时间三个方面着重分析比较了在服务器推动模型基础上建立的两种调度算法，并发推动调度算法和改进的并发推动调度算法，为我们进行相关的系统设计提供了理论依据．     

中厚板热轧生产调度优化方法

中厚板热轧生产调度, 是一个有优先约束、等待时间和缓冲容量有限的单机调度问题. 用AON (Activity-on-node)网络对问题进行描述, 提出并证明了面向单机调度问题的AON网络平衡定理, 根据平衡定理, 建立了以轧机利用率最大为优化目标的非线性约束优化数学模型, 并利用优化软件LINGO进行求解. 计算实例表明, 所提出的数学优化方法, 与现有的启发式方法相比, 能够获得更好的优化目标, 所得到的生产调度方案, 生产节奏稳定, 更有利于组织生产.     

基于关键链的资源受限项目调度新方法

针对资源受限项目调度问题（RCPSPs）的实际需求建立了多目标优化调度模型，综合运用现有研究成果，设计了基于关键链的项目调度方法。该方法首先采用基于优先规则的启发式算法生成工期最小的近优项目计划，再在该计划中嵌入输入缓冲和项目缓冲，保证项目计划在非确定环境下的稳定执行。论文引用RCPSPs的标准问题库PSPLIB中大量案例对算法进行了的仿真试验，结果表明本文方法较传统项目调度方法有很大改进，论文最后对仿真结果进行了深入讨论，并指出了未来的研究方向。     

A switched priority scheduling mechanism for ATM switches with multi-class output buffers

In this paper, we propose a switched priority scheduling mechanism for an Asynchronous Transfer Mode (ATM) switch with multi-class output buffers. The switched priority scheduling mechanism is composed of a model-based linear controller, a heuristic nonlinear controller and the corresponding switching law of the controllers. The nonlinear controller is first applied to bring each class buffer into a small neighborhood of its operating point such that the linear controller can be used. The linear controller is then used to ensure that each buffer occupancy converges to its desired operating point. The service rate of each class buffer is periodically computed and dynamically adjusted. We derive the design formulae of the control mechanism such that each buffer occupancy globally converges to its desired operating point related to quality-of-service requirements.     

Grouped sweeping scheduling for DASD-based multimedia storage management

This paper presents a new formulation of DASD (direct access storage device) disk arm scheduling schemes for multimedia storage management. The formulation, referred to as grouped sweeping scheduling (GSS), provides a framework for minimizing the buffer space required in the retrieval of multimedia streams. In GSS, the set ofn media streams that are to be served concurrently is divided intog groups. Groups are served in fixed order and streams within each group are served in an elevator-like SCAN scheme. Hence, the fixed order (FIFO) and SCAN schemes are special cases of GSS wheng=n andg=1, respectively. In this paper an optimization problem is formulated in which the buffer requirement is minimized with respect to the two design parameters:g and the size of the service unit, i.e. the number of blocks accessed in each service cycle. This formulation initially assumes that all media streams have the same playout requirements. A procedure of complexityO(1) is developed in computing the optimum solution to this problem. The proof of optimality and comparisons between the optimized GSS scheme and FIFO and SCAN are also presented. The paper also discusses the effect of disk arrays in the GSS formulation and issues related to operating GSS in a dynamic setting where streams arrive and depart in random order. Finally, the GSS scheme is extended to support heterogeneous media streams where each stream may have its own playout requirement.This paper extends earlier results that were presented at NOSDAV'92 [1] and Multimedia'93 [2].     

功率受限和自动重传请求条件下系统吞吐量最大化的研究

本文研究了具有ARQ功能的基于衰落信道和数据链路层缓冲区队列状态的资源最优分配问题，目标是通过自适应调整功率分配和调制方式，在系统平均功率的限制下，使系统的吞吐量达到最大。在这个系统中并不限制ARQ的重发次数，所以最大化系统的吞吐量等效于使链路层的缓冲区溢出的数据包最小。本文把这样一个优化问题构造为马尔可夫决策过程，并提出了用动态规划解决该问题的方法。出于实用性的考虑，本文还提出了一种简单的次优资源分配方法，仿真结果显示这种方法与最优的调度方法性能非常接近。     

On the duality between routing and scheduling systems with finitebuffer space

A duality between scheduling and routing problems associated with a set of parallel queues is established. This allows one to determine the optimal policy for either system, once it is determined for its dual system. Moreover, the evaluation of different design alternatives (e.g., allocation of buffers) can be accommodated in the same duality framework. A crucial assumption is that both systems should be Markovian. Furthermore, when there is no buffer at the controller, the scheduling policy is assumed to be preemptive. On the other hand, when there exists buffer space dedicated to the controller, both the routing and scheduling policies are assumed to be nonidling. Various applications are presented. It is shown, for instance, that the smallest residual capacity scheduling policy is optimal, as it is the dual of the well-known shortest queue routing policy     

Efficient scheduling of page access in index-based join processing

The paper examines the issue of scheduling page accesses in join processing, and proposes new heuristics for the following scheduling problems: 1) an optimal page access sequence for a join such that there are no page reaccesses using the minimum number of buffer pages, and 2) an optimal page access sequence for a join such that the number of page reaccesses for a given number of buffer pages is minimum. The experimental performance results show that the new heuristics perform better than existing heuristics for the first problem and also perform better for the second problem, provided that the number of available buffer pages is not much less than the optimal buffer size     

一种基于分布式并行系统的流媒体数据分发系统

现有的p2p流媒体系统中的数据调度机制给网络带来了很大的压力,提出了一种基于分布式文件系统的调度机制,具有就近调度、站内调度客户节点、站间服务节点自调度的特点,有效降低了主干网上的数据调度。基于这种调度机制,本文以组播为例具体介绍了采用分片技术实现流媒体的数据分发。经过测试本系统数据缓冲稳定,节点更新性能较好。     

鲁棒性项目调度中缓冲设置方法

研究应对不确定因素的鲁棒性项目调度, 针对其所用时间缓冲区技术中的两种重要方法——集中缓冲和STC (starting time criticality) 分散缓冲, 采用仿真模拟实验, 以项目管理库中的帕特森例1 为对象, 进行详细的比较研究. 研究结果表明, 分散缓冲法具有更好的解鲁棒性; 当活动时间的不确定性程度较大时, 集中缓冲法的质量鲁棒性较好; 当项目工期较紧时, 分散缓冲法具有更好的鲁棒性. 这些研究结论为管理者在特定的项目环境下选择合适的缓冲方法提供了决策依据.     

考虑缓冲区的自动生产单元的无死锁调度策略

在制造系统中,必须防止死锁的发生.本文提出了一种在制造系统(带有有限缓冲区)中搜索最优的无死锁调度的算法.为此首先介绍了死锁问题及其图论表示方法,然后在遗传算法的基础上,运用图论算法来保证无死锁的调度结果.为了保证遗传算法生成的调度策略能够满足所要求的约束,运用图论方法选择无死锁个体,或添加缓冲区,从而在基本保证了系统的主要性能指标的同时,得到系统可行的无死锁调度结果.最后给出了一个运用此方法解决死锁问题的实例.     

Fair Scheduling Algorithms in Grids

In this paper, we propose a new algorithm for fair scheduling, and we compare it to other scheduling schemes such as the earliest deadline first (EDF) and the first come first served (FCFS) schemes. Our algorithm uses a max-min fair sharing approach for providing fair access to users. When there is no shortage of resources, the algorithm assigns to each task enough computational power for it to finish within its deadline. When there is congestion, the main idea is to fairly reduce the CPU rates assigned to the tasks so that the share of resources that each user gets is proportional to the users weight. The weight of a user may be defined as the users contribution to the infrastructure or the price he is willing to pay for services or any other socioeconomic consideration. In our algorithms, all tasks whose requirements are lower than their fair share CPU rate are served at their demanded CPU rates. However, the CPU rates of tasks whose requirements are larger than their fair share CPU rate are reduced to fit the total available computational capacity in a fair manner. Three different versions of fair scheduling are adopted in this paper: the simple fair task order (SFTO), which schedules the tasks according to their respective fair completion times, the adjusted fair task order (AFTO), which refines the SFTO policy by ordering the tasks using the adjusted fair completion time, and the max-min fair share (MMFS) scheduling policy, which simultaneously addresses the problem of finding a fair task order and assigning a processor to each task based on a max-min fair sharing policy. Experimental results and comparisons with traditional scheduling schemes such as the EDF and the FCFS are presented using three different error criteria. Validation of the simulations using real experiments of tasks generated from 3D image- rendering processes is also provided. The three proposed scheduling schemes can be integrated into existing grid computing architectures.