Overview Locks and mutexes Working with multiple locks Summary and next lecture
XJCO3221 Parallel Computation
University of Leeds
Copyright By PowCoder代写 加微信 powcoder
Lecture 7: Lock and mutexes
XJCO3221 Parallel Computation
Locks and mutexes Previous lecture
Working with multiple locks Today¡¯s lecture Summary and next lecture
Previous lecture
In the last lecture we saw how critical regions of code could be serialised:
Only one thread can enter the region at a time, a form of coordination.
Avoids data races.
Can incur a significant performance penalty.
Implemented in OpenMP as #pragma omp critical
Single arithmetic instructions can be optimised by using atomic instructions (#pragma omp atomic).
XJCO3221 Parallel Computation
Locks and mutexes Previous lecture Working with multiple locks Today¡¯s lecture
Summary and next lecture
Today¡¯s lecture
For today¡¯s final lecture on shared memory parallelism, we will look at what is going on ¡®behind the scenes¡¯.
Thread coordination performed using locks, sometimes known as mutexes.
Locks can control access to data structures.
Multiple locks can improve performance of memory access. However, multiple locks can give rise to deadlock.
This lecture is largely theoretical1 and will not help with any courseworks, but the material may appear in the exam.
1There are code examples for this lecture, and a question on Worksheet 1. and XJCO3221 Parallel Computation
Locks and mutexes
Working with multiple locks Summary and next lecture
Locks for critical regions
Implementations of locks Potential mistakes with locks
Recap: Critical regions
… // Non-critical
… // code executed
… // in parallel
#pragma omp critical {
… // Critical region …
Instructions before #pragma omp critical executed concurrently (e.g. if in a parallel loop).
Instructions in the scope (¡®{¡¯ to ¡®}¡¯) only executed by one thread at a time.
Other threads blocked from entering; they are idle. XJCO3221 Parallel Computation
Locks and mutexes
Working with multiple locks Summary and next lecture
Locks for critical regions
Implementations of locks Potential mistakes with locks
Thread coordination with locks
This synchronisation is performed using a lock:
Single lock for the critical region.
Can be in one of two states: locked and unlocked.
The first thread to reach the critical region locks it. Also known as acquiring the lock.
This thread is said to be the lock¡¯s owner.
No other threads can enter the region (¡®acquire the lock¡¯) until it becomes unlocked.
The owning thread unlocks (or releases) it when leaving the region, allowing another thread to take over ownership.
XJCO3221 Parallel Computation
Locks and mutexes
Working with multiple locks Summary and next lecture
Locks for critical regions
Implementations of locks Potential mistakes with locks
Critical region using a lock
11 22 33 44 55 66 77 88 99
Lock pseudocode:
// Multiple threads exec –
// uting concurrently , // (e.g. parallel loop).
#pragma omp critical {
… // Critical code. …
// All threads access a // single lock object. lock_t regionLock;
regionLock.lock();
… // Critical code. … regionLock.unlock();
regionLock.lock() does not return until the thread has acquired the lock; it is said to be blocking.
XJCO3221 Parallel Computation
Locks and mutexes
Working with multiple locks Summary and next lecture
Locks for critical regions
Implementations of locks
Potential mistakes with locks
Implementations of locks
Most parallel APIs support locks, although they are sometimes called mutexes as they control mutual exclusion:
Java¡¯s Lock interface (in java.util.concurrent.locks). std::mutex in C++11 (in
pthread mutex t in the pthreads library (C/C++).
When implemented as classes, they are typically opaque:
The user does not have access to instance variables or details of the implementation.
XJCO3221 Parallel Computation
Locks and mutexes
Working with multiple locks Summary and next lecture
Locks for critical regions
Implementations of locks
Potential mistakes with locks
Locks in OpenMP
OpenMP runtime library also supports locks:
1 2 3 4 5 6 7 8 9
#include
// Initialise lock (opaquely).
omp_lock_t regionLock;
omp_init_lock(®ionLock);
… // (in parallel). omp_set_lock(®ionLock); // LOCK.
… // (critical code). omp_unset_lock(®ionLock); // UNLOCK.
// Deallocate the lock. omp_destroy_lock(®ionLock);
You could implement your own critical region this way, although it is easier to use #pragma omp critical.
XJCO3221 Parallel Computation
Locks and mutexes
Working with multiple locks Summary and next lecture
Locks for critical regions
Implementations of locks
Potential mistakes with locks
Programming locks
Note there is no explicit link between the lock regionLock, and the critical region of code, or data structure, that it is trying to protect.
It is down to the programmer to correctly link each lock with its associated block of critical code, or data structure.
This gives greater flexibility, but also greater scope for programming errors.
Could use a struct or class to keep the lock with the data it is protecting, with the lock private/protected.
and XJCO3221 Parallel Computation
Locks and mutexes
Working with multiple locks Summary and next lecture
Locks for critical regions Implementations of locks Potential mistakes with locks
Lock mistakes (1): Forgetting to lock()
lock_t regionLock;
//regionLock.lock(); // Forgot to lock()! …
… // Critical code
regionLock.unlock();
1 2 3 4 5 6 7
This is precisely the situation we were trying to avoid! All threads enter the critical region.
Race conditions become a possibility.
unlock() will have no effect, except possibly a small performance overhead1 .
1Generally, this depends on the API: In C++11, attempting to unlock a std::mutex that is not locked leads to undefined behaviour.
XJCO3221 Parallel Computation
Locks and mutexes
Working with multiple locks Summary and next lecture
Locks for critical regions Implementations of locks Potential mistakes with locks
Lock mistakes (2): Forgetting to unlock()
lock_t regionLock; … regionLock.lock(); …
… // Critical code
//regionLock.unlock(); // Forgot to unlock!
1 2 3 4 5 6 7
The first thread exclusively enters the critical region. It never releases the lock.
Therefore no other thread can acquire the lock.
All other threads remain idle at lock().
XJCO3221 Parallel Computation
Locks and mutexes
Working with multiple locks Summary and next lecture
Locks for critical regions Implementations of locks Potential mistakes with locks
RAII = Resource Acquisition Is Initialisation.
This second mistake is easier to make than it seems:
The critical code may throw an exception (C++/Java).
A break or continue command may jump over unlock().
May be support for locks that automatically release when they leave their scope.
If defined at start of a routine, automatically released at end of routine however it reached there.
e.g. std::lock guard
This mechanism is generally known as RAII, for Resource Acquisition Is Initialisation.
XJCO3221 Parallel Computation
Overview Locks and mutexes Working with multiple locks Summary and next lecture
Using multiple locks for data access
Nested critical regions
Multiple locks
Code on Minerva: multipleLockCopy.c
1 2 3 4 5 6 7 8 9
Suppose we want to copy randomly-selected elements of an array data of size N to another randomly-selected element.
Decide to use a lock to control data writes.
#pragma omp parallel for for( n=0; n