A SystemC-Based RTOS Model for Multiprocessor Systems-on-Chips: Part 2 - Uniprocessor Systems - Embedded.com

A SystemC-Based RTOS Model for Multiprocessor Systems-on-Chips: Part 2 – Uniprocessor Systems

Following the discussion in Part 1 on basics andterminology, in this part in this three part series we present thebasics of uniprocessor scheduling, which are the prerequisites forunderstanding multiprocessor scheduling.

We will describe how a uniprocessor system may be modeled usingSystemC and, in particular, compare two widely used on-line schedulersfor uniprocessor scheduling; RMS and EDF.

Our basic system model consists of three types of components: task, RTOS, and link, with thelink providing communication between the tasks and the RTOS. Here wepresent the scheduling service of the RTOS model, and later extend theRTOS service model to include synchronization and resource allocation.

Tasks can send the messages (ready and finished) to the scheduler,which, in turn, can send one of the three commands to the tasks (run,preempt, and resume). We start by describing how each of the threecomponents and their interactions can be modeled in SystemC.

Link Model
The communication between the tasks and the scheduler is modeled as twochannels: one to send messages from the tasks to the scheduler and oneto send commands from the scheduler to the tasks, as illustrated in Figure 10-3 in Part 1.

Our objective is to develop a convenient way to add tasks andschedulers to the system without having to create separatecommunication channels for each task/scheduler communication, i.e., newtasks and/or schedulers should be added by creating and connectingthem.

The Master-Slave library of SystemC provides an elegant solution tothis problem. The sc_link_mp component is a high-level implementationof a channel, providing a bus-like functionality, i.e., allowing thescheduler to communicate with n tasks through a single port, butwithout the complexity of a bus cycle-accurate implementation.

For each master port on one side of the link, there has to be atleast one slave port on the other side. In our model, we have multiplemaster ports connected from the tasks to the slave port in thescheduler through link1 and multiple master ports on the schedulersconnected to the slave port in the tasks through link2.

From the Master-Slave library, we use the in-lined executionsemantics (Remote Procedure Call) of the sc_link_mp channel. Here, aslave method executes in line with the caller process and returns tothe caller after execution. The caller invokes the slave by writing adata value of type message_type to its master port.

In our model, each of the tasks and the scheduler have a master portand a slave port, whereby each task writes messages to its master portinvoking the slave method of the scheduler, and the scheduler writescommands to its master port invoking the slave method of each task(Fig. 10-3).

If two tasks (or schedulers in a multiprocessor system) try to senda message at the same time, there will be two master ports writing tothe same slave port of the scheduler.

This is handled by the sc_link_mp as follows: two concurrentprocesses accessing the same link over the master ports access the linkin a sequential but undetermined order. This allows the abstraction ofany relationship of simultaneity between the two concurrent processes.

The sc_link_mp object does not provide built-in arbitration orprivatization functions. It is a primitive (atomic) object that allowsabstraction of such refinements. If any arbitration is needed, it hasto be implemented in the channel interface.

In our model, we do not use explicit arbitration; it is implicit inthe behavior. This means that the scheduler just handles one request ata time (in real time), giving the feeling of arbitration at the time ofsimulation and making the implementation of a scheduler more intuitive,i.e., it is written as one would write the scheduling algorithm inpseudo-code.

Task Model
At the system level, we are not interested in how a task isimplemented, i.e., its exact functionality, but we need informationregarding the execution of the task, such as the WCET (wcet i ),BCET(bcet i ), context switching overhead (csw i ),period (T i ), deadline (d i ),and offset (o i ), in order to characterize theexecution of the task.

Periodic Tasks. The behavior of a periodic task is modeled as a finite state machine(FSM) with four stages: idle, ready, running, and preempted, asillustrated in Figure 10-5 below.

We assume that all the tasks start in the idle state with a certainoffset that can have any value including zero, in which case, the taskgoes immediately to the ready state, sending a ready message to thescheduler and waiting for the RTOS to issue a run command.

Figure10-5.

The task stays in the ready state until it receives a run commandfrom the scheduler. It then goes to the running state, where it countsthe number, c running , of cycles. When entering therunning state,crunning is initialized to the value of the task execution time e i .When c running = = 0 , the task has finished itscomputation.

It then issues a finished message to the scheduler and goes to theidle state. In all states, c period is decremented each cycle.Afterreaching the idle state, the task stays there until c period = = 0 ,indicating the start of a new period by making a transition to theready state and setting c period = T i .

For preemptive scheduling policies, the task may be preempted by thescheduler at any time during the running state, i.e., the schedulersends a preempt command to the task. When preempted, the task goes intothe preempted state, where it waits for a resume command from thescheduler. During the preempted state, only c period is updated.

The task model is implemented in SystemC using three processes. Thebasic code elements of the header file are outlined in Figure 10-6 below.

Figure10-6.

The SC_SLAVE(get_comm_from_scheduler, in_command) process takes careof commands from the scheduler and, based on these, determines whatshould be the new state of the task, i.e., new_state. The processSC_METHOD(update_state), updates the actual state of the task (state)on the rising edge of the clock, i.e., when a cycle has been completed.

It then notifies the process SC_METHOD(new state), by issuing anevent (newStateEvent) that immediately triggers the methodSC_METHOD(new state), i.e., it does not have to wait for the abstracttime to advance. An interesting feature of this model is that, within asingle cycle, the state of a task may change several times.

The state changes during a cycle are handled by updating a localvariable, new_state. At the next clock tick, when the system is stable,it is the last updated state value that determines the new state of thetask. By this way of modeling, we avoid any dependency on thesequencing of concurrent messages sent to the scheduler.

Aperiodic andSporadic Tasks. In contrast to the periodic tasks, an aperiodictask executes at irregular intervals and has only a soft deadline. Inother words, the deadlines for aperiodic tasks are not rigid, butadequate response times are desirable. For example, an aperiodic taskmay process user input from a terminal. A sporadic task is an aperiodictask with a hard deadline and minimum interarrival time.

The aperiodic and sporadic tasks are modeled in the same way as theperiodic task, i.e., a four-state FSM implemented by three processes inSystemC, one for handling the FSM, a second receiving the commands fromthe schedulers and updating the next_state variable, and a third onesensitive to the clock edge, setting the new state of the FSM.

The major difference is that the period counter, cperiod, is changedto an interval counter, which models the time to the next execution ofthe task. The value of the interval counter, which is based on randomnumbers (or by an event sequence provided by the user), is calculatedevery time the task finishes its previous execution.

Scheduler Model
From a system point of view, the major job of the RTOS is to determinethe execution order of the tasks, i.e., to perform task scheduling. Thescheduler maintains a list of tasks ready to be executed. In our model,the list is a priority queue in which each task is given a priorityaccording to the scheduling policy of the scheduler.

For example, for the RMS, the task priority is based on the periodof the task, whereas for the deadline monotonic scheduling (DMS) andthe EDF scheduling, the task priority is based on the task's deadline.In the following, we use p(t i ) to denote the priority of task t i .

The scheduler is modeled as an event-based process that runswhenever a message (ready or finished) is received from a task. In thecase of a finished message received from a task t i , the schedulerselects, among the ready tasks, the one with the highest priority, t j ,and issues the command run to t j .

In the case of an empty list and no running task, the scheduler justwaits to receive a ready message. As soon as it receives this message,it issues a run command to the task, t i , which issuedthe readymessage. If the list is empty, but a task, t k , is currently running,then:

If the list is not empty, ti is only executed if it has the highestpriority; otherwise the task, tj ,with the highest priority isselected.

The scheduler is designed to service several messages in zerosimulation time. When two or more different tasks send a ready messagesimultaneously to the scheduler in the same simulation cycle, thescheduler will choose the task with the highest priority to run andenqueue the others. This is handled by the Master-Slave library and theSystemC simulation kernel. Tasks are actually served sequentiallyduring the simulation cycle.

Rate Monotonic Scheduling
In the case of RMS, the list is a priority queue, and each task isgiven a unique priority based solely on the period of the task, i.e.,it is independent of e i . The task withthe shortest period gets thehighest priority. The priority scheme is fixed, meaning that it isdetermined at compile time and is known to be optimal.

Let p( ti ) be the priority of the task ti .RMS assumes that tasks areindependent and that they can be preempted. Furthermore, deadlines areequal to the period, and the context switching overhead is ignored.

The implementation of the RM scheduler is rather straightforward. Figure 10-7 below shows the SystemCcode for the RMS algorithm, in which ti is the task sending the messagereceived through in_message,  tj isthe task with the highest priorityfrom the priority queue, Q, of tasks that are ready to be executed, andtk is the currently running task.

Figure10-7.

The scheduling algorithm is executed within a slave process, i.e.,it is executed every time the scheduler receives a message on its inputslave port. In line 2 the received message is set to task followedin line 3 by a check, which indicates whether the received message wasactually meant for the scheduler. If a ready message is received (line4), ti is placed in the priority queue(line 5).

If a finished message is received, the currently running task, tk ,is marked as not running (line 6). The scheduler is now ready to decidewhich task to execute. In line 9, tj is set to the highest prioritytask (note that this may be ti ).

If the queue does contain tasks, which is checked in line 10, andthere is a task currently running (line 11), it is checked if therunning task should be preempted (line 12). In the case of preemption,the running task is stopped (line 13) and the new task is started (line15).

In line 14, the new task is set to the currently running task. Ifthe running task should not be preempted, it is just left running (line16). In the case of no currently running task, the highest prioritytask from the queue is started (lines 18, 19). Finally, if the queue isempty, a situation that is only possible when a finished message isreceived, the scheduler does nothing.

Example 1. Consider a task set:

with no dependencies. An important issue in real-time schedulingis that we have to guarantee that all tasks meet their deadlines,independent of the order of their release. The critical instance of atask occurs when the task and all the higher priority tasks arereleased simultaneously. Hence, the worst-case scenario is when alltasks are released at the same time, for example, at time zero. Table 10-1 below shows the periods,priorities, and execution times (WCET) for the three tasks.

Table10-1.

Figure 10-8 below showsthe activities for each task. All three tasks are released at time 0.As t3 has the highest priority, it starts executing immediately,whereas t2 and t1 are preempted. After 10 cycles, t3 finishesexecution, and t2 starts executing, whereas t1 is still preempted.

Figure10-8.

After 30 cycles, t1 has been running for 10 cycles (its WCET is12 cycles). At this point, t3 becomes ready again as its period of 30cycles is repeating. As t3 has higher priority than t1, t1 is preemptedand t3 is executed. After 50 cycles, both t3 and t2 have been executedtwice, whereas t is still missing the last two cycles of its firstrun. Since the period (and hence deadline) of t2 is 50 cycles, itmisses its deadline.

Figure 10-9 below showsthe schedule of Figure 10-8 as a waveform produced by simulating themodel. The numbers in the waveform correspond to the various states ofthe task, i.e., 0 = idle, 1 = ready, 2 = running, and 3 = preempted.

Figure10-9.

EarliestDeadline First Scheduling. Another popular scheduling policy isthe EDF scheduling. This is a dynamic priority assignment schemewhereby priorities are changed during execution, based on the releasetimes. Tasks are prioritized according to their deadline such that thetask with the closest deadline gets the highest priority.

Our model can handle both static and dynamic priority policies. Bothapproaches follow the above-mentioned algorithm, in which the model forhandling dynamic priorities has an extra method that is sensitive tothe global clock. At each clock cycle, the priority of the currentlyrunning task, p(?k), is updated as well as the priorities of the tasksin the ready queue.

For the simplest case of EDF scheduling, the task priority isincremented by one at each clock cycle. For the static approaches,there is no need for this extra method as the priority scheme is fixed,i.e., it is determined at compile time.

Example 2. Figure 10-10 below shows the result ofscheduling Example 1 using the EDF scheduling algorithm.

Figure10-10.

Synchronization Model
Another of the basic services provided by an RTOS is synchronizationamong cooperative tasks that are running in parallel. Thissynchronization enables the simulator to model a real-time system withdata dependencies among tasks. For example, if ti needs data computedby tj, then ti has to wait until the completion of tj in order toexecute.

Task dependencies can be of various types, but, at the system level,we do not care about the nature of a dependency. We can formulate anabstraction and assert that the task tj is eligible to be released justafter the task ti has finished its execution.

As we have designed our framework to support multiprocessorplatforms, the synchronizer handles intra- and interprocessordependencies as well as multirate systems.

A synchronization protocol governs how the tasks are released forexecution such that their precedence constraints are satisfied. One ofthe more commonly used synchronization protocols is the directsynchronization (DS) protocol. According to this protocol, when aninstance of a task completes, a synchronization signal is sent to theprocessor, where its immediate successor executes, and an instance ofits immediate successor is released immediately.

In our implementation of the DS protocol, the synchronizer can beseen as a “message filter” between the tasks and the schedulers,letting other schedulers know when a task is “really ready,” i.e., whenits dependency constraints have been resolved. The finished messagewill always pass, but the ready message will pass only when thedependency constraints have been resolved.

Each time a task issues a ready or a finished message, that messageis passed to the synchronizer. If the synchronizer receives a readymessage, it searches its dependency_database to check whether the taskissuing that message is dependent on any other task.

If so, the synchronizer checks the finished_task_list to see whetherthe dependent task has already finished its execution. If it has, thedependent task is erased from the finished_task_list, and the readymessage is passed to the scheduler; otherwise, the information aboutthe task issuing the ready message is stored in the waiting_dep_list.

If the synchronizer receives a finished message, it searches itsdependency_database to check whether the task issuing that message hasany other task dependent on it. If so, it scans the waiting_dep_list tosee if that dependent task is ready to execute. If it is, the taskwaiting for the resolution of dependency is released to its schedulerfor execution, but if it is not ready to execute, the information aboutthe task issuing the finished message is stored in thefinished_task_list.

Some synchronization protocols may require more complex modeling,whereas for others (e.g., if multirate is not needed) a simpler modelwould be enough. The use of the data structures is determined by thesynchronization protocol; for this, the synchronization model definesstandard interfaces to the data structures in order to separate thefunctionality of the model from the functionality of the datastructures.

This allows for change in the synchronization protocol without theneed to modify the functionality of the data structures. Othersynchronization protocols reported in the literature are the phasemodification (PM) protocol and the release guard (RG) protocol, whichhave been proposed elsewhere which can also be modeled in SystemC andused in our framework.

Resource Allocation Model
In an embedded real-time system, we often find a number ofnon-preemptable resources used by a number of tasks. For example, wecan have several concurrent tasks competing for the utilization of ashared memory unit, which, in principle, is a non-preemptable resource.Resource allocation is a basic service provided by the RTOS thatcoordinates access to the resources in a real-time system.

In a real-time system, the lack of a proper resource allocationmechanism can result in the phenomena of priority inversion anddeadlocks which lead to timing anomalies (unpredictable timingbehavior). Therefore, a resource access control protocol is needed tokeep the duration of each priority inversion and hence keep theblocking times of the tasks bounded.

For a uniprocessor system, priority inheritance protocols have beendeveloped elsewhere as well a priority ceiling protocol (PCP).developed the stack-based protocol (SBP) has also been developedelsewhere which gives the same upper bound on the blocking time of eachtask as with the PCP. In addition, the SBP is applicable to bothstatic- and dynamic-priority scheduling policies.

In our model, the resource allocator implements the priorityinheritance protocol for allocating the resources requested by thetasks. The priority inheritance protocol ensures that, in the absenceof deadlocks, no task is ever blocked for an indefinitely long timebecause an uncontrolled priority inversion cannot occur.

When a task requires a resource, it sends a request message to theallocator, which issues either a grant message to the scheduler if therequested resource is available or a refuse message if it is not. Inboth cases, the priority of the task requesting the resource is updatedin accordance with the priority inheritance protocol and is notified tothe scheduler by an updatePriority message.

In a similar way, when a task has occupied a resource for itsdesignated duration, it sends a release message to the allocator, whichupdates its resource database and issues an updatePriority message tothe scheduler as demanded by the priority inheritance protocol.

Next, in Part 3: Mulitprocessor Systems
To read Part 1, go to: Basicconcepts and terminology

This series of articles is based oncopyrighted material submitted by Jan Masden, Kashif Virk and MercuryJair Gonzalez to “MultiprocessorSystems-On-Chips,” edited by Wayne Wolf and Ahmed Amine Jerraya. Itis used with the permission of the publisher, Morgan Kaufmann, animprint of Elsevier. The book can be purchased on-line.

Ahmed Jerraya is researchdirector with CNRS and is currently managing research on multiprocessorsystem-on-chips at TIMA Laboratory in France. Wayne Wolf is currently the GeorgiaResearch Alliance Eminent Scholar holding the Rhesa “Ray” S. Farmer,Jr. Distinguished Chair in Embedded Computer Systems at Georgia Tech'sSchool of Electrical and Computer Engineering (ECE). Previously aprofessor of electrical engineering at Princeton University, he workedat AT&T Bell Laboratories.

JanMadsen is professor of computer based systems at the Departmentof Informatics and Mathematical Modeling at the Technical University ofDenmark where he heads the System-On-Chip Design Group.

KashifVirk works for Jan Masden in preparation for a doctorate. Hehas a B.Sc. in Electrical Engineering from the University ofEngineering and Technology, Lahore, Pakistan and an M.Sc. from theTechnical University of Denmark.

Mercury JairGonzalez is a design engineerat the Semiconductor Technology Center of CINVESTAV in Mexico. Hisresearch interests are VLSI design methods, MP SoC design methods, andthe timing analysis of real-time systems.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.