TY - GEN
T1 - Pinwheel scheduling with three distinct numbers
AU - Lin, Shun Shii
AU - Lin, Kwei Jay
PY - 1994
Y1 - 1994
N2 - 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 [5] 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.
AB - 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 [5] 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.
UR - http://www.scopus.com/inward/record.url?scp=24044476051&partnerID=8YFLogxK
U2 - 10.1109/EMWRTS.1994.336846
DO - 10.1109/EMWRTS.1994.336846
M3 - 会议稿件
AN - SCOPUS:24044476051
SN - 0818663405
SN - 9780818663406
T3 - Proceedings - Euromicro Conference on Real-Time Systems
SP - 174
EP - 179
BT - Proceedings - 6th Euromicro Workshop on Real-Time Systems, ECRTS 1994
T2 - 6th Euromicro Workshop on Real-Time Systems, ECRTS 1994
Y2 - 15 June 1994 through 17 June 1994
ER -