V. V. Nikiforov, V. I. Shkirtil

A state of mutual waiting (mutual blocking) of jobs may occur during functioning of multi-task software with incorrect intertask synchronizing links. High-quality development of multi-task software applications shall include methods that ensure impossibility of such blocking states. Special models of tasks shall be developed and analyzed to resolve this issue. Each task is presented in these models as a sequence of segments. Each segment ends with a synchronizing operation that, when executed, advances the current task and the system to a new state. Universal methods for analysis of such models are based on construction of a graph of system states. Suitability of this method is limited because the number of vertices in a system states graph grows exponentially with growth of the number of tasks. Authors propose a more efficient method that is based on identification of special pairs of synchronizing operations (links) for each task - those pairs of synchronizing operations that may cause mutual blocking of the jobs. Then a directed multi-fraction graph is constructed (graph of links) ? each vertex in this graph represents a link of synchronizing operations. The possibility of mutual blocking of jobs manifests itself through existence of inter-fraction contour in the graph of links. Construction and analysis of the graph of links to control the possibility of mutual blocking of jobs may be widely employed because the number of vertices in graph of links grows lin-early with growth of the number of tasks.