【正文】 lock 4 is 9, P in block 5 is 8。 the results are B(4)=9 B(5)=8 C(4)=1 C(5)=1 . 74 ? Step 3： A(2,4)=1, B(2)=10 A(3,4)=1, B(3)=10 ? According to A(2,5)=1, A(3,5)=1,the value of B(2) and B(3) should be 9, however, B(2)=9 that is less than B(2)=10, the value of B(2) should not be changed according to step 3。 so is B(3). ? Step 4, ? A(2,4)=0, A(3,4)=0, A(2,5)=0,A(3,5)=0, ). 75 ? The new value of A(I,J) are shown in Table . ? Step 5, Because not all the C(I) =0(I=1, … ,n), it returns to the step 2. 76 ? The second time of running static level storage algorithm: Step 2 ? b e c a u s e A(2 , J ) = 0 (J=1 ， … , 5 ), A(3,J)=0(J=1， … ,5), in addition C(2)=0, C(3)=0, P in block 2 is 8, P in block 3 is 10, so B(2)= 17 B(3 )= 19 C(2 )=1 C(3 )=1 . 77 ? Step 3： A(1,2)=1, B(1)=18 When A(1,3)=1, then B(1)=20, because that B(1)=20 that is larger than B(1)=18, the value of B(1 ) s h o u l d be changed as B(1 )=20 ? Step 4： A(1,2)=0, A(1,3)=0 ? Step 5： because of C(1)≠0, it should return to step 2 78 ? The third time of running static level storage algorithm: ? Step 2： because A(1,J)=0(J=1， … ,5), in addition C(1)=0, P in block 1 is 10 so B(1)= 29, C(1)=1 ? Step 3, there is no A(K,1)=1(K=1,… 5) ? Step 4, because all C(I)=1(I=1,… 5), so go to end of the algorithm. 79 Dynamic Storage Allocation ? Stack allocation Stack allocation is based on the idea of a control stack。 storage is anized as a stack, activation records are pushed into stack when activations begin, and they are popped after activations ending. . 80 ? Identifier, constant and variable are named records, name it local. Locals are bound to fresh each activation storage, When the activation ends, the storage for locals disappears when the activation record is popped . 81 ? We use register pointer to mark the top of the stack. At running time, an activation record can be allocated by incrementing by the size of the record, and deallocated by decrementing top according to the size of the record. For example, Procedure P has an activation record of size a, then the top is incremented by a, as P is released, top is d e c r e m e n t e d by a . 82 Example ? PROGRAM main (input, output)。 CONST a = 1。 VAR b: integer。 c: real 。 PROCEDURE 2 (x: integer)。 VAR d: real。 PROCEDURE 4 (y: real)。 CONST e = 15。 …… END 。 ｛ 4｝ two parallel procedures that are procedure 2 and procedure 3. 83 ? PROCEDURE 5(z: real) VAR i: integer。 BEGIN …… z=z+a …… END 。 ｛ 5｝ BEGIN …… 4 (d)。 …… 5 (d)。 …… 84 END 。｛ 2｝ PROCEDURE 3 (h: real)。 VAR f: real。 BEGIN …… 4 (f)。 …… 5 (f)。 …… END。｛ 3｝ 85 ? BEGIN …… 2 (b)。 …… 3 (c)。 …… END.｛ main｝ two parallel procedures that are procedure 2 and procedure 3. Procedure 2 calls procedure 4 and procedure 5, procedure 3 runs procedure 4 and procedure 5 too 86 ? In the main program, there are one constant a and two identifiers b and c that need to be pushed into stack S1, then we first run procedure 2 and at the same time to allocate stack S2 that includes identifiers x and d, next allocate identifiers y and e to S3 for procedure 4, furthermore, it is the turn of procedure 5 that are allocated by stack S4, its identifiers are z and i. Because procedure 3 also calls procedure 4 and procedure 5, the allocation of procedure 3 is stack S5, the identifiers in stack S6 and S7 are same with stack S3 and S4. All of the stack allocation is shown in figure . 87 ? When procedure returns to main program, stacks are firstly released from the top of the stack, that is stack S7, then stack S6 is released, next is the turn of S5 and so on , the program can not be finished until stack S1 is released. ? a, b, c S1 (a) x, d S2 S1 (b) a, b, c (c) y, e S3 S2 S1 a, b, c x, d 88 ? (d) z, i S1 S2 S3 S4 x, d a, b, c y, e z, i S1 S2 S3 S4 x, d a, b, c y, e h, f S5 (e) z, i y, e z, i S1 S2 S3 S4 x, d a, b, c y, e h, f S5 (f) Fig. Runtime stack 圖 示例的運(yùn)行棧 S 89 ? Allocation with nested procedure 90 ? From example , we know that there are nested procedures in it. Such as procedure 4 and procedure 5 are nested in procedure 2, so is procedure 3. But, how to connect the nested calling procedure with called procedure? We add a pointer named access link to each activation record. If procedure 4 is nested within the most recent activation procedure 2, the access link in activation record for procedure 4 points to the access link in the record for procedure 2, it is shown in figure . . 91 ? In figure b, we can see that there is procedure 4 in the stack. If we want to find the calling of procedure 4 quickly, it is better to know the depth of procedure 4, namely, when we should label the nesting depth of every procedure. Let the main program be at nesting dep