출처
Randal E. Bryant & David R. O'Hallaron. (2015). Computer Systems: A Programmer's Perspective (3rd ed.). Pearson.
3. 스레드를 이용하여 동시성 프로그래밍하기
지금까지 동시성 논리 흐름을 만드는 두 가지 접근을 살펴봤다. 첫 번째 접근인 프로세스 접근으로 우리는 각각의 흐름을 위해 별개의 프로세스를 사용했다. 커널은 각 프로세스를 자동으로 스케줄링하고 각 프로세스는 자신만의 사적 주소 공간을 가진다. 이는 흐름들이 데이터를 공유하는 것을 어렵게 만든다. 두 번째 접근인 I/O 멀티플렉싱 접근으로 우리는 우리만의 논리 흐름들을 만들고 흐름을 스케줄링하기 위해 I/O 멀티플렉싱을 사용했다. 오직 하나의 프로세스만 있기 때문에 흐름들은 전체 주소 공간을 공유한다.
이제 세 번째 접근인 스레드 기반 동시성 프로그래밍을 소개하려고 한다. 이는 앞선 두 가지 접근의 혼합이다.
스레드는 프로세스의 컨텍스트에서 실행되는 논리 흐름이다. 지금까지 이 책에서 프로세스는 프로세스당 단일 스레드로 이루어졌었다. 하지만 현대 시스템은 단일 프로세스에서 동시에 실행되는 여러 개의 스레드를 가진 프로그램을 지원한다. 스레드는 커널에 의해 자동으로 스케줄링된다. 각각의 스레드는 자신만의 스레드 컨텍스트를 가진다. 스레드 컨텍스트는 정수형의 스레드 아이디 (TID), 스택, 스택 포인터, 프로그램 카운터, 일반 목적 레지스터, condition code들을 포함한다. 프로세스에서 실행되는 모든 프로세스는 프로세스의 전체 주소 공간을 공유한다.
스레드 기반 논리 흐름은 프로세스 기반 흐름과 I/O 멀티플렉싱 기반 흐름의 우수함을 모두 가진다. 프로세스처럼 스레드는 커널에 의해 자동으로 스케줄링되고 정수 ID를 통해 커널에 의해 식별된다. I/O 멀티플렉싱처럼 여러 개의 스레드는 단일 프로세스의 컨텍스트에서 실행되기 때문에 코드, 데이터, 힙, 공유 라이브러리, 열려 있는 파일 등의 프로세스 주소 공간의 전체 콘텐츠를 공유할 수 있다.
(1) Thread Execution Model
멀티 스레드를 위한 실행 모델은 멀티 프로세스를 위한 실행 모델과 많은 면에서 비슷하다. 다음 예시를 보면 각 프로세스는 main thread라고 불리는 단일 스레드로 라이프를 시작한다. 그러다가 어느 시점에 main thread는 peer thread를 생성하고 이때부터 두 개의 스레드는 동시에 실행된다. 컨텍스트 스위칭을 통해 제어가 peer thread에게 넘어가는데 이것은 main thread가 read나 sleep 과 같은 느린 시스템 콜을 호출했거나 시스템의 인터벌 타이머에 의해 interrupt 당했기 때문이다. peer thread는 한동안 실행되다가 제어가 다시 main thread로 넘어간다.
스레드 실행은 프로세스 실행과 분명히 다른 점이 있다. 스레드 컨텍스트가 프로세스 컨텍스트보다 훨씬 작기 때문에 스레드 컨텍스트 스위칭이 프로세스 컨텍스트 스위칭보다 빠르다. 그리고 스레드는 프로세스와 다르게 rigid 부모-자식 계층으로 조직되어 있지 않다. 프로세스와 관련된 스레드는 peer의 pool을 이룬다. 이때 pool의 개념은 어떤 스레드가 어떤 스레드에 의해 생성되었는지와 독립적이다.
main thread는 그것이 프로세스에서 가장 먼저 실행되는 스레드라는 점에서만 다른 스레드와 구별된다. peer의 pool이라는 개념의 주요성은 스레드는 자신의 peer를 kill할 수도 있고 peer가 종료되기를 기다릴 수도 있따는 것이다. 그리고 peer는 같은 공유된 데이터를 읽고 쓸 수 있다.
(2) Posix Threads
Posix threads (Pthreads)는 C 프로그램에서 스레드를 조작하는 데 사용하는 표준 인터페이스이다. 이는 1995년에 도입되었고 모든 Linux 시스템에서 이용할 수 있다. Pthreads는 프로그램이 create, kill, reap thread, peer thread와 안전하게 데이터 공유하기, peer에게 system state에서의 변화를 알려주는 것을 가능하게 하는 60개의 함수를 정의한다.
다음은 간단한 Pthreads 프로그램이다.
main thread는 peer thread를 생성하고 peer thread가 종료되기를 기다린다. peer thread는 Hello, world!\n를 출력한 뒤 종료한다. main thread가 peer thread가 종료되었다는 것을 감지했을 때 main thread는 exit를 호출함으로써 프로세스를 종료한다.
#include "csapp.h"
void *thread(void *vargp);
int main()
{
pthread_t tid;
Pthread_create(&tid, NULL, thread, NULL);
Pthread_join(tid, NULL);
exit(0);
}
void *thread(void *vargp) /* thread routine */
{
printf("Hello, world!\n");
return NULL;
}
프로토타입에서 볼 수 있는 것처럼 각각의 스레드 루틴은 입력으로 단일 제네릭 포인터를 받고 제네릭 포인터를 리턴한다. 만약 스레드 루틴에 여러 개의 인자를 전달하고 싶다면 인자를 구조체에 넣어서 구조체를 각리키는 포인터를 전달해야 한다. 비슷하게 만약 스레드 루틴이 다수의 인자를 리턴하게 하고 싶다면 구조체를 가리키는 포인터를 리턴할 수 있다.
main thread는 지역 변수 tid를 선언한다. main thread는 pthread_create를 호출함으로써 새로운 peer thread를 생성한다. pthread_create에 대한 호출이 리턴되면 main thread와 새롭게 생성된 peer thread는 동시에 실행되고 tid는 새로운 스레드의 ID를 가지게 된다. main thread는 pthread_join 함수를 이용하여 peer thread가 종료되기를 기다린다. 마지막으로 main thread는 exit을 호출하여 프로세스에서 현재 실행 중인 모든 스레드 (이 경우, 오직 메인 스레드만 해당됨)를 종료한다.
peer thread는 단순히 문자열을 출력한 다음 return문을 실행함으로써 peer thread를 종료한다.
(3) 스레드 생성
스레드는 pthread_create 함수를 호출하여 다른 스레드를 생성한다.
#include <pthread.h>
typdedef void *(func)(void *);
/* Returns 0 if OK, nonzero on error */
int pthread_create(pthread_t *tid, pthread_attr_t *attr, func *f, void *arg);
/* Returns: thread ID of caller */
pthread_t pthread_self(void);
pthread_create 함수는 새로운 함수를 생성하고 새로운 스레드의 컨텍스트에서 스레드 루틴 f를 인자 arg와 함께 실행시킨다. attr 인자는 새롭게 생성되는 스레드의 기본 속성을 변경할 때 사용될 수 있다. 이러한 기본 속성은 우리의 논의를 벗어난다. 여기서는 이 인자를 항상 NULL로 설정하여 pthread_create를 호출할 것이다.
pthread_create가 리턴될 때 인자 tid는 새롭게 생성된 스레드의 ID를 가진다. 새로운 스레드는 pthread_self 함수를 호출함으로써 자신의 스레드 ID를 정한다.
(4) 스레드 종료
스레드는 다음 중 한 가지 방법으로 종료한다.
- 상위 스레드 루틴이 리턴될 때 암묵적으로 종료한다.
- pthread_exit 함수를 호출함으로써 명시적으로 종료한다. 만약 main thread가 pthread_exit을 호출하면 main thread는 모든 peer thread가 종료되기를 기다린 다음 main thread와 전체 프로세스를 리턴값 thread_return과 함께 종료한다.
- 어떤 peer thread는 Linux의 exit 함수를 호출한다. 이 함수는 프로세스와 관련된 모든 스레드와 프로세스를 종료한다.
- 어떤 peer thread는 현재 스레드의 ID와 함께 pthread_cancel 함수를 호출하여 현재 스레드를 종료한다.
#include <pthread>
/* Never returens */
void pthread_exit(void *thread_return);
/* Returns: 0 if OK, nonzero on error */
int pthread_cancel(pthread_t tid);
(5) 종료된 스레드 거두기
스레드는 pthread_join 함수를 호출하여 다른 스레드를 종료한다.
#include <pthread.h>
/* Returns: 0 if OK, nonzero on error */
int pthread_join(pthread_t tid, void **thread_return);
pthread_join 함수는 스레드 tid가 종료할 때까지 block되고, thread_return이 가리키는 위치에 스레드 루틴에 의해 리턴된 제네릭 포인터 (void *)를 할당하고, 종료된 스레드가 들고 있는 모든 메모리 리소스를 거둔다.
Linux의 wait 함수와 다르게, pthread_join은 특정 스레드의 종료만 기다릴 수 있다. pthread_join으로는 임의의 스레드가 종료되는 것을 기다릴 수 없다. 이는 프로세스 종료를 감지하기 위해 직관적이지 않은 메커니즘을 강제하게 하여 우리의 코드를 복잡하게 만든다. Steven[110]의 경우 이런 사양은 버그가 있는 것이라고 주장한다.
(6) 스레드 분리하기
스레드는 어느 시점에나 합쳐지거나 분리될 수 있다. joinable thread는 다르 스레드에 의해 거두어지거나 kill될 수 있다. joinable thread의 메모리 자원(스택 등)은 이 스레드가 다르 스레드에 의해 거두어지기 전까지 해제되지 않는다. 반대로 분리된 스레드는 다른 스레드에 의해 거두어지거나 kill될 수 없다. 이 스레드의 메모리 자원은 스레드가 종료될 때 시스템에 의해 자동으로 해제된다.
기본적으로 스레드는 합쳐질 수 있는 상태로 생성된다. 메모리 누수를 피하기 위해 모든 합쳐질 수 있는 스레드는 명시적으로 다른 스레드에 의해 거두어지거나 pthread_detach 함수를 호출함으로써 분리되어야 한다.
#include <pthread.h>
/* Returns: 0 if OK, nonzero on error */
int pthread_detach(pthread_t tid);
pthread_detach 함수는 joinable thread tid를 분리한다. 스레드는 pthread_self()의 인자와 함께 pthread_detach를 호출함으로써 그들 자신을 분리할 수 있다.
비록 몇몇 예시에서 joinable thread를 사용할 것이기는 하지만 실제 프로그램에서는 분리된 스레드를 쓰는 것이 좋다. 예를 들어 고성능 웹 서버는 웹 브라우저로부터 connection 요청을 받을 때마다 새로운 peer thread를 생성해야 할 수 있다. 각각의 connection이 별개의 스레드에서 처리되기 때문에, 서버는 각각의 peer thread가 종료되는 것을 기다릴 필요가 없다. 이런 경우에 peer thread는 요청을 처리하기 전에 자기 자신을 분리하여 이 스레드가 종료될 때 메모리 리소스가 재사용될 수 있도록 해야 한다.
(7) 스레드 초기화하기
pthread_once 함수는 스레드 루틴과 관련된 상태를 초기화할 수 있게 해준다.
#include <pthread.h>
pthread_once_t onece_control = PTHREAD_ONCE_INIT;
/* Always returns 0 */
int pthread_once(pthread_once_t *once_control, void (*init_routine)(void));
once_control 변수는 전역 또는 지역 변수이다. 항상 PTHREAD_ONCE_INIT 으로 초기화된다. pthread_once를 once_control 인자와 함께 처음 호출하면 pthread_once는 인자도 없고 리턴 값도 없는 init_routine을 호출한다. 그 이후에는 once_control 인자와 함께 pthread_once 함수를 호출해도 아무 동작도 하지 않는다. pthread_once는 여러 개의 스레드에 의해 공유되는 전역 변수를 동적으로 초기화해야 할 때 유용하다.
(8) 스레드 기반 동시성 서버
다음은 스레드 기반 동시성 에코 서버 코드이다. 전반적인 구조는 프로세스 기반 디자인과 비슷하다. main thread는 반복적으로 connection 요청을 기다린 다음 요청을 처리할 peer thread를 생성한다. 코드는 간단해보이지만 조금 더 자세히 살펴봐야 하는 일반적인 미묘한 이슈들이 있다.
#include "csapp.h"
void echo(int connfd);
void *thread(void *vargp);
int main(int argc, char **argv)
{
int listenfd, *connfdp;
socklen_t clientlen;
struct sockaddr_storage clientaddr;
pthread_t tid;
if (argc != 2) {
fprintf(stderr, "usage: %s <port>\n", argv[0]);
exit(0);
}
listenfd = Open_listenfd(argv[1]);
while (1) {
clientlen=sizeof(struct sockaddr_storage);
connfdp = Malloc(sizeof(int));
*connfdp = Accept(listenfd, (SA *) &clientaddr, &clientlen);
Pthread_create(&tid, NULL, thread, connfdp);
}
}
/* Thread routine */
void *thread(void *vargp)
{
int connfd = *((int *)vargp);
Pthread_detach(pthread_self());
Free(vargp);
echo(connfd);
Close(connfd);
return NULL;
}
첫 번째 이슈는 pthread_create를 호출할 때 어떻게 peer thread에게 connected descriptor를 전달할 것인지의 문제이다. 분명한 접근은 디스크립터를 가리키는 포인터를 전달하는 것이다. 이는 다음과 같다.
connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
Pthread_create(&tid, NULL, thread, &connfd);
그다음 포인터를 역참조하고 그것을 지역 변수에 할당한다.
void *thread(void *vargp) {
int connfd = *((int *)vargp);
...
}
하지만 이는 잘못되었다. 왜냐하면 peer thread에 있는 할당문과 main thread에 있는 accept 사이에 race condition 경쟁 상태를 유발하기 때문이다. 만약 peer thread의 할당문이 다음 accept 전에 완료되면 peer thread에 있는 지역 connfd 변수는 정확한 값을 가지게 된다. 하지만 할당문이 다음 accept 이후에 완료되면 peer thread에 있는 지역 변수 connfd 는 다음 connection의 디스크립터 번호를 갖게 된다. 반갑지 않은 결과로 두 개의 스레드가 같은 디스크립터에서 입출력을 수행하게 된다. 이러한 잠재적인 치명적인 race를 피하기 위하여 우리는 accept에 의해 리턴된 각각의 connected descriptor를 자신의 동적으로 할당된 메모리 블록에 할당해야 한다.
또다른 이슈는 스레드 루틴에서 메모리 누수를 피해야 한다는 것이다. 우리가 스레드를 명시적으로 거두고 있지 않기 때문에 우리는 각각의 스레드를 분리하여 스레드가 종료될 때 메모리 자원이 재할당될 수 있게 해야 한다. 그리고 main thread에 의해 할당받은 메모리 블록을 해제할 때는 매우 주의해야 한다.
4. 스레드 프로그램에서의 공유 변수 Shared Variables in Threaded Programs
개발자의 관점에서 스레드의 매력적인 측면 중 하나는 여러 개의 스레드가 같은 프로그램 변수를 공유할 수 있다는 점의 편리함이다. 하지만 공유는 까다로울 수 있다. 스레드 프로그램을 정확하게 작성하기 위해서 우리는 공유가 무엇을 의미하는지 공유가 어떻게 작동하는지를 명확하게 이해해야 한다.
C 프로그램에 있는 변수가 공유되는지 아닌지를 이해하기 위해 거쳐야 하는 기본적인 질문들이 있다.
(1) 스레드의 기반 메모리 모델은 무엇인가?
(2) 이 모델에서 변수들의 인스턴스는 어떻게 메모리에 매핑되는가?
(3) 마지막으로, 얼마나 많은 스레드가 이 인스턴스들을 참조한는가?
변수는 여러 개의 스레드가 변수의 인스턴스를 참조할 때만 공유된다.
공유에 대한 논의를 구체적으로 이어나가기 위해 위 프로그램을 예시로 사용하겠다. 비록 조금 억지스러운 부분이 있기는 하지만 공유와 관련된 미묘한 지점들을 많이 보여주기 때문에 유용한 자료이다. 예시 프로그램은 main thread와 두 개의 peer thread로 이루어져 있다. main thread는 각각의 peer thread에게 고유한 ID를 전달한다. peer thread는 스레드 루틴이 호출된 총 횟수와 함께 개인화된 메시지를 출력하는 데 사용된다.
#include "csapp.h"
#define N 2
void *thread(void *vargp);
char **ptr; /* Global variable */
int main()
{
int i;
pthread_t tid;
char *msgs[N] = {
"Hello from foo",
"Hello from bar"
};
ptr = msgs;
for (i = 0; i < N; i++)
Pthread_create(&tid, NULL, thread, (void *)i);
Pthread_exit(NULL);
}
void *thread(void *vargp)
{
int myid = (int)vargp;
static int cnt = 0; //line:conc:sharing:cntdec
printf("[%d]: %s (cnt=%d)\n", myid, ptr[myid], ++cnt);
return NULL;
}
(1) 스레드 메모리 모델
동시성 스레드의 풀은 프로세스의 컨텍스트에서 실행된다. 각각의 스레드는 별개의 스레드 컨텍스트를 가진다. 이 스레드 컨텍스트는 스레드 아이디, 스택, 스택 포인터, 프로그램 카운터, condition code, 일반 목적 레지스터 값을 포함한다. 각각의 스레드는 다른 스레드와 프로세스의 나머지 부분을 공유한다. 이는 전체 사용자 가상 주소 공간 (읽기 전용 텍스트 (코드), 읽기/쓰기 데이터, 힙, 공유 라이브러리 코드와 데이터 영역)을 포함한다. 스레드는 또한 open file의 집합도 공유한다.
동작 방식상 하나의 스레드가 다른 스레드의 레지스터 값을 읽거나 레지스터 값을 쓰는 것은 불가능하다. 반면 모든 스레드는 공유 가상 메모리의 모든 위치에 접근할 수 있다. 만약 어떤 스레드가 메모리 위치를 변경했다면 다른 모든 스레드도 그 위치를 읽을 때 변화를 보게 된다. 즉 레지스터는 절대 공유되지 않는 반면 가상 메모리는 항상 공유된다.
별개의 스레드 스택을 위한 메모리 모델은 깔끔하지 않다. 이 스택들은 가상 주소 공간의 스택 영역에 포함되어 있고 "일반적으로" 각각의 스레드에 의해 독립적으로 접근된다. 여기서 "항상"이 아니라 "일반적으로"라고 말한 이유는 다른 스레드의 스택이 다른 스레드로부터 보호되지 않기 때문이다. 따라서 만약 어떤 스레드가 다른 스레드 스택을 가리키는 포인터를 얻었다면 그 스레드는 그 스택의 모든 파트를 읽고 그 파트에 쓸 수가 있다. 우리의 예시 프로그램이 이것을 보여준다. peer thread는 전역 변수 ptr을 통해 main thread의 스택의 콘텐츠를 간접적으로 참조한다.
(2) 메모리에 변수 매핑하기
C 프로그램에 있는 변수는 스토리지 유형에 따라 가상 메모리에 매핑된다.
전역 변수
전역 변수는 함수 밖에서 선언된 모든 변수이다. 런타임에 가상 메모리의 읽기/쓰기 영역은 모든 스레드에 의해 참조될 수 있는 각각의 전역 변수에 대한 인스턴스를 정확히 하나 포함한다. 예를 들어, 전역 변수 ptr은 가상 메모리의 읽기/쓰기 영역에 하나의 런타임 인스턴스를 가진다. 변수의 인스턴스가 오직 하나만 있을 때 그 인스턴스는 변수명을 이용하여 표현하겠다.
지역 자동 변수 Local automatic variables
지역 자동 변수는 static 속성 없이 함수 안에서 선언된 변수이다. 런타임에 각 스레드 스택은 모든 지역 자동 변수의 인스턴스를 포함한다. 이는 여러 개의 스레드가 같은 스레드 루틴을 실행하는 상황에서도 마찬가지이다. 예를 들어, 지역 변수 tid의 인스턴스 하나가 있고 tid가 main thread의 스택에 있다. 우리는 이 인스턴스를 tid.m이라고 표현할 것이다. 다른 예시로 지역 변수 myid의 두 개의 인스턴스가 있다. 하나는 peer thread 0의 스택에 있는 인스턴스이고 다르 하나는 peer thread 1의 스택에 있는 인스턴스이다. 우리는 이들을 각각 mypid.p0, mypid.p1이라고 부르겠다.
지역 정적 변수 Local static variables
지역 정적 변수는 함수 안에서 static 속성과 함께 선언된 변수이다. 전역 변수처럼 가상 메모리의 읽기/쓰기 영역은 프로그램에서 정의된 각 지역 정적 변수의 인스턴스를 오직 하나만 포함한다. 예를 들어, 예시 프로그램에 있는 각각의 peer thread가 cnt를 선언한다고 해도 런타임에 가상 메모리의 읽기/쓰기 영역에는 cnt의 인스턴스가 오직 하나만 있다. 각각의 peer thread는 이 인스턴스를 읽고 이 인스턴스에 쓴다.
(3) 공유 변수
변수의 인스턴스가 하나보다 더 많은 스레드에 의해 참조될 때 그 변수 v를 공유되었다고 말한다. 예를 들어, 우리의 예시 프로그램에서 변수 cnt는 공유되었다. 왜냐하면 하나의 런타임 인스턴스만 가지며 그 인스턴스는 두 개의 peer thread 모두에서 참조되기 때문이다. 반면 myid는 공유되지 않는다. 왜냐하면 두 개의 인스턴스가 각각 오직 하나의 스레드에 의해 참조되기 때문이다. 하지만 msgs와 같은 지역 자동 변수는 공유될 수 있다.
5. 세마포어로 스레드 동기화하기
공유 변수는 편리할 수 있지만 끔찍한 동기화 에러의 가능성을 가져온다. 다음 badcnt.c 프로그램을 보라. 이 프로그램은 두 개의 스레드를 생성하는데 각각의 스레드는 전역 공유 변수 cnt를 증가시킨다.
/* WARNING: This code is buggy! */
#include "csapp.h"
void *thread(void *vargp); /* Thread routine prototype */
/* Global shared variable */
volatile long cnt = 0; /* Counter */
int main(int argc, char **argv)
{
long niters;
pthread_t tid1, tid2;
/* Check input argument */
if (argc != 2) {
printf("usage: %s <niters>\n", argv[0]);
exit(0);
}
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 != (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;
}
각 스레드가 이 카운터 변수를 niters 번 증가시켰기 때문에 우리는 최종 값이 2 x niters 라고 기대할 것이다. 하지만 badcnt.c 프로그램을 실행시켜보면 우리는 잘못된 답을 얻을 뿐만 아니라 매번 실행할 때마다 다른 답을 얻게 된다.
무엇이 잘못된 걸까? 이 문제를 명확하게 이해하기 위해서 우리는 이 카운터 루프의 어셈블리 코드를 봐야 한다. thread i의 루프 코드를 다음과 같이 다섯 파트로 나누어보자.
Hi: 루프의 맨 상단에 있는 명령 블록문
Li: accumulator register %rdx(i)로 공유 변수 cnt를 로드하는 명령
Ui: %rdx를 업데이트 (증가)하는 명령
Si: 공유 변수 cnt로 업데이트된 %rdx의 값을 복원하는 명령
Ti: 루프의 마지막에 있는 명령 블록
맨 상단과 마지막은 지역 스택 변수만 조작하는 반면, Li, Ui, Si는 공유 카운터 변수의 콘텐츠를 조작한다.
badcnt.c에 있는 두 개의 peer thread가 단일 프로세서에서 동시에 실행될 때 기계어는 순서대로 완료된다. 따라서 각각의 동시 실행은 두 개의 스레드에 있는 명령의 총 순서(교차)를 정의한다. 불행히도 어떤 순서는 정확한 결과를 내지만 다른 결과는 그렇지 않을 것이다.
일반적으로 운영체제가 당신의 스레드를 위해 정확한 순서를 선택해줄 것이라고 예측할 수 있는 방법은 없다. 예를 들어, 위 그림에서 (a)는 올바른 명령 순서의 순차적인 순서를 보여준다. 각 스레드가 공유 변수 cnt를 업데이트한 다음에 메모리에 있는 변수는 우리가 기대한 결과인 2이다.
반면 (b)의 순서는 cnt에 대해 부정확한 값을 낸다. 이러한 문제는 스레드 1이 step 2에서 cnt를 로드한 이후에 하지만 스레드 1이 step 6 이전에 업데이트된 값을 저장하기 전에 스레드 2가 step 5에서 cnt를 로드했기 때문에 발생한 것이다. 따라서 각 스레드는 1이라는 값을 저장하게 된다. 우리는 이렇게 정확하고 부정확한 명령 순서의 개념을 프로세스 그래프라고 알려진 도구의 힘으로 명확하게 할 수 있다.
(1) 프로세스 그래프
프로세스 그래프는 n개의 동시 스레드의 실행을 n-차원 좌표 공간 (cartesian space)를 통해 궤도 (trajectory)로 모델링한다. 각각의 축 (axis) k는 스레드 k의 프로그레스에 대응된다. 각각의 점 (I1, I2, I3, ... , In)은 스레드 k (k = 1, ..., n)가 명령 Ik를 완료했을 때의 상태를 나타낸다. 그래프 원본은 아무 스레드도 명령을 완료하지 않았을 때인 initial state에 해당한다.
다음은 badcnt.c 프로그램의 첫 번째 루프를 위한 2차원 progress graph이다. 수평축은 스레드 1에 해당하고 수직축은 스레드 2에 해당한다. 점 (L1, S2)은 스레드 1이 L1을 완료했고 스레드 2는 S2를 완료했을 때의 상태에 해당한다.
progress graph는 명령의 실행을 한 상태에서 다른 상태로의 transition으로 모델링한다. transition은 한 점에서 인점한 점으로의 방향이 있는 간선으로 표현된다. 합법적인 transition은 오른쪽 방향(스레드 1이 명령을 완료했을 때) 또는 윗쪽 방향(스레드 2가 명령을 완료했을 때)으로 이동한다. 두 명령은 동시에 완료될 수 없다. 즉, 대각선의 transition은 허용되지 않는다. 프로그램은 절대 뒤로 가지 않기 때문에 아래 방향 또는 왼쪽 방향으로 가는 것은 모두 허용되지 않는다.
프로그램의 실행 히스토리는 state space를 통해 궤도로 모델링된다. 다음은 다음 명령 순서에 해당하는 궤도를 보여준다.
H1, L1, U1, H2, L2, S1, T1, U2, S2, T2
스레드 i에서, 공유 변수 cnt의 값을 조작하는 명령 (Li, Ui, Si)은 다른 스레드의 임계 영역과 절대 교차되어서는 안 되는 임계 영역 (critical section)을 만든다. 즉, 각 스레드가 임계 영역 안에서 명령을 실행 중일 때에는 각 스레드가 공유 변수에 상호배타적인 접근 (mutually exclusive access)를 할 수 있도록 보장해주어야 한다. 이러한 현상은 일반적으로 mutual exclusion이라고 알려져 있다.
process graph에서 두 임계 영역의 교차는 unsafe region이라고 알려진 state space 영역을 정의한다. 다음은 변수 cnt의 unsafe region을 보여준다. 이때 unsafe region은 둘레(경계선)에 있는 state와 인접해 있지만 이 state들을 포함하지 않는다는 것을 확인하길 바란다. 예를 들어 상태 (H1, H2)와 (S1, U2)는 unsafe region을 인접하지만 usafe region의 부분은 아니다. (경계선이 있는 점이다.)
unsafe region을 피해가는 궤도는 safe trajectory라고 알려져 있다. 반대로 unsafe region의 부분을 건드리는 궤도는 unsafe trajectory라고 알려져 있다. 위 그림에서 위쪽 궤도는 unsafe region을 왼쪽과 위쪽으로 피해가는 safe trajectory이다. 반면 아래쪽 궤도는 unsafe region을 가로지르는 unsafe trajectory이다.
safe trajectory는 공유 카운터 변수를 정확하게 업데이트한다. 전역 자료 구조를 공유하는 동시성 서버의 정확한 실행을 보장하기 위해서는 스레드들이 언제나 safe trajectory를 가질 수 있게 스레드들을 동기화해야 한다. 이를 위한 전형적인 접근은 세마포어 방식이다.
(2) 세마포어
Edsger Dijkstra라는 동시성 프로그래밍의 선구자는 세마포어라는 특별한 유형의 변수에 기반을 둔, 스레드 동기화 문제의 해결책을 제안했다. 세마포어는 비음수 정수 값을 가진 전역 변수로 오직 두 개의 연산자 P와 V를 통해서만 조작할 수 있다.
P(s)
만약 s가 0이 아니라면 P는 s를 감소시키고 즉시 리턴한다.
만약 s가 0이라면 V 연산에 의해 s가 0이 아니게 되고 스레드가 재시작될 때까지 스레드를 중단시킨다. 스레드가 재시작되고 나서 P 연산은 s를 감소시키고 호출자에게 제어를 리턴한다.
V(s)
V 연산은 s를 1 증가시킨다. s가 0이 아닌 값이 되기를 기다리는 P 연산에서 블록된 스레드가 있다면 V 연산은 이 스레드 중 하나의 스레드를 재시작한다. 그러면 그 이후에 s를 감소시킴으로써 P 연산이 완료된다.
* Edsger Dijkstra (1930-2002)는 네덜란드 사람이었다. P와 V 이름은 네덜란드어 proberen (테스트하기)와 verhogen(증가시키기)에서 유래된 것이다.
P에서의 테스트 연산과 감소 연산은 세마포어가 0이 아니게 되면 s의 감소는 interruption 없이 발생한다는 점에서 불가분 (indivisible)의 형태로 발생한다. V에서의 증가 연산 또한 V 연산이 interruption 없이 세마포어를 로드하고 증가시키고 저장한다는 점에서 불가분의 형태로 발생한다.
V를 정의할 때는 기다리고 있는 스레드가 어떤 순서로 재시작할지를 정의하지 않는다. V에게 요구되는 것은 기다리는 스레드를 하나만 재시작해야 한다는 점이다. 따라서 세마포어에서 여러 개의 스레드가 기다리고 있을 때 당신은 V 연산의 결과로 어떤 스레드가 재시작될지 예측할 수 없다.
P와 V의 정의는 실행 프로그램이 세마포어(적절하게 초기화됨)가 음수 값을 가지는 상태에 절대 진입하지 않도록 보장한다.이 속성은 semaphore invariant라고 알려져 있는데 이는 동시성 프로그램의 궤도를 제어하는 데 강력한 도구를 제공한다.
Posix 표준은 세마포어를 조작할 수 있는 다양한 함수를 정의하고 있다.
#include <semaphore.h>
/* Returns: 0 if OK, -1 on error */
int sem_init(sem_t *sem, 0, unsigned int value);
int sem_wait(sem_t *s); /* P(s) */
int sem_post(sem_t *s); /* V(s) */sem_init 함수는 세마포어 sem의 값을 value로 초기화한다. 각 세마포어는 사용되기 전에 반드시 초기화되어야 한다. 우리의 사용례에서 가운데 인자는 항상 0이다. 프로그램은 sem_wait 과 sem_post 함수를 호출함으로써 P와 V를 수행한다.
정확성을 위해 우리는 wrapper 함수 P와 V를 사용할 것이다.
#include "csapp.h"
/* Returns: nothing */
void P(sem_t *s); /* Wrapper function for sem_wait */
void V(sem_t *s); /* Wrapper function for sem_post */
(3) Mutual Exclusion을 위해 세마포어 이용하기
세마포어는 공유 변수에 대한 상호배타 접근을 보장하는 데 편리한 방법을 제공한다. 기본적인 아이디어는 공유 변수에 1로 초기화된 세마포어를 연관시키고 P(s)와 V(s) 연산으로 임계 영역을 둘러싸는 것이다.
공유 변수를 보호하기 위해 이런 식으로 사용되는 세마포어를 binary semaphore라고 한다. 왜냐하면 그 값이 항상 0 또는 1을 가지기 때문이다. mutual exclusion을 제공하기 위한 목적의 binary semaphore는 종종 mutex라고 불린다. mutex에서 P 연산을 수행하는 것을 mutex를 lock한다고 말한다. V 연산을 수행하는 것을 mutex를 unlock한다고 말한다. lock이 걸리고 unlock되지 않은 스레드는 mutex를 hold하고 있다고 말한다. 한편 이용 가능한 리소스 집합을 위한 카운터로서 사용되는 세마포어는 counting semaphore라고 발한다.
다음 progress graph는 우리의 예시 카운터 프로그램을 적절하게 동기화하기 위해 binary semaphore (mutex)를 어떻게 사용해야 하는지를 보여준다.
각 state는 그 상태에서의 세마포어 s 값으로 라벨링되어 있다. 핵심 아이디어는 P와 V 연산의 조합이 forbidden region이라는, s < 0인 state의 collection을 만들어낸다는 것이다. 세마포어는 invariant하기 때문에 그 어떤 궤도도 forbidden region에 있는 상태를 포함할 수 없다. 그리고 forbidden region이 완전히 unsafe region을 에워싸고 있기 때문에 그 어떤 궤도도 unsafe region에 접근할 수 없다. 따라서 명령의 실행 순서와 관계없이 런타임에 모든 가능한 궤도는 안전하고 프로그램은 정확하게 카운터를 증가시킨다.
동작상 P와 V 연산에 의해 생성된 forbidden region은 여러 개의 스레드가 임계 영역에서 실행되는 것을 불가능하게 만든다. 즉, 세마포어 연산은 임계 영역으로의 상호배타 접근을 보장한다.
세마포어를 이용하여 프로그램을 동기화려면 먼저 mutex라고 불리는 세마포어를 선언한다.
volatile long cnt = 0; /* Counter */
sem_t mutex; /* Semaphore that protects counter */
그리고 메인 루틴에서 세마포어를 1로 초기화한다.
Sem_init(&mutex, 0, 1) /* mutex = 1 */
마지막으로 스레드 루틴에서의 공유 변수 cnt에 대한 업데이트를 P와 V 연산으로 둘러싸서 보호한다.
for (i = 0; k < niters; i++) {
P(&mutex);
cnt++;
V(&mutex);
}
적절하게 동기화된 프로그램을 실행시키면 이제 매번 정확한 결과가 나온다.
*progress graph의 한계
progress graph는 단일 프로세서에서의 동시성 프로그램을 시각화하고 동기화를 위해 필요한 것이 무엇인지 이해하는 데 좋은 방법이다. 하지만 CPU/cache 쌍이 같은 메인 메모리를 공유하는 멀티프로세서에서의 동시 실행의 관점에서는 한계가 있다. 멀티프로세서의 행동은 process graph로 설명될 수 없다. 특히 멀티프로세스 메모리 시스템은 process graph에 있는 궤도에 해당하지 않는 state에 있을 수 있다. 그렇지만 메시지는 같다. 언제나 공유 자원에 대한 접근을 동기화하라.
(4) 공유 리소스를 스케줄링하기 위해 세마포어 사용하기
세마포어의 쓰임 중 또다른 중요한 쓰임은 공유 자원에 대한 접근을 스케줄링하는 것이다. 이 시나리오에서 스레드는 다르 스레드에게 프로그램에서의 어떤 condition을 알리기 위해 세마포어 연산을 사용한다. 전형적이고 유용한 예시로는 producer-consumer와 readers-writers 문제가 있다.
Producer-Consumer 문제
Producer-consumer 문제는 다음과 같다.
producer와 consumer 스레드는 n개의 슬롯을 가진 bounded buffer를 공유한다.
producer 스레드는 반복적으로 아이템을 생산하고 버퍼에 그것을 삽입한다. consumer 스레드는 반복적으로 버퍼에 있는 아이템을 제거하고 이들을 이용한다. 여러 개의 producer와 consumer가 있는 상황도 가능하다.
아이템을 삽입하고 제거하는 것은 공유 자원을 업데이트하는 일이기 때무에 버퍼에 대한 상호 배타 접근을 보장해야 한다. 하지만 mutual
exclusion을 보장하는 것으로는 충분하지 않다. 우리는 또한 버퍼에 대한 접근을 스케줄링해야 한다. 만약 버퍼가 가득 찼다면 (빈 슬롯이 없다면) producer는 슬롯이 이용 가능해질 때까지 기다려야 한다. 만약 버퍼가 비어 있다면 consumer는 아이템이 이용 가능할 때까지 기다려야 한다.
producer-consumer 상호작용은 실제 시스템에서 빈번하게 발생한다. 예를 들어, 멀티미디어 시스템에서 producer는 비디오 프레임을 인코딩하고 consumer는 이를 디코딩해서 화면에 렌더링할 수 있다. 버퍼의 목적은 개별 프레임의 인코딩과 디코딩 시간에서의 data-dependent 차이점에 의해 발생하는 비디오 스트림의 불안정함을 감소시키는 것이다. 버퍼는 producer를 위해 슬롯 저장소를 제공하고 consumer를 위해 인코딩된 프레임의 저장소를 제공한다.
또 다른 예는 그래픽 유저 인터페이스 설계이다. producer는 마우스와 키보드 이벤트를 감지하고 이들을 버퍼에 넣는다. consumer는 어떤 우선순위 기반 방법으로 버퍼에서 이벤트를 제거하고 스크린에 페인팅을 한다.
이 절에서 우리는 producer-consumer 프로그램을 만들기 위해 간단한 패키지 SBUF를 사용할 것이다. SBUF는 sbuf_t 타입의 bounded buffer를 조작한다. 아이템들은 n개의 아이템을 가진 동적으로 할당되는 정수 배열 (buf)에 저장된다. front와 rear 인덱스는 배열에서 첫 번째 아이템과 마지막 아이템을 추적한다. 버퍼에 대한 접근은 세 개의 세마포어가 동기화한다. mutex 세마포어는 버퍼에 대한 상호 배타적 접근을 제공한다. slots와 items 세마포어는 counting semaphore로 빈 슬롯과 이용 가능한 아이템의 수를 카운팅한다.
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;
다음은 SBUF 패키지의 구현이다. sbuf_init 함수는 버퍼를 위한 힙 메모리를 할당하고, 빈 버퍼를 나타내기 위해 front와 rear를 설정하고, 세 개의 세마포어에 초깃값을 할당한다. sbuf_deinit 함수는 애플리케이션이 버퍼 스토리지를 다 사용했을 때 버퍼 스토리지를 해제한다. sbuf_insert 함수는 이용 가능한 슬롯을 기다리고, mutex를 lock 걸고 아이템을 추가하고 mutex를 unlock하고 새로운 아이템이 이용 가능해졌음을 알린다. sbuf_remove 함수는 대칭적이다. 이용 가능한 버퍼 아이템을 기다리고, 버퍼의 front에서 아이템을 제거하고, mutex를 unlock하고 새로운 슬롯이 이용 가능해졌음을 알린다.
#include "csapp.h"
#include "sbuf.h"
/* 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 zero data 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 문제
readers-writers 문제는 mutual exclusion 문제의 일반화이다. 동시성 스레드의 집합은 메인 메모리에 있는 자료구조나 디스크에 있는 데이터베이스 등의 공유 자원에 접근한다. 어떤 스레드는 object를 읽기만 하고 어떤 스레드는 변경도 한다. object를 변경하는 스레드는 writer라고 한다. object를 읽기만 하는 스레드는 reader라고 한다. writer는 object에 대해 배타적인 접근을 가져야 하지만 reader는 수많은 reader들과 object를 공유할 수 있다. 일반적으로 무한한 수의 동시 reader와 writer가 있다.
reader-writer 상호작용은 실제 시스템에서 빈번하게 발생한다. 예를 들어, 온라인 항공사 예약 시스템에서 수많은 고객은 좌석 배치를 동시에 볼 수 있지만 좌석을 예약하는 것은 데이터베이스에 대한 독점적인 접근을 가져야 한다. 또 다른 예로는 멀티 스레드로 구성된 캐싱 기능이 있는 Web proxy이다. 수많은 스레드가 공유되는 페이지 캐시에 있는 페이지를 가져올 수 있지만 캐시에 새로운 페이지를 쓰려는 스레드는 독점적잊 접근을 가져야 한다.
reader-writer 문제는 몇 가지 변형이 있는데 각각은 reader와 writer의 우선순위에 기반하고 있다.
first readers-writers 문제는 reader를 선호하여, writer가 object를 사용할 수 있는 권한을 인정받지만 않았다면 reader가 기다릴 필요가 없다. 즉, writer가 기다리는 중이라는 이유로 reader가 기다릴 필요가 없다.
second reader-writers 문제는 writer를 선호하여, writer가 쓰기에 준비가 되었다면 가능한 빨리 쓰기를 수행한다. 첫 번째와 다르게 writer가 기다리고 있다고 하더라도 writer 이후에 도착한 reader는 반드시 기다려야 한다.
다음은 first readers-writers 문제를 보여준다. 많은 동기화 문제에 대한 해결책과 같이 미묘한 부분이 있고 자칫하면 간단해보인다.
/* Global variables */
int readcnt; /* Initially = 0 */
sem_t mutex, w; /* Both 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);
}
void writer(void)
{
while (1) {
P(&w);
/* Critical section */
/* Writing happens */
V(&w);
}
}
}
w 세마포어는 공유 object를 접근하는 임계 영역에 대한 접근을 제어한다. mutex 세마포어는 현재 임계 영역에 있는 readers의 수를 카운팅하는, 공유 변수 readcnt에 대한 접근을 보호한다. writer는 임계 영역에 진입할 때마다 w mutex를 lock 걸고 떠날 때마다 w mutex를 unlock한다. 이는 임계 영역에 writer가 최대 하나만 있도록 보장한다. 한편 임계 영역에 처음 진입한 reader만 w를 lock 걸고 마지막으로 임계 영역을 떠난 reader만 mutex를 unlock한다. 다른 reader가 이미 있을 때 임계 영역에 진입하거나 임계 영역을 떠나는 reader는 w mutex를 무시한다. 이는 어떤 reader가 w mutex를 들고 있는 한 무한한 수의 reader가 임계 영역에 방해받지 않고 진입할 수 있음을 의미한다.
두 가지의 readers-writers 문제에 대한 정확한 해결책은 starvation 이라는 결과를 맞이할 수 있다. starvation이란 스레드가 무한히 블록되어서 progress를 만드는 데 실패하는 것이다. 예를 들어, 위 예시에서 writer는 reader의 stream이 도착하는 동안 무한히 기다려야 할 수 있다.
*다른 동기화 메커니즘
세마포어는 전형적이고 간단하고 깔끔한 semantic model을 가진 동기화 방법이다. 하지만 다른 동기화 기술도 있다는 것을 알아야 한다. 예를 들어, 자바의 스레드는 Java monitor라고 불리는 메커니즘으로 동기화된다. Java monitor는 mutual exclusion과 세마포어의 스케줄링 능력의 고수준 추상화를 제공한다. 사실 monitor는 세마포어로 구현될 수 있다. 또 다른 예로 Pthread 인터페이스는 mutex와 condition 이라는 변수에 동기화 연산의 집합을 정의해놓고 있다. Pthread mutex는 mutual exclusion에 사용된다. condition variable은 공유 자원(예를 들어, producer-consumer 프로그램의 bounded buffer)에 대한 접근을 스케줄링할 때 사용된다.
(5) Prethreading 기반 동시성 서버
지금까지 공유 자원에 접근할 때 그리고 공유 자원에 대한 접근을 스케줄링할 때 세마포어가 어떻게 쓰일 수 있는지 살펴봤다. 이런 아이디어들을 더 명확하게 이해하는 데 도움을 주기 위해서 이를 prethreading 이라는 기술에 기반으로 둔 동시성 서버에 적용해보겠다.
위에서 봤던 동시성 서버에서 우리는 새로운 클라이언트 각각을 위해 새로운 스레드를 생성했다. 이러한 접근의 단점은 각각의 클라이언트를 위한 새로운 스레드를 생성하는 비용이 든다는 것이다. prethreading은 producer-consumer 모델을 이용하여 이것의 오버헤드를 줄이고자 노력한다. 서버는 main thread와 worker thread 집합으로 이루어져 있다. main thread는 반복적으로 클라이언트로부터 connection 요청을 받고 그 결과로 생긴 connected descriptor를 bounded buffer 에 넣는다. 각각의 worker thread는 반복적으로 버퍼로부터 디스크립터를 제거하고, 클라이언트에게 서비스하고, 다음 디스크립터를 기다린다.
다음은 prethreaded 동시성 에코 서버를 구현하기 위해 SBUF 패키지를 어떻게 사용할 수 있는지를 보여준다.
#include "csapp.h"
#include "sbuf.h"
#define NTHREADS 4
#define SBUFSIZE 16
void echo_cnt(int connfd);
void *thread(void *vargp);
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;
if (argc != 2) {
fprintf(stderr, "usage: %s <port>\n", argv[0]);
exit(0);
}
listenfd = Open_listenfd(argv[1]);
sbuf_init(&sbuf, SBUFSIZE); //line:conc:pre:initsbuf
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 */
}
}
void *thread(void *vargp)
{
Pthread_detach(pthread_self());
while (1) {
int connfd = sbuf_remove(&sbuf); /* Remove connfd from buffer */ //line:conc:pre:removeconnfd
echo_cnt(connfd); /* Service client */
Close(connfd);
}
}
버퍼 sbuf를 초기화하고 나서 main thread는 worker thread의 집합을 생성한다. 그다음 무한 루프에 진입해서 connection 요청을 받고 그 결과로 생긴 connected descriptor를 sbuf에 넣는다. 각각의 worker thread는 매우 간단한 행동을 한다. 버퍼에서 connected descriptor를 제거할 수 있을 때까지 기다리고 에코 클라이언트 입력에 대해 echo_cnt 함수를 호출한다.
#include "csapp.h"
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;
}
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; //line:conc:pre:cntaccess1
printf("server received %d (%d total) bytes on fd %d\n",
n, byte_cnt, connfd);
V(&mutex);
Rio_writen(connfd, buf, n);
}
}
echo_cnt 함수는 공유 변수 byte_cnt에 모든 클라이언트로부터 받은 바이트를 축적해서 저장하는 echo 함수이다. 이 코드는 공부하기 흥미로운 코드이다. 왜냐하면 스레드 루틴에서 호출된 패키지를 초기화하는 일반적인 기술을 보여주기 때문이다. 우리는 byte_cnt 카운터 변수와 mutex 세마포어를 초기화해야 한다. 한 가지 접근 방법은 SBUF와 RIO 패키지를 사용할 때처럼 메인 스레드가 초기화 함수를 명시적으로 호출하는 것이다. 또 다른 접근은 이 예시처럼 어떤 스레드가 echo_cnt 함수를 처음 호출했을 때 pthread_once 함수를 이용하여 초기화 함수를 호출하는 것이다. 이 접근의 이점은 패키지를 이용하게 편하게 만든다는 것이다. 단점은 echo_cnt에 대한 모든 호출이 대부분의 경우에 하는 게 없는, pthread_once에 대한 호출을 만든다는 것이다.
패키지가 초기화되고 나면 echo_cnt 함수는 RIO 버퍼 I/O 패키지를 초기화하고 클라이언트로부터 받은 각 텍스트 라인을 에코한다. 공유 변수 byte_cnt에 대한 접근은 P 연산과 V 연산에 의해 보호된다.
* 스레드 기반 이벤트 드리븐 프로그램
이벤트 드리븐 프로그램을 작성할 때 I/O 멀티플렉싱이 유일한 방법은 아니다. 예를 들어, 위에서 소개한 prethreaded 동시성 서버가 main thread와 worker thread에 대한 간단한 state machine을 가진 이벤트 드리븐 서버이다. main thread는 두 개의 상태("connection 요청을 기다리는 상태"와 "버퍼 슬롯이 이용 가능해지기를 기다리는 상태"), 두 개의 I/O 이벤트("connection 요청이 도착함"와 "버퍼 슬롯이 이용 가능해짐"), 두 개의 transition("connection 요청 받기"와 "버퍼 아이템 넣기")를 가진다. 각각의 worker thread는 하나의 상태("이용 가능한 버퍼 아이템을 기다리는 상태")와 하나의 I/O 이벤트("버퍼 아이템이 이용 가능해짐"), 그리고 하나의 transition("버퍼 아이템 제거하기")를 가진다.
6. 병렬성을 위해 스레드 사용하기
지금까지의 동시성 논의에서 우리는 동시성 스레드가 단일 프로세서 시스템에서 실행되는 상황을 가정했다. 하지만 대부분의 현대 시스템은 멀티 코어 프로세서를 가지고 있다. 동시성 프로그램은 종종 이런 멀티 코어 프로세서에서 더 빠르게 실행된다. 왜냐하면 커널이 단일 프로세서에서 동시 스레드들을 순차적으로 스케줄링하기보다 멀티 코어에서 동시 스레드를 병렬적으로 스케줄링하기 때문이다. 이러한 병렬성을 사용하는 것은 바쁜 웹 서버, 데이터베이스 서버 그리고 큰 과학 코드에 중요하며 웹 브라우저, 스프레드시트, 문서 프로세서와 같은 주류 애플리케이션에서도 점점 중요해지고 있다.
다음은 순차적, 동시성, 병렬 프로그램의 집합 관계를 보여준다.
순차적 프로그램은 단일 논리 흐름으로 작성된다. 동시성 서버는 여러 개의 동시 흐름으로 작성된다. 병렬 프로그램은 여러 개의 프로세서에서 실행되는 동시성 프로그램이다. 따라서 병렬 프로그램은 동시성 프로그램의 하위 집합이다.
병렬 프로그램의 자세한 내용은 우리의 범위를 넘어서지만 몇 가지 간단한 예시 프로그램을 살펴보면 병렬 프로그램의 중요한 측면들을 이해하는 데 도움이 될 것이다. 예를 들어 우리가 정수의 순열인 0, ..., n - 1을 병렬적으로 더한다고 생각해보자. 여러 개의 스레드에게 일을 할당하는 가장 간단한 접근은 순열을 t 개의 서로소 영역으로 나눈 다음에 t 개의 스레드에게 각각의 영역을 계산하도록 하는 것이다. 단순하게 가기 위해 n이 t의 배수라고 해보자. 그래서 각 영역은 n / t 개의 요소를 더하게 되는 것이다. 여러 개의 스레드들이 할당받은 영역을 병렬적으로 작업할 수 있는 몇 가지 방법을 살펴보겠다.
가장 간단한 방법은 mutex로 보호되는 공유 전역 변수에 스레드들이 계산 결과를 더하는 것이다. 다음 코드가 그 예를 보여준다.
#include "csapp.h"
#define MAXTHREADS 32
void *sum_mutex(void *vargp); /* Thread routine */
/* Global shared variables */
long gsum = 0; /* Global sum */
long nelems_per_thread; /* Number of elements to sum */
sem_t mutex; /* Mutex to protect global sum */
int main(int argc, char **argv)
{
long i, nelems, log_nelems, nthreads, myid[MAXTHREADS];
pthread_t tid[MAXTHREADS];
/* Get input arguments */
if (argc != 3) {
printf("Usage: %s <nthreads> <log_nelems>\n", argv[0]);
exit(0);
}
nthreads = atoi(argv[1]);
log_nelems = atoi(argv[2]);
nelems = (1L << log_nelems);
/* Check input arguments */
if ((nelems % nthreads) != 0 || (log_nelems > 31)) {
printf("Error: invalid nelems\n");
exit(0);
}
nelems_per_thread = nelems / nthreads;
sem_init(&mutex, 0, 1);
/* Create peer threads and wait for them to finish */
for (i = 0; i < nthreads; i++) {
myid[i] = i;
Pthread_create(&tid[i], NULL, sum_mutex, &myid[i]);
}
for (i = 0; i < nthreads; i++)
Pthread_join(tid[i], NULL);
/* Check final answer */
if (gsum != (nelems * (nelems-1))/2)
printf("Error: result=%ld\n", gsum);
exit(0);
}
/* Thread routine for psum-mutex.c */
void *sum_mutex(void *vargp)
{
long myid = *((long *)vargp); /* Extract the thread ID */
long start = myid * nelems_per_thread; /* Start element index */
long end = start + nelems_per_thread; /* End element index */
long i;
for (i = start; i < end; i++) {
P(&mutex);
gsum += i;
V(&mutex);
}
return NULL;
}
메인 스레드는 peer thread에게 고유한 스레드 아이디 역할을 하는 작은 정수를 전달한다. 각 peer thread는 자신의 스레드 아이디를 이용하여 어느 부분을 작업해야 하는지를 결정한다.이렇게 peer thread에게 고유한 스레드 아이디를 전달하는 방법은 많은 병렬 애플리케이션에서 사용하는 일반적인 기술이다.peer thread가 종료되면 전역 변수 gsum은 최종 결과를 얻게 된다. 메인 스레드는 이 결과를 검증한다. peer thread는 공유 전역 변수 gsum을 업데이트할 때마다 P와 V mutex 연산으로 이를 보호한다.
그런데 우리가 psum-mutex를 4 코어 시스템에서 n = 2^31 을 전달하여 실행시키고 스레드의 수별로 실행 시간을 (초 단위로) 측정해보면 놀라운 결과가 나타난다.
하나의 스레드에서 순차적으로 실행될 때 극도로 느릴 뿐만 아니라 여러 개의 스레드에서 병렬적으로 실행될 때 매우 느려진다. 코어를 늘릴수록 성능은 더 안 좋아진다. 이런 결과의 이유는 동기화 연산인 P와 V가 단일 메모리를 업데이트하는 것과 비교했을 때 매우 비싼 연산이기 때문이다. 이는 병렬 프로그램과 관련해 중요한 교훈을 준다. 동기화 오베허드는 비싸기 때문에 가능하다면 피해야 한다. 만약 피하는 것이 불가능하다면 오버헤드는 그만큼 유용한 연산으로 상환되어야 한다.
동기화를 피할 수 있는 한 가지 방법은 peer thread가 부분 합을 다른 스레드와 공유되지 않는 사적인 변수에 저장하게 하는 것이다. 다음 코드가 이를 보여준다.
#include "csapp.h"
#define MAXTHREADS 32
void *sum_array(void *vargp); /* Thread routine */
/* Global shared variables */
long psum[MAXTHREADS]; /* Partial sum computed by each thread */
long nelems_per_thread; /* Number of elements summed by each thread */
int main(int argc, char **argv)
{
long i, nelems, log_nelems, nthreads, myid[MAXTHREADS], result = 0;
pthread_t tid[MAXTHREADS];
/* Get input arguments */
if (argc != 3) {
printf("Usage: %s <nthreads> <log_nelems>\n", argv[0]);
exit(0);
}
nthreads = atoi(argv[1]);
log_nelems = atoi(argv[2]);
nelems = (1L << log_nelems);
/* Check input arguments */
if ((nelems % nthreads) != 0 || (log_nelems > 31)) {
printf("Error: invalid nelems\n");
exit(0);
}
nelems_per_thread = nelems / nthreads;
/* Create peer threads and wait for them to finish */
for (i = 0; i < nthreads; i++) {
myid[i] = i;
Pthread_create(&tid[i], NULL, sum_array, &myid[i]);
}
for (i = 0; i < nthreads; i++)
Pthread_join(tid[i], NULL);
/* Add up the partial sums computed by each thread */
for (i = 0; i < nthreads; i++)
result += psum[i];
/* Check final answer */
if (result != (nelems * (nelems-1))/2)
printf("Error: result=%ld\n", result);
exit(0);
}
/* Thread routine for psum-array.c */
void *sum_array(void *vargp)
{
long myid = *((long *)vargp); /* Extract the thread ID */
long start = myid * nelems_per_thread; /* Start element index */
long end = start + nelems_per_thread; /* End element index */
long i;
for (i = start; i < end; i++) {
psum[myid] += i;
}
return NULL;
}
메인 스레드는 전역 배열 psum을 정의하고 각 스레드 i는 부분 합을 psum[i]에 저장한다. 각 peer thread는 고유한 메모리 위치에 업데이트를 하기 때문에 이를 mutex로 보호할 필요가 없다. 메인 스레드가 모든 자식 프로세스들이 끝나기를 기다릴 때만 동기화가 필수적이다. peer thread가 모두 종료되면 메인 스레드는 psum 배열의 요소를 모두 합하여 최종 결과를 얻는다.
psum-array를 4 코어 시스템에서 실행시키면 psum-mutex보다 빠르게 실행되는 것을 볼 수 있다.
5장에서 불필요한 메모리 참조를 제거하기 위해 지역 변수를 잘 사용하는 방법을 배웠다. 이를 이 프로그램에 적용해보면 peer thread가 부분 합을 전역 변수가 아닌 지역 변수에 저장하게 할 수 있다. 이를 적용한 코드는 아래과 같으며 4 코어 머신에서 psum-local을 실행시키면 실행 시간은 또 한 번 줄어든다.
#include "csapp.h"
#define MAXTHREADS 32
void *sum_local(void *vargp); /* Thread routine */
/* Global shared variables */
long psum[MAXTHREADS]; /* Partial sum computed by each thread */
long nelems_per_thread; /* Number of elements summed by each thread */
int main(int argc, char **argv)
{
long i, nelems, log_nelems, nthreads, myid[MAXTHREADS], result = 0;
pthread_t tid[MAXTHREADS];
/* Get input arguments */
if (argc != 3) {
printf("Usage: %s <nthreads> <log_nelems>\n", argv[0]);
exit(0);
}
nthreads = atoi(argv[1]);
log_nelems = atoi(argv[2]);
nelems = (1L << log_nelems);
/* Check input arguments */
if ((nelems % nthreads) != 0 || (log_nelems > 31)) {
printf("Error: invalid nelems\n");
exit(0);
}
nelems_per_thread = nelems / nthreads;
/* Create peer threads and wait for them to finish */
for (i = 0; i < nthreads; i++) {
myid[i] = i;
Pthread_create(&tid[i], NULL, sum_local, &myid[i]);
}
for (i = 0; i < nthreads; i++)
Pthread_join(tid[i], NULL);
/* Add up the partial sums computed by each thread */
for (i = 0; i < nthreads; i++)
result += psum[i];
/* Check final answer */
if (result != (nelems * (nelems-1))/2)
printf("Error: result=%ld\n", result);
exit(0);
}
/* Thread routine for psum-local.c */
void *sum_local(void *vargp)
{
long myid = *((long *)vargp); /* Extract the thread ID */
long start = myid * nelems_per_thread; /* Start element index */
long end = start + nelems_per_thread; /* End element index */
long i, sum = 0;
for (i = start; i < end; i++) {
sum += i;
}
psum[myid] = sum;
return NULL;
}
여기서 얻어가야 하는 중요한 교훈은 병렬 프로그램을 작성하는 것은 매우 까다롭다는 것이다. 코드의 작은 변화로도 성능에 큰 영향을 줄 수 있다.
병렬 프로그램의 성능 특징
다음은 psum-local 프로그램의 스레드 수별 총 실행 시간을 보여준다.
각 케이스에서 프로그램은 4 코어에서 실행되고 n = 2^31 요소들의 순열을 합한다. 도표를 보면 4 스레드까지는 스레드 수를 늘릴수록 실행 시간이 감소하지만 스레드 수를 더 늘리면 미세하게 실행 시간이 늘어나기 시작한다.
이상적인 케이스에서 우리는 코어의 수에 비례하게 실행 시간이 감소되는 것을 기대할 것이다. 즉, 스레드 수를 두 배로 늘리면 실행 시간이 절반이 되기를 기대할 것이다. 이는 t > 4 가 될때까지, 4개의 코어가 하나 이상의 스레드를 실행시키느라 바빴던 그때까지는 사실이었다. 그런데 실행 시간은 스레드 수를 늘렸을 때 더 늘어나는데 이는 같은 코어에서 여러 개의 스레드를 컨텍스트 스위칭하는 것의 오버헤드 때문이다. 이런 이유를 병렬 프로그램은 각 코어에서 하나의 스레드만 실행시키도록 작성되곤 한다.
비록 절대 실행 시간이 프로그램의 성능을 평가하는 궁극의 척도이지만 병렬 프로그램이 잠재적 병렬성을 얼마나 잘 활용하는지를 보여줄 수 있는 다른 유용한 상대 척도가 있다.
병렬 프로그램의 speedup은 일반적으로 다음과 같이 정의된다. 이 식은 strong scaling이라고 불리기도 한다.
Sp = T1 / Tp
p는 프로세서 코어의 수이다. Tk는 k 개의 코어에서의 실행 시간이다. T1이 순차 프로그램의 실행시간이라면 Sp는 absolute speedup이라고 불린다. T1이 하나의 코어에서 실행되는 병렬 프로그램의 실행 시간이라면 Sp는 relative speedup이라고 불린다. absolute speedup은 relative speedup보다 더 병렬성의 이점을 잘 보여주는 척도이다. 병렬 프로그램은 종종 동기화 오버헤드라는 문제를 겪는데 이는 단일 프로세서에서도 마찬가지이며 이러한 오버헤드는 인공적으로 relative speedup 숫자를 증가시킨다. 왜냐하면 동기화로 인해 전체 실행 시간이 증가하면 속도 향상을 계산할 때 분자가 커지기 때문이다.
한편 absolute speedup은 relative speedup보다 측정하기 어렵다. 왜냐하면 absolute speedup을 측정하려면 프로그램의 두 가지 버전이 필요하기 때문이다. 복잡한 병렬 코드의 경우 별개의 순차 버전을 만드는 것이 불가능할 수도 있다. 왜냐하면 코드가 너무 복잡하거나 소스 코드가 이용 가능하지 않기 때문이다.
관련 척도로 효율성 efficiancy가 있는데 이는 다음과 같이 정의된다.
Ep = Sp / p = T1 / pTp
효율성은 일반적으로 퍼센테이지로 보고된다. 효율성은 병렬성으로 인한 오베허드의 척도이다. 높은 효율성을 가진 프로그램은 낮은 효율성을 가진 프로그램과 비교해서 유용한 일을 하는 데 더 많은 시간을 소요하고 다른 프로그램과 동기화하고 소통하는 데 시간을 덜 소요한다.
우리 프로그램은 90%가 넘는 높은 효율성을 보여주는데 이는 프로그램이 병렬화하기 간단했기 때문에 가능했던 것이고 실제에서는 이렇게 하기 쉽지 않다. 병렬 프로그래밍은 수십 년동안 활발히 연구되어 오고 있는 분야이다. 몇 년마다 코어 수가 배가 되는 상용 멀티 코어 머신의 출현으로 병렬 프로그램은 더더욱 어려워지고 딥해지고 활발히 연구되고 있다.
speedup에 대한 또 다른 관점으로 weak scaling이 있다. 이는 프로세서의 수와 함께 문제 수를 증가시킨다. 그래서 각 프로세서에서 수행되는 일의 양은 프로세서의 수가 증가해도 고정이다. 이 공식으로 speedup과 효율성은 단위 시간당 성취되는 총 일의 양으로 표현된다. 예를 들어, 프로세서의 수를 두 배로 만들고 시간당 작업량을 두 배로 만들 수 있다면 우리는 그에 비례하는 speedup과 100%의 효율성을 얻을 수 있다.
weak scaling은 종종 strong scaling보다 더 실제에 가까운 척도이다. 왜냐하면 이는 우리가 더 많은 작업을 할 때 더 큰 머신을 쓰고자 한다는 것을 반영하기 때문이다. 이는 특히 과학 코드의 경우에 그렇다. 과학 코드에서 문제의 크기는 쉽게 증가하고 큰 문제 크기가 nature에 대해 더 나은 예측으로 이어지기 때문이다. 하지만 사이즈가 쉽게 증가하지 않는 애플리케이션도 있다. 이런 애플리케이션의 경우 strong scaling이 더 적합하다. 예를 들어, 실시간 시그널 프로세싱 애플리케이션에 의해 수행되는 작업량은 시그널을 생성하는 물리 센서의 속성에 의해 결정된다. 전체 작업량을 바꾸려면 다른 물리 센서를 이용해야 하는데 이는 실행 가능하지 않거나 필수적이지 않을 수 있다. 이런 애플리케이션의 경우 우리는 고정된 작업량을 가능한 빨리 성취하기 위해 병렬성을 이용하고 싶을 수 있다.
'Computer System > CSAPP' 카테고리의 다른 글
| [CSAPP] 12장 동시성 프로그래밍 (1/3) [1] Process [2] I/O Multiplexing (0) | 2025.02.08 |
|---|---|
| [CSAPP] 8장 예외적인 제어 흐름 (4/4) Signal, Nonlocal Jump (0) | 2025.01.22 |
| [CSAPP] 8장 예외적인 제어 플로우 (3/4) Process Control (1) | 2025.01.22 |
| [CSAPP] 8장 예외적인 제어 플로우 (2/4) Process (0) | 2025.01.19 |
| [CSAPP] 8장 예외적인 제어 플로우 (1/4) Exception (0) | 2025.01.17 |