Объекты и их дескрипторы в ОС Windows

· Объектом в ОС Windows называется структура данных, которая представляет системный ресурс (файл, поток, графический рисунок).

Категории объектов

Объекты пользовательского интерфейса	Объекты интерфейса графических устройств	Объекты ядра
User	Graphics Device Interface	Kernel
Окна, курсоры	Кисти, перья	Процессы, потоки, каналы

· Под доступом к объектам понимается возможность приложения выполнять над объектами некоторые функции.

· Для работы с объектами используются функции Win32API

Дескрипторы объектов

· Приложение не имеет прямого доступа к объектам, а обращается к ним косвенно. Для этого каждому объекту Windows ставит в соответствие дескриптор (типа HANDLE) . Дескриптор – запись таблицы, поддерживаемой системой, содержит адрес объекта и информацию о типе.

· Дескриптор создается вызовом системной функции (например, CreateThread)

Имя объекта

· При создании объекта можно указать ему имя, которое делает объект доступным всем приложениям. Такой объект ведет себя как одиночка (потому что в системе нет двух объектов с одинаковым именем)

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

· Порядок работы прикладной программы с объектами ядра:

1) Создать объект ядра посредством вызова Create, который возвращает дескриптор созданного объекта.

2) Выполнить доступ к объекту через дескриптор, используя функции интерфейса Win32API

3) Закрыть дескриптор объекта посредством вызова функции CloseHandle.

·

·

·

· !!пропуск лекции у Наташи!!

·

·

· Кроме того, введем для потоков состояния, которые обозначают:

· Существование программного кода для создания потока.

· Завершение использования потока

Диаграмма состояний потока

Завершен

Новый

Готов

Выполняется

Блокирован

Create

Unblock

Block

Exit

Run

Interrupt

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

Операции над потоками, которые выполняются самими потоками

· Операция Create выполняется потоком, который создает новый поток из функции. Эта операция переводит поток из состояния «новый» в состояние «готов».

· Операция Exit выполняется самим исполняемым потоком и завершает его. Эта операция переводит поток из состояния «выполняется» в состояние «завершен».

Операции над потоками, которые выполняются ОС

· Операция Run запускает готовый поток на выполнение, то есть потоку выделяется процессорное время. Эта операция переводит поток из состояния «готов» в состояние «выполняется». Поток получает процессорное время в том случае, если подошла его очередь к процессору на обслуживание.

· Операция Interrupt задерживает исполнение потока и переводит его из состояния «выполняется» в состояние «готов». Эта операция выполняется над потоками, если истекло процессорное время, выделенное потоку на исполнение.

· Операция Block блокирует исполнение потока, то есть переводит его из состояния «выполняется» в состояние «блокирован». Эта операция выполняется над потоком в том случае, если он ждет наступления некоторого события, например, завершения операции ввода-вывода или освобождения ресурса.

· Операция Unblock разблокирует поток, т.е. переводит его из состояния «блокирован» в состояние «готов».

Процессы

Определение процесса

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

Контекст процесса

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

· Процессу обязательно принадлежат следующие ресурсы:

– Адресное пространство процесса

– Потоки, исполняемые в контексте процесса

Адресное пространство процесса

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

· Адресные пространства разных процессов не пересекаются.

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

Взаимодействие потоков процесса

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

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

2.4 Потоки в Windows

· Потоком в Windows называется объект ядра, которому операционная система выделяет процессорное время для выполнения приложения.

Идентификация потока в Windows

· С каждым потоком в Windows связаны:

– уникальный дескриптор (HANDLE);

– уникальный идентификатор.

· Дескрипторы используются служебными программами, которые позволяют пользователям системы отслеживать работу потоков.

Контекст потока в Windows

· Каждому потоку в Windows принадлежат следующие ресурсы:

– код исполняемой функции

– набор регистров процессора

– стек для работы приложения

– маркер доступа, который содержит информацию для системы безопасности

· Все эти ресурсы образуют контекст потока в Windows.

Типы потоков в Windows

· В Windows различают потоки двух типов:

– системные потоки

– пользовательские потоки

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

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

Типы потоков в приложении

· В приложении различаются потоки двух типов:

– рабочие потоки (working threads)

– потоки интерфейса пользователя (user interface threads)

· Рабочие потоки выполняют различные задачи в приложении.

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

Первичный поток приложения

· Каждое приложение имеет, по крайней мере, один поток, который называется первичным (primary) или главным (main) потоком.

· В консольных приложениях это поток, который исполняет функция main.

· В приложениях с графическим интерфейсом это поток, который исполняет WinMain.

Функции управления потоками в Windows

ü CreateThread – один поток создает другой поток;

ü ExitThread – поток завершает свою работу;

ü TerminateThread – один поток приостанавливает исполнение другого;

ü ResumeThread – один поток возобновляет исполнение другого;

ü Sleep – поток приостанавливает свое исполнение на заданный интервал времени.

Процессы в Windows

Определение процесса в Windows

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

Идентификация процесса в Windows

· С каждым процессом в Windows связаны:

– уникальный дескриптор (HANDLE);

– уникальный идентификатор.

· Дескрипторы используются программами пользователя для управления процессами.

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

Ресурсы процесса в Windows

· Каждый процесс в Windows владеет следующими ресурсами:

– виртуальным адресным пространством

– рабочим набор страниц в реальной памяти

– первичным потоком

– маркером доступа, содержащим информацию для системы безопасности

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

Начало и завершение процесса в Windows

· Выполнение каждого процесса начинается с первичного потока.

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

· Исполнение процесса заканчивается при завершении всех его потоков.

Функции ля управления процессами в Windows

ü CreateProcess – один процесс создает другой процесс;

ü ExitProcess – процесс завершает свою работу;

ü TerminateProcess – один процесс завершает работу другого.

Дочерние процессы

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

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

2.6 Наследование дескрипторов объектов в ОС Windows

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

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

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

Установка свойства наследования дескриптора объекта

· В Windows свойство наследования объекта устанавливается двумя способами:

– функцией Create при создании объекта;

– функцией SetHandleInformation.

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

– функцию GetHandleInformation.

Решение проблемы уникального именования объектов

· Проблема: независимые процессы могут создавать различные объекты с одинаковыми именами.

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

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

3.1 Управление исполнением процессов

Использование процессов в однопрограммной ОС

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

Причины и недостатки блокировки процесса в однопрограммной ОС

· Причиной блокировки процесса в однопрограммной ОС является ожидание этим процессом завершения операций ввода-вывода.

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

Исполнение процессов в мультипрограммных ОС

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

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

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

Допущения для простоты изложения

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

· В этом случае обслуживание параллельных потоков можно отождествить с обслуживанием параллельных процессов.

· Также для простоты считаем, что компьютер имеет только один процессор.

Принципы обслуживания процессов в мультипрограммных операционных системах

· 1. Время работы процессора делится на кванты (интервалы), которые выделяются процессам для работы.

· 2. По истечении кванта времени исполнение процесса прерывается и процессор назначается другому процессу.

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

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

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

– сохранить контекст прерываемого процесса;

– восстановить контекст запускаемого процесса на момент прерывания;

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

Контекст процесса и состояние регистров микропроцессора

· Контекст процесса – это содержимое памяти, с которым работает процесс.

· Адреса оперативной памяти, состояния микропроцессора и команды микропроцессора хранятся в регистрах микропроцессора.

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

– для сохранения контекста процесса необходимо сохранять содержимое регистров микропроцессора на момент прерывания процесса;

– при восстановлении контекста процесса необходимо восстановить содержимое этих регистров.

3.2 Диспетчеризация и планирование потоков

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

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

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

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

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

Критерии оптимизации планирования и диспетчеризации процессов

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

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

· Время нахождения процесса в системе должно быть минимальным.

· Время ожидания потока в очереди должно быть минимальным.

· Время реакции системы на обслуживание заявки должно быть минимальным.

Оптимальный интервал обслуживания процессов

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

Зависимость времени исполнения процесса от его трудоемкости

· В общем случае разделение времени работы процессора между параллельными процессами позволяет:

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

– замедляет исполнение трудоемких процессов.

3.3 Алгоритмы планирования непрерываемых процессов

Непрерываемый процесс

· Предположим, что работа процесса не прерывается во время его исполнения.

· В этом случае для обслуживания процессов применяются следующие стратегии:

1. Стратегия FCFS

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

– процессы, готовые к исполнению, становятся в очередь на исполнение;

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

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

· Такое обслуживание называется FCFS (first come – first served)

2. Стратегия SPN

· Чтобы отложить обработку длинных процессов, при выборе процессов из очереди применяется стратегия SPN (shortest process next): для исполнения выбирается процесс с наименьшим ожидаемым временем исполнения.

· При использовании этой стратегии нужно решить проблему оценки времени работы процесса.

Оценка времени работы процесса

· В простейшем случае время работы процесса оценивается по следующей формуле: , где S₁ – начальное, предсказанное время исполнения процесса; T_n – действительное время работы процесса при его n-том запуске; S_n+1 – предсказанное время работы при его (n+1)-ом запуске.

3.4 Алгоритмы планирования прерываемых процессов

Прерываемый процесс

· Предположим, что исполнение процесса может быть прервано по истечении кванта времени процессора, выделенного этому процессу (потоку этого процесса)

· Кроме того, предположим, что все процессы имеют одинаковый приоритет.

· В этом случае для обслуживания процессов применяются следующие стратегии.

1. Стратегия RR

«пропуск лекции»

Функции для динамического управления потоками

· Для динамического управления приоритетами потоков в Windows предназначены следующие функции:

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

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

– SetThreadPriorityBoost – позволяет отменить или установить режим динамического изменения базового приоритета только одного потока;

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

3.8 Задачи на обслуживание непрерываемых потоков

Задача 1.

· ОС обслуживает процессы по алгоритму FCFS (First Come – First Served).

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

Номер процесса
Время поступления в систему
Время исполнения

· Требуется вычислить

– среднее время нахождения процесса в системе;

– среднее время ожидания процесса в очереди на исполнение

· Обозначения: Г – процесс готов к исполнению; И – процесс исполняется.

И

И

И

И

И

Г

Г

Г

И

И

И

И

Г

Г

Г

Г

Г

Г

И

И

И

И

И

И

Г

Г

Г

Г

Г

Г

Г

Г

Г

Г

И

Г

Г

Г

Г

Г

Г

Г

Г

Г

И

И

И

Среднее время нахождения процесса в системе 47/5 = 9,4.

Среднее время нахождения процесса в очереди на исполнение 28/5 = 5,6.

Задача 2.

· ОС обслуживает процессы по алгоритму SPN (Shortest Process Next)

· В ОС поступают процессы, указанные в задаче 1.

И

И

И

И

И

Г

Г

Г

И

И

И

И

Г

Г

Г

Г

Г

Г

Г

Г

Г

Г

И

И

И

И

И

И

Г

Г

Г

Г

И

Г

Г

Г

И

И

И

Среднее время нахождения процесса в системе 39/5 = 7,8.

Среднее время нахождения процесса в очереди на исполнение 20/5 = 4.

3.9 Задачи на обслуживание прерываемых процессов

Задача 3.

· ОС обслуживает процессы по алгоритму RR (Round-robin)

· В ОС поступают процессы, указанные в задаче 1.

· Предполагается, что

– переключение контекстов процессов выполняется мгновенно;

– каждому процессу для исполнения выделяется два кванта времени;

– прерванные процессы становятся в очередь раньше новых процессов.

И

И

И

И

Г

Г

Г

Г

И

Г

Г

И

И

Г

Г

Г

Г

И

И

Г

Г

Г

И

И

Г

Г

Г

Г

Г

Г

И

И

Г

И

И

Г

Г

Г

Г

И

Г

Г

Г

Г

Г

И

И

Г

Г

И

Среднее время нахождения процесса в системе 50/5 = 10.

Среднее время нахождения процесса в очереди на исполнение 31/5 = 6,2.

Синхронизация потоков

4.1 Атомарные действия (операции)

Определение действия и контекста действия

· Действием называется изменение контекста потока.

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

Определение атомарного действия

· Действие называется атомарным или непрерывным, или непрерываемым, если оно удовлетворяет двум требованиям:

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

– контекст действия изменяется только самим действием.

Группы атомарных действий: Элементарные и Составные

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

· На практике к элементарным действиям относятся команды микропроцессора

– которые выполняются за один цикл работы микропроцессора;

– при выполнении которых блокируется обработка прерываний.

Атомарные команды микропроцессора

· Условно считают, что атомарными являются следующие команды микропроцессора:

– операции над данными, хранящимися в регистрах микропроцессора;

– операции чтения данных из памяти в регистрах микропроцессора;

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

Маскирование прерываний

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

disable_interrupt();

составное действие;

enable_interrupt();

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

4.2 Частные и разделяемые переменные

Определение частной и разделяемой переменной

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

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

Доступ параллельных потоков к разделяемым переменным

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

Примеры атомарных и неатомарных действий

shared x, y;

private a, b;

a = x; //атомарное

y = b; //атомарное

x = x+1; //неатомарное

++a; //атомарное

x =a; //атомарное

x = y; //неатомарное

4.3 Параллельные потоки

Параллельные и псевдопараллельные потоки

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

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

Обмен сигналами между параллельными потоками

· Мы рассматриваем параллельные потоки как программы, параллельно исполняемые на одном компьютере.

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

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

Аксиомы параллельности

· Аксиома 1 (Non-interference postulate) Параллельные потоки, которые не имеют общих разделяемых переменных, не взаимодействуют (интерферируют) друг с другом.

· Аксиома 2 (Atomicity postulate) Операции чтения и записи значения частной переменной потока в разделяемые переменные являются атомарными.

· Аксиома 3 (Interleaving postulate – постулат чередования) Результатом исполнения псевдопараллельных (конкурирующих) потоков является последовательность атомарных действий этих потоков.

Гонка потоков

· Если результат исполнения псевдопараллельных потоков зависит от последовательности атомарных действий, исполняемых этими потоками, то говорят, что эти потоки находятся в состоянии гонки (race condition).

· Как правило, состояние гонки является причиной ошибок работы многопоточных приложений.

· Причиной состояния гонки потоков является неправильная синхронизация этих потоков.

4.4 Определение синхронизации

Определение синхронизации

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

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

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

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

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

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

· Такое атомарное действие называется условным.

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

Обозначение условного атомарного действия

· Введем для условного атомарного действия следующее обозначение:

<await(условие) действие>

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

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

· Условное атомарное действие выполняется следующим образом:

– оператор await ждет до тех пор, пока значение условия не станет истинным;

– как только условие стало истинным, выполняется действие.

· В общем случае не существует эффективной реализации условного атомарного действия.

· Поэтому на практике рассматривают его частные случаи.

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

· Взаимное исключение, <await(true) действие > := <действие>

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

· Этот случай называют взаимным исключением.

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

Частные случаи условного атомарного действия: условная синхронизация

· Условная синхронизация, <await(условие)>

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

· Этот случай называется условная синхронизация.

4.5 Проблема взаимного исключения

Формулировка проблемы

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

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

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

Требования к решению задачи взаимного исключения

1. Безопасность (safety requirement) – в любой момент времени в критической секции может находиться только один поток.

2. Поступательность (progress requirement) – любой поток должен находиться в критической секции ограниченное время (нет тупиков).

3. Справедливость (fairness requirement) – любой поток получает доступ в критическую секцию за ограниченное время (нет голодания).

· Можно отметить, что из выполнения требования 3 следует выполнение требования 2.

· Однако требование 3 иногда невозможно выполнить.

· В этом случае доказывают, что решение задачи удовлетворяет только требованию 2.

4.6 Программное решение проблемы взаимного исключения

· Программное решение проблемы взаимного исключения для двух параллельных потоков было впервые дано Петерсоном (Peterson G.L. 1981)

Алгоритм Петерсона

bool x1, x2;

int q //обеспечивает ассиметричное решение задачи взаимного исключения

x1 = false;

x2 = false;

void thread1() {

while (true)

{

noncriticalSection1();

x1 = true; //поток 1 хочет войти в критическую секцию

q = 2; //но сначала предоставляет право входа потоку 2

while (x2 &&q == 2); //идет ожидание

criticalSection1();

x1 = false;

} }

void thread2() {

while (true)

{

nonCriticalSection2();

x2 = true;

q = 1;

while(x1 && q == 1);

criticalSection2();

x2 = false;

} }

Доказательство правильности алгоритма Петерсона

– 1. Безопасность.

Поток thread1 находится в критической секции 1 только в том случае, если выполняется условие: ((x₂ & q == 2) ≡ 0) => (not(x₂ & q==2) ≡ 1) => (not(x₂) | not(q==2) ≡ 1) => (not(x₂) | q==1 ≡ 1). Кроме того, если поток thread1 находится в критической секции 1, то выполняется условие (x₁ == true) ≡ 1 Определим следующий предикат: Q1 = x₁ & (notx₂ | q == 1) который является инвариантом критической секции 1, т.е. если поток thread1 находится внутри критической секции 1, то выполняется условие Q1 = 1. Аналогично, введем инвариант для критической секции 2: Q2 = x₂& (notx₁ | q == 2). Теперь рассмотрим предикат:

Q1&Q2 ≡ (x₁ & (notx₂ | q == 1)) & (x₂& (notx₁ | q == 2)) ≡ (x1 &x2) & (notx₁ | q == 2) & (notx₂ | q == 1) ≡ (x₁ & x₂) & ((notx₁ & notx₂) | (notx₁ & q == 1) | (notx₂ & q==2) | (q == 1 & q == 2)) ≡ (x1 & x2 & notx₁ & notx₂) | (x₁ & x₂ & notx₁ & q == 1) | (x₁ & x₂ & notx₂ & q==2) ≡ 0.

В результате получили, что Q1&Q2 ≡0. Следовательно, потоки thread1 и thread2 не могут одновременно находиться в своих критических секциях.

– 2. Поступательность.

Поток thread1 может быть заблокирован только при условии, если (x₂&q==1) ≡ 1. Аналогично, поток thread2 может быть заблокирован только при условии (x₁&q==2) ≡ 1. Рассмотрим предикат

(x₂&q==2)&(x₁&q==1) ≡ x₁&x₂&q==1&q==2 ≡ 0

Следовательно, потоки thread1 и thread2 не могут быть заблокированы одновременно.

– 3. Справедливость

Предположим обратное, т.е., что поток thread1 заблокирован.

Тогда выполняется условие (x₂&q==2) ≡1. Отсюда следует, что x₂ ≡1 & (q==2) ≡1.

Но из пункта 2 следует, что поток thread2 не может быть заблокирован одновременно с потоком thread1.

Откуда следует, что выполняется условие (x₁ & q==1) not≡ 1.

Следовательно, поток thread2 пройдет цикл while и установит значения x₂ = false или q=1 что противоречит предположению.

Значит предположение неверно. Поэтому требование справедливости тоже выполняется.

4.7 Программное решение условной синхронизации

Решение проблемы условной синхронизации для двух потоков

bool event;

event = false;

void thread1()

{

beforeEvent1();

while(!event);

afterEvent1();

}

void thread2()

{

beforeEvent2();

event = true; //установить событие

afterEvent2();

}

· Очевидно, что поток thread1 выполнит функцию afterEvent1 только в том случае, если поток thread2 установит истинным значение переменной event.

4.8 Непрерываемые (атомарные) команды микропроцессора

Определение атомарных команд микропроцессора

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

· При исполнении такой команды микропроцессор «запирает» (закрывает доступ) шину передачи данных.

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

Команда xchg

· В микропроцессоре Intel x86 существует команда xchg (а в настоящее время и много других команд), которая не прерывается во время своего исполнения и реализует следующую функцию:

void xchg(register int r, int* x)

{

register int temp;

temp = r;

r = *x;

*x = temp;

}

Решение проблемы взаимного исключения для N-параллельных потоков

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

Решение

int lock = 0;

void thread()

{

while(true)

{

int key=1; //ключ для входа в критическую секцию

while(key==1) //ждем пока вход закрыт

xchg(key, &lock);

criticalSection();

lock =0;

nonCriticalSection();

} }

Доказательство правильности работы алгоритма

· 1. Безопасность. Доказываем от противного. Предположим, что key_i = 0 и key_j = 0 при некоторых i<>j. Это может быть только в том случае, если одна команда xchg прервала исполнение другой такой команды. Но это невозможно, так как эта команда атомарная. Следовательно, наше предположение неверно, и в критической секции может находиться только один из потоков.

· 2. Поступательность. Доказываем от противного. Предположим, что все потоки выполняют циклы while(key==1) xchg(key, &lock); Отсюда следует, что ∑key_i + lock = n+1. Но это невозможно, так как величина ∑key_i + lock = n является инвариантом в силу атомарности команды xchg. Следовательно, тупик невозможен.

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

Занятие ожиданием

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

· Поэтому все эти алгоритмы синхронизации получили общее название занятие ожиданием (busy waiting).

Спин-лок

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

· Цикл ожидания while с атомарными командами микропроцессора называется спин-локом, или спин-блокировкой, или активным ожиданием (spin lock, live lock).

Примитивы синхронизации

5.1 Примитив синхронизации и блокировка потоков

Определение примитива синхронизации

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

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

Блокировка потоков

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

· При этом предположим, что микропроцессор имеет только одно ядро.

· В этом случае атомарность действий можно обеспечить посредством запрещения прерываний.

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

Очередь потоков

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

Спецификация очереди блокированных потоков

class ThreadQueue

{

Thread* tp;

public:

ThreadQueue():tp(NULL){}

~ThreadQueue(){…}

void enqueueThread(Thread& t);

bool dequeueThread();

};

void ThreadQueue::enqueueThread(Thread& t)

{

includeThreadToList(t);

t.suspendThread();//заблокировать

}

bool ThreadQueue::dequeueThread()

{

Thread t;

if (!tp)

return false;

else

{

t = excludeThreadFromQueue();

t.resumeThread();//возобновить

return true;

}

}

5.2 Примитив синхронизации Lock(замок)

Схема реализации примитива синхронизации Lock

class Lock

{

bool free;

ThreadQueue tq;

public:

Lock(): free(true){}

~Lock(){…}

void acquire();//закрываем замок

void release();//открываем замок

};

void Lock::acquire()

{

disableInterrupt();

if(!free)

tq.enqueueThread(currentThread());

else

free = false;

enableInterrupt();

}

void Lock::release()

{

disableInterrupt();

if(!tq.dequeueThread())

free = true;

enableInterrupt();

}

Решение проблемы взаимного исключения при помощи примитива синхронизации Lock

· Для этого рассмотрим следующие потоки

Lock lock; void thread1() { beforeCS1(); lock.acquire(); cS1(); lock.release(); afterCS1(); }

Lock lock; void thread2() { beforeCS2(); lock.acquire(); cS2(); lock.release(); afterCS2(); }

Аналоги примитива Lock в Windows

· В операционной системе Windows аналогами примитива синхронизации Lock являются примитивы синхронизации CRITICAL_SECTION, Mutex.

5.3 Примитив синхронизации Condition

Схема реализации примитива синхронизации Condition

class Condition

{

bool event;

ThreadQueue tq;

public:

Condition():event(false){}

~Condition(){…}

void wait();//ждем выполнения условия

void signal(); //сигнализируем о выполнении условия

};

void Condition::wait()

{

disableInterrupt();

if(event)

event = false;

else

tq.enqueueThread(currentThread());

enableInterrupt();

}

void Condition::signal()

{

disableInterrupt();

if(!tq.dequeueThread())

event = true;

enableInterrupt(); }

Решение задачи условной синхронизации при помощи примитива синхронизации Condition

· Для этого рассмотрим следующие потоки

Condition c;

void thread1)

{

beforeCS1();

c.wait();

afterCS1();

}

void thread2()

{

beforeCS2();

c.signal();

afterCS2();

}

Решение проблемы взаимного исключения при помощи примитива синхронизации Condition

Condition c;

c.signal();//начальное состояние сигнальное

void thread1()

{

beforeCS1();

c.wait();

cS1();

c.signal();

afterCS1();

}

void thread2()

{

beforeCS2();

c.wait();

cS2();

c.signal(;

afterCS2();

}

Аналог примитива Condition в Windows

· В ОС Windows аналогом примитива синхронизации Condition является Event

5.4 Семафоры Дейкстры

· Семафор – это неотрицательная целочисленная переменная, значение которой может изменяться только при помощи атомарных операций.

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

Операции над семафорами

· Пусть s – семафор, тогда над ним можно определить следующие атомарные операции: p(s) – захватить семафор; v(s) – освободить семафор.

p(s) { if s > 0 then s = s – 1; else wait;} v(s) { if somebody is waiting release one; else s = s -1; }

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

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

Определения семафора Дейкстры

· Семафор, с операциями p и v называется семафором Дейкстры, голландского математика, который первым использовал семафоры для решения задач синхронизации.

Сильный и слабый семафоры

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

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

Двоичный и считающий семафоры

· Семафор, который может принимать только значения 0 или 1, называется двоичным или бинарным семафором.

· Семафор, который может быть больше 1, обычно называется считающим семафором.

Решение проблемы взаимного исключения для двух потоков при помощи семафора

Semaphor s = 1; //семафор свободен

void thread1() { beforeCS1(); P(s); //захватить CriticalSection1(); V(s); //освободить afterCS1(); }

void thread2() { beforeCS2(); P(s); //захватить CriticalSection2(); V(s); //освободить afterCS2(); }

Решение проблемы условной синхронизации для двух потоков при помощи семафора

Semaphor s = 0; //семафор занят

void thread1() { beforeEvent1(); P(s); //ждать afterEvent1(); }

void thread2() { beforeEvent2(); V(s); //сигнал afterEvent2(); }

5.5 Примитив синхронизации семафор

Схема реализации примитива синхронизации семафор

class Semaphore

{

int count; //счетчик

ThreadQueue tq; //очередь потоков

public:

Semaphore(int& n): count(n){}

~Semaphore() {...}

void wait(); //закрыть семафор

void signal(); //открыть семафор

};

void Semaphore::wait()

{

disableInterrupt();

if (count > 0)

--count;

else

tq.enqueueThread(currentThread());

enableInterrupt();

}

void Semaphore::signal()

{

disableInterrupt();

if (!tq.dequeueThread())

++count;

enableInterrupt();

}

5.6 Объекты синхронизации и функции ожидания в Windows

Объекты синхронизации

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

Классификация объектов синхронизации

· Объекты синхронизации могут быть разбиты на три класса:

– собственно объекты синхронизации, которые служат только для решения проблемы синхронизации параллельных потоков. К таким объектам синхронизации в Windows относятся мьютекс(Mutex), событие(Event), семафор(Semaphore).

– ожидающий таймер (waitable timer).

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

Функции ожидания

· Функции ожидания в Windows – это такие функции, которые используются для блокировки исполнения потоков в зависимости от состояния объекта синхронизации, который является параметром функции ожидания.

· При этом блокировка потоков выполняется следующим образом:

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

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

Функции ожидании в Windows

· WaitForSingleObject – ждет перехода в сигнальное состояние одного объекта синхронизации.

· WaitForMultipleObjects – ждет перехода в сигнальное состояние одного или нескольких объектов из массива объектов синхронизации.

5.7 Критические секции в Windows

Назначение объекта «критическая секция»

· Для решения проблемы взаимного исключения для параллельных потоков, выполняемых в контексте одного процесса, в ОС Windows предназначены объекты типа CRITICAL_SECTION.

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

Функции для работы с объектами типа CRITICAL_SECTION

· InitializeCriticalSection – инициализация объекта;

· EnterCriticalSection – вход в критическую секцию;

· TryEnterCriticalSection – попытка входа в критическую секцию;

· LeaveCriticalSection – выход из критической секции;

· DeleteCriticalSection – завершение работы с объектом.

5.8 Мьютексы в Windows

Назначение мьютексов

· Для решения проблемы взаимного исключения для параллельных потоков, выполняющихся в контексте разных процессов, в ОС Windows предназначен объект ядра мьютекс (mutex).

· Мьютекс находится в сигнальном состоянии, если он не принадлежит ни одному потоку. В противном случае мьютекс находится в несигнальном состоянии.

· Одновременно мьютекс может принадлежать только одному потоку.

Функции для работы с мьютексами

· CreateMutex – создание мьютекса;

· OpenMutex – получение доступа к существующему мьютексу;

· ReleaseMutex – освобождение мьютекса (переход мьютекса в сигнальное состояние);

· WaitForSingleObject или WaitForMultipleObjects – захват мьютекса (ожидание сигнального состояния мьютекса)

5.9 События в Windows

Назначение событий

· В ОС Windows события описываются объектами ядра Event.

· Объекты типа Event предназначены для решения задачи условной синхронизации.

Типы событий

· В Windows различают два типа событий: с ручным и с автоматическим сбросом.

События с ручным сбросом

· Событие с ручным сбросом можно перевести в несигнальное состояние только посредством функции ResetEvent;

События с автоматическим сбросом

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

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

Функции для работы с событиями

· CreateEvent – создать событие;

· OpenEvent – получение доступа к существующему событию;

· SetEvent – переход в сигнальное состояние;

· ResetEvent – переход в несигнальное состояние;

· PulseEvent – освобождение нескольких потоков, ждущих событие с ручным сбросом;

· WaitForSingleObject, WaitForMultiplyObject – ожидание наступления событий;

5.10 Семафоры в Windows

Назначение семафоров

· Семафоры в Windows описываются объектом ядра Semaphore.

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

· Семафор называют универсальным примитивом.

Состояния и значения семафора

· сигнальное состояние – значение больше 0

· несигнальное состояние – значение =0

Функции для работы с семафорами

· CreateSemaphore – создать;

· OpenSemaphore – получить доступ к существующему;

· ReleaseSemaphore – «+1»;

· WaitForSingleObject, WaitForMultiplyObject – ожидание перехода семафора в сигнальное состояние, «-1»;