1. Concurrency vs Parallelism
1. 병행성 (Concurrency)
- 동시에 실행되는 것처럼 보이는 것
- Logical Level에 속함
- Single Core
- 물리적으로 병렬이 아닌 순차적으로 동작할 수 있다.
- 실제로는 Time-sharing으로 CPU를 나눠 사용함으로써 사용자가 Concurrency를 느낄 수 있도록 한다. - Multi Core
- 물리적으로 병렬로 동작할 수 있다. - Case
- Mutex, Deadlock
2. 병렬성 (Parallelism)
- 실제로 동시에 작업이 처리가 되는 것
- Physical Level에 속함
- 오직 Multi Core에서만 가능하다.
- Case
- OpenMP, MPI, CUDA
2. Race Condition
- Race condition이란, 두 개 이상의 프로세스가 공통 자원 하나를 두고 서로 사용하려고 경쟁하는 상황을 말한다.
Race condition인 경우, 세 가지 제어 문제에 직면할 수 있다.
1. Mutual exclusion
2. Deadlock
3. Starvation
1. Mutual exclusion
Race condition을 막기 위해서는 두 개 이상의 프로세스가 공용 데이터에 동시에 접근 하는 것을 막아야 한다. 즉, 한 프로세스가 공용 데이터를 사용하고 있으면 그 자원을 사용하지 못하도록 막거나, 다른 프로세스가 그 자원을 사용하지 못하도록 막으면 이 문제를 피할 수 있다.
이것을 상호 배제(Mutual exclustion)이라고 부른다.
2. Deadlock
그러나 위와 같은 상호 배제를 시행하면 추가적인 제어 문제가 발생한다. 하나는 교착상태 즉 여기서 말하는 Deadlock이다. 프로세스가 각자 프로그램을 실행하기 위해 두 자원 모두에 엑세스 해야 한다고 가정할 때 프로세스는 두 자원 모두를 필요로 하므로 필요한 두 리소스를 사용하여 프로그램을 수행할 때까지 이미 소유한 리소스를 해제하지 않는다. 이러한 상황에서 두 프로세스는 교착 상태에 빠지게 되는 문제가 발생할 수 있다.
3. Starvation
이 제어 문제는 '기아 상태' 라고도 한다. 이러한 문제는 프로세스들이 더 이상 진행을 하지 못하고 영구적으로 블록되어 있는 상태로, 시스템 자원에 대한 경쟁 도중에 발생할 수 있고 프로세스 간의 통신 과정에도 발생할 수 있는 문제다. 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로는 아무것도 완료되지 못하는 상태가 된다.
이렇게 Race condition인 경우에는 스레드의 실행 순서를 잘 조절해주지 않으면 이상한 상태, 비정상적인 상태가 나오게 된다. 이 문제는 항상 발생하는 것이 아니라 특정한 순서대로 수행되었을 때 발생하는 것이다. 이 문제는 디버깅을 할 때에는 전혀 보이지 않는 문제점이고, 발생 시에 모든 프로세스에 원하는 결과가 발생하는 것을 보장할 수 없으므로 후에 더욱 큰 문제를 야기할 수 있으므로 반드시 피해야 하는 상황이다.
이러한 문제가 발생하지 않도록, OS는 다른 프로세스의 의도하지 않은 간섭으로부터 각 프로세스의 데이터 및 물리적 자원을 보호해야 하며 여기에 메모리, 파일 및 I/O 장치와 관련된 내용이 포함된다.
그리고 프로세스에서 수행하는 내용과 프로세스가 생성하는 결과는, 다른 동시 프로세스의 실행 속도와 무관, 즉 기능과 결관느 서로 독립적이여야 한다.
3. How to prevent Race condition
- Race condition을 예방할 수 있는 방법으로, 즉 병행 처리를 위한 프로세스 동기화 기법 Semaphore와 Mutex 2가지가 있다.
임계영역(Critical section)
공유자원에 접근할 수 있는 영역을 말한다. 임계 영역은 반드시 보호 되어야하는 구간으로 보호 메커니즘으로는 세마포어와 뮤텍스 등이 있습니다.
1. Semaphore
- 일단 세마포어는 P연산, V연산으로 이루어져 있습니다.
P : S를 1 감소
V : S를 1 증가
프로세스는 S가 1일때만 임계영역에 진입할 수 있다고 가정해보면, 아래와 같은 순서로 진행됩니다.
초기 S = 1
P(S) (S가 1 감소되어 0)
//critical section start
//공유 자원을 사용할 수 있는 영역
//critical section end
V(S) (S가 1 증가되어 1)
다른 프로세스가 임계영역을 확인하고, 그때 S의 값이 0이라면 대기하게 됩니다.
즉, P연산에는 S가 0이라면 대기하는 코드가 들어가야 하고, 0이 아닐때 S의 값을 1 감소시킨 후 임계영역으로 들어갈 수 있게됩니다.
P(S){
while(S==0){
//wait
}
S--;
}V(S)는 S의 값을 1 증가시키고, P(S)에서 기다리고 있는 프로세스가 S가 1이 되는 순간 진입할 수 있게 해주게됩니다. V(S)를 간단히 구현해보면 다음의 코드와 같습니다.
V(S){
S++;
}여기서 S에 주목해보면, 만약 S가 1이라면 임계영역에 들어갈 수 있는 프로세스는 1개가 되지만, S가 2라면 임계영역에 들어갈 수 있는 프로세스는 2개가 되게 됩니다.
여기서 Semephore와 Mutex의 차이가 보이게 됩니다.
| Semephore | Mutex |
|---|---|
| 여러개의 프로세스가 동시에 공유자원에 접근할 수 있음 | lock, unlock의 상태만 존재하는 일종의 binary semaphore |
1. sem_init
int sem_init(sem_t *sem, int pshared, unsigned int value)- sem - 초기화 할 세마포어의 포인터를 넣는 위치
- pshared - 0인 경우 세마포어는 프로세스 안에서 쓰레드들끼리 공유 가능
그 외의 경우 프로세스 간 공유 가능 - value - 세마포어가 가지는 초기 값 설정
아래와 같이 사용하여 초기화를 수행하도록 합니다.
#include <semaphore.h>
sem_t s;
sem_init(&s, 0, 1);2. sem_wait(sem_t *s)
sem_t *s 에서 받은 세마포어 값이 1 이상이면 그 값을 감소시키고 즉시 함수를 빠져나가도록 합니다. 만약 그 값이 0이라면 이 값이 1 이상이 되어 감소를 수행할 수 있거나 인터럽트 호출이 있지 않는 이상 현재 지점에서 작업이 대기하도록 만듭니다.
- 세마포어 값 > 0 👉 그 값을 감소시키고 즉시 함수 탈출
- 세마포어 값 <= 0 👉 현재 지점에서 대기 and 현재 기다리고 있는 스레드의 수
3. sem_post(sem_t *sem)
세마포어의 값을 1 증가시킨다.
4. sem_destory(sem_t *sem)
세마포어와 관련된 리소스들을 소멸시킨다. (객체 소멸)
5. Binary Semaphore
이러한 세마포어의 활용 예제로 이진세마포어(Binary Semaphore)가 있습니다.
이진세마포어는 위에서 초기화 과정에서 초기값을 1로 주어 사용하는 것을 의미합니다.
이런 이진세마포어는 Lock과 동등한 역할을 합니다.
// binary semaphore // lock
// ==================== // ====================
sem_t m; // lock_t m;
sem_init(&m, 0, 1); //
//
sem_wait(&m); // lock(&m)
// 임계 구역 // // 임계 구역
sem_post(&m); // unlock(&m)이와 비슷하게 활용하는 예제로 조건 변수와 같이 활용하는 방법이 있습니다. 이는 초기값을 0으로 주어 구현할 수 있습니다.
sem_t s;
void *child(void *arg){
printf("child\n");
sem_post(&m);
return NULL;
}
int main(int argc, char *argv[]){
int X = 0
sem_init(&s, 0, X); // X의 값이 0이면 조건 변수로 사용할 수 있습니다.
printf("parent: begin\n");
pthread_t c;
pthread_create(c, NULL, child, NULL);
sem_wait(&s);
printf("parent: end\n");
return 0;
}
// ------------출력 결과입니다.------------ //
parent: begin
child
parent: end
이를 잘 활용하면 문제가 있었던 유한 버퍼 문제를 해결할 수 있습니다.
int buffer[MAX];
int fill = 0;
int use = 0;
void put(int value){
buffer[fill] = value;
fill = (fill + 1) % MAX;
}
int get(){
int temp = buffer[use];
use = (use + 1) % MAX;
return temp;
}
sem_t empty;
sem_t full;
void *producer(void *arg){
int i;
for(i = 0; i < loops; i++){
sem_wait(&empty);
put(i); // 요기서 문제 일어나게됨
sem_post(&full);
}
}
void *consumer(void *arg){
int i, temp = 0;
while(temp != -1){
sem_wait(&full);
temp = get();
sem_post(&empty);
printf("%d\n", temp);
}
}
int main(int argc, char *argv[]){
// ...
sem_init(&empty, 0, MAX);
sem_init(&fill, 0, 0);
// ...
}- MAX 값이 1인 경우 - 완벽하게 동작합니다.
- MAX 값이 1 이상인 경우 - Race condition 상태가 일어나 과거의 데이터가 덮어 씌어지는 문제가 발생할 수 있습니다. 여기서 임계 구역은 put() 및 get()을 수행하는 부분이 그 대상이 됩니다.
이를 고려해서 상호 배제를 위한 Lock(세마포어)을 하나 추가해 수정 하게 되면 아래의 코드와 같습니다.
sem_t empty; // cond_t empty
sem_t full; // cond_t full
sem_t mutex; // mutex_t mutex
void *producer(void *arg){
int i;
for(i = 0; i < loops; i++){
sem_wait(&mutex); // pthread_mutex_lock(&mutex);
sem_wait(&empty); // pthread_cond_wait(&empty, &mutex);
put(i);
sem_post(&full); // pthread_cond_signal(&full);
sem_post(&mutex); // pthread_mutex_lock(&mutex);
}
}
void *consumer(void *arg){
int i;
for(i = 0; i < loops; i++){
sem_wait(&mutex);
sem_wait(&empty);
int temp = get(i);
sem_post(&full);
sem_post(&mutex);
printf("%d\n", temp);
}
}
int main(int argc, char *argv[]){
// ...
sem_init(&empty, 0, MAX);
sem_init(&fill, 0, 0);
sem_init(&mutex, 0, 1);
// ...
}하지만 이 방법은 답이 될 수 없습니다. 왜냐하면 만약 소비자(consumer)가 mutex를 획득을 하고, sem_wait()를 세마포어가 가득찬 상태에서 진행한다고 가정하겠습니다. 그 후에 소비자가 대기 상태에 들어가고 CPU에 의해 생산자(producer)가 깨어나게 됩니다. 하지만 앞에서 소비자가 mutex를 가지고 있기 때문에 생산자는 sem_wait() 상태에 들어가게 됩니다. 이러면 소비자가 다시 시간이 지나 깨어난다고 해도 empty 세마포어가 조건을 만족하지 못하므로 대기 상태에 들어가게 됩니다. 그렇게 되면 교착상태에 걸리게 됩니다.
lock을 잡은 상태에서 조건 변수를 기다리면 교착상태에 걸리게 되고, 조건 변수를 만족되면 그 다음에 lock을 잡아야 deadlock이 발생하지 않습니다. 따라서 해결 방법은 그냥 락과 조건 변수의 위치를 서로 반대로 해주면 바로 해결됩니다. 이는 아래와 같이 각 내용을 변경을 하면 됩니다.
sem_wait(&empty);
sem_wait(&mutex);
// Critical Section
sem_post(&mutex);
sem_post(&full)아직 뮤텍스와 세마포어 차이가 잘 이해가지 않는다면 여기를 참고해보자. 너무 잘 정리해주셨다
4. 동기화 문제
1. The Producer/Consumer Problem
2. Readers - Writers Problem
3. The Dining Philosophers
