So when execute concurrently, the result depends on how the instructions
interleave. What are possible results?
0 : 1 0 : 1
1 : 2 1 : 1
1 : 2 1 : 1
0 : 1 0 : 1
1 : 1 0 : 2
0 : 2 1 : 2
0 : 2 1 : 2
1 : 1 0 : 2
So the results are nondeterministic - you may get different results when you run
the program more than once. So, it can be very difficult to reproduce bugs.
Nondeterministic execution is one of the things that makes writing parallel
programs much more difficult than writing serial programs.
Chances are, the programmer is not happy with all of the possible results
listed above. Probably wanted the value of a to be 2 after both
threads finish. To achieve this, must make the increment operation atomic. That
is, must prevent the interleaving of the instructions in a way that would
interfere with the additions.
Concept of atomic operation. An atomic operation is one that executes
without any interference from other operations - in other words, it executes as
one unit. Typically build complex atomic operations up out of sequences of
primitive operations. In our case the primitive operations are the individual
machine instructions.
More formally, if several atomic operations execute, the final result is
guaranteed to be the same as if the operations executed in some serial order.
In our case above, build an increment operation up out of loads, stores and
add machine instructions. Want the increment operation to be atomic.
Use synchronization operations to make code sequences atomic. First
synchronization abstraction: semaphores. A semaphore is, conceptually, a counter
that supports two atomic operations, P and V. Here is the Semaphore interface
from Nachos:
class Semaphore {
public:
Semaphore(char* debugName, int initialValue);
~Semaphore();
void P();
void V();
}
Here is what the operations do:
- Semphore(name, count) : creates a semaphore and initializes the
counter to count.
- P() : Atomically waits until the counter is greater than 0, then
decrements the counter and returns.
- V() : Atomically increments the counter.
Here is how we can use the semaphore to make the sum example
work:
int a = 0;
Semaphore *s;
void sum(int p) {
int t;
s->P();
a++;
t = a;
s->V();
printf("%d : a = %d\n", p, t);
}
void main() {
Thread *t = new Thread("child");
s = new Semaphore("s", 1);
t->Fork(sum, 1);
sum(0);
}
We are using semaphores here to implement a mutual exclusion mechanism. The
idea behind mutual exclusion is that only one thread at a time should be allowed
to do something. In this case, only one thread should access a. Use
mutual exclusion to make operations atomic. The code that performs the atomic
operation is called a critical section.
