Разное

Вытесняющая многозадачность – Вытесняющая многозадачность — Википедия

Содержание

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

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

В системах с
невытесняющей диспетчеризацией(non-preemptivemultitasking) работа любого
процесса может быть прервана только
«по инициативе самого процесса», а
точнее – только когда процесс вызывает
определенные системные функции. К ним
относятся, в частности, описанные выше
блокирующие функции. Может также иметься
функция, специально предназначенная
для добровольной уступки процессом
очереди на выполнение (Yield).
Вызов такой функции не приводит к
блокировке, но может привести к вытеснению
процесса1.
Если работающий процесс не вызывает
системных функций, а занимается, например,
долгими расчетами, то все остальные
процессы вынуждены простаивать. Когда
же системная функция, наконец, вызвана,
то система, прежде всего, проверяет,
может ли эта функция быть выполнена
сразу или предполагает ожидание
некоторого события (требуемый ресурс
может быть занят другим процессом;
операция ввода/вывода обычно требует
определенного времени на свое выполнение;
очередь сообщений, требующих обработки,
может быть пуста). Если требуется
ожидание, то система блокирует процесс,
выбирая какой-либо другой из готовых
процессов для выполнения. Не исключена
ситуация, когда заблокированными по
разным причинам оказываются все
пользовательские процессы.

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

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

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

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

Использование
невытесняющей диспетчеризации позволило
разработать достаточно впечатляющие
примеры ОС, из которых наиболее известной
является Windowsверсий 1, 2
и 3. Обычно в таких системах большая
часть процессов находится в спящем
состоянии, ожидая, пока пользователь
обратится к соответствующему приложению.
Для пользователя это выглядит совершенно
естественно.

Главный недостаток
многозадачности невытесняющего типа
заключается в том, что любой процесс в
принципе имеет возможность полностью
и надолго захватить процессор. Это
«многозадачность на честном слове»,
основанная на предположении, что
программы всех процессов написаны так,
чтобы достаточно часто вызывать
блокирующие функции. Даже если программист
пишет программу для выполнения сложных
многочасовых вычислений, он должен
искусственно вставлять в некоторых
местах вызов системных функций, передающих
управление планировщику. Если же это
не сделано, то система фактически теряет
многозадачность и будет выполнять один
процесс, не реагируя на действия
пользователя, до тех пор, пока либо
«нахальный» процесс завершится, либо
рассвирепевший пользователь снимет
его по Ctrl+Alt+Del.

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

  • когда активизируется
    (т.е. пробуждается или запускается)
    процесс, обладающий более высоким
    приоритетом, чем текущий;

  • когда истекает
    квант времени, выделенный
    планировщиком для текущего процесса.

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

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

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

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

studfiles.net

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




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

Преимущества:

– упрощение приложений – не нужно заботится о многозадачности.

– процессу не нужно регулировать процесс переключения процессов

– упрощенное паралельное выполнение процессов

– можно запускать много задач

Недостаток – задача не может контролировать промежуток своей работыи врямя отключения

 

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

Преимущества:

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

– ядро ОС упрощено

Недостаток – приложение более сложное (должно уметь возвращать управление ОС, выполнять более одной задачи в единицу времени)

 

Существует два основных типа процедур планирования процессов – вытесняющие (preemptive) и невытесняющие (non-preemptive).

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

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

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



Существенным преимуществом non-preemptive систем является более высокая скорость переключения с задачи на задачу.

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

 

Среди множества существующих вариантов реализации многозадачности можно выделить две группы алгоритмов: невытесняющая многозадачность (NetWare, Windows 3.x) и вытесняющая многозадачность (Windows NT, OS/2, UNIX). Основным различием между вытесняющим и невытесняющим вариантами многозадачности является степень централизации механизма планирования процессов. В первом случае механизм планирования процессов целиком сосредоточен в операционной системе, а во втором – распределен между системой и прикладными программами. При невытесняющей многозадачности активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление операционной системе для того, чтобы та выбрала из очереди другой готовый к выполнению процесс. При вытесняющей многозадачности решение о переключении процессора с одного процесса на другой принимается операционной системой (таймер), а не самим активным процессом.

 

Многонитивость

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

Нити могут пораждать нити потоки и переходить из состояния в состояние (ожидания, готовности или выполнения)

Многонитивая обработка повышает эффективность работы системы по сравнению с многозадачной обработкой.

Пример: в многозадачной ОС Windows, если работать в текстовом редакторе и в электронной таблице и запустить пересчет электронной таблици, она блокиуется. Этого бы не произошло если при написании электронной таблицы учитывалась многонитевая обработка данных. Также нити можно использовать для ожидния ввода информации.




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

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

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

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

Нити иногда называют облегченными процессами или мини-процессами взаимодействовать, а не бороться за ресурсы.

Многонитевая обработка повышает эффективность работы системы по сравнению с многозадачной обработкой.

Важным свойством операционных систем является возможность распараллеливания вычислений в рамках одной задачи. Многонитевая ОС разделяет процессорное время не между задачами, а между их отдельными ветвями (нитями). Например, в ходе выполнения задачи происходит обращение к внешнему устройству, и на время этой операции можно не блокировать полностью выполнение процесса, а продолжить вычисления по другой “ветви” процесса. Особенно эффективно можно использовать многонитевость для выполнения распределенных приложений, например, многонитевый сервер может параллельно выполнять запросы сразу нескольких клиентов. Нити иногда называют облегченными процессами или мини-процессами. Действительно, нити во многих отношениях подобны процессам. Каждая нить выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Нити, как и процессы, могут, например, порождать нити-потомки, могут переходить из состояния в состояние. Подобно традиционным процессам (то есть процессам, состоящим из одной нити), нити могут находится в одном из следующих состояний: ВЫПОЛНЕНИЕ, ОЖИДАНИЕ и ГОТОВНОСТЬ. Пока одна нить заблокирована, другая нить того же процесса может выполняться. Итак, нити имеют собственные: программный счетчик, стек, регистры, нити-потомки, состояние. Нити разделяют: адресное пространство, глобальные переменные, открытые файлы, таймеры, семафоры, статистическую информацию.

 











infopedia.su

Вытесняющая многозадачность (Операционные Системы) — Национальная библиотека им. Н. Э. Баумана

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:34, 7 июня 2019.

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

Основные особенности вытесняющей многозадачности

При вытесняющей многозадачности каждое приложение,которое выполняется,периодически получает квант процессорного времени. Блок Windows,который отвечает за распределение времени процессора,может в любое время прервать активную задачу и передать управление следующей. В 32-разрядных приложениях функция GetMessage,не обнаруживая определенного потока,может управление системе не передавать,а просто продолжить опрос очереди до истечения кванта.

Преимущества

Основными преимуществами вытесняющей многозадачности являются:

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

Недостатки

Основными недостатками вытесняющей многозадачности являются

  • задача не может контролировать промежуток своей работы и время отключения.
  • необходимость особой дисциплины при написании кода,особые требования к его реентрантности,к защите всех разделяемых и глобальных данных объектами типа критических секций и mutex’ов.[1]

Операционные системы,поддерживающие вытесняющую многозадачность

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

  • Windows NT и в режиме ядра,и в пользовательском режиме
  • AmigaOS все версии,до версии 4.0 без полноценной защиты памяти
  • Linux в пользовательском режиме (а часто и в режиме ядра) всех UNIX подобных OS/2, Mac OS и BeOS[2]
  • MenuetOS
  • KolibriOS[3].

Различия между вытесняющим и невытесняющим вариантами многозадачности

Основным различием между вытесняющим и невытесняющим вариантами многозадачности является степень централизации механизма планирования процессов.

  • При вытесняющей многозадачности механизм планирования процессов целиком сосредоточен в операционной системе. Решение о переключении процессора с одного процесса на другой принимается операционной системой (таймер),а не самим активным процессом.
  • При невытесняющей многозадачности механизм планирования процессов-распределен между системой и прикладными программами. Активный процесс выполняется до тех пор,пока он сам,по собственной инициативе,не отдаст управление операционной системе для того,чтобы та выбрала из очереди другой готовый к выполнению процесс.

[4]

Источники

Ссылки

ru.bmstu.wiki

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

Операционная
система Windows является многозадачной
(multitasking – мультизадачной), т.е. она способна
“одновременно” выполнять несколько
программ. На самом деле один микропроцессор
может выполнять инструкции только одной
программы. Однако операционная система
настолько оперативно реагирует на
потребности той или иной программы, что
создается впечатление одновременности
их работы. Например, в процессе подготовки
текста можно параллельно печатать
содержимое какого-либо файла и проверять
на вирус жесткий диск.

Многозадачность
может быть кооперативнойивытесняющей[2,
5]. Прикооперативной
многозадачности
(cooperative multitasking)
операционная система не занимается
решением проблемы распределения
процессорного времени. Распределяют
его сами программы. Причем активная
программа самостоятельно решает,
отдавать ли процессор другой программе.
Момент передачи управления здесь зависит
от хода выполнения задачи. Таким моментом
должен быть системный вызов, т.е. обращение
к системе за какой-либо услугой (ввод
или вывод на внешнее устройство и пр.).
Фоновым задачам выделяется процессорное
время при простое приоритетной задачи
(ожидание нажатия клавиши и др.).
Кооперативная многозадачность была
реализована в среде Windows 3.1. В Windows 95
кооперативная многозадачность
обеспечивается для 16-раэрядных приложений,
так как эти приложения, созданные для
Windows 3.1, умеют самостоятельно распределять
процессорное время.

При вытесняющей
многозадачности
(preemptive multitasking)
распределением процессорного времени
между программами занимается операционная
система. Она выделяет каждой задаче
фиксированный квант времени процессора.
По истечении этого кванта времени
система вновь получает управление,
чтобы выбрать другую задачу для ее
активизации. Если задача обращается к
операционной системе до истечения ее
кванта времени, то это также служит
причиной переключения задач. Такой
режим многозадачности Windows 95 реализует
для: 32-разрядных приложений, а также для
программ, написанных для MS DOS.

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

Графический пользовательский интерфейс

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

studfiles.net

Вытесняющая многозадачность на ассемблере Z80 / Habr

Медленный процессор и маленький объем ОЗУ — это еще не значит, что на такой платформе нельзя реализовать вытесняющую многозадачность. Более того, главный смысл организации многозадачной среды — это эффективное использование процессорного времени, чтобы процессор не простаивал, пока одни программы ждут какого-либо события, а использовался другими программами. Даже на таких платформах, как 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).

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

habr.com

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

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

Совместная или кооперативная многозадачность

Сюда
перенаправляется запрос «Кооперативная
многозадачность». На эту тему нужна
отдельная статья.

Тип
многозадачности, при котором следующая
задача выполняется только после того,
как текущая задача явно объявит себя
готовой отдать процессорное время
другим задачам. Как частный случай,
такое объявление подразумевается при
попытке захвата уже занятого объекта
mutex (ядро Linux), а также при ожидании
поступления следующего сообщения от
подсистемы пользовательского интерфейса
(Windows версий до 3.x включительно, а также
16-битные приложения в Windows 9x).

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

Преимущества
кооперативной многозадачности: отсутствие
необходимости защищать все разделяемые
структуры данных объектами типа
критических секций и mutex’ов, что упрощает
программирование, особенно перенос
кода из однозадачных сред в многозадачные.

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

Реализована
в пользовательском режиме ОС Windows версий
до 3.х включительно, Mac OS версий до Mac OS
X, а также внутри ядер многих UNIX-подобных
ОС, таких, как FreeBSD, а в течение долгого
времени — и Linux.

Вытесняющая или приоритетная многозадачность (режим реального времени) Вытесняющая многозадачность

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

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

Недостатки:
необходимость особой дисциплины при
написании кода, особые требования к его
реентрантности, к защите всех разделяемых
и глобальных данных объектами типа
критических секций и mutex’ов.

Реализована
в таких ОС, как:

  • VMS

  • Linux

  • в
    пользовательском режиме (а часто и в
    режиме ядра) всех UNIX-подобных ОС, включая
    версии Mac OS от OS X и старше, iPod OS и iPhone OS

  • в
    режиме ядра ОС Windows 3.x — только при
    исполнении на процессоре 386 или старше,
    «задачами» являются только все
    Windows-приложения вместе взятые и каждая
    отдельная виртуальная машина ДОС, между
    приложениями Windows вытесняющая
    многозадачность не использовалась

  • Windows
    95/98/Me — без полноценной защиты памяти,
    что служило причиной крайне низкой, на
    одном уровне с MS-DOS, Windows 3.x и Mac OS версий
    до X — надежности этих ОС

  • Windows
    NT/2000/XP/Vista/7 и в режиме ядра, и в
    пользовательском режиме.

  • AmigaOS
    — все версии, до версии 4.0 без полноценной
    защиты памяти, что на практике для
    системных программ почти не сказывалось
    на надёжности из-за высокой
    стандартизированности, прозрачных API
    и SDK. Программы ориентированные на
    «железо» Амиги, наоборот не отличались
    надёжностью.

studfiles.net

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

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

В
системах с невытесняющей
диспетчеризацией

(non-preemptive
multitasking)
работа любого процесса может быть
прервана только «по инициативе самого
процесса», а точнее – только когда
процесс вызывает определенные системные
функции. К ним относятся, в частности,
описанные выше блокирующие функции.
Может также иметься функция, специально
предназначенная для добровольной
уступки процессом очереди на выполнение
(Yield).
Вызов такой функции не приводит к
блокировке, но может привести к вытеснению
процесса1.
Если работающий процесс не вызывает
системных функций, а занимается, например,
долгими расчетами, то все остальные
процессы вынуждены простаивать. Когда
же системная функция, наконец, вызвана,
то система, прежде всего, проверяет,
может ли эта функция быть выполнена
сразу или предполагает ожидание
некоторого события (требуемый ресурс
может быть занят другим процессом;
операция ввода/вывода обычно требует
определенного времени на свое выполнение;
очередь сообщений, требующих обработки,
может быть пуста). Если требуется
ожидание, то система блокирует процесс,
выбирая какой-либо другой из готовых
процессов для выполнения. Не исключена
ситуация, когда заблокированными по
разным причинам оказываются все
пользовательские процессы.

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

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

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

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

Использование
невытесняющей диспетчеризации позволило
разработать достаточно впечатляющие
примеры ОС, из которых наиболее известной
является Windows
версий 1, 2 и 3. Обычно в таких системах
большая часть процессов находится в
спящем состоянии, ожидая, пока пользователь
обратится к соответствующему приложению.
Для пользователя это выглядит совершенно
естественно.

Главный
недостаток многозадачности невытесняющего
типа заключается в том, что любой процесс
в принципе имеет возможность полностью
и надолго захватить процессор. Это
«многозадачность на честном слове»,
основанная на предположении, что
программы всех процессов написаны так,
чтобы достаточно часто вызывать
блокирующие функции. Даже если программист
пишет программу для выполнения сложных
многочасовых вычислений, он должен
искусственно вставлять в некоторых
местах вызов системных функций, передающих
управление планировщику. Если же это
не сделано, то система фактически теряет
многозадачность и будет выполнять один
процесс, не реагируя на действия
пользователя, до тех пор, пока либо
«нахальный» процесс завершится, либо
рассвирепевший пользователь снимет
его по Ctrl+Alt+Del.

Более
сложным и совершенным типом многозадачных
ОС являются системы с вытесняющей
диспетчеризацией

процессов (preemptive
multitasking).
Их отличие заключается в том, что
планировщик вступает в работу не только
(и не столько) при вызове системных
функций, но и в следующих двух случаях
(или хотя бы в одном из них):

  1. когда
    активизируется (т.е. пробуждается или
    запускается) процесс, обладающий более
    высоким приоритетом, чем текущий;

  2. когда
    истекает квант
    времени
    ,
    выделенный планировщиком для текущего
    процесса.

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

процесс с высоким приоритетом будет
все же вынужден подождать истечения
кванта времени.

Системы,
в которых перепланировка процесса
выполняется после истечения каждого
кванта времени, называют системами с
квантованием
времени1

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

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

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

studfiles.net

Отправить ответ

avatar
  Подписаться  
Уведомление о