고전적 동기화 문제들
고전적 동기화 문제들은 병행 프로그래밍에서 자주 발생하는 문제를 추상화한 예제.
여러 프로세스나 스레드가 공유 자원에 접근할 때 어떤 방식으로 동기화해야 하는지를 보여주는 역할.
대표적인 문제는 유한 버퍼 문제, 독자-필자 문제, 식사하는 철학자 문제.
유한 버퍼 문제는 생산자와 소비자가 제한된 크기의 버퍼를 공유하는 상황.
독자-필자 문제는 여러 독자와 필자가 하나의 공유 데이터베이스에 접근하는 상황.
식사하는 철학자 문제는 여러 프로세스가 여러 자원을 동시에 필요로 하는 상황.
이 세 문제는 동기화 도구의 사용 방법을 설명하는 데 자주 사용됨.
또한 실제 시스템에서 발생하는 생산자-소비자 관계, 공유 데이터베이스 접근, 여러 자원 경쟁 문제와 연결됨.
유한 버퍼 문제
유한 버퍼 문제는 생산자-소비자 문제의 대표적인 형태.
생산자는 항목을 만들어 버퍼에 넣는 프로세스.
소비자는 버퍼에서 항목을 꺼내 사용하는 프로세스.
버퍼는 크기가 제한되어 있음.
따라서 버퍼가 가득 차면 생산자는 더 이상 항목을 넣을 수 없음.
반대로 버퍼가 비어 있으면 소비자는 항목을 꺼낼 수 없음.
이 문제의 핵심은 생산자와 소비자가 같은 버퍼를 공유하면서도 올바른 순서로 접근하도록 만드는 것.
유한 버퍼 문제에서는 세 개의 세마포를 사용할 수 있음.
첫 번째 세마포는 mutex.
mutex는 버퍼 자체에 대한 상호 배제를 제공함.
생산자와 소비자가 동시에 버퍼 자료구조를 변경하지 못하게 하는 역할.
mutex의 초기값은 1.
두 번째 세마포는 empty.
empty는 비어 있는 버퍼 공간의 개수를 나타냄.
버퍼 크기가 n이라면 empty의 초기값은 n.
세 번째 세마포는 full.
full은 채워진 버퍼 공간의 개수를 나타냄.
처음에는 버퍼가 비어 있으므로 full의 초기값은 0.
따라서 mutex는 임계구역 보호, empty는 빈 공간 개수 관리, full은 채워진 공간 개수 관리를 담당함.
생산자는 항목을 만든 뒤 버퍼에 넣기 전에 먼저 empty에 대해 wait를 실행함.
empty가 0이면 비어 있는 공간이 없다는 의미이므로 생산자는 기다려야 함.
empty가 양수이면 생산자는 빈 공간 하나를 사용할 수 있음.
그 다음 생산자는 mutex에 대해 wait를 실행함.
이 과정은 버퍼에 대한 배타적 접근 권한을 얻는 과정.
mutex를 얻은 생산자는 버퍼에 항목을 넣음.
항목을 넣은 뒤에는 mutex에 대해 signal을 실행함.
이것은 버퍼 사용을 마쳤음을 알리는 것.
마지막으로 full에 대해 signal을 실행함.
이것은 채워진 버퍼 공간이 하나 늘어났음을 알리는 것.
생산자의 기본 흐름은 항목 생산, empty 대기, mutex 획득, 버퍼에 항목 추가, mutex 반환, full 증가 순서.
소비자는 항목을 꺼내기 전에 먼저 full에 대해 wait를 실행함.
full이 0이면 버퍼에 꺼낼 항목이 없다는 의미이므로 소비자는 기다려야 함.
full이 양수이면 소비자는 채워진 공간 하나를 사용할 수 있음.
그 다음 소비자는 mutex에 대해 wait를 실행함.
이 과정은 버퍼에 대한 배타적 접근 권한을 얻는 과정.
mutex를 얻은 소비자는 버퍼에서 항목을 꺼냄.
항목을 꺼낸 뒤에는 mutex에 대해 signal을 실행함.
이것은 버퍼 사용을 마쳤음을 알리는 것.
마지막으로 empty에 대해 signal을 실행함.
이것은 비어 있는 버퍼 공간이 하나 늘어났음을 알리는 것.
소비자의 기본 흐름은 full 대기, mutex 획득, 버퍼에서 항목 제거, mutex 반환, empty 증가, 항목 소비 순서.
이 구조에서 empty와 full은 생산자와 소비자 사이의 실행 순서를 제어함.
empty는 버퍼가 가득 찼을 때 생산자가 기다리게 함.
full은 버퍼가 비었을 때 소비자가 기다리게 함.
mutex는 생산자와 소비자가 버퍼를 동시에 조작하지 못하게 함.
따라서 유한 버퍼 문제에서는 자원 개수 제어와 상호 배제가 함께 필요함.
empty와 full은 자원 개수 제어 역할.
mutex는 임계구역 보호 역할.
이 세마포들의 wait 순서는 매우 중요함.
생산자가 mutex를 먼저 얻고 empty를 기다리면 버퍼가 가득 찬 상황에서 문제가 생길 수 있음.
생산자가 mutex를 가진 상태로 empty를 기다리면 소비자는 mutex를 얻지 못함.
소비자가 mutex를 얻지 못하면 버퍼에서 항목을 꺼낼 수 없음.
그 결과 생산자는 빈 공간을 기다리고, 소비자는 mutex를 기다리는 상황이 생길 수 있음.
따라서 생산자는 먼저 empty를 확인하고, 그 다음 mutex를 얻어야 함.
소비자도 먼저 full을 확인하고, 그 다음 mutex를 얻어야 함.
유한 버퍼 문제에서는 어떤 세마포를 쓰는지도 중요하지만 wait와 signal의 위치와 순서도 중요함.
독자-필자 문제
독자-필자 문제는 여러 프로세스가 하나의 공유 데이터베이스를 함께 사용하는 상황을 다룸.
어떤 프로세스는 공유 데이터를 읽기만 함.
이 프로세스를 독자라고 함.
어떤 프로세스는 공유 데이터를 수정함.
이 프로세스를 필자라고 함.
여러 독자는 동시에 공유 데이터를 읽을 수 있음.
읽기 작업은 데이터 값을 변경하지 않기 때문.
그러나 필자가 공유 데이터를 수정하는 동안에는 다른 필자나 독자가 동시에 접근하면 안 됨.
필자와 다른 필자가 동시에 쓰면 데이터가 깨질 수 있음.
필자가 쓰는 동안 독자가 읽으면 일관성 없는 데이터를 읽을 수 있음.
따라서 독자-필자 문제의 핵심은 여러 독자는 동시에 허용하되, 필자는 배타적으로 접근하도록 만드는 것.
독자-필자 문제에는 여러 변형이 있음.
첫 번째 독자-필자 문제는 필자가 기다리고 있더라도 이미 읽고 있는 독자들이 계속 읽을 수 있도록 하는 방식.
이 방식에서는 독자에게 우선권이 주어질 수 있음.
그 결과 필자가 오래 기다리는 기아 상태가 발생할 수 있음.
두 번째 독자-필자 문제는 필자가 준비되면 가능한 한 빨리 쓰기를 수행하도록 보장하는 방식.
이 방식에서는 필자에게 우선권이 주어질 수 있음.
그 결과 독자가 오래 기다리는 기아 상태가 발생할 수 있음.
기본적인 독자-필자 해결안에서는 두 개의 세마포와 하나의 정수 변수를 사용할 수 있음.
첫 번째 세마포는 rw_mutex.
rw_mutex는 필자가 공유 데이터베이스에 접근할 때 사용하는 세마포.
또한 첫 번째 독자가 데이터베이스에 들어갈 때도 사용됨.
rw_mutex의 초기값은 1.
두 번째 세마포는 mutex.
mutex는 read_count 변수를 보호하기 위해 사용됨.
mutex의 초기값은 1.
read_count는 현재 공유 데이터를 읽고 있는 독자의 수.
read_count의 초기값은 0.
필자는 쓰기 작업을 수행하기 전에 rw_mutex에 대해 wait를 실행함.
rw_mutex를 얻으면 필자는 데이터베이스에 배타적으로 접근할 수 있음.
쓰기 작업을 끝낸 뒤 rw_mutex에 대해 signal을 실행함.
필자의 흐름은 rw_mutex 획득, 쓰기 작업 수행, rw_mutex 반환 순서.
독자는 읽기 작업을 시작하기 전에 read_count를 증가시킴.
하지만 read_count는 여러 독자가 함께 접근하는 공유 변수이므로 mutex로 보호해야 함.
독자는 먼저 mutex에 대해 wait를 실행함.
그 뒤 read_count를 1 증가시킴.
만약 read_count가 1이 되었다면 이 독자가 첫 번째 독자라는 의미.
첫 번째 독자는 rw_mutex에 대해 wait를 실행함.
이것은 필자가 데이터베이스에 들어오지 못하게 막는 역할.
그 뒤 mutex에 대해 signal을 실행하여 read_count 보호를 끝냄.
독자는 읽기 작업을 수행함.
읽기 작업을 끝낸 뒤 다시 mutex에 대해 wait를 실행함.
그 다음 read_count를 1 감소시킴.
만약 read_count가 0이 되었다면 이 독자가 마지막 독자라는 의미.
마지막 독자는 rw_mutex에 대해 signal을 실행함.
이것은 필자가 데이터베이스에 접근할 수 있도록 허용하는 역할.
마지막으로 mutex에 대해 signal을 실행함.
독자의 흐름은
mutex 획득, read_count 증가,
첫 번째 독자이면 rw_mutex 획득, mutex 반환, 읽기 작업 수행, mutex 재획득, read_count 감소,
마지막 독자이면 rw_mutex 반환, mutex 반환 순서.
이 해결안에서는 첫 번째 독자가 rw_mutex를 잠금.
그 후 들어오는 다른 독자들은 rw_mutex를 다시 기다리지 않고 함께 읽을 수 있음.
마지막 독자가 나갈 때 rw_mutex를 해제함.
따라서 여러 독자가 동시에 읽는 것이 가능함.
그러나 필자가 쓰기 위해 기다리는 동안에도 새로운 독자들이 계속 들어올 수 있음.
이 경우 필자는 오래 기다릴 수 있음.
필자 기아 상태가 발생할 수 있음.
독자-필자 문제는 reader-writer lock으로도 해결할 수 있음.
Reader-writer lock은 읽기 모드와 쓰기 모드를 구분하는 락.
스레드가 공유 데이터를 읽기만 할 때는 읽기 모드로 락을 획득함.
여러 스레드가 동시에 읽기 모드 락을 가질 수 있음.
스레드가 공유 데이터를 수정할 때는 쓰기 모드로 락을 획득함.
쓰기 모드 락은 배타적임.
쓰기 모드 락이 잡혀 있으면 다른 독자나 필자는 들어올 수 없음.
Reader-writer lock은 읽기 작업이 많고 쓰기 작업이 적은 경우에 유용함.
또한 읽기 작업과 쓰기 작업을 명확히 구분할 수 있어야 함.
하지만 reader-writer lock은 일반 Mutex 락보다 관리 비용이 더 클 수 있음.
따라서 읽기 작업이 많지 않거나 임계구역이 매우 짧다면 일반 Mutex가 더 단순할 수 있음.
식사하는 철학자 문제
식사하는 철학자 문제는 여러 프로세스가 여러 자원을 공유하는 상황을 표현하는 고전적 동기화 문제.
다섯 명의 철학자가 원형 테이블에 앉아 있다고 가정함.
각 철학자 사이에는 젓가락이 하나씩 있음.
철학자는 생각하거나 식사하는 상태를 반복함.
철학자가 식사하려면 자신의 왼쪽 젓가락과 오른쪽 젓가락을 모두 가져야 함.
한 젓가락은 한 번에 한 철학자만 사용할 수 있음.
철학자는 두 젓가락을 모두 얻은 뒤에만 식사할 수 있음.
식사를 마치면 두 젓가락을 내려놓고 다시 생각함.
이 문제의 핵심은 철학자들이 서로 이웃한 자원을 공유하면서 교착 상태와 기아 상태 없이 식사할 수 있도록 만드는 것.
식사하는 철학자 문제는 여러 프로세스가 여러 자원을 필요로 하고,
각 자원을 배타적으로 사용해야 하는 실제 시스템의 자원 할당 문제와 비슷함.
따라서 교착 상태와 기아 상태를 설명하는 대표적인 동기화 예제.
세마포 해결안
세마포를 사용한 단순한 해결안에서는 각 젓가락을 하나의 세마포로 표현할 수 있음.
chopstick[i]는 i번째 젓가락을 나타내는 세마포.
각 chopstick[i]의 초기값은 1.
철학자 i는 식사하기 전에 wait(chopstick[i])를 실행하여 한쪽 젓가락을 집음.
그 다음 wait(chopstick[(i + 1) % 5])를 실행하여 다른 쪽 젓가락을 집음.
두 젓가락을 모두 얻으면 식사함.
식사를 마친 뒤 signal(chopstick[i])와 signal(chopstick[(i + 1) % 5])를 실행하여 젓가락을 내려놓음.
단순한 세마포 해결안에서 철학자 i의 흐름은
첫 번째 젓가락 획득, 두 번째 젓가락 획득, 식사, 첫 번째 젓가락 반환, 두 번째 젓가락 반환, 생각의 반복.
이 해결안은 인접한 두 철학자가 동시에 같은 젓가락을 사용할 수 없게 함.
따라서 상호 배제는 만족함.
그러나 교착 상태가 발생할 수 있음.
예를 들어 모든 철학자가 동시에 자신의 왼쪽 젓가락을 집었다고 가정함.
그 다음 모든 철학자는 오른쪽 젓가락을 기다림.
하지만 각 오른쪽 젓가락은 이미 이웃 철학자가 가지고 있음.
모든 철학자가 서로가 젓가락을 내려놓기를 기다리게 됨.
아무도 식사를 시작하지 못하고 아무도 젓가락을 내려놓지 않음.
이것이 교착 상태.
교착 상태를 피하기 위한 방법은 여러 가지가 있음.
첫 번째 방법은 동시에 최대 네 명의 철학자만 테이블에 앉도록 허용하는 것.
다섯 명 모두가 동시에 젓가락 하나씩 들지 못하게 하면 순환 대기 가능성을 줄일 수 있음.
두 번째 방법은 철학자가 양쪽 젓가락을 모두 얻을 수 있을 때만 젓가락을 집도록 하는 것.
한쪽 젓가락만 들고 기다리는 상황을 막는 방식.
세 번째 방법은 비대칭 해결안을 사용하는 것.
예를 들어 홀수 번호 철학자는 먼저 왼쪽 젓가락을 집고, 짝수 번호 철학자는 먼저 오른쪽 젓가락을 집는 방식.
모든 철학자가 같은 순서로 젓가락을 집지 않게 하여 순환 대기를 깨는 방식.
모니터 해결안
식사하는 철학자 문제에 대해 교착 상태가 없는 해결안을 제시하면서 모니터 개념을 설명할 수 있음.
이 해결안은 철학자가 양쪽 젓가락을 모두 얻을 수 있을 때만 젓가락을 집을 수 있다는 제한을 강제함.
철학자가 한쪽 젓가락만 들고 다른 쪽 젓가락을 기다리는 상황을 만들지 않는 방식.
이 해결안을 구현하려면 철학자가 처할 수 있는 상태를 구분해야 함.
철학자의 상태는 세 가지로 구분됨.
THINKING은 철학자가 생각 중인 상태.
HUNGRY는 철학자가 배고파서 식사하려고 하는 상태.
EATING은 철학자가 실제로 식사 중인 상태.
이를 위해 THINKING, HUNGRY, EATING 값을 가지는 state[5] 배열을 도입함.
state[i]는 철학자 i의 현재 상태를 나타냄.
철학자 i는 자신의 양쪽 두 이웃이 식사하지 않을 때만 state[i]를 EATING으로 설정할 수 있음.
왼쪽 이웃은 state[(i + 4) % 5]로 표현됨.
오른쪽 이웃은 state[(i + 1) % 5]로 표현됨.
따라서 철학자 i가 식사할 수 있으려면 왼쪽 이웃이 EATING이 아니어야 함.
또한 철학자 i 자신은 HUNGRY 상태여야 함.
그리고 오른쪽 이웃도 EATING이 아니어야 함.
각 철학자가 원하는 젓가락을 집을 수 없을 때 기다릴 수 있도록 조건 변수 self[5]도 선언함.
self[i]는 철학자 i가 배고프지만 자신이 원하는 젓가락을 집을 수 없을 때 기다리기 위한 조건 변수.
젓가락의 분배는 모니터 DiningPhilosophers에 의해 제어됨.
이 모니터는 철학자의 상태 배열 state와 조건 변수 self를 내부에 가지고 있음.
철학자는 젓가락을 집으려고 할 때 pickup(i)를 호출함.
철학자가 식사를 마치고 젓가락을 내려놓을 때는 putdown(i)를 호출함.
pickup(i)는 철학자 i가 젓가락을 집으려고 할 때 호출하는 프로시저.
철학자 i는 먼저 자신의 상태를 HUNGRY로 변경함.
그 다음 test(i)를 호출하여 자신이 식사할 수 있는지 검사함.
test(i)는 양쪽 이웃이 모두 식사 중이 아니고, 철학자 i가 HUNGRY 상태이면 state[i]를 EATING으로 변경함.
그 뒤 self[i].signal을 호출하여 철학자 i가 식사할 수 있음을 알림.
만약 test(i)를 호출했는데도 state[i]가 EATING으로 바뀌지 않았다면
철학자 i는 아직 양쪽 젓가락을 모두 얻을 수 없는 상태.
이 경우 self[i].wait를 호출하여 기다림.
putdown(i)는 철학자 i가 식사를 마치고 젓가락을 내려놓을 때 호출하는 프로시저.
철학자 i는 자신의 상태를 THINKING으로 변경함.
그 뒤 왼쪽 이웃과 오른쪽 이웃에 대해 test를 호출함.
이유는 철학자 i가 식사를 끝내면 양쪽 이웃 중 누군가가 이제 식사할 수 있게 될 수 있기 때문.
test((i + 4) % 5)는 왼쪽 이웃이 식사할 수 있는지 확인하는 과정.
test((i + 1) % 5)는 오른쪽 이웃이 식사할 수 있는지 확인하는 과정.
test(i)는 철학자 i가 식사할 수 있는지 검사하는 핵심 프로시저.
철학자 i가 HUNGRY 상태이고, 양쪽 이웃이 모두 EATING 상태가 아니면 철학자 i는 식사 가능 상태.
이 경우 state[i]를 EATING으로 바꾸고 self[i].signal을 호출함.
self[i].signal은 self[i]에서 기다리고 있던 철학자 i를 깨우는 역할.
초기화 코드에서는 모든 철학자의 상태를 THINKING으로 설정함.
처음에는 어떤 철학자도 식사 중이 아니기 때문.
철학자 i는 식사를 시작하기 전에 DiningPhilosophers.pickup(i)를 호출함.
식사를 끝낸 뒤에는 DiningPhilosophers.putdown(i)를 호출함.
이 모니터 해결안은 인접한 두 철학자가 동시에 식사하지 못하게 보장함.
철학자 i가 EATING 상태가 되려면 양쪽 이웃이 EATING 상태가 아니어야 하기 때문.
또한 철학자는 양쪽 젓가락을 모두 얻을 수 있을 때만 식사 상태가 됨.
따라서 모든 철학자가 한쪽 젓가락만 들고 서로 기다리는 교착 상태를 방지할 수 있음.
그러나 이 해결안도 철학자가 굶어 죽지 않는다는 것까지 완전히 보장하지는 않음.
교착 상태는 피할 수 있지만 기아 상태가 발생하지 않는다는 보장은 별도의 고려가 필요함.
어떤 철학자가 계속해서 이웃 철학자들에게 밀리면 오랫동안 식사하지 못할 수 있음.
따라서 모니터 해결안은 교착 상태 없는 구조를 제공하지만, 기아 방지까지 자동으로 해결하는 것은 아님.
커널 안에서의 동기화
운영체제 커널은 여러 공유 자료구조를 관리함.
프로세스 테이블, 파일 테이블, 메모리 관리 자료구조, 입출력 큐 등이 대표적인 예.
커널 코드는 여러 프로세스, 스레드, 인터럽트 처리 루틴에 의해 병행적으로 실행될 수 있음.
따라서 커널 내부에서도 동기화가 반드시 필요함.
커널 동기화는 일반 사용자 프로그램보다 더 조심스럽게 설계되어야 함.
커널 자료구조가 깨지면 특정 프로그램만 문제가 되는 것이 아니라 시스템 전체가 불안정해질 수 있기 때문.
또한 커널은 성능이 중요하므로 동기화 도구의 비용도 고려해야 함.
이 절에서는 Windows와 Linux가 커널 안에서 동기화를 어떻게 제공하는지 설명함.
Windows 동기화
Windows 운영체제는 다중 스레드 커널을 사용함.
커널 내부의 전역 자원과 공유 자료구조를 보호하기 위해 여러 동기화 기법이 사용됨.
단일 처리기 시스템에서는 전역 자원에 접근할 때 인터럽트를 잠시 마스크할 수 있음.
인터럽트를 마스크하면 현재 실행 중인 코드가 인터럽트에 의해 중단되지 않음.
따라서 짧은 커널 임계구역을 보호할 수 있음.
하지만 다중 처리기 시스템에서는 인터럽트 마스크만으로 충분하지 않음.
다른 처리기에서 동시에 같은 커널 자료구조에 접근할 수 있기 때문.
이 경우 Windows는 spinlock을 사용하여 전역 커널 자료구조를 보호함.
Spinlock은 짧은 시간 동안만 보유되는 커널 락에 적합함.
락을 기다리는 스레드는 락이 풀릴 때까지 반복적으로 검사함.
Windows는 디스패처 객체라는 동기화 객체도 제공함.
디스패처 객체는 커널에서 제공하는 여러 동기화 객체의 공통 형태.
디스패처 객체에는 mutex lock, semaphore, event, timer 등이 포함됨.
디스패처 객체는 signaled 상태 또는 nonsignaled 상태를 가질 수 있음.
객체가 signaled 상태이면 그 객체를 기다리는 스레드가 계속 실행될 수 있음.
객체가 nonsignaled 상태이면 그 객체를 기다리는 스레드는 봉쇄됨.
Mutex 객체는 소유되지 않은 상태일 때 signaled 상태.
어떤 스레드가 mutex를 획득하면 mutex는 nonsignaled 상태가 됨.
Mutex를 소유한 스레드가 mutex를 해제하면 다시 signaled 상태가 됨.
Semaphore 객체는 세마포 카운트가 0보다 클 때 signaled 상태.
카운트가 0이면 nonsignaled 상태.
스레드가 semaphore를 획득하면 카운트가 감소함.
스레드가 semaphore를 해제하면 카운트가 증가함.
Event 객체는 특정 사건이 발생했음을 알리는 데 사용됨.
Event가 signaled 상태가 되면 그 이벤트를 기다리던 스레드들이 깨어날 수 있음.
Timer 객체는 지정된 시간이 지나면 signaled 상태가 될 수 있음.
Windows 스레드는 디스패처 객체가 signaled 상태가 될 때까지 기다릴 수 있음.
객체가 nonsignaled 상태이면 스레드는 대기 상태로 들어감.
객체가 signaled 상태가 되면 커널은 기다리던 스레드 중 하나 또는 여러 개를 깨울 수 있음.
Windows는 사용자 모드에서도 동기화 도구를 제공함.
대표적인 것이 critical-section 객체.
Critical-section 객체는 같은 프로세스 안의 스레드들 사이에서 상호 배제를 제공함.
Critical-section 객체는 일반적으로 사용자 모드에서 빠르게 동작함.
경쟁이 심하지 않으면 커널 호출 없이 락을 얻고 해제할 수 있음.
하지만 락을 얻지 못하면 커널 mutex를 사용하여 스레드를 대기시킬 수 있음.
Windows의 critical-section 객체는 spin count를 사용할 수 있음.
Spin count는 락을 얻기 전에 몇 번 정도 반복해서 검사할지를 나타내는 값.
다중 처리기 시스템에서는 잠깐 spin한 뒤 락이 풀리면 문맥 교환 없이 빠르게 임계구역에 들어갈 수 있음.
하지만 오래 기다려야 하면 커널 객체를 통해 봉쇄될 수 있음.
이 방식은 사용자 모드의 빠른 락과 커널 모드의 대기 기능을 결합한 구조.
Linux 동기화
Linux 커널도 공유 자료구조를 보호하기 위해 다양한 동기화 기법을 제공함.
초기의 Linux 커널은 비선점형 커널에 가까운 구조.
프로세스가 커널 모드에서 실행 중일 때는 선점되지 않았음.
이 방식은 커널 자료구조 보호를 단순하게 만들 수 있음.
그러나 최신 Linux 커널은 선점형 커널을 지원함.
커널 모드에서도 선점이 가능하므로 커널 자료구조 보호를 위한 동기화가 필요함.
Linux는 원자적 정수, mutex 락, 세마포, spinlock, reader-writer lock, RCU 같은 동기화 도구를 제공함.
원자적 정수는 atomic_t 자료형으로 제공될 수 있음.
atomic_t는 정수 값에 대한 원자적 연산을 지원하는 자료형.
atomic_set은 원자적 정수 값을 설정하는 연산.
atomic_read는 원자적 정수 값을 읽는 연산.
atomic_inc는 원자적 정수 값을 1 증가시키는 연산.
atomic_dec는 원자적 정수 값을 1 감소시키는 연산.
atomic_add와 atomic_sub는 특정 값을 더하거나 빼는 연산.
원자적 정수는 단순한 카운터나 플래그를 보호할 때 유용함.
그러나 여러 자료구조를 함께 갱신해야 하는 복잡한 임계구역에는 충분하지 않음.
이 경우에는 mutex나 spinlock 같은 락이 필요함.
Linux의 mutex 락은 임계구역을 보호하기 위해 사용됨.
스레드는 mutex_lock을 호출하여 락을 획득함.
락을 얻을 수 없으면 스레드는 대기 상태로 들어갈 수 있음.
임계구역을 끝낸 뒤 mutex_unlock을 호출하여 락을 해제함.
Mutex는 락 보유 시간이 비교적 길거나 잠들 수 있는 코드에서 사용될 수 있음.
Linux의 spinlock은 짧은 임계구역을 보호하기 위해 사용됨.
spin_lock을 호출한 스레드는 락을 얻을 때까지 바쁜 대기를 수행함.
spin_unlock을 호출하면 락이 해제됨.
Spinlock은 잠들 수 없는 커널 코드나 인터럽트 관련 코드에서 유용함.
단일 처리기 시스템에서는 spinlock이 실제 회전 대기를 할 필요가 적음.
하지만 커널 선점을 막거나 인터럽트를 조절하여 임계구역을 보호할 수 있음.
다중 처리기 시스템에서는 다른 CPU가 락을 해제할 수 있으므로 spinlock이 의미를 가짐.
Linux는 reader-writer spinlock과 reader-writer semaphore도 제공할 수 있음.
Reader-writer lock은 여러 독자가 동시에 읽을 수 있게 하면서 필자는 배타적으로 접근하도록 함.
읽기 작업이 많고 쓰기 작업이 적은 커널 자료구조에서 유용함.
Linux는 RCU도 제공함.
RCU는 Read-Copy-Update의 약어.
RCU는 읽기 작업이 매우 많고 쓰기 작업이 상대적으로 적은 상황에 적합한 동기화 기법.
RCU의 기본 아이디어는 독자가 락을 거의 사용하지 않고 읽을 수 있게 하는 것.
필자는 기존 자료구조를 직접 수정하지 않고 먼저 복사본을 만듦.
그 복사본을 수정한 뒤 포인터를 새 복사본으로 바꿈.
기존 데이터를 읽고 있던 독자들은 계속 기존 버전을 읽을 수 있음.
새로 들어오는 독자들은 새 버전을 읽을 수 있음.
기존 독자들이 모두 읽기를 끝낸 뒤에야 이전 버전을 안전하게 해제할 수 있음.
이때 기존 독자들이 모두 빠져나가기까지의 기간을 grace period라고 함.
RCU는 독자에게 매우 낮은 오버헤드를 제공함.
읽기 작업이 락 때문에 봉쇄되지 않기 때문.
하지만 쓰기 작업은 복사와 지연 해제 과정을 관리해야 하므로 더 복잡함.
RCU는 커널 안의 연결 리스트나 네트워크 라우팅 테이블처럼 읽기 빈도가 높은 자료구조에 유용함.
POSIX 동기화
POSIX는 스레드 동기화를 위한 표준 API를 제공함.
POSIX 스레드, Pthreads는 UNIX 계열 시스템에서 널리 사용됨.
POSIX 동기화 도구에는 mutex 락, 세마포, 조건 변수가 있음.
이 도구들은 C 프로그램에서 스레드 간 동기화를 구현할 때 사용됨.
POSIX Mutex 락
POSIX Mutex 락은 pthread_mutex_t 자료형으로 선언됨.
Mutex는 임계구역에 대한 상호 배제를 제공함.
공유 자료에 접근하기 전에 mutex를 잠그고, 접근이 끝난 뒤 mutex를 해제하는 방식.
Mutex 변수는 pthread_mutex_init 함수를 사용하여 초기화할 수 있음.
기본 속성을 사용하려면 속성 인자로 NULL을 전달할 수 있음.
스레드는 pthread_mutex_lock 함수를 호출하여 mutex를 획득함.
mutex가 사용 가능하면 스레드는 락을 얻고 계속 실행함.
mutex가 이미 다른 스레드에 의해 잠겨 있으면 호출한 스레드는 락이 풀릴 때까지 기다림.
임계구역 실행이 끝나면 pthread_mutex_unlock 함수를 호출하여 mutex를 해제함.
더 이상 사용하지 않는 mutex는 pthread_mutex_destroy 함수로 제거할 수 있음.
POSIX Mutex는 같은 프로세스 안의 여러 스레드가 공유 자료에 접근할 때 자주 사용됨.
Mutex를 올바르게 사용하려면 모든 공유 자료 접근이 같은 mutex로 보호되어야 함.
어떤 스레드가 mutex 없이 공유 자료에 접근하면 상호 배제가 깨질 수 있음.
POSIX 세마포
POSIX는 세마포도 제공함.
POSIX 세마포에는 이름 있는 세마포와 이름 없는 세마포가 있음.
이름 없는 세마포는 일반적으로 같은 프로세스 안의 스레드들 사이에서 사용됨.
이름 있는 세마포는 서로 다른 프로세스 사이에서도 사용할 수 있음.
POSIX 세마포는 sem_t 자료형으로 선언될 수 있음.
이름 없는 세마포는 sem_init 함수로 초기화함.
sem_init 함수에는 세마포 포인터, 공유 범위, 초기값이 전달됨.
공유 범위 인자가 0이면 같은 프로세스 안의 스레드들 사이에서 공유됨.
초기값은 세마포의 시작 카운트.
스레드는 sem_wait 함수를 호출하여 세마포 값을 감소시키려고 함.
세마포 값이 양수이면 값이 감소되고 스레드는 계속 실행함.
세마포 값이 0이면 스레드는 기다림.
스레드는 sem_post 함수를 호출하여 세마포 값을 증가시킴.
기다리는 스레드가 있으면 그중 하나가 깨어날 수 있음.
사용이 끝난 이름 없는 세마포는 sem_destroy 함수로 제거함.
이름 있는 세마포는 sem_open 함수를 통해 생성하거나 열 수 있음.
sem_open은 이름을 가진 세마포에 대한 접근을 제공함.
사용이 끝나면 sem_close로 닫을 수 있음.
더 이상 필요 없는 이름 있는 세마포는 sem_unlink로 제거할 수 있음.
POSIX 세마포는 자원 개수 제어나 프로세스 간 동기화에 사용할 수 있음.
Counting semaphore로 사용할 수도 있고, 초기값을 1로 두어 binary semaphore처럼 사용할 수도 있음.
POSIX 조건 변수
POSIX 조건 변수는 특정 조건이 만족될 때까지 스레드를 기다리게 하는 동기화 도구.
조건 변수는 pthread_cond_t 자료형으로 선언됨.
조건 변수는 보통 mutex와 함께 사용됨.
조건 자체를 검사하는 공유 변수는 mutex로 보호되어야 하기 때문.
조건 변수는 pthread_cond_init 함수로 초기화할 수 있음.
스레드는 조건이 만족되지 않으면 pthread_cond_wait 함수를 호출하여 기다림.
pthread_cond_wait 함수에는 조건 변수와 mutex가 전달됨.
pthread_cond_wait는 호출한 스레드를 조건 변수의 대기 큐에 넣음.
동시에 전달된 mutex를 원자적으로 해제함.
이것이 중요한 이유는 다른 스레드가 mutex를 얻어 조건을 변경할 수 있어야 하기 때문.
조건이 만족되어 다른 스레드가 signal을 보내면 기다리던 스레드가 깨어남.
깨어난 스레드는 pthread_cond_wait에서 반환되기 전에 mutex를 다시 획득함.
따라서 조건 변수 wait는 mutex 해제, 대기, mutex 재획득을 하나의 구조로 제공함.
다른 스레드는 조건을 만족시키는 작업을 한 뒤 pthread_cond_signal을 호출할 수 있음.
pthread_cond_signal은 조건 변수에서 기다리는 스레드 중 하나를 깨움.
여러 스레드를 모두 깨우려면 pthread_cond_broadcast를 사용할 수 있음.
조건 변수는 일반적으로 while문과 함께 사용됨.
조건이 거짓인 동안 pthread_cond_wait를 호출하는 방식.
스레드가 깨어났다고 해서 조건이 반드시 참이라는 보장이 항상 있는 것은 아니기 때문.
또한 여러 스레드가 깨어난 뒤 경쟁하여 조건이 다시 거짓이 될 수도 있음.
따라서 조건은 깨어난 뒤 다시 검사되어야 함.
조건 변수는 생산자-소비자 문제에서 버퍼가 비었거나 가득 찬 상태를 기다리는 데 사용할 수 있음.
조건 변수는 세마포처럼 값을 저장하는 객체가 아님.
따라서 signal이 먼저 발생하고 나중에 wait가 호출되면 그 signal은 저장되지 않음.
조건 변수는 반드시 조건을 나타내는 공유 변수와 함께 사용되어야 함.
Java에서의 동기화
Java는 언어 수준과 라이브러리 수준에서 동기화 기능을 제공함.
여러 스레드를 쉽게 생성할 수 있는 Java 프로그램에서는 공유 객체에 대한 동기화가 중요함.
대표적인 동기화 도구에는 모니터, 재진입 락, 세마포, 조건 변수가 있음.
Java 모니터
Java의 모든 객체는 하나의 모니터 락을 가짐.
이 락을 intrinsic lock 또는 monitor lock이라고 부를 수 있음.
synchronized 키워드는 이 모니터 락을 사용하여 상호 배제를 제공함.
synchronized 메서드를 선언하면 그 메서드에 들어가기 전에 객체의 모니터 락을 획득해야 함.
어떤 스레드가 synchronized 메서드를 실행 중이면
같은 객체의 다른 synchronized 메서드에 다른 스레드가 동시에 들어갈 수 없음.
같은 객체의 synchronized 메서드들은 같은 모니터 락으로 보호됨.
메서드 실행이 끝나면 모니터 락은 자동으로 해제됨.
synchronized 블록도 사용할 수 있음.
synchronized 블록은 특정 객체의 락을 기준으로 코드 일부만 보호하는 방식.
특정 객체를 기준으로 synchronized 블록에 들어가면 해당 객체의 모니터 락을 획득한 뒤 블록을 실행함.
블록을 빠져나오면 락이 해제됨.
이 방식은 메서드 전체가 아니라 필요한 코드 영역만 동기화할 수 있다는 점에서 유용함.
Java 모니터는 상호 배제를 자동으로 제공하므로 공유 객체의 상태를 보호하는 데 사용됨.
또한 Object 클래스에 정의된 wait, notify, notifyAll 메서드를 통해 조건 대기도 지원함.
wait는 현재 스레드를 객체의 조건 대기 집합에 넣고 모니터 락을 해제함.
notify는 해당 객체에서 기다리는 스레드 중 하나를 깨움.
notifyAll은 해당 객체에서 기다리는 모든 스레드를 깨움.
wait, notify, notifyAll은 synchronized 영역 안에서 호출되어야 함.
wait를 호출한 스레드는 깨어난 뒤 다시 모니터 락을 획득해야 계속 실행할 수 있음.
notify가 호출되었다고 해서 깨어난 스레드가 즉시 실행되는 것은 아님.
현재 락을 가진 스레드가 synchronized 영역을 빠져나가야 깨어난 스레드가 락을 얻을 수 있음.
Java 모니터의 조건 대기 기능은 조건 변수와 비슷한 역할.
그러나 하나의 객체에는 하나의 wait set만 존재함.
따라서 여러 조건을 구분하기 어려울 수 있음.
이런 경우에는 java.util.concurrent.locks 패키지의 Condition을 사용할 수 있음.
재진입 락
Java는 ReentrantLock 클래스를 제공함.
ReentrantLock은 java.util.concurrent.locks 패키지에 포함됨.
ReentrantLock은 명시적인 lock과 unlock 연산을 제공함.
스레드는 lock 메서드를 호출하여 락을 획득함.
임계구역 실행이 끝나면 unlock 메서드를 호출하여 락을 해제함.
unlock은 보통 finally 블록에서 호출함.
그 이유는 예외가 발생해도 락이 반드시 해제되도록 하기 위함.
만약 unlock이 실행되지 않으면 다른 스레드들이 계속 락을 기다릴 수 있음.
ReentrantLock은 재진입 가능함.
재진입 가능하다는 것은 같은 스레드가 이미 획득한 락을 다시 획득할 수 있다는 의미.
같은 스레드가 같은 락을 여러 번 획득하면 그만큼 unlock도 호출해야 락이 완전히 해제됨.
Java의 synchronized 락도 재진입 가능함.
ReentrantLock은 synchronized보다 더 명시적인 락 제어를 제공함.
또한 공정성 옵션을 사용할 수 있음.
공정한 ReentrantLock은 오래 기다린 스레드가 먼저 락을 얻도록 할 수 있음.
하지만 공정성 보장은 성능 비용을 증가시킬 수 있음.
ReentrantLock은 tryLock 같은 기능도 제공할 수 있음.
tryLock은 락을 즉시 얻을 수 있으면 true를 반환하고, 얻을 수 없으면 기다리지 않고 false를 반환함.
이 기능은 교착 상태를 피하거나 대기 시간을 제한하는 데 사용할 수 있음.
Java 세마포
Java는 Semaphore 클래스를 제공함.
Semaphore는 java.util.concurrent 패키지에 포함됨.
Java Semaphore는 counting semaphore로 사용할 수 있음.
Semaphore 객체는 허가의 개수를 가지고 있음.
스레드는 acquire 메서드를 호출하여 허가 하나를 얻으려고 함.
허가가 남아 있으면 acquire는 허가 수를 감소시키고 스레드를 계속 실행시킴.
허가가 없으면 스레드는 허가가 반환될 때까지 기다림.
스레드는 release 메서드를 호출하여 허가 하나를 반환함.
release는 허가 수를 증가시키고, 기다리는 스레드가 있으면 깨울 수 있음.
Semaphore의 초기 허가 수를 1로 두면 binary semaphore처럼 사용할 수 있음.
초기 허가 수를 n으로 두면 n개의 동일 자원을 제어하는 counting semaphore처럼 사용할 수 있음.
예를 들어 동시에 최대 5개의 스레드만 특정 자원에 접근하게 하려면 Semaphore를 5로 초기화할 수 있음.
각 스레드는 자원 사용 전에 acquire를 호출하고, 자원 사용 후 release를 호출함.
Java Semaphore도 공정성 옵션을 제공할 수 있음.
공정한 Semaphore는 오래 기다린 스레드가 먼저 허가를 받도록 할 수 있음.
하지만 공정성 옵션은 성능에 영향을 줄 수 있음.
Java 조건 변수
Java의 Condition 인터페이스는 조건 변수를 제공함.
Condition은 ReentrantLock과 함께 사용됨.
하나의 ReentrantLock에서 여러 개의 Condition 객체를 만들 수 있음.
이 점은 객체마다 하나의 wait set만 제공하는 기본 Java 모니터보다 유연함.
Condition 객체는 newCondition 메서드를 통해 생성됨.
예를 들어 lock.newCondition()을 호출하여 조건 변수를 만들 수 있음.
스레드는 조건이 만족되지 않으면 await 메서드를 호출함.
await는 현재 스레드를 조건 대기 큐에 넣고 락을 해제함.
나중에 깨어난 스레드는 다시 락을 획득한 뒤 계속 실행함.
다른 스레드는 조건을 만족시키는 작업을 한 뒤 signal 또는 signalAll을 호출함.
signal은 기다리는 스레드 중 하나를 깨움.
signalAll은 기다리는 모든 스레드를 깨움.
Condition을 사용할 때도 조건 검사는 일반적으로 while문으로 수행함.
스레드가 깨어났더라도 조건이 여전히 만족되지 않을 수 있기 때문.
Condition은 생산자-소비자 문제에서 notFull과 notEmpty처럼 여러 조건을 분리하는 데 유용함.
버퍼가 가득 찼을 때 생산자는 notFull 조건에서 기다림.
버퍼가 비었을 때 소비자는 notEmpty 조건에서 기다림.
생산자가 항목을 넣으면 notEmpty.signal을 호출하여 소비자를 깨울 수 있음.
소비자가 항목을 꺼내면 notFull.signal을 호출하여 생산자를 깨울 수 있음.
이처럼 Java Condition은 모니터의 조건 변수 개념을 명시적인 락과 함께 제공하는 방식.
대체 접근법
Mutex 락, 세마포, 모니터 같은 전통적인 동기화 도구는 강력하지만 사용하기 어려울 수 있음.
락을 잘못 사용하면 경쟁 조건, 교착 상태, 기아 상태가 발생할 수 있음.
또한 락의 범위가 너무 크면 병행성이 떨어짐.
반대로 락의 범위가 너무 작으면 오류 가능성이 커질 수 있음.
이러한 문제를 줄이기 위해 여러 대체 접근법이 제안됨.
대표적인 대체 접근법에는 트랜잭션 메모리, OpenMP, 함수형 프로그래밍 언어가 있음.
트랜잭션 메모리
트랜잭션 메모리는 데이터베이스의 트랜잭션 개념을 메모리 연산에 적용한 방식.
트랜잭션은 하나의 논리적 작업 단위.
트랜잭션 안의 연산들은 모두 성공하거나 모두 실패해야 함.
트랜잭션 메모리에서는 공유 메모리에 대한 읽기와 쓰기 연산을 하나의 원자적 트랜잭션으로 묶음.
트랜잭션이 성공하면 그 안의 모든 변경 사항이 한꺼번에 반영됨.
트랜잭션이 실패하면 변경 사항은 취소되고 원래 상태로 되돌아감.
프로그래머는 명시적인 락 대신 atomic 블록과 같은 구조를 사용할 수 있음.
atomic 블록 안의 코드는 하나의 트랜잭션처럼 실행됨.
동시에 실행되는 다른 트랜잭션과 충돌이 없으면 정상적으로 완료됨.
만약 두 트랜잭션이 같은 데이터를 충돌하는 방식으로 접근하면 하나의 트랜잭션이 중단될 수 있음.
중단된 트랜잭션은 롤백된 뒤 다시 시도될 수 있음.
트랜잭션 메모리의 장점은 명시적인 락 사용을 줄일 수 있다는 점.
프로그래머가 lock과 unlock의 정확한 위치를 직접 관리하지 않아도 됨.
따라서 교착 상태 가능성을 줄일 수 있음.
또한 시스템은 실제 충돌이 발생할 때만 트랜잭션을 중단시킬 수 있음.
서로 충돌하지 않는 트랜잭션들은 병렬로 실행될 수 있음.
트랜잭션 메모리는 하드웨어로 구현될 수도 있고 소프트웨어로 구현될 수도 있음.
하드웨어 트랜잭션 메모리는 HTM이라고 함.
HTM은 캐시와 캐시 일관성 프로토콜 같은 하드웨어 기능을 활용하여 트랜잭션 충돌을 감지함.
하드웨어 지원이 있으므로 빠를 수 있지만 하드웨어 제한을 받을 수 있음.
소프트웨어 트랜잭션 메모리는 STM이라고 함.
STM은 컴파일러와 런타임 시스템이 트랜잭션을 관리하는 방식.
하드웨어 지원 없이 구현할 수 있지만 오버헤드가 더 클 수 있음.
트랜잭션 메모리는 병행 프로그래밍을 단순화할 수 있는 접근법.
하지만 모든 상황에서 전통적인 락을 완전히 대체하는 것은 아님.
트랜잭션 크기, 충돌 빈도, 하드웨어 지원 여부에 따라 성능이 달라질 수 있음.
OpenMP
OpenMP는 C, C++, FORTRAN에서 공유 메모리 병렬 프로그래밍을 지원하는 API와 컴파일러 지시문의 집합.
OpenMP는 개발자가 코드에 지시문을 추가하여 병렬 실행을 표현하게 함.
스레드 생성과 관리의 많은 부분은 컴파일러와 런타임 시스템이 처리함.
동기화와 관련하여 OpenMP는 critical 지시문을 제공함.
critical 지시문이 붙은 코드 영역은 한 번에 하나의 스레드만 실행할 수 있음.
OpenMP critical section은 임계구역을 표현하는 방법.
여러 스레드가 공유 변수 sum을 갱신하는 경우, sum 갱신 부분을 critical 영역으로 지정할 수 있음.
그러면 여러 스레드가 동시에 sum을 변경하지 못함.
OpenMP의 critical 지시문은 명시적인 mutex 락을 직접 만들지 않고도 상호 배제를 제공함.
프로그래머는 임계구역으로 보호할 코드 블록을 지정하면 됨.
OpenMP 런타임은 그 영역에 한 번에 하나의 스레드만 들어가도록 관리함.
OpenMP는 atomic 지시문도 제공할 수 있음.
atomic 지시문은 단일 메모리 위치에 대한 단순 갱신을 원자적으로 수행하도록 지정하는 방식.
critical은 코드 블록 전체를 보호할 수 있음.
atomic은 보통 하나의 단순 연산에 더 적합함.
OpenMP는 병렬 루프와 동기화 지시문을 함께 제공하므로 과학 계산이나 배열 처리에 유용함.
하지만 OpenMP를 사용하더라도 공유 자료 접근을 잘못 설계하면 성능 저하나 동기화 오류가 발생할 수 있음.
함수형 프로그래밍 언어
함수형 프로그래밍 언어는 병행 프로그래밍에서 동기화 문제를 줄일 수 있는 또 다른 접근법.
전통적인 명령형 프로그래밍에서는 변수의 상태가 계속 변경됨.
여러 스레드가 같은 변수를 변경하면 경쟁 조건이 발생할 수 있음.
함수형 프로그래밍은 상태 변경을 최소화하거나 피하려는 특징을 가짐.
함수형 언어에서는 데이터가 불변으로 취급되는 경우가 많음.
불변 데이터는 한 번 만들어진 뒤 변경되지 않음.
여러 스레드가 같은 불변 데이터를 읽어도 데이터가 바뀌지 않으므로 경쟁 조건이 발생하지 않음.
또한 함수형 프로그래밍은 부작용이 없는 함수를 강조함.
부작용이 없는 함수는 외부 상태를 변경하지 않고 입력에 따라 출력만 계산함.
이런 함수는 병렬로 실행하기 쉬움.
공유 상태를 변경하지 않기 때문에 동기화가 덜 필요하기 때문.
Erlang과 Scala 같은 언어는 함수형 프로그래밍 개념을 병행 프로그래밍에 활용할 수 있음.
Erlang은 메시지 전달 기반 병행성을 강조함.
프로세스들이 메모리를 직접 공유하기보다 메시지를 주고받는 방식.
Scala는 함수형 프로그래밍과 객체지향 프로그래밍을 함께 지원함.
함수형 접근법은 공유 가변 상태를 줄여 동기화 문제를 완화할 수 있음.
하지만 모든 프로그램을 순수 함수형 방식으로 작성하는 것은 쉽지 않을 수 있음.
입출력, 사용자 인터페이스, 데이터베이스 갱신처럼 상태 변경이 필요한 작업도 존재함.
따라서 함수형 프로그래밍은 동기화 문제를 줄이는 중요한 방향이지만, 모든 동기화 문제를 자동으로 없애는 것은 아님.