void ExecuteStatement();

выполнить очередную инструкцию

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

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

map<string, int> Locked; list<Process> Processes;

Займемся реализацией функций-членов класса Process.

Функция BlockedBy () возвращает идентификатор процесса, блокирующего текущий. Текущий процесс считается заблокированным, если таблица, указанная в его текущей инструкции, заблокирована каким-либо другим процессом. Если текущий процесс никем не заблокирован, то есть выпол-

няется нормально, функция возвращает нуль (таким образом, нуль нельзя использовать в качестве идентификатора процесса):

int Process::BlockedByО const {

блокирована ли таблица, с которой будет проведена операция? map<string, int>::iterator it = Locked.find(front О.Table);

if(it != Locked.end0 && it->second != ProcNo)

если да, вернуть номер блокирующего процесса return it->second;

return 0;

Функция-член UnlockAllTables () удаляет из массива Locked все таблицы, заблокированные текущим процессом:

void Process::UnlockAllTables() const {

map<string, int>::iterator it;

while((it = find if(Locked.begin(), Locked.end(), composel(bind2nd(equal to<int>(), ProcNo),

select2nd<map<string, int>::value type>()))) 1= Locked.end()) Locked.erase(it);

Немного экстравагантный предикат, переданный в качестве третьего аргумента функции find if (), возвращает true для всех элементов ассоциативного массива Locked, поля значение которых равны ProcNo.

Рассмотрим устройство предиката. Функция

select2nd<map<string, int>::value type>()

для любого переданного объекта типа map<s tr ing, int>: : valuetype (to есть пары вида (string, int)) возвращает его правую (типа int) составляющую.

Вспомогательная функция bind2nd () в контексте

bind2nd(equal to<int>(), ProcNo)

превращаетдвухаргументнуюфункциюequal to<int>(int а, int b), сравнивающую два целых числа, в одноаргументную функцию, сравнивающую переданное число со значением ProcNo.

5 Здесь подразумевается, что элементами ассоциативного массива являются пары вида (ключ,

значение).

struct statement {

string Command, Table;

bool operator==(const Statements rhs) const

{ return Command == rhs.Command && Table == rhs.Table; }

Процесс представляет собой очередь инструкций:

class Process : public c3ueue<Statement> (

private:

int ProcNo; идентификатор процесса public:

Process(int pn) : ProcNo(pn) {}

bool operator==(const Process& rhs) const

{ return ProcNo == rhs.ProcNo; } int GetProcNoO const { return ProcNo; } int BlockedByO const получить идентификатор

блокирующего процесса

void UnlockAllTables() const; разблокировать все таблицы,

заблокированные процессом

------------------------------------------------------------

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

int N;

ввести количество процессов cin N;

randomize(); string line; getline(cin, line);

считать N строк, каждая из которых содержит инструкции одного процесса. Например: lock а read а unlock а for(int i = 1; i <= N; i++) {

getline(cin, line); istringstream is(line);

создать процесс с идентификатором i Process proc(i); while(lis.eof()) {

считать все инструкции из строки line

Statement s;

is s.Command;

is s.Table;

добавить очередную инструкцию в процесс proc.push(s);

добавить процесс в список процессов Processes.push back(proc);

пока существует хотя бы один выполняющийся процесс

while( ! Processes.empty О)

посчитать количество незаблокированных процессов int NotBlocked = 0;

for(list<Process>::iterator it = Processes.begin();

it != Processes.endO; it++)

if(it->BlockedBy0 ==0) NotBlocked++;

если все процессы заблокированы if(NotBlocked ==0)

разрешить взаимные блокировки ResolveDeadlocks();

else {

Функция composel () объединяет возвращаемые операциями bind2nd () и select2nd () функциональные объекты в композицию. Теперь в качестве сравниваемого с числом ProcNo объекта выступает второй элемент пары ключ, значение , возвращаемый функцией select2nd().

Последняя функция-член класса Process выполняет очередную инструкцию процесса (в предположении, что это возможно):

void Process: :ExecuteStateinent () {

найти процесс, заблокировавший таблицу, указанную в текущей команде

map<string, int>::iterator it = Locked.find(front().Table);

if(front 0.Command == unlock )

{ .

разблокировать таблицу, если она заблокирована

if(it != Locked.end()) Locked.erase(it);

else if(front 0.Command == lock ) {

заблокировать таблицу, если она еще не заблокирована if(it == Locked.end О)

Locked[front О.Table] = ProcNo;

вывести выполняемую операцию

cout ProcNo : front0 .Command front().Table endl; popO; удалить операцию из очереди

если операций больше нет

if(empty О)

cout ProcNo : нормальное завершение процесса endl; UnlockAllTables();

Функция main () реализует алгоритм на псевдокоде, приведенный в подсказке.

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

Из двух процессов больше тот, который блокируется процессом

с большим идентификатором

bool ProcCompare(const Process& Ihs, const ProcessSc rhs) {

return Ihs.BlockedBy() < rhs.BlockedBy();

it->ExecuteStatement();

выполнить операцию

если процесс завершился, удалить его из списка if(it->empty())

Processes.erase(it);

return 0;

Общий алгоритм разрешения взаимных блокировок выглядит так:

цикл

deadlocks left = false*,

ЕСЛИ некоторый процесс Р принадлещ /циклу а- -ррафё-блокировок яяк1=>г>т11гтк ныпопнение Р .-ls

завершить выполнение Р удалить Р из списка выполняемыхПроцессов deadlocksleft = true ПОКА deadlocks left

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

enum COLOR { BLACK, WHITE, GREY }; цвет меток вершин vector<COLOR> Marks; метки вершин

----------------------------------------------------------------

int Search(int v) {

Marks[v] = GREY;

пометить текущую вершину серым цветом

Мы переходим к центральному алгоритму программы: поиску и разрешению взаимных блокировок. Как уже было сказано, схему блокировок процессов можно представить в виде графа (рис. 3.1). Одним из методов выявления циклов в графе является так называемый цветной поиск в глубину (colored depth-first search).

Изначально все вершины графа помечаются белым цветом. Затем выполняется следующий алгоритм:

цикл по B<i&A вершинам графа

ЕСШГРекущая вершина помечена белым цветом пометить вершину серым цветом

цикл .

V пометить очередную вершину-потомок серым цветом С/если помечаемая вердина уже серая, цикл в графе найден КОНЕЦ ЦИКЛА

пометить все рассмотренные вершины чёрным цветом

КОНЕЦ ткш / >

6 Поскольку здесь происходит поиск в глубину, рассматриваются как непосредственные потом-

ки, так и потомки потомков.

найти вершину, являющуюся непосредственным потомком int и = (find(Processes.begin(), Processes.end(), (*)

Process(v)))->BlockedBy();

if(u != 0) если вершина существует

if(Marks[u] == GREY) и помечена серым, то цикл найден: return и; вернуть вершину, принадлежащую циклу else if(Marks[и] == WHITE) {

если вершина помечена белым продолжить поиск для подграфа

int V = Search(и);

if(v > 0)

return v;

) все чёрные вершины уже рассмотрены ранее, } для них никаких действий не требуется

Marks[v] = BLACK; пометить текущую вершину чёрным цветом return 0; цикл не найден

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

сортировать по идентификатору блокирующего процесса, чтобы все незаблокированные процессы (идентификатор блок1фующего равен нулю) оказались в начале списка Processes.sort(ProcCompare);

выбрать случайный незаблокированный процесс int г = random(NotВ1ocked);

list<Process>::iterator it = Processes.begin(); for(int i = 0; i < r; i++) it+ + ;