POT-AVL: A Novel CPU Scheduling Algorithm based on AVL Trees and Postorder Traversal

Abstract

Purpose – This study aims to offer a new perspective on the development and optimization of CPU scheduling algorithms in the field of research utilizing the concept of an Adelson-Velsky and Landis (AVL) tree which has not been used before in related studies which signifies a departure from standard practices, seeking to offer fresh insights into scheduling challenges.

Method – A novel scheduling algorithm called POT-AVL encompasses the structure of an AVL tree while using the postorder traversal to identify and select which processes shall be chosen and executed by the scheduler. The proposed algorithm was tested against the more common FCFS and two optimized RR algorithms, AMRR and MMRRA in terms of their Average Turnaround Time, Average Waiting Time, and Context Switch metrics.

Results –The results show that POT-AVL consistently performs better than the other algorithms in instances when the burst times for the processes are long burst times. POT- AVL performs worse than the FCFS algorithm when there are long gaps between arrival times.

Conclusion – The novel approach of integrating an AVL tree wait queue leads to an improved efficiency in terms of searching and managing processes in the queue which may be useful as a new path in the development and optimization of CPU scheduling algorithms.

Recommendations – The inclusion and other factors such as quantum time, and priority level, among others, can identify the strengths and weaknesses of the proposed algorithms in different scenarios.

Research Implications – This study exhibits more possibilities for amalgamating data structures and CPU scheduling algorithms.

Practical Implications – This study could suggest exploring alternative balancing techniques or adapting AVL trees to leverage hardware features efficiently.