Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по СПО - файл 1.doc


Лекции по СПО
скачать (469 kb.)

Доступные файлы (1):

1.doc469kb.16.11.2011 00:47скачать

содержание

1.doc

  1   2
Лекция 1. Структура и функции СПО ЭВМ

  1. Понятие СПО;

  2. Состав и основные функции.

Понятие СПО

Для выполнения вычислений в современной практике используются вычислительные машины и системы.

ЭВМ – это комплекс аппаратуры, который обеспечивает выполнение действий некоторого набора алгоритмов.

ВС – это набор одной или нескольких ЭВМ и программ, которые обеспечивают выполнение возложенных на ВС функций.

Таким образом, ВС делятся на 2 части:

    • программную;

    • аппаратную.

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

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

Программная часть состоит из большого количества взаимосвязанных компонентов, которые называются системой программного обеспечения (ПО).

Замечание: слово «обеспечение» указывает, что программа реализует функции, возложенные на ВС.

В общем случае система ПО делится на 2 большие части:

  1. Прикладное ПО (пользовательское);

  2. Системное ПО.

Прикладное программное обеспечение – это то, которое разрабатывается самими пользователями (для себя).

Системное программное обеспечение – то, которое разрабатывается для всех и является универсальным. Оно делится на 2 части:

  1. Общее СПО;

  2. Специализированное СПО.

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

Общее СПО является универсальным и предназначено для решения широкого круга задач.

В дальнейшем будем рассматривать общее СПО. Оно состоит:

  1. системные обрабатывающие программы;

  2. системные управляющие программы;

  3. дополнительные, как 1, так и 2;

  4. контрольно-диагностические;

  5. пакеты прикладных программ;

  6. комплекс документации СПО.

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

  2. Системные управляющие программы (СУП) предназначены для организации эффективного функционирования всей ^ ВС в целом и для создания удобного интерфейса между ВС и пользователем.

Замечание: Только СУП имеет непосредственный доступ к аппаратуре.

Замечание: СУП принято называть операционными системами (ОС).

ОС может обеспечивать следующие варианты интерфейса:

    • командный интерфейс;

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

    • пользовательский интерфейс (окна, меню, кнопки и т.д.)

3. Дополнительные системные программы (ДСП) предназначены для расширения возможностей обрабатывающих и управляющих программ.

К ДСП относятся:

  • сервисные программы;

  • инструментальные.

К сервисным относятся:

    • программные оболочки (надстройки);

    • утилиты.

Значение программной оболочки – улучшение доступа к ресурсам ВС (проводник Windows и т.д.).

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

К инструментальным программным средствам относятся:

  • СУБД;

  • Системы машинной графики.

и т. д.

4. Контрольно-диагностические программы предназначены для профилактики контроля и локализации неисправностей в процессе эксплуатации ЭВМ, либо в автономном режиме.

^ 5. Пакет ПП – это набор программ, предназначенных для решения практических задач – научные расчеты, моделирование и т.д.

Замечание: В каждом ППП есть язык, на котором описывается порядок выполнения работ в рамках этого пакета.

6. Комплекс документации – совокупность текстовых документов, подготовленных согласно ГОСТам (ЕСКД); в них – сведения по правилам эксплуатации и настройки соответствующих частей СПО.

Состав и основные функции

Состав и функции системных обрабатывающих программ:

  1. Ассемблер;

  2. Редакторы связи и загрузчики;

  3. Макропроцессоры;

  4. Трансляторы (переводчики);

  5. Языковые конверторы;

  6. Редакторы и текстовые процессоры;

  7. Отладчики;

  8. Дизассемблер;

  9. Кросс-системы;

  10. Библиотекари.

1. Ассемблер – это такая системная обрабатывающая программа, которая обеспечивает преобразование исходной программы, написанной на некотором машинно-ориентированном языке в так называемый объективный код. (Текст на Ассемблере содержит директивы, имена, а машинный код содержит только байты).

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

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

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

Замечание: загрузчики могут быть либо перемещающими, либо абсолютными.

  • Абсолютные загрузчики каждая программа загружается по одному фиксированному адресу.

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

3. Макропроцессоры – это такая программа, которая предназначена для символьной обработки, в процессе которой неким коротким фразам (макровызовам) ставятся в соответствие длинные (макрорасширения). На входе макропроцессора имеется некий текст из макровызовов, на выходе – макрорасширения.

4. Трансляторы (переводчики) переводят текст с одного языка на другой. Можно выделить следующие разновидности трансляторов:

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

Особенность: четкое разделение функций перевода и выполнение переведенного.

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

5. Языковые конверторы выполняют преобразование текста программы с одного языка высокого уровня на другой язык высокого уровня. Он нужен для того, чтобы программу, написанную на S1 преобразовать вS2.







6. Тестовые редакторы отличаются необыкновенными расширенными возможностями для обработки текста.

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

^ 8. Дизассемблер это программа, которая переводит последовательность машинных кодов в ассемблерный вид.

Замечание: они также позволяют в ассемблерном виде видеть выполнение систем некоторых действий.

9. Кросс-система – это программа для получения на одной ВМ программ, представленных в машинных кодах некоторой другой ВМ. Используется для отладки проектируемых архитектурных ВС.

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

Возможность развития операционной системы

Причины непрерывного развития ОС:

1. Обновление и возникновение новых видов аппаратного обеспечения

2. Новые сервисы

3. Внесение исправлений

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

К примеру, Windows NT начало вытесняться с рынка после внедрения Intel процессоров Hyper Thread, которые эмулировали второй процессор. Как работать с эмуляцией ядра Windows NT «не знало»- система падала.

^ Операционный системы могут развиваться

1.скачкообразно (Windows) и

2.постепенно (UNIX).

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

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

^ Разработка операционных систем

Существует три решения по разработке операционных систем.

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

Достоинством такого подхода может служить ответственность фирмы за разрабатываемый программный продукт. Хорошая документированность. Универсальность. Стандартизация. К наиболее известным фирмам, использующим такой подход, относятся: Microsoft, SUN, SCO.

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

^ Открытое решение. Разрабатываемые решения подчиняются одной общей лицензии сообщества открытого кода. Любой желающий может получить исходный код программного продукта, если она предоставлена автором или работающую версию. Такое решение не гарантирует, что программный продукт будет работать корректно. Как правило, эти решения плохо документированы. К достоинствам такого подхода относится возможность работы специалистов разных направлений и разных стран в единой команде. Быстрая реакция команды разработчиков на изменившиеся условия. Возможность работы на всевозможных платформах и с любыми другими системами. К наиболее известным фирмам, использующим такой подход, относятся: RedHat, SuSe, FreeBSD; Novell.

^ Смешанное решение. Разрабатываемые решения используют как открытый общедоступный код, так и собственные разработки, защищенные лицензиями. Такой подход позволяет выбрать лучшие реализации из открытых решений и на их базе создавать свои. Такой подход сочетает лучшие качества обоих подходов, поскольку фирма документирует и несет ответственность и не только за свои решения, но и за привлекаемые открытые решения. По такому пути идут фирмы MacOS, BeOs, QNX, Netrino.

^ Лекция 2. Назначение и основные функции операционной системы.

Под термином «операционная система» мы будем понимать комплекс программ, функциями которого является контроль за использованием и распределением ресурсов вычислительной системы. Мы говорили, что в вычислительной системе есть физические ресурсы, то есть те ресурсы, которые связаны с реальным оборудованием (магнитные диски, оперативная память, время работы процессора). Мы говорили также, что в системе для ее успешного функционирования имеются логические (иногда их называют виртуальными) ресурсы, то есть ресурсы, которые в виде реального оборудования не существуют, но реализуются в виде некоторых средств, предоставляемых пользователю. Физические и логические ресурсы мы будем называть просто ресурсами вычислительной системы.

Любая операционная система (ОС) оперирует некоторыми сущностями, которые вместе со способами управления ими во многом характеризуют ее свойства. К таким сущностям могут относиться понятия файла, процесса, объекта, и т.д. Каждая ОС имеет свой набор таких сущностей. К примеру, в ОС Windows NT к таким сущностям можно отнести понятие объекта, и уже через управление этой сущностью предоставляются все возможные функции. Если мы посмотрим UNIX, то в ней такой сущностью, в первую очередь, является понятие файла, а во вторую очередь, понятие процесса.

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

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

Управление процессами:

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

  2. Управление «подкачкой» и буфером ввода.

  3. Управление разделяемыми ресурсами.

Основные проблемы управления процессами.

Первое - управление использованием времени центрального процессора (ЦП), или эту проблему иногда называют планированием ЦП, то есть управление тем, в какой момент времени какая из задач или какой из процессов будет владеть активностью ЦП: на какой из процессов будет работать ЦП.

Второе - управление «подкачкой» и буфером ввода. Предположим ситуацию, когда большое количество людей, например весь курс, сидит за компьютерами, и все одновременно запустили какие-то задания в виде процессов. В системе образовалась масса задач (гарантированно больше ста). А вся вычислительная система не может принять для работы в мультипрограммном режиме сто задач - это слишком много. В этом случае образуется, так называемый, буфер ввода задач, или буфер ввода процессов, то есть буфер, в котором аккумулируются те процессы, которые ожидают начала своей обработки процессором. Возникает проблема очередности выбора процессов из этого буфера для начала обработки. Это задача планирования буфера.

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

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

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

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

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

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

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

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


^ Системы пакетной обработки. Первая ситуация. У меня есть большое количество задач или программ, требующих большого объема вычислительных мощностей системы. Это те задачи, которые называют счетными задачами; они требуют большого объема вычислений и мало обращаются к внешним устройствам. Эти задачи должны выполняться на одной вычислительной системе. Что будет являться критерием эффективности для работы системы при выполнении этого пакета задач? Какой набор параметров можно взять и сказать: если они большие - то хорошо, если наоборот - то плохо? Для такой ситуации критерием эффективности работы вычислительной системы является степень загрузки ЦП. Если он мало простаивает (т.е. работает в режиме ожидания, а все процессы занимаются обменом, либо ОС берет на себя время), то мы можем сказать, что такая система работает эффективно. Этого можно добиться с использованием соответствующего алгоритма планирования, который заключается в следующем. Мы запускаем для обработки тот набор задач, который у нас есть по возможностям ОС (либо максимум, либо все задачи), что обеспечивается режимом мультипрограммирования. Алгоритм планирования времени ЦП в этом случае будет следующий: если ЦП выделен одному из процессов, то этот процесс будет занимать ЦП до наступления одной из следующих ситуаций:

  1. Обращение к внешнему устройству.

  2. Завершение процесса.

  3. Зафиксированный факт зацикливания процесса.

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

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


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

Для такой системы подойдет критерий времени ожидания пользователя: с момента, как он послал заказ на выполнение какого-то действия, до момента ответа системы на этот заказ. Чем эффективнее работает система, тем это среднестатистическое время ожидания в системе меньше.

Рассмотрим ситуацию для второго случая. В системе находится некоторое количество процессов, и задача планировщика распределить время ЦП таким образом, чтобы время реакции системы на запрос пользователя было минимальным, либо по крайней мере, гарантированным. Предлагается следующая схема. В системе используется некоторый параметр t, который называют квантом времени (в общем случае, квант времени - это некоторое значение, которое может изменяться при настройке системы). Все множество процессов, которое находится в мультипрограммной обработке, подразделяется на два подмножества. Первое подмножество составляют те процессы, которые еще не готовы к продолжению выполнения: например, те процессы, которые заказали себе обмен и ждут его результатов. А есть процессы, которые готовы к выполнению. Работа будет осуществляться следующим образом. Тот процесс, который в данный момент времени занимает ЦП, будет владеть им до наступления одного из следующих событий:

  1. Обращение с заказом на обмен.

  2. Завершение процесса.

  3. Исчерпание выделенного данному процессу кванта времени t.

При наступлении одного из этих событий планировщик ОС выбирает из процессов, готовых к выполнению, некоторый процесс и передает ему ресурсы ЦП. А выбирает он этот процесс в зависимости от того алгоритма планирования, который был использован в данной конкретной ОС. Например, процесс может выбираться случайно. Второй способ заключается в том, что происходит как бы последовательный обход процессов, то есть мы взяли в работу сначала один из процессов, затем он освободился, и время ЦП будет предоставлено следующему по порядку процессу из готовых к выполнению. Третьим критерием, по которому отбирается очередная задача, может быть время, которое данный процесс не обслуживался ЦП. В этом случае система может выбирать процесс, у которого такое время самое большое. Эти алгоритмы должны быть реализованы в ОС, а значит, они должны быть простыми, иначе система будет работать неэффективно, сама на себя (хотя такие системы есть: в частности, этим страдает семейство Windows).

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

Системы разделения времени (например, UNIX, VMS) призваны исправить основной недостаток систем пакетной обработки - изоляцию пользователя-программиста от процесса выполнения его задач. Каждому пользователю системы разделения времени предоставляется терминал, с которого он может вести диалог со своей программой. Так как в системах разделения времени каждой задаче выделяется только квант процессорного времени, ни одна задача не занимает процессор надолго, и время ответа оказывается приемлемым. Если квант выбран достаточно небольшим, то у всех пользователей, одновременно работающих на одной и той же машине, складывается впечатление, что каждый из них единолично использует машину. Ясно, что системы разделения времени обладают меньшей пропускной способностью, чем системы пакетной обработки, так как на выполнение принимается каждая запущенная пользователем задача, а не та, которая "выгодна" системе, и, кроме того, имеются накладные расходы вычислительной мощности на более частое переключение процессора с задачи на задачу. Критерием эффективности систем разделения времени является не максимальная пропускная способность, а удобство и эффективность работы пользователя.


^ Системы реального времени. Теперь посмотрим следующую задачу. Предположим, у нас есть самолет, управляемый автопилотом, который на автопилоте производит операцию снижения. У каждого самолета есть прибор, который измеряет высоту от самолета до поверхности земли. Режим работы самолета таков, что управление его функциями по некоторой заданной программе осуществляет компьютер. Итак, если у нас есть система автопилота, и самолет снижается, это система должна контролировать высоту полета. Центральный компьютер этого самолета может решать несколько задач: он может контролировать высоту полета, уровень топлива в баках, какие-то показатели работы двигателей и т.д. Управлением каждой из этих функций занимается свой процесс. Предположим, у нас пакетная ОС, и мы внимательно контролируем уровень топлива в баках. При этом, очевидно, возникает аварийная ситуация, ведь самолет продолжает снижаться, а ОС этого не замечает.

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

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

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


Замечание. Подводя некоторую черту под функцией управления использованием времени ЦП и планирования ЦП, обращаю внимание на два факта. Первый факт это то, что те алгоритмы, которые реализованы в системе планирования распределением времени ЦП во многом определяют эксплуатационные свойства вычислительной системы. Я специально приводил примеры, предлагая использовать разные ОС для разных целей. Второй факт. Мы рассмотрели три типовых разновидности ОС: системы пакетной обработки, системы разделения времени и системы реального времени. На сегодняшний день можно говорить о том, что система реального времени это отдельный класс ОС. Гарантированно, ОС Windows не будет управлять какими-то объектами, у которых это реальное время очень критично. Также не будет управлять такими объектами и ОС СОЛЯРИС или LINUX и т.д., потому что эти системы не являются системами реального времени.

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

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

^ Управление подкачкой и буфером ввода.

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

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

^ Управление разделяемыми ресурсами.

Здесь мы обозначим только проблему, потому что конкретные ее решения мы рассмотрим на примере ОС UNIX.

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

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

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

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

На прошлой лекции мы говорили о том, что практически любая операционная система обеспечивает буферизацию ввода/вывода. На самом деле, это одна из основных функций операционной системы. По аналогии борьбы с разными скоростями доступа к различным компонентам вычислительной системы операционная система вводит в своих пределах программную буферизацию, которая также решает проблемы сглаживания времени доступа и проблемы синхронизации в целом (пример с устройством печати). Сглаживание проблем доступа заключается в том, что практически каждая операционная система имеет КЭШ-буфера, которые аккумулируют обращения к внешнему запоминающему устройству (ВЗУ) аналогично аппаратной буферизации при работе с оперативной памятью. Это позволяет существенно оптимизировать операционную систему. Признаком наличия такой буферизации является требование прекратить выполнение операционной системы перед выключением машины. Например, работая с операционной системой MS-DOS, можно выключить компьютер в любой момент времени, потому что такой буферизации в ней нет. В операционных системах типа Windows и UNIX считается некорректным просто выключить машину при работающей системе, в этом случае есть вероятность, что произойдет некоторая потеря информации (так как, например, моменты заказа на обмен и непосредственно обмена далеко не совпадают). Степень этой буферизации определяет реальную эффективность системы. Когда на нашем факультете стали появляться Pentium-ы, то обнаружилось, что при работе с Windows 95 практически нет качественного различия между тем, работает ли система на 486 процессоре или на Pentium-е. Это говорит о том, что эффективность системы не упирается в эффективность работы с внешним устройством. Если взять операционную систему UNIX, то эта разница будет заметна, так как здесь быстродействие процессора сильнее влияет на качество работы системы, нежели чем для Windows 95, потому что в системе Windows 95 обменов с внешним носителем значительно больше за счет некоторой «тупости» алгоритмов буферизации работы с внешними устройствами.

^ Лекция 3. Файловая система.

Мы с вами говорили, что каждая из операционных систем оперирует некоторыми сущностями, одной из которых является процесс. Есть вторая сущность, которая также важна - это понятие файла. Файловая система - это компонент операционной системы, обеспечивающий организацию создания, хранения и доступа к именованным наборам данных. Эти именованные наборы данных называются файлами.

Основные свойства файлов

1. Файл - это некий объект, имеющий имя, и позволяющий оперировать с содержимым файла через ссылку на это имя. Обычно имя - это последовательность некоторых символов, длина которой зависит от конкретной операционной системы.

^ 2. Независимость файла от расположения. Для работы с конкретным файлом не требуется иметь информацию о местоположении этого файла на внешнем устройстве.

^ 3. Набор функций ввода/вывода. Практически каждая операционная система однозначно определяет набор функций, обеспечивающий обмен с файлом. Обычно, этот набор функций состоит из следующих запросов:

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

  2. Чтение/запись. Обычно обмен с файлами может организовываться некоторыми блоками данных. Блок данных, с которым происходит обмен, несет двоякую сущность. С одной стороны, для любой вычислительной системы известны размеры блоков данных, которые наиболее эффективны для обмена, то есть это программно-аппаратные размеры. С другой стороны, эти блоки данных при реальном обмене могут варьироваться достаточно произвольно программистом. В функциях чтения/записи обычно фигурирует размер блока данных для обмена и количество блоков данных, которые необходимо прочесть или записать. От выбранного размера блока данных может зависеть эффективность реальных обменов, потому что, предположим для некоторой машины размером эффективного блока данных является 256Кб, а вы хотите обмены проводить по 128Кб, и вы выполняете два обращения для прочтения ваших логических блоков по 128Кб. Очень вероятно, что вместо того, чтобы за один обмен прочесть блок в 256Кб, вы обращаетесь два раза к одному блоку и читаете сначала одну половину, а затем другую. Здесь есть элементы неэффективности, хотя они могут сглаживаться «умной» операционной системой, а если она не сглаживает, то это уже ваша вина.

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

  4. ^ Закрытие файла. Эта операция может осуществляться двумя функциями: 1) Закрыть и сохранить текущее содержимое файла. 2) Уничтожить файл.

После закрытия файла все связи с ним прекращаются, и он приходит в некоторое каноническое состояние.


^ 4. Защита данных. Многие стратегические решения повторяются как на аппаратном уровне, так и на уровне операционной системы. Если мы вспомним мультипрограммный режим, то одним из необходимых условий его существования является обеспечение защиты (памяти и данных). Если мы рассмотрим файловую систему, то она так же, как и операционная система, может быть однопользовательской. В этом случае проблемы защиты данных не существует, потому что человек, который работает с этой операционной системой, является хозяином всех файлов. Примеры однопользовательских систем - MS-DOS или Windows 95. Можно загрузить машину и уничтожить все файлы других пользователей, которые размещены на диске, потому что в этих системах защиты нет никакой. Многопользовательская система обеспечивает корректную работу многих пользователей. MS-DOS также может работать в режиме мультипрограммирования, но он не достаточно корректен, потому что ошибка в одном процессе может привести к затиранию операционной системы и соседнего процесса. Также и в операционной системе Windows 95 может работать много пользователей, но эта работа некорректна, потому что эта операционная система не обеспечивает все права защиты. Итак, многопользовательская система должна обеспечивать защиту информации от несанкционированного доступа. На самом деле, проблема защиты связана не только с файловой системой. Реально операционная система обеспечивает защиту данных во всех областях: это и файлы, и процессы, и ресурсы, принадлежащие процессам, запущенным от имени одного пользователя. Здесь я обращаю ваше внимание на этот факт, потому что для файлов это наиболее критичная точка.


Основные свойства файловых систем.

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

Давайте рассмотрим некоторое пространства ВЗУ, и рассмотрим, как мы можем организовать размещение файлов в пределах этого пространства.


^ 1. Одноуровневая организация файлов непрерывными сегментами. Термин «одноуровневая» означает, что система обеспечивает работу с файлами уникально именованными. В пределах пространства ВЗУ выделяется некоторая область для хранения данных, которая называется каталог. Каталог имеет следующую структуру:


имя

начальный блок

конечный блок











«Начальный блок» ссылается на некоторый относительный адрес пространства ВЗУ, с которого начинается файл с заданным именем. «Конечный блок» определяет последний блок данного файла. Функция открытия файла сводится к нахождению в каталоге имени файла и определении его начала и конца (реально данные могут занимать несколько меньше места, об этом будет сказано позже). Это действие очень простое, к тому же каталог можно хранить в памяти операционной системы, и тем самым уменьшить количество обменов. Если создается новый файл, то он записывается на свободное место. Аналогично каталогу имен может иметься таблица свободных пространств (фрагментов).

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

Что будет, когда нужно записать в такой файл дополнительную информацию, а свободного пространства за этим файлом нет? В этом случае система может поступить двояко. Первое, она скажет, что нет места и вы должны сделать что-то сами, например, запустить некий процесс, который перенесет этот файл в другое место и добавит нужную информацию. Этот перенос - функция достаточно дорогостоящая. Вторая возможность - в обмене будет отказано. Это означает, что при открытии файла нужно было заранее зарезервировать дополнительное место; при этом файловая система проверяет размер свободного буфера, и если его мало, то ищет свободное место там, где этот файл разместится.

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

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


^ 2. Файловая система с блочной организацией файлов. Пространство ВЗУ разделено на блоки (те самые блоки, которые эффективны для обмена). В файловой системе такого типа распределение информации происходит аналогично распределению информации процесса в оперативной памяти со страничной организацией. В общем случае, с каждым именем файла связан набор номеров блоков устройства, в которых размещены данные этого файла. Причем, номера этих блоков имеют произвольный порядок, то есть блоки могут быть разбросаны по всему устройству в произвольном порядке. При такой организации нет фрагментации, хотя могут быть потери кратные блоку (если файл занял хотя бы один байт в блоке, то весь блок считается занятым). Следовательно, нет проблем компрессии, и эта система может использоваться при многопользовательской организации.

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

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

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

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


^ 3. Иерархическая файловая система. Все файлы файловой системы построены в структуру, которая называется деревом. В корне дерева находится, так называемый, корень файловой системы. Если узел дерева является листом, то это файл, который может содержать данные пользователя, либо являться файлом-каталогом. Узлы дерева отличные от листа являются файлами-каталогами. Именование в такой иерархической файловой системе может происходить разными способами. Первый тип - именование файла относительно ближайшего каталога, т. е. если мы посмотрим файлы, которые являются ближайшими для каталога F0, - это файл F1, который является также каталогом, и файл F2. Для успешного именования в такой системе на одном уровне не могут повторяться имена. С другой стороны, так как все файлы связаны с помощью дерева, мы можем говорить о, так называемом, полном имени файла, которое составляется из всех имен файлов, которые составляют путь от корня файловой системы к конкретному файлу. Полное имя файла F3 будет обозначаться так: /F0/F1/F3. Такая организация хороша тем, что она позволяет работать как с коротким именем файла (если системно подразумевается, что мы работаем в данном каталоге), так и с полным именем файла. Полные имена файлов есть пути, а в любом дереве от его корня до любого узла существует единственный путь, следовательно, этим решается проблема унификации имен. Первый раз такой подход был использован в операционной системе Multix, которая разрабатывалась в университете Беркли в конце 60-х годов. Это красивое решение стало появляться впоследствии во многих операционных системах. Согласно этой иерархии, каждому из файлов можно привязывать какие-то атрибуты, связанные с правами доступа. Правами доступа могут обладать как пользовательские файлы, так и каталоги. Структура этой системы хороша для организации многопользовательской работы, за счет отсутствия проблемы именования, и такая система может очень хорошо наращиваться.


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

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

Если мы с вами посмотрим на любимую нами операционную систему MS-DOS, то там не было понятия пользователя со всеми вытекающими последствиями - она однопользовательская.

Второй уровень операционных систем - это операционные системы, которые позволяют регистрировать пользователей, но все пользователи представляются в виде единого набора некоторых субъектов и не связаны друг с другом никак. Примером таких операционных систем могут служить некоторые операционные системы фирмы IBM для mainframe-компьютеров. Например, лектор не знает, кто из его слушателей к какой группе относится, но все, сидящие перед ним, пользователи его курса. Это и хорошо, и плохо. С точки зрения прослушивания курса лекций - это хорошо, но для проведения этим лектором какого-то опроса это плохо, потому что за один день он не успеет опросить всех. Ему надо будет всех слушателей как-то поделить, а как - не известно.

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

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

Лекция 4. Структуры данных и способы их представления и использования.

  1. Понятие и общее описание структуры данных;

  2. Классификация СД;

  3. Простейшие статические структуры данных.

Понятие и общее описание структуры данных

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

  1. на логическом уровне;

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

На обоих уровнях можно дать более конкретное определение данных.

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

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

Множество элементарных данных, которые рассматриваются и обрабатываются вместе, называются структурами данных (СД).

В общем случае структура данных – совокупность правил и ограничений, которые отражают отношения, существующие между элементами данных (ЭД).

Все связи одного ЭД с другими ЭД, в некоторой СД образуют элемент «отношение».

СД состоит из ЭД, определенным образом взаимосвязанных между собой. Каждый элемент структуры в общем случае состоит из 2-х частей:

  1. ЭД;

  2. элемент отношения.

В свою очередь ЭД могут быть либо однозначные данные некоторого типа, либо некоторый набор данных одного (разного) типа.

В понятие типа элемента данных закладывается следующее:

  1. диапазон возможных значений;

  2. набор допустимых операций;

  3. способ машинного представления.

Взаимосвязь между элементами СД может быть представлена в виде графа, где вершины – отдельные ЭД, а ребра (дуги) – связи между ними.

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

На физическом уровне СД называется физической (структура хранения).

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

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



Кроме логической и физической формы любая структура характеризуется множеством операций над логической и физической структурой (ЛС и ФС). Набор операций над ФС определяется тем, в какой памяти реализуется СД: в ОП или ВП.

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

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

Классификация СД

Может проводиться по четырем признакам:

  1. наличие или отсутствие явно заданных связей между элементами структуры. По этому признаку выделяются:

  • связные структуры;

  • несвязные структуры.

К несвязным относятся вектора, массивы, строки. К связным – всевозможные списки.

  1. с точки зрения изменчивости структуры выделяются:

  • статические. Статические – такие структуры, в которых число элементов и связи между элементами не меняются (строки, вектора, массивы);

  • полустатические. Полустатические – возможно частичное изменение структуры (стеки);

  • динамические. Динамические – число элементов и связи могут меняться произвольно в любой момент (списки).

  1. по степени упорядоченности различают:

  • линейно-упорядоченные – один элемент строго следует за другим

  • линейно-неупорядоченные – нелинейные

  1. характер взаимного расположения элементов в памяти друг относительно друга. Различают:

  • структуры с последовательным расположением элементов (вектора, массивы, строки)

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

Простейшие статические структуры данных

К ним относятся:

  1. вектора;

  2. массивы;

  3. записи;

  4. таблицы.

1. Вектор – упорядоченное множество данных одного и того же типа.

Вектору соответствует одномерный массив. Элементы располагаются в памяти строго последовательно друг за другом. Такая упорядоченность позволяет перенумеровать элементы (номера-индексы).

Одна из наиболее частых операций – операция доступа к элементу с заданным индексом.

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

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

Физическая структура вектора сопровождается дескриптором, который располагается в памяти и имеет следующую природу - дескриптор состоит из полей:

  • внутренний код структуры данных

  • имя вектора

  • адрес первого элемента

  • нижнее значение индекса

  • верхняя граница индекса

  • тип элемента

  • размер слота

Первое поле позволяет определить ту СД, с которой связан дескриптор.

Адресная функция (функция отображения) в случае вектора может иметь следующий вид:

Исходные данные:

  • минимальное значение индекса: p

  • индекс, для которого ищется адрес: i

  • максимальное значение: q

  • размер слота: I

2. Массив, в общем случае, - это структура данных, каждый элемент которой может быть вектором.

Могут быть двумерные, трехмерные, n-мерные массивы. Для определения каждого элемента массива используется индекс (по каждой координате): .

Для доступа к элементу массива используется n индексов.

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

Рассмотрим пример.

Пусть имеется n-мерный массив:



– начальный элемент

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

Адресная функция рассчитывается:

,

где:

L – размер слота

D – определяется способом расположения массива в памяти (по строкам или столбцам). Если по строкам, то вначале располагается первая строка и т.д., если по столбцам – вначале первый столбец и т.д.

Для случая, если элементы располагаются по строкам, то:







Встречаются также:

  • симметричная квадратная матрица (элементы симметричны относительно главной диагонали и равны)

  • разреженная матрица (большинство элементов равны 0). Такие матрицы хранятся в виде списков.

3. Запись – упорядоченное множество элементов в общем случае разного типа (называются полями).

Записи могут быть простыми и вложенными (вместо поля может располагаться другая запись). Уровень вложенности отражается в дескрипторе записи.

4. Таблица – упорядоченная последовательность записей одного и того же типа (массив записей).

Таблицы широко используются для представления внутри системы (служба таблицы, таблицы кодов операций и т.д.).

Таблица состоит из записей, а запись – из полей.

Свойство однотипности записей означает, что все одноименные поля должны иметь одинаковые типы.

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

Типичные операции при работе с таблицами:

  • поиск записи (ищется вся запись);

  • добавление элемента;

  • удаление элемента;

  • сортировка.

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


Лекция 5. Понятие списковой структуры.

  1. Линейный список;

  2. Стек;

  3. Очередь;

  4. Дек.

Линейный список

Линейным списком называется линейно упорядоченная последовательность элементов данных. Их можно назвать: .

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

Если число n (элементов) при работе с такой структурой не меняется, то их можно свести к статической структуре данных (СД). Если же n меняется и структура связи неявная, - то это полустатическая СД; n меняется и структура связи явная, - это динамическая СД.

^ Стек

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





Xn


Операции со стеком:

  • исключение;

  • включение элемента.

Адресуется голова с помощью указателя, адрес которого хранится в ячейке.

При исключении элемента, содержимое ячейки Хn считывается, голова стека перемещается вниз, на следующий занятый элемент. Процесс продолжается до тех пор, пока голова стека не займёт позицию ниже Х1.

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

В дескриптор стека могут включаться следующие элементы:

  • код структуры;

  • имя;

  • адрес верхней границы (ВГ);

  • адрес нижней границы (НГ);

  • указатель на голову;

  • описание (тип, размер) элементов.


Очередь

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







Для каждого элемента – один слот.

Тип элементов одинаковый.

Р2 – адрес первого свободного слота за хвостом.

Операции:

  • исключение;

  • включение.

Новый элемент записывается в Р2, затем Р2 увеличивается.

При исключении: Р1 после исключения перемещается на следующий элемент.

Переполнение очереди: чтобы эта ситуация не была безвыходной, в случае, когда Р2 превышает Хmax – значение Р2 переводится на Х1, если он свободен.

Элементы дескриптора очереди:

  • код структуры;

  • имя;

  • адрес верхней границы;

  • адрес нижней границы;

  • указатель свободного места;

  • описатель элементов.

Очереди используют при описании ресурсов ЭВМ.

Дек

Дек – очередь, в которой включение и исключение элементов может выполнятся с любого из его концов.

Разновидности деков:

  • дек с ограниченным входом – включение только с одного конца, а исключение с обоих;

  • дек с ограниченным выходом – включать можно с обоих концов, исключать - с одного.

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


Лекция 6. Линейно-динамические структуры (ЛДС)

  1. Односвязные и двухсвязные списки;

  2. Линейные двухсвязные списки.

Односвязные и двухсвязные списки

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

^ Связный список – это СД, элементами которой являются записи одинакового формата. Эти элементы связываются с помощью указателей, которые в них же и располагаются. Элемент такого списка в простейшем случае – это два поля:

  • информационное;

  • поле связи.

Логическая структура




Простейший из связных списков – линейные односвязные списки. Линейность заключается в том, что для каждого элемента имеется единственный предыдущий и единственный последующий элемент (кроме первого и последнего элементов).

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

Физическая структура:

  • дескриптор;

  • набор областей памяти для записей.

Число записей неизвестно. Это определяет такой состав элементов в дескрипторе:

  • код структуры;

  • имя;

  • адрес начала;

  • текущая длина;

  • описатель отдельного элемента.

Операции: просмотр (для включения и исключения) списка от начала до его конца. Нужный элемент отыскивается по содержимому. Чтобы облегчить просмотр, делают из такого списка – кольцевой, где вместо признака Null находится адрес первого элемента. И тогда просмотр может начинаться с любого элемента.

^ Линейные двухсвязные списки

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

Удобство: можно двигаться в любом направлении.

Операции:

  • включение

  • исключение элемента.

Все элементы можно разбить на две группы:

1 – подлежат обработке (функциональный список);

2 – пустые (список свободных блоков).

Их форматы совпадают.







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

Для дальнейших примеров введём обозначения исходных данных:

  • FREE – указатель начала свободного списка в ячейке.

  • NEW – новый элемент, который можно добавить.

  • START – адрес начала функционального списка.

  • DATA – поле информации.

  • LINK - поле связи.


Лекция 7. Нелинейные связанные структуры (Древовидные и сетевые)

  1. Многосвязный список;

  2. Дерево.


Многосвязный список

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

Дерево – такая структура, которая характеризуется:

  • единственный элемент, на который не ссылается никакой другой элемент

  • начиная с корня, следуя по цепочке указателей, можно получить доступ к любому элементу.

  • на любой элемент (кроме корня) существует единственная ссылка.

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




Если имеется по крайней мере 2 вершины: x и y, то узел х называется родительским, у – подчиненным, если узлов у несколько, то все они являются потомками х, между собой они являются братьями или сестрами.

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

Те деревья, которые обычно рассматриваются, являются упорядоченными. Упорядоченность дерева означает упорядоченность между узлами-потомками, она означает, что слева направо между потомками существует отношение старшинства: слева- старший, справа – младший. Если степень исхода каждого узла не превышает m, то дерево называется m-арным.

Для m-арных деревьев: если степень исхода либо m, либо 0, то это полное m-арное дерево.

Каждое дерево характеризуется высотой – максимальной длиной пути от корня дерева до любого из листьев (измеряется в дугах)

Дерево представляется в виде многосвязного списка, если дерево m-арное, то число указателей = m.

Для каждого узла в памяти используется структура вида :


data

степень исхода

link1

link2



linkm






Рассмотрим пример:





Корнем дерева является узел А. С точки зрения полноты картины для каждого узла нужно использовать 5 слотов, но в этом нет необходимости. Нули означают конечный узел. Первый ноль – степень исхода, второй – конец цепочки.

Существуют бинарные деревья, у которых степень исхода<=2. Если в двоичном дереве степень исхода=2 или 0, то это полное бинарное дерево. Они представляют большой интерес, т. к. более просто представляются в машинной памяти в том смысле, что для каждого элемента необходимо хранить 2 указателя: первый – связь влево, второй – связь вправо.

Любое бинарное дерево также можно представить в виде двухсвязного списка.

Данное дерево является неполным. Любое m-арное дерево может быть заменено на эквивалентное бинарное.

Основными операциями над бинарным деревом являются:

  • 1. операция обхода узлов

  • 2. добавление

  • 3. исключение

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

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

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


Лекция 8. Компиляторы

  1. Элементы теории компиляции.

  2. Общая схема работы компилятора.

Элементы теории компиляции

Компилятор - системная обрабатывающая программа, которая переводит исходную программу, написанную на языке высокого уровня, в машинную форму (объектную программу).

^ Объектная программа представляет из себя последовательность машинных кодов.

То, что делает компилятор, состоит в изменении алфавита, лексики, синтаксиса при сохранении семантики (смысла).

^ Алфавит – множество допустимых символов, которое используется для построения конструкций языка.

Лексика – набор отдельных смысловых единиц языка (лексемы).

Лексема – минимальная конструкция языка, имеющая смысл.

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

Синтаксис – система правил, которые задают описание правильных конструкций языка.

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

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

Общая схема работы

Работа компилятора состоит из двух фаз:

1. фаза анализа

2. фаза синтеза

1. Фаза анализа начинается с работы лексического анализатора (сканера).

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

1) Таблица терминальных символов языка.

Она является исходной для работы сканера и строится разработчиком компилятора.

Терминальными символами являются:

  • Разделители

  • Знаки операций

  • Ключевые слова языка

2) Таблица символических имен (идентификаторов).

В нее сканер вносит каждое встретившееся ему имя, если оно построено по правилам и не относится к ключевым словам.

3) Таблица констант.

Для каждой константы запоминаются следующие характеристики:

  • Значение

  • Тип

  • Основание СС

  • Ширина (размер области памяти)

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

Кроме того, строится таблица кодов лексем, которая состоит из записей, в каждой из которых 2 поля.

Код типа лексем

Номер в таблице

I

5







I – признак того, что лексема является идентификатором

5 – позиция в таблице идентификаторов

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

Следующая часть фазы анализа – синтаксический анализатор (parser).

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

Конструкция – некоторая последовательность лексем, имеющая смысл.

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

Исходной информацией для работы синтаксического анализатора является таблица кодов лексем.

Следующая часть – семантический анализатор. Когда правильность конструкций установлена, запускается семантический анализатор. Проверка заключается в попытке интерпретации смысла конструкции. Достаточно часто синтаксически правильная конструкция является неправильной с точки зрения семантики. Например:

Var

a: integer;

Const

N:=2;

Begin

N:=a;

С точки зрения семантики это не правильно, т.к. делается попытка присвоить значение константе.

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

  • форма машинных кодов

  • форма языка Ассемблер

  • промежуточная форма

Наиболее часто используется промежуточная форма:

1) Тетрадная форма. В ней каждому оператору ставится в соответствие тетрада. Тетрада имеет следующий вид: Т1,Т2,Т3,Т4

Т1 – операция

Т2,3 – операнды

Т4 – результат

Например: А:=В + С*Д; *,С,Д,Т1

+,В,Т1,Т2

:=,Т2,

Здесь Т1,Т2 – промежуточные переменные.

2) Польская запись:

А:=В + С*Д СД*В + А=

На работе семантического анализатора фаза анализа заканчивается.

2. Фаза синтеза начинается с распределения памяти по переменным программы.

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

Такое выделение памяти называется статическим выделением памяти.

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

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

Следующий этап – оптимизация кода. Обычно осуществляется в двух направлениях:

  • сокращение объема программы

  • ускорение работы

Существуют два подхода:

  • оптимизация на уровне машинных команд

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

У данной схемы работы синтаксический и семантический анализ четко разделяется. Такая схема работы предполагает построение компиляторов с исполнением синтаксических методов и ориентированных на работу с широким классом языков.

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

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

^ Лекция 9. Понятие формального языка (ФЯ) и формальной грамматики (ФГ)

  1. Понятие формального языка (ФЯ) и формальной грамматики (ФГ).

Понятие формального языка (ФЯ) и формальной грамматики (ФГ)

Формальный язык – это некоторое множество предложений, состоящих из слов (строк).

Строка – это последовательность символов конечной длины (символы записаны один за другим). Каждый из этих символов является частью некоторого заранее определенного алфавита.

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

Замечание:

Для задания формального языка необходимо указать его алфавит и формальную грамматику.

^ Формальная грамматика – система правил для описания множества строк (конечной последовательности символов).

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

Пусть алфавит это ={0, 1}. Пусть из этого алфавита образована строчка 01001. Число символов в цепочке называется длиной цепочки m (независимо от совпадения символов). Пустой цепочкой называется цепочка, у которой m=0. Она обозначается ..или ..

Знак обозначает множество определенных над алфавитом строк (с точки зрения здравого смысла).

..={0,1,01,10,101,110,..}.

Пустое множество входит в любое множество.

Формальным языком L над алфавитом .. называется некоторое произвольное подмножество множества .. .

Знак .. разница с .. в одном символе. .. не включает в сея пустую строку.

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

Но число возможных предложений настолько велико, что их нельзя перечислить.

Поэтому существуют специальные языки для описания синтаксиса языков – метаязыки (языки над языками). На этом языке описывают систему правил, которая определяет правильность конструкций языка.

Грамматика – множество правил синтаксиса языка.

Грамматики могут быть двух разновидностей:

  • Порождающие;

  • Распознающие.

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

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

Замечание:

Эти грамматики различаются направлением движения.

Рассмотрим пример порождающей грамматики.

Она будет напоминать часть усеченного русского языка. Объекты грамматики: члены предложения, части речи.

Обозначения:

ПР- предложение

П – подлежащее

С – сказуемое

ИС – имя существительное

М – местоимение

ГФ – глагольная форма

Правила:

  1. <ПР>--<П><С>

  2. <П>--<ИС>

  3. <П>--<М>

  4. <С>--<ГФ>

  5. <ИС>--самолет

  6. <ИС>--дом

  7. <М>--он

  8. <ГФ>--стоит

  9. <ГФ>--строится

  10. <ГФ>--летит

Обозначения:

a—b a порождает b; из a следует b; b следует из a.

Стрелка указывает направление вывода.

-- есть, определяется как.

Замечание:

То, что справа, определяет то, что слева.

<имя> - нетерминальный символ

имя – терминальный символ.

Терминальные символы не подлежат раскрытию с помощью правил грамматики, нетерминальные подлежат.

Множество правил грамматики называется P.

В данном случае P указано в виде перечисления.

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

Правила ^ P содержат информацию о том, как из символов алфавита V построить правильное предложение языка (Те предложения, которые построены не по этим правилам, считается неправильными). В данном случае алфавит для грамматики G0 обозначается:

V = {<ПР>, <С>, <ИС>, <П>, <М>, <ГФ>, самолет, дом, он, стоит, строится, летит}.

В общем случае множество ^ V состоит из двух частей N и T, из множества символов.

Любой нетерминальный символ должен хотя бы один раз войти в левую часть правил (множество N).

N = {<ПР>, <П>, <С>, <М>, <ИС>, <ГФ>}

T – множество терминальных символов, входят только в правые части.

T = {самолет, дом, он, строится, стоит, летит}

Для порождающей грамматики S – начальный символ.

S = {<ПР>}.

Для компилятора (Паскаль) в качестве S выступает понятие «программа».

<Программа>--<Раздел описаний><Раздел действий>.

Если в правой части правил одна конструкция следует строго за другой, это означает конкатенацию (сцепление) этих строк.

Любая грамматика должна позволять две задачи:

  • либо задачи распознавания;

  • либо задачи порождения.

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

Каждое полученное понятие заменяется на своё определение. Этот процесс продолжается до тех пор, пока в правой части не окажется только терминальные символы.

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

Предложение состоит из конкатенации подлежащего и сказуемого. Подлежащим может быть либо ИС, либо М.

Предложение




Подлежащее Сказуемое


Существительное Местоимение Глагол


Самолет Дом Он Стоит Летит Строится

Вывод каждого конкретного предложения требует принятия решения: по какому пути пойти дальше вниз. Дерево описывает правила вообще. Самолет строится – например.

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

Двигаясь по дереву снизу вверх надо дойти от конкретного предложения до начального символа. Здесь производится замена правой части на левую (сворачиваем) часть правила.

Например, Дом летит.

ИС и ГФ; --П и С; --ПР.

В общем случае грамматика состоит из:

  1. Множество нетерминальных символов

  2. Множество терминальных символов

  3. Начальный символ

  4. Набор правил
  1   2



Скачать файл (469 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации