Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật toán xấp xỉ cho các nhiệm vụ thời gian thực định kỳ với các hàm thời gian thực thi phụ thuộc vào tải công việc
Tóm tắt
Bài báo này giải quyết vấn đề phân bổ tài nguyên cho các nhiệm vụ thời gian thực định kỳ phân tán, hoạt động trong các môi trường có sự thay đổi không dự đoán được và không phù hợp với việc chỉ định thời gian thực thi tồi tệ nhất có nghĩa. Các nhiệm vụ này được cung cấp bởi dữ liệu đầu vào xuất phát từ nhiều nguồn tải công việc môi trường khác nhau. Thay vì sử dụng thời gian thực thi tồi tệ nhất (WCETs) để mô tả mức sử dụng CPU của các nhiệm vụ, chúng tôi giả định rằng các hồ sơ thực thi được cung cấp để mô tả thời gian chạy của các nhiệm vụ dựa trên kích thước dữ liệu đầu vào của mỗi nguồn tải công việc. Mục tiêu của việc phân bổ tài nguyên là tạo ra một phân bổ ban đầu mạnh mẽ chống lại các biến động trong các tham số môi trường. Chúng tôi cố gắng tối đa hóa kích thước đầu vào (tải công việc) mà hệ thống có thể xử lý, và do đó trì hoãn các phân bổ lại (tốn kém) càng lâu càng tốt. Chúng tôi trình bày một thuật toán xấp xỉ dựa trên đầu tiên - phù hợp và tìm kiếm nhị phân mà chúng tôi gọi là FFBS. Như chúng tôi đã chỉ ra ở đây, thuật toán đầu tiên - phù hợp sản xuất các giải pháp thường gần với tối ưu. Cụ thể, chúng tôi cho thấy phân tích rằng FFBS được đảm bảo cung cấp một giải pháp ít nhất là 41% so với tối ưu, asymptotically, trong một số giới hạn hợp lý về thời gian chạy của các nhiệm vụ trong hệ thống. Hơn nữa, chúng tôi cho thấy rằng nếu ít nhất 12% sử dụng của hệ thống bị tiêu tốn bởi các nhiệm vụ độc lập đầu vào (ví dụ, các nhiệm vụ thời gian cố định), thì FFBS được đảm bảo cung cấp một giải pháp ít nhất là 33% so với tối ưu, asymptotically. Hơn nữa, chúng tôi trình bày các mô phỏng để so sánh thuật toán xấp xỉ FFBS với một tập hợp các heuristics chuẩn (tìm kiếm địa phương) như leo núi, làm mát giả lập và tìm kiếm ngẫu nhiên. Các kết quả cho thấy rằng FFBS, kết hợp với các chiến lược cải thiện địa phương khác, có thể là một phương pháp hợp lý cho việc phân bổ tài nguyên trong các hệ thống thời gian thực động.
Từ khóa
#phân bổ tài nguyên #nhiệm vụ thời gian thực #hàm thời gian thực thi #xấp xỉ thuật toán #hệ thống thời gian thực độngTài liệu tham khảo
Aber E, Drews F, Gu D, Juedes D, Lenharth A, Parrott D, Welch L, Zhao H, Fleeman D (2004) Experimental comparison of heuristic and optimal resource allocation algorithms for maximizing allowable workload in dynamic, distributed real-time systems. In: 6th Brazilian Workshop on Real-Time Systems
Ali S, Maciejewski AA, Siegel HJ, Kim J-K (2004) Measuring the robustness of a resource allocation. IEEE Trans Parall Distrib Syst 15(7):630–641
Blazewicz J, Ecker KH, Pesch E, Schmidt G, Weglarz J (2001) Scheduling computer and manufacturing processes. Springer Heidelberg, New York
Burns A (2000) The meaning and role of value in scheduling flexible real-time systems. J Syst Architect 46:305–325
Burns A, Nicholson M, Tindell K, Zhang N (1993) Allocating and scheduling hard real-time tasks on a point-to-point distributed system. In: Proceedings of the The Workshop on Parallel and Distributed Real-Time System, pp 11–20
Garey MR, Johnson DS (1979) Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Company, San Francisco
Gertphol S, Yu Y, Alhusaini A, Prasanna VK (2001) An integer programming approach for static mapping of paths onto heterogeneous real-time systems. In: Ninth Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), 15th International Parallel and Distributed Processing Symposium (IPDPS 2001)
Gertphol S, Yu Y, Gundala SB, Prasanna VK, Ali S, Kim J-K, Maciejewski AA, Siegel H (2002) A metric and mixed-integer-programming-based approach for resource allocation in dynamic real-time systems. In: Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS 2002)
Hou C-J, Shin KG (1997) Allocation of periodic task modules with precedence and deadline constraints in distributed real-time systems. IEEE Trans Comp 46(12):1338–1355
Humphrey M, Brandt S, Nutt G, Berk T (1997) The DQM architecture: Middleware for application -centered QoS resource management. In: Proceedings of the IEEE Workshop on Middleware for Distributed Real-Time Systems and Services, pp 97–104
Juedes D, Drews F, Welch L, Fleeman D (2004) Heuristic resource allocation algorithms for maximizing allowable workload in dynamic, distributed, real-time systems. In: The 12th Workshop on Parallel and Distributed Real-Time Systems (WPDRTS2004), Santa Fe, Mexico, USA
Karr D, Rodrigues C, Loyall J, Schantz R (2001) Controlling quality-of-service in a distributed video application by an adaptive middleware framework. In: Proceedings of ACM Multimedia
Krishnamurth Y, Kachroo V, Karr D, Rodrigues C, Loyall J, Schantz R, Schmidt D (2001) Integration of QoS-enabled distributed object computing middleware for developing next-generation distributed applications. In: Proceedings of the ACM SIGPLAN Workshop on Optimization of Middleware and Distributed Systems
Lee C, Siewiorek D (1999) On quality of service optimization with discrete qos options. In: Proceedings of the 5th IEEE Real-Time Technology and Applications Symposium (RTAS ’99), pp 276–286
Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J Assoc Comp Mach 20(1):46–61
Lopez JM, Diaz JL, Garcia DF (2004) Utilization bounds for edf scheduling on real-time multiprocessor systems. Real-Time Syst 28:39–68
Loyall J, Rubel P, Schantz R, Atighetchi M, Zinky J (2002) Emerging patterns in adaptive, distributed real-time, embedded middleware. In: Proceedings of the 9th Conference on Pattern Language of Programs
Manolache S, Eles P, Peng Z (2004) Optimization of soft real-time systems with deadline miss ratio constraints. In: 10th IEEE Real-Time and Embedded Technology and Applications Symposium
Oh D-I, Baker TP (1998) Utilization bounds for N-processor rate monotonic scheduling with stable processor assignment. Real Time Syst J 15(1):183–193
Peng DT, Shin KG, Abdelzaher TF (1997) Assignment and scheduling of communicating periodic tasks in disributed real-time systems. IEEE Transactions on Software Engineering 23(12)
Puschner P, Schedl A (1997) Computing maximum task execution times—a graph-based approach. The Journal of Real-time Systems 13:67–91
Rajkumar R, Lee C, Lehoczky J, Siewiorek D (1997) A qos-based resource allocations model. In: Proceedings of the IEEE Real-Time Systems Symposium
Rajkumar R, Lee C, Lehoczky J, Siewiorek D (1998) Practical solutions for qos-based resource allocation problems. In: Proceedings of the IEEE Real-Time Systems Symposium, pp 315–326
Rajkumar R, Lee C, Lehoczky J, Siewiorek D (1999) A scalable solution to the multi-resource QoS problem. In: Proceedings of the 20th IEEE Real-Time Systems Symposium, pp 315–326
Ramamritham K (1995) Allocation and scheduling of precedence-related periodic tasks. IEEE Trans Parall Distrib Syst 6(4):412–420
Ravindran B, Welch L, Shirazi B (2000) Resource management middleware for dynamic, dependable real-time systems. Real-Time Syst 20:183–196
Shirazi B, Welch L, Ravindran B, Cavanaugh C, Yanamula B, Brucks R, Huh E (1999) DynBench: A dynamic benchmark suite for distributed real-time systems. In: Proceedings of the Parallel and Distributed Processing: IPPS/SPDP Workshops, pp 1335–1349
Tan Z (2003) .Producing application CPU profiles in DynBench via curve fitting. In: Technical Report, Center for Intelligent, Distributed, and Dependable Systems, Ohio University
Tia T-S, Deng Z, Shankar M, Storch M, Sun J, Wu L-C, Liu JW-S (1995) Probabilistic performance guarantee for real-time tasks with varying computation times. In: IEEE Real-Time Technology and Applications Symposium
Tindell K, Burns A, Wellings A (1992) Allocating real-time tasks (an np-hard problem made easy). J Real-Time Syst 4(2):145–165
Welch LR, Ravindran B, Shirazi BA, Bruggeman C (1998) Specification and modeling of dynamic distributed real-time systems. In: Proceedings of the 19th IEEE Real-Time Systems Symposium. IEEE Computer Society Press, Washington, pp 72–81
Welch LR, Shirazi BA (1999) A dynamic real-time benchmark for assessment of qos and resource management technology. In: Proceedings of the IEEE Real-Time Technology and Applications Symposium, pp 36–45
Welch LR, Werme P, Ravindran B, Fontenot LA, Masters MW, Mills DW, Shirazi BA (1999) Adaptive QoS and resource management using a posteriori workload characterizations. In: Proceedings of the Fifth IEEE Real-Time Technology and Applications Symposium. IEEE Computer Society Press, Washington, pp 266–275
Zhou Y, Welch LR, Huh E-N, Alexander C, Lawrence D (2001) Execution time analysis for dynamic, periodic processes. In: The 9th Workshop on Parallel and Distributed Real-Time Systems