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
         
        
        
        
        
        
            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;
         
        
        
        
            Conference_Titel : 
Real-Time Systems, 1994. Proceedings., Sixth Euromicro Workshop on
         
        
            Conference_Location : 
Vaesteraas
         
        
            Print_ISBN : 
0-8186-6340-5
         
        
        
            DOI : 
10.1109/EMWRTS.1994.336846