Race Condition (경쟁 상태)
- 공유하고 있는 Data에 동시에 접근할 경우
- 어떤 순서로 접근하냐에 따라 결과는 달라짐
Race Condition 해결법
- 한번에 하나의 프로세스만 동작하게 하면 된다 (Synchronization: 동기화)
Critical Section Problem (임계 영역)
- n개의 process가 있을 때 자원을 공유하는 코드 영역을 말함
- 하나의 process가 critical section에 접근할때 다른 process의 자원 접근을 막아야 함
Critical Section Problem Solution
- Mutual Exclusion (상호 배제)
- 어떤 process가 실행중일때 다른 processs가 실행되면 안됨- Progress: (avoid deadlock)
- critical section에 실행되고 있는 프로세스가 없다면 다른 프로세스가 접근 가능해야 함
- deadlock: 프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태. 공유 자원을 획득하기 위해 무한정 대기하는 상태- Bounded Waiting: (avoid starvation)
- 동일한 프로세스가 critical section을 독점할 수 없도록 해야 함
- starvation: 특정 프로세스의 우선 순위가 낮아서 원하는 자원을 계속 할당받지 못하는 상태
위 3가지 조건을 다 만족시키기는 어렵다
- simple solution in a single-core environment
- Interrupt 발생을 막음 (Multiprocessor 환경에선 어려움)
- preemptive / non-preemptive kernels (비선점 커널의 경우 거의 안씀)
뮤텍스 알고리즘
Peterson's solution
int turn; // (i or j)
boolean flag[2]; // (i or j)
while (true) {
flag[i] = ture;
turn = j;
while (flag[j] && turn == j) {
// 차례가 올때까지 대기
}
/* critical section */
flag[i] = false;
/* remainder section*/
} Peterson's solution은 no guarantee
하지만
- 알고리즘적으로는 맞는 개념
- 개념적으로 완벽하면서 증명가능함
- 상호배제, 데드락 X, 기아 상태 X 모두 해결한 소프트웨어적 개념
하드웨어적 지원이 없으면 완벽한 구현이 어렵다
다양한 해결 방법
- memory barrier
- hardware instruction: 상호배제 보장
- 인터럽트를 걸 수 없는 operation의 단위로 명령어를 만들어서 사용 - atomic variables
- java의 AtmoicBoolean
- static AtomicBoolean[] flag;
뮤텍스 LOCK (Mutex Locks)
- mutex: mutual exclusion
- critical section을 보호하고 경쟁 상태를 예방함
- critical section에 진입하기 위해선 lock을 얻음 / acquire()
- critical section에서 빠져나오면 lock을 반납 / release()
acquire() {
while (!available)
/* busy wait */
available = false;
}
release() {
available = true;
}- acquire()와 release()도 atomically하게 동작해야 된다.
Busy Waiting 상태가 일어남
- 무한 loop를 이용하여 문제가 됨 (CPU 쓸데없이 소모)
- CPU를 생산적으로 쓸 수 있는 시간을 낭비하게 됨
Spinlock: busy waiting 하면서 기다리는 mutex lock
- CPU 코어가 여러개일 경우 유용하게 사용가능 (context switching 시간을 줄일 수 있음)
세마포어 (Semaphore)
- semaphore: 신호장치, 신호기
- semaphore S는 정수 변수
- atomic하게 동작하는 명령어 wait(), signal() 또는 P(), V()가 있음
wait(S) {
while (S <= 0) {}
// busy wait
S --;
}
signal(S) {
S++;
}열쇠함에 열쇠가 여러개가 있다고 생각하면 된다
- Semaphore를 1로 초기화하면 mutex lock과 동일하게 동작
- Semaphore를 구현하면 mutex lock은 따로 구현하지 않아도 된다.
- semaphore는 사용가능한 자원의 수로 값을 초기화
동기화 문제를 Semaphore로 해결
Process1의 동작 S1과 Process2의 동작 S2
S2는 무조건 S1 이후 실행 되어야 한다면
P1, P2는 Semaphore "synch"를 공유, 0으로 초기화 한다.
S1;
signal(synch);
wait(synch);
S2;synch를 0으로 초기화했기 때문에 S2는 S1의 동작 이후
signal 함수를 통해 synch 값을 증가시켜야 S2가 동작한다
세마포어도 busy waiting 문제가 있음
하지만 세마포어의 무한 루프를 통해 wait() 함수를 구현하여 busy waiting 하는것이 아니라
semaphore가 양수가 아닐때 자신을 suspend시켜 waiting queue에 들어가게 구현하면 됨
다른 process가 signal을 호출하면 waiting queue에 대기중이였던 process를 깨워 ready queue에 넣어주면 됨
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list
sleep();
}
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
/* kernel level implementation */semaphore / mutex 모두 locking 기법 활용
모니터 (Monitor)
- 세마포어가 편리하고 효과적이긴 하지만 timing error가 발생함
ex) mutex를 사용할 때 wait, signal 순서를 지키지 않으면 critical section에 동시에 접근하는 상황이 발생 - 아주 simple한 tools를 쓰자
- monitor: High-level synchronization
모니터는 ADT(추상 데이터 타입), mutex를 제공해주는 데이터 타입, 쉽게 말하면 자바의 클래스
monitor {
function P1() {}
function P2() {}
function P3() {}
initialization_code() {}
}Monitor block 내부의 함수들은 동기화가 되어 있음
- 하나의 struct로 묶어줌
- Monitor 자료구조를 사용하는 쓰레드끼리 entry queue가 존재
Monitor가 제대로 동작하게 하기 위해서는 Condition Variables가 필요
Conditional Variables: 동기화 mechanisms 제공
condition x, y;
x.wait();
x.signal();자바는 Monitor와 같이 동작하는 기능을 제공하는데 이를 monitor-lock 또는 intrinsic-lock이라고 부른다
- synchronized keyword
- wait() / notify() method
synchronized keyword
- 임계영역에 해당하는 코드 블록을 선언할 때 사용하는 자바 키워드
- 임계영역에 진입하기 위해서는 모니터락을 획득해야 함
- 모니터락을 가진 객체 인스턴스를 지정할 수 있음
synchronized (object) { // object의 모니터 lock을 획득한 후 진입 가능 // critical section } or public synchronized void add() { // critical section }
wait() / notify() method
- 쓰레드가 wait() 메소드를 호출하면 해당 객체의 모니터락을 획득하기 위해 대기상태로 진입
- 쓰레드가 notify() 메소드를 호출하면 해당 모니터에 대기중인 쓰레드 하나를 깨움
