Многопоточность в c#

183

09 марта 2022, 23:30

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

static void FindPaths (ulong x, ulong y) {
    if (x == width - 1 && y == height - 1) {
        count++;
        return;
    }
    if (x + 1 < width)
        FindPaths (x + 1, y);
    if (y + 1 < height)
        FindPaths (x, y + 1);
}

Вызывая FindPaths (0, 0), я получал правильный ответ. И тут я решил воспользоваться многопоточностью и начинать искать пути от клеток в первом столбце и последней строке: В конце концов у меня получился такой код:

static uint width;
static uint height;
static ulong count;
static List<System.Threading.Thread> threads = new List<System.Threading.Thread> ();
static void Main (string[] args) {
    do {
        Console.WriteLine ("Введите количество столбцов:");
    } while (!uint.TryParse (Console.ReadLine (), out width));
    do {
        Console.WriteLine ("Введите количество рядков:");
    } while (!uint.TryParse (Console.ReadLine (), out height));
    for (uint i = 1; i < height; i++) {
        threads.Add (new System.Threading.Thread (() => FindPaths (0, i)));
        threads[(int) i - 1].Start ();
    }
    for (uint i = 1; i < width; i++) {
        threads.Add (new System.Threading.Thread (() => FindPaths (i, 0)));
        threads[(int) i + (int) height - 2].Start ();
    }
    while (threads.Count (x => x.IsAlive) > 0)
        System.Threading.Thread.Sleep (10);
    Console.WriteLine ("Количество путей равно " + count + ".");
    Console.ReadKey ();
}
static void FindPaths (ulong x, ulong y) {
    if (x == width - 1 && y == height - 1) {
        count++;
        return;
    }
    if (y != 0 && x + 1 < width)
        FindPaths (x + 1, y);
    if (x != 0 && y + 1 < height)
        FindPaths (x, y + 1);
}

Но ответ выдаёт каждый раз разный и я не могу понять почему. У меня есть предположение, что x и y из разных потоков конфликтуют, но может быть у меня ошибка в коде. Заранее спасибо за помощь!

Answer 1

Это происходит из-за замыкания:

for (uint i = 1; i < height; i++) {
    threads.Add (new Thread(() => FindPaths (0, i))); // тут
    threads[(int) i - 1].Start ();
}

Этот код компилируется примерно в (тут можете посмотреть полную версию):

private sealed class <>c__DisplayClass4_0
{
    public uint i;
    internal void <Main>b__0()
    {
        FindPaths(0uL, i);
    }
}
<>c__DisplayClass4_0 <>c__DisplayClass4_ = new <>c__DisplayClass4_0();
<>c__DisplayClass4_.i = 1u;
while (<>c__DisplayClass4_.i < height)
{
    threads.Add(new Thread(new ThreadStart(<>c__DisplayClass4_.<Main>b__0)));
    threads[(int)(<>c__DisplayClass4_.i - 1)].Start();
    <>c__DisplayClass4_.i++;
}

Как видете у вас в потоках вызывается один и тот же метод (из одного и того же объекта), т.е. они все используют одну и туже переменную i. Исправить это можно, создав промежуточную переменную:

for (uint i = 1; i < height; i++) {
    var index = i;
    threads.Add (new System.Threading.Thread (() => FindPaths (0, index)));
    threads[(int) i - 1].Start ();
}

Тогда компилятор будет создавать каждый раз новый объект:

for (uint num = 1u; num < height; num++)
{
    <>c__DisplayClass4_0 <>c__DisplayClass4_ = new <>c__DisplayClass4_0();
    <>c__DisplayClass4_.index = num;
    threads.Add(new Thread(new ThreadStart(<>c__DisplayClass4_.<Main>b__0)));
    threads[(int)(num - 1)].Start();
}

Также у вас все потоки используют одну и туже переменную count. Операция ++ не атомарна и не потоко-безопасна. count = count + 1 тут идет одновременно чтение и запись и в теории, может произойти чтение старых данных (т.е. два потока прочитали 2 и оба же потока потом увеличили на 1 и записала 3). Лучше использовать Interlocked.Increment.

P.S. Вы каждый раз создаете новый поток, это достаточно "тяжелая" операция, возможно вам будет хватать потоков из ThreadPool.