왜 동기화가 중요해졌을까?
개념을 잡기 전에..
- 동기화의 본질: 프로세스가 공유 자원에 접근할 때 충돌이나 불일치를 방지하는 기술
- 동기화가 없으면 발생할 수 있는 문제
- race condition
- deadlock
- consistency voilation(일관성 붕괴)
결론적으로 시스템 전체의 신뢰와 안정성을 보장하기 위한 방법이다.
- 왜 동기화가 중요해졌을까?
- 멀티코어 프로세서의 보편화: 단일 CPU에는 이슈가 적었다. 하지만 요즘은 병렬 실행이 기본이 되었다.
- 분산 시스템/ 클라우드 환경
- 실시간 서비스의 확대 및 밀리초 단위 정확성을 요구하는 서비스들이 많아졌다.(동기화가 미흡하면 치명적 사고). SNS의 좋아요 수 카운트도 동기화가 없다면 수치가 잘못 표시될 것이다.
About
저자: 앨런 B. 다우니 (Allen B. Downey)
버전 2.2.1
The Little Book of Semaphores 다운로드 링크
- 책에서 필요한 부분을 정리. 추가 코드는 GPT에게 예제를 요청했다.
- 소개: 동기화 개념과 고전적 문제(생산자-소비자, 독자-작가 등)를 퍼즐 형식으로 풀어내는 실습 중심 교재다.(실제 저자가 대학에서 운영체제 수업자료로 활용함)
Python 기반의 의사코드와 실제 실행 가능한 예제, 다양한 패턴을 통해 세마포어 활용법을 익히도록 구성된 무료 오픈 라이선스 책.
1장: 소개
1.1 동기화 (Synchronization)
- 동기화: 두 가지 일이 동시에 일어나도록 만드는 것
- 동기화 제약조건(synchronization constraints)
- 직렬화(Serialization): 이벤트 A는 반드시 이벤트 B보다 먼저 발생해야 한다.
- 상호 배제(Mutual exclusion): 이벤트 A와 B는 동시에 발생해서는 안 된다.
- 현실 세계에서는 시계를 사용하여 동기화 제약을 확인하고 강제할 수 있다.
- 컴퓨터 시스템에서는 시계없이 동기화 제약을 만족시켜야 할 때가 많다. 공통 시계가 없거나 이벤트가 발생한 정확한 시점을 알 수 없기 때문
1.2 실행 모델 (Execution model)
소프트웨어 동기화를 이해하려면 컴퓨터 프로그램이 어떻게 실행되는지에 대해 이해해야 한다.
- 현실에서 실행 모델이 복잡한 이유
1) 병렬 처리 시스템: 하나의 컴퓨터에 여러 개의 프로세서가 있어 동시에 실행된다.(이 경우 한 프로세서에서 실행된 명령어가 다른 프로세서의 명령어보다 먼저 실행되었는지를 알기 어렵다)
2) 멀티스레드 시스템: 하나의 프로세서에서 여러 스레드가 실행된다. 스레드는 순차적인 명령어의 집합이며, 운영체제의 스케줄러가 어떤 스레드를 실행할지 결정한다. 프로그래머는 언제 어떤 스레드가 실행될지 제어할 수 없다.
Puzzle1
내일 점심을 내가 bob보다 먼저 먹도록 보장할 수 있는 방법이 있을까?
당신과 친구 밥(Bob)이 각각 다른 도시에 살고 있다.
어느 날 저녁 “오늘 점심을 누가 먼저 먹었을까?”가 궁금해졌다고 생각해보자. 어떻게 확인할 수 있을까?
- 현실: 전화나 메시지로 점심을 몇 시에 먹을 것인지 물어보면 된다.
- 이것이 직렬화(serialization)
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#include <unistd.h>
sem_t done_eating; // Alice가 점심을 끝냈음을 알리는 세마포어
void *alice(void* arg)
{
printf("Alice: 점심 시작!\n");
sleep(2); // 점심 먹는 중
printf("Alice: 점심 다 먹었어. 이제 Bob 시작해도 돼!\n");
sem_post(&done_eating); // Alice가 signal() 보냄
return NULL;
}
void *bob(void* arg)
{
printf("Bob: Alice 신호 기다리는 중...\n");
sem_wait(&done_eating); // Bob은 wait() -> Alice의 signal() 전까지 대기
printf("Bob: 이제 점심 시작!\n");
return NULL;
}
int main()
{
pthread_t t1, t2;
sem_init(&done_eating, 0, 0); // 초기값 0 (Alice가 먼저 signal 해야 Bob이 실행 가능)
pthread_create(&t1, NULL, alice, NULL);
pthread_create(&t2, NULL, bob, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
sem_destroy(&done_eating);
return 0;
}
클럭이 비교적 정확하더라도 정밀도에는 한계가 있다. 대부분의 시스템에서는 이벤트가 발생한 시점을 기록하지 않는다. 너무 많은 일이 너무 빠르게 일어나기 때문에 모든 시점을 기록하는 것은 불가능하다. (로그가 너무 많아짐. 그래서 중요한 사건만 기록한다. context switch, I/O 완료, 락 획득 등 중요한 시스템 이벤트만)
1.5 공유 변수 (Shared variables)
1.5.1 동시 쓰기 (Concurrent writes): 둘 이상의 스레드가 동시에 값을 씀
threadA
x = 5 #(a1)
print(x) #(a2)threadB
x = 7 #(b1)puzzle2
출력이 7인데, 최종값이 5인 경우가 가능할까?
| 순서 | output | value |
|---|---|---|
| 쓰레드 A만 | 5 | 5 |
| a1 -> b1 -> a2 | 7 | 7 |
| a1 -> a2 -> b1 | 5 | 7 |
A: 가능하지 않다.
세마포어를 이용해 출력값 = 최종값이 일치하도록 보장해보자.
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
sem_t done_write; // Thread B가 x=7을 완료했음을 알리는 세마포어
int x;
void *threadA(void* arg)
{
sem_wait(&done_write); // B가 쓰기 끝낼 때까지 기다림
printf("Thread A: x = %d\n", x); // 출력은 항상 최종 값
return NULL;
}
void *threadB(void* arg)
{
x = 7;
sem_post(&done_write); // B가 쓴 뒤 A에게 신호
return NULL;
}
int main()
{
pthread_t t1, t2;
sem_init(&done_write, 0, 0);
pthread_create(&t2, NULL, threadB, NULL); // B 먼저 실행 가능
pthread_create(&t1, NULL, threadA, NULL);
pthread_join(t1, NULL);
pthread_join(t2, NULL);
sem_destroy(&done_write);
return 0;
}
1.5.2 동시 업데이트 (Concurrent updates): 둘 이상의 스레드가 값을 읽고 계산 후 다시 씀
1) 업데이트: 현재 값을 읽고, 그 값을 기반으로 새 값을 계산하여 저장하는 것
2) 두 개의 스레드가 동시에 공유 변수 count를 업데이트 하는 예
프로그래머의 의도는 2를 원하지만, 최종값이 1이 된다.
threadA
count = count + 1threadB
count = count + 13) 어떻게 해결?
모든 업데이트 및 쓰기 연산은 atomic하지 않다고 가정하고, 동기화 제약 조건을 명시적으로 적용해야 한다.
- mutex(공유 변수에 한 번에 하나의 스레드만 접근하도록 보장) 적용하기
puzzle3
100개의 스레드가 다음 코드를 동시에 실행한다고 가정한다.
race condition(경쟁 조건)
for i in range(100):
temp = count
count = temp + 1
// race condition
// 10000 보장 x, 동기화가 없어서 실행마다 결과가 달라진다.
#include <stdio.h>
#include <pthread.h>
#define THREADS 100
int count = 0;
void *worker(void *arg)
{
int i;
int temp;
(void)arg;
for (i = 0; i < 100; i++)
{
temp = count;
count = temp + 1;
}
return (NULL);
}
int main(void)
{
pthread_t t[THREADS];
int i;
for (i = 0; i < THREADS; i++)
pthread_create(&t[i], NULL, worker, NULL);
for (i = 0; i < THREADS; i++)
pthread_join(t[i], NULL);
printf("Final count = %d\n", count);
return (0);
}
질문 1. 모든 스레드가 종료된 후, count 의 최댓값은 얼마일 수 있을까?
경쟁 조건이 없다면, 10000.
질문 2. 최솟값은 얼마일까?
100개의 스레드, 100번의 반복 -> 10000번의 연산이지만, 100번 반복(loop) 모두 동시 충돌이라면 100개가 가능하다.
추가 질문. 그렇다면 이 race condition을 해결하는 방법을 알아보자
1) 원자적(atomic)
참고 출처: gcc.gnu.org 7.9.2 Legacy __sync Built-in Functions for Atomic Memory Access
- CPU의 원자적 명령어를 직접 활용하는 빌트인 함수다.
- CPU 수준에서 한 번에 실행되므로 다른 스레드가 끼어들 수 없다.
- (참고) 단순 카운트 외에도 공유 자원의 동시점유/해제를 해야 하는 철학자 문제에는 적용하기 어렵다.
#include <stdio.h>
#include <pthread.h>
#define THREADS 100
#define LOOP 100
int count = 0;
void *worker(void *arg)
{
for (int i = 0; i < 100; i++)
{
__sync_fetch_and_add(&count, 1);
}
return NULL;
}
int main() {
pthread_t threads[THREADS];
for (int i = 0; i < THREADS; i++)
pthread_create(&threads[i], NULL, worker, NULL);
for (int i = 0; i < THREADS; i++)
pthread_join(threads[i], NULL);
printf("Final count = %d\n", count);
return 0;
}2) mutex -> 자원 보호에 특화(오직 1개의 스레드만 보호 구역에 들어올 수 있다. lock. 열쇠는 하나뿐이다!)
#include <stdio.h>
#include <pthread.h>
#define THREADS 100
int count = 0;
pthread_mutex_t lock;
void *worker(void *arg)
{
int i;
int temp;
(void)arg;
for (i = 0; i < 100; i++)
{
pthread_mutex_lock(&lock); //임계 구역 보호
temp = count;
count = temp + 1;
pthread_mutex_unlock(&lock);
}
return (NULL);
}
int main(void)
{
pthread_t t[THREADS];
int i;
pthread_mutex_init(&lock, NULL);
for (i = 0; i < THREADS; i++)
pthread_create(&t[i], NULL, worker, NULL);
for (i = 0; i < THREADS; i++)
pthread_join(t[i], NULL);
pthread_mutex_destroy(&lock);
printf("Final count = %d\n", count);
return (0);
}3) semaphore -> 위 뮤텍스 코드와 동일한 동작을 하는 코드.
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
#define THREADS 100
int count = 0;
sem_t lock;
void *worker(void *arg)
{
int i;
int temp;
(void)arg;
for (i = 0; i < 100; i++)
{
sem_wait(&lock);
temp = count;
count = temp + 1;
sem_post(&lock);
}
return (NULL);
}
int main(void)
{
pthread_t t[THREADS];
int i;
sem_init(&lock, 0, 1); // 세마포어 초기화 여기서 1
for (i = 0; i < THREADS; i++)
pthread_create(&t[i], NULL, worker, NULL);
for (i = 0; i < THREADS; i++)
pthread_join(t[i], NULL);
sem_destroy(&lock);
printf("Final count = %d\n", count);
return (0);
}
- sem_init(&lock, 0, 1):
여기서 1은 동시에 들어올 수 있는 스레드의 수다. 이를 N으로 바꾸면 동시에 N개의 스레드가 임계구역에 들어올 수 있다.- 초기값1 = 화장실 칸이 1개인 공중 화장실(뮤텍스와 동일함)
- 초기값N = 화장실 칸이 N개인 공중화장실-> 이렇게 하는 경우 뮤텍스보다 더 범용적으로 활용 가능
1.5.3 메시지를 이용한 상호 배제 (Mutual exclusion with messages): 대부분은 동기화 문제 x
(참고) race condition tool
Valrind(Helgrind/DRD)
helgrind
valgrind --tool=helgrind ./a.outDRD(Data Race Detector)
valgrind --tool=drd ./a.out- 대충 어떻게 보나
==1686868== drd, a thread error detector
==1686868== Copyright (C) 2006-2020, and GNU GPL'd, by Bart Van Assche.
==1686868== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==1686868== Command: ./test
==1686868==
==1686868== Thread 3:
==1686868== Conflicting load by thread 3 at 0x00404044 size 4
==1686868== at 0x401169: worker (in /home/borlee/assignment/tlpi/threads/borlee/test)
==1686868== by 0x485437A: ??? (in /usr/libexec/valgrind/vgpreload_drd-amd64-linux.so)
==1686868== by 0x4929AC2: start_thread (pthread_create.c:442)
==1686868== by 0x49BAA03: clone (clone.S:100)
==1686868== Allocation context: BSS section of /home/borlee/assignment/tlpi/threads/borlee/test
==1686868== Other segment start (thread 2)
==1686868== (thread finished, call stack no longer available)
==1686868== Other segment end (thread 2)
==1686868== (thread finished, call stack no longer available)
==1686868==
==1686868== Conflicting store by thread 3 at 0x00404044 size 4
==1686868== at 0x401179: worker (in /home/borlee/assignment/tlpi/threads/borlee/test)
==1686868== by 0x485437A: ??? (in /usr/libexec/valgrind/vgpreload_drd-amd64-linux.so)
==1686868== by 0x4929AC2: start_thread (pthread_create.c:442)
==1686868== by 0x49BAA03: clone (clone.S:100)
==1686868== Allocation context: BSS section of /home/borlee/assignment/tlpi/threads/borlee/test
==1686868== Other segment start (thread 2)
==1686868== (thread finished, call stack no longer available)
==1686868== Other segment end (thread 2)
==1686868== (thread finished, call stack no longer available)
==1686868==
Final count = 10000
==1686868==
==1686868== ERROR SUMMARY: 19800 errors from 2 contexts (suppressed: 10 from 6)
==1686868==
==1686868== 9900 errors in context 1 of 2:
==1686868== Conflicting store by thread 3 at 0x00404044 size 4
==1686868== at 0x401179: worker (in /home/borlee/assignment/tlpi/threads/borlee/test)
==1686868== by 0x485437A: ??? (in /usr/libexec/valgrind/vgpreload_drd-amd64-linux.so)
==1686868== by 0x4929AC2: start_thread (pthread_create.c:442)
==1686868== by 0x49BAA03: clone (clone.S:100)
==1686868== Allocation context: BSS section of /home/borlee/assignment/tlpi/threads/borlee/test
==1686868==
==1686868==
==1686868== 9900 errors in context 2 of 2:
==1686868== Conflicting load by thread 3 at 0x00404044 size 4
==1686868== at 0x401169: worker (in /home/borlee/assignment/tlpi/threads/borlee/test)
==1686868== by 0x485437A: ??? (in /usr/libexec/valgrind/vgpreload_drd-amd64-linux.so)
==1686868== by 0x4929AC2: start_thread (pthread_create.c:442)
==1686868== by 0x49BAA03: clone (clone.S:100)
==1686868== Allocation context: BSS section of /home/borlee/assignment/tlpi/threads/borlee/test
==1686868==
--1686868--
--1686868-- used_suppression: 10 drd-ld /usr/libexec/valgrind/default.supp:566
==1686868==
==1686868== ERROR SUMMARY: 19800 errors from 2 contexts (suppressed: 10 from 6)1) 핵심 문제
Conflicting load by thread 3 at 0x00404044 size 4
Conflicting store by thread 3 at 0x00404044 size 4- 0x00404044주소(전역변수, BSS 영역에 있음)에 대해 여러 스레드가 동시에 접근하고 있다
- datat race가 발생했어요!
2) 어디서 발생했는가
- 0x401169, 0x401179 전역 변수를 읽고 쓰는 과정
- thread2 와 thread3이 동일한 메모리를 동시에 접근한 흔적(실행할 때마다 스레드 번호는 달라질 수 있다=비결정성. 숫자는 일종의 예시상황이므로 번호에 집중하지 말자. 동기화 처리가 필요하다는 게 핵심)
ThreadSanitizer
- 컴파일 옵션 중에
cc -fsanitize=thread -g -pthread 소스코드명.c -o 실행파일
gdb ./실행파일참고 영상
위 정리와는 무관한 그냥 참고 영상이다.
[10분 테코톡] 🎲 와일더의 Mutex vs Semaphore
뮤텍스
- 여러 스레드를 사용하는 환경에서 자원에 대한 접근을 강제하기 위한 동기화 매커니즘이다.
- boolean 타입의 lock변수를 사용한다
- 공유자원을 사용 중인 스레드가 있을 때, 다른 스레드가 공유 자원에 접근한다면 blocking 후 대기 큐로 보낸다.
- lock을 건 스레드만 lock을 해제할 수 있다.
스핀락
- 기본적으로 뮤텍스와 유사하다
- busy-waiting하며 대기 큐를 갖지 않는다
- Mutex-nonblocking 모델로 볼 수 있다.
세마포어
- 세마포어 변수를 통해 wait, signal을 관리한다. 세마포어 변수는 0 이상의 정수형 변수를 갖는다.
- 계수 세마포어로 사용할 수 있으며, 접근 가능한 공유 자원의 수가 1개일 때는 이진 세마포어로 뮤텍스처럼 사용할 수 있다.
thread 디버깅하기
#include <stdio.h>
#include <pthread.h>
#define THREADS 100
#define LOOP 100
int count = 0;
void *worker(void *arg)
{
for (int i = 0; i < 100; i++)
{
__sync_fetch_and_add(&count, 1);
}
return NULL;
}
int main()
{
pthread_t threads[THREADS];
for (int i = 0; i < THREADS; i++)
pthread_create(&threads[i], NULL, worker, NULL);
for (int i = 0; i < THREADS; i++)
pthread_join(threads[i], NULL);
printf("Final count = %d\n", count);
return 0;
}위 코드를 실행하고
gdb run을 실행
아래 내용은 이 중간의 "info th"의 결과다
(gdb) info th
Id Target Id Frame
1 Thread 0x7ffff7fa2740 (LWP 1269368) "test" clone3 ()
at ../sysdeps/unix/sysv/linux/x86_64/clone3.S:62
* 2 Thread 0x7ffff7bff640 (LWP 1269370) "test" worker (arg=0x0) at test.c:20
3 Thread 0x7ffff73fe640 (LWP 1269384) "test" worker (arg=0x0) at test.c:18
4 Thread 0x7ffff6bfd640 (LWP 1269385) "test" worker (arg=0x0) at test.c:18
5 Thread 0x7ffff63fc640 (LWP 1269386) "test" clone3 ()- Thread 0x7ffff7fa2740: 스레드 핸들(포인터 주소). pthread_t가 실제 메모리에 매핑된 주소
- LWP 1269368 : Light Weight Process ID. OS 커널 레벨에서 관리하는 스레드의 ID.
- 해당 코드는 스레드를 100개 만드는 것이므로 light weight process id가 100개 생성될 것이다.
strace -c -f ./실행파일
strace: Process 1273835 attached
strace: Process 1273836 attached
strace: Process 1273837 attached
..
..
..
strace: Process 1273932 attached
strace: Process 1273933 attached
strace: Process 1273934 attached
Final count = 10000\n% time seconds usecs/call calls errors syscall
------ ----------- ----------- --------- --------- ----------------
28.69 0.008284 82 100 clone3
26.29 0.007590 18 401 rt_sigprocmask
9.90 0.002857 28 100 madvise
7.75 0.002238 21 104 mprotect
7.42 0.002141 19 108 mmap
6.85 0.001978 19 101 rseq
6.12 0.001767 17 101 set_robust_list
4.60 0.001327 13 97 munmap
1.76 0.000509 509 1 execve
0.11 0.000032 10 3 brk
0.08 0.000024 12 2 openat
0.08 0.000023 7 3 newfstatat
0.08 0.000022 5 4 pread64
0.05 0.000013 13 1 write
0.04 0.000012 6 2 close
0.04 0.000011 11 1 1 access
0.04 0.000011 5 2 1 arch_prctl
0.03 0.000008 8 1 read
0.03 0.000008 8 1 getrandom
0.02 0.000007 7 1 prlimit64
0.02 0.000006 6 1 rt_sigaction
0.02 0.000005 5 1 set_tid_address
------ ----------- ----------- --------- --------- --------- 여기서 특히 clone3의 호출 횟수로 스레드가 몇 개 생성되었는지 가늠할 수 있다.
- futex 없음
- 코드 상의 "__sync_fetch_and_add()" 때문. GCC 빌트인 원자적 연산. 커널에 내려가지 않고 CPU 명령어만으로 처리. 그래서 이 futex시스템 콜이 발생하지 않는다.
[참고]
- futex(Fast Userspace muTEX): 사용자 공간에서 빠르게 동작하는 잠금 메커니즘
- 동작 원리
1) 대부분의 경우(잠금 경쟁이 없는 경우) → 사용자 공간에서 바로 처리 → 커널에 안 내려감 → 빠름.
2) 경쟁이 발생해서 기다려야 할 때만 → 커널의 futex 시스템콜을 호출 → 커널이 스레드를 sleep 상태로 블록.
빠른 경합 없는 경우에는 성능 손해가 거의 없고, 경합 발생 시에는 커널이 개입해 스케줄링을 담당합니다.
- 🤔 철학자 문제를 풀 때 strace에서 futex를 살펴보면 좋을 것 같다.
수학을 사랑하는 애독자📚 Stop dreaming. Start living. - 'The Secret Life of Walter Mitty'