[운영체제 OS] Concurrency

1. 병행성

병행성은 여러 프로세스나 쓰레드가 동시에 번갈아 실행되는 환경에서 나타난다.

• 실행 환경:
  • 멀티프로그래밍 (Multiprogramming): 단일 CPU에서 여러 프로세스를 인터리빙(Interleaving) 방식으로 번갈아 실행.
  • 멀티프로세싱 (Multiprocessing): 멀티코어 시스템에서 프로세스들을 물리적으로 동시에 오버랩핑(Overlapping)하여 실행.
  • 분산 처리 (Distributed Processing): 네트워크로 연결된 여러 컴퓨터가 작업을 분담.
• 주요 발생 문제:
  • 경쟁 상태 (Race Condition): 공유 데이터에 동시 접근 시 실행 순서에 따라 결과가 변하는 현상.
  • 교착 상태 (Deadlock): 프로세스들이 서로의 자원을 기다리며 무한 대기하는 상태.
  • 기아 상태 (Starvation): 특정 프로세스가 자원을 영영 할당받지 못하는 상태.

2. 병행성 관련 주요 용어

• 원자적 연산 (Atomic Operation)
  • 연산이 실행되는 도중에 다른 프로세스가 끼어들 수 없다. 따라서 연산은 전부 실행되거나 아예 실행되지 않음이 보장되어야 한다.
• 임계 영역 (Critical Section)
  • 공유 자원(Shared Resource)에 접근하는 코드의 일부 영역.
• 교착 상태 (Deadlock)
  • 두 개 이상의 프로세스가 서로가 점유하고 있는 자원을 기다리며 영원히 대기하는 상태.
• 라이브락 (Livelock)
  • 두 개 이상의 프로세스가 서로의 상태 변화에 반응하며 자신의 상태를 계속 바꾸기만 할 뿐 실질적인 진행은 하지 못하는 상태.
• 상호 배제 (Mutual Exclusion)
  • 한 프로세스가 임계 영역에서 공유 자원을 사용하고 있을 때, 다른 프로세스들이 해당 임계 영역에 접근하지 못하도록 막는 것을 의미하는 조건.
• 경쟁 상태 (Race Condition)
  • 두 개 이상의 프로세스가 공유 자원에 동시에 접근하여 조작하려 할 때, 접근하는 실행 순서(타이밍)에 따라 결과가 달라지는 예측 불가능한 상황.
• 기아 (Starvation)
  • 특정 프로세스가 실행될 수 있는 조건임에도 불구하고, 시스템의 스케줄링 정책이나 다른 프로세스들에 의해 CPU나 자원을 계속해서 할당받지 못하고 무한정 기다리는 경우.

3. 경쟁 상태 예시

공유 자원을 관리하지 않았을 때 발생하는 실제 오류 사례.

• 공유 함수 문제

echo 함수가 전역 변수 chin을 사용할 때, P1이 입력한 값이 P2의 입력값에 의해 덮어씌워져 P1이 엉뚱한 값을 출력하는 경우.

 

• 공유 데이터 문제

두 변수가 항상 a=b여야 한다는 규칙이 있을 때, 연산 도중 문맥 교환이 발생하면 이 규칙이 깨짐.

• 예: 초기 a = 2, b = 2 일 때, P1(a = a + 1)과 P2(b = b ∗ 2)가 뒤섞여 실행되면 결과적으로 a = 6, b = 5가 되어 일관성이 무너짐.

4. 상호 배제 구현 방법

4.1 하드웨어 지원

• 인터럽트 금지: 임계 영역 동안 CPU 전환을 막음. 멀티코어에서는 효과 없음.
• 원자적 명령어: 하드웨어가 '읽기-수정-쓰기'를 한 번에 처리.

Compare and Swap

compare_and_swap(&bolt, 0, 1):  만약bolt의 현재 값이 0이라면, 그 값을 1로 바꾸고 원래 값(0)을 반환. 만약 0이 아니라면, 아무것도 바꾸지 말고 원래 값(1)을 반환.

while (compare_and_swap(&bolt, 0, 1) == 1) {
    /* 대기 */;
}

 

진입 구역 (잠금 획득):

• 동작: 이 코드는 bolt가 0이 될 때까지 계속해서 compare_and_swap을 시도.
  • 잠금 성공: 만약 bolt가 0이었다면, compare_and_swap은 bolt를 1로 바꾸고 0을 반환. while (0 == 1)은 거짓이므로 루프를 빠져나와 임계 구역으로 진입.
  • 잠금 실패: 만약 bolt가 1이었다면, compare_and_swap은 아무것도 바꾸지 않고 1을 반환. while (1 == 1)은 참이므로, 다른 프로세스가 잠금을 해제할 때까지 루프를 계속 돔.

bolt = 0;

• 퇴출 구역 (잠금 해제):
  • 동작: 임계 구역에서의 작업을 마친 후, bolt 값을 다시 0으로 만들어 다른 프로세스가 진입할 수 있도록 함.

Exchange

exchange(&keyi, &bolt)는 지역 변수 keyi의 값과 전역 변수 bolt의 값을 원자적으로 맞바꾸는 명령어.

int keyi = 1;
do {
    exchange(&keyi, &bolt);
} while (keyi != 0);

진입 구역 (잠금 획득):

• 동작: 이 코드는 bolt의 원래 값이 0일 때까지 계속해서 keyi(값 1)와 bolt를 교환.
  • 잠금 성공: 만약 bolt가 0이었다면, 교환 후 keyi는 0이 되고 bolt는 1이 됨. while. (0 != 0)은 거짓이므로 루프를 빠져나와 임계 구역으로 진입.
  • 잠금 실패: 만약 bolt가 1이었다면, 교환 후에도 keyi는 1이 되고 bolt도 1로 유지. while (1 != 0)은 참이므로, 다른 프로세스가 bolt를 0으로 만들 때까지 루프를 계속 돔.

bolt = 0;

퇴출 구역 (잠금 해제):

• 동작: bolt 값을 다시 0으로 되돌려 잠금을 해제.

5. 병행성 기법

• 세마포어 (Semaphore): 프로세스 간에 시그널을 주고받기 위해 사용되는 정수 값. 카운팅 세마포어는 여러 개의 자원을 관리할 수 있고, 이진 세마포어는 값이 0과 1만 가질 수 있어서 단일 자원 접근 제어에 쓰임.
• 뮤텍스 (Mutex): 이진 세마포어와 비슷하지만, 오직 잠금을 획득한 스레드만이 잠금을 해제할 수 있다는 중요한 규칙이 있음.
• 조건 변수 (Conditional Variable): 단순히 잠그는 걸 넘어서, 어떤 특정 조건이 만족될 때까지 스레드를 잠들게(wait) 했다가, 다른 스레드가 그 조건을 만족시키면 신호(signal)를 보내 깨워주는 역할.
• 모니터 (Monitor): 프로그래밍 언어 차원에서 제공하는 고급 동기화 도구. 공유 데이터와 그걸 처리하는 함수들을 하나로 묶고, 자동으로 상호 배제를 보장.
• 스핀락 (Spinlock): 뮤텍스처럼 잠금장치지만, 잠금을 얻지 못했을 때 잠드는 게 아니라 제자리에서 계속 돌면서(busy-waiting) 잠금이 풀렸는지 반복적으로 확인하는 방식.

6. 세마포어

정수 값(S)과 두 가지 원자적 연산으로 자원을 관리.

• semWait (P연산): S를 감소시킴. S<0이면 프로세스는 대기 큐로 가서 잠듦(Block).
• semSignal (V연산): S를 증가시킴. S≤0이면 대기 큐의 프로세스를 깨움(Wake-up).
  

세마포어를 이용하여 보호되는 공유 데이터를 접근하는 프로세스들의 수행 과정

1. 초기 상태
   • 세마포어 값: 1
   • 대기 큐: 비어있음.
   • 의미: 임계 영역에 진입할 수 있는 "허가증"이 1개 있다.
2. A, semWait(lock) 호출
   • 프로세스 A가 임계 영역 진입을 시도한다.
   • 세마포어 값: 1 -> 0으로 감소.
   • 결과: A는 대기 없이 임계 영역으로 진입하여 정상 실행한다.
3. B, semWait(lock) 호출
   • A가 임계 영역에 있는 동안, B가 진입을 시도한다.
   • 세마포어 값: 0 -> -1으로 감소.
   • 결과: 값이 음수가 되었으므로, B는 블록(Blocked) 상태가 되어 대기 큐에 들어간다.
4. C, semWait(lock) 호출
   • A가 아직 임계 영역에 있는 동안, C도 진입을 시도한다.
   • 세마포어 값: -1 -> -2로 감소.
   • 결과: C 역시 블록 상태가 되어 대기 큐에 들어간다. (큐 상태: C, B)
5. A, semSignal(lock) 호출
   • A가 임계 영역 작업을 마치고 빠져나온다.
   • 세마포어 값: -2 -> -1으로 증가.
   • 결과: 값이 0 이하이므로 대기 중인 프로세스가 있다는 의미. 큐에서 B를 깨운다(Wake-up). B는 이제 임계 영역으로 진입한다.
6. B, semSignal(lock) 호출
   • B가 임계 영역 작업을 마치고 빠져나온다.
   • 세마포어 값: -1 -> 0으로 증가.
   • 결과: 값이 0 이하이므로 대기 중인 프로세스가 있다는 의미. 큐에서 C를 깨운다. C는 이제 임계 영역으로 진입한다.
7. C, semSignal(lock) 호출
   • C가 임계 영역 작업을 마치고 빠져나온다.
   • 세마포어 값: 0 -> 1로 증가.
   • 결과: 값이 양수이므로 대기 중인 프로세스가 없음. 아무도 깨우지 않고, 시스템은 다시 초기 상태와 같이 "허가증"이 1개 있는 상태가 된다.

7. 생산자-소비자 문제 (Producer-Consumer Problem)

공유 버퍼를 사이에 두고 데이터를 넣고 빼는 고전적인 동기화 문제.

 

해결 조건

• 버퍼 접근 시 상호 배제 (한 번에 하나만).
• 버퍼가 비었을 때 소비자는 대기.
• 버퍼가 가득 찼을 때 생산자는 대기.

7.1 무한 버퍼에서 이진 세마포어를 이용한 생산자 소비자 문제 해결 방법

1. 소비자가 임계 영역에 들어가 아이템을 꺼낸다. n은 0이 된다.
2. 소비자는 m = n;을 통해 m에 0을 저장한다. (잠들기로 결정 완료)
3. 소비자가 semSignalB(s)를 호출하여 잠금을 해제한다.
4. 여기서 생산자가 끼어들어도 괜찮다!
5. 생산자가 semWaitB(s)로 잠금을 얻고, 아이템을 추가하며 n을 1로 만든다.
6. n이 1이 되었으므로 semSignalB(delay)를 호출하여 delay 세마포어 값을 1로 만든다. (깨우기 신호 보냄)
7. 이제 다시 소비자로 돌아오면, 소비자는 if (m == 0)을 검사한다. m은 자신의 지역 변수이므로 생산자의 작업에 영향을 받지 않고 여전히 0이다.
8. 소비자는 semWaitB(delay)를 호출하지만, 생산자가 이미 delay를 1로 만들어 놓았기 때문에 전혀 기다리지 않고 바로 통과한다.

결과적으로, 생산자가 보낸 깨우기 신호가 delay 세마포어에 안전하게 저장되어 잃어버리지 않게 되므로 교착 상태가 발생하지 않는다.

7.2 무한 버퍼에서 범용 세마포어를 이용한 생산자 소비자 문제 해결 방법

이 해결법은 목적이 다른 두 개의 세마포어를 사용한다.

• semaphore s = 1: 상호 배제(Mutual Exclusion)를 위한 세마포어이다.
  • 이것은 이전 예제들의 뮤텍스(Mutex)와 동일한 역할을 한다.
  • 공유 버퍼에 오직 하나의 프로세스만 접근할 수 있도록 보장하는 잠금(Lock) 장치이다.
• semaphore n = 0: 동기화(Synchronization)를 위한 세마포어이다.
  • 이 세마포어의 값은 버퍼에 들어있는 아이템의 개수를 의미한다.
  • 소비자가 텅 빈 버퍼에 접근하려 할 때, 이 세마포어를 통해 대기(Block)하도록 만든다.

생산자 (Producer)의 동작

1. produce(): 아이템을 생성한다.
2. semWait(s): 버퍼에 아이템을 추가하기 위해 임계 영역으로 진입한다 (잠금을 획득).
3. append(): 버퍼에 아이템을 추가한다.
4. semSignal(s): 임계 영역에서 빠져나온다 (잠금을 해제).
5. semSignal(n): 아이템을 하나 추가했으므로, 아이템의 총 개수를 의미하는 n의 값을 1 증가시킨다. 만약 이 신호로 인해 잠들어 있던 소비자가 있다면, 그중 하나를 깨우게 된다.

소비자 (Consumer)의 동작

1. semWait(n): 버퍼에 소비할 아이템이 있는지 먼저 확인한다.
   • 만약 n > 0이라면, n을 1 감소시키고 다음 단계로 진행한다.
   • 만약 n = 0이라면, 소비할 아이템이 없다는 의미이므로 생산자가 semSignal(n)을 호출해 줄 때까지 여기서 잠든다(Block).
2. semWait(s): 소비할 아이템이 있음을 확인한 후, 버퍼에 안전하게 접근하기 위해 임계 영역으로 진입한다 (잠금을 획득).
3. take(): 버퍼에서 아이템을 꺼낸다.
4. semSignal(s): 임계 영역에서 빠져나온다 (잠금을 해제).
5. consume(): 가져온 아이템을 소비한다.

7.3 유한 버퍼에서 범용 세마포어를 이용한 생산자 소비자 문제 해결 방법

1. semaphore s = 1: 상호 배제를 위한 세마포어.
   • 이전과 동일하게 임계 영역(버퍼)에 대한 접근을 제어하는 잠금(Lock) 역할을 한다.
2. semaphore n = 0: 채워진 버퍼 슬롯의 개수를 세는 세마포어.
   • n의 값은 소비자가 가져갈 수 있는 아이템의 개수를 의미한다.
   • 버퍼가 비어있을 때(n=0) 소비자가 잠들게 하는 역할을 한다.
3. semaphore e = sizeofbuffer: 비어있는 버퍼 슬롯의 개수를 세는 세마포어.
   • e의 값은 생산자가 아이템을 저장할 수 있는 공간의 개수를 의미한다.
   • 버퍼가 가득 찼을 때(e=0) 생산자가 잠들게 하는 역할을 한다.

생산자 (Producer)의 동작

1. produce(): 아이템을 생성한다.
2. semWait(e): 빈 공간이 있는지 확인한다.
   • 만약 빈 공간이 없다면(e=0), 즉 버퍼가 가득 찼다면 소비자가 공간을 만들 때까지 여기서 잠든다(Block).
   • 빈 공간이 있다면 e를 1 감소시키고 계속 진행한다.
3. semWait(s): 버퍼에 접근하기 위해 잠금을 획득한다.
4. append(): 버퍼에 아이템을 추가한다.
5. semSignal(s): 잠금을 해제한다.
6. semSignal(n): 채워진 슬롯의 개수가 하나 늘었음을 알린다. 잠들어 있던 소비자가 있다면 깨운다.

소비자 (Consumer)의 동작

1. semWait(n): 소비할 아이템이 있는지 확인한다.
   • 만약 아이템이 없다면(n=0), 즉 버퍼가 비어있다면 생산자가 아이템을 만들 때까지 여기서 잠든다(Block).
   • 아이템이 있다면 n을 1 감소시키고 계속 진행한다.
2. semWait(s): 버퍼에 접근하기 위해 잠금을 획득한다.
3. take(): 버퍼에서 아이템을 꺼낸다.
4. semSignal(s): 잠금을 해제한다.
5. semSignal(e): 빈 공간의 개수가 하나 늘었음을 알린다. 잠들어 있던 생산자가 있다면 깨운다.
6. consume(): 아이템을 소비한다.

8. 모니터 (Monitor)

세마포어의 복잡함을 해결하기 위해 프로그래밍 언어 차원에서 제공하는 고수준 동기화 도구.

 

특징

• 암묵적 상호 배제: 한 번에 하나의 프로세스만 모니터 내부 함수를 실행할 수 있음 (자동 잠금).
• 조건 변수: cwait(c)로 특정 조건까지 잠들고, csignal(c)로 깨움.

• int count: 버퍼에 저장된 아이템의 개수를 나타내는 변수.
• cond notfull: 버퍼가 가득 차 "꽉 차지 않은 상태가 되기를" 기다리는 생산자를 위한 조건 변수.
• cond notempty: 버퍼가 비어있어 "비어있지 않은 상태가 되기를" 기다리는 소비자를 위한 조건 변수.

생산자 프로시저 (append)

1. if (count == N) cwait(notfull);
   • 조건 검사: 모니터에 진입 후, 버퍼가 가득 찼는지(count == N) 확인한다.
   • 대기: 만약 가득 찼다면, cwait(notfull)를 호출하여 모니터의 잠금을 풀고 notfull 조건 변수 큐에서 잠든다. 이는 다른 프로세스(소비자)가 모니터에 들어와 아이템을 가져갈 수 있도록 길을 열어주는 핵심 동작이다.
2. 아이템 추가: 버퍼에 자리가 있다면, 아이템을 추가하고 count를 1 증가시킨다.
3. csignal(notempty);
   • 신호 보내기: 아이템을 하나 추가했으므로, 버퍼는 이제 절대 비어있지 않다(not empty). 따라서 notempty 조건에서 잠들어 있는 소비자가 있다면 하나를 깨워준다.

소비자 프로시저 (take)

1. if (count == 0) cwait(notempty);
   • 조건 검사: 모니터에 진입 후, 버퍼가 비어있는지(count == 0) 확인한다.
   • 대기: 만약 비어있다면, cwait(notempty)를 호출하여 모니터의 잠금을 풀고 notempty 조건 변수 큐에서 잠든다. 이는 생산자가 들어와 아이템을 채울 수 있도록 허용하는 것이다.
2. 아이템 꺼내기: 버퍼에 아이템이 있다면, 아이템을 꺼내고 count를 1 감소시킨다.
3. csignal(notfull);
   • 신호 보내기: 아이템을 하나 꺼냈으므로, 버퍼에는 반드시 빈 공간이 생겼다(not full). 따라서 notfull 조건에서 잠들어 있는 생산자가 있다면 하나를 깨워준다.

producer()

• produce(x): 자신의 로직에 따라 아이템 x를 생성한다.
• append(x): 모니터의 append 프로시저를 호출한다. 생산자는 그저 "버퍼에 x를 추가해 줘"라고 요청할 뿐, 버퍼가 가득 찼는지, 다른 프로세스와 충돌하는지 등 복잡한 상황은 전혀 신경 쓰지 않는다. 모든 동기화 처리는 append 프로시저 내부에 숨겨져 있다.

consumer()

• take(x): 모니터의 take 프로시저를 호출한다. 소비자는 "버퍼에서 아이템 하나를 꺼내줘"라고 간단히 요청한다. 버퍼가 비어있는지에 대한 검사와 대기(wait)는 take 프로시저가 알아서 처리한다.
• consume(x): 가져온 아이템 x를 사용한다.

main()

• parbegin(producer, consumer): 생산자와 소비자를 병렬로 실행시켜, 공유 버퍼(모니터)에 대한 동시 접근 상황을 만든다.

 

출처

• William Stallings, 운영체제 내부구조 및 설계원리