12.4 쓰레드 프로그램에서 공유 변수
- 어떤 변수 x는 다중 쓰레드들이 x의 어떤 인스턴스instance를 참조할 때만 공유된다고 정의한다.
- 다음 질문들에 대답해야 한다.
- 쓰레드를 위한 메모리 모델은?
- 변수들의 인스턴스는 어떻게 메모리에 매핑되나?
- 얼마나 많은 쓰레드가 각 인스턴스를 참조하나?
12.4.1 쓰레드 메모리 모델
- 컨셉적 모델
- 다중 쓰레드는 단일 프로세스의 컨텍스트에서 실행된다.
- 각 쓰레드는 분리된 쓰레드 컨텍스트를 가진다. (TID, 스택, 스택 포인터, PC 등)
- 모든 쓰레드들은 나머지 프로세스 컨텍스트를 공유한다. (코드, 데이터, 힙, 공유 라이브러리 세그먼트 등)
- 동작적인 측면에서, 이 모델은 엄격하게 수행되지 않는다.
- 레지스터 값들은 확실히 분리되고 보호되지만...
- 어떤 쓰레드는 다른 쓰레드의 스택에 읽고 쓸 수 있다.
char **ptr; /* global var */
int main()
{
long i;
pthread_t tid;
char *msgs[2] = {
"Hello from foo",
"Hello from bar"
};
ptr = msgs;
for (i = 0; i < 2; i++)
Pthread_create(&tid,
NULL,
thread,
(void *)i);
Pthread_exit(NULL);
}
void *thread(void *vargp)
{
long myid = (long)vargp;
static int cnt = 0;
printf("[%ld]: %s (cnt=%d)\n",
myid, ptr[myid], ++cnt);
return NULL;
}12.4.2 변수들을 메모리로 매핑하기
- 전역 변수
- 정의: 함수 밖에서 선언된 변수
- 가상 메모리는 어떤 전역 변수의 정확히 하나의 인스턴스를 포함한다.
- 지역 변수
- 정의: static 속성 없이 함수 안에서 선언된 변수
- 각 쓰레드 스택은 각 지역 변수의 하나의 인스턴스를 포함한다.
- 지역 정적 변수
- 정의: static 속성을 가지고 함수 안에서 선언된 변수
- 가상 메모리는 어떤 지역 정적 변수의 정확히 하나의 인스턴스를 포함한다.
char **ptr; /* global var */
int main()
{
long i;
pthread_t tid;
char *msgs[2] = {
"Hello from foo",
"Hello from bar"
};
ptr = msgs;
for (i = 0; i < 2; i++)
Pthread_create(&tid,
NULL,
thread,
(void *)i);
Pthread_exit(NULL);
}
void *thread(void *vargp)
{
long myid = (long)vargp;
static int cnt = 0;
printf("[%ld]: %s (cnt=%d)\n",
myid, ptr[myid], ++cnt);
return NULL;
}12.4.3 공유 변수
위 코드에서 공유되는 변수들은 다음과 같다.
| Variable instance | Referenced by main thread? |
Referenced by peer thread 0? |
Referenced by peer thread 1? |
| ptr | ⭕ | ⭕ | ⭕ |
| cnt | × | ⭕ | ⭕ |
| i.m | ⭕ | × | × |
| msgs.m | ⭕ | ⭕ | ⭕ |
| myid.p0 | × | ⭕ | × |
| myid.p1 | × | × | ⭕ |
- ptr, cnt, msgs는 공유변수다.
- i와 myid는 공유변수가 아니다.
12.5 세마포어로 쓰레드 동기화하기
👎 잘못된 동기화 예제
// badcnt.c
/* Global shared variable */
volatile long cnt = 0; /* Counter */
int main(int argc, char **argv)
{
long niters;
pthread_t tid1, tid2;
niters = atoi(argv[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 != (2 * niters))
printf("BOOM! cnt=%ld\n", cnt);
else
printf("OK cnt=%ld\n", cnt);
exit(0);
}
/* Thread routine */
void *thread(void *vargp)
{
long i, niters = *((long *)vargp);
for (i = 0; i < niters; i++)
cnt++;
return NULL;
}linux> ./badcnt 10000
OK cnt=20000
linux> ./badcnt 10000
BOOM! cnt=13051
linux>위 코드에서 카운터 루프가 문제를 일으킬 수 있다.
# Hᵢ: Head
movq (%rdi), %rcx
testq %rcx,%rcx
jle .L2
movl $0, %eax
#-----------------------------
.L3:
movq cnt(%rip),%rdx # Lᵢ: Load cnt
addq $1, %rdx # Uᵢ: Update cnt
movq %rdx, cnt(%rip) # Sᵢ: Store cnt
#-----------------------------
# Tᵢ: Tail
addq $1, %rax
cmpq %rcx, %rax
jne .L3
.L2:- badcnt.c의 두 피어 쓰레드가 동시에 단일 프로세서에서 돌아갈 때, 머신 인스트럭션들은 어떤 순서로 하나씩 완료된다.
- 따라서 각각의 동시성 실행은 일종의 두 쓰레드 내 인스트럭션의 순서를 정의한다.
- 불행하게도 이 연산의 일부는 정확한 결과를 만들지만 나머지는 그렇지 않다.
- 일반적으로 OS가 쓰레드를 위해서 정확한 순서를 선택하게 될 지 여부를 예측할 수 있는 방법은 없다.
- 이러한 정확성/부정확성을 가지는 인스트럭션 순서를 진행 그래프progress graph를 사용해 분석할 수 있다.
12.5.1 진행 그래프
12.5.2 세마포어
- 쓰레드들이 위험 궤적을 가지지 않게 하려면 쓰레드의 실행을 동기화synchronize해야 한다.
- 즉, 각 크리티컬 섹션마다 상호 배타적인 접근mutually exclusive access를 보장해야 한다.
- 세마포어Semaphore: 음이 아닌 전역 정수형 동기화 변수로, P와 V 연산을 통해 조작된다.
- P(s)
- s가 0이 아니면, s를 1 감소시키고 즉시 리턴한다. (테스트와 감소 연산은 개별적(독립적)으로 일어난다.)
- s가 0이라면, s가 0이 아닌 값이 될 때까지 쓰레드를 중지시키고 V 연산을 통해 쓰레드를 다시 시작한다.
- 재시작한 이후에 P 연산은 s를 감소시키고 함호출자에게 컨트롤을 반환한다.
- V(s)
- s를 1 증가시킨다. (증가 연산은 개별적으로 일어난다.)
- s가 0이 아닌 갑싱 되기를 기다리면서 P 연산에서 멈춰 있는 쓰레드가 있으면, 그 중에서 정확히 하나를 재시작하고, s를 감소시켜서 P 연산을 완료한다.
- 세마포어 불변성Semaphore invariant (s ≥ 0)
- P와 V의 정의는 돌고 있는 프로그램이 적절히 초기화된 세마포어가 음수 값을 가진 상태로 절대 들어갈 수 없도록 보장한다.
🔹 C 세마포어 연산
- Pthreads 함수
#include <semaphore.h>
int sem_init(sem_t *s, 0, unsigned int val);} /* s = val */
int sem_wait(sem_t *s); /* P(s) */
int sem_post(sem_t *s); /* V(s) */- CSAPP 래퍼 함수
#include "csapp.h"
void P(sem_t *s); /* Wrapper function for sem_wait */
void V(sem_t *s); /* Wrapper function for sem_post */12.5.3 상호 배제를 위해 세마포어 사용하기
- 기본 아이디어
- 특별한 이진 세마포어인 뮤텍스mutex(1로 초기화됨)를 각 공유 변수 (또는 공유 변수의 관련된 집합)와 연관짓는다.
- 대응하는 크리티컬 섹션을 P(mutex)와 V(mutex) 연산으로 둘러싼다.
- 적절한 동기화 예제 (goodcnt.c)
// Define and initialize a mutex for the shared variable cnt
volatile long cnt = 0; /* Counter */
sem_t mutex; /* Semaphore that protects cnt */
Sem_init(&mutex, 0, 1); /* mutex = 1 */
// Surround critical section with P and V:
for (i = 0; i < niters; i++) {
P(&mutex);
cnt++;
V(&mutex);
}
🔹 개발자들은 변수가 쓰레드들에 의해 어떻게 공유되는지에 대한 명확한 모델을 필요로 한다.
🔹 다중 쓰레드에 의해 공유되는 변수들은 상호 배제 접근을 확실히 하기 위해 보호되어야 한다.
🔹 세마포어는 상호 배제를 강요하는 근본적인 메커니즘이다.
12.5.4 세마포어를 이용한 공유 자원 스케줄링하기
- 기본 아이디어 : 쓰레드는 다른 쓰레드에게 어떤 조건이 성립되었음을 알리기 위해 세마포어 연산을 사용한다.
- 리소스 상태를 추적하고 다른 쓰레드에게 알리기 위해 카운팅 세마포어를 쓴다.
- 리소스로의 접근을 보호하기 위해 뮤텍스를 쓴다.
🔹 생산자-소비자 문제
- 공용 동기화 패턴
- 생산자는 빈 slot을 기다리고, 버퍼에 아이템을 삽입하고, 소비자에게 알린다.
- 소비자는 item을 기다리고, 버퍼에서 아이템을 제거하고, 생산자에게 알린다.
- (예) 멀티미디어 프로세싱 : 생산자는 MEGG 비디오 프레임을 만들고, 소비자가 렌더링한다.
- (예) Event-driven GUI
- 생산자가 마우스 클릭, 마우스 이동, 키보드 타자를 탐지하고 버퍼에 대응되는 이벤트를 삽입한다.
- 소지바가 버퍼에서 이벤트를 받아 디스플레이에 그려낸다.
- 하나의 뮤텍스와 2개의 카운팅 세마포어를 요구한다.
- mutex: 버퍼에 상호 배제 접근을 강요한다.
- slots: 버퍼 내의 가능한 슬롯 수를 센다.
- items: 버퍼 내의 가능한 아이템 수를 센다.
- sbuf이라고 불리는 공유 버퍼 패키지를 사용해 구현된다.
#include "csapp.h"
typedef struct {
int *buf; /* Buffer array */
int n; /* Maximum number of slots */
int front; /* buf[(front+1)%n] is first item */
int rear; /* buf[rear%n] is last item */
sem_t mutex; /* Protects accesses to buf */
sem_t slots; /* Counts available slots */
sem_t items; /* Counts available items */
} sbuf_t;
void sbuf_init(sbuf_t *sp, int n);
void sbuf_deinit(sbuf_t *sp);
void sbuf_insert(sbuf_t *sp, int item);
int sbuf_remove(sbuf_t *sp);
/* Create an empty, bounded, shared FIFO buffer with n slots */
void sbuf_init(sbuf_t *sp, int n)
{
sp->buf = Calloc(n, sizeof(int));
sp->n = n; /* Buffer holds max of n items */
sp->front = sp->rear = 0; /* Empty buffer iff front == rear */
Sem_init(&sp->mutex, 0, 1); /* Binary semaphore for locking */
Sem_init(&sp->slots, 0, n); /* Initially, buf has n empty slots */
Sem_init(&sp->items, 0, 0); /* Initially, buf has 0 items */
}
/* Clean up buffer sp */
void sbuf_deinit(sbuf_t *sp)
{
Free(sp->buf);
}
/* Insert item onto the rear of shared buffer sp */
void sbuf_insert(sbuf_t *sp, int item)
{
P(&sp->slots); /* Wait for available slot */
P(&sp->mutex); /* Lock the buffer */
sp->buf[(++sp->rear)%(sp->n)] = item; /* Insert the item */
V(&sp->mutex); /* Unlock the buffer */
V(&sp->items); /* Announce available item */
}
/* Remove and return the first item from buffer sp */
int sbuf_remove(sbuf_t *sp)
{
int item;
P(&sp->items); /* Wait for available item */
P(&sp->mutex); /* Lock the buffer */
item = sp->buf[(++sp->front)%(sp->n)]; /* Remove the item */
V(&sp->mutex); /* Unlock the buffer */
V(&sp->slots); /* Announce available slot */
return item;
}
🔹 Readers-Writers 문제
- 상호 배제 문제의 일반화
- 문제 설명
- Reader 쓰레드들은 객체를 읽기만 한다.
- Writer 쓰레드들은 객체를 수정하기만 한다.
- Writer들은 객체에 배타적으로 접근해야 한다.
- 객체에 접근하는 Reader의 수는 무제한이다.
- 온라인 항공 예약 시스템, 멀티쓰레드 캐싱 웹 프록시 등 현실의 시스템에서도 빈번하게 나타난다.
🔹 Readers-Writers의 변형
- First readers-writers 문제 (readers 선호)
- writer가 이미 객체를 쓰도록 허락을 받지 않은 한 reader는 대기할 필요가 없다.
- 대기 중인 writer 이후에 도착한 reader는 writer보다 우선순위를 가진다.
- Second readers-writers 문제 (writers 선호)
- writer가 쓸 준비가 되었으면, 가능한 바로 쓴다.
- writer 이후에 도착한 reader는 writer 역시 대기 중이더라도 반드시 대기해야 한다.
🔹 First Readers-Writers 문제의 해결책
- Readers
int readcnt; /* Initially = 0 */
sem_t mutex, w; /* Initially = 1 */
void reader(void)
{
while (1) {
P(&mutex);
readcnt++;
if (readcnt == 1) /* First in */
P(&w);
V(&mutex);
/* Critical section */
/* Reading happens */
P(&mutex);
readcnt--;
if (readcnt == 0) /* Last out */
V(&w);
V(&mutex);
}
}- Writers
void writer(void)
{
while (1) {
P(&w);
/* Critical section */
/* Writing happens */
V(&w);
}
}12.5.5 종합 설계: 사전 쓰레딩Prethreaded에 기초한 동시성 서버
sbuf_t sbuf; /* Shared buffer of connected descriptors */
int main(int argc, char **argv)
{
int i, listenfd, connfd;
socklen_t clientlen;
struct sockaddr_storage clientaddr;
pthread_t tid;
listenfd = Open_listenfd(argv[1]);
sbuf_init(&sbuf, SBUFSIZE);
for (i = 0; i < NTHREADS; i++) /* Create worker threads */
Pthread_create(&tid, NULL, thread, NULL);
while (1) {
clientlen = sizeof(struct sockaddr_storage);
connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
sbuf_insert(&sbuf, connfd); /* Insert connfd in buffer */
}
}- Worker 쓰레드 루틴
void *thread(void *vargp)
{
Pthread_detach(pthread_self());
while (1) {
int connfd = sbuf_remove(&sbuf); /* Remove connfd from buf */
echo_cnt(connfd); /* Service client */
Close(connfd);
}
}- echo_cnt 초기화 루틴
static int byte_cnt; /* Byte counter */
static sem_t mutex; /* and the mutex that protects it */
static void init_echo_cnt(void)
{
Sem_init(&mutex, 0, 1);
byte_cnt = 0;
}- Worker 쓰레드 초기화 루틴
void echo_cnt(int connfd)
{
int n;
char buf[MAXLINE];
rio_t rio;
static pthread_once_t once = PTHREAD_ONCE_INIT;
Pthread_once(&once, init_echo_cnt);
Rio_readinitb(&rio, connfd);
while((n = Rio_readlineb(&rio, buf, MAXLINE)) != 0) {
P(&mutex);
byte_cnt += n;
printf("thread %d received %d (%d total) bytes on fd %d\n",
(int) pthread_self(), n, byte_cnt, connfd); V(&mutex);
Rio_writen(connfd, buf, n);
}
}12.7 다른 동시성의 이슈
12.7.1 쓰레드 안전성
- 쓰레드에서 호출되는 함수들은 쓰레드-안전Thread-safe해야 한다.
- 정의 : 다중의 동시적인 쓰레드들에 의해 반복적으로 호출되더라도 항상 올바른 결과만을 만드는 함수
- 쓰레드-불안전thread-unsafe한 함수들의 클래스
- 클래스 1: 공유 변수들을 보호하지 않는 함수
- 클래스 2: 다중 실행 시에도 상태를 유지하는 함수
- 클래스 3: 정적 변수로의 포인터를 리턴하는 함수
- 클래스 4: 쓰레드-불안전한 함수를 호출하는 함수
- (클래스 1) 공유 변수 보호에 실패한 경우
- 해결책: 세마포어 P, V 연산 사용 (예: goodcnt.c)
- 이슈 : 동기화 연산이 실행 속도를 느리게 함
- (클래스 2) 다중 함수 호출에서도 일관적인 상태를 의존하는 경우
- (예) 정적 상태에 의존하는 난수 생성기
static unsigned int next = 1;
/* rand: return pseudo-random integer on 0..32767 */
int rand(void)
{
next = next*1103515245 + 12345;
return (unsigned int)(next/65536) % 32768;
}
/* srand: set seed for rand() */
void srand(unsigned int seed)
{
next = seed;
}// Thread-safe한 버전: global state 제거
/* rand_r - return pseudo-random integer on 0..32767 */
int rand_r(int *nextp)
{
*nextp = *nextp * 1103515245 + 12345;
return (unsigned int)(*nextp/65536) % 32768;
}- (클래스 3) 정적 변수로의 포인터를 리턴하는 경우
- (해결책 1) 함수가 결과를 저장하는 변수의 주소를 통과하도록 함수를 수정: 호출자와 피호출자도 수정해야 함
- (해결책 2) Lock-and-Copy: 호출자를 조금만 수정하면 되지만, 호출자에서 메모리 free를 해줘야 함
/* lock-and-copy version */
char *ctime_ts(const time_t *timep,
char *privatep)
{
char *sharedp;
P(&mutex);
sharedp = ctime(timep);
strcpy(privatep, sharedp);
V(&mutex);
return privatep;
}- (클래스 4) 쓰레드-불안전한 함수를 호출하는 경우
- 쓰레드-불안전한 함수 하나를 호출하는 것은 함수 전체를 쓰레드-불안전하게 만든다.
- (해결책) 쓰레드-안전한 함수만을 호출하도록 수정한다🙃🙃🙃
12.7.2 재진입성
- 다중 쓰레드에 의해 호출된 어떤 함수가 공유 변수에 접근하지 않으면 재진입성reentrant 함수라고 한다.
- 쓰레드-안전한 함수들의 중요한 부분집합
- 동기화 연산 필요 없음
- 클래스 2 함수를 쓰레드-안전하게 만드는 유일한 방법은 재진입 가능하게 만드는 것임 (예: rand_r)
12.7.3 쓰레드-안전한 라이브러리 함수
- 표준 C 라이브러리의 모든 함수들은 쓰레드-안전하다. (예: malloc, free, printf, scanf 등)
- 대부분의 Unix 시스템 콜들은 몇몇 예외를 제외하면 쓰레드-안전하다.
| Thread-unsafe function | Class | Reentrant version |
| asctime | 3 | asctime_r |
| ctime | 3 | ctime_r |
| gethostbyaddr | 3 | gethostbyaddr_r |
| gethostbyname | 3 | gethostbyname_r |
| inet_ntoa | 3 | - |
| localtime | 3 | localtime_r |
| rand | 2 | rand_r |
12.7.4 경쟁 상태
프로그램의 정확성이 다른 쓰레드가 포인트 y에 도달하기 전에 포인트 x에 도달하는 어떤 쓰레드에 의존할 때 경쟁race이 발생한다.
/* A threaded program with a race */
int main()
{
pthread_t tid[N];
int i; // ← N threads are sharing i
for (i = 0; i < N; i++)
Pthread_create(&tid[i], NULL, thread, &i);
for (i = 0; i < N; i++)
Pthread_join(tid[i], NULL);
exit(0);
}
/* Thread routine */
void *thread(void *vargp)
{
int myid = *((int *)vargp);
printf("Hello from thread %d\n", myid);
return NULL;
}
- 메인 쓰레드와 피어 쓰레드 안의 vargp의 deref의 i의 증가에서의 경쟁
- i = 0인 동안 deref가 발생하면 OK
- 그렇지 않으면, 피어 쓰레드는 잘못된 id 값을 가진다.
🔹 경쟁이 진짜 일어나는가?
🔸 메인 쓰레드
int i;
for (i = 0; i < 100; i++) {
Pthread_create(&tid, NULL, thread,&i);
}🔸 피어 쓰레드
void *thread(void *vargp) {
Pthread_detach(pthread_self());
int i = *((int *)vargp);
save_value(i);
return NULL;
}- Race 테스트
- 경쟁이 없다면 각 쓰레드는 각각 다른 i 값을 가진다.
- 저장된 값들의 집합은 각각 0~99의 각 복사본을 구성한다.
🔹 경쟁 제거
- 상태의 의도치 않은 공유를 피한다
/* Threaded program without the race */
int main()
{
pthread_t tid[N];
int i, *ptr;
for (i = 0; i < N; i++) {
ptr = Malloc(sizeof(int));
*ptr = i;
Pthread_create(&tid[i], NULL, thread, ptr);
}
for (i = 0; i < N; i++)
Pthread_join(tid[i], NULL);
exit(0);
}
/* Thread routine */
void *thread(void *vargp)
{
int myid = *((int *)vargp);
Free(vargp);
printf("Hello from thread %d\n", myid);
return NULL;
}12.7.5 데드락
- 정의 : 절대 true가 되지 않는 조건을 기다릴 때 그 프로세스가 교착상태deadlock에 있다고 한다.
- 프로세스 P1과 P2가 두 리소스 A, B를 필요로 한다고 하자. P1은 A를 가지고 있고 B를 기다리고 있다. P2는 B를 가지고 있고 A를 기다리고 있다. 두 프로세스는 영원히 대기할 것이다!
🔹 세마포어를 사용한 교착상태
int main()
{
pthread_t tid[2];
Sem_init(&mutex[0], 0, 1); /* mutex[0] = 1 */
Sem_init(&mutex[1], 0, 1); /* mutex[1] = 1 */
Pthread_create(&tid[0], NULL, count, (void*) 0);
Pthread_create(&tid[1], NULL, count, (void*) 1);
Pthread_join(tid[0], NULL);
Pthread_join(tid[1], NULL);
printf("cnt=%d\n", cnt);
exit(0);
}
void *count(void *vargp)
{
int i;
int id = (int) vargp;
for (i = 0; i < NITERS; i++) {
P(&mutex[id]); P(&mutex[1-id]);
cnt++;
V(&mutex[id]); V(&mutex[1-id]);
}
return NULL;
}
🔹 데드락 피하기
공유된 리소스들을 동일한 순서로 취득해야 한다.
int main()
{
pthread_t tid[2];
Sem_init(&mutex[0], 0, 1); /* mutex[0] = 1 */
Sem_init(&mutex[1], 0, 1); /* mutex[1] = 1 */
Pthread_create(&tid[0], NULL, count, (void*) 0);
Pthread_create(&tid[1], NULL, count, (void*) 1);
Pthread_join(tid[0], NULL);
Pthread_join(tid[1], NULL);
printf("cnt=%d\n", cnt);
exit(0);
}
void *count(void *vargp)
{
int i;
int id = (int) vargp;
for (i = 0; i < NITERS; i++) {
P(&mutex[0]); P(&mutex[1]);
cnt++;
V(&mutex[id]); V(&mutex[1-id]);
}
return NULL;
}
'Krafton Jungle > 4. CSAPP' 카테고리의 다른 글
| [Computer System] ⑫ 동시성 프로그래밍 (1) (0) | 2025.05.05 |
|---|---|
| [Computer System] ⑪ 네트워크 프로그래밍 (2) (0) | 2025.05.02 |
| [Computer System] ⑪ 네트워크 프로그래밍 (1) (0) | 2025.05.01 |
| [Computer System] ⑨ 가상메모리 (2) (0) | 2025.04.24 |
| [Computer System] ⑨ 가상메모리 (1) (0) | 2025.04.22 |