MUTEX & CONDITIONAL VARIABLES TERRIBLE
THREADS
• • •
Synchronization primitives
Common patterns in multithreaded programs Thread-safe data structures and their design
OBJECTIVE
•
•
•
•
•
Rendezvous Ungraded
OUTLINE
Semamore
A extended version of semaphore, bounded above
Thread safe queue
RENDEZVOUS
abc->bcd
PRINT B
DATA A
THREAD I
MODIFY A
THREAD II
MODIFY B
PRINT A
result: A:bcd B:efg
DATA B
def->efg
create thread I, thread J I -> modify A print B J-> modify B print A
possible result
• • • •
• • • •
How to use a semaphore to solve it?
•
J modify B really fast, I is still sleeping J print A when I just started modifying J print A[0] before I modify it
A: acd B:efg
RENDEZVOUS WITHOUT SEMAPHORE
• •
• • •
•
SEMAMORE UPPER-BOUNDED SEMAPHORE
A semaphore that blocks when it reaches some maximum value typedef struct {
int value, max_value; pthread_mutext_t m; pthread_cond_t cv;
} Semamore;
•
•
•
•
•
•
SEMAMORE DONEC QUIS NUNC
When max_value is reached
All thread trying to post should be blocked
Where/How do you notify these blocked threads when a thread decrease semamore’s value so its not max_value?
When 0 is reached
All thread trying to wait should be blocked
Where/How do you notify these blocked thread when a thread increase semamore’s value so it’s not 0?
SEMAMORE SEMM_WAIT
SEMAMORE
Two processes cannot access semamore in the same time!!!!
value == 0 wait till value > 0
How do I know if the value is change?
value > 0 decrease value
What should I do if the value is deceased from max value
THREAD-SAFE QUEUE
A queue that is safe even in multi-thread programs.
No two threads can access it(pull/push) at the same time.
Remember to lock the queue before you do anything. No overflow/underflow problem
If it is full -> block on every push request
If it is empty-> block on every pull request
If you pass a negative value to maxSize, then the queue should be unbounded.
•
•
•
•
•
•
•
QUEUE
THREAD-SAFE QUEUE QUEUE_PUSH
BLOCK
Wait until condition: size != max_size
INCOMING ELEMENT
TO REMIND YOU..
Use while loop to check the condition when using cond_wait.
•
• A thread might be awoken even the condition for waking up is not reached.
• Google spurious wakeup ( https://goo.gl/TEJVOl)
• Write a correctly working queue first before making it thread-safe.
PTHREAD_MUTEX_INITIALIZER only works for initialization.
Use pthread_mutex_init(&mtex, NULL) if you are not at the place declare it.
• Think of all critical cases to test your queue/semamore
• One thread can start working really late
• One thread might get modify data structure at any time.
Semamore is not a really term!!
•
•
•