동시성과 병렬성
[동시성 프로그래밍]
이 포스트는 레퍼런스로 동시성 프로그래밍(OREILLY, 한빛미디어) 를 사용하고 있습니다.
프로세스
동시성과 병렬성 개념 이전에 프로세스란 무엇인가? 이 책에서 프로세스란 특정 시간에 일부만 존재하는(시간적인 넓이를 갖는) 개념 으로 소개하고 있다.
프로세스는 4가지 상태를 가질 수 있는데:
실행 전 상태: 계산 실행 전의 상태. 실행 상태로 전이 가능
실행 상태: 계산 실행중의 상태. 대기 또는 계산 종료 상태로 전이 가능
대기 상태: 계산을 일시적으로 정지한 상태. 실행 상태로 전이 가능
종료 상태: 계산을 종료한 상태
프로세스는 실행 이후에 실행 상태와 대기 상태 간을 전이하다가 종료될 수 있는데, 계속 실행되지 않고 대기 상태로 전이하게 되는 이유로 아래 세 가지가 있다.
데이터 도착을 기다리는 상황. 연산을 수행할 데이터가 아직 도착하지 않았다면 계산을 수행할 수 없다.
계산 리소스를 기다리는 상황. 계산에 필요한 리소스가 현재 충분하지 않은 경우 리소스가 반환되어 계산이 가능해지는 상황을 기다려야 한다.
타이머 등에 의해 자발적으로 대기 상태로 진입하는 경우. 이 경우 데이터와 리소스가 충분함에도 계산 조건(예: 시간)을 만족하지 않으면 대기 상태를 유지한다.
동시성
동시성이란 2개 이상의 프로세스가 동시에 계산을 진행하는 상태를 의미한다.
위 그림에서 $t_{0}$ 에서 $t_{1}$ 까지를 계산 중 상태 라고 정의한다.
계산 중 상태는 실행 상태 + 대기 상태, 즉 프로세스가 실행 시작 이후 종료되기까지의 시간이다.
따라서 이 계산 중인 시간이 겹치는 상황에서 동시에 실행되고 있다고 말할 수 있다. (개인적으로 실행과 계산 중의 개념이 다르기 때문에 동시에 실행한다는 표현이 헷갈릴 수 있다고 생각한다.)
책의 정의에선 동시를 아래와 같이 설명하고 있다.
동시: 시각 $t$에서 여러 프로세스 $p_{0} ... p_{n}$이 계산 중인 상태에 있을 때 프로세스 $p_{0} ... p_{n}$ 이 동시에 실행되고 있다고 한다.
따라서 위 그림에서 프로세스 A와 B는 $(t_{0}, t_{1})$에 동시에 실행되고 있는 것이다.
병렬성
동시성 프로그래밍 책에서 병렬성은 같은 시각에서 여러 프로세스가 동시에 계산을 실행하는 상태를 의미한다고 정의한다.
동시성과의 차이가 있다면 병렬성은 실행 상태가 겹치는 순간만을 포함한다. 대기 상태가 겹치거나, 하나가 실행 상태, 다른 하나가 대기 상태에 있는 것과 같은 상황은 포함되지 않는다.
병렬성에는 크게 세 가지 종류가 있는데
태스크 병렬성
데이터 병렬성
인스트럭션 레벨 병렬성 이 있다.
태스크 병렬성
앞에서 본 그림은 태스크 병렬성이다. 태스크 병렬성은 여러 태스크(프로세스)가 동시에 실행되는 것을 의미한다.
데이터 병렬성
데이터를 여러 개로 나눠서 병렬로 처리하는 방법이다.
이건 연산기가 한 개인 경우에서 수행되는 계산의 상황인데, 연산기가 4개라면 각각의 덧셈을 각각의 연산기에서 수행해서 더 빠르게 연산할 수 있다. 이를 벡터 연산 이라 한다.
이러한 벡터 연산은 CPU가 제공하는 벡터 연산 명령으로도 구현될 수 있지만 아까의 연산기 4개를 4개의 스레드로 실행해도 구현할 수 있다.
그런데 이것처럼 계산량이 적은 문제는 오히려 스레드를 생성하는 데에 들어가는 오버헤드로 인해 더 느려질 수 있다. (항상 좋은 것이 아니다!)
응답 속도와 처리량
계산속도에는
응답 속도
처리량 이라는 두 가지 척도로 계산할 수 있다. 정리하자면
응답 속도: 정의: 계산 시작부터 마칠 때까지의 시간 척도: CPU 클록 수, 소비 CPU 인스트럭션 수 -> 시간으로 표현 가능
처리량: 정의: 단위 시간당 실행 가능한 계산량
암달의 법칙
암달의 법칙이란 일부 처리의 병렬화가 전체적으로 고속화에 어느 정도 영향을 미치는지 예측하는 법칙이다.
수식으로는 1(1−P)+PN
로 나타낸다. (P: 전체 프로그램 중 병렬화 가능한 처리의 비율, N: 병렬화 수)
이 식은 병렬화를 위한 오버헤드가 없는 상태에서의 성능 향상률을 나타낸다.
이제 병렬화에 사용되는 오버헤드를 고려한다면
1H+(1−P)+PN 가 될 것이다.( H: 오버헤드의 응답 속도와 순차 실행했을 때 응답 속도의 비율)
이것을 산술적으로 계산하는 게 중요하다기보다는 병렬화 수를 바꿨을 때 얼마나 성능이 향상되는지를 확인할 수 있다는 것이다.
그래프로는
이렇게 나온다.
눈에 띄는 것은 P = 1.0 즉 전체 병렬화 가능한 처리인 경우 병렬화 수 N일 때 N만큼 빨라진다.
그러나 병렬화 불가능한 처리가 있는 경우 고속화 자체는 될지언정 그 배율이 작아진다는 것이다. 한마디로 늘린만큼 좋아지진 않는다.
인스트럭션 레벨 병렬성
인스트럭션 레벨 병렬성이란 CPU의 명령어 레벨에서의 병렬화이다.
주로 하드웨어나 컴파일러가 이것을 수행하게 되고 프로그래머가 여기까지 고려하는 것은 루프 전개나 데이터 프리패치 이외에는 흔치 않다.
그러나 대체로 컴파일러가 최적화를 수행하는 경우가 대부분이므로 컴파일러 설계가 아닌 이상 자주 볼 일은 많지 않다.
그런 이유로 파이프라인 처리 개념을 위주로 다루고 넘어가자.
파이프라인 처리
CPU의 명령 실행은 다음 5가지로 나눌 수 있다.
명령 읽기(IF)
명령 해석(ID)
실행(EX)
메모리 엑세스(MEM)
쓰기(WB)
11011(2+3 계산 후 addr[1]과 a 레지스터에 결과를 저장) 수행의 과정을 각각의 과정으로 나눠보면 위와 같이 시각화할 수 있다.
IF로 메모리상의 명령을 읽어 버킷에 명령을 저장한다.
ID: 버킷 내 명령을 해석한다.
2+3이 계산되고 5로 치환된다.
메모리 엑세스: addr[1]에 결과가 쓰인다.
쓰기: a 레지스터에 결과가 쓰인다.
의 과정인 것이다.
위는 간소화한 설명이지만 실제 파이프라인 처리에서도 각 클록에서 처리를 실행하는 단계 이외에는 아무것도 수행하지 않는다. 자기가 일하는 시간 외에는 놀고 있는 것이다. 이들을 놀지 않게 두려면 여러 인스트럭션을 병렬로 주면 되는 것이다.
이상적인 상황에서 단순 계산을 하자면 처리량은 파이프라인 수의 배율만큼(위에서는 5개니 5배만큼.) 향상되겠지만 현실에서는 데이터 의존 관계 등의 조건으로 인해 5배까지는 향상되지 않는 경우가 대부분이다.
이렇게 데이터 의존 관계 등으로 인스트럭션 레벨에서 병렬 실행할 수 없는 상태를 파이프라인 해저드라고 한다.
따라서 컴파일러를 만들어야한다면 이러한 파이프라인 해저드까지 처리를 해야하는 것이다. 그러나 컴파일러를 여기서 만들지는 않으므로...
파이프라인 해저드의 종류
3가지 종류가 있는데:
구조 해저드 하드웨어적으로 병렬 실행할 수 없는 명령을 실행했을 때 발생한다. 예를 들어 하드웨어적으로 동시에 메모리 접근을 할 수 없다면 구조 해저드가 된다.
데이터 해저드 위에서 말한 데이터 의존 관계에 의해 병렬 실행이 불가능할 때의 이야기이다. 명령 1의 연산 결과를 명령 2가 사용하는 경우 데이터 해저드이다.
제어 해저드 조건 분기가 있을 때 발생한다. 명령 1이 조건 분기이고 이 조건에 따라 명령2의 실행 여부가 결정되는 상황이라면 제어 해저드이다.
동시 처리와 병렬 처리의 필요성
동시 처리와 병렬 처리가 왜 필요하냐는 내용에 대해서이다.
먼저
병렬 처리와 성능 향상
병렬 처리는 성능 향상을 위해 필요하다. 그런데 아까 알아본 3가지 병렬성 중 데이터 병렬성과 인스트럭션 병렬성은 컴파일러나 하드웨어 차원에서 수행된다. 그래서 여기서 주로 다루는 것은 태스크 병렬성 처리이다.
결과적으로는 소프트웨어 차원에서도 병렬성(적어도 태스크 병렬성)은 의식해야된다는 내용인데, 하드웨어 기술의 한계로 소프트웨어에서도 이것을 의식해야한다는 것이다.
동시 처리의 필요성과 계산 경로 수 급증
동시 처리는 효율적인 계산 리소스 활용, 공평성, 편리성이 필요성이라고 할 수 있다.
효율적인 계산 리소스 활용: IO 대기 상태 중 다른 일 가능 공평성: 여러 작업을 한 쪽에 치우치지 않고 동시 작업 가능(예: 노래 들으면서 웹서핑하기)
그런데 동시 처리가 무조건 좋은 것은 아니다. 동시 처리는 복잡하다.
이유는 동시 처리의 계산 경로가 순차적으로 수행할 때보다 크게 늘어나기 때문이다. 동시 처리 시 계산 조합 수는 $n!$ 이 된다.
C
책에서는 어셈블리를 다루지만 내용이 매우 간단하고 약소한 관계로 C 위주로 설명한다.
Pthreads
C언어에서는 기본 라이브러리에 스레드를 다루는 기능이 제공되지 않아서 외부 라이브러리가 필요하다. Pthreads란 POSIX 표준 인터페이스를 갖춘 스레드 라이브러리를 총칭한다고 한다.
//Pthreads를 사용하기 위해 pthreads.h를 읽어야한다.
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define NUM_THREADS 10 // 생성할 스레드 수
// 스레드용 함수
void *thread_func(void *arg) {
int id = (int)arg;
for (int i = 0; i < 5; i++) {
printf("id = %d, i = %d\n", id, i);
sleep(1);
}
return "finished!"; // 반환값
}
int main(int argc, char *argv[]) {
// 스레드용 핸들러 저장 배열.
pthread_t v[NUM_THREADS];
// 스레드 생성
for (int i = 0; i < NUM_THREADS; i++) {
if (pthread_create(&v[i], NULL, thread_func, (void *)i) != 0) {
perror("pthread_create");
return -1;
}
}
// 스레드 종료 대기
for (int i = 0; i < NUM_THREADS; i++) {
char *ptr;
if (pthread_join(v[i], (void **)&ptr) == 0) {
printf("msg = %s\n", ptr);
} else {
perror("pthread_join");
return -1;
}
}
return 0;
}
디태치 스레드
앞에서는 스레드 종료를 pthread_join 함수에서 기다렸는데 이것으로 종료하지 않으면 메모리 누출이 된다.
그런데 스레드 종료 시 자동으로 스레드용 리소스를 해제하는 방법도 있는데 이것을 디태치 스레드라고 한다.
두 가지 방법으로 스레드를 디태치 스레드로 만들 수 있는데
pthread_create 함수 호출 시 어트리뷰트로 지정
pthread_detach함수 호출
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
// 스레드용 함수
void *thread_func(void *arg) {
for (int i = 0; i < 5; i++) {
printf("i = %d\n", i);
sleep(1);
}
return NULL;
}
int main(int argc, char *argv[]) {
// 어트리뷰트 초기화
pthread_attr_t attr;
if (pthread_attr_init(&attr) != 0) {
perror("pthread_attr_init");
return -1;
}
// 디태치 스레드로 설정
if (pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED) != 0) {
perror("pthread_attr_setdetachstate");
return -1;
}
// 어트리뷰터를 지정해 스레드 생성
pthread_t th;
if (pthread_create(&th, &attr, thread_func, NULL) != 0) {
perror("pthread_join");
return -1;
}
// 어트리뷰트 파기
if (pthread_attr_destroy(&attr) != 0) {
perror("pthread_attr_destroy");
return -1;
}
sleep(7);
return 0;
}
volatile 수식자
volatile 수식자를 이용하면 컴파일러의 최적화를 억제한 메모리 접근을 구현할 수 있다.
최적화를 왜 억제하냐 하겠지만 컴파일러가 느린 메모리 접근을 억제하기 위해 레지스터에 복사해서 값을 이용하는 작업이 메모리 값 감시 시에는 장애가 될 수도 있다.
사용법은 간단하다.
void wait_while_0(int *p) {
while (*p == 0) {}
}
에서 int *p 앞에 volatile만 붙여주면 된다.
void wait_while_0(volatile int *p) {
while (*p == 0) {}
}
이런 식이다.
스택 메모리와 힙 메모리
이 부분은 러스츠 소유권 이해하기에서 가져왔다.
스택
스택은 후입선출(last in first out)방식으로 값을 처리한다. 입출구가 하나인 통처럼 맨 꼭대기에서 무언가를 집어넣고 꺼내는 것은 가능하지만 중간과 아래에 있는 것은 바로 건드릴 수 없다. 스택에 저장될 데이터는 모두 명확하고 크기가 정해져 있어야 한다. 컴파일 타임에 크기를 알 수 없거나 크기가 변할 수 있는 데이터는 힙에 저장되어야 한다.
함수를 호출하면 호출한 함수에 넘겨준 값과 해당 함수의 로컬 변수들이 스택에 들어가고, 이 데이터들은 함수가 종료될 때 팝된다.
힙
데이터에 힙을 넣을 때 절차는 다음과 같다.
저장할 공간이 있는지 운영체제에 물어보고
메모리 할당자가 힙 영역 내에서 빈 지점을 찾는다.
아까 발견한 빈 지점을 사용 중이라고 표시하고
그 지점을 가리키는 포인터를 반환한다.
이 전체 과정을 힙 공간 할당이라고 한다.
레스토랑에 비유하자면
레스토랑에 방문하는 인원수를 수용할 좌석이 있는지 묻는다.
직원은 빈 테이블을 찾아서
테이블이 사용 중임으로 상태를 바꾸고(비유가 이상하긴 한데 다른 손님이 들어왔을 때 여전히 빈 테이블이라고 하지는 않을테니까...)
손님에게 테이블 위치를 안내할 것이다.
라고 할 수 있다.
힙 영역은 포인터가 가리키는 곳을 찾아가는 과정 때문에 느려진다. 힙에 있는 데이터들은 붙어 있는 것이 아니라 이곳 저곳에 떨어져 있는데 이렇게 되면 프로세서가 돌아다니면서 데이터들을 처리해야하기 때문에 느리다.