[OS] 프로세스 동기화

OS 동기화

Race condition (자원 경쟁)

두 개의 프로세스가 하나의 자원에 대해 동시에 접근하는 상태

• 예시1. kernel 수행 중 인터럽트 발생
  kernel 모드가 실행중인데 인터럽트가 들어왔다. (예를 들면, 타이머 인터럽트) 인터럽트 또한 OS가 주도권을 갖고 있는 상황이기 때문에 kernel mode이며 이전에 실행되던 프로세스와 같은 주소공간을 공유하고 있다. 이에 따라 공유된 data 를 가지고 경쟁하게 되는 상황이 된다.

• 예시2. process가 system call를 하여 kernel mode로 수행 중인데 인터럽트 당하여 context switch 가 일어나고 다시 kernel mode로 들어가는 경우
  모든 프로세스는 kernel mode에서 다같은 공유 데이터 공간을 쓰기 때문에 발생하는 문제이다.

• 예시3. multiprocessor 에서 shared memory 내의 kernel data

예시 1과 2는 모두 kernel 모드 도중에 인터럽트 당하여 생기는 문제이다. 하지만 통상 이러한 상황을 방지하기 위해 kernel mode에서는 인터럽트 처리루틴으로 넘어가지 않도록 설계되어 있다.

그리고 예시 3은 cpu가 여러개이고 하나의 메모리를 접근하기 때문에 생기는 문제이다.

Process Synchronization 문제

concurrent process 가 공유 데이터에 동시 접근을 하는 경우 데이터 불일치 문제가 발생할 수 있다. 따라서 concurrent process 간의 실행 순서를 정해주는 매커니즘이 필요하고 이것을 동기화 한다고 얘기한다.

이때 동기화에 사용되는 변수를 synchronization variable 이라고 한다. 그리고 각 프로세스의 공유데이터에 접근하는 코드 부분을 critical section 이라고 한다.

동기화 충족 조건

1. Mutual Exclusion

특정 프로세스가 critical section 를 수행 중이면 다른 모든 프로세스들은 critical section 에 들어가면 안된다.

2. Progress

아무도 critical section 에 있지 않은 상태에서 critical section 에 들어가고자 하는 프로세스가 있다면 critical section 에 들어가게 해주어야 한다.

3. Bounded Waiting

프로세스가 critical section 에 들어가려고 요청한 후 부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section 에 들어가는 횟수에 한계가 있어야한다. 즉 프로세스를 무한정 대기시켜서는 안된다.

동기화 알고리즘

첫 번째 시도

do {
  while (turn!=0); // 내 턴이 올 때까지 대기
  critical section
  turn = 1;
  ...
} while(1)

synchronization variable : int turn (turn == i 일때 프로세스 i 가 진입 가능)
progress 조건을 만족시키지 못한다. 예를 들어 현재 critical section 에 아무도 없는 상태이고 프로세스 1이 진입하려고 할때 다른 프로세스에서 turn 값을 1로 바꿔주지 않는다면 영영 진입 불가이다.

두 번째 시도

do {
  flag[i] = true; // 가고 싶다는 의사를 flag 로 표시
  while (flag[j]);
  critical section
  flag[i] = false;
  ...
} while(1)

synchronization variable : boolean flag[2] (flag[i] = true 일때 프로세스 i가 진입 가능)
progress 조건을 만족시키지 못한다. 예를 들어 프로세스 1과 2가 동시에 실행되어 서로의 flag 가 1이 되는 경우 둘다 critical section 에 못 들어간다.

세 번째 시도 (Peterson's Algorithm)

첫번째 시도와 두번째 시도를 합한 방법이다.

do {
  flag[i] = true; // 가고 싶다는 의사 표시
  turn = j; // 다른 쪽으로 턴을 넘긴다
  while (flag[j] && turn == j); // 다른 쪽 턴인데 그 쪽에서 cs 진입 원한다면 대기
  critical section
  flag[i] = false;
  ...
} while (1);

세 가지 조건을 모두 만족시킨다. 하지만 cpu는 while 문을 통해 지속적으로 확인을 해주어야한다. 이는 cpu와 메모리에 부하를 주는 일이므로 비효율적이다. 이를 Busy Waiting 또는 Spin Lock 이라고 부른다.

하드웨어로 동기화

하드웨어적으로 Test & set 를 atomic 하게 (무조건 한 번에 수행이 되도록 명령어가 쪼개지지 않는 상황) 수행할 수 있도록 지원하는 경우에도 해결이 가능하다.

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

즉, 하드웨어적으로 특정한 행위가 한 큐에 실행되도록 구현만 가능하다면 이전의 방법보다 훨씬 간단하게 동기화가 가능하다. 그렇게 구현한 것이 Semaphore 이다.

세마포어

추상 자료형으로 구현되어 있는 세마포어는 오브젝트와 함수로 구현되어있다.

typedef struct 
{
    int value; // 세마포어 (자원의 남은 개수)
    struct process *L; // process wait 큐
} semaphore

P(S) { // 자원 획득
  while (S<= 0) do no-op;
  S--;
}

V(S) { // 자원 반납
    S++;
}

이때 세마포어의 value 가 1 인 것을 mutex 라고 칭한다. 자원이 1개라는 것은 단 하나의 프로세스만 Critical Section 에 들어갈 수 있음을 뜻한다.

세마포어를 이용한 동기화 - busy-wait

semaphore mutex;

do {
  P(mutex); // mutex 가 양수이면 cs 에 진입 가능 그러나 여기서 busy-wait 문제 발생
  critical section
  V(mutex);
  ...
} while (1);

P 함수 구현을 보면 while 문을 통해 세마포어의 값을 확인해줘야 한다. 이는 부하로 이어지기 때문에 단점이다.

세마포어를 이용한 동기화 - block/wake-up implementation

typedef struct 
{
    int value;
    struct process *L;
} semaphore;

P(S) {
  S.value--;
  if(S.value < 0) {
    add this process to S.L; (세마포어에 대한 wait 큐)
    block();
  }
}

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

S 가 0 보다 작다는 것은 자원을 기다리고 있는 프로세스가 있다는 것이다. 즉 세마포어에 대한 대기 큐에 줄 서있다.

block - 커널은 block를 호출한 프로세스를 정지(suspend)시킨다. 그리고 프로세스의 PCB를 세마포어에 대한 wait queue에 넣는다.
wakeup(P) - block된 프로세스 P를 wakeup 시킨다. 프로세스의 PCB가 ready queue에 들어간다.

기억하자! 다양한 행위에 대한 wait 큐가 존재한다. 입출력 장치, CPU 에 대한 큐를 앞에서 보았었고 여기서는 공유데이터에 대한 큐도 추가된 것이다. (특별히 CPU의 wait queue는 메모리에 적재되었지만 아직 CPU 할당 받지 못한 것들을 위한 ready queue 라고 불린다.)

block/wakeup 도 세마포어에 대한 wait 큐로 옮기고 다시 ready 큐로 옮기는 것에 대한 부하는 존재한다.

busy-wait vs block/wakeup

block/wakeup 의 단점 : 세마포어 큐와 CPU ready 큐로 옮기는 과정에서의 부하
busy-wait 의 단점: while 문에서 세마포어를 확인하는 것에 대한 부하

결론적으로는 critical section 소요 시간이 오래걸려서 다른 프로세스의 while 문이 많이 돌아가는 경우 busy-wait 보단 block/wakeup 방식이 좋다. 그러나 critical section 이 아주 짧아서 while 문에 대한 부담이 거의 없다면 큐를 왔다갔다 하지 않는 busy-wait 방식이 더 좋다. (하지만 대체로 block/wakeup 방식이 더 좋다. redis에서 lettuce 가 아니라 redisson를 썼던 이유가 되기도 한다.)

동기화 문제 예시

Bounded-Buffer Problem (Producer-Consumer Problem)

유한한 크기를 갖는 버퍼에서의 생산자-소비자 문제이다. 이곳에서는 여러 가지 동기화 문제가 존재한다.

• 생상자 (또는 소비자) 둘이 와서 같은 장소를 비어있다고 (채워져있다고) 확인했다. 둘이 동시에 같은 곳의 데이터에 접근한다면?
• 생산자가 비어있는 자리를 확인하고 접근했는데 그 사이에 다른 생산자가 벌써 채워버린다면?

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)
  ...
  consume the item in y
  ...
} while(1);

synchronization variable

• full : 채워져있는 버퍼 개수
• empty : 비어져있는 버퍼 개수
• mutex : critical section에 락을 걸기 위함

  Readers-Writers Problem

  
  하나의 프로세스가 DB 에 write 중 일때 다른 프로세스가 접근하면 안된다. 대신 read 는 동시에 여럿이 접근해도 괜찮다.
  
  shared data
• readcount
• db 그 자체
  synchronization variable
• db : db 접근에 대한 세마포어 변수
• mutex : readcount 라는 공유 변수에 대한 세마포어 변수

writer 의 입장에서 누군가가 읽기 위해 DB 자원을 가져갔다면 (P(db)) 기다린다. 그러다가 자원이 반납되면 (V(db)) 그제서야 쓸 수 있는 권한이 생겼다.

reader 의 입장에서 누구든지 읽으러 들어온다면 mutex 로 동기화를 하며 readcount++ 를 한다. 그 중에서도 만약 첫 reader 라면 db 자원을 가져간다(P(db)). 읽기가 끝난다면 mutex 로 동기화를 하며 readcount--를 해준다. 그 중에서도 나가는 reader 가 마지막 reader 라면 db 자원을 반납한다. (V(db))

하지만 여기서의 문제는 reader가 끊임없이 들어온다면 writer 가 영영 db 자원을 못 얻는다는 것이다. 이것은 우선순위 큐를 통해 오래 기다리면 우선순위를 높여주도록 구현을 한다면 해결이 가능하다.

Dining Philosophers Problem

철학자가 원형 테이블에 모여 식사를 하려고 한다. 양쪽의 젓가락 두 개를 모두 가져야 식사가 가능하지만 영영 식사를 못할 가능성이 존재한다. 예를 들면 모든 철학자가 동시에 왼쪽 젓가락을 집는다면 아무도 식사를 못한다.

이를 해결하기 위해 젓가락 두개 모두 잡을 수 있을 떄에만 젓가락을 집을 수 있게 하려고 한다.

• self : 젓가락 2개를 모두 잡을 수 있는 권한이 있을 때 1
• mutex : state 에 대한 락을 걸기 위한 동기화 변수
• test : 두 개 다 잡을 수 있는 상황인지 확인해보기

모니터

세마포어는 프로그래머가 직접 코드를 짜야하기 때문에 번거롭고 실수하면 큰 문제로 이어질 수 있다. 따라서 안전한 동기화 방법을 high-level 에서 제공해주는 것을 monitor 라고 한다.

모니터는 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위해 고수준에서 구현이 되어있다. (예를 들면 자바의 synchronized) 하나의 프로세스만이 모니터에 접근할 수 있고 나머지는 entry queue 에서 대기하게 된다.