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

lpContext – указатель на структуру CONTEXT куда будет записана

информация.

Для изменения контекста потока используется функция

SetThreadContext с прототипом:

BOOL SetThreadContext(HANDLE hThread, LPCONTEXT

lpContext);

hThread – описатель потока для получения контекста.

lpContext – указатель на структуру CONTEXT, где записан новый

контекст потока.

Примечание: функции работают корректно только с приостановленными

потоками.

Пример 9. Программа приостанавливает поток, выполняющий бесконечный цикл и получает его контекст,

выводя содержимое регистров EAX, EIP и ESP на экран.

// Функция потока с бесконечным циклом

DWORD __stdcall Loop(LPVOID lpParam)

{

for(;;){}

return 0;

}

int main(int argc, char* argv[])

{
HANDLE hThread; //		Описатель потока
CONTEXT cnt;	//	Контекст потока

// Создание приостановленного потока с бесконечным циклом

hThread = CreateThread(NULL, 0, Loop, NULL,

CREATE_SUSPENDED, NULL);

31

// Получаем контекст потока

GetThreadContext(hThread, &cnt);

// Распечатка содержимого регистров на экране printf("EAX=0x%X\n", cnt.Eax); printf("EIP=0x%X\n", cnt.Eip); printf("ESP=0x%X\n", cnt.Esp);

// Остановка потока

TerminateThread(hThread, 0xFF);

return 0;}

Использование потоков для научных вычислений

Параллельные вычисления часто используются для решения сложных вычислительных задач, которые можно эффективно представить в параллельной форме (по данному вопросу рекомендуется обратиться к источникам [7], [15]). В данном пособии мы рассмотрим задачу квадратуры -

аппроксимации интеграла непрерывной функции f(x) на отрезке [a, b] (см.

Рисунок 4).

Рисунок 4. Задача квадратуры для двухпроцессорной конфигурации.

32

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

Если для решения задачи мы можем использовать многопроцессорную конфигурацию, то становится возможным разделить весь отрезок интегрирования [a, b] на несколько равных отрезков [a, k1], [k1, k2], ..., [kn, b] с числом отрезков равным числу процессоров и выполнить вычисления параллельно в отдельных потоках. После окончания работы потоков суммарный результат будет являться решением задачи квадратуры (см. Пример 10).

Пример 10 Параллельный алгоритм численного интегрирования методом прямоугольников с фиксированным шагом с адаптацией к числу процессоров.

#include<windows.h> #include <iostream> #include <math.h> // F(x)

#define FX(x) x // Очень простая функция F(x)=x // Метод прямоугольников.

#define Q(x, h) h*FX(x)

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

{

// Конструктор по умолчанию

_PARAM(): h(0.0), a(0.0), b(0.0), res(0.0){}

// Шаг интегрирования

33

double h;

// Пределы интегрирования для потока double a;

double b;

// Результат интегрирования double res;

} PARAM, *LPPARAM;

// Функция потока, выполняющая аппроксимацию интеграла

DWORD __stdcall WorkerThread(LPVOID p)

{

// Через параметр LPVOID переданы параметры интегрирования

LPPARAM param = (LPPARAM)p;

//Численное интегрирование на отрезке [param->a; param->b]

//с накоплением суммы в param->res

for (double x = param->a; x < param->b; x+=param- >h)

param->res+=Q(x, param->h); return 0;

}

//Пределы интегирования

#define A 0.0F #define B 10.0F

// Возвращает число процессоров в системе

34

DWORD GetProcessorCount()

{

SYSTEM_INFO si;

GetSystemInfo(&si);

return si.dwNumberOfProcessors;

}

int _tmain(int argc, _TCHAR* argv[])

{

// Получить число процессоров в системе

DWORD pc = GetProcessorCount();

//Создаѐм число потоков=числу процессоров.

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

//Каждый поток через структуру PARAMS получает

//в качестве параметра свои пределы интегрирования.

//Число заданий = числу процессоров.

LPPARAM params = new PARAM[pc];

// Число потоков=числу процессоров.

LPHANDLE hthreads = new HANDLE[pc];

// Длина отрезка интегрирования double l = abs(B-A) / pc;

// Число интервалов

#define N 10000L

// Подгатавливаем заявки на интегрирование

35

double a = A;

for (DWORD i = 0; i < pc; i++)

{

params[i].a = a; params[i].b = a + l; params[i].h = l/N; a+=l;

}

// Создание потоков

for (DWORD i=0; i < pc; i++)

hthreads[i] = CreateThread(NULL, 0, WorkerThread, &params[i], 0, NULL);

// Ждѐм завершения интегрирования

WaitForMultipleObjects(pc, hthreads, TRUE, INFINITE);

double res = 0;

// Суммируем результаты и закрываем описатели потоков

for (DWORD i = 0; i < pc; i++)

{

res+=params[i].res;

CloseHandle(hthreads[i]);

}

// Освобождаем ресурсы delete[] params;

36

delete[] hthreads;

// Вывод результата

std::cout << "result=" << res << std::endl;

return 0;

}

Задачи и упражнения

1.Рассчитайте базовые приоритеты потоков (Ptb):

a.Pp = NORMAL_PRIORITY_CLASS; Pt=THREAD_PRIORITY_TIME_CRITICAL; Ptb=?

b.Pp = IDLE_PRIORITY_CLASS; Pt=THREAD_PRIORITY_IDLE; Ptb=?

2.Какие комбинации Pp и Pt могут дать следующие Ptb:

a.Ptb=9;

b.Ptb=15;

c.Ptb=27;

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

THREAD_PRIORITY_BELOW_NORMAL;

4.Модифицируйте программу из Пример 6 для обеспечения возможности

остановки потоков, если они оба не завершились за 2000 мс.

3.Модифицируйте программу из Пример 6 для обеспечения возможности приостановки/возобновления выполнения потоков.

3.Модифицируйте программу из Пример 9, что бы пользователь мог изменить контекст потока (регистры Esp, Eip, Eax) и возобновить его работу.

4.Спроектируйте и реализуйте класс на языке С++, инкапсулирующий работу с потоками. Класс выполняет следующие обязанности:

создаѐт новый поток, выполняющий заданную функцию;

чтение/изменение базового приоритета потока;

приостановка/возобновление работы потока;

остановка потока;

чтение/изменение контекста потока.

37

Атрибуты класса:

описатель потока;

идентификатор потока.

5.Создайте следующие параллельные программы, адаптированные к числу процессоров в системе:

параллельное перемножение матриц;

параллельная рекукрсивная быстрая сортировка;

параллельное транспонирование матриц;

параллельный поиск подстроки в заданных файлах: fsearch.exe

<подстрока> <файл, ... >. Пример: fsearch.exe Hello c:\1.txt d:\2.txt.

Программа выводит на экран имена файлов, где подстрока найдена и смещение в файле.

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

1.В чем состоит принципиальное отличие состояний «ожидания» и «готовности» потока, ведь и в том и в другом он ожидает некоторого события?

2.Расскажите о механизме назначения приоритета потоку в ОС Windows 2000.

3.Почему в большинстве современных ОС у каждого потока существует два стека: стек пользовательского режима и стек ядра?

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

5.Что такое контекст потока? Какая информация туда входит? Почему структура CONTEXT является аппаратно-зависимой?

6.В какой очереди (ожидающих или готовых) скапливается большее число потоков:

a.в интерактивных системах разделения времени;

b.в системах пакетной обработки, решающих «счетные» задачи.

38

7. Чем объясняется потенциально более высокая надежность операционных систем, в которых реализована вытесняющая многозадачность?

8. В каких ОС реализована невытесняющая многозадачность? А вытесняющая многозадачность?

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

имеем дело со статическим планированием?

10.Приведите пример алгоритма планирования, в результате работы которого поток, располагая всеми необходимыми ресурсами, может бесконечно долго находиться в системе, не имея возможности завершиться.

11.Могут ли быть применены сразу все перечисленные характеристики к одному алгоритму планирования потоков?

a.вытесняющий, с абсолютными динамическими приоритетами;

b.невытесняющий, с абсолютными фиксированными приоритетами;

c.невытесняющий, с относительными динамическими приоритетами;

d.вытесняющий, с абсолютными фиксированными приоритетами, основанный на квантовании с динамически изменяющейся длиной кванта;

e.невытесняющий, основанный на квантовании с фиксированной

длиной кванта.

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

12.Можно ли задачу планирования потоков целиком возложить на приложения?

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

14.Возможно ли существование асимметричной мультипроцессорной ОС для компьютера с симметричной мультипроцессорной архитектурой?

15.Сравните два варианта организации мультипроцессорной обработки. В первом случае процесс (поток), начав выполняться на каком-либо процессоре, при каждой следующей активизации будет назначаться планировщиком на этот же процессор. Во втором варианте процесс

39

(поток) каждый раз, в общем случае, выполняется на произвольно выбранном свободном процессоре. Какой вариант эффективнее в отношении времени выполнения отдельного приложения? В отношении суммарной производительности компьютера?

16.Какие события вызывают перепланирование потоков?

40