Deep learning (DL) based knowledge tracing (KT) models have challenges for uninterpretable prediction and parameter representation in educational applications, though they achieved remarkable outcomes in predicting the exercise performance of students. This paper proposes a novel knowledge tracing model of high precision and interpretability (namedXKT) for questions with multiple knowledge concepts based on cognitive learning theories and multidimensional item response theory (MIRT). TheXKTconsists of three differentiable network components: multi-feature embedding, cognition processing network, andMIRT-based neural predictor, which aim to provide an explainable prediction of student exercise performance. Specifically, inXKT, multi-feature embedding learns the rich semantic representation (e.g., knowledge distribution information) to enhance knowledge tracing using a cognition processing network. The cognition processing network performs selective perception, ability memory processing, and long-term knowledge memory processing to ensure the explainable factor representation for theMIRT-based neural predictor. Lastly, theMIRT-based neural predictor employs psychometric parameters to interpret student exercise predictions better. Extensive experiments on four real-world datasets show thatXKToutperforms existingKTmethods in predicting future learner responses. Moreover, ablation studies further show thatXKToffers good interpretability of student performance predictions with multiple knowledge concepts, indicating excellent potential in real-world educational applications.

Building accurate human behavior models is necessary for ambient intelligence. However, human activity recognition (HAR) in continuously monitored physical space faces challenges to achieve a good performance yet using only simple computing resources. In this work, we model HAR as an edge classification problem for a collaborative event graph of context entities in a sequential bipartite graph form. We design a semantic learning framework, called KGAR, to perform HAR by mining, encoding, and exploiting deep semantic knowledge of activities in an end-to-end fashion. KGAR has three components: preprocessor, KGEncoder, and predictor. The preprocessor builds offline a tiny knowledge graph of activities, to model and capture multidimensional semantic relationships between activities and core context entities. KGEncoder encodes the knowledge graph of activities using improved graph neural networks (GNNs) models, to avoid different confusing context patterns. The predictor can be deployed using lightweight deep neural networks to produce real-time labels. Experimental results show that using KGEncoder in KGAR improves the performance of original deep neural networks by 25% - 439% on five datasets. The time of labeling each sensor event during testing with event streams is less than 0.5ms. We have also conducted extensive experimental study to show that KGAR outperforms different types of models in more complex activity scenarios. We believe KGAR could be used for real-time HAR in real life with its high prediction performance and low computing requirement.

Casting sequential recommendation (SR) as a reinforcement learning (RL) problem is promising and some RL-based methods have been proposed for SR. However, these models are sub-optimal due to the following limitations: (a) they fail to leverage the supervision signals in the RL training to capture users’ explicit preferences, leading to slow convergence; and (b) they do not utilize auxiliary information (e.g., knowledge graph) to avoid blindness when exploring users’ potential interests. To address the above-mentioned limitations, we propose a multiplex information-guided RL model (MELOD), which employs a novel RL training framework with Teach and Explore components for SR. We adopt a Teach component to accurately capture users’ explicit preferences and speed up RL convergence. Meanwhile, we design a dynamic intent induction network (DIIN) as a policy function to generate diverse predictions. We utilize the DIIN for the Explore component to mine users’ potential interests by conducting a sequential and knowledge information joint-guided exploration. Moreover, a sequential and knowledge-aware reward function is designed to achieve stable RL training. These components significantly improve MELOD’s performance and convergence against existing RL algorithms to achieve effectiveness and efficiency. Experimental results on seven real-world datasets show that our model significantly outperforms state-of-the-art methods.

Explicit and implicit knowledge about users and items have been used to describe complex and heterogeneous side information for recommender systems (RSs). Many existing methods use knowledge graph embedding (KGE) to learn the representation of a user-item knowledge graph (KG) in low-dimensional space. In this article, we propose a lightweight end-to-end joint learning framework for fusing the tasks of KGE and RSs at the model level. Our method proposes a lightweight KG embedding method by using bidirectional bijection relation-type modeling to enable scalability for large graphs while using self-adaptive negative sampling to optimize negative sample generating. Our method further generates the integrated views for users and items based on relation-types to explicitly model users’ preferences and items’ features, respectively. Finally, we add virtual “recommendation” relations between the integrated views of users and items to model the preferences of users on items, seamlessly integrating RS with user-item KG over a unified graph. Experimental results on multiple datasets and benchmarks show that our method can achieve a better accuracy of recommendation compared with existing state-of-the-art methods. Complexity and runtime analysis suggests that our method can gain a lower time and space complexity than most of existing methods and improve scalability.

Real-time/online activity recognition (AR) is an important technology in smart Internet of Things (IoT) systems where users are assisted by smart devices in their daily activities. How to generate appropriate feature representation from sensor event streaming is a challenging issue for accurate and efficient real-time AR. Previous AR models that rely on explicit domain knowledge are not appropriate for online recognition of complex human activities. We propose to use unsupervised learning to learn about the latent knowledge and embed the activity probability distribution prediction as high-level features to boost real-time AR performance. The proposed approach first learns the latent knowledge from explicit-activity window sequences using unsupervised learning, and derives the probability distribution prediction of activity classes for a given sliding window. Our approach then feeds the prediction with other basic features of the sliding window into a classifier to produce the final class result on each event-count sliding window. Experiments on five smart home datasets show that the proposed method achieves a higher accuracy by at least 20 percent improvement on F1_score than previous traditional algorithms, while maintaining a lower time cost than deep learning based methods. An analysis on the feature importance shows that the addition of probability distribution prediction about activity classes leads to a promising direction for real-time AR.

Many advances have been introduced recently for service-oriented computing and applications (SOCA). The Internet of Things (IoT) has been pervasive in various application domains. Fog/Edge computing models have shown techniques that move computational and analytics capabilities from centralized data centers where most enterprise business services have been located to the edge where most customer’s Things and their data and actions reside. Network functions between the edge and the cloud can be dynamically provisioned and managed through service APIs. Microservice architectures are increasingly used to simplify engineering, deployment and management of distributed services in not only cloud-based powerful machines but also in light-weighted devices. Therefore, a key question for the research in SOCA is how do we leverage existing techniques and develop new ones for coping with and supporting the changes of data and computation resources as well as customer interactions arising in the era of IoT and Fog/Edge computing. In this editorial paper, we attempt to address this question by focusing on the concept of ensembles for IoT, network functions and clouds.

Social recommender system, using social relation networks as additional input to improve the accuracy of traditional recommender systems, has become an important research topic. However, most existing methods utilize the entire user relationship network with no consideration to its huge size, sparsity, imbalance, and noise issues. This may degrade the efficiency and accuracy of social recommender systems. This study proposes a new approach to manage the complexity of adding social relation networks to recommender systems. Our method first generates an individual relationship network (IRN) for each user and item by developing a novel fitting algorithm of relationship networks to control the relationship propagation and contracting. We then fuse matrix factorization with social regularization and the neighborhood model using IRN's to generate recommendations. Our approach is quite general, and can also be applied to the item-item relationship network by switching the roles of users and items. Experiments on four datasets with different sizes, sparsity levels, and relationship types show that our approach can improve predictive accuracy and gain a better scalability compared with state-of-the-art social recommendation methods.

The world is seeing more sensing and actuating devices deployed in our environment as part of the global digital ecosystem. One issue for perpetually running Internet of Things (IoT) devices is the energy efficiency. Many new IoT devices are running on powerful platforms that have ample computing and memory capacities to support multiple services. One energy saving strategy is therefore to co-locate several services on one device in order to reduce the computing and communication energy cost. Our research proposes the service merging approach for mapping and co-locating many services on one device. The service co-location problem is modeled as the Maximum Weighted Independent Set (MWIS) problem. We study the algorithms to transform a service flow to a co-location graph, and then use heuristic algorithms to find the maximum independent set which will be used for the service co-location decisions. The performance of different co-location algorithms are evaluated by simulation in this study.

This paper presents an on-line admission control methodology for periodic and aperiodic service processes with end-to-end real-time constraints. Both types of service process requests dynamically join and leave a system at run time. During the admission test, the schedulability of a periodic task is determined by using its fixed task capacity. Aperiodic tasks are admitted using the available capacity after admitted periodic tasks. At run time, the earliest deadline first (EDF) scheduling is used to schedule the mixed periodic and aperiodic workloads. Simulation results show that the proposed algorithm may achieve up to 90% in system utilization, while incurring a low admission overhead for each service request.

For advanced features of next generation vehicles, the real-time programs in automotive embedded systems are dramatically increasing. For such large volume program codes, this paper proposes a novel framework to use high-density and low-cost nonvolatile memory, i.e., NAND flash memory, as a low-cost means of storing and executing hard real-time programs. Regarding this, one challenge is that NAND flash memory allows only 2 KB page-based read operations not per-byte random accesses, which requires RAM as working storage for code executions. This paper proposes two solutions, i.e., partitioned RAM solution and shared RAM solution, that minimize the RAM size required to deterministically guarantee the deadlines of all the hard real-time tasks. The proposed solutions are verified with the actual real-time programs for unmanned autonomous driving. To the best of our knowledge, this is the first work that allows us to use NAND flash memory for hard real-time program executions with the minimal usage of RAM.

Service flow in SOA systems need to detect quality of service (QoS) problems and to guarantee end-to-end performance. In previous work, we have proposed two faulty service identification methods: a dependency matrix based diagnosis and a Bayesian network based diagnosis. In this paper, we present a hybrid diagnosis to achieve high diagnosis accuracy and low diagnosis cost. The hybrid diagnosis reduces the problem size by applying dependency matrix based diagnosis result in Bayesian network and excluding services that are not critical to the end-to-end QoS from the diagnosis. Our experimental results show that the accuracy of the hybrid diagnosis is similar to the Bayesian network diagnosis yet reduces more than 90% of the diagnosis time.

Service-oriented architectures (SOA) provide application systems the flexibility and cost-savings of dynamically composing workflows from reusable services. However, current SOA frameworks do not provide support for real-time workflow planning and execution. The goal of the RT-Llama SOA middleware framework is to address these new requirements. It works both at the service-level, by enhancing existing SOA middleware with service execution reservation capabilities, and at the end-to-end workflow-level, by creating a distributed component infrastructure for deadline-based workflow composition. This paper focuses on the design and implementation of the Virtual CPU (VCPU) resource scheduling scheme in RT-Llama to achieve predictable process executions. We have created a prototype implementation of RT-Llama using Sun Real-time JVM running on Solaris OS. Experiments consisting of real world service applications show that requests with end-to-end deadlines can be admitted and completed before deadlines with the VCPU scheme. We also show that service class differentiation can be achieved.

In the business context, accountability has become a major concern for businesses around the world in aftermath of corporate scandals and fallouts. However, accountability has not been rigorously considered in IT system technologies and solutions. The goal of this study is to provide a clear understanding of accountability concept in service-oriented computing and, more generally, e-society. We first outline the general concept of accountability and presents a review on accountability from both management and IT perspective. We also clarify the ambiguity between the accountability concern and other architectural concerns such as security, QoS, trust and reputation.We present an SOA research project, the Llama accountability framework, which is an accountable service delivery infrastructure to support the monitoring, analysis, and reconfiguration of service processes. We believe such a framework will be useful for ensuring better e-services in an e-society.

Service processes in SOA are composed dynamically by services from different service providers. At run-time, some services may become faulty and cause a service process to violate its end-to-end quality of service (QoS) constraints. We propose an effective approach for replacing only faulty services and some of their neighboring services to maintain the original end-to-end QoS constraints. We use an iterative algorithm to search for a reconfiguration region that has replaceable services to meet the original QoS constraint for the region. Services in reconfiguration regions may be replaced using one-to-one, one-to-many, or many-to-one service mappings. By replacing only services in reconfiguration regions rather than the whole service process, reconfiguration overheads are lowered and service disruptions may be reduced. We have implemented the Adaptation Manager in the Llama ESB middleware. Performance study shows that our approach may efficiently repair service processes.

In SOA, services may become volatile and fail to deliver the quality of service as requested by users. In this paper, we present an approach for repairing failed services by replacing them with new services and ensuring the new service process still meets the user specified end-to-end QoS constraints. An iterative structural inspection algorithm is designed to produce reconfiguration regions that include one or more failed service. By reconfiguring only services in the selected regions, the business process will not be affected significantly. The algorithm may also utilize those available QoS constraints to relax the original constraints of a reconfiguration region and to provide more effective reconfiguration solutions. We also present the middleware components to support the service reconfiguration in the LLAMA framework.

Real-time systems using rate-monotonic fixed priority scheduling can be checked for schedulability either by sufficient but pessimistic schedulability conditions or by exact testing. Exact testing provides a more precise result but may not be performed in polynomial time. Audsley et al. proposed one of the earliest methods by iteratively deriving the response times of jobs. Other researchers have improved the exact test method by using different initial values for testing. In this paper, we propose new initial values of p, - p, , and f in a task set of i tasks, where p, is the period of task Tl. We show that the new initial values can significantly improve the efficiency of exact testing. These period-dependent initial values can also be used for the schedulability test of multiframe task models and effectively reduce the number of iterations for testing.

The real-time multiframe task model first studied by Mok and Chen assumes that the computation times of a periodic task vary instance by instance. They have derived an utilization bound for verifying the schedulability of multiframe task sets. Their schedulability test has since been improved by other researchers. In this paper we use the information about the relative period ratios between tasks in a system to derive a new schedulability condition. By considering the smallest and the largest period values in a system, we can show that the RM schedulability bound can be improved significantly. This method also can be applied to other test methods studied earlier to improve the schedulability of real-time multiframe systems.

Real-time systems using rate monotonic fixed priority scheduling can be checked for schedulability either by pessimistic schedulability conditions or exact testing. Exact testing provides a more precise result but cannot always be performed in polynomial time. Audsley et al. proposed one of the earliest methods by iteratively deriving the job response times. Other researchers have improved the efficiency of their exact test method by using different initial values. All currently proposed initial values do not use the relationship between task periods. In this paper we define initial values using the largest and the second largest periods in a system. We show that the new initial values can significantly improve the exact test.

Many optimal uniprocessor schedulers, such as earliest deadline first (EDF) and rate monotonic (RM), do not have a good schedulability bound on multiprocessor systems. In this paper, we study an on-line algorithm earliest deadline first until Zero laxity (EDZL) for multiprocessor systems. A set of tasks scheduled by EDZL is scheduled using EDF until a job experiences a zero laxity. To avoid the job from missing its deadline, the priority of the job is immediately promoted to the highest priority. We derive the schedulability bound of 3/2+\umax-1/2\ for two-processor systems, where umaxis the maximum utilization of an individual task in the given task set. We also discuss the best known upper bound and lower bound on EDZL schedulability conditions.

Service-Oriented Architecture (SOA) provides a flexible framework for service composition. Using standard-based protocols (such as SOAP and WSDL), composite services can be constructed by integrating atomic services developed independently. Algorithms are needed to select service components with various QoS levels according to some application-dependent performance requirements. We design a broker-based architecture to facilitate the selection of QoS-based services. The objective of service selection is to maximize an application-specific utility function under the end-to-end QoS constraints. The problem is modeled in two ways: the combinatorial model and the graph model. The combinatorial model defines the problem as a multidimension multichoice 0-1 knapsack problem (MMKP). The graph model defines the problem as a multiconstraint optimal path (MCOP) problem. Efficient heuristic algorithms for service processes of different composition structures are presented in this article and their performances are studied by simulations. We also compare the pros and cons between the two models.

Feasibility and schedulability problems have received considerable attention from the real-time systems research community in recent decades. Since the publication of the Liu and Layland bound, many researchers have tried to improve the schedulability bound of the RM scheduling. The LL bound does not make any assumption on the relationship between any of the task periods. In this paper we consider the relative period ratios in a system. By reducing the difference between the smallest and the largest virtual period values in a system, we can show that the RM schedulability bound can be improved significantly. This research has also proposed a system design methodology to improve the schedulability of real time system with a fixed system load.

Web service may be used to construct autonomic business processes, where several Web services interact with each other to carry out complex transactions or workflows. During the execution of an autonomic process, if one component service fails or becomes overloaded, a mechanism is needed to ensure that the running process is not interrupted and the failed service is quickly and efficiently replaced. In this paper, we present two algorithms to solve the problem. The first algorithm uses the backup path approach so that the predecessor of a failed service may quickly switch to a predefined backup path. The second algorithm uses the replacement path approach to re-construct a new process by skipping a failed service. All these dynamic adaptations can be done by business process itself or a QoS broker which is part of an autonomic system. The simulation result shows that, when producing the information needed for dynamic adaptation, the running time of business process composition increases only by a constant factor regardless of the system size.

Web services are self contained and self described modular applications that can be published, discovered and employed on the Web. Many standard protocols supporting Web services have been adopted and more are being proposed. We study the issue on providing intelligent Web services. We propose the enhancement of Web service functionalities by deploying software agents on both server side and/or client side. Our goal of designing the WISE Web service architecture is to provide a working middle ground between the current Web service standards and the semantic Web architecture. The WISE software agent architecture for Web services is presented. We discuss the design issues of WISE. We also present the QoS management protocol and algorithm that can be used by WISE servers.

Researchers in the real-time system community have designed and studied many advanced scheduling algorithms. However, most of these algorithms have not been implemented since it is very difficult to support new scheduling algorithms on most operating systems. To address this problem, we enhance the scheduling mechanism in Linux to provide a flexible scheduling framework. In the real-time and embedded Linux (RED-Linux) project, we implement a general scheduling framework which divides the system scheduler into two components: dispatcher and allocator. The dispatcher provides the mechanism of system scheduling and resides in the kernel space. The allocator is used to define the scheduling policy and implemented as a user space function. This framework allows users to implement application-specific schedulers in the user space which is easy to program and to debug. The framework also relieves the deficiency from the stock Linux scheduler which is not designed for real-time applications. To further enhance its power, a hierarchical scheduling mechanism has been provided in RED-Linux to allow a system designer to integrate different real-time applications together. Using scheduling groups, real-time jobs can be managed and scheduled in a hierarchical manner. In this paper, we discuss how the group mechanism is implemented in RED-Linux.

Many computer systems, such as those for open system environments or multimedia services, need an efficient schedulability test for online admission control of new jobs. Although various polynomial time schedulability tests have been proposed, they often fail to decide the schedulability of the system precisely when the system is heavily loaded. On the other hand, most precise schedulability tests proposed to date have a high complexity and may not be suitable for online tests. We present new efficient online schedulability tests for both the periodic process model [C. L. Liu et al., (1973)] and the multiframe process model [A. K. Mok et al., (1997)] in uniprocessor environments. The schedulability tests are shown to be more precise and efficient than any existing polynomial-time schedulability tests. Moreover, the tests can be done incrementally as each new task arrives at the system. Our proposed tests can also be used for the multiframe model where a task may have different computation times in different periods. We show the performance of the proposed schedulability tests in several simulation experiments.

A hierarchical scheduling mechanism has been implemented in RED-Linux to integrate different scheduling paradigms together. We extend the concept of group so that the execution budget for jobs in RED-Linux can be managed in a hierarchical way. A budget group contains a set of jobs that share the available budget for the group. The jobs in a budget group could be a normal job or another budget group job, which contains its own group of jobs. Every job has its system budget. But if it belongs to a budget group, the job's budget is also constrained by its group's budget. We discuss how the budget group mechanism is implemented in RED-Linux. We also show how to use the mechanism to implement several schedulers.

Distributed real-time applications share a group of processors connected by some local area network. A rigorous and sound methodology to design real-time systems from independently designed distributed real-time applications is needed. In this paper, we study a distributed real-time system design scheme using CBS-based end-to-end scheduling. The scheduling scheme utilizes CBS to allocate both CPU shares and network bandwidth to a distributed real-time application when it arrives at the system. Our proposed solution uses the same scheduling paradigm for both resources. In this way, we believe the system can have a more consistent scheduling objective and may achieve a tighter schedulability condition.

In RED-Linux kernel, a General Scheduling Framework (GSF) has been implemented. Under GSF, different scheduling algorithms can be easily implemented. However GSF only addresses the scheduling of CPU. Other system resources are not considered. In this paper we propose a general resource management framework for various OS resources. When user applications request and consume system resources, they may use uniform APIs although each type of OS resource has its own properties and means to be controlled. In the resource management framework, we also allow the inter-relationship between different types of resources to be defined and managed.

This paper investigates a class of rate-based real-time scheduling algorithms based on the idea of general processor sharing (GPS). We extend the GPS framework of Parekh and Gallager (1993) for periodic and sporadic process scheduling and show the optimality of GPS-based scheduling. In particular, we propose the earliest-completion-time GPS (EGPS) scheduling algorithm to simulate the GPS algorithm with much lower run-time overheads. The schedulability of each process is enforced by a guaranteed CPU service rate, independent of the demands of other processes. We provide a theoretical foundation to assign proper CPU service rates to processes to satisfy their individual stringent response time requirements. We also propose a GPS-based scheduling mechanism for jitter control. Finally, the performance of the proposed algorithms is studied using a generic avionics platform example and simulation experiments on jitter control and mixed soft and hard real-time process scheduling.

Real-time distributed applications have timing constraints on tasks running on several processors. To design real-time systems with end-to-end performance requirements, we need to have algorithms to schedule and to coordinate tasks on different processor nodes. An end-to-end scheduling approach based on the pinwheel scheduling model is presented for distributed real-time systems, We show how tasks on different nodes may be transformed to have periods consisting of only harmonic numbers. With harmonic periods, we can use a polynomial-time algorithm to find the start and finish times of each task on each node. Phase alignment algorithms are then applied to adjust the phases between schedules of neighboring nodes so that the overall end-to-end delay is minimized. Using the distributed pinwheel model, schedules on different nodes are synchronized to lessen the delays. For many real-time systems, this approach provides a predictable performance and a short end-to-end delay.

Hierarchical schedulers are useful to integrate different scheduling paradigms together. The original RED-Linux general scheduling framework does not support hierarchical schedulers efficiently because the dispatcher cannot tell whether a job is an aperiodic job or a real-time job. In the work reported in this paper, we add an extra parameter, the group number, to the RED-Linux scheduling framework in order to identify the type of jobs. This mechanism does not introduce any overhead to normal real-time tasks and only a constant overhead per job for hierarchical jobs. We discuss how to implement hierarchical schedulers and how to use this extension to support sporadic schedulers. We also discuss various versions of the sporadic server algorithm.

Most computer-based systems have hard real-time constraints. Schedulers in complex systems must be designed to manage a set of applications developed and deployed independently. We study an open real-time environment architecture for distributed systems where real-time applications may run concurrently with non-real-time applications. The architecture uses a two-level scheduling scheme. Each application is assigned a sporadic server to schedule the processes in the application. All sporadic servers are then scheduled by a system-wide fixed priority scheduler. Using the proposed open environment architecture, all hard real-time applications are guaranteed to have their reserved CPU utilization in order to meet all their deadlines. The guarantee is independent of the behaviors of all other applications in the same system. We present the schedulability analysis methods on systems with or without shared memory.

Many scheduling paradigms have been studied for real-time applications and real-time communication network. Among them, the most commonly used paradigms include priority-driven, time-driven and share-driven paradigms. In this paper, we present a general scheduling framework which is designed to integrate these paradigms in one framework. The framework is implemented in our real-time extension of the Linux kernel, RED-Linux. Two scheduler components are used in the framework: Allocator and Dispatcher. For each job, the framework identifies four scheduling attributes: priority, start time, finish time and budget. We show that the framework can be used to efficiently implement many well-known scheduling algorithms. We also measure and analyze the performance of the framework implemented in RED-Linux.

Pinwheel scheduling algorithms can be used to produce distance-constrained real-time system schedules where the temporal distance between any two consecutive completions of a task must be less than a pre-defined time interval. A pinwheel schedule can be generated off-line and executed cyclically. Such an approach provides a good predictability and allows for off-line schedule optimization. However, the static approach is inflexible and may require a large space to store the schedule. By taking advantage of the harmonic property between pinwheel task periods, one can generate the pinwheel schedule dynamically at run time in polynomial time and space. In this way, efficient and flexible time-driven schedulers can be implemented. The authors show the algorithms and study the practical issues on implementing on-line pinwheel schedulers.

A class of real time scheduling algorithms EGPS is proposed. Using EGPS, the schedulability of each process is enforced by a guaranteed CPU service rate, independent of the demands of other processes. Our research uses a GPS based framework for periodic and sporadic process scheduling, jitter control, service rate adjustment, and mixed scheduling of soft and hard real time processes. We then study the performance of the proposed algorithms by using a generic avionics platform example for our simulation experiments in jitter control and mixed scheduling of soft and hard real time processes.

The field of multi-criteria optimization is reviewed as it pertains to lexicographic optimization over real-valued vector spaces. How lexicographic optimization differs from multi-criteria optimization that is restricted to proper Pareto optima is explained. Through a survey of previous work, it is revealed that there are currently no generally applicable methods for solving lexicographic optimization problems, and it is explained that this is due to the lack of an adequate mathematical theory for such problems. A more adequate mathematical theory is then presented for lexicographic optimization in this paper.

Several pinwheel schedulers have been reported previously for scheduling real-time systems in which the temporal distances between consecutive executions of tasks must be less than their respective distance constraints. The scheduler Sr has been used for task sets with real number distance constraints and execution times. Sr transforms the distance constraints in a system into harmonic values with a base of 2. The authors present a pinwheel scheduler Sr/sup b/ which is derived from Sr using any base greater than or equal to d. The schedulability condition of Sr/sup b/ is presented and its optimality is proved. They also study the performance of Sr/sup b/ by simulation and compare it with a near-optimal heuristic algorithm HSr.

In hard real time systems, each task must not only be functionally correct but also meet its timing constraints. A common approach to characterizing hard real time tasks with repetitive requests is the periodic task model. In the periodic task model, every task needs to be executed once during each of its periods. The execution of a task in one period is independent of the execution of the same task in another period. Hence, the executions of the same task in two consecutive periods may be right next to each other, or at the far ends of the two periods. While the periodic task model can serve as a simple paradigm for scheduling tasks with repetitive requests, it may not be suitable for all real time applications. For example, in some real time systems, the temporal distance between the finishing times of any two consecutive executions of the same task must be less than or equal to a given value. In other words, each execution of a task has a deadline relative to the finishing time of the previous execution of the same task. Scheduling algorithms designed for the periodic task model may not provide efficient solutions for tasks with temporal distance constraints. We propose the (preemptive) distance constrained task system model which can serve as a more intuitive and adequate scheduling model for "repetitive" task executions. We design an efficient scheduling scheme for the model, and derive a schedulability condition for the scheduling scheme. We also discuss how to apply the scheduling scheme to real time sporadic task scheduling and to real time communications.

Algorithms for allocating resources and scheduling tasks are important to the success of many real-time systems with end-to-end performance requirements. In this paper, an end-to-end scheduling model based on the pinwheel scheduling algorithms is presented for distributed real-time systems. We discuss how tasks on different nodes may be transformed to have harmonic periods. We also present algorithms to adjust the phases between schedules on neighboring nodes so that the overall end-to-end delay is reduced. Using the pinwheel approach, schedules on different nodes are closely synchronized and more static. However, for many real-time systems, this practical approach may provide a more predictable performance and a shorter end-to-end delay.

The job scheduling problems for real-time jobs with temporal distance constraints (JSD) are presented. In JSD, the start times of two related jobs must be within a given distance. The general JSD problem is NP-hard. We define the multilevel unit-time JSD (MUJSD) problem for systems with m chains of unit-time jobs in which neighboring jobs in each chain must be scheduled within c time units. We present an $O(n^{2})$-time algorithm, where n is the total number of jobs in the system, and also an $O(m^{2}c^{2})$-time algorithm. Some other variations of the JSD problems are also investigated.

The imprecise computation technique has been proposed as a way to handle transient overload and to enhance fault tolerance of real-time systems. In a system based on this technique, each time-critical task is designed in such a way that it can produce a usable, approximate result in time whenever a failure or overload prevents it from producing the desired, precise result. This paper describes ways to implement imprecise computations, models to characterize them and algorithms for scheduling them. An imprecise mechanism for the generation and use of approximate results can be integrated in a natural way with a traditional fault-tolerance mechanism. An architectural framework for this integration is described.>

In addition to maintaining database consistency as in conventional databases, real-time database systems must also handle transactions with timing constraints. While transaction response time and throughput are usually used to measure a conventional database system, the percentage of transactions satisfying the deadlines or a time-critical value function is often used to evaluate a real-time database system. Scheduling real-time transactions is far more complex than traditional real-time scheduling in the sense that (1) worst case execution times are typically hard to estimate, since not only CPU but also I/O requirement is involved; and (2) certain aspects of concurrency control may not integrate well with real-time scheduling. In this paper, we first develop a taxonomy of the underlying design space of concurrency control including the various techniques for achieving serializability and improving performance. This taxonomy provides us with a foundation for addressing the real-time issues. We then consider the integration of concurrency control with real-time requirements. The implications of using run policies to better utilize real-time scheduling in a database environment are examined. Finally, as timing constraints may be more important than data consistency in certain hard realtime database applications, we also discuss several approaches that explore the nonserializable semantics of real-time transactions to meet the hard deadlines.>

The authors study dynamic load balancing algorithms in loosely coupled hard-real-time systems. The gradient model, focused addressing and the bidding methods are used. The gradient model entails transferring backlogged tasks to nearby idle processors according to pressure gradient indirectly established by request from idle processors. The focused addressing node uses network-wide surplus information in determining the target node to send excessive tasks to. Busy nodes in the bidding method send out requests for bids to migrate tasks that are not to be completed. In the model, each job is divided into a hard task and a soft task. All hard tasks must be finished by their deadlines and will not be migrated to other nodes. If a soft task cannot be completed by its deadline, it can be migrated to a neighboring node with less load or more surplus CPU time. Three load-balancing algorithms were evaluated.>

The relevance of formal methods for practical software system design is discussed. Prominent representatives of formal approaches present their findings and experience about the use and the usefulness of formal methods. It has been proposed that all programmers would be more productive and produce higher quality products if they would learn two things: predicate calculus; and program correctness (including formal program development). It is argued that the complexity, pervasiveness, and critical nature of modern and future computer systems makes it imperative that such systems be engineered for reliability and maintainability. Formal methods constitute an extremely promising approach to the design of reliable systems. The schedulability aspect of real-time system development is discussed. In general, formal methods should be preferred over other less formal methods since they can provide much better and stronger guarantees on real-time system performance.>

A novel model of real-time task systems with temporal distance constraints is presented. In such systems, the distance between any two consecutive finishing times of the same task must be less than or equal to a given value. Using the periodic task model for such tasks may not provide an efficient solution. The authors discuss the scheduling approaches for this distance-constrained task model and propose several scheduling algorithms. They also study the schedulability conditions for these algorithms.>

The scheduling problems for real-time systems with multiversion computations are studied. A computation is performance polymorphic if it has been implemented in several versions each with a different performance characteristics like the time needed to produce a result. Given a set of periodic or aperiodic jobs, each with multiple versions, an investigation is made of the scheduling problem which determines the execution time for each job, and a version is selected to optimize the overall system performance objective. The problems are modeled as resource sharing problems. Known techniques for the sharing problem can be used to allocate the time to each job. Several heuristic algorithms are studied for problems which are NP-complete, and their performances are compared.>

The problem of assigning execution intervals for periodic transactions in real-time databases is discussed. The object value evolution rate and the importance of the object are used as two factors for deciding transaction periods. Two different objective functions are defined to reflect different system design goals. Algorithms for optimizing each objective function are presented. The principle behind these algorithms is to allow the transactions which have higher weights to be executed more often. It is assumed that systems use the rate monotonic algorithm for scheduling transactions. Many other scheduling algorithms, like the earliest deadline first algorithm can also be used. Some examples using the proposed algorithms are given.>

A systematic optimization process for multiple-instance resource sharing in real-time systems is presented. The authors derive the schedulability condition for systems with such resources and present an algorithm which can be used to divide a resource pool into smaller groups in order to improve the worst-case blocking behavior. They present the system model used and review some related work. The multi-instance priority ceiling protocol and its properties are discussed, the effect of resource preallocation on the schedulability of a system is studied, and an optimal resource preallocation algorithm is presented.>

A novel model for complex real-time systems is proposed. In this model, several versions of a program fragment are provided to perform a particular action. These versions will differ only in their performance parameters such as the time required, the resources consumed, and the precision of the results. The authors describe an implementation of a technique called performance polymorphism, in which the process of selecting a version from this set may be automated. Performance polymorphism is a unified theory to express the choice among multiple versions in a way that is both natural and powerful. It allows the flexibility of adding new versions at any time, of adapting to unforeseen constraints, and of adapting to automatically generated variants of a procedure (as, for example, might come from a parallelizing compiler). A means to implement the theory of performance polymorphism that requires very low overheads at run time has been developed.>

Sophisticated and flexible real-time systems may use several versions of a program fragment that performs a particular computation. These versions differ only in their performance parameters, such as the time required, the resources consumed, and the precision of the results. A model is presented of performance polymorphism, whereby the process of selecting a version from the available set is automated. The binding problem for this new model of polymorphism and the problem of allocating resources among computations that all support performance polymorphisms are discussed.>

The problem of scheduling periodic jobs in hard real-time systems that support imprecise computations is discussed. Timing faults are avoided in such systems by making available intermediate, imprecise results of acceptable quality when results of the desired quality cannot be produced on time. Two workload models of imprecise computations are presented. These models differ from traditional models in that a task may be terminated any time after it has produced an acceptable result. Each task is logically decomposed into a mandatory part followed by an optional part. In a feasible schedule, the mandatory part of every task is completed before the deadline of the task. The optional part refines the result produced by the mandatory part to reduce the error in the result.>

In real-time systems, jobs must be finished before their deadlines. When several jobs have similar requests, handling related operations together may improve both the response times of individual jobs and the total execution time of the system. This is because many jobs have common operations which can be performed only once if jobs are coalesced as a single job. Scheduling algorithms which use the technique of job coalescing to meet more job deadlines are studied. Optimal scheduling algorithms for different system models are investigated. Due to the high complexities of these optimal algorithms, several online heuristic algorithms and their performances are investigated.>

The effect of parallel execution on the complexity of scheduling hard real time jobs on multiprocessors is analyzed. Studied is the scheduling problem in which a job may be parallelized and executed on any number of processors concurrently. In hard real-time systems, each job must be completed before a deadline. Parallelization gives a scheduler the flexibility to allocate more processors to a job whose deadline is near. Unfortunately, with this flexibility some of the multiprocessor scheduling problems are very difficult. The NP-hardness of scheduling parallelizable jobs where each job has a fixed priority is proved. A heuristic algorithm is proposed for finding an approximate job partition on two processors. Simulation results show that the heuristic algorithm usually has a very good performance.>

The timing constraint mechanism in a real-time programming language called FLEX is described. A FLEX program can use the constraint primitives to express timing and resource requirements. If the required time or resources are not available at run-time, a FLEX program can dynamically produce monotonic imprecise results. Both time and system resources are defined as first-class objects in the language so that they can be evaluated just like any other first-class object. By unifying time, resources, and normal objects, the semantics and the executions of real-time programs are more manageable. Some implementation issues for FLEX are discussed, and some performance data are presented.>

In real-time database systems, a transaction may not have enough time to complete. In such cases, partial, or imprecise, results can still be produced. The authors have proposed an imprecise result mechanism for producing partial results, which is used to implement timing error recovery in real-time database systems. They also present a model of real-time systems that distinguishes the external data consistency from the internal data consistency maintained by non-real-time systems. Providing a timely response may require sacrificing internal consistency. The authors discuss three examples that have different requirements of data consistency and present algorithms for implementing them.>

Remote procedure call (RPC) is a programming primitive that makes building distributed programs easier. Atomicity, whkh implies totality and serializability, has been recognized as an important property to assure consistency in spite of computing node crashes. We have implemented an atomk remote procedure call mechanism which provides users a simple and reliable language primitive. Concurrency is controlled by attaching a call graph path identifier to each message representing a procedure call. Procedures keep their last accepted calling message paths to compare against incoming message paths. Only calls that can be serialized are accepted. Associated states of static variables are saved in backup processors on procedure entry and restored to corresponding variables in case of procedure crash. Detailed concurrency control and recovery algorithms are given, and illustrated with examples.