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.

Trường đại học

Ohio University

Người đăng

Ẩn danh

Thể loại

Dissertation

2005

115
2
0

Phí lưu trữ

35 Point

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ÀI LIỆU LIÊN QUAN

Ứng dụng công nghệ thông tin trong dạy học tại trường

124
81
1

Ứng dụng Active Learning trong Lựa Chọn Dữ Liệu Gán Nhãn

53
20
0

Kỹ Thuật Kiểm Thử Dòng Dữ Liệu Tĩnh Trong Luận Văn Thạc

56
18
0

Tóm tắt luận án tiếng Việt cho sinh viên

28
13
0

Bản đồ ngập lụt và giải pháp phòng chống thiên tai cho

166
14
0

Nghiên cứu thuật toán mã hóa deoxysii với xác thực

66
3
0

Xây dựng Cloud Storage và VPN trong Điện Toán Đám Mây

83
3
0

Chương trình thực thi mã ECIES với xác thực dựa trên

71
8
0

Ứng dụng mạng neural trong phát hiện xâm nhập trái phép

67
6
0

Nghiên cứu thuật toán mã hóa xác thực Norx cho luận văn

73
7
0
Luận án tiến sĩ resource management for dynamic distributed real time systems

Bạn đang xem trước tài liệu:

Luận án tiến sĩ resource management for dynamic distributed real time systems

Tải đầy đủ

Tài liệu Resource Management for Dynamic, Distributed Real-time Systems trình bày các phương pháp và chiến lược quản lý tài nguyên trong môi trường hệ thống thời gian thực phân tán và biến động liên tục. Người đọc sẽ nắm được cách phân bổ tài nguyên động nhằm đảm bảo các ràng buộc thời gian nghiêm ngặt, kỹ thuật lập lịch thích ứng trước sự thay đổi topology mạng, cùng các giải thuật cân bằng tải cho hệ thống nhúng và IoT quy mô lớn. Tài liệu đặc biệt hữu ích cho kỹ sư hệ thống và nhà nghiên cứu cần giải quyết bài toán đảm bảo QoS trong điều kiện tài nguyên hạn chế và độ trễ tối thiểu. Để hiểu sâu hơn về nền tảng lý thuyết, bạn nên tham khảo thêm mẫu thiết kế hệ thống thời gian thực — một công trình nghiên cứu bổ sung trực tiếp cho các khái niệm phân tán được đề cập.

#Hệ thống thời gian thực phân tán
#Hệ thống thời gian thực linh hoạt
#Phân bổ tài nguyên động
#Quản lý tài nguyên hệ thống thời gian thực
#Giải pháp quản lý tài nguyên phân tán

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.4 Comparisons of robustness quality and running time in small problem instances.5 Comparisons of robustness quality and running time in medium prob- lem instances.6 Comparisons of robustness quality and running time in large problem instances.7 Significance test for Approx in medium and large problem instances.8 Comparison of number of violations.9 Comparison of maximum workloads.10 Comparison of accuracy of metrics in robustness characterization.1 An illustration of the algorithm’s search process.2 Utility comparison among the approximation algorithm (Approx), ran- dom search (RN), and simulated annealing (SA).3 Running time comparison among the approximation algorithm (Ap- prox), random search (RN), and simulated annealing (SA).4 Comparison between the utility by the approximation algorithm (Ap- prox) and its theoretical lower bound.5 Robustness comparison among the approximation algorithm (Approx), random search (RN), and simulated annealing (SA). 105 8 List of Tables 3.1 R|T|O|E taxonomy for task allocation in distributed real-time systems with environmental variables.2 Distribution of dominating problems.1 Max robustness value found with RARN-n, RAFF-n, RABB-n algo- rithms under three scenarios.1 An illustration of the robustness metric.2 Table of execution time parameters. 75 9 Chapter 1 Introduction Distributed real-time systems provide guarantees on timing requirements while boosting performance through concurrency in computing resources. They are useful for building large and complex real-time applications. Systematic resource manage- ment is necessary to properly allocate resources to achieve the guarantees. However, the deployment of distributed real-time systems into dynamic operational environ- ments poses a new problem for resource management. Performance of these systems are affected by environmental factors that cannot be known a priori, and traditional resource allocation techniques do not apply. A current area of active research is resource allocation with an objective of robustness, which seeks to maximize an al- location’s tolerance of unpredictable environment changes without jeopardizing fea- sibility. Such robust allocation reduces the necessity of reallocations, which are time-consuming both to compute and to enact. Additionally, reallocations are not appropriate for stateful real-time applications whose complex states are costly to recover. The problem is being studied by researchers. A heuristic mixed-integer programming approach was proposed by Gertphol et al. (2002) to maximize the al- lowable increase in load for a static allocation. Several heuristic algorithms were used in Shestak et al. (2005) to find robust allocations for periodic task strings. Juedes et al. (2004) developed heuristic algorithms to find robust allocations for indepen- dent, periodic real-time tasks. 10 Task 1: Task 2: Task 3: detect engage/launch guide missile Operator sensors filter/sense evaluate/ act actuator decide Figure 1.1: A generic air defense system. The notion of tasks that have dependencies on environmental factors originated from the study of a generic air defense system in Welch and Shirazi (1999). The sys- tem is sketched in Figure 1. The detect task identifies threats to a defended entity. The task runs periodically and performs the functions of filtering and evaluating radar tracks. When a threat is detected, the detect task triggers the engage task, which fires a missile at the threat. After a missile is in flight, the guide missile task keeps the missile on the correct course. The guide missile task executes periodically; uses sensor data to track the threat; recalculates the flight path for the missile; and issues guidance commands to the missile. During operation, there may be multiple replicas of the three tasks running concurrently. When the number of radar tracks grows too large for a single replica of the detect task to process within the required time, one or more replicas are created and the radar tracks are partitioned among them. In a similar manner, the guide missile task is replicated as necessary to meet deadlines, and replication is also used for the engage task when heavy workloads are anticipated. All three of the tasks have resource needs that are environment dependent. The execution time of the detect task is primarily workload-dependent. Since the task 11 evaluates each radar track to determine if it is a potential threat, its execution time is a function of the number of radar tracks in the environment. The workload of the engage task is also variable since it is activated by the number of tracks deemed as threats. Similarly, the work performed by the guide missile depends on the number of missiles in flight. Thus, an important problem to solve for this system is how to allocate resources to the tasks in a manner that allows real-time constraints to be met and that minimizes the need for reallocations (which create overhead in the system). Also, it is desirable to know the maximum numbers of missiles and radar tracks that can be sustained by a given configuration. Execution times of tasks in these dynamic distributed real-time systems, or DDRTSs, must be regarded as functions of unpredictable environmental factors be- cause the running time of an algorithm generally depends on sizes of their inputs. The algorithms implemented in real-time tasks are no exception, Gu et al. Ravindran et al. (2000) realized that employing the systems in unpredictable envi- ronments may affect these input sizes and result in varying execution times of tasks that cannot be known in advance. Meaningful worst-case execution times (WCET ’s) cannot be given. Therefore, Tia et al. (1995); Hu et al. (2001); Wandeler et al. (2004); Manolache et al. (2004) all pointed out that traditional periodic task scheduling and allocation based on worst-case estimation are not applicable. Existing approaches to address such systems include adaptive resource allocation, probabilistic deadline guarantee, and proactive robust allocation. However, these ap- proaches have not yet provided satisfactory resource allocation solutions for dynamic real-time systems. Adaptive resource allocation reacts to changes in environment and a system’s resource needs by passively reallocating the system, Welch et al. (1998, 1999); Ravin- dran et al. Thus it is vulnerable to frequent environment changes that trigger costly reallocations and result in thrashing, and no guarantees can be made. Further, it is often infeasible to reallocate stateful applications in real-time. The probabilistic model characterizes unpredictable task execution times as ran- dom variables, and the objective is to derive statistical confidence in deadline misses, 12 Tia et al. (1995); Hu et al. The task allocation problem was studied for sys- tems with dependencies and multiple processors by Manolache et al. How- ever, the allocation search and evaluation were expensive. The probabilistic models inherently lack any hard deadline guarantee. Proactive robust allocation approaches, such as Gertphol et al. (2002); Ali et al. (2003); Shestak et al. (2005), are still primitive. They employ coarse robustness met- rics, which can result in poor allocations. The robustness metric of Ali et al. (2003) was based on l-2 norm. It measures the radius of maximum environment perturba- tion environment without violating feasible boundaries. However, the metric only partially characterizes feasible regions by using an intangent sphere, and more seri- ously, no algorithm was developed to optimize it. Furthermore, existing approaches ignore real-time scheduling and feasibility. CPUs were assumed to be fair-shared in Gertphol et al. A special scheduler based on tightness was assumed by Shestak et al. (2005), but no feasibility guarantee was developed. These shortcomings are addressed by this research. First, a new model that explicitly incorporates environmental factors is presented. It characterizes task exe- cution time as functions of the environment. Second, metrics that accurately charac- terize the robustness of allocations are introduced. Robust task allocation problems are defined based on the metrics. Third, allocation algorithms are designed that use the metrics to find feasible and robust allocations. They are approximation algorithms with fast running time and scalability, which are necessary for modern distributed systems that may contain hundreds of processors and thousands of tasks. Theoretical bounds for their solution quality are derived, allowing guarantees to be made on the minimum robustness that can be achieved by the algorithms. Perfor- mance of the algorithms are experimentally validated by comparisons with baseline algorithms implementing standard search techniques.

Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ

Chủ đề

Quản lý tài nguyên hệ thống thời gian thực
Hệ thống phân tán và tính linh hoạt
Thiết kế hệ thống thời gian thực
Giải pháp điều phối tài nguyên động
Tải xuống (115 Trang - 1.35 MB)