ভাল-ফেড দার্শনিক বা প্রতিযোগিতামূলক .NET প্রোগ্রামিং

আসুন দেখি কিভাবে সমসাময়িক এবং সমান্তরাল প্রোগ্রামিং .Net-এ কাজ করে, উদাহরণ হিসেবে ফিলোসফার্স ডাইনিং প্রবলেম ব্যবহার করে। পরিকল্পনা হল এই, থ্রেড/প্রসেসের সিঙ্ক্রোনাইজেশন থেকে অভিনেতা মডেল পর্যন্ত (নিম্নলিখিত অংশে)। নিবন্ধটি প্রথম পরিচিতির জন্য বা আপনার জ্ঞানকে রিফ্রেশ করার জন্য উপযোগী হতে পারে।

কেন এটা সব? ট্রানজিস্টর তাদের সর্বনিম্ন আকারে পৌঁছায়, মুরের আইন আলোর গতির সীমাবদ্ধতার উপর নির্ভর করে এবং সেইজন্য সংখ্যায় বৃদ্ধি পরিলক্ষিত হয়, আরও ট্রানজিস্টর তৈরি করা যেতে পারে। একই সময়ে, ডেটার পরিমাণ বাড়ছে, এবং ব্যবহারকারীরা সিস্টেমগুলি থেকে একটি তাত্ক্ষণিক প্রতিক্রিয়া আশা করে৷ এমন পরিস্থিতিতে, "স্বাভাবিক" প্রোগ্রামিং, যখন আমাদের একটি কার্যকরী থ্রেড থাকে, তখন আর কার্যকর হয় না। আপনাকে একরকম বা একযোগে কার্যকর করার সমস্যার সমাধান করতে হবে। তদুপরি, এই সমস্যাটি বিভিন্ন স্তরে বিদ্যমান: থ্রেডের স্তরে, প্রক্রিয়াগুলির স্তরে, নেটওয়ার্কের মেশিনগুলির স্তরে (বিতরণ করা সিস্টেম)। দ্রুত এবং দক্ষতার সাথে এই ধরনের সমস্যা সমাধানের জন্য .NET-এর উচ্চ-মানের, সময়-পরীক্ষিত প্রযুক্তি রয়েছে।

কাজের

এডজার ডিজকস্ট্রা 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);
}

থ্রেড পুলটি থ্রেড তৈরি এবং মুছে ফেলার জন্য অপ্টিমাইজ করার জন্য ডিজাইন করা হয়েছে। এই পুলে টাস্ক সহ একটি সারি রয়েছে এবং CLR এই কাজের সংখ্যার উপর নির্ভর করে থ্রেড তৈরি করে বা সরিয়ে দেয়। সমস্ত AppDomains জন্য একটি পুল. এই পুল প্রায় সবসময় ব্যবহার করা উচিত, কারণ. থ্রেড তৈরি করা, মুছে ফেলা, তাদের সারি ইত্যাদি নিয়ে মাথা ঘামানোর দরকার নেই৷ এটি একটি পুল ছাড়াই সম্ভব, তবে আপনাকে এটি সরাসরি ব্যবহার করতে হবে Thread, যখন আপনাকে একটি থ্রেডের অগ্রাধিকার পরিবর্তন করতে হবে, যখন আমাদের একটি দীর্ঘ অপারেশন আছে, একটি ফোরগ্রাউন্ড থ্রেড ইত্যাদির ক্ষেত্রে এটি কার্যকর।

অন্য কথায়, System.Threading.Tasks.Task ক্লাস একই Thread, কিন্তু সব ধরণের সুবিধার সাথে: অন্যান্য কাজের একটি ব্লকের পরে একটি টাস্ক চালানোর ক্ষমতা, সেগুলিকে ফাংশন থেকে ফিরিয়ে দেওয়া, সুবিধামত বাধা দেওয়া এবং আরও অনেক কিছু। ইত্যাদি। এগুলিকে অ্যাসিঙ্ক/ওয়েট কনস্ট্রাকশন সমর্থন করার জন্য প্রয়োজন (টাস্ক-ভিত্তিক অ্যাসিঙ্ক্রোনাস প্যাটার্ন, আইও অপারেশনের জন্য অপেক্ষা করার জন্য সিনট্যাকটিক চিনি)। আমরা পরে এই বিষয়ে কথা হবে.

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

এই কোড সম্পর্কে গুরুত্বপূর্ণ বিষয় হল যে চারটি দার্শনিকের মধ্যে দুইজন তাদের বাম কাঁটা নিচে রাখতে ভুলে যান। এবং দেখা যাচ্ছে যে তারা আরও খাবার খায়, অন্যরা ক্ষুধার্ত হতে শুরু করে, যদিও থ্রেডগুলির একই অগ্রাধিকার রয়েছে। এখানে তারা পুরোপুরি ক্ষুধার্ত নয়, কারণ। খারাপ দার্শনিকরা কখনও কখনও তাদের কাঁটা পিছনে রাখে। দেখা যাচ্ছে ভালো মানুষ খারাপের চেয়ে প্রায় ৫ গুণ কম খায়। সুতরাং কোডে একটি ছোট ত্রুটি কর্মক্ষমতা হ্রাসের দিকে নিয়ে যায়। এখানে এটিও লক্ষণীয় যে একটি বিরল পরিস্থিতি সম্ভব যখন সমস্ত দার্শনিক বাম কাঁটা নেয়, সেখানে ডান কেউ নেই, তারা বামদিকে রাখেন, অপেক্ষা করেন, আবার বামটি নেন ইত্যাদি। এই পরিস্থিতিও অনাহার, অনেকটা অচলাবস্থার মতো। আমি এটি পুনরাবৃত্তি করতে ব্যর্থ হয়েছে. নীচে এমন একটি পরিস্থিতির জন্য একটি ছবি যেখানে দুটি খারাপ দার্শনিক উভয়ই কাঁটাচামচ নিয়েছে এবং দুটি ভাল ক্ষুধার্ত।

এখানে আপনি দেখতে পারেন যে থ্রেডগুলি মাঝে মাঝে জেগে ওঠে এবং সংস্থান পেতে চেষ্টা করে। চারটি কোরের মধ্যে দুটি কিছুই করে না (উপরের সবুজ গ্রাফ)।

একজন দার্শনিকের মৃত্যু

ঠিক আছে, আরেকটি সমস্যা যা দার্শনিকদের একটি মহিমান্বিত নৈশভোজে বাধা দিতে পারে তা হ'ল যদি তাদের মধ্যে একজন হঠাৎ তার হাতে কাঁটা নিয়ে মারা যায় (এবং তারা তাকে এভাবে কবর দেবে)। তারপর প্রতিবেশীদের রাতের খাবার ছাড়াই চলে যাবে। আপনি এই ক্ষেত্রে নিজের জন্য একটি উদাহরণ কোড নিয়ে আসতে পারেন, উদাহরণস্বরূপ, এটি ফেলে দেওয়া হয় 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 (যা সেখানে ব্যবহৃত হয়)। এখন তিনি জানেন কীভাবে অপেক্ষাকারীদের গণনা করতে হবে, তাদের একটু ঘুমাতে হবে এবং আরও অনেক কিছু। ইত্যাদি। সাধারণভাবে, অপ্টিমাইজ করার জন্য সবকিছু সম্ভব করে। কিন্তু আমাদের অবশ্যই মনে রাখতে হবে যে এটি এখনও একই সক্রিয় চক্র যা প্রসেসরের সংস্থানগুলিকে খায় এবং প্রবাহকে ধরে রাখে, যা ক্ষুধার্ত হতে পারে যদি একজন দার্শনিক অন্যদের চেয়ে বেশি অগ্রাধিকার পায়, কিন্তু সোনার কাঁটা না থাকে (অগ্রাধিকার বিপরীত সমস্যা) . অতএব, আমরা এটি ব্যবহার করি শুধুমাত্র শেয়ার করা মেমরিতে খুব অল্প পরিবর্তনের জন্য, কোনো তৃতীয় পক্ষের কল, নেস্টেড লক এবং অন্যান্য চমক ছাড়াই।

জন্য অঙ্কন 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, কারণ C# এ একটি সুপরিচিত আছে lock বাক্য গঠন. Monitor এটি একই সেমাফোর যার সর্বোচ্চ মান 1 (mutex), কিন্তু একটি লুপে অপেক্ষা করার জন্য সমর্থন, পুনরাবৃত্তি, কন্ডিশন ভেরিয়েবল প্যাটার্ন (নীচে আরও বেশি), ইত্যাদি। এর সাথে একটি সমাধান দেখা যাক।

// Спрячем объект для Монитора от всех, чтобы без дедлоков.
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টি আছে)। এবং বাকি সবাই সম্পদ কেড়ে নেবে। এই সমস্যার একটি সমাধান হল অ্যাসিঙ্ক/ওয়েট প্যাটার্ন। এর ধারণা হল যে ফাংশনটি থ্রেড ধরে রাখে না যদি এটি চালিয়ে যাওয়ার জন্য কিছু অপেক্ষা করতে হয়। এবং যখন এটি কিছু করে, এটি তার মৃত্যুদন্ড পুনরায় শুরু করে (তবে একই থ্রেডে অগত্যা নয়!) আমাদের ক্ষেত্রে, আমরা কাঁটাচামচ জন্য অপেক্ষা করব।

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টি থ্রেডের প্রতিটি প্রায় 2 মিলিমিটারের জন্য নিষ্ক্রিয় ছিল। এবং অ্যাসিঙ্ক/ওয়েট সলিউশনটি 100টি চলে, যার প্রতিটির গড় অপেক্ষা 6.8 সেকেন্ড। অবশ্যই, বাস্তব সিস্টেমে, 6 সেকেন্ডের জন্য নিষ্ক্রিয় থাকা অগ্রহণযোগ্য এবং এর মতো এতগুলি অনুরোধ প্রক্রিয়া না করাই ভাল। মনিটরের সাথে সমাধানটি মোটেই স্কেলযোগ্য নয় বলে প্রমাণিত হয়েছে।

উপসংহার

আপনি এই ছোট উদাহরণগুলি থেকে দেখতে পাচ্ছেন, .NET অনেকগুলি সিঙ্ক্রোনাইজেশন গঠন সমর্থন করে। যাইহোক, কিভাবে তাদের ব্যবহার করতে হবে তা সবসময় স্পষ্ট নয়। আমি এই নিবন্ধটি সহায়ক ছিল আশা করি. আপাতত, এটাই শেষ, কিন্তু এখনও অনেক আকর্ষণীয় জিনিস বাকি আছে, যেমন, থ্রেড-সেফ কালেকশন, টিপিএল ডেটাফ্লো, রিঅ্যাকটিভ প্রোগ্রামিং, সফটওয়্যার লেনদেন মডেল ইত্যাদি।

সূত্র

• ফ্লো ভিজ্যুয়ালাইজেশন: কনকারেন্সি ভিজ্যুয়ালাইজার
• MSDN: থ্রেডিং, অ্যাসিঙ্ক্রোনাস প্রোগ্রামিং প্যাটার্ন এবং অনেক অন্যান্য এট অল।
• [রিখটার] - C# এর মাধ্যমে CLR, Jeffrey Richter
• [এরিক লিপার্ট] - তালা সম্পর্কে
• উত্স কোড
• ছবি - "তলোয়ার মধ্যে নাচ", জি সেমিরাডস্কি

উত্স: www.habr.com