Многозадачные (multitasking) операционные системы бывают двух видов: системы с кооперативной (cooperative) многозадачностью и системы с вытесняющей (preemptive, преемптивной) многозадачностью. Операционная система Linux, так же как и большинство вариантов ОС Unix и других современных операционных систем, обеспечивает вытесняющую многозадачность. В системе с вытесняющей многозадачностью решение о том, когда один процесс должен прекратить выполнение, а другой возобновить его, принимает планировщик. Событие, заключающееся в принудительном замораживании выполняющегося процесса, называется вытеснением (preemption) этого процесса. Период времени, в течение которого процесс выполняется перед тем, как будет вытеснен, известен заранее. Этот период называется квантом времени (timeslice) процесса. В действительности квант времени соответствует той части процессорного времени, которая выделяется процессу. С помощью управления величинами квантов времени процессов планировщик принимает также и глобальное решение о планировании работы всей системы. При этом, кроме всего прочего, предотвращается возможность монопольного использования ресурсов всей системы одним процессом. Как будет показано далее, величины квантов времени в операционной системе Linux рассчитываются динамически, что позволяет получить некоторые интересные преимущества.
В противоположность рассмотренному выше типу многозадачности, в системах с кооперативной многозадачностью процесс продолжает выполняться до тех пор, пока он добровольно не примет решение о прекращении выполнения. Событие, связанное с произвольным замораживанием выполняющегося процесса, называется передачей управления (yielding). У такого подхода очень много недостатков: планировщик не может принимать глобальные решения относительно того, сколько процессы должны выполняться; процесс может монополизировать процессор на большее время, чем это необходимо пользователю; "зависший" процесс, который никогда не передает управление системе, потенциально может привести к неработоспособности системы. К счастью, большинство операционных систем, разработанных за последнее десятилетие, предоставляют режим вытесняющей многозадачности. Наиболее известным исключением является операционная система Mac OS версии 9 и более ранних версий. Конечно, операционная система Unix имеет вытесняющую многозадачность с момента своего создания.
При разработке ядер ОС Linux серии 2.5, планировщик ядра был полностью реконструирован. Новый тип планировщика часто называется O(1)-планировщиком (O(1) scheduler) в связи с соответствующим масштабированием времени выполнения алгоритма планирования[19]. Этот планировщик позволяет преодолеть недостатки предыдущих версий планировщика ядра Linux и обеспечить расширенную функциональность, а также более высокие характеристики производительности. В этой главе будут рассмотрены основы работы планировщиков, как эти основы использованы в О(1)-планировщике, а также цели создания O(1)-планировщика, его устройство, практическая реализация, алгоритмы работы и соответствующие системные вызовы.
Стратегия планирования
Стратегия (policy) планирования— это характеристики поведения планировщика, которые определяют, что и когда должно выполняться. Стратегия планирования определяет глобальный характер поведения системы и отвечает за оптимальное использование процессорного времени. Таким образом, это понятие очень важное.
Процессы, ограниченные скоростью ввода-вывода и скоростью процессора
Процессы можно классифицировать как те, которые ограничены скоростью ввода-вывода (I/O-bound), и те, которые ограничены скоростью процессора (processor-bound). К первому типу относятся процессы, которые большую часть своего времени выполнения тратят на отправку запросов на ввод-вывод информации и на ожидание ответов на эти запросы. Следовательно, такие процессы часто готовы к выполнению, но могут выполняться только в течение короткого периода времени, так как в конце концов они блокируются в ожидании выполнения ввода-вывода (имеются в виду не только дисковые операции ввода-вывода, но и любой другой тип ввода-вывода информации, как, например, работа с клавиатурой).
Процессы, ограниченные скоростью процессора, наоборот, большую часть времени исполняют программный код. Такие процессы обычно выполняются до того момента, пока они не будут вытеснены, так как эти процессы не блокируются в ожидании на запросы ввода-вывода. Поскольку такие процессы не влияют на скорость ввода-вывода, то для обеспечения нормальной скорости реакции системы не требуется, чтобы они выполнялись часто. Стратегия планирования процессов, ограниченных скоростью процессора, поэтому предполагает, что такие процессы должны выполняться реже, но более продолжительный период времени. Конечно, оба эти класса процессов взаимно не исключают друг друга. Пример процесса, ограниченного скоростью процессора, — это выполнение бесконечного цикла.
Указанные классификации не являются взаимно исключающими. Процессы могут сочетать в себе оба типа поведения: сервер системы X Windows — это процесс, который одновременно интенсивно загружает процессор и интенсивно выполняет операции ввода-вывода. Некоторые процессы могут быть ограничены скоростью ввода-вывода, но время от времени начинают выполнять интенсивную процессорную работу. Хороший пример — текстовый процессор, который обычно ожидает нажатия клавиш, но время от времени может сильно загружать процессор, выполняя проверку орфографии.
Стратегия планирования операционной системы должна стремиться к удовлетворению двух несовместных условий: обеспечение высокой скорости реакции процессов (малого времени задержки, low latency) и высокой производительности (throughput). Для удовлетворения этим требованиям часто в планировщиках применяются сложные алгоритмы определения наиболее подходящего для выполнения процесса, которые дополнительно гарантируют, что все процессы, имеющие более низкий приоритет, также будут выполняться. В Unix-подобных операционных системах стратегия планирования направлена на то, чтобы процессы, ограниченные скоростью ввода-вывода, имели больший приоритет. Использование более высокого приоритета для процессов, ограниченных скоростью ввода-вывода, приводит к увеличению скорости реакции процессов, так как интерактивные программы обычно ограничиваются скоростью ввода-вывода. В операционной системе Linux для обеспечения хорошей скорости реакции интерактивных программ применяется оптимизация по времени оклика (обеспечение малого времени задержки), т.е. процессы, ограниченные скоростью ввода-вывода, имеют более высокий приоритет. Как будет видно далее, это реализуется таким образом, чтобы не пренебрегать и процессами, ограниченными скоростью процессора.
Приоритет процесса
Наиболее широко распространенным типом алгоритмов планирования является планирование с управлением по приоритетам (priority-based). Идея состоит в том, чтобы расположить процессы по порядку в соответствии с их важностью и необходимостью использования процессорного времени. Процессы с более высоким приоритетом будут выполняться раньше тех, которые имеют более низкий приоритет, в то время как процессы с одинаковым приоритетом планируются на выполнение циклически (по кругу, round-robin), т.е. периодически один за другим. В некоторых операционных системах, включая Linux, процессы с более высоким приоритетом получают также и более длительный квант времени. Процесс, который готов к выполнению, у которого еще не закончился квант времени и который имеет наибольший приоритет, будет выполняться всегда. Как операционная система, так и пользователь могут устанавливать значение приоритета процесса и таким образом влиять на работу планировщика системы.
19
Обозначение O(1) — это пример обозначения "большого O". Практически, эта запись означает, что планировщик может выполнить все свои действии за постоянное время, независимо от объема входных данных. Полное объяснение того, что такое обозначение "большого O", приведено в приложении В, "Сложность алгоритмов".