CENG479 PARALLEL COMPUTING

Lec.9: POSIX Threads - Mutex

Dr. Hüseyin TEMUÇİN

Gazi Üniversitesi Bilgisayar Mühendisliği Bölümü
 Critical Section

These slides are based on Peter Pacheco, An Introduction to Parallel Programming Book, 2012
 Critical Section

These slides are based on Peter Pacheco, An Introduction to Parallel Programming Book, 2012
 Busy - Waiting

● The while loop is an example of busy-waiting. In busy-waiting, a thread repeatedly tests a

condition, but, effectively, does no useful work until the condition has the appropriate
value (false in our example).
● Compiler optimization problem !

These slides are based on Peter Pacheco, An Introduction to Parallel Programming Book, 2012
Mutexes

● Since a thread that is busy-waiting may continually use the CPU, busy-waiting is generally not an
ideal solution to the problem of limiting access to a critical section.
● Two better solutions
○ Semaphores
○ Mutex
● Mutex is an abbreviation of mutual exclusion, and a mutex is a special type of variable that, together
with a couple of special functions, can be used to restrict access to a critical section to a single
thread at a time
○ A mutex can be used to guarantee that one thread “excludes” all other threads while it executes the critical
section.
Mutexes

● The Pthreads standard includes a special type for mutexes: pthread mutex t. A variable of type
pthread mutex t needs to be initialized by the system before it’s used. This can be done with a call
to

● We won’t make use of the second argument, so we’ll just pass in NULL .
Mutexes

● When a Pthreads program finishes using a mutex, it should call

○ int pthread mutex destroy(pthread mutex t ∗ mutex p / ∗ in/out ∗/);
● To gain access to a critical section, a thread calls
○ int pthread mutex lock(pthread mutex t ∗ mutex p / ∗ in/out ∗/);
● When a thread is finished executing the code in a critical section, it should call
○ int pthread mutex unlock(pthread mutex t ∗ mutex p / ∗ in/out ∗/);
Mutexes

● The call to pthread mutex lock will cause the thread to wait until no other thread is in the critical
section,
● The call to pthread mutex unlock notifies the system that the calling thread has completed
execution of the code in the critical section.
● We can use mutexes instead of busy-waiting in our global sum program by declaring a global mutex
variable,
○ The main thread initialize it, and then, instead of busy-waiting and incrementing a flag,
● The threads call pthread mutex lock before entering the critical section, and they call pthread
mutex unlock when they’re done with the critical section.
Mutexes
Mutexes

● The first thread to call pthread mutex lock will, effectively, “lock the door” to the critical section.
● Any other thread that attempts to execute the critical section code must first also call pthread mutex lock ,
○ Until the first thread calls pthread mutex unlock , all the threads that have called pthread mutex lock will block in their
calls
● After the first thread calls pthread mutex unlock , the system will choose one of the blocked threads and
allow it to execute the code in the critical section.
● This process will be repeated until all the threads have completed executing the critical section.
● Locking” and “unlocking” the door to the critical section isn’t the only metaphor that’s used in connection
with mutexes.
○ Programmers often say that the thread that has returned from a call to pthread mutex lock has “obtained the mutex”
or “obtained the lock.”
○ A thread that calls pthread mutex unlock “relinquishes” the mutex or lock.
Mutexes

● Notice that with mutexes (unlike our busy-waiting solution), the order in which the threads
execute the code in the critical section is more or less random:
● The first thread to call pthread mutex lock will be the first to execute the code in the critical
section.
● Subsequent accesses will be scheduled by the system.
○ Pthreads doesn’t guarantee (for example) that the threads will obtain the lock in the order in which they
called Pthread mutex lock .
● Only finitely many threads will try to acquire the lock. Eventually each thread will obtain the lock
Mutex Performance

● The mutex program, we see that for both versions the ratio of the run-time of the single-threaded
program with the multithreaded program is equal to the number of threads, as long as the number
of threads is no greater than the number of cores.

● In which provided thread count is less than or equal to the number of cores.
● T serial /T parallel is called the speedup,
● When the speedup is equal to the number of threads, we have achieved more or less “ideal”
performance or linear speedup.
Mutex Cost

● If we compare the performance of the version that

uses busy-waiting with the version that uses
mutexes,
● The programs are run with fewer threads than cores.
● That is expected
○ Unless the critical section is very long, or the
Pthreads functions are very slow,
● if we start increasing the number of threads beyond
the number of cores, the performance of the
● version that uses mutexes remains pretty much
unchanged,
● While the performance of the busy-wait version
degrades.
Busy-waiting on multi-core
Semaphores
Semaphores
● Busy-waiting is generally wasteful of CPU resources, but it has the property by which
we know, in advance, the order in which the threads will execute the code
○ Thread 0 is first, then thread 1, then thread 2, and so on.
● While mutexes guarantees that all threads will enter critical section, but order of
thread is ubiquitous
● It’s not difficult to think of situations in which we also want to control the order in
which the threads execute the code in the critical section.
Ordered thread problem - 2

● For example, suppose each thread generates an n × n matrix, and we want to multiply the matrices
together in thread-rank order.
Ordered thread problem - 2

● Each thread “send a message” to another thread.

● We want thread 0 to send a message to thread 1, thread 1 to send a message to thread 2, . . . ,
thread t − 2 to send a message to thread t − 1 and thread t − 1 to send a message to thread 0.
○ Circular manner
● After a thread “receives” a message, it can print the message and terminate.
● In order to implement the message transfer, we can allocate a shared array of char∗ .
● Each thread can allocate storage for the message it’s sending, and, after it has initialized the
message, set a pointer in the shared array to refer to it.
● In order to avoid dereferencing undefined pointers, the main thread can set the individual entries
in the shared array to NULL .
Ordered thread problem - 2

if -else block sync

problem?
Ordered thread problem - 2
Ordered thread problem - 2

● After executing the assignment in Line 10, we’d like to “notify” the thread with rank dest that it can
proceed to print the message. We’d like to do something like this:
Ordered thread problem - 2

● It’s not at all clear how mutexes can be of help here.

● We might try calling pthread mutex unlock to “notify” the thread with rank dest .
● However, mutexes are initialized to be unlocked, so we’d need to add a call before initializing
messages [ dest ] to lock the mutex.
● This will be a problem since we don’t know when the threads will reach the calls to pthread mutex
lock
● To make this a little clearer, suppose that the main thread creates and initializes an array of
mutexes, one for each thread.
Ordered thread problem - 2
Semaphores

● POSIX also provides a somewhat different means of controlling access to critical sections:
semaphores.
● Semaphores can be thought of as a special type of unsigned int , so they can take on the values 0, 1,
2, . . . .
● In most cases, we’ll only be interested in using them when they take on the values 0 and 1.
○ A semaphore that only takes on these values is called a binary semaphore.
○ 0 corresponds to a locked mutex, and 1 corresponds to an unlocked mutex.
● To use a binary semaphore as a mutex, you initialize it to 1—that is, it’s “unlocked.”
Semaphores

● Before the critical section you want to protect, you place a call to the function sem_wait.
● A thread that executes sem wait will block if the semaphore is 0. If the semaphore is nonzero, it will
decrement the semaphore and proceed.
● After executing the code in the critical section, a thread calls sem_post
● sem_post increments the semaphore, and a thread waiting in sem wait can proceed.
Semaphores
Semaphores

● The syntax of the various semaphore functions is

Semaphores

● Finally, note that the message-sending problem didn’t involve a critical section.
● The problem wasn’t that there was a block of code that could only be executed by one thread at a
time.
● Thread my rank couldn’t proceed until thread source had finished creating the message.
● This type of synchronization, when a thread can’t proceed until another thread has taken some
action, is sometimes called producer-consumer synchronization.
Barriers

● Barrier : Synchronizing the threads by making sure that they all are at the same point in a program.
○ Such a point of synchronization is called a barrier because no thread can proceed beyond the barrier until all
the threads have reached it
Barrier - Busy waiting and mutex
Barrier - Semaphores
Condition variables

● A somewhat better approach to creating a barrier in Pthreads is provided by condition variables.

● A condition variable is a data object that allows a thread to suspend execution until a certain event
or condition occurs.
● When the event or condition occurs another thread can signal the thread to “wake up.” A condition
variable is always associated with a mutex.
Condition Variables

● Condition variables in Pthreads have type pthread_cond_t .

● Unlock mutex and waiting on condition
○ int pthread cond wait(pthread_cond_t * cond var, pthread_mutex_t * mutex);
● Unblock one waiting thread :
○ int pthread cond signal(pthread cond t ∗ cond var p / ∗ in/out ∗/);
● Unblock all waiting threads:
○ int pthread cond broadcast(pthread cond t ∗ cond var p / ∗ in/out ∗/);
● So in effect, pthread cond wait implements the following sequence of functions:
○ pthread mutex unlock(&mutex p);
○ wait on signal(&cond var p);
○ pthread mutex lock(&mutex p);
Barriers - Condition Variables
BBM101- Bilgisayar Programlamaya Giriş-I

Questions