[운영체제] Process Synchronization 2 : 임계 구역, Synchronization Hardware, 세마포어, Block & Wake up, Dead lock and Starvation

본 포스팅은
https://core.ewha.ac.kr/publicview/C0101020140404144354492628?vmode=f 강의를 참고하여 정리했습니다.
(반드시 이전 포스팅을 학습하고 읽어주세요)

---

임계구역 프로그래밍하기

프로그램을 작성할 때, 개발자 입장에서 임계 구역 코드 앞뒤로 다른 프로세스가 접근하지 못하게 막아야 한다고 했다.

그럼 프로세스 끼리도 통신이 가능해야 얘가 들어갔는지 알 수 있을 것 아닌가?
그래서 프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있다. 이를 Synchronization Variable이라 한다.

프로그램 해결법의 충족 조건

• Mutual Exclustion (상호 배제)
  - 한 프로세스가 임계구역 부분 수행 중이면 다른 프로세스들은 들어가면 안된다.
• Progress
  - 임계구역 비어있으면 입장 원하는 프로세스가 들어가게 해줘야 한다.
• Bounded waiting (유한 대기)
  - 프로세스가 임계구역 들어가려고 요청한 후 부터 허용될 때까지 유한하게 대기해야 된다. 무한 대기 안된다.

프로그램을 짤 때, 위 3가지를 모두 만족하는 코드를 작성해야 된다는 것이다. 너무너무 당연한 내용들이다.

프로그램 코드 예시 1

프로세스 마다 turn 값이 있다. P0은 turn = 0, P1은 turn = 1
내 차례면 들어가고, 나와서 상대방에게 턴을 주는 것이다.

이 방법은 직관적으로 봐도 문제가 많다. 내가 끝나고 상대에게 줬는데, 상대가 안하고 있으면? 나는 무한 대기를 해야된다.
위 3가지 척도를 기준으로 평가한다면

• 상호 배제 : ㅇㅋ 한개만 들어가는 건 ㅇㅈ
• progress : 비어있는데도 상대 턴이면 난 못들어간다 ㅅㅂ
• Bounded waiting : 상대 턴에 무한히 안 쓰면 난 못들어간다 ㅅㅂ

ㅈㄴ 구린 코드인 것이다.

프로그램 코드 예시 2

이번엔 프로그램 마다 깃발이 있다. 한 flag[] = true면 누가 쓰고 있다는 뜻이다.
위 코드를 해석해보자.

• 나 들어가고 싶으니까 내 깃발 true라고 해둬야지
• 상대방이 쓰고 있나? 그렇다면 대기
• 비어있으면 내가 들어가서 쓰자
• 끝났으면 내 깃발 false라고 하자.

위 코드는 어떠한가? 3가지 척도를 기준으로 평가해보자면

• 상대방이 쓰고 있으면 못들어간다 => Mutual exclusion OK
• Progress => 괜찮은거 같은데?
• Bounded waiting => 잘 모르겠는데?

근데 여기서 하나 간과한게 있다. 만약 1번째 줄까지 실행하고 context switching이 발생한다면?
둘다 깃발을 true로 들어놓게 된다면? 둘다 무한 대기가 걸린다. 결국 비었는데도 못들어가고, 무한대기까지 걸린다.
그럴싸하지만 구린 코드인 것이다.

프로그램 코드 예시 3 : 피터슨 알고리즘

코드 1,2(턴 + 깃발)를 섞어서 피터슨이 만든 코드다. 딱봐도 이름 걸렸으면 믿음이 간다. 식당도 이름 걸면 있어보이지 않는가?

• 나 들어가고 싶으니 flag true로 두자.
• 턴을 상대에게 주자.
• 상대도 들어가고 싶어하면서 and 상대 턴이면 기다리자.
• 아니면 내가 쓰자.
• 썼으면 flag false로 두자.

별거 아닌 코드 같은데, 한 줄 한 줄마다 context switching이 발생해도 3가지 조건을 충족할 수 있다. ㅈㄴ 잘짠 코드인 것이다.

문제는, While문이다. CPU 돌아가는 동안 계속 while문을 돌리고 있어야 한다. 이를 Busy waiting(=spin lock)이라고 한다.
CPU와 memory를 쓰면서 기다려야 하는 자원 낭비가 쪼금 있는 것이다.

Synchronization Hardware

근본적인 문제의 원인을 생각해보자.
동시에 여러 프로세스가 공유 자원을 접근하려고 할때, 자원의 동기화 문제가 생긴다.
왜?
왜?
왜?

결국 CPU instruction이 한번에 읽기 + 쓰기가 안되니까 그런거 아닌가?

인터럽트가 걸리든 시스템 콜이 걸리든, CPU는 일단 하고 있는 명령어 1줄까진 끝내고 change를 한다. 그럼 이 한줄에 읽기 + 쓰기가 되면
아무 문제가 없는 것이 아닌가?

하드웨어 적으로 Test & Modify를 atomic(한번에, 못 쪼개고 한방에) 수행할 수 있도록 지원한다면 다 해결이 된다.

읽고 쓰기가 원콤에 된다고 가정해보자.

• while(Test and set(lock)) : 비었나?(읽기) + 나 쓸게 lock = true로 바꿈 (쓰기)
• 끝나면 lock = false

이러면 아무런 문제가 없는 것이다.
요걸 실제 컴퓨터에서 있고, 세마포어, 락 등을 사용해서 구현이 가능하다.
디테일한 방법은 다음 시간에 계속...

세마포어

• 앞 방식들을 추상화 시킴
• Semaphore S : 정수 변수, 아래 두 가지 atomic 연산에 의해서만 접근 가능
  
  여기서 P(S)는 획득, V(S)는 반납이라고 생각하면 쉽다.
  자원이 0 이하면 자리가 없으니 기다리고, 아닐 경우 자원 하나 차지하고 사용을 한다.
  나올 땐 S 값을 하나 키워주면 된다.
  여기서도 while 문이 있으니, 운 없으면 CPU burst time에 하루 종일 while문 실행만 하다 끝날 수 있다. (busy-wait)

그래서 다른 방법으로도 구현이 가능한데, 그것이 Block & Wake Up 방식이다.

Block & Wake Up

앞에서 본 그림이다. CPU가 I/O 작업을 하러 갈 경우, 상태가 blocked가 되어 CPU 사용을 못한다.
I/O 작업 큐에서 기다리다가 완료하면 ready 상태가 되서 다시 CPU 사용 줄에 줄 스는, 그런 방식인데, 이를 활용한 것이다.

이 방식은 Queue를 하나 만들고, 대기열을 만든다. 그림처럼 PCB를 연결지어서 말이다.
block은 공유 자원 쓰려고 대기열 들어갔을 경우 CPU를 block으로 바꿔 그 동안 CPU 못 쓰게 하고,
Wake up은 다 썼으면 block된 프로세스를 다시 ready queue에 넣는 동작인 것이다.

일단 -1를 했을 때 음수면(to 없는 경우) '아 바로 못 쓰겠네, 줄 서야 겠네' 하면서 자신을 block 상태로 만든다.
V(S)는 다른 프로세스가 자원을 다 사용했을 경우, +1 해주고 0이하면(block 된 누가 있음) 그를 깨워주는 것이다.

busy-wait vs block & wake up

• 임계 구역이 긴 경우 : block & wake up이 적당
• 임계 구역 매우 짧은 경우 : block & wake up 오버헤드가 더 클 수 있음
• 일반적으로는 block & wake up이 좋음

busy-wait : while문으로 CPU 사용
block & wake up : PCB 상태 변경 (ready, blocked) 오버헤드 발생

문제가 있다. 따라서 공유 자원을 쓰는 시간에 따라 개발자가 결정하면 좋을 것이다.

Two types of Semaphores

1. Counting semaphore

• 도메인 0 이상인 임의 정수 값(4,5,6...)
• 주로 resource counting에 사용

2. Binary sempahore(=mutex)

• 0 또는 1만 가질 수 있는 semaphore
• 주로 mutual exclusion(block/unlock)에 사용

Dead lock and Starvation

Dead lock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

S와 Q 자원 둘다 동시에 필요한 경우가 있는데,
P0은 S를 집었고, Q를 집으려고 했는데 CPU time이 만료되서 P1이 Q를 차지했다.
서로가 서로의 것이 필요한데 놔줄 수가 없다. 놔주는 건 아래 V에서 반환하니까, 서로 무한히 대기하는 것이다.

이를 해결하려면 의존 관계를 설정하면 좋을 것이다.
Q를 집으려면 이미 S가 있게, 서로 의존하는 경우 둘 다 가질 수 있어야 집을 수 있게 하는 것이다.

Starvation

CPU starvation은 우선순위가 밀려 영원히 CPU를 사용할 수 없는 현상인데,
여기서는 세마포어 큐에서 무한히 대기하는 것을 말한다.

식사하는 철학자 문제 :

그림과 같은 상황을 생각해보자. 젓가락 2개가 모두 있어야 밥을 먹는다.
이 상황에선 데드락, 스타베이션 둘 다 발생할 수 있을 것이다.
데드락 : 5명 모두가 동시에 왼쪽 젓가락을 들면? 영원히 밥 못 먹는다. 코드를 보면 알 수 있듯 밥을 먹고 젓가락을 내려놓기 때문이다.

스타베이션 : 내 왼쪽 젓가락을 옆사람이 쓰고 있다. 저거 내려놓으면 먹을 수 있겠지? 왼쪽 젓가락을 내려놨는데 이번엔 오른쪽 젓가락을 쓴다. 이런 시발. 굶어 죽겠네