Optimal scheduling of parallel processing systems with real-time constraints

Abstract : We consider parallel execution of structured jobs with real time constraints in (possibly heterogeneous) multiprocessor systems. A job is composed of a set of tasks and a partial order specifying the precedence constraints between the tasks. The task processing times are random variables with known probability distribution functions. The interarrival times of the jobs are also random variables with arbitrary distributions. The real time constraints are specified by reference times, also called soft real-time deadlines. In the discussion we assume first that all the jobs have the same task graph, i.e. the same task set and the same partial order. We assume that there is a predefined mapping from the set of tasks onto the set of machines, identical for all jobs, that allocates tasks to machines. We focus on dynamic scheduling policies which do not use information on the processing times of the tasks to be scheduled. The policies can be non-preemptive or preemptive-resume. For non-preemptive policies, we assume that task processing times are independently and identically distributed, whereas for the preemptive ones, we assume that they are independently and identically distributed and come from some specific distributions. Some of the results that are obtained generalize to the case where jobs have a random structure. This more difficult case is treated at the end of the paper. We are interested in such performance criteria as the number of jobs in the system, the throughput in term of jobs and the job lag times, which correspond to the differences between the reference times and the completion times of tasks or jobs. We show that FCFS policies, applied at task level (which imply FIFO for jobs), stochastically minimize the number of jobs and maximize the system throughput. We establish that FCFS policies minimize the vector of the transient response times in the sense of Schur convex ordering, and minimize the stationary response times in the convex ordering sense. Awe c real time applications, we prove that within the class of local order preserving policies that is defined in the paper, the SRF (shortest reference first) and LRF (longest reference first) policies bound respectively from below and from above the lag times vector of the n first jobs, in the Schur convex sense. This in turn yields an analogous convex ordering among the stationary job lag times.
Type de document :
[Research Report] RR-1113, INRIA. 1989
Liste complète des métadonnées

Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 18:14:03
Dernière modification le : jeudi 11 janvier 2018 - 16:31:43
Document(s) archivé(s) le : mardi 12 avril 2011 - 19:02:59



  • HAL Id : inria-00075446, version 1



François Baccelli, Zhen Liu, Don Towsley. Optimal scheduling of parallel processing systems with real-time constraints. [Research Report] RR-1113, INRIA. 1989. 〈inria-00075446〉



Consultations de la notice


Téléchargements de fichiers