A Clustering Based CPU Scheduling Algorithm for Real Time Systems

Abstract

CPU scheduling is a fundamental function of operating system. The performance and efficiency of multitasking operating systems mainly depend upon the uses of CPU scheduling algorithm. When an operating system wants to execute a process, it does not know the execution time it needs. After running, the exact execution time of that process would appear. Here we present a new scheduling approach using the Partitioning Around Medoid (PAM) clustering algorithm in conjunction with Shortest Job First (SJF). This proposed approach is able to estimate the execution time (next CPU-burst time) of a process. The processes in each cluster are processed in the ready queue, for the time period of one time quantum, equal to medoid of respective cluster. The remaining processes, which are not completely processed in first cycle, are clustered again with remaining burst time and time quantum equal to medoid is assigned to the processes in respective clusters. This process continues until there is no process in the ready queue.

Keywords:  Scheduling, Clustering, Partitioning Around Medoid (PAM), Shortest Job First(SJF)