Thesis (Ph. D.)--University of Hong Kong, 1999. / Includes bibliographical references.

D.Phil. (Electrical and Electronic Engineering) / This thesis explores methods for improving, or optimizing, Operating System (OS) scheduling. We first study the problem of tuning an OS scheduler by setting various parameters, or knobs, made available. This problem has not been addressed extensively in the literature, and has never been solved for the default Linux OS scheduler. We present three methods useful for tuning an Operating System scheduler in order to improve the quality of scheduling leading to better performance for workloads. The first method is based on Response Surface Methodology, the second on the Particle Swarm Optimization (PSO), while the third is based on the Golden Section method. We test our proposed methods using experiments and suitable benchmarks and validate their viability. Results indicate significant gains in execution time for workloads tuned with these methods over execution time for workloads running under schedulers with default, unoptimized tuning parameters. The gains for using RSM-based over default scheduling parameter settings are only limited by the type of workload (how much time it needs to execute); gains of up to 16:48% were obtained, but even more are possible, as described in the thesis. When comparing PSO with Golden Section, PSO produced better scheduling parameter settings, but it took longer to do so, while Golden Section produced slightly worse parameter settings, but much faster. We also study a problem very critical to scheduling on modern Central Processing Units (CPUs). Modern CPUs have multicore designs, which corresponds to having more than one CPU on a single chip. These are known as Chip Multiprocessors (CMPs). The CMP is now the standard type of CPU for many different types of computers, including Personal Computers.

International Telemetering Conference Proceedings / October 26-29, 1998 / Town & Country Resort Hotel and Convention Center, San Diego, California / The recent proliferation of Low Earth Orbiting (LEO) science, earth resources, and global communication satellites requires a significant number of ground stations for support. A network of satellite tracking ground stations with the ability to support multiple users and communicate with multiple satellites requires a robust scheduling and conflict resolution system. This paper describes an automated scheduling implementation for managing such a commercial, multi-user, multiple satellite, ground station network.

No description available.

This dissertation addresses the problem of scheduling a set of jobs under two different measures of performance: total tardiness and weighted number of tardy jobs. A new solution approach is presented for the single-machine tardiness problem. This views the problem as one of determining an optimal partition of the job set into early and tardy subsets. The scheme is validated by the development of necessary conditions for optimality. It is shown that if an optimal partition of the jobs into early and tardy subsets is given, the conditions are not only necessary but also sufficient. These results are used to derive a polynomial algorithm to generate a sequence that satisfies these conditions for any arbitrary partition. The implications of these results with respect to solving the tardiness problem, as well as some other related problems, are examined. Particular emphasis is placed on the impact of the partition approach as a device to enhance the performance of existing branch-and-bound procedures. The use of this approach to generate valid inequalities is also discussed. The problem of scheduling a single machine to minimize the weighted number of tardy jobs is examined in detail. A new branch-and-bound procedure is presented as well as the first extensive computational study of the problem. The proposed algorithm relies on lower bounds obtained by means of two relaxations of the problem for which efficient solution procedures exist. The merits of both bounding schemes are extensively tested. The computational results indicate that exact solutions for large problems can be obtained in just a few seconds of computer time. The efficacy of the approach as a heuristic method is also verified. Further, the computational experience provides insight into how various problem parameters affect the solution difficulty of particular problem instances. The multiple-processor version of the weighted number of tardy jobs model is also considered. The basic algorithmic framework for the single-machine problem is extended to obtain optimal preemptive schedules for parallel machines, which may be identical, uniform, or unrelated.

published_or_final_version / abstract / Computer Science / Master / Master of Philosophy

High Speed Downlink Packet Access (HSDPA) is the extension to the Universal Mobile Telecommunication System (UMTS). HSDPA allows for higher data rates due to new adaptive Modulation and Coding (AMC) techniques, Hybrid Automatic Repeat reQuest (H-ARQ) and fast scheduling algorithm. One of the key features of HSDPA technology is to handle UMTS traffic classes with different Quality of Service (QoS) requirements. In order to provide QoS several scheduling algorithms, QoS control constraints, and different other schemes have been proposed in literature. In the thesis, a simple matlab based model for HSDPA is presented in order to simulate various algorithms. The QoS controls in terms of guaranteed bit rate (GBR) have been implemented by means of barrier functions which perform barrier around the feasible region. The results illustrate the trade-off between the cell throughput and the minimum guaranteed bit rate. Traffic classes are prioritized by means of QoS parameters. The priority is given to RT traffic streams over interactive services. Real-Time (RT) algorithms have been simulated to prioritize traffic classes based on delays. / QoS is the ability to provide resources and prioritize different applications. As mentioned before, the 3GPP standard defines four categories of service (Conversation, streaming, interactive and background) for UMTS. Strategies in traffic management, priority GBR allowances and bandwidth are important strategies for traffic differentiation and quality of service (QoS). Providing QoS over HSDPA is one of the challenging tasks for researchers. The significant results and findings of our thesis are as follows • In this thesis various algorithms were implemented with their duties barrier to provide guarantees of quality, in terms of speed guaranteed (GBR). The emphasis was to ensure the flow and priority categories of traffic. First the performance of algorithms were studied alone and then along with the barrier functions. It is concluded that barrier functions play an important role by means of providing QoS guarantee in HSDPA, considering channel conditions. Traffic classes were prioritized on QoS parameters defined for barrier functions. It was found that minimum bit rates were maintained by barrier functions but the cell throughput decreases with their barrier functions depending upon QoS parameters. The streaming aware scheduler has been evaluated by means of simulations in mixed scenarios and it is concluded that this algorithm protects streaming QoS in high overload conditions. It is therefore concluded that barrier functions and streaming aware schedulers are the best option for QoS control. These schedulers are very simple and consider diversity gains as well.

No description available.

No description available.

No description available.