[OS] 8. 공유 자원과 임계구역

공유 자원(Shared Resource)

• 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말한다.
• 공유 자원은 공동으로 이용되기 때문에 누가 언제 데이터를 읽거나 쓰느냐에 따라 그 결과가 달라질 수 있다.
• 따라서 프로세스들의 공유 자원 접근 순서를 정하여 예상치 못한 문제가 발생하지 않도록 해야한다.
• 경쟁 조건(Race Condition)
  • 2개 이상의 프로세스가 공유 자원을 병렬적으로 읽거나 쓰는 상황
  • 경쟁 조건이 발생하면 공유 자원 접근 순서에 따라 실행 결과가 달라질 수 있다.

임계 구역(Critical Section)

• 공유 자원 접근 순서에 따라서 실행 결과가 달라지는 프로그램의 영역
• 임계구역에서는 프로세스들이 동시에 작업하면 안된다.
  • 어떤 프로세스가 임계구역에 들어가면 다른 프로세스는 기다려야 하며 임계구역의 프로세스가 나와야 들어갈 수 있다.
• 전역 변수 뿐만 아니라 하드웨어 자원을 사용할 때도 적용되는 개념이다.
  • e.g. 프린터 1대를 여러 명이 동시에 사용하는 경우 프린터는 임계구역이 된다.
• 생산자 - 소비자 문제
  • 임계구역 관련한 유명한 문제로 생산자 소비자 문제가 있다.
  • 생산자는 계속 물건을 생산해서 버퍼에 넣고, 소비자는 계속 버퍼에서 물건을 가져온다.
  • 버퍼의 크기 확인을 위해 sum 이라는 전역변수를 사용하는데, 이 때 생산자와 소비자가 동시에 실행되면 문제가 발생한다.

임계 구역 해결 조건

1. 상호 배제(Mutual Exclusion) = Mutex = Lock
   • 한 프로세스가 임계구역에 들어가면 다른 프로세스는 임계구역에 들어갈 수 없다.
2. 한정 대기(Bounded Wating)
   • 어떤 프로세스도 무한 대기(Infinite Postpone)하지 않아야한다.
   • 특정 프로세스가 임계구역에 진입하지 못하면 안된다.
3. 진행의 융통성(Progress Flexibility)
   • 한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다.

임계 구역 해결 방법

• 가장 단순한 방법은 잠금(lock)을 이용하는 것이다.
• 임계구역에 들어갈 때 잠금을 걸고, 나올 때 잠금 해제와 동시에 동기화 신호를 보낸다.
• 피터슨 알고리즘
  • 게리 피터슨(Gary Peterson)이 제안한 알고리즘
  • 변수 turn은 두 프로세스가 동시에 lock 을 설정하여 임계 구역에 못들어가는 상황에 대비하는 장치
  • 두 프로세스가 동시에 loc k을 설정했더라도 turn 을 사용하여 다른 프로세스에게 양보
  • 한계
    • 임계구역 해결의 세가지 조건을 모두 만족하지만 프로세스 수가 늘어나면 변수도 늘어나고 전체적인 알고리즘도 복잡해진다.
    • 바쁜 대기(busy waiting)를 사용하여 자원을 낭비한다. (while loop)

    // 공유 변수
    boolean lock1 = false;
    boolean lock2 = false;
    int turn = 1;
    
    // 프로세스 1
    lock1 = true;
    turn = 2;
    while(lock2 == true && turn == 2);
    /*** 임계구역 ***/
    lock1 = false;
    
    // 프로세스 2
    lock2 = true;
    turn = 1;
    while(lock1 == true && turn == 1);
    /*** 임계구역 ***/
    lock2 = false;
    

• 데커 알고리즘
  • 테오도뤼스 데커(Theodorus Dekker)가 제안한 알고리즘
  • 하드웨어의 도움 없이도 임계구역 문제를 해결할 수 있다.
  • 한계
    • 임계구역 해결의 세가지 조건을 모두 만족하지만 프로세스 수가 늘어나면 변수도 늘어나고 전체적인 알고리즘도 복잡해진다.
    • 바쁜 대기(busy waiting)를 사용하여 자원을 낭비한다. (while loop)

    // 공유 변수
    boolean lock1 = false;
    boolean lock2 = false;
    int turn = 1;
    
    // 프로세스 1
    lock1 = true;
    while(lock2 == true) {
        if(turn == 2) {
            lock1 = false;
            while(turn == 2);
            lock1 = true;
        }
    }
    /*** 임계구역 ***/
    turn = 2;
    lock1 = false;
    
    // 프로세스 2
    lock2 = true;
    while(lock1 == true) {
        if(turn == 1) {
            lock2 = false;
            while(turn == 1);
            lock2 = true;
        }
    }
    /*** 임계구역 ***/
    turn = 1;
    lock2 = false;
    

• 세마포어 알고리즘
  • 에츠허르 데이크스트라(Edsger Dijkstra)가 제안한 알고리즘
  • 데커 알고리즘과 비교하여 간단하고 사용이 쉬우며, wakeup 신호를 사용하기 때문에 바쁜 대기를 하지 않아도 된다.
  • P()와 V()의 내부 코드는 검사와 지정을 사용하여 분리 실행되지 않고 완전히 실행되게 해야한다.
  • P()나 V() 내부 코드가 실행되는 도중 다른 코드가 실행되면 상호 배제와 한정 대기 조건을 보장하지 못하기 때문이다.
  • 한계
    • 잘못된 사용으로 인해 임계구역이 보호받지 못할 수 있다.
    • 사용자가 고의로 세마포어를 사용하지 않거나 사용 중에 실수를 한 경우, 즉 직접 변수에 접근하여 조작하기 때문에 위험하다.
  • 순서
    1. 임계구역 사용전에 Semaphore(n) 로 초기화를 한다.
       • n은 공유 가능한 자원의 수를 나타낸다. 전역변수 RS를 n으로 초기화 한다.
       • 예를 들어 프린터가 1대이면 1이고, 2대이면 2가 된다.
    2. 초기화가 끝난 후 임계구역에 들어가기 전 사용중이라고 표시를 한다.
       • P(): 잠금을 수행하는 코드
       • RS가 0보다 크면(사용 가능한 자원이 있으면) 1을 감소시키고 임계구역에 진입한다.
       • RS가 0보다 작으면(사용 가능한 자원이 없으면) 0보다 커질 때 까지 기다린다.
    3. 임계구역을 나올 때 비었다고 표시한다.
       • V(): 잠금 해제와 동기화를 같이 수행하는 코드
       • RS값을 1 증가시키고 세마포어에서 기다리는 프로세스에게 임계구역에 진입해도 좋다는 wakeup 신호를 보낸다.

    Semaphore(n); // RS = n;
    
    P();
    // if RS > 0 them RS = RS - 1
    // else block()
    
    /*** 임계구역 ***/
    
    V();
    // RS = RS + 1
    // wake_up()
    

• 모니터
  • 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공하여 자원을 보호하고 프로세스간에 동기화를 시킨다.
  • 시스템 호출과 같은 개념이다.
  • 사용자 입장에서는 복잡한 코드를 실행하지 않아서 좋고 시스템 입장에서는 임계구역을 보호할 수 있어서 좋다.
  • 순서
    1. 임계구역으로 지정된 변수나 자원에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.
       • 잠금이나 세마포어를 사용하지 않고 increase() 문을 사용
       • wait(): 모니터 큐에서 자신의 차례가 올때까지 기다린다. — P()
       • signal(): 모니터 큐에서 기다리는 다음 프로세스에 순서를 넘겨준다. — V()
    2. 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.

맨 위로 이동 ↑