[OS] Process Synchronization and Mutual Exclusion

yo·2020년 9월 5일

강의 이전 맥락

HW solution(TestAndSet(TAS) instruction이 해결책으로 나왔지만,
Busy waiting의 문제를 해결하지 못했고, 이를 해결하기 위해 os가 나서게 되는데....

OS supported SW solution

-Spinlock
-Semaphore
-Eventcount/sequencer

Language-Level solution

-Monitor

Spinlock

정수 변수(S)
초기화, P(), V()연산으로만 접근 가능하다.
위 연산들은 indivisible(or atomic)연산

OS support
전체가 한 instruction cycle에 수행 됨

설명
-s = a +1 같은 연산이 불가능하고 위의 세 가지 연산만 가능하다.
초기화 연산은 이름 그대로 초기화 하는 것.
위 연산들은 실행이 끝날 때 까지 쫓겨나지 않고 한 번에 완성됨. 이를 os가 보장해준다.

S 물건 갯수
P 물건 꺼내가는 것 (자물쇠를 거는 것)
V 물건 반납하는 것 (자물쇠를 푸는 것)

아래 그림을 보고 이해해보자.

기본전제: 연산 하나 시작하면 끝날 때 까지 작업 보장됨(중간에 쫓겨나지 않음, 하나가 끝나야 다음 게 시작됨

1)Pi가 먼저 연산 시작.
2)active가 1인 상태에서, Pi의 P가 실행되며 0으로 바뀜.
3)Pi의 V가 실행되며 active가 1로 다시 바뀜.
4)Pi가 끝나고, 그제서야 Pj시작
5)2~3과정 반복.
결과적으로 Mutual exclusion보장됨.
동시에 들어가거나, 둘 다 못들어가는 문제 다 해결됨.
Q) os가 도와주니 문제가 이렇게 쉽게 해결되는데, 그동안 HW, SW로 이 문제 해결하려 한 시도들은 다 뻘짓 아닙니까?
A)그런 노력들의 끝에 이런 결과가 나온거다.

Spinlock의 문제점

Spinlock은 CPU가 하나일 때 문제가 크다.
Pi가 Critical Section에서 멈췄다 치자.
active는 Pi의 P를 지나며 0이 됐을거다.
Pi가 멈춘다는 건 CPU를 빠져나온다는 얘기다.
곧이어 CPU로 Pj가 들어온다. 하지만 active가 0 이므로 P에서 계속 돌기만 한다.
작업이 진행이 안된다.
Pi는 다시 들어갈라 해도 Pj가 선점하고 있기 때문에 못들어간다.
문제는 이 와중에 Pi로 while문을 계속 돌고 있다.
한 번 시작하면 끝날때까지 작업이 절대 끝나지 않는 Spinlock의 특성 때문이다.

결론:
-Spinlock은 멀티 프로세서 시스템에서만 사용 가능하다.
-위 문제 경우처럼 Busy Waiting이 해결 안된다.

이것을 해결하기 위해 Semaphore가 나오는데......(Semaphore는 32분짜리 강의다...ㄷㄷ)

Semaphore

<개요>
-1965년 Dijkstra(님)이 제안한 방법
-Busy waiting문제를 해결해버림
-semaphore는 음이 아닌 정수형 변수(s)
-초기화 연산, p(), v()로만 접근 가능
-P: Probern(검사)
-V: Verhogen(증가)
(참고로 네덜란드어)

이까지 보면 뭐야, 이거 Spinlock이랑 똑같은데? 싶다.
-임의의 s변수 하나에 ready queue 하나가 할당됨
요게 중요한 특성임.

Binary semaphore vs Counting semaphore

Binary semaphore
-s가 0과 1 두 종류의 값만 갖는 경우다.
-상호배제나 프로세스 동기화의 목적으로 사용

Counting semaphore
-s가 0 이상의 정수값을 가질 수 있는 경우
-producer-Consumer문제 등을 해결하기 위해 사용한다.(생산자-소비자 문제)

일단 대충 이렇게 뜻만 알아놓으라고 선생님이 말씀하셨으니 이쯤 하고 pass

Semaphore 작동 기본원리

Semaphore로 해결하는 문제

상호배제 문제 먼저 해결해보자

프로세스 동기화 문제를 해결해보자

여기서 비동기적이라는게 무슨 뜻일까?ㅜㅜ

producer-consumer problem을 정의하고 해결해보자

1)문제정의
-프로듀서가 물건을 놓는 동안 컨슈머가 가져가면 안됨/컨슈머가 가져갈 때 프로듀서가 물건 놓으면 안됨.
-프로듀서가 물건을 놓을 때, 또 다른 물건을 동시에 놓아선 안됨.(동기화 필요)

Single buffer일 때

버퍼 크기가 n일 때

생산자 여러 명, 소비자 여러 명, 버퍼도 여러 개인 상황이다.
한 번에 한 명만 일 해야한다.

nrfull:찼니? (물건의 수=채워진 buffer 수)
nrempty: 비었니?(빈 공간의 수= 비어있는 buffer 수)
mutexP: producer에 대해 mutual exclusion거는 것
mutexC: Counsumer에 대해 mutual exclusion거는 것

Producer Pi과정
1)create a new message M: 물건 만듬
2)P(mutexP): 화장실 들어가서 문 잠그듯, 나 이제 쓴다 하고 자물쇠 잠금(다른 Producer못들어오게)
3)P(nerempty): 빈 공간(물건 만들어 채울 공간)있는지 보고, >0이면 나 이제 물건 놓을게 하고 잠금.
3-1)만약에 공간 없으면 대기실에서 자다가, 공간 생겼을 때 들어감.
4)buffer[in] <-M: 버퍼에 물건 놓기
5)in <-(in + 1) mod N: 다음에 물건 놓을 공간을 업데이트 해주기
6)V(nrfull): 나오면서 물건 수 +1해주기, Counsumer대기실 가서 잠자는 애 있으면 깨우기
7)V(mutextP): 나오면서 잠금 해제

Consumer Cj 과정
1)P(mutextC): 들어갈가면서 다른 컨수머 못들어오게 문 잠그기
2)P(nrfull):물건 확인, >0이라면 안에 들어가기, 아니라면 대기실에서 잠자기
3)m <-buffer[out]: 버퍼에서 물건 꺼내오기
4)out<- (out +1) mod N: 꺼내는 위치 갱신
5)V(nrempty): 공간이 +1됐다 표시, Producer대기실 가서 잠자는 애 있으면 깨우기
6)V(mutextC) : 문 잠금해제

Reader-Writer problem

reader: 여러 명 동시에 읽기 됨
Writer: 한 명만 써야됨
읽고 있을 땐 쓰면 안됨
writer끼리 상호배제, reader-writer간 상호배제 필요

Solution!!!!!!!!!!!!!!!

wmutex: Writer mutex
rmutex: Reader mutex
nreaders: reader의 수

우측의 Writer Wj 먼저 살펴보자.
1)P(wmutex): writer작업시작, 문 잠금(다른 writer못 들어오게)
2)Perform writer operations: 쓰기작업
3)V(wmutex): 쓰기 완료, 문 열고 나가기

엄청 간단하다.

좌측의 Reader Ri를 살펴보자. 복잡해 보이는데 별거 아니다.
reader는 동시작업 가능하다 했는데, 왜 mutex가, 그것도 두 쌍 씩이나 있는거지? 라고 생각이 들었다면
이 수업을 잘 따라가고 있는 거다.
먼저, 위에 rmutex는 읽으러 들어갈 때, 아래는 읽고 나올 때다. 읽는건 여러명이 읽을 수 있지만, 사전, 사후 작업은 딱 한 명만 할 수 있다.
1)P(rmutex):사전작업 드가면서 문 잠그기
2)

if(nreaders =0) then
	P(wmutex);
  endlif:

P(wmutex): 나 읽을거니까, writer야 너는 쓰지마 하고 문 잠그기
이 작업은 nreaders = 0일 때만 한다.
0> 라면 이미 읽고 있는 reader가 이 작업을 했을 것임으로 생략한다.

nreaders <-nreaders + 1 : 나 읽으니까 읽는 사람 수 하나 증가시킨다~
V(rmutex): 잠금해제
Perform read operations: 읽기작업 (이 단계는 여러명의 reader가 있을 수 있다.)
P(rmutex):사후작업 시작, 잠그기
nreaders <-nreaders -1; 리더 하나 빼기

if (nreaders =0) then
	V(wmutex);
endlif;

내가 마지막 독자였다면, 이제 누군가 쓸 수 있게 잠금상태였던 wmutex잠금해제하기
만약 >0이라면 아직 누군가 읽고 있는 거니까 그냥 패스.

Semaphore 결론

No busy waiting

기다리는 프로세스는 block(asleep)이 된다->계속 돌지 않아도 됨->busy waiting해결!

Semaphore queue에 대한 wake-up순서는 비결정적

Starvation problem
wake up one of them, 즉 대기실 찾아가서 누구 깨워주긴 하는데, 어떤 순서 없이 아무나 잡고 꺠우는 거라 이게 문제가 될 수 있다.
이를 해결하기 위한 방법이 다음 강의에 나온다.

Eventcount/Sequencer

개요

Semaphore의 starvation problem을 해결하기 위해 등장.
은행의 번호표와 비슷한 개념
Sequencer
-정수형 변수
-처음 생성시 0으로 초기화되고, 숫자가 감소하지 않고 증가만 한다.(은행 번호표 숫자가 줄지 않듯이)
-ticket()연산으로만 접근 가능

ticket(S)
-현재까지 ticket()연산이 호출 된 횟수를 반환
=번호표 뽑는 행위와 같음
-번호표 뽑으면 현재 번호 출력되고, 동시에 번호가 +1되는 것과 같은 이치.(sequencer += 1)
-indivisible operation

Eventcount

=은행 번호 기계
-정수형 변수
생성시 0으로 초기화, 감소하지 않음
-특정 사건의 발생 횟수를 기록
-read(E), advance(E), await(E,v)연산으로만 접근 가능

read(E)

-현재 Eventcount값 반환

advance(E)

=은행원이 번호기계 누르는 행위(다음 고객님~)

E <-E + 1
E를 기다리고 있는 프로세스를 깨움(wake-up)

await(E,v)

-v는 정수형 변수
-if(E <v)면 E에 연결된 QE에 프로세스 전달(push) 및 scheduler 호출
=만약 내 번호(v)가 현재 번호(E)보다 크면 기다린다, 대기실(Q)에서, E=v가 될 때 까지.

Mutual exclusion해결

Producer-Consumer problem 해결

결론

No busy waiting
No starvation(FIFO scheduling for QE)
Semaphore보다 더 low_level control이 가능(순서 컨트롤 가능하다)

Monitor(Language_Level solution)

그동안 봐왔던 해결법들: Difficult to use, Error-prone, Low-level Mechanism

그래서 두둥 High-level Mechanism나왔다. 그것은 'Monitor'. 사용이 아주 쉽다.

Monitor 기본개념

-공유 데이터와 Critical section의 집합(무슨 소리지)
-Conditional variable(무슨 소리지)
(뒤에가면 이해됨)
-wait(), signal() operations
-모니터는 1명씩만 들어올 수 있는 책방의 개념이다.

-critical data: 빌리고 싶은 책(1권 밖에 없음)
-Critical sections: 책방, 책방에서 하는 연산

Monitor 구조

-procedure은 function이라 생각하면 됨.
-mutual exclusion을 language가 보장해줌.
-condition queue: 특정 조건을 기다리는 큐
-signaler queue: 전화부스와 같은 것, 시그널을 보내기 위해 잠깐 들어가는 곳.너 이제 나와서 일 해도 돼!
예제 보면 이해 됨.

*참고로 C#, C++, F#, VB, JAVA에 Monitor class있다.

자원 할당 문제

Producer-Consumer Problem

-fillBuf-물건 넣는 애(producer)
-emptyBuf-물건 가져가는 애(consumer)
-conditional queue2개(bufHasData, bufHasSpace)
-bufHasData: 물건 있니?(consumer가 물어봄)
-bufHasSpace: 공간 있니?(producer가 물어봄)
-in: 위치(물건 어디다 넣을지) shared data
-out: 위치(물건 어디서 빼갈지) shared data
-validBufs:물건 개수, shared data