در این مطلب جدید دام های متداولی که در برنامه نویسان تازه کار در هنگام ایجاد برنامه های چندریسمانه یا multi-threaded یا چندنخی، در آن ها گرفتار می شوند را معرفی می کنیم. با ما در وبسایت آموزش الگوریتم ها و برنامه نویسی ، اوپن مایند، همراه باشید.

بن بست ها، قطحی منابع، لایولاک و وضعیت رقابتی

بن بست ها (Deadlocks)، قطحی (Starvation)، لایولاک (Livelock) و وضعیت رقابتی (Race Conditions) بلای جان برنامه های چندنخی یا multithreaded هستند. این موارد می توانند عملکرد کل سیستمی را که دچار آن ها شده متوقف سازند. پس بهتر که به مانند انیشتین ابتدا خیلی خوب تعریف مشکل و مسئله را بفهمیم و سپس برای حل آن ها راه حلی بیاندیشیم. یادآوری می شود که انیشتین گفته است:

اگر من یک ساعت برای حل مسئله زمان در اختیار داشته باشم، ۵۵ دقیقه از آن زمان را صرف فکر کردن درباره خود مسئله می کردم و ۵ دقیقه باقی مانده را به فکر درباره روش حل اختصاص می دادم.

تعاریف Livelock ، Deadlock ، Starvation و Race Conditions

حالت بن بست یا Deadlock چیست؟

این حالت زمانی میان دو پردازه یا process اتفاق می افتد که هر کدام از دو پردازه رقیب (از لحاظ منابع لازم) منتظر اتمام پردازش دیگری باشد تا بالاخره پردازش خود را شروع کند. در واقع طی این مدت چون هر دو پردازه منتظر آن دیگری هستند، پس هیچ پردازشی انجام نمی شود و فقط انتظار بی نهایت ایجاد می شود. این حالت همان بن بست یا Deadlock نام دارد.

حالت گرسنگی یا قحطی یا Starvation چیست؟

گرسنگی یا قحطی زمانی پیش می آید به هر دلیلی، یک پردازه به یک یا چند منبع (resource) مورد نیازش دسترسی پیدا نکند و برنامه اجرایی آن هرگز پایان نیابد (به طور مثال یک پردازه از برنامه دیگری، حق استفاده از منبع مورد نیاز پردازه ما را در اختیار داشته باشد و رها نکند).

وضعیت رقابتی یا Race Conditions چیست؟

زمانی که به جای اتمام اجرای هر پردازه طبق ترتیبی خاص، پردازه ها بدون ترتیب و در میان زمان اجرای دیگران، به شکل چند نخی (multiple threading) مدیریت و اجرا شوند. منظور آن است که برای خواندن و نوشتن مقدار داده ها، بدون ترتیب خاصی زمینه اجرای پردازه ها متوقف و تغییر کند و پردازه ها مقادیر منابع داده ای مشترک را بدون ترتیب و بدون اطلاع دیگران تغییر دهند که موجب رفتارها و نتایج ناخواسته و غیرمنطقی گردد (مثل مسئله تولید کننده-مصرف کننده).

حالت Livelock چیست؟

می توان گفت که Livelock نوع خاصی از گرسنگی یا Starvation است که به بن بست یا Deadlock هم بی شباهت نیست. در واقع زمانی که دو پردازه به سیگنال پردازه دیگری برای شروع پردازش نیاز دارد، اما حداقل یکی از آن دو پیشروی خاصی در پردازش خود ندارد یا این که هر دو هم زمان به همدیگر سیگنال دهند، می گوییم Livelock پیش امده است.

تعارف زدن ما ایرانی ها هنگام ورود یا برداشتن خوراک نمونه خوبی برای Livelock است! فرض کنید دو نفر برای بالا رفتن از یک راهرو پلکانی همزمان به همدیگر می رسند و هر کدام می خواهند به رسم ادب، دیگری اول برود. باز هم فرض کنید که بی اندازه زمان دارند و بی اندازه مودب هستند، پس آن ها می توانند ساعت ها و حتی سال ها به همدیگر تعارف کنند و با وجود خالی بودن راهرو (به عنوان منبع مشترک) هیچکدام از آن دو (به عنوان پردازه) بالا نروند. یا فرض کنید سر سفره، یکی به دیگری ظرف خوراک را بدهد که مقداری بردارد، اما آن دیگری بلافاصله ظرف را برگرداند و تعارف کند که اولی مقدم تر است و این چرخه همین طور ادامه یابد.

گمان می کنم با مثال های بالا، اگر یک ایرانی (که مودب و نوع دوست است) باشید، تعریف Livelock را با تمام وجود درک کرده اید!

با بن بست یا Deadlock چه کنیم؟

بیایید به Deadlock کمی عینی تر نگاه کنیم و درباره خود مسئله بیشتر فکر کنیم و بعد به سراغ راه حل برویم (نقل قول انیشتین را همچنان ملکه ذهن خود داشته باشیم). مجموعه ای از تقاطع های شهری را در نظر بگیرید که ترافیک آن ها به شکل زیر قفل شده است.

ترافیک قفل شده در تعدادی تقاطع شهری

در هر خیابان هر ردیف از ماشین ها منتظرند تا در خیابان دیگر ماشین ها عبور کنند تا بلکه خودشان هم بتوانند رد شوند. اما از آن جا که همه منتظر دیگری هستند، تمام ترافیک قفل شده و عبور و مرور انجام نمی شود.

در حوزه صحبت چند نخی (multithreading) ، اگر A تعدادی منبع را در اختیار گرفته باشد و به تعداد دیگری که B گرفته است نیاز داشته باشد تا پردازشش تمام شود، و B نیز به همین ترتیب به منابع A برای تکمیل نیازها و اتمام پردازش نیاز داشته باشد، هیچ کدام اجرا و کامل نمی شوند و این وضعیت کاملاً مختل کننده است. یک مثال واضح تر در جدول زیر ارائه شده است. ابتدا خودتان به دقت آن را بررسی کنید.

یک نمونه از اجرا و تخصیص منابع که دچار بن بست شده

در مثالی که جزئیات آن در جدول بالا نشان داده شده، هر کدام از نخ ها (threads) به منابع ۱ ، ۲ ، ۳ و ۴ برای کامل کردن اجرای خود نیاز دارند، اما فقط حق دسترسی به دو تا از آن ها را پیدا کرده اند. از آن جا که هیچکدام از نخ ها منابع در اختیار خود را آزاد نمی کنند تا دیگری استفاده کند، یک انتظار بی نهایت و بن بست ایجاد شده است. این شبیه به این است که در تصویر اول ماشین های هر خیابان می خواهند رو به جلو برانند و نیاز دارند تا مسیر جلو آزاد باشد، اما ماشین های ردیف جلویی هم که بخشی از خیابان را اشغال کرده اند و می خواهند عبور کنند، حاضر نیست دنده عقب بگیرند (منابع را به نفع اجرای دیگری آزاد کنند).

راه چاره برای Deadlock

خوشبختانه روش هایی برای حل بن بست وجود دارد. به نظر می رسد که انتقال پیام و انتقال سیگنال مابین نخ ها، برای ایجاد نوعی هماهنگی و یا نوعی ترتیب بندی در زمان و یا نوبت استفاده، می تواند مفید باشد. این روش ها به interprocess communication و mutex و semaphore ها معروف هستند. صحبت درباره هر کدام از آن ها مقاله ای جداگانه را می طلبد که در تحریریه اوپن مایند در حال اماده سازی برای انتشار هستند. اما حالا که به تفصیل درباره بن بست صحبت کردیم و ایده های حل آن و نام برخی از حل های موجود را آوردیم، می توانید خودتان هم دست به کار شوید!

با گرسنگی یا قحطی یا Starvation چه کنیم؟

تجربه شخصی ثابت کرده که در حین آموزش مشکلات و دام های معمول برنامه نویسی چند نخی، گرسنگی یا Starvation از همه قابل فهم تر است! چرا که همان است که نام آن بیان می کند.

می گوییم یک پردازه واقعاً دچار گرسنگی و قحطی است، اگر که هیچ وقت منابعی که می خواهد به آن داده نشود و هیچ وقت پردازش را انجام ندهد (ادامه ندهد). به مانند انچه در ابتدا برای بن بیان شد، یک مثال عینی تر به نزدیک تر شدن ما به مسئله کمک می کند. به تصویر چهارراه زیر بنگرید. در این چهارراه اگر در یک خیابان ماشینی رد شود، در خیابان متقاطع آن، ماشین ها باید متوقف شوند یا اصطلاحاً استاپ کنند. حالا فرض کنید در یک خیابان جریان بی شماری از ماشین های عبوری را داشته باشیم (یک پردازه منبع یا منابعی را هیچگاه آزاد نکند)، آن گاه ماشین های خیابان متقاطع هیچگاه نمی توانند عبور کنند (منابع لازم برای پردازش را هیچگاه به دست نمی آورند).

تصویر یک چهارراه که می تواند در آن قحطی یا starvation پیش آید

در این چهارراه اگر جریان بی شماری از ماشین از راست به چپ/چپ به راست وجود داشته باشد، ماشین های خیابان بالا به پایین/پایین به بالا دچار قحطی منبع (خیابان آزاد برای عبور) می شوند!

حالا به جدول زیر نگاه کنید. پردازه نخ A منابع ۱ ، ۲ ، ۳ و ۴ را در اخیتار دارد اما هیچگاه آن ها رها نمی کند و نخ B هم که به آن منابع نیاز دارد، هیچگاه اجرا نمی شود و در قحطی منابع به سر می برد.

یک نمونه از اجرا و تخصیص منابع که دچار قحطی شده

راه چاره برای Starvation

یک راه حل ساده برای گرسنگی یا starvation آن است که یک mutex بسازیم که بر اساس قطعه های زمانی، نوبت دهی استفاده نخ ها از منابع را مدیریت کند. الزامی به استفاده از زمان برای ایجاد عدالت در استفاده از منابع نیست؛ در واقع هر عامل دیگری که در طراحی برنامه به نظر شما برای ایجاد این عدالت به شکل بازپس گیری اجباری منابع و تخصیص به دیگری درست می آید، قابل استفاده است. یک ایده آن است که اگر مثلاً اگر یک نخ نیاز به عملیات i/o داشت، به دلیل زمان گیر بودن این نوع عملیات، نوبت استفاده از سی پی یو را از آن بگیریم و به دیگری بدهیم تا عملیات درخواستی آن روی دیسک یا شبکه پایان پذیرد.

با وضعیت رقابتی یا Race conditions چه کنیم؟

در برنامه نویسی چند نخی هنگامی که صحبت از وضعیت رقابتی به میان می آید، معمولاً منظور رقابت بر سر داده هاست (تفاوتی میان Race conditions و data race وجود دارد که به زیبایی در این مطلب به قلم یکی از اساتید دانشگاه یوتاه توضیح داده شده است: Race Condition vs. Data Race). این وضعیت رقابتی برای داده ها زمانی پیش می آید که دو نخ (thread) به طور همزمان به یک داده حساس اشتراکی که مسیر اجرای الگوریتم نخ فعلی به مقدار آن وابستگی زیادی دارد، دسترسی پیدا کنند و مقدار آن را تغییر دهند. در این باره می توانید درباره ناحیه بحرانی در الگوریتم های موازی تحقیق کنید تا چیزی از موضوع نماند که گنک باشد.

گاهی اوقات رقابت بر سر داده اشتراکی، رفتارهای ناخواسته و بسیار عجیبی در برنامه ایجاد می کند که امکان دارد در اجراهای قبلی مشاهده نشده باشد. همین موضوع تشخیص دقیق مشکل را بسیار دشوار می کند. پس به نظر می آید که شما به عنوان برنامه نویس لازم است که خوب این مشکل را بشناسید و طوری برنامه را پیاده سازی کنید که از آن جلوگیری به عمل آورید؛ چرا که در عمل وضعیت رقابتی بسیار فاجعه بار است و به بیشتر اوقات به بن بست (deadlock) یا قحطی (starvation) در اجرای چند نخی می انجامد.

یک مثال وضعیت رقابتی در دنیای واقعی

بسیار پیش می آید که در چهار راهی یکی می خواهد از تقاطع آن چهار راه عبور کند و دیگری از خیابان بغلی چراغ قرمز را رد می کند و یک تصادف پیش می آید (رقابت بر سر عبور) و راه بندان می شود. و همانطور که گفتیم در نهایت می تواند به بن بست ختم شود. یادتان هست که در بخش تعریف گفتیم وضعیت رقابتی یا Race conditions زمانی اتفاق می افتد که ترتیب به هم بخورد؟ خب آن راننده که چراغ قرمز را رد کرده، همان است که بدون ترتیب وارد بخش اشتراکی (فضای تقاطع چهار راه) شده است.

مثالی از وضعیت رقابتی برای عبور از میان چهار راه

صد البته که در پردازش کامپیوتری مقداری فرق در بیان موضوع هست. ما در آن جا خودمان خواسته ایم که برنامه های چند نخی بنویسیم و قدرت و زمان پردازشی را میان چند نخ تقسیم کنیم. پس کنترل ترتیب و جلوگیری از وضعیت رقابتی بر سر اشتراکات چه می شود؟ در ادامه درباره راه حل هم صحبت خواهیم کرد.

یک مثال وضعیت رقابتی در برنامه نویسی چند نخی

همانطور که صحبت آن شد، ضروری است تا از داده های حساس اشتراکی که مسیر اجرای الگوریتم در قدم های بعدی به مقادیر آن ها وابسته است، به طور ناخواسته از طرف دیگر پردازه ها دستکاری نشود تا بالاخره پردازه فعلی کارش با بخش مقادیر حساس اشتراکی (ناحیه بحرانی) تمام شود. اما اگر به فرض مثال چاره ای برای این موضوع نیاندیشیم، چه می شود؟ مثال زیر را ببینیم.

مثالی از رقابت بر سر پردازش یک داده اشتراکی

در این مثال، چون نخ A و B هر دو همزمان و بدون اطلاع از پردازش یکدیگر (بدون mutex و signaling) در حال اجرا هستند، مشخص نیست مقدار نهایی resource 1 چه می شود! در صورتی که نخ A انتظار دارد سه باشد و نخ B انتظار دارد که چهار باشد! چندتا از احتمالات ممکن به شکل زیر است:

• resource 1 برابر با سه باشد (نخ B قبل از اجرای نخ A به طور کامل اجرا شود)
• resource 1 برابر با چهار باشد (نخ A قبل از اجرای نخ B به طور کامل اجرا شود)
• resource 1 برابر با پنج باشد (اول A: Resource 1 = 2، دوم B: Resource 1 = 3، سوم A: Recourse 1 += 1، چهارم B: Resource 1 += 1 و در نهایت Resource 1 برابر با ۵)
• از طرق مختلف دیگر resource 1 برابر با سه یا چهار باشد.

کاملاً مشخص است که این هدف ما از برنامه نویسی نیست. ما نمی خواهیم نتیجه نامشخص و تصادفی باشد و رفتارهای ناخواسته در اجرای برنامه خود داشته باشیم. برای جلوگیری از این مورد کافی است حواسمان باشد که طوری مدیریت نخ ها را انجام دهیم که به طور همزمان هر دو در بخش حساس و بحرانی نباشند (برای مثال بالا، هر دو همزمان در بخش انتساب و افزایش برای Resource 1 نباشند که جا به جایی نوبت اجرای آن ها در پردازش چندنخی، موجب تغییرات ناخواسته در مقدار ذخیره شده دیگر نخ نشود).

راه چاره برای Race conditions

در واقع ما برای کنترل رقابت بر سر داده های اشتراکی، نیاز داریم تا اعمال ما در بخش حساس الگوریتم روی داده های اشتراکی اصطلاحاً تجزینه ناپذیر یا atomic باشد؛ به این معنی که یک پردازش واحد و غیر قابل توقف و بدون دخالت دیگران را تا انتها با موفقیت به انجام برسانیم. با استفاده از mutex می توانیم به این هدف برسیم و در واقع مدیریت حق دسترسی بودن در ناحیه بحرانی اجرا را توسط mutex انجام دهیم و مطمئن باشیم در هر لحظه فقط یک پردازه روی ناحیه اشتراکی حساس در حال پردازش است و دیگران هم با اطلاع از این موضوع، روی آن بخش پردازش نمی کنند تا بالاخره حق دسترسی به آن ها منتقل شود.

مطالعه درباره مسئله تولیدکننده – مصرف کننده (Producer-Consumer) و نحوه مدیریت مدل چند نخی آن، دید خوبی برای روبرو شدن با وضعیت رقابتی به شما می دهد. مثال خوبی از مسئله در تحریریه اوپن میاند در دست آماده سازی قرار دارد.

با Livelock چه کنیم؟

لایولاک را می توان بن بستی برای حفظ ادب یا اولویت تصور کرد؛ هر چه که هست خصومتی در کار نیست! لایولاک جایی میان یک بن بست و قحطی قرار می گیرد (چرا که نه پردازه ای به منابع می رسد و نه پیشرفتی حاصل می شود). به طور دقیق تر، زمانی که دو پردازه می توانند با همدیگر ارتباط بگیرند (از طریق انتقال پیام مستقیم، متغیرهای مشترک و غیره) و هر دو پردازه می خواهند با هماهنگی و بر اساس پاسخ دیگری کاری را انجام دهند، اما هر دو پیغام یا واکنش یکسانی به همدیگر می دهند، هیچکدام نمی تواند تصمیم بگیرد که پیشروی کند.

الگوی Livelock

الگوی این اتفاق را باید به خوبی بشناسید تا از ایجاد ناخواسته آن اجتناب کنید. برای توضیح این الگو، پاراگراف بالا را بیشتر باز می کنیم. اگر پردازه ها از داشتن منابع در اختیارشان به نفع اجرای پردازه دیگری بر اساس حدس خود یا هر درخواستی از آن دیگری رها کنند (نوعی تعارف)، و ۱- دوباره سریعاً آن را بگیرند یا ۲- دیگری هم به نفع اولی رها کند (باز هم همان تعارف و کوتاه آمدن)، آن گاه لایولاک در برنامه حتمی است.

مثال های بیشتر برای Livelock

در بخش تعریف، دو مثال برای لایولاک ارائه شد. حالا مثال زیر را هم ارائه می دهیم تا ببینید الگوی لایولاک چگونه در خود نمود پیدا می کند. در کد جاوای زیر، رستم و تهمینه هر دو گرسنه اند و می خواند خوراک میل کنند (الگوریتم پردازش)؛ اما فقط یک قاشق (منبع مشترک) وجود دارد. و آن ها هم بسیار همدیگر را دوست می دارند و در قبال هم فداکاری می کنند. پس هر دو به همدیگر تعارف می کنند که دیگری اول از قاشق استفاده کند و خوراک بخورد. در نتیجه هیچکدام راضی نمی شوند قبل از دیگری قاشق را استفاده کنند و لایولاک اتفاق می افتد. به بخش هایلات شده که گرسنگی طرف مقابل را بررسی می کند، دقت کنید.

public class Livelock {
    static class Spoon {
        private Diner owner;
        public Spoon(Diner d) { owner = d; }
        public Diner getOwner() { return owner; }
        public synchronized void setOwner(Diner d) { owner = d; }
        public synchronized void use() { 
            System.out.printf("%s has eaten!", owner.name); 
        }
    }

    static class Diner {
        private String name;
        private boolean isHungry;

        public Diner(String n) { name = n; isHungry = true; }       
        public String getName() { return name; }
        public boolean isHungry() { return isHungry; }

        public void eatWith(Spoon spoon, Diner spouse) {
            while (isHungry) {
                // Don't have the spoon, so wait patiently for spouse.
                if (spoon.owner != this) {
                    try { Thread.sleep(1); } 
                    catch(InterruptedException e) { continue; }
                    continue;
                }                       

                // If spouse is hungry, insist upon passing the spoon.
                if (spouse.isHungry()) {                    
                    System.out.printf(
                        "%s: You eat first my darling %s!%n", 
                        name, spouse.getName());
                    spoon.setOwner(spouse);
                    continue;
                }

                // Spouse wasn't hungry, so finally eat
                spoon.use();
                isHungry = false;               
                System.out.printf(
                    "%s: I am stuffed, my darling %s!%n", 
                    name, spouse.getName());                
                spoon.setOwner(spouse);
            }
        }
    }

    public static void main(String[] args) {
        final Diner husband = new Diner("Rostam");
        final Diner wife = new Diner("Tahmineh");

        final Spoon s = new Spoon(husband);

        new Thread(new Runnable() { 
            public void run() { husband.eatWith(s, wife); }   
        }).start();

        new Thread(new Runnable() { 
            public void run() { wife.eatWith(s, husband); } 
        }).start();
    }
}

در جدول زیر هم این مورد در اجرای دو نخ A و B که هر دو resource 1 را برای اجرا نیاز دارند، نشان داده شده است. آن ها مدام حق دسترسی resource 1 را قبل از استفاده و به محص دریافت، به همدیگر پاس می دهند و هیچکدام در اجرای خود پیشروی ندارند.

یک مثال از رخداد Livelock میان دو نخ

همان طور که متوجه شدید، هر دو نخ A و B به محض دریافت درخواست دیگری، منبع را رها می کند و بلافاصله هم دوباره درخواست استفاده از آن را به دیگری می فرستد. این اتفاق به طور مداوم بعد از دریافت درخواست و بعد از محض رها سازی تکرار می شود و مانع از پیشروی کل برنامه می شود.

راه چاره برای Livelock

یک راه حل ساده و خوب این است که، مدت زمانی میان رهاسازی یک منبع و ارسال درخواست برای دریافت مجدد آن قائل شویم. بدین ترتیب موجب می شویم که پردازه دارای منبع، فرصتی برای شروع پردازش داشته باشد و در یک حلقه باطل گرفتار نشود.

امیدواریم از این مقاله در وبسایت اوپن مایند استفاده کافی را برده باشید و همواره برنامه های چندنخی بهتری بنویسید.

لطفاً در نوشتن نظر، پرسش و انتقاد مردد نباشید و آن ها را با ما در میان بگذارید.