超载实时系统的算法

Algorithm for Overload Real-Time Systems

近年来，超载实时系统ｏｎ－ｌｉｎｅ排序已被许多作者研究过，对单台机问题，Ｓ．Ｂａｒｕａｈ等给出了一个最坏性能比的上界１／（１＋√Ｋ）~２，其中Ｋ为重要性比，Ｇ．Ｋｏｒｅｎ等提出了一个达到此界的最优算法（Ｄ－ｏｖｅｒ算法），对多台机问题，Ｍ． Ｄｅｒｔｏｕｚｏｓ等证明即使在非超载情况下也不存在最优算法． Ｆ． Ｗａｎｇ等证明不可能存在竞争因子大于１／２的算法，并提出了一个算法，在Ｋ＝１及没有松弛时问的条件下，达到了１／２．对一般情况，他们证明任一Ｏｎ－ｌｉｎｅ算法的竞争因子均不会大于１／ａ，其中．对多台机情况，虽已发现了一些有用的性质，但如何构造一个较好的算法仍有待于进一步的研究．

The On-Line schedule of overload real-time systems has been variously studied in recent years. For single-machine problem,S. Baruah gave a up bound of 1/(1+√k)~2 ,and G. Koren presented a optimal algorithm (D-over algorithm) which bounded it. M. Dertouzos proved that there had not been optimal algorithm, even if it's not overload. F. Wang also proved that there had not been algorithm when the competitive factor was larger than 1 /2,and gave an algorithm,when k = 1 and there was not relaxation time,the competitive factor could reach 1/2. Under the general condition,they proved that the competitive factor of every on-line algorithm could not larger than 1/a,where . For multiprocessor, it is need to word ahead for a good algorithm.