[운영체제] 5장: Concurrency: Mutual Exclusion and Synchronization

Race Condition

• 여러 프로세스나 Thread가 공유 자원을 동시에 읽거나 쓰려고 할 때 발생한다.
• 실행 순서에 따라 프로그램의 결과가 달라질 수 있다.
• Concurrency Control: Race Condition이 발생하지 않도록 제어하는 것
• Critical Section: 프로그램의 일부 코드로, 공유 변수를 사용함으로써 문제 발생이 가능한 부분이다.

Mutual Exclusion

• 소프트웨어적 접근

- Mutual Exclusion 보장
- 교대로 작업하기 때문에 상대 프로세스가 fail 하거나, critical section에 도달하는 데에 오랜 시간이 걸리거나, 더 이상 critical section 진입을 시도하지 않는다면, critical section 진입이 불가할 수 있다.
- Busy-waiting 발생: turn 값이 상대 값일 때 프로세서를 할당 받는다면 while 문을 반복하는 데에 시간을 다 쓰게 된다.

- Mutual Exclusion 보장 X
- flag 값이 둘 다 false 인 상태에서 while 문 탈출 직 후에 프로세서가 상대에게 넘어가면, 둘 다 critical section에 진입할 수 있는 상황이 발생한다.

- Mutual Exclusion 보장
- Deadlock 발생 가능: P0의 flag[0] = true 수행 직후 P1의 flag[1] = true 가 수행된다면 프로세스 둘 다 while 문 탈출이 불가능해진다.
- 교대로 작업하는 것이 아닌 상대 flag가 false 이기만 하면 연속 재진입이 가능하다.
<증명>
1. P0와 P1이 동시에 critical section 에 진입했음을 가정한다.
2. P0가 critical section에 진입하려면 flag[0] = true, flag[1] == false 확인 작업이 필요하다.
3. 이러한 상황에서 P1이 critical section에 진입하려면 P0의 flag[0] = true 가 수행되기 전에 flag[1] = true, flag[0] == false 확인 작업이 필요하다.
4. 이때 P0의 flag[1] == false 확인이 모순이 된다.
5. 따라서 Mutual Exclusion 이 보장된다.

- Mutual Exclusion 보장
- Deadlock 발생 X
- Livelock 발생 가능: while 문을 실행하고 있는 동안에 상대편의 flag 값이 바뀔 가능성이 있기 때문에 while 문 탈출이 가능하다.
- 교대로 작업하지 않는다.

[Dekker's Algorithm]
- Mutual Exclusion 보장
- turn 값이 상대편 값이면 내 flag 값을 false 로 변경하여 차례를 양보한다.
- Deadlock, Livelock, Starvation 발생 X
- 상대 프로세스가 critical section에 진입할 의사가 없다면 현재 프로세스는 대기 없이 바로 진입 가능하다.
< 둘 다 critical section에 진입하려는 상황에서 turn == 0 >
- P0은 while (flag[1]) 을 반복한다.
- P1는 turn 값이 0임을 확인 후에 flag[1] = false 를 수행하고 while (turn == 0) 을 반복한다.
- P1이 Timeout 되고 P0가 실행 됐을 때 flag[1] == false 를 확인하고 while (flag[1]) 을 탈출하면서 critical section 에 진입하게 된다.
< 둘 다 critical section에 진입하려는 상황에서 P0가 먼저 진입했을 때, 작업 후에 또 다시 P0가 진입하는 경우 >
- turn == 0 일 때, P1은 flag[1] = false 수행 후 while (turn == 0) 반복한다.
- P1의 Timeout 후에 P0는 flag[1] == false 를 확인하고 critical section 을 수행한다.
- critical section 작업을 끝낸 후에 재진입을 시도하면 flag[1] == false 이기 때문에 대기 없이 바로 수행 가능하다.
- 재진입 전에 turn 값은 1로 변경되고, P0가 계속 실행되는 동안 turn 값의 변화는 발생하지 않는다.
- 이후 P0가 어떤 지점에서 실행 중단 되든 간에 P1는 while (turn == 0) 을 탈출하고 flag[1] = true 수행 후 flag[0] 이 false 가 되기만을 기다린다.
- P0는 turn == 1 을 확인하여 flag[0] = false 수행 후 while (turn == 1) 반복한다.
- 최종적으로 P1의 critical section 진입이 가능해지고 Starvation 이 발생하지 않는다.
< while (flag[1]) 반복 -> while (turn == 1) 반복 상황 >
- 불가능
- while (flag[1]) 반복 조건: flag[1] == true, turn == 0
- while (turn == 1) 반복 조건: turn == 1
- P0의 while 문 내에서 turn 값이 바뀔 수 없고, P1에서는 turn = 1 코드가 없기 때문이다.
< while (turn == 1) 반복 -> while (flag[1]) 반복 상황 >
- 가능
- while (turn == 1) 반복 조건: turn == 1
- while (flag[1]) 반복 조건: flag[1] == true, turn == 0
- P1의 critical section 작업 완료 후 turn = 0 까지만 수행되고 프로세서가 넘어가면 가능하다.

[Peterson's Algorithm]
- Mutual Exclusion 보장
- 교대 진입이 불필요하고, 다른 프로세스가 critical section 진입 의사가 없으면 대기 없이 바로 진입 가능하다.
- Deadlock, Livelock, Starvation 발생 X
- 둘 다 critical section에 진입하려는 상황에서, 먼저 turn 값을 상대 값으로 바꾼 프로세스가 먼저 critical section 에 진입하게 된다.
- 둘 다 critical section에 진입하려는 상황에서, 한 프로세스의 critical section 수행 후에 재진입이 불가능하다. (turn)
<증명>
- P0의 critical section 진입 조건: flag[1] == false OR turn == 0
1. flag[1] == false
- P1의 flag[1] = true 수행 전에 P0가 실행되면 critical section 진입 가능
- P1의 진입 시도에서 while (flag[0] && turn == 0) 에서 걸리기 때문에 critical section 진입 불가능
2. turn == 0
- P0의 turn = 1 먼저 수행 후 P1의 turn = 0 수행
- P0 critical section 진입
- P1의 진입 시도에서 while (flag[0] && turn == 0) 에서 걸리기 때문에 critical section 진입 불가능

Process Interaction

• 프로세스 간에 자원을 차지하기 위해 경쟁한다.
• 프로세스 간에 데이터나 자원을 공유한다.
• 프로세스 간에 통신한다.
• 이 같은 프로세스 간 상호작용 때문에 Concurrency Control이 필요하다.

Control Problems

• 프로세스 상호작용에 의해 발생하는 문제
• Mutual Exclusion: Critical section, data concurrency
• Deadlock
• Starvation

Requirements for Mutual Exclusion

• 한 번에 하나의 프로세스만 critical section 진입이 가능해야 한다.
• critical section을 수행하고 있지 않은 프로세스가 다른 프로세스의 critical section 수행을 방해해서는 안된다.
• Deadlock과 Livelock 은 없으면 좋다.
• 어떠한 프로세스도 critical section을 수행하고 있지 않을 때, critical section에 바로 진입 가능해야 한다.
• 프로세스 수나 상대적 프로세스 실행 속도에 대한 가정은 없어야 한다.
• critical section에 진입한 프로세스는 유한한 시간 동안에만 수행할 수 있다.

Hardware Instruction

• 하나의 instruction 처럼 동작하기 때문에 중간에 interrupt가 발생하지 않는다.

[Compare & Swap Instruction]
- bolt == 0 일 때 가장 먼저 compare_and_swap() 을 실행한 프로세스가 critical section 에 진입한다.
- 동시에 여러 프로세스가 bolt 값에 접근하는 것이 불가능하기 때문에 여러 프로세스가 동시에 실행되는 상황에서도 사용 가능하다.
- Mutual Exclusion 보장
- Busy-waiting O

[Exchange Instruction]
- bolt == 0 일 때 가장 먼저 exchange() 를 실행한 프로세스가 critical section에 진입한다.
- 일시적으로 여러 프로세스의 keyi 값이 동시에 0 인 상태가 나타날 수 있다. (한 프로세스의 critical section 및 bolt = 0 수행 후 다른 프로세스가 진입을 시도할 때)
- 반복문 없이 여러 critical section을 구현할 때 keyi 값의 초기화가 필수적이다.

• Advantages
  • 프로세스 개수에 관계 없이 적용 가능하다.
  • 간단하기 때문에 증명하기 쉽다.
  • 여러 개의 bolt 변수를 사용하여 여러 critical section을 구현할 수 있다.
• Disadvantages
  • Busy-waiting
  • Starvation: 한 프로세스의 critical section 실행 도중에만 Timeout 이 걸리는 경우
  • Deadlock: critical section을 1개만 구현할 때는 발생하지 않지만 여러 개를 구현할 경우에는 발생할 수 있다. (bolt = 0 수행 전에 fail?)

Software Approach, Hardware Instruction 모두 Busy-waiting 이라는 문제점을 가진다.

Semaphore

• 정수 변수 1개와 큐를 가지고 있는 구조체이다.
  • OS가 지원하는 기능이기 때문에 작동 방식을 수정할 수는 없다.
  • 대입, 산술, 연산에 사용할 수 없다.
• 정수 변수 s: critical section 진입 가능 여부를 확인하기 위해 사용되고, 시스템 콜을 통해서만 접근 가능하다.
  • Initialize: 0 이상의 값으로 초기화한다. 음수 X
  • SemWait: s 값을 1 감소시키고, 그 값이 0보다 작다면 프로세스를 Blocked 상태로 전이시킨다.
  • SemSignal: s 값을 1 증가시키고, 그 값이 0보다 작거나 같으면 Blocked queue에 있던 프로세스 하나를 Ready queue로 옮긴다.
  • s < 0: 절댓값 s 는 Blocked queue 에 있는 프로세스 수를 의미한다.
  • s > 0: Blocked 되지 않고 SemWait를 통과할 수 있는 프로세스 수를 의미한다.
• 큐: critical section에 진입 불가능할 때 프로세스를 대기시키기 위해 사용되며 대기하고 있는 프로세스가 프로세서를 차지할 경우는 없기 때문에 Busy-waiting 을 해결한다.
  • Strong Semaphores: FIFO
    • Starvation 발생 X
  • Weak Semaphores: 무작위로 Ready queue 로 보냄
    • Starvation 발생 가능

• Mutual Exclusion 보장
• Deadlock X
• Livelock X
• Busy-waiting X

• Binary Semaphore: s가 0 또는 1 값만을 가지기 때문에 하나의 프로세스만 critical section에 진입 가능하다.
  • s == 1, SemWait 통과
  • s == 0, SemWait -> Blocked
  • Blocked 상태의 프로세스가 여러 개여도 s 값은 항상 0이다.
  • s 값으로 Blocked queue에 있는 프로세스 수를 유추할 수 없기 때문에 직접 큐를 확인하는 작업이 필요하다.

Producer / Consumer Problem (대칭)

• 둘 중 하나라도 critical section을 수행 중인 경우 대기한다.

[Bounded Buffer]
- b 가득 찼을 때: producer 대기
- b 비었을 때: consumer 대기
- in, out 값 때문에 critical section 구현이 필요하다.

[3개의 Semaphore를 이용한 구현]
- s: critical section을 구현하기 위한 세마포어
- n: 사용 가능한 데이터 개수를 표현하기 위한 세마포어로 버퍼가 비었을 때 consumer를 blocked 시킨다.
- e: 버퍼의 빈 자리 개수를 표현하기 위한 세마포어로 버퍼가 가득 찼을 때 producer를 blocked 시킨다.
< Producer, semWait(s) -> semWait(e) ? >
- 버퍼가 가득 찼을 때, critical section에 먼저 진입한 후에 semWait(e)에서 Blocked 되므로 어떤 consumer도 critical section에 진입할 수 없고, 따라서 producer의 Blocked 상태를 해제할 수 없으므로 Deadlock이 발생할 수 있다.
< Consumer, semWait(s) -> semWait(n) ? >
- 버퍼가 비었을 때, critical section에 먼저 진입한 후에 semWait(n)에서 Blocked 되므로 어떤 producer도 critical section에 진입할 수 없고, 따라서 consumer의 Blocked 상태를 해제할 수 없으므로 Deadlock이 발생할 수 있다.

Monitors

- 여러 procedure와 지역 변수, 초기화 시퀀스, 컨디션 변수들로 구성된다.
< Characteristics >
- 지역 변수들은 모니터 안에서만 접근 가능하다.
- 프로세스는 모니터 내의 procedure 를 호출함으로써 모니터에 진입한다.
- 하나의 프로세스만 모니터에 진입 가능하기 때문에 Mutual Exclusion이 보장된다.
< Synchronization >
- 모니터에 의해서만 접근할 수 있는 컨디션 변수를 통해 동기화가 이루어진다.
- cwait(c): 해당 프로세스는 Blocked 시켜 큐에서 대기하도록 한다.
- csignal(c): 해당 컨디션 변수(큐)에 있던 프로세스를 모니터에 진입하게 한다.
- 컨디션 변수는 원하는 만큼 생성 가능하다.
+) 모니터 내에서 해야 할 작업이 남은 프로세스는 csignal 을 호출하면서 urgent 큐에서 대기하고, 큐에 있던 프로세스는 모니터에 진입한다.
+) 컨디션 변수에서 대기하고 있는 프로세스가 모니터 밖에서 대기하고 있는 프로세스보다 우선순위가 높기 때문에 먼저 모니터에 진입하여 작업을 종료한다.

• Producer / Consumer Problem

- 모니터 자체가 critical section이기 때문에 세마포어 s 를 구현할 필요가 없다.
- 세마포어 n, e 대신에 2개의 컨디션 변수를 사용하여 구현한다.
- producer의 append(x)와 consumer의 take(x), 그리고 버퍼는 모니터 안에서 구현된다.
- count: 세마포어 방식과 달리 critical section 내의 변수로 자유롭게 연산이 가능하다.
- Producer: 버퍼가 가득 차 있다면 notfull에서 대기하고 notempty의 consumer를 모니터로 꺼낸다.
- Consumer: 버퍼가 비어 있다면 notempty에서 대기하고 notfull의 producer를 모니터로 꺼낸다.
+) 세마포어 방식에서는 critical section에 먼저 진입한 뒤에 버퍼의 상태를 확인하면 Deadlock이 발생할 수 있다. 하지만 모니터 방식에서는 발생하지 않는다. 모니터 자체가 critical section으로, 모니터에 진입한 프로세스가 없다면 얼마든지 다른 프로세스의 진입이 가능하고 큐에서 대기하던 프로세스의 Blocked 상태를 풀어줄 수 있기 때문이다.

Readers / Writers Problem (비대칭)

• Conditions
  • 여러 reader들이 한 번에 데이터를 읽을 수 있다.
  • writer가 하나라도 데이터 쓰기를 작업한다면 어떠한 reader, writer 도 작업할 수 없다.

[Semaphore를 이용한 구현]
- wsem 큐에서 reader는 대표 한 명만 대기하고, 그 한 명이 critical section에 진입하면 semWait(x) 에서 대기하던 프로세스들도 우르르 진입하게 된다.
- readcount: 내가 첫 번째 reader 인지, 마지막 reader 인지를 확인하는 변수이다.
- readcount 자체가 공유 변수이기 때문에 readcount 연산을 critical section으로 구현한다.
- semWait(x): readcount 연산을 critical section으로 구현하기 위해 사용하고, 첫 번째 reader를 제외한 나머지 reader들이 대기하는 장소이다.
- reader가 critical section에 존재하는 상황에서 새로운 reader들이 진입하려고 하면 이미 대기하고 있던 writer를 제치고 먼저 진입한다. (reader 우선)