MODELS FOR HANDLING MULTI-DIMENSIONAL PROCESSES IN CENTRAL PROCESSING UNIT USING TASK-BASED PRIORITY QUEUES DATA STRUCTURES
A.H. Eneh*, A. J. Jimoh & U. C. Arinze
Department of Computer Science
Faculty of Physical Sciences
University of Nigeria, Nsukka-South East, Nigeria
Email: agozieh.eneh@unn.edu.ng, jimoh.johnson@unn.edu.ng
*Corresponding author
ABSTRACT
This paper reviews different process scheduling criteria; algorithms; properties; objectives and underlying dynamic data structures that optimize process scheduling such as concurrent priority queues (PQs). PQs are known for handling multi-dimensional processes in central processing units (CPUs) by using tasked-based PQs such as – SkipQueue, a highly distributed PQ-based on a simple modification of Pugh’s concurrent SkipList algorithm. SkipLists – search structures based on hierarchically ordered linked-lists. PQs are fundamental in the design of modern multiprocessor algorithms, with many applications ranging from numerical algorithms through discrete event simulation and expert systems design and implementation. For such algorithms to be used in the CPU they must possess certain inherent properties such as: fairness; predictability; throughput maximization and enforcement of priorities respectively. Scheduling priority criteria such as – CPU utilization, throughput; turnaround; waiting and response times are also critical for such systems. Several attempts have been made to address the design of concurrent priority queue algorithms for multi-dimensional processes and small scale machines. Nevertheless, the problem of obtaining optimality in performance is yet to be resolved. This work attempts to address the problem. Results and findings from our algorithm simulation on MATLAB environment indicate that to search a list of N items, O (logN) level lists are traversed, and a constant number of items is traversed per level, making the expected overall complexity of an Insert or Delete operation on a PQ O(logN). This indicates an improvement in performance threshold, as other algorithms exhibited O (N) complexity for similar search times.
Keywords: multiprocessors, concurrent data structures, priority queues.
