本論文針對週期性的嚴格即時系統(Hard Real-Time systems)之排程提出三種快速且能保證公平(fairness)的排程演算法。
大型工作(Supertask)首次由Moir與Ramamthy兩人所提出，並且應用在比例式公平(Proportionate fairness, Pfair)的排程中。當某些工作被限定在同一個處理器上面執行時，這些工作可以組合起來成為一個大型工作，並且被視為一般的Pfair工作來進行排程。也就是說, 當大型工作被排程時, 它所包含的其中一個工作（又稱為子工作(component task)）就會被挑出來執行。然而, 他們亦提出反例說明子工作在某些情況下無法被大型工作所排程。而Holman與Anderson提出了一種重新加權的演算法來改善Moir等人所提出的大型工作排程方法。然而，根據他們的實驗結果，這種重新加權的演算法會大幅增加系統閒置的時間。這篇論文中的第一個目標是要降低系統閒置時間。也就是說，儘可能降低大型工作的重新加權的幅度與次數。我們提出一個更有效率的重新加權演算法。它能夠大幅降低大型工作加權後的膨脹係數,也就是加權後的權重減去加權前的權重。根據實驗結果，可以發現我們的方法執行所需時間更短，並且能大幅降低工作平均膨脹係數與重新加權的次數。
服務品質在電腦系統中一直是一個很重要的議題。尤其在即時的應用中，工作之間的間隔距離必須限制在某一個範圍以內，而不能只以週期性的方式去執行這些工作。更具體地說，若一個工作以一連串的工作要求來表示，則任意兩個工作要求之間的時間間隔必須被限制在某個固定的範圍內。這種即時系統排程被稱為限制距離工作系統（Distance-Constrainted Task Systems，DCTS）。在論文的第二部份中，我們以提早釋放公平排程(Early- Release fairness，ERfair)為基礎，提出一個快速的重新加權的排程演算法，使得ERfair排程可以滿足DCTS的限制。
另外，動態電源管理(Dynamic Voltage Scaling, DVS)主要的功能是以作業系統層次去控制硬體的工作電壓。在不影響工作有效率執行之前提下，它能動態管理電壓，以達到省電的效果。在有限的電源供應的情況下，嚴格即時系統要求在最小能源消耗的情況下，使每個工作都能在他們的時間限制之內完成。 Weiser 等人首先建議以動態方式調整CPU的速度與電壓使得工作可利用空閒時間來延長它的執行週期，藉由此一方式來節省電源又能保證工作可以在期限內完成。另外，許多文獻指出目前有許多處理器的速度可以在某個區間內任意調整。例如Crusoe processor可以在33MHz的頻率範圍內任意改變執行頻率。因此，在論文的第三部分,我們將以DCTS為模型,發展一個離線的演算法負責排程的初始化工作，其中包括了參數的計算以及工作週期的轉換等等．另外，還要發展出一套線上的DVS演算法；當發生工作提早完成時，必須很快地找出其它哪些工作適合分享因該工作提早完成所剩下的空閒時間，並且動態調整這些工作的執行速度同時也必須保證這些Job能在它們各自的期限內完成。

This dissertation studies the fairness and energy efficiency of the hard real-time schedules with periodic tasks.
The supertask approach was proposed by Moir and Ramamthy as a means of supporting non-migratory tasks in Proportionate-fair (Pfair) scheduled systems. In this approach, tasks bound to the same processor are combined into a single server task, called a supertask, which is scheduled as an ordinary Pfair task. When a supertask is scheduled, one of its component tasks is selected for execution. However, counterexamples presented by them showed that component-tasks, which bound to the supertask may miss their deadlines. Holman et al. showed that component-task deadlines can be guaranteed by inflating each supertask’s utilization. In addition, their experimental results showed that the required inflation factors should be smaller in practice. Consequently, the average inflation produced by their rules is much greater than that actually required by the supertasks. We propose an efficient scheduling algorithm for Pfair supertasks in which the deadlines of all component tasks can be guaranteed. In addition, we propose a task merging process which combines the unschedulable supertasks with some Pfair tasks. Therefore, a new supertask can be scheduled in the system. We also propose the new reweighting functions that can be used when the previous two methods fail.
The guarantee of quality of service (QoS) of multimedia applications is a main issue in computer system resource management. Tasks in these real-time applications must be performed in a distance-constrained manner, rather than just periodically. That is, the temporal distance between any two consecutive executions, called the job requests, of the same task should always be less than a given amount of time. Such real-time systems are called Distance-Constrained Task Systems (DCTS) and to remedy the deficiency of the periodic task model. In the second part, we propose two variant Distance-Constraint Task Systems (DCTS) by using the Early-Release-Fair (ERfair) model with integral assumptions for identical multi-processor real-time systems. ERfair is a scheduling model for real-time tasks on a multiprocessor system. For the different definitions of distance constraint, we propose two efficient scheduling algorithms which can probe whether the distance constraints of all ER-fair tasks can be guaranteed. If the distance constraints cannot be guaranteed, then the proposed algorithms gather the unfeasible tasks and inflate them with a reweighting function. The proposed algorithms are in linear time and most suitable for dynamic systems.
In addition, dynamic voltage scaling (DVS) has been a key technique to reduce energy consumption by lowering the supply voltage and operating frequency. We propose a novel on-line DVS scheme for tasks in DCTS, which can decrease significantly more energy than dynamic reclaiming and speculative scheduling techniques can. We provide a deterministic and smooth voltage-adjusting (SVA) method rather than an estimative or speculative one. Our scheme is to generate off-line the task parameters in polynomial time, which are employed to help a fast on-line scheduler which can generate the scheduling sequence in linear time.

[1]J. Anderson and A. Srinivasan, Early-release fair scheduling, in: Proceedings of the 12th Euromicro Conference on Real-Time Systems, pp. 35-43, 3 June 2000.
[2]J. Anderson and A. Srinivasan, A new look at Pfair priorities, Technical Report, University of North Carolina, Oct. 1999.
[3]J. Anderson and A. Srinivasan, Mixed pfair/erfair scheduling of asynchronous periodic tasks, in: Proceedings. of the 13th Euromicro Conference on Real-Time Systems, pp. 76-85, June 2001.
[4]J. Anderson and A. Srinivasan, Pfair scheduling: Beyond periodic task systems, in: Proceedings of the 7th International Conference on Real-Time Computing Systems and Applications, pp. 297-306, Dec. 2000.
[5]B. Andersson and J. Jonsson, The utilization bounds of partitioned and pfair static-priority scheduling on multiprocessors are 50%, in: Proceedings of the 15th Euromicro Conference on Real-time Systems, pp. 33-40, July 2-4, 2003.
[6]H. Aydin, R. Melhem, D. Mosse, and P. Mejia-Avarez, Power-Aware Scheduling for Periodic Real-Time Tasks, IEEE Trans. Computers, Vol. 53 (5), pp. 584-600, May 2004.
[7]H. Aydin, R. Melhem, D. Mosse, and P. Mejia-Avarez, Dynamic and Aggressive Power-Aware Scheduling Techniques for Real-Time Systems, in: Proceedings of the 22nd IEEE Real-time Systems Symposium, London, England, pp. 95–105, Dec. 2001.
[8]S. Baruah, Scheduling periodic tasks on uniform multiprocessors, Information Processing Letters, Vol. 80 (2), pp. 97-104, 2001.
[9]S. Baruah, Fairness in periodic real-time scheduling, in: Proceedings of the 16th IEEE Real-Time Systems Symposium, Pisa, Italy, pp. 200-209, Dec. 4-7, 1995.
[10]S.Baruah, N. Cohen, C.G. Plaxton, and D.Varvel, Proportionate progress: A notion of fairness in resource allocation, Algorithmica, Vol. 15, pp. 600-625, 1996.
[11]S. K. Baruah, J. E. Gehrke, and C. G. Plaxton, Fast scheduling of periodic tasks on multiple resources, in: Proceedings of 9th International Parallel Processing Symposium, pp. 280-288, 1995.
[12]S. K. Baruah, Mok, A., Rosier, L., Algorithms and Complexity Concerning the Preemptively Scheduling of Periodic, Real-Time Tasks on One Processor, RealTime Systems Journal , Vol. 2, pp. 301-324, 1990.
[13]S. K. Baruah, A. K. Mok, and L. E. Rosier, Preemptively scheduling hard-real-time sporadic tasks on one processor, in: Proceedings of the Real-Time System Symposium, Lake Buena Vista, FL, pp. 182-190, Dec. 1990.
[14]S. K. Baruah, Shun-Shii Lin, Pfair scheduling of generalized pinwheel task systems, IEEE Transactions on Computers, Vol. 47 (7), pp. 812-816, July 1998.
[15]T. Burd, R. Brodersen, Processor design for portable systems, Journal of VLSI Signal Processing, Vol. 13 (2-3), pp. 203–221, Aug/Sept 1996.
[16]A. Chandra, M. Adler, and P.Shenoy, Deadline fair scheduling: Bridging the theory and practice of proportionate fair scheduling in multiprocessor systems, Technical Report TR00-38, Department of Computer Science, University of Massachusetts at Amherst, Dec. 2000.
[17]A. P. Chandrakasan, S. Sheng, and R. W. Brodersen, Low-power CMOS digital design, IEEE Journal of Solid-State Circuits, Vol. 27, pp. 473-484, Apr. 1992.
[18]H. M. Chaskar and U. Madhow, Fair scheduling with tunable latency: A round-robin approach, IEEE/ACM Transactions on Networking, Vol. 11 (4), pp. 592-601, Aug. 2003.
[19]T. H. Chen and Muhlethaler. A scheduling algorithm for tasks described by time value function. Journal of Real-Time Systems, Vol. 10, No.3, pp. 293-312, May 1996.
[20]S. K. Dhall and C. L. Liu, On a real-time scheduling problem, Operations Research, Vol. 26 (1), pp. 127-140, 1978.
[21]S. Davari and S. K. Dhall, An On-Line Algorithm for Real-Time Tasks Allocation, In IEEE Real Time Systems Symposium, pp. 194-200, 1986.
[22]R. Emst and W. Ye, Embedded Program Timing Analysis Based on Path Clustering and Architecture Classification, in: Proceedings International Conference on Computer-Aided Design (ICCAD ’97), pp. 598-604, 1997.
[23]C.-S. Shih, M. Caccamo, C.-G. Lee and L.Sha, Radar Dwell Scheduling with Temporal Distance and Energy Constraints, in: Proceedings of Radar 2004 International Conference (RADAR '04), Toulouse, France, Oct. 2004.
[24]J. Goossens, S. Funk and S. Baruah, Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors, Real-Time Systems, Vol. 25, pp. 187-205, 2003.
[25]K. Govil, E. Chan and H. Wasserman, Comparing Algorithms for Dynamic Speed-Setting of a LOW-Power CPU, in: Proceedings of The First ACM International Conference on Mobile Computing and Networking, Berkeley, CA, pp. 13-25, Nov. 1995.
[26]F. Gruian, Hard Real-Time Scheduling for Low-Energy Using Stochastic Data and DVS Processors, in: Proceedings of the International Symposium on Low-Power Electronics and Design (ISLPED'01), Aug. 2001.
[27]C.-C. Han and K.-J. Lin, Scheduling Distance-Constrained Real-Time Tasks, in: Proceedings of the 13th IEEE Real-Time Systems Symposium, Pheonix, Arizona, pp. 300-308, Dec. 1992.
[28]P. Holman and J. Anderson, Guaranteeing Pfair Supertasks by Reweighting, in: Proceedings of the 22nd IEEE Real-time System Symposium, pp. 203-212. Dec. 2001.
[29]P. Holman and J. Anderson, Using supertasks to improve processor utilization in multiprocessor real-time systems, in: Proceedings of the 15th Euromicro Conference on Real-time Systems, to appear in July 2003.
[30]P. Holman, J. H. Anderson, Object Sharing in Pfair-scheduled Multiprocessor Systems, in: Proceedings of the 14th Euromicro Conference on Real-time Systems, pp.111-121, 2002.
[31]M.A. Horowitz, Self-clocked structures for low power systems, ARPA semi-annual report, Computer Systems Laboratory, Stanford University, Dec. 1993.
[32]C.-W. Hsueh and K.-J. Lin, Scheduling Real-Time Systems with End-to-End Timing Constraints Using the Distributed Pinwheel Model, IEEE Transactions on Computers, vol. 50 (1), pp. 51-66, Jan. 2001.
[33]C.-C. Han, K.-J. Lin and Chao-Ju Hou, Distance-Constrained Scheduling and Its Applications to Real-Time Systems, IEEE Transactions on Computers, vol. 45 (7), pp. 814-826, July 1996.
[34]T. Ishihara and H Yasuura, Voltage scheduling problem for dynamically variable voltage processors, in: Proceedings of the International Symposium on Low Power Electronics and Design, pp. 197–202, Aug. 1998.
[35]R. Jejurikar and R. Gupta, Energy aware task scheduling with task synchronization for embedded real time systems, in: Proceedings of the international conference on Compilers, Architecture and Synthesis for Embedded Systems, Grenoble, France, pp. 8-11, Oct. 2002.
[36]W. Kim, D. Shin, H.-S. Yun, J. Kim, and S. L. Min, Performance Comparison of Dynamic Voltage Scaling Algorithms for Hard Real-Time Systems, in: Proceedings of the Eighth IEEE Real-Time Technology and Applications Symposium (RTAS’02), pp. 219, Sep. 2002.
[37]C.M. Krishna and Y.-H. Lee, Voltage-clock-scaling adaptive scheduling techniques for low power in hard real-time systems, in: Proceedings of Sixth Real-Time Technology and Applications Symposium (RTAS’00), pp. 156, May 2000.
[38]P. Kumar and M. Srivastava, Power-aware multimedia systems using run-time prediction, in: Proceedings of 13th International Conference on Computer Design, Jan. 2001.
[39]T.-W. Kuo, L.-P. Chang, Y.-H. Liu and K.-J. Lin, Efficient online schedulability tests for real-time systems, Software Engineering, IEEE Transactions on, Vol. 29 (8), pp. 734-751, Aug. 2003.
[40]J. Y.-T. Leung and J. Whitehead, On the complexity of fixed-priority scheduling of periodic real-time tasks, Performance Evaluation, Vol. 2, pp. 237-250, 1982.
[41]T. Li and C. Ding, Instruction balance and its relation to program energy consumption, in: Proceedings of International Workshop on Languages and Compilers for Parallel Computing, Kentucky, Aug. 2001.
[42]C. L. Liu, Scheduling algorithms for multiprocessors in a hard real-time environment, JPL Space Programs Summary, pp. 37-60, 1969.
[43]C. L. Liu and J. Layland, Scheduling algorithms for multiprogramming in a hard real-time environment, Journal of the ACM, Vol. 20 (1), pp. 46-61, 1973.
[44]M. Moir and S. Ramamurthy, Pfair scheduling of fixed and migrating periodic tasks on multiple resources, in: Proceedings of the 20th IEEE Real-Time Systems Symposium, pp. 294-303, Dec. 1999.
[45]D. Mosse´, H. Aydin, B. Childers, and R. Melhem, Compiler-Assisted Dynamic Power-Aware Scheduling for Real-Time Applications, in: Proceedings of the Workshop Compilers and Operating Systems for Low-Power (COLP ’00), Oct. 2000.
[46]Y. Oh and S. H. Son, Tight performance bounds of heuristics for a real-time scheduling problem, Technical Report CS-93-24, University of Virginia, 1993.
[47]P. Pillai and K.G. Shin, Real-Time dynamic voltage scaling for low power embedded operating systems, in Proceedings of the 18th ACM Symposium on Operating Systems Principles (SOSP), Oct. 2001.
[48]J. Pouwelse, K. Langendoen and H. Sips, Dynamic voltage scaling on a low-power microprocessor, in: Proceedings of the 7th International Conference on Mobile Computing and Networking (Mobicom 01), pp. 251-259, Rome, Italy, July 2001.
[49]C.-S. Shih, S. Gopalakrishnan, P. Ganti, M. Caccamo, and L. Sha, Synthesizing Task Periods for Dwells in Multi-Function Phased Array Radars, in: Proceedings of the IEEE Euromicro Conference on Real-Time Systems, Catania, Italy, June 2004.
[50]A. Srinivasan and J. H. Anderson, Optimal rate-based scheduling on multiprocessors, in: Proceedings of the 34th ACM Symposium on Theory of Computing, pp. 189-198, 2002.
[51]A. Srinivasan and J. H. Anderson, Efficient Scheduling of Soft Real-Time Applications on Multiprocessors, in: Proceedings of the 15th Euromicro Conference on Real-time Systems, pp. 51-71, 2003.
[52]A. Srinivasan, P. Holman, J. H. Anderson and S. K. Baruah, The Case for Fair Multiprocessor Scheduling, IPDPS, pp. 114-130, 2003.
[53]A. Srinivasan, P. Holman, J. H. Anderson and J. Kaur, Multiprocessor Scheduling in Processor-based Router Platforms, In 2nd Workshop on Network Processors(NP2), Anaheim, CA.
[54]M. Weiser, B. Welch, A. Demers and S. Shenker, Scheduling for reduced CPU energy, in: proceedings of the first USENIX Symposium on operating systems design and implementation, pp. 13-23, Nov. 1994.
[55]F. Yao, A. Demers and S. Shenker, A Scheduling Model for Reduced CPU Energy, in: Proceedings of the IEEE Symposium on Foundations of Computer Science, pp. 374-382, 1995.
[56]D. Zhu, D. Mosse and R. Melhem, Power-Aware Scheduling for AND/OR Graphs in Real-Time Systems, IEEE Transactions on Parallel and Distributed Systems, Vol. 15 (9), pp. 849-864, Sep. 2004.
[57]Transmeta Corporation, 2000. <http://www.transmeta.com>