Scheduling forms an important aspect of operating systems because it has a direct impact on system performance. Most existing general-purpose schedulers use a priority-based scheme to schedule processes. Such priority-based mechanisms cannot guarantee proportional fairness for every process. Proportional share schedulers maintain fairness among tasks based on given weight values. In both of these scheduler types, the scheduling decision is done per-process. However, system usage policies are typically set on a per-consumer basis, where a consumer represents a group of related processes that may belong to the same application or user. The COPS framework uses the idea of consumer sets to group processes. Its design guarantees system usage per consumer, based on relative weights. We have added a share management layer on top of a proportional share scheduler to ease the administrative job of share assignment for these consumer sets. We have evaluated our system in real world scenarios and show that the CPU usage for consumer sets with CPU-bound processes complies with the administrator-defined policy goals. / Master of Science

In this thesis, we present a MAC-layer packet scheduling algorithm, called Best-effort Packet Scheduling Algorithm(BPA), for real-time switched Ethernet networks. BPA considers a message model where application messages have trans-node timeliness requirements that are specified using Jensen's benefit functions. The algorithm seeks to maximize aggregate message benefit by allowing message packets to inherit benefit functions of their parent messages and scheduling packets to maximize aggregate packet-level benefit. Since the packet scheduling problem is NP-hard, BPA heuristically computes schedules with a worst-case cost of O(n^2), faster than the O(n^3) cost of the best known Chen and Muhlethaler's Algorithm(CMA) for the same problem. Our simulation studies show that BPA performs the same or significantly better than CMA. We also construct a real-time switched Ethernet by prototyping an Ethernet switch using a Personal Computer(PC) and implementing BPA in the network protocol stack of the Linux kernel for packet scheduling. Our actual performance measurements of BPA using the network implementation reveal the effectiveness of the algorithm. Finally, we derive timeliness feasibility conditions of real-time switched Ethernet systems that use the BPA algorithm. The feasibility conditions allow real-time distributed systems to be constructed using BPA, with guaranteed soft timeliness. / Master of Science

No description available.

No description available.

No description available.

An analysis tableau suitable for investigating flow-shop attributes is presented in detail 1. Geometric properties, inherent within the tableau, are employed using graph theory concepts in developing a heuristic algorithm for makespan minimization. Computer implementation of this algorithm revealed promising results when compared with several state of-the-art heuristic algorithms. The tableau can be conceived as a three-dimensional matrix with the first two indices consisting of job numbers (rows) and machine numbers (columns). The third index is used to distinguish processing times and accumulative makespan values. The matrix is as informative as the Gantt Chart and yet offers additional advantages when considering the flow-shop problem, such as: 1. Provides an instructional tableau format which is organized, systematic, and directly amenable for hand or digital-computer calculations, 2. Depicts computational contingencies for accumulative makespan values (individual job due-dates as well as flow-shop makespan), 3. Depicts machine and job dominances, 4. Allows for sensitivity analysis {effects of processing times upon accumulative makespan values), 5. Identifies critical-processing times, 6. Reveals where external improvements would be cost effective, 7. Representation is easily modified for job permutations, 8. Representation is not limited to small flow-shops (low number of jobs and/or machines), 9. Allows for additional insight when investigating heuristics, and 10. Can be used as an instructional- , managerial- , and/or a research- tool for analyzing flow-shop attributes. The tableau allows a macro-sensitivity analysis of the entire flow-shop. Specifically, the maximum increase in various processing times, without increasing the flow-shop make span, can be determined. This analysis utilizes graphical representations (segments and nodes) in matrix (tableau). Graphical representation is a convenient means for preserving the history of how each accumulative makespan value was mathematically generated. Concepts such as: partial-paths and critical-paths in conjunction with regions-of-influence are discussed in order to determine the interrelationship between the accumulative makespan values and the processing times, for a specific job sequence. / M. S.

Scheduling large real world problems is a complex process and finding high quality solutions is not a trivial task. In cooperation with Trimble MRM Ltd., who provide scheduling solutions for many large companies, a problem is identified and modelled. It is a general model which encapsulates several important scheduling, routing and resource allocation problems in literature. Many of the state-of-the-art heuristics for solve scheduling problems and indeed other problems require specialised heuristics tailored for the problem they are to solve. While these provide good solutions a lot of expert time is needed to study the problem, and implement solutions. This research investigates methods to enhance existing search based methods. We study hyperheuristic techniques as a general search based heuristic. Hyperheuristics raise the generality of the solution method by using a set of tools (low level heuristics) to work on the solution. These tools are problem specific and usually make small changes to the problem. It is the task of the hyperheuristic to determine which tool to use and when. Low level heuristics using exact/heuristic hybrid method are used in this thesis along with a new Tabu based hyperheuristic which decreases the amount of CPU time required to produce good quality solutions. We also develop and investigate the Variable Fitness Function approach, which provides a new way of enhancing most search-based heuristics in terms of solution quality. If a fitness function is pushing hard in a certain direction, a heuristic may ultimately fail because it cannot escape local minima. The Variable Fitness Function allows the fitness function to change over the search and use objective measures not used in the fitness calculation. The Variable Fitness Function and its ability to generalise are extensively tested in this thesis. The two aims of the thesis are achieved and the methods are analysed in depth. General conclusions and areas of future work are also identified.

This study attempted to determine if the type of class schedule (traditional, A/B block, or accelerated block) used in Texas public high schools significantly affects students' achievement results, attendance rates and dropout rates. One thousand four hundred ninety (1490) Texas high school principals were surveyed to determine the type of schedule currently in use on each campus, the type of schedule previously used on each campus, the length of time the current schedule has been in place on each campus, and the length of time that the previous schedule was used on each campus. This study is particularly significant in that this research provides information to assist principals in determining if block scheduling is instrumental in improving achievement in reading and mathematics, in improving attendance and in lowering dropout rates. The results of the study indicated that the use of a particular type of schedule: traditional, A/B block, or accelerated block is not directly correlated to improved achievement, attendance, or dropout rates. An expectation that the implementation of a traditional, A/B block, or accelerated block schedule will be the sole factor to cause improved student achievement, improved attendance rates or improved dropout rates is inappropriate. Ultimately, campus and districts officials must assure that effective teaching practices are occurring on each campus, regardless of the schedule type. Currently, a projected (Texas) state education funding shortfall is causing school district administrators to review cost-saving options for the 2003 - 2004 fiscal year. There is discussion in many districts regarding the fact that traditional scheduling is more economical than A/B block or accelerated block scheduling. The results of this study indicate that the decision to move campuses from A/B block or accelerated block to traditional scheduling might be made as a cost-saving move without negatively impacting student achievement, attendance rates or dropout rates.

Heterogeneity in modern datacenters is on the rise, in hardware resource characteristics, in workload characteristics, and in dynamic characteristics (e.g., a memoryresident copy of input data). As a result, which machines are assigned to a given job can have a significant impact. For example, a job may run faster on the same machine as its input data or with a given hardware accelerator, while still being runnable on other machines, albeit less efficiently. Heterogeneity takes on more complex forms as sets of resources differ in the level of performance they deliver, even if they consist of identical individual units, such as with rack-level locality. We refer to this as combinatorial heterogeneity. Mixes of jobs with strict SLOs on completion time and increasingly available runtime estimates in production datacenters deepen the challenge of matching the right resources to the right workloads at the right time. In this dissertation, we hypothesize that it is possible and beneficial to simultaneously leverage all of this information in the form of declaratively specified spacetime soft constraints. To accomplish this, we first design and develop our principal building block—a novel Space-Time Request Language (STRL). It enables the expression of jobs’ preferences and flexibility in a general, extensible way by using a declarative, composable, intuitive algebraic expression structure. Second, building on the generality of STRL, we propose an equally general STRL Compiler that automatically compiles STRL expressions into Mixed Integer Linear Programming (MILP) problems that can be aggregated and solved to maximize the overall value of shared cluster resources. These theoretical contributions form the foundation for the system we architect, called TetriSched, that instantiates our conceptual contributions: (a) declarative soft constraints, (b) space-time soft constraints, (c) combinatorial constraints, (d) orderless global scheduling, and (e) in situ preemption. We also propose a set of mechanisms that extend the scope and the practicality of TetriSched’s deployment by analyzing and improving on its scalability, enabling and studying the efficacy of preemption, and featuring a set of runtime mis-estimation handling mechanisms to address runtime prediction inaccuracy. In collaboration with Microsoft, we adapt some of these ideas as we design and implement a heterogeneity-aware resource reservation system called Aramid with support for ordinal placement preferences targeting deployment in production clusters at Microsoft scale. A combination of simulation and real cluster experiments with synthetic and production-derived workloads, a range of workload intensities, degrees of burstiness, preference strengths, and input inaccuracies support our hypothesis that leveraging space-time soft constraints (a) significantly improves scheduling quality and (b) is possible to achieve in a practical deployment.

The purpose of this study was to observe the differences in English achievement, critical-thinking ability, and attitude toward subject attributable to two scheduling approaches -- "Concurrent" and "Intensive"--in the teaching of first-semester freshman English composition to community college students. Further, the study was initiated in order to provide factual information as a basis for administrative and instructional judgments affecting future planning for accelerated scheduling at the experimental institution. Two classes of first-semester freshman English composition, meeting three hours weekly for fifteen weeks, comprised the control group (Concurrent); two classes of first-semester freshman English composition, meeting nine hours weekly for five weeks, comprised the experimental group (Intensive). The same form of three criterion instruments was administered to both groups before and after the experimental treatment. The instruments were the Cooperative English Expression Test, the Watson-Glaser Critical Thinking Appraisal, and the Purdue Attitude Scale, Part A -- Attitude Toward Any Subject. Three instructors were involved in the experiment during the fall and spring semesters of the 1973-74 school year. Conventional methods of instruction, using the same course of study, were duplicated in all situations. Statistical analyses utilized in the study were analysis of covariance and multiple linear regression. It was felt that Intensive scheduling was superior to Concurrent as a means of promoting student-faculty harmony. Also, the frustrations experienced within the traditional classroom situation could be lessened by granting greater freedom from the constraints of hourly schedules and competing classes. With tensions reduced, English proficiency could be increased. Acting upon these suppositions, three hypotheses--related to each of the criterion measures-- were formulated. All hypotheses stated that the adjusted post-test scores for the experimental groups would be significantly greater than the adjusted post-test scores for the control groups. The results of the experiment, however, showed no significant difference for any of the hypotheses at the . 05 level of confidence; thus, all were rejected. Within the limitations of this study, it was evident that any difference in the effectiveness of the two scheduling approaches for first-semester freshman composition was negligible. But of significance was the observation that a quality instructional program could be effectively adapted to scheduling variations. In general, the successful implementation of any such variation was dependent upon careful course planning and widespread publicity. Furthermore, attitudes toward a subject did not seem to be materially altered as a result of differences in scheduling format. Pertinent to the improvement of the English discipline, the study revealed a strong correlation between critical-thinking ability and skill in English expression. It appeared, however, that class attendance was more important in the improvement of English skill--especially in accelerated classes--than it was in the improvement of critical-thinking ability. In conclusion, the possibilities of an expanded academic program should be fully investigated as a scheduling option for the community college. In this connection, continuing research should examine the effects of various combinations of grouping plans upon learning. Related goals and objectives should be formulated and program particulars transmitted to students. Available data, defining the type of student most likely to benefit from scheduling options, should be utilized in an effort to create a more favorable total situation.