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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علم کامپیوتر، معکوس کردن اولویت یک سناریوی مشکل در برنامه ریزی است که در آن یک کار با اولویت بالا به طور غیر مستقیم توسط یک کار با اولویت متوسط در حال دستیابی است که به طور موثر "معکوس" اولویت نسبی دو کار است.

این امر ناقض مدل اولویت است که فرایندهای با اولویت بالا تنها می‌توانند مانع اجرا شدن توسط فرایندهای اولویت بالاترو به طور خلاصه فرایندهای اولویت پایین شوند که به سرعت تکمیل خواهد شد. استفاده از منابع به اشتراک گذاشته شده توسط فرایندهای با اولویت بالا و پایین.

مثالی از معکوس کردن اولویت[ویرایش]

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

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

نتایج[ویرایش]

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

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

راه حل‌ها[ویرایش]

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

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

توجه کنید که این تنها کار در زمانی است که همه وقفه‌ها توانایی اجرا ندارند. اگر فقط یک وقفهٔ دستگاههای سخت‌افزار به خصوص غیرفعال باشد اولویت معکوس دوباره توسط اولویت‌بندی وقفه‌های سخت‌افزار تولید می‌شود. در ورژن‌های اولیه Unix مجموعه‌ای از اولیه‌هایی با نام‌های Splx(0)… splx(7) همهٔ وقفه‌هایی را که از اولویت معین فعال می‌شوند غیرفعال می‌کند. با انتخاب مناسب بالاترین اولیت بین همهٔ وقفه‌هایی که همواره به ناحیه بحرانی وارد می‌شوند، مسئله اولویت معکوس می‌تواند بدون قفل کردن همهٔ وقفه‌ها حل شود. سقف‌ها به ترتیب نرخ یکنواخت (rate-monotonic) انتساب داده می‌شوند، به عبارت دیگر دستگاههای کندتر اولویت کمتری دارند.

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

سقف اولویت[ویرایش]

با استفاده از سقف اولویت، فرایند mutex مشترک (که کد سیستم عامل را اجرا می‌کند) یک اولویت ویژه (بالا) دارد که آن را به کار قفل کردن mutex انتساب می‌دهد. این کارها اولویت بالا برای بقیه کارهایی که سعی در دسترسی به mutex را دارند و اولویت بالاتری نسبت به سقف اولویت ندارند فراهم می‌کنند.

ارث‌بری اولویت[ویرایش]

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

بالا بردن تصادفی[ویرایش]

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

جلوگیری کردن از قفل کردن[ویرایش]

به دلیل اینکه در اولویت معکوس کار با اولویت کم کار با اولویت بالا را قفل می‌کند یک روش برای اجتناب از قفل کردن اولویت معکوس روش Avoid blocking است برای مثال با استفاده از همگام سازی بدون قفل یا با روش read-copy-update

منابع[ویرایش]

  1. hat Really Happened on Mars by Glenn Reeves of the JPL Pathfinder team
  2. Jump up Explanation of priority inversion problem experienced by Mars Pathfinder
  3. Jump up Lampson, B; Redell, D. (June 1980). "Experience with processes and monitors in MESA". Communications of the ACM (CACM). 23 (2): 105–117.