배경
•
여러 개의 프로세서에서 동시에 같은 메모리에 접근하여 데이터를 조작하려한다면, 값이 제대로 저장되지 않거나 제대로 읽어오지 못하는 부정확 상태가 된다.
•
이렇게 여러 프로세스가 동일한 데이터에 접근하여 조작하고, 실행 결과가 특정 순서에 의존하는 상황을 경쟁 상황(race condition)이라 한다.
•
다중 스레드 어플리케이션에서 자원을 공유할 가능성이 높은 여러 스레드가 서로 다른 코어에서 병렬로 실행된다면, 서로 간에 영향을 주지 않기 위해 프로세스 동기화와 조정이 필요하다.
임계구역 문제
•
프로세스 동기화는 임계구역 문제를 해결하기 위한 방안으로, 임계 구역(critical section)이란 각 프로세스에 적어도 다른 하나의 프로세스와 공유하여 동시에 데이터에 접근할 수 있는 구간을 말한다.
•
임계 구역 문제는 이러한 임계 구역에 접근하는 프로세스들이 자신의 활동을 동기화하지 않고 동시에 접근하는 문제로, 이를 피하기 위해서는 임계 구역으로 진입하기 전에 진입 허가를 요청해야한다.
•
임계 구역에 진입하기 위해 허가 요청을 하는 코드 구현 부분을 진입 구역(entry section)이라 부르고, 임계 구역에서 작업을 처리 후 임계 구역에서 나오는 부분을 퇴출 구역(exit section)이라 부른다. 그 외의 나머지 코드 부분을 나머지 구역(remainder section)이라 부른다.
•
임계 구역 문제를 해결하기 위해서는 세 가지 조건을 충족해야한다.
◦
상호 배제(mutual exclusion) : 하나의 프로세스나 스레드가 임계 구역에서 실행 중이라면, 다른 스레드는 해당 임계 구역에 접근할 수 없다. 즉, 오직 하나의 프로세스만이 임계 구역에 진입할 수 있다.
◦
진행(progress) : 한 임계 구역에 접근하는 스레드를 결정하는 것은 유한 시간 이내에 이루어져야 한다는 의미로, 임계 구역에 대한 접근 요청이 영원히 지연되지 않아야 한다. 다시말해, 임계 구역에 진입한 프로세스가 없다면 임계 구역에 접근하기 위해 대기 중인 프로세스 중 하나는 반드시 진입할 수 있어야 한다.
◦
한정된 대기(bounded waiting) : 임계 구역에 진입하기 위해 대기하는 모든 스레드는 유한 시간 이내에 해당 임계 구역으로 진입할 수 있어야 한다는 의미로, 어떤 프로세스든 임계 구역 진입을 영원히 기다리지 않아야 한다. 어떤 프로세스의 진입 요청이 거부되면, 일정 시간 내에 그 프로세스에 대한 다음 진입 요청이 승인되어야 한다.
•
운영체제 내에서도 임계구역을 다루기 위해서 선점형 커널 방식과 비선점형 커널 방식이 존재한다.
◦
선점형 커널 방식은 커널 모드에서 수행되는 프로세스가 있다면, 해당 프로세스의 선점을 허용하는 방식이다.
◦
비선점형 커널 방식은 커널 모드에서 수행되는 프로세스가 있더라도, 자발적으로 CPU의 제어를 양보할 때까지 계속 수행되는 방식이다.
Peterson 알고리즘
•
Peterson 알고리즘은 임계구역으로 진입할 순번을 나타내는 turn 변수와 각 프로세스가 임계구역에 진입할 준비가 되었는지를 나타내는 flag 변수를 통해 임계 구역으로 진입할 프로세스를 정하는 방식이다.
하드웨어 기반 해결방법
•
동기화 문제를 하드웨어 측면에서 해결하기 위한 방법으로, 공유 자원에 접근이 이뤄지는 동안 인터럽트가 발생하지 않도록 하는 방법이다.
1.
메모리 장벽(Memory Barrier)
•
메모리의 모든 변경 사항을 모든 프로세서에 전파하여, 다른 프로세서에서 실행 중인 스레드에 의한 메모리 변경 사항을 확인하는 방법이다. 다른 프로세서에서 메모리를 변경하기 전까지 대기하도록 구성하여 메모리 장벽 이전의 동작이 완료된 후 뒤의 동작이 실행되도록 보장한다.
2.
test_and_set() & compare_and_swap()
•
데이터 접근 → 연산 → 결과 저장의 과정을 원자적(atomically)으로 동작하는 명령어인 test_and_set()이나 compare_and_swap() 명령어를 사용하는 방법이다.
원자적(atomically) 동작
더 이상 나누어질 수 없는 하나의 동작처럼 작업을 수행하는 것으로, 인터럽트가 발생해도 멈추지 않는다.
3.
원자적 변수
•
정수형이나 bool 형과 같은 기본 데이터 유형에 대한 원자적 연산을 제공하는 원자적 변수(atomic variable)을 사용하여 데이터를 저장하는 방법이다.
Mutex Locks
•
임계 구역을 보호하고 경쟁 조건을 방지하기 위해 mutex lock을 사용하는 방법으로, 프로세스가 임계 구역에 들어가기 위해서는 락을 획득해야만 하고 임계 구역을 빠져나올 때 락을 반환한다.
•
어느 프로세스가 임계 구역에 진입해있다면 락을 획득하고 들어갔기 때문에, 다른 프로세스가 락을 얻지 못해 임계 구역에 진입하지 못하게 되어 동기화 문제를 해결한다.
•
락을 획득할 때까지 반복해서 확인하고 있는 스핀락(spin-lock) 방식이기 때문에 바쁜 대기(busy waiting)를 해야한다는 단점이 있다. 하나의 프로세스가 임계 구역에 들어가 있다면, 임계 구역에 접근하려는 모든 프로세스는 락을 획득하기 위한 함수를 호출하는 반복문을 실행하고 있어야한다. 이런 바쁜 대기 상태는 다른 프로세스가 CPU를 생산적으로 활용할 수 있는 주기를 낭비한다.
Semaphores
•
세마포어는 mutex와 비슷하게 동작하지만 정수 변수 S를 두어 락을 획득할 수 있는 프로세스의 수를 조정할 수 있는 방식이다.
•
세마포어는 정수 변수 S를 두고 두 개의 원자적 연산 wait()과 signal()로만 접근 가능하다. wait()을 통해 락을 획득하고 signal()을 통해 락을 반환한다.
•
정수 S를 초기화하고 프로세스에서 락을 획득할 때마다 그 값을 감소하여 0이 되면 더이상 락을 획득할 수 없고 락을 얻은 프로세스가 반환하기를 기다려야한다. 이러한 방식으로 S가 초기화된 수만큼의 프로세스만 접근을 허용한다.
•
S값의 제한이 없는 카운팅 세마포어(counting semaphore)와 0과 1의 값만 가져 mutex와 유사하게 동작하는 이진 세마포어(binary semaphore)가 있다.
•
세마포어 역시 바쁜 대기를 해야한다는 문제점이 있다. 이 문제는 세마포어가 0인 경우 프로세스를 세마포어와 연관된 대기 큐에 넣고 대기 상태로 전환 후 signal() 연산이 발생하면 큐에서 꺼내 wakeup 시키는 방법을 통해 부분적으로 해결할 수 있다.
모니터
•
동기화를 잘못 사용하게 되면, 발견하기 어렵거나 간헐적으로 발생하는 타이밍 오류가 생길 수 있다. 이런 오류는 mutex lock이나 semaphore를 잘못 사용하는 경우 발생하는데, 이를 상황을 피하기 위해 고급 언어 구조물인 monitor 타입을 이용한다.
•
추상화된 데이터 형(ADT, Abstract Data Type)은 데이터와 해당 데이터를 조작하는 함수들을 하나의 단위로 묶어 보호하는 방법이다. 모니터 방식은 이런 ADT의 일종인 모니터 형을 통해 변수의 선언부터 변수의 조작까지 일괄적으로 관리하여 동기화 문제를 해결하는 방법이다.
•
하나의 예시를 들면, condition이라는 모니터 형을 사용하여 변수를 정의하고 이를 통해 락을 얻고 반환하는 연산은 다음과 같다.
condition x, y;
x.wait();
x.signal();
TypeScript
복사
•
wait()이 호출되면 해당 프로세스는 다른 프로세스에서 signal()을 호출할 때까지 일시 중지된다.
라이브니스(Liveness)
•
라이브니스는 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야하는 속성을 말한다.
1.
교착 상태(Deadlock)
•
프로세스나 스레드가 자원을 얻지 못해 다음 작업을 수행하지 못하는 상태로, 교착 상태라고도 불린다. 주로 멀티 프로그래밍 환경에서 한정된 자원을 사용하려 서로 경쟁하는 과정에서 발생한다.
2.
우선순위 역전
•
우선순위 역전(priority inversion) 문제는 낮은 우선순위를 가진 프로세스에서 특정 자원을 차지하고 있을 때, 높은 우선순위를 가지는 프로세스가 해당 자원을 필요로 하는 상황에서 중간 우선순위의 프로세스가 실행 가능 상태가 되어 선점해버리게 되면 발생한다.
•
우선순위 역전 문제는 높은 우선순위를 가지는 프로세스가 원하는 자원을 가지고 있는 프로세스가 해당 프로세스보다 높은 우선순위를 가지게 하는 우선순위 상속 프로토콜(priority-inheritance protocol)을 통해 해결할 수 있다.