병행제어
데이터의 접근
Race Condition(경쟁상태)
- 중복 접근이 발생하는 경우 결과 값에 문제가 발생해 원치 않은 결과를 얻게 될 수 있다
OS 에서 Race Condition이 발생하는 경우
- Kernel 수행 중 인터럽트 발생 (interrupt handler vs kernel)
- 중요한 변수값을 kernel이 처리하는 경우 interrupt 처리를 disable 시켜서 kernel이 수행하는 프로세스가 종료된 후 interrupt를 처리하는 방식으로 문제를 주로 해결함.
- Process가 System Call을 발생시켜 Kernel mode로 수행 중인데 문맥교환(Context Switch)이 발생하는 경우
- 해결방안 : 커널 모드에서 수행 중일 때는 CPU를 preempt하지 않음. 커널 모드에서 사용자 모드로 돌아갈 때 preempt
3. Multiprocessor에서 shared memory 내의 kernel data
- 방법 1은 큰 overhead발생으로 비효율적임
- lock을 걸어서 다른 어느 누구도 현재 사용하고 있는 data에 접근하지 못하도록 하는 해결법.
- 프로세스가 끝난 후에는 lock을 해제하여 다른 프로세스도 사용할 수 있도록 처리함.
Process Synchronization Problem
-
shared data(공유 데이터)의 concurrent access(동시 접근)은 데이터의 inconsistency(불일치)를 발생시킬 수 있다.
-
Consistency(일관성) 유지를 위해서는 cooperating procee(협력 프로세스)간의
orderly execution(실행 순서)를 정의해주는 메커니즘이 필요하다. -
Race Condition
- 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
- 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 바뀜
-
race condition을 막기 위해서는 공존하 프로세스(concurrent process)가 동기화(Synchronize)되어야 한다.
The Critical-Section Problem
-
n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
-
각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
-
문제점 : 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 함
Initial Attempts to solve problem
- 두 개의 프로세스가 있다고 가정. P0, P1 : 프로세스들의 일반적인 구조
do {
entry section
critical section
exit section
reminder section
} while(1);- Synchronization variable : 프로세스들은 수행의 동기화(Synchronize)를 위해 몇몇 변수를 공유할 수 있음
프로그램적 해결법의 충족 조건
- Mutual Exclusion (상호 배제)
- 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
- 프로세스는 서로 배타적이어야 한다.
- Progress (진행)
- 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면
critical section에 들어가게 해 주어야 한다. - 만족하지 못하는 경우가 있기 때문에 당연하지만 중요한 충족 조건임.
- Bounded Waiting (유한 대기)
- 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용할 때까지
다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. - starvation(기아 상태)이 발생하지 않는 것을 의미함.
가정
- 모든 프로세스의 수행 속도는 0보다 크다
- 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
Synchronization Algorithm
Method 1
-
Synchronization variable int turn; -> 어떤 프로세스의 차례인지를 나타내는 변수값으로 사용 initially turn = 0;
=> P1 can enter its critical section if(turn == i) -
Process P0
do {
while (turn != 0); # My turn? 0은 자기자신
critical section
turn = 1; # Now it's your turn 1이 다른 프로세스
remainder section
} while(1);- Process P1
do {
while (turn != 1); # My turn?
critical section
turn = 0; # Now it's your turn
remainder section
} while(1);- turn 변수값을 파악 후 while문의 조건이 true면 무한루프를 돌면서 대기. 나머지 프로세스는 critical section에 진입. 나머지 프로세스가 critical section에서 빠져나오면 turn 변수값의 값이 변경되므로 대기하던 프로세스는 while문에서 빠져나와 critical section에 진입 가능하게 됨.
- Satisfies mutual exclusion, but not progress (과잉 양보)
-반드시 한번씩 교대로 들어가야만 함. (swap-turn) turn 값을 내 값으로 바꿔줘야만 내가 critical section에 들어갈 수 있음. - 만약 특정 프로세스가 더 빈번히 critical section에 들어가야 한다면 turn 변수값을 변경하지 않고 계속 critical section을 점유하게 될 수도 있으므로 이 알고리즘은 완벽한 알고리즘은 아님.
Method 2
-
Synchronization variable boolean flag[2]; initially flag[all] = false; => No one is in CS (critical section)
-
Pi ready to enter its critical section if (flag[i] == true)
-
Process Pi
do {
flag[i] = true; # Pretend I am in (프로세스에 들어가고 싶다는 의사 표시)
while (flag[j]); # Is It also in? than wait (프로세스가 이미 점유되고 있는지 확인)
critical section
flag[i] = false; # I'm out now
remainder section
} while(1);- Satisfies mutual exclusion, but not progress requirement.
- 둘 다 2행까지 수행 후 끊임 없이 양보하는 상황 발생 가능
Method 3 (Peterson's Algorithm)
- Combined synchronization variables of algorithms 1 and 2
- Process Pi
do {
flag[i] = true; # My intention is to enter ...
turn = j; # set to its turn
while (flag[j] && turn == j);
critical section
flag[i] = false; # I'm out now
remainder section
} while(1);- Meets all three requirements. solves the critical section problem for two processes.
- Busy waiting (= spin lock, 계속 CPU와 memory를 사용하면서 waiting)
Synchronization Hardware
- 하드웨어적으로 Test & Modify를 동시에 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결됨.
- Mutual Exclusion with Test & set
- Synchronization variable boolean lock = false
do {
while (Test_and_Set(lock));
critical section
lock = false;
remainder section
} while(1);- 하드웨어적으로 읽는 작업과 값을 세팅하는 작업을 동시에 할 수 있다는 가정 하에 만들어진 해결 방법
Semaphonrs (세마포) - 추상 자료형
- lock을 걸고 lock을 푸는 과정을 쉽게 구현
- 자원을 얻고 반납하는 과정을 효율적으로 정의
- Semaphore S
- Integer variable (정수)
- 아래의 두 가지 atomic 연산에 의해서만 접근 가능
p(S): 자원을 획득
while(S <= 0) do no-op; # wait
S--;-
누군가가 자원을 반납하면 S를 1 감소시키고 작업을 실행
-
추상적으로 연산을 구현해놓은 것
-
자원이 있으면 가져가는 것이고 없으면 while문을 돌면서 대기하는 것. (busy-wait은 발생하게 됨.)
-
V(S): 자원을 반납
S++;Critical Section of n Processes
Synchronization variable
semaphore mutex; # 추상 변수처럼 semaphore 정의
Process Pi;
do {
P(mutex);
critical section
V(mutex);
remainder section
} while(1);- busy-wait은 효율적이지 못함. (= spin lock)
- Block & Wake-up 방식의 구현 (= sleep lock)
Block / Wakeup Implementation
- Semaphore를 다음과 같이 정의
typedef struct
{
int value; # Semaphore
struct process *L; # process wait queue
} semaphore;-
block과 wakeup을 다음과 같이 가정
- block : 세마포를 획득할 수 없으면, 커널은 block을 호출한 프로세스를 suspend 시킴. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음.
- wakeup(P) : block된 프로세스 P를 wakeup 시킴. 이 프로세스의 PCB를 ready queue로 옮김.
-
semaphore 연산이 이제 다음과 같이 정의됨.
p(S):
S.value++; # 자원을 다 쓰고 나면 S.value 값 증가시키기 (반납)
if(S.value <= 0) {
remove a process P from S.L; # ready queue에서 삭제
wakeup(P); # 만약 잠들어 있다면, 프로세스 깨우기
} V(S):
S.value--; # Prepare to enter
if(S.value < 0) { # 자원 여분 X. Semaphore 획득 실패 (대기 상태)
add this process to S.L; # ready queue에 추가
block(); # block 상태
} Busy-Wait vs Block & Wakeup
- Critical Section의 경쟁이 치열한 경우(길이가 긴 경우) Block & wakeup이 적당.
- Critical Section의 경쟁이 치열하지 않은 경우(길이가 매우 짧은 경우) Block & Wakeup 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
- Block & wakeup 방식이 일반적으로 더 효율적임.
Types of Semaphores
- Counting Semaphore
- 도메인이 0 이상인 임의의 정수값
- 주로 resource counting 에 사용
-Binary Semaphore (= mutex) - 0 또는 1 값만 가질 수 있는 semaphore
- 주로 mutual exclusion (lock/unlock)에 사용
Studying Everyday