•
참고 강의
contents
Inital Attempts to Solve Problem
•
공유 데이터를 접근하는 코드 : Critical Section → 동시 접근으로 문제 발생
◦
Entry Section를 통해서 lock를 걸어서 동시에 들어가는걸 막음
◦
Exit Section를 통해서 unlock를 해서 다른 프로세스가 들어가도록 함
Critical Section문제를 풀기 위해서 만족해야하는 조건
[ 가정 : 모든 프로세스의 수행 속도는 0보다 크다 ]
[ 가정 : 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다 ]
1.
Mutual Exclusion(상호 배제)
프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
2.
Progress(진행)
아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
3.
Bounded Waiting(유한 대기)
프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
→ Starvation이 생기지 않도록
ex. 3개의 프로세스가 critical section에 들어가야할 때, 2개의 프로세스가 계속 번갈아가면서 critical section를 사용하고 나머지 하나가 들어가지 못할 때 Bounded Waiting이 지켜지지 않았다고 볼 수 있다.
상호 배제 실현 조건
고급 언어의 instruction들이 단일 instruction이 아니기에 실행 도중에 CPU를 뺏기기 때문에 문제가 발생하게 된다.
Algorithm 1
turn : 누구의 차례인지 나타내는 변수
Process P0
do {
while(turn != 0)
critical section
turn = 1
remainder section
} while(1)
C
복사
Process P1
do {
while(turn != 1)
critical section
turn = 0
remainder section
} while(1)
C
복사
상대방이 critical section에서 빠져나올 때, 다른 프로세스가 critical section으로 들어갈 수 있게 된다.
•
Mutual Exclusion 만족 → 동시에 들어가는 일이 생기지 않기 때문에
•
Progress 불만족
◦
다른 프로세스가 critical section에 들어갔다가 나와야지만 turn이 바뀌게 된다. 하지만 critical section에 들어가려는 빈도가 균일하지 않다면 계속 들어가고 싶은 프로세스도 turn을 상대방이 바꿔주지 않아서 안으로 들어가지 못하게 된다.
◦
turn 이라는 변수가 있기 때문에 첫 turn이 정해져 있다. 비어있는 Critical Section은 바로 진입 가능하다는 조건을 불만족
◦
누구든 연속해서 두 번 이상 진입이 불가능
◦
실행 속도가 느린 프로세스의 속도에 의존적일 수 밖에 없다는 문제 발생
Critical Section 문제 해결 불가Algorithm 2
flag : critical section에 들어가고 싶은 의중을 표시하는 것, 프로세스 각각 가지게 된다.
•
critical section으로 들어가고 싶은 프로세스는 flag를 true로 만든다.
•
상대방도 critical section에 들어가고 싶다는 표시를 했다면 while에서 기다린다.
•
critical section에서 나올 때는 자신의 flag를 false로 만든다.
Process P0
do {
flag[0] = true
while(flag[1])
critical section
flag[0] = false
remainder section
} while(1)
C
복사
Process P1
do {
flag[1] = true
while(flag[0])
critical section
flag[1] = false
remainder section
} while(1)
C
복사
•
Mutual Exclusion 만족 → 동시에 들어가는 일이 생기지 않기 때문에
•
Progress 불만족
만약, flag[0]이 true가 된 상태에서 CPU를 뺏기면 다른 프로세스에서 critical section에 들어가고 싶어도 프로세스 0이 들어가 있다고 판단을 하여 while에서 기다리게 된다.
→ 프로세스 0이 다시 while문을 실행했을 때, 다른 프로세스도 flag[i]가 0이라서 결국 둘 다 양보하는 상황이 발생한다.(= Livelock)
Algorithm 3(Peterson’s Algorithm)
Dekker의 알고리즘이 있는데 이는 간결하게 만든 것이 Peterson’s Algorithm이다. Dekker 알고리즘의 단점을 해결하였다.
turn과 flag 변수를 모두 사용하는 알고리즘
Process P0
do {
flag[0] = true
turn = 1
while(flag[1] && turn == 1)
critical section
flag[0] = false
remainder section
} while(1)
C
복사
Process P1
do {
flag[1] = true
turn = 0
while(flag[0] && turn == 0)
critical section
flag[1] = false
remainder section
} while(1)
C
복사
•
중간에 CPU를 뺏긴다고 하더라도 문제를 내지 않는다. → 조건을 모두 충족
•
Busy Waiting(== spin lock) 발생
: 계속 CPU와 memory를 쓰면서 wait
→ 계속 쓸데없이 while문을 체크하는데에 CPU를 사용함. 비효율적인 방식.
•
문장 하나하나 실행중에도 CPU를 빼앗길 수 있기 때문에 소프트웨어적으로 복잡한 코드가 되었다.
n 프로세스 간의 상호배제를 위한 소프트웨어 기법들
Synchronization Hardware
이런 문제가 생겼던 이유는 데이터를 읽는것과 쓰는것을 하나의 instruction으로 할 수 없기 때문이다.
•
Test and set(a) : a라는 데이터 값을 읽어내고 a 데이터값을 1로 바꿔주는 instruction를 한 번에(atomic) 처리 → 하드웨어적
이게 지원이 된다면 코드를 복잡하게 짜지 않아도 된다. 간결하게 바뀐다.◦
기계명령어를 활용하면 간단하고, 다중처리 시스템에서도 쉽게 쓸 수 있으며, 한 프로그램 내에서 서로 다른 변수를 사용하여 여러 개의 임계 영역도 지원할 수 있는 장점이 있다.
Synchronization variable:
boolean lock = false;
do {
while(Test_and_Set(lock));
critical seciton
lock = false
remainder section
}
C
복사
인터럽트 금지를 사용한 기법