تعیین برش زمانی پویا در الگوریتم زمانبندی نوبت گردشی با استفاده از یادگیری ماشین

یکی از رایج‌ترین الگوریتم‌های زمانبندی پردازنده در سیستم‌های اشتراک زمانی، الگوریتم نوبت گردشی است. در این الگوریتم یک برش زمانی در نظر گرفته می‌شود که بیانگر حداکثر زمانی است که فرآیند می‌تواند پردازنده را در اختیار داشته باشد و پردازنده به اندازه برش زمانی به صورت چرخشی به فرآیندهای صف آماده تخصیص می‌یابد. اندازه برش زمانی تاثیر بسزایی بر کارایی الگوریتم نوبت گردشی دارد به گونه‌ای که اگر برش زمانی خیلی کوتاه باشد، به دلیل افزایش تعداد تعویض‌متن و سربار ناشی از آن، بهره‌وری پردازنده کاهش می‌یابد. در مقابل اگر برش زمانی خیلی بزرگ باشد، میانگین زمان پاسخ فرآیندها افزایش می‌یابد که استفاده از الگوریتم نوبت گردشی در کاربردهای تعاملی را ناکارآمد می‌سازد. هدف این مقاله ارائه روشی کارا برای تعیین برش زمانی به صورت پویا با استفاده از یادگیری ماشین است. برای این منظور، ابتدا یک مجموعه آموزش شامل ویژگی‌های تعداد فرآیندها و بیشینه، کمینه، میانگین و میانه زمان انفجار فرآیند‌ها و ویژگی هدف برش زمانی بهینه ساخته شد. سپس با آموزش طبقه‌بندهای یادگیری ماشین بر روی این مجموعه به پیش‌بینی برش زمانی بهینه برای نمونه‌های جدید پرداخته شد. نتایج ارزیابی‌ها نشان می‌دهد که در مجموع روش پیشنهادی در مقایسه با سایر روش‌های تعیین برش زمانی عملکرد بهتری بر اساس معیارهای سنجش کارایی الگوریتم‌های زمانبندی دارد. برای مثال در مقایسه با الگوریتم ژنتیک که در میان روش‌های موجود بهترین عملکرد را دارد، میانگین زمان انتظار و میانگین تعداد تعویض‌متن روش پیشنهادی به ترتیب 12 میلی‌ثانیه و 1.76 واحد بهبود و میانگین زمان برگشت حدود 2 میلی‌ثانیه افت داشته است.

Determining dynamic time quantum in round-robin scheduling algorithm using machine learning

One of the most common CPU scheduling algorithms in time-sharing systems is the round-robin algorithm. This algorithm considers a time quantum for each process, which represents the maximum amount of time that a process can have access to the processor. The processor is then allocated to ready processes in a rotating manner for the duration of the time quantum. The size of the quantum has a significant impact on the efficiency of the round-robin algorithm, such that if the quantum is too short, there will be an increase in context switches and associated overheads, which will decrease CPU utilization. Conversely, if the quantum is too large, it will increase the average response time of processes and make the use of the round-robin scheduling algorithm inefficient in interactive applications. The aim of this paper is to propose an effective method for determining the dynamic time quantum using machine learning. To this end, a training set consisting of features such as the number of processes and their maximum, minimum, average, and median burst times and the optimal time quantum as the class is constructed. Machine learning classifiers are then trained on this set to predict the optimal time quantum for new samples. The experimental results show that the proposed method outperforms other methods for determining optimal time quantum based on performance evaluation metrics of scheduling algorithms. For instance, in comparison with the genetic algorithm, which has the best performance among the available methods, the proposed method improves the average waiting time, the average number of context switches, and the average turnaround time by 12 milliseconds, 1.76 units, and about 2 milliseconds, respectively.