[OS] 8 - Process Synchronization

1. Background

기계어란? -> 0, 1로 이루어진 언어 (컴퓨터가 해석가능함)

어셈블리어란? -> 기계어를 사람이 읽을 수 있도록 만들어 놓은 언어 (기계어에 1대1 매칭이 가능)

고수준 언어란? -> 문장 한개가 복수 개의 기계어에 매칭 가능 -> 동기화 문제 발생 가능성 대두

 

프로세스는 동시 실행이 가능 -> 언제든 중단 될 수 있으며, 부분적으로만 완료 될 수도 있음

공유 데이터에 대한 동시 액세스는 데이터 부정합성이 발생 될 수 있음

--> 생산자-소비자 문제가 대두됨

Race Condition -> 공유 자원을 동시에 액세스하는 현상 -> 프로세스 실행 순서에 따라 값이 달라지는 현상이 발생함

2. Critical Section

공유 데이터룰 액세스하는 코드

-> Critical Section은 통시에 두 프로세스가 실행 될 수 없어야 한다. -> 임의의 한 순간에 한 프로세스만 들어간다면 동기화 문제는 해결된다.

Critical Section

Critical Section의 요구사항

• Mutual Exclusion
  • 임의의 한 순간에 무조건 한 프로세스만이 Critical Section에 진입한다.
  • 만약, P1이라는 프로세스가 Critical Section에 진입했다면 그 어떠한 프로세스도 Critical Section에 진입하면 안된다.
• Progress
  • Critical Section에 들어갈 준비가 되어있는 프로세스들을 대상으로 다음으로 어떤 것이 들어갈 것인가 결정
• Bounded Waiting
  • 임의의 프로세스가 Critical Section에 들어갈 준비가 되었다면, 일정 시간후에 반드시 Critical Section에 진입해야한다.
  • 프로세스를 무한정 기다릴 수는 없다.

3. Critical Section (Solution)

3.1. Peterson's Solution

코드 기반 솔루션이다.

LOAD, STORE 명령어가 atomic하다고 가정한다. -> 즉, 인터럽트가 발생하지 않는다.

 

두 개의 프로세스에 대해서만 해결 가능하다.

두 개의 프로세스는 두 변수를 공유한다.

1.  int turn
   • 어떤 프로세스가 Critical Section에 들어갈지에 대해 정하는 지시자
2. boolean flag[2]
   •  각 프로세스가 Critical Section에 들어갈 준비가 되면 각 flag를 True로함
   • 준비를 표시하는 지시자

      

      

      

    
    

      <cpp />
    
// 프로세스 i 과정
do {
    flag[i] = TRUE; // i의 flag를 true로
	turn = j; // 다음 들어올 프로세스를 j로 지정
	while (flag[i] = TRUE && turn == i); // i 실행
    
    // critical section
    
    flag[i] = FALSE; // Critiacl Section 종료 후 i를 false로
    
	// remainder section
} while (TRUE)

// 프로세스 j 과정
do {
    flag[j] = TRUE; // j의 flag를 true로
	turn = i; // 다음 들어올 프로세스를 i로 지정
	while (flag[j] = TRUE && turn == j); // j 실행
    
    // critical section
    
    flag[j] = FALSE; // Critiacl Section 종료 후 j를 false로
    
	// remainder section
} while (TRUE)

3.2. Synchronization HardWare

하드웨어를 통해 도움을 받을 수 있음

 

"UniProcessor"

• 인터럽트를 허용하지 않으며 Context Switching을 일어나지 않게함 (하지만 다른 영역에도 영향을 줄 수 있기에 거의 사용안함)
• 실행 중인 코드는 선점(Preemptive)하지 않게 동작
• 다중 프로세서 시스템에서는 굉장히 비효율적

      

      

      

    
    

      <cpp />
    
do {
	/* Acquire Lock 락을 통해 다른 것을 못들어오게 함*/
	critical section
	/* Release Lock */
	remainder section
} while (TRUE);

4. Mutex Locks

위의 솔루션을 직접 구현하기엔 복잡하고 프로그래머 물리적으로 접근하기는 어렵기 때문에 나온 개념

소프트웨어를 통해 Lock을 구현

acquire() 메소드를 통해 Lock을 얻고 release() 메소드를 통해 Lock을 해제함

각 메소드는 atomic해야함 (단, Mutex solution은 Busy Waiting해야함 추후설명)

      

      

      

    
    

      <cpp />
    
acquire() {
	while(!available) // lock이 획득 되었는지 확인
    	; /* busy wait */ // available이 false이면 될 때까지 계속 루프함 다른 프로세스가 lock을 획득하지 못하게-> busy wait
        
    available = false;
}

release() {
	available = true;
}



// 사용

do {
	// acquire lock
    
    critical section
    // critical section은 짧을수록 좋음
    
    // release lock
    
    remainder section
} while(true);

5. Semaphore

Critical Section 문제 해결을 위한 실제 솔루션

두 가지 atomic한 실행에 따라 액세스할 수 있는 정수형 변수 

뮤텍스 잠금보다 프로세스를 동기화할 수 있는 정교한 방법을 제공하는 동기화 도구이다.

      

      

      

    
    

      <cpp />
    
// S가 semaphore 변수
wait(S) {
	while(S <= 0);
    S--;
}

signal(S) {
	S++;
}

Semaphore에는 두가지 타입이 있음

1. Binary Semaphore (0..1) --> Mutex Lock과 동일
2. Counting Semaphore (0..N) --> N개의 프로세스가 동시에 Critical Section에 들어갈 수 있게 해준다.

사용법

      

      

      

    
    

      <cpp />
    
do {
	wait(mutex) // 반드시 mutex는 아니여도 됨 (정수형 변수)
                // s == 0 이면 자원이 모두 사용 중
    
    // critical section
    
    signal(mutex) // 자원을 해제하면 S++해서 원복
    
    remainder section
} while(true);

 

Semaphore를 통해 프로세스간 실행 순서 제어

P2가 먼저 시작하더라도 wait에 의해서 P1이 끝나고 Sync을 넘겨 주어야만 P2가 실행이 된다.

 

5.1. Semaphore Problems

Semaphore에는 두 가지 알려진 문제가 있다.

1. DeadLock & Starvation
2. Priority Inversion

DeadLock

-> 잘못 사용했을 때 나타나는 현상

-> 여러 개의 Process들이 어떤 이벤트가 일어나기를 무한정 기다리는 현상

 

Semaphore S = 1, Q = 1일 때,

1. P0가 S를 얻음 -> S--에 의해 S = 0

2. 그 다음 P1이 Q를 얻음 -> Q-- 에 의해 Q = 0

3. 그 후, P0가 Q를 얻으려고함 -> Q = 0이기 때문에 Busy Wait (loop)를 하며 P0가 기다림

4. 이때. P1이 S를 얻으려고함 -> S = 0 이기 때문에 Busy Wait (loop)를 하며 P1이 기다림

5. 이렇게 Semaphore를 얻으려다가 모든 프로세스가 서로 무한정 기다리게됨

--> DeadLock 발생

 

Starvation

-> 잘못 구현했을 때 나타나는 현상

-> 프로세스가 일시 중단된 세마포어 큐에서 제거되지 못하는 현상

 

Priority Inversion

-> 우선 순위가 낮은 프로세스가 Lock을 가짐으로 인해 우선순위가 높은 프로세스가 실행되지 못하는 문제

Prioirity Inversion

해결법 - Priority Inheritance Protocol (우선 순위 계승)

->  특정 Process가 우선 순위가 높은 Process에서 요구하는 자원을 가지고 있을 때 Process의 우선 순위를 자원을 요구하는 Process의 우선 순위로 높여주는 기법

 

규칙

‒ 자원이 사용 중이면 Process는 Block됨

‒ 자원이 사용 가능하면 Process는 자원을 소유

‒ 우선 순위가 높은 Process가 같은 자원을 요청하면 기존 Process의 우선 순위 는 자원을 요청한 Process의 우선 순위로 높아짐

‒ Process가 자원을 반환하면 원래의 우선 순위로 돌아옴

Priority Inheritance Protocol