- •Введение
- •1. Основные понятия системного программного обеспечения
- •1.1. Понятия прикладного и системного программного обеспечения
- •1.2. Состав системного программного обеспечения
- •2. Состав и архитектура операционных систем
- •2.1. Состав операционных систем
- •2.2. Архитектура ос
- •3. Процессы и потоки
- •3.1. Концепция процессов и потоков
- •3.2. Многозадачность. Формы программной работы
- •3.3. Подсистема управления процессами и потоками
- •3.4. Роль процессов, потоков и волокон в многозадачности
- •3.5. Создание процессов
- •3.6. Потоки и их модели
- •3.7. Планирование и синхронизация процессов и потоков
- •3.7.1. Виды планирования
- •3.7.2. Алгоритмы планирования потоков
- •3.7.3. Алгоритмы приоритетного планирования
- •3.7.4. Взаимоисключения
- •3.7.5. Семафоры
- •3.7.6. Тупики
- •4. Управление памятью
- •4.1. Функции ос по управлению памятью
- •4.2. Классификация методов распределения памяти
- •4.3. Распределение памяти без использования внешней памяти
- •4.4. Методы структуризации виртуальной памяти
- •4.4.1. Страничная организация виртуальной памяти
- •4.4.2. Сегментная организация виртуальной памяти
- •4.4.3. Странично-сегментная организация памяти
- •5. Файловые системы
- •5.1. Цели и задачи файловой системы
- •5.2. Организация файлов и доступ к ним
- •5.3. Логическая организация файла
- •5.4. Каталоговые системы
- •5.5. Основные возможности файловой системы ntfs
- •5.6. Структура тома с файловой системой ntfs
- •5.7. Возможности ntfs по ограничению доступа к файлам и каталогам
- •6. Управление вводом-выводом
- •6.1. Физическая организация устройств ввода-вывода
- •6.2. Организация программного обеспечения ввода-вывода
- •6.3. Обработка прерываний
- •6.4. Драйверы устройств
- •6.5. Независимый от устройств слой ос
- •6.6. Пользовательский слой программного обеспечения
- •7. Построение операционных систем
- •7.1. Принципы построения операционных систем
- •7.1.1. Принцип модульности
- •7.1.2. Принцип функциональной избирательности
- •7.1.3. Принцип генерируемости ос
- •7.1.4. Принцип функциональной избыточности
- •7.1.5. Принцип виртуализации
- •7.1.6. Принцип независимости программ от внешних устройств
- •7.1.7. Принцип совместимости
- •7.1.8. Принцип открытой и наращиваемой ос
- •7.1.9. Принцип мобильности
- •7.1.10. Принцип обеспечения безопасности вычислений
- •7.2. Построение интерфейсов операционных систем
- •7.3. Интерфейс прикладного программирования
- •7.3.1. Реализация функций api на уровне ос
- •7.3.2. Реализация функций api на уровне системы программирования
- •7.3.3. Реализация функций api с помощью внешних библиотек
- •7.4. Классификация системных вызовов
- •7.5. Интерфейс пользователя
- •7.6. Пользовательский интерфейс приложений
- •7.7. Архитектура, управляемая событиями
- •8. Семейство операционных систем unix
- •8.1. Основные понятия системы unix
- •8.1.1. Виртуальная машина
- •8.1.2. Пользователь
- •8.1.3. Интерфейс пользователя
- •8.1.4. Привилегированный пользователь
- •8.1.5. Команды
- •8.1.6. Процессы
- •8.1.7. Выполнение процессов
- •8.1.8. Структура файловой системы
- •8.2. Операционная система Linux
- •9.1.2. Определение компилятора. Отличие компилятора от транслятора
- •9.1.3. Определение интерпретатора. Разница между интерпретаторами и трансляторами
- •9.1.4. Этапы трансляции. Общая схема работы транслятора
- •9.1.5. Понятие прохода. Многопроходные и однопроходные компиляторы
- •9.2. Таблицы идентификаторов. Организация таблиц идентификаторов
- •9.2.1. Назначение таблиц идентификаторов
- •9.2.2. Принципы организации таблиц идентификаторов
- •9.2.3. Простейшие методы построения таблиц идентификаторов
- •9.2.4. Построение таблиц идентификаторов по методу бинарного дерева
- •9.2.8. Комбинированные способы построения таблиц идентификаторов
- •9.3. Лексические анализаторы
- •9.3.1. Назначение лексического анализатора
- •9.3.2. Принципы построения лексических анализаторов
- •9.3.3. Определение границ лексем
- •9.3.4. Выполнение действий, связанных с лексемами
- •9.4. Формальные языки и грамматики
- •9.4.1. Первичные понятия
- •9.4.2. Примеры, иллюстрирующие первичные понятия
- •9.4.3. Типы формальных языков и грамматик
- •9.4.3.1. Грамматики типа 0
- •9.4.3.2. Грамматики типа 1
- •9.4.3.3. Грамматики типа 2
- •9.4.3.4. Грамматики типа 3
- •9.4.3.5. Вывод в кс-грамматиках и правила построения дерева вывода
- •9.4.3.6. Синтаксический разбор
- •9.4.3.7. Левый и правый выводы
- •9.4.3.8. Неоднозначные и эквивалентные грамматики
- •9.4.4. Способы задания схем грамматик
- •9.4.4.1. Форма Наура-Бэкуса
- •9.4.4.2. Итерационная форма
- •9.4.4.3. Синтаксические диаграммы
- •9.4.5. Построение грамматик и грамматики, описывающие основные конструкции языков программирования
- •9.4.5.1. Рекомендации по построению грамматик
- •9.4.5.2. Описание списков
- •9.4.5.3. Пример построения грамматик
- •9.4.5.4. Грамматики, описывающие целые числа без знака и идентификаторы
- •9.4.5.5. Грамматики для арифметических выражений
- •9.4.5.6. Грамматика для описаний
- •9.4.5.7. Грамматика, задающая последовательность операторов присваивания
- •9.4.5.8. Грамматики, описывающие условные операторы и операторы цикла
- •9.4.5.9. Бесскобочные выражения
- •9.4.5.10. Префиксная польская запись
- •9.4.5.11. Вычисление префиксных польских записей
- •9.4.5.12. Постфиксная польская запись
- •9.4.5.13. Вычисление постфиксных записей
- •9.5. Конечные автоматы и регулярные грамматики
- •9.6. Макроязыки и макрогенерация
- •9.6.1. Определения макрокоманд и макрогенерации
- •9.6.2. Примеры макрокоманд
- •9.6.3. Макроязыки и препроцессоры
- •Заключение
- •Библиографический список
- •Оглавление
- •394026 Воронеж, Московский просп., 14
9.2.2. Принципы организации таблиц идентификаторов
Компилятор пополняет записи в таблице идентификаторов по мере анализа исходной программы и обнаружения в ней новых элементов, требующих размещения в таблице. Поиск информации в таблице выполняется всякий раз, когда компилятору необходимы сведения о том или ином элементе программы. Причем следует заметить, что поиск элемента в таблице будет выполняться компилятором существенно чаще, чем помещение в нее новых элементов. Так происходит потому, что описания новых элементов в исходной программе, как правило, встречаются гораздо реже, чем эти элементы используются. Кроме того, каждому добавлению элемента в таблицу идентификаторов в любом случае будет предшествовать операция поиска - чтобы убедиться, что такого элемента в таблице нет.
На каждую операцию поиска элемента в таблице компилятор будет затрачивать время, и поскольку количество элементов в исходной программе велико (от единиц до сотен тысяч в зависимости от объема программы), это время будет существенно влиять на общее время компиляции. Поэтому таблицы идентификаторов должны быть организованы таким образом, чтобы компилятор имел возможность максимально быстро выполнять поиск нужной ему записи таблицы по имени элемента, с которым связана эта запись.
Можно выделить следующие способы организации таблиц идентификаторов:
простые и упорядоченные списки;
бинарное дерево;
хэш-адресация с рехэшированием;
хэш-адресация по методу цепочек;
комбинация хэш-адресации со списком или бинарным деревом.
9.2.3. Простейшие методы построения таблиц идентификаторов
В простейшем случае таблица идентификаторов представляет собой линейный неупорядоченный список, или массив, каждая ячейка которого содержит данные о соответствующем элементе таблицы. Размещение новых элементов в такой таблице выполняется путем записи информации в очередную ячейку массива или списка по мере обнаружения новых элементов в исходной программе.
Поиск нужного элемента в таблице будет в этом случае выполняться путем последовательного перебора всех элементов и сравнения их имени с именем искомого элемента, пока не будет найден элемент с таким же именем. Тогда если за единицу времени принять время, затрачиваемое компилятором на сравнение двух строк (в современных вычислительных системах такое сравнение чаще всего выполняется одной командой), то для таблицы, содержащей N элементов, в среднем будет выполнено N/2 сравнений.
Время, требуемое на добавление нового элемента в таблицу (Tд), не зависит от числа элементов в таблице (N). Но если N велико, то поиск потребует значительных затрат времени. Время поиска (Tп) в такой таблице можно оценить как Тп = O(N). Поскольку именно поиск в таблице идентификаторов является наиболее часто выполняемой компилятором операцией, такой способ организации таблиц идентификаторов является неэффективным. Он применим только для самых простых компиляторов, работающих с небольшими программами.
Поиск может быть выполнен более эффективно, если элементы таблицы отсортированы (упорядочены) естественным образом. Поскольку поиск осуществляется по имени, наиболее естественным решением будет расположить элементы таблицы в прямом или обратном алфавитном порядке. Эффективным методом поиска в упорядоченном списке из N элементов является бинарный, или логарифмический, поиск.
Алгоритм логарифмического поиска заключается в следующем:
искомый символ сравнивается с элементом (N+1)/2 в середине таблицы;
если этот элемент не является искомым, то мы должны просмотреть только блок элементов, пронумерованных от 1 до (N+1)/2 - 1, или блок элементов от (N+1)/2 + 1 до N в зависимости от того, меньше или больше искомый элемент того, с которым его сравнили;
затем процесс повторяется над нужным блоком в два раза меньшего размера;
так продолжается до тех пор, пока либо искомый элемент не будет найден, либо алгоритм не дойдет до очередного блока, содержащего один или два элемента (с которыми можно выполнить прямое сравнение искомого элемента).
Так как на каждом шаге число элементов, которые могут содержать искомый элемент, сокращается в два раза, максимальное число сравнений равно 1 + log2 N. Тогда время поиска элемента в таблице идентификаторов можно оценить как Тп = O (log2 N).
Для сравнения: при N = 128 бинарный поиск требует самое большее 8 сравнений, а поиск в неупорядоченной таблице – в среднем 64 сравнения.
Метод называют «бинарным поиском», поскольку на каждом шаге объем рассматриваемой информации сокращается в два раза, а «логарифмическим» - поскольку время, затрачиваемое на поиск нужного элемента в массиве, имеет логарифмическую зависимость от общего количества элементов в нем.
Недостатком логарифмического поиска является требование упорядочивания таблицы идентификаторов. Так как массив информации, в котором выполняется поиск, должен быть упорядочен, время его заполнения уже будет зависеть от числа элементов в массиве. Таблица идентификаторов зачастую просматривается компилятором еще до того, как она заполнена, поэтому требуется, чтобы условие упорядоченности выполнялось на всех этапах обращения к ней. Следовательно, для построения такой таблицы можно пользоваться только алгоритмом прямого упорядоченного включения элементов.
Если пользоваться стандартными алгоритмами, применяемыми для организации упорядоченных массивов данных, то среднее время, необходимое на помещение всех элементов в таблицу, можно оценить следующим образом:
Tд = O (N * log2 N) + k * O (N2)
Здесь k – некоторый коэффициент, отражающий соотношение между временами, затрачиваемыми компьютером на выполнение операции сравнения и операции переноса данных.
При организации логарифмического поиска в таблице идентификаторов обеспечивается существенное сокращение времени поиска нужного элемента за счет увеличения времени на помещение нового элемента в таблицу. Поскольку добавление новых элементов в таблицу идентификаторов происходит существенно реже, чем обращение к ним, этот метод следует признать более эффективным, чем метод организации неупорядоченной таблицы. Однако в реальных компиляторах этот метод непосредственно также используется редко, поскольку существуют более эффективные методы.