The big kernel lock strikes again May 26, 2008

http://lwn.net/Articles/281938/

Yanmin Zhang은 최근 2.6.26-rc1 커널부터 system performance가 약 40%가량 더 나뻐졌다고 보고했다. 그가 한 테스트는 AIM을 이용한 것이며 AIM은 많은 task들을 생성하여 각 task들이 커널의 여러 subsystem에 관련된 작업을 하는 benchmark 툴이다.

그가 찾은 문제는 generic semaphore였다. 문제를 BKL로 촛점을 맞추는 데는 그리 오랜 시간이 걸리지 않았다. BKL은 몇년전 semaphore로 교체되었었다.

Ingo Molnar은 새로운 semaphore코드로 구현을 교체하여 해결하는 방식을 제안하였다.
문제는 기존의 semaphore 구현이 너무 공평하다는 것이다. 하지만 이 공평함은 상당히 비싸다. semaphore를 얻은 쓰레드는 다른 프로세서의 run queue에 있을 수 있으며 게다가 그 쓰레드는 오랫동안 실행권을 얻지 못하여 상당히 cache cold할 것이다. 심지어 그 쓰레드는 굉장히 낮은 priority를 가지고 있어 오랫동안 실행되지 못할 수도 있다. 그 동안 그 semaphore를 기다리고 있는 큐에 저 뒤쪽에 있는 쓰레드들 (즉, 공평성의 관점에서 봤을 때 요청의 시간이 늦어 q->list의 저 뒤족에 매달려 있는 놈들) 또한 실행권을 얻지 못하는 문제가 발생한다.

결과적으로 semaphore의 어떤 쓰레드도 실행하지 못하는 dead time이 상당히 늘어난 다는 것이다.

해결은 기존의 semaphore구현을 빌려오는 것이다. 즉 공평하지 않게 처리하는 것이다.
경쟁을 하여 누가 가져갈지 모른다는 것이다.

흥미로운 것은 이 패치가 2.6.26-rc2 이전에 mainline에 merge되었다가 다시 revert되었다는 것인데 그 이유는 그 패치가 몇몇 사황에서 semaphore를 broken시켰다는 것이다. 즉 semaphore가 몇몇 상황에서 쓰레드를 깨우는 데 실패하는 경우가 있었던 것이다.


Linus는 또 다른 패치를 넣어 이 문제를 해결하였다. BKL을 spinlock을 대체하는 패치였다. 대신에 느려터지지만 공평한 generic semaphore는 그대로 남겨두었다. 하지만 이 패치는 non-preemption구간을 증가시켜 rt guy들에게는 결코 환영받지 못하였다.

하지만 Linus가 이렇게 패치를 한 이유는 BKL이나 semaphore는 제거되거나 minimization되어야 하는 상당히 낡은 메커니즘이라는 것이다. 그러한 관점에서 더 복잡했던 semaphore 코드를 다시 되돌리자고 하는 노력은 가치가 없다고 판단하였다.

그래서 이러한 결론은 다시 BKL을 커널에서 제거하고자 하는 사람들에 또다시 격려가 될지도 모른다.