Resource Management for Dynamic, Distributed Real-time Systems

Luận án tiến sĩ về quản lý tài nguyên cho hệ thống thời gian thực phân tán linh hoạt. Nghiên cứu giải pháp tối ưu, đảm bảo tính ổn định trong môi trường động.

• 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.

Nội dung chính

Tổng quan luận án

Nghiên cứu của Dazhang Gu (2005) mang tiêu đề "Resource Management for Dynamic, Distributed Real-time Systems" (Quản lý tài nguyên cho các hệ thống thời gian thực phân tán, động - DDRTS), được thực hiện dưới sự hướng dẫn của Giáo sư Lonnie R. Welch tại Trường Kỹ thuật Điện và Khoa học Máy tính, Trường Cao đẳng Kỹ thuật và Công nghệ Russ thuộc Đại học Ohio. Luận án giải quyết bài toán cốt lõi trong việc triển khai các hệ thống thời gian thực phân tán vào những môi trường vận hành biến động, nơi các yếu tố môi trường không thể xác định trước và không tồn tại ước lượng thời gian thực thi xấu nhất (Worst-Case Execution Time - WCET) có ý nghĩa.

Khoảng trống nghiên cứu được chỉ rõ: các kỹ thuật phân bổ tài nguyên tĩnh truyền thống dựa trên WCET cố định hoàn toàn không áp dụng được cho hệ thống động; trong khi đó, các phương pháp phân bổ thích ứng thụ động (adaptive allocation) dễ dẫn đến hiện tượng đảo chuyển (thrashing) do tái phân bổ liên tục và không phù hợp với các ứng dụng có trạng thái (stateful applications). Các tiếp cận xác suất (probabilistic models) không thể đưa ra bảo đảm hạn định ngặt (hard deadlines), còn các nghiên cứu phân bổ bền vững chủ động (proactive robust allocation) trước đó chỉ áp dụng các chỉ số thô (như chuẩn $l_2$), giả định tải đơn biến tuyến tính hoặc bỏ qua các điều kiện khả thi về lập lịch thời gian thực trên từng bộ xử lý.

Mục tiêu nghiên cứu tổng quát của luận án là phát triển một giải pháp phân bổ tài nguyên có bảo đảm thời gian thực tường minh, đồng thời tối đa hóa khả năng dung thứ (độ bền vững - robustness) trước các biến đổi môi trường mà không cần tái phân bổ. Tác giả cụ thể hóa thành 4 nhiệm vụ nghiên cứu:

1. Xây dựng mô hình tính toán thời gian thực mới tích hợp các biến môi trường vào hàm thời gian thực thi của tác vụ.
2. Thiết lập hệ thống phân loại toàn diện ($R|T|O|E$) cho các bài toán phân bổ tài nguyên và xác định các chỉ số định lượng độ bền vững đa chiều.
3. Thiết kế các thuật toán xấp xỉ phân bổ tài nguyên bền vững, chứng minh các biên tỷ số xấp xỉ lý thuyết (approximation ratios) dưới lập lịch Rate-Monotonic Scheduling (RMS) và Earliest Deadline First (EDF).
4. Mở rộng bài toán phân bổ bền vững cho các hệ thống tác vụ có cấp độ dịch vụ (service levels/QoS) nhằm tối ưu hóa hàm thỏa dụng (utility).

Đối tượng nghiên cứu là các tác vụ định kỳ độc lập có thời gian thực thi phụ thuộc vào môi trường, được phân bổ trên tập hợp các bộ xử lý đồng nhất loosely-coupled. Phạm vi ứng dụng tập trung vào các hệ thống điều khiển phân tán phức tạp như hệ thống phòng thủ phòng không (air defense system với các tác vụ phát hiện, đánh chặn, dẫn đường tên lửa), hệ thống giám sát tòa nhà và phương tiện thông minh.

---

Tổng quan tài liệu và vị trí của luận án

Tác giả Dazhang Gu hệ thống hóa các hướng nghiên cứu liên quan đến lập lịch và phân bổ tài nguyên thời gian thực theo các nhóm tiếp cận chính:

                                  Các hướng tiếp cận quản lý tài nguyên
Phân bổ thích ứng (Adaptive)   Mô hình xác suất (Probabilistic)   Dòng sự kiện & Đa khung    Phân bổ bền vững chủ động
- Welch & Shirazi (1999)      - Tia et al. (1995)                - Wandeler et al. (2004)   - Gertphol et al. (2002)
- Welch et al. (1998)         - Hu et al. (2001)                 - Chen et al. (2000)       - Ali et al. (2003)
- Ravindran et al. (2000)     - Manolache et al. (2004)                                     - Juedes et al. (2003, 2004)
                                                                                            - Shestak et al. (2005)

1. Phân bổ tài nguyên thích ứng (Adaptive Allocation): Welch và Shirazi (1999), Welch và cộng sự (1998), Ravindran và cộng sự (2000) nghiên cứu cơ chế phản ứng thụ động với sự thay đổi của môi trường thông qua việc tái cấu hình và di trú tác vụ. Nhược điểm là chi phí tái phân bổ cao, gây trễ và không thể áp dụng cho các ứng dụng có trạng thái phức tạp.
2. Mô hình thống kê và xác suất (Probabilistic Deadline Guarantee): Tia và cộng sự (1995) đề xuất mô hình tác vụ bán định kỳ với phân phối xác suất thời gian thực thi; Hu và cộng sự (2001), Manolache và cộng sự (2004) mở rộng cho hệ thống nhiều bộ xử lý có phụ thuộc tác vụ và dùng Tabu Search để tối ưu hóa độ lệch vượt ngưỡng xác suất trượt hạn định. Hạn chế là chi phí đánh giá không gian trạng thái rất lớn và không bảo đảm được hạn định ngặt.
3. Mô hình dòng sự kiện và đa khung: Wandeler và cộng sự (2004) dùng mô hình Event Stream dựa trên các đường cong tỷ lệ loại sự kiện (type-rate curves); Chen và cộng sự (2000) đề xuất mô hình tác vụ đa khung tổng quát phân tán (DGMF). Tuy nhiên, các chuỗi sự kiện hoặc khung tác vụ phải được biết trước.
4. Phân bổ tác vụ trên hệ thống phân tán: Các công trình kinh điển của Stone (1977), Lo (1988) dùng lát cắt đồ thị (max flow/min cut); Chu và Lan (1987) tối thiểu hóa tải nút cổ chai; Bettati và Liu (1990, 1992) giải quyết lập lịch dòng (flow shop) và quan hệ thứ tự; Natale và Stankovic (1994) giải bài toán chia hạn định con (slicing problem); Burns và cộng sự (1993), Tindell và cộng sự dùng tôi luyện ảo (Simulated Annealing); Peng và cộng sự (1997), Hou và Shin (1997) dùng nhánh và cận (Branch-and-Bound); Lee và cộng sự (1999a) nghiên cứu phân bổ QoS đa chiều tối ưu hóa thỏa dụng; Ali và cộng sự (2002) phát triển giải thuật heuristic max-min thích ứng ràng buộc host.
5. Tiền đề phân bổ bền vững: Gertphol và cộng sự (2002) dùng quy hoạch nguyên hỗn hợp (MIP) để tìm mức tăng tải cực đại cho một biến duy nhất nhưng bỏ qua kiểm tra khả thi lập lịch; Ali và cộng sự (2003) đề xuất chỉ số bán kính nhiễu loạn cực đại dựa trên chuẩn $l_2$ nhưng không xây dựng thuật toán tối ưu hóa; Juedes, Welch và cộng sự (2004) phát triển thuật toán First-Fit kết hợp tìm kiếm nhị phân cho hệ thống một biến tải, chứng minh tỷ số xấp xỉ trong Juedes và cộng sự (2003); Aber và cộng sự (2004), Zhao và cộng sự (2005) mở rộng sang các thuật toán heuristic và bản sao tác vụ.

Vị trí của luận án được xác lập thông qua việc giải quyết triệt để các hạn chế trên: chuyển từ không gian một chiều sang đa biến môi trường ngẫu nhiên/không xác định, sử dụng chỉ số độ bền vững bảo đảm tính phi thay thế giữa các chiều, kết hợp chặt chẽ với điều kiện khả thi RMS/EDF và chứng minh các tỷ số xấp xỉ lý thuyết chặt chẽ.

---

Cơ sở lý thuyết và phương pháp nghiên cứu

Luận án kết hợp giữa lý thuyết lập lịch thời gian thực, giải tích toán học hàm lồi và phương pháp xấp xỉ thuật toán kết hợp mô phỏng thực nghiệm:

• Cơ sở lý thuyết lập lịch thời gian thực: Sử dụng mô hình tác vụ định kỳ của Liu (2000b). Tính khả thi của việc phân bổ tác vụ lên từng bộ xử lý đơn lẻ được bảo đảm thông qua các ngưỡng sử dụng tài nguyên xấu nhất:
  • Đối với RMS: Áp dụng biên sử dụng của Oh và Baker (1998) cho thuật toán First-Fit, tiệm cận ở mức $\sqrt{2}-1 \approx 0{,}414$.
  • Đối với EDF: Áp dụng biên sử dụng của Lopez và cộng sự (2004) với cận $\frac{m+1}{2m}$ hoặc $\frac{\beta m + 1}{\beta + 1}$.
• Công cụ giải tích: Khai triển Taylor bậc $k$ có số dư dạng tích phân để đánh giá xu hướng tăng trưởng của hàm tổng độ khả dụng hệ thống $U(w)$ mà không cần biết dạng giải tích tường minh cụ thể.
• Phương pháp nghiên cứu thực nghiệm và đánh giá:
  • Mô phỏng thực nghiệm trên các tập dữ liệu bài toán quy mô nhỏ, trung bình và lớn (lên tới hàng trăm bộ xử lý và hàng ngàn tác vụ).
  • So sánh đối chuẩn thuật toán xấp xỉ đề xuất (RAFF-n, Approx) với các thuật toán chuẩn: Tìm kiếm ngẫu nhiên (Random Search - RARN-n), Leo đồi (Hill-Climbing - RAHC-n), Tôi luyện ảo (Simulated Annealing - RASA-n/SA), và Nhánh và cận tối ưu (Branch-and-Bound - RABB-n).
  • Kiểm định ý nghĩa thống kê (significance test) để so sánh chất lượng nghiệm và thời gian thực thi (running time).

---

Nội dung chính theo từng chương

Chương 1: Introduction

Chương này đặt nền móng nghiên cứu bằng việc phân tích ca điển hình: Hệ thống phòng thủ tên lửa phòng không tổng quát (generic air defense system) dựa trên Welch và Shirazi (1999). Hệ thống gồm ba tác vụ định kỳ liên kết: tác vụ phát hiện (detect), tác vụ kích hoạt/phóng (engage), và tác vụ dẫn đường tên lửa (guide missile). Thời gian thực thi của các tác vụ phụ thuộc trực tiếp vào số lượng vệt radar ($w_1$), số lượng mối đe dọa và số lượng tên lửa đang bay ($w_2$).

Tác giả chỉ rõ sự thất bại của các kỹ thuật phân bổ tĩnh khi môi trường thay đổi, đồng thời định vị giải pháp phân bổ bền vững trong Kiến trúc Quản lý Tài nguyên Thích ứng Dựa trên Chất lượng (Quality-based Adaptive Resource Management Architecture - QARMA) của Fleeman và cộng sự (2004). Thuật toán phân bổ bền vững đóng vai trò là hạt nhân ra quyết định trong Dịch vụ Quản lý Tài nguyên (Resource Management Service) của QARMA.

Chương 2: Literature Review

Chương 2 tổng thuật chi tiết toàn bộ các tài liệu học thuật theo hai trục: các nghiên cứu xử lý môi trường động (thích ứng, xác suất, dòng sự kiện, phân bổ bền vững) và các nghiên cứu phân bổ tác vụ phân tán tổng quát (lập lịch toàn cục, đa chiều QoS, phân bổ có ràng buộc giao tiếp và hạn định con). Tác giả chỉ ra các điểm nghẽn thuật toán và chứng minh sự cần thiết phải có một cách tiếp cận hình thức hóa toàn diện.

Chương 3: A Taxonomy for Resource Allocation Problems

Tác giả xây dựng hệ thống phân loại $R|T|O|E$ đại diện cho 4 trường thuộc tính của bài toán phân bổ tài nguyên có xét đến yếu tố môi trường:

Trường thuộc tính	Ký hiệu	Các giá trị và ý nghĩa phân loại
Resource (R)	$R_c$, $R_d$	- $R_c$ (Bậc tài nguyên): 1. Đơn lớp (single class), 2. Đa lớp (multiple class). - $R_d$ (Phân chia): 1. Chia được (divisible), i. Không chia được (indivisible).
Task (T)	$T_b, T_p, T_s, T_c, T_e$	- $T_b$ (Hành vi): 1. Định kỳ (periodic), 2. Kích hoạt sự kiện (event-driven), 3. Hỗn hợp. - $T_p$ (Phụ thuộc): 0. Độc lập, 1. Chuỗi (chain), 2. Đồ thị (graph). - $T_s$ (Biến dịch vụ): 0. Không, 1. Đơn biến, 2. Đa biến. - $T_c$ (Liên tục dịch vụ): 1. Liên tục, 2. Rời rạc. - $T_e$ (Hồ sơ thực thi): 1. Hằng số, 2. Tuyến tính, 3. Tăng không giảm lồi, 4. Tăng không giảm, 5. Tùy ý.
Objective (O)	$O_m, O_c, O_a$	- $O_m$ (Mục tiêu): 0. Không, 1. Độ bền vững (robustness), 2. Hàm chi phí, 3. Thỏa dụng (utility), 4. Độ tin cậy. - $O_c$ (Hạn định): 1. Mềm (soft), 2. Vững (firm), 3. Ngặt (hard). - $O_a$ (Ràng buộc phụ): 0. Không, 1-2. Sống sót (survivability), 3. An ninh (security).
Environment (E)	$E_r, E_b, E_c, E_v$	- $E_r$ (Mức độ liên quan): 0. Không, 1. Đơn biến, 2. Đa biến. - $E_b$ (Biên biến môi trường): 1. Không chặn (unbounded), 2. Bị chặn (bounded). - $E_c$ (Tính liên tục): 1. Liên tục, 2. Rời rạc. - $E_v$ (Dạng biến thiên): 1. Hàm thời gian, 2. Thống kê, 3. Mẫu hình đều, 4. Hỗn loạn/Không biết trước (chaotic/unknown).

Dựa trên quan hệ bao hàm (dominance), tác giả phân tích không gian 32 bài toán kết hợp từ trường $E$, xác định bài toán mục tiêu trọng tâm của luận án là $1|2,1,0,0,-,3/4|1,3,0|2,1,2,4$ (Chương 5, 6) và $1|2,1,0,2,2,4|3,3,0|2,1,2,4$ (Chương 7).

Chương 4: System Model

Chương này mô hình hóa hệ thống gồm $n$ tác vụ định kỳ $S = {T_1, \dots, T_n}$ với chu kỳ $p_i$, hạn định $d_i = p_i$, thực thi trên $m$ bộ xử lý đồng nhất $H = {P_1, \dots, P_m}$. Môi trường được biểu diễn bằng vector $\vec{w} = (w_1, w_2, \dots, w_l)$, trong đó $w_i \in \mathbb{Z}^+$. Thời gian thực thi của tác vụ $T_i$ là hàm $e_i(\vec{w})$. Tổng độ khả dụng hệ thống là:

$$U(\vec{w}) = \sum_{i=1}^n \frac{e_i(\vec{w})}{p_i}$$

Trong đó $U(0) = \delta m$ đại diện cho phần sử dụng độc lập với môi trường. Phân bổ $M: S \rightarrow H$ là ánh xạ nhiều-một từ tập tác vụ sang tập bộ xử lý.

Chương 5: Robust Task Allocation for Dynamic Distributed Real-time Systems

Chương 5 thiết lập chỉ số độ bền vững đa chiều có trọng số và giải thuật phân bổ:

• Hệ thống động bậc $k$ (Order-$k$ dynamic DDRTS): Định nghĩa hàm $f(w)$ chuẩn tắc đến bậc $k$ khi $f^{(i)}(w) \ge 0$ với mọi $1 \le i \le k+1$ và $f^{(k)}(w) \neq 0$.
• Tỷ số xấp xỉ cho bài toán một chiều (RAFF-1):
  • Lập lịch RMS: Tỷ số tuyệt đối $r_{FF}^1(RM) < \frac{\sqrt{2}-2\delta}{\sqrt{2}-1-\delta}$. Tỷ số tiệm cận cho hệ thống bậc $k$: $$r_{FF}^{1*}(RM) \le \left(\frac{1-\delta}{\sqrt{2}-1-\delta}\right)^{1/k}$$
  • Lập lịch EDF: Tỷ số tuyệt đối $r_{FF}^1(EDF) < \frac{2-2\delta}{1+1/m-2\delta}$. Tỷ số tiệm cận cho hệ thống bậc $k$: $$r_{FF}^{1*}(EDF) \le \left(\frac{2-2\delta}{1+1/m-2\delta}\right)^{1/k}$$
• Chỉ số độ bền vững đa chiều: Phê phán chuẩn $l_2$ do tính chất bù trừ sai lệch thực tế; tác giả đề xuất chỉ số cực tiểu hóa có trọng số: $$R(\vec{W}) \equiv \min_{1 \le i \le l} (k_i W_i) \quad (k_i > 0, W_i \ge 0)$$
• Thuật toán RAFF-n được thiết kế dựa trên kỹ thuật thu hẹp không gian tìm kiếm và kiểm tra tính khả thi bằng First-Fit. Kết quả thực nghiệm cho thấy RAFF-n đạt chất lượng tiệm cận nghiệm tối ưu của nhánh và cận (RABB-n) nhưng thời gian chạy thấp hơn nhiều bậc độ phức tạp so với RASA-n, RAHC-n và RARN-n.

Chương 6: Robust Task Allocation with Improved Robustness Metric

Chương 6 hoàn thiện chỉ số độ bền vững chính xác hơn bằng cách xem xét chi tiết biên vùng khả thi, khắc phục hiện tượng đánh giá dưới mức độ chịu tải khi các tác vụ phân tán không đồng đều. Tác giả phát triển thuật toán xấp xỉ Approx, chứng minh các cận dưới độ bền vững (robustness lower bounds) đối với các hàm khối lượng công việc tuyến tính và hàm tổng quát, đồng thời kiểm định ý nghĩa thống kê về số lượng vi phạm hạn định và tải tối đa chịu đựng được.

Chương 7: Robust Allocation of Tasks with Service Levels

Mở rộng mô hình cho các hệ thống có mức dịch vụ (service levels). Mỗi tác vụ có nhiều cấu hình chất lượng khác nhau, mang lại giá trị thỏa dụng (utility) khác nhau. Luận án xây dựng thuật toán phân bổ vừa tối đa hóa hàm thỏa dụng hệ thống, vừa bảo đảm độ bền vững trước biến động môi trường, chứng minh cận dưới lý thuyết của hàm thỏa dụng và đối sánh hiệu năng với Simulated Annealing và Random Search.

Chương 8: Conclusions

Chương tổng kết toàn bộ các kết quả đạt được, khẳng định tính hiệu quả của mô hình toán học, hệ thống phân loại, các chỉ số độ bền vững và các thuật toán xấp xỉ phân bổ tài nguyên cho DDRTS.

---

Kết quả và những đóng góp mới

Luận án tự đúc kết các đóng góp học thuật và thực tiễn:

1. Về mặt lý luận và mô hình hóa:
   • Đề xuất mô hình tính toán thời gian thực mới tích hợp các biến môi trường trực tiếp vào hàm thời gian thực thi $e_i(\vec{w})$, thoát ly khỏi giả định WCET cố định.
   • Xây dựng bảng phân loại $R|T|O|E$ gồm 4 trường và 14 thuộc tính, cung cấp khung phân loại toàn diện cho các bài toán phân bổ tài nguyên thời gian thực chịu ảnh hưởng môi trường.
   • Định nghĩa khái niệm hệ thống động bậc $k$ (order-$k$ dynamic DDRTS) dựa trên đạo hàm của hàm khả dụng.
   • Xây dựng chỉ số độ bền vững đa chiều có trọng số khắc phục nhược điểm của chuẩn $l_2$.
2. Về mặt thuật toán và phân tích lý thuyết:
   • Chứng minh giải tích các tỷ số xấp xỉ tuyệt đối và tiệm cận ($r_{FF}^1, r_{FF}^{1*}$) cho thuật toán phân bổ First-Fit dưới cả hai cơ chế lập lịch RMS và EDF. Chứng minh rằng hệ thống có bậc động học $k$ càng cao thì tỷ số xấp xỉ tiệm cận càng tiệm cận 1.
   • Thiết kế các thuật toán xấp xỉ thời gian đa thức (RAFF-n, Approx) có khả năng mở rộng cho các hệ thống quy mô lớn hàng trăm node.
3. Về mặt thực tiễn và ứng dụng:
   • Tích hợp trực tiếp thuật toán vào dịch vụ Resource Management Service thuộc kiến trúc QARMA (Fleeman et al., 2004), cho phép ứng dụng thời gian thực tự động thích ứng với biến động môi trường mà không gây trễ do tái phân bổ.

---

Hạn chế và hướng nghiên cứu tiếp

Dựa trên các phân tích trong văn bản:

• Hạn chế:
  • Nghiên cứu tập trung chủ yếu vào các tác vụ định kỳ độc lập; các ràng buộc phụ thuộc phức tạp dạng chuỗi hoặc đồ thị dòng công việc (task graphs, end-to-end precedence) chưa được tích hợp hoàn toàn trong thuật toán đa chiều ở Chương 5 và 6.
  • Giả định các bộ xử lý là đồng nhất (identical processors) và mô hình truyền thông chưa xét đầy đủ độ trễ mạng bất định chi tiết trong thuật toán phân bổ bền vững đa chiều.
• Hướng nghiên cứu tiếp:
  • Mở rộng thuật toán phân bổ bền vững cho các hệ thống phần cứng không đồng nhất (heterogeneous COTS hosts).
  • Tích hợp mô hình phân bổ bền vững cho các tác vụ có phụ thuộc phức tạp, truyền thông không đồng bộ và có ràng buộc độ trễ đầu cuối (end-to-end latency).
  • Triển khai thử nghiệm thực tế trên các nền tảng phân tán quy mô lớn sử dụng chuẩn CORBA.

---

Giá trị tham khảo

• Đối với nghiên cứu sinh và giảng viên ngành Khoa học Máy tính / Hệ thống nhúng:
  • Chương 3 cung cấp khung lý thuyết phân loại $R|T|O|E$ hữu ích cho việc định vị đề tài nghiên cứu mới.
  • Kỹ thuật chứng minh tỷ số xấp xỉ bằng khai triển Taylor bậc $k$ trong Chương 5 là phương pháp luận mẫu mực để phân tích thuật toán lập lịch thời gian thực.
• Đối với kỹ sư hệ thống và chuyên gia phát triển phần mềm quốc phòng / hàng không vũ trụ:
  • Cung cấp mô hình định lượng tải môi trường và thuật toán phân bổ tài nguyên giúp các hệ thống radar, điều khiển hỏa lực và giám sát tự hành tránh được tình trạng trượt hạn định khi quá tải đột ngột.

---

Câu hỏi thường gặp

1. Tại sao chuẩn $l_2$ lại không phù hợp để làm chỉ số độ bền vững cho hệ thống nhiều biến môi trường?
Chuẩn $l_2$ đo bán kính hình cầu nhiễu loạn cực đại, ngầm định rằng các biến môi trường có thể bù trừ thay thế cho nhau. Một điểm nằm trên mặt cầu có thể đạt giá trị cực đại khi chỉ một biến môi trường đạt giá trị lớn trong khi các biến khác bằng 0. Trong thực tế (ví dụ hệ thống phòng không), việc xử lý được 15 vệt radar mà không xử lý được tên lửa nào ($15, 0$) không thể thay thế cho khả năng xử lý đồng thời 5 vệt radar và 5 tên lửa ($5, 5$), mặc dù $\sqrt{15^2+0^2} = 15 > \sqrt{5^2+5^2} \approx 7{,}07$. Chuẩn $l_2$ sẽ dẫn thuật toán tối ưu hóa chọn sai cấu hình phân bổ.

2. Khái niệm "Order-$k$ dynamic DDRTS" được định nghĩa như thế nào và có ý nghĩa gì đối với tỷ số xấp xỉ?
Một hệ thống là động bậc $k$ nếu hàm thời gian thực thi của mọi tác vụ không giảm và hàm tổng độ khả dụng $U(w)$ là chuẩn tắc bậc $k$ ($U^{(i)}(w) \ge 0$ với mọi $1 \le i \le k+1$, và $U^{(k)}(w) \neq 0$). Ý nghĩa: bậc $k$ càng lớn thì tốc độ tăng trưởng của độ khả dụng càng nhanh, giúp thuật toán First-Fit tiệm cận nghiệm tối ưu nhanh hơn, với tỷ số xấp xỉ tiệm cận được rút căn bậc $k$, tức $\left(\frac{1-\delta}{\sqrt{2}-1-\delta}\right)^{1/k}$ đối với RMS.

3. Tỷ số xấp xỉ tuyệt đối của thuật toán RAFF-1 dưới cơ chế lập lịch RMS và EDF là bao nhiêu?

• Dưới RMS: $r_{FF}^1(RM) < \frac{\sqrt{2}-2\delta}{\sqrt{2}-1-\delta}$, trong đó $\delta = \frac{U(0)}{m}$ là tỷ lệ sử dụng độc lập với môi trường trên $m$ bộ xử lý.
• Dưới EDF: $r_{FF}^1(EDF) < \frac{2-2\delta}{1+1/m-2\delta}$.

4. Khung phân loại $R|T|O|E$ gồm những trường chính nào và phân loại bài toán của Chương 5 như thế nào?
Khung $R|T|O|E$ gồm: Resource (Tài nguyên), Task (Tác vụ), Objective (Mục tiêu và ràng buộc), Environment (Biến môi trường). Bài toán trong Chương 5 được phân loại là $1|2,1,0,0,-,3/4|1,3,0|2,1,2,4$, đại diện cho: tài nguyên đơn lớp không chia cắt; tác vụ định kỳ độc lập không có biến dịch vụ, hồ sơ thời gian tăng không giảm lồi/không giảm; mục tiêu tối đa hóa độ bền vững với hạn định ngặt; môi trường đa biến, không chặn, giá trị rời rạc và biến thiên không xác định trước.

---

Kết luận

Luận án của Dazhang Gu giải quyết bài toán quản lý tài nguyên trong các hệ thống thời gian thực phân tán động bằng phương pháp phân bổ bền vững chủ động. Tác giả xây dựng hoàn chỉnh khung phân loại lý thuyết $R|T|O|E$, mô hình tính toán phụ thuộc môi trường và chỉ số độ bền vững phi thay thế. Các thuật toán xấp xỉ dựa trên First-Fit được phát triển với các chứng minh biên tỷ số xấp xỉ toán học chặt chẽ dưới cơ chế lập lịch RMS và EDF. Kết quả nghiên cứu cung cấp cơ sở khoa học và giải pháp thuật toán tin cậy cho các hệ thống thời gian thực phức tạp vận hành trong môi trường biến động.

Trích đoạn nội dung tài liệu

Resource Management for Dynamic, Distributed Real-time Systems A dissertation presented to the faculty of the Russ College of Engineering the Russ and Technology College of Engineering andofTechnology Ohio University In partial fulfillment of the requirements for the degree Doctor of Philosophy Dazhang Gu November 2005 UMI Number: 3247487 UMI Microform 3247487 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code. ProQuest Information and Learning Company 300 North Zeeb Road P.

Box 1346 Ann Arbor, MI 48106-1346 This dissertation entitled Resource Management for Dynamic, Distributed Real-time Systems by Dazhang Gu has been approved for the School of Electrical Engineering and Computer Science and the Russ College of Engineering and Technology by Lonnie R. Welch Professor of Electrical Engineering and Computer Science Dennis Irwin Dean, Russ College of Engineering and Technology Gu, Dazhang. Electrical Engineering and Computer Science Resource Management for Dynamic, Distributed Real-time Systems (114pp.) Director of Dissertation: Lonnie R. Welch A current challenge facing resource management is the need to deploy real-time systems in dynamic operational environments.

The systems are often affected by un- predictable environmental factors that cannot be known a priori and have no mean- ingful worst-case estimates. As a result, traditional resource allocation techniques do not apply. Current attempts to address these systems have been limited. This research addresses the resource management problem for dynamic, distrib- uted real-time systems (DDRTSs).

A resource allocation approach is developed for these systems that offers explicit real-time guarantees with maximized tolerance (ro- bustness) of unpredictable environment changes. This work has developed (1) a real-time computing model that incorporates environmental factors, (2) metrics that characterize robustness, and (3) resource allocation algorithms that find feasible, robust allocations. The approach is validated by both theoretical analysis and ex- perimentation. The main contribution of the work is a reliable resource management solution for DDRTSs, which allows real-time applications to be versatile in real world environments.

Welch Professor of Electrical Engineering and Computer Science 4 Table of Contents Abstract 3 List of Figures 6 List of Tables 8 1 Introduction 9 2 Literature Review 15 3 A Taxonomy for Resource Allocation Problems 26 3.2 Classification of existing work. 31 4 System Model 34 5 Robust Task Allocation for Dynamic Distributed Real-time Sys- tems 37 5.1 Robust allocation for the one-dimensional problem .1 Order of dynamic real-time systems .2 A multi-dimensional robustness metric .1 Search space reduction .3 Robust allocation for the multi-dimensional problem. 66 6 Robust Task Allocation with Improved Robustness Metric 67 6.1 An accurate robustness metric .2 A robust allocation algorithm .3 Analysis of the algorithm .1 A robustness lower bound for linear workload functions .2 A robustness lower bound for general workload functions .3 Proofs of optimality bounds .5 Comparisons of the robustness metrics. 94 7 Robust Allocation of Tasks with Service Levels 96 7.1 Service level extensions to the system model .2 A robust allocation algorithm .3 Analysis of the algorithm.

106 8 Conclusions 107 Bibliography 109 6 List of Figures 1.1 A generic air defense system.2 The QARMA architecture.1 Example of a general control system.1 Asymptotic approximation ratio as a function of order k and indepen- dent utilization δ.2 Contour lines of robustness metric in two dimensions.3 Different tangents between feasibility boundary and robustness metric contour.4 Illustration of the search for an allocation with the maximum robust- ness metric.5 Comparisons of robustness values found by RAFF-n, RABB-n, and bounds from absolute and asymptotic approximation ratios under RMS or EDF scheduling for three orders of DDRTS.6 Comparisons of robustness values found by RAFF-n, RARN-n, RAHC- n, and RASA-n for large problem instances under RMS and EDF scheduling for three orders of DDRTS .7 Comparisons of running times of RAFF-n, RARN-n, RAHC-n, and RASA-n for large problem instances under RMS or EDF scheduling for three orders of DDRTS .8 Significance test for RAFF-n with RMS and EDF scheduling systems under three orders of DDRTS.1 Deficiencies of two previous metrics.2 Illustration of the new metric with l = 2 and l = 3.3 Comparisons of the approximation algorithm performance with its analytical lower bound in small, medium, and large instances.