Chapter 2 The PMS and ISP descriptive systems 35
selects only the next instruction and then after decoding (or examining it) proceeds to have the instruction executed by K(instruction execution).
Resource Allocation. At the PMS level the concept of resources, their uses and allocation, becomes a major focus of analysis. This is obvious by now in multiprogramming and multiprocessing systems where many programs share the same Mp and hence must be allocated space. But this holds equally well at all levels of detail.
By giving a resource allocation diagram along with the state diagram (Fig. 5) we show the relationship of resources, their function, and time for the instruction-interpretation process. In Fig. 5 the add instruction for a simple 1 accumulator computer consisting of 1Pc-2Mp is given. The interpretation for Fig. 5 in ISP is as follows:
1 Calculates the address of instruction q in state soq. t1- t0 = toq.
PC <- PC + 1; next advance the program counter
2 The instruction is fetched (accessed) from Mp in state saq. t2- t1 = taq.
M.instruction ¬ Mp[PC]; next
3 The operation o to be performed and the address part, v, for the data in M.instruction to be added to A are obtained in state soo + sov.r. t3 - t2 = too + tov.r
M.address ¬ M.instruction á vñ ; next
4 The data Mp[v] are fetched in state sav.r. t4 - t3 = tav.r
M.temporary ¬ Mp[M.address]; next
5 The operation part o of the instruction is carried out on A; that is, the actual addition is performed on the data previously accessed in the state so. t5 - t4 = to.
A ¬ M.temporary + A; next
In the state diagram, each state represents the time spent for a given activity. The two states at the top of the state diagram (Fig. 5) are waiting for primary memory accesses, and the three lower states represent processor activity waits. If we were to specialize the state diagram for the conventional 1 address/ instruction computer, we would need one additional state, representing operand storage, sav.w, and this would occur after state, so. Note that we have ignored the operation decoding state, so.o. Of course, conditional state transformation paths have to be added to describe all instructions (e.g., a complement-the-accumulator instruction has only states soq, saq, and so). Similarly, we could make a more general state diagram to handle the different processors (e.g., multiple addresses/instruction, stack, and general registers), as shown in Fig. 4. At the PMS level, a derivative of the state diagram, the resource allocation diagram is more useful because it relates to the physical structure.
Fig. 5. State and resource allocation diagram for a 1Pc-2Mp add instruction-interpretation process.
A resource allocation diagram expresses the above instruction activity in terms of the time each unit is occupied with a particular activity. In this diagram a slightly more complex computer structure with two primary memories has been assumed. In the case of the add instruction, the long memory-cycle time suggests that two memories can be used so that an operand be fetched while the instruction memory restoration occurs. These diagrams show the time various resources are utilized; thus performance and utilization can be measured.
Resource allocation diagrams can express other time scales. Interest in operating-system software analysis is often in the activities on a longer time scale of the resources utilization as a