31장: Semaphore
Semaphore API
sem_init(세마포어 변수, 0, 초기값)
- 세 번째 매개변수는 음수가 될 수 없음
sem_t s;
sem_init(&s, 0, 1); // 초기값 1
sem_wait(&s)
- sem 값을 하나 감소 시킴
- 감소시켰는데, 결과가 0 이상이면 바로 반환
- 감소시켰는데 음수이면 0될 때까지 대기
- sem 값이 음수일 때, 절대값은 대기 중인 스레드 수와 같음
sem_post(&s)
- 세마포어 값 하나를 증가시킴
- 대기 중인 스레드가 있다면, 하나를 깨움 (큐로 동작)
이진 세마포어: Lock으로 활용하기
sem_t s;
sem_init(&s, 0, 1);
sem_wait(&m);
// 여기에 임계영역 코드 작성
sem_post(&m);
- 0번 스레드가 wait()하고 임계영역 진입
- 1번 스레드가 wait()하고 임계영역 진입하려 했으나, 음수이므로 대기
- 0번 스레드가 post함
- 1번 스레드가 깨어나서 동작하고 post 함
문제
아래 결과 출력되게 구현하기
sem_t s;
void* child(void* arg) {
printf("child");
sem_post(&s);
return NULL;
}
int main(int argc, char* argv[]) {
sem_init(&s, 0, 0);
printf("parent: begin");
pthread_t c;
pthread_create(&c, NULL, child, NULL);
sem_wait(&s);
printf("parent: end");
return 0;
}
실행 예 2가지가 있는데,
자식 실행 전에 부모가 먼저 sem_wait(&s)를 호출 한 경우
s 값이 음수 이므로 부모는 대기함,
자식이 post 해주면 그때 다시 동작
자식이 먼저 실행되어 종료된 경우
s 값이 처음에 0인데, 자식이 실행되어 “child” 출력함
이후 post 호출을 하여 s가 1이 됨
부모가 sem_wait를 하여 세마포어 사용
프로듀서/컨슈머 문제
생산자는 버퍼에 자리가 비기를 기다려 put() 호출
소비자는 버퍼에 데이터가 오기를 기다려 get() 호출
단순 구현의 문제 발생
int buffer[MAX];
int fill = 0;
int use = 0;
void put(int value) {
buffer[fill] = value;
fill = (fill + 1) % MAX;
}
int get() {
int tmp = buffer[use];
use = (use + 1) % MAX;
return tmp;
}
sem_t empty;
sem_t full;
void* producer(void* arg) {
for (int i=0; i<loop; i++) {
sem_wait(&empty);
put(i);
sem_post(&full);
}
}
void* consumer(void* arg) {
int tmp = 0;
while (tmp != -1) {
sem_wait(&full);
tmp = get();
sem_post(&empty);
printf("%d", tmp);
}
}
int main(int argc, char* argv[]) {
..
sem_init(&empty, 0, MAX);
sem_init(&full, 0, 0);
}
상호배제 Mutual Exclusion 필요
두 개의 생산자가 동시에 Put할 경우,
첫 번째 세팅한 값이 두 번째에 의해 덮어질 수 있음
MAX 값이 2 이상일 때,
다수의 생산자/소비자가 있을 시 버퍼 접근할 때 경쟁조건이 발생함
== Mutaul Exclusion 필요함
상호배제 Mutaul Exclusion 추가
또 문제 발생
sem_t empty;
sem_t full;
sem_t mutex;
void* producer(void* arg) {
for (int i=0; i<loop; i++) {
sem_wait(&mutex); // p1
sem_wait(&empty); // p2
put(i); // p3
sem_post(&full); // p3
sem_post(&mutex); // p4
}
}
void* consumer(void* arg) {
for (int i=0; i<loop; i++) {
sem_wait(&mutex); // c1
sem_wait(&full); // c2
int tmp = get(); // c3
sem_post(&empty); // c3
sem_post(&mutex); // c4
printf("%d", tmp);
}
}
소비자가 먼저 동작함
sem_wait(&mutex)를 통해 락을 얻고,
sem_wait(&full)을 통해 임계 영역 접근도 얻으려 했으나,
버퍼가 비어있으므로 대기상태에 빠짐
생산자가 동작하려는데, sem_wait(&mutex)에서 음수가 됨
lock의 권한이 아직 소비자에게 있기 때문
둘 다 슬립 상태가 됨
최종 구현
sem_t empty;
sem_t full;
sem_t mutex;
void* producer(void* arg) {
for (int i=0; i<loop; i++) {
sem_wait(&empty); // p1
sem_wait(&mutex); // p2
put(i); // p3
sem_post(&mutex); // p3
sem_post(&full); // p4
}
}
void* consumer(void* arg) {
for (int i=0; i<loop; i++) {
sem_wait(&full); // c1
sem_wait(&mutex); // c2
int tmp = get(); // c3
sem_post(&mutex); // c3
sem_post(&empty); // c4
printf("%d", tmp);
}
}
int main(int argc, char* argv[]) {
..
sem_init(&empty, 0, MAX);
sem_init(&full, 0, 0);
sem_init(&mutex, 0, 1);
..
}
Reader-Writer Locks
병행 삽입/검색 연산
상황
- 삽입
- 리스트의 상태 변경, 임계 영역 필요
- 검색
- 리스트 변경 없이 읽기만 수행
- 삽입 연산이 없는 경우, 제한없이 병행 수행 가능
Writer
- 한 번에 하나씩 락 획득
- Reader나 Writer가 있으면 대기
Reader
- Writer 락 사용 중에는 대기
- Reader를 잡은 애가 있다면,
다수 진입 가능 (병행수행 ㅇㅋ)
writer는 한 번에 하나씩 락 획득
reader 또는 writer가 락을 사용 중이면 획득하지 못함
문제점
Reader가 한 명이라도 읽고 있으면,
Writer는 접근하지 못 하고 기다림
그러나, Reader들은 계속 들어올 수 있음
⇒ Writer는 접근하지 못 하고 기다림
식사하는 철학자
철학자는 생각하거나 먹음
먹으려면좌우 양쪽 젓가락
을 집어야 함
젓가락 = 공유자원, 상호배제 필요
목표
- Deadlock이 없어야 함
- 굶어 죽는 철학자가 없어야 함
- 병행성을 최대로 유지해야 함
세마포어로 관리하기 → 문제 발생
sem_t forks[5]; // 처음에는 For문 1로 초기화
int left(int p) { return p; }
int right(int p) {
return (p + 1) % 5; // 5명
}
void getForks() {
sem_wait(forks[left(p)]);
sem_wait(forks[right(p)]);
}
void putForks() {
sem_post(forks[left(p)]);
sem_post(forks[right(p)]);
}
왼쪽 포크를 잡고, 오른쪽 포크를 잡음
내려 놓을 때도 왼쪽부터 내려놓음
→ Deadlock 발생
= 5명의 철학자가 동시에 젓가락 잡으면 사이클이 발생함
식사하는 철학자 DeadLock 해결
의존성 제거 ⇒ 한 명의 철학자만 포크 집는 순서를 바꿈
원형 큐로 되어 있으니 마지막 철학자가 right를 잡게하면 됨
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)]); } }
동시에 먹을 수 있는 철학자 수 제한 (병행성 제한)
데드락 발생 시 모두 굶어 죽으니 제한해버림 (병행성 떨어짐)
여분의 포크 제공
제마포어 구현
Lock + 조건 변수로 구현
typedef struct __Zem_t {
int value;
pthread_cond_t cond;
pthread_mutex_t lock;
} Zem_t;
void Zem_init(Zem_t* s, int value) {
s->value = value;
Cond_init(&s->cond);
Mutex_init(&s->lock);
}
void Zem_wait(Zem_t* s) {
Mutex_lock(&s->lock);
while(s->value <= 0) // value가 음수가 되지 않음
Cond_wait(&s->cond, &s->lock);
s->value--; // value--를 먼저 하지 않은 이유: 음수 안되게
// + 하드웨어 지원이 없으므로 동시성 문제 해결하고자 검사를 먼저함
Mutex_unlock(&s->lock);
}
void Zem_post(Zem_t* s) {
Mutex_lock(&s->lock);
s->value++;
Cond_signal(&s->cond);
Mutex_unlock(&s->lock);
}
세마포어와 다른점
세마포어는 초기값에 음수가 불가능
제마포어는 가능
세마포어는 수행중에 값이 음수가 될 수 있음
제마포어는 0 아래로 내려가면 wait 시킴
'Computer Science > Operating System' 카테고리의 다른 글
[OS] 32장: Common Concurrency Problems (1) | 2024.07.05 |
---|---|
[OS] 30장: Condition Variables (0) | 2024.07.03 |
[OS] 28장: Locks (0) | 2024.07.02 |
[OS] 19장: TLB (Translation Lookaside Buffers) (1) | 2024.07.01 |
[OS] 18장: 메모리 가상화의 Paging (0) | 2024.06.30 |