[KOCW] 반효경 운영체제 강의 정리 - 6. Process Synchronization 1

데이터의 접근

Race Condition

OS에서의 race condition (1/3)

• OS에서 race condition이 발생하는 경우
  1. kernel 수행 중 인터럽트 발생 시
  2. Process가 system call을 하여 kernel mode로 수행 중인데 context switch가 일어나는 경우
  3. Multiprocessor에서 shared memory 내의 kernel data

OS에서의 race condition (2/3)

OS에서의 race condition (3/3)

• multiprocessor

Process Syynchronization 문제

• 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(Inconsistency)를 발생시킬 수 있다.
• 일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)를 정해주는 매커니즘 필요
• Race condition
  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
• race condition을 막기 위해서는 concurrent process는 동기화(synchronize) 되어야 한다.

The Critical-Section Problem

• n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
• Problem
  • 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

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

• Mutual Exclution (상호 배제)
  • 프로세스 P가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.
• Progress
  • 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
• Bounded Waiting (유한 대기)
  • 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
• 가정
  • 모든 프로세스의 수행 속도는 0보다 크다.
  • 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

Initial Attempts to Solve Problem

• 두 개의 프로세스가 있다고 가정 P0, P1
• 프로세스들의 일반적인 구조

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

• 프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있다.
  • synchronization variable

Algorithm 1

• Synchronization variable

int turn;
initially turn = 0; // Pi는 Critical Section을 turn이 i일 때 들어갈 수 있다.

• Process P0

do {
    while(turn != 0); // turn을 기다림
    critical section
    turn = 1; // turn을 넘김
    remainder section
} while(1);

• Process P1

do {
    while(turn != 1); // turn을 기다림
    critical section
    turn = 0; // turn을 넘김
    remainder section
} while(1);

• 과잉양보
  • 반드시 한번씩 교대로 들어가야만 함 (swap-turn)
  • Progress 조건을 만족하지 못함
    • 특정 프로세스가 빈번하게 critical section을 들어가고 싶지만 못함

Algorithm 2

• Synchronization variable
  • boolean flag[2];
  • initially flag[모두] = false;
  • flag[i] == true일 경우 Pi는 critical section에 들어갈 수 있음
• Process Pi

do {
    flag[i] = true;
    while(flag[j]); // turn을 기다림
    critical section
    flag[i] = false; // turn을 넘김
    remainder section
} while(1);

• Progress 조건을 만족하지 못함
• 둘 다 2행까지 수행 후 끊임 없이 양보하는 상황 발생

Algorithm 3 (Peterson's Algorithm)

• Algorithm 1과 2를 혼합해서 사용
• Process Pi

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

• 3가지 조건을 모두 충족시킨다.
• Busy Waiting (계속 CPU와 memory를 쓰면서 기다린다.)

Synchronization Hardware

출처 : http://www.kocw.net/home/cview.do?lid=5cf910642999f4a5