|
(a)With the aid of a diagram,explain the characteristics of a stack.[6
marks ]
Award marks for points such as these.Up to
three of those marks may be gained from a suitable diagram,but do
not allow credit for the same point twice (so if the diagram labels
the stack base,do not give an extra mark for describing the stack
base in words).
Stack is an area of memory set aside for use in a particular way —last
in,first out (1).
Stack base is lowest address of this area of memory;stack limit is
highest (1).
Somewhere else (usually in a register)the stack pointer holds the
address of the top element in use (1).Adding an element to the stack
is called a PUSH.The stack pointer is incremented,and the new element
is written into memory at the location now pointed to (1).Removing
an element is a POP:the value pointed to by the stack pointer is copied
into a register,and the stack pointer is decremented (1).PUSHing when
the stack pointer is already at the stack limit is an overflow;POPing
when the stack pointer is at the stack base is an under flow (1).A
binary operation is one in which the top two elements are POPed from
the top of the stack,some operation is performed on the two values,and
the result is PUSHed back onto the stack (1).
(b)What is arameter passing?Describe two different ways in which
a system might perform arameter passing,and explain the benefits of
each.[5 marks ]
When calling a subroutine,a program must
provide to the subroutine the parameters, that is,the operands or
their addresses,to be used in the computation (1).Later,the subroutine
returns other parameters,in this case,the results of the computation
(1).
This exchange of information between a calling program and a subroutine
is referred to as parameter passing.
Three marks for points from the following,or similar:
Parameter passing may occur in several ways.The parameters may be
placed in registers or in fixed memory locations,where they can be
accessed by the subroutine (1),Alternatively,the parameters may be
placed on a stack,possibly the processor stack used for saving the
return address (1).
Passing parameters throug CPU registers is straightforward and efficient
(1).
However,if many parameters are involved,there may not be enough general-purpose
registers available for this purpose (1).And the calling program may
need to retain information in some registers for use after returning
from the subroutine,making these registers unavailable for passing
parameters.Using a stack,on the other hand,is highly flexible;a stack
can handle a large number of parameters (1).
(c)Write machine instructions (LOAD x ,ADD,SUB,etc.)which use a stack
to compute thefollowing expression.What is the minimum stack size
needed by your program?
X =(A*B ) +(C-D )
[4 marks ]
One solution (not optimal):
PUSH A
PUSH B
MUL
PUSH C
PUSH D
SUB
ADD
POP X
Award (3)for any correct program;(2)for
a program with one mistake;(1)for a
program with two mistakes. This program requires a stack size of at
least 3.(1)Allow consequential marks;answer will vary depending on
how the program is written.
|