운영체제(Operating System) 5강

 in Computer Science / Operating-system
운영체제(Operating System) 5강

반효경 교수님 - Process Synchronization


Lecture


임계구역(Critical section)

  • n 개의 프로세스가 공유 자원을 동시에 사용하기를 원하는 경우, 공유 자원에 접근하려 하는 코드 블럭을 의미
  • A프로세스에서 공유자원 c의 값을 1만큼 증가시키고, B프로세스에서는 동시에 c의 값을 1만큼 감소시킨다면 어떤 현상이 발생하는가?
  • 이러한 경우 발생할 수 있는 문제들을 해결하기 위해 동기화(synchronization)가 필요하다


프로그램적 해결법의 충족 조건

Mutual Exclusion (상호 배제)

  • 프로세스가 임계구역 부분을 수행 중이면 다른 모든 프로세스들은 그들의 임계구역에 들어갈 수 없다

Progress (진행)

  • 아무 프로세스도 임계구역에 있지 않는 상태에서 임계구역에 들어가고자 하는 프로세스가 생긴다면 즉시 임계구역에 들어가게 해줘야한다

Bounded Waiting (유한 대기)

  • 프로세스가 임계구역에 들어가려고 요청한 후 부터 그 요청이 허용될 때까지 다른 프로세스들이 임계구역에 들어가는 횟수에 한계가 있어야 한다


문제 해결 알고리즘

다음과 같이 가정한다.

  • 모든 프로세스의 수행 속도는 0보다 크다
  • 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다


Algorithm 1


do {
    while (turn != 0)
    critical section
    turn = 1;
    remainder section
} while (1);


turn이라는 변수를 가지고 자기 차례에만 임계구역에 들어가게 강제한다.


상호배제를 만족하지만, 프로세스 간의 임계구역에 들어가야하는 횟수가 다르다면 문제가 생길 수 있다.

  • 프로세스 1은 임계구역에 한 번만 들어가도 되고, 프로세스 2는 임계구역에 여러 번 들어가야 되는 상황이다
  • 코드가 한 번 작동한 이후, 프로세스 1이 더이상 들어갈 일이 없게 되기 때문에 프로세스 2에게는 자신의 차례가 돌아오지 않게 되버린다
  • 즉, Progress(진행) 조건을 만족하지 못한다


Algorithm 2


do {
    flag[i] = true;
    while(flag[j]);
    critical section
    flag[i] = false;
    remainder section
} while(1);


flag라는 boolean 변수를 가지고 임계구역에 들어갈 상태를 표현한다.

  • 다른 프로세스의 flag를 체크하고, 프로세스의 flag가 true라면 양보, false라면 자신이 들어간다

이 또한 상호배제는 만족하므로 얼핏 보기에는 문제가 없어 보이지만, 선점 문제가 발생 할 수있다.

  • 프로세스 1이 임계구역에 들어가기 위해 flag를 true로 만들어 둔 상태에서 CPU를 뺏기게 된다
  • 프로세스 2도 임계구역에 들어가기 위해 flag를 true로 만들고 들어가려하는데, 다른 프로세스의 flag가 이미 true이기에 양보를 하게된다
  • 프로세스 1에게 다시 CPU가 넘어와 임계구역에 들어가려하는데, 다른 프로세스의 flag가 true이므로 프로세스1도 마찬가지로 양보를 하게되버린다
  • 즉, 서로 무한정으로 양보하는 상황이 발생한다 (데드락)


Algorithm 3(Peterson`s Algorithm)


do {
    flag[i]= true;
    turm = j;
    while(flag[j] && turn == j);
    critical section
    flag[i] = false;
    remainder section
} while(1);


flag 변수와 turn 변수를 둘 다 사용하는 방법으로, 프로그램적 해결법의 충족 조건을 모두 만족하게 된다.

하지만 Busy Waiting(Spin Lock)문제가 발생한다.

Busy Waiting은 계속 CPU와 Memory를 사용하며 wait하고 있는 상태를 의미하며, 코드상으로 while문을 계속해서 돌고있는 상태이다.


Synchronization Hardware

하드웨어적으로 Test & modify를 atomic 하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결 가능하다.

  • lock을 걸고 푸는 작업을 하나의 명령어(논리)로 처리하기 때문에, 문제를 손 쉽게 해결 할 수 있다.


Synchronization variable;
    boolean lock = false;

do {
    while(Test_and_Set(losk));
    critical section
    lock = false;
    remainder section
}


Semaphores

  • 앞의 방식들을 추상화 시킨 것
  • 앞서 보았던 잠금을 걸고, 푸는 작업을 대신 해준다. (공유 자원을 획득하고, 다시 반납하는 작업)


P(S) - 잠금을 거는 연산


while (S<=0) do no-op;
S--;


V(S) - 잠금을 푸는 연산


S++;


Semaphores Examples

Synchronization variable:
semaphore mutex; // 1로 초기화

do{
	P(mutex);
	/* critical section */
	V(mutex); 
} whlile (1);


프로그래머는 위처럼 세마포어를 이용해서 더 간단하게 프로그램을 작성할 수 있다.


Block & Wakeup (Sleep Lock) 방식의 구현을 이용한다.

  • 임계구역의 길이가 긴 경우 적당하다.

Busy-wait (Spin Lock)

  • 임계구역의 길이가 매우 짧은 경우 오버헤드가 비교적 더 작다.
  • 그렇기 때문에 일반적으로 Block & Wakeup 방식이 더 효율적으로 사용할 수 있다.

Block & Wakeup Implementation

세마포어는 다음과 같이 정의 할 수있다.


typedef struct
{
	int value; // 세마포어 변수
	struct process *L; // 세마포어를 사용하기 위한 대기 큐
}semaphore;


image


  • block()
    • 커널은 block을 호출한 프로세스를 suspend하고, 이 프로세스의 PCB를 세마포어의 대기큐에 넣는다
  • wakeup(P)
    • block된 프로세스를 wake up하고, 이 프로세스의 PCB를 레디큐에 넣는다


세마포어 연산은 다음과 같이 정의 및 구현한다

P(S):

세마포어 변수 S를 무조건 1 줄이고, 그 변수의 값이 음수면 해당 프로세스를 대기큐로 보낸 후 Block 상태로 만든다.


// P(S)
S.value--;
if (S.value < 0)
{
    add this process to S.L;
    block();
}


V(S):

세마포어 변수 S를 무조건 1 늘리고, 그 변수의 값이 0보다 작거나 같으면 이미 기다리고 있는 프로세스가 있으므로 프로세스를 대기큐에서 꺼내 레디큐로 보낸다. 세마포어 변수 S 값이 양수면 아무나 임계 구역에 들어 갈 수 있으므로 별다른 추가 연산을 하지 않는다. V 연산은 특정 프로세스가 공유 데이터를 반납한 후 임계 구역에서 나가는 연산이다.


// V(S)
S.value++;
if (S.value <= 0)
{
    remove a process P from S.L;
    wakeup(P);
}


  • block()
    • 커널은 block을 호출한 프로세스를 대기 시킨다.
    • 이 프로세스의 PCB를 세마포어를 위한 대기 큐에 넣는다.
  • wakeup(P)
    • block 된 프로세스 P를 wakeup 시킨다.
    • 이 프로세스의 PCB를 준비 큐로 옮긴다.


Type of Semaphore

  • Counting Semaphore
    • 도메인이 0이상인 임의의 정수값
    • 여러 개의 공유 자원을 상호 배제
    • 주로 resource counting에 사용

-Binary Semaphore

  • 0 또는 1값만 가질 수 있는 세마포어
  • 한 개의 공유 자원을 상호 배제
  • mutex와 유사하나 완전히 같지는 않다


Deadlock & Starvation

Deadlock

둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상으로, 예시는 다음과 같다.


S와 Q가 1로 초기화된 세마포어라 하자.

image


P0이 CPU를 얻어 P(S) 연산까지 수행하여 S 자원을 얻었다고 가정 한다. 이 때, P0의 CPU 점유 시간이 끝나 Context Switch가 발생하고 P1에게 CPU 제어권이 넘어갔다.

P1은 P(Q) 연산을 수행하여 Q 자원을 얻었으나 또 다시 CPU 점유 시간이 끝나 Context Switch가 발생하여 P0에게 CPU 제어권이 넘어갔다.

P0은 P(Q) 연산을 통해 Q 자원을 얻고 싶지만, 이미 Q 자원은 P1이 갖고 있는 상태이므로 Q 자원을 가져올 수가 없다.

마찬가지로 P1도 P(S) 연산을 통해 S 자원을 얻고 싶지만, 이미 S 자원은 P0이 갖고 있는 상태이므로 S 자원을 가져올 수 없다.

이렇게 P0와 P1은 영원히 서로의 자원을 가져올 수 없고, 이러한 상황을 Deadlock이라고 한다.


이러한 현상을 해결하는 방법 중 하나로, 자원의 획득 순서를 정해주어 해결하는 방법이 있다.

S를 획득해야만 Q를 획득할 수 있게끔 순서를 정해주면 프로세스 A가 S를 획득했을 때 프로세스 B가 Q를 획득할 일이 없다.


Starvation

indefinite blocking(무기한적인 차단)으로, 프로세스가 자원을 얻지 못하고 무한히 기다리는 현상을 의미한다.


Deadlock vs Starvation

언뜻 보기에 둘 다 자원을 가져오지 못하고 무한히 기다리니까 같은 단어라고 혼동할 수 있다.

Deadlock은 P0 프로세스가 A 자원을 보유하고 있고, P1 프로세스가 B 자원을 보유하고 있을 때 서로의 자원을 요구하여 무한히 기다리는 현상이다.

반면 Starvation은 프로세스가 자원 자체를 얻지 못하고 무한히 기다리는 현상이다. SJF 알고리즘을 생각하면 이해가 쉬울 수 있다.


Producer-Consumer Problem

image


  • 주황색: Full buffer
  • 회색: Empty buffer


  • Producer
    • empty buffer가 있는지 확인하고 없다면 기다린다
    • 공유 데이터에 lock을 건다
    • empty buffer에 데이터를 입력한다
    • lock을 푼다
    • full buffer가 하나 증가한다


  • Consumer
    • full buffer가 있는지 확인하고 없다면 기다린다
    • 공유 데이터에 lock을 건다
    • full buffer에서 데이터를 꺼낸다
    • lock을 푼다
    • empty buffer가 하나 증가한다


Synchronization Problem

  • 공유 버퍼이기 때문에 여러 생산자가 동시에 한 버퍼에 데이터를 입력 할 수 있다
  • 마찬가지로 여러 생산자가 동시에 한 버퍼의 데이터를 꺼내가려 할 수 있다


Uses of semaphores

  • 공유 데이터의 상호배제를 위해 이진 세마포어가 필요
  • 가용 자원의 갯수를 세기 위해 계수 세마포어가 필요


Solution example using semaphore

image

  • Producer
    • P 연산을 통해 empty buffer가 있는지 확인하고 없다면 대기한다
    • P 연산을 통해 empty buffer가 있다면 mutex를 0으로 만들고 임계 구역에 진입한다
    • empty buffer에 데이터를 입력한다
    • V 연산을 통해 mutex 값을 1로 만든다
    • V 연산을 통해 full buffer를 1 증가하고 임계 구역에서 빠져나온다


  • Consumer
    • P 연산을 통해 full buffer가 있는지 확인하고 없다면 대기한다
    • P 연산을 통해 full buffer가 있다면 mutex를 0으로 만들고 임계 구역에 진입한다
    • full buffer에서 데이터를 빼 간다
    • V 연산을 통해 mutex 값을 1로 만든다
    • V 연산을 통해 empty buffer를 1 증가하고 임계 구역에서 빠져나온다


Readers-Writers Problem

  • 한 프로세스가 DB에 쓰기 중일 때 다른 프로세스가 접근하면 안 된다
  • 읽기는 동시에 여러 명이 해도 된다


Solution

image

image


이진 세마포어 두 개를 사용한다

  • semaphore mutex = 1
    • 상호 배제를 보장해야 하므로 각각의 세마 포어 값은 1로 지정하며, 다수의 Reader들이 readCount에 동시 접근하면 데이터 불일치의 위험이 있으므로 mutex를 정의
  • db = 1
    • db는 Reader와 Writer가 공통 데이터베이스에서 서로 상호 배제를 보장해야하므로 정의


  • Reader
    • readCount도 공유 변수이기 때문에 P(mutex) 연산을 통해 readCount를 상호 배제 처리하고 값을 1 증가시킨다 (readCount++)
    • Reader가 없고, Reader가 오로지 본인 혼자라면 (if(readCount == 1)) db에 lock을 건다 (P(db))
    • V(mutex) 연산을 통해 임계 구역에서 빠져 나온다
    • db를 원하는 만큼 읽는다
    • P(mutex) 연산을 통해 readCount 상호 배제 처리하고 값을 1 감소시킨다 (readCount–)
    • 마지막으로 read를 그만하고 나가려는 프로세스가 나 하나라면 (if(readCount == 0)) db의 lock을 해제한다 (V(db))
    • V(mutex) 연산을 통해 임계 구역에서 빠져나온다.


  • Wrtier
    • P(db) 연산을 통해 db에 lock이 걸려있는지 확인한다
    • lock이 걸려 있지 않으면 db에 lock을 걸고 임계 구역에 진입한다
    • 쓰기 작업이 끝나면 V(db) 연산을 통해 db의 lock을 해제하고 임계 구역에서 빠져 나온다


  • 문제점
    • Writer가 쓰기 작업을 하고 싶어도 무조건 Read 하고 있는 프로세스인 Reader가 없어야 한다
    • 만약 Reader가 무한히 read 작업을 실행한다면 Writer는 영영 임계 구역에 진입 하지 못하는 Startvation에 빠질 수도 있다


Dining-Philosophers Problem

철학자 다섯이서 원형 식탁에 둘러앉아 생각에 빠져있다가, 배가 고파지면 밥을 먹는다.

그들의 양쪽엔 각각 젓가락 한 짝씩 놓여있고, 밥을 먹으려 할 땐 다음의 과정을 따른다.

  1. 왼쪽 젓가락부터 집어든다. 다른 철학자가 이미 왼쪽 젓가락을 쓰고 있다면 그가 내려놓을 때까지 생각하며 대기한다
  2. 왼쪽을 들었으면 오른쪽 젓가락을 든다. 들 수 없다면 1번과 마찬가지로 들 수 있을 때까지 생각하며 대기한다
  3. 두 젓가락을 모두 들었다면 일정 시간동안 식사를 한다
  4. 식사를 마쳤으면 오른쪽 젓가락을 내려놓고, 그 다음 왼쪽 젓가락을 내려놓는다
  5. 다시 생각하다가 배고프면 1번으로 돌아간다


Example

do {
    P(chopstick[i]);
    P(chopstick[(i + 1) % 5]);
    ...
    eat();
    ...
    V(chopstick[(i + 1) % 5]);
    V(chopstick[i]);
    ...
    think();
    ...
} while (1);


모두가 동시에 왼쪽 젓가락을 드는 순간부터 환형대기에 빠져 다 같이 오른쪽 젓가락을 들 수 없으므로 Deadlock이 발생할 수 있다

Deadlock의 필요 조건은 다음과 같으며, 아래의 조건이 단 하나라도 만족하지 않는다면 Deadlock은 발생하지 않는다.

  • 상호 배제
  • 비선점
  • 점유와 대기
  • 원형 대기


Solution

  • 4명의 철학자만 테이블에 동시에 앉을 수 있게 한다
  • 젓가락을 두 개 모두 집을 수 있을 때만 젓가락을 집을 수 있게 한다
  • 비대칭
    • 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집도록 방향을 정해준다


세마포어 예제

enum {thinking, hungry, earting} state[5]; // 5명의 철학자들이 가질 수 있는 상태
semaphore self[5] = 0; // 5명의 철학자들이 젓가락 2개를 모두 들 수 있는 지를 판단 (0이면 불가, 1이면 가능)
semaphore mutex = 1; // 5명의 철학자들이 state에 동시에 접근하지 못하도록 상호 배제

do {
    pickup(i); // 젓가락을 든다
    eat(); // 먹는다
    putdown(i); // 젓가락을 내린다
    think(); // 생각한다
} while (1);

void pickup(int i) {
    P(mutex); // state에 lock을 걸고 임계구역에 진입
    state[i] = hungry; // 철학자의 상태를 hungry로 변경
    test(i); // 젓가락 2개를 들 수 있는지 확인하고 가능하면 상태를 eating으로 변경한다
    V(mutex); // state의 lock을 풀고 임계 구역을 빠져나옴
    P(self[i]); // 젓가락 2개를 들 수 없는 상태로 변경
}

void putdown(int i) {
    P(mutex); // state에 lock을 걸고 임계구역에 진입
    state[i] = thinking; // 철학자의 상태를 thinking으로 변경
    test((i + 4) % 5); // 양 옆 철학자가 식사할 수 있는 상태인지 확인하고
    test((i + 1) % 5); // 식사할 수 있는 상태라면 상태를 eating으로 변경해줌 
    V(mutex); // state의 lock을 풀고 임계 구역을 빠져나옴
}

void test(int i) {
    if (state[(i + 4) % 5] != eating && state[i] == hungry && state[(i + 1) % 5] != eating) {
        state[i] = eating;
        V(self[i]); // 젓가락 2개를 들 수 있는 상태로 변경
    }
}


Monitor

The problem with semaphores

image


Concept

모니터는 동시 수행중인 프로세스 사이에서 추상 데이터 타입의 안전한 공유를 보장하기 위한 고수준의 동기화 도구이다.


monitor monitor-name
{
    shared variable declarations
    procedure body P1 (...) {
        ...
    }
    procedure body P2 (...) {
        ...
    }
    procedure body Pn (...) {
        ...
    }
    {
        initialization code
    }
}


프로세스가 공유 데이터에 접근하기 위해서는 위와 같이 모니터 내부의 프로시저를 통해서만 공유 데이터를 접근할 수 있도록 설계한다.


image


예를 들어 공유 데이터들이 있으면 밖에서 아무나 접근할 수 있는 것이 아니라 모니터 내부에 공유 데이터에 접근하는 프로시저를 정의해 놓고 이 프로시저를 통해서만 접근할 수 있게 제어한다.

모니터가 내부에 있는 프로시저는 동시에 여러 개가 실행되지 않도록 통제하는 권한을 준다.

즉, 모니터 내에서는 한 번에 하나의 프로세스만이 활동이 가능하도록 제어하므로 프로그래머 입장에서 lock을 임의로 걸 필요가 없다는 장점이 있다.


image


Producer-Consumer Problem

image


  • Producer
    • empty buffer가 없으면 empty buffer를 기다리는 큐에서 대기
    • empty buffer가 있다면 empty buffer에 데이터를 집어넣는다
    • 작업이 끝나면 full.signal()을 통해 full buffer를 기다리는 큐에 프로세스 하나를 깨우라고 알림


  • Consumer
    • full buffer가 없으면 full buffer를 기다리는 큐에서 대기
    • full buffer가 있다면 full buffer의 데이터를 꺼내서 *x에 값을 저장한다
    • 작업이 끝나면 empty.signal()을 통해 empty buffer를 기다리는 큐에 프로세스 하나를 깨우라고 알림


Dining-Philosopher Problem

monitor dining_philosopher
{
    enum {thinking, hungry, eating} state[5]; // 5명의 철학자들이 가질 수 있는 상태
    condition self[5]; // 5명의 철학자들이 젓가락 2개를 모두 들 수 있는 지를 판단

    void pickup(int i) {
        state[i] = hungry; // 철학자 자신의 상태를 hungry로 변경
        test(i); // 철학자 자신에게 식사할 수 있는 기회를 준다 (test 함수 참고)
        
        // 식사를 하지 못했다면 상태가 eating으로 변경되지 않았음을 의미한다
        // 따라서 wait 큐에서 대기한다
        if (state[i] != eating) {
            self[i].wait();
        }
    }

    void putdown(int i) {
        state[i] = thinking; // 식사를 마쳤으므로 상태를 thinking으로 변경한다
        test[(i + 4) % 5]; // 자신의 왼쪽 철학자에게 식사할 수 있는 기회를 준다 (test 함수 참고)
        test[(i + 1) % 5]; // 자신의 오른쪽 철학자에게 식사할 수 있는 기회를 준다 (test 함수 참고)
    }

    void test(int i) {
        // 자신의 왼쪽 젓가락과 오른쪽 젓가락을 모두 들 수 있는지 확인
        if ((state[(i + 4) % 5] != eating) && (state[i] == hungry) && (state[(i + 1) % 5] != eating) {
            // 모두 들 수 있다면 수행
            state[i] = eating; // 상태를 eating으로 변경한다 
            self[i].signal(); // wait 큐에서 자신을 깨운다
        }
    }
}

Each Philosopher:
{
    pickup(i);
    eat();
    putdown(i);
    think();
} while (1)


© 2022. All rights reserved.