프로세스 동기화(ProcessSynchornization)

Background

• 프로세스들은 동시에(concurrently)실행할(될) 수 있다. - 언제나 방해 받을 수 있다. 부분적으로는 실행을 끝내는 경우도 있다.              
• 공유된 데이터에 동시에 접근하는 것은 데이터 불일치, 모순을 발생 시킬 수 있다. - 데이터를 일관성 있게 유지시키는 것은 프로세스들 간의 순서를 보장하는 메커니즘이다. 

---

Race Condition

• 동시에 여러 개의 프로세스가 동일한 자료에 접근하여 경쟁하는 현상이다.
• 공유된 데이터의 일관성 문제이다. 

 

해결: 동시적인(concurrent) 실행을 만들지 않는다. 

---

Critical Section Problem

• 각각의 프로세스는 Critical Section을 가진다. 
• Critical Section: 한 프로세스가 Critical Section에서 실행하면, 다른 프로세스는 접근할 수 없다. 한번에 한 프로세스만 Critical Section에 있을 수 있다.

Creitical Section

• Entry Section(진입섹션): 대기 함 --OS 허가---> Critical Section -----> Exit Section: 나간다

 

 

 

Critical-Section Problem

1. Mutal Exclusion(상호 배제): Critical Section안에는 하나의 프로세스만 존재! 다른 프로세스들은 Critical Section에서 실행할 수 없다. 

2. Progress: 현재 Critical Section에서 실행중인 프로세스가 없고, 몇몇 프로세스들이 Critical Section에 진입하기를 희망할떄, 그 다음에 Critical Section에 들어갈 프로세스를 무조건 선택해야 한다. --> 무제한 연기 X 

3. Bounded Waiting: 어떤 프로세스가 Critical Section에 진입을 요청하고, 아직 승이되지 않은 상태에서 다를 프로세스들이 Critical Section에 진입하는 횟수에는 제한이 있다. --> 공평한 기회가 주어져야 함. 무제한 대기X

 

Critical-Section Handling in OS

커널이 preemptive하냐 non-preemptive하냐에 따라 2가지 접근 방법이 있음

• Preemptive: 커널 모드로 수행될 때, 프로세스의 선점 허용
• Non-Preemptive: 커널모드에서 수행되는 선점을 허용하지 않음. 프로세스가 빠져 나가거나, 봉쇄되거나, cpu제어를 양보 --> 동기화 문제 발생하지 않는다. 

---

Peterson's Solution

 

SW적인 solution이다. 2개의 프로세스에서의 solution.

 

2 프로세스는 2개의 변수를 공유한다.

int turn : 다음에 Critical Section에 누가 들어갈 것인가! 진입 순번

Boolean flag[2] : 프로세스가 Critical Section에 들어가고 싶은지 의도(False: 들어가기 싫다/ True:들어가고 싶다)

 

1번째 네모: entry section, flag[]가 true이고, turn이 '자기' 이어야지 Critical Section에 진입할 수 있다.

2번째 네모: exit section

 

Mutual exclusion이 보장된다 --> 특정 조건(1번 네모)일떄만 진입 가능

Progress 만족

Bounded waiting이 충족 --> while문이 공회전 시킨다.

 

---

Synchronization Hardware

 

많은 시스템은 Critical Section Code를 실행시키기 위해 하드웨어 지원을 제공

Lock을 이용해 Critical Section을 보호

 

Uniprocessors - 인터럽트를 무력화 할 수 있다. 

현재 실행중인 코드는 선점(preemption)없이 실행

멀티프로세스 시스템에는 비효율적이다.

 

Atomic(non-interruptible) hardware instructions

 

---

Mutex Locks

• Critical Section문제를 해결할 수 있는 가장 간단한 방법
• Critical Section에 들어가기 전에 lock을 받고, 나갈때 lock을 반환 
• acquire() lock --> release() lock 을 통해 critical section보호
• acquire()와 release()를 호출하는 것은 atomic해야 한다. -- 보통 hardware atomic instructions을 통해 실행
• 단점: busy waiting -> spinlock(계속 lock을 얻기 위해 lock이 가용해지기를 기다리면서 프로세스가 계속 회전) 호출->   CPU 사이클 낭비

 

 

• boolean available : lock의 가용 여부를 나타낸다. 만약 이 값이 true이면 acquire()실행, lock사용 불가  
• release() 가 호출되면 available = true가 되면서 lock을 반납함을 알 수 있다.

 

---

Semaphore

 

• mutex lock 보다 더 복잡한 방식의 동기화를 지원한다.
• Semaphore S - integer 변수(만약 Semaphore = 5이라면, Critical Section에 최대 5개의 프로세스가 들어갈 수 있다)
• 2개의 atomic한 실행에 의해서 접근할 수 있다. 

 

• wait() : Semaphore가 0보다 클 떄, 하나씩 감소
• signal() : Semaphore 하나씩 증가

wait()과 signal()의 정의

• 동시에 같은 Semaphore에서 wait()랑 signal() 동시에 실행 불가. atomic하게 실행되어야 한다. 

 

• busy waiting 문제 

• 각 semaphore는 관련 waiting queue를 가진다.
• waiting queue에 각 엔트리는 2개의 데이터를 가진다

     - int value;

     - struct process *list : 리스트의 다음의 포인터 

• 2개의 연산

      - block : 호출한 프로세스를 waiting queue에 넣는다. - 프로세스 중지

      - wakeup : waiting queue에 있는 프로세스를 꺼내서 ready queue에 넣는다. - 프로세스 재시작 

 

 

---

Deadlock and Starvation

 

• Deadlock : 2개 이상의 프로세스가 대기중인 프로세스에 의해서만 발생하는 이벤트를 영원히 기다리는 것. 계속 잠들어 있는 상태

조건

 

• 상호 배제(mutual exclusion)

한 번에 한 프로세스만 공유 자원을 사용할 수 있다.

좀 더 정확하게는, 공유 자원에 대한 접근 권한이 제한된다. 자원의 양이 제한되어 있더라도 교착상태는 발생할 수 있다.

 

• 들고 기다리기(hold and wait) = 점유대기

공유 자원에 대한 접근 권한을 갖고 있는 프로세스가, 그 접근 권한을 양보하지 않은 상태에서 다른 자원에 대한 접근 권한을 요구할 수 있다.

 

• 선취(preemption) 불가능 = 비선점

한 프로세스가 다른 프로세스의 자원 접근 권한을 강제로 취소할 수 없다.

 

• 대기 상태의 사이클(circular wait) = 순환대기

두 개 이상의 프로세스가 자원 접근을 기다리는데, 그 관계에 사이클이 존재한다.

 

 

• Starvation : 무한한 blocking. 프로세스가 오랜시간 동안 실행 하지 못함.
• Priority Inversion : 우선순위가 낮은 프로세스가 우선순위가 높은 프로세스가 필요한 lock을 들고 있을 때 발생하는 스케쥴링 문제. --> priority-inheritance protocol로 해결 가능 

---

Classical Problem of Synchronization

 

1. Bounded-Buffer Problem 

공유 리소스를 다루는 buffer

Buffer 접근 부분을 Critical Section으로

Buffer가 가득 차있다면 -> data를 못 넣고 기다린다. 

Buffer가 비어있다면 -> 기다려야 함

 

 

2. Readers-Writers Problem 

데이터 set이 많은 concurrent한 프로세스들 사이에서 공유된다.

Reader : 오직 data set읽기만. update하지 않는다.  

Writer : 읽고, update 가능. 

 

문제1. 여러 readers들이 동시에 read할 수 있고, 오직 한 writer만이 공유 데이터에 접근해야 한다. -어느 reader도 기다려서는 않된다 

문제2. writer가 공유 데이터에 접근을 기다리면, 어떤 reader도 접근할 수 없다 -> writer가 준비되면 가능한 빨리 쓰기 수행 요구 

 

3. Dining-Philosopher Problem 

 

설명: 원형 테이블에 5명의 철학자. 각 사람당 오른쪽, 왼쪽에 젓가락 하나씩. 먹기 위해서는 오른쪽,왼쪽 양쪽 모두 젓가락이 필요. 

공유데이터: 밥(data set), Semaphore 젓가락. 젓가락이 하나의 Semaphore -> wait(): 젓가락을 집는다. signal(): 젓가락을 놓는다. 

 

문제: 동시에 모두가 왼쪽을 집으면, 모두가 오른쪽을 기다리기 때문에 deadlock

 

해결:

• eating을 시도하는 철학자는 동시에 4명
• 젓가락을 모두 잡을 수 있는 상황에만 집는다 ->  Critical Section안에서만 젓가락을 잡아야 한다. 
• 비대칭 해결방법: 홀수 철학자는 왼쪽을 먼저 잡고, 그 다음 오른쪽. 짝수 철학자는 오른쪽을 먼저 잡고, 그 다음 왼쪽

---

출처

https://velog.io/@doyuni/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9COS-6.-Process-Synchronization#petersons-solution

https://gmlwjd9405.github.io/2017/10/01/basic-concepts-of-development-os.html