Как работает многозадачность

В ответ на Как вы считаете, как работает многозадачность на 80386?. По моему мнению, ни один из предлагавшихся вариантов ответа не верен, а верен такой:

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

Шаги этого процесса элегантны и поучительны.

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

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

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

При переключении процессов, дополнительно перегружаются регистры виртуальной памяти.

Множество деталей в этом изложении опущено (например, приоритет прерываний), их можно найти в соответствующей литературе.

Советская терминология отличалась от американской. Поток назывался процессом, а процесс — задачей, в соответствии с работой Дейкстры Взаимодействие последовательных процессов.

Источник

Технологии многопоточности процессоров: принцип работы и сферы применения

Содержание

Содержание

Физические ядра, логические ядра, технологии многопоточности — все это разрабатывалось инженерами для увеличения производительности компьютерного железа, требования к которому постоянно растут. Программы и игры требуют все больше ресурсов. Как же производители процессоров увеличивают мощность своих детищ? Процессор является «сердцем» компьютера и выполняет вычисления, необходимые для работы софта. Модели CPU отличаются между собой даже в рамках одного семейства. Например, Intel Core i7 отличается от i5 технологией многопоточности под названием «Hyper-Threading», о которой далее пойдет речь (Core i3, i9, и некоторые Pentium также обладают данной технологией).

Принцип работы процессорных ядер и многопоточности

В современных операционных системах одновременно работает множество процессов.
Нагрузка от операционной системы на процессор идет по так называемому конвейеру, на который «выкладываются» нужные задачи для ядра. В качестве примера возьмем одно ядро процессора на частоте 4 ГГц с одним ALU (арифметико-логическое устройство) и одним FPU (математический сопроцеесор). Частота в 4 ГГц означает, что ядро исполняет 4 миллиарда тактов в секунду. К ядру по конвейеру поступают задачи, требующие исполнительной мощности, на которые тратится процессорное время.

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

Данный конвейер можно представить, как настоящую сборочную линию на заводе — рабочий (ядро) выполняет работу, поступающую к нему на ленту. И если необходимо взять нужный инструмент, работник отходит, оставляя конвейер простаивать без работы. То есть, исполняемая задача прерывается. Инструментом, за которым пошел рабочий, в данном случае является информация из оперативной памяти или же L3 кэша. Поскольку L1 и L2 кэш намного быстрее, чем любая другая память в компьютере, работа с вычислениями теряет в скорости.

На конвейере с одним потоком не могут выполняться одновременно несколько процессов. Ядро постоянно прерывает выполнение одной операции для другой, более приоритетной. Если появятся две одинаково приоритетные задачи, одна из них обязательно будет остановлена, ведь ядро не сможет работать над ними одновременно. И чем больше поступает задач одновременно, тем больше прерываний происходит.

Способы увеличения производительности процессоров

Разгон

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

Увеличение количества потоков на ядро

В процессорах Intel данная технология носит название Hyper-Threading, а в процессорах от Amd — SMT. Производители добавляют еще один регистр для работы со вторым конвейером. Пока один поток простаивает, ожидая нужные данные, свободная вычислительная мощность может быть использована вторым потоком. На кристалл же добавлен еще один контроллер прерываний и набор регистров.

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

Стоит учитывать, что логический поток это не второе ядро, как может показаться с первого взгляда. Это лишь дополнительная «линия производства», чтобы более эффективно использовать доступную мощность. Из минусов технологии Hyper-Threading или SMT можно выделить увеличение тепловыделения, недостаток кэша (кэш на два потока по-прежнему общий), и проблемы с оптимизацией некоторых программ или игр, не способных отличать настоящее ядро от логического потока.

Именно по этой причине процессоры серии i7 «горячее» и имеют больше кэша по сравнению с i5. Использование технологии многопоточности может принести примерно до 30 % прироста производительности. Все это применимо как к Intel Hyper-Threading, так и к AMD SMT, поскольку технологии во многом схожи. Может возникнуть вопрос: «Если можно добавить второй поток, то почему бы не добавить третий и четвертый?» Это реализуемо, но не имеет смысла, поскольку кэш одного ядра достаточно мал для большего количества потоков и прироста производительности практически не будет.

Увеличение количества ядер

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

Сферы применения многопоточных процессоров

С развитием компьютерных технологий перечень программ, использующих многопоточность, неуклонно растет. Это дает огромный простор разработчикам для создания нового софта и игр. Например, сейчас каждый современный triple-A проект оптимизирован для многопоточных процессоров, что позволяет наслаждаться игрой, получая высокий уровень fps на многоядерном CPU.

Еще больше распространены многоядерные системы в среде разработчиков. Программы для 3D-моделирования, монтажа видео и создания музыки требуют параллельного выполнения большого количества задач, с чем хорошо справляются системы с Hyper-Threading или SMT. В операционных системах мощность одного потока может тратиться на фоновые задачи (Skype, браузер, мессенджер), в то время как остальные задействуются для тяжелой игры или программы.

Но далеко не всегда увеличение количества потоков означает увеличение общей производительности. Почему же SMT процессоры порой уступают немногопоточным собратьям? Дело в программной поддержке. Иногда плохо оптимизированные программы не могут отличать логический поток от настоящего ядра, из-за чего на одно ядро может попасть две тяжелых задачи и замедлить работу. Тем не менее, подобные технологии имеют огромный потенциал, главное — грамотно реализовать его на программном уровне.

Источник

МНОГОЗАДАЧНОСТЬ И ПРОЦЕССОРЫ

Кооперативная и вытесняющая многозадачность

Многозадачность, multitasking — свойство операционной системы или среды программирования, обеспечивать возможность параллельной (или псевдопараллельной) обработки нескольких процессов. Истинная многозадачность операционной системы возможна только в распределенных вычислительных системах.

Примитивные многозадачные среды обеспечивают чистое “разделение ресурсов”, когда за каждой задачей закрепляется определённый участок памяти, и задача активизируется в строго определённые интервалы времени.

Более развитые многозадачные системы проводят распределение ресурсов динамически, когда задача стартует в памяти или покидает память в зависимости от её приоритета и от стратегии системы. Такая многозадачная среда обладает следующими особенностями:

Типы псевдопараллельной многозадачности

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

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

Кооперативную многозадачность можно назвать многозадачностью “второй ступени” поскольку она использует более передовые методы, чем простое переключение задач, реализованное многими известными программами (например, МS-DOS shell из МS-DOS 5.0 при простом переключении активная программа получает все процессорное время, а фоновые приложения полностью замораживаются. При кооперативной многозадачности приложение может захватить фактически столько процессорного времени, сколько оно считает нужным. Все приложения делят процессорное время, периодически передавая управление следующей задаче.

Вид многозадачности, в котором операционная система сама передает управление от одной выполняемой программы другой. Распределение процессорного времени осуществляется планировщиком процессов. Этот вид многозадачности обеспечивает более быстрый отклик на действия пользователя.

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

Каждая работающая программа имеет свое защищенное адресное пространство. Многопоточное (англ. multithread) выполнение отдельных задач позволяет при задержке в выполнении одного потока не останавливать задачу полностью, а работать со следующим потоком.

Процессы, потоки выполнения

Многозадачная (multi-process) система позволяет двум или более программам выполняться одновременно. Многопотоковая (multi-threaded) система позволяет одной программе выполнять сразу несколько потоков одновременно. Современные операционные системы сочетают в себе оба эти свойства.

Процесс — это понятие, относящееся к операционной системе. Каждый раз, как вы запускаете приложение, система создает и запускает новый процесс. С каждым процессом система связывает такие ресурсы, как:

Поток (thread) — это основной элемент системы, которому ОС выделяет машинное время. Поток может выполнять какую-то часть общего кода процесса, в том числе и ту часть, которая в это время уже выполняется другим потоком.

Скалярные, супер-скалярные, векторные, SMT процессоры

Классификация параллельных архитектур по Флинну (M. Flynn)

Вычислительная система с одним потоком команд и данных (однопроцессорная ЭВМ — SISD, Single Instruction stream over a Single Data stream).

Вычислительная система с общим потоком команд (SIMD, Single Instruction, Multiple Data — одиночный поток команд и множественный поток данных).

Вычислительная система со множественным потоком команд и одиночным потоком данных (MISD, Multiple Instruction Single Data — конвейерная ЭВМ).

Вычислительная система со множественным потоком команд и данных (MIMD, Multiple Instruction Multiple Data).

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

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

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

Увеличение быстродействия, которое можно получить с помощью конвейера приблизительно дается следующей формулой: nd/(n+d)

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

Векторный процессор — это процессор, в котором операндами некоторых команд могут выступать упорядоченные массивы данных — векторы (SIMD процессор). Отличается от скалярных процессоров, которые могут работать только с одним операндом в единицу времени. Абсолютное большинсто процессоров являются скалярными или близкими к ним. Векторные процессоры были распространены в сфере научных вычислений, где они являлись основой большинства суперкомпьютеров начиная с 1980-х до 1990-х. Но резкое увеличение производительности и активная разработка новых процессоров привели к вытеснению векторных процессоров со сферы повседневных процессоров.

Одновременная многопоточность (SMT — simultaneous multithreading) — следующий шаг в расширении возможностей процессора, ориентированный на приложения, требовательные к производительности, и поддерживающий метод распараллеливания задач на уровне инструкций на несколько каналов обработки процессора.

Одновременная многопоточная обработка на уровне приложений позволяет “видеть” два процессора вместо одного задействованного. В случае когда режим SMT отключен (однопоточная обработка), каждый физический процессор использует один логический. Когда же режим SMT активирован, каждый процессор, исполняющий в данный момент команды приложения, использует два логических процессора вместо одного. Технология многопоточности реализуется за счет того, что при выполнении разных команд приложения используются разные устройства процессора, что позволяет распределять по ним потоки.

Шины доступа к памяти и NUMA

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

Уровни этих сигналов в данный момент времени определяют состояние системы в этот момент.

На адресную шину, состоящую из 24 линий, микропроцессор выставляет адрес байта или слова, который будет пересылаться по шине данных в процессор или из него. Кроме того, шина адреса используется микропроцессором для указания адресов периферийных портов, с которыми производится обмен данными.

Шина данных состоит из 16 линий. по которым возможна передача как отдельных байтов. так и двухбайтовых слов. При пересылке байтов возможна передача и по старшим 8 линиям, и по младшим. Шина данных двунаправлена, так как передача байтов и слов может производится как в микропроцессор, так и из него.

Шина управления формируется сигналами, поступающими непосредственно от микропроцессора, сигналами от шинного контроллера, а также сигналами, идущими к микропроцессору от других микросхем и периферийных адаптеров.

Для того, чтобы понять динамику работы, разберем, каким образом осуществляется процессором чтение слов из оперативной памяти. Это происходит в течение 4 тактов CLK, или 2 состояний процессора (т.е. каждое состояние процессора длится 2 такта синхросигнала CLK). Во время первого состояния, обозначаемого, как Т 4s 0, процессор выставляет на адресную шину значение адреса, по которому будет читаться слово. Кроме того, он формирует на шине совместно с шинным контроллером соответствующие значения управляющих сигналов. Эти сигналы и адрес обрабатываются схемой управления памятью, в результате чего, начиная с середины второго состояния процессора

Т 4c 0 (т.е. в начале четвертого такта CLK), на шине данных появляется значение содержимого соответствующего слова из оперативной памяти. И наконец, процессор считывает значение этого слова с шины данных. На этом перенос (копирование) значения слова из памяти в процессор заканчивается.

Таким образом, если частота кварцевого генератора, определяющая частоту CLK, равна 20 МГц, то максимальная пропускная способность шины данных равна (20/4) миллионов слов в секунду, или 10 В/сек. Реальная пропускная способность существенно ниже.

Cимметричное мультипроцессирование (англ. Symmetric Multiprocessing, или SMP) это архитектура многопроцессорных компьютеров, в которой два или более одинаковых процессоров подключаются к общей памяти. Большинство многопроцессорных систем сегодня используют архитектуру SMP. SMP системы позволяют любому процессору работать над любой задачей независимо от того, где в памяти хранятся данные для этой задачи; с должной поддержкой операционной системы, SMP системы могут легко перемещать задачи между процессорами эффективно распределяя нагрузку. С другой стороны, память гораздо медленнее процессоров, которые к ней обращаются, даже однопроцессорным машинам приходится тратить значительное время на получение данных из памяти. В SMP ситуация ещё более усугубляется, так как только один процессор может обращаться к памяти в данный момент времени.

SMP это лишь один подход к построению многопроцессорной машины; другим подходом является NUMA, которая предоставляет процессорам отдельные банки памяти.

NUMA, Non-Uniform Memory Architecture — “Архитектура с неравномерной памятью”) — схема реализации компьютерной памяти, используемая в мультипроцессорных системах, когда время доступа к памяти определяется её расположением по отношению к процессору.

Системы NUMA состоят из однородных базовых узлов, содержащих небольшое число процессоров с модулями основной памяти.

Практически все архитектуры ЦПУ используют небольшое количество очень быстрой неразделяемой памяти, известной как кеш, который ускоряет обращение к часто требуемым данным. В NUMA поддержка когерентности через разделяемую память даёт существенное преимущество в производительности.

Хотя системы с некогерентным доступом к NUMA проще проектировать и создавать, становится предельно сложно создавать программы в классической модели архитектуры фон Неймана. В результате, все продаваемые NUMA-компьютеры используют специальные аппаратные решения для достижения когерентности кеша, и классифицируются как кеш-когерентные системы с распределенной разделяемой памятью, или ccNUMA.

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

Источник

Организация многозадачности в ядре ОС

Волею судеб мне довелось разбираться с организацией многозадачности, точнее псевдо-многозадачности, поскольку задачи делят время на одном ядре процессора. Я уже несколько раз встречала на хабре статьи по данной теме, и мне показалось, что данная тема сообществу интересна, поэтому я позволю себе внести свою скромную лепту в освещение данного вопроса.
Сначала я попытаюсь рассказать о типах многозадачности (кооперативной и вытесняющей). Затем перейду к принципам планирования для вытесняющей многозадачности. Рассказ рассчитан скорее на начинающего читателя, который хочет разобраться, как работает многозадачность на уровне ядра ОС. Но поскольку все будет сопровождаться примерами, которые можно скомпилировать, запустить, и с которыми при желании можно поиграться, то, возможно, статья заинтересует и тех, кто уже знаком с теорией, но никогда не пробовал планировщик “на вкус”. Кому лень читать, может сразу перейти к изучению кода, поскольку код примеров будет взят из нашего проекта.
Ну, и многопоточные котики для привлечения внимания.

Введение

Многозада́чность (англ. multitasking) — свойство операционной системы или среды программирования обеспечивать возможность параллельной (или псевдопараллельной) обработки нескольких процессов.

In computing, multitasking is a method where multiple tasks, also known as processes, are performed during the same period of time. The tasks share common processing resources, such as a CPU and main memory. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for that task. Multitasking solves the problem by scheduling which task may be the one running at any given time, and when another waiting task gets a turn. The act of reassigning a CPU from one task to another one is called a context switch.

В нем вводится понятие разделение ресурсов (resources sharing) и, собственно, планирование (scheduling). Именно о планировании (в первую очередь, процессорного времени) и пойдет речь в данной статье. В обоих определениях речь идет о планировании процессов, но я буду рассказывать о планировании на основе потоков.

Таким образом, нам необходимо ввести еще одно понятие, назовем его поток исполнения — это набор инструкций с определенным порядком следования, которые выполняет процессор во время работы программы.
Поскольку речь идет о многозадачности, то естественно в системе может быть несколько этих самых вычислительных потоков. Поток, инструкции которого процессор выполняет в данный момент времени, называется активным. Поскольку на одном процессорном ядре может в один момент времени выполняться только одна инструкция, то активным может быть только один вычислительный поток. Процесс выбора активного вычислительного потока называется планированием (scheduling). В свою очередь, модуль, который отвечает за данный выбор принято называть планировщиком (scheduler).

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

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

Рассматриваемый невытесняющий планировщик очень простой, данный материал дан для начинающих, чтобы было проще разобраться в многозадачности. Тот, кто имеет представление, хотя бы теоретическое, может сразу перейти к разделу “Вытесняющий планировщик”.

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

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

Результаты вывода:

График занятости процессора:

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

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

Результаты вывода:

Second activated
First activated

График занятости процессора

Невытесняющий планировщик на основе очереди сообщений

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

Результаты работы:

Second activated
Message 2 to first
Message 1 to first

График занятости процессора

Невытесняющий планировщик с сохранением порядка вызовов

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

Результаты работы:

First create
Second create
Second create again

График занятости процессора

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Создание

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

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

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

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

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

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

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

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

Cоотвественно, описание структуры у нас в проекте выглядит следующим образом:

В структуре есть поля не описанные в статье (sigstate, local, cleanups) они нужны для поддержки полноценных POSIX потоков (pthread) и в рамках данной статьи не принципиальны.

Планировщик и стратегия планирования

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

Рассмотрим реализацию стратегии планирования поподробнее.

Пример стратегии планирования

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

Планировщик

Теперь мы перейдем к самому интересному — описанию планировщика.

Запуск планировщика

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

Пробуждение и запуск потока

Как мы помним из описания машины состояний, пробуждение и запуск потока для планировщика — это один и тот же процесс. Вызов этой функции есть в запуске планировщика, там мы запускаем поток idle. Что, по сути дела, происходит при пробуждении? Во-первых, снимается пометка о том, что мы ждем, то есть поток больше не находится в состоянии waiting. Затем возможны два варианта: успели мы уже уснуть или еще нет. Почему это происходит, я опишу в следующем разделе “Ожидание”. Если не успели, то поток еще находится в состоянии ready, и в таком случае пробуждение завершено. Иначе мы кладем поток в очередь планировщика, снимаем пометку о состоянии waiting, ставим ready. Кроме того, вызывается перепланирование, если приоритет пробужденного потока больше текущего. Обратите внимание на различные блокировки: все действо происходит при отключенных прерываниях. Для того, чтобы посмотреть, как пробуждение и запуск потока происходит в случае SMP, советую вам обратиться к коду проекта.

Ожидание

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

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

A — active
R — ready
W — wait

На картинке буквами обозначено наличие состояний. Светло-зеленый цвет — состояние потока до wait_prepare, зеленый — после wait_prepare, а темно-зеленый — вызов потоком перепланирования.
Если событие не успеет произойти до перепланирования, то все просто — поток уснет и будет ждать пробуждения:

Перепланирование

Основная задача планировщика — планирование, прошу прощения за тавтологию. И мы наконец подошли к моменту когда можно разобрать как этот процесс реализован у нас в проекте.
Во-первых перепланирование должно выполняться при заблокированном планировщике. Во-вторых мы хотим дать возможность разрешить вытеснение потока или нет. Поэтому мы вынесли логику работы в отдельную функцию окружили ее вызов блокировками и вызвали ее указав, что в этом месте мы не позволяем вытеснение.
Далее идут действия с очередью готовых потоков. Если активный на момент перепланирования потока не собирается уснуть, то есть если у него не выставлено состояние waiting, мы просто добавим его в очередь потоков планировщика. Затем мы достаем самый приоритетный поток из очереди. Правила нахождения этого потока реализуются с помощью стратегии планирования.
Затем если текущий активный поток совпадает с тем который мы достали из очереди, нам не нужно перепланирование и мы можем просто выйти и продолжить выполнение потока. В случае же если требуется перепланирование, вызывается функция sched_switch, в которой выполняются действия необходимые планировщику и главное вызывается context_switch который мы рассматривали выше.
Если же поток собирается уснуть, находится в состоянии waiting, то он не попадает в очередь планировщика, и с него снимают метку ready.
В конце происходит обработка сигналов, но как я отмечала выше, это выходит за рамки данной статьи.

Проверка работы многопоточности

В качестве примера я использовала следующий код:

Собственно, это почти обычное приложение. Макрос EMBOX_EXAMPLE(run) задает точку входа в специфичный тип наших модулей. Функция thread_join дожидается завершения потока, пока я ее тоже не рассматривала. И так уже очень много получилось для одной статьи.
Результат запуска этого примера на qemu в составе нашего проекта следующий

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

Источник