Threads

여기서는 몇 가지 기억에 남는 것들만 정리함.

먼저 대기하는 스레드가 조건을 검사할 때 if문 대신 while문을 사용하는데 이게 일반적으로 간단하고 안전하다.  예를 들어 pthread 라이브러리에서 변수를 제대로 갱신하지 않고 대기하던 스레드를 깨울 수 있다. 이런 경우 재검사를 하지 않는다면 대기하던 스레드는 조건이 변경되지 않더라도 변경되었다고 생각함. 때문에 컨디션 변수에서 시그널 도착은 변경 사실을 알리는 것이 아니라, 변경된 것 같으니 검사해 보라는 힌트 정도로 보는 것이 더 안전하다. 또한 컨디션 변수 사용하지 않고 간단하게 플래그 형식으로만 구현하면 굉장히 위험하다. 코드의 성능이 일단 좋지 않고, 오류 발생하기가 쉽다.

lock

여러개의 명령어들을 원자적으로 실행해보고 싶지만 단일 프로세서의 인터럽트로 인해서 그렇게 할 수가 없었다. 따라서 락을 사용해서 이 문제를 직접 다룸 . 그렇다면 락은 어떻게 만들까 효율적인 락은 무엇이고, 낮은 비용으로 상호 배제 기법을 제공하고 . 어떤 하드웨어 자원과 운영체제의 지원이 필요할까. 락이 효율적으로 동작하고 있다고 평가할 수 있는 지표는 상호 배제를 제대로 지원하는가와 공정성 그리고 성능이다.  공정성은 락 획득에 대한 공정한 기회가 주어지는가에 대한 답을 할 수 있어야하고, 성능은 락 사용의 시간적 오버헤드를 평가한다. 고려해야할 몇가지 사항이 있는데, 하나는 경쟁이 전혀 없는 경우의 성능이다. 하나의 쓰레드가 실행 중에 락을 획득하고 해제하는 과정에서 발생하는 부하는 얼마나 되는가? 다음은 여러 쓰레드가 단일 CPU상에서 락을 획득하려고 경쟁할때의 성능이다. 마지막은 멀티 CPU 상황에서 락 경쟁 시의 성능이다. 초기의 단일 프로세스 시스템에서는 단순히 상호 배제를 인터럽트를 비활성화 하는 방식으로 했다. 장점은 단순하다는 것이다. 반면에 단점이 많은데, 인터럽트를 실행하려면 특권연산을 실행 할 수 있도록 허가를 해야하고, 운영체제가 전적으로 프로그램을 믿어야한다. 또 다른 단점은 멀티 프로세서에서는 적용할 수가 없다. 여러 쓰레드가 여러 CPU에서 실행 중이라면 각 쓰레드가 동일한 임계 영역을 진입하려고 시도할 수 있다. 이때에 특정 프로세서에서의 인터럽트 비활성화는 다른 프로세서에서 실행 중인 프로그램에는 전혀 영향을 주지 못해서 임계영역에 다른 프로세서가 진입할 수 있게 된다. 세번째 단점으로는 장시간 동안 인터럽트를 중지시키는 것은 중요한 인터럽트의 시점을 놓칠 수가 있다는 것이다.예를 들면 CPU가 저장 장치에서 읽기 요청을 마친 사실을 모르고 지나갔을때 운영체제가 이 읽기 결과를 기다리는 프로세스를 언제 깨울지 알 수가 없다. 마지막 단점은 비효율적이라는 것이다. 인터럽트를 비활성화 시키는 코드들은 최신 CPU에서 느리게 실행되는 경향이 있다.

Test-And-Set (Atomic Exchange)

멀티프로세서에서는 인터럽트를 중지시키는 것이 의미가 없기 때문에 시스템 설계자들은 락 지원을 위한 하드웨어를 설계함. 하드웨어 기법 중 가장 기본은 Test-And-Set 명령어 또는 원자적 교체라고 불린다. 일단 기존 간단한 플래그로 만든 락을 보자

위의 코드에는 정확성과 성능면에서 둘다 문제가 있는데, 정확성 부분에서는  처음 flag가 0일때 인터럽트가 발생하면 두 쓰레드 모두 플래그를 1로 설정하는 문제가 생길 수 있다. 성능 문제에서는 spin-wait라는 방법에 의해 플래그 값을 무한히 검사하는데, 이방법은 다른 쓰레드가 락을 해제할 때까지 시간을 낭비한다.  이 방법은 단일 프로세서에서 특히 손해가 크다. 왜냐면 락을 소유한 쓰레드 조차 실행할 수 없기 때문(context-switch가 있기 전까지).  이래서 우리가 위에서 말한 Test-And-Set이 나온다. 밑의 코드를 보자.

 ptr이 가리키고 있던 예전의 값을 반환하고 동시에 new에 새로운 값을 저장한다. 핵심은 이 동작들이 원자적으로 수행된다는 것이다. 이게 어셈블리 명령어로 구현되어 있다. 구체적인 동작은 위에 플래그로 설정하는 lock과 같지만 잘 돌아간다. 가장 기초적인 형태의 락으로서 , cpu사이클을 소모하면서 락을 획득할 때까지 돈다. 이 방식을 제대로 사용하려면 선점형 스케줄러를 사용해야함. 인터럽트가 발생해야 다른 쓰레드가 cpu를 점유할 수 있기 때문이다. 다음은 이제 평가를 해보자 정확성은 괜찮다. 문제는 공정성인데, 대기 중인 쓰레드들에 있어서 스핀 락은 얼마나 공정한가,  공정성을 보장 할 수가 없다. 마지막은 성능 항목인데, 오버헤드가 상당하다. 단일 프로세서에서 락을 가지지 못한 쓰레드들을 하나씩 깨울때 CPU사이클을 낭비하면서 계속 대기함. 반면에 CPU가 여러개인 경우 스핀락은 나름 합리적이다. 다른 하드웨어 기법으로는 Compare-And-Swap이 있다.  기본 개념은 ptr이 가리키고 있는 주소의 값이 expected 변수와 일치하는지 검사해서 같다면 ptr이 가리키는 주소의 값을 새로운 값으로 변경하고, 다르면 아무것도 하지 않는다.  나머지는 Test-And-Set과 비슷하다.  어떤 플랫폼은 임계 영역 진입 제어 함수를 제작하기 위한 명령어 쌍을 제공한다. load-linked 와 store-conditional 명령어를 앞뒤로 사용하여 락이나 기타 병행 연산을 위한 자료 구조를 만들 수 있다. load-linked는 일반 로드 명령어와 같고, store-conditional은 동일한 주소에 다른 스토어가 없었던 경우에만 저장을 성공 한다. lock 부분의 코드를 한번 보자 한 쓰레드가 loadlinked에서 0이 나와서 store-conditional명령어를 실행하려다가 인터럽트가 걸려 다른 쓰레드가 다시 loadlinked에서 flag가 0이 뜨고 둘다 storecond를 부르려는데, 하나의 쓰레드만이 flag 값을 1로 설정한 후에 락을 획득할 수 있도록한다. 그래서 두번째는 기다려야함

Fetch-And-Add 

마지막 하드웨어 기법으로 원자적으로 특정 주소의 예전 값을 반환 하면서 값을 증가 시킨다. 이 명령어를 사용하여 티켓락 예시를 보자 

이 방식과 이전 까지의 방법이 다른점은 모든 쓰레드들이 각자의 순서에 따라 진행한다는 것이다.

과도한 스핀

지금까지 소개한 하드웨어 기반의 락은 간단하지만, 문제가 있는데 락을 가지지 못한 쓰레드는 지속적으로 스핀하면서 CPU 자원을 낭비하게 된다. 따라서 이제는 운영체제로부터 지원을 받는 방식을 알아보자. 

처음 방식은 무조건 양보하는 방법이다. 만약 락이 없다면 yield함수를 통해 바로 양보해버린다. 이 방식을 사용하려면 쓰레드의 상태들에 대해 정의해야한다. running, blocked, ready 상태들이 있다. 양보라는 시스템콜은 running 중에서 ready상태로 바꾼다. 동작을 잘하는 것 같지만 이것 역시 문제가 생기는게 라운드 로빈 스케줄러를 사용한다고 했을때, 상당한 context-switch 비용이 발생한다. 더 안 좋은 것은 starvation문제는 해결 하지 못한다. 그래서 나온 해결책이 큐를 사용하는 것이다. 이전 방법들은 너무 많은 부분을 운에 맡기는 점이다. 여기서는 특정 쓰레드를 깨울지 명시를 해주는 것이다. solaris 방식을 사용해서 예시를 보자

여기서는 앞에서 배운 Test-And-Set개념을 락 대기자 전용 큐와 함께 사용하여 좀 더 효율적인 락을 만든다, 또한 큐를 사용하여 다음으로 락을 획득할 대상을 제어하여 기아 현상을 피할 수 있도록 해본다.  guard변수를 사용하여 flag와 큐의 삽입과 삭제 동작을 스핀락으로 보호하는데 사용한다. 여기서의 스핀은 단지 락과 언락의 몇개의 명령어만 수행하면 되기 때문에 굉장히 짧다. 여기서 문제는 park() 직전에 경쟁 조건이 발생한다는 것이다. 한 쓰레드는 락이 사용 중이라 park()문을 수행하려 한다. 그 직전에 락 소유자 한테 cpu가 할당된다면 문제가 발생할 수 있다. 예를 들어 락을 보유한 쓰레드가 그 락을 해체했다고 해보자. 쓰레드가 자기 차례에 park()를 수행하면 깨어날 방법이 없다.(잠들기 전 락을 풀어버리고 잠드니 풀어줄 쓰레드가 없음). 다른 무언가가 더 필요하다. 그래서 setpark()라는 시스템 콜을 추가 park가 실제로 호출되기 전에 다른 쓰레드가 unpark를 호출해 버리면 추후 park 문은 잠자는 대신 바로 리턴한다.

lock usage

자료 구조에 락을 추가하여 쓰레드가 사용할 수 있도록 만들면 그 구조는 쓰레드 사용에 안전 하다고 할 수 있다.  여기서는 자료구조를 일단 병행이 가능하게 만들고 확정성까지 높이는 방식으로 알아 본다. 병행성이 있는 카운터는 변수에 접근할때 락을 거는 방식으로 간단하게 구현 가능하다. 하지만 확장성은 좀 더 살펴봐야하는데, 이상적으로는 하나의 쓰레드가 하나의 CPU에서 작업을 끝내는 것처럼 멀티프로세서에서 실행되는 쓰레드들도 빠르게 작업을 처리하고 싶을 것이다. 이와 같이 동작하는 것을 완벽한 확장성이 있다. 더 많은 작업을 처리하더라도 각 작업이 병렬적으로 처리되어 완료시간이 늘어나지 않는다는 것이다. 카운팅에서도 이런 연구가 있었는데 그 기법중 하나가 엉성한 카운터이다. 4개의 CPU가 있고 각 cpu는 저마다의 지역 카운터를 갖고 전체 시스템에서 하나의 전역 카운터가 있다. 최신 값으로 갱신하기 위해서 지역 카운터의 값은 주기적으로 전역 카운터로 전달됨.  지역에서 전역으로 값을 전달하는 빈도는 S값에 의해 결정된다.  S의 값이 작을수록 확장성이 없는 카운터 처럼 동작하며, 커질 수록 전역 카운터의 값은 실제 값과 차이가 있다. 정확한 카운터 값을 얻기 위해 모든 지역락과 전역 락을 획득한 후 계산을 하면 되지만, 확장성이 없게 된다.  표를 보면 S 값이 낮다면 성능이 낮은 대신에 카운터의 값이 매우 정확하고, S의 값이 크면 성능은 탁월하지만 전역 카운터 값이 cpu개수와 S의 곱만큼 뒤처진다. (그니까 너무 전역 카운터에 전달하면 값이 달라질 수가 있고, 그 빈도 수가 적으면 늦지만 안정적일 것이다)

엉성한 카운터의 확장성

나머지 자료구조에서는 연결 리스트, 큐 ,해쉬 등이 있는데 각각 락을 전체적으로 놓을지 아니면 노드마다 놓을지 또는 헤드와 테일 각각 놓을지 등등 여러 방식으로 확장성을 증가 할 수 있다. 락을 많이 걸 수록 오버헤드가 증가해서 마냥 좋은게 아니다 그냥 하나 거는게 효율적으로 좋을 수도 있다. 

마지막으로 중요한 이야기 , 그리고 non-blocking 자료구조에 대해서도 알아보자