معنا و نقش ارزش در برنامه ریزی انعطاف پذیر سیستم های زمان واقعی

The real-time community is devoting considerable attention to flexible scheduling and adaptive systems. One popular means of increasing the flexibility, and hence effectiveness, of real-time systems is to use value-based scheduling. It is surprising however, how little attention has been devoted, in the scheduling field, to the actual assignment of value. This paper deals with value assignment and presents a framework for undertaking value-based scheduling and advises on the different methods that are available. A distinction is made between ordinal and cardinal value functions. Appropriate techniques from utility theory are reviewed. An approach based on constant value modes is introduced and evaluated via a case example.

The specification and design of any computer-based system (real-time or not) inevitably involves trade-offs and compromises. Not all possible services (to use a general term) can be supported. And those services that are implemented will not all have maximum functionality. With most current real-time systems, the implementation phase has little flexibility. A fixed set of `hard' services must be mapped on to the available resources, and pre run-time checks must be made to ensure that all timing constraints (typically, deadlines) are satisfied. This, of course, requires a predictable (bounded) model of the environment's impact on the computer system. 1.1. Need for dynamic scheduling In this paper we attempt to increase the flexibility of real-time systems by allowing certain decisions about the system's behaviour to be made at run-time. This will require some form of dynamic scheduling. The notion of `value' (of a service or sub-service) will be used to control the run-time decision process. Although certain aspects of value-based scheduling have been addressed before 21, 4, 1, 38, 7 and 15, no systematic study has yet been published. In this paper we attempt to lay the foundation for the systematic approach that is needed. The motivation for incorporating run-time decisions is largely based on two observations about the behaviour of typical static schedules. • They use resources inefficiently. As there are sufficient resources to cope with the maximum possible load on the system (i.e. worst-case execution times, worst possible phasings, and worst-case arrival of sporadic work) the average resource utilization is low. Hence, there is considerable scope for value-added computation. • They react inflexibly to failures and overloads. Although the static scheme may be able to cope with certain failures (as defined in its failure model), once the system moves outside its failure model or load hypothesis then no level of service can be depended upon. Hence, it is desirable to allow graceful degradation (of service) when resources are scarce. The need to support value-added computation and graceful degradation is necessarily complicated by the reality that not all services have equal utility. When an implementation is constrained to support all services (all of the time), this is not an issue. For run-time decision making, it becomes an almost insurmountable one (because of the excessive overheads it inevitably introduces, at least in the general case). 1.2. Need for value-based scheduling To keep the terminology clear we shall use the term `utility' to mean the actual benefit that accrues from the delivery of services. In general this measure will not be known with absolute certainty. The value of a service will be some approximation for utility, used to influence the real-time scheduling behaviour of the computer system. During the development of any system many design trade-offs are made. The system designer(s) must articulate preferences between services (or groups of services). Such preferences may be static or vary depending on operating conditions. They are based upon an informed belief in the utility of the system as represented by its services. Due to the complexity of run-time decision making most trade-offs are evaluated at design time. To postpone such decisions until run-time can only be worthwhile if • The decision becomes much more effective if it takes into account run-time data/conditions. • The decision would lead to pessimistic resource usage if taken pre run-time. To facilitate run-time decision making requires the preference relationships to be stored and searched. However, this is only feasible if the overheads involved in making such decisions do not overshadow the potential benefits. This issue is a critical one, many published results in dynamic scheduling have ignored run-time overheads and are therefore misleading. As Chen and Muhlethaler [16] discuss, such scheduling is invariably NP-hard. There are clearly a number of ways of holding preference relationships. In this paper we consider the use of a value attribute assigned to services and subservices. We present a framework (in Section 3) for value-based scheduling, and use this, in Section 4, to evaluate a number of approaches that have been reported in the literature. Section 5of the paper then returns to the key issue of assigning values so that they represent an adequate approximation of the designers' preferences. An extensive example is introduced in Section 2and considered in detail in Section 6. Conclusions are presented in Section 7.

Although there is considerable literature in the real-time community on flexible scheduling and adaptive systems, this work lacks an engineering context. This paper has attempted to formulate a framework for value-based scheduling that will enable this technique to be used in practice. It has shown that general models must take into account run-time overheads if effective dynamic behaviour is to be realised. It is surprising that there is actually very little literature in the scheduling field, on the actual assignment of value. An approach is developed in this paper that allows values to be assigned off-line (on a per mode basis and assuming constant value within a mode). To cater for the requirement that some services have value incomparable with other services, the alternatives available in a particular mode are split into groups. An ordinal relationship exists between the groups. Within a group a cardinal value function is deemed to exist. At run-time changes between modes can accommodate various forms of flexible scheduling and can approximate time-varying value functions. To derive a cardinal value function (i.e. set of values) within a particular mode and group, it is recommended that a technique based on pair-wise comparisons is employed. Assessment routines are available that allow the consistency of a set of pair-wise comparisons to be evaluated and constant values to be generated that furnish maximum consistency. These values can then be used by a range of flexible scheduling techniques that are described in the literature. Future work will attempt to include notions of confidence into the pair-wise comparisons (that is, make use of the knowledge that some judgements are based on sounder engineering data). It will also be necessary to more rigorously integrate multiple attribute functions into the pair-wise comparisons technique. It remains a open question whether time-varying value functions can be adequately approximated by this (or any other) approach. Ultimately the evaluation of the approach supported in this paper will come from application experience in an appropriate industrial context. The case study described in this paper will be expanded with the intention of including more domain knowledge and practical experience. It is intended that this will form the basis for an extensive evaluation of the approach.