Synchronize(2)

임계 구역

• 여러 프로세스가 데이터를 공유하며 수행될 때 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분
• 임계구역에서 다른 프로세스가 중간에 끼는 것을 방지해야함

Semaphore

• 공요된 자원의 데이터를 한 번에 하나의 프로세스만 접근하도록 허용
• 멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제어하는 방법

세마포어 연산

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

P : 임계 구역 들어가기 전에 수행
V : 임계 구역에서 나올 때 수행

𝑆1이 완료된 후에만 𝑆2가 실행되어야 한다고 가정, 𝑃1과 𝑃2가 0으로 초기화된 세마포어 동기화를 공유

Mutex

• 임계 구역 가진 스레드들의 실행시간이 겹치지 않고 단독으로 실행하도록 허용
• Lock, Unlock 기법, 이진 세마포어라고도 불림

Busy Waiting

• 해당 프로세스가 권한을 얻을 때까지 대기 (좋지 않은 동기화 방식)
• aquire() 호출에서 계속 루프 반복
• 단일 CPU코어가 여러 프로세스에서 공유되는 실제 다중 프로그래밍 시스템에서 문제 발생
• spinlock 기법 이용하여 해결, 밑의 알고리즘들로 표현하여 해결 가능

데커(Dekker) 알고리즘

• flag(누가 임계구역에 들어갈지)와 turn(차례는 어떻게 되는지) 변수 통해 임계 구역에 들어갈 프로세스 및 스레드 결정

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

피터슨(Peterson) 알고리즘

• 데커와 유사하지만 프로세스 및 스레드에게 먼저 양보한다는 차이점이 있음

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

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

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

제과점(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; // 임계 구역 사용 종료