ENEE350H - Fall, 2004

Homework 7

(Due in class on Thursday, December 9)

Q. 1.   Assume there is a task queue (implemented in linked-list) that is already initialized and static, meaning once the list is empty, it will always stay empty. Only one process can access this task queue at one time.  Its data structure is implemented as follows:

struct task {
     int value;
     struct task *next;

struct task *queue; // tail of queue
int sema_value = 1; // only one process can access queue at a time

There are two processes, P1 and P2, which have the exact same code. Both P1 and P2 de-queue the value from the task queue and call function do_task on the value. Function do_task takes a lot of time, so processes must be able to do do_task in parallel. Dequeue means taking the item at the tail of the queue. Here is the code for the processes:

while ( queue != NULL ) { // while queue is not empty
     int temp = queue->value;
     queue = queue->next // don't worry about memory leak

Your job is to add up(sema_value) and down(sema_value) semaphore statements into the process code to make sure the two concurrent processes will work correctly.  Do not change the existing code; the only change should be the addition of semaphore statements.
(Note: working correctly means
- each element of the queue is processed by do_task exactly once.
- all elements of the queue are processed.
- in the end, "done" gets printed twice.
- no deadlock occurs )

Q. 2.  Below is an assembly program that uses a hardware timer to wait in a loop for a given period of time. When the set time elapses the timer triggers an interrupt.  The interrupt routine sets r1 to 1.


            add r1, r0, r0

            trap                  (activate timer)


            subi r1, r1, 1

            beqz r1, _timeelapsed

            addi r1, r1, 1

            j _waitloop


            (program continues)


How might this program malfunction? Modify this program so that it always works correctly.  You should not use semaphores.  (Hint: re-write the code within waitloop to only read from r1, and that too, once.  Use additional registers if needed.)


Q. 3.  Consider the following DLX program.  The .global assembler directive declares a global symbol, .space N allocates space of N bytes, and .align N aligns the next address to be aligned to a multiple of N bytes. DLX is a 32-bit instruction set

.global   _main

.global   _counter

_counter:           .space   4

.align    8

_main:              LHI                  R4, (_counter>>16)&0xffff

ADDUI             R4, R4, (_counter&0xffff)

ADD                R5, R0, 18

AND                R5, R5, 0x10

BNEZ               R5, _L1

ADD                R5, R0, 37

_L1:                 SW                   0(R4), R5

JR                    R31

(a)    Show the contents of the symbol table after the program is processed in the assembler.  Assume that the symbol table stores only the name and offset-from-start-of-file-in-bytes for each symbol.  [You can show the symbols in any order].

(b)   What is the value of the immediate argument of the ADDUI instruction after assembly?

 (c)    After assembly the resulting executable is run.  How many cycles does the program take for execution?  Assume all cache hits, perfect branch prediction and no page faults. [Ignore the fact that the program is not quite correct since it does not do stack-related operations!]                

(d)   If the above code is modified to insert a procedure call immediately after the ADDUI instruction, which registers would need to be saved using a caller-saves convention?