Медленный процессор и маленький объем ОЗУ — это еще не значит, что на такой платформе нельзя реализовать вытесняющую многозадачность. Более того, главный смысл организации многозадачной среды — это эффективное использование процессорного времени, чтобы процессор не простаивал, пока одни программы ждут какого-либо события, а использовался другими программами. Даже на таких платформах, как ZX Spectrum (Z80 3.5МГц, 48-128кБ ОЗУ), или 8-битные микроконтроллеры AVR, организация вытесняющей многозадачности имеет большой смысл.
Предлагаю вашему вниманию собственную реализацию многозадачного диспетчера на ассемблере Z80 (ZX Spectrum), который не является частью какой-либо ОС, а может использоваться отдельно. В нем нет ничего лишнего — только организация исполнения потоков и синхронизации между ними. Диспетчер можно использовать как составную часть программного проекта, как основу для создания более серьезного диспетчера для ОС, или как обучающий материал.
Архитектура была навеяна концепциями ядра Windows NT при изучении мною исходников ReactOS [2]. Из этих концепций был реализован минимум, который дает необходимые черты многозадачности. Более полная реализация возможна, но начиная с некоторого момента дополнительные функции перестают себя оправдывать из-за их затратности на малых ЭВМ.
Потоки [1] являются основными единицами, которыми управляет диспетчер. Каждый поток имеет исполняемый код и собственный стек, которым можно пользоваться для хранения адресов возврата из подпрограмм и другой информации. Диспетчер переключает исполнение с одного потока на другой таким образом, чтобы по возможности все потоки исполнили столько кода, сколько желают.
Каждый поток может находиться в одном из трех состояний: ожидание (waiting), готовность к исполнению (ready) и исполнение (running). В состоянии ожидания диспетчер не дает коду потока исполняться до наступления события, которое ожидаетя потоком. Поток, находящийся в состоянии готовности, получит управление от диспетчера, как только это станет возможным. В состоянии исполнения может находиться только один поток, так как в системе имеется только один процессор. Его код исполняется процессором до тех пор, пока поток не перейдет в состояние ожидания, либо пока не произойдет вытеснение, т. е. диспетчер по собственной инициативе не передаст управление другому потоку.
Количество потоков в системе фиксировано. Новые потоки не запускаются, а старые — не завершаются. Для микроконтроллерного применения или в рамках отдельной прикладной программы это ограничение несущественно. Зато упрощается диспетчер и ускоряется его работа.
Каждому потоку соответствует приоритет. Если имеется несколько потоков в состоянии готовности — то диспетчер выбирает к исполнению тот из них, приоритет которого наивысший. В текущей версии диспетчера приоритет потока нельзя изменять в процессе работы. Динамический приоритет потоков затратен в реализации, хотя эта возможность необходима для решения проблемы инверсии приоритета [1].
Приоритет всех потоков в системе различный. Это значит, что диспетчер не организует псевдопараллельное исполнение кода с одинаковым приоритетом, быстро переключая процессор с одного потока на другой (“Round-Robin”). Но на самом деле это ограничение несущественно. Псевдопараллельное исполнение нескольких потоков дает замедление каждого из них. Учитывая ограниченные ресурсы памяти компьютера, лучше организовать последовательное исполнение таких программ. Главная польза от вытесняющей многозадачности состоит не в возможности псевдопараллельного исполнения, а в эффективном разделении процессора между кратковременными задачами обработки запросов от важных источников (например, реакция на нажатие пользователем клавиши на клавиатуре) и длительной работой программ, время завершения которых некритично (компиляция, архивация). Если назначить для потока, обрабатывающего нажатия клавиш, высокий приоритет, а для потока архивации — низкий, то с точки зрения пользователя, редактирующего текст, скорость работы редактора не упадет, но зато в фоновом режиме в качестве бонуса заархивируется файл.
На их основе поток может перейти в состояние ожидания путем вызова соответствующей функции диспетчера. Объект ожидания может быть сигнализирован или несигнализирован. Если он сигнализирован — то функция ожидания возвращается немедленно, и поток продолжает исполнение. Если же объект несигнализирован — то поток переходит в состояние ожидания, а исполняться начинают другие потоки, которые находятся в состоянии готовности. Как только объект станет сигнализирован, ожидающий поток вернется в состояние готовности и при первой возможности получит управление от диспетчера. В операционных системах обычно имеются такие объекты ожидания, как события (events), семафоры (semaphores), мутексы (mutex) и др. В рассматриваемом диспетчере реализованы два типа Events: Notification Event (Manual Reset), и Synchronization Event (Auto-Reset).
Состояние процессора. Аббревиатура в Windows NT расшифровывается как ”Interrupt Request Level” [3], хотя это не совсем точно отражает смысл понятия. В описываемом диспетчере существует три уровня IRQL. PASSIVE_LEVEL – это когда в данный момент процессор исполняет код одного из потоков. В это время может произойти вытеснение исполняемого потока другим потоком, либо процессор может начать обрабатывать аппаратное прерывание. DISPATCH_LEVEL — в этом состоянии находится процессор во время исполнения критического кода диспетчера. Например, переключение исполнения между потоками — операция, состоящая из множества действий. В это время нельзя сказать, что процессор исполняет тот или иной поток — он как бы находится «между ними». В связи с этим вытеснение кода, исполняемого в режиме DISPATCH_LEVEL, невозможно. Наконец, третий уровень — DIRQL — соответствует тому, что процессор в данный момент обрабатывает аппаратное прерывание.
В отличие от Windows NT, в моем диспетчере нет такого места, где бы хранился текущий уровень IRQL. Также нет функций, повышающих или понижающих его в явном виде. Но IRQL как концепция подразумевается в системе и объективно существует в ней, хоть и неявно.
Пользовательский код может исполняться либо в потоках (на PASSIVE_LEVEL), либо в пользовательской подпрограмме обработки прерываний (ISR) на DIRQL. Набор доступных функций диспетчера различен для разных IRQL. Нарушение требований по IRQL приводит к сбою системы.
Пользовательский код, исполняющийся в потоках, не должен запрещать прерывания. Код ISR исполняется с запрещенными прерываниями, и поэтому наоборот, их нельзя разрешать. Что касается DISPATCH_LEVEL — то в Windows NT в этом режиме прерывания не запрещены, а в моем диспетчере, для простоты, на DISPATCH_LEVEL прерывания запрещены.
Приводится назначение функций и описание их работы. Подробности передачи параметров в эти функции приведены в комментариях к исходному коду и здесь не дублируются, чтобы не загромождать текст. Имена функций по возможности взяты идентично именам аналогичных функций ядра Windows NT [2,3].
Снять сигнализацию объекта ожидания типа Event. Можно вызывать на любом уровне IRQL.
Сигнализировать объект ожидания типа Notification Event (Manual Reset). Все потоки, которые ожидали сигнализации этого объекта, перейдут в состояние готовности к исполнению. Если среди них окажется поток с более высоким приоритетом, чем текущий – то исполнение текущего потока будет вытеснено в пользу того, который имеет высший приоритет.
Объект останется сигнализирован до вызова KeResetEvent.
Функцию можно вызывать только на IRQL=PASSIVE_LEVEL.
То же самое, но для вызова на IRQL>=DISPATCH_LEVEL. При вызове этой функции из ISR переключение потоков, если произойдет, то после завершения исполнения ISR.
Сигнализировать объект ожидания типа Synchronization Event (Auto Reset). Если у этого объекта были ожидающие потоки — то один из них перейдет в состояние готовности, а объект сразу вернется в несигнализированное состояние. Остальные потоки продолжат ожидание. Если ожидающих потоков не было — то объект останется сигнализирован до тех пор, пока какой-нибудь поток не вызовет на нем функцию ожидания, либо KeResetEvent.
Когда сигнализации такого объекта ожидают несколько потоков, порядок их выхода из ожидания не определен.
Если ожидавший и перешедший в стостояние готовности поток имеет более высокий приоритет, чем текущий — то произойдет вытеснение.
Функцию можно вызывать только на IRQL=PASSIVE_LEVEL.
То же самое, но для вызова на IRQL>=DISPATCH_LEVEL. При вызове этой функции из ISR переключение потоков, если произойдет, то после завершения исполнения ISR.
Ожидание сигнализации объекта (Event). Если на момент вызова этой функции объект был сигнализирован — то функция немедленно возвращается. При этом, в случае Synchronization Event, произойдет сброс объекта в несигнализированное состояние. Если же объект не был сигнализирован — то текущий поток перейдет в режим ожидания, и диспетчер станет исполнять код из других потоков, находящихся в состоянии готовности.
Функцию можно вызывать только на IRQL=PASSIVE_LEVEL.
Под этим разумеется возможность исполнения пользовательской подпрограммы обработки прерываний. В виде функции не выделена, но в исходнике диспетчера предусмотрено место для ее вызова или вставки. Для взаимодействия с потоками эта подпрограмма может использовать функции KeSetNotifEventFromIsr и KeSetSynchrEventFromIsr и, таким образом, «разбудить» какой-нибудь поток и привести к вытеснению другого потока.
При исполнении ISR используется отдельная область стека, которая не принадлежит ни одному из потоков. При обслуживании аппаратного прерывания в стек потока помещается только адрес возврата из прерывания (2 байта). Другие функции диспетчера также не злоупотребляют стеком. Поэтому на стеках потоков можно экономить, резервируя для них минимальное количество памяти.
Остальные функции диспетчера не предназначены для вызова из пользовательских программ.
Чтобы использовать диспетчер в каком-либо программном проекте, необходимо его настроить. В исходном тексте следует заполнить структуру данных threads для каждого потока. Пример заполнения приведен в исходнике. Главное, что следует заполнять — это адреса стеков потоков. Последние два байта стека каждого потока содержат адрес его точки входа. Также следует указать количество потоков путем задания константы NUM_THREADS. Максимальное количество потоков в системе — 255.
При старте системы все потоки должны находиться в состоянии готовности. Последний поток, имеющий самый низкий приоритет, не должен переходить в режим ожидания. Этот поток представляет из себя аналог System Idle Process и не решает какую-либо задачу, а предназначен для «сжигания» неиспользуемого времени процессора. В нем рекомендуется циклически исполнять команду HALT.
Также следует настроить размещение в памяти самого диспетчера, таблицы векторов прерываний, и адрес ISR диспетчера. Пользовательская ISR вызывается из ISR диспетчера.
Выделение памяти под объекты ожидания, которых в принципе может быть неограниченное количество, оставлено на усмотрение пользователя. Можно хранить эти объекты в стеке, в глобальных статических переменных или подключить к проекту менеджер кучи (heap) и выделять память под указанные объекты в куче.
Для среды исполнения, реализуемой диспетчером, характерны ситуации, проблемные для систем вытесняющей многозадачности вообще [1]. К ним относятся: голодание (Starvation), гонки (Race Conditions) и инверсия приоритета (Priority Inversion). Первые две проблемы могут быть решены правильным проектированием системы, разумным распределением задач по потокам, разумного выбора их приоритета и использованием примитивов синхронизации (в первую очередь Auto-Reset Synchronization Events). Третья ситуация в моем диспетчере не разрешается, так как отсутствуют динамический приоритет потоков и объекты синхронизации типа Mutex. Поэтому, если эта ситуация возникает в конкретном проекте, ее следует учесть и при необходимости добавить в диспетчер вышеуказанные средства.
Исходный код диспетчера вместе с описанием структур данных, параметров функций и прочей информацией, можно скачать на GitHub.
1. Википедия. Статья «Многозадачность»
2. ReactOS. Исходный код, компонент «ntoskrnl”
3. Windows WDK Documentation. MSDN. Kernel-mode driver architecture
Предлагаю вашему вниманию собственную реализацию многозадачного диспетчера на ассемблере Z80 (ZX Spectrum), который не является частью какой-либо ОС, а может использоваться отдельно. В нем нет ничего лишнего — только организация исполнения потоков и синхронизации между ними. Диспетчер можно использовать как составную часть программного проекта, как основу для создания более серьезного диспетчера для ОС, или как обучающий материал.
Архитектура реализованной многозадачной системы
Архитектура была навеяна концепциями ядра Windows NT при изучении мною исходников ReactOS [2]. Из этих концепций был реализован минимум, который дает необходимые черты многозадачности. Более полная реализация возможна, но начиная с некоторого момента дополнительные функции перестают себя оправдывать из-за их затратности на малых ЭВМ.
Потоки (Threads)
Потоки [1] являются основными единицами, которыми управляет диспетчер. Каждый поток имеет исполняемый код и собственный стек, которым можно пользоваться для хранения адресов возврата из подпрограмм и другой информации. Диспетчер переключает исполнение с одного потока на другой таким образом, чтобы по возможности все потоки исполнили столько кода, сколько желают.
Каждый поток может находиться в одном из трех состояний: ожидание (waiting), готовность к исполнению (ready) и исполнение (running). В состоянии ожидания диспетчер не дает коду потока исполняться до наступления события, которое ожидаетя потоком. Поток, находящийся в состоянии готовности, получит управление от диспетчера, как только это станет возможным. В состоянии исполнения может находиться только один поток, так как в системе имеется только один процессор. Его код исполняется процессором до тех пор, пока поток не перейдет в состояние ожидания, либо пока не произойдет вытеснение, т. е. диспетчер по собственной инициативе не передаст управление другому потоку.
Количество потоков в системе фиксировано. Новые потоки не запускаются, а старые — не завершаются. Для микроконтроллерного применения или в рамках отдельной прикладной программы это ограничение несущественно. Зато упрощается диспетчер и ускоряется его работа.
Каждому потоку соответствует приоритет. Если имеется несколько потоков в состоянии готовности — то диспетчер выбирает к исполнению тот из них, приоритет которого наивысший. В текущей версии диспетчера приоритет потока нельзя изменять в процессе работы. Динамический приоритет потоков затратен в реализации, хотя эта возможность необходима для решения проблемы инверсии приоритета [1].
Приоритет всех потоков в системе различный. Это значит, что диспетчер не организует псевдопараллельное исполнение кода с одинаковым приоритетом, быстро переключая процессор с одного потока на другой (“Round-Robin”). Но на самом деле это ограничение несущественно. Псевдопараллельное исполнение нескольких потоков дает замедление каждого из них. Учитывая ограниченные ресурсы памяти компьютера, лучше организовать последовательное исполнение таких программ. Главная польза от вытесняющей многозадачности состоит не в возможности псевдопараллельного исполнения, а в эффективном разделении процессора между кратковременными задачами обработки запросов от важных источников (например, реакция на нажатие пользователем клавиши на клавиатуре) и длительной работой программ, время завершения которых некритично (компиляция, архивация). Если назначить для потока, обрабатывающего нажатия клавиш, высокий приоритет, а для потока архивации — низкий, то с точки зрения пользователя, редактирующего текст, скорость работы редактора не упадет, но зато в фоновом режиме в качестве бонуса заархивируется файл.
Объекты ожидания (объекты синхронизации)
На их основе поток может перейти в состояние ожидания путем вызова соответствующей функции диспетчера. Объект ожидания может быть сигнализирован или несигнализирован. Если он сигнализирован — то функция ожидания возвращается немедленно, и поток продолжает исполнение. Если же объект несигнализирован — то поток переходит в состояние ожидания, а исполняться начинают другие потоки, которые находятся в состоянии готовности. Как только объект станет сигнализирован, ожидающий поток вернется в состояние готовности и при первой возможности получит управление от диспетчера. В операционных системах обычно имеются такие объекты ожидания, как события (events), семафоры (semaphores), мутексы (mutex) и др. В рассматриваемом диспетчере реализованы два типа Events: Notification Event (Manual Reset), и Synchronization Event (Auto-Reset).
IRQL
Состояние процессора. Аббревиатура в Windows NT расшифровывается как ”Interrupt Request Level” [3], хотя это не совсем точно отражает смысл понятия. В описываемом диспетчере существует три уровня IRQL. PASSIVE_LEVEL – это когда в данный момент процессор исполняет код одного из потоков. В это время может произойти вытеснение исполняемого потока другим потоком, либо процессор может начать обрабатывать аппаратное прерывание. DISPATCH_LEVEL — в этом состоянии находится процессор во время исполнения критического кода диспетчера. Например, переключение исполнения между потоками — операция, состоящая из множества действий. В это время нельзя сказать, что процессор исполняет тот или иной поток — он как бы находится «между ними». В связи с этим вытеснение кода, исполняемого в режиме DISPATCH_LEVEL, невозможно. Наконец, третий уровень — DIRQL — соответствует тому, что процессор в данный момент обрабатывает аппаратное прерывание.
В отличие от Windows NT, в моем диспетчере нет такого места, где бы хранился текущий уровень IRQL. Также нет функций, повышающих или понижающих его в явном виде. Но IRQL как концепция подразумевается в системе и объективно существует в ней, хоть и неявно.
Пользовательский код может исполняться либо в потоках (на PASSIVE_LEVEL), либо в пользовательской подпрограмме обработки прерываний (ISR) на DIRQL. Набор доступных функций диспетчера различен для разных IRQL. Нарушение требований по IRQL приводит к сбою системы.
Пользовательский код, исполняющийся в потоках, не должен запрещать прерывания. Код ISR исполняется с запрещенными прерываниями, и поэтому наоборот, их нельзя разрешать. Что касается DISPATCH_LEVEL — то в Windows NT в этом режиме прерывания не запрещены, а в моем диспетчере, для простоты, на DISPATCH_LEVEL прерывания запрещены.
Функции диспетчера
Приводится назначение функций и описание их работы. Подробности передачи параметров в эти функции приведены в комментариях к исходному коду и здесь не дублируются, чтобы не загромождать текст. Имена функций по возможности взяты идентично именам аналогичных функций ядра Windows NT [2,3].
KeResetEvent
Снять сигнализацию объекта ожидания типа Event. Можно вызывать на любом уровне IRQL.
KeSetNotifEvent
Сигнализировать объект ожидания типа Notification Event (Manual Reset). Все потоки, которые ожидали сигнализации этого объекта, перейдут в состояние готовности к исполнению. Если среди них окажется поток с более высоким приоритетом, чем текущий – то исполнение текущего потока будет вытеснено в пользу того, который имеет высший приоритет.
Объект останется сигнализирован до вызова KeResetEvent.
Функцию можно вызывать только на IRQL=PASSIVE_LEVEL.
KeSetNotifEventFromIsr
То же самое, но для вызова на IRQL>=DISPATCH_LEVEL. При вызове этой функции из ISR переключение потоков, если произойдет, то после завершения исполнения ISR.
KeSetSynchrEvent
Сигнализировать объект ожидания типа Synchronization Event (Auto Reset). Если у этого объекта были ожидающие потоки — то один из них перейдет в состояние готовности, а объект сразу вернется в несигнализированное состояние. Остальные потоки продолжат ожидание. Если ожидающих потоков не было — то объект останется сигнализирован до тех пор, пока какой-нибудь поток не вызовет на нем функцию ожидания, либо KeResetEvent.
Когда сигнализации такого объекта ожидают несколько потоков, порядок их выхода из ожидания не определен.
Если ожидавший и перешедший в стостояние готовности поток имеет более высокий приоритет, чем текущий — то произойдет вытеснение.
Функцию можно вызывать только на IRQL=PASSIVE_LEVEL.
KeSetSynchrEventFromIsr
То же самое, но для вызова на IRQL>=DISPATCH_LEVEL. При вызове этой функции из ISR переключение потоков, если произойдет, то после завершения исполнения ISR.
KeWaitForObject
Ожидание сигнализации объекта (Event). Если на момент вызова этой функции объект был сигнализирован — то функция немедленно возвращается. При этом, в случае Synchronization Event, произойдет сброс объекта в несигнализированное состояние. Если же объект не был сигнализирован — то текущий поток перейдет в режим ожидания, и диспетчер станет исполнять код из других потоков, находящихся в состоянии готовности.
Функцию можно вызывать только на IRQL=PASSIVE_LEVEL.
User ISR
Под этим разумеется возможность исполнения пользовательской подпрограммы обработки прерываний. В виде функции не выделена, но в исходнике диспетчера предусмотрено место для ее вызова или вставки. Для взаимодействия с потоками эта подпрограмма может использовать функции KeSetNotifEventFromIsr и KeSetSynchrEventFromIsr и, таким образом, «разбудить» какой-нибудь поток и привести к вытеснению другого потока.
При исполнении ISR используется отдельная область стека, которая не принадлежит ни одному из потоков. При обслуживании аппаратного прерывания в стек потока помещается только адрес возврата из прерывания (2 байта). Другие функции диспетчера также не злоупотребляют стеком. Поэтому на стеках потоков можно экономить, резервируя для них минимальное количество памяти.
Остальные функции диспетчера не предназначены для вызова из пользовательских программ.
Настройка диспетчера под конкретный проект
Чтобы использовать диспетчер в каком-либо программном проекте, необходимо его настроить. В исходном тексте следует заполнить структуру данных threads для каждого потока. Пример заполнения приведен в исходнике. Главное, что следует заполнять — это адреса стеков потоков. Последние два байта стека каждого потока содержат адрес его точки входа. Также следует указать количество потоков путем задания константы NUM_THREADS. Максимальное количество потоков в системе — 255.
При старте системы все потоки должны находиться в состоянии готовности. Последний поток, имеющий самый низкий приоритет, не должен переходить в режим ожидания. Этот поток представляет из себя аналог System Idle Process и не решает какую-либо задачу, а предназначен для «сжигания» неиспользуемого времени процессора. В нем рекомендуется циклически исполнять команду HALT.
Также следует настроить размещение в памяти самого диспетчера, таблицы векторов прерываний, и адрес ISR диспетчера. Пользовательская ISR вызывается из ISR диспетчера.
Выделение памяти под объекты ожидания, которых в принципе может быть неограниченное количество, оставлено на усмотрение пользователя. Можно хранить эти объекты в стеке, в глобальных статических переменных или подключить к проекту менеджер кучи (heap) и выделять память под указанные объекты в куче.
Проблемные ситуации
Для среды исполнения, реализуемой диспетчером, характерны ситуации, проблемные для систем вытесняющей многозадачности вообще [1]. К ним относятся: голодание (Starvation), гонки (Race Conditions) и инверсия приоритета (Priority Inversion). Первые две проблемы могут быть решены правильным проектированием системы, разумным распределением задач по потокам, разумного выбора их приоритета и использованием примитивов синхронизации (в первую очередь Auto-Reset Synchronization Events). Третья ситуация в моем диспетчере не разрешается, так как отсутствуют динамический приоритет потоков и объекты синхронизации типа Mutex. Поэтому, если эта ситуация возникает в конкретном проекте, ее следует учесть и при необходимости добавить в диспетчер вышеуказанные средства.
Исходный код
Исходный код диспетчера вместе с описанием структур данных, параметров функций и прочей информацией, можно скачать на GitHub.
Литература
1. Википедия. Статья «Многозадачность»
2. ReactOS. Исходный код, компонент «ntoskrnl”
3. Windows WDK Documentation. MSDN. Kernel-mode driver architecture
