Думаю многие слышали, что помимо стандартного O(1) планировщика в linux, появился CFS(Completely Fair Scheduler; «абсолютно справедливый планировщик»), над которым работает Ingo Molnar. Собственно эту заметку я хотел бы посвятить сравнению этих двух планировщиков и краткому рассмотрению их основных алгоритмов. В конце заметки можно немного почитать по FreeBSD'шный планировщие ULE.
preamble:
preamble:
- O(1) scheduler — вкратце, политика планировщика была довольно проста: каждый cpu имел 2 очереди: в одной находятся таски, которые в скором времени будут запущены, в другом — спящие таски. когда первая очередь оказывалась пуста, она менялась местами со второй, соответсвенно во второй очереди все спящие процессы 'просыпались', а в первая служила очередью для отработавших и уснувших процессов. посему время работы алгоритма во-первых, не зависит от кл-ва процессов, во-вторых, оно постоянно — O(1).
- Completely Fair Scheduler — для хранения процессов использует red-black дерево, где ключём является wait_runtime каждого процесса. wait_runtime — это кл-во наносекунд, которое данный процесс недоработал или переработал. т.е. если оно < 0, значит он переработал, если оно > 0, значит он недоработал. эта мера позволяет засечь out-of-ballance от 'идеального случая'. в зависимости от значения wait_runtime, процесс занимает своё место в дереве. если wait_runtime < 0, то, я полагаю, процесс будет сидеть на нижних уровнях, если больше 0, то ближе к вершине. следовательно, CFS — не O(1) scheduler, он O(logN).
