Вытесняющий планировщик

Теперь давайте представим следующую картину. У нас есть два вычислительных потока, выполняющих одну и ту же программу, и есть планировщик, который в произвольный момент времени перед выполнением любой инструкции может прервать активный поток и активировать другой. Для управления подобными задачами уже недостаточно информации только о функции вызова потока и ее параметрах, как в случае с невытесняющими планировщиками. Как минимум, еще нужно знать адрес текущей выполняемой инструкции и набор локальных переменных для каждой задачи. То есть для каждой задачи нужно хранить копии соответствующих переменных, а так как локальные переменные для потоков располагаются на его стеке, то должно быть выделено пространство под стек каждого потока, и где-то должен храниться указатель на текущее положение стека. 

Эти данные — instruction pointer и stack pointer — хранятся в регистрах процессора. Кроме них для корректной работы необходима и другая информация, содержащаяся в регистрах: флаги состояния, различные регистры общего назначения, в которых содержатся временные переменные, и так далее. Все это называется контекстом процессора.
 

Контекст процессора

Контекст процессора (CPU context) — это структура данных, которая хранит внутреннее состояние регистров процессора. Контекст должен позволять привести процессор в корректное состояние для выполнения вычислительного потока. Процесс замены одного вычислительного потока другим принято называть переключением контекста (context switch).

Описание структуры контекста для архитектуры x86 из нашего проекта:

struct context {
 /* 0x00 */uint32_t eip; /**< instruction pointer */
 /* 0x04 */uint32_t ebx; /**< base register */
 /* 0x08 */uint32_t edi; /**< Destination index register */
 /* 0x0c */uint32_t esi; /**< Source index register */
 /* 0x10 */uint32_t ebp; /**< Stack pointer register */
 /* 0x14 */uint32_t esp; /**< Stack Base pointer register */
 /* 0x18 */uint32_t eflags; /**< EFLAGS register hold the state of the processor */
};

Понятия контекста процессора и переключения контекста — основополагающие в понимании принципа вытесняющего планирования.
 

Переключение контекста

Переключение контекста — замена контекста одного потока другим. Планировщик сохраняет текущий контекст и загружает в регистры процессора другой.
Выше я говорила, что планировщик может прервать активный поток в любой момент времени, что несколько упрощает модель. На самом же деле не планировщик прерывает поток, а текущая программа прерывается процессором в результате реакции на внешнее событие — аппаратное прерывание — и передает управление планировщику. Например, внешним событием является системный таймер, который отсчитывает квант времени, выделенный для работы активного потока. Если считать, что в системе существует ровно один источник прерывания, системный таймер, то карта процессорного времени будет выглядеть следующим образом:

Процедура переключения контекста для архитектуры x86:

 .global context_switch
context_switch:
 movl 0x04(%esp), %ecx /* Point ecx to previous registers */
 movl (%esp), %eax /* Get return address */
 movl %eax, CTX_X86_EIP(%ecx) /* Save it as eip */
 movl %ebx, CTX_X86_EBX(%ecx) /* Save ebx */
 movl %edi, CTX_X86_EDI(%ecx) /* Save edi */
 movl %esi, CTX_X86_ESI(%ecx) /* Save esi */
 movl %ebp, CTX_X86_EBP(%ecx) /* Save ebp */
 add $4, %esp /* Move esp in state corresponding to eip */
 movl %esp, CTX_X86_ESP(%ecx) /* Save esp */
 pushf /* Push flags */
 pop CTX_X86_EFLAGS(%ecx) /* ...and save them */

 movl 0x04(%esp), %ecx /* Point ecx to next registers */
 movl CTX_X86_EBX(%ecx), %ebx /* Restore ebx */
 movl CTX_X86_EDI(%ecx), %edi /* Restore edi */
 movl CTX_X86_ESP(%ecx), %esi /* Restore esp */
 movl CTX_X86_EBP(%ecx), %ebp /* Restore ebp */
 movl CTX_X86_ESP(%ecx), %esp /* Restore esp */
 push CTX_X86_EFLAGS(%ecx) /* Push saved flags */
 popf /* Restore flags */
 movl CTX_X86_EIP(%ecx), %eax /* Get eip */
 push %eax /* Restore it as return address */

 ret

Машина состояний потока

Мы обсудили важное отличие структуры потока в случае с вытесняющим планировщиком от случая с невытесняющим планировщиком — наличие контекста. Посмотрим, что происходит с потоком с момента его создания до завершения:

 

• Состояния init отвечает за то, что поток создан, но не добавлялся еще в очередь к планировщику, а exit говорит о том, что поток завершил свое исполнение, но еще не освободил выделенную ему память.
• Состояние run тоже должно быть очевидно — поток в таком состоянии исполняется на процессоре.
• Состояние ready же говорит о том, что поток не исполняется, но ждет, когда планировщик предоставит ему время, то есть находится в очереди планировщика.

Но этим не исчерпываются возможные состояния потока. Поток может отдать квант времени в ожидании какого-либо события, например, просто заснуть на некоторое время и по истечении этого времени продолжить выполнение с того места, где он заснул (например, обычный вызов sleep).
Таким образом, поток может находиться в разных состояниях (готов к выполнению, завершается, находиться в режиме ожидания и так далее), тогда как в случае с невытесняющим планировщиком достаточно было иметь флаг об активности той или иной задачи.

Вот так можно представить обобщенную машину состояний:

В этой схеме появилось новое состояние wait, которое говорит планировщику о том, что поток уснул, и пока он не проснется, процессорное время ему выделять не нужно.
Теперь рассмотрим поподробнее API управления потоком, а также углубим свои знания о состояниях потока.
 

Реализация состояний

Если посмотреть на схему состояний внимательнее, то можно увидеть, что состояния init и wait почти не отличаются: оба могут перейти только в состояние ready, то есть сказать планировщику, что они готовы получить свой квант времени. Таким образом состояние init избыточное.

Теперь посмотрим на состояние exit. У этого состояния есть свои тонкости. Оно выставляется планировщику в завершающей функции, о ней речь пойдет ниже. Завершение потока может проходить по двум сценариям: первый — поток завершает свою основную функцию и освобождает занятые им ресурсы, второй — другой поток берет на себя ответственность по освобождению ресурсов. Во втором случае поток видит, что другой поток освободит его ресурсы, сообщает ему о том, что завершился, и передает управление планировщику. В первом случае поток освобождает ресурсы и также передает управление планировщику. После того, как планировщик получил управление, поток никогда не должен возобновить работу. То есть в обоих случаях состояние exit имеет одно и то же значение — поток в этом состоянии не хочет получить новый квант времени, его не нужно помещать в очередь планировщика. Идейно это также ничем не отличается от состояния wait, так что можно не заводить отдельное состояние.

Таким образом, у нас остается три состояния. Мы будем хранить эти состояния в трех отдельных полях. Можно было бы хранить все в одном целочисленном поле, но для упрощения проверок и в силу особенности многопроцессорного случая, который здесь мы обсуждать не будем, было принято такое решение. Итак, состояния потока:
 

• active — запущен и исполняется на процессоре
• waiting — ожидает какого-то события. Кроме того заменяет собой состояния init и exit
• ready — находится под управлением планировщика, т.е. лежит в очереди готовых потоков в планировщике или запущен на процессоре. Это состояние несколько шире того ready, что мы видим на картинке. В большинстве случаев active и ready, а ready и waiting теоретически ортогональны, но есть специфичные переходные состояния, где эти правила нарушаются. Про эти случаи я расскажу ниже.

Создание

Создание потока включает в себя необходимую инициализацию (функция thread_init) и возможный запуск потока. При инициализации выделяется память для стека, задается контекст процессора, выставляются нужные флаги и прочие начальные значения. Поскольку при создании мы работаем с очередью готовых потоков, которую использует планировщик в произвольное время, мы должны заблокировать работу планировщика со структурой потока, пока вся структура не будет инициализирована полностью. После инициализации поток оказывается в состоянии waiting, которое, как мы помним, в том числе отвечает и за начальное состояние. После этого, в зависимости от переданных параметров, либо запускаем поток, либо нет. Функция запуска потока — это функция запуска/пробуждения в планировщике, она подробно описана ниже. Сейчас же скажем только, что эта функция помещает поток в очередь планировщика и меняет состояние waiting на ready.
Итак, код функции thread_create и thread_init:
 

struct thread *thread_create(unsigned int flags, void *(*run)(void *), void *arg) {
 int ret;
 struct thread *t;

//…

 /* below we are going work with thread instances and therefore we need to
 * lock the scheduler (disable scheduling) to prevent the structure being
 * corrupted
 */
 sched_lock();
 {
 /* allocate memory */
 if (!(t = thread_alloc())) {
 t = err_ptr(ENOMEM);
 goto out;
 }

 /* initialize internal thread structure */
 thread_init(t, flags, run, arg);

 //…

 }
out:
 sched_unlock();

 return t;
}

void thread_init(struct thread *t, unsigned int flags,
 void *(*run)(void *), void *arg) {
 sched_priority_t priority;

 assert(t);
 assert(run);
 assert(thread_stack_get(t));
 assert(thread_stack_get_size(t));

 t->id = id_counter++; /* setup thread ID */

 dlist_init(&t->thread_link); /* default unlink value */

 t->critical_count = __CRITICAL_COUNT(CRITICAL_SCHED_LOCK);
 t->siglock = 0;
 t->lock = SPIN_UNLOCKED;
 t->ready = false;
 t->active = false;
 t->waiting = true;
 t->state = TS_INIT;

 /* set executive function and arguments pointer */
 t->run = run;
 t->run_arg = arg;

 t->joining = NULL;

//...

 /* cpu context init */
 context_init(&t->context, true); /* setup default value of CPU registers */
 context_set_entry(&t->context, thread_trampoline);/*set entry (IP register*/
 /* setup stack pointer to the top of allocated memory
 * The structure of kernel thread stack follow:
 * +++++++++++++++ top
 * |
 * v
 * the thread structure
 * xxxxxxx
 * the end
 * +++++++++++++++ bottom (t->stack - allocated memory for the stack)
 */
 context_set_stack(&t->context,
 thread_stack_get(t) + thread_stack_get_size(t));

 sigstate_init(&t->sigstate);

 /* Initializes scheduler strategy data of the thread */
 runq_item_init(&t->sched_attr.runq_link);
 sched_affinity_init(t);
 sched_timing_init(t);
}

Режим ожидания

Поток может отдать свое время другому потоку по каким-либо причинам, например, вызвав функцию sleep. То есть текущий поток переходит из рабочего режима в режим ожидания. Если в случае с невытесняющим планировщиком мы просто ставили флаг активности, то здесь мы сохраним наш поток в другой очереди. Ждущий поток не кладется в очередь планировщика. Чтобы не потерять поток, он, как правило, сохраняется в специальную очередь. Например, при попытке захватить занятый мьютекс поток, перед тем как заснуть, помещает себя в очередь ждущих потоков мьютекса. И когда произойдет событие, которое ожидает поток, например, освобождение мьютекса, оно его разбудит и мы сможем вернуть поток обратно в очередь готовых. Подробнее про ожидание и подводные камни расскажем ниже, уже после того, как разберемся с кодом самого планировщика.
 

Завершение потока

Здесь поток оказывается в завершающем состоянии wait. Если поток выполнил функцию обработки и завершился естественным образом, необходимо освободить ресурсы. Про этот процесс я уже подробно описала, когда говорила об избыточности состояния exit. Посмотрим же теперь на реализацию этой функции.
 

void __attribute__((noreturn)) thread_exit(void *ret) {
 struct thread *current = thread_self();
 struct task *task = task_self();
 struct thread *joining;

 /* We can not free the main thread */
 if (task->main_thread == current) {
 /* We are last thread. */
 task_exit(ret);
 /* NOTREACHED */
 }

 sched_lock();

 current->waiting = true;
 current->state |= TS_EXITED;

 /* Wake up a joining thread (if any).
 * Note that joining and run_ret are both in a union. */
 joining = current->joining;
 if (joining) {
 current->run_ret = ret;
 sched_wakeup(joining);
 }

 if (current->state & TS_DETACHED)
 /* No one references this thread anymore. Time to delete it. */
 thread_delete(current);

 schedule();

 /* NOTREACHED */
 sched_unlock(); /* just to be honest */
 panic("Returning from thread_exit()");
}

Трамплин для вызова функции обработки

Мы уже не раз говорили, что, когда поток завершает исполнение, он должен освободить ресурсы. Вызывать функцию thread_exit самостоятельно не хочется — очень редко нужно завершить поток в исключительном порядке, а не естественным образом, после выполнения своей функции. Кроме того, нам нужно подготовить начальный контекст, что тоже делать каждый раз — излишне. Поэтому поток начинает не с той функции, что мы указали при создании, а с функции-обертки thread_trampoline. Она как раз служит для подготовки начального контекста и корректного завершения потока.
 

static void __attribute__((noreturn)) thread_trampoline(void) {
 struct thread *current = thread_self();
 void *res;

 assert(!critical_allows(CRITICAL_SCHED_LOCK), "0x%x", (uint32_t)__critical_count);

 sched_ack_switched();

 assert(!critical_inside(CRITICAL_SCHED_LOCK));

 /* execute user function handler */
 res = current->run(current->run_arg);
 thread_exit(res);
 /* NOTREACHED */
}

Резюме: описание структуры потока

Итак, для описания задачи в случае с вытесняющим планировщиком нам понадобится достаточно сложная структура. Она содержит в себе:

• информацию о регистрах процессора (контексте).
• информацию о состоянии задачи, готова ли она к выполнению или, например, ждет освобождения какого-либо ресурса.
• идентификатор. В случае с массивом это индекс в массиве, но если потоки могут добавляться и удаляться, то лучше использовать очередь, где идентификаторы и пригодятся.
• функцию старта и ее аргументы, возможно, даже и возвращаемый результат.
• адрес куска памяти, который выделен под стек, поскольку при выходе из потока его нужно освободить.