انحصار متقابل

انحصار متقابل[ ۱] ( به انگلیسی: Mutual exclusion ) به اختصار mutex الگوریتمی است که در برنامه نویسی همروند برای جلوگیری از استفادهٔ همزمان از منابع مشترک مانند متغیرهای سراسری توسط قسمتی از کد رایانه که به آن بخش بحرانی گفته می شود به کار می رود. به عبارت دیگر، باید مطمئن شویم که دو فرایند یا دو ریسه به طور همزمان وارد ناحیه بحرانی خود نشده اند. خودِ بخش بحرانی، ساختار یا الگوریتمی برای انحصار متقابل نیست. یک برنامه، پردازش، یا نخ ( به انگلیسی: Thread ) می تواند بخش بحرانی داشته باشد بدون اینکه ساختار یا الگوریتمی که انحصار متقابل را پیاده سازی کند داشته باشد. [ ۲]
مسئله انحصار متقابل اولین بار توسط ادسخر دکسترا شناسایی و حل شد. یک مثال از اینکه چرا انحصار متقابل در عمل اهمیت دارد را می توان به کمک لیست پیوندی نشان داد. در یک لیست پیوندی یک طرفه، حذف کردن یک گره، اشاره گر next گره قبلی را با گره بعدی مقدار دهی می کنیم. برای مثال اگر بخواهیم گره i را حذف کنیم، باید اشاره گر next گره i - 1 را طوری تغییر دهیم که به گره i+1 اشاره کند. اگر این لیست در بین چند فرایند به اشتراک گذاشته شده باشد، ممکن است دو پروسه بخواهد به شکل همزمان دو گره متفاوت را از لیست حذف کنند که مشکل زیر را ایجاد می کند:
اگر قرار باشد گره i و i+1 حذف شوند و هیچ کدام از آن ها هم گره سر یا گره دم نباشند ( گره داخلی باشند ) ، اشاره گر next گره i - 1 باید به i+1 اشاره کند و اشاره گر next گره i باید به گره i+2 اشاره کند. هر چند که هر دو عملِ حذف، با موفقیت انجام می شود، اما گره i+1 در لیست باقی خواهد ماند و حذف نخواهد شد. چرا که گره i - 1، با جا انداختن گره i ( که به i+2 اشاره می کرد ) ، به گره i+1 اشاره می کند. این مشکل در شکل روبرو نشان داده شده است. این مشکل را می توان با استفاده از انحصار متقابل حل کرد. به این صورت که باید مطمئن شویم که یک دو یا چند فرایند سعی نمی کنند قسمت یکسانی از لیست را به شکل همزمان تغییر دهند. در برنامه نویسی از سمافورها برای این کار استفاده می شود.
این مشکل را هم می توان به شکل سخت افزاری و هم به شکل نرم افزاری حل کرد.
در سیستم های تک پردازنده ای، راحت ترین راه این است که در هنگام ورود فرایند به ناحیه بحرانی، کلیه وقفه ها را غیر فعال کنیم. بدین ترتیب، وقتی که پروسه ای در ناحیه بحرانی قرار دارد، هیچ روال وقفه گیری اجرا نخواهد شد، حتی وقفه ساعت هم بی اثر می شود و فرایند قبضه نخواهد شد. هر چند که این راه حل مؤثر است، اما مشکلات زیادی را ایجاد می کند. اگر ناحیه بحرانی طولانی باشد، باعث می شود که فرایند بتواند تا هر وقتی که خواست پردازنده را در اختیار بگیرد، چرا که روال وقفه گیر برای وقفه ساعت اجرا نمی شود و پردازنده فرایند جاری را تعویض نمی کند. در حقیقت نمی توان به برنامه کاربر اطمینان کرد. همچنین اگر پروسه در حالی که در ناحیه بحرانی قرار دارد، از کار بیفتد، کنترل هیچگاه به پروسه دیگری داده نمی شود و در نتیجه کل سیستم از کار خواهد افتاد. یک راه حل بهتر برای برقرارسازی انحصار متقابل، استفاده از راه حل انتظار مشغول است.