- Forward


Ensuring the Mutual Exclusion of Shared Variables
in Pthreads


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Review
Back SMYC Forward
  • Threads:
    • A mechanism that permits a single process to perform multiple tasks concurrently
  • Shared Variables:
    • Threads share the initialized data, uninitialized data, and heap segments
The Good and the Bad
Back SMYC Forward
  • The Good:
    • Because threads share the "global" data segments it is easy for them to share information
  • The Bad:
    • Multiple threads can modify the value of a variable concurrently
    • Some threads can be modifying the value of a variable while others are retrieving the value
The Bad (cont.)
Back SMYC Forward
unixexamples/mutexes/threaded_counter_race.c
 
The Bad (cont.)
Back SMYC Forward
  • Counting to 200:
    • thread_a probably finishes before thread_b starts so the expected and actual are the same
  • Counting to 20,000,000:
    • The two threads each get some time on the processor so the lack of coordination causes a failure
The Bad (cont.)
Back SMYC Forward
  • The Race Condition:
    • Read-Modify-Write
  • The Implications:
    • thread_a can read global_counter, assign its value to local_counter, modify local_counter, and then get swapped-off before it writes global_counter
    • thread_b can then read global_counter (which contains an incorrect value)
The Bad (cont.)
Back SMYC Forward
  • Is This Example Contrived?
    • A little, but just to make the race condition obvious
  • An Observation:
    • On some architectures ++global_counter is not atomic meaning the same race condition exists
Coordination
Back SMYC Forward
  • An Important Property of Some Coordination Protocols:
    • Mutual exclusion - it is possible to exclude multiple parties from using a resource at the same time
  • What's Needed:
    • We must ensure that threads use shared variables in a mutually exclusive way
Ensuring Mutual Exclusion
Back SMYC Forward
  • The Mechanism:
    • pthread_mutex_t variables
  • States:
    • "Locked" and "Unlocked"
  • Ownership:
    • A thread that "locks" (a.k.a. "acquires") a pthread_mutex_t variable becomes the "owner" of that variable
    • Only the "owner" of a pthread_mutex_t variable can "unlock" (a.k.a. "release") it
    • A thread that attempts to "lock" a "locked" pthread_mutex_t will block until it is "unlocked"
Using "Mutexes" (i.e., pthread_mutex_t Variables)
Back SMYC Forward
  • Pattern:
    • Use one mutex for each resource that needs to be shared
  • Protocol:
    • Lock the mutex for the shared resource
    • Use the shared resource (in the critical section of the code) for as little time as possible
    • Unlock the mutex
Using "Mutexes" (cont.)
Back SMYC Forward
  • Power/Authority:
    • A mutex is not like a permission -- it doesn't prevent a resource from being used
  • Implication:
    • Threads must cooperate (i.e., agree to follow the protocol)
Creating Mutexes
Back SMYC Forward
  • Step 1 - Allocation:
    • Allocate memory for the mutex either statically in the initialized data segment, automatically (on the stack), or dynamically (on the heap)
  • Step 2 - Initialization:
    • Assign attributes to the mutex
Creating Mutexes (cont.)
Back SMYC Forward
  • Static Allocation and Initialization:
    • static pthread_mutex_t example = PTHREAD_MUTEX_INITIALIZER
  • Dynamic Initialization:
    • Must be used for mutexes that are dynamically allocated (on the heap) or automatically allocated (on the stack)
    • Can be used for mutexes that are statically allocated when non-default attributes are needed
State Transitions
Back SMYC Forward
  • Initial State:
    • A mutex is initially unlocked/unowned
  • Transitions:
    • A mutex can transition from being unlocked/unowned to locked/owned
    • A mutex can transition from being locked/owned to unlocked/unowned
Locking: pthread_mutex_lock() pthread_mutex_lock
Back SMYC Forward
int pthread_mutex_lock(pthread_mutex_t *mutex)
Purpose:
Lock (i.e., acquire or become the owner of) a mutex
Details:
mutex The mutex
Return 0 on success; positive error number on error
#include <pthread.h> pthread.h
Attempting to Lock a Locked Mutex
Back SMYC Forward
  • By the thread that owns the mutex:
    • The thread deadlocks (unless the thread's type is PTHREAD_MUTEX_ERROR_CHECK or PTHREAD_MUTEX_RECURSIVE, neither of which is the default)
  • By another thread:
    • The thread blocks until the mutex is unlocked by the owning thread (at which point some indeterminate blocked thread will unblock and become the owner)
Unlocking: pthread_mutex_unlock() pthread_mutex_unlock
Back SMYC Forward
int pthread_mutex_unlock(pthread_mutex_t *mutex)
Purpose:
Unlock (i.e., release) a mutex
Details:
mutex The mutex
Return 0 on success; positive error number on error
#include <pthread.h> pthread.h
Unlock Errors
Back SMYC Forward
  • Attempting to Unlock an Unlocked Mutex:
    • EINVAL
  • Attempting to Unlock a Mutex Owned by Another Thread:
    • EPERM
A Corrected Example
Back SMYC Forward
unixexamples/mutexes/threaded_counter_mutex.c
 
Performance
Back SMYC Forward
  • Costs:
    • Locking and unlocking a mutex both take time
  • Coarse Measures of Performance:
    • time time can be used to obtain both the amount of time spent executing in user mode and the amount of time spend executing in kernel mode
Performance (cont.)
Back SMYC Forward
  • Two Threads with Race Condition (10,000,000 iterations each):
    • User 0.328s; Kernel 0.000s
  • Two Threads with Mutexes (10,000,000 iterations each):
    • User 3.088s; Kernel 4.176s
  • One Thread with Mutexes (20,000,000 iterations):
    • User 0.464s; Kernel 0.000s
  • Main Thread (20,000,000 iterations):
    • User 0.120s; Kernel 0.000s
Variants of pthread_mutex_lock()
Back SMYC Forward
  • pthread_mutex_trylock() pthread_mutex_trylock :
    • Does not block; returns EBUSY if the mutex is locked
    • Can be used to check if a mutex is locked
  • pthread_mutex_timedlock() pthread_mutex_timedlock :
    • Places a limit on the blocking time; returns ETIMEDOUT if the lock can't be acquired within the limit
Avoiding Deadlocks
Back SMYC Forward
  • Use a Hierarchy:
    • Have all threads lock mutexes in the same order
  • Back Off:
    • Lock the first mutex and then use pthread_mutex_trylock() on the others. If there are any errors release all of the locks, delay a random amount of time, and try again.
Dynamic Initialization: pthread_mutex_init() pthread_mutex_init
Back SMYC Forward
int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr)
Purpose:
Initialize a mutex
Details:
mutex The mutex to be initialized
attr The attributes to use (of NULL for the default attributes)
Return 0 on success; a positive error number on error
#include <pthread.h> pthread.h
Mutex Attributes
Back SMYC Forward
  • Linux:
    • Only supports one attribute (the "type"), which determines what happens when a thread attempts to lock a mutex it owns (and all of the kinds are non-portable)
  • SUSv3:
    • Has three "types", PTHREAD_MUTEX_NORMAL does not detect self-deadlock, PTHREAD_MUTEX_ERRORCHECK provides error checking, and PTHREAD_MUTEX_RECURSIVE uses a lock count
Destruction
Back SMYC Forward
  • Which Mutexes?
    • Those that are automatically or dynamically allocated
  • When?
    • When the mutex is unlocked (and no longer needed)
    • Before freeing the memory (for dynamically allocated) or before the "host function" returns (for automatically allocated)
Destruction (cont.): pthread_mutex_destroy() pthread_mutex_destroy
Back SMYC Forward
int pthread_mutex_destroy(pthread_mutex_t *mutex)
Purpose:
Indicate that a mutex will no longer be used
Details:
mutex The mutex to be destroyed
Return 0 on success; a positive error number on error
#include <pthread.h> pthread.h
There's Always More to Learn
Back -