|
CPU 1 CPU 2
--------------------- ------------------------
move.l bal, D0 (D0 = 1000)
move.l bal, D0 (D0 = 1000)
add.l #100, D0 (D0 = 1100)
sub.l #200, D0 (D0 = 800)
move.l D0, bal (bal = 1100)
move.l D0, bal (bal = 800)
|
And when both threads finish with their access of the "balance" variable, the resulting value of balance is 800 !
From CS351, you may have learned the following common synchronization methods:
You can construct Binary semaphores and Counting semaphores using Conditional variables...
So it is no big deal that PThreads do not implement them...
(There are different way to achieve this "atomic" execution effect and will not discussed here. If you are interested, read more on "interrupt disable", "test-and-set" instructions)
pthread_mutex_t x; |
int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr); Example: pthread_mutex_init(&x, NULL); /* Default initialization */ |
int pthread_mutex_lock(pthread_mutex_t *mutex); Example: pthread_mutex_lock(&x); |
int pthread_mutex_unlock(pthread_mutex_t *mutex); Example: pthread_mutex_unlock(&x); |
A common usage of mutex is to synchronize updates to shared (global) variables
Whenever a thread want to read or write a shared variable, it must enclose the operation by a "lock - unlock" pair.
Example:
The atomic execution of the mutex lock function prevents multiple threads from executing instructions that access the common variable.
A common error is to forget the unlock call... the result is "deadlock" - you program hangs (no progress)
void MutexInit(mutex **m)
{
*m = (mutex *) malloc(sizeof(mutex));
pthread_mutex_init(&((*m)->mutex), NULL);
}
Usage: mutex *x;
MutexInit(&x);
|
void MutexLock(mutex *m)
{
if (m == NULL)
{ fprintf(stderr, "Err: Uninitialized mutex\n");
exit(1);
}
pthread_mutex_lock(&(m->mutex));
}
Usage: MutexLock(x);
|
void MutexUnLock(mutex *m)
{
if (m == NULL)
{ fprintf(stderr, "Err: Uninitialized mutex\n");
exit(1);
}
pthread_mutex_unlock(&(m->mutex));
}
Usage: MutexUnLock(x);
|
int pthread_rwlock_init(pthread_rwlock_t *rwlock, const pthread_rwlockattr_t *attr); |
The "test-and-set(x)" operation on a (memory) variable "x" performs the following operations atomically:
The test-and-set operation is a powerful operation that can be use to implement all shared memory synchronization primitives.
pthread_mutex_init(&x) <----> x = 0; |
pthread_mutex_lock(&x) <--> Loop: if ( test-and-set(x) == 1 ) goto Loop; |
pthread_mutex_unlock(&x) <----> x = 0; |
int pthread_cond_init(pthread_cond_t *cond,
const pthread_condattr_t *attr);
Example:
pthread_cond_t x;
pthread_cond_init(&x, NULL);
|
int pthread_cond_wait(pthread_cond_t *cond,
pthread_mutex_t *mutex);
|
Atomically:
int pthread_cond_signal(pthread_cond_t *cond); |
sema.phore \'sem-*-.fo-(*)r, -.fo.(*)r\ n [Gk se-ma sign, signal + ISV -phore] 1: an apparatus for visual signaling (as by the position of one or more movable arms) 2: a system of visual signaling by two flags held one in each hand |
If s = 1 (up), P(s) returns immediately and the thread that executes the P(s) operation continues - this is the success case (no train in the critical section)
If s = 0 (down), P(s) blocks - the thread executing the P(s) operation will be made unrunnable (not ready to run) and put in a queue that is associated with the semaphore s.
Note: the "P" operation is the acronym for Pass - Dutch: Passeren)
Set s = 1 and if the queue that is associated with the semaphore s is not empty, then reactivate a block process from that queue
Note: V(s) always succeeds (leaving the critical section can always be done).
Note: the "V" operation is the acronym for leaVe :-) - Just kidding, you need to know Dutch to find the acronym: Verlaten in Dutch means to leave.... hence the V - remember, Dijkstra was a Dutch...)
typedef struct BIN_SEMA
{
pthread_cond_t cv; /* cond. variable
- used to block threads */
pthread_mutex_t mutex; /* mutex variable
- used to prevents concurrent
access to the variable "flag" */
int flag; /* Semaphore state:
0 = down, 1 = up */
} bin_sema;
|
void BinSemaInit(bin_sema **s)
{
/* Allocate space for bin_sema */
*s = (bin_sema *) malloc(sizeof(bin_sema));
/* Init mutex */
pthread_mutex_init(&((*s)->mutex), NULL);
/* Init cond. variable */
pthread_cond_init(&((*s)->cv), NULL);
/* Set flag value */
(*s)->flag = 1;
}
|
void BinSemaP(bin_sema *s)
{
/* Try to get exclusive access to s->flag */
pthread_mutex_lock(&(s->mutex));
/* Success - no other thread can get here unless
the current thread unlock "mutex" */
/* Examine the flag and wait until flag == 1 */
while (s->flag == 0)
{
pthread_cond_wait(&(s->cv), &(s->mutex) );
/* When the current thread execute this
pthread_cond_wait() statement, the
current thread will be block on s->cv
and (atomically) unlocks s->mutex !!!
Unlocking s->mutex will let other thread
in to test s->flag.... */
}
/* -----------------------------------------
If the program arrive here, we know that
s->flag == 1 and this thread has now
successfully pass the semaphore !!!
------------------------------------------- */
s->flag = 0; /* This will cause all other threads
that executes a P() call to wait
in the (above) while-loop !!! */
/* Release exclusive access to s->flag */
pthread_mutex_unlock(&(s->mutex));
}
|
The V-operation is relatively easy - remember that the thread that calls V() must have been successful in a P() operation and this thread "owns" the semaphore....
void BinSemaV(bin_sema *s)
{
/* Try to get exclusive access to s->flag */
pthread_mutex_lock(&(s->mutex));
pthread_cond_signal(&(s->cv));
/* This call may restart some thread that
was blocked on s->cv (in the P() call)
- if there was not thread blocked on
- cv, this operation does absolutely
- nothing... */
/* Update semaphore state to Up */
s->flag = 1;
/* Release exclusive access to s->flag */
pthread_mutex_unlock(&(s->mutex));
}
|
Thread 1: Thread 2: BinSemaP(s); BinSemaP(s); balance = balance + 100; balance = balance - 200; BinSemaV(s); BinSemaV(s); |
The famous "Reader and Writer" synchronization problem can be solved with semaphores, but not with mutexes:
share variable x
Reader sums all values written by writer exactly once
Main:
Use 2 semaphores:
ReadSema and WriteSema
BinSemaInit(WriteSema, 1); /* Allow writer to start first */
BinSemaInit(ReadSema, 0); /* Block reader until writer
has written something */
|
|
|
来自： astrotycoon > 《thread》
