Yaxshi oziqlangan faylasuflar yoki raqobatbardosh .NET dasturlash

Keling, faylasuflarning tushlik muammosi misolidan foydalanib, .Net-da parallel va parallel dasturlash qanday ishlashini ko'rib chiqaylik. Reja quyidagicha, ip/jarayonni sinxronlashtirishdan aktyor modeligacha (keyingi qismlarda). Maqola birinchi tanishish yoki bilimingizni yangilash uchun foydali bo'lishi mumkin.

Nega buni qanday qilishni bilasizmi? Tranzistorlar o'zlarining minimal o'lchamlariga erishmoqdalar, Mur qonuni yorug'lik tezligi chegarasiga etib boradi va shuning uchun raqamlarda o'sish kuzatiladi; ko'proq tranzistorlar yasash mumkin. Shu bilan birga, ma'lumotlar miqdori o'sib bormoqda va foydalanuvchilar tizimlardan darhol javob kutishadi. Bunday holatda, bizda bitta bajaruvchi ipga ega bo'lgan "oddiy" dasturlash endi samarali bo'lmaydi. Biz qandaydir tarzda bir vaqtning o'zida yoki bir vaqtning o'zida ijro etish muammosini hal qilishimiz kerak. Bundan tashqari, bu muammo turli darajalarda mavjud: ip darajasida, jarayon darajasida, tarmoqdagi mashinalar darajasida (tarqatilgan tizimlar). .NET bunday muammolarni tez va samarali hal qilish uchun yuqori sifatli, vaqt sinovidan o'tgan texnologiyalarga ega.

Maqsad

Edsger Deykstra 1965 yilda o'z shogirdlariga bu muammoni so'ragan. Belgilangan formulasi quyidagicha. Ma'lum (odatda besh) faylasuflar soni va bir xil miqdordagi vilkalar mavjud. Ular dumaloq stolda o'tirishadi, ular orasidagi vilkalar. Faylasuflar o'zlarining cheksiz taomlaridan eb-ichishi, o'ylashlari yoki kutishlari mumkin. Ovqatlanish uchun faylasuf ikkita vilka olishi kerak (ikkinchi vilkani birinchisi bilan baham ko'radi). Vilkani ko'tarish va qo'yish ikkita alohida harakatdir. Hamma faylasuflar jim. Vazifa shunday algoritmni topishdan iboratki, ularning barchasi 54 yildan keyin ham o'ylaydi va yaxshi ovqatlanadi.

Birinchidan, umumiy maydondan foydalanish orqali ushbu muammoni hal qilishga harakat qilaylik. Vilkalar umumiy stolda yotadi va faylasuflar u erda bo'lganda ularni olib, orqaga qo'yishadi. Aynan shu erda sinxronizatsiya bilan bog'liq muammolar paydo bo'ladi, vilkalarni qachon olish kerak? vilka bo'lmasa nima qilish kerak? va hokazo. Lekin birinchi navbatda faylasuflardan boshlaylik.

Mavzularni boshlash uchun biz orqali iplar hovuzidan foydalanamiz Task.Run usul:

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);
}

Ip hovuzi iplarni yaratish va olib tashlashni optimallashtirish uchun mo'ljallangan. Ushbu hovuzda vazifalar navbati mavjud va CLR ushbu vazifalar soniga qarab mavzularni yaratadi yoki o'chiradi. Barcha AppDomains uchun bitta hovuz. Bu hovuzdan deyarli har doim foydalanish kerak, chunki... mavzularni, ularning navbatlarini va hokazolarni yaratish va o'chirish bilan bezovtalanishning hojati yo'q. Siz buni hovuzsiz ham qilishingiz mumkin, lekin keyin uni to'g'ridan-to'g'ri ishlatishingiz kerak bo'ladi. Thread, bu biz ipning ustuvorligini o'zgartirishimiz kerak bo'lgan holatlar uchun foydalidir, biz uzoq vaqt operatsiya qilganimizda, Oldingi ip uchun va hokazo.

Boshqa so'z bilan, System.Threading.Tasks.Task sinf bir xil Thread, lekin har xil qulayliklar bilan: boshqa vazifalar blokidan keyin vazifani ishga tushirish, ularni funktsiyalardan qaytarish, ularni qulay tarzda to'xtatish va boshqalar. va hokazo. Ular asinxron/kutish konstruksiyalarini qo'llab-quvvatlash uchun kerak (Vazifaga asoslangan asinxron naqsh, IO operatsiyalarini kutish uchun sintaktik shakar). Bu haqda keyinroq gaplashamiz.

CancelationTokenSource bu erda ip chaqiruvchi ipning signali bilan o'zini tugatishi kerak.

Sinxronlash muammolari

Bloklangan faylasuflar

Yaxshi, biz iplarni qanday yaratishni bilamiz, keling, tushlik qilaylik:

// Кто какие вилки взял. К примеру: 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();
    }
}

Bu erda biz birinchi navbatda chap, keyin esa o'ng vilkani olishga harakat qilamiz va agar u ishlayotgan bo'lsa, biz ovqatlanamiz va ularni qaytarib qo'yamiz. Bitta vilka olish atomik, ya'ni. ikkita ip bir vaqtning o'zida bittasini ololmaydi (noto'g'ri: birinchisi vilka bo'sh ekanligini o'qiydi, ikkinchisi xuddi shunday qiladi, birinchisi oladi, ikkinchisi oladi). Buning uchun Interlocked.CompareExchange, bu protsessor ko'rsatmasi yordamida amalga oshirilishi kerak (TSL, XCHG), atomik ketma-ket o'qish va yozish uchun xotira qismini blokirovka qiladi. Va SpinWait qurilishga teng while(true) faqat bir oz "sehr" bilan - ip protsessorni oladi (Thread.SpinWait), lekin ba'zida boshqaruvni boshqa ipga o'tkazadi (Thread.Yeild) yoki uxlab qoladi (Thread.Sleep).

Lekin bu yechim ishlamaydi, chunki... tez orada (men uchun bir soniya ichida) iplar bloklanadi: barcha faylasuflar chap vilkalarini olishadi, lekin to'g'ri yo'q. Keyin vilkalar qatori quyidagi qiymatlarga ega bo'ladi: 1 2 3 4 5.

Rasmda iplarni blokirovka qilish (o'lik qulf). Yashil rang bajarilishni, qizil rang sinxronizatsiyani va kul rang ipning uxlayotganligini bildiradi. Olmoslar Vazifalarni ishga tushirish vaqtini bildiradi.

Faylasuflarning ochligi

O'ylash uchun ko'p ovqat kerak bo'lmasa-da, ochlik har kimni falsafadan voz kechishga majbur qilishi mumkin. Keling, muammomizda ip ochligi holatini taqlid qilishga harakat qilaylik. Ochlik - bu ipning ishlayotgani, ammo muhim ishsiz, boshqacha qilib aytganda, xuddi shunday o'lik, faqat hozir ip uxlamayapti, lekin faol ravishda ovqatlanish uchun biror narsa qidirmoqda, ammo ovqat yo'q. Tez-tez to'sib qo'ymaslik uchun, agar boshqasini olish imkoni bo'lmasa, vilkani orqaga qaytaramiz.

// То же что и в 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)
    );
}

Ushbu kodning muhim tomoni shundaki, har to'rtta faylasufdan ikkitasi chap vilkasini qo'yishni unutishadi. Va ma'lum bo'lishicha, ular ko'proq ovqat iste'mol qiladilar va boshqalar och qolishni boshlaydilar, garchi iplar bir xil ustuvorlikka ega. Bu erda ular to'liq och qolishmayapti, chunki... yomon faylasuflar ba'zan vilkalarini orqaga qaytaradilar. Ma'lum bo'lishicha, yaxshilar yomonlarga qaraganda taxminan 5 baravar kam ovqatlanishadi. Shunday qilib, koddagi kichik xato ishlashning pasayishiga olib keladi. Shuni ham ta'kidlash kerakki, barcha faylasuflar chap vilkani olishsa, o'ng yo'q, ular chapni qo'yishadi, kutishadi, chapni yana olishadi va hokazo. Bu holat ham ochlik, ko'proq o'zaro blokirovkaga o'xshaydi. Men buni takrorlay olmadim. Quyida ikkita yomon faylasuf ikkala vilkani olgan va ikkita yaxshi ochlikdan o'layotgan vaziyat uchun rasm.

Bu yerda siz mavzular ba'zan uyg'onib, resurs olishga harakat qilayotganini ko'rishingiz mumkin. To'rt yadrodan ikkitasi hech narsa qilmaydi (yuqoridagi yashil grafik).

Faylasufning o'limi

Faylasuflarning shonli kechki ziyofatiga xalaqit berishi mumkin bo'lgan yana bir muammo shundaki, ulardan biri to'satdan qo'lida vilkalar bilan vafot etsa (va u shu tarzda dafn etiladi). Keyin qo'shnilar tushliksiz qoladilar. Siz o'zingiz bu ish uchun misol kodini topishingiz mumkin, masalan, u tashlanadi NullReferenceException faylasuf vilkalarni olganidan keyin. Aytgancha, istisno ko'rib chiqilmaydi va qo'ng'iroq kodi uni shunchaki ushlamaydi (buning uchun AppDomain.CurrentDomain.UnhandledException va boshq.). Shuning uchun, xato ishlov beruvchilar iplarning o'zida va oqlangan tugatish bilan kerak.

Ofitsiant

Xo'sh, bu boshi berk ko'cha, ochlik va o'lim muammosini qanday hal qilamiz? Biz vilkalar uchun faqat bitta faylasufga ruxsat beramiz va biz bu joy uchun iplarni o'zaro istisno qilamiz. Buni qanday qilish kerak? Faraz qilaylik, faylasuflarning yonida ofitsiant bor, u bitta faylasufga vilkalar olishga ruxsat beradi. Bu ofitsiantni qanday qilishimiz kerak va faylasuflar unga qanday savol berishlari qiziq savollar.

Eng oddiy usul faylasuflar uchun ofitsiantdan vilkalarga kirishni doimiy ravishda so'rashdir. Bular. Endi faylasuflar yaqin atrofda vilka kutishmaydi, balki kutish yoki ofitsiantdan so'rashadi. Buning uchun avvaliga biz faqat Foydalanuvchi maydonidan foydalanamiz, unda yadrodan hech qanday protseduralarni chaqirish uchun uzilishlardan foydalanmaymiz (ular haqida quyida batafsilroq).

Foydalanuvchi maydoni yechimlari

Bu erda biz bir vilka va ikkita faylasuf bilan ilgari qilgan ishni qilamiz, biz halqada aylanamiz va kutamiz. Ammo endi bu barcha faylasuflar bo'ladi va xuddi shunday, faqat bitta vilkalar, ya'ni. bu “oltin vilka”ni ofitsiantdan olgan faylasufgina ovqatlanadi, deyishimiz mumkin. Buning uchun biz SpinLock-dan foydalanamiz.

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 Bu bloker, taxminan aytganda, xuddi shunday while(true) { if (!lock) break; }, lekin undan ham ko'proq "sehr" bilan SpinWait (u erda ishlatiladi). Endi u kutayotganlarni qanday hisoblashni, ularni biroz uxlashni va yana ko'p narsalarni biladi. va hokazo. Umuman olganda, optimallashtirish uchun hamma narsani qiladi. Ammo shuni yodda tutishimiz kerakki, bu hali ham protsessor resurslarini iste'mol qiladigan va ipni ushlab turadigan faol halqadir, agar faylasuflardan biri boshqalarga qaraganda ko'proq ustuvor bo'lsa, lekin oltin vilkaga ega bo'lmasa, ochlikka olib kelishi mumkin (Priority Inversion muammosi). ). Shuning uchun biz uni faqat umumiy xotiradagi juda qisqa o'zgarishlar uchun, uchinchi tomon qo'ng'iroqlari, ichki qulflar yoki boshqa kutilmagan hodisalarsiz foydalanamiz.

uchun chizish SpinLock. Oqimlar doimo oltin vilka uchun "kurashmoqda". Muvaffaqiyatsizliklar yuzaga keladi - rasmdagi ta'kidlangan maydon. Yadrolar to'liq ishlatilmaydi: bu to'rtta ipning atigi 2/3 qismi.

Bu erda yana bir yechim faqat foydalanish bo'ladi Interlocked.CompareExchange yuqoridagi kodda ko'rsatilgandek faol kutish bilan (och faylasuflarda), lekin bu, yuqorida aytib o'tilganidek, nazariy jihatdan blokirovkaga olib kelishi mumkin.

haqida Interlocked nafaqat borligini aytishga arziydi CompareExchange, balki atomik o'qish va yozishning boshqa usullari. Va o'zgartirishni takrorlash orqali, agar boshqa ip o'z o'zgarishlarini amalga oshirishga muvaffaq bo'lsa (1-ni o'qing, 2-ni o'qing, 2-ni yozing, 1-ni yozing yomon), u bitta qiymatga murakkab o'zgartirishlar uchun ishlatilishi mumkin (Interlocked Anything naqsh).

Yadro rejimi yechimlari

Loopda resurslarni isrof qilmaslik uchun, keling, ipni qanday blokirovka qilishni ko'rib chiqaylik. Boshqacha qilib aytganda, misolimizni davom ettirsak, keling, ofitsiant faylasufni qanday uxlatayotganini va kerak bo'lganda uni uyg'otayotganini ko'rib chiqaylik. Birinchidan, buni operatsion tizimning yadro rejimi orqali qanday qilishni ko'rib chiqamiz. U erdagi barcha tuzilmalar ko'pincha foydalanuvchi maydonidagiga qaraganda sekinroq bo'ladi. Masalan, bir necha marta sekinroq AutoResetEvent ehtimol 53 marta sekinroq SpinLock [Rixter]. Ammo ularning yordami bilan siz butun tizim bo'ylab jarayonlarni sinxronlashtirishingiz mumkin, boshqariladi yoki yo'q.

Bu erda asosiy dizayn yarim asrdan ko'proq vaqt oldin Dijkstra tomonidan taklif qilingan semafordir. Semafor, sodda qilib aytganda, tizim tomonidan boshqariladigan musbat butun son va unda ikkita operatsiya - oshirish va kamaytirish. Agar nolni kamaytirishning iloji bo'lmasa, chaqiruvchi ip bloklanadi. Raqam boshqa faol ip/jarayon tomonidan oshirilsa, iplar uzatiladi va semafor yana o'tgan songa kamayadi. Poezdlarni semafor bilan darboğazda tasavvur qilishingiz mumkin. .NET shu kabi funksiyalarga ega boʻlgan bir nechta konstruksiyalarni taklif etadi: AutoResetEvent, ManualResetEvent, Mutex va men o'zimni Semaphore. foydalanamiz AutoResetEvent, bu konstruksiyalarning eng oddiyi: faqat ikkita qiymat 0 va 1 (noto'g'ri, rost). Uning usuli WaitOne() agar qiymat 0 bo'lsa, chaqiruvchi ipni bloklaydi va agar 1 bo'lsa, uni 0 ga tushiradi va uni o'tkazib yuboradi. Bir usul Set() 1 ga ortadi va bir kishi o'tishiga imkon beradi, u yana 0 ga kamayadi. Metroda turniket kabi ishlaydi.

Keling, yechimni murakkablashtiramiz va bir vaqtning o'zida emas, balki har bir faylasuf uchun blokirovkadan foydalanamiz. Bular. Endi bitta emas, balki bir nechta faylasuflar bir vaqtning o'zida ovqatlanishlari mumkin. Ammo biz poyga sharoitidan qochib, vilkalarni to'g'ri qabul qilish uchun stolga kirishni yana bloklaymiz.

// Для блокирования отдельного философа.
// Инициализируется: 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();
}

Bu erda nima sodir bo'layotganini tushunish uchun faylasuf vilkalarni ololmaganini ko'rib chiqing, keyin uning harakatlari quyidagicha bo'ladi. U stolga kirishni kutmoqda. Uni qabul qilib, vilkalarni olishga harakat qiladi. Ishdan chiqmadi. Bu jadvalga kirish imkoniyatini beradi (o'zaro istisno). Va u o'zining "turniketidan" o'tadi (AutoResetEvent) (dastlab ular ochiq). Bu yana tsiklga tushadi, chunki uning vilkalari yo'q. U ularni olishga harakat qiladi va o'zining "turniketida" to'xtaydi. O'ng yoki chap tarafdagi bahtli qo'shnimiz ovqatlanib bo'lgach, "turniketini ochib" bizning faylasufimizni blokdan chiqaradi. Bizning faylasuf ikkinchi marta o'tadi (va uning orqasida yopiladi). Uchinchi marta vilkalarni olishga harakat qiladi. Omadli. Va u tushlik qilish uchun turniketdan o'tadi.

Bunday kodda tasodifiy xatolar mavjud bo'lganda (ular har doim mavjud), masalan, qo'shni noto'g'ri ko'rsatiladi yoki xuddi shu ob'ekt yaratiladi. AutoResetEvent Barcha uchun (Enumerable.Repeat), keyin faylasuflar ishlab chiquvchilarni kutishadi, chunki Bunday koddagi xatolarni topish juda qiyin ish. Bu yechimning yana bir muammosi shundaki, u qandaydir faylasuf och qolmasligiga kafolat bermaydi.

Gibrid yechimlar

Biz sinxronlashtirishning ikkita yondashuvini ko'rib chiqdik, biz foydalanuvchi rejimida qolib, tsiklda aylanamiz va yadro orqali ipni bloklaymiz. Birinchi usul qisqa bloklar uchun yaxshi, ikkinchisi uzun bo'lganlar uchun. Ko'pincha siz avval o'zgaruvchining tsiklda o'zgarishini qisqa kutishingiz kerak, keyin kutish uzoq bo'lganda ipni blokirovka qilishingiz kerak. Bu yondashuv deb atalmish amalga oshiriladi. gibrid dizaynlar. U yadro rejimi bilan bir xil konstruksiyalarga ega, ammo endi foydalanuvchi rejimi tsikli bilan: SemaphorSlim, ManualResetEventSlim va hokazo. Bu erda eng mashhur dizayn Monitor, chunki C# da taniqli mavjud lock sintaksis. Monitor Bu maksimal qiymati 1 (mutex) bo'lgan bir xil semafor, lekin tsiklda kutish, rekursiya, Shart o'zgaruvchan naqsh (quyida batafsilroq) va hokazolarni qo'llab-quvvatlaydi. Keling, u bilan yechimni ko'rib chiqaylik.

// Спрячем объект для Монитора от всех, чтобы без дедлоков.
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);
    }
}

Bu erda biz yana butun stolni vilkalarga kirishni to'sib qo'yamiz, ammo endi kimdir ovqatni tugatgandan so'ng qo'shnilar emas, balki bir vaqtning o'zida barcha iplarni blokdan chiqaramiz. Bular. Birinchidan, kimdir ovqatlanib, qo'shnilarni to'sib qo'yadi va bu kimdir tugatsa, lekin darhol yana ovqatlanmoqchi bo'lsa, u blokga kiradi va qo'shnilarini uyg'otadi, chunki uning kutish vaqti kamroq.

Shunday qilib, biz boshi berk ko'chadan va qandaydir faylasufning ochligidan qochamiz. Qisqa vaqtni kutish va ipni uzoq vaqt davomida blokirovka qilish uchun pastadirdan foydalanamiz. Hammani bir vaqtning o'zida blokdan chiqarish, yechimda bo'lgani kabi, faqat qo'shni blokdan chiqarilganidan ko'ra sekinroq AutoResetEvent, lekin farq katta bo'lmasligi kerak, chunki mavzular avval foydalanuvchi rejimida qolishi kerak.

У lock sintaksisda noxush kutilmagan hodisalar mavjud. Foydalanish tavsiya etiladi Monitor to'g'ridan-to'g'ri [Rixter] [Erik Lippert]. Ulardan biri shu lock har doim chiqadi Monitor, agar istisno mavjud bo'lsa ham, keyin boshqa mavzu umumiy xotira holatini o'zgartirishi mumkin. Bunday hollarda, ko'pincha boshi berk ko'chaga kirish yoki dasturni qandaydir tarzda xavfsiz tarzda tugatish yaxshiroqdir. Yana bir ajablanarli tomoni shundaki, Monitor soat bloklaridan foydalanadi (SyncBlock), barcha ob'ektlarda mavjud. Shuning uchun, agar nomaqbul ob'ekt tanlangan bo'lsa, siz osonlikcha o'liksiz qolishingiz mumkin (masalan, agar siz internirlangan satrni qulflasangiz). Buning uchun biz har doim yashirin ob'ektdan foydalanamiz.

Shartli o'zgaruvchan naqsh sizga ba'zi bir murakkab shartlarni kutishni yanada aniqroq amalga oshirish imkonini beradi. .NETda bu to'liq emas, menimcha, chunki... Nazariy jihatdan, bir qulfda emas, balki bir nechta o'zgaruvchilarda (Posix Threads-dagi kabi) bir nechta navbat bo'lishi kerak. Shunda ularni barcha faylasuflar uchun qilish mumkin edi. Ammo bu shaklda ham kodni qisqartirish imkonini beradi.

Ko'pgina faylasuflar yoki async / await

OK, endi biz iplarni samarali tarzda bloklashimiz mumkin. Ammo bizda faylasuflar ko'p bo'lsa-chi? 100? 10000? Misol uchun, biz veb-serverga 100000 4 so'rov oldik. Har bir so'rov uchun mavzu yaratish qimmatga tushadi, chunki shuning uchun ko'p iplar parallel ravishda bajarilmaydi. Faqat shuncha mantiqiy yadro bajariladi (menda XNUMX tasi bor). Qolganlarning hammasi resurslarni olib qo'yishadi. Ushbu muammoning yechimlaridan biri async/wait naqshidir. Uning g'oyasi shundaki, agar biror narsa davom etishini kutish kerak bo'lsa, funktsiya ipni ushlab turmaydi. Va biror narsa sodir bo'lganda, u o'z ijrosini davom ettiradi (lekin bir xil mavzuda bo'lishi shart emas!). Bizning holatda, biz vilkalar kutamiz.

SemaphoreSlim Buning uchun bor WaitAsync() usuli. Mana bu naqsh yordamida amalga oshirish.

// Запуск такой же, как раньше. Где-нибудь в программе:
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();
}

Bilan usul async / await makkor chekli holat mashinasiga tarjima qilinadi, u darhol ichki qismini qaytaradi Task. U orqali siz usul tugashini kutishingiz, uni bekor qilishingiz va Vazifa bilan bajarishingiz mumkin bo'lgan hamma narsani qilishingiz mumkin. Usul ichida davlat mashinasi bajarilishini nazorat qiladi. Xulosa shuki, agar kechikish bo'lmasa, u holda ijro sinxronlashtiriladi, agar mavjud bo'lsa, u holda ip chiqariladi. Buni yaxshiroq tushunish uchun ushbu davlat mashinasiga qarash yaxshiroqdir. Siz ulardan zanjir yaratishingiz mumkin async / await usullari.

Keling, sinab ko'raylik. 100 mantiqiy yadroli mashinada 4 ta faylasufning ishi, 8 soniya. Monitor bilan oldingi yechim faqat dastlabki 4 ta ipni bajardi va qolganlarini umuman bajarmadi. Ushbu 4 ta ipning har biri taxminan 2 ms bo'sh edi. Va async/await yechimi hammasini 100 ni bajardi, har bir kutish uchun o'rtacha 6.8 soniya. Albatta, haqiqiy tizimlarda 6 soniya bo'sh turish qabul qilinishi mumkin emas va juda ko'p so'rovlarni shu tarzda qayta ishlamaslik yaxshiroqdir. Monitor bilan yechim umuman kengaytirib bo'lmaydigan bo'lib chiqdi.

xulosa

Ushbu kichik misollardan ko'rinib turibdiki, .NET ko'plab sinxronizatsiya konstruksiyalarini qo'llab-quvvatlaydi. Biroq, ulardan qanday foydalanish har doim ham aniq emas. Umid qilamanki, bu maqola foydali bo'ldi. Biz buni hozircha yakunlaymiz, ammo hali ham juda ko'p qiziqarli narsalar bor, masalan, iplar uchun xavfsiz to'plamlar, TPL Dataflow, Reaktiv dasturlash, Software Transaction modeli va boshqalar.

Axborot manbalari

• Oqim vizualizatsiyasi: Bir vaqtning o'zida vizualizator
• MSDN: Tishli, Asinxron dasturlash naqshlari va boshqalar va boshqalar.
• [Rixter] — C# orqali CLR, Jeffri Rixter
• [Erik Lippert] - Qulf haqida
• Manba kodi
• Rasm - "Qilichlar orasida raqs", G. Semiradskiy

Manba: www.habr.com