[운영체제] ep4-3) Concurrency: Mutual Exclusion and Synchronization

Concurrency 방안 3가지

1. Software Approaches - 알고리즘을 잘 설계

2. HW instruction을 이용

3. OS가 제공하는 동기화 툴 이용 (e.g. 세마포, 모니터)

1번과 2번에 이어 3번에 대해 알아보자

 

3. OS가 제공하는 동기화 툴 이용

2가지에 대해서 다룰 거다

ㅇ세마포(Semaphore): 정수 변수 + (blocked)큐가 결합된 구조체 변수

오로지 3개의 동작만 수행한다

 

① Initialize: 세마포를 0이나 양수값으로 초기화

(음수값으로 초기화 하는 건 의미가 없다)

 

② semWait: 세마포값 -1, "blocked 큐에서 wait!"

if (세마포값 >=0) 통과

else if(세마포값 < 0) 프로세스 blocked(blocked 큐에 가서 대기)

 

③ semSignal: 세마포값 +1, "blocked 큐에서 ready 큐로 이동 signal!"

 세마포값 +1 후에 만약 큐에 대기하고 있는 프로세스가 있으면 그중에 하나를 unblocked(ready 큐로 꺼낸다)

- 더한 값은 당연히 0이하다 (만약에 더한 값이 양수라면 대기하고 있는 프로세스가 없다라고 생각하면 된다)

 

Counting Semaphore

세마포 메커니즘

 

(여기서 알 수 있는 법칙)

세마포(s) = 0: 세마포 큐(blocked 큐)에 프로세스가 0개

세마포(s) = -1: 세마포 큐(blocked 큐)에 프로세스가 1개

세마포(s) = -2: 세마포 큐(blocked 큐)에 프로세스가 2개

 

 

프로세스를 semSignal(s)로 하나씩 이동시켜주는 순서에는 2가지 방식이 있다

ㅇStrong Semaphores: FIFO

들어간 순서대로 semSignal(s)

 

ㅇWeak Semaphores: 순서가 따로 정해져 있지 않다

요즘 대부분의 세마포 방식

 

 

ㅇBinary 세마포

 

 

<Binary 세마포의 상호배제>

Binary 세마포도 똑같다

세마포의 초기값은 매우 중요하다! (음수값으로 초기화 하는 건 의미가 없다)

 

Processes Accessing Shared Data Protected by a Semaphore

 

 

ㅁProducer/Consumer Problem

Producers 라는 프로세스들과 Consumers 라는 프로세스들이 있다

Producers: data를 만들어 버퍼에 집어넣는다

Consumers: 버퍼에서 data를 가져간다

 

(Bounded Buffer)

Finite Circular Buffer for the Producer/Consumer Problem

 

코드로 나타내면 다음과 같다 (세마포 사용 X)

functions in a Bounded Buffer

 

세마포를 이용해보자!

n: 버퍼에 들어있는 데이터의 개수

e: 버퍼의 빈자리 개수 (버퍼 크기)

Bounded Buffer using Semaphores

bust-waiting 문제 X

 

 

Q. 만약에 순서가 바뀐다면 어떻게 될까?

 

 

 

 

 

제안) 사용자가 모니터를 이용해서 상호배제 + 동기화 문제를 쉽게 해결

ㅇ모니터(Monitors): 세마포를 이용한 라이브러리 함수

<모니터의 구성>

- 변수들 (모니터 안에서만 사용 가능한 지역변수)

- function들

- 변수들을 초기화하는 코드

 

<모니터의 특성>

- 프로세스는 function을 통해 모니터 안으로 들어간다

- 모니터 안에서 한 프로세스만 실행 가능 (mutual exclusion)

- 동기화를 위한 condition 변수 有

cwait(c) = semWait(s)

csignal(c) = semSignal(s)

 

<모니터의 구조>

하얀색 부분: 모니터 / 회색 부분: 모니터에 들어가기 위해 큐에서 대기하는 영역

structure of a Monitor

 

모니터에 들어가기 위해 큐에서 대기

-> 모니터 자체가 mutual exclusion이 지켜지는 c.s.이다!

 

 

 

 

모니터를 이용한 Producer/Consumer Problem

Bounded Buffer Solution Using Monitor

 

Q. (잘못 작성된)세마포와 달리 모니터에서는 데드락이 안 생기는 이유

A. 모니터 안에서 멈춰있는 게 아니라 모니터의 바깥 큐에서 대기하고 있어서 (c.s.안에서 멈춰있지 않다)

 

 

 

 

 

ㅁReaders/Writers Problem

- Reader 두 명은 동시에 작업해도 O (단순히 읽는 거라 아무 영향 x)

- Writer 두 명은 동시에 작업하면 X (앞의 은행 예제와 같이 race condition이 발생)

W && W (X)

W && R (X)

R && W (X)

R && R (O)

 

[Reader가 우선권을 갖는 경우]

효율성 ↑

공정성 ↑

Starvation 방지

 

<readcount의 2가지 의미>

① 내가 첫 번째 reader인지 마지막 reader인지

② 몇 명이 같이 shared data를 읽고 있는지

 

모식도

 

(Writer가 우선권을 갖는 코드도 있기는 하다)

 

 

 

 

 

(3. OS가 제공하는 동기화 툴 이용 정리)

- 세마포

- 모니터

[장점]

Starvation X

busy-waiting X

3개 이상 process 가능

 

[단점]

multiple c.s.을 사용하는 경우에 데드락 O

 

 

 

 

 

<Concurrency 방안 3가지 총정리>

 

 

 

 

 

 

 

참고 및 출처: Operating Systems: Internals and Design Principles(William Stalling), Operating System Concepts(Silberschatz, Abraham)