운영체제 6 - (Process Synchronization & Mutual Exclusion)

해당 정리는 youtube HPC Lab. KOREATECH의 OS 강의를 듣고 정리한 내용입니다.

강의 자료는 https://hpclab.tistory.com/1?category=887083 해당 링크에 있습니다.

목차

• 동기화(Synchronization)
  • 기계어 명령(Machine Instruction)의 특성
• 상호배체(Mutual exclusion)
  • ME Primitives version 1
  • ME Primitives version 2
  • ME Primitives version 3
• Mutual Exclusion Solutions
  • SW solutions
    • Dekker’s Algorithm
    • Peterson’s Algorithm
    • Dijkstra’s Algorithm
    • SW solution의 문제점
  • HW solution
    • TAS
    • HW solution 장단점
  • OS supported SW solution
    • Spinlock
    • Semaphore
    • Eventcout/Sequencer
  • Language-Level solution
    • Monitor

동기화(Synchronization)

현대 프로그래밍은 다중 프로그래밍으로 되어 있다.

이에 따른 문제가 발생하는데

여러 개의 프로세스들이 존재하고 각각의 프로세스들은 서로 독립적으로 동작을 한다.(즉 동시에 동작한다는 의미)

각각의 프로세스들의 공유데이터를 동시에 사용하려고 할 때 문제가 발생할 수 있다.

 

위와 같은 문제를 해결하기 위해 나온 개념이 동기화(Synchronization)라고 볼 수 있다.

동기화란 대화라고 의미하면 된다. 즉, 동작을 맞추고 서로 정보 공유를 하는 것을 의미한다.

 

다시 한번 정리하면 병행 수행 중인 비 동기적 프로세스들이 공유 자원에 동시 접근할 때 문제가 발생할 수 있고 이에 따른 해결하는 방법이 동기화(Synchronization)이다.

 

앞으로 쓰이게 될 용어부터 정리해 보자

• Shared Data(공유 데이터) : 여러 프로세스들이 공유하는 데이터
• Critical Section(임계 영역)(CS) : 공유 데이터를 접근하는 코드 영역
• Mutual exclusion(상호 배제) : 둘 이상의 프로세스가 동시에 Critical section에 진입하는 것을 막는 것

Critical section에 대한 예를 한번 위 그림을 통해 봐 보자

현재 공유 데이터인 sdata는 0이 들어가 있는 상태이다.

만약 Pi와 Pj가 연산을 하게 되면 sdata는 2가 될까?

해당 답을 알기 전에 알아야 할 개념에 대해서 한번 알아보고 sdata가 2가 되는지 확인해 보자

기계어 명령(Machine Instruction)의 특성

Atomicity(원자성), Indivisible(분리불가능)이 있다. 즉, 한 기계어 명령의 실행 도중에 인터럽트를 받지 않는다는 것을 의미한다.

그러면 위의 식을 기계어로 다시 한번 봐보자

 

1,2,3, A, B, C 동작 중에는 Machine Instruction의 특성으로 인해 실행 도중에 인터럽트 영향을 받지 않는다. 그러나 각각의 명령어 사이에는 인터럽트가 발생할 수 있다.(즉 preemption이 발생할 수 있다.)

만약 1 → 2 → 3 → A → B → C와 같은 순서로 처리가 되었으면 sdata는 2가 된다. 그러나 1 → 2 이후에 preemption이 발생되고 A →B → C → 3 처리를 하게 되면 sdata는 1이 된다.

 

즉 실행순서에 따라 결과가 달라지는데 이를 Race condition이라고 한다.

Race condition을 막고, 원하는 결과를 도출해 내기 위한 방법이 Mutual Exclusion(상호배제)라고 한다.

상호배제(Mutual Exclusion)

Mutual Exclusion에는 기본이 되는 2가지 primitives 가 존재하는데 enterCS(), exitCS()이다.(CS = Critical Section)

즉, enterCS()는 Critical Section 전 다른 프로세스가 있는지 확인하는 연산이고, exitCS()는 Critical Section을 벗어났을 때 시스템에게 알리는 연산을 의미한다.

Mutual Exclusion primitives의 요구를 만족하기 위해서는 3가지가 만족을 해야 한다.

• Mutual exclusion(상호배제) : CS에 프로세스가 있으면 다른 프로세스의 진입 금지
• progress(진행) : CS 안에 있는 프로세스 외에는 다른 프로세스가 CS에 진입하는 것을 방해하면 안 됨(안에 아무도 없으면 CS안으로 들어갈 수 있어야 한다)
• Bounded Waiting(한정대기) : 프로세스의 cs 진입은 유한시간 내 허용해야 한다. 즉, 계속 기다리면 안 된다.

지금부터 여러 가지 Mutural Exclusion을 지키려 했던 방법들에 대해서 알아보자.

ME Primitives version 1

위 방식은 turn이라는 변수를 통해서 각각의 프로세스가 본인 턴일 때 CS에 들어가고 나간 이후에 상대방 turn으로 넘겨주는 방식이다.

위 방식대로 할 경우 위 3가지 조건을 만족할까? → Progress 조건에 위배된다.

왜냐면 만약 P0 프로스가 CS 진입 전에 죽게 되면 어떻게 될까? P1은 턴을 계속 비울 수 없는 상태이고 이것은 Progress를 위배하게 된다.

ME Primitives version 2

위 방식은 각각의 프로세스들의 flag를 이용해서 CS에 들어갔는지 표시하는 방법이다(깃발 올리기라고 이해하면 된다) 위 방식대로 할 경우 위 3가지 조건을 만족할까? → Mutual Exclusion이 위배된다.

왜 나면 위 그림처럼 해당 부분에 Preemption이 발생했다고 치자 그럼 P0의 깃발이 올리기 전에 멈춘다는 의미고 이때 P1이 작동하게 되면 P1은 P0의 깃발이 올라와 있지 않는 것을 보고 CS에 들어가게 된다. 이후 P0가 다시 실행될 경우 CS에 P0 P1 두 개가 같이 존재하게 되는 상황이 발생한다.

ME Primitives version 3

위 방식은 version 2에서 순서만 바꾼 방법이다. 들어가기 전에 들어가는지 먼저 의사를 밝힌 후 CS에 들어가는 방법이다. 위 방식대로 할 경우 3가지 조건을 만족할까? → Bounded Waiting 조건에 위배된다.

왜냐면 위 그림처럼 해당 부분에 Preemption이 발생했다고 치자. 그럼 P0 같은 경우 알리고 난 후 멈추게 된다. 이후 P1이 동작을 하게 되면 flag0의 깃발이 세워져 있으므로, CS에 들어갈 수 없고 이후 P0 역시 들어갈 수 없는 상태가 된다. 즉 CS에 어떠한 프로세스도 접근하지 못한다.

 

위 3가지 방식 결국 각각의 조건에 위배된다. 앞으로는 Mutual Exclusion을 준수하는 방법들에 대해 알아볼 것이다.

Mutual Exclusion Solutions

Mutual Exclusion을 지원하는 여러 가지 방법이 있다.

• 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, HW, OS solution 경우 Low-Level mechanism이라고 불리고 Language-Level solution 같은 경우 High-Level mechanism이라고 불린다.

SW solutions

지금부터는 소프트웨어에서 Mutual Exclusion 문제를 해결하는 방법에 대해서 알아볼 것이다.

Dekker’s Algorithm

Two process ME를 보장하는 최초의 알고리즘이다.

앞에서 했던 flag와 turn을 이용해서 문제를 해결하는 방법이다.

방식은 위 슈도코드를 참고하면 된다.

위 방식에서 간단하게 구현된 것이 Peterson’s Algorithm이다.

Peterson’s Algorithm

이 방식은 쉽게 말해서 깃발을 올려서 의사 표시를 한 후 다른 프로세스에게 양보를 한다. 즉 늦게 양보한 사람이 늦게 들어가는 방식이다.

현재까지 2가지 프로세스가 존재했을 때 Mutural Exclusion을 해결하기 위한 방법이다. 다음으로는 N개의 프로세스가 있을 때 해결하는 방법에 대해서 알아보자

N개의 프로세스에서 Mutural Exclusion을 해결하는 방법은 4가지가 있다. Dijkstra, Knuth, lamport, brinch Hansen 4가지 방법이 존재하는데 이번에는 Dijkstra 방식에 대해서만 알아보자

Dijkstra’s Algorithm

Dijkstra 알고리즘 같은 경우 프로세스 개수와 같은 Flag를 사용하는데 Flag에 들어갈 변수로는 위에서와 같이 단순히 들어갈 의사표시가 아닌 3가지 변수(idle, want-in, in-CS) 3가지가 있다.

• idle : 프로세스가 임계 지역 진입을 시도하고 있지 않을 때 (깃발 x)
• want-in : 프로세스의 임계 지역 진입 시도 1단계일 때 (처음 의사를 밝히는 단계)
• in-CS : 프로세스의 임계 지역 진입 시도 2단계 및 임계 지역 내에 있을 때 (진입 직전)

SW solution의 문제점

위 방식들은 여러 문제가 발생한다.

1. 속도가 느리다.
2. 구현이 복잡하다.
3. ME primitive 실행 중에 Preemption이 될 수 있다. → overhead 발생
4. Busy waiting이 발생한다. (무한반복문을 통해서 기다리는데 효율적이지 않다)

SW solutions의 문제점을 해결하기 위해 HW가 도와주는데 HW solution에 대해서 알아보자.

HW solution

하드웨어에서는 TAS(TestAndSet) insdtruction 을 통해 Mutual exclusion 문제를 도와줄 수 있다.

TAS

Test와 Set을 한 번에 수행하는 기계어이다. 즉 Test와 Set을 함께 수행하는데 이때 기계어이기 때문에 원자성을 준수하게 되고 이는 곧 중간에 Preemption이 되지 않는다.

 

TAS를 통해 Preemption이 발생하지 않는 것을 보장해 주기 때문에 간편하게 Mutual exclusion 문제를 해결할 수 있다. 그러나 위 코드대로 진행할 경우 프로세스가 3개 이상일 경우 Bounded waiting 조건을 위배할 수 있다. 그 이유는 P1 ~ P3가 있다고 쳤을 때, P1이 CS에 돌아가고 나올 동안 P2, P3가 while문에서 대기를 한다. 그 후 P1이 나왔을 때 P3가 들어갈 수 있고 P3가 CS에 들어갈 동안 또 다른 프로세스 P4가 오고 P3가 나올 때 P4가 CS로 들어올 수 있기 때문이다.

 

즉 N개 프로세스일 때 Mutual exclusion문제를 해결하기 위해 위 코드를 좀 더 복잡하게 작성을 해야 한다.

위 코드는 N개의 프로세스일 때, TAS 코드를 의미한다.

HW solution 장단점

위 방식의 장점으로는 SW solution 보다 구현이 훨씬 간단하다는 장점이 있다. (TAS를 쓰기만 하면 되니까) 그러다 단점으로는 Busy waiting 문제를 해결하지 못했다.

OS supported SW solution

os 차원에서 Mutual exclusion을 지원하는 방법은 Spinlock, Semaphore, Evencount/sequencer 가 존재한다.

Spinlock

쉽게 말해서 정수형 변수이다. 그러나 단순 변수가 아니라 조금은 특별한데 초기화, P(), V()로만 접근이 가능한 변수이다.

OS는 P(), V() 연산할 때 Machine Instruction을 보장해 준다. 즉, Preemption이 일어나지 않게 보장을 해준다.

P() 연산은 쉽게 말해서 물건을 꺼내는 것, 자물쇠를 거는 것을 의미하고 V() 연산은 물건을 집어넣는 것, 자물쇠를 푸는 것이라고 생각하면 된다.

위 그림에서 active의 변수는 Spinlock의 변수이다. active가 1일 경우 Critical Section에서 동작하는 프로세스가 없는 것이고 active가 0일 경우 Critical Section에서 동작하는 프로세스가 있는 것을 의미한다.

위 방식의 Spinlock의 한계점으로는 첫 번째로 Busy waiting이 여전히 해결되지 않은 것이다. 또한 Spinlock은 멀티 프로세서에서만 가능하고 단일 프로세서에서는 의도대로 동작하지 않는다는 한계점을 가진다.

왜 단일 프로세서에서는 동작하지 않을까? → 만약 Pi가 Critical Section에서 동작을 하다가 멈췄다고 생각을 해보자. Pi는 멈췄기 때문에 밖으로 나가지게 되고 CPU 자리가 비어있기 때문에 Pj가 들어가게 된다. 이때 OS에서는 P() 연산에서 멈추지 않는 것을 보장해 줬기 때문에 CPU 내에서 Pj가 계속해서 동작을 하게 되고 Pi는 들어갈 수 없는 현상이 발생한다. 즉 둘 다 일을 못하는 상황이 발생하게 된다.

Semaphore

쉽게 말해서 차단기라고 생각을 하면 된다.

Semaphore의 가장 큰 특징으로는 여태까지 해결할 수 없었던 Busy Waiting 문제를 해결했다.(그래서 많은 운영체제에서 Semaphore를 사용한다)

Semaphore는 Spinlock과 유사하게 초기화 연산, P(), V() 연산으로만 접근이 가능하고 음이 아닌 정수형 변수이다.

Spinlock과 가장 큰 차이점은 임의의 S 변수 하나에 Ready Queue 하나가 할당된다.

 

Semaphore는 Binary Semaphore과 Counting Semaphore로 구분된다.

• Binary semaphore : 0과 1만 가지는 경우이다. 프로세스 Synchronization과 Mutual Exclusion 목적으로 사용된다.
• Counting semaphore : s가 0 이상의 정수값을 가지는 경우이다. Producer-Consumer 문제 등을 해결하기 위해 사용된다.

Spinlock과 차이점은 Spinlock 같은 경우 P() 연산에서 Critical Section에서 대기할 경우 반복문을 통해 대기를 하게 되는데 Semaphore는 Queue에서 대기한다.

 

Semaphore로 해결가능한 동기화

• Mutual exclusion
• process synchronization problem
• producer-consumer problem
• Reader-Writer
• Dining philosopher problem

Semaphore의 장점으로는 여태까지 Busy Waiting문제로 해결할 수 없었으나, Semaphore에서는 이 문제를 해결했다.

그러나 단점으로는 Queue에서 wake-up 하는 순서가 비 결정적이기 때문에 이는 Stavation problem 현상이 발생할 수 있다.

Eventcount/Sequencer

위 방식은 Semaphore의 단점인 Queue에서 기다리는 프로세스를 wake-up 하는 순서를 먼저 들어온 프로세스부터 깨우기 위해 생겨난 방법이다.

현실로 비유를 하자면 은행의 번호표를 뽑는 것과 비슷한 개념이다.

 

Sequencer

(은행으로 따지면 번호를 뽑는 기계를 의미한다.)

정수형 변수이고 생성 시 0으로 초기화되며, 감소하지 않는다.

발생 사건들의 순서를 유지하고 ticket() 연산으로만 접근이 가능하다

 

ticket(S)

guswoRkwl ticket() 연산이 호출된 횟수를 반환한다.

 

Eventcout

(은행으로 따지면 은행원이 누르는 번호를 의미한다)

정수형 변수로 생성 시 0으로 초기화하고 이후 감소하지 않는다.

특정 발생 횟수를 기록하며, read(E), advance(E), await(E, v) 연산으로 접근 가능하다

 

read(E)

현재 Eventcount 값 반환

 

advance(E)

(은행원이 누루는 행위)

Eventcount를 기다리고 있는 프로세스를 깨우는 행위

 

await(E, v)

if(E < v)이면 E에 연결된 Q에 프로세스 전달 및 CPU scheduler 호출

즉, 본인번호까지 기다리는 것을 말한다.

Eventcount/Sequencer의 장점으로는 Busy Waiting이 없다는 것, No starvation이 없다는 것이다.

Semaphore 보다 더 Low-Level control이 가능하다.

Language-Level solution

여태까지 High-Level mechanisms에 대해서 알아봤다. SW, HW, OS 3개 모두 복잡하고 사용하기에 어렵다.

Language-Level solution은 앞서 배웠던 것보다 복잡한 것이 줄어들고 실용성 있는 방식이다.

 

해당 방식에는 Monitor, Path expressions, Serializers, Critical region, conditional critical region 이 있는데 Monitor에 대해서 알아보자.

Monitor

Monitor는 공유데이터와 Critical Section의 집합이다.

 

Monitor 구조

• Entry Queue(진입 큐) : 모니터 내 procedure 수만큼 존재
• Mutual Exclusion : 모니터 내에는 항상 하나의 프로세스만 진입 가능(Language에서 보장)
• Information hiding(정보 은폐) : 공유 데이터는 모니터 내의 프로세스만 접근 가능
• Condition Queue(조건 큐) : 모니터 내의 특정 이벤트를 기다리는 프로세스 대기하는 곳
• Signaler Queue(신호제공자 큐) : 하나의 신호제공자 큐가 존재해서 signal() 명령을 실행한 프로세스가 임시 대기

Monitor의 장점으로는 사용이 쉽고 error 발생 가능성이 낮다. 단점으로는 지원하는 언어에서만 사용이 가능하며 컴파일러가 OS를 이해하고 있어야 한다.