UPM Institutional Repository

Improving utility and recovery algorithms for adaptive real time system in multiprocessor environment


Ahmad, Idawaty (2012) Improving utility and recovery algorithms for adaptive real time system in multiprocessor environment. PhD thesis, Universiti Putra Malaysia.


Among the issues in adaptive real time system is the efficiency of the scheduling algorithm to satisfy the predefined deadline and utility requirements. The design of real time scheduler to achieve an efficient utility and fault recovery algorithm in multiprocessor environment is the main problem focused in this research. This thesis considers the independent tasks that are subject to deadline constraints specified in the TUF/UA scheduling environment. The algorithms for uniprocessor environment are known as Priority Inversion Utility Accrual Scheduling (PUAS) and Negation Oriented Utility Accrual Scheduling (NUAS). These algorithms solved the abortion problem in the existing General Utility Scheduling (GUS). PUAS implements a preemption strategy while NUAS negates the scheduling decision to abort by resuming the owner task. Simulation results reveal that the proposed algorithms outperforms the existing algorithm for the entire load range. The algorithm for multiprocessor environment is known as Global PUAS (GPUAS). GPUAS is adapted from the existing Greedy-Global Utility Accrual (G-GUA) and Non-Greedy Global Utility Accrual (NG-GUA) algorithms that considered task migration attribute for load sharing purposes. GPUAS enhanced the task placement mechanism in G-GUA and NGGUA algorithms. From the simulation results, GPUAS outperforms the existing G-GUA algorithm. The placement of task into a queue according to the value of utility in GPUAS has efficiently accrued at most 4.98% higher utility as compared to the existing G-GUA in dual core platform during overloaded condition in the system. GPUAS also tremendously outperforms NG-GUA in all platforms at most 12.44% higher utility accrued to the system. The scheduling algorithms with fault recovery are implemented in the uniprocessor and multiprocessor environment. The Backward Recovery (BR) mechanism is adapted from the Responsive Algorithm (RA) and works by re-executing of the erroneous request after its transient error period is over. The Backward Recovery PUAS (BRPUAS) and Backward Recovery NUAS (BRNUAS) algorithms are implemented for the uniprocessor scheduling environment. The Backward Recovery GPUAS (BR_GPUAS) algorithm is implemented in the multiprocessor environment. This thesis has proven that the BR mechanism is efficient to be used in the uniprocessor as BRPUAS saved at most 8.94% higher utility as compared to the abortion recovery. In multiprocessor environment, the BR_GPUAS saved at most 31.98% utility and thus enhanced the system performance in transient erroneous environment.

Download File

FSKTM 2012 29R.pdf

Download (828kB) | Preview

Additional Metadata

Item Type: Thesis (PhD)
Subject: Algorithms
Subject: Real-time data processing
Subject: Multiprocessors
Call Number: FSKTM 2012 29
Chairman Supervisor: Shamala Subramaniam, PhD
Divisions: Faculty of Computer Science and Information Technology
Depositing User: Haridan Mohd Jais
Date Deposited: 13 Jan 2015 01:53
Last Modified: 13 Jan 2015 01:53
URI: http://psasir.upm.edu.my/id/eprint/32774
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item