글 수 117
어떻게 O(1)이 되나 예전부터 찾아봐야지 하다가 방금
찾아봤는데 허무하게도..
하드웨어 명령에 비스무리한걸 지원해주는군요
sched_find_first_bit를 찾아보면
arm은 clz 명령(msb부터 최초의 1이 나올때까지 숫자센다)를 이용하고
x86은 bsfl 이라는 명령을 사용하는 군요
예전에 ucos-ii를 볼때 테이블을 만들어서 찾아내는 뭐 그런걸 생각했는데 하드웨어적으로 명령이 구현이 되어 있군요..
근데 뭐 쪼잔하게 더 깊이 들어가자면 이 하드웨어적인 명령이 O(1)인가?? 라는 의문도 드는군요
ㅋㅋㅋㅋ 뭐 그렇겠죠..^^..
찾아봤는데 허무하게도..
하드웨어 명령에 비스무리한걸 지원해주는군요
sched_find_first_bit를 찾아보면
arm은 clz 명령(msb부터 최초의 1이 나올때까지 숫자센다)를 이용하고
x86은 bsfl 이라는 명령을 사용하는 군요
예전에 ucos-ii를 볼때 테이블을 만들어서 찾아내는 뭐 그런걸 생각했는데 하드웨어적으로 명령이 구현이 되어 있군요..
근데 뭐 쪼잔하게 더 깊이 들어가자면 이 하드웨어적인 명령이 O(1)인가?? 라는 의문도 드는군요
ㅋㅋㅋㅋ 뭐 그렇겠죠..^^..
단순히 첫번째 비트를 찾는 것 하나만을 의미하는 것 같지는 않습니다.
N개의 테스크가 있을 때 이중에 한 개를 선택해 처리를 해야 하는 시점에서 모든 태스크의 우선순위를 계산한다는게 O(n)일테구, 미리 우선순위가 정해져 있기 때문에 첫번째 우선순위의 태스크부터 처리를 하면 되는게 O(1) 스케줄러라고 봤을 때 첫번째 우선순위의 태스크를 선택하는 것만을 O(1) 이라고 보기 보다는
각 태스크의 타임슬라이스가 끝날 때마다 다음 타임슬라이스 값을 계산하고 다 계산된(expired) 우선순위큐와 active 큐의 포인터를 교환하는 동작까지를 O(1)의 핵심이라고 묶어서 봐야 되지 않을까 싶습니다.
그나저나 최근에 커널에 선택되었다는 CFS 스케줄러는 O(1) 스케줄러에 개선의 여지가 남아 있었다는 것으로 봐야되나요? 그룹 스케줄링이 가능하다는 이야기는 들었지만 단순히 토발즈가 그러한 이유때문에 CFS를 선택했다고 이해하기에는 좀 어려운 감이 없잖아 있습니다만.. 잘 만들어 둔 O(1)을 제껴둔 진짜 이유를 아직 잘 모르겠습니다..