No description available.

No description available.

No description available.

This dissertation presents a class of utility accrual scheduling and synchronization algorithms for dynamic, single and multiprocessor real-time systems. Dynamic real-time systems operate in environments with run-time uncertainties including those on activity execution times and arrival behaviors. We consider the time/utility function (or TUF) timing model for specifying application time constraints, and the utility accrual (or UA) timeliness optimality criteria of satisfying lower bounds on accrued activity utility, and maximizing the total accrued utility. Efficient TUF/UA scheduling algorithms exist for single processors---e.g., the Resource-constrained Utility Accrual scheduling algorithm (RUA), and the Dependent Activity Scheduling Algorithm (DASA). However, they all use lock-based synchronization. To overcome shortcomings of lock-based (e.g., serialized object access, increased run-time overhead, deadlocks), we consider non-blocking synchronization including wait-free and lock-free synchronization. We present a buffer-optimal, scheduler-independent wait-free synchronization protocol (the first such), and develop wait-free versions of RUA and DASA. We also develop their lock-free versions, and upper bound their retries under the unimodal arbitrary arrival model. The tradeoff between wait-free, lock-free, and lock-based is fundamentally about their space and time costs. Wait-free sacrifices space efficiency in return for no additional time cost, as opposed to the blocking time of lock-based and the retry time of lock-free. We show that wait-free RUA/DASA outperform lock-based RUA/DASA when the object access times of both approaches are the same, e.g., when the shared data size is so large that the data copying process dominates the object access time of two approaches. We derive lower bounds on the maximum accrued utility that is possible with wait-free over lock-based. Further, we show that when maximum sojourn times under lock-free RUA/DASA is shorter than under lock-based, it is a necessary condition that the object access time of lock-free is shorter than that of lock-based. We also establish the maximum increase in activity utility that is possible under lock-free and lock-based. Multiprocessor TUF/UA scheduling has not been studied in the past. For step TUFs, periodic arrivals, and under-loads, we first present a non-quantum-based, optimal scheduling algorithm called Largest Local Remaining Execution time-tasks First (or LLREF) that yields the optimum total utility. We then develop another algorithm for non-step TUFs, arbitrary arrivals, and overloads, called the global Multiprocessor Utility Accrual scheduling algorithm (or gMUA). We show that gMUA lower bounds each activity's accrued utility, as well as the system-wide, total accrued utility. We consider lock-based, lock-free, and wait-free synchronization under LLREF and gMUA. We derive LLREF's and gMUA's minimum-required space cost for wait-free synchronization using our space-optimal wait-free algorithm, which also applies for multiprocessors. We also develop lock-free versions of LLREF and gMUA with bounded retries. While the tradeoff between wait-free LLREF/gMUA versus lock-based LLREF/gMUA is similar to that for the single processor case, that between lock-free LLREF/gMUA and lock-based LLREF/gMUA hinges on the cost of the lock-free retry, blocking time under lock-based, and the operating system overhead. / Ph. D.

We review MIT research in manufacturing systems engineering, and we describe current and possible future research activities in this area. This includes advances in decomposition techniques, optimization, token-based control systems analysis, multiple part types, inspection location, data collection and several other topics. / Singapore-MIT Alliance (SMA)

The majority of computers around us are embedded in productsand dedicated to perform certain tasks. A specific task is thecontrol of a dynamic system. The computers are ofteninterconnected by communication networks forming a distributedsystem. Vehicles and manufacturing equipment are two types ofmechatronic machines which often host dedicated computercontrol systems. A research problem is how the real-timebehaviour of the computer system affects the application,especially the control of the dynamic system. If the internal or external conditions varies over time, itbecomes difficult to assign a fixed resource reservation thatwill work well in all situations. In general, the more time anapplication gets of a resource, the better its gauged orperceived quality will be. A strategy is to alter the resourcereservation when the condition changes. This can be constructedas a negotiation between competing applications, a method forwhich the termquality of control, QoC, has been coined. Scalability isthe ability to change the structure and configuration of asystem. It promotes evolving systems and a can help manage acomplex product family. An architecture for a QoC middleware ontop of a scalable computer system, has been proposed. As aquality measureof a control application, the well-knownweighted quadratic loss function used in optimal control, hasbeen revised to encompass a subset of the so called timingproperties. The timing properties are the periods and thedelays in the control loop, including time-varying period anddelay. They are the interface between control and computerengineering, from a control engineering viewpoint. The qualitymeasure can be used both offline and on-line given a model ofthe sampled-data system and an appropriate description of thetiming properties. In order to use a computer system efficiently and toguarantee its responsiveness, real-time scheduling is a must.In fixed priority scheduling each task arrives periodically andhas a fixed priority. A task with a high priority can preempt alow priority task and gain access to the resource. Thebest-case response time characterizes the delays in the system,which is useful from a control viewpoint. A new algorithm tocalculate thebest-caseresponsetime has been derived. It is based on ascheduling scenario which yields a recurrence equation. Themodel is dual to the well-known worst-case response timeanalysis. Besides the dynamic fixed priority scheduling algorithm,optimal control usingstatic schedulinghas been studied, assuming a limitedcommunication. In the static schedule, which is constructedpre-runtime, each task is assigned a time window within aschedule repeated in eternity. The optimal scheduling sequenceis sought by optimizing the overall control performance. Aninteresting aspect is that the non-specified control periodfalls out as a result of theoptimal schedule. The time-varying delay is accountedfor in the control design. Keywords:Real-time scheduling, sampled-data control,performance measure, quality of control, limited communication,time-varying delay, jitter.

<p>The majority of computers around us are embedded in productsand dedicated to perform certain tasks. A specific task is thecontrol of a dynamic system. The computers are ofteninterconnected by communication networks forming a distributedsystem. Vehicles and manufacturing equipment are two types ofmechatronic machines which often host dedicated computercontrol systems. A research problem is how the real-timebehaviour of the computer system affects the application,especially the control of the dynamic system.</p><p>If the internal or external conditions varies over time, itbecomes difficult to assign a fixed resource reservation thatwill work well in all situations. In general, the more time anapplication gets of a resource, the better its gauged orperceived quality will be. A strategy is to alter the resourcereservation when the condition changes. This can be constructedas a negotiation between competing applications, a method forwhich the term<i>quality of control</i>, QoC, has been coined. Scalability isthe ability to change the structure and configuration of asystem. It promotes evolving systems and a can help manage acomplex product family. An architecture for a QoC middleware ontop of a scalable computer system, has been proposed.</p><p>As a<i>quality measure</i>of a control application, the well-knownweighted quadratic loss function used in optimal control, hasbeen revised to encompass a subset of the so called timingproperties. The timing properties are the periods and thedelays in the control loop, including time-varying period anddelay. They are the interface between control and computerengineering, from a control engineering viewpoint. The qualitymeasure can be used both offline and on-line given a model ofthe sampled-data system and an appropriate description of thetiming properties.</p><p>In order to use a computer system efficiently and toguarantee its responsiveness, real-time scheduling is a must.In fixed priority scheduling each task arrives periodically andhas a fixed priority. A task with a high priority can preempt alow priority task and gain access to the resource. Thebest-case response time characterizes the delays in the system,which is useful from a control viewpoint. A new algorithm tocalculate the<i>best-caseresponse</i>time has been derived. It is based on ascheduling scenario which yields a recurrence equation. Themodel is dual to the well-known worst-case response timeanalysis.</p><p>Besides the dynamic fixed priority scheduling algorithm,optimal control using<i>static scheduling</i>has been studied, assuming a limitedcommunication. In the static schedule, which is constructedpre-runtime, each task is assigned a time window within aschedule repeated in eternity. The optimal scheduling sequenceis sought by optimizing the overall control performance. Aninteresting aspect is that the non-specified control periodfalls out as a result of the<i>optimal schedule</i>. The time-varying delay is accountedfor in the control design.</p><p><b>Keywords:</b>Real-time scheduling, sampled-data control,performance measure, quality of control, limited communication,time-varying delay, jitter.</p>

Cyber-physical systems (CPS) are systems that are composed of physical and computational components. CPS components are typically interconnected through a communication network that allows components to interact and take automated actions that are beneficial for the overall CPS. Future Power-Grid is one of the major example of Cyber-physical systems. Traditionally, Power-Grids use a centralized approach to manage the energy produced at power sources or large power plants. Due to the advancement and availability of renewable energy sources such as wind farms and solar systems, there are more number of energy sources connecting to the power grid. Managing these large number of energy sources using a centralized technique is not practical and is computationally very expensive. Therefore, a decentralized way of monitoring and scheduling of energy across the power grid is preferred. In a decentralized approach, computational load is distributed among the grid entities that are interconnected through a readily available communication network like internet. The communication network allows the grid entities to coordinate and exchange their power state information with each other and take automated actions that lead to efficient consumption of energy as well as the network bandwidth. Thus, the future power grid is appropriately called a "Smart-Grid". While Smart-Grids provide efficient energy operations, they also impose several challenges in the design, verification and monitoring phases. The computer network serves as a backbone for scheduling messages between the Smart-Grid entities. Therefore, network delays experienced by messages play a vital role in grid stability and overall system performance. In this work, we study the effects of network delays on Smart-Grid performance and propose adaptive algorithms to efficiently schedule messages between the grid entities. Algorithms proposed in this work also ensure the grid stability and perform network congestion control. Through this work, we derive useful conclusions regarding the Smart-Grid performance and find new challenges that can serve as future research directions in this domain.

In real-word manufacturing environments, finding the right job sequences and their associated schedules when resource, precedence, and timing constraints are imposed is a difficult task. For most practical problems classical scheduling easily leads to an exponential growth in the number of possible schedules. Moreover, a decision time period of hours or even minutes is too long. Good solutions are often needed in real-time. The problem becomes even more complicated if changes, such as new orders or resource breakdowns, occur within the manufacturing system. One approach to overcome the challenges of solving classical scheduling problems is the use of distributed schemes such as agent or holonic-based control architectures. This dissertation presents an innovative control architecture that uses the holonic concept, capable of delivering good solutions when applied in dynamic environments. The general holonic control framework presented in this research has specific characteristics not found in others reported so far. Using a modular approach it takes into account all the categories of hardware and software resources of a manufacturing system. Due to its modularity, the holonic control framework can be used for assigning and scheduling different task types, separately or simultaneously. Thus, it can be used not only for assigning and scheduling transport tasks, but also for finding feasible solutions to the job assignment and scheduling of processing tasks, or to better utilize the auxiliary equipment and devices in a manufacturing system. In the holonic system, under real-time constraints, a feasible schedule for the material handling resources emerges from the combination of individual holon's schedules. Internal evaluation algorithms and coordination mechanisms between the entities in the architecture form the basis for the resultant schedules. The experimental results obtained show a percentage difference between the makespan values obtained using the holonic scheduling approach and the optimal values of under seven percent. Since current control systems in use in industry lack the ability to adapt to dynamic manufacturing environments, the holonic architecture designed and the tests performed in this research could be a part in the effort to build the foundations for the control systems of the next generation manufacturing systems. / Ph. D.

FlexRay is a new automotive network communication protocol for control and interconnection among ECUs (electronic control units) in the cluster. In the FlexRay protocol, a communication cycle consists of static segment and dynamic segment. The static segment is a TDMA scheme designed for transmitting time-triggered messages. Due to its determinism and reliability, it is particularly applicable to X-by-wire applications. Each static slot is allocated to a specified task and the task can transmit message during the exclusive slot. However, if the task has no message to transmit during its assigned slot, the slot cannot be used by other tasks. The overall utilization is low if the bandwidth requirement of each task is not high. To improve the system utilization, we apply the real-time scheduling techniques to devising a deterministic, static cyclic scheduling. The objective is to reduce the demand on the number of static slots needed for scheduling time-triggered tasks. Specifically, we treat the set of static slots that are in the same position in every communication cycle as an individual real-time channel. We model each task as a real-time task, specified by (Ci,Ti). It requires that for every Ti communication cycles, the system must allocate at least Ci time slots to satisfy the real-time constraint of the task. We decompose each such task into a set of subtasks, allocate them to the real-time channels and then apply the rate-monotonic scheduling algorithm to schedule the subtasks within each channel. Finally, we perform computer simulation to evaluate the effectiveness of our proposal. From the simulation results, we conclude that our proposal is able to effectively reduce the demand for the static slots under a wide range of real-time requirements.