Abstract
Real-time systems such as multimedia systems and embedded systems are appearing in many applications. Many researchers have been extensively working on multiprocessor real-time systems. The main challenge for these systems is to design a scheduling algorithm for the task system T such that all tasks in T can meet their timing constraints. In some applications, task systems allow few transient faults. This kind of task systems is characterized by the “k-fault tolerant” model. Whenever a fault is detected, the system enters the recovery mode. Some extra recovery tasks must be scheduled and finished before the deadline of the current task. In this dissertation, first, we have done research to improve the performance of the systems, and develop a feasible-checking algorithm for k-fault tolerant systems under the “Earliest Deadline First” schedule. Also, a multiprocessor system can be modeled as an undirected graph G; each processor corresponds to the vertex and each communication channel available between pairs of processors corresponds to the edge. Therefore, second, we propose a number of simple algorithms for solving connectivity augmentation problem related to bipartite graphs. In these algorithms, we add a set of edges with the smallest possible cardinality so that the resulting graph is 2-edge-connected. Third, the vertices of a graph G are partitioned into k groups by adding the smallest number of edges to G such that the resulting graph is 2-vertex connected. The above augmentation problems are solved in linear time in the size of the input graph.