협력적 프로세스는 시스템 안에서 실행 중인 다른 프로세스에 영향을 주거나
다른 프로세스의 영향을 받을 수 있는 프로세스.
협력적 프로세스는 논리 주소 공간을 직접 공유할 수도 있음.
또는 공유 메모리나 메시지 전달을 통해 자료를 공유할 수도 있음.
공유 자료에 여러 프로세스가 동시에 접근하면 데이터 불일치가 발생할 수 있음.
데이터의 일관성을 유지하려면 협력적 프로세스들이 정해진 순서에 따라 실행되도록 보장하는 기법이 필요함.
이러한 실행 순서와 접근 시점을 조정하는 기법이 동기화.
생산자 프로세스와 소비자 프로세스는 공통 버퍼를 공유함.
생산자는 버퍼에 항목을 넣는 역할.
소비자는 버퍼에서 항목을 꺼내는 역할.
유한 버퍼에서는 버퍼가 가득 차면 생산자가 기다려야 함.
또한 버퍼가 비어 있으면 소비자가 기다려야 함.
원형 버퍼 구현에서는 in과 out 변수를 사용함.
in은 생산자가 다음 항목을 넣을 위치.
out은 소비자가 다음 항목을 꺼낼 위치.
이 방식에서는 in과 out의 값으로 버퍼의 상태를 판단함.
하지만 이 구조는 최대 BUFFER_SIZE - 1개의 항목만 저장할 수 있음.
버퍼가 완전히 찬 상태와 완전히 빈 상태를 구분하기 위해 한 칸을 비워 두는 방식이기 때문.
버퍼 안에 들어 있는 항목 수를 정확히 관리하려면 count 변수를 사용할 수 있음.
count는 버퍼에 현재 들어 있는 항목의 개수를 나타내는 공유 변수.
count가 0이면 버퍼가 비어 있는 상태.
count가 BUFFER_SIZE이면 버퍼가 가득 찬 상태.
생산자는 새 항목을 버퍼에 넣은 뒤 count 값을 증가시킴.
소비자는 항목을 버퍼에서 꺼낸 뒤 count 값을 감소시킴.
생산자 코드에서는 count++ 연산이 사용될 수 있음.
소비자 코드에서는 count-- 연산이 사용될 수 있음.
count++는 count 값을 레지스터로 읽고, 레지스터 값을 1 증가시키고, 다시 count에 저장하는 과정.
count--는 count 값을 레지스터로 읽고, 레지스터 값을 1 감소시키고, 다시 count에 저장하는 과정.
이때 생산자와 소비자가 병행 실행되면 두 명령어 묶음이 서로 섞여 실행될 수 있음.
예를 들어 count의 초기값이 5라고 가정함.
생산자가 count 값을 읽어 register1에 5를 저장함.
소비자도 count 값을 읽어 register2에 5를 저장함.
생산자가 register1 값을 6으로 증가시킴.
소비자가 register2 값을 4로 감소시킴.
생산자가 count에 6을 저장함.
소비자가 count에 4를 저장함.
이 경우 최종 count 값은 4가 됨.
반대로 소비자가 먼저 count에 4를 저장하고 생산자가 나중에 count에 6을 저장하면 최종 count 값은 6이 됨.
하지만 논리적으로 생산자 한 번과 소비자 한 번이 각각 실행되었다면 count 값은 다시 5가 되어야 함.
count++와 count--가 모두 실행되었는데도 결과가 5가 아니라 4 또는 6이 될 수 있음.
이 문제는 두 프로세스의 명령어 실행 순서가 섞였기 때문에 발생함.
이처럼 여러 프로세스가 같은 자료를 동시에 접근하고 조작할 때
실행 결과가 접근 순서에 따라 달라지는 상황을 경쟁 조건이라고 함.
경쟁 조건은 공유 자료에 대한 병행 접근이 적절히 제어되지 않을 때 발생함.
경쟁 조건을 막으려면 한 순간에 오직 하나의 프로세스만 공유 자료를 조작하도록 보장해야 함.
생산자와 소비자가 count를 동시에 갱신하지 못하게 해야 하는 것.
이러한 보장을 제공하는 것이 프로세스 동기화의 핵심.
운영체제 내부에서도 경쟁 조건은 중요한 문제.
커널 안의 여러 자료구조는 여러 프로세스나 여러 스레드에 의해 동시에 접근될 수 있음.
예를 들어 프로세스 테이블, 열린 파일 테이블, 메모리 할당 자료구조, 입출력 큐 같은 자료구조는
여러 실행 흐름이 동시에 접근할 수 있음.
커널 자료구조가 경쟁 조건에 노출되면 시스템 전체의 안정성이 깨질 수 있음.
따라서 운영체제는 사용자 프로그램뿐 아니라 커널 내부에서도 동기화 기법을 사용해야 함.
임계구역 문제
n개의 프로세스가 존재한다고 가정함.
각 프로세스는 공유 자료에 접근하는 코드 부분을 가질 수 있음.
이 공유 자료는 공통 변수, 테이블, 파일, 버퍼 등이 될 수 있음.
각 프로세스에서 공유 자료를 접근하고 갱신하는 코드 부분을 임계구역이라고 함.
임계구역에서는 공유 자료를 읽거나 쓰거나 수정하는 작업이 수행됨.
임계구역 문제의 핵심은 한 프로세스가 자신의 임계구역에서 실행 중일 때
다른 프로세스가 자신의 임계구역에 들어가지 못하게 하는 것.
두 프로세스가 동시에 임계구역 안에서 실행되지 않도록 보장해야 함.
각 프로세스는 임계구역에 들어가기 전에 진입 구역을 실행함.
진입 구역은 임계구역에 들어가도 되는지 검사하고 허가를 받는 코드 부분.
임계구역 실행이 끝나면 퇴출 구역을 실행함.
퇴출 구역은 임계구역 사용이 끝났음을 알리고 다른 프로세스가 들어올 수 있도록 하는 코드 부분.
그 밖의 코드는 나머지 구역이라고 함.
나머지 구역은 공유 자료를 직접 갱신하지 않는 일반 코드 부분.
프로세스의 일반적인 구조는 진입 구역, 임계구역, 퇴출 구역, 나머지 구역으로 구성됨.
각 프로세스는 이 구조를 반복적으로 실행할 수 있음.
임계구역 문제에 대한 해결안은 세 가지 요구 조건을 만족해야 함.
첫 번째 조건은 상호 배제
상호 배제는 한 프로세스가 임계구역에서 실행 중이면 다른 프로세스는 자신의 임계구역에서 실행될 수 없다는 조건.
상호 배제는 공유 자료가 동시에 수정되는 것을 막기 위한 기본 조건.
두 번째 조건은 진행
진행은 임계구역에서 실행 중인 프로세스가 없고, 어떤 프로세스들이 임계구역에 들어가기를 원할 때 적용되는 조건.
이때 다음에 임계구역에 들어갈 프로세스를 선택하는 결정은
나머지 구역에서 실행 중이지 않은 프로세스들만 참여해야 함.
또한 이 결정은 무한정 연기되어서는 안 됨.
진행 조건은 임계구역이 비어 있는데도 아무도 들어가지 못하는 상황을 막기 위한 조건.
들어가고자 하는 프로세스가 있으면 결국 누군가는 들어갈 수 있어야 한다는 의미.
세 번째 조건은 한정 대기
한정 대기는 어떤 프로세스가 임계구역에 들어가겠다고 요청한 뒤,
그 요청이 허용되기 전까지 다른 프로세스들이 임계구역에 들어가는 횟수에 한계가 있어야 한다는 조건.
어떤 프로세스도 무한정 기다려서는 안 됨.
한정 대기 조건은 기아 상태를 막기 위한 조건.
임계구역 문제를 해결할 때는 각 프로세스가 0이 아닌 속도로 실행된다고 가정함.
그러나 프로세스들의 상대적인 실행 속도에 대해서는 어떤 가정도 하지 않음.
어떤 프로세스가 더 빠르거나 느리게 실행될 수 있음.
또한 프로세스들이 어떤 순서로 CPU를 얻는지도 미리 가정하지 않음.
따라서 임계구역 해결안은 실행 속도나 스케줄링 순서에 의존하지 않아야 함.
운영체제에서 임계구역 문제는 커널 자료구조를 보호하는 문제와 직접 연결됨.
커널 코드는 여러 프로세스나 인터럽트 처리 루틴에 의해 병행적으로 실행될 수 있음.
커널 안의 공유 자료구조를 안전하게 갱신하려면 임계구역 보호가 필요함.
커널 접근 방식은 크게 비선점형 커널과 선점형 커널로 나눌 수 있음.
비선점형 커널은 커널 모드에서 실행 중인 프로세스가 커널을 빠져나가거나 봉쇄될 때까지 선점되지 않는 구조.
비선점형 커널에서는 한 순간에 하나의 프로세스만 커널 안에서 실행되므로
커널 자료구조의 경쟁 조건이 상대적으로 단순함.
프로세스가 커널 모드에 있는 동안에는 다른 프로세스가 그 커널 실행을 중간에 빼앗지 못하기 때문.
그러나 비선점형 커널은 실시간 프로세스가 커널 안에서 오래 기다릴 수 있음.
따라서 비선점형 커널은 실시간 시스템에는 적합하지 않을 수 있음.
선점형 커널은 커널 모드에서 실행 중인 프로세스도 선점될 수 있는 구조.
선점형 커널은 실시간 프로세스가 더 빠르게 CPU를 받을 수 있음.
따라서 선점형 커널은 실시간 프로그래밍에 더 적합함.
그러나 선점형 커널에서는 커널 자료구조에 대한 경쟁 조건이 발생할 수 있음.
커널 자료구조를 수정하는 중에 선점이 발생할 수 있기 때문.
따라서 선점형 커널은 공유 커널 자료구조를 보호하기 위한 동기화 장치가 반드시 필요함.
현대 운영체제는 대화형 응답성과 실시간 요구를 위해 선점형 커널을 많이 사용함.
Peterson의 해결안
Peterson의 해결안은 두 프로세스가 임계구역 문제를 해결하기 위한 고전적인 소프트웨어 알고리즘.
이 해결안은 두 프로세스가 load와 store 명령을 원자적으로 실행한다고 가정함.
메모리에서 값을 읽고 쓰는 기본 명령은 중간에 끼어들 수 없다고 가정함.
Peterson의 해결안은 두 프로세스 Pi와 Pj를 대상으로 함.
i와 j는 서로 다른 프로세스 번호.
Peterson의 해결안은 두 개의 공유 변수를 사용함.
하나는 turn 변수.
다른 하나는 flag 배열.
turn 변수는 어느 프로세스가 임계구역에 들어갈 차례인지를 나타냄.
flag 배열은 각 프로세스가 임계구역에 들어가고 싶어 하는지를 나타냄.
flag[i]가 true이면 프로세스 Pi가 임계구역에 들어가고 싶다는 의미.
flag[j]가 true이면 프로세스 Pj가 임계구역에 들어가고 싶다는 의미.
프로세스 Pi는 임계구역에 들어가기 전에 flag[i]를 true로 설정함.
이 설정은 Pi가 임계구역에 들어가려는 의사를 표시하는 것.
그 뒤 turn을 j로 설정함.
이 설정은 상대 프로세스 Pj에게 우선권을 양보하는 것.
이후 Pi는 flag[j]가 true이고 turn이 j인 동안 기다림.
Pj도 임계구역에 들어가고 싶어 하고 차례가 Pj라면 Pi는 기다림.
Pj가 임계구역에 들어가고 싶어 하지 않거나 turn이 i가 되면 Pi는 임계구역에 들어감.
임계구역을 빠져나온 뒤 Pi는 flag[i]를 false로 설정함.
이 설정은 Pi가 더 이상 임계구역에 들어가기를 원하지 않는다는 의미.
프로세스 Pi의 구조는 다음과 같이 설명 가능.
flag[i] = true
turn = j
while flag[j] && turn == j 동안 대기
임계구역 실행
flag[i] = false
나머지 구역 실행
프로세스 Pj도 같은 구조를 대칭적으로 사용함.
Pj는 flag[j]를 true로 설정하고 turn을 i로 설정함.
그 뒤 flag[i]가 true이고 turn이 i인 동안 기다림.
Peterson의 해결안은 상호 배제 조건을 만족함.
두 프로세스가 동시에 임계구역에 들어가려면 flag[i]와 flag[j]가 모두 true여야 함.
이때 turn 값은 i 또는 j 중 하나만 가질 수 있음.
turn이 j이면 Pi가 기다림.
turn이 i이면 Pj가 기다림.
따라서 두 프로세스가 동시에 임계구역에 들어갈 수 없음.
Peterson의 해결안은 진행 조건도 만족함.
임계구역에 아무도 없고 한 프로세스만 들어가기를 원하면 상대방의 flag가 false임.
따라서 그 프로세스는 기다리지 않고 임계구역에 들어갈 수 있음.
두 프로세스가 모두 들어가기를 원하면 turn 값에 따라 하나가 선택됨.
이 선택은 임계구역에 들어가려는 두 프로세스에 의해서만 결정됨.
나머지 구역에 있는 프로세스가 선택을 방해하지 않음.
Peterson의 해결안은 한정 대기 조건도 만족함.
한 프로세스가 임계구역에 들어가려고 기다리는 동안
상대 프로세스가 무한히 반복해서 임계구역에 들어가는 것은 불가능함.
상대 프로세스가 임계구역을 빠져나오면 자신의 flag 값을 false로 바꿈.
또는 다시 들어가려고 할 때 turn 값을 상대에게 양보함.
따라서 기다리는 프로세스는 일정 횟수 이후 임계구역에 들어갈 수 있음.
Peterson의 해결안은 알고리즘적으로 세 가지 요구 조건을 모두 만족하는 좋은 예.
그러나 현대 컴퓨터 구조에서는 Peterson의 해결안이 항상 올바르게 동작한다고 보장하기 어려움.
그 이유는 최신 프로세서와 컴파일러가 성능 향상을 위해 명령어 순서를 재배치할 수 있기 때문.
단일 스레드 관점에서는 결과가 같아 보이도록 순서를 바꿀 수 있음.
그러나 다중 스레드 환경에서는 이런 순서 재배치가 다른 스레드가 관찰하는 메모리 순서를 바꿀 수 있음.
예를 들어 flag 값을 쓰는 명령과 turn 값을 쓰는 명령의 순서가 재배치될 수 있음.
이 경우 Peterson의 알고리즘이 가정한 메모리 접근 순서가 깨질 수 있음.
따라서 현대 시스템에서는 단순한 소프트웨어 알고리즘만으로 동기화를 보장하기 어려움.
이 때문에 실제 운영체제와 프로그래밍 언어는 하드웨어 수준의 원자 명령어와 메모리 순서 보장 장치를 사용함.
동기화를 위한 하드웨어 지원
임계구역 문제는 소프트웨어 알고리즘만으로 해결할 수도 있음.
하지만 현대 운영체제는 일반적으로 하드웨어 지원을 사용함.
하드웨어는 동기화 구현을 위해 여러 기능을 제공함.
대표적인 하드웨어 지원에는 메모리 장벽, 하드웨어 원자 명령어, 원자적 변수가 있음.
이러한 기능들은 임계구역 보호, 락 구현, 세마포 구현 같은 상위 수준 동기화 도구의 기반이 됨.
메모리 장벽
컴퓨터 구조에서는 메모리 변경이 다른 프로세서에 언제 보이는지가 중요함.
메모리 모델은 한 프로세서가 수행한 메모리 변경이 다른 프로세서에 보이는 방식을 정의함.
메모리 모델은 강한 순서와 약한 순서로 나눌 수 있음.
강한 순서 메모리 모델은 한 프로세서의 메모리 변경이 다른 모든 프로세서에 즉시 보이는 구조.
약한 순서 메모리 모델은 한 프로세서의 메모리 변경이 다른 프로세서에 즉시 보이지 않을 수 있는 구조.
현대 프로세서는 성능 향상을 위해 저장 버퍼, 캐시, 명령어 재정렬을 사용함.
이 때문에 한 스레드가 수행한 메모리 연산의 순서가 다른 스레드에게 같은 순서로 보장되지 않을 수 있음.
컴파일러도 성능 최적화를 위해 명령어 순서를 바꿀 수 있음.
단일 스레드 결과가 같다면 컴파일러나 프로세서가 명령어 순서를 조정할 수 있기 때문.
하지만 병행 실행에서는 다른 스레드가 중간 상태를 볼 수 있으므로 문제가 발생할 수 있음.
메모리 장벽은 이러한 문제를 제어하기 위해 사용되는 명령어.
메모리 장벽은 메모리 연산의 순서를 강제로 보장하는 역할.
메모리 장벽 이전의 load와 store 연산은 메모리 장벽 이후의 load와 store 연산보다 먼저 완료되어야 함.
메모리 장벽은 그 앞의 메모리 변경이 다른 프로세서에 보이도록 보장한 뒤 다음 연산이 진행되도록 함.
메모리 장벽은 memory fence라고도 부름.
예를 들어 한 스레드가 데이터를 먼저 저장하고, 그 뒤 데이터가 준비되었다는 flag 값을 true로 바꿀 수 있음.
다른 스레드는 flag가 true인지 확인한 뒤 데이터를 읽을 수 있음.
이때 메모리 재정렬이 발생하면 flag가 먼저 보이고 실제 데이터 저장이 나중에 보일 수 있음.
그러면 다른 스레드는 준비되지 않은 데이터를 읽을 수 있음.
메모리 장벽은 이러한 순서 뒤바뀜을 막기 위해 사용됨.
메모리 장벽을 사용하면 flag를 설정하기 전에 데이터 저장이 먼저 완료되도록 강제할 수 있음.
메모리 장벽은 매우 낮은 수준의 연산.
따라서 일반 응용 프로그래머가 직접 사용하기보다는
운영체제 커널이나 동기화 라이브러리 내부에서 사용되는 경우가 많음.
하드웨어 명령어
많은 시스템은 임계구역 문제를 해결하기 위한 특별한 하드웨어 명령어를 제공함.
이러한 명령어는 하나의 메모리 위치를 검사하고 변경하는 작업을 원자적으로 수행함.
원자적 수행은 명령어가 실행되는 동안 중간에 끼어들 수 없다는 의미.
대표적인 하드웨어 명령어에는 test_and_set과 compare_and_swap이 있음.
test_and_set 명령어는 대상 값을 읽고 그 값을 true로 설정하는 작업을 하나의 원자적 연산으로 수행함.
test_and_set은 원래 값을 반환하면서 동시에 대상 값을 true로 바꿈.
test_and_set의 의미는 다음과 같이 설명 가능.
현재 target 값을 임시 변수에 저장함.
target 값을 true로 변경함.
이전에 저장한 target 값을 반환함.
이 전체 과정은 원자적으로 수행됨.
이 명령어를 사용하면 간단한 상호 배제 락을 만들 수 있음.
공유 변수 lock이 false이면 임계구역이 비어 있다는 의미.
공유 변수 lock이 true이면 누군가 임계구역에 있다는 의미.
프로세스는 임계구역에 들어가기 전에 test_and_set(lock)을 실행함.
test_and_set(lock)의 반환값이 false이면 이전에 락이 비어 있었다는 뜻.
따라서 해당 프로세스는 락을 획득하고 임계구역에 들어감.
test_and_set(lock)의 반환값이 true이면 이미 다른 프로세스가 락을 가지고 있다는 뜻.
따라서 해당 프로세스는 계속 반복하면서 기다림.
임계구역을 빠져나올 때는 lock을 false로 설정함.
test_and_set 기반 락은 상호 배제를 제공할 수 있음.
그러나 기다리는 프로세스가 반복적으로 lock을 검사하므로 바쁜 대기가 발생함.
compare_and_swap 명령어는 대상 값이 예상 값과 같으면 새 값으로 바꾸는 원자적 연산.
대상 값이 예상 값과 다르면 값을 바꾸지 않음.
compare_and_swap은 기존 값을 반환함.
compare_and_swap의 의미는 다음과 같이 설명 가능.
현재 value 값을 임시 변수에 저장함.
현재 value 값이 expected 값과 같으면 value를 new_value로 변경함.
임시 변수에 저장해 둔 이전 value 값을 반환함.
이 전체 과정은 원자적으로 수행됨.
compare_and_swap을 사용하면 lock 값이 0일 때만 1로 바꾸는 방식으로 락을 구현할 수 있음.
lock이 0이면 임계구역이 비어 있는 상태.
lock이 1이면 임계구역이 사용 중인 상태.
프로세스는 compare_and_swap(lock, 0, 1)을 실행함.
반환값이 0이면 lock 값이 0에서 1로 바뀐 것이므로 락 획득 성공.
반환값이 0이 아니면 다른 프로세스가 이미 lock을 가지고 있으므로 대기.
임계구역을 빠져나올 때는 lock 값을 0으로 설정함.
compare_and_swap 기반 락도 상호 배제를 제공할 수 있음.
하지만 단순한 compare_and_swap 락도 바쁜 대기를 유발할 수 있음.
또한 단순한 락 구현은 한정 대기를 보장하지 않을 수 있음.
어떤 프로세스가 계속 락 획득에 실패하면 기아 상태가 발생할 수 있음.
한정 대기를 보장하려면 waiting 배열 같은 추가 구조를 사용할 수 있음.
waiting[i]는 프로세스 Pi가 임계구역에 들어가기를 기다리는지를 나타냄.
프로세스는 자신이 기다리고 있음을 waiting[i]에 표시함.
그 뒤 compare_and_swap을 사용하여 lock을 획득하려고 시도함.
임계구역을 빠져나올 때는 waiting 배열을 검사하여 다음에 들어갈 프로세스를 선택할 수 있음.
이 방식은 단순한 락보다 복잡하지만 한정 대기를 보장하는 데 도움이 됨.
하드웨어 명령어는 상호 배제를 쉽게 구현할 수 있게 함.
하지만 하드웨어 명령어만 직접 사용하는 방식은 여전히 복잡하고 오류 가능성이 있음.
따라서 실제 운영체제는 하드웨어 원자 명령어를 바탕으로
Mutex 락, 세마포, 모니터 같은 더 높은 수준의 동기화 도구를 구현함.
원자적 변수
원자적 변수는 정수나 불리언 같은 기본 자료형에 대한 연산을 원자적으로 수행할 수 있게 하는 동기화 도구.
원자적 변수에 대한 연산은 중간에 다른 스레드가 끼어들 수 없음.
예를 들어 atomic increment 연산은 변수 값을 읽고, 증가시키고, 다시 저장하는 과정을
하나의 원자적 연산으로 수행함.
원자적 변수는 counter 같은 단순 공유 변수 갱신에 유용함.
생산자-소비자 예제에서 count 값을 원자적으로 증가시키거나 감소시키면 단순한 갱신 경쟁 조건을 줄일 수 있음.
원자적 변수는 보통 compare_and_swap 같은 하드웨어 명령어를 사용하여 구현됨.
예를 들어 atomic increment는 현재 값을 읽고,
새 값을 계산한 뒤 compare_and_swap으로 현재 값이 변하지 않았을 때만 갱신하는 방식으로 구현될 수 있음.
만약 compare_and_swap이 실패하면 다른 스레드가 값을 바꾼 것이므로 다시 시도함.
이러한 반복을 통해 최종적으로 안전한 갱신을 수행함.
원자적 변수는 단일 변수의 단순 갱신에는 효과적임.
그러나 복잡한 임계구역 전체를 보호하는 데는 충분하지 않을 수 있음.
여러 자료구조를 함께 변경해야 하는 경우에는 단일 atomic 연산만으로는 부족함.
이 경우 Mutex 락이나 세마포 같은 더 높은 수준의 동기화 도구가 필요함.
원자적 변수는 동기화 도구의 구성 요소로도 사용됨.
운영체제와 동기화 라이브러리는 원자적 연산을 기반으로 락, 조건 변수, 세마포 등을 구현할 수 있음.
Mutex 락
Mutex 락은 임계구역 문제를 해결하기 위한 가장 단순한 소프트웨어 도구.
Mutex는 mutual exclusion의 줄임말.
상호 배제를 제공하기 위해 사용되는 락.
프로세스는 임계구역에 들어가기 전에 반드시 락을 획득해야 함.
임계구역을 빠져나올 때는 락을 반환해야 함.
Mutex 락은 acquire 함수와 release 함수로 사용됨.
acquire 함수는 락을 얻는 연산.
release 함수는 락을 놓는 연산.
락이 사용 가능하면 acquire는 락을 획득하고 바로 반환함.
락이 이미 다른 프로세스에 의해 사용 중이면 acquire는 락이 사용 가능해질 때까지 기다림.
release는 락을 사용 가능 상태로 바꾸는 연산.
Mutex 락은 내부적으로 available이라는 불리언 변수를 가질 수 있음.
available이 true이면 락을 얻을 수 있는 상태.
available이 false이면 락이 이미 사용 중인 상태.
acquire의 기본 구조는 다음과 같이 설명 가능.
while available == false 동안 대기.
available = false.
release의 기본 구조는 다음과 같이 설명 가능.
available = true.
acquire와 release 함수는 원자적으로 수행되어야 함.
acquire 실행 중에 다른 프로세스가 동시에 available 값을 변경하면 락 자체가 경쟁 조건에 빠질 수 있음.
따라서 acquire와 release는 보통 compare_and_swap 같은 하드웨어 원자 명령어를 사용하여 구현됨.
Mutex 락을 사용하는 프로세스의 일반적인 구조는 다음과 같음.
acquire 실행.
임계구역 실행.
release 실행.
나머지 구역 실행.
Mutex 락의 단점은 바쁜 대기.
프로세스가 임계구역에 들어가기를 기다리는 동안 acquire 안에서 계속 반복문을 실행할 수 있음.
이 방식은 spinlock이라고도 부름.
spinlock은 락을 얻을 때까지 프로세스가 회전하듯 계속 검사하는 구조.
바쁜 대기는 CPU 시간을 낭비할 수 있음.
특히 단일 처리기 시스템에서는 락을 가진 프로세스가 실행되어 락을 놓아야 함.
그런데 기다리는 프로세스가 CPU를 사용하며 반복하면 비효율적일 수 있음.
그러나 spinlock이 항상 나쁜 것은 아님.
다중 처리기 시스템에서는 한 처리기에서 기다리는 동안
다른 처리기에서 락을 가진 스레드가 임계구역을 끝내고 락을 놓을 수 있음.
임계구역이 매우 짧다면 문맥 교환을 하는 비용보다 잠깐 바쁜 대기하는 비용이 더 작을 수 있음.
따라서 spinlock은 짧은 시간 동안만 락을 보유하는 커널 코드에서 유용할 수 있음.
Spinlock은 프로세스를 봉쇄하고 다시 깨우는 문맥 교환 오버헤드를 피할 수 있음.
운영체제 커널은 다중 코어 환경에서 짧은 임계구역을 보호하기 위해 spinlock을 자주 사용함.
그러나 임계구역이 길거나 락 대기 시간이 길다면 바쁜 대기 방식은 비효율적임.
이 경우 기다리는 프로세스를 대기 큐에 넣고 CPU를 다른 프로세스에 양보하는 방식이 더 적절함.
Mutex 락은 단순하고 구현하기 쉽지만, 사용 방식에 따라 CPU 낭비가 발생할 수 있음.
따라서 락의 보유 시간이 짧은지 긴지에 따라 spinlock과 blocking lock 중 적절한 방식이 선택되어야 함.
세마포
세마포는 Mutex 락보다 더 일반적인 동기화 도구.
세마포는 정수 변수로 표현됨.
세마포 값은 초기화 이후 wait와 signal 두 원자적 연산을 통해서만 접근할 수 있음.
wait 연산은 전통적으로 P 연산이라고도 부름.
signal 연산은 전통적으로 V 연산이라고도 부름.
wait(S)는 세마포 S의 값이 양수일 때 값을 감소시키고 진행하는 연산.
만약 S의 값이 0 이하라면 프로세스는 기다려야 함.
signal(S)는 세마포 S의 값을 증가시키는 연산.
기다리는 프로세스가 있다면 그중 하나를 깨울 수 있음.
세마포 연산은 원자적으로 수행되어야 함.
한 프로세스가 세마포 값을 변경하는 동안 다른 프로세스가 동시에 같은 세마포 값을 변경할 수 없어야 함.
세마포는 크게 counting semaphore와 binary semaphore로 나눌 수 있음.
Counting semaphore는 값이 제한되지 않은 정수 범위를 가질 수 있음.
Counting semaphore는 여러 개의 동일한 자원을 관리하는 데 사용될 수 있음.
예를 들어 사용 가능한 자원이 5개라면 세마포 값을 5로 초기화할 수 있음.
프로세스가 자원을 사용할 때 wait를 실행하여 값을 1 감소시킴.
프로세스가 자원을 반환할 때 signal을 실행하여 값을 1 증가시킴.
세마포 값이 0이면 사용 가능한 자원이 없으므로 프로세스는 기다림.
Binary semaphore는 값이 0 또는 1만 가질 수 있는 세마포.
Binary semaphore는 Mutex 락과 유사하게 상호 배제에 사용될 수 있음.
Binary semaphore는 일부 시스템에서 Mutex lock 대신 제공되기도 함.
Counting semaphore는 여러 자원 인스턴스를 관리할 때 유용함.
Binary semaphore는 하나의 임계구역에 대한 상호 배제를 제공할 때 유용함.
세마포 사용
세마포는 공유 자원에 대한 접근 제어에 사용할 수 있음.
예를 들어 n개의 동일한 자원이 있는 시스템에서 세마포 S를 n으로 초기화할 수 있음.
프로세스가 자원을 사용하려면 wait(S)를 실행함.
자원 사용을 마치면 signal(S)를 실행함.
S 값은 현재 사용 가능한 자원의 개수를 의미함.
S 값이 0이 되면 모든 자원이 사용 중이라는 의미.
이때 추가로 자원을 요청하는 프로세스는 기다려야 함.
세마포는 실행 순서를 강제하는 데도 사용할 수 있음.
예를 들어 프로세스 P1의 명령문 S1이 프로세스 P2의 명령문 S2보다 먼저 실행되어야 한다고 가정함.
이 경우 세마포 synch를 0으로 초기화할 수 있음.
P1은 S1을 실행한 뒤 signal(synch)를 실행함.
P2는 S2를 실행하기 전에 wait(synch)를 실행함.
P2가 먼저 실행되더라도 wait(synch)에서 기다리게 됨.
P1이 S1을 끝내고 signal(synch)를 실행한 뒤에야 P2가 S2를 실행할 수 있음.
이 방식은 두 프로세스 사이의 실행 순서 관계를 보장함.
세마포는 상호 배제에도 사용할 수 있음.
Binary semaphore를 1로 초기화한 뒤 임계구역 앞에서 wait를 실행하고 임계구역 뒤에서 signal을 실행하면 됨.
이 경우 한 번에 하나의 프로세스만 임계구역에 들어갈 수 있음.
세마포는 생산자-소비자 문제, 독자-필자 문제, 식사하는 철학자 문제 같은 고전적 동기화 문제 해결에 사용될 수 있음.
그러나 세마포는 사용자가 wait와 signal의 위치를 정확히 지정해야 하는 도구.
따라서 잘못 사용하면 교착 상태나 기아 상태가 발생할 수 있음.
세마포 구현
단순한 세마포 구현에서는 wait 연산이 세마포 값이 양수가 될 때까지 바쁜 대기를 할 수 있음.
이 방식은 spinlock과 같은 문제를 가짐.
기다리는 동안 CPU 시간을 낭비함.
세마포 값이 사용 가능해질 때까지 계속 반복문을 수행하기 때문.
이를 해결하기 위해 세마포는 대기 큐를 사용하는 방식으로 구현될 수 있음.
세마포는 정수 값과 프로세스 대기 리스트를 함께 가질 수 있음.
세마포 구조는 value와 list로 구성될 수 있음.
value는 세마포의 현재 정수 값.
list는 이 세마포를 기다리는 프로세스들의 목록.
프로세스가 wait(S)를 실행했을 때 S 값이 사용 가능하지 않으면 자신을 S의 대기 리스트에 넣음.
그 뒤 block 연산을 통해 자신을 대기 상태로 전환함.
block 연산은 프로세스를 CPU에서 제거하고 대기 큐에 넣는 역할.
다른 프로세스가 signal(S)를 실행하면 S의 대기 리스트에 있는 프로세스 중 하나를 꺼냄.
그 프로세스는 wakeup 연산을 통해 준비 큐로 이동됨.
wakeup 연산은 대기 중인 프로세스를 다시 실행 가능 상태로 만드는 역할.
이 방식에서는 프로세스가 기다리는 동안 CPU를 사용하지 않음.
따라서 긴 대기 시간에는 바쁜 대기보다 효율적임.
세마포의 대기 리스트는 연결 리스트로 구현될 수 있음.
각 세마포는 자신의 값을 저장하는 정수와 대기 중인 프로세스 목록을 가짐.
wait와 signal 연산은 세마포 값과 대기 리스트를 변경함.
따라서 wait와 signal 자체도 원자적으로 실행되어야 함.
단일 처리기 시스템에서는 wait와 signal을 실행하는 동안 인터럽트를 잠시 불능화하여 원자성을 보장할 수 있음.
다중 처리기 시스템에서는 인터럽트 불능화만으로 충분하지 않을 수 있음.
여러 처리기가 동시에 같은 세마포에 접근할 수 있기 때문.
다중 처리기에서는 compare_and_swap 같은 하드웨어 명령어나 spinlock을 사용하여
wait와 signal의 임계구역을 보호할 수 있음.
세마포 구현에서 wait와 signal 자체의 임계구역은 매우 짧아야 함.
짧은 임계구역에 대해서는 spinlock을 사용하는 것이 가능함.
이렇게 하면 세마포 사용자는 긴 시간 바쁜 대기를 하지 않으면서도,
세마포 내부 구현은 짧은 원자 구간을 보호할 수 있음.
세마포는 바쁜 대기 없이 구현될 수 있지만, 완전히 대기 문제가 사라지는 것은 아님.
세마포를 잘못 사용하면 여러 문제가 생길 수 있음.
프로세스가 wait를 실행한 뒤 signal을 실행하지 않으면 다른 프로세스들이 무한히 기다릴 수 있음.
signal을 wait보다 먼저 잘못 실행하면 상호 배제가 깨질 수 있음.
wait와 signal의 순서가 뒤바뀌면 동기화 의미가 완전히 달라질 수 있음.
두 프로세스가 서로 상대방이 signal할 세마포를 기다리면 교착 상태가 발생할 수 있음.
교착 상태는 둘 이상의 프로세스가 서로의 진행을 기다리며 영원히 멈추는 상태.
기아 상태는 어떤 프로세스가 세마포 대기 큐에서 계속 선택되지 못해 무한히 기다리는 상태.
대기 큐가 LIFO처럼 동작하면 오래 기다린 프로세스가 계속 밀릴 수 있음.
따라서 세마포 구현에서는 대기 큐의 정책도 중요함.
FIFO 큐를 사용하면 한정 대기를 보장하는 데 도움이 될 수 있음.
세마포는 강력하지만 낮은 수준의 도구.
따라서 프로그래머가 wait와 signal을 정확하게 배치해야 함.
이 부담을 줄이기 위해 더 높은 수준의 동기화 구조인 모니터가 사용될 수 있음.
모니터
세마포는 강력한 동기화 도구이지만 올바르게 사용하기 어려움.
wait와 signal 연산의 순서나 위치가 조금만 잘못되어도 경쟁 조건, 교착 상태, 기아 상태가 발생할 수 있음.
예를 들어 signal 대신 wait를 잘못 사용하거나, wait와 signal의 순서를 바꾸면 프로세스들이 영원히 기다릴 수 있음.
또한 wait를 빠뜨리면 상호 배제가 깨질 수 있음.
signal을 빠뜨리면 다른 프로세스가 깨어나지 못할 수 있음.
이러한 문제를 줄이기 위해 더 높은 수준의 동기화 구조가 필요함.
모니터는 고수준 동기화 구조.
모니터는 추상 자료형의 한 형태.
모니터는 공유 자료와 그 자료를 조작하는 프로시저들을 하나로 묶은 구조.
모니터 내부의 변수들은 모니터 내부에 정의된 프로시저를 통해서만 접근 가능.
외부 프로세스는 모니터 내부 자료를 직접 접근할 수 없음.
프로세스는 모니터가 제공하는 프로시저를 호출하여 공유 자료를 조작함.
모니터의 가장 중요한 특징은 한 순간에 오직 하나의 프로세스만 모니터 안에서 활성화될 수 있다는 점.
여러 프로세스가 동시에 모니터 프로시저를 호출하더라도 실제로 모니터 내부에서 실행되는 프로세스는 하나뿐임.
이 특성 때문에 모니터는 기본적으로 상호 배제를 제공함.
프로그래머는 세마포처럼 임계구역 앞뒤에 wait와 signal을 직접 배치하여 상호 배제를 구현할 필요가 줄어듦.
모니터는 공유 데이터에 대한 접근을 구조적으로 제한함.
따라서 세마포보다 동기화 오류 가능성을 줄이는 데 도움이 됨.
모니터의 일반적인 구조는 공유 변수 선언, 여러 프로시저 또는 함수, 초기화 코드로 구성됨.
공유 변수는 모니터 내부에서만 사용됨.
프로시저는 외부 프로세스가 모니터에 접근할 수 있는 유일한 통로.
초기화 코드는 모니터 내부 변수의 초기값을 설정하는 부분.
모니터는 자동으로 상호 배제를 제공함.
하지만 이것만으로 모든 동기화 문제가 해결되는 것은 아님.
프로세스가 특정 조건이 만족될 때까지 기다려야 하는 경우가 있기 때문.
예를 들어 버퍼가 가득 찬 상태에서 생산자는 버퍼에 새 항목을 넣을 수 없음.
또한 버퍼가 비어 있는 상태에서 소비자는 항목을 꺼낼 수 없음.
이처럼 모니터 내부에서도 특정 조건을 기다리는 기능이 필요함.
이를 위해 모니터는 조건 변수를 제공함.
조건 변수는 condition 자료형으로 선언됨.
조건 변수는 일반 변수처럼 값을 저장하는 것이 아님.
조건 변수는 특정 조건을 기다리는 프로세스들을 대기시키기 위한 동기화 객체.
조건 변수에는 wait와 signal 연산이 사용됨.
x.wait는 조건 x가 만족될 때까지 호출한 프로세스를 대기시키는 연산.
x.wait를 호출한 프로세스는 모니터 내부 실행을 멈추고 조건 변수 x의 대기 큐에서 기다림.
이때 모니터 안에는 다른 프로세스가 들어올 수 있음.
x.signal은 조건 변수 x에서 기다리고 있는 프로세스 중 하나를 깨우는 연산.
x에서 기다리는 프로세스가 없다면 x.signal은 아무 효과가 없음.
조건 변수의 signal은 세마포의 signal과 다름.
세마포의 signal은 세마포 값을 증가시킬 수 있음.
그러나 조건 변수의 signal은 값이 누적되지 않음.
따라서 기다리는 프로세스가 없는 상태에서 x.signal이 실행되면
나중에 들어오는 프로세스를 위해 신호가 저장되지 않음.
조건 변수 wait도 세마포 wait와 다름.
세마포 wait는 세마포 값을 감소시키거나 값이 없으면 기다리는 연산.
조건 변수 wait는 특정 조건이 만족될 때까지 모니터 안에서 대기 상태로 빠지는 연산.
모니터는 상호 배제를 자동으로 제공하고, 조건 변수는 조건 동기화를 제공함.
따라서 모니터는 상호 배제와 조건 동기화를 함께 표현할 수 있는 구조.
모니터 사용
모니터를 사용하는 대표적인 예는 식사하는 철학자 문제.
식사하는 철학자 문제에서는 다섯 명의 철학자가 원형 테이블에 앉아 있음.
각 철학자 사이에는 젓가락이 하나씩 있음.
철학자는 생각하거나 식사하는 상태를 가짐.
식사하려면 자신의 왼쪽과 오른쪽 젓가락을 모두 집어야 함.
문제는 서로 이웃한 철학자들이 동시에 식사할 수 없다는 점.
모니터를 사용하면 철학자들의 상태를 배열로 관리할 수 있음.
각 철학자의 상태는 THINKING, HUNGRY, EATING 중 하나로 표현 가능.
THINKING은 철학자가 생각 중인 상태.
HUNGRY는 철학자가 식사하고 싶어 하는 상태.
EATING은 철학자가 실제로 식사 중인 상태.
각 철학자마다 condition 변수 self[i]를 둘 수 있음.
self[i]는 철학자 i가 식사할 수 있을 때까지 기다리는 조건 변수.
철학자가 젓가락을 집으려면 pickup(i)를 호출함.
pickup(i)는 철학자 i의 상태를 HUNGRY로 바꿈.
그 뒤 test(i)를 호출하여 양쪽 이웃이 식사 중인지 확인함.
만약 양쪽 이웃이 모두 식사 중이 아니고 철학자 i가 HUNGRY 상태라면 철학자 i의 상태를 EATING으로 바꿈.
이 경우 철학자 i는 식사를 시작할 수 있음.
그러나 양쪽 이웃 중 하나라도 EATING 상태라면 철학자 i는 self[i].wait를 호출하여 기다림.
철학자가 식사를 마치면 putdown(i)를 호출함.
putdown(i)는 철학자 i의 상태를 THINKING으로 바꿈.
그 뒤 왼쪽 이웃과 오른쪽 이웃에 대해 test를 호출함.
이웃 철학자들이 HUNGRY 상태이고, 그들의 양쪽 이웃이 식사 중이 아니라면 그들을 깨워 식사할 수 있게 함.
이 모니터 해결안은 서로 이웃한 두 철학자가 동시에 식사하지 못하게 보장함.
인접한 철학자 사이의 상호 배제를 제공함.
또한 철학자가 젓가락을 사용할 수 없을 때는 조건 변수에서 기다리게 함.
젓가락을 사용할 수 있게 되면 signal을 통해 기다리던 철학자를 깨울 수 있음.
다만 이 해결안도 모든 경우에 기아 상태가 절대 발생하지 않는다고 보장하지는 않을 수 있음.
어떤 철학자가 계속해서 이웃 철학자들에게 밀리면 오랫동안 식사하지 못할 수 있음.
따라서 모니터는 상호 배제를 구조적으로 제공하지만, 공정성이나 기아 방지까지 항상 자동으로 보장하는 것은 아님.
세마포를 사용한 모니터 구현
모니터는 고수준 개념이지만, 실제 구현에서는 세마포 같은 낮은 수준의 동기화 도구를 사용할 수 있음.
모니터의 핵심은 한 순간에 하나의 프로세스만 모니터 내부에서 실행되도록 하는 것.
이를 구현하기 위해 mutex 세마포를 사용할 수 있음.
mutex는 1로 초기화됨.
프로세스가 모니터 프로시저에 들어갈 때 wait(mutex)를 실행함.
프로세스가 모니터 프로시저를 빠져나올 때 signal(mutex)를 실행함.
이렇게 하면 한 번에 하나의 프로세스만 모니터 안에서 실행될 수 있음.
그러나 조건 변수의 wait와 signal을 구현하려면 추가적인 세마포와 카운터가 필요함.
조건 변수 x를 구현하기 위해 x_sem과 x_count를 둘 수 있음.
x_sem은 조건 변수 x에서 기다리는 프로세스를 대기시키기 위한 세마포.
x_count는 조건 변수 x에서 기다리는 프로세스의 수.
x.wait가 호출되면 x_count를 증가시킴.
그 뒤 현재 프로세스는 모니터를 비워 주고 x_sem에서 기다림.
모니터를 비워 주어야 다른 프로세스가 모니터에 들어와 조건을 바꾸고 signal을 호출할 수 있음.
x.signal이 호출되면 x_count가 0보다 큰지 확인함.
x_count가 0보다 크면 조건 변수 x에서 기다리는 프로세스가 있다는 의미.
이 경우 x_sem에 signal을 보내 대기 중인 프로세스 하나를 깨움.
하지만 모니터 안에는 한 순간에 하나의 프로세스만 있어야 함.
따라서 signal을 호출한 프로세스와 깨어난 프로세스가 동시에 모니터 안에서 실행되면 안 됨.
이를 해결하기 위해 next 세마포와 next_count 변수를 사용할 수 있음.
next는 signal을 호출한 프로세스가 잠시 기다리기 위한 세마포.
next_count는 next에서 기다리는 프로세스 수.
조건 변수 signal을 호출한 프로세스는 기다리던 프로세스를 깨운 뒤 자신이 next에서 기다릴 수 있음.
깨어난 프로세스가 모니터를 빠져나가거나 다시 기다리면 next에서 기다리던 프로세스가 다시 실행될 수 있음.
이 방식은 signal-and-wait 방식에 가까운 모니터 구현.
signal-and-wait 방식에서는 signal을 호출한 프로세스가 즉시 모니터를 양보하고, 깨어난 프로세스가 바로 실행됨.
이 구현은 세마포를 사용하여 모니터의 상호 배제와 조건 변수 동작을 실현하는 방식.
하지만 구현이 복잡함.
따라서 일반 프로그래머가 직접 구현하기보다는
언어, 런타임, 운영체제 수준에서 제공하는 모니터 기능을 사용하는 것이 일반적.
모니터 안에서 프로세스 재개
조건 변수 x에서 여러 프로세스가 기다리고 있을 수 있음.
이때 어떤 프로세스가 x.signal을 호출하면 기다리던 프로세스 중 하나만 재개됨.
문제는 여러 프로세스 중 어느 프로세스를 먼저 재개할 것인지임.
가장 단순한 방법은 FCFS 순서로 기다리던 프로세스를 깨우는 방식.
그러나 모든 상황에서 FCFS가 적절한 것은 아님.
어떤 경우에는 우선순위가 높은 프로세스를 먼저 깨우는 것이 필요할 수 있음.
이를 위해 conditional-wait 구조를 사용할 수 있음.
conditional-wait는 x.wait(c) 형태로 표현됨.
여기서 c는 우선순위 값을 나타내는 정수.
프로세스가 x.wait(c)를 호출하면 조건 변수 x에서 기다리면서 자신의 우선순위 c를 함께 전달함.
나중에 x.signal이 호출되면 조건 변수 x에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스가 재개됨.
책에서는 숫자 c가 작을수록 더 높은 우선순위를 의미하는 형태로 설명될 수 있음.
이 구조를 사용하면 조건 변수에서 기다리는 프로세스들 사이의 재개 순서를 제어할 수 있음.
대표적인 예는 자원 할당 모니터.
어떤 시스템에 하나의 자원이 있고, 여러 프로세스가 그 자원을 사용하려고 한다고 가정함.
프로세스는 acquire(time)을 호출하여 자원을 요청함.
여기서 time은 그 프로세스가 자원을 사용할 예상 시간.
자원이 사용 중이면 프로세스는 x.wait(time)을 호출하여 기다림.
자원이 사용 가능해지면 release가 호출되고, x.signal을 통해 기다리는 프로세스 중 하나가 깨어남.
이때 조건 변수는 time 값이 가장 작은 프로세스를 먼저 깨울 수 있음.
자원을 가장 짧게 사용할 것으로 예상되는 프로세스를 먼저 재개하는 방식.
이런 방식은 자원 사용 시간을 기준으로 대기 프로세스의 순서를 결정할 수 있음.
그러나 모니터를 사용한다고 해서 모든 오류가 자동으로 사라지는 것은 아님.
프로그래머가 모니터 프로시저를 올바른 순서로 호출해야 함.
예를 들어 자원을 얻지 않은 프로세스가 release를 호출하면 문제가 생김.
또한 자원을 얻은 프로세스가 release를 호출하지 않으면 다른 프로세스들이 계속 기다릴 수 있음.
프로세스가 acquire를 호출하지 않고 직접 자원에 접근할 수 있다면 모니터의 보호 의미가 깨짐.
따라서 모니터 내부 자료는 반드시 모니터 프로시저를 통해서만 접근되도록 제한되어야 함.
컴파일러나 런타임 시스템은 모니터의 상호 배제를 보장할 수 있음.
하지만 모니터 프로시저를 의미에 맞게 사용하는 책임은 여전히 프로그래머에게 있음.
모니터는 세마포보다 안전하고 구조적인 방법.
하지만 잘못된 사용으로 인한 논리 오류까지 완전히 제거하는 것은 아님.
라이브니스
라이브니스는 시스템이 실행되는 동안 프로세스들이 계속 진행할 수 있도록 보장하는 성질.
동기화 도구는 상호 배제를 제공해야 하지만, 상호 배제만으로 충분하지 않음.
프로세스가 임계구역에 들어가지 못하고 무한히 기다린다면 시스템은 올바르게 동작한다고 보기 어려움.
동기화는 안전성뿐 아니라 진행 가능성도 보장해야 함.
안전성은 잘못된 일이 일어나지 않도록 막는 성질.
예를 들어 두 프로세스가 동시에 임계구역에 들어가지 못하게 하는 것은 안전성.
라이브니스는 좋은 일이 결국 일어나도록 보장하는 성질.
예를 들어 임계구역에 들어가기를 요청한 프로세스가 언젠가는 들어갈 수 있어야 한다는 것은 라이브니스.
라이브니스 실패의 대표적인 예는 교착 상태와 우선순위 역전.
교착 상태는 여러 프로세스가 서로 상대방의 행동을 기다리며 아무도 진행하지 못하는 상태.
우선순위 역전은 높은 우선순위 프로세스가 낮은 우선순위 프로세스 때문에 간접적으로 오래 기다리게 되는 상태.
라이브니스 문제는 병행 시스템에서 매우 중요함.
프로세스들이 서로 동기화 도구를 올바르게 사용하지 않으면
시스템 전체가 멈추거나 특정 프로세스가 무한히 기다릴 수 있음.
교착 상태
교착 상태는 둘 이상의 프로세스가 서로의 진행을 기다리며 무한히 대기하는 상태.
각 프로세스가 기다리는 사건이 오직 대기 중인 다른 프로세스에 의해서만 발생할 수 있을 때 교착 상태가 발생함.
세마포를 잘못 사용하면 쉽게 교착 상태가 발생할 수 있음.
예를 들어 두 개의 세마포 S와 Q가 있다고 가정함.
S와 Q는 둘 다 1로 초기화됨.
프로세스 P0는 먼저 wait(S)를 실행하고, 그 다음 wait(Q)를 실행함.
프로세스 P1은 먼저 wait(Q)를 실행하고, 그 다음 wait(S)를 실행함.
만약 P0가 wait(S)를 실행하여 S를 획득함.
그 직후 P1이 wait(Q)를 실행하여 Q를 획득함.
이제 P0는 wait(Q)를 실행하지만 Q는 P1이 가지고 있으므로 기다림.
P1은 wait(S)를 실행하지만 S는 P0가 가지고 있으므로 기다림.
결국 P0는 P1이 Q를 놓기를 기다림.
P1은 P0가 S를 놓기를 기다림.
하지만 두 프로세스 모두 다음 단계로 진행하지 못하므로 signal을 실행할 수 없음.
따라서 두 프로세스는 영원히 기다리게 됨.
이것이 교착 상태.
교착 상태는 시스템 자원이 여러 개이고, 프로세스들이 자원을 서로 다른 순서로 요청할 때 자주 발생할 수 있음.
세마포뿐 아니라 Mutex 락, 모니터, 파일 락, 데이터베이스 락에서도 교착 상태가 발생할 수 있음.
교착 상태를 피하려면 자원을 요청하는 순서를 일관되게 정하는 방법이 있음.
예를 들어 모든 프로세스가 항상 S를 먼저 요청하고 Q를 나중에 요청한다면 위와 같은 순환 대기가 발생하지 않음.
또 다른 문제는 무한 대기 또는 기아 상태.
기아 상태는 프로세스가 계속 기다리지만 결코 선택되지 못하는 상태.
세마포의 대기 큐에서 어떤 프로세스가 계속 뒤로 밀리면 기아 상태가 발생할 수 있음.
예를 들어 세마포 대기 리스트가 LIFO 순서로 관리된다면 나중에 들어온 프로세스가 먼저 깨어날 수 있음.
이 경우 오래전에 기다리기 시작한 프로세스가 계속 선택되지 못할 수 있음.
기아 상태는 교착 상태와 다름.
교착 상태는 관련된 프로세스들이 모두 서로 기다리며 멈추는 상태.
기아 상태는 시스템 전체는 계속 진행되지만 특정 프로세스가 계속 기회를 얻지 못하는 상태.
둘 다 라이브니스 문제에 해당함.
왜냐하면 프로세스가 결국 진행해야 한다는 보장이 깨지기 때문.
우선순위 역전
우선순위 역전은 낮은 우선순위 프로세스가 가진 자원 때문에 높은 우선순위 프로세스가 기다리게 되는 문제.
우선순위 스케줄링 시스템에서 특히 중요한 라이브니스 문제.
우선순위 역전은 실시간 시스템에서 심각한 문제가 될 수 있음.
높은 우선순위 프로세스는 정해진 시간 안에 실행되어야 할 수 있기 때문.
예를 들어 세 프로세스 L, M, H가 있다고 가정함.
L은 낮은 우선순위 프로세스.
M은 중간 우선순위 프로세스.
H는 높은 우선순위 프로세스.
L이 어떤 자원 R을 획득한 상태에서 실행 중이라고 가정함.
그때 H가 실행 준비 상태가 되고, 자원 R을 요청함.
그러나 R은 L이 가지고 있으므로 H는 기다려야 함.
이 상황 자체는 자연스러운 대기.
문제는 그 다음 M이 실행 준비 상태가 되는 경우.
M은 L보다 우선순위가 높기 때문에 스케줄러는 M을 실행할 수 있음.
그러면 L은 CPU를 받지 못해 자원 R을 빨리 반환할 수 없음.
H는 L이 R을 반환할 때까지 기다려야 함.
결과적으로 가장 높은 우선순위 H가 중간 우선순위 M 때문에 간접적으로 지연됨.
이 현상을 우선순위 역전이라고 함.
겉으로 보면 H는 L이 가진 자원을 기다리는 것처럼 보임.
하지만 실제 지연을 더 길게 만드는 것은 M이 L을 선점하는 상황.
낮은 우선순위 L이 자원을 들고 있고, 중간 우선순위 M이 L의 실행을 방해하여 높은 우선순위 H가 더 오래 기다리게 됨.
우선순위 역전은 단순한 우선순위 스케줄링만으로 해결하기 어려움.
대표적인 해결 방법은 우선순위 상속 프로토콜.
우선순위 상속 프로토콜은 낮은 우선순위 프로세스가 높은 우선순위 프로세스가 필요로 하는 자원을 가지고 있을 때,
낮은 우선순위 프로세스가 일시적으로 높은 우선순위를 상속받는 방식.
예를 들어 H가 L이 가진 자원 R을 기다리면, L은 H의 우선순위를 일시적으로 상속받음.
그러면 중간 우선순위 M이 L을 선점하지 못함.
L은 높은 우선순위로 실행되어 자원 R을 빠르게 반환함.
자원 R을 반환한 뒤 L의 우선순위는 원래 낮은 우선순위로 돌아감.
그 뒤 H가 R을 획득하고 실행을 계속할 수 있음.
우선순위 상속은 높은 우선순위 프로세스의 지연 시간을 줄이는 데 도움이 됨.
특히 실시간 시스템에서 우선순위 역전으로 인한 마감시간 위반을 줄이기 위해 사용됨.
우선순위 역전은 실제 시스템에서도 중요한 문제로 알려져 있음.
따라서 실시간 운영체제와 동기화 라이브러리는 우선순위 상속 또는 이와 유사한 기법을 제공할 수 있음.