sleep sort, 슬립 정렬이라고 2년 전이였나? 3년 전에 꽤 핫했던 친구가 있습니다. 사실 왜 Hot했는지는 이해가 가지 않습니다. 아이디어 정도만 보시고 넘어가셔도 무난할 듯 싶어요. 대략적인 구조를 보면, worker 역할을 하는 객체에게 몇 단위시간 동안 sleep 할 건지 그러한 정보를 넘겨주고, 해당 객체가 몇 단위 시간 동안 깨어나면 출력하는 식으로 프로그램을 짜는 듯 싶습니다. 더 쉽게 말하면, 길이가 n인 데이터가 있을 때, worker_i는 arr[i] 단위시간 만큼 잠이 듭니다. t만큼 시간이 지났을 때, t만큼 잠들어야 하는 worker들이 모두 깨어나면서 t를 출력하는 것입니다. 단위 시간이 매우 작다면, 꽤 효율적일 겁니다.

 

 


 코드는 생각보다 짧은데요. 많이 찾아볼 수 있는 코드를 조금 변형하였습니다. 먼저, 11번째 줄에서 fork() 함수를 호출하는데요. 이 함수는 리턴값이 2개입니다. fork를 호출한 프로세스에서는, 자식 프로세스의 pid 값이, 자식은 0이 리턴이 됩니다. 

 

 

 그러면 부모던 자식이던 pc 값은 11번째 줄을 일단 가리킬 건데요. 다음에 12번째 줄을 수행할 때, 자식은 if문에 걸리기 때문에, if에 걸리는 괄호 안으로 들어갈 거에요. 그 괄호 안의 내용을 봅시다.

 

 

 일단, 몇 단위초만큼 sleep을 할 건지 정보를 받습니다. 그리고 1 단위 시간이 0.01초인데요. 대략 argv[i+1]의 값이 "300"이라면, 3초동안 잠듭니다. 그리고 val 값이 출력이 됩니다. 이 단위 시간을 0.01초가 아닌 0.001이나, 0.0001로 줄일 수 있는데요. 그러면 어떤 문제가 발생하는지는 밑에서 계속 서술하도록 하겠습니다.

 

 그리고, return 0; 이 호출되는데요. 프로세스가 종료되는 것입니다.

 

 

 대략적인 실행 흐름은 다음과 같습니다. 여기서 보라색 부분이 자식 프로세스가 실행하는 코드입니다.

 

 

 다음에, 부모 단에서는 while loop가 끝나고, 자식이 종료가 될 때 까지 기다려야 하는데요. waitpid의 경우, 1번째 인자에 pid 값을, 2번째에 status의 주솟값을, 3번째에 WNOHANG이라는 것을 넣었습니다. 이것은 종료된 자식이 없다고 해도, blocking 상태에 빠지지 않고, 특정한 값인 0을 리턴하면서 빠져 나옵니다. 즉, 저는 argc개의 자식 프로세스에 대해서 그것들이 종료될 때 까지, 대기하는 것입니다.

 

 

 즉, 부모는, 자식들이 종료될 때 까지 종료하지 않습니다. 그러면 대충 프로그램이 어떻게 실행되는 지 이해하셨을 겁니다. 각각의 프로세스들을 만듭니다. 그리고, 그 프로세스들이 atoi(argv[i]) 만큼의 단위 시간동안 잠들고 깨어난 후에, 해당 값을 출력한다.

 

 


 이제 이 프로그램을 실행시켜 봅시다. 데이터는 5 1 3 2 11 6 4입니다.

 

 

 이것까지만 보면 제대로 수행이 되는 것처럼 보입니다.

 

 

 그런데, 이 경우는 또 이야기가 달라집니다. 단위 시간이 대략 0.05초인데요. 아래 실행 결과를 봅시다.

 

 

 그러면 6과 5가 정렬이 되어 있지 않습니다. 일단, 프로세스가 여러 개가 띄워져 있어요. 그러면 if(pid == 0)에 걸리는 조건 블록을 수행하려고 여러 프로세스들이 경쟁할 거에요. 이걸 그림으로 그려보면 다음과 같아요.

 

 

 그러면 이런 경우를 생각해 볼 수 있어요. 실제로 pid가 7200인 친구가 9를 가지고 있었고, 7201인 친구가 10을 가지고 있었어요. 그런데 7201인 친구가 끝나고 나서 0.1초 후에, 7200인 친구가 실행되었다고 해 봅시다. 그러면, 10이 출력되고 나서 9가 출력이 될 거에요.

 

 분명한 것은, 실행 순서에 따라, 화면에 뿌려지는 결과가 달라질 수도 있다는 것입니다.

 

 

 다음에 이런 경우도 생각해 봅시다. 2 9 ... 9 1 이런 식으로 데이터가 들어오는 경우에는 어떨지. 9가 5000개 정도 있다고 생각해 봅시다.

 

 

 기본적으로, fork는 프로세스를 하나 생성하기 때문에, 연산이 결코 가볍지 않습니다. 단위 시간이 0.001초로 매우 짧다. 그러면, 5000번 정도 프로세스를 생성하면 단위 시간을 기준으로 보면, 그 시간 또한 무시하지 못할 겁니다. 예를 들어서, 1번 fork를 수행하는데, 평균적으로 0.01단위 만큼 걸린다고 하면, 우리가 보았을 때는 매우 짧을 겁니다. 그런데, 이게 5000번 가량 누적이 되면, 50단위 만큼이 됩니다.

 

 만약에, 2가 들어왔을 때 단위 시간 2만큼 재우고, 1이 들어왔을 때 단위 시간 1만큼 재운다면, 문제가 될 소지가 있을 겁니다. 그러니까, 아. 이런 아이디어도 있군. 정도만 보시는 게 좋아 보입니다.