Priority in Scheduling 3996.20, and the correct result is returned. This follows because Q = 0 and the outer loop is
never entered. At the end of the procedure, NotlnCycle = 0 0 V.
If some vertex has outdegree zero, then at least one vertex is put in both NotlnCycle
and Q. The outer loop is executed, since Q # 0 is true. The inner loop may identify ad-
ditional vertices that cannot be in a directed cycle. All such additional vertices, as they
are recognized, are included in the set NotlnCycle and put on Q. Each instance of the in-
ner loop will terminate, since each vertex is adjacent only to finitely many other vertices.
The outer loop executes at most once for each vertex in V. This is because the first time
a vertex is put on Q, the vertex has outdegree 0 in the current graph. Hence, it can never
serve as the tail of an edge in the remaining graph and, so, cannot be put on Q a second
time.
Therefore, the outer loop terminates after at most I V I iterations. Finally, the procedure
determines whether there is a directed cycle in the directed graph by asking whether all the
vertices have been put in NotlnCycle. If V = NotlnCycle, then the directed graph does
not contain a directed cycle. If V : NotlnCycle, then it can be shown that the subgraph
induced by the vertices in V - NotInCycle contains a directed cycle by using Exercise 3 in
Section 6.20.
Priority in Scheduling
In addition to being able to determine whether a set of processes is in deadlock, an operat-
ing system must be able to schedule all the processes in a system so that each process has
its required input available before it is executed. When a complicated expression is evalu-
ated, each operator must have access to the values of its operands at the time it is carried
out, so the operators in the expression must be "scheduled."
One additional example involves a manufacturing assembly process. In manufacturing
a complex product, assembly is decomposed into a sequence of subassemblies that must
be scheduled so that required subassemblies are completed before their output is needed
by another subassembly. Figure 6.59 shows a directed graph that models the relationships
among a set of subassemblies in a manufacturing process. The directed graph has a di-
rected edge from subassembly A to subassembly B if subassembly A must be completed
before subassembly B can begin. A practical problem to solve is how to schedule all these
processes sequentially so that whenever a subassembly begins, all the subassemblies that
it requires have been completed.
BA••GE FFigure 6.59 Related subassemblies.