صف چندسطحی فیدبک

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

در رایانش، صف چندسطحی فیدبک (به انگلیسی: Multilevel feedback queue) یک الگوریتم زمان‌بندی است. در این الگوریتم چند صف در سیستم وجود دارد که فرایندها وارد این صف‌ها می‌شوند. هر صف می‌تواند الگوریتم زمان‌بندی خاص خود را داشته باشد. صف‌ها نسبت به یکدیگر اولویت دارند. این الگوریتم برای پاسخگویی به موارد زیر در نظر گرفته شده است:

چند صف FIFO استفاده می‌شود و عملیات به شرح زیر است:

  1. یک فرایند جدید در انتهای اولین صف FIFO قرار می‌گیرد. (که اولوین اولین صف نسبت به بقیه بالاتر است)
  2. وقتی که فرایند به سر صف رسید، پردازنده به آن اختصاص می‌یابد.
  3. اگر فرایند به اتمام رسید، سیستم را ترک خواهد کرد
  4. اگر فرایند به شکل داوطلبانه کنترل را واگذاری کرد، صف‌ها را ترک خواهد کرد، و وقتی که مجدداً آماده شد، وارد همان صفی می‌شود که از آن خارج شده بود.
  5. اگر فرایند از کل برش زمانی خود استفاده کرد اما به اتمام نرسید، پردازنده از آن گرفته شده و فرایند مورد نظر وارد یک صف سطح پایینتر می‌شود.
  6. این عملیات ادامه می‌یابد تا فرایند مورد نظر به اتمام رسیده و یا به آخرین صف برسد.
    • در آخرین صف، فرایند به روش نوبت گردشی زمان‌بندی می‌شود تا به اتمام برسد و از سیستم خارج شود.
    • به طور اختیاری، اگر پروسه برای انجام عمل ورودی/خروجی بلوکه شود، یک سطح «ارتقا» یافته و در انتهای یک صف سطح بالاتر قرار می‌گیرد. به این ترتیب زمان‌بند به فرایندهای با تنگنای ورودی/خروجی اولویت بخشیده و به این پروسه‌ها اجازه «فرار» از آخرین صف را می‌دهد.

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

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

  • Kleinrock, L.; Muntz, R. R. (July 1972). "Processor Sharing Queueing Models of Mixed Scheduling Disciplines for Time Shared System". Journal of the ACM 19 (3): 464–482. DOI:10.1145/321707.321717.