[운영체제] 6. Process Synchronization 프로세스 동기화

프로세스 동기화의 배경 - Background

프로세스 병행 처리에 의해 언제든지 인터럽트(문맥 교환) 발생 가능.

• 병행 프로세스의 공유 변수 갱신 불일치 발생 - 일관성 X
• 공유 변수 동시 접근 시, 변수 갱신 불일치 발생 가능

 

생산자-소비자 문제 (데이터 불일치 발생 사례)

• 생산자는 유한한 길이를 가진 버퍼에 데이터를 생산하여 저장하고, 소비자는 버퍼에 데이터를 소비합니다.
  
  • count : 버퍼에 저장된 데이터의 수
  • buffer : 데이터 저장 배열
• 생산자와 소비자 프로세스가 동시에 비동기적으로 공유 자원(buffer)에 접근할 때 데이터 불일치가 발생

// 생산자
while (true){
    // next_produced 위치에 아이템을 생산합니다.
    
    // 버퍼에 아이템이 가득찼다면 생산자는 대기
    while(count == BUFFER_SIZE)
    	; //아무일 않고 대기 ( busy-wating -> wait() )
    
    buffer[in] = next_produced; //데이터 저장
    in = (in + 1 ) % BUFFER_SIZE;
    count++;
    //notify() 추가 위치
}

// 소비자
while(true){
    // 버퍼에 아이템이 없다면 소비자는 대기합니다.
    while(count == 0)
        ;
     
    next_consumed = buffer[out];   // 아이템을 가져옴
    out = (out + 1) % BUFFER_SIZE; // 다음 소비할 위치를 가리킴
    count--;                       // 아이템의 개수를 감소시킴
    //notify() 추가 위치
}

* wait() : 다른 스레드가 notify()로 깨워줄 때까지 대기 (같은 클래스 안에서만 사용 가능)

 

생산자 소비자간의 통신 (wait-notify 사용)

• busy-waiting 하지 않고, wait을 통해 cpu를 놓음
• notify로 랜덤한 wait대상을 깨우고 wait대상이 없으면 효과 없음
• notifyAll은 wait대상에 모두 알림

Race Condition (경쟁 상태) (용어 영어로 기억)

• 두 개 이상의 병행 프로세스가 공유 변수에 접근 시 적절한 동기화 메커니즘이 없어 비정상적 실행 결과를 보이는 현상.

생산자 또는 소비자가 버퍼와 count 변수에 접근하여 조작하는 과정에서 다른 프로세스(생산자, 소비자)가 현재 실행 중인 프로세스를 선점하고 버퍼 또는 count 변수에 값을 업데이트한다면 데이터 불일치가 발생한다.

 

왜 생산자-소비자 문제에서 count 변수는 데이터 불일치가 발생하는가?

"count++"는 다음과 같이 기계어로 구현

register1 = count
register1 = register1 + 1
count = register1

 

위에서 register1은 한 CPU만 접근할 수 있는 지역 레지스터

"count--"는 다음과 같이 구현

register2 = count
register2 = register2 + 1
count = register2

위 레지스터의 내용은 인터럽트 처리기에 의하여 메모리에 잠시 보관 후 다시 적재된다.

 

T0 : 생산자가 register1 = count를 수행         {register1 = 5}
T1 : 생산자가 register1 = register1 + 1을 수행 {register1 = 6} => 소비자 프로세스로 context switch 발생
T2 : 소비자가 register2 = count를 수행         {register2 = 5}
T3 : 소비자가 register2 = register2 - 1을 수행 {register2 = 4}
T4 : 생산자가 count = register1을 수행         {count = 6}
T5 : 소비자가 count = register2을 수행         {count = 4}

생산자 소비자 모두 load, add, store로 3개 클럭 펄스 필요
갱신된 count 값 반영 전에 다른 스레드가 count값에 접근해 문제 발생

 

위와 같이 count 변수에 register1,2가 저장되기 전에 프로세스의 문맥 교환(Context Switch)이 발생하게 되면 counte 변수는 부정확한 값이 저장됩니다.

 

상호 배제 오류: 공유 변수 count = 5

• 공유 변수를 접근 update 하는 코드를 임계 구역(critical section)이라 하며, 상호 배제(Mutual Exclusion) 필요

임계 구역 상호 배제 X

• 프로세스 0, 1의 임계 구역이 적절한 상호 배제된다면, count=5
• 상호 배제 안된다면 count값은 4,5,6 중에 하나가 된다.

상호배제 구현 코드 추가

상호배제 구현

•  공유 변수가 접근하는 update 영역에 추가한다.
  • enter_mx(), exit_mx()
  • lock(), unlock()

 

임계 구역의 조건

• 상호 배제(Mutual exclusion)
  • 하나의 프로세스가 임계 구역에 들어가 있다면 다른 프로세스는 들어갈 수 없어야 한다.
• 진행(Progress : 교착상태(DeadLock) 회피)
  • 임계 구역에 들어간 프로세스가 없는 상태에서, 들어가려고 하는 프로세스가 여러 개 있다면 어느 것이 들어갈지를 적절히 결정해주어야 한다.
• 한정된 대기(Bounded waiting : 기아(Starvation) 회피)
  • 임계 구역에 대기하는 프로세스의 기아(Starvation)를 방지해야한다. 임계 구역 대기시간에 한계 존재해야 함.

 

 

Synchronization Hardware 사용한 상호 배제

최근 많은 시스템이 임계구역 코드에 대한 HW를 지원한다.

 

하드웨어 설루션

• Either test memory word and set value : TestAndSet() (여기만 배울 예정)
  임계 영역의 상태를 체크함
• Or swap contents of two memory words: Swap()

 

TestAndndSet Instruction (테스트 후 Set (True) 설정)

TestAndSet(&lock) -> lock
무조건 TRUE로 만들고 체크한 상태 반환

 

기존 target 값

• True : 이미 다른 프로세스가 사용 중
• False : 임계 구역 진입 가능 (임계 구역 접근한 프로세스 없음)

 

Mutex Locks (상호 배제 락)

• acquire(): 임계 영역 사용권 획득
• release(): 임계 영역 사용권 반납

 

Semaphore: 상호 배제 동기화 도구

mutex : 0일 때 not available, 1일 때 available, N일 때 N개 프로세스 available
wait(), signal()

Semaphore 기능 - 세마포어 1) 상호 배제 2) 실행 순서 제어

• Semaphore 객체 1로 초기화하면, 원래대로 상호 배제 기능
• 0으로 초기화 시, 실행 순서 제어 용도 기능
  • p1에서 S1 실행하고 나서 signal()하면 p2의 wait() 이후의 S2 실행 가능

 

Deadlock and Starvation

semaphore문제점

교착상태(deadlock)는 wait()의 순서 문제로 발생 가능

한 줄마다 문맥 교환이 일어나면 P0, P1모두 진행이 불가능한 상황

• 상대방이 가진 세마포어를 P0, P1 모두 대기하며 교착상태(Deadlock) 발생
• 기아(Starvation)는 S를 가진 프로세스가 일시 정지되어 다른 프로세스가 장시간 S를 획득하지 못하는 상황

우선순위 역전 (Priority Inversion)

높은 우선순위 프로세스가 요구하는 세마포어를 낮은 우선 순위 프로세스가 소유할 때 발생

 

Classical Problems of Synchronization

Bounded-Buffer solution with semaphore

• 세마포어를 활용한 생산자, 소비자 문제 구현 (버퍼 사이즈 한계)
• count 변수 사용하지 않고, 세마포어 full, empty를 사용하여 생산자 소비자의 동기화 문제를 구현
• full이 0이면 소비자가 동기화 불가, empty가 0이면 생사자가 동기화 불가 
  • N개의 버퍼
  • Semaphore mutex = 1; (상호 배제)
  • Semaphore full = 0; (full: 생산된 데이터 수 - count 역할)
  • Semaphore empty = N; (empty: 버퍼의 빈 공간 수 = BUF_SIZE - count)

 

Dining-Philosophers Problem

공유된 데이터

• Bow of rice (data set)
• Semaphore chopstick [5] = 1; (세마포어 객체 젓가락 5개 사용 가능 초기화)

• 왼쪽 젓가락, 오른쪽 젓가락 모두 1일 때까지 대기한다.
• 젓가락 모두 있을 때 식사 가능. 식사 중에는 세마포어 객체 chopstic 0으로 초기화.
• 식사 후 다시 chopstic 1로 초기화

교착상태(Deadlock) 가능성

모든 철학자 동시에 왼쪽 젓가락 잡는 경우, 모두 오른쪽 젓가락 잡지 못함. 교착상태 발생.

 

교착상태(Deadlock) 처리 방안

• 최대 5명 정원에서 4명만 앉도록 하면 최소 1명은 식사 가능
• 두 젓가락이 사용 가능할 때, 동시에 획득
• 홀수 철학자는 왼쪽 젓가락부터, 짝수 철학자는 오른쪽 젓락부터 잡도록 한다.
  • 첫 번째 젓가락을 잡은 철학자들끼리 두 번째 젓가락을 잡으려 함으로 결국 한 사람은 두 젓가락 잡기 가능

 

Problems with Semaphores (세마포어 문제점)

한 프로세스의 잘못된 semaphore가 다른 프로세스까지 영향을 준다. (주의 깊은 프로그램 작성 필요) -> 모니터 이용

 

Monitors - 객체, 추상 데이터 타입 (ADT)

모니터는 편리하고 효율적인 프로세스 동기화를 제공해주는 추상데이터 타입이다.

• 내부 변수는 내부 함수를 이용해서만 접근 가능하다.
• 오직 하나의 프로세스만 모니터 내에서 액티브하다. (상호 배제)

기존 Semaphore이용 시 acquire(), release() 통해서 상호 배제함 (기존 공유 변수에 프로세스가 직접 접근함.)

Monitor : 외부에서 직접 데이터 접근 불가, 정해진 procedure를 통해 접근 가능 -> 데이터 캡슐화