동기화
•
A라는 메모리에 10이 저장되어 있고 프로세스 P1에서 해당 메모리를 읽어 10이라는 값을 들고 있는 상황에서, 프로세스 P2에서 A의 값을 15로 바꾸고 나서 프로세스 P1에서 A에 10의 값을 추가하는 동작을 수행하면 15 + 10 = 25가 아닌 10 + 10 = 20의 값이 저장된다.
•
이처럼 다수의 프로세스나 스레드에서 동일한 공유 자원에 동시에 접근해야하는 경우, 일관된 순서가 보장되지 않으면 데이터 일관성이 깨지게 된다. 이러한 상황을 경쟁 상태(Race Condition)이라 하고, 이를 막기 위해 공유자원에 접근할 때 접근 순서를 보장해주는 과정이 동기화다.
데이터 일관성(데이터 정합성, Data Consistency)
데이터들의 값들이 서로 일치되는 상태를 의미한다. 데이터 일관성 문제는 두 개 이상의 프로세스나 스레드가 데이터를 공유하는 환경에서 서로 교차적으로 데이터를 사용할 때 각 스레드에서 데이터가 달라 데이터 정합성이 지켜지지 않는 상황을 말한다.
경쟁 상태(Race Condition)
•
다수의 프로세스나 스레드들이 같은 공유 자원에 동시에 접근하고 값을 조작하는 상황을 의미한다.
•
경쟁 상태가 발생하면 동시성 이슈가 발생할 수 있다.
임계 구역(Critical Section)
•
경쟁 상태에 놓인 프로세스들의 공유 메모리나 스레드의 메모리 영역을 의미하며, 여러 프로세스나 스레드에 의해 동시 다발적으로 접근될 가능성이 있는 영역을 말한다.
•
공유 자원의 데이터 일관성을 지키기 위해 공유 자원에 접근하는 스레드가 하나만 존재하도록 관리해야하는데, 이 공유 자원을 임계 구역이라 부른다.
임계 구역 문제(CSP, Critical Section Problem)
•
여러 프로세스나 스레드들이 임계 구역을 상호배제를 지키지 않고 임계 구역에 접근하는 문제를 임계 구역 문제(CSP, Critical Section Problem)라 부른다.
•
임계 구역 문제를 해결하기 위해서는 다음 세 가지 조건을 만족 해야 한다.
◦
상호배제(Mutual Exclusion)
▪
하나의 프로세스나 스레드가 임계 구역에서 실행 중이라면, 다른 스레드는 해당 임계 구역에 접근할 수 없다. 즉, 오직 하나의 프로세스만이 임계 구역에 진입할 수 있다.
◦
진행(Progress)
▪
한 임계 구역에 접근하는 스레드를 결정하는 것은 유한 시간 이내에 이루어져야 한다는 의미로, 임계 구역에 대한 접근 요청이 영원히 지연되지 않아야 한다. 다시말해, 임계 구역에 진입한 프로세스가 없다면 임계 구역에 접근하기 위해 대기 중인 프로세스 중 하나는 반드시 진입할 수 있어야 한다.
◦
한정 대기(Bounded Waiting)
▪
임계 구역에 진입하기 위해 대기하는 모든 스레드는 유한 시간 이내에 해당 임계 구역으로 진입할 수 있어야 한다는 의미로, 어떤 프로세스든 임계 구역 진입을 영원히 기다리지 않아야 한다. 어떤 프로세스의 진입 요청이 거부되면, 일정 시간 내에 그 프로세스에 대한 다음 진입 요청이 승인되어야 한다.
•
임계 구역 문제 해결에 대한 코드는 아래와 같이 구성된다.
◦
enter section(entry section) : 임계 구역에 들어가기 위해 진입 허가 요청을 하는 부분
◦
critical section: 임계 구역. 한 프로세스가 임계 구역에 진입 중이면 다른 프로세스는 접근할 수 없다.
◦
exit section: 임계 구역을 빠져나오는 부분
◦
remainder section: 임계 구역이 아닌 나머지 부분
임계 구역 문제 해결 방법(동기화 방법)
1.
소프트웨어 기반 해결 방법
•
임계 구역을 가진 스레드의 런타임이 겹치지 않게 하는 방법이다.
•
Peterson 알고리즘
◦
임계 구역으로 진입할 프로세스의 순번을 나타내는 turn과 특정 프로세스가 임계 구역으로 들어갈 준비가 되었다는 것을 나타내는 flag를 통해 임계 구역으로 진입할 스레드를 결정하는 방법이다.
•
Bakery 알고리즘
◦
프로세스에 잠금을 걸고 잠금이 걸린 다른 프로세스를 확인하고 우선순위를 확인하여 임계 구역에 진입하는 방법으로, 우선순위는 프로세스에 오름차순으로 번호를 할당하여 받은 번호와 pid를 통해 결정한다.
2.
하드웨어 기반 해결 방법(Memory Barrier, test_and_set & compare_and_swap)
•
동기화 문제를 하드웨어 측면에서 해결하기 위한 방법으로, 공유 자원에 접근이 이뤄지는 동안 인터럽트가 발생하지 않도록 하는 방법이다.
•
메모리 장벽(Memory Barrier)
◦
메모리의 모든 변경 사항을 모든 프로세서에 전파하여, 다른 프로세서에서 실행 중인 스레드에 의한 메모리 변경 사항을 확인하는 방법이다. 다른 프로세서에서 메모리를 변경하기 전까지 대기하도록 구성하여 메모리 장벽 이전의 동작이 완료된 후 뒤의 동작이 실행되도록 보장한다.
•
test_and_set() & compare_and_swap()
◦
데이터 접근 → 연산 → 결과 저장의 과정을 원자적(atomically)으로 동작하는 명령어인 test_and_set()이나 compare_and_swap() 명령어를 사용하는 방법이다.
원자적(atomically) 동작
더 이상 나누어질 수 없는 하나의 동작처럼 작업을 수행하는 것으로, 인터럽트가 발생해도 멈추지 않는다.
3.
상위 수준 소프트웨어 도구(Mutex Lock, Semaphore)
•
하드웨어 기반 해결 방법은 응용 프로그래머가 사용할 수 없기 때문에, 임계 구역 문제를 쉽게 해결하기 위해 개발된 상위 수준의 소프트웨어 도구이다.
•
Mutex Lock
◦
mutual exclusion의 축약어로, 임계 구역 진입 전에 mutex lock을 걸고 임계 구역을 빠져나올 때 mutex lock을 해제하는 방법이다.
•
Semaphore
◦
Mutex lock과 유사하게 동작하지만 더 정교하게 동기화할 수 있는 방법으로, S라는 정수 변수를 저장하여 wait() 함수를 통해 S를 감소 시키고 signal() 함수를 통해 S를 증가 시키며 S가 음수인 경우 다른 스레드에서 S를 증가시키기까지 대기하는 방법이다.
Spin-lock과 Busy-wating
•
spin-lock
◦
Lock을 얻을 때까지 무한 루프를 돌며 계속 Lock을 얻으려 시도하는 방식이다. CPU 스케줄링에 따라 Context Switching이 발생하기 전까지 계속하여 시도하기 때문에 busy-wating 문제가 있다.
•
busy-wating
◦
운영체제에서 원하는 자원을 얻기 위해, 대기하는 것이 아니라 권한을 얻을 때까지 반복해서 확인하는 것을 의미한다. 권한을 획득하기 위해 반복적으로 확인하며 CPU를 점유하고 있기 때문에, 다른 스레드가 생산적인 작업을 할 수 있는 CPU 주기를 낭비한다.
•
따라서 busy-wating 방식은 자원의 권한을 얻는데 적은 시간이 소요되는 상황과, Context Switching의 오버헤드보다 성능적 이득이 더 큰 경우에 사용하는 것이 효율적이다.
•
Sleeping
◦
busy-wating 문제로 인해 성능 저하가 예상된다면, 타이머를 설정하고 Wait Queue에 스레드 정보를 담은 후 타이머 인터럽트가 발생하면 해당 스레드를 깨워 CPU를 사용하는 sleeping 방식을 사용하는 것이 좋다.
•
sleeping 방식에는 Wait Queue에 스레드 정보를 넣고 꺼내는 비용과 Context Switching 비용이 발생하기 때문에 프로그램의 특성을 잘 파악하고 설계하는 것이 좋다.
Mutex lock
•
상호 배제의 개념을 이용하여 임계 구역에 진입하기 전 mutex lock을 걸고 임계 구역에서 나올 때 mutex lock을 해제하는 방식이다.
•
다른 스레드가 임계 구역에 접근 중이면 mutex lock이 걸려있기 때문에 임계 구역에 접근할 수 없게 만들어 동기화 문제를 해결한다.
•
mutex lock은 spin-lock 방식이기 때문에 busy-wating 문제가 존재한다.
Semaphore
•
mutex lock과 유사하게 동작하지만, S라는 정수 변수를 두어 임계 구역에 접근할 수 있는 스레드의 수까지 제어할 수 있는 방법이다.
•
각 스레드는 임계 구역에 접근할 때 S 값을 감소시키고 임계 구역에서 나올 때 S 값을 증가시키는 방식으로 동작하며, S 값이 음수가 되면 임계 구역에 들어가 있는 스레드 중 하나가 임계 구역을 나오며 S 값을 증가시키기까지 대기한다.
•
mutex lock과 유사하게 동작하는 0과 1의 값만 가능한 이진 세마포어와 제한 없이 사용하는 카운팅 세마포어가 있다.
•
세마포어의 변수 S는 두 개의 atomic한 연산을 통해서만 증가시키고 감소시킬 수 있다. 한 프로세스가 세마포어 변수를 수정할 때 다른 프로세서가 동시에 세마포어 변수를 수정할 수 없다.
•
세마포어를 사용하여도 busy-waiting 문제를 완전히 해결하지는 못한다. 다만 busy-waiting 문제를 연산의 임계 구역에만 국한하였고, 이 임계 구역은 매우 짧기 때문에 busy-waiting은 드물게 발생하고 그 시간이 아주 짧다.
Monitor
•
동기화를 잘못 사용하게 되면, 발견하기 어렵거나 간헐적으로 발생하는 타이밍 오류가 생길 수 있다. 이런 오류는 mutex lock이나 semaphore를 잘못 사용하는 경우 발생하는데, 이를 상황을 피하기 위해 고급 언어 구조물인 monitor 타입을 이용한다.
•
개발자의 코드를 상호 배제 하게끔 만든 추상화된 데이터 형태로, 하나의 데이터마다 하나의 모니터와 결합하여 모니터와 결합된 데이터가 동시에 두 개 이상의 스레드에서 접근할 수 없는 잠금(lock) 기능을 제공한다.
•
다시말해, 데이터에 모니터를 결합하면 하나의 스레드가 그 데이터를 사용하는 동안 다른 스레드가 그 데이터를 사용할 수 없게 된다. 프로그래머는 Monitor를 사용하면 직접 lock을 하지 않아도 동기화 문제 없이 공유 데이터를 사용할 수 있다.