Athronwyr wedi'u bwydo'n dda neu Raglennu NET Cystadleuol

Gadewch i ni edrych ar sut mae rhaglennu cydamserol a chyfochrog yn gweithio yn .Net, gan ddefnyddio'r enghraifft o broblem athronwyr cinio. Mae'r cynllun fel a ganlyn, o gydamseru edafedd/proses i fodel yr actor (yn y rhannau canlynol). Efallai y bydd yr erthygl yn ddefnyddiol i rywun sy'n gyfarwydd â chi neu i adnewyddu'ch gwybodaeth.

Pam hyd yn oed gwybod sut i wneud hyn? Mae transistorau yn cyrraedd eu maint lleiaf, mae cyfraith Moore yn taro terfyn cyflymder golau, ac felly gwelir twf mewn niferoedd; gellir gwneud mwy o transistorau. Ar yr un pryd, mae swm y data yn tyfu, ac mae defnyddwyr yn disgwyl ymateb ar unwaith gan systemau. Mewn sefyllfa o'r fath, nid yw rhaglennu “normal”, pan fydd gennym un edefyn gweithredu, yn effeithiol mwyach. Mae angen i ni rywsut ddatrys y broblem o weithredu ar yr un pryd neu ar yr un pryd. Ar ben hynny, mae'r broblem hon yn bodoli ar wahanol lefelau: ar lefel yr edau, ar lefel y broses, ar lefel y peiriannau ar y rhwydwaith (systemau dosbarthedig). Mae gan NET dechnolegau o ansawdd uchel sydd wedi'u profi gan amser ar gyfer datrys problemau o'r fath yn gyflym ac yn effeithlon.

Gorchwyl

Gofynnodd Edsger Dijkstra y broblem hon i'w fyfyrwyr yn ôl yn 1965. Mae'r fformiwleiddiad sefydledig fel a ganlyn. Mae yna nifer penodol (fel arfer pump) o athronwyr a'r un nifer o ffyrc. Maent yn eistedd wrth fwrdd crwn, ffyrch rhyngddynt. Gall athronwyr fwyta o'u platiau o fwyd diddiwedd, meddwl neu aros. I fwyta, mae angen i athronydd gymryd dwy fforc (mae'r olaf yn rhannu fforc gyda'r cyntaf). Mae codi a gosod fforc yn ddau gam gweithredu ar wahân. Mae pob athronydd yn dawel. Y dasg yw dod o hyd i algorithm o'r fath fel eu bod i gyd yn meddwl ac yn cael eu bwydo'n dda hyd yn oed ar ôl 54 mlynedd.

Yn gyntaf, gadewch i ni geisio datrys y broblem hon trwy ddefnyddio gofod a rennir. Mae'r ffyrc yn gorwedd ar y bwrdd cyffredin ac mae'r athronwyr yn syml yn eu cymryd pan fyddant yno ac yn eu rhoi yn ôl. Dyma lle mae problemau cydamseru yn codi, pryd yn union i gymryd ffyrc? beth i'w wneud os nad oes plwg? ac ati Ond yn gyntaf, gadewch i ni ddechrau gyda'r athronwyr.

I ddechrau edafedd rydym yn defnyddio pwll edau drwy Task.Run dull:

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

Mae'r pwll edau wedi'i gynllunio i wneud y gorau o greu a thynnu edafedd. Mae gan y gronfa hon giw o dasgau ac mae'r CLR yn creu neu'n dileu edafedd yn dibynnu ar nifer y tasgau hyn. Un pwll ar gyfer pob AppDomains. Dylid defnyddio'r pwll hwn bron bob amser, oherwydd ... nid oes angen trafferthu creu a dileu edafedd, eu ciwiau, ac ati. Gallwch chi ei wneud heb bwll, ond yna bydd yn rhaid i chi ei ddefnyddio'n uniongyrchol Thread, mae hyn yn ddefnyddiol ar gyfer achosion pan fydd angen i ni newid blaenoriaeth edau, pan fydd gennym weithrediad hir, ar gyfer edau Blaendir, ac ati.

Mewn geiriau eraill, System.Threading.Tasks.Task dosbarth yr un peth Thread, ond gyda phob math o gyfleusterau: y gallu i lansio tasg ar ôl bloc o dasgau eraill, eu dychwelyd o swyddogaethau, torri ar draws yn gyfleus, a llawer mwy. ac ati Mae eu hangen i gefnogi asyncronig / cystrawennau aros (Patrwm Asynchronous Seiliedig ar Dasg, siwgr cystrawen ar gyfer aros am lawdriniaethau IO). Byddwn yn siarad am hyn yn nes ymlaen.

CancelationTokenSource yma mae'n angenrheidiol y gall yr edefyn derfynu ei hun ar signal o'r edefyn galw.

Materion Cysoni

Athronwyr wedi'u rhwystro

Iawn, rydyn ni'n gwybod sut i greu edafedd, gadewch i ni roi cynnig ar ginio:

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

Yma rydyn ni'n ceisio cymryd y chwith yn gyntaf ac yna'r fforch dde, ac os yw'n gweithio, rydyn ni'n eu bwyta a'u rhoi yn ôl. Mae cymryd un fforc yn atomig, h.y. ni all dwy edefyn gymryd un ar yr un pryd (anghywir: mae'r cyntaf yn darllen bod y fforc yn rhydd, mae'r ail yn gwneud yr un peth, mae'r cyntaf yn cymryd, mae'r ail yn cymryd). Am hyn Interlocked.CompareExchange, y mae'n rhaid ei weithredu gan ddefnyddio cyfarwyddyd prosesydd (TSL, XCHG), sy'n cloi darn o gof ar gyfer darllen ac ysgrifennu dilyniannol atomig. Ac mae SpinWait yn cyfateb i'r gwaith adeiladu while(true) dim ond gydag ychydig o “hud” - mae'r edefyn yn cymryd y prosesydd (Thread.SpinWait), ond weithiau mae'n trosglwyddo rheolaeth i edefyn arall (Thread.Yeild) neu'n cwympo i gysgu (Thread.Sleep).

Ond nid yw'r ateb hwn yn gweithio, oherwydd ... yr edafedd yn fuan (o fewn eiliad i mi) a rwystrir: yr holl athronwyr a gymerant eu fforch chwith, ond nid oes un iawn. Yna mae gan yr arae ffyrch y gwerthoedd: 1 2 3 4 5.

Yn y llun, blocio edafedd (deadlock). Mae gwyrdd yn dynodi dienyddiad, mae coch yn dynodi cydamseriad, ac mae llwyd yn dynodi bod yr edau yn cysgu. Mae diemwntau yn nodi amser lansio Tasks.

Newyn yr Athronwyr

Er nad oes angen llawer o fwyd arnoch i feddwl, gall newyn orfodi unrhyw un i roi'r gorau i athroniaeth. Gadewch i ni geisio efelychu sefyllfa newyn edau yn ein problem. Newyn yw pan fydd edau'n gweithio, ond heb waith sylweddol, mewn geiriau eraill, yr un sefyllfa yw hi, dim ond nawr nad yw'r edau'n cysgu, ond mae wrthi'n chwilio am rywbeth i'w fwyta, ond nid oes unrhyw fwyd. Er mwyn osgoi blocio aml, byddwn yn rhoi'r fforc yn ôl os na allem gymryd un arall.

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

Yr hyn sy'n bwysig am y cod hwn yw bod dau o bob pedwar athronydd yn anghofio rhoi eu fforch chwith i lawr. Ac mae'n ymddangos eu bod yn bwyta mwy o fwyd, ac mae eraill yn dechrau llwgu, er bod gan yr edafedd yr un flaenoriaeth. Yma nid ydynt yn newynu'n llwyr, oherwydd ... mae athronwyr drwg weithiau yn rhoi eu ffyrch yn ol. Mae'n ymddangos bod y rhai da yn bwyta tua 5 gwaith yn llai na'r rhai drwg. Felly mae gwall bach yn y cod yn arwain at ostyngiad mewn perfformiad. Yma, mae'n werth nodi hefyd bod sefyllfa brin yn bosibl pan fydd pob athronydd yn cymryd y fforch chwith, nid oes un iawn, maen nhw'n rhoi'r un chwith i lawr, yn aros, yn cymryd yr un chwith eto, ac ati. Mae'r sefyllfa hon hefyd yn newyn, yn debycach i rwystr ar y cyd. Ni allwn ei ailadrodd. Isod mae llun ar gyfer sefyllfa lle mae dau athronydd drwg wedi cymryd y ddwy fforch, a dau o rai da yn newynu.

Yma gallwch weld bod edafedd weithiau'n deffro ac yn ceisio cael adnodd. Nid yw dau o bob pedwar craidd yn gwneud dim (graff gwyrdd uchod).

Marwolaeth Athronydd

Wel, un broblem arall a allai dorri ar draws cinio gogoneddus athronwyr yw os bydd un ohonyn nhw'n marw'n sydyn gyda ffyrc yn ei ddwylo (a bydd yn cael ei gladdu felly). Yna bydd y cymdogion yn cael eu gadael heb ginio. Gallwch chi lunio cod enghreifftiol ar gyfer yr achos hwn eich hun, er enghraifft mae'n cael ei daflu NullReferenceException wedi i'r athronydd gymeryd y ffyrch. A, gyda llaw, ni fydd yr eithriad yn cael ei drin ac ni fydd y cod galw yn ei ddal yn unig (ar gyfer hyn AppDomain.CurrentDomain.UnhandledException ac ati). Felly, mae angen trinwyr gwallau yn yr edafedd eu hunain a chyda therfyniad gosgeiddig.

Y gweinydd

Iawn, sut ydyn ni'n datrys y broblem hon o ddiswyddo, newyn a marwolaethau? Ni a adawn ond un athronydd i'r ffyrch, a chwanegwn gyd-ddieithriad o edafedd i'r lle hwn. Sut i'w wneud? Tybiwch, wrth ymyl yr athronwyr, fod gweinydd yn rhoddi caniatad i un athronydd gymeryd y ffyrch. Mae sut y dylem wneud y gweinydd hwn a sut y bydd athronwyr yn gofyn iddo yn gwestiynau diddorol.

Y ffordd symlaf yw i athronwyr ofyn yn gyson i'r gweinydd am fynediad i'r ffyrc. Y rhai. Yn awr ni bydd athronwyr yn aros am fforch gerllaw, ond yn aros neu yn gofyn i'r gweinydd. Ar y dechrau rydym yn defnyddio Gofod Defnyddiwr yn unig ar gyfer hyn; ynddo nid ydym yn defnyddio ymyriadau i alw unrhyw weithdrefnau o'r cnewyllyn (mwy arnynt isod).

Atebion gofod defnyddiwr

Yma byddwn yn gwneud yr un peth ag a wnaethom o'r blaen gydag un fforch a dau athronydd, byddwn yn troelli mewn dolen ac yn aros. Ond nawr bydd yn athronwyr i gyd ac, fel petai, dim ond un fforch, h.y. gallwn ddweud mai dim ond yr athronydd a gymerodd y “fforch aur” hon oddi ar y gweinydd a fydd yn bwyta. I wneud hyn rydym yn defnyddio 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 ataliwr yw hwn, gyda, yn fras, yr un peth while(true) { if (!lock) break; }, ond gyda hyd yn oed mwy o “hud” nag yn SpinWait (a ddefnyddir yno). Nawr mae'n gwybod sut i gyfrif y rhai sy'n aros, eu rhoi i gysgu ychydig, a llawer mwy. ac ati Yn gyffredinol, mae'n gwneud popeth posibl i wneud y gorau. Ond rhaid inni gofio mai dyma'r un ddolen weithredol o hyd sy'n bwyta adnoddau prosesydd ac yn dal edefyn, a all arwain at newyn os daw un o'r athronwyr yn fwy o flaenoriaeth na'r lleill, ond nad oes ganddo fforc euraidd (problem Gwrthdroad Blaenoriaeth ). Felly, dim ond ar gyfer newidiadau byr iawn mewn cof a rennir y byddwn yn ei ddefnyddio, heb unrhyw alwadau trydydd parti, cloeon nythu, neu bethau annisgwyl eraill.

Arlunio ar gyfer SpinLock. Mae nentydd yn “ymladd” yn gyson am y fforc aur. Methiannau yn digwydd - yr ardal a amlygwyd yn y ffigur. Nid yw'r creiddiau'n cael eu defnyddio'n llawn: dim ond tua 2/3 gan y pedair edefyn hyn.

Ateb arall yma fyddai ei ddefnyddio yn unig Interlocked.CompareExchange gyda'r un arosiad gweithredol ag a ddangosir yn y cod uchod (mewn athronwyr newynog), ond gallai hyn, fel y dywedwyd eisoes, arwain yn ddamcaniaethol at rwystro.

Про Interlocked mae'n werth dweud nad oes yn unig CompareExchange, ond hefyd dulliau eraill ar gyfer darllen atomig AC ysgrifennu. A thrwy ailadrodd y newid, os bydd edefyn arall yn llwyddo i wneud ei newidiadau (darllenwch 1, darllenwch 2, ysgrifennwch 2, ysgrifennwch 1 yn ddrwg), gellir ei ddefnyddio ar gyfer newidiadau cymhleth i un gwerth (patrwm Cyd-gloi Unrhyw beth).

Atebion modd cnewyllyn

Er mwyn osgoi gwastraffu adnoddau mewn dolen, gadewch i ni edrych ar sut i rwystro edau. Mewn geiriau eraill, gan barhau â'n hesiampl, gadewch i ni weld sut mae'r gweinydd yn rhoi'r athronydd i gysgu ac yn ei ddeffro dim ond pan fo angen. Yn gyntaf, gadewch i ni edrych ar sut i wneud hyn trwy ddull cnewyllyn y system weithredu. Mae'r holl strwythurau yno yn aml yn arafach na'r rhai yn y gofod defnyddwyr. Arafach sawl gwaith, er enghraifft AutoResetEvent efallai 53 gwaith yn arafach SpinLock [Richter]. Ond gyda'u help nhw, gallwch chi gydamseru prosesau ar draws y system gyfan, wedi'u rheoli neu beidio.

Mae'r dyluniad sylfaenol yma yn semaffor, a gynigiwyd gan Dijkstra fwy na hanner canrif yn ôl. Mae semaffor, yn syml, yn gyfanrif positif a reolir gan y system, a dau weithrediad arno - cynnydd a gostyngiad. Os nad yw'n bosibl lleihau sero, yna caiff yr edefyn galw ei rwystro. Pan fydd y nifer yn cael ei gynyddu gan ryw edau / proses weithredol arall, yna mae'r edafedd yn cael eu pasio ac mae'r semaffor yn cael ei leihau eto gan y nifer a basiwyd. Gallwch ddychmygu trenau mewn tagfa gyda semaffor. Mae .NET yn cynnig sawl llun gyda nodweddion tebyg: AutoResetEvent, ManualResetEvent, Mutex a minnau Semaphore. Byddwn yn defnyddio AutoResetEvent, dyma'r lluniadau symlaf hyn: dim ond dau werth 0 ac 1 (ffug, gwir). Ei dull WaitOne() blocio'r edefyn galw os oedd y gwerth yn 0, ac os yw 1, yna'n ei israddio i 0 a'i hepgor. Mae dull Set() yn cynyddu i 1 ac yn gadael i un person drwodd, sydd eto'n gostwng i 0. Yn gweithredu fel gatiau tro yn yr isffordd.

Gadewch i ni gymhlethu'r ateb a defnyddio blocio ar gyfer pob athronydd, ac nid i bawb ar unwaith. Y rhai. Nawr gall sawl athronydd fwyta ar unwaith, ac nid un yn unig. Ond rydyn ni eto'n rhwystro mynediad i'r bwrdd er mwyn cymryd ffyrc yn gywir, gan osgoi amodau rasio.

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

I ddeall beth sy'n digwydd yma, ystyriwch yr achos pan fethodd yr athronydd â chymryd y ffyrch, yna bydd ei weithredoedd fel a ganlyn. Mae'n aros am fynediad at y bwrdd. Wedi ei dderbyn, mae'n ceisio cymryd y ffyrc. Heb weithio allan. Mae'n rhoi mynediad i ffwrdd i'r bwrdd (gwaharddiad ar y cyd). Ac mae'n mynd heibio ei “gam dro” (AutoResetEvent) (ar y dechrau maent yn agored). Mae'n disgyn i'r cylch eto, oherwydd nid oes ganddo ffyrc. Mae'n ceisio eu cymryd ac yn stopio wrth ei “gam dro”. Bydd rhyw gymydog mwy ffodus i’r dde neu’r chwith, ar ôl gorffen bwyta, yn dadflocio ein hathronydd trwy “agor ei gamfa.” Y mae ein hathronydd yn myned trwyddo (ac yn cau ar ei ol) eilwaith. Yn ceisio cymryd y ffyrc am y trydydd tro. Llwyddiannus. Ac mae'n mynd trwy ei gatiau tro i gael cinio.

Pan fo gwallau ar hap mewn cod o'r fath (maent bob amser yn bodoli), er enghraifft, bydd cymydog yn cael ei nodi'n anghywir neu bydd yr un gwrthrych yn cael ei greu AutoResetEvent i bawb (Enumerable.Repeat), yna bydd yr athronwyr yn aros am y datblygwyr, oherwydd Mae dod o hyd i wallau mewn cod o'r fath yn dasg eithaf anodd. Problem arall gyda'r ateb hwn yw nad yw'n gwarantu na fydd rhai athronydd yn llwgu.

Datrysiadau hybrid

Fe wnaethom edrych ar ddau ddull cydamseru, pan fyddwn yn aros yn y modd defnyddiwr ac yn troelli mewn dolen a phan fyddwn yn rhwystro'r edau trwy'r cnewyllyn. Mae'r dull cyntaf yn dda ar gyfer blociau byr, yr ail ar gyfer rhai hir. Yn aml mae angen i chi aros yn fyr yn gyntaf i newidyn newid mewn dolen, ac yna blocio'r edau pan fydd yr aros yn hir. Mae'r dull hwn yn cael ei weithredu yn yr hyn a elwir. dyluniadau hybrid. Mae ganddo'r un lluniadau ag ar gyfer modd cnewyllyn, ond nawr gyda dolen modd defnyddiwr: SemaphorSlim, ManualResetEventSlim ac ati Y dyluniad mwyaf poblogaidd yma Monitor, achos yn C# mae adnabyddus lock cystrawen. Monitor dyma'r un semaffor gyda gwerth mwyaf o 1 (mutex), ond gyda chefnogaeth ar gyfer aros mewn dolen, recursion, Cyflwr Patrwm Newidyn (mwy ar hynny isod), ac ati Gadewch i ni edrych ar ateb ag ef.

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

Yma eto rydyn ni'n rhwystro'r bwrdd cyfan rhag cyrchu'r ffyrc, ond nawr rydyn ni'n dadflocio'r holl edafedd ar unwaith, yn hytrach na chymdogion pan fydd rhywun yn gorffen bwyta. Y rhai. yn gyntaf, mae rhywun yn bwyta ac yn blocio'r cymdogion, a phan fydd hyn yn rhywun yn gorffen, ond eisiau bwyta eto ar unwaith, mae'n mynd i mewn i'r bloc ac yn deffro ei gymdogion, oherwydd mae ei amser aros yn llai.

Fel hyn rydym yn osgoi deadlocks a newyn rhai athronydd. Rydyn ni'n defnyddio dolen i aros am gyfnod byr ac yn rhwystro'r edau am amser hir. Mae dadflocio pawb ar unwaith yn arafach na phe bai'r cymydog yn unig yn cael ei ddadflocio, fel yn yr ateb AutoResetEvent, ond ni ddylai'r gwahaniaeth fod yn fawr, oherwydd rhaid i edafedd aros yn y modd defnyddiwr yn gyntaf.

У lock mae gan gystrawen rai syrpreisys annymunol. Argymhellir ei ddefnyddio Monitor yn uniongyrchol [Richter] [Eric Lippert]. Un ohonyn nhw yw hynny lock bob amser yn dod allan Monitor, hyd yn oed os oedd eithriad, ac yna gall edefyn arall newid cyflwr y cof a rennir. Mewn achosion o'r fath, yn aml mae'n well mynd i sefyllfa ddiddatrys neu derfynu'r rhaglen yn ddiogel rywsut. Syndod arall yw bod Monitor yn defnyddio blociau cloc (SyncBlock), y rhai sydd yn bresennol yn mhob gwrthddrychau. Felly, os dewisir gwrthrych amhriodol, gallwch chi gael clo yn hawdd (er enghraifft, os ydych chi'n cloi ar linyn mewnol). Rydym bob amser yn defnyddio gwrthrych cudd ar gyfer hyn.

Mae'r patrwm Newid Cyflwr yn eich galluogi i weithredu'r disgwyliad o gyflwr cymhleth yn fwy cryno. Yn .NET mae'n anghyflawn, yn fy marn i, oherwydd... Mewn egwyddor, dylai fod sawl ciw ar sawl newidyn (fel yn Posix Threads), ac nid ar un clo. Yna byddai yn bosibl eu gwneud i bob athronydd. Ond hyd yn oed yn y ffurflen hon mae'n caniatáu ichi fyrhau'r cod.

Mae llawer o athronwyr neu async / await

Iawn, nawr gallwn rwystro edafedd i bob pwrpas. Ond beth os oes gennym ni lawer o athronwyr? 100? 10000? Er enghraifft, cawsom 100000 o geisiadau i'r gweinydd gwe. Bydd creu edefyn ar gyfer pob cais yn ddrud, oherwydd ni fydd cymaint o edafedd yn cael eu gweithredu ochr yn ochr. Dim ond cymaint o greiddiau rhesymegol fydd yn cael eu gweithredu (mae gen i 4). A bydd pawb arall yn cymryd adnoddau i ffwrdd. Un ateb i'r broblem hon yw'r patrwm async / aros. Ei syniad yw nad yw swyddogaeth yn dal edefyn os oes angen iddi aros i rywbeth barhau. A phan fydd rhywbeth yn digwydd, mae'n ailddechrau ei weithredu (ond nid o reidrwydd yn yr un edefyn!). Yn ein hachos ni, byddwn yn aros am fforc.

SemaphoreSlim wedi ar gyfer hyn WaitAsync() dull. Dyma weithrediad gan ddefnyddio'r patrwm hwn.

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

Dull gyda async / await yn cael ei chyfieithu yn beiriant cyfrwys cyfrwys meidrol, yr hwn sydd ar unwaith yn dychwelyd ei fewnol Task. Trwyddo, gallwch chi aros i'r dull ei gwblhau, ei ganslo, a phopeth arall y gallwch chi ei wneud gyda Tasg. Y tu mewn i'r dull, mae peiriant cyflwr yn rheoli gweithredu. Y gwir amdani yw, os nad oes oedi, yna mae'r gweithrediad yn gydamserol, ac os oes, yna caiff yr edau ei ryddhau. I gael gwell dealltwriaeth o hyn, mae'n well edrych ar y peiriant cyflwr hwn. Gallwch greu cadwyni o'r rhain async / await dulliau.

Gadewch i ni ei brofi. Gwaith 100 o athronwyr ar beiriant gyda 4 craidd rhesymegol, 8 eiliad. Dim ond y 4 edafedd cyntaf a weithredwyd gan yr ateb blaenorol gyda Monitor ac ni weithredodd y gweddill o gwbl. Roedd pob un o'r 4 llinyn hyn yn segur am tua 2ms. A gwnaeth yr ateb async / await bob 100, gyda chyfartaledd o 6.8 eiliad yr un aros. Wrth gwrs, mewn systemau go iawn, mae bod yn segur am 6 eiliad yn annerbyniol ac mae'n well peidio â phrosesu cymaint o geisiadau fel hyn. Nid oedd yr ateb gyda Monitor yn un y gellir ei raddio o gwbl.

Casgliad

Fel y gwelwch o'r enghreifftiau bach hyn, mae .NET yn cefnogi llawer o luniadau cydamseru. Fodd bynnag, nid yw bob amser yn amlwg sut i'w defnyddio. Rwy'n gobeithio bod yr erthygl hon wedi bod yn ddefnyddiol. Rydyn ni'n lapio hyn am y tro, ond mae yna lawer o bethau diddorol ar ôl o hyd, er enghraifft, casgliadau edau-diogel, TPL Dataflow, Rhaglennu Adweithiol, model Trafodion Meddalwedd, ac ati.

Ffynonellau

• Delweddu llif: Concurrency Visualizer
• MSDN: edafu, Patrymau rhaglennu asyncronaidd a llawer mwy etc.
• [Richter] — CLR trwy C#, Jeffrey Richter
• [Eric Lippert] - Ynglŷn â chlo
• Cod ffynhonnell
• Llun – “Dawns ymhlith y cleddyfau”, G. Semiradsky

Ffynhonnell: hab.com