Well-Fed Philosophers o Competitive .NET Programming

Atong tan-awon kon sa unsang paagi naglihok ang dungan ug parallel nga programming sa .Net, gamit ang Philosophers Dining Problem isip pananglitan. Ang plano mao kini, gikan sa pag-synchronize sa mga hilo / proseso, ngadto sa modelo sa aktor (sa mosunod nga mga bahin). Ang artikulo mahimong mapuslanon alang sa unang kaila o aron ma-refresh ang imong kahibalo.

Nganong buhaton man kini? Ang mga transistor nakaabot sa ilang minimum nga gidak-on, ang balaod ni Moore nagdepende sa limitasyon sa katulin sa kahayag ug busa usa ka pagtaas ang nakita sa gidaghanon, mas daghang transistor ang mahimo. Sa samang higayon, ang gidaghanon sa datos nagkadako, ug ang mga tiggamit nagpaabot sa diha-diha nga tubag gikan sa mga sistema. Sa ingon nga sitwasyon, ang "normal" nga pagprograma, kung kita adunay usa nga nagpatuman sa thread, dili na epektibo. Kinahanglan nimo nga masulbad ang problema sa dungan o dungan nga pagpatay. Dugang pa, kini nga problema anaa sa lainlaing lebel: sa lebel sa mga hilo, sa lebel sa mga proseso, sa lebel sa mga makina sa network (giapod-apod nga mga sistema). Ang .NET adunay taas nga kalidad, nasulayan sa panahon nga mga teknolohiya alang sa dali ug episyente nga pagsulbad sa maong mga problema.

Tumong

Gihatag ni Edsger Dijkstra kini nga problema sa iyang mga estudyante kaniadtong 1965. Ang natukod nga pormula mao ang mosunod. Adunay usa ka piho (kasagaran lima) nga gidaghanon sa mga pilosopo ug parehas nga gidaghanon sa mga tinidor. Nanglingkod sila sa lingin nga lamesa, mga tinidor sa tunga nila. Ang mga pilosopo makakaon gikan sa ilang mga plato sa walay katapusan nga pagkaon, maghunahuna o maghulat. Aron makakaon sa usa ka pilosopo, kinahanglan ka nga magkuha og duha ka mga tinidor (ang naulahi nakigbahin sa tinidor sa una). Ang pagkuha ug pagbutang og tinidor duha ka managlahing aksyon. Ang tanang pilosopo hilom. Ang tahas mao ang pagpangita sa ingon nga algorithm nga silang tanan maghunahuna ug mapuno bisan pagkahuman sa 54 ka tuig.

Una, atong sulayan pagsulbad kini nga problema pinaagi sa paggamit sa usa ka shared space. Ang mga tinidor nahimutang sa komon nga lamesa ug ang mga pilosopo nagkuha lang niini kung anaa na sila ug ibalik kini. Dinhi adunay mga problema sa pag-synchronize, kanus-a eksakto ang pagkuha sa mga surebets? what if walay tinidor? ug uban pa. Apan una, atong sugdan ang mga pilosopo.

Aron masugdan ang mga hilo, gigamit namon ang usa ka pool sa hilo Task.Run pamaagi:

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

Ang thread pool gidisenyo aron ma-optimize ang paghimo ug pagtangtang sa thread. Kini nga pool adunay pila nga adunay mga buluhaton ug ang CLR nagmugna o nagtangtang sa mga hilo depende sa gidaghanon niini nga mga buluhaton. Usa ka pool alang sa tanan nga AppDomains. Kini nga pool kinahanglan nga gamiton hapit kanunay, tungod kay. dili kinahanglan nga magsamok sa paghimo, pagtangtang sa mga hilo, sa ilang mga pila, ug uban pa. Posible nga wala’y pool, apan kinahanglan nimo nga gamiton kini direkta Thread, kini mapuslanon alang sa mga kaso kung kinahanglan nimo nga usbon ang prayoridad sa usa ka hilo, kung kami adunay taas nga operasyon, alang sa usa ka Foreground nga hilo, ug uban pa.

Sa ato pa, System.Threading.Tasks.Task parehas ra ang klase Thread, apan uban sa tanan nga mga matang sa kasayon: ang abilidad sa pagpadagan sa usa ka buluhaton human sa usa ka block sa ubang mga buluhaton, ibalik kini gikan sa mga gimbuhaton, sayon ​​nga makabalda niini, ug uban pa. ug uban pa. Sila gikinahanglan aron suportahan ang async / maghulat nga mga konstruksyon (Task-based Asynchronous Pattern, syntactic sugar para sa paghulat sa mga operasyon sa IO). Atong hisgotan kini sa ulahi.

CancelationTokenSource dinhi kini gikinahanglan aron ang hilo makahunong sa iyang kaugalingon sa signal sa calling thread.

Mga Isyu sa Pag-sync

Gi-block nga mga Pilosopo

Okay, nahibal-an namon kung giunsa paghimo ang mga hilo, sulayan naton ang paniudto:

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

Dinhi una natong sulayan ang pagkuha sa wala nga tinidor, ug dayon ang tuo nga tinidor, ug kung kini molihok, nan kita mokaon ug ibalik kini. Ang pagkuha sa usa ka tinidor kay atomic, i.e. Ang duha ka mga hilo dili makakuha sa usa sa samang higayon (dili husto: ang una nagbasa nga ang tinidor libre, ang ikaduha - usab, ang una gikuha, ang ikaduha gikuha). Alang niini Interlocked.CompareExchange, nga kinahanglang ipatuman uban ang instruksiyon sa processor (TSL, XCHG), nga nag-lock sa usa ka piraso sa memorya alang sa atomic sequential nga pagbasa ug pagsulat. Ug ang SpinWait katumbas sa pagtukod while(true) lamang sa usa ka gamay nga "salamangka" - ang hilo nagkinahanglan sa processor (Thread.SpinWait), pero usahay ibalhin ang kontrol sa laing thread (Thread.Yeild) o makatulog (Thread.Sleep).

Apan kini nga solusyon dili molihok, tungod kay ang mga agos sa dili madugay (alang kanako sulod sa usa ka segundo) gibabagan: ang tanan nga mga pilosopo mikuha sa ilang wala nga tinidor, apan dili ang tuo. Ang forks array unya adunay mga kantidad: 1 2 3 4 5.

Sa numero, gibabagan ang mga hilo (deadlock). Berde - pagpatay, pula - pag-synchronize, abohon - ang hilo natulog. Gipakita sa mga rhombus ang oras sa pagsugod sa Mga Buluhaton.

Ang Kagutom sa mga Pilosopo

Bisan kung dili kinahanglan nga maghunahuna labi na ang daghang pagkaon, apan ang kagutom naghimo sa bisan kinsa nga mohunong sa pilosopiya. Atong sulayan nga masundog ang kahimtang sa kagutom sa mga hilo sa atong problema. Ang kagutom mao kung ang usa ka hilo nagdagan, apan kung wala’y hinungdanon nga trabaho, sa ato pa, parehas kini nga deadlock, karon lang ang hilo wala natulog, apan aktibo nga nangita usa ka makaon, apan wala’y pagkaon. Aron malikayan ang kanunay nga pagbabag, among ibalik ang tinidor kung dili kami makakuha og lain.

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

Ang importante nga butang mahitungod niini nga code mao nga ang duha sa upat ka mga pilosopo nakalimot sa pagbutang sa ilang wala nga tinidor. Ug kini nahimo nga sila mokaon og daghang pagkaon, samtang ang uban nagsugod sa kagutom, bisan kung ang mga hilo adunay parehas nga prayoridad. Dinhi sila dili hingpit nga gigutom, tungod kay. Ang dili maayo nga mga pilosopo nagbutang sa ilang mga tinidor balik usahay. Nahibal-an nga ang maayo nga mga tawo mokaon mga 5 ka beses nga mas ubos kaysa daotan. Mao nga ang usa ka gamay nga sayup sa code nagdala sa usa ka pagkunhod sa pasundayag. Angay usab nga hinumdoman dinhi nga ang usa ka talagsaon nga sitwasyon posible kung ang tanan nga mga pilosopo mokuha sa wala nga tinidor, wala’y tuo, gibutang nila ang wala, maghulat, kuhaa usab ang wala, ug uban pa. Kini nga sitwasyon usa usab ka kagutom, nga sama sa usa ka deadlock. Napakyas ko sa pagsubli niini. Sa ubos mao ang usa ka hulagway alang sa usa ka sitwasyon diin ang duha ka dili maayo nga mga pilosopo mikuha sa duha ka tinidor ug duha ka maayo nga gigutom.

Dinhi imong makita nga ang mga hilo makamata usahay ug mosulay sa pagkuha sa kapanguhaan. Ang duha sa upat ka mga core walay mahimo (berde nga graph sa ibabaw).

Kamatayon sa usa ka Pilosopo

Buweno, ang laing problema nga makabalda sa usa ka mahimayaon nga panihapon sa mga pilosopo mao kung ang usa kanila kalit nga mamatay nga adunay mga tinidor sa iyang mga kamot (ug ila siyang ilubong sa ingon). Unya ang mga silingan mabiyaan nga walay paniudto. Makahimo ka og usa ka pananglitan nga code alang niini nga kaso sa imong kaugalingon, pananglitan, kini gilabay NullReferenceException pagkahuman gikuha sa pilosopo ang mga tinidor. Ug, sa tinuud, ang eksepsiyon dili madumala ug ang code sa pagtawag dili lang makuha kini (alang niini AppDomain.CurrentDomain.UnhandledException ug uban pa). Busa, ang mga tigdumala sa sayup gikinahanglan sa mga hilo sa ilang kaugalingon ug uban ang madanihon nga pagtapos.

Ang waiter

Okay, unsaon nato pagsulbad kining deadlock, kagutom, ug problema sa kamatayon? Gitugotan ra namon ang usa ka pilosopo nga makaabut sa mga tinidor, magdugang usa ka us aka pagbulag sa mga hilo alang sa kini nga lugar. Unsaon pagbuhat niini? Pananglit adunay usa ka waiter sunod sa mga pilosopo nga naghatag pagtugot sa bisan kinsa nga pilosopo sa pagkuha sa mga tinidor. Giunsa naton paghimo kini nga waiter ug kung giunsa mangutana ang mga pilosopo kaniya, ang mga pangutana makapaikag.

Ang pinakasimple nga paagi mao kung ang mga pilosopo kanunay nga mangutana sa waiter alang sa pag-access sa mga tinidor. Mga. karon ang mga pilosopo dili na maghulat sa usa ka tinidor sa duol, apan maghulat o mangutana sa waiter. Sa sinugdan, gigamit lang namo ang User Space alang niini, niini wala kami mogamit og mga interrupts sa pagtawag sa bisan unsang mga pamaagi gikan sa kernel (mahitungod niini sa ubos).

Mga solusyon sa wanang sa tiggamit

Dinhi atong buhaton sama sa atong gibuhat kaniadto sa usa ka tinidor ug duha ka pilosopo, kita magtuyok sa usa ka cycle ug maghulat. Apan karon kini mahimong tanan nga mga pilosopo ug, ingon nga kini, usa lamang ka tinidor, i.e. maingon nga ang pilosopo lang nga mikuha niining “golden fork” gikan sa waiter ang mokaon. Alang niini among gigamit ang 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 kini mao ang usa ka blocker, uban sa, halos sa pagsulti, sa mao gihapon nga while(true) { if (!lock) break; }, apan adunay mas daghang "magic" kaysa sa SpinWait (nga gigamit didto). Karon nahibal-an na niya kung giunsa ang pag-ihap sa mga naghulat, gipakatulog sila gamay, ug daghan pa. ug uban pa. Sa kinatibuk-an, gibuhat ang tanan nga posible aron ma-optimize. Apan kinahanglan natong hinumdoman nga kini mao gihapon ang sama nga aktibo nga siklo nga mokaon sa mga kapanguhaan sa processor ug magpadayon sa pag-agos, nga mahimong mosangpot sa kagutom kung ang usa sa mga pilosopo mahimong mas prayoridad kay sa uban, apan walay bulawan nga tinidor (Priority Inversion nga problema) . Busa, gigamit lang namo kini alang sa mubo kaayo nga mga pagbag-o sa gipaambit nga panumduman, nga walay bisan unsang mga tawag sa ikatulo nga partido, mga nested lock, ug uban pang mga surpresa.

Pagdrowing para sa SpinLock. Ang mga sapa kanunay nga "nag-away" alang sa bulawan nga tinidor. Adunay mga kapakyasan - sa numero, ang napili nga lugar. Ang mga cores dili hingpit nga gigamit: mga 2/3 lamang niining upat ka mga hilo.

Ang laing solusyon dinhi mao ang paggamit lamang Interlocked.CompareExchange nga adunay parehas nga aktibo nga paghulat sama sa gipakita sa kodigo sa ibabaw (sa gigutom nga mga pilosopo), apan kini, ingon sa giingon na, mahimo’g theoretically mosangput sa pagbabag.

sa Interlocked Kini kinahanglan nga matikdan nga adunay dili lamang CompareExchange, apan uban pang mga pamaagi alang sa atomic read AND write. Ug pinaagi sa pagsubli sa pagbag-o, kung ang lain nga hilo adunay panahon sa paghimo sa mga pagbag-o niini (basaha ang 1, basaha ang 2, isulat ang 2, isulat ang 1 dili maayo), mahimo kini gamiton alang sa komplikado nga mga pagbag-o sa usa ka kantidad (Interlocked Anything pattern) .

Mga Solusyon sa Kernel Mode

Aron malikayan ang pag-usik sa mga kapanguhaan sa usa ka loop, tan-awon naton kung giunsa naton ma-block ang usa ka hilo. Sa laing pagkasulti, sa pagpadayon sa atong panig-ingnan, atong tan-awon kon sa unsang paagi gipakatulog sa waiter ang pilosopo ug gipukaw lamang siya kung gikinahanglan. Una, atong tan-awon kon unsaon pagbuhat niini pinaagi sa kernel mode sa operating system. Ang tanan nga mga istruktura sa kasagaran mas hinay kaysa sa naa sa wanang sa tiggamit. Daghang mga higayon nga hinay, pananglitan AutoResetEvent tingali 53 ka beses nga hinay SpinLock [Richter]. Apan sa ilang tabang, mahimo nimong i-synchronize ang mga proseso sa tibuuk nga sistema, madumala o dili.

Ang batakang pagtukod dinhi mao ang semaphore nga gisugyot ni Dijkstra kapin sa tunga sa siglo ang milabay. Ang usa ka semaphore, sa yano nga pagkasulti, usa ka positibo nga integer nga gidumala sa sistema, ug duha nga mga operasyon niini, pag-uswag ug pagkunhod. Kung kini mapakyas sa pagkunhod, zero, nan ang hilo sa pagtawag gibabagan. Kung ang numero gidugangan sa ubang aktibo nga hilo/proseso, nan ang mga hilo gilaktawan ug ang semaphore gipaubos pag-usab sa gidaghanon nga gipasa. Ang usa makahanduraw sa mga tren sa usa ka bottleneck nga adunay semaphore. Nagtanyag ang .NET og daghang mga konstruksyon nga adunay parehas nga gamit: AutoResetEvent, ManualResetEvent, Mutex ug sa akong kaugalingon Semaphore. Atong gamiton AutoResetEvent, mao kini ang pinakayano niini nga mga konstruksyon: duha lamang ka mga kantidad 0 ug 1 (bakak, tinuod). Iyang Pamaagi WaitOne() gibabagan ang hilo sa pagtawag kung 0 ang kantidad, ug kung 1, ipaubos kini sa 0 ug laktawan kini. Usa ka pamaagi Set() mosaka ngadto sa 1 ug mopalusot sa usa ka waiter, kinsa mopaubos pag-usab ngadto sa 0. Molihok sama sa usa ka subway turnstile.

Himoon nga komplikado ang solusyon ug gamiton ang kandado alang sa matag pilosopo, ug dili alang sa tanan sa usa ka higayon. Mga. karon mahimo nga adunay daghang mga pilosopo sa usa ka higayon, ug dili usa. Apan gibabagan na usab namo ang pag-access sa lamesa aron sa husto, paglikay sa mga lumba (kondisyon sa lumba), pagkuha og surebets.

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

Aron masabtan kung unsa ang nahitabo dinhi, tagda ang kaso kung ang pilosopo napakyas sa pagkuha sa mga tinidor, unya ang iyang mga aksyon mahimong ingon sa mosunod. Naghulat siya nga makaadto sa lamesa. Sa pagkadawat niini, siya misulay sa pagkuha sa mga tinidor. Wala molampos. Naghatag kini og access sa lamesa (mutual exclusion). Ug gipasa ang iyang "turnstile" (AutoResetEvent) (sa sinugdan sila bukas). Mobalik kini sa siklo, tungod kay wala siyay mga tinidor. Siya misulay sa pagkuha kanila ug mihunong sa iyang "turnstile". Ang ubang mas swerte nga silingan sa tuo o wala, pagkahuman sa pagkaon, giablihan ang among pilosopo, "pag-abli sa iyang turnstile." Gipasa kini sa atong pilosopo (ug gisirad-an kini) sa ikaduhang higayon. Gisulayan niya sa ikatulong higayon ang pagkuha sa mga tinidor. Good luck. Ug gipasa niya ang iyang turnstile aron manihapon.

Kung adunay mga random nga sayup sa ingon nga code (kanunay sila nga naglungtad), pananglitan, ang usa ka silingan dili husto nga gipiho o ang parehas nga butang gihimo AutoResetEvent para sa tanan (Enumerable.Repeat), unya ang mga pilosopo maghulat alang sa mga developers, tungod kay Ang pagpangita sa mga sayup sa ingon nga code usa ka lisud nga buluhaton. Ang laing problema sa kini nga solusyon mao nga dili kini garantiya nga ang pila ka pilosopo dili gutomon.

Hybrid nga mga Solusyon

Gitan-aw namo ang duha ka pamaagi sa timing, kung magpabilin kami sa user mode ug loop, ug kung among gibabagan ang thread pinaagi sa kernel. Ang una nga pamaagi maayo alang sa mugbo nga mga kandado, ang ikaduha alang sa taas. Kasagaran kinahanglan nga una nga maghulat sa kadali alang sa usa ka variable nga mausab sa usa ka loop, ug dayon babagan ang hilo kung ang paghulat dugay. Kini nga pamaagi gipatuman sa gitawag nga. hybrid nga mga istruktura. Ania ang parehas nga mga konstruksyon sama sa kernel mode, apan karon adunay usa ka user mode loop: SemaphorSlim, ManualResetEventSlim ug uban pa. Ang pinakasikat nga desinyo dinhi mao Monitor, kay sa C# naay usa ka ilado lock syntax. Monitor kini mao ang sama nga semaphore uban sa usa ka maximum nga bili sa 1 (mutex), apan uban sa suporta alang sa paghulat sa usa ka loop, recursion, ang Condition Variable pattern (labaw pa niana sa ubos), ug uban pa Atong tan-awon ang usa ka solusyon niini.

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

Dinhi gibabagan na usab namon ang tibuuk nga lamesa aron ma-access ang mga tinidor, apan karon gi-unblock namon ang tanan nga mga hilo sa usa ka higayon, ug dili mga silingan kung adunay usa nga nakahuman sa pagkaon. Mga. una, adunay mokaon ug mobabag sa mga silingan, ug kung kini adunay usa nga makahuman, apan gusto nga mokaon pag-usab, siya moadto sa blocking ug pukawon ang iyang mga silingan, tungod kay. gamay ra ang oras sa paghulat niini.

Mao kini ang paagi nga malikayan nato ang mga deadlock ug ang kagutom sa pipila ka pilosopo. Gigamit namon ang usa ka laang alang sa usa ka mubo nga paghulat ug gibabagan ang hilo sa usa ka taas. Ang pag-unblock sa tanan sa usa ka higayon mas hinay kaysa kung ang silingan ra ang gi-unblock, sama sa solusyon sa AutoResetEvent, apan ang kalainan kinahanglan dili dako, tungod kay Ang mga hilo kinahanglang magpabilin una sa user mode.

У lock Ang syntax adunay dili maayo nga mga sorpresa. Girekomenda nga gamiton Monitor direkta [Richter] [Eric Lippert]. Usa niini mao kana lock kanunay gawas sa Monitor, bisan kung adunay usa ka eksepsiyon, diin ang laing hilo mahimong makausab sa gipaambit nga kahimtang sa panumduman. Sa ingon nga mga kaso, kasagaran mas maayo nga moadto sa deadlock o bisan unsang paagi nga luwas nga tapuson ang programa. Ang laing katingala mao nga ang Monitor naggamit sa mga bloke sa pag-synchronize (SyncBlock), nga anaa sa tanang butang. Busa, kung gipili ang usa ka dili angay nga butang, dali ka makakuha usa ka deadlock (pananglitan, kung imong gi-lock ang usa ka interned string). Gigamit namo ang kanunay nga tinago nga butang alang niini.

Gitugotan ka sa Condition Variable pattern nga mas mubu nga ipatuman ang pagpaabut sa pipila ka komplikado nga kondisyon. Sa .NET, kini dili kompleto, sa akong opinyon, tungod kay sa teorya, kinahanglan adunay daghang mga pila sa daghang mga variable (sama sa Posix Threads), ug dili sa usa ka lok. Unya ang usa makahimo kanila alang sa tanan nga mga pilosopo. Apan bisan sa kini nga porma, gitugotan ka nga makunhuran ang code.

daghang pilosopo o async / await

Okay, karon epektibo namong ma-block ang mga thread. Apan komosta kon daghan kitag pilosopo? 100? 10000? Pananglitan, nakadawat kami og 100000 ka hangyo sa web server. Kini mahimong overhead sa paghimo sa usa ka hilo alang sa matag hangyo, tungod kay daghan kaayong mga hilo ang dili magkaparehas. Modagan ra kutob sa adunay lohikal nga mga cores (ako adunay 4). Ug ang tanan mokuha lang sa mga kahinguhaan. Usa ka solusyon sa kini nga problema mao ang async / naghulat nga pattern. Ang ideya niini mao nga ang function wala magkupot sa hilo kung kinahanglan nga maghulat alang sa usa ka butang nga magpadayon. Ug sa diha nga kini adunay usa ka butang, kini nagpadayon sa pagpatuman niini (apan dili kinahanglan sa parehas nga hilo!). Sa among kaso, maghulat kami sa tinidor.

SemaphoreSlim adunay alang niini WaitAsync() pamaagi. Ania ang usa ka pagpatuman gamit kini nga sumbanan.

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

Pamaagi uban sa async / await gihubad ngadto sa usa ka tricky state machine nga diha-diha dayon mibalik sa iyang internal Task. Pinaagi niini, makahulat ka sa pagkompleto sa pamaagi, kanselahon kini, ug tanan nga mahimo nimo sa Task. Sa sulod sa pamaagi, ang makina sa estado nagkontrol sa pagpatay. Ang hinungdan mao nga kung wala’y paglangan, nan ang pagpatay dungan, ug kung adunay, nan ang hilo gibuhian. Alang sa mas maayo nga pagsabot niini, mas maayo nga tan-awon kini nga makina sa estado. Makahimo ka og mga kadena gikan niini async / await mga pamaagi.

Testingan ta. Trabaho sa 100 ka pilosopo sa usa ka makina nga adunay 4 logical cores, 8 segundos. Ang miaging solusyon sa Monitor nagpadagan lamang sa una nga 4 nga mga hilo ug ang nahabilin wala gyud modagan. Ang matag usa niining 4 ka mga hilo walay trabaho sulod sa mga 2ms. Ug ang async / maghulat nga solusyon nagdagan sa tanan nga 100, nga adunay average nga paghulat nga 6.8 segundos matag usa. Siyempre, sa tinuod nga mga sistema, ang idle sa 6 segundos dili madawat ug mas maayo nga dili iproseso ang daghang mga hangyo nga sama niini. Ang solusyon sa Monitor nahimo nga dili scalable sa tanan.

konklusyon

Sama sa imong makita gikan niining gagmay nga mga pananglitan, ang .NET nagsuporta sa daghang mga pagtukod sa pag-synchronize. Bisan pa, dili kanunay klaro kung giunsa kini gamiton. Nanghinaut ko nga kini nga artikulo makatabang. Sa pagkakaron, kini ang katapusan, apan adunay daghan pa nga makapaikag nga mga butang nga nahabilin, pananglitan, mga koleksyon nga luwas sa thread, TPL Dataflow, Reactive programming, Software Transaction model, ug uban pa.

Mga tinubdan

• Pagtan-aw sa dagan: Concurrency Visualizer
• MSDN: Paglusot, Asynchronous nga mga pattern sa programming ug uban pa sa uban
• [Richter] - CLR pinaagi sa C#, Jeffrey Richter
• [Eric Lippert] - Mahitungod sa lock
• Source code
• Hulagway - "Sayaw taliwala sa mga espada", G. Semiradsky

Source: www.habr.com