이 글에선 Thread와 Mutex Lock에 대해 알아본다. 우선 Thread가 무엇인지 알아보자.
일단 Multi proecessor는 고려하진 말자. Thread는 Single Processor일때도 있던 개념이다. UNIX OS에서 계산기 프로그램을 실행시켰는데 시계가 작동하지 않는다면 사고다.
우리는 어떻게 여러 작업을 동시에 처리할 수 있는지에 대해 기술적인 고민을 할 수 있다.
예를들어 실제로 우리가 웹 브라우저로 특정 웹사이트에 들어갔는데 데이터가 많을 수 있는데, 이럴때 우리 웹브라우저는 하나씩 다운로드 받지 않고, 병렬로 여러 데이터를 다운받는다. client인 우리 웹부라우저만 이러는게 아니라 web sever도 data를 병렬로 보내준다.
이게 딱히 새로운건 아니다. 예전 글에서 fork-exec로 동시에 다른 process를 같이 실행해보기도 했었다.
Thread란?
직역하자면 "실"이라는 의미로, process보다 더 작은 실행 흐름의 최소 단위이다.
아래 그림은 Single Thread가 실행되는 그림을 나타낸 것이다.
Text segment에서 이렇게 인스트럭션 실행 순서를 끊지않고 추적한 path를 thread of execution이라고 한다.
위 경우는 main()에서 print_msg() 함수를 순차적으로 호출하지만, 이를 동시에 호출해서 실행시키고 싶다면 어떻게 해야할까?
위 그림처럼 fork 느낌으로 여러 thread를 만들면 될 것이다. fork는 process 자체를 분기시켜 버리지만, thread는 같은 process내에 존재한다는 점이 다르다.
Single Processor라면 이렇게 thread를 분기 시켰을때 OS 스케줄러가 번갈아가면서 동시에 실행되는 것처럼 알아서 잘 스케줄을 짜준다. Multi Processor라면 동시에 돌려버릴 것이고...
싱글 코어일때 multi threading을 이용하면 어떤 작업들이 동시에 일어난다는 느낌을 받게 해준다.
multi core일땐 작업이 실제로 동시에 일어나기도 하므로 동시성과 더불어 작업 처리가 그만큼 빨라지기도 한다.
Q. 다른 process로 분기(ex. fork())시키는 것과 자세하게 무엇이 다른걸까? 둘 다 OS에서 번갈아가며 실행시킬건데..
A. 위에서도 말했듯 일단 threads는 한 process 내에서의 실행 흐름이다. 따라서 아예 다른 memory 공간을 사용하는 multi processing과 달리 multi threading은 Stack을 제외한 memory 영역을 공유한다. file descriptors와 process ID number도 모두 공유한다. Stack에서만 thread마다 별도 공간 사용하고, (같은 메모리 공간을 쓰니까) 나머지는 다 공유한다.
(PC register에서 현재 실행 inst.를 저장하는데 아마 multi threading을 하면 thread마다 PC "값"이 따로 생길거임. Text 영역 자체는 모든 threads가 당연히 공유하고.)
그렇기 때문에 전역변수라던가 static/malloc 같은 공간들도 모두 경우가 된다. 따라서 비교적 복잡한 IPC를 사용하지 않아도 thread 간엔 소통할 수 있다.
또 multi threading을 사용하면 context switching 시에 overhead가 줄어든다. 다른 thread를 실행시키려고해도 메모리 영역은 stack 제외하곤 다를게 없기 때문이다. 하지만 multi processes에서 context switching은 CPU register 뿐만아니라 cache memory의 데이터도 초기화되므로 부담이 크다.
그렇기 때문에 아예 다른 일을 하는 경우라면 multi processes를 적용할 수 밖에 없겠지만, 그런 경우가 아니고 비슷한 일을 하는 경우라면 multi threading이 이득이다. 단, multi threading은 자원 공유가 편리한만큼 주의해서 사용하지 않으면 오류가 쉽게 생길 수 있으니 조심하자.
POSIX Thread (pthread) 사용
thread의 한 종류인 POSIX thread 함수 알아보자.
process는 UNIX의 초기부터 있던 개념이지만, thread는 나중에 추가된 개념이다. 따라서 thread 개념은 다양한 곳에서 발전해왔기때문에 종류마다 그 특징이 다를 수 있다. 우리가 볼 것은 POSIX thread라는 것이다.
기본적은 흐름은 위와 같다. fork와 유사하지만, 위에서 언급했듯 둘은 근본부터 다르다.
주의할 것은 Main thread가 종료되면 process 자체가 종료된 것이므로 실행중이던 다른 threads도 모두 종료된다는 것이다.
따라서 pthread_join 함수로 다른 threads의 종료를 기다린다.(자세한건 아래에서)
multi threading을 하면 전역변수나 heap 영역 데이터를 threads간 쉽게 공유할 수 있기 때문에 또 공유자원 문제가 발생할 수 있다.
따라서 이를 제한할 수 있는 mutex_lock 관련 함수들에 대해서도 알아본다.(자세한 개념은 아래에서..)
프로세스때는 context switching할때 메모리로 기존 값을 쫓아내서 공유자원 문제가 생겼는데, threads간엔 그럼 왜 공유자원 문제가 생기는거지?
→ 굳이 메모리에 값을 올려두지 않아도, 접근하는 순서가 조금만 이상해도 문제가 생긴다.
예를들어 thread1이 전역변수의 값을 가져오고, 그 사이 thread2가 같은 전역변수 값을 가져오고, thread1이 그 값을 증가해서 업데이트 시키고, thread2도 그 값을 증가해서 업데이트 시키는 순서로 진행되면,
thread1이 한 일은 덮어씌워진다.
아래 헤더에 정의된 data type과 함수들을 알아보자.
#include <pthread.h>gcc -lpthread 옵션을 줘야한다.
> pthread_t
thread 정보를 담을 수 있는 구조체 type이다.
> int pthread_create(pthread_t *restrict thread, const pthread_attr_t *restrict attr
, void *(*start_routine)(void *), void *restrict arg);
첫번째 인자는 pthread_t type의 스레드 식별자 주소이다. 이곳에 생성된 스레드의 정보를 담아준다.
두번째 인자는 thread 특성?을 설정해주기 위해 pthread_attr_t type 변수의 주소를 넘겨준다는데, 보통 그냥 NULL 쓴다.
세번째 인자는 분기시켜 실행하게 될 thread 함수이다. " void* "을 return하고 " void* "을 parameter로 선언해야 한다.
네번째 인자는 thread 함수에 넘겨줄 argument이다. void* type이기때문에 구조체에 담아서 넘겨줄 수도 있고, 배열로 여러개 넘겨줄수도 있고, 매개인자 형식이 자유롭다.
> int pthread_join(pthread_t thread, void **retval);
첫번째 인자는 pthread_t type의 스레드 식별자이다. 어떤 스레드의 종료를 기다릴지 정한다.
두번째 인자는 void ** type으로 스레드가 종료할때 반환되는 값을 받아온다. ( ** type인거 주의!!!)
pthread_join을 사용하지 않으면 main thread가 종료될때 프로세스 자체가 종료되므로 다른 threads도 모두 종료된다.(실행되고있어도 그냥 종료되버림)
또 thread가 종료된다고 하더라도 즉시 메모리 자원등이 해제 되지 않는다. pthread_join 함수()를 만나야지만 자원이 해제되기 때문에 모든 joinable threads에 대해서는 반드시 pthread_join()을 호출해야한다. 아니면 메모리 누수가 발생할 것이다.
> pthread_mutex_t
mutex lock을 위한 정보를 담기위한 구조체 type이다.
아래 함수들에 동일한 변수를 넘겨주며 lock/unlock을 할 수 있다.(semaphore에서 V-P 동작과 거의 같으니 그거 생각하면 이해 잘 됨. mutex lock은 S가 0/1 밖에 안되는 세마포어라고 생각하면 쉽다.)
> int pthread_mutex_lock(pthread_mutex_t *mutex);
정확하게 어떤식으로 구현됐는진 모르겠으나 Semaphore의 V 함수처럼 구현돼있을 것이다.
critical area 이전에 호출돼서 다른 tread/process가 접근하지 못하게 lock을 건다.
> int pthread_mutex_unlock(pthread_mutex_t *mutex);
정확하게 어떤식으로 구현됐는진 모르겠으나 Semaphore의 P 함수처럼 구현돼있을 것이다.
critical area 이후에 호출돼서 다른 tread/process가 접근할 수 있게 lock을 해제한다.
Mutex Lock이란??
Semaphore처럼 동기화 도구 중 하나이다.
Mutex Lock은 Semaphore에서 변수가 0/1 밖에 안된다고 생각하면 쉽다.
앞서 말했듯이 thread들은 메모리 영역을 stack 빼고 다 공유한다. code가 있는 text 영역도 공유한다.
거기서 특정 code 영역을 semaphore에서 처럼 한 thread만 접근할 수 있도록 critical section으로 정해두고 위아래로 pthread_mutex_lock()과 pthread_mutex_unlock()을 해버리면 된다. 그럼 해당 임계영역에는 한 thread만 접근할 수 있다.
해당 코드 영역은 보통 공유자원 접근하는 부분에 해당하겠지만, semaphore에서도 말했듯이 이건 정하기 나름이다.
Q. Semaphore와 Mutex Lock의 차이??
A. 둘 다 processes간 동기화를 하든 threads간 동기화를 하든 언제든 적용할 수 있다.
(mutex lock은 한 프로세스 내에서만 되는게 아닌가? -> mutex_t 객체 공유한다면 다른 processes끼리도 동기화 가능)
둘의 차이점을 나열해보자면 다음과 같다.
1. Mutex를 사용하면 접근 허용 최대 프로세스/스레드 수가 1개이다.
2. Semaphore는 아무나 외부에서 P를 호출해서 들어갈 수 있는 반면, Mutex에선 실행중인 놈이 unlock을 해줘야한다.
3. Semaphore는 시스템 범위에 걸쳐 있고, 파일 시스템 상의 파일로 존재한다. 하지만 Mutex는 프로세스 범위를 가지며 프로세스 종료될 때 자동으로 Clean up 된다.
예제 코드를 하나 작성해보자.
특정 숫자를 입력으로 받아서 그 숫자보다 작거나 같은 소수(prime number)가 몇개 있는지 구하는 프로그램이다.
#include <stdio.h>
#include <pthread.h>
int isPrime(int n)
{
for (int i=2; i<=n/2; i++)
if (n%i == 0)
return 0;
return 1;
}
int main()
{
int N;
int count = 0;
printf("Enter an integer >= 2 : ");
scanf("%d", &N);
for (int i=2; i<=N; i++)
if (isPrime(i))
count++;
printf("The number of prime numbers : %d\n", count);
return 0;
}
위 프로그램의 시간 복잡도는 얼마일까?
O(n^2)처럼 보이지만, 실제론 O(2^n)이다. (어 2^n 맞나? 강의 올라오면 다시 확인해보기 ~~?)
다른 알고리즘으로 좀 더 빠르게 할 수도 있긴 하겠다만,
위에서 배운 pthread를 활용해보자. 병렬로 실행되도록 해버리면 처리 속도가 빨라질 것이다.
1~N/2 까지 한 thread가 맡아서 하고, (N/2)+1~N 까지 다른 thread가 맡아서 처리하도록 해보자.
#include <stdio.h>
#include <pthread.h>
struct PrimeTestRange {
int startN;
int endN;
};
int N;
int total_count = 0;
pthread_mutex_t total_lock;
int isPrime(int n)
{
for (int i=2; i<=n/2; i++)
if (n%i == 0)
return 0;
return 1;
}
void *func(void *arg) //argument를 다르게 줘서 각 쓰레드가 다른 범위를 처리하도록 함
{
struct PrimeTestRange range;
range = *(struct PrimeTestRange *)arg;
for (int i = range.startN; i <= range.endN; i++)
if (isPrime(i)) {
pthread_mutex_lock (&total_lock); //critical area 전에 lock
total_count++;
pthread_mutex_unlock(&total_lock); //critical area 후에 unlock
}
printf("Thread is done from %d to %d.\n", range.startN, range.endN);
}
int main()
{
pthread_t thrd1, thrd2;
int * status;
struct PrimeTestRange r1, r2;
printf("Enter an integer >= 2 : ");
scanf("%d", &N);
r1.startN = 2;
r1.endN = N/2;
r2.startN = N/2+1;
r2.endN = N;
pthread_create(&thrd1, NULL, func, &r1);
pthread_create(&thrd2, NULL, func, &r2);
pthread_join(thrd1, &status);
pthread_join(thrd2, &status);
printf("The number of prime numbers : %d\n", total_count);
return 0;
}공유자원인 전역변수 total_count에 접근하여 카운팅한다. 공유자원이기때문에 위에서 배운 mutex lock을 사용해 제한을 걸었다.
pthread_creat()의 첫번째 인자로 각 thread 정보를 담을 수 있는 pthread_t type 변수의 주소를 넘겨준다.(이후 join 등에서 thread를 특정해야할때 사용함)
func thread function은 void*을 인자로 받고 void*을 return하도록 해서 type도 맞췄으며, thread function의 argument로 활용하기위해 PrimeTestRange 구조체도 만들었다.
그리고 각 thread마다 인자를 다르게 줘서 서로 다른 범위에 대해 Prime number 개수를 구하도록 했다.
그런데 이런 경우 다른 방식으로도 공유 자원 문제를 해결 할 수 있다. 위처럼 mutex lock을 사용할 경우 correctness는 충족할 수 있지만, 함수 호출이 매우 빈번하게 일어나므로 성능면에서 좋지 않다.
(mutex lock 같은게 general한 방법이고 지금 소개하는 방법은 특정 경우에서만 적용 가능함)
우리 목적은 결국 누적합을 구하는 것이기 때문에 굳이 저렇게 전역 변수를 두지않고 각 thread별로 합을 구하게 한 다음 return 값으로 각자 구한 합을 받아온다음 그 값을 더하면 된다.
위에서 언급했듯이 pthread_join() 함수로 각 thread의 return 값을 받아올 수 있다.
#include <stdio.h>
#include <pthread.h>
struct PrimeTestRange {
int startN;
int endN;
};
int N;
int total_count = 0;
int isPrime(int n)
{
for (int i=2; i<=n/2; i++)
if (n%i == 0)
return 0;
return 1;
}
void *func(void *arg) //함수 그냥 하나로 통일, argument를 다르게 줘서 각 쓰레드가 다른 일을 하도록 함
{
int local_count = 0;
struct PrimeTestRange range;
range = *(struct PrimeTestRange *)arg;
int *ctr;
for (int i = range.startN; i <= range.endN; i++)
if (isPrime(i))
local_count++;
printf("Thread1 is done.\n");
ctr = (int *) malloc(sizeof(int));
*ctr = local_count;
return ctr;
}
int main()
{
pthread_t thrd1, thrd2;
int * status;
struct PrimeTestRange r1, r2;
printf("Enter an integer >= 2 : ");
scanf("%d", &N);
r1.startN = 2;
r1.endN = N/2;
r2.startN = N/2+1;
r2.endN = N;
pthread_create(&thrd1, NULL, func, &r1);
pthread_create(&thrd2, NULL, func, &r2);
pthread_join(thrd1, &status);
total_count += *status;
pthread_join(thrd2, &status);
total_count += *status;
printf("The number of prime numbers : %d\n", total_count);
return 0;
}이렇게 전역 변수를 사용하지 않고, 각 local에서 값을 각각 누적시킨다.
(각 thread별로 stack 영역은 따로 생기기때문에, 같은 함수 코드라서 같은 변수를 쓰는 것 같지만 사실은 다른 공간이다.)
이후 pthread_join()에서 각 threads가 종료되고 return 값으로 각 누적합을 받아온 후 main에서 "순차적으로" 공유자원에 접근한다. → 해결
위에서도 말했지만 pthread_join() 함수에서 return을 받아올때 " ** " type이라는 것을 주의해야한다.
여기서도 " int* " type의 status의 주소를 넘겨줬다. 그래야 제대로 작동한다.
(아마 포인터를 return 할수도 있어서 모든 return type을 다 수용해주려고 애초에 thread 함수의 return type을 void * 로 쓰는듯. int 같은거만 return할거면 void * type만 해도 괜찮음. pthread_join에선 그 void * 을 저장해와야되니까 void **을 넘겨주는 것이고. return 값 담아오는건 pthread_join에서 내부적으로 뭐 알아서 어떻게 해주겠지)
보다시피 thread function에서 return 해줄때 static 변수나 malloc으로 할당받은 공간을 가리키는 변수를 반환해야한다는 것도 주의하자.
좋은 병렬화?
소수 카운팅 스레드에서...
한 thread는 2~N/2까지 알아보고, 다른 thread는 N/2+1 ~ N까지 알아보도록하는데, 이건 좋은 병렬화가 아니다.
두번째 thread의 숫자들이 더 크므로 N이 커지면 이 thread가 무조건 더 오래걸린다.
두 threads가 거의 동시에 끝나도록해야 좋은 병렬화이고, 이런 낭비되는 초과시간을 해소할 수 있다.
이 경우 두가지정도 방법이 있다.
1. 2를 제외하고는 어차피 홀수만 test해도 되니까 스레드 하나는 3부터, 하나는 5부터 시작해서 각자 4칸씩 뛰면서 검사하기
2. testNum 전역변수를 선언해두고 쓰레드가 테스트할 숫자를 여기서 가져오도록 한다. 각 쓰레드는 한 작업을 마친 후 이 변수에서 다음 테스트할 값을 가져오고, testNum 값을 1 늘려주면 된다. 그럼 하나씩 번갈아 가져오기때문에 두 스레드의 작업이 거의 동시에 끝날 것이다. 이 testNum은 공유 자원이므로 Mutex Lock 등으로 제한을 걸어줘야한다.
2번 방법을 이용해 구현한 코드는 아래와 같다.
//prime counter with global variable and mutex lock
//2를 제외하고 홀수만 테스트하도록 하면 더 빨라질 것으로 예상됨
#include <stdio.h>
#include <pthread.h>
int N;
int total_cnt;
int testNum = 2;
pthread_mutex_t total_cnt_lock;
pthread_mutex_t testNum_lock;
int isPrime(int n);
void *func(void *arg);
int main()
{
pthread_t thrd1, thrd2;
int * status;
printf("Enter an integer >= 2 : ");
scanf("%d", &N);
pthread_create(&thrd1, NULL, func, NULL);
pthread_create(&thrd2, NULL, func, NULL);
pthread_join(thrd1, &status);
pthread_join(thrd2, &status);
printf("total number of prime numbers : %d\n", total_cnt);
return 0;
}
int isPrime(int n)
{
for (int i=2; i<=n/2; i++)
if (n%i == 0)
return 0;
return 1;
}
void *func(void *arg)
{
int num;
while (testNum <= N) {
pthread_mutex_lock (&testNum_lock);
num = testNum;
testNum++;
pthread_mutex_unlock(&testNum_lock);
if (isPrime(num)) {
pthread_mutex_lock(&total_cnt_lock);
total_cnt++;
pthread_mutex_unlock(&total_cnt_lock);
}
}
printf("Thread is done.\n");
}
ㅡㅡㅡ
<참고>
multi threading시 exec, fork, signal 등을 사용하려면 주의가 필요하다.
exec를 호출하면 나머지 threads들이 모두 중지된다. fork를 호출하면 호출한 thread에 대해서만 복사된다. signal은 좀 복잡하다, 어느 thread에 시그널을 줄지 같은 문제도 있고...
(나중에 자세히 볼거면 책 p.465 보기, 아니면 검색해봐도 되지싶고)
mutex lock도 동기화시에 사용할 수 있지만, 각 thread가 서로 소통(통신)하며 동기화를 해줘야 할 수도 있다.
pthrad_join으로 할 수 있지않나 생각할 수 있는데 그건 사용이 제한적이다. 어떤 thread가 먼저 끝날지 모르기 때문에 제대로 작동하지 않을 수 있고, 애초에 threads가 끝나야 무언가를 할 수 있다.
따라서 조건변수를 이용한 동기화 개념이 나오게 되었다. 참고
pthread_cond_wait() 같은 관련 함수나 개념을 수업에서 자세하게 하진 않았으므로 패스.
<개선사항>
위 소스코드들에선 mutex lock을 사용할 때 pthread_mutex_init() 함수를 통한 mutex 변수 초기화가 없다.
찾아보니 아마 시스템에서 자동으로 초기화된게 아다리가 잘 맞아서 잘 작동했던거고.. 원래는 pthread_mutex_init() 함수로 초기화하는게 good practice라고 한다!!!!!
'수업 > System Programming' 카테고리의 다른 글
| [System Programming] Semaphore (0) | 2022.12.03 |
|---|---|
| [System Programming] Barrier (0) | 2022.11.26 |
| [System Programming] Inter Process Communication(IPC) (0) | 2022.11.23 |
| [System Programming] pipe 공부 (0) | 2022.11.09 |
| [System Programming] Shell 공부 (0) | 2022.11.05 |