1Edgar GabrielCOSC 6385 Computer Architecture - Multi-Processors (III)SynchronizationEdgar GabrielSpring 2010COSC 6385 – Computer ArchitectureEdgar GabrielSynchronization between processors• Required on all levels of multi-threaded programming– Lock/unlock– Mutual exclusion– Barrier synchronization• Key hardware capability:– Uninterruptable instruction capable of automatically retrieving or changing a value2COSC 6385 – Computer ArchitectureEdgar GabrielThread synchronization• Reading and writing a shared variable between two threads• Timing between two threads will differ in every iteration• If you need a specific value for thread B of the variable you need to synchronize access to the shared variable Thread AThread Btimereadwrite1write2readCOSC 6385 – Computer ArchitectureEdgar GabrielMutex locks in POSIX threads• Mutex: Mutual exclusion – a lock is used before accessing a shared resource and released after the access– mutex lock represented by a mutex variable – while mutex lock is set, other threads that try to access the lock will be denied– if more than one thread wait for the lock, all of them will be made runnable, but only one thread will get the lock• All threads have to use mutex locks for accessing the variable, else no guarantee on correctness3COSC 6385 – Computer ArchitectureEdgar GabrielMutex locks(II)– mutex: mutex variable to be initialized/destroyed counter part• once initialized, a mutex variable can be used for an unlimited number of lock/unlock operations– attr: attributes for the mutexint pthread_mutex_init (pthread_mutex_r *mutex, const pthread_mutexattr_t *attr);int pthread_mutex_destroy (pthread_mutex_t *mutex);COSC 6385 – Computer ArchitectureEdgar GabrielMutex locks (III)• pthread_mutex_lock: acquire lock for the mutex. – If mutex is already blocked by another thread, wait until the mutex is unlocked• pthread_mutex_trylock: acquire lock for the mutex. – If mutex is already blocked by another thread, do not wait but return EBUSY to indicated failureint pthread_mutex_lock (pthread_mutex_t *mutex );int pthread_mutex_trylock (pthread_mutex_t *mutex );int pthread_mutex_unlock (pthread_mutex_t *mutex );4COSC 6385 – Computer ArchitectureEdgar GabrielThread synchronization revisited• Example: Force thread B to read value of shared variable after write2Thread AThread Btimereadwrite1write2readCOSC 6385 – Computer ArchitectureEdgar GabrielSimple Example (IIIa)#include <pthread.h>int value=0; // shared variablepthread_mutex_t mymutex; // mutex variableint main ( int argc, char **argv ) {int threadid, ret;// main thread spawns another thread ret = pthread_create (&threadid, NULL, tfunc, NULL);if ( ret != 0 ) printf(“Error creating a thread\n”);pthread_mutex_init (&mymutex,NULL); //Initialize mutexpthread_mutex_lock (&mymutex); // Acquire mutex lock value = 1; // write 1value ++; // write 2pthread_mutex_unlock (&mymutex); // Release lockpthread_join( threadid, &val); // wait for other threadpthread_mutex_destroy (&mymutex); // destroy mutexreturn (0);}5COSC 6385 – Computer ArchitectureEdgar GabrielSimple Example (IIIb)void *tfunc (void *arg){int localvalue; pthread_mutex_lock (&mymutex); // wait for locklocalvalue = value; // read shared variablepthread_mutex_unlock (&mymutex);do_work(localvalue);pthread_exit ((void *) 1);return NULL;}COSC 6385 – Computer ArchitectureEdgar GabrielMutex locks (IV)• A thread will deadlock itself if it tries to lock the same mutex twice• If more than one mutex is used a deadlock can occur if one thread holds lock1 and waits for lock2 and the other thread holds lock2 and waits for lock1– Order for accessing mutexes has to be identical in all code pathes– e.g. need to hold lock1 in order to be allows to hold lock26COSC 6385 – Computer ArchitectureEdgar GabrielSynchronization • Lock/unlock operations on the hardware level, e.g.– Lock returning 0 if lock is free/available– Lock returning 1 if lock is unavailable• Implementation using atomic exchange– Process sets the value of a register/memory location to the required operation– Setting the value must not be interrupted in order to avoid race conditions– Access by multiple processes/threads will be resolved by write serializationCOSC 6385 – Computer ArchitectureEdgar GabrielSynchronization (II)• Alternative implementations:– Test-and-set– Fetch-and-increment• Problems with all three algorithms:– Require a read and write operation in a single, uninterruptable sequence– Hardware can not allow any operations between the read and the write operation– Complicates cache coherence– Must not deadlock7COSC 6385 – Computer ArchitectureEdgar GabrielLoad linked/store conditional• Alternative implementations (II):– Pair of instructions where the second instruction returns a value indicating, whether the pair of instructions was executed as if the instructions were atomic– Special pair of load and store operations• Load linked (LL)• Store conditional (SC): returns 1 if successful, 0 otherwise– Store conditional returns an error if• Contents of memory location specified by LL changed before calling SC• Processor executes a context switchCOSC 6385 – Computer ArchitectureEdgar GabrielLoad linked/store conditional (II)• Assembler code sequence to atomically exchange the contents of register R4 and the memory location specified by R1try: MOV R3, R4LL R2, 0(R1)SC R3, 0(R1)BEQZ R3, tryMOV R4, R28COSC 6385 – Computer ArchitectureEdgar GabrielLoad linked/store conditional (III)• Implementing fetch-and-increment using load linked and conditional storetry: LL R2, 0(R1)DADDUI R3, R2, #1SC R3, 0(R1)BEQZ R3, try• Implementation of LL/SC by using a special Link Register, which contains the address of the operationCOSC 6385 – Computer ArchitectureEdgar GabrielSpin locks• A lock that a processor continuously tries to acquire, spinning around in a loop until it succeeds.• Trivial implementationDADDUI R2, R0, #1lockit: EXCH R2, 0(R1) !atomic exchangeBNEZ R2, lockit• Since the EXCH operation includes a read and a modify operation– Value will be loaded into the cache• Good if only one processor tries to access the lock• Bad if multiple processors in an SMP try to get the lock (cache coherence)– EXCH includes a write attempt, which will lead to a write-miss for SMPs9COSC 6385 – Computer ArchitectureEdgar GabrielSpin locks (II)• For