Markov chain analyses of multiprogrammed computer systems

Most operating systems for large computing facilities involve service disciplines which base, to some extent, the sequencing of object program executions on the amount of running time they require. It is the object of this paper to study mathematical models of such service disciplines applicable to both batch and time-shared processing systems. In particular, Markov queueing models are defined and analyzed for round-robin and foreground-background service disciplines. With the round-robin discipline, the service facility processes each program or job for a maximum of q seconds; if the program's service is completed during this quantum, it leaves the system, otherwise it returns to the end of the waiting line to await another quantum of service. With the foreground-background discipline each new arrival joins the end of the foreground queue and awaits a single quantum of service. If it requires more it is subsequently placed at the end of the background queue which is allocated service only when the foreground queue is empty. The analysis focuses on the efficiency of the above systems by assuming a swap or set-up time (overhead cost) associated with the switching of programs on and off the processor. The analysis leads to generating functions for the equilibrium queue length probabilities, the moments of this latter distribution, and measures of mean waiting times. The paper concludes with a discussion of the results along with several examples.     

Parallel machine scheduling with job assignment restrictions

In the classical multiprocessor scheduling problem independent jobs must be assigned to parallel, identical machines with the objective of minimizing the makespan. This article explores the effect of assignment restrictions on the jobs for multiprocessor scheduling problems. This means that each job can only be processed on a specific subset of the machines. Particular attention is given to the case of processing times restricted to one of two values, 1 and λ, differing by at most 2. A matching based polynomial time ε‐approximation algorithm is developed that has a performance ratio tending to . This algorithm is shown to have the best possible performance, tending to 3/2, for processing times 1 and 2. For the special case of nested processing sets, i.e., when the sets of machines upon which individual jobs may be assigned are non‐overlapping, the behavior of list scheduling algorithms is explored. Finally, for assignment restrictions determined by just one characteristic of the machines, such as disc storage or memory constraint in the case of high performance computing, we contribute an algorithm that provides a 3/2 worst case bound and runs in time linear in the number of jobs. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2007     

随机弱实时系统作业调度概率保证分析

随机弱实时系统与强实时系统的显著区别是 ,它不要求实时任务的每一项作业都满足时限要求 ,只要保证作业的时限延误率低于某一阈值 ,其总体执行性能就是可以接受的。提出了概率时间需求分析法 (PTDA) ,用于估计可剥夺静态优先级调度策略下周期性任务的作业满足时限约束的概率的下界 ,并通过一个具体的实例考察了下界的紧性。对实例系统的仿真结果表明 ,PTDA分析的误差小于 1 0 % ,计算速度快 ,可以为弱实时应用的设计提供重要的参考依据     

公安边防部队士官学历教育浅谈

公安边防部队的士官学历教育尚在起步阶段,任重而道远。各级领导应着眼部队长远建设,确立优先发展的战略地位;应立足部队现实需要,设置学科专业;应根据岗位任职需求,确定课程体系,突出实用性;应适应教学任务的要求,完善管理与保障体系。     

A robust policy for serial agile production systems

One of the major problems in modeling production systems is how to treat the job arrival process. Restrictive assumptions such as Markovian arrivals do not represent real world systems, especially if the arrival process is generated by job departures from upstream workstations. Under these circumstances, cost‐effective policies that are robust with respect to the nature of the arrival process become of interest. In this paper, we focus on minimizing the expected total holding and setup costs in a two‐stage produce‐to‐order production system operated by a cross‐trained worker. We will show that if setup times are insignificant in comparison with processing times, then near‐optimal policies can be generated with very robust performances with respect to the arrival process. We also present conditions under which these near‐optimal policies can be obtained by using only the arrival and service rates. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

一种用于 UWB 雷达实时信号处理的可重构多处理机结构

超宽带（UWB）雷达信号处理是个多任务、大运算量的过程，必须采用多处理机并行处理技术。本文对UWB雷达实时信号处理系统的特点进行了深入的分析，在比较各种多处理机系统优缺点的基础上，提出了一种可重构的UWB雷达实时信号处理系统结构。将此结构应用于实际系统表明，该结构具有良好的性能，并具有可重构性和扩展性。     

多处理机系统的微任务并行

本文讨论微任务技术及其在多机系统上的实现。微任务技术使得一个程序能在循环和语句块一级并行执行,它的显著特点是系统开销较小、效率较高,适应于小粒度并行。     

On competitive analysis for polling systems

Polling systems have been widely studied, however most of these studies focus on polling systems with renewal processes for arrivals and random variables for service times. There is a need driven by practical applications to study polling systems with arbitrary arrivals (not restricted to time-varying or in batches) and revealed service time upon a job's arrival. To address that need, our work considers a polling system with generic setting and for the first time provides the worst-case analysis for online scheduling policies in this system. We provide conditions for the existence of constant competitive ratios, and competitive lower bounds for general scheduling policies in polling systems. Our work also bridges the queueing and scheduling communities by proving the competitive ratios for several well-studied policies in the queueing literature, such as cyclic policies with exhaustive, gated or l-limited service disciplines for polling systems.     

Assembly of systems having maximum reliability

The first problem considered in this paper is concerned with the assembly of independent components into parallel systems so as to maximize the expected number of systems that perform satisfactorily. Associated with each component is a probability of it performing successfully. It is shown that an optimal assembly is obtained if the reliability of each assembled system can be made equal. If such equality is not attainable, then bounds are given so that the maximum expected number of systems that perform satisfactorily will lie within these stated bounds; the bounds being a function of an arbitrarily chosen assembly. An improvement algorithm is also presented. A second problem treated is concerned with the optimal design of a system. Instead of assembling given units, there is an opportunity to “control” their quality, i.e., the manufacturer is able to fix the probability, p, of a unit performing successfully. However, his resources, are limited so that a constraint is imposed on these probabilities. For (1) series systems, (2) parallel systems, and (3) k out of n systems, results are obtained for finding the optimal p's which maximize the reliability of a single system, and which maximize the expected number of systems that perform satisfactorily out of a total assembly of J systems.     

General multiprocessor task scheduling

Most papers in the scheduling field assume that a job can be processed by only one machine at a time. Namely, they use a one‐job‐on‐one‐machine model. In many industry settings, this may not be an adequate model. Motivated by human resource planning, diagnosable microprocessor systems, berth allocation, and manufacturing systems that may require several resources simultaneously to process a job, we study the problem with a one‐job‐on‐multiple‐machine model. In our model, there are several alternatives that can be used to process a job. In each alternative, several machines need to process simultaneously the job assigned. Our purpose is to select an alternative for each job and then to schedule jobs to minimize the completion time of all jobs. In this paper, we provide a pseudopolynomial algorithm to solve optimally the two‐machine problem, and a combination of a fully polynomial scheme and a heuristic to solve the three‐machine problem. We then extend the results to a general m‐machine problem. Our algorithms also provide an effective lower bounding scheme which lays the foundation for solving optimally the general m‐machine problem. Furthermore, our algorithms can also be applied to solve a special case of the three‐machine problem in pseudopolynomial time. Both pseudopolynomial algorithms (for two‐machine and three‐machine problems) are much more efficient than those in the literature. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 57–74, 1999     

弹载SINS/GPS组合导航信息同步与融合技术

针对一种基于DSP+FPGA+MCU多处理器计算机平台的弹载组合导航系统设计了精确有效的信息同步的方法,采用GPS接收机提供的1PPS脉冲和MCU提供的脉冲信号实现GPS和SINS信号时间上的同步,采用杆臂校正算法完成了GPS和SINS测量信号空间上的同步.由于系统噪声难于准确统计,因此采用自适应卡尔曼滤波算法进行数据融合.最后对系统进行了跑车试验,试验结果表明系统所采用的方法具有较好的效果.     

网络化作战系统的软硬件体系

分析了发展网络化作战系统的两个推动要素——信息技术的发展和第二代作战系统所面临的问题 ,讨论了网络作战系统的发展目标 ,提出了网络化作战系统的软硬件体系结构 ,包括硬件的三层次结构和集成化作战软件的技术方案 ,指出了实现作战系统网络化的巨大效用。     

Transputer 处理机在连续系统并行仿真中的应用

Transputer是最近几年由lnmos公司研制推出的一种新型VLSI单片计算机,它具有价格低廉,处理能力强,方便灵活等特点,其应用广泛。作者将连续系统仿真应用中的一个典型实例——某型号飞机六自由度飞行的仿真——在Transputer,YH—F1,YH—1等各种类型计算机上求解。结果表明,Transputer多机系统具有很高的性能价格比,比大型机约高一个数量级。     

多机环境下系统程序并行化的实现方法

本文给出了多处理机环境对系统程序的要求,阐述了系统程序并行化研制过程中遇到的问题和解决办法,给出了实现临界段互斥的三种处理方法及其性能评价。     

The mixed ordering policy in periodic review stochastic multi-commodity inventory systems

In multi-commodity inventory systems with variable setup costs, the mixed ordering policy assumes that commodities may be ordered either individually, or may be arbitrarily grouped for joint ordering. Thus, for a two-commodity system, commodity one or commodity two or commodities one and two may be ordered incurring respectively fixed order costs of K, K₁, or K₂, where max (K₁, K₂) ≤ K ≤ K₁ + K₂, This paper considers a two-commodity periodic review system. The stationary characteristics of the system are analyzed, and, for a special case, explicit solutions are obtained for the distribution of the stock levels at the beginning of the periods. In a numerical example, optimal policy variables are computed, and the mixed ordering policy is compared with individual and joint ordering policies.     

对舰用监控系统中复杂多机通讯模式实现方法的研究

结合舰船电力网络绝缘监测装置 ,提出了一种解决舰船监控系统中复杂多机通讯问题的方法 ,对其实现中的关键技术进行了细致的分析 ,并给出了结论 .     

Opportunistic retooling of a flexible machine subject to failure

A set of jobs can be processed without interruption by a flexible machine only if the set of tools required by all jobs can be loaded in the tool magazine. However, in practice the total number of tools required by a job set would exceed the tool magazine capacity. In such situations, the job set has to be carefully partitioned at the start of the production run such that each partition can be processed without interruption. During the production run, if there are unscheduled machine downtimes due to machine failure, this provides an additional opportunity to optimally retool the magazine for a smaller job set consisting of just the unprocessed jobs. In this paper, we study job sequencing rules that allow us to minimize the total expected cost of machine down time due to machine failures and magazine retooling, assuming a dynamic re‐sequencing of the unprocessed jobs after each machine failure. Using these rules, we develop a branch‐and‐bound heuristic that allows us to solve problems of reasonable size. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 79–97, 2001     

并行程序运行故障原因识别

高性能计算系统的复杂性和规模的不断增长使得系统的平均无故障时间越来越短,因此系统的硬软件故障导致并行程序运行出错的概率随之增加。此外,并行程序本身可能存在的编程错误也会导致运行出错。由于处理上述两类故障原因的措施迥异,所以在程序运行出现故障时,用户需要关注故障原因的类别。针对这一问题,设计和实现了一种基于作业管理系统Slurm的并行程序运行故障原因识别系统。通过对Slurm进行扩展,监控作业状态,重提交和重运行作业。根据作业运行结果,区分故障原因类别。故障注入方式进行的实验表明,该系统具有较高的识别准确率。     

Matrix-geometric solution of discrete time MAP/PH/1 priority queue

We use the matrix-geometric method to study the discrete time MAP/PH/1 priority queue with two types of jobs. Both preemptive and non-preemptive cases are considered. We show that the structure of the R matrix obtained by Miller for the Birth-Death system can be extended to our Quasi-Birth-Death case. For both preemptive and non-preemptive cases the distributions of the number of jobs of each type in the system are obtained and their waiting times are obtained for the non-preemptive. For the preemptive case we obtain the waiting time distribution for the high priority job and the distribution of the lower priority job's wait before it becomes the leading job of its priority class. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 23–50, 1998     

关于机器人力控制器计算机系统的设计方案探讨

本文从机器人力反馈依从控制的任务和要求出发,对机器人控制多处理机系统设计中的几个主要问题,包括总的系统结构、存储器结构、机间互连结构、中断系统结构、并发实时操作系统、处理机选型和多处理机系统的调试等,进行了探讨。