운영체제 5장 Concurrency : Mutual Exclusion and Synchronization



# Race Condition on critical section
concurrent 하게 실행시 문제가 된다
순서에 따라서 틀린 결론이 나온다, 실행 순서에 따라 결과가 결정되는 상황이 발생


#
Deadlock - 1개 리소스에 여러 프로세스가 경쟁하며 양보 기다림
Starvation - 계속 기다리는 경우



# Mutual Exclusion

상호 배제가 보장되어야 한다, 단 한개의 프로세스만 critical section에 들어가야 하고, 둘이 섞이면 안된다.
모든 프로세스는 critical section이 비어있으면 들어갈수 있고
유한시간만 critical section에 머무를 수 있다
다른 프로세스를 방해하지 않아야 한다.
프로세스들의 상대속도에 대해 어떤 가정도 하지 않아야 한다


# 가장 간단한 방법 Hardware support

방법 1.
interrupt disabling - 리눅스는 이렇게 구현, 멀티프로세서는 비효율적
uniprocessor 경우 interrupt disable 시키면 다른 프로세스가 실행중 상태 프로세스를 중단시킬수 없다.
단점은 효율이 떨어지고, 멀티프로세스에서 사용불가 
interrupt disable 시킨다는건 버스를 중단시킨다는것, 다른 프로세서들도 메모리에 접근 불가능하게 되므로 효율 떨어짐


# 
방법 2.
Special Machine Instructions - compare & swap Instruction (compare and exchange instruction)
메모리 값을 비교하고 스왑하는 연산을 한 클럭에, Fetch, inst~ (atomic 하게 이루어져서 중단할수 없다, 중간에 인터럽트 불가)


한명이 bolt 변수를 획득하면 다른사람은 불가
critical section 마친 뒤에는 다시 0으로 되돌려 놓는다
여러 프로세스가 동일한 과정을 거쳐서 critical section 들어가면 자원을 상호배제적으로 이용가능


다른 방법 : exchange - bolt값을 자신이 가진 key값으로 교환
원리 같음



장첨 - 몇개의 프로세서든 사용가능, 간단하게 사용가능, 변수를 여러개 만든다면 multiple critical section에도 가능
단점 - Busy-waiting (한 프로세스가 들어가면 나머지는 대기), Starvation(버스를 무작정 기다리는것, 경쟁에서 누가 이길지 모름), Deadlock (공유자원이 여러개일때 하나를 잡고 다른 자원을 놓아주도록 계속 기다림) 



# 세마포어

하나의 클래스
음수가 아닌 정수로 초기화, 초기화된 변수에 대해 2가지 연산


세마포어는 신호등이란 뜻으로
프로세스가 신호등을 기다리고, 자원을 기다리고 허용되면 critical section에 들어가도록 보장해준다 
프로세스가 decrement 시키기 전에는 block될지 진행될지 알수없다
2개 프로세스가 실행될때 어떤것이 먼저 실행될지 결정적이지 않다
프로세스는 이전의 몇개의 프로세스가 먼저 기다리고 있는지 알수없다


busy-waiting 해결 위해 세마포어는 PCB를 쌓아두는 큐를 만들어둔다
critical section에 들어갈수 없다면 큐에 대기하도록 함 


busy-waiting을 해결했음을 알수있다.
??

strong 세마포어 - 큐를 관리할때 fifo로 blocked process를 released 하는것
weak - 순서에 대해 별도의 정책 없음




# 



처음에 1로 초기화
나머지는 레디 큐에 대기
blocked queue는 세마포어를 위한것, ready queue는 process management에서 관리


처음에 1로 초기화
자원이 1개 있을때, A가 semWait() - 0(자원이 없다)
B가 semWait() - -1 (1개가 대기하고 있다)
C가 semWait() -  -2 (2개가 대기하고 있다)
A가 semSignal() - -1 (release하면 queue에 있던 B가 critical section 들어감)
...
critical section이 mutual exclusive 하게 사용되도록 한다



# 대표적 문제

위의 그림이 리소스를 생성하고 소비하는 프로세스의 예시를 보여주고 있는데
이것을 Producer/Consumer Problem 이라고 한다
1개 그 이상의 Producer가 data를 생성하고 버퍼에 넣는다
1개의 Consumer가 그것을 가져다가 처리한다
중요한것은 1개의 producer, consumer만 버퍼에 접근할수 있다

버퍼가 가득차면 data를 집어넣을수 없고, consumer는 버퍼가 비어있으면 꺼내갈 수 없다는것을 보장



producer는 data를 넣을때 in pointer 사용
consumer는 가져갈때 out 사용
버퍼 크기는 무한대



처음 버퍼에 들어있는 data수 n = 0 초기화
만약 자원을 다 썼다면 delay, delay는 처음에 0이므로 semWait 부르면 마이너스가 된다

복잡해보인다.
버퍼가 가득차면 data를 집어넣을수 없고, consumer는 버퍼가 비어있으면 꺼내갈 수 없다는것을 보장 -> 이것을 해결하는 것이 간단하지는 않다



이것을 해결하는 가장 간단한 코드
Producer도 semWait(), semSignal() 
Consumer도 semWait(), semSignal() 상호 배제적으로 critical section 보호

버퍼가 가득차면 어떻게 할지는 semWait() 을 이용해서
처음에 n = 0 이므로, producer가 증가시키는만큼 data 개수를 의미하게 된다
그것이 0이라면 모든 consumer는 semWait(n)에서 기다리게 된다
producer가 돌면서 증가시키면 consumer는 세마포어를 통과해서 실행하게 되는것

프로세스간 상호 배제적으로 실행할수 있는것은 s로
버퍼에 있는 데이터 개수는 n으로 해서 비어있을때 가져갈수 없도록 함




유한 버퍼의 경우
producer는 버퍼가 가득 찼을때 block
consumer는 버퍼가 비어있을때
producer는 데이터를 더 넣을수 있으면 unblock
consumer는 데이터를 사용할수 있으면


세마포어 s로 critical section을 보호하는것은 같다
n도 똑같다.
처음 버퍼의 사이즈는 e로 만들어주고, 버퍼 사이즈가 가능한만큼 데이터를 추가할수 있도록 만들어준다
하나 소비할때마다 e값을 증가시켜서 버퍼가 있음을 유지

서로 대칭적으로 맞물려 돌아가도록 작성되어 있다.

(이 부분은 암기)



세마포어를 구현하는 방법은 다양하게 있는데
두 연산자는 atomic하게 구현되어야 한다
hw,sw로 구현될수 있다.




# monitor
세마포어 구현이 복잡하므로 
모니터는 프로그램 언어에서 세마포어와 동일한 기능을 제공하도록 한것
자바에서 synchronized




지역변수를 모니터라는 하나의 프로시저 안에서만 접근할수 있도록 하고
프로시저에서는 하나의 프로세스만 들어갈수 있도록 해서 상호배제를 보장
한번에 하나의 프로세스, 스레드만 함수 안에 들어갈수 있게 해서 상호배제 보장



# message passing
프로세스와 다른 프로세스가 interact 할때 두가지가 만족되어야 한다
동기화 - 상호 배제적으로 critical section 사용할수 있어야
communication - 데이터를 서로 교환할수 있어야
이것을 허용해주는것이 message passing

분산 시스템에서 활용


목적지와, 원천지 주소가 들어감




메시지를 주고받을때 동기화가 이루어지는데
다른 프로세스에 의해 보내지기 전에는 리시버는 받을수 없다.(기다리게 됨)
어떤 리소스에 대해 반응하려면 기다려야 하는 동기화가 일어나는것

도착한 메시지가 없다면 블록되는 경우가 있을수 있고
없어도 그대로 계속되는 경우가 있을수 있다, 두 경우 다 만들어짐
메시지가 있으면 받아서 실행을 계속하는 경우 ....


메시지가 도착할때까지 블럭되는가 안되는가에따라 여러가지 방법이 제공되고 있다
블럭되는 경우를 랑데뷰라고 함
이것을 이용해서 강한 synchronization이라고 함



블럭되지 않는 경우는
nonblocking send, blocking receive - 가장 좋은 방법, 보통 사용

nonblocking send, blocking receive - 큐에 쌓아놓고 처리(대용량)




addressing에 따라서
주소값을 직접주소를 주는방법
간접주소를 주는 방법이 있다.


구현방법에는 여러가지가 있다

일반적으로 주고받는 메시지 포맷
헤더 - envelop
보낸 메시지 자체는 body에


semaWait() 대신 receive
semaSignam() 대신 send
메시지를 가져간것만 critical section으로




message passing 이용해서 producer/consumer 문제 해결
비어있는 개수만큼 메일 보냄
세마포어 - 오버헤드 작다, 게임 서버라면...
메시지 - 배달앱, 일기예보같은... Rest api의 원형