ТУСУР – Лабораторная работа – Параллельное программирование

ОГЛАВЛЕНИЕ
Может быть интересно
ВВЕДЕНИЕ…………………………………………………………………………………….. 5
1.Задание ………………………………………………………………………………………. 15
Результаты работы………………………………………………..…………9
Заключение…………………………………………………………………….17
СПИСОК ЛИТЕРАТУРЫ……………………………………………………………… ..20
ВВЕДЕНИЕ
Для разделения различных выполняемых приложений в операцион- ных системах используются процессы. Потоки являются основными эле- ментами, для которых операционная система выделяет время процессора; внутри процесса может выполняться более одного потока. Каждый поток поддерживает обработчик исключений, планируемый приоритет и набор структур, используемых системой для сохранения контекста потока во время его планирования. Контекст потока содержит все необходимые данные для возобновления выполнения (включая набор регистров процес- сора и стек) в адресном пространстве ведущего процесса.
По умолчанию все разрабатываемые приложения являются однопо- точными. Многопоточность позволяет приложениям разделять задачи и ра- ботать над каждой независимо, чтобы максимально эффективно задейство- вать процессор и пользовательское время. Однако чрезмерное злоупотребле- ние многопоточностью может снизить эффективность программы. Разделять процесс на потоки следует только в том случае, если это оправданно.
ЗАДАНИЕ
Тема задания: «Реализация многопоточной обработки данных».
Цель: освоить реализацию многопоточной обработки данных, а также пула потоков и механизма асинхронного ввода/вывода.
В работе необходимо реализовать многопоточную обработку массива структур данных (из N элементов) четырьмя способами:
- При помощи массива из M потоков (M ≤ N), используя для синхро- низации объект ядра – семафор.
- При помощи массива из M потоков (M ≤ N), используя для синхро- низации сеть Петри, моделирующую семафор.
- При помощи пула из M потоков (M ≤ N), используя системный пул потоков или асинхронные потоки ввода/вывода.
- При помощи пула из M потоков (M ≤ N), моделируя его при помощи сети Петри.
При обработке массива данных массивом потоков каждый поток либо заранее выбирает диапазон элементов массива данных, которые он будет обрабатывать, либо просто берет первый необработанный элемент. Завер- шив обработку одного элемента, поток переходит к обработке следующего. При обработке массива данных пулом потоков, завершив обработку одного элемента массива данных, освободившийся в пуле, поток переходит
к обработке следующего необработанного элемента.
Чтобы не требовалось создавать слишком большие массивы (для ко- торых эффект от параллельной обработки будет наиболее очевидным), можно имитировать ситуацию, когда обработка одного элемента массива требует больше процессорного времени, чем в действительности. Для этого после обработки очередного элемента массива поток может делать паузу на указанное количество миллисекунд.
Входной файл должен иметь имя «input.txt», «input.xml», «input.json» и т. п. Если оба задания контрольной или лабораторной работы реализуются в одной и той же программе, имена входных файлов для разных заданий должны отличаться (, для задания № 2 входной файл может иметь имя «input2.txt», «input2.xml input2.json и т. п.). Формат входного файла представлен в таблице 2.3.
Таблица 2.3 – Формат входного файла для задания № 2
Поле | Значение |
PA | Выбранный способ обработки массива |
N | Размер массива структур данных |
M | Количество параллельных потоков (если 0, то принимается
равным числу процессорных ядер в системе) |
PT | Пауза после обработки каждого элемента массива, мс |
… | Дополнительные входные данные (если требуются согласно
индивидуальному варианту задания) |
… | Значения атрибутов каждой структуры данных. Если какие-то атрибуты не заданы (или заданы пустой строкой), то генери-
руются программой случайным образом |
Выходной файл должен иметь имя «output.txt». Формат выходного файла представлен в таблице 2.4.
Таблица 2.4 – Формат выходного файла для задания № 2
Поле | Значение |
T1 | Время, требующееся на линейную обработку массива данных
(без распараллеливания вычислений) |
TP | Время, требующееся на параллельную обработку массива дан-
ных выбранным способом |
… | Результаты обработки (зависят от варианта) |
Для ввода и вывода данных допускается использование в программе визуального интерфейса вместо файлового ввода/вывода.
Вариант 14. Структура содержит сведения о странице телефонной записной книжки: буква, с которой начинаются фамилии на данной странице, а также список фамилий и номеров телефонов. Программа должна по маске номера телефона T определить подходящие фамилии абонентов и вывести сведения о них в выходной файл. В маске вместо неизвестной цифры используется знак вопроса.
- Результаты работы
Структура содержит сведения о странице телефонной записной книжки – это буква, с которой начинаются фамилии на данной странице, а также список фамилий и номеров телефонов. Программа должна по маске номера телефона T определить подходящие фамилии абонентов и вывести сведения о них в выходной файл. В маске вместо неизвестной цифры используется знак вопроса.
Описать структуру с именем ТЕЛЕФОННАЯ КНИЖКА, содержащую следующие поля:
- фамилия, имя;
- номер телефона;
- дата рождения (массив из трех чисел).
Написать программу, выполняющую следующие действия:
- ввод с клавиатуры данных в массив, состоящий из восьми элементов типа ТЕЛЕФОННАЯ КНИЖКА, записи должны быть упорядочены по трем первым цифрам номера телефона;
- вывод на экран информации о человеке, чья фамилия введена с клавиатуры;
- если такого нет, выдать на дисплей соответствующее сообщение.
Код программы:
//—————————————————————————
#include<iostream.h>
#include<conio.h>
#include<windows.h>
#include<math.h>
#include<vcl.h>
#pragma hdrstop
#pragma argsused
//—————————————————————————
char *rus(const char *text);//функция для распознавания русских символов
int main(int argc, char* argv[])
{
const int m=3,k=30;//объявление именованных констант
struct Телефонная книжка //объявление структуры
{
char fio[k]; //объявление
int telnumb; //полей
int bdate[m]; //структуры
int tel3numb;
};
int i,j,n; //объявление
bool not_found,sort=1;
char surname[k]; //переменных
cout<<rus(” Введите количество структур ТЕЛЕФОННАЯ КНИЖКА: “);cin>>n;//ввод кол-ва структур
cout<<endl;
Телефонная книжка *ТЕЛЕФОННАЯ КНИЖКА=new Телефонная книжка[n];//выделение в динамической памяти место под массив структур
for(i=0;i<n;i++)
{
cout<<‘ ‘<<(i+1)<<rus(“.Введите фамилию и имя: “);
cin.ignore();cin.getline(ТЕЛЕФОННАЯ КНИЖКА[i].fio,k); //ввод
cout<<rus(” Введите номер телефона: “);cin>>ТЕЛЕФОННАЯ КНИЖКА[i].telnumb; //данных
int tel=ТЕЛЕФОННАЯ КНИЖКА[i].telnumb;
int len=(int)log10((double)tel)+1;
char *strtel=new char[len+1];
char *tel3=new char[len+1];
for(int l=len-1;l>=0;–l)
{
int chartel=tel%10;
strtel[l]=’0’+chartel;
tel/=10;
}
strtel[len]=’\0′;
int cnt=0;
for(int m=0;m<3;m++)
{
tel3[m]=strtel[m];
cnt++;
if (cnt==3)break;
}
tel3[m]=’\0’;
ТЕЛЕФОННАЯ КНИЖКА[i].tel3numb=atoi(tel3);
for(j=0;j<m;j++) //в структуру
{
cout<<rus(” Введите день рождения: “);cin>>ТЕЛЕФОННАЯ КНИЖКА[i].bdate[j++];
cout<<rus(” Введите месяц рождения: “);cin>>ТЕЛЕФОННАЯ КНИЖКА[i].bdate[j++];
cout<<rus(” Введите год рождения: “);cin>>ТЕЛЕФОННАЯ КНИЖКА[i].bdate[j];
}
cout<<endl;
}
while(sort)
{ //сортировка
sort=0; //структуры
for(i=0;i<n-1;i++) //по первым трем
if(ТЕЛЕФОННАЯ КНИЖКА[i].tel3numb>ТЕЛЕФОННАЯ КНИЖКА[i+1].tel3numb) //цифрам телефона
{
temp=ТЕЛЕФОННАЯ КНИЖКА[i];
ТЕЛЕФОННАЯ КНИЖКА[i]=ТЕЛЕФОННАЯ КНИЖКА[i+1];
ТЕЛЕФОННАЯ КНИЖКА[i+1]=temp;
sort=1;
}
}
cout<<rus(” Записи упорядоченные по первым трем цифрам номера телефона:\n\n”);
for(i=0;i<n;i++)
{ //вывод отсортированной структуры
cout<<rus(” Фамилия и имя: “)<<ТЕЛЕФОННАЯ КНИЖКА[i].fio<<endl;
cout<<rus(” Номер телефона: “)<<ТЕЛЕФОННАЯ КНИЖКА[i].telnumb<<endl;
cout<<rus(” Первые 3 цифры номера телефона: “)<<ТЕЛЕФОННАЯ КНИЖКА[i].tel3numb<<endl;
cout<<rus(” Дата рождения:”);
for(j=0;j<m;j++)
{
cout<<ТЕЛЕФОННАЯ КНИЖКА[i].bdate[j]<<‘.’;
}
cout<<endl<<endl;
}
cout<<rus(” Информации о человеке. чья фамилия введена с клавиатуры:”)<<endl;
while(true)
{
cout<<rus(” Введите фамилию человека или “”\”end\” для окончания: “);cin>>surname;
cout<<endl;
if(strcmp(surname,”end”)==0)break;
not_found=true;
for(i=0;i<n;i++)
{
if(strstr(ТЕЛЕФОННАЯ КНИЖКА[i].fio,surname))
if(ТЕЛЕФОННАЯ КНИЖКА[i].fio[strlen(surname)]==’ ‘||ТЕЛЕФОННАЯ КНИЖКА[i].fio[strlen(surname)]==’\0’)
{
cout<<rus(” Фамилия и имя: “)<<ТЕЛЕФОННАЯ КНИЖКА[i].fio<<endl;
cout<<rus(” Номер телефона: “)<<ТЕЛЕФОННАЯ КНИЖКА[i].telnumb<<endl;
cout<<rus(” Дата рождения: “); //вывод
for(j=0;j<m;j++) //запрошенной
{ //информации
cout<<ТЕЛЕФОННАЯ КНИЖКА[i].bdate[j]<<‘.’;
}
not_found=false;
cout<<endl<<endl;
}
} //если нет такой информации выводится сообщение
if(not_found)cout<<rus(” Таких людей нет!”)<<endl<<endl;
}
getch();
return 0;
}
//—————————————————————————
char bufrus[256];
char *rus(const char *text)
{
CharToOem(text,bufrus);
return bufrus;
}
//—————————————————————————
Для уменьшения количества выводимой на экран информации, заполним только 2 структуры ТЕЛЕФОННАЯ КНИЖКА.
Заключение
В данном проекте рассмотрены теория схем программ, семантическая теория программ и теория параллельных вычислений. Построение схем программ позволяет изучить структурные свойства программы, а также проводить эквивалентные преобразования программ. Методы формального описания семантики программ, семантические методы преобразования и доказательства утверждений о программах позволяют оценить математический смысл программы и, в перспективе, автоматизировать отладку и даже синтез программ. Параллельное программирование используется уже довольно давно, тем не менее, именно сейчас оно переживает настоящий всплеск. Активно строятся новые суперкомпьютерные системы, и даже самые маленькие компьютерные устройства (ноутбуки, смартфоны и т. д.) имеют возможность проведения параллельных вычислений. В связи с этим исследование методов распараллеливания алгоритмов и программ актуально как никогда.
Литература
- Ершов, А. П. Введение в теоретическое программирование / А. П. Ершов. – М. : Наука, 1977. – 228 с. 2. Котов, В. Е. Теория схем программ / В. Е. Котов, В. К. Сабельфельд. – М. : Наука, 1991. – 248 с. 3. Котов, В. Е. Введение в теорию схем программ / В. Е. Котов. – Новосибирск : Наука, 1978. – 257 с. 4. Минский, М. Вычисления и автоматы / М. Минский. – М. : Мир, 1971. – 366 с. 5. Непомнящий, В. А. Прикладные методы верификации программ / В. А. Непомнящий, О. М. Рякин ; под ред. А. П. Ершова. – М. : Радио и связь, 1988. – 356 с. 6. Андерсон, Р. Доказательство правильности программ : пер. с англ. / Р. Андерсон. – М. : Мир, 1982. – 186 с. 7. Хоар, Ч. Взаимодействующие последовательные процессы / Ч. Хоар. – М. : Мир, 1988. – 264 с. 8. Питерсон, Дж. Теория сетей Петри и моделирование систем / Дж. Питерсон. – М. : Наука, 1984. – 264 с. 9. Котов, В. Е. Сети Петри / В. Е. Котов. – М. : Наука, 1984. – 161 с. 10. Грис, Д. Конструирование компиляторов для цифровых вычислительных систем / Д. Грис. – М. : Мир, 1975. – 554 с. 11. Донован, Дж. Системное программирование / Дж. Донован. – М. : Мир, 1975. – 540 с. 12. Кнут, Д. Искусство программирования для ЭВМ / Д. Кнут. – М. : Мир, 1976–1978. – Т. 1–3. 13. Рейуорд-Смит, В. Дж. Теория формальных языков / В. Дж. РейуордСмит. – М. : Мир, 1988. – 128 с. 14. Бек, Л. Введение в системное программирование / Л. Бек. – М. : Мир, 1988. – 448 с. 15. Вишняков, В. А. Организация вычислительных процессов / В. А. Вишняков. – Минск : Вышэйшая школа, 1988. – 207 с. 16. Шпаковский, Г. И. Организация параллельных ЭВМ и суперскалярных процессоров / Г. И. Шпаковский. – Минск : Белгосуниверситет, 1996. – 296 с. 160 17. Ахо, А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. – М. : Мир, 1979. – 536 с. 18. Дейтл, Г. Введение в операционные системы / Г. Дейтл. – М. : Мир, 1987. – Т. 1. – 398 с.
Здравствуйте. Скажите пожалуйста, планирую поступать в магистратуру на факультет Психологии « Психология личности»в РГГУ скажите пожалуйста, есть ли у вас, ответы на вступительные экзамены? так как, планирую, сделать акцент на бюджет. Спасибо.
Арсений, здравствуйте! Прошу Вас прислать всю необходимую информацию на почту info@otlichnici.ru и написать что необходимо выполнить. Я посмотрю описание к заданиям и подскажу вам по стоимости и срокам выполнения.
Дистанционная помощь в защите ВКР
Анастасия, здравствуйте! Прошу Вас прислать всю необходимую информацию на почту info@otlichnici.ru и написать что необходимо выполнить. Я посмотрю описание к заданиям и подскажу вам по стоимости и срокам выполнения.
Здравствуйте. Нужна срочно практическая часть вкр, третья глава. Скину похожие работы, на которые можно ориентироваться
Александр, здравствуйте! Прошу Вас прислать всю необходимую информацию на почту info@otlichnici.ru и написать что необходимо выполнить. Я посмотрю описание к заданиям и подскажу вам по стоимости и срокам выполнения.
вкр по теме: экологический туризм России : анализ состояния, проблемы и перспективы
Людмила, здравствуйте! Прошу Вас прислать всю необходимую информацию на почту info@otlichnici.ru и написать что необходимо выполнить. Я посмотрю описание к заданиям и подскажу вам по стоимости и срокам выполнения.
Здравствуйте вы защищаете ВКР?
Ольга, здравствуйте! Прошу Вас прислать всю необходимую информацию на почту info@otlichnici.ru и написать что необходимо выполнить. Я посмотрю описание к заданиям и подскажу вам по стоимости и срокам выполнения.
Написать магистерскую ВКР на тему «Совершенствование логистических бизнес-процессов на примере торговой компании». Не менее 100 страниц.
Миша, здравствуйте! Прошу Вас прислать всю необходимую информацию на почту info@otlichnici.ru и написать что необходимо выполнить. Я посмотрю описание к заданиям и подскажу вам по стоимости и срокам выполнения.
Здравствуйте нужна работа Вкр
Лена, здравствуйте! Прошу Вас прислать всю необходимую информацию на почту info@otlichnici.ru и написать что необходимо выполнить. Я посмотрю описание к заданиям и подскажу вам по стоимости и срокам выполнения.
Написать ВКР 3 раздела Тема строительство строительство жилого дома с применением каркасно-монолитных технологий Антиплагиат от 75% ПЗ и чертежи
Владимир, здравствуйте! Прошу Вас прислать всю необходимую информацию на почту info@otlichnici.ru и написать что необходимо выполнить. Я посмотрю описание к заданиям и подскажу вам по стоимости и срокам выполнения.