임계영역 세마포

Critical Section(임계영역)

임계영역 정의

• 멀티 스레딩에 문제점에서 나오듯, 동일한 자원을 동시에 접근하는 작업(e.g. 공유하는 변수 사용, 동일 파일, 동일한 데이터베이스를 사용하는 등)을 실행하는 코드 영역을 Critical Section 이라 칭한다.
• 원래 임계 영역이란 둘 이상의 쓰레드가 동시에 실행될 경우 생길 수 있는 동시 접근 문제를 발생시킬 수 있는 코드 블록을 임계 영역이라고 한다. 동시 접근 문제가 발생한 메모리 공간(힙, 데이터 영역)을 임계 영역이라고 하는 게 아니라, 동시 접근 문제가 발생할 수 있는 우리가 짠 코드 블록을 임계영역이라고 한다.
• 임계 영역에 대한 정의를 있어보이는 말로 표현하면, 임계 영역(Critical Section)이란 배타적 접근(한 순간에 하나의 쓰레드만 접근)이 요구되는 공유 리소스(힙, 데이터 영역에 할당된 값)에 접근하는 코드 블록을 의미한다.

LONG gTotalCount = 0;
void IncreaseCount() {
	//critical section
	gTotalCount++; 
}​ 

임계영역 구역

• 진입 구역(entry section) - 각 프로세스는 자신의 임계구역으로 진입하려면 진입 허가를 요청해야 한다. 이러한 요청을 구현하는 코드 부분을 진입 구역이라고 한다.
• 퇴출 구역(exit section) - 임계구역 뒤에는 퇴출 구역이 따라올 수 있다.
• 나머지 구역(remainder section) - 코드의 나머지 부분을 총칭하여 remainder section이라고 한다.

출처 http://blog.naver.com/PostView.nhn?blogId=bycho211&logNo=221003687645

 

Critical Section Problem(임계영역 문제)

임계영역 문제정의

• 프로세스들이 Critical Section 을 함께 사용할 수 있는 프로토콜을 설계하는 것이다.

Requirements(해결을 위한 기본조건)

• Mutual Exclusion (상호 배제) - 프로세스 P1 이 Critical Section 에서 실행중이라면, 다른 프로세스들은 그들이 가진 Critical Section 에서 실행될 수 없다. 아무 프로세스도 critical section에 못 들어가도 상호 배제는 만족한다
• Progress (진행) - Critical Section 에서 실행중인 프로세스가 없고, 별도의 동작이 없는 프로세스들만 Critical Section 진입 후보로서 참여될 수 있다. 만약 어떤 프로세스도 critical section내에 있지 않고, critical section에 진입하려는 프로세스가 존재한다면 remainder section에서 실행 중이 아닌 프로세스들만이 누가 진입할지 결정할 수 있어야 한다.
• Bounded Waiting (한정된 대기) - P1 가 Critical Section 에 진입 신청 후 부터 받아들여질 때가지, 다른 프로세스들이 Critical Section 에 진입하는 횟수는 제한이 있어야 한다. 프로세스가 Critical section에 진입할 때까지 걸리는 시간에 한계(limit)가 존재하여야 한다. 여기서 말하는 한계는, 프로세스의 개수가 n개이고 time quantum이 q라고 할 때, (n-1)*q 이다.

경쟁상태

• 경쟁상태란 여러프로세스가 공유 데이터를 동시에 접근할때 실행순서에 따라 실행결과가 달라지는 상황
• 예를들어 계좌 데이터베이스를 두 스레드가 동시에 withdraw 를 할때 어느 스레드가 먼저 실행되냐에 따라 잔액의 결과가 달라짐

동기화 (Process Synchronization)

• 경쟁 상황으로부터 보호하기 위하여, 한 순간에는 하나의 프로세스만이 변수를 조작하도록 보장해야 한다.
• 공유 변수에 대한 concurrent access가 발생하지 않도록 해야하며, ordering을 통해 막을 수 있다.
• 데이터 일관성(consistency)을 유지하기 위해서는 서로 협력하여 수행되는 프로세스들(cooperating processes)이 순차적으로 수행하게 만드는 기법, 즉 동기화 기법이 필요하다. 즉, 동기화는 경쟁 상황(Race condition)을 없애는 기법(mechanism)이라고 할 수 있다.
• Race condition은 Parallel execution 에서 뿐 만 아니라 Concurrent execution 에서도 발생할 수 있다.

 

뮤텍스 락(Mutex Locks)

 뮤텍스락의 특징

• mutex라는 이름은, mutual exclusion에서 왔다.
• 뮤텍스 락은 available이라는 boolean 변수를 가지며, 이 변수가 락의 가용 여부를 표시한다.
• 락을 획득할 때 acquire() 함수를 사용하고, 락을 반환할 때 release() 함수를 사용한다.
• 프로세스는 critical section에 들어가기 전 반드시 락을 획득해야 하고, critical section을 빠져 나올 때 락을 반환해야 한다.
• 두 함수는 원자적으로 수행되며, 동기화 인스트럭션 등을 사용하여 구현된다.
  

 

acquire() { 
	while (!available); 
    // busy waiting available = false; 
} 

release() { available = true; }

 

뮤텍스 락의 단점 busy waiting

• 하나의 프로세스가 critical section에 있는 동안, critical section에 들어가길 원하는 다른 프로세스들은 while() 문을 계속 반복하여 수행하여야 한다.
• spinlock 이라고 부른다.
• 이 지속적인 반복은 CPU 싸이클을 차지하기 때문에, 싱글코어 멀티프로그래밍 환경에서 치명적이다. 
  

뮤텍스 락의 장점

• 락을 기다리는 동안 CPU 싸이클을 차지하는 단점이 있는 반면, 컨텍스트 스위칭으로 인한 오버헤드는 없다.
  즉, 프로세스들이 짧은 시간 동안만 락을 차지하는 환경이나, 멀티코어 환경에서는 spinlock이 유용하다.

 

Semaphores(세마포)

세마포 정의

• 소프트웨어상에서 Critical Section 문제를 해결하기 위한 동기화 도구
• boolean 변수 available 을 가지는 뮤텍스 락과는 달리, 세마포어는 좀 더 확장 된 정수 변수이다. 이 변수는 2개의 원자적인 연산(atomic operation)에 의해서만 접근됨
• 락을 획득할 때 wait() 또는 P()  함수를 사용하고, 락을 반환할 때 signal() 또는 V() 함수를 사용한다.
• 뮤텍스 락에서의 acquire(), release() 함수와 마찬가지로, 동기화 인스트럭션 등을 사용하여 구현된다.
• P와 V 연산은 서로 독립적으로 그리고 원자적으로 수행된다.
• 하나의 프로세스가 P를 수행하여 세마포어의 값을 수정하는 동안 다른 프로세스에서 P나 V를 수행하여 같은 세마포어의 값을 수정하지 못한다.

카운팅 세마포

• 가용한 개수를 가진 자원 에 대한 접근 제어용으로 사용되며, 세마포는 그 가용한 자원의 개수 로 초기화 된다.
• 자원을 사용하면 세마포가 감소, 방출하면 세마포가 증가 한다.
• 유한한 개수를 가진 자원에 대한 접근을 제어하는 데 사용될 수 있다.

이진 세마포

• 세마포어 value 가 가질 수 있는 값은 0과 1 뿐이다.
• Test-and-Set과 같은 하드웨어의 도움을 받아서 구현할 수 있다.
• Counting semaphore보다 구현이 간단하다.
• 뮤텍스 락 대신에 사용될 수 있다.

 

세마포어의 두 가지 구현 방식

busy waiting

• 뮤텍스 락과 같이, busy waiting 방법으로 구현할 수 있다.
• busy waiting으로 인한 장/단점 모두 뮤텍스 락과 같다.
• 컨텍스트 스위칭이 발생하는 sleep queue 방식의 세마포어와는 달리, 컨텍스트 스위칭이 발생하지 않는다.
  

sleep queue

• Busy waiting 방식의 CPU cycle을 낭비하는 문제를 sleep queue를 사용하여 해결할 수 있다.
  세마포어의 자료구조에 sleep queue를 추가하여, 대기 중인 프로세스를 관리한다.
  busy waiting을 하지 않고, sleep queue에 넣은 후 sleep 한다. (CPU 싸이클을 소모하지 않는다.)
• 컨텍스트 스위칭이 발생한다!
• 세마포어의 값이 양수가 되어 critical section에 진입이 가능하게 되면, sleep queue에서 대기중인 프로세스를 깨워 실행시킨다.
• 이러한 방식의 단점은, 컨텍스트 스위칭을 하는 비용이 추가된다는 점이다.
• busy waiting을 하는 경우보다 컨텍스트 스위칭의 비용이 더 큰 경우에는 busy waiting 을 하는 것이 더 낫다. (예를 들면, 멀티코어 환경)

하이브리드

• 현실에서는 하이브리드 방식을 사용한다. 즉, busy waiting을 몇 번 해보다가, 시간이 오래 걸릴 것 같으면 sleep queue로 들어간다.
• wakeup()을 하면 sleep queue의 모든 프로세스가 깨워지며, 모든 프로세스가 ready queue로 보내진다.
• 어떤 순서로 프로세스를 실행할 지는 스케줄러의 몫이지, 동기화의 역할이 아니다. 만약, 깨울 프로세스를 동기화에서 정하게 된다면, 이는 스케줄러의 역할을 침범하는 꼴이 된다.

CPU 를 자발적으로 놓는 두 가지 경우

• I/O를 수행하는 경우
• sleep queue 기반의 세마포어 P() 함수

커널이 싱글 스레드인 경우

• 커널 내에서 P(), V()를 시스템 콜로 구현 및 처리하여 세마포어의 동작을 구현한다.
• 커널 내의 수행이 non preemptive 이므로, 커널에 들어간 것이 곧 critical section에 들어간 것이다.

커널이 멀티 스레드인 경우

• P(), V()를 시스템 콜러 구현 및 처리하되, 커널 내에서 별도로 동기화를 해야 한다.

세마포어로 실행순서 정하기

• 세마포는 프로세스 실행 순서를 원하는 대로 제어하는 역할로도 사용할 수 있다. 이를 Ordering이라고 한다. 예를 들어 설명해보자. 프로세스가 P1과 P2가 있다고 하자. 각각의 프로세스는 각자의 코드를 가지고 있다. P1은 S1이라는 내부 코드를 P2는 S2라는 내부 코드를 가지고 있다고 가장하자. 그런데 여기서 우리는 CPU 스케줄링과 상관없이 무조건 P1의 S1이 먼저 실행시키고 싶다고 하자. 그러면 어떻게 코드를 짜야할까? 우리는 세마포를 도구 사용하면 가능하다. 세마포는 정수 값과 프로세스 보관을 가지는 도구이다. 먼저 세마포의 정수 값에 0으로 놓는다. 초기 값은 허용되는 프로세스의 수이므로 0이면 아무도 허용이 되지 않는다는 것을 의미한다. 만약 P1이 먼저 실행되면 S1이 먼저 실행이 되므로 우리는 아무런 효과를 주지 않아도 된다. 하지만 만약 P2가 CPU 스케줄링에 의해 먼저 실행되게 된다면 우리가 의도한 대로 실행이 되지 않는 것이다. 그래서 우리는 임의로 P2의 실행코드 앞에 acquire()명령을 넣어준다. acquire()명령을 실행하면 세마포의 정수 값이 1감소하게 되어 –1이 된다. 그렇게 되면 세마포의 정수 값이 0보다 작은 값을 가지게 되므로 P2는 세마포의 프로세스 보관 Queue에 block 당하게 된다. 그러면 뒤의 코드를 실행할 수 없는 상황에 생긴다. 그렇게 되면 어떻게 되든 문맥전환에 의해 P1이 먼저 실행하게 된다. 그런데 P2를 영원히 갇혀있게 하면 안 된다. 따라서 P1의 내부코드 끝부분에 release()명령을 넣는다. 그렇게 되면 세마포의 정수 값이 1증가하게 되어 다시 0이 된다. 그러면 세마포에 저장된 P2가 wakeup이 되어 세마포에서 빠져나오게 된다.

 

Deadlock(교착상태)

교착상태 정의

• 세마포가 Ready Queue 를 가지고 있고, 둘 이상의 프로세스가 Critical Section 진입을 무한정 기다리고 있고, Critical Section 에서 실행되는 프로세스는 진입 대기 중인 프로세스가 실행되야만 빠져나올 수 있는 상황을 지칭한다.
• 두 개 이상의 프로세스를 사용하는 경우, 한 프로세스에 의해서만 야기될 수 있는 이벤트, 즉 signal()를 영원히 기다리는 상황이 발생할 수 있다.

출처: http://blog.naver.com/PostView.nhn?blogId=bycho211&logNo=221003687645

 

partial order

• 공유 자원들에 대해서 순서(order)를 지정함으로써 데드락을 예방할 수 있다.
• C()를 실행하기 위해서는 B()를 실행하는데 필요한 자원을 모두 할당 받아야 하며, B()를 실행하기 위해서는 A()를 실행하는데 필요한 자원을 모두 할당 받아야 한다.

출처: http://blog.naver.com/PostView.nhn?blogId=bycho211&logNo=221003687645

 

원자적 연산

• 연산을 수행하면서 그 누군가의 방해도 받지 않고 하나의 연산을 하는 것입니다.
• 두 대 이상의 쓰레드가 하나의 공유 변수를 사용할 때에는 하나의 쓰레드만 공유 변수에 접근할 수 있도록 '원자적 연산'을 '보장'해줘야한다는 것입니다.

모니터

• 고급 언어의 설계 구조물로서, 개발자의 코드를 상호배제 하게끔 만든 추상화된 데이터 형태이다.
• 공유자원에 접근하기 위한 키 획득과 자원 사용 후 해제를 모두 처리한다. (세마포어는 직접 키 해제와 공유자원 접근 처리가 필요하다. )

Lock

• 하드웨어 기반 해결책으로써, 동시에 공유 자원에 접근하는 것을 막기 위해 Critical Section 에 진입하는 프로세스는 Lock 을 획득하고 Critical Section 을 빠져나올 때, Lock 을 방출함으로써 동시에 접근이 되지 않도록 한다.

한계

• 다중처리기 환경에서는 시간적인 효율성 측면에서 적용할 수 없다.

 

 

참조글

https://copycode.tistory.com/62

https://blog.shovelman.dev/514 

blog.naver.com/PostView.nhn?blogId=bycho211&logNo=221003687645

github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/OS