معکوس کردن اولویت

دو کار H و L رو در نظر بگیرید، که به ترتیب دارای ارجحیت بالا و پایین هستند. هر کدام از این دو کار می‌تواند استفاده انحصاری از یک منبع مشترک به نام R را به دست آورد. اگر بعد از این که L منبع را به دست آورد، H تلاش کند تا منبع را به دست گیرد، آنگاه H تا زمانی که L منبع را رها نکرده‌است، مسدود می‌شود. به اشتراک گذاشتن یک منبع با استفاده انحصاری (در این مورد R) در یک سیستم که به خوبی طراحی شده‌است، معمولاً مستلزم این هست که L بلافاصله R را رها کند تا H، که یک کار با ارجحیت بالاتر است، برای مدت طولانی در وضعیت انسداد باقی نماند. با وجود این طراحی خوب، این امکان وجود دارد که یک کار سوم به نام M که دارای ارجحیت متوسط است، در زمانی که L از منبع R استفاده می‌کند، اجرا شود. در این لحظه، M که دارای ارجحیت بالاتر از L هست، اجرای L را متوقف می‌کند (زیرا M وابسته به R نیست) و باعث می‌شود تا L نتواند فوراً R را رها کند و در عوض، موجب می‌شود H که پروسه‌ای با بیشترین ارجحیت است، نتواند اجرا شود. در واقع H دچار یک انسداد غیرقابل پیش‌بینی می‌شود که به‌طور غیر مستقیم توسط یک کار با ارجحیت پایین‌تر نظیر M ایجاد شده‌است.

در برخی موارد وارونگی ارجحیت می‌تواند بدون ایجاد آسیب فوری رخ دهد، در این حالت کسی متوجه نمی‌شود که کار با ارجحیت بالاتر با تأخیر انجام شده‌است و سرانجام کاری که ارجحیت پایین‌تر دارد، منبع مشترک را آزاد می‌کند. با این وجود، موقعیت‌های بسیاری وجود دارد که در آن وارونگی ارجحیت می‌تواند باعث مشکلات جدی شود. اگر کاری که بیشترین ارجحیت را دارد دچار قحطی منابع شود، ممکن است منجر به اختلال عملکرد سیستم یا تحریک آغاز یک اقدام اصلاحی از پیش تعریف شده شود، مثلاً باعث شود که تایمر نگهبان کل سیستم را ریست کند. مشکلی که برای کاوشگر مریخ با نام Mars Pathfinder در سال ۱۹۹۷ پیش آمد، یک مثال کلاسیک از مشکلاتی است که در نتیجه وارونگی ارجحیت در سیستم‌های بی درنگ به وجود می‌آید.

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

این مشکل از دهه ۱۹۷۰ وجود داشته‌است. Lampson و Redell یکی از اولین مقالات را در رابطه با مشکل وارونگی ارجحیت منتشر کردند. سیستم‌هایی نظیر کرنل یونیکس، برای حل مشکل از عنصر ()splx استفاده می‌کنند. هیچ روش بی نقصی برای پیش‌بینی این مشکل وجود ندارد. با این وجود، راه حل‌های مختلفی وجود دارند که از بین آنها شایع ترین‌ها به شرح زیر هستند:

غیرفعال کردن تمام وقفه‌ها برای محافظت از نواحی بحرانی

زمانی که از غیرفعال کردن وقفه‌ها برای پیشگیری از وارونگی ارجحیت استفاده می‌شود، فقط دو ارجحیت وجود دارد: قابلیت بازداشته شدن و وقفه‌های غیرفعال شده. در نبود ارجحیت سوم، وارونگی غیرممکن است. از آنجایی که فقط یک قطعه دادهٔ قفل وجود دارد (بیت فعال کننده وقفه)، فلذا، قفل کردن نامنظم غیرممکن است و بنابراین بن‌بست هرگز رخ نمی‌دهد. از آنجایی که نواحی بحرانی همیشه باید تا کامل شدن اجرا شوند، بنابراین تعلیق نیز رخ نمی‌دهد. توجه کنید که این روش فقط زمانی جواب می‌دهد که تمام وقفه‌ها غیرفعال شده باشند. اگر فقط وقفهٔ وسیلهٔ سخت‌افزاری خاصی غیرفعال شده باشد، وارونگی ارجحیت مجدداً توسط اولویت بندی وقفه‌ها توسط سخت‌افزار مورد نظر ایجاد می‌شود. با انتخاب مناسب بالاترین اولویت هر وقفه ای که تاکنون وارد ناحیه بحرانی شده‌است، می‌توان مشکل وارونگی ارجحیت را بدون قفل کردن تمام وقفه‌ها برطرف کرد. انتساب سقف‌ها، بترتیب نرخ-یکنواخت است، یعنی ابزارهای کندتر دارای ارجحیت‌های پایین‌تر هستند.

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

پروتکل سقف ارجحیت

در پروتکل سقف ارجحیت، پروسه میوتکس مشترک (که کد سیستم عامل را اجرا می‌کند)، دارای یک ارجحیت مشخصهٔ بالا برای خودش است که به عملی که میوتکس را قفل می‌کند اختصاص داده شده‌است. این روش به خوبی کار می‌کند، به شرط اینکه عمل/اعمال دیگری که سعی می‌کند که به میوتکس دسترسی پیدا کند، دارای ارجحیتی بالاتر از ارجحیت سقف نباشد.

وراثت اولویت

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

تقویت تصادفی

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

اجتناب از مسدود کردن

از آنجایی که وارونگی ارجحیت، در واقع، زمانی رخ می‌دهد که یک عمل با ارجحیت پایین یک عمل با ارجحیت بالا را مسدود می‌کند، لذا یک راه حل برای پیشگیری از وارونگی ارجحیت این است که از مسدود شدن اجتناب کنیم، برای مثال، با استفاده از همگام سازی غیر مسدودکننده یا روش آماده- کپی-به‌روز رسانی.

• بن‌بست (علوم رایانه)
• قفل (رایانه)
• الگوریتم‌های غیرمسدودکننده
• انحصار متقابل
• گرسنگی منابع

مشارکت‌کنندگان ویکی‌پدیا. «Priority inversion». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۳ آوریل ۲۰۲۱.

1. ↑ Glenn Reeves, What Really Happened on Mars, JPL Pathfinder team, retrieved 2019-01-04
2. ↑ Explanation of priority inversion problem experienced by Mars Pathfinder (PDF), retrieved 2019-01-04
3. ↑ Lampson, B; Redell, D. (June 1980). "Experience with processes and monitors in MESA". Communications of the ACM. 23 (2): 105–117. CiteSeerX 10.1.1.46.7240. doi:10.1145/358818.358824. S2CID 1594544.
4. ↑ Priority Inversion on MSDN