TY - GEN

T1 - Pinwheel scheduling with three distinct numbers

AU - Lin, Shun-Shii

AU - Lin, Kwei Jay

PY - 1994/12/1

Y1 - 1994/12/1

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

UR - http://www.scopus.com/inward/citedby.url?scp=24044476051&partnerID=8YFLogxK

U2 - 10.1109/EMWRTS.1994.336846

DO - 10.1109/EMWRTS.1994.336846

M3 - Conference contribution

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 -