System Programming Windows

Синхронізація — Наскрізний Приклад та Deadlock Detection

Практична частина теми 06 — Dining Philosophers Problem, Thread-Safe Repository з fine-grained лocking, налагодження Deadlock у production через ProcDump та VS Debugger. Завершений наскрізний проєкт від А до Я.

Синхронізація: Наскрізний Приклад та Production Debugging

Dining Philosophers Problem: Класика Паралельного Програмування

Перш ніж будувати наскрізний приклад, варто розібрати Dining Philosophers Problem — класичну навчальну задачу, що демонструє всі проблеми синхронізації в одній постановці. Запропонована Е. Дейкстрою у 1965 році, вона досі є стандартним benchmark для перевірки алгоритмів синхронізації.

Постановка Задачі

П'ять філософів сидять за круглим столом. Між кожними двома філософами лежить по одній виделці — всього 5 виделок. Кожен філософ циклічно або думає, або їсть. Щоб їсти, потрібно взяти дві виделки — ліву і праву. Після їжі — покласти обидві.

      [Ф0]
   [В4]   [В0]
[Ф4]         [Ф1]
   [В3]   [В1]
      [Ф3]-[В2]-[Ф2]

Наївне рішення — deadlock: кожен бере ліву виделку → всі чекають на праву → deadlock.

Мета: реалізувати алгоритм де:

  • Deadlock неможливий
  • Starvation мінімізована (кожен філософ рано чи пізно поїсть)
  • Максимальний паралелізм (не просто "один за одним")

Рішення 1: Lock Ordering (Asymmetric Solution)

DiningPhilosophers_LockOrder.cs
using System;
using System.Threading;

class DiningPhilosophers_LockOrdering
{
    private const int Count = 5;
    private readonly object[] _forks = Enumerable.Range(0, Count)
        .Select(_ => new object())
        .ToArray();

    private volatile bool _running = true;
    private readonly long[] _mealCount = new long[Count];

    public void Run(CancellationToken ct)
    {
        var threads = Enumerable.Range(0, Count)
            .Select(i => new Thread(() => Philosopher(i)) { Name = $"Philosopher-{i}" })
            .ToList();

        threads.ForEach(t => t.Start());
        ct.WaitHandle.WaitOne();
        _running = false;
        threads.ForEach(t => t.Join(2000));

        PrintResults();
    }

    private void Philosopher(int id)
    {
        while (_running)
        {
            Think(id);
            Eat(id);
        }
    }

    private void Think(int id)
    {
        // Console.WriteLine($"[P{id}] думає..."); -- закоментуємо для чистоти
        Thread.Sleep(Random.Shared.Next(50, 200));
    }

    private void Eat(int id)
    {
        // ── LOCK ORDERING: менший індекс завжди береться першим ──
        // Для філософа N: ліва виделка = N, права = (N+1)%Count
        int leftFork  = id;
        int rightFork = (id + 1) % Count;

        // Глобальний порядок: завжди менший індекс → більший
        int firstFork  = Math.Min(leftFork, rightFork);
        int secondFork = Math.Max(leftFork, rightFork);

        // Філософ 4 (остання): його ліва=4, права=0
        // Без LockOrdering: він би брав fork4 → fork0 (різний порядок від решти)
        // З LockOrdering: firstFork=0, secondFork=4 (розриваємо circular wait!)

        lock (_forks[firstFork])
        {
            lock (_forks[secondFork])
            {
                // ── Їмо ──
                Interlocked.Increment(ref _mealCount[id]);
                Thread.Sleep(Random.Shared.Next(30, 100));
            }
        }
    }

    private void PrintResults()
    {
        Console.WriteLine("\n=== Dining Philosophers Results ===");
        for (int i = 0; i < Count; i++)
            Console.WriteLine($"  Philosopher-{i}: {_mealCount[i]} meals");

        long min = _mealCount.Min();
        long max = _mealCount.Max();
        Console.WriteLine($"  Min meals: {min}, Max meals: {max}");
        Console.WriteLine($"  Fairness ratio: {(double)min / max:P1}");
    }
}

Рішення 2: Resource Hierarchy (Monitor.TryEnter з jitter)

DiningPhilosophers_TryEnter.cs
class DiningPhilosophers_TryEnter
{
    private const int Count = 5;
    private readonly object[] _forks = Enumerable.Range(0, Count)
        .Select(_ => new object())
        .ToArray();

    private volatile bool _running = true;
    private readonly long[] _mealCount = new long[Count];
    private readonly long[] _retryCount = new long[Count];

    public void Run(CancellationToken ct)
    {
        var threads = Enumerable.Range(0, Count)
            .Select(i => new Thread(() => Philosopher(i)) { Name = $"Philosopher-{i}" })
            .ToList();

        threads.ForEach(t => t.Start());
        ct.WaitHandle.WaitOne();
        _running = false;
        threads.ForEach(t => t.Join(2000));

        PrintResults();
    }

    private void Philosopher(int id)
    {
        var rng = new Random(id * 42 + 7);

        while (_running)
        {
            Think(rng);

            // Retry loop з jitter — запобігає livelock
            bool ate = false;
            while (!ate && _running)
            {
                bool leftTaken = false, rightTaken = false;

                try
                {
                    Monitor.TryEnter(_forks[id], 0, ref leftTaken);
                    if (leftTaken)
                    {
                        Monitor.TryEnter(_forks[(id + 1) % Count], 0, ref rightTaken);
                        if (rightTaken)
                        {
                            Interlocked.Increment(ref _mealCount[id]);
                            Thread.Sleep(rng.Next(30, 80));
                            ate = true;
                        }
                    }
                }
                finally
                {
                    if (rightTaken) Monitor.Exit(_forks[(id + 1) % Count]);
                    if (leftTaken && !rightTaken) Monitor.Exit(_forks[id]);
                    else if (leftTaken && rightTaken) Monitor.Exit(_forks[id]);
                }

                if (!ate)
                {
                    Interlocked.Increment(ref _retryCount[id]);
                    Thread.Sleep(rng.Next(5, 25));  // рандомний jitter — запобігає livelock
                }
            }
        }
    }

    private void Think(Random rng) => Thread.Sleep(rng.Next(50, 150));

    private void PrintResults()
    {
        Console.WriteLine("\n=== TryEnter Solution Results ===");
        for (int i = 0; i < Count; i++)
            Console.WriteLine($"  Philosopher-{i}: {_mealCount[i]} meals, {_retryCount[i]} retries");
    }
}

Наскрізний Приклад: Thread-Safe In-Memory Repository

Побудуємо повноцінний thread-safe Repository для зберігання даних, що демонструє різні стратегії locking у реальному застосунку.

Крок 1: Модель та інтерфейси

Models.cs
namespace ThreadSafeRepo;

// Незмінна модель (immutable record — thread-safe за природою)
public sealed record Product(
    int Id,
    string Name,
    string Category,
    decimal Price,
    int Stock
);

// Команди оновлення (теж immutable)
public sealed record PriceUpdate(int ProductId, decimal NewPrice);
public sealed record StockAdjustment(int ProductId, int Delta);

// Статистика
public sealed record RepoSnapshot(
    int TotalProducts,
    decimal TotalValue,
    IReadOnlyDictionary<string, int> CountByCategory
);

Крок 2: Thread-Safe Repository

ProductRepository.cs
using System.Collections.Generic;
using System.Threading;

namespace ThreadSafeRepo;

/// <summary>
/// Thread-safe in-memory repository з двома рівнями lock granularity:
/// - _globalLock: для операцій що зачіпають структуру (Add/Remove/Snapshot)
/// - _priceLocks: fine-grained locks для оновлення ціни конкретного продукту
/// </summary>
public class ProductRepository
{
    private readonly Dictionary<int, Product> _products = new();
    private readonly object _globalLock = new object();

    // Fine-grained locks: окремий lock для ціни кожного продукту
    // Дозволяє оновлювати ціни різних продуктів паралельно
    private readonly Dictionary<int, object> _priceLocks = new();

    private long _readCount = 0;
    private long _writeCount = 0;

    // ─── Read Operations ─────────────────────────────────────────

    /// <summary>Отримати продукт за ID. Thread-safe читання.</summary>
    public Product? GetById(int id)
    {
        Interlocked.Increment(ref _readCount);

        // Dictionary не thread-safe → потрібен lock навіть для читання
        lock (_globalLock)
        {
            return _products.GetValueOrDefault(id);
        }
    }

    /// <summary>Отримати всі продукти категорії.</summary>
    public IReadOnlyList<Product> GetByCategory(string category)
    {
        Interlocked.Increment(ref _readCount);
        lock (_globalLock)
        {
            // Повертаємо копію! Не посилання на внутрішню колекцію.
            return _products.Values
                .Where(p => p.Category == category)
                .ToList()
                .AsReadOnly();
        }
    }

    // ─── Write Operations ─────────────────────────────────────────

    /// <summary>Додати або замінити продукт.</summary>
    public void AddOrUpdate(Product product)
    {
        Interlocked.Increment(ref _writeCount);
        lock (_globalLock)
        {
            _products[product.Id] = product;
            // Реєструємо fine-grained lock для нового продукту
            _priceLocks.TryAdd(product.Id, new object());
        }
    }

    /// <summary>
    /// Оновити ціну конкретного продукту.
    /// Використовує fine-grained lock: паралельне оновлення різних продуктів ✓
    /// </summary>
    public bool UpdatePrice(PriceUpdate update)
    {
        Interlocked.Increment(ref _writeCount);

        // Спочатку отримуємо fine-grained lock (без globalLock!)
        object? priceLock;
        lock (_globalLock)
        {
            _priceLocks.TryGetValue(update.ProductId, out priceLock);
        }

        if (priceLock is null) return false;

        // Оновлюємо ціну через fine-grained lock
        lock (priceLock)
        {
            lock (_globalLock)
            {
                if (!_products.TryGetValue(update.ProductId, out var current))
                    return false;

                if (update.NewPrice < 0) return false;

                // record: незмінний, тому "оновлення" = створення нового record
                _products[update.ProductId] = current with { Price = update.NewPrice };
                return true;
            }
        }
        // Інший потік може оновлювати _products[otherId] одночасно ✓
    }

    /// <summary>Скоригувати кількість на складі (delta може бути від'ємним).</summary>
    public bool AdjustStock(StockAdjustment adjustment)
    {
        Interlocked.Increment(ref _writeCount);
        lock (_globalLock)
        {
            if (!_products.TryGetValue(adjustment.ProductId, out var current))
                return false;

            var newStock = current.Stock + adjustment.Delta;
            if (newStock < 0) return false;  // ← atomic check-and-set за lock

            _products[adjustment.ProductId] = current with { Stock = newStock };
            return true;
        }
    }

    /// <summary>Bulk операція: застосувати список оновлень цін атомарно.</summary>
    public void BulkUpdatePrices(IEnumerable<PriceUpdate> updates)
    {
        // Для bulk операцій — один lock на весь блок → атомарно
        lock (_globalLock)
        {
            foreach (var u in updates)
            {
                if (_products.TryGetValue(u.ProductId, out var p))
                    _products[u.ProductId] = p with { Price = u.NewPrice };
            }
        }
    }

    // ─── Snapshot / Analytics ─────────────────────────────────────

    /// <summary>Консистентний знімок стану (atomic read of derived data).</summary>
    public RepoSnapshot GetSnapshot()
    {
        Interlocked.Increment(ref _readCount);
        lock (_globalLock)
        {
            // Всередині lock — всі читання консистентні
            var total = _products.Count;
            var value = _products.Values.Sum(p => p.Price * p.Stock);
            var byCategory = _products.Values
                .GroupBy(p => p.Category)
                .ToDictionary(g => g.Key, g => g.Count());

            return new RepoSnapshot(total, value, byCategory);
        }
    }

    public long ReadCount  => Interlocked.Read(ref _readCount);
    public long WriteCount => Interlocked.Read(ref _writeCount);
}

Крок 3: Симуляція навантаження

Program.cs
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Threading;
using System.Threading.Tasks;
using ThreadSafeRepo;

Console.OutputEncoding = System.Text.Encoding.UTF8;
Console.WriteLine("=== Thread-Safe Product Repository ===\n");

var repo = new ProductRepository();
using var cts = new CancellationTokenSource(TimeSpan.FromSeconds(10));

// ─── Seed initial data ─────────────────────────────────
var categories = new[] { "Electronics", "Clothing", "Food", "Books" };
for (int i = 1; i <= 50; i++)
{
    repo.AddOrUpdate(new Product(
        Id:       i,
        Name:     $"Product-{i:D3}",
        Category: categories[i % categories.Length],
        Price:    Random.Shared.Next(10, 1000),
        Stock:    Random.Shared.Next(5, 100)
    ));
}

Console.WriteLine($"Seeded {50} products\n");
var sw = Stopwatch.StartNew();

// ─── Concurrent workers ─────────────────────────────────

// 4 Readers: постійно читають різні продукти
var readers = Enumerable.Range(0, 4).Select(i => Task.Run(async () =>
{
    var rng = new Random(i * 7);
    long ops = 0;
    while (!cts.Token.IsCancellationRequested)
    {
        int id = rng.Next(1, 51);
        var product = repo.GetById(id);

        if (product is not null)
            _ = repo.GetByCategory(product.Category);

        ops++;
        await Task.Delay(rng.Next(1, 5), cts.Token).ConfigureAwait(ConfigureAwaitOptions.SuppressThrowing);
    }
    return ops;
})).ToList();

// 2 Price Updaters: оновлюють ціни
var priceUpdaters = Enumerable.Range(0, 2).Select(i => Task.Run(async () =>
{
    var rng = new Random(i * 13 + 17);
    long ops = 0;
    while (!cts.Token.IsCancellationRequested)
    {
        for (int j = 0; j < 5; j++)
        {
            int id = rng.Next(1, 51);
            decimal newPrice = rng.Next(5, 1500);
            bool ok = repo.UpdatePrice(new PriceUpdate(id, newPrice));
            if (ok) ops++;
        }
        await Task.Delay(rng.Next(10, 30), cts.Token).ConfigureAwait(ConfigureAwaitOptions.SuppressThrowing);
    }
    return ops;
})).ToList();

// 1 Stock Manager: коригує кількість на складі
var stockManager = Task.Run(async () =>
{
    var rng = new Random(99);
    long ops = 0;
    while (!cts.Token.IsCancellationRequested)
    {
        int id = rng.Next(1, 51);
        int delta = rng.Next(-10, 20);
        bool ok = repo.AdjustStock(new StockAdjustment(id, delta));
        if (ok) ops++;
        await Task.Delay(rng.Next(5, 15), cts.Token).ConfigureAwait(ConfigureAwaitOptions.SuppressThrowing);
    }
    return ops;
});

// 1 Analytics: знімає snapshot кожну секунду
var analytics = Task.Run(async () =>
{
    while (!cts.Token.IsCancellationRequested)
    {
        await Task.Delay(1000, cts.Token).ConfigureAwait(ConfigureAwaitOptions.SuppressThrowing);
        if (cts.Token.IsCancellationRequested) break;

        var snap = repo.GetSnapshot();
        Console.WriteLine(
            $"[t={sw.Elapsed.TotalSeconds:F0}s] " +
            $"Products: {snap.TotalProducts} | " +
            $"TotalValue: {snap.TotalValue:C0} | " +
            $"Reads: {repo.ReadCount:N0} | " +
            $"Writes: {repo.WriteCount:N0}");

        foreach (var (cat, count) in snap.CountByCategory.OrderBy(x => x.Key))
            Console.WriteLine($"  {cat}: {count} products");
    }
});

await Task.WhenAll(readers.Concat(priceUpdaters).Append(stockManager).Append(analytics));

Console.WriteLine($"\n=== Завершено ===");
Console.WriteLine($"Total Reads:  {repo.ReadCount:N0}");
Console.WriteLine($"Total Writes: {repo.WriteCount:N0}");
Console.WriteLine($"Duration: {sw.Elapsed.TotalSeconds:F2}s");

Крок 4: Збірка та запуск

dotnet new console -n ThreadSafeRepo
# Скопіюйте Models.cs, ProductRepository.cs, Program.cs
dotnet run
Thread-Safe Repository
=== Thread-Safe Product Repository ===
Seeded 50 products
[t=1s] Products: 50 | TotalValue: $1,247,830 | Reads: 1,842 | Writes: 413
Books: 12 products
Clothing: 13 products
Electronics: 13 products
Food: 12 products
[t=2s] Products: 50 | TotalValue: $1,198,441 | Reads: 3,701 | Writes: 829
...
=== Завершено ===
Total Reads: 18,472
Total Writes: 4,183
Duration: 10.04s

Deadlock Detection у Production

Інструменти

Реальний production deadlock — найстрашніший баг: program "завис", CPU близько до нуля, але процес не завершується. Ось набір інструментів для діагностики.

Метод 1: Аналіз через dotnet-dump

# Встановлення
dotnet tool install --global dotnet-dump

# Збір dump-у живого процесу
dotnet-dump collect --process-id <PID>

# Аналіз
dotnet-dump analyze <dump-file>

# Внутрішні команди аналізатора:
# clrthreads             — список всіх managed потоків
# clrstack               — call stack поточного потоку
# parallelstack           — стеки всіх потоків одночасно
# syncblk                — таблиця syncblocks (хто тримає які locks)

Приклад виводу syncblk при deadlock:

Index SyncBlock MonitorHeld Recursion Owning Thread Info          SyncBlock Owner
  12  0x7f8a..  1           1         0x7f8b.. 12  MDB.Thread-1   0x7f1a {BankAccount}
  13  0x7f8c..  1           1         0x7f8d.. 14  MDB.Thread-2   0x7f1b {BankAccount}
# Thread 12 тримає 0x7f1a, Thread 14 тримає 0x7f1b
# clrstack для кожного покаже що вони чекають ДРУГий lock → Circular Wait!

Метод 2:Timeout-Based Detection у Коді

DeadlockDetector.cs
using System.Threading;
using System.Diagnostics;

/// <summary>
/// Production-ready helper для виявлення потенційних deadlock-ів через timeout.
/// Не заміняє профайлер, але допомагає в early detection.
/// </summary>
public static class LockHelper
{
    /// <summary>
    /// Виконати дію в критичній секції з таймаутом.
    /// Якщо lock не отримано за maxWait — кидає DeadlockSuspectException.
    /// </summary>
    public static T RunWithTimeout<T>(
        object lockObject,
        Func<T> action,
        TimeSpan maxWait,
        string operationName = "UnknownOperation")
    {
        bool lockTaken = false;

        try
        {
            Monitor.TryEnter(lockObject, maxWait, ref lockTaken);

            if (!lockTaken)
            {
                // Збираємо діагностичну інформацію
                var stackTrace = new StackTrace(true).ToString();

                throw new TimeoutException(
                    $"[DeadlockSuspect] Операція '{operationName}' не змогла отримати lock " +
                    $"за {maxWait.TotalSeconds:F1}s. Можливий deadlock!\n" +
                    $"Stack trace:\n{stackTrace}");
            }

            return action();
        }
        finally
        {
            if (lockTaken) Monitor.Exit(lockObject);
        }
    }

    // Перевантаження для void
    public static void RunWithTimeout(
        object lockObject,
        Action action,
        TimeSpan maxWait,
        string operationName = "UnknownOperation")
        => RunWithTimeout(lockObject, () => { action(); return 0; }, maxWait, operationName);
}

// Використання:
var _lock = new object();

LockHelper.RunWithTimeout(
    lockObject: _lock,
    action: () =>
    {
        // критична секція
        _balance -= amount;
    },
    maxWait: TimeSpan.FromSeconds(5),
    operationName: "TryWithdraw"
);

Метод 3: Watchdog Thread

WatchdogThread.cs
using System;
using System.Diagnostics;
using System.Threading;

/// <summary>
/// Watchdog: окремий потік що моніторить підозрілі lock-очікування.
/// При виявленні довгого очікування — логує стеки всіх потоків.
/// </summary>
public class LockWatchdog : IDisposable
{
    private readonly TimeSpan _threshold;
    private readonly Thread _watchdog;
    private volatile bool _running = true;

    public LockWatchdog(TimeSpan threshold)
    {
        _threshold = threshold;
        _watchdog = new Thread(WatchdogLoop)
        {
            IsBackground = true,
            Name = "LockWatchdog",
            Priority = ThreadPriority.AboveNormal
        };
        _watchdog.Start();
    }

    private void WatchdogLoop()
    {
        while (_running)
        {
            Thread.Sleep(_threshold);

            // Перевіряємо процес: задіяний CPU і є заблоковані потоки?
            using var proc = Process.GetCurrentProcess();
            var managedThreads = proc.Threads.Cast<ProcessThread>()
                .Where(t => t.ThreadState == System.Diagnostics.ThreadState.Wait)
                .Count();

            if (managedThreads > Environment.ProcessorCount * 2)
            {
                Console.Error.WriteLine(
                    $"[Watchdog] ⚠️ Підозріла кількість заблокованих потоків: {managedThreads}. " +
                    $"Можливий deadlock. Рекомендується: dotnet-dump collect --pid {proc.Id}");
            }
        }
    }

    public void Dispose() { _running = false; }
}

Реентерабельність (Reentrancy) та Рекурсивний lock

Що Таке Реентерабельний Lock

Monitor (і відповідно lock) у .NET є реентерабельним (reentrant): якщо потік вже тримає lock і намагається захопити той самий lock знову — він не блокується:

Reentrancy.cs
private readonly object _lock = new();

public void MethodA()
{
    lock (_lock)
    {
        Console.WriteLine("MethodA: отримав lock");
        MethodB();  // ← рекурсивний lock! Той самий потік, той самий _lock
    }   // ← lock звільняється лише тут (після виходу з останнього lock)
}

public void MethodB()
{
    lock (_lock)  // потік вже тримає _lock → не блокується!
    {
        Console.WriteLine("MethodB: також всередині lock (re-entrant!)");
    }
    // Monitor.Exit викликається. Але lock НЕ звільняється поки не вийдемо з MethodA
    // CLR підраховує recursion count (глибину рекурсії)
}

Monitor (і lock) підтримує recursion counting: він рахує скільки разів поточний потік захопив lock і звільнює його тільки коли кількість Enter == кількість Exit.

System.Threading.Lock (новий у .NET 9) навмисно не підтримує reentrancy — щоб виявляти потенційні баги (рекурсивне захоплення часто є ознакою неправильного дизайну). Якщо потрібна рекурсія — Monitor/object lock.

Підсумок

Dining Philosophers

  • Lock Ordering (asymmetric): розриває Circular Wait
  • TryEnter + jitter: усуває No Preemption, запобігає livelock
  • Жодне рішення не є ідеальним — компроміс між складністю і fairness

Fine-Grained Locking

  • Coarse-grained: простий, безпечний, низький паралелізм
  • Fine-grained: складніший, вищий паралелізм, ризик deadlock
  • Repository патерн: globalLock для структури + priceLock для запису

Production Debugging

  • dotnet-dump collect + syncblk → видно хто тримає які locks
  • LockHelper.RunWithTimeout → TimeoutException замість вічного hang
  • Watchdog thread → автоматичне виявлення підозрілих ситуацій

Reentrancy

  • Monitor/lock — reentrant (recursion counting)
  • Lock (.NET 9) — intentionally non-reentrant
  • Рекурсивний lock часто = ознака поганого дизайну

Практичні Завдання

Рівень 1: Thread-Safe Inventory

Реалізуйте thread-safe InventoryManager:

  • AddItem(string sku, int quantity) — додати або поповнити
  • ReserveItem(string sku, int quantity) — забронювати (повертає false якщо недостатньо)
  • FulfillReservation(string sku, int quantity) — підтвердити відвантаження
  • Тест: 10 потоків одночасно резервують і поповнюють — кількість ніколи не стає від'ємною

Рівень 2: Dining Philosophers Comparison

Реалізуйте обидва рішення Dining Philosophers (Lock Ordering та TryEnter+jitter):

  1. Запустіть обидва на 30 секунд
  2. Виміряйте: total meals, min meals, fairness ratio (min/max)
  3. Виміряйте: CPU usage, retry count
  4. Зробіть висновок який підхід краще і чому

Рівень 3: Deadlock Simulation та Fix

  1. Створіть ThreadSafeTransfer між двома BankAccount об'єктами
  2. Навмисно викличте deadlock (два потоки, зворотній порядок lock)
  3. Підтвердіть deadlock через dotnet-dump syncblk або timeout
  4. Виправте через Lock Ordering
  5. Виправте через Monitor.TryEnter з timeout і retry
  6. Порівняйте обидва рішення по throughput