|
main
Thread 1
Thread2
starts running
prints “main: begin”
creates Thread 1
creates Thread 2
waits for T1
runs
prints “A”
returns
waits for T2
runs
prints “B”
returns
prints “main: end”
Table 26.1: Thread Trace (1)
main
Thread 1
Thread2
starts running
prints “main: begin”
creates Thread 1
runs
prints “A”
returns
creates Thread 2
runs
prints “B”
returns
waits for T1
returns immediately; T1 is done
waits for T2
returns immediately; T2 is done
prints “main: end”
Table 26.2: Thread Trace (2)
main
Thread 1
Thread2
starts running
prints “main: begin”
creates Thread 1
creates Thread 2
runs
prints “B”
returns
waits for T1
runs
prints “A”
returns
waits for T2
returns immediately; T2 is done
prints “main: end”
Table 26.3: Thread Trace (3)
O
PERATING
S
YSTEMS
[V
ERSION
0.80]
WWW
.
OSTEP
.
ORG
C
ONCURRENCY
: A
N
I
NTRODUCTION
267
1
#include
2
#include
3
#include "mythreads.h"
4
5
static volatile int counter = 0;
6
7
//
8
// mythread()
9
//
10
// Simply adds 1 to counter repeatedly, in a loop
11
// No, this is not how you would add 10,000,000 to
12
// a counter, but it shows the problem nicely.
13
//
14
void *
15
mythread(void *arg)
16
{
17
printf("%s: begin\n", (char *) arg);
18
int i;
19
for (i = 0; i < 1e7; i++) {
20
counter = counter + 1;
21
}
22
printf("%s: done\n", (char *) arg);
23
return NULL;
24
}
25
26
//
27
// main()
28
//
29
// Just launches two threads (pthread_create)
30
// and then waits for them (pthread_join)
31
//
32
int
33
main(int argc, char *argv[])
34
{
35
pthread_t p1, p2;
36
printf("main: begin (counter = %d)\n", counter);
37
Pthread_create(&p1, NULL, mythread, "A");
38
Pthread_create(&p2, NULL, mythread, "B");
39
40
// join waits for the threads to finish
41
Pthread_join(p1, NULL);
42
Pthread_join(p2, NULL);
43
printf("main: done with both (counter = %d)\n", counter);
44
return 0;
45
}
Figure 26.3: Sharing Data: Oh Oh (t2)
26.2 Why It Gets Worse: Shared Data
The simple thread example we showed above was useful in showing
how threads are created and how they can run in different orders depend-
ing on how the scheduler decides to run them. What it doesn’t show you,
though, is how threads interact when they access shared data.
c
2014, A
RPACI
-D
USSEAU
T
HREE
E
ASY
P
IECES
268
C
ONCURRENCY
: A
N
I
NTRODUCTION
Let us imagine a simple example where two threads wish to update a
global shared variable. The code we’ll study is in Figure
26.3
.
Here are a few notes about the code. First, as Stevens suggests [SR05],
we wrap the thread creation and join routines to simply exit on failure;
for a program as simple as this one, we want to at least notice an error
occurred (if it did), but not do anything very smart about it (e.g., just
exit). Thus, Pthread create() simply calls pthread create() and
makes sure the return code is 0; if it isn’t, Pthread create() just prints
a message and exits.
Second, instead of using two separate function bodies for the worker
threads, we just use a single piece of code, and pass the thread an argu-
ment (in this case, a string) so we can have each thread print a different
letter before its messages.
Finally, and most importantly, we can now look at what each worker is
trying to do: add a number to the shared variable counter, and do so 10
million times (1e7) in a loop. Thus, the desired final result is: 20,000,000.
We now compile and run the program, to see how it behaves. Some-
times, everything works how we might expect:
prompt> gcc -o main main.c -Wall -pthread
prompt> ./main
main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 20000000)
Unfortunately, when we run this code, even on a single processor, we
don’t necessarily get the desired result. Sometimes, we get:
prompt> ./main
main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 19345221)
Let’s try it one more time, just to see if we’ve gone crazy. After all,
aren’t computers supposed to produce deterministic results, as you have
been taught?! Perhaps your professors have been lying to you? (gasp)
prompt> ./main
main: begin (counter = 0)
A: begin
B: begin
A: done
B: done
main: done with both (counter = 19221041)
Not only is each run wrong, but also yields a different result! A big
question remains: why does this happen?
O
PERATING
S
YSTEMS
[V
ERSION
0.80]
WWW
.
OSTEP
.
ORG
C
ONCURRENCY
: A
N
I
NTRODUCTION
269
T
IP
: K
NOW
A
ND
U
SE
Y
OUR
T
OOLS
You should always learn new tools that help you write, debug, and un-
derstand computer systems. Here, we use a neat tool called a disassem-
bler.
When you run a disassembler on an executable, it shows you what
assembly instructions make up the program. For example, if we wish to
understand the low-level code to update a counter (as in our example),
we run objdump (Linux) to see the assembly code:
prompt> objdump -d main
Doing so produces a long listing of all the instructions in the program,
neatly labeled (particularly if you compiled with the -g flag), which in-
cludes symbol information in the program. The objdump program is just
one of many tools you should learn how to use; a debugger like gdb,
memory profilers like valgrind or purify, and of course the compiler
itself are others that you should spend time to learn more about; the better
you are at using your tools, the better systems you’ll be able to build.
26.3 The Heart of the Problem: Uncontrolled Scheduling
To understand why this happens, we must understand the code se-
quence that the compiler generates for the update to counter. In this
case, we wish to simply add a number (1) to counter. Thus, the code
sequence for doing so might look something like this (in x86);
mov 0x8049a1c, %eax
add $0x1, %eax
mov %eax, 0x8049a1c
This example assumes that the variable counter is located at address
0x8049a1c. In this three-instruction sequence, the x86 mov instruction is
used first to get the memory value at the address and put it into register
eax
. Then, the add is performed, adding 1 (0x1) to the contents of the
eax
register, and finally, the contents of eax are stored back into memory
at the same address.
Let us imagine one of our two threads (Thread 1) enters this region of
code, and is thus about to increment counter by one. It loads the value
of counter (let’s say it’s 50 to begin with) into its register eax. Thus,
eax=50
for Thread 1. Then it adds one to the register; thus eax=51.
Now, something unfortunate happens: a timer interrupt goes off; thus,
the OS saves the state of the currently running thread (its PC, its registers
including eax, etc.) to the thread’s TCB.
Now something worse happens: Thread 2 is chosen to run, and it en-
ters this same piece of code. It also executes the first instruction, getting
the value of counter and putting it into its eax (remember: each thread
when running has its own private registers; the registers are virtualized
by the context-switch code that saves and restores them). The value of
c
2014, A
RPACI
-D
USSEAU
T
HREE
E
ASY
P
IECES
270
C
ONCURRENCY
: A
N
I
NTRODUCTION
(after instruction)
Do'stlaringiz bilan baham: | 
