데이터 접근 패턴 in 컴퓨터시스템

• 데이터를 읽어오는 곳과 연산하는 곳이 다르기 때문에 synchronization 문제가 발생한다.

Process Synchronization 문제

• == Concurrency Control
• 공유 데이터에 동시 접근 (concurrent access) 하면 데이터의 불일치 (inconsistency) 가 발생할 수 있다.
• 일관성 유지를 위해서 협력 프로세스 간 실행 순서를 정해주는 메커니즘이 필요하다.

Race Condition

• 여러 프로세스들이 동시에 공유 데이터에 접근하는 상황
• 데이터의 최종 연산 결과는 마지막에 해당 데이터를 다룬 프로세스에 따라 다른 결괏값이 나오게 된다.

• 하나의 저장 공간(Memory Address Space) 공유하는 여러 실행장치(CPU Process) 가 있다면 Race Condition 이 일어날 가능성이 있다.

• 1. Multiprocessor
• 2. 공유 메모리를 사용하는 프로세스
  • 다른 값이 나올 순 있지만 심각한 문제를 초래하진 않음.
• 3. Kernel 루틴 사이에 (심각)
  • 만약... 커널 모드로 수행 중에 인터럽트로 커널 모드의 다른 루틴을 실행한다면...?

해결 : concurrent process 를 동기화(synchronize - 순서대로 접근하게) 해야함.

Race Condition in OS

우리가 배우는 Single processor 환경에서는 사용자 프로세스의 공유 메모리가 아니면 race condition 이 잘 일어날 일이 없는데,
OS 커널 코드는 여러 프로세스가 실행할 수 있기 때문에 문제가 생긴다.

1 커널 수행 중 인터럽트 발생

• count++ 이라는 문장에 CPU 에서는 ( load / Inc 연산 / store ) 3가지 문장으로 나누어져 실행
• 2번 연산을 하던 중에 (저장 안됨) 인터럽트가 걸린다면? -> 인터럽트 처리 루틴
• 인터럽트 처리 루틴 역시 커널 코드이므로..
• count-- 실행해서 저장하고 count++ 의 컨텍스트로 돌아오면 count-- 한 것은 없고 count++ 연산중인 곳으로 돌아와서 저장.

해결 : 중요한 변수에 작업 중일때는 인터럽트 처리를 못하도록 한다.
-> 근데 그걸 어떻게 효율적으로 할지...

2 프로세스가 시스템콜을 해서 커널 모드로 실행중인데 context switch 가 일어남

• 프로세스는 사용자 모드와 커널 모드를 반복하면서 실행된다.
  • 시스템콜을 통해서 커널모드로 실행

사용자 프로세스가 시스템콜을 통해 커널 모드로 프로세스 실행중에 timer interrupt 가 걸리면?

• PA 가 진행한 count++ 이 한번만 반영되게 된다.

해결 : 커널 모드에서 수행 중일 때는 CPU를 preempt 하지 못하게 한다.

3 multiprocessor 에서 공유 메모리 내의 커널 데이터

CPU 가 여러개 - 앞의 해결책으로는 해결할 수가 없음.

해결책
1. 한번에 하나의 CPU 만 커널에 들어갈 수 있게 한다. -> 비효율적...
2. 공유 데이터에 접근할 때 그 데이터에 대한 lock / unlock 을 걸어서 프로세서의 접근을 제어한다. -> 효율적.

Critical Section

공유 데이터에 접근하는 '코드'

• 하나의 프로세스가 critical section 에 있다면
• 다른 프로세스는 CPU를 잡더라도 critical section 에 접근하지 못하고 기다리게 한다.
• 이걸 어떻게 효율적으로 수행할지??

해결책 1 : Lock

가정

• 프로세스 2개 (P0, P1)
• 프로세스의 구조

do {
    entry section // lock
    critical section
    exit section // unlock
    remainder section
} while(1);

• 프로세스들은 수행 시 동기화를 위해서 변수(synchronization variable)를 공유한다.

충족 조건

• Mutual Exclusion
  • 프로세스 하나가 critical section 에 있으면 다른 프로세스는 critical section 에 들어가지 못하도록.
• Progress
  • critical section 에 아무도 없는 상황에서 어떤 프로세스가 critical section 에 들어가고 싶어하면 들어가게 해줘야 함.
• Bounded Waiting (유한 대기)
  • 프로세스가 critical section 에 들어가려고 요청한 후부터 요청이 허용되기 전까지 다른 프로세스들이 critical section 에 들어가는 횟수에 한계가 있어야한다.
  • starvation : 하나가 기다리고 있는데 나머지 두개가 critical section 에 번갈아 들어가는 경우

Algorithm 1

• synchronization variable

int turn = 0; 
// turn 이 i 이면 Pi 가 critical section 에 들어갈 수 있음.

• Process P0

do {
    while (turn != 0); // turn 이 0 이 아니면 무한루프 대기.
    critical section
    turn = 1; // 나올 때 상대방의 차례로 만들어 줌.
    remainder section
} while(1);

• mutual exclusion O / progress X
  • 동시 접근은 일어나지 않지만,
  • 한번씩 교대로 들어갈 수만 있음.
  • 둘 중 하나의 프로세스가 더 많이 critical section 에 접근한다면..? -> 영원히 못 들어감.

Algorithm 2

• synchronization variable

boolean flag[2] = { false }; // flag [i] == true 이면 Pi 가 critical section 에 접근할 준비가 되었다.

• Process P0

do {
    flag[i] = true; // 나 들어가고 싶어.
    while (flag[j]); // 상대방의 flag 확인.
    critical section
    flag[i] = false; // 나올 때 unlock
    remainder section
} while(1);

• mutual exclusion O / progress X
  • Pi 가 깃발을 들고 CPU 를 Pj에 빼앗기면 들어간 녀석은 없는데 두 flag 만 모두 true
  • while 문에서 서로 계속 양보하게 된다.

Algorithm 3 : Peterson's Algorithm

• turn, flag 를 모두 사용.

do {
    flag[i] = true; // 나 들어가고 싶어.
    turn = j; // turn 역시 들어가기 전에 바꿔 놓음.
    while (flag[j] && turn == j); // 상대방의 flag 를 들고 있고 상대방의 차례이면 기다림.
    critical section
    flag[i] = false; // 나올 때 unlock
    remainder section
} while(1);

• flag[j] && turn == j
• 3가지 요구사항 모두 만족.
• 변수를 두개나 쓰면서까지 코드를 짜야 하는 이유
  • 고급 기계어는 여러 instruction 으로 나누어져서 실행되기 때문에, 나누어진 하나의 instruction 을 실행하다 CPU 를 빼앗길 수 있기 때문. -> HW 적으로 하나의 instruction 만 주어지면 해결

• 문제점 : Busy Waiting (== Spin Lock) - 계속 CPU 와 메모리를 쓰면서 기다리게 된다.
• 다른 프로세스가 critical section 에 들어가있으면 한 프로세스가 CPU 잡은 동안 계속 while 문을 돌면서 critical section 에 들어갈 수 있는지 확인해야 함.
• 하지만 상대방이 CPU 를 잡기 전에는 while 을 빠져나갈 가능성이 없음.. 낭비

Hardware

• process synchronization 문제는 데이터를 읽고 쓰는 것이 하나의 instruction 으로 이루어져있지 않아서 발생하는 문제.
• HW 적으로 Test & modify 를 atomic 하게 (동시에) 실행할 수 있다면 간단하게 해결 가능.

• synchronization variable

boolean lock = false;

do {
    while (Test_and-Set(lock)); // lock 이 걸려있는지 체크하고, 안걸려있으면 lock = true 를 atomic 하게 넣는다.
    critical section
    lock = false; // 나올 때 unlock
    remainder section
} while(1);

해결책 2 : 추상자료형 - Semaphores

• 프로그래머가 critical section 에 들어가는 모든 코드를 신경쓰긴 힘드니
• 추상자료형(필요한 프로퍼티, 메서드로 이루어진 논리자료형)으로 연산을 통해 확인할 수 있게 만든 것.

Semaphores

Semaphore S

• 정수 변수. 공유 자원의 개수를 가지고 있음.
• P, V 라는 atomic 연산으로만 접근 가능
  • P : 공유 변수 획득 + lock / 자원 개수 --
  • V : 공유 변수 반납 + unlock / 자원 개수 ++
  • 해당 연산을 구현하는 시스템의 몫.

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

V(S): S++;

• 종류
  • counting semaphore
    • 자원의 개수가 여러개라 0 이상의 정수값을 사용.
  • binary semaphore (= mutex)
    • 0 또는 1의 값만 가짐
    • mutual exclusion (lock / unlock) 에 사용한다.

busy-waiting

Semaphore mutex;

do {
    P(mutex);
    critical section
    V(mutex);
    remainder section
} while(1);

-> while 문으로 계속 기다리는 busy-waiting 은 효율적이지 못하므로 block & wakeup 방식으로 구현한다.

Block & wakeup

P(S)

S.value--;
if (S.value < 0) { // 공유 자원 접근 불가
    add this process to S.L;
    block(); // 자도록.
}

V(S)

S.value++;
if (S.value <= 0) { // 자원을 내놨는데 기다리는 프로세스가 있음.
    remove a process P from S.L;
    wakeup(P); // 일어나도록.
}

• block & wakeup 프로세스를 재우고 깨우는데에 대한 오버헤드가 있으므로, critical section 의 길이가 매우 짧은 경우 busy-wait 가 나을 수도 있다.
• 일반적으로는 block & wakeup 이 더 효율적.

세마포어의 문제점 : Deadlock & Starvation

Deadlock : 둘 이상의 프로세스가 서로가 가진 공유 자원을 무한히 기다리는 현상.

• 코드 각각은 논리적으로 문제가 없지만 둘이 같이 있으면 문제가 생긴다.
• 자원을 획득하는 순서를 맞추어서 해결할 수 있다.
  • 둘 다 S 먼저 얻어야 Q 를 얻을 수 있게!

Starvation

• Indefinite blocking : 몇 프로세스만 공유 자원을 독점하면서 어떤 프로세스는 영원히 자원을 얻지 못해서 실행되지 못함.
• Deadlock 도 일종의 starvation

Synchronization 의 고전 예시

Bounded-Buffer Problem (Producer-Consumer Problem)

시나리오

생산자 프로세스는 데이터를 생산해서 버퍼에 넣고, 소비자 프로세스는 데이터를 버퍼에서 꺼내가서 소비함.

발생 가능한 문제점

1. 생산자 둘이 버퍼 한칸에 동시에 데이터를 씀 -> 버퍼에 대한 mutex (lock) 필요
2. buffer 가 다 찼는데 생산자가 도착함 -> 생산자 입장에서 자원이 0개인 것이므로 소비자가 data 꺼내갈 때까지 기다려야 함.
3. buffer 가 비어있는데 소비자가 도착함 -> 생산자가 data 생산할 때까지 기다려야 함.

Shared Data

크기가 유한한 버퍼.

buffer x;

Synchronization variables

• mutex (binary semaphore)
  • 버퍼에 대한 mutual exclusion 을 제공하기 위해 lock 을 걸고 푸는 용도
• integer semaphore
  • 남는 full / empty buffer 의 수를 표시함.

semaphore full = 0, empty = n, mutex = 1; // 들어있는 버퍼 개수, 비어있는 버퍼 개수, 버퍼에 하나의 프로세스만 접근하게 하기 위한 lock

Producer

do {
    produce an item in x
    
    P(empty); // 비어있으면 버퍼 얻어오면서 빈개수--
    P(mutex); // 버퍼에 접근하기 위한 락
    
    add x to buffer
    
    V(mutex);
    V(full); // 가득찬개수++
} while(1)

Consumer

do {
    P(full);
    P(mutex);
    
    remove an item from buffer to y
    
    V(mutex);
    V(empty);
    
    comsume the item in y
} while(1);

Readers and Writers Problem

시나리오 : 공유 자원에 데이터를 읽기만 하는 Reader 와 데이터를 변경할 수 있는 Writer 존재.
Reader 는 한번에 여러 프로세스가 접근해도 되지만,
Writer 가 접근 중일 때는 다른 프로세스가 접근할 수 없음.

Shared Data

db;
int readcount; // 현재 DB에 접근 중인 Reader 의 수.

Synchronization Varaibles

semaphore mutex = 1; // readcount 를 위한 lock
semaphore db = 1; // db 에 대한 lock

Writer

P(db); // lock

writing DB is performed;

V(db); // unlock

Reader

• DB 에는 여러 reader 가 동시에 접근 가능하지만, Writer 는 접근하면 안되므로 lock 을 걸긴 해야함.

P (mutex); // readcount 에 대한 lock 
readcount++;
if (readcount == 1) P(db); // 처음으로 접근하는 reader 라면 db에 lock
V(mutex);

reading DB is performed

P(mutex);
readcount--;
if (readcount == 0) V(db);  // Reader 가 있다면, Writer 는 이걸 기다렸다가 접근 가능
V(mutex);

Starvation

만약 Reader 가 읽는 중에 계속해서 reader 가 접근하게 된다면 계속해서 reader 의 접근을 허용하므로 문제가 있다. reader 를 일정 수까지만 허용하는 등의 조치가 필요.

Dining Philosophers Problem

시나리오

5명의 철학자가 원탁에 둘러앉아서 밥을 먹는데 젓가락이 철학자 양 옆으로 1개씩 총 5개 놓여있다.
철학자는 생각을 하거나 식사를 할 수 있는데, 젓가락 양쪽을 모두 집어야 식사를 할 수 있다.

Synchronization variables

양 옆의 철학자가 공유하는 자원 젓가락

Semaphore chopstick[5] = { 1 };

Philosopher i

각 프로세스인 철학자

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

문제점

• Deadlock : 모든 철학자가 동시에 왼쪽 젓가락을 집는다면?
• 계속해서 서로 오른쪽 젓가락만을 기다린다.

해결방안

1. 4명의 철학자만 테이블에 앉을 수 있게 한다. - 혹은 밥을 먹을 때만 식탁에 앉도록
2. 젓가락을 두개 모두 집을 수 있을 때만 젓가락을 집을 수 있게 한다.
3. 비대칭 : 짝수(홀수) 철학자는 왼쪽(오른쪽) 젓가락부터 집게 한다.

해결방안 2 코드

• 양쪽 철학자가 식사중이 아니면 젓가락을 집을 수 있다.

enum { thinking, hungry, eating } state[5]; // 철학자의 상태
semaphore self[5] = 0; // 양쪽 젓가락을 잡을 권한. 처음엔 전부 권한이 없음 (0) -> 보통 semaphore 는 양수 값에 시작하는데 0으로 시작하는게 특이한 포인트
semaphore mutex = 1; // lock : 옆 철학자의 상태가 바뀌면 나의 젓가락을 집을 권한에도 영향이 오기 때문에 상태를 바꾸기 전에 lock 을 걸어야 함.

do {
    pickup(i);
    eat();
    putdown(i);
    think();
} while(1);


void pickup(int i) {
    P(mutex); // lock for state
    state[i] = hungry;
    test(i); // 젓가락 2개를다 집을 수 있는지.
    V(mutex); // unlock
    P(self[i]); // self[i] 1 -> 0 : 만약 젓가락을 잡을 수 있다면 젓가락 사용 / 없다면 대기.
}

void putdown(int i) {
    P(mutex); // lock for state
    state[i] = thinking;
    // 양 옆 철학자가 내가 젓가락을 쥐고있어서 밥을 못먹었다면 먹을수 있게 해준다.
    test((i + 1) % 5); // 오른쪽
    test((i - 1) % 5); // 왼쪽
    V(mutex); // unlock
}

void test(int i) {
    // 조건 : 양 쪽이 식사중이 아니면서 나는 배고픔.
    if (state[(i - 1) % 5] != eating && state[i] == hungry && state[(i + 1) % 5] != eating) {
        state[i] = eating;
        V(self[i]); // self[i]  0 -> 1 / 젓가락을 잡을 권한을 줌.
    }
}

근데 이렇게 코딩하니까...

Semaphore 의 문제점

• 여전히 코딩하기 어렵다. 버그 잡기 어려움.
• 정확성 입증이 어려움.
• 인터페이스 없이 자발적으로 협력해야 함.
• 한번의 실수가 시스템에 치명적인 영향을 끼칠 수 있음.

P(mutex)
critical section
V(mutex) // 잘못해서 P(mutex) 라고 써버리면... 무한대기 상태에 빠짐.

-> Monitor 로 해결해보자.

해결 3 : Monitor

• 프로그래밍 언어차원에서 Process Synchronization 을 해결하는 방법.
• 동시 수행중인 프로세스 사이에서 추상자료형을 안전하게 공유할 수 있게 보장해주는 high-level synchronization construct
  • 프로그래밍 기법인 것임.
  • 맘대로 main 함수에서 V(mutex) 이러는게 아니라 모니터의 함수를 통해 접근하게 규칙을 정해서.
  • 세마포어나 P, V 를 이해하지 않고도 사용 가능한게 장점.
  • java 에서는 procedure 에 synchronized 라는 키워드를 붙여서 이걸 지원한다.
  • wait / notify (signal) 함수도 제공.
  • 언어별로 세부 구현은 다르다.

시나리오

• 프로세스 A가 모니터 안에 와서 operation 을 하고 있다가 CPU 를 빼앗겨서 프로세스 B가 모니터에 들어오려고 하면, 이미 모니터에 active 되어있는 프로세스 A가 있으므로, 프로세스 B는 entry queue 에 줄서서 기다리게 됨.

• 프로세스가 모니터를 빠져나가거나 잠들어서 active 프로세스가 0개가 되면 엔트리 큐에 있는 프로세스가 모니터로 들어옴.

• monitor 내부에 있는 procedure (함수로 구현됨) 를 통해서만 각 공유 자원에 접근할 수 있게 하며, 여러 procedure 에 동시에 접근할 수 없다. -> lock 걸 필요가 없다.

• 모니터 내에서는 한번의 하나의 프로세스만 활동 가능하다.
• 프로그래머가 synchronization 제약 조건을 명시적으로 코딩할 필요가 없다.
• 프로세스가 모니터 안에서 기다릴 수 있도록 condition variable(Semaphore 와 비슷) 사용.
  • condition var 이용해서 프로세스가 어떤 요인 때문에 wait 하는지를 알 수 있게 코드를 짜면 된다.
• Condition Varaible 에는 wait, signal 연산을 통해서만 접근한다.
  • wait : 공유 자원에 여분이 없을 때 signal 을 부르기 전까지 잠듬. (~= P)
  • signal : 깨움. 이전에 공유 자원에 접근한 프로세스가 나가면서 호출한다. suspended 가 없으면 아무 일도 일어나지 않음. (~= V)
  • 애초에 condition var 는 값을 가지는 변수가 아니기 때문에 세마포어처럼 변수에 대한 변화는 없음.

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

Bounded-Buffer

• 공유 버퍼가 모니터 내부에 있으면서, 생산/소비자 프로세스가 접근하려고 할 때 monitor 내부 코드를 실행해야하기 때문에 한번에 하나의 프로세스만 활성화 된다. -> lock 을 걸지 않아도 됨.
• semaphore 의 경우는 lock 연산 + count 변수를 위한 것.

monitor bounded_buffer {
    int buffer[N];
    condition full, empty; // 값을 가지지 않고, 자신의 큐에 프로세스를 매달아서 sleep 시키거나 큐에서 프로세스를 깨워주는 역할만 한다.
    // full : 내용이 있는 버퍼를 기다리는 프로세스를 줄세운다.
    // empty :     없는
    
    void produce(int x) {
        if there is no empty buffer
            empty.wait(); // 생산자 기준 자원 없음 -> 재움
        add x to an empty buffer
        full.signal(); // 소비자 깨움
    }
    
    void consume(int x) {
        if there is no full buffer
            full.wait(); // 소비자 기준 자원 없음 -> 재움
        add x to an full buffer
        empty.signal(); // 생산자 깨움
    }
}

Dining Philosophers

monitor dining_philosopher {
    enum { thinking, hungry, eating } state[5];
    condition self[5];
    
    void pickup(int i) {
        state[i] = hungry;
        test(i); // 젓가락 2개를다 집을 수 있는지.
        if (state[i] != eating) 
            self[i].wait(); // semaphore 일 땐 P 연산으로 들어가던 것.
    }

    void putdown(int i) {
        state[i] = thinking;
        test((i + 1) % 5);
        test((i - 1) % 5);
    }

    void test(int i) {
        if (state[(i - 1) % 5] != eating && state[i] == hungry && state[(i + 1) % 5] != eating) {
            state[i] = eating;
            self[i].signal(); // 잠들어 있다면 깨운다.
        }
    }
    
    void init() {
        for (int i = 0; i < 5; i++)
            state[i] = thinking;
    }
}


Philosopher {
    do {
        pickup(i); // 모니터 안에 있는 연산을 이용.
        eat();
        putdown(i); // 모니터 안에 있는 연산을 이용.
        think();
    } while(1);
}

• 자바의 경우 모니터를 사용하고, 자바의 모든 객체는 모니터가 될 수 있다.
• Swift 는 모니터도 있고 세마포어도 있는데 더 찾아보면 좋을듯 참고

• 세마포어는 자원을 획득하기 위해 프로그래머가 직접 연산을 하는 것.
• 모니터는 프로세스를 하나만 접근하게 하기 위해 제공하는 인터페이스.

출처 / 참고

반효경 교수님의 2014 운영체제 6. Process Synchronization, 2, 3, 4 강의를 듣고 포스팅하고,
공룡책을 읽고 추가 정리합니다.

사진 출처는 강의 자료.