운영체제를 공부하기 위해 운영체제 아주 쉬운 세 가지 이야기 라는 책을 읽고 공부한 내용을 정리합니다.
잘못되거나 부족한 부분이 있으면 언제든 댓글로 가르침 부탁드립니다.
락은 병행성 문제를 해결하는데 필요한 하나의 변수이다. 락이라는 변수를 A 스레드가 소유하고 있다면 A 스레드 만이 공유 메모리 영역에 접근할 수 있고 나머지 스레드들은 접근할 수 없음을 의미한다.
초창기 단일 프로세스 시스템에서는 인터럽트를 활용하여 락 기능을 구현했다. 기능은 간단하다. 한 스레드가 임계영역에 들어가면 인터럽트를 막는다. (즉 다른 스레드가 인터럽트를 발생시킬 수 없다.) 스레드가 임계영역에서 나오면 다시 인터럽트를 사용가능하게 한다. 이 방법은 단점이 많다.
인터럽트를 활용한 락은 단점이 많기 때문에 하드웨어를 활용하여 락을 구현할 수 있다. 그 중 Test-And-Set이라는 원자성을 가진 하드웨어 명령어를 이용하여 락을 구현할 수 있다. 락 소유가 가능할 때까지 루프를 돌며 대기하기 때문에 스핀 락 이라고 부른다.
do {
while(TestAndSet(lock_flag, 1) == 1)
; // spin
// critical section
lock_flag = 0;
} while(true);누군가 lock을 소유하고 있다면, 다른 스레드는 while(TestAndSet(&lock)) 을 빠져나올 수 없으며 그 곳에서 lock의 free를 기다린다. lock을 소유한 스레드가 임계 구역 지나면면 lock에 0을 넣게 되고, 이후 가장 먼저 TestAndSet을 실행하는 명령어가 lock을 얻게 된다.
정확성 측면에서는 잘 작동하지만, 공정성이나 성능 측면에서 좋지 않다.
Compare-And-Swap의 기본 개념은 ptr가 가리키는 주소의 값과 기대값이 일치하는지 검사하는 것이다. 현재 값과 기대하는 값을 비교해(Compare) 같으면 새로운 값으로 변경하고, 다르면 아무것도 하지 않는 방법이다. Test-And-Set과 비슷하게 스핀 락을 구현할 수 있다.
do {
while(CompareAndSwap(lock_flag, 0, 1) == 1)
; // spin
// critical section
lock_flag = 0;
} while(true);flag 변수가 0인지 검사하고(lock 소유자가 없음), 1로 바꿔주면서 lock을 소유한다. flag 변수가 0과 일치하지 않으면 계속 스핀하며 대기한다. Test-And-Set은 매번 lock에 1을 넣지만 CompareAndSwap은 비교해서 다를 때만 넣기 떄문에 조금 더 효율적이다.
Load-Linked를 통해 현재 lock이 free인지 확인한다.(free가 아니라면 spin 한다.) 그리고 store-conditional 을 통해 lock 소유한다. 이때 핵심은 lock의 free 여부를 확인한 이후 lock을 소유하는 사이에 인터럽트가 발생하여 다른 스레드가 lock을 소유하는 경우가 발생한다는 점이다. 그럼 다음 기회를 기다려야 한다.
do {
while(LoadLinked(lock_flag) == 1 || !StoredConditional(lock_flag, 1))
; // spin
// critical section
lock_flag = 0;
} while(true);티켓 락이란 여러 스레드에 티켓을 주고, 락이 free 되었을 때, 차례와 티켓이 동일하면 락을 소유하는 방법이다. 이 방법과 다른 방법들과의 가장 큰 차이점은 모든 스레드들이 순서대로 진행하게 된다는 점이다.
do {
int myTurn = FetchAndAdd(lock_ticket); //티켓을 준다.
while(lock_turn != myTurn)
; // spin
// critical section
FetchAndAdd(lock_turn); // 차례를 넘긴다.
}while(true);위 락 기법들은 모두 루프를 통해 스핀하며 락을 기다린다. 또한 일부는 starving이 발생하기도 한다. 이는 매우 비효율적인 기법이다. 따라서 운영체제의 도움을 받아 비효율성을 해결할 수 있는 락 기법이 필요하다.
먼저, 스레드를 잠재울 수 있는 park 함수와, 스레드를 깨울 수 있는 unpark(threadId) 함수와, 다음 락 획득 대상을 제어하는 Queue를 이용하여 락을 구현할 수 있다. 이 때 문제점이 하나 있다. 다음 차례에 락을 소유할 예정인 한 스레드가 park() 함수 수행 직전에, 락을 소유한 스레드가 락을 해제한다면, 아무도 락을 소유하지 못하는 상황이 발생한다. 이를 Solaris는 setpark()를 이용해 해결한다. park() 발생 직전 인터럽트 발생 및 다른 스레드에서 unpark()이 발생한 경우 park()를 수행하고자 하는 스레드는 잠을 자는 대신 바로 리턴이 된다.
락이 곧 해제될 것을 기다리며 스핀하다가 락이 해제되지 않으면 슬립한다. 그 뒤 락이 풀리면 깨어나는 하이브리드 기법이다.