Planning Calculations in a Multiprocessor System with Unspecified Moments of Operational Readiness
- PDF / 427,687 Bytes
- 8 Pages / 612 x 792 pts (letter) Page_size
- 84 Downloads / 198 Views
EMS ANALYSIS AND OPERATIONS RESEARCH
Planning Calculations in a Multiprocessor System with Unspecified Moments of Operational Readiness M. G. Furugyan Federal Research Center Informatics and Control, Russian Academy of Sciences, Moscow, 119333 Russia e-mail: [email protected] Received February 10, 2020; revised February 26, 2020; accepted March 30, 2020
Abstract—The problem of compiling an acceptable multiprocessor schedule without interruptions and switching is considered for the case when the set of partial relations is specified on the set of operations, all operations have a common deadline, and the distribution of tasks on the processors is specified. At some undetermined times, requests may be made to perform additional, higher priority operations, for which some processors are freed for a certain time. As a result, the execution of the initial set of tasks is postponed to a later time and thereby violates the schedule built for it. A strategy is developed for constructing an acceptable schedule in which the probability of its violation due to requests for additional operations is minimal.
DOI: 10.1134/S1064230720040048
INTRODUCTION When developing mathematical programs and software for multiprocessor systems, in particular realtime systems, one of the main tasks is to plan calculations and construct valid schedules for program modules. When testing and operating complex technical objects, a contingency situation often arises when, in addition to performing basic software modules, at some unspecified time, requests may be made to perform additional, higher priority tasks. If such requests arrive at a time when the main operation is being performed and at the same time it is required to free the processors occupied by them, this leads to a violation of the previously constructed schedule for the main operation. In this case, the task is to minimize the likelihood of such violations. These situations arise when testing aircraft, space systems, nuclear reactors, and other complex equipment. In this case, there are tasks of compiling an acceptable schedule in the presence of undefined factors, which are reduced to game tasks. Such tasks are especially relevant when designing onboard automated control systems. The problems of resource allocation and scheduling in the presence of undefined factors were previously considered by a number of authors. In [1], the minimax problem of the theory of schedules for an unspecified duration of operation was described, for the solution of which a method was developed for constructing stability domains of the optimal schedules. In [2], the possibility of a dynamic change in the network’s operation structure, specifying a partial operation order, is additionally assumed. The task of minimizing the execution time of a network’s operation package in the case when the durations of operations are functions of the resource allocation vector and the number of processors is not limited was studied in [3] and reduced to a nonlinear programming problem. In [4], the problem of minimizing
Data Loading...
