Параллельная обработка односвязных кольцевых списков в памяти ОС Windows

Министерство образования и науки Украины Харьковский национальный университет им. В. Н. Каразина Факультет компьютерных наук Кафедра искусственного интеллекта и программного обеспечения Курсовой проект по дисциплине Системное программирование и операционные системы Тема:

Параллельная обработка односвязных кольцевых списков в памяти ОС Windows

Исполнитель: студентка гр. КС-31

Е.В. Кунина Руководитель: ст. преподаватель О. М. Горбань Харьков 2012

СОДЕРЖАНИЕ Введение

1. Аналитический обзор

1.1 Постановка задачи

1.2 Общий обзор методов реализации задачи

2. Выполнение проекта

2.1 Функционал кольцевого списка

2.2 Описание функций API для работы с пулом памяти в ОС Windows и их роль в проекте

2.3 Средства создания потоков

2.4 Порядок работы программы

2.5 Набор тестов для отладки программы и скриншоты результатов8

Выводы Использованные источники информации Приложение А. Задание на выполнение КП Приложение Б. Листинг программы

ВВЕДЕНИЕ

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

Цели:

— ознакомиться с такими понятиями, как куча (пул памяти), связный список, синхронизация потоков;

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

Задачи:

— найти необходимую справочную информацию об особенностях организации связных списков и использования функций API для работы с пулом памяти в ОС Windows;

— реализовать программно структуру списка и его функциональность;

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

— обеспечить исключение возможности перекрытия разных потоков друг другом;

— разработать ряд тестов для проверки корректности работы программы.

Связный список — структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки на следующий и/или предыдущий узел списка. Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd edition. The MIT Press, 2001 Кольцевой односвязный список содержит, кроме данных, ссылку на следующий элемент, при этом указатель последнего элементы ссылается на первый (образуя, таким образом подобие кольца). Принципиальным преимуществом перед массивом является структурная гибкость: порядок элементов связного списка может не совпадать с порядком расположения элементов данных в памяти компьютера, а порядок обхода списка всегда явно задаётся его внутренними связями. http://ru.wikipedia.org/wiki/Связный_список, А вот удалять элементы из списка куда труднее, чем из массива, так как удаление напрямую будет связано с поиском, нельзя удалить элемент напрямую по индексу. Это можно отнести к недостаткам такой организации данных.

Пул памяти (куча) — распределяемая процессом область виртуальной памяти, используемая им для захвата и освобождения блоков памяти, размер которых может быть меньше размера виртуальной страницы. Для работы с кучей используется ряд функций, описанных в разделе «Аналитический обзор». Методические указания к выполнению работы

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

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

1. АНАЛИТИЧЕСКИЙ ОБЗОР

1.1 Постановка задачи Результатом выполнения проектного задания должна была стать программа, разработанная для платформы ОС Windows, которая реализовывала бы параллельную обработку односвязного кольцевого списка. За параллельную обработку должны отвечать 5 потоков:

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

— поток, добавляющий элементы в список;

— поток, удаляющий элементы из списка;

— поток, изменяющий существующие элементы;

— поток, читающий информацию списка (выводящий список на экран).

1.2 Общий обзор методов реализации задачи Таким образом, первым этапом написания программы стала реализация структуры списка, а также функций, работающих с ним. См. пункт 2.1 Главная задача — синхронизация потоков, работающих со списком. См. пункт 2.2 Для этого я использовала выделение дополнительной кучи для списка. Это несет в себе ключевой смысл: каждый раз, когда какой либо поток получает доступ к списку (а значит и к куче), то он как критический раздел блокируется, а значит любой другой поток, также пытающийся получить доступ к списку будет приостановлен до момента его освобождения. Более того в программе мною были использованы методы обеспечения многопоточности. См. пункт 2.3

2. ВЫПОЛНЕНИЕ ПРОЕКТА

2.1 Функционал кольцевого списка К структуре списка применимы следующие методы:

— InitialList — инициализация списка;

— AddElem — добавление узла в конец списка;

— EraseElem — удаление элемента из списка; так как реализованный мною список имеет всего 2 поля: указатель на следующий элемент и целое число (непосредственно данные), то поиск элемента для его удаления производится по этому самому числу, при эьтом считается, что элементы в списке не повторяются (для формализации задачи);

— ChangeElem — изменение данных уже существующего узла; поиск элементы аналогичен поиску при удалении;

— Print — вывод на экран всех узлов списка. Код функций см. в Приложении Б

2.2 Описание функций API для работы с пулом памяти в ОС Windows и их роль в проекте В постановке задачи есть немаловажный пункт — обеспечение исключения возможности перекрытия разных потоков друг другом. Реализовывать его предлагается посредством создания под список отдельной кучи, а все операции со списком осуществлять при помощи функций API работы с пулом памяти. В своей программе я использовала следующие функции:

— HeapCreate. Создает дополнительную кучу в процессе. Принимает 3 параметра: параметр fdwOptions модифицирует способ выполнения операций над кучей. В нем можно указать 0, НЕАР_NO_SERIALIZE, НЕАР_GENERATE_EXCEPTIONS, HEAP_CREATE_ENABLE_EXECUTE или комбинацию этих флагов. Второй параметр функции HeapCreate — dwInitiallSize — определяет количество байтов, первоначально передаваемых куче. При необходимости функция округляет это значение до ближайшей большей величины, кратной размеру страниц. И последний параметр, dwMaximumSize, указывает максимальный объем, до которого может расширяться куча (предельный объем адресного пространства, резервируемого под кучу). Если он больше 0, вы создадите кучу именно такого размера и нс сможете его увеличить. А если этот параметр равен 0, система резервирует регион и, если надо, расширяет его до максимально возможного объема. При успешном создании кучи HeapCreate возвращает описатель, идентифицирующий новую кучу. В своей программе этой функцией я создавала кучу для объекта структуры кольцевого списка.

— HeapAlloc. Выделяет блок памяти из кучи. Я использовала эту функцию при создании нового элемента списка. Принимает 3 параметра: параметр hHeap идентифицирует описатель кучи, из которой выделяется память. Параметр dwBytes определяет число выделяемых в куче байтов. Параметр fdwFlags позволяет указывать флаги, влияющие на характер выделения памяти. В настоящее время поддерживается только три флага: HEAP_ZERO_MEMORY, HEAP_GENERATE_EXCEPTIONS и HEAP_NO_SERIALIZE.

Примечание. Для выделения больших блоков памяти (от 1 Мб) рекомендуется использовать функцию VirtualAlloc, а не функции, оперирующие с кучами.

— HeapFree. Служит для освобождения блока памяти. В реализованной программе используется при удалении элемента. Принимает 3 параметра: параметр hHeap идентифицирует кучу, а параметр pvMem сообщает адрес блока. Параметр fdwFlags принимает два значения: 0 или HEAP_NO_SERIALIZE.

— HeapDestroy. Уничтожает кучу вместе со всеми данными, которые в ней хранятся. Поэтому при ее использовании необходимо удостовериться, что ни один из процессов больше не будет использовать эти данные. В противном случае будет выброшено исключение или программа закончится некорректно. Принимает всего 1 параметр hHeap, который идентифицирует кучу.

— Следующие две функции — HeapLock и HeapUnlock — используются парно. Они предназначены для синхронизации потоков. После успешного вызова HeapLock поток, который вызывал эту функцию, становится владельцем указанной кучи. Если другой поток обращается к этой куче, указывая тот же описатель кучи, система приостанавливает его выполнение до тех пор, пока куча не будет разблокирована вызовом HeapUnlock. Функции HeapAlloc, HeapSize, HeapFree и другие — все обращаются к HeapLock и HeapUnlock, чтобы обеспечить последовательный доступ к куче. Поэтому явно в коде они могут быть не прописаны. Информация для пункта 2.2 взята из книги Джеффри Рихтера «Windows для профессионалов»

2.3 Средства создания потоков Создание потока осуществляется с помощью следующей функции:

uintptr_t _beginthread (

void (*start_address)(void *),

unsigned stack_size,

void *arglist

);

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

void myThread (void* pParams)

{

.. .

}

Имя конечно же может быть любое. Второй аргумент это начальный размер стека. Почти в любом случае его можно указать как 0. Тогда размер стека будет равен тому же, что и у главной задачи процесса. С третьим все ещё легче, это аргументы функции потока, которые вполне могут быть как NULL. Или же выглядеть как (void*)(pParam) в случае с первой функцией. Для корректной работы вышеописанных функций требуется подключение библиотеки. Информация для пункта 2.3 взята с сайта http://forum.xakep.ru/

2.4 Порядок работы программы Основной поток программы создает список и инициализирует его. После чего запускаются 4 потока. См. Приложение, А Первый пытается по очереди добавить в список элементы от 1 до 9, второй — удалить аналогичные узлы, третий — изменить аналогичные элементы путем прибавления к ним 1000, а четвертый — вывести на экран содержимое списка (10 попыток). Все потоки используют соответствующие функции работы со списком. Подробнее о функционале списка см. в пункте 2.1 В силу особенностей работы многопоточных приложений, при каждом его запуске результаты работы разные, так как потоки выполняются совершенно произвольно, поэтому и последовательность действий непредсказуема.

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

Итак вот скриншоты результатов 3 запусков программы, которые говорят о корректности ее работы:

Рисунок 1. Результат работы программы

Как видно из Рисунка 1, первым делом поток 1 добавил в список узел со значением 1. После чего поток 3 изменил его на узел 1001. Остальные попытки изменить узлы списка не увенчались успехом, так как элементы 2−9 в список добавлены не были. На следующем этапе программы критическую секцию захватил поток 4 и 10 раз вывел содержимое списка на экран. Последующие 10 попыток потока 2 удалить элементы успешными не были, так как таких узлов в списке нет (узел 1 был изменен на 1001, остальные еще не были добавлены). Далее управление снова передалось потоку 1 и он добавил остальные элементы в список. Контрольный вывод списка на экран соответствует ожиданиям. После завершения всех потоков главный поток удалил кучу.

Рисунок 2. Результат работы программы

На Рисунке 2 видно, что в начале выполнения поток 1 получил доступ к куче со списком и успешно добавил в него 10 элементов. Далее поток 4 2 раза распечатал список. После этого все элементы были удалены потоком 2, из-за чего 10 попыток потока 3 изменить элементы и 8 попыток потока 4 вывести их на экран не удались, так список был пуст. После завершения всех потоков главный поток удалил кучу.

Работа программы при 3-ем запуске полностью совпала с 1-ым случаем, что отражено на Рисунке 3.

Рисунок 3. Результат работы программы

пул поток связной список

ВЫВОДЫ Чтобы подытожить выполнение данного курсового проекта хотелось бы сделать ряд выводов. Во-первых, все цели данной работы были достигнуты путем пошагового выполнения поставленных в соответствии с ними задач. См.

Введение

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

ИСПОЛЬЗОВАННЫЕ ИСТОЧНИКИ ИНФОРМАЦИИ

1. Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 2nd edition. The MIT Press, 2001

2. http://ru.wikipedia.org/wiki/Связный_список

3. Методические указания к выполнению работы

4. Джеффри Рихтер «Windows для профессионалов»

5. http://forum.xakep.ru/

ПРИЛОЖЕНИЕ, А Задание на КП

1. Ознакомиться со свойствами и особенности обработки списочных структур.

2. Изучить функции API для работы с пулом памяти в ОС Windows

3. Разработать и реализовать программу в соответствии с условием задачи.

4. Разработать ряд тестов для демонстрации правильности работы программы.

5. Подготовить отчет по курсовому проекту.

Демонстрационная программа должна содержать:

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

— поток, добавляющий элементы в список;

— поток, удаляющий элементы из списка;

— поток, изменяющий существующие элементы;

— поток, читающий информацию списка (выводящий список на экран).

ПРИЛОЖЕНИЕ Б Листинг программы

//—————————————————————————————————————;

//HEADER.H

//—————————————————————————————————————;

typedef struct node //узел списка, состоящий из целого числа и указателя на следующий элемент

{

int number;

struct node *next;

}Node, *pnode;

typedef struct list //структура односвязного кольцевого списка

{

int nodes; //кол-во узлов в списке

node *end; //указатель на последний элемент в списке

node *beg; //указатель на первый элемент в списке

}List, *pList;

typedef struct params //структура для передачи параметров потоку

{

List *pq; //указатель на список

HANDLE hp; //указатель на кучу

}Params;

HANDLE InitialList (List *pq, HANDLE hp); //инициализация списка

bool AddElem (List *pq, HANDLE hp, int n); //добавление узла с number =

n в конец списка

bool EraseElem (List *pq, HANDLE hp, int n); //удаление узла с number =

n

bool ChangeElem (List *pq, HANDLE hp, int o, int n); //изменение узла с

number=o на узел с number=n

bool Print (const List *pq, HANDLE hp); //вывод всех узлов списка на

экран

void ThreadAdd (void *p); //поток добавления узлов

void ThreadErase (void *p); //поток удаления узлов

void ThreadChange (void *p); //поток изменения узлов

void ThreadPrint (void *p); //поток вывода всех узлов списка на экран

//—————————————————————————————————————;

//LFUN.CPP — содержит тела функций работы со списком

//—————————————————————————————————————;

#include

#include

#include

#include

#include

#include

#include

#include

#include «header.h»

using namespace std;

HANDLE InitialList (List *pq, HANDLE hp) //инициализация списка

{

hp = HeapCreate (0, 0×1000, 0×10 000); //создание кучи для списка

pq->beg = NULL; //инициализация указателей начала и конца списка

pq->end = NULL;

pq->nodes = 0; //инициализация счетчика узлов

return hp;

}

bool AddElem (List *pq, HANDLE hp, int n) //добавление узла с number =

n в конец списка

{

int fl = HeapLock (hp); //блокировка доступа к куче списка других

потоков

if (fl == 0) //если блокировать не удалось

{

cout << «adding failed» << endl;

return false;

}

Node *p_new;

p_new = (pnode)HeapAlloc (hp, HEAP_ZERO_MEMORY, 10);

//выделение памяти в куче под новый узел

if (p_new == NULL) //если выделить не удалось

return false;

p_new->number = n; //инициализация элементов узла

p_new->next = pq->beg; //так как добавление производится в конец, то

указатель на след. узел

// равен указателю на начало

if (pq->nodes == 0) //если список еще пуст

{

pq->beg = pq->end = p_new;

p_new->next = pq->beg;

}

else //в противном случае

{

pq->end->next = p_new;

pq->end = p_new;

}

pq->nodes++; //инкремент счетчика узлов

cout << n << «added» << endl;

HeapUnlock (hp); //отмена блокировки кучи для других потоков

return true;

}

bool EraseElem (List *pq, HANDLE hp, int n) //удаление узла с number = n

{

int fl = HeapLock (hp); //блокировка доступа к куче списка других

потоков

if (fl == 0) //если блокировать не удалось

{

cout << «erase failed» << endl;

return false;

}

Node *curr;

Node *lcurr;

if (pq->nodes == 0) //если список пуст

{

cout << «list is empty, erase failed» << endl;

HeapUnlock (hp); //отмена блокировки кучи для других потоков

return false;

}

curr = pq->beg; //в противном случае

lcurr = pq->end;

if (curr->number == n) //если первый элемент — искомый

{

if (pq->nodes == 1) //при этом единственный

{

pq->beg = NULL; //регенерация указателей и счетчика объектов в

списке

pq->end = NULL;

pq->nodes = 0;

HeapFree (hp, 0, curr); //освобождение блока памяти

cout << n << «erased» << endl;

HeapUnlock (hp); //отмена блокировки кучи для других потоков

return true;

}

lcurr->next = curr->next; //при этом не единственный

pq->beg = curr->next;

HeapFree (hp, 0, curr); //освобождение блока памяти

pq->nodes—; //декремент счетчика объектов

cout << n << «erased» << endl;

HeapUnlock (hp); //отмена блокировки кучи для других потоков

return true;

}

if (pq->nodes == 1) //если элемент единственный в списке и искомым не

является

{

cout << «there is no such node in list, erase failed» << endl;

HeapUnlock (hp); //отмена блокировки кучи для других потоков

return false;

}

lcurr = curr;

curr = curr->next;

while (curr ≠ pq->beg) //поиск элемента

{

if (curr->number ≠ n) //если текущий не является искомым — двигаемся

дальше

{

lcurr = curr;

curr = curr->next;

}

else //если текуший равен искомому

{

if (curr == pq->end)

pq->beg = lcurr;

lcurr->next = curr->next;

HeapFree (hp, 0, curr); //освобождение блока памяти

pq->nodes—; //декремент счетчика объектов

cout << n << «erased» << endl;

HeapUnlock (hp); //отмена блокировки кучи для других потоков

return true;

}

}

cout << «there is no such node in list, erase failed» << endl;

HeapUnlock (hp); //отмена блокировки кучи для других потоков

return false;

}

bool ChangeElem (List *pq, HANDLE hp, int o, int n) //изменение узла с

number=o на узел с number=n

{

int fl = HeapLock (hp); //блокировка доступа к куче списка других

потоков

if (fl == 0) //если блокировать не удалось

{

cout << «change failed» << endl;

return false;

}

Node *curr;

if (pq->nodes == 0) //если список пуст

{

cout << «list is empty, change failed» << endl;

HeapUnlock (hp); //отмена блокировки кучи для других потоков

return false;

}

curr = pq->beg;

int it_count = pq->nodes;

while (it_count > 0) //поиск элемента

{

if (curr->number ≠ o) //если не нашли — движение дальше по списку

{

curr = curr->next;

}

else //если нашли

{

curr->number = n; //изменение значения элемента

cout << o << «changed to «<< n << endl;

HeapUnlock (hp); //отмена блокировки кучи для других потоков

return true;

}

it_count—;

}

cout << «there is no such node in list, change failed» << endl;

HeapUnlock (hp); //отмена блокировки кучи для других потоков

return false;

}

bool Print (const List *pq, HANDLE hp)

{

int fl = HeapLock (hp); //блокировка доступа к куче списка других

потоков

if (fl == 0) //если блокировать не удалось

{

cout << «print failed» << endl;

return false;

}

Node *curr;

if (pq->nodes == 0) //если список пуст

{

cout << «list is empty, there is nothing to print» << endl;

HeapUnlock (hp); //отмена блокировки кучи для других потоков

return false;

}

curr = pq->beg;

cout << curr->number;

curr = curr->next;

while (curr ≠ pq->beg) //вывод всех элементов списка на экран

{

cout << ' ' << curr->number;

curr = curr->next;

}

cout << endl;

HeapUnlock (hp); //отмена блокировки кучи для других потоков

return true;

}

//—————————————————————————————————————;

//MAIN.CPP — тела главного и второстепенных потоков

//—————————————————————————————————————;

#include //подключение библиотек

#include

#include

#include

#include

#include

#include «header.h»

#include

#include

#include

#include

#include

#include

#include

#include

using namespace std;

int c = 0; //счетчик завершившихся потоков

void ThreadAdd (void *p) //поток добавления узлов

{

int counter = 1;

Params *pp = new Params ();

pp = (Params*) p;

while (counter < 10) //добавление в указанный в параметрах список

элементов от 0 до 9

{

AddElem (pp->pq, pp->hp, counter);

counter++;

}

c++; //инкремент счетчика завершившихся процессов

_endthread ();

}

void ThreadErase (void *p) //поток удаления элементов

{

int counter = 1;

Params *pp = new Params ();

pp = (Params*) p;

while (counter < 10) //удаление узла из указанного в параметрах списка

со значениями от 0 до 9

{

EraseElem (pp->pq, pp->hp, counter);

counter++;

}

c++; //инкремент счетчика завершившихся процессов

_endthread ();

}

void ThreadChange (void *p) //поток изменения элементов

{

int counter = 1;

Params *pp = new Params ();

pp = (Params*) p;

while (counter < 10) //изменение узла указанного в параметрах списка со

значениями от 0 до 9 путем прибавления к ним 1000

{

ChangeElem (pp->pq, pp->hp, counter, counter+1000);

counter++;

}

c++; //инкремент счетчика завершившихся процессов

_endthread ();

}

void ThreadPrint (void *p) //поток вывода списка на экран

{

int counter = 0;

Params *pp = new Params ();

pp = (Params*) p;

while (counter < 10) //10 попыток вывести узлы списка на экран

{

Print (pp->pq, pp->hp);

counter++;

}

c++; //инкремент счетчика завершившихся процессов

_endthread ();

}

int main ()

{

HANDLE hp = NULL;

List q;

hp = InitialList (&q, hp); //инициализация списка

Params *p = new Params ();

p->pq = &q;

p->hp = hp;

_beginthread (ThreadAdd, 2, (void*)(p)); //добавление второстепенных

потоков

_beginthread (ThreadErase, 2, (void*)(p));

_beginthread (ThreadChange, 2, (void*)(p));

_beginthread (ThreadPrint, 2, (void*)(p));

while (1) //ожидание завершения второстепенных потоков

{

if (c == 4)

{

Print (&q, hp); //контрольное распечатывание списка

HeapDestroy (hp); //удаление кучи

cout << «heap destroyed» << endl;

break;

}

}

}