الگوریتم زمان بندی SJF در پایتون
الگوریتم SJF یک الگوریتم زمان بندی برای برنامه های کاربردی یا پروسه‌های سیستم عامل است که بر اساس طول زمان اجرای باقی‌مانده آن‌ها ترتیب اجرا را تعیین می‌کند. SJF به عنوان یک الگوریتم غیرقطعی (non-preemptive) عمل می‌کند، به این معنی که زمانی که یک پروسه شروع به اجرا کرد، تا پایان آن اجرا خواهد شد و در صورتی که پروسه جدیدی با طول زمان اجرای کمتری وارد سیستم شود، تنها پس از پایان اجرای پروسه فعلی شروع به اجرا می‌کند. در SJF، پروسه‌ها بر اساس طول زمان اجرای باقی‌مانده‌ی آن‌ها مرتب می‌شوند و پروسه با کوچکترین طول زمان اجرای باقی‌مانده به عنوان بعدی انتخاب می‌شود. این الگوریتم می‌تواند به صورت غیرقابل بازگشت (non-preemptive) یا قابل بازگشت (preemptive) پیاده‌سازی شود.
در الگوریتم SJF، هرگاه یک پروسه جدید وارد سیستم شود، زمان باقی‌مانده آن را محاسبه کرده و با پروسه هایی که در صف قرار دارند مقایسه می‌کند. پروسه‌ای که باقی‌مانده کوچکتری دارد نیز در صف بعدی قرار می گیرد. در صورتی که پروسه‌ای با باقی‌مانده کمتری وارد صف شود، آن پروسه باید منتظر پایان اجرای پروسه فعلی باشد. اگر پروسه‌ای با باقی‌مانده کمتری وارد شود و الگوریتم SJF به صورت قابل بازگشت پیاده‌سازی شده باشد، پروسه جدید ممکن است بلافاصله شروع به اجرا کند و پروسه فعلی در حال اجرا، به حالت انتظار در آید. در SJF، ممکن است پروسه‌های با طول زمان اجرای طولانی بیش از حد برای پروسه‌های با طول زمان اجرای کوتاه تر در صف منتظر بمانند، که مشکلی به نام انتظار بی مورد (Convoy Effect) ایجاد می‌کند. این مشکل به این دلیل پیش می‌آید که پروسه‌های طولانی‌مدت باعث می‌شوند که پروسه های کوتاه تر نیز برای انتظار در صف قرار بگیرند و به این ترتیب، زمان اجرای کلی کاهش می‌یابد.
بنابراین، الگوریتم SJF می‌تواند در صورتی که پروسه‌های با طول زمان اجرای متفاوت وجود دارند، بهینه ترین زمانبندی را به دست آورد؛ اما در صورت وجود پروسه‌هایی با طول زمان اجرای طولانی، ممکن است به مشکلاتی برخورد کند. برای رفع مشکلات SJF، الگوریتم‌های دیگری مانند الگوریتم زمان بندی Round Robin یا الگوریتم زمان بندی Priority می‌توانند مورد استفاده قرار گیرند. برای مثال، در الگوریتم زمان بندی Round Robin، هر پروسه به طور متوسط به مدت زمان ثابتی اجرا می‌شود و پس از آن، اگر هنوز اجرایی دارند، به صف برمی‌گردند و پروسه دیگری شروع به اجرا می‌کند. در الگوریتم زمان بندی Priority نیز، پروسه‌ها بر اساس اولویت‌شان مرتب می‌شوند و پروسه‌های با اولویت بالاتر اجرای اولویت‌دار را تعطیل کرده و خود شروع به اجرا می‌کنند. این الگوریتم‌ها به عنوان روش های بهینه سازی زمانبندی، در مواردی که SJF به مشکل برخورد می‌کند، می‌توانند مورد استفاده قرار گیرند.
پیاده سازی الگوریتم SJF به زبان Python
در الگوریتم SJF (Shortest Job First)، فرایندی که کمترین زمان اجرای آن را دارد، اولویت بیشتری در برنامه ریزی دارد. در این مثال ورودی های ما شامل نام فرایند ، زمان ورود و زمان اجرا بوده و خروجی مورد انتظار نیز نمودار گانت مربوط به زمانبندی کل پروسه ها توسط CPU می باشد. برای پیاده سازی این الگوریتم در زبان برنامه نویسی پایتون، می‌توانیم از یک لیست از دیکشنری‌ها برای نگهداری اطلاعات هر فرایند استفاده کنیم. در هر دیکشنری، سه کلید “name” (نام فرایند)، “arrival_time” (زمان ورود) و “burst_time” (زمان اجرا) برای نگهداری اطلاعات فرایند وجود دارد. سپس، با استفاده از تابع sorted و key، لیست فرایندها به ترتیب زمان اجرا مرتب می‌شود. در ادامه، با استفاده از یک حلقه، فرایندها به ترتیب زمان اجرا اجرا می‌شوند و نمودار گانت ساخته می‌شود.
کد پیاده سازی این الگوریتم در زبان پایتون به شکل زیر است:
def sjf(processes): # مرتب‌سازی فرایندها بر اساس زمان اجرا sorted_processes = sorted(processes, key=lambda x: x['burst_time']) # زمان شروع اولیه برابر با زمان ورود فرایند اول current_time = sorted_processes[0]['arrival_time'] # ساختن نمودار گانت gantt_chart = [] # اجرای هر فرایند به ترتیب زمان اجرا for process in sorted_processes: # اگر زمان ورود فرایند بعد اززمان کنونی باشد، زمان کنونی را برابر با زمان ورود فرایند قرار می‌دهیم if process['arrival_time'] > current_time: current_time = process['arrival_time'] # افزودن فرایند به نمودار گانت gantt_chart.append({'name': process['name'], 'start_time': current_time}) # افزایش زمان کنونی با زمان اجرای فرایند current_time += process['burst_time'] # نمایش نمودار گانت print("Gantt Chart:") for process in gantt_chart: print(process['name'], end=' ') print() # محاسبه میانگین زمان انتظار و زمان اجرا total_wait_time = 0 total_burst_time = 0 for process in processes: wait_time = gantt_chart[0]['start_time'] - process['arrival_time'] for i in range(1, len(gantt_chart)): if gantt_chart[i]['name'] == process['name']: wait_time= gantt_chart[i]['start_time'] - gantt_chart[i-1]['start_time'] - process['burst_time'] break total_wait_time += wait_time total_burst_time += process['burst_time'] avg_wait_time = total_wait_time / len(processes) avg_turnaround_time = (total_wait_time + total_burst_time) / len(processes) print(f"Average Wait Time: {avg_wait_time:.2f}") print(f"Average Turnaround Time: {avg_turnaround_time:.2f}")
در این کد، تابع sjf یک لیست از دیکشنری‌ها به نام processes دریافت می‌کند و با استفاده از تابع sorted و key، فرایندها بر اساس زمان اجرا مرتب می‌شوند. سپس، با حلقه اجرای هر فرایند به ترتیب زمان اجرا صورت می‌گیرد و نمودار گانت ساخته می‌شود. سپس، با محاسبه میانگین زمان انتظار و زمان اجرا، عملکرد الگوریتم SJF بررسی می‌شود و در نهایت مقادیر میانگین زمان انتظار و زمان اجرا چاپ می‌شوند. برای استفاده از این تابع، می‌توانیم یک لیست از دیکشنری‌ها به عنوان ورودی به تابع sjf بدهیم. مثال استفاده از این تابع به شکل زیر است:
processes = [ {'name': 'P1', 'arrival_time': 0, 'burst_time': 8}, {'name': 'P2', 'arrival_time': 1, 'burst_time': 4}, {'name': 'P3', 'arrival_time': 2, 'burst_time': 9}, {'name': 'P4', 'arrival_time': 3, 'burst_time': 5}, {'name': 'P5', 'arrival_time': 4, 'burst_time': 2}, ] sjf(processes)
در این مثال، ۵ فرایندبا نام‌های P1 تا P5 با زمان‌های ورود و زمان اجرا مشخص شده‌اند. تابع sjf با استفاده از این لیست از فرایندها فراخوانی می‌شود و نمودار گانت و میانگین زمان انتظار و زمان اجرا چاپ می‌شود.