프로세스 동기화 (Process Synchronization and Mutual Exclusive)

이 글은 앞서 포스팅한 공룡책 6장 프로세스 동기화에서 이해되지 못한 부분을 정리하기 위해서 작성한 글입니다.

다르거나 이상한 점이 있다면 댓글로 알려주시면 감사하겠습니다.

---

Process Synchronization (동기화)

• 다중 프로그래밍 시스템
  • 여러 개의 프로세스들이 존재합니다.
  • 프로세스들은 서로 독립적으로 동작합니다. 즉, 동시에 동작합니다. 만약 공유 자원을 동시에 접근하려고 하면 문제가 생길 수 있습니다. 예를들어 한 종이에 두 명의 사람이 그림을 그리려고 하는데, 한 종이에 두 사람이 동시에 그림을 그리면 그림은 엉망이 됩니다. 그래서 그림을 그리기 위해 대화를 해야하는데, 이 대화하는 행위가 동기화입니다.
  • 공유 자원 또는 데이터가 있을 때, 문제 발생 가능합니다.
• 동기화 (Synchronization)
  • 프로세스들이 서로 동작을 맞추는 것입니다.
  • 프로세스들이 서로 정보를 공유 하는 것입니다.

Asynchronous and Concurrent P's

• 비동기적 (Asynchronous)
  
  • 프로세스들이 서로에 대해 모릅니다.
• 병행적 (Concurrent)
  • 여러 개의 프로세스들이 동시에 시스템에 존재합니다.
• 병행 수행중인 비동기적 프로세스들이 공유자원에 동시 접근할 때 문제가 발생 할 수 있습니다. 동시에 작업을 하고 있는데 서로 대화가 없어서 모른다면, 문제가 발생할 수 있습니다.

Terminologies (용어 정리)

• Shaerd data (공유 데이터) or Critical data
  • 여러 프로세스들이 공유하는 데이터입니다.
• Critical section (임계 영역)
  • 공유 데이터를 접근하는 코드 영역(code segment)
• Mutual exclusion (상호배제)
  • 둘 이상의 프로세스가 동시에 critical section에 진입하는 것을 막는 것입니다.

Critical Section (example)

• 이런 상황에서는 2가 되기를 원하고 작업을 할 것입니다. 하지만 꼭 그렇진 않습니다. 기계어 명령(machine instruction)의 특성 때문입니다.
  • 기계어 명령의 특성으로는 Atomicity (원자성), Indivisible (분리불가능)이 있습니다. 즉, 한 기계어 명령의 실행 도중에 인터럽트를 받지 않습니다.
  • 아래와 같은 그림으로 명령 수행 과정에 따라 답이 달라질 수 있다는 것을 주의해야 합니다.
  • 이처럼 실행 과정에 따라 결과가 달라지는 것을 Race condition이라고 합니다.

Mutual Exclusion (상호배제)

• 방금과 같은 문제를 막기 위해선 어떻게 해야 할까요? 그래서 등장한 개념이 상호배제입니다. 즉, 한 프로세스가 실행하는 동안 다른 프로세스가 들어와선 안됩니다.
• Mutual exclusion primitives(연산)
  • enterCS() primitive
    • Critical section 진입 전 검사
    • 다른 프로세스가 critical section 안에 있는지 검사
  • exitCS() primitive
    • Critical section을 벗어날 때의 후처리 과정
    • Critical section을 벗어남을 시스템이 알림
• 그럼 실제로 어떻게 enterCS()와 exitCS()를 어떻게 구현할까요? 만들기 전에 필요조건을 생각해봅시다.

Requirements for ME primitives

• Mutual exclusion (상호배제)
  • Critical section (CS)에 프로세스가 있으면, 다른 프로세스의 진입을 금지
• Progress (진행)
  • CS 안에 있는 프로세스 외에는, 다른 프로세스가 CS에 진입하는 것을 방해 하면 안됨
• Bounded waiting (한정대기)
  • 프로세스의 CS 진입은 유한시간 내에 허용되어야 함, CS 진입까지 계속 기다려선 안된다는 뜻입니다.

여기까지 필요조건을 구분해봤으면 직접 짜보도록 합시다.

Version 1. Two Process Mutual Exclusion

turn이라는 변수를 둬서 turn을 상대편에게 넘겨주는 식으로 일을 진행시키게 만들었습니다. turn은 0과 1이 있습니다. 그렇다면 이 식은 3가지를 모두 만족할까요?  만약 P0이 실행 중 turn <- 1을 실행하지 못하고 종료된다고 했을 땐 turn이라는 변수는 영원히 변경이 되지 않기 때문에 P1이 들어갈 수 없습니다. 즉, Progress 조건 위배 입니다. 또한, 한 Process가 두 번 연속 CS에 진입 불가능합니다.

Version 2. Two Process Mutual Exclusion

turn으로 하니 문제가 있으니, 깃발이라는 변수를 만들어 봅시다. 만약 CS에 들어가 있으면 깃발을 들고, CS에 안들어가면 깃발을 내립니다. 이 방법은 괜찮을까요? while이 끝나고 P0가 인터럽트로 인해 다른 일을 하고 올 동안 P1이 다시 재진입을 할 수 있습니다. 거기서 P0가 다른 일을 마치고 CS에 진입하면 Mutual exlcusion 조건에 위배가 됩니다.

그러면 깃발을 먼저 들어보면 어떻게 될까요?

이런 경우엔 서로의 깃발이 들어있어서 Progress, Bounded waiting 조건 위배가 됩니다.

---

이 전에 설명한건 대단히 기초적인 Mutual Exclusion (상호배제) 솔루션이었습니다. 이제는 좀 더 효과적인 상호배제 솔루션을 보도록 하겠습니다. 아래와 같은 해결 방법이 있습니다.

Mutual Exclusion Solutions

• SW solutions
  • Dekker's algorithm
  • Dijkstra's algorithm
• HW solution
  • TestAndSet (TAS) instruction
• OS supported SW solution
  • Spinlock
  • Semaphore
  • Eventcount/sequencer
• Language-Level solution
  • Monitor

---

SW solutions

Dekker's Algorithm

• Two process ME을 보장하는 최초의 알고리즘입니다.

• 아이디어는 flag와 turn을 같이 쓴 것입니다.
• 우선 깃발을 들고 확인하고 그 다음 turn을 확인 합니다. 턴을 확인하고 본인 턴이 아니면 깃발을 내리고 자기 턴을 기다립니다. 자기턴이 오면 그제서야 깃발을 들고 CS에 진입합니다. CS가 끝나면 turn을 넘겨주고 깃발을 내립니다.
• Peterson's Algorithm이라고 있는데, Dekker's Algorithm을 보다 축약한 버전입니다.

• 2개 짜리를 했으니 N개짜리를 보도록 합시다.

Dijkstra

• 최초로 프로세스 n개의 상호배제 문제를 소프트웨어적으로 해결했습니다.
• 실행 시간이 가장 짧은 프로세스에 프로세서 할당하는 세마포 방법입니다. 가장 짧은 평균 대기시간을 제공합니다.
• 마찬가지로 flag[] 변수를 이용합니다. 변수가 좀 많습니다.

flag[] 값	의미
idle	프로세스가 임계 지역 진입을 시도하고 있지 않을 때
want-in	프로세스의 임계 지역 진입 시도 1단계일 때
in-CS	프로세스의 임계 지역 진입 시도 2단계 및 임계 지역 내에 있을 때

• idle은 깃발을 내린 상태입니다. want-in은 CS에 들어가고 싶다고 의사를 밝히는 단계입니다. in_CS는 거의 진입하기 직전의 단계입니다.

• 변수 turn은 현재 진행 중인 프로세스 번호입니다.
• 임계 지역 진입시도 2단계 부분에서 while 문을 보시면 결국 in-CS 영역이 자기 자신밖에 없을 때 j를 빠져나오게 됩니다. 누군가 있으면 until에서 걸러져서 다시 repeat문을 실행합니다.
• 운이 없어서 여러번 못 들어갈 수 없지만, bounded waiting 조건을 위배하진 않습니다.

SW solution들의 문제점

• 속도가 느립니다.
• 구현이 복잡합니다.
• ME primitive 실행 중 preemption 될 수 있습니다.
  • 공유 데이터 수정 중은 interrupt를 억제 함으로서 해결 가능하지만 overhead가 발생할 수 있습니다.
• Busy waiting
  
  • 아무것도 안하고 기다리는 데 실행은 계속하는 중인 상태입니다.

---

HW solution

TestAndSet (TAS) instruction

• Test와 Set을 한번에 수행하는 기계어입니다.
• 기계어 수준에서 실행 중 interrupt를 받지 않습니다. (preemption 되지 않음)
• Busy waiting이 존재합니다.

target이라는 값이 있고 이를 잠시 temp에 넣고 target을 true로 만들고 temp를 리턴합니다. target의 현재 값을 반환하면서 target 값을 바꾼다는 것을 한 번에 수행한다는 것을 유의해야합니다.

이렇게 하면 간단하게 상호배제가 간단히 해결됩니다.

lock의 초기값이 false이면 TAS를 거치면 return은 false가 되고 lock은 true가 됩니다. 이 상태에서 다른 프로세스가 들어가면 True인 상태니 CS()에 못 들어갑니다.

단, 3개 이상의 프로세스의 경우, Bounded waiting 조건을 위배합니다. 기다리고 있는 두 개의 프로세스 중 하나만 채택되어서 들어간다면 못 들어가는 프로세스가 있을 수 있기 때문입니다.

위의 식은 N개짜리 프로세스가 있을 때 상호배제를 하는 방법입니다. key가 있고 waiting이 있다는 것을 유의 깊게 봅시다.

• HW Solution
  • 장점
    • 구현이 간단
  • 단점
    • Busy waiting
      • Inefficient
  • Busy waiting 문제를 해소한 상호배제 기법
    • Semaphore
      • 대부분의 OS들이 사용하는 기법

---

OS supported SW solution

HW 솔루션도 보았지만 여전히 Busy waiting이 존재합니다. 그래서 OS가 지원하는 솔루션을 적용해보겠습니다.

Spinlock

• 정수 변수를 Spinlock이라고 합니다.
  • S는 물건의 양으로 S가 있으면, 그 것을 하나 들고 CS에 입장합니다.
• 초기화, P(), V() 연산으로만 접근 가능합니다.
  • P(), V() 연산은 OS가 보장해주기에 중간에 선점 되지 않습니다.

• S가 1 이상이면 CS에 들어가기 전에 P()로 자물쇠를 걸고, V()는 자물쇠를 여는 행위입니다.

• active는 Spinlock 변수입니다.
• active = 1 : 임계 지역을 실행중인 프로세스 없음
• active = 0 : 임계 지역을 실행중인 프로세스 있음

스핀락의 단점으로는 멀티 프로세서에서만 사용 가능합니다. 그리고 Busy waiting이 존재합니다.

Semaphore

Spinlock을 사용했지만 Busy waiting 문제가 여전히 존재합니다. 그래서 세마포어가 탄생했습니다.

• 음이 아닌 정수형 변수를 세마포어라 합니다. (S)
  • 초기화 연산, P(), V()로만 접근 가능합니다.
  • 임의의 S 변수 하나에 ready queue 하나가 할당 됩니다. (Spinlock과 Semaphore의 결정적 차이입니다)

Semaphore의 종류

• Binary semaphore
  • S가 0과 1 두 종류의 값만 갖는 경우
  • 상호배제나 프로세스 동기화의 목적으로 사용
• Counting semaphore
  • S가 0이상의 정수값을 가질 수 있는 경우
  • Producer-Consumer 문제 등을 해결하기 위해 사용
    • 생산자-소비자 문제

Semaphore의 연산

• 초기화 연산
  • S 변수에 초기값을 부여하는 연산입니다.
  • S는 물건의 양으로, S가 있으면 그걸 들고 CS에 입장합니다.
• P() 연산, V() 연산
  • P는 자물쇠를 거는 연산입니다. (물건이 있는 경우에만 가능합니다)
  • V는 자물쇠를 푸는 연산입니다.
  • 단, CS에 들어갈 수 없으면 ready queue에서 대기하게 됩니다. (while 문으로 계속 실행되지 않습니다)
  • 자물쇠를 풀 땐 대기실에 존재하는 프로세스가 있으면 wakeup을 시킵니다.

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

• 상호배제 문제
• 프로세스 동기화 문제
• 생산자-소비자 문제
• Reader-writer 문제
• Dining philosopher problem

Mutual exclusion

Spinlock과 마찬가지로 CS에 들어가기전에 P(), V()를 해줌으로써 해결 가능합니다. 단, 대기할 때 계속해서 while을 실행하는 것이 아닌, Ready Queue에서 대기합니다.

Process synchronization

프로세스들의 실행 순서 맞추는 것을 세마포어로 가능합니다. 프로세스들은 병행적이며, 비동기적으로 수행합니다.

sync라는 세마포어 변수를 두고 Pj가 그 물건을 가지고 있다고 합시다. 그러면 Pi는 sync는 0이 되어 있기 때문에, ready queue에서 대기하게 됩니다. Pj가 수행을 완료하면 sync에 1을 반납하고, Pi를 wakeup합니다. 그러면 Pi는 다시 물건을 가지고 수행을 하게되면서 순서를 지킬 수 있습니다.

Producer-Consumer problem

• 생산자(Producer) 프로세스
  • 메시지를 생성하는 프로세스 그룹
• 소비자(Consumer) 프로세스
  • 메시지를 전달받는 프로세스 그룹

• 생산된 데이터가 쌓여있는 곳이 buffer입니다. 생산자가 물건을 놓는 동안에 consumer가 가져가면 문제가 될 수 있기 때문에 동기화가 필요합니다.

• 물건을 놓을 수 있는 buffer의 크기가 1이라고 합시다. 이렇게 되면 생산자가 물건을 놓는 동안엔 소비자가 가져갈 수 없고 소비자가 가져가는 동안엔 생산자가 물건을 놓을 수 없습니다.
  • 2 개의 세마포어 변수랑 buffer를 하나 뒀습니다.
  • 생산자가 물건을 놓으려 한다면 consumed가 1인지를 확인해야 합니다. 1이면 0으로 바꾸고 안에 들어가서 물건을 놓습니다. 수행이 끝나면 V를 통해서 produced를 다시 1로 바꾸게 됩니다.
  • 소비자가 물건을 가지고 가려 한다면 produced가 1인지를 확인합니다. 0이면 아직 생산이 안된 것이기 때문에 ready queue에서 대기하고 1이 되는 순간 wake up을 받아서 buffer에서 메시지를 가지고 갑니다.
• Buffer 크기가 N인 경우엔 원형 큐를 사용합니다.

• 저기 지워진 mutex만 유의 깊게 보면 나머진 혼자 buffer 일 때와 같습니다. 왜냐면 mutex는 생산자가 여러명이 있을 수 있기 때문에, 그 중 한 명만 실행되어야 합니다. 그래서 실행하는 부분입니다. 나머지는 buffer에 물건 수가 있는지 없는지를 확인합니다.

Reader-Writer problem

생산자 소비자 문제와 비슷하지만 다른 문제입니다.

• Reader
  • 데이터에 대해 읽기 연산만 수행합니다.
  • 동시에 데이터 접근이 가능합니다. 읽기만 하니까요.
• writer
  • 데이터에 대해 갱신 연산을 수행합니다.
  • writer는 한 사람만 필요합니다. 혹은 reader와 write가 동시 데이터 접근 시 상호배제(동기화)가 필요합니다.
• 해결법으론 reader / writer에 대한 우선권을 부여하는 것입니다.
  • reader preference solution (write는 쭈욱 기다립니다. reader가 읽는 동안)
  • writer preference solution (얘는 reader가 기다리겠죠)
• reader가 우선권을 가지는 솔루션
  • writer의 경우엔 쓸 때 자물쇠를 걸고 나올 땐 풀고 나옵니다.
  • reader 쪽에서는 P(), V() / P(), V() 식으로 구간을 나눌 수 있습니다. 처음 P(), V()는 읽으러 들어가기 전에 하는 작업입니다.  사전작업과 사후작업은 reader 중 한 명만 할 수 있습니다. 그래서 mutext로 묶어 놓았습니다. 처음에 reader의 수를 체크하고 0명이면 writer mutex를 P로 잠급니다. 왜냐면 이제 읽을거니까 만약, 1보다 크면 어떻게 크면 누군가 이미 했던 작업이니까 넘어갑니다. 여기까지가 사전 작업입니다.
  • 사후 작업에서 마지막에 나가는 친구는 writer에게 권한을 주고 나가야합니다.
  • , CS에 먼저 들어가는 애는 자물쇠를 잠그고, 나오는 애는 자물쇠를 풀고 나오면 됩니다.

 

Semaphore의 특징

• No busy waiting
  • 기다려야 하는 프로세스는 block 상태가 됩니다.
• 단, Semaphore queue에 대한 wake-up 순서는 비결정적입니다.
  • Starvation problem이 있습니다.
  • 상식적으론 들어온 순서대로 풀어주면 되겠죠.

---

Eventcount / Sequencer

• 세마포에서 busy waiting을 해결했지만, 깨울 때 무작위로 깨우다 보니 기아 문제가 발생할 수 있습니다.
• 은행의 번호표와 비슷한 개념입니다.
• Sequencer(번호 뽑는 기계라고 생각하면 됩니다)
  
  • 정수형 변수입니다.
  • 생성시 0으로 초기화, 감소하지 않습니다
  • 발생 사건들의 순서 유지가 됩니다.
  • ticket() 연산으로만 접근 가능합니다.
• ticket(S)
  • 현재까지 ticket() 연산이 호출 된 횟수를 반환합니다.
  • OS가 연산 중간에 선점이 되지 않도록 보장해줍니다.
• Eventcount
  • ticket을 부여받고 기다리고 있으면 은행원이 띵동~하고 부릅니다. 이 번호 부르는 것이 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) 혹은 CPU scheduler 호출합니다.
  • v는 자신이 든 번호표이고 E는 호출한 번호입니다. E가 V보다 작으면 계속 대기해야 합니다. (Queue에 Push 됩니다)

이 방법으로 많은 문제들을 어떻게 해결할 수 있을까요?

• Mutual exclusion
  • 우선 티켓을 뽑고 기다립니다. 자기 차례가 되면 CS에 입장하고 수행을 끝내면 advance(E)로 띵동~ 하고 눌러서 대기 순번을 올립니다.

• Producer-Consumer problem
  • 이 부분은 어려워서... 다들 화이팅 하셔서 공부해봅시다.

Eventcount / Sequencer의 특징

• No busy waiting
• No starvation
  • FIFO입니다.
• Semaphore 보다 더 low-level control이 가능합니다. (순서를 컨트롤 할 수 있기 때문입니다)

---

Language-Level Solution

지금까지 알아본 솔루션들은 모두 Low-level mechanisms입니다. Flexible 하지만 사용하기 어렵습니다. 그렇다면 저희가 쓰는 Language 수준에서 해결하면 어떨까요? 그게 바로 모니터입니다.

High-level Mechanism

• Language-level constructs
• Object-Oriented concept과 유사
• 사용이 쉽습니다.

Monitor

공유 데이터와 Critical Section의 집합입니다. 책방이 있는데 한 사람만 들어올 수 있는 경우라 생각하면 됩니다. Conditional variable이 존재합니다.

---

이상 프로세스 동기화 (Process Synchronization and Mutual Exclusive) 였습니다. ^_^