Одиночная очередь имеет временную сложность [ 1 ] из O (1) при поиске, поскольку она может просто отправить следующий процесс в исполнение. Вставка также имеет O (1), поскольку она помещает новый элемент в конец очереди. Этот тип циклического планировщика был использован, например, в раннем ядре Linux. Недостатком было то, что все задачи выполнялись каждый раз в одном порядке.
Чтобы исправить это, простое улучшение состоит в том, чтобы продолжать выдвигать начало очереди с помощью O (1) и искать подходящий интервал в очереди при вставке по приоритету и / или требованиям времени, таким образом имея O (n). Некоторые планировщики поддерживают несколько очередей (или даже очередь с приоритетами), время работы которых варьируется в зависимости от реализации и потребностей.
Красно-черное дерево, с другой стороны, имеет временную сложность O (log n), чтобы получить следующий процесс и при вставке. Принципиальная идея красно-черного дерева заключается в том, что оно сохраняет равновесие при каждой операции, таким образом оставаясь эффективным без каких-либо дополнительных операций оптимизации. Очередь приоритетов также может быть реализована с помощью красно-черного дерева внутри.
Хорошей отправной точкой для планировщиков (Linux) является статья CFS на сайте IBM, на которой также есть хороший набор ссылок.