[OS] 동기화 문제를 해결해보자! - Locks, Perterson’s Algorithm

Locks

lock은 말 그대로 자물쇠 역할이다. 크리티컬 섹션에는 한 명만 들어가야 하는데, 들어갈 때 lock 하고, 나올 때 unlock 하는 방식으로 동기화 문제를 방지한다.

• acquire() : lock이 풀릴 때 까지 기다렸다가 풀리면 잡는다. 풀려있다면 그냥 잡는다.
  • 대기하다 보면 여러 쓰레드가 대기할 수 있다. 여러 쓰레드들을 다 고려해서 acquire()하는 메커니즘을 고려해야 한다.
• release() : unlock

Lock은 초기에 열려있다. 크리티컬 섹션에 들어갈 때 acquire을 부르고 나올 때 release 한다.

acquire과 release 사이에 쓰레드는 락을 잡고 있어야 한다. 또, 최대 하나의 쓰레드만이 락을 잡고 있어야 한다.

아래의 그림을 잘 이해하자!

 

Lock은 spin할 수 있어서 spinlock이라 불리고, block할 수 있어서 mutex라 불린다.

 

---

Implementing Locks

오른쪽 아래의 코드를 실행하는 두 개의 쓰레드 T1, T2를 생각해 보자.

• T1은 held값을 1로 만들고 코드를 실행한다.
• T2는 held값이 1이라서 0으로 바뀔 때까지 while() 문을 돌면서 대기한다.
• T1이 release를 호출해서 held 값을 0으로 만들면 그때부터 T2가 크리티컬 섹션을 들어갈 수 있다.

Problem

사실 이 코드는 문제가 있다. 코드 자체에도 크리티컬 섹션이 있어서 동기화 문제의 위험성이 있다.

T1, T2가 글로벌 변수 held에 의존하고 있어서 그런 문제가 발생한다.

 

acqurie, release는 Atomic operation하게 설계해야 한다.

• 코드가 여러 줄이 있다면 Context Switching이 일어나지 않고 한 번에 실행을 하던가 아예 실행을 못하게 설계되는 것을 Atomic operation이라 한다.
• Atomic operation은 어셈블리어의 레벨로 생각해야 한다. count+=1;이 어셈블리어로는 세 줄인 것처럼, CPU 한 클락에 코드가 한 번에 다 실행되어야 한다.

Solutions

• 소프트웨어적으로 잘 짜는 방법
• 하드웨어를 설계할 때부터 Atomic operation을 넣어서 그것의 도움을 받는 법.
• 하드웨어적으로 지원하는 인터럽트에 대한 disable/reenable를 사용한다. 인터럽트를 받지 않는다는 말은 타이머 인터럽트를 받지 않는다는 것이고, 그럼 context switching이 일어날 리가 없다.

---

Software-only Algorithms

이런 식으로 acquire, release를 호출하는 쓰레드의 id로 부르는 방법이 있다.

이 알고리즘 역시 문제를 가지고 있다.

빨간색 화살표의 위치에서 contextSwitch가 일어나면 어떻게 될까? T1도, T2도 interested [other] 값이 1이 되어서 무한 루프를 돌게 된다.

progress를 지키지 못한 알고리즘이다.

Perterson’s Algorithm

어디서 context switch가 일어나던 무한 루프를 돌지 않는다. turn이 글로벌 변수여서 context switch와는 무관하게 잘 동작한다는 것이 포인트이다. 잘 이해해 보자. turn 위아래로 context를 넣어서 직접 시뮬레이션해보자.

---

Hardware Atomic Instructions

하드웨어적인 도움을 받는 해결책이다.

Test-and-Set이라는 인스럭션이 있는데 예를 들어 C로 바꾸면 이렇게 동작할 것이다. 당연히 실제로는 하드웨어적으로 동작한다.

위의 인스트럭션이 어셈블리어 레벨에서 Atomic 하게 작동하기에 아래와 같이 사용할 수 있다.

기존에 잘못된 알고리즘에서는 l.value를 확인하고 값을 바꾸는 두 과정을 거쳐서 잘못된 부분이 생겼는데, 하드웨어적으로 도움을 받아서 CPU 한 클락에 TestAndSet Atomic 하게 실행하기에 그사이에 컨텍스트 스위칭이 일어날 수 없다.

 

Swap도 Atomic하게 어셈블리 인스트럭션을 제공한다.

사용하는 예시도 잘 이해해야 한다.

C로 된 모든 예제는 멀티 쓰레드로 시뮬레이션해보면서 잘 기억하자. 하드웨어의 도움을 받으면 알고리즘이 간단해진다.

Problems with Spinlocks

lock을 생각해 보면 사실 Spinlocks이라 불린다.

• 사실 spin은 CPU cycle을 끔찍하게 많이 낭비한다.
• 가장 큰 문제는 acquire에서 while문을 무한히 돈다는 것이다. 그 말은 CPU를 계속 사용한다는 것이다.
• 크리티컬 섹션이 길어지면 대기하는 쓰레드는 그만큼 CPU 사이클을 더 많이 낭비하고 spin이 많아진다.
• lock을 가지고 있는 쓰레드가 갑자기 죽거나, context switch가 lock을 가지고 있지 않은 쓰레드, 혹은 아예 다른 프로세스로 넘어간다면 낭비가 더 심해진다.

따라서 spinlock은 high level의 동기화 구성을 구성할 때만 기본적인 요소로 사용하는 게 좋다.

---

Disable Interrupts

acquire()에서 cli()를 불러서 인터럽트를 무시하기 시작할 수 있다.

그리고 release()에서 sti()를 불러서 이제 인터럽트를 받겠다고 알려줄 수 있다.

 

인터럽트를 무시하면 당연히 타이머 인터럽트도 받지 않게 되고, 당연히 context switch가 일어나지 않는다.

이 방법도 문제를 가지고 있다.

• 인터럽트를 켜고 끄는 건 당연히 커널만 가능하다.
  • 애플리케이션이 임의로 cli()를 부를 수 있으면 그 프로세스가 CPU를 독점하기에 위험하다.
• 멀티프로세서 CPU에서 여러 CPU가 cli()를 호출하면 문제가 생긴다.
• 크리티컬 섹션이 길다면 아무 인터럽트도 받지 못해서 문제가 생길 수 있다.

spinlock와 마찬가지로 high-level 동기화를 구현하기 위한 기본적인 방법으로만 사용하자.