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

 

Министерство образования и науки Украины

Харьковский национальный университет им. В.Н. Каразина

Факультет компьютерных наук

Кафедра искусственного интеллекта и программного обеспечения

Курсовой проект по дисциплине

Системное программирование и операционные системы

Тема:

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

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

Е.В. Кунина

Руководитель: ст. преподаватель

О.М. Горбань

Харьков 2012

СОДЕРЖАНИЕ

Введение

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

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

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

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

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

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

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

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

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

Выводы

Использованные источники информации

Приложение А. Задание на выполнение КП

Приложение Б. Листинг программы

ВВЕДЕНИЕ

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

Цели:

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

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

Задачи:

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

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

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

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

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

Связный список - структура данных <#"justify">-главный, инициализирующий структуру списка и освобождающий после его использования память;

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

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

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

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

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

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

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

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

К структуре списка применимы следующие методы:

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

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

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

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

Print - вывод на экран всех узлов списка.

.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, чтобы обеспечить последовательный доступ к куче. Поэтому явно в коде они могут быть не прописаны.

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

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

uintptr_t _beginthread(( *start_address )( void * ),stack_size,*arglist

);

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

myThread(void* pParams)

{

. . .

}

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

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

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

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. #"justify">ПРИЛОЖЕНИЕ А

Задание на КП

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 <stdafx.h>

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <windows.h>

#include <iostream>

#include <string.h>

#include <string>

#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;

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

return false;

}= pq->beg;it_count = pq->nodes;(it_count > 0) //поиск элемента

{

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

{= curr->next;

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

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

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

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

return true;

}_count--;

}<< "there is no such node in list, change failed" << endl;

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

return false;

}

Print(const List *pq, HANDLE hp)

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

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

{<< "print failed" << endl;false;

}*curr;(pq->nodes == 0) //если список пуст

{<< "list is empty, there is nothing to print" << endl;

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

return false;

}= pq->beg;<< curr->number;= curr->next;

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

{<< ' ' << curr->number;= curr->next;

}<< endl;

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

}

//---------------------------------------------------------------------------

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

//---------------------------------------------------------------------------

#include <stdafx.h> //подключение библиотек

#include <stdio.h>

#include <malloc.h>

#include <stdlib.h>

#include <windows.h>

#include <iostream>

#include "header.h"

#include <tchar.h>

#include <string>

#include <stdlib.h>

#include <string.h>

#include <assert.h>

#include <process.h>

#include <time.h>

#include <Windows.h>namespace std;

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

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

{counter = 1;*pp = new Params();

pp = (Params*) p;(counter < 10) //добавление в указанный в параметрах список

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

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

counter++;

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

_endthread();

}

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

{counter = 1;*pp = new Params();

pp = (Params*) p;(counter < 10) //удаление узла из указанного в параметрах списка

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

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

counter++;

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

_endthread();

}

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

{counter = 1;*pp = new Params();

pp = (Params*) p;(counter < 10) //изменение узла указанного в параметрах списка со

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

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

counter++;

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

_endthread();

}

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

{counter = 0;*pp = new Params();

pp = (Params*) p;(counter < 10) //10 попыток вывести узлы списка на экран

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

counter++;

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

_endthread();

}

main()

{hp = NULL;q;= InitialList(&q,hp); //инициализация списка*p = new Params();>pq = &q;>hp = hp;

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

потоков

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

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

_beginthread(ThreadPrint, 2, (void*)(p));(1) //ожидание завершения второстепенных потоков

{(c == 4)

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

HeapDestroy(hp); //удаление кучи<< "heap destroyed" << endl;

break;

}

}

}

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

Больше работ по теме: