OS: 프로세스 동기화(Process Synchronization)

용어

원자성(Atomicity) - 어떤 메소드(Method)를 2개 이상의 쓰레드가 동시에 호출하지 못하는 것을 말한다.

동기화 - 스레드 간의 협력을 보장하기 위한 원자(indivisible)작업을 사용하는 것.

Mutual exclusion - 한 번에 하나의 스레드만 Critical Section 사용, 다른 모든 스레드는 해당 활동에서 제외.

Critical Section - 한 번에 하나의 스레드만 실행할 수 있는 코드(예: 공유 데이터를 수정하는 코드)

lock - 다른 스레드가 작업을 수행할 수 없도록 하는 메커니즘:
    critical section에 들어가기 전에 잠금.

    critical section을 떠날 때 잠금 해제
    잠긴 critical section에 들어가려는 스레드는 잠금이 해제될 때까지 대기

---

하나의 타임퀀텀에 10을 더하는 연산이 전부 수행 될 경우, 

먼저 스케줄된 쓰레드가 이김

---

상호배제 enforce:
    User가 - 스레드가 서로 명시적으로 조정
    OS가 – OS가 상호 배제를 지원
    하드웨어가 — 하드웨어는 상호 배제를 위한 아키텍처 지원을 제공

 

Solution:
    Starvation 방지 - 스레드가 Critical section에 액세스를 시도하면 시간이 걸리더라도 무조건 성공하게 함.
    DeadLock 방지 - 여러 스레드가 Critical Section에 들어가려고 할 경우 그 중 하나가 시간이 걸리더라도 무조건 성공하게 함.

 

스레드는 non critical section에서는 멈출 수 있지만 critical section에서는 멈출 수 없다고 가정.

---

알고리즘 2a
비공식 설명:
● 각각의 실에는 그들만의 이글루가 있습니다 (스택 말하는건가?)
스레드는 자체 칠판을 검사/변경
스레드는 다른 스레드의 칠판을 검사 가능, 변경 불가
칠판의 "true" = 스레드가 critical section에 있습니다
critical section을 실행하려는 스레드가 다른 스레드의 이글루로 들어가 칠판을 검사합니다

다른 스레드가 critical section에 없음을 나타내는 "거짓"을 칠판에서 찾습니다
– 그런 일이 발생하면 자신의 이글루로 돌아가 자신의 칠판에 "true"라고 쓴 다음 critical section으로 이동합니다
critical section에서 돌아오면 이글루로 들어가 칠판에 "거짓"이라고 적습니다

 

 

참고 

동기화란?

동기화란 프로세스 또는 스레드들이 수행되는 시점을 조절하여 서로가 알고 있는 정보가 일치하는 것을 의미.

아직까진 순차화밖에 답이 없다.

 

동기화가 필요한 이유:

1. Race Condition

여러 프로세스가 동기화 없이 데이터에 접근하는 상황, 접근 순서에 따라 결과 값이 달라질 수 있음.

 

2. CSP(Critical Section Problem):

1. enter section(entry section):

    각 프로세스가 임계구역(critical section)에 들어가기 위해 진입허가 요청을 하는 코드가 있는 부분
2. critical section:

    프로세스마다 임계구역을 가지고 있음.

    한 프로세스가 자신의 임계구역에서 작업을 수행하는 동안에는 다른 프로세스는 그들의 임계구역에 접근할수 없다
3. exit section:

    임계구역을 빠져나오는 코드가 있는 부분
4. remainder section:

    나머지 구역

 

CSP 문제 해결방안 3가지

mutual exclusion(상호배제):

    프로세스 P_i가 자기의 임계구역에서 실행된다면, 다른 프로세스(P_j)는 그들 자신의 임계구역에서 실행될수 없다.
progress(deadlock 회피, 진행):

    임계구역을 사용하고 있지 않다면 다른 프로세스가 접근할 수 있도록 한다.
    자신의 임계구역에서 실행되는 프로세스가 없고, 그들 자신의 임계구역으로 진입하려고 하는 프로세스들이 있다면,

    remainder section에서 실행 중이지 않은 프로세스들만 그 임계구역으로 진입할 수 있는지를 결정하는데 참여할 수 있으며,

    이 선택은 무기한 연장될수 있다.
bounded waiting(starvation 회피, 한정 대기): 

    프로세스가 자신의 임계구역에 진입 대기 중일 때,

    다른 프로세스들이 그들 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 한다.
    임계구역 진입횟수에 한계를 두어 같은 프로세스가 계속해서 독점해서 사용하지 못하게 한다. (starvation 방지)

[Algorithm 1]

 

현재 Critical Section에 들어갈 프로세스가 어떤 프로세스인지를 한 변수로 나타내어 일치하는 프로세스만 진입하도록 하는 단순한 방식이다. 

 

 

 

이 방식은 Mutual Exclusion은 만족하지만 Progress는 만족하지 못한다.

turn으로 무조건 번갈아가며 ciritcal section에 접근하는 방식! 

Pi의 remainder section 수행 시간이 매우 길어서 여전히 remainder section에서 수행 중이고, Pj가 수행을 한번 마치고 다시 Critical Section으로 진입하려고 한다면 turn == i이기 때문에 진입할 수 없다. 

 

 

[Algorithm 2]

 

다른 방식으로는, critical section의 사용여부를 프로세스마다 flag로 표시, 다른 프로세스의 flag가 true이면 현재 프로세스는 wait.

 

이 방식도 마찬가지로 Mutual Exclusion은 만족하지만 Progress는 만족하지 못한다. 

두 프로세스가 flag = true를 수행하고 나면 두 프로세스 모두 무한히 Critical Section에 진입하지 못하고 기다리는 상황이 발생하게 된다.

 

peterson solution

CSP를 소프트웨어 기반으로 해결. 두 프로세스가 두개의 데이터 항목을 공유하며 해결.

int turn:

    임계구역으로 진입할 프로세스의 순번(turn = i이면 프로세스 Pi가 임계구역에서 실행)
bool flag[2]:

    특정 프로세스가 임계구역으로 들어갈 준비가 되었다는 것을 나타냄

    (flag[i] = true면 프로세스 Pi가 임계구역으로 들어갈 준비가 되었다는 것)

프로세스 i가 critical section으로 들어가는 코드

프로세스 j가 critical영역을 사용중이면 (flag[j] && turn == j) busy waiting.

아니면 i 진입

 

peterson solution은 CSP를 만족하는가?

mutual exculsion:
    while(flag[j] && turn == j)으로 busy waiting, 하나의 프로세스라도 critical section에 있으면 다른 프로세스는 배제.
progress:
    크리티컬 섹션을 이용하는 프로세스가 없는 경우, 어떤 프로세스라도 지체없이 크리티컬 섹션에 접근할 수 있는가?
    각 프로세스의 초기 flag 값은 false, 크리티컬 섹션에서 할 작업이 생기면 피터슨의 솔루션에 접근하여 true로 바뀜.
    flag가 2개인 경우에는 해당 조건을 고려할 필요가 없다. 상호배제에 의해서 이미 동기화 문제가 해결되기 때문
bounded waiting
    하나의 프로세스가 critical section을 빠져나오는 순간 flag는 false로 바뀜. 기아상태는 발생하지 않음.

 

peterson solution의 한계:

참여하는 프로세스가 최대 2개.

3개 이상의 프로세스가 참여하면 별도의 스케줄러가 필수.

busy waiting 방식이기 때문에 cpu자원을 사용.