پرش به محتوا

نخست کوتاه‌ترین کار

از ویکی‌پدیا، دانشنامهٔ آزاد

نخست کوتاه‌ترین کار (به انگلیسی: Shortest Job First) که با نام کوتاه‌ترین کار بعدی (به انگلیسی: Shortest job next) هم شناخته می‌شود، یک سیاست زمان‌بندی در سیستم‌عامل است. در این الگوریتم، از بین فرایندهای منتظر در صف اجرا، فرایندی انتخاب می‌شود که به کوتاه‌ترین زمان برای اجرا شدن نیاز داشته باشد. این الگوریتم، یک الگوریتم انحصاری است. الگوریتم کوتاه‌ترین زمان باقیمانده حالت غیرانحصاری این الگوریتم است. این الگوریتم از نظر سادگی به صرفه و مناسب است. همچنین این الگوریتم، میانگین مدت زمانی که هر پروسه باید منتظر باشد تا اجرایش کامل شود را هم به حداقل می‌رساند.

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

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

منابع

[ویرایش]
  1. Silberschatz, A.; Galvin, P.B.; Gagne, G. (2005). Operating Systems Concepts (7th ed.). Wiley. p. 161. ISBN 0-471-69466-5.
  2. Tanenbaum, A. S. (2008). Modern Operating Systems (3rd ed.). Pearson Education, Inc. p. 156. ISBN 0-13-600663-9.