| Scheduling in computing systems is an important problem due to its pervasive use in computer assisted applications. Among the scheduling algorithms proposed in the literature, round robin (RR) in general purpose computing and rate monotonic (RM) in real-time and embedded systems, are widely used and extensively analyzed. However, these two algorithms have some performance limitations. The main objective of this thesis is to address these limitations by proposing suitable modifications. These modifications yield many efficient versions of RR and RM. The appeal of our improved algorithms is that they alleviate the observed limitations significantly while retaining the simplicity of the original algorithms.;In general purpose computing context, we present a generic framework called fair-share round robin (FSRR) from which many scheduling algorithms with different fairness characteristics can be derived. In real-time context, we present two generic frameworks, called off-line activation-adjusted scheduling (OAA) and adaptive activation-adjusted scheduling (AAA), from which many static priority scheduling algorithms can be derived. These algorithms reduce unnecessary preemptions and hence increase: (i) processor utilization in real-time systems; and (ii) task schedulability. Subsequently, we adopt and tune AAA framework in order to reduce energy consumption in embedded systems. We also conducted a simulation study for selected set of algorithms derived from the frameworks and the results indicate that these algorithms exhibits improved performance. |
