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

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

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

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

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

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

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

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

    И вот теперь, когда мы всё ещё находимся внутри функции обслуживания прерывания, но собственно прерывания обслужили и должным образом уведомили контроллер прерываний об этом (и, конечно, сами прерывания глобально запрещены), мы можем проверить, нет ли запроса 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;
    


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

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

    Уф. Наверное, на сегодня — всё. Продолжение здесь.

    Комментарии 20

      0
      А зачем хранить примитивы синхронизации на которых нить заснула?
      Если я правильно понимаю, то после того как ее пробудили она продолжит выполнение в каком то участке кода, у которого есть информация об этом объекте )например хранится на стеке)
        0
        В данном случае видимо речь о том, что нить при многопоточном выполнении «ждет» сигнала на продолжение, шедулер даже не будет ее будить если примитив все еще залочен (имею ввиду не поступил сигнал от другого потока). Зачем будить нить, если она все равно не будет работать, а восстановление стека, регистров и всего остального состояние нити — затратно.
          +2
          Если я правильно понимаю принцип работы, то сигнал поступает с помощью
          queue_chain_t chain; // used by mutex/cond code to chain waiting threads

          То есть у каждого объекта синхронизации есть очередь заснувших на нем потоков. Приведенная переменная является элементом этой очереди. Когда объект разблокируется, он будит (посылает сигнал) эту очередь (или сам выбирает следующий поток для побудки), а эти переменные нужны вероятно для других целей.
            +1
            Совершенно верно.
          +1
          Только для отладки — отображение, на чём нить заснула.
          0
          Есть ли причина, по которой поток раз за разом называется нитью? Если экскурс — общетеоритический, почему не традиционное «поток»? В Windows NT, например, поток и нить — разные сущности.
            +2
            Причин-то много можно придумать. Слово поток в системном программировании часто используют в смысле stream. Пример, multiple threads accessing a message stream.
              0
              Это не создаст путаницы даже при употреблении рядом, потому что понятия относятся к разным областям, stream скорее к IO или IPC.
              0
              В Windows NT, например, поток и нить — разные сущности.

              Если Вы про Thread и Fiber, то во многих книгах это нить и волокно. А поток и нить все же всегда об одном.
              P.S. Тема холиварная, сам лично предпочитаю сленговый «трэд».
                0
                Именно про них. Ни разу не видел такого перевода, встречал только thread и fiber как поток и нить соответственно. Перевод fiber как волокно — откровенно неудачный, просто взято словарное понятие, так мог перевести переводчик «в общем», не понимающий сути текста. Слово волокно означает нить именно в физическом смысле, как волокно из которого соткана ткань. Слово нить же имеет и другой смысл, как «нить повествования» и т.д.
                Программирование у нас многопоточное же, а не многонитевое, в конце концов.

                Словарь по ВТ дает перевод thread как поток (поток выполнения).
                  +1
                  Я лишь хотел заметить, что поток и нить никогда не являются разными понятиями в переводах, а если и были прецеденты, то это неправильно. Как уже заметил предыдущий оратор (я), тема холиварная.
                  P.S. В английском довольно логично, что волокно это часть нити, да и в русском по смыслу ок, если не выдумывать какие-то «нити повествования».
                    0
                    Я лишь хотел заметить, что поток и нить никогда не являются разными понятиями в переводах, а если и были прецеденты, то это неправильно

                    Как раз напротив. Эти понятия бывают разными по смыслу, и это логично. Иначе придется вставлять некорректное «волокно».

                    да и в русском по смыслу ок, если не выдумывать какие-то «нити повествования».

                    Не ок, нет никакого выдумывания. Языки разные, слова разные, логика языков разная. Перевод — не механический процесс. Весь смысл в том, что у нас есть поток или нить выполнения. Волокно — это совсем другой объект, чисто материальный, в отличие от нити (не в смысле нитки). Это неправильно выбранное слово.
                    Вы можете уловить нить повествования? А волокно повествования?
                    И да, опять же: «программирование у нас многопоточное, а не многонитевое, в конце концов».
                      +1
                      Вы же поняли, о чём речь? Ну и слава богу. Я, право, совсем не люблю споры о терминологии. Смысла нет. Если вы считаете, что другой термин лучше — назовите его в комментариях. Читатели увидят и обрадуются.
                        0
                        Смысл есть. Новояз — зло, вот и все, что я пытаюсь сказать. Особенно для устоявшихся терминов. Можно табуретку называть… не знаю… «арбузом» и не спорить о терминологии. Можно не пользоваться метрической системой и выпускать болты на 6.27мм — ведь болт же, всем это понятно. Унификация — великое дело; унификация терминологии позволяет всем понимать текст однозначно. Термин execution thread (сокращенно thread) переводится как поток (исполнения) уже лет 40.

                        Не принимайте всерьез, не собираюсь разводить срач; просто очень раздражает неверный перевод и использование некорректных англицизмов. Вроде «дигитальный-цифровой» или «софистицированный-утонченный», «экспертиза-мастерство, опыт и пр», «преемптивный-вытесняющий».
                          +1
                          Я этим делом тридцать лет занимаюсь. Вы уверены, что именно моя терминология — новояз? :)

                          И регулярно общаюсь с (русскоязычными) системщиками во многих конторах в России и за рубежом. Включая людей из МС и Интел. Я ни разу не наблюдал ни у кого ни тени сомнения относительно смысла термина «нить». Я даже не знаю, как его понять-то неоднозначно.

                          Он Вам просто не нравится. А мне просто не нравится (омонимичный) термин «поток», который куда более io stream, чем thread. И то, что большинство людей называют копир ксероксом не делает этот «термин» более верным.

                          Это разговор о вкусах. И, ещё раз повторю — в нём был бы хоть какой смысл, если бы термин «нить» был бы хоть на полграна омонимичен.

                          Забейте. Единственное важное свойство буквенного лейбла, приклеенного к точке в семантическом пространстве — понятность. Если его поняли — всё хорошо.
                            0
                            Я этим делом тридцать лет занимаюсь. Вы уверены, что именно моя терминология — новояз? :)

                            Устоявшийся термин — поток, многопоточное программирование. Точка.

                            Включая людей из МС и Интел. Я ни разу не наблюдал ни у кого ни тени сомнения относительно смысла термина «нить». Я даже не знаю, как его понять-то неоднозначно.

                            Элементарно: вопрос «чем отличается thread от fiber (поток от, например, нити)».

                            Он Вам просто не нравится

                            Нет. Мне не нравится использование нестандартной терминологии.

                            А мне просто не нравится (омонимичный) термин «поток», который куда более io stream, чем thread.

                            Разговор об омонимичности «потока» не имеет смысла, потому что мы обсуждаем контекст переключения задач.

                            И то, что большинство людей называют копир ксероксом не делает этот «термин» более верным.

                            Не надо передергивать: речь не идет о верности, я говорил об устоявшемся термине. Вы же не будете спорить с тем, что «ксерокс» или «ксерокопия» — устоявшиеся термины? Покажите, пожалуйста, какой-нибудь серьезный труд (м.б. монографию), с теоритической составляющей, где использовался бы термин «нить» для execution thread'а. Я уверен, что такие есть, но я таких ни разу не видел, мне интересно.

                            в нём был бы хоть какой смысл, если бы термин «нить» был бы хоть на полграна омонимичен.

                            В Windows world нить, иногда волокно, используются для легковесных потоков (кооп.) fiber.

                            Забейте. Единственное важное свойство буквенного лейбла, приклеенного к точке в семантическом пространстве — понятность. Если его поняли — всё хорошо.

                            Так вот не было ее, понятности. Право слово, я впервые увидел «нить» вместо «потока» в ваших статьях (замечательных, тут вбез вопросов). Отсюда и родился вопрос. Возможно, это моя неосведомленность, связанная с преимущественным использованием англоязычных источников.

                            Заметьте, что тред начался с вопроса «есть ли причина». Вам стоило просто сказать «мне так нравится» и все. Я спросил на тот случай, если в ваших статьях термин «поток» по каким-то причинам однозначно зарезервирован за чем-то другим и это может вызвать путаницу при совместном употреблении. Однако это вылилось в утомительный излишний холивор.
                              +1
                              ок. мне так нравится. :)
                              давайте тратить байты на обсуждение сути, а не фантика.
                                0
                                Конечно. Поймите — мне неинтересн спор ради спора. Вы написали замечательные статьи.
                                Просто ради эксперимента — представьте себя новичком, зайдите в поиск хабра и наберите «вытесняющий». Ну, ищет молодой человек хорошие статьи про вытесняющую многозадачность. И о чудо — вашей статьи там нет! Если же он наберет «преемптивный», то получит 5 статей: 4 ваших и еще 1.
                                Поиск по «нить» и «поток» вызовет опять раздрай: половина результатов для пассажей вида «какой-нить», «поток» дает больше результатов «в масть», хоть и разбавлен потоками данных и пр.
                                Сама двойственность уже тут обсуждалась, тут в комментариях, например: https://habrahabr.ru/post/40275/;

                                Обидно, что информационное поле расползается. Для вас важна статья, как таковая, и обсуждение ваших идей. Я смотрю с т.з. доступности информации. Это не претензия, просто мысли вслух, закончим на этом.
              0
              А в чём ненормальность такого программирования?
              На некоторых простых микроконтроллерах вытесняющую многозадачность по другому и не реализовать (доводилось такое делать для 80186).
                0
                Да её и нигде по другому не реализовать, насколько я знаю. :) Наверное, я неверно понимаю «ненормальное» — этим занимаются единицы людей на планете, наверное, поэтому я не считаю его особенно нормальным. :)

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое