Параллельная обработка односвязных кольцевых списков в памяти ОС Windows
Министерство
образования и науки Украины
Харьковский
национальный университет им. В.Н. Каразина
Факультет
компьютерных наук
Кафедра
искусственного интеллекта и программного обеспечения
Курсовой
проект по дисциплине
Системное
программирование и операционные системы
Тема:
Параллельная
обработка односвязных кольцевых списков в памяти ОС Windows
Исполнитель:
студентка гр. КС-31
Е.В. Кунина
Руководитель:
ст. преподаватель
О.М. Горбань
Харьков 2012
СОДЕРЖАНИЕ
Введение
.
Аналитический обзор
.1
Постановка задачи
.2
Общий обзор методов реализации задачи
.
Выполнение проекта
.1
Функционал кольцевого списка
.2
Описание функций API для работы с пулом памяти в ОС Windows и их роль в проекте
.3
Средства создания потоков
.4
Порядок работы программы
2.5
Набор тестов для отладки программы и скриншоты результатов8
Выводы
Использованные
источники информации
Приложение
А. Задание на выполнение КП
Приложение
Б. Листинг программы
ВВЕДЕНИЕ
На основании полученного задания, приведенного в
Приложении А, можно сформулировать ряд целей и задач выполнения данного
курсового проекта, которые описаны ниже.
Цели:
- ознакомиться с такими понятиями, как куча (пул
памяти), связный список, синхронизация потоков;
- приобрести навыки написания
многопоточных программ, обеспечивающих исключение возможности перекрытия разных
потоков друг другом.
Задачи:
- найти необходимую справочную информацию об
особенностях организации связных списков и использования функций API для работы
с пулом памяти в ОС Windows;
- реализовать программно структуру списка
и его функциональность;
дополнить программу 5-ью потоками:
первый инициализирует список и удаляет кучу после ее использования, второй и
третий добавляет элементы в список и удаляет их соответственно, четвертый
изменяет существующие элементы, пятый выводит содержимое списка на экран;
обеспечить исключение возможности
перекрытия разных потоков друг другом;
разработать ряд тестов для проверки
корректности работы программы.
Связный список - структура данных
<#"551372.files/image001.gif">
Рисунок 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/Связный_список
<http://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9_%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA>
.
Методические указания к выполнению работы
.
Джеффри Рихтер "Windows для профессионалов"
.
http://forum.xakep.ru/
ПРИЛОЖЕНИЕ А
Задание на КП
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;
}
}
}