2024. 4. 29. 10:31ㆍCS/Operating System
spinlock의 문제점
[OS] 동기화 문제를 해결해보자! - Locks, Perterson’s Algorithm
Locks lock은 말 그대로 자물쇠 역할이다. 크리티컬 섹션에는 한 명만 들어가야 하는데, 들어갈 때 lock 하고, 나올 때 unlock 하는 방식으로 동기화 문제를 방지한다. acquire() : lock이 풀릴 때 까지 기다
jun-n.tistory.com
위의 글에서 동기화 문제 해결 방법으로 Locks을 공부했다. 그런데 사실 위에서 배운 Lock은 해결법 중 하나인 spinlock이다. spinlock 외에도 많은 Locks가 있는데, spinlock에 어떤 문제가 있어서 새로운 Lock이 등장하게 되었을까?
- spinlock은 CPU를 너무 낭비한다. (wasteful)
- spinlock을 이용해서 좀 더 좋은 lock을 만들 필요성이 느껴진다.
- spinlock의 가장 큰 문제는 spin이다. 즉, Block waiters이다.
그래서 Semaphores, Monitors의 두 가지 방법이 나왔다.
Semaphores
- 다익스트라가 OS THE를 개발하면서 만들었다.
- Semaphores의 큰 특징은 busy wating을 요구하지 않는다는 것이다.
- 주로 두 개의 연산을 지원한다.
- Wait(S) : 내부의 count 값을 감소시킨다. 즉, 세마포어가 열릴 때 까지 block한다. P나 down 함수라고도 불린다.
- Signal(S) : count 값을 증가시켜 다른 쓰레드가 들어올 수 있는 기회를 제공한다. V나 up 함수라고도 불린다.
Semaphores의 block
- 쓰레드가 크리티컬 섹션에 들어갈 수 없다면 기다리지 않고 block한다. 이 부분이 spinlock과 가장 큰 차이이다.
- 프로세스나 쓰레드를 위해 큐를 가지고 있고, 큐를 이용해서 block한다.
- wait()
- count값을 감소시킨다. 락이 열려있다면 그냥 들어가고, 닫혀있다면 block시킨다.
- block 당한 쓰레드는 CPU를 사용하지 않고 큐에서 대기한다. CPU 스케줄러의 wait queue가 있는 느낌이다. 이 과정은 OS가 당연히 필요하다.
- signal()
- 세마포어를 연다(counter값을 증가시킨다).
- 큐에 기다리고있는 쓰레드가 있다면 쓰레드를 unblocked 시킨다.
- 세마포어는 history를 가지고 있다고도 한다.
- history는 counter이다.
- counter 값으로 세마포어를 열고 닫는다. counter가 0보다 작아지면 닫힌 것이다.
Implementing Semaphores
typedef struct{
int value; // 1 or N
struct process *L;
} semaphore;
void wait(semaphore S){
S.value--
if (S.value < 0){
add this process to S.L;
block();
}
}
void signal(semaphore S){
S.value++
if(S.value <= 0){
remove a process P from S.L;
wakeup(P);
}
}위의 코드를 잘 이해해야 한다!
spinlock과 유사하지만 if문을 사용하여 무한 루프를 돌며 대기하지 않고, 큐에 추가하여 block한는 차이가 있다.
주의할 점은 wait, signal 모두 크리티컬 섹션이다. 따라서 이 코드들이 atomic한 코드로 처리되어야 한다.
시스템 콜과 인터럽트 무시/받기 혹은 하드웨어 instruction으로 가능하다!
semaphore의 종류
Binary semaphore
- mutex라고도 불린다.
- spinlock과 마찬가지로 크리티컬 섹션에 하나만 들어가야 한다. 따라서 mutually exclusive한 것이 보장된다.
- count 값을 1로 두면 mutex가 된다.
Counting semaphore
- 크리티컬 섹션에 여러 개가 들어갈 수 있다.
- 쓰레드나 프로세스가 가능한 많이 들어가는 것을 허용한다.
- count 값을 N으로 두면 Counting semaphore가 되고, count 값만큼 쓰레드에 들어갈 수 있다.
Lock을 사용할 때 주의해야할 포인트
Deadlock
데드락은 여러 프로세스들이 서로를 기다리다가 락이 풀리지 않고 죽어버리는 상황을 말한다.
프로세스가 S, Q의 락을 잡아야 한다고 생각해보자.
그런데 중간에 컨텍스트 스위치가 일어나면 P1은 S를 잡을 수 없다. 그리고 P0는 Q를 잡을 수 없다.
만약 P1이 Q가 아닌 S를 먼저
잡으면 문제가 생기지 않는다.
- 데드락은 일단 일어나면, 해결 방법은 없고 코드를 잘 짜서 데드락이 생기지 않도록 설계해야 한다.
Starvation
- 데드락 등의 이유로 프로세스가 더 이상 진행이 되지 않아서 굶어 죽는 상황이다.
Priority Inversion
- CPU 스케줄링의 문제이다. 스케줄링의 우선순위가 낮은 프로세스가 lock을 잡고 있어서 우선순위가 높은 프로세스가 실행이 되지 못해서 생기는 문제이다.
만약 우리가 새로운 lock 메커니즘을 만든다고 생각해보자. 우리는 앞에서 배운 데드락, Starvation, 우선순위 역전 문제를 신경쓰면서 메커니즘을 짜야하고 이는 상당히 번거로운 일이다.
그런 상황들을 위해 아래의 문제들이 고안되었다. 아래의 문제들을 새로운 lock 메커니즘으로 풀 수 있으면 괜찮은 메커니즘이다. 테스트 용으로 사용하는 문제인 셈이다. 그러한 문제들로 mutex 세마포어를 사용하면 문제가 없을지 생각해보자.
Bounded Buffer Problem
Producer/consumer problem
- 리소스 버퍼가 있고, 이 버퍼는 producer와 cunsumer가 공유한다.
- producer는 버퍼에 리소스를 넣고, consumer는 버퍼에서 자원을 제거한다.
- 문제는 producer와 consumer가 다른 속도로 실행된다는 것이다. 상황에 따라 누가 더 빠른지 결정된다.
count 만큼 데이터가 들어있고, 최대 N개의 데이터가 들어갈 수 있다. in, out에서 삽입/삭제가 일어난다.
이 코드를 보면 당연하게도 버퍼를 공유하므로 문제가 된다. in과 out은 공유되고 있지 않아서 상관 없다. count는 공유되어서 또 문제가 된다. 특히 count++, count--는 어셈블리어로 세 줄이므로 문제가 된다.
critical section을 정해보자. while(count==N); ~ count++ 까지가 critical section이 된다.
크리티컬 섹션 전체를 lock으로 걸어주면 잘 보호된다.
하지만 병렬성이 떨어진다는 문제가 생긴다.
- 만약 producer 쓰레드가 네 개고, consumer 쓰레드가 한 개라면, producer는 사실 네 개가 다같이 들어가도 된다.
- 그런데 전체 lock을 걸면 병렬성이 매우 떨어진다.
병렬성을 올려주려면 counting 세마포어를 사용하면 되는데 쉽지는 않다.
Dining philosopher
- 철학자의 일생은 생각하고, 배가 고파져서 두개의 젓가락을 들고, 밥먹고 다시 생각하기를 반복한다고 한다.
- 이런 상황에서 아래 그림과 같이 철학자들이 앉아있다면 어떤 방식으로 젓가락을 들어야 할까?
- 모든 철학자가 동시에 식사를 시작하려 할 때 Deadlock이 발생하면 안된다.
- Starvation을 방지하여 모든 철학자가 식사를 완료할 수 있어야 한다.
- 간단하게 mutex 세마포어를 사용해서 해결해보자면 위의 코드가 될 것이다.
- 그런데 이 코드대로라면 데드락의 위험성이 존재한다.
- 모든 철학자가 왼쪽 젓가락을 들어올렸다고 생각해보자. 그럼 E는 0번을 들 수 없고, A는 1번을 들 수 없다. 데드락이 발생하는 것이다.
Problems with Semaphores
- shared되는 글로벌 변수를 사용한다. 글로벌 변수이므로 코드의 어느 부분에서든 접근이 가능하다.
- 글로벌 변수는 사실 안좋은 엔지니어링이다.
- 세마포어는 뮤텍스와 coordination(scheduling) 둘 다에서 사용된다.
- 사실 세마포어는 동기화 문제를 위해서만 고안된 것은 아니고, count를 사용하여 특정 리소스를 요구하는 프로세스를 block하는 알고리즘 그 자체이다.
- signal, wait의 순서가 중요하고 누락이 있어서는 안된다.
- Deadlock과 starvation의 위험이 있다.
- Semaphores는 사용하기도, 버그를 잡아내기도 매우 힘들다.
- 그렇다면 프로그래밍 언어 차원에서 지원을 해주면 어떨까?
Monitors
- 프로그래밍 언어가 구성하는 것이다.
- 동기화 코드가 런타임에 컴파일러에 의해 추가된다. 크리티컬 섹션에 알아서 코드를 삽입해주는 방식이다.
- 모니터는 아래의 사항을 가지는 소프트웨어 모듈이다.
- 모니터는 shared 데이터 구조를 가진다.
- 공유된 데이터를 연산하는 과정도 가지고 있다.
- 이렇게 쓰게되면 글로벌 변수에 접근하는 것에 대한 프로텍션이 가능하다.
- 자바에서는 동기화 문제의 위험성이 있는 함수에 synchronized 를 붙여서 lock을 구현할 수 있다.spinlock 방법은 문제가 많다.