1. Consider the following faulty code for a Producer-Consumer pair sharing a bounded buffer [0..N-1]:
Producer: Consumer:
while (true) { while (true) {
while (counter == N) {} // empty loop body while (counter == 0) {} // empty loop body
buffer[in] = ch; // produced character ch = buffer[out]; // consumed character
in = (in + 1) % N; out = (out + 1) % N;
counter = counter + 1; counter = counter - 1;
} }
Assume that global shared variables have current values: N=2, counter=1, out=0, in=1. Describe an execution sequence such that the Producer thinks the buffer is full when, in fact, the buffer is not full, thus illustrating the faulty code. Use any combination of description, diagrams, charts, etc. to help describe the execution sequence.
Note: this should not be just a temporary misalignment, which rights itself. This should be an extreme fault to the system.
2. Consider resource allocation graphs with a set of processes P = {P1, P2, P3}, a set of resources R = {R1, R2, R3}, and a set E of request (Pj®Ri) or assignment (Ri®Pj) edges. R1, R2, R3 have 1, 2, 1 instances, respectively.
In each of the following, draw the graph and state whether deadlock exists or not. Briefly explain each answer.
a) E = {P1®R1, P3®R2, R1®P2, R2®P2, R2®P1, R3®P3, P2®R3}
b) E = {P1®R1, P3®R2, R1®P2, R2®P2, R2®P1, R3®P3}
c) E = {P1®R1, R2®P3, R1®P2, P2®R2, R2®P1, R3®P3}
Note: the bold edges are intended to highlight the differences between the graphs.
3. A simple ALU performs ADD, SUB, AND, OR, and XOR.
Draw a diagram for a 1-bit slice of the ALU.
You should assume decoded control lines.
Use a block diagram for the full adder.
4.Show the circuit diagram for a 5-bit counter that increments the stored value on each clock pulse. It should use JK flip-flops and be a lookahead counter that minimizes gate delay.