6.823 Problem Set 6

Chris Laas

May 5, 2000

Problem 6-1

(a) try:    LWRV r3, (r2)
        SWCD (r2), r1, r4
        BEQZ r4, spin
        MOV r1, r3

(b) The processor must check whether its own reservation has been cancelled, and must cancel other processors’ reservations, if any. This is relatively costless for the issuing processor if the SMP uses snoopy caches which detect writes going over the bus.

(c)  ADD r2, r0, mutex
try:    LWRV r1, (r2)
        BEQZ r1, try
        ADD r1, r0, r0
        SWCD (r2), r1, r3
        BEQZ r3, try

In the old mechanism, the processor trying to set the semaphore could have its reservation cancelled by the spinning process, causing it to have to try again (potentially over and over again until it succeeds). With this mechanism, the spinning process polls the semaphore location without cancelling any reservations; thus, the semaphore is set correctly the first time, and exactly one blocking process will be sent on its way.

(d) Imagine that several processors are each running several processes which reserve the memory address M. Let’s pay attention to one processor, running tasks A and B. Task A issues a LWRV to reserve the location M, and there is immediately a context switch to task B. Task B issues a LWRV to reserve M, then issues a SWCD on the location with a new value, and again there is a context switch to task A. Now, since the processor doesn’t cancel the reservation on a context switch, task A continues on to perform its SWCD on location M, succeeding because it sees that it has a valid reservation on the location. However, sequential consistency has been violated, because the value in memory location M was changed (by task B) in between the times that task A read the location and wrote the location, and thus task A was using a stale value of the memory location value when it performed the store.

Chris Laas  6.823  5/5/2000  2

Problem 6-3

(a)