Домашнее заданее

Московский государственный технический университет имени Н.Э. Баумана

Домашнее задание

по курсу «Параллельное программирование»

Тема:

Исследование системы обмена сообщениями

Преподаватель:

к.т.н., доцент Бобков А.В.

Москва, 2008

Цель работы: Изучить особенности механизма взаимодействия потоков в системах с обменом сообщениями.

Отчет по ДЗ должен содержать:

- Описание каждого из этапов работы, его особенностей, наблюдаемых явлений и их объяснение.

- Листинг ключевых моментов программы (с комментариями на русском языке)

К отчету должен прилагаться электронный носитель информации с исходными кодами программы.

Задание 1. Напишите программу, исследующую сходимость комплексного ряда в точках комплексной плоскости в области x=‑2..+2, y=‑2..+2. Ряд задан рекуррентным соотношением:

(1)

где –N-ный член комплексного ряда,

– точка комплексной плоскости.

Ряд является расходящимся, если при .

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

Исследования ряда (1) показали, что если вещественная часть одного из членов ряда по модулю превысит число , то ряд в данной точке расходится.

Таким образом, исследование поведения ряда (1) в заданной точке сводится к определению вещественных частей членов этого ряда, и сравнению их модулей с верхним пределом .

Вычисления происходят по следующей схеме.

Z[i+1]=Z[i]^2+C=

=(Xi+jYi)^2+Cx+jCy=

=(Xi^2–Yi^2+Cx)+j(2*Xi*Yi+Cy).

Отсюда:

X[i+1]=X[i]*X[i] – Y[i]*Y[i] + Cx,

Y[i+1]=2*X[i]*Y[i] + Cy.

Начальные условия:

X0=0;Y0=0  X1=Cx, Y1=Cy.

Реализацию программы удобно разбить на несколько шагов.

1.Напишите функцию для вычисления сходимости в точке (x,y). Функция может иметь следующий вид:

int Limit=256; //Максимальное число итераций

int Compute(long double Cx, long double Cy)

{long double Zx=Cx, Zy=Cy, tmpX; HDC c=CreateDC("DISPLAY", 0, 0, 0);::TextOut(c,100,300,"Что, Данила-мастер, не выходит каменная чаша?",45);ReleaseDC(0,c);return 0;

int n=0;

HDC dc=CreateDC("DISPLAY", 0, 0, 0); ::TextOut(dc,200,320,"Ну, не судьба. Может, каменная рюмка выйдет?",45);ReleaseDC(0,dc);return 0;

while ((n<Limit)&&(Zx<3.14) &&(Zx>-3.14))

{ Zx=(tmpX=Zx)*Zx-Zy*Zy + Cx;

Zy=2* tmpX*Zy + Cy;

n++;

}

return n;

}

(Пожалуйста, напишите свою функцию. Не надо копировать текст из методички.)

2.При помощи полученной функции исследуйте ряд в диапазоне [-1.5..+1.5, -1.5..+1.5]. Шаг выбирается таким, чтобы число исследуемых точек было равно числу точек в окне программы. Напишите функцию, которая будет раскрашивать соответствующую точку в черный цвет, если ряд в ней расходится, и в белый – если сходится. Можете использовать номер итерации, на которой ряд разошелся, для задания своего цвета.

Как пересчитать координату х из диапазона [a1..a2] в диапазон [b1..b2]?

1.Переносим начало координат в 0:

x1=x-a1; x1[0..a2-a1]

2.Устанавливаем единичный диапазон:

x2=x1/(a2-a1), x2[0..1]

3.Устанавливаем требуемый диапазон:

x3=x2*(b2-b1), x3[0..b2-b1]

4. Переносим начало координат в b1:

x4=x3+b1, x4[b1..b2].

Итоговая формула:

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

Задание 2

Добавьте обработчик нажатия на кнопку мыши. Правая кнопка должна обеспечивать перезапуск вычислений в увеличенном масштабе, левая – в уменьшенном. Центром новой области является место щелчка мышью. Если удерживается кнопка Shift, область должна увеличиваться/уменьшаться не в два, а в четыре раза.

Для добавления обработчика сообщений от мыши удобно использовать Class Wizard (ctrl+W). Откройте вкладку Message Maps, в левом верхнем списке выберите класс диалогового окна, в правом верхнем – сообщение WM_LBUTTONDOWN (сообщение о нажатии левой кнопки мыша). Нажмите Add Function и Edit Code.

Функция-обработчик сообщения принимает два параметра:

point – запись, полями x и y которой являются координаты мыши относительно текущего окна. Обращение к полям – point.x и point.y соответственно.

nFlags – переменная, указывающая состояние клавиш Shift, Ctrl, а также кнопок мыши (нажато или нет). Если клавиша нажата, соответствующий бит nFlags равен 1. Для проверки состояния отдельных битов следует использовать операцию бинарное И (&):

if ((nFlags & MK_SHIFT) ==0) <Shift не нажат>

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

Задание 3

Добавьте на форму список, в котором можно выбирать цветовую схему. В списке должны присутствовать схемы:

• черно-белая. Черный – точки схождения, белый – расхождения.

• прогрессивная. Color=RGB(n*r,n*g,n*b). n-номер итерации, на которой зафиксировано расхождение ряда, r,g,b –константы (например – 2,3,4).

• гармоническая:

red =128+127*Cos(n*r); //r=0.10

green=128+127*Sin(n*g);//g=0.11

blue =128+127*Cos(n*b);//b=0.08

• ваша собственная.

При изменении схемы форма должна сразу же перерисовываться.

Для реакции на выбор элемента списка добавьте обработчик для сообщения SBN_SELCHANGE.

Для получения номера выбранного элемента в списке можно использовать метод int GetCurSel() списка CComboBox.

Задание 4

Добавьте обработчик перерисовки формы. Рисунок на форме должен сохраняться при переключении окон. Перерисовка должна выполняться не более двух секунд.

Для перерисовки используйте обработчик OnPaint. Он уже по умолчанию присутствует в диалоге.

Добавьте на форму окно редактирования, в котором можно менять глубину расчета.

При изменении текста в окне редактирования вызывается сообщение EN_CHANGE.

Задание 5.

Добавьте возможность изменения размеров окна. При этом областью отрисовки сделайте все окно.

Для отклика на изменение размера окна используйте сообщение WM_SIZE.

Для изменения области исследования комплексного ряда удобно ввести динамический массив. Для работы с динамическими массивами используйте операторы new и delete.

Как использовать одномерный массив вместо двухмерного?

Пусть Width-ширина массива, Height – высота. Размер массива равен Width*Height*sizeof(тип элемента);

Элемент с индексами x и y будет находиться в одномерном массиве в позиции pos=y* Width+x.

Тогда вместо A[10][20] следует написать: B[10+Width*20].

Задание 6

Запустите функцию отдельным потоком, используя функцию CreateThread.

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

Задание 7

Модифицируйте программу для работы на многопроцессорной ЭВМ. Первый процессор ориентирован на выполнение арифметических операций, и не имеет средств взаимодействия с пользователем. Второй процессор ­– процессор на ПЭВМ под управлением ОС WINDOWS. Процессоры могут присутствовать физически или эмулироваться путем запуска отдельных потоков в псевдопараллельном режиме.

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

Для посылки сообщений служат функции PostMessage и SendMessage. PostMessage помещает сообщение в очередь окна и возвращается, а SendMessage помещает сообщение и ожидает оканчания его обработки. Удобно пользоваться перегруженными версиями этих функций, которые определены для класса диалогового окна:

DWORD CDlg.PostMessage(int Message_ID,int lParam, int wParam);

DWORD CDlg.SendMessage(int Message_ID,int lParam, int wParam);

Здесь Message_ID –идентификатор сообщения. Пользовательские сообщения должны начинаться с константы WM_USER:

#define MyMessage WM_USER+10

Как добавить обработчик сообщения? К сожалению, Class Wizard не умеет добавлять обработчики пользовательских сообщений, и это придется делать вручную.

Сначала надо добавить к классу диалога функцию-обработчик, которая возвращает void и принимает два целых параметра – параметры сообщения. На вкладке Classes левого окна выбираем имя диалога, правой кнопкой кликаем на имени класса диалога, и выбираем AddFunction. Компилятор добавляет функцию, например – такую:

void CPrDlg::OnMy(LPARAM l, WPARAM p)

В ней мы напишем текст обработчика сообщения.

Теперь свяжем сообщение с кодом обработчика. Найдите код, начинающийся с макроса BEGIN_MESSAGE_MAP(CPrDlg, CDialog). Этот участок кода называется картой сообщений (message map). Он связывает сообщения с их обработчиком, и выглядит примерно так:

BEGIN_MESSAGE_MAP(CPrDlg, CDialog)

//{{AFX_MSG_MAP(CPrDlg)

ON_WM_PAINT()

ON_WM_QUERYDRAGICON()

ON_BN_CLICKED(IDC_BUTTON1, OnButton1)

ON_MESSAGE(MyMessage,OnMy)

//}}AFX_MSG_MAP

END_MESSAGE_MAP()

Добавьте макрос ON_MESSAGE. Он принимает два параметра – идентификатор сообщения и имя функции-обработчика. Теперь при посылке сообщения MyMessage будет автоматически вызываться функция OnMy. Аргументами функции будут являться значения, переданные функциям PostMessage и SendMessage. Это могут быть или целые числа, или указатель на структуру с дополнительными данными.

В итоге должна получиться программа, эмулирующая выполнение сложных вычислений на отдельном процессоре, и обеспечивающая удобный интерфейс с пользователем за счет основного процессора. Обратите внимание, что в обоих случаях используется один и тот же механизм – обмен сообщениями.

Контрольные вопросы

1.Какие способы организации взаимодействия между процессорами вы знаете? В чем состоят достоинства и недостатки этих способов?

2.Почему в ОС Windows (и аналогичных современных многозадачных системах) используется коммуникация между процессами путем обмена сообщений? Какие преимущества это дает?

3.Что может являться источником сообщений в ОС Windows?

4.Что представляет из себя сообщение ОС Windows?

5.Каким образом происходит обработка сообщений в ОС Windows?