세마포어의 동작 원리는 다음과 같다.
- sem_wait(&s): s의 값이 1이여야 critical section에 접근할 수 있다.
0이하에서 시작할 경우 blocked 상태로 변경된다.- sem_post(&s): s의 값이 -1 이하일 경우 blocked 상태에 놓여있는 쓰레드/프로세스를 깨운다.
1에서 critical section으로 접근하면 0이 되고 schedule이 발생한다. 이후 다른 쓰레드가 접근하려 할 때, blocked 상태가 된다.
세마포어는 상호배제로 사용할 수도 있고, CV로도 사용할 수 있다. 전자의 경우 혼자 lock, unlock을 수행하지만 CV로 사용할 경우 디버깅이 힘들다. 마치 if문의 형태처럼 mutex는 알기 쉬우나 CV는 버그를 알아차리기 힘들다는 것이다.
Correctness를 파악하기 힘들다.
Deadlock by semaphore
위의 코드는 세마포어가 프로그램 상에서 흩어져 있을 때의 데드락을 유발하는 코드이다.
이전에 확인한 코드이다.
Readers-Writers Problem
생산자 소비자 문제와 유사하지만 차이가 존재한다.
- Readers: read 행위 자체는 동기화가 필요 없으므로 다수의 reader가 shared resource를 읽을 수 있다.
- Writers: writer는 읽기, 쓰기 모두 할 수 있다. 쓰기를 할 때 reader는 share resource를 읽을 수 없다. 일관성 문제가 발생하기 때문이다.
그럼 writer는 공유된 자원에 하나밖에 들어가지 못한다. reader는 다수가 들어갈 수 있다.
그럼 read_count 변수를 통해 가드를 조정하면 된다.
read_count도 공유 자원이며 mutex가 필요하다. semaphore 변수를 1로 설정한다.
reader가 읽는 중일 때, writer를 못 들어오게 하기 위해 semaphore 변수를 1로 설정한다.
reader의 경우, 가드를 초기의 reader가 친 경우, 이후 reader는 자유롭게 들어올 수 있다.
하지만 이는 readers preferenced 되어 있다. 왜냐하면 reader가 많다면 writers는 starvation이 발생한다.
세마포어 변수 rsem이 하나 더 생긴 것을 확인할 수 있다. 이러한 이유는 writer에게 우선순위를 주기 위함이다.
rsem은 다수의 reader가 들어올 수 있도록 허용하되, writer가 잡았을 경우 reader를 막기 위함이다. 다수의 reader를 허용할 수 있도록 빠르게 rsem을 풀어야 한다.
그러나, reader가 rsem을 해제하기 전에, writer가 들어온다면, writer가 rsem에서 대기하게 된다. 그리고 reader가 들어온다면 얘네들도 rsem에서 대기한다.
여기서까지도 writer에게 우선순위를 주려면, guard를 한번 더 쳐야한다. 최대 하나의 reader 또는 writer만 rsem에서 대기할 수 있게 하는 것이다.
밑에 부분은 뇌피셜이다.
가드 z를 치지 않은 경우 reader가 rsem, wsem을 잡았을 때의 동작 방식을 알아보자.
- reader가 rsem을 잡고 들어왔을 때: rsem을 reader가 잡고 들어온 상태에 write 하나가 lock을 시도한다면, rsem에 잡힐 것이다. 이후에 들어오는 reader들은 모두 rsem에 잡히기 때문에, rsem에 존재하는 writer가 가장 먼저 나온다.(FIFO로 먼저 나오는 경우)
- reader rsem signal 이후 wsem에 있을 때: rsem에서 나온 writer는 wsem에 잡히게 될 것이다. 이후 들어오는 write들은 전부 wsem에 잡힌다. wsem을 잡고 read를 수행하던 reader가 모두 끝이나고 writer가 writer를 수행한다. 우선순위가 보장된 것이다.
- writer가 rsem을 먼저 잡았을 때: 위에서 writer가 resem을 풀고 나왔을 때와 똑같이 동작한다. 풀고 나왔을 때, wsem을 대기한다면 기존에 read를 수행하던 reader들이 끝나고 writer가 write를 수행한다. writer가 대기하지 않고 wsem을 잡는다면 바로 수행한다.
문제점
그런데 이게 여전히 reader에게 우선순위가 있다는 것은 rsem에 다수의 reader가 있어서 그런 것인데, 만약에 R1이 rsem을 잡고 rsem을 풀기 전에 W1이 왔다고 가정하자. W1도 잠들고 뒤따라 오는 R2, R3도 rsem에 잠든다. 그리고 W2는 y에 잠든다고 하자.
다시 R1으로 스케줄 되어 rsem을 풀었을 때, FIFO 전략이라면 당연히 W1이 먼저나오고 rsem을 잡은 상태에서 wsem에서 대기한다. 그 이후 y에 있던 W2도 내려와 wsem에서 대기한다. 그러면 z가 없어도 충분히 우선순위가 보장된 것으로 보인다. FIFO일 때만 가능한 것일까?
z가 필요한 이유는 blocekd ready 전략이 FIFO가 아니라 그런 것인가? 그런데 우린 세마포어에 사용되는 자료구조를 Queue라고 칭하고 진도를 나갔다.
