гуд работа. Курс лекций теория вычислительных процессов
 Скачать 1.54 Mb.
|
|
ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ КАФЕДРА ИНФОРМАЦИОННЫХ СИСТЕМ КУРС ЛЕКЦИЙ Теория вычислительных процессов Направление подготовки 654600 — Информатика и вычислительная техника Специальность 220400 — Программное обеспечение вычислительной техники и автоматизированных систем Иркутск - 2005 2 СОДЕРЖАНИЕ 1. СЕМАНТИЧЕСКАЯ ТЕОРИЯ ПРОГРАММ.................................................................. 4 Н ЕКОТОРЫЕ ВОПРОСЫ СЕМАНТИЧЕСКОЙ ТЕОРИИ ПРОГРАММ . .................................................. 4 Р АССМОТРИМ ОСНОВНЫЕ ПОДХОДЫ ПРИ ОРГАНИЗАЦИИ ВЫЧИСЛЕНИЙ ПРИ ВЫПОЛНЕНИИ ПОСЛЕДОВАНЫХ ПРОГРАММ С ПАМЯТЬЮ ................................................................................... 5 И НФОРМАЦИОННЫЕ СВЯЗИ И СЕЧЕНИЯ : ..................................................................................... 7 2. ВЕРИФИКАЦИЯ ПРОГРАММ.......................................................................................... 9 О СНОВНЫЕ ПОНЯТИЯ И ТЕОРЕМЫ ............................................................................................... 9 З АДАЧИ ..................................................................................................................................... 14 3. ТЕОРЕТИЧЕСКИЕ МОДЕЛИ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ................... 16 В ЗАИМОДЕЙСТВИЕ И УПРАВЛЕНИЕ ПРОЦЕССАМИ .................................................................... 16 Э ЛЕМЕНТАРНОЕ ОПРЕДЕЛЕНИЕ И СВОЙСТВА ПРОЦЕССА .......................................................... 16 Введение ............................................................................................................................... 16 Определения термина «процесс» .................................................................................... 17 Состояния процесса........................................................................................................... 17 Управление процессами в многопроцессорном компьютере ......................................... 19 Переход процесса из состояния в состояние ................................................................ 20 Контекст и дескриптор процесса .................................................................................. 21 Форматы таблиц процессов ............................................................................................ 21 Блок управления процессом .............................................................................................. 22 Операции над процессами................................................................................................. 22 Приостановка и возобновление ....................................................................................... 24 С ЛОЖНЫЕ ВЗАИМОДЕЙСТВИЯ ПРОЦЕССОВ ............................................................................... 25 У РОВНИ ПАРАЛЛЕЛИЗМА .......................................................................................................... 26 К ЛАССИФИКАЦИЯ Ф ЛИННА ...................................................................................................... 26 К ЛАССИФИКАЦИЯ Ш ОРА .......................................................................................................... 28 Ф ОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ ПРОЦЕССА , МОДЕЛЬ Х ОРНИНГА -Р ЕНДЕЛЛА . ............................. 29 Р ЕАЛИЗАЦИЯ ПРОЦЕССА . .......................................................................................................... 30 А ЛГОРИТМЫ ПЛАНИРОВАНИЯ ПРОЦЕССОВ ............................................................................... 31 В ЫТЕСНЯЮЩИЕ И НЕВЫТЕСНЯЮЩИЕ АЛГОРИТМЫ ПЛАНИРОВАНИЯ ...................................... 32 С ИНХРОНИЗАЦИЯ ПРОЦЕССОВ .................................................................................................. 34 С ИНХРОНИЗАЦИЯ НИЖНЕГО УРОВНЯ ........................................................................................ 35 С ЕМАФОРЫ . .............................................................................................................................. 37 С ИНХРОНИЗАЦИЯ ВЕРХНЕГО УРОВНЯ . ...................................................................................... 39 М ОНИТОРЫ И СЕРВЕРЫ ТРАНЗАКЦИЙ ....................................................................................... 40 Т УПИКИ ..................................................................................................................................... 41 Н ИТИ ......................................................................................................................................... 43 4. СИНХРОНИЗАЦИЯ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ ..................................... 44 А ЛГОРИТМ СИНХРОНИЗАЦИИ ЛОГИЧЕСКИХ ЧАСОВ ............................................................. 44 А ЛГОРИТМЫ ВЗАИМНОГО ИСКЛЮЧЕНИЯ ............................................................................. 46 Централизованный алгоритм ......................................................................................... 46 Распределенный алгоритм................................................................................................ 46 Алгоритм Token Ring......................................................................................................... 46 3 Неделимые транзакции....................................................................................................... 47 5. ПРОЦЕССЫ И НИТИ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ.................................. 49 П ОНЯТИЕ " НИТЬ " ...................................................................................................................... 49 Р АЗЛИЧНЫЕ СПОСОБЫ ОРГАНИЗАЦИИ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА С ИСПОЛЬЗОВАНИЕМ НИТЕЙ ........................................................................................................................................ 50 В ОПРОСЫ РЕАЛИЗАЦИИ НИТЕЙ ................................................................................................. 51 6. ПЛАНИРОВАНИЕ ПРОЦЕССОВ В ОС UNIX ............................................................. 52 7. ПРОЦЕССЫ И НИТИ В ОС WINDOWS NT................................................................. 54 8. УПРАВЛЕНИЕ ПАМЯТЬЮ ............................................................................................. 57 Т ИПЫ АДРЕСОВ ......................................................................................................................... 57 М ЕТОДЫ РАСПРЕДЕЛЕНИЯ ПАМЯТИ БЕЗ ИСПОЛЬЗОВАНИЯ ДИСКОВОГО ПРОСТРАНСТВА ......... 58 Распределение памяти фиксированными разделами....................................................... 59 Распределение памяти разделами переменной величины .......................................... 60 Перемещаемые разделы..................................................................................................... 61 М ЕТОДЫ РАСПРЕДЕЛЕНИЯ ПАМЯТИ С ИСПОЛЬЗОВАНИЕМ ДИСКОВОГО ПРОСТРАНСТВА .......... 62 Понятие виртуальной памяти........................................................................................... 62 Страничное распределение .............................................................................................. 62 Сегментное распределение ............................................................................................... 64 Странично-сегментное распределение .......................................................................... 66 Свопинг................................................................................................................................. 67 9. ИЕРАРХИЯ ЗАПОМИНАЮЩИХ УСТРОЙСТВ. ПРИНЦИП КЭШИРОВАНИЯ ДАННЫХ................................................................................................................................... 68 Аппаратно-независимый уровень управления виртуальной памятью........................ 70 Исключительные ситуации при работе с памятью........................................................ 70 Алгоритмы замещения страниц....................................................................................... 71 Заключение ........................................................................................................................ 74 10. АСИНХРОННОЕ ПРОГРАММИРОВАНИЕ .............................................................. 75 10.1. О СНОВНЫЕ ПОНЯТИЯ ....................................................................................................... 75 10.1.1 П ОНЯТИЕ АСИНХРОННОЙ ПРОГРАММЫ ......................................................................... 75 10.1.2. Н ЕКОРРЕКТНОЕ ВЫЧИСЛЕНИЕ ДАННЫХ ........................................................................ 77 10.1.3. Н ЕКОРРЕКТНОЕ СЧИТЫВАНИЕ ДАННЫХ ........................................................................ 78 10.2. С ЕТИ П ЕТРИ ..................................................................................................................... 78 10.2.1. О ПРЕДЕЛЕНИЕ СЕТИ П ЕТРИ .......................................................................................... 78 10.2.2. Р АЗМЕТКА СЕТИ ............................................................................................................ 79 10.2.3. Г РАФ ДОСТИЖИМОСТИ .................................................................................................. 82 10.2.4. Д ЕДЛОКИ ....................................................................................................................... 83 10.3. M ESSAGE PASSING INTERFACE .......................................................................................... 86 10.3.1. О ПРЕДЕЛЕНИЕ MPI ....................................................................................................... 86 10.3.2. П АРАЛЛЕЛЬНАЯ ПРОГРАММА РАЗДЕЛЕНИЯ МНОЖЕСТВ ............................................... 88 10.3.3. К ОММУНИКАЦИОННО - ЗАМКНУТЫЕ СЛОИ ПАРАЛЛЕЛЬНОЙ ПРОГРАММЫ ..................... 90 10.3.4. К ОГЕРЕНТНОСТЬ ПАРАЛЛЕЛЬНЫХ ПРОГРАММ .............................................................. 91 10.3.5. А НАЛИЗ ПРОГРАММЫ РАЗДЕЛЕНИЯ МНОЖЕСТВ ............................................................ 92 4 1. СЕМАНТИЧЕСКАЯ ТЕОРИЯ ПРОГРАММ Некоторые вопросы семантической теории программ. Программирование теоретическое – математическая дисциплина, изучающая математические абстракции программ, трактуемых как объекты, выраженные на формальном языке, обладающие опре- деленной информационной и логической структурой и подлежащие исполнению на автоматических устройствах. Т.п. сформировалось на основе двух моделей вычислений: - последовательных программ с памятью или операторных программах; - рекурсивных программ. Обе модели строятся над абстрактной алгебраической системой Φ = {γ1, γ2, … , γm} и предикатных Π={π1,… πn} символов с заданным для каждого символа числом его аргументов (арностью). Определение класса программ слагается из трех частей: - схемы программ (синтаксиса) - интерпретации; - семантики. Схема программы – это конструкционный объект, показывающий, как строится программа с ис- пользованием сигнатуры и других формальных символов. Интерпретация – этьо задание конкретной предметной области и сопоставление символам сигна- туры конкретных функций и предикатов (базовых операций), согласованных с предметной областью и арностью символов. Семантика – это способ сопоставления каждоц программе результата ее выполнения. Как правило, с программами связывают вычисляемые ими функции. Схема программ с памятью, называемая также алголоподобной, или операторной, схемой, зада- ется в виде конечного ориентированного графа переходов, имеющего обычно одну входную и одну вы- ходную вершины, вершины с одной (преобразователи) и двумя (распознаватели) исходящими дугами. С помощью символов сигнатуры и счетного множества символов переменных и констант обыч- ным образом строится множество функциональных и предикатных термов. Каждому распознавателю сопоставляется некоторый предикатный терм, а преобразователю – оператор присваивания, имеющий вид y = τ, где y – символ переменной, а τ - функциональный терм. Конечная совокупность всех переменных в схеме образуют ее память. Интерпретация в дополнение к конкретезации базовых операций предписывает каждой перемен- ной область ее изменения, а каждой константе – ее значния. Интерпретация обычно входит в семантику как параметр, поэтому схема прогрммы задает мно- жество программ и вычисляемые ими функции, которое получается при варьировании интерпретаций над некоторым запасом базовых операций. Для программ с памятью обычна т.н операционная семантика,состоящая из алгоритма выполне- ния программы на заданном состоянии памяти. - Программа выполняется при движении по графу переходов: ++ при попадании на распознаватель вычисляется предикатный терм и происходит пере- ход по дуге, соответствующей значению предиката. ++ при попадании на преобразователь с оператором x := a вычисляется значение a и при- сваевается переменной x. - Результат выполнения программы – состояние памяти пр попадании на выходную вершину. Схема рекурсивной программы, или рекурсивная схема, использует кроме функциональных т.н. условные термы, которые образуют вместе с первыми (функциональными) множество вычислительных термов, если задаем условный терм в виде ( ρ|τ1 | τ2), где ρ - предикатный терм, а τ1 и τ2 – вычисли- тельные термы. n! = n(n-1)! = n(n-1)(n-2)! 5 Указанные формализмы отмечают уровни абстракции языков программирования: ++ если операторные схемы близки к структуре машинной программы ++ то рекурсивные схемы ближе к исходной формулировке задач, подлежащих программирова- нию. Исследования по теоретическому программированию несут в себе отпечаток общематематиче- ских средств, используемых при изучении моделей программы. ++ формально-комбинаторные методы формируют теорию схем программ, которая изучает свой- ства программ, инвариантные относительно выбора интерпретации базовых операций. ++ логические методы изучают способы определения семантики программы, а так же ищут зако- номерность в процессе построения программы. ++ алгебраические методы, отвлекаясь от конкретной структуры программы, концентрируют свое внимание на изучении множеств, возникающих при рассмотрении программы или класса про- грамм. Сложившиеся разделы теоретического программирования охватывают в основном модели по- следовательных вычислений, выполняемых одним активным устройством. Совместная работа машин над общей задачей решается параллельным программированием. Рассмотрим основные подходы при организации вычислений при выполнении последованых программ с памятью. Пример 1. Вычислить x 7 (надо вычислить x 7 , не используя операцию возведения в степень). Возможные три варианта вычислений: Начало вещ x, y, x1, x2, x3, x4, x5, x6; Ввод (x); x2 := x * x; x3 := x2 * x; x4 := x3 * x; x5 := x4 * x; x6 := x5 * x; y := x6 * x; Вывод(y); Конец Пример 2. Вычислить x 7 Начало вещ x, y Ввод(x); y := x * x y := y * x y := y * x y := y * x y := y * x y := y * x Вывод(y); Конец Пример 3. Вычислить x 7 Начало вещ x, y; цел i Ввод(x); y := x * x для i := 1 шаг 1 до 5 цикл y := y * x; Вывод(y); Конец Первый вывод. Задача может быть запрограммирована разными способами: один способ лучше, другие хуже. Второй вывод. Программы могут отличаться друг от друга сильнее и слабее: 1 и 2 ближе чем 1 и 6 3. Третий вывод. Первые две программы настолько похожи, что даже лучше говорить, что это одна и та же программа, только с разными обозначениями промежуточных велечин. Четвертый вывод. Имеет смысл такая проблема: составить программу, используя минимальное количество обозначений. Это даст экономию памяти. При написании программ придерживаются следующих Двух основных принципов: А. Программу надо писать так, чтобы она содержала минимальное количество обозначений. Б. Имея в операторе некоторый результат не следует торопиться вводить для него новое обозна- чение, а посмотреть, есть ли в данный момент «свободная» величина, текущее значение которой больше не потребуется. Рассмотрим следующий пример Пример 4. Вычислить x 59 Начало вещ x, y; цел i Ввод(x); y := x * x для i := 1 шаг 1 до 57 цикл y := y * x; Вывод(y); Конец Но короткая запись программы требует все же 3·57 операций: умножение, изменение i и сравне- ние его с 57. Представим 59 = 32 + 16 + 8 + 2 + 1 x 59 = x 32 x 16 x 8 x 2 x Пример 5. Вычислить x 59 Начало вещ x, y, x2, x4, x8, x16, x32 Ввод(x); x2 := x*x; x4 := x2*x2; x8 := x4*x4; x16 := x8*x8; x32 := x16*x16; y := x * x2; y := y * x8; y := y * x16; y := y * x32; Вывод(y); Конец После шага 3 нам уже не нужна величина x4, поэтому см.пример 6. Пример 6. Вычислить x 59 Начало вещ x, y, x2, x4, x16, x32 Ввод(x); x2 := x*x; x4 := x2*x2; x4 := x4*x4; x16 := x4*x4; x32 := x16*x16; y := x * x2; y := y * x4; y := y * x16; y := y * x32; 7 Вывод(x); Конец; Но это плохо организованная программа, с точки зрения программного кода Пример 7. Вычислить x 59 Начало вещ x, y Ввод(x); y := x * x; x 2 x := x * y; x 3 y := y * y; x 4 y := y * y; x 8 x := x * y; x 11 y := y * y; x 16 x := x * y; x 27 y := y * y; x 32 y := x * y; x 59 Вывод(y); Конец; Мы должны отдавать себе отчет, что мы еще очень далеки от решения общей задачи экономии памяти. У нас всего один принцип Б и то для решения в линейных простых программах. |