Состояние процессов

1.  Ввод в систему;

2.  Диспетчеризация;

3.  Освобождение;

4.  Ожидание события;

5.  Событие;

6.  Тайм аут;

7.  Свопинг;

8.  Активация.

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

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

Описание процессов

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

В общем, ОС поддерживает четыре различных вида таблиц:

1.  для памяти;

2.  для устройств ввода-вывода;

3.  для файлов;

4.  для процессов.

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

Таблицы памяти должны включать следующую информацию:

1) объем основной памяти, отведенной процессу;

2) объем вторичной памяти, отведенной процессу;

3) все атрибуты защиты блоков основной и виртуальной памяти, как например указание, какой из процессов имеет доступ к той или иной совместно используемой области памяти;

4) всю информацию, необходимую для управления виртуальной памятью.

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

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

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

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

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

Аппаратная поддержка взаимоисключений

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

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

Такой подход не будет работать в многопроцессорной системе.

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

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

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

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

Операционная проверка и установка реализована на большинстве компьютеров. Команда TS (test and set) является двухадресной.
Ее действие заключается в том, что процессор присваивает значение второго операнда первому, после чего второму операнду присваивается значение 1. Команда TS является неделимой операцией, так как между ее началом и концом не могут выполняться никакие другие операции. Чтобы использовать команду TS для решения проблемы критического интервала, с ней связывают переменную, которая является общей для всех процессов, использующих некий критический ресурс. Данная переменная будет принимать единичное значение, если какой-либо из взаимодействующих процессов находится в своем критическом интервале.

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

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

Современные ЦП поддерживают либо атомарную операцию CAS (compare and swap), либо атомарную операцию LL/SC (linked loading/save condition). Предназначены для операций взаимного исключения. Команда считывает значение флага и помещает его в регистр назначения, а затем очищает флаг. Если исходное значение флага было 0, это говорит о том, что структура данных используется другим процессом. Соответственно процесс не может обращаться к общим данным и может цикле проверять значение флага, пока не обнаружит, что структура данных свободна.

Если же исходное значение флага было отличным от 0, это означает, что структура данных свободна, тогда процесс входит в критическую секцию, очищает флаг, указывающий другим процессам, что структура данных занята. Данная операция поддерживается процессами PR RISC и совместима с архитектурами процессоров RISC.

В микропроцессорах, начиная с i8086 также используются специальные команды BTC, BTS и BTR.

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

1) этот подход очень простой, поэтому легко проверяем;

2)    применим к любому количеству процессов;

3)    может использоваться для поддержки множества критических разделов, каждый из которых может быть определен при помощи своей собственной переменной.

Недостатки:

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

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

3)    возможна взаимоблокировка.

Архитектура ОС

Наиболее общим подходом к структуризации ОС является разделение всех ее модулей на 2 группы:

1.    ядро, содержащее модули, которые выполняют основные функции ОС.

2.    модули, выполняющие вспомогательные функции ОС.

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

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

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

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

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

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

1.    утилиты (архивирование, дефрагментация…)

2.    системные обрабатывающие программы (компиляторы, компоновщики, отладчики, текстовые и графические редакторы)

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

4.    библиотеки процедур, упрощающие разработку приложений.

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

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

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

Поскольку все основные функции ОС выполняет ядро, то именно ядро работает в привилегированном режиме.

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

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

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

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

На базе 4х уровней, обеспечиваемых процессором компании Intel, ОС OS/2 строит 3х уровневую систему привилегий, а ОС Windows NT и UNIX имеют 2х уровневую систему защиты.

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

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

Барьеры

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

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

Задачи на межпроцессное взаимодействие.

Читатель- писатель. Варианты решения:

1.         Решение с помощью передачи сообщений. Предположим, что вес сообщения имеют одинаковый размер и все сообщения которые посланы, но еще не получены автоматически помещаются ОС в буфер. При решении этой задачи используются N сообщений. Читатель начинает с того, что посылает писателю N пустых сообщений. Как только у писателя оказывается элемент данных, который он может предоставить читателю, он берет пустое сообщение и отправляет полное. Т.о. общее число сообщений в системе постоянно и их можно хранить в заданном участке памяти. Если писатель работает быстрее читателя, то все сообщение будут ожидать читатель в заполненном виде, при этом писатель блокируется в ожидании пустого сообщения.  Если читатель работает быстрее писателя, то все сообщение будут ожидать писателя в пустом виде, при этом читатель блокируется в ожидании заполненного сообщения.

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

3.         Использование семафоров.
Введем два семафора:

e- число пустых буферов;

f- количество заполненных буферов.

N- общее количество буферов

p- SemSignal

v- SemWait

В исходном состоянии e= N; f=0

4.         Неправильное решение. Поток писатель. Выполняется p(e), потом проверяется, доступен p(f) ли критический ресурс, если все нормально, то выполняется запись и v(e),v(f). Поток читатель. p(f)

p(e)

v(e),v(e).

 

Блокирующие переменные

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

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

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

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

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

Динамическими, в отличие от неизменяемых фиксированных приоритетов.

Процессам, имеющим приоритет, процессорное время также может предоставляться квантами. Процессы, выполняющие ввод/вывод часто блокируются, не исчерпав своего кванта времени. Кроме того они могут осуществлять доступ к общим системным ресурсам, которые должны освобождаться как можно скорее. Когда система переводит процесс из состояния «Блокирован» в состояние «Готов», она ставит его в очередь высокоприоритетных процессов. Если процесс снова блокируется до конца своего кванта времени, система вновь ставит его в очередь высокоприоритетных процессов.

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

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

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

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

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

Диспетчеризация и приоретизация прерываний

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

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

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

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

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

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

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

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

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

Таблица прерываний Windows NT

Уровни IRQL

высший приоритет (ошибка шины) питание межпроцессорное прерывание таймер

устройство n … устройство 1

диспетчерский (DPC) (от ОС)

APC уровень системных вызовов от приложений

низший (само приложение)

		IRQL текущего кода
	заблокированные уровни запросов прерывания

Основные виды ресурсов



Реентирабельные – при прерывании модуля, его состояние сохраняется для последующего восстановления.

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

Exec запуска приложения, хранящемся

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

Файл имеет 2 признака разрешения смены ID-ра, которые разрешают смену ID-ров пользователя и группы при выполнении данного файла.

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

FCFS (первым пришел – первого обслужили).

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

Когда процесс попадает в очередь готовых, он становиться в конец очереди.

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

К достоинствам этой дисциплины относятся: простота реализации и малые расходы системных ресурсов на формирование очереди задач.

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

2.

Компоновщики и загрузчики ОС. Форматы COFF (command object file format) и PE (portable executable).

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

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

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

Различают статическое и динамическое связывание.

Статическое связывание бывает внешним и внутренним. Оно обеспечивается на стадии формирования исполняемого модуля еще до этапа выполнения программы.

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

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

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

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

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

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

Наименьшая часть объектного файла, которая подвергается перемещению – это секция. Можно рассматривать секцию как элемент COFF или PE модуля, который содержит однотипную информацию. Объектный модуль COFF начинается со структуры Image File Header. – основной заголовок – информация о типе процессора, время создания, количество секций.

Таблица секций – это массив структур Image Section Header, каждая из которых полностью описывает конкретную секцию: имя секции – физический адрес секции в модуле, размер секции и тип содержимого в секции. Кроме параметров содержимого секции в Image Section Header указывается наличие таблицы поправок для данной секции и таблицы номеров строк.

В объектном модуле COFF таблица поправок и таблица номеров строк хранятся для каждой секции внутри самой секции непосредственно после данных.

Таблица поправок представляет собой массив структур Image Relocation. Данные поправки или привязки основаны на использовании таблицы символов и используются компоновщиком для настройки связей.

Таблица номеров строк является массивом структур Image Line Number – ставит в соответствие одной строке программного кода источник ее RVA в исполняемом отображении. Таблица номеров строк является отладочной информацией.

После заголовка Image Section Header последовательно располагаются сами секции. После секции идет таблица символов, которая представляет собой массив структур Image Symbol. Каждая такая структура описывает один символ, которым может являться имя секции, имя процедуры, имя переменной, области памяти и т.д.

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



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

После таблицы символов идет таблица ASCII-Z строк, которые представляют собой длинные имена элементов таблицы символов. Если какой-то элемент таблицы символов имеет более 8 символов, то вместо самого имени в таблице символов содержится RVA на строку из таблицы ASCII-Z (zero) строк.

В простейшем случае компоновщик PE модулей выполняет простейшие функции:

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

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

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

Так как таблица символов описывает функции типа external в объектных модулях, то можно построить секцию импорта на основе анализа таблицы символов.



1.    Выявляются символы external и сопоставляются с именами функций dll.

2.    Запись в секцию имен внешних функций и имен dll где они находятся.

3.    Создание 2х массивов указателей на структуры Image_Import_by_name

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

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

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

После того, как секции созданы и произведена настройка связей можно создать заголовки Image File Header, Image Optional Header, Image Section Header, хотя некоторые поля заголовком могут заполняться в начале или во время любого этапа.

Создание секции PE из секции COFF состоит из следующих шагов:

1.    установка указателя на первую секцию первого модуля;

2.    копирование/добавление информации в создаваемую PE секцию. Если есть привязки, то происходит редактирование связей;

3.    поиск следующих секций с информацией того же типа;

4.    если такие секции есть, то установка указателя на следующую подходящую секцию текущего модуля и переход к п.2;

5.    установка указателя на следующую подходящую секцию следующего модуля, т.е. PE секция собирается из секций COFF всех объектных модулей.

Контроль доступа к файлам

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

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

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

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

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

Различают два основных подхода к определению прав доступа:

1)    Избирательный доступ, когда для каждого объекта сам владелец может определить допустимые операции с ним. Этот подход также называется произвольным или дискреционным. Дискреционная модель одно из  самых распространенных. В соответствии с ней, каждый объект является собственностью соответствующего пользователя. Этот пользователь имеет все права доступа к объекту, а иногда и права передавать часть или все права другим пользователям. Кроме того, собственник объекта определяет права доступа других субъектов к этому объекту, т.е. модель безопасности в отношение этого объекта. Указанные права записываются в виде матрицы доступа:

		O1		O2		…		On		объекты
S1		Х,Ч		З
S2		Ч,В
…
Sm
с у б ъ е к т ы

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

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

Примеры:

1.    Решение о доступе в данный момент времени основывается на анализе предыдущих доступов к другим объектам;

2.    Решение о доступе в данный момент времени основывается на динамике состояния системы, т.е. права доступа субъекта зависят от текущих прав доступа других субъектов;

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

Существует несколько вариантов задания матрицы доступа:

листы возможности- для каждого субъекта создается лист всех объектов к которому имеет доступ данный субъект;

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

Размерность матрицы зависит от количества объектов и субъектов в системе и может динамически изменяться. Для уменьшения размерности матрицы доступа могут применяться способы:

1.    Установление групп субъектов каждое, из которых представляет собой группу субъектов с одинаковыми правами;

2.    Установление групп терминалов по классам полномочий;

3.    Группировка объектов по уровням категорий;

4.    Хранение списка пар вида (o,f), где o- защищаемый объект, f-разрешение на использование его субъектом.

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

не выдерживает атак «троянского коня»;

не автоматическое создание матрицы  доступа;

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

Расширением дискреционной модель доступа является многоуровневая модель доступа (мандатный доступ) – это такой подход к определению прав доступа при котором система наделяет пользователя определенными правами по отношению к каждому разделяемому ресурсу в зависимости от того к какой группе пользователь отнесен.


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

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

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

Мандатный контроль называется обязательным т.к. его проходит каждое обращение субъекта к объекту если субъект и объект находятся под защитой системы безопасности. Для реализации мандатного контроля каждый субъект C(S) и объект C(O) имеет метку. Субъект имеет метку содержащую информацию о том какой класс доступа он имеет.

Мандатный контроль сравнивает метки и удовлетворяет запрос субъекта S к объекту О на чтение, если C(S)>C(O) и удовлетворяет запрос на запись, если C(S)<C(O).

Критическая секция программы

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

Любая возможность обеспечения поддержки взаимодействия исключений должна соответствовать следующим требования:

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

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

3)    не должна возникать ситуация бесконечного ожидания доступа к критическому разделу.

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

5)    не делается никаких предположений о количестве процессов или их относительной скорости работы.

6)    процессы остаются в критической секции только в течение ограниченного времени.

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

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

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

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

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

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

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

3)    на переключение между процессами с разделяемым адресным пространством также требуется много времени.

Многослойная структура ядра (монолитное ядро).

Ядро может состоять из следующих слоев:

1.    средства аппаратной поддержки ОС

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

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

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

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

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

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

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

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

4.    система прерываний. Позволяет реагировать на внешние события, синхронизировать выполнение процессов и устройств ввода/вывода.

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

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

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

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

Если код ОС может быть сравнительно легко перенесен с процессора одного типа на процессор другого типа и с аппаратной платформы одного типа – на другой тип, то такую ОС называют переносимой – portable.

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

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

2.    объем машинно-зависимых частей кода, который непосредственно взаимодействует с аппаратными средствами, должен быть по возможности минимизирован.

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

Не позволить другим осуществить доступ к объекту.

Встроенный администратор Win NT в отличие от суперпользователя UNIX может не иметь некоторых разрешений на доступ к объекту. Для реализации этой возможности ID-ры администратора и группы админов могут входить в ACL как и ID-ры рядовых пользователей. Но админ имеет возможность выполнить любые операции с любыми объектами, так как он всегда может стать владельцем объекта, а затем уже как владелец получить полный набор разрешений. Однако вернуть владение предыдущему владельцу объекта админ не может.

При запросе процесса некоторой операции доступа к объекту управление всегда передается монитору безопасности для сравнения ID-ров пользователя и групп из токена доступа с ID-рами в элементах ACL объекта. В отличие от UNIX в элементах ACL могут существовать как списки разрешенных, так и списки запрещенных для пользователя оперций.

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

Обход тупиков.

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

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

В точке S процессу А уже должен быть предоставлен принтер. Точка t – критическая, лежит на линии. В точке x – уже капец! Тупик!

В любой момент времени существует состояние, составленное из величин (E;A;C;R). Говорят, что состояние безопасно если оно не находится в тупике и существует некоторый порядок планирования при котором каждый процесс может работать до завершения, даже если все процессы захотят немедленно получить свое максимальное количество ресурсов.

(короче в лекциях подробнее записано!!!)

Чтобы избежать тупика можно использовать алгоритм Дейкстры (банкира).

основано на использовании квантования

Планирование в ОС OS/ 2 основано на использовании квантования и абсолютных динамических приоритетов. Определены четыре приоритетных класса: критический, серверный, стандартный и остаточный, в каждом из которых имеется 32 приоритетных уровня.

Потоки критического класса имеют наивысший приоритет. К этому классу относятся системные потоки и потоки ядра.

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

Потоки пользователя относятся к стандартному классу.

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

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

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

2)    если поток ушел на выполнение операции ввода/вывода, то после ее завершения он получит наивысшее значение приоритета своего класса.

3)    приоритет потока автоматически повысится, когда он поступит на выполнение.

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

Переключение процессов.

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

1) прерывание;

2) исключение;

3) системный вызов.

Переключение режимов.

При возникновении прерывания процессор выполняет следующие действия:

1) сохраняет контекст текущей программы;

2) загружает адрес программы обработки прерываний;

3) переключается из пользовательского режима в режим ядра.

При переключении состояния процесса ОС должна произвести определенные изменения в своей конфигурации:

1) сохранение контекста процесса;

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

3) помещение управляющего блока данного процесса в соответствующую очередь;

4) выбор следующего процесса для выполнения;

5) обновление управляющего блока выбранного процесса;

6) обновление структур данных по управлению памятью;

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

Планирование процессов и потоков

Процесс

– абстракция, описывающая выполняющиеся программы.

Для ОС процесс представляет собой единицу работы и заявку на потребление системных ресурсов.

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

Когда говорят о процессах, это означает, что ОС поддерживает их обособленность.

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

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

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

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

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

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

Потоки совместно используют адресное пространство процесса и все выделенные ему ОС ресурсы.

Планирование в системах реального времени

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

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

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

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

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

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

2)    активная задача выполнила системный вызов, связанный с запросом на ввод/вывод и на доступ к ресурсу, который в настоящий момент занят; планировщик переводит задачу в состояние ожидания и выполняет перепланирование.

3)    активная задача выполнила системный вызов, связанный с освобождением ресурса; планировщик проверяет не ожидает ли этот ресурс какая-либо задача, если да, то эта задача переводится из состояния ожидания в состояние готовности.

4)    внешнее прерывание, которое сигнализирует о завершении периферийным устройством операции ввода/вывода; планировщик переводит соответствующую задачу в очередь готовых и выполняет перепланирование.

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

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

Предотвращение тупиков.

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

1.    Если в системе нет ресурсов отданных в единоличное пользование одному процессу, то система никогда не попадет в тупик;

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

При этом возникают проблемы:

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

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

3.    Условие отсутствия перераспределения;

4.    Условие кругового/циклического ожидания. Его можно устранить несколькими способами:

Процессу предоставляется право только на один ресурс в конкретный момент времени, если нужен второй ресурс, то процесс должен освободить первый;

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

Недостаток: невозможно найти порядок предоставления ресурсов удовлетворяющий всем.

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

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

Приоритеное планирование

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

К внутренним факторам относятся:

требования к памяти;

кол-во открытых файлов;

отношение среднего времени ВВ/ВЫВ к среднему времени ЦП;

и т.д.

К внешним относятся:

важность процесса;

тип и величина файлов;

отдельно выполненную работу;

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

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

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

Проблемы проектирования

Чтобы ОС была успешно спроектирована, разработчики должны четкое представление о том, что они хотят.

Для универсальных ОС основными являются следующие 4 положения:

1.    определение абстракций

2.    представление примитивных операций

3.    обеспечение изоляций (одну программу от другой)

4.    управление аппаратурой

Сложность проектирования ОС заключается в следующем:

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

2.    ОС должны управлять параллельно выполняющимися процессами и при этом решать проблемы гонок и тупиков.

3.    ОС должна предпринимать меры против вмешательства в ее работу.

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

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

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

7.    от ОС требуется переносимость и поддержка множества устройств ввода/вывода, которые проектируются независимо друг от друга.

8.    при разработке ОС необходимо учитывать совместимость с предыдущей версией.

Разделение памяти на уровне привилегий

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

В каждом дескрипторе сегмента имеется поле, которое определяет уровень привилегий связанного с ним сегмента.

Процессоры используют схему защиты ОС и программ друг от друга, состоящую из привилегий 4-х уровней от 0 до 3.

Когда ОС подготавливает программу для запуска, она формирует в GDT или IDT дескриптор, описывающий сегмент кода программы. В этом дескрипторе в поле DPL байта доступа проставляется уровень привилегий, в котором будет работать данная программа. Получаем текущий уровень привилегий CPL. CPL копируется в поле RPL селектора сегмента кода, загруженного в регистр CS. Программа всегда может проанализировать свой текущий уровень привилегий, но не может изменить его заменой содержимого поля RPL в регистре CS.

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

Программа будет предоставлять доступ к сегментам только в случае, когда уровень привилегий дескриптора запрашиваемого сегмента

Реализация операций семафора

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

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

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

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

б)    низкоприоритетный процесс может стоять в очереди семафора перед процессом с более высоким приоритетом.

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

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

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

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



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

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

3)    Реализация семафоров на пользовательском уровне. Пользовательский поток, которому требуется доступ к общему ресурсу или синхронизация с другим пользовательским потоком, может вызвать методы SimWait() и SimSignal() класса семафора, реализованного в исполнительной системе.

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

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

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

RR («карусельная»).

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

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

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

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

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

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

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

Семафоры

Это объект с операциями SimWait() и SimSignal(). Его атрибутом обычно является целое число и очередь, а его операции определены следующим образом.

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

SimSignal() – если ни один процесс не ждет у данного семафора, увеличить целое число на единицу, в противном случае освободить один процесс и продолжить его работу с инструкции, следующей за инструкцией «ждать».

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

Синхронизация передачи сообщений.

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

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

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

Еще одной проблемой является производительность: копирование сообщений из одного процесса в другой происходит гораздо медленнее, чем операция на семафоре. Один из вариантов решения: ограничить размер сообщения до размера регистра и передавать сообщение через регистр.

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

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

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

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

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

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

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

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

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

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


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

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

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

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

Основные достоинства почтовых ящиков:

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

2.    два процесса могут обмениваться более чем одним сообщением за раз;

3.    ОС может гарантировать, что ни какой процесс не вмешается во взаимодействие других процессов;

4.    очереди буферов позволяют процессу- получателю продолжить работу, не обращая внимания на получателя.

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

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

 

Системные вызовы

Большинство ОС организуют свои функции в виде набора процедур, которые могут быть вызваны задачами.

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

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

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

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

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

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

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

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

–          системы, которые осуществляют вызовы через шлюз ловушек, могут пересылать параметры в регистрах.

SJF (или SJN).

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

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

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

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

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

Совместимость и множественные прикладные среды.

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

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

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

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

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

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

Эмуляция значительно замедляет работу программы.

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

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

Способы использования семафоров

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

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

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

2)    Условная синхронизация – два взаимосвязанных процесса должны иметь возможность синхронизировать свои действия. Процессы могут быть связаны следующим образом: при достижении процессом А определенной точки, он не может продолжить роботу, пока процесс В не выполнит некоторую задачу. Для их синхронизации можно применять инициализированный значением 0 семафор, у которого процесс А должен ждать в точке синхронизации, выполнив вызов SimWait(), пока процесс В не вызовет метод SimSignal(). Особенность данного способа применения семафора заключается в том, что вызов SimWait() выполняет один процесс, а вызов SimSignal() – другой.

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

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

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

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

Доступ к дескриптору процесса может осуществляться от имени другого процесса. Если предположить, что время выполнения операций блокировать и разблокировать фиксировано, то можно гарантировать и время выполнения операций SimWait() и SimSiganl().

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

Способы реализации прикладных программных сред.

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

ОС ОС1 кроме своих приложений  поддерживает приложения ОС2 и ОС3. Для этого в ее составе имеются специальные приложения, прикладные программные среды, которые транслируют интерфейсы чужих ОС API ЩС2 и API ОС3 в интерфейс своей родной ОС API ОС1.

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

В пространстве ядра системы размещаются прикладные программные интерфейсы всех ОС.

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

Функции каждого API реализуются ядром с учетом специфики соответствующей ОС, даже если они имеют аналогичное назначение. 

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

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

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

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

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

Такому подходу конструирования множественных прикладных сред присущи все достоинства и недостатки микроядерной архитектуры.

SRT.

Следующее задание требует меньше всего времени для своего завершения.

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

Для решения подобных проблем существует дисциплина диспетчеризации

Стратегии планирования.

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

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

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

2)                    Произошла ошибка;

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

4)                    Исчерпан квант процессорного времени, отведенный данному потоку.

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

Чем больше потоков в системе, тем больше время ожидания и тем меньше возможности вести одновременную интерактивную работу нескольким пользователям.

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

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

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

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

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

Дифференциация обслуживания при квантовании базируется на истории существования потока в системе.

Структура PE модуля

В начале PE модуля перед заголовком находится заглушка DOS, которая представляет собой минимальную DOS-программу («this program cannot run in DOS mode»).

Заголовок PE файла содержится после DOS заглушки и начинается с сигнатуры PE00.

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

За сигнатурой PE00 следует сигнатура типа Image File Header. Поля этой сигнатуры содержат только самую общую информацию о файле.

После заголовка PE файла находится таблица секций. Эта таблица содержит инфу о каждой секции отображения.

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

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

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

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

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

Поскольку PE файлы работают в 32-разрядном режиме, компоновщик объединяет все секции .text из различных объектных файлов в одну большую секцию .text в exe-файле. Кроме кода собственно программы в файле будет присутствовать дополнительный программный код в секции .text помимо того, который создается компилятором или используется из библиотек поддержки выполнения программы.

В PE файле в случае вызова функции из другого модуля инструкция CALL сгенерированная компилятором не передает управление непосредственно данной функции в DLL. Вместо этого инструкция CALL передает управление команде JMP DWORD PTR [xxxxxxxx] также находящейся в секции .text.

Команда JMP передает управление по адресу, хранящемся в двойном слове в секции .idata.  Это двойное слово содержит настоящий адрес точки входа функции ОС.

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

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

.idata содержит информацию о функциях и данных, которые модуль импортирует из других dll. Каждая функция, импортируемая PE файлом, перечислена в этой секции.



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

После загрузки, секция .idata содержит указатели функций, импортируемых exe-файлом или dll.

Секция .idata, называемая таблицей импорта, начинается с массива, состоящего из Image_Import_descriptor, каждый элемент которого соответствует одной из dll, с которой неявно связан данный PE файл.

Количество элементов в массиве нигде не учитывается, но последняя структура массива имеет поля, содержащие null.

Структура управления процессами.

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

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

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

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

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

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

Управляющий блок содержит:

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

2) регистры, доступные пользователю.

3) управляющие регистры и регистры состояния.

4) указатели на стек.

5) информацию по планированию и состоянию. Включает состояние процесса (его готовность к выполнению), приоритет, информацию о событиях.

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

7) обмен информацией между процессами.

8) привилегии процессов.

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

10) владение ресурсами и их использование

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

1) информация по идентификации процесса;

2) информация по состоянию процесса;

3) информация, использующаяся при управлении процессом.

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

Информация о состоянии процесса состоит из содержимого его регистров. В процессорах любого вида имеется регистр, называемый «слово состояния программы» (PSW).

управляющий блок процесса   Идентификатор процесса Информация о процессе Информация управления процессом Пользовательский стек Пользовательское адресное пространство Совместно используемое адресное пр-во

Типы планирования процессора.

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

Диаграмма планирования:

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

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

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

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

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

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

Планирование потоков осуществляется на основе информации, хранящейся в описателях процессов и потоков.

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

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

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

1.  Определение момента времени для системы текущего активного потока;

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

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

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

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

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

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

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

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

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

Диспетчеризация сводиться к следующему:

1) Сохранение контекста текущего потока, который требуется сменить.

2) Загрузка контекста нового потока, выбранного в результате планирования.

3) Запуск нового потока на выполнение.

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

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

1) Использование процессорного времени. В реальных системах этот показатель колеблется от 40 до 90%.

2) Время оборота. Для некоторых процессов важным критерием является полное время выполнения. Это время включает в себя время ожидания во входной очереди, время ожидания в очереди готовых процессов, время ожидания в очередях к оборудованию, время ввода-вывода и время выполнения на процессоре.

3) Время ожидания. Это суммарное время нахождения процесса в очереди готовых процессов.

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

Тупики.

При рассмотрении проблемы тупиков, понятия ресурсов системы целесообразно обобщить и разделить их все на два класса:

повторноиспользуемые (системные) типа SR;

потребляемые или расходуемые типа CR.

Повторноиспользуемый ресурс- конечное множество идентичных единиц со свойствами:

1.     число единиц ресурса постоянно;

2.    каждая единица ресурса или доступна или распределена только одному ресурсу;

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

Расходуемый ресурс обладает свойствами:

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

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

тупик:

  Р1

Послать сообщение (Р2, М1,ПЯ2)

   Ждать сообщение (Р3, М3,ПЯ1)

Р2

Послать сообщение (Р3, М2,ПЯ3)

   Ждать сообщение (Р1, М1,ПЯ2)

Р3

Послать сообщение (Р1, М3,ПЯ1)

   Ждать сообщение (Р2, М2,ПЯ3)

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

Для возникновения ситуации взаимоблокировки должны выполнится 4-е условия:

1.    Условие взаимного исключения, при котором процесс осуществляет монопольный доступ к ресурсу;

2.    Условие ожидания и удержания. Процессы в данный момент удерживающие полученные ранее ресурсы могут запрашивать новые ресурсы;

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

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

При столкновении со взаимоблокировкой используется 4-е стратегии:

1.    Пренебрежение проблемой в целом;

2.    Обнаружение и восстановление, т.е. позволить взаимоблокировке произойти, обнаружить ее и предпринять какие- либо действия;

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

4.    Предотвращение тупиков с помощью опровержения условий необходимых для взаимоблокировки.

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

Обнаружение взаимоблокировки при наличии одного ресурса каждого типа

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

Система имеет 7-6 процессов и 6 ресурсов. Состояние системы на данный момент соответствует списку:

1.    Процесс П1 занимает ресурс Р1 и хочет получить Р2;

2.    Процесс П2 ничего не использует, но хочет получить Р3;

3.    Процесс П3 ничего не использует, но хочет получить Р2;

4.    Процесс П4 занимает ресурс Р4 и хочет получить Р2 и Р3;



5.    Процесс П5 занимает ресурс Р3 и хочет получить Р5;

6.    Процесс П6 занимает ресурс Р6 и хочет получить Р2;

7.    Процесс П7 занимает ресурс Р5 и хочет получить Р4.



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

1.    Задаются начальное условие: L- пустой список(все ребра не маркированные);

2.    Текущий узел добавляется в конец списка L и проверяется количество появлений узла в списке. Если узел присутствует в двух местах, значит, граф содержит цикл и работа алгоритма завершается;

3.    Для заданного узла определяется, выходит ли из него хотя бы одно не маркированное ребро, если да то к шагу 4, нет то к 5;

4.    Выбирается любое, не маркированное исходное ребро, помечается и за тем по нему осуществляется переход к новому текущему узлу и выполняется шаг 3;

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

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

m- число классов ресурсов,

- количество ресурсов класса 1 и т.д.

- вектор существующих ресурсов.

В любой момент времени некоторые из ресурсов могут оказаться заняты следовательно, вводится понятие A- вектор доступных ресурсов, C- матрица текущего распределения, R- матрица запросов.

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



 

R- показывает сколько ресурсов может потребоваться каждому процессу.



Для обнаружения тупиков нужно составить матрицу.

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

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

Алгоритм обнаружения тупиков состоит из шагов:

1.    Ищем не маркированный процесс,  для которого i-ая строка матрицы запросов R<= A (вектора доступных ресурсов);

2.    Если такой процесс найден, то прибавляем i-ю строку матрицы текущего распределения С к вектору А, маркируем процесс и возвращаемся к шагу 1;

3.    Если таких процессов не существует, то работа алгоритма завершается.

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

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





 

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

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


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

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

UNIX. Базовая версия.

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

Процессы системного класса зарезервированы для ядра и используют стратегию фиксированных приоритетов. Уровень приоритета процессу назначается ядром и никогда не изменяется.

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

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

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

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

Управление памятью в ОС

В любой многозадачной ОС процессы взаимодействуют друг с другом и система должна поддерживать эту возможность:

1) Процессы взаимодействуют для выполнения общей задачи. Процессу может потребоваться возможность запрашивать сервисы у другого процесса и ждать выполнения соответствующих операций. Процессы могут также синхронизироваться друг с другом. Это происходит, когда один из процессов достигает точки, в которой ему нужно убедиться в выполнении другим процессом какой-либо операции и лишь затем продолжить работу. Процессу требуется операции «Ждать» для синхронизации с другим процессом или аппаратным обеспечением. Кроме того необходимы механизмы сигнализации о завершении операции, когда процесс ждет, что-то должно инициировать продолжение его работы. Причем взаимную синхронизацию необходимо осуществлять независимо от того, имеется ли у процессов общее адресное пространство или нет.

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

Для успешного взаимодействия процессов необходимо два механизма:

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

2)    взаимное исключение – «соревнующиеся» процессы должны ждать освобождения общего ресурса и сигнализировать об окончании его использования.

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

Важным понятием синхронизации процессов является понятие

Выполнить… и т.д.

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

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

Проверка разрешения доступа процесса к объекту производится в соответствии с общей схемой доступа.

При входе пользователя в систему для него создается токен доступа (access token), включающий ID пользователя и ID всех групп, в которые входит пользователь.

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

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

Владелец объекта, который его создал, обладает правом избирательного управления доступом к объекту и может изменять ACL объекта, чтобы позволить им

Windows NT

В системе 32 уровня приоритетов и 2 класса потоков: потоки реального времени (16-31) и потоки с переменным приоритетом (1-15). Приоритет 0 зарезервирован для системных целей.

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

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

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

---

---