Введение в разработку многопоточных приложений

Поморгаем int main() { while(true) { EnableLedOne(); DisableLedOne(); }

Поморгаем int Delay(int ms) { for(int i = 0; i < ms * k ; i++){} } int main() { while(true) { EnableLedOne(); Delay(300); DisableLedOne(); Delay(900); }

Одна лампочка t(мс)

Две лампочки t(мс)

Две лампочки t(мс) мс

Очередь заданий Task1, через 50мс Task2, через 100мс Task1, сейчас Task2, через 50мс Task2, сейчас t(мс)

Поморгаем с планировщиком void EnableLedOneTask() { EnableLedOne(); RegisterDelayedTask(DisableLedOneTask, 300); } void DisableLedOneTask() { DisableLedOne(); RegisterDelayedTask(EnableLedOneTask, 900); } int main() { RegisterDelayedTask(EnableLedOneTask, 0); RegisterDelayedTask(EnableLedTwoTask, 0); while(true) { Delay(50); ExecuteTaskByTime(); }

Sleep void LedOne () { while(true) { EnableLedOne(); Sleep(300); DisableLedOne(); Sleep(600); }

Sleep void LedOneThread() { B202 while(true) B203 { B204 EnableLedOne(); B205 Sleep(300); B207 DisableLedOne(); B208 Sleep(600); B209 } }

Sleep void LedOneThread() { int i = GetOnTime(); int j = GetOffTime(); while(true) { EnableLedOne(); Sleep(i); DisableLedOne(); Sleep(j); }

Стек и регистры j Регистры Стек i

Стек и регистры j Регистры Стек g h

Стеки и регистры Регистры i j Стек потока 1 i

Стеки и регистры Регистры Стек потока 2 g h j Стек потока 1 i g

Поток Физически – процедура потока, служебные данные и стек Логически – виртуальный процессор

Типы многопоточности Sleep() Поток 1Поток 2 t t

Типы многопоточности Кванты Sleep() Поток 1Поток 2 t t Квант кончился

Создание потоков WinAPI: CreateThread/TerminateThread.NET: class Thread static void Main(string[] args) { Thread thread = new Thread(DoA); thread.Start(); } static void DoA() { … }

Пул потоков WinAPI: QueueUserWorkItem.NET: class ThreadPool static void Main(string[] args) { ThreadPool.QueueUserWorkItem(DoA); } static void DoA(object state) { }

GUI void OnClick() { ThreadPool.QueueUserWorkItem(DoA); } void DoA(object state) { resultTextBox.Text = ComputeSmth(); }

GUI Очередь сообщений Поток окна Перерисуй окно Кликнули мышкой

GUI Очередь сообщений Поток окна Перерисуй окно Кликнули мышкой Обработай окончание вычисления

GUI static void DoA(object state) { _result = ComputeSmth(); resultTextBox.BeginInvoke(SetResult); } static void SetResult (object state) { resultTextBox.Text = _result; }

Проблемы многопоточности Проблемы корректности Проблемы живучести

Состояние гонки _i++; MOV EAX, [_ i ] INC EAX MOV [ _i ], EAX

«Одновременное» выполнение Поток 1 MOV EAX, [ i ] INC EAX MOV [ i ], EAX Поток 2 MOV EAX, [ i ] INC EAX MOV [ i ], EAX t

Многопроцессорная машина Процессор 1Процессор 2 Память Кэш 1Кэш 2 i = 2 i = 3

Многопроцессорная машина Процессор 1Процессор 2 Память Кэш 1Кэш 2 i = 2 i = 3 Когерентность кэша

Последовательное выполнение Поток 1 Enter() MOV EAX, [ i ] INC EAX MOV [ i ], EAX Exit() Поток 2 Enter() INC EAX MOV EAX, [ i ] MOV [ i ], EAX t

Критический регион … EnterCriticalRegion() _i++; LeaveCriticalRegion() …

Критический регион int taken = 0; void EnterCriticalRegion() { while(taken != 0) {} taken = 1; } void LeaveCriticalRegion() { taken = 0; }

Строгое чередование const int N = 2; int turn = 0; void EnterCriticalRegion (int i) { while (turn != i ) {} } void LeaveCriticalRegion (int i) { turn = (i + 1) % N; }

Алгоритм Петерсона(1981) bool flags[2]; int turn = 0; void EnterCriticalRegion (int i) { flags [ i ] = true ; turn = 1 - i ; while ( flags[1 - i] && turn != i ) {} } void LeaveCriticalRegion (int i) { flags [i] = false; }

CAS long CompareExchange(long *Destination, long Exchange, long Comparand); int taken = 0; void EnterCriticalRegion() { while( CompareExchange((&taken,1, 0)) {} } void LeaveCriticalRegion() { taken = 0; }

Interlocked Interlocked.Increment(ref _i);

Mutex static Mutex _mutex = new Mutex(); static void DoA(object state) { _mutex.WaitOne(); _i++; _mutex.ReleaseMutex(); }

Monitor void EnterCriticalRegion() { for(int i = 0; i < 1000 && ! CompareExchange((&taken,1, 0)) ; i++) {} if(taken == 0) { _mutex.WaitOne(); }

Monitor private static object _lockObject; static void DoA(object state) { lock(_lockObject) { ThreadUnsafeOperation(); } WinAPI: EnterCriticalSection/LeaveCriticalSection

Неблокирующая синхронизация

Фокус flags[i] = true; turn = 1 - i; while (flags[1 - i] && turn != i) { }

Фокус flags[i] = true; turn = 1 - i; int tmp1 = flags[1 - i] int tmp2 = turn != I …

Фокус flags[i] = true; int tmp1 = flags[1 - i] …

Фокус CPU1 flags[0] = true; int tmp1 = flags[1] … CPU2 flags[1] = true; int tmp1 = flags[0] …

Фокус CPU1 flags[0] = true; int tmp1 = flags[1] … CPU2 flags[1] = true; int tmp1 = flags[0] …

Многопроцессорная машина Процессор 1Процессор 2 Память Кэш 1Кэш 2 flags[0] = true flags[1] = true flags[0]=0 flags[1]=0 flags[0]=0 flags[1]=0

Фокус int tmp1 = flags[1 - i] flags[i] = true; …

Memory barrier flags[i] = true; Thread.MemoryBarrier(); int tmp1 = flags[1 - i] …

lock flags[i] = true; turn = 1 - i; lock (_object) { while (flags[1 - i] && turn != i) { }

Deadlock public static void Transfer(BankAccount a, BankAccount b, decimal amount) { lock (a) { if (a.m_balance < amount) throw new Exception("Insufficient funds."); lock (b) { a.m_balance -= amount; b.m_balance += amount; }

Deadlock Поток 1Поток 2 Lock(счет1)Lock(счет2) Lock(счет1) t

Банковский алгоритм public static void Transfer(BankAccount a, BankAccount b, decimal amount) { LockManager.LockAccounts(a, b) if (a.m_balance < amount) throw new Exception("Insufficient funds."); a.m_balance -= amount; b.m_balance += amount; }

Сортировка Поток 1Поток 2 Lock(счет1) Lock(счет2) Lock(счет1) Lock(счет2) t

Что почитать Concurrent Programming on Windows (Joe Duffy) CLR via C# (Jeffrey Richter ) Memory Barriers: a Hardware View for Software Hackers