Параллельная обработка односвязных кольцевых списков в памяти ОС Windows
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
то метод синхронизации потоков путем использования дополнительной кучи в процессе оказался для меня неожиданным. Но разобравшись в его особенностях, я нашла его весьма удобным и, как следствие, полезным.
ИСПОЛЬЗОВАННЫЕ ИСТОЧНИКИ ИНФОРМАЦИИ
1. Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd edition. The MIT Press, 2001
">2.
. Методические указания к выполнению работы
. Джеффри Рихтер "Windows для профессионалов"
.
ПРИЛОЖЕНИЕ А
Задание на КП
1.Ознакомиться со свойствами и особенности обработки списочных структур.
2.Изучить функции API для работы с пулом памяти в ОС Windows
.Разработать и реализовать программу в соответствии с условием задачи.
.Разработать ряд тестов для демонстрации правильности работы программы.
.Подготовить отчет по курсовому проекту.
Демонстрационная программа должна содержать:
-главный, инициализирующий структуру списка и освобождающий после его использования память;
-поток, добавляющий элементы в список;
поток, удаляющий элементы из списка;
поток, изменяющий существующие элементы;
поток, читающий информацию списка (выводящий список на экран).
ПРИЛОЖЕНИЕ Б
Листинг программы
//---------------------------------------------------------------------------
//HEADER.H
//---------------------------------------------------------------------------struct node //узел списка, состоящий из целого числа и указателя на следующий элемент
{number;node *next;
}Node, *pnode;struct list //структура односвязного кольцевого списка
{nodes; //кол-во узлов в списке*end; //указатель на последний элемент в списке*beg; //указатель на первый элемент в списке
}List, *pList;struct params //структура для передачи параметров потоку
{*pq; //указатель на списокhp; //указатель на кучу
}Params;InitialList(List *pq, HANDLE hp); //инициализация спискаAddElem(List *pq, HANDLE hp, int n); //добавление узла с number =
n в конец спискаEraseElem(List *pq, HANDLE hp, int n); //удаление узла с number =
nChangeElem(List *pq, HANDLE hp, int o, int n); //изменение узла с
number=o на узел с number=nPrint(const List *pq, HANDLE hp); //вывод всех узлов списка на
экранThreadAdd(void *p); //поток добавления узловThreadErase(void *p); //поток удаления узловThreadChange(void *p); //поток изменения узлов
void ThreadPrint(void *p); //поток вывода всех узлов списка на экран
//---------------------------------------------------------------------------
//LFUN.CPP - содержит тела функций работы со списком
//---------------------------------------------------------------------------
#include
#include
#include
#include
#include
#include
#include
#include
#include "header.h"namespace std;
InitialList(List *pq, HANDLE hp) //инициализация списка
{= HeapCreate(0, 0x1000, 0x10000); //создание кучи для списка>beg = NULL; //инициализация указателей начала и конца списка>end = NULL;>nodes = 0; //инициализация счетчика узловhp;
}
bool AddElem(List *pq, HANDLE hp, int n) //добавление узла с number =
n в конец списка
{fl = HeapLock(hp); //блокировка доступа к куче списка других
потоков(fl == 0) //если блокировать не удалось
{<< "adding failed" << endl;false;
}*p_new;_new = (pnode)HeapAlloc(hp, HEAP_ZERO_MEMORY, 10);
//выделение памяти в куче под новый узел(p_new == NULL) //если выделить не удалосьfalse;_new->number = n; //инициализация элементов узла_new->next = pq->beg; //так как добавление производится в конец, то
указатель на след. узел
// равен указателю на начало(pq->nodes == 0) //если список еще пуст
{>beg = pq->end = p_new;_new->next = pq->beg;
}//в противном случае
{>end->next = p_new;>end = p_new;
}>nodes++; //инкремент счетчика узлов<< n << " added" << endl;(hp); //отмена блокировки кучи для других потоков
return true;
}
EraseElem(List *pq, HANDLE hp, int n) //удаление узла с number = n
{fl = HeapLock(hp); //блокировка доступа к куче списка других
потоков(fl == 0) //если блокировать не удалось
{<< "erase failed" << endl;false;
}*curr;*lcurr;(pq->nodes == 0) //если список пуст
{<< "list is empty, erase failed" << endl;
HeapUnlock(hp); //отмена блокировки кучи для других потоковfalse;
}= pq->beg; //в противном случае= pq->end;(curr->number == n) //если первый элемент - искомый
{(pq->nodes == 1) //при этом единственный
{>beg = NULL; //регенерация указателей и счетчика объектов в
списке
pq->end = NULL;>nodes = 0;
HeapFree(hp,0,curr); //освобождение блока памяти<< n << " erased" << endl;(hp); //отмена блокировки кучи для других потоковtrue;
}>next = curr->next; //при этом не единственный>beg = curr->next;(hp,0,curr); //освобождение блока памяти>nodes--; //декремент счетчика объектов<< n << " erased" << endl;(hp); //отмена блокировки кучи для других потоковtrue;
}(pq->nodes == 1) //если элемент единственный в списке и искомым не
является
{<< "there is no such node in list, erase failed" << endl;
HeapUnlock(hp); //отмена блокировки кучи для других потоков
return false;
}= curr;= curr->next;(curr != pq->beg) //поиск элемента
{(curr->number != n) //если текущий не является искомым - двигаемся
дальше
{= curr;= curr->next;
}//если текуший равен искомому
{
if(curr == pq->end)>beg = lcurr;>next = curr->next;(hp,0,curr); //освобождение блока памяти>nodes--; //декремент счетчика объектов<< n << " erased" << endl;
HeapUnlock(hp); //отмена блокировки кучи для других потоков
return true;
}
}<< "there is no such node in list, erase failed" << endl;
HeapUnlock(hp); //отмена блокировки кучи для других потоков
return false;
}
ChangeElem(List *pq, HANDLE hp, int o, int n) //изменение узла с
number=o на узел с number=n
{fl = HeapLock(hp); //блокировка доступа к куче списка других
потоков(fl == 0) //если блокировать не удалось
{<< "change failed" << endl;false;
}*curr;(pq->nodes == 0) //если список пуст
{<< "list is empty, change failed" << endl;
HeapUn