Some Algorithms for Analysis and Synthesis of Real-Time Multiprocessor Computing Systems

摘要

The problem of preemptive scheduling in a real-time multiprocessor computing system with release time/deadline intervals is investigated. Approximate algorithms based on the generalization of a single-processor algorithm of relative priority are developed and compared to the exact maximum flow algorithm. An algorithm has been developed for the case where requests for the tasks occur periodically with given periods. An algorithm for determining the values of the processor performance for which there exists an admissible schedule for a given assembly of tasks with release time/deadline intervals has been developed.