Semaphore(세마포어): structure for concurrency control
0
Semaphore(세마포어)
세마포어는 병행성 제어를 위한 잘 알려진 구조이다.
- 세마포어는 락 또는 조건 변수로 사용될 수 있다.
- 이진 세마포어(binary semaphore), 카운팅 세마포어(counting semaphore) 등이 있다.
- 다양한 병행성 문제에서 활용이 가능하다.
- 1) producer/consumer 문제
- 2) reader/writer 문제
- 3) 식사하는 철학자 문제
- ...
세마포어 정의
세마포어 객체는 크게 세가지 메서드를 통해 정수값을 제어하는 방식으로 병행성을 제어한다.
- sem_init(semaphore, p_shared, initial_value)
- sem_wait() (P(), down()으로도 불린다.)
: 세마포어의 값을 감소시킨다. 그리고 S >= 0 일 때 곧바로 반환하거나, S < 0 일때 caller는 실행을 중지하고 후속 post를 기다린다. - sem_post() (V(), up(), sem_signal()으로도 불린다.)
: 세마포어의 값을 증가시킨다. 그리고 만약 대기중인 쓰레드가 있다면 그 중 하나를 깨운다.
#include <semaphore>
sem_t s;
sem_init(&s, 0, 1); // p_shared = 0 (공유 x), 초기 값: 1
int sem_wait(sem_t* s) {
// 세마포어 값을 1 줄인다.
// 세마포어의 값이 음수이면 wait
}
int sem_post(sem_t* s) {
// 세마포어 값을 1 증가시킨다.
// 하나이상의 쓰레드가 wait 상태라면 그 중 하나를 깨운다.
}세마포어를 lock으로 사용하는 예시
- test_and_set(HW지원) + sleep lock(OS 지원)
- 세마포어 값을 1로 초기화
sem_t m;
// 세마포어 값을 1로 초기화하면 lock으로 사용할 수 있다.
sem_init(&m, 0, 1);
sem_wait(&m); // == pthread_mutex_lock(), 락 변수 값을 1 줄인다.
//
// 임계 영역
//
sem_post(&m); // == pthread_mutex_unlock(), 락 변수 값을 1 증가시킨다.- 상호배제를 지원할 수 있다.
- 음수의 값에 절댓값을 씌우면 대기중인 쓰레드 갯수가 된다.
세마포어를 condition variable(조건 변수)로 사용하는 예시
- 세마포어 값을 0으로 초기화
- 후 순서 작업 수행 전 sem_wait
- 전 순서 작업 수행 후 sem_post
sem_t s;
void* child(void* arg) {
printf("child \n");
sem_post(&s); // signal here: child is done
return NULL;
}
int main(int argc, char* argv[]) {
// // 세마포어 값을 0로 초기화하면 조건 변수로 사용할 수 있다.
sem_init(&s, 0, 0);
printf("parent: begin \n");
pthread_t c;
pthread_create(&c, NULL, child, NULL);
sem_wait(&s); // 메인 쓰레드가 자식 쓰레드를 기다림
printf("parent: end \n");
return 0;
}메인 쓰레드가 sem_wait(&s);를 호출하면 세마포어 값이 -1이 되고 wait 상태로 들어간다. 이 후 자식 쓰레드가 run 상태에서 작업을 끝내고 post를 호출하면서 세마포어 값을 증가시키고 메인 쓰레드를 깨운다.
생산자/소비자 문제에서의 세마포어 활용
생산자/소비자 문제에서 병행성을 제어하려면 두 가지 세마포어를 사용해야 한다.
- mutex를 위한 이진 세마포어
- full/empty를 관리하기 위한 카운팅 세마포어
#define MAX 10
int buffer[MAX]; // 원형 큐
int fill = 0;
int use = 0;
// 버퍼 put 함수 //
void put(int value) {
buffer[fill] = value;
fill = (fill + 1) % MAX;
}
// 버퍼 get 함수 //
int get() {
int temp = buffer[use];
use = (use + 1) % MAX;
return temp;
}
// counting semaphore
sem_t empty;
sem_t full;
// binary semaphore
sem_t mutex;
/*
1) 세마포어가 있기에 pthread 라이브러리 사용 방식에서의 카운터 변수는 필요없다.
2) pthread 방식에서는 mutex -> ordering 순서였지만,
semaphore 방식에서는 ordering -> mutex 순서이다.
*/
// 생성자 함수 //
void* producer(void* arg) {
int i;
for (int i = 0; i < loops; i++) {
sem_wait(&empty); // empty 세마포어 변수로 wait
sem_wait(&mutex);
///////////////
/// 임계구역///
put(i);
///////////////
///////////////
sem_post(&mutex);
sem_post(&full); // full 세마포어 변수로 post
}
}
// 소비자 함수 //
void* consumer(void* arg) {
int i;
for (i = 0; i < loops; i++) {
sem_wait(&full); // full 세마포어 변수로 wait
sem_wait(&mutex);
//////////////
///임계구역///
int temp = get(i);
//////////////
//////////////
sem_post(&mutex);
sem_post(&empty); // empty 세마포어 변수로 post
printf("%d \n", temp);
}
}
int main(int argc, char* argv[]) {
// MAX: 넣을 수 있는 버퍼의 가용 공간
sem_init(&empty, 0, MAX);
// O: 생성자에 의해 만들어진 갯수
sem_init(&full, 0, 0);
// lock 변수로 사용할 세마포어는 1로 초기화
sem_init(&mutex, 0, 1);
// ...
}Reader/Writer 문제에서의 세마포어 활용
생산자/소비자 문제에서는 소비가 허용될 때 소비자 쓰레드 하나만 동작하여야만 했다.
- A consumer in critical section -> next producer or consumer must wait
하지만 reader/writer 문제에서는 다수의 reader(tree lookup and insert)를 허용하여야 한다.
- A reader in critical section -> next writer must wait, but next reader can enter(better performance)
sem_t lock;
sem_t writelock;
int readers;
void init() {
readers = 0;
sem_init(&lock, 0, 1);
sem_init(&writelock, 0, 1); // writer 최대 하나 허용
}
void acquire_readlock() {
sem_wait(&lock);
readers++;
if (readers == 1)
sem_wait(&writelock);
sem_post(&lock);
}
void release_readlock() {
sem_wait(&lock);
readers--;
if (readers == 0)
sem_post(&writelock);
sem_post(&lock);
}
void acquire_writelock() {
sem_wait(&writelock);
}
void release_writelock() {
sem_post(&writelock);
}식사하는 철학자 문제에서의 세마포어 활용
식사하는 철학자 문제를 간단히 말하자면,
철학자의 숫자만큼 포크가 놓여있다. 철학자는 양 옆에 있는 두 개의 포크를 사용해야 식사를 할 수 있다.
만약 철학자들 모두가 왼쪽 포크를 잡으려고 한다면 데드락이 발생한다. 아래 코드가 데드락이 발생될 수 있는 코드이다.
int left(int p) {
return p;
}
int right(int p) {
return (p + 1) % 5;
}
sem_t forks[5];
void init() {
int i = 0;
for (i = 0; i < 5; i++) {
sem_init(&forks[i], 0, 1); // 각 포크에 할당된 락 변수
}
}
void getforks() {
sem_wait(forks[left(p)]);
sem_wait(forks[right(p)]);
}
void putforks() {
sem_post(forks[left(p)]);
sem_post(forks[right(p)]);
}
// 각 철학자(p) 쓰레드가 아래 코드를 수행한다.
while (1) {
think();
getforks();
eat();
putforks();
}
이를 어떻게 해결할 수 있을까?
바로 철학자(쓰레드) 한 명의 순서를 반대로 두는 것이다. 모두가 왼쪽 포크를 먼저 잡으려 할 때 한 명의 철학자는 오른쪽 포크를 잡게 하는 것이다.
void getforks() {
if (p == 4) {
sem_wait(forks[right(p)]);
sem_wait(forks[left(p)]);
}
else {
sem_wait(forks[left(p)]);
sem_wait(forks[right(p)]);
}
}
