Одноядерный процессор в любую конкретную наносекунду исполняет ровно одну инструкцию одного потока. Тем не менее пользователь Windows десятилетиями слушал музыку, печатал текст и скачивал файл одновременно, и система не выглядела занятой чем-то одним. Эта договорённость между железом, планировщиком и человеческим восприятием держится на таймерных прерываниях, переключениях контекста, очередях готовых потоков и аппаратных помощниках вроде DMA. Ниже разобраны механизмы, которые создают эту иллюзию, и границы, за которыми иллюзия начинает трещать.
Кооперативная многозадачность Windows 3.x и вытесняющая модель Windows 9x против NT
Первая массовая многозадачность на PC была кооперативной. В Windows 3.x весь 16-битный мир жил в одном адресном пространстве, и планировщик не мог отнять процессор у приложения силой. Программа должна была сама вызвать GetMessage, WaitMessage или PeekMessage и тем самым вернуть управление диспетчеру задач. Пока приложение крутилось в длинном цикле вычислений без цикла выборки сообщений, вся система замерзала: не перерисовывались окна, не двигался курсор в других программах, иконка не отзывалась. Зависшее приложение означало зависшую сессию, потому что отобрать управление было некому.
Windows 9x добавила вытесняющее планирование, но лишь частично: 32-битные потоки получили кванты и таймерные прерывания, однако весь 16-битный слой Win16 по-прежнему защищался одним глобальным мьютексом Win16Mutex. Шестнадцатибитное приложение, захватившее этот мьютекс и зависшее внутри кода USER или GDI, по-прежнему останавливало систему, и ради совместимости от этого архитектурного наследия не смогли избавиться. Вытеснение работало между легитимными Win32-потоками, но не между поколениями кода.
Windows NT, спроектированная Дэвидом Катлером с чистого листа, сделала вытеснение принципом без исключений. Любой поток в любой момент может быть прерван по таймеру или по приходу готового потока с более высоким приоритетом. Никакого общего мьютекса между приложениями нет, каждый процесс живёт в своём виртуальном адресном пространстве, и зависшее приложение для системы просто поток, чей квант истёк. Разница философская: кооперативная модель доверяет приложениям, вытесняющая модель не доверяет никому.
Таймер 8253 на 18.2 Гц, кванты и переключение контекста
У классического IBM PC системный таймер Intel 8253 был подключён к каналу IRQ0 контроллера прерываний и программировался на частоту примерно 18.2065 Гц, то есть один тик каждые 55 миллисекунд. Число выбрано не случайно: чип тактировался от делителя 65536 при опорной частоте 1.19318 МГц, и это был максимум. На каждый тик процессор получал прерывание, выполнял обработчик, обновлял часы DOS и отдавал шанс планировщику сменить исполняемый поток. Современные Windows работают на гораздо более коротких интервалах, от 0.5 до 15.6 миллисекунд на тик, а server-side вариации меняют и кванты: на клиентских сборках базовый квант около двух тиков, на серверных порядка 12 тиков, чтобы снизить накладные расходы на переключения для длинных рабочих нагрузок.
Само переключение контекста состоит из фиксированного набора шагов. Планировщик сохраняет состояние текущего потока: регистры общего назначения, указатель стека, указатель инструкций, регистры флагов, при необходимости состояние блока FPU и SSE и селекторы сегментов. Вся эта информация помещается в структуру контекста, в NT она называется CONTEXT и хранится вместе с объектом потока KTHREAD. Затем планировщик проходит очередь готовых потоков, выбирает следующий, при смене процесса переключает каталог страниц регистра CR3, тем самым инвалидируя TLB, загружает контекст нового потока и выполняет возврат из прерывания, который поднимает его на ту самую точку, где он когда-то был вытеснен.
В x86 есть и аппаратный механизм: Task State Segment, TSS, структура, в которую Intel-совместимый процессор умеет дамповать весь регистровый контекст при смене задачи одной инструкцией JMP TSS или CALL TSS. На практике Windows и Linux от аппаратного переключения отказались: оно медленнее ручного сохранения, не даёт контролировать, что именно сохранять, и TSS оставлен в режиме минимального присутствия, по одному сегменту на процессор, только для корректной смены стека при переходе из user mode в kernel mode. Программное переключение контекста стоит в среднем десятки микросекунд с учётом промахов TLB и кэша, а происходят такие переключения тысячи раз в секунду. Грубый счёт показывает, что несколько процентов процессорного времени одноядерной машины уходят на саму смену задач, и это ещё без учёта косвенных потерь на замусоривание кэша L1/L2 при миграции потоков по горячим структурам данных.
Почему музыка и текст ощущаются одновременными
Иллюзия параллелизма складывается из огромного несовпадения масштабов времени. Планировщик оперирует интервалами в десятки миллисекунд, а переключения контекста занимают микросекунды. Реакция человека на зрительный стимул начинается от 150 миллисекунд, порог восприятия мерцания порядка 16 миллисекунд, а синхронность звука и видео субъективно не замечается даже при сдвигах в 45-90 миллисекунд в зависимости от направления. Если машина успевает за одну секунду прорисовать 60 кадров оболочки, отдать декодеру MP3 две сотни коротких квантов и ещё оставить время Word на перерисовку каретки, человек все эти потоки честно воспринимает как одновременные. Планировщик может заменить 30 потоков между двумя нажатиями клавиш, и пользователь этого не увидит, потому что человеческое восприятие ниже миллисекунд не решает.
Поэтому квант выбирается в диапазоне, где он с одной стороны короче порога заметности для интерактивных задач, а с другой достаточно длинный, чтобы амортизировать стоимость переключения. Слишком короткий квант растратит бюджет на оверхед, и курсор начнёт дёргаться от того, что система тратит 20 процентов времени на то, чтобы менять потоки местами. Слишком длинный квант сделает отзывчивость вязкой. Windows балансирует это разделением на клиентские и серверные профили планирования, где серверные предпочитают пропускную способность и длинные кванты, а клиентские постоянно смещены в сторону отзывчивости.
Приоритеты 0-31, foreground boost и очередь готовых
В Windows планировщик выбирает следующий поток по уровню приоритета от 0 до 31, где уровни 0-15 зарезервированы под динамический диапазон обычных приложений, а уровни 16-31 отданы потокам реального времени, включая критические системные. Нити в user mode почти всегда получают приоритет, вычисленный из сочетания класса приоритета процесса (Idle, Below Normal, Normal, Above Normal, High, Realtime) и относительного приоритета потока (Lowest, Below Normal, Normal, Above Normal, Highest, Time Critical, Idle). Главный закон простой: пока в очереди готовых есть хоть один поток с более высоким приоритетом, поток с более низким приоритетом не получит процессор вообще.
Чтобы интерактивные приложения чувствовались шустрыми, NT вводит foreground boost. Потоки процесса, владеющего активным окном, получают увеличенный квант, в клиентских сборках обычно втрое, с 2 до 6 тиков по умолчанию. Нити внутри того же процесса ловят фоновые коррекции приоритета, когда поток выходит из ожидания на ввод-вывод, на семафоре или на событии ввода: кратковременный буст на 1-2 уровня помогает GUI быстро среагировать на клик и сразу же вернуться к обычному режиму. Именно связка коротких очередей ожидания и этих мелких бустов делает так, что на одиночном ядре открытое окно ощущается шустрым, даже если рядом идёт компиляция проекта.
Базовая справедливость планировщика опирается на понятие готовых потоков. Поток бывает исполняющимся, ожидающим и готовым. Нить в состоянии ready стоит в очереди Dispatcher Ready List и ждёт выбора. В каждый момент времени на одноядерной машине исполняется одна нить, всё остальное либо ждёт события, либо стоит в очереди. Никакой параллельности нет, есть лишь быстрая карусель.
Голодание, инверсия приоритетов и Mars Pathfinder 1997
Небесконечный приоритетный диспетчер честно исполняет свой контракт, но при этом легко допускает голодание: поток с низким приоритетом может вообще никогда не получить процессор, если постоянный поток более приоритетных задач заполняет процессор. Windows смягчает это специальным механизмом: когда поток сидит в очереди ready дольше примерно трёх секунд, функция балансировки даёт ему аварийный буст до уровня 15 и выделяет удвоенный квант, а потом возвращает приоритет на место.
Инверсия приоритетов, обратная картина, когда высокоприоритетный поток вынужден ждать низкоприоритетный, потому что тот удерживает общий ресурс. Классический сценарий: высокий поток H ждёт мьютекс, который держит низкий поток L, а средний поток M постоянно вытесняет L под нулём, и в результате H фактически исполняется с приоритетом M. Mars Pathfinder столкнулся с этим прямым текстом в июле 1997 года. Основной высокоприоритетный поток управления шиной bc_sched периодически зависал на мьютексе, который держал низкоприоритетный поток ASI/MET, передающий данные о погоде. Среднеприоритетный коммуникационный поток этого не позволял L закончить работу до дедлайна, watchdog срабатывал, и роутер уходил в полный сброс системы. Телеметрия на Землю терялась. Инженеры JPL в лабораторной копии софта под VxWorks отладили ситуацию за пару суток, поняли, что в настройках мьютекса не включено наследование приоритетов (priority inheritance), залили на аппарат в космос патч, включивший наследование, и сбросы прекратились. Этот инцидент прочно вписал инверсию приоритетов в учебники реального времени: любая реализация планирования по приоритетам на одном ядре должна иметь стратегию против инверсии, будь то наследование приоритета или потолок приоритета.
DMA, аппаратные прерывания и конвейеры как переходный этап к гиперпоточности
В реальном компьютере процессор не одинок, и значительная часть ощущения параллелизма обеспечивается не планировщиком, а пассивным параллелизмом аппаратных контроллеров. Звуковая карта играет не потому, что процессор постоянно выдаёт в неё очередной семпл. Поток декодирует кусок MP3, копирует его в кольцевой буфер в памяти, и контроллер DMA начинает самостоятельно перекачивать байты из памяти в звуковой кодек, не занимая процессор. По заполнению буфера или по исчерпании половины он поднимает прерывание, драйвер получает управление, процессор на десятки микросекунд дозаполняет буфер и возвращается к другим потокам. Пользователь слышит непрерывный звук, в реальности же процессор 98 процентов времени музыкой не занят. Дисковые контроллеры, сетевые карты, USB, GPU-командные процессоры построены точно так же: центральный процессор формирует пачку работы, отдаёт её аппаратуре и получает прерывание по завершении. Это последний, но может быть самый практичный источник подлинного параллелизма на одноядерной машине.
Дальше началась микроархитектурная эскалация. Пятистадийный конвейер классического RISC, потом суперскалярные ядра с несколькими конвейерами, предсказание переходов, переименование регистров и внеочередное исполнение: всё это способы выжать из инструкционного уровня параллелизм, не добавляя ядер. Hyper-Threading, реализованный в Pentium 4, сделал следующий шаг и раздвоил архитектурное состояние: два набора регистров, две программные точки исполнения, но один физический конвейер и один набор исполнительных блоков. Когда один логический поток встал на промахе кэша, на прерывании ввода-вывода или на длинной цепочке зависимостей, второй логический поток занимал простаивающие исполнительные порты. По сути Hyper-Threading это тот же механизм циклического переключения задач, только внутри такта и между двумя виртуальными процессорами, а не между потоками операционной системы. Это был удобный переходный этап, потому что экономически возвращал 10-30 процентов производительности за гораздо более дешёвое усложнение кристалла, чем втычивание второго полноценного ядра. Когда технология позволила удвоить само ядро, наступление многоядерности просто подняло всю матрёшку на уровень выше: иллюзия многозадачности перешла на слой ниже, но её принципы остались теми же - очереди готовых, кванты, приоритеты, DMA и передоверие параллелизма любой аппаратуре, которая умеет работать сама.