在即時系統中，工作通常都是週期性的，而且有最後的完成期限。即使有錯誤發生導致不利的系統環境，這些工作仍是被預期在期限前完成。為了避免這些錯誤的發生，有許多技術設計來重新分配工作到無錯誤發生的工作環境。但是這些重新配置可能導致處理器的超額負載並且無法滿足所有工作在期限前如期完成。在本論文中，我們採用了一套稱作DGA的Guaranteed (m,k)-firm排程模型，它會在系統在遭遇錯誤後，選擇一些工作捨棄掉，以滿足系統的QoS Requirement。我們對(m,k)-firm的排程模型特性有一些新的研究，並且以此設計出一套保證式的Semantic Based (m,k)-firm排程演算法，以修改控制法則來增進原有系統的效能。為了驗證我們演算法的效能與效率，我們設計了一套模擬實驗，並且把實驗結果與原本的DGA演算法相互比較。

In real-time control applications, tasks are usually periodic and they have deadline constraints by which each instance of a task is expected to complete its computation, even in the adverse circumstances caused by dynamic failures. In order to avoid the dynamic failures, many techniques are designed to reassign the tasks to fault-free processors. But these reconfigurations may cause in processor overload where it would no longer meet the deadlines of all tasks. In this paper, we adopted guaranteed (m,k)-firm scheduling model called DGA which discards selected task instances that the performance of the system remains satisfactory even after a failure. We have made some new discoveries concerning the characteristics of (m,k)-firm scheduling model, and have designed a guaranteed semantic-based (m,k)-firm scheduling algorithm to modify the control law to improve the performance of the control system. To verify the effectiveness and efficiency of our algorithm, experiments are designed and implemented. The results compare or algorithm with the current ones.

[1] B. Babcock, S. Babu, M. Datar, R. Motwani, and D. Thomas. “Operator scheduling in data stream systems,” The VLDB Journal, pages 23-31, December 2004.

[2] D. Carney, U. Cetintermel, A. Rasin, S. Zdonik, M. Cherniack, and M. Stonebraker. “Operator scheduling in a data stream manager,” In VLDB, pages 37-44, August 2003

[3] D.K. Pradhan, ed. Prentic Hall, “Fault-Tolerant Computer System Design,” 1996.

[4] G. Quan and X.Hu. “Enhanced fixed-priority scheduling with (m,k)-firm guarantee,” In Proc. Of 21st IEEE Real-time Systems Symposium, pages 27-30, November 2000.

[5] J. Lechoczky, L. Sha, and Y. Ding, “The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior,” Proc. Real-Time Systems Symp., pp. 166-171, Dec. 1989.

[6] Liu, C. L. and Layland J. W. “Scheduling Algorithms for Multiprogramming in a Hard Real Time Environment”. JACM 20 (1) (1973), 46-61.

[7] M. Hamdaoui and P. Ramanathan, “A Dynamic Priority Assignment Technique for Streams with (m,k)-firm Deadlines,” IEEE Trans. Computers, vol.44, no. 12, pp. 1,443-1,451, Dec. 1995.

[8] P. Ramanathan. “Overload management in real-time control applications using (m,k)-firm guarantee.” IEEE transactions on Parallel and Distributed Systems, 10(6):549-559, 1999.

[9] S.Babu, R. Motwani, and K. Munagala. “Adaptive ordering of pipelined stream filters,” In Proc. of SIGMOD, 2004.

[10] Y.-C. Tu, Y. Xia, and S. Prabhakar. Quality of service adaptation in data stream management system: a control-based approach. In International Conference on Very Large Data Bases, Seoul, Korea, September 2004.