운영체제 기본/동시성: 두 판 사이의 차이
RCU 총론 소개에서 구현 각론 연결 |
과도한 강조와 반복 대조를 정리하고 동기화 규약 설명을 간결하게 수정 |
||
| (같은 사용자의 중간 판 하나는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
{{이전 다음 문서 | {{이전 다음 문서 | ||
|이전= | |이전=이전 문서<br />[[운영체제 기본/프로세스와 스레드|프로세스와 스레드]] | ||
|목차=[[운영체제 기본#총론|총론 목차]] | |목차=[[운영체제 기본#총론|총론 목차]] | ||
|다음=다음 문서 | |다음=다음 문서<br />[[운영체제 기본/가상 메모리|가상 메모리]] | ||
}} | }} | ||
| 8번째 줄: | 8번째 줄: | ||
동시성(Concurrency)은 여러 작업의 진행 기간이 겹치는 성질이다. 병렬성(Parallelism)은 여러 작업이 실제로 같은 순간에 실행되는 성질이다. CPU 코어가 하나여도 스케줄러가 작업을 번갈아 실행하면 동시성이 생긴다. 코어가 여러 개면 병렬 실행도 가능하지만, 코어 수가 동시성 문제의 유무를 결정하지는 않는다. 작업 하나가 공유 상태를 바꾸다 멈춘 사이 다른 작업이 그 상태에 접근하는 것만으로 문제가 생긴다. | 동시성(Concurrency)은 여러 작업의 진행 기간이 겹치는 성질이다. 병렬성(Parallelism)은 여러 작업이 실제로 같은 순간에 실행되는 성질이다. CPU 코어가 하나여도 스케줄러가 작업을 번갈아 실행하면 동시성이 생긴다. 코어가 여러 개면 병렬 실행도 가능하지만, 코어 수가 동시성 문제의 유무를 결정하지는 않는다. 작업 하나가 공유 상태를 바꾸다 멈춘 사이 다른 작업이 그 상태에 접근하는 것만으로 문제가 생긴다. | ||
[[운영체제 기본/프로세스와 스레드|스레드]]가 주소 공간을 공유하면 데이터를 복사하거나 전달하는 비용을 줄일 수 있다. 대신 누가 언제 읽고 쓰는지 합의해야 한다. 서로 다른 프로세스도 [[운영체제 기본/프로세스 간 통신#공유 메모리와 동기화|공유 메모리]]를 사용하면 같은 문제를 만난다. 공유를 없애고 메시지로 소유권을 넘기면 조정 범위는 줄지만, 전달 비용과 대기열 관리가 생긴다. | [[운영체제 기본/프로세스와 스레드|스레드]]가 주소 공간을 공유하면 데이터를 복사하거나 전달하는 비용을 줄일 수 있다. 대신 누가 언제 읽고 쓰는지 합의해야 한다. 서로 다른 프로세스도 [[운영체제 기본/프로세스 간 통신#공유 메모리와 동기화|공유 메모리]]를 사용하면 같은 문제를 만난다. 공유를 없애고 메시지로 소유권을 넘기면 조정 범위는 줄지만, 전달 비용과 대기열 관리가 생긴다. 공유 범위를 정할 때는 데이터 전달 비용과 동기화 비용을 함께 고려해야 한다. | ||
== 공유 상태의 불변식과 레이스 컨디션 == | == 공유 상태의 불변식과 레이스 컨디션 == | ||
| 33번째 줄: | 33번째 줄: | ||
</pre> | </pre> | ||
지켜야 할 불변식(Invariant)은 | 지켜야 할 불변식(Invariant)은 '승인된 주문 수와 남은 재고의 합은 최초 재고와 같다'는 관계다. 여기서는 취소와 입고가 없다고 가정한다. 재고 확인부터 차감과 승인 기록까지 다른 주문 처리와 겹치지 않게 묶어야 한다. 이렇게 보호해야 하는 구간이 임계 구역(Critical Section)이다. 모든 명령 사이에 불변식이 성립할 필요는 없지만, 다른 작업에 상태를 넘겨주는 경계에서는 복구되어 있어야 한다. | ||
== 뮤텍스와 임계 구역 == | == 뮤텍스와 임계 구역 == | ||
재고 확인부터 주문 승인까지 하나의 작업으로 묶으려면, 다른 스레드가 그 구간에 동시에 들어오지 못하게 해야 한다. | 재고 확인부터 주문 승인까지 하나의 작업으로 묶으려면, 다른 스레드가 그 구간에 동시에 들어오지 못하게 해야 한다. 상호 배제 (Mutual Exclusion)는 한 번에 하나의 스레드만 임계 구역을 실행하게 하는 성질이다. 이를 제공하는 락(Lock)의 한 종류가 뮤텍스 (Mutex)다. 뮤텍스는 잠겨 있지 않거나, 어떤 스레드가 획득해 소유하고 있는 상태다. 스레드는 들어가기 전에 뮤텍스를 획득하고, 작업을 끝내면 자신이 소유한 뮤텍스를 해제한다. 다른 스레드가 이미 소유하고 있다면 기다려야 한다.<ref name="mutex-ownership">[https://man7.org/linux/man-pages/man3/pthread_mutex_lock.3p.html POSIX pthread_mutex_lock()], 획득한 스레드의 소유권과 해제 규칙.</ref> | ||
<pre> | <pre> | ||
| 46번째 줄: | 46번째 줄: | ||
</pre> | </pre> | ||
A가 뮤텍스를 가진 동안 B는 같은 뮤텍스를 획득하지 못하므로, A의 재고 확인과 차감 사이에 B가 끼어들지 못한다. A가 해제한 뒤 B가 들어오면 이미 줄어든 재고를 확인한다. 다만 재고를 다루는 모든 경로가 같은 규칙을 따라야 한다 | A가 뮤텍스를 가진 동안 B는 같은 뮤텍스를 획득하지 못하므로, A의 재고 확인과 차감 사이에 B가 끼어들지 못한다. A가 해제한 뒤 B가 들어오면 이미 줄어든 재고를 확인한다. 다만 재고를 다루는 모든 경로가 같은 규칙을 따라야 한다. 락을 거치지 않고 접근하는 코드는 데이터를 훼손할 수 있다. | ||
뮤텍스의 소유자는 임계 구역을 빠져나오며 직접 해제해야 한다 | 뮤텍스의 소유자는 임계 구역을 빠져나오며 직접 해제해야 한다. 구현은 원자 연산과 운영체제의 대기 처리를 조합하며, 경합 없는 획득은 사용자 공간에서 처리할 수 있다.<ref name="mutex-futex">[https://man7.org/linux/man-pages/man7/futex.7.html Linux man-pages: futex(7)], 사용자 공간의 빠른 경로와 커널 대기 지원.</ref> 구간을 크게 묶으면 규칙은 단순해지는 대신 동시에 진행할 수 있는 작업이 줄어든다. | ||
== 세마포어와 자원 수량 == | == 세마포어와 자원 수량 == | ||
사용 가능한 작업 버퍼가 세 개라면 한 번에 하나만 허용하는 뮤텍스로 버퍼 사용 전체를 감쌀 필요는 없다. 서로 다른 버퍼를 쓰는 세 작업은 함께 진행할 수 있어야 한다. | 사용 가능한 작업 버퍼가 세 개라면 한 번에 하나만 허용하는 뮤텍스로 버퍼 사용 전체를 감쌀 필요는 없다. 서로 다른 버퍼를 쓰는 세 작업은 함께 진행할 수 있어야 한다. 세마포어 (Semaphore)는 사용할 수 있는 자원이나 누적된 통지의 수를 정수로 나타내고, 그 수를 소비하거나 추가하면서 실행을 조정하는 도구다. 0 이상의 값을 가지는 카운팅 세마포어(Counting Semaphore)는 여러 개의 사용권을 표현한다.<ref name="sem-definition">[https://man7.org/linux/man-pages/man7/sem_overview.7.html Linux man-pages: sem_overview(7)], 세마포어의 값과 두 기본 연산.</ref> | ||
기본 연산은 | 기본 연산은 wait와 post다. wait는 값이 양수일 때 확인과 감소를 원자적으로 수행하고 사용권 하나를 얻는다. 값이 0이면 사용권이 생길 때까지 기다린다. post는 값을 하나 늘려 사용권을 추가하며, 기다리는 작업이 있으면 진행할 기회를 준다. 서로 다른 두 작업이 마지막 사용권 하나를 동시에 가져가서는 안 되므로, 단순한 일반 변수의 확인과 감소를 따로 실행해서는 구현할 수 없다.<ref name="sem-wait">[https://man7.org/linux/man-pages/man3/sem_wait.3.html Linux man-pages: sem_wait(3)].</ref><ref name="sem-post">[https://man7.org/linux/man-pages/man3/sem_post.3.html Linux man-pages: sem_post(3)].</ref> | ||
<pre> | <pre> | ||
초기 사용권: 3 | 초기 사용권: 3 | ||
A: wait | A: wait -> 2, 버퍼 사용 시작 | ||
B: wait | B: wait -> 1, 버퍼 사용 시작 | ||
C: wait | C: wait -> 0, 버퍼 사용 시작 | ||
D: wait | D: wait -> 대기 | ||
B: 버퍼 반환, post | B: 버퍼 반환, post -> D가 사용권을 얻고 진행 가능 | ||
</pre> | </pre> | ||
| 68번째 줄: | 68번째 줄: | ||
세마포어에는 뮤텍스와 같은 소유자 개념이 없다. 초기값을 0으로 두고 생산자가 작업을 완성할 때 post하면, 소비자는 wait로 완료된 작업 하나를 기다릴 수 있다. 통지가 먼저 도착하면 수량으로 남으므로 이후 wait가 이를 소비한다. 이 용도에서는 post한 작업과 wait하는 작업이 다른 것이 자연스럽다. 뮤텍스는 임계 구역의 배타적 소유를, 세마포어는 수량과 작업 사이의 순서를 표현한다. | 세마포어에는 뮤텍스와 같은 소유자 개념이 없다. 초기값을 0으로 두고 생산자가 작업을 완성할 때 post하면, 소비자는 wait로 완료된 작업 하나를 기다릴 수 있다. 통지가 먼저 도착하면 수량으로 남으므로 이후 wait가 이를 소비한다. 이 용도에서는 post한 작업과 wait하는 작업이 다른 것이 자연스럽다. 뮤텍스는 임계 구역의 배타적 소유를, 세마포어는 수량과 작업 사이의 순서를 표현한다. | ||
값을 0과 1로만 유지하는 | 값을 0과 1로만 유지하는 이진 세마포어 (Binary Semaphore)도 상호 배제에 사용할 수 있지만, 소유권과 해제 규약까지 뮤텍스와 같아지지는 않는다. 무엇을 하나로 세는지, 언제 소비하고 돌려줄지를 일관되게 정해야 한다. | ||
== 대기열을 이용한 내부 구현 == | == 대기열을 이용한 내부 구현 == | ||
뮤텍스와 세마포어의 상태도 여러 스레드가 함께 읽고 바꾼다. 따라서 내부의 | 뮤텍스와 세마포어의 상태도 여러 스레드가 함께 읽고 바꾼다. 따라서 내부의 소유자, 수량, 대기열을 갱신하는 짧은 구간에는 별도의 원자적 보호가 필요하다. 아래의 <code>guard</code>는 CAS 같은 원자 연산으로 획득하는 짧은 스핀락이다. 사용자가 뮤텍스로 보호하는 긴 작업 동안에는 guard를 보유하지 않는다. guard의 원자적 획득과 메모리 순서는 뒤의 [[#원자 연산을 이용한 락 구현|원자 연산을 이용한 락 구현]]에서 설명한다. | ||
대기에는 | 대기에는 대기열에 자신을 등록하는 일과 CPU를 놓고 잠드는 일을 연결하는 규약이 필요하다. 등록 후 guard를 먼저 풀고 나중에 아무 조건 없이 잠들면, 그 사이 다른 스레드가 보낸 깨우기를 놓칠 수 있다. 여기서 <code>park_and_unlock(guard)</code>는 guard를 보유한 상태에서 대기를 확정하고 guard를 해제하는 일을 깨우기와 조정한다. 상대가 guard를 얻은 뒤 <code>wake</code>를 실행했다면, 대기자는 그 통지를 잃고 뒤늦게 잠들지 않는다. <code>wake</code>는 대기자를 실행 가능하게 만들고 스케줄러가 실행 시점을 정한다. 이 대기 연산은 해당 스레드에게 소유권이나 사용권이 전달되었을 때 복귀하며, 깨우기 이전의 상태 변경을 복귀한 스레드가 관찰할 수 있도록 메모리 순서도 연결한다.<ref name="wait-implementation">[https://mit-pdos.github.io/xv6-riscv-book/sleep.html MIT xv6: Sleep and Wakeup], Sleep and wakeup의 lost wakeup 방지와 락 규약.</ref> | ||
=== 뮤텍스의 소유권 전달 === | === 뮤텍스의 소유권 전달 === | ||
| 114번째 줄: | 114번째 줄: | ||
순서 A B owner / 대기열 | 순서 A B owner / 대기열 | ||
1 lock 성공 A / [] | 1 lock 성공 A / [] | ||
2 lock 시도 | 2 lock 시도 -> 대기 A / [B] | ||
3 unlock: 소유권을 B로 B / [] | 3 unlock: 소유권을 B로 B / [] | ||
4 wake(B) 실행 가능 B / [] | 4 wake(B) 실행 가능 B / [] | ||
| 157번째 줄: | 157번째 줄: | ||
초기 1 / [] | 초기 1 / [] | ||
1 wait: 사용권 획득 0 / [] | 1 wait: 사용권 획득 0 / [] | ||
2 wait | 2 wait -> 대기 0 / [B] | ||
3 post: B에 사용권 전달 0 / [] | 3 post: B에 사용권 전달 0 / [] | ||
4 wake(B) 실행 가능 0 / [] | 4 wake(B) 실행 가능 0 / [] | ||
| 164번째 줄: | 164번째 줄: | ||
</pre> | </pre> | ||
대기자를 깨우는 분기에서는 count를 늘리지 않는다. 사용권을 대기자에게 넘긴 뒤에도 count를 올려 두면, 다른 스레드가 같은 사용권을 다시 가져갈 수 있기 때문이다. 대기자가 획득 호출에서 돌아올 때 count를 다시 줄이지 않는 이유도 같다. 이미 자신에게 예약된 사용권을 받은 것이다. 이 구현에서 | 대기자를 깨우는 분기에서는 count를 늘리지 않는다. 사용권을 대기자에게 넘긴 뒤에도 count를 올려 두면, 다른 스레드가 같은 사용권을 다시 가져갈 수 있기 때문이다. 대기자가 획득 호출에서 돌아올 때 count를 다시 줄이지 않는 이유도 같다. 이미 자신에게 예약된 사용권을 받은 것이다. 이 구현에서 count는 현재 누구에게도 예약되지 않은 사용권의 수다. | ||
뮤텍스와 세마포어 모두 원자 연산으로 내부 상태를 안전하게 바꾸고, 기다리는 실행 흐름을 운영체제의 | 뮤텍스와 세마포어 모두 원자 연산으로 내부 상태를 안전하게 바꾸고, 기다리는 실행 흐름을 운영체제의 대기, 깨우기와 연결한다. 하드웨어는 guard의 원자적 갱신을 지원하지만, 소유권, 수량의 의미와 대기열 관리, 다음 실행 대상의 선택은 소프트웨어가 구현한다. | ||
== 락의 상호 배제와 메모리 순서 == | == 락의 상호 배제와 메모리 순서 == | ||
락에는 메모리의 가시성과 순서를 연결하는 역할도 있다. 올바른 동기화 규약 아래에서 락을 해제하기 전의 변경은 같은 락을 이어서 획득한 작업에 전달된다. 단순히 실행 시간이 앞섰다는 사실만으로는 이런 관계가 생기지 않는다. 컴파일러와 하드웨어가 허용하는 재배치를 고려한 동기화가 필요하다. 서로 다른 스레드가 같은 메모리 위치에 접근하고 한쪽 이상이 쓰기일 때, 적어도 하나가 비원자적이며 동기화로 순서가 정해지지 않으면 데이터 레이스(Data Race)가 된다. C에서 데이터 레이스는 정의되지 않은 동작을 일으킨다. 반면 앞의 재고 예시처럼 개별 읽기와 쓰기를 원자적으로 만들더라도, 확인과 갱신을 따로 수행하면 전체 결과가 잘못될 수 있다 | 락에는 메모리의 가시성과 순서를 연결하는 역할도 있다. 올바른 동기화 규약 아래에서 락을 해제하기 전의 변경은 같은 락을 이어서 획득한 작업에 전달된다. 단순히 실행 시간이 앞섰다는 사실만으로는 이런 관계가 생기지 않는다. 컴파일러와 하드웨어가 허용하는 재배치를 고려한 동기화가 필요하다. 서로 다른 스레드가 같은 메모리 위치에 접근하고 한쪽 이상이 쓰기일 때, 적어도 하나가 비원자적이며 동기화로 순서가 정해지지 않으면 데이터 레이스(Data Race)가 된다. C에서 데이터 레이스는 정의되지 않은 동작을 일으킨다. 반면 앞의 재고 예시처럼 개별 읽기와 쓰기를 원자적으로 만들더라도, 확인과 갱신을 따로 수행하면 전체 결과가 잘못될 수 있다. <ref name="source-1">[https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf C11 위원회 초안 N1570, 5.1.2.4].</ref> | ||
원자 연산(Atomic Operation)인 증가나 비교 후 교환(CAS)은 하나의 연산이 중간에 쪼개져 관찰되는 문제를 해결한다. 그러나 재고 차감과 승인 기록을 각각 원자적으로 바꿔도 두 필드의 관계가 저절로 보호되지는 않는다. 원자성의 범위와 불변식의 범위가 다르기 때문이다. 여러 값을 하나의 상태로 묶거나 별도의 프로토콜을 설계할 수 있지만, 그 정확성과 실패 시 재시도 비용까지 부담해야 한다. | 원자 연산(Atomic Operation)인 증가나 비교 후 교환(CAS)은 하나의 연산이 중간에 쪼개져 관찰되는 문제를 해결한다. 그러나 재고 차감과 승인 기록을 각각 원자적으로 바꿔도 두 필드의 관계가 저절로 보호되지는 않는다. 원자성의 범위와 불변식의 범위가 다르기 때문이다. 여러 값을 하나의 상태로 묶거나 별도의 프로토콜을 설계할 수 있지만, 그 정확성과 실패 시 재시도 비용까지 부담해야 한다. | ||
| 195번째 줄: | 195번째 줄: | ||
</pre> | </pre> | ||
* | * x86-64: 공유 메모리 대상의 <code>LOCK CMPXCHG</code>로 CAS를 구현할 수 있다. <code>LOCK</code> 접두사는 다중 프로세서에서 원자성을 보장한다.<ref name="concurrency-intel-cmpxchg">[https://cdrdv2.intel.com/v1/dl/getContent/671199 Intel SDM Volume 2A], "CMPXCHG: Compare and Exchange".</ref> | ||
* | * RISC-V RV64: A 확장의 <code>LR/SC</code>로 값을 읽어 비교한 뒤 조건부 저장하고, 저장 실패 시 재시도하여 CAS를 구성할 수 있다. <code>SC</code>는 다른 작업의 값 변경이 없어도 실패할 수 있다. 다른 방법인 <code>AMOSWAP.W.AQ</code>는 1을 무조건 교환하여 이전 값이 0인 작업만 진입시키는 test-and-set 방식이다.<ref name="concurrency-riscv-a">[https://docs.riscv.org/reference/isa/unpriv/a-st-ext.html RISC-V Unprivileged ISA, A Extension], LR/SC, AMO 및 상호 배제 예제.</ref> | ||
acquire/release는 앞 소유자의 변경을 다음 소유자가 관찰하도록 순서를 연결하며, 컴파일러와 하드웨어 양쪽에서 보장되어야 한다. RISC-V에서는 <code>aq</code>/<code>rl</code> 또는 필요한 <code>FENCE</code>로 순서를 구현한다.<ref name="concurrency-riscv-a" /> | |||
이 스핀락(Spinlock)은 대기 중에도 CPU를 쓰고, 반복적인 원자적 갱신은 캐시 일관성 트래픽을 늘릴 수 있으며, 획득 순서의 공정성을 보장하지 않는다. 이 비용은 아래의 [[#대기 방식과 비용|대기 방식]]과 [[#데드락(Deadlock)|진행 보장]] 문제로 이어진다. | 이 스핀락(Spinlock)은 대기 중에도 CPU를 쓰고, 반복적인 원자적 갱신은 캐시 일관성 트래픽을 늘릴 수 있으며, 획득 순서의 공정성을 보장하지 않는다. 이 비용은 아래의 [[#대기 방식과 비용|대기 방식]]과 [[#데드락(Deadlock)|진행 보장]] 문제로 이어진다. | ||
== 대기 방식과 비용 == | == 대기 방식과 비용 == | ||
스핀락도 상호 배제를 위한 락이지만 기다리는 동안 CPU에서 획득을 반복 시도한다. | 스핀락도 상호 배제를 위한 락이지만 기다리는 동안 CPU에서 획득을 반복 시도한다. 뮤텍스, 세마포어가 무엇을 조정하는지와, 구현이 스핀하거나 대기 스레드를 재우는지는 구별해야 한다. | ||
락을 얻지 못했을 때 스핀 방식은 실행을 계속하며 획득 가능 여부를 확인한다. 아주 짧은 기다림이라면 잠들고 다시 실행되는 비용을 피할 수 있다. 반면 대기가 길면 유용한 일을 하지 못하면서 CPU 시간과 전력을 소비한다. 락 소유자가 실행되지 못하는 상황에서는 기다리는 쪽이 바쁘게 실행되어도 해제 시점을 앞당기지 못한다. <ref name="source-2">[https://docs.oracle.com/cd/E19253-01/816-5137/ggecq/index.html Oracle: Using Spin Locks].</ref> | 락을 얻지 못했을 때 스핀 방식은 실행을 계속하며 획득 가능 여부를 확인한다. 아주 짧은 기다림이라면 잠들고 다시 실행되는 비용을 피할 수 있다. 반면 대기가 길면 유용한 일을 하지 못하면서 CPU 시간과 전력을 소비한다. 락 소유자가 실행되지 못하는 상황에서는 기다리는 쪽이 바쁘게 실행되어도 해제 시점을 앞당기지 못한다. <ref name="source-2">[https://docs.oracle.com/cd/E19253-01/816-5137/ggecq/index.html Oracle: Using Spin Locks].</ref> | ||
블로킹(Blocking) 방식은 기다리는 작업을 재우고 CPU를 다른 작업에 내준다. 대신 대기 등록, 깨우기, 다시 스케줄되는 과정이 필요하다. | 블로킹(Blocking) 방식은 기다리는 작업을 재우고 CPU를 다른 작업에 내준다. 대신 대기 등록, 깨우기, 다시 스케줄되는 과정이 필요하다. 선택할 때는 예상 대기 시간과 실행 여건을 비교해야 한다. 실제 뮤텍스는 짧게 스핀한 뒤 블로킹하는 전략을 섞을 수도 있다. | ||
락 하나로 큰 구조를 보호하면 규칙이 단순하지만 서로 무관한 작업도 줄을 선다. 락을 세분화하면 병렬 처리 여지는 커지지만 획득 횟수와 관리할 관계도 늘어난다. 임계 구역 안에 오래 걸리는 작업을 넣으면 대기가 늘고, 밖으로 옮기면 그 사이 상태가 바뀌지 않는지 다시 확인해야 한다. 락 범위를 줄이는 최적화는 불변식의 보호 범위를 보존할 때만 의미가 있다. | 락 하나로 큰 구조를 보호하면 규칙이 단순하지만 서로 무관한 작업도 줄을 선다. 락을 세분화하면 병렬 처리 여지는 커지지만 획득 횟수와 관리할 관계도 늘어난다. 임계 구역 안에 오래 걸리는 작업을 넣으면 대기가 늘고, 밖으로 옮기면 그 사이 상태가 바뀌지 않는지 다시 확인해야 한다. 락 범위를 줄이는 최적화는 불변식의 보호 범위를 보존할 때만 의미가 있다. | ||
| 213번째 줄: | 213번째 줄: | ||
== 데드락(Deadlock) == | == 데드락(Deadlock) == | ||
데드락은 작업들이 서로가 제공해야 할 자원이나 사건을 기다려 더 이상 진행하지 못하는 상태다. 여기서는 스레드가 뮤텍스를 보유한 채 다른 뮤텍스를 기다리는 경우를 살펴본다. 락으로 임계 구역을 보호해 데이터 레이스를 없앴더라도, 락을 획득하는 순서가 잘못되면 데드락이 생길 수 있다. 즉, 공유 데이터의 안전성과 작업의 진행 가능성은 따로 확인해야 한다. | |||
=== 두 스레드와 두 뮤텍스 === | === 두 스레드와 두 뮤텍스 === | ||
| 235번째 줄: | 235번째 줄: | ||
</pre> | </pre> | ||
화살표는 | 화살표는 기다리는 스레드에서 필요한 락의 소유자로 향한다. A가 진행하려면 B가 주문 락을 해제해야 하지만, B도 A가 재고 락을 해제해야 진행할 수 있다. 두 스레드 모두 해제 코드에 도달하지 못한다. 다른 순서로 실행하면 문제가 드러나지 않을 수 있지만, 한 번 이 상태가 되면 단순히 오래 기다리거나 CPU 실행 순서를 바꾸는 것으로 풀리지 않는다. 스케줄러는 CPU를 배분할 뿐, 보유 중인 뮤텍스를 안전하게 대신 해제해 주지 않는다. 일반적인 블로킹 뮤텍스 획득은 다른 소유자가 락을 해제할 때까지 기다린다.<ref name="oracle-mutex">Oracle, [https://docs.oracle.com/cd/E19253-01/816-5137/sync-110/index.html Using Mutual Exclusion Locks], ''Multithreaded Programming Guide''.</ref> | ||
=== 데드락의 네 가지 필요조건 === | === 데드락의 네 가지 필요조건 === | ||
자원을 획득하고 반납하는 모델에서 데드락이 발생하려면 다음 네 조건이 함께 성립해야 한다. 이를 | 자원을 획득하고 반납하는 모델에서 데드락이 발생하려면 다음 네 조건이 함께 성립해야 한다. 이를 코프먼 조건(Coffman Conditions)이라고 한다.<ref name="illinois-deadlock">University of Illinois, [https://cs341.cs.illinois.edu/coursebook/Deadlock Deadlock], CS 341 Coursebook, "Resource Allocation Graphs", "Coffman Conditions".</ref> | ||
# | # 상호 배제(Mutual Exclusion): 해당 자원을 한 번에 하나의 작업만 사용할 수 있다. 예제의 각 뮤텍스는 소유자가 하나다. | ||
# | # 점유 대기(Hold and Wait): 자원을 이미 보유한 상태로 다른 자원을 기다린다. A와 B 모두 첫 번째 락을 놓지 않고 두 번째 락을 기다린다. | ||
# | # 비선점(No Preemption): 다른 작업이 보유한 자원을 강제로 회수하지 못한다. 여기서 비선점은 뮤텍스 등 보유 자원의 강제 회수를 금지한다는 뜻이다. | ||
# | # 순환 대기(Circular Wait): 각 작업이 다음 작업이 보유한 자원을 기다리고, 그 연결이 다시 처음으로 돌아온다. 예제에서는 A -> B -> A다. | ||
어느 하나라도 성립하지 않도록 설계하면 이 모델의 데드락을 예방할 수 있다 | 어느 하나라도 성립하지 않도록 설계하면 이 모델의 데드락을 예방할 수 있다. 위 예제처럼 각 자원이 하나뿐인 뮤텍스 모델에서 실제 대기 고리가 생기면 데드락이다. <ref name="illinois-deadlock" /> | ||
=== 예방과 다른 진행 실패의 구별 === | === 예방과 다른 진행 실패의 구별 === | ||
가장 직접적인 예방책은 | 가장 직접적인 예방책은 락 획득 순서를 통일하는 것이다. 모든 경로에서 재고 락 다음 주문 락을 획득하게 하면, 주문 락을 보유한 채 재고 락을 기다리는 역방향 연결이 생기지 않아 순환 대기가 끊어진다. 락이 늘어나면 전체 순서를 정하고 중첩 획득 때 이를 지킨다. 보유한 락보다 뒤 순서의 락만 요청하게 하면 처음 락으로 되돌아오는 요청 고리를 만들 수 없다. 일부 함수만 순서를 지켜서는 부족하며, 호출되는 함수가 내부에서 획득하는 락도 포함해야 한다.<ref name="oracle-lock-hierarchy" /> | ||
순서를 지키기 어려운 경우에는 두 번째 락을 <code>try_lock</code>으로 시도하고, 실패하면 이미 획득한 락을 해제한 뒤 다시 시도할 수 있다. | 순서를 지키기 어려운 경우에는 두 번째 락을 <code>try_lock</code>으로 시도하고, 실패하면 이미 획득한 락을 해제한 뒤 다시 시도할 수 있다. 재시도 과정에서는 부분적으로 수행한 작업을 안전하게 취소하거나 상태를 다시 검사해야 하며, 반복 획득과 해제에도 비용이 든다.<ref name="oracle-lock-hierarchy" /> | ||
서로 양보하고 다시 시도하는 동작만 반복해 작업을 끝내지 못하면 라이브락(Livelock)이다. 다른 스레드들은 진행하지만 특정 스레드만 계속 자원을 얻지 못하면 기아(Starvation)다. 데드락은 대기 의존성이 풀리지 않는 문제, 라이브락은 동작은 계속하지만 유효한 진전이 없는 문제, 기아는 특정 작업의 진전이 계속 배제되는 문제라는 차이가 있다.<ref name="oracle-starvelive">Oracle, [https://docs.oracle.com/javase/tutorial/essential/concurrency/starvelive.html Starvation and Livelock], ''The Java Tutorials''.</ref> | |||
== 조건 변수와 상태 변화 대기 == | == 조건 변수와 상태 변화 대기 == | ||
재고가 들어올 때까지 기다리는 주문은 또 다른 문제다. 락을 잡은 채 기다리면 입고 작업도 재고를 바꾸지 못한다. 조건 변수(Condition Variable)는 락 해제와 대기 진입을 연결하고, 깨어난 뒤 락을 다시 획득하도록 한다. 조건을 확인한 직후 입고 알림이 지나가고 그다음 잠드는 | 재고가 들어올 때까지 기다리는 주문은 또 다른 문제다. 락을 잡은 채 기다리면 입고 작업도 재고를 바꾸지 못한다. 조건 변수(Condition Variable)는 락 해제와 대기 진입을 연결하고, 깨어난 뒤 락을 다시 획득하도록 한다. 조건을 확인한 직후 입고 알림이 지나가고 그다음 잠드는 '놓친 깨우기'를 피하려면, 조건 확인과 상태 변경도 같은 뮤텍스 규약으로 묶어야 한다. | ||
세마포어는 사용권이나 통지의 수를 저장하지만, 조건 변수의 알림은 나중을 위해 누적되지 않는다. 조건 변수와 함께 쓰는 실제 조건은 재고 수처럼 뮤텍스로 보호하는 별도의 상태에 있으며, 깨어난 작업은 이를 다시 검사한다.<ref name="cond-notification">[https://man7.org/linux/man-pages/man3/pthread_cond_broadcast.3p.html POSIX pthread_cond_broadcast()], 대기자가 없을 때의 알림.</ref> | 세마포어는 사용권이나 통지의 수를 저장하지만, 조건 변수의 알림은 나중을 위해 누적되지 않는다. 조건 변수와 함께 쓰는 실제 조건은 재고 수처럼 뮤텍스로 보호하는 별도의 상태에 있으며, 깨어난 작업은 이를 다시 검사한다.<ref name="cond-notification">[https://man7.org/linux/man-pages/man3/pthread_cond_broadcast.3p.html POSIX pthread_cond_broadcast()], 대기자가 없을 때의 알림.</ref> | ||
대기 코드는 | 대기 코드는 '재고가 없는 동안 기다린다'라는 while 구조여야 한다. 깨어나도 다른 주문이 재고를 먼저 가져갈 수 있고, 알림 없이 깨어나는 스퓨리어스 웨이크업(Spurious Wakeup)도 가능하다. 알림을 받은 작업은 조건을 다시 검사한다. <ref name="source-4">[https://docs.oracle.com/cd/E88353_01/html/E37843/pthread-cond-wait-3c.html Oracle: pthread_cond_wait].</ref> | ||
== 읽기 중심의 동기화와 RCU == | == 읽기 중심의 동기화와 RCU == | ||
읽기는 매우 잦지만 갱신은 드문 자료구조에서는 독자가 매번 같은 락을 다투는 비용도 커질 수 있다. Linux에서 사용하는 | 읽기는 매우 잦지만 갱신은 드문 자료구조에서는 독자가 매번 같은 락을 다투는 비용도 커질 수 있다. Linux에서 사용하는 RCU(Read-Copy Update)는 읽기 쪽의 부담을 줄이기 위한 동기화 방식이다. 갱신자는 새 상태를 공개하거나 이전 객체를 자료구조에서 떼어 낼 수 있지만, 이미 그 객체를 보고 있던 독자가 남아 있다면 바로 메모리를 해제해서는 안 된다. RCU는 자료구조의 변경과 이전 객체의 메모리 회수 시점을 분리하여 이 수명 문제를 다룬다.<ref name="rcu-overview">[https://docs.kernel.org/RCU/whatisRCU.html Linux kernel documentation: What is RCU?], 제거와 회수의 분리.</ref> | ||
갱신자 사이의 충돌, 독자가 관찰할 수 있는 상태, 객체를 참조해도 되는 기간에는 별도의 규칙이 필요하다. 구체적인 읽기 구간과 공개, 회수 절차는 [[운영체제 기본/Linux/RCU|Linux의 RCU]] 각론에서 다룬다. | |||
== 참고 문헌 == | == 참고 문헌 == | ||
| 271번째 줄: | 271번째 줄: | ||
{{이전 다음 문서 | {{이전 다음 문서 | ||
|이전= | |이전=이전 문서<br />[[운영체제 기본/프로세스와 스레드|프로세스와 스레드]] | ||
|목차=[[운영체제 기본#총론|총론 목차]] | |목차=[[운영체제 기본#총론|총론 목차]] | ||
|다음=다음 문서 | |다음=다음 문서<br />[[운영체제 기본/가상 메모리|가상 메모리]] | ||
}} | }} | ||
{{운영체제 기본 둘러보기}} | {{운영체제 기본 둘러보기}} | ||