[OS Chapter 6] Process Synchronization

데이터의 접근과정에서 문제를 먼저 살펴보도록 합니다.

Process Synchronization = 프로세스 동기화 = Concurrency Control = 병행 제어

데이터의 접근

데이터를 가져와 연산하고 연산 후 결과를 데이터에 다시 저장

연산(실행)	데이터 저장
CPU	Memory
컴퓨터 내부	디스크
프로세스	프로세스의 주소공간

Race Condition

출처: Source :  https://securingtomorrow.mcafee.com/technical-how-to/testing-race-conditions-web-applications/

하나의 storage를 여러 실행장치에서 접근함

이래서 동기화(Synchronizaition) 문제가 생김

 

언제 발생하는가?

1. Kenel 수행중 인터럽트가 발생하여 인터럽트 처리루틴이 수행됨

강의

 

• 양쪽 다 커널 코드이므로 kenel address space 공유
• 결과적으로는 interrupt는 반영안되고 count++만 반영
• 기존 커널 코드 작업이 끝날때까지 interrupt를 받아들이지 않는 방식으로 해결

 

2. Process가 systemcall 하여 kernel mode로 수행 중인데 context swtich가 일어나는 경우

강의

• 커널모드에서 수행중일 때는 CPU를 preempt하지 않음
• 커널모드에서 사용자 모드로 돌아갈 때 preempt

3. Multiprocessor에서 shared memory 내의 kernel data

출처: 강의

• 작업주체가 여러개기 때문에 disable하는 것만으로 불가능
• 방법 1 한번에 하나의 CPU 만이 커널에 들어갈 수 있게
• 방법 2 data에 대해서 lock을 걸어야한다. data 처리가 끝나면 unlock

 

Process Synchronization 문제 

• 공유 데이터의 동시접근은 데이터의 불일치 문제
• 일관성 유지를 위해서는 협력 프로세스간의 실행 순서를 정해주는 메커니즘 필요
• Race condition
  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐

=> race condition을 막기 위해서는 concurrent process는 동기화 되어야 한다.

---

Critical Section Problem(임계 구역)

n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

공유데이터를 접근하는 코드가 critical section이다.

 

하나의 프로세스가 ctritical section이 있으면 다른 프로세스는 critical section에 들어갈 수 없다.

 

해결방법

해결방법의 충족 조건

Mutal Exclusion (상호 배제)

- 어떤 프로세스가 critical section에 들어가 있으면 다른 프로세스는 들어가지 못한다.

 

Progress(진행)

- crtical section에 아무것도 들어가지 않았으면 critical section에 들어가게 해주어야 한다.

 

Bounded Waiting(유한 대기)

- critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지

다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다. (starvation 과 비슷)

 

 

소프트웨어적으로 어떻게 락을 걸고 풀수 있느냐?

 

알고리즘 1

출처: 강의

• turn = 0 이나 1이냐는 프로세스 번호
• 본인 입장일 때 while문을 들어가고 끝날때 turn을 상대 차례로 바꿔 준다.
• 문제점
  • progress 조건을 만족하지 못한다.
  • turn을 교대를 해가며 바꾸지만, 만약에 프로세스 자체가 실행이 안되거나 0번 프로세스만 계속 실행되면 조건 만족하지 못한다.

알고리즘 2

출처: 강의

• flag라는 변수를 둔다.
• 상대 flag가 있으면 계속 기다린다. critical section이 끝나면 flag를 false로 한다.
• 문제점
  • progress 문제: 만약에 동시에 flag=true인 상태이면, 무한히 기다리게 된다. 

 

알고리즘 3 = 피터슨 알고리즘

• flag turn 두개 모두 사용
• flag=true하고 상대방 turn으로 체크
• turn을 추가함으로 써 progress의 문제를 해결
• 문제점
  • 위의 3개의 조건을 만족하지만 Busy Waiting(=spin lock)문제가 발생함
  • 계속 CPU와 memory를 쓰면서 wait

 

위의 해결방법들은 소프트웨어적으로 해결하기 위해 코드가 복잡해진 경우이다.

하드웨어적으로 Test&modify를 atomic하게 수행할 수 있도록 지원하는 경우 간단히 해결할 수 있다.

• Test_and_set(a) - 원래값을 읽어내고 1로 세팅하는 작업이다.
• while(Test_and_set(lock)) - lock이 0일때는 읽고 1로 세팅

---

추상 자료형인 Semaphores

추상자료형 = object랑 operation이 있음

예시! 정수라는 자료형에 더하기 뺄셈 곱하기등의 연산이 있음

 

Semaphore S

출처: 강의

• 정수값
• 두가지 연산
  • P(S): 공유데이터를 획득하는 과정
  • V(S): 반납하는 과정
  • 두 연산은 atomic 하다.
• S = 자원의 개수
• P연산은 자원이 있으면 가져가는 것 여기서도 busy-waiting 문제는 생김

출처: 강의

위와 같이 코드가 구현이 됨.

P와 V연산은 돌아간다는 전제하에 코드를 짜면 됨.

---

Block & Wakeup

spin lock대신 Block & Wakeup(= sleep lock)방식으로 구현

출처: 강의

• struct내부에 큐가 있음

출처: 강의

• 여기서 S = 자원의 개수가 아님. 상태적인 의미를 나타낸다
• 음수가 되면 누군가 자원을 기다리고 있다.
• 양수는 자원의 여분이 있다. 
• P연산 - 자원이 없으면 process를 큐에 추가하고 block
• V연산 - 0 이하면 잠들어 있는 프로세스를 깨워줌

보통은 Block & Wakeup를 쓰는것이 더 효율적

하지만, block하고 wakeup하는 오버헤드가 발생

Critical section길이가 매우 짧으면 busy-wait이 더 적절할 수 도 있음.

 

 

세마포어 두 타입

• Counting semaphore
  • 도메인이 정수값일 때 사용
  • 자원의 개수를 세는데 사용
• Binary semaphore
  • mutex
  • 0또는 1값만 가짐
  • mutal exclusion(lock/unlock)에 사용

---

세마포어의 주의점 Deadlock and Starvation

Deadlock: 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상

 

출처: 강의

위의 그림에서

• P0은 P(S) P(Q)가 필요
• P1도 P(S) P(Q)가 필요 P0가 P(S)를 쥐고 있고, P1이 P(Q)를 쥐고 있으면 둘다 무한히 기다림.

이 문제는 자원을 얻는 순서를 동일하게 해면 해결된다.

 

 

Starvation문제

• indefinite blocking
• 특정 프로세스들만 자원을 공유하여 하나의 프로세스는 자원을 할당받지 못하는 상황
• 식사하는 철학자 문제에서 양쪽 사람이 젓가락을 계속 가져가는 경우
• 주의! 데드락은 전부 왼쪽 젓가락을 잡아버리면 5명이 다 못먹는 문제

---

동기화 문제

1. Bounded-Buffer Problem(= Producer와 Consumer 문제)

출처: 강의

• Producer와 Consumer가 있음
  • producer는 데이터를 집어넣는 역할
  • Consumer는 데이터를 끄집어 내는 역할
• 공유 데이터(Shared data)
  
  •  buffer 자체 및 buffer 조작 변수(buffer의 위치)
• 동기화 변수(Synchronization variables)
  • mutual exclusion: shared data의 mutual exclusion을 위해 (binary semaphore)
  • resource count: full/empty buffer의 수 (integer semaphore)

 

꽉 차있는데 producer가 오면, 넣지 못하고 Consumer가 올 때까지 기다린다.

Producer 입장에서는 비어있는 buffer의 개수가 자원의 개수이다.

Consumer도 반대로 생각하면 된다.

(Producer는 empty buffer, Consumer는  full buffer 사용)

 

세마포어 코드로 구현

출처: 강의

• Producer의 P(empty)는 꽉차있으면 consumer가 V(empty)할 때까지 기다린다.
• 중간에 P(mutex) V(mutex)연산은 공유 버퍼에 대한 lock을 걸고 푸는 과정

---

2. Readers-Writers Problem

DB를 공유데이터로 생각

DB에 write중일 때 다른 process가 접근하면 안됨, read는 동시에 해도 됨

 

출처: 강의

• 공유 데이터(Shared data)
  • DB자체
  • readcount
• 동기화 변수(Synchronization variables)
  • mutex 공유변수 readcount를 접근하는 코드(critical section)의 mutual exclusion을 위함
  • db Reader와 writer가 공유 DB자체를 올바르게 접근하게 하는 역할
• 쓸 때는 db에 대한 lock만 걸면 됨
• 읽을 때도 Lock은 걸어야 함. but, 읽을 사람은 여러사람이 가능하므로 readcount 변수로 조절
• readcount가 1이면(처음 들어온 reader면) DB에 lock을 걸고 읽기 시작한다.
• readcount가 0이면(남은 reader가 없으면) DB에 lock을 푼다.
• readcount라는 공유변수에도 lock이 필요하다. 이게 P(mutex) V(mutex)이다.

 

writer가 대기하는 상황에서 reader가 계속 오면 starvation 현상이 생김.

Q. 어떻게 해결하냐?

A.

신호등이 없는 상황에서 차가 끊임없이 오면 교차로에서 지나가지 못한다.

하지만 신호등이 있다면, 차들이 멈추고 그 때 지나갈 수 있다.

이와 비슷하게 starvation을 해결하면 된다.

---

3. Dining-Philosophers Problem(식사하는 철학자 문제)

각 철학자(process)는 eat과 think만 함

 

위의 코드는 데드락의 문제가 있음

• 모든 철학자가 왼쪽젓가락을 먼저 잡으면 오른쪽 젓가락을 못얻으므로 데드락이 걸림
• 다먹어야 젓가락을 내려놓기 때문이다.

해결방안

• 4명의 철학자만이 테이블에 앉도록
• 젓가락 두 개를 모두 집을 수 있을 때에만 젓가락을 집을 수 있게한다.
• 비대칭하게 집도록, 짝수 철학자는 왼쪽 젓가락부터 집도록, 홀수철학자는 오른쪽 젓가락을 집도록

 

2번째 해결방안의 경우만 코드로 구현

 

출처: 강의

• self[5]의 변수가 젓가락 두개를 다 가질수 있는지 없는지의 여부
• state 상태 3가지 (eating, hungry, thinking)
• state라는 공유변수 접근을 막기위한 mutex를 가지고있음

pickup함수

• test단계에서 옆사람 둘이 밥을 먹고 있지 않으면서 배가 고프면 젓가락 잡을수 있는 권한을 얻음
• P(self[i]) 부분에서 인접한 철학자가 V 해줄때까지 기다리게 된다.

putdown

• 철학자의 상태를 생각하는 상태로 바꿈
• 젓가락을 내려놓으면서 인접한 사람에게 test함수를 재호출 한다.

세마포어의 문제점

• 코딩과 디버깅이 힘들다.
• 정확성에 대한 검증이 어렵다.
• V연산 P연산 순서 거꾸로 되면 Mutual exclusion 깨짐
• P연산을 두번 하면 Deadlock 걸림 

---

Monitor

위의 semaphore문제를 해결한 high level synchronization construct

세마포어는 P연산과 V연산으로 관리하지만, 모니터는 공유데이터를 접근하는 문제를 프로그래머가 신경쓰지 않아도 된다.

출처: 강의

• 공유데이터를 내부의 프로시저로만 접근 가능하다.
• 프로시저를 하나씩 실행하기 때문에 lock을 걸 필요가 없다.(세마포어와의 차이점)
• condition variable이 있음 큐에 프로세스를 sleep 시키거나 깨우는 역할만 함
  • 큐에 줄세우고 깨우고하는 역할 wait과 signal

monitor로 bound buffer 문제 해결

출처: 강의

• empty, full이 condition variable
  • wait(sleep)과 signal(wakeup)을 하기 위한 변수
  • signal은 잠들어 있는 것이 있으면 깨우지만 없으면 아무것도 하지 못한다.
• 공유 버퍼에 대한 lock 코드가 없음
• produce는 비어있지 않으면 empty할 때까지 기다리기(=프로세스 재우기)
• empty queue에 추가(= 생산하는 것)
• 마지막에 full 큐에 값이 있으면 full(consumer)을 깨운다.
• consumer는 반대이다.

 

monitor로 식사하는 철학자 해결

출처: 강의

• state가 공유변수
• test는 조건은 똑같으나 self[i].signal() //잠든 프로세스를 깨움
• 만약 test실패해서 eating이 아니면 wait() 잠들게 된다.
• 세마포어와 if(state[i] != eating)문과 lock을 걸고 안걸고의 차이가 느껴진다.