Создание и удаление процессов и потоков

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

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

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

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

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

3.1.2 Планирование и диспетчеризация
процессов и потоков

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

§ по возможности заканчивать вычисления в том же самом порядке, в каком они были начаты;

§ отдавать предпочтение более коротким процессам;

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

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

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

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

Планирование включает в себя решение двух задач:

§ определение момента времени для смены активного потока;

§ выбор для выполнения потока из очереди готовых потоков.

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

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

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

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

§ сохранение контекста текущего потока, который требуется сменить;

§ загрузка контекста нового потока, выбранного в результате планирования;

§ запуск нового потока на выполнение.

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

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

3.1.3 Алгоритмы планирования

С точки зрения решения первой задачи планирования (выбор момента времени для смены активного потока) алгоритмы планирования делятся на два больших класса – вытесняющие и невытесняющие алгоритмы:

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

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

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

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

Достоинства данного подхода:

§ исключено прерывание потока в неудобный для него момент;

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

§ более высокая скорость переключения с потока на поток.

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

Примеры:

1. В операционной системе Windows 3.x разработанные в ней приложения действовали именно таким образом, и программисты должны были сами обеспечивать "дружественное" отношение своих программ к другим задачам (крайним проявлением "недружественности" является зависание приложения, которое приводит к краху системы).

2. Файл-серверы NetWare 3.x, 4.x – высокая скорость выполнения файловых операций. Поток, чтобы не занимать процессор слишком долго, сам отдает управление с помощью системных вызовов. Простой алгоритм планирования и иерархии контекстов обуславливает небольшие накладные расходы на диспетчеризацию потоков, вследствие чего невытесняющий механизм организации многопоточной работы в этой ОС очень производителен.

Вытесняющие алгоритмы – циклический, или круговой тип планирования, при котором операционная система сама решает вопрос о прерывании активного приложения и переключает процессор с одной задачи на другую в соответствии с тем или иным критерием. В системе с такими алгоритмами программисту не надо заботиться о том, что его приложение будет выполняться одновременно с другими задачами. В качестве примеров можно назвать операционные системы UNIX, Windows NT/2000, OS/2. Алгоритмы этого класса ориентированы на высокопроизводительное выполнение приложений.

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

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

Кванты могут быть одинаковыми для всех потоков или различными.

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

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

Замечание

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

Алгоритмы, основанные на приоритетах. Вытесняющие алгоритмы этого класса основаны на механизме абсолютных приоритетов, при котором задача снимается с выполнения, когда появляется в системе задание с более высоким приоритетом.

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

Теперь рассмотрим некоторые наиболее распространенные дисциплины планирования.

1) Обслуживание в порядке поступления. Выделение процессора производится по принципу FIFO (First In First Out), т.е. в порядке поступления заявок на обслуживание. Этот подход позволяет реализовать стратегию "по возможности заканчивать вычисления в порядке их появления". Те задачи, которые были заблокированы в процессе выполнения, после перехода в состояние готовности ставятся в очередь перед теми задачами, которые ещё не выполнялись. Таким образом, создается две очереди: одна из новых задач, а другая – из задач, перешедших из
состояния ожидания.

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

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

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

Алгоритм относится к разряду невытесняющих бесприоритетных.

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

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

3)
Карусельная дисциплина, или круговая – RR (Round Robin). Данная дисциплина относится к вытесняющим алгоритмам и основана на квантовании. После окончания выделенного задаче кванта времени она снимается с процессора и ставится в конец очереди потоков, готовых к выполнению, а на обслуживание процессором принимается очередная задача.

В некоторых ОС есть возможность указывать в явном виде величину кванта времени или допустимый диапазон его значений. Например, в OS/2 в файле CONFIG.SYS с помощью оператора TIMESLICE указывается минимальное и максимальное значения для кванта времени: TIMESLICE=32,256 указывает, что квант возможно изменять в пределах от 32 до 256 миллисекунд.

Дисциплина планирования RR является одной из самых распространенных. В некоторых случаях, когда ОС не поддерживает в явном виде дисциплину карусельного планирования, такое обслуживание можно организовать искусственно. Например, в некоторых ОСРВ используется планирование с абсолютными приоритетами, а при равенстве приоритетов действует принцип очередности. Тогда снять задачу с выполнения может только задача с более высоким приоритетом. При необходимости организовать обслуживание равномерно и равноправно, т.е. чтобы все задания получали одинаковые кванты времени, системный оператор может сам реализовать такое обслуживание. Для этого достаточно всем пользовательским задачам присвоить одинаковые приоритеты и создать одну высокоприоритетную задачу, которая не должна ничего делать, кроме как планироваться на выполнение по таймеру через указанные интервалы времени. Эта задача будет только снимать с выполнения текущее приложение, оно переместится в конец очереди, а сама задача тут же покинет процессор и уступит его следующему в очереди процессу.

В простейшей реализации карусельная дисциплина обслуживания предполагает, что все задания имеют одинаковый приоритет. Если же необходимо ввести механизм приоритетного обслуживания, обычно организуют несколько очередей, в зависимости от приоритетов, и к обслуживанию менее приоритетной очереди переходят только в том случае, когда более приоритетная очередь пуста. По такому алгоритму выполняется планирование в системах OS/2 и Windows NT.

4) Планирование согласно приоритетам.

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

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

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

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

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

Пример

Рассмотрим схему назначения потоков, принятую в Windows NT. В системе определено 32 уровня приоритетов и два класса потоков – потоки реального времени и потоки с переменными приоритетами. Диапазон от 1 до 15 включительно отведен для потоков с переменными приоритетами, а от 16 до 31 – для более критичных ко времени потоков реального времени (приоритет 0 зарезервирован для системных целей). При создании процесса он в зависимости от класса получает базовый приоритет в верхней или нижней части диапазона. Этот базовый приоритет процесса может быть в дальнейшем повышен или понижен операционной системой. Поток первоначально получает значение базового приоритета из диапазона базового приоритета процесса, в котором он был создан. Пусть, например, значение базового приоритета процесса равно k. Тогда все потоки данного процесса получат базовые приоритеты из диапазона [ k-2,k+2 ].

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

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

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

Примеры

Рассмотрим примеры операционных систем, в которых квантование сочетается с динамическими абсолютными приоритетами.

1. Именно так организовано планирование в системе Windows NT. На выполнение выбирается поток с наивысшим приоритетом, ему выделяется квант времени. Если во время его выполнения в очереди готовых появляется поток с более высоким приоритетом, то он вытесняет выполняемый поток. Вытесненный поток возвращается в очередь готовых, причём ставится впереди всех остальных потоков, имеющих такой же приоритет.

2. В системе OS/2 планирование основано на тех же принципах. При этом на множестве потоков определены приоритетные классы – критический, серверный, стандартный и остаточный, в каждом из которых имеется 32 приоритетных уровня. Потоки критического класса относятся к задачам реального времени и имеют наивысший приоритет (системные потоки, управляющие сетью), следующий по приоритетности класс предназначен для потоков, обслуживающих серверные приложения. Потоки обычных приложений относятся к стандартному классу (ещё его называют регулярным), самый низкий приоритет у потоков остаточного класса (например, программа проверки электронной почты или поток вывода на экран заставки). Поток из менее приоритетного класса не может быть выбран на выполнение, пока очередь более приоритетного класса не пуста. Внутри класса потоки также выбираются по приоритетам, а потоки с одинаковым приоритетом обслуживаются в циклическом порядке. Переход от одного потока к другому происходит либо по окончании отведенного ему кванта процессорного времени, либо по системному прерыванию, передающему управление задаче с более высоким приоритетом (обеспечивает более быструю реакцию на события).

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

3. В ОС UNIX System V Release 4 (SVR4) понятие "поток" отсутствует, и планирование осуществляется на уровне процессов в соответствии с алгоритмом вытесняющей многозадачности, основанной на использовании приоритетов и квантовании.

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

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

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

В рассмотренных выше системах UNIX System V Release 4, OS/2 и Windows NT имеется приоритетный класс реального времени. Для потоков этого класса обеспечено только предпочтение в скорости обслуживания, но не гарантировано выполнение заданных временных ограничений. Поэтому эти ОС могут быть основой для построения лишь мягких систем реального времени, но непригодны для жёстких систем.

За последние годы появился ряд интересных подходов к планированию, основанных на дополнительной информации о заданиях:

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

§ Предельное время начала выполнения – время, когда должно начаться выполнение задания.

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

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

§ Требования к ресурсам – множество ресурсов, требующихся заданию для его выполнения.

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

§ Структура подзадач. Задача может быть разбита на обязательные и необязательные подзадачи, при этом жёсткие предельные сроки имеют только обязательные подзадачи.

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

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

Рассмотрим пример планирования периодических заданий с предельным временем завершения.

Пусть система собирает и обрабатывает данные от двух датчиков, A и B. Сроки сбора данных от датчика A – каждые 20 мс, от датчика B – каждые 50 мс. Процесс снятия данных, включая накладные расходы ОС, занимает: для датчика A – 10 мс, для датчика B – 25 мс.

 

Время поступления, выполнения и предельное время

Схема выполнения с приоритетом A

Предположим, что используется схема с приоритетами. В случае более высокого приоритета A задание B получит только 20 мс процессорного времени в двух смежных интервалах по 10 мс, после этого будет достигнуто его предельное время выполнения, а задание ещё не выполнится (см. иллюстрацию ниже).
Если более высокий приоритет назначить заданию B, то (что очевидно) в срок не успеет выполниться задание A. Хотя по суммарному времени выполнения 5 заданий А и 2 задания В должны успевать выполниться за 100 мс.

В данной ситуации наиболее целесообразно использовать вытесняющее планирование с предельным временем завершения (т.е. каждый раз в ситуации выбора на выполнение выбирается то задание, которое имеет меньшее предельное время завершения). В момент времени t=0 поступают задания A1 и B1. Поскольку предельный срок A1 наступает раньше, сначала выполняется A1. После его завершения начинает выполняться B1, но после появления в момент t=20 задания A2 его предельное время завершения оказывается меньшим, поэтому выполнение B1 прерывается и не продолжается, пока не выполнится A2 (к моменту t=30). В момент времени t=40 появляется очередное задание A3, но его предельное время завершения больше, чем у выполняющегося B1, поэтому сначала оно завершится (в момент t=45), и только затем начнет выполняться A3. Данная схема проиллюстрирована на рисунке.

3.1.4 Контрольные вопросы

1. Каковы функции подсистемы управления процессами и потоками?

2. Что происходит при создании задачи? С какими ещё подсистемами взаимодействует при этом подсистема управления задачами?

3. Что представляет из себя дочерняя задача? Имеет ли она право на удаление или приостановку родительской задачи?

4. Каким может быть взаимодействие дочерней и родительской задач?

5. Каковы действия системы управления задачами при завершении процесса?

6. Что такое планирование и каковы его цели?

7. Назовите две основные задачи планирования.

8. В чём отличие статического типа планирования от динамического? В каких системах используется статическое планирование?

9. Что такое диспетчеризация? Какие действия входят в её состав?

10. Каким образом можно уменьшить потери времени при переключении контекста одного потока на другой?

11. Какую из задач планирования позволяют решить невытесняющие алгоритмы планирования?

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

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

14. Каковы особенности планирования в системах реального времени?

15. В чём отличие жёстких систем реального времени от мягких?