Процессор, оперативная память, шина, внешние устройства. Протокол работы шины и подключение новых внешних устройств. Фон-Неймановская архитектура и алгоритм работы компьютера. Регистры процессора. Регистры, играющие особую роль: счетчик команд (или указатель инструкции) PC (Program Counter), указатель стека SP (Stack Pointer), указатель кадра FP (Frame Pointer). Абстрактный стек, стековый вычислитель и обратная польская запись выражений. Аппаратный стек и его реализация. Использование аппаратного стека для сохранения состояния задачи, для хранения точек возврата при вызове функций. Размещение локальных переменных функции в аппаратном стеке. Соглашения о вызовах функций в языке C/C++: передача параметров через стек и использование регистра FP для относительной адресации параметров и локальных переменных. Классы памяти в языке C/C++: статическая, стековая, динамическая, правила их использования. Реализация рекурсии, примеры рекурсивных программ: простой и расширенный алгоритмы Евклида.
Новые соглашения о вызовах функций для 64-битового процессора типа Intel/AMD x86-64: поскольку добавлено 8 новых регистров R8-R15 и регистров стало в 2 раза больше, теперь возможно передавать аргументы функции через регистры, что делат программы значительно более быстрыми. В Unix-подобных системах (Linux, MAC OS-X) и в MS Windows для 64-разрядных процессоров Intel 86-64 используются разные соглашения о передаче параметров. В MS Windows первые 4 целочисленных аргумента передаются через регистры RCX, RDX, R8, R9, остальные через стек; в Linux первые 6 целочисленных аргументов передаются через регистры RDI, RSI, RDX, RCX, R8, R9, остальные также через стек. Функции должны сохранять значения следующих регистров: в MS Windows RBX, RBP, RDI, RSI, RSP, R12-R15; в Linux/OS-X RBX, RSP, RBP, R12-R15. Значение функции возвращается в регистре RAX. Отметим, что в любых 64-разрядных архитектурах регистры RAX, RCX, RDX, R8, R9 можно использовать для промежуточных вычислений и для хранения локальных переменных функции, поскольку сохранять их не обязательно.
gcc -o tstmax tstmax.c max64Win.s
команда для сборки программы, Linux/OS-X:
gcc -o tstmax tstmax.c max64.s
gcc -o tstsum tstsum.c sum64Win.s
команда для сборки программы, Linux/OS-X:
gcc -o tstsum tstsum.c sum64.s
В задании 2 варианта. Студенты с нечетными номерами по журналу делают первую задачу, с четными — вторую. Требуется написать функцию на Ассемблере и тестирующую программу, использующую эту функцию, на языке C; примеры таких микро-проектов приведены выше. Можно писать проект для MS Windows (с используванием CygWin) или для Linux/OS-X в зависимости от того, какая OS установлена на вашем компьютере.
int arrayMax(const int *a, int n);
int numSignChanges(const int *a, int n);
Мы считаем, что числа ≥ 0 положительны (знак +),
числа < 0 отрицательные (знак -). Например,
в последовательности
Уровни защиты (Protection rings) и их использование в операционных системах. Режим ядра (нулевое кольцо) и пользовательский режим (кольцо 3), почему необходимы такие уровни. Промежуточные уровни защиты 1 и 2 (используются редко).
Прерывания: аппаратные (асинхронные) и программные (синхронные). Векторы прерываний и порядок обработки прерывания: сохранение состояния прерванной задачи в аппаратном стеке, переключение контекстов и вызов обработчика прерывания в операционной системе, восстановление контекста и продолжение исполнения прерванной задачи. Причины синхронных прерываний: ошибка в программе (деление на 0, обращение по несуществующему адресу и т.п.) или исполнение специальной команды прерывания, например, команды INT процессора Intel 80X86. Использование команды прерывания INT для вызова функций операционной системы (INT 21 в MS DOS, INT 80 в Linux).
Виртуальная память, почему она необходима в многозадачных операционных системах. Два способа организации виртуальной памяти: устаревшая сегментная реализация (на примере процессора Intel 80286), современная страничная реализация виртуальной памяти. Таблица описателей страниц и алгоритм вычисления физического адреса по виртуальному. Вытеснение страниц виртуальной памяти на диск при нехватке физического пространства. Прерывание "Page fault" и своппинг.
Основные функции операционной системы:
1) предоставление прикладным программам удобного
интерфейса для работы с устройствами, файлами и т.п.
и одновременное обеспечение независимости прикладных
программ от конкретных устройств;
2) управление процессами, исполняющимися на компьютере
(обеспечение взаимной независимости, передача информации
между процессами - IPC, распределение памяти и процессорного
времени и т.п.).
Краткая история операционных систем. Эпоха компьютеров без ОС - использование перфокарт и лент для ввода и выполнения программ. Пакетный (Batch) режим исполнения заданий. ЭВМ IBM 360/370 и их советский аналог ЕС ЭВМ, одновременная загрузка нескольких задач в память (с использованием позиционно-независимого кода или сегментных регистров). Первые мини-ЭВМ - PDP-11 фирмы DEC с 16-разрядной архитектурой и их операционные системы: однозадачная RT-11 с непрерывными файлами, многозадачная RSX-11. Первая 32-разрядная мини-ЭВМ VAX и многозадачная ОС с высокой степенью защиты VAX VMS. MS DOS как одна из первых ОС для персональных компьютеров, 16-разрядная MS Windows 3.1. Windows NT, созданная совместно фирмами Microsoft и IBM с использованием опыта разработки VAX VMS (разработчик Дейв Катлер из фирмы DEC) и API Win32. Понятие API (Application Program Interface) как центральное в области разработки программного обеспечения - контракт между создателями операционной системы и разработчиками прикладных программ.
Возвращение к 16-разрядной операционной системе Windows 95 и причины этого. Новое в Windows 95: поддержка Internet-протоколов, удобный оконный интерфейс. Линия 16-разрядных ОС фирмы Microsoft - Windows 98, Millenium Edition. Обратное возвращение к Windows NT: Windows 2000, Windows XP, Vista, Windows 7/8 и 64-битные варианты этих систем.
Операционная система Unix, ее краткая характеризация и история. Unix как первая переносимая операционная система, написанная почти целиком на языке высокого уровня C. Варианты Unix - System-V от Bell Labs и AT&T, системы, разработанные в университете Berkeley - FreeBSD (Berkeley Software Distribution), NetBSD, использования этих систем как серверов в Internet. Система Linux, созданная финским студентом Линусом Торвальдсом, и ее развитиев рамках проекта открытого программного обеспечения.
Операционные системы компьютеров Apple Macintosh. Ранние версии сисмемы Mac OS и их особенности (отождествление файлов по двум целым числам вместо традиционных имен или путей к файлам, подпись Signature программ и файлов с документами, файлы, состоящие из двух частей - Data fork и Resource fork, оконный интерфейс как часть операционной системы).Современные системы Apple Macintos, начинающиеся с Mac OS X, ядро которой построено на основе FreeBSD-Unix с использованием микроядра Mach. Операционные системы Android и Chromium фирмы Google для планшетных компьютеров и смартфонов на основе Linux.
Понятие процесса является основным в любой операционной системе. Процесс - это задача, запущенная на компьютере (хотя такой термин не очень точный, поскольку задача может выполняться и несколькими процессами, работающими параллельно). У каждого процесса есть следующие компоненты.
В программировании постоянно возникает необходимость параллельного выполнения нескольких задач. Во-первых, в настоящее время резервы для увеличение быстродействия процессоров почти исчерпаны, и дальнейшее наращивание мощности компьютеров возможно лишь в параллельных системах. Во-вторых, при программировании в оконной среде в оконной программе, как правило, должно быть несколько нитей, поскольку одна нить должна обязательно обрабатывать сообщения оконной системы, чтобы программа могла мгновенно реагировать на действия пользователя. Любые длительные вычисления, сетевой обмен, файловые операции и т.п. в оконной программе должны исполняться параллельно другими нитями или процессами.
Существуют следующие способы обмена данными между процессами.
int fds[2];
int res = pipe(fds);
После успешного выполнения системного вызова pipe процесс
выполняет вызов fork, создающий два одинаковых процесса,
один из которых является родителем (parent), другой -
ребенком (child). Допустим, данные нужно передавать от ребенка
к родителю. Тогда родительский процесс закрывает второй файловый
дескриптор, а процесс-ребенок - первый дескриптор. Ребенок пишет
данные, используя второй дескриптор, родитель их читает,
используя первый дескриптор:
int pid = fork();
if (pid != 0) {
// This is the parent process
close(fds[1]);
len = read(fds[0], buffer, maxLen);
. . .
} else {
// This is the child process
close(fds[0]);
res = write(fds[1], buffer, len);
. . .
}
Таким способом реализуется односторонняя связь между процессом-ребенком и процессом-родителем (pipe - это труба, по которой данные текут лишь в одну сторону). Для двусторонней связи надо создать две трубы и четыре файловых дескриптора.
В MS Windows использование программных каналов (pipe) менее популярно, чем в Unix, поскольку отсутствует системный вызов fork.
Код длясоздания программного канала в MS Windows намного более сложный, чем в Unix. Программный канал создается с помощью функции CreatePipe, которая возвращает пару связанных между собой HANDLE'ов файлов, первый открыт для чтения, второй для записи. При этом надо обязательно заполнить структуру SECURITY_ATTRIBUTES, если мы хотим, чтобы эти хендлы был наследуемыми. Вот пример создания программного канала (трубы):
SECURITY_ATTRIBUTES sa;
memset(&sa, 0, sizeof(sa));
sa.nLength = sizeof(SECURITY_ATTRIBUTES);
sa.bInheritHandle = TRUE;
HANDLE hParentInput, hParentOutput;
HANDLE hChildInput, hChildOutput;
// Create a pipe for the child process's STDOUT.
if (!CreatePipe(
&hParentInput, &hChildOutput, &sa, 0
))
errorExit("Child output pipe creation failed");
// Ensure the hParentInput handle is not inherited.
SetHandleInformation(
hParentInput, HANDLE_FLAG_INHERIT, 0
);
Здесь создается труба для односторонней связи от процесса-ребенка
к процессу-отцу. Ребенок унаследует хендл hChildOutput, в который
он будет записывать информацию. Эта информация будет читаться
процессом-отцом из хендла hParentInput. Этот хендл не должен быть
наследуемым, поэтому он отмечается как ненаследуемый с помощью
системного вызова SetHandleInformation.
Для двусторонней связи между отцом и ребенком нужна и вторая труба, по которой отец будет посылать сообщения ребенку. Она создается аналогично. Сообщения будут посылаться отцом в файл с хендлом hParentOutput и приниматься ребенком из файла с хендлом hChildInput. При этом хендл hParentOutput также помечается как ненаследуемый:
// Create a pipe for the child process's STDIN.
if (!CreatePipe(
&hChildInput, &hParentOutput, &sa, 0
))
errorExit("Child input pipe creation failed");
// Ensure the hParentOutput handle is not inherited.
SetHandleInformation(
hParentOutput, HANDLE_FLAG_INHERIT, 0
);
Процесс-ребенок создается с помощью функции CreateProcess, при этом мы заполням структуру STARTUPINFO, в которой указываем хендлы, котторые будут унаследованы процессом-ребенком для стандартного ввода и вывода:
// Create the child process
PROCESS_INFORMATION pi;
memset(&pi, 0, sizeof(pi));
STARTUPINFO si;
memset(&si, 0, sizeof(si));
si.cb = sizeof(si);
si.hStdError = hChildOutput;
si.hStdOutput = hChildOutput;
si.hStdInput = hChildInput;
si.dwFlags |= STARTF_USESTDHANDLES;
if (!CreateProcess(
"rcalc.exe", // Module name
"rcalc.exe", // Command line
NULL, // Process handle not inheritable
NULL, // Thread handle not inheritable
TRUE, // Inherit handles
0, // CREATE_NEW_CONSOLE, // Creation flags
NULL, // Use parent's environment block
NULL, // Use parent's starting directory
&si, // Pointer to STARTUPINFO structure
&pi // Pointer to PROCESS_INFORMATION structure
))
errorExit("CreateProcess failed");
// Close process and thread handles.
CloseHandle(pi.hProcess);
CloseHandle(pi.hThread);
Для чтения и записи данных через программые каналы мы используем функции ReadFile и WriteFile операционной системы MS Windows, которые осуществляют доступ к открытым файлам через хендлы:
// Write to child
DWORD written = 0;
if (!WriteFile(
hParentOutput, inputLine, len,
&written, NULL
))
break;
// Receive from child
DWORD numRead = 0;
if (
!ReadFile(
hParentInput, outputLine, 62,
&numRead, NULL
) ||
numRead == 0
)
break;
outputLine[numRead] = 0;
outputLine[63] = 0; // for safety
printf("%s", outputLine);
Процесс-ребенок использует хендлы входного и выходного потоков для чтения и записи. Чтение и запись выполняется с помощью функций ReadFile и WriteFile, доступ к потокам осуществляется через хендлы:
int main(int argc, char *argv[]) {
HANDLE hStdin, hStdout, hStderr;
hStdout = GetStdHandle(STD_OUTPUT_HANDLE);
hStdin = GetStdHandle(STD_INPUT_HANDLE);
hStderr = GetStdHandle(STD_ERROR_HANDLE);
if (
(hStdout == INVALID_HANDLE_VALUE) ||
(hStdin == INVALID_HANDLE_VALUE)
)
return(-1);
. . .
char line[256];
while (true) {
// Read from standard input.
DWORD numRead = 0;
BOOL fSuccess = ReadFile(
hStdin, line, 254, &numRead, NULL
);
if (!fSuccess || numRead == 0)
break;
line[numRead] = 0;
// Processing the line...
. . .
DWORD len = (DWORD) strlen(line);
DWORD written = 0;
// Write to standard output.
fSuccess = WriteFile(
hStdout, line, len, &written, NULL
);
if (!fSuccess)
break;
}
См. проект "WinPipe + Calculator": winpipe.cpp, rcalc.cpp.
Студенты с нечетными номерами по журналу делают первую задачу, с четными — вторую. В обеих задачах надо модифицировать (или просто подменить) файл rcalc.cpp, скомпилировав подмененный файл в исполняемую программу с именем "rcalc.exe". В проекте parent-процесс winpipe.exe запускает child-процесс rcalc.exe. Процесс-ребенок получает от процесса-родителя строку, каким-либо образом обрабатывает ее и отсылает обработанную строку обратно процессу-родителю. Процесс-родитель печатает полученный результат, так продолжается в бесконечном цикле (для выхода надо ввести пустую строку или букву 'q' (от слова quit).
child receives a line from a parent
parent a from line a receives child
56
fifty six
9
nine
70
seventy
В Unix работа с нитями описана в стандарте POSIX. Нить отождествляется с помощью переменной типа pthread_t. Для создания и старта нити используется системная функция pthread_create. Ей передается адрес функции, которую нить исполняет в процессе своей работы.
#include <pthread.h>
// Prototype of thread body function
void* run(void* arg);
int main() {
pthread_t thread1, thread2;
// Create the first thread
int res = pthread_create(
&thread1, // Thread identifier
NULL, // Thread attributes: defaults
&run, // Thread start function
(void *) heads // Parameter of thread function
);
. . .
}
void run(void* arg) {
// Thread function
. . .
}
Одна нить может ожидать завершения другой нити:
pthread_join(thread1, NULL);
Здесь нить, исполняющая эту команду, приостанавливается
до тех пор, пока нить thread1 не завершит свою работу.
В MS Windows нить, как и процесс, является объектом ядра системы и, как все объекты ядра, отождествляется значением типа HANDLE. Для создания нити используется системный вызов CreateThread. В приведенном ниже фрагменте программы создается нить, HANDLE которой помещается в переменную hThread1. Идентификатор нити (четырехбайтовое целое число) записывается в переменную threadID1. Нить исполняет функцию run.
#include <windows.h>
// Prototype of thread body function
DWORD WINAPI run(void* arg);
int main() {
HANDLE hThread1, hThread2;
DWORD threadID1, threadID2;
const char *arg1 = "Heads";
const char *arg2 = "Tails";
// Create the first thread
hThread1 = CreateThread(
NULL, // pointer to thread attributes
0, // stack size - default
&run, // thread starting function
(void *) arg1, // parameter of thread function
0, // creation flags
&threadID1 // pointer to threadID (out)
);
. . .
}
DWORD WINAPI run(void* arg) {
// Thread function
. . .
}
Для ожидания завершения нити используется системный вызов
WaitForSingleObject:
WaitForSingleObject(hThread1, INFINITE);
После завершения работы нити надо обязательно закрыть
ее HANDLE, иначе операционная система не освободит память,
которая используется под структуры данных, связанные с нитью.
CloseHandle(hThread1);
Различные вычислительные алгоритмы эфективно распараллеливаются с помощью нитей. Основная нить запускает несколько вспомогательных вычислительных нитей, каждая из которых проделывает свою часть общей работы. Основная нить должна дождаться завершения всех вычислительных нитей, после чего при необходимости вычислить общий ответ, используя результаты, полученные каждой вычислительной нитью.
Для примера рассмотрим вычисление интеграла от функции f(x) по отрезку [a, b]. Мы запускаем numThreads вспомогательных нитей, каждая из которых считает интеграл по своей части отрезка; здесь число нитей numThreads является параметром алгоритма. Нить с индексом i вычисляет интеграл по отрезку
Для вычисления интеграла по части отрезка одной нитью используется функция simpson(f, a, b, n), вычисляющая интеграл по формуле Симпсона:
double simpson(double (*f)(double), double a, double b, int n) {
assert(n > 0);
double h = (b - a)/n;
double s1 = (*f)(a) + (*f)(b);
double s2 = 0.;
double x = a + h;
for (int i = 0; i < n - 1; ++i) {
s2 += (*f)(x);
x += h;
}
double s4 = 0.;
x = a + h/2.;
for (int i = 0; i < n; ++i) {
s4 += (*f)(x);
x += h;
}
return (s1 + 2.*s2 + 4.*s4)*h/6.;
}
При запуске нитей мы передаем каждой нити указатель на ее блок аргументов:
class ArgBlock {
public:
double (*f)(double); // Function to integrate
double a; // Beginning of line segment
double b; // End of line segment
int n; // Number of sub-segments
double integral; // Result should be written here
};
Он содержит указатель на интегрируемую функцию, пределы интегрирования,
число отрезков разбиения, а также поле integral, куда нить должна записать
результат своей работы, т.е. интеграл по отрезку [a, b] от функции f(x),
вычисленный приближенно путем разбиения отрезка на n частей.
Функция работы нити у всех нитей одна и та же:
DWORD WINAPI computeIntegral(void* threadArgs) {
ArgBlock* args = (ArgBlock*) threadArgs;
double s = simpson(args->f, args->a, args->b, args->n);
args->integral = s;
return 0;
}
Нити создаются в цикле в функции main():
int k = n/numThreads;
if (k < 1)
k = 1;
double dx = (b - a)/numThreads;
for (int i = 0; i < numThreads; ++i) {
// Define arguments of i-th thread
threadArg[i].a = a + i*dx;
threadArg[i].b = threadArg[i].a + dx;
threadArg[i].n = k;
threadArg[i].f = &f;
// Create i-th thread
hThread[i] = CreateThread(
NULL, // lpThreadAttributes
0, // dwStackSize - default
&computeIntegral, // thread starting function
(void *) &(threadArg[i]), // parameter of thread starting function
0, // dwCreationFlags
&(threadID[i])
);
}
После этого основная нить программы дожидается завершения всех
нитей, вычисляющих интегралы по numThreads сегментам,
на которые разбит отрезок [a, b]:
// Wait until all threads finish.
WaitForMultipleObjects(
(DWORD) numThreads, // Number of threads
hThread, // Array of thread handles
TRUE, // Wait for all
INFINITE // Wait timeout: infinite
);
И затем суммируются интегралы по отрезкам разбиения,
вычисленные отдельными нитями:
// Compute the total integral as a sum of
// integrals for all segments
double s = 0.;
for (int i = 0; i < numThreads; ++i) {
s += threadArg[i].integral;
}
Большинство алгоритмов работы с матрицами очень хорошо распараллеливаются. Для примера мы рассмотрим самый основной алгоритм — приведение матрицы к ступенчатому виду методом Гаусса. Пусть в методе Гаусса в цикле необработанная часть (минор) матрицы a начинается со строки i и столбца j. Мы сканируем столбец j матрицы, начиная со строки i, в поиске максимального по модулю элемента. Пусть он содержися в строке k, где k≥i. Если он по модулю не превосходит eps, то мы считаем, что столбец нулевой, увеличиваем j и переходим к следующей итерации цикла. В противном случае мы при необходимости меняем строки i и k, чтобы максимальный элемент в столбце встал на место i. (При обмене строк мы меняем знак одной из строк, чтобы определитель матрицы остался инвариантным.) И затем мы из всех строк с номерами l>i вычитаем строку i, умноженную на коэффициент ali/aij. При этом элементы столбца j обнуляются, начиная со строки i+1. Алгоритм Гаусса реализован в файле matrix.cpp, функция
int gaussMethod(double *a, int m, int n); // Return a matrix rank
В алгоритме Гаусса распараллеливается обнуление столбца матрицы, начиная со строки i+1, с помощью элементарных преобразований второго рода — прибавления к строке l матрицы строки i, умноженной на число (-ali/aij), где индекс l строки пробегает значения от i+1 до m-1 (здесь m-1 — макимальный индекс строки матрицы, напомним, что индексы в программировании начинаются с нуля). Для разных строк элементарные преобразования можно выполнять параллельно. Например, пусть надо обработать 14 строк матрицы с индексами от 3 до 16. Пусть мы запустили 4 рабочие нити. Тогда первым трем нитям достаются для обработки по 4 строки каждой, последняя нить обработает 2 последние строки:
В параллельном алгоритме используется пул рабочих нитей, количество нитей является параметром алгоритма. Каждая нить ожидает своего задания и начинает его выполнять, как только получает от основной нити описание задания и команду на начало его выполнения. Для синхронизации нитей применяются объекты синхронизации типа События (Events), используются автоматически сбрасываемые события (auto-reset events). (В POSIX-версии программы используются семафоры, которые эквивалентны автоматически сбрасываемым событиям Win32, если значение семафора на превышает единицы.) Для каждой нити используются два объекта типа Event: первое событие hStartEvent переводится в сигнальное состояние, когда основная нить сформировала задание для рабочей нити и сигнализирует ей о том, что она должна начать работу. Таким образом, с помощью события hStartEvent передается информация от основной нити к рабочей. Второе событие hFinishEvent используется для передачи информации в обратном направлении, от рабочей нити к основной. Событие hFinishEvent переводится в сигнальное состояние рабочей нитью, когда она завершает выполнение задания. При этом рабочая нить не завершается, а в потенциально бесконечном цикле ожидает следующего задания.
Для управления каждой рабочей нитью используется блок аргументов:
class ThreadArgs {
public:
double* a; // Pointer to matrix elements
int rows; // Matrix dimension: rows,
int cols; // columns
int resolveRow; // Indices of resolution element: row,
int resolveCol; // column
int row0; // Initial row to process
int numRows; // Number of rows to process
HANDLE hStartEvent; // Event to start the work
HANDLE hFinishEvent; // Event that signals about finish of work
HANDLE hThread; // Thread handle
DWORD threadID; // Thread ID
bool terminate; // Request for suicide
};
Помимо хендлов событий, хендла и идентификатора нити,
он содержит также описание текущего задания для нити:
параметры матрицы, индексы разрешающего элемента в методе Гаусса,
номер начальной строки для обработки нитью и число строк,
которые она должна обработать, начиная с номера начальной строки.
Нить должна последовательно вычесть из строк с номерами
k=row0, row0+1, ..., row0+numRows-1 строку resolveRow, умноженную
на соответствующий коэффициент так, чтобы элемент k-й строки
в столбце resolveCol обнулился. Обозначим i=resolveRow,
j=resolveCol, тогда этот коэффициент равен
akj/aij. Каждая нить выполняет следующую
функцию:
DWORD WINAPI annihilateColumn(void* arg) {
ThreadArgs* threadArg = (ThreadArgs *) arg;
double* a = threadArg->a;
int m = threadArg->rows;
int n = threadArg->cols;
// printf("Thread started, ID=%d\n", threadArg->threadID);
while (true) {
WaitForSingleObject(
threadArg->hStartEvent,
INFINITE
);
if (threadArg->terminate) {
break;
}
assert(threadArg->numRows > 0);
int i = threadArg->resolveRow;
int j = threadArg->resolveCol;
double r = a[i*n + j];
int row0 = threadArg->row0;
int row1 = row0 + threadArg->numRows;
/*
printf(
"Thread ID=%d: process row0=%d, numRows=%d, i=%d, j=%d\n",
threadArg->threadID, row0, threadArg->numRows, i, j
);
*/
for (int k = row0; k < row1; ++k) {
double coeff = (-a[k*n + j]/r);
addMatrixRows(
a, m, n,
k, i, coeff
);
a[k*n + j] = 0.;
}
SetEvent(threadArg->hFinishEvent);
}
// printf("Thread terminated, ID=%d\n", threadArg->threadID);
return 0;
}
Здесь в начале цикла нить ожидает команду на выполнение очередного
задания: когда команда сформирована основной нитью, та переводит
событие threadArg->hStartEvent в сигнальное состояние, после чего
функция WaitForSingleObject завершается и нить начинает выполнять
тело цикла. По окончания выполнения тела цикла нить переводит
событие threadArg->hFinishEvent в сигнальное состояние, сообщая
основной нити о завершении задания.
Если при получении очередного задания флаг terminate в блоке аргументов установлен в true, то это означает команду на окончание работы. В ответ нить должна совершить самоубийство, выйдя из цикла и завершив выполнение ее основной функции annihilateColumn.
Для создания пула рабочих нитей используется функция initializeThreadPool:
void initializeThreadPool(
double *a, int m, int n,
int numThreads,
ThreadArgs* threadArgs
) {
for (int i = 0; i < numThreads; ++i) {
ThreadArgs* arg = &(threadArgs[i]);
arg->a = a;
arg->rows = m;
arg->cols = n;
arg->resolveRow = 0;
arg->resolveCol = 0;
arg->row0 = 0;
arg->numRows = 0;
arg->terminate = false;
arg->hStartEvent = CreateEvent(
NULL, // LPSECURITY_ATTRIBUTES - default
FALSE, // bManulReset is false => auto-reset
FALSE, // bInitialState - nonsignaled
NULL // pName is NULL => not named
);
arg->hFinishEvent = CreateEvent(
NULL, // LPSECURITY_ATTRIBUTES - default
FALSE, // bManulReset is false => auto-reset
FALSE, // bInitialState - nonsignaled
NULL // pName is NULL => not named
);
arg->hThread = CreateThread(
NULL, // lpThreadAttributes
0, // dwStackSize - default
&annihilateColumn, // thread starting function
(void *) arg, // parameter of thread starting function
0, // dwCreationFlags
&(arg->threadID)
);
}
}
В ней для каждой нити сначало инициализируются параметры заданий,
затем создаются два события для связи с основной нитью
(функции CreateEvent), и в конце нить создается с помощью
функции CreateThread.
Все нити завершаются в результате исполнения функции releaseThreadPool:
void releaseThreadPool(
int numThreads,
ThreadArgs* threadArgs
) {
HANDLE* activeThreads = new HANDLE[numThreads];
for (int i = 0; i < numThreads; ++i) {
threadArgs[i].terminate = true;
SetEvent(threadArgs[i].hStartEvent);
activeThreads[i] = threadArgs[i].hThread;
}
WaitForMultipleObjects(
numThreads,
activeThreads,
TRUE,
INFINITE
);
delete[] activeThreads;
for (int i = 0; i < numThreads; ++i) {
CloseHandle(threadArgs[i].hStartEvent);
CloseHandle(threadArgs[i].hFinishEvent);
CloseHandle(threadArgs[i].hThread);
}
}
Здесь для каждой нити сначала устанавливается в true
флаг terminate в ее блоке аргментов и затем
событие hStartEvent, на котором нить выполняет ожидание,
переводится в сигнальное состояние. В результате нить
должна завершить свою работу (выполнив самоубийство).
В функции WaitForMultipleObjects происходит ожидание
завершения всех нитей, после чего закрываются хендлы
всех объектов ядра, связанных с нитями.
Предлагается сделать одну из двух задач на тему параллельных вычислений с матрицами. Студенты с нечетными номерами делают задачу 1, с четными задачу 2. В качестве образца даются две программы.
Отметим, что мы представляем прямоугольную матрицу A размера m строк на n столбцов линейным массивом a, в котором элементы матрицы хранятся по строкам: сначала элементы строки с индексом 0, затем строки с индексом 1, в конце элементы строки с индексом m-1. Каждая строка содержит n чисел. Таким образом, элемент матрицы A в i-й строке и j-м столбце соответствует элементу линейного массива a с индексом i*n+j:
int parallelGaussMethod( // Return a matrix rank
double *a, int m, int n,
int numThreads = 4
);
bool parallelInverseMatrix(
const double *a, int n, // matrix n*n
double* inverse, // out: inverse matrix
int numThreads = 4 // number of working threads
);
bool parallelSolveLinearSystem(
const double *a, int n, // matrix n*n
const double* b, // column of free terms
double* x, // out: solution of the system a*x = b
int numThreads = 4 // number of working threads
);
При обращении нитей к общим статическим переменным обязательно требуется синхронизация. В противном случае возможна ситуация, когда нить, начавшая модификацию данных, прерывается системой еще до того, как она завершит критические операции. Данные остаются в некорректном состоянии, и их использование другой нитью может привести к ошибке.
Для синхронизации совместной работы нитей используются различные объекты синхронизации: мьютексы (mutex), критические секции, семафоры, условные переменные, атомарные счетчики и др.
Наиболее часто используется объект синхронизации mutex, от слов MUTual EXclusive — взаимно исключающий. Он служит для защиты критических данных. Мьютекс может принадлежать лишь одному процессу или нити. Нить или процесс, прежде чем начать модификацию или чтение критических данных, пытается сначала захватить мьютекс. Если он свободен (или уже принадлежит данной нити), то мьютекс захватывается нитью и помечается занятым; в противном случае нить приостанавливается до тех пор, пока другая нить, которой принадлежит мьютекс в данный момент, не освободит его. После захвата мьютекса нить может работать с критическими данными. По окончании работы нить освобождает мьютекс. Таким образом, использование мьютекса исключает одновременную работу с критическими данными двух и более нитей.
При работе с базами данных используется понятие транзакции — последовательности команд изменения критических данных, в процессе выполнения которой данные находятся в некорректном состоянии. Перед началом транзакции нить должна захватить мьютекс, а по окончании транзакции освободить его. Любая нить, обращающаяся к критическим данным, также должна перед обращением захватывать мьютекс, а после освобождать его. Благодаря этому доступ к данным, находящимся в некорректном состоянии, исключается.
Чтобы проиллюстрировать понятие мьютекса, можно привести следующие примеры "из жизни". Мьютексом может служить ключ от комнаты, в которую может войти только один человек (туалет и т.п.). Еще один красивый пример можно увидеть в фильме BBC о железных дорогах в Англии XIX века. Они были в основном однопутными и использовались попеременно поездами, движущимися в разных направлениях. Чтобы исключить встречное столкновение поездов, использовался так называемый Token (жетон, опознавательный знак), представлявший собой большое металлическое кольцо с латунным знаком на нем. Машинист поезда не имел право выехать на перегон между станциями, пока он не получал в свои руки это кольцо (его передавал машинисту дежурный по станции, когда поезд проходил мимо станции на малом ходу). Проехав перегон, машинист оставлял это кольцо на следующей станции, и потом встречный поезд привозил его обратно. Таким образом, кольцо защищало перегон между станциями и делало невозможным выезд на перегон одновременно двух поездов.
В современных операционных системах используются так называемые "рекурсивные" мьютексы: если нить уже владеет мьютексом и производит повторный его захват, то система не приостанавливает нить, а просто увеличивает счетчик числа его использований. Аналогично при исполнении команды освобождения мьютекса нитью счетчик уменьшается, и реально мьютекс освобождается, лишь когда счетчик становится равным нулю. Пусть, например, мы реализуем класс, который осуществляет какую-либо работу с критическими данными. Эти данные защищаются мьютексом. При исполнении метода данного класса, модифицирующего или просто читающего данные, сначала захватывается мьютекс, затем при завершении метода мьютекс освобождается. При этом в процессе выполнения метода могут вызываться другие методы того же класса, которые также захватывают тот же самый мьютекс. Если бы при попытке повторного захвата мьютекса нить переводилась бы в режим ожидания, то возникала бы ситуация ситуация Deadlock (смертельная блокировка): нить ожидает освобождения мьютекса, однако освободить его может только она сама. Но этого не происходит благодаря "рекурсивности" мьютекса.
Мьютексы бывают именованные и неименованные. Первые можно использовать для синхронизации процессов и нитей, вторые — только для синхронизации нитей. Рассмотрим лишь второй случай.
В OC Unix использование нитей и мьютексов описано в стандарте POSIX, программы, работающие с этими объектами, используют библиотеку pthread (первая буква "p" — от слова POSIX). Программы на C/C++ должны подключать стандартный заголовочный файл "pthread.h". Объект mutex имеет тип pthread_mutex_t, должен описываться как глобальный и размещаться в статической памяти. Для его инициализации используется специальная константа PTHREAD_MUTEX_INITIALIZER (для мьютексов, реализация которых может не быть рекурсивной) или PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP (для рекурсивных мьютексов). Например, в приведенном ниже фрагменте описан мьютекс, содержащийся в переменной mtx.
#include <pthread.h>
static pthread_mutex_t mtx =
PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP;
При использовании мьютекса нить сначала захватывает его, используя функцию pthread_mutex_lock, затем выполняет критические действия и после освобождает мьютекс с помощью функции pthread_mutex_unlock:
pthread_mutex_lock(&mtx);
// Критические действия
. . .
pthread_mutex_unlock(&mtx);
По окончании использования мьютекса нужно уничтожить его, освобождая тем самым системную память:
pthread_mutex_destroy(&mtx);
(Отметим, что при статической инициализации мьютекса с помощью константы PTHREAD_MUTEX_INITIALIZER или PTHREAD_RECURSIVE_MUTEX_INITIALIZER_NP системный объект типа мьютекс на самом деле создается и инициализируется при первом обращении к нему в функции pthread_mutex_lock. Можно также явно создать и инициализировать мьютекс, используя функцию pthread_mutex_init.)
В OC MS Windows (вернее, при использовании Win32 API) мьютекс, как и процесс, нить и т.п., является объектом ядра системы и отождествляется значением типа HANDLE. Мьютекс создается и инициализируется с помощью функции CreateMutex:
#include <Windows.h>
static HANDLE hMutex = NULL;
int main() {
. . .
hMutex = CreateMutex(
NULL, // default security attributes
FALSE, // initially not owned
NULL // unnamed mutex
);
if (hMutex == NULL) {
printf(
"Cannot create a mutex: error %d\n",
GetLastError()
);
exit(-1);
}
. . .
}
В Win32 все мьютексы рекурсивные. Для захвата мьютекса в MS Windows используется одна из двух универсальных функций ожидания, применимых ко всем объектам ядра системы, которые могут находиться в сигнальном и несигнальном состояниях. Это функции WaitForSingleObject и WaitForMultipleObjects. В первой функции задается лишь один объект и функция ожидает, когда он перейдет в сигнальное состояние (до этого момента исполнение нити приостанавливается). Во второй функции можно задать целый массив объектов, причем вызов ее имеет два варианта (которые задаются третьим параметром типа BOOL): в первом варианте (третий параметр FALSE) функция ждет, пока хотя бы один из указанных объектов перейдет в сигнальное состояние; во втором варианте (третий параметр TRUE) функция ждет до тех пор, пока все указанные объекты перейдут в сигнальное состояние. Последний аргумент функций ожидания задает таймаут в миллисекундах, специальная константа INFINITE используется для потенциально бесконечного ожидания. Вот прототипы функций ожидания:
DWORD WaitForSingleObject(
HANDLE hHandle,
DWORD dwMilliseconds
);
DWORD WaitForMultipleObjects(
DWORD nCount,
const HANDLE *lpHandles,
BOOL bWaitAll,
DWORD dwMilliseconds
);
Считается, что свободный мьютекс находится в сигнальном состоянии, захваченный — в несигнальном. Захват мьютекса выполняется с помощью функции WaitForSingleObject, освобождение — с помощью функции ReleaseMutex.
WaitForSingleObject(hMutex, INFINITE);
// Критические действия
. . .
ReleaseMutex(hMutex);
(Здесь для простоты мы опустили обработку статуса завершения функции WaitForSingleObject. Она может завершиться успешно и вернуть значение WAIT_OBJECT_0, при неудаче возвращается значение WAIT_FAILED, при завершении по таймауту — значение WAIT_TIMEOUT; если нить, владевшая мьютексом, завершилась аварийно, не освободив его — значение WAIT_ABANDONED.)
По окончании использования мьютекса нужно закрыть его хендл с помощью функции CloseHandle. Отметим еще раз, что в MS Windows так завершают работу с любыми объектами ядра системы (любые объекты ядра управляются через хендлы). Реально объект удаляется, только когда он становится никому не нужным, функция CloseHandle лишь уменьшает счетчик числа его использований:
CloseHandle(hMutex);
В теории программирования критической секцией с некоторым именем ("A", например) называется отмеченный данным именем участок кода, который в любой момент времени может исполняться только одной нитью или процессом. Если нить вошла в критическую секцию с именем "A", то любая другая нить при попытке войти в критическую секцию с тем же именем приостанавливается системой, пока первая нить не покинет критическую секцию. Одним и тем же именем могут быть помечены несколько участков кода, которые представляют одну и ту же критическую секцию.
Очевидно, что критические секции могут быть смоделированы с помощью мьютексов: критической секции с данным именем соответствует мьютекс, который надо захватывать при входе в критичекую секцию и освобождать при выходе. Тем не менее в MS Windows (точнее, в Win32 API) имеется специальный объект типа CRITICAL_SECTION, который используется для моделирования критических секций. Работа с ним чуть проще, чем с мьютексом, поскольку критические секции, в отличие от мьютексов, используются только для синхронизации нитей одного процесса, а именованные мьютексы могут использоваться и нитями разных процессов. К тому же вход в критичекскую секцию, выполняемый функцией EnterCriticalSection, в отличие от захвата мьютекса (функция WaitForSingleObject) не требует анализа возвращаемого значения. Благодаря этому при программировании с использованием Win32 API критические секции используются даже чаще, чем мьютексы.
Объект типа CRITICAL_SECTION описывается как глобальный в статической памяти. Перед первым использованием критическую секцию нужно инициализировать с помощью функци InitializeCriticalSection, а по окончании использования — удалить, использовав функцию DeleteCriticalSection:
#include <Windows.h>
static CRITICAL_SECTION critSect;
. . .
int main() {
InitializeCriticalSection(&critSect);
. . .
DeleteCriticalSection(&critSect);
return 0;
}
Вход в критическую секцию выполняется с помощью функции EnterCriticalSection; покидая критическую секцию, нить вызывает функцию LeaveCriticalSection:
EnterCriticalSection(&critSect);
// Критическая секция
. . .
LeaveCriticalSection(&critSect);
Семафоры, наряду с мьютексами и критическими секциями, являются одними из самых важных и популярных объектов синхронизации. Именно семафоры в первую очередь реализуются в любой операционной системе, внутренняя реализация других объектов синхронизации может использовать семафоры. Для реализации семафоров в современных процессорах предусмотрены специальные команды, такие, как атомарное увеличение или уменьшение счетчиков в памяти. (Слово "атомарное" означает, что выполнение команды не может быть приостановлено в результате аппаратного прерывания.)
Терминология восходит к семафорам на железных дорогах. Простейший семафор может находиться в двух состояниях: он может быть открыт (зеленый свет, сигнальное состояние) или закрыт (красный свет, несигнальное состояние). Поезд может пройти семафор только когда он открыт (на зеленый свет); при прохождении поезда семафор автоматически закрывается (загорается красный свет). Для открытия семафора ему нужно передать специальный сигнал (на железной дороге это происходит, когда поезд отойдет от семафора на значительное, заранее заданное расстояние). Если поезд подходит к семафору, когда он закрыт (красный свет), то поезд останавливается и ждет до тех пор, пока семафор не откроется.
Такой простейший семафор в компьютерах моделируется целочисленной переменной S, которая может принимать два значения: значение S=1 означает, что семафор открыт (сигнальное состояние); значение S=0 означает, что семафор закрыт. Нить, ждущая семафор, приостанавливается, если он не находится в сигнальном состоянии (т.е. если S=0). При переходе семафора в сигнальное состояние S=1 операционная система возобновляет работу нити, а значение семафора уменьшается на 1 (S снова становится равным нулю). Для перевода семафора в сигнальное состояние S=1 какая-нибудь нить должна выполнить специальную команду, увеличивающую значение S на единицу.
В общем случае семафор — это целочисленная переменная S, принимающая неотрицательные значения. При этом считается, что семафор закрыт, если значение S=0, и открыт, если значение S>0. Обычно программа пишется таким образом, что семафор S не может принимать значений, превосходящих заранее заданное максимальное значение M. (В Win32 API при создании семафора указывается его максимальное значение.) Каждая нить при ожидании и прохождении семафора уменьшает его значение на единицу. Можно рассмотреть следующую аналогию: имеется музей, работающий в зимнее время, и при нем гардероб, в котором 100 номерков. Посетитель музея должен сначала сдать верхнюю одежду в гардероб и получить номерок. Если номерки закончились, т.е. в музее уже 100 посетителей, то очередной посетитель ждет в гардеробе, пока кто-нибудь из предыдущих посетителей не сдаст номерок в гардероб и не получит назад свою одежду; только тогда новый посетитель сможет пройти в музей. Здесь значением семафора является текущее количество свободных номерков в гардеробе (начальное значение 100); каждый посетитель, проходящий в музей, уменьшает это значение на единицу; посетитель, покидающий музей, увеличивает значение на единицу. Значение семафора никогда не может превысить начального значения 100.
В Unix'е для описания семафора используется тип sem_t. Семафор создается с помощью функции sem_init. Пример:
#include <semaphore.h>
static sem_t mySemaphore;
. . .
int main() {
. . .
sem_init(
&mySemaphore, // semaphore
0, // shared between processes: No
1 // initial value: semaphore is open
);
. . .
}
Объект семафор чаще всего описывается как глобальный
в статической памяти. При создании семафора указывается
его начальное значение (1 в данном случае) и флаг,
определяющий, является ли семафор разделяемым между разными процессами
(в данном случае нет). Если семафор используется
разными процессами, то он должен быть помещен в разделяемую
память (shared memory). Если нет, то он используется для
синхронизации нитей, принадлежащих одному и тому же процессу.
По окончании использования семафор должен быть освобожден с помощью функции sem_destroy:
sem_destroy(&mySemaphore);
Нить увеличивает значение семафора на единицу с помощью функции sem_post:
sem_post(&mySemaphore);
Ожидание семафора выполняется с помощью функции
sem_wait:
sem_wait(&mySemaphore);
Если значение семафора больше нуля, то оно уменьшается
на единицу и нить продолжает работать. В противном
случае нить переводится в состояние ожидания, потенциально
бесконечного (вызов sem_wait в Unix'е не имеет таймаута).
Нить пробуждается, когда какая-либо другая нить выполнит
sem_post для данного семафора. Если блокировка нити в случае
нулевого значения семафора нежелательна, то можно использовать
функцию sem_trywait, которая завершается мгновенно, возвращая
ненулевое значение, если семафор был ненулевым
(в этом случае она уменьшает его значение на 1), или 0,
если семафор нулевой.
Файл "semExample.cpp" содержит пример программы, использующей семафоры для синхронизации нитей. Создаются две нити. Первая вводит строку с клавиатуры терминала и помещает ее в массив в статической памяти. После этого вторая нить инвертирует введенную строку и печатает перевернутую строку на экран. Эти действия повторяются в бесконечном цикле. Первая нить сообщает второй о том, что строка введена, с помощью семафора "inputReady". Вторая нить информирует первую о том, что она готова принять следующую строку, используя семафор "invertReady".
В Win32 API, в отличие от Unix, при создании семафора указывается его максимальнное значение. Пример:
static HANDLE hMySemaphore = NULL;
int main() {
. . .
// Initialize the semaphore
hMySemaphore = CreateSemaphore(
NULL, // default security attributes
8, // initial count
8, // maximal count
NULL // unnamed semaphore
);
. . .
}
Здесь создается семафор, допускающий одновременный
доступ к критической информации не более восьми нитей
(третий параметр функции). Семафор неименованный, т.е.
он может использоваться только нитями одного процесса.
Начальное значение семафора также равно 8. Возможен вариант,
когда начальное значение нулевое (семафор закрыт),
и можно его в подходящий момент открыть, увеличив
его на произвольное число (конечно, так, чтобы не превысить
заданный максимум). Пример:
// Initialize the semaphore
hMySemaphore = CreateSemaphore(
NULL,
0, // initial count: closed!
8, // maximal count
NULL
);
. . .
ReleaseSemaphore(
hMySemaphore, // handle to semaphore
8, // increase count by 8
NULL // do not need the previous count
);
Для ожидания семафора нить использует универсальную функцию WaitForSingleObject, применимую для всех объектов синхронизации. Пример:
WaitForSingleObject(hMySemaphore, INFINITE);
Второй параметр задает таймаут в миллисекундах, в данном
случае он бесконечный.
Для увеличения семафора используется функция ReleaseSemaphore; в отличие от Unix-функции sem_post, она может увеличить значение семафора на число, большее единицы — это число задается вторым параметром функции:
ReleaseSemaphore(
hMySemaphore, // handle to semaphore
1, // increase count by one
NULL // not interested in previous count
);
По окончании использования семафора мы закрываем его хендл:
CloseHandle(hMySemaphore);
При программировании под Win32 API гораздо чаще, чем семафоры, используются объекты синхронизации типа "Событие" (Event). По сути дела, события — это простейшие семафоры, принимающие только 2 значения: 0 и 1 (т.е. максимальное значение семафора ограничено единицей). Таким образом, объект типа событие может находиться лишь в двух состояниях: сигнальном (значение 1) и несигнальном (значение 0). Событие можно представлять себе как лампочку, которая может гореть (сигнальное состояние) или быть потушена (несигнальное). Можно представить себе кабинет врача в поликлинике и очередь пациентов, ожидающих приема. Когда врач освобождается и готов принять очередного пациента, он зажигает лампочку над дверью, что означает приглашение войти очередному пациенту. Потушенная лампочка означает, что врач занят.
Объекты "события" в MS Windows бывают двух типов: manual-reset events (события, сбрасываемые вручную) и auto-reset events (события, сбрасывающиеся автоматически). Семафоры соответствуют автоматическим событиям. Тип auto-reset означает, что, когда некоторая нить, ждавшая перехода события в сигнальное состояние, активизируется операционной системой, то событие автоматически переходит в несигнальное состояние. (Аналогия: когда поезд проходит зеленый семафор, то семафор автоматически переключатся на красный.) Автоматически сбрасываемое событие при переходе в сигнальное состояние всегда пробуждает только одну нить: если несколько нитей ждали события, то активизируется лишь одна из них (причем нельзя сказать, какая именно, порядок очереди FIFO здесь не гарантируется).
Сбрасываемые вручную события (manual-reset events), в отличие от автоматических, сохраняют свое сигнальное состояние и после пробуждения одной или нескольких нитей до тех пор, пока явно не будет вызвана функция ResetEvent, которая переводит событие в несигнальное состояние. Также существенное отличие от автоматических событий в том, что при переходе в сигнальное состояние сбрасываемое вручную событие активизирует все нити, которые его ждали (автоматическое событие пробуждает лишь одну из них).
Для работы с событиями используются следующие функции. CreateEvent создает объект типа событие, возвращая его хендл. Пример:
HANDLE hMyEvent;
. . .
hMyEvent = CreateEvent(
NULL, // LPSECURITY_ATTRIBUTES - default
FALSE, // bManulReset is false => auto-reset
FALSE, // bInitialState - nonsignaled
NULL // pName is NULL => not named
);
Здесь создается событие, сбрасываемое автоматически
(второй параметр FALSE), находящееся изначально
в несигнальном состоянии (третий параметр) и не
имеющее имени (четвертый параметр). Права доступа
к созданному объекту определяются по умолчанию
(первый параметр). Отсутствие имени у объекта означает,
что он может использоваться только нитями одного
процесса — того, который создал этот объект.
Это общее правило касается всех объктов синхронизации
(мьютексов, семафоров, событий и др.): если их
нужно использовать нитями разных процессов, то
они должны иметь глобальные имена, по которым
процессы их могут находить и использовать.
В частности, если именованный объект уже
существует (создан другим процессом), то
при вызове функции CreateEvent с указанием его имени
объект не создается заново, а текущий процесс
лишь открывает хендл для доступа к нему
(для открытия уже существующего именованного
события можно также использовать функцию OpenEvent).
Событие переводится в сигнальное состояние с помощью функции SetEvent:
SetEvent(hMyEvent);
Вызов функции SetEvent соответствует включению лампочки
(в англоязычной литературе часто используется
выражение "fire event", зажечь событие).
Можно также использовать функцию PulseEvent,
которая на мгновение переводит событие в сигнальное
состояние и тут же его сбрасывает обратно в несигнальное,
это соответствует однократному миганию лампочки.
При этом в случае автоматического события пробуждается
лишь одна нить из числа ждущих события, в случае
события, сбрасываемого вручную — все нити.
Функцию PulseEvent имеет смысл использовать лишь для события, сбрасываемого вручную (для автоматического события функции SetEvent и PulseEvent эквивалентны). Более того, Microsoft вообще не рекомендует больше использовать функцию PulseEvent (она оставлена в системе лишь для совместимости с предыдущими версиями), т.к. возможны некоторые ситуации, в которых она приводит к нежелательным последствиям (ждущая нить может не быть активизирована). Вместо этого рекомендуется для синхронизации использовать более новую технологию условных переменных (condition variables), которую мы здесь рассматривать не будем.
Перевод события в несигнальное состояние выполняется с помощью функции ResetEvent:
ResetEvent(hMyEvent);
(она, как правило, используется лишь для
событий, сбасываемых вручную).
Имеются разделяемые ресурсы и несколько процессов или нитей, которые с ними работают. При этом при захвате ресурса участником другие участники использовать его не могут, пока участник, им владеющий, не освободит его. В процессе такой работы может возникнуть ситуация, когда все участники ждут освобождения ресурсов и не могут ничего сделать. Это возникает при циклическом ожидании.
Например, есть 3 участника A, B, C.
Дейкстра, 1965, задача для студентов.
За круглым столом сидят 5 обедающих философов, между ними лежат 5 вилок. В середине стола блюдо со спагетти, для еды нужны 2 вилки. Каждый философ думает какое-то время, потом, когда проголодается, берет сначала левую вилку, если она свободна, затем правую вилку, если она свободна, затем ест какое-то время, после чего кладет обе вилки на стол, освобождая их.
Каждый философ выпоняет такие действия независимо от остальных. Оказывается, при этом может возникнуть deadlock, когда все философы взяли левую вилку и ждут, когда освободится правая.
Напишем программу, которая моделирует такую ситуацию. Каждому философу соответствует нить,которая исполняет его алгоритм:
цикл 50 раз выполнить
| подождать случайное время ≤ макс. время размышления
| захватить левую вилку
| подождать случайное время ≤ макс. время между захватами вилок
| захватить правую вилку
| поесть случайное время ≤ макс. время еды
| освободить левую вилку
| освободить правую вилку
конец цикла
Каждой вилке соответствует мьютекс. Захвату вилки соответствует команда
WaitForSingleObject(hMutex, INFINITE);
Освобождению вилки соответствует функция
ReleaseMutex(hMutex);
Случайные промежутки времени, в течение которых философ думает,
ест, промежуток между захватом левой вилки и попыткой захватить праву вилку
моделируются с помощью функции
Sleep(milliseconds);
Как философам избежать клинча (deadlock)? Можно ли каким-либо образом изменить порядок действий каждого отдельного философа за столом, чтобы deadlock не возникал?
Оказывается, можно, и такой алгоритм был предложен Dijkstra (Дайкстра, как правильно произносится его фамилия по-голландски, или Дейкстра, как обычно пишут его фамилию в русскоязычной литературе).
Основная причина возникновения deadlock состоит в циклическом ожидании:Следствие для задачи об обедающих фиософах. Deadlock не возникнет, если каждый философ сначала будет брать вилку с меньшим номером и затем вилку с большим номером.
То есть из 5-ти философов, сидящих за столом, философы с номерами 0, 1, 2, 3 сначала берут левую вилку и затем правую, и только философ 4 сначала берет правую вилку и затем левую.
Задача на дом: переделать программу обедающих философов "diningPhil.cpp" в соответствии с алгоритмом Дейкстры и проверить, что deadlock больше не возникает.
. . .
. . .
Пример простейшей программы Поставщик-Обработчик (Producer-Consumer), использующей нити, мьютексы и условные переменные из стандартной библиотеки STL языка С++11: "prodCons.cpp".
Параллельная реализация метода Гаусса приведения матрицы к ступенчатому виду, использующая условные переменные и нити из стандартной библиотеки STL: "parallelMatrixSTL.cpp".
. . .
Примеры сетевых программ:
Студенты с нечетными номерами по журналу решают задачу 1, с четными — задачу 2.
Заголовок ответа сервера записывать в файл не нужно!!! Только текст самой страницы.
Указание 1: берем программу "client.cpp" и модифицируем ее. Исправленная программа должна реализовать следующий диалог: после установки соединения переслать http-демону запрос
GET http://mech.math.msu.su/~vvb/Dush/OSDrafts2021.html HTTP/1.1 Host: mech.math.msu.su пустая строкаВ этом примере используется адрес страницы
HTTP/1.1 200 OK . . . Content-Length: 6136 . . . X-Pad: avoid browser bug Тест html-страницы (ОН ИДЁТ ПОСЛЕ ПУСТОЙ СТРОКИ, КОТОРОЙ ЗАКАНЧИВАЕТСЯ ЗАГОЛОВОК).Первая строка ответа сервера указывает статус запроса, в данном примере 200, что означает успех (коды 200-299). Коды 400-499 означают ошибку. Длина страницы указана в строке заголовка Content-Length.
Указание 2: Заголовок ответа сервера состоит из набора строк до пустой строки включительно. Для чтения и разбора заголовка удобно реализовать функцию "Прочесть строку из сокета", которая будет считывать строки заголовка ответа сервера одну за другой, пока не прочитает пустую строку. Прототип функции:
bool receiveLine(int s, char* line, int maxLen, int& len);s — номер открытого сокета, из которого мы читаем данные;
Функция возвращает true, когда всё нормально, и false, когда соединение разорвано.
Идея реализации функции receiveLine: читаем данные по одному байту, пока не встретим символ '\n', который означает конец строки. Этот символ мы выбрасываем из конца строки, а также при необходимости выбрасываем предыдущий символ '\r'.
bool receiveLine(int s, char* line, int maxLen, int& len) {
char buffer[2];
int n = 0;
while (n < maxLen) {
int res = recv(s, buffer, 1, 0);
if (res <= 0) {
return false;
}
if (buffer[0] == '\n')
break;
line[n] = buffer[0];
++n;
}
if (n > 0 && line[n-1] == '\r') {
// Remove CR at the end of line
--n;
}
line[n] = 0;
len = n;
return true;
}
Чат-клиент должен сначала спросить у человека адрес и порт сервера, затем какой порт он сам будет использовать. Ну и затем надо вводить сообщение с клавиатуры, посылать его серверу, потом принимать от сервера сообщения, которые он присылает каждому клиенту, в том числе и нам.
Указания: В чат-клиенте должна быть отдельная нить, которая занимается только чтением строк из сети (эти строки ей пересылает чат-сервер). Прочитанные строки добавляются в очередь принятых строк
std::deque<std::string> stringBuffer;
Чат-клиент сначал вводит строку с клавиатуры и отсылает ее серверу.
Затем он печатает все строки, полученные от сервера, который является
посредником между ним и другими чат-клиентами. Строки принимаются
параллельно в отдельной нити.
std::string lineToSend;
std::getline(lineToSend);
res = sendto(
s, lineToSend.data(), int(lineToSend.size()), 0,
(sockaddr*) &serverAddr, sizeof(serverAddr)
);
EnterCriticalSection(&critSect);
while (!stringBuffer.empty()) {
// Печатаем все принятые строки
std::string s = stringBuffer.front();
stringBuffer.pop_front();
std::cout << s << std::endl;
}
LeaveCriticalSection(&critSect);
Строки принимаются и складываются в очередь stringBuffer в отдельной нити,
которая исполняет следующую функцию:
DWORD WINAPI runReceiveThread(void*) {
char buffer[LINE_MAXLEN + 4];
// cout << "Receiving thread starts..." << endl;
while (!finished) {
sockaddr_in clientAddr;
int addLen = sizeof(clientAddr);
int res = recvfrom(
s, buffer, LINE_MAXLEN, 0,
(sockaddr*) &clientAddr, &addLen
);
// cout << "recvfrom: res = " << res << endl;
buffer[LINE_MAXLEN - 1] = 0;
if (res < 0) {
cout << "Cannot receive: err=" <<
WSAGetLastError() << endl;
break;
}
if (res > 0) {
buffer[res] =0;
// cout << "Received: " << buffer << endl;
// Add a new line to the queue
EnterCriticalSection(&critSect);
std::string s = buffer;
stringBuffer.push_back(s);
LeaveCriticalSection(&critSect);
}
}
cout << "Receive thread is ended" << endl;
return 0;
}
Зачем нужны файловые системы? У первых компьютеров их не было, данные непосредственно читались с диска (магнитной ленты, барабана и т.п.) в виде записей. Файловая система позволяет удобно огранизовать доступ к многообразным данным, расположенном на одном носителе. Файл — это набор данных, имеющий свое имя, с ним можно работать либо как с целостным объектом (создавать, удалять, перемещать, копировать, переименовывать и т.п.), либо читать или записывать его содержимое.
Отметим, что файл может отождествляться не только именем. Примером является ранняя версия файловой системы HFS компьютеров Apple Macintosh, в которой файл определялся двумя числами (стандартные диалоги открытия файлов возвращали именно пару чисел для доступа к файлу).
Прежде чем перейти к устройству файловых систем, рассмотрим, что представляет собой диск. У него есть пластины, у каждой пластины две поверхности и соответственно используются две считывающие головки. Информация записывается на дорожках, которые представляют собой концентрические окружности. Набор таких дорожек, расположенных друг над другом на разных пластинах и их поверхностях, обычно называют цилиндром. Каждая дорожка делится на сектора, стандартное число секторов 64 (они нумеруются с единицы, в отличие от цилиндров и головок). Чаще всего в одном секторе записывается 512 байтов. Сектор — минимальная единица записи и чтения для диска.
Раньше для адресации секторов на диске использовалась схема CHS — Cylinder, Head, Sector: для указания сектора нужно было указать номера силиндра, головки и сектора на дорожке. В современных дисках она заменена на схему LBA: Logical Block Address. В этой схеме каждый сектор получает свой собственный уникальный номер, начиная с нуля. Сектора нумеруются последовательно по цилиндрам и головкам. С этой точки зрения диск можно рассматривать просто как массив секторов, т.е. блоков размером в 512 байтов. Все современные контроллеры дисков используют логическую адресацию секторов LBA, скрывая от операционной системы детали физического устройства диска.
Для создания файловой системы надо придумать структуры данных, в которых хранятся имена файлов и каталогов (директорий), содержимое файлов, их атрибуты (тип файла, его собственник, группа, времена создания и модификации, права доступа к файлу и т.п.), а также данные, связанные с файловой системой в целом (число блоков и свободных блоков, точка монтирования, признак того, что файловая система была размонтирована корректно и т.п.). Также надо определить, в каком виде эта информация будет храниться в блоках диска или другого блокового устройства.
Отметим, что большинство современных файловых систем имеют иерархическую структуру: файлы хранятся в каталогах (или директориях), причем каталоги также могут вкладываться друг в друга. Обычно каталоги реализуются как файлы специального типа, которые хранят ссылки на другие файлы и каталоги.
В прошлом файловые системы часто хранили файлы в виде непрерывной последовательности блоков. Серьезным недостатком такого подхода является то, что после длительной работы, когда файлы многократно уничтожаются и создаются заново, свободное место на диске становится фрагментированным. В результате файл большого размера уже невозможно разместить на диске — нет достаточно большого свободного фрагмента, хотя в сумме свободного места может быть еще много. Приходилось выполнять опасные и длительные процедуры дефрагментации диска, в ходе которых информация переписывалась с места на место так, чтобы свободное пространство объединялось в один непрерывный фрагмент. При огромном количестве файлов на современных дисках подобное решение неприемлемо. Следовательно, блоки с содержимым файла могут располагаться на диске не подряд, и используемые структуры данных файловой системы должны это учитывать.
. . .