[OS] Process Synchronization (2) - 프로세스 동기화 (강의 내용)

• 일반적인 프로세스 구조
  • critical section 진입 전 entry section을 통해 3가지 조건 중 상호배제 조건을 갖춤
  • 위 그림 중 위 그림은 상호배제 조건을 만족한 그림으로 count 변수 사용을 상호 배제 상태에서 진행함
  • 하지만 아래 그림은 같은 변수를 같은 동기화 내에서 진행하는 그림으로 표현됨
  • 어느 한 process가 critical section에 진입하게 되면 interrupt system을 disable해버린다. 그렇게 할 경우 다른 process가 같은 critical section에 진입하는 것을 방지할 수 있다.
  • CPU가 한 개일 경우에는 위처럼 해결할 수 있으나 그렇지 않은 경우에는 확장성에 문제가 생겨 그렇게 할 수 없다.

 

 

 

• Busy Waiting을 요구하지 않는 Synchronziation Tool이다.
• wait()과 signal() 방식 두 가지 존재하는데 뒤에서 설명

 

 

• Counting Semaphore : semaphore가 가질 수 있는 값이 제한적이지 않다. 값이 계속 변할 수 있다.
• Binary Semaphore : 가질 수 있는 값이 0 or 1, 구현하기 쉬움 [mutex locks]
• Counting Semaphore는 몇 개의 binary semaphore를 사용하여 구현 가능함
• wait()과 signal() 동작방식

1. process하나가 먼저 작업을 시작하기 위해 진입함 초기 값 1
2. 초기값이 1이므로 첫번째 while문 (S<=0)에 충족하지 않고 건너뜀
3. critical section에 진입하여 작업 시작과 동시에 S--에 의해 S가 0이 됨
4. 다음 process가 작업을 시작하고자 함, 하지만 S는 0이 되었음
5. 따라서 while문에 무한반복으로 작업이 지연됨 (wait)
6. 첫 번째 process가 작업을 마치고 exit하고자 할 때 S++를 하고 나감 (signal)
7. 대기중이던 작업은 S가 1이 되어 while문을 빠져나오고 critical section에 진입함
8. 위 과정들로 Process Synchronization 적용

 

 

• Semaphore 구현을 위해서 같은 semaphore을 대상으로 동시에 두 개의 프로세스가 wait()과 signal()을 동시에 실행시키지 못하도록 하는 것
  • 단일 CPU면 disable interrupt로
  • 다중 CPU먄 SpinLock 사용 : Lock을 흭득하기 위해 process가 spin하고 있다 (= busywaiting)
  • spinlock(=busy waiting)은 short time에 유용, 아닐 때는 context switching이 유용
• Busy waiting은 코드가 짧고 critical section에 진입하는 경우가 별로 없는 경우 유용
• critical section에 오랜 시간 남아있다면 결코 좋은 방법이 아님 그래서 다른 방법 등장 -> no Busy waiting

 

 

 

• 각각의 semaphore가 waiting queue를 가지고 있음
• waiting queue 내부 각각의 entry는 value와 pointer를 가지고 있음
• 두 가지 operation 존재
  • 1) block - Process 중지시킨 후 적절한 waiting queue에 넣기
  • 2) wakeup - waiting queue에서 가져온 후 ready queue로 전환

 

 

 

 

• 위에서 설명한 방법과 비슷
• value 값이 0보다 작으면 block상태로 전환
• value값 --해도 0보다 크거나 같으면 critical section에 진입
• 끝난 후 Signal() method 진행, value값 ++하는데 0보다 작거나 같으면 waiting queue에서 삭제한 후 ready state로 전환

 

 

 

• Deadlock - 두 개 또는 그 이상의 프로세스들이 서로 상대방이 풀어줘야 하는 것을 풀어주지 못해 서로 간 기다리고만 있는 상태
• 상대방이 양보를 하지 않아서 계속 기다리고 있는 상태
• 위 그림으로 예를 들어보자.
• S와 Q는 초기 상태 1로 되어있다.
• P(0)가 먼저 wait상태 진입하게 되면 0이 됨. P(1) 또한 마찬가지로 0이 된다.
• 그럼 위 상태를 지나고 난 후의 wait()은 while문에 걸리게 된다. 
• 위 조건을 해소할 수 있는 건 signal()밖에 없다. 
• 풀어주지 못해서 계속 blocking 되는 상태를 starvation이라 한다.

 

 

 

• 동기화의 전형적인 문제점들
• Bounded-Buffer 문제 이것만 함

 

 

• Bounded-Buffer Problem에는 N개의 버퍼가 있음
• 사용하는 Semaphore는 3가지 종류가 있음
• mutex : 초기값은 1, 상호배제의 용도로 사용
• full : 데이터가 할당되어있는 개수 따라서 초기값 0
• empty : 비어있는 버퍼 공간 따라서 초기값 N

 

 

 

• Flow를 한 번 보면 : Producer Process임

1) Item 생성

2) buffer가 가득 찬 상태인지 확인 : wait(empty)

3) wait(mutex) 과정으로 S-- 연산 수행

4) Critical Section 진입 (공유하고 있는 버퍼 : Producer와 Consumer 공유)

5) Signal(mutex)로 다음 프로세스가 진입할 수 있도록 해줌

6) signal(full)로 차있는 상태의 버퍼가 하나 늘어났음을 표시 

 

 

 

 

• 이건 Consumer 측 상태, Consumer가 최대 관심사가 버퍼가 비어있는지 여부이다. 버퍼가 비어있으면 빼 올 데이터가 존재하지 않기 때문에 
• 따라서 wait(full)을 가장 먼저 수행함

 

 

 

 

• 왼쪽은 producer, 오른쪽은 consumer
• 위 사진으로 보면 알 수 있듯이 관심사가 정반대임. 데이터가 차있는 상태인지 비어있는 상태인지에 대한 관심사가 정반대
• producer가 critical section에 진입하면 signal(mutex)를 수행하여 풀어주기 전까지 consumer는 접근할 수 없음, 반대도 마찬가지

아래 when p.p.p.p then c,c,c,c로 예제를 들었다. p-p-p-p를 진행하면서 empty 공간은 줄어들고 full 공간은 늘어난다. 왼쪽 표모양처럼. 4번째 p를 수행하게 되면 no op로 표시되어있음

 

 

• Multitasking, Multithreading, Multiprocessing 등 지원하기 위해 Lock 매커니즘 제공
• Adaptive mutexes(상황에 맞도록 최적화된 방법) 사용
• Wait & Sleep 기법 사용을 하거나 reader-writers lock을 사용
• adaptive mutex를 사용하기 위해 기다리고 있는 thread들을 순서화하기 위해 turnstiles 사용

 

 

 

• XP의 uniprocessor system (CPU 1개) 환경에서는 interrupt masks를 사용
• CPU가 여러 개인 경우 spinlocks 사용
• mutexes와 semaphores처럼 동작하는 dispatcher object제공
• Dispatcher object는 condition variable(wait & sleep과 유사한 Event를 제공

Condition variable : 조건에 따라 wait 또는 sleep 동작

 

 

 

 

 

• critical sections이 적은 경우 Linux에서는 interrupts를 Disable해버린다.
• 또 Linux에서는
  • semaphores
  • Multiprocessor에서는 sprin locks
  • Single Processor에서는 Kenel preemption(interupptable)과 nonpreemption(Non-interruptable) 제공

 

 

 

 

• Pthreads는 OS와 독립적