프로세스 동기화 및 상호배제

동기화

공유자원 또는 데이터가 있을 때, 여러개의 프로세스들이 서로 동작을 맞추어 서로의 정보를 공유하는 것이다. 

 

- 동기화 -

1.  동기화에서 사용되는 용어들 

 Shared data (공유된 데이터): 여러 프로세스들이 서로 공유할 수 있는 데이터 

 Critical section (임계영역): 공유데이터를 동시에 접근하는 코드 영역  

 Mutual exclusion (상호배제): 둘 이상의 프로세스가 동시에 공유데이터에 진입하는 것을 막는 것 

 Race condition (경쟁조건): 공유된 자원의 둘 이상의 입력 또는 조작의 순서 등이 결과값에 영향을 줄 수 있는 상태가 되어 자료의 일관성을 침해한다. 

* 다량의 프로세스들은 자원들을 공유하게 되는데, 이들을 접근할 때 나타나는 문제점들을 Race condition(경쟁조건)이라 하고, 이 문제를 해결하기 위한 방법을 Mutual exclusion(상호배제)라 한다. 

---

상호배제

임계영역에 접근한 프로세스가 있다면 다른 프로세스가 들어오지 못하게 막는 것, 즉 동기화를 시키는 것 

 

1. 상호배제 기초요소 

- 상호배제 기초요소 -

 가. Enter cs primitives

  1) 임계영역 진입 전 검사 

  2) 다른 프로세스가 임계영역 안에 있는지 검사 

 

 나. Exit cs primitives 

  1) 임계영역을 벗어날때 후처리 과정 필요 

  2) 임계영역을 벗어남을 시스템에 알림 

 

2. 상호배제 여러가지 방법

 상호배제를 시키는 기본적인 방법은 Lock이다. 특정 프로세스가 공유자원에 접근 중일때는 다른 프로세스가 접근을 하지 못하도록 Lock를 걸어 해결한다. 

 

 가. 소프트웨어를 이용한 해결

  1) Dekker's 알고리즘 : Two process Me를 보장하는 최초의 알고리즘 

  2) Peterson's 알고리즘 : Deker's 알고리즘을 보다 간단하게 구현한 알고리즘

 

   * 단점: 속도가 느리고, 구현이 복잡하며, Busy waiting이 일어날 수 있는 가능성이 높음, 또한 Interrupt로 인해 Premumtiation 될 확률이 높음

 

* Busy wating: 계속적으로 무한 루프를 돌면서 최대한 다른 스레드에게 CPU를 양보하지 않는 것  

 

 나. 하드웨어를 이용한 해결 

  1) TestAndSet(TAS): Test와 Set을 한번에 수행하는 기계어로 실행중에 Interrupt를 받지 않음, 즉 Premumtation 될 확률이 적음

 

  *단점: 3개 이상의 프로세스가 하나의 공유자원을 사용하는 경우, Busy waiting이 일어날 수 있는 가능성이 높음 

 

 다. OS를 이용한 해결 

  1) Spinlock

  2) 세마포어 

 

  * 밑에서 알아보겠습니다. 

---

Spinlock 

하나의 프로세스가 Lock을 소유하고 있다면, 그 Lock이 반환될 때까지 계속 확인하며 기다리는 기법으로 Critical section(임계영역)에 진입이 불가능할때 Context Switching을 하지 않고 잠시 Loop를 돌면서 재시도를 하는 것을 말한다.   

- Spinlock 도식화 -

active = 1 : 임계 영역에서 실행중인 프로세스가 있음

active = 0 : 임계 영역에서 실행중인 프로세스가 없음

 

1. Spinlock의 특징

 - 초기화, p(), v() 연산으로만 접근이 가능하며, OS에서 Support를 해준다. 

 - Lock을 얻을 수 없다면, 계속해서 Lock을 확인하며 얻을 때까지 기다린다. (busy wating)

 - Lock을 얻을 경우 Context switch를 줄여 CPU의 부담을 덜어준다. 하지만 만약 어떤 프로세스가 Lock을 오랫동안 유지한다면 CPU시간을 많이 소모할 가능성이 존재한다. 

 

2. Spinlock의 단점

 싱글 CPU인 경우에는 유용하지 않음 -> 만약 하나의 프로세스가 Lock을 가지고 있고, 그 프로세스가 Lock을 풀어주기 위해서는, 즉 프로세스 교환을 위해서는 싱글 CPU시스템에서는 필연적으로 Context switch가 일어나야 하기 때문이다.  

여전히 busy waiting 문제가 존재함 -> Spinlock은 기본적으로 무한 루프를 돌면서 Lock을 기다리므로 하나의 프로세스가 Lock을 오랫동안 가지고 있다면, 다른 프로세스는 계속 기다려야하는 상황이 발생되기 때문이다. 

---

세마포어 

Spinlock과 목적은 동일하지만 Spinlock이 가지고 있는 단점을 해결한 기법 

- 세마포어 도식화 -

1. 세마포어의 특징

 - 초기화, p(), v() 연산으로만 접근이 가능하며, OS에서 Support를 해준다. 

 - 임의의 S변수 하나에 Ready queue 하나가 할당된다. 즉 대기실이 존재한다.

 - Spinlock과 가장 큰 차이점은 Ready queue가 존재한다는 점이다. Spinlock에서는 loop를 통해 공유자원을 기다렸다면, 세마포어에서는 Ready queue라는 공간(대기실)에서 기다리면서, 공유자원을 할당받는 방식으로 이루어진다.   

 

2. 세마포어의 종류 

 가. 바이너리 세마포어 

  - 임의의 변수 S가 0과 1 두 종류의 값만 갖는 경우 

  - 상호배제, 프로세스 동기화 목적으로 사용

 

 나. 카운팅 세마포어 

  - 임의의 변수 S가 0이상의 정수값을 가질 수 있는 경우 

  - 생산자, 소비자 문제를 해결

 

* 생산자 - 소비자 문제: 생산자가 생산하는 속도와 소비자가 소비하는 속도의 차이가 존재하는데, 일반적으로 생산되는 속도가 소비되는 속도보다 빠른 경우가 많아서 생산된 데이터를 바로 소비하지 못하게 된다. 이런 상황에서 발생되는 문제를 일컫는다.   

 

3 세마포어를 통해 해결한 부분 

 - 프로세스 동기화 

 - 생산자 - 소비자 문제 

 - Reader, Writter 문제

 - Busy waiting 문제 

 

4. 세마포어의 단점 

  - Starvation 문제가 발생 

---

< 참고자료 >

 

https://www.youtube.com/watch?v=EdTtGv9w2sA&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4

[도서] 컴퓨터구조  - 김형근, 손진곤 지음 -

 

<Computer structures> chapter 16, 프로세스 동기화 및 상호배제 end>

 

---