Higher-level solution for CSP
- 뮤텍스 락(Mutex Locks): 가장 간단한 동기화 도구 → “2개의 프로세스” 임계 영역에 진입할 때 lock을 걸어 다른 프로세스에서 접근하지 못하게 하고, 임계 영역에서 빠져나올 때 lock을 푼다.
- 세마포어(Semaphore): n개의 프로세스를 관리할 수 있기 때문에 보편적이고, 효율적인 방식. (6.6에서 자세히 다룰 예정)
- 모니터(Monitor): 뮤텍스와 세마포어의 단점을 극복한 방식
⇒ 위 3가지 해결방법은 “상호배제”만 해결해준다.
- 라이브니스(Liveness): 상호배제 + 데드락 고려
뮤텍스 락(Mutex Lock)
Mutex : 상호 배제 (mutual exclusion)
임계영역에 들어가기 위한 락(열쇠)을 획득하는 과정을 acquire, 다시 락을 반납하는 과정을 release라고 부름.
구현을 위해 2개의 메소드 (acquire(), release())와 1개의 변수 (bool available)가 필요하다.
acquire()
{
while (!available)
; // busy wait
available = false;
}
release()
{
available = true;
}acquire()와 release() 모두 원자적 (atomically)으로 구현되어야 한다 → compare_and_swap을 이용해 구현할 수 있다.
(두 메소드 실행 중에 Context Switch가 일어나 원하는 결과가 나오지 않을수도 있기때문)
Busy waiting
- 프로세스가 임계영역에 들어가기 위해 acquire() 메소드에서 무한루프를 돌면서 CPU를 낭비하는 현상
멀티프로그래밍 시스템에서 심각한 문제. Ready Queue에서 실행을 기다리고 있는 프로세스들이 있는데 한 프로세스가 CPU 리소스를 낭비하게 되면 효율이 좋지 않다.
Spinlock
- Busy Waiting 동작중인 뮤텍스 락
여러 개의 CPU 코어가 존재할 때 사용하지 않는 코어에서 스핀락을 통해 대기하고 있다가 락을 얻은 뒤 곧바로 임계 영역으로 진입할 수 있음.
Busy Waiting 중에는 Context Switch가 일어나지 않기 때문에 소요시간을 줄일 수 있다.
(일반적으로 Waiting상태 → key를 얻고 ready상태 → running상태를 거치면 시간이 오래 걸린다.)
하지만 running상태인 busy waiting중에 key를 얻고 임계영역에 진입하면 Context Switch가 일어나지 않는다.)
- Spinlock 예제
#include <stdio.h>#include <pthread.h>int sum = 0;
pthread_mutex_t mutex;
void* counter(void* param)
{
for (int k = 0; k < 10000; k++)
{
/* entry section */
pthread_mutex_lock(&mutex);
/* critical section */
sum++;
/* exit section */
pthread_mutex_unlock(&mutex);
/* remainder section */
}
pthread_exit(0);
}
int main()
{
pthread_t tid1, tid2;
pthread_mutex_init(&mutex, NULL); // 뮤텍스 초기화
pthread_create(&tid1, NULL, counter, NULL); // 스레드 생성
pthread_create(&tid2, NULL, counter, NULL);
pthread_join(tid1, NULL); // Join
pthread_join(tid2, NULL);
printf("sum = %d\n", sum);
}세마포어 (semaphore) [신호기]
- 여러 프로세스 (n개의 프로세스)에서의 임계 영역 문제를 해결하기 위한 방법.
- 세마포어 (semaphore)
**S**- 정수 변수(Integer variable)
- 초기화를 어떻게 하는지에 따라
wait()와signal()(혹은P(), V())이라는 2가지 원자적 연산을 가진다. P: 테스트,V: 증가
- 원자적으로(atomically) 구현되어야 한다.
wait(S)
{
while (S <= 0)
; // busy wait
S--;
}
signal(S)
{
S++;
}Binary Semaphore (n = 1)
- 범위가 0~1 → Mutex lock과 비슷하다.
Counting Semaphore (n > 1)
- 여러개의 자원을 가진 인스턴스에 이용할 수 있다.
- 유한한 자원(finite resource)을 관리하기에 좋다. Counting Semaphore(계수 세마포어)를 사용하기 위해서 S = n (n > 1) 사용가능한 자원의 개수로 세마포어를 초기화 한다. 자원을 사용할 때 :
wait()메소드 호출 [P()와 같다.] → count 1 감소 자원 사용 후 반납 :signal()메소드 호출 [V()와 같다.] → count 1 증가
count가 0이 되면 모든 자원들이 사용되고 있는 것이므로
다른 프로세스는 임계 영역에 접근할 수 없다.
자원을 사용하고 있는 프로세스가 자원을 반납하면 그때 자원을 사용할 수 있다.
Semaphore를 이용한 동기화 문제(synchronization problem) 해결
Q) P1, P2 2개의 프로세스 & P1의 S1코드, P2의 S2코드가 존재할 때 반드시 S1이 수행된 다음에 S2가 수행되도록 만들고 싶다면?
Sol) 세마포어를 synch라는 이름으로 선언하고 0으로 초기화한다.
S1;
signal(synch);wait(synch);
S2;- S1코드 실행 | S2실행 전 wait()
- signal(synch); → synch가 0에서 1로 증가 | synch가 1이 되었으므로 wait를 풀고 S2로 진입
세마포어도 Busy waiting의 문제가 있다.
이를 해결하는 방법 :
wait()메소드가 호출되면 프로세스를 Wait Queue로 보낸다.- 다른 프로세스에서
signal()메소드를 호출하면 Wait Queue에 있던 프로세스를 ready queue로 보내 CPU 자원을 획득하기를 기다리도록 한다.
typedef struct
{
int value;
struct process* list; // linked list
} semaphore;
wait(semaphore* S)
{
S->value--;
if (S->value < 0)
{
// 프로세스 ->list에 추가한다.
sleep(); // Wait Queue로 이동
}
}
signal(semaphore* S)
{
S->value++;
if (S->value <= 0)
{
// 프로세스를 list에서 제거
wakeup(P); // Ready Queue로 이동
}
}Note:
만약 sum() 인스턴스1개에 5개의 스레드가 접근할 때 세마포어를 통해 동기화를 한다면?
( sum() 인스턴스가 10000을 증가한다고 가정해보자)
코드 실행 시 50000이 출력되지 않는다. 왜 이런 문제가 발생할까?
계수 세마포어의 전제조건은 "n개의 인스턴스"이다.
코드 실행 시 Race condition이 발생할 수 밖에 없다.
잘 생각해보면 어떤 프로세스가 먼저 접근할 것인지 순서가 정해져 있지 않기 때문이다.
→ 5개의 인스턴스를 생성하고 각각의 스레드에 할당하면 제대로 된 결과가 나올 것이다.
만약 이진 세마포어로 바꾼다면 다시 제대로 된 결과가 나온다.
1개의 세마포어를 한 프로세스 (스레드)가 차지하여 작업을 수행하는 동안 다른 프로세스 (스레드)는 접근하지 못하기 때문이다.
- 코드
#include <stdio.h>
#include <pthread.h>
#include <semaphore.h>
int sum = 0;
sem_t sem;
void* counter(void* param)
{
for (int k = 0; k < 10000; k++)
{
/* entry section */
sem_wait(&sem);
/* critical section */
sum++;
/* exit section */
sem_post(&sem); // 자바는 notify()를 씀. 이름은 다르지만 개념은 동일함.
/* remainder section */
}
pthread_exit(0);
}
int main()
{
pthread_t tid[5]; // 5개의 스레드 리스트
sem_init(&sem, 0, 5); // 0으로 초기화 및 5개의 세마포어 생성
for (int i = 0; i < 5; i++)
pthread_create(&tid[i], NULL, counter, NULL); // 5개의 스레드 생성
for (int i = 0; i < 5; i++)
pthread_join(tid[i], NULL); // 스레드 Join
printf("sum = %d\n", sum);
}참고 :
Silberschatz et al. 『Operating System Concepts』. WILEY, 2020.
