Fair Priority Scheduling (FPS): A Process Scheduling Algorithm Based on Skip Ring Data Structure

Aksu M., KARCI A.

ARABIAN JOURNAL FOR SCIENCE AND ENGINEERING, cilt.42, ss.677-689, 2017 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 42 Konu: 2
  • Basım Tarihi: 2017
  • Doi Numarası: 10.1007/s13369-016-2288-y
  • Sayfa Sayıları: ss.677-689


Our process scheduling algorithm was created with the help of circular linked list and skip ring data structures and algorithms. Skip ring data structure consists of circular link lists formed in layers which are linked in a canonical way. Time complexity of search, insertion and deletion equals to O (lgN) in an N-element skip ring data structure. Therefore, skip ring data structure is employed more effectively (O(lgN)) in circumstances where circular linked lists (O(N)) are used. In this paper, the applications of data structures such as red-black tree, binary search tree and skip ring were performed and the obtained results were compared. The obtained results demonstrated that skip ring data structure is superior to red-black tree and binary search tree. Process scheduling is the most important part of operating systems. Linux operating system (version 6.23) uses Completely Fair Scheduler for process scheduling by using red-black tree data structures, Whereas skip ring data structure can be used effectively instead of red-black tree data structure. A new algorithm for process scheduling which was called as Fair Priority Scheduling was proposed in this paper.