В самом первом приближении компьютер состоит из трёх частей: процессор, память и шина данных. Процессор умеет считать, память - хранить данные, а шина данных позволяет передавать данные между первыми двумя.
/-----\ +-----+
| CPU | <=Data Bus=> | RAM |
\-----/ +-----+Такими были большинство компьютеров со времён их возникновения. В память помещалась программа и данные, которые она обрабатывала. В конце работы программы в памяти хранился результат выполнения.
Во время же работы по шине байт за байтом передавались команды и данные процессору. Так что по сути компьютер - это конвейер заданий и данных.
Тут сразу у современного пользователя возникает вопрос: а где мышка, клавиатура и монитор? А это уже надстройки над нашим конвейером. Через прерывания контроллера переферийных устройств в стройный ряд инструкций и данных, летящих из памяти вклиниваются и аппаратные команды, которые заставляют наш конвейер прерваться и перейти к определённому адресу, где расположена программа-обработчик прерывания.
В Linux можно посмотреть статистику по прерываниям с помощью команды vmstat -
под system есть колонка in (сокращение от interrupts) - количество прерываний
в секунду (не все они аппаратные).
Данная команда будет выводить статистику каждую секунду 5 раз:
vmstat 1 5После выполнения программы-обработчика прерывания работа конвейера возобновляется. Так работает обработка сигналов от мышки и клавиатуры. Работа с видео-картой и монитором построена иначе, но сейчас мы не будем это рассматривать.
Важно, что только через прерывания компьютер и программы понимают, что во внешнем мире что-то произошло. К примеру, прошло какое-то время - по прерыванию от аппаратного таймера.
Как вы думаете, что произойдёт, если по какой-то причине перестанут поступать прерывания от таймера? Или таймер начнёт медленнее тикать?
Операционная система посчитает, что мир стал медленнее, или же компьютер быстрее. В предельном случае процессор будет исполнять текущую задачу, не обращая внимания на остальное.
Иллюзия многозадачности
В частности, наша система станет однозадачной. Ведь никакой многозадачности нет (особенно, если мы рассматриваем однопроцессорную систему). Однако, потребность в этом есть: на компьютере могут работать несколько пользователей одновременно, а каждый пользователь хочет запустить несколько задач.
Поэтому нам нужно сделать из однозадачной системы иллюзию многозадачной. Для этого мы поделим время работы процессора между всеми задачами. Точнее - поделим всё время работы на небольшие части, а в эти небольшие части (time slice), в которые будем исполнять то одну задачу, то другую. Если делать это очень быстро - создаётся иллюзия параллельной обработки нескольких задач одновременно.
И тут появляется планировщик
Возникает логичный вопрос: а кто будет заниматься созданием иллюзии многозадачности? Какая-то программа для управления программами (этакая мета-программа) - как раз планировщик. Причём от него зависит довольно многое - на сколько хорошо будет работать иллюзия параллельного исполнения множества процессов.
Поэтому наша программа-планировщик должна стараться раздавать имеющиеся кванты времени “справедливо”. При этом понятие “справедливо” - тоже довольно обширное. К примеру, пользователь будет недоволен, если воспроизведение фильма будет подвисать, при этом не сильно расстроится, если фоновая задача будет притормаживать.
Плюсом к этому будет грустно, если задача распределения ресурсов процессора будет съедать сильно много процессорного времени - неприятно, когда управленцы получают больше, чем исполнители.
Также важно помнить, что пользователю важен отклик системы. Поэтому планировщик должен быть привязан как-то к реальному времени.
И тут есть множество проблем для планировщика. Так, к примеру, нельзя определить, когда программа дойдёт до определённого момента (идеальный момент для переключения) чисто по алгоритмическим причинам.
К слову, может быть кто-то знает альтернативные подходы к реализации вычислительных систем, не процессор-шина-память?
Что-то может пойти не так и какая-то программа зависнет - что тут делать, как решать, что нужно передать управление, что делать с этой программой? Опять же, понять, что она реально зависла для произвольной программы мы не можем…
И тут остаётся использовать те самые аппаратные прерывания. Если программа сама не передаёт управление - через прерывание таймера мы можем понять, что время пришло переключить управление. Ну и в целом - можно по таймеру следить за “справедливостью” выделения процессорного времени. На него ориентироваться при планировании исполнения процессов.
Пара слов о проблемах реализации многозадачности
Работа с системными ресурсами напрямую предполагает работу программы в реальном режиме процессора, а не в защищённом. Работая в GNU/Linux нам невозможно получить доступ напрямую к любому участку памяти, а также работать с регистрами процессора типа sp, ip и т.д. без изменения кода ядра и его пересборки.
С другой стороны можно взять более старую ОС, которая не поддерживает многозадачность (равно как и защищённый режим работы процессора) и пофантазировать - что нам нужно сделать, чтобы там можно было получить иллюзию многозадачности. Например, DOS.
Здесь, запустив программу из командной строки, мы получаем доступ ко всем ресурсам - ОС никак не защищает ресурсы компьютера от пользовательских программ, а лишь предоставляет набор процедур для более простого программирования. Поэтому мы можем делать всё, что захотим. К примеру, написать программу, которая будет обеспечивать работу других программ псевдо-параллельно.
То есть она будет запускать другие программы, отдавать им или прерывать их исполнение, а между запусками хранить их состояние. Например, значения регистров процессора. Куда важнее, сохранить состояние регистра IP (instruction pointer) - регистра, который указывает на исполняемый в текущий момент код. И здесь важно, чтобы программа сохраняла его по условленному адресу в памяти при передаче управления. Тогда планировщик сможет использовать его для возврата управления.
Итого, нам нужно как минимум выделить некоторую память под список IP, соответствующих адресам текущих исполняемых команд в процессах. Кроме того - память компьютера доступна всем и сразу, так что нужно договориться, чтобы авторы программ писали в разных областях памяти, чтобы не залезать в чужую. Опять же нужно позаботиться о стеке процессов. В общем, масса проблем. Многие из них сейчас решаются аппаратными средствами, прочее же делает ОС.
Как можно было заметить, действий производится довольно много, чтобы одна программа могла работать рядом с другой. При этом очень многое держится чисто на человеческих договорённостях. И любой отход от договорённостей или ошибка в программе может привести к отказу работы всего компьютера.
Надеюсь, в общих чертах было ясно, какие действия необходимы и на сколько непросто написать даже такой примитивный планировщик?
Многозадачность и справедливость
Итак, представим, что у нас есть N процессов и 1 процессор. Нам нужно поделить время процессора между всеми процессами справедливым образом. То есть каждому по 1÷N. Однако, пусть мы и справедливы, и все процессы равны, но некоторые всё же “равнее” - есть процессы с низкой потребностью в отзывчивости и ресурсе CPU, есть же критичные - задержку работы которых пользователь сразу заметит. Поэтому процессы приоритезируются. Тогда наша формула принимает следующий вид: “Процент времени процесса = Приоритет ÷ Сумма приоритетов”.
Но это в идеальном мире. В реальности же процессы вольно или невольно стараются получить времени больше, или же отдают управление раньше (через тот же sched_yield), чем им выделено. Тем не менее, за условной “справедливостью” следить нужно.
При этом от времени процессора также “откусит” и сам планировщик - мы уже видели, что сама операция переключения рабочего процесса довольно затратна. Плюс ещё нужно рассчитать порядок выполнения - работа алгоритма расчёта также займёт какое-то время.
Есть 2 основных подхода к многозадачности: кооперативный и вытесняющий.
В кооперативной многозадачности процессы сами решают, когда они готовы отдать
управление. В вытесняющей многозадачности планировщик ведёт подсчёт времени
исполнения процессов (с помощью таймера) и сам прерывает рабочий процесс, когда
тот выходит за выделенный лимит.
Кооперативная многозадачность
В случае кооперативной многозадачности плюсами будут простота реализации планировщика - ему не приходится принимать решения, а также меньший расход времени на переключение задач - предполагается, что задачи будут переключаться, когда они завершили какой-то этап своей работы и, например, запросили новые данные.
Среди минусов же - потенциально низкая отзывчивость, а также зависания из-за ошибок в какой-то конкретной программе (не возвращает управление).
Среди примеров ОС, работающих по такому принципу - Windows 3.* Кто-нибудь слышал или даже знаком с этой веткой Windows?
К примеру, для переключения между тредами может быть использована команда ThreadSwitch. Текущая задача остаётся активной (готовой) и передаёт управление следующей готовой задаче. Хоть внутри и выполняются низкоуровневые операции, для языка программирования высокого уровня данная функциональная возможность выглядит как обычная функция.
void ThreadSwitch () {
old_thread = current_thread;
// Текущий тред убрали в конец очереди
add_to_queue_tail(current_thread);
// Новый активный тред взяли из начала очереди
current_thread = get_from_queue_head();
// Сохраняем stack pointer
asm {
move bx, old_thread
push bp
move ax, sp
move thread_sp[bx], ax
move bx, current_thread
move ax, thread_sp[bx]
pop bp
}
return;
}Из очереди тредов берётся новый из начала, текущий помещается в конец.
Текущий стек сохраняется в предварительно подготовленный map
(словарь номер_треда - адрес_стека_треда), из этого же map берётся адрес
стека для нового треда, кладётся в регистр SP (stack pointer),
запускается новый тред.
К слову, и в Linux можно попросить ОС забрать управление у треда досрочно
с помощью вызова pthread_yield.
Все помнят, что такое очередь? Как работает FIFO?
Аналогично работает async-await в современных языках программирования
высокого уровня таких как ECMA Script, Python3 и т.д.
На команде await управление передаётся следующему исполняемому потоку.
Внутри событийной петли (по сути - той же очереди) они кружат,
выполняясь один за другим.
from asyncio import *
# Сопрограмма
async def hello(word):
counter = 0
while counter < 10:
print("from " + word)
# Здесь отдаём управление,
# как минимум пока не закончится sleep(0.1)
await sleep(0.1)
counter += 1
loop = get_event_loop()
# Запускаем на петле 2 сопрограммы
loop.run_until_complete(
gather(hello("A"), hello("B"))
)
loop.close()Вытесняющая многозадачность
Из плюсов - бóльшая привязка к реальности (планировщик следит за реальным временем исполнения процесса), а значит более прогнозируемая отзывчивость. Также выше стабильность - если какой-то процесс завис - он будет "выедать" только отведённое ему время.
Однако, если размер кусков, на которые мы нарезаем процессорное время мал, то из-за частых смен задач (смен контекста) можно получить потерю производительности.
За счёт прогнозируемости и отзывчивости данный подход распространился на почти все современные ОС.
Говоря о расходе времени при переключении контекста, как вы думаете, на чём же больше всего теряется время?
Смена контекста (context switch)
Само собой, при смене контекста производится много работы. Часть из неё мы уже описали выше, но особого внимания заслуживает отдельный момент, который мы ещё не обсуждали.
Кеш процессора
Современные компьютеры много сложнее, чем процессор-шина-память. В частности, для ускорения работы этой связки был добавлен ещё один вид памяти, который расположен ближе к процессору, чем RAM - кеш процессора. Размер кеша меньше, чем памяти. Однако, редко какая программа оперирует всей памятью сразу. Обычно необходимые для работы программы данные лежат вместе и их размер невелик.
/-----\
| CPU |
| +-----+ +-----+
\---|cache| <=Data Bus=> | RAM |
+-----+ +-----+Именно благодаря этому небольшая память кеша, но низкое время обращения процессора к ней, и даёт значительный прирост производительности на многих задачах. С другой стороны - при переключении контекстов в кеше может не хватать места под оперативные данные всех процессов - тогда кеш будет обновляться (также говорят “прогреваться”) из памяти по мере необходимости. И это может сильно замедлить работу компьютера по сравнению с работой при горячем кеше.
В следующем примере мы запустим программу в 8 потоков на 8-ми ядрах. Они будут увеличивать общий счётчик до довольно большого числа. Так как они будут параллельно обрабатывать одни и те же данные, компьютер будет постоянно синхронизировать кеши.
#include "pthread.h"
#include "stdio.h"
#include "time.h"
#define THREAD_COUNT 8
#define ITERATION_LIMIT 1000000000LL
// Общие данные
long long count = 0;
static void *hello(void* d) {
while(count < ITERATION_LIMIT)
++count; // Изменяем общие данные
return NULL;
}
int main() {
pthread_t thread[THREAD_COUNT];
// Запускаем треда
for (int i = 0; i < THREAD_COUNT; ++i)
pthread_create(&thread[i], NULL, &hello, i);
// Ждём завершения в основном треде
for (int i = 0; i < THREAD_COUNT; ++i)
pthread_join(thread[i], NULL);
return 0;
}Сборка:
clang -lpthread file.cДля примера, если запустить эту же программу но на одном ядре (пусть и в 8
потоков) - смены контекста также будут происходить, но кеш будет “горячим” -
программа выполнится быстрее. Для запуска на определённых процессорах программ
(или миграции) используется утилита taskset (или программно
sched_setaffinity).
$ time taskset 1 ./a.out
real 0m1,372s
user 0m1,368s
sys 0m0,005s
$ time ./a.out
real 0m5,007s
user 0m39,886s
sys 0m0,004sПосмотреть же статистическую информацию о смене контекстов за секунду можно всё
также в vmstat. Столбик system, раздел “cs” (от “context switch”).
nice и приоритет исполнения процессов
Если же мы хотим настроить приоритет программы, воспользуемся утилитой nice
(или программно с setpriority). С помощью неё можно указать ОС, с каким
приоритетом мы бы хотели запустить программу. Приоритеты в Linux определяются
цифрами от -20 до 19. Чем меньше - тем приоритетнее. Для установки приоритета
ниже 0 необходимы права супер-пользователя (например, можно установить через
sudo).
Есть ещё процесс idle (процесс для простоя процессора, или же программа
запущенная с политикой SCHED_IDLE), приоритет которого ниже 19 и
migration_thread (для вытеснения процесса с ядра для миграции его на другой
процессор) - у него выше -20.
Для примера, запустим параллельно с разными приоритетами несколько экземпляров предыдущей программы:
#!/bin/bash
nice -n 19 ./a.out >> /dev/null && echo 19 &
nice -n 18 ./a.out >> /dev/null && echo 18 &
nice -n 11 ./a.out >> /dev/null && echo 11 &
nice -n 10 ./a.out >> /dev/null && echo 10 &
nice -n 1 ./a.out >> /dev/null && echo 1 &
nice -n 0 ./a.out >> /dev/null && echo 0 &И посмотрим на результат выполнения:
$ ./nice.sh
$ 1
0
10
11
18
19Идут почти в порядке приоритетов.
Также есть renice для изменения приоритета процессу, группе процессов или
процессам определённого пользователя.
Посмотреть же приоритет запущенных процессов можно через утилиту ps, указав,
что нам хочется видеть и столбик nice (NI):
ps ax -o pid,ni,cmdКванты времени
Говоря о смене контекстов при переключении задач, стоит сказать и о том времени, которое непосредственно выделяется. Кванты или time slice - единицы планирования, тот ресурс, за который борются процессы.
Для начала посмотрим настройки, которые можно использовать для тюнинга планировщика:
sysctl -A | grep sched | grep -v domainОсобо нас интересует kernel.sched_min_granularity_ns - это как раз размер
кванта времени, выделяемого за раз. На пользовательских машинах и серверах
значения могут сильно отличаться. К примеру, на моём ноутбуке это 3мс, а на
сервере 10мс. Меньше отзывчивость, зато меньше смен контекста.
При этом программа может отдать управление раньше, чем закончился выделенный
квант - через sched_yield / pthread_yield.
Настройки, увиденные вами характерны для текущего планировщика по умолчанию Linux - CFS - Completely Fair Scheduler (полностью честный планировщик). Однако, до него было ещё несколько планировщиков, а также есть альтернативные.
Планировщики в Linux
К примеру, всё началось с планировщика O(n) - все задачи расположены в списке, каждому исходя из приоритета присвоено определённое количество тиков (tick), которые соответствуют time slice-ам. Ищем задачу с максимальным значением, исполняем, понижаем счётчик тиков задачи. Если не можем найти задачи с положительным счётчиком - поднимаем счётчик всем задачам, исходя из приоритета.
Очевидная проблема данного планировщика - при росте количества задач растёт и время работы планировщика. Причём растёт линейно. В теории сложности вычислений этот алгоритм относится к классу O(n) - рост времени вычисления растёт пропорционально количеству входных данных.
Также данный планировщик имеет проблемы при работе с несколькими процессорами - одна блокировка на одну очередь - то есть одновременно с ней может работать только один процессор.
В 2002-ом году в Linux стали использовать более продвинутый планировщик - O(1). Как можно догадаться, алгоритм работы был изменён. Время работы планировщика более не зависело от числа запущенных процессов. Теперь у каждого процессора было по паре списков. В первом отсортированном списке - текущие процессы, ожидающие выполнения, во втором - исчерпавшие своё время. Как только первый список заканчивался - они менялись местами.
Уже гораздо лучше. Однако и здесь есть свои проблемы. При балансировке нагрузки между процессорам необходимо время от времени производить миграцию процессов с одного процессора на другой. Для этого приходится блокировать очередь работы одного процессора другим.
Также имелись и проблемы с честным выделением ресурсов пользователям. Если один запустит 10 процессов, а другой 1, то разделение времени будет нечестым.
В ядре 2.6.23 появился новый планировщик CFS - Completely Fair Scheduler
(полностью честный планировщик). Он уже оперирует не процессами, а сущностями
планирования (sched_entity) - появилась возможность честнее разделять время
между пользователями. Сам планировщик стал выделять время ближе к приоритетам.
Алгоритм стал несколько “дороже” - O(logN) - используется красно-чёрное дерево, что с ростом количества процессов заметно всё меньше и меньше. Планирование из одной структуры данных организовано довольно оптимально - для работы на многопроцессорных системах подходит также лучше. Именно он сейчас используется в Linux.
Помимо планировщиков общего назначения в Linux есть и планировщик для систем реального времени. Это системы, в которых важно, чтобы время реакции системы на внешний сигнал не превышало определённого времени. К примеру, от момента определения заноса до запуска сервоприводов тормозных колодок должно пройти не более 5мс. Помимо планировщика на работу влияют и многие другие части ОС, например, буферы, обработчики прерываний и т.д. Однако, и планировщик и программы должны быть специальными для работы в реальном времени.
Так в Linux используется SCHED_DEADLINE с алгоритмом планирования по
ближайшему сроку завершения (EDF - Earliest deadline first):
- планировщик ведёт список процессов, отсортированный по сроку завершения (deadline);
- в работу берётся готовый процесс, имеющий самый близкий deadline;
- при появлении нового процесса — пересортировка.
Программы же должны при запуске указывать через sched_setattr параметры
runtime, deadline и period - время исполнения в худшем случае, срок
завершения и период.
Планировщик ввода-вывода
Помимо ресурса процессора также немаловажен ресурс ввода / вывода. С появлением и распространением SSD дела стали лучше, чем при HDD (аж 10мс для перехода к нужному участку носителя), но всё равно это сильно медленнее, чем работа с памятью. Да и в целом ресурсами лучше зря не разбрасываться.
При работе с дисковой подсистемой используется планировщик ввода / вывода.
Причём для разных устройств и задач подходят разные планировщики. Так CFQ
(Completely Fair Queue) и deadline планировщики сначала будут буферизировать
запросы на чтение / запись, чтобы сгруппировать запросы к устройству так, чтобы
эффективнее с него считать. Например, чтобы за один оборот диска можно было
прочитать сектора для разных процессов.
С другой стороны, если используется сетевое хранилище, или виртуальное - лучше
использовать noop - планировщик, который не будет ничего придумывать, а просто
писать / читать как есть. Пусть сетевое хранилище или хостовая система думает об
эффективности, а мы не будем на это тратить CPU.
Посмотреть доступные для устройства планировщики можно через
cat /sys/block/устройство/queue/schedulerЗаписав же туда нужный планировщик с помощью echo - изменить на нужный.
Для приоритизации операций ввода-вывода используется ionice. Для начала
разберёмся с классами планирования:
- Real time - получают первыми доступ к диску. Использование данного класса может помешать работе других программ. Имеет 8 приоритетов.
- Best effort (по умолчанию) - также имеет 8 приоритетов. Программы с одним приоритетом обслуживаются по очереди (round-robin).
- Idle - получает доступ к диску, если другим он не нужен.
Приоритеты от 0 до 7. Меньше - приоритетнее.
Не все планировщики используют приоритеты. К примеру, deadline стремится к тому, чтобы ожидание операции не превышало определённого времени. Noop не делает ничего - просто выполняет операции последовательно. С другой стороны, тот же CFQ использует приоритеты - с ним ionice будет работать.