6. Process Synchronization_2

H/W Support for Synchronization

 

• Memory model : 메모리가 실질적으로 어떻게 동작하고 어떤 내용을 보장해주는지 알려준다.

- Strongly ordered : 한 프로세스에서 바꾸면 모든 프로세스에 즉시 알린다. => performance가 손해볼 수 있다.

- Weakly ordered : 한 프로세스가 메모리의 내용을 바꿨는데, 즉시 다른 프로세스에 바로 반영이 되지 않는 경우

                               (현대의 운영체제에서 사용한다 -> performance 때문)

 

! 하지만 weakly ordered를 사용하면 synchronization 문제가 발생할 수 있다 => race condition 생길 수 있음!

 

Memory Barriers (memory fences) <- 위의 문제의 해결책

메모리를 바꾼 그 모든 내용이 다른 프로세스에 다 반영되도록 force한다.

Memory barrier 예시

< Memory Barrier 예시

 

이 때까지의 바뀐 내용을 실제 메모리에 반영해서 다른 프로세스들이 볼 수 있게 한다.

 

 

 

 

 

• Hardware Instructions

 lock 변수를 통해 critical section을 보호함으로써 race condition 을 방지할 수 있다.

 

lock은 shared variable로 여러개의 프로세스가 공통적으로 값을 볼 수 있다.

Boolean lock = 0; (초기값)

lock = flase; // 어떤 프로세스도 critical section에 들어갈 수 있다. (지금 critical section이 비어있다.)

lock = true; // 프로세스 i가 지금 critical section에 들어가 있다.

 

Initially, lock = false;

 

=> 제대로 동작하지 않는다 . : mutual exclusion이 보장되지 않기 때문

P0과 P1이 완전히 동시에 돌아가면 P0과 P1이 둘 다 critical section에 들어가는 상황이 발생할 수 있다.

 

-> nocking과 locking이 구분되어 있지 않기 때문에 발생!

 

 

- Interrupt Disable

HW에 의한 mutual exclusion을 보장하는 과거의 방법

과거에는 Single process system을 사용했기 때문에, 단순히 disabling interrupt로 switching을 안해서 race condition이 발생하지 않도록 한다.

 

-> 하지만 이 방법은 multi processor에서는 맞지 않는다. 그리고 non-preemptive kernel에서만 사용가능하다.

 

 

- Atomic instructions (cpu에 따라 제공될 수도 있고, 안 될 수도 있다)

실행 중간의 상태는 존재하지 않고, 실행 전과 실행 후 상태만 존재한다.

function 형태로 나타냈지만 실제로는 machine language이다.

 

 

1. TestAndSet

=> target이 lock을 나타내는 변수이다

기능 :

현재의 Lock 변수 값을 알려주고 동시에 그 변수를 true로 설정한다.

 

Mutual Exclusion using TestAndSet

 

 

 

2. Swap 

두개의 값을 exchange 한다.

파라미터 중에 하나는 lock variable, 하나는 초기값이 true인 local variable.

두 변수의 값을 바꾸면 lock 변수가 true로 된다.

-> TestAndSet과 비슷한 역할

 

Mutual Exclusion using Swap

 

 

 

3. Compare And Swap

*value가 lock 변수, expected 변수는 lock 값과 비교하는 변수, new_value는 초기 값이 true인 lock 변수에 집어넣을 변수.

lock 변수 값을 리턴해주고 expected값과 같으면 lock 변수에 new_value 값을 집어넣어준다.

Mutual Exclusion using CAS

 

 

• Bounded Waiting Mutual Exclusion

critical sections에 들어가고 싶은 프로세스가 여러개 있다고 할 때,

각 프로세스가 bounded waiting을 보장받기 위해서

critical section에 있던 프로세스가 critical section을 나오면서 자신보다 오른 쪽에 있는 프로세스에게 기회를 주는 것이다.

(최악의 경우는 n-1번 기다리는 것이다.)

 

 

 

 

TestAndSet을 이용한 bounded waiting Mutual Exclusion 구현

- mutual exclusion을 위한 boolean lock 변수

- boolean waiting[i] : true라면, Pi가 들어가고 싶어서 기다리는 중이라는 것을 나타냄

 

 

 

 

 

 

<- j=i 이면 waiting 하는 프로세스가 없다는 것을 뜻한다.

 

 

 

 

 

 

Compare And Swap을 이용한 bounded waiting Mutual Exclusion 구현

 

 

 

 

 

 

 

 

 

 

 

 

 

 

• Atomic Variables 

TestAndSet, SWAP, CAS

Mutual exclusion을 쉽게 구현할 수 있게 해준다.

"special data type + operation"으로 제공한다.

 

 

---

 

Mutex and Semaphore

• Mutex Locks

mutual exclusion 구현을 위한 synchronization tool.

Boolean 변수 available; // critical section에 들어가도 되는지 아닌지를 표시한다.

available 변수는 lock 변수의 반대이다. lock변수는 0일때 critical section에 들어갈 수 있지만, available 변수는 1일 때 들어간다.

 

 

-> entry section에서 호출

 

 

 

-> exit section에서 호출

 

=> 둘 다 무조건 atomic이어야 한다.

 

 

 

 

• Semaphores

mutex lock의 일반화된 버전이라고 할 수 있다.

두개의 atomic한 함수로 조작되는 정수 변수로, 멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제한한다.

 

wait()과 signal()이 있다.

여기서 사용되는 변수 S의 초기 값은 1 또는 그 이상이다. => S는 동시에 critical section에 들어가도 되는 프로세스의 갯수이다. 

 

Semaphores가 mutex lock과 다른 점은 두개 이상의 프로세스가 들어갈 수 있다는 것이다.

즉, Semaphores는 mutex lock이 될 수 있지만, mutex lock은 Semaphores가 될 수 없다.

 

Semaphores는 재사용 가능한 티켓과도 같다.

Semaphores의 atomic한 함수들

S의 초기값이 1이면, wait(S)는 mutex lock 함수의 acquires lock이고, signal(S)는 releases lock이다.

 

 

 

mutex lock에서도 마찬가지지만, 위에 처럼 구현 하면 문제가 생긴다.

 

바로 spinlock이라는 문제로, 위의 wait(S)를 통해 프로세스를 붙잡는 역할은 하지만 critical section 전체를 CPU time을 계속 잡고 있는 busy waiting이 되어서 중요한 자원인 CPU time을 낭비하는 문제가 발생한다.

 

이에 대한 해결책은, 다른 방법으로 Semaphores를 구현하는 것이다.

-> Block operation 사용 ( 아예 들어가지 않는 프로세스를 waiting 상태로 만들어버리는 것이다.)

 

block operation을 사용한 semaphore

block();를 통해 ready queue에 들어가지 않도록 해주고, wakeup(P)를 통해 해당 프로세스를 ready queue로 보내준다.

 

 

- Semaphore의 중요한 부분 : atomicity (Sempahore operation에 대한 atomicity)

Atomicity is often enforced by mutual exclusion

  Single processor 환경에서는 disable interrupt를 통해 mutual exclusion을 보장할 수 있다.

  Multi processor 환경에서는 spinlock을 이용한다. ....... 여기서 잠깐,

 

아까 spinlock을 피하기 위해 block operation을 사용한건데, 또 여기서 spinlock을 사용한다?????

-> 아까는 critical section 전체에 spinlock을 사용하기 때문에 많은 CPU time을 잡아먹는다. 하지만 여기서는 wait, signal 부분만 짧게 spinlock으로 기다리기 때문에 짧게 써서 괜찮다.