Fair Priority Scheduling (FPS): A Process Scheduling Algorithm Based on Skip Ring Data Structure
Küçük Resim Yok
Tarih
2017
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
Springer Heidelberg
Erişim Hakkı
info:eu-repo/semantics/closedAccess
Özet
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.
Açıklama
Anahtar Kelimeler
Data structures, Skip ring, Design of algorithms, Process scheduling, Operating systems, FPS
Kaynak
Arabian Journal For Science and Engineering
WoS Q Değeri
Q3
Scopus Q Değeri
Q1
Cilt
42
Sayı
2
