DocumentCode :
2205099
Title :
Pinwheel scheduling with three distinct numbers
Author :
Lin, Shun-Shii ; Lin, Kwei-Jay
Author_Institution :
Dept. of Inf. & Comput. Educ., Nat. Taiwan Normal Univ., Taipei, Taiwan
fYear :
1994
fDate :
15-17 Jun 1994
Firstpage :
174
Lastpage :
179
Abstract :
Given a multiset of positive integers A={a1, a2 , ..., an}, the pinwheel problem is to find an infinite sequence over { 1, 2,..., n} such that there is at least one symbol i within any subsequence of length ai. The density of A is defined as ρ(A)=Σi=1n (1/ai). We limit ourselves to instances composed of three distinct integers. Currently, the best scheduler can schedule such instances with a density less than 0.77. A new and fast scheduling scheme based on spectrum partitioning is proposed which improves the 0.77 result to a new 5/6≈0.83 density threshold. This scheduler has achieved the exact theoretical bound of this problem
Keywords :
multiprocessing programs; real-time systems; scheduling; distinct numbers; infinite sequence; pinwheel scheduling; positive integers; spectrum partitioning; theoretical bound; Computer science education; Contracts; Delay; Dynamic scheduling; Fault tolerant systems; Jitter; Petroleum; Processor scheduling; Real time systems; Timing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Real-Time Systems, 1994. Proceedings., Sixth Euromicro Workshop on
Conference_Location :
Vaesteraas
Print_ISBN :
0-8186-6340-5
Type :
conf
DOI :
10.1109/EMWRTS.1994.336846
Filename :
336846
Link To Document :
بازگشت