From First-Come-First-Served to EEVDF: An Empirical Survey of CPU Scheduling Using Google Borg Cluster Traces

The choice of a scheduling algorithm is one of the most important decisions for system designers. A scheduling algorithm dictates the overall latency, throughput, and fairness of the running process of that system. The goal of this study is to show how a practical implementation of CPU scheduling algorithm in the Linux kernel relates to the basic scheduling algorithms. This study reviews eight different scheduling algorithms (FCFS, SJF, RR, Priority, MLQ, MLFQ, EDF, CFS) and then discusses the implementation of EEVDF (the successor to CFS). This work utilizes the Google 2019 Borg cluster traces dataset to examine various scheduling algorithms. The experimental results are measured with various metrics such as throughput, turnaround time, waiting time, response time, fairness and context switches by applying 500 and 2000-job samples. This empirical study concludes that no algorithm dominates on all six metrics, SJF yields the lowest average waiting and turnaround time, MLFQ yields the lowest average response time, and CFS yields the highest fairness index. The effect of time quantum is analyzed using different time quantum ranging from 1 to 500 units. The results suggest using variable time quantum is better than using a fixed one. Furthermore, it also discusses a multi-core affinity study across 2 to 16 cores that demonstrates soft affinity having roughly 95% cache-hit rate, against only 6.2% for random placement. The experimental results demonstrate that no single CPU scheduling algorithm is optimal across all performance metrics. Instead, the appropriate scheduler depends on the workload characteristics and system objectives, while modern Linux schedulers such as EEVDF improve responsiveness by combining classical scheduling principles with fairness-aware design.