Resource Management for Dynamic, Distributed Real-time Systems

• Tác giả: Dazhang Gu
• Người hướng dẫn: Lonnie R. Welch, Professor Of Electrical Engineering And Computer Science
• Trường học: Ohio University
• Chuyên ngành: Electrical Engineering And Computer Science
• Đề tài: Resource Management for Dynamic, Distributed Real-time Systems
• Loại tài liệu: Dissertation
• Năm xuất bản: 2005
• Địa điểm: Ann Arbor

Mục lục chi tiết

• 1. CHƯƠNG 1: INTRODUCTION
• 2. CHƯƠNG 2: LITERATURE REVIEW
• 3. CHƯƠNG 3: A TAXONOMY FOR RESOURCE ALLOCATION PROBLEMS
• 4. CHƯƠNG 4: SYSTEM MODEL
• 5. CHƯƠNG 5: ROBUST TASK ALLOCATION FOR DYNAMIC DISTRIBUTED REAL-TIME SYSTEMS
• 6. CHƯƠNG 6: ROBUST TASK ALLOCATION WITH IMPROVED ROBUSTNESS METRIC
• 7. CHƯƠNG 7: ROBUST ALLOCATION OF TASKS WITH SERVICE LEVELS
• 8. CHƯƠNG 8: CONCLUSIONS
• BIBLIOGRAPHY

Tóm tắt

I. Quản lý Tài nguyên Thời gian Thực Tổng quan Lợi ích

Hệ thống thời gian thực phân tán mang lại những đảm bảo về thời gian trong khi vẫn tăng hiệu suất thông qua tính đồng thời trong tài nguyên tính toán. Chúng rất hữu ích để xây dựng các ứng dụng thời gian thực lớn và phức tạp. Quản lý tài nguyên một cách có hệ thống là cần thiết để phân bổ tài nguyên phù hợp, đạt được những đảm bảo này. Tuy nhiên, việc triển khai các hệ thống thời gian thực phân tán vào môi trường hoạt động năng động đặt ra một vấn đề mới cho quản lý tài nguyên. Hiệu suất của các hệ thống này bị ảnh hưởng bởi các yếu tố môi trường không thể biết trước, và các kỹ thuật phân bổ tài nguyên truyền thống không áp dụng được. Một lĩnh vực nghiên cứu tích cực hiện nay là phân bổ tài nguyên với mục tiêu về độ tin cậy hệ thống thời gian thực, tìm cách tối đa hóa khả năng chịu đựng của một hệ thống đối với những thay đổi môi trường không thể đoán trước mà không gây nguy hiểm cho tính khả thi. Phân bổ mạnh mẽ như vậy làm giảm sự cần thiết của việc phân bổ lại, vốn tốn thời gian để tính toán và ban hành.

1.1. Tầm quan trọng của Quản lý Tài nguyên Thời gian Thực Phân tán

Việc quản lý tài nguyên thời gian thực trong môi trường phân tán rất quan trọng vì nó đảm bảo các ứng dụng quan trọng về thời gian đáp ứng thời hạn của chúng. Nếu không có quản lý tài nguyên hiệu quả, hệ thống có thể không đáp ứng được các yêu cầu về thời gian, dẫn đến hậu quả nghiêm trọng trong các ứng dụng như hệ thống phòng không, điều khiển công nghiệp và xe tự lái. Việc phân bổ lại tài nguyên thường tốn kém và không phù hợp với các ứng dụng thời gian thực có trạng thái phức tạp. Theo Welch và Shirazi (1999), các hệ thống phòng không là một ví dụ điển hình, việc xử lý các mối đe dọa đòi hỏi sự phân bổ tài nguyên kịp thời và chính xác.

1.2. Thách thức trong Môi trường Hoạt động Năng động

Các hệ thống thời gian thực phân tán hoạt động trong môi trường năng động phải đối mặt với những thách thức đáng kể. Các yếu tố môi trường không thể lường trước, chẳng hạn như sự thay đổi tải trọng, sự xuất hiện và biến mất của các tác vụ và sự thay đổi về khả năng của tài nguyên, có thể ảnh hưởng đến hiệu suất của hệ thống. Việc xử lý các sự kiện không chắc chắn này đòi hỏi các chiến lược phân bổ tài nguyên thích ứng và linh hoạt, có thể điều chỉnh để đáp ứng với các điều kiện thay đổi. Các thuật toán truyền thống dựa trên ước tính trường hợp xấu nhất không còn phù hợp, vì chúng có thể dẫn đến việc cung cấp tài nguyên quá mức và sử dụng tài nguyên kém hiệu quả. Cần các cơ chế tối ưu hóa tài nguyên linh hoạt hơn để đảm bảo hiệu suất và độ tin cậy tối ưu.

II. Xác định Vấn đề Hệ thống Thời gian Thực Yếu tố Môi trường

Thời gian thực của các tác vụ trong hệ thống thời gian thực phân tán, hay DDRTS, phải được xem là các hàm của các yếu tố môi trường không thể đoán trước, vì thời gian chạy của một thuật toán thường phụ thuộc vào kích thước đầu vào của chúng. Các thuật toán được triển khai trong các tác vụ thời gian thực cũng không ngoại lệ. Gu et al. Ravindran et al. (2000) nhận ra rằng việc sử dụng các hệ thống trong môi trường không thể đoán trước có thể ảnh hưởng đến kích thước đầu vào và dẫn đến thời gian thực hiện khác nhau của các tác vụ mà không thể biết trước. Không thể đưa ra thời gian thực hiện trường hợp xấu nhất (WCET) có ý nghĩa. Do đó, Tia et al. (1995); Hu et al. (2001); Wandeler et al. (2004); Manolache et al. (2004) đều chỉ ra rằng việc lập lịch và phân bổ tác vụ định kỳ truyền thống dựa trên ước tính trường hợp xấu nhất là không thể áp dụng được.

2.1. Sự phụ thuộc của Thời gian Thực hiện vào Môi trường

Thời gian thực hiện của các tác vụ trong hệ thống thời gian thực phân tán chịu ảnh hưởng đáng kể bởi các điều kiện môi trường. Các yếu tố như tải hệ thống, nhiễu mạng và sự cạnh tranh tài nguyên có thể dẫn đến các biến động trong thời gian thực hiện. Gu et al. nhấn mạnh rằng các thuật toán được sử dụng trong các tác vụ thời gian thực thường phụ thuộc vào kích thước đầu vào của chúng. Ví dụ, thời gian thực hiện của một tác vụ phát hiện mối đe dọa trong hệ thống phòng không phụ thuộc vào số lượng bản ghi radar cần được xử lý. Do đó, việc quản lý và lập lịch tài nguyên phải xem xét các sự phụ thuộc này để đảm bảo đáp ứng thời hạn.

2.2. Hạn chế của Ước tính Trường hợp Xấu nhất WCET

Các phương pháp lập lịch và phân bổ truyền thống dựa trên ước tính trường hợp xấu nhất (WCET) không phù hợp để quản lý các hệ thống thời gian thực phân tán hoạt động trong môi trường năng động. WCET là ước tính trên của thời gian thực hiện mà không tính đến các yếu tố môi trường khác nhau có thể ảnh hưởng đến thời gian thực hiện. Khi môi trường không thể đoán trước, việc sử dụng WCET có thể dẫn đến việc cung cấp tài nguyên quá mức và sử dụng tài nguyên kém hiệu quả. Tia et al. (1995) và Hu et al. (2001) chỉ ra rằng các mô hình lập lịch tác vụ định kỳ và phân bổ dựa trên WCET không áp dụng được cho các hệ thống này.

III. Phương pháp Quản lý Phân bổ Linh hoạt Đảm bảo RB

Các phương pháp tiếp cận hiện tại để giải quyết các hệ thống như vậy bao gồm phân bổ tài nguyên thích ứng, đảm bảo thời hạn xác suất và phân bổ mạnh mẽ chủ động. Tuy nhiên, các phương pháp này vẫn chưa cung cấp các giải pháp phân bổ tài nguyên thỏa đáng cho các hệ thống thời gian thực năng động. Phân bổ tài nguyên thích ứng phản ứng với những thay đổi trong môi trường và nhu cầu tài nguyên của một hệ thống bằng cách thụ động phân bổ lại hệ thống, Welch et al. (1998, 1999); Ravin- dran et al. Do đó, nó dễ bị tổn thương trước những thay đổi môi trường thường xuyên kích hoạt việc phân bổ lại tốn kém và dẫn đến tình trạng trashing, và không thể đưa ra bất kỳ đảm bảo nào. Hơn nữa, thường không khả thi để phân bổ lại các ứng dụng có trạng thái trong thời gian thực. Mô hình xác suất mô tả thời gian thực hiện tác vụ không thể đoán trước là các biến ngẫu nhiên và mục tiêu là đưa ra độ tin cậy thống kê về việc bỏ lỡ thời hạn.

3.1. Phân bổ Tài nguyên Thích ứng Ưu điểm và Nhược điểm

Phân bổ tài nguyên thích ứng là một kỹ thuật quản lý tài nguyên điều chỉnh việc phân bổ tài nguyên dựa trên các điều kiện hệ thống thời gian thực hiện và động. Các phương pháp này có thể phản ứng với những thay đổi trong môi trường và nhu cầu tài nguyên của hệ thống, nhưng chúng dễ bị tổn thương trước những thay đổi thường xuyên kích hoạt việc phân bổ lại tốn kém và dẫn đến tình trạng trashing. Hơn nữa, thường không khả thi để phân bổ lại các ứng dụng có trạng thái trong thời gian thực. Welch et al. (1998, 1999) và Ravindran et al. đã trình bày các kỹ thuật phân bổ tài nguyên thích ứng cho các hệ thống thời gian thực.

3.2. Đảm bảo Thời hạn Xác suất Ưu điểm và Hạn chế

Một cách tiếp cận khác để quản lý hệ thống thời gian thực năng động là đảm bảo thời hạn xác suất. Cách tiếp cận này mô tả thời gian thực hiện tác vụ không thể đoán trước là các biến ngẫu nhiên và mục tiêu là đưa ra độ tin cậy thống kê về việc bỏ lỡ thời hạn. Tia et al. (1995) đã đề xuất một mô hình tác vụ bán định kỳ giả định thời gian thực hiện được lập hồ sơ với các biểu đồ xác suất và đưa ra hai phương pháp để tính toán xác suất bỏ lỡ thời hạn của mỗi tác vụ. Mặc dù cách tiếp cận này có thể cung cấp thông tin hữu ích về hiệu suất của hệ thống, nhưng nó vốn thiếu bất kỳ đảm bảo thời hạn cứng nào.

IV. Giải pháp Mới Mô hình Môi trường Độ tin cậy và Thuật toán

Những thiếu sót này được giải quyết bằng nghiên cứu này. Đầu tiên, một mô hình mới tích hợp rõ ràng các yếu tố môi trường được trình bày. Nó mô tả thời gian thực hiện tác vụ là các hàm của môi trường. Thứ hai, các số liệu đặc trưng chính xác cho độ tin cậy hệ thống thời gian thực của các phân bổ được giới thiệu. Các vấn đề phân bổ tác vụ mạnh mẽ được xác định dựa trên các số liệu. Thứ ba, các thuật toán phân bổ được thiết kế sử dụng các số liệu để tìm các phân bổ khả thi và mạnh mẽ. Chúng là các thuật toán xấp xỉ với thời gian chạy và khả năng mở rộng nhanh chóng, cần thiết cho các hệ thống phân tán hiện đại có thể chứa hàng trăm bộ xử lý và hàng ngàn tác vụ. Các giới hạn lý thuyết cho chất lượng giải pháp của chúng được suy ra, cho phép đưa ra các đảm bảo về độ tin cậy hệ thống thời gian thực tối thiểu có thể đạt được bằng các thuật toán. Hiệu suất của các thuật toán được xác nhận bằng thực nghiệm bằng cách so sánh với các thuật toán cơ sở triển khai các kỹ thuật tìm kiếm tiêu chuẩn.

4.1. Mô hình hóa các Yếu tố Môi trường

Mô hình hóa chính xác các yếu tố môi trường là rất quan trọng để quản lý tài nguyên hiệu quả trong các hệ thống thời gian thực phân tán. Mô hình nên nắm bắt những đặc điểm chính của môi trường, chẳng hạn như số lượng tác vụ, mức độ sử dụng tài nguyên và nhiễu mạng. Bằng cách mô hình hóa thời gian thực hiện tác vụ là các hàm của môi trường, hệ thống có thể thích ứng với các điều kiện thay đổi và đưa ra các quyết định phân bổ tài nguyên sáng suốt. Mô hình nên cho phép tính toán và phân tích các số liệu độ tin cậy chính xác, chẳng hạn như mức độ chịu đựng của hệ thống đối với các thay đổi môi trường.

4.2. Phát triển Thuật toán Phân bổ Mạnh mẽ

Các thuật toán phân bổ tác vụ mạnh mẽ là cần thiết để tìm các phân bổ tài nguyên khả thi và mạnh mẽ trong các hệ thống thời gian thực phân tán. Các thuật toán nên xem xét các yếu tố môi trường và các số liệu độ tin cậy hệ thống thời gian thực. Chúng nên hiệu quả về mặt tính toán và có khả năng mở rộng để xử lý các hệ thống lớn với hàng trăm bộ xử lý và hàng ngàn tác vụ. Các thuật toán nên cung cấp các giới hạn lý thuyết về chất lượng giải pháp của chúng, cho phép đưa ra các đảm bảo về độ mạnh mẽ tối thiểu có thể đạt được. Hiệu suất của các thuật toán nên được xác nhận bằng thực nghiệm bằng cách so sánh với các thuật toán cơ sở triển khai các kỹ thuật tìm kiếm tiêu chuẩn.

V. Kết quả Giải pháp Quản lý Tài nguyên Ứng dụng QARMA

Thuật toán phân bổ tài nguyên được phát triển trong nghiên cứu này sẽ mang lại lợi ích cho các nhà quản lý tài nguyên. QARMA, viết tắt của Kiến trúc quản lý tài nguyên thích ứng dựa trên chất lượng của Fleeman et al. (2004), đóng vai trò là cơ sở để tích hợp các dịch vụ CORBA và cơ chế quản lý hiện có vào một khuôn khổ mạch lạc duy nhất để quản lý tài nguyên và nó có thể dễ dàng mở rộng để cho phép sử dụng các cơ chế quản lý tài nguyên mới. Nó bao gồm ba thành phần chính: Dịch vụ kho lưu trữ hệ thống, Dịch vụ quản lý tài nguyên và Dịch vụ thực thi. Dịch vụ kho lưu trữ hệ thống lưu trữ cả thông tin tĩnh và động mô tả các hệ thống phần mềm và tài nguyên trong môi trường tính toán. Thông tin được cung cấp từ các tệp đặc tả và được thu thập bởi các màn hình khác nhau trong thời gian chạy. Dịch vụ quản lý tài nguyên (hộp nét đứt) chịu trách nhiệm sử dụng thông tin trong kho lưu trữ hệ thống để quyết định những hành động nào nên được thực hiện để đảm bảo rằng các yêu cầu hiệu suất được đáp ứng và hiệu suất hệ thống được tối ưu hóa. Dịch vụ thực thi nhận hướng dẫn từ dịch vụ quản lý tài nguyên về các hành động cần thực hiện và ban hành chúng. Các hành động có thể bao gồm việc điều chỉnh cài đặt chất lượng, việc chỉ định hoặc di chuyển tác vụ và sao chép tác vụ. Thuật toán như một phần của Dịch vụ quản lý tài nguyên sẽ cung cấp cả tính khả thi và độ tin cậy trong các điều chỉnh này.

5.1. Kiến trúc QARMA cho Quản lý Tài nguyên Linh hoạt

Kiến trúc QARMA cung cấp một khuôn khổ mạch lạc để tích hợp các dịch vụ CORBA và cơ chế quản lý hiện có để quản lý tài nguyên. Nó cho phép quản lý tài nguyên linh hoạt bằng cách cung cấp một cách để điều chỉnh cài đặt chất lượng, chỉ định hoặc di chuyển tác vụ và sao chép tác vụ. QARMA bao gồm ba thành phần chính: Dịch vụ kho lưu trữ hệ thống, Dịch vụ quản lý tài nguyên và Dịch vụ thực thi. Dịch vụ kho lưu trữ hệ thống lưu trữ cả thông tin tĩnh và động mô tả các hệ thống phần mềm và tài nguyên trong môi trường tính toán. Dịch vụ quản lý tài nguyên chịu trách nhiệm sử dụng thông tin trong kho lưu trữ hệ thống để quyết định những hành động nào nên được thực hiện để đảm bảo rằng các yêu cầu hiệu suất được đáp ứng và hiệu suất hệ thống được tối ưu hóa. Dịch vụ thực thi nhận hướng dẫn từ dịch vụ quản lý tài nguyên về các hành động cần thực hiện và ban hành chúng.

5.2. Tối ưu hóa Hiệu suất và Độ tin cậy với QARMA

QARMA cho phép các nhà quản lý tài nguyên tối ưu hóa hiệu suất và độ tin cậy của các hệ thống thời gian thực phân tán. Bằng cách sử dụng thuật toán phân bổ tài nguyên được phát triển trong nghiên cứu này, QARMA có thể đảm bảo cả tính khả thi và độ tin cậy trong các điều chỉnh. Điều này có nghĩa là hệ thống có thể đáp ứng các yêu cầu về thời gian của nó và có thể chịu đựng các thay đổi môi trường mà không gây nguy hiểm cho hiệu suất của nó. Do đó, QARMA cung cấp một giải pháp hiệu quả để quản lý tài nguyên trong các hệ thống thời gian thực phân tán.

VI. Tương lai Phát triển Ứng dụng Quản lý Tài nguyên

Nghiên cứu này đóng góp vào lĩnh vực quản lý tài nguyên cho các hệ thống thời gian thực phân tán bằng cách cung cấp một giải pháp toàn diện xem xét các yếu tố môi trường và tìm cách tối đa hóa độ tin cậy hệ thống thời gian thực. Thuật toán phân bổ tài nguyên được phát triển trong nghiên cứu này có thể được sử dụng để cải thiện hiệu suất và độ tin cậy của nhiều ứng dụng khác nhau, chẳng hạn như hệ thống phòng không, điều khiển công nghiệp và xe tự lái. Nghiên cứu cũng mở ra những con đường mới cho nghiên cứu trong tương lai, chẳng hạn như phát triển các thuật toán phân bổ tài nguyên thích ứng hơn và khám phá các ứng dụng của quản lý tài nguyên trong các hệ thống thời gian thực phân tán mới nổi.

6.1. Hướng Nghiên Cứu Tương Lai trong Quản lý Tài nguyên

Có một số hướng nghiên cứu trong tương lai trong lĩnh vực quản lý tài nguyên cho các hệ thống thời gian thực phân tán. Một hướng là phát triển các thuật toán phân bổ tài nguyên thích ứng hơn có thể phản ứng với những thay đổi trong môi trường theo thời gian thực. Một hướng khác là khám phá các ứng dụng của quản lý tài nguyên trong các hệ thống thời gian thực phân tán mới nổi, chẳng hạn như điện toán đám mây thời gian thực và internet vạn vật (IoT) thời gian thực. Ngoài ra, điều quan trọng là phải phát triển các phương pháp mới để mô hình hóa và phân tích các yếu tố môi trường, cũng như để đánh giá hiệu suất của các thuật toán quản lý tài nguyên.

6.2. Tác động của Quản lý Tài nguyên đến Ứng dụng Tương lai

Quản lý tài nguyên có tiềm năng tác động đáng kể đến hiệu suất và độ tin cậy của nhiều ứng dụng khác nhau trong tương lai. Bằng cách đảm bảo rằng tài nguyên được phân bổ một cách hiệu quả và hiệu quả, các hệ thống có thể đáp ứng các yêu cầu về thời gian của chúng và có thể chịu đựng các thay đổi môi trường. Điều này đặc biệt quan trọng trong các ứng dụng quan trọng về thời gian, chẳng hạn như hệ thống phòng không, điều khiển công nghiệp và xe tự lái. Khi các hệ thống thời gian thực phân tán tiếp tục trở nên phức tạp hơn và được sử dụng rộng rãi hơn, vai trò của quản lý tài nguyên sẽ ngày càng trở nên quan trọng hơn.