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

Министерство образования и науки Российской Федерации

ФГБОУ ВПО «Челябинский государственный педагогический университет»

КАФЕДРА ИНФОРМАТИКИ И МЕТОДИКИ ПРЕПОДАВАНИЯ ИНФОРМАТИКИ

Квалификационная работа

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

И.о. зав. кафедрой

… / Рузаков А.А./

" … " … 2012 г.

Руководитель:

к.п.н., доцент

… / Рузаков А.А./

" … " … 2012 г.

Автор работы:

студент группы 591

Попков Данила Игоревич Работа защищена с оценкой

" … " … 2012 г.

Челябинск, 2012

• Введение 2
• Глава 1. Теоретические основы синхронизации процессов 6
• 1.1 Назначение операционной системы 6
• 1.2 Понятие процесса и потока 7
• 1.3 Свойства процессов и потоков 7
• 1.4 Определение процесса и потока 11
• 1.5 Создание процессов и потоков 12
• 1.6 Эффективность концепции потоков для параллельных вычислений 15
• 1.7 Необходимость синхронизации и гонки 17
• 1.8 Проблема взаимного исключения 20
• 1.9 Требования к алгоритмам синхронизации 23
• 1.10 Алгоритмы синхронизации 24
• 1.10.1 Запрет прерываний 24
• 1.10.2 Переменная-замок 25
• 1.10.3 Алгоритм Петерсона 25
• 1.10.4 Алгоритм булочной (Bakery algorithm) 27
• 1.11 Взаимное исключение на примере монитора 29
• 1.12 Взаимное исключение на примере семафора 32
• 1.13 Семафоры в Windows 35
• Выводы по главе 1 39
• Глава 2. Элективный курс «Процессы в операционной системе Windows» 40
• 2.1 Методика изучения элективного курса 40
• 2.2 Программная поддержка элективного курса «Процессы в ОС Windows» 65
• 2.3 Апробация результатов исследования в средней школе 69
• Выводы по главе 2 70
• Заключение 71
• Список литературы 72
• Приложение 73

операционная система windows элективный курс

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

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

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

Объект исследования: алгоритмы и механизмы синхронизации.

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

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

1. Определить разницу между понятиями процесс и поток.

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

3. Разработать и адаптировать школьный элективный курс по изучению процессов в операционной системе Windows в школе для 10−11 классов.

4. Разработать программно-методическую поддержку элективного курса в виде электронного пособия «Процессы в ОС Windows».

5. Составить методические рекомендации по курсу для учителей.

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

Научная новизна работы состоит в том, что:

1. Рассмотрены основные алгоритмы и механизмы синхронизации, такие как «алгоритм Петерсона», «алгоритм булочной», «монитор» и «семафор».

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

3. Разработан элективный курс «Процессы в операционной системе Windows» и программно-методическая поддержка к нему.

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

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ СИНХРОНИЗАЦИИ ПРОЦЕССОВ

1.1 Назначение операционной системы

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

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

Рис. 1. Функции операционной системы

1.2 Понятие процесса и потока

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

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

1.3 Свойства процессов и потоков

Любая работа вычислительной системы заключается в выполнении определенного программного кода. Чтобы этот программный код мог быть выполнен, его необходимо загрузить в оперативную память, возможно, выделить некоторое место на диске для хранения данных, предоставить доступ к устройствам ввода-вывода, например к последовательному порту для получения данных по подключенному к этому порту модему; и т. д. В ходе выполнения программе может также понадобиться доступ к информационным ресурсам, например файлам, портам TCP/UPD. И для выполнения программы необходимо предоставление ей процессорного времени, то есть времени, в течение которого процессор выполняет коды данной программы.

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

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

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

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

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

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

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

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

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

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

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

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

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

· Отдельное виртуальное адресное пространство

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

· Начальные параметры запуска — аргументы запуска, рабочую папку и т. п.

· Набор привилегий на доступ к системным ресурсам и вызовам

· Текущее состояние, включая статус процесса Набор потоков, выполняющих код программы в адресном пространстве процесса, имеющих доступ к общим ресурсам процесса

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

· Счетчик команд — указатель на текущую выполняемую команду

· Регистры — значения регистров процессора в текущий момент времени

· Стек

· Состояние Для конкретной операционной системы определение процесса может быть лаконичнее, так как опирается на конкретные механизмы этой системы, например:

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

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

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

Создать процесс — это прежде всего означает создать описатель процесса, в качестве которого выступает одна или несколько информационных структур, содержащих все сведения о процессе, необходимые операционной системе для управления им. В число таких сведений могут входить, например, идентификатор процесса, данные о расположении в памяти исполняемого модуля, степень привилегированности процесса (приоритет и права доступа) и т. п. Примерами описателей процесса являются блок управления задачей (ТСВ — TaskControlBlock) в OS/360, управляющий блок процесса (РСВ — ProcessControlBlock) в OS/2, дескриптор процесса в UNIX, объект-процесс (object-process) в Windows NT.

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

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

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

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

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

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

Для создания потока используется функция CreateThread. Синтаксис функции CreateThread:

HANDLE CreateThread (lpsa: LPSECURITY_ATTRIBUTES; cbStack: DWORD; lpStartAddr: LPTHREAD_START_ROUTINE; lpvThreadParam: LPVOID; fdwCreate: DWORD; lpIDThread: LPVOID);

Параметр lpsa — это указатель на структуру, задающую нестандартные дескрипторы защиты. Значение параметра lpsa NULL указывает на стандартные атрибуты защиты.

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

DWORD ThreadFunc (lpvThreadParam: LPVOID) {

…

return (dwResult);

}

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

Параметр fdwCreate — дополнительные флаги управления потоком. Флаг — CREATE_SUSPENDED указывает системе создать поток и приостановить его выполнение. Возобновить выполнение потока может родительский поток вызовом функции ResumeThread(HANDLE), передав ей в качестве параметра описатель, возвращённый функцией создания потока. Вообще родительский поток может в любое время остановить поток вызовом функции SuspendThread(HANDLE), и возвратить его к выполнению приведённой выше функцией ResumeThread(HANDLE). В структуре управления потоком есть переменная SuspendCount, в которой запоминается количество вызовов SuspendThread, а вызов ResumeThread уменьшает эту переменную на единицу. Как только она примет нулевое значение поток возобновляет выполнение.

Последний параметр lpIDThread — адрес переменной типа двойного слова, в которую будет записан уникальный идентификатор потока.

1.6 Эффективность концепции потоков для параллельных вычислений

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

Рис. 2. Сравнение многопоточной системы с однопоточной

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

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

Введение

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

1.7 Необходимость синхронизации и гонки

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

1. Считать из файла базы данных в буфер запись о клиенте с заданным идентификатором.

2. Внести новое значение в поле Заказ (для потока А) или Оплата (для потока В).

3. Вернуть модифицированную запись в файл базы данных.

Рис. 3 Возникновение гонок при доступе к разделяемым данным

Обозначим соответствующие шаги для потока, А как Al, A2 и A3, а для потока В как Bl, B2 и ВЗ. Предположим, что в некоторый момент поток, А обновляет поле Заказ записи о клиенте N. Для этого он считывает эту запись в свой буфер (шаг А1), модифицирует значение поля Заказ (шаг А2), но внести запись в базу данных (шаг A3) не успевает, так как его выполнение прерывается, например, вследствие завершения кванта времени.

Предположим также, что потоку В также потребовалось внести сведения об оплате относительно того же клиента N. Когда подходит очередь потока В, он успевает считать запись в свой буфер (шаг В1) и выполнить обновление поля Оплата (шаг В2), а затем прерывается. Заметим, что в буфере у потока В находится запись о клиенте N, в которой поле Заказ имеет прежнее, не измененное значение.

Когда в очередной раз управление будет передано потоку А, то он, продолжая свою работу, запишет запись о клиенте N с модифицированным полем Заказ в базу данных (шаг A3). После прерывания потока, А и активизации потока В последний запишет в базу данных поверх только что обновленной записи о клиенте N свой вариант записи, в которой обновлено значение поля Оплата. Таким образом, в базе данных будут зафиксированы сведения о том, что клиент N произвел оплату, но информация о его заказе окажется потерянной (Рис. 4, А).

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

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

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

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

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

Неразделение ресурсов происходит по одной из следующих причин:

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

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

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

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

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

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

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

Механизмы взаимоисключения должны обеспечивать:

· целостность структур разделяемых данных;

· отсутствием взаимных блокировок задач;

· отсутствие тупиков.

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

Одним из классических средств обеспечения целостности разделяемых данных при обращении к неразделяемому ресурсу является механизм семафоров. Семафоры не допускают выполнения некоторого участка кода несколькими задачами одновременно. Самый простой семафор — замок (lock) или mutex (от английского mutually exclusive, взаимоисключающий). Для того чтобы задача могла выполнить критический участок кода, она должна сначала захватить замок. После захвата замка задача выполняет критический участок кода и потом освобождает замок, чтобы другая задача могла его получить и выполнить охраняемый замком критический участок своего кода. Задача, столкнувшись с занятым другой задачей замком, обычно ждет его освобождения.

1.9 Требования к алгоритмам синхронизации

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

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

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

3. Если процесс Pi исполняется в своем критическом участке, то не существует никаких других процессов, которые исполняются в своих соответствующих критических секциях. Это условие получило название условия взаимоисключения (mutual exclusion).

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

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

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

1.10 Алгоритмы синхронизации

1.10.1 Запрет прерываний

Наиболее простым решением поставленной задачи является следующая организация пролога и эпилога:

while (условие) {

запретить все прерывания

критическая секция

разрешить все прерывания

остальной код

}

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

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

1.10.2 Переменная-замок

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

shared int lock = 0;

while (условие) {

while(lock); lock = 1;

критическая секция

lock = 0;

остальной код

}

К сожалению, внимательное изучение показывает, что такое решение, не удовлетворяет условию взаимоисключения, так как действие while (lock); lock = 1; не является атомарным. Допустим, что процесс P0 протестировал значение переменной lock и принял решение двигаться дальше. В этот момент, еще до присваивания переменной lock значения 1, планировщик передал управление процессу P1. Он тоже изучает содержимое переменной lock и тоже принимает решение войти в критический участок. Мы получаем два процесса одновременно выполняющих свои критические секции.

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

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

shared int ready[2] = {0, 0};

shared int turn;

while (условие) {

ready[i] = 1;

turn =1- i;

while (ready[1-i] && turn == 1-i);

критическая секция

ready[i] = 0;

остальной код

}

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

Удовлетворение требований 1 и 2 очевидно.

Докажем выполнение условия взамоисключения методом от противного. Пусть оба процесса одновременно оказались внутри своих критических секций. Заметим, что процесс Pi может войти в критическую секцию, только если ready[1-i] == 0 или turn == i. Заметим также, что если оба процесса одновременно выполняют свои критические секции, то значения флагов готовности для обоих процессов совпадают и равны 1. Могли ли оба процесса войти в критические секции из состояния, когда они оба одновременно находились в процессе выполнения цикла while? Нет, так как в этом случае переменная turn должна была бы одновременно иметь значения 0 и 1 (когда оба процесса выполняют цикл, то значения переменных измениться не могут). Пусть процесс P0 первым вошел в критический участок, тогда процесс P1 должен был выполнить перед вхождением в цикл while, по крайней мере, один предваряющий оператор (turn = 0;). Однако после этого он не может выйти из цикла до окончания критического участка процесса P0, так как при входе в цикл ready[0] == 1 и turn == 0, и эти значения не могут измениться до тех пор, пока процесс P0 не покинет свой критический участок. Мы получили противоречие. Следовательно, имеет место взаимоисключение.

Докажем выполнение условия прогресса. Возьмем, без ограничения общности, процесс P0. Заметим, что он не может войти в свою критическую секцию только при совместном выполнении условий ready[1] == 1 и turn == 1. Если процесс P1 не готов к выполнению критического участка, то ready[1] == 0 и процесс P0 может осуществить вход. Если процесс P1 готов к выполнению критического участка, то ready[1] == 1 и переменная turn имеет значение либо 0, либо 1, позволяя либо процессу P0, либо процессу P1 начать выполнение критической секции. Если процесс P1 завершил выполнение критического участка, то он сбросит свой флаг готовности ready[1] == 0, разрешая процессу P0 приступить к выполнению критической работы. Таким образом, условие прогресса выполняется.

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

1.10.4 Алгоритм булочной (Bakery algorithm)

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

shared enum {false, true} choosing[n];

shared int number[n];

Изначально элементы этих массивов инициируются значениями false и 0 соответственно. Введем следующие обозначения

(a, b) < (c, d), если a < c или если a == c и b < d

max (a0, a1,.…, an) — это число k такое, что k >= ai для всех i = 0,.., n

Структура процесса Pi для алгоритма булочной приведена ниже

while (условие) {

choosing[i] = true;

number[i] = max (number[0],.., number[n-1]) + 1;

choosing[i] = false;

for (j = 0; j < n; j++){

while (choosing[j]);

while (number[j] ≠ 0 && (number[j], j) < (number[i], i));

}

критическая секция

number[i] = 0;

остальной код

}

1.11 Взаимное исключение на примере монитора

Рассмотренные в предыдущем пункте алгоритмы хотя и являются корректными, но достаточно громоздки и не обладают элегантностью. Более того, процедура ожидания входа в критический участок включает в себя достаточно длительное вращение процесса в пустом цикле, вхолостую пожирая драгоценное время процессора. Существуют и другие серьезные недостатки у алгоритмов, построенных средствами обычных языков программирования. Допустим, что в вычислительной системе находятся два взаимодействующих процесса: один из них — H — с высоким приоритетом, другой — L — с низким приоритетом. Пусть планировщик устроен так, что процесс с высоким приоритетом вытесняет низкоприоритетный процесс всякий раз, когда он готов к исполнению, и занимает процессор на все время своего CPU burst (если не появится процесс с еще большим приоритетом). Тогда в случае, когда процесс L находится в своей критической секции, а процесс H, получив процессор, подошел ко входу в критическую область, мы получаем тупиковую ситуацию. Процесс H не может войти в критическую область, находясь в цикле, а процесс L не получает управления, чтобы покинуть критический участок.

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

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

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

Монитор состоит из:

· набора процедур, взаимодействующих с общим ресурсом

· мьютекса

· переменных, связанных с этим ресурсом

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

monitor monitor_name {

описание переменных ;

void mn(…){… }

{блок инициализации внутрениих переменных ;} }

Здесь функции m1,…, mn представляют собой функции-методы монитора, а блок инициализации внутренних переменных содержит операции, которые выполняются только один раз: при создании монитора или при самом первом вызове какой-либо функции-метода до ее исполнения.

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

Однако одних только взаимоисключений не достаточно для того, чтобы в полном объеме реализовать решение задач, возникающих при взаимодействии процессов. Нужны еще и средства организации очередности процессов, подобно семафорам full и empty. Для этого в мониторах было введено понятие условных переменных (condition variables), над которыми можно совершать две операции wait и signal, до некоторой степени похожие на операции P и V над семафорами.

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

Когда ожидаемое событие происходит, другой процесс внутри функции-метода совершает операцию signal над той же самой условной переменной. Это приводит к пробуждению ранее заблокированного процесса, и он становится активным. Если несколько процессов дожидались операции signal для этой переменной, то активным становится только один из них. Что нам нужно предпринять для того, чтобы у нас не оказалось двух процессов, разбудившего и пробужденного, одновременно активных внутри монитора? Хор предложил, чтобы пробужденный процесс подавлял исполнение разбудившего процесса, пока он сам не покинет монитор. Несколько позже Хансен (Hansen) предложил другой механизм: разбудивший процесс покидает монитор немедленно после исполнения операции signal.

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

1.12 Взаимное исключение на примере семафора

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

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

V-операция над семафором представляет собой увеличение значения семафора на 1. Если при этом имеются процессы, задержанные на выполнении P-операции на данном семафоре, один из этих процессов выходит из состояния ожидания и может выполнить свою P-операцию.

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

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

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