Взаимодействие процессов

Требования, выдвигаемые к механизму взаимодействия

1. Взаимоисключения
   • …
2. Прогресс
   • Когда ресурс свободен существует хотя бы один процесс, готовый его использовать, но особенность алгоритма синхронизации не позволяет ему это сделать
3. Отсутствие голодания
   • Должна быть невозможна ситуация, когда процесс неограниченно долго ожидает ресурса, из-за того что алгоритм синхронизации предоставляет ресурс другим процессам
4. Отсутствие тупиков
   • Должна быть невозможно ситуация, когда в некотором множестве процессов каждый процесс ждёт события, зависящего от исполнения другого процесса множества

Алгоритмы взаимоисключения

1. Замок (Глобально блокирующая переменная)

shared int lock = 0;

p_i() {
	// ... some code before
	
	while (lock);
	lock = 1;
	{critical section}
	
	lock = 0;
	
	// ... some code after
}

2. Строгое чередование

shared int turn = 0;

p_i() {
	// ... some code before
	
	while (turn != i);
	{critical section}
	
	turn = 1 - i;
	
	// ... some code after
}

3. Флаги готовности

shared int reads[2] = {0,0};

p_i() {
	// ... some code before
	
	ready[i] = i;
	while (reads[1-i]);
	{critical section}
	
	ready[i] = 0;
	
	// ... some code after
}

4. Алгоритм Петерсона

// some code before
shared int ready[2] = {0,0};
shared int turn = 0;

p_i() {
	// ... some code before
	ready[i] = 1;
	turn = 1 - i;
	
	while (turn != i && ready[1-i]);
	{critical section}
	
	ready[i] = 0;
	// ... some code after
}

5. Аппаратная поддержка взаимоисключений (spinlock)

shared int lock = 0;

p_i() {
	// ... some code before
	
	while test_and_set(&lock));
	{critical section}
	
	lock = 0;
	
	// ... some code after
}