DETECTION OF DEADLOCK AMONG WAITING TASKS IN A MULTI- PROCESSING, MULTIPROGRAMMING CPU ENVIRONMENT

摘要

The wait relations among N tasks in a multiprocessing, multiprogramming CPU environment are conformed to a vector of N+1 fields recording which tasks in a system are active and upon what other task any given task directly waits. The vector may be stored in a global register. Positions 1 through N are assigned to the N tasks such that a value p in position r means that task r is waiting directly on task p. One value j of the possible values 0,1,2, . . . , N+1 is designated to indicate an active task. Position j always shows the value j. Without loss of generality and to facilitate the discussion j is assumed to be 0. Thus, the value 0 in register position r means that task r is not waiting and position 0 always has the value 0. The presence of any deadlocks (closures) among the wait relations can always be detected by the computing system by making repeated translations of the vector fields within and upon themselves in no more than log2(N+1) iterations. In this regard, log2(N+1) denotes the smallest integer equal to or greater than the base 2 logarithm. The translation of fields within and upon themselves means that for each global register position r containing pointer p, then the contents g of register position p are substituted as the new contents of position r for the iteration 0/=r, p, g/=N.