Планирование процессов в современных ОС на примере FreeBSD // Блог программиста
Опубликовано: 01.09.2018
Множество людей каждый день запускают на компьютерах несколько программ одновременно, совершенно не задумываясь об этом. Word, Excel, музыка на фоне, какая-нибудь игра: нет чего-нибудь одного, ведь без этого сложно представить современный рабочий день за компьютером. Даже пока вы читаете эту статью, ваша операционная система параллельно выполняет какие-нибудь задачи.
Операционные системы, лекция 4, часть 3
Собственно, многозадачность
Как же это работает? Почему? Что за это отвечает?
Поскольку мне интересно, как работают ОС, я хочу раскопать этот вопрос настолько глубоко, насколько это вообще возможно. Итак, начнем с теории.
Параллельность в компьютерах
В основе компьютера лежит процессор, который последовательно выполняет простые инструкции из своего набора. Эти инструкции оперируют данными, которые хранятся в памяти или в регистрах.
Но они выполняются последовательно.
Конечно, существуют многоядерные процессоры, которые могут выполнять инструкции по-настоящему параллельно, но это не создает многозадачность, ведь если у вас четырехъядерный процессор, это же не значит, что вы можете запустить только четыре программы. Нет, основную работу делает операционная система. 
Отладка процесса в дебаггере GDB. Видно, что инструкции выполняются последовательно
Организация процессов в операционных системах
В любой современной ОС есть понятие процесса или потока. По сути, процесс — это набор тех самых последовательных инструкций для процессора. Благодаря тому, что эти инструкции сгруппированы по процессам, ОС может в любой момент сохранить текущее состояние и прервать их выполнение, запустив инструкции другого процесса. Текущее состояние называется контекстом, который содержит все необходимые данные, для того чтобы восстановить выполнение процесса на любом шаге. 
Секции процесса в памяти, в сегменте text располагаются инструкции для процессора
Итак, у ОС есть возможность перераспределять процессорные инструкции, что это дает?
Вместо того, чтобы просто запихивать эти инструкции друг за другом в ОС есть специальная подсистема, которая управляет исполнением — диспетчер процессов. Диспетчер организует очередь выполнения (runqueue), в которую добавляются процессы, готовые к работе. Диспетчер может добавить или убрать процесс из этой очереди в любой момент времени, что называется вытесняющей многозадачностью. В свою очередь процессы сами могут приостановить свое выполнение, ожидая чтения с диска или ввода пользователя, или просто определенный промежуток времени. В момент приостановки процесс убирается из очереди выполнения и выполняется следующий процесс.
Однако все это перемещение процессов должно быть как-то организовано, чтобы грамотно использовать ресурсы процессора. Поэтому положение в очереди, время выполнения на процессоре и момент удаления из очереди определяются другой подсистемой — планировщиком процессов, а способ их смены это определенные алгоритмы, разработанные для различных задач. Рассмотрим их по-подробнее.
Алгоритмы планирования
В основном алгоритмы планирования делятся на вытесняющие и невытесняющие. Вытесняющие могут прервать выполнение работающего процесса, для того чтобы выбрать следующий, что позволяет операционной системе не зависать из-за одного сбойного процесса, и в целом быть эффективнее. В противовес вытесняющим, преимуществом кооперативной многозадачности является отсутствие необходимости организовывать разделение доступа к критическим секциям кода, что упрощает программирование, особенно перенос кода из однозадачных сред в многозадачные.
Среди всех нижеперечисленных алгоритмов есть одна общая черта: процессы организованы в очередь, которая отсортирована по приоритетам. Алгоритм определяет то, чем будет выступать приоритет и как его рассчитывать.
Невытесняющие:
FIFO (First In First Out) – простейший алгоритм, выбирающий для запуска следующий процесс из очереди
На графике отображено время выполнения нескольких процессов, видно что они запускаются последовательно в порядке поступления в очередь. В этом алгоритме не учитываются какие-либо показатели процесса, поэтому он эффективен лишь в очень простых, либо специально подготовленных случаях.
Сначала самое короткое задание (Shortest Process Next) – очередь выстраивается так, чтобы первыми выполнялись небольшие задачи
Хотя этот способ и эффективнее FIFO в большинстве случаев, он все же неэффективно использует вычислительные ресурсы, например, не рассматривается ситуация, когда процесс ничего не делает, ведь тогда компьютер будет простаивать. Однако основная проблема это необходимость определения времени выполнения процесса. Невозможно точно его определить, оценка времени выполнения это довольно сложная задача, требующая отдельного рассмотрения.
Вытесняющие:
Циклическое планирование (Round Robin)
Модификация алгоритма FIFO, где каждому процессу выделяется определенный промежуток времени (квант) в течении которого он может выполняться, после которого выполняется следующий процесс. В общем случае квант выделяется фиксированного размера. Такой подход использовался в старых операционных системах, и, в своем базовом варианте он очень не эффективен: если квант слишком маленький, то смена контекста будет выполняться слишком часто, процессор будет терять слишком много времени на это. А если квант слишком большой, то система просто будет "тормозить".
Преимущество этого алгоритма в том, что его довольно просто реализовать и использовать как часть другого алгоритма.
Улучшенная версия этого алгоритма, которая используется в большинстве современных систем позволяет динамически изменять размер кванта на основе показателей использования процессора, что позволяет избегать ситуации простоя системы, однако накладные расходы на смену контекста остаются.
Наименьшее оставшееся время выполнения
Этот алгоритм похож на тот, где выбирается самое короткое задание, с одним отличием: какой-нибудь долго выполняющийся процесс может быть вытеснен, чтобы какой-нибудь другой процесс закончил все свои дела, тем самым освободив очередь для новых заданий. Это довольно эффективный алгоритм, но он не может использоваться в системах общего назначения, из-за той же проблемы, что и в SPN-алгоритме — необходимость оценивать время выполнения процесса.
В современных операционных системах общего назначения повсеместно используется вытесняющая многозадачность на основе различных улучшений алгоритма циклического планирования.
В принципе, на этом теория закончилась. Разумный человек на этом давно бы уже остановился, но, поскольку мне в университете дали задание на практику — написать планировщик, нужны решительные шаги в исходники . Ссылочка
Добавление планировщика в FreeBSD
В качестве подопытного мне дали FreeBSD.
Она предоставляет удобный интерфейс для добавления новой реализации планировщика, ввиду того, что в самой операционной системе на данный момент есть два поддерживаемых планировщика – исторический 4BSD, и новый ULE, ориентированный на работу в многопроцессорных системах.
Регистрация нового планировщика для включения его в сборку
Для того чтобы добавить планировщик в систему, сначала необходимо зарегистрировать специальную опцию для препроцессора. Все опции должны быть прописаны в файле sys/conf/options, где они группируются по категориям, либо объявляются как глобальные. Опции, касающиеся планировщика собираются в файле opt_sched.h. Также опция должна быть прописана в файле sys/conf/NOTES, где хранятся подробные описания опций. После этого нужно зарегистрировать файл с будущей реализацией планировщика, добавив строчку kern/sched_u.c optional sched_u в sys/conf/files.
После того, как опция добавлена, можно создать свою конфигурацию ядра в архитектурно-специфичном каталоге sys/amd64/conf.
Взяв за основу GENERIC-конфигурацию я заменил опцию планировщика ULE на свою, а также включил различные опции отладки, например шикарный дебаггер, который запускается сразу после паники ядра. 
Пример работы дебаггера
К слову FreeBSD предоставляет удобные средства для отладки, такие как DTrace и kernel tracing facility, позволяющие отмечать события в коде, и указывать метки для отладки кода.
Интерфейс планировщика
Многие думают, что Си это только процедурный язык программирования и для ООП нужны C++ или Java, однако на самом деле некоторые принципы ООП очень часто используются в крупных проектах на Си. Хороший пример этому — интерфейсы. Еще в ядре UNIX такая вещь как VFS представляла собой набор указателей на функции, т.е. функции без реализации в современном понимании. Заполняя эти указатели функциями, специфичными для файловой системы, мы получаем конкретную реализацию интерфейса.
В свою очередь в FreeBSD интерфейс планировщика определен в файле sys/sys/sched.h:
// Служебная информация планировщика int sched_load(void); int sched_rr_interval(void); int sched_runnable(void); // Функции для настройки приоритета процесса void sched_exit(struct proc *p, struct thread *childtd); void sched_fork(struct thread *td, struct thread *childtd); void sched_fork_exit(struct thread *td); void sched_class(struct thread *td, int class); void sched_nice(struct proc *p, int nice); // Функции для управления сменой процессов, слежения за блокировками и ресурсами, // использованием CPU, а также для обработки наследования приоритетов void sched_exit_thread(struct thread *td, struct thread *child); void sched_fork_thread(struct thread *td, struct thread *child); void sched_lend_prio(struct thread *td, u_char prio); void sched_lend_user_prio(struct thread *td, u_char pri); fixpt_t sched_pctcpu(struct thread *td); void sched_prio(struct thread *td, u_char prio); void sched_sleep(struct thread *td, int prio); void sched_switch(struct thread *td, struct thread *newtd, int flags); void sched_throw(struct thread *td); void sched_unlend_prio(struct thread *td, u_char prio); void sched_user_prio(struct thread *td, u_char prio); void sched_userret(struct thread *td); void sched_wakeup(struct thread *td); void sched_preempt(struct thread *td); // Функции для добавления или удаления процессов из очереди выполнения void sched_add(struct thread *td, int flags); void sched_clock(struct thread *td); void sched_rem(struct thread *td); void sched_tick(int cnt); void sched_relinquish(struct thread *td); struct thread *sched_choose(void); void sched_idletd(void *); // Функции для работы с многопроцессными системами void sched_bind(struct thread *td, int cpu); void sched_unbind(struct thread *td); int sched_is_bound(struct thread *td); void sched_affinity(struct thread *td); // Инициализация планировщика void schedinit(void);Алгоритм работы
В рамках этого интерфейса можно расписать алгоритм работы планировщика:
На самом раннем этапе загрузки ядро создает первый процесс thread0 и вызывает schedinit для инициализации всех полей, касающихся планировщика:
void schedinit(void) { proc0.p_sched = NULL; thread0.td_sched = &td_sched0; thread0.td_lock = &sched_lock; td_sched0.ts_slice = sched_slice; mtx_init(&sched_lock, "sched lock", NULL, MTX_SPIN | MTX_RECURSE); }Затем инициализируется первый процесс – init, вызывается функция sched_add для добавления его в очередь выполнения. Для гибкости планировщика очередь выполнения своя для каждого процессора (ядра):
// Глобальная очередь выполнения static struct runq runq; #ifdef SMP // Если многопроцессорность поддерживается, здесь создаются очереди под каждый процессор static struct runq runq_pcpu[MAXCPU]; long runq_length[MAXCPU]; static cpuset_t idle_cpus_mask; #endifsched_add ищет подходящую очередь и добавляет в неё процесс. Если в конфигурации ядра разрешено вытеснение, то сразу же после после добавления вызывается usched_try_resched для переключения на этот процесс, если позволяет его приоритет.
После инициализации таймера ядро вызывает sched_clock из statclock (sys/kern/kern_clock.c) по определенному тику, заданному для пересчета статистики. В этой функции планировщик пересчитывает оставшееся время выполнения, и, если оно закончилось, то устанавливается флаги TDF_NEEDRESCHED и TDF_SLICEEND для смены контекста.
При переходе потока в режим ожидания вызывается sched_sleep, где процесс перемещается в конец очереди выполнения, также инициализируется таймер сна. При возобновлении выполнения вызывается sched_wakeup, где вычисляется время сна, процессу назначается промежуток времени и он добавляется в очередь выполнения.
Если в данный момент нет потоков для выполнения, то из очереди выполнения ставится sched_idletd, который ждет пока не появятся процессы, готовые к запуску и затем сменяет контекст:
void sched_idletd(void *dummy) { struct pcpuidlestat *stat; // Запрет перехода в сон THREAD_NO_SLEEPING(); stat = DPCPU_PTR(idlestat); for (;;) { mtx_assert(&Giant, MA_NOTOWNED); while (sched_runnable() == 0) { // Пока нет доступных процессов, вызываем функцию простоя, // специфическую для архитектуры процессора и обновляем счетчик простоя cpu_idle(stat->idlecalls + stat->oldidlecalls > 64); stat->idlecalls++; } mtx_lock_spin(&sched_lock); // Смена контекста для переключения на доступный процесс mi_switch(SW_VOL | SWT_IDLE, NULL); mtx_unlock_spin(&sched_lock); } }Для смены контекста вызывается функция mi_switch, выполняющая архитектурно-независимые операции при смене контекста. Эта функции также вызывает sched_switch, где для текущего процесса cбрасываются флаги NEED_RESCHED и TDF_SLICEEND, если они установлены. Затем, если не был передан параметр newtd, через функцию sched_choose, которая вызывается из choosethread (sys/kern/kern_switch.c). sched_choose выбирает следующий поток из очереди выполнения, принадлежащей текущему ядру процессора.
После этого sched_switch вызывает архитектурно-зависимый cpu_switch, который, собственно, и завершает процедуру смены контекста.
Все это реализует алгоритм roundrobin. Улучшение алгоритма состоит в том, что приоритет процесса в очереди рассчитывается исходя из загруженности системы и процессора, на котором происходит выполнение, за это отвечает поле td->td_estcpu:
// Формула из планировщика 4BSD #define loadfactor(loadav) (2 * (loadav) ) #define decay_cpu(loadfac, cpu) (((loadfac) * (cpu)) / ((loadfac) + FSCALE) ) static void usched_update_priority(struct thread *td) { struct td_sched *ts; fixpt_t loadfac; unsigned int newcpu; ts = td->td_sched; // Расчет использования процессора loadfac = loadfactor(averunnable.ldavg[0]); if( ts->ts_sleeptime > 5 * loadfac ) td->td_estcpu = 0; else { newcpu = td->td_estcpu; ts->ts_sleeptime--; while( newcpu && --ts->ts_sleeptime ) newcpu = decay_cpu(loadfac, newcpu); td->td_estcpu = newcpu; } } // Расчет приоритета в пространстве пользователя static void usched_reset_priority(struct thread *td) { unsigned int newpriority; if( td->td_pri_class == PRI_TIMESHARE ) { newpriority = PUSER + td->td_estcpu / INVERSE_ESTCPU_WEIGHT + NICE_WEIGHT * (td->td_proc->p_nice - PRIO_MIN); newpriority = min(max(newpriority, PRI_MIN_TIMESHARE), PRI_MAX_TIMESHARE); sched_user_prio(td, newpriority); } }Также во всех UNIX-подобных системах существуют дополнительные очки приоритера – значение "любезности" (nice). Чем больше это значение, тем меньше приоритет процесса, т.е. он уступает другим из-за "любезности".
Заключение
Ну вот, собственно, и все, что можно было сказать о планировщиках. Для меня это был захватывающий опыт погружения в разработку в пространстве ядра. Не могу сказать, что для меня этого было достаточно, теперь я буду и дальше расширять свои горизонты в области системного программирования.
Современные операционные системы – это сложные и интересные системы, только по-настоящему познав их мощь можно понять как работают современные компьютеры и программы. Хотя планирование процессов это одна из основных подсистем, она лишь вершина айсберга, в ОС есть еще множество других вещей, которые можно также разобрать. Пусть в современном мире рабочая среда большинства программистов абстрагирована от всех этих деталей, я все равно считаю, что хотя бы иногда программисту нужно задумываться о том, как же все это работает на самом деле, чтобы писать более эффективный код.