| Abstract UML is the standard visual object modeling language which may be very useful as a system design communication language. However, UML as a real-time modeling language has limitations. It basically provides a lot of syntax, but not enough semantics. The UML Profile for Schedulability, Performance and Time, extends the notation and semantics for the real-time domain. It is supposed to overcome the limitations which are related to and provide suitability for modeling real-time systems. Since we are mainly concerned with the problem of real-time operating system scheduling, the article discusses the ability of UML and its profile to determine the schedulability of a planned piece of software. 1 INTRODUCTION Object-oriented modeling is naturally fitted for capturing various characteristics and requirements of systems. However, the current object-oriented techniques do not provide the tools and proper services in order to design all the characteristics of real-time systems, particularly those concerning constraints (timing constraints, resource constraints...) and non-functional requirements (QoS, security requirements...). The Unified Modeling Language (UML) is an industry standard which provides notation for describing object oriented models. The language represents a collection of the best engineering practices that have proven successful in the modeling of large and complex systems [UML03]. Nowadays, UML is commonly used as a description language and is more complete than other languages in its support for modeling complex systems, being also suitable for modeling real-time systems [Bj?rkander03], [Douglass98], [Gomaa00]. UML has been also used in a large number of time-critical and resource-critical systems [UMLSPT03]. Despite its real-time capabilities [Douglass98b], [Jigorea00], [Küster01], [Selic98], UML has some limitations as well, because it lacks in notations and semantics to represent several aspects that are of particular concern to real-time system developers [Bichler02], [Lavazza01]. However, it has mechanisms for improving the design phase through its extensibility capabilities: the UML profile mechanism provides a way of specializing the concepts defined in the UML standard. The UML Profile for Schedulability, Performance, and Time was submitted in response to a Request for Proposal (RFP) to define a common, standard way in which timeliness and related properties could be specified. The Schedulability Modeling is a sub-profile, which is intended as a general base for supporting a wide variety of known and future schedulability analysis methods [UMLSPT03]. In order to asses UML validity and limitations for modeling real-time systems, in this article, we provide a concrete periodic task scheduling example in a RTOS. Our goal is to determine how useful UML designing real-time task schedulability is [Cottet02]. 2 REAL-TIME SCHEDULING The scheduler is the part of the operating system that responds to the requests sent by programs, interrupts and gives control of the processor to those processes. It is the component that implements the scheduling algorithms and can also stand alone to act as a centerpiece to a program that requires moderation among many different concurrent tasks. In this working-mode, each task that a program must accomplish is written so that it can be called by the scheduler as necessary. Tasks can be ranked in priority, allowing the scheduler to hand control of the processor to each process in turn. The major factors that affect real-time system schedulability include [Saiedian04]:
Due to the necessity of considering the schedulability analysis as early as possible in software development, its integration with the industry UML standard (schedulability analysis can be integrated with object-oriented design) and its schedulability extension (UML Profile for Schedulability, Performance, and Time) is a very important issue, because it may allow to detect unfeasible real-time architectures at an early stage of development, preventing costly design mistakes, accelerating development schedules and allowing developers to verify the real-time performance of the design throughout the software lifecycle [Martins03]. Real-time task model
Also, when tasks are allowed to access shared resources, their access needs to be controlled in order to maintain data consistency.
Fixed-priority algorithm:
Rate Monotonic Priority inversion Priority inversion is the phenomenon that causes a high priority task to be delayed indefinitely while awaiting a resource that has been held by a low priority task. The low priority task is often unable to run due to the presence of an unrelated medium priority task. In the situation that results, one finds that the high priority task is effectively denied the CPU because of the lower medium priority task. In order to prevent the priority inversion phenomenon, the priority inheritance protocol can be applied. The basic idea is to dynamically change the priority of some tasks. So a task ti, which is using a critical resource inside a critical section, gets the priority of any task tj waiting for this resource whenever the priority of task tj is higher than that of task ti. 3 REAL-TIME UML The UML Profile for Schedulability, Performance, and Time uses stereotypes, tagged values, and constraints with specific names. Although the UML Profile for Schedulability, Performance, and Time predefines a number of stereotypes, tagged values and constraints, the user is free to add more, whenever it clarifies of simplifies the analysis and design models. The stereotypes may extend one or more classes through extensions as part of the profile, and enables the use of domain specific terminology or notation. Stereotypes may clarify the model to domain experts trying to construct or understand the system. However, stereotypes are more useful when they contain special values that apply to that kind of stereotype: tagged values. A tagged value is a property name-value pair and provides the definition of the kind of information added to the stereotype. A constraint is a user-defined rule or rule of correctness. We use constraints to express restrictions that make sense in our particular domain. UML dynamic modeling Sequence diagrams emphasize message sequence, so the next message in time is the message following the current one on the diagram. Time goes down the page, but usually linearity is no implied; that is, further down implies later in time, but the same distance at different places in the diagram does not imply the same amount of time. Also, messages on sequence diagrams are only partially ordered, so in many cases the relative timing between messages is not specified. Sequence diagrams support concurrent semantics, which means that the relative ordering of some messages is not specified; we would expect that, if one event (such as sending or receiving a message) is marked below another one in the diagram, then the second one comes after the first one in absolute time, but this is true only if both events belong to the same lifeline, not if they belong to different lifelines; therefore, when messages begin on different lifelines, we cannot know which one is first in time; and, if messages terminate on different lifelines, we cannot assume that they are received in the same sequence as they are depicted, even when they are sent in that particular sequence. Timing diagrams were not included in UML 1.x., even though electrical engineers have used timing diagrams for a long time in the design of electronic state machines. A timing diagram is a simple representation with time along the horizontal axis and object state or attribute value along the vertical axis. However, timing diagrams are different from statecharts, even though we can see the change in state of the different lifelines, because statecharts specify all the reactive behavior of the classifier it is specifying, but not a particular scenario. In UML 2.0, they are used to show interactions when a primary purpose of the diagram is to reason about time. Since timing diagrams are shown against a common clock (depicted with the time ruler on the diagram), messages on timing diagram are fully ordered. Run-to-completion
semantics 4 CASE STUDY: TASK
SET SCHEDULING SHARING A CRITICAL RESOURCE
In order to describe in more detail this task
set and the critical sections of task ?1 and ?3, we add new parameters
that specify the three components of
Table 1. Case study: a task set sharing a critical resource According to the RM algorithm, where tasks with shorter periods get higher priorities, task receives the highest priority and task the lowest one. For simplicity, we have been considered UML run-to-completion semantics for each event consumption. The schedule obtained under the RM algorithm is illustrated in Figures 2 and 3 using a UML 2.0 sequence diagram and a UML 2.0 timing diagram, respectively.
Figure 2. Sequence diagram showing the example task set accordingly to the RM scheduling Analyzing the sequence diagram, we can stereotype this diagram as <<SAsituation>> to use it in the context of schedulability analysis, representing a real-time situation. In UML 2.0, the notation for an interaction in a sequence diagram is a solid-outline rectangle (a rectangular frame). The five sided box at the upper left hand corner names the sequence diagram: keyword sd followed by the interaction name, “RM Scheduling”1. Each lifeline in the diagram represents an individual participant in the scenario:
In the general resource modeling of the UML Profile for Schedulability, Performance, and Time, an action is defined as a kind of scenario. Therefore, we use the stereotype <<SAaction>> of this profile (schedulability modeling) to characterize the behavior of each task in our model (we had to add some tags that there were not present in the <<SAaction>> stereotype of the schedulability model):
We use the new metaclass in UML 2.0, TimeObservationAction, to know when a task awakes. A time observation action is an action that, when executed, returns the current value of time in the context in which it is executing. It is depicted with the keyword “now”. A time observation action lets us determine the absolute deadline that each task has to meet, shown in the diagram with time constraints. We use also the new metaclass in UML 2.0, StateInvariant, to show the different states associated to each lifeline as restrictions. A state invariant is a constraint on the state of a lifeline, and this constraint is evaluated during runtime. If the constraint is true the trace is a valid trace. It is a possible way to show the state value of a lifeline in the sequence diagram. For instance, the state of the resource r1 has to be “Busy” if we want to release it. Finally, we use notes to display the textual information that we want to emphasize. It is assumed that the task set is schedulable because there is not any element indicating a timing fault (i.e., the tasks do not miss their deadlines), but it is difficult to check by simple inspection of the diagram. Figure 3 illustrates the timing diagram for the proposed scheduling. We have represented a longer period of time than in sequence diagram spanning over several scheduling cycles.
Again, we stereotype the diagram <<SAsituation>>
to use it in our context of schedulability analysis. The notation
of the rectangular frame and the five sided box is the same as in
the previous sequence diagram, but now we have different elements
in the model. We generate the diagram with four lifelines: the resource
(r1) and the three tasks ( Task states used in the timing diagram are explained in Table 2. The resource lifeline has two simple states, idle or busy. The timing diagrams let us see how the states change over time for each lifeline and it is very useful in scheduling. Therefore, we do not need to use the metaclass StateInvariant as a restriction in lifelines to know the state value at a particular time. The time axis is linear so it clarifies absolute timing of events, state changes and relative timing between the different lifelines. Therefore, we do not need to use notes indicating when a task awakes (when the state of a task changes to “Ready”), and we do not need the stereotype <<SAaction>> representing the length of time in different actions as in the sequence diagram, because we can use the time axis to know it (we only use the stereotype <<SAaction>> to characterize the task set parameters). We use notes to emphasize some aspects of the schedule,
for instance, when task Once more, we use the metaclass TimeObservationAction to control when a task awakes, and we use this time value to set the constraints (task deadlines). Now, since we have the time along the horizontal axis, we can check the scheduling and see that the schedule is feasible or not.
Table 2. Task states For our purpose, the timing diagram view is probably more adequate than the sequence diagram view, but the last one offers another point of view which is quite interesting as well. It is therefore better to use the two diagrams in order to have both views. However, even after having modeled and understood the schedule with the two diagrams, we can not assure that the schedule is feasible, i.e., the two diagrams themselves are not sufficient for deciding if the task set is schedulable or not: we do not know if we will have enough resources to perform the schedule (available processor, memory space...), and we should apply the mathematical feasibility model [Cottet02] to the diagrams. Since, in our case study, the tasks are not independent, then we have to consider a task set sharing resources. Thus, we have to calculate the worst-case response time for each task by including the blocking delay (assessment of a task response time): the utilization factor of the processor has to be low enough to let the task set to be scheduled, whatever the blocking time due to the shared resources 5 CONCLUSIONS With respect to real-time systems, UML 2.0 has introduced options to manage the complexity of interactions and, relating to time, the new type of diagram, timing diagram, provides an expressive way to detail change in value or state of the different classifiers and attributes. UML and the UML profile for Schedulability, Performance, and Time allow models where information related to time aspects may be annotated. Thus, software engineers may be able to specify and design their real-time systems with UML models which could be the formal description of the system, so that the different models could be analyzed in order to assure that they accomplish all the properties needed in the system. Timing diagrams and sequence diagrams are the two kinds of interaction diagram more adequate to model task scheduling. Thus, we recommend to use both diagrams when analyzing schedulability. A timing diagram is similar to a sequence diagram in that they both show scenarios of collaborations, but they are not the same at all. Although timing diagrams do not show any information beyond that available in annotated sequence diagrams, the absolute timing of events, state changes and the relative timing among the lifelines is clearer and more readable than on sequence diagrams, even when explicit timing constraints are added. Since deadlines are of critical importance, as opposed to message sequence, we think that perhaps it is therefore better to use timing diagrams instead of sequence diagrams. However, each diagram provides different points of view to the same scenario and both could be very useful. However, although the resulting models are quite complete and facilitate communication and understanding, the diagrams themselves are not sufficient to indicate if we have a feasible schedule. We would need to apply the mathematical feasibility model to the UML diagrams. Also, as we mentioned before, since the UML profile for Schedulability, Performance, and Time is clearly biased towards rate monotonic analysis, it would be interesting to extend the specification to comprise cyclic scheduling. Static cyclic scheduling is easier to implement and will be sometimes more efficient than fixed priority scheduling, for instance, for control related tasks with strict requirements on small timing variations: reaching the same performance level with fixed priority scheduling may require higher sampling rates or more sophisticated control algorithms. Event handling could be another example where static cyclic scheduling should be recommended [Lonn99], [Drapper99]. Footnote: 1 The notation within this rectangular frame comes in several forms depending on the specific diagram: sequence diagram, communication diagram (which was known as collaboration diagram in UML 1.x), interaction overview diagram (new in UML 2.0) and timing diagram (new in UML 2.0) 2 A broker is an instance of a run-time entity responsible for controlling access to the exclusive services of a resource. REFERENCES [Bj?rkander03] M. Bj?rkander, C. Kobryn: “Architecting Systems with UML 2.0”. IEEE Computer Society, IEEE Software. 2003. [Cottet02] F. Cottet, J. Delacroix, C. Kaiser, Z. Mammeri: “Scheduling in real-time systems”. John Wiley & Sons. 2002. [Douglass98] B. P. Douglass: “Real-Time UML.Developing Efficient Objects for Embedded Systems”. Addison-Wesley. 1998. [Douglass98b] B. P. Douglass: “Designing Real-Time Systems with UML”. Embedded Systems Programming. 1998. [Douglass04] B. P. Douglass: “Real Time UML. Advances in The UML For Real-Time Systems”. Addison-Wesley. Third Edition. 2004. [Drapper99] D. Draper, A. K. Jónsson, D. P. Clements, D. Joslin: “Cyclic Scheduling”. In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Morgan Kaufmann Publishers Inc. 1999, pp. 1016-1021. San Francisco CA, USA. [Fowler03] M. Fowler: “UML Distilled. A Brief Guide to the Standard Object Modeling Language”. Addison-Wesley. Third Edition. 2003. [Gomaa00] H. Gomaa: “Designing Concurrent, Distributed, and Real-Time Applications with UML”. Addison-Wesley. 2000. [Jigorea00] R. Jigorea, S. Manolache, P. Eles, Z. Peng: “Modelling of Real-Time Embedded Systems in an Object-Oriented Design Environment with UML”. 2nd ARTES Graduate Student Conference. Chalmers University of Technology, G?teborg (Sweden). March 2000. [Küster01] J. M. Küster, J. Stroop: “Consistent Design of Embedded Real-Time Systems with UML-RT”. 4th IEEE International Symposium on Object Oriented Real-Time Distributing Computing ISORC 2001. Los Alamitos, CA, USA, IEEE Computer Society 2001, pp. 31-40 Conference Paper. [Lavazza01] L. Lavazza, G. Quaroni, M. Venturelli: “Combining UML and Formal Notations for Modelling Real-Time Systems”. Software Engineering Notes, vol. 26, no. 5, pp. 196-206, September 2001. [Liu73] C. L. Liu, J. W. Layland: “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment”. Journal of the ACM, vol. 20, no. 1, pp. 46-61, January 1973. [Lonn99] H. Lonn, J. Axelsson: “A Comparison of Fixed-Priority and Static Cyclic Scheduling for Distributed Automotive Control Applications”. In Proceedings of the 11th Euromicro Conference on Real-Time Systems (ECRT99). York, England. 1999. [Martins03] P. Martins: “Integrating Real-Time UML Models with Schedulability Analysis”. White Paper in Tri Pacific Software Products 2003. [Saiedian04] H. Saiedian, S. Raguraman: “Using UML-Based Rate Monotonic Analysis to Predict Schedulability”. IEEE Computer Society, vol. 37, no. 10, pp. 56-63, October 2004. [Selic98] B. Selic, J. Rumbaugh: “Using UML for Modeling Complex Real-Time Systems”. White Paper, published by ObjecTime Limited, 340 March Rd., Kamata, Astario, Canada. 1998. [UML03] UML 2.0 Superstructure Specification. August 2003, ptc/03-08-02. Unified Modeling Language Infrastructure Specification, September 2003, ptc/03-09-15. http://www.omg.org/. [UMLSPT03] UMLTM Profile for Schedulability, Performance, and Time Specification. January 2005, version 1.1, formal/05-01-02. http://www.omg.org/. About the authors Cite this article as follows: Maricruz Valiente, Gonzalo Genova, Jesus Carretero: “UML 2.0 Notation for Modeling Real-Time Task Scheduling”, in Journal of Object Technology, vol. 5, no 4, May-June 2005, pp. 91-105 http://www.jot.fm/issues/issue_2006_05/article2 |
,
and
. 
:task duration before entering the critical section. 
:critical
section duration. 
:task
duration after the critical section. 
Maria
Cruz Valiente is a PhD researcher and teaching assistant in the
Department of Informatics at the Carlos III University of Madrid.
Her research in Information Engineering Group is focused on domain
analysis and modeling, and modeling methods in software engineering.
Gonzalo
Genova is an Associate Professor of Software Engineering in the
Department of Informatics at the Carlos III University of Madrid.
His main research subjects, within the Information Engineering Group
and in close cooperation with The Reuse Company, is modeling and
modeling languages in software engineering, as well as requirements
engineering.
Dr. Jesus
Carretero is a professor in the Department of Informatics at the
Carlos III University of Madrid. His research interests include
parallel and distributed systems and real time systems.