[운영체제] 병행성

728x90

/* 병행성 Concurrency*/

동시에 실행하는 것 처럼 보여진다. (실제로는 짧은 시간 동안 작업들이 번갈아 가며 실행되는 것처럼 보인다.)

병렬성 (Parallelism) 은 실제로 동시에 실행이 된다. 멀티코어에서 멀티 스레드를 동작시킨다.

스레드 들은 동시에 메모리에 접근하게 되는데 이를 조정하지 않으면 문제가 될 수 있다.

주요 개념

프로세스: 운영체제에서 실행되는 프로그램. 각 프로세스는 독립적인 메모리 공간을 가진다.
스레드: 프로세스 내부에서 실행되는 작은 실행 단위. 한 프로세스 내에 여러 스레드가 존재할 수 있으며, 메모리를 공유한다. 스레드 생성시 스택을 생성한다. 즉, 스택은 공유하지 않는다.

두 스레드가 하나의 프로세스에서 실행 중이라면 Context Switch를 통해 교체 된다. (스레드의 Context Siwtch에는 TCB (Thread Control Block, 스레드 제어 블럭)이 사용된다. 프로세스의 Context Switch에는 PCB (Process Control Block, 프로세스 제어 블럭)이 사용된다.)

/* 스레드 */

스레드가 생성되고 작업을 수행할 때 실행 가능 순서는 다양하다. 어떤 스레드가 언제 실행되는지 알기 어렵다.

ex) 두 스레드에서 공유 변수에 +1하는 과정을 10,000번 반복하면 20,000이 나오지 않는 문제가 발생한다.

race condition (경쟁 조건): 여러 프로세스나 스레드가 공유 자원에 동시에 접근하여 예상치 못한 결과를 초래할 수 있는 상황

critical section (임계 영역): 공유 변수를 접근하고 하나 이상의 스레드에서 동시에 실행되면 안되는 코드 (영역)

이러한 문제를 해결하려면 상호 배제 (mutual exclusion) 속성이 필요하다.

한 스레드에서 임계 영역 내의 코드를 실행 중일 때 다른 스레드가 실행할 수 없도록 보장한다.

하지만 이러면 하나의 스레드가 다른 스레드의 동작이 끝날 때까지 대기해야 하는 상황이 발생한다.

/* 락 */

스레드 라이브러리에서는 락(lock) 함수를 통해 임계 영역에 대한 상호 배제 기법을 제공한다.

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

- lock 이 호출되었을 때 다른 스레드도 락을 가지고 있지 않다면 락을 얻어 임계 영역에 진입

- 다른 스레드가 락을 가지고 있으면 락을 얻을때까지 호출에서 리턴하지 않는다 (기다린다)

- 락을 호출한 스레드가 언락을 호출해야 한다.

락을 획득한 스레드는 락 소유자라고 한다.

여러가지 상호배제 기법들이 있다.

/* 1. 뮤텍스 */

락을 얻지 못한 스레드는 블로킹 상태로 전환되어 CPU 시간을 낭비하지 않는다.

락을 얻지 못한 스레드는 블로킹 상태로 전환되어 대기 큐에 들어갑니다.
락이 해제되면, 뮤텍스는 스레드 스케줄러에게 대기 중인 스레드를 깨우도록 신호를 보냅니다. (운영체제의 내부 메커니즘에 의해)
스레드 스케줄러는 대기 중인 스레드를 실행 가능 상태로 전환하고, 락을 획득할 수 있도록 합니다.
이 모든 과정은 운영체제의 커널과 스레드 스케줄링 메커니즘에 의해 자동으로 관리되므로, 사용자 스레드가 별도로 락 반환 여부를 확인하지 않아도 됩니다.

- 장점: 공유 자원에 대한 접근을 제어하여 데이터의 무결성을 보장한다. CPU 시간을 낭비 하지 않는다

- 단점: 데드락 (두 스레드가 서로의 락을 무한정 기다린다),

/* 2. 컨디션 변수 */

뮤텍스에서 락이 해제될 때 대기 중인 스레드를 깨우는 작업은 컨디션 변수가 아니라, 뮤텍스와 운영체제의 내부 메커니즘에 의해 자동으로 이루어진다. 그러나 컨디션 변수는 특정 조건이 만족될 때까지 스레드를 대기시키고, 조건이 충족되면 대기 중인 스레드를 깨우는 데 사용된다. 뮤텍스만으로는 해결할 수 없는 복잡한 동기화 문제를 해결하는 데 사용된다.

/* 3. 스핀락 */

스핀락은 대기 중인 스레드가 공유 자원의 상태를 무한 루프를 이용해 확인하는 방식이다. 반복적으로 락이 반환될 때까지 확인하며 대기한다.

- 장점: 스핀락은 스레드가 대기 상태로 전환되지 않기에 Context Switch가 일어나지 않는다. Context Switch에 필요한 CPU 오버헤드를 줄일 수 있다, 락의 획득이 빠르다.

- 단점: Busy Waiting (바쁜 대기) - 스핀 락 획득을 위해 CPU 를 계속 사용하면서 대기 루프를 돈다. Starvation (기아 상태) - 특정 스레드가 락을 얻지 못한 채로 계속 기다리게 되어 영원히 자원에 접근하지 못하는 상황

/* 4. 세마포어 */

세마포어는 락과 컨디션 변수를 모두 사용할 수 있다.

뮤텍스는 한번에 하나의 스레드만 임계 영역에 진입이 가능하지만, 세마포어는 여러 스레드가 제한된 자원 (하나 이상의 자원)에 접근할 수 있게 한다.

세마포어는 화장실의 열쇠에 비유를 많이 든다. (참조: https://baebalja.tistory.com/340)

식당에 화장실이 3개가 존재하고 식당 카운터에 열쇠가 3개 있다고 가정해보자.

세마포어 S는 현재 공유 자원에 접근할 수 있는 프로세스/스레드의 수를 의미한다.

그러면 여기서 S는 카운터에 남아 있는 열쇠의 개수를 의미한다.

열쇠를 하나 가져가는 연산을 P라고 하고, 열쇠를 반납하는 연산을 V라고 하자

(P와 V의 연산이 번갈아 이루어지다가 S가 0이 될 수 있다. 이는 곧 누군가가 V를 해줘야 P가 이루어질 수 있다.)

세마포어에는 Busy-Waiting 방식과 Block-Wakeup 방식이 있다.

Busy Waiting
P(S) {
     while S <=0; // 아무것도 하지 않음 (반복문)
     S--;
 }

 V(S) {
     S++;
 }

Busy Waiting에서는 Spin Lock 방법이 사용되었다. 하지만 이는 곧 CPU 시간을 낭비한다.

이를 해결하기 위해 S가 0이면 스레드를 Wait Queue 에 추가하는 방법이 있다.

S가 0이하이면 block()을 통해 스레드를 Wait Queue에 넣고 S가 1이상이면 Wait Queue에서 스레드를 꺼내와 wakeup()을 수행한다.

이를 Block-Wakeup 방식이라고 한다.

Block-Wakeup
P(S) {
     S--;
     if S < 0
         // 이 프로세스를 재움 큐에 추가 (잠 듦)
         block(); 
 }

 V(S) {
     S++;
     if S <= 0
         // 재움 큐로부터 프로세스를 제거 (깨어남)
         wakeup(); 
 }

하지만 여기서는 똑같이 DeadLock이 발생할 수 있다.

화장실을 이용하는데 열쇠가 두개가 필요하다면?
한 스레드는 열쇠 하나, 다른 스레드는 다른 열쇠 하나를 소유하고 있고 나머지 열쇠를 얻기 위해 무한정 대기하는 상황이 발생할 수 있다.

/* 데드락 DeadLock */

데드락 (교착상태라고도 불리움)이 발생하기 위해서는 아래 네 가지 요건이 모두 충족 되어야 한다.

상호 배제
- 스레드가 자신이 필요로 하는 자원에 대한 독자적인 제어권 주장 (이 자원은 나만 가져야해!)
점유 및 대기
- 스레드가 자신에게 할당된 자원을 점유한 동시에 다른 자원 대기
비선점
- 락을 점유하고 있는 스레드로부터 자원을 강제적으로 빼앗을 수 없음
순환 대기
- 각 스레드는 다음 스레드가 요청한 하나 또는 그 이상의 락을 갖고 있는 스레드들의 순환 고리 존재
- (사이클이 형성된 상태로 기다리는 상황. 서로 빠져주기를 기다리는 상황)

데드락을 처리하는 방법.

예방, 회피, 탐지 및 복구, 무시가 있다.

예방
- 상호배제 부정
  - 읽기 전용 파일과 같은 공유 자원 사용
- 점유와 대기 부정
  - 대기를 없애기 위해 프로세스가 실행되기 전 모든 자원 할당
  - 자원을 점유하지 않고 있을 때만 다른 자원 요청 가능 (기아상태 될 수 있다.)
- 비선점 부정
  - 모든 자원에 대한 선점 허용. (락을 점유하고 있는 스레드로부터 자원을 빼앗을 수 있다.)
- 순환대기 부정
  - 자원에 고유한 번호를 할당해서 번호 순서대로 자원을 요구
회피
- 데드락에 빠질 가능성이 있는지 없는지 OS가 검사를 해서 진행한다.
탐지 및 복구
- 데드락에 빠지면 바로 전 상태로 회복. 복잡한 알고리즘으 거쳐야 해서 오버헤드가 크다
무시
- 데드락은 드문 상황이다. 데드락이 발생하면 사용자가 직접 프로세스를 종료한다. 대부분이 이 방법을 사용한다.