공유된 자원에 여러 프로세스들이 동시에 접근했을 경우 데이터 무결성에 문제가 발생할 수 있다.

이러한 문제를 해결하기 위해 동기화(Synchronization) 개념이 도입되었다. 즉 공유 데이터에 대하여 동시에 접근하려 할 때, 처리 순서에 상관없이 원하는 결과를 얻기 위함이다. 이를 데이터 일관성(Data Consistency)라고 한다.

1. 경쟁 상태(Race Condition)

• 공유된 자원에 대해 여러 프로세스가 동시에 접근을 시도할 때, 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태를 의미한다.

  • 동시에 접근할 때 데이터의 일관성을 해치는 결과가 나타날 수 있음.

• OS에서 Race Condition이 발생하는 경우 세 가지

  1. 커널 안의 코드를 수행하는 중 인터럽트가 발생하는 경우

     

     • 커널 안에 있는 변수를 증가시키는 중 인터럽트가 발생하고 인터럽트 처리 함수에서 해당 변수를 감소시킬 때 변수의 결과값에 문제가 생김.
     • 사용자 프로세스는 해당 프로세스의 할당받은 메모리에만 존재할 수 있지만 커널은 서로 다른 프로세스가 공유하기 때문에 발생한다.
     • 해결법: 작업을 할 때 인터럽트가 발생하더라도 작업이 완료된 후 인터럽트가 발생하도록 처리 순서를 부여한다.

  2. 프로세스가 시스템 콜을 호출하여 커널 모드로 수행 중일 때 문맥교환이 발생하는 경우

     

     • 사용자 프로세스가 시스템 콜을 호출하면 커널 모드로 커널 안에 존재하는 변수를 수정할 수 있다. 할당된 CPU 사용기간이 만료되면 문맥교환이 발생하는데 새롭게 CPU를 할당받은 사용자 프로세스가 이전 프로세스와 동일한 시스템 콜을 호출하여 수정하고 있던 변수에 대한 작업을 수행할 때 결과적으로 변수 값에 문제가 발생하는 경우
     • 해결법: 사용자 프로세스가 시스템 콜을 호출하여 커널 모드의 작업을 완료한 후 종료될 때 문맥교환이 발생할 수 있게 한다. 즉, 커널 모드에 있다면 CPU 제어권을 빼앗지 않는다.

  3. 여러 프로세스의 공유 메모리 내의 커널 데이터에 접근하는 경우

     

     • CPU가 여러 개인 시스템에서 공유 메모리 속 데이터를 여러 프로세스가 접근할 때 발생하는 경우
     • 해결법: 커널 안 데이터에 접근할 때 lock/unlock을 걸어 매 순간 데이터에 접근하는 프로세스는 1개로 한정한다.

2. 임계영역 문제(The Critical-Section Problem)

• 임계영역이란 OS에서 여러 프로세스가 데이터를 공유하면서 수행될 때, 각 프로세스에서 공유 데이터를 액세스하는 프로그램 코드 부분을 의미한다.

  • 공유 자원의 독점을 보장해주는 역할을 수행함.

• 임계영역 문제를 해결하기 위한 기본 조건 세 가지

  1. 상호 배제(Mutual exclusion)

     • 어떤 프로세스가 임계영역에서 실행 중이라면, 다른 프로세스는 임계영역에 접근할 수 없다.

  2. 진행(Progress)

     • 임계영역에서 실행 중인 프로세스가 없다면, 다른 프로세스가 접근할 수 있도록 한다.

  3. 한정된 대기(Bounded Waiting)

     • 다른 프로세스의 기아(Starvation)를 방지하기 위해, 한번 임계영역에 들어간 프로세스는 다음 번 임계영역에 들어갈 때 제한을 두어야 한다.

3. 피터슨의 해결안(Peterson's Solution)

• 임계영역 문제를 해결하는 기본 조건 세 가지를 충족하는 고전적 SW 기반 해결책으로 피터슨의 해결안이 있다.

  • 이 해결방안은 임계영역과 나머지 영역을 오가며 실행하는 두 개의 프로세스로 한정한다.

  • 두 프로세스는 아래의 두 데이터 항목을 공유한다.

    int turn; //임계영역으로 진입할 순번
    boolean flag[2]; //프로세스가 임계영역으로 진입할 준비 되었음을 의미

  • turn == i 이면 프로세스 Pi가 임계영역으로 실행될 수 있고 flag[i]가 true이면 Pi가 임계영역으로 진입할 준비 됨을 의미한다.

  • 프로세스 Pi의 실행 구조

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

    1. flag[i] = true에 의해 프로세스 Pi는 임계영역에 들어갈 준비가 됐다는 것을 알려주고 turn = j에 의해 프로세스 Pj가 실행될 차례라는 것을 알려줌.
    2. flag[j] = true이고 turn == j 이면 프로세스 Pj가 임계영역에 들어갈 차례이므로, Pi는 무한 루프에 들어가 기다리게 됨.
    3. 프로세스 Pj가 임계영역 작업을 마치고 flag[j] = false가 되면, 프로세스 Pi는 무한루프를 빠져나와 임계영역에 들어가게 됨.
    4. 프로세스 Pi가 작업 완료 후 flag[i] = false로 설정하면, 다른 프로세스가 임계영역을 사용할 수 있게 됨.

• 피터슨의 해결안이 세 가지 조건을 만족하는지 확인해보자.

  1. 상호 배제

     • flag와 turn을 이용해 한 개의 프로세스만 임계영역에 접근할 수 있도록 하였다.

  2. 진행

     • 하나의 프로세스가 임계영역에서 빠져나오면서 flag를 false로 만들어 버리고 다른 프로세스가 접근이 가능하도록 한다.

  3. 한정된 대기

     • 마찬가지로 하나의 프로세스가 임계영역을 빠져나오며 flag를 false로 만드니 다른 프로세스가 실행될 기회가 적어도 한번은 주어지게 된다.

• 피터슨의 알고리즘의 문제점은 while (flag[j] && turn == j); 부분이다.

  • 이 무한루프에 CPU 자원을 쓰고 있다보니 운영체제가 CPU를 효율적으로 활용하지 못하여 문제가 발생하는데 이를 Busy waiting이라고 한다.

4. 세마포어(Semaphore) & 뮤텍스(Mutex)

세마포어와 뮤텍스는 공유 자원 관리를 위해 상호 배제를 달성하는 기법들이다.

1. 세마포어(Semaphore)

• 세마포어는 멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법으로 현재 공유 자원에 접근할 수 있는 쓰레드, 프로세스의 수를 나타내는 값을 두어 상호 배제를 달성하는 기법이다.

• 세마포어 P, V 연산

  • P: 임계영역 들어가기 전에 수행 (프로세스 진입 여부를 자원의 개수(S)를 통해 결정)
  • V: 임계영역에서 나올 때 수행 (자원 반납 알림, 대기 중인 프로세스를 깨우는 신호)

  • 구현 방법

    P(S);
    //critical section
    V(S); 

    procedure P(S)
    	while S=0 do wait
    	S := S-1
    end P
    
    procedure V(S)
    	S := S+1
    end V

  • 흐름

    최초 S값은 1이고, 현재 해당 구역을 수행할 프로세스가 A, B 있다고 가정한다. (2개 이상도 가능)

    1. 먼저 도착한 A가 P(S)를 실행하여 S를 0으로 만들고 임계영역에 들어감
    2. 그 뒤에 도착한 B가 P(S)를 실행하지만 S가 0이므로 대기 상태
    3. A가 임계영역 수행을 마치고 V(S)를 실행하면 S는 다시 1이 됨
    4. B는 P(S)에서 while문을 빠져나올 수 있고, 임계영역으로 들어가 수행함.

2. 뮤텍스(Mutual Exclusion)

• 임계영역을 가진 쓰레드들의 실행시간이 서로 겹치지 않고 단독으로 실행되게 하는 기술로 해당 접근을 조율하기 위해 lock과 unlock을 사용한다.

  • lock: 현재 임계영역에 들어갈 권한을 얻어옴 (만약 다른 프로세스/쓰레드가 임계영역 수행 중이면 종료할 때까지 대기)
  • unlock: 현재 임계영역을 모두 사용했음을 알림 (대기 중인 다른 프로세스/쓰레드가 임계영역에 진입할 수 있음)

• 구현 방법

  lock();
  // critical section
  unlock();

  mutex = 1;
  
  void lock() {
  	while (mutex != 1) {
  	}
  	mutex = 0;
  }
  
  void unlock() {
  	mutex = 1;
  }

세마포어와 뮤텍스의 차이

• 세마포어는 공유 자원에 세마포어의 변수만큼의 프로세스, 쓰레드가 접근할 수 있다. 반면, 뮤텍스는 오직 1개만의 프로세스, 쓰레드만 접근할 수 있다.
• 현재 수행 중인 프로세스가 아닌 다른 프로세스(wait 하지 않는 프로세스)가 세마포어를 해제할 수 있다. 반면, 뮤텍스는 lock을 획득한 프로세스가 반드시 unlock 해야 한다.
• 세마포어는 뮤텍스가 될 수 있지만 (S = 1인 경우), 뮤텍스는 세마포어가 될 수 없다. 뮤텍스를 상태가 0, 1 두 개인 이진 세마포어로 부르기도 한다.

세마포어와 뮤텍스의 단점

• Busy waiting이 발생한다.

• 세마포어의 경우 큐 or 리스트를 활용하여 Busy waiting을 해결하는 방법이 있다고 한다.

  • 임계영역 진입을 위해 무한루프를 돌며 대기하는 것 대신, 프로세스를 중지시키고 큐에 넣는다.
  • S ≤ 0 이면 waiting하는 프로세스를 중지시키고 waiting queue에 넣는다.
  • 어떤 프로세스가 임계영역에서 나오면 signal() 로 대기 큐에 있는 프로세스를 waiting queue에서 빼고 깨워 ready queue에 넣는다.

5. 동기화 문제들

• 유한 버퍼 문제(bounded-buffer problem)

  • 여러 개의 프로세스를 어떻게 동기화할 것인가에 관한 고전적인 문제
  • 유한한 개수의 데이터를 임시로 보관하는 버퍼에 여러 명의 생산자들과 소비자들이 접근하는 것.
  • 생산자는 데이터가 생기면 버퍼에 저장하는데 저장할 공간이 없는 문제가 발생할 수 있음
  • 소비자는 데이터를 가져가는데 소비할 데이터가 없는 문제가 발생할 수 있다.
  • 세마포어 등으로 해결 가능

• Readers-Writers 문제

  • 여러 명의 Reader와 Writer들이 하나의 저장 공간(버퍼)을 공유하며 이를 접근할 때 발생하는 문제.
  • 세마포어 등으로 해결 가능

• 식사하는 철학자들 문제

  • 여러 프로세스에게 제한된 자원을 할당하는 상황에서 발생할 수 있는 문제.
  • 각각의 철학자들이 동시에 자신의 왼쪽에 있는 젓가락을 드는 경우 Deadlock과 Starvation이 발생할 수 있음.
  • n명이 앉을 수 있는 테이블이면 n-1명만 앉게 하여 자원의 개수를 더 많이 두거나 한 철학자가 젓가락 두 개를 모두 집을 수 있을 때만 젓가락을 집는 것을 허용하도록 하거나 누군가는 왼쪽 젓가락을 먼저 잡지 않고 오른쪽 젓가락을 먼저 잡게 하여 해결하는 방법 등이 있다.

참고링크

• https://hibee.tistory.com/297
• https://dduddublog.tistory.com/25