[운영체제] Process Synchronization(2)

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

critical section: 공유 데이터에 접근하는 코드

remainder section: 공유 데이터가 아닌 데이터에 접근하는 코드

 

아무나 공유 데이터에 접근하면 문제가 발생하기 때문에 ciritical section이 실행되기 이전에 entrt section을 넣어서 lock을 먼저 걸어줌. 이걸 통해 여러 프로세스들이 동시에 critical section에 접근하는 걸 막음. 그리고 프로세스가 끝나면 lock을 풀어줌

 

Mutual Exclusion: 하나의 프로세스가 critical section에 있으면 다른 프로세스들은 critical section에 접근x

Progress: 아무도 critical section에 없을 때, 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해줌

Bounded Waiting: 유한 대기. 특정 프로세스 입장에서 critical section에 들어가지 못해 starvation이 발생하지 않게. 예를 들어 세 개의 프로세스가 대기하고 있는데, 두 개의 프로세스만 계속 이용하고 나머지 하나는 이용하지 못하는 상황을 방지.

---

turn: 프로세스의 차례. turn이 0이면 0번 프로세스의 차례, 1이면 1번 프로세스의 차례

critical section에 들어가기 전에 while문에서 turn을 확인. 사전에 turn을 0으로 설정했기 때문에, turn이 0이 아닐 때 까지 기다리다가 turn이 1이 되면 그때 critical section으로 들어감. 그리고 critical section에서 나오면 다시 turn을 1로 바꿔서 순서를 프로세스1에게 넘겨줌.

Mutual exclusion은 만족.

---

flag: critical section에 들어가고자 하는 표시

프로세스가 critical section에 들어가고싶으면 flag를 1로 변경.

그 다음 또 다른 프로세스의 flag가 1인지 확인. 1라면 계속 대기하다가 상대방의 flag가 0으로 변하면 그때 critical section에 들어갔다가 작업이 끝나면 다시 flag를 0(false)으로 변경해줌

하지만 만약 프로세스가 0이 flag만 1로 바꾼 상태에서 CPU가 프로세스1에게 넘어가면, 둘 모두 critical section에 들어가기 전에 flag를 들어서 아무도 critical section에 진입하지 못하는 상태 발생

---

1. flag를 1로 바꾸고

2. turn을 상대방의 순서로 설정

3. 상대방의 flag가 1이고 turn 역시 상대방 일 때에는 상대방의 순서가 끝날 때까지 대기

4. 상대방의 flag가 0이거나, turn이 상대방이 아닌 자신이라면 critical section 진입

5. critical section이 끝난 뒤에는 flag를 0으로 변경해서 상대방이 critical section에 들어갈 수 있게 설정

 

하지만 Busy waiting(=spin lock)의 문제. 내가 CPU를 잡았는데 상대방이 critical section에 존재한다면, CPU 할당 시간 내내 while문을 체크하겠지만 CPU는 자신에게 있기 때문에 while문에서 빠져나오지 못하고 시간이 끝나면 CPU를 반납함. 비효율적.

 

고급 언어의 프로그램에서는 코드 한 줄 한 줄을 실행하는 도중에 CPU가 다른 프로세스가 넘어갈 수 있기 때문에, 다양한 경우의 수들을 고려해야함

---

하드웨어에서 하나의 instruction을 통해 읽고 쓰는 것이 가능하다면 위에서 발생한 문제들은 해결될 수 있음

Test_and_set: a라는 데이터의 현재값을 1) 읽어낸 다음, 2) 그 값을 1로 바꿔줌

Test_and_set(a)에서 a가 원래 0이었다면 0이 읽히고 a의 값은 1로 바뀜. 반대로 a가 1이었다면 1이 읽힌 다음 다시 한 번 1로 값이 세팅. Test_and_set은 즉 읽어낸 값을 1로 변경해줌.

이게 가능하다면 critical section에 들어가기 전에 lock의 값을 1로 바뀐 다음 구간이 끝나면 다시 0으로 변경

 

만약 Test_and_Set(lock)의 값이 0이었다면, lock이 걸려있지 않다는 건 아무도 critical section에 없다는 의미. while문을 빠져나온 다음 Test_and_Set이 lock의 값을 1로 바꾸고 critical section 사용.

lock이 1이었다면 이미 다른 프로세스가 critical section을 사용하고 있으니 계속 while문에서 대기. 그러다 lock이 0으로 바뀌면 Test_and_Set이 0을 읽어 while문을 빠져나오고 다시 lock의 값은 1로 바뀐 뒤 critical section 진입

하드웨어적으로 1) 값을 읽는 작업과 2) 값을 변경하는 작업이 동시에 이뤄진다면 lock 문제를 해결하는 게 간단해짐

---

Semaphore 자료형은 두 개의 연산을 가짐. 공유자원을 획득하고 반납하는 걸 프로그래머가 용이하게 사용하기 위해

1) P연산: Semaphore값을 갖게 되는 과정

2) V연산: Semaphore값을 반납하게 되는 과정

 

Semaphore 값은 정수 값을 가질 수 있는데, 자원의 개수라고 생각하면 됨. 만약 S가 5라면 자원이 5개 있는 상황. 여기서 P 연산을 진행하면 자원이 1개가 줄어 4개가 됨. 또 다른 프로세스가 사용하면 S가 3개가 됨. 이런 식으로 줄어듦

그리고 V연산을 하게 되면 자원을 다 사용하고 S를 반납하게 되고 S의 값이 1 증가. 

lock을 걸고 푸는 과정은 S 변수값이 1인 상황. 자원의 개수가 1개이니 P 연산을 하면 lock을 걸고, V 연산을 하면 lock을 풀어줌

 

P(S): while문에서 우선 S의 값이 0 이하인지 파악하여 0보다 작다면 S값이 0보다 클 때까지 아무것도 하지 않고(no-op) 대기. 그러다 S값이 양수가 되면, 즉 누군가 자원을 내어놓으면 자원을 얻고 S값을 1 감소.

V(S): P 연산을 통해 자원을 얻은 프로세스가 작업을 마친 뒤 V연산을 통해 자원을 반납하고 S값을 1 증가. 

여기서도 역시 busy-waiting 문제는 발생함. 어떤 프로세스가 CPU 제어권을 얻었는데, 이미 다른 프로세스가 critical section에 있어서 S 값이 0이라면 while문을 빠져나오지 못하고 계속 기다리기만 하다가 timer에 의해 CPU를 빼앗김. 비효율적.

---

Semaphore 변수를 사용하면, critical section에 들어갈 땐 P를, 다 사용하면 V연산을 사용.

프로그래머는 Semaphore 자료형이 지원된다면 P 연산과 V 연산만 사용하면 됨.

 

Block&Wakeup(=sleep lock): CPU를 얻었는데 critical section 이용을 하지 못하면 자원을 낭비하지 않고 sleep 상태

---

semaphore 자료형에서 프로세스들의 주소를 연결해서 가지고 있다가 넘겨줌

P연산 : 자원을 획득하는 과정. P연산을 통해 S의 값을 1 감소. S가 음수라면, 즉 자원이 존재하지 않는다면 해당 프로세스를 L에 추가해서, 즉 연결해서 block 상태가 됨. S가 0이더라도 value를 빼고 시작

 

V연산 : 자원을 다 쓰고 반납하는 과정. 그리고 자원을 기다리는 프로세스가 있다면, 즉 S.value에 1을 더했는데도 s가 0이거나 음수라면 S의 L에 연결된 P연산을 깨워줌. 여기서 S는 정확한 자원의 개수와는 좀 다름

---

보통은 block/wakeup을 사용하는 게 더 효율적. 

하지만 Block/wakeup 역시 프로세스의 상태를 block->wakeup, wakeup->block으로 바꾸는 데 오버헤드가 걸릴 수 밖에 없음. 때문에 critical section의 길이가 짧다면 busy-wait을 해도 대기 시간이 짧기 때문에 큰 문제 없음

하지만 critical section의 길이가 길다면 busy-wait에서 낭비하는 CPU 자원이 많기 때문에 오버헤드를 감수하더라도 Block/wakeup 방식을 사용하는 게 효율적

Binary semaphore: 자원의 개수가 하나. 주로 lock/unlock에 사용

Counting semaphore: 자원의 개수가 여러 개. 여분이 있다면 자원을 가져다 사용할 수 있는 용도.

---

세마포의 주의점: 두 개의 세마포 S와 Q. 둘 모두를 획득해야 조건이 충족. 

P0과 P1이 있는데 P0에서 S만 획득하고 CPU를 P1에게 빼앗겼을 때, 상대방이 가진 세마포를 요구하면서 자신이 가진 세마포는 반납하지 않을 때, 영원히 대기하는 deadlock 상태에 빠짐. 왜냐하면 S를 가진 P0은 Q를 얻어 작업을 한 뒤에 S를 반납하고, P1 역시 S를 얻어 작업을 한 뒤에 Q를 반납하기 때문.

 

세마포를 얻는 순서를 정해놓으면 이러한 문제를 해결할 수 있음. 만약 S를 먼저 얻어야 Q를 얻을 수 있다고 설정하면, P0이 S를 얻은 뒤 CPU를 빼앗겨도 P1이 S를 얻지 않았기 때문에 Q를 얻지 못함. 

 

Starvation: 특정 프로세스가 자원을 얻지 못하고 무한히 대기하는 상황. deadlock도 일종의 starvation. 여기서 말하는 starvation은 특정 프로세스들만 자원을 사용하고 다른 프로세스는 영원히 자원을 얻지 못하는 상황