Лекция 1. Введение в сетевые ОС (стр. 2 )

· вызовы функций API, которые содержит приложение, должны поддерживаться данной ОС;

· внутренняя структура исполняемого файла приложения должна соответствовать структуре исполняемых файлов данной ОС.

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

Существуют три основных варианта построения множественных прикладных сред (рис. 2.6-2.8).

Рис. 2.6. Прикладные программные среды, транслирующие системные вызовы

Рис. 2.7. Реализация совместимости на основе нескольких равноправных API

Рис. 2.8. Клиент-серверная реализация множественных прикладных сред

Не существует какого-либо однозначно лучшего способа реализации механизма множественных прикладных сред, их достоинства и недостатки приведены в табл. 2.1.

Таблица 2.1. Сравнение подходов реализации прикладных сред

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

Лекция 3. Процессы и потоки в ОС

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

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

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

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

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

3) в интерактивных системах – при обработке запроса пользователя на запуск процесса;

4) в системах пакетной обработки – при инициировании пользователем пакетного задания.

Процесс завершает свою работу, когда происходит одно из следующих событий:

1) обычный выход (преднамеренное завершение);

2) выход по ошибке (преднамеренное завершение);

3) выход по неисправимой ошибке (непреднамеренное);

4) уничтожение другим процессом (непреднамеренное).

В промежуток времени между созданием и уничтожением процесс может находиться в одном из трех состояний (рис. 3.1):

· работающем (процесс использует процессор);

· ожидающем (процесс готов к выполнению, но процессор занят);

· блокированном (процесс не может быть запущен прежде, чем произойдет некое внешнее событие).

Рис. 3.1. Состояния процесса и переходы между ними: 1 - процесс блокируется в ожидании события, 2 - планировщик выбирает другой процесс, 3 - планировщик выбирает данный процесс, 4 - происходит ожидаемое событие

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

Таблица 3.1. Некоторые поля типичного элемента таблицы процессов

Управление процессом	Управление памятью	Управление файлами
Регистры Счётчик команд Указатель стека Состояние процесса Приоритет Параметры планирования Идентификатор процесса Родительский процесс* Группа процесса* Сигналы* Время начала процесса Использованное процессорное время Время, оставшееся до тайм-аута	Указатель на сегмент кода Указатель на сегмент данных Указатель на сегмент стека	Идентификатор пользователя* Идентификатор группы* Корневой каталог* Рабочий каталог* Дескрипторы файлов*

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

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

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

Концепция потоков добавляет к модели процесса возможность одновременного выполнения в одной и той же среде процесса нескольких программ, в достаточной степени независимых. Потоки иногда называют упрощенными процессами. Основные преимущества использования потоков таковы: 1) возможность использования параллельными объектами общего адресного пространства и всех содержащихся в нем данных; 2) легкость создания и уничтожения (примерно в 100 раз быстрее); 3) увеличение производительности при совмещении вычислений и операций ввода-вывода; 4) параллелизм в мультипроцессорных системах.

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

Элементы процесса	Элементы потока
Адресное пространство Глобальные переменные Открытые файлы Дочерние процессы Необработанные аварийные сигналы Сигналы и их обработчики Информация об использовании ресурсов	Счетчик команд Регистр Стек Состояние

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

Рис. 3.2. Организация потоков в ОС в пространстве пользователя

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

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

Рис. 3.3. Организация потоков в ОС в ядре

В целях совмещения преимуществ обоих подходов была предложена смешанная реализация, при которой некоторое количество пользовательских потоков N мультиплексируется в M (N>=M) потоков ядра. Такой подход используется, например, в ОС Solaris, Mach.

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

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

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

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

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

Алгоритмы, основанные на квантовании, отводят поочередно каждому потоку (процессу, если ОС является не многозадачной, а многопрограммной) ограниченный непрерывный период процессорного времени – квант. Смена активного потока происходит в следующих случаях:

· поток завершился и покинул систему;

· произошла ошибка;

· поток перешел в состояние ожидания;

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

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

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

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

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

1) системы пакетной обработки данных;

2) интерактивные среды;

3) системы реального времени.

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

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

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

Задачи алгоритмов планирования различаются в зависимости от среды, кроме того, есть общие требования, предъявляемые ко всем алгоритмам планирования, см. табл. 3.2.

Таблица 3.2. Некоторые задачи алгоритмов планирования

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

В системах пакетной обработки при планировании применяются следующие алгоритмы:

· «первым пришёл – первым обслужен». Процессам предоставляется доступ к процессору в том порядке, в котором они его запрашивают. В ходе работы процессы не прерываются, а при блокировании запускается следующий процесс из очереди. После разблокирования процесс он помещается в конец очереди. Данный алгоритм легок в понимании и программировании, но не учитывает специфику работающих процессов (ограничение по вычислениям или вводу-выводу);

· «кратчайшая задача – первая». Используется в том случае, когда временные отрезки работы известны заранее. Если в очереди есть несколько одинаково важных задач, планировщик выбирает первой самую короткую задачу. Алгоритм показывает лучший результат по среднему оборотному времени только в том случае, если на момент принятия решений все задачи присутствуют одновременно;

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

В интерактивных системах используются другие виды алгоритмов:

· «циклическое планирование». Каждому процессу выделяется квант времени. Если к концу кванта процесс все еще работает, то он прерывается, а управление передается другому процессу из очереди. Эффективность напрямую зависит от выбранной величины кванта. Алгоритм хорошо работает только с равнозначными процессами;

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

· «самый короткий процесс следующий». Интерактивные процессы чаще всего работают по схеме «ожидание команды, исполнение команды». Если рассматривать выполнение каждой команды как отдельную задачу, можно минимизировать общее среднее время отклика, запуская первой самую короткую задачу. Алгоритм пытается выяснить, какой процесс самый короткий, по оценке длины процесса, базирующейся на его предыдущем поведении. Если предполагаемое время работы при предыдущем запуске было T1, а фактическое время работы – T0, то новая оценка времени работы может быть получена как aT0 + (1 - a)T1, где a – коэффициент, влияющий на то, как долго алгоритм оценки «помнит» о предыдущих запусках. Метод оценки следующего значения серии через взвешенное среднее предыдущего значения и предыдущей оценки называют старением;

· «гарантированное планирование». В основе данного алгоритма лежит обязательство системы по предоставлению фиксированной части мощности процессора каждому процессу. Для выполнения этого обещания ОС отслеживает распределение процессора между процессами с момента создания. Затем рассчитывается количество ресурсов процессора, на которое процесс имеет право, например время с момента создания, деленное на количество процессов в системе. Теперь можно сосчитать отношение времени, предоставленного процессу, ко времени, на которое он имеет право. Полученное число 0,5 означает, что процессу выделили только половину положенного времени, а 2,0 – что процессу досталось в два раза больше чем положено. Затем запускается процесс, у которого это отношение наименьшее, пока оно не станет больше, чем у ближайшего соседа;

· «лотерейное планирование». Алгоритм выдает процессам «лотерейные билеты» для доступа к процессору. Когда планировщику необходимо принять решение, выбирается случайным образом лотерейный билет, и его обладатель получает доступ к процессору;

· «справедливое планирование». Алгоритм планирует процессы с учётом хозяев процессов. Пользователю достается доля процессорного времени, и планировщик подбирает процессы в соответствии с этим фактом.

Отдельно от прочих алгоритмов планирования следует рассматривать планирование в системах реального времени. Главным критерием эффективности является реакция на сигналы управляемого объекта в заданных временных ограничениях. Однако задача планирования облегчается тем, что весь набор выполняемых задач известен заранее. Кроме того, часто в системе имеется информация о длительности выполнения задач, моментах активации, предельных допустимых сроках ожидания ответа и т. д. Эти данные могут быть использованы планировщиком для создания статического расписания или построения адекватного алгоритма динамического планирования.

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

Внешние события, на которые система должна реагировать, можно разделить на периодические (возникающие через регулярные интервалы времени) и апериодические (возникающие непредсказуемо). Возможно наличие нескольких периодических потоков событий, которые система должна обрабатывать. В зависимости от времени, затрачиваемого на обработку одного из событий, может оказаться, что система не в состоянии своевременно обработать все события. Если в систему поступает m периодических событий, а длительность обработки событий Ci и периоды их поступления Pi известны, то все потоки могут быть своевременно обработаны только при выполнении условия ΣCi /Pi ≤ K, где K – количество доступных процессоров. Системы, удовлетворяющие этому условию, называются поддающимися планированию или планируемыми.