Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Các bài kiểm tra khả năng lập lịch trực tuyến cho các đặt chỗ thích ứng trong lập lịch ưu tiên cố định
Tóm tắt
Đặt chỗ thích ứng là một kỹ thuật lập lịch thời gian thực, trong đó mỗi ứng dụng được liên kết với một phần tài nguyên tính toán (một sự đặt chỗ) có thể được điều chỉnh động theo các yêu cầu thay đổi của ứng dụng bằng cách sử dụng các thuật toán điều khiển phản hồi phù hợp. Đặt chỗ thích ứng thường được triển khai bằng cách sử dụng thuật toán máy chủ không chu kỳ (ví dụ: máy chủ ngẫu nhiên) với chu kỳ cố định và ngân sách biến đổi. Khi luật phản hồi yêu cầu tăng ngân sách đặt chỗ, hệ thống phải thực hiện một bài kiểm tra khả năng lập lịch để kiểm tra xem có đủ băng thông dư thừa để đáp ứng sự tăng đó hay không. Bài kiểm tra khả năng lập lịch phải rất nhanh, vì nó có thể được thực hiện ở mỗi lần cập nhật ngân sách, tức là có thể ở mỗi thời điểm của một tác vụ; tuy nhiên, nó phải hiệu quả nhất có thể để tối đa hóa việc sử dụng tài nguyên. Trong bài báo này, chúng tôi giải quyết vấn đề thực hiện một bài kiểm tra khả năng lập lịch trực tuyến hiệu quả cho các đặt chỗ tài nguyên thích ứng trong các bộ lập lịch ưu tiên cố định. Trong tài liệu, một số thuật toán đã được đề xuất cho việc kiểm soát quyền truy cập trực tuyến trong các hệ thống ưu tiên cố định. Chúng tôi mô tả bốn bài kiểm tra trong số đó, với độ phức tạp và hiệu suất tăng dần. Ngoài ra, chúng tôi đề xuất một bài kiểm tra trực tuyến mới, có tên là thuật toán Spare-Pot, đã được thiết kế đặc biệt cho vấn đề đang xem xét và cho thấy tỷ lệ chi phí/hiệu suất tốt so với các bài kiểm tra khác.
Từ khóa
#đặt chỗ thích ứng #lập lịch thời gian thực #kiểm tra khả năng lập lịch #thuật toán máy chủ không chu kỳ #ngân sách biến đổi #hệ thống ưu tiên cố định #kiểm soát quyền truy cập trực tuyếnTài liệu tham khảo
Abeni L, Buttazzo G (1998) Integrating multimedia applications in hard real-time systems. In: Proc 19th IEEE real time systems symposium
Abeni L, Buttazzo G (1998) Integrating multimedia applications in hard real-time systems. In: Proceedings of the 19th IEEE real-time systems symposium, Madrid, Spain, December 1998, pp 4–13
Abeni L, Palopoli L, Buttazzo G (2000) On adaptive control techniques in real-time resource allocation. In: Proceedings of the 12th Euromicro conference on real-time systems, Stockholm, Sweden, June 2000, pp 129–136
Abeni L, Palopoli L, Lipari G, Walpole J (2002) Analysis of a reservation feedback scheduler. In: Proc 23rd IEEE real time systems symposium
Abeni L, Cucinotta T, Lipari G, Marzario L, Palopoli L (2005) Qos management through adaptive reservations. Real-Time Syst, 29(2–3):131–155
Almeida L, Anand M, Fischmeister S, Lee I (2007) A dynamic scheduling approach to designing flexible safety-critical systems categories and subject descriptors. In: Proc of the 7th annual ACM conference on embedded software EMSOFT
Audsley NC, Burns A, Richardson M, Tindell KW, Wellings AJ (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8(5):284–292
Bini E, Buttazzo GC (2004) Schedulability analysis of periodic fixed priority systems. IEEE Trans Comput 53(11):1462–1473
Bini E, Buttazzo GC, Buttazzo GM (2003) Rate monotonic scheduling: the hyperbolic bound. IEEE Trans Comput 52(7):933–942
Bini E, Di Natale M, Buttazzo GC (2007) Sensitivity analysis for fixed-priority real-time systems. Real-Time Syst 39(1–3):5–30
Bini E, Huyen T, Nguyen C, Richard P, Baruah SK (2009) A response-time bound in fixed-priority scheduling with arbitrary deadlines. IEEE Trans Comput 58(2):279–286
Block A, Brandenburg B, Anderson JH, Quint S (2008) An adaptive framework for multiprocessor real-time system. In: Euromicro conference on real-time systems. ECRTS’08, July 2008, pp 23–33
Burchard A, Liebeherr J, Oh Y, Son SH (1995) New strategies for assigning real-time tasks to multiprocessor systems. IEEE Trans Comput 44(12):1429–1442
Buttazzo G, Lipari G, Caccamo M, Abeni L (2002) Elastic scheduling for flexible workload management. IEEE Trans Comput 51(3):289–302
Buttazzo G, Lipari G, Abeni L, Caccamo M (2005) Soft real-time systems: predictability vs. efficiency. Springer, Berlin
Caccamo M, Buttazzo G, Sha L (2000a) Elastic feedback control. In: IEEE proceedings of the 12th Euromicro conference on real-time systems, pp 121–128
Caccamo M, Buttazzo G, Sha L (2000b) Capacity sharing for overrun control. In: Proceedings of the 21st IEEE real-time systems symposium, Orlando (FL), USA, December 2000, pp 295–304
Caccamo M, Buttazzo GC, Thomas DC (2005) Efficient reclaiming in reservation-based real-time systems with variable execution times. IEEE Trans Comput 54(2):198–213
Chen D, Mok AK, Kuo T-W (2003) Utilization bound revisited. IEEE Trans Comput 52(3):351–361
Cucinotta T, Lipari G Adaptive reservation simulator. http://gna.org/projects/arsim
Cucinotta T, Palopoli L (2007) Feedback scheduling for pipelines of tasks. In: Proceedings of the 10th international conference on hybrid systems: computation and control, HSCC’07. Springer, Berlin, pp 131–144
Cucinotta T, Palopoli L, Marzario L (2004a) Stochastic feedback-based control of qos in soft real-time systems. In: 43rd IEEE conference on decision and control, 2004. CDC, vol 4, pp 3533–3538
Cucinotta T, Palopoli L, Marzario L, Lipari G, Abeni L (2004b) Adaptive reservations in a Linux environment. In: Proc of 10th IEEE real-time and embedded technology and applications symposium
Cucinotta T, Abeni L, Palopoli L, Lipari G (2011) A robust mechanism for adaptive scheduling of multimedia applications. ACM Trans Embed Comput Syst 10(4):1–24
Han C-C, Tyan H-y (1997) A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithm. In: Proceedings of the 18th IEEE real-time systems symposium, San Francisco (CA), USA, December 1997, pp 36–45
Joseph M, Pandya PK (1986) Finding response times in a real-time system. Comput J 29(5):390–395
Lauzac S, Melhem R, Mossé D (2003) An improved rate-monotonic admission control and its applications. IEEE Trans Comput 52(3):337–350
Lee C-G, Sha L, Peddi A (2004) Enhanced utilization bounds for QoS management. IEEE Trans Comput 53(2):187–200
Lehoczky JP, Sha L, Ding Y (1989) The rate-monotonic scheduling algorithm: exact characterization and average case behavior. In: Proceedings of the 10th IEEE real-time systems symposium, Santa Monica (CA), USA, December 1989, pp 166–171
Lipari G, Baruah SK (2000) Greedy reclamation of unused bandwidth in constant bandwidth servers. In: Proceedings of the 12th Euromicro conference on real-time systems, Stockholm, Sweden, June 2000
Lipari G, Bertolini C Real-time simulator. http://rtsim.sssup.it/
Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J Assoc Comput Mach 20(1):46–61
Lu C, Stankovic J, Tao G, Son S (2002) Feedback control real-time scheduling: framework, modeling and algorithms. Real-Time Syst 23:85–126
Manabe Y, Aoyagi S (1998) A feasibility decision algorithm for rate monotonic and deadline monotonic scheduling. Real-Time Syst 14(2):171–181
Marzario L, Lipari G, Balbastre P, Crespo A (2004) Iris: A new reclaiming algorithm for server-based real-time systems. In: IEEE real-time and embedded technology and applications symposium, pp 211–218
Masrur A, Chakraborty S (2011) Near-optimal constant-time admission control for DM tasks via non-uniform approximations. In: Proceedings of the 17th IEEE real-time and embedded technology and applications symposium (RTAS), Chicago, IL, USA, pp 57–67
Palopoli L, Abeni L, Lipari G (2003a) On the applications of hybrid control to CPU reservations. In: Proc of hybrid systems computation and control HSCC03. LNCS
Palopoli L, Cucinotta T, Bicchi A (2003b) Quality of service control in soft real-time application. In: Proc 42nd IEEE conference on decision and control, December 2003 pp 664–669
Palopoli L, Abeni L, Cucinotta T, Lipari G, Baruah SK (2008) Weighted feedback reclaiming for multimedia applications. In: IEEE/ACM/IFIP workshop on embedded systems for real-time multimedia. ESTImedia 2008, October 2008 pp 121–126
Park D-W, Natarajan S, Kanevsky A, Kim MJ (1995) A generalized utilization bound test for fixed-priority real-time scheduling. In: Proceedings of the 2nd international workshop on real-time systems and applications, Tokyo, Japan, October 1995, pp 73–77
Rajkumar R, Juvva K, Molano A, Oikawa S (1998) Resource kernels: A resource-centric approach to real-time and multimedia systems. In: Proc of the SPIE/ACM conference on multimedia computing and networking, January 1998
Sprunt B, Sha L, Lehoczky JP (1989) Aperiodic task scheduling for hard-real-time systems. Real-Time Syst 1:27–60
Stankovic JA, Lu C, Son SH (1998) The case for feedback control in real-time scheduling. In: Proceedings of the IEEE Euromicro conference on real-time, York, England, June 1998
Zabos A, Davis R, Burns A, Gonzalez Harbour M (2009) Spare capacity distribution using exact response-time analysis. In: 17th international conference on real-time and network systems, Paris, France, October 2009