Exercise 2.29 The fi rst three problems in this exercise refer to a critical section of the form lock(lk);

operation unlock(lk);

where the “operation” updates the shared variable shvar using the local (nonshared)

variable x as follows:

Operation

a. shvar=shvar+x;

b. shvar=min(shvar,x);

2.29.1 [10] <2.11> Write the MIPS assembler code for this critical section, assuming that the address of the lk variable is in $a0, the address of the shvar variable is in $a1, and the value of variable x is in $a2. Your critical section should not contain any function calls, i.e., you should include the MIPS instructions for lock(), unlock(), max(), and min() operations. Use ll/sc instructions to implement the lock() operation, and the unlock() operation is simply an ordinary store instruction.

2.29.2 [10] <2.11> Repeat problem 2.29.1, but this time use ll/sc to perform an atomic update of the shvar variable directly, without using lock() and unlock().

Note that in this problem there is no variable lk.

2.29.3 [10] <2.11> Compare the best-case performance of your code from 2.29.1 and 2.29.2, assuming that each instruction takes one cycle to execute. Note:
best-case means that ll/sc always succeeds, the lock is always free when we want to lock(), and if there is a branch we take the path that completes the operation with fewer executed instructions.
2.29.4 [10] <2.11> Using your code from 2.29.2 as an example, explain what happens when two processors begin to execute this critical section at the same time, assuming that each processor executes exactly one instruction per cycle.
2.29.5 [10] <2.11> Explain why in your code from 2.29.2 register $a1 contains the address of variable shvar and not the value of that variable, and why register $a2 contains the value of variable x and not its address.
2.29.6 [10] <2.11> If we want to atomically perform the same operation on two shared variables (e.g., shvar1 and shvar2) in the same critical section, we can do this easily using the approach from 2.29.1 (simply put both updates between the lock operation and the corresponding unlock operation). Explain why we cannot do this using the approach from 2.29.2., i.e., why we cannot use ll/sc to access both shared variables in a way that guarantees that both updates are executed together as a single atomic operation.