🌟 본 게시물은 이화여자대학교 반효경 교수님 강의를 참고로 작성한 게시물 입니다. 틀린 내용은 꼬옥 지적 부탁드립니다 ! 🌟
1. 프로세스 동기화 프로그램적 해결법의 충족 조건
프로세스가 임계구역에 동시에 접근하는 것을 방지하고 데이터 일관성을 유지하려면 아래 세가지 조건을 충족해야한다.
✔️ Mutual Exclustion
- 프로세스 Pi가 Critical Section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 Critical Section에 접근하면 안된다.
✔️ Progress
- Critical Section에 접근한 프로세스가 없는 상황에서 Critical Section에 접근하고자 하는 프로세스가 있으면 Critical Section에 접근하게 해야한다.
✔️ Bounded Waiting
- 프로세스가 Critical Section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 Critical Section에 들어가는 횟수에는 한계가 있어야 한다. (기다리는 시간이 유한 해야함)
- 기아현상 방지
‼️ 예제 알고리즘으로 위 세가지 조건에 만족할 수 있는 방법이 무엇인지 알아보자
💡 실습 가정 !
- 모든 프로세스 수행 속도는 0보다 크다
- 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다
- 예제 알고리즘은 두개의 프로세스가 있다고 가정한다 (P1, P2)
- 프로세스들은 수행의 동기화를 위해 몇몇 변수를 공유할 수 있다 (Synchronization variable)
2. Algorithm - 1
[변수 초기화]
✔️ Synchronization variable
- int turn; → 프로세스가 임계구역에 들어갈 수 있는 조건인지 확인하는 변수
- initially turn = 1; → 첫 진입을 P1에게 허용하기 위해 1로 초기화 함
[구현 코드]
✔️ Process P1 구현 코드
1
2
3
4
5
6
do {
while(turn != 1); /* P1가 접근 가능한 상황이 될 때까지 while */
**critical section** /* 임계구역 */
****turn ****= 2; /* 프로세스 P2(이)가 접근할 수 있게 값 변경*/
**remainder section**
} while (1);
✔️ Process P2 구현 코드
1
2
3
4
5
6
do {
while(turn != 2); /* P2가 접근 가능한 상황이 될 때까지 while */
**critical section** /* 임계구역 */
****turn ****= 1; /* 프로세스 P1(이)가 접근할 수 있게 값 변경 */
**remainder section**
} while (1);
💡 Algorithm - 1 은 Mutual Exclustion 을 만족하지만 Progress 조건은 만족하지 못한다. 💡
Algorithm - 1 을 예로 들면 반드시 교대로 임계구역에 들어갈 수 있게 설계되어있기 때문에 P1이 임계구역 접근에 시도를 하지않을 경우 turn의 값은 영원히 바뀌지 않는다. turn이 변경되지 않을 경우 P2이 입계구역에 접근하려고 해도 접근할 수 없게 된다. 또한 임계구역 접근 빈도가 서로 다를 경우에도 문제가 발생할 수 있다.
3. Algorithm - 2
[변수 초기화]
✔️ Synchronization variable
- boolean falg[2];
- initially flag[모두] = false; /* no one is in CS */
- 프로세스가 임계구역에 접근할 준비가 되면 (flag[i] == true)
[구현코드]
✔️ Process P1 구현 코드
1
2
3
4
5
6
7
do {
flag[0] = true /* 임계구역에 들어갈 준비가 되었다 */
while (flag[1]) /* P2가 임계구역에 접근한 상태인지? 접근했다면 P1은 대기 */
**critical section** /* 임계구역 */
flag[0] = false;
**remainder section**
} while(1);
✔️ Process P2 구현 코드
1
2
3
4
5
6
7
do {
flag[1] = true /* 임계구역에 들어갈 준비가 되었다 */
while (flag[0]) /* P1가 임계구역에 접근한 상태인지? 접근했다면 P2은 대기 */
**critical section** /* 임계구역 */
flag[1] = false;
**remainder section**
} while(1);
💡 Algorithm - 2 은 Mutual Exclustion 을 만족하지만 Progress 조건은 만족하지 못한다. 💡
P1과 P2가 둘 다 임계구역에 접근하려고 값을 true로 변경했을 경우 2행까지 수행 후 끊임 없이 양보하는 상황이 발생할 수 있다. 이럴 경우 P1, P2 두 프로세스가 전부 임계구역에 접근하지 못하는 상황이 발생하기 때문에 Progress 조건을 만족하지 못한다.
4. Algorithm - 3 (Peterson’s Algorithm)
[변수 초기화]
- Combined syschronization variables of algorithms 1 and 2
- Peterson’s Algorithm은 Algorithm - 1 , Algorithm - 2 에서 사용했던 모든 변수를 사용한다.
[구현코드]
1
2
3
4
5
6
7
8
do {
flag[0] = true; /* My intention is to enter */
turn = 2; /* Set to his turn */
while(flag[1] && turn == 2) /* wait only if */
**critical section** /* 임계구역 */
flag[0] = false;
**remainder section**
}
💡 Algorithm - 3는 프로세스 동기화의 세가지 요구사항을 모두 만족한다. 💡
피터슨의 알고리즘은 다른 프로세스가 임계구역에 접근한 상황인지와 다른 프로세스의 임계구역 접근 차례를 모두 검사하고 접근을 시도하기 때문에 세가지 요구사항을 모두 만족한다.
‼️ Algorithm - 3 의 문제점 → Busy Waiting(=spin lock)! (계속 CPU와 memory를 쓰면서 wait) ‼️
만약 한 프로세스가 임계구역에 접근한 상황에서 다른 프로세스가 CPU를 할당받을 경우 while 조건에 충족하기 때문에 다른 작업은 수행하지 못하고 CPU를 빼앗길 때까지 while을 반복하게 된다. (의미없이 CPU 수행시간을 낭비하게 됨)
5. Synchronization Hardware
프로세스 동기화 문제는 소프트웨어가 Input과 Output을 하나의 인스트럭션으로 진행할 수 없어서 생긴 문제점이다. 이러한 문제점을 하드웨어적으로 test & modify를 atomic하게 수행할 수 있도록 지원하면 앞의 문제는 간단히 해결된다.
✔️ Counting semaphore (세마포어)
- 도메인이 0 이상인 임의의 정수값
- 자원의 갯수가 여러개인 경우
- 주로 resource counting에 사용
✔️ Binary semaphore (=mutex)
- 0 또는 1 값만 가질 수 있는 세마포어
- 자원의 갯수가 하나인 경우
- 주로 mutual exclusion (lock/unlock)에 사용 (=mutex)
5.1 Mutex
Mutex는 Mutual Exclustion의 약자이고 상호배재 한다는 뜻으로 사용된다. Mutex는 Locking 매커니즘으로 오직 하나의 쓰레드만이 동일한 시점에 뮤텍스를 얻어 임계 영역에 들어올 수 있고 오직 이 쓰레드만이 임계 영역에서 나갈 때 뮤텍스를 해제할 수 있다.
5.2 Mutual Exclustion with Test & Set
[변수 초기화]
✔️ Synchronization variable
- boolean lock = false;
[구현코드]
1
2
3
4
5
6
do {
while (Test_and_Set(lock));
**critical section**
lock = false;
**remainder section**
}
💡 Test_and_set()
파라미터 변수의 값을 읽고, TRUE로 변경작업을 수행한다. 이전 알고리즘 1,2,3은 값을 읽고 변경하는 작업을 따로따로 진행했다면, Test_and_set()은 값을 읽고 변경하는 작업을 하나의 인터럭션으로 수행하므로 조금 더 간결하게 해결할 수 있도록 도와준다.
6. Semaphores
세마포어란 임계구역에 진입하기 어려울 때 프로세스가 자발적으로 대기 상태로 들어가는 방식이다. 세마포어는 앞의 방식들을 추상화 시킨 방식이다.
❓ 세마포어
- block/wakeup 알고리즘
- 진입 불가능 시에는 대기상태로 전환
- 임계구역을 떠나는 프로세스가 대기 프로세스를 준비 상태로 깨워줌
❓ 세마포어 구성
- 하나의 정수값 (정수변수 value)
- 프로세스 대기 큐
- 정수에 대한 3가지 연산 : init, wait, signal
- wait 은 P 연산이라고도 불린다.
- signal 은 V 연산이라고도 불린다.
✔️ Semaphore 객체를 S 라 할 때
- S.value: 자원 활용 현황
- 양수: 남아있는 자원의 수
- 음수: 부족하여 대기하고 있는 대기자 수
- S.value의 초기값 n : 자원의 개수
아래의 두 가지 atomic 연산에 의해서만 자원에 접근 가능하다.
1
2
3
4
P(S): while (s<=0) do no-op; /*wait*/
S--;
V(S): S++; /* 자원 반납 */
세마포어의 모든 오퍼레이션은 atomic하게 실행되어야 한다. wait 연산을 하는 동안 signal 연산을 하거나, 또는 그 반대의 경우 모두 발생해서는 안된다. 이를 보장하기 위해 각 연산이 실행되는 동안 인터럽트를 disable 시킴으로써 해결할 수 있다. 만약 다중 CPU 환경이라면 모든 CPU의 인터럽트를 disable 시켜야 한다. 헌데 모든 인터럽트를 디스에이블 할 경우 성능이 저하될 수 있기 때문에 compare_and_swap()을 사용하거나 spinlock 과 같은 busy waiting 기법을 사용하기도 한다.
6.1 Block & Wakeup Inmplementation
✔️ Busy-wait 과 Block/wakeup
busy-wait과 block/wakeup 방식을 비교하자면 block/wakeup 방식을 사용하는 것이 효율적이다. busy-wait 방식은 자기 차례가 아니면 의미없이 CPU 시간을 낭비하는 반면에 block/wakeup 방식은 자기 차례가 아닐 경우 block 상태로 전환하기 때문이다.
그런데 임계구역의 코드가 짧을 경우에는 block/wakeup 방식보다 busy-wait 방식이 더 효율적일 수 있다. ready 상태에서 block 상태로 전환하고 다시 block 상태에서 ready 상태로 전환하는 것에 오버헤드가 따르기 때문이다.
정리하자면 임계구역이 짧을 경우에는 busy-wait 방식이 효율적이고 임계구역 코드가 길 경우에는 block/wakeup 방식이 효율적이다.
7. Deadlock
둘 이상의 프로세스가 서로 원하는 리소스가 상대방에게 할당되어 있을 경우 무한히 대기하는 현상을 말한다. 보통 시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.
Reference
https://mangkyu.tistory.com/104
이화여자대학교 반효경 교수님 운영체제 강의