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

76

Денотационная семантика

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

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

Модели вычислительных процессов: Модель графов распределения ресурсов

Модель вычислительного процесса

Абстрактно модель вычислительного процесса можно представить в виде схемы черного

ящика.

Определим вычисления, определяющие процесс P и протекающие в вычислительных ресурсах R как обработку операционного пакета Iin, в результате чего формируется выходной пакет Iout. Пусть момент начала вычислений определяется входным управляющим воздействием Cin, а их завершение фиксируется по выдаче вычислительным ресурсом управляющего сигнала Cout. Графическое обозначениеэтих вычислений представлено на рисунке 1. Иерархическая организация вычислений позволяет говорить о том, что процесс можно разделить на более мелкие подпроцессы, каждый из которых может выполняться в отведенной для этого части общих ресурсов. При этом, одни и те же ресурсы могут повторно использоваться при выполнении различных вычислений, разделяясь подпроцессами во времени.

Рисунок 1 - Процесс как вычисления, протекающие в ресурсе В данном случае ключевыми абстракциями, важными факторами, являются исходные

данные – входной пакет Iin и входное управляющее воздействие Cin. В результате работы вычислительного процесса на выходе получится выходной пакет Iout и входное управляющее воздействие Cout.

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

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

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

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

77

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

Информацияовыполненииусловийготовностиврассматриваемоймоделиподтверждается наборами соответствующих управляющих сигналов:

1.сигналами готовности элементов операционного пакета;

2.сигналами готовности необходимых вычислительных ресурсов;

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

ресурсов.

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

Модель графов распределения ресурсов.

Объясним понятие «Тупики» Для описания и исследования подобных ситуаций введем формальную модель системы в

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

Пустьвсистемеимеетсяmвидовресурсов(например,процессор,память,устройствавводавывода). Будем обозначать типы ресурсов в системе R1, R2, ... Rm. Пусть каждый тип ресурса Ri имеет Wi экземпляров. Каждый процессможет использовать ресурсоднимиз следующих способов:

-запрос (request);

-использование(use);

-освобождение (release).

Тупик может возникнуть, если одновременно выполняются следующие четыре условия:

-взаимное исключение: только один процесс в каждый момент времени может получить доступ к ресурсу;

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

-отсутствие прерываний: процесс может освободить ресурс только добровольно, когда завершит свою работу;

-циклическое ожидание: существует множество {РО, Р1, ... Р0}, такое, что РО ожидает ресурса, которым обладает P1; P1 ожидает ресурса, которым обладает Р2 ... Рn ожидает ресурса, которым обладает Р0.

Граф распределения ресурсов Множество вершин V и множество дуг Е. V подразделяется на два типа вершин:

-Р = {Р1 Р2 ,..., Рп}, множество всех процессов в системе,

-R = {R1 ,R2, ..., Rm}, множество всех ресурсов в системе,

•Дуга типа "запрос" (request edge) – направленная дуга Pj → Rj

•Дуга типа "присваивание" (assignment edge) – направленная дуга Rj → Pj

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

78

Граф распределения ресурсов

Данный граф изображает систему с 3 процессами и 4 видами ресурсов: ресурсы видов 1 и 3 имеют по 1 экземпляру, ресурс вида 2 – 2 экземпляра, ресурс вида 4 – 3 экземпляра.

Процесс 1 претендует на ресурс 1, который занят процессом 2. Процесс 2 претендует на ресурс 3, который занят процессом 3 Две единицы ресурса 2 отданы процессам 1 и 2 соответственно. Ресурс 4 не распределялся (все три единицы свободны).

Граф распределения ресурсов с тупиком

Имеется ситуация циклического ожидания между процессами 1, 2 и 3. Процесс 1 претендует на ресурс, которым владеет процесс 2. Процесс 2 претендует на ресурс, которым владеет процесс 3.

Процесс 3 претендует на ресурс, одна единица которого отдана процессу 1, а вторая – процессу 2.

Граф распределения ресурсов с циклом, но без тупика

Вданном случае (имеется четыре процесса и два вида ресурсов.

Вцикле участвуют вершины-процессы 1 и 3.

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

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

Аналогично, процесс 3, претендоющий на ресурс 2, сможет его получить после его освобождения процессом 4 (а не 1).

Если граф распределения ресурсов не содержит циклов, то в системе тупиков нет; Если граф распределения ресурсов содержит цикл, то возможно два случая:

-если ресурсов каждого вида имеется только по одному экземпляру, то имеет место тупик;

-если ресурсов по несколько экземпляров, то тупик возможен.

Граф распределения ресурсов для стратегии избегания тупиков(ИТ)

Для реализации стратегии ИТ к данному графу необходимо добавить информацию не только о фактических, но и о возможных в будущем запросах ресурсов со стороны процессов. Для этого, в дополнение к дугам запросов и присваиваний, введем в рассмотрение дугу потребности (claim edge), которая ведет из вершины-процесса Р1, в вершину-ресурс R2 обозначается пунктирной линией и означает, что процесс Р1 может потреблять ресурс R2, когда процесс фактически запрашивает данный ресурс, дуга потребности преобразуется в дугу запроса (пунктирная линия

→ сплошной). Когда процесс освобождает ресурс, дуга присваивания преобразуется обратно в дугу потребности. Цель данной модификации графа – обеспечить, чтобы потребность в ресурсах была априорно известна

системе.

79

Вычислительные схемы

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

Графпотокаданных(информационный граф) определяет входные и выходные данные для каждого оператора. Дуга (Ri Sk) от регистра Ri к оператору Sk означает, что данные Ri являются элементом входных данных этого оператора;

дуга (Sk Rj) определяет данные Rj как выходные для Sk. Некоторые данные R могут являться выходными для оператора Si и входными для оператора Sj. Пример графа потока данных для некоторой вычислительной схемы представлен на рисунке 5.1 а);

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

Граф управления определяет последовательность выполнения операторов.

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

Пример графа управления представлен на рисунке 5.1 б).

Последовательность операторов S1, S2, … , Sn, ..., называется последовательностью исполнения схемы.

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

80

Реляционные системы управления базами данных Объектно-ориентированные базы данных

Реляционные СУБД

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

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

История реляционной модели

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

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

Иерархическая модель широко применялась в ранних СУБД, однако оказалась недостаточно гибкой. Отдельные записи в ней могут иметь несколько дочерних записей, однако по иерархии каждая записьможет иметь только одного «родителя». Поэтому ранниеиерархическиебазыданных были ограничены только отношениями «один к одному» и «один ко многим». Отсутствие поддержки отношения «многие ко многим» становилось проблемой при работе с точками данных, которые нужно связать с несколькими родителями.

Вконце 1960-х ученый-компьютерщик Эдгар Ф. Кодд, работавший в IBM, разработал реляционную модель управления базами данных. Реляционная модель Кодда позволяет связывать отдельные записи более чем с одной таблицей, тем самым создавая между точками данных отношения «многие ко многим» (в дополнение к отношениям «один ко многим»). Когда дело касалось проектирования структур БД, эта модель обеспечила большую гибкость, чем другие существующие на тот момент модели. Это означало, что реляционные системы управления базами данных (РСУБД) могли удовлетворить гораздо более широкий спектр потребностей.

Кодд предложил язык для управления реляционными данными по имени Alpha, который повлиял на развитие более поздних языков БД. Двое коллег Кодда из IBM, Дональд Чемберлин и РэймондБойс, создали свой язык, вдохновленный Alpha. Они назвали его SEQUEL (StructuredEnglishQueryLanguage), но такая торговая марка уже существовала, и тогда они сократили название языка до SQL (StructuredQueryLanguage).

Из-за аппаратных ограничений ранние реляционные базы данных были очень медленными. Чтобы технология получила широкое распространение, потребовалось некоторое время. Но к середине 1980-х годов реляционная модель Кодда была реализована в ряде коммерческих продуктов для управления базами данных как от IBM, так и от ее конкурентов. Эти вендоры последовали примеру IBM, разработав и внедрив свои собственные диалекты SQL. К 1987 году и Американский национальный институт стандартов, и Международная организация по стандартизации ратифицировали и опубликовали стандарты для SQL, укрепив его статус как принятого языка для управления СУБД.

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

Всвязи с резким ростом популярности РСУБД в 1980-х годах многие компании стали позиционировать свои СУБД как «реляционные» в рекламных целях, иногда не имея для этого достаточныхоснований,вследствиечего автор реляционноймоделиданныхЭдгарКоддв1985году опубликовал свои знаменитые «12 правил Кодда», которым должна удовлетворять каждая РСУБД.

13 правил (в данном случае исчисление начинается с 0), которым должна удовлетворять каждая РСУБД .