[운영체제] 6주차: Process synchronzation

Review

race condition

공유 데이터 access 시 접근 순서에 따라 결과가 달라지는 상태

 

Race condition이 발생한다는 것은 공유 데이터가 있다는 것. 이 부분을 Critical section이라 함

 

여러 프로세스가 동시에 Critical section에 접근해서 data가 깨지기 때문에 발생하는 문제임

-> 한 번에 한 프로세스만 접근할 수 있도록 한다.

 

이 문제를 해결하려면 다음의 세 조건을 충족해야 함

Mutual exclusion

Critical section에 접근하는 프로세스는 한 시점에 한 개뿐이어야 함

 

Progress

Critical section에 진입할 준비가 된 프로세스들만을 대상으로 다음에 접근할 프로세스가 정해짐

 

Bounded waiting

Critical section에 진입할 준비가 됐으면 일정 시간 후에는 반드시 진입해야 함

-> 프로세스들 간의 상대적인 속도를 가정해선 안 된다.

 

Peterson's solution

LOAD와 STORE는 atomic하게 작동한다.

 

 

Semaphore

wait

semaphore 값이 0 이하면 루프를 돈다.

아니면 semaphore 값을 1 줄인다.

 

signal

semaphore 값을 1 늘린다.

 

wait과 signal은 atomic하다.

 

Binary semaphore: Semaphore 값이 0 아님 1 (Mutex lock과 같음)

Counting semaphore:  Semaphore 값이 0..N

 

Critical section 문제와 Process synchronization 문제를 해결할 수 있다.

 

Deadlock: 잘못 사용

Starvation: 잘못 구현

 

 

Semaphore problem

 

Priority inversion

우선순위가 낮은 프로세스가 lock을 가져서(자원을 점유해서) 우선순위가 높은 프로세스가 실행되지 못 하는 문제

우선 순위는 A > B > C다.

① C가 실행되는 중 wait()를 호출 해 sem-A를 획득한다.

② B의 우선순위가 더 높아 C의 자원이 B에 할당된다. C는 block된다.

③ A의 우선순위가 더 높아 B의 자원이 A에 할당된다.

④ A도 critical section에 진입하기 위해 sem-A를 요청한다.

⑤ 그런데 이 sem-A는 현재 C에게 있으므로 A는 wait(sem-A) 호출 후(sem-A 요청 후) block된다.

⑥ 이제 우선순위가 높은 B가 실행된다.

 

따라서 C보다 우선순위가 높은 프로세스가 계속 ready queue에 올려지면 C는 sem-A를 가진 상태로

계속 block되므로 결국 A도 실행이 안 된다.

 

우선순위 계승(Priority inheritance Protocol)

어떤 프로세스가 우선 순위가 높은 프로세스가 요구하는 자원을 가지고 있을 때

그 프로세스의 우선순위를 자원을 요구하는 프로세스의 우선순위로 높이는 방법

 

ⓐ 어떤 프로세스가 자원을 사용 중인데 다른 프로세스가 이 자원을 요청하면 요청한 프로세스는 block된다.

ⓑ 자원이 사용가능하면 프로세스는 자원을 할당받는다.

ⓒ 우선순위 계승이 발생한다.

ⓓ 우선순위를 계승받은 프로세스가 자원을 반환하면 원래 우선순위로 낮아진다.

 

① C가 실행되다가 wait() 호출 -> sem-A 획득

② A가 wait() 호출

③ 현재 sem-A는 C에게 있으므로 C의 우선순위를 A의 우선순위로 높임

④ C 실행 (C의 우선순위는 1)

⑤ C가 완료(signal())되면 C의 우선순위는 다시 5가 됨, 이제 A가 sem-A를 획득해서 실행

 

 

 

 

Monitor

Semaphore로 문제를 해결할 때 문제가 발생하는지 아닌지는 전적으로 프로그래머에게 달려있다.

Ex) wait() 후 signal 해야 되는데 반대로 함, Semaphore의 초기값을 잘못 줌

-> 프로세스 간 실행 순서가 뒤죽박죽 되거나 Critical section 문제가 해결되지 않을 수 있음

 

Monitor는 이런 오류를 근본적으로 줄이는 방법으로, 프로그래밍 언어에서 제공되는 문법이다.

Ex) Java: $synchronized$

Java의 경우 메소드에 $synchronized$ 키워드가 붙으면

여러 thread가 이 메소드를 호출해도 한 번에 한 스레드만 호출할 수 있게 한다.

-> 별도로 wait() 하고 어쩌고 할 필요 없음

 

Monitor의 구현 방법은 여러가지가 있는데, 다음이 한 예시다.

일종의 pseudocode라고 보면 됨

Syntax of a monitor

Monitor는 세 부분으로 구성될 수 있다

ⓐ 함수: 여러 개의 프로세스가 이 함수를 호출해도 한 번에 한 프로세스만 접근함을 보장한다.

ⓑ 공유변수:

ⓒ 공유변수 초기화 부분

 

signal()로 공유변수에 대한 접근을 반환하는 방식으로 프로그램을 작성해야 하는데,

이 부분은 프로그래머에 전적으로 의존한다. 따라서 이 부분을 해결하기 위해 Monitor를 사용하는 것이다.

 

- Critical section problem

여러 개의 프로세스가 동시에 Monitor의 메소드를 호출하면 이 프로세스들은 Queue에 저장된 후

한 프로세스씩 Critical section에 접근하게 된다.

 

 

- Process synchronization

Monitor는 프로세스 간 동기화 문제 (실행 순서 문제)는 해결할 수 없다.

따라서 condition 변수를 추가한다.

 

 

Condition variables

$p.wait()$

$p$는 $p.signal()$이 호출될 때까지 suspend(보류)된다 (Queue에 올려진다).

 

$p.signal()$

$wait()$를 호출한 프로세스 중 하나를 wakeup 시킨다.

이런 프로세스가 없는 경우 아무 동작도 하지 않는다.

 

* 여기서 $wait$과 $signal$은 Semaphore의 그것과 아무 관련이 없다. 그냥 이름만 같은 거임

 

 

 

 

각 condition 변수는 Monitor안에 존재하며 독자적인 queue를 갖는다.

$x.wait()$를 호출하면 $x$의 queue에 추가된다.

 

Constraint

여러 개의 프로세스($P_1,\; P_2$)가 함수 $f_1()$을 동시에 호출했다고 하자.

이 경우 Monitor 특성에 의해 둘 중 하나는 Queue에 올려진다. 여기서는 $P_1$이 올려졌다고 하자.

그러면 $P_2$가 실행 중일 것이다. 여기서 $P_2$가 $x.wait()$를 호출했다고 하자. 이제 $P_2$는 x의 queue에 올려진다.

이 상태에서 어떤 조건에 의해 $P_2$가 queue에서 나오게 되면 $P_1$과 $P_2$가 동시에 $f_1()$에 접근하게 된다.

 

이번에는 $P_2$가 Queue에 올려졌다고 하자. 그러면 $P_1$이 $f_1()$에 접근 중일 것이다.

이 상태에서 $P_1$이 x.wait()을 호출했다고 하자. 이제 $P_1$은 x의 queue에 올려진다. 이제 $P_2$가 queue에서 나와 $f_1()$에 접근 중일 것이다.

이 상태에서 $P_2$가 x.signal()을 호출했다고 하자. 그러면 $P_1$은 전에 실행되던 지점부터 다시 실행되는데, 이 지점이 $f_1()$이다.

따라서 두 프로세스가 동시에 $f_1()$에 접근하게 된다.

 

이 문제를 해결방안은 다음과 같다.

프로세스 P와 Q가 있으며 P는 x.signal()을 호출했고 Q는 x.wait()으로 인해 x의 queue에서 대기 중이라고 하자.

ⓐ Signal and wait: P가 x.signal() 호출 후 x.wait()을 호출해 자기 자신을 queue에 올린다.

ⓑ Signal and continue: P가 x.signal() 호출 후 Q를 condition에서 꺼내서 실행시키는 게 아니라 ready queue에 넣는다.

 

 

ⓐ

mutex

Mutual exclusion 보장을 위한 semaphore

 

next_count

condition의 signal 호출 후 기다리고 있는 프로세스의 수

 

next

관련된 semaphore

 

Monitor 내부에 존재하는 prodedure는 그 자체로 임계 구역이다.

따라서 prodecure에 진입하기 전에 wait(mutex)를 호출해 한 프로세스만 진입할 수 있도록 한다.

prodecure가 끝날 때는 signal을 호출한다.

 

 

 

x_sem

condition  변수 x를 가리키기 위한 변수

 

x_count

x.wait()를 호출한 프로세스의 수 = x의 queue에 있는 프로세스의 수

 

next_count > 0

x.signal 호출 후 기다리는 프로세스가 있음을 의미

 

else

x.wait() 후 프로시저 F에 진입할 프로세스가 없는 경우 반드시 signal(mutex)를 호출해서

다른 프로세스가 F 메소드로 진입할 수 있게 해야 함

 

wait(x_sem)

프로시저 종료 시 무조건 x.wait() 해줘야 함

 

x_count--

wait(x_sem)이 종료되었다는 것은 어떤 프로세스가 x.signal()을 호출했음을 의미함

따라서 x_count 값을 1 줄인다.

 

 

x_count

x의 queue에서 대기 중인 프로세스가 있을 경우

 

next_count++

자기자신은 wait하고 x의 queue에서 하나를 실행시키므로 next_count를 1 늘린다.

 

signal(x_sem)

x의 queue에서 대기 중인 프로세스를 wakeup 시키고

 

wait(next)

나 자신은 next 세마포어를 기다려야 한다.

P, Q가 있을 때 P가 x.wait()을 호출하면 Q를 wakeup시키고 자기 자신은 sleep 상태가 된다.

 

next_count--

위 작업이 다 끝나면 P를 wakeup하기 떄문에 next_count를 1 줄인다.

 

 

 

(나중에 정리할 부분)

 

 

여러 개의 프로세스에서 x.wait()을 호출해서 대기 중일 때 x.signal()은 어느 프로세스를 wake up시킬 것인가?

간단하게는 FCFS

-> 급하게 실행해야 되는 프로세스가 있다면?

=> Conditional wait: wait 할 때 자신의 우선순위까지 queue에 올린다

 

Single resource allocation

Monitor를 이용해 해결할 수 있다.

예를 들어 print 기능을 여러 프로세스가 한 번에 접근해 사용하면 이상한 게 출력될 수 있으므로 한 번에 한 프로세스만 print에 접근해야 한다.

R은 ResourceAllocator의 instance

acquire()

resource에 대한 사용권을 얻는다.

parameter $t$는 현재 resource를 사용중인 프로세스를 계속 기다릴 건지 일정시간만 기다릴 건지를 나타낸다.

 

release()

사용권을 release한다.

 

 

busy

공유 변수

이 변수가 TRUE면 현재 이 자원은 사용 중임을 의미함

최초에는 FALSE

 

① aPrinter.acquire(100) (A)

a가 먼저 printer에 대한 사용권을 얻고

 

② print out something (A)

출력한다

 

③ aPrinter.acquire(200)

A가 출력하는 중에 B가 사용권을 얻으려 한다.

그런데 이 때는 ①에 의해 busy가 TRUE이므로 B는 x.wait()을 호출한다.

 

④ aPrinter.release() (A)

busy를 FALSE로 바꾸고 x.signal()하면 B가 Printer를 사용하게 된다.

 

⑤ print out something (B)

⑥ aPrinter.release() (B)

기다리는 프로세스가 없으므로 그냥 종료

 

 

Summary

Race condition

Critical section

Atomicity: 그 operation 수행 중에는 interrupt가 발생하지 않는다.

 

Semaphore

Integer variables

wait, signal : atomic operation

 

Monitor

Critical section 문제는 해결 가능하나 Process synchronization은 해결 불가

-> Condition 변수: x.wait(), x.signal()