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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В главе 2 “Компьютер” рассмотрены функции операционных систем и их семейства на ПК.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	Тема	Часы
		теория	практика	итого
1	Основные сведения об ОС семейства Windows	2		2
2	Приемы работы в ОС семейства Windows		1	1
3	Концепция процессов и потоков в ОС семейства Windows	2	1	3
4	Принципы взаимодействия процессов и потоков	1	1	2
5	Алгоритмы синхронизации	1	1	2
6	Механизмы синхронизации	1	1	2
7	Исследование стабильности синхронизации процессов в ОС	1	1	2
8	Классические задачи взаимодействия процессов	1	1	2
9	Контрольное занятие		1	1
	Итого:	9	8	17

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

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

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

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

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

Уметь:

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

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

Урок 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.

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

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

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

Урок 2.

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

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

Цели урока:

знать:

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

· функции ОС.

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

Урок 3.

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

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

Цели урока:

знать:

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Урок 4.

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

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

Цели урока:

знать:

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

Урок 5.

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

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

Цели урока:

знать:

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

Урок 6.

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

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

Цели урока:

знать:

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

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

Урок 7.

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

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

Цели урока:

знать:

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

Урок 8.

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

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

Цели урока:

знать:

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

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

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

Урок 9.

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

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

Цели урока:

знать:

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

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

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

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

Урок 10.

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

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

Цели урока:

знать:

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

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

Урок 11.

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

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

Цели урока:

знать:

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

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

Урок 12.

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

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

Цели урока:

знать:

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

Урок 13.

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

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

Цели урока:

знать:

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Урок 14.

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

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

Цели урока:

знать:

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Урок 15.

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

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

Цели урока:

знать:

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

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

Урок 16.

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

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

Цели урока:

знать:

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

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

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

уметь:

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

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

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

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

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

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

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

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

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

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

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

Урок 17.

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

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

Цели урока:

уметь:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· Классификацию ОС семейства 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 для последующего динамического рисования графиков.

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

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

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

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

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



Рис.7. Окно программы.

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

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

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

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

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

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

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

Рис. 8. Представление в числовом виде.

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

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

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

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