T-preemptive priority queue and its application to the analysis of an opportunistic spectrum access in cognitive radio networks

We propose a new priority discipline called the T-preemptive priority discipline. Under this discipline, during the service of a customer, at every T time units the server periodically reviews the queue states of each class with different queue-review processing times. If the server finds any customers with higher priorities than the customer being serviced during the queue-review process, then the service of the customer being serviced is preempted and the service for customers with higher priorities is started immediately. We derive the waiting-time distributions of each class in the M/G/1 priority queue with multiple classes of customers under the proposed T-preemptive priority discipline. We also present lower and upper bounds on the offered loads and the mean waiting time of each class, which hold regardless of the arrival processes and service-time distributions of lower-class customers. To demonstrate the utility of the T-preemptive priority queueing model, we take as an example an opportunistic spectrum access in cognitive radio networks, where one primary (licensed) user and multiple (unlicensed) users with distinct priorities can share a communication channel. We analyze the queueing delays of the primary and secondary users in the proposed opportunistic spectrum access model, and present numerical results of the queueing analysis.     

The AMVA priority approximation

Most computer systems contain one or more system resources whose usage is controlled on the basis of workload priorities. Unfortunately, the exact analysis of queueing network models incorporating priority scheduling disciplines is usually infeasible. The MVA Priority Approximation has been proposed as a comparatively inexpensive, and yet reasonably accurate, approximation technique for queueing networks with priority scheduled service centers. Even this algorithm, however, is too expensive to apply to large networks with many classes of customers.In this paper, we show how the MVA Priority Approximation can be modified so that it utilizes approximate rather than exact Mean Value Analysis (MVA), without significant loss of accuracy. Extensive numerical experiments are performed to further assess the accuracy of the modified algorithm, termed here the AMVA Priority Approximation. These experiments utilize the parameter space mapping technique for studying ‘local’ queueing network approximations.     

A parallel priority queueing system with finite buffers

In this paper we pose and analyze a novel model of a priority queueing system that represents a conveyor model. What is novel in this model is that priority is designed to minimize the idleness of the system. Thus, we discussed a general parallel finite buffer multi-server priority queueing system with balking and reneging and analyze a two-station case of it. An algorithmic solution for the general two-station case and closed-form solutions for special cases of this model are given. We use block-matrix method to find distribution of the queue length, probability of the system idleness, probability of loss to the system, probability of stations being busy, and the first two moments. Numerical examples are given for comparison with Disney's model [R.L. Disney, Some multichannel queueing problems with order entry, J. Ind. Engng. 13 (1962) 46–48; R.L. Disney, D. Kögin, Queuing networks: a survey of their random processes, SIAM Rev. 27 (3) (1958) 335–400] and discussion of properties of the model.     

Analysis of a multi-server queue with two priority classes and (M, N)-threshold service schedule I: non-preemptive priority

In this paper, we propose an ( M , N )-threshold non-preemptive priority service schedule for a queueing system consisting of two-parallel queues and a multi-server. The arrival process for each queue is Poisson, and the service times are exponentially distributed with different means. We derive the generating functions of the stationary joint queue-length distribution, and then obtain the mean queue length and the mean waiting time for each queue.     

Evolving priority scheduling heuristics with genetic programming

This paper investigates the use of genetic programming in automated synthesis of scheduling heuristics for an arbitrary performance measure. Genetic programming is used to evolve the priority function, which determines the priority values of certain system elements (jobs, machines). The priority function is used within an appropriate meta-algorithm for a given environment, which forms the priority scheduling heuristic. The evolved solutions are compared with existing scheduling heuristics and found to perform similarly to or better than existing algorithms. We intend to show that this approach is particularly useful for combinations of scheduling environments and performance measures for which no adequate scheduling algorithms exist.     

On fluid queueing systems with strict priority

We consider priority fluid queueing systems where high-priority class has strict priority access to service. Sample path analysis tools, such as Poisson counter driven stochastic differential equation, are employed to study system queueing behavior in steady state. We are able to obtain various analytical results for different fluid traffic models and system configurations. Those results can be used as a general rule of thumb in buffer dimensioning and other traffic engineering issues.     

Analysis of a nonpreemptive priority queue with SPP arrivals of high class

This paper considers a nonpreemptive priority queueing system with two priority classes of customers, where high priority customers arrive to the system in accordance with a switched Poisson process (SPP) and low priority customers in accordance with a Poisson process. Using the supplementary variable technique, we derive the joint probability generating function of the stationary queue length distributions and the Laplace-Stieltjes transforms of the stationary waiting time distributions of high and low priority customers. We also present some numerical results in order to show the computational feasibility of the analytical results.     

Performance analysis of wireless mobile networks with queueing priority and guard channels

The blocking probability of originating calls and forced termination probability of handoff calls are important criteria in performance evaluation of integrated wireless mobile communication networks. In this paper, we model call traffic in a single cell in an integrated voice/data wireless mobile network by a finite buffer queueing system with queueing priority and guard channels. We categorize calls into three types of service classes: originating voice calls, handoff voice calls and data calls. The arrival streams of calls are mutually independent Poisson processes, and channel holding times are exponentially distributed with different means. We describe the behavior of the system by a three‐dimensional continuous‐time Markov process and present the explicit expression for steady‐state distribution of queue lengths using a recursive approach. Furthermore, we calculate the blocking, forced termination probabilities and derive the Laplace–Stieltjes transform of the stationary distribution of actual waiting times and their arbitrary kth moment. Finally, we give some numerical results and discuss the optimization problem for the number of guard channels.     

A note on the effect of preemptive policies on the stability of a priority queue

We study the stability condition of an M/G/1 priority queue with two classes of jobs. Class 1 jobs have preemptive priority over class 2 jobs. We consider three different types of preemptions and the effects of possible work loss (due to preemption) on the stability condition for the queueing system.     

区分服务中一种动态概率优先级调度算法*

提出了一种动态概率优先级算法DPP,针对一类对延时和丢包率要求相对较高的应用,根据AF1队列长度动态调整概率计算参数p,有效地解决了由于突发流量带来的QoS性能下降问题。不同实验环境下的仿真结果表明,DPP算法有效改善了突发性对分组平均排队延时的影响,减少了分组丢包率。     

Energy aware fixed priority scheduling in mixed-criticality systems

Most of studies about energy management for MC systems are based on dynamic priority scheme. The disadvantages of dynamic priority scheme are high system overhead and poor predictability. Unlike previous studies, we focus on the problem of scheduling mixed-criticality (MC) periodic tasks with minimizing energy consumption in MC systems based on fixed priority scheme. Firstly, we explain a criticality rate monotonic scheduling (CRMS) and propose the sufficient schedulability condition of CRMS. Secondly, we compute the energy minimization uniform scaled speed and present an optimal static solution algorithm based on CRMS. The extra workload of the high criticality level (HI) task executes with the maximum processor speed in the high criticality mode (HI-mode). But this algorithm does not exploit the slack time generated from the HI task in the low criticality mode (LO-mode). For energy efficiency, we propose a dynamic fixed priority energy minimization algorithm which exploits the slack time generated from the HI task in LO-mode to save energy. In addition, it combines a dynamic voltage and frequency scaling technique and a dynamic power management technique to reduce energy consumption. Finally, the experiments are applied to evaluate the performance of the proposed algorithm and the experimental results show that the proposed algorithm can save up 23.89% energy compared with other existing algorithms.     

A simple fluid model for servicing priority traffic

We consider a simple priority queueing system with two different types of traffic, high and low priority. Each type of traffic generates arrivals to its own buffer that are modeled by continuous fluid flows. The input flow into the high priority buffer is Markov modulated, while the input rate into the low priority buffer is constant. The fluid is transmitted from the buffers with the high priority buffer having priority over the low priority buffer. The problem for the joint distribution of the buffer contents is derived and solved explicitly. Approximations are constructed for the tail behavior of the buffer content     

A group priority earliest deadline first scheduling algorithm

In most priority scheduling algorithms, the number of priority levels is assumed to be unlimited. However, if a task set requires more priority levels than the system can support, several jobs must in practice be assigned the same priority level. To solve this problem, a novel group priority earliest deadline first (GPEDF) scheduling algorithm is presented. In this algorithm, a schedulability test is given to form a job group, in which the jobs can arbitrarily change their order without reducing the schedulability. We consider jobs in the group having the same priority level and use shortest job first (SJF) to schedule the jobs in the group to improve the performance of the system. Compared with earliest deadline first (EDF), best effort (BE), and group-EDF (gEDF), simulation results show that the new algorithm exhibits the least switching, the shortest average response time, and the fewest required priority levels. It also has a higher success ratio than both EDF and gEDF.     

Analytical and simulation modeling of a multi-server queue with Markovian arrivals and priority services

We consider a multi-server queueing system in which two types of customers arrive according to a Markovian arrival process. Type 1 customers have preemptive priority over Type 2 customers. A Type 2 arrival finding all servers busy will be lost. However, a Type 1 customer finding all servers busy with at least one Type 2 in service will get into service by pre-empting one of the Type 2 customers in service. Pre-empted Type 2 customers enter into a buffer of finite capacity. These (preempted) customers eventually leave the system after completing a service. In the case of exponential services, this model is studied analytically in steady-state by exploiting the special nature of the queueing model. A number of useful performance measures along with some illustrative examples are reported. In the case of non-exponential services, we simulate the model and discuss the effect of the variatio the services on some selected performance measures.     

Fuzzy priority rule for job shop scheduling

Job shop scheduling uses various kinds of priority rules such as SPT, CR, COVERT, etc. Each of these rules aims at satisfying a single criterion though scheduling is a multi criteria problem. In this paper, a new approach using fuzzy logic is introduced to combine SPT, CR priority rules, and next machine's load (NML) rate the job to be processed next in order to satisfy not only a single objective but also all objectives. Fuzzy logic calculates priority value by considering SPT, CR, and NML. We named this priority rule as fuzzy priority rule (FPR). The job with the highest priority value is assigned to machine to be processed. To compare FPR with other priority rules such as SPT, EDD, etc. we run simulation. The results indicate significant improvements on mean flow time, mean tardiness, work in process (WIP), and throughput simultaneously.     

Semaphore queue priority assignment for real-time multiprocessorsynchronization

Prior work on real time scheduling with global shared resources in multiprocessor systems assigns as much blocking as possible to the lowest priority tasks. We show that better schedulability can be achieved if global blocking is distributed according to the blocking tolerance of tasks rather than their execution priorities. We describe an algorithm that assigns global semaphore queue priorities according to blocking tolerance, and we present simulation results demonstrating the advantages of this approach with rate monotonic scheduling. Our simulations also show that a simple FIFO usually provides better real time schedulability with global semaphores than priority queues that use task execution priorities     

A maximum entropy priority approximation for a stableG/G/1 queue

Summary The principle of maximum entropy is used under two different sets of mean value constraints to analyse a stableG/G/1 queue withR priority classes under preemptive-resume (PR) and non-preemptive head-of-line (HOL) scheduling disciplines. New one-step recursions for the maximum entropy state probabilities are established and closed form approximations for the marginal queue length distribution per priority class are derived. To expedite the utility of the maximum entropy solutions exact analysis, based on the generalised exponential (GE) distribution, is used to approximate the marginal mean queue length and idle state probability class constraints for both the PR and HOLG/G/1 priority queues. Moreover, these results are used as building blocks in order to provide new approximate formulae for the mean and coefficient of variation of the effective priority service-time and suggest a maximum entropy algorithm for general open queueing networks with priorities in the context of the reduced occupancy approximation (ROA) method. Numerical examples illustrate the accuracy of the proposed maximum entropy approximations in relation to simulations involving different interarrival-time and service-time distributions per class. Comments on the extension of the work to more complex types of queueing systems are included.This work is sponsored in part by the Science and Engineering Research Council (SERC), UK, under grant GR/D/12422 and in part by the Ministry of Higher Education of the Algerian Government     

面向敏捷询单处理的订单优先级排序方法

在分析了企业敏捷询单中订单排程问题的基础上,构建了面向敏捷询单处理的订单排程框架.对订单排程阶段中的关键问题——订单优先级排序方法进行了研究.结合电子行业的具体应用,从顾客系数、订单价值和订单复杂程度3个维度构建了订单优先级排序的评价指标体系,采用基于新标度法的层次分析法计算出订单优先级的排序.分析结果表明,该方法能有效解决实际订单评审阶段的订单排程问题,对提高企业询单的敏捷性和准确性具有较好的指导意义.     

Performance analysis of a non-preemptive priority queuing system subjected to a correlated Markovian interruption process

In this paper, we consider a discrete-time queuing system with head-of-line non-preemptive priority scheduling and a single server subjected to server interruptions. We model the server interruptions by a correlated Markovian on/off process with geometrically distributed on and off periods. Two classes of traffic are considered, namely high-priority and low-priority traffic. In the first part of the paper, we derive an expression for the functional equation describing the transient evolution of this priority queuing system. This functional equation is then manipulated and transformed into a mathematical tractable form. This allows us to derive the joint probability generating function (pgf) of the system contents. From this pgf, closed-form expressions for various performance measures, such as mean and variance of system contents and customer delay can be derived. Finally, we illustrate our solution technique with some numerical examples, whereby we demonstrate the negative effect of correlation in the interruption process on the performance of both classes. Some numerical results illustrating the impact of second-order characteristics of the arrival process on mean delays are also presented. The proposed approach which is purely based on pgfs is entirely analytical and enables the derivation of not only steady-state but transient performance measures, as well. The paper presents new insights into the performance analysis of discrete-time queues with service interruption and it also covers some previously published results as a special case.

Scope and purpose

In this contribution, we consider a practical queuing model, with HOL priority scheduling, two classes of traffic, and a server which is subjected to a correlated Markovian interruption process. We first derive a non-linear functional equation relating the joint pgf of the system state vector between two consecutive slots. Then we outline a solution technique to solve for this functional equation. This allows us to derive the joint pgf of the system contents of both classes, from which various performance measures related to mean system contents and customer delays are derived. We also demonstrate how the proposed approach allows for derivation of transient performance measures, as well. It should be noted that detailed coverage of the transient analysis of the system is beyond the scope of this paper.To our best knowledge, this is the first initiative that aims to explore the performance of queuing systems with priority scheduling when the shared server is subjected to service interruption. The paper also generalizes the results of Walraevens et al. (Analysis of a single-server ATM queue with priority scheduling, Computers & Operations Research 2003;30(12):1807–30) by incorporating service interruption into their original queuing model. By means of numerical results, the paper also demonstrates the effect of correlation in the service interruption process on the performance of both classes of customers. The impact of second-order characteristics of the arrival process on mean delays is also investigated.