동기화 툴(Synchronization Tools: Semaphore, Mutex)

개념

Atomic operation: 더 이상 나눌 수 없는(indivisible) 하나 이상의 명령들로 구성된 함수나 행동
Critical section: 코드의 일부로, 공유 자원에 접근해야 해서 다른 프로세스와 동시에 접근할 수 없는 영역
Deadlock: 두 개 이상의 프로세스가 다른 프로세스의 행동을 기다리느라 진행할 수 없는 상황

<교차로에서 차가 멈춰 선 상황과 비슷>

Livelock: 두 개 이상의 프로세스가 다른 프로세스에 반응하느라 계속 상태를 바꾸는 상황 (유용한 작업이 일어나지 않음)
비슷한 예로 복도에서 마주친 두 사람이, 같은 방향으로 움직여 서로 지나가지 못하는 상황을 생각할 수 있음

<Livelock의 예시>

Mutual exclusion: 하나의 프로세스가 critical section에 들어가 있으면 다른 프로세스는 해당 section에 들어가 공유자원을 활용할 수 없다는 성질
Race conditon: 여러 스레드나 프로세스가 공유 데이터를 읽고 써서 최종 결과가 프로세스들의 상대적인 실행 순서에 의존하는 상황

Starvaton: 실행 가능한 프로세스가 스케줄러에 의해서 계속 무시당하는 상황(우선순위가 낮거나 하는 이유로)

동시성 프로그래밍의 어려운 점:

• 동시성 프로세스(스레드)는 자원을 공유(ex. 전역 변수)할 일이 생기는데, 이때 deadlock, race condition 등의 문제가 발생할 수 있음
• OS가 자원을 최적으로 할당하는 것이 어려움
• 프로그래밍 에러 찾기 어려움(에러가 자주 발생하는 것이 아니기 때문에) -> 디버깅도 당연히 어려움

critical section 조작 시 주의 사항:

• 프로세스가 공유 자원을 조작하는 코드를 실행할 때, 프로세스가 critical section(CS)에 있다고 함
• critical section에서의 실행은 mutually exclusive한 성질을 가져야 함(CPU가 많더라도 critical section에서는 프로세스 하나만 실행)
• critical section이 아닌 부분을 remainder section(RS) 라고 함
  코드를 CS와 RS로 나누었을 때, 언제 공유 자원에 접근이 일어나는지 entry section과 exit section을 명확하게 해야 함
  

예시) 공동 냉장고에 우유 채우기

상황: 나랑 룸메이트랑 냉장고(공유 자원)를 같이 쓰는데, 냉장고에 우유가 없으면 우유를 사러 감
Q: 어떻게 한 명만 우유를 사 올 수 있을까? 지금 냉장고가 비었는데, 룸메이트가 우유를 사 올까?

A1. 우유 사러 갈 때, 냉장고를 잠근다.
P: 룸메이트는 내가 돌아올 때까지 냉장고를 쓰지 못함

A2. 메모를 남겨 두자

• 우유가 없는데, 메모가 없으면, "내가 우유 사올게" 메모 남김 -> 우유 사 와서 -> 메모 제거
  P: 괜찮아보이지만, context switch 일어나면..? 메모가 없겠지?
• 가끔 에러가 발생할 수 있음 -> critical section 문제 해결 안 됨
  

A(2.5). 메모를 먼저 남기자
P: 컴퓨터는 메모를 구별할 수 없으니까, 메모 남아있으면 우유 안 삼,
세밀하게 프로그램 설계하다보면 오류 가능성 있음

A3. 각자 다른 메모지를 사용해 메모를 남기자
P: Deadlock 문제 발생 가능(서로 상대 메모가 없어지기를 기다림)

A4. 상대 노트가 있으면 wait, 없으면 우유 사러 감
P: 너무 복잡함, A와 B의 코드가 다름(비대칭적)

A5. 일종의 lock을 생각, 둘 중 한 명만 우유에 접근 가능하게
- 이런 lock이 뮤텍스, 세마포어

세마포어(다익스트라, 1968): P와 V operation 있음

• P: 독일어 proberen에서 유래, "테스트한다"는 뜻
  - while(s==0) {wait}; s=s-1
  • 플래그를 확인했을 때, 0이면(다른 프로세스가 사용 중) 대기, 1이면 0으로 바꿈(다른 프로세스가 공유자원 사용 못하게)
• V: verhogen에서 유래, "증가시킨다"는 뜻
  - 공유자원 사용 후 플래그를 증가시킴(자원 사용 가능하다는 뜻)

<세마포어를 사용했을 때 프로그램 흐름>

1. flag 1로 시작
2. 프로세스 A가 공유자원 접근(P)
3. flag가 0으로 바뀜
4. 프로세스 B가 접근 시도(P), wait
5. 프로세스 A가 공유자원 다 쓰고 반환(V)
6. wait 중이던 B가 공유자원 사용
   ...

카운팅 세마포어(counting semaphore): 이때는 s값이 2 이상, s 값이 사용 가능한 자원의 수를 의미
ex) 프로세서, I/O 등등

컨텍스트 스위치가 문제이면 interrupt를 무시하게 만들면 안 됨?

• scheduling granularity(스케줄링이 미세한 정도, granularity: 미세한)에 따라 실행 시간을 보장 못 할 수 있음

P: 구현하기 너무 복잡(스레드 개수 증가하면 P,V 상태를 추적하기 어려움, P만 하고 V 놓칠 수도)
, 너무 세밀하게(small granularity) 프로그램을 설계하면 Race condition 발생, 너무 크게(large granularity) 설계하면 CPU 활용도 떨어짐

• Counting 세마포어 아니면 잘 안 씀

Spin Lock, Writer/Reader Lock, Monitor 등 여러가지 방법이 있지만, 뮤텍스라는 간단한 방법을 많이 이용

뮤텍스(Mutex):
1. Atomicity
2. Singularity
3. Non-busy wait조건을 만족하는 lock

• 세마포어보다 가벼움, pthread에서 제공
• pthread_mutex_init으로 생성, pthread_mutex_lock으로 잠금, pthread_mutex_unlock으로 잠금 해제, pthread_mutex_destroy로 제거

P: Priority Inversion:
우선순위가 3순위(t3)인 프로세스가 mutex를 통해 자원을 잡고 있어, 더 높은 우선순위(1순위, t1)를 가지는 프로세스가 해당 프로세스 종료까지 자원을 사용하지 못함. 그런데 2순위 프로세스(t2)가 3순위 프로세스(t3)를 밀어내고 실행되면서 우선순위가 뒤바뀐 것처럼 보이는 현상

S: Priority inheritance
3순위 프로세스(t3)의 우선순위를 1순위 프로세스(t1)의 우선순위로 격상시킴(우선순위 상속) -> 3순위 프로세스가 종료되고(t3) 1순위 프로세스에게 자원을 넘겨줌(t1) -> 우선순위가 지켜짐

References.

1. 강순주 교수님 PPT
2. Operating System Concepts_10ed. Abraham_Silberschatz
3. https://www.baeldung.com/cs/deadlock-livelock-starvation