CSAPP(12) - Concurrent Programming

동시성은 여러 레벨의 컴퓨터 시스템에서 나타난다.

• 하드웨어 예외 핸들러, 프로세스, 리눅스 시그널 핸들러 등
• 지금까지는 os 커널이 주로 처리했지만, 응용 프로그램에서도 중요하다.
  • 느린 입출력 장치에 접근할 때 다른 프로세스가 CPU를 사용할 수 있다.
  • 유저와 상호작용 시 여러 태스크를 동시에 처리한다.
    • 유저가 액션할 때마다 별도의 동시 논리 흐름이 생성된다.
  • 작업을 연기하여 지연시간을 감소시킬 수 있다.
    • 동적 할당자는 각각의 free명령을 연기하여 한번에 처리한다.
  • 여러 네트워크 클라이언트를 제공한다.
    • 동시성 서버는 각 클라이언트별로 별도의 논리 흐름을 생성한다.
  • 멀티 코어 머신에서 병렬 연산

현대 os는 동시성 프로그램을 만들기 위한 3가지의 기본 접근방식을 제공한다.

• Processes
  • 각 논리 제어 흐름은 커널에 의해 계획되고 유지된다.
  • 프로세스는 별도의 가상 주소 공간을 갖기에, 논리 흐름간 통신하려면 inter-process communication(IPC) 를 사용해야 한다.
• I/O muiltiplexing
  • 애플리케이션이 단일 프로세스에서 명시적으로 자신의 논리 흐름을 계획한다.
  • 상태 머신으로 모델링되었다.
    • 파일 서술자에 도착하는 데이터의 결과에 따라 상태가 전환한다.
  • 프로그램이 단일 프로세스이므로 모든 흐름은 같은 주소 공간을 공유한다.
• Threads
  • 단일 프로세스에서 실행되고 커널에 의해 계획되는 논리 흐름.
  • 프로세스처럼 커널에 의해 계획됨 + 입출력 멀티플렉싱처럼 동일한 가상 주소 공간을 사용함.

1. Concurrent Programming with Processes

fork, exec, waitpid 함수를 이용하여 동시성 프로그램을 쉽게 만들 수 있다.

• 동시성 서버는 부모 프로세스에서 클라이언트 연결 요청을 받아서 각 클라이언트별로 자식 프로세스를 만든다.

1. Server accepts connection request from client
2. Server forks a child process to service the client
   1. 부모와 자식 프로세스가 동일한 서술자를 가지므로 부모는 연결된 서술자를 닫아야 한다.
3. Server accepts another connection request
4. Server forks another child to service the new client.

1.1. A concurrent Server Based on Process

• 서버는 오랫동안 실행된다. 때문에 좀비 자식 프로세스를 회수할 SIGCHLD 핸들러를 포함해야 한다.
• 부모와 자식 프로세스는 각자의 connfd를 닫아야 한다.
• 소켓의 파일 테이블 엔트리 내 참조 카운트 때문에, 클라이언트의 커넥션은 부모와 자식 모두의 connfd가 닫힐 때까지 종료되지 않는다.

#include "csaap.h"
void echo(int connfd);

void sigchld_handler(int sig)
{
  while (waitpid(-1, 9, WHOHANG) > 0)
    ;
  return;
}

int main(int argc, char **argv)
{
  int listenfd, connfd;
  socklen_t clientlen;
  struct sockaddr_storage clientaddr;
  
  if (argc != 2) {
    fprintf(stderr, "usage: %s <port>\n", argv[0]);
    exit(0);
  }

  Signal(SIGCHLD, sigchld_handler);
  listenfd = Open_listenfd(argv[1]); // 인자로 받은 포트로 listen

  while(1) {
    clientlen = sizeof(struct sockaddr_storage);
    connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
    if (Fork() == 0) {
      Close(listenfd); // 자식은 listen 소켓을 닫는다
      echo(connfd);    // 자식은 클라이언트에게 서비스한다.
      Close(connfd);   // 자식은 클라이언트와의 커넥션을 닫는다.
      exit(0);         // 자식 exit
    }
    Close(connfd);     // 부모는 연결된 소켓을 닫는다. (중요!)
  }
}

1.2. Pros and Cons of Processes

프로세스는 부모 자식 간 공유하는 상태 정보가 명료하다.

• 파일 테이블은 공유되고 유저 주소 공간은 공유되지 않는다.
• 프로세스 간 별도의 주소 공간을 가진다
  • 장점 : 메모리 공간을 침범하지 않는다.
  • 단점
    • 상태 정보를 공유하기 위해서는 명시적인 IPC(inter-process communication)이 필요하다.
    • 느리다. 프로세스 제어와 IPC의 오버헤드가 크기 때문.

2. Concurrent Programming with I/O multiplexing

대화형 명령을 응답해야 하는 에코 서버는 두개의 독립적인 입출력 이벤트를 응답해야 한다.

1. 클라이언트의 커넥션 요청
2. 유저의 명령줄 타이핑

만약 1 요청을 accept로 기다린다면, 서버는 2에 응답할 수 없다. 만약 read로 2를 기다린다면, 서버는 1에 응답할 수 없다.

이를 해결하는 게 I/O multiplexing이다.

• select 함수를 사용해서 커널에게 프로세스를 일시중지하고
• 한 개 이상의 입출력 이벤트가 발생하면 제어를 애플리케이션에게 돌려준다. 아래는 예시
  • 0, 4 서술자가 read 준비가 되면 제어 반환
  • 1, 2, 7 서술자가 write 준비가 되면 제어 반환
  • 입출력 이벤트 발생을 기다리다가 타임아웃

select함수는 서술자 집합을 조작한다.

• int select(int nfds, // 카디널리티
    fd_set *restrict readfds,  // 읽기 서술자 집합
    fd_set *restrict writefds, // 쓰기 서술자 집합
    fd_set *restrict errorfds, // 에러 서술자 집합
    struct timeval *restrict timeout // 타임아웃
    );
  

• 서술자 집합과 카디널리티를 파라미터로 받음.
• fdset중 하나라도 읽기 준비가 되었을 때까지 블락한다.

#include "csapp.h"
void echo(int connfd);
void command(void);

int main(int argc, char **argv)
{
  int listenfd, connfd;
  socklen_t clientlen;
  struct sockaddr_storage clientaddr;
  fd_set read_set, ready_set;

  if (argc != 2) {
    fprintf(stderr, "usage: %s <port>\n", argv[0]);
    exit(0);
  }
  listenfd = Open_listenfd(argv[1]);

  FD_ZERO(&read_set); // read set 초기화
  FD_SET(STDIN_FILENO, &read_set) // read set 에 표준입력 추가
  FD_SET(listenfd, &read_set);  // read set에 listen 파일서술자 추가

  while (1) {
    ready_set = read_set;
    Select(listenfd+1, &ready_set, NULL, NULL, NULL); // listen 서술자나 표준입력 서술자가 읽기 준비될 때까지 block
    if (FD_ISSET(STDIN_FILENO, &ready_set))
      command(); // 표준입력으로부터 명령줄 읽기
    if (FD_ISSET(listenfd, &ready_set)) {
      clientlen = sizeof(struct sockaddr_storage);
      connfd = Accept(listenfd, (SA *)&clientaddr, &clientlen);
      echo(connfd); // EOF까지 클라이언트 입력을 echo
      Close(connfd);
    }
  }
}

void command(void) {
  char buf[MAXLINE];
  if (!Fgets(buf, MAXLINE, stdin))
    exit(0); // EOF
  printf("%s", buf); // 입력 명령 처리
}

위 예제의 문제

• 한번 클라이언트에 커넥트되면 커넥션 종료 시까지 echo를 계속한다. 그동안 command()를 할 수 없다.
• 더 나은 접근은 루프 돌 때마다 echo를 최대 하나의 라인만 하도록 하는 것.

2.1. A conncurent Event-Driven Server Based on I/O Multiplexing

입출력 멀티플렉싱은 동시성 이벤트 프로그램의 기반이다.

• 논리 흐름을 상태 기계로 모델링한다. (오토마타 참고)
  • 상태 기계 : 상태, 입력 이벤트, 상태 전이의 집합
  • 각 전이는 (입력 상태, 입력 이벤트) 쌍을 출력 상태로 매핑한다.
  • self-loop는 동일한 입/출력 상태간의 전이다.
  • 방향성 그래프로 나타냄
    • 노드는 상태, 화살표는 전이, 화살표의 레이블은 입력 이벤트
  • 상태 기계는 초기 상태로 시작한다.
  • 각 입력 이벤트는 현재 상태에서 다음 상태로의 전이를 트리거한다.
• 동시성 입출력 멀티플렉싱 서버는 각 클라이언트 $k$ 에 대해 상태 기계 $s_{k}$를 생성한다.
• $s_{k}$를 연결된 서술자 $d_{k}$와 연관시킨다.
• State machine for a logical flow in a concurrent event-driven echo server.

#include "csapp.h"

typedef struct { // connected 서술자 풀
  int maxfd;  // read_set에서 최대 서술자
  fd_set read_set;  // 모든 활성화된 서술자 집합
  fd_set ready_set; // 읽기 준비된 서술자 집합
  int nready; // select에서 준비된 서술자 수
  int maxi; // High water index into client array
  int clientfd[FD_SETSIZE]; // 활성화된 서술자 집합
  rio_t clientrio[FD_SETSIZE]; // 활성화된 읽기 버퍼 집합
} pool;

int byte_cnt = 0; // 서버가 받은 전체 바이트 수

int main(int argc, char **argv)
{
  int listenfd, connfd;
  socklen_t clientlen;
  struct sockaddr_storage clientaddr;
  static pool pool;

  if (argc != 2) {
    fprintf(stderr, "usage: %s <port>\n", argv[0]);
    exit(0);
  }
  listenfd = Open_listenfd(argv[1]);
  init_pool(listenfd, &pool);

  while (1) {
    // listening / connected 서술자가 준비되기를 기다림
    pool.ready_set = pool.read_set;
    pool.nready = Select(pool.maxfd+1, &pool.ready_set, NULL, NULL, NULL);

    // listening 서술자가 준비되면 새로운 클라이언트를 풀에 추가한다
    if (FD_ISSET(listenfd, &pool.ready_set)) {
      clientlen = sizeof(struct sockaddr_storage);
      connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
      add_client(connfd, &pool);
    }

    // 준비된 connected 서술자로부터 읽은 텍스트 라인 echo
    check_clients(&pool);
  }
}

void init_pool(int listenfd, pool *p)
{
  // 초기에는 connected 서술자가 없다
  int i;
  p->maxi = -1;
  for (i=0; i< FD_SETSIZE; i++)
    p->clientfd[i] = -1;

  // 초기에 listenfd는 select read set 의 유일한 멤버
  p->maxfd = listenfd;
  FD_ZERO(&p->read_set);
  FD_SET(listenfd, &p->read_set);
}

void add_client(int connfd, pool *p)
{
  int i;
  p->nready--;
  for (i = 0; i < FD_SETSIZE; i++) // 가용 슬롯 찾는다
    if (p->clintfd[i] < 0) {
      // connected 서술자를 풀에 추가
      p->clientfd[i] == connfd;
      Rio_readinitb(&p->clientrio[i], connfd)

      // 서술자를 서술자 집합에 추가
      FD_SET(connfd, &p->read_set);

      // 최대 서술자와 pool high water mark 갱신
      if (connfd > p->maxfd)
        p->maxfd = connfd;
      if (i > p->maxi)
        p->maxi = i;
      break;
    }
  if (i == FD_SETSIZE) // 빈 슬롯이 없을 때
    app_error("add client error: Too many clients");
}

void check_clients(pool *p)
{
  int i, connfd, n;
  char buf[MAXLINE];
  rio_t rio;

  for (i = 0; (i <= p->maxi) && (p->nready > 0); i++) {
    connfd = p->clientfd[i];
    rio = p->clientrio[i];

    // 서술자가 준비되면, echo
    if ((connfd> 0) && (FD_ISSET(connfd, &p->ready_set))) {
      p->nready--;
      if ((n = Rio_readlineb(&rio, buf, MAXLINE)) != 0) {
        byte_cnt += n;
        printf("Server received %d (%d total) bytes on fd %d\n", n, byte_cnt, connfd);
        Rio_writen(connfd, buf, n);
      }
      // EOF 감지. 풀에서 서술자 제거
      else {
        Close(connfd);
        FD_CLR(connfd, &p->read_set);
        p->clientfd[i] = -1;
      }
    }
  }
}

유한 상태 모델 용어로

• select 함수는 입력 이벤트를 감지
• add_client 함수는 새로운 논리 흐름(상태 기계)를 생성
• check_clients 함수는
  • 입력 라인을 echo하는 상태 전이를 수행
  • 클라이언트가 텍스트 라인 전송을 마치면 상태 기계를 제거

2.2 Pros and Cons of I/O multiplexing

장점

• 이벤트 기반 설계는 프로세스 기반 설계보다 프로그램을 동작을 잘 제어할 수 있다.
  • eg. 프로세스 기반에서 특정 사용자에게만 다른 동작을 하는 서버를 구현하기 어렵다.
• 단일 프로세스에서 동작하므로
  • 논리 흐름 간 데이터 공유가 쉽다.
  • 디버깅이 쉽다
• 컨텍스트 스위치가 없으므로 프로세스 기반보다 효율적이다.

단점

• 높은 코딩 복잡도
• 멀티 코어 프로세서를 제대로 활용할 수 없다.

3. Concurrent Programming with Threads

각 스레드는 고유의 스레드 컨텍스트를 가진다.

• 고유 정수 스레드 ID
• 스택
• 스택 포인터
• 프로그램 카운터
• 일반 목적 레지스터
• 조건 코드
• 프로세스 내 모든 스레드는 전체 가상 주소 공간을 공유한다.

스레드 기반 논리 흐름은

• 프로세스처럼 스레드는 커널에 의해 자동 스케줄링된다.
• 입출력 멀티플렉싱처럼 스레드는 단일 프로세스의 컨텍스트에서 실행되고 code, data, heap, 공유 라이브러리, open file을 공유한다.

3.1. Thread Execution Model

멀티스레드 실행 모델은 멀티프로세스와 유사하다.

• 프로세스는 메인 스레드라는 단일 스레드에서 시작한다.
• 메인 스레드는 peer thread를 생성한다.
  • 두 스레드는 동시 실행된다.

멀티 프로세싱보다 컨텍스트 스위치가 빠르며, 부모-자식 계층 구조를 갖지 않는다.

• 메인 스레드는 프로세스의 첫번째 스레드이다. 부모가 아니다.
• 스레드는 peer 중 어떤 것이라도 죽이거나 종료시까지 대기할 수 있다.
• 각 스레드는 동일한 공유 데이터를 읽고 쓸 수 있다.

3.2. Posix Threads

posix threads(Pthreads)는 C프로그램이 스레드를 조작하는 표준 인터페이스다.

• Creating Threads
  • pthread_create
• Terminating Threads
  • 암시적 : 최고 레벨 스레드 루틴이 반환할 때 스레드는 종료한다.
  • 명시적
    • pthread_exit 를 메인 스레드가 호출할 때 다른 피어 스레드의 종료를 대기하고 메인 스레드를 종료한다.
    • 피어 스레드가 리눅스 exit 함수를 호출하면 프로세스와 모든 스레드를 종료한다.
    • 다른 피어 스레드가 pthread_cancel 호출하여 현재 스레드를 종료한다.
• Reaping Terminated Threads
  • pthread_join은 특정 스레드가 종료될때까지 블락한 뒤 메모리 자원을 회수한다.
• Detaching Threads
  • joinable 스레드와 달리 detached 스레드는 다른 스레드가 죽이거나 회수할 수 없다.
  • 다른 스레드가 명시적으로 회수하지 않더라도 자동으로 스택 메모리 정리된다.
  • 메모리 릭을 막기 위해 각 joinable 스레드는 명시적으로 회수되거나 pthread_detach 함수로 detach되어야 한다.
  • eg) 웹서버에서 각 스레드는 피어 스레드의 자원 회수를 위해 불필요하게 기다리게 된다. detach하게 되면 스레드 종료를 기다릴 필요가 없다.
• Initializing Threads
  • 스레드 루틴의 상태를 초기화한다.
  • pthread_once는 동적으로 여러 스레드가 공유하는 전역 변수를 초기화할 때 유용하다.

3.8. A Concurrent Server Based on Threads

#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;
}

• 어떻게 피어 스레드에 connected 서술자를 전달하는가
  • pthread_create 인자에 서술자의 포인터를 전달한다.
  • 피어 스레드는 포인터를 역참조 후 지역변수로 할당한다.
• 피어 스레드의 할당과 메인 스레드의 accept간 race 발생할 수 있기에 잘못되었다.
  • 할당이 다음 aceept이후에 완료된다면, 피어 스레드의 connfd 변수는 다음 커넥션의 서술자를 갖게 된다.
  • 두 스레드가 동일한 서술자에 입출력하게 됨
  • 경합을 회피하기 위해 고유의 동적 할당 메모리 블록에서 각 커넥션 서술자를 반환받게 해야 한다.(Malloc)
• 스레드 루틴의 메모리 누수를 피하는 방법
  • 각 스레드를 detach해야 한다.
  • 동적할당한 메모리 블락을 해제해야 한다.

4. Shared Vairables in Threaded Programs

스레드의 매력 중 하나는 동일 변수를 공유하는 것. C 프로그램 변수의 공유 여부를 이해하기 위해서는 아래를 알아야 함.

• 스레드의 기반 메모리 모델은 무엇인가?
• 변수의 인스턴스는 어떻게 메모리에 매핑되는가?
• 얼마나 많은 스레드가 이 인스턴스를 참조하는가?

4.1. Thread Memory Model

각 스레드는 다음을 공유한다.

• 전체 유저 가상 주소 공간
  • code, data, heap 공유 라이브러리 code/data 영역
• 열린 파일 집합

각 스레드는 다음을 공유하지 않는다.

• 스레드 ID, 스택, 스택 포인터, 프로그램 카운터, 조건 코드, 일반 목적 레지스터 값

구조적으로 한 스레드가 다른 스레드의 레지스터 값을 읽거나 쓸 수 없다. 공유 가상 메모리에는 접근 가능하다.

• 한 스레드가 메모리 공간을 수정하면 다른 스레드들은 변경을 볼 수 있다.

스택들은 가상 주소 공간의 스택 공간에 있다.

• 스레드 스택은 다른 스레드로부터 보호될 수 없다.
• 따라서 다른 스레드의 스택의 포인터를 얻으면 그 스택에 접근 가능하다.

4.2. Mapping Variables to Memory

• 전역 변수
  • 런타임에 각 전역 변수는 정확히 하나의 인스턴스로, 스레드가 참조한다.
• 지역 변수
  • 런타임에 각 스레드의 스택에는 고유의 지역 변수가 포함되어 있다.
• 지역 정적 변수
  • 정확히 하나의 인스턴스로, 스레드가 참조한다.

4.3. Shared Variabels

변수의 인스턴스 중 하나를 한 개 이상의 스레드가 참조하게 되면 공유 변수라고 한다.

5. Synchronizing Threads with Semaphores

공유 변수는 동기화 문제를 동반한다.

C 코드는 어셈블리 코드로 변경되어 명령을 하나씩 수행한다.

• Assembly code for the counter loop

로컬 스택 변수를 조작하는 명령이 아닌, 공유 변수를 조작하는 명령이 critical section이다.

• Safe and unsafe trajectories

5.2. Semaphoes

동시성 프로그래밍 창시자인 다익스트라는 동기화 문제를 해결하기 위해 특별한 변수인 세마포어를 제안했다.

• 음수가 아닌 정수값 전역 변수
• 두 가지 연산만 가능하다
  • $P(s)$ : $s$가 0이 아니면 s를 감소시키고 즉시 반환. s가 0이면 0이 아니게 될 때까지 스레드를 중지한다. 재시작되면 s를 감소시키고 반환한다.
  • $V(s)$ : s를 1 증가시킨다. P로 중단된 스레드들이 있다면 그 중 하나를 재시작한다.

상호 배제를 위한 세마포어 사용

• 안전하지 않은 구역을 금지 구역(s =-1)으로 감싸서 상호 배제

• for (i = 0; i < niters; i++) {
    P(&mutex);
    cnt++;
    V(&mutex);
  }
  

5.4. Using Semaphores to Schedule Shared Resources

세마포어는 상호 배제 이외에 공유 자원의 접근을 스케줄하는데도 쓰인다.

• 스레드는 다른 스레드에 특정 조건이 변경되었다는 것을 알리기 위해 세마포어를 사용한다

Producer-Consumer Problem

• 생산자 스레드는 버퍼에 아이템을 넣는다.
• 소비자 스레드는 버퍼에서 아이템을 가져온다.
• 버퍼 접근은 상호 배제여야 한다.
• 버퍼 접근을 스케줄링할 필요도 있다.
  • 버퍼가 풀이면 생산자는 기다린다
  • 버퍼가 비었으면 소비자는 기다린다.

Readers-Writers Problem

• 상호 배제 문제의 일반화
• 동시성 스레드의 집합이 공유 객제에 접근한다. 어떤 스레드는 객체를 읽고 나머지는 수정한다.
• 쓰기는 독점 접근해야 한다.
• 읽기는 다른 읽기들과 객체를 무제한 공유할 수 있다.
• first readers-writers problem
  • 쓰기가 기다리는 중이라도 읽기는 기다리지 않는다.
  • 쓰기 기아 현상
  • 읽기 선호
• second readers-writers problem
  • 쓰기 뒤에 도착한 읽기는 기다려야 한다.
  • 쓰기 선호

5.5. A Concurrent Server Based on Prethreading

prethreaded 동시성 서버 구조

• 마스터 스레드는 클라이언트로부터 커넥션을 받아 커넥션 서술자를 버퍼에 넣는다.
• 미리 생성해둔 워커 스레드가 반복해서 버퍼에서 연결된 서술자를 제거하고 처리한다.
• 생산자-소비자 모델

#include "csapp.h"
#include "sbuf.h"
#define NTHREADS 4
#define SBUFSIZE 16

void echo_cnt(int connfd);
void *thread(void *vargp);

sbuf_t sbuf; // connected 서술자 공유 버퍼

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);
  for(i = 0; i < NTHREADS; i++) // 워커 스레드 생성
    Pthread_create(&tid, NULL, thread, NULL);

  while (1) {
    clientlen = sizeof(struct sockaddr_storage);
    connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
    sbuf_insert(&sbug, connfd); // 버퍼에 connfd 추가
  }
}

void *thread(void *vargp)
{
  Pthread_detach(pthread_self());
  while (1) {
    int connfd = sbuf_remove(&sbuf); // 버퍼에서 connfd 제거
    echo_cnt(connfd)
    CLose(connfd)
  }
}

6. Using Threads for Parallelism

모든 프로그램은 순차 프로그램과 동시 프로그램 두 개로 나뉘며, 병렬 프로그램은 동시 프로그램의 부분집합이다.

• 순차 프로그램은 단일 논리 흐름
• 동시 프로그램은 여러 동시성 흐름
• 병렬 프로그램은 여러 프로세서에서 실행되는 동시성 프로그램

[0:n-1]의 합을 병렬로 구하는 방법

1. 시퀀스를 t개의 파티션으로 나눈다.
2. 각 파티션을 다른 스레드가 처리한다.

뮤텍스로 보호되는 공유 전역 변수에 합을 저장하는 방법(psum-mutex)

• 멀티스레드 수를 증가시킬수록, 더 느리다
• 동기화 오버헤드는 비싸서 가능한 피해야 한다.

#include "csapp.h"
#define MAXTHREADS 32

void *sum_mutex(void *vargp); // 스레드 루틴

// 전역 공유 변수
long gsum = 0;  // 전역 합
long nelems_per_thread; // 합할 요소의 수
sem_t mutex;  // 전역 합 보호를 위한 뮤텍스

int main(int argc, char **argv)
{
  long i, nelems, log_nelems, nthreads, myid[MAXTHREADS];
  pthreads_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);
  nelems_per_thread = nelems / nthreads;
  sem_init(&mutex, 0, 1);

  // 피어 스레드를 생성하고 완료를 대기
  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);
}

void *sum_mutex(void *vargp)
{
  long myid = *((long *)vargp); //스레드 ID 추출
  long start = myid * nelems_per_thread; // 시작 요소 인덱스
  long end = start + nelems_per_thread; // 마지막 요소 인덱스
  long i;

  for (i = start; i < end; i++) {
    P(&mutex);
    gsum += i;
    V(&mutex);
  }
  return NULL;
}

각 스레드가 공유하지 않는 개인 배열만 처리하는 방법(psum-array)

• psum-mutex 보다 매우 빠르다.

void *sum_array(void *argp)
{
  long myid = *((long *)vargp);
  long start = myid * nelems_per_thread;
  long end = start + nelems_per_thread;
  long i;

  for (i = start; i < end; i++) {
    psum[myid] += i;
  }
  return NULL;
}

각 스레드가 지역변수에 부분합을 저장하는 방법

• 위 두개보다 빠르다.

void *sum_local(void *vargp)
{
  long myid = *((long *)vargp);
  long start = myid * nelems_per_thread;
  long end = start + nelems_per_thread;
  long i, sum = 0;

  for (i = start; i < end; i++) {
    sum += i;
  }
  psum[myid] = sum;
  return NULL;
}

병렬 프로그램 성능 특성화

• 한 코어에 여러 스레드가 실행되면 문맥 교환으로 인해 느려질 수 있다.
  • 때문에 자주 하나의 코어당 하나의 스레드가 수행되도록 작성된다.

내 생각

그럼에도 웹서버 등 프로그램에서는 코어보다 많은 수의 스레드를 생성하기도 하는데. 다음 이유가 아닐까 추측된다

• 코어 당 하나의 스레드라면 블락킹 I/O로 인해 스레드가 멈추고 코어가 놀게 됨. CPU 효율성이 감소된다.
  • 파이썬에서 멀티스레딩은 불가능한데, 단일 스레드에서 추상화된 스레드 라이브러리를 사용하면 입출력이 다수인 프로그램에서는 성능개선이 된다는 주장과 동일한 맥락
• 성능보다는 단위시간 당 더 많은 커넥션을 처리하기 위해
• 입출력이 아닌 CPU연산이 중심이 되는 로직이라면 다수의 스레드는 성능이 별로일 듯.

7. Other Concurrentcy Issues

7.1. Thread Safety

여러 동시성 스레드에서 반복적으로 호출하더라도 올바른 결과를 내는 함수를 thread-safe 라 한다.

thread-unsafe 함수

1. 공유 변수를 보호하지 않는 함수
2. 여러번의 호출 간 상태를 공유하는 함수
3. 정적 변수의 포인터를 반환하는 함수
4. thread-unsafe 함수를 호출하는 함수

7.2. Reentrancy

재입력 가능 함수는 공유 데이터를 참조하지 않는다.

• thread-safe 함수의 부분집합
• 동기화 연산이 없기에 재입력 불가능한 thread-safe 함수보다 일반적으로 효율적
• 함수의 모든 인자가 포인터가 아니고, 모든 참조가 로컬 스택 변수라면 명시적으로 재입력 가능하다.
• 함수의 인자가 포인터라면 암시적으로 재입력 가능한 함수다. 포인터가 가리키는 데이터가 비공유 변수여야 재입력 가능한 함수다.

7.5. Deadlocks

세마포어는 데드락을 유발할 수 있다.

Progress graph for a program that can deadlock.

• 프로그래머가 부정확하게 $P$, $V$ 연산을 배치하면 데드락에 걸릴 수 있다.
• 데드락은 예측 불가능하기에 특히 어려운 이슈다.

데드락 예방법

• Process graph for a deadlock-free program
• 뮤텍스 락 순서 규칙 : 각 스레드가 뮤텍스를 순서대로 얻고 역순으로 해제하면 데드락에서 안전하다

8. Summary

동시성 프로그램을 작성하는 세 가지 방법

• 프로세스
• 입출력 멀티플렉싱
• 스레드

프로세스를 이용한 동시성 처리

• 커널에 의해 자동 스케줄링됨
• 별도의 가상 주소 공간 가짐
  • 데이터 공유하기 위해서는 명시적 IPC가 필요함

입출력 멀티플렉싱

• 이벤트 기반 프로그램은 상태 기게로 모델링되는 동시 논리 흐름을 가짐
• 명시적인 스케줄링이 필요
• 단일 프로세스에서 실행됨
  • 데이터 공유가 쉽고 빠르다

스레드를 이용한 동시성 처리

• 위 두가지의 하이브리드
• 커널에 의해 자동 스케줄링
• 단일 프로세스에서 실행됨
  • 데이터 공유가 쉽고 빠르다.

공유 데이터 동기화

• 세마포어는 공유 데이터에 대한 상호 배제 접근을 제공한다
• 세마포어는 producer-consumer 시스템의 버퍼 접근, readers-writers 시스템의 공유 객체 접근을 스케줄링하는데도 쓰인다.

동시성 문제

• 스레드가 호출하는 함수들은 스레드 안전해야 한다.
• 반복가능한 함수는 스레드 안전 함수의 부분집합으로, 스레드간 데이터를 공유하지 않는다.
  • 반복불가능한 스레드 안전 함수보다 효율적이다. 공유 데이터 동기화가 필요없기 때문
• 경합
  • 프로그래머가 논리 흐름의 스케줄링을 부정확하게 가정할 때 발생
• 데드락
  • 논리 흐름이 절대 일어나지 않을 이벤트를 기다릴 때 발생