Լավ սնված փիլիսոփաներ կամ մրցակցային .NET ծրագրավորում

Տեսնենք, թե ինչպես է աշխատում զուգահեռ և զուգահեռ ծրագրավորումը .Net-ում՝ որպես օրինակ օգտագործելով Philosophers Dining Problem-ը: Պլանը սա է՝ թելերի/գործընթացների համաժամացումից մինչև դերասանի մոդել (հետևյալ մասերում)։ Հոդվածը կարող է օգտակար լինել առաջին ծանոթության կամ ձեր գիտելիքները թարմացնելու համար։

Ինչու՞ դա անել ընդհանրապես: Տրանզիստորները հասնում են իրենց նվազագույն չափի, Մուրի օրենքը հիմնված է լույսի արագության սահմանափակման վրա և հետևաբար նկատվում է թվի աճ, կարելի է ավելի շատ տրանզիստորներ պատրաստել։ Միևնույն ժամանակ տվյալների քանակն աճում է, և օգտատերերը համակարգերից ակնկալում են անհապաղ արձագանք: Նման իրավիճակում «նորմալ» ծրագրավորումը, երբ մենք ունենք մեկ կատարող թել, այլեւս արդյունավետ չէ։ Դուք պետք է ինչ-որ կերպ լուծեք միաժամանակյա կամ միաժամանակյա կատարման խնդիրը: Ընդ որում, այս խնդիրն առկա է տարբեր մակարդակներում՝ թելերի, պրոցեսների մակարդակում, ցանցի մեքենաների (բաշխված համակարգերի) մակարդակում։ .NET-ն ունի բարձրորակ, ժամանակի փորձարկված տեխնոլոգիաներ՝ նման խնդիրների արագ և արդյունավետ լուծման համար։

Առաջադրանք

Էդսգեր Դեյկստրան այս խնդիրը դրել է իր ուսանողներին դեռևս 1965թ.-ին: Սահմանված ձևակերպումը հետևյալն է. Կա որոշակի (սովորաբար հինգ) թվով փիլիսոփաներ և նույնքան պատառաքաղներ: Նրանք նստում են կլոր սեղանի շուրջ, պատառաքաղներ նրանց միջև: Փիլիսոփաները կարող են ուտել իրենց ափսեներից անվերջ սնունդ, մտածել կամ սպասել: Փիլիսոփային ուտելու համար հարկավոր է վերցնել երկու պատառաքաղ (վերջինը պատառաքաղը կիսում է առաջինի հետ): Պատառաքաղը վերցնելը և ցած դնելը երկու առանձին գործողություններ են: Բոլոր փիլիսոփաները լռում են. Խնդիրն այնպիսի ալգորիթմ գտնելն է, որ բոլորը մտածեն ու կուշտ լինեն նույնիսկ 54 տարի անց։

Նախ, եկեք փորձենք լուծել այս խնդիրը ընդհանուր տարածության օգտագործման միջոցով: Պատառաքաղները պառկած են ընդհանուր սեղանի վրա, և փիլիսոփաները պարզապես վերցնում են դրանք և հետ են դնում: Այստեղ համաժամացման հետ կապված խնդիրներ կան, կոնկրետ ե՞րբ վերցնել surebets: իսկ եթե պատառաքաղ չկա՞ և այլն: Բայց նախ, եկեք սկսենք փիլիսոփաներից:

Թելերը սկսելու համար մենք օգտագործում ենք թելերի լողավազան Task.Run մեթոդ:

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

Թելերի ֆոնդը նախատեսված է թելերի ստեղծումն ու ջնջումը օպտիմալացնելու համար: Այս լողավազանն ունի առաջադրանքների հերթ, և CLR-ն ստեղծում կամ հեռացնում է թելեր՝ կախված այդ առաջադրանքների քանակից: Մեկ լողավազան բոլոր AppDomains-ի համար: Այս լողավազանը պետք է օգտագործել գրեթե միշտ, քանի որ. կարիք չկա անհանգստանալ թելերի ստեղծման, ջնջման, դրանց հերթերի և այլնի հետ: Դա հնարավոր է առանց լողավազանի, բայց հետո դուք պետք է օգտագործեք այն ուղղակիորեն: Thread, սա օգտակար է այն դեպքերի համար, երբ պետք է փոխել թեմայի առաջնահերթությունը, երբ մենք երկար աշխատանք ունենք, առաջնային թեմայի համար և այլն։

Այլ կերպ ասած, System.Threading.Tasks.Task դասը նույնն է Thread, բայց ամենատարբեր հարմարություններով. առաջադրանքը այլ առաջադրանքների բլոկի հետևից հետո գործադրելու, գործառույթներից դրանք վերադարձնելու, դրանք հարմար կերպով ընդհատելու և այլնի հնարավորություն: և այլն: Դրանք անհրաժեշտ են async/wait կոնստրուկցիաներին աջակցելու համար (Առաջադրանքի վրա հիմնված Asynchronous Pattern, շարահյուսական շաքար IO գործողությունների սպասման համար): Այս մասին ավելի ուշ կխոսենք:

CancelationTokenSource այստեղ դա անհրաժեշտ է, որպեսզի շարանը կարողանա ինքն իրեն վերջանալ կանչող շարանի ազդանշանով:

Համաժամացման խնդիրներ

Արգելափակված փիլիսոփաներ

Լավ, մենք գիտենք, թե ինչպես ստեղծել թեմաներ, եկեք փորձենք ճաշել.

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

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

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

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

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

Այստեղ մենք նախ փորձում ենք վերցնել ձախ պատառաքաղը, իսկ հետո՝ աջ պատառաքաղը, և եթե ստացվի, ապա ուտում ենք և հետ ենք դնում։ Մեկ պատառաքաղ վերցնելը ատոմային է, այսինքն. երկու թելերը չեն կարող միաժամանակ մեկը վերցնել (սխալ է. առաջինը կարդում է, որ պատառաքաղն ազատ է, երկրորդը նույնպես, առաջինը վերցնում է, երկրորդը վերցնում է): Սրա համար Interlocked.CompareExchange, որը պետք է իրականացվի պրոցեսորի հրահանգով (TSL, XCHG), որը կողպում է հիշողության մի կտոր ատոմային հաջորդական ընթերցման և գրելու համար: Իսկ SpinWait-ը համարժեք է կոնստրուկտին while(true) միայն մի փոքր «կախարդանքով» - շարանը վերցնում է պրոցեսորը (Thread.SpinWait), բայց երբեմն վերահսկողությունը փոխանցում է մեկ այլ թեմա (Thread.Yeild) կամ քնում է (Thread.Sleep).

Բայց այս լուծումը չի աշխատում, քանի որ հոսքերը շուտով (ինձ համար մեկ վայրկյանում) արգելափակվում են. բոլոր փիլիսոփաները վերցնում են իրենց ձախ պատառաքաղը, բայց ոչ ճիշտը: Պատառաքաղների զանգվածն այնուհետև ունի արժեքներ՝ 1 2 3 4 5:

Նկարում արգելափակող թելերը (փակուղի): Կանաչ - կատարում, կարմիր - համաժամացում, մոխրագույն - շարանը քնած է: Ռոմբուսները ցույց են տալիս առաջադրանքների մեկնարկի ժամանակը:

Փիլիսոփաների սովը

Թեև պետք չէ հատկապես ուտելիք մտածել, բայց քաղցը ստիպում է որևէ մեկին հրաժարվել փիլիսոփայությունից։ Փորձենք մոդելավորել թելերի սովի իրավիճակը մեր խնդրի մեջ։ Սովն այն է, երբ թելը հոսում է, բայց առանց էական աշխատանքի, այսինքն՝ սա նույն փակուղին է, միայն թե հիմա թելը ոչ թե քնում է, այլ ակտիվ ուտելու բան է փնտրում, բայց ուտելիք չկա։ Հաճախակի արգելափակումից խուսափելու համար պատառաքաղը հետ կդնենք, եթե չկարողանանք մյուսը վերցնել։

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

        Think(i);

        if (token.IsCancellationRequested)
            break;
    }
}

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

Այս կոդի հետ կապված կարևորն այն է, որ չորս փիլիսոփաներից երկուսը մոռանում են իրենց ձախ պատառաքաղը վայր դնել: Եվ պարզվում է, որ նրանք ավելի շատ սնունդ են ուտում, իսկ մյուսները սկսում են սովամահ լինել, թեև թելերն ունեն նույն առաջնահերթությունը։ Այստեղ նրանք ամբողջովին սովից չեն մեռնում, քանի որ. վատ փիլիսոփաները երբեմն ետ են դնում իրենց պատառաքաղները: Պարզվում է, որ լավ մարդիկ մոտ 5 անգամ ավելի քիչ են ուտում, քան վատերը։ Այսպիսով, կոդի փոքր սխալը հանգեցնում է կատարողականի անկման: Այստեղ հարկ է նշել նաև, որ հնարավոր է հազվագյուտ իրավիճակ, երբ բոլոր փիլիսոփաները վերցնում են ձախ պատառաքաղը, ճիշտը չկա, ձախը դնում են, սպասում են, նորից ձախը վերցնում և այլն։ Այս իրավիճակը նույնպես սովամահություն է, ավելի շուտ փակուղային իրավիճակի։ Ինձ չհաջողվեց կրկնել: Ստորև ներկայացված է մի իրավիճակ, որտեղ երկու վատ փիլիսոփաներ վերցրել են երկու պատառաքաղը, իսկ երկու լավը սովամահ են լինում:

Այստեղ դուք կարող եք տեսնել, որ թելերը երբեմն արթնանում են և փորձում են ստանալ ռեսուրսը: Չորս միջուկներից երկուսը ոչինչ չեն անում (վերևում կանաչ գրաֆիկ):

Փիլիսոփայի մահը

Դե, ևս մեկ խնդիր, որը կարող է ընդհատել փիլիսոփաների փառահեղ ընթրիքը, եթե նրանցից մեկը հանկարծ մահանա՝ պատառաքաղները ձեռքերին (և նրան այդպես կթաղեն)։ Հետո հարեւանները կմնան առանց ճաշի։ Դուք ինքներդ կարող եք այս դեպքի համար օրինակ կոդ հորինել, օրինակ՝ այն դուրս է նետված NullReferenceException այն բանից հետո, երբ փիլիսոփան վերցնում է պատառաքաղները: Եվ, ի դեպ, բացառությունը չի կարգավորվի, և զանգի կոդը պարզապես չի բռնի այն (դրա համար AppDomain.CurrentDomain.UnhandledException և այլն): Հետևաբար, սխալների մշակիչներ են անհրաժեշտ հենց թելերում և նրբագեղ ավարտով:

Մատուցող

Լավ, ինչպե՞ս լուծենք այս փակուղային, սովի և մահվան խնդիրը: Մենք թույլ կտանք միայն մեկ փիլիսոփայի հասնել պատառաքաղներին, ավելացնել թելերի փոխադարձ բացառում այս վայրի համար: Ինչպե՞ս դա անել: Ենթադրենք, փիլիսոփաների կողքին կանգնած է մատուցող, որը թույլ է տալիս որևէ փիլիսոփայի վերցնել պատառաքաղները։ Ինչպե՞ս ենք այս մատուցողին սարքում, և ինչպես են նրան հարցնելու փիլիսոփաները, հարցերը հետաքրքիր են։

Ամենապարզ ճանապարհն այն է, երբ փիլիսոփաները պարզապես անընդհատ մատուցողից կխնդրեն մուտք գործել պատառաքաղներ: Նրանք. այժմ փիլիսոփաները չեն սպասի մոտակայքում պատառաքաղի, այլ կսպասեն կամ կհարցնեն մատուցողին։ Սկզբում մենք դրա համար օգտագործում ենք միայն Օգտվողի տարածքը, դրանում մենք չենք օգտագործում ընդհատումներ միջուկից որևէ ընթացակարգ կանչելու համար (դրանց մասին ստորև):

Լուծումներ օգտագործողի տարածքում

Այստեղ մենք կանենք նույնը, ինչ անում էինք մեկ պատառաքաղով և երկու փիլիսոփաներով, կպտտվենք ցիկլով և կսպասենք։ Բայց հիմա դա կլինի բոլոր փիլիսոփաները և, ինչպես որ եղավ, միայն մեկ պատառաքաղ, այսինքն. Կարելի է ասել, որ ուտելու է միայն այն փիլիսոփան, ով այս «ոսկե պատառաքաղը» վերցրել է մատուցողից։ Դրա համար մենք օգտագործում ենք SpinLock-ը:

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

        Think(i);

        if (token.IsCancellationRequested)
            break;
    }
}

SpinLock սա արգելափակող է, կոպիտ ասած՝ նույնը while(true) { if (!lock) break; }, բայց նույնիսկ ավելի «կախարդանքով», քան ներսում SpinWait (որն օգտագործվում է այնտեղ): Հիմա նա գիտի սպասողներին հաշվել, մի քիչ քնեցնել, և ավելին։ և այլն։ Ընդհանրապես, անում է հնարավոր ամեն ինչ՝ օպտիմալացնելու համար։ Բայց մենք պետք է հիշենք, որ սա դեռ նույն ակտիվ ցիկլն է, որը խժռում է պրոցեսորային ռեսուրսները և պահպանում հոսքը, ինչը կարող է հանգեցնել սովի, եթե փիլիսոփաներից մեկը դառնա ավելի առաջնահերթ, քան մյուսները, բայց չունենա ոսկե պատառաքաղ (Priority Inversion խնդիր) . Հետևաբար, մենք այն օգտագործում ենք միայն ընդհանուր հիշողության մեջ շատ կարճ փոփոխությունների համար՝ առանց որևէ երրորդ կողմի զանգերի, տեղադրվող կողպեքների և այլ անակնկալների:

Նկարչություն համար SpinLock. Առվակներն անընդհատ «կռվում են» ոսկե պատառաքաղի համար։ Կան ձախողումներ - նկարում, ընտրված տարածքը: Միջուկները ամբողջությամբ չեն օգտագործվում. միայն մոտ 2/3-ը այս չորս թելերով:

Մեկ այլ լուծում այստեղ կլինի միայն օգտագործելը Interlocked.CompareExchange նույն ակտիվ սպասումով, ինչպես ցույց է տրված վերը նշված օրենսգրքում (սոված փիլիսոփաներում), բայց դա, ինչպես արդեն ասվեց, տեսականորեն կարող է հանգեցնել արգելափակման:

Մոտ Interlocked Հարկ է նշել, որ կա ոչ միայն CompareExchange, այլ նաև ատոմային կարդալու և գրելու այլ մեթոդներ: Եվ փոփոխության կրկնության միջոցով, եթե մեկ այլ շարանը ժամանակ ունենա իր փոփոխությունները կատարելու (կարդալ 1, կարդալ 2, գրել 2, գրել 1-ը վատ է), այն կարող է օգտագործվել մեկ արժեքի բարդ փոփոխությունների համար (Interlocked Anything օրինաչափություն) .

Kernel Mode Solutions

Որպեսզի ռեսուրսները մի օղակում վատնվեն, տեսնենք, թե ինչպես կարող ենք արգելափակել շարանը: Այսինքն, շարունակելով մեր օրինակը, տեսնենք, թե ինչպես է մատուցողը քնեցնում փիլիսոփային ու միայն անհրաժեշտության դեպքում արթնացնում։ Նախ, եկեք տեսնենք, թե ինչպես դա անել օպերացիոն համակարգի միջուկի ռեժիմի միջոցով: Այնտեղ բոլոր կառույցները հաճախ ավելի դանդաղ են, քան օգտագործողների տարածքում: Մի քանի անգամ ավելի դանդաղ, օրինակ AutoResetEvent գուցե 53 անգամ ավելի դանդաղ SpinLock [Ռիխտեր]. Բայց նրանց օգնությամբ դուք կարող եք համաժամացնել գործընթացները ողջ համակարգում՝ կառավարվող, թե ոչ:

Հիմնական կառուցվածքն այստեղ ավելի քան կես դար առաջ Դեյկստրայի առաջարկած սեմալտն է: Սեմաֆորը, պարզ ասած, դրական ամբողջ թիվ է, որը կառավարվում է համակարգի կողմից, և դրա վրա երկու գործողություն՝ ավելացում և նվազում: Եթե ​​չհաջողվի նվազեցնել, զրո, ապա զանգող շարանը արգելափակված է: Երբ թիվը ավելանում է ինչ-որ այլ ակտիվ թելով/գործընթացով, ապա թելերը բաց են թողնվում, և սեմալտը կրկին նվազում է անցած թվով: Կարելի է պատկերացնել գնացքները սեմալտով խցանման մեջ: .NET-ն առաջարկում է նմանատիպ ֆունկցիոնալությամբ մի քանի կառուցվածք. AutoResetEvent, ManualResetEvent, Mutex և ես Semaphore. Մենք կօգտագործենք AutoResetEvent, սա այս կոնստրուկցիաներից ամենապարզն է՝ ընդամենը երկու արժեք 0 և 1 (կեղծ, ճիշտ): Նրա մեթոդը WaitOne() արգելափակում է կանչող շարանը, եթե արժեքը եղել է 0, իսկ եթե 1 է, իջեցնում է այն մինչև 0 և բաց է թողնում այն: Մեթոդ Set() բարձրացնում է 1-ը և բաց է թողնում մեկ մատուցողի, ով նորից իջեցնում է 0-ի: Գործում է մետրոյի շրջադարձայինի պես:

Եկեք բարդացնենք լուծումը և օգտագործենք կողպեքը յուրաքանչյուր փիլիսոփայի համար, և ոչ միանգամից: Նրանք. այժմ կարող է լինել միանգամից մի քանի փիլիսոփա, և ոչ թե մեկը: Բայց մենք կրկին արգելափակում ենք մուտքը դեպի աղյուսակ, որպեսզի ճիշտ, խուսափելով մրցավազքներից (մրցավազքի պայմաններից), վերցնենք 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();
}

Հասկանալու համար, թե ինչ է կատարվում այստեղ, հաշվի առեք այն դեպքը, երբ փիլիսոփան չկարողացավ վերցնել պատառաքաղները, ապա նրա գործողությունները կլինեն հետևյալը. Նա սպասում է մուտքի սեղանին: Ստանալով այն՝ նա փորձում է վերցնել պատառաքաղները։ Չստացվեց. Այն հնարավորություն է տալիս մուտք գործել աղյուսակ (փոխադարձ բացառում): Եվ անցնում է իր «պտույտը» (AutoResetEvent) (նրանք սկզբում բաց են): Այն նորից մտնում է ցիկլի մեջ, քանի որ նա պատառաքաղներ չունի: Նա փորձում է վերցնել դրանք ու կանգ է առնում իր «պտույտի» մոտ։ Աջ կամ ձախ կողմում գտնվող մի ավելի բախտավոր հարևան, ուտելն ավարտելուց հետո, բացում է մեր փիլիսոփայի կողպեքը՝ «բացելով իր շրջադարձը»։ Մեր փիլիսոփան երկրորդ անգամ է այն անցնում (և փակվում է դրա հետևում): Նա երրորդ անգամ է փորձում վերցնել պատառաքաղները։ Հաջողություն. Եվ նա անցնում է իր շրջագայությունը ճաշելու համար:

Երբ նման կոդում պատահական սխալներ կան (դրանք միշտ կան), օրինակ, հարեւանը սխալ է նշված կամ ստեղծվում է նույն օբյեկտը. AutoResetEvent բոլորի համար (Enumerable.Repeat), ապա փիլիսոփաները կսպասեն մշակողներին, քանի որ Նման կոդում սխալներ գտնելը բավականին բարդ խնդիր է։ Այս լուծման մյուս խնդիրն այն է, որ այն չի երաշխավորում, որ ինչ-որ փիլիսոփա սոված չի մնա:

Հիբրիդային լուծումներ

Մենք դիտարկել ենք ժամանակի երկու մոտեցում՝ երբ մենք մնում ենք օգտագործողի ռեժիմում և հանգույցում, և երբ արգելափակում ենք շարանը միջուկի միջով: Առաջին մեթոդը լավ է կարճ կողպեքների համար, երկրորդը երկարների համար: Հաճախ անհրաժեշտ է նախ հակիրճ սպասել, որ փոփոխականը փոխվի օղակում, իսկ հետո արգելափակել շարանը, երբ սպասումը երկար է: Այս մոտեցումն իրականացվում է այսպես կոչված. հիբրիդային կառույցներ. Ահա նույն կառուցվածքները, ինչ միջուկի ռեժիմի համար, բայց այժմ օգտագործողի ռեժիմի հանգույցով. SemaphorSlim, ManualResetEventSlim և այլն: Այստեղ ամենահայտնի դիզայնն է Monitor, որովհետեւ C#-ում հայտնի է lock շարահյուսություն. Monitor սա նույն սեմաֆորն է առավելագույն արժեքով 1 (mutex), բայց աջակցում է օղակում սպասելու համար, ռեկուրսիա, Condition Variable օրինաչափություն (այդ մասին ավելին ստորև) և այլն: Եկեք նայենք դրա լուծմանը:

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

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

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

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

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

Այստեղ մենք կրկին արգելափակում ենք ամբողջ սեղանը պատառաքաղներին մուտք գործելու համար, բայց հիմա մենք միանգամից ապաշրջափակում ենք բոլոր թելերը, և ոչ թե հարևաններին, երբ ինչ-որ մեկն ավարտում է ուտելը: Նրանք. նախ՝ ինչ-որ մեկը ուտում և արգելափակում է հարևաններին, և երբ այս մեկը վերջացնում է, բայց ուզում է անմիջապես նորից ուտել, նա մտնում է արգելափակման մեջ և արթնացնում է իր հարևաններին, քանի որ. դրա սպասման ժամանակը քիչ է:

Այսպես մենք խուսափում ենք փակուղուց և ինչ-որ փիլիսոփայի սովից։ Մենք օգտագործում ենք հանգույց կարճ սպասման համար և երկար ժամանակ փակում ենք շարանը: Բոլորին միանգամից ապաշրջափակելը ավելի դանդաղ է, քան եթե միայն հարեւանն ապաարգելափակված լիներ, ինչպես լուծման հետ AutoResetEvent, բայց տարբերությունը չպետք է մեծ լինի, քանի որ թելերը նախ պետք է մնան օգտագործողի ռեժիմում:

У lock շարահյուսությունը տհաճ անակնկալներ ունի. Խորհուրդ է տրվում օգտագործել Monitor ուղղակիորեն [Ռիխտեր] [Էրիկ Լիպերտ]: Դրանցից մեկն այն է lock միշտ դուրս Monitor, նույնիսկ եթե լիներ բացառություն, որի դեպքում մեկ այլ շարանը կարող է փոխել ընդհանուր հիշողության վիճակը։ Նման դեպքերում հաճախ ավելի լավ է գնալ փակուղի կամ ինչ-որ կերպ ապահով կերպով դադարեցնել ծրագիրը: Մեկ այլ անակնկալ այն է, որ Մոնիտորը օգտագործում է համաժամացման բլոկներ (SyncBlock), որոնք առկա են բոլոր օբյեկտներում: Հետևաբար, եթե ընտրված է անհամապատասխան օբյեկտ, դուք հեշտությամբ կարող եք փակուղի ստանալ (օրինակ, եթե կողպեք ներկառուցված տողի վրա): Դրա համար մենք օգտագործում ենք միշտ թաքնված օբյեկտը:

Condition Variable օրինակը թույլ է տալիս ավելի հակիրճ իրականացնել որոշ բարդ պայմանների ակնկալիքը: .NET-ում այն ​​թերի է, իմ կարծիքով, քանի որ տեսականորեն մի քանի փոփոխականների վրա պետք է լինեն մի քանի հերթեր (ինչպես Posix Threads-ում), այլ ոչ թե մեկ lok-ում: Այդ դեպքում կարելի էր դրանք պատրաստել բոլոր փիլիսոփաների համար: Բայց նույնիսկ այս տեսքով այն թույլ է տալիս նվազեցնել կոդը:

շատ փիլիսոփաներ կամ async / await

Լավ, այժմ մենք կարող ենք արդյունավետորեն արգելափակել թեմաները: Բայց ի՞նչ, եթե մենք շատ փիլիսոփաներ ունենանք։ 100? 10000? Օրինակ, մենք ստացել ենք 100000 հարցում վեբ սերվերին: Յուրաքանչյուր խնդրանքի համար թեմա ստեղծելը գերավճար կլինի, քանի որ այնքան շատ թելեր զուգահեռ չեն անցնի: Կաշխատի այնքան, որքան տրամաբանական միջուկներ կան (ես ունեմ 4): Իսկ մնացած բոլորը պարզապես կխլեն ռեսուրսները: Այս խնդրի լուծումներից մեկը async / await օրինակն է: Նրա գաղափարն այն է, որ ֆունկցիան չի պահում շարանը, եթե այն պետք է սպասի ինչ-որ բան շարունակելուն: Եվ երբ այն ինչ-որ բան է անում, այն վերսկսում է իր կատարումը (բայց պարտադիր չէ, որ նույն թելի վրա): Մեր դեպքում մենք կսպասենք պատառաքաղին:

SemaphoreSlim ունի սրա համար WaitAsync() մեթոդ. Ահա այս օրինաչափության օգտագործմամբ իրականացումը:

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

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

        Think(i);

        if (token.IsCancellationRequested) break;
    }
}

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

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

Մեթոդ հետ async / await թարգմանվում է բարդ վիճակի մեքենայի, որն անմիջապես վերադարձնում է իր ներքինը Task. Դրա միջոցով կարող եք սպասել մեթոդի ավարտին, չեղարկել այն և մնացած ամեն ինչ, որ կարող եք անել Task-ի հետ։ Մեթոդի ներսում պետական ​​մեքենան վերահսկում է կատարումը։ Ներքեւի տողն այն է, որ եթե ուշացում չկա, ապա կատարումը համաժամանակյա է, իսկ եթե կա, ապա շարանը բաց է թողնվում։ Սա ավելի լավ հասկանալու համար ավելի լավ է նայել այս պետական ​​մեքենային։ Դրանցից կարող եք շղթաներ ստեղծել async / await մեթոդները։

Եկեք փորձարկենք. 100 փիլիսոփաների աշխատանքը 4 տրամաբանական միջուկով մեքենայի վրա, 8 վայրկյան: Նախորդ լուծումը Monitor-ով աշխատում էր միայն առաջին 4 թելերով, իսկ մնացածն ընդհանրապես չէր աշխատում: Այս 4 թելերից յուրաքանչյուրը անգործության մեջ էր մոտ 2 մս: Եվ async / await լուծումն աշխատեց բոլոր 100-ը, յուրաքանչյուրը միջինը 6.8 վայրկյան սպասելով: Իհարկե, իրական համակարգերում 6 վայրկյան անգործությունը անընդունելի է, և ավելի լավ է այսքան հարցումներ չմշակել: Մոնիտորով լուծումը պարզվեց, որ ամենևին էլ մասշտաբային չէ։

Ամփոփում

Ինչպես տեսնում եք այս փոքրիկ օրինակներից, .NET-ն աջակցում է համաժամացման բազմաթիվ կառուցվածքների: Այնուամենայնիվ, միշտ չէ, որ ակնհայտ է, թե ինչպես օգտագործել դրանք: Հուսով եմ, որ այս հոդվածը օգտակար էր: Առայժմ սա վերջն է, բայց դեռ շատ հետաքրքիր բաներ են մնացել, օրինակ՝ thread-safe հավաքածուներ, TPL Dataflow, Reactive programming, Software Transaction մոդելը և այլն։

Տեղեկատվության աղբյուրներ

• Հոսքի պատկերացում. Concurrency Visualizer
• MSDN: threading, Ասինխրոն ծրագրավորման օրինաչափություններ եւ շատ ուրիշներ մյուսները
• [Richter] - CLR C#-ի միջոցով, Ջեֆրի Ռիխտեր
• [Էրիկ Լիպերտ] - Կողպեքի մասին
• Աղբյուրի կոդը
• Նկար - «Պար սրերի մեջ», Գ.Սեմիրադսկի

Source: www.habr.com