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

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

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

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

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

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

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

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

« …. » ………..…… 2012 г.

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

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

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

« …. » ………….…….…. 2012 г.

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

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

Попков Данила Игоревич

Работа защищена с оценкой

« …. » ……………….. 2012 г.

Челябинск, 2012

Оглавление

Введение    2

Глава 1. Теоретические основы синхронизации процессов         6

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

.2 Понятие процесса и потока        7

.3 Свойства процессов и потоков  7

.4 Определение процесса и потока 11

.5 Создание процессов и потоков  12

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

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

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

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

.10 Алгоритмы синхронизации      24

.10.1 Запрет прерываний       24

.10.2 Переменная-замок         25

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

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

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

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

.13 Семафоры в Windows      35

Выводы по главе 1       39

Глава 2. Элективный курс “Процессы в операционной системе Windows”   40

.1 Методика изучения элективного курса         40

.2 Программная поддержка элективного курса “Процессы в ОС Windows”  65

.3 Апробация результатов исследования в средней школе 69

Выводы по главе 2       70

Заключение         71

Список литературы      72

Приложение        73

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ГЛАВА 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), задачу ведения базы данных клиентов некоторого предприятия. Каждому клиенту отводится отдельная запись в базе данных, в которой среди прочих полей имеются поля Заказ и Оплата. Программа, ведущая базу данных, оформлена как единый процесс, имеющий несколько потоков, в том числе поток А, который заносит в базу данных информацию о заказах, поступивших от клиентов, и поток В, который фиксирует в базе данных сведения об оплате клиентами выставленных счетов. Оба эти потока совместно работают над общим файлом базы данных, используя однотипные алгоритмы, включающие три шага:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.10.1 Запрет прерываний

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

while (условие) {

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

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

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

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

}

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

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

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

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

shared int lock = 0;(условие) {(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}; int turn; (условие) { [i] = 1; =1- i; (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]; int number[n];

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

(a,b) < (c,d), если a < c или если a == c и b < d (a0, a1,...., an) - это число k такое, что k >= ai для всех i = 0,...,n

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

while (условие) { [i] = true; [i] = max(number[0],..., number[n-1]) + 1; [i] = false; (j = 0; j < n; j++){ (choosing[j]); (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, при этом никаких предположений не делается о том, какой это будет процесс.

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

Рис. 5. Обращение процессов к семафору.

Операции Р и V выполняются операционной системой в ответ на запрос, выданный некоторым процессом и содержащий имя семафора в качестве параметра. По операциям Р и V выполняются следующие действия:

P(S): if S=1

then S=S-1 /*закрыть семафор*/

else БЛОКИРОВАТЬ обратившийся процесс по S

V(S): if список процессов, ожидающих S, не пуст

then ДЕБЛОКИРОВАТЬ процесс, ожидающий S

else S=1 /*открыть семафор*/

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

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

P(S)

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

V(S)

Процесс, входящий в критическую секцию, выполняет операцию P(S) и переводит семафор в 0. Если в критической секции уже находится другой процесс, то значение семафора уже равно 0. Тогда второй процесс, желающий войти в критическую секцию, блокируется своей P-операцией до тех пор, пока процесс, находящийся в критической секции сейчас, не выйдет из нее, выполнив на выходе операцию V(S).

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

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

В качестве примера, предположим, что операционная система выполняет два процесса A и B, один из которых (процесс А) добавляет элемент в очередь, а другой (процесс В) удаляет элемент из очереди. Чтобы указатели очереди не стали перепутанными, необходимо ограничить доступ к очереди до одного процесса одновременно. Таким образом, добавление и удаление элементов могут быть закодированы как критические секции.

Программа для процесса А Программа для процесса В

код программы код программы

P(S) P(S)

добавить элемент в очередь удалить элемент из очереди

V(S) V(S)

код программы код программы

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

Рис. 6. Использование двоичного семафора.

1.13 Семафоры в Windows

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

Создание семафора

Для создания семафора приложение должно вызвать функцию CreateSemaphore. Синтаксис функции CreateSemaphore:

HANDLE CreateSemaphore(lpsa: LPSECURITY_ATTRIBUTES; cSemInitial: LONG; cSemMax: LONG; lpszSemName: LPTSTR);

Параметр lpsa задаёт дескриптор защиты, отличный от стандартного дескриптора. Значение параметра lpsa NULL указывает на стандартные атрибуты защиты.

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

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

В случае удачного создания семафора функция CreateSemaphore возвращает его идентификатор. В случае возникновения ошибки возвращается значение NULL, при этом код ошибки можно узнать при помощи функции GetLastError.

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

Уничтожение семафора

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

Увеличение значения счетчика семафора

Для увеличения значения счетчика семафора приложение должно использовать функцию ReleaseSemaphore. Синтаксис вызова функции ReleaseSemaphore:

BOOL ReleaseSemaphore(Semaphore: HANDLE; cRelease: LONG; lplPrevious LPLONG);

Функция ReleaseSemaphore увеличивает значение счетчика семафора, идентификатор которого передается ей через параметр Semaphore, на значение, указанное в параметре cRelease. С помощью функции ReleaseSemaphore счётчик ресурсов, принадлежащий семафору, можно увеличивать, более чем на единицу единовременно. Параметр cRelease определяет, какими порциями должен освобождаться семафор.

Заметим, что через параметр cRelease можно передавать только положительное значение, большее нуля. При этом если в результате увеличения новое значение счетчика должно будет превысить максимальное значение, заданное при создании семафора, функция ReleaseSemaphore возвращает признак ошибки и не изменяет значение счетчика.

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

Если функция ReleaseSemaphore завершилась успешно, она возвращает значение TRUE. При ошибке возвращается значение FALSE. Код ошибки в этом случае можно определить, как обычно, при помощи функции GetLastError.

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

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

Уменьшение значения счетчика семафора

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

DWORD WaitForSingleObject(Semaphore: HANDLE; Milliseconds: DWORD);

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

Определение текущего значения счетчика семафора

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

Выводы по главе 1

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

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

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

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

.   Он позволяет одновременный доступ к ресурсам.

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

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

.        На основе семафора можно реализовать механизм синхронизации эквивалентный монитору.

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

ГЛАВА 2. ЭЛЕКТИВНЫЙ КУРС “ПРОЦЕССЫ В ОПЕРАЦИОННОЙ СИСТЕМЕ WINDOWS”

.1 Методика изучения элективного курса

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

Знания по данной теме отражены в требованиях к уровню подготовки учеников.

Ученики должны знать/понимать:

·   назначение и функции операционных систем;

Ученики должны уметь:

·   распознавать и описывать информационные процессы в социальных, биологических и технических системах;

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

·   ориентации в информационном пространстве, работы с распространенными автоматизированными информационными системами;

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

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

Знания по этой темы отражены в требованиях к уровню подготовки выпускников.

Ученики должны знать/понимать:

·  Виды и свойства информационных моделей реальных объектов и процессов, методы и средства компьютерной реализации информационных моделей;

Ученики должны уметь:

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

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

Знания по этой темы отражены в требованиях к уровню подготовки выпускников.

Ученики должны знать/понимать:

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

·        способы и средства обеспечения надежного функционирования средств ИКТ;

Ученики должны уметь:

·  устранять простейшие неисправности, инструктировать пользователей по базовым принципам использования ИКТ;

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

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

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

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

Знания по этой темы отражены в требованиях к уровню подготовки выпускников.

Ученики должны уметь:

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

На профильном уровне к программированию можно отнести следующие темы:

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

·        Язык программирования. Типы данных. Основные конструкции языка программирования. Система программирования. Основные этапы разработки программ. Разбиение задачи на подзадачи.

Ученики должны знать/понимать:

·  Основные конструкции языка программирования.

Ученики должны уметь:

·  Строить информационные модели объектов, систем и процессов, используя для этого типовые средства (язык программирования, таблицы, графики, диаграммы, формулы и т.п.)

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

1. Н.Д. Угринович (11 класс, базовый уровень) «Информатика и ИКТ»

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

2. И.Г. Семакин, Е.К. Хеннер (10-11 классы, базовый уровень) “Информатика и ИКТ”

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

В главе 3 “Информационные модели” более детально рассматриваются алгоритмы и структуры данных.

3. Н.Д. Угринович (10 класс, профильный уровень) «Информатика и ИКТ

В главе 1 “Архитектура компьютера и защита информации” детально изучается операционная система, её назначение и состав, а так же этапы её загрузки.

Глава 4 “Алгоритмизация и основы объектно-ориентированного программирования” полностью посвящена изучению алгоритмических структур и различным языкам программирования. Затрагиваются такие вопросы, как процедуры и функции, модульный принцип программирования, массивы.

4. И.Г. Семакин (10 класс, профильный уровень) “Информатика и ИКТ”

В главе 1 “Теоретические вопросы информатики” изучаются такие понятия, как процессы, алгоритмы и логические основы обработки информации.

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

Учебный курс “Процессы в ОС Windows” предназначен для учеников старших классов общеобразовательных школ, изучающих информатику на профильном уровне. Курс является элективным (обязательным для посещения курсом по выбору учащегося) и рассчитан на 17 часов, которые проводятся в течение учебного времени по 1 часу в неделю.

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

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

Целью курса является знакомство со структурой ОС Windows, основными понятиями темы “Процессы и потоки в ОС”, алгоритмами и механизмами синхронизации потоков. Предусмотрено знакомство и работа с программой “Реализация синхронизации при помощи семафора”. Расширение знаний учащихся по программированию (алгоритмические структуры, подпрограммы, модульная структура построения программ, некоторые функции Windows API), применение полученных знаний на практике.

Основными задачами курса являются:

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

·        Изучить структуру операционных систем.

·        Изучить различные алгоритмы синхронизации.

·        Изучить различные механизмы синхронизации.

·        Оценивать стабильность работы многопоточных программ.

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

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

Элективный курс “Процессы в операционной системе Windows” базируется на предшествующем изучении курса “Информатика и ИКТ”.

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

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

Для успешного освоения элективного курса ученикам предъявляются следующие требования:

Знать/понимать:

·  Знать понятие “операционная система”

·        Понимать основное назначение операционной системы

·        Знать понятие “алгоритм”

Уметь:

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

Поурочное планирование

Урок 1.

Тема: Эволюция ОС семейства Windows.

Тип урока: Усвоения новых знаний.

Цели урока:

знать:

·  особенности ОС семейства Windows 9x.

·        особенности ОС семейства Windows NT.

иметь представление о:

·  истории развития ОС семейства Windows.

уметь:

·  назвать отличия ОС семейства Windows от семейства UNIX.

·        приводить пример ОС, относящейся к тому или иному семейству.

Краткое содержание урока:

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

Приводится история развития операционных систем семейства Windows, разделенная на 3 этапа: семейство Windows 16-битная, Windows 9x и Windows NT. Подробно рассматриваются особенности и отличия двух последних семейств. Приводятся отличия ОС семейства Windows от ОС семейства UNIX.

Контрольные вопросы:

1. Как вы понимаете, что такое операционная система, и какое её назначение?

2.       Назовите отличительные особенности ОС семейства Windows 9x; Windows NT.

.        Какое главное отличие ОС семейства Windows от ОС семейства UNIX?

Методические рекомендации учителю:

Уделить внимание последним ОС семейства Windows NT. Привести статистические данные по популярности различных версий Windows на рынке персональных компьютеров.

Урок 2.

Тема: Основные функции и структура ОС Windows.

Тип урока: Усвоения новых знаний.

Цели урока:

знать:

·  понятие “ядро ОС”.

·        функции ОС.

иметь представление о:

·  структуре ОС.

уметь:

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

Краткое содержание урока:

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

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

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

Контрольные вопросы:

1. Назовите 4 основных функции ОС.

2.       К какой функции можно отнести сохранение информации в текстовой файл?

.        За что отвечает ядро операционной системы?

Методические рекомендации учителю:

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

Урок 3.

Тема: Приемы работы в ОС семейства Windows.

Тип урока: Практический

Цели урока:

знать:

·  значение системной информации об ОС и оборудование компьютера.

иметь представление о:

·  приемах работы в ОС Windows 7.

уметь:

·  управлять доступом к файлам и общими папками.

·        настраивать сетевое взаимодействие.

·        управлять безопасностью ОС Windows 7.

·        использовать инструменты мониторинга производительности Windows

Краткое содержание урока:

В ходе урока ученики закрепляют навыки работы в ОС, выполняя различные практические задания в ОС Windows 7.

Типы практических заданий:

1. Изучение структуры рабочего стола, панели управления.

2.       Изучение системной информации о компьютере.

.        Работа с файлами и папками.

.        Изучение сетевых установок.

.        Настройка безопасности и обновлений.

Контрольные вопросы:

1. Какую информацию о системе можно получить через панель управления?

2.       Где можно посмотреть ip-адрес компьютера?

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

Методические рекомендации учителю:

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

Урок 4.

Тема: Концепция потоков и процессов.

Тип урока: Усвоения новых знаний.

Цели урока:

знать:

·  понятия “процесс”, ”поток”.

иметь представление о:

·  значении процессов и потоков в работе ОС.

·        многопоточности.

уметь:

·  отличать процесс от потока.

Краткое содержание урока:

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

Контрольные вопросы:

1. Как вы понимаете, что такое процесс, поток?

2.       Какое значение они имеют для ОС?

.        В чем заключается смысл многопоточности?

Методические рекомендации учителю:

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

Урок 5.

Тема: Концепция многозадачности и параллельных вычислений.

Тип урока: Усвоения новых знаний.

Цели урока:

знать:

·  понятия “многозадачность”, ” параллельные вычисления”, “системные ресурсы”, “процессорное время”.

иметь представление о:

·  принципах работы многозадачных систем.

уметь:

·  называть преимущества многозадачных систем; параллельных вычислений

·        классифицировать системные ресурсы по значимости.

Краткое содержание урока:

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

Контрольные вопросы:

1. Какие существуют системные ресурсы?

2.       Почему процессорное время считается наиболее важным?

.        Назовите принцип работы многозадачных систем.

.        Как вы представляете параллельные вычисления?

Методические рекомендации учителю:

Уделить внимание понятию “процессорное время”. Объяснить его связь с работой процессов и потоков. Целесообразно привести примеры многозадачности из реальной жизни.

Урок 6.

Тема: Работа с системным монитором Windows 7.

Тип урока: Практический

Цели урока:

знать:

·  особенности монитора ресурсов.

иметь представление о:

·  ресурсопотребляемости ОС.

·        принципах работы с системным монитором.

уметь:

·  диагностировать состояние системы.

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

·        создавать шаблон для сбора системной информации.

Краткое содержание урока:

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

Контрольные вопросы:

1. Какую информации можно получить, используя системный монитор?

2.       Какие виды ресурсов использует ОС?

.        Можно ли сказать, что система оптимально использует ресурсы компьютера?

.        Для чего нужны шаблоны для сбора системной информации?

Методические рекомендации учителю:

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

Урок 7.

Тема: Необходимость синхронизации потоков.

Тип урока: Комбинированный (усвоение новых знаний + практическая работа)

Цели урока:

знать:

·  понятия “критическая секция”, ”взаимоисключение”, “синхронизация”.

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

иметь представление о:

·  принципах взаимодействия процессов и потоков.

уметь:

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

Краткое содержание урока:

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

Типы практических заданий:

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

Контрольные вопросы:

1. Как вы понимаете, что такое критическая секция, взаимоисключение, синхронизация?

2.       Какие ситуации могут привести к гонкам потоков?

.        Для чего нужна синхронизация процессов и потоков?

Методические рекомендации учителю:

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

Урок 8.

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

Тип урока: Комбинированный (усвоение новых знаний + практическая работа)

Цели урока:

знать:

·  понятия “планирование”, “приоритет”, “идентификатор процесса”.

·        виды приоритетов.

иметь представление о:

·  принципах планирования процессов.

уметь:

·  называть виды приоритетов.

·        определять для каких задач подходит тот или иной приоритет.

Краткое содержание урока:

В ходе урока ученикам объясняется концепция планирования процессов в ОС Windows. Раскрываются значения понятий “идентификатор процесса”, “планирование”, “приоритет”. Рассматриваются виды приоритетов и их влияние на выполнение процессов.

Типы практических заданий:

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

Контрольные вопросы:

1. Что такое идентификатор процесса?

2.       Как вы понимаете, что из себя представляет планирование процессов?

.        Какие существуют виды приоритетов процессов?

.        Какой системный ресурс является наиболее важным для приоритета?

Методические рекомендации учителю:

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

Урок 9.

Тема: Алгоритмы синхронизации процессов (запрет прерываний, алгоритм Петерсона).

Тип урока: Комбинированный (усвоение новых знаний + практическая работа)

Цели урока:

знать:

·  определение “алгоритм синхронизации”.

·        алгоритм запрета прерываний.

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

иметь представление о:

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

уметь:

·  работать с алгоритмом запрета прерываний.

·        работать с алгоритмом Петерсона.

Краткое содержание урока:

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

Типы практических заданий:

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

Контрольные вопросы:

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

2.       Какие требования предъявляются к алгоритмам синхронизации?

.        Опишите алгоритм запрета прерываний; алгоритм Петерсона.

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

Методические рекомендации учителю:

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

Урок 10.

Тема: Алгоритмы синхронизации процессов (переменная-замок, алгоритм булочной).

Тип урока: Комбинированный (усвоение новых знаний + практическая работа)

Цели урока:

знать:

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

·        алгоритм булочной.

иметь представление о:

·  значении алгоритмов синхронизации.

уметь:

·  работать с переменной-замком.

·        работать с алгоритмом булочной.

Краткое содержание урока:

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

Типы практических заданий:

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

Контрольные вопросы:

1. Опишите алгоритм переменной-замка; алгоритм булочной.

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

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

Методические рекомендации учителю:

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

Урок 11.

Тема: Механизмы синхронизации процессов (монитор).

Тип урока: Комбинированный (усвоение новых знаний + практическая работа)

Цели урока:

знать:

·  понятие “механизм синхронизации”.

·        чем механизмы синхронизации отличаются от алгоритмов.

·  механизм синхронизации типа монитор.

иметь представление о:

·  значении механизмов синхронизации.

уметь:

·  работать с механизмом синхронизации монитор.

Краткое содержание урока:

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

Типы практических заданий:

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

Контрольные вопросы:

1. Опишите работу механизма синхронизации типа монитор.

2.       Чем механизм синхронизации отличается от алгоритма? Назовите недостатки алгоритмов синхронизации по сравнению с механизмами.

.        На каких языках программирования можно реализовать монитор?

Методические рекомендации учителю:

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

Урок 12.

Тема: Механизмы синхронизации процессов (семафор).

Тип урока: Комбинированный (усвоение новых знаний + практическая работа)

Цели урока:

знать:

·  механизм синхронизации типа семафор.

иметь представление о:

·  различиях и сходствах между мониторами и семафорами.

уметь:

·  работать с механизмом синхронизации семафор.

Краткое содержание урока:

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

Типы практических заданий:

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

Контрольные вопросы:

1. Опишите работу механизма синхронизации типа семафор.

2.       Чем механизм синхронизации семафор отличается от монитора?

.        Можно ли считать, что механизмы синхронизации являются эквивалентными? Почему?

Методические рекомендации учителю:

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

Урок 13.

Тема: Изучение и работа с программой реализации семафоров.

Тип урока: Комбинированный (усвоение новых знаний + практическая работа)

Цели урока:

знать:

·  понятие “время работы вне критической секции”, “время работы в критической секции” и “время ожидания освобождения семафора”.

иметь представление о:

·  о программной реализации семафора.

уметь:

·  работать с программой реализации семафора.

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

Краткое содержание урока:

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

1. Работа с программой реализации семафора - изучение кода, интерфейса, функционала.

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

.        Установка различных параметров работы семафора.

Контрольные вопросы:

1. Что такое “критическая переменная”; “время работы вне критической секции”; “время работы в критической секции”; “время ожидания освобождения семафора”?

2.       Расскажите, какой функционал имеет программа реализации семафора?

.        Сколько потоков используется в программе? Можно ли установить большее количество потоков?

Методические рекомендации учителю:

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

Урок 14.

Тема: Исследование стабильности синхронизации.

Тип урока: Комбинированный (повторение + практическая работа)

Цели урока:

знать:

·  понятие “критическая переменная”.

иметь представление о:

·  стабильной работе механизмов синхронизации.

уметь:

·  оценивать стабильность работы семафора.

·        определять стабильность критической переменной.

Краткое содержание урока:

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

Типы практических заданий:

1. Ученики проверяют стабильность работы механизма синхронизации.

2.       А так же проверяют правильность обращения к критической секции.

.        Наблюдают за значениями критической переменной.

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

Контрольные вопросы:

1. Для чего нужна синхронизация?

2.       Что может случиться при неправильной синхронизации процессов/потоков?

.        Оцените стабильность механизмов синхронизации на примере работы программы реализации семафоров.

.        Нужны ли механизмы синхронизации?

.        Нужна ли сама многопоточность?

Методические рекомендации учителю:

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

Урок 15.

Тема: Задача обедающих философов.

Тип урока: Комбинированный (усвоение новых знаний + практическая работа)

Цели урока:

знать:

·  понятие “классическая задача синхронизации”.

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

иметь представление о:

·  решении классических задач синхронизации.

уметь:

·  применять знания о механизмам синхронизации на практике.

Краткое содержание урока:

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

Типы практических заданий:

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

Контрольные вопросы:

1. Что из себя представляют классические задачи синхронизации?

2.       Какие проблемы нужно решить в задаче обедающих философов?

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

Методические рекомендации учителю:

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

Урок 16.

Тема: Задача читателей и писателей.

Тип урока: Комбинированный (усвоение новых знаний + практическая работа)

Цели урока:

знать:

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

иметь представление о:

·  решении классических задач синхронизации.

уметь:

·  применять знания о механизмам синхронизации на практике.

Краткое содержание урока:

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

Типы практических заданий:

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

Контрольные вопросы:

4. Что из себя представляют классические задачи синхронизации?

5.       Какие проблемы нужно решить в задаче обедающих философов?

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

Методические рекомендации учителю:

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

Урок 17.

Тема: Контрольное занятие.

Тип урока: Практический.

Цели урока:

уметь:

·  отвечать на теоретические вопросы по пройденному материалу.

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

Краткое содержание урока:

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

Типы практических заданий:

Выполняется работа, которая должна содержать следующие пункты:

1. Вариант индивидуального задания.

2.       Временные диаграммы работы потоков.

.        Результаты решения, представленные в режиме «Числовые параметры».

.        Анализ стабильности синхронизации.

.        Выводы по работе.

Требования к уровню подготовки учащихся после изучения элективного курса.

Учащиеся должны:

Знать/понимать:

·  Основные понятия, связанные с процессами и синхронизацией, такие как “процесс”, “поток”, “системные ресурсы”, “процессорное время”, “синхронизация”, “критические секции”, “семафор”, “монитор”.

·        Классификацию ОС семейства Windows.

·        Иметь представление о принципах взаимодействия процессов.

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

·        Структуру механизма синхронизации типа семафор.

Уметь:

·  Приводить примеры ОС разных поколений.

·        Называть различные алгоритмы и механизмы синхронизации.

·        Применять алгоритмы синхронизации.

·        Применять механизм синхронизации типа семафор.

·        Решать классические задачи синхронизации.

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

2.2 Программная поддержка элективного курса “Процессы в ОС Windows”

Описание программного продукта “Реализация семафора”

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

Программа состоит из двух модулей: основного модуля Main.pas и модуля WriterThread.pas.

В основном модуле прописаны процедуры создания потоков и их начальные параметры, а также процедуры, обеспечивающие отображение работы программы (графику) в двух режимах: “Числовые параметры” и “Диаграмма работы”. При нажатии на кнопку “Создать потоки” создаются два потока, которые, получив соответствующие параметры, запускаются и работают, пока не выполнят функцию Execute (основная функция потока). Так же при этом создается семафор с параметрами: начальное значение счётчика равно 1, максимальное значение счётчика равно 1 (семафор является двоичным), имя семафора - qwerty. Для создания семафора вызывается функция Semaphore:=CreateSemaphore(nil, 1,1, 'qwerty').

Модуль WriterThread.pas имитирует работу потоков. Работа потоков оформлена как процедуры Thread1.Execute и Thread2.Execute. В этом же модуле реализовано динамическое построение графиков для потоков и самого семафора, а так же динамическое добавление числовой информации.

Окно программы поделено на две части (рис 7):

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

·  Работа в критической секции - WorkSemafor.

·        Работа вне критической секции - SleepDuration.

·        Время ожидания освобождения семафора - WaitForDuration.

2) Вывод данных полученных в результате работы потоков через семафор. Данные представлены в двух видах - числовом и графическом. За переключение режима отображения отвечает кнопка “Диаграмма работы/Числовые параметры”. (рис 7-2)

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

Функция отвечает за:

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

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

·        Добавление пояснительных надписей

·        Рисование квадратов с примерами цветового оформления графиков.

В режиме отображения числовых параметров в ListBox выводятся следующие данные (Рис 8):

.   Номер потока.

2.       ID (идентификатор), присваиваемый потоку операционной системой.

.        Число, присваиваемое потоком критическому объекту Х.

.        Время работы потока вне критической секции (в миллисекундах).

.        Время работы потока в критической секции (в миллисекундах).

.        Время ожидания освобождения семафора(в миллисекундах).

В режиме отображения диаграмм рисуются следующие графические данные (Рис. 8):

)   Время работы потока вне критической секции (зеленым цветом).

2)      Время работы потока в критической секции (красным цветом).

)        Время ожидания освобождения семафора (синим цветом).

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

)   Семафор свободен (желтым цветом).

2)      Первый поток занимает семафор (голубым цветом).

)        Второй поток занимает семафор (розовым цветом).

Процедура Execute для каждого потока содержит следующие этапы:

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

2.       Ожидание освобождения семафора в пределах времени заданного пользователем.

.        Работа с критическим объектом. Время работы задается пользователем.

.        Освобождение семафора.

Результаты работы программы отображаются в просмотровом окне в режимах "Числовые параметры" (рис. 8) и "Диаграмма работы" (рис. 9).

За критический объект берется переменная Х, которая является общей для обоих потоков.(x: integer;). Работа потока с критическим объектом имитируется обращением к генератору равномерно распределенных случайных чисел FWorkSemafor. Число, выработанное этим генератором, присваивается переменной j, которая определяет длительность работы потока с критической секцией. В режиме "Числовые параметры" (рис. 8) значение переменной j отображает переменная Работа с крит. секцией. Новое значение переменной x, присваемое потоком критическому объекту, вырабатывается обращением к генератору равномерно распределенных случайных чисел в диапазоне от 1 до 100.

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

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

Описание электронного пособия

Программно-методической поддержкой элективного курса является электронное пособие «Процессы в ОС Windows», разработанное с помощью Adobe Dreamweaver CS3. Данный программный продукт представляет собой обучающее пособие, содержащее: методический материал для учителя, теоретический материал, адаптированный для школьников, практические задания и вопросы для повторения.

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

Электронное учебное пособие содержит два основных раздела:

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

Запустив электронное пособие, вы попадаете в его главное меню, представленное на рисунке 11.

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

Разделы электронного пособия представлены на рисунках 12 и 13.

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

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

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

2.3 Апробация результатов исследования в средней школе

Педагогический эксперимент проводился во время педагогической практики в МАОУ СОШ № 147 г. Челябинска. Курс изучался в общеобразовательном классе. В течение занятий были рассмотрены темы:

.   Концепция процессов и потоков (1 ч.).

2.       Изучение механизма синхронизации семафор (1 ч.).

.        Исследование стабильности синхронизации (1 ч.).

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

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

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

Выводы по главе 2

В главе 2 был проанализирован стандарт среднего (полного) общего образования по предмету информатика и ИКТ базового и профильного уровня, так же были рассмотрены некоторые учебные программы. Анализ показал, что содержания стандарта и материала учебников по теме “Процессы в операционных системах” недостаточно для понимания структуры операционной системы и принципах её работы. Так же по содержанию стандарта и материалам учебника невозможно составить представление о взаимодействии процессов в ОС. Для этих целей был разработан элективный курс “Процессы в операционной системе Windows”, рассчитанный на 17 часов. Разработан тематический план, с требованиями к уровню знаний учащихся по изучению курса. Разработано поурочное планирование. Для каждого урока сформулирована тема и образовательные цели; представлено краткое содержание урока; приведены типы практических заданий; поставлены контрольные вопросы и даны методические рекомендации учителю по проведению уроков.

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

Так же было разработано электронное учебное пособие “Процессы в ОС Windows”, которое содержит методические сведения для учителя и теоретический материал, адаптированный для школьников.

ЗАКЛЮЧЕНИЕ

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

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

.   Проанализирован теоретический материал по исследуемой области.

2.       Рассмотрены различные виды алгоритмов и механизмов синхронизации и выявлены особенности их работы.

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

.        Анализ теоретического материала позволил отобрать содержание для элективного курса “Процессы в операционной системе Windows” и адаптировать его для старших классов.

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

.        Успешно проведена апробация курса в 10В классе в МАОУ СОШ №147 г. Челябинска, в результате которой ученики полностью усвоили материал проводимых уроков.

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

СПИСОК ЛИТЕРАТУРЫ

1. Бэкон, Д. Операционные системы/ Д.Бэкон. - СПб.: Питер, BHV, 2004 г. - 800с.

2.       Гордеев, А.В. Операционные системы: Учебник для вузов/ А.В.Гордеев.-2-е изд.-СПб.и др.: Питер, 2004 г.- 415 с.

.        Олифер, В.Г. Сетевые операционные системы/ В.Г.Олифер, Н.А.Олифер.- СПб.: Издательский дом «Питер», 2001 г. - 544 с.

.        Побегайло А. П. - Системное программирование в Windows. / А. П. Побегайло - СПб: БХВ-Петербург, 2006 г. - 1056 с.

.        Столингс, В. Операционные системы/В. Столлингс. - 4-е издание. - М.: Вильямс, 2004 г. - 848 с.

.        Таненбаум, Э,. Операционные системы: Разработка и реализация 3-е издание./ Э Таненбаум, А Вудхалл - СПб.: 2007 г.- 704 с.

.        Таненбаум, Э. Современные операционные системы/ Э.Таненбаум. - СПб.: Издательский дом «Питер», 2005. - 1038 с.

.        Эндрюс Г.Р. Основы многопоточного, параллельного и распределённого программирования/ Г. Р. Эндрюс - СПб: “Вильямс”, 2003. - 512 с.

ПРИЛОЖЕНИЕ

Конспект урока «Концепция процессов и потоков»

Тема урока: Концепция процессов и потоков.

Вид: урок усвоения новых знаний.

Цели урока:

• Образовательная: знать понятия “процесс”, ”поток”; иметь представление о значении процессов и потоков в работе ОС; иметь представление о многопоточности; уметь отличать поток от процесса.

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

• Развивающая: развитие познавательных интересов.

План урока:

1. Организационный момент. (1 мин)

2.       Актуализация знаний. (2 мин)

.        Повторение ранее изученного материала. (2 мин)

.        Изложение нового материала. (20 мин)

.        Практическая работа. (18 мин)

.        Подведение итогов. (2 мин)

Конспект урока «Изучение механизма синхронизации семафор»

Тема урока: Изучение механизма синхронизации семафор.

Вид: урок усвоения новых знаний.

Цели урока:

• Образовательная: знать понятия синхронизация, механизм синхронизации типа семафор; иметь представление о механизмах синхронизации; иметь представление о критической секции.

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

• Развивающая: развитие познавательных интересов.

План урока:

1. Организационный момент. (1 мин)

2.       Актуализация знаний. (2 мин)

.        Повторение ранее изученного материала. (10 мин)

.        Изложение нового материала. (30 мин)

.        Подведение итогов. (2 мин)