[OS] 정리5

프로세스 동기화

공유 메모리에 동시 접근하면 문제가 생긴다.

다음 코드를 보자.

counter++과  counter--의 구현이 다음과 같을 것이다

counter++

register1 = counter

register1 = register1 + 1

counter = register1

counter--

register2 = counter

register2 = register1 - 1

counter = register2

이제 다음과 같은 순서로 실행이 된다고 생각해 보자.

counter는 5로 시작한다.

결과는 counter가 5여야 하지만, 각각 4, 6이 된다.

Race Condition

- 여러 프로세스가 공유 데이터를 동시에 엑세스하고 조작하는 상황. 공유 데이터의 최종적인 값이 마지막으로 완료되는 프로세스에 의해 결정되는 상황.

- 이 때, 프로세스 동기화가 필요하다.

- 위에서 살펴본 ++, --연산은 Atomic하게 수행되어야 한다.

Atomic Operation : 프로세스가 수행 중에 중단되지 않고 완료되는 동작

Critical Section

- N개의 프로세스들이 공유 데이터를 사용하기 위해 경쟁하는 상황을 해결하기 위한 동기화 방법

- 각 프로세스는 공유 데이터에 엑세스하게 해 주는 Critical Section이라는 코드를 가진다.

- 한 프로세스가 Critical Section에서 실행 중일 때, 해당 코드를 다른 프로세스가 실행하는 것을 허용하지 않는 방식.

Critical Section의 구현 방법

- 동기화 하드웨어 사용

- TestAndSet 명령

- Swap 명령

- Semaphore 사용

- High-Level 동기화 구성을 이용

- Monitor

크리티컬 섹션의 속성

- Mutual Exclusion(상호 배제) : 프로세스 Pi가 어떤 크리티컬 섹션 안에서 실행중일 때, 다른 프로세스들이 해당 크리티컬 섹션에서 실행될 수 없다.

- Progress(진행) : 크리티컬 섹션에 진입한 프로세스가 없는 상태에서, 진입하려는 프로세스가 여러 개 있다면 어느 것이 들어갈지를 결정해 준다.

- Bounded Waiting(한정 대기) : Thread의 Starvation상태를 막기 위해 크리티컬 섹션에 대한 접근 대기 시간은 한정되어야 한다.

크리티컬 섹션 구현 알고리즘

기본적으로 다음과 같은 구조를 가진다.

Entry / Exit을 통해 크리티컬 섹션에 진입하고 나올수 있다.

알고리즘 1.

프로세스가 위 코드에 접근했을 때, turn이 i가 아니면 대기하고, i가 되면 크리티컬 섹션에 진입할 수 있다. 

처리가 끝나면 turn을 j로 바꾸면서 나온다. 

이렇게 한 번에 하나의 Thread만 접근하게 되어 Mutual exclusion은 성립하지만, 다음과 같은 상태일 때 문제가 발생한다.

1. turn이 i이고, Thread i가 크리티컬 섹션을 제외한 나머지 코드를 실행중

2. Thread j가 크리티컬 섹션에 들어가려고 한다면 turn이 여전히 i이기 때문에 크리티컬 섹션에 접근 불가

그래서 Progress가 성립되지 않는다.

알고리즘 2.

이러면 한 상황에 한 스레드만 접근이 되지만,

1. flag[0] = true

2. 컨텍스트 스위칭 0 to 1

3. falg[1] = true

이 순서가 되면 둘다 수행이 되지 않는다.

피터슨 알고리즘

위에서 살펴 본 1, 2 알고리즘을 결합

- flag : 크리티컬 섹션 진입 의사를 설정. 일단 상대방이 크리티컬 섹션 진입 의사가 없다면 현재 프로세스를 크리티컬 섹션에 진입시킴

- turn : race condition에 의해, turn 설정하는 코드가 늦게 수행된 프로세스가 상대방에게 기회를 양보하도록 함.

많은 시스템에서는 하드웨어에서 크리티컬 섹션에 대한 동기화를 지원한다.

- Uni-Processors : 인터럽드를 비활성화할 수 있음

- 현재 실행되는 코드가 선점 없이 실행될 수 있다.

- 멀티 프로세서 시스템에서 비효율적

- 현재 대부분은 Atomic 하드웨어 명령을 제공한다(Atomin = Non interruptable).

- TestAndSet

- CompareAndSwap

TestAndSet를 이용한 크리티컬 섹션 구현

이렇게 구현하면, TestAndSet이 Atomic 연산이므로, 이미 크리티컬 섹션에 진입한 프로세스가 존재하게 되면 해당 프로세스를 제외한 다른 프로세스들은 while에서 대기하게 된다.

CompareAndSwap

void CompareAndSwap(int *value, int expected, int new_value)

{

int temp = *value;

if (*value == expected)

*value = new_value;

return temp;

}

do {

while (CompareAndSwap(&lock, 0, 1) != 0); // 이미 다른 프로세스가 lock을 가지고 있다면 대기

/* Critical Section */

lock = 0; // lock 해제

} while(true)

이렇게 하면 CompareAndSwap이 Atomic 연산이므로 lock 가지는 프로세스는 언제나 하나뿐이게 된다.

Semaphores : busy waiting을 피하는 동기화 방법. 커널 오브젝트를 생성해서 커널에서 관리되도록 구현.

- wait(), signal()로 진입, 진입해제를 함

세마포어 및 wait(), signal()의 대략적인 구현

- 실제 구현은 하드웨어 동기화 혹은 Interrupt Disable/Enable을 통해 함수 내에서는 컨텍스트 스위칭을 방지하는 방법으로 진행할 수 있다.

block()을 하게되면 현재 프로세스를 wait_queue에 넣는다.

wakeup()을 하게 되면 현재 프로세스를 ready_queue에 넣는다.

세마포어의 사용 방식은 2가지 존재.

- Counting : 정수값 제한 없음. 동시에 진행 가능한 프로세스(혹은 스레드)의 수를 설정할 수 있음.

- Binary(Mutex) : 0, 1 두개의 값만 존재. 바이너리 세마포어를 뮤텍스라고 함. 

- 뮤텍스를 사용하게 되면 이는 곧 임계구역에 한 번에 한 프로세스(혹은 스레드)만 접근할 수 있게 되는 것을 의미한다.

busy waiting : 프로세스나 스레드가 lock을 획득하기 위한 동기화 상황에서 일반적으로 반복문을 통해 구현되는데, lock을 얻기 위해 이런 식으로 CPU를 낭비하는 것은 비효율적이다. 

Spin lock : busy waiting 개념을 이용하여 구현되며, 컨텍스트 스위칭 비용보다 busy waiting으로 대기하는 시간이 더 부하가 적다고 생각될 때 사용됨.

DeadLock

- 2개 이상의 프로세스가 대기 상태의 프로세스 중 하나에서만 발생할 수 있는 Event를 영원히 대기하는 상황

Starvation

- 무한하게 Block 상태로 남는 것. 세마포어의 Block상태 프로세스 리스트에서 프로세스를 영원히 제거하지 못하는 상황

동기화 문제 해결 (당연한 사실이다)

- Bounded-Buffer Problem : 생산자-소비자 개념이 등장. 동기화를 사용하지 않을 경우, 생산자는 버퍼에 데이터를 넣고, 소비자는 버퍼의 데이터를 가져온다. 이 때, 저장할 공간이 없는 문제, 가져올 데이터가 없는 문제가 발생.

- 데이터가 버퍼에 꽉 채워져 있는지, 데이터가 하나도 없는지 등을 세마포어로 설정

Readers-Writers Problem

- 여러 명의 독자 및 저자들이 있고, 하나의 저장 공간을 공유하며 이를 접근할 때 발생하는 문제.

1. 여러 명의 독자가 동시에 데이터를 읽는 것이 가능

2. 한 저자가 공유 공간에 데이터를 쓰고 있는 동안에는 그 저자만 접근이 가능.

* 독자가 한 명이라도 읽고 있는 중에는 저자가 데이터를 쓸 수 없음

세마포어로 다음과 같이 구현 가능하다(출처 : 위키백과)

• 변수
  • readcount : 현재 버퍼에 접근 중인 독자의 수를 나타낸다. (초기값=0)
  • wrt : 저자들 사이의 관계를 통제한다. 즉, 동기화한다. (초기값=1)
  • mutex : readcount와 wrt에 접근하는 것이 원자적으로 수행될 수 있도록 하는 세마포어 (초기값=1)
• 저자 프로세스

wait(wrt);    // 임계구역에 들어가기 위해 허가가 나기를 기다린다.
...
쓰기 작업 수행
...
signal(wrt);  // 임계구역에서 빠져나왔음을 알린다.

• 독자 프로세스

wait(mutex);
    readcount++;     // 독자 수 1 증가
    if readcount = 1
        wait(wrt);   // 쓰고 있는 저자가 없을 때까지 기다린다.
signal(mutex);
...
읽기 작업 수행
...
wait(mutex);
    readcount--;     // 독자 수 1 감소
    if readcount = 0
        signal(wrt); // 독자가 없다면 이를 알린다. 

signal(mutex);

Dining-Philosophers(식사하는 철학자) Problem

- Dead Lock(교착 상태)을 설명하기 위한 내용이다.

- N명의 철학자가 원탁에 앉아서 식사를 한다. 철학자들 사이에는 포크가 하나씩 놓여 있고, 다음의 규칙을 순서대로 수행하며 식사를 한다.

1. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 사용 가능해지면 집는다.

2. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 사용 가능해지면 집는다.

3. 양쪽의 포크를 집으면 정해진 시간(CPU Time Slice)만큼 식사를 한다.

4. 오른쪽 포크를 내려놓는다.

5. 왼쪽 포크를 내려놓는다.

6. 1번을 수행한다.

- 만일 모든 철학자가 동시에 자신의 왼쪽 포크를 잡는다면 모든 철학자들이 자신의 오른쪽 포크를 영원이 기다려야 한다.

이를 Deadlock이라고 하는데, Deadlock이 일어나는 필요 조건 중 하나를 깨버리면 된다.

필요조건은 다음과 같다.

1. Mutual Exclusion(상호 배제) : 프로세스들이 공유 자원을 동시에 쓸 수 없는 상황

2. Hold and Wait(보유 및 대기) : 공유 자원을 점유한 상태에서 다른 자원을 기다리는 상황. 점유한 자원을 또다른 프로세스가 대기하게 되고, 최악의 경우 Circular Wait(순환성 대기) 상황에 빠진다.

3. No Preemption(선점 불가) : 프로세스들이 서로 공유 자원을 뺏을 수 없다.

Monitor

- 동기화 기법 중 하나. 어떤 공유 데이터에 모니터를 지정해 놓으면, 프로세스는 그 데이터에 접근하기 위해 모니터에 진입해야 한다. 그리고 모니터 내부에 들어간 프로세스에게만 공유 데이터를 접근할 수 있는 기능을 제공한다.

- 이미 모니터에 프로세스가 존재하면 대기 큐가 존재해서 해당 대기 큐에서 대기한다.

뮤텍스와의 차이 : 뮤텍스는 프로세스 간의 동기화가 가능하고, 모니터는 한 번에 한 프로세스만 진입 가능하므로 스레드 간의 동기화라고 할 수 있다.

Java에서는 synchronized라는 명령어로 이를 제공한다.