Автоматы с магазинной памятью.

Число: 4.9.12. Лекция номер 1.

Вычислительные процессы.

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

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

Формальное определение процесса.

В 1973г. пара ученых по фамилиям Хорнинг и Рендел построили систему формальных определений понятий процессов и сопутствующих ему других понятий. Согласно их определению, процесс определяется через набор переменных характеризующий его состояний Х=(Х0, Х1,..., Хn)- набор переменных состояний.

Состояние описывается заданием всех значений входящих в НПС(набор переменных состояний).

Пространство состояний для фиксированного НПС это множество состояний которое может принимать этот набор переменных. Размер пространства состояний определяется как P(x)=|X0|*|X1|*...*|Xn|*...

Действие это присваивающие значений некоторым некоторым из n событий.

Работа это последовательность состояний принадлежащий пространству состояний.

Выполнение работы это применение действий некоторым переменным

Функция действия описывает действие которое нужно применить к каждому очередному состоянию.

В пространстве состояний есть особые элементы совокупность которых формирует начальный НПС.

Реализация процесса.

Каждый программный процесс однозначно определяется некоторой структурой, называемой дескриптором (описатель) состоит из:

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

2) Защищенные области хранящие текущие значения регистров памяти.

3) Информация ресурса которыми владеет, может владеть и может пользоваться данным процессом.

Машинное представление процесса есть, дескриптор процесса и область памяти, которая для него выделяется.

Существует два подхода к построению ОС:

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

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

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

Лекция номер 2.

Вычислительный процесс. Простейшие модели вычислительных процессов. Отношения между элементами ВП.

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

Фактически программа является одним из способов задания алгоритма наследуя при этом его свойства:

1. Дискретность - разделены конечным не нулевым отрезком времени.

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

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

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

5. Конечность - алгоритм должен быть определен по времени.

Простейшие модели ВП.

Детерминированные формальные грамматики которыми описываются автоматы. Автомат определяется через следующие составляющие:

A. Алфавит автомата V,

B. Q- множество состояний автомата,

C. R множество закл состояний,

D. q0 выделенное начальное состояние автомата,

E. l длина цепочки символов подаваемых на вход автоматам.

Конечный автомат можно представить как абстрактную машину похожую на машину Тьюринга со следующими особенностями:

1. Выделенное конечное состояние автомата.

2. Машина является только читающей.

3. Считав символ на каждом шаге головка автомата передвигается на одну позицию вправо переводя автомат в новое состояние.

4. Заканчивает работу автомат, когда головка доходит до конца слова.

Работа автомата представляет собой последовательность шагов.

Определяется набором значений (q,w,n) , где q - текущее состояние, w - цепочка входных символов, а n - положение указателя в данной цепочки.

Приведем пример конечного автомата выполняющего действия по размену одной 10-ти рублевой монеты на две 5-ти рублевые.

Автоматы с магазинной памятью.

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

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

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

ВП формируется из элементов двух видов:

1. Действие.

2. Изменение условий(переход).

Все элементы ВП уникальные, между элементами ВП могут возникать следующие отношения :

1. Отношение предшествовния - когда элемент X входит в процесс раньше чем элемент Y.

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

3. Отношение альтернативы - когда реализация одного из элементов исключает реализацию другого.

Лекция 3.

Для описания процессов исследования их свойств связей между ними используется синтаксическая форма представления процесса.

Разновидности ВП.

1. Последовательный процесс: все элементы такого процесса связаны отношением следствия.

2. Параллельный процесс: любая пара различных элементов связанные либо отношением следствия либо отношением параллелизмом.

3. Последовательный процесс: любоя пара связана либо отношением следования либо отношением альтернативы.

4. Параллельный альтернативный процесс: связана либо отношением следования либо отношением параллелизмом.

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

Существует три основных видов структурных конфликтов:

1. RAW: read after write, когда последующая команда пытается прочитать операнд прежде, чем команда-предшественник данные в этот операнд запишет.

2. WAR: write after read, когда последующая команда пытается записать данные в операнд прежде чем команда предшественник сможет написать данные в операнд.

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

Какая-то тема.

Процесс выполняется в одном из двух режимов:

1. Системный процесс запускается в режиме ядра и не имеет запускающего файла.

2. Прикладной процесс пораждается при запуске любых прикладных программ.

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

Процесс может находится в системе в одном из следующих состояний:

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

2. Процесс исполняется в режиме ядра, процесс может ожидать в системе освобождение не доступного в данный момент ресурса(как бы засыпает возвращая управление ОС).

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

4. Процесс создан и готов к исполнению и ему доступны все ресурсы кроме вычислительных.

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

6. Процесс завершается.

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

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

0-кольцо уровень ядра ОС доступ для пользовательских задач полностью зарыт,

1-е кольцо уровень системы вызовов на уровне этого кольца ядро системы общается с пользовательскими задачами перешедшие в режим ядра,

3-е уровень системных библиотек может вызывать приложения их функции и читать данные но не может модифицировать что либо из этих данных.

Уровень задач низший приоритет:

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

Лекция 4.

Состав ядра ОС.

Ядра любой ОС состоит из нескольких базовых блоков. Основных блоков 3 иногда те же функции выполняет 4-ре блока:

1. Блок управления процессами- в его задачу входит:

1. создание новых процессов

2. Планирование выполнения процессов, путем переключения.

3. Поддержка межпроцессного взаимодействия.

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

3. Блок управлением кэш памятью - осуществляет работу с кэш памятью.

4. Блок управления файлами/файловыми системами - он осуществляет управление драйверами устройств(или отдельный блок).

5. Блок управлениями файловыми системами.

6. Блок управлением сетью.

При запуске нового процесса, ОС предпринимает ряд шагов:

1. Выделение адресного пространства для выполнения задачи.

2. Восстановление среды исполнения задачи.

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

4. При запуске каждой новой задачи ОС приходится решать следующие вопросы:

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

2. Как оптимально разместить и разграничить области памяти занимаемые родительскими и дочерними процессами

3. Как сохранять состояние процессов при переключении между ними.

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

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

В современных системах, механизм трансляции "зашит" в специальный блок микропроцессора - блок управлением памятью(MMU). У каждого процесса имеется своя собственная таблица описателей, называется она LDT, а также в системе ведется(в современных ОС она дублирована) GDT

Лекция 5.

Архитектура памяти.

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

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

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

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

3. Сегмент стека.

4. Сегменты не иницыализированных данных в него попадают данные не имеющие начальные значения.

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

Виды моделей памяти:

1. TINY в ней данные и код находятся в одном сегменте, используются только короткие указатели, а исполняемый модуль имеет только com формат.

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

3. COMPACT 1 сегмент кода/много сегментов данных, первая модель в которой могут быть использованы дальние указатели.

4. MEDIUM 1 сегмент данных/много сегментов кода, так же могут быть использованы дальние указатели.

5. LARGE много сегментов кода и много сегментов данных, используются дальние указатели.

6. HUGE много сегментов кода и много сегментов данных, принудительно все указатели переводятся в дальние.

Виртуальная память.

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

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

Еще одним механизмом управления виртуальной памяти является механизм своппинга, с его помощью происходит управление ВП за три основных этапа:

1. Управление пространством на устройстве куда выгружаются страницы.

2. Контроль выгрузки областей памяти на устройство выгрузки.

3. Подкачка фрагментов в основную память.

Этот механизм может использовать как отдельные файлы своп файлы, так и области на диске которые он бронирует.

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: