Лабораторная работа № - Fiz.lang

Лабораторная работа №1
«Надежные и правильные программы»
1. Цель занятия
Изучение стандартных схем, способов их построения, реализация соответствующих
интерпретаций. Выполнение программы и создание протокола выполнения программы.
2.



Литература
Ершов А.П. Введение в теоретическое программирование. М.: Наука, 1977.
Котов В.Е . Введение в теорию схем программ. Новосибирск.: Наука, 1978. -258с.
Котов В.Е., Сабельфельд В.К. Теория схем программ. М: Наука, Гл. ред. физ.-мат. лит., 1991. 248с.
3. Выполнение работы
 Изучить понятия:
 Программа как формализованное описание процесса обработки
 Правильная программа и надежная программа
 Написать в соответствии с заданием правильную и надежную программу;
 составить отчет по проделанной работе в соответствии с требованиями, предъявляемыми в
пункте 6.
4.
1.
2.
3.
4.
5.
6.
7.
8.
Контрольные вопросы
Что такое правильна программа?
Что такое надежная программа?
Какие существуют разделы теоретического программирования?
Что включают в себя математические основы теоретического программирования?
Что включает в себя теория вычислительных процессов?
Что включает в себя теория схем программ?
Что включает в себя семантическая теория программ?
Что включают в себя прикладные задачи теоретического программирования?
5.




Содержание работы
Ознакомиться с кратким теоретическим материалом, ответить на контрольные вопросы;
определить номер выполняемого варианта;
для заданного варианта написать правильную и надежную программу:
Результат выполнения программы необходимо отразить в протоколе выполнения программы.
6. Содержание отчета
Отчет должен содержать следующее:
 титульный лист с указанием наименования и цели занятия; фамилии, имени, отчества и номера
группы студента; фамилии, имени, отчества преподавателя, а также номер выполняемого
варианта;
 дату выполнения работы;
 цель занятия;
 условия предложенной задачи;
 реализацию соответствующей программы;
 протокол выполнения программы;
 выводы о проделанной работе.
Краткий теоретический материал
Следуя А. П. Ершову, мы употребляем термин «теоретическое программирование» в
качестве названия математической
дисциплины, изучающей синтаксические и
семантические свойства программ, их структуру, преобразования, процесс их составления и
исполнения. Это словосочетание построено по аналогии с названиями таких наук, как
теоретическая физика, теоретическая механика и т. д. В такой аналогии есть глубокий смысл:
во всех случаях теоретическая научная дисциплина изучает фундаментальные понятия и
законы основной науки и на основании обнаруженных закономерностей строит более
частные математические модели исследуемых объектов, на которых ставит и решает
прикладные задачи. В нашем случае ситуация усложняется еще тем, что объект
моделирования – программа – уже представляет собой абстрактный объект.
В настоящее время сложились следующие основные направления исследований
теоретического программирования.
1. Математические основы программирования. Основная цель исследований –
развитие математического аппарата, ориентированного на теоретическое
программирование, разработка общей теории машинных вычислений. Эта теория
тесно соприкасается с теорией алгоритмов и вычислимых функций, теорией
автоматов и формальных языков, логикой, алгеброй, с теорией сложности
вычислений.
2. Теория схем программ. В этих работах внимание концентрируется на изучении
структурных свойств и преобразований программ, а именно тех, которые
отличают программы от других способов задания алгоритмов. Главным объектом
исследования становится схема программы – математическая модель программы,
в которой с той или иной степенью детализации отражено строение программы,
взаимодействие составляющих ее компонентов.
3. Семантическая теория программ. Семантика программы или отдельных
конструкций языков программирования – это их смысл, математический смысл
для программиста и описание функционирования для машины. Этот раздел
теоретического программирования изучает методы формального описания
семантики программ, семантические методы преобразования и доказательства
утверждений о программах. В частности, работы по методам проверки
семантической правильности программ нацелены на автоматизацию их отладки и
автоматический синтез программ.
4. Теория вычислительных процессов и структур (теория параллельных вычислений).
Исследования в этой области направлены на разработку и обоснование новых
методов программирования, прежде всего методов программирования
параллельных процессов. В частности, изучаются модели, структуры и
функционирование операционных
систем,
методы
распараллеливания
алгоритмов и программ, ведется поиск новых архитектурных принципов
конструирования вычислительных машин и систем на основе результатов и
рекомендаций теоретического программирования и вычислительной математики.
5. Прикладные задачи теоретического программирования. Сюда в первую очередь
относятся разработка и обоснование алгоритмов трансляции и алгоритмов
автоматической оптимизации программ.
Две дисциплины государственного стандарта специальности 220400 – Программное
обеспечение вычислительной техники и автоматизированных систем – «Теория языков
программирования и методы трансляции» и «Теория вычислительных процессов»
рассматривают основы теоретического программирования. Первая дисциплина охватывает
первый и последний пункты нашей, не претендующей на классификационную строгость и
полноту, рубрикации. Вторая дисциплина, составляющая предмет настоящего курса,
раскрывает пункты 2 – 4.
Программа как формализованное описание процесса обработки данных
Целью программирования является описание процессов обработки данных (в
дальнейшем - просто процессов). Данные - это представление фактов и идей в
формализованном виде, пригодном для передачи и переработке в некоем процессе, а
информация - это смысл, который придается данным при их представлении. Обработка
2
данных - это выполнение систематической последовательности действий с данными. Данные
представляются и хранятся на носителях данных. Совокупность носителей данных,
используемых при какой-либо обработке данных, будем называть информационной средой.
Набор данных, содержащихся в какой-либо момент в информационной среде, будем
называть состоянием этой информационной среды. Процесс можно определить как
последовательность сменяющих друг друга состояний некоторой информационной среды.
Описать процесс - значит определить последовательность состояний заданной
информационной среды. Если мы хотим, чтобы по заданному описанию требуемый процесс
порождался автоматически на компьютере, необходимо, чтобы это описание было
формализованным. Такое описание называется программой. С другой стороны, программа
должна быть понятной и человеку, так как и при разработке программ, и при их
использовании часто приходится выяснять, какой именно процесс она порождает. Поэтому
программа составляется на понятном человеку формализованном языке программирования, с
которого она автоматически переводится на язык соответствующего компьютера с помощью
другой программы, называемой транслятором. Программисту, прежде чем составить
программу, приходится проделывать большую подготовительную работу по уточнению
постановки задачи, выбору метода ее решения, выяснению специфики применения
требуемой программы, прояснению общей организации разрабатываемой программы и
многое другое.
Правильная программа и надежная программа
Под «программой» часто понимают правильную программу, т.е. программу, не
содержащую ошибок, соответствующую спецификации и дающую возможность
формального вывода программы из формального набора предпосылок. Однако понятие
ошибки в программе трактуется программистами неоднозначно. Будем считать, что в
программе имеется ошибка, если она не выполняет того, что разумно ожидать от нее на
основании документации по применению программы. Следовательно, правильнее говорить о
несогласованности между программами и документацией по их применению.
В связи с тем, что задание на программу обычно формулируется не формально, а также
из-за неформализованности понятия ошибки в программе, нельзя доказать формальными
методами (математически) правильность программы. Нельзя доказать правильность
программы и тестированием: как указал Дейкстра, тестирование может лишь
продемонстрировать наличие в программе ошибки.
Альтернативой правильной программы является надежная программа. Надежность
программы - это ее способность безотказно выполнять определенные функции при заданных
условиях в течение заданного периода времени с достаточно большой вероятностью. При
этом под отказом в программе понимают проявление в нем ошибки. Таким образом,
надежная программа не исключает наличия в ней ошибок - важно лишь, чтобы эти ошибки
при практическом применении этой программы в заданных условиях проявлялись
достаточно редко. Убедиться, что программа обладает таким свойством можно при его
испытании путем тестирования, а также при практическом применении. Таким образом,
фактически мы можем разрабатывать лишь надежные, а не правильные программы.
Разрабатываемая программа может обладать различной степенью надежности. Как
измерять эту степень? Так же как в технике, степень надежности можно характеризовать
вероятностью работы программы без отказа в течение определенного периода времени.
Однако в силу специфических особенностей программ определение этой вероятности
наталкивается на ряд трудностей по сравнению с решением этой задачи в технике.
При оценке степени надежности программ следует также учитывать последствия каждого
отказа. Некоторые ошибки в программах могут вызывать лишь некоторые неудобства при
его применении, тогда как другие ошибки могут иметь катастрофические последствия,
например, угрожать человеческой жизни. Поэтому для оценки надежности программных
3
средств иногда используют дополнительные показатели, учитывающие стоимость (вред) для
пользователя каждого отказа.
7. Варианты заданий
Номер
Действия, выполняемые
варианта
программой
1
Расчет суммы членов
арифметической
прогрессии. Разность
арифметической
прогрессии d=3
2
Расчет суммы первых
членов геометрической
прогрессии. Знаменатель
прогрессии q=2
3
Расчет чисел Фибоначчи
4
5
6
7
8
9
10
Расчет произведения
членов арифметической
прогрессии. Разность
арифметической
прогрессии d=2
Расчет произведения
первых членов
геометрической
прогрессии. Знаменатель
прогрессии q=4
Расчет суммы чисел
Фибоначчи
Расчет произведения чисел
Фибоначчи
Решение квадратного
уравнения
Нахождение наименьшего
общего кратного двух
чисел
Нахождение наибольшего
общего делителя
(алгоритм Евклида)
Пример для выполнения
программы
Расчет суммы первых пяти
членов арифметической
прогрессии
Расчет суммы первых пяти
членов геометрической
прогрессии
Расчет седьмого числа
Фибоначчи
Расчет произведения
первых четырех членов
арифметической
прогрессии
Расчет произведения
первых четырех членов
геометрической прогрессии
Расчет суммы первых
четырех чисел Фибоначчи
Расчет произведения
первых четырех чисел
Фибоначчи
Решить квадратное
уравнение x 2  5x  4  0
Найти наименьшее общее
кратное чисел: 2 и 3
Найти наибольший общий
делитель чисел: 45 и 72
4
Лабораторная работа №2
«Стандартные схемы программ»
8. Цель занятия
Изучение стандартных схем, способов их построения, реализация соответствующих
интерпретаций. Выполнение программы и создание протокола выполнения программы.
9.



Литература
Ершов А.П. Введение в теоретическое программирование. М.: Наука, 1977.
Котов В.Е . Введение в теорию схем программ. Новосибирск.: Наука, 1978. -258с.
Котов В.Е., Сабельфельд В.К. Теория схем программ. М: Наука, Гл. ред. физ.-мат. лит., 1991. 248с.
10. Выполнение работы
 Изучить:
 состав базиса класса стандартных схем программ;
 графовую форму стандартной схемы;
 линейную форму стандартной схемы;
 интерпретации стандартных схем программ.

 построить базис стандартной схемы;
 реализовать стандартную схему в графовой и линейной формах;
 составить интерпретацию для заданной стандартной схемы;
 составить протокол выполнения программы;
 составить отчет по проделанной работе в соответствии с требованиями, предъявляемыми в
пункте 6 данного практического занятия.
11. Контрольные вопросы
9. Что такое схема программы? Чем отличается схема программы от программы?
10. Из каких частей стандартная схема программы?
11. Какие множества составляют полный базис класса стандартных схем?
12. Что такое термы и тесты? В чем разница между ними?
13. Из каких видов вершин состоит граф стандартной схемы программ?
14. Что такое линейная форма стандартной схемы программ?
15. Что называют интерпретацией базиса в области интерпретации?
16. Что такое конфигурация программы?
17. Для чего служит протокол выполнения программы? В каком случае программа считается
остановившейся?
12. Содержание работы
 Ознакомиться с кратким теоретическим материалом, ответить на контрольные вопросы;
 определить номер выполняемого варианта;
 для заданного варианта построить стандартную схему:
 построить полный базис стандартной схемы;
 реализовать стандартную схему в графовой и линейной формах;
 для полученной стандартной схемы программ реализовать соответствующую интерпретацию;
 для заданного варианта выполнить программу. Результат выполнения программы необходимо
отразить в протоколе выполнения программы.
13. Содержание отчета
Отчет должен содержать следующее:
 титульный лист с указанием наименования и цели занятия; фамилии, имени, отчества и номера
группы студента; фамилии, имени, отчества преподавателя, а также номер выполняемого
варианта;
 дату выполнения работы;
 цель занятия;
5





условия предложенной задачи;
построенную стандартную схему программ (полный базис, реализации в графовой и линейной
формах);
реализацию соответствующей интерпретации;
протокол выполнения программы;
выводы о проделанной работе.
14. Краткий теоретический материал
Программы и схемы программ
Схемы программ - это математические модели программ, описывающие строение программы,
или точнее строение множества программ, где конкретные операции и функции заменены
абстрактными функциональными и предикатными символами. Следующий пример программ
вычисления факториала n! и переворачивания слов поясняет различие между программами и их
схемой S1.
begin integer x, y;
ввод(x);
y:=1;
L: if x=0 then goto L1;
y:=x*y
x:=x-1;
goto L;
L1: вывод(y);
end
begin integer x, y;
ввод(x);
y:=ε;
L: if x=0 then goto L1;
y:=CONSCAR(x, y);
x:=CDR(x);
goto L;
L1: вывод(y);
End
begin
ввод(x);
y:=a;
L: if p(x) then goto L1;
y:=g(x, y);
x:=h(x);
goto L;
L1: вывод(y);
end
Функция CONSCAR (суперпозиция функций CONS и CAR из языка Лисп) приписывает
первую букву первого слова ко второму слову (т. е. CONSCAR(аб, в) = ав), а функция CAR стирает
первую букву слова (т. е. CAR(аб) = б).
Стандартные схемы программ
Базис класса стандартных схем программ
Стандартные схемы программ (ССП) характеризуются базисом и структурой схемы.
Базис класса фиксирует символы, из которых строятся схемы, указывает их роль
(переменные, функциональные символы и др.), задает вид выражений и операторов схем.
Полный базис В класса стандартных схем состоит из 4-х непересекающихся, счетных
множеств символов и множества операторов - слов, построенных из этих символов.
Множества символов полного базиса:
1. Х = {x, х1, х2..., у, у1 у2..., z, z1, z2...} - множество символов, называемых переменными;
2. F = {f(0), f(1), f(2)..., g(0), g(1), g(2)..., h(0), h(1), h(2)...} - множество функциональных символов; верхний
символ задает местность символа; нульместные символы называют константами и
обозначают начальными буквами латинского алфавита a, b, c...;
3. Р = {р(0), р(1), р(2)...; q(0), q(1), q(2)...; } - множество предикатных символов; р(0), q(0) - ; нульместные
символы называют логическими константами;
4. {start, stop, ...,:= и т. д.} - множество специальных символов.
Термами (функциональными выражениями) называются слова, построенные из переменных,
функциональных и специальных символов по следующим правилам:
1. односимвольные слова, состоящие из переменных или констант, являются термами;
2. слово τ вида f(n)(τ1, τ2...τn), где τ1, τ2...τn - термы, является термом;
Примеры термов: х, f(0), а, f(1)(х), g(2)(x, h(3)(y, a)).
Тестами (логическими выражениями) называются логические константы и слова вида р(n)(τ1,
τ2,...,τn). Примеры: p(0), p(0)(х), g(3)(x, y, z), p(2) (f(2(x, y)). Допускается в функциональных и логических
выражениях опускать индексы местности, если это не приводит к двусмысленности или
противоречию.
Множество операторов включает пять типов:
1. начальный оператор - слово вида start(х1, х2...хк), где k ≥0, а х1, х2...хк - переменные,
называемые результатом этого оператора;
6
2. заключительный оператор - слово вида stop(τ1, τ2...τn), где n ≥0, а τ1, τ2...τn - термы; вхождения
переменных в термы τ называются аргументами этого оператора;
3. оператор присваивания - слово вида х := τ, где х – переменная (результат оператора), а τ терм; вхождения переменных в термы называются аргументами этого оператора;
4. условный оператор (тест) - логическое выражение; вхождения переменных в логическое
выражение называются аргументами этого оператора;
5. оператор петли - односимвольное слово loop.
Среди операторов присваивания выделим случаи: когда τ - переменная, то оператор называется
пересылкой (х:=у) и когда τ -константа, то оператор называется засылкой (х:=а).
Подклассы используют ограниченные базисы. Так, например, подкласс У1 имеет базис:
х1, х2, а, f(1), p(1), start, stop, (,),:=, ,и множество операторов start(х1, х2); х1:= f(x1), x2=f(x2),
x1:=а, х2:= а, р(х1), р(х2), stop(х1,х2), т. е. схемы из этого подкласса используют две переменные,
константу а, один одноместный функциональный символ, один предикатный символ и операторы
указанного вида.
Графовая форма стандартной схемы
Представим стандартную схему программ как размеченный граф, вершинам которого
приписаны операторы из некоторого базиса В.
Стандартной схемой в базисе В называется конечный (размеченный ориентированный) граф
без свободных дуг и с вершинами следующих пяти видов:
1. Начальная вершина (ровно одна) помечена начальным оператором. Из нее выходит ровно
одна дуга. Нет дуг, ведущих к начальной вершине.
2. Заключительная вершина (может быть несколько). Помечена заключительным оператором.
Из нее не выходит ни одной дуги.
3. Вершина-преобразователь. Помечена оператором присваивания. Из нее выходит ровно одна
дуга.
4. Вершина-распознаватель. Помечена условным оператором (называемым условием данной
вершины). Из нее выходит ровно две дуги, помеченные 1 (левая) и 0 (правая).
5. Вершина-петля. Помечена оператором петли. Из нее не выходит ни одной дуги.
Конечное множество переменных схемы S составляют ее память ХS.
Из определения следует, что один и тот же оператор может помечать несколько вершин схемы.
Вершины именуются (метки вершины) целым неотрицательным числом (0, 1, 2...). Начальная
вершина всегда помечается меткой 0.
Схема S называется правильной, если на каждой дуге заданы все переменные.
Пример правильной ССП S1 в графовой форме приведен на рисунке 1.
Вершины изображены прямоугольниками, а вершина-распознаватель - овалом. Операторы
записаны внутри вершины.
Линейная форма стандартной схемы
Для использования линейной формы СПП множество специальных символов расширим
дополнительными символами :, goto, if, then, else. СПП в линейной форме представляет собой
последовательность инструкций, которая строится следующим образом:
start(x)
1
y:= a
2
p(x)
0
1
3 y:=g(x,y)
stop(y)
7
5
4
x:= h(x)
Рис.1.1 Графовая форма стандартной схемы
1. если выходная дуга начальной вершины с оператором start(х1,..., хn) ведет к вершине с меткой L,
то начальной вершине соответствует инструкция:
0: start(х1,..., хn) goto L;
2. если вершина схемы S с меткой L - преобразователь с оператором присваивания х:=τ, выходная
дуга которого ведет к вершине с меткой L1, то этому преобразователю соответствует инструкция:
L: x: =τ goto L1;
3. если вершина с меткой L - заключительная вершина с оператором stop(τ1,...τm), то ей
соответствует инструкция
L: stop(τ1,..., τm);
4. если вершина с меткой L - распознаватель с условием р(τ1,...τk), причем 1-дуга ведет к вершине с
меткой L1, а 0-дуга - к вершине с меткой L0, то этому распознавателю соответствует инструкция
L: if р(τ1,...τk) then L1 else L0;
5. если вершина с меткой L - петля, то ей соответствует инструкция
L: loop.
Обычно используется сокращенная запись (опускание меток). Полная и сокращенная линейные
формы ССП (Рис. 1.1) приведены ниже:
0: start(х) goto 1,
1: у: = а goto 2,
2: if р(х) then 5 else 3,
3: у: = g(x,y) goto 4,
4: х: = h(x) goto 2,
5: stop(у).
start(х),
у: = а,
2: if р(х) then 5 else 3,
3: у: = g(x,y),
х: = h (x) goto 2,
5: stop(у).
Интерпретация стандартных схем программ
ССП не является записью алгоритма, поэтому позволяет исследовать только структурные
свойства программ, но не семантику вычислений. При построении «семантической» теории схем
программ вводится понятие интерпретация ССП. Определим это понятие.
Пусть в некотором базисе В определен класс ССП. Интерпретацией базиса В в области
интерпретации D называется функция I, которая сопоставляет:
1.
каждой переменной х из базиса В - некоторый элемент d = I(x) из области интерпретации
D;
2.
каждой константе а из базиса В - некоторый элемент d = I(а) из области интерпретации D;
3.
каждому функциональному символу f(n) - всюду определенную функцию F(n)=I(f(n));
4.
каждой логической константе р(0) - один символ множества { 0,1 };
5.
каждому предикатному символу р(n) - всюду определенный предикат P(n) = I(p(n)).
Пара (S,I) называется интерпретированной стандартной схемой (ИСС), или стандартной
программой (СП).
Определим понятие выполнения программы.
Состоянием памяти программы (S,I) называют функцию W: XS  D, которая каждой
переменной x из памяти схемы S сопоставляет элемент W(x) из области интерпретации D.
Значение терма τ при интерпретации I и состоянии памяти W (обозначим τI(W)) определяется
следующим образом:
1) если τ=х, x – переменная, то τI(W) = W(x);
2) если τ=a, a – константа, то τI(W) = I(a);
3) если τ=f(n)(τ1, τ2..., τn), то τI(W)= I(f(n))(τ1I(W), τ2I(W),..., τnI(W)).
Аналогично определяется значение теста  при интерпретации I и состоянии памяти W или
I(W):
если =р(n)(τ1, τ2..., τn), то I(W)= I(p(n))(τ1I(W), τ2I(W),... τnI(W)), n ≥0.
8
Конфигурацией программы называют пару U=(L,W), где L - метка вершины схемы S, а W состояние ее памяти. Выполнение программы описывается конечной или бесконечной
последовательностей конфигураций, которую называют протоколом выполнения программы (ПВП).
Протокол (U0, U1,..., Ui, Ui+1,...) выполнения программы (S,I) определяем следующим образом
(ниже ki означает метку вершины, а Wi - состояние памяти в i-й конфигурации протокола, Ui=(ki,Wi)):
U0=(0, W0), W0 – начальное состояние памяти схемы S при интерпретации I.
Пусть Ui=(ki, Wi) - i-я конфигурация ПВП, а О - оператор схемы S в вершине с меткой ki. Если
О - заключительный оператор stop(τ1, τ2... τn), то Ui - последняя конфигурация, так что протокол
конечен. В этом случае считают, что, программа (S,I) останавливается, а последовательность
значений τ1I(W), τ2I(W),..., τnI(W) объявляют результатом val(S,I) выполнения программы (S,I). В
противном случае, т. е. когда О - не заключительный оператор, в протоколе имеется следующая,
(i+1)-я конфигурация
Ui+1 = (ki+1, Wi+1), причем
а) если О - начальный оператор, а выходящая из него дуга ведет к вершине с меткой L, то ki+1
= L и Wi+1 = Wi;
б) если О - оператор присваивания х:=τ, а выходящая из него дуга ведет к вершине с меткой L,
то ki+1 = L, Wi+1 = Wi, Wi+1(х) = τ1(Wi);
в) если О - условный оператор  и I(Wi) = Δ, где Δ 0,1, а выходящая из него дуга ведет к
вершине с меткой L, то ki+1 = L и Wi+1 = Wi;
г) если О - оператор петли, то ki+1 = L и Wi+1 = Wi, так что протокол бесконечен.
Таким образом, программа останавливается тогда и только тогда, когда протокол ее
выполнения конечен. В противном случае программа зацикливается и результат ее выполнения не
определен.
Рассмотрим две интерпретации СПП S1 (Рис. 1.1). Интерпретация (S1, I1) задана так:
 область интерпретации D1  Nat - подмножество множества Nat целых неотрицательных
чисел;
 I1(x)=4; I1(y)=0; I1(a)=1;
 I1(g)=G, где G - функция умножения чисел, т. е. G(d1,d2)= d1*d2;
 I1(h)=H, где H - функция вычитания единицы, т. е. H(d)= d-1;
 I1(p)=P1, где P1 - предикат «равно 0», т.е. P1(d)=1, если d=0.
Программа (S1, I1) вычисляет 4! (Рис. 1.1).
ПВП (S1, I1) конечен, результат - 24 (Таб. 1.1).
Таблица 1.1
Конфигурация U0 U1 U2 U3 U4 U5 U6 U7 U8 U9 U10 U11 U12 U13
Метка
0 1 2 3 4 2 3 4 2 3 4 2 5
Значения х
4 4 4 4 3 3 3 2 2 2 1 1 1 0
у
0 1 1 4 4 4 12 12 12 24 24 24 24 24
15. Номер варианта
0
1
7
3
Последняя цифра зачетной книжки
2
3
4
5
6
7
Номер варианта
4
9
1
8
2
5
16. Варианты заданий
9
8
9
6
10
17.
Номер
Действия, выполняемые
варианта
программой
1
Расчет суммы членов
арифметической
прогрессии. Разность
арифметической
прогрессии d=3
2
Расчет суммы первых
членов геометрической
прогрессии. Знаменатель
прогрессии q=2
3
Расчет чисел Фибоначчи
4
5
6
7
8
9
10
Расчет произведения
членов арифметической
прогрессии. Разность
арифметической
прогрессии d=2
Расчет произведения
первых членов
геометрической
прогрессии. Знаменатель
прогрессии q=4
Расчет суммы чисел
Фибоначчи
Расчет произведения чисел
Фибоначчи
Решение квадратного
уравнения
Нахождение наименьшего
общего кратного двух
чисел
Нахождение наибольшего
общего делителя
(алгоритм Евклида)
Пример для выполнения
программы
Расчет суммы первых пяти
членов арифметической
прогрессии
Расчет суммы первых пяти
членов геометрической
прогрессии
Расчет седьмого числа
Фибоначчи
Расчет произведения
первых четырех членов
арифметической
прогрессии
Расчет произведения
первых четырех членов
геометрической прогрессии
Расчет суммы первых
четырех чисел Фибоначчи
Расчет произведения
первых четырех чисел
Фибоначчи
Решить квадратное
уравнение x 2  5x  4  0
Найти наименьшее общее
кратное чисел: 2 и 3
Найти наибольший общий
делитель чисел: 45 и 72
10
Лабораторная работа №3
«Рекурсивные схемы»
1. Цель занятия
Изучение рекурсивных схем, рекурсивных уравнений, соответствующих им интерпретаций.
Выполнение программы и создание протокола выполнения программы.
2.



Литература
Ершов А.П. Введение в теоретическое программирование. М.: Наука, 1977.
Котов В.Е . Введение в теорию схем программ. Новосибирск.: Наука, 1978. -258с.
Котов В.Е., Сабельфельд В.К. Теория схем программ. М: Наука, Гл. ред. физ.-мат. лит., 1991. 248с.
3. Выполнение работы
 Изучить:
 состав полного базиса рекурсивных схем;
 интерпретации рекурсивных схем.
 построить базис рекурсивной схемы;
 составить интерпретацию для заданной рекурсивной схемы;
 составить протокол выполнения программы;
 составить отчет по проделанной работе в соответствии с требованиями, предъявляемыми в
пункте 6 данного практического занятия.
4.
1.
2.
3.
4.
5.
6.
7.
8.
5.





Контрольные вопросы
В чем разница между операторным программированием и рекурсивным?
Какие операторные и рекурсивные языки программирования Вам известны?
Из чего состоит полный базис рекурсивной схемы?
Чем отличается базис стандартной схемы программ от базиса рекурсивной схемы?
Что такое логическое выражение?
Что такое термы?
Что такое рекурсивное уравнение?
Дайте определение рекурсивной схемы.
Содержание работы
Ознакомиться с кратким теоретическим материалом, ответить на контрольные вопросы;
определить номер выполняемого варианта;
для заданного варианта построить рекурсивную схему:
 базис рекурсивной схемы;
 рекурсивные уравнения:
для полученной рекурсивной схемы реализовать соответствующую интерпретацию;
для заданного варианта выполнить программу. Результат выполнения программы необходимо
отразить в протоколе выполнения программы.
6. Содержание отчета
Отчет должен содержать следующее:
 титульный лист с указанием наименования и цели занятия; фамилии, имени, отчества и номера
группы студента; фамилии, имени, отчества преподавателя, а также номер выполняемого
варианта;
 дату выполнения работы;
 цель занятия;
 условия предложенной задачи;
 построенную рекурсивную схему (полный базис, рекурсивные уравнения);
 реализацию соответствующей интерпретации;
 протокол выполнения программы;
 выводы о проделанной работе.
7. Краткий теоретический материал
11
Рекурсивные схемы
Рекурсивное программирование
Среди упомянутых выше методов формализации понятия вычислимой функции метод
Тьюринга — Поста основан на уточнении понятия процесса вычислений, для чего используются
абстрактные «машины», описанные в точных математических терминах. Другой подход (метод Черча
— Клини) основан на понятии рекурсивной функции, рекурсивная функция задается с помощью
рекурсивных определений. Рекурсивное определение позволяет связать искомое значение функции
для заданных аргументов с известными значениями той же функции при некоторых других
аргументах. Эта связь устанавливается с помощью универсального механизма рекурсии, дающего
механическую процедуру поиска значений функции. Двум подходам к определению вычислимых
функций соответствуют два метода программирования этих функций — операторное и рекурсивное
программирование. При операторном методе программа представляет собой явно выписанную
последовательность,
описаний
действий
гипотетической
вычислительной
машины
(последовательность операторов, команд и т. п.).
Язык Фортран — типичный представитель операторных языков. С другой стороны,
рекурсивная программа — это совокупность рекурсивных определений, задающих рекурсивную
функцию, для которой аргументами служат начальные данные программы, а значением — результат
выполнения программы. Известный язык рекурсивного программирования — язык Лисп —
предназначен для обработки символьной информации. В других зыках комбинируют оба метода
программирования. Так, Паскаль — операторный язык с возможностью рекурсивного
программирования, предоставляемой механизмом рекурсивных процедур и функций.
Примером рекурсивно определяемой функции является факториальная функция FACT: Nat →
Nat:
FACT(х) = 1,если х = 0, FACT(х)=хFACT(х — 1), если х >0.
Эту же функцию можно запрограммировать в некотором рекурсивном языке, базирующемся на
механизме рекурсивных функций языка Паскаль:
FACT(a),
FACT(х) = if х = 0 then 1 else х  FACT(х - 1),
где а — некоторое целое неотрицательное число.
Выполнение этой программы для некоторого значения а (пусть а=4) может быть осуществлено
следующим образом. В обе части рекурсивного определения вместо х подставляется 4, после чего
вычисляется правая часть определения. Вычисление правой части начинается с вычисления
логического выражения. Если его значение 1 (истина), то вычисляется левое функциональное
выражение (стоящее после then), а если его значение 0 (ложь) — вычисляется правое выражение
(стоящее после else). Вычисление функционального выражения сводится к его упрощению, т. е.
выполнению всех возможных вычислений. Если в упрощенном выражения остается вхождение
символа определяемой функции FACT, то осуществляется переход к новому шагу выполнения
программы. На этом шаге вхождение FACT(m), где m — значение внутри скобок после упрощения,
заменяется левым (т = 0) или правым (m > 0) функциональным выражением, в котором все
вхождения х заменены на m. Упрощения продолжаются до тех пор, пока не будет получено
выражение, не содержащее FACT (в нашем случае это выражение — число).
Вычисление рекурсивной программы может завершиться за конечное число шагов с
результатом, равным значению запрограммированной функции для заданных аргументов (начальных
значений переменных), но может и продолжаться бесконечно. В последнем случае значение функции
не определено.
Определение рекурсивной схемы
Рекурсивная схема (РС) так же, как СПП определяется в некотором базисе. Полный базис РС,
как и базис ССП, включает четыре счетных множества символов: переменные, функциональные
символы, предикатные символы, специальные символы.
Множества переменных и предикатных символов ничем не отличаются от ССП. Множество
специальных символов - другое, а именно: {if, то, else, (, ), ,}. Отличие множества функциональных
символов состоит в том, что оно разбито на два непересекающиеся подмножества: множество
базовых функциональных символов и множество определяемых функциональных символов
(обозначаются для отличия прописными буквами, например, F(1),G(2), и т.д.).
12
В базисе РС нет множества операторов, вместо него – множество логических выражений и
множество термов.
Простые термы определяются так же, как термы–выражения в СПП. Среди простых термов
выделим базовые термы, которые не содержат определяемых функциональных символов, а также
вызовы-термы вида F(n)(1,2,…n), где 1,2,… n - простые термы, F(n) - определяемый
функциональный символ.
Логическое выражение - слово вида
p(n)(1,2,…n),
(n)
где p - предикатный символ, а 1,2,…n - базовые термы.
Терм - это простой терм, или условный терм, т.е. слово вида if  then 1 else 2,
где  - логическое выражение, 1, 2 - простые термы, называемые левой и соответственно правой
альтернативой.
Примеры термов:
− f(x, g(x, y)); h(h(a)) - базовые термы;
− f(F(x), g(x, F(y))); H(H(a)) - простые термы;
− F(x); H(H(a)) - вызовы;
− if p(x, y) then h(h(a)) else F(x) - условный терм.
Используется бесскобочная форма представления:
if pxy then hha else Fx - условный терм.
Расширим в базисе В множество специальных символов символом "=".
Рекурсивным уравнением, или определением функции F назовем слово вида
F(n)(x1,x2,…xn) = (x1,x2,…xn),
где (x1,x2,…xn) - терм, содержащий переменные, называемые формальными параметрами функции
F.
Рекурсивной схемой называется пара (, М), где  - терм, называемый главным термом схемы
(или ее входом). М - такое множество рекурсивных уравнений, что все определяемые
функциональные символы в левых частях уравнений различны и всякий определяемый символ,
встречающийся в правой части некоторого уравнения или в главном терме схемы, входит в левую
часть некоторого уравнения. Другими словами, в РС имеется определение всякой вызываемой в ней
функции, причем ровно одно.
Примеры РС:
RS1: F(x); F(x) = if p(x) then a else g(x, F(h(x))).
RS2: A(b, c); A(x, y) = if p(x) then f(x) else B(x, y);
B(x, y) = if p(y) then A(g(x), a) else C(x, y);
C(x, y) = A(g(x), A(x, g(y))).
RS3: F(x); F(x) = if p(x) then x else f(F(g(x)), F(h(x))).
Пара (RS, I), где RS - PC в базисе В, а I - интерпретация этого базиса, называется рекурсивной
программой. При этом заметим, что определяемые функциональные символы не интерпретируются.
Протокол выполнения программы (RS1, I1), где I1 - интерпретация из практического занятия 1
(Рис. 1.1), выглядят следующим образом:
№ п/п
1
2
3
4
5
6
Значение терма для (RS1, I1)
F(4)
4*F(3)
4*(3*F(2))
4*(3*(2*F(1)))
4*(3*(2*(1*F(0))))
4*(3*(2*(1*1)))=24
8. Номер варианта
0
1
10
5
Последняя цифра зачетной книжки
2
3
4
5
6
7
Номер варианта
4
2
6
3
1
9
9. Варианты заданий
13
8
9
7
8
Номер
варианта
Действия, выполняемые программой
1
Расчет суммы членов арифметической
прогрессии. Разность арифметической
прогрессии d=1
2
Расчет произведения первых членов
арифметической
прогрессии.
Знаменатель прогрессии d=1
3
Расчет чисел Фибоначчи
4
Вкладчик положил в банк сумму в sum
единиц под p процентов за один период
времени (год). Составить рекурсивную
программу-функцию,
возвращающую
величину вклада по истечении n
периодов времени (n = 1, 2, …).
5
Пусть a - вещественное число отличное
от нуля и n есть целое неотрицательное
число.
Составить
рекурсивную
программу-функцию,
возвращающую
величину a n
6
Составить рекурсивную программуфункцию подсчета количества всех
положительных делителей натурального
числа n.
Нахождение наибольшего общего
делителя (алгоритм Евклида)
7
8
Пример для
выполнения
программы
Расчет суммы
первых
пяти
членов
прогрессии
Расчет
произведения
первых
пяти
членов
прогрессии
Расчет
седьмого числа
Фибоначчи
Рассчитать
величину
вклада в 100
руб. через 10
лет при
процентной
ставке в 2%.
Найти
значение 4 3
Рассчитать
количество
делителей для
числа 10.
Найти
наибольший
общий
делитель
чисел: 45 и 72
Составить рекурсивную программу- Рассчитать
функцию вычисления биномиальных значение
коэффициентов С(n,m), где n и m - целые функции C 3
3
и 0≤m≤n. При выполнении задачи
учитывать, что:
9
Расчет суммы первых n чисел Фибоначчи
10
Расчет произведения первых n чисел
Фибоначчи
14
Рассчитать
сумму пяти
первых чисел
Рассчитать
произведение
пяти первых
чисел
Лабораторная работа №4
«Аксиоматическая семантика. Определение слабейших предусловий
операторов»
1. Цель занятия
Изучение аксиоматической семантики, преобразователей предикатов и способов определения
слабейших предусловий операторов программ.
2. Литература
1.
В.Н. Агафонов. Спецификация программ: понятийные средства и их организация. Новосибирск: Наука (Сибирское отделение), 1987. - С. 30-73.
2.
Ian Sommerville. Software Engineering. - Addison-Wesley Publishing Company, 1992. - P.
3.
Д. Скотт. Теория решеток, типы данных и семантика// Данные в языках программирования. М.: Мир, 1982. - С. 25-53.
4.
У. Дал, Э. Дейкстра, К. Хоор. Структурное программирование. - М.: Мир, 1975. - С. 98-197.
3. Выполнение работы
 изучить аксиоматическую семантику, преобразователи предикатов и аксиоматическое
определение операторов языков программирования;
 в соответствии с вариантом задания разработать алгоритм программы, решающей поставленную
задачу;
 составить стандартную схему программы и записать полученную программу в линейной форме;
 для каждого оператора определить слабейшие предусловия;
 составить отчет по проделанной работе в соответствии с требованиями, предъявляемыми в
пункте 6 данного практического занятия.
4. Контрольные вопросы
1. Что такое аксиоматическая семантика?
2. Что такое триада Хоара? Из чего она состоит?
3. Что такое слабейшие предусловия? Каким образом они определяются?
4. Что такое преобразователь предикатов?
5. Перечислите свойства преобразователя предикатов.
6. Назовите слабейшие предусловия для основных операторов программы..
7. Сформулируйте основную теорему инвариантности оператора цикла.
5.





Содержание работы
ознакомиться с кратким теоретическим материалом, ответить на контрольные вопросы;
определить номер выполняемого варианта;
для выполнения предложенного варианта необходимо разработать алгоритм программы,
решающей поставленную задачу;
составить линейную форму стандартной схемы программ;
на основе составленной линейной формы определить и записать слабейшие предусловия для
каждого оператора стандартной схемы;
6. Содержание отчета
отчет должен содержать следующее:
 титульный лист с указанием наименования и цели занятия; фамилии, имени, отчества и номера
группы студента; фамилии, имени, отчества преподавателя, а также номера выполняемого
варианта;
 дату выполнения работы;
 цель занятия;
 условия предложенной задачи;
 алгоритм решения поставленной задачи на языке программирования высокого уровня;
 линейную форму стандартную схемы программы;
 составленные слабейшие предусловия для каждого оператора программы;
 выводы о проделанной работе.
15
7. Краткий теоретический материал
Аксиоматическая семантика
Аксиоматическая семантика была создана в процессе разработки метода доказательства
правильности программ. Данный метод распространяет на программы область применения
исчисления предикатов. Семантику каждой синтаксической конструкции языка можно определить
как некий набор аксиом или правил вывода, который можно использовать для вывода результатов
выполнения этой конструкции. Чтобы понять смысл всей программы (то есть разобраться, что и как
она делает), эти аксиомы и правила вывода следует использовать так же, как при доказательстве
обычных математических теорем. В предположении, что значения входных переменных
удовлетворяют некоторым ограничениям, аксиомы и правила вывода могут быть использованы для
получения (вывода) ограничений на значения других переменных после выполнения каждого
оператора программы. В конце концов, когда программа выполнена, мы получаем доказательство
того, что вычисленные результаты удовлетворяют необходимым ограничениям на их значения
относительно входных значений. То есть, доказано, что выходные данные представляют значения
соответствующей функции, вычисленной по значениям входных данных.
Такие доказательства показывают, что программа выполняет вычисления, описанные ее
спецификацией. В доказательстве каждый оператор программы сопровождается предшествующим и
последующим логическими выражениями, устанавливающими ограничения на переменные в
программе. Эти выражения используются для определения смысла оператора вместо полного
описания состояния абстрактной машины (как в операционной семантике).
Аксиоматическая семантика основана на математической логике. Будем называть предикат,
помещенный в программу утверждением. Утверждение, непосредственно предшествующее
оператору программы, описывает ограничения, наложенные на переменные в данном месте
программы. Утверждение, следующее непосредственно за оператором программы, описывает новые
ограничения на те же (а возможно, и другие) переменные после выполнения оператора.
Введем обозначение (триада Хоара)
{Q} S {R}
(3.1)
где Q, R - предикаты, S - программа (оператор или последовательность операторов).
Обозначение определяет следующий смысл: «Если выполнение S началось в состоянии,
удовлетворяющем Q, то имеется гарантия, что оно завершится через конечное время в
состоянии, удовлетворяющем R».
Предикат Q называется предусловием или входным утверждением S, предикат R постусловием или выходным утверждением. Следовательно, R определяет то, что нужно установить.
Можно сказать, что R определяет спецификацию задачи. В предусловии Q нужно отражать тот факт,
что входные переменные получили начальные значения.
В дальнейшем при изучении утверждений мы будем предполагать, что предусловия операторов
вычисляются на основе постусловий, хотя этот процесс можно рассматривать и с противоположной
точки зрения. Предположим, что.
Пример 3.1 Рассмотрим оператор присваивания для целочисленных переменных и
постусловие:
sum := 2 * х + 1 {sum > 1}
Одним из возможных предусловий данного оператора может быть {х > 10}.
Слабейшими предусловиями называются наименьшие предусловия, обеспечивающие
выполнение соответствующего постусловия. Например, для приведенного выше оператора и его
постусловия предусловия {х > 10}, {х > 50} и {х > 1000} являются правильными. Слабейшим из всех
предусловий в данном случае будет {х > 0}.
Преобразователь предикатов.
Э. Дейкстра рассматривает слабейшие предусловия, т.е. предусловия, необходимые и
достаточные для гарантии желаемого результата.
«Условие, характеризующее множество всех начальных состояний, при которых запуск
обязательно приведет к событию правильного завершения, причем система (машина, конструкция)
16
останется в конечном состоянии, удовлетворяющем заданному постусловию, называется слабейшим
предусловием, соответствующим этому постусловию».
Условие называют слабейшим, так как чем слабее условие, тем больше состояний
удовлетворяют ему. Наша цель - охарактеризовать все возможные начальные состояния, которые
приведут к желаемому конечному состоянию.
Если S - некоторый оператор (последовательность операторов), R - желаемое постусловие, то
соответствующее слабейшее предусловие будем обозначать wp(S, R).
Аббревиатура wp определяется начальными буквами английских слов weakest (слабейший) и
precondition (предусловие). Предполагается, что известно, как работает оператор S (известна
семантика S), если можно вывести для любого постусловия R соответствующее слабейшее
предусловие wp(S, R).
Определение семантики оператора дается в виде правила, описывающего, как для любого
заданного постусловия R можно вывести соответствующее слабейшее предусловие wp(S, R).
Для фиксированного оператора S такое правило, которое по заданному предикату R
вырабатывает предикат wp(S,R), называется «преобразователем предикатов»: {wp(S, R)} S {R}.
Это значит, что описание семантики оператора S представимо с помощью преобразователя
предикатов. Применительно к конкретным S и R часто бывает неважным точный вид wp(S,R), бывает
достаточно более сильного условия Q, т.е. условия, для которого можно доказать, что утверждение Q
=> wp(S, R) справедливо для всех состояний. Значит, множество состояний, для которых Q - истина,
является подмножеством того множества состояний, для которых wp(S, R) - истина. Возможность
работать с предусловиями Q, не являющимися слабейшими, полезна, поскольку выводить wp(S, R)
явно не всегда практично.
Сформулируем свойства (по Э. Дейкстра) wp(S, R).
Свойство 1. wp (S, F) = F для любого S. (Закон исключенного чуда).
Свойство 2. Закон монотонности. Для любого S и предикатов P и R таких, что P => R для всех
состояний, справедливо для всех состояний wp(S, P) => wp(S, R).
Свойство 3. Дистрибутивность конъюнкции. Для любых S, P, R справедливо
wp(S, P) AND wp(S, R) = wp(S, P AND R).
Свойство 4. Дистрибутивность дизъюнкции. Для любых S, P, R справедливо
wp(S, P) OR wp(S, R) = wp(S, P OR R).
Если для каждого оператора языка по заданным постусловиям можно вычислить слабейшее
предусловие, то для программ на данном языке может быть построено корректное доказательство.
Доказательство начинается с использования результатов, которые надо получить при выполнении
программы, в качестве постусловия последнего оператора программы, и выполняется с помощью
отслеживания программы от конца к началу с последовательным вычислением слабейших
предусловий для каждого оператора. При достижении начала программы первое ее предусловие
отражает условия, при которых программа вычислит требуемые результаты.
Для некоторых операторов программы вычисление слабейшего предусловия на основе
оператора и его постусловия является достаточно простым и может быть задано с помощью аксиомы.
Однако, как правило, слабейшее предусловие вычисляется только с помощью правила логического
вывода, т.е. метода выведения истинности одного утверждения на основе значений остальных
утверждений.
Аксиоматическое определение основных операторов языка программирования в
терминах wp.
Определим слабейшее предусловие для основных операторов: оператора присваивания,
составного оператора, оператора выбора и оператора цикла.
Оператор присваивания имеет вид: x := E, где x - простая переменная, E – выражение (типы x
и E совпадают).
Определим слабейшее предусловие оператора присваивания как Q = wp(x := E, R), где Q
получается из R заменой каждого вхождения x на E, что обозначим Q = RxЕ.
Предполагается, что значение Е определено и вычисление выражения Е не может изменить
значения ни одной переменной. Последнее ограничение запрещает функции с побочным эффектом.
Следовательно, можно использовать обычные свойства выражений такие, как ассоциативность,
коммутативность и логические законы.
Составной оператор имеет вид: begin S1; S2; ... ; Sn end
17
Определим слабейшее предусловие для последовательности двух операторов:
wp(S1;S2, R) = wp(S1, wp(S2, R)).
Аналогично слабейшее предусловие определяется для последовательности из n операторов.
Оператор выбора определим так: if B1 → S1 П B2 → S2 ... П Bn → Sn fi
Здесь n  0, B1, B2, ..., Bn - логические выражения, называемые охранами, S1, S2, ..., Sn операторы, пара Bi → Si называется охраняемой командой, П - разделитель, if и fi играют роль
операторных скобок.
Выполняется оператор следующим образом.
Проверяются все Bi. Если одна из охран не определена, то происходит аварийное завершение.
Далее, по крайней мере, одна из охран должна иметь значение истина, иначе выполнение завершается
аварийно.
Выбирается одна из охраняемых команд Bi → Si, у которой значение Bi истина, и выполняется
Si.
Определим слабейшее предусловие:
wp(if, R) = BB AND (B1 => wp(S1, R)) AND ... AND (Bn => wp(Sn, R)),
где BB = B1 OR B2 OR ... OR Bn.
Предполагается, что охраны являются всюду определенными функциями (значение их
определено во всех состояниях).
Естественно определить wp(if, R) с помощью кванторов:
wp(if, R) = ( i: 1  i  n : Bi ) AND (i: 1  i  n : Bi => wp(Si, R))
Пример 2. Определить z = |x|.
С использованием оператора выбора :if x  0 → z := x П x  0 → z := -x fi.
К особенностям оператора выбора следует отнести, во-первых, тот факт, что он включает
условный оператор (if... then..), альтернативный оператор (if… then... else...) и оператор выбора (case).
Во-вторых, оператор выбора не допускает умолчаний, что помогает при разработке сложных
программ, так как каждая альтернатива представлена подробно, и возможность что-либо упустить
уменьшается.
В-третьих, благодаря отсутствию умолчаний, запись оператора выбора представлена в
симметричном виде.
Оператор цикла. В обозначениях Э. Дейкстры цикл имеет вид: do B → S do.
Обозначим это соотношение через DO и представим его в следующем виде:
DO: do B1 → S1 П B2 → S2 ... П Bn → Sn od, где n  0, Bi → Si - охраняемые команды.
Выполняется оператор следующим образом. Пока возможно выбирается охрана Bi со
значением истина, и выполняется соответствующий оператор Si. Как только все охраны будут иметь
значение ложь, выполнение DO завершится.
Выбор охраны со значением истина и выполнение соответствующего оператора называется
выполнением шага цикла. Если истинными являются несколько охран, то выбирается любая из них.
Следовательно, оператор DO эквивалентен оператору
do BB → if B2 → S1 П B2 → S2 ... П Bn → Sn fi od или do BB → IF od,
где BB - дизъюнкция охран, IF - оператор выбора.
Дадим формальное определение слабейшего предусловия для оператора цикла DO.
Пусть предикат H0(R) определяет множество состояний, в которых выполнение DO
завершается за 0 шагов (в этом случае все охраны с самого начала ложны, после завершения R имеет
значение истина):
H0(R) = NOT BB AND R
Другими словами, требуется, чтобы оператор цикла DO завершил работу, не производя
выборки охраняемой команды, что гарантируется первым конъюнктивным членом предиката H0(R):
NOT BB = T. При этом истинность R до выполнения DO является необходимым условием для
истинности R после выполнения DO.
Определим предикат Hk(R) как множество состояний, в которых выполнение DO заканчивается
за k шагов при значении R истина (Hk(R) будет определяться через Hk-1(R)):
Hk(R) = H0(R) OR wp(IF, Hk-1(R)), k > 0 → wp(DO, R) = ( k: k  0: Hk(R)).
Это значит, что должно существовать такое значение k, что потребуется не более, чем k шагов,
для обеспечения завершения работы в конечном состоянии, удовлетворяющем постусловию R.
Определение DO. Если предикаты Hk(R) задаются в виде
Hk(R) = NOT B AND R, k = 0
Hk(R) = wp(IF, Hk-1(R)), k > 0, → wp (DO,R)=( k: k  0: Hk(R))
18
Основная теорема для оператора цикла. Пусть оператор выбора IF и предикат P таковы, что
для всех состояний справедливо
(P AND BB) => wp(IF, R).
(3.2)
Тогда для оператора цикла справедливо:
(P AND wp(DO, T)) => wp(DO, P AND NOT BB).
Эта теорема известна как основная теорема инвариантности для цикла. Предикат Р,
истинный перед выполнением и после выполнения каждого шага цикла, называется
инвариантным отношением или просто инвариантом цикла. В математике термин
«инвариантный»
означает
не
изменяющийся
под
воздействием
совокупности
рассматриваемых математических операций.
Поясним смысл теоремы. Условие (3.2) означает, что если предикат P первоначально
истинен и одна из охраняемых команд выбирается для выполнения, то после ее выполнения
P сохранит значение истинности. После завершения оператора, когда ни одна из охран не
является истиной, будем иметь:
P AND NOT BB.
Работа завершится правильно, если условие wp(DO, T) справедливо и до выполнения
DO. Так как любое состояние удовлетворяет T, то wp(DO,T) является слабейшим
предусловием для начального состояния такого, что запуск оператора цикла DO приведет к
правильно завершаемой работе.
19
8. Номер варианта
0
1
5
9
Последняя цифра зачетной книжки
3
4
5
6
7
Номер варианта
6
3
2
7
4
10
2
9. Варианты заданий
Номер
варианта
1
2
3
4
5
6
7
8
9
10
Действия, выполняемые программой
Расчет суммы членов арифметической прогрессии.
Расчет суммы первых членов геометрической прогрессии.
Расчет чисел Фибоначчи
Расчет произведения членов арифметической прогрессии.
Расчет произведения первых членов геометрической
прогрессии.
Расчет суммы чисел Фибоначчи
Расчет произведения чисел Фибоначчи
Решение квадратного уравнения
Нахождение наименьшего общего кратного двух чисел
Нахождение наибольшего общего делителя (алгоритм
Евклида)
20
8
9
8
1
Лабораторная работа №5
«Верификация программ»
1. Цель занятия
Изучение верификации как способа доказательства правильности программ, метода
индуктивных утверждений и правил верификации Хоара.
2. Литература
1. Непомнящий В.А., Рякин О.М. Прикладные методы верификации программ. М.: Радио и
связь. 1988
2. Андерсон Р. Доказательство правильности программ. М., Мир, 1982.
3. Вирт Н. Систематическое программирование. Введение. М., Мир, 1977.
3. Выполнение работы
 изучить метода индуктивных утверждений и правила верификации Хоара;
 в соответствии с вариантом задания разработать алгоритм программы, решающей поставленную
задачу;
 составить стандартную схему программы и записать полученную программу в линейной форме;
 используя метод индуктивных утверждений и правила верификации Хоара произвести
верификацию программы;
 составить отчет по проделанной работе в соответствии с требованиями, предъявляемыми в
пункте 6 данного практического занятия.
Контрольные вопросы
Какие методы доказательства правильности программ Вам известны?
Что такое верификация программ?
В чем суть метода индуктивных утверждений?
Изложите алгоритм доказательства правильности программы
утверждений.
5. Что такое набросок доказательства?
6. Сформулируйте правила верификации Хоара.
4.
1.
2.
3.
4.
5.






методом
индуктивных
Содержание работы
ознакомиться с кратким теоретическим материалом, ответить на контрольные вопросы;
определить номер выполняемого варианта;
для выполнения предложенного варианта необходимо разработать алгоритм программы,
решающей поставленную задачу;
составить линейную форму стандартной схемы программ;
на основе составленной линейной формы составить входные и выходные утверждения;
построить и доказать условия верификации.
6. Содержание отчета
Отчет должен содержать следующее:
 титульный лист с указанием наименования и цели занятия; фамилии, имени, отчества и номера
группы студента; фамилии, имени, отчества преподавателя, а также номера выполняемого
варианта;
 дату выполнения работы;
 цель занятия;
 условия предложенной задачи;
 алгоритм решения поставленной задачи на языке программирования высокого уровня;
 линейную форму стандартную схемы программы;
 составленные входное и выходное утверждения;
 построенные условия верификации;
 доказательство условий верификации;
 выводы о проделанной работе.
21
7. Краткий теоретический материал
Верификация программ.
Методы доказательства правильности программ.
Как
известно,
универсальные
вычислительные
машины
могут
быть
запрограммированы для решения самых разнородных задач - в этом заключается одна из
основных их особенностей, имеющая огромную практическую ценность. Один и тот же
компьютер, в зависимости от того, какая программа находится у него в памяти, способен
осуществлять арифметические вычисления, доказывать теоремы и редактировать тексты,
управлять ходом эксперимента и создавать проект автомобиля будущего, играть в шахматы
и обучать иностранному языку. Однако успешное решение всех этих и многих других задач
возможно лишь при том условии, что компьютерные программы не содержат ошибок,
которые способны привести к неверным результатам.
Можно сказать, что требование отсутствия ошибок в программном обеспечении
совершенно естественно и не нуждается в обосновании. Но как убедиться в том, что
ошибки, в самом деле, отсутствуют? Вопрос не так прост, как может показаться на первый
взгляд.
К неформальным методам доказательства правильности программ относят отладку и
тестирование, которые являются необходимой составляющей на всех этапах процесса
программирования, хотя и не решают полностью проблемы правильности. Существенные
ошибки легко найти, если использовать соответствующие приемы отладки (контрольные
распечатки, трассировки).
Тестирование – процесс выполнения программы с намерением найти ошибку, а не
подтвердить правильность программы. Суть его сводится к следующему. Подлежащую
проверке программу неоднократно запускают с теми входными данными, относительно
которых результат известен заранее. Затем сравнивают полученный машиной результат с
ожидаемым. Если во всех случаях тестирования налицо совпадение этих результатов,
появляется некоторая уверенность в том, что и последующие вычисления не приведут к
ошибочному итогу, т.е. что исходная программа работает правильно.
Мы уже обсуждали понятие правильности программы с точки зрения отсутствия в ней
ошибок. С интуитивной точки зрения программа будет правильной, если в результате ее
выполнения будет достигнут результат, с целью получения которого и была написана
программа. Сам по себе факт безаварийного завершения программы еще ни о чем не
говорит: вполне возможно, что программа в действительности делает совсем не то, что
было задумано. Ошибки такого рода могут возникать по различным причинам.
В дальнейшем мы будем предполагать, что обсуждаемые программы не содержат
синтаксических ошибок, поэтому при обосновании их правильности внимание будет
обращаться только на содержательную сторону дела, связанную с вопросом о том,
достигается ли при помощи данной программы данная конкретная цель. Целью можно
считать поиск решения поставленной задачи, а программу рассматривать как способ ее
решения. Программа будет правильной, если она решит сформулированную задачу.
Метод установления правильности программ при помощи строгих средств известен как
верификация программ.
В отличие от тестирования программ, где анализируются свойства отдельных
процессов выполнения программы, верификация имеет дело со свойствами программ.
В основе метода верификации лежит предположение о том, что существует
программная документация, соответствие которой требуется доказать. Документация
должна содержать:
 спецификацию ввода-вывода (описание данных, не зависящих от процесса обработки);
 свойства отношений между элементами векторов состояний в выбранных точках программы;
 спецификации и свойства структурных подкомпонентов программы;
 спецификацию структур данных, зависящих от процесса обработки.
К такому методу доказательства правильности программ относится метод
индуктивных утверждений, независимо сформулированный К. Флойдом и П. Науром.
Суть этого метода состоит в следующем:
22
1) формулируются входное и выходное утверждения: входное утверждение описывает
все необходимые входные условия для программы (или программного фрагмента),
выходное утверждение описывает ожидаемый результат;
2) предполагая истинным входное утверждение, строится промежуточное
утверждение, которое выводится на основании семантики операторов, расположенных
между входом и выходом (входным и выходным утверждениями); такое утверждение
называется выведенным утверждением;
3) формулируется теорема (условия верификации):
из выведенного утверждения следует выходное утверждение;
4) доказывается теорема; доказательство свидетельствует о правильности программы
(программного фрагмента).
Доказательство проводится при помощи хорошо разработанных математических
методов, использующих исчисление предикатов первого порядка.
Условия верификации можно построить и в обратном направлении, т.е., считая
истинным выходное утверждение, получить входное утверждение и доказывать теорему:
«из входного утверждения следует выведенное утверждение».
Такой метод построения условий верификации моделирует выполнение программы в
обратном направлении. Другими словами, условия верификации должны отвечать на такой
вопрос: если некоторое утверждение истинно после выполнения оператора программы, то,
какое утверждение должно быть истинным перед оператором?
Построение индуктивных утверждений помогает формализовать интуитивные
представления о логике программы. Оно и является самым сложным в процессе
доказательства правильности программы. Это объясняется, во-первых, тем, что необходимо
описать все содержательные условия, и, во-вторых, тем, что необходимо аксиоматическое
описание семантики языка программирования.
Важным шагом в процессе доказательства является доказательство завершения
выполнения программы, для чего бывает достаточно неформальных рассуждений.
Таким образом, алгоритм доказательства правильности программы методом
индуктивных утверждений представляется в следующем виде:
1) Построить структуру программы.
2) Выписать входное и выходное утверждения.
3) Сформулировать для всех циклов индуктивные утверждения.
4) Составить список выделенных путей.
5) Построить условия верификации.
6) Доказать условие верификации.
7) Доказать, что выполнение программы закончится.
Этот метод сравним с обычным процессом чтения текста программы (метод сквозного
контроля). Различие заключается в степени формализации.
Преимущество верификации состоит в том, что процесс доказательства настолько
формализуем, что он может выполняться на вычислительной машине. В этом направлении
в восьмидесятые годы проводились исследования, даже создавались автоматизированные
диалоговые системы, но они не нашли практического применения.
Использование утверждений в программах.
Утверждения используются для доказательства правильности программ. Тогда
утверждения необходимо формулировать в некоторой формальной логической системе.
Обычно используется исчисление предикатов первого порядка.
Исчисление - это метод или процесс рассуждений посредством вычислений над
символами. В исчислении предикатов утверждения являются логическими переменными или
выражениями, имеющими значение T - истина или F - ложь. Наша цель - при написании
программы некоторым способом доказать истинность утверждения - триады Хоара {Q} S {R}.
Для этого нужно уметь записывать его в исчислении предикатов и формально доказывать
его истинность.
Предикат, помещенный в программу, был нами назван утверждением. Утверждается,
что он истинен в соответствующий момент выполнения программы. В предусловии Q нужно
23
отражать тот факт, что входные переменные получили начальные значения. Для
обозначения начальных значений будем использовать большие буквы.
Пример 4.1 Пусть надо определить приближенное значение квадратного корня: s =
sqrt(n), где n, s  Nat. Определим постусловие в виде:
R: s*s  n < (s+1)*(s+1).
Пример 4.2 Даны целочисленные n > 0 и массив a[1,...,n]. Отсортировать массив, т.е.
установить
R: ( i: 1  i < n: a[i]  a[i+1]).
Пример 4.3 Определить x как максимальное значение массива a[1,...,n]. Определим
постусловие:
R: {x = max({y | y  a})}.
Для построения программы следует определить математическое понятие max. Тогда
R: {( i: 1  i  n: x = a[i]) AND ( i: 1  i  n: a[i] = x)}.
Пример 4.4 Пусть имеем программу S обмена значениями двух целых переменных a и
b. Сформулируем входное и выходное утверждения программы и представим программу S в
виде предиката:
{ a = A AND b = B } S { a = B AND b = A },
(4.1)
где A, B - конкретные значения переменных a, b.
Программа вместе с утверждениями между каждой парой соседних операторов
называется наброском доказательства. Последовательно, для каждого оператора
программы формулируя предикат (1), можно доказать, что программа удовлетворяет своим
спецификациям. Представим набросок доказательства для программы S:
{ a = A AND b = B }
r := a; { r = a AND a = A AND b = B };
a := b; { r = a AND a = B AND b = B };
b := r; { a = B AND b = A }.
Не обязательно набросок доказательства должен быть настолько полным. Для
документирования программы нужно вставить достаточно утверждений, чтобы программа
стала понимаемой.
Программа, содержащая утверждения для ее документирования, называется
аннотированной программой. Чтобы использовать утверждения для доказательства
правильности программы, необходимы соответствующие правила верификации.
Правила верификации Хоара.
Сформулируем правила (аксиомы) К.Хоара, которые определяют предусловия как
достаточные предусловия, гарантирующие, что исполнение соответствующего оператора
при успешном завершении приведет к желаемым постусловиям.
A1. Аксиома присваивания: { Ro } x := Е { R }
Неформальное объяснение аксиомы: так как x после выполнения будет содержать
значение Е, то R будет истинно после выполнения, если результат подстановки Е вместо x в
R истинен перед выполнением. Таким образом, Ro = R(x) при x = E. Для Ro вводится
обозначение: Ro = RxЕ (у Вирта) или Rx→Е (у Дейкстры), что означает, что x заменяется на
Е.
Аксиома присваивания будет иметь вид:{RxЕ} x := Е {R}.
Сформулируем два очевидных правила монотонности.
A2. Если известно: { Q } S { P } и { P } => { R }, то { Q } S { R }
A3. Если известно: { Q } S { P } и { R } => { Q }, то { R } S { P }
Пусть S - это последовательность из двух операторов S1; S2 (составной оператор).
A4. Если известно:{ Q } S1 { P1 } и { P1 } S2 { R }, то { Q } S { R }.
Это правило можно сформулировать для последовательности, состоящей из n
операторов.
Сформулируем правило для условного оператора (краткая форма).
A5. Если известно:
{ Q AND B } S1 { R } и { Q NOT B } => { R },то { Q } if B then S1 { R }.
Правило A5 соответствует интерпретации условного оператора в языке
программирования.
24
Сформулируем правило для альтернативного оператора (полная форма условного
оператора).
A6. Если известно: { Q AND B } S1 { R } и { Q NOT B } S2 { R },то { Q } if B then S1 else S2
{ R }.
Сформулируем правила для операторов цикла.
Предусловия и постусловия цикла until удовлетворяют правилу:
A7. Если известно: { Q AND NOT B } S1 { Q }, то { Q } repeat S1 until B { Q AND NOT B }
Правило отражает инвариантность цикла. В данном случае единственная операция это выполнение шага цикла при условии истинности Q вначале.
Предусловия и постусловия цикла while удовлетворяют правилу:
A8. Если известно: { Q AND B } S1 { Q } , то { Q } while B do S1 { Q AND NOT B }
Правила A1 - A8 можно использовать для проверки согласованности передачи данных
от оператора к оператору, для анализа структурных свойств текстов программ, для
установления условий окончания цикла и для анализа результатов выполнения программы.
Пример 4.5 (верификация программы) Пусть надо определить частное q и остаток r
от деления x на y.
Входные данные x, y и выходные данные q, r  Nat, причем y > 0.
Задать(x,y); /* x,y получают конкретные значения X,Y */
r := x; q := 0;
while y  r do
begin
r := r - y; q := q + 1
end;
выдать(q,r);
Сформулируем постусловие
R: (r < y) AND (x = y*q + r)
Нужно доказать, что
{y > 0 AND x/y} S {(r < y) AND (x = y*q + r )}.
Доказательство.
Очевидно, что Q => x = x + y * 0.
Применим аксиому A1 к оператору r := x, тогда получим { x = x + y * 0 } r := x { x = r + y * 0 }
Аналогично, применяя A1 к оператору q := 0, получим: { x = r + y * 0 } q := 0 { x = r + y*q }
Применяя правило A3 к результатам пунктов 1 и 2, получим { Q } r := x { x = r + y * 0 }
Применяя правило A4 к результатам пунктов 4 и 3, получим { Q } r := x; q := 0 { x = r + y*q }
Выполним равносильное преобразование x = r + y * q AND y  r => x = (r - y) + y*(q + 1)
Применяя правило A1 к оператору r:= r - y, получим {x = (r - y) + y*( q + 1)} r:= r - y {x = r+
y*(q+1)}
Для оператора q := q + 1 аналогично получим { x = r + y*(q + 1) } q := q + 1 { x = r + y*q }
Применяя правило A4 к результатам пунктов 7 и 8, получим
{ x = (r - y) + y*( q + 1) } r := r - y; q := q + 1 { x = r + y*q }
Применяя правило A2 к результатам пунктов 6 и 9, получим
{ x = r + y*q AND y  r } r := r - y; q := q + 1 { x = r + y*q }
Применяя правило A8 к результату пункта 10, получим
{x = r + y*q } while y  r do begin r := r - y; q := q + 1 end { NOT (y <= r) AND (x = r + y*q) }
Утверждение x = r + y*q является инвариантом цикла, так как значение его остается
истинным до цикла и после выполнения каждого шага цикла.
Применяя правило A4 к результатам пунктов 5 и 11, получаем то, что требовалось доказать,
{ Q } S { NOT (y  r) AND (x = r + y*q) }
Осталось доказать, что выполнение программы заканчивается.
Доказывать будем от противного, т.е. предположим, что программа не заканчивается. Тогда
должна существовать бесконечная последовательность значений r и q, удовлетворяющая
условиям
1) y  r;
2) r, q  Nat.
Но значение r на каждом шаге цикла уменьшается на положительную величину: r := r y (y > 0). Значит, последовательность значений r и q является конечной.
25
8. Номер варианта
0
1
4
1
Последняя цифра зачетной книжки
3
4
5
6
7
Номер варианта
5
9
6
3
8
7
2
9. Варианты заданий
Номер
варианта
1
2
3
4
5
6
7
8
9
10
Действия, выполняемые программой
Расчет суммы членов арифметической прогрессии.
Расчет суммы первых членов геометрической прогрессии.
Расчет чисел Фибоначчи
Расчет произведения членов арифметической прогрессии.
Расчет произведения первых членов геометрической
прогрессии.
Расчет суммы чисел Фибоначчи
Расчет произведения чисел Фибоначчи
Решение квадратного уравнения
Нахождение наименьшего общего кратного двух чисел
Нахождение наибольшего общего делителя (алгоритм
Евклида)
26
8
9
10
2
Лабораторная работа №6
«Разработка и исследование мультизадачных приложений в операционных системах Microsoft
Windows»
18. Цель занятия
Изучение способов построения мультизадачных приложений в операционных системах Microsoft
Windows. Разработка и исследование учебного мультизадачного приложения.
19. Литература
1.Фролов А.В., Фролов Г.В. Программирование для Windows NT. – М: ДИАЛОГ-МИФИ, 1996. – 272
с. – (Библиотека системного программиста; Т.26).
2.Фролов А.В., Фролов Г.В. Операционная система Windows 95 для программиста. – М: ДИАЛОГМИФИ, 1996. – (Библиотека системного программиста; Т.22).
3.Фролов А.В., Фролов Г.В. Графический интерфейс GDI в Microsoft Windows. – М: ДИАЛОГМИФИ, 1994. – (Библиотека системного программиста; Т.14).
4.Саймон Р. Windows 2000 API Энциклопедия. – М: ДиаСофт, 2002.- 1088 с.
5.Неббет Г. Справочник по базовым функциям API Windows NT/2000. – М: Вильямс, 2002. – 528 с.





20. Выполнение работы
Изучить:
 способы построения мультизадачных приложений (создание, запуск, остановка,
завершение, а также изменение приоритета задач);
 синхронизацию выполняющихся задач с помощью критических секций;
 способы рисования геометрических фигур;
разработать алгоритм работы учебного мультизадачного приложения;
программно реализовать учебное мультизадачное приложение;
исследовать работу, разработанного приложения;
составить отчет по проделанной работе в соответствии с требованиями, предъявляемыми в
пункте 6 настоящего пособия.
21. Контрольные вопросы
18. Что такое процесс, задача? Чем процесс отличается от задачи?
19. Каким образом осуществляется запуск задачи? Какие еще существуют способы запуска
процесса?
20. Каким образом можно узнать приоритет выполняемой задачи?
21. Каким образом можно задать необходимый приоритет для выполняемой задачи?
22. Какие виды приоритетов вам известны? Какие значения может принимать приоритет?
23. Как можно приостановить выполнение задачи? Каким образом продолжить выполнение
приостановленной задачи;
24. Как временно приостановить выполнение задачи?
25. Как завершается выполнение запроса?
26. Что такое критическая секция и для чего она предназначена?
27. Прокомментируйте работу с критическими секциями





22. Содержание работы
Ознакомиться с кратким теоретическим материалом, ответить на контрольные вопросы;
определить номер выполняемого варианта;
разработать алгоритм работы учебного мультизадачного приложения;
разработать и отладить программу работы учебного мультизадачного приложения;
требования к разрабатываемому учебному мультизадачному приложению:
 должно обеспечивать запуск неограниченного числа задач;
 перед запуском задачи пользователь должен указать ее приоритет;
 пользователь должен иметь возможность приостановить выполнение выбранной задачи, а
также продолжить ее выполнение после остановки;
27




пользователь должен иметь возможность завершать выбранную задачу;
пользователь должен иметь возможность изменять приоритет выбранной задачи;
пользователь должен иметь возможность получить информацию о приоритете выбранной
задачи и ее идентификаторе (handle);
 каждая задача должна последовательно выполнять рисование следующих геометрических
объектов в окне: эллипсов, прямоугольников, а также выводить произвольный текст.
Координаты местоположения геометрических объектов и текста в окне, а также их
размеры и цвет выбираются каждый раз произвольно при помощи генератора случайных
чисел.
 каждая задача для всех типов геометрических объектов и текста должна вести учет
количества ранее нарисованных объектов начиная с момента запуска задачи.
Приостановка выполнения задачи пользователем не должна изменять учитываемые
значения. Пользователь должен иметь возможность обнулять учитываемые значения как
для выбранной задачи, так и для всех запущенных задач;
 каждая задача должна рисовать геометрические объекты в окне приложения (SDIприложение);
 синхронизация процесса рисования между выполняющимися задачами
должна
производиться при помощи критической секции
произвести исследование работы учебного мультизадачного приложения:
 необходимо провести пять серий измерений количества выведенных геометрических
объектов и текста для каждой задачи в соответствии с вариантом задания;
 выполнение приложения для получения результатов должно производиться одну минуту;
 полученные результаты необходимо занести в таблицу:
№
серии

Номер
Задачи
Приоритет
задачи
Количество объектов,
нарисованных задачей
ЭллипПрямо- Текста
сов
угольников
сделать вывод о зависимости скорости выполнения задачи от ее приоритета;
23. Содержание отчета
Отчет должен содержать следующее:
 титульный лист с указанием наименования и цели занятия; фамилии, имени, отчества и номера
группы студента; фамилии, имени, отчества преподавателя;
 дату выполнения работы;
 цель занятия;
 номер выполняемого варианта;
 условия предложенной задачи;
 код программы, реализующей учебное мультизадачное приложение;
 результаты исследований работы учебного мультизадачного приложения:
 выводы о проделанной работе.
24. Краткий теоретический материал
Процессы и задачи в Microsoft Windows
В операционных системах Microsoft Windows существует два понятия, имеющие отношение к
мультизадачности. Это процессы и задачи.
28
Процесс (process) создается, когда программа загружается в память для выполнения. Вы
создаете процессы, запуская, например, консольные программы или графические приложения при
помощи Проводника. Процессу выделяется в монопольное владение 2 Гбайт изолированного
адресного пространства, в которое другие процессы не имеют никакого доступа.
Сразу после запуска процесса создается одна задача (thread), или, как ее еще называют в
литературе, поток. Задача - это просто фрагмент кода приложения, который может выполняться
автономно и независимо от других задач в рамках одного процесса. При необходимости эта задача
может запускать другие задачи, реализуя, таким образом, мультизадачность в рамках процесса. Все
задачи имеют доступ к памяти, выделенной запустившему их процессу.
Из сказанного выше следует, что, с одной стороны, в операционных системах Microsoft
Windows могут работать одновременно несколько процессов, с другой - в рамках каждого процесса
могут параллельно работать несколько задач. Пользователь может запустить процесс, загрузив ту или
иную программу в память для выполнения, но он не может запустить задачу, так как эта операция
выполняется только процессами.
Запуск задач
Для запуска задач будем использовать функцию CreateThread. Прототип данной функции
приводится ниже:
HANDLE CreateThread(
LPSECURITY_ATTRIBUTES
lpThreadAttributes,
DWORD dwStackSize,
LPTHREAD_START_ROUTINE
lpStartAddress,
LPVOID lpPar// флаг наследования
// идентификатора
ameter,
DWORD dwCreationFlags,
LPWORD lpThreadId);
// атрибуты защиты
// начальный размер стека
в
// байтах
// адрес функции задачи
// параметры для задачи
// параметры создания
задачи
// адрес переменной для
// идентификатора задачи
Через параметр IpThreadAttributes передается адрес структуры SECURITY_ATTRIBUTES,
определяющей атрибуты защиты для создаваемой задачи, или значение NULL. В последнем случае
для задачи будут использованы атрибуты защиты, принятые по умолчанию. Это означает, что
идентификатор созданной задачи можно использовать в любых функциях, выполняющих любые
операции над задачами. Указывая атрибуты защиты, вы можете запретить использование тех или
иных функций. Приведем структуру SECURITY_ATTRIBUTES:
typedef struct _SECURITY_ATTRIBUTES
{
DWORD nLength;
LPVOID IpSecurityDescriptor;
BOOL blnheritHandle;
// размер структуры в
байтах
// указатель на
дескриптор
// защиты
// флаг наследования
// идентификатора
} SECURITY_ATTRIBUTES;
При подготовке структуры в поле nLength следует записать размер структуры
SECURITY_ATTRIBUTES.
Поле указателя на дескриптор защиты IpSecurityDescriptor не заполняется приложением
непосредственно. Вместо этого для установки дескриптора защиты используется набор функций,
29
которым в качестве одного из параметров передается указатель на структуру
SECURITY_ATTRIBUTES. Эти функции подробно описаны в SDK.
Параметр dwStackSize функции CreateThread позволяет указать начальный размер стека для
запускаемой задачи. Если указать для этого параметра нулевое значение, размер стека запущенной
задачи будет равен размеру стека главной задачи процесса. При необходимости размер стека
автоматически увеличивается.
Таким образом, первые два параметра функции CreateThread не вызывают затруднений. Они
могут быть в большинстве случаев указаны соответственно как NULL и 0.
Параметр IpStartAddress задает адрес функции, которая будет выполняться как отдельная задача.
Здесь вы можете просто указать имя этой функции. Функция задачи имеет один 32-разрядный
параметр и возвращает 32-разрядное значение. Указанный параметр передается функции
CreateThread через параметр IpParameter.
Если значение параметра dwCreationFlags равно нулю, после вызова функции CreateThread задача
немедленно начнет свое выполнение. Если же в этом параметре указать значение
CREATE_SUSPENDED, задача будет загружена, но приостановлена. Возобновить выполнение
приостановленной! задачи можно будет позже с помощью функции ResumeThread.
И наконец, через параметр IpThreadld вы должны передать адрес переменной типа DWORD, в
которую будет записан системный номер созданной задачи (thread identifier).
В случае успеха функция CreateThread возвращает идентификатор задачи (thread handle),
пользуясь которым можно выполнять над задачей те или иные операции. Не путайте этот
идентификатор с системным номером задачи. При ошибке функция CreateThread возвращает
значение NULL.
Ниже мы привели пример использования функции CreateThread:
hThread = CreateThread (
NULL,
0,
(LPTHREAD_START_ROUTINE) ThreadRoutine,
(LPVOID)hwndChild,
0,
(LPDWORD)SdwIDThread) ;
Здесь мы не используем атрибуты защиты и делаем размер стека запускаемой задачи равным
размеру стека главной задачи процесса.
В качестве функции задачи мы использовали функцию с именем ThreadRoutine, имеющую
следующий вид:
DWORD ThreadRoutine (HWND hwnd)
{
. . .
// Оператор return завершает выполнение задачи
return 0;
}
Эта функция имеет один параметр, который в нашем случае будет принимать значение
hwndChild.
Наша функция задачи завершает свое выполнение оператором return. Для проверки значения,
возвращенного функцией задачи, процесс может воспользоваться функцией GetExitCodeThread,
которая будет описана позже.
Так как при запуске задачи мы указали значение параметра dwCreationFlags равное нулю, сразу
после запуска задача начнет свою работу. Системный номер созданной задачи будет записан в
переменную dwIDThread.
Управление запущенными задачами
После того как задача запущена, запустившая задача знает идентификатор дочерней задачи.
30
Пользуясь этим идентификатором, запустившая задача может управлять состоянием дочерней задачи,
изменяя ее приоритет, приостанавливая, возобновляя или завершая ее работу.
Изменение приоритета задачи
Родительская задача может изменить относительныйприоритет запущенной ей дочерней задачи с
помощью функции SetThreadPriority:
BOOL SetThreadPriprity(
HANDLE hThread,
int nPriority);
// идентификатор задачи
// новый уровень
приоритета задачи
Через параметр hThread этой функции передается идентификатор задачи, для которой необходимо
изменить относительный приоритет. Новое значение относительного приоритета передается через
параметр nPriority и может принимать одно из следующих значений:
 THREAD_PRIORITY_TIME_CRITICAL;
 THREAD_PRIORITY_HIGHEST;
 THREAD_PRIORITY_ABOVE_NORMAL;
 THREAD_PRIORITY_NORMAL;
 THREAD_PRIORITY_BELOW_NORMAL;
 THREAD_PRIORITY_LOWEST;
 THREAD_PRIORITY_IDLE.
Абсолютный уровень приоритета, который получит задача, зависит от класса приоритета
процесса.
Определение приоритета задачи
Зная идентификатор задачи, нетрудно определить ее относительный приоритет. Для этого следует
воспользоваться функцией GetThreadPriority:
int GetThreadPriority(HANDLE hThread);
Эта функция возвращает одно из значений, перечисленных выше в пункте "Изменение
приоритета задачи", или значение THREAD_PRIORITY_ERROR_RETURN при возникновении
ошибки.
Приостановка и возобновление выполнения задачи
В некоторых случаях имеет смысл приостановить выполнение задачи. Например, если
пользователь работает с многооконным приложением и для каждого окна запускается отдельная
задача, для повышения производительности можно приостановить выполнение задач в неактивных
окнах.
Приостановка выполнения задачи делается с помощью функции SuspendThread:
DWORD SuspendThread(HANDLE hThread);
Через единственный параметр этой функции нужно передать идентификатор приостанавливаемой
задачи.
Для каждой задачи операционная система хранит счетчик приостановок, который увеличивается
при каждом вызове функции SuspendThread. Если значение этого счетчика больше нуля, задача
приостанавливается.
Для уменьшения значения счетчика приостановок и, соответственно, для возобновления
выполнения задачи вы должны использовать функцию ResumeThread:
DWORD ResumeThread(HANDLE hThread);
В случае ошибки функции SuspendThread и ResumeThread возвращают значение 0xFFFFFFFF.
Временная приостановка работы задачи
31
С помощью функции Sleep задача может приостановить свою работу на заданный период
времени:
VOID Sleep (DWORD cMilliseconds); // время в миллисекундах
Задача, выполняющая ожидание с помощью этой функции, не снижает производительности
системы, так как ей не распределяются кванты времени. Через единственный параметр вы можете
задать функции время ожидания в миллисекундах.
Если для времени ожидания указать нулевое значение, то при наличии в системе запущенных
задач с таким же приоритетом, как и у задачи, вызвавшей эту функцию, ожидающая задача отдает
оставшееся время от своего кванта другой задаче, В том случае, когда в системе нет других задач с
таким же значением приоритета, функция Sleep немедленно возвращает управление вызвавшей ее
задаче, которая сама будет использовать остаток своего кванта времени.
Есть еще одна возможность: можно организовать бесконечную задержку, передав функции Sleep
значение INFINITE
Завершение задачи
Задача может завершиться по собственной инициативе и по инициативе другой задачи. В первом
случае задача либо выполняет оператор возврата из функции задачи, либо пользуется специальными
функциями.
Для того чтобы завершить свое выполнение, задача, запущенная с помощью функции
CreateThread, может вызвать функцию ExitThread, передав ей код завершения:
VOID ExitThread(DWORD dwExitCode);
Для принудительного завершения дочерней задачи родительская задача может использовать
функцию TerminateThread, передав ей идентификатор завершаемой задачи и код завершения:
BOOL TerminateThread(
HANDLE hThread,
// идентификатор завершаемой задачи
DWORD dwExitCode); // код завершения
Как родительская задача может получить код завершения дочерней задачи?
должна вызвать функцию GetExitCodeThread:
BOOL
GetExitCodeThread(
HANDLE hThread,
LPDWORD
IpExitCode);
Для этого она
// идентификатор завершаемой задачи
//адрес для приема кода завершения
Если задача, для которой вызвана функция GetExitCodeThread, все еще работает, вместо кода
завершения возвращается значение STILL_ACTIVE.
Освобождение идентификатора задачи
После завершения процесса идентификаторы всех созданных им задач освобождаются. Однако
лучше, если приложение будет самостоятельно освобождать ненужные ей идентификаторы задач, так
как они являются ограниченным системным ресурсом.
Для освобождения идентификатора задачи вы должны передать его функции CloseHandle,
имеющей единственный параметр.
Еще одно замечание относительно освобождения идентификаторов задач и процессов приведено
в следующей главе, посвященной процессам.
Критические секции
Критические секции являются наиболее простым средством синхронизации задач для
обеспечения последовательного доступа к ресурсам. Они работают быстро, не снижая заметно
производительности системы, но обладают одним существенным недостатком - их можно
использовать только для синхронизации задач в рамках одного процесса.
32
Критическая секция создается как структура типа CRITICAL_SECTION:
CRITICAL_SECTION csWindowPaint;
Обычно эта структура располагается в области глобальных переменных, доступной всем
запущенным задачам процесса. Так как каждый процесс работает в своем собственном адресном
пространстве, вы не сможете передать адрес критической секции из одного процесса в другой.
Именно поэтому критические секции нельзя использовать для синхронизации задач, созданных
разными процессами.
В документации SDK отмечено, что структуру типа CRITICAL_SECTION нельзя перемещать или
копировать.
Инициализация критической секции
Перед использованием критической секции ее необходимо проинициализировать, вызвав для
этого функцию InitializeCriticalSection:
CRITICAL_SECTION csWindowPaint;
InitializeCriticalSection(&csWindowPaint);
Функция InitializeCriticalSection имеет только один
CRITICALJSECTION) и не возвращает никакого значения.
параметр (адрес структуры типа
Удаление критической секции
Если критическая секция больше не нужна, ее нужно удалить при помощи функции
DeleteCriticalSection, как это показано ниже:
DeleteCriticalSection(scsWindowPaint);
При этом освобождаются все ресурсы, созданные операционной системой для критической
секции.
Вход в критическую секцию и выход из нее
Две основные операции, выполняемые задачами над критическими секциями, - это вход в
критическую секцию и выход из критической секции.
Первая операция выполняется при помощи функции EnterCriticalSection, вторая - при помощи
функции LeaveCriticalSection. Эти функции, не возвращающие никакого значения, всегда
используются в паре, как это показано в следующем фрагменте исходного текста программы:
EnterCriticalSection(&csWindowPaint);
hdc=BeginPaint(hWnd,&ps);
GetClientRect(hWnd,&rc);
DrawText(hdc,"Text",-1,&rc,
DT_SINGLELINE|DT_CENTER|DT_VCENTER); EndPaint(hWnd,&ps);
LeaveCriticalSection(&csWindowPaint);
В качестве единственного параметра функциям EnterCriticalSection и LeaveCriticalSection
необходимо передать адрес структуры типа CRITICAL_SECTION, проинициализиро-ванной
предварительно функцией InitializeCriticalSection.
Критические секции работают следующим образом. Если одна задача вошла в критическую
секцию, но еще не вышла из нее, то при попытке других задач войти в ту же самую критическую
секцию они будут переведены в состояние ожидания. Задачи пробудут в этом состоянии до тех пор,
пока задача, которая вошла в критическую секцию, не выйдет из нее.
Таким образом, гарантируется, что фрагмент кода, заключенный между вызовами функций
EnterCriticalSection и LeaveCriticalSection, будет выполняться задачами последовательно, если все они
работают с одной и той же критической секцией.
25. Номер варианта
33
0
1
4
6
Последняя цифра зачетной книжки
2
3
4
5
6
7
Номер варианта
3
7
5
8
1
9
26. Варианты заданий
Номер
варианта
1
2
3
4
5
6
7
8
Номер
серии
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
Приоритет задач
А
Б
В
Г
Д
А
Б
В
В
Ж
Г
В
В
Г
Е
А
Б
В
Е
Е
А
Б
В
Д
Ж
Б
В
В
В
Д
В
Д
Е
Б
Ж
Б
Г
Б
Б
В
Д
Е
А
В
В
Е
Д
Б
Д
В
Д
Ж
Г
В
Г
Ж
Ж
Г
В
Д
Е
Ж
А
Б
Б
Г
Е
А
Г
Е
В
Ж
В
В
В
В
Г
Е
Е
Б
Б
Б
Е
Е
А
Б
Б
Е
Д
Д
Б
Д
Ж
Ж
Б
Д
Г
Е
Е
Д
Г
В
Е
Е
Г
Д
Ж
В
Е
Д
Б
Г
Г
Д
Е
Ж
В
Г
Б
Д
Ж
А
Г
Б
Ж
Ж
А
В
В
В
Ж
Д
В
В
Ж
Е
А
Д
Г
Е
Ж
Д
Б
Е
Д
Е
А
Д
34
Д
Д
Е
Ж
Ж
Г
Д
Д
Ж
Е
Б
Д
А
Е
Е
Б
Д
Б
Е
Е
А
Г
Б
Г
Д
В
Д
Д
Ж
Ж
Б
В
Д
Г
Д
А
Б
8
9
2
10
9
10
3
4
5
1
2
3
4
5
1
2
3
4
5
Г
Е
Д
Д
Б
В
Е
Ж
Б
Г
В
Д
Ж
В
Е
Е
А
Д
Б
Е
Е
Д
Б
В
Д
Е
В
Д
Ж
А
Д
В
Д
Ж
А
В
В
Е
Д
Д
Д
Ж
Б
В
Д
Г
Ж
А
Д
Г
Е
Е
где
Код
А
Б
В
Г
Д
Е
Ж
Приоритет
THREAD_PRIORITY_IDLE
THREAD_PRIORITY_HIGHEST
THREAD_PRIORITY_ABOVE_NORMAL
THREAD_PRIORITY_NORMAL
THREAD_PRIORITY_BELOW_NORMAL
THREAD_PRIORITY_LOWEST
THREAD_PRIORITY_TIME_CRITICAL
35
В
Д
Е
В
Г
В
Г
Е
Г
Д
Г
Е
Ж
Лабораторная работа №7
«Синхронизация задач в операционных системах
Microsoft Windows»
1. Цель занятия
Изучение способов синхронизации параллельно выполняющихся задач в операционных системах
Microsoft Windows. Доработка учебного мультизадачного приложения.
2. Литература
3. Фролов А.В., Фролов Г.В. Программирование для Windows NT. – М: ДИАЛОГ-МИФИ, 1996. –
272 с. – (Библиотека системного программиста; Т.26).
4. Фролов А.В., Фролов Г.В. Операционная система Windows 95 для программиста. – М: ДИАЛОГМИФИ, 1996. – (Библиотека системного программиста; Т.22).
5. Фролов А.В., Фролов Г.В. Графический интерфейс GDI в Microsoft Windows. – М: ДИАЛОГМИФИ, 1994. – (Библиотека системного программиста; Т.14).
6. Саймон Р. Windows 2000 API Энциклопедия. – М: ДиаСофт, 2002.- 1088 с.
7. Неббет Г. Справочник по базовым функциям API Windows NT/2000. – М: Вильямс, 2002. – 528 с.
3. Выполнение работы
 Изучить:
 способ синхронизации задач с помощью объектов – событие, Mutex, семафоров и
ожидаемых таймеров;
 способы построения MDI-приложений;
 разработать алгоритм работы учебного мультизадачного приложения;
 доработать, созданное на лабораторной работе №1 учебное приложение;
 составить отчет по проделанной работе в соответствии с требованиями, предъявляемыми в
пункте 6 настоящего пособия.
4. Контрольные вопросы
1. Для чего предназначена функция WaitForSingleObject?
2. Какие значения и при каких обстоятельствах возвращает функция WaitForSingleObject?
3. Каким образом дочерние задачи могут использовать объекты синхронизации родительской
задачи?
4. Для чего предназначен объект событие?
5. Какие виды объектов – событие Вам известны?
6. Для чего предназначен объект Mutex и каков принцип его работы?
7. Для чего предназначен семафор и чем он отличается от других объектов синхронизации?
8. Прокомментируйте работу ожидаемого таймера с ручным сбросом и автосбросом.
9. В каком состоянии находится ожидаемый таймер после создания?
10. Как определить текущее значение счетчика семафора?
11. В чем отличия объекта Mutex от критической секции?
12. Какой из объектов синхронизации целесообразнее использовать для синхронизации задач
одного приложения? Обоснуйте свой ответ.
5. Содержание работы
 Ознакомиться с кратким теоретическим материалом, ответить на контрольные вопросы;
 определить номер выполняемого варианта;
 разработать алгоритм работы учебного приложения;
 доработать и отладить программу работы мультизадачного приложения;
 требования к разрабатываемому мультизадачному приложению:

должно обеспечивать запуск и одновременную работу до семи задач;

пользователь должен иметь возможность прио-станавливать выполнение всех задач;

приоритет
каждой
задачи
должен
быть
равным
константе
THREAD_PRIORITY_NORMAL (нормальный приоритет);
36

в зависимости от варианта синхронизация процесса рисования между выполняющимися
задачами должна производиться с помощью одного из объектов синхронизации: событие, Mutex,
семафор или ожидаемый таймер;

каждая задача должна последовательно выполнять рисование следующих геометрических
объектов в окне: эллипсов, прямоугольников, а также выводить произвольный текст. Координаты
местоположения геометрических объектов и текста в окне, а также их размеры и цвет выбираются
каждый раз произвольно при помощи генератора случайных чисел;

каждая задача для всех типов геометрических объектов и текста должна вести учет
количества ранее нарисованных объектов начиная с момента запуска задачи. Приостановка
выполнения задачи пользователем не должна изменять учитываемые значения. Пользователь должен
иметь возможность обнулять учитываемые значения для всех запущенных задач;

задача, производящая рисование выводить свой идентификатор в строку состояния;

задача, выполнившая рисование в главном окне должна временно приостановить свою
работу на произвольное время не большее двух секунд, затем возобновляет свою работу
6. Содержание отчета
Отчет должен содержать следующее:
 титульный лист с указанием наименования и цели занятия; фамилии, имени, отчества и
номера группы студента; фамилии, имени, отчества преподавателя;
 дату выполнения работы;
 цель занятия;
 номер выполняемого варианта;
 условия предложенной задачи;
 код программы, реализующей мультизадачное приложение;
 выводы о проделанной работе.
7. Краткий теоретический материал
7.1. Ожидание завершения задачи или процесса
Если нужно дождаться завершения одной задачи или одного процесса, лучше всего
воспользоваться для этого функцией WaitForSingleObjectс которой вы уже знакомы из предыдущих
приложений.
Прототип функции WaitForSingleObject представлен ниже:
DWORD WaitForSingleObject
HANDLE hObject,
DWORD dwTimeout);
// идентификатор объекта
// время ожидания в миллисекундах
В качестве параметра hObject этой функции нужно передать идентификатор объекта, для
которого выполняется ожидание, а в качестве параметра dwTimeout - время ожидания в
миллисекундах (ожидание может быть и бесконечным, если для времени указать значение
INFINITE).
Многие объекты операционных систем Microsoft Windows, такие, например, как идентификаторы
задач, процессов, файлов, могут находиться в двух состояниях - отмеченном (signaled) и
неотмеченном (nonsignaled). В частности, если задача или процесс находятся в состоянии выполнения
(то есть работают), соответствующие идентификаторы находятся в неотмеченном состоянии. Когда
же задача или процесс завершают свою работу, их идентификаторы отмечаются (то есть переходят в
отмеченное состояние).
Если задача создает другую задачу или процесс, и затем вызывает функцию WaitForSingleObject,
указав ей в качестве первого параметра идентификатор созданной задачи, а в качестве второго значение INFINITE, родительская задача переходит в состояние ожидания. Она будет находиться в
состоянии ожидания до тех пор, пока дочерняя задача или процесс не завершит свою работу.
Заметим, что функция WaitForSingleObject не проверяет состояние идентификатора дочерней
задачи или процесса в цикле, дожидаясь ее (или его) завершения. Такое действие привело бы к тому,
что родительской задаче выделялись бы кванты процессорного времени, а это как раз то, чего мы
хотели бы избежать. Вместо этого функция WaitForSingleObject сообщает планировщику задач, что
37
выполнение родительской задачи, вызвавшей эту функцию, необходимо приостановить до тех пор,
пока дочерняя задача или процесс не завершит свою работу.
Принимая решение о выделении родительской задаче кванта процессорного времени,
планировщик проверяет состояние дочерней задачи. Квант времени выделяется планировщиком
родительской задаче только в том случае, если дочерняя задача завершила свою работу и ее
идентификатор находится в отмеченном состоянии. Такая проверка не отнимает много времени и,
следовательно, не приводит к заметному снижению производительности системы.
На рис. 2.1 показано, как задача с номером 1 ожидает завершение задачи с номером 2, имеющей
идентификатор hThread2.
Задача 1
hThread1
Ожидание
WaitForSingleObject(hThread2, INFINITE)
Задача 2
hThread2
Выполнение
длительной
работы
Рис. 2.1. Ожидание завершения задачи
Пунктирной стрелкой здесь показано событие, которое ведет к завершению ожидания. Этим
событием, очевидно, является завершение работы задачи hThread2.
В качестве примера использования функции WaitForSingleObject для ожидания завершения
дочернего процесса, рассмотрим фрагмент исходного текста некого приложения:
if (CreateProcess (NULL, ofn.lpstrFile, NULL, NULL,
FALSE, dwCreationFlags, NULL, NULL, &si, &pi))
{ if(WaitForSingleObject(pi.hProcess, INFINITE) !=WAIT_FAILED)
{ GetExitCodeProcess(pi.hProcess, &dwExitCode);
...
}
CloseHandle (pi.hProcess);
CloseHandle (pi.hThread);
}
Здесь главная задача с помощью функции CreateProcess запускает процесс. Идентификатор этого
процесса сохраняется в поле hProcess структуры pi. Если запуск процесса произошел успешно,
главная задача приложения приостанавливает свою работу до тех пор, пока запущенный процесс не
завершит свою работу. Для этого она вызывает функцию WaitForSingleObject, передавая ей
идентификатор запущенного процесса.
Если родительский процесс не интересуется судьбой своего дочернего процесса, функция
WaitForSingleObject не нужна. В этом случае главная задача может сразу закрыть идентификаторы
дочернего процесса и главной задачи дочернего процесса, оборвав “родительские узы”:
if(CreateProcess (NULL, ofn.lpstrFile, NULL, NULL,
FALSE, dwCreationFlags, NULL, NULL, &si, &pi))
{
CloseHandle (pi.hProcess);
CloseHandle (pi.hThread);
}
Запущенный таким образом процесс называется отсоединенным (detached). Он будет жить своей
жизнью независимо от состояния запустившего его процесса.
Теперь поговорим о коде завершения функции WaitForSingleObject.
В случае ошибки функция возвращает значение WAIT_FAILED. При этом код ошибки можно
получить при помощи функции GetLastError.
Если же функция завершилась успешно, она может вернуть одно из следующих трех значений:
WAIT_OBJECT_0, WAIT_TIMEOUT или WAIT_ABANDONED.
38
Если состояние идентификатора объекта, для которого выполнялось ожидание, стало
отмеченным, функция возвращает значение WAIT_OBJECT_0. Таким образом, когда мы ожидаем
завершение задачи и задача завершилась “естественным образом”, функция WaitForSingleObject
вернет именно это значение.
Если время ожидания, заданное во втором параметре функции WaitForSingleObject истекло, но
объект так и не перешел в отмеченное состояние, возвращается значение WAIT_TIMEOUT.
Очевидно, при бесконечном ожидании вы никогда не получите этот код завершения.
Код завершения WAIT_ABANDONED возвращается для объекта синхронизации типа Mutex (его
мы рассмотрим далее), который не был освобожден задачей, завершившей свою работу. Таким
образом, в этом случае ожидание было отменено и соответствующий объект (Mutex) не перешел в
отмеченное состояние.
7.2. Объекты – события
Объекты - события - наиболее простая разновидность объектов синхронизации. Они содержат
счетчик числа пользователей и две булевы переменные: одна сообщает тип данного объекта-события,
другая - его состояние (свободен или занят).
Объекты - события просто уведомляют об окончании какой-либо операции. Объекты-события
бывают двух типов: со сбросом вручную (manual-reset events) и с автосбросом (auto-reset events).
Первые позволяют возобновлять выполнение сразу нескольких ждущих потоков, вторые - только
одного.
Объекты-события обычно используют в том случае, когда какой-то поток выполняет
инициализацию, а затем сигнализирует другому потоку, что тот может продолжить работу.
Инициализирующий поток переводит объект - событие» в занятое состояние и приступает к своим
операциям. Закончив, он сбрасывает событие в свободное состояние. Тогда другой поток, который
ждал перехода события в свободное состояние, пробуждается.
Создание объекта - событие
Для создания объекта - событие вы должны использовать функцию CreateEvent, прототип которой
приводится ниже:
HANDLE CreateEvent(
LPSECURITY_ATTRIBUTES
lpSecurityAttributes
BOOL fManualReset,
BOOL fInitialState,
LPCTSTR IpName);
// атрибуты защиты
// тип объекта –
событие
// начальное состояние
// имя объекта событие
В качестве первого параметра (атрибуты защиты) вы можете указать значение NULL.
Параметр fManualReset сообщает системе, хотите Вы создать объект - событие со сбросом
вручную (TRUE) или с автосбросом (FALSE).
Параметр fInitialState определяет начальное состояние события: свободное (TRUE) или занятое
(FALSE).
После того как система создает объект событие, CreateEvent возвращает идентификатор события,
специфичный для конкретного процесса.
Через параметр IpName вы должны передать указатель на имя объекта – событие. Это имя не
должно содержать символ "\" и его длина не должна превышать значение МАХ_РАТН.
Задачи из других процессов могут получить доступ к этому объекту следующими способами:
1. вызовом функции CreateEvent с тем же параметром lpName;
2. наследованием описателя;
3. применением функции DuplicateHandle;
4. вызовом функции OpenEvent c передачей в параметре pszName имени, совпадающего с
указанным в аналогичном параметре функции CreateEvent.
Открытие объекта - событие
39
Зная имя объекта - событие, задача может его открыть с помощью функции OpenEvent, прототип
которой приведен ниже:
HANDLE OpenEvent(
DWORD fdwAccess,
BOOL fInherit,
LPCTSTR IpName );
// требуемый доступ
// флаг наследования
// адрес имени объекта –
событие
Флаги доступа, передаваемые через параметр fdwAccess, определяют требуемый уровень доступа
к объекту - событие. Этот параметр может быть комбинацией следующих значений:
EVENT_ALL_ACCESS
EVENT_MODIFY_STATE
SYNCHRONIZE
Приложение получает полный
доступ к объекту
Приложение может изменять
состояние объекта функциями
SetEvent и ResetEvent
Только для Windows NT – приложение может использовать объект
только в функциях ожидания
Параметр fInherit определяет возможность наследования полученного идентификатора. Если этот
параметр равен TRUE, идентификатор может наследоваться дочерними процессами. Если же он
равен FALSE, наследование не допускается.
Через параметр lpName вы должны передать функции адрес символьной строки, содержащей имя
объекта - событие.
Управление состоянием объекта - событие
Для перевода объекта - событие в свободное состояние необходимо использовать функцию
ResetEvent:
BOOL ResetEvent(HANDLE hEvent);
Для перевода объекта - событие в занятое состояние необходимо использовать функцию SetEvent:
BOOL SetEvent(HANDLE hEvenеt);
Объекты – событие с автосбросом
Для объектов - событий с автосбросом действует следующее правило: когда его ожидание
потоком успешно завершается, этот объект автоматически сбрасывается в занятое состояние. Отсюда
и произошло название таких объектов - событий Для такого объекта не требуется вызывать функцию
ResetEvent, поскольку система сама восстанавливает его состояние А для событий со сбросом
вручную никаких побочных эффектов после успешного ожидания не предусмотрено.
7.3. Объекты Mutex
Если необходимо обеспечить последовательное использование ресурсов задачами, созданными в
рамках разных процессов, вместо критических, секций необходимо использовать объекты
синхронизации Mutex. Свое название они получили от выражения "mutually exclusive", что означает;
"взаимно исключающий". Однако допускается использовать объект Mutex для обеспечения
последовательного использования ресурсов задачами, созданными в рамках одного процесса.
Объект Mutex может находиться в отмеченном или неотмеченном состоянии. Когда какая-либо
задача, принадлежащая любому процессу, становится владельцем объекта Mutex, последний
переключается в неотмеченное состояние. Если же задача "отказывается" от владения объектом
Mutex, его состояние становится отмеченным.
Организация последовательного доступа к ресурсам с использованием объектов Mutex возможна
потому, что в каждый момент только одна задача, может владеть этим объектом. Все остальные
40
задачи для того, чтобы завладеть объектом, который уже захвачен, должны ждать, например, с
помощью уже функции WaitForSingleObject.
Для того чтобы объект Mutex был доступен задачам, принадлежащим различным процессам, при
создании вы должны присвоить ему имя. Данное имя будет глобальным для всех процессов.
Создание объекта Mutex
Для создания объекта Mutex вы должны использовать функцию CreateMutex, прототип которой
мы привели ниже:
HANDLE CreateMutex(
LPSECURITY_ATTRIBUTES
lpSecurityAttributes
BOOL bInitialOwner
LPCTSTR IpName);
// атрибуты защиты
// начальное состояние
// имя объекта Mutex
В качестве первого параметра (атрибуты защиты) вы можете указать значение NULL.
Параметр bInitialOwner определяет начальное состояние объекта Mutex. Если он имеет значение
TRUE, задача, создающая объект Mutex, будет им владеть сразу после создания. Если же значение
этого параметра равно FALSE, после создания объект Mutex не будет принадлежать ни одной задаче,
пока не будет захвачен ими явным образом.
Через параметр IpName вы должны передать указатель на имя объекта Mutex. Это имя не должно
содержать символ "\" и его длина не должна превышать значение МАХ_РАТН.
Если объект Mutex будет использован только задачами одного процесса, вместо адреса имени
можно указать значение NULL. В этом случае будет создан "безымянный" объект Mutex.
Функция CreateMutex возвращает идентификатор созданного объекта Mutex или NULL при
ошибке.
Возможно возникновение такой ситуации, когда приложение пытается создать объект Mutex с
именем, которое уже используется в системе другим объектом Mutex. В этом случае функция
CreateMutex вернет идентификатор существующего объекта Mutex, а функция GetLastError,
вызванная сразу после вызова функции CreateMutex, вернет значение ERROR_ALREADY_EXISTS.
Заметим, что функция создания объектов-событий CreateEvent ведет себя в данной ситуации
аналогичным образом.
Освобождение идентификатора объекта Mutex
Если объект Mutex больше не нужен, вы должны освободить его идентификатор при помощи
универсальной функции CloseHandle. Заметим тем не менее, что при завершении процесса
освобождаются идентификаторы всех объектов Mutex, созданных для него.
Открытие объекта Mutex
Зная имя объекта Mutex, задача может его открыть с помощью функции OpenMutex, прототип
которой приведен ниже:
HANDLE OpenMutex(
DWORD fdwAccess,
BOOL fInherit,
LPCTSTR IpszMutexName );
// требуемый доступ
// флаг наследования
// адрес имени объекта
Mutex
Флаги доступа, передаваемые через параметр fdwAccess, определяют требуемый уровень доступа
к объекту - событие. Этот параметр может быть комбинацией следующих значений:
MUTEX_ALL_ACCESS
SYNCHRONIZE
Приложение получает полный
доступ к объекту
Только для Windows NT –
приложение может использовать
объект только в функциях
ожидания и функции ReleaseMutex
С помощью функции OpenMutex несколько задач могут открыть один и тот же объект Mutex и
41
затем выполнять одновременное ожидание для этого объекта.
Как завладеть объектом Mutex
Зная идентификатор объекта Mutex, полученный от функций CreateMutex или OpenMutex, задача
может завладеть объектом при помощи функций ожидания событий, например при помощи функции
WaitForSingleObject.
Напомним, что функция WaitForSingleObject возвращает управление, как только идентификатор
объекта, передаваемый ей в качестве параметра, перейдет в отмеченное состояние. Если объект
Mutex не принадлежит ни одной задаче, его состояние будет отмеченным.
Когда вы вызываете функцию WaitForSingleObject для объекта Mutex, который никому не
принадлежит, она сразу возвращает управление. При этом задача, вызвавшая функцию
WaitForSingleObject, становится владельцем объекта Mutex. Если теперь другая задача вызовет
функцию WaitForSingleObject для этого же объекта Mutex, то она будет переведена в состояние
ожидания до тех пор, пока первая задача не "откажется от своих прав" на данный объект Mutex.
Освобождение объекта Mutex выполняется функцией ReleaseMutex.
Захват объекта Mutex во владение по своему значению аналогичен входу в критическую секцию.
Освобождение объекта Mutex
Для отказа от владения объектом Mutex (то есть для его освобождения) вы должны использовать
функцию ReleaseMutex:
BOOL ReleaseMutex(HANDLE hMutex);
Через единственный параметр этой функции необходимо передать идентификатор объекта Mutex.
Функция возвращает значение TRUE при успешном завершении и FALSE при ошибке.
Проводя аналогию с критическими секциями, заметим, что освобождение объекта Mutex
соответствует выходу из критической секции.
7.4 Семафоры
В отличие от объектов Mutex, которые используются для организации последовательного доступа
задач к ресурсу, семафоры позволяют обеспечить доступ к ресурсу для заранее определенного
ограниченного приложением количества задач. Все остальные задачи, пытающиеся получить доступ
сверх установленного лимита, будут переведены при этом в состояние ожидания до тех пор, пока
какая - либо задача, получившая доступ к ресурсу раньше, не освободит ресурс, связанный с данным
семафором.
Примером области применения семафоров может послужить программное обеспечение какоголибо аппаратного устройства, с которым может работать только ограниченное количество задач. Все
остальные задачи, пытающиеся получить доступ к этому устройству, должны быть переведены в
состояние ожидания и пребывать в нем до тех пор, пока не завершит свою работу одна из задач, уже
получившая доступ к устройству.
Ресурс, доступ к которому управляется семафором, может быть устройством не только
физическим, но и чисто логическим.
Как работает семафор
В отличие от железнодорожного семафора, который может быть либо открыт, разрешая
движение, либо закрыт, запрещая его, семафоры в операционных системах Microsoft Windows
действуют более сложным образом.
Так же как и объект Mutex, семафор может находиться в отмеченном или неотмеченном
состоянии. Приложение выполняет ожидание для семафора при помощи таких функции, как
WaitForSingleObject (точно так же, как и для объекта Mutex). Если семафор находится в
неотмеченном состоянии, задача, вызвавшая для него функцию WaitForSingleObject, находится в
состоянии ожидания. Когда же состояние семафора становится отмеченным, работа задачи
возобновляется.
В отличие от объекта Mutex с каждым семафором связывается счетчик, начальное и
максимальное значения которого задаются при создании семафора. Значение этого счетчика
уменьшается, когда задача вызывает для семафора функции WaitForSingleObject и увеличивается при
вызове другой, специально предназначенной для этого функции.
42
Если значение счетчика семафора равно нулю, он находится в неотмеченном состоянии. Если же
это значение больше нуля, семафор переходит в отмеченное состояние. Пусть, например, приложение
создало семафор, указав для него максимальное значение счетчика равное трем. Пусть начальное
значение этого счетчика также будет равно трем.
Если в этой ситуации несколько запускаемых по очереди задач будут выполнять с помощью
функции WaitForSingleObject ожидание семафора, то первые 3 запущенные задачи будут работать, а
все остальные перейдут в состояние ожидания. Это связано с тем, что первые 3 вызова функции
WaitForSingleObject приведут к последовательному уменьшению значения счетчика семафора до
нуля, в результате чего семафор переключится в неотмеченное состояние.
Задача, запущенная четвертой, вызовет функцию WaitForSingleObject для неотмеченного
семафора, в результате чего она будет ждать. Точно так же задачи, запущенные после запуска
четвертой задачи, будут выполнять ожидание для того же семафора.
Как долго продлится ожидание? До тех пор, пока одна из первых трех задач не освободит
семафор, увеличив его счетчик на единицу вызовом специальной функции. Сразу после этого будет
запущена одна из задач, ожидающих наш семафор.
На рис. 2.2 мы показали последовательное изменение счетчика семафора (обозначенного
символом N) при запуске первых трех задач. Так как счетчик больше нуля, семафор открыт, то есть
находится в отмеченном состоянии, и поэтому функция WaitForSingleObject не будет выполнять
ожидание.
N=3
N=2
N=1
Рис. 2.2. Изменение значения счетчика семафора от трех до единицы
После запуска четвертой задачи, выполняющей ожидание семафора, значение счетчика
уменьшится до нуля. При этом семафор будет закрыт, то есть перейдет в неотмеченное состояние
(рис. 2.3).
N=0
Рис. 2.3. После запуска четвертой задачи семафор закрывается
Функции для работы с семафорами
Рассмотрим функции программного интерфейса операционных систем Microsoft Windows,
предназначенные для работы с семафорами.
Создание семафора
Для создания семафора приложение должно вызвать функцию CreateSemaphore, прототип
которой приведен ниже:
43
HANDLE CreateSemaphore(
LPSECURITY_ATTRIBUTES
IpSemaphoreAttributes,
LONG lInitialCount,
LONG lMaximumCount,
LPCTSTR IpName);
// атрибуты защиты
// начальное значение
// счетчика семафора
// максимальное значение
// счетчика семафора
// адрес строки с именем
// семафора
В качестве атрибутов защиты вы можете передать значение NULL.
Через параметры lInitialCount и lMaximumCount передается соответственно начальное и
максимальное значение счетчика, связанного с создаваемым семафором. Начальное значение
счетчика lInitialCount должно быть больше или равно нулю и не должно превосходить максимальное
значение счетчика, передаваемое через параметр lMaximumCount.
Имя семафора указывается аналогично имени рассмотренного нами ранее объекта Mutex с
помощью параметра IpName.
В случае удачного создания семафора функция CreateSemaphore возвращает его идентификатор.
В случае возникновения ошибки возвращается значение NULL, при этом код ошибки можно узнать
при помощи функции GetLastError.
Так как имена семафоров доступны всем приложениям в системе, возможно возникновение
ситуации, когда приложение пытается создать семафор с уже использованным именем. При этом
новый семафор не создается, а приложение получает идентификатор для уже существующего
семафора. Если возникла такая ситуация, функция GetLastError, вызванная сразу после функции
CreateSemaphore, возвращает значение ERROR_ALREADY_EXISTS.
Уничтожение семафора •
Для уничтожения семафора вы должны передать его идентификатор функции CloseHandle;
Заметим, что при завершении процесса все созданные им семафоры уничтожаются автоматически.
Открытие семафора
Если семафор используется только для синхронизации задач, созданных в рамках одного
приложения, вы можете создать безымянный семафор, указав в качестве параметра IpName функции
CreateSemaphore значение NULL. В том случае, когда необходимо синхронизировать задачи разных
процессов, следует определить имя семафора. При этом один процесс создает семафор с помощью
функции CreateSemaphore, а второй открывает его, получая идентификатор для уже существующего
семафора.
Существующий семафор можно открыть функцией OpenSemaphore, прототип которой приведен
ниже:
HANDLE OpenSemaphore(
DWORD
fdwAccess,
// требуемый доступ
BOOL
fInherit,
// флаг наследования
LPCTSTR IpazSemaphoreName);
// адрес имени
семафора
Флаги доступа, передаваемые через параметр fdwAccess, определяют требуемый уровень доступа
к семафору. Этот параметр может быть комбинацией следующих значений:
Значение
SEMAPHORE_ALL_ACCESS
SEMAPHORE_MODIFY_STA
TE
SYNCHRONIZE
Описание
Указаны все возможные флаги
доступа
Возможно изменение значения
счетчика семафора функцией
ReleaseSemaphore
Полученный идентифи-катор
можно будет использовать в
любых функциях ожидания
события
44
Параметр fInherit определяет возможность наследования полученного идентификатора; Если этот
параметр равен TRUE, идентификатор может наследоваться дочерними процессами. Если же он
равен FALSE, наследование не допускается.
Через параметр IpszSemaphoreName вы должны передать функции адрес символьной строки,
содержащей имя семафора.
Если семафор открыт успешно, функция OpenSemaphore возвращает его идентификатор. При
ошибке возвращается значение NULL. Код ошибки вы можете определить при помощи функции
GetLastError.
Увеличение значения счетчика семафора
Для увеличения значения счетчика семафора приложение должно Использовать функцию
ReleaseSemaphore:
BOOL ReleaseSemaphore(
HANDLE hSemaphore,
LONG
cReleaseCount,
LPLONG IplPreviousCount);
// идентификатор семафора
// значение инкремента
// адрес переменной для записи
// предыдущего значения счетчика
семафора
Функция ReleaseSemaphore увеличивает значение счетчика семафора, идентификатор которого
передается ей через параметр hSemaphore, на значение, указанное в параметре cReleaseCount.
Заметим, что через параметр cReleaseCount вы можете передавать только положительное
значение не равные нулю. При этом если в результате увеличения новое значение счетчика должно
будет превысить максимальное значение, заданное при образовании семафора, функция
ReleaseSemaphore возвращает признак ошибки и не изменяет значения счетчика.
Предыдущее значение счетчика, которое было до использования функции ReleaseSemaphore,
записывается в переменную типа LONG. Адрес этой переменной передается функции через параметр
lplPreviousCount,
Если функция ReleaseSemaphore завершилась успешно, она возвращает значение TRUE. При
ошибке возвращается значение FALSE. Код ошибки в этом случае можно определить, как обычно,
при помощи функции GetLastError.
Функция используется обычно для решения двух задач.
Во-первых, с помощью этой функции задачи освобождают ресурс, доступ к которому
регулируется семафором. Они могут делать это после использования ресурса или перед своим
завершением.
Во-вторых, эта функция может быть использована на этапе инициализации мультизадачного
приложения. Создавая семафор с начальным значением счетчика равным нулю, главная задача
блокирует работу задач, выполняющих ожидание этого семафора. После завершения инициализации
главная задача с помощью функции ReleaseSemaphore может увеличить значение счетчика семафора
до максимального, в результате чего известное количество ожидающих задач будет активизировано.
Уменьшение значения счетчика семафора
В программном интерфейсе операционных систем Microsoft Windows нет функции, специально
предназначенной для уменьшения значения счетчика семафора. Счетчик уменьшается, когда задача
вызывает функцию ожидания, такую, как WaitForSingleObject. Если задача вызывает несколько раз
функцию ожидания для одного и того же семафора, содержимое его счетчика каждый раз будет
уменьшаться.
Определение текущего значения счетчика семафора
Единственная возможность определения текущего значения счетчика семафора заключается в
увеличении этого значения функцией ReleaseSemaphore. Значение счетчика, которое было до
увеличения, будет записано в переменную, адрес которой передается функции ReleaseSemaphore
через параметр IplPreviousCount.
Заметим, что в операционных системах Microsoft Windows не предусмотрено средств, с помощью
45
которых можно было бы определить текущее значение семафора, не изменяя его. В частности, вы не
можете задать функции ReleaseSemaphore нулевое значение инкремента, так как в этом случае
функция просто вернет соответствующий код ошибки.
7.5 Ожидаемые таймеры
Ожидаемые таймеры (waitable timers) - это объекты синхронизации, которые самостоятельно
переходят в свободное состояние в определенное время или через регулярные промежутки времени.
Ожидаемый таймер отсутствует в Windows 95 и для его использования необходимы: Windows 98,
Windows NT 4.0 и выше.
Создание и открытие ожидаемого таймера
Чтобы создать ожидаемый таймер, необходимо вызвать функцию CreateWaitableTimer:
HANDLE CreateWaitableTimer(
LPSECURITY_ATTRIBUTES
lpSecurityAttributes
BOOL fManualReset,
LPCTSTR IpName);
// атрибуты защиты
// тип ожидаемого таймера
// имя ожидаемого таймера
В качестве атрибутов защиты вы можете передать значение NULL.
По аналогии с объектами - событиями параметр fManualReset определяет тип ожидаемого
таймера: со сбросом вручную или с автосбросом. Когда освобождается таймер со сбросом вручную,
возобновляется выполнение всех потоков, ожидавших этот объект, а когда в свободное состояние
переходит таймер с автосбросом - лишь одного из потоков.
Через параметр IpName вы должны передать указатель на имя объекта – событие. Это имя не
должно содержать символ "\" и его длина не должна превышать значение МАХ_РАТН.
Для открытия ранее созданного ожидаемого таймера необходимо использовать функцию
OpenWaitableTimer:
HANDLE OpenWaitableTimer(
DWORD fdwAccess,
BOOL fInherit,
LPCTSTR IpName );
// требуемый доступ
// флаг наследования
// адрес имени ожидаемого
таймера
Флаги доступа, передаваемые через параметр fdwAccess, определяют требуемый уровень доступа
к ожидаемому таймеру и могут принимать следующие значения:
TIMER_ALL_ACCESS
TIMER_MODIFY_
STATE
SYNCHRONIZE
Разрешает полный доступ к объекту
Разрешает изменять состояние
таймера функциями SetWaitableTimer
и CancelWaitableTimer
Только Windows NT – разрешает
использовать таймер в функциях
ожидания
Параметр fInherit определяет возможность наследования полученного идентификатора. Если этот
параметр равен TRUE, идентификатор может наследоваться дочерними процессами. Если же он
равен FALSE, наследование не допускается.
Через параметр lpName вы должны передать функции адрес символьной строки, содержащей имя
ожидаемого таймера.
Функции для работы с ожидаемым таймером
Объекты «ожидаемый таймер» всегда создаются в занятом состоянии. Чтобы сообщить таймеру, в
какой момент он должен перейти в свободное состояние, вызовите функцию SetWaitableTimer:
46
BOOL SetWaitableTimer(
HANDLE hTimer,
Const LARGE_INTEGER
lpDueTime,
LONG lPeriod,
PTIMERAPCROUTINE
pfnCompletionRoutine,
PVOID
lpArgToCotnpletionRoutine,
BOOI fResume);
// идентификатор ожидаемого
таймера
// время срабатывания
// период повторения срабатывания
// процедура-обработчик
// параметр процедурыобработчика
// задает, будет ли операцион-ная
система
// «пробуждаться» из suspended
режима
Параметр lpDueTime задает время срабатывания таймера. Время задается в формате FILETIME и
базируется на coordinated universal time (UTC), т.е. должно указываться по Гринвичу. Для
преобразования системного времени в FILETIME используется функция SystemTimeToFileTime. Если
время имеет положительный знак, оно трактуется как абсолютное, если отрицательный – как
относительное от момента запуска таймера.
Параметр lPeriod задает срок между повторными срабатываниями таймера. Если lPeriod равен 0 –
таймер сработает один раз.
Параметр pfnCompletionRoutine задает адрес функции, объявленной как:
VOID APIENTRY TimerAPCRoutine(
PVOID pvArgToCompleUonRoutine,
DWORD dwTimerLowValue,
DWORD dwTimerHighValue)
Эта функция вызывается, когда срабатывает таймер, если поток, ожидающий его срабатывания,
использует функцию ожидания, поддерживающую асинхронный вызов процедур. В функцию
передаются 3 параметра:
lpArgToCompletionRoutine – значение, переданное в качестве одноименного параметра в функцию
SetWaitableTimer. Приложение может использовать его для передачи в процедуру обработки адреса
блока данных, необходимых для её работы
dwTimerLowValue и dwTimerHighValue – соответственно члены dwLowDateTime и
dwHighDateTime структуры FILETIME. Они описывают время срабатывания таймера. Время задается
в UTC формате (по Гринвичу).
Если дополнительная функция обработки не нужна, в качестве этого параметра можно передать
NULL.
Параметр lpArgToCompletionRoutine передается в функцию pfnCompletionRoutine при её вызове.
Параметр fResume определяет необходимость “пробуждения” системы, если на момент
срабатывания таймера она находится в режиме экономии электроэнергии (suspended). Если
операционная система не поддерживает пробуждение и fResume равно TRUE, функция
SetWaitableTimer выполнится успешно, однако последующий вызов GetLastError вернет результат
ERROR_NOT_SUPPORTED.
Для перевода таймера в неактивное состояние, необходимо использовать функцию
CancelWaitableTimer:
BOOL CancelWaitableTimer(HANDLE hTimer);
Данная функция использует идентификатор таймера и отменяет его (таймер), после чего тот уже
никогда не сработает, - если только вы не переустановите его повторным вызовом SetWaitableTimer.
Если Вам понадобится перенастроить таймер, то вызывать CancelWattableTimer перед повторным
обращением к SetWaitableTimer не требуется; так как каждый вызов SetWaitableTimer автоматически
отменяет предыдущие настройки перед установкой новых.
8. Номер варианта
47
0
1
6
2
Последняя цифра зачетной книжки
2
3
4
5
6
7
Номер варианта
4
5
10
8
1
7
9. Варианты заданий
Номер
варианта
1
2
3
4
5
6
7
8
9
10
Задание для выполнения
Синхронизация задач одного MDI-приложения с
помощью безымянного объекта Mutex
Синхронизация
задач
нескольких
MDIприложений с помощью ожидаемого таймера с
автосбросом,
который
срабатывает
через
промежутки времени равные 1,5 секундам
Синхронизация задач одного MDI-приложения с
помощью безымянного объекта Semaphore, со
значением счетчика равным 4
Синхронизация задач одного SDI-приложения с
помощью ожидаемого таймера с ручным сбросом,
который
срабатывает
через
произвольные
промежутки времени не превышающие 2 секунд
Синхронизация задач нескольких SDI-приложений
с помощью объекта - события с ручным сбросом
Синхронизация задач нескольких SDI-приложений
с помощью объекта Mutex
Синхронизация
задач
нескольких
SDIприложений с помощью ожидаемого таймера с
ручным сбросом, который срабатывает через
равные промежутки времени, равные 2 секундам.
Синхронизация задач нескольких SDI-приложений
с помощью объекта-события с автосбросом
Синхронизация
задач
нескольких
MDIприложений с помощью объекта Semaphore с
возможностью
задания
значения
счетчика
Semaphore
Синхронизация задач одного MDI-приложения с
помощью ожидаемого таймера с автосбросом,
который
срабатывает
через
произвольные
интервалы времени не превышающие 3 секунд
48
8
9
3
9
Лабораторная работа №8
«Передача данных между процессами в операционных системах Microsoft Windows»
1. Цель занятия
Изучение способов передачи данных между процессами в операционных системах Microsoft
Windows.
2. Литература
1.Фролов А.В., Фролов Г.В. Программирование для Windows NT. – М: ДИАЛОГ-МИФИ, 1996. – 272
с. – (Библиотека системного программиста; Т.26).
2.Фролов А.В., Фролов Г.В. Операционная система Windows 95 для программиста. – М: ДИАЛОГМИФИ, 1996. – (Библиотека системного программиста; Т.22).
3.Фролов А.В., Фролов Г.В. Графический интерфейс GDI в Microsoft Windows. – М: ДИАЛОГМИФИ, 1994. – (Библиотека системного программиста; Т.14).
4.Саймон Р. Windows 2000 API Энциклопедия. – М: ДиаСофт, 2002.- 1088 с.
5.Неббет Г. Справочник по базовым функциям API Windows NT/2000. – М: Вильямс, 2002. – 528 с.






3. Выполнение работы
Изучить универсальные функции Windows API: CreateFile, WriteFile, ReadFile;
изучить способы передачи информации между процессами в операционных системах Microsoft
Windows:
 обмен через файлы, отображаемые на память;
 обмен с помощью передачи сообщений;
 канал передачи данных Pipe;
 канал передачи данных MailSlot.
разработать алгоритм работы учебного приложения;
программно реализовать учебное приложение;
отладить работу, разработанного приложения;
составить отчет по проделанной работе в соответствии с требованиями, предъявляемыми в
пункте 6 настоящего пособия.
4. Контрольные вопросы
1. Какие способы передачи данных между процессами в операционных системах Microsoft
Windows Вы знаете?
2. Поясните принцип работы механизма отображения файлов на память? Где используется
данный механизм в операционной системе?
3. Почему в процессе отображения адресного пространства больших размеров не приводит к
переполнению виртуальной памяти?
4. В каких операционных системах можно использовать канал передачи данных Pipe?
5. Поясните принцип передачи информации с помощью каналов Pipes.
6. Какие способы передачи данных через канал Pipe Вам известны?
7. Поясните принцип передачи информации с помощью каналов MailSlot.
8. Какие универсальные функции применяются для работы с каналами передачи данных?
9. Каким образом осуществляется передача сообщений между процессами?
10. Какой способ передачи данных между процессами является самым быстрым? Обоснуйте свой
ответ.
11. Какой способ передачи данных между процессами позволяет осуществлять
широковещательную передачу данных в рамках домена?
12. Какие способы передачи данных между процессами позволяет осуществлять передачу данных
между процессами, запущенными на разных компьютерах?
13. Почему использование рассмотренных способов является более предпочтительным при
разработке системного программного обеспечения по сравнению с технологиями DDE
(динамического обмена данными) и OLE?
5. Содержание работы
 Ознакомиться с кратким теоретическим материалом, ответить на контрольные вопросы;
49




определить номер выполняемого варианта;
разработать алгоритм работы учебного приложения;
разработать и отладить программу работы учебного приложения;
разрабатываемое учебное приложение должно обеспечивать:
 ввод текстовой информации с клавиатуры;
 осуществлять передачу введенной информации другому приложению (копии данного
приложения), используя способ передачи данных, указанный в Вашем варианте;
 осуществлять прием информации от другого приложения (копии данного приложения),
используя способ передачи данных, указанный в Вашем варианте;
 отображать принятую информацию;
6. Содержание отчета
Отчет должен содержать следующее:
 титульный лист с указанием наименования и цели занятия; фамилии, имени, отчества и
номера группы студента; фамилии, имени, отчества преподавателя;
 дату выполнения работы;
 цель занятия;
 номер выполняемого варианта;
 условия предложенной задачи;
 код программы, реализующей учебное приложение;
 выводы о проделанной работе.
7. Теоретический материал
7.1. Универсальные функции для работы с файлами в операционных системах Microsoft
Windows
Прежде всего, рассмотрим универсальные функции: CreateFile, WriteFile, ReadFile и CloseHandle.
Область использования этих функция широка: данные функции позволяют работать с файлами,
каналами передачи данных, дисковыми устройствами, консолями и др. Данные функции будут
использоваться нами в каждом варианте.
Функция CreateFile
Функция CreateFile предназначена не только для создания файлов. С помощью функции CreateFile
можно выполнять не только создание нового файла, но и открывание существующего файла или
каталога, а также изменение длины существующего файла. Кроме того, эта функция может
выполнять операции не только над файлами, но и над каналами передачи данных pipe и mailslot,
дисковыми устройствами и консолями.
Прототип функции CreateFile мы привели ниже:
HANDLE CreateFile (
LPCTSTR lpFileName,
DWORD dwDesiredAccess,
DWORD dwShareMode,
LPSECURITY_ATTRIBUTES
lpSecurityAttributes,
DWORD
dwCreationDistribution,
DWORD
dwFlagsAndAttributes,
HANDLE hTemplateFile);
// адрес строки имени файла
// режим доступа
// режим совместного
использования файла
// дескриптор защиты
// параметры создания
// атрибуты файла
//
идентификатор
атрибутами
файла
с
Через параметр lpFileName вы должны передать этой функции адрес строки, содержащей имя
50
файла, который вы собираетесь создать или открыть. Строка должна быть закрыта двоичным нулем.
Параметр dwDesiredAccess определяет тип доступа, который должен быть предоставлен к
открываемому файлу. Здесь вы можете использовать логическую комбинацию следующих констант:
Константа
0
GENERIC_READ
GENERIC_WRITE
Описание
Доступ запрещен, однако приложение может
определять атрибуты файла или устройства,
открываемого при помощи функции CreateFile
Разрешен доступ на чтение
Разрешен доступ на запись
С помощью параметра dwShareMode задаются режимы совместного использования открываемого
или создаваемого файла. Для этого параметра вы можете указать комбинацию следующих констант:
Константа
0
FILE_SHARE_READ
FILE_SHARE_WRITE
Описание
Совместное использование файла
запрещено
Другие приложения могут открывать файл с
помощью функции CreateFile для чтения
Аналогично предыдущему, но на запись
Через параметр lpSecurityAttributes необходимо передать указатель на дескриптор защиты или
значение NULL, если этот дескриптор не используется. В наших приложениях мы не работаем с
дескриптором защиты.
Параметр dwCreationDistribution определяет действия, выполняемые функцией CreateFile, если
приложение пытается создать файл, который уже существует. Для этого параметра вы можете указать
одну из следующих констант:
Константа
CREATE_NEW
CREATE_ALWAYS
OPEN_EXISTING
OPEN_ALWAYS
TRUNCATE_EXISTING
Описание
Если создаваемый файл уже существует,
функция CreateFile возвращает код
ошибки
Существующий файл перезаписывается,
при этом содержимое старого файла
теряется
Открывается существующий файл. Если
файл с указанным именем не существует,
функция CreateFile возвращает код
ошибки
Если указанный файл существует, он
открывается. Если файл не существует, он
будет создан
Если файл существует, он открывается,
после чего длина файла устанавливается
равной нулю. Содержимое старого файла
теряется. Если же файл не существует,
функция CreateFile возвращает код
ошибки
Параметр dwFlagsAndAttributes задает атрибуты и флаги для файла.
При этом можно использовать любые логические комбинации следующих атрибутов (кроме
атрибута FILE_ATTRIBUTE_NORMAL, который можно использовать только отдельно):
Атрибут
FILE_ATTRIBUTE_ARCHIVE
Описание
Файл был архивирован
(выгружен)
51
FILE_ATTRIBUTE_COMPRESSED
FILE_ATTRIBUTE_NORMAL
FILE_ATTRIBUTE_HIDDEN
FILE_ATTRIBUTE_READONLY
FILE_ATTRIBUTE_SYSTEM
Файл, имеющий этот атрибут,
динамически сжимается при
записи и восстанавливается
при чтении. Если этот атрибут
имеет каталог, то для всех
расположенных в нем файлов
и каталогов также выполняется динамическое сжатие
данных
Остальные перечисленные в
этом списка атрибуты не
установлены
Скрытый файл
Файл можно только читать
Файл является частью
операционной системы
В дополнение к перечисленным выше атрибутам, через параметр dwFlagsAndAttributes вы можете
передать любую логическую комбинацию флагов, перечисленных ниже:
Флаг
FILE_FLAG_WRITE_THROUGH
FILE_FLAG_NO_BUFFERING
FILE_FLAG_OVERLAPPED
FILE_FLAG_RANDOM_ACCESS
FILE_FLAG_SEQUENTIAL_SCAN
FILE_FLAG_DELETE_ON_CLOSE
FILE_FLAG_BACKUP_SEMANTIC
S
FILE_FLAG_POSIX_SEMANTICS
Описание
Отмена промежуточного кэширования данных для уменьшения
вероятности потери данных при
аварии
Отмена промежуточной буферизации
или кэширования. При использовании этого флага необходимо
выполнять чтение и запись
порциями, кратными размеру сектора
(обычно 512 байт)
Выполнение чтения и записи
асинхронно. Во время асинхронного
чтения или записи приложение
может продолжать обработку данных
Указывает, что к файлу будет
выполняться произвольный доступ.
Флаг предназначен для оптимизации
кэширования
Указывает, что к файлу будет
выполняться последовательный
доступ от начала файла к его концу.
Флаг предназначен для оптимизации
кэширования
Файл будет удален сразу после того
как приложение закроет его идентификатор. Этот флаг удобно
использовать для временных файлов
Файл будет использован для выполнения операции выгрузки или восстановления. При этом выполняется
проверка прав доступа
Доступ к файлу будет выполняться в
соответствии со спецификацией
POSIX
52
И, наконец, последний параметр hTemplateFile предназначен для доступа к файлу шаблона с
расширенными атрибутами для создаваемого файла. Этот параметр рассматривать не будем для
экономии места. При необходимости вы найдете всю информацию по этому вопросу в документации,
поставляемой вместе с SDK.
В случае успешного завершения функция CreateFile возвращает идентификатор созданного или
открытого файла (или каталога). При ошибке возвращается значение INVALID_HANDLE_VALUE (а
не NULL, как можно было бы предположить). Код ошибки можно определить при помощи функции
GetLastError.
В том случае, если файл уже существует и были указаны константы CREATE_ALWAYS или
OPEN_ALWAYS, функция CreateFile не возвращает код ошибки. В то же время в этой ситуации
функция GetLastError возвращает значение ERROR_ALREADY_EXISTS.
Функция CloseHandle
Функция CloseHandle позволяет закрыть файл. Она имеет единственный параметр идентификатор закрываемого файла. Заметим, что если мы указали функции CreateFile флаг
FILE_FLAG_DELETE_ON_CLOSE, сразу после закрывания файл будет удален. Как мы уже
говорили, такая методика очень удобна при работе со временными файлами.
Функции ReadFile и WriteFile
С помощью функций ReadFile и WriteFile приложение может выполнять, соответственно, чтение
из файла и запись в файл. Приведем прототипы функций ReadFile и WriteFile:
BOOL ReadFile (
HANDLE hFile,
LPVOID lpBuffer,
DWORD nNumberOfBytesToRead,
LPDWORD lpNumberOfBytesRead,
LPOVERLAPPED lpOverlapped);
BOOL WriteFile (
HANDLE hFile,
LPVOID lpBuffer,
DWORD nNumberOfBytesToWrite,
LPDWORD lpNumberOfBytesWrite,
LPOVERLAPPED lpOverlapped);
// идентификатор файла
// адрес буфера для данных
// количество байт, которые
// необходимо прочесть в буфер
// адрес слова, в которое будет записано
// количество прочитанных байт
// адрес структуры типа OVERLAPPED
// идентификатор файла
// адрес записываемого блока данных
// количество байт, которые
// необходимо записать
// адрес слова, в котором будет сохранено
// количество записанных байт
// адрес структуры типа OVERLAPPED
Через параметр hFile этим функциям необходимо передать идентификатор файла, полученный от
функции CreateFile.
Параметр lpBuffer должен содержать адрес буфера, в котором будут сохранены прочитанные
данные (для функции ReadFile), или из которого будет выполняться запись данных (для функции
WriteFile).
Параметр nNumberOfBytesToRead используется для функции ReadFile и задает количество байт
данных, которые должны быть прочитаны в буфер lpBuffer. Аналогично, параметр
nNumberOfBytesToWrite задает функции WriteFile размер блока данных, имеющего адрес lpBuffer,
который должен быть записан в файл.
Так как в процессе чтения возможно возникновение ошибки или достижение конца файла,
количество прочитанных или записанный байт может отличаться от значений, заданных,
соответственно, параметрами nNumberOfBytesToRead и nNumberOfBytesToWrite. Функции ReadFile и
WriteFile записывают количество действительно прочитанных или записанных байт в двойное слово
с адресом, соответственно, lpNumberOfBytesRead и lpNumberOfBytesWrite.
Параметр lpOverlapped используется в функциях ReadFile и WriteFile для организации
аснхронного режима чтения и записи. Если запись выполняется синхронно, в качестве этого
параметра следует указать значение NULL.
Если функции ReadFile и WriteFile были выполнены успешно, они возвращают значение TRUE.
53
При возникновении ошибки возвращается значение FALSE. В последнем случае вы можете получить
код ошибки, вызвав функцию GetLastError.
В процессе чтения может быть достигнут конец файла. При этом количество действительно
прочитанных байт (записывается по адресу lpNumberOfBytesRead) будет равно нулю. В случае
достижения конца файла при чтении ошибка не возникает, поэтому функция ReadFile вернет
значение TRUE.
7.2. Обмен через файлы, отображаемые на память
Перед рассмотрением данного способа ознакомимся, с механизмом, осуществляющим
отображение файлов на память, и рассмотрим соответствующие функции.
Механизм отображения файлов на память
В операционные системы Microsoft Windows встроен эффективный механизм виртуальной
памяти. При использовании этого механизма приложениям доступно больше виртуальной
оперативной памяти, чем объем физической оперативной памяти, установленной в компьютере.
Виртуальная память реализована с использованием обычной оперативной памяти и дисковой
памяти. Когда приложение обращается к странице виртуальной памяти, отсутствующей в физической
памяти, операционная система автоматически читает ее из файла виртуальной памяти в физическую
память и предоставляет приложению. Если же приложение изменяет содержимое страницы памяти в
физической оперативной памяти, операционная система сохраняет такую страницу в файле
виртуальной памяти.
Механизм работы с файлами, отображаемыми на память, напоминает механизм работы
виртуальной памяти.
В операционных системах Microsoft Windows каждому процессу выделяется 2 Гбайта адресного
пространства. Любой фрагмент этого пространства может быть отображен на фрагмент файла
соответствующего размера.
На рис. 3.1 показано отображение фрагмента адресного пространства приложения, размером в 1
Гбайт, на фрагмент файла, имеющего размер 5 Гбайт.
Адресное пространство
приложения
Файл
5 Гбайт
2 Гбайт
1 Гбайт
1 Гбайт
0
Отображение
0
Рис. 3.1. Отображение фрагмента адресного пространства приложения на файл
С помощью соответствующей функции программного интерфейса, которая рассматривается
далее, приложение Microsoft Windows может выбрать любой фрагмент большого файла для
отображения в адресное пространство. Поэтому, несмотря на ограничение адресного пространства
величиной 2 Гбайт, вы можете отображать (по частям) в это пространство файлы любой длины,
возможной в Microsoft Windows NT. В простейшем случае при работе с относительно небольшими
файлами вы можете выбрать в адресном пространстве фрагмент подходящего размера и отобразить
его на начало файла.
Если установлено отображение фрагмента адресного пространства на фрагмент файла, то
операционная система обеспечивает тождественность содержимого отображаемого фрагмента памяти
54
и фрагмента файла, выполняя при необходимости операции чтения и записи в файл (с буферизацией
и кешированием).
В процессе отображения адресного пространства память не выделяется, а только резервируется.
Поэтому отображение фрагмента размером 1 Гбайт не вызовет переполнение файлов виртуальной
памяти. Более того, при отображении файлы виртуальной памяти вообще не используются, так как
страницы фрагмента связываются с отображаемым файлом.
Если приложение обращается в отображенный фрагмент для чтения, возникает исключение.
Обработчик этого исключения загружает в физическую оперативную память соответствующую
страницу из отображенного файла, а затем возобновляет выполнение прерванной команды. В
результате в физическую оперативную память загружаются только те страницы, которые нужны
приложению.
При записи происходит аналогичный процесс. Если нужной страницы нет в памяти, она
подгружается из отображенного файла, затем в нее выполняется запись. Загруженная страница
остается в памяти до тех пор, пока не будет вытеснена другой страницей при нехватке физической
оперативной памяти. Что же касается записи измененной страницы в файл, то эта запись будет
выполнена при закрытии файла, по явному запросу приложения или при выгрузке страницы из
физической памяти для загрузки в нее другой страницы.
Создание отображения файла
Рассмотрим процедуру создания отображения файла на память. Прежде всего, приложение
должно открыть файл при помощи функции CreateFile, которая рассмотрена в пункте
«Универсальная функция CreateFile».
Через параметр lpFileName вы, должны передать этой функции адрес текстовой строки,
содержащей путь к открываемому файлу.
С помощью параметра dwDesiredAccess следует указать нужный вам вид доступа. Если файл
будет открыт только для чтения, в этом параметре необходимо указать флаг GENERIC_READ. Если
вы собираетесь выполнять над файлом операции чтения и записи, следует указать логическую
комбинацию флагов GENERIC_READ и GENERIC_WRITE. В том случае, когда будет указан только
флаг GENERIC_WRITE, операция чтения из файла будет запрещена.
Не забудьте также про параметр dwShareMode. Если файл будет использоваться одновременно
несколькими процессами, через этот параметр необходимо передать режимы совместного
использования файла: FILE_SHARE_READ или FILE_SHARE_WRITE.
Остальные параметры этой функции смотрите в пункте «Универсальная функция CreateFile».
В случае успешного завершения, функция CreateFile возвращает идентификатор открытого файла.
При ошибке возвращается значение INVALID_HANDLE_VALUE. Здесь все как обычно, пока
никакого отображения еще не выполняется.
Для того чтобы создать отображение файла, вы должны вызвать функцию CreateFileMapping,
прототип которой приведен ниже:
HANDLE CreateFileMapping (
HANDLE hFile,
LPSECURITY_ATTRIBUTES
lpFileMappingAttributes,
DWORD flProtect,
DWORD dwMaximumSizeHigh,
DWORD dwMaximumSizeLow,
LPCTSTR lpName);
// идентификатор
отображаемого файла
// дескриптор защиты
// защита для
отображаемого файла
// размер файла (старшее
слово)
// размер файла (младшее
слово)
// имя отображенного
файла
Через параметр hFile этой функции нужно передать идентификатор файла, для которого будет
выполняться отображение в память, или значение 0xFFFFFFFF. В первом случае функция
CreateFileMapping отобразит заданный файл в память, а во втором - создаст отображение с
использованием файла виртуальной памяти. Как мы увидим позже, отображение с использованием
55
файла виртуальной памяти удобно для организации передачи данных между процессами.
Обратим ваше внимание на одну потенциальную опасность, связанную с использованием в паре
функций CreateFile и CreateFileMapping. Если функция CreateFile завершится с ошибкой и эта ошибка
не будет обработана приложением, функция CreateFileMapping получит через параметр hFile
значение INVALID_HANDLE_VALUE, численно равное 0xFFFFFFFF. В этом случае она сделает
совсем не то, что предполагал разработчик приложения: вместо того чтобы выполнить отображение
файла в память, функция создаст отображение с использованием файла виртуальной памяти.
Параметр lpFileMappingAttributes задает адрес дескриптора защиты. В большинстве случаев для
этого параметра вы можете указать значение NULL.
Теперь займемся параметром flProtect, задающим защиту для создаваемого отображения файла.
Для этого параметра вы можете задать следующий набор значений, комбинируя их с
дополнительными атрибутами, которые будут перечислены ниже:
Значение
Описание
PAGE_READONLY
К выделенной области памяти
предоставляется доступ только для
чтения. При создании или открывании
файла необходимо указать флаг
GENERIC_READ
PAGE_READWRITE К выделенной области памяти
предоставляется доступ для чтения и
записи. При создании или открывании
файла необходимо указать флаги
GENERIC_READ и GENERIC_WRITE
PAGE_WRITECOPY К выделенной области памяти
предоставляется доступ для
копирования при записи. При создании
или открывании файла необходимо
указать флаги GENERIC_READ и
GENERIC_WRITE. Режим
копирования при записи будет описан
позже в главе, посвященной обмену
данными между процессами
Эти значения можно комбинировать при помощи логической операции ИЛИ со следующими
атрибутами:
Атрибут
Описание
SEC_COMMIT
Если указан этот атрибут, выполняется
выделение физических страниц в памяти
или в файле виртуальной памяти. Этот
атрибут используется по умолчанию
SEC_IMAGE
Используется при отображении
программного файла, содержащего
исполнимый код. Этот атрибут
несовместим с остальными
перечисленными в этом списке атрибутами
SEC_NOCACHE
Отмена кэширования для всех страниц
отображаемой области памяти. Должен
использоваться вместе с атрибутами
SEC_RESERVE или SEC_COMMIT
SEC_RESERVE
Если указан этот атрибут, вместо
выделения выполняется резервирование
страниц виртуальной памяти.
Зарезервированные таким образом
страницы можно будет получить в
пользование при помощи функции
VirtualAlloc. Атрибут SEC_RESERVE
можно указывать только в том случае, если
в качестве параметра hFile функции
56
CreateFileMapping передается значение
0xFFFFFFFF
С помощью параметров dwMaximumSizeHigh и dwMaximumSizeLow необходимо указать
функции CreateFileMapping 64-разрядный размер файла. Параметр dwMaximumSizeHigh должен
содержать старшее 32-разрядное слово размера, а параметр dwMaximumSizeLow - малдшее 32разрядное слово размера. Для небольших файлов, длина которых укладывается в 32 разряда, нужно
указывать нулевое значение параметра dwMaximumSizeHigh.
Заметим, что вы можете указать нулевые значения и для параметра dwMaximumSizeHigh, и для
параметра dwMaximumSizeLow. В этом случае предполагается, что размер файла изменяться не
будет.
Через параметр lpName можно указать имя отображения, которое будет доступно всем
работающим одновременно приложениям. Имя должно представлять собой текстовую строку,
закрытую двоичным нулем и не содержащую символов “\”.
Если отображение будет использоваться только одним процессом, вы можете не задавать для него
имя. В этом случае значение параметра lpName следует указать как NULL.
В случае успешного завершения функция CreateFileMapping возвращает идентификатор
созданного отображения. При ошибке возвращается значение NULL.
Так как имя отображения глобально, возможно возникновение ситуации, когда процесс пытается
создать отображение с уже существующим именем. В этом случае функция CreateFileMapping
возвращает идентификатор существующего отображения. Такую ситуацию можно определить с
помощью функции GetLastError, вызвав ее сразу после функции CreateFileMapping. Функция
GetLastError при этом вернет значение ERROR_ALREADY_EXISTS.
Выполнение отображения файла в память
Итак, мы выполнили первые два шага, необходимые для работы с файлом, отображаемым на
память, - открывание файла функцией CreateFile и создание отображения функцией
CreateFileMapping. Теперь, получив от функции CreateFileMapping идентификатор объектаотображения, мы должны выполнить само отображение, вызвав для этого функцию MapViewOfFile
или MapViewOfFileEx. В результате заданный фрагмент отображенного файла будет доступен в
адресном пространстве процесса.
Прототип функции MapViewOfFile приведен ниже:
LPVOID MapViewOfFile (
HANDLE hFileMappingObject, // идентификатор отображения
DWORD dwDesiredAccess,
// режим доступа
DWORD dwFileOffsetHigh,
// смещение в файле (старшее
слово)
DWORD dwFileOffsetLow,
// смещение в файле (младшее
слово)
DWORD
// количество отображаемых байт
dwNumberOfBytesToMap);
Функция MapViewOfFile создает окно размером dwNumberOfBytesToMap байт, которое смещено
относительно начала файла на количество байт, заданное параметрами dwFileOffsetHigh и
dwFileOffsetLow. Если задать значение параметра dwNumberOfBytesToMap равное нулю, будет
выполнено отображение всего файла.
Смещение нужно задавать таким образом, чтобы оно попадало на границу минимального
пространства памяти, которое можно зарезервировать. Значение 64 Кбайта подходит в большинстве
случаев.
Более точно гранулярность памяти можно определить при помощи функции GetSystemInfo. Этой
функции в качестве единственного параметра необходимо передать указатель на структуру типа
SYSTEM_INFO, определенную следующим образом:
typedef struct _SYSTEM_INFO
{
union {
57
DWORD dwOemId; // зарезервировано
struct
{
WORD wProcessorArchitecture; // архитектура системы
WORD wReserved; // зарезервировано
};
};
DWORD dwPageSize;
// размер страниц
LPVOID lpMinimumApplicationAddress; // минимальный адрес,
// доступный приложениям и библиотекам DLL
LPVOID lpMaximumApplicationAddress; // максимальный адрес,
// доступный приложениям и библиотекам DLL
DWORD dwActiveProcessorMask; // маски процессоров
DWORD dwNumberOfProcessors; // количество процессоров
DWORD dwProcessorType;
// тип процессора
DWORD dwAllocationGranularity; // гранулярность памяти
WORD wProcessorLevel;
// уровень процессора
WORD wProcessorRevision; // модификация процессора
} SYSTEM_INFO;
Функция заполнит поля этой структуры различной информацией о системе. В частности, в поле
dwAllocationGranularity будет записан минимальный размер резервируемой области памяти.
Вернемся к описанию функции MapViewOfFile.
Параметр dwDesiredAccess определяет требуемый режим доступа к отображению, то есть режимы
доступа для страниц виртуальной памяти, используемых для отображения. Для этого параметра вы
можете указать одно из следующих значений:
Значение
FILE_MAP_WRITE
FILE_MAP_READ
FILE_MAP_ALL_ACCESS
FILE_MAP_COPY
Описание
Доступ на запись и чтение. При
создании отображения функции
CreateFileMapping необходимо
указать тип защиты
PAGE_READWRITE
Доступ только на чтение. При
создании отображения
необходимо указать тип защиты
PAGE_READWRITE или
PAGE_READ
Аналогично FILE_MAP_WRITE
Доступ для копирования при
записи. При создании
отображения необходимо указать
атрибут PAGE_WRITECOPY
В случае успешного выполнения отображения функция MapViewOfFile возвращает адрес
отображенной области памяти. При ошибке возвращается значение NULL.
При необходимости приложение может запросить отображение в заранее выделенную область
адресного пространства. Для этого следует воспользоваться функцией MapViewOfFileEx:
LPVOID MapViewOfFileEx (
HANDLE
hFileMappingObject,
DWORD dwDesiredAccess,
DWORD dwFileOffsetHigh,
DWORD dwFileOffsetLow,
DWORD
// идентификатор отображения
// режим доступа
// смещение в файле (старшее слово)
// смещение в файле (младшее слово)
// количество отображаемых байт
58
dwNumberOfBytesToMap
LPVOID lpBaseAddress);
//
предполагаемый
отображения
// файла
адрес
для
Эта функция аналогична только что рассмотренной функции MapViewOfFile за исключением
того, что она имеет еще один параметр lpBaseAddress - предполагаемый адрес для выполнения
отображения.
Выполнение отображения с использованием функции MapViewOfFileEx используется в тех
случаях, когда с помощью файла, отображаемого на память, организуется общая область памяти,
доступная нескольким работающим параллельно процессам. При этом вы можете сделать так, что
начальный адрес этой области будет одним и тем же для любого процесса, работающего с данным
отображением.
Заметим, что функция MapViewOfFileEx сама выполняет резервирование адресов, поэтому вы не
должны передавать ей адрес области памяти, полученный от функции VirtualAlloc. Еще одно
ограничение заключается в том, что адрес, указанный через параметр lpBaseAddress, должен
находиться на границе гранулярности памяти.
Приложение может создавать несколько отображений для разных или одинаковых фрагментов
одного и того же файла.
Открытие отображения
Если несколько процессов используют совместно одно и то же отображение, первый процесс
создает это отображение с помощью функции CreateFileMapping, указав имя отображения, а
остальные должны открыть его, вызвав функцию OpenFileMapping:
HANDLE OpenFileMapping (
DWORD dwDesiredAccess,
BOOL bInheritHandle,
LPCTSTR lpName);
// режим доступа
// флаг наследования
// адрес имени отображения файла
Через параметр lpName этой функции следует передать имя открываемого отображения. Имя
должно быть задано точно также, как при создании отображения функцией CreateFileMapping.
Параметр dwDesiredAccess определяет требуемый режим доступа к отображению и указывается
точно также, как и для описанной выше функции MapViewOfFile.
Параметр bInheritHandle определяет возможность наследования идентификатора отображения.
Если он равен TRUE, порожденные процессы могут наследовать идентификатор, если FALSE - то
нет.
Отмена отображения файла
Если созданное отображение больше не нужно, его следует отменить с помощью функции
UnmapViewOfFile:
BOOL UnmapViewOfFile (LPVOID lpBaseAddress);
Через единственный параметр этой функции необходимо передать адрес области отображения,
полученный от функций MapViewOfFile или MapViewOfFileEx.
В случае успеха функция возвращает значение TRUE. При этом гарантируется, что все
измененные страницы оперативной памяти, расположенные в отменяемой области отображения,
будут записаны на диск в отображаемый файл. При ошибке функция возвращает значение FALSE.
Если приложение создало несколько отображений для файла, перед завершением работы с
файлом все они должны быть отменены с помощью функции UnmapViewOfFile. Далее с помощью
функции CloseHandle следует закрыть идентификаторы отображения, полученный от функции
CreateFileMapping и CreateFile.
Принудительная запись измененных данных
Как мы только что сказали, после отмены отображения все измененные страницы памяти
записываются в отображаемый файл. Если это потребуется, приложение может в любое время
59
выполнить принудительную
FlushViewOfFile:
BOOL FlushViewOfFile (
LPCVOID lpBaseAddr,
DWORD
dwNumberOfBytesToFlush);
запись
измененных
страниц в файл при помощи функции
// начальный адрес сохраняемой
области
// размер области в байтах
С помощью параметров lpBaseAddr и dwNumberOfBytesToFlush вы можете выбрать любой
фрагмент внутри области отображения, для которого будет выполняться сохранение измененный
страниц на диске. Если задать значение параметра dwNumberOfBytesToFlush равным нулю, будут
сохранены все измененные страницы, принадлежащие области отображения.
Обмен через файлы, отображаемые на память
Рассмотрев все функции Microsoft Windows для отображения файлов на память, приступим к
изучению способа передачи информации между процессами, на основе файлов, отображаемых на
память.
Данный способ обладает высоким быстродействием, так как данные передаются между
процессами непосредственно через виртуальную память.
Методика работы с файлами, отображаемыми на память, была описана выше. Эта методика
может быть использована без изменений для организации передачи данных между процессами,
однако мы все же сделаем некоторые замечания.
Вот фрагмент кода, в котором создается отображение файла, а затем выполняется отображение
этого файла в память:
hFileMapping=CreateFileMapping(hSrcFile,NULL,PAGE_READWRITE, 0,wFileSize,NULL);
if (hFileMapping == NULL) return;
lpFileMap = MapViewOfFile (hFileMapping, FILE_MAP_WRITE, 0, 0, 0);
if (lpFileMap == 0) return;
Здесь в качестве первого параметра для функции CreateFileMapping мы передаем идентификатор
файла, открытого функцией CreateFile. Последний параметр указан как NULL, поэтому отображение
не имеет имени.
Если отображение будет использоваться для передачи данных между процессами, удобно указать
для него имя. Пользуясь этим именем, другие процессы смогут открыть отображение функцией
OpenFileMapping.
Другое замечание касается идентификатора файла, передаваемого функции CreateFileMapping
через первый параметр. Если вы создаете отображение только для того чтобы обеспечить передачу
данных между процессами, вам не нужно создавать файл на диске компьютера. Указав в качестве
идентификатора файла значение (HANDLE) 0xFFFFFFFF, вы создадите отображение
непосредственно в виртуальной памяти без использования дополнительного файла.
Ниже мы привели фрагмент кода, в котором создается отображение с именем
$SpecialFileShareName$, причем это отображение создается в виртуальной памяти:
CHAR lpFileShareName[] = "$SpecialFileShareName$";
hFileMapping = CreateFileMapping((HANDLE)0xFFFFFFFF,NULL,
PAGE_READWRITE, 0, 100, lpFileShareName);
После того как вы создали объект-отображение, следует выполнить отображение файла в память
при помощи функции MapViewOfFile, как это было показано выше. В случае успеха эта функция
вернет указатель на отображенную область памяти.
Итак, первый процесс создал отображение. Второй процесс, который будет выполнять обмен
данными с первым процессом, должен открыть это отображение по имени при помощи функции
OpenFileMapping, например, так:
60
hFileMapping = OpenFileMapping (FILE_MAP_READ | FILE_MAP_WRITE, FALSE, lpFileShareName);
Далее второе приложение выполняет отображение, вызывая функцию MapViewOfFile:
lpFileMap = MapViewOfFile(hFileMapping,FILE_MAP_READ | FILE_MAP_WRITE, 0, 0, 0);
Пользуясь значением, полученным от функции MapViewOfFile, второе приложение получает
указатель на отображенную область памяти. Физически эта область находится в тех же страницах
виртуальной памяти, что и область, созданная первым процессом. Таким образом, два процесса
получили указатели на общие страницы памяти.
Перед завершением своей работы процессы должны отменить отображение файла и освободить
идентификатор созданного объекта-отображения:
UnmapViewOfFile (lpFileMap);
CloseHandle (hFileMapping);
Пример приложения, использующего файлы, отображаемые на память
В данном приложении используется еще один способ синхронизации приложений – с помощью
событий. Мы не будем останавливаться на подробном рассмотрении этого способа. В своем
приложении Вы должны использовать этот способ, по аналогии с рассматриваемым примером.
Сначала рассмотрим серверную часть приложения.
Сначала объявим переменные, которые будут использоваться в программе, и присвоим им
необходимее значения.
// Идентификаторы объектов-событий, которые используются
// для синхронизации задач, принадлежащих разным процессам
HANDLE hEventChar;
HANDLE hEventTermination;
HANDLE hEvents[2];
// Имя объекта-события для синхронизации ввода и отображения
CHAR lpEventName[] = "$MyVerySpecialEventName$";
// Имя объекта-события для завершения процесса
CHAR lpEventTerminationName[] = "$MyVerySpecialEventTerminationName$";
// Имя отображния файла на память
CHAR lpFileShareName[] = "$MyVerySpecialFileShareName$";
// Идентификатор отображения файла на память
HANDLE hFileMapping;
// Указатель на отображенную область памяти
LPVOID lpFileMap;
Создаем объект событие для синхронизации:
// Создаем объект-событие для синхронизации ввода и отображения, выполняемого в
// разных процессах
EventChar = CreateEvent(NULL, FALSE, FALSE, lpEventName);
// Если произошла ошибка, получаем и отображаем ее код, а затем завершаем
// работу приложения
if(hEventChar == NULL)
{ fprintf(stdout,"CreateEvent: Error %ld\n", GetLastError ());
getch();
return 1;
}
Аналогично создаем событие для определения момента завершения работы процесса ввода:
hEventTermination = CreateEvent(NULL, FALSE, FALSE, lpEventTerminationName);
if(hEventTermination == NULL)
{fprintf(stdout,"CreateEvent (Termination): Error %ld\n", GetLastError ());
getch();
61
return 1;
}
Создаем объект-отображение:
hFileMapping = CreateFileMapping ((HANDLE)0xFFFFFFFF, NULL,
PAGE_READWRITE, 0, 100, lpFileShareName);
// Если создать не удалось, выводим код ошибки
if(hFileMapping == NULL)
{fprintf(stdout,"CreateFileMapping: Error %ld\n",
GetLastError ());
getch();
return 1;
}
Выполняем отображение файла на память в переменную lpFileMap будет записан указатель на
отображаемую область памяти:
lpFileMap = MapViewOfFile (hFileMapping, FILE_MAP_READ | FILE_MAP_WRITE, 0, 0, 0);
// Если выполнить отображение не удалось, выводим код ошибки
if(lpFileMap == 0)
{fprintf(stdout,"MapViewOfFile: Error %ld\n",
GetLastError ());
getch();
return 1;
}
Готовим массив идентификаторов событий для функции WaitForMultipleObjects:
hEvents[0] = hEventTermination;
hEvents[1] = hEventChar;
Цикл отображения. Этот цикл завершает свою работу при завершении процесса ввода:
while(TRUE)
{ // Выполняем ожидание одного из двух событий:
// - завершение клиентского процесса;
// - завершение ввода символа
dwRetCode = WaitForMultipleObjects (2, hEvents, FALSE, INFINITE);
Если ожидание любого из двух событий было отменено, если произошло первое событие
(завершение клиентского процесса) или если произошла ошибка, прерываем цикл:
if(dwRetCode == WAIT_ABANDONED_0 ||
dwRetCode == WAIT_ABANDONED_0 + 1 ||
dwRetCode == WAIT_OBJECT_0 ||
dwRetCode == WAIT_FAILED) break;
Читаем символ из первого байта отображенной области памяти, записанный туда клиентским
процессом, и отображаем его в консольном окне:
putch (*((LPSTR)lpFileMap));
}
Закрываем идентификаторы объектов-событий
CloseHandle (hEventChar);
CloseHandle (hEventTermination);
Отменяем отображение файла:
UnmapViewOfFile (lpFileMap);
62
Освобождаем идентификатор созданного объекта-отображения:
CloseHandle (hFileMapping);
Рассмотрим работу клиентской части. Сначала объявим
использоваться в программе, и присвоим им необходимее значения:
переменные,
которые
будут
// Идентификаторы объектов-событий, которые используются
// для синхронизации задач, принадлежащих разным процессам
HANDLE hEvent;
HANDLE hEventTermination;
// Имя объекта-события для синхронизации ввода и отображения
CHAR lpEventName[] = "$MyVerySpecialEventName$";
// Имя объекта-события для завершения процесса
CHAR lpEventTerminationName[] = "$MyVerySpecialEventTerminationName$";
// Имя отображния файла на память
CHAR lpFileShareName[] = "$MyVerySpecialFileShareName$";
// Идентификатор отображения файла на память
HANDLE hFileMapping;
// Указатель на отображенную область памяти
LPVOID lpFileMap;
Открываем объект-событие для синхронизации ввода и отображения:
hEvent = OpenEvent(EVENT_ALL_ACCESS, FALS, lpEventName);
if(hEvent == NULL)
{ fprintf(stdout,"OpenEvent: Error %ld\n", GetLastError ());
getch();
return 0;
}
Открываем объект-событие для сигнализации о завершении процесса ввода:
hEventTermination = OpenEvent(EVENT_ALL_ACCESS, FALSE, lpEventTerminationName);
if(hEventTermination == NULL)
{ fprintf(stdout,"OpenEvent (Termination): Error %ld\n", GetLastError ());
getch();
return 0;
}
Открываем объект-отображение:
hFileMapping = OpenFileMapping (FILE_MAP_READ | FILE_MAP_WRITE, FALSE, lpFileShareName);
// Если открыть не удалось, выводим код ошибки
if(hFileMapping == NULL)
{ fprintf(stdout,"OpenFileMapping: Error %ld\n", GetLastError ());
getch();
return 0;
}
Выполняем отображение файла на память. В переменную lpFileMap будет записан указатель на
отображаемую область памяти:
lpFileMap = MapViewOfFile (hFileMapping, FILE_MAP_READ | FILE_MAP_WRITE, 0, 0, 0);
// Если выполнить отображение не удалось, выводим код ошибки
if(lpFileMap == 0)
{ fprintf(stdout,"MapViewOfFile: Error %ld\n", GetLastError ());
getch();
return 0;
}
Цикл ввода. Этот цикл завершает свою работу, когда пользователь нажимает клавишу <ESC>,
63
имеющую код 27:
while(TRUE)
{ // Проверяем код введенной клавиши
chr = getche();
// Если нажали клавишу <ESC>, прерываем цикл
if(chr == 27)
break;
// Записываем символ в отображенную память, доступную серверному процессу
*((LPSTR)lpFileMap) = chr;
// Устанавливаем объект-событие в отмеченное состояние
SetEvent(hEvent);
}
После завершения цикла переключаем оба события в отмеченное состояние для отмены
ожидания в процессе отображения и для завершения этого процесса:
SetEvent(hEvent);
SetEvent(hEventTermination);
Закрываем идентификаторы объектов-событий:
CloseHandle (hEvent);
CloseHandle (hEventTermination);
Отменяем отображение файла:
UnmapViewOfFile (lpFileMap);
Освобождаем идентификатор созданного объекта-отображения:
CloseHandle (hFileMapping);
7.3. Каналы передачи данных Pipes
В среде операционной системы Microsoft Windows NT вам доступно такое удобное средство
передачи данных между параллельно работающими процессами, как каналы типа Pipe. Это средство
позволяет организовать передачу данных между локальными процессами, а также между процессами,
запущенными на различных рабочих станциях в сети.
Каналы типа Pipe больше всего похожи на файлы, поэтому они достаточно просты в
использовании.
Через канал можно передавать данные только между двумя процессами. Один из процессов
создает канал, другой открывает его. После этого оба процесса могут передавать данные через канал
в одну или обе стороны, используя для этого хорошо знакомые вам функции, предназначенные для
работы с файлами, такие как ReadFile и WriteFile. Заметим, что приложения могут выполнять над
каналами Pipe синхронные или асинхронные операции, аналогично тому, как это можно делать с
файлами. В случае использования асинхронных операций необходимо отдельно побеспокоиться об
организации синхронизации.
Именованные и анонимные каналы
Существуют две разновидности каналов Pipe - именованные (Named Pipes) и анонимные
(Anonymous Pipes).
Как видно из названия, именованным каналам при создании присваивается имя, которое доступно
для других процессов. Зная имя какой-либо рабочей станции в сети, процесс может получить доступ
к каналу, созданному на этой рабочей станции.
Анонимные каналы обычно используются для организации передачи данных между
родительскими и дочерними процессами, запущенными на одной рабочей станции или на “отдельно
стоящем” компьютере. В дальнейшем мы будем использовать именованные каналы.
Имена каналов
Имена каналов в общем случае имеют следующий вид:
\\ИмяСервера\pipe\ИмяКанала
Если процесс открывает канал, созданный на другой рабочей станции, он должен указать имя
сервера. Если же процесс создает канал или открывает канал на своей рабочей станции, вместо имени
указывается символ точки: \\.\pipe\ИмяКанала
64
В любом случае процесс может создать канал только на той рабочей станции, где он запущен,
поэтому при создании канала имя сервера никогда не указывается.
Реализации каналов
В простейшем случае один серверный процесс создает один канал (точнее говоря, одну
реализацию канала) для работы с одним клиентским процессом.
Однако часто требуется организовать взаимодействие одного серверного процесса с несколькими
клиентскими. Например, сервер базы данных может принимать от клиентов запросы и рассылать
ответы на них.
В случае такой необходимости серверный процесс может создать несколько реализаций канала,
по одной реализации для каждого клиентского процесса.
Создание канала
Для создания именованных каналов Pipes используется функция CreateNamedPipe, прототип
которой приводится ниже:
HANDLE CreateNamedPipe(
LPCTSTR lpName,
DWORD dwOpenMode,
DWORD dwPipeMode
DWORD nMaxInstances,
// адрес строки имени канала
// режим открытия канала
// режим работы канала
// максимальное количество
реализаций канала
DWORD nOutBufferSize, // размер выходного буфера в
байтах
DWORD nInBufferSize,
// размер входного буфера в
байтах
DWORD
// время ожидания в
nDefaultTimeOut,
миллисекундах
LPSECURITY_ATTRIBUT // адрес переменной для
ES
атрибутов защиты
lpSecurityAttributes);
Через параметр lpName передается адрес строки имени канала в форме \\.\pipe\ИмяКанала
(напомним, что при создании канала имя сервера не указывается, так как канал можно создать только
на той рабочей станции, где запущен процесс, создающий канал).
Параметр dwOpenMode задает режим, в котором открывается канал. Остановимся на этом
параметре подробнее.
Канал Pipe может быть ориентирован либо на передачу потока байт, либо на передачу сообщений.
В первом случае данные через канал передаются по байтам, во втором - отдельными блоками
заданной длины.
Режим работы канала (ориентированный на передачу байт или сообщений) задается,
соответственно, константами PIPE_TYPE_BYTE или PIPE_TYPE_MESSAGE, которые указываются в
параметре dwOpenMode. По умолчанию используется режим PIPE_TYPE_BYTE.
Помимо способа передачи данных через канал, с помощью параметра dwOpenMode можно
указать, будет ли данный канал использован только для чтения данных, только для записи или
одновременно для чтения и записи. Способ использования канала задается указанием одной из
следующих констант:
Константа
Использование канала
PIPE_ACCESS_INBOUND
Только для чтения
PIPE_ACCESS_OUTBOUND
Только для записи
PIPE_ACCESS_DUPLEX
Для чтения и записи
Перечисленные выше параметры должны быть одинаковы для всех реализаций канала (о
реализациях канала мы говорили выше). Далее мы перечислим параметры, которые могут отличаться
для разных реализаций канала:
Константа
Использование канала
PIPE_READMODE_BYTE
Канал открывается на
чтение в режиме последовательной передачи
отдельных байт
65
PIPE_READMODE_MESSAGE
PIPE_WAIT
PIPE_NOWAIT
FILE_FLAG_OVERLAPPED
FILE_FLAG_WRITE_THRO
UGH
Канал открывается на
чтение в режиме передачи
отдельных сообщений
указанной длины
Канал будет работать в
блокирующем режиме,
когда процесс переводится
в состояние ожидания до
завершения операций в
канале
Неблокирующий режим
работы канала. Если
операция не может быть
выполнена немедленно, в
неблокирующем режиме
функция завершается с
ошибкой
Использование асинхронных операций (ввод и
вывод с перекрытием).
Данный режим позволяет
процессу выполнять
полезную работу параллельно с проведением
операций в канале
В этом режиме функции,
работающие с каналом, не
возвращают управление до
тех пор, пока не будет
полностью завершена
операция на удаленном
компьютере. Используется
только с каналом,
ориентированном на
передачу отдельных байт и
только в том случае, когда
канал создан между
процессами, запущенными
на различных станциях сети
Дополнительно к перечисленным выше флагам, через параметр dwOpenMode можно передавать
следующие флаги защиты:
Флаг
WRITE_DAC
WRITE_OWNER
ACCESS_SYSTEM_SECURITY
Описание
Вызывающий процесс
должен иметь права доступа на запись к произвольному управляющему
списку доступа именованного канала access control
list (ACL)
Вызывающий процесс
должен иметь права
доступа на запись к процессу, владеющему именованным каналом Pipe
Вызывающий процесс
66
должен иметь права доступа на запись к управляющему списку доступа
именованного канала access
control list (ACL)
Подробное описание этих флагов выходит за рамки нашей книги. При необходимости обратитесь
к документации, входящей в состав SDK.
Теперь перейдем к параметру dwPipeMode, определяющему режим работы канала. В этом
параметре вы можете указать перечисленные выше константы:
PIPE_TYPE_BYTE,
PIPE_TYPE_MESSAGE,
PIPE_READMODE_BYTE,
PIPE_READMODE_MESSAGE,
PIPE_WAIT и PIPE_NOWAIT.
Для всех реализаций канала необходимо указывать один и тот же набор констант.
Параметр nMaxInstances определяет максимальное количество реализаций, которые могут быть
созданы для канала. Вы можете указывать здесь значения от 1 до PIPE_UNLIMITED_INSTANCES. В
последнем случае максимальное количество реализаций ограничивается только наличием свободных
системных ресурсов.
Заметим, что если один серверный процесс использует несколько реализаций канала для связи с
несколькими клиентскими, то общее количество реализаций может быть меньше, чем потенциальное
максимальное количество клиентов. Это связано с тем, что клиенты могут использовать реализации
по очереди, если только они не пожелают связаться с серверным процессом все одновременно.
Параметры nOutBufferSize и nInBufferSize определяют, соответственно, размер буферов,
используемых для записи в канал и чтения из канала. При необходимости система может
использовать буферы других, по сравнению с указанными, размеров.
Параметр nDefaultTimeOut определяет время ожидания для реализации канала. Для всех
реализаций необходимо указывать одинаковое значение этого параметра.
Через параметр lpPipeAttributes передается адрес переменной, содержащей атрибуты защиты для
создаваемого канала. В наших приложениях мы будем указывать этот параметр как NULL. В
результате канал будет иметь атрибуты защиты, принятые по умолчанию.
В случае успеха функция CreateNamedPipe возвращает идентификатор созданной реализации
канала, который можно использовать в операциях чтения и записи, выполняемых с помощью таких
функций, как ReadFile и WriteFile.
При ошибке функция CreateNamedPipe возвращает значение INVALID_HANDLE_VALUE. Код
ошибки вы можете уточнить, вызвав функцию GetLastError.
Установка соединения с каналом со стороны сервера
После того как серверный процесс создал канал, он может перейти в режим соединения с
клиентским процессом. Соединение со стороны сервера выполняется с помощью функции
ConnectNamedPipe.
Прототип функции ConnectNamedPipe представлен ниже:
BOOL ConnectNamedPipe (
HANDLE hNamedPipe,
LPOVERLAPPED lpOverlapped);
// идентификатор
именованного канала
// адрес структуры
OVERLAPPED
Через первый параметр серверный процесс передает этой функции идентификатор канала,
полученный от функции CreateNamedPipe.
Второй параметр используется только для организации асинхронного обмена данными через
канал. Если вы используете только синхронные операции, в качестве значения для этого параметра
можно указать NULL.
В случае успеха функция ConnectNamedPipe возвращает значение TRUE, а при ошибке - FALSE.
Код ошибки можно получить с помощью функции GetLastError.
67
В зависимости от различных условий функция ConnectNamedPipe может вести себя по разному.
Если параметр lpOverlapped указан как NULL, функция выполняется в синхронном режиме. В
противном случае используется асинхронный режим.
Для канала, созданного в синхронном блокирующем режиме (с использованием константы
PIPE_WAIT), функция ConnectNamedPipe переходит в состояние ожидания соединения с клиентским
процессом. Именно этот режим мы будем использовать в наших примерах программ, исходные
тексты которых вы найдете ниже.
Если канал создан в синхронном неблокирующем режиме, функция ConnectNamedPipe
немедленно возвращает управление с кодом TRUE, если только клиент был отключен от данной
реализации канала и возможно подключение этого клиента. В противном случае возвращается
значение FALSE. Дальнейший анализ необходимо выполнять с помощью функции GetLastError. Эта
функция может вернуть значение ERROR_PIPE_LISTENING (если к серверу еще не подключен ни
один клиент), ERROR_PIPE_CONNECTED (если клиент уже подключен) или ERROR_NO_DATA
(если предыдущий клиент отключился от сервера, но клиент еще не завершил соединение).
Ниже мы привели пример использования функции ConnectNamedPipe:
HANDLE hNamedPipe;
LPSTR lpszPipeName = "\\\\.\\pipe\\$MyPipe$";
hNamedPipe = CreateNamedPipe (lpszPipeName, PIPE_ACCESS_DUPLEX,
PIPE_TYPE_MESSAGE | PIPE_READMODE_MESSAGE | PIPE_WAIT,
PIPE_UNLIMITED_INSTANCES, 512, 512, 5000, NULL);
fConnected = ConnectNamedPipe (hNamedPipe, NULL);
В данном случае функция ConnectNamedPipe перейдет в состояние ожидания, так как канал был
создан для работы в синхронном блокирующем режиме.
Пример приложения, использующего каналы передачи данных Pipes
После изложения теоретического материала рассмотрим пример. Сначала рассмотрим серверную
часть приложения.
Объявим переменные, которые будут использоваться в программе, и присвоим им необходимее
значения:
BOOL fConnected;
// Флаг успешного создания канала
HANDLE hNamedPipe;
// Идентификатор канала Pipe
LPSTR lpszPipeName = "\\\\.\\pipe\\$MyPipe$"; // Имя создава-емого канала Pipe
char szBuf[512];
// Буфер для передачи данных через канал
DWORD cbRead;
// Количество байт данных, принятых через канал
DWORD cbWritten; // Количество байт данных, переданных через канал
Создаем канал Pipe, имеющий имя lpszPipeName:
hNamedPipe = CreateNamedPipe (lpszPipeName, PIPE_ACCESS_DUPLEX,
PIPE_TYPE_MESSAGE | PIPE_READMODE_MESSAGE | PIPE_WAIT,
PIPE_UNLIMITED_INSTANCES, 512, 512, 5000, NULL);
// Если возникла ошибка, выводим ее код и зваершаем работу приложения
if(hNamedPipe == INVALID_HANDLE_VALUE)
{fprintf(stdout,"CreateNamedPipe: Error %ld\n", GetLastError ());
getch();
return 0;
}
Ожидаем соединения со стороны клиента:
fConnected = ConnectNamedPipe (hNamedPipe, NULL);
// При возникновении ошибки выводим ее код
if(!fConnected)
{ switch(GetLastError ())
{ case ERROR_NO_DATA:
fprintf(stdout,"ConnectNamedPipe: ERROR_NO_DATA");
getch();
CloseHandle (hNamedPipe);
return 0;
68
break;
case ERROR_PIPE_CONNECTED:
fprintf(stdout, "ConnectNamedPipe: ERROR_PIPE_CONNECTED");
getch();
CloseHandle (hNamedPipe);
return 0;
break;
case ERROR_PIPE_LISTENING:
fprintf(stdout,"ConnectNamedPipe: ERROR_PIPE_LISTENING");
getch();
CloseHandle (hNamedPipe);
return 0;
break;
case ERROR_CALL_NOT_IMPLEMENTED:
fprintf(stdout,"ConnectNamedPipe:
ERROR_CALL_NOT_IMPLEMENTED");
getch();
CloseHandle (hNamedPipe);
return 0;
break;
default:
fprintf(stdout,"ConnectNamedPipe: Error %ld\n", GetLastError ());
getch();
CloseHandle (hNamedPipe);
return 0;
break;
}
CloseHandle (hNamedPipe);
getch();
return 0;
}
Цикл получения команд через канал:
while(TRUE)
{ // Получаем очередную команду через канал Pipe if(ReadFile (hNamedPipe, szBuf, 512, &cbRead,
NULL))
{ // Посылаем эту команду обратно клиентскому приложению
if(!WriteFile (hNamedPipe, szBuf, strlen(szBuf) + 1, &cbWritten, NULL)) break;
// Выводим принятую команду на консоль
printf("Received: <%s>\n", szBuf);
// Если пришла команда "exit", завершаем работу приложения
if(!strcmp(szBuf, "exit")) break;
}
else
{
fprintf(stdout,"ReadFile: Error %ld\n",
GetLastError ());
getch();
break;
}
}
Закрываем идентификатор канала:
CloseHandle (hNamedPipe);
А теперь рассмотрим клиентскую часть приложения.
Объявим переменные, которые будут использоваться в программе, и присвоим им необходимее
значения:
69
HANDLE hNamedPipe;
// Идентификатор канала Pipe
DWORD cbWritten;
// Количество байт, переданных через канал
DWORD cbRead;
// Количество байт, принятых через канал
char szBuf[256];
// Буфер для передачи данных
char szPipeName[256]= "\\\\%s\\pipe\\$MyPipe$"// Буфер для имени канала
Создаем канал с процессом PIPES:
hNamedPipe = CreateFile (szPipeName, GENERIC_READ | GENERIC_WRITE, 0, NULL,
OPEN_EXISTING, 0, NULL);
// Если возникла ошибка, выводим ее код и завершаем работу приложения
if(hNamedPipe == INVALID_HANDLE_VALUE)
{ fprintf(stdout,"CreateFile: Error %ld\n", GetLastError ());
getch();
return 0;
}
Цикл обмена данными с серверным процессом:
while(TRUE)
{ // Выводим приглашение для ввода команды
printf("cmd>");
// Вводим текстовую строку
gets(szBuf);
// Передаем введенную строку серверному процессу в качестве команды
if(!WriteFile (hNamedPipe, szBuf, strlen(szBuf) + 1, &cbWritten, NULL)) break;
// Получаем эту же команду обратно от сервера
if(ReadFile (hNamedPipe, szBuf, 512, &cbRead, NULL))
printf("Received back: <%s>\n", szBuf);
// Если произошла ошибка, выводим ее код и завершаем работу приложения
else
{ fprintf(stdout,"ReadFile: Error %ld\n", GetLastError ());
getch();
break;
}
// В ответ на команду "exit" завершаем цикл обмена данными с серверным процессом
if(!strcmp(szBuf, "exit")) break;
}
Закрываем идентификатор канала:
CloseHandle (hNamedPipe);
7.4. Каналы передачи данных Mailslot
Рассмотрим последний способ передачи данных между приложениями: каналы MailSlot.
Каналы Mailslot позволяют выполнять одностороннюю передачу данных от одного или
нескольких клиентов к одному или нескольким серверам. Главная особенность каналов Mailslot
заключается в том, что они, в отличие от других средств, позволяют передавать данные в
широковещательном режиме.
Это означает, что на компьютере или в сети могут работать несколько серверных процессов,
способных получать сообщения через каналы Mailslot При этом один клиентский процесс может
посылать сообщения сразу всем этим серверным процессам.
С помощью каналов Pipe вы не сможете передавать данные в широковещательном режиме, так
как только два процесса могут создать канал типа Pipe.
Создание канала Mailslot
Канал Mailslot создается серверным процессом с помощью специально предназначенной для
этого функции CreateMailslot, которую мы рассмотрим немного позже. После создания серверный
процесс получает идентификатор канала Mailslot. Пользуясь этим идентификатором, сервер может
читать сообщения, посылаемые в канал клиентскими процессами. Однако сервер не может выполнять
над каналом Mailslot операцию записи, так как этот канал предназначен только для односторонней
передачи данных - от клиента к серверу.
70
Приведем прототип функции CreateMailslot:
HANDLE CreateMailslot (
LPCTSTR lpName,
адрес имени канала Mailslot
DWORD nMaxMsgSize,
// максимальный размер
сообщения
DWORD lReadTimeout,
// время ожидания для чтения
LPSECURITY_ATTRIBUTES
// адрес структуры защиты
lpSecurityAttributes);
Через параметр lpName вы должны передать функции CreateMailslot адрес строки символов с
именем канала Mailslot. Эта строка имеет следующий вид:
\\.\mailslot\[Путь]ИмяКанала
В этом имени путь является необязательной компонентой. Тем не менее, вы можете указать его
аналогично тому, как это делается для файлов. Что же касается имени канала Mailslot, то оно задается
аналогично имени канала Pipes.
Параметр nMaxMsgSize определяет максимальный размер сообщений, передаваемых через
создаваемый канал Mailslot. Вы можете указать здесь нулевое значение, при этом размер сообщений
не будет ограничен. Есть, однако, одно исключение - размер широковещательных сообщений,
передаваемых всем рабочим станциям и серверам домена не должен превышать 400 байт.
С помощью параметра lReadTimeout серверное приложение может задать время ожидания для
операции чтения в миллисекундах, по истечении которого функция чтения вернет код ошибки. Если
вы укажите в этом параметре значение MAILSLOT_WAIT_FOREVER, ожидание будет
бесконечным..
Параметр lpSecurityAttributes задает адрес структуры защиты, который мы в наших приложениях
будем указывать как NULL.
При ошибке функцией CreateMailslot возвращается значение INVALID_HANDLE_VALUE. Код
ошибки можно определить при помощи функции GetLastError.
Ниже мы привели пример использования функции CreateMailslot в серверном приложении:
LPSTR lpszMailslotName = "\\\\.\\mailslot\\$MailslotName$";
hMailslot = CreateMailslot(lpszMailslotName, 0,
MAILSLOT_WAIT_FOREVER, NULL);
В этом примере мы задали максимальный размер сообщения, поэтому на эту величину нет
ограничений (кроме ограничения в 400 байт для сообщений, передаваемых всем компьютерам
домена в широковещательном режиме).
Время ожидания указано как MAILSLOT_WAIT_FOREVER, поэтому функции, работающие с
данным каналом Mailslot, будут работать в блокирующем режиме.
Открытие канала Mailslot
Прежде чем приступить к работе с каналом Mailslot, клиентский процесс должен его открыть. Для
выполнения этой операции следует использовать функцию CreateFile, например, так:
LPSTR lpszMailslotName = "\\\\.\\mailslot\\$MailslotName$";
hMailslot= CreateFile (lpszMailslotName, GENERIC_WRITE, FILE_SHARE_READ, NULL,
OPEN_EXISTING, 0, NULL);
Здесь в качестве первого параметра функции CreateFile передается имя канала Mailslot. Заметим,
что вы можете открыть канал Mailslot, созданный на другой рабочей станции в сети. Для этого строка
имени канала, передаваемая функции CreateFile, должна иметь следующий вид:
\\ИмяРабочейСтанции\mailslot\[Путь]ИмяКанала
Можно открыть канал для передачи сообщений всем рабочим станциям заданного домена. Для
этого необходимо задать имя по следующему образцу:
\\ИмяДомена\mailslot\[Путь]ИмяКанала
71
Для передачи сообщений одновременно всем рабочим станциям сети первичного домена имя
задается следующим образом:
\\*\mailslot\[Путь]ИмяКанала
В качестве второго параметра функции CreateFile мы передаем константу GENERIC_WRITE. Эта
константа определяет, что над открываемым каналом будет выполняться операция записи.
Напомним, что клиентский процесс может только посылать сообщения в канал Mailslot, но не читать
их оттуда. Чтение сообщений из канала Mailslot - задача для серверного процесса.
Третий параметр указан как FILE_SHARE_READ, и это тоже необходимо, так как сервер может
читать сообщения, посылаемые одновременно несколькими клиентскими процессами.
Обратите также внимание на константу OPEN_EXISTING. Она используется потому, что
функция CreateFile открывает существующий канал, а не создает новый.
Запись сообщений в канал Mailslot
Запись сообщений в канал Mailslot выполняет клиентский процесс, вызывая для этого функцию
WriteFile:
HANDLE hMailslot;
char szBuf[512];
DWORD cbWritten;
WriteFile (hMailslot, szBuf, strlen(szBuf) + 1,&cbWritten, NULL);
В качестве первого параметра этой функции необходимо передать идентификатор канала Mailslot,
полученный от функции CreateFile.
Второй параметр определяет адрес буфера с сообщением, третий - размер сообщения. В нашем
случае сообщения передаются в виде текстовой строки, закрытой двоичным нулем, поэтому для
определения длины сообщения мы воспользовались функцией strlen.
Чтение сообщений из канала Mailslot
Серверный процесс может читать сообщения из созданного им канала Mailslot при помощи
функции ReadFile, как это показано ниже:
HANDLE hMailslot;
char szBuf[512];
DWORD cbRead;
ReadFile (hMailslot, szBuf, 512, &cbRead, NULL);
Через первый параметр функции ReadFile передается идентификатор созданного ранее канала
Mailslot, полученный от функции CreateMailslot. Второй и третий параметры задают, соответственно,
адрес буфера для сообщения и его размер.
Заметим, что перед выполнением операции чтения следует проверить состояние канала Mailslot.
Если в нем нет сообщений, то функцию ReadFile вызывать не следует. Для проверки состояния
канала вы должны воспользоваться функцией GetMailslotInfo, описанной ниже.
Определение состояния канала Mailslot
Серверный процесс может определить текущее состояние канала Mailslotпо его идентификатору с
помощью функции GetMailslotInfo. Прототип этой функции мы привели ниже:
BOOL GetMailslotInfo(
HANDLE hMailslot,
LPDWORD
lpMaxMessageSize
LPDWORD lpNextSize,
LPDWORD
// идентификатор канала Mailslot
// адрес максимального размера
сообщения
// адрес размера следующего
сообщения
// адрес количества сообщений
72
lpMessageCount,
LPDWORD
lpReadTimeout);
// адрес времени ожидания
Через параметр hMailslot функции передается идентификатор канала Mailslot, состояние которого
необходимо определить.
Остальные параметры задаются как указатели на переменные типа DWORD, в которые будут
записаны параметры состояния канала Mailslot.
В переменную, адрес которой передается через параметр lpMaxMessageSize, после возвращения
из функции GetMailslotInfo будет записан максимальный размер сообщения. Вы можете использовать
это значение для динамического получения буфера памяти, в который это сообщение будет
прочитано функцией ReadFile.
В переменную, адрес которой указан через параметр lpNextSize, записывается размер следующего
сообщения, если оно есть в канале. Если же в канале больше нет сообщений, в эту переменную будет
записана константа MAILSLOT_NO_MESSAGE.
С помощью параметра lpMessageCount вы можете определить количество сообщений, записанных
в канал клиентскими процессами. Если это количество равно нулю, вам не следует вызывать
функцию ReadFile для чтения несуществующего сообщения.
И, наконец, в переменную, адрес которой задается в параметре lpReadTimeout, записывается
текущее время ожидания, установленное для канала (в миллисекундах).
Если вам не нужна вся информация, которую можно получить с помощью функции
GetMailslotInfo, некоторые из ее параметров (кроме, разумеется, первого) можно указать как NULL.
В случае успешного завершения функция GetMailslotInfo возвращает значение TRUE, а при
ошибке - FALSE. Код ошибки можно получить, вызвав функцию GetLastError.
Ниже приводится пример использования функции GetMailslotInfo:
BOOL fReturnCode;
DWORD cbMessages;
DWORD cbMsgNumber;
fReturnCode = GetMailslotInfo(hMailslot, NULL, &cbMessages, &cbMsgNumber, NULL);
Изменение состояния канала Mailslot
С помощью функции SetMailslotInfo серверный процесс может изменить время ожидания для
канала Mailslot уже после его создания.
Прототип функции SetMailslotInfo приведен ниже:
BOOL SetMailslotInfo(
HANDLE hMailslot
DWORD dwReadTimeout);
// идентификатор канала
Mailslot
// время ожидания
Через параметр hMailslot функции SetMailslotInfo передается идентификатор канала Mailslot, для
которого нужно изменить время ожидания.
Новое значение времени ожидания в миллисекундах задается через параметр dwReadTimeout. Вы
также можете указать здесь константы 0 или MAILSLOT_WAIT_FOREVER. В первом случае
функции, работающие с каналом, вернут управление немедленно, во втором - будут находиться в
состоянии ожидания до тех пор, пока не завершится выполняемая операция.
Пример приложения, использующего каналы передачи данных MailSlot
Рассмотрим пример реализации каналов передачи данных MailSlot. Сначала рассмотрим
серверную часть.
Объявим переменные, которые будут использоваться в программе, и присвоим им необходимее
значения:
BOOL fReturnCode;
DWORD cbMessages;
// Код возврата из функций
// Размер сообщения в байтах
73
DWORD cbMsgNumber;
// Количество сообщений в каналеMailslot
HANDLE hMailslot
// Идентификатор канала Mailslot
LPSTR lpszMailslot Name ="\\\\.\\mailslot\\$Channel$"; // Имя
создаваемого канала
char szBuf[512];
// Буфер для передачи данных
через канал
DWORD cbRead;
// Количество байт данных,
Через канал
Создаем канал Mailslot, имеющий имя lpszMailslotName:
hMailslot = CreateMailslot(lpszMailslotName, 0, MAILSLOT_WAIT_FOREVER, NULL);
// Если возникла ошибка, выводим ее код и завершаем работу приложения
if(hMailslot== INVALID_HANDLE_VALUE)
{fprintf(stdout,"CreateMailslot: Error %ld\n", GetLastError ());
getch();
return 0;
}
Цикл получения команд через канал:
while(TRUE)
{ // Определяем состояние канала Mailslot
fReturnCode = GetMailslotInfo(hMailslot, NULL, &cbMessages, &cbMsgNumber, NULL);
if(!fReturnCode)
{ fprintf(stdout,"GetMailslotInfo: Error %ld\n", GetLastError ());
getch();
break;
}
// Если в канале есть Mailslot сообщения, читаем первое из них и выводим на экран
if(cbMsgNumber != 0)
{if(ReadFile(hMailslot, szBuf, 512, &cbRead, NULL))
{ printf("Received: <%s>\n", szBuf);
// Выводим принятую строку на консоль
// Если пришла команда "exit", завершаем работу приложения
if(!strcmp(szBuf, "exit")) break;
}
else
{ fprintf(stdout,"ReadFile: Error %ld\n", GetLastError ());
getch();
break;
}
}
Sleep (500); // Выполняем задержку на 500 миллисекунд
}
Перед завершением приложения закрываем идентификатор канала Mailslot:
CloseHandle (hMailslot);
Рассмотрим работу клиентской части. Объявим переменные, которые будут использоваться в
программе, и присвоим им необходимее значения:
HANDLE hMailslot;
// Идентификатор канала Mailslot
char szMailslotName[256]= "\\\\.\\mailslot\\$Channel$"; // Буфер для имени канала
char szBuf[512];
// Буфер для передачи данных через канал
DWORD cbWritten;
// Количество байт, переданных
через канал
Создаем канал с процессом MSLOTS
74
hMailslot = CreateFile (szMailslotName, GENERIC_WRITE, FILE_SHARE_READ, NULL,
OPEN_EXISTING, 0, NULL);
// Если возникла ошибка, выводим ее код и завершаем работу приложения
if(hMailslot == INVALID_HANDLE_VALUE)
{ fprintf(stdout,"CreateFile: Error %ld\n", GetLastError ());
getch();
return 0;
}
Цикл посылки команд через канал:
while(TRUE)
{ printf("cmd>");
// Выводим приглашение для ввода команды
gets(szBuf);
// Вводим текстовую строку
// Передаем введенную строку серверному процессу в качестве команды
if(!WriteFile (hMailslot, szBuf, strlen(szBuf) + 1, &cbWritten, NULL)) break;
// В ответ на команду "exit" завершаем цикл обмена данными с серверным процессом
if(!strcmp(szBuf, "exit")) break;
}
Закрываем идентификатор канала:
CloseHandle (hMailslot);
7.5. Передача сообщений между приложениями
Метод передачи данных между процессами, основанный на использовании файлов,
отображенных на виртуальную память, работает достаточно быстро, так как процессы имеют прямой
доступ к общим страницам памяти. Тем не менее, при использовании этого метода необходимо
заботиться о синхронизации процессов, для чего следует использовать объекты синхронизации.
Если скорость передачи данных не является критичной, можно воспользоваться удобным
способом передачи данных, не требующим синхронизации. Этот метод основан на передаче
сообщения WM_COPYDATA из одного приложения в другое при помощи функции SendMessage
(функцию PostMessage для передачи этого сообщения использовать нельзя).
Сообщение WM_COPYDATA использует оба параметра - wParam и lParam. Через параметр
wParam необходимо передать идентификатор окна, посылающего сообщение. Параметр lParam
используется
для
передачи
указателя
на
предварительно
заполненную
структуру
COPYDATASTRUCT, в которой находится ссылка на передаваемые данные.
Если приложение обрабатывает сообщение WM_COPYDATA, то соответствующий обработчик
должен вернуть значение TRUE, а если нет - FALSE.
Ниже мы привели формат структуры COPYDATASTRUCT:
Typede fstruct
tagCOPYDATASTRUCT
{ DWORD dwData;
DWORD cbData;
PVOID lpData;}
// 32-разрядные данные
// размер передаваемого
буфера с данными
// указатель на буфер с
данными
Перед посылкой сообщения WM_COPYDATA приложение должно заполнить структуру
COPYDATASTRUCT.
В поле dwData можно записать произвольное 32-разрядное значение, которое будет передано
вместе с сообщением.
В поле lpData вы дополнительно можете записать указатель на область данных, полученную,
например, при помощи функции HeapAlloc. Размер этой области следует записать в поле cbData.
Когда функция окна принимающего приложения получит сообщение WM_COPYDATA, она
должна скопировать в свой локальный буфер данные, которые были переданы вместе с сообщением.
И это единственное, что можно с этими данными сделать. Их, например, нельзя изменять. Не следует
также надеяться, что данные сохранятся до обработки другого сообщения, поэтому копирование
следует выполнить во время обработки сообщения WM_COPYDATA.
75
Если вам достаточно передать из одного приложения в другое 32-разрядное значение, в поле
lpData можно записать константу NULL.
Пример приложения, использующего передачу сообщений между процессами
Рассмотрим реализацию клиентской части приложения (отправителя):
HWND hWnd;
//Идентификатор главного окна приложения - отправителя
HWND hWndServer;
// Идентификатор главного окна
приложения - получателя
COPYDATASTRUCT cd; // Структура для передачи данных между процессами
char szBuf[80];
// Буферы для передаваемых данных
// Записываем адрес и размер строки в структуру типа COPYDATASTRUCT
cd.lpData=szBuf;
cd.cbData=strlen(szBuf) + 1;
// Посылаем сообщение серверному приложениию-получателю
SendMessage(hWndServer, WM_COPYDATA,(WPARAM)hWnd, (LPARAM)&cd);
Реализацию серверной части приложения (получателя). сводится к получению и обработке
сообщения WM_COPYDATA. В качестве примера рассмотрим обработчик, осуществляющий вывод
на экран полученной информации:
LRESULT WINAPI
WndProc(HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam)
{ char szBuf[80]; // Буферы для передаваемых данных switch(msg)
{ case WM_COPYDATA:
{ // Копируем полученные данные во внутренний буфер
strcpy(szBuf, ((PCOPYDATASTRUCT)lParam)->lpData);
printf(szBuf,%s);
break;
}
HANDLE_MSG(hWnd, WM_CREATE,
WndProc_OnCreate);
WM_DESTROY, WndProc_OnDestroy);
HANDLE_MSG(hWnd, WM_PAINT, WndProc_OnPaint);
default:
return(DefWindowProc(hWnd, msg, wParam, lParam));
}
}
HANDLE_MSG(hWnd,
8. Номер варианта
Последняя цифра зачетной книжки
0
1
2
3
4
5
Номер варианта
8
3
4
1
6
7
6
7
8
9
7
5
9
1
0
9. Варианты заданий
Номер
варианта
1
2
3
4
5
Способ взаимодействия процессов
Взаимодействие посредством механизма
отображения файлов на память: совместное
использование двумя процессами виртуальной
памяти;
Взаимодействие посредством анонимного канала
Pipe;
Взаимодействие посредством канала передачи
данных Mailslot;
Взаимодействие посредством сообщения
WM_COPYDATA;
Взаимодействие посредством механизма
76
6
7
8
9
10
отображения файлов на память: совместное
использование двумя процессами виртуальной
памяти;
Взаимодействие посредством сообщения
WM_COPYDATA;
Взаимодействие посредством механизма
отображения файлов на память: совместное
использование двумя процессами одного и того же
файла;
Взаимодействие посредством именованного
канала Pipe;
Взаимодействие посредством канала передачи
данных Mailslot;
Взаимодействие посредством сообщения
WM_COPYDATA;
77
Лабораторная работа №9
«Моделирование систем на основе сетей Петри»
1. Цель занятия
Изучение сетей Петри. Моделирование систем на основе сетей Петри.
2.



Литература
Котов B.E. Сети Петри. М., Наука, 1984.
Питерсон Дж. Теория сетей Петри и моделирование систем. - М.: Мир, 1984.
Майника Э. Алгоритмы оптимизации на сетях и графах /Под ред. Е.К.Масловского - М.:
Мир,1981. - 322 c.
3. Выполнение работы
 Изучить:
 структуру и состав сетей Петри;
 маркировку сетей Петри;
 правила выполнения сетей Петри;
 способы моделирования процессов в сетях Петри
 составить алгоритм выполняемого процесса;
 определить множества условий и событий для процесса;
 построить сеть Петри для моделируемого процесса;
 описать работу полученной сети Петри;
 составить отчет по проделанной работе в соответствии с требованиями, предъявляемыми в
пункте 6 данного практического занятия.
4.
1.
2.
3.
4.
5.
6.
7.
8.
5.






Контрольные вопросы
Дайте определение сети Петри.
Чем определяется структура сети Петри?
Что такое граф сети Петри? Как он строится?
Что такое маркировка сети Петри?
Сформулируйте правила выполнения сетей Петри?
Что такое событие в сетях Петри?
Что такое условие в сетях Петри?
Кратко сформулируйте алгоритм моделирования процессов в сетях Петри
Содержание работы
Ознакомиться с кратким теоретическим материалом, ответить на контрольные вопросы;
определить номер выполняемого варианта;
для заданного варианта построить составить алгоритм выполняемого процесса;
определить множества условий и событий для процесса;
построить сеть Петри для моделируемого процесса;
описать работу полученной сети Петри.
6. Содержание отчета
Отчет должен содержать следующее:
 титульный лист с указанием наименования и цели занятия; фамилии, имени, отчества и номера
группы студента; фамилии, имени, отчества преподавателя, а также номер выполняемого
варианта;
 дату выполнения работы;
 цель занятия;
 условия предложенной задачи;
 алгоритм моделируемого процесса;
 перечень событий и условий моделируемого процесса;
 таблицу пред- и постусловий для событий и условий моделируемого процесса;
 описать работу полученной сети Петри;
 выводы о проделанной работе.
78
7. Краткий теоретический материал
7.1. Введение в сети Петри
Сети Петри это инструмент для математического моделирования и исследования сложных
систем. Цель представления системы в виде сети Петри и последующего анализа этой сети состоит в
получении важной информации о структуре и динамическом поведении моделируемой системы. Эта
информация может использоваться для оценки моделируемой системы и выработки предложений по
ее усовершенствованию. Впервые сети Петри предложил немецкий математик Карл Адам Петри.
Сети Петри предназначены для моделирования систем, которые состоят из множества
взаимодействующих друг с другом компонент. При этом компонента сама может быть системой.
Действиям различных компонент системы присущ параллелизм. Примерами таких систем могут
служить вычислительные системы, в том числе и параллельные, компьютерные сети, программные
системы, обеспечивающие их функционирование, а также экономические системы, системы
управления дорожным движением, химические системы, и т. д.
В одном из подходов к проектированию и анализу систем сети Петри используются, как
вспомогательный инструмент анализа. Здесь для построения системы используются общепринятые
методы проектирования. Затем построенная система моделируется сетью Петри, и модель
анализируется. Если в ходе анализа в проекте найдены изъяны, то с целью их устранения проект
модифицируется. Модифицированный проект затем снова моделируется и анализируется. Этот цикл
повторяется до тех пор, пока проводимый анализ не приведет к успеху.
Другой подход предполагает построение проекта сразу в виде сети Петри. Методы анализа
применяются только для создания проекта, не содержащего ошибок. Затем сеть Петри преобразуется
в реальную рабочую систему.
В первом случае необходима разработка методов моделирования систем сетями Петри, а во
втором случае должны быть разработаны методы реализации сетей Петри системами.
7.2. Основные определения
7.2.1. Теоретико-множественное определение сетей Петри
Пусть мультимножество это множество, допускающее вхождение нескольких экземпляров
одного и того же элемента.
Сеть Петри N является четверкой N=(P,Т,I,O), где
P = {p1, p2,..., pn} — конечное множество позиций, n  0;
T = {t1, t2,..., tm} — конечное множество переходов, m  0;
I: T  P* — входная функция, сопоставляющая переходу мультимножество его входных
позиций;
О: T  P* - выходная функция, сопоставляющая переходу мультимножество его выходных
позиций.
Позиция pP называется входом для перехода tT, если pI(t). Позиция pP называется
выходом для перехода tT, если pO(t). Структура сети Петри определяется ее позициями,
переходами, входной и выходной функциями.
Пример 5.1 Сеть Петри N =(P,T,I,O),
P={p1, p2, p3},
T={t1, t2},
I(t1)={ p1, p1, p2},
O(t1)={p3},
I(t2)={ p1, p2, p2},
O(t2)={p3}.
79
Рис. 5.1
Использование мультимножеств входных и выходных позиций перехода, а не множеств,
позволяет позиции быть кратным входом и кратным выходом перехода соответственно. При этом
кратность определяется числом экземпляров позиции в соответствующем мультимножестве.
7.2.2. Графы сетей Петри.
Наиболее наглядным представлением сети Петри является её графическое представление,
которое представляет собой двудольный, ориентированный мультиграф.
Граф сети Петри обладает двумя типами узлов: кружок , представляющий позицию сети
Петри; и планка , представляющая переход сети Петри. Ориентированные дуги этого графа
(стрелки) соединяют переход с его входными и выходными позициями. При этом дуги направлены от
входных позиций к переходу и от перехода к выходным позициям. Кратным входным и выходным
позициям перехода соответствуют кратные входные и выходные дуги. Граф сети Петри примера 5.1.
В графе сети Петри не возможны дуги между двумя позициями и между двумя переходами.
7.2.3. Маркировка сетей Петри.
Маркировка — это размещение по позициям сети Петри фишек, изображаемых на графе сети
Петри точками. Фишки используются для определения выполнения сети Петри. Количество фишек в
позиции при выполнении сети Петри может изменяться от 0 до бесконечности.
Маркировка  сети Петри N=(P,T,I,О) есть функция, отображающая множество позиций P во
множество Nat неотрицательных целых чисел. Маркировка , может быть также определена как nвектор =<

(pn)>, где n – число позиций в сети Петри и для каждого 1  i  n
1
2),
(pi)  Nat – количество фишек в позиции pi.
Маркированная сеть Петри N=(P,Т,I,О,) определяется совокупностью структуры сети Петри
(P,T,I,О) и маркировки .
Рис. 5.2
На рисунке 5.2 представлена маркированная сеть Петри  = <1,0,1>.
Множество всех маркировок сети Петри бесконечно. Если фишек, помещаемых в позицию
слишком много, то удобнее не рисовать фишки в кружке этой позиции, а указывать их количество.
7.2.4. Правила выполнения сетей Петри.
Сеть Петри выполняется посредством запусков переходов. Запуск перехода управляется
фишками в его входных позициях и сопровождается удалением фишек из этих позиций и
добавлением новых фишек в его выходные позиции.
Переход может запускаться только в том случае, когда он разрешен. Переход называется
разрешенным, если каждая из его входных позиций содержит число фишек, не меньшее, чем число
дуг, ведущих из этой позиции в переход (или кратности входной дуги).
80
Пусть функция ^#: PT  Nat для произвольных позиции pP и перехода tТ задает значение
^
#(p,t), которое совпадает с кратностью дуги, ведущей из p в t, если такая дуга существует, и с нулем,
в противном случае.
Пусть функция #^: TP Nat для произвольных и перехода tT позиции pP задает значение
^
# (t,p), которое совпадает с кратностью дуги, ведущей из t в p, если такая дуга существует, и с нулем,
в противном случае.
Переход tT в маркированной сети Петри N=(P,T,1,О,) разрешен, если для всех p  I(t)
справедливо 
 ^#(p,t).
Запуск разрешённого перехода tT из своей входной позиции pI(t) удаляет ^#(p,t) фишек, а в
свою выходную позицию p’ O(t) добавляет #^(t,p’) фишек.
а
б
Рис. 5.3
Сеть Петри до запуска перехода t1 (рис. 5.3, а). Сеть Петри после запуска перехода t1 (рис. 5.3,
б).
Переход t в маркированной сети Петри с маркировкой  может быть запущен всякий раз, когда
он разрешен и в результате этого запуска образуется новая маркировка ', определяемая для всех pP
следующим соотношением:
'(p)= (p) – ^#(p,t) + #^(t,p).
Запуски могут осуществляться до тех пор, пока существует хотя бы один разрешенный
переход. Когда не останется ни одного разрешенного перехода, выполнение прекращается.
Если запуск произвольного перехода t преобразует маркировку  сети Петри в новую
маркировку ', то будем говорить, что ' достижима из  посредством запуска перехода t и
обозначать этот факт, как  t '. Это понятие очевидным образом обобщается для случая
последовательности запусков разрешённых переходов. Через R(N,) обозначим множество всех
достижимых маркировок из начальной маркировки  в сети Петри N.
Преобразование маркировки сети Петри изображено на рисунке 5.3. Переход t1 преобразует
 =<5,1> в маркировку ’=<2,3>.
7.3. Моделирование систем на основе сетей Петри
7.3.1. События и условия
Представление системы сетью Петри основано на двух основополагающих понятиях: событиях
и условиях. Возникновением событий управляет состояние системы, которое может быть описано
множеством условий. Условие может принимать либо значение «истина», либо значение «ложь».
Возникновение события в системе возможно, если выполняются определённые условия –
предусловия события. Возникновение события может привести к выполнению других условий –
постусловий события. В качестве примера рассмотрим следующую ниже задачу моделирования.
Пример 5.2. Моделирование последовательной обработки запросов сервером базы данных.
Сервер находится в состоянии ожидания до тех пор, пока от пользователя не поступит запрос
клиента, который он обрабатывает и отправляет результат такой обработки пользователю.
Условиями для рассматриваемой системы являются:
а) сервер ждет;
б) запрос поступил и ждет;
в) сервер обрабатывает запрос;
г) запрос обработан.
Событиями для этой системы являются:
81
1.Запрос поступил.
2. Сервер начинает обработку запроса.
3. Сервер заканчивает обработку запроса.
4. Результат обработки отправляется клиенту.
Для перечисленных событий можно составить следующую таблицу их пред- и постусловий
Событие
Предусловия
Постусловия
1
нет
б
2
а, б
в
3
в
г, а
4
г
нет
Такое представление системы легко моделировать сетью Петри. В сети Петри условия
моделируются позициями, события — переходами. При этом входы перехода являются
предусловиями соответствующего события; выходы — постусловиями. Возникновение события
моделируется запуском соответствующего перехода. Выполнение условия представляется фишкой в
позиции,
Рис. 5.4
соответствующей этому условию. Запуск перехода удаляет фишки, представляющие выполнение
предусловий и образует новые фишки, которые представляют выполнение постусловий.
На рисунке 5.4. предусловие выполняется для события 2.
7.3.2. Одновременность и конфликт
Особенность сетей Петри - их асинхронная природа. В сетях Петри отсутствует измерение
времени. В них учитывается лишь важнейшее свойство времени – частичное упорядочение событий.
Выполнение сети Петри (или поведение моделируемой системы) рассматривается здесь как
последовательность дискретных событий, которая является одной из возможных. Если в какой-то
момент времени разрешено более одного перехода, то любой из них может стать «следующим»
запускаемым. Переходы в сети Петри, моделирующей некоторую систему, представляют ее
примитивные события (длительность которых считается равной 0), и в один момент времени может
быть запущен только один разрешённый переход.
Моделирование одновременного (параллельного) возникновения независимых событий
системы в сети Петри
а
б
Рис. 5.5
демонстрируется на рисунке слева (рис. 5.5, а).
В этой ситуации два перехода являются разрешенными и не влияют друг на друга в том
смысле, что могут быть запущены один вслед за другим в любом порядке.
Другая ситуация в приведенной справа (рис. 5.5, б) сети Петри. Эти два разрешённые перехода
находятся в конфликте, т. е. запуск одного из них удаляет фишку из общей входной позиции и тем
самым запрещает запуск другого. Таким образом, моделируются взаимоисключающие события
системы
8. Номер варианта
0
1
Последняя цифра зачетной книжки
2
3
4
5
6
7
Номер варианта
82
8
9
3
8
2
9
7
10
6
9. Варианты заданий
Номер
Моделируемый процесс
варианта
1
Работа автомата разменивающего монеты
2
Работа автомата продающего прохладительные напитки
3
Установление местного телефонного соединения между
двумя абонентами
4
Работа критической секции на примере трех
взаимодействующих процессов
5
Работа объекта синхронизации ОС Windows ожидающий
таймер
на
примере
трех
одновременно
взаимодействующих процессов
6
Работа банкомата
7
Установление междугороднего телефонного соединения с
возможностью отказа в обслуживании
8
Работа объекта синхронизации ОС Windows событие на
примере
трех
одновременно
взаимодействующих
процессов
9
Работа Интернет магазина
10
Работа объекта синхронизации семафор на примере трех
одновременно взаимодействующих процессов
83
4
1
5