что такое вытесняющая многозадачность
Что такое вытесняющая многозадачность
Для пользователей это означает, что управление системой теряется на произвольный период времени, который определяется приложением (а не пользователем). Если приложение тратит слишком много времени на выполнение какой-либо работы, например, на форматирование диска, пользователь не может переключиться с этой задачи на другую задачу, например, на текстовый редактор, в то время как форматирование продолжалось бы в фоновом режиме. Эта ситуация нежелательна, так как пользователи обычно не хотят долго ждать, когда машина завершит свою задачу. Поэтому разработчики приложений для non-preemptive операционной среды, возлагая на себя функции планировщика, должны создавать приложения так, чтобы они выполняли свои задачи небольшими частями. Например, программа форматирования может отформатировать одну дорожку дискеты и вернуть управление системе. После выполнения других задач система возвратит управление программе форматирования, чтобы та отформатировала следующую дорожку. Подобный метод разделения времени между задачами работает, но он существенно затрудняет разработку программ и предъявляет повышенные требования к квалификации программиста. Программист должен обеспечить «дружественное» отношение своей программы к другим выполняемым одновременно с ней программам, достаточно часто отдавая им управление. Крайним проявлением «недружественности» приложения является его зависание, которое приводит к общему краху системы. В системах с вытесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный планирующий механизм снимет зависшую задачу с выполнения. Однако распределение функций планировщика между системой и приложениями не всегда является недостатком, а при определенных условиях может быть и преимуществом, потому что дает возможность разработчику приложений самому проектировать алгоритм планирования, наиболее подходящий для данного фиксированного набора задач. Так как разработчик сам определяет в программе момент времени отдачи управления, то при этом исключаются нерациональные прерывания программ в «неудобные» для них моменты времени. Кроме того, легко разрешаются проблемы совместного использования данных: задача во время каждой итерации использует их монопольно и уверена, что на протяжении этого периода никто другой не изменит эти данные. Существенным преимуществом non-preemptive систем является более высокая скорость переключения с задачи на задачу. Примером эффективного использования невытесняющей многозадачности является файл-сервер NetWare, в котором, в значительной степени благодаря этому, достигнута высокая скорость выполнения файловых операций. Менее удачным оказалось использование невытесняющей многозадачности в операционной среде Windows 3.х.
Однако почти во всех современных операционных системах, ориентированных на высокопроизводительное выполнение приложений (UNIX, Windows NT, OS/2, VAX/VMS), реализована вытесняющая многозадачность. В последнее время дошла очередь и до ОС класса настольных систем, например, OS/2 Warp и Windows 95. Возможно в связи с этим вытесняющую многозадачность часто называют истинной многозадачностью.
Вытесняющая и невытесняющая многозадачность
При вытесняющей многозадачности управление ядру возвращается по таймеру. Все процессы практически равны по времени исполнения и постоянно переключаются по таймеру, либо в ожидании взаимодействия с внешним устройством.
— упрощение приложений – не нужно заботится о многозадачности.
— процессу не нужно регулировать процесс переключения процессов
— упрощенное паралельное выполнение процессов
— можно запускать много задач
Недостаток – задача не может контролировать промежуток своей работыи врямя отключения
При невытесняющей многозадачности процесс сам возвращает управление ядру. Один процесс являющийся главным работает занимая все процессорное время и возвращает управление по своему усмотрению, иногда по таймеру. Либо если ожидает взаимодействия с внешним устройством. Также процессы могут передавать управление между собой
— система сосредоточена над выполнением одной задачи
Недостаток – приложение более сложное (должно уметь возвращать управление ОС, выполнять более одной задачи в единицу времени)
Существенным преимуществом non-preemptive систем является более высокая скорость переключения с задачи на задачу.
Однако почти во всех современных операционных системах, ориентированных на высокопроизводительное выполнение приложений, реализована вытесняющая многозадачность.
Многонитивость
Задача решаемая в рамках одного процесса может обладать внутренним паралелизмом, который позволяет ускорить ее решение. Для этого в ОС используется механизм многонитивой обработки (multithreading). Задача, оформленная в виде нескольки нитий в рамках одного процесса и может быть выполнена быстрее блаодаря параллельному или псевдопараллельному выполнению. Нити часто называют процессами или нити-процессами. Каждая нить выполняется строго последовательно и имеет свой программный счетчик
Нити могут пораждать нити потоки и переходить из состояния в состояние (ожидания, готовности или выполнения)
Многонитивая обработка повышает эффективность работы системы по сравнению с многозадачной обработкой.
Пример: в многозадачной ОС Windows, если работать в текстовом редакторе и в электронной таблице и запустить пересчет электронной таблици, она блокиуется. Этого бы не произошло если при написании электронной таблицы учитывалась многонитевая обработка данных. Также нити можно использовать для ожидния ввода информации.
В многопроцессорных системах нити выполняются паралельно, но при разработке многонитивого приложения необходимо рассматривать ее исполнение и на однопроцессорной системе.
Важным свойством операционных систем является возможность распараллеливания вычислений в рамках одной задачи. Многонитевая ОС разделяет процессорное время не между задачами, а между их отдельными ветвями (нитями).
Мультипрограммирование теперь реализуется на уровне нитей, и задача, оформленная в виде нескольких нитей в рамках одного процесса, может быть выполнена быстрее за счет псевдопараллельного (или параллельного в мультипроцессорной системе) выполнения ее отдельных частей. Особенно эффективно можно использовать многонитевость для выполнения распределенных приложений, например, многонитевый сервер может параллельно выполнять запросы сразу нескольких клиентов.
Нити, относящиеся к одному процессу, не настолько изолированы друг от друга, как процессы в традиционной многозадачной системе, между ними легко организовать тесное взаимодействие. Действительно, в отличие от процессов, которые принадлежат разным, вообще говоря, конкурирующим приложениям, все нити одного процесса всегда принадлежат одному приложению, поэтому программист, пишущий это приложение, может заранее продумать работу множества нитей процесса таким образом, чтобы они могли.
Нити иногда называют облегченными процессами или мини-процессами взаимодействовать, а не бороться за ресурсы.
Многонитевая обработка повышает эффективность работы системы по сравнению с многозадачной обработкой.
Важным свойством операционных систем является возможность распараллеливания вычислений в рамках одной задачи. Многонитевая ОС разделяет процессорное время не между задачами, а между их отдельными ветвями (нитями). Например, в ходе выполнения задачи происходит обращение к внешнему устройству, и на время этой операции можно не блокировать полностью выполнение процесса, а продолжить вычисления по другой «ветви» процесса. Особенно эффективно можно использовать многонитевость для выполнения распределенных приложений, например, многонитевый сервер может параллельно выполнять запросы сразу нескольких клиентов. Нити иногда называют облегченными процессами или мини-процессами. Действительно, нити во многих отношениях подобны процессам. Каждая нить выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Нити, как и процессы, могут, например, порождать нити-потомки, могут переходить из состояния в состояние. Подобно традиционным процессам (то есть процессам, состоящим из одной нити), нити могут находится в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ. Пока одна нить заблокирована, другая нить того же процесса может выполняться. Итак, нити имеют собственные: программный счетчик, стек, регистры, нити-потомки, состояние. Нити разделяют: адресное пространство, глобальные переменные, открытые файлы, таймеры, семафоры, статистическую информацию.
Вытесняющая многозадачность на ассемблере Z80
Медленный процессор и маленький объем ОЗУ — это еще не значит, что на такой платформе нельзя реализовать вытесняющую многозадачность. Более того, главный смысл организации многозадачной среды — это эффективное использование процессорного времени, чтобы процессор не простаивал, пока одни программы ждут какого-либо события, а использовался другими программами. Даже на таких платформах, как ZX Spectrum (Z80 3.5МГц, 48-128кБ ОЗУ), или 8-битные микроконтроллеры AVR, организация вытесняющей многозадачности имеет большой смысл.
Предлагаю вашему вниманию собственную реализацию многозадачного диспетчера на ассемблере 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).
Состояние процессора. Аббревиатура в 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.