[go: up one dir, main page]
Scribd
Upload
53 views26 pages

SPThreads 5 Sync

1) Read-write locks and barriers are additional synchronization primitives that can be built using mutexes and condition variables. 2) Deadlock occurs when threads are waiting for each other in a cyclic manner. It can be avoided by enforcing a fixed locking order. 3) The readers-writers problem involves synchronizing access to a data structure that is frequently read but infrequently written. Read-write locks and mutex/condition variable implementations can solve this problem.

Uploaded by

loopnumber2020
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
53 views26 pages

SPThreads 5 Sync

1) Read-write locks and barriers are additional synchronization primitives that can be built using mutexes and condition variables. 2) Deadlock occurs when threads are waiting for each other in a cyclic manner. It can be avoided by enforcing a fixed locking order. 3) The readers-writers problem involves synchronizing access to a data structure that is frequently read but infrequently written. Read-write locks and mutex/condition variable implementations can solve this problem.

Uploaded by

loopnumber2020
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 26

(T5): More Threads Synchronization

Ion Mandoiu
Laurent Michel
Revised by M. Khan and J. Shi
More Synchronization Primitives

• So far
• Mutexes
• Condition variables
• Today
• Read-write locks
• Barriers

Mutexes and condition variables are primitive constructs


• Read-Write Locks and Barriers can be built using mutexes and
condition variables
2
Deadlock

• Deadlock is a state in which no member can make progress


• All are waiting for other members to take actions
• A member can be a thread, a process, a computer, etc.

Example: Two mutexes A and B

Thread 1, locked A, try to get B

Thread 2, locked B, try to get A


Common solutions

• Fixed order
• All the threads lock mutexes in the same order

m0, m1, and so on

• Try and back off


• Try to lock. If it fails, release all locks and try again
Readers-Writers Problem

• In many applications, a data structure is read frequently but written


infrequently
• Constraints:
• Multiple readers can read simultaneously
• A reader can start even if other readers are reading
• Only one writer can write at a time
• Read and write cannot happen at the same time
• A reader has to wait if a writer is writing
• A writer has to wait for other readers and writers to finish

5
Solutions?

• Use Pthreads read-write locks


• Like a mutex with two different lock functions (read/write)

• Use mutex and condition variables


• Keep track of the number of readers and writers
• Active and watiting
• Choose proper predicate
• If the predicate is true, proceed to read/write
• If the predicate not true, wait
• Notify others when a thread is done with reading/writing
6
Pthread Read-Write Lock

#include <pthread.h>
pthread_rwlock_t rwlock; // define a read-write lock

// initialize and destroy a read-write lock


int pthread_rwlock_init(pthread_rwlock_t *restrict rwlock,
const pthread_rwlockattr_t *restrict attr);
int pthread_rwlock_destroy(pthread_rwlock_t *rwlock);

// lock functions for readers and writers, and unlock


int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock);
int pthread_rwlock_unlock(pthread_rwlock_t *rwlock);
7
Pthread Read-Write Locks For Reading

• First lock function locks for reading


• A thread gets read lock if and only if no writer has the lock and no
writer is blocked on the lock
• More than one thread can get the read lock

8
Pthread Read-Write Locks For Writing

• Second lock function locks for writing


• A thread gets write lock if and only if no reader or writer has the lock
• Wait for read lock, too !
• Only one writer is allowed at any time

9
Read-Write Lock Issues

• Writer starvation
• Too many readers. Writers do not have a chance to start
• Solution?
• "write locks shall take precedence over read locks"
• which leads to reader starvation

• Reader starvation: readers do not have a chance


• Too many writers. Readers do not have a chance
• Another writer starts when a writer unlocks

10
Pthread read-write lock

• Pthread rwlock prefers writer


• From the manual page

The pthread_rwlock_rdlock() function shall apply a read


lock to the read-write lock referenced by rwlock.
The calling thread acquires the read lock if a writer
does not hold the lock and there are no writers blocked
on the lock.

11
Use mutex and condition to implement rwlock

• Using mutex and condition is more flexible, we can adjust our strategy
• There are many ways

• Best for us:


One mutex and two condition variables (one for rd, one for wr)
• Keep track of the numbers needed by the predicate

http://heather.cs.ucdavis.edu/~matloff/158/PLN/RWLock.c

12
Pseudocode for rwlock lock

pthread_mutex_lock(&mutex);
// increment/decrement waiting counter and the while loop
increment waiting counter
// predicate depends on the policy!
while (! predicate) // check if this thread can lock
pthread_cond_wait(&cond); // using either rd or wr condition
decrement waiting counter
increment active counter
pthread_mutex_unlock(&mutex);
// rwlock is locked. Can start to read/write
// Note that mutex is unlocked!

13
Pseudocode for rwlock unlock

Perform read/write operations // Depending on the lock type


// unlock rwlock when the operation is done
pthread_mutex_lock(&mutex);
decrement active counter
// inform waiting threads
// policy decides checking writer or reader first
if there is a writer waiting
signal write cond
if there is a reader waiting // only needed for write unlock
broadcast read cond
pthread_mutex_unlock(&mutex);

14
Example: rwlock_writeunlock()

Does this lock prefer reader or writer? A: reader B: writer C: don't know

status = pthread_mutex_lock (&rwl->mutex);


rwl->w_active = 0;
if (rwl->r_wait > 0) {
status = pthread_cond_broadcast (&rwl->read);
if (status != 0) {
pthread_mutex_unlock (&rwl->mutex);
return status;
}
} else if (rwl->w_wait > 0) {
status = pthread_cond_signal (&rwl->write);
if (status != 0) {
pthread_mutex_unlock (&rwl->mutex);
return status;
}
}
pthread_mutex_unlock (&rwl->mutex);
15
Barriers

• Purpose
• For applications where work is done in “phases”
• Must have “worker” threads wait for the entire “group” to be done before
proceeding to next phase
• Number of workers known a priori

16
Visually

T1

T2

T3

T4

T5

5 17
Visually

T1

T2

T3

T4

T5

5 18
Visually

T1

T2

T3

T4

T5 Zzzz…

5 19
Visually

T1

T2 Zzzz…

T3 Zzzz…

T4

T5 Zzzz…

5 20
Visually

T1

T2 Zzzz…

T3 Zzzz…

T4 Zzzz…

T5 Zzzz…

5 21
Visually

T1

T2 Zzzz…

T3 Zzzz…

T4 Zzzz…

T5 Zzzz…

5 22
Visually

5 Last one
notifies!
T1

T2 Zzzz…

T3 Zzzz…

T4 Zzzz…

T5 Zzzz…

5 23
Reusable Barrier?

T1

T2 Wakeup…

T3 Wakeup…

T4 Wakeup…

T5 Wakeup…

24
POSIX Barriers Support

#include <pthread.h>
// create barrier. note the count argument
int pthread_barrier_init(pthread_barrier_t *restrict barrier,
const pthread_barrierattr_t *restrict attr, unsigned count);

// destroy a barrier
int pthread_barrier_destroy(pthread_barrier_t *barrier);

// wait on a barrier. When the function returns,


// one thread gets PTHREAD_BARRIER_SERIAL_THREAD, others get 0
int pthread_barrier_wait(pthread_barrier_t *barrier);

25
Sync mechanisms in this course

• We can use mutex, condition, read/write lock, barriers, and only call
blocking functions!

• The following mechanisms are not allowed for synchronization!


• Busy waiting, like spin lock
• sleep functions

26

You might also like