Skip to content

Lecture 11-12.md

Latest commit

 

History

History
139 lines (125 loc) · 20.6 KB

Lecture 11-12.md

File metadata and controls

139 lines (125 loc) · 20.6 KB

Многопоточность

Виды параллелизации

  1. ILP - распараллеливание команд на 1 процессоре (всякие скедулеры)
  2. SIMD - например есть регистры по размеру как 4 int.
  3. Hyper-threading
  4. Multi core threading

Создаем поток

#include <thread>

int main() {
std::thread t([] {
std::cout << "Hello";
});
t.join(); //Дождись пока поток закончится
t.detach(); //Отвяжись от вызывающего потока (нужен редко)
}

Race condition

Осторожно, дальше псевдокод

int accounts[10000]

void transfer(size_t from, size_t to, int amount) {
if (accounts[from] < amount) {
throw runtime_error("in sufficient funds");
}
accounts[from] -= amount;
accounts[to] += amount;
}

Race condition - если результат работы нашей программы зависят от того в каком порядке выполняются потоки и в каком порядке скедулятся их команды, то программа некорректна

В многопоточном случае 2 потока могут проверить, что денег достаточно, и оба вычесть, а потом уйти в минус.
Ну и как заставить это работать? Например mutex

int accounts[10000]
std::mutex m;

void transfer(size_t from, size_t to, int amount) {
m.lock(); //Если залочен - ждет, когда разлочен - лочит
-//-
m.unlock(); //Разлочивает
}

Заметим что если полетит исключение, то останется залоченным навсегда

Спинлок - реализация mutex через просто while
Жрем цпу, ниче полезного не делаем, но быстро, потому что “уснуть” и “проснуться” не бесплатные операции, потому может быть полезен когда lock() применяется на очень маленький участок

int accounts[10000]
std::mutex m;

void transfer(size_t from, size_t to, int amount) {
std::lock_guard<std::mutex> lg(m); //Unlock в деструкторе
-//-
}

Операция называется атомарной, если мы не можем видеть ее промежуточных шагов (не может быть частично выполнена, а частично не выполнена)

Н-р (не факт что верно)

std::atomic<bool> locked;
locked.load(); //Атомарно получить
locked.store(smth); //Атомарно заменить
locked.exchange(smth);  //Атомарно заменить и вернуть преж
locked.compare_exchange(v1, v2); //Если locked не равно v1 - заменяет v1 на locked, если равно заменяет locked на v2. Возращает равно ли locked v1

Атомик гарантирует, что все что было до load выполнится до load, все что после - после

Но что-то у нас теперь не многопоточный код

void transfer(size_t from, size_t to, int amount) {
	std::lock_guard<std::mutex> lg(m[from]);
	std::lock_guard<std::mutex> lg(m[to]);
	-//-
}

Может быть deadlock (A -> B, B -> A) - бесконечное ожидание ресурсов потоками, которые сами жти ресурсы залочили

void transfer(size_t from, size_t to, int amount) {
	std::lock_guard<std::mutex> lg(m[min(from. to)]);
	std::lock_guard<std::mutex> lg(m[max(from, to)]);
	-//-
}

Уже не может - нет циклов

Количество поток ограничено только памятью, каждый поток требует стек (по умолчанию 4мб)

struct queue {
	void push(T val) {
		lock_guard<mutex> lg(m);
		q.push_back(move(val));
	}

<span class="token keyword">bool</span> <span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token keyword">const</span> <span class="token punctuation">{</span>
	lock_guard<span class="token operator">&lt;</span>mutex<span class="token operator">&gt;</span> <span class="token function">lg</span><span class="token punctuation">(</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> q<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>

T <span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
	lock_guard<span class="token operator">&lt;</span>mutex<span class="token operator">&gt;</span> <span class="token function">lg</span><span class="token punctuation">(</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token function">assert</span><span class="token punctuation">(</span><span class="token operator">!</span>q<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	T res <span class="token operator">=</span> <span class="token function">move</span><span class="token punctuation">(</span>q<span class="token punctuation">.</span><span class="token function">front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	q<span class="token punctuation">.</span><span class="token function">pop_front</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">return</span> res<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token keyword">mutable</span> mutex m<span class="token punctuation">;</span>
deque<span class="token operator">&lt;</span>T<span class="token operator">&gt;</span> q<span class="token punctuation">;</span>



}

Казалось бы - каждая функция многопоточная, в чем проблема? Если 2 потока делают if(!empty()) pop(), то оба могут попытаться удалить один и тот же элемент
Следовательно нужно изменить интерфейс

struct queue {
	-//-

<span class="token keyword">void</span> <span class="token function">push</span><span class="token punctuation">(</span>T val<span class="token punctuation">)</span> <span class="token punctuation">{</span>
	lock_guard<span class="token operator">&lt;</span>mutex<span class="token operator">&gt;</span> <span class="token function">lg</span><span class="token punctuation">(</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
	q<span class="token punctuation">.</span><span class="token function">push_back</span><span class="token punctuation">(</span><span class="token function">move</span><span class="token punctuation">(</span>val<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
	non_empty<span class="token punctuation">.</span><span class="token function">notify_all</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>	

T <span class="token function">pop</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
	unique_lock<span class="token operator">&lt;</span>mutex<span class="token operator">&gt;</span> <span class="token function">lock</span><span class="token punctuation">(</span>m<span class="token punctuation">)</span><span class="token punctuation">;</span>
	<span class="token keyword">if</span> <span class="token punctuation">(</span>q<span class="token punctuation">.</span><span class="token function">empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
		non_empty<span class="token punctuation">.</span><span class="token function">wait</span><span class="token punctuation">(</span>lock<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//Атомарно анлочит и начинает ждать, когда придет сигнал снова залочит</span>
	<span class="token punctuation">}</span>
	<span class="token operator">-</span><span class="token comment">//-</span>
<span class="token punctuation">}</span>

condition_variable <span class="token function">non_empty</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">mutable</span> mutex m<span class="token punctuation">;</span>
deque<span class="token operator">&lt;</span>T<span class="token operator">&gt;</span> q<span class="token punctuation">;</span>



}

Condition variable:

  1. wait(unique_lock) - залочиться и ждать
  2. notify_one() - разлочить кого-то одного
  3. notify_all() - разлочить всех

Печально только что мы будем всех, но только одному удается продолжить выполнение, остальные опять засыпают. Для этого и есть notify_one()