Search

We consider an online version of the classical problem of preemptive scheduling on uniformly related machines. We are given m machines with speeds s1 s2 sm and a sequence of jobs, each described by its processing time (length). The actual time needed to process a job with length p on a machine with speed s is p=s. In the preemptive version, each job may be divided into several pieces, which can be assigned to different machines in disjoint time slots. (A job may be scheduled in several time slots on the same machine, and there may be times when a partially processed job is not running at all.) The objective is to find a schedule of all jobs in which the maximal completion time (makespan) is minimized. In the online problem, jobs arrive one by one and the algorithm needs to assign each incoming job to some time slots on some machines, without any knowledge of the jobs that arrive later. This problem, also known as list scheduling, was first studied by Graham [8] for identical machines (i.e., s1 D D sm D 1), without preemption. In the preemptive version, upon the arrival of a job, its complete assignment at all times must be given and the algorithm is not allowed to change this assignment later. In other words, the online nature of the problem is in the order of the input sequence, and it is not related to possible preemptions and the time in the schedule.

We consider a scheduling problem on two identical parallel machines, in which the jobs are moved between the machines by an uncapacitated transporter. In the processing preemption is allowed. The objective is to minimize the time by which all completed jobs are collected together on board the transporter. We identify the structural patterns of an optimal schedule and design an algorithm that either solves the problem to optimality or in the worst case behaves as a fully polynomial-time approximation scheme.

When job parameters are uncertain or unpredictable, new types of policies become possible. Besides static policies, we now should consider dynamic policies, with or without preemption. Objectives too have more variety. The makespan, for example, is now random; we usually choose to minimize its expectation.

The question whether preemptive systems are better than non-preemptive systems has been debated for a long time, but only partial answers have been provided in the realtime literature and some issues still remain open to discussion. In fact, each approach has advantages and disadvantages, and no one dominates the other when both predictability and efficiency have to be taken into account in the system design. This chapter presents and compares some existing approaches for reducing preemptions and describes an efficient method for minimizing preemption costs by removing unnecessary preemptions while preserving system schedulability.

Computational grids typically involve parallel machines at the sites of the grid. We apply a grid model where the grid scheduler potentially negotiates scheduling of remote jobs for guaranteed start times with site schedulers that operate independently and autonomously. Then, response times are a main criterion to decide where to place a job for remote execution and job placement may involve advanced reservations. The latter are known to have negative impact on the response times of local jobs. In previous work, we have shown that adaptive resource allocation and gang scheduling can reduce this impact and therefore support advanced reservations. However, gang scheduling has the disadvantage of a high memory pressure. We present an approach for coarse-grain timesharing with preemption of jobs to disk. The approach is explicitly controllable regarding the resource shares allocated to different job classes with potential differentiation for different times of the day. The approach can easily be extended to support advanced reservation, group shares, and resource provisioning. The differentiation of service over the day is supported by collection and presentation of detailed statistics.

This presentation aims to discuss the needs for better and more solid foundations of model-based development in embedded control systems. Three particular points are discussed: a comparison between model-based development in controi and in computer sciences, the need for a sampling theory of discrete event systems and the need for precise implementation methods based on preemptive scheduling.

A new switching technique, called Optical Burst Switching (OBS), has been proposed as one of the candidate technologies for future optical networks with higher bandwidth efficiency. Many issues of OBS have been researched and some solutions of them are published by both academia and industry. In this chapter, after a brief review of OBS concepts, we present some of our experiences that we have obtained from research on OBS related projects in Alcatel research and network strategy group. These will include multi-Terabit IP Optical Router (TIPOR), the first publicly demonstrated prototype, that is based on burst switching technology, preemptive scheduling technique with QoS support, tree-shared multicasting, and operation and maintenance framework for OBS networks.

Condor is a batch job system that, unlike many other scheduling systems, allows users to access both dedicated computers and computers that are not always available, perhaps because they are used as desktop computers or are not under local control. This introduces a number of problems, some of which are solved by Condor's preemptive resume scheduling, which is the focus of this paper. Preemptive resume scheduling allows jobs to be interrupted while running, and then restarted later. Condor uses preemption in several ways in order to implement the policies supplied by users, computer owners, and system administrators.

This chapter describes precedence and preemption in Land Mobile Radio (LMR), the primary communications medium used by First Responders worldwide. It differentiates between implicit and explicit means for achieving precedence and preemption, and describes the situational variability in priority — a fundamental characteristic of public safety emergency communication requirements. The priority mechanisms in the APCO Project 25 standards and the ETSI Trans-European Trunked Radio (TETRA) standards are described in the context of these requirements. The chapter also describes priority calling in the third-generation Automatic Link Establishment (ALE) HF radio standards, now the US and NATO standard for digital HF radio communications, often used for critical back-up communications.

This chapter presents an overview of Multi-Level Precedence and Preemption and its architecture behaviors. It describes the key components of the MLPP architecture, and a list of issues to consider.

This chapter describes evolving priority and precedence in commercial wireless systems, beginning with the Final Report of the Public Safety Wireless Advisory Committee (PSWAC) statement of needs. The chapter describes the Global System for Mobile (GSM) and, most importantly, the Enhanced Multi-Level Precedence and Preemption capability. GSM is shown to provide the MLPP capability needed in the US after 9–11 to provide priority services for National Security and Emergency preparedness subscribers.

The continuously increasing demand for computation resources is being met by clusters of workstations and servers, as well as distributed or shared memory supercomputers. The usage of this infrastructure must meet a dual objective: optimization of resource utilization, and guarantee of quality of service to users. Batch scheduling methods based on space sharing and static partitioning have limited performance scalability with respect to the number of users.

Test scheduling is a major problem in system-on-a-chip (SOC) test automation. In this chapter1, we extend previous work on scheduling presented in Chapter 5 to develop an integrated framework that addresses several important test scheduling problems. We first present efficient techniques to determine optimal SOC test schedules with precedence constraints, i.e., schedules that preserve desirable orderings among tests. We then present a new algorithm that uses preemption to obtain optimal test schedules in polynomial time. Finally, we present a new method for determining optimal power-constrained schedules. Experimental results for a representative SOC show that test schedules can be obtained in reasonable CPU time for all cases.

In this chapter we study several methods to propagate a One-Machine resource constraint: A set of n activities A1,…, A n require the same resource of capacity 1. The propagation of resource constraints is a purely deductive process that allows to deduce inconsistencies and to tighten the temporal characteristics of activities and resources. In the non-preemptive case (Section 2.1), the earliest start times and the latest end times of activities are updated. When preemption is allowed (Section 2.2), modifications of earliest end times and latest start times also apply.

Given a set of communication tasks (best described in terms of a weighted bipartite graph where one set of nodes denotes the senders, the other set the receivers, edges are communication tasks, and the weight of an edge is the time required for transmission), we wish to minimize the total time required for the completion of all communication tasks assuming that tasks can be preempted (that is, each edge can be subdivided into many edges with weights adding up to the edge’s original weight) and that preemption comes with a cost. In this paper, we first prove that one cannot approximate this problem within a factor smaller than 7/6 unless P = NP. It is known that a simple approximation algorithm achieves within a ratio of two [2]. However, our experimental results show that its performance is worse than the originally proposed heuristic algorithm [5]. We devise a more sophisticated algorithm, called the potential function algorithm which, on the one hand, achieves a provable approximation ratio of two, and on the other hand, shows very good experimental performance Moreover, the way in which our more sophisticated algorithm derives from the simple one, suggests a hierarchy of algorithms, all of which have a worst-case performance at most two, but which we suspect to have increasingly better performance, both in worst case and with actual instances.

This paper evaluates a Markov decision approach to single-link Call Admission Control for CBRlVBR and ABRlUBR services. Two different schemes that sup­ port integration of narrow-band ABRlUBR and wide-band CBRlVBR services are evaluated: the standard preemptive scheme and the modified partial blocking scheme. The structure of the Markov decision policy shows an "intelligent block­ ing" feature, which implements bandwidth reservation for wide-band calls. The numerical results show that the Markov decision method yields higher long-term reward than the complete sharing method when the ability to create sufficient capacity for wide-band calls through partial blocking/preemption is limited. The results also show that the modified partial blocking scheme, which allows total preemption, gives the highest average reward rate.

This paper describes thread management mechanisms of an operating system for communication-execution fusion, CEFOS (Communication-Execution Fusion Operating System). CEFOS is based on a fine-grain multithreading approach. Once a thread begins to run, it never stops until it is completed, and the maximam run time of a thread is 1 msec. A basic policy of thread management is to realize light-weight threads and fairness of executions. And we suggest the DRD(Display Requests and Data) function which takes small overhead in executions cooperation of processes and OS kernel. The basic mechanisms of thread management, scheduling, preemption, time-slice and synchronizing are described.