race condtion과 이를 예방할 동기화 기법을 알아본다.
위의 코드가 과연 0이 나올까? 각각 1000번의 반복으로 increment, decrement를 수행한다.
그러나 특정 순간에 Scheduling이 발생한다면 어떻게 할까?
함수명이 바뀌면 scheduling이 발생했다 가정해보면
x:0
thread_increment
val=x
thread_decrement(Scheduled)
val=x -> x=val-1
x: -1
thread_increment(Scheduled)
x=val+1
x:1
이런 결과가 나온다. 두 함수를 각각 한 번씩 실행했는데 결과값이 1이 나온 것이다.
이는 postfix, prefix increment, decrement 연산자를 풀어놓은 것과 같다.
이 연산자들도 위와 같이 x를 가져오고, 1를 빼거나 더해주고, 다시 x에 저장한다.
lw, add, sw 최소 세 개의 instruction으로 구성되어 있으며, 이 instruction 수행 중 scheduling이 발생하면 예상한 값과 다른 값이 나오는 것이다.
이를 race condition이라 칭한다.
race condtion이란 쓰레드나 프로세스가 Shared resource에 동시에 접근했을 때 발생한다.
race condtion은 알아차리기 쉽지 않다. 이는 instruction 레벨에서 발생하기 때문이다.
scheduling도 매번 프로그램을 실행할 때마다 다를 것이다.
uniprocessor 환경에서 scheduling 때문에 발생할 수 있고
multiprocessor 환경에선, 두 개의 thread가 하나의 shared resource에 동시에 접근할 때 발생한다.
이제부터 race condtion을 해결할 수 있는 동기화 기법을 알아본다.
이 쓰레드를 사용할 때, 하나의 연산자는 instruction 레벨에선 여러개일 수 있고, atomic operation을 구현하는 것이 여간 쉽지 않다.
게다가 atomic operation을 잘못 구현하면, 연산의 순서도 꼬이게 된다.
Synchronization
동기화를 위한 용어를 정리해보자.
- Critical Resource: Thread는 자신의 stack이 있으므로, 다른 쓰레드와 공유하는 자원을 의미한다. e.g. static data, heap, files, I/O(printer, tape)
- Critical Section: Critical Resource를 store, load하는 code들을 일컫는다.
동기화를 위해 critical section에 mutual exclusive(상호배제)가 필요하다. 이는 한 번에 하나의 쓰레드만 section에 접근할 수 있다는 것이다. 상호적으로 배타적이다.
정리하여 프로세스/쓰레드 동기화란, 상호배제를 통해 critical section에 하나의 프로세스/쓰레드만을 접근하게 하여 race condtion을 피하기 위한 기법이다.
Mutual Exclusvie
위의 코드는 Mutual Exclusion의 예시이다. Ra라는 shared resource에 접근할 때, enter와 exit라는 함수 또는 다른 구현을 통해, 다른 쓰레드 또는 프로세스가 접근하지 못하게 하는 것이다. critical section을 지정하는 것이다.
위와 같은 상황은 a==b가 되어야 하는 조건에서, 하나의 line씩 critical section을 지정했을 때이다.
이는 다음과 같이 scheduling이 발생해 오른쪽같은 incorrectness가 발생한다.
Three conditions
동기화 상호배제를 하며 지켜야하는 조건은 다음과 같다.
- Mutual Exclusion: 쓰레드/프로세스는 critical section에 동시에 접근할 수 없다.
- Progress: 쓰레드/프로세스 A가 critical section에 접근하고 있지 않는다면 바로 B는 접근할 수 있어야한다.
- Bounded Waiting: critical section에 들어가고 싶어하는 n개의 쓰레드/프로세스가 있다 했을 때, starvation이 발생하면 안 된다.
두 쓰레드 모두 critical section에 들어올 수 있다.
mutual exclusion x
둘 다 무한루프에 빠질 수 있다.
progress x
Peterson's
위는 양보하는 동기화 기법이다.
상호배제 ok, progress ok turn이 0아니면 1이니.
근데 얘의 문제는 소프트웨어적 문제로 검증이 어렵고, 비효율적이다.
그리고 현대 아키텍쳐에서 돌아가지 않는다. reordering 문제가 발생할 수 있음.(architecture dependent)
아마도 REMAINDER SECTION에 발생할 수 있을 것 같다.
Synchronization
이제부터 동기화 기법을 알아보자. 이전의 예시들은 상호배제의 조건 세 가지를 위해 알아보았다.
Disabling Interrupts
인터럽트를 중단시키는 방법으로 race condtion을 막을 수 있다. time-out 같은 timer 인터럽트를 막아 race condtion을 발생시키는 비자발적 선점을 예방할 수 있다.
위와같이 lock을 수행하고 critical section에 들어가 수행한다. 이후 unlock 함수를 통해 인터럽트를 발생시킬 수 있는 상태로 되돌아간다.
장점은 간단하다는 것이다.
단점을 알아보자.
- 인터럽트는 다양한 디바이스를 효율적으로 관리하기 위해 사용되는데, 이 방법은 굉장히 비효율적이다.
- (질문) 악의적인 유저코드가 이 방법을 남용할 수 있다.
- 멀티 프로세서 환경에서 사용할 수 없다.
이 방법을 중첩해서 사용하면 인터럽트 on/off 제어가 의도대로 되지 않을 수 있다.
이 때, on/off 이전의 값을 저장해두고, critical section 수행 이후 이전값으로 돌아가는 방법을 사용한다.
Speical Machine Instructions
disabling interrupt는 멀티프로세서 환경에서 사용할 수 없으므로, locking을 위한 새로운 하드웨어를 사용할 수 있다.
추가적인 하드웨어는 추가적인 instruction들을 동반하는데, Compare and Swap Instruction(CAS)라는 instruction을 통해 lock/unlock을 하나의 instruction으로 처리하여 atomic한 연산을 critical section에서 수행할 수 있다.
oldvalue에 word에 저장된 값을 옮기고 이게 0인 경우 1로 변경한다.(자신이 사용한다는 것이다.) 그리고 0을 리턴하여 while문을 깨고 critical section에 진입한다.
이미 쓰고있으면 1을 리턴한다.
위의 이미지와 같이 busy wating을 하는 Spin lock을 사용할 수 있다.
이러한 lock들은 선점 모드인 scheduler가 요구된다.
