[OS] 동기화(2) - OS Solutions

1. Spinlock

1) Spinlock이란?

- 정수 변수(S)

- 초기화, P(), V() 연산으로만 접근 가능 : 한 번에 수행되는 것이 보장됨

- 원자성

 

2) P(), V() 연산

 

3) Spinlock의 문제점

- 멀티 프로세서(2개 이상의 CPU) 시스템에서만 사용 가능 : P()는 한 번에 수행된다는 보장이 있고 p() 내에는 자원 할당 대기를 위한 무한루프문이 존재한다. 즉 단일 프로세서에서는 모든 프로세스가 일을 못하는 경우가 발생할 수 있다.

- 여전히 Busy waiting 문제가 존재한다.

 

 

2. Semaphore(세마포어)

1) Semaphore란?

- Dijkstra가 제안한 기법

- 음이 아닌 정수 변수(S)

- 초기화, P(), V() 연산으로만 접근 가능

- Busy waiting 문제 해결 : 임의의 S변수 하나에 ready queue ★ 하나가 할당됨, Busy waiting -> block(asleep)

 

2) P(), V() 연산

 

3) Semaphore의 종류

- Binary semaphore : S=0,1

- Counting semaphore : S>=0

 

4) Semaphore로 해결 가능한 동기화 문제들

(1) 상호 배제 문제

 

(2) 프로세스 동기화 문제 : 프로세스들의 실행 순서를 맞출 수 있음

예시

 

(3) Producer-Consumer 문제 : 생산을 해야 소비를 하고, 소비를 해야 생산을 한다는 논리로 접근한 경우

<1> 단일 버퍼

 

<2> 복합 버퍼

 

※ 복합 버퍼 도식화

버퍼 배열 이용

 

(4) Reader-writer 문제

- 데이터를 읽는 Reader과 데이터를 갱신하는 Writer를 이용하는 경우

- 하나의 데이터에 대해 읽기, 갱신 과정이 동시에 이루어질 때 값이 깨질 수 있는 문제

- 하나의 데이터를 여러 Writer가 동시에 갱신할 때 값이 깨질 수 있는 문제

- Reader/Writer에게 우선권을 부여하여 해결

 

예시 - Reader가 우선권을 가지는 경우

(5) Dining philosopher(철학자들의 저녁식사) 문제 : Deadlock(교착 상태)를 설명하기 위한 문제

(6) 기타

 

5) Semaphore의 문제점

Semaphore queue에 대한 wake-up 순서는 비결정적이기 때문에 기아(Starvation)문제 발생 가능성 존재

 

 

3. Eventcount/Sequencer

1) Eventcount/Sequencer이란?

은행에서 번호표 순서로 처리하는 원리를 이용한 기법

 

2) Eventcount

- 정수형 변수이고 0으로 초기화 되어있으며, 특정 사건의 발생 횟수를 기록함

- read(E) 연산 : 현재 Eventcount값 반환

- advance(E) 연산 : 다음 프로세스를 깨움(E=E+1)

- await(E,v) 연산 : v는 도착한 고객의 번호이며, v>E이면 대기할 수 있도록 Queue에 프로세스를 push하거나 CPU scheduler을 호출함

 

3) Sequencer

- 정수형 변수이고 0으로 초기화 되어있으며, 발생 사건들의 순서를 유지해주는 역할을 함

- Sequencer은 ticket() 연산으로만 접근 가능한데, ticket(S)은 현재까지 ticket() 연산이 호출된 횟수를 반환함

- ticket() 연산은 원자성을 가짐

 

 

4) Eventcount/Sequencer로 해결한 Producer-Consumer 문제

Producer측의 await(Out, t-N+1); 은 생산자와 소비자가 한 바퀴의 버퍼 차이가 날 때, 고객이 버퍼에서 데이터를 소비하기 전에 생산자가 해당 버퍼의 값을 갱신하는 경우를 방지하기 위한 부분이다.

예를 들어 N=10이고 t=10일 경우에는 생산자는 버퍼 한바퀴를 돌아 buffer[0]부분의 데이터를 갱신해줘야 한다.

그런데 소비자가 만약 buffer[0] 데이터를 가져가는 중이거나 아직 가져가지 않았다면 문제가 발생할 수 있는 것이다.

 

그리고 Consumer측의 await(In, u+1); 은 생산자가 버퍼에 데이터를 넣고 다음 순번으로 넘어갔을 때 소비자가 버퍼의 데이터를 가져가기 위해, In<u+1일 때 buffer에 접근하도록 하는 부분이다. 생산자가 버퍼에 올바른 데이터를 갱신하기 전에 소비자가 버퍼에 접근한다면 문제가 발생할 수 있는 것이다.

 

5) Eventcount/Sequencer의 장점

- No busy waiting

- FIFO -> No starvation

- Semaphore보다 더 low-level(구체적이고 복잡한) control이 가능

 

 

이미지 출처 : 한빛 미디어 운영체제

참고 자료 : 김덕수 교수님 - www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN