Преемптивность: как отнять процессор

Эта статья не имеет смысла без предыдущей, в которой описывались основные механизмы переключения контекстов в многозадачной ОС.

Здесь я расскажу, как кооперативная многозадачность превращается во враждебную преемптивную.

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

Но, как обычно, есть нюансы. См. код для интела.

Сам «отъём» процессора делается как в рамках обычного хардверного прерывания, обычно — по таймеру, так и в рамках «софтверного» прерывания — которое, собственно, такое же прерывание, но вызванное специальной инструкцией процессора. Такой способ переключения контекста нужен, если мы (например, в рамках примитива синхронизации) явно останавливаем нить и не хотим ждать, пока прилетит таймерное прерывание.
Во-первых, перед тем как заниматься отъёмом процессора у бедных нитей, нужно обслужить само прерывание. Процессор/контроллер прерываний «знает», что прерывание началось, и его нужно «успокоить», сообщив, что мы завершили обслуживание, до того, как мы переключились в другую нить. Иначе состояние контроллера прерываний может оказаться очень странным и система перестанет вразумительно функционировать. Да и сам хендлер прерывания не будет счастлив, если перед его исполнением пару секунд поработают другие нити.

Поэтому сначала обслужим собственно прерывание. Потом убедимся, что оно не было вложенным — что мы не прервали обслуживание другого прерывания, которое тоже должно бы завершиться.

И вот теперь, когда мы всё ещё находимся внутри функции обслуживания прерывания, но собственно прерывания обслужили и должным образом уведомили контроллер прерываний об этом (и, конечно, сами прерывания глобально запрещены), мы можем проверить, нет ли запроса soft irq, и если да — обслужить его.

Тут надо понимать, что в старших битах переменной irq_nest лежит флаг запрета обслуживания софверных прерываний и флаг отсутствия запроса софтверного прерывания. То есть если она равна нулю, то, одновременно, равна нулю вложенность запросов хардверных прерываний, нет запрета на софтверное прерывание и есть запрос на софтверное прерывание.

    if(irq_nest)
        return;

    // Now for soft IRQs
    irq_nest = SOFT_IRQ_DISABLED|SOFT_IRQ_NOT_PENDING;
    hal_softirq_dispatcher(ts);
    ENABLE_SOFT_IRQ();

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

При инициализации нитей ядро регистрирует хендлер софтверного прерывания

    hal_set_softirq_handler( SOFT_IRQ_THREADS, (void *)phantom_scheduler_soft_interrupt, 0 );

Этот хендлер, если не считать всяких проверок, сводится к вызову phantom_thread_switch (), то есть просто приводит к переключению на очередную нить.

Остались два момента. Первый — как явно «отдать» процессор. Например, когда мы пытаемся захватить уже запертый мьютекс — нить надо остановить.

Для этого мы взводим запрос софтверного прерывания и запрашиваем (любое, но лучше — редко используемое) хардверное прерывание.

void
phantom_scheduler_request_soft_irq()
{
    hal_request_softirq(SOFT_IRQ_THREADS);
    __asm __volatile("int $15");
}

Как сказано выше, это приведёт к тому, что функция phantom_thread_switch будет вызвана из контекста софтверного прерывания.

Второй:, а кто запросит софтверное прерывание, чтобы завершить работающую в настоящий момент нить по окончании выделенного ей слота времени процессора?

Для этого есть вот такой запрос:

void
phantom_scheduler_schedule_soft_irq()
{
    hal_request_softirq(SOFT_IRQ_THREADS);
}

Он исполняется вот когда. Внутри таймерного прерывания вызывается специальная функция:

// Called from timer interrupt 100 times per sec.
void phantom_scheduler_time_interrupt(void)
{
    if(GET_CURRENT_THREAD()->priority & THREAD_PRIO_MOD_REALTIME)
        return; // Realtime thread will run until it blocks or reschedule requested

    if( (GET_CURRENT_THREAD()->ticks_left--) <= 0 )
        phantom_scheduler_request_reschedule();
}

Как нетрудно видеть, она декрементирует переменную нити ticks_left, и если досчитала до нуля — запрашивает переключение нити.

Саму переменную ticks_left выставляет шедулер, когда выбирает нить для запуска — он прописывает в эту переменную число 10 мсек интервалов, которые нить отработает (если до того не захочет остановиться сама).

Время работы шедулер может выставлять фиксированное (обслуживая приоритеты через частоту постановки нити на процессор) или учитывать приоритет (давая более высокоприоритетным нитям более длинные интервалы).

К этому надо добавить, что вызвать phantom_scheduler_request_reschedule () может всякий, кто счёл, что настала пора определиться, кому сейчас встать на процессор.

Как пример, такое может быть уместно, если текущая нить разблокировала примитив синхронизации, на котором была заблокирована нить с высоким (тем более — realtime) приоритетом.

Сам по себе этот вызов только выставляет флаг — реальное переключение будет только в конце обслуживания прерываний, как написано выше.

Для полноты картины рассмотрим структуру описания нити (struct phantom_thread) в деталях.

Поле cpu содержит специфичные для данной архитектуры поля, в которые сохраняется состояние процессора при остановке нити. cpu_id — номер процессора, на котором нить запускалась в последний раз или работает сейчас. tid — просто идентификатор нити. owner применяется объектной средой фантома, чтобы привязать сюда объект, описывающий нить на прикладном уровне. Если нить обслуживает подсистему совместимости с Юниксом — pid хранит номер процесса Юникса, к которому нить принадлежит. Имя — исключительно для отладки.

    /** NB! Exactly first! Accessed from asm. */
    cpu_state_save_t            cpu;

    //! on which CPU this thread is dispatched now
    int                         cpu_id; 

    int                         tid;

    //! phantom thread ref, etc
    void *                      owner;

    //! if this thread runs Unix simulation process - here is it
    pid_t                       pid;

    const char *                name;

ctty — буфер stdin для нити, применяется для связи с графической подсистемой. stack/kstack — виртуальный и физический адрес сегмента стека, соответственно для user и kernel mode. start_func и start_func_arg — точка входа в функцию («main») нити и аргумент этой функции.

    wtty_t *                    ctty; 

    void *                      stack;
    physaddr_t             stack_pa;
    size_t                      stack_size;

    void *                      kstack;
    physaddr_t              kstack_pa;
    size_t                      kstack_size;
    void *                      kstack_top; // What to load to ESP

    void *                      start_func_arg;
    void                        (*start_func)(void *);

sleep_flags — признаки засыпания нити по той или иной причине. Если не ноль — нить запускать нельзя (ждёт мьютекса, таймера, не родилась, умерла и т.п.). thread_flags — различные признаки нити: нить обслуживает виртуальную машину Фантом, у нити случился таймаут примитива синхронизации и т.п.

waitcond/mutex/sem — нить спит на этом примитиве, ждёт его освобождения. ownmutex — эта нить заперла этот mutex, если помрёт — надо освободить. (Для семафора всё, увы, неочевидно.)

sleep_event — применяется если примитив синхронизации заперт с таймаутом — таймерная подсистема ядра хранит здесь состояние таймерного запроса.

chain — применяется при постановке нити в очередь если одного примитива синхронизации ждёт несколько нитей.

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

    u_int32_t                   thread_flags; // THREAD_FLAG_xxx

    /** if this field is zero, thread is ok to run. */
    u_int32_t                   sleep_flags; //THREAD_SLEEP_xxx

    hal_cond_t *                waitcond;
    hal_mutex_t *               waitmutex;
    hal_mutex_t *               ownmutex;
    hal_sem_t *                 waitsem;

    queue_chain_t               chain; // used by mutex/cond code to chain waiting threads
    queue_chain_t               kill_chain; // used kill code to chain threads to kill

    //* Used to wake with timer, see hal_sleep_msec
    timedcall_t                 sleep_event; 

snap_lock — нить находится в состоянии, в котором нельзя делать snapshot.

preemption_disabled — нить нельзя снимать с процессора. Вообще-то смысла в этой штуке почти нет, особенно в SMP среде.

death_handler — будет вызван, если нить померла. atexit.

trap_handler — это аналог тому, что в user mode называется сигналы — функция вызывается, если нить привела к эксепшну процессора.

    int                         snap_lock; // nonzero = can't begin a snapshot
    int                         preemption_disabled;

    //! void (*handler)( phantom_thread_t * )
    void *                      death_handler; // func to call if thread is killed

    //! Func to call on trap (a la unix signals), returns nonzero if can't handle
    int                         (*trap_handler)( int sig_no, struct trap_state *ts );

Остальное — машинерия шедулера. Тут всё просто:

priority содержит приоритет нити (вместе с классом — realtime, normal, idle)

ticks_left — сколько «тиков» (10 мсек интервалов) нить отработает на процессоре

runq_chain — если нить готова к исполнению, но не исполняется, то она присутствует в очереди на исполнение.

sw_unlock — содержит указатель на спинлок, который будет отперт после снятия нити с процессора, используется в реализации примитивов синхронизации.

    u_int32_t                   priority;

    /**
     * How many (100HZ) ticks this thread can be on CPU before resched.
     * NB! Signed, so that underrun is not a problem.
    **/
    int32_t                     ticks_left;

    /** Used by runq only. Is not 0 if on runq. */
    queue_chain_t               runq_chain;

    /** Will be unlocked just after this thread is switched off CPU */
    hal_spinlock_t              *sw_unlock;

Последний бантик, который надо бы добавить к картине мира: в системе всегда есть нить (несколько нитей, по числу процессоров), которая ставится на процессор, если шедулер не нашёл ни одной достойной работы нити.

Эта нить не делает ничего — она исполняет инструкцию процессора, которая останавливает процессор до получения прерывания, и считает время исполнения себя. Время её исполнения в секунду позволяет получить процент загрузки процессора, а остановка процессора экономит электричество и тепло.

Уф. Наверное, на сегодня — всё.

© Habrahabr.ru