Busog na mga pilosopo o mapagkumpitensyang programming sa .NET

Tingnan natin kung paano gumagana ang concurrent at parallel programming sa .Net, gamit ang halimbawa ng problema sa lunching philosophers. Ang plano ay ang mga sumusunod, mula sa pag-synchronize ng thread/proseso hanggang sa modelo ng aktor (sa mga sumusunod na bahagi). Ang artikulo ay maaaring maging kapaki-pakinabang para sa isang unang kakilala o upang i-refresh ang iyong kaalaman.

Bakit alam mo pa kung paano gawin ito? Ang mga transistor ay umaabot na sa kanilang pinakamababang sukat, ang batas ni Moore ay umaabot sa limitasyon ng bilis ng liwanag, at samakatuwid ang paglaki ay sinusunod sa mga numero; mas maraming transistor ang maaaring gawin. Kasabay nito, lumalaki ang dami ng data, at inaasahan ng mga user ang agarang tugon mula sa mga system. Sa ganoong sitwasyon, ang "normal" na programming, kapag mayroon kaming isang executing thread, ay hindi na epektibo. Kailangan nating lutasin ang problema ng sabay-sabay o sabay-sabay na pagpapatupad. Bukod dito, ang problemang ito ay umiiral sa iba't ibang antas: sa antas ng thread, sa antas ng proseso, sa antas ng mga makina sa network (mga distributed system). Ang .NET ay may mataas na kalidad, nasubok sa oras na mga teknolohiya para sa mabilis at mahusay na paglutas ng mga naturang problema.

Gawain

Tinanong ni Edsger Dijkstra ang problemang ito sa kanyang mga estudyante noong 1965. Ang itinatag na pormulasyon ay ang mga sumusunod. Mayroong tiyak (karaniwang limang) bilang ng mga pilosopo at kaparehong bilang ng mga tinidor. Nakaupo sila sa isang round table, mga tinidor sa pagitan nila. Ang mga pilosopo ay maaaring kumain mula sa kanilang mga plato ng walang katapusang pagkain, mag-isip o maghintay. Upang kumain, ang isang pilosopo ay kailangang kumuha ng dalawang tinidor (ang huli ay nagbabahagi ng isang tinidor sa una). Ang pagkuha at pagbaba ng tinidor ay dalawang magkahiwalay na aksyon. Tahimik ang lahat ng pilosopo. Ang gawain ay upang mahanap ang gayong algorithm upang silang lahat ay mag-isip at mabusog kahit na pagkatapos ng 54 na taon.

Una, subukan nating lutasin ang problemang ito sa pamamagitan ng paggamit ng shared space. Ang mga tinidor ay nakahiga sa karaniwang mesa at ang mga pilosopo ay kinuha lamang ito kapag sila ay naroroon at ibinalik ang mga ito. Ito ay kung saan ang mga problema sa pag-synchronize ay lumitaw, kailan eksaktong kumuha ng mga tinidor? ano ang gagawin kung walang plug? atbp. Ngunit una, magsimula tayo sa mga pilosopo.

Para magsimula ng mga thread, gumagamit kami ng thread pool sa pamamagitan ng Task.Run paraan:

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 ay idinisenyo upang i-optimize ang paggawa at pag-alis ng mga thread. Ang pool na ito ay may pila ng mga gawain at ang CLR ay gumagawa o nagtatanggal ng mga thread depende sa bilang ng mga gawaing ito. Isang pool para sa lahat ng AppDomains. Ang pool na ito ay dapat gamitin halos palagi, dahil... hindi na kailangang mag-abala sa paggawa at pagtanggal ng mga thread, kanilang mga pila, atbp. Magagawa mo ito nang walang pool, ngunit pagkatapos ay kakailanganin mong gamitin ito nang direkta Thread, ito ay kapaki-pakinabang para sa mga kaso kung kailan kailangan nating baguhin ang priyoridad ng isang thread, kapag mayroon tayong mahabang operasyon, para sa isang Foreground na thread, atbp.

Sa ibang salita, System.Threading.Tasks.Task pareho ang klase Thread, ngunit sa lahat ng uri ng kaginhawahan: ang kakayahang maglunsad ng isang gawain pagkatapos ng isang bloke ng iba pang mga gawain, ibalik ang mga ito mula sa mga pag-andar, maginhawang matakpan ang mga ito, at marami pa. atbp. Kinakailangan ang mga ito upang suportahan ang mga async/naghihintay na mga konstruksyon (Task-based Asynchronous Pattern, syntactic sugar para sa paghihintay sa mga operasyon ng IO). Pag-uusapan natin ito mamaya.

CancelationTokenSource dito ito ay kinakailangan na ang thread ay maaaring wakasan ang sarili sa isang senyas mula sa pagtawag thread.

Mga Isyu sa Pag-sync

Naka-block na mga pilosopo

Okay, alam namin kung paano gumawa ng mga thread, subukan natin ang tanghalian:

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

Dito muna natin sinubukang kunin ang kaliwa at pagkatapos ay ang kanang tinidor, at kung ito ay gumagana, tayo ay kumakain at ibinalik ang mga ito. Ang pagkuha ng isang tinidor ay atomic, i.e. dalawang thread ay hindi maaaring kumuha ng isa sa parehong oras (mali: ang una ay nagbabasa na ang tinidor ay libre, ang pangalawa ay pareho, ang una ay tumatagal, ang pangalawa ay tumatagal). Para dito Interlocked.CompareExchange, na dapat ipatupad gamit ang pagtuturo ng processor (TSL, XCHG), na nagla-lock ng isang piraso ng memorya para sa atomic sequential na pagbasa at pagsulat. At ang SpinWait ay katumbas ng konstruksyon while(true) lamang sa isang maliit na "magic" - ang thread ay tumatagal ng processor (Thread.SpinWait), ngunit kung minsan ay nagpapasa ng kontrol sa isa pang thread (Thread.Yeild) o matutulog (Thread.Sleep).

Ngunit ang solusyon na ito ay hindi gumagana, dahil... ang mga thread sa lalong madaling panahon (sa loob ng isang segundo para sa akin) ay naharang: lahat ng mga pilosopo ay kumukuha ng kanilang kaliwang tinidor, ngunit walang tama. Ang hanay ng mga tinidor ay mayroong mga halaga: 1 2 3 4 5.

Sa larawan, hinaharangan ang mga thread (deadlock). Ang berde ay nagpapahiwatig ng pagpapatupad, ang pula ay nagpapahiwatig ng pag-synchronize, at ang kulay abo ay nagpapahiwatig na ang thread ay natutulog. Ipinapahiwatig ng mga diamante ang oras ng paglulunsad ng Mga Gawain.

Ang Pagkagutom ng mga Pilosopo

Bagama't hindi mo kailangan ng maraming pagkain para makapag-isip, mapipilitan ng gutom ang sinuman na talikuran ang pilosopiya. Subukan nating gayahin ang sitwasyon ng thread starvation sa ating problema. Ang gutom ay kapag ang isang thread ay gumagana, ngunit walang makabuluhang trabaho, sa madaling salita, ito ay parehong deadlock, ngayon lamang ang thread ay hindi natutulog, ngunit aktibong naghahanap ng makakain, ngunit walang pagkain. Upang maiwasan ang madalas na pagharang, ibabalik namin ang tinidor kung hindi na namin makuha ang isa pa.

// То же что и в 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 mahalaga sa code na ito ay nakalimutan ng dalawa sa apat na pilosopo na ibaba ang kanilang kaliwang tinidor. At lumalabas na kumakain sila ng mas maraming pagkain, at ang iba ay nagsisimulang magutom, kahit na ang mga thread ay may parehong priyoridad. Dito hindi sila ganap na nagugutom, dahil... ang masasamang pilosopo kung minsan ay nagbabalik ng kanilang mga tinidor. Lumalabas na ang mga mabubuti ay kumakain ng halos 5 beses na mas mababa kaysa sa mga masama. Kaya ang isang maliit na error sa code ay humahantong sa isang pagbaba sa pagganap. Dito ay nararapat ding tandaan na ang isang bihirang sitwasyon ay posible kapag ang lahat ng mga pilosopo ay kunin ang kaliwang tinidor, walang kanan, inilagay nila ang kaliwa pababa, maghintay, kunin muli ang kaliwa, atbp. Ang sitwasyong ito ay gutom din, higit na katulad ng pagbara sa isa't isa. Hindi ko na naulit. Nasa ibaba ang isang larawan para sa isang sitwasyon kung saan dalawang masasamang pilosopo ang kumuha ng parehong tinidor, at dalawang mabubuti ay nagugutom.

Dito makikita mo na ang mga thread kung minsan ay nagigising at sumusubok na kumuha ng mapagkukunan. Dalawa sa apat na core ay walang ginagawa (berdeng graph sa itaas).

Kamatayan ng isang Pilosopo

Buweno, ang isa pang problema na maaaring makagambala sa maluwalhating hapunan ng mga pilosopo ay kung ang isa sa kanila ay biglang namatay na may mga tinidor sa kanyang mga kamay (at siya ay ililibing sa ganoong paraan). Pagkatapos ay maiiwan ang mga kapitbahay na walang tanghalian. Maaari kang gumawa ng isang halimbawa ng code para sa kasong ito sa iyong sarili, halimbawa ito ay itinapon NullReferenceException pagkatapos kunin ng pilosopo ang mga tinidor. At, sa pamamagitan ng paraan, ang pagbubukod ay hindi hahawakan at ang code sa pagtawag ay hindi basta-basta mahuhuli (para dito AppDomain.CurrentDomain.UnhandledException at iba pa.). Samakatuwid, ang mga humahawak ng error ay kinakailangan sa mga thread mismo at may magandang pagwawakas.

Ang weyter

Okay, paano natin malulutas ang problemang ito ng deadlocks, gutom, at pagkamatay? Papayagan lamang namin ang isang pilosopo sa mga tinidor, at magdaragdag kami ng kapwa pagbubukod ng mga thread para sa lugar na ito. Paano ito gagawin? Ipagpalagay na sa tabi ng mga pilosopo ay may isang waiter na nagbibigay ng pahintulot sa isang pilosopo na kumuha ng mga tinidor. Kung paano natin gagawin ang waiter na ito at kung paano tatanungin siya ng mga pilosopo ay mga interesanteng tanong.

Ang pinakasimpleng paraan ay para sa mga pilosopo na patuloy na magtanong sa waiter para sa access sa mga tinidor. Yung. Ngayon ang mga pilosopo ay hindi maghihintay ng isang tinidor sa malapit, ngunit maghintay o magtanong sa waiter. Sa una ay gumagamit lamang kami ng User Space para dito; hindi kami gumagamit ng mga interrupts para tumawag ng anumang mga pamamaraan mula sa kernel (higit pa sa mga ito sa ibaba).

Mga solusyon sa espasyo ng gumagamit

Dito ay gagawin natin ang parehong bagay na ginawa natin noon sa isang tinidor at dalawang pilosopo, iikot tayo sa isang loop at maghihintay. Ngunit ngayon ito ay magiging lahat ng mga pilosopo at, kumbaga, isang tinidor lamang, i.e. masasabi nating ang pilosopo na kumuha ng “gintong tinidor” na ito sa waiter ang kakain. Upang gawin ito, ginagamit namin 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 ito ay isang blocker, na may, halos pagsasalita, pareho while(true) { if (!lock) break; }, ngunit may higit pang "magic" kaysa sa in SpinWait (na ginagamit doon). Ngayon alam na niya kung paano bilangin ang mga naghihintay, pinatulog sila ng kaunti, at marami pang iba. atbp. Sa pangkalahatan, ginagawa nito ang lahat ng posible upang ma-optimize. Ngunit dapat nating tandaan na ito pa rin ang parehong aktibong loop na kumakain ng mga mapagkukunan ng processor at may hawak na isang thread, na maaaring humantong sa gutom kung ang isa sa mga pilosopo ay magiging mas priyoridad kaysa sa iba, ngunit walang ginintuang tinidor (Priority Inversion problem ). Samakatuwid, ginagamit lang namin ito para sa napakaikling pagbabago sa nakabahaging memorya, nang walang anumang mga third-party na tawag, nested lock, o iba pang mga sorpresa.

Pagguhit para sa SpinLock. Ang mga batis ay patuloy na "naglalaban" para sa gintong tinidor. Nangyayari ang mga pagkabigo - ang naka-highlight na lugar sa figure. Ang mga core ay hindi ganap na ginagamit: halos 2/3 lamang ng apat na thread na ito.

Ang isa pang solusyon dito ay ang paggamit lamang Interlocked.CompareExchange na may parehong aktibong paghihintay tulad ng ipinapakita sa code sa itaas (sa mga nagugutom na pilosopo), ngunit ito, gaya ng nasabi na, ay maaaring humantong sa pagharang.

Tungkol sa Interlocked ito ay nagkakahalaga ng sabihin na mayroong hindi lamang CompareExchange, ngunit pati na rin ang iba pang mga pamamaraan para sa atomic na pagbasa AT pagsulat. At sa pamamagitan ng pag-uulit ng pagbabago, kung ang isa pang thread ay namamahala na gumawa ng mga pagbabago nito (basahin ang 1, basahin ang 2, isulat ang 2, isulat ang 1 ay masama), maaari itong magamit para sa mga kumplikadong pagbabago sa isang halaga (Interlocked Anything pattern).

Mga solusyon sa kernel mode

Upang maiwasan ang pag-aaksaya ng mga mapagkukunan sa isang loop, tingnan natin kung paano i-block ang isang thread. Sa madaling salita, sa pagpapatuloy ng ating halimbawa, tingnan natin kung paano pinatulog ng waiter ang pilosopo at ginigising lamang kung kinakailangan. Una, tingnan natin kung paano ito gawin sa pamamagitan ng kernel mode ng operating system. Ang lahat ng istruktura doon ay kadalasang nagiging mas mabagal kaysa sa mga nasa espasyo ng gumagamit. Mabagal ng ilang beses, halimbawa AutoResetEvent marahil 53 beses na mas mabagal SpinLock [Mayaman]. Ngunit sa kanilang tulong, maaari mong i-synchronize ang mga proseso sa buong system, pinamamahalaan man o hindi.

Ang pangunahing disenyo dito ay isang semaphore, na iminungkahi ni Dijkstra mahigit kalahating siglo na ang nakalipas. Ang isang semaphore ay, sa madaling salita, isang positibong integer na kinokontrol ng system, at dalawang operasyon dito - pagtaas at pagbaba. Kung hindi posible na bawasan ang zero, kung gayon ang thread ng pagtawag ay naharang. Kapag ang numero ay nadagdagan ng ilang iba pang aktibong thread/proseso, ang mga thread ay naipasa at ang semaphore ay muling nababawasan ng bilang na naipasa. Maaari mong isipin ang mga tren sa isang bottleneck na may isang semaphore. Nag-aalok ang .NET ng ilang mga konstruksyon na may katulad na pag-andar: AutoResetEvent, ManualResetEvent, Mutex at ang aking sarili Semaphore. Gagamitin natin AutoResetEvent, ito ang pinakasimple sa mga construct na ito: dalawang value lang 0 at 1 (false, true). Pamamaraan niya WaitOne() hinaharangan ang thread sa pagtawag kung 0 ang value, at kung 1, ibinababa ito sa 0 at nilalaktawan ito. Isang paraan Set() tataas sa 1 at hinahayaan ang isang tao na makalusot, na muling bumaba sa 0. Nagsisilbing parang turnstile sa subway.

Gawin nating kumplikado ang solusyon at gumamit ng pagharang para sa bawat pilosopo, at hindi para sa lahat nang sabay-sabay. Yung. Ngayon ang ilang mga pilosopo ay maaaring kumain ng sabay-sabay, at hindi lamang isa. Ngunit muli naming hinarangan ang pag-access sa talahanayan upang tama ang pagkuha ng mga tinidor, pag-iwas sa mga kondisyon ng lahi.

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

Upang maunawaan kung ano ang nangyayari dito, isaalang-alang ang kaso kapag ang pilosopo ay nabigo na kunin ang mga tinidor, kung gayon ang kanyang mga aksyon ay ang mga sumusunod. Naghihintay siya ng access sa mesa. Nang matanggap ito, sinubukan niyang kunin ang mga tinidor. Hindi nag work out. Nagbibigay ito ng access sa talahanayan (mutual exclusion). At dinaanan niya ang kanyang “turnstile” (AutoResetEvent) (sa una ay bukas sila). Nahuhulog na naman sa cycle, kasi wala siyang tinidor. Sinusubukan niyang kunin ang mga ito at huminto sa kanyang "turnstile". Ang ilang mas masuwerteng kapitbahay sa kanan o kaliwa, pagkatapos kumain, ay i-unblock ang ating pilosopo sa pamamagitan ng "pagbubukas ng kanyang turnstile." Ang aming pilosopo ay dumaan dito (at ito ay nagsara sa likod niya) sa pangalawang pagkakataon. Sinusubukan sa ikatlong pagkakataon na kunin ang mga tinidor. Matagumpay. At dumaan siya sa kanyang turnstile para kumain ng tanghalian.

Kapag may mga random na error sa naturang code (palagi silang umiiral), halimbawa, ang isang kapitbahay ay matukoy nang hindi tama o ang parehong bagay ay malilikha AutoResetEvent para sa lahat (Enumerable.Repeat), pagkatapos ay maghihintay ang mga pilosopo sa mga nag-develop, dahil Ang paghahanap ng mga error sa naturang code ay medyo mahirap na gawain. Ang isa pang problema sa solusyon na ito ay hindi nito ginagarantiyahan na ang ilang pilosopo ay hindi magugutom.

Mga solusyon sa hybrid

Tumingin kami sa dalawang diskarte sa pag-synchronize, kapag nananatili kami sa mode ng gumagamit at umiikot sa isang loop at kapag hinarangan namin ang thread sa pamamagitan ng kernel. Ang unang paraan ay mabuti para sa maikling mga bloke, ang pangalawa para sa mahaba. Kadalasan kailangan mo munang maghintay nang panandalian para sa isang variable na magbago sa isang loop, at pagkatapos ay i-block ang thread kapag ang paghihintay ay mahaba. Ang pamamaraang ito ay ipinatupad sa tinatawag na. hybrid na disenyo. Ito ay may parehong mga konstruksyon tulad ng para sa kernel mode, ngunit ngayon ay may isang user-mode loop: SemaphorSlim, ManualResetEventSlim atbp. Ang pinakasikat na disenyo dito ay Monitor, dahil sa C# may kilala lock syntax. Monitor ito ay ang parehong semaphore na may pinakamataas na halaga ng 1 (mutex), ngunit may suporta para sa paghihintay sa isang loop, recursion, Condition Variable pattern (higit pa sa ibaba), atbp. Tingnan natin ang isang solusyon dito.

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

Dito ay muli naming hinarangan ang buong mesa mula sa pag-access sa mga tinidor, ngunit ngayon ay na-unblock namin ang lahat ng mga thread nang sabay-sabay, sa halip na mga kapitbahay kapag may natapos na kumain. Yung. una, may kumakain at humaharang sa mga kapitbahay, at kapag ito ay may natapos, ngunit nais na kumain muli kaagad, pumasok siya sa bloke at ginising ang kanyang mga kapitbahay, dahil ang oras ng paghihintay nito ay mas kaunti.

Sa ganitong paraan maiiwasan natin ang mga deadlock at gutom ng ilang pilosopo. Gumagamit kami ng isang loop upang maghintay ng maikling panahon at harangan ang thread sa loob ng mahabang panahon. Ang pag-unblock sa lahat nang sabay-sabay ay mas mabagal kaysa kung ang kapitbahay lang ang na-unblock, tulad ng sa solusyon sa AutoResetEvent, ngunit ang pagkakaiba ay hindi dapat malaki, dahil dapat manatili muna ang mga thread sa user mode.

У lock Ang syntax ay may ilang hindi kasiya-siyang sorpresa. Inirerekomenda na gamitin Monitor direkta [Richter] [Eric Lippert]. Isa sa kanila ay iyon lock laging lumalabas Monitor, kahit na mayroong isang pagbubukod, at pagkatapos ay maaaring baguhin ng isa pang thread ang estado ng nakabahaging memorya. Sa ganitong mga kaso, madalas na mas mahusay na pumunta sa isang deadlock o kahit papaano ay ligtas na wakasan ang programa. Ang isa pang sorpresa ay ang Monitor ay gumagamit ng mga bloke ng orasan (SyncBlock), na naroroon sa lahat ng mga bagay. Samakatuwid, kung pipiliin ang isang hindi naaangkop na bagay, madali kang makakuha ng deadlock (halimbawa, kung magla-lock ka sa isang interned string). Palagi kaming gumagamit ng nakatagong bagay para dito.

Ang pattern ng Condition Variable ay nagbibigay-daan sa iyo na mas maigsi na ipatupad ang inaasahan ng ilang kumplikadong kundisyon. Sa .NET ito ay hindi kumpleto, sa aking palagay, dahil... Sa teorya, dapat mayroong ilang mga pila sa ilang mga variable (tulad ng sa Posix Threads), at hindi sa isang lock. Pagkatapos ay posible na gawin ang mga ito para sa lahat ng mga pilosopo. Ngunit kahit na sa form na ito pinapayagan ka nitong paikliin ang code.

Maraming pilosopo o async / await

Okay, ngayon ay epektibo na nating mai-block ang mga thread. Ngunit paano kung marami tayong pilosopo? 100? 10000? Halimbawa, nakatanggap kami ng 100000 kahilingan sa web server. Ang paglikha ng isang thread para sa bawat kahilingan ay magiging mahal, dahil napakaraming mga thread ang hindi maipapatupad nang magkatulad. Kung gaano karaming mga lohikal na core ang isasagawa (mayroon akong 4). At ang iba ay kukuha lamang ng mga mapagkukunan. Ang isang solusyon sa problemang ito ay ang pattern ng async / await. Ang ideya nito ay ang isang function ay hindi nagtataglay ng isang thread kung kailangan nitong maghintay para sa isang bagay na magpatuloy. At kapag may nangyari, ipinagpatuloy nito ang pagpapatupad nito (ngunit hindi kinakailangan sa parehong thread!). Sa aming kaso, maghihintay kami ng isang tinidor.

SemaphoreSlim mayroon para dito WaitAsync() paraan. Narito ang isang pagpapatupad gamit ang pattern na ito.

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

Pamamaraan na may async / await ay isinalin sa isang tusong may hangganan na makina ng estado, na agad na nagbabalik ng panloob nito Task. Sa pamamagitan nito, maaari mong hintayin na makumpleto ang pamamaraan, kanselahin ito, at lahat ng iba pang magagawa mo sa Task. Sa loob ng pamamaraan, isang makina ng estado ang kumokontrol sa pagpapatupad. Ang ilalim na linya ay na kung walang pagkaantala, pagkatapos ay ang pagpapatupad ay kasabay, at kung mayroon, pagkatapos ay ang thread ay inilabas. Para sa isang mas mahusay na pag-unawa sa mga ito, ito ay mas mahusay na tingnan ang makina ng estado na ito. Maaari kang lumikha ng mga chain mula sa mga ito async / await paraan.

Subukan natin ito. Trabaho ng 100 pilosopo sa isang makina na may 4 na lohikal na core, 8 segundo. Ang nakaraang solusyon na may Monitor ay nagsagawa lamang ng unang 4 na mga thread at hindi naisagawa ang natitira sa lahat. Ang bawat isa sa 4 na thread na ito ay idle nang humigit-kumulang 2ms. At ginawa ng async / await na solusyon ang lahat ng 100, na may average na 6.8 segundo bawat paghihintay. Siyempre, sa mga totoong system, ang pagiging idle sa loob ng 6 na segundo ay hindi katanggap-tanggap at mas mainam na huwag iproseso ang napakaraming kahilingan sa ganitong paraan. Ang solusyon sa Monitor ay naging hindi nasusukat.

Konklusyon

Tulad ng nakikita mo mula sa maliliit na halimbawang ito, sinusuportahan ng .NET ang maraming mga konstruksyon ng pag-synchronize. Gayunpaman, hindi palaging halata kung paano gamitin ang mga ito. Sana ay nakatulong ang artikulong ito. Tinatapos namin ito sa ngayon, ngunit marami pa ring kawili-wiling bagay ang natitira, halimbawa, mga koleksyon na ligtas sa thread, TPL Dataflow, Reactive programming, modelo ng Software Transaction, atbp.

pinagmumulan

• Visualization ng daloy: Concurrency Visualizer
• MSDN: threading, Asynchronous na mga pattern ng programming at marami pang iba iba pa
• [Richter] — CLR sa pamamagitan ng C#, Jeffrey Richter
• [Eric Lippert] - Tungkol sa lock
• Source code
• Larawan - "Sumayaw sa gitna ng mga espada", G. Semiradsky

Pinagmulan: www.habr.com