Sharing
다수의 스레드가 변수 x의 인스턴스를 참조하는 경우, x는 공유된다(Shared)고 표현한다. (필요충분조건)
Mappinng Variable Instances to Memory
| Type | Definition | Instance |
|---|
| 전역 변수 (Global variable) | 함수 외부에서 선언된 변수 | 가상 메모리에 존재 |
| 지역 변수 (Local variable) | 함수 내부에서 static 속성 없이 선언된 변수 | 각 스레드의 스택에 존재 |
| 지역 정적 변수 (Local static variable) | 함수 내부에서 static 속성으로 선언된 변수 | 가상 메모리에 존재 |
Shared Variable Analysis
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| char **ptr; /* Global variable */
void *thread(void *vargp) {
long myid = (long)vargp;
static long cnt = 0;
printf("[%ld]: %s (cnt=%ld)\n", myid, ptr[myid], ++cnt);
return NULL;
}
int main(int argc, char *argv[]) {
pthread_t tid;
char *msgs[N] = {
"Hello from foo",
"Hello from bar"
};
ptr = msgs;
for (long i = 0; i < N; i++)
Pthread_create(&tid, NULL, thread, (void *)i);
Pthread_exit(NULL);
return 0;
}
|
| Variable instance | Referenced by (thread) | Shared |
|---|
ptr | main, peer 0, peer 1 | O |
cnt | peer 0, peer 1 | O |
i (main) | main | X |
msgs (main) | main, peer 0, peer 1 | O |
myid (peer 0) | peer 0 | X |
myid (peer 1) | peer 1 | X |
Improper Synchronization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| volatile long cnt = 0; /* Global shared variable */
void *thread(void *vargp) {
long niters = *((long *)vargp);
for (long i = 0; i < niters; i++)
cnt++;
return NULL;
}
int main(int argc, char *argv[]) {
long niters;
pthread_t tid1, tid2;
if (argc != 2) {
printf("Usage: %s <niters>\n", argv[0]);
return 2;
}
niters = atoi(argv[1]);
/* Create threads and wait for them to finish */
Pthread_create(&tid1, NULL, thread, &niters);
Pthread_create(&tid2, NULL, thread, &niters);
Pthread_join(tid1, NULL);
Pthread_join(tid2, NULL);
/* Check result */
if (cnt == niters * 2)
printf("OK cnt=%ld\n", cnt);
else
printf("BOOM! cnt=%ld\n", cnt);
return 0;
}
|
이 프로그램에 인자로 10,000을 주면 20,000이 나와야 하지만, 때때로 이상한 숫자가 나오는 버그가 존재한다.
1
2
3
4
| $ ./a.out 10000
OK cnt=20000
$ ./a.out 10000
BOOM! cnt=14290
|
Assembly Code for Counter Loop
1
2
| for (long i = 0; i < niters; i++)
cnt++;
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| ; H_i (Head)
movq (%rdi), %rcx
testq %rcx, %rcx
jle .L2
movl $0, %eax
.L3:
movq cnt(%rip), %rdx ; L_i (Load cnt)
addq $1, %rdx ; U_i (Update cnt)
movq %rdx, cnt(%rip) ; S_i (Store cnt)
; T_i (Tail)
addq $1, %rax
cmpq %rcx, %rax
jne .L3
|
Concurrent Execution
명령어가 실행되는 순서(스케줄링)에 따라 결과가 달라질 수 있다. (경쟁 상태)
OK
| $\mathrm{instr}_i$ | $\mathrm{\%rdx}_1$ | $\mathrm{\%rdx}_2$ | cnt | Critical section |
|---|
| $H_1$ | | - | 0 | |
| $L_1$ | 0 | - | 0 | Thread 1 |
| $U_1$ | 1 | - | 0 | Thread 1 |
| $S_1$ | 1 | - | 1 | Thread 1 |
| $H_2$ | - | | 1 | |
| $L_2$ | - | 1 | 1 | Thread 2 |
| $U_2$ | - | 2 | 1 | Thread 2 |
| $S_2$ | - | 2 | 2 | Thread 2 |
| $T_2$ | - | 2 | 2 | |
| $T_1$ | 1 | - | 2 | |
BOOM!
공유 변수 cnt를 조작하는 명령어 $L_i$, $U_i$, $S_i$는 cnt에 대한 임계 구역(Critical section)을 형성한다. 이러한 임계 구역에 여러 스레드가 동시에 접근하는 경우, 문제가 발생한다.
| $\mathrm{instr}_i$ | $\mathrm{\%rdx}_1$ | $\mathrm{\%rdx}_2$ | cnt | Critical section |
|---|
| $H_1$ | | - | 0 | |
| $L_1$ | 0 | - | 0 | Thread 1 |
| $U_1$ | 1 | - | 0 | Thread 1 |
| $H_2$ | - | | 0 | |
| $L_2$ | - | 0 | 0 | Thread 2 |
| $S_1$ | 1 | - | 1 | Thread 1 |
| $T_1$ | 1 | - | 1 | |
| $U_2$ | - | 1 | 1 | Thread 2 |
| $S_2$ | - | 1 | 1 | Thread 2 |
| $T_2$ | - | 1 | 1 | |
| $\mathrm{instr}_i$ | $\mathrm{\%rdx}_1$ | $\mathrm{\%rdx}_2$ | cnt | Critical section |
|---|
| $H_1$ | | - | 0 | |
| $L_1$ | 0 | - | 0 | Thread 1 |
| $H_2$ | - | | 0 | |
| $L_2$ | - | 0 | 0 | Thread 2 |
| $U_2$ | - | 1 | 0 | Thread 2 |
| $S_2$ | - | 1 | 1 | Thread 2 |
| $U_1$ | 1 | - | 1 | Thread 1 |
| $S_1$ | 1 | - | 1 | Thread 1 |
| $T_1$ | 1 | - | 1 | |
| $T_2$ | - | 1 | 1 | |
Critical Sections and Unsafe Regions
Progress graph를 통해 여러 가지 경우를 한눈에 파악할 수 있다.
- 그래프에서 각 스레드의 임계 구역이 교차하는 영역은 안전하지 않은 영역(Unsafe region)이다.
- 안전한 궤적(Trajectory)은 안전하지 않은 영역을 지나지 않는다.
Mutual Exclusion
항상 안전한 궤적으로 스케줄링되도록 하기 위해, 임계 구역에 대한 상호 배타적 접근을 보장(동기화)해야 한다.
Semaphores
세마포어(Semaphore)는 동기화에 사용되는 전역 변수로, 0 이상의 정수 값을 가진다. P와 V 연산으로 값을 조작할 수 있다.
1
2
3
4
5
6
7
8
9
10
| /* Pseudo-code */
P(s) {
while (s == 0) /* Atomic */
wait();
s--; /* Atomic */
}
V(s) {
s++; /* Atomic */
}
|
- 커널은
P 연산에서 차단된 스레드의 큐를 유지한다. V 연산은 s를 1만큼 증가시킨 뒤, P 연산에서 차단된 스레드가 있다면 그 중 임의의 하나를 차단 해제한다.
C Semaphore Operations
1
2
3
4
5
| #include <semaphore.h>
int sem_init(sem_t *sem, int pshared, unsigned int value);
int sem_wait(sem_t *sem); /* P(s) */
int sem_post(sem_t *sem); /* V(s) */
|
Proper Synchronization
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| /* Global shared variables */
volatile long cnt = 0;
sem_t mutex;
void *thread(void *vargp) {
long niters = *((int *)vargp);
for (long i = 0; i < niters; i++) {
Sem_wait(&mutex);
cnt++;
Sem_post(&mutex);
}
return NULL;
}
int main(int argc, char *argv[]) {
long niters;
pthread_t tid1, tid2;
if (argc != 2) {
printf("Usage: %s <niters>\n", argv[0]);
return 2;
}
niters = atoi(argv[1]);
/* Create threads and wait for them to finish */
Sem_init(&mutex, 0, 1);
Pthread_create(&tid1, NULL, thread, &niters);
Pthread_create(&tid2, NULL, thread, &niters);
Pthread_join(tid1, NULL);
Pthread_join(tid2, NULL);
/* Check result */
if (cnt == niters * 2)
printf("OK cnt=%ld\n", cnt);
else
printf("BOOM! cnt=%ld\n", cnt);
return 0;
}
|
- 임계 구역을 세마포어(뮤텍스)로 보호하여, 한 번에 하나의 스레드만 쓰기 작업을 수행할 수 있도록 한다.
- 세마포어 값을 조작하는 함수는 시스템 콜이므로, 큰 오버헤드가 발생한다.
Progress graph를 통해 세마포어의 원리를 파악할 수 있다.
References