Recently, technological developments have affected most lifestyles, especially with the growth in Internet usage. Internet applications highlight the E-commerce capabilities and applications which are now available everywhere; they receive a great number of users on a 24-7 basis because online services are easy to use, faster and cheaper to acquire. Thus E-commerce web sites have become crucial for companies to increase their revenues. This importance has identified certain effective requirements needed from the performance of these applications. In particular, if the web server is overloaded, poor performance can result, due to either a huge rate of requests being generated which are beyond the server's capacity, or due to saturation of the communication links capacity which connects the web server to the network. Recent researches consider the overload issue and explore different mechanisms for managing the performance of E-commerce applications under overload condition. This thesis proposes a formal approach in order to investigate the effects of the extreme load and the number of dropped requests on the performance of E- III commerce web servers. The proposed approach is based on the class-based priority scheme that classifies E-commerce requests into different classes. Because no single technique can solve all aspects of overload problems, this research combines several techniques including: admission control mechanism, session-based admission control, service differentiation, request scheduling and queuing model-based approach. Request classification is based on the premise that some requests (e.g. buy) are generally considered more important than others (e.g. browse or search). Moreover, this research considers the extended models from Priority Scheduling Mechanism (PSM). These models add a new parameter, such as a review model or modify the basic PSM to low priority fair model, after the discovery of ineffectiveness with low priority customers or to add new features such as portal models. The proposed model is formally specified using the π-calculus in early stage of models design and a multi-actor simulation was developed to reflect the target models as accurately as possible and is implemented as a Java-based prototype system. A formal specification that captures the essential PSM features while keeping the performance model sufficiently simple is presented. Furthermore, the simplicity of the UML bridges the gap between π-calculus and Java programming language. IV There are many metrics for measuring the performance of E-commerce web servers. This research focuses on the performance of E-commerce web servers that refer to the throughput, utilisation, average response time, dropped requests and arrival rate. A number of experiments are conducted in order to test the performance management of the proposed approaches.

As terascale supercomputers become more common, and as the high-performance computing community turns its attention to petascale machines, the challenge of providing effective resource management for high-end machines grows in both importance and difficulty. These computing resources are by definition expensive, so the cost of underutilization is also high, e.g., wasting 5% of the compute nodes on a 10,000 node cluster is a much more serious problem than on a 100 node cluster. Moreover, the high energy and cooling costs incurred in maintaining these high end machines (often millions of dollars per year) can be justified only when these machines are used to their full capacity. On large clusters, conventional jobs schedulers are hard-pressed to achieve over 90% utilization with typical job-mixes. A fundamental problem is that most conventional parallel job schedulers only support static scheduling, so that the number of processors allocated to an application cannot be changed at runtime. As a result, it is common to see jobs stuck in the queue because they require just a few more processors than are currently available, resulting in long queue wait times for applications and low overall system utilization. A more flexible and effective approach is to support dynamic resource management and scheduling, where the number of processors allocated to jobs can be expanded or contracted at runtime. This is the focus of this dissertation --- dynamic resizing of parallel applications. Dynamic resizing significantly improves individual application turn-around time and helps the scheduler to achieve higher machine utilization and job throughput. This dissertation focuses on the potential benefits and challenges of dynamic resizing using ReSHAPE, a new framework for dynamic Resizing and Scheduling of Homogeneous Applications in a Parallel Environment. It also details several interesting and effective scheduling policies implemented in ReSHAPE and demonstrates their effectiveness to improve overall cluster utilization and individual application turn-around time. / Ph. D.

Recently, technological developments have affected most lifestyles, especially with the growth in Internet usage. Internet applications highlight the E-commerce capabilities and applications which are now available everywhere; they receive a great number of users on a 24-7 basis because online services are easy to use, faster and cheaper to acquire. Thus E-commerce web sites have become crucial for companies to increase their revenues. This importance has identified certain effective requirements needed from the performance of these applications. In particular, if the web server is overloaded, poor performance can result, due to either a huge rate of requests being generated which are beyond the server¿s capacity, or due to saturation of the communication links capacity which connects the web server to the network. Recent researches consider the overload issue and explore different mechanisms for managing the performance of E-commerce applications under overload condition. This thesis proposes a formal approach in order to investigate the effects of the extreme load and the number of dropped requests on the performance of E- III commerce web servers. The proposed approach is based on the class-based priority scheme that classifies E-commerce requests into different classes. Because no single technique can solve all aspects of overload problems, this research combines several techniques including: admission control mechanism, session-based admission control, service differentiation, request scheduling and queuing model-based approach. Request classification is based on the premise that some requests (e.g. buy) are generally considered more important than others (e.g. browse or search). Moreover, this research considers the extended models from Priority Scheduling Mechanism (PSM). These models add a new parameter, such as a review model or modify the basic PSM to low priority fair model, after the discovery of ineffectiveness with low priority customers or to add new features such as portal models. The proposed model is formally specified using the ¿ -calculus in early stage of models design and a multi-actor simulation was developed to reflect the target models as accurately as possible and is implemented as a Java-based prototype system. A formal specification that captures the essential PSM features while keeping the performance model sufficiently simple is presented. Furthermore, the simplicity of the UML bridges the gap between ¿-calculus and Java programming language. IV There are many metrics for measuring the performance of E-commerce web servers. This research focuses on the performance of E-commerce web servers that refer to the throughput, utilisation, average response time, dropped requests and arrival rate. A number of experiments are conducted in order to test the performance management of the proposed approaches.

With multiprocessors and multicore processors becoming ubiquitous, focus has shifted from research on uniprocessors to that on multiprocessors. Results derived for the uniprocessor case unfortunately do not always directly extend to the multiprocessor case in a straightforward manner. This necessitates a paradigm shift in the approach used to design and analyse the behaviour of such processors. In the case of Real-time systems, that is, systems characterised by explicit timing constraints, analysis and performance guarantees are more important, as failure is unacceptable. Scheduling algorithms used in Real-time systems have to be carefully designed as the performance of the system depends critically on them. Efficient tests for determining if a set of tasks can be feasibly scheduled on such a computing system using a particular scheduling algorithm thus assumes importance. Traditionally, the ‘task utilization’ parameter has been used for devising such tests. Utilization based tests for Earliest Deadline First(EDF) and Rate Monotonic(RM) scheduling algorithms are known and are well understood for uniprocessor systems. In our work, we derive limits on similar bounds for the multiprocessor case. Our work diners from previous literature in that we explore the case when the individual processors constituting the multiprocessor need not be identical. Each processor in such a system is characterised by a capacity, or speed, and the time taken by a task to execute on a processor is inversely proportional to its speed. Such instances may arise during system upgradation, when faster processors may be added to the system, making it a non-identical multiprocessor, or during processor design, when the different cores on the chip may have different processing power to handle dynamic workloads. We derive results for the partitioned paradigm of multiprocessor scheduling, that is, when tasks are partitioned among the processors, and interprocessor migration after a part of execution is completed is not allowed. Results are derived for both fixed priority algorithms(RM)and dynamic priority algorithms (EDF) used on individual processors. A maximum and minimum limit on the bounds for a ‘greedy’ class of algorithms are established, since the actual value of the bound depends on the algorithm that allocates the tasks. We also derive the utilization bound of an algorithm whose bound is close to the upper limit in both cases. We find that an expression for the utilization bound can be obtained when EDF is used as the uniprocessor scheduling algorithm, but when RM is the uniprocessor scheduling algorithm,an O(mn) algorithm is required to find the utilization bound, where m is the number of tasks in the system and n is the number of processors. Knowledge of such bounds allows us to carry out very fast schedulability tests, although we have the limitation that the tests are sufficient but not necessary to ensure schedulability. We also compare the value of the bounds with those achievable in ‘equivalent’ identical multiprocessor systems and find that the performance guarantees provided by the non-identical multiprocessor system are far higher than those offered by the equivalent identical system.

The requirements for real-time systems in safety-critical applications typically contain strict timing constraints. The design of such a system must be subject to extensive validation to guarantee that critical timing constraints will never be violated while the system operates. A mathematically rigorous technique to do so is to perform a schedulability analysis for formally verifying models of the computational workload. Different workload models allow to describe task activations at different levels of expressiveness, ranging from traditional periodic models to sophisticated graph-based ones. An inherent conflict arises between the expressiveness and analysis efficiency of task models. The more expressive a task model is, the more accurately it can describe a system design, reducing over-approximations and thus minimizing wasteful over-provisioning of system resources. However, more expressiveness implies higher computational complexity of corresponding analysis methods. Consequently, an ideal model provides the highest possible expressiveness for which efficient exact analysis methods exist. This thesis investigates the trade-off between expressiveness and analysis efficiency. A new digraph-based task model is introduced, which generalizes all previously proposed models that can be analyzed in pseudo-polynomial time without using any analysis-specific over-approximations. We develop methods allowing to efficiently analyze variants of the model despite their strictly increased expressiveness. A key contribution is the notion of path abstraction which enables efficient graph traversal algorithms. We demonstrate tractability borderlines for different classes of schedulers, namely static priority and earliest-deadline first schedulers, by establishing hardness results. These hardness proofs provide insights about the inherent complexity of developing efficient analysis methods and indicate fundamental difficulties of the considered schedulability problems. Finally, we develop a novel abstraction refinement scheme to cope with combinatorial explosion and apply it to schedulability and response-time analysis problems. All methods presented in this thesis are extensively evaluated, demonstrating practical applicability.

Real-time computing paradigm is being pervasively deployed in many critical and non-critical applicationssuch as aerospace and telecommunication systems. Most of these systems employ a preemptiveFixed Priority Scheduling (FPS) policy to schedule real-time tasks. Fixed priority scheduling is knownfor its implementation simplicity and low run-time overheads. However, FPS may not be able to use100% of the processor time, when compared to dynamic priority scheduling policies such as the EarliestDeadline First (EDF) scheduling scheme. Dynamic priority scheduling scheme, on the other hand, has tore-calculate the priorities on-line and hence may have significantly high run-time overheads. In this thesis, we investigate a novel scheduling scheme, known as the Dual Priority Scheduling scheme,that can potentially guarantee a feasible schedule. The main advantage of using a dual priority scheduleris that, it can achieve the implementation simplicity of a FPS scheme, while potentially assuring 100%processor utilization similar to EDF. Alan Burns proved the optimality of the dual priority scheme for twotasks, leaving its optimality for n tasks as an open problem. We investigate the optimality of dual priorityscheduling for three tasks, using simulations. We propose and evaluate three different approaches: lastchance method, slack method and brute force method, to calculate the dual priorities and the time intervalswhere these priorities are valid. Our evaluations showed that, of the proposed heuristics, the extended slack method which is a variationof the slack method, performed same as the brute force method. An interesting observation was that,the brute force and the extended slack methods could not schedule the same task sets, nor was the tasksets schedulable using any of the proposed methods.

No description available.

Different applications of communication networks have different requirements that depend on the type of application. We consider the problem of differentiating between delay-sensitive applications based on their average delay requirements, as may be of interest in signalling networks. We consider packets of different classes that are to be transmitted on the same link with different average delay requirements, to reside in separate queues with the arrival statistics for the queues being specified. This statistical multiplexer has to schedule packets from different queues in so that the average delays of the queues approach the specified target delays as quickly as possible. For simplicity, we initially consider a discrete-time model with two queues and a single work-conserving server, with independent Bernoulli packet arrivals and unit packet service times. With arrival rates specified, achieving mean queue lengths in a ratio which corresponds to the ratio of target mean delays is a means of achieving individual target mean delays. We formulate the problem in the framework of Markov decision theory. We study two scheduling policies called Queue Length Balancing and Delay Balancing respectively, and show through numerical computation that the expectation of magnitude of relative error in θ (1/m) and θ (1/√m) respectively, and that the expectation of the magnitude of relative error in weighted average delays decays as θ (1/√m) and θ (1/m) respectively, where m is the averaging interval length. We then consider the model for an arbitrary number of queues each with i.i.d. batch arrivals, and analyse the errors in the average delays of individual queues. We assume that the fifth moment of busy period is finite for this model. We show that the expectation of the absolute value of error in average queue length for at least one of the queues decays at least as slowly as θ (1/√m), and that the mean squared error in queue length for at least one of the queues decays at least as slowly as θ (1/m). We show that the expectation of the absolute value of error in approximating Little’s law for finite horizon is 0 (1/m). Hence, we show that the mean squared error in delay for at least one of the queues decays at least slowly as θ (1/m). We also show that if the variance of error in delay decays for each queue, then the expectation of the absolute value of error in delay for at least one of the queues decays at least as slowly as θ (1/√m).

Embedded systems are becoming ubiquitous in our daily life. Due to close interaction with physical world, embedded systems are typically subject to timing constraints. At design time, it must be ensured that the run-time behaviors of such systems satisfy the pre-specified timing constraints under any circumstance. In this thesis, we develop techniques to address the timing analysis problems brought by the increasing complexity of underlying hardware and software on different levels of abstraction in embedded systems design. On the program level, we develop quantitative analysis techniques to predict the cache hit/miss behaviors for tight WCET estimation, and study two commonly used replacement policies, MRU and FIFO, which cannot be analyzed adequately using the state-of-the-art qualitative cache analysis method. Our quantitative approach greatly improves the precision of WCET estimation and discloses interesting predictability properties of these replacement policies, which are concealed in the qualitative analysis framework. On the component level, we address the challenges raised by multi-core computing. Several fundamental problems in multiprocessor scheduling are investigated. In global scheduling, we propose an analysis method to rule out a great part of impossible system behaviors for better analysis precision, and establish conditions to guarantee the bounded responsiveness of computing tasks. In partitioned scheduling, we close a long standing open problem to generalize the famous Liu and Layland's utilization bound in uniprocessor real-time scheduling to multiprocessor systems. We also propose to use cache partitioning for multi-core systems to avoid contentions on shared caches, and solve the underlying schedulability analysis problem. On the system level, we present techniques to improve the Real-Time Calculus (RTC) analysis framework in both efficiency and precision. First, we have developed Finitary Real-Time Calculus to solve the scalability problem of the original RTC due to period explosion. The key idea is to only maintain and operate on a limited prefix of each curve that is relevant to the final results during the whole analysis procedure. We further improve the analysis precision of EDF components in RTC, by precisely bounding the response time of each computation request.