Projects/Hackathon Update

Mutual Exclusion

Requirements:

1. Only one thread may be in the critical section at any time.
2. Each must eventually be able to enter its critical section.
3. Must be symmetrical (all run same program, cannot introduce static priority).
4. Cannot make any assumptions about speed of threads.

What's "wrong" with this solution?

loop {
    if turn == i:     
         critical_section;
         turn = i + 1;
}

What's "wrong" with this solution?

loop {
    if not lock: 
         lock = true;
         critical_section;
         lock = false;
}

Test and Set

Atomic instruction that: - returns current value of v - sets value of v to true

How can you implement mutual exclusion using test-and-set?

ARM's Exclusion Instructions

LDREX dest location
     dest = location
     Sets monitor on location in Exclusive state

STREX success value location
     Conditionally store into exclusive .
     If permitted, = 1 and = .
     If not, = 0 and value unchanged.

Context switch clears monitor (Open) state.

ARM Synchronization Primitives

lock_mutex(lock):
try_again:    
        LDREX R2, [lock]
        if R2 goto try_again
        STREX R2, 1, [lock]
        if not R2 goto try_again

unlock_mutex(lock):
        STR [lock], 0

Why don't we need to use STREX in unlock?

How should this be different if we care about energy?

Dijkstra's Solution

   loop {         
         b[i] := false
L1:  if k != i 
               c[i] := true
                     if b[k]:
                          k := i
                  goto L1
         else:
               c[i] := false
               for j in [1, ..., N]:
                    if j != i and not c[j]:
                         goto L1  
               critical section;   
               c[i] := true
               b[i] := true    
    }

Why is this guaranteed to provide mutual exclusion?

How do we know threads will make progress?

Dijkstra's Cry for Generalization

comments powered by Disqus