[OS(운영체제)] Concurrency: Locks

1. Idea

프로그램이 작동할 때 프로세스나 많은 작업들이 리소스를 사용하는데 여기서 동시에 작동하는 thread에서 공유된 자원을 활용하기에 앞서 여러 문제들이 발생한다. 그래서 이런 문제를 해결하고자 lock이라는 방식을 사용하며 이런 공유 자원들을 여러 thread에서 접근을 한다고 한다면 이를 충돌을 막기 위해 lock이 활용되는 부분을 critical section이라 한다.

 

동일한 리소스를 접근하는 critical section의 예시는 아래와 같다.

 

• 공유 변수 또는 데이터 구조 : 두 개의 스레드가 동시에 동일한 변수를 증가시키는 경우
• 메모리 공유(Shared Memory)
• 파일 시스템: 여러 프로세스가 동시에 동일한 파일에 쓰기를 하는 경우

2. Locks

lock은 데이터에 대한 mutual exclusion의 특성을 만들어주며 acquire(), release() 함수를 통해서 사용된다.

순서

Lock free -> critical section 시작 전에 acquire() -> release() 

 

• acquire()은 lock을 가지고 있으면 호출되지 않는다.
• acquire()을 호출하면 thread는 spin(spinlock) 혹은 block(mutex)가 된다.
• 하나의 thread는 하나의 lock을 가진다.

위에 있는 사진처럼 각자 다른 thread에서 critical section이 실행된다면 thread의 acquire호출이 있고 그 요청이 다른 thread에서 다 종료된 이후에 또 다른 thread에서 요청이 실행된다.

 

3. Requirements for Locks

• Correctness

        - Mutual exclusion : critical section 의 실행은 thread에서 하나만 실행 가능하다. 

        - Progress(deadlock-free) : critical setion이 여러 thread에서 동작을 한다면 하나의 동작만 수행한다.

        - Bounded waiting(starvation-free) : 기다리고있는 thread는 반드시 나중에 critical section에 들어가야 한다.

• Fairness

        - 각각의 thread는 lock을 동일하게 분배받아야 한다.

• Performance

        - Thread에서 처리를 기다리는 추가적인 오버헤드가 생긴다.

 

 

4. Implementation

4.1 Controlling Interrupts

lock이 실행되는 부분에서는 context switch가 불가능하고 interrupt가 가능하지 않다. 이런 구현의 장점은 간단하고 단일 프로세스에서는 사용이 용이하다. 하지만 이런 방식은 커널에서만 가능하고 다중 프로세스 상황에서는 충분하지 않다. 또한 critical section이 길다면 많은 delay시간이 소요된다. 

 

4.2 Multicore 

 

Multicore에서는 이런 acquire에서 spin lock의 초기 모델로서 lock이 끝날 때까지 CPU를 사용하면서 기다리는 방식이다. 하지만 이런 방식은 동시에 acquire함수를 수행하는 thread가 존재한다면 비슷하게 while문을 빠져나와서 원하는 atomic 한 수행을 하기 어려운 문제가 있다. 즉 race condition 한 상황을 야기한다.

 

4.3 Hardware atomic instructions

1) Test-And-Set

Test-And-Set방식은 Spin lock 구조를 가지면서 while문을 통해서 acquire함수를 수행하면 release 할 때까지 기다리를 구조를 기본으로 한다. 하지만 여기서 while의 조건을 이전에 가지고 있던 상태 값을 반환하여 진행된다.

 

위의 코드를 해석을 해보자면 기존 방식에서는 while 문의 waiting 하는 부분과 lock을 할당을 해주는 부분에 따로 실행이 된다. 다른 thread에서 acquire을 실행을 한다고 할 때를 예로 들어 보면 thread A 에서 while문이 끝나고 lock을 하기 위해서 held 을 1로 지정을 하려고 할때 thread B에서 while을 먼저 수행하고 먼저 lock을 하면 race condition문제가 발생한다.

 

왜 TestAndSet은 안전한가?

동일한 변수에 대해 여러 스레드가 동시에 TestAndSet을 호출해도 문제없이 작동하는 이유는 이 연산이 어토믹 하기 때문입니다:

• 스레드 A가 TestAndSet(&l->held, 1)을 호출할 때, 하드웨어가 보장하는 atomic 연산으로 인해 l->held의 상태를 읽고, 값을 1로 설정하며, 그 이전 값을 반환하는 모든 작업이 중단 없이 수행됩니다.
• 만약 스레드 B가 거의 동시에 TestAndSet(&l->held, 1)을 호출하더라도, 하드웨어는 이 두 연산이 절대로 동시에 일어나지 않도록 합니다. 스레드 A가 TestAndSet을 수행하는 동안 스레드 B는 기다려야 합니다.
• 스레드 A가 연산을 완료하면, 스레드 B가 그제야 TestAndSet을 수행할 수 있게 됩니다. 이때 스레드 B가 연산을 시작할 때 l->held는 이미 스레드 A에 의해 설정된 상태일 것입니다.

2) Compare-And-Swap

이 방식은 위에서 이야기했던 TestAndSet방식의 약간의 최적화 버전으로 초기 상태에서만 1 값으로 업데이트를 해주고 한번 lock을 할당했다면 그 이후에는 release 하기 전까지 계속 할당받았던 이전의 값을 반환한다. 

 

3) LL & SC

MIPS, Alpha, PowerPC, ARM, etc. 등등 다양하게 많이 쓰는 방식이다. 

• Load-Locked(LL) : 메모리에서 값을 가지고 오는 부분, 또한 주소를 관찰 상태로 두고 변화를 본다.
• Store-Conditional(SC) : intervening 없이 1을 반환하면 성공 조건인데 이는 다른 thread가 이 주소에 쓰기를 하지 않음을 의미한다.  하지만 그 주소에 쓰기 연산이 일어났다면  다시 LL을 실행한다.

 

 

4) Fetch-And-Add

 

위의 코드를 기준으로 thread A, B가 존재할 때 예시를 말해보겠다.

 

• 스레드 A가 acquire 호출:
  • 스레드 A가 acquire 함수를 호출하여 락을 획득하려고 합니다.
  • FetchAndAdd(&l->ticket, 1)이 실행되어 ticket이 1로 증가하고, A는 myturn = 0을 받습니다.
  • while (l->turn!= myturn);에서 l->turn이 0이므로, A의 myturn과 일치합니다. 따라서 A는 즉시 락을 획득하고, 공유 자원에 접근합니다.
• 스레드 B가 acquire 호출:
  • 스레드 B가 acquire 함수를 호출하여 락을 획득하려고 합니다.
  • FetchAndAdd(&l->ticket, 1)이 실행되어 ticket이 2로 증가하고, B는 myturn = 1을 받습니다.
  • while (l->turn != myturn);에서 l->turn이 0이므로, B의 myturn과 일치하지 않습니다. 따라서 B는 자신의 차례가 될 때까지 대기해야 합니다.

즉 설명에서 처럼 ticket값으로 값을 더해서 각각의 thread의 순서를 지정하고 lock을 지정하고 release 한 이후에 다른 thread에서 접근이 가능하게 코드가 수행된다.

 

 

4.4 Fetch-And-Add 방식에서 yield() 추가

아래의 그림처럼 대기하는 thread의 yield()를 호출하여서 thread의 실행을 중지한다.