[OS] Critical Section 📌

공유 자원 (Shared resource)

여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일 등을 말한다

공유 자원은 공동으로 이용되기 때문에 누가 언제 어떻게 데이터를 읽거나 쓰거나에 따라 그 결과가 달라질 수 있다

 

 

 

경쟁 조건 (race condition)

2개 이상의 프로세스가 공유 자원을 병행적으로 읽거나 쓰는 상황을 말하며, 공유 자원 접근 순서에 따라 실행 결과가 달라지는 상황을 말한다

즉, 타이밍이나 순서 등이 결과 값에 영향을 줄 수 있는 상태를 말한다 -> 동시성 문제

 

 

 

Critical Section (임계 영역)

• 임계구역 또는 공유변수 영역이라고 불린다
• 이는 병렬 컴퓨팅에서 둘 이상의 스레드가 동시에 접근해서는 안되는 공유 자원(자료 구조 또는 장치)을 접근하는 코드의 일부를 말한다
• 공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 코드 영역으로, critical section 안에서 race condition이 발생하는 것이다
• critical section은 지정된 시간이 지난 후 종료된다
• 따라서 어떤 스레드(태스크 또는 프로세스)가 임계 구역에 들어가고자 하면, 지정된 시간만큼 대기해야 한다
• 스레드 공유자원의 배타적인 사용을 보장받기 위해 임계 구역에 들어가거나 나올 때는 세마포어 같은 동기화(synchronized) 매커니즘이 사용된다

 

 

 

 

cirtical section의 특징

• 공유 자원의 독점을 보장해주는 역할을 수행한다
• 커널 객체를 사용하지 않아서 빠르고 효율적이다
• 일반 동기화 객체와 달리 개별 프로세스의 유저(user) 메모리 영역에 존재하는 단순한 구조체이다
• 서로 다른 프로세스 간에 접근이 불가능하기 때문에 한 프로세스에 속한 스레드 간 동기화에만 사용한다
• 내부적으로 인터락 함수를 사용한다
• 커널 오브젝트를 사용하지 않기 때문에 핸들을 사용하지 않고, CRITICAL_SECTION 이라는 타입을 정의하여 사용한다

 

 

💡 critical section vs mutex vs semaphore
- critical section : 사용자 객체를 사용하며, 커널 객체가 아니므로 가볍고 빠르다. 그러나 한 프로세스 내의 쓰레드 사이에서만 동기화가 가능하다. 보통의 경우 가볍고 쉽게 쓸 수 있는 동기화 객체이다
- mutex : 커널 객체를 사용한다. 크리티컬 섹션보다 무겁다. 크리티컬 섹션이 한 프로세스 내의 쓰레드 사이에서만 동기화가 가능한 반면, 뮤텍스는 여러 프로세스의 스레드 사이에서 동기화가 가능하다. 뮤텍스를 가장 흔히 사용하는 예가 프로세스 다중 실행을 막을 때로, 이런 기능은 critical section으로 불가능하다
- semaphore : 커널 객체를 사용한다. 뮤텍스는 동기화 함에 있어서 동시에 하나의 쓰레드만 실행되게 하는 반면, semaphore는 지정된 수만큼의 스레드가 동시에 실행되도록 동기화하는 것이 가능하다. 지정된 수보다 작거나 같을 때까지 쓰레드의 실행을 허용하고, 지정된 수를 넘어서 쓰레드가 실행되려 하면 실행을 막는다

 

 

 

코드의 구역

각 프로세스는 자신의 임계 구역에 진입하려면 진입 허가를 요청해야 한다

이런 요청을 구현하는 코드 부분을 입장 구역(entry section)이라고 한다

입장 구역에서 기다리다가 진입 허가가 나면 임계 구역(critical section)에 들어간다

임계 구역 이후에는 임계 구역을 빠져나왔음을 알리는 코드 부분인 퇴장 구역(exit section)이 있다

또한 그 밖의 나머지 코드 부분들을 총칭하여 나머지 구역(reminder section)이라고 한다

do {
	wait(mutex);	// 입장구역
    
    // 임계 구역
    
    signal(mutex);	// 퇴장 구역
    
    // 나머지 구역
}

 

 

 

 

임계 구역 문제

• 임계 구역 문제란 임계 구역으로 지정되어야 할 코드 영역이 임계 구역으로 지정되지 않았을 때 발생할 수 있는 문제를 말한다
• 관련 문제로는 입출금 문제, 생산자-소비자 문제, 독자-저자 문제 등이 있다

 

 

 

 

생산자-소비자 문제 (producer-consumer problem)

critical section에 관련된 전통적인 문제로 생산자-소비자 문제가 있다

여기서 생산자 프로세스와 소비자 프로세스는 서로 독립적으로 작업을 한다

생산자는 말 그대로 계속 물건을 생성해서 버퍼에 넣고, 소비자는 계속해서 버퍼에서 물건을 가져온다

 

• 가운데에는 buf라는 원형 큐 자료구조가 존재하고, producer는 값을 넣어준다.
• sum은 큐의 원소 수에 해당한다. 
• consumer은 큐의 원소를 빼낸다. 
• producer는 원소를 맨 뒤부터 차근차근 넣지만 consumer는 맨 앞부터 차근차근 빼낸다.
• 겉으로 보기에는 문제가 없는 것 같지만 producer, consumer 둘이 같이 동시에 실행되면 문제가 발생한다.
• 생산자와 소비자가 전역 변수 sum에 접근하는 타이밍을 서로 맞추지 않기 때문이다.
• 즉, sum이 바로 critical section이며 race codition이 발생하는 것이다.

 

발생 예시

1. 현재 sum은 3이다.
2. producer가 buf에 물건을 하나 추가한다. 그러나 sum을 아직 안바꾸었다. 현재 sum은 3이다.
3. consumber가 buf에서 물건을 하나 소비한다. sum을 2로 바꾸어야하는데 아직 바꾸지 않았다. 현재 sum은 3이다.
4. 이 상태에서 sum = sum + 1과 sum = sum - 1```이 동시에 실행되는 문제가 생긴다.
5. 만약 sum = sum + 1이 먼저 실행되면 4가 되고, sum = sum - 1을 하면 sum은 2가 된다. 왜냐하면 2번에서의 sum은 4가 아니라 3이기 때문이다.
6. 만약 sum = sum - 1이 먼저 실행되면 2가 되고, sum = sum + 1이 실행되면 4가 된다. 1번 에서의 sum은 3이기 때문이다.

 

 

 

임계 구역 문제 해결 조건

임계 구역 문제를 해결할 수 있는 방법은 다음 3가지 조건을 만족해야 한다

 

1. 상호 배제 (mutal exclusion)

• 하나의 프로세스가 임계 구역에서 실행되고 있다면, 다른 프로세스들은 임계 구역에서 실행될 수 없다

 

2. 진행의 융통성 (progress flexibility, progress)

• 임계 구역에 실행되고 있는 프로세스가 없을 경우, 들어갈 프로세스를 적절히 선택해줘야 한다

 

3. 한정된 대기 (bounded waiting)

• 프로세스의 기아를 방지하기 위해, 한 번 임계 구역에서 실행될 프로세스는 다음 실행에 대한 제한을 두어야 한다

 

 

임계구역 해결 방법

임계 구역 문제를 해결하는 단순한 방법은 Lock을 사용하는 것이다

즉, 한 프로세스가 critical section에 들어간다면 lock을 걸어 놓아 다른 프로세스가 들어오지 못하게 하는 것이다

그리고 프로세스가 critical section에서 빠져나오게 되면 lock을 해제하고 동시에 동기화 신호를 보내는 것이다

동기화 신호는 다음 프로세스에게 critical section을 사용해도 좋다는 신호를 주는 것이다

 

임계 구역 문제를 해결하기 위한 3가지 조건(상호 배제, 한정 대기, 진행의 융통성)을 모두 만족하는 lock, unlock, 동기화 구현 방법이다

 

 

상호 배제 문제(mutal exclusion)

해당 예제는 IPC 방법으로 shared memory를 사용하는 것과 같다

lock을 통한 상호 배제 문제 해결

• (공유 변수 boolean lock은 shared memory에 있는 변수이다)
• 프로세스 p1과 p2는 임계구역에 진입하기 전에 코드를 통해 임계 구역에 잠금이 걸려있는 지 확인한다
• 만약 lock이 true라면 잠금 상태로 다른 프로세스가 임계 구역에서 작업을 하고 있다는 뜻이므로 잠금이 해제될 때까지 무한 루프를 돌면서 기다린다
• 임계 구역에 있는 프로세스가 작업을 마치고 잠금을 해제하면 lock==false가 되기 때문에 기다리고 있던 프로세스는 무한 루프에 빠져나와 작업을 수행한다
• 즉, lock==false 는 임계 구역을 사용할 수 있다고 다른 프로세스에 보내는 동기화 신호이다
• 잠금이 풀려서 새로 임계 구역에 진입하는 프로세스는 다른 프로세스가 진입하지 못하도록 잠금을 걸고 (lock=true) 작업을 하며, 작업을 마치면 다른 프로세스가 사용할 수 있도록 잠금을 해제(lock=true)한다

 

그러나 해당 방법은 아래와 같은 상황에서 문제가 발생한다

상호 배제 시 발생 가능한 문제 상황

위 그림에서 임계 구역에 진입한 프로세스가 없고, 아래의 순서대로 실행된다고 하자

1. 프로세스 p1은 while(lock==true); 문을 실행한다
   • 이 때 임계 구역에 프로세스가 없기 때문에 무한 루프를 빠져 나온다
   • 이어서 다음 문장을 실행하려는 순간 자신에게 주어진 CPU 시간을 다해(timeout) ready 상태로 옮겨진다
   • context switching이 발생하고 프로세스 p2가 running 상태로 바뀐다
2. 프로세스 p2는 while(lock==ture); 문을 실행한다
   • 아직 프로세스 p1이 잠금을 걸지 않았기 때문에 lock은 여전히 fale이며 프로세스 p2는 임계 구역에 진입할 수 있다
3. 프로세스 p1은 lock=true; 문을 실행하여 임계 구역에 잠금을 걸고 진입한다
4. 프로세스 p2도 lock=true; 문을 실행하여 임계 구역에 잠금을 걸고 진입한다
5. 결국 두 프로세스 모두 임계 구역에 진입하게 된다

 

프로세스 p1은 while(lock=true); 문을 실행하고 나서 곧바로 lock=true 문을 실행해야 다른 프로세스가 임계 구역에 들어오는 것을 막을 수 있다

그러나 프로세스 p1이 lock=true; 문을 실행하기 전에 프로세스 p2가 while(lock=true);문을 실행하면 둘 다 임계 구역에 진입하게 된다

결국 위 그림과 같은 상황의 경우, 상호 배제 조건(Mutual Exclusion)을 보장하지 못한다

또 다른 문제는 잠금이 해제되기 전까지 busy waiting이 발생한다는 것이다

바로 whlle(lock=true); 문 부분에서 작업을 할 필요가 없는 시간에도 계속 무한 루프를 돌면서 시스템 자원을 낭비한다

 

 

 

한정 대기 문제 (bounded waiting)

위에서 발생한 mutal exclusion 문제를 해결하기 위해 lock을 2개를 두기로 하자

이전에는 lock을 두 프로세스가 공유하였기 때문에 문제가 발생했던 것이다

따라서 각 프로세스가 자신들만의 lock을 가지고 있도록 하는 것이다

 

예를 들어 이전에는 화장실에 들어가서 문을 잠그는 것을 까먹고 있다가 다른 사람도 화장실에 들어가고 나서 둘이서 같이 문을 잠그고 같은 변기를 사용하는 것이다 (?)

그래서 이번에는 두 사용자에게 화장실 문을 잠글 수 있는 각자의 키를 주는 것이다

먼저 내가 문을 잠가놓고 들어가버리면, 잠가놓는 걸 까먹는 일이 없기 때문에 상호 배제 문제가 발생하지 않는다

 

프로세스 p1은 임계 구역에 진입하기 전에 먼저 잠금을 설정하고(lock1=true;), 프로세스 p2가 잠금을 설정했는지 확인한다 (while(lock==true);)

만약 잠금을 설정하지 않았다면 임계 구역에 진입하여 작업을 마친 후 잠금을 해제한다 (lock1=false;)

프로세스 p2도 같은 방식으로 임계 구역에 진입한다

위 코드는 일단 잠금을 하고 다른 프로세스가 잠겼는지 확인하므로 두 프로세스의 상호 배제가 보장된다

 

그러나 두 프로세스 모두 임계 구역에 진입하지 못하는 무한 대기 현상이 발생할 수 있다

1. 프로세스 p1은 lock1=true; 문을 실행한 후 주어진 CPU 시간을 다 써버려 raedy 상태로 돌아간다. 그 후 context switching이 발생하여 프로세스 p2가 running 상태로 바뀐다
2. 프로세스 p2도 lock2=true; 문을 실행한 후 자신의 CPU 시간을 다 써버려 ready 상태로 돌아간다. 그 후 context switching이 발생하여 프로세스 p1이 running 상태로 바뀐다
3. 프로세스 p2가 lock2=true; 문을 실행했기 때문에 프로세스 p1은 while(lock2==false); 문에서 무한 루프에 빠진다
4. 또한 프로세스 p1이 lock1=true; 문을 실행했기 떄문에 프로세스 p2는 while(lock1==false); 문에서 무한 루프에 빠진다

위처럼 두 프로세스 모두 무한 루프에 빠져 critical section에 진입하지 못한다

이는 bounded waiting 조건을 보장하지 못하고 Deadlock(교착상태)에 빠진 것이다

(Deadlock : 프로세스가 살아 있으나 작업이 진행되지 못하는 상태)

또한 위의 코드는 확장성의 문제가 있는데, 만약 프로세스 p3이 추가되면 또 lock3를 추가해야 되기 떄문에 코드가 갈수록 복잡해진다

 

 

진행의 융통성 문제 (Progress)

ciritical section 문제를 해결하기 위해 lock 값이 1이면 p1이 ciritical section에 들어갈 수 있고, lock이 2이면 p2가 ciritical section에 들어갈 수 있도록 한다

 

• 공유 변수 lock의 값을 통해 다른 프로세스가 ciritical section에 있는지 확인하고, 없으면 진입한다
• 프로세스 p1은 while(lock==2); 문을 실행하고 프로세스 p2가 잠금을 걸었으면 기다린다
• lock == 1 이면 프로세스 p1이 ciritical section에 진입하고, cirtical section에 빠져나올 때 lock을 2로 바꾼다
• 잠금을 확인하는 문장은 하나이므로, mutal exclusion과 bounded waiting을 보장한다
• 그러나 서로 번갈아가면서 실행된다는 것이 문제다
• 즉, 한 프로세스가 두 번 연달아 임계 구역에 진입하는 것이 불가능하다
• 이렇게 프로세스의 진행이 다른 프로세스로 인해 방해받는 현상을 경직된 동기화(lockstep synchronization)라고 한다
• 따라서 위의 예시는 progress를 보장하지 못한다

 

 

하드웨어 측면에서의 해결 방법

위의 코드는 이전에 본 코드로, lock=true 가 작동하기 직전에 timeout이 걸려 ready 상태로 돌아가면 mutual exclusion에 위배되는 문제가 발생하는 코드이다

이를 해결하기 위해 while과 lock 사이에서 timeout이 발생하지 않도록 해야하는데, 이를 원자성(atomicity)를 갖는다 라고 한다

원자성을 갖는 작업은 실행되어 진행되다가 종료하지 않고 중간에 멈추는 경우는 있을 수 없다

이를 해결하기 위해 하드웨어의 도움을 받을 수 있는데, 하드웨어적으로 두 명령어를 동시에 실행하도록 하면 critical section 문제를 쉽게 해결할 수 있다

 

testandset(검사와 지정) 이라는 코드로 하드웨어 지원을 받아 while(lock==true); 문과 lock=true; 문을 한꺼번에 실행한다

검사와 지정 코드를 이용하면 명령어 실행 중간에 타임 아웃이 걸려 critical section이 보호되지 않는 문제가 발생하지 않는다

즉, 원자성(atomicity)를 보장한다는 것이다

그러나 이는 편리하다는 장점이 있지만, busy waiting을 사용하여 검사하기 때문에 자원 낭비가 있다

일부 하드웨어에서는 busy waiting 없이 잠금을 동기화해주기도 하지만, 이는 성능 좋은 하드웨어에서만 가능하다

 

 

위의 4가지 해결 방법은 임계 구역 해결 조건을 완벽하게 충족하지 못했다

이를 해결하기 위해 등장한 방법이 피터슨 알고리즘과 데커 알고리즘이다

그러나 이들은 구조가 복잡하여 현재 잘 사용되지 않는다

 

 

 

 

---

참고)

https://velog.io/@chappi/OS%EB%8A%94-%ED%95%A0%EA%BB%80%EB%8D%B0-%ED%95%B5%EC%8B%AC%EB%A7%8C-%ED%95%A9%EB%8B%88%EB%8B%A4.-8%ED%8E%B8-Critical-section-%EC%9E%84%EA%B3%84-%EA%B5%AC%EC%97%AD

OS는 할껀데 핵심만 합니다. 8편 Critical section (임계 구역)

https://ko.wikipedia.org/wiki/%EC%9E%84%EA%B3%84_%EA%B5%AC%EC%97%AD

임계 구역 - 위키백과, 우리 모두의 백과사전