Многозадачность в операционных системах, виды многозадачности
Многозада́чность — свойство ОС или среды выполнения обеспечивать возможность параллельной обработки нескольких процессов. Иными словами, многозадачность — способ выполнения нескольких задач в один период времени. При этом задачи делят между собой общие ресурсы (resources sharing), помимо этого осуществляется планирование (scheduling). [1]
Система называется однозадачной,если она не обладает свойством многозадачности, т.е. задачи в ней выполняются последовательно. DOS — однозадачная ОС.
Многозадачность имеет место при наличии нескольких потоков исполнения.
Поток исполнения — набор последовательных инструкций, выполняемых процессором во время работы программы. На одном процессорном ядре одновременно выполняется лишь один поток исполнения, который называется активным. Процесс выбора активного исполнительного потока носит название планирование.
По типу наименьшего элемента управляемого кода
Процессная многозадачность.
Здесь программа — наименьший элемент управляемого кода, которым может управлять планировщик операционной системы. Известна большинству пользователей (одновременная работа в текстовом редакторе и прослушивание музыки). Многозадачная система позволяет двум или более программам выполняться одновременно.
Поточная многозадачность.
Многопоточность — специализированная форма многозадачности. Наименьший элемент управляемого кода — поток. Многопотоковая (multi-threaded) система предоставляет возможность одновременного выполнения одной программой 2 и более задач
По способу организации времени выполнения каждого процесса
Параллельная многозадачность
Параллельная многозадачность, когда каждая задача исполняется в своём аппаратном микропроцессорном ядре действительно одновременно друг с другом. Реализация данного типа многозадачности требует больших материальных вложений. Альтернативой параллельной многозадачности является применение псевдопараллельной многозадачности или совокупности параллельной и псевдопараллельной многозадачности при наличии нескольких процессорных ядер.
Типы псевдопараллельной многозадачности
Невытесняющая многозадачность. Существенным ограничением такого подхода является то, что время, затрачиваемое программой на обработку сообщения может быть очень большим, а управление операционной системе передается только после обработки сообщения.
Совместная или кооперативная многозадачность. ОС передает управление от одного приложения другому не в любой момент времени, а только когда текущее приложение отдает управление системе, получил, как было упомянуто, название кооперативной многозадачности
Вытесняющая, или приоритетная, многозадачность (режим реального времени)
С Windows 95 ОС действительно контролирует и управляет процессами, потоками и их переключением. Способность ОС прервать выполняемый поток практически в любой момент времени и передать управление другому ожидающему потоку определяется термином preemptive multitasking — преимущественная, или вытесняющая, многозадачность.
Про многозадачность: окна под контролем
Марат Хайрулин, эксперт Microsoft в России, продолжает исследовать нюансы работы с несколькими задачами и рассказывает о совмещении окон и разделении экрана, о вашей личной машине времени для сайтов и документов, и о реальной пользе виртуальных столов.
В прошлой заметке мы писали о том, как современная наука относится к многозадачности и делились небольшими приемами, которые помогут сосредоточиться на одной задаче. А теперь хочтим напомнить (а кого-то может быть и познакомить) с полезными возможностями, которые помогут, если решение вашей задачи требует работы сразу с несколькими приложениями.
Переключение по-старому и по-новому
Переключение между приложениями – наверное то, что большинство из нас делает «на автомате», и никого, конечно, не удивит сочетание клавиш Alt + Tab. Но если одновременно нажать также и Ctrl (то есть Ctrl + Alt + Tab), то эта комбинация зафиксирует меню со всеми открытыми окнами на экране и позволит выбрать нужное приложение одним кликом мыши или касанием пальца (выбрать окно можно также с помощью стрелок на клавиатуре, а открыть – с помощью Enter). Может быть полезно, когда у вас открыто много окон.
Чуть менее известное, но тоже классическое сочетание клавиш Windows + Tab дает больше возможностей, чем кажется на первый взгляд.
Нажимая эти клавиши в актуальных версиях Windows 10, мы попадаем в раздел «Представление задач». Здесь можно не только переключаться между приложениями, но и воспользоваться «Временной шкалой» и «Виртуальными рабочими столами». К слову, вместо горячих клавиш вы можете кликнуть по кнопке «Представление задач» (обычно она расположена рядом с кнопкой «Пуск») или провести пальцем от левого края к центру сенсорного экрана. Кстати, если у вас современный ноутбук – попробуйте жест для тачпада: проведите по нему тремя пальцами вверх.
Режим Представление задач
«Временная шкала»
«Временная шкала» появилась в Windows 10 два года назад. Она помогает вернуться к задачам, над которыми вы работали ранее на вашем компьютере. При необходимости вы также сможете синхронизировать ее и с другими устройствами с вашей учетной записью*.
Для меня «Временная шкала» стала своеобразной машиной времени. Работа над многими проектами длится несколько дней. И если, допустим, в прошлую пятницу я работал с определенными сайтами и документами, вернувшись к этому проекту в среду, я смогу легко восстановить картину. Я просто отмотаю шкалу до нужной даты – той самой пятницы, увижу и смогу открыть те самые сайты и документы, в которые я тогда был погружен.
Поиск на Временной шкале
Поиск на «Временной шкале» тоже не раз меня выручал. В отличие от обычного поиска по файлам, я смогу искать не среди всех документов на устройстве (а их может быть очень много), а именно среди тех, с которыми я работал в последние дни. Возможно, вам знакомо сочетание Ctrl + F, запускающее поиск в Проводнике и во многих приложениях. Эта комбинация сработает и на экране «Представление задач»: то есть можно нажать сначала Windows + Tab, а затем – Ctrl + F и ввести искомое слово для поиска по «Временной шкале».
Виртуальные рабочие столы Windows 10
Концепция виртуальных рабочих столов далеко не нова. Если говорить о Windows, то одним из вариантов их использования была утилита Desktops, которую когда-то (последняя версия вышла в 2012 году) разработал Марк Руссинович. В Windows 10 виртуальные рабочие столы встроены в систему и помогают разделять потоки задач, переключаться между ними.
Если раньше вы не работали с виртуальными столами, для понимания их логики представьте такую аналогию: вам доступно несколько мониторов, на каждом вы можете открыть нужные программы, разделив их по рабочим потокам, например: на одном мониторе – работа с почтой и календарем, на другом – работа с несколькими документами Word, а на третьем – работа с браузером и OneNote. В каждый момент вы смотрите только на один монитор (виртуальный рабочий стол) со своим набором приложений. А переключаясь между виртуальными столами, вы как будто переводите взгляд с одного монитора на другой.
Перетаскивание окна для переноса его на новый виртуальный рабочий стол
Создать новый виртуальный рабочий стол можно на экране «Представление задач»: нажмите Windows + Tab и перетащите нужные окна открытых приложений на поле с надписью «+ Создать рабочий стол», и они будут перемещены на другой виртуальный рабочий стол. Можно также создать новый, пустой виртуальный стол (Windows + Ctrl + D) и уже затем открыть на нем нужные программы.
«Переводить взгляд» (то есть переключаться между настроенными рабочими столами) можно, выбирая нужный стол на экране «Представление задач», но намного удобнее переключаться с помощью горячих клавиш: Windows + Ctrl + стрелки вправо/влево, а на современных тачпадах – 4 пальца влево или вправо.
Полезные решения для работы с несколькими приложениями
Теперь еще об одной повседневной необходимости – работе с несколькими приложениями одновременно.
Разделение экрана
Первой возможности, о которой хочу напомнить, уже много лет, и в первоначальном виде (под названием Aero Snap) она появилась еще в Windows 7. В Windows 10 ее возможности расширили и назвали Snap Assist. Речь про разделение экрана для закрепления двух (а в Windows 10 – до четырех) приложений.
Snap Assist предлагает выбрать второе окно для закрепления справа
Чтобы это сделать, нужно взять приложение за самую верхнюю полоску, поднести его к правой или левой границе экрана до появления на экране его «тени» и отпустить (тем самым, закрепив первое приложение), а затем в появившихся рядом миниатюрах других приложений выбрать второе для закрепления рядом. Сценарий несложный, работает и для мыши, и для пальца. Еще проще это можно сделать с помощью сочетания клавиш Windows + клавиши со стрелками вправо/влево. Этому сочетанию уже больше 10 лет, но у тех, кто применяет его впервые, и сейчас порой возникает ощущение «цифровой магии».
Любознательным пользователям также напомню, что в Windows 10 можно отправлять приложение в «четвертинку» экрана, перенеся его в угол (или используя дополнительно клавиши Windows + стрелки вверх/вниз). При закреплении двух приложений можно перемещать границу между ними, выделяя какому-то из приложений больше места. Чтобы выбрать приложения для закрепления на экране, можно кликнуть правой кнопкой мыши по их миниатюрам на экране «Представление задач».
Окно поверх
У меня было довольно мало ситуаций, когда требовалось закреплять окно одного приложения поверх другого (кажется, на телевизорах подобное называлось режимом «картинка в картинке»), но если у вас такая необходимость возникает, напомню в завершение заметки о двух небольших возможностях.
Мини-режим встроенного видеоплеера (приложение «Кино и ТВ», которое воспроизводит видео в Windows 10 по умолчанию). Запустите видео и нажмите на небольшую кнопку в правом нижнем углу (Воспроизвести в мини-режиме), окно с видеороликом будет размещено поверх всех окон.
Видео в режиме Окно поверх
Аналогичную возможность, только с закреплением поверх всех приложений окна браузера, можно получить с использованием отдельных утилит. Однажды мне потребовалось работать над документом, постоянно сверяясь при этом с сайтом одного онлайн-сервиса, и меня выручило приложение Always on Top, доступное в Microsoft Store. Оно встраивается в меню «Поделиться» в Edge и позволяет отправить любой сайт в окно, расположенное поверх всех приложений. Я мог бы пошутить, что этот вариант отлично подошел бы для просмотра каналов на YouTube «одним глазком» во время работы, например, над сводными таблицами в Excel. Но как мы и обсуждали в первой заметке, такая многозадачность скорее повредит и просмотру, и работе.
В этом обзоре я поделился некоторыми возможностями при работе с одной или несколькими задачами, которыми пользуюсь сам. В следующих заметках продолжу разговор о приемах, которые помогут сделать нашу «цифровую жизнь» более продуктивной.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Организация многозадачности в ядре ОС
Волею судеб мне довелось разбираться с организацией многозадачности, точнее псевдо-многозадачности, поскольку задачи делят время на одном ядре процессора. Я уже несколько раз встречала на хабре статьи по данной теме, и мне показалось, что данная тема сообществу интересна, поэтому я позволю себе внести свою скромную лепту в освещение данного вопроса.
Сначала я попытаюсь рассказать о типах многозадачности (кооперативной и вытесняющей). Затем перейду к принципам планирования для вытесняющей многозадачности. Рассказ рассчитан скорее на начинающего читателя, который хочет разобраться, как работает многозадачность на уровне ядра ОС. Но поскольку все будет сопровождаться примерами, которые можно скомпилировать, запустить, и с которыми при желании можно поиграться, то, возможно, статья заинтересует и тех, кто уже знаком с теорией, но никогда не пробовал планировщик “на вкус”. Кому лень читать, может сразу перейти к изучению кода, поскольку код примеров будет взят из нашего проекта.
Ну, и многопоточные котики для привлечения внимания.
Введение
Многозада́чность (англ. 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:
Машина состояний потока
Мы обсудили важное отличие структуры потока в случае с вытесняющим планировщиком от случая с невытесняющим планировщиком — наличие контекста. Посмотрим, что происходит с потоком с момента его создания до завершения: 
- Состояния 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:
Режим ожидания
Поток может отдать свое время другому потоку по каким-либо причинам, например, вызвав функцию 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 в составе нашего проекта следующий 
Как видно из результатов, сначала созданные потоки выполняются один за другим, планировщик дает им время по очереди. В конце некоторое расхождение. Я думаю, это следствие того, что у планировщика достаточно грубая точность (не сопоставимая с выводом одного символа на экран). Поэтому на первых проходах потоки успевают выполнить разное количество циклов.
В общем, кто хочет поиграться, можно скачать проект и попробовать все вышеописанное на практике.
Если тема интересна, я попробую продолжить рассказ о планировании, еще достаточно много тем осталось не раскрытыми.