An Efficient Algorithm to Reduce the Inflations in Multi-Supertask Environment by Using a Transient Behavior Prediction Method(<Special Section>Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• The supertask approach was proposed by Moir and Ramamthy as a means of supporting non-migratory tasks in Pfair-scheduled systems. In this approach, tasks bound to the same processor are combined into a single server task, called a supertask, which is scheduled as an ordinary Pfair task. When a supertask is scheduled, one of its component tasks is selected for execution. In previous work, Holman et al. showed that component-task deadlines can be guaranteed by inflating each supertask's utilization. In addition, their experimental results showed that the required inflation factors should be small in practice. Consequently, the average inflation produced by their rules is much greater than that actually required by the supertasks. In this paper, we first propose a notion of Transient Behavior Prediction for supertasks, which predicts the latest possible finish time of subtasks that belong to supertasks. On the basis of the notion, we present an efficient schedulability algorithm for Pfair supertasks in which the deadlines of all component tasks can be guaranteed. In addition, we propose a task merging process which combines the unschedulable supertasks with some Pfair tasks; hence, a newly supertask can be scheduled in the system. Finally, we propose the new reweighting functions that can be used when the previous two methods fail. Our reweighting functions produce smaller inflation factor than the previous work does. To demonstrate the efficacy of the supertasking approach, we present the experimental evaluations of our algorithm, which decreases substantially a number of reweights and the size of inflation when there are many supertasks in the Pfair-scheduled systems.

• 社団法人電子情報通信学会の論文
• 2005-05-01

著者

• Hsu Chiun

  Department Of Information Management National Taiwan University Of Science And Technology

• Chen Da

  Department Of Information Management National Taiwan University Of Science And Technology:department

関連論文

• Body Distributioin of RGD-mediated Liposome in Brain-targeting Drug Delivery
• Simultaneous Wavelength Selection and Outlier Detection in Multivariate Regression of Near-Infrared Spectra
• An Efficient Algorithm to Reduce the Inflations in Multi-Supertask Environment by Using a Transient Behavior Prediction Method(Discrete Mathematics and Its Applications)

スポンサーリンク