동기화 (Synchronization) - (2)

1. Peterson의 해결안 (Peterson's Solution)

• flag, turn 변수를 사용
• flag : 특정한 프로세스가 임계 구역으로 들어갈 준비가 되었다는 것을 나타낸다. (true, false)
  • flag [i]가 true라면 Pi가 임계 구역으로 진입할 준비가 되었다는 것을 나타낸다.
• turn : 임계 구역으로 진입할 프로세스의 순번
  • turn == i이면 프로세스 Pi가 임계 구역에서 실행될 수 있다.

// 프로세스 i의 실행 구조
while (true) {
    flag[i] = true;  //프로세스 i가 임계구역에 들어갈 준비가 됨
    turn = j; // 프로세스 j가 실행될 차례 (turn을 상대방에게 양보한다)
    while (flag[j] && turn == j); //flag[j]가 false이거나 turn이 i인 경우 무한루프 탈출
    
    /* critical section */  
    
    flag[i] = false; //프로세스 i 작업 완료 후, flag[i] = false로 설정
    
    /* remainder section */
}

(1) Peterson의 해결책 증명

• 피터슨의 해결책은 임계 구역 해결책의 세 가지 조건을 충족한다.
• 상호 배제 (mutual exclusion)
  • Pi는 flag[j]==false이거나 turn==i인 두 조건 중 하나가 만족되어야만 임계 구역에 들어간다.
  • Pi와 Pj는 동시에 임계 구역에 들어갈 수 없다.
• 진행 (progress)
  • Pi는 flag[j]==true이고 turn==j인 경우에만 멈춘다.
• 한정된 대기 (bounded waiting)
  • Pi는 기껏해야 Pj의 한 번의 출입 후 임계 구역에 들어가게 된다.

(2) Peterson의 해결책 적용 어려움

• 피터슨의 해결책은 최신 컴퓨터 구조(out of order)에는 보장되기 어렵다.
  • 성능 향상을 위해 종속성이 없는 읽기 및 쓰기 작업들을 재 정렬할 수 있다.
  • Multual exclusion이 보장되지 않는다.

 

2. 동기화 하드웨어 (Synchronization Hardware)

(1) 메모리 장벽 (Memory Barriers)

(2) 하드웨어 명령어 (Hardware Instructions)

(3) 원자적 변수 (Atomic Variables)

• 임계 구역 문제에 대한 하드웨어 기반 해결책은 복잡할 뿐 아니라 application 프로그래머는 사용할 수 없다.

 

3. Mutex Locks

• 프로세스가 임계 구역에 들어가기 전에 lock을 획득하고, 나올 때는 lock을 반환하는 방식
• mutex lock에서는 available이라는 변수를 가지고, 이 available 변수를 가지고 lock의 가용 여부를 판단
• 단점 : busy waiting (기다리면서 계속 반복 실행, CPU 시간 낭비)

while (true) {
    acquire lock // lock이 가용하다면 acquire()를 호출해서 lock을 획득하고, 다른 프로세스가 접근하지 못하도록 lock 사용불가 처리
    
    /* critical section */
    
    release lock
    
    /* remainder section */
}

acquire() {
    while (!available);   /* busy wait */
    
    available = false;
}

release() {
    available = true;
}

 

4. Semaphore

• 세마포 S는 정수 변수로서, 초기화를 제외하고는 단지 두 개의 표준 원자적 연산 wait()와 signal()로만 접근할 수 있다.
• 이진 세마포
  • 0과 1사이의 값만 가능하다. 
  • 시작 시 1로 초기화
• 카운팅 세마포
  • 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용
  • 세마포는 가용한 자원의 개수로 초기화된다.
• 각 자원을 사용하려는 프로세스는 세마 포에 wait() 연산을 수행하며, 이때 세마포의 값은 감소한다.
• 프로세스가 자원을 방출할 때는 signal() 연산을 수행하고 세마포는 증가하게 된다. 
• 세마포의 값이 0이 되면 모든 자원이 사용 중임을 나타낸다.
• 이후 자원을 사용하려는 프로세스는 세마포 값이 0보다 커질 때까지 봉쇄된다.
• busy waiting 발생 할 수 있다.

wait(S) {
    while (S <= 0); //busy wait
    S--;
}

signal(S) {
    S++;
}​

(1) Example

• P1의 S1 명령문 실행 후 P2의 S2 명령문 실행을 보장한다.

// P1
S1; synch 0으로 초기화 S1 명령문 실행
signal(synch); // synch++ => 1

// P2
wait(synch); // synch-- => 0
S2; S2 명령문 실행

(2) 세마포 구현 (Semaphore Implementation)

• busy wait을 없는 세마포를 구현한다.
• block() 연산에 의해서 waiting queue에 들어간다.
• wakeup() 연산에 의해서 waiting queue에서 제거되고 ready queue에 들어간다.

typedef struct {
    int value; // 세마포 값
    struct process &list; // 대기 중인 PCB 리스트를 가르키는 포인터
} semaphore;

wait (semaphore *S) {
    S->value--;
    if (S->value < 0) {     //S->value가 음수면 waiting list에 넣는다.
    	add this process to S->list;
        block(); 
    }
}

//종료시
signal (semaphore *s) {
    S->value++;
    if (S->value <= 0) {
    	remove a process P from S->list;  //process waiting list에서 뺀다.
        wakeup(p); 
    }
}

• Semaphore의 waiting queue 구현 방법
  • Semaphore 구조체에 연결된 연결 리스트로 구현
  • 대기 중인 프로세스들의 PCB를 연결
  • 음수 값은 대기 중인 프로세스의 개수를 의미한다.
  • 양수 값은 이용 가능한 자원의 개수를 의미한다.

5. Monitors

• 세마포어를 이용하여 임계 구역 문제를 해결할 때 프로그래머가 세마포어를 잘못 사용할 경우 다양한 유형의 오류가 쉽게 발생한다
• 쉽고 효율적인 프로세스 동기화 수단을 제공하는 고급 언어 수준의 동기화 구조물이다.

(1) 조건 변수 (Condition Variables)

• mutex 간의 순서를 보장하기 위함
• 조건 변수(Condition Variables)
  • 조건(Condition) x, y
  • 프로그래머는 하나 이상의 조건 타입 변수를 정의할 수 있다.
• 조건 변수에 적용되는 두 가지 연산
  • wait() : 연산을 호출한 프로세스는 보류
  • signal()
    • wait()를 호출한 프로세스 중 하나가 재개
    • 보류하는 프로세스가 없다면, 아무것도 일어나지 않는다.
• 연산이 발생된 이후 2가지 가능성
  • P가 signal(), Q가 wait()인 경우
    • Singal and wait : P는 Q가 모니터를 떠날 때까지 기다리거나 또는 다른 조건을 기다린다.
    • Singal and continue : Q는 P가 모니터를 떠날 때까지 기다리거나 또는 다른 조건을 기다린다.

(2) 모니터 내에서 프로세스 수행 재개

• 일시 중지되었던 프로세스 중 어느 프로세스가 수행 재개될 것인가를 어떻게 결정하는가?
• FCFS 
• Condition-wait
  • x.wait(c) 
  • wait() 연산이 호출될 때 값이 계산된다.
  • c는 우선순위 번호(priority number)