SIMT 교착상태(deadlock), 기아(starvation)

 SIMT에서의 교착상태(dead lock)란 무엇인가?

 SIMT에서 교착상태를 알기 위해서는 교착상태를 일으키는 상호배재(mutex)에 대해 알아야 합니다.

 상호배제(mutex) 

•  OS에서의 상호배제 :  

두 개 이상의 프로세스가 동시에 한 자원에 접근 시 한 개의 프로세스만이 자원에 접근할 수 있게 합니다.

즉, A와 B 프로세스가 동시에 같은 자원에 접근했을 경우 A가 상호배제에 의해 접근이 허락된다면, B는 A가 모두 사용한 후에 해당 자원에 대한 허가가 떨어져 접근을 할 수 있게 됩니다.

•  SIMT에서의 상호배제 : 

두 개 이상의 thread가 동시에 한 자원에 접근 시 한 개의 thread만이 자원에 접근할 수 있게 됩니다.

역시 OS에서의 process와 마찬가지로 A와 B라는 thread가 동시에 같은 자원에 접근을 시도하였으며, A가 허가가 나서 자원에 접근을 했습니다. 이에 따라 B는 A가 해당 자원의 사용을 마칠때까지 대기를 하게 됩니다.

여기서 대기하는 상황을 교착상태(dead lock)라고 합니다.

 쉽게 코드로 설명 드려보겠습니다.

//deadlock이라는 변수가 존재

*deadlock = 0      

             

//atomicCAS라는 함수는 첫 번째 인자와 두 번째 인자가 같다면, 첫 번째 인자를 세 번째 인자로 교체     

while(!atomicCAS(deadlock, 0, 1));       

 만약 A와 B라는 thread가 deadlock에 동시에 접근해 atomicCAS를 수행해야 한다면?

A가 먼저 접근했다고 가정한다면, A는 atomicCAS에 의해 deadlock을 1로 교체합니다.

따라서 B가 접근을 했을 때는 deadlock은 이미 1로 바뀌어 무한루프에서 빠져나오지 못하게 됩니다.

이를 방지하기 위해 다시 deadlock을 0으로 바꾸어주는 작업을 필요로 하게 됩니다.

//첫 번째 인자를 두 번째 인자로 교체

atomicExch(deadlock, 0);

•  교착상태가 발생하면 나타나는 현상

위의 상황처럼 교착상태를 해결하려면 과정이 복잡해지는 문제가 있지만, 더 큰 문제가 존재합니다.

SIMT구조에서는 수천개의 thread가 실행됩니다. 

만약 이러한 상황에서 모든 thread가 같은 자원에 접근하게 된다면 어떻게 될까요?

한 thread가 동작을 하는 동안 다른 많은 thread들이 대기를 하게 되겠죠...

엄청난 성능 저하가 뒤따르게 됩니다.

•  기아(starvation)이 발생하게 됩니다

 기아란 OS에서는 프로세스가, SIMT에서는 thread가 수행이 가능한 상황임에도 불구하고 매우 오랜 기간 대기하는 현상을 의미합니다.

만약 A, B, C라는 thread가 R이라는 자원에 동시에 접근을 한 경우, thread의 접근 우선순위가 A > B > C라고 하겠습니다.

우선순위때문에 A가 먼저 접근을 했으므로 B와 C는 대기상태를 유지합니다.

이 후 A가 R의 사용을 마치고 B가 R을 사용하게 되어 C는 대기상태를 유지합니다.

만약 이 상황에서 A가 다시 R에 대해 접근을 시도한다면?

B가 R의 사용을 종료함과 동시에 다시 A가 R에 접근을 하게 됩니다.

따라서 C는 수행이 가능한 상황임에도 불구하고 대기만 하는 상황이 생깁니다.

이 역시 thread가 동작하지 못하므로 성능저하를 야기시킵니다.