Konspekt_lektsiy_SPO_31-8-13


МИНОБРНАУКИ РОССИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
САМАРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра «Вычислительная техника»





А.А.Тихомиров


Конспект лекций
по дисциплине
«Системное программное обеспечение»

























Самара 2012

Системное программное обеспечение

Структура и объем курса
Лекции - 36 часов
Лабораторные работы - 36 часов
Курсовая работа
Самостоятельная работа – 72 часа.
Экзамен 5 семестр
Литература
Основная литература
[ Cкачайте файл, чтобы посмотреть ссылку ][ Cкачайте файл, чтобы посмотреть ссылку ]Современные операционные системы [Текст] : [Пер.с англ.] / Э. Таненбаум. - 2-е изд. - М. ; СПб. ; Нижний Новгород : Питер, 2007. - 1037 с. : ил. - (Классика computer science). - ISBN 978-5-318-002 99-1(в пер.). - ISBN 5-318-00299-4. - ISBN 0-13-031358-0
[ Cкачайте файл, чтобы посмотреть ссылку ] [ Cкачайте файл, чтобы посмотреть ссылку ]Системное программное обеспечение [Текст] : учеб. / А.В.Гордеев, А.Ю.Молчанов. - М. ; СПб. ; Нижний Новгород : Питер, 2003. - 736 с. : ил. - (Учеб.для вузов). - ISBN 5-272-00341-1 (в пер.)
Дополнительная литература
[ Cкачайте файл, чтобы посмотреть ссылку ][ Cкачайте файл, чтобы посмотреть ссылку ]Внутреннее устройство Microsoft Windows [Текст] : windows Server 2003,Windows XP и Windows 2000:[Пер.с англ.] / М.Руссинович, Д.Соломон. - 4-е изд. - М. : Рус.Ред. ; СПб. : Питер, 2008. - 968 с. - (Мастер-класс). - ISBN 978-5-469-011 74-3(в пер.). - ISBN 0-7356-1917-4. - ISBN 978-5-7502-00 85-6
[ Cкачайте файл, чтобы посмотреть ссылку ][ Cкачайте файл, чтобы посмотреть ссылку ] Проектирование и конструирование компиляторов [Текст] : пер.с англ. / Р. Хантер. - М. : Финансы и статистика, 1984. - 232 с. : ил. - ISBN ... :
13 LINK http://WWW.SYSINTERNALS.COM 14www.sysinternals.com15
[ Cкачайте файл, чтобы посмотреть ссылку ]
№ лекции
Номер раздела

Тема лекции и перечень дидактических единиц
Трудоемкость, часов


1
Операционные системы и среды


1

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

2

Тема 1.2. Назначение, функции и структура операционной системы (ОС).
1.2.1. Типы ОС. Функции ОС. Интерфейсы ОС. Пользовательский интерфейс ОС. Интерфейс прикладного программирования (API). Управление ресурсами. Оценка эффективности управления ресур-сами. Счетчики производительности. Использование счетчиков производительности. Защита ресурсов.


2

3

Тема 1.3. Управление временем центрального процессора (ЦП).
1.3.1. Процессы и потоки. Задания. Службы. Демоны. Структуры данных ОС для хранения параметров процессов и потоков. Мониторинг процессов и потоков. Диспетчер задач.

2

4

1.3.2. Создание и завершение процесса. Использование потоков при разработке приложений. Создание потока. Завершение потока. Планирование и диспетчеризация. Дисциплины диспетчеризации. Классы приоритетов.


2


5

1.3.3. Синхронизация взаимодействующих вычислительных пото-ков. Независимые и взаимодействующие потоки. Критические участки. Синхронизация потоков без поддержки операционной системы. Семафорные примитивы Дейкстры.

2

6

1.3.4. Синхронизация потоков средствами операционной системы.
Средства синхронизации потоков. Мьютексы. Функции ожидания одного и нескольких событий. Применение объектов ядра мьютекс. Отказ от объекта мьютекс. Семафоры. События. Мониторы.


2

7

1.3.5. Проблема тупиков. Модель Холта. Условия возникновения тупика. Методы борьбы с тупиками. Функции распознавания тупиков WCT.
2

8

Тема 1.4. Управление памятью
1.4.1. Защищенный режим процессоров Intel и его возможности. Сегментная и страничная организация памяти. Дескрипторные таблицы. Формат дескрипторов. Условие доступа к сегменту. Регистры МП Intel 80286 и Intel 80386, используемые в защищенном режиме.


2

9

1.4.2. Реализация многозадачного режима в защищенном режиме процессоров Intel. Шлюзы задач. Обработка прерываний в защищенном режиме

2

10

1.4.3. Организация виртуальной памяти Управление страничной памятью в ОС MS Windows. Оптимальный размер страницы. Стратегии подкачки и рабочие наборы страниц

2

№ лекции
Номер раздела

Тема лекции и перечень дидактических единиц
Трудоем-кость, часов

11

1.4.4. Разделы в виртуальном адресном пространстве процесса. Адресное пространство процесса ОС MS Windows. Резервирование регионов в адресном пространстве и передача физической памяти региону. Освобождение регионов. Файлы, проецируемые в память. Создание и использование куч. Получение информации о состоянии виртуальной памяти.
2

12

Тема 1.5. Статическое и динамическое связывание. Динамически связываемые библиотеки (Dinamic Linked Libraries – DLL), их создание и использование. Области применения DLL. Основные DLL MS Windows. Достоинства и недостатки DLL. Способы подключения библиотек. Обмен данными между процессами
2

13

Тема 1.6. Структура ОС MS Windows и драйверы режима ядра
1.6.1. Структура ОС MS Windows. Виды драйверов режима ядра. Диспетчер ввода-вывода. Структура драйвера. Средства разработки и отладки драйверов. Пакет DDK.
2

14

1.6.2. Способы установки драйверов в ОС. SCM сервисы. Взаимодействие прикладной программы с драйвером. Функция DEVICEOICONTROL, назначение аргументов и их использование.
2

15

Тема 1.7. Управление вводом-выводом и файловые системы Win32
1.7.1. Эволюция файловых систем ЭВМ. Сравнительный анализ файловых систем FATx и NTFS. Основные свойства NTFS. Обеспечение восстанавливаемости и отказоустойчивости. Структуры данных NTFS. Недостатки NTFS.
2


2
Программирование в операционной среде


16

Тема 2.1. Ассемблеры и макроязыки.
2.1.1. Этапы подготовки программ к выполнению. Программные модули. Ассемблеры. Формат предложения ассемблера. Операнды команд. Директивы. Базы данных ассемблера. Алгоритмы работы ассемблера.

2

17

Тема 2.2. Трансляторы.
2.2.1. Трансляторы: компиляторы и интерпретаторы. Мобильность программного обеспечения. Структура компилятора и интерпретатора. Этапы, фазы и проходы компилятора. Лексический, синтаксический и семантический анализаторы.



2

18

Тема 2.3. Формальные языки и грамматики.
2.3.1. Типы грамматик. Вывод цепочек. Конечный и магазинный автоматы. Распознаватели и преобразователи. Построение автомата по заданной грамматике.
Заключение.


2

Итого:

36 часов


РАЗД. 1. ОПЕРАЦИОННЫЕ СИСТЕМЫ И СРЕДЫ
Введение. Цель и задачи курса
Целью освоения дисциплины «Системное программное обеспечение» является формирование профессиональных компетенций, необходимых для реализации технологической деятельности:
ПК-15, навыков использования операционных систем, сетевых технологий, средств разработки программного интерфейса, применения языков и методов формальных спецификаций, систем управления базами данных;
ПК-16, навыков использования различных технологий разработки программного обеспечения.
Основными задачами преподавания дисциплины являются приобретение в рамках освоения теоретического материала знаний, умений и навыков, характеризующих определенный уровень сформированности целевых компетенций, обеспечивающих изучение основ системного программного обеспечения, а также изучение базовых алгоритмов и структур данных операционных систем и применения языков и методов формальных спецификаций.
Основной задачей преподавания дисциплины в области теоретической деятельности выпускников является получение знаний:
основополагающих понятий теории и практики построения операционных систем;
взаимодействия аппаратных и программных средств на различных уровнях;
внутреннего интерфейса современных операционных систем;
основных управляющих структур данных операционных систем;
элементов формальных грамматик и методов компиляции.

Тема 1.1. Структура программного обеспечения вычислительной системы
Состав системного программного обеспечения (СПО)
В состав СПО входят:
Операционные системы (ОС).
Системы управления файлами.
Виртуальные машины.
Системы программирования.
Утилиты.

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

Рисунок 1-1 – Взаимодействие пользователя, ОС и аппаратуры

Взаимодействие с пользователем.
Управление ресурсами ПК.

Функции ОС
Управление временем ЦП (управление задачами).
Управление памятью.
Управление устройствами.
Управление информацией, хранящейся на внешних устройствах.
Поддержка диалога с пользователем.
Создание интерфейсов – пользовательского интерфейса операционной среды и программного интерфейса приложений.
Защита ресурсов ПК.
Пользовательский интерфейс операционной среды реализован в виде интерфейса командной строки или виде графического интерфейса пользователя (GUI). Возможности интерфейса командной строки шире возможностей GUI, интерфейс GUI интуитивно более понятный и поэтому широко используется непрофессионалами. Интерфейс командной строки используется администраторами локальной сети и администраторами баз данных.
Состав ОС
Ядро, которое управляет временем ЦП и памятью.
Файловая система управляет информацией на внешних устройствах.
Драйверы – управляют устройствами.
Утилиты. Проверка оборудования, системный мониторинг, обслуживание устройств.
Для управления процессами в реальном масштабе времени используют, как правило, ОС реального времени. Системы реального времени – это информационные системы, получающие информацию с датчиков физических величин, установленных на объекте управления и выдающие результаты обработки оператору и (или) на устройства управления объектом.
В некоторых системах управления или информационных системах могут использоваться ОС на базе Windows или Unix c дополнительными модулями. Модули обеспечивают предсказуемость времени выполнения тех задач, которые должны выполняться в заданное время - Т зад. > Т – за счёт ухудшения характеристик выполнения остальных задач.

1.2.1 Типы ОС. Системы реального времени и операционные системы реального времени
Операционные системы в зависимости от количества одновременно выполняемых задач делятся на однозадачные и многозадачные.
Многозадачные ОС делятся на однопользовательские и многопользовательские.
Многопользовательские ОС делятся на офисные, серверные и ОС реального времени.
Системы реального времени делятся на ОС жесткого реального времени и ОС мягкого реального времени.

Обзор современных операционных систем. Перспективные ОС

Современные операционные системы – ОС фирмы Microsoft – MS Windows 2000, XP, Serwer 2003, Windows , операционные системы UNIX и Linux.
Перспективная операционная система - MS Windows 8.

Управление ресурсами. Понятие ресурса. Виды ресурсов
Вычислительный процесс - выполнение отдельной программы с её данными на процессоре.
Ресурсом ПК называется любой объект, который может распределяться при работе системы. Ресурсы могут быть разделяемыми, если несколько процессов могут использовать его одновременно, или параллельно (попеременно) используемыми, или неделимыми.
Виды ресурсов
Время центрального процессора (ЦП) (разделяемый, используется попеременно потоками).
Оперативная память (разделяемый, используется одновременно или параллельно)
Внешние устройства (разделяемый – винчестер; неразделяемый – магнитная лента, стриммер; модем – разделяемый ресурс).
Информационные ресурсы:
Данные на внешних устройствах (файлы).
Программные модули:
Реентерабельные (прерываемые в любой момент);
Повторно входимые – состоящие из секций. Прерывание и повторное вхождение возможно после завершения выполнения секции;
Нереентерабельные. Последовательно исполняемые или выполняемые в режиме последовательной многозадачности. Требует меньше памяти, чем реентерабельные, поскольку локальные данные могут не храниться в стеке.
Состояния вычислительного процесса
Вычислительный процесс может находиться в одном из трёх состояний:
Готовность к выполнению
Выполнение
Ожидание, блокировка.

Рисунок 1- 2 – диаграмма состояний процесса в офисной ОС
Для систем реального времени в наборе состояний задач определено четвёртое состояние: бездействие.










Рисунок 1-3 – диаграмма состояний процесса в ОС реального времени

Реализация управления задачами в ОС
Для управления задачами ОС должна располагать необходимой информацией о каждой задаче. На каждую задачу заводится специальная структура – описатель задачи или дескриптор процесса. Он включает в себя:
идентификатор процесса (PID);
переменную состояния (в каком состоянии находится процесс);
область памяти для сохранения регистров ЦП (контекст задачи);
приоритет процесса;
информацию о ресурсах процесса: открытые файлы, состояние ввода-вывода.

Тема 1.3. Управление временем центрального процессора

1.3.1. Процессы и потоки. Задания
Ранее в MS DOS и Win 3. 1 процесс определялся как экземпляр выполняемой программы. В отличие от MS DOS, процессы в Win 32 инертны, т. е. В Win 32 процесс ничего не выполняет.
Процесс владеет:
4 Гб адресным пространством (при выполнении на 32-х разрядном ЦП).
Файлами.
Одним или несколькими потоками.
Процесс обладает:
базовым классом приоритета;
маркером доступа (access token);
рабочим множеством страниц оперативной памяти.

Процессы
Чтобы процесс что-нибудь выполнил, в нем нужно создать поток (Thread). В принципе, один процесс может содержать несколько потоков и они одновременно используют код в адресном пространстве процесса. Для этого каждый поток должен поток располагать собственным набором регистров процессора, а каждый процесс – как минимум – одним потоком.
Чтобы все эти потоки работали, ОС отводит каждому из них определенное процессорное время (квант времени). Время выдается потокам квантами по кругу (см. рис. 4):
13 SHAPE \* MERGEFORMAT 1415
Рисунок 1- 4 - схема выделения квантов времени потокам

При создании процесса первичный поток создается системой автоматически, далее первичный поток может создавать дополнительные потоки, используя функцию CreateThread (параметры);
Потоки также могут создаваться драйверами режима ядра.
В Win9x, ME - потоки выполняются одним процессором.
В WinNT, 2000, XP Windows Server за потоком может быть закреплен отдельный процессор (процессоров может быть до 4 (32)), тогда потоки действительно выполняются параллельно.
В Win2000 введено понятие задания (JOB).
Задание - объект ядра, обеспечивающий управление одним или несколькими процессами как группой.
Процесс может входить только в одно задание.
Задания необходимы для расширения возможностей управления процессами (потоками) - на сервере в том числе:
1. завершить все потоки задания
2. установить ограничения на потоки задания:
ограничение числа одновременно выполняющихся процессов заданий;
общий лимит на процессорное время (после истечения времени все процессы будут завершены);
индивидуальные лимиты времени на процессорное время пользовательского режима (для каждого процесса);
приоритета для всех потоков;
минимальный и максимальный размер рабочего множества страниц в ОП.
Нити (Fiber) – позволяют программисту управлять выполнением участков программы.
Функции ОС по управлению процессами и потоками.
1. создание и завершение процессов и потоков;
2. получение информации о процессах и потоках;
3. изменение приоритета процессов и потоков;
4. синхронизация потоков.
Процесс может породить другой процесс, используя функцию
CreateProcess();
13 SHAPE \* MERGEFORMAT 1415
Рисунок 5 – порождение процесса

Процесс Пр1порождает процесс Пр2, который в свою очередь порождает процессы Пр3 и Пр4.

Диспетчеризация потоков. Дисциплины диспетчеризации
Известные дисциплины диспетчеризации делятся на:
бесприоритетные (в современных ОС практически не используются);
приоритетные.
Приоритетные дисциплины делятся на дисциплины:
с относительными приоритетами;
с абсолютными приоритетами.
Дисциплины с абсолютными приоритетами делятся на дисциплины:
с фиксированными приоритетами;
с динамическими приоритетами.
В Win32 используется дисциплина диспетчеризации с абсолютными приоритетами – с фиксированными и динамическими приоритетами.

Уровни приоритета в Win32. Классы приоритетов процессов и потоков

Используется 32 уровня приоритета – уровень 31 самый высокий, 0 – самый низкий. Уровни приоритета разбиты на 3 группы (см. рис. 6).
13 SHAPE \* MERGEFORMAT 1415
13 SHAPE \* MERGEFORMAT 1415
Рисунок 1- 6 – группы приоритетов потоков

Приоритет потока равен базовому значению приоритета потока, к которому может быть добавлена динамическая составляющая. Динамическая составляющая добавляется при определенных условиях операционной системой к значениям приоритета потока в интервале от 1 до 14.
Базовый приоритет потока Win32 устанавливается, исходя из класса приоритета его процесса и уровня относительного приоритета.
В Win32 определены следующие классы приоритета процесса:
реального времени – RealTime со значением 24;
высокий – High со значением 13;
выше среднего – Above normal со значением 10;
обычный – Normal со значением 8;
ниже среднего – Below normal со значением 6;
низкий – Idle со значением 4.
В Win32 определены следующие уровни относительного приоритета потока:
Time Critical;
Highest;
Above Normal;
Normal;
Below Normal;
Lowest;
Idle.

Таблица 1. Базовые значения приоритета потоков в Win 32

Относительный приоритет потока
Класс приоритета процесса


Idle(4)
Normal (-8)
High(13)
Real_Time(24)



(-1)фоновый
ст.(0)
Повыш.(+1)



Time Critical
15
15
15
15
15
31

Highest
6
9
10
11
15
26

Above Normal
5
8
9
10
14
25

Normal
4
7
8
9
13
24

Below Normal
3
6
7
8
12
23

Lowest
2
5
6
7
11
22

Idle
1
1
1
1
1
16


Не все значения приоритета могут быть установлены.

Установка базового приоритета потока выполняется в два этапа. На первом этапе с помощью функции Res := SetPriorityClass (Handle, Class) устанавливается базовый класс приоритета процесса. Затем с использованием функции
Res:= SetThreadPrioriry (Handle, Prioritet)
задается базовый приоритет потока.
Рекомендуется всегда проверять возвращаемое значение Res.

Получение и использование процессом ссылок на себя
В Win32 имеется несколько функций, которым необходим описатель процесса. Поток процесса может получить описатель своего процесса, используя вызов функции GetCurrentProcess : Thandle;
Для изменения приоритета выполнения процесса используется функция
SetPriorityClass(GetCurrentProcess, Значение_класса_приоритета);

Мониторинг процессов и потоков. Получение списка процессов, выполняющихся в системе
Задача получения списка выполняющихся в системе процессов является одной из основных при выполнении мониторинга ресурсов, как отдельного ПК, так и ЛВС в целом, поэтому для ее решения разработано значительное количество утилит, имеется встроенное системное средство – диспетчер задач.
Все перечисленные программные средства используют как функции Win32 API (Application Program Interface – прикладной программный интерфейс), так и функции еще одного базового интерфейса, называемого Native API (естественный API). Внешняя часть Native API пользовательского режима содержится в модуле ntdll.dll, «настоящий» интерфейс реализован в ntoskernel.exe – ядре операционной системы NT (NT operation system kernel). Функции Win32 API, как правило, обращаются к функциям Native API, отбрасывая часть полученной от них информации. Поэтому использование функций Native API позволяет получить, вообще говоря, более эффективное ПО.
К функциям Win32 API для получения информации о выполняющихся в системе процессах относятся функции CreateToolhelp32Snapshot(), Process32First(), Process32Next(), Thread32First (), Thread32Next(), Module32First(), Module32Next(), Heap32ListFirst(), Heap32ListNext() и некоторые другие. Самая известная из функций Native API для доступа к содержимому многих важных внутренних структур операционной системы, таких как списки процессов, потоков, дескрипторов, драйверов и т. п. – функция NtQuerySystemInformation ().
Использование функций CreateToolHelp32Snapshot () и Process32xxxx() для получения списка имен процессов
Первый этап получения информации о выполняющихся в системе процессах - получение снимка (snapshot) системы, который содержит информацию о состоянии системы в момент выполнения снимка.
Снимок создается с помощью функции CreateToolhelp32Snapshot (dwFlags, th32ProcessID), первый аргумент определяет, какая информация будет записана в снимок - возможные значения dwFlags приведены в таблице.
Таблица 1
Флаг - dwFlags
Описание

TH32CS_SNAPHEAPLIST
В снимок включается информация о динамически распределяемой памяти указанного процесса

TH32CS_SNAPPROCESS
В снимок включается список процессов, присутствующих в системе

TH32CS_SNAPTHREAD
В снимок включается список потоков

TH32CS_SNAPMODULE
В снимок включается список модулей, принадлежащих указанному процессу

TH32CS_SNAPALL
В снимок включается список куч, процессов, потоков и модулей


Второй аргумент определяет процесс (указанием его идентификатора), информация о котором необходима (если требуется список куч или модулей). В остальных случаях он игнорируется.
Второй этап - извлечение из снимка списка процессов. Для выполнения этой операции служат функции:
BOOL Process32First (HANDLE hSnapshot, LPPROCESSENTRY32 lppe);
BOOL Process32Next (HANDLE hSnapshot, LPPROCESSENTRY32 lppe);
Первый аргумент - хэндл созданного снимка (возвращает функция CreateToolhelp32Snapshot).
Второй аргумент- структура, содержащая 10 полей:
Первое поле этой структуры - dwSize - должно перед вызовом функции содержать размер структуры в байтах - sizeof (PROCESSENTRY32).
Второе поле - cntUsage - содержит число ссылок на процесс, то есть число потоков, которые в настоящий момент используют какие-либо данные процесса.
Третье поле - th32ProcessID - является идентификатором процесса.
Шестое поле - cntThreads - определяет число потоков, принадлежащих процессу.
Седьмое поле - th32ParentProcessID - является идентификатором родительского по отношению к текущему процесса.
Поле pcPriClassBase cодержит базовый приоритет процесса.
Поле szExeFile[MAX_PATH] cодержит имя файла, создавшего процесс.
Для того, чтобы получить информацию о первом процессе в снимке, необходимо вызвать функцию Process32First. В случае успешного завершения функция возвращает TRUE. Для того, чтобы просмотреть все оставшиеся процессы, нужно вызывать функцию Process32Next до тех пор, пока она не возвратит FALSE.

Пример 1. Получить список имен выполняющихся в системе процессов, используя рассмотренные выше функции.
На форме разместить компоненты ListBox, Label и Button. В список директив проекта добавить директиву
#include
Обработчик события OnClick кнопки должен иметь вид:
// получение снимка процессов
HANDLE HS = CreateToolhelp32Snapshot(TH32CS_SNAPPROCESS, 0);
PROCESSENTRY32 P;
ListBox1->Clear();
// задать размер структуры
P.dwSize = sizeof(PROCESSENTRY32);
// получение имен процессов и их запись в ListBox1
if (Process32First(HS, &P))
{
do
{
ListBox1->Items->Add (P.szExeFile);
}
while (Process32Next (HS, &P));
}
// освобождение ресурса – снимка состояния системы
CloseHandle (HS);

1.3.2. Создание и завершение процессов и потоков.
Для создания процесса используются три функции:
WinExec (путь и имя .exe файла’, вид окна приложения);
ExecuteFile (путь и имя файла’,’’,’’, вид окна приложения);
CreateProcess ().
Первая функция - устаревшая, поддерживается для совместимости с Windows 3.1. Вторая функция позволяет запустить приложение, указав имя и тип файла, который должен быть обработан.
Для завершения процесса используются две функции:
1. ExitProcess (код завершения);
2. TerminateProcess (Handle, код завершения).
Первая функция обеспечивает нормальное завершение процесса, вторая должна использоваться для аварийного завершения.
Использование потоков при разработке приложений
Большинство приложений обходятся единственным, первичным потоком.
Использование дополнительных потоков позволяет добиться минимального простоя процессора. За счет чего?
За счет переключения на другой поток во время пауз между вводом символов с клавиатуры;
За счет времени ожидания данных от внешних устройств.
Пример 1. В электронных таблицах нужно пересчитывать данные при изменении пользователем содержимого ячеек. Для этого можно выделить блок расчетов в отдельный поток. Пока пользователь вводит данные - расчет не ведется. Пауза - работает поток более высокого приоритета – выполняется пересчет.
Пример 2. – Текстовый процессор. Дополнительный поток используется для разбивки введенного документа на страницы.
Пример 3. При выполнении операций, отнимающих длительное время (копирование файлов) можно открыть диалоговое окно кнопкой «отмена» (допустим пользователь передумал или копирует не тот файл). Копирование должно выполняться отдельным потоком.
Появление процессоров, поддерживающих гипертрединг (Hyperthreding - многопоточность), и многоядерных процессоров делает многопопочность необходимым условием конкурентоспособности разрабатываемых приложений.

Влияние приоритета потока на время его выполнения
Поток получает время ЦП в соответствии с его приоритетом – чем выше приоритет, тем больше времени он получает боле высокий приоритет потока ещё не означает, что приложение в целом станет работать быстрее. Существенное влияние оказывает загрузка процессора.

1.3.3 Синхронизация взаимодействующих потоков
Независимые и взаимодействующие потоки

Потоки делятся на независимые (параллельные) и взаимодействующие.
Взаимодействовать могу конкурирующие потоки (имеющие доступ к общим переменным) и сотрудничающие потоки (реализующие схему «поставщик-потребитель»).
Пример 1: Два потока одного приоритета увеличивают значение общей переменной global следующим образом:
Поток 1
Поток 2

x:=global
x:=global

x:=x+1
x:=x+1

global:=x
global:=x

Если сначала работает поток 1, потом – 2, то в итоге переменная global увеличится на 2. если произойдет прерывание потока 1, то в итоге переменная global увеличится на 1.
Решения:
1. (global);
2. interlocked (increment(global)).

Критические участки

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

Условный пример: Два потока имеют доступ к одному и тому же файлу.
13 SHAPE \* MERGEFORMAT 1415
Рисунок 1 -7

Поток 1: открывает запись, пишет в поля 1-4, и его квант времени заканчивается.
Поток 2: изменяет поля5-6, записывает изменения.
Поток 1: из буфера пишет в базу, и изменения, сделанные потоком 2, уничтожаются.
Другой, более наглядный и более простой пример: Два потока, переменная global: word; начальное значение переменной равно 100, каждый поток пытается увеличить значение переменной global на 1, следующим образом:
For I: =1 to 10 do
Begin
Sleep(5);
I: =global;
I: =i+1;
запись в ListBox1 I;
Global: =I;
end;
Поток 2 также имеет:
For I; =1 to 10 do
Begin
Sleep (2);
I: =global;
I: =i+1;
запись в ListBox2 I;
Global: =I;
end;
Будет ли в итоге global=120, если потоки стартуют одновременно?

Если поток 1 берет I:=102, прибавляет 1, будет 103, квант истек.
Поток 2 берет I:=102, прибавляет 1, запишет 103, поток 1 запишет 103. в обоих случаях могут быть разные значения, единица потеряна!
Простейшее решение – inc(global).

Interlocked – функции.
Для увеличения или уменьшения на единицу глобальных переменных типа long:
InterlockedIncrement(I);
InterlockedDecrement(I);
Возвращают: 0 – при переходе через 1; положительное число, если результат больше 0; отрицательное число, если результат меньше 0.
Обмен переменными:
InterlockedExchange (LTarget, LValue);
Обеспечивает правильное увеличение (уменьшение) глобальной переменной типа longint без использования критических секций или мьютексов.
Общее решение: использование средств синхронизации операционной системы:
- критических секций;
- мьютексов (Mutex – mutually exclusive – взаимоисключающие);
- семафоров.
Требования к средствам доступа к критическим участкам:
1. В любой момент времени только один поток может находиться в критическом участке;
2. Ни один поток не должен находиться в критическом участке бесконечно долго;
3. Ни один поток не должен ждать бесконечно долго входа в критический участок;
4. Поток завершившийся (аварийно) в критическом участке, не должен блокировать вход в критический участок для других потоков.
Пример 2: Сотрудничающие потоки – задача «поставщик-потребитель».
Поток - поставщик создает порции данных для передачи (через линии связи), а поток - потребитель передает их. Для хранения сообщений используется совокупность (пул) буферов на одно сообщение.
13 SHAPE \* MERGEFORMAT 1415
Рисунок 1 – 8 - Взаимодействие поставщика и потребителя

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

Средства синхронизации параллельных потоков без поддержки ОС

Чисто программное решение без поддержки ОС. Достоинства, недостатки

Чисто программное решение использует цикл активного ожидания –
While < условие > do;
Два варианта – использование признака «критический участок занят»
и поочередный вход в критический участок
Первый вариант некорректен, второй требует примерно одинаковой скорости выполнения потоков.
Достоинства – простота, независимость от операционной системы.
Недостатки – потеря времени в цикле активного ожидания, инверсия приоритетов
Семафорные примитивы Дейкстры

Семафор – переменная специального, типа доступная для выполнения операций
P(S) - открыть
V(S) - закрыть
Смысл операции P(S) состоит
P(S) – S>0 => S:=S-1 и поток имеет возможность продолжится
Иначе – (S(0) - остановить поток (поставить в очередь)
V(S) –если S(0 – поместить один ожидающих потоков в очередь готовности.
S:=S-1
InitSem (S, нач. знач.) – S:= нач значение

Решение проблемы критических участков с помощью семафорных примитивов Дейкстры
InitSem (S,1)
Поток1
WhileTrue do
Begin
P(S); S=0
Критический участок
V(S); S=1
End;
Поток2
WhileTrue do
Begin
P(S)
Критический участок
V(S)
End;

1.3.4 Синхронизации потоков средствами операционной системы

Средства синхронизации потоков.
Это средства ОС Windows, которые являются общими для всех потоков в системе и используются для координирования доступа к ресурсам. Их можно разделить на средства синхронизации пользовательского режима и средства синхронизации режима ядра.
Средство синхронизации пользовательского режима – критические секции.
Средства синхронизации рассмотренной ранее критической секции и Interlocted – функции – работают весьма быстро, поскольку процессор при их использовании переводится в режим ядра на непродолжительное время, однако их возможности ограничены. Другие средства синхронизации используют режим ядра (каждый переход в режим ядра занимает около1000 тактов ЦП) и поэтому работают медленнее, чем средства синхронизации последовательного режима.
Критическая секция должна быть описана и инициализирована вызовом функции InitializeCriticalSection (Sect1).
Перед операциями с общими переменными в искомом потоке помещается вызов функции: EnterCriticalSection (Sect1);
//операции с общими переменными
LeaveCriticalSection (Sect1);
Если поток 1 пытается войти в критическую секцию и она не занята, то ему это позволяется функцией EnterCriticalSection (Sect1), ставится флаг занятости, тогда поток 2 при попытке сделать то же самое переводится в состояние ожидания (Sleep) до тех пор, пока поток 1 не выполнит LeaveCriticalSection (Sect1).
После завершения работы с критической секцией ее необходимо удалить с помощью вызова функции DeleteCriticalSection (Sect1).
Функция TryEnterCriticalSection(Sect1) –проверяет, занята ли критическая секция в данный момент, поток может заняться чем-либо другим, ожидая доступ к критическому участку.

Объекты ядра, использующиеся для синхронизации потоков.
Mutex (Mutualli Exclusive – взаимное исключение)
Semaphore - семафор.
Events – событие
Process – процесс
Thread – поток
JOB – задания
File – файл
Консольный ввод/вывод
Notification –уведомление

Создание объекта ядра **** выполняется с помощью функций вида
Create **** (атрибут безопасности, )

Мьютексы
Это средство синхронизации, позволяющее синхронизировать 2 и более параллельных потоков с критическими участками одного или нескольких процессов.
Создание мьютекса
CreateMutex (nil, initOwnes - начальный владелец, boolean true: владелец-поток который создал его, False: владелец 1-й обратившийся поток, имя) : Thandle
Используется для синхронизации потоков, принадлежащих разным процессам.
Если 2-й параметр true, то данный поток становится владельцем мьютекса, объект mutex будет занят. Любой другой поток будет приостановлен, пока первый поток не освободит его.
Передача false показывает что mutex не принадлежит ни одному потоку, и поэтому «рождается свободным». Любой поток может захватить его и продолжить его выполнение. Мьютексы способны синхронизировать потоки, выполняемые в разных процессах.

Функции ожидания одного или нескольких событий

Функции - WaitForSingleObject() и WaitForMultipleObjects () - назначение и аргументы

Вызов функции WaitForSingleObject () оказывает влияние на некоторые объекта ядра.
Пример 1
Поток_1

WaitForSingleObject(Handle Process, ) либо Handle Thread, .)
Если в момент выполнения потоком_1 процесс Handle Process (или поток Handle Thread) выполняются, поток_1 будет ждать, пока процесс или поток Thread завершится. Как только это произойдет, объект Handle Process, Handle Thread получит статус свободного и поток_1 продолжит работу.

Пример 2
В этом примере состояние объектов, указанных в функции WaitForSingleObject изменяется в момент вызова функции.
Поток_1

если
свободен ––> WaitForSingleObject(Handle_Mutex, infinite) (или событие с автоматическим сбросом )
mutex

если не свободен – стоп.
При вызове функции WaitForSingleObject (), если объект свободен, продолжает выполнение, а состояние объект изменится на противоположное (остальные процессы, в которых используется WaitForSingleObject() c этим Mutex будут ждать).
В случае функции WaitForMultipleObjects (когда 3-й параметр равен TRUE) – объекты указанные в массиве, переустанавливаются в занятое состояние до тех пор, пока не освобождаются все указанные объекты (сначала дождаться освобождения всех, затем устанавливать в занятое). Это сделано, чтобы избежать тупиков.
Это относится к функции WaitForMultipleObjects.
(если параметр равен TRUE), лишь одного объекта (если FALSE). Четвертый параметр – аналогичен последнему параметру предыдущей функции. Возвращаемое значение – индекс описателя в массиве описателей того объекта, который освободился (если освободилось несколько, то первого из освободившихся).
102Н – ни один из объектов в течение заданного времени не освободился.

Пример 3
Поток_1 Поток_2

ждать mutex A ждать mutex A,
и mutex B mutex B

Допустим, поток_3 освободил mutex A. Тогда ОС передает права на него потоку_1. Затем 3-й поток освободит mutex B.
Система передает права на него потоку_2.
Теперь поток_1 и поток_2 друг друга – 1-й владеет mutex’ом A, но не может выполнятся и освободить его, поток_2 никогда не освододит mutex A. Поток_2 – владеет B, но никогда не освободит его.
Это пример тупика двух процессов.
Для борьбы с тупиками функция WaitForMultipleObjects никогда не восстанавливает занятое состояние объектов, пока все из числа указанных объектов не освободятся.

Применение Обектов mutex вместо критических критических секций.
Вместо критических секции используется Mutex.
1) создать mutex
HM:=CreateMutex(nil, False, nil);
2) создать поток
Th1:=CreateTHread(nil, .);
Th2:= CreateTHread(nil, );
Перед критическим участком каждого потока вызвать функцию
WaitForSingleObject (HM, Infinite) (если HM свободен, он переводится в занятое состояние, а поток входит в критический участок). В конце критического участка необходимо перевести mutex в свободное состояние.
ReleaseMutex (Hmutex):boolean; Эта функция переводит объект mutex из занятого состояния в свободное (аналогично LeaveCriticalSection ).
Функция ReleaseMutex воздействует на mutex, только если поток, вызвавший ее, владеет этим объектом.

Отказ от объекта mutex
Объект mutex отличается от других синхронизирующих объектов ядра тем, что вызвавшему его потоку передаются права на владения им. Другие синхронизирующие объекты могут быть либо свободны, либо заняты. А объекты mutex способны еще и запомнить, какому потоку они принадлежат.
В случае аварийного завершения потока, владеющего объектом Mutex, Mutex никогда не освободить, так как никакой другой поток не сможет освободить его вызовом функции RealeseMutex. ОС не терпит подобных ситуаций и переводит mutex в свободное состояние (для предотвращения блокировки оставшихся потоков). Это действие называется отказ от мьютекса.
С объектами mutex связан счетчик числа их владельцев. Поэтому, если поток вызывает WaitForSingleObject для того объекта mutex, который уже принадлежит ему, он сразу получит доступ к защищенным данным (благодаря счетчику система определяет, что поток уже владеет объектом mutex). При каждом вызове WaitForSingleObject потоком – владельцем объекта mutex – этот счетчик увеличивается на 1. Поэтому для освобождения mutex потоку придется соответствующее число раз вызывать функцию RealeseMutex.
Семафоры
Объекты ядра “семафор” используются для учета ресурсов. При запросе у семафора ресурса ОС проверяет, свободен ли данный ресурс, и если свободен, уменьшает счетчик доступных ресурсов, не давая вмешиваться другому потоку. Только после этого система разрешает другому потоку запрашивать какой-либо ресурс. Например, у ПК установлено три последовательных порта, значит одновременно или могут воспользоваться не более чем три потока ( порт может быть закреплен за одним потоком). Для выделения портов необходимо создать семафор со счетчиком, равным 3. Семафор считается свободным, если его счетчик ресурсов больше 0, и занятым, если счетчик равен 0. При каждом вызове из потока функции WaitForSingleObject с передачей ей описателя семафора система проверяет, больше ли нуля счетчик ресурсов у данного семафора. Если да, то счетчик ресурсов уменьшается на 1, выполнение потока продолжается. Если счетчик ресурсов=0, поток должен ждать освобождения ресурса.
В отличие от mutex, семафоры не передаются во владение какому-либо потоку.
Семафор создается функцией
CreateSemafore (nil //атрибуты, InitSem, MaxSem //integer, LpszSemName // Имя семафора для ссылок на семафор из других процессов): Thandle;
Для случая использования 3 портов семафор создается функцией
Hs := CreateSemafore (nil, 3, 3, ’);
.– все 3 порты свободны.
Освобождение семафора – увеличение счетчика ресурсов – выполняет функция
ReleaseSemafore (HandleSem, CRelease //количество возвращаемых ресурсов, lpPrevios):boolean;
Последний параметр – указывает на переменную integer, в которую заносится значение счетчика ресурсов, предшествовавшему тому, что получается после увеличения его на CRelease. Можно передавать nil.
Получить содержимое счетчика семафора, не измерив его значения, нельзя.

Решение задачи поставщик – потребитель с помощью операций P(S) и V(S)

InitSem (Sсв, N)
InitSem (Sзап, 0)
InitSem (Sвз, 1)
Поставщик: WhileTrue do
Begin
Создать сообщение
P(Sсв)
P(Sвз)
Послать сообщение
V(Sсв)
V(Sвз)
End.
Потребитель: WhileTrue do
Begin
Создать сообщение
P(Sзап)
P(Sвз)
Послать сообщение
V(Sсв)
V(Sвз)
End.
Семафоры Sсв, Sзап используется как счетчики свободных и занятых буферов т.е. являются общими переменными для обоих потоков. Поэтому они должны быть защищены двоичным семафором Sвз. Если поставщик проверил P(Sсв) и находится на семафоре Sсв=0, он блокируется на нем. Если потребитель проверил P(Sзап) и находит при этом Sзап.=0, он блокируется на семафоре Sзап.
2 семафора предназначен для возможности блокировки 2 потоков. 3-й семафор Sвз обеспечивает неделимость операций.
.

События - Event.
Самые примитивные средства синхронизации – только оповещают об окончании какой-либо операции. Используются два типа объектов “события” :
событие со сбросом вручную (manual-reset-events);
событие с автоматическим сбросом (auto-reset-events).
Типичная схема использования событий – 1 поток выполняет некоторую подготовительную операцию (например, считывание данных из файла в буфер), а затем сигнализирует другому потоку (или нескольким потокам), что они могут продолжить работу (например, обработать считанные данные).



1.3.5. Проблема тупиков и методы борьбы с тупиками

Понятие тупика двух процессов

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

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

Рисунок 1-9 запрос 2 х единиц R1

Дуга, соединяющая ресурс и процесс – показывает выделение ресурса процессу.

Рисунок 1-10 - P2 владеет одной единицей ресурса R2

Пример модели Холта.


Рисунок 1-11 –модель Холта граф используемых ресурсов

В некоторый момент времени P1 запрашивает 2 единицы R1 и запрашивает 1 единицу R2. P2 – запрашивает 1 единицу R2 и владеет 2 единицами R1.
Каждому процессу нужны все требуемые ресурсы, чтобы он мог продолжить выполнение. Предположим, что процесс Р1 получил бы теперь запрошенную им единицу R2. Если удовлетворить запрос Р1 на ресурс R2 это может привести к тупиковой ситуации. P1 не сможет продолжиться до тех пор, пока Р2 не освободит единицу ресурса R1, а процесс Р2 не сможет продолжиться до тех пор, пока Р1 не освободит единицу R2.
Если не удовлетворить Р1 – отдать Р2 – он завершится.
Пример тупика двух конкурирующих процессов.

Процесс_1 Процесс_2
* *
* *
1: P(S2);
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
4: V(S2); 8: V(S2);
* *
Возникновение тупика возможно, Если выполнена последовательность 1..5 – теперь тупик неизбежен.

Условия возникновения тупика

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

Методы борьбы с тупиками

Имеются 3 метода:
предотвращение тупика (самый дорогой);
обход тупика;
распознавание тупика с последующим восстановлением.

Предотвращение тупика.
Дисциплина, предотвращающая тупик, должна гарантировать, что не может возникнуть какое-либо из четырех условий, необходимых для его наступления.
1 условие – условие взаимного исключения – можно устранить путем разрешения неограниченного разделения ресурсов. Это удобно для повторно-входимых программ и ряда драйверов, но совершенно неприемлемо к совместно используемым переменным в критических интервалах.
2 условие – условие ожидания - можно устранить, предварительно выделяя ресурсы. Процесс может начать исполнение, только получив все ресурсы. Не всегда заранее известны все ресурсы, необходимые процессу.
3 условие – условие отсутствия перераспределения – можно исключить, позволяя операционной системе отнимать у процесса ресурсы. Для этого в операционной системе должен быть предусмотрен механизм запоминания состояния процесса с целью последующего восстановления.
4 условие – условие кругового ожидания – исключить можно, предотвращая образование цепи запросов. Это можно сделать, если ресурсам приписать определенные номера. Все запросы на ресурсы должны выполняться в порядке возрастания номеров ресурсов. Если запросы следуют в порядке возрастания номеров, - 1,2,3,4 – то они удовлетворяются по мере того, как ресурсы становятся доступными.
Процесс, имеющий ресурс i-го уровня, в дальнейшем может потребовать только ресурсы i+1-го уровня. После того, как процесс получил, а потом освободил ресурсы данного уровня, он может запросить ресурсы на том же самом уровне. Освободить процесс i-го уровня можно только после освобождения всех ресурсов на более высоких уровнях.
Например, имеются процессы P1, P2, ресурсы R1, R2; уровни R1 – 1, R2 – 2. Если P1 получил R1, он может получить R2. Но P2 не может получить R2, пока не получит R1. Т.о. создание замкнутой цепи невозможно. Иерархическое выделение ресурсов часто не дает никакого выигрыша, если порядок использования ресурсов, определенный в описании процессов, отличается от порядка уровней иерархии. В этом случае ресурсы будут использоваться крайне неэффективно.
В целом стратегия предотвращения тупиков – это дорогое решение проблемы, и оно используется нечасто.

2. Обход тупиков.
Обход тупика – это запрет входа в опасное состояние (такое состояние, которое может привести к тупику).
Для обхода тупика перед выделением ресурса необходимо проверить, не приводит ли выделение ресурсов к опасному состоянию, и если да – ресурс выделять нельзя.
Необходимо иметь информацию о максимальных потребностях процессов в ресурсах.


Ресурсы должны быть одного типа.
Например, имеем 6 единиц ресурса и 2 процесса


Имеет
Требует
Максимальная потребность
“Остаток” потребностей

Р1
1
3
5
1

Р2
2
2
4
0


3
Резерв-3
9>6


возможны тупики!
1. Удовлетворение запроса Р1 – приведет к продолжению его выполнения – но состояние будет опасным – если он запросит еще – то ни Р1, ни Р2 не будут выполняться.
2. Удовлетворение запроса Р2 – он завершится.
Обход тупиков – это процесс определения, для каждого требования (предполагается, что требование удовлетворено), будет ли полученное состояние системы безопасным. Задача решается с помощью алгоритма банкира Дейкстры (практически не используется).
Его ограничения:
количество ресурсов в системе должно быть постоянным;
необходимо заранее указывать потребности в ресурсах;
число работающих процессов должно оставаться постоянным.

3. Распознавание с последующим восстановлением.
Данный метод основан на распознавании тупика и принудительном освобождении всех ресурсов попавших в тупик процессов. Обнаружение тупика возможно с помощью графа повторно используемых ресурсов (модель Холта).

Тема 1.4 Управление памятью

Защищенный режим процессоров Intel и его возможности
Защищенный режим появился в МП Intel 80286. Цели создания:
защита программ и данных в ОП от непреднамеренного изменения;
обеспечение доступа ко всей ОП;
поддержка виртуальной памяти;
аппаратная поддержка многозадачности.

Адресация ОП в защищенном режиме.(МП i 80286)

Рисунок 1-12 – формат селектор сегмента
Размер сегмента составляет 216 байт.

Сегментная и страничная организация памяти

Сегментная адресация. Достоинства – размер сегмента в точности равен размеру данных (отсутствует внутренняя фрагментация). Недостаток – при размещении очередного сегмента в свободном месте ОП возникает внешняя фрагментация.
Борьба – перемещение сегментов в ОП (время!). При дорогой ОП – это разумный способ адресации.
Альтернатива : страничная адресация :
Есть внутренняя фрагментация, нет внешней (используется в МП Intel 386 и выше).
Сегмент характеризуется:
базовым адресом;
размером;
допустимыми операциями (чтение, запись);
направлением изменения адресов.

Дескрипторные таблицы (ДТ).

Обращение к ОП в защищенном режиме выполняется через дескрипторные таблицы: одна GDT (единая глобальная DТ) и несколько локальных LDT. В любой момент времени возможно обращение либо к GDT, либо к LDT (бит Т – выбор таблицы)

Рисунок 1-13 -схема формирования физического адреса в защищенном режиме

База – 3 байта; 224=220*16=16 Мб.

Формат дескриптора 286.

Рисунок 1-14 –формат байта доступа
Бит присутствия Р (наличие сегмента в ОП) – если обращение к сегменту, которого нет (поддержка виртуальной памяти) в ОП – он загружается. Проблема – найти свободное место – какой-то сегмент нужно удалить. Для этого используется бит А – access. Он устанавливается в 1 при каждом обращении к сегменту. Сброс в 0 – с заданным периодом ~20мс программно. Те сегменты, у которых при необходимости удаления из ОП в бите А находится 0 – не использовались в последнее время и удаляются в первую очередь – алгоритм LRU.
R – возможность чтения кода.
С – бит подчинения.
W – возможность записи в сегмент.
ED – данные/стек – направление изменения адресов.


Вводятся 4 уровня привилегий: 0, 1, 2, 3. Самый высокий – 0, низкий – 3 :
RPL – запрашиваемый уровень привилегий (из селектора).
DPL – уровень привилегий дескриптора.
CPL – текущий уровень.
После запуска программы
CPL:=DPL ее сегмента кода, если С=0.

Формат дескриптора МП 386

1)Размер слова – 32 бита, адресуемая ОП – 232 – 4Гб, размер сегмента - 232 Гб.
2)Должна обеспечиваться совместимость с 286.

Рисунок 1-15 –формат селектора сегмента в защищенном режиме

База – 4 байта (4Гб = 232)
Размер 220 байт – то 1 Мб (макс).
Все 0 слева – то 216
4 бита поля доступа:
G – размер сегмента (G=0 – в байтах, G=1 – в страницах по 212 байт).
Тогда максимальный размер сегмента 220 *212 =232 .
Теперь, если размер сегмента = 232 , то есть 4Гб – сегментной адресации нет, нет и защиты. В этом случае должна использоваться страничная адресация памяти.

Условие доступа программы к сегменту

Доступ разрешен, если max(CPL, DPL) <= DPL.


Для чего используется RPL ?
4 кольца защиты.
Программа 3 кольца цель – разрушать данные 2-го кольца. Непосредственно этого сделать нельзя – CPL=3? DPL-2. Можно обратиться к 1,0 кольцу, а адрес возврата результата указать во 2-м кольце. При использовании RPL программа 0,1 кольца проверит адрес возврата и найдет RPL=3.
Новая команда ARPL(RPL1,RPL2)->max RPL должна использоваться привилегированной программой для проверки и установки поля RPL всех селекторов для возвращаемых программой результатов.
Возвращается результат в кольцо 2, RPL=2; RPL из адреса возврата = 3. max=3. Запись по условию max(CPL,RPL)<=DPL не производится, т.к. условие 3<=2 не выполняется.

Адресация в МП 386.
Поддерживает режим 286 – сегментная адресация.
Новый режим – режим страничной адресации 32-х разрядной.
Плоская модель памяти – сегмент = 232 байта – размер, базовый адрес = 0.
Нет дескрипторов сегментов. Задача состоит из 1 единственного сегмента, которые, в свою очередь, разбит на страницы.

Новые регистры МП Intel 80286 и Intel 80386

1. Теневые регистры
2. Регистры GDT и IDT (база и размер)
3. Отладочные и управляющие регистры МП 80386.

Метод Родена

Метод Родена – средство использования ОП размером более 1 Мбайт под управлением ОС MS DOS

1.4.2. Реализация многозадачного режима в защищенном режиме процессоров фирмы Intel

Реализация защиты ОС от прикладных программ
Защита ОС от разрушения требует наложения на прикладные программы трех типов ограничений:
обычным программам запрещается выполнять некоторые команды;
обычным программам должны быть недоступны некоторые сегменты, досупные ОС;
получение привилегий ОС должно быть возможным только входом в нее в определенных точках входа.
Возможны 2 способа реализации защиты ОС :
работа процессора в состояниях супервизор-задача:
вызов процедур привилегированного кольца.
1 способ – при необходимости получения услуг от ОС(ввод-вывод) прикладная программа выполняет команду SVC . При этом процессор переключается в режим супервизор. Недостаток – время переключения задач в 7 раз больше врмени вызова процедуры, поэтому в МП Intel используется и второй метод – вызов процедур:
Шлюзы вызова
Для вызова процедур ОС в определенных точках применяются шлюзы вызова. Хранятся в GDT, имеют формат дескриптора

Рисунок 1 – 16 – формат шлюза вызова
Системные и прикладные программы имеют раздельные стеки, при вызове сист программы выполняется перепись n слов из стека прикладной программы в стек системной процедуры.
Вызовы из 0 кольца процедер 3 кольца(из более прив менее прив) запрещены.
Аппаратная поддержка многозадачности.
При переключении задач необходимо сохранение текущего состояния задачи – для этого служит TSS – Task Status Segment. (сохранение регистров ЦП). Имеется регистр задачи TSS.
Для переключения на задачу необходимо в регистр TSS записать селектор TSS.

Шлюзы задач

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

Рисунок 1-17 –формат шлюза задачи


Аппаратная поддержка многозадачности

Многозадачность поддерживается с помощью переключения с одной задачи на другую. (Задача - это поток, время выделяется потокам).
С каждым потоком связывается сегмент памяти, содержащий информацию для запуска и остановки. Сегмент TSS (Task Status Segment).
Регистр задачи – 16-ти разрядный регистр, в котором содержится сегмент TSS.

GDT

дескриптор TSS
Селектор TSS


Структура TSS:

Селектор вызвавшей задачи

Стек кольца 0 (указатель начала)

Стек кольца 1

Стек кольца 2

Регистры ЦП

Регистры LTD

Дополнительные параметры


Рисунок 1-18 – структура TSS
Стек кольца 0,1,2- указатель на начало стека.
Регистр задачи: селектор текущей задачи (регистр TR)

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

1024


CS:IP

Номер
Прерывания 0
Seg off

Рисунок 1-19 схема обработки прерываний в реальном режиме
Пользователь легко может изменить содержимое таблицы векторов и прерываний – нарушение работы ОС (DOS). Серьёзный недостаток!

Обработка прерываний в защищенном режиме
В защищенном режиме – система прерываний имеет дело не с таблицей векторов прерываний, а с таблицей дескрипторов прерываний (IDT – interrupt descriptor table) – доступ к содержимому IDT из пользовательских программ невозможен.
47 IDTR 0
адрес
Размер


Рисунок 1-20 – структура регистра IDTR

Содержимое таблицы IDT:
шлюзы прерываний (interrupt gate)
шлюзы спец. прерываний (trap gate)
шлюзы задач (task gate)
При возникновении прерывания (если они разрешены) – действия ЦП определяются дескриптором; определяемым номером прерывания
Шлюз задачи – выполняет прерывание задач и смену TSS. Обработка выполняется медленнее.
Необходимость в подобном переключении возникает, если, например, разрушен TSS текущей задачи.
Так же как и в реальном режиме, все прерывания защищенного режима имеют свои номера, причем их общее количество не должно превышать 256. В реальном режиме процессор при регистрации прерывания обращается к таблице векторов прерываний, находящейся всегда в самом начале памяти и содержащей двухсловные адреса обработчиков прерываний. В защищенном режиме аналогом таблицы векторов прерывании является таблица дескрипторов прерываний (IDT от Interrupt Descriptor Table), которую создает операционная система защищенного режима. Таблица IDT содержит дескрипторы обработчиков прерываний, в которые, в частности, входят их адреса.
Если в таблицах дескрипторов памяти (LDT и GDT) находятся дескрипторы сегментов программы, то таблица дескрипторов прерываний 1DT состоит из дескрипторов другого вида, которые называются шлюзами (вентилями). Через шлюзы осуществляется доступ к обработчикам прерываний и исключений. Шлюз, как и дескриптор памяти, занимает 8 байт и в него входит полный адрес (16-разрядный селектор и 32-разрядное смещение) обработчика данного прерывания.
Процессор, зарегистрировав то или иное исключение, сохраняет в стеке содержимое расширенного регистра флагов, селектор сегмента команд, смешение точки возврата, а также (в некоторых случаях) 32-битовый код ошибки. Таким образом, в отличие от реального режима, где в результате прерывания стек смещается на 3 слова, в - защищенном режиме в стек заносятся 3 или даже 4 двойных слова. Код ошибки, если он есть, должен быть снят со стека обработчиком соответствующего исключения.
Сохранив вектор прерванного процесса, процессор по номеру вектора извлекает из IDT шлюз, определяет адрес обработчика и передает ему управление. Обработчик заканчивается командой iret, возвращающей управление в прерванную программу.

Различные устройства компьютера (таймер» клавиатура и др.) сигнализируют о необходимости программного вмешательства в их работу с помощью сигнала прерывания, который, пройдя через контроллер прерываний, поступает на вход 1NT микропроцессора и инициирует в нем выполнение процедуры прерывания.
В состав этой процедуры входит, в частности, чтение номера вектора, устанавливаемого контроллером прерываний на шине данных компьютера. При этом контроллер прерываний формирует передаваемый в процессор номер вектора путем сложения базового номера, хранящегося п контроллере, с номером линии, по которой поступил запрос от устройства. Номер базового вектора (в принципе в диапазоне 0..255) устанавливается в процессе программной инициализации контроллера. Поскольку в защищенном режиме векторы 0...31 зарезервированы за исключениями, базовые векторы контроллеров прерываний должны быть расположены в диапазоне 32...255.
Нарушения в работе программы, приводящие к исключениям, могут иметь разную природу и разные возможности исправления в процессе выполнения программы. В соответствии с этим исключения подразделяются на 3 класса: нарушения, ловушки и аварии.
Нарушение, или отказ, (fault) - это исключение, фиксируемое еще до выполнения команды или в процессе ее выполнения. Типичными примерами нарушений являются адресация за установленной границей сегмента или обращение к отсутствующему дескриптору. При обработке нарушения процессор сохраняет в стеке адрес той команды, выполнение которой привело к исключению. При этом предполагается, что в обработчике нарушения его причина будет ликвидирована, после чего команда iret вернет управление на ту же, еще не выполненную команду. Таким образом, сам механизм обработки нарушений предполагает восстановление этого программного сбоя.
Ловушка (trap) обрабатывается процессором после выполнения команды, вызвавшей это исключение, и в стеке сохраняется адрес не этой, а следующей команды. Таким образом, после возврата из обработчика ловушки выполняется не команда, инициировавшая исключение, а следующая за ней команда программы. К ловушкам относятся все команды программных прерываний int.
Авария, или выход из процесса, (abort) является следствием серьезных невосстановимых ошибок, например обнаружение в системных таблицах неразрешенных или несовместимых значений. Адрес, сохраняемый в стеке, не позволяет локализовать вызвавшую исключение команду, и восстановление программы не предполагается. Обычно аварии требуют перезагрузки системы.
По-другому обстоит дело в 32-разрядных приложениях. В таких приложениях используется модель плоской памяти, в которой все сегменты имеют размер 4 Гбайт. В этом случае нельзя выйти за пределы сегмента; однако программе реально выделяется в оперативной памяти (в процессе отображения линейных адресов на физические) лишь столько места, сколько она фактически занимает. Выход за пределы объявленного в программе массива приведет к попытке обращения к ячейке оперативной памяти, находящейся за пределами адресов, отображенных на линейное пространство программы. В этом случае будет сформировано страничное нарушение.
Режимы работы МП 386
Реальный
Защищенный 286
Защищенный 386
V86 (можно выполнить несколько реальных режимов)
Системный S, или SMM, или ICE – предназначен для отладки аппаратуры и ПО.
Системный режим
Это специальный режим, предназначенный для системных функций (например, перевод всей системы в состояние с пониженным энергопотреблением).
S – режим не используется прикладными программами.
Особенности S – режима.
Вход и выход в него являются прозрачными для операционной системы и приложений. Когда процессор переключается в S – режим (аппаратно, при получении сигнала SMI по линии SMI или сообщения SMI по шине APIC – SMI -прерывание, работающее независимо от механизма обработки прерываний, SMI имеет приоритет перед NMI и маскируемыми прерываниями, и запрещ. в S – режиме).Он сохраняет текущий контекст и переходит к выполнению кода, находящегося в специальной памяти SHRAM. Для завершения работы в S – режиме необходимо выполнить команду RSM.
Функционирование процессора в S – режиме похоже на R (реальный) режим, но нет уровней привилегий и преобразования адресов. S – код может адресовать до 4Гб памяти, выполнять операции ввода/вывода и работы с прерываниями.

Reset
or
PC=0
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
· SMI



Рисунок 1- 21 – схема переключения режимов

Организация виртуальной памяти

Адреса памяти, формируемые программой, называемые логическими адресами (или виртуальными адресами) образуют виртуальное адресное пространство.
В ОС Windows каждый процесс имеет собственное виртуальное адресное пространство размером 4 Гб
После преобразования виртуального адреса в линейный полученный адрес преобразуется диспетчером памяти Memory Manadgement Unit - MMU в физический адрес страничной памяти.

13 SHAPE \* MERGEFORMAT 1415

Рисунок 1- 22 преобразование линейного адреса в физический

Для 16 разрядного виртуального адреса виртуальное адресное пространство имеет размер 64 Кбайт. Если размер установленной физической памяти равен 32 Кбайт и размер страницы равен 4 Кбайт, схема преобразования виртуального адреса в физический может быть представлена в виде, показанном на рис. 1-23

13 SHAPE \* MERGEFORMAT 1415
Рисунок 1 – 23 схема страничного преобразования

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

Управление страничной памятью в ОС MS Windows

Схема преобразования логического адреса (из программы) в физический адрес основной памяти в МП Intel 80386 (и в последующих моделях).


Линейный адрес
логич. адрес физич. адрес






Рисунок 1-24 – схема преобразования логического адреса в физический
Линейный адрес

31 22 21 12 11 0
Каталог страниц
Таблица стр.
Смещение

10 10 12

32 PDE 32


Эл-т каталога





эл-т данных




20 32 PTE


эл-т таблицы



32
CR3



CR3 – управляющий регистр – содержит базовый адрес таб. кат.
Рисунок 1-25 – схема преобразования линейного адреса в физический

Каждый процесс имеет свое адресное пространство, свой адрес в CR3 и соответственно, свой каталог.

Элемент TC(дескриптор страницы):

31 12 11 10 9 8 7 6 5 4 3 2 1 0
адрес TG
исп. ОС
0
0

А

U/S
Р/W
Р


U/S – User/sustem (super visor)
A – Access
Рисунок 1-26 –формат дескриптора страницы

Оптимальный размер страницы

С увеличением размера страницы увеличиваются потери памяти на внутреннюю фрагментацию, которая равна
p/2, где p – размер страницы.
С уменьшением размера страницы увеличивается количество страниц, необходимых для хранения некоторого сегмента размера S
Sq/p , где q – размер описателя страницы
Для нахождения оптимального размера страницы памяти, при котором потери памяти минимальны, необходимо найти минимум выражения
p/2 + Sq/p

Стратегии подкачки и рабочие наборы страниц

Стратегии подкачки должны обеспечить выбор страницы памяти, содержимое которой должно быть заменено при нехватке места для размещения новой страницы.
1. Оптимальный алгоритм реализовать нельзя – невозможно заранее определить, к каким страницам может произойти обращение процесса в будущем.
2. Алгоритм FIFO – удаляется страница, первой загруженная в ОП.
3. Алгоритм LRU (рассмотрен ранее в разделе Управление памятью в защищенном режиме) – удаляется не используемая в последнее время страница.
4. Алгоритм, использующий понятие рабочего набора страниц.


1.4.4. Разделы в виртуальном адресном пространстве процесса

Адресное пространство процесса Windows
Адресное пространство процесса разделено на системный и пользовательский разделы – см. рис. 2- 27.

13 SHAPE \* MERGEFORMAT 1415

Рисунок 1 – 27 – разделы в адресном пространстве процесса Windows

В Win32 определены четыре механизма управления виртуальной памятью:
виртуальная память, используемая для операций с большими массивами объектов или структур (размер массива превышает размер страницы). Для реализации метода используется резервирование регионов в адресном пространстве процесса и последующая передача физической памяти региону;
кучи (heaps), применяемые для операций с большим количеством малых объектов (размер объекта меньше размера страницы);
файлы, проецируемые в память - средства для операций с файлами большого размера и для обеспечения совместного доступа приложений к данным;
AWE (Adressing Windowing Extension) – отображение виртуального адресного пространства на окно размером 4 Гб физической памяти, размер которой превышает 4 Гб.

Резервирование регионов в адресном пространстве процесса и передача физической памяти региону

Регионом в адресном пространстве процесса называется совокупность смежных страниц виртуальной памяти, имеющих одинаковый статус, тип и атрибут защиты.
Приложение резервирует регион в адресном пространстве процесса, используя функцию
VirtualAlloc(lpvAddress: Pointer; dwSize, flAllocationType, flProtect: DWORD): Pointer;
Первый параметр определяет положение резервируемого региона в адресном пространстве. Если параметр равен Nil, система определяет положение региона самостоятельно. Регионы всегда резервируются на границе 64К.
Если запрос выполнен, функция возвращает базовый адрес зарезервированного региона.
Второй параметр задает размер резервируемого региона в байтах. Заданный размер увеличивается до величины, кратной размеру страницы.
Третий параметр определяет вид операции – MEM_RESERVE – зарезервировать регион, MEM_COMMIT - передать региону физическую память (сначала нужно зарезервировать регион, затем передать ему память).
При указании параметра MEM_TOP_DOWN система размещает регион по максимально возможному адресу - Allocates memory at the highest possible address. Это дает возможность уменьшить фрагментацию виртуального адресного пространства.
В принципе можно одновременно зарезервировать регион и передать ему физическую память – например
VirtualAlloc (Nil, 100*1024, MEM_RESERVE OR MEM_COMMIT, PAGE_READWRITE);
Последний параметр определяет атрибут защиты.
Для возврата физической памяти, спроецированной на регион, или освобождения всего региона адресного пространства используется функция
VirtualFree (lpAddress: Pointer; dwSize,: DWORD): BOOL;
В простейшем случае использования этой функции – для освобождения всей переданной региону физической памяти – в параметр lpAddress необходимо передать базовый адрес региона, в параметр dwSize=0, так как системе известен размер региона. В третьем параметре следует передать MEM_RELEASE – это приведет к возврату системе всей физической памяти, спроецированной на регион, и освобождению самого региона. Если необходимо не освобождая регион вернуть в систему часть физической памяти, переданной региону, в параметр lpAddress заносится адрес, идентифицирующий первую возвращаемую страницу, в параметр dwSize – количество возвращаемых байт, в параметре dwFreeType - MEM_DECOMMIT.

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

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

Создание и использование куч
Процессу разрешено создавать несколько куч, являющихся частью его адресного пространства.
Куча - это регион зарезервированного адресного пространства. Первоначально большей его части физическая память не передается. После того, как программа занимает эту область под данные, диспетчер, управляющий кучами, передает ей страницы физической памяти. При освобождении страниц в куче диспетчер возвращает физическую память системе.
Одна куча предоставляется процессу по умолчанию. Ее описатель возвращает функция
GetProcessHeap() : Handle;
Дополнительные кучи создаются вызовом функции
HeapCreate ( flOption, dwInitialSize, MaximumSize) : Handle;
Первый параметр определяет характер операций, выполняемых над кучей. По умолчанию (значение 0) действует принцип последовательного доступа к куче (как к критическому участку).
Второй параметр определяет количество байт, первоначально передаваемых куче.
Третий параметр указывает максимальный размер кучи. Может быть равен 0 - в этом случае система резервирует регион, самостоятельно определяя его размер и при необходимости расширяет его до максимально возможного объема.
Выделение блока памяти из кучи выполняет функция
HeapAlloc ( Handle, dwFlags, dwBytes ) : pointer;
Первый параметр - описатель кучи, возвращаемый функциями GetProcessHeap() или HeapCreate()
Второй параметр указывает на характер выделения памяти. При его значении, равным HEAP_ZERO_MEMORY=8, выделяемый блок заполняется нулями.
Третий параметр определяет число выделяемых в куче байт.
Освобождение блока памяти выполняет функция
HeapFree ( Handle, dwFlags, dwBytes ) : Boolean;
Уничтожение кучи выполняет функция HeapDestroy (Handle) : Boolean.

Получение информации о состояниии виртуальной памяти

Сведения о конкретной платформе предоставляет процедура:
void GetSystemInfo(LPSYSTEM_INFO [ Cкачайте файл, чтобы посмотреть ссылку ])
Структура данных SYSTEM_INFO описана cледующим образом:
typedef struct _SYSTEM_INFO {
union {
DWORD [ Cкачайте файл, чтобы посмотреть ссылку ]; struct {
WORD [ Cкачайте файл, чтобы посмотреть ссылку ];
WORD [ Cкачайте файл, чтобы посмотреть ссылку ];
};
};
DWORD [ Cкачайте файл, чтобы посмотреть ссылку ]
);
Структура данных _MEMORYSTATUS описана как
type
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Назначение полей данной структуры:
dwMemoryLoad - оценка занятости системы управления памятью(0-100)
dwTotalPhys - общий размер физической памяти RAM-памяти в байтах
dwAvailPhys - общий размер физической памяти RAM-памяти в байтах, доступной для выделения
dwTotalPageFile - максимальное количество байтов, которое может содержаться в страничном файде на жестком диске (или дисках)
dwAvailPageFile - максимальное количество байтов, которое может быть передано процессу из страничного файла
dwTotalVirtual: DWORD - количество байтов в адресном пространстве, принадлежащих лично данному процессу
dwAvailVirtual - суммарный объем всех свободных регионов в адресном пространстве процесса, вызывающего процедуру GlobalMemoryStatus
вычитая из dwTotalVirtual полученное значение, можно найти размер зарезервированной процессом области в виртуальном адресном пространстве

Перед вызовом процедуры необходимо занести в поле dwLength размер структуры в байтах с помощью функции sizeof().

Для запроса информации об участке памяти по заданному адресу (размер, тип памяти, атрибуты защиты) текущего процесса служит функция:
SIZE_T VirtualQuery(
LPCVOID [ Cкачайте файл, чтобы посмотреть ссылку ],
PMEMORY_BASIC_INFORMATION [ Cкачайте файл, чтобы посмотреть ссылку ],
SIZE_T [ Cкачайте файл, чтобы посмотреть ссылку ]
);

При вызове функции первый параметр должен содержать адрес виртуальной памяти, о котором нужно получить информацию.
Второй параметр – переменная типа, описанного как
typedef struct _MEMORY_BASIC_INFORMATION { PVOID 13 HY
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·–
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·Назначение полей данной структуры:
BaseAddress - значение параметра lpAddress, округленное до значения, кратного размеру страницы
AllocationBase - базовый адрес региона, включающего адрес запроса
AllocationProtect - атрибут защиты региона – некоторые из возможных значений PAGE_NOACCESS, PAGE_READONLY, PAGE_READWRITE
RegionSize - суммарный размер (в байтах) группы страниц, начинающихся с базового адреса и имеющих те же атрибуты защиты, состояние и тип, что и страница, обнаруженная по адресу lpAddress
State - указывает состояние (MEM_FREE, MEM_RESERVE, MEM_COMMIT) всех смежных страниц, имеющих те же атрибуты защиты, состояние и тип, что и страница, расположенная по адресу lpAddress

Для состояния MEM_FREE элементы Allocationbase, Alloocation, Protect и Type не определяются
Protect - содержит атрибут защиты (PAGE_*),общий для всех смежных страниц, имеющих те же атрибуты защиты, состояние и тип, что и страница, расположенная по адресу lpAddress
Type - определяет тип физической памяти (MEM_IMAGE, MEM_MAPPED или MEM_PRIVATE), связанной с группой смежных страниц, имеющих имеющих те же атрибуты защиты,состояние и тип, что и страница, расположенная по адресу lpAddress

Параметр dwLength задает размер структуры MEORY_BASIC_INFORMATION.
Функция VirtualQuery() возвращает число байт, скопированных в буфер. Если возвращено нулевое значение, информация о запрошенном участке НЕ ПОЛУЧЕНА.
Сканируя память в диапазоне от минимального до максимального адреса, можно построить карту виртуальной памяти процесса.



Тема 1.5. Статическое и динамическое связывание. Динамически подключаемые библиотеки (DLL)
Статическое и динамическое связывание
При разработке программ, используется принцип модульности (разбиения программы на составные части), каждая из которых может подготавливаться отдельно.
Программный модуль - программа или функционально завершенный фрагмент программы, предназначенный для хранения, трансляции, объединения с другими программными модулями и загрузки в оперативную память.
От написания до выполнения программа проходит следующие этапы:
Трансляция
Редактирование связей (компоновка)
Загрузка.
На рисунке 1 -28 показаны перечисленные этапы и используемые для их выполнения системные обрабатывающие программы.

13 SHAPE \* MERGEFORMAT 1415

Рисунок 1-28- этапы подготовки и выполнения прикладной программы
Программа пишется в виде исходного модуля, на рисунке - файл ИМ.
Исходный модуль - программный модуль на исходном языке, обрабатываемый транслятором и представляемый для него как целое, достаточное для проведения трансляции.
Трансляция - преобразование программы, представленной на одном языке программирования, в программу на другом языке программирования, в определенном смысле равносильную первой.
Как правило, выходным языком транслятора является машинный язык целевой вычислительной системы. Машинный язык - язык программирования, предназначенный для представления программы в форме, позволяющей выполнять ее непосредственно техническими средствами обработки информации.
Трансляторы - общее название для программ, осуществляющих трансляцию. Они подразделяются на Ассемблеры и Компиляторы - в зависимости от исходного языка программы, которую они обрабатывают.
Объектный модуль (ОМ) - программный модуль, получаемый в результате трансляции исходного модуля.
Поскольку результатом трансляции является модуль на языке, близком к машинному, в нем уже не остается признаков того, на каком исходном языке был написан программный модуль. Это создает принципиальную возможность создавать программы из модулей, написанных на разных языках. Специфика исходного языка, однако, может сказываться на физическом представлении базовых типов данных, способах обращения к процедурам/функциям и т.п.
Большая часть объектного модуля - команды и данные машинного языка именно в той форме, в какой они будут существовать во время выполнения программы. Однако, программа в общем случае состоит из многих модулей. Поскольку транслятор обрабатывает только один конкретный модуль, он не может должным образом обработать те части этого модуля, в которых запрограммированы обращения к данным или процедурам, определенным в другом модуле. Такие обращения называются внешними ссылками. Те места в объектном модуле, где содержатся внешние ссылки, транслируются в некоторую промежуточную форму, подлежащую дальнейшей обработке. Говорят, что объектный модуль представляет собой программу на машинном языке с неразрешенными внешними ссылками.
Разрешение внешних ссылок выполняется на следующем этапе подготовки, который обеспечивается Редактором Связей (Компоновщиком). Редактор Связей соединяет вместе все объектные модули, входящие в программу. Поскольку Редактор Связей "видит" уже все компоненты программы, он имеет возможность обработать те места в объектных модулях, которые содержат внешние ссылки. Результатом работы Редактора Связей является загрузочный модуль.
Загрузочный модуль - программный модуль, представленный в форме, пригодной для загрузки в оперативную память для выполнения.
Загрузочный модуль сохраняется в виде файла на внешней памяти. Для выполнения программа должна быть перенесена (загружена) в оперативную память. Иногда при этом требуется некоторая дополнительная обработка (например, настройка адресов в программе на ту область оперативной памяти, в которую программа загрузилась). Эта функция выполняется Загрузчиком, который обычно входит в состав операционной системы.
Описанный процесс называется статическим связыванием.
Статическое связывание использовалось в однозадачных ОС. В многозадачных ОС (к которым относится и MS Windows) статическое связывание приводит к неэффективному использованию ОП, и вместо него используется динамическое связывание, основанное на использовании динамически связываемых (подключаемых) библиотек – DLL – dynamic linked libraries. В этом случае редактирование связей выполняется при каждом запуске программы на выполнение и совмещается с загрузкой. Этот вариант связывания при запуске более расходный, т.к. затраты на связывание тиражируются при каждом запуске. Но он обеспечивает:
большую гибкость в сопровождении, так как позволяет менять отдельные объектные модули программы, не меняя остальных модулей;
экономию внешней памяти, так как объектные модули, используемые во многих программах не копируются в каждый загрузочный модуль, а хранятся в одном экземпляре.
Области применения DLL
Реализация модульности ОП и приложений
Системные службы
Серверы автоматизации
Объекты СОМ

В DLL могут храниться:
разделяемые константы
набор функций и процедур
формы, объекты.

Основные DLL MS Windows:
Kernel32.dll – функции управления памятью, процессами и потоками
User32.dll – интерфейс пользователя, создание окон и посылка сообщений
GDI32.dll – графика и вывод текста
AdvAPI32.dll – защита объектов, работа с реестром
ComCtl32.dll – стандартные элементы управления.

Достоинства и недостатки DLL
К достоинствам DLL относятся:
расширение функциональности приложения;
возможность использования разных языков программирования;
более простое управление проектом;
экономия памяти;
разделение ресурсов;
упрощение локализации.
Недостатки DLL - возможность конфликта версий DLL, снижение надежности приложений (возможность использования для внедрения посторонних внешних объектов).

Создание DLL
В RAD Delphi выбрать команду New, в окне выбрать пиктограмму DLL, нажать ОК. Текст:
Library Project1;
{комментарий }
Uses Sysutils, Classes,
Begin

End.

Смысл комментария: если DLL импортирует или экспортирует функции со строковыми переменными или возвращает строковые значения, в оператор Uses необходимо добавить модуль ShareMem. Чтобы избежать этого, строковую информацию следует передавать с помощью параметров типа Pchar или ShortString.
Рассмотрим простейшее применение DLL:
Определение некоторого числа функций, которые потом могут использоваться разными приложениями.
Объявление экспортируемой функции в DLL выполняется в трех местах:
в разделе interfase модуля;
в разделе export;
тело функции следует определять в разделе implementation
Пример: Создать DLL с именем My DLL для экспорта функций plus1(х),
Function plus1(x: integer):integer;
Создать через File |New| проект DLL, создать модуль Unit1 и доставить его к проекту, в разделе interfase этого модуля:
Function
plus1(x:integer):integer; stdcall;
Стандартное соглашение о вызовах
Параметры передаются для функции справа налево, за освобождение стека отвечает вызываемая процедура.
раздел export – дописать plus1;
3.implementation
function plus1 (x:integer): integer;
begin
plus1:=x+1;
end;

Использование DLL (импорт функций из DLL)

Способы подключения библиотек
В большинстве случаев используется неявная загрузка и явная загрузка DLL
Для того, чтобы приложение или другая DLL могли вызывать функции, содержащиеся в DLL, файл DLL нужно спроецировать на адресное пространство вызывающего процесса. Это делается либо неявным подключение при загрузке, либо явным в период выполнения (оба способа рассмотрены ниже).
Как только DLL спроецирована на адресное пространство вызывающего процесса, её функции доступны всем его потокам. Для потоков код и данные DLL – просто дополнительный код и данные, оказавшиеся в адресном пространстве процесса. Когда поток вызывает какую-либо функцию из DLL, функция считывает свои данные из стека потока и использует этот стек для размещения своих локальных переменных.
Любые созданные потоком DLL объекты принадлежат вызвавшему потоку –
DLL ничем не владеет.

Неявная загрузка DLL (неявное подключение)
DLL загружается одновременно с загрузкой программы по объявлениям функций, импортируемых из DLL. По данным объявлениям компоновщик Delphi записывает имена импортирующих функций и содержащих их DLL по определенному адресу внутри EXE – файла. Когда происходит запуск программы и её EXE – файл отображается в адресное пространство процесса, Windows обращается по этому адресу и извлекает имена всех DLL, используемых программой, вместе с именами импортируемых из них функций.
Как только Windows определяет, что программа использует некоторую DLL, она вызывает функцию LoadLibrary (). Эта функция ищет DLL – файл и, если не находит – выгружает программу. Если же DLL находится, её файл отображается в адресное пространство процесса. После этого Windows находит определенный адрес внутри образа DLL – файла и извлекает оттуда имена всех экспортируемых DLL функций. Если не удастся найти хотя бы одной функции, которую программа предполагает и импортировать, выполнение программы прекращается.

Пример неявной загрузки DLL:
В разделе implementation
{$ R*.DRM}
function pls1(x:integer):integer;
stdcall;
external путь\Mydll.DLL’
name plus1;

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

Явная загрузка DLL
Явная загрузка и импортирование более динамичны и программно управляемы.
Для реализации этого способа необходимо:
в разделе type добавить
Tplus1= function pls1(x:integer):integer; stdcall;
2. В разделе implementation добавить описание переменных:

Var plus1:Vplus1;
hDll: Thandle;
3. При возникновении необходимости в выполнение функции библиотеки должна быть загружена:
hDll:= LoadLibrary(путь\myDll.dll’);
//(возвращение внутреннего адреса загрузки или 0)
@plus1:=GetprocAddress(hDll,’plus1’);
//вызов функции plus1( );
4. Выгрузка библиотеки:
FreeLibrary(hDll);
Выполнение процедур инициализации и деинициализации Dll
Для инициализации глобальных переменных при отображении Dll в адресное пространство процесса используется системная переменная DllProc, которой в блоке инициализации должен быть присвоен адрес некоторой процедуры, после этого указанная процедура будет вызываться автоматически вызываться при отображении Dll в адресное пространство какого-либо процесса и при выгрузке её из адресного пространства со счетчиком обращения 0.
Library DllEntry ;
Uses Windows,SysUtills,Classes;
procedure DllMain(kod:DWord);
begin
case kod of
dll_Process_Attach:{операторы};
dll_Process_Detach:{операторы};
end;
end;
begin DllProc:[email protected];
DllMain(Dll_Process_Attach);
end.
Инициализационный блок выполняется 1 раз на каждый процесс. Вызов блока инициализации приводит к присвоению глобальной переменной адреса процедуры DllMain. После этого все вызовы (завершения) передаются DllMain.

Обмен данными между процессами

13 SHAPE \* MERGEFORMAT 1415

Рисунок 1-29 схема обмена данными между приложениями с использованием DLL

Для создания общей области, принадлежащей двум процессам, необходимо:
Создать общий проецируемый файл с именем или без имени (для решения данной задачи с именем).
TH:= CreateFileMapping (- --имя’);
2) Спроецировать отображаемый файл в адресное пространство процесса:
p:=MapViewOfFie(TH,---,--);
Полученный указатель р возвращать каждому приложению.
Действия 1 и 2 должны выполняться для каждого процесса один раз, а действие 3- всякий раз когда возникает необходимость обращаться к области.
Создание Dll, в которой при подключение к процессу (отображение на адресное пространство) с помощью процедуры DllMain будет выполняться действие 1 и 2, а выдача указателя – с помощью экспортируемой функции.
Library Share;
Uses SysUtils,Classes,Windows;
var
HObj: THandle;// отображение объекта отображаемого файла
pMem: Pointer; // указатель на блок
procedure UnMapMemory;// память надо освобождать при завершении приложений, а также при невозможности ее отображения .
begin
If Assigned(pMem) then
begin
UnMapViewOfFile(pMem);
pMem:= nil;

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·/удалить отображение
end;
//3) procedure DllMain(Act:Dword);
begin
case kod of
dll_Process_Attach;
begin
pMem:=nil;

·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Тема 1.6 Структура MS Windows и драйверы режима ядра

Упрощенная версия архитектуры MS Windows показана на рис. 1-30. Данная схема не отражает всех деталей архитектуры (например, здесь не показаны уровни сетевых компонентов и различных типов драйверов устройств).


13 SHAPE \* MERGEFORMAT 1415
Рисунок 1-30 –упрощенная архитектура MS Windows
На рис. 1-30 линия разделяет те части Windows, которые выполняются в режиме ядра и в пользовательском режиме. Прямоугольники над этой линией соответствуют процессам пользовательского режима, а компоненты под ней сервисам режима ядра. Потоки пользовательского режима выполняются в защищенных адресных пространствах процессов (хотя при выполнении в режиме ядра они получают доступ к системному пространству). Таким образом, процессы поддержки системы, сервисов, приложений и подсистем окружения имеют свое адресное пространство. Существует четыре типа пользовательских процессов:
фиксированные процессы поддержки системы (system support processes) например, процесс обработки входа в систему и диспетчер сеанcов, не являющиеся сервисами Windows (т. е. не запускаемые диспетчером управления сервисами);
процессы сервисов (service processes) носители Windows-сервисов де Task Scheduler и Spooler. Многие серверные приложения Windows, пример Microsoft SQL Server и Microsoft Exchange Server, тоже включают компоненты, выполняемые как сервисы;
пользовательские приложения (user applications) бывают шести типов- для 32-разрядной Windows, 64-разрядной Windows, 16-разрядной Windows 3.1, 16-разрядной MS-DOS, 32-разрядной POSIX и 32-разрядной OS/2;
подсистемы окружения (environment subsystems) реализованы как часть поддержки среды операционной системы, предоставляемой пользователям и программистам. Изначально Windows NT поставлялась с тремя подсистемами окружения: Windows, POSIX и OS/2. Последняя была изъята в Windows 2000. Что касается Windows XP, то в ней поставляется только подсистема Windows улучшенная подсистема POSIX доступна как часть бесплатного продукта Services for UNIX.
В Windows пользовательские приложения не могут вызывать сервисы операционной системы напрямую, вместо этого они работают с одной или несколькими DLL подсистем. Их назначение заключается в трансляции документированных функций в соответствующие внутренние (и обычно недокументированные) вызовы системных сервисов Windows. Трансляция может осуществляться как с помощью сообщения, посылаемого процессу подсистемы окружения, обслуживающему пользовательское приложение, так и без него.
Windows включает следующие компоненты режима ядра.
Исполнительная система (executive) Windows, содержащая базовые сервисы операционной системы, которые обеспечивают управление памятью, процессами и потоками, защиту, ввод-вывод и взаимодействие между процессами.
Ядро (kernel) Windows, содержащее низкоуровневые функции операционной системы, которые поддерживают, например, планирование потоков, диспетчеризацию прерываний и исключений, а также синхронизацию при использовании нескольких процессоров. Оно также предоставляет набор процедур и базовых объектов, применяемых исполнительной системой для реализации структур более высокого уровня.
Драйверы устройств (device drivers), в состав которых входят драйверы аппаратных устройств, транслирующие пользовательские вызовы функций ввода-вывода в запросы, специфичные для конкретного устройства, а также сетевые драйверы и драйверы файловых систем.
Уровень абстрагирования от оборудования (hardware abstraction layer HAL), изолирующий ядро, драйверы и исполнительную систему Windows от специфики оборудования на данной аппаратной платформе (например, от различий между материнскими платами)
Подсистема поддержки окон и графики реализует функции графического пользовательского интерфейса (GUI) – поддержку окон, элементов управления пользовательского интерфейса и отрисовку окон.

Драйверы режима ядра, их возможности
Типы драйверов устройств
Windows поддерживает множество типов драйверов устройств и сред их программирования. Среды программирования могут различаться даже для драйверов одного типа в зависимости от типа устройства, для которого предназначен драйвер. Драйверы могут работать в двух режимах: в пользовательском или в режиме ядра. Windows поддерживает несколько типов драйверов пользовательского режима:
Драйверы виртуальных устройств (virtual device drivers, VDD) Используются для эмуляции 16-разрядных программ MS-DOS. Они перехватывают обращения таких программ к портам ввода-вывода и транслируют их в вызовы Windows-функций ввода-вывода, передаваемые реальным драйверам устройств. Поскольку Windows является полностью защищенной операционной системой, программы MS-DOS пользовательского режима не могут напрямую обращаться к аппаратным средствам - они должны делать это через драйверы устройств режима ядра.
Драйверы принтеров Драйверы подсистемы Windows, которые транслируют аппаратно-независимые запросы на графические операции в команды, специфичные для принтера. Далее эти команды обычно направляются драйверу режима ядра, например драйверу параллельного порта (Parportsys) или драйверу порта принтера на USB-шине (Usb-print.sys).

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

WDM-драйверы
Это драйверы устройств, отвечающие спецификации Windows Driver Model (WDM). WDM требует от драйверов поддержки управления электропитанием, Plug and Play и WMI. Большинство драйверов Plug and Play построено на модели WDM. Эта модель реализована в Windows, Windows 98 и Windows Millennium Edition, поэтому WDM-драйверы этих операционных систем совместимы на уровне исходного кода. Существует три типа WDM-драйверов.
Драйверы шин. Управляют логическими или физическими шинами Примеры шин - PCMCIA, PCI, USB, IEEE 1394, ISA. Драйвер шины отвечает за распознавание устройств, подключенных к управляемой им шине, оповещение о них диспетчера РпР и управление параметрами электропитания шины.
Функциональные драйверы. Управляют конкретным типом устройств. Драйверы шин представляют устройства функциональным драйверам через диспетчер РпР. Функциональным счита
·ется драйвер, экспортирующий рабочий интерфейс устройства операционной системе. Как правило, это драйвер, больше других знающий о функционировании определенного устройства.
Драйверы фильтров Занимающие более высокий логический уровень, чем функциональные драйверы, они дополняют функциональность или изменяют поведение устройства либо другого драйвера. Так, утилиту для перехвата ввода с клавиатуры можно реализовать в виде драйвера фильтра клавиатуры, расположенного на более высоком уровне, чем функциональный драйвер клавиатуры.
В WDM ни один драйвер не отвечает за все аспекты управления конкретным устройством. Драйвер шины определяет изменения в составе на шине (при подключении и отключении устройств), помогает диспетчеру РпР в перечислении устройств на шине, обращается к cпeцифичным для шины регистрам и в некоторых случаях управляет электропитанием подключенных к шине устройств. К аппаратной части устройства обращается только функциональный драйвер.

Многоуровневые драйверы

Поддержка индивидуального устройства часто распределяется между несколькими драйверами, каждый из которых обеспечивает часть функциольности, необходимой для нормальной работы устройства. Кроме WDM-драйверов шин, функциональных драйверов и драйверов фильтров, оборудование могут поддерживать и следующие компоненты.
драйверы классов устройств (class drivers) Реализуют обработку ввода-вывода для конкретного класса устройств, например дисковых устройств, ленточных накопителей или приводов CD-ROM, где аппаратные интерфейсы стандартизированы и один драйвер может обслуживать аналогичные устройства от множества производителей.
порт-драйверы (port drivers) Обрабатывают запросы на ввод-вывод, специфичные для определенного типа порта ввода-вывода, например SCSI. Порт-драйверы реализуются как библиотеки функций режима ядра, а не как драйверы устройств.
минипорт-драйверы (miniport drivers) Преобразуют универсальные запросы ввода-вывода к порту конкретного типа в запросы, специфичные для адаптера конкретного типа, например для SCSI-адаптера. Минипорт-драйверы являются истинными драйверами устройств, которые импортируют функции, предоставляемые порт-драйвером,
Рассмотрим пример, который демонстрирует, как работают драйверы устройств. Драйвер файловой системы принимает запрос на запись данных в определенное место конкретного файла. Он преобразует его в запрос на запись определенного числа байтов по определенному «логическому» адресу на диске, а затем передает этот запрос (через диспетчер ввода-вывода) драйверу диска. Последний в свою очередь преобразует запрос в физический адрес на диске (цилиндр/дорожка/сектор) и позиционирует головки дискового устройства для записи данных.

Структура драйвера
Управление работой драйверов осуществляет подсистема ввода-вывода.
Драйвер устройства состоит из набора процедур, вызываемых на различных этапах обработки запроса ввода-вывода.
Основные процедуры драйвера показаны на рис. 1-31.

13 SHAPE \* MERGEFORMAT 1415
Рисунок 1-31 – основные процедуры драйвера

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

Взаимодействие прикладной программы с драйвером режима ядра

Для организации передачи драйверу данных и получения данных от драйвера используется функция
DeviceIOControl ()

Cредства построения драйверов

Драйверы режима ядра программируются на языке С в среде MS Visual Studio. Основной инструмент построения драйверов режима ядра – Windows DDK, содержащий необходимые справочные материалы, заголовочные файлы и утилиты. Для справочных целей может использоваться MSDN.


Тема 1.7 Управление вводом-выводом и файловые системы Win32

Эволюция файловых систем ЭВМ

Файловые системы со сквозной записью (FAT)
Файловые системы с отложенной записью (Ext2fs)
Журналируемые (восстанавливаемые) файловые системы (NTFS)

Файловые системы Windows
Windows поддерживает файловые системы:
CDFS;
UDF;
FAT12, FАТ16 и FАТ32;
NTFS.
Каждая из этих файловых систем оптимальна для определенной среды.

CDFS
CDFS, или файловая система CD-ROM (только для чтения), обслуживается драйвером \Windows\System32\Drivers\Cdfs.sys, который поддерживает надмножества форматов ISO-9660 и Joliet.
Формат ISO-9660 сравнительно прост и имеет ряд ограничений, например имена с буквами верхнего регистра в кодировке ASCII и максимальной длиной в 32 символа.
Joliet более гибок и поддерживает Unicode-имена произвольной длины.
Если на диске присутствуют структуры для обоих форматов (чтобы обеспечить максимальную совместимость), CDFS использует формат Joliet. CDFS имеет ряд ограничений:
максимальная длина файлов не должна превышать 4 Гб;
число каталогов не может превышать 65 535.

UDF
Файловые системы UDF обладают следующими преимуществами:
длина имен файлов и каталогов может быть до 254 символов в ASCII-кодировке или до 127 символов в Unicode-кодировке;
файлы могут быть разреженными (sparse);
размеры файлов задаются 64-битными значениями.
Хотя формат UDF разрабатывался с учетом особенностей перезаписыва-емых носителей, драйвер UDF в Windows (\Windows\System32\Drivers\ Udfs.sys) поддерживает носители только для чтения. Кроме того, в Windows не реализована поддержка других возможностей UDF, в частности именованных потоков, списков управления доступом и расширенных атрибутов.

FAT12, FAT16 и FAT32
Windows поддерживает файловую систему FAT по трем причинам:
для возможности обновления операционной системы с прежних версий Windows до современных,
для совместимости с другими операционными системами при многовариантной загрузке
как формат гибких дисков. Драйвер файловой системы FAT в Windows реализован в \Windows\System32\Drivers\Fastfatsys.
В название каждого формата FAT входит число, которое указывает разрядность, применяемую для идентификации кластеров на диске. 12-разрядный идентификатор кластеров в FAT12 ограничивает размер дискового раздела 4096 кластерами. В Windows используются кластеры размером от 512 байтов до 8 Кб, так что размер тома FAT12 ограничен 32 Мб. Поэтому Windows использует FAT12 как формат 3,5-дюймовых дискет, способных хранить до 1,44 Мб данных.

FAT16 за счет 16-разрядных идентификаторов кластеров может адресовать до 65 536 кластеров. В Windows размер кластера FAT16 варьируется от 512 байтов до 64 Кб, поэтому размер тома c FАТ16 ограничен 4 Гб.
Размер кластеров, используемых Windows, зависит от размера тома

Размер тома (Мб)
Размер кластера

0-32
512 байт

33-64
1 К

65-128
2 К

512-1023
16 К

1024-2047
32 К

2048-4095
64 К

Структуры данных FAT

Структура раздела FAT изображена на рисунке 1-32.
Загрузочный сектор

Загрузочный сектор


FAT1

Структура FSInfo



Резервная область


FAT2


FAT1


Корневой каталог


FAT2



Область данных



Область данных


Системы FAT12 и FAT16 Система FAT32

Рисунок 1-32 Структура раздела с файловой системой FAT

В файловой системе FAT дисковое пространство логического раздела делится на две области - системную и область данных (см. рис. 1-32). Системная область создается и инициализируется при форматировании, а впоследствии обновляется при манипулировании файловой структурой. Системная область файловых систем FAT состоит из следующих компонентов:
загрузочная запись (boot record, BR);
резервная область;
таблицы размещения файлов;
область корневого каталога (не существует в FAT32).
Область данных логического диска содержит файлы и каталоги, подчиненные корневому, и разделена на участки одинакового размера кластеры. Кластер может состоять из одного или нескольких последовательно расположенных на диске секторов. Число секторов в кластере должно быть кратно 2n и может принимать значения от 1 до 64. Размер кластера зависит от типа используемой файловой системы и объема логического диска.
Загрузочный сектор
В первом секторе логического диска с системой FAT располагается загрузочный сектор и блок параметров BIOS.
Загрузочный сектор выполняет две важные функции: описывает структуру данных на диске, а также позволяет осуществить загрузку операционной системы.
Для доступа к содержимому файла, находящемуся на разделе с файловой системой FAT, необходимо получить номер первого кластера файла. Этот номер входит в состав элемента каталога, содержащего запись о файле. Номеру первого кластера соответствует элемент таблицы FAT, в котором хранится адрес кластера, содержащего следующую часть файла. Элемент FAT, соответствующий последнему кластеру в цепочке, содержит сигнатуру конца файла. Для FАT12 это значение составляет 0xFFF, для FAT16 - 0xFFFF, для FAT32 - 0xFFFFFFFF.
Назначение, структура и типы таблицы размещения файлов
Своё название FAT получила от одноимённой таблицы размещения файлов - File Allocation Table – FAT. В таблице размещения файлов хранится информация о кластерах логического диска. Каждому кластеру соответствует элемент таблицы FAT, содержащий информацию о том, свободен данный кластер или занят данными файла. Если кластер занят под файл, то в соответствующем элементе таблицы размещения файлов указывается адрес кластера, содержащего следующую часть файла. Номер начального кластера, занятого файлом, хранится в элементе каталога, содержащего запись об этом файле. Последний элемент списка кластеров содержит признак конца файла (EOF - End Of File). Первые два элемента FAT являются резервными.
Файловая система FAT всегда заполняет свободное место на диске последовательно от начала к концу. При создании нового файла или увеличении существующего она ищет самый первый свободный кластер в таблице размещения файлов. Если в процессе работы одни файлы были удалены, а другие изменились в размере, то появляющиеся в результате пустые кластеры будут рассеяны по диску. Если кластеры, содержащие данные файла, расположены не подряд, то файл называется фрагментированным.
[ Cкачайте файл, чтобы посмотреть картинку ]
Рисунок 1-33. Пример таблицы размещения файлов

На рис. 2 показано размещение трех файлов – первый состоит из трех кластеров – это непрерывный (нефрагментированный) файл. Второй файл фрагментированный..

Корневой каталог
За таблицами размещения файлов следует корневой каталог. Каждому файлу и подкаталогу в корневом каталоге соответствует 32-байтный элемент каталога (directory entry), содержащий имя файла, его атрибуты (архивный, скрытый, системный и только для чтения), дату и время создания (или внесения в него последних изменений), а также прочую информацию. Для файловых систем FАТ12 и FAT16 положение корневого каталога на разделе и его размер жестко зафиксированы. В FAT32 корневой каталог может быть расположен в любом месте области данных раздела и иметь произвольный размер.
Форматы имен файлов
Одной из характеристик ранних версий FAT (FAT12 и FAT16) является использование коротких имен файлов.
Короткое имя состоит из двух полей - 8-байтного поля, содержащего собственно имя файла, и 3-байтного поля, содержащего расширение (формат - 8.3). Структура элемента каталога для короткого имени файла представлена в таблице 4. Первый байт короткого имени выполняет функции признака занятости каталога:
если первый байт равен 0хЕ5, то элемент каталога свободен и его можно использовать при создании нового файла;
если первый байт равен 0x00, то элемент каталога свободен и является началом чистой области каталога (после него нет ни одного задействованного элемента).
Таблица Структура элемента каталога для короткого имени файла

Смеще-ние
Размер
(байт)
Содержание

0x00
11
Короткое имя файла

0x0B
1
Атрибуты файла

0x0C
1
Зарезервировано для Windows NT. Поле обрабатывается только в FAT32

0x0D
1
Поле, уточняющее время создания файла (содержит десятки миллисекунд). Поле обрабатывается только в FAT32

0x0E
1
Время создания файла. Поле обрабатывается только в FAT32

0x10
2
Дата создания файла. Поле обрабатывается только в FАТ32

0x12
2
Дата последнего обращения к файлу для записи или считывания данных. Поле обрабатывается только в FАТ32

0x14
2
Старшее слово номера первого кластера файла. Поле обрабатывается только в FAT32

0x16
2
Время выполнения последней операции записи в файл

0x18
2
Дата выполнения последней операции записи в файл

0x1A
2
Младшее слово номера первого кластера файла

0x1C
4
Размер файла в байтах


В файловых системах FАТ32 и VFАТ (виртуальная FАТ, расширение FАТ16) включена поддержка длинных имен файлов (long file name, LFN). Для хранения длинного имени используются элементы каталога, смежные с основным элементом. Имя файла записывается не ASCII -символами, а в Unicode. В одном элементе каталога можно сохранить фрагмент длиной до 13 символов Unicode. Неиспользованный участок последнего фрагмента заполняется кодами 0хFFFF. Структура элемента каталога для длинного имени файла представлена в таблице

Структура элемента каталога для длинного имени файла
Смещение
Размер
(байт)
Содержание

0x00
1
Номер фрагмента

0x01
10
Символы 1-5 имени файла в Unicode

0x0B
1
Атрибуты файла

0x0C
1
Байт флагов

0x0D
1
Контрольная сумма короткого имени

0x0E
12
Символы 6-11 имени файла в Unicode

0x1A
2
Номер первого кластера (заполняется нулями)

0x1C
4
Символы 12-13 имени файла в Unicode


Длинное имя записывается в каталог первым, причём фрагменты размещены в обратном порядке, начиная с последнего. Вслед за длинным (полным) именем размещается стандартный описатель файла, содержащий укороченный по специальному алгоритму вариант этого имени. Пример хранения длинного имени файла показан в http:\\www.ntfs.com/fat-filenames.htm
Один из недостатков FAT –возможность потери данных. При неожиданной остановке системы целостность метаданных тома FAT может быть утрачена, что вызовет повреждение структуры каталогов и значительного объема данных.

Основные свойства NTFS

NTFS встроенная («родная») файловая система Windows. NTFS использует 64-разрядные номера кластеров. Это позволяет NTFS адресовать тома размером до 16 экзабайт (16 миллиардов Гб). Однако Windows ограничивает размеры томов NTFS до значений, при которых возможна адресация 32-разрядными кластерами, т. е. до 128 Тб (с использованием кластеров по 64 Кб). В таблице перечислены размеры кластеров на томах NTFS по умолчанию (эти значения можно изменить при форматировании тома NTFS).
Размеры кластеров на томах NTFS по умолчанию
Размер тома
Размер кластера

512 Мб и менее
5 12 байтов

513-1024 Мб
1Кб

1025-2048 Мб
2 Кб

Более 2048 Мб
4 Кб


Восстанавливаемость
NTFS поддерживает ряд дополнительных возможностей защиту и каталогов, дисковые квоты, сжатие файлов, символьные ссылки на основе каталогов и шифрование. Одно из важнейших свойств NTFS восстанавливаемость. NTFS ведет журнал изменений метаданных путем протоколирования транзакций, поэтому целостность структур файловой системы может быть восстановлена без потери информации о структуре файлов или каталогов. Однако данные файлов могут быть потеряны.
NTFS обеспечивает восстановление файловой системы на основе концепции атомарной транзакции (atomic transaction). Суть атомарных транзакций заключается в том, что некоторые операции над базой данных, называемые транзакциями, выполняются по принципу «все или ничего». Транзакцию можно определить как операцию ввода, изменяющую данные файловой системы или структуру каталогов тома. Отдельные изменения на диске, составляющие транзакцию, выполняются атомарно: в ходе транзакции на диск должны быть внесены все требуемые изменения. Если транзакция прервана аварией системы, часть изменений, уже внесенных к этому моменту, нужно отменить. Такая отмена называется откатом (roll back). После отката база данных возвращается в исходное согласованное состояние, в котором она была до начала транзакции
NTFS использует атомарные транзакции для реализации возможности восстановления файловой системы. Если некая программа инициирует операцию ввода-вывода, которая изменяет структуру NTFS-тома, т. е. модифицирует структуру каталогов, увеличивает длину файла, выделяет место под новый файл и др., то NTFS обрабатывает такую операцию как атомарную транзакцию. NTFS гарантирует, что транзакция будет либо полностью выполнена, либо отменена, если хотя бы одну из операций не удастся завершить из-за сбоя системы. Для реализации данной операции используется протоколирование операций.
Кроме того, NTFS использует избыточность для хранения критически важной информации файловой системы, так что, если на диске появится сбойный сектор, она все равно сможет получить доступ к этой информации. Это одна из особенностей NTFS, отличающих ее от FAT.
Защита
Защита в NTFS построена на модели объектов Windows. Файлы и каталога защищены от доступа пользователей, не имеющих соответствующих прав.
Открытый файл реализуете виде объекта «файл» с дескриптором защиты, хранящимся на диске как часть файла. Прежде чем процесс сможет открыть описатель какого-либо объекта, в том числе объекта «файл», система защиты Windows должна убедиться, что у этого процесса есть соответствующие полномочия. Дескриптор защиты в сочетании с требованием регистрации пользователя при входе в систему гарантирует, что ни один процесс не получит доступа к файлу без разрешения системного администратора или владельца файла.
Избыточность данных и отказоустойчивость
Восстанавливаемость NTFS действительно гарантирует, что файловая система тома останется доступной, но не дает гарантии полного восстановления пользовательских файлов. Последнее возможно за счет поддержки избыточности данных.
Избыточность данных для пользовательских файлов реализуется через многоуровневую модель драйверов Windows, которая поддерживает отказоустойчивые диски. При записи данных на диск NTFS взаимодействует с диспетчером томов, а тот с драйвером жесткого диска. Диспетчер томов может зеркалировать, или дублировать, данные одного диска на другом и таким образом позволяет при необходимости использовать данные избыточной копии. Поддержка таких функций обычно называется RAID уровня 1 . Диспетчеры томов также могут записывать данные в чередующиеся области (stripes) на три и более дисков, используя один диск для хранения информации о четности. Если данные на одном диске потеряны или стали недоступными, драйвер может реконструировать содержимое диска с помощью логической операции XOR. Такая поддержка называется RAID уровня 5 .

Дополнительные возможности NTFS
NTFS это не только восстанавливаемая, защищенная, надежная и эффективная файловая система, способная работать в системах повышенной ответственности. Она поддерживает ряд дополнительных возможностей (некоторые из них доступны приложениям через API-функции, другие являются внутренними):
множественные потоки данных;
имена на основе Unicode;
универсальный механизм индексации;
динамическое переназначение плохих кластеров;
жесткие связи и точки соединения;
сжатые и разреженные файлы;
протоколирование изменений;
квоты томов, индивидуальные для каждого пользователя;
отслеживание ссылок;
шифрование;
дефрагментация;
поддержка доступа только для чтения.

Структуры данных NTFS

Структура главной файловой таблицы $MFT
Структура тома NTFS

РАЗДЕЛ 2. Программирование в операционной среде

Тема 2.1. Ассемблеры и макроязыки
2.1.1. Этапы подготовки программы к выполнению
При разработке программ, используется принцип модульности (разбиения программы на составные части), каждая из которых может подготавливаться отдельно. Модульность является основным инструментом структурирования программного изделия, облегчающим его разработку, отладку и сопровождение.
Программный модуль - программа или функционально завершенный фрагмент программы, предназначенный для хранения, трансляции, объединения с другими программными модулями и загрузки в оперативную память.
При выборе модульной структуры должны учитываться следующие основные соображения:
Функциональность - модуль должен выполнять законченную функцию
Несвязность - модуль должен иметь минимум связей с другими модулями, связь через глобальные переменные и области памяти нежелательна
Специфицируемость - входные и выходные параметры модуля должны четко формулироваться.
От написания до выполнения программа проходит следующие этапы:
Обработка макропроцессором
Трансляция
Редактирование связей (компоновка)
Загрузка.
На рисунке показаны перечисленные этапы и используемые для их выполнения системные обрабатывающие программы.

13 SHAPE \* MERGEFORMAT 1415

Рисунок 2-1- этапы подготовки и выполнения прикладной программы
Программа пишется в виде исходного модуля, на рисунке - файл ИМ.
Исходный модуль - программный модуль на исходном языке, обрабатываемый транслятором и представляемый для него как целое, достаточное для проведения трансляции.
Первым (не для всех языков программирования обязательным) этапом подготовки программы является обработка ее Макропроцессором (или Препроцессором). Макропроцессор обрабатывает текст программы и на выходе его получается новая редакция текста (на рис.2-1 – ИМ’). В большинстве систем программирования Макропроцессор совмещен с транслятором, и для программиста его работа и промежуточный ИМ' "не видны". Следует иметь в виду, что Макропроцессор выполняет обработку текста, это означает, с одной стороны, что он "не понимает" операторов языка программирования и "не знает" переменных программы, с другой, что все операторы и переменные Макроязыка (тех выражений в программе, которые адресованы Макропроцессору) в промежуточном ИМ' уже отсутствуют и для дальнейших этапов обработки "не видны". Так, если Макропроцессор заменил в программе некоторый текст A на текст B, то транслятор уже видит только текст B, и не знает, был этот текст написан программистом или подставлен Макропроцессором.
Следующим этапом является трансляция.
Трансляция - преобразование программы, представленной на одном языке программирования, в программу на другом языке программирования, в определенном смысле равносильную первой.
Как правило, выходным языком транслятора является машинный язык целевой вычислительной системы. (Целевая ВС - та ВС, на которой программа будет выполняться.)
Машинный язык - язык программирования, предназначенный для представления программы в форме, позволяющей выполнять ее непосредственно техническими средствами обработки информации.
Трансляторы - общее название для программ, осуществляющих трансляцию. Они подразделяются на Ассемблеры и Компиляторы - в зависимости от исходного языка программы, которую они обрабатывают.
Язык Ассемблера - язык программирования, который представляет собой символьную форму машинного языка с рядом возможностей, характерных для языка высокого уровня (обычно включает в себя макросредства).
Язык высокого уровня - язык программирования, понятия и структура которого удобны для восприятия человеком.
Объектный модуль - программный модуль, получаемый в результате трансляции исходного модуля.
Поскольку результатом трансляции является модуль на языке, близком к машинному, в нем уже не остается признаков того, на каком исходном языке был написан программный модуль. Это создает принципиальную возможность создавать программы из модулей, написанных на разных языках. Специфика исходного языка, однако, может сказываться на физическом представлении базовых типов данных, способах обращения к процедурам/функциям и т.п. Для совместимости разноязыковых модулей должны выдерживаться общие соглашения.
Большая часть объектного модуля - команды и данные машинного языка именно в той форме, в какой они будут существовать во время выполнения программы. Однако, программа в общем случае состоит из многих модулей. Поскольку транслятор обрабатывает только один конкретный модуль, он не может должным образом обработать те части этого модуля, в которых запрограммированы обращения к данным или процедурам, определенным в другом модуле. Такие обращения называются внешними ссылками. Те места в объектном модуле, где содержатся внешние ссылки, транслируются в некоторую промежуточную форму, подлежащую дальнейшей обработке. Говорят, что объектный модуль представляет собой программу на машинном языке с неразрешенными внешними ссылками.
Разрешение внешних ссылок выполняется на следующем этапе подготовки, который обеспечивается Редактором Связей (Компоновщиком). Редактор Связей соединяет вместе все объектные модули, входящие в программу. Поскольку Редактор Связей "видит" уже все компоненты программы, он имеет возможность обработать те места в объектных модулях, которые содержат внешние ссылки. Результатом работы Редактора Связей является загрузочный модуль.
Загрузочный модуль - программный модуль, представленный в форме, пригодной для загрузки в оперативную память для выполнения.
Загрузочный модуль сохраняется в виде файла на внешней памяти. Для выполнения программа должна быть перенесена (загружена) в оперативную память. Иногда при этом требуется некоторая дополнительная обработка (например, настройка адресов в программе на ту область оперативной памяти, в которую программа загрузилась). Эта функция выполняется Загрузчиком, который обычно входит в состав операционной системы.
Возможен также вариант, в котором редактирование связей выполняется при каждом запуске программы на выполнение и совмещается с загрузкой. Это делает Связывающий Загрузчик, другое название – динамический загрузчик. Вариант связывания при запуске более расходный, т.к. затраты на связывание тиражируются при каждом запуске. Но он обеспечивает:
большую гибкость в сопровождении, так как позволяет менять отдельные объектные модули программы, не меняя остальных модулей;
экономию внешней памяти, так как объектные модули, используемые во многих программах не копируются в каждый загрузочный модуль, а хранятся в одном экземпляре.
Вариант интерпретации подразумевает прямое исполнение исходного модуля. Интерпретация - реализация смысла некоторого синтаксически законченного текста, представленного на конкретном языке.
Интерпретатор читает из исходного модуля очередное предложение программы, переводит его в машинный язык и выполняет. Все затраты на подготовку тиражируются при каждом выполнении, следовательно, интепретируемая программа принципиально менее эффективна, чем транслируемая. Однако, интерпретация обеспечивает удобство разработки, гибкость в сопровождении и переносимость.
Примеры интерпретаторов: языки процедур (sell, REXX), JVM.
Не обязательно подготовка программы должна вестись на той же вычислительной системе и в той же операционной среде, в которых программа будет выполняться. Системы, обеспечивающие подготовку программ в среде, отличной от целевой называются кросс-системами. В кросс-системе может выполняться вся подготовка или ее отдельные этапы:
Макрообработка и трансляция
Редактирование связей
Отладка
Типовое применение кросс-систем - для тех случаев, когда целевая вычислительная среда просто не имеет ресурсов, необходимых для подготовки программ, например, встроенные системы.

Ассемблеры

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

Формат предложения языка Ассемблера

Предложения языка Ассемблера описывают команды или псевдокоманды (директивы). Предложения-команды задают машинные команды вычислительной системы; обработка Ассемблером команды приводит к генерации машинного кода. Обработка псевдокоманды не приводит к непосредственной генерации кода, псевдокоманда управляет работой самого Ассемблера. Во всех языках Ассемблеров каждое новое предложение языка начинается с новой строки. В общем случае предложения языка Ассемблера состоят из следующих компонент:
метка или имя;
мнемоника;
операнды;
комментарии.
Метка или имя является необязательным компонентом. Не во всех языках Ассемблеров эти понятия различаются. Если они различаются (например, MASM), то метка - точка программы, на которую передается управление. Однако, физический смысл и метки, и имени - одинаков, это - адрес памяти. Во всех случаях, когда Ассемблер встречает в программе имя или метку, он заменяет ее на адрес той ячейки памяти, к которую имя/метка именует. В языке должны предусматриваться некоторые специальные правила, позволяющие Ассемблеру распознать и выделить метку/имя, например:
метка/имя должна начинаться в 1-й позиции строки, если метки/имени нет, то в 1-й позиции д.б. пробел, или
за меткой/именем должно следовать двоеточие, и т.п.
Мнемоника - символическое обозначение команды/псевдокоманды.
Операнды - один или несколько операндов, обычно разделяемые запятыми. Операндами команд являются имена регистров, непосредственные операнды, адреса памяти.
Комментарии - любой текст, который игнорируется Ассемблером.

Операнды команд

Константы - могут представлять непосредственные операнды или абсолютные адреса памяти. Применяются 10-ные, 8-ные, 16-ные, 2-ные, символьные константы.
Непосредственные операнды - записываются в сам код команды.
Имена - адреса ячеек памяти. При трансляции Ассемблер преобразует имена в адреса. Способ преобразования имени в значение зависит от принятых способов адресации. Как правило, в основным способом адресации в машинных языках является адресация относительная: адрес в команде задается в виде смещения относительно какого-то базового адреса, значение которого содержится в некотором базовом регистре. В качестве базового могут применяться либо специальные регистры (DS, CS в Intel) или регистры общего назначения (S/390).
Литералы - записанные в особой форме константы. Концептуально литералы - те же имена. При появлении в программе литерала Ассемблер выделяет ячейку памяти и записывает в нее заданную в литерале константу. Далее все появления этого литерала Ассемблер заменяет на обращения по адресу этой ячейки. Таким образом, литеральные константы, хранятся в памяти в одном экземпляре, независимо от числа обращений к ним.
Специальный синтаксис - явное описание способа адресации (например, указание базового регистра и смещения и т.п.).
Директивы
Директивы являются указаниями Ассемблеру о том, как проводить ассемблирование. Рассмотрим несколько практически обязательных директив (мнемоники директив везде - условные, в конкретных Ассемблерах те же по смыслу директивы могут иметь другие мнемоники).
EQU
Определение имени. Перед этой директивой обязательно стоит имя. Операнд этой директивы определяет значение имени. Операндом может быть и выражение, вычисляемое при ассемблировании. Имя может определяться и через другое имя, определенное выше. Как правило, не допускается определение имени со ссылкой вперед.

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

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

END
Конец программного модуля. Указание Ассемблеру на прекращение трансляции. Обычно в модуле, являющемся главным (main) операндом этой директивы является имя точки, на которую передается управление при начале выполнения программы. Во всех других модулях эта директива употребляется без операндов.

Базы данных Ассемблера
[ Cкачайте файл, чтобы посмотреть картинку ]
Алгоритмы работы Ассемблеров
Ассемблер просматривает исходный программный модуль один или несколько раз. Наиболее распространенными являются двухпроходные Ассемблеры, выполняющие два просмотра исходного модуля. На первом проходе Ассемблер формирует таблицу символов модуля, а на втором - генерирует код программы
Двухпроходный Ассемблер - 1-й проход
Алгоритм работы 1-го прохода двухпроходного Ассемблера.
1. Начальные установки:
установка в 0 счетчика адреса PC;
создание пустой таблицы символов;
создание пустой таблицы литералов;
открытие файла исходного модуля;
установка в FASLE признака окончания.
Считывание следующей строки исходного модуля. Добавка к счетчику адреса устанавливается равной 0.
При считывании был обнаружен конец файла?
Если конец файла обнаружен до того, как обработана директива END, - ошибка (преждевременный конец файла), при этом также устанавливается признак окончания обработки..
Лексический разбор оператора программы. При этом:
выделяется метка/имя, если она есть;
выделяется мнемоника операции;
выделяется поле операндов;
удаляются комментарии в операторе;
распознается строка, содержащая только комментарий.
Строка содержит только комментарий? В этом случае обработка оператора не производится.
Мнемоника операции ищется в таблице директив.
Завершился ли поиск в таблице директив успешно?
Если мнемоника была найдена в таблице директив, происходит ветвление, в зависимости от того, какая директива была опознана.
Обработка директив типа DD (определения данных).

2.1.2. Макроязыки
Рассмотрим возможности макроязыка, в той или иной форме реализованные во всех Макропроцессорах.

Заголовок макроопределения

Макроопределение должно как-то выделяться в программе, поэтому оно всегда начинается с заголовка. Заголовок имеет формат, подобный следующему:
имя_макрокоманды MACRO список формальных параметров
имя_макрокоманды является обязательным компонентом. При макровызове это имя употребляется в поле мнемоники оператора. Имена макроопределений, имеющихся в программе, должны быть уникальны. Обычно при распознавании макровызова поиск по имени макрокоманды ведется сначала среди макроопределений имеющихся в программе, а затем (если в программе такое макроопределение не найдено) - в библиотеках макроопределений. Таким образом, имя макрокоманды, определенной в программе, может совпадать с именем макрокоманды, определенной в библиотеке, в этом случае макрокоманда, определенная в программе, заменяет собой библиотечную.
Формальные параметры играют ту же роль, что и формальные параметры процедур/функций. При обработке макровызова вместо имен формальных параметров в теле макроопределения подставляются значения фактических параметров макровызова.
В развитых Макроязыках возможны три формы задания параметров: позиционная, ключевая и смешанная. При использовании позиционной формы соответствие фактических параметров формальным определяется их порядковым номером. (Позиционная форма всегда применяется для подпрограмм).
Пример:
Заголовок макроопределения
Макровызов
Результат подстановки

M1 MACRO A,B,C
M1 X,Y,Z
A=X, B=Y, C=Z

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

M1 MACRO A=Q,B=,C=R
M1 C=Z,B=X
A=Q, B=X, C=Z

В смешанной форме первые несколько параметров подчиняются правилам позиционной формы, а остальные - ключевые.
Пример:
Заголовок макроопределения
Макровызов
Результат подстановки

M1 MACRO A,B,C=Q,D=,E=R
M1 X,Y,Z,D=T,E=S
A=X,B=Y,C=Q,D=T,E=S

В некоторых Макропроцессорах имена параметров начинаются с некоторого отличительного признака (например, амперсанда - &), чтобы Макропроцессор мог отличить "свои" имена (имена, подлежащие обработке при обработке макроопределения) от имен, подлежащих обработке Ассемблером. Возникает проблема распознавания имени в теле макроопределения. Например, если макроопределение имеет формальный параметр &P, а в макровызове указано для него фактическое значение 'X', то как должна обрабатываться подстрока '&PA' в теле макроопределения? Должна ли эта подстрока быть заменена на 'XA' или оставлена без изменений?
Логика, которой следует большинство Макропроцессоров в этом вопросе, такова. &PA является именем в соответствии с правилами формирования имен. Поэтому оно не распознается как имя &P и остается без изменений. Если мы хотим, чтобы подстановка в этой подстроке все-таки произошла, следует поставить признак, отделяющий имя параметра от остальной части строки. Обычно в качестве такого признака используется точка - '.': '&P.A' заменяется на 'XA'.
Окончание макроопределения
Конец макроопределения определяется оператором MEND. Этот оператор не требует параметров. Макроопределение, взятое в "скобки" MACRO - MEND может располагаться в любом месте исходного модуля, но обычно все макроопределения размещают в начале или в конце модуля.

Локальные переменные макроопределения

Поскольку генерация макрорасширения ведется по некоторому алгоритму, описанному в макроопределении, реализация этого алгоритма может потребовать собственных переменных. Эти переменные имеют силу только внутри данного макроопределения, в макрорасширении не остается никаких "следов" переменных макроопределения.
Переменные макроопределения могут использоваться двумя способами:
их значения могут подставляться вместо их имен в тех операторах макроопределения, которые переходят в макрорасширение;
их значения могут проверяться в условных операторах макроязыка и влиять на последовательность обработки.
При подстановке значений переменных макроопределения в макрорасширение работают те же правила, что и при подстановки значений параметров.
Для сильносвязанных Макропроцессоров необходимости в локальных переменных макроопределения, вместо них могут использоваться имена программы (определяемые директивой EQU). Для сильносвязанных и независимых процессоров переменный макроопределения и имена программы должны различаться, для этого может применяться тот же признак, что и для параметров макроопределения. Объявление локальной переменной макроопределения может иметь, например, вид:
имя_переменной LOCL начальное_значение (последнее необязательно)
Присваивание значений переменным макроопределения
Присваивание может производиться оператором вида:
имя_переменной SET выражение
или
имя_переменной = выражение
Выражения, допустимые при присваивании, могут включать в себя имена переменных и параметров макроопределения, константы, строковые, арифметические и логические операции, функции. Основной тип операций - строковые (выделение подстроки, поиск вхождения, конкатенация. etc.), так как обработка макроопределения состоит в текстовых подстановках. Строковые операции обычно реализуются в функциях. Однако, в некоторых случаях может потребоваться выполнение над переменными макроопределения операций нестрокового типа. Как обеспечить выполнение таких операций? Можно предложить два варианта решения этой проблемы:
Ввести в оператор объявления переменной макроопределения определение ее типа. При выполнении операций должно проверяться соответствие типов.
Все переменные макроопределения имеют строковый тип, но при вычислении выражений автоматически преобразуются к типу, требуемому для данной операции (при таком преобразовании может возникать ошибка). Результат выражения автоматически преобразуется в строку.
Как правило, операции присваивания могут применяться к параметрам макроопределения точно так же, как и к переменным макроопределения.
Глобальные переменные макроопределения
Значения локальных переменных макроопределения сохраняются только при обработке данного конкретного макровызова. В некоторых случаях, однако, возникает необходимость, чтобы значение переменной макроопределения было запомнено Макропроцессором и использовано при следующем появлении той же макрокоманды в данном модуле. Для этого могут быть введены глобальные переменные макроопределения.
Объявление глобальной переменной макроопределения может иметь, например, вид:
имя_переменной GLBL начальное_значение (последнее необязательно)
Присваивание значений глобальным переменным макроопределения выполняется так же, как и локальным.
Уникальные метки
В некоторых случаях операторы машинных команд, имеющихся в макроопределении, должны быть помечены, например, для того, чтобы передавать на них управление. Если применить для этих целей обычную метку, то может возникнуть ошибочная ситуация. Если метка в макроопределении имеет обычное имя, и в модуле данная макрокоманда вызывается два раза, то будет сгенерировано два макрорасширения, и в обоих будет метка с этим именем. Чтобы избежать ситуации неуникальности меток, в макроязыке создается возможность определять метки, для которых формируются уникальные имена. Обычно имя такой метки имеет тот же отличительный признак, который имеют параметры и переменные макроопределения. Каждую такую метку Макропроцессор заменяет меткой с уникальными именем.
Уникальное имя метки может формироваться формате, подобном следующему:
&имя.nnnnnn
где - nnnnnn - число, увеличивающееся на 1 для каждой следующей уникальной метки.
Другой возможный способ формирования, например:
имя&SYSNDX
где SYSNDX - предустановленное имя, имеющее числовое значение, начинающееся с 00001 и увеличивающееся на 1 для каждой следующей уникальной метки.
Следующие операторы Макроязыка влияют на последовательность обработки операторов макроопределения. В тех или иных Макропроцессорах имеется тот или иной набор таких операторов.
Оператор безусловного перехода и метки макроопределения
Возможный формат оператора:
MGO макрометка
Концептуально важным понятием является макрометка. Макрометка может стоять перед оператором Макроязыка или перед оператором языка Ассемблера. Макрометки не имеют ничего общего с метками в программе. Передача управления на макрометку означает то, что при обработке макроопределения следующим будет обрабатываться оператор, помеченный макрометкой. Макрометки должны иметь какой-то признак, по которому их имена отличались бы от имен программы и переменных макроопределения. Например, если имена переменных макроопределения начинаются с символа &, то имя макрометки может начинаться с &&.
Оператор условного перехода
Возможный формат оператора:
MIF условное_выражение макрометка
Если условное_выражение имеет значение "истина", обработка переходит на оператор, помеченный макрометкой, иначе обрабатывается следующий оператор макроопределения.
Условные блоки
Возможный формат оператора:
IF условное_выражение
операторы_макроопределения_блок1
ENDIF
ELSE
операторы_макроопределения_блок2
ENDIF
Если условное_выражение имеет значение "истина", обрабатываются операторы макроопределения от оператора IF до оператора ENDIF, иначе обрабатываются операторы макроопределения от оператора ESLE до оператора ENDIF. Как и в языках программирования блок ELSE - ENDIF не является обязательным.
Условные выражения описаны выше. Обычно предусматриваются специальные формы:
IFDEF имя
IFNDEF имя
проверяющие просто определено или не определено данное имя.
Операторы условных блоков довольно часто являются не операторами Макроязыка, а директивами самого языка Ассемблера.
Операторы повторений
Операторы повторений Макроязыка (или директивы повторений языка Ассемблера) заставляют повторить блок операторов исходного текста, возможно, с модификациями в каждом повторении. Операторы повторений играют роль операторов цикла в языках программирования, они не являются обязательными для макроязыка, так как цикл можно обеспечить и условным переходом.
Как и в языках программирования, в Макроязыке может быть несколько форм операторов повторения, приведем некоторые из возможных форм:
MDO выражение
блок_операторов_макроопределения
ENDMDO
выражение должно иметь числовой результат, обработка блока операторов повторяется столько раз, каков результат вычисления выражения.
MDOLIST переменная_макроопределения,список_выражений
блок_операторов_макроопределения
ENDMDO
обработка блока операторов повторяется столько раз, сколько элементов имеется в списке_выражений, при этом в каждой итерации переменной_макроопределения присваивается значение очередного элемента из списка_выражений.
MDOWHILE условное_выражение
блок_операторов_макроопределения
ENDMDO
обработка блока операторов повторяется до тех пор, пока значение условного_выражения - "истина".
Завершение обработки
Обработка макроопределения завершается при достижении оператора MEND. Однако, поскольку алгоритм обработки макроопределения может разветвляться, должна быть предусмотрена возможность выхода из обработки и до достижения конца макроопределения. Эта возможность обеспечивается оператором MEXIT. Операндом этого оператора может быть код_серьезности.


Тема 2.2.Трансляторы
2.3.1.  Трансляторы. Компиляторы и интерпретаторы. Мобильность программного обеспечения
Под трансляцией в самом широком смысле можно понимать процесс восприятия компьютером программы, написанной на некотором формальном языке. При всем своем различии формальные языки имеют много общего и, в принципе, эквиваленты с точки зрения потенциальной возможности написать одну и ту же программу на любом из них.
Компиляция - преобразование объектов (данных и операций над ними) с входного языка в объекты на другом языке для всей программы в целом с последующим выполнением полученной программы в виде отдельного шага.
Интерпретация - анализ отдельного объекта на входном языке с одновременным выполнением (интерпретацией).
Следовательно, компиляция и интерпретация отличаются не характером и методами анализа и преобразования объектов программы, а совмещением фаз обработки этих объектов во времени. То есть при компиляции фазы преобразования и выполнения действий разнесены во времени, но зато каждая из них выполняется над всеми объектами программы одновременно. При интерпретации, наоборот, преобразование и выполнение действий объединены во времени, но для каждого объекта программы.
Интерпретатор непосредственно выполняет действия, связанные с определением или преобразованием объектов программы, а компилятор - переводит их на другой (не обязательно машинный язык). Отсюда можно сделать несколько выводов:

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

· процессор и память любого компьютера (а в широком смысле и вся программная среда, создаваемая операционной системой, является интерпретатором машинного кода);

· в практике построения трансляторов часто встречается случай, когда программа компилируется с входного языка на некоторый промежуточный уровень (внутренний язык), для которого имеется программный интерпретатор. Многие языковые системы программирования, называемые интерпретаторами, на самом деле имеют фазу компиляции во внутренне представление, на котором производится интерпретация.
Выходной язык компилятора может быть машинным языком для компьютера с другой архитектурой, нежели тот, в котором работает компилятор. Такой компилятор называется кросс-компилятором, а сама система программирования кросс-системой программирования. Такие системы используются для разработки программ для архитектур, не имеющих собственных операционных систем или систем программирования (контроллеры, управляющие микропроцессоры).
Таким образом, граница между компиляцией и интерпретацией в трансляторе может перемещаться от входного языка (тогда мы имеем чистый интерпретатор) до машинного кода (тогда речь идет о чистом компиляторе).
Создание слоя программной интерпретации для некоторого промежуточного языка в практике построения трансляторов обычно встречается при попытке обеспечить мобильность (переносимость) программного обеспечения для имеющегося многообразия языков программирования, операционных систем, архитектур и т.д. То есть определяется некоторый внутренний промежуточный язык, достаточно простой, чтобы для него можно было написать интерпретатор для всего имеющегося многообразия операционных систем или архитектур. Затем пишется одни (или несколько) компиляторов для одного (или нескольких) входных языков на этот промежуточный уровень. Приведем примеры такой стандартизации:
для обеспечения совместимости и переносимости трансляторов на компьютеры с различной архитектурой или с различными операционными системами был разработан универсальный внутренний язык (P-код). Для каждой такой архитектуры необходимо реализовать свой интерпретатор P-кода. При этом все разнообразие имеющихся компиляторов с языков высокого уровня на P-код может быть использовано без каких-либо изменений.
язык программирования Java аналогично был разработан для обеспечения переносимости различных приложений в среде Internet.
Фазы трансляции и выполнения программы
Подготовка программы начинается с редактирования файла, содержащего текст этой программы, который имеет стандартное расширение для данного языка. Затем выполняется его трансляция, которая включает в себя несколько фаз: препроцессор, лексический, синтаксический, семантический анализ, генерация кода и его оптимизация. В результате трансляции получается объектный модуль - некий «полуфабрикат» готовой программы, который потом участвует в ее сборке. Файл объектного модуля имеет стандартное расширение obj. Компоновка (сборка) программы заключается в объединении одного или нескольких объектных модулей программы и объектных модулей, взятых из библиотечных файлов и содержащих стандартные функции и другие полезные вещи. В результате получается исполняемая программа в виде отдельного файла (загрузочный модуль, программный файл) со стандартным расширением -".exe", который затем загружается в память и выполняется.
Препроцессор
Препроцессор - предварительная фаза трансляции, которая выполняет обработку текста программы. Он производит замену одних частей текста на другие, при этом сама программа так и остается в исходном виде.
 В языке Си директивы препроцессора оформлены отдельными строками программы, которые начинаются с символа "#". Например
#define идентификатор строка_текста
Директива обеспечивает замену встречающегося в тексте программы идентификатора на соответствующую строку текста. Наиболее часто она применяется для символического обозначения константы, которая встречается многократно в различных частях программы. Например, размерность массива:
#define SIZE 100
int A[SIZE];
for (i=0; iВ данном примере вместо имени SIZE в текст программы будет подставлена строка, содержащая константу 100.
#define идентификатор(параметры) строка_с_параметрами
Директива отдаленно напоминает определение функции с формальными параметрами, где вместо тела функции используется строка текста. Если препроцессор находит в тексте программы указанный идентификатор со списком фактических параметров в скобках, то он подставляет вместо него соответствующую строку из директивы define с заменой в строке формальных параметров на фактические. Основное отличие от функции: если функция реализует подобные действия (подстановка параметров, вызов) во время работы программы, то препроцессор - еще до трансляции. Кроме этого, директива define позволяет оформить в таком виде любую часть программы, независимо от того, законченная это конструкция языка или ее фрагмент. В следующем примере стандартный заголовок цикла for представлен в виде директивы define с параметрами:
 
#define FOR(i,n) for(i=0; iFOR(k,20) A[k]=0; // for(k=0; k<20; k++) A[k]=0;
FOR(j,m+2) {...} // for(j=0; jВ таком варианте директива define представляет собой макроопределение, а замена в тексте программы идентификатора с параметрами на строку -макроподстановку.
#include <имя_файла>
#include "имя_файла"
В текст программы вместо указанной директивы включается текст файла, находящегося в системном или, соответственно, в текущем (явно указанном) каталоге. Наиболее часто в программу включаются тексты заголовочных файлов, содержащие необходимую информацию транслятору о внешних функциях, находящихся в других объектных модулях и библиотеках. Например,
#include
включает в программу текст заголовочного файла, содержащего объявления внешних функций из библиотеки стандартного ввода-вывода (выполняет подключение библиотек).

Трансляция и ее фазы

Собственно трансляция начинается с лексического анализа программы. Лексика языка программирования - это правила «правописания слов» программы, таких как идентификаторы, константы, служебные слова, комментарии. Лексический анализ разбивает текст программы на указанные элементы. Особенность любой лексики - ее элементы представляют собой регулярные линейные последовательности символов. Например, идентификатор - это произвольная последовательность букв, цифр и символа "_", начинающаяся с буквы или "_".
Синтаксис языка программирования - это правила составления предложений языка из отдельных слов.
Семантика языка программирования - это смысл, который закладывается в каждую конструкцию языка. Семантический анализ - это проверка смысловой правильности конструкции. Например, если мы в выражении используем переменную, то она должна быть определена ранее по тексту программы, а из этого определения может быть получен ее тип. Исходя из типа переменной, можно говорит о допустимости операции с данной переменной.
Генерация кода - это преобразование элементарных действий, полученных в результате лексического, синтаксического и семантического анализа программы, в некоторое внутреннее представление. Это могут быть коды команд, адреса и содержимое памяти данных, либо текст программы на языке Ассемблера, либо стандартизованный промежуточный код (например, P-код). В процессе генерации кода производится и его оптимизация.

Структура компилятора и интерпретатора. Этапы, фазы и проходы компилятора

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

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

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

Лексический, синтаксический и семантический анализаторы

Первая фаза трансляции – лексический анализ. На этом этапе исходный текст программы «нарезается» на лексемы – последовательности входных символов (литер), допускающие альтернативу (выбор), повторение и взаимное пересечение в процессе распознавания не более чем на заданную глубину. Элементами лексики являются идентификаторы, константы, строки, комментарии, одно- и многосимвольные знаки операций и т.п.. Механизм распознавания базируется на простых системах распознавания, имеющих всего одну единицу памяти (текущее состояние) и табличное описание правил поведения (конечный автомат). Результат классификации лексем (классы лексем) является входной информацией для синтаксического анализатора (класс лексемы называется на входе синтаксического анализатора символом). Значения лексем поступают на вход семантического анализатора в виде первичного заполнения семантических таблиц.
[ Cкачайте файл, чтобы посмотреть картинку ]
Рисунок 2-2 – схема процесса трансляции
Синтаксический анализ является центральным элементом транслятора и выполняется с помщью синтаксического анализатора.. Во-первых, потому что синтаксис характеризует элементы, относящиеся к структуре программы: описания и определения данных, функций, классов и других элементов программы, операторы, выражения – это все синтаксические элементы разных уровней. Кроме того, вся программа представляет собой одно синтаксическое целое. Задачей синтаксического анализа является построение структуры – синтаксического дерева, отражающего взаимное расположение всех синтаксических элементов программы (их порядка следования, повторяемости, вложенности, приоритетов). Средством описания синтаксиса являются формальные грамматики, а их свойства используются для построения распознавателей, базирующихся на табличном описании правил их поведения в сочетании со стековой памятью (магазинные автоматы).
Лексический и синтаксический анализ являются формализованными компонентами языка, как с точки зрения их описания (конечные автоматы и формальные грамматики), так и с точки зрения проектирования распознавателей для них (для чего используются известные методы и алгоритмы).
Заключительная фаза трансляции – семантический анализ, а также фаза синтеза – генерация кода (оптимизация) или интерпретация - привязаны к синтаксису (и, соответственно, к синтаксическому анализатору), поскольку интерпретируют «смысловое» содержание и правила преобразования (или исполнения) элементарных синтаксических единиц, выделенных синтаксическим анализатором. Особенностью семантического анализа является то, что он менее привязан к структуре программы: семантика одного и того же объекта программы может определяться синтаксически не связанными элементами программы. Во-вторых, семантический анализ не формализуем, поскольку семантика программы представляется в процессе трансляции уникальной структурой данных, содержащей описания множеств объектов языка, определенных в программе, их свойств и взаимосвязей (семантические таблицы). Работа с такими таблицами производится через и семантические процедуры, соответствующие элементам синтаксиса (правила грамматики), которые также разрабатываются содержательным образом, не имея под собой формальной основы. Генерация кода и оптимизация также проектируются содержательными методами и содержат много специфических моментов, касающихся особенностей проецирования традиционных объектов языков программирования на элементы архитектуры компьютера (распределение памяти под переменные, распределение регистров под промежуточные результаты и оптимизация их использования и т.п..).
Генератор кода. Распределение памяти. Виды переменных

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

·  при определении языка;

·  при реализации компилятора;

·  во время трансляции, включающей в себя:

·  при работе препроцессора (макропроцессор)

·  во время лексического, синтаксического и семантический анализа, генерации кода и его оптимизации;

·  при компоновке (связывании);

·  во время загрузки программы;

·  во время выполнения программы, в том числе:

·  при входе в модуль (процедуру, функцию);

·  в произвольной точке выполнения программы.
В качестве примера рассмотрим простейший фрагмент программы, для которого перечислим более-менее полный перечень времен связывания его различных свойств с элементами архитектуры компьютера:
 
int a,b; a+b
 
1.  Тип переменных int - как способ определения целой переменной в машинном слове стандартной длины (представление целого со знаком, дополнительный код), связывается с аналогичной формой представления данных в компьютере при определении языка. Язык Си характерен тем, что базовые типы данных в нем полностью совпадают с соответствующими формами представления данных в компьютере.
2.  Конкретная размерность переменной int определяется при реализации соответствующего компилятора.
3.  Имя a может быть определено в конструкции вида #define a 0x11FF. В этом случае имя (псевдо-переменная) связывается со своим значением на первой фазе трансляции - в препроцессоре.
4.  Если переменная определяется обычным способом в виде int a; то связывание переменной с соответствующим ей типом происходит во время трансляции (на фазе семантического анализа).
5.  Если переменная определяется как внешняя (глобальная, вне тела функции), то смысл ее трансляции заключается в распределении под нее памяти в сегменте данных программы, который создается для текущего модуля (файла). Но при этом сама распределенной памяти к конкретной оперативной памяти осуществляется в несколько этапов:

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

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

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

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

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

·  связывание локальным переменной с ее адресом в сегменте стека осуществляется при выполнении в момент входа в тело функции (блок). Благодаря такому способу связывания в рекурсивной функции существует столько «экземпляров» локальных переменных, сколько раз функция вызывает сама себя.
7.  Тип операции “+” в конкретном выражении a+b определяется при трансляции в зависимости от типов операндов. В данном случае генерируется операция целого сложения.
8.  С точки зрения времени связывания понятие инициализация внешних переменных можно определить как связывание переменных с их значениями в процессе трансляции программы (int a=10;) С этой точки зрения обычное присваивание можно рассматривать как связывание переменной с ее значением во время выполнения программы.
С понятием связывания тесно переплетаются понятия статического и динамического определения данных. Статически определенные данные имеют раннее время связывания - обычно во время трансляции программы, динамические данные - позднее, во время выполнения. Этот принцип легко проиллюстрировать средствами языка Си, в котором все действия, связанные с динамическими данными и поздним связыванием производятся только в явном виде. Возьмем, к примеру, массивы:

·  обычное статическое определение массива предполагает его связывание с памятью во время трансляции программы, поэтому тип сохраняемых в нем элементов и их количество должны быть величинами неизменными:
int A[100];

·        динамический массив, размерность которого определяется в процессе работы программы, может быть вычислена в момент создания, но затем не меняется , может быть представлен в Си указателем на динамическую переменную (массив) соответствующей размерности, создаваемую и уничтожаемую внешними функциями. Легко представить себе язык программирования, в котором массивы такого рода определяются в самом трансляторе, в этом случае можно говорить о связывании массива с его размерностью и памятью во время выполнения программы, например, в момент входа в модуль (блок):
 
double *p;
p = malloc(sizeof(double)*n); // или
p = new double[n];
for (i=0; i// ПРИМЕР СИНТАКСИСА ДИНАМИЧЕСКОГО МАССИВА
// n = getnum();
// ReDim double A[n];
 

·  виртуальный массив, размерность которого может меняться уже в процессе работы программы, по мере заполнения его данными, в Си также может быть смоделирован с использованием функций перераспределения динамической памяти realloc. При определении таких массивов в самом трансляторе можно говорить о связывании массива с его размерностью и памятью во время выполнения программы, причем многократной, во время заполнения его данными, то есть в любой точке программы:
 
double *p; int n=10;
p = malloc(sizeof(double)*n);
for (i=0; i<10000; i++)
{
if (i >= n) // Если надо,
{ n = n+10; // увеличить размерность
p = realloc(p, sizeof(double)*n);
}
p[i] = 5.44
}
// ПРИМЕР СИНТАКСИСА ВИРТУАЛЬНОГО МАССИВА
// ReDim double A[];
// for (i=0; i<10000; i++) A[i]=5.44;
 

· виртуальный массив, в котором может меняться не только размерность, но и типы хранящихся в нем элементов, можно смоделировать в Си с помощью динамического массива указателей на переменные - элементы массива:
 
void **p; int n=10;
p = malloc(sizeof(void*)*n);
int b; double c;
i = 5;
if (i >= n) // Если надо,
{ n = i+10; // увеличить размерность
p = realloc(p, sizeof(void *)*n);
}
p[i] = &b;
// ПРИМЕР СИНТАКСИСА ВИРТУАЛЬНОГО МАССИВА
// С ПРОИЗВОЛЬНЫМИ ТИПАМИ ЭЛЕМЕНТОВ
// ReDim A[];
// int b; double c;
// A[5] = b;
// A[66]= c;
 
Из рассмотренного примера видно, что реализация позднего связывания в языках программирования связана с использованием неявных (скрытых) указателей на структуры данных. Это предположение можно подтвердить и примером связывания для такого объекта, как функция:

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

·  если функция вызывается в том же самом модуле, где она определена, то связывание вызова функции с ее телом (адресом) осуществляется в процессе трансляции;

·  если функция определена в другом модуле (частный случай, библиотека), то связывание вызова функции с ее телом (адресом) осуществляется при компоновке. Для этой цели тело функции в объектном модуле сопровождается информацией, именуемой “точкой входа”, сам вызов сопровождается “внешней ссылкой”, а для корректного формирования вызова Си-компилятору необходимо объявить прототип внешней функции. Для библиотечных функций необходимо подключить заголовочный файл, в котором они содержатся.
В технологии объектно-ориентированного программирования существует фундаментальное понятие полиморфизма. В Си++ оно реализовано через виртуальные функции. Виртуальная функция представляет собой группу одноименных функций, определенных соответственно для группы родственных (производных классов). При вызове такой функции для объекта обобщающего их класса (базового класса) программа должна идентифицировать, к какому конкретно классу относится текущий объект, и выбрать соответствующую ему функцию. С точки зрения понятия связывания это означает, что связывание вызова функции с ее телом может осуществляться в таком случае только во время работы программы. Действительно, в Си++ механизм виртуальных функций реализуется при помощи массива указателей на функции, который назначения объекту в момент его создания (в конструкторе), то есть при выполнении программы.
К позднему (динамическому) связыванию функций относятся и используемые в Windows динамически связываемые библиотека (DLL - Dynamic Linking Library) . Фактически в них процесс связывания вызова и тела внешней функции, выполняемый при компоновке, откладывается до момента загрузки программы. В этом случае программный файл содержит несвязанные вызовы внешних функций (внешние ссылки) и перечень используемых библиотек. Загрузка требуемых библиотек и связывание внешних ссылок и точек вход производится в момент загрузки программного файла. Этот способ дополнительно позволяет разделять одну и ту же библиотеку нескольким программам в общем для них адресном пространстве.

Тема 2.3 Формальные языки и грамматики

2.3.1. Понятие грамматики для определения формальных языков

Компилятор должен создавать правильный целевой код при любом входе, принадлежащем исходному языку, для которого разработан компилятор, или же одно или несколько сообщений об ошибках, если это невозможно (вход является искаженным или неправильным). Проверка правильности входа требует определения языка, на котором написан исходный код. Это определение должно быть:
точным (или формальным);
лаконичным.
Определение языка должно определять все строки символов, существующих в данном языке (синтаксис языка), а также их значения или планируемый эффект (семантика языка). Если язык состоит из конечного числа строк, то его определение не представляет принципиальной сложности и заключается в перечислении всех элементов. В то же время, поскольку все интересующие нас языки содержат бесконечное число строк, требуется найти средство представления бесконечного числа строк конечным образом.
Рассмотрим несколько очень простых языков и продемонстрируем метод представления бесконечного числа строк символов, содержащихся в языке. Например, язык, состоящий из всех строк, которые содержат произвольное число символов х, можно описать следующим образом.
{xn | n>0}
Здесь знак "|" можно прочесть как "где", n целое, а умножение следует понимать как конкатенацию.
Другой пример языка.
{ xn yn | n>0}
Данный язык состоит из всех строк, которые состоят из одного или большего числа символов х, после чего следует такое же количество символов у. Например, этому языку могут принадлежать следующие строки.
ху
хххууу
ххххххххуууууууу
С другой стороны, определение
{ xm yn | m, n > 0}
представляет язык, состоящий из строк, в которых вначале располагается хотя бы один символ х, за которым следует хотя бы один у, причем число элементов х не обязательно должно совпадать с числом элементов у. Если язык можно определить следующим образом
{ xm yn | m, n
· 0}
тогда строки
ххх (нуль элементов у)
и
ууууууу (нуль элементов х)
также представляют возможные строки языка. При таком определении языка ему также принадлежит элемент (.
Этот элемент пустая строка, не содержащая ни знаков х, ни знаков у. Как будет показано далее, пустые строки играют важную роль в определении языков программирования.

Регулярные выражения
Рассмотренные выше языки можно также определить с помощью регулярных выражений, подобных приведенному ниже.
x *y*
Здесь символ "*" обозначает, что предшествующий ему элемент, употребляется нуль или большее число раз. Если в каждой строке языка должно находиться минимум по одному элементу х и у, то язык можно определить следующим образом - хх*уу*
Возможна альтернативная запись х+y+
Здесь плюс означает одно или большее число вхождений предшествующего элемента. Кроме того, в регулярных выражениях можно использовать символ "|" (в данном контексте читается как "или"). Таким образом, выражение х* | у* представляет определение языка, строки которого состоят из нуля или большего количества элементов x или из нуля или большего количества элементов у. Выражение (а | b)* представляет язык, строки которого состоят из нуля или большего числа элементов а или b (другими словами, строка состоит из нуля или большего числа знаков, каждый из которых может быть а или b). В последнем выражении скобки употребляются для того, чтобы показать более высокий приоритет знака | над знаком *. Принято, что знак * имеет более высокий приоритет, чем | , поэтому язык a | b*
будет содержать только строки, состоящие из одного элемента а или же нуля или большего числа элементов b. Приведем другой пример регулярного выражения
(aab | ab)*
Этот язык будет включать в себя следующие строки.
(
aababaab
ababab
aabaabaabab
Регулярное выражение (ааа | ab)*
иллюстрирует три оператора, используемых в регулярных выражениях, т.е. *, конкатенацию (представленную последовательными символами) и | , перечисленные в порядке убывания их приоритета.

Определение формальной грамматики

Формальная грамматика или просто грамматика определяется как четверка (VT, VN, P, S)
Здесь VT алфавит, символы которого называют терминальными символами, или терминалами;
VN алфавит с нетерминальными символами, или нетерминалами.
VT и VN не имеют общих символов (т.е. VT ( VN = ()
Р множество продукций (или правил), каждый элемент которого состоит из пары
((, (), где ( левая часть продукции, ( правая часть продукции, а сама продукция записывается следующим образом ( -> (
Здесь ( принадлежит V+ (строки, состоящие из одного или более символов
V= VT ( VN), a ( принадлежит V* (строки, состоящие из нуля или более символов V).
S принадлежит VN, называется символом предложения, или аксиомой грамматики, и с него начинается генерация любой строки языка.
Грамматика используется для генерации последовательностей символов, составляющих строки языка, начиная с аксиомы и последовательно заменяя ее (или нетерминалы, которые появятся позднее) с помощью одного из порождений грамматики. На каждом этапе к нетерминалу из левой части применяется продукция, заменяющая этот нетерминал последовательностью символов своей правой части. Процесс прекращается после получения строки, состоящей только из терминальных символов (т.е. не содержащей нетерминалов). Языку принадлежат те и только те строки символов, которые можно получить с помощью заданной грамматики. Можно считать, что с помощью грамматики выполняется вывод цепочек, принадлежащих языку.

Типы грамматик

Хомский определил четыре класса грамматик, которые назвал грамматиками 0-го ... 3-го типов. Грамматики 0-го типа, или рекурсивно перечислимые (recursively enumerable) грамматики, определяются как все грамматики, которые соответствуют данному выше определению без ограничений на типы продукций. Данные грамматики это наиболее общий класс. Грамматики других типов могут быть получены путем наложения ограничений на возможные формы продукций грамматик 0-го типа.
Грамматики 0-го типа эквивалентны машинам Тьюринга в том смысле, что для любой данной грамматики 0-го типа существует машина Тьюринга, которая допускает, и только допускает, все предложения, сгенерированные данной грамматикой. И наоборот, для данной машины Тьюринга существует грамматика 0-го типа, которая генерирует точно все предложения, допускаемые машиной Тьюринга.
Первое ограничение на форму продукции, которое может возникнуть в грамматике, задать, чтобы для всех продукций вида ( -> ( длина строки а (исчисляемая в количестве символов, которое она может содержать) была не больше длины строки | ( | ( | ( |
Грамматики, все продукции которых подчиняются данному ограничению, называются грамматиками 1-го типа, или контекстно-зависимыми (context sensitive). Если обратиться к теории автоматов, грамматики 1-го типа эквивалентны линейно ограниченным автоматам в том же смысле, как грамматики 0-го типа эквивалентны машинам Тьюринга. Следует отметить, что рассмотренная выше грамматика для языка
{ аm | m является неотрицательной степенью двойки} является грамматикой 0-го, а не 1-го типа, поскольку в продукции Q -> ( левая часть длиннее правой.
Если (помимо уже названного ограничения) в левой части продукции должен находиться только один нетерминал, грамматика называется грамматикой 2-го типа, или контекстно-свободной (КС) грамматикой. За исключением G3, все рассмотренные в этой теме грамматики принадлежат ко 2-му типу.
Теория компиляторов практически полностью основывается на грамматиках 2-го и 3-го типов. Например, для распознавания цепочек символов КС языка используются магазинные автоматы (автоматы с магазинной памятью, МП).

Вывод цепочек

Регулярные выражения
Чтобы формально определить понятие регулярного выражения, введем вначале понятие алфавита. Алфавит представляет собой конечный набор символов, подобный приведенным ниже.
{0,1} {а..я} {0..9}
Если А алфавит, то к числу регулярных выражений относятся:
нулевая строка (обозначается ();
любой элемента А.
Кроме того, если Р и Q являются регулярными выражениями, то регулярными являются также следующие выражения.
PQ (Q следует после Р)
P | Q (Р или Q)
P* (нуль или более вхождений Р)
Следует отметить, что введенный ранее оператор + (одно или более вхождений элемента), строго говоря, не является оператором регулярного выражения, поскольку при описании любого регулярного выражения можно обойтись и без него. Это связано с тем, что любое выражение, содержащее +, можно заменить эквивалентным выражением, содержащим оператор конкатенации и оператор *. Например, выражение
(abc)+
эквивалентно записывается следующим образом (abc)(abc)*
Регулярные выражения часто употребляются для определения символов языков программирования через составляющие их знаки. Например, во многих языках программирования идентификатор можно представить следующим регулярным выражением
I ( I | d)*
Здесь I обозначает букву, a d цифру. Число с фиксированной запятой можно пред-ставить следующим выражением.
(d*d.d*) | (d*.dd*)
Здесь d также обозначает любую цифру.
Один из языков, ранее рассмотренных в данном разделе,
{ xn yn | n>0}
невозможно определить посредством регулярного выражения, поскольку в регулярных выражениях не существует возможности указать, что количество элементов х должно равняться количеству элементов у. Следовательно, в этом случае нам необходим более мощный механизм, который позволит описать такой очевидно простой язык. Один из методов заключается в использовании продукции (production), подобной приведенным ниже.
S->xSy
S->xy
Здесь символ "->" можно читать как "может иметь вид". Продукции могут использоваться для генерации строк языка с использованием следующих правил:
Начать с символа S и заменить его строкой, расположенной справа от знака продукции.
Если полученная строка не содержит больше символов S, она является строкой языка. В противном случае следует снова заменить S строкой после знака продукции, а затем снова вернуться к п. 2.
Приведем пример последовательности строк.
S
xSy
xxSyy
хххууу
Обычно подобную последовательность записывают следующим образом:
S => xSy => xxSyy => хххууу
Здесь знак "=>" читается "порождает". Последовательность шагов, использованная для генерации строки с применением продукций грамматики, называется порождением (derivation) строки.
Очевидно, что описанным выше способом могут быть получены все строки языка
{ xn yn | n>0}
При этом не будет порождена ни одна строка, не принадлежащая указанному языку.
Определим понятия грамматики, основываясь на введенном выше понятии продукции.

Формальные грамматики и вывод цепочек

Например, грамматикой для языка
{ xn yn | n>0}
будет грамматика G1.
G1 = ({х, y}, {S}, P, S)
Здесь P={S->xSy, S->xy}
Грамматикой для языка { xm yn | m, n
· 0} является G2.
G2 = ({х, у], {S, B}, Р, S)
Здесь набор продукций Р имеет следующий вид.
S ->xS
S->yB
S->x
S->y
B->yB
B->y
Поскольку пустая строка также принадлежит языку, то в набор Р входит следующая продукция S ->(
Строка ххууу генерируется следующим образом:
S => xS => xxS => xxyB => ххууВ => ххууу
Каждая из строк, фигурирующих в порождении, называется сентенциальной формой (sentential form), а последняя строка (состоящая только из терминалов) называется предложением (sentence) языка. Использование символа "=>" между двумя сентенциальными формами обозначает, что строка справа от этого символа получена из строки слева от него посредством одного порождения. В то же время можно записать следующее выражение
*
S => хууу
Это означает, что хууу порождается из S за нуль или более шагов. Подобным образом выражение
+ S => ххууу
означает, что хууу порождается из S за один или более шагов. Условимся, что порождения
B->уВ
В-> у
можно записать в более сжатой форме
В -> уВ | у
Здесь, как и ранее, символ "|" читается как "или".
Как и в приведенных выше примерах, будем, как правило, использовать строчные буквы (иногда слова, состоящие только из строчных букв) для обозначения терминалов грамматики, а заглавные буквы (иногда слова из заглавных букв) для обозначения нетерминалов. Символы предложений часто будут обозначаться буквой S, хотя это обозначение не является обязательным. Греческие буквы будут использоваться для обозначения строк терминалов и/или нетерминалов.

Магазинный автомат

В общем виде МП-автомат можно определить следующим образом:
R(Q, V, Z, (,q0,z0,F),
где Q множество состояний автомата;
V алфавит входных символов автомата;
Z специальный конечный алфавит магазинных символов автомата (обычно он включает в себя алфавиты терминальных и нетерминальных символов грамматики),
V ( Z;
( функция переходов автомата, которая отображает множество Qx(V ({(})xZ на конечное множество подмножеств P(QxZ');
q 0 ( Q начальное состояние автомата;
z0 ( Z начальный символ магазина;
F ( Q множество конечных состояний.
МП-автомат в отличие от обычного конечного автомата (КА) имеет стек (магазин), в который можно помещать специальные «магазинные» символы (обычно это терминальные и нетерминальные символы грамматики языка). Переход из одного состояния в другое зависит не только от входного символа, но и от одного или нескольких верхних символов стека. Таким образом, конфигурация автомата определяется тремя параметрами: состоянием автомата, текущим символом входной цепочки (положением указателя в цепочке) и содержимым стека.

13 SHAPE \* MERGEFORMAT 1415

Рисунок 2 -3. Общая условная схема автомата с магазинной памятью (МП-автомата)

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

Распознаватели и преобразователи

Синтаксический и лексический анализатор
Одной из особенностей такого подхода к разбору строк является то, что анализ выполняется по мере считывания символов, с использованием информации о текущем символе и символах, прочитанных ранее. Синтаксический анализатор это программа или часть программы, выполняющая [ Cкачайте файл, чтобы посмотреть ссылку ], на первом шаге которого выполняется [ Cкачайте файл, чтобы посмотреть ссылку ], далее строится дерево разбора. Синтаксический анализатор входит в структуру [ Cкачайте файл, чтобы посмотреть ссылку ]. Конструкции, распознаваемые [ Cкачайте файл, чтобы посмотреть ссылку ] описываются автоматной [ Cкачайте файл, чтобы посмотреть ссылку ] и [ Cкачайте файл, чтобы посмотреть ссылку ]. На первом этапе лексического анализа происходит построение конечного автомата по регулярному выражению, затем строится таблица переходов для конечного автомата, а далее входной поток символов интерпретируется анализатором в выходной поток лексем. Определим понятие [ Cкачайте файл, чтобы посмотреть ссылку ].
Конечным автоматом-распознавателем называется следующий набор объектов А={S,X,So,
·,F}, где:
S – конечное непустое множество состояний
Х – конечное непустое множество входных сигналов(входной алфавит)
So – начальное состояние

·:S*XS – функция переходов
F – множество заключительных состояний
Конечный автомат-распознаватель А допускает входную цепочку
·, принадлежащую алфавиту, если
· переводит его из начального в одно из заключительных состояний.
Регулярные множества и автоматные языки
Рассмотрим класс множеств цепочек над конечным словарем. Эти множества называются регулярными. Пусть V1,V2 – множества цепочек.Тогда операции над этими множествами:
V1 U V2 (операция объединения);
V1V2 (операция конкатенации или склеивания);
V*=V0 U V1 U V2 U (итерация);
Класс регулярных выражений над конечным словарем:

· и
·
{a} для любого а из V
если R1 ,R2 регулярные, то:
R1+R2;
R1R2;
R1*,R2* ;
Регулярное выражение – это конечная формула, схематично показывающая,как было построено соответствующее ей регулярное множество с помощью перечисленных операций, задающая бесконечное множество цепочек, т.е. язык.
Построение автомата по заданной грамматике
[ Cкачайте файл, чтобы посмотреть ссылку ]: Классы регулярных множеств и автоматных языков совпадают.
Детерминированные и недетерминированные автоматы
Важным аспектом является преобразование недетерминированного конечного автомата к детерминированному. Недетерминированные конечноавтоматные распознаватели могут быть двух типов: либо существует переход, помеченный пустой цепочкой
·, либо из одного состояния выходят несколько переходов, помеченных одним и тем же символом (возможны оба случая).
Теорема 3: Для любого недетерминированного конечноавтоматного распознавателя существует эквивалентный ему детерминированный.
Алгоритм построения эквивалентного детерминированного конечного автомата.
Приведение недетерминированного автомата к автомату без
·-переходов.
Определение:
·-замыканием состояния s называется множество всех состояний, которые достижимы из s без подачи входного сигнала. Множеством состояний полученного автомата являются
·-замыкания состояний автомата с
·-переходами.
Построение по полученному автомату без
·-переходов эквивалентного ему детерминированного автомата, допускающего тот же язык. В качестве начального (конечного) состояния искомого автомата выбрать множество начальных(конечных) состояний исходного автомата.
Алгоритм синтаксического анализа
На входе алгоритма дан конечный автомат, заданный либо диаграммой переходов, представляющей собой граф автомата, либо таблицей переходов. В нем кодируется информация о возможных последовательностях цепочек, которые будут распознаваться синтаксическим анализатором.
Все эти цепочки представляют собой регулярные выражения, поскольку по теореме Клини класс языков, распознаваемых автоматом, и класс регулярных множеств совпадают.
Сканирование (из исходного текста строятся лексемы, реализуется в виде конечного автомата)
построение эквивалентного детерминированного автомата (поскольку по теореме для любого недетерминированного конечного автомата существует эквивалентный ему детерминированный).(Шаг 1).
строится таблица переходов для полученного конечного автомата.(Шаг 2).
поток символов интерпретируется в выходной поток лексем (обработка потока символов в соответствии с заданной автоматной грамматикой).(Шаг 3).
Оценка (конструируются токены, проход по символам лексемы для получения значения токена).(Шаг 4).
Построение дерева разбора (результат синтаксического анализа).(Шаг 5).
Рассмотрим работу алгоритма на двух примерах.
Пример 1
Рассмотрим алгоритм построения по недетерминированному конечному автомату эквивалентного ему детерминированного автомата на Примере 1.
[ Cкачайте файл, чтобы посмотреть ссылку ]
Конечный автомат в Примере 1 распознает цепочки языка (а+bb)(a+b)*. Это недетерминированный конечный автомат. Построим для него эквивалентный автомат без
·-переходов,заменив состояния автомата
·-замыканием.
[ Cкачайте файл, чтобы посмотреть ссылку ]
Таблица переходов для эквивалентного детерминированного автомата.

a
b

po={qo;q1}
p2
p1

p1={q2}

p2

p2={q2;q3}
p3
p2

p3={qo;q1;q2;q3}
p3
p2


[ Cкачайте файл, чтобы посмотреть ссылку ](Шаг 1 + Шаг 2).

Построим автоматную грамматику для языка из Примера 1.(Шаг 3).
Po->bP1|aP2; P2->bP2|aP3; P3->bP2|aP3; P1->bP2
Рассмотрим пример вывода цепочки bbab: (Шаг 4). Po->bP1->bbP2->bbaP3->bbabP2.
Построение дерева вывода цепочки автоматного языка выполняется сверху вниз. Корень дерева помечается начальным состоянием Ро. Если в исходной грамматике построить соответствующий детерминированный конечный автомат, то символ, помечающий каждый следующий узел, совпадает с меткой состояния, в которое переходит автомат на очередном шаге.

[ Cкачайте файл, чтобы посмотреть ссылку ](Шаг 5).
Пример 2
Рассмотрим пример построения по [ Cкачайте файл, чтобы посмотреть ссылку ] детерминированного конечного автомата. Конечный автомат в Примере 2 распознает цепочки языка b+(а+bb)(b+ab)*a. Синтаксическая диаграмма для данного автомата представлена на рисунке.
[ Cкачайте файл, чтобы посмотреть ссылку ]
Построим детерминированный конечный автомат по алгоритму, описанному выше.
[ Cкачайте файл, чтобы посмотреть ссылку ]
Эквивалентный автомат без
·-переходов.
[ Cкачайте файл, чтобы посмотреть ссылку ]
Таблица переходов для эквивалентного автомата из Примера 2.


a
b

p1{1}
p3
p2

p2{2;6}

p3

p3{3;4;7}
p2
p3

Эквивалентный детерминированный автомат. (Шаг 1 + Шаг 2). [ Cкачайте файл, чтобы посмотреть ссылку ]

Построим автоматную грамматику для языка из Примера 2.(Шаг 3).
P1->bP2|aP3; P2->bP3; P3->bP3|aP2;
Рассмотрим пример вывода цепочки bbab:(Шаг 4). P1->bP2->bbP3->bbaP2->bbabP3.
Построение дерева разбора для цепочки bbab, распознаваемой автоматом Приме
ра 2. (Шаг 5)
. [ Cкачайте файл, чтобы посмотреть ссылку ]









13PAGE 15


13PAGE 14615




ЦПУ

П

П

П

П

П

П

П

П

Пр1

Пр2

Пр4

Пр3

Макропроцессор

Выполнение

ИМ

0

1


Динамические приоритеты

15

Статические приоритеты реального времени

31

16

Поток 2

Поток 1

Запись

1-4 5-6

Поставщик

Потребитель


Пул - очередь

Таблица страниц

Физический адрес

Линейный адрес


MMU

Пользовательский интерфейс операционной среды



Прил2

Прил1

Real Mode

Выполнение

Бездействие

Готовность

Protected Mode

SMM

V.86

TLB


Преобразователь


LTD

GDT

Пользователь-ские приложения

Процессы
поддержки
системы

Компилятор

Загруз
чик

Редактор связей

ЗМ

Связывающий Загрузчик

ОМ

Подсистемы
окружения

DLL подсистем

Процедуры инициализации ввода-вывода

Процедуры
диспетчеризации

Драйверы устройств

Выполнение

Поддержка окон и графики

Процессы
сервисов

ИМ

Уровень абстрагирования от оборудования

Исполнительная система

Ядро

Процедура
добавления
устройства

Подсистема
Ввода-
вывода

Блокировка

ИМ’

Ассемблер или
Компилятор

Интерпретатор

Загруз
чик

ЗМ

Редактор связей

Связывающий Загрузчик

ОМ

Входная цепочка символов
a1a2. an

уу

Z1

Стек
(магазин)

Физическая память

Ядро Windows
Драйверы


Системные
таблицы

Системные DLL
Пользовательские
DLL
Данные
Приложения

Системный
раздел

Пользовательский
радел

Процедура обслуживания прерываний

Инициализирующая процедура

DPC процедура



Заголовок 1 Заголовок 2 Заголовок 3 Заголовок 4 Заголовок 5 Заголовок 615

Приложенные файлы

  • doc 17431289
    Размер файла: 869 kB Загрузок: 1

Добавить комментарий