Примеры работы программы-планировщика:

D:\Projects>dbms 2

lock а write а read а unlock а lock b write b read b unlock b 1: lock a

lock b write b read b 1: write a 1: read a unlock a

нормальное завершение процесса 2: unlock b

2: нормальное завершение процесса

2: 2: 2:

1: 1:

D:\Proj ееt s>dbms

lock a lock b unlock b unlock a lock b lock a unlock a unlock b 2: lock b 1: lock a

1: аварийное завершение процесса 2: lock a 2: unlock a 2: unlock b

2: нормальное завершение процесса

D:\Projects>dbms 2

lock a read a unlock a lock a read a unlock a 2: lock a 2: read a 2: unlock a

2: нормальное завершение процесса 1: lock a 1: read a 1: unlock a

1: нормальное завершение процесса

3.1.3. Сортировка сайтов Поиск компонент связности графа

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

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

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

И вот, наконец, код функции, разрешающей взаимные блокировки:

void ResolveDeadlocks(> {

выделить Пс1мять под массив меток вершин (нулевой элемент зарезервирован) Marks.resize(Processes.size О + 1);

bool deadlocks left;

deadlocks left = false;

пометить все процессы (вершины графа) белым цветом for(list<Process>::iterator it = Processes.begin();

it != Processes.endO; it++) Marks[it->GetProcNo()] = WHITE;

int p;

цикл no всем белым вершинам

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

it != Processes.endO; it+ + ) if(Marks[it->GetProcNo()] == WHITE)

if((p = Search(it->GetProcNo())) != 0) {

если в графе найден цикл (р принадлежит циклу) получить итератор на соответствующий объект процесса

list<Process>::iterator it = find(Processes.beginO,

Processes.endO, Process(p)); cout it->GetProcNo()

*: аварийное завершение процесса endl; it->UnlockAllTables(); Processes.erase(it); deadlocks left = true; break;

while(deadlocks left);

cout pages[i-l]->name * pg->cluster;

cout endl; } while (FindNext(sr) == 0); FindClose(sr);

Решение

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

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

struct THtmlPage {

string name; имя файла

int cluster; кластер, к которому относится страница

vector <THtmlPage*> references; массив ссылок на другие страницы

vector <THtinlPage*> pages; страницы, подлежащие кластеризации

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

Изначально каждая страница находится в своём собственном кластере:

void LoadAllPagesО {

THtmlPage* pg; TSearchRec sr; int i = 0;

будут просмотрены *.htm и *.html файлы if (FindFirst(*data\\*.htm?*, 0, sr) == 0) {

do {

pg = new THtmlPage; pg->name = sr.Name.c str();

инициализация: каждая страничка - свой кластер pg->cluster = i++; pages.push back(pg);

В более общем виде задача кластеризации рассматривается в шестой главе.

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

void CreateGraph() {

for ( int i = 0; i < pages.size(); i++) {

загружаем содержимое странички

ifstream in{ ( dataW + pages [i]->name) . c str ()) ;

string buf;

int Ipos, rpos;

TSearchRec sr;

выявляем наличие гиперссылок и проверяем, есть ли такие среди имён в массиве pages while ( in buf ) {

ищем строку, в которой есть гиперссылка if (dpos = buf .find (-href =*, 0)) +1) {

находим второй, он же крайний знак Ipos = rpos = buf .findC , 6); 6 == strlen{-href=-) + 1 while (buf[-Ipos] <= / && buf[lpos] != )

lpos++;

скопируем интересующее нас имя файла string file name;

copy(buf.begin() + Ipos, buf.beginO + rpos,

back inserter(file name)); for ( int f = 0 ; f < pages.sizeO ; f + + ) if ( i != f)

проверяем на соответствие

if (pages[f]->name == file name)

ссылка найдена, добавляем её

(собственно, создание графа)

pages[i]->references.push back(pages[f]);

делаем граф неориентированным

pages[f]->references.push back(pages[i]);

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

Функция GetClusters () находит компоненты связности полученного графа:

void GetClustersО {

int i, j;

int new cluster, old cluster;

bool changed;

changed = false;

for (i = 0; i < pages.sizeO ; i++)

for (j = 0; j < pages[il->references.size(); j++) {

если кластеры ссылающейся странички и ссылки еще не совпадают, помещаем их в один кластер if ((new cluster = pages[i]->cluster) != (old cluster = pages[i]->references[j]->cluster))

pages[i]->references[j]->cluster = new cluster;

в этот же кластер помещаем все странички, ранее находившиеся в old cluster

for ( int к = 0; к < pages.sizeO; к++ )

if ( pages[k]->cluster == old cluster ) pages[k]->cluster = new cluster; changed = true;

}while(changed);

for ( i = 0; i < pages.sizeO; i++ )

cout page pages [i]->naine cluster pages[i]->cluster \n;

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

void SaveGraphO {

TSearchRec sr;

for ( int i = 0; i < pages.sizeO; i++) {

сохраняем каждый кластер в отдельный каталог

if (FindFirst( ( dataW + pages[i]->name) .c str() , 1, sr) == 0)

if (!DirectoryExists(-sorted\\ + (AnsiSt-ring)pagesU]->cluster) ) if (iCreateDir( sortedW + (AnsiString)pages[i]->cluster)) . throw Exception( Cannot create sorted directory. ); CopyFile (( dataW + pages [i]->name) .c str () ,

( sortedW + (AnsiString)pages [i]->cluster + W + sr .Name) .c str О , 0); FindClose(sr);

Для наглядности напишем ещё одну вспомогательную функцию, выводящую результаты:

void ShowGraph() {

cout \n;

for ( int i = 0; i < pages.sizeO; i + + ) {

cout page name: pages[i]->name endl; for ( int j = 0 ; j < pages[i]->references.size();]++) cout references:

pages[i]->references[j]->name endl;

cout \n;

Теперь всё. Осталось написать функцию main ():

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

if (!DirectoryExists( sorted )) {

if (ICreateDir( sorted ))

throw Exception( Cannot create sorted directory. );

русский текст следует выводить в консоль с помощью CharToOem()®.

char buf[256]; размер буфера зависит от размера исходной строки

::CharToOem( Файлы, подлежающие сортировкеХп , buf ); cout buf << endl; LoadAllPages(); CreateGraph();

8 Вопрос о выводе кириллицы в консоль часто поднимается на различных форумах, поэтому я

счел уместным привести здесь его простое решение.