Semaphores: A Definition
semaphore는 value와 queue를 갖는 synchronization primitive이다. lock과 condition variable 두 가지로 사용할 수 있다.
sem_wait()와 sem_post() 두 함수가 있고, 그전에 먼저 초기화를 해줘야 한다.
Code: Initializing A Semaphore
#include <semaphore.h> sem_t s; sem_init(&s, 0, X); // X??
sem_init()의 세 번째 인자를 X로 초기화했다.
Code: Semaphore: Definitions Of Wait And Post
// P() int sem_wait(sem_t *s) { decrement the value of semaphore s by one wait if value of semaphore s is negative } // V() int sem_post(sem_t *s) { increment the value of semaphore s by one if there are one or more threads waiting, wake one }
sem_wait: value에 1을 빼고 value가 음수면 wait한다.(sleep)
sem_post(): value에 1을 더하고 value가 양수면 signal을 보낸다.(wake up)
Binary Semaphores (Locks)
semaphore를 lock처럼 사용할 수 있다.
P()를 여럿이서 호출하면 value가 음수가 되는데, 이 값이 lock을 기다리는 큐의 개수이다.
Code: A Binary Semaphore (That Is, A Lock)
sem_t m; sem_init(&m, 0, 1); // init with 0 sem_wait(&m); // critical section here sem_post(&m);X를 1로 초기화하면 Binary Semaphore라고 한다.(Lock이 1개)
sem_wait()에서 lock(), sem_post()에서 unlock()하므로 critical section
Trace: Thread 1개
Trace: Thread 2개
스레드가 두개여도 mutual exclusive하게 동작한다.
T1은 sem_wait()에서 lock을 얻었는데, T2로 context switching이 일어났다고 가정하자.
T1의 critical section에 T2가 들어가는 것처럼 보이지만 T2는 sem의 value를 보고 sleep한다. 따라서 lock을 얻지 못하고 다시 T1이 critical section을 끝낸다.
이후 T1이 sem_post()로 sem→value를 돌려놓고 T1을 깨운다.
binary semaphore는 이렇게 lock이 두 가지 상태만 갖는다.
Semaphores As Condition Variables
semaphore를 condition variable처럼 사용할 수도 있다. 이를 이용해 deterministic하게 만들 수 있다.(ordering)
Code: A Parent Waiting For Its Child
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[]) { sem_init(&s, 0, 0); // init with 1 printf("parent: begin\n"); pthread_t c; Pthread_create(c, NULL, child, NULL); sem_wait(&s); // wait here for child printf("parent: end\n"); return 0; }
Tracing: A Parent Waiting For Its Child 1
Tracing: A Parent Waiting For Its Child 2
The Producer/Consumer Problem
First Attempt
semaphore로 producer/consumer problem을 다뤄보자.
Code: The Put() And Get() Routines
int buffer[MAX]; int fill = 0; int use = 0; void put(int value) { buffer[fill] = value; // line F1 fill = (fill + 1) % MAX; // line F2 } int get() { int tmp = buffer[use]; // line G1 use = (use + 1) % MAX; // line G2 return tmp; }
put()은 fill이 가리키는 공간에 버퍼를 넣고 그다음 주소를 가리키게 한다.
get()은 use가 가리키는 공간에서 버퍼를 가져오고 그다음 주소를 가리키게 한다.
put()과 get()은 atomic하지 않으므로 앞뒤에 wait()과 post()로 lock을 해줘야 한다.
Code: Adding The Full And Empty Conditions
sem_t empty; // 빈자리가 몇개인지 들어있음 (예: 2개 -> 빈자리 2개) sem_t full; // item이 들어있음 void *producer(void *arg) { int i; for (i = 0; i < loops; i++) { sem_wait(&empty); // line P1 put(i); // line P2 sem_post(&full); // line P3 } } void *consumer(void *arg) { int i, tmp = 0; while (tmp != -1) { sem_wait(&full); // line C1 tmp = get(); // line C2 sem_post(&empty); // line C3 printf("%d\n", tmp); } } int main(int argc, char *argv[]) { // ... sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with... sem_init(&full, 0, 0); // ... and 0 are full // ... }producer()는 wait()으로 empty의 값을 확인해서 빈자리가 있는지 확인한다. 없으면 sleep하고, 있으면 lock()을 걸고 put() 한다. 이후 post()로 full을 증가시키고 unlock 한다.
consumer()는 wait()으로 full의 값을 확인해서 item이 들어있는지 확인한다. 없으면 sleep하고, 있으면 lock()을 걸고 get() 한다. 이후 post()로 empty를 증가시키고 unlock 한다.
하지만 empty의 value가 최대 2인 경우 아래처럼 race condition이 발생할 수 있다.
Tracing: Race condition
empty의 최댓값이 2이므로 Tp1이 empty에 lock을 걸어도 Tp2도 lock을 걸 수 있다.
따라서 critical section인 put()의 LD와 ST를 수행할 때 race condition이 발생 한다.
F1(LD)과 F2(ST)가 atomic하지 않아서 F2로 둘 다 같은 곳에 값을 쓴다.(race condition 발생)
A Solution: Adding Mutual Exclusion
race condition을 해결하기 위해 아래처럼 binary semaphore인 mutex를 추가했다.
Code: Adding Mutual Exclusion (use mutex but DeadLock)
sem_t empty; sem_t full; sem_t mutex; void *producer(void *arg) { int i; for (i = 0; i < loops; i++) { sem_wait(&mutex); // line p0 (NEW LINE) sem_wait(&empty); // line p1 put(i); // line p2 sem_post(&full); // line p3 sem_post(&mutex); // line p4 (NEW LINE) } void *consumer(void *arg) { int i; for (i = 0; i < loops; i++) { sem_wait(&mutex); // line c0 (NEW LINE) sem_wait(&full); // line c1 int tmp = get(); // line c2 sem_post(&empty); // line c3 sem_post(&mutex); // line c4 (NEW LINE) printf("%d\n", tmp); } } int main(int argc, char *argv[]) { // ... sem_init(&empty, 0, MAX); // MAX buffers are empty to begin with... sem_init(&full, 0, 0); // ... and 0 are full sem_init(&mutex, 0, 1); // mutex=1 because it is a lock (NEW LINE) // ... }기존 코드의 wait()과 post() 앞뒤에 mutex()를 이용해 critical section을 atomic하게 만들어 주었다.
하지만 이 코드는 아래처럼 DeadLock을 유발할 수 있다.
Trace: Deadlock 발생
Tc가 mutex lock을 얻고 wait()으로 sleep한다. 이후 Tp가 스케줄 되지만 mutex lock을 얻지 못해서 sleep 한다.
Solution: Avoiding Deadlock
mutex lock으로 empty와 fill을 감싸는 대신 반대로 empty나 fill로 lock을 얻고 나서 mutex lock을 걸도록 수정했다.
Code: Adding Mutual Exclusion (Correctly)
sem_t empty; sem_t full; sem_t mutex; void *producer(void *arg) { int i; for (i = 0; i < loops; i++) { sem_wait(&empty); // line p1 sem_wait(&mutex); // line p1.5 (MOVED MUTEX HERE...) put(i); // line p2 sem_post(&mutex); // line p2.5 (... AND HERE) sem_post(&full); // line p3 } } void *consumer(void *arg) { int i; for (i = 0; i < loops; i++) { sem_wait(&full); // line c1 sem_wait(&mutex); // line c1.5 (MOVED MUTEX HERE...) int tmp = get(); // line c2 sem_post(&mutex); // line c2.5 (... AND HERE) sem_post(&empty); // line c3 printf("%d\n", tmp); } } int main(int argc, char *argv[]) { // ... sem_init(&empty, 0, MAX); // MAX buffers are empty to in with... sem_init(&full, 0, 0); // ... and 0 are full sem_init(&mutex, 0, 1); // mutex=1 because it is a lock // ... }처음에는 버퍼가 비어있으므로 full은 0으로 초기화 해주고, empty는 버퍼의 최대 개수로 초기화 해준다. mutex lock을 empty나 full안에서 걸어주었다.
그러면 정상적으로 동작한다.
Reader-Writer Lock
여러 스레드가 한 메모리에 concurrent하게 read/write 한다고 가정했을 때, 동시에 read를 해도 상관이 없다.
이렇게 read와 write에 관해서 구현한 lock이 reader-writer lock이다. 이때 write에 관련한 lock은 한 스레드만 가져가야 한다.
Code: A Simple Reader-Writer Lock
typedef struct _rwlock_t { sem_t lock; // binary semaphore (basic lock) sem_t writelock; // used to allow ONE writer or MANY readers int readers; // count of readers reading in critical section } rwlock_t; void rwlock_init(rwlock_t *rw) { rw->readers = 0; sem_init(&rw->lock, 0, 1); sem_init(&rw->writelock, 0, 1); } void rwlock_acquire_readlock(rwlock_t *rw) { sem_wait(&rw->lock); rw->readers++; if (rw->readers == 1) sem_wait(&rw->writelock); // first reader acquires writelock sem_post(&rw->lock); } void rwlock_release_readlock(rwlock_t *rw) { sem_wait(&rw->lock); rw->readers--; if (rw->readers == 0) sem_post(&rw->writelock); // last reader releases writelock sem_post(&rw->lock); } void rwlock_acquire_writelock(rwlock_t *rw) { sem_wait(&rw->writelock); } void rwlock_release_writelock(rwlock_t *rw) { sem_post(&rw->writelock); }첫번째 reader가 lock을 얻으려고 시도하면 reader 수를 하나 증가시키고 sem_wait()으로 writelock을 얻는다. writelock은 마지막 reader가 unlock을 시도할 때만 반납할 수 있다. 따라서 첫번째 reader 이후로 read하려는 reader들은 writelock을 얻지 않고 read한다.
writer들은 reader와 공유하는 writelock을 얻은 첫번째 스레드만 write 할 수 있다.
Reader는 첫 번째 reader만 writelock을 얻으려 경쟁하고 Writer들은 Reader/Writer들과 경쟁해야 하므로 unfair하다.(Writer가 starve)
또한 Read와 Write가 복잡하면 overhead가 발생한다.
The Dining Philosophers
Dining Philosophers's problem은 concurrency problem 중 하나다.
Broken Solution
The getforks() And putforks() Routines
// 왼쪽 포크를 잡고, 오른쪽 포크를 잡는다. void getforks() { sem_wait(forks[left(p)]); sem_wait(forks[right(p)]); } // 왼쪽 포크를 내려놓고, 오른쪽 포크를 내려놓는다. void putforks() { sem_post(forks[left(p)]); sem_post(forks[right(p)]); } // basic loop of each philosopher while (1) { think(); getforks(); eat(); putforks(); } // 왼쪽 포크은 index가 같다. int left(int p) { return p; } // 오른쪽 포크는 index+1이다. int right(int p) { return (p + 1) % 5; }
자기 왼쪽 포크를 들고, 오른쪽을 원할 때 deadlock 발생
(race condition에 상관없이 순서 때문에 문제 발생)
A Solution: Breaking The Dependency
Code: dinning solution
void getforks() { // 마지막 p는 오른쪽 포크 먼저 잡기 if (p == 4) { sem_wait(forks[right(p)]); sem_wait(forks[left(p)]); } else { sem_wait(forks[left(p)]); sem_wait(forks[right(p)]); } }
마지막에서 실행 흐름을 바꿔 주면 deadlock을 방지할 수 있다.
How To Implement Semaphores
race condition과 deadlock을 해결했으니 performance를 고려해보자.
스레싱 현상이 발생할 수 있으니 오래 걸리는 영역은 sem을 따로 만들자.
zemaphore: value가 항상 0 이상이 되도록 구현
Implementing Zemaphores With Locks And CVs
typedef struct __Zem_t { int value; pthread_cond_t cond; pthread_mutex_t lock; } Zem_t; // only one thread can call this 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 ----------- Mutex_lock(&s->lock); while (s->value <= 0) Cond_wait(&s->cond, &s->lock); s->value--; Mutex_unlock(&s->lock); // ----------- mutex unlock --------- } void Zem_post(Zem_t *s) { // ----------- mutex lock ----------- Mutex_lock(&s->lock); s->value++; Cond_signal(&s->cond); Mutex_unlock(&s->lock); // ----------- mutex unlock --------- }
Uploaded by Notion2Tistory v1.1.0