A cautious scheduler for multistep transactions

Given a classC of serializable schedules, a cautiousC-scheduler is an on-line transaction scheduler that outputs schedules in classC and never resorts to rollbacks. Such a scheduler grants the current request if and only if the partial schedule it has granted so far, followed by the current request, can be extended to a schedule inC. A suitable extension is searched among the set of all possible sequences of the pending steps, which are predeclared by the transactions whose first requests have already arrived. If the partial schedule cannot be extended to a schedule inC, then the current request is delayed. An efficient cautiousCPSR-scheduler has been proposed by Casanova and Bernstein.This paper discusses cautiousWRW-scheduling, whereWRW is the largest polynomially recognizable subclass of serializable schedules currently known. Since cautiousWRW-scheduling is, in general, NP-complete as shown in this paper, we introduce, a subclass (namedWRW ^#) ofWRW and discuss an efficient cautiousWRW ^#-scheduler. We also show that the fixed point set of the cautiousWRW ^#-scheduler properly containsCPSR. Therefore, ourWRW ^#-scheduler allows more concurrency than anyCPSR- scheduler.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada under Grant No. A5240 and in part by the Ministry of Education, Science and Culture of Japan under Scientific Research Grant-in-Aid.     

Preference-oriented real-time scheduling and its application in fault-tolerant systems

In this paper, we consider a set of real-time periodic tasks where some tasks are preferably executed as soon as possible (ASAP) and others as late as possible (ALAP) while still meeting their deadlines. After introducing the idea of preference-oriented (PO) execution, we formally define the concept of PO-optimality. For fully-loaded systems (with 100% utilization), we first propose a PO-optimal scheduler, namely ASAP-Ensured Earliest Deadline (SEED), by focusing on ASAP tasks where the optimality of ALAP tasks’ preference is achieved implicitly due to the harmonicity of the PO-optimal schedules for such systems. Then, for under-utilized systems (with less than 100% utilization), we show the discrepancies between different PO-optimal schedules. By extending SEED, we propose a generalized Preference-Oriented Earliest Deadline (POED) scheduler that can obtain a PO-optimal schedule for any schedulable task set. The application of the POED scheduler in a dual-processor fault-tolerant system is further illustrated. We evaluate the proposed PO-optimal schedulers through extensive simulations. The results show that, comparing to that of the well-known EDF scheduler, the scheduling overheads of SEED and POED are higher (but still manageable) due to the additional consideration of tasks’ preferences. However, SEED and POED can achieve the preference-oriented execution objectives in a more successful way than EDF.     

A lower bound on the period length of a distributed scheduler

Ad-scheduling of a graphG is a sequence of rounds, each consisting of some of the nodes of the graph, such that the distance between any two nodes participating in the same round is greater thand. Ad-scheduler is a protocol that determines ad-scheduling ofG. A 1-scheduler is applicable to process scheduling in a resource-sharing system, and to proper communication scheduling of the half-duplex model in communication networks. A 2-scheduler can be used as a collision-free protocol for radio networks.In this paper a simpled-scheduler is analyzed. We first discuss basic properties of this scheduling, and give a complete characterization of this scheduling for trees and cycles. We study the period length of this scheduling, and the main result is a worst-case exponential lower bound for this length.The research of Shmuel Zaks was supported by the Fund for Research in Electronics, Computers, and Communications adminstered by the Israeli Academy of Sciences and Humanities.     

An accurate parallel genetic algorithm to schedule tasks on a cluster

Recent breakthroughs in the mathematical estimation of parallel genetic algorithm parameters are applied to the NP-complete problem of scheduling multiple tasks on a cluster of computers connected by a shared bus. Numerous adjustments to the original method of parameter estimation were made in order to accurately reflect differences in the problem model. The parallel scheduler used m-ary encoding and included a shared communication bus constraint. Fitness was an indirect computation requiring an evaluation of the meaning and implications (i.e., effect on communication time) of the encoding. The degree of correctness was defined as the “nearness” to the optimal schedule that could be obtained in a limited amount of time. Experiments reveal that the parallel scheduling algorithm developed very accurate schedules when the modified parameter guidelines were used. This article describes the scheduling problem, the parallel genetic scheduler, the adjustments made to the mathematical estimations, the quality of the schedules that were obtained, and the accuracy of the schedules compared to mathematically predicted expected values.     

On the complexity of concurrency control using semantic information

In the presence of semantic information, serializability is too strong a correctness criterion and unnecessarily restricts concurrency. Many researchers have investigated the use of semantic information to allow interleaving among transactions which are non-serializable, but which nonetheless preserves the consistency of the database and is acceptable to the users. In this paper we consider a class of schedules, calledconflict-correct schedules, first proposed by Farrag and Özsu, which enlarges upon the class of serializable schedules by taking semantic information of transactions into account. In this paper we show that the problem of recognizing schedules in this class is NP-complete. Thus it is unlikely that there exists an efficient scheduler which accepts the entire class of conflict-correct schedules.This research was partially supported by MICRO grants with IBM and XEROX Corporations.     

On strictly optimal schedules for the cumulative cost-optimal scheduling problem

Given a set ofn events (or jobs) which are constrained by a precedence relation, we want to order them into a totally ordered sequence (i. e., one machine schedule). Each event has an integer cost (which may be negative) associated with it, and our objective is to minimize the maximum cumulative cost within a schedule, i. e., to obtain a cumulative cost-optimal schedule. We introduce the concept of “strict optimality” and investigate properties of strictly optimal schedules. The usefulness of these schedules is demonstrated in the special case where the precedence relation is “series-parallel”. For this case we describe an algorithm which finds a cumulative cost-optimal schedule inO (n logn) time.     

Gauss-turán quadratures of chebyshev type and error formulae

This paper begins with an investigation of two special forms of the Gauss-Turán quadrature of Chebyshev-type of precision 6n?1. Then the remainder formulas of these quadratures are developed and sharp error bounds for the functions inC ^q [?1, 1] are shown, whereq is a positive integer. Most importantly this study proves that these reslts can be extended in order to yield sharp error estimates for all such quadratures of higher precision.     

Algorithms minimizing mean flow time: schedule-length properties

Summary The mean flow time of a schedule provides a measure of the average time that a task spends within a computer system, and also the average number of unfinished tasks in the system. The mean flow time of a schedule is defined to be the sum of the finishing times of all tasks in the system. On a system of identical processors O(nlog n) algorithms exist for determining minimal mean flow time schedules for n independent tasks. In general, there will be a large class C of schedules, of widely differing lengths, that all minimize mean flow time. The problem of finding the shortest schedule in C is NP-complete. We give heuristics that find schedules in C that are no more than 25% longer than the shortest schedule in C. The advantage of a short schedule is that processor utilization is high.Partial support provided by NSF Grant GJ-28290     

On the complexity of some inductive logic programming problems

The bounded ILP-consistency problem for function-free Horn clauses is described as follows. Given at setE ⁺ andE ^? of function-free ground Horn clauses and an integerk polynomial inE ⁺∪E ^?, does there exist a function-free Horn clauseC with no more thank literals such thatC subsumes each element inE ⁺ andC does not subsume any element inE ^?? It is shown that this problem is Σ ₂ ^P complete. We derive some related results on the complexity of ILP and discuss the usefulness of such complexity results.     

数据库并发操作的可串行化调度与死锁检测算法

封锁与可串行化调度是数据库并发操作采取的两种主要措施。判断一个调度是否可串行化调度的最有效方法是两段锁协议。但是,一方面,事务遵守两段锁协议只是可串行化调度的充分条件而不是必要条件;另一方面,遵守两段锁协议的事务仍可能发生死锁。文中给出了一种算法,利用该算法,不仅可判断出一个调度是否为可串行化调度,而且可判断出该调度是否会发生死锁。     

A collocation method for boundary value problems of differential equations with functional arguments

A collocation procedure with polynomial and piecewise polynomial approximation is considered for second order functional differential equations with two side-conditions. The piecewise polynomials are taken in the classC ¹ and reduce to polynomials of increasing degree on each interval of a suitable assigned partition. Appropriate choices of the partition are made, according to the jump discontinuities in the derivatives caused by the functional argument, in order to optimize the rate of convergence.     

Edge-skeletons in arrangements with applications

An edge-skeleton in an arrangementA(H) of a finite set of planes inE ³ is a connected collection of edges inA(H). We give a method that constructs a skeleton inO(√n logn) time per edge. This method implies new and more efficient algorithms for a number of structures in computational geometry including order-k power diagrams inE ² and space cutting trees inE ³. We also give a novel method for handling special cases which has the potential to substantially decrease the amount of effort needed to implement geometric algorithms.     

Adaptive Scheduling of Computations and Communications on Distributed-Memory Systems

Compile-time scheduling is one approach to extract parallelism which has proved effective when the execution behavior is predictable. Unfortunately, the performance of most priority-based scheduling algorithms is computation dependent. Scheduling based on the concept of earliest-startable-task produces reasonably short schedules only when available parallelism is large enough to cover the communications. A priority-based decision is more effective when parallelism is low. We propose a scheduling in which the decision function combines two concepts: (1) task-level as global priority and (2) earliest-task-first as local priority The degree of dominance of one of the above concepts is controlled by a computation profile factor that is the ratio of task parallelism to communication. It is shown that the above factor is an upper bound on the deviation of schedule length from optimum. To tune the solution finish time the above scheduler is iteratively applied on the computation graph. In each iteration, the newly generated schedule is used to sharpen the task-levels which contribute in finding shorter schedules in the next iteration. Evaluation is carried out for a wide category of computation graphs with communications for which optimum schedules are known. It is found that pure local scheduling and static priority-based scheduling significantly deviate from the optimum under specific problem instances. Our approach to adapting the scheduling decision to the computation profile is able to produce near-optimum solutions via a much reduced number of iterations than other approaches.     

Conditions for On-line Scheduling of Hard Real-Time Tasks on Multiprocessors

In this paper we consider the problem ofon-linescheduling ofhard real-timetasks onmultipleprocessors. For a given set of ready tasks, one can propose many schedules. These schedules, however, may not necessarily be suitable for on-line scheduling. A suitable on-line schedule is one which can accommodate any future task set when it arrives. The traditional approach to solve the on-line scheduling problem is to propose a heuristic, and then to prove its effectiveness by comparing it with existing heuristics using simulation. No attempt has, however, been made to obtain a condition on the current schedule which when satisfied will permit one to schedule an arbitrary future task. In this paper, we aim at developing such a condition on the current schedule for the set of ready tasks which when satisfied can guarantee an on-line schedule for any futurefeasibletask set.     

A note on balanced immunity

For a finite alphabet ∑ we define a binary relation on \(2^{\Sigma *} \times 2^{2^{\Sigma ^* } } \) , called balanced immunity. A setB ? ∑* is said to be balancedC-immune (with respect to a classC ? 2^Σ* of sets) iff, for all infiniteL εC, $$\mathop {\lim }\limits_{n \to \infty } \left| {L^{ \leqslant n} \cap B} \right|/\left| {L^{ \leqslant n} } \right| = \tfrac{1}{2}$$ Balanced immunity implies bi-immunity and in natural cases randomness. We give a general method to find a balanced immune set'B for any countable classC and prove that, fors(n) =o(t(n)) andt(n) >n, there is aB εSPACE(t(n)), which is balanced immune forSPACE(s(n)), both in the deterministic and nondeterministic case.     

Positive Versions of Polynomial Time

We show that restricting a number of characterizations of the complexity classPto be positive (in natural ways) results in the same class of (monotone) problems, which we denote byposP. By a well-known result of Razborov,posPis a proper subclass of the class of monotone problems inP. We exhibit complete problems forposPvia weak logical reductions, as we do for other logically defined classes of problems. Our work is a continuation of research undertaken by Grigni and Sipser, and subsequently Stewart; indeed, we introduce the notion of a positive deterministic Turing machine and consequently solve a problem posed by Grigni and Sipser.     

RTAI混合任务调度器的设计与实现

针对RTAI系统只能调度单一类型任务的问题,提出一种可调度多类型任务的混合任务调度器。该调度器支持CBS调度策略,并采用LXRT机制关联软实时任务和CBS服务器,根据服务器调度策略对软实时任务进行调度。实验结果表明,该混合任务调度器在保证硬实时任务正常运行的同时提高了软实时任务的服务水平。     

A general theory of translation

The concept of a translation is fundamental to any theory of compiling. Formally, atranslation is any set of pairs of words. Classes of finitely describable translations are considered in general, from the point of view of balloon automata [17, 18, 19]. A translation can be defined by atransducer, a device with an input tape and an output terminal. If, with inputx, the stringy appears at the output terminal, then (x, y) is in the translation defined by the transducer. One can also define a translation by a two input taperecognizer. Ifx andy are placed on the two tapes, the recognizer tells if (x, y) is in the defined translation. One can define closed classes of transducers and recognizers by:

1. restricting the way in which infinite storage may be used (pushdown structure, stack structure, etc.),
2. allowing the finite control to be nondeterministic or deterministic,
3. allowing one way or two way motion on the input tapes.

We have some results on classes of translations which can be categorized roughly into three types.

1. Translations defined by certain classes of transducers and recognizers are equivalent.
2. Translations of a given class are sometimes closed under composition and decomposition with a finite memory translation (gsm mapping).
3. A nondeterministically defined translation can be expressed as the composition of a finitely defined translation and a related deterministically defined translation in many cases.

In addition, ifC is a class of translations, then one can write a compiler-compiler to render any translationT inC and only if the following question is solvable: For any translationT inC and stringx, does there exist ay such that (x, y) is inT? We shall show that, in general, the decidability of this question is equivalent to the decidability of one or more questions from automata theory, depending upon the type of devices defining the classC.     

Reliability of task graph schedules with transient and fail-stop failures: complexity and algorithms

This paper deals with the reliability of task graph schedules with transient and fail-stop failures. While computing the reliability of a given schedule is easy in the absence of task replication, the problem becomes much more difficult when task replication is used. We fill a complexity gap of the scheduling literature: our main result is that this reliability problem is #P??-Complete (hence at least as hard as NP-Complete problems), both for transient and for fail-stop processor failures. We also study the evaluation of a restricted class of schedules, where a task cannot be scheduled before all replicas of all its predecessors have completed their execution. Although the complexity in this case with fail-stop failures remains open, we provide an algorithm to estimate the reliability while limiting evaluation costs, and we validate this approach through simulations.     

Automatically generating consistent schedules for multimedia documents

A schedule for a multimedia document indicates when document events should occur. We describe a two-phase algorithm that automatically produces schedules for interactive multimedia documents, which can contain both predictable behavior (such as audio and video) and unpredictable behavior (such as user interaction and programs with unpredictable execution times). The first phase of the algorithm, called the compiletime scheduler, preprocesses high-level temporal specifications before the document is presented and creates as much of the schedule as possible. Our compiletime scheduler is conceptually similar to T_EX's spatial layout algorithm in that it permits time to be stretched or shrunk between events inside media segments to arrive at an optimal presentation for a document. The second phase of the algorithm, called the runtime scheduler, resolves the presentation of media segments that depend upon unpredictable behavior.