동시 접근의 문제
- 멀티 프로세서 환경에서는 CPU가 동시에 접근 하는 문제가 생김
- 일반적인 CPU가 하나인 환경에서는 동시에 접근할 다른 CPU가 없는데 문제가 생기나?
- 데이터를 처리함에 있어 읽기, 연산, 저장 단계에서 Atomic하게 처리할 수 없음. 이때 CPU의 제어권이 넘어가는 Context Switch로 인해 문제가 발생.
Race Condition(경쟁 상태)
✨ Race Condition(경쟁 상태)은 여러 프로세스들이 동시에 데이터에 접근하는 상황에서, 어떤 순서로 데이터에 접근하느냐에 따라 결과 값이 달라질 수 있는 상황을 말한다.
✨ 공유 데이터의 동시 접근(Concurrent access)은 데이터의 불일치 문제를 발생시킬 수 있다. 따라서, Race condition을 막고 일관성을 유지하기 위해서는 협력 프로세스 간의 실행 순서를 정해주는 메커니즘인 동기화(Synchronization)가 필요하다.
Race Condition은 언제 발생하는가?
1. kernel 수행 중 인터럽트 발생 시
📌 interrupt handler vs kernel
💡 커널모드 running 중 interrupt가 발생하여 인터럽트 처리루틴이 수행
-> 양쪽 다 커널 코드이므로 kernel address space 공유
2. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
- 두 프로세스의 address space 간에는 data sharing이 없음
- 그러나 system call을 하는 동안에는 kernel address space의 data를 access하게 됨(share)
- 이 작업 중간에 CPU를 preempt 해가면 race condition 발생
- 해결책 : 커널 모드에서 수행 중일 때는 CPU를 preempt하지 않음. 커널 모드에서 사용자 모드로 돌아갈 때 preempt
3. Multiprocessor에서 shared memory 내의 kernel data
어떤 CPU가 마지막으로 count를 store 했는가? -> race condition
multiprocessor의 경우 interrupt enable/disable로 해결되지 않음
📌(방법 1) 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법 (overhead 문제)
📌(방법 2) 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock/unlock을 하는 방법
Process Synchronization 문제
-
공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다.
-
일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)를 정해주는 메커니즘 필요
-
Race condition
✓ 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
✓ 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐 -
race condition을 막기 위해서는 concurrent process는 동기화(synchronize)되어야 한다
Critical-Section Problem
✨ n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
✨ 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
✨ Problem
- 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.
💡Critical Section(임계 구역)은 코드 상에서 Race condition이 발생할 수 있는 특정 부분을 말한다. 즉, 공유 데이터를 접근하는 코드 부분을 말한다.
Critical-Section 해결방법
프로그램적 해결법의 충족 조건
✨ Mutual Exclusion (상호 배제)
- 프로세스 Pₓ critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.
✨ Progress (진행)
- 아무도 critical section에 있지 않은 상태에서 critical section에
들어가고자 하는 프로세스가 있으면 critical section에 들어가
게 해주어야 한다
✨ Bounded Waiting (유한 대기)
- 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다
🏴 가정
- 모든 프로세스의 수행 속도는 0보다 크다
- 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.
Example Algorithm 1
✨현재 Critical Section에 들어갈 프로세스가 어떤 프로세스인지를 한 변수로 나타내어 일치하는 프로세스만 진입하도록 하는 단순한 방식이다.
✨ Synchronization variable
- int turn;
- initially turn = 0; → Pᵢ can enter its critical section if (turn == i)
✨ Process P₀
do {
while (turn !=i); /* My turn? */
critical section
turn = j; /* Now it's your turn */
remainder section
} while (1);
- Mutual Exclusion은 만족하지만 Progress는 만족하지 못한다.
- 즉, 과잉양보: 반드시 한번씩 교대로 들어가야만 함 (swap-turn). turn 을 내값으로 바꿔줘야만 내가 들어갈 수 있음. A 프로세스가 remainder section에서 오래 있고 B 프로세스가 더 빈번히 crticial section을 들어가야 한다면 B 프로세스는 계속 기다려야되는 문제가 생김.
Example Algorithm 2
✨ 특정 프로세스가 Critical Section에 진입할 준비가 되었다는 것을 나타내는 변수를 두어, 다른 프로세스가 Critical Section에 진입하려고 한다면 현재 프로세스는 기다리는 방법이다
✨ Synchronization variables
- boolean flag[2];
initially flag [모두] = false; / no one is in CS / - "Pᵢ ready to enter its critical section" if (flag [i] == true)
✨ Process Pᵢ
do {
flag[i] = true; /* Pretend I am in */
while (flag[j]); /* Is he also in? then wait "/
critical section
flag [i] = false; /* I am out now */
remainder section
} while (1);- Mutual Exclusion은 만족하지만 Progress는 만족하지 못한다.
- 둘다 flag = true를 수행하고 나면 두 프로세스 모두 Critical Section에 진입하지 못하고 기다리는 상황이 발생하게 된다
Peterson's Algorithm
✨ Peterson's Algorithm은 이전의 알고리즘 1과 2를 합쳐놓은 개념이다. turn 변수와 flag 변수를 동시에 사용한다.
✨ Process Pᵢ
do {
flag [i] = true; /* My intention is to enter .... " */
turn = j; /* Set to his turn */
while (flag [i] && turn == j); /* wait only if ...*/
critical section
flag [i] = false;
remainder section
} while (1);Pᵢ 프로세스에 대해서, Pᵢ는 flag[i] = true로 바꾸면서 Critical Section에 진입하려고 한다. 그리고 turn = j로 바꿔주면서 상대방이 들어가게 한다. 만약 상대방이 들어가고 싶고 (flag[j] == true), 현재 상대방이 Critical Section에 들어가 있으면 (turn == j) 기다린다. 그렇지 않으면 Pi가 들어간다.
그리고나서 Critical Section을 빠져나오면 들어가고 싶지 않다고 flag[i] = false로 바꿔준다.
- 세 가지 요구 사항을 모두 충족하고, 두 프로세스의 critical section을 해결한다.
- 문제점 : Busy Waiting(= Spin lock) (계속 CPU와 memory를 쓰면서 wait)
Synchronization Hardware
✨ 하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결
✨ 현대 기계들은 특별한 atomic hardware instruction을 제공한다. (Test_and_Set 등)
-
lock이 1 =>누가 critical section에 들어가있다.
-
lock이 0 -> critical section에 아무도 없다.
-
하드웨어적인 명령어는 bounded waiting 조건을 만족하지 못하는 단점이 있다. 이 문제를 해결하기 위해서 waiting array라는 배열을 추가로 사용할 수 있는데, 자세한 설명은 생략하겠다.
Semaphores(세마포어)
✨ 앞의 방식들을 추상화시킴. 일종의 추상 자료형
✨ 세마포어(Semaphore)는 Busy Waiting이 필요 없는 동기화 도구이며, 여러 프로세스나 스레드가 Critical Section에 진입할 수 있는 Signaling 메커니즘이다.
✨ 세마포어는 카운터(Counter)를 이용하여 동시에 자원에 접근할 수 있는 프로세스를 제한한다. 주로 S 라는 정수형 변수로 나타내며, 이는 사용 가능한 자원의 개수를 의미한다.
- integer variab
- 세마포어 변수는 두 가지 atomic 연산에 의해서만 접근 가능. 한 프로세스가 세마포어 변수를 수정할 때 다른 프로세스가 동시에 같은 세마포어 변수를 수정할 수 없다.
Busy-wait implemantation
P(S) /*자원을 획득하는 과정, lock을 거는 과정 */
while (S≤0) do no-op;
S --;
V(S) /* 자원을 반납하는 과정, lock을 푸는 과정 */
S++;세마포어가 주어질시 Synchronization, Critical Section 문제를 쉽게 해결 가능
Synchronization variable
semaphore mutex; /* 초기화 1: 1개가 CS에 들어갈 수 있다 */
Process P
do {
P(mutex); /* If positive, dec-&-enter, Otherwise, wait. */
critical section
V(mutex); /* Increment semaphore */
remainder section
} while (1);
-
하지만, 이 방식은 Busy Waiting이 발생하므로 비효율적이다. 따라서 Block & Wakeup 방식을 사용한다.
-
Block & Wakeup 방식은 Critical Section으로의 진입에 실패한 프로세스를 기다리게 하지 않고 Block 시킨 뒤 Critical Section에 자리가 나면 다시 깨워줌으로써 Busy waiting에서의 CPU 낭비 문제를 해결해준다.
-
일반적으로 Busy Waiting이 비효율적이지만, Critical Section이 매우 짧은 경우 Block & Wakeup의 오버헤드가 더 커질 수도 있다.
Block / Wakeup Implementation
Semaphore를 다음과 같이 정의
typedef struct
{
int value; /* semaphore */
struct process *L; /*process wait queue*/
} semaphore;-
value는 세마포어 변수를 의미하고, L은 block 된 프로세스들이 기다리는 Queue다. 따라서 P(S), V(S) 함수도 아래와 같이 구현된다.
✓ block : 커널은 block을 호출한 프로세스를 suspend 시키고 해당 프로세스의 PCB를 wait queue에 넣어준다.
✓ wakeup(P) : block 된 프로세스 P를 깨운 다음, 이 프로세스의 PCB를 ready queue로 이동시킨다.
P(S) : S.value--; /*prepare to enter */ if(S.value < 0) { add this process to S.L; block(); } V(S) : S.value++; if(S.value <=0) { remove a process P from S.L; wakeup(P); }
세마포어의 두가지 타입
-
Counting Semaphore : 도메인이 0 이상인 임의의 정수값. 주로 resource counting에 사용
-
Binary Semaphore(=mutex) : 0 또는 1 값만 가질 수 있는 semaphore. mutual exclusion(lock/unlock)에 사용
결론
- Block/wakeup overhead vs Critical section 길이
- Critical section의 길이가 긴 경우 Block/Wakeup이 적당
- Critical section의 길이가 매우 짧은 경우 Block/Wakeup 오버 헤드가 busy-wait 오버헤드보다 더 커질 수 있음.
- 일반적으로는 Block/wakeup 방식이 더 좋음
Deadlock과 Starvation
✨ Deadlock
둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
나중에 저 자세히 다룸.
✨ S와 Q가 1로 초기화된 semaphore라 하자.
P₁ P₀
P(Q); P(S); 하나씩 차지
P(S); P(Q); 상대방 것을 요구
: :
V(S); V(Q); 여기와야 release 함
V(Q) V(S);✨ Starvation
- indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상
Classical Problems of Synchronization
1. Producer-Consumer Problem (Bounded-Buffer Problem)
In (Producer) Out (Consumer)
1. Empty 버퍼가 있나요? 1. full 버퍼가 있나요?
(없으면 기다림) (없으면 기다림)
2. 공유데이터에 lock을 건다 2. 공유데이터에 lock을 건다
3.Empty buffer에 데이터 3. Full buffer에서 데이터
입력 및 buffer 조작 꺼내고 buffer 조작
4. Lock을 푼다. 4. Lock을 푼다
5. Full buffer 하나 증가 5. empty buffer 하나 증가
- 둘 이상의 생산자가 비어있는 버퍼를 동시에 보고 데이터를 만들어 넣는다면 문제가 발생할 수 있다. 마찬가지로 둘 이상의 소비자가 동시에 동일한 버퍼의 데이터를 사용한다면 문제가 발생할 수 있다. 따라서, 동시에 버퍼에 접근할 수 없도록 락을 걸어줘야 한다.
- 버퍼가 꽉 찬 상태에서 생산자는 반드시 소비자가 버퍼의 데이터를 사용하기를 기다려야 하고, 버퍼가 빈 상태에서 소비자는 생산자가 버퍼를 채우기를 기다려야 한다.
- 그러므로 락을 걸고 푸는 용도, 자원의 개수를 카운팅 하는 용도로 세마포어 변수를 사용한다.
✨ Shared data
- buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)
✨ Synchronization variables
- mutual exclusion → Need binary semaphore (shared data의 mutual exclusion을 위해)
- resource count → Need integer semaphore (남은 fulll/empty buffer의 수 표시)
2. Readers-Writers Problem
✨ 한 process가 DB에 데이터를 write 중일 때 다른 process가 접근하면 안됨
✨ read는 여러 프로세스가 동시에 수행 가능
✨ solution
- Writer가 DB에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 Reader들을 다 DB에 접근하게 해준다.
- Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근이 허용된다.
- 일단 Writer가 DB에 접근 중이면 Reader들은 접근이 금지된다.
- Writer가 DB에서 빠져나가야만 Reader의 접근이 허용된다.
📌Shared data
→ DB 자체
→ readcount; : 현재 DB에 접근 중인 Reader의 수
📌Synchronization variables
→ mutex : 공유 변수 readcount를 접근하는 코드(critical section)의 mutual exclusion 보장을 위해 사용
→ db : Reader와 writer가 공유 DB 자체를 올바르게 접근하게 하는 역할
Writer Reader
P(mutext)
P(db); readcount++;
... if(readcount == 1) P(db); /* block writer */
writing DB is performed V(mutex); /* readers follow */
... ...
V(db); reading DB is performed
...
P(mutext);
readcount--;
if(readcount == 0) V(db); /*enable writer */
V(mutext);-
만약 n개의 reader가 기다리고 있다면, 제일 처음 reader만 db 세마포어에 넣고 나머지 n-1개의 reader는 mutex 세마포어 큐에 넣어둠으로써 효율성을 높여준다.
-
Readers-Writers Problem의 해결책은 Starvation의 가능성이 있다. 계속해서 reader가 들어오거나 writer가 들어오는 경우 한쪽이 계속 수행되지 않을 수 있다.
-
이는 큐에 우선순위를 부여한다거나, 일정 시간이 지나면 자동으로 write or read가 되도록 하여 해결할 수 있다.
3. Dining-Philosophers Problem
5명의 철학자가 원탁에 둘러앉아있고, 젓가락도 5개가 놓여있다
각 철학자는 식사를 하기를 원하고, 철학자가 식사를 하기 위해서는 양쪽 젓가락을 모두 집어야 한다.
Synchronization variables
semaphore chopstick[5];
/* 초기화 된 변수의 값은 모두 1 */Philosopher i
do {
P(chopstick[i]);
P(chopstick[(i+1) % 5]);
...
eat();
...
V(chopstick[i]);
V(chopstick[(i+1) % 5]);
...
think();
...
} while (1);✨ 앞의 solution의 문제점
- Deadlock 가능성이 있다
- 모든 철학자가 동시에 배가 고파져 왼쪽 젓가락을 집어버린 경우
✨ 해결 방안
- 4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다
- 젓가락을 두 개 모두 집을 수 있을 때에만 젓가락을 집을 수 있게 한다
- 비대칭
✓ 짝수/홀수 철학자는 왼쪽/오른쪽 젓가락을 먼저 집도록 하는 방법
ex) 밑의 예제는 각 철학자가 양쪽 젓가락을 다 들 수 있을 때만 들도록 하는 방법의 코드
💡 세마코어 본연의 의미를 담은 코드가 아니라 Monitor 방식에 기반해서 고스란히 세마코어 방식으로 바꿔 놓은 방식.
self[5] = 0 젓가락을 둘다 못잡음. = 1 젓가락 둘다 잡을 수 있음 테스트 전에는 0으로 출발
state[5] 철학자의 상태 체크를 위한 변수
mutex = 1 상태를 나타내는 변수에 락을 걸기 위한 용도로 사용
Monitor
✨ Semaphore의 문제점
- 코딩하기가 힘들고 실수하기 쉬우며, 정확성을 입증하기가 어렵다.
- 자발적 협력(voluntary cooperation)이 필요하다
- V(mutex)와 P(mutex)의 순서에 따라 Deadlock이 생기거나 Mutual Exclusion이 깨질 수 있다.
- 한번의 실수가 모든 시스템에 치명적 영향
✨ Monitor(모니터)는 동시 수행 중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 High-level synchronization construct. 공유 데이터를 접근하기 위해서는 모니터의 내부 Procedure를 통해서만 접근할 수 있도록 한다.
✨ 세마포어와의 가장 큰 차이점은, 모니터는 공유 데이터에 락(Lock)을 걸 필요가 없다. 세마포어는 프로그래머가 직접 P연산과 V연산을 사용하여 Race condition을 해결해야 하지만 모니터는 자체적인 기능으로 해결할 수 있게 된다.
✨ 기본적으로 락을 걸 필요는 없지만 자원이 없어서 잠들어 두게 해야될때는 condition을 두어서 처리한다
✨ 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
✨ 프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요없음
✨ 프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해 condition variable
e.g) condition x, y;
✨ Condition variable은 wait와 signal 연산에 의해서만 접근 가능
📌 x.wait();
- x.wait()을 invoke한 프로세스는 다른 프로세스가
- x.signal()을 invoke하기 전까지 suspend된다.
📌 x.signal();
- x.signal()은 정확하게 하나의 suspend 프로세스 resume한다.
- Suspend된 프로세스가 없으면 아무 일도 일어나지 않는다.
Bounded-Buffer Problem
💡 모니터의 condition variable은 자원의 개수를 세는 역할을 하지 않는다. 자원이 없을때 큐에 줄 세워주는 역할만 한다. 실제 프로그래머 입장에서는 코드가 훨씬 자연스럽게 느껴진다. 세마포어처럼 P연산과 V연산의 추상적인 의미를 알아야지만 코딩을 할 수 있는 것이 아니고 자연스럽게 코딩하면 된다.
밑의 코드를 통해 알 수 있다.
monitor bounded_buffer
{ int buffer[N];
condition full, empty;
/* condition var.은 값을 가지지 않고 자신의 큐에 프로세스를
매달아서 sleep 시키거나 큐에서 프로세스를 깨우는 역할만 함 */
void produce (int x)
{ if there is no empty buffer
empty.wait();
add x to an empty buffer
full.signal();
}
void consume (int *x)
{ if there is no full buffer
full.wait();
remove an item from buffer and store it to *x
empty.signal();
}
}Dining Philosophers Example
Each Philosopher
{
pickup(i);
eat();
putdown(i);
think();
} while(1)🏴 pickup() , putdown() -> Eenter monitor
monitor dining_philosopher
{
eunm {thingking, hungry, eating} state[5];
conditin self[5]
void pickup(int i) {
state[i] = hungry;
test(i);
if(state[i] != eating)
self[i].wait(); /* wait here */
}
void putdown(int i) {
state[i] = thinking; /* test left and right neighbors */
test((i+4) % 5); /* if L is waiting */
test((i+1) % 5);
}
void test (int i) {
if( (state[(i+4) % 5] != eating
&& (state[i] == hungry) && (state[(i+1) % 5] != eating) ) {
state[i] = eating;
self[i].signal(); /* wake up Pi */
}
}
void init() {
for(int i = 0; i<5; i++)
state[i] = thinking;
}
}
