Race Condition, Semaphore, Mutex

태그

1 more property

Race Condition

•

race condition이란 두 개 이상의 프로세스가 공통 자원을 병행적으로(concurrently) 읽거나 쓰는 동작을 할 때, 공용 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 같지 않고 달라지는 상황을 말한다. 

•

Race의 뜻 그대로, 간단히 말하면 경쟁하는 상태, 즉 두 개의 스레드가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황을 말한다.

Race Condition이 발생하는 경우

커널 작업을 수행하는 중에 인터럽트 발생

•

문제점 : 커널모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우

•

해결법 : 커널모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.

프로세스가 'System Call'을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환이 발생할 때

•

문제점 : 프로세스1이 커널모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우 ( 프로세스2가 작업에 반영되지 않음 )

•

해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함

멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때

•

문제점 : 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우

•

해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법

임계 구역 (Critical Section)

•

여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분

•

공유 데이터를 여러 프로세스가 동시에 접근할 때 잘못된 결과를 만들 수 있기 때문에, 한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야 한다.

세마포어(Semaphore)

•

공유된 자원의 데이터를 여러 프로세스가 접근하는 것을 막는 방법이다.

•

또한 세마포어는 리소스의 상태를 나타내는 간단한 카운터라고 할 수 있다.

•

하나의 스레드만 들어가게 할 수도 있고 여러 개의 스레드가 들어가게 할 수 있다. 이것이 뮤텍스와의 차이이다.

•

Spin Up 방식과 Block & wakeup 2가지 방식이 존재한다. 하지만 Spin Up 방식은 CPU를 계속 점유하고 있기 때문에 busy-waiting이 발생한다.

세마포어의 P, V 연산 (Block & Wakeup 방식)

P : 임계 구역 들어가기 전에 수행 ( 프로세스 진입 여부를 자원의 개수(S)를 통해 결정)

커널은 wait ( == block )을 호출한 프로세스를 suspend 시키고 이 프로세스의 PCB를 세마포어에 대한 wait queue에 넣는다.

V : 임계 구역에서 나올 때 수행 ( 자원 반납 알림, 대기 중인 프로세스를 깨우는 신호 )

block된 프로세스를 wakeup 시키고 이 프로세스의 PCB를 ready queue로 옮긴다.

procedure P(S)   --> 최초 S값은 1임
    while S=0 do wait  --> S가 0면 1이 될때까지 기다려야 함
    S := S-1   --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함
end P

--- 임계 구역 ---

procedure V(S) --> 현재상태는 S가 0임
    S := S+1   --> S를 1로 원위치시켜 해제하는 과정
end V
C
복사

뮤텍스 (Mutex)

•

상호 배제(Mutual Exclusion)의 약자로 임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술이다.

•

해당 접근을 조율하기 위해 lock과 unlock을 사용한다.

◦

lock : 현재 임계 구역에 들어갈 권한을 얻어옴 ( 만약 다른 프로세스/스레드가 임계 구역 수행 중이면 종료할 때까지 대기 )

◦

unlock : 현재 임계 구역을 모두 사용했음을 알림. ( 대기 중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있음 )

•

뮤텍스는 상태가 1, 0 밖에 없고, 이진 세마포어라고 부르기도 한다.

뮤텍스 알고리즘

데커(Dekker) 알고리즘

flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식

•

flag : 프로세스 중 누가 임계영역에 진입할 것인지 나타내는 변수

•

turn : 누가 임계구역에 들어갈 차례인지 나타내는 변수

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    while(flag[j]) { // 프로세스 j가 현재 임계 구역에 있는지 확인
        if(turn == j) { // j가 임계 구역 사용 중이면
            flag[i] = false; // 프로세스 i 진입 취소
            while(turn == j); // turn이 j에서 변경될 때까지 대기
            flag[i] = true; // j turn이 끝나면 다시 진입 시도
        }
    }
}

// ------- 임계 구역 ---------

turn = j; // 임계 구역 사용 끝나면 turn을 넘김
flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림
C
복사

2. 피터슨 (Peterson) 알고리즘

데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있음

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    turn = j; // 다른 프로세스에게 진입 기회 양보
    while(flag[j] && turn == j) { // 다른 프로세스가 진입 시도하면 대기
    }
}

// ------- 임계 구역 ---------

flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림
C
복사

3. 제과점 (Bakery) 알고리즘

여러 프로세스/스레드에 대한 처리가 가능한 알고리즘. 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입한다.

while(true) {
    
    isReady[i] = true; // 번호표 받을 준비
    number[i] = max(number[0~n-1]) + 1; // 현재 실행 중인 프로세스 중에 가장 큰 번호 배정 
    isReady[i] = false; // 번호표 수령 완료
    
    for(j = 0; j < n; j++) { // 모든 프로세스 번호표 비교
        while(isReady[j]); // 비교 프로세스가 번호표 받을 때까지 대기
        while(number[j] && number[j] < number[i] && j < i);
        
        // 프로세스 j가 번호표 가지고 있어야 함
        // 프로세스 j의 번호표 < 프로세스 i의 번호표
    }
}

// ------- 임계 구역 ---------

number[i] = 0; // 임계 구역 사용 종료
C
복사