Я стараюсь чередовать статьи про разработку ОС вообще и специфические для ОС Фантом статьи. Эта статья — общего плана. Хотя, конечно, я буду давать примеры именно из кода Фантома.
В принципе, реализация собственно механизма многозадачности — довольно простая вещь. Сама по себе. Но, во-первых, есть тонкости, и во-вторых, она должна кооперироваться с некоторыми другими подсистемами. Например, та же реализация примитивов синхронизации очень тесно связана с реализацией многозадачности. Есть небанальная связь так же и с подсистемой обслуживания прерываний и эксепшнов. Но об этом позже.
Начнём с того, что есть два довольно мало связанных модуля — собственно подсистема переключения задач (контекстов) и подсистема шедулинга. Вторую мы сегодня обсуждать почти не будем, просто опишем кратко.
Шедулер — это функция, которая отвечает на вопрос «какой нити отдать процессор прямо сейчас». Всё. Простейший шедулер просто перебирает все нити (но, конечно, готовые к исполнению, не остановленные) по кругу (RR алгоритм). Реальный шедулер учитывает приоритеты, поведение нити (интерактивные получают больше, чем вычислительные), аффинити (на каком процессоре нить работала в прошлый раз) и т.п., при этом умеет сочетать несколько классов приоритетов. Типично это класс реального времени (если есть хотя бы одна нить этого класса — работает она), класс разделения времени и класс idle (получает процессор только если два предыдущих класса пустые, то есть в них нет нитей, готовых к исполнению).
На сём пока про шедулер закончим.
Перейдём к собственно подсистеме, которая умеет отнять процессор у одной нити и отдать его другой.
Опять же, начнём с простого. Многозадачность бывает кооперативная и преемптивная.
Кооперативная крайне проста — каждая нить время от времени честно и сознательно «отдаёт» процессор, вызывая функцию yield().
В реальности она применяется редко, но в основе каждой преемптивной многозадачности лежит кооперативная. Строго говоря, вся преемптивная многозадачность сводится к тому, чтобы при помощи таймерного прерывания отобрать процессор у пользовательской нити и далее вполне кооперативно, «руками», переключиться на другую нить.
Сама же кооперативная многозадачность базируется на всего одной функции. Функции, которую вызвали все нити одновременно.
В это место надо немножко вдуматься. Это действительно так: с точки зрения всех нитей системы кроме той, что сейчас работает (для простоты рассмотрим однопроцессорную систему) все они вызвали функцию переключения контекста и в ней были приостановлены. В самой её середине. Работающая же нить (сама, или по принуждению через прерывание) тоже вызовет эту функцию, когда придёт время «отдать» процессор. Вызов этот приведёт к тому, что вызвавшая нить остановится, а функция переключения контекста вернётся в другую нить. (Ту, которую выбрал шедулер).
Чуть позже мы рассмотрим весь код переключения контекста, но сейчас — самая сердцевина, собственно переключение между нитями.
Ссылка на реализацию для Intel 32 bit
Я немного почистил код для простоты:
Функция принимает три аргумента — с какой нити переключаемся, на какую нить переключаемся, какой спинлок отпереть после переключения.
Смысл её крайне прост. Сложим всё (важное) состояние процессора на стек, потом запишем позицию указателя стека в специальное поле структуры, которая описывает текущую нить. Затем вынем из структуры для новой нити положение указателя стека, восстановим указатель стека и вынем из стека состояние процессора новой нити. Всё, после этого функция вернётся уже в новую нить.
Перед этим мы отопрём спинлок, который нам передала прошлая нить — как видно, отопрём мы его строго после переключения, то есть когда старая нить уже остановлена — это важно для реализации примитивов синхронизации и для поддержки многопроцессорности. (Если мы отопрём спинлок до переключения, другой процессор может попытаться активировать нить, которую мы ещё не до конца деактивировали.)
То, что мы рассмотрели — самое сердце реализации. Но напрямую эта функция не вызывается (она вообще реализует только архитектурно-зависимую часть кода), а вызывается она из обёртки phantom_thread_switch().
См. код phantom_thread_switch().
Что происходит в обёртке. Пойдём по шагам.
Убедимся, что мы не в контексте прерывания (прерывания приостанавливать нельзя, нарушится целостность хардверного состояния процессора) и что вообще подсистема нитей активирована. Запретим гарантированно прерывания. Вот уж что нам сейчас точно не нужно.
Запрём общий спинлок переключения контекстов. Вообще-то его можно бы делать per CPU, но для спокойствия — только одно переключение контекста в момент времени. Вынем из структуры описания нити ссылку на спинлок, который надо отпереть после переключения — её нам передал примитив синхронизации. Обнулим ссылку внутри структуры, чтобы спинлок не отперли повторно.
Заберём у нынешней нити последний «тик» — запланированный для неё интервал работы на процессоре. Это для шедулера, так что сейчас в детали вдаваться не буду. Спросим шедулер, кому отдать процессор. Запомним кто была нынешняя нить. Убедимся для порядка, что шедулер не сошёл с ума и не предложил нам запустить нить, которая не имеет права работать (ненулевые sleep_flags).
Чтобы не заниматься фигнёй, проверим, не ту же ли самую нить надо будет запустить, если ту же — просто закончим упражнение, отметив в статистике это событие.
Уберём новую нить из очереди нитей, готовых к исполнению (именно в ней шедулер ищет претендентов на постановку на процессор). На самом деле, очередей несколько, но это уже детали — уберём из всех.
Если старая нить не заблокирована, то, наоборот, поставим её в очередь (вот тут-то нам и полезен глобальный schedlock), чтобы она могла претендовать на постановку на процессор в дальнейшем. (Если заблокирована, то в очередь её вернёт тот, кто разблокирует.)
Дальше всё жёстко. Надо чётко понимать, что после вызова phantom_switch_context мы работаем в другой нити, у нас ДРУГИЕ ЗНАЧЕНИЯ ЛОКАЛЬНЫХ ПЕРЕМЕННЫХ. В частности, переменная next, в которой хранится указатель на дескриптор той нити, которую мы запускаем, после запуска нити будет содержать неверное значение. Поэтому глобальную переменную, которая хранит знание о том, какая нить сейчас работает, мы исправим до переключения, а не после. (Вообще-то, после тоже можно, но из другой переменной.:)
Дальше мы разрешаем софтверные прерывания перед собственно переключением, и запрещаем их после. Это нужно потому, что именно преемптивное переключение контекста происходит именно из софтверных прерываний, и нужно гарантировать определённый протокол работы с ними. Это я расскажу отдельно, момент реально тонкий.
Дальше — напомню, все локальные переменные поменяли значение. Для спокойствия души я ими больше не пользуюсь (хотя, по сути, и можно бы — просто надо понимать, что именно они содержат), и снова выясняю, «кто я» — какая нить запущена. Во-первых, я сообщаю ей, на каком процессоре она «проснулась», во-вторых, вызывается архитектурно-специфичная функция восстановления контекста после переключения.
Для Интела эта специфичная функция восстанавливает настройку верхушки стека при переключении в ядерный режим:
Она нужна если нить вернётся в режим пользователя после переключения контекста — прерывания и системные вызовы из пользовательского режима приводят к аппаратному переключению стека процессором, и для каждой нити такой стек индивидуален, конечно.
Есть и ещё тонкости, которые я не упомянул. Например, традиционно на Интеле при восстановлении состояния процессора не восстанавливают регистры плавающей точки и SSE — вместо этого выставляют флаг запрета доступа к ним. Если код нити реально попытается этими регистрами воспользоваться, произойдёт исключение, которое и восстановит состояние этих регистров. Они довольно весомы, а используются очень не всеми, и такая оптимизация имеет смысл.
Теперь о запуске нити. Чтобы создать новую нить, нужно, чтобы она могла… вернуться из phantom_switch_context()!
Это значит, что нужно «собрать» на стеке новой нити такую картину, которая возникает когда она находится внутри phantom_switch_context() в точке, где мы переключили указатель стека на новую нить. При этом адрес возврата из phantom_switch_context() должен быть адресом функции, которая, во-первых, сделает то, что делает после переключения нити phantom_thread_switch(), во-вторых, закончит инициализацию нити, и, наконец, вызовет функцию, которая должна быть исполнена в рамках новой нити.
Мы не рассмотрели в этой статье собственно преемптивность — как именно реализуется «отъём» процессора у старой нити, и кто и когда вызывает phantom_thread_switch(). Но это уже отдельная статья.
В принципе, реализация собственно механизма многозадачности — довольно простая вещь. Сама по себе. Но, во-первых, есть тонкости, и во-вторых, она должна кооперироваться с некоторыми другими подсистемами. Например, та же реализация примитивов синхронизации очень тесно связана с реализацией многозадачности. Есть небанальная связь так же и с подсистемой обслуживания прерываний и эксепшнов. Но об этом позже.
Начнём с того, что есть два довольно мало связанных модуля — собственно подсистема переключения задач (контекстов) и подсистема шедулинга. Вторую мы сегодня обсуждать почти не будем, просто опишем кратко.
Шедулер — это функция, которая отвечает на вопрос «какой нити отдать процессор прямо сейчас». Всё. Простейший шедулер просто перебирает все нити (но, конечно, готовые к исполнению, не остановленные) по кругу (RR алгоритм). Реальный шедулер учитывает приоритеты, поведение нити (интерактивные получают больше, чем вычислительные), аффинити (на каком процессоре нить работала в прошлый раз) и т.п., при этом умеет сочетать несколько классов приоритетов. Типично это класс реального времени (если есть хотя бы одна нить этого класса — работает она), класс разделения времени и класс idle (получает процессор только если два предыдущих класса пустые, то есть в них нет нитей, готовых к исполнению).
На сём пока про шедулер закончим.
Перейдём к собственно подсистеме, которая умеет отнять процессор у одной нити и отдать его другой.
Опять же, начнём с простого. Многозадачность бывает кооперативная и преемптивная.
Кооперативная крайне проста — каждая нить время от времени честно и сознательно «отдаёт» процессор, вызывая функцию yield().
В реальности она применяется редко, но в основе каждой преемптивной многозадачности лежит кооперативная. Строго говоря, вся преемптивная многозадачность сводится к тому, чтобы при помощи таймерного прерывания отобрать процессор у пользовательской нити и далее вполне кооперативно, «руками», переключиться на другую нить.
Сама же кооперативная многозадачность базируется на всего одной функции. Функции, которую вызвали все нити одновременно.
В это место надо немножко вдуматься. Это действительно так: с точки зрения всех нитей системы кроме той, что сейчас работает (для простоты рассмотрим однопроцессорную систему) все они вызвали функцию переключения контекста и в ней были приостановлены. В самой её середине. Работающая же нить (сама, или по принуждению через прерывание) тоже вызовет эту функцию, когда придёт время «отдать» процессор. Вызов этот приведёт к тому, что вызвавшая нить остановится, а функция переключения контекста вернётся в другую нить. (Ту, которую выбрал шедулер).
Чуть позже мы рассмотрим весь код переключения контекста, но сейчас — самая сердцевина, собственно переключение между нитями.
Ссылка на реализацию для Intel 32 bit
Я немного почистил код для простоты:
// called and returns with interrupts disabled
/* void phantom_switch_context(
phantom_thread_t *from,
phantom_thread_t *to,
int *unlock );
*/
ENTRY(phantom_switch_context)
movl 4(%esp),%eax // sw from (store to)
movl (%esp),%ecx // IP
movl %ecx, CSTATE_EIP(%eax)
movl %ebp, CSTATE_EBP(%eax)
// we saved ebp, can use it.
movl %esp, %ebp
// params are on bp now
pushl %ebx
pushl %edi
pushl %esi
movl %cr2, %esi
pushl %esi
movl %esp, CSTATE_ESP(%eax)
// saved ok, now load
movl 8(%ebp),%eax // sw to (load from)
movl CSTATE_ESP(%eax), %esp
popl %esi
movl %esi, %cr2
popl %esi
popl %edi
popl %ebx
movl CSTATE_EIP(%eax), %ecx
movl %ecx, (%esp) // IP
// now move original params ptr to ecx, as we will use and restore ebp
movl %ebp, %ecx
movl CSTATE_EBP(%eax), %ebp
// Done, unlock the spinlock given
movl 12(%ecx),%ecx // Lock ptr
pushl %ecx
call EXT(hal_spin_unlock)
popl %ecx
// now we have in eax (which is int ret val) old lock value
ret
Функция принимает три аргумента — с какой нити переключаемся, на какую нить переключаемся, какой спинлок отпереть после переключения.
Смысл её крайне прост. Сложим всё (важное) состояние процессора на стек, потом запишем позицию указателя стека в специальное поле структуры, которая описывает текущую нить. Затем вынем из структуры для новой нити положение указателя стека, восстановим указатель стека и вынем из стека состояние процессора новой нити. Всё, после этого функция вернётся уже в новую нить.
Перед этим мы отопрём спинлок, который нам передала прошлая нить — как видно, отопрём мы его строго после переключения, то есть когда старая нить уже остановлена — это важно для реализации примитивов синхронизации и для поддержки многопроцессорности. (Если мы отопрём спинлок до переключения, другой процессор может попытаться активировать нить, которую мы ещё не до конца деактивировали.)
То, что мы рассмотрели — самое сердце реализации. Но напрямую эта функция не вызывается (она вообще реализует только архитектурно-зависимую часть кода), а вызывается она из обёртки phantom_thread_switch().
См. код phantom_thread_switch().
Что происходит в обёртке. Пойдём по шагам.
Убедимся, что мы не в контексте прерывания (прерывания приостанавливать нельзя, нарушится целостность хардверного состояния процессора) и что вообще подсистема нитей активирована. Запретим гарантированно прерывания. Вот уж что нам сейчас точно не нужно.
assert_not_interrupt();
assert(threads_inited);
int ie = hal_save_cli();
Запрём общий спинлок переключения контекстов. Вообще-то его можно бы делать per CPU, но для спокойствия — только одно переключение контекста в момент времени. Вынем из структуры описания нити ссылку на спинлок, который надо отпереть после переключения — её нам передал примитив синхронизации. Обнулим ссылку внутри структуры, чтобы спинлок не отперли повторно.
hal_spin_lock(&schedlock);
toUnlock = GET_CURRENT_THREAD()->sw_unlock;
GET_CURRENT_THREAD()->sw_unlock = 0;
Заберём у нынешней нити последний «тик» — запланированный для неё интервал работы на процессоре. Это для шедулера, так что сейчас в детали вдаваться не буду. Спросим шедулер, кому отдать процессор. Запомним кто была нынешняя нить. Убедимся для порядка, что шедулер не сошёл с ума и не предложил нам запустить нить, которая не имеет права работать (ненулевые sleep_flags).
// Eat rest of tick
GET_CURRENT_THREAD()->ticks_left--;
phantom_thread_t *next = phantom_scheduler_select_thread_to_run();
phantom_thread_t *old = GET_CURRENT_THREAD();
assert( !next->sleep_flags );
Чтобы не заниматься фигнёй, проверим, не ту же ли самую нить надо будет запустить, если ту же — просто закончим упражнение, отметив в статистике это событие.
if(next == old)
{
STAT_INC_CNT(STAT_CNT_THREAD_SAME);
goto exit;
}
Уберём новую нить из очереди нитей, готовых к исполнению (именно в ней шедулер ищет претендентов на постановку на процессор). На самом деле, очередей несколько, но это уже детали — уберём из всех.
Если старая нить не заблокирована, то, наоборот, поставим её в очередь (вот тут-то нам и полезен глобальный schedlock), чтобы она могла претендовать на постановку на процессор в дальнейшем. (Если заблокирована, то в очередь её вернёт тот, кто разблокирует.)
t_dequeue_runq(next);
if(!old->sleep_flags)
t_enqueue_runq(old);
Дальше всё жёстко. Надо чётко понимать, что после вызова phantom_switch_context мы работаем в другой нити, у нас ДРУГИЕ ЗНАЧЕНИЯ ЛОКАЛЬНЫХ ПЕРЕМЕННЫХ. В частности, переменная next, в которой хранится указатель на дескриптор той нити, которую мы запускаем, после запуска нити будет содержать неверное значение. Поэтому глобальную переменную, которая хранит знание о том, какая нить сейчас работает, мы исправим до переключения, а не после. (Вообще-то, после тоже можно, но из другой переменной.:)
Дальше мы разрешаем софтверные прерывания перед собственно переключением, и запрещаем их после. Это нужно потому, что именно преемптивное переключение контекста происходит именно из софтверных прерываний, и нужно гарантировать определённый протокол работы с ними. Это я расскажу отдельно, момент реально тонкий.
// do it before - after we will have stack switched and can't access
// correct 'next'
SET_CURRENT_THREAD(next);
hal_enable_softirq();
phantom_switch_context(old, next, toUnlock );
hal_disable_softirq();
Дальше — напомню, все локальные переменные поменяли значение. Для спокойствия души я ими больше не пользуюсь (хотя, по сути, и можно бы — просто надо понимать, что именно они содержат), и снова выясняю, «кто я» — какая нить запущена. Во-первых, я сообщаю ей, на каком процессоре она «проснулась», во-вторых, вызывается архитектурно-специфичная функция восстановления контекста после переключения.
phantom_thread_t *t = GET_CURRENT_THREAD();
t->cpu_id = GET_CPU_ID();
arch_adjust_after_thread_switch(t);
Для Интела эта специфичная функция восстанавливает настройку верхушки стека при переключении в ядерный режим:
cpu_tss[ncpu].esp0 = (addr_t)t->kstack_top;
Она нужна если нить вернётся в режим пользователя после переключения контекста — прерывания и системные вызовы из пользовательского режима приводят к аппаратному переключению стека процессором, и для каждой нити такой стек индивидуален, конечно.
Есть и ещё тонкости, которые я не упомянул. Например, традиционно на Интеле при восстановлении состояния процессора не восстанавливают регистры плавающей точки и SSE — вместо этого выставляют флаг запрета доступа к ним. Если код нити реально попытается этими регистрами воспользоваться, произойдёт исключение, которое и восстановит состояние этих регистров. Они довольно весомы, а используются очень не всеми, и такая оптимизация имеет смысл.
Теперь о запуске нити. Чтобы создать новую нить, нужно, чтобы она могла… вернуться из phantom_switch_context()!
Это значит, что нужно «собрать» на стеке новой нити такую картину, которая возникает когда она находится внутри phantom_switch_context() в точке, где мы переключили указатель стека на новую нить. При этом адрес возврата из phantom_switch_context() должен быть адресом функции, которая, во-первых, сделает то, что делает после переключения нити phantom_thread_switch(), во-вторых, закончит инициализацию нити, и, наконец, вызовет функцию, которая должна быть исполнена в рамках новой нити.
Мы не рассмотрели в этой статье собственно преемптивность — как именно реализуется «отъём» процессора у старой нити, и кто и когда вызывает phantom_thread_switch(). Но это уже отдельная статья.
