Process Syncronization & Mutual Exclusive

원래 이렇게 TIL 자세히 쓰는 거 좋아하지 않지만 

운체 배울 때 배속으로 들어서 그런가 이해가 한 번에 안 되었음 ㅋㅋ 특히 process가 N개 일 때..

그래서 나중에 또 잊어버릴 수도 있을 거 같아서 좀 자세히 정리하려고 함.  

 

Introduction

어떤 도화지가 있을 때 a가 거기에 그림을 그리고 b가 그 위에 그림을 그린다면 엉망이 될 것이다. 

따라서 a, b는 서로 대화를 해서 약속을 정해야할 것이다. 즉, 정보를 공유하고 동작을 맞춰야 할 것이다. 

 

이를 multi programming system에서의 syncronization이라고 한다. 

 

프로세스들은 서로 어떻게 동작하는지 모른다. 비동기적인데 시스템에는 Concurrent 하게 여러 개의 프로세스들이 존재한다. 자원을 공유할 때 문제가 생길 수 있으므로 우리는 syncronization을 해줘야만 한다. 

 

Terminologies

 

shared data or critical data 

여러 프로세스들이 공유하는 데이터 

 

Critical section 

공유데이터에 접근하는 code segment.

 

Mutual exclusive

둘 이상의 process가 critical section에 접근하는 것을 막는 것. 

 

Machine Instruction 

기계어 명령으로 atomicity와 indivisible 특성을 지님

즉, 한 기계어 명령 실팽 도중에 interruption을 받지 않게 됨. 

그래서 수행되면 반드시 끝날 때까지 수행하게 된다. 

우리가 짠 code를 compiler가 MI로 번역해주는데 MIPS 라고 생각해도 될 듯. 

완전 assembly 언어임.

 

근데 각 MI 사이에는 preemption이 발생할 수 있는데 (process가 CPU를 deallocation 된 상태라고 이해하면 됨.)

그래서 우리가 원하는 동작을 수행하지 않을 수도 있게 된다. 명령의 수행 과정에 따라 결과값의 신뢰도가 떨어지는 

Race condition이 발생하게 된다. 

 

따라서 이를 해결하기 위해 Mutual exclusive개념이 등장하였고 

우리가 CS에서 동작하는 동안 다른 process의 접근을 막아주게 되어 data를 덮어쓰는 등의 문제를 해결하려고 하였다. 

mutual exclusion primitives는 다음과 같이 구현된다. 

 

enterCS() : CS들어가기 전 다른 프로세스가 있는지 검사.

exitCS() : CS를 벗어나면 벗어났다고 알려주는 역할. 

 

이런 개념들을 구현한 OS의 발전 과정을 살펴보자!

구현을 위해선

ME:mutual exclusion

progress : CS안에 있는 프로세스 외 다른 프로세스가 진입 방해할 수 없음.

BW:bounded waiting-프로세스의 CS진입은 한정시간 이내

 

3가지 조건들을 만족해야 한다. 

 

1. 처음엔 turn 을 이용한 개념으로 접근했다. 

내 턴이면 진입하고 진입 후에는 turn을 변경해주는 코드. 

 

처음에 turn 이 정해져있었고 그 turn에 해당하는 process가 CS 진입 전 체크하는 code에서 죽어버리면 

다른 프로세스들은 영영 들어갈 수 없는 Prog조건을 위반한다. 

또한 process가 일처리`를 너무 빨리해서 다른 프로세스가 오기 전에 다시 repeat를 시도한다면

다른 프로세스의 turn이라서 여전히 진입을 할 수 없는 Prog조건 위배.

 

2. flag로 해보자. 

들어갈거면 깃발을 들고 아니라면 내리자.

상대편 깃발을 확인하고 진입이 가능하면 내 깃발을 올리고 CS진입

exit후에는 깃발 내려주자. 

 

상대편 깃발이 내려가 있어서 진입하고 깃발을 올리기 전 preemption된다면? 

다른 process가 도착해서 보니 상대 깃발 없다고 생각해서 CS에 진입할 것이다. 

이 때 다시 CPU가 allocation되어 처음 프로세스가 CS에 진입한다면 ME조건을 위배하게 된다. 

 

3.그렇다면 깃발을 먼저 들면 괜찮지 않을까?

 

근데 깃발을 들고 preemption된다면, 다른 프로세스가 깃발을 들고 들어오게 되고

처음 프로세스가 깃발을 든 것을 보고 while문을 돌고 있을 것이다. 

처음 프로세스가 다시 allocation되어도 다른 프로세스가 깃발을 든 것을 보고 

while문을 돌게 되겠지. 그래서 Prog와 BW 두 개를 위반하게 된다. 

 

4.그렇다면 깃발과 턴을 같이 쓰면 되지 않을까?

Dekker's Algorithm이 등장하게 된다. 

 

turn =0인 상태에서 CS진입 전 check 하는 code에서 첫번째 프로세스가 죽어버려도 다른 프로세스는 진입이 가능하고

둘 다 깃발을 들고 있어도 안 에서 turn을 한 번 더 check하게 됨으로서 ME, prog, BW가 해결되었다. 

 

음 여기서 Dekker의 알고리즘보다 조금 더 간단하게 구현한 Peterson의 알고리즘이 있는데 

turn을 양보하면서 좀 더 간단하게 code를 구현할 수 있게 되었다. 

=

5.자 그럼 이제 N개의 process가 있을 때를 살펴보자.

Dijkstra님의 알고리즘 중 하나를 보자. 이 분은 님자를 붙여야 함... ㅎㄷㄷ

마찬가지로 flag를 보는데 state를 3개로 구분하게 된다. 

 

idle : 프로세스가 들어올 생각이 없는 것,. 별로 신경쓰지 말자.

want in : 들어가고 싶다고 의사를 밝힘.

in CS : CS진입 직전.

 

나는 여기서 2단계인 in-CS가 잘 이해가 안 되었는데 지금은 이해함.

j가 counter변수이고

pseudo code는 다음과 같다. 

while( (j<n) & (j= i or flag[j] is not in-CS) ) 

j가 n보다 작고 j=i 의 뜻인 나일 때는 pass해서 다음거 살펴보고

flag[j] is not in_CS는 나 말고 다른 프로세스가 CS에 있으면 loop가 깨져서 want in 부분으로 돌아가게 된다. 

즉 in-CS에 나 혼자 있는 경우에만 CS영역으로 들어가게 된다. 그렇게 해서 한 명만 들어가는 조건을 만족시키게 된다. 

 

지금까지 SW solution을 살펴보았는데. 단점이 있다.

1. 뭔가 뺑뺑 돌게 되어서 속도가 느리고

2. 코드만 봐도 구현이 복잡하다. 

3. code한줄은 반드시 실행된다고 가정했는데 사실 MI로 complie 하면은 그 중간 preemption이 일어날 수도 있다.

4.Busy waiting 기다리면서 뺑뺑 도는 상태... 비효율적

 

이를 해결하기 위해 HW solution이 나오게 된다.