[운영체제] Process Synchronization

Process Synchronization

공유 데이터의 동시 접근 상황에서 데이터 불일치가 발생할 수 있기 때문에 일관성을 유지하기 위해 프로세스 간의 실행 순서를 정해주는 메커니즘이 필요하다.

Race condition

공유된 자원에 여러개의 프로세스가 동시에 접근할 때 발생하는 문제.
ex) 공유자원에 count라는 변수가 있을 때, 프로세스 a에서는 count--, 프로세스 b에서는 count++을 해주었을 때 실행 순서에 따라 값이 달라지는 경우

race condition을 막기 위해 concurrent process는 동기화 되어야한다.

• kernal 수행 중 인터럽트 발생 시
  -> 공유 데이터를 건드리는 동안 interrupt를 못하도록 막기
  
• Process가 system call을 하여 커널 모드로 수행 중인데 context switch가 일어나는 경우
  -> 커널 모드에서 수행 중일 때는 CPU를 뺏지 않고, 커널 모드가 끝나 유저 모드로 돌아갈 때 CPU를 가져온다.
  
• Multiprocessor(cpu가 여러개)에서 shared memory 내의 kernal data
  -> 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
  -> 공유 데이터 사용시 해당 데이터에 대해 lock을 걸어 어느 누구도 접근 못하게 함
  

Critical Section Problem

Critical Section이란 공유 데이터를 접근하는 코드.

공유 데이터를 접근하는 코드가 실행중이라면 CPU가 뺏겨서 다른 프로세스에 CPU가 넘어가더라도 다른 프로세스의 공유 데이터를 접근하는 Critical Section에 들어가지 못하도록 해야한다.

do {
    entry section - 여러 프로세스가 동시에 critical section에 들어가지 못하도록 lock
    critical section - 공유 데이터를 접근하는 코드
    exit section - lock 풀어서 다른 프로세스가 critical section에 들어갈 수 있도록
    remainder section
} while(1);

Critical Section 문제를 해결하기 위하여 만족해야 하는 조건

1. Mutual Exclusion(상호 배제)
   -> 어떤 프로세스가 critical section에 들어가 있으면 다른 모든 프로세스들을 critical section에 들어갈 수 없다.
2. Progress(진행)
   -> critical section에 아무도 들어가 있지 않을 때 critical section에 들어가려는 프로세스가 있다면 critical section에 들어가게 해주어야 한다.
3. Bounded Waiting(유한 대기)
   -> 특정 프로세스가 critical section에 들어가지 못하고 지나치게 오래 기다려서는 안된다.(starvation 방지)

algorithm1

do {
    while(turn != 0); - 자기 차례가 될 때 까지 기다린다.
    critical section
    turn = 1;         - 다음 차례로 넘겨준다.
    remainder section
} while(1);

Mutual Exclusion은 만족하지만 Progress를 만족하지 못한다.(예를 들어 P0은 critical section에 100번 들어가야하고, P1은 1번만 들어가도 된다고 하면 P0이 100번 들어갈 수 없다. P1이 진행되어야지만 P0 차례로 넘어갈 수 있기 때문이다.

algorithm2

boolean flag[2]; - 각 프로세스마다 flag가 존재. critical section에 들어가고자 하는 상태를 나타냄. 초기에는 모두 false

do {
    flag[i] = true; - critical section에 들어가고자 하는 의사를 나타냄
    while(flag[j]); - 상대방 flag를 체크
    critical section
    flag[i] = false; - 사용 완료를 나타냄
    remainder section
} while(1);

Mutual Exclusion은 만족하지만 Progress를 만족하지 못한다.(예를 들어 Pi가 flag를 true로 바꾸고 바로 CPU를 빼앗겨 Pj에 CPU가 넘어가면 Pj도 flag를 true로 바꿨는데 이미 Pi의 flag가 true이므로 아무도 critical section에 없더라도 아무 프로세스도 critical section에 들어갈 수 없다.)

algorithm3(peterson's algorithm)

do {
    flag[i] = true; - critical section에 들어가고자 하는 의사를 나타냄
    turn = j; - 상대방 turn으로 바꿔줌
    while(flag[j] && turn == j); - 상대방이 flag를 들고 있고 동시에 상대방 차례인 경우만 기다림
    critical section
    flag[i] = false; - 사용 완료를 나타냄
    remainder section
} while(1);

모든 조건을 만족함. 그러나 Busy Waiting(spin lock) 문제가 발생(상대 프로세스가 critical section에 있는 경우 본인은 while문을 계속 돌고 있다.)