운영체제 - 병행제어(3)

2020-09-28

OS를 공부하면서 정리를 한 내용들 입니다.

운영체제의 동시접근과 관련된 Synchronization을 알아보았습니다.

그 다음부터는 프로세스간의 동기화 문제에 대해서 알아봅시다.

Process Synchronization 문제

  • 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있습니다.

  • 일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process)간의 실행 순서(orderly execution)를 정해주는 매커니즘이 필요합니다.

Race condition

  • 하나의 공유 데이터를 여럿이 접근하려할 때 생기는 문제를 Race Condition이라고 합니다.

  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라집니다.

  • Race condition를 막기 위해서는 concurrent process는 동기화 되어야 합니다.

The Critical-Section Problem

  • n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우

  • 각 프로세스의 code segment에는 공유 데이터를 접근하는 코드인 critical section이 존재합니다.

  • 이때의 문제는 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스가 해당 section에 들어갈 수 없어야 합니다.

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

critical section에 들어가기 전과 나오는 부분의 section에서 어떤 알고리즘을 사용해야하는가에 대해 알아봅시다.

Algorithm 1

Process P0

do{
    while(turn != 0);
    critical section
    turn = 1;
    remainder section
}while(1);

Process P1

do{
    while(turn != 1);
    critical section
    turn = 0;
    remainder section
}while(1);

P0과 P1에서 동시에 접근을 하는데 여기서 발생하는 문제를 해결하기 위해서 이 알고리즘은 어떤 방법을 쓰느냐,

turn이라는 Synchronization variable을 사용합니다.

critical section에 들어가기 전에 turn을 보면서 지금 어떤 프로세스의 차례인지 확인을 합니다.

P0의 입장에서 turn은 0이라면 본인 차례, P1의 입장에서 turn이 1이라면 본인 차례입니다.

만약 본인 차례가 아니라면 while문으로 대기를 하게됩니다.

여기서 turn을 변경하는 것은 상대방 프로세스에 의해 결정됩니다.

critical section을 거치고 빠져나갈 때 순서를 바꿉니다.(양보한다)

여기서 어떤문제가 발생하는가?

무조건 번갈아가면서 들어가야하기에, 상대방의 critical section이 끝날 때 까지 본인의 차례는 돌아오지 않습니다.

특정 프로세스가 더 빈번하게 critical section을 들어가야하는데 상대방이 critical section을 들어가지 않는다면?

영원히 차례를 기다리계 됩니다.

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

Mutual Exclusion(상호배제)

  • 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안된다.

Progress(진행)

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

Bounded Wating(유한대기)

  • 프로세스가 critical section에 들어가려고 요청한 후 부터 그 요청이 허용될 때 까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.

가정.

  • 모든 프로세스의 수행 속도는 0보다 크다.
  • 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

-참고 KOCW 이화여자 대학교 반효경 교수님 : 운영체제 강의