SPO_VM_konspekt

Поток создается функцией CreateThread.

При переключении контекста сохраняются: 1) программный счетчик; 2) регистр состояния; 3) остальные регистры; 4) указатели на стек ядра и стек пользователя; 5) указатель на каталог таблиц страниц процессов.

11

Лекция №4 (17.03.2012): Планирование

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

Моменты для принятия решения:

события, связанные с освобождением процессора:

-завершение кванта времени текущего потока;

-переход потока в состояние блокировки;

-завершение потока.

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

-создание потока;

-выход из состояния блокировки;

-изменение приоритета какого-либо потока.

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

4.1.Приоритеты

ВОС Windows реализовано вытесняющее приоритетное планирование. Это означает, что каждому потоку присваивается определенное числовое значение, в соответствии с которым ему выделяется процессорное время. Потоки с одинаковым приоритетом планируются по алгоритму Round Robin (Карусель).

Всистеме предусмотрено 32 уровня приоритетов. Приоритеты из группы 16-31 считаются приоритетами реального времени. Приоритеты 1-15 – обычные потоки. Нулевой приоритет зарезервирован для системного потока обновления страниц (IDLE).

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

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

12

4.2.Динамическое повышение приоритета

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

4.3.Планирование в условиях многопроцессорности

У каждого потока имеется маска привязки к процессору (affinity mask), указывающая на каких процессорах можно выполнять данный поток. По умолчанию Windows поддерживает нежесткую привязку (soft affinity). Это означает, что при выборе процессора некоторое преимущество имеет тот процессор, на котором последний раз выполнялся поток, чтобы можно было повторно использовать данные из кэша процессора. Также в блоке ядра потока хранится номер идеального процессора, который предпочтителен для выполнения данного потока. Идеальный процессор выполняется случайным образом при создании потока. Готовый к выполнению поток система пытается запустить на простаивающем процессоре. Если таких несколько, предпочтение отдается идеальному, а затем последнему, на котором выполнялся поток.

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

13

Лекция №5 (24.03.2012): Межпроцессный обмен

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

Организация связи между процессами предполагает определение следующих характеристик:

1)направление связи

∙однонаправленная связь (симплексная);

∙двунаправленная связь бывает полудуплексная (half duplex) – одновременно передача информации может идти только в одном направлении и полнодуплексная – одновременный обмен информацией в обоих направлениях.

2)тип адресации

∙прямая адресация – информация посылается непосредственно получателю;

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

3)модель передачи данных

∙потоковая модель;

∙модель сообщений.

4)объем передаваемой информации для выделения буфера соответствующего размера;

5)синхронность обмена данными – если отправитель блокируется до получения ответа адресатом, то обмен считается синхронным, иначе – несинхронным.

5.1.Способы межпроцессного обмена

Рисунок 5.1 - Способы межпроцессного обмена

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

5.2. Разделяемые ресурсы

14

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

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

5.3. Каналы связи

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

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

Рисунок 5.2 - Взаимодействие через канал

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

5.4. Создание каналов в Windows. Анонимные каналы

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

5.5. Именованные каналы

15

Именованные каналы являются объектом ядра, позволяющим организовать межпроцессный обмен не только в одной вычислительной системе, но и в локальной сети. Являются полнодуплексными средствами связи, могут использовать как потоковую модель передачи данных, так и модель сообщений. Обмен данными может быть синхронным и асинхронным. Такие каналы должны иметь уникальные имена в пределах локальной сети, имена должны соответствовать правилам именования ресурсов в сетях Windows (UNC Universal Naming Convention). В соответствии с таким правилом имя канала выглядит: \\server\pipe\PipeName1 (server - имя компьютера в локальной сети). Если отображение происходит в рамках одной вычислительной системы: \\.\pipe\PipeName1.

Именованный канал создается при помощи функции CreateNamedPipe. После создания канала сервер вызывает функцию ConnectNamedPipe и ждет отклика от клиентов, которые соединяются с каналом при помощи функции CallNamedPipe или

CreateFile.

16

Лекция №6 (31.03.2012): Синхронизация потоков

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

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

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

6.1. Способы синхронизации потоков. Переменная-замок

Одним из возможных не вполне корректных решений проблемы синхронизации является использование переменной-замка. Например, можно сделать условием вхождения в критическую секцию значение 0 некоторой разделяемой переменной lock. Сразу же после проверки это значение меняется на 1 (закрытие замка). При выходе из критической секции замок открывается (значение переменной lock сбрасывается в 0).

shared int lock; while(1)

{

while(lock); lock = 1; KO();

lock = 0; non_KO();

}

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

6.2. TSL-команды

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

int TSL(int lock)

{

17

if(lock)

lock=1; return lock;

}

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

6.3. Семейство Interlocked-функций

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

6.4. Спин-блокировка

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

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

6.5.Функции Critical Section

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

EnterCriticalSection();

LeaveCriticalSection();

Вкачестве параметра используют структуру типа CRITICAL_SECTION.

CRITICAL_SECTION CS; void SecondThread()

{

…

EnterCticalSection() …; KO LeaveCriticalSection()

…

}

main()

18

{

…

CreateThread(… SecondThread, …);

…

EnterCriticalSection(CS);

…

}

Функции EnterCriticalSection() и LeaveCriticalSection() реализованы на основе Interlocked-функции, выполняются атомарно и очень быстро. В случае невозможности входа поток переходит в состояние ожидания. Когда возможность входа появится, поток будет разбужен и повторит попытку входа. Механизм пробуждения реализован с помощью объекта ядра «событие». Чтобы функция входа в случае необходимости выполняла заданное число циклов спин-блокировки, критическую секцию необходимо проинициализировать с помощью функции InitializeCriticalSectionAndSpinCount().

6.6. Синхронизация потоков с использованием объектов ядра

Рассмотренные ранее критические секции подходят для синхронизации потоков одного процесса, синхронизацию разных процессов принято решать с помощью объектов ядра. Несмотря на простоту, использование объектов связано с переходом в режим ядра, что существенно медленнее критических секций. Почти все объекты подходят для синхронизации в контексте этой задачи, о каждом объекте можно сказать, находится он в свободном сигнальном состоянии, либо занятом. Например, если объект «поток» выполняется, то он находится в занятом состоянии. Потоки находятся в состоянии ожидания, пока связанные с ними объекты заняты. Как только объект освобождается, ОС самостоятельно будит поток и позволяет продолжить выполнение. Для приостановки потока используется функция WaitForSingleObject(hObject object, dw miliSec).

6.7. Семафоры

Семафоры – целочисленная переменная из пространства ядра, доступ к которой после инициализации осуществляется через две атомарные функции: wait и signal (up/down). В Windows это WaitForSingleObject, ReleaseSemaphore.

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

6.8. Мьютексы

Также являются объектом ядра, но могут регулировать доступ только к одному ресурсу и не содержат счетчиков, ведут себя как критические секции, но могут регулировать доступ потоков разных процессов. Создаются с помощью функции CrеateMutex, вход с помощью WaitForSingleObject, а выход RelеaseMutex.

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

6.9. События

19

Объекты «события» являются наиболее примитивными объектами ядра и предназначены для информирования одного потока другим по окончании какой-либо операции. Создаются с помощью функции CreateEvent. В занятое состояние переводится функцией WaitForSingleObject, в свободное состояние – SetEvent.

6.10. Синхронизация в ядре

Одна из проблем синхронизации связана с тем, что код ядра работает на высоких IRQL. Это означает, что традиционные средства синхронизации, связанные с блокировкой

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

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

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

20