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

详细信息    查看全文

• 作者：Mustafa Aksu ; Ali Karcı
• 关键词：Data structures ; Skip ring ; Design of algorithms ; Process scheduling ; Operating systems ; FPS
• 刊名：Arabian Journal for Science and Engineering
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：42
• 期：2
• 页码：677-689
• 全文大小：
• 刊物类别：Engineering
• 刊物主题：Engineering, general; Science, Humanities and Social Sciences, multidisciplinary;
• 出版者：Springer Berlin Heidelberg
• ISSN：2191-4281
• 卷排序：42

文摘

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.