N-1, which indicates that no items are in the queue; Empty-flag to true; full-flag to false; Item-count to 0; and the Clear-request flag to false.

The Put subprocess, shown in Figure MQ-4c, performs several tasks: increments the Item-count by one; sets the Empty-flag to false; if tem-count equals N, sets the Full-flag to true; increments Put-ptr by one (mod N) and stores the data item from Put-buff at this address (rear of the queue); and sets the Put- request flag to false.

The Get subprocess, shown in Figure MQ-4d, performs these tasks: decrements the Item-count by one; sets the full-flag to false and the Empty-flag to true if the Item-count is zero; increments Get-ptr by one (mod N) and takes the data item at this address (front of the queue) and places it in Get-buff; sets the Get-request flag to false.

Figure MQ-5 shows various examples of usage of the queue.

ADDITIONAL PROBLEMS

1. Carry out a design which minimizes cost by storing control information about the queue (i.e., Put-ptr, Get-ptr, Item-count) in the memory array.

2. Design an M(queue) which has a number of data parts (stages) which transfer data from stage to stage in a pipeline fashion. Carry out the design for 2,3,...,n data parts.

3. Do a cost/performance analysis to determine the feasibility of always keeping Get-buff filled.

4. Design a time-shared M(queue) which provides for data inputs from multiple sources and data outputs to multiple sinks. Assume that there is a fixed amount of memory to be shared which is shared equally among all queues. Alternatively consider a design with a fixed amount of memory dynamically shared among the queues.

5. Determine the rate at which Put, Get and Clear operations can be processed. In the system described above, an operation request is lost if it is given while a previous request of the same type is being handled. Design an M(queue) that can stack up to K requests of the same type without losing a request.

6. Use K(arbiter) to design M(queue).

M(STACK) LAST-IN, FIRST-OUT MEMORY

KEYWORDS: Stack, LIFO, push, pop, memory

The usual example given of a stack is that of a pile of plates stacked on top of a spring-loaded rack, to which new plates are always put on or taken from the top. In the stack memory, words would correspond to the plates. The stack is used less than the queue in hardware structures, but it is quite useful in programming and in studying theoretical models of computation. Stacks have been used as the main memory in computers, and in desk calculators for holding intermediate results. The two applications of the stack that are most frequently encountered in programming are saving procedure (or subroutine) return addresses, saving temporary information which subroutines use, and evaluating nested arithmetic expressions.

The advantage of the stack as a memory for saving return addresses and temporary information is that space is not required within each subroutine to hold that information. All subroutines use a common memory and the total requirement for the memory is equal to the space required by all subroutines active at a given moment - a dynamic requirement. The bookkeeping required to

280