فیلسوفان خوب تغذیه یا برنامه نویسی رقابتی دات نت

بیایید ببینیم برنامه‌نویسی همزمان و موازی در Net چگونه کار می‌کند و از مسئله غذاخوری فیلسوفان به عنوان مثال استفاده می‌کنیم. طرح این است، از همگام سازی نخ ها / فرآیندها، تا مدل بازیگر (در قسمت های بعدی). مقاله ممکن است برای اولین آشنایی یا به منظور تجدید دانش شما مفید باشد.

اصلا چرا این کار را بکنم؟ ترانزیستورها به حداقل اندازه خود می رسند، قانون مور بر محدودیت سرعت نور استوار است و بنابراین افزایش در تعداد مشاهده می شود، ترانزیستورهای بیشتری می توان ساخت. در عین حال، حجم داده ها در حال افزایش است و کاربران انتظار پاسخ فوری از سیستم ها را دارند. در چنین شرایطی، برنامه نویسی "عادی"، زمانی که یک رشته اجرایی داریم، دیگر کارایی ندارد. شما باید به نحوی مشکل اجرای همزمان یا همزمان را حل کنید. علاوه بر این، این مشکل در سطوح مختلف وجود دارد: در سطح رشته ها، در سطح فرآیندها، در سطح ماشین های موجود در شبکه (سیستم های توزیع شده). دات نت دارای فناوری های باکیفیت و تست شده برای حل سریع و کارآمد چنین مشکلاتی است.

کار

Edsger Dijkstra این مشکل را در اوایل سال 1965 برای دانش آموزان خود مطرح کرد. فرمول ایجاد شده به شرح زیر است. تعداد معینی (معمولاً پنج) فیلسوف و به همان تعداد چنگال وجود دارد. آنها در یک میز گرد می نشینند و بین آنها چنگال می زنند. فیلسوفان می توانند از بشقاب های خود غذای بی پایان بخورند، فکر کنند یا منتظر بمانند. برای خوردن یک فیلسوف، باید دو چنگال بردارید (آخری چنگال را با اولی تقسیم می کند). برداشتن و گذاشتن چنگال دو عمل مجزا هستند. همه فیلسوفان ساکت هستند. کار پیدا کردن چنین الگوریتمی است که همه آنها فکر کنند و حتی بعد از 54 سال سیر شوند.

ابتدا بیایید سعی کنیم این مشکل را از طریق استفاده از یک فضای مشترک حل کنیم. چنگال ها روی میز مشترک قرار می گیرند و فیلسوفان به سادگی آنها را در زمانی که هستند می گیرند و دوباره می گذارند. در اینجا مشکلاتی برای همگام سازی وجود دارد، دقیقاً چه زمانی باید مطمئن شوید؟ اگر چنگال نباشد چه؟ اما ابتدا فیلسوفان را شروع می کنیم.

برای شروع نخ ها، از یک thread pool استفاده می کنیم Task.Run روش:

var cancelTokenSource = new CancellationTokenSource();
Action<int> create = (i) => RunPhilosopher(i, cancelTokenSource.Token);
for (int i = 0; i < philosophersAmount; i++) 
{
    int icopy = i;
    // Поместить задачу в очередь пула потоков. Метод RunDeadlock не запускаеться 
    // сразу, а ждет своего потока. Асинхронный запуск.
    philosophers[i] = Task.Run(() => create(icopy), cancelTokenSource.Token);
}

Thread Pool برای بهینه سازی ایجاد و حذف موضوع طراحی شده است. این Pool دارای یک صف با وظایف است و CLR بسته به تعداد این وظایف، رشته ها را ایجاد یا حذف می کند. یک استخر برای همه AppDomains. این استخر باید تقریبا همیشه استفاده شود، زیرا. نیازی به ایجاد، حذف رشته ها، صف های آنها و غیره نیست. Thread، این برای مواردی مفید است که شما نیاز به تغییر اولویت یک موضوع دارید، زمانی که عملیات طولانی داریم، برای یک رشته پیش زمینه و غیره.

به عبارت دیگر، System.Threading.Tasks.Task کلاس هم همینطور Thread، اما با انواع امکانات: توانایی اجرای یک کار پس از یک بلوک از وظایف دیگر، بازگرداندن آنها از توابع، قطع راحت آنها و موارد دیگر. و غیره. آنها برای پشتیبانی از ساختارهای async / await (الگوی ناهمزمان مبتنی بر وظیفه، قند نحوی برای انتظار برای عملیات IO) مورد نیاز هستند. بعداً در این مورد صحبت خواهیم کرد.

CancelationTokenSource در اینجا لازم است تا نخ بتواند خود را در سیگنال نخ فراخوان خاتمه دهد.

مشکلات همگام سازی

فیلسوفان مسدود شده

خوب، ما می دانیم که چگونه رشته ایجاد کنیم، بیایید سعی کنیم ناهار بخوریم:

// Кто какие вилки взял. К примеру: 1 1 3 3 - 1й и 3й взяли первые две пары.
private int[] forks = Enumerable.Repeat(0, philosophersAmount).ToArray();

// То же, что RunPhilosopher()
private void RunDeadlock(int i, CancellationToken token) 
{
    // Ждать вилку, взять её. Эквивалентно: 
    // while(true) 
    //     if forks[fork] == 0 
    //          forks[fork] = i+1
    //          break
    //     Thread.Sleep() или Yield() или SpinWait()
    void TakeFork(int fork) =>
        SpinWait.SpinUntil(() => 
            Interlocked.CompareExchange(ref forks[fork], i+1, 0) == 0);

    // Для простоты, но можно с Interlocked.Exchange:
    void PutFork(int fork) => forks[fork] = 0;

    while (true)
    {
        TakeFork(Left(i));
        TakeFork(Right(i));
        eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
        PutFork(Left(i));
        PutFork(Right(i));
        Think(i);

        // Завершить работу по-хорошему.
        token.ThrowIfCancellationRequested();
    }
}

در اینجا ابتدا سعی می کنیم چنگال سمت چپ و سپس چنگال سمت راست را بگیریم و اگر درست شد می خوریم و دوباره می گذاریم. گرفتن یک چنگال اتمی است، یعنی. دو رشته نمی توانند همزمان یکی را بگیرند (نادرست است: اولی می گوید که چنگال آزاد است، دومی - همچنین، اولی می گیرد، دومی می گیرد). برای این Interlocked.CompareExchangeکه باید با دستور پردازنده پیاده سازی شود (TSL, XCHG) که بخشی از حافظه را برای خواندن و نوشتن متوالی اتمی قفل می کند. و SpinWait معادل ساختار است while(true) فقط با کمی "جادو" - موضوع پردازنده را می گیرد (Thread.SpinWait، اما گاهی اوقات کنترل را به رشته دیگری منتقل می کند (Thread.Yeild) یا به خواب می رود (Thread.Sleep).

اما این راه حل کار نمی کند، زیرا جریان ها به زودی (برای من در یک ثانیه) مسدود می شوند: همه فیلسوفان چنگال چپ خود را می گیرند، اما نه چنگال سمت راست را. سپس آرایه فورک دارای مقادیر: 1 2 3 4 5 است.

در شکل، موضوعات مسدود کننده (بن بست). سبز - اجرا، قرمز - همگام سازی، خاکستری - موضوع خواب است. لوزی ها زمان شروع Tasks را نشان می دهند.

گرسنگی فیلسوفان

اگرچه نیازی به فکر کردن به غذا نیست، اما گرسنگی هر کسی را وادار می کند که فلسفه را کنار بگذارد. بیایید سعی کنیم وضعیت گرسنگی نخ ها را در مشکل خود شبیه سازی کنیم. گرسنگی زمانی است که یک نخ در حال اجرا است، اما بدون کار قابل توجه، به عبارت دیگر، این همان بن بست است، فقط اکنون نخ خواب نیست، بلکه فعالانه دنبال چیزی برای خوردن است، اما غذایی نیست. برای جلوگیری از مسدود شدن مکرر، اگر نتوانستیم چنگال دیگری را برداریم، چنگال را برمی‌گردانیم.

// То же что и в RunDeadlock, но теперь кладем вилку назад и добавляем плохих философов.
private void RunStarvation(int i, CancellationToken token)
{
    while (true)
    {
        bool hasTwoForks = false;
        var waitTime = TimeSpan.FromMilliseconds(50);
        // Плохой философов может уже иметь вилку:
        bool hasLeft = forks[Left(i)] == i + 1;
        if (hasLeft || TakeFork(Left(i), i + 1, waitTime))
        {
            if (TakeFork(Right(i), i + 1, TimeSpan.Zero))
                hasTwoForks = true;
            else
                PutFork(Left(i)); // Иногда плохой философ отдает вилку назад.
        } 
        if (!hasTwoForks)
        {
            if (token.IsCancellationRequested) break;
            continue;
        }
        eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
        bool goodPhilosopher = i % 2 == 0;
        // А плохой философ забывает положить свою вилку обратно:
        if (goodPhilosopher)
            PutFork(Left(i));
        // А если и правую не положит, то хорошие будут вообще без еды.
        PutFork(Right(i));

        Think(i);

        if (token.IsCancellationRequested)
            break;
    }
}

// Теперь можно ждать определенное время.
bool TakeFork(int fork, int philosopher, TimeSpan? waitTime = null)
{
    return SpinWait.SpinUntil(
        () => Interlocked.CompareExchange(ref forks[fork], philosopher, 0) == 0,
              waitTime ?? TimeSpan.FromMilliseconds(-1)
    );
}

نکته مهم در مورد این کد این است که از هر چهار فیلسوف دو نفر فراموش می کنند که چنگال چپ خود را زمین بگذارند. و معلوم می شود که آنها غذای بیشتری می خورند، در حالی که دیگران شروع به گرسنگی می کنند، اگرچه نخ ها همان اولویت را دارند. در اینجا آنها کاملاً گرسنه نیستند، زیرا. فیلسوفان بد گاهی اوقات چنگال های خود را پس می زنند. معلوم می شود که افراد خوب حدود 5 برابر کمتر از افراد بد غذا می خورند. بنابراین یک خطای کوچک در کد منجر به افت عملکرد می شود. همچنین در اینجا شایان ذکر است که یک موقعیت نادر ممکن است زمانی که همه فیلسوفان چنگال چپ را بگیرند، سمت راستی وجود نداشته باشد، چپ را بگذارند، صبر کنند، دوباره چپ کنند و غیره. این وضعیت نیز گرسنگی است، بیشتر شبیه به بن بست است. من نتوانستم آن را تکرار کنم. در زیر تصویری برای موقعیتی است که دو فیلسوف بد هر دو چنگال را گرفته اند و دو فیلسوف خوب گرسنه می میرند.

در اینجا می توانید ببینید که موضوعات گاهی اوقات بیدار می شوند و سعی می کنند منبع را بدست آورند. دو هسته از چهار هسته هیچ کاری انجام نمی دهند (نمودار سبز رنگ بالا).

مرگ یک فیلسوف

خوب، مشکل دیگری که می تواند یک شام باشکوه فیلسوفان را مختل کند این است که یکی از آنها ناگهان با چنگال هایی در دستانش بمیرد (و او را به همین ترتیب دفن کنند). سپس همسایه ها بدون شام می مانند. می تونید خودتون یه کد مثال برای این مورد بیارید مثلا بیرون انداخته بشه NullReferenceException بعد از اینکه فیلسوف چنگال ها را می گیرد. و، به هر حال، استثنا مورد بررسی قرار نمی گیرد و کد تماس فقط آن را نمی گیرد (برای این AppDomain.CurrentDomain.UnhandledException و غیره.). بنابراین، کنترل‌کننده‌های خطا در خود رشته‌ها و با خاتمه دلپذیر مورد نیاز هستند.

خدمتکار

خوب، چگونه این مشکل بن بست، گرسنگی و مرگ را حل کنیم؟ ما فقط به یک فیلسوف اجازه می‌دهیم به چنگال‌ها برسد، یک استثناء متقابل از رشته‌ها را برای این مکان اضافه می‌کنیم. چگونه انجامش بدهیم؟ فرض کنید پیشخدمتی در کنار فیلسوفان ایستاده و به هر فیلسوفی اجازه می‌دهد که چنگال‌ها را بردارد. چگونه این گارسون را بسازیم و فیلسوفان چگونه از او خواهند پرسید، سؤالات جالب است.

ساده ترین راه زمانی است که فیلسوفان به سادگی از گارسون برای دسترسی به چنگال ها می خواهند. آن ها اکنون فیلسوفان منتظر یک چنگال در این نزدیکی نیستند، بلکه منتظر می مانند یا از پیشخدمت می پرسند. در ابتدا، ما فقط از فضای کاربری برای این کار استفاده می کنیم، در آن از وقفه برای فراخوانی هیچ رویه ای از هسته (در مورد آنها در زیر) استفاده نمی کنیم.

راه حل ها در فضای کاربری

در اینجا همان کاری را می کنیم که قبلاً با یک چنگال و دو فیلسوف انجام می دادیم، در یک چرخه می چرخیم و منتظر می مانیم. اما اکنون همه فیلسوفان خواهند بود و، همانطور که بود، فقط یک چنگال، یعنی. می توان گفت فقط فیلسوفی می خورد که این "چنگال طلا" را از پیشخدمت گرفته است. برای این ما از SpinLock استفاده می کنیم.

private static SpinLock spinLock = new SpinLock();  // Наш "официант"
private void RunSpinLock(int i, CancellationToken token)
{
    while (true)
    {
        // Взаимная блокировка через busy waiting. Вызываем до try, чтобы
        // выбрасить исключение в случае ошибки в самом SpinLock.
        bool hasLock = false;
        spinLock.Enter(ref hasLock);
        try
        {
            // Здесь может быть только один поток (mutual exclusion).
            forks[Left(i)] = i + 1;  // Берем вилку сразу, без ожидания.
            forks[Right(i)] = i + 1;
            eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
            forks[Left(i)] = 0;
            forks[Right(i)] = 0;
        }
        finally
        {
            if(hasLock) spinLock.Exit();  // Избегаем проблемы со смертью философа.
        }

        Think(i);

        if (token.IsCancellationRequested)
            break;
    }
}

SpinLock این یک مسدود کننده است، با تقریباً یکسان است while(true) { if (!lock) break; }، اما با "جادویی" حتی بیشتر از در SpinWait (که در آنجا استفاده می شود). حالا او می داند چگونه منتظران را بشمارد، کمی بخواباند و بیشتر. و غیره به طور کلی، هر کاری که ممکن است برای بهینه سازی انجام می دهد. اما باید به یاد داشته باشیم که این هنوز همان چرخه فعالی است که منابع پردازنده را می خورد و جریان را حفظ می کند، که اگر یکی از فیلسوفان اولویت بیشتری نسبت به دیگران داشته باشد، اما چنگال طلایی نداشته باشد (مشکل وارونگی اولویت) می تواند منجر به گرسنگی شود. . بنابراین، ما از آن فقط برای تغییرات بسیار کوتاه در حافظه مشترک، بدون تماس های شخص ثالث، قفل های تودرتو و سایر موارد غافلگیر استفاده می کنیم.

نقاشی برای SpinLock. نهرها دائماً برای چنگال طلا "جنگ" می کنند. شکست وجود دارد - در شکل، منطقه انتخاب شده. هسته ها به طور کامل مورد استفاده قرار نمی گیرند: فقط حدود 2/3 توسط این چهار رشته.

راه حل دیگر در اینجا فقط استفاده است Interlocked.CompareExchange با همان انتظار فعال همانطور که در کد بالا نشان داده شده است (در فیلسوفان گرسنه)، اما این، همانطور که قبلاً گفته شد، از نظر تئوری می تواند منجر به مسدود شدن شود.

بر Interlocked لازم به ذکر است که نه تنها وجود دارد CompareExchangeو همچنین روش های دیگری برای خواندن و نوشتن اتمی. و از طریق تکرار تغییر، در صورتی که رشته دیگری زمان داشته باشد تا تغییرات خود را انجام دهد (خواندن 1، خواندن 2، نوشتن 2، نوشتن 1 بد است)، می توان از آن برای تغییرات پیچیده به یک مقدار استفاده کرد (الگوی Interlocked Anything) .

راه حل های حالت هسته

برای جلوگیری از هدر رفتن منابع در یک حلقه، بیایید ببینیم چگونه می توانیم یک موضوع را مسدود کنیم. به عبارت دیگر، در ادامه مثال خود، ببینیم که چگونه پیشخدمت فیلسوف را می خواباند و تنها در مواقع ضروری او را بیدار می کند. ابتدا، بیایید نحوه انجام این کار را از طریق حالت هسته سیستم عامل بررسی کنیم. همه ساختارها در آنجا اغلب کندتر از ساختارهای موجود در فضای کاربر هستند. برای مثال چندین برابر کندتر AutoResetEvent شاید 53 برابر کندتر SpinLock [ریشتر]. اما با کمک آنها، می توانید فرآیندها را در سراسر سیستم، مدیریت شده یا غیر مدیریت شده، همگام کنید.

ساختار اصلی در اینجا سمافوری است که توسط دایکسترا بیش از نیم قرن پیش پیشنهاد شده است. سمافور به زبان ساده یک عدد صحیح مثبت است که توسط سیستم مدیریت می شود و دو عملیات افزایش و کاهش روی آن انجام می شود. اگر نتواند کاهش یابد، صفر، آنگاه رشته فراخوان مسدود می شود. هنگامی که عدد توسط یک رشته/فرآیند فعال دیگر افزایش می‌یابد، رشته‌ها حذف می‌شوند و سمافور دوباره با عدد ارسال شده کاهش می‌یابد. می توان قطارهایی را در گلوگاه با سمافور تصور کرد. دات نت چندین ساختار با عملکرد مشابه ارائه می دهد: AutoResetEvent, ManualResetEvent, Mutex و خودم Semaphore. ما استفاده خواهیم کرد AutoResetEvent، این ساده ترین این ساختارها است: فقط دو مقدار 0 و 1 (نادرست، درست). روش او WaitOne() اگر مقدار 0 بود، رشته فراخوان را مسدود می کند و اگر 1 باشد، آن را به 0 کاهش می دهد و آن را رد می کند. یک روش Set() به 1 می‌برد و به یک پیشخدمت اجازه می‌دهد که دوباره به 0 برسد.

بیایید راه حل را پیچیده کنیم و از قفل برای هر فیلسوف استفاده کنیم، نه برای همه یکباره. آن ها اکنون ممکن است چندین فیلسوف در آن واحد وجود داشته باشد، نه یک فیلسوف. اما ما مجدداً دسترسی به جدول را مسدود می کنیم تا به درستی، اجتناب از مسابقه (شرایط مسابقه)، مطمئن شرط بندی شود.

// Для блокирования отдельного философа.
// Инициализируется: new AutoResetEvent(true) для каждого.
private AutoResetEvent[] philosopherEvents;

// Для доступа к вилкам / доступ к столу.
private AutoResetEvent tableEvent = new AutoResetEvent(true);

// Рождение философа.
public void Run(int i, CancellationToken token)
{
    while (true)
    {
        TakeForks(i); // Ждет вилки.
        // Обед. Может быть и дольше.
        eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
        PutForks(i); // Отдать вилки и разблокировать соседей.
        Think(i);
        if (token.IsCancellationRequested) break;
    }
}

// Ожидать вилки в блокировке.
void TakeForks(int i)
{
    bool hasForks = false;
    while (!hasForks) // Попробовать еще раз (блокировка не здесь).
    {
        // Исключающий доступ к столу, без гонок за вилками.
        tableEvent.WaitOne();
        if (forks[Left(i)] == 0 && forks[Right(i)] == 0)
            forks[Left(i)] = forks[Right(i)] = i + 1;
        hasForks = forks[Left(i)] == i + 1 && forks[Right(i)] == i + 1;
        if (hasForks)
            // Теперь философ поест, выйдет из цикла. Если Set 
            // вызван дважды, то значение true.
            philosopherEvents[i].Set();
        // Разблокировать одного ожидающего. После него значение tableEvent в false.
        tableEvent.Set(); 
        // Если имеет true, не блокируется, а если false, то будет ждать Set от соседа.
        philosopherEvents[i].WaitOne();
    }
}

// Отдать вилки и разблокировать соседей.
void PutForks(int i)
{
    tableEvent.WaitOne(); // Без гонок за вилками.
    forks[Left(i)] = 0;
    // Пробудить левого, а потом и правого соседа, либо AutoResetEvent в true.
    philosopherEvents[LeftPhilosopher(i)].Set();
    forks[Right(i)] = 0;
    philosopherEvents[RightPhilosopher(i)].Set();
    tableEvent.Set();
}

برای درک آنچه در اینجا اتفاق می افتد، موردی را در نظر بگیرید که فیلسوف نتوانست چنگال ها را بگیرد، سپس اقدامات او به شرح زیر خواهد بود. او منتظر دسترسی به میز است. با دریافت آن، سعی می کند چنگال ها را بگیرد. نتیجه نداد. دسترسی به جدول را می دهد (حذف متقابل). و از "گردنگردان" خود می گذرد (AutoResetEvent) (در ابتدا باز هستند). دوباره وارد چرخه می شود، زیرا او چنگال ندارد او سعی می کند آنها را بگیرد و در "تورنتیکل" خود می ایستد. یکی از همسایه‌های خوش شانس‌تر در سمت راست یا چپ، پس از پایان غذا خوردن، قفل فیلسوف ما را باز می‌کند و «درگردش را باز می‌کند». فیلسوف ما برای بار دوم از آن می گذرد (و پشتش می بندد). او برای سومین بار سعی می کند چنگال ها را بگیرد. موفق باشید. و گردانش را رد می کند تا غذا بخورد.

هنگامی که خطاهای تصادفی در چنین کدهایی وجود دارد (آنها همیشه وجود دارند)، به عنوان مثال، یک همسایه به اشتباه مشخص شده است یا همان شی ایجاد می شود. AutoResetEvent برای همه (Enumerable.Repeat، سپس فیلسوفان منتظر توسعه دهندگان خواهند بود، زیرا یافتن خطاها در چنین کدهایی کار بسیار دشواری است. مشکل دیگر این راه حل این است که تضمین نمی کند که فلان فیلسوف گرسنه نمی ماند.

راه حل های ترکیبی

ما دو رویکرد را برای زمان‌بندی بررسی کرده‌ایم، زمانی که در حالت کاربر و حلقه باقی می‌مانیم، و زمانی که رشته را از طریق هسته مسدود می‌کنیم. روش اول برای قفل های کوتاه خوب است، روش دوم برای قفل های بلند. اغلب لازم است ابتدا به طور خلاصه منتظر تغییر یک متغیر در یک حلقه باشیم و سپس زمانی که انتظار طولانی است، رشته را مسدود کنیم. این رویکرد در به اصطلاح اجرا می شود. ساختارهای ترکیبی در اینجا همان ساختارهای حالت هسته وجود دارد، اما اکنون با یک حلقه حالت کاربر: SemaphorSlim, ManualResetEventSlim و غیره محبوب ترین طرح در اینجا است Monitor، زیرا در سی شارپ به خوبی شناخته شده است lock نحو. Monitor این همان سمافور با حداکثر مقدار 1 (mutex) است، اما با پشتیبانی از انتظار در یک حلقه، بازگشت، الگوی Condition Variable (در مورد آن در زیر)، و غیره. اجازه دهید راه حلی را با آن بررسی کنیم.

// Спрячем объект для Монитора от всех, чтобы без дедлоков.
private readonly object _lock = new object();
// Время ожидания потока.
private DateTime?[] _waitTimes = new DateTime?[philosophersAmount];

public void Run(int i, CancellationToken token)
{
    while (true)
    {
        TakeForks(i);
        eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
        PutForks(i);
        Think(i);
        if (token.IsCancellationRequested) break;
    }
}

// Наше сложное условие для Condition Variable паттерна.
bool CanIEat(int i)
{
    // Если есть вилки:
    if (forks[Left(i)] != 0 && forks[Right(i)] != 0)
        return false;
    var now = DateTime.Now;
    // Может, если соседи не более голодные, чем текущий.
    foreach(var p in new int[] {LeftPhilosopher(i), RightPhilosopher(i)})
        if (_waitTimes[p] != null && now - _waitTimes[p] > now - _waitTimes[i])
            return false;
    return true;
}

void TakeForks(int i)
{
    // Зайти в Монитор. То же самое: lock(_lock) {..}.
    // Вызываем вне try, чтобы возможное исключение выбрасывалось выше.
    bool lockTaken = false;
    Monitor.Enter(_lock, ref lockTaken);
    try
    {
        _waitTimes[i] = DateTime.Now;
        // Condition Variable паттерн. Освобождаем лок, если не выполненно 
        // сложное условие. И ждем пока кто-нибудь сделает Pulse / PulseAll.
        while (!CanIEat(i))
            Monitor.Wait(_lock); 
        forks[Left(i)] = i + 1;
        forks[Right(i)] = i + 1;
        _waitTimes[i] = null;
    }
    finally
    {
        if (lockTaken) Monitor.Exit(_lock);
    }
}

void PutForks(int i)
{
    // То же самое: lock (_lock) {..}.
    bool lockTaken = false;
    Monitor.Enter(_lock, ref lockTaken);
    try
    {
        forks[Left(i)] = 0;
        forks[Right(i)] = 0;
        // Освободить все потоки в очереди ПОСЛЕ вызова Monitor.Exit.
        Monitor.PulseAll(_lock); 
    }
    finally
    {
        if (lockTaken) Monitor.Exit(_lock);
    }
}

در اینجا ما دوباره کل جدول را برای دسترسی به چنگال‌ها مسدود می‌کنیم، اما اکنون همه رشته‌ها را به یکباره رفع انسداد می‌کنیم، نه همسایه‌ها را وقتی که کسی غذا خوردن را تمام کرد. آن ها اول یک نفر غذا می خورد و همسایه ها را مسدود می کند و وقتی این یکی تمام می کند اما می خواهد فوراً دوباره غذا بخورد، وارد بلاک می شود و همسایه ها را بیدار می کند، زیرا. زمان انتظارش کمتره

اینگونه است که از بن بست و گرسنگی فلاسفه دوری می کنیم. ما از یک حلقه برای یک انتظار کوتاه استفاده می کنیم و نخ را برای مدت طولانی مسدود می کنیم. رفع انسداد همه به یکباره کندتر از زمانی است که فقط همسایه رفع انسداد شود، مانند راه حل با AutoResetEvent، اما تفاوت نباید زیاد باشد، زیرا نخ ها ابتدا باید در حالت کاربر باقی بمانند.

У lock نحو شگفتی های بدی دارد. توصیه به استفاده Monitor مستقیما [ریشتر] [اریک لیپرت]. یکی از آنها این است lock همیشه خارج از Monitor، حتی اگر یک استثنا وجود داشته باشد، در این صورت رشته دیگری می تواند وضعیت حافظه مشترک را تغییر دهد. در چنین مواردی، اغلب بهتر است به بن بست بروید یا به نحوی ایمن برنامه را خاتمه دهید. شگفتی دیگر این است که مانیتور از بلوک های همگام سازی استفاده می کند (SyncBlock) که در همه اشیا وجود دارد. بنابراین، اگر یک شی نامناسب انتخاب شود، به راحتی می توانید یک بن بست دریافت کنید (به عنوان مثال، اگر روی یک رشته داخلی قفل کنید). برای این کار از شی همیشه پنهان استفاده می کنیم.

الگوی Condition Variable به شما این امکان را می دهد که به طور مختصرتر انتظارات برخی شرایط پیچیده را پیاده سازی کنید. در دات نت به نظر من ناقص است چون در تئوری، باید چندین صف در چندین متغیر وجود داشته باشد (مانند موضوعات Posix)، و نه در یک lok. سپس می توان آنها را برای همه فیلسوفان ساخت. اما حتی در این فرم به شما امکان کاهش کد را می دهد.

بسیاری از فیلسوفان یا async / await

خوب، اکنون می‌توانیم به‌طور مؤثر موضوعات را مسدود کنیم. اما اگر فیلسوفان زیادی داشته باشیم چه؟ 100؟ 10000؟ به عنوان مثال، ما 100000 درخواست به وب سرور دریافت کردیم. ایجاد یک موضوع برای هر درخواست سربار خواهد بود، زیرا بنابراین بسیاری از موضوعات به صورت موازی اجرا نمی شوند. فقط به تعداد هسته های منطقی اجرا می شود (من 4 هسته دارم). و بقیه فقط منابع را از بین خواهند برد. یکی از راه حل های این مشکل الگوی async / await است. ایده آن این است که تابع اگر نیاز به منتظر ماندن برای ادامه چیزی باشد، نخ را نگه نمی دارد. و وقتی کاری انجام می دهد، اجرای خود را از سر می گیرد (اما نه لزوماً در همان رشته!). در مورد ما، ما منتظر چنگال خواهیم بود.

SemaphoreSlim برای این دارد WaitAsync() روش. در اینجا پیاده سازی با استفاده از این الگو است.

// Запуск такой же, как раньше. Где-нибудь в программе:
Task.Run(() => Run(i, cancelTokenSource.Token));

// Запуск философа.
// Ключевое слово async -- компилятор транслирует этот метот в асинхронный.
public async Task Run(int i, CancellationToken token)
{
    while (true)
    {
        // await -- будем ожидать какого-то события.
        await TakeForks(i);
        // После await, продолжение возможно в другом потоке.
        eatenFood[i] = (eatenFood[i] + 1) % (int.MaxValue - 1);
        // Может быть несколько событий для ожидания.
        await PutForks(i);

        Think(i);

        if (token.IsCancellationRequested) break;
    }
}

async Task TakeForks(int i)
{
    bool hasForks = false;
    while (!hasForks)
    {
        // Взаимоисключающий доступ к столу:
        await _tableSemaphore.WaitAsync();
        if (forks[Left(i)] == 0 && forks[Right(i)] == 0)
        {
            forks[Left(i)] = i+1;
            forks[Right(i)] = i+1;
            hasForks = true;
        }
        _tableSemaphore.Release();
        // Будем ожидать, чтобы сосед положил вилки:
        if (!hasForks)
            await _philosopherSemaphores[i].WaitAsync();
    }
}

// Ждем доступа к столу и кладем вилки.
async Task PutForks(int i)
{
    await _tableSemaphore.WaitAsync();
    forks[Left(i)] = 0;
    // "Пробудить" соседей, если они "спали".
    _philosopherSemaphores[LeftPhilosopher(i)].Release();
    forks[Right(i)] = 0;
    _philosopherSemaphores[RightPhilosopher(i)].Release();
    _tableSemaphore.Release();
}

روش با async / await به یک ماشین حالت فریبنده ترجمه می شود که بلافاصله داخلی خود را برمی گرداند Task. از طریق آن، می‌توانید منتظر تکمیل روش، لغو آن و سایر کارهایی که می‌توانید با Task انجام دهید، بمانید. در داخل متد، ماشین حالت اجرا را کنترل می کند. نکته اصلی این است که اگر تاخیر وجود نداشته باشد، اجرا همزمان است و اگر وجود داشته باشد، نخ آزاد می شود. برای درک بهتر این موضوع، بهتر است به این ماشین حالت نگاه کنید. شما می توانید از این ها زنجیره ایجاد کنید async / await مواد و روش ها.

بیایید تست کنیم. کار 100 فیلسوف روی ماشینی با 4 هسته منطقی، 8 ثانیه. راه حل قبلی با مانیتور فقط 4 تای اول را اجرا کرد و بقیه اصلا اجرا نشد. هر یک از این 4 رشته حدود 2 میلی ثانیه بیکار بودند. و راه حل async / await تمام 100 مورد را اجرا کرد، با میانگین انتظار هر کدام 6.8 ثانیه. البته در سیستم های واقعی بیکار بودن 6 ثانیه غیرقابل قبول است و بهتر است این همه درخواست از این قبیل پردازش نشود. راه حل با مانیتور به هیچ وجه مقیاس پذیر نیست.

نتیجه

همانطور که از این مثال های کوچک می بینید، دات نت از بسیاری از ساختارهای همگام سازی پشتیبانی می کند. با این حال، نحوه استفاده از آنها همیشه مشخص نیست. امیدوارم این مقاله مفید بوده باشد. در حال حاضر، این پایان است، اما هنوز چیزهای جالب زیادی باقی مانده است، به عنوان مثال، مجموعه های امن، TPL Dataflow، برنامه نویسی Reactive، مدل Transaction نرم افزار و غیره.

منابع

• تجسم جریان: ویژوالایزر همزمانی
• MSDN: نخ کشی, الگوهای برنامه نویسی ناهمزمان و خیلی های دیگر دکتر.
• [ریشتر] - CLR از طریق سی شارپ، جفری ریشتر
• [اریک لیپرت] - در مورد قفل
• منبع
• تصویر - "رقص در میان شمشیرها"، G. Semiradsky

منبع: www.habr.com