Многопоточное программирование. 1. Алгоритм Петерсона... чуть более подробно

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

#define FALSE 0
#define TRUE 1
#define N 2 // количество процессов

int turn; // чья очередь
int interested[N];   // изначально значения равны 0

void enter_region(int process) // номер процесса - 0 или 1
{
  int other;
  other = 1 - process;    // точка 1
  interested[process] = TRUE;  // точка 2 (заинтересованный процесс)
  turn = process;         // точка 3
  while(turn == process && interested[other] == TRUE); // активное ожидание
}

void leave_region(int process) // номер процесса - 0 или 1
{
  interested[process] = 0; // признак выхода из критической секции
}

Итак, turn и interested[] являются глобальными переменными, прочие
переменные - локальные.
Случай 1: переключение процессов возникло в точке 1

Процесс 0	Процесс 1
other = 1
Прерывание процесса 0, переключение на процесс 1
	other = 0, interested[1] = TRUE, turn = 1
	Проверка условий turn == 1 (true) и interested[0] == TRUE (false)
	Вход в критическую секцию
	Прерывание процесса 1, переключение на процесс 0
interested[0] = TRUE, turn = 0
Проверка условий turn == 0 (true) и interested[1] == TRUE (true)
Вход в бесконечный цикл, переключение на процесс 1
	Процесс 1 выходит из критической секции и устанавливает interested[1] = FALSE
	Прерывание процесса 1, переключение на процесс 0
Проверка условий turn == 0 (true) и interested[1] == TRUE (false)
Вход в критическую секцию

Случай 2: переключение процессов возникло в точке 2

Процесс 0	Процесс 1
other = 1, interested[0] = TRUE
Прерывание процесса 0, переключение на процесс 1
	other = 0, interested[1] = 1, turn = 1
	Проверка условий turn == 1 (true) и interested[0] == TRUE (true)
	Вход в бесконечный цикл, переключение на процесс 0
turn = 0
Проверка условий turn == 0 (true) и interested[1] == 1 (true)
Вход в бесконечный цикл, преключение на процесс 1
	Проверка условий turn == 1 (false) и interested[0] == 1 (true)
	Вход в критическую секцию
	Прерывание процесса 1, переключение на процесс 0
Проверка условий turn == 0 (true) и interested[1] == 1 (true)
Вход в бесконечный цикл, преключение на процесс 1
	Процесс 1 выходит из критической секции и устанавливает interested[1] = FALSE
	Прерывание процесса 1, переключение на процесс 0
Проверка условий turn == 0 (true) и interested[1] == 1 (false)
Вход в критическую секцию

Случай 3: переключение процессов возникло в точке 3

Процесс 0	Процесс 1
other = 1, interested[0] = TRUE, turn = 0
Прерывание процесса 0, переключение на процесс
	other = 0, interested[1] = TRUE, turn = 1
	Проверка условий turn == 1 (true) и interested[0] == TRUE (true)
	Вход в бесконечный цикл, преключение на процесс 0
Проверка условий turn == 0 (false) и interested[1] == TRUE (true)
Вход в критическую секцию
Прерывание процесса 0, переключение на процесс
	Проверка условий turn == 1 (true) and interested[0] == TRUE (true)
	Вход в бесконечный цикл, преключение на процесс 0
Процесс 0 выходит из критической секции и устанавливает interested[0] = FALSE
Прерывание процесса 0, переключение на процесс
	Проверка условий turn == 1 (true) и interested[0] == TRUE (false)
	Вход в критическую секцию

Продолжение следует...

Особенности выравнивания данных в структурах

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

struct Test
{
 char var1; // 1 байт
 short var2; // 2 байта
};

Как видно, суммарный размер структуры должен быть равен 3 байтам, на деле же оказывается вовсе не 3, а 4 байта.
Именно такой результат возвратит нам sizeof(Test). Все дело в выравнивание, которое осуществляет компилятор.
Т.е. данные помещаются по адресам, кратным размерам своих типов - 2-байтовые данные буду находятся по адресу, кратному 2, 4-байтные - по адресу, кратному 4 и т.д. (выравнивание по умолчанию)
Выравнивание нужно, потому что с выровненными данными процессор работает более эффективно. Если процессор обращается к невыровненным данным, то сначала он считывает одну часть данных, затем считывает другую часть, после этого компонует и получает исходные данные. Все это сокращает производительность.
Для выравнивания между данными помещаются специальные байты отступа (padding)

Рассмотрим примеры (ОС Windows).

struct Test
{
    unsigned char var1;
    unsigned char var2;
    unsigned char var3;
};

0	1	2	3	4	5	6	7	8
char	char	char	...

В данном примере все просто. 3 однобайтовых данных выравниваются по однобайтовой границе.
В итоге суммарный размер равен 3 байта.

Другой пример:

struct Test
{
    unsigned char var1;
    unsigned short var2;
};

0	1	2	3	4	5	6	7	8
char	P	short		...

Здесь данные типа short будут выровнены по 2-байтовой границе, для этого будет использован отступ в 1 байт. Поменяем местами данные следующим образом:

struct Test
{
    unsigned short var1;
    unsigned char var2;
};

0	1	2	3	4	5	6	7	8
short		char	P	...

В данном примере байт отступа будет использоваться для дополнения последнего члена структуры до размера, кратного максимальному размеру члена, т.е. до 2 байт. Таким образом, 1 байт на char + 1 байт на отступ = 2 байта (short)
Допустим у нас есть такая структура:

struct Test
{
    unsigned int var1;
    unsigned char var2;
};

0	1	2	3	4	5	6	7	8	9	10
int				char	P	P	P	...

В данном случае в структуре присутствуют данные с максимальным размером 4 байта (int), следовательно последний член структуры необходимо дополнить до ближайшего кратного 4 числа, большего 1 (т.к. char), т.е. до 4 байтов. Для этого потребуется 3 байта для отступа.

Если имеется структура

struct Test
{
    unsigned int var1;
    unsigned short var2;
    unsigned char var3;
};

0	1	2	3	4	5	6	7	8	9	10
int				short		char	P	...

В данном случае член типа short не дополняется до размера int, потому что следом идет член типа char, который не требует выравнивания по 4-байтной границе. А после этого члена для выравнивания до 4 байт (число, кратное максимальному размеру типа в данной структуре (int) - 4 байта)

Аналогично рассмотрим структуру вида

struct Test
{
 double var1;
 unsigned int var2;
 unsigned short var3;
 unsigned char var4;
};

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
double								int				short		char	P	...

Член типа double занимает как есть 8 байт, далее 4 байта на int, после которого байты отступа не требуются, т.к. граница выровнена уже по 4 байтам, а идущий следом член типа short требует всего лишь 2-байтового выравнивания. Затем один байт на char и байт отступа для выравнивания по числу, кратному размеру максимального типа (double), т.е. 16.

Представим такую ситуацию:

struct Test
{
    unsigned short var1;
    unsigned char var2;
    double var3;
};

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18
short		char	P	P	P	P	P	double								...

В данном примере данное типа char дополняется 1 байтом отступа до размера short, но далее идет член типа double, его рамер равен 8 байтами, поэтому он должен выравниваться по 8-байтовой границе. Следовательно отступ увеличивается еще на 4 недостающих байта.

ВНИМАНИЕ! Данные результаты получены при опции компилятора
Struct member alignment = Default;
Для значений /zp1, /zp2, zp[n] результаты будут отличны от полученных.