अच्छी तरह से खिलाए गए दार्शनिक या प्रतिस्पर्धी .NET प्रोग्रामिंग

उदाहरण के तौर पर फिलॉसॉफर्स डाइनिंग प्रॉब्लम का उपयोग करते हुए आइए देखते हैं कि समवर्ती और समानांतर प्रोग्रामिंग .Net में कैसे काम करती है। योजना यह है, धागे/प्रक्रियाओं के सिंक्रनाइज़ेशन से, अभिनेता मॉडल (निम्नलिखित भागों में)। लेख पहले परिचित के लिए या आपके ज्ञान को ताज़ा करने के लिए उपयोगी हो सकता है।

ऐसा बिल्कुल क्यों करें? ट्रांजिस्टर अपने न्यूनतम आकार तक पहुँच जाते हैं, मूर का नियम प्रकाश की गति की सीमा पर टिका होता है और इसलिए संख्या में वृद्धि देखी जाती है, अधिक ट्रांजिस्टर बनाए जा सकते हैं। इसी समय, डेटा की मात्रा बढ़ रही है, और उपयोगकर्ता सिस्टम से तत्काल प्रतिक्रिया की अपेक्षा करते हैं। ऐसी स्थिति में, "सामान्य" प्रोग्रामिंग, जब हमारे पास एक निष्पादन थ्रेड होता है, अब प्रभावी नहीं होता है। आपको किसी तरह एक साथ या समवर्ती निष्पादन की समस्या को हल करने की आवश्यकता है। इसके अलावा, यह समस्या विभिन्न स्तरों पर मौजूद है: थ्रेड्स के स्तर पर, प्रक्रियाओं के स्तर पर, नेटवर्क में मशीनों के स्तर पर (वितरित सिस्टम)। .NET के पास ऐसी समस्याओं को जल्दी और कुशलता से हल करने के लिए उच्च-गुणवत्ता, समय-परीक्षणित प्रौद्योगिकियाँ हैं।

कार्य

Edsger Dijkstra ने 1965 की शुरुआत में इस समस्या को अपने छात्रों के सामने रखा। स्थापित सूत्र इस प्रकार है। दार्शनिकों की एक निश्चित (आमतौर पर पांच) संख्या और समान संख्या में कांटे होते हैं। वे एक गोल मेज पर बैठते हैं, उनके बीच कांटे होते हैं। दार्शनिक अपनी अंतहीन भोजन की थाली से खा सकते हैं, सोच सकते हैं या प्रतीक्षा कर सकते हैं। एक दार्शनिक को खाने के लिए, आपको दो कांटे लेने की जरूरत है (आखिरी वाला पहले के साथ कांटा साझा करता है)। कांटे को उठाना और नीचे रखना दो अलग-अलग क्रियाएं हैं। सभी दार्शनिक मौन हैं। काम है ऐसा एल्गोरिद्म ढूंढ़ना कि ये सभी 54 साल बाद भी सोचेंगे और भरे रहेंगे।

सबसे पहले, आइए साझा स्थान के उपयोग के माध्यम से इस समस्या को हल करने का प्रयास करें। कांटे आम ​​मेज पर पड़े होते हैं और दार्शनिक उन्हें तभी ले लेते हैं जब वे होते हैं और उन्हें वापस रख देते हैं। यहां सिंक्रोनाइज़ेशन की समस्याएं हैं, अचूक दांव कब लेना है? यदि कांटा न हो तो क्या होगा? आदि। लेकिन पहले, आइए दार्शनिकों से शुरुआत करें।

थ्रेड शुरू करने के लिए, हम थ्रेड पूल का उपयोग करते हैं 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);
}

थ्रेड पूल को थ्रेड निर्माण और विलोपन को अनुकूलित करने के लिए डिज़ाइन किया गया है। इस पूल में कार्यों के साथ कतार है और सीएलआर इन कार्यों की संख्या के आधार पर धागे बनाता है या हटा देता है। सभी AppDomains के लिए एक पूल। इस पूल का उपयोग लगभग हमेशा किया जाना चाहिए, क्योंकि। धागे बनाने, हटाने, उनकी कतारों आदि से परेशान होने की आवश्यकता नहीं है। पूल के बिना यह संभव है, लेकिन फिर आपको इसे सीधे उपयोग करना होगा Thread, यह उन मामलों के लिए उपयोगी है जब आपको किसी थ्रेड की प्राथमिकता को बदलने की आवश्यकता होती है, जब हमारे पास एक लंबा ऑपरेशन होता है, फोरग्राउंड थ्रेड आदि के लिए।

दूसरे शब्दों में, System.Threading.Tasks.Task वर्ग समान है Thread, लेकिन सभी प्रकार की सुविधाओं के साथ: अन्य कार्यों के एक ब्लॉक के बाद एक कार्य को चलाने की क्षमता, उन्हें कार्यों से वापस करना, आसानी से उन्हें बाधित करना, और बहुत कुछ। आदि। उन्हें async / प्रतीक्षा निर्माण (कार्य-आधारित अतुल्यकालिक पैटर्न, 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), जो परमाणु अनुक्रमिक पढ़ने और लिखने के लिए स्मृति का एक टुकड़ा ताला लगा देता है। और स्पिनवाइट निर्माण के बराबर है 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 और आदि।)। इसलिए, त्रुटि संचालकों को स्वयं थ्रेड्स में और सुंदर समाप्ति के साथ आवश्यक हैं।

Oficiant

ठीक है, हम इस गतिरोध, भुखमरी और मौत की समस्या को कैसे सुलझा सकते हैं? हम केवल एक दार्शनिक को कांटे तक पहुंचने की अनुमति देंगे, इस स्थान के लिए धागे का पारस्परिक बहिष्करण जोड़ें। इसे कैसे करना है? मान लीजिए कि एक वेटर दार्शनिकों के बगल में खड़ा है, जो किसी एक दार्शनिक को कांटे लेने की अनुमति देता है। हम इस वेटर को कैसे बनाएंगे और दार्शनिक उससे कैसे पूछेंगे, सवाल दिलचस्प हैं।

सबसे सरल तरीका है जब दार्शनिक बस वेटर से लगातार कांटे तक पहुंचने के लिए कहेंगे। वे। अब दार्शनिक पास के कांटे का इंतजार नहीं करेंगे, बल्कि इंतजार करेंगे या वेटर से पूछेंगे। सबसे पहले, हम इसके लिए केवल यूजर स्पेस का उपयोग करते हैं, इसमें हम कर्नेल से किसी भी प्रक्रिया को कॉल करने के लिए इंटरप्ट का उपयोग नहीं करते हैं (उनके बारे में नीचे)।

उपयोगकर्ता स्थान में समाधान

यहां हम वही करेंगे जो एक कांटे और दो दार्शनिकों के साथ करते थे, हम एक चक्र में घूमेंगे और प्रतीक्षा करेंगे। लेकिन अब यह सभी दार्शनिक होंगे और जैसा कि यह था, केवल एक कांटा, यानी। यह कहा जा सकता है कि वेटर से यह "सुनहरा कांटा" लेने वाले दार्शनिक ही खाएंगे। इसके लिए हम स्पिनलॉक का इस्तेमाल करते हैं।

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 (जो वहाँ प्रयोग किया जाता है)। अब वह जानता है कि प्रतीक्षा करने वालों को कैसे गिनना है, उन्हें थोड़ा सुलाना है, और बहुत कुछ। आदि सामान्य तौर पर, अनुकूलन के लिए हर संभव प्रयास करता है। लेकिन हमें याद रखना चाहिए कि यह अभी भी वही सक्रिय चक्र है जो प्रोसेसर संसाधनों को खा जाता है और प्रवाह को बनाए रखता है, जो भुखमरी का कारण बन सकता है यदि दार्शनिकों में से एक दूसरों की तुलना में अधिक प्राथमिकता बन जाता है, लेकिन इसमें सुनहरा कांटा नहीं होता है (प्राथमिकता उलटा समस्या) . इसलिए, हम इसे केवल साझा स्मृति में बहुत ही कम परिवर्तनों के लिए उपयोग करते हैं, बिना किसी तृतीय-पक्ष कॉल, नेस्टेड लॉक और अन्य आश्चर्य के।

के लिए आरेखण SpinLock. सुनहरे कांटे के लिए धाराएँ लगातार "लड़" रही हैं। विफलताएँ हैं - चित्र में, चयनित क्षेत्र। कोर का पूरी तरह से उपयोग नहीं किया जाता है: इन चार धागों द्वारा केवल लगभग 2/3।

यहां एक और समाधान केवल उपयोग करना होगा Interlocked.CompareExchange उपरोक्त कोड में दिखाए गए समान सक्रिय प्रतीक्षा के साथ (भूख से मरने वाले दार्शनिकों में), लेकिन यह, जैसा कि पहले ही कहा गया है, सैद्धांतिक रूप से अवरुद्ध हो सकता है।

पर Interlocked यह ध्यान दिया जाना चाहिए कि न केवल है CompareExchange, लेकिन परमाणु पढ़ने और लिखने के अन्य तरीके भी। और परिवर्तन की पुनरावृत्ति के माध्यम से, यदि किसी अन्य थ्रेड के पास अपने परिवर्तन करने का समय है (1 पढ़ें, 2 पढ़ें, 2 लिखें, 1 लिखें खराब है), इसका उपयोग एकल मान में जटिल परिवर्तनों के लिए किया जा सकता है (इंटरलॉक्ड एनीथिंग पैटर्न) .

कर्नेल मोड समाधान

लूप में संसाधनों की बर्बादी से बचने के लिए, आइए देखें कि हम थ्रेड को कैसे ब्लॉक कर सकते हैं। दूसरे शब्दों में, हमारे उदाहरण को जारी रखते हुए, देखते हैं कि वेटर दार्शनिक को सोने के लिए कैसे डालता है और केवल आवश्यक होने पर उसे जगाता है। सबसे पहले, आइए देखें कि ऑपरेटिंग सिस्टम के कर्नेल मोड के माध्यम से इसे कैसे किया जाए। वहाँ सभी संरचनाएँ अक्सर उपयोगकर्ता स्थान की तुलना में धीमी होती हैं। कई बार धीमा, उदाहरण के लिए AutoResetEvent शायद 53 गुना धीमा SpinLock [रिक्टर]। लेकिन उनकी मदद से, आप पूरे सिस्टम में प्रक्रियाओं को सिंक्रनाइज़ कर सकते हैं, प्रबंधित या नहीं।

यहां की मूल संरचना दिज्क्स्ट्रा द्वारा आधी सदी पहले प्रस्तावित सेमाफोर है। एक सेमाफोर, सरल शब्दों में, सिस्टम द्वारा प्रबंधित एक सकारात्मक पूर्णांक है, और उस पर दो ऑपरेशन, वेतन वृद्धि और कमी। यदि यह घटने में विफल रहता है, शून्य, तो कॉलिंग थ्रेड अवरुद्ध है। जब संख्या किसी अन्य सक्रिय थ्रेड/प्रक्रिया द्वारा बढ़ाई जाती है, तो थ्रेड्स को छोड़ दिया जाता है और पास की गई संख्या से सेमाफोर फिर से घट जाता है। एक टोंटी में एक सेमाफोर के साथ ट्रेनों की कल्पना कर सकते हैं। .NET समान कार्यक्षमता वाले कई निर्माण प्रदान करता है: AutoResetEvent, ManualResetEvent, Mutex और मैं खुद Semaphore. हम इस्तेमाल करेंगे AutoResetEvent, यह इन निर्माणों में सबसे सरल है: केवल दो मान 0 और 1 (गलत, सत्य)। उसकी विधि WaitOne() यदि मान 0 था, तो कॉलिंग थ्रेड को ब्लॉक कर देता है, और यदि 1, इसे 0 तक कम कर देता है और इसे छोड़ देता है। एक विधि Set() 1 तक उठाता है और एक वेटर को जाने देता है, जो फिर 0 पर नीचे आता है। सबवे टर्नस्टाइल की तरह काम करता है।

आइए समाधान को जटिल करें और प्रत्येक दार्शनिक के लिए लॉक का उपयोग करें, न कि सभी के लिए एक साथ। वे। अब एक साथ कई दार्शनिक हो सकते हैं, एक नहीं। लेकिन हम दौड़ (दौड़ की स्थिति) से बचने के लिए सही तरीके से टेबल तक पहुंच को फिर से ब्लॉक कर देते हैं।

// Для блокирования отдельного философа.
// Инициализируется: 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, क्योंकि सी # में एक प्रसिद्ध है lock वाक्य - विन्यास। Monitor यह 1 (म्यूटेक्स) के अधिकतम मान के साथ एक ही सेमाफोर है, लेकिन एक लूप, रिकर्सन, कंडीशन वेरिएबल पैटर्न (नीचे उस पर अधिक), आदि में प्रतीक्षा के लिए समर्थन के साथ, आइए इसके साथ एक समाधान देखें।

// Спрячем объект для Монитора от всех, чтобы без дедлоков.
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), जो सभी वस्तुओं में मौजूद हैं। इसलिए, यदि कोई अनुपयुक्त वस्तु का चयन किया जाता है, तो आप आसानी से गतिरोध प्राप्त कर सकते हैं (उदाहरण के लिए, यदि आप एक आंतरिक स्ट्रिंग पर लॉक करते हैं)। हम इसके लिए हमेशा छुपी हुई वस्तु का उपयोग करते हैं।

कंडीशन वेरिएबल पैटर्न आपको कुछ जटिल स्थिति की अपेक्षा को अधिक संक्षेप में लागू करने की अनुमति देता है। .NET में, मेरी राय में, यह अधूरा है, क्योंकि सिद्धांत रूप में, कई चर (पॉज़िक्स थ्रेड्स में) पर कई कतारें होनी चाहिए, न कि एक लोक पर। तब कोई उन्हें सभी दार्शनिकों के लिए बना सकता था। लेकिन इस रूप में भी, यह आपको कोड को कम करने की अनुमति देता है।

कई दार्शनिक या async / await

ठीक है, अब हम थ्रेड्स को प्रभावी रूप से ब्लॉक कर सकते हैं। लेकिन क्या होगा अगर हमारे पास बहुत सारे दार्शनिक हैं? 100? 10000? उदाहरण के लिए, हमें वेब सर्वर से 100000 अनुरोध प्राप्त हुए। प्रत्येक अनुरोध के लिए एक थ्रेड बनाना ओवरहेड होगा, क्योंकि इतने सारे धागे समानांतर में नहीं चलेंगे। केवल उतने ही चलेंगे जितने तार्किक कोर हैं (मेरे पास 4 हैं)। और बाकी सब सिर्फ संसाधनों को छीन लेंगे। इस समस्या का एक समाधान async/प्रतीक्षा पैटर्न है। इसका विचार यह है कि यदि फ़ंक्शन को कुछ जारी रखने के लिए प्रतीक्षा करने की आवश्यकता है तो फ़ंक्शन थ्रेड को नहीं रखता है। और जब यह कुछ करता है, तो यह अपने निष्पादन को फिर से शुरू करता है (लेकिन जरूरी नहीं कि उसी धागे पर!) हमारे मामले में, हम कांटे की प्रतीक्षा करेंगे।

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. इसके माध्यम से, आप विधि के पूरा होने की प्रतीक्षा कर सकते हैं, इसे रद्द कर सकते हैं, और बाकी सब कुछ जो आप टास्क के साथ कर सकते हैं। विधि के अंदर, राज्य मशीन निष्पादन को नियंत्रित करती है। लब्बोलुआब यह है कि यदि कोई देरी नहीं होती है, तो निष्पादन समकालिक होता है, और यदि होता है, तो थ्रेड जारी किया जाता है। इसे बेहतर ढंग से समझने के लिए इस स्टेट मशीन को देखना बेहतर होगा। इनसे आप चेन बना सकते हैं async / await तरीके।

चलो परीक्षण करते हैं। 100 लॉजिकल कोर, 4 सेकंड वाली मशीन पर 8 दार्शनिकों का काम। मॉनिटर के साथ पिछले समाधान ने केवल पहले 4 धागे चलाए और बाकी बिल्कुल नहीं चले। इन 4 थ्रेड्स में से प्रत्येक लगभग 2ms के लिए निष्क्रिय था। और async / प्रतीक्षा समाधान सभी 100 चला, प्रत्येक 6.8 सेकंड के औसत प्रतीक्षा के साथ। बेशक, वास्तविक प्रणालियों में, 6 सेकंड के लिए निष्क्रिय होना अस्वीकार्य है और इस तरह के कई अनुरोधों को संसाधित नहीं करना बेहतर है। मॉनिटर वाला समाधान बिल्कुल भी मापनीय नहीं निकला।

निष्कर्ष

जैसा कि आप इन छोटे उदाहरणों से देख सकते हैं, .NET कई तुल्यकालन संरचनाओं का समर्थन करता है। हालांकि, यह हमेशा स्पष्ट नहीं होता है कि उनका उपयोग कैसे किया जाए। मुझे उम्मीद है कि यह लेख मददगार था। अभी के लिए, यह अंत है, लेकिन अभी भी बहुत सी दिलचस्प चीजें बाकी हैं, उदाहरण के लिए, थ्रेड-सुरक्षित संग्रह, टीपीएल डेटाफ्लो, रिएक्टिव प्रोग्रामिंग, सॉफ्टवेयर लेनदेन मॉडल, आदि।

सूत्रों का कहना है

• प्रवाह दृश्यता: समवर्ती विज़ुअलाइज़र
• MSDN: थ्रेडिंग, अतुल्यकालिक प्रोग्रामिंग पैटर्न और कई अन्य एट अल।
• [रिक्टर] - सी# के माध्यम से सीएलआर, जेफरी रिक्टर
• [एरिक लिपर्ट] - लॉक के बारे में
• स्रोत कोड
• चित्र - "तलवारों के बीच नृत्य", जी। सेमिरैडस्की

स्रोत: www.habr.com