catch (...) нормальное завершение работы {

cout Нормальное завершение работыХп ; печать значений всех переменных программы for(map<string, int>::iterator p = Variables.begin(); p

Variables.end(); p++) cout p->first * = * p->second endl;

for(unsigned i = 0; i < Program.size(); i++) delete Program[i];

return 0;

Примеры:

D:\Projects>solveunsolvable 10 asgn i i + 1 goto 20 20 asgn s s + i goto 30 30 if i < 5 goto 10 else 40 40 end

Нормальное завершение работы i = 5 s = 15

D:\Projects>solveunsolvable

10 asgn С С + 1 goto 15

15 asgn С С - 1 goto 20

20 if 10 = 10 goto 10 else 30

30 end

Обнаружен бесконечный цикл!

D:\Projects\>solveunsolvable 10 asgn i i + 1 goto 10 20 end

Выход переменной за границы допустимого диапазона!

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

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

Задача останова для реальной компьютерной программы, занимающей заведомо конечный объём памяти, теоретически может быть

3 Зм.772

ProgramStateC) : CurLine(CurrentLine), Vars(Variables) {}

определим на множестве состояний отношение порядка

bool operator<(const ProgramState& rhs) const

if(CurLine == rhs.CurLine)

return Vars < rhs.Vars; return CurLine < rhs.CurLine;

Возникаюище в программе состояния записываются во множество

States:

set<ProgramState> States;

Осталось лишь написать функцию main ():

int main(int argc, char* argv[]) {

string line;

ввод nporpeiMMbi на языке TinyPower с клавиатуры while(getline(cin, line) && line != * ) ParseLine(line);

CurrentLine = Program.begin()->first; первая инструкция

while(1) {

текущее состояние ProgramState curstate;

если состояние не найдено во множестве States if (States, find(curstate) == States. end О) ,

добавить curState в States

States.insert(curstate);

else {

если состояние найдено, программа зациклилась cout Обнаружен бесконечный цикл! ; break;

выполнить очередную инструкцию Program[CurrentLine]->Perform();

catch(overflow error&) {

cout Выход переменной за границы допустимого диапазона!Хп ;

!\1а1аШаш

Поскольку таблица, в которую производится запись, всего одна, а пользователей несколько, фактическая последовательность выполняемых операций зависит от планировщика СУБД (то есть операции у нас выполняются не параллельно, а всё-таки последовательно2). Например, не исключён такой сценарий:

изначально на счету находится 20 ООО рублей

муж: М = ДенегНаСчёте(А)

жена: М = ДенегНаСчёте(А)

муж: М = М + S1

муж: ЗаписатьНаСчёт(А, М)

жена: М = М + S2

жена: ЗаписатьНаСчёт(А, М)

- М = 20 ООО

М = 20 ООО

М = 20 ООО + 10 ООО

на счету 30 ООО рублей

М = 20 ООО + 100

на счету 20 100 рублей

итого: на счету 20 100 рублей

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

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

lock А- заблокировать таблицу А (если таблица уже заблокирована, ничего не делать);

unlock А - разблокировать таблицу А (если таблица уже разблокирована, ничего не делать);

read А - считать данные из А;

write А - записать данные в А.

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

Если предположить, что сведения о счетах хранятся в таблице Accounts, процедура положить деньги на счёт дополняется парой операций lock/unlock:

lock Accounts

М = ДенегНаСчёте(А)

М = М + S

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

файл с интернета и слушаете музыку на однопроцессорном компьютере.

решена с помопЦ)Ю приведённой выше процедуры (в предположении, что памяти компьютера хватит для хранения всего множества состояний),

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

3.1.2. Планировщик СУБД Разрешение взаимных блокировок

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

Написать домашнюю картотеку довольно просто. Придумать оптимальный способ хранения больших объёмов данных сложнее. Реализовать поддержку языка SQL ещё сложнее, но СУБД промышленного уровня сталкиваются и с проблемами совершенно иного рода, связанными, например, с организацией доступа к данным нескольким пользователям одновременно.

Одной из таких проблем нам сейчас и предстоит заняться. Речь пойдёт о разрешении так называемых взаимных блокировок (deadlocks).

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

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

М = ДенегНаСчёте(А) М = М + S

ЗаписатьНаСчёт(А, М)

р1: lock А

р2: lock В

р1: lock В

р2: lock А

/7 процесс приостановлен до освобождения

таблицы В процессом р2

процесс приостановлен до освобождения

таблицы А процессом р1

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

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

Безусловно, наличие операций блокировки не гарантирует отсутствия ошибок со стороны программиста. Но этот вопрос остаётся за рамками компетенции планировщика СУБД.

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

Пример ввода:

lock а lock b

write а read а unlock а первый процесс write b read b unlock b второй процесс

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

3 Проще всего из всех процессов-кандидатов выбрать случайный. В СУБД промышленного

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

ВЗАИМНЫХ

БЛОКИРОВОК

блокируется

ВЗАИМНАЯ БЛОКИРОВКА

блокируется

Рис 3.1. Использование графа для выявления взаимных блокировок

Подсказка

Планировщик работает по следующему алгоритму:

ПОКА существует хотя бы один выполняющийся процесс . найти множество мезаблокированных процессов Р ЕСЛИ Р xiycTO Дз*с есть все процессу заблокированы) - >/ ЛрКА в, сйсздаме есть; взаимные блокировки . * I * прервать выполнение одного из процессов

ясключить, его из списка процессов

КОНЕЦ ЦИКЛА

ИНАЧЕ; {есть незаблокированные 1фоцёесы)]

случайш!1М образом выбрать процесс- из, - ,J

выполнить очередную его инструкцию * \ * если процесс з<э.верл1ился, исключить его из списка процессов КОНЕЦ ЦИКЛА

Для поиска взаимных блокировок придётся проанализировать граф, вершинами которого являются процессы, а дугами - блокировки (рис. 3.1). Дуга р1 -► р2 существует, если процесс р1 блокируется процессом р2.

Решение

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

Первым делом определим тип данных Statement, описывающий произвольную инструкцию каждого процесса, выполняемого на сервере баз данных. Инструкция состоит из команды (read, write, lock, unlock)и имени таблицы, над которой производится действие:

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

ЗаписатьНаСчёт(А, М) unlock Accounts

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

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