[OS] 동기화와 Critical Section(임계구역) 문제

2020. 4. 22. 17:54ㆍProgramming/CS

임계구역 문제

Critical Section, Critical Section Problem

  • Critical Section(어떤 특정 코드가 작동하는 영역) Problem[임계구역 문제] : common variable을 update하는 구역에 생기는 문제들을 말한다. common variables 부분을 update하거나 write 하는 경우..
  • 다시한번 정리해보면 Critical Section : 하나의 시스템에는 여러개의 쓰레드(멀티 쓰레드)로 구성되어있는데, common으로 사용하는 부분이 있다. 그 부분을 업데이트 하는 부분의 코드를 말한다.
  • 예를들어, Parent 클래스에서 계좌의 balance에 접근하여 연산하고, Child클래스에서도 계좌의 balance에 접근하여 연산하는 코드가 있을 텐데, 그 코드부분을 Critical Section이라고 한다.
  • common variables의 예 : 같이 사용하는 영역의 variable, file, code, db ...

 

임계구역 문제의 Solution

  • Mutual Exclusion(상호배타) : 오직 한 쓰레드만 진입가능하게 한다.
    • ex. Parent <-> Child 둘중 하나만 들어갈수있게 한다.
  • Progress(진행) : 정해진 시간(유한 시간)내에 입장을 결정한다.
    • ex. 유한시간 내에 Parent, Child 둘 중 누가 먼저 들어갈것인지를 결정한다.
  • Bounded Waiting(유한 대기) : 어떤 스레드라도 기다리고있다면 유한 시간 내에는 꼭 Critical Section안에 들어갈 수 있어야한다.

이 세가지가 전부 만족되어져야 Critical Section Problem을 Solution 할 수 있다.

 

 

프로세스/쓰레드의 동기화

  • 임계구역 문제 해결(Mutual Exclusion, Progress, Bounded Waiting) : 틀린답이 나오면 안됨
  • 프로세스 실행 순서 제어 : 원하는대로 실행순서를 제어할 수 있어야한다
  • Busy wait 등 비효율성은 제거 나중에 더 추가로 나올예정

 

 

✏️현재까지의 정리

OS는

  1. Process Management
    • CPU Scheduling : ex. FCFS, RR, SJF ...
    • Synchronization : for 임계구역문제 해결, 프로세스 실행순서 제어, 비효율성 체크
  2. Main Mem Management
  3. File System
  4. I/O

를 해야한다고 배웠다.
그런데, 동기화이야기가 갑자기 왜 나오냐 ?!?

 

컴퓨터의 자원은 한정되어있고, cpu에서만 작업을 처리할 수 있다.

메모리에서는 기다리고있었다가, 작업 처리를 대기할뿐. 하지만 컴퓨터 작업은 최대한 빨리 처리되는게 좋기 때문에, Synchronization 을 통해 (ex. TSS도 그렇고) 프로세스를 처리시키고 아웃시키고 다시들어오게하고.. 너무 작업이 길어진다면 내쫓기도 하고.. 하는데 그때 그 자원/데이터의 효율적인 처리를 하기위해, 상호 독립적으로 프로세스를 처리하기 위해서 필요한 개념이 Synchronization이다.

 

그래서 아주 빠른 시간내에 빠른 switching & process 가 일어나는 Sync로 인하여, 서로의 상태를 주시하며 코드가 서로 간섭하지 않게 하려면 임계구역문제를 해결해야하고, 프로세스의 실행 순서를 제어할수있게 해야하고 비효율성을 체크해야한다는 것이다.

 

그렇다면 그 동기화를 어떻게 꼬이지 않게 할수있는건지, Synchronization Tools에 대해 한번 알아보자.

 

 

동기화 도구(Synchronication Tools)

  • Semaphores
  • Monitors ex. JAVA에서 많이 씀

가 있다. 그중에서, 동기화를 의미있게. 가능케하는. 몇가지 Tools를 알아보자.

 

Semaphores (세마포)

  • 동기화 문제 해결을 위한 sw 도구
  • 쉽게말하면 A class와 B class둘이부모자식관계가아닐수도있음가 Critical Section을 가질 경우(공통된 common variables를 가지고있을경우) A class 가 들어가면 B 클래스를 들어가지 못하게 하는 개념이다
  • 구조 : 정수형 변수 + P, V동작(2가지 mode)
    • P : 정수값을 검사한다. test -> acquire() 
      void acquire() {
    value--;
    if(value < 0) {
        add this process/thread to list; // 어떤 프로세스나 쓰레드가 acquire()을 실행시키면 list(queue)에 집어넣고
        block; // 누가 꺼내기 전까지는 멈춰있는다
    }
}
    • V : 정수값을 증가시킨다. increment -> release() 
      void release() {
    value++;
    if(value <= 0){
        remove a process P from list; // 어떤 프로세스나 쓰레드가 release()를 실행시키면 list(queue)에서 뺄것이다
        wakeup P; // Queue(list)에서 해방시킨다
    }
}
    • 마치 스택에서 push, pop 을 하듯 release, acquire가 있다고 생각하면 편할듯 하다.

시나리오를 한번 그려보자.

Parent, Child 클래스 내부에 balance에 접근하는 연산코드가 있다.

  1. Parent가 접근하는 동안에는 Child는 접근을 금지시키려한다.
  2. 그러면 p.acquire() -> balance연산 -> p.release() 순서로 코드 사용이 되는데
  3. 그떄 release에서 value++;하게되고
  4. child가 해당 영역(Critical Section)의 코드를 사용하려고 하면, (c.release() -> balance연산 -> c.acquire()가 진행되려고 할 때)
  5. child는 release() 연산에서 if에서 걸려서, process/thread 가 queue(list)에 대기하게된다.

Sync되게 사용할 경우 (쓰레드 겁나 빨ㄹ리 스위칭하는경우) 지연시간이 있으니까, context switching이 이루어지면서 Critical section 문제를 해결할 수 없었는데 Semaphore를 사용함으로써 Critical Section Problem을 해결!!

실제로 Semaphore docs를 읽어보면 exception 처리 (sw interrupt)를 하는 코드가 실제로 써있다. acquire시 try catch로 막아버림. 그래서 지연시간이 길던 짧던, 정확한 결과를 가져올 수 있는것이다. Critical Section 에서 서로 간섭할 수 없도록 만든게 세마포.

 

 

 

기타 전통적 동기화 문제

 

생산자-소비자 문제

(Producer-Consumer Problem)

생산자가 데이터를 생산하면 소비자는 그것을 소비한다. 예를들어
소스코드를 -> compiler(생산자)가 어셈블리 코드로 만들어 -> 어셈블러(소비자)가 기계어로 만들어.. 이 번역 과정을 거쳐서 가는 전체 과정에서도 생산자-소비자를 이야기할 수 있다.

위와같은 맥락으로 생산자>소비자 : 컴파일러 > 어셈블러, 파일서버 > 클라이언트, 웹서버 > 웹클라이언트 등의 예가 존재한다.

producer processor가 -> buffer에 저장Bounded Buffer -> consumer가 바로 소비하는 과정을 거친다. 여기서 Bounded Buffer는 다음과같은 특징을 가진다.

  • 생산된 데이터는 일단 버퍼에 저장한다
  • 현실 시스템에서 버퍼의 크기는 유한하다(Bounded 라는 뜻!)
  • 생산자는 버퍼가 가득 차면 더 넣을 수 없다.
  • 소비자는 버퍼가 비면 소비할 수 없다.
class Buffer {
    int[] buf;
    int size;
    int count; // Bounded Buffer에 들어가있는 개수
    int in; // Buffer을 in(초깃값 : 0)
    int out;
    Semaphores mutex; // import java.util.concurrent.Semaphores

    Buffer(int size) {
        buf = new int[size]; // Bounded Buffer(유한 크기)
        this.size = size;
        count = in = out = 0;
        mutex = new Semaphore(1);
    }
}

void insert(int item) {
    while(count == size){
        // buffer is full
    }

    //////////// Critical Section /////////////////
    mutex.acquire(); // 세마포

    buf[in] = item;
    in = (in+1)%size;
    count++;

    mutex.release(); // 세마포
    ///////////////////////////////////////////////
}

void remove() {
    while(count == 0){
        // buffer is empty
    }
    //////////// Critical Section /////////////////
    mutex.acquire();

    int item = buf[out];
    out = (out+1)%size;
    count--;

    mutex.release();
    ///////////////////////////////////////////////
    return item;
}

class Producer extends Thread {
    Buffer b;
    int N;
    Producer(Buffer b, int N) {
        this.b = b;
        this.N = N;
    }
    public void run() {
        for(int i=0 ; i<N ; i++) b.insert(i);
    }
}

class Consumer extends Thread {
    Buffer b;
    int N;
    Consumer(Buffer b, int N) {
        this.b = b;
        this.N = N;
    }
    public void run() {
        for(int i=0 ; i<N ; i++) item = b.remove();
    }
}

class Test {
    public static void main(String[] arg){
        Buffer b = new Buffer(100);
        Producer p = new Producer(b, 10000); // 생산해서 넣고.. 10000번 반복
        Consumer c = new Consumer(c, 10000); // 10000번 소비
        p.start();
        c.start();
        try {
            p.join();
            c.join();
        } catch (InterruptedException e) {}
        System.out.println("Number of items in the buffer is " + b.count); // buf 몇개 남았는가. 정상적으로 동작했다면 0이 나와야 정상.
        // 동기화가 되지 않으면 0이 나오지 않음
    }
}

이 예제에서 Semaphore처리부분을 제거한다면 잘못된 결과가 나온다. count !=0이거나, 심지어 실행이 되지 않는 경우도 존재한다.

여기서는 binaty Semaphore을 예시로들고있다. 참고로 세마포와 Lock은 작ㄱ동 원리가 반대이다.

 

❓ 원인은?

  • Critical Section Problem 떄문이다. 공통변수 업데이트 구간(임계구역)에 대한 동시 진입이 있기 때문이다. => buffer를 바꾸는 도중에 switching이 일어나기 때문.
  • 공통변수 count, buf[] 에 대해 동시에 업데이트 하려고 해서 생기는 문제
  • atomic instruction이 아니기 때문에 == 인터럽트가 발생될 가능성이 아주 낭낭!하다 == context switching 이 발생할 수 있고 == 동시 접근을 허용하게될수도 있다 는 파생되는 여러가지 문제점이 생길수있는 것이다.

❗️Solution

  • Critical Section 안에 Producer 가 들어가면 Consumer는 절대 들어가지 못하도록, 세마포를 사용하여 Producer: 10000번 도는동안 연산들어갈때 mutex.acquire();, 나오면서 mutex.release(); mutex는 mutual exclusion의 약자, rel; Consumer: 10000번 도는동안 들어가면서 mutex.acquire();, 나오면서 mutex.release(); 해주어 mutual exclusion하도록 처리해주어야한다.

  • buffer가 꽉차면 세마포 감옥에 가두어버리고, block 되어버린다.

그렇다면, 위같은 Critical Section Problem이 존재하는 value++등의 연산을 해주기 전에 single CPU일 때 사용하는 방법같이 lock()을 해주는 방법으로 막아버리는 방법이 존재하는데 그렇게 lock() 해주면 busy waiting한다고 한다. (사실 이는 짧은 Critical Section에만 사용하는게 좋다고 한다. 왜냐면, 그 임계영역이 길어질수록 오랫동안 busy-waiting을 해야하기 때문이다.)

 

Busy-wait

인 상황이라면, 생산자와 소비자는 각각

  • Producer : Buffer가 가득 차면 기다려야함 = empty 공간이 있어야함
  • Consumer : Buffer가 비면 기다려야함 = full 공간이 있어야함

이런 동작을 해야한다. 세마포를 이용해 busy-wait을 회피해보자. 아래의 코드는 개념을 정리하기에 좋고 굉장히 중요하니 설명할 수 있어야한다. Semaphore 형 변수를 empty, full, mutex 세가지로 사용하는 경우이다.

  • Producer : empty.acquire() full.release()// defaultVal = BUF_SIZE
  • Consumer : full.acquire() empty.release()// defaultVal = 0

Producer가 꽉찼으면 Consumer에게 하나 빼주라고, 그래야 내가 넣을수있다!! 하는 꺠워주는 작업이 필요하다. 그래서 소비자가 empty.release() 해주면 Producer가 깨어나서 이제 다시 들어가게해줌.

 

Readers Writers Problem

데이터베이스를 공통으로 사용하기떄문에, 문제들이 생긴다.

  • Readers : 오직 읽기만 Able, 수정 Unable
  • Writers : 읽기 Able 수정 Able

보통 공통으로 접근해서 생기는 문제를 해결하기위해서는 DB접근 자체를 Critical Section으로 만들어 두면 되지만, 보통의 경우처럼 한번에 한개의 프로세스만 접근을 허용하게 하는 것은 굉장히 비효율적이다.

특히나, Reader가 1명 들어오건 100명 들어오건 내용이 변화할 일은 없기 때문에 Reader는 상관이 없다. 그렇기때문에 한 Reader가 들어가면 Writer는 못들어오게 하되, 다른 Reader들은 들어올 수 있게 해줘야한다.

이러한 R/W들이 들어와서 생기는 problem을 case로 나누어보면 다음과같은 경우들이 존재한다.

  • First R/W problem (readers-preference) : 항상 Reader에게 우선권을 주고, Writer가 미루어지는 경우
  • Second R/W problem (writers-preference) : 항상 Writer에게 우선권을 주고, Reader가 미루어지는 경우
  • Third R/W problem : 아무에게도 우선권을 주지 않는 경우

 

Dining Philosopher Problem

5명의 철학자, 5개의 젓가락1짝으로 각각의 철학자가 식사할수있는경우를 따진다. 철학자는 항상 식사를 하거나 생각을 한다. 이러한 문제를 프로그래밍으로 생각해보면,

  • 철학자 : Thread
  • 젓가락 : 각각이 semapho(# innitialValue = 1)
  • 젓가락을 드는 순서: 왼쪽 acquire -> 오른쪽 acquire -> 식사 -> 왼쪽 relieve -> 오른쪽 relieve -> 생각 -> 왼쪽 acq... 으로 정형화한다.

위 경우를 코드로 작성하면, 계속 무한히 반복할 경우 어느정도 실행되다가 중지된다. 바로 deadlock(교착상태-암것도못함) 동기화 문제 떄문이다.

이런경우를 생각해야함

. 이 상황에서는, 모든 철학자들이 식사하려고 왼쪽 젓가락을 acquire 하였을 경우가 바로 문제가 되는 것이다.

한번 다시 정리를 해보자.

  • OS에서 가장 중요한게 프로세스 관리
  • 프로세스 관리에는 크게 CPU 스케쥴링, 프로세서 Synchronization(동기화) 가 있었다
  • 프로세스 동기화를 정상 동작하게 하기 위해서 해결해야 하는 문제들이 있는데, 크게는 임계구역문제 해결, 프로세스 실행순서 제어, 비효율성 체크
  • 특히나 동기화에서는 위의 방식을 사용하던, 사용하지 않던 교착상태(Deadlock)에 빠지게 되는 경우가 분명히 존재한다.
저작자표시 비영리 변경금지

'Programming > CS' 카테고리의 다른 글

[OS] Monitor(모니터)  (0) 2020.04.25
[OS] Deadlock (교착상태)와 Deadlock 처리  (0) 2020.04.24
[OS] Thread와 프로세스 동기화  (0) 2020.04.20
[OS] 프로세스의 생성과 종료  (0) 2020.04.19
[OS] CPU Scheduling 알고리즘, 평가 척도  (0) 2020.04.11

관련글

댓글 0

티스토리툴바