Работа №2. Синхронизация потоков
Предисловие
Дана программа TM1.cpp (см. [code]). Этa программа реализует однопоточный менеджер задач, который выполняет задачи из очереди задач qt. Очередь qt состоит из элементов типа TCB (Task Control Block):
struct TCB { // Task Control Block
int tcb_id;
int func_id;
int arg;
double start;
TCB *next;
};
Комментарии:
tcb_id - порядковый номер TCB в qt.
func_id - индекс стандартной функции из массива fplist, определяющей вычислительный процесс, связанный с данным TCB. Сами функции определены непосредственно в программе. Предполагается, что спецификации всех функций в fplist одинаковы и соответствуют типу LPFTM:
typedef int(*LPFTM)(int);
arg - значение аргумента для функции, определяемой func_id.
start - время старта функции.
next - указатель на следующий TCB в qt.
В программе предусмотрено меню для управления TМ, которое позволяет формировать TCB для включения в qt, просматривать qt и запускать qt на исполнение. См. пример протокола работы TM1 в out-файле.
Задание
1. Составить программу TM.cpp, которая реализует выполнение очереди задач qt в nth потоках.
2. Реализовать недостающие операции меню.
3. Исследовать поведение программы TM.cpp в зависимости от числа рабочих потоков, т.е. определить как зависит общее время выполнения всех задач из очереди задач от числа потоков. Определить коэффициенты ускорения по отношению к однопоточному варианту программы.
Содержание отчета
1. Текст задания
2. Исходный код программ на языке C++.
3. Примеры входа и выхода программ.
4. Результаты исследования поведения программы TM.cpp.
Представить в форме таблицы с последующим указанием сведений о среде выполнения программ (ПК, ОС, и т.п.).
5. Выводы
Контрольные вопросы
1. Дайте определение двоичного семафора Дейкстры.
2. Как реализовать функции P и V семафора Дейкстры средствами API Win32?
3. Объясните назначение и способы использования следующих функций API Win32: CreateSemaphore, ReleaseSemaphore.
4. Объясните организацию потоков в примере ProCons [1].
5. Дайте сравнительную характеристику программ TM1.cpp и TM.cpp.
6. Можно ли в TM.cpp организовать выполнение операций меню в отдельном потоке? Какие преимущества при этом будут получены?
Приложение 1. TM1.cpp.
// TM1.cpp (Task Manager) - 18-09-16
#include <windows.h>
#include <iostream>
#include <stdio.h>
using namespace std;
#define FLISTLEN 2 // len of fplist
#define NTH 1 // number of threads
int nth = 1; // number threads for workers
int t0;
double clock() {return (GetTickCount() - t0)/1000.0;}
struct TCB { // Task Control Block
int tcb_id;
int func_id;
double start;
int arg;
TCB *next;
};
TCB *head = 0, *last = 0;
int qt_cnt = 0;
int nextPrime(int N) {
if(N < 2) return 2;
int res = N;
res++;
if(res % 2 == 0) res++;
int dd = 0;
bool isPrime;
do {
isPrime = true;
while(dd*dd < res) dd++;
for(int d=3; d<=dd; d+=2) {
if(res % d == 0) {isPrime = false; break; }
}
if(!isPrime) res += 2;
} while(!isPrime);
return res;
}
int piR(int N) {
int n = 0;
int pcnt = 0;
while(true) {
n = nextPrime(n);
if(n >= N) break;
pcnt++;
}
return pcnt;
}
typedef int(*LPFTM)(int);
LPFTM fplist[FLISTLEN] = { nextPrime, piR };
const char* fnlist[FLISTLEN] = { "nextPrime", "piR" };
int main(int argc, char *argv[]) {
int answer, func_id, arg, tcb_id = 0;
head = new TCB();
head->next = 0;
last = head;
cout << "TM1 started" << endl;
while(true) {
cout << "--- List of standard functions:" << endl;
for(int i=0; i<FLISTLEN; i++)
cout << i << " - " << fnlist[i] << endl;
cout << "-------------------------" << endl
<< "0 - stop TM" << endl
<< "1 func_id arg - insert tcb into qt" << endl
<< "2 - view qt" << endl
<< "3 tcb_id - delete tcb from qt" << endl
<< "4 nth - set nth" << endl
<< "5 - run qt" << endl
<< "-------------------------" << endl;
bool isRun = false;
while(!isRun) {
cout << "? ";
cin >> answer;
TCB *p;
switch(answer) {
case 0:
return 0;
case 1:
cin >> func_id >> arg;
tcb_id++;
p = new TCB();
p->tcb_id = tcb_id;
p->func_id = func_id;
p->arg = arg;
p->next = 0;
last->next = p;
last = p;
break;
case 2:
p = head->next;
cout << "----- qt:" << endl;
while(p!= 0) {
cout << p->tcb_id << " " << p->func_id << " " << p->arg << endl;
p = p->next;
}
cout << "-----" << endl;
break;
case 5:
isRun = true;
break;
}
}
cout << "Running qt with " << nth << " threads..." << endl;
t0 = GetTickCount();
TCB *p = head->next;
while(p!= 0) {
p->start = clock();
int res = fplist[p->func_id](p->arg);
double stop = clock();
printf("%3d %3d %10d %10d %7.3f %7.3f\n",
p->tcb_id, p->func_id, p->arg, res, p->start, stop);
p = p->next;
}
}
return 0;
}
Приложение 2. Пример диалога взаимодействия.
TM1 started
--- List of standard functions:
0 - nextPrime
1 - piR
-------------------------
0 - stop TM
1 func_id arg - insert tcb into qt
2 - view qt
3 tcb_id - delete tcb from qt
4 nth - set nth
5 - run qt
-------------------------
? 1 1 1000000
? 1 1 10000000
? 2
----- qt:
1 1 1000000
2 1 10000000
-----
? 3
? 4
? 5
Running qt with 1 threads...
1 1 1000000 78498 0.000 0.187
2 1 10000000 664579 0.187 5.023
--- List of standard functions:
0 - nextPrime
1 - piR
-------------------------
0 - stop TM
1 func_id arg - insert tcb into qt
2 - view qt
3 tcb_id - delete tcb from qt
4 nth - set nth
5 - run qt
-------------------------
? 0