프로세스 동기화 (Process Synchronization)

Operating System

 

프로세스 동기화

---

동기화(Synchronization)

• 동기화의 필요성

은행의 1000원의 잔고가 남아있다고 가정하자.

내가 500원을 찾는 순간 동시에 어머니가 500원을 송금해 오셨다면? 우리는 1000원의 잔고를 예상한다.

Process A : incoming
Register1 = Balance
Register1 = Register1 + 500
Balance = Register1

Process B : outgoing
Register2 = Balance
Register2 = Register2 - 500
Balance = Register2

T0: Process A  Register1 = Balance										R1 = 1000
T1: Process A  Register1 = Register1 + 500						R1 = 1500
T2: Process B  Register2 = Balance										R2 = 1000
T3: Process B  Register2 = Register2 - 500						R2 = 500
T4: Process A  Balance = Register1										B = 1500
T5: Process B  Balance = Register2										B = 500

어떠한 데이터에 대해 동시 작업이 일어났을 경우 처리순서에 상관없이 원하는 결과값을 얻기 위해 동기화가 필요하다.

동기화의 목적은 Data Consistency(데이터 일관성)을 보장해주는 것이다.

 

유저 동기화는 critical section

커널 동기화는 mutex / semaphore

 

Critical Section

멀티 프로세스 환경에서 둘 이상의 프로세스가 동시에 접근해서는 안되는 공유 자원의 코드 영역.

임계구역은 시간이 지나면 종료되며, 어떤 프로세스가 임계구역에 접근하기 위해서는 지정된 시간만큼 대기해야 한다.

이때 쓰레드나 프로세스가 배타적인 사용권을 보장받기 위해 세마포어 같은 동기화 메커니즘이 사용된다.

한 프로세스 내의 쓰레드 사이에서만 동기화가 가능. 유저 객체(커널에서 제공하는 객체가 아니다.)

 

임계구역 문제를 해결하기 위한 3가지 조건

1. Mutual Exclusion(상호배제) : 임계구역에는 무조건 하나의 프로세스
2. Progress(진행) : 임계구역이 비었으면 어느 프로세스가 들어갈지 적절히 선택한다
3. Bounded Waiting(한정 대기) : 기아 상태를 방지하기 위해, 한 번 들어갔다 나온 프로세스는 다음에 들어갈때 제한을 준다.

 

동기화 방법

 

상호배제 (MUUual EXclusion)  뮤텍스.

공유데이터가 하나의 프로세스에 의해 독점적으로 사용되는 원칙

entry section
		
		critical section
		
exit section

프로세스는 critical section에 들어가기 전에 entry section 단계에서 출입을 허가받아야한다.

critical section 오직 하나의 프로세스만 존재하도록 한다.

동시프로그래밍 환경(멀티 프로세스 및 멀티 쓰레드 같은)에서 공유 불가능한 자원 처리 (critical section과 구분)

DB의 프로그램에서는 자동적인 부가기능으로 지원되지만, OS의 경우는 사용자의 요구에 따라 지원된다.

장점 혼란이없고 간단하다.

단점 read/write 두 처리 모두 대기한다.

write는 대기하는게 맞지만, read는 데이터를 변화시키지 않으므로 상관없다.

하지만 상호배제는 read도 대기해야한다.

→ 해결법

kernel자체가 하나의 커더란 critical section의 역할을 하는 것.

[Spin lock]

0 : critical section가 비어있다. 사용 가능 .

1 : critical section안에 다른 프로세스가 들어와 있는것.

Spin lock이 1일 경우 다음 수행을 기다리는 프로세스는 lock을 계속 돌게된다.

exit section에 의해 프로세스가 처리되었는지를 인식해 spin lock을 조정한다.

장점 : "조금만 기다리면 바로 쓸 수 있는데 굳치 context switching을 해서 부하를 줄 필요가 있나?"

스핀락을 잘 사용하면 context switching을 줄여 효율을 높일 수 있다.

 

[Sleep lock] — 세마포어

lock이 1일 경우 기다리던 프로세스는 sleep을 하게 되는 것.

critical section내에 프로세스의 작업이 끝나게 되면 sleep중인 프로세스를 깨워 처리하게 된다.

 

—두개의 차이

프로세스가 exit section에 도착했을때.

spin lock은 lock으로 접근해 1로 바꾼다 : waiting process가 항시 대기하며 값이 바뀌기를 기다리고 있으므로 lock만 바꿔주면 된다.

sleep lock은 sleeping process를 깨운다.

 

But, 동시에 2개 이상의 프로세스가 접근하면 상호배제 불가.

A와 B가 동시에 접근해서 lock 이 0인걸 확인했다.

A는 0을 1로 바꿨고, B는 read만 수행하고 context switching이 발생했다.

B는 다음 작업이 수행하게 될때 이미 read 했기때문에, 다시 확인하지 않고(A가 1로 바꿔놨는데 0인줄 알고) 데이터에 접근한다.

해결방법 : read/write를 하나의 명령어로 만들어 놓는다.

 

피터슨의 알고리즘

상호배제를 위한 병렬프로그래밍 알고리즘.

do{
  flag[me] = true; //임계 구역 사용을 원함 
  turn =! me; //me 프로세스의 차례가 아님 
  while(flag[me]&&turn =! me); //me 프로세스가 사용을 원하지만, 턴은 아니면 대기  
  **critical section**
  flag[me]=false; //임계구역 사용이 끝나면 폴스로 바꿔준다. 
  **remainder section**
} while(true);

그러나 프로세스가 많이 몰리면 계속 while문을 대기해야 하는데 이를 busy waiting(바쁜 대기)상태라고 부른다.

 

세마포어(Semaphore)

critical section, mutex는 동기화에 있어서 동시에 하나의 쓰레드만 실행되게 하지만, 세마포어는 지정된 수만큼의 쓰레드가 동시에 실행되도록 동기화하는 것이 가능.

• 임계구역에 들어가기 전 스위치를 사용중으로 놓고 들어간다.

• 이후에 도착하는 프로세스는 앞의 프로세스가 작업을 마칠때까지 기다린다.

• 프로세스가 작업을 마치면 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다.

• 임계구역이 잠겼는지 직접 점검하건, 바쁜 대기를 하거나, 다른 프로세스에 동기화 메시지를 보낼 필요가 없다.

• 세마포어에서 잠금이 해제되기를 기다리는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up신호를 받으면 큐에서 나와 임계구여에 진입.

• 함수 P는 임계구역 들어가기전에 수행 / V는 나올때 수행

• 2개의 공유자원을 가지고 3개의 프로세스가 작업할 때 (Rs=2;)

  1. 프로세스 P1은 RS 값을 1 감소시키고 임계구역에 진입한다.
  2. 프로세스 P2도 RS 값을 1 감소시키고 임계구역에 진입한다.
  3. P3은 RS가 0이므로 대기.
  4. P1이 작업을 마치고 V()를 실행하면 RS값은 1이 되고 wake_up신호가 프로세스 P3에게 전달
  5. P3 임계구역 진입

• 문제점

  세마포어를 잘못 사용하면 임계구역을 보호할 수 없다.

  (1) P() - P() : wake_up신호가 발생하지 않아 무한대기에 빠진다.

  (2) V() - P() : 상호배제가 보장되지 않는 경우

   

MUTEX vs Semaphore

세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없다. 뮤텍스는 상태가 0,1 뿐인 binary 세마포어

세마포어는 소유할 수 없는 반면 뮤텍스는 소유할 수 있고 소유자가 이에 책임을 진다.

뮤텍스는 1개만 동기화가 되지만 세마포어는 하나 이상의 동기화를 할 수 있다.

 

ex ) 변기가 3개가 있는 화장실에서

각각의 변기 앞에 3줄로 줄을 선다 —> 뮤텍스

화장실 문 앞에 한줄로 줄을 선다 —> 세마포어

 

데드락(DeadLock: 교착상태)

프로세스들이 서로 작업을 진행하지 못하고 영원히 대기상태로 빠지는 현상.

프로세스 사이에 할당된 자원의 충돌로 인하여 발생하게 된다.

2개 이상의 프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태.

cf) starvation - OS가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제

교착상태 - 자연적으로 일어나는 문제

 

데드락은 한 시스템 내에서 다음의 네가지 조건이 동시에 성립할 때 발생한다.

아래의 네 가지 조건 중 하나라도 성립하지 않도록 만든다면 교착 상태를 해결할 수 있다.

• 상호배제 (Mutual exclusion)

  한 번에 한 프로세스만 사용 가능

• 점유대기(Hold and wait)

  최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.

• 비선점(No preemption)

  빼앗을 수 없다.

• 순환대기(Circular wait)

  프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다.

 

데드락 처리

1. 예방

   교착상태 발생조건 중 하나를 제거하면서 해결 -> 자원 낭비가 심하다

2. 회피

   은행원 알고리즘

   • 프로세스가 자원을 요구할 때 , 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 사전에 검사하여 교착 상태 회피.
   • 안정상태면 자원 할당, 아니면 다른 프로세스들이 자언을 해지할때까지 대기.

 

식사하는 철학자 문제

철학자가 스테이크를 먹기 위해 양옆의 포크를 동시에 들어야한다.

해결책

• n명이 앉을 수 있는 테이블에서 철학자를 n-1명 앉힌다.
• 한 철학자가 젓가락 두개를 모두 집을 수 있는 상황에서만 젓가락 집도록 허용
• 누군가는 왼쪽 젓가락을 먼저 집지 않고 오른쪽 젓가락을 먼저 집도록 허용

 

 

—> Synchronization을 구현하는 것은 사용자의 필요성에 의해 각자에게 맡겨진 것이다.

어떠한 1명이 실수로 잘못 구현하면 심각한 문제 발생. —> 해결방안 : 모니터

 

모니터

• 시스템 호출과 같은 개념. 인터페이스만 제공한다
• 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.
• 모니터는 요청받은 작업을 모니터 큐에 저장한후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.
• 사용자 입장에서는 복잡한 코드를 실행하지 않아서 좋고, 시스템 입장에서는 임계구역을 보호할 수 있어서 좋다.