|
Message
From: cvs at opencores.org<cvs@o...>
Date: Sat Aug 25 20:03:52 CEST 2007
Subject: [cvs-checkins] MODIFIED: jop ...
Date: 00/07/08 25:20:03 Added: jop/doc/book/runtime rt_user_interaction.pdf rt_intro.tex
rt_profile.tex rt_user.tex
Log:
Handbook update
Revision Changes Path
1.1 jop/doc/book/runtime/rt_user_interaction.pdf
http://www.opencores.org/cvsweb.shtml/jop/doc/book/runtime/rt_user_interaction.pdf?rev=1.1&content-type=text/x-cvsweb-markup
<<Binary file>>
1.1 jop/doc/book/runtime/rt_intro.tex
http://www.opencores.org/cvsweb.shtml/jop/doc/book/runtime/rt_intro.tex?rev=1.1&content-type=text/x-cvsweb-markup
Index: rt_intro.tex
===================================================================
A Java processor alone is not a complete JVM. This chapter describes
the definition of a real-time profile for Java and a framework for a
user-defined scheduler in Java. It concludes with the description of
the JVM internal data structures to represent classes and objects.
1.1 jop/doc/book/runtime/rt_profile.tex
http://www.opencores.org/cvsweb.shtml/jop/doc/book/runtime/rt_profile.tex?rev=1.1&content-type=text/x-cvsweb-markup
Index: rt_profile.tex
===================================================================
\section{A Real-Time Profile for Embedded Java}
\label{sec:rtprof}
As standard Java is under-specified for real-time systems and the
RTSJ does not fit for small embedded systems a new and simpler
real-time profile is defined in this section and implemented on JOP.
The guidelines of the specification are:
\begin{itemize}
\item High-integrity profile
\item Easy syntax, simplicity
\item Easy to implement
\item Low runtime overhead
\item No syntactic extension of Java
\item Minimum change of Java semantics
\item Support for time measurement if a WCET analysis tool is not available
\item Known overheads (documentation of runtime behavior and memory
requirements of every JVM operation and all methods have to be
provided)
\end{itemize}
The real-time profile under discussion is inspired by the restricted
versions of the RTSJ described in \cite{Pusch01} and \cite{583825}
(see Section~\ref{subsec:restr:rtsj}). It is intended for
high-integrity real-time applications and as a test case to evaluate
the architecture of JOP as a Java processor for real-time systems.
The proposed definition is not compatible with the RTSJ. Since the
application domain for the RTSJ is different from high-integrity
systems, it makes sense for it \emph{not} to be compatible with the
RTSJ. Restrictions can be enforced by defining new classes (e.g.\
setting thread priority in the constructor of a real-time thread
alone, enforcing minimum interarrival times for sporadic events).
%Hardware interrupts, that are usually handled by device drivers, are
%part of this profile. These interrupts are mapped to events and
%scheduled in the same way as application threads. This feature
%allows priority assignment to the device drivers and the execution
%time can be incorporated in the schedulability analysis with normal
%tasks. This solution also avoids problems with preemption latency
%caused by device drivers.
All hardware interrupts are represented by threads under the control
of the scheduler. With this solution, a priority is assigned to the
device drivers and the execution time can be incorporated in the
schedulability analysis with normal tasks. This solution also avoids
problems with preemption latency provoked by device drivers. One
example of this problem is the \emph{caps-lock} issue in Linux
\cite{REDLinux2003}: A device driver performs a spinlock wait for
keyboard acknowledgement and produces preemption latency up to
9166$\mu$s. With the proposed concept of hardware interrupts under
scheduler control, a lower assigned priority to such a device driver
avoids preemption delays of \emph{more important} real-time threads
and events.
%This specification is functional compatible with Ravenscar-Java (RJ)
%\cite{583825}, but avoids inheritance of complex RTSJ classes. In
%fact, it is possible (and has been done) to implement RJ with the
%additional necessary RTSJ classes on top of it.
To verify that this specification is expressive enough for
high-integrity real-time applications, Ravenscar-Java (RJ)
\cite{583825} (see Section~\ref{subsec:rj}), with the additional
necessary RTSJ classes, has been implemented on top of it. However,
RJ inherits some of the complexity of the RTSJ. Therefore, the
implementation of RJ has a larger memory and runtime overhead than
this simple specification.
\subsection{Application Structure}
The application is divided in two different phases:
\emph{initialization} and \emph{mission}. All non time-critical
initialization, global object allocations, thread creation and
startup are performed in the initialization phase. All classes need
to be loaded and initialized in this phase. The mission phase starts
after invocation of \code{startMission()}. The number of threads is
fixed and the assigned priorities remain unchanged. The following
restrictions apply to the application:
\begin{itemize}
\item Initialization and mission phase
\item Fixed number of threads
\item Threads are created at initialization phase
\item All shared objects are allocated at initialization
\end{itemize}
\subsection{Threads}
Concurrency is expressed with two types of \emph{schedulable
objects}:
\begin{description}
\item[Periodic activities] are represented by threads that execute
in an infinite loop invoking \code{waitForNextPeriod()} to get
rescheduled in predefined time intervals.
\item[Asynchronous sporadic activities] are represented by event
handlers. Each event handler is in fact a thread, which is released
by an hardware interrupt or a software generated event (invocation
of \code{fire()}). Minimum interarrival time has to be specified on
creation of the event handler.
\end{description}
%
The classes that implement the \emph{schedulable objects} are:
%
\begin{description}
\item[RtThread] represents a periodic task. As usual task
work is coded in \code{run()}, which gets invoked on
\code{missionStart()}. A scoped memory object can be attached to an
\code{RtThread} at creation.
\item[HwEvent] represents an interrupt with a minimum
interarrival time. If the hardware generates more interrupts, they
get lost.
\item[SwEvent] represents a software-generated event.
It is triggered by \code{fire()} and needs to override
\code{handle()}.
\end{description}
%
Listing~\ref{lst:arch:rt:profile:schobj} shows the definition of the
basic classes.
\begin{lstlisting}[float,caption={Schedulable objects},
label=lst:arch:rt:profile:schobj,{emph=RtThread,enterMemory,
exitMemory,run,waitForNextPeriod,startMission,HwEvent,handle,
SwEvent,fire,handle}]
public class RtThread {
public RtThread(int priority, int period)
public RtThread(int priority, int period, int offset)
public RtThread(int priority, int period, Memory mem)
public RtThread(int priority, int period, int offset,
Memory mem)
public void enterMemory()
public void exitMemory()
public void run()
public boolean waitForNextPeriod()
public static void startMission()
}
public class HwEvent extends RtThread {
public HwEvent(int priority, int minTime, int number)
public HwEvent(int priority, int minTime, Memory mem,
int number)
public void handle()
}
public class SwEvent extends RtThread {
public SwEvent(int priority, int minTime)
public SwEvent(int priority, int minTime, Memory mem)
public final void fire()
public void handle()
}
\end{lstlisting}
Listing~\ref{lst:arch:rt:profile:example} shows the principle coding
of a worker thread. An example for creation of two real-time threads
and an event handler can be seen in
Listing~\ref{lst:arch:rt:profile:usage}.
\subsection{Scheduling}
The scheduler is a preemptive, priority-based scheduler with
unlimited priority levels and a unique priority value for each
schedulable object. No real-time threads or events are scheduled
during the initialization phase.
The design decision to use unique priority levels, instead of FIFO
within priorities, is based on following facts: Two common ways to
assign priorities are rate monotonic and, in a more general form,
deadline monotonic assignment. When two tasks are given the same
priority, we can choose one of them and assign a higher priority to
that task and the task set will still be schedulable. This results
in a strictly monotonic priority order and we do not need to deal
with FIFO order. This eliminates queues for each priority level and
results in a single, priority ordered task list with unlimited
priority levels.
Synchronized blocks are executed with priority ceiling emulation
protocol. An object, used for synchronization, for which the
priority is not set, top priority is assumed. This avoids priority
inversions on objects that are not accessible from the application
(e.g. objects inside a library).
In addition, the scheduler contains methods for worst-case time
measurement for both the periodic work and handler methods. These
measured execution times can be used during development when no WCET
analysis tool is available.
\subsection{Memory}
The profile does not support a garbage collector. All memory should
be allocated at the initialization phase. Without a garbage
collector, the heap implicitly becomes immortal memory (as defined
by the RTSJ). For objects created during the mission phase, a scoped
memory is provided. Each scoped memory area is assigned to one
\code{RtThread}. A scoped memory area cannot be shared between
threads. No references are allowed from the heap to scoped memory.
Scoped memory is explicitly entered and left using invocations from
the application logic. Memory areas are cleared both on creation and
when leaving the scope (invocation of \code{exitMemory()}), leading
to a memory area with constant allocation time, as opposed to memory
with linear allocation time (as the memory type \code{LTMemory} in
the RTSJ) \cite{Corsaro:2003:DPR}.
\subsection{Restriction of Java}
A list of some of the language features that should be avoided for
WCET analyzable real-time threads and bound memory usage:
\begin{description}
\item[WCET:] Only analyzable language constructs are allowed (see \cite{84850}).
\item[Static class initialization:] Since the definition when
to call the static class initializer is problematic (see
Section~\ref{para:restrict:clinit}), they are disallowed. Move this
code to a static method (e.g. \code{init()}) and invoke it explicit
in the initialization phase.
\item[Inheritance:] Reduce usage of interfaces and overridden methods.
\item[String concatenation:] In immortal memory scope only string concatenation with string
literals is allowed.
\item[Finalization:] \code{finalize()} has a weak definition
in Java. Because real-time systems run \emph{forever}, objects in
the heap, which is immortal in this specification, will never be
finalized. Objects in scoped memory are released on
\code{exitMemory()}. However, finalizations on these objects
complicate WCET analysis of \code{exitMemory()}.
\item[Dynamic Class Loading:] Due to the implementation and WCET analysis
complexity dynamic class loading is avoided.
\end{description}
%
A program analysis tool can greatly help in enforcing these
restrictions.
\begin{lstlisting}[float,caption={A periodic real-time thread},
label=lst:arch:rt:profile:example]
public class Worker extends RtThread {
private SwEvent event;
public Worker(int p, int t,
SwEvent ev) {
super(p, t,
// create a scoped memory area
new Memory(10000)
);
event = ev;
init();
}
private void init() {
// all initialzation stuff
// has to be placed here
}
public void run() {
for (;;) {
work(); // do some work
event.fire(); // and fire an event
// some work in scoped memory
enterMemory();
workWithMem();
exitMemory();
// wait for next period
if (!waitForNextPeriod()) {
missedDeadline();
}
}
// should never reach this point
}
}
\end{lstlisting}
\begin{lstlisting}[float,caption={Start of the application},
label=lst:arch:rt:profile:usage]
// create an Event
Handler h = new Handler(3, 1000);
// create two worker threads with
// priorities according to their periods
FastWorker fw = new FastWorker(2, 2000);
Worker w = new Worker(1, 10000, h);
// change to mission phase for all
// periodic threads and event handler
RtThread.startMission();
// do some non real-time work
// and invoke sleep() or yield()
for (;;) {
watchdogBlink();
Thread.sleep(500);
}
\end{lstlisting}
\subsection{Implementation Results}
The initial idea was to implement scheduling and dispatching in
microcode. However, many Java bytecodes have a one to one mapping to
a microcode instruction, resulting in a single cycle execution. The
performance gain of an algorithm coded in microcode is therefore
negligible. As a result, almost all of the scheduling is implemented
in Java. Only a small part of the dispatcher, a memory copy, is
implemented in microcode and exposed with a special bytecode.
Experimental results of basic scheduling benchmarks, such as
periodic thread jitter, context switch time for threads and
asynchronous events, can be found in Section~\ref{subsec:rt:perf}.
To implement system functions, such as scheduling, in Java, access
to JVM and processor internal data structures have to be available.
However, Java does not allow memory access or access to hardware
devices. In JOP, this access is provided by way of additional
bytecodes. In the Java environment, these bytecodes are represented
as static native methods. The compiled invoke instruction for these
methods (\code{invokestatic}) is replaced by these additional
bytecodes in the class file. This solution provides a very efficient
way to incorporate low-level functions into a pure Java system. The
translation can be performed during class loading to avoid
non-standard class files.
A pure Java system, without an underlying RTOS, is an unusual system
with some interesting new properties. Java is a safer execution
environment than C (e.g.\ no pointers) and the boundary between
\emph{kernel} and \emph{user space} can become quite loose.
Scheduling, usually part of the operating system or the JVM, is
implemented in Java and executed in the same context as the
application. This property provides an easy path to a framework for
user-defined scheduling.
1.1 jop/doc/book/runtime/rt_user.tex
http://www.opencores.org/cvsweb.shtml/jop/doc/book/runtime/rt_user.tex?rev=1.1&content-type=text/x-cvsweb-markup
Index: rt_user.tex
===================================================================
\section{User-Defined Scheduler}
\label{sec:usersched}
\emph{TODO: rewrite and explain the scheduler in detail.}
The novel approach to implement a real-time scheduler in Java opens
up new possibilities. An obvious next step is to extend this system
to provide a framework for user-defined scheduling in Java. New
applications, such as multimedia streaming, result in \emph{soft}
real-time systems that need a more flexible scheduler than the
traditional fixed priority based ones. This section provides a
simple-to-use framework to evaluate new scheduling concepts for
these applications in real-time Java.
The following section analyzes which events are exposed to the
scheduler and which functions from the JVM need to be available in
the user space. It is followed by the definition of the framework
and examples of how to implement a scheduler using this framework.
\subsection{Schedule Events}
The most important element of the user-defined scheduler is to
define which events result in the scheduling of a new task. When
such an event occurs, the user-defined scheduler is invoked. It can
update its task list and decide which task is dispatched.
\begin{description}
\item[Timer interrupt:] For timed scheduling decisions, a programmable
timer generates exact timed interrupts. The scheduler controls the
time interval for the next interrupt.
\item[HW interrupt:] Each hardware-generated interrupt can be associated
with an asynchronous event. This allows the execution of a device
driver under the control of the scheduler. Latencies of the device
driver can be controlled by assigning the right priority in a
priority scheduler.
\item[Monitor:] To allow different implementations of priority inversion
protocols, hooks for \code{monitorenter} and \code{monitorexit} are
provided.
\item[Thread block:] Each thread can cease execution via a call of the
scheduler. This function is used to implement methods such as
\code{waitForNextPeriod()} or \code{sleep()}. The reason for
blocking (e.g. end of periodic work) has to be communicated to the
scheduler (e.g. next time to be unblocked for a periodic task).
\item[SW event:] Invoking \code{fire()} on an event provides support for
signaling. \code{wait()}, \code{notify()} or \code{notifyAll()} are
not necessary. However, this mechanism is not part of the scheduling
framework. It can be implemented with the user-defined scheduler and
an associated thread class.
\end{description}
\subsection{Data Structures}
To implement a scheduler in Java, some JVM internal data structures
need to be accessible.
\begin{description}
\item[Object:] In Java, any object (including an object from the class
\code{Class} for static methods) can be used for synchronization.
Different priority inversion protocols require different data
structures to be associated with an object. Each object provides a
field, accessed through a \code{Scheduler} method, in which these
data structures can be attached.
\item[Thread:] A list of all threads is provided to the scheduler. The
scheduler is also notified when a new thread object is created or a
thread terminates. The scheduler controls the start of threads.
\end{description}
\subsection{Services for the Scheduler}
The real-time JVM and the hardware platform have to provide some
minimum services. These services are exposed through
\code{Scheduler}:
\begin{description}
\item[Dispatch:] The current active thread is interrupted and a new
thread is placed in the run state.
\item[Time:] System time with high resolution (microseconds, if the
hardware can provide it) is used for time derived scheduling
decisions.
\item[Timer:] A programmable timer interrupt (not a timer tick) is
necessary for accurate time triggered scheduling.
\item[Interrupts:] To protect the data structures of the scheduler all
interrupts can be disabled and enabled.
\end{description}
\subsection{Class Scheduler}
The class \code{Scheduler} has to be extended to implement a
user-defined scheduler. The class \code{Task} represents
\emph{schedulable objects}. For non-trivial scheduling algorithms,
\code{Task} is also extended. The scheduler lives in normal thread
space. There is no special context such as kernel space. The methods
of \code{Scheduler} are categorized by the caller module and
described in detail below.
\paragraph{Application}
To use a scheduler in an application, the application only has to
create one instance of the scheduler class and has to decide when
scheduling starts.
\begin{lstlisting}[emph=Scheduler]
public Scheduler()
\end{lstlisting}
A single instance of the scheduler is created by the application.
\begin{lstlisting}[emph=start]
public void start()
\end{lstlisting}
This method initiates the transition to the mission phase of the
application. All created tasks are started and scheduled under the
control of the user scheduler.
\paragraph{Task}
A user-defined scheduler usually needs an associated user-defined
thread class (an extension of \code{Task}). This class interacts
with the scheduler by invoking following methods from
\code{Scheduler}:
\begin{lstlisting}[emph=addTask]
void addTask(Task t)
\end{lstlisting}
The scheduler has access to the list of created tasks to use at the
start of scheduling. For dynamic task creation after the start of
the scheduler, this method is called by the constructor of Task, to
notify the scheduler to update its list.
\begin{lstlisting}[emph=isDead]
void isDead(Task t)
\end{lstlisting}
The scheduler is notified when a Task returns from the \code{run()}
method. The scheduler removes this Task from the list of schedulable
objects.
\begin{lstlisting}[emph=block]
void block()
\end{lstlisting}
Every \code{Task} can cease execution via a call of the scheduler.
This method is used to implement methods such as
\code{waitForNextPeriod()} or \code{sleep()} in a user defined
thread class.
\paragraph{Java Virtual Machine}
The methods listed below provide the essential points of
communication between the JVM and the scheduler. As a response to an
interrupt (hardware or timer), entrance or exit of a synchronized
method/block the JVM invokes a method from the scheduler.
\begin{lstlisting}[emph=schedule]
abstract void schedule()
\end{lstlisting}
This is the main entry point for the scheduler. This method has to
be overridden to implement the scheduling algorithm. It is called
from the JVM on a timed event or a software interrupt (see
\code{genInt()}) is issued (e.g. when a \code{Task} gives up
execution).
\begin{lstlisting}[emph=interrupt]
void interrupt(int nr)
\end{lstlisting}
The scheduler is notified on a hardware event. It can directly call
an associated device driver or use this information to unblock a
waiting task.
\begin{lstlisting}[emph={monitorEnter,monitorExit}]
void monitorEnter(Object o)
void monitorExit(Object o)
\end{lstlisting}
These methods are invoked by the JVM on synchronized methods and
blocks (JVM bytecodes \code{monitorenter} and \code{monitorexit}).
They provide hooks for executing dynamic priority changes in the
scheduler.
\paragraph{Scheduler}
Services of the JVM needed to implement a scheduler are provided
through static methods.
\begin{lstlisting}[emph=genInt]
static final void genInt()
\end{lstlisting}
This service from the JVM schedules a software interrupt. As a
result, \code{schedule()} is called. This method is the standard way
of switching control to the scheduler. It is e.g. invoked by
\code{block()}.
\begin{lstlisting}[emph={enableInt,disableInt}]
static final void enableInt()
static final void disableInt()
\end{lstlisting}
The scheduler cannot use monitors to protect its data structures as
the scheduler itself is in charge of handling monitors. To protect
the data structures of the scheduler, it can globally enable and
disable interrupts.
\begin{lstlisting}[emph=dispatch]
static final void dispatch(Task nextTask, int nextTim)
\end{lstlisting}
This method dispatches a \code{Task} and schedules a timer interrupt
at \code{nextTim}.
\begin{lstlisting}[emph={attachData,getAttachedData}]
static final void attachData(Object obj, Object data)
static final Object getAttachedData(Object obj)
\end{lstlisting}
The behavior of the priority inversion avoidance protocol is defined
by the user scheduler. The root of the Java class hierarchy
(\code{java.lang.Object}) contains a JVM internal reference of
generic type Object that can be used by the scheduler to attach data
structures for monitors. The first argument of these methods is the
object that is used as monitor.
\paragraph{Scheduler or Task}
The following two methods are utility functions useful for the
scheduler and the thread implementation.
\begin{lstlisting}[emph=getNow]
static final int getNow()
\end{lstlisting}
To support time-triggered scheduling, the system provides access to
a high-resolution time or counter. The returned value is the time
since startup in microseconds. The exact resolution is
implementation-dependent.
\begin{lstlisting}[emph=getRunningTask]
static final Task getRunningTask()
\end{lstlisting}
The current running \code{Task} (in which context the scheduler is
called) is returned by this method.
\subsection{Class Task}
A basic structure for schedulable objects is shown in
Listing~\ref{lst:arch:rt:user:task}. This class is usually extended
to provide a thread implementation that fits to the user-defined
scheduler. The class \code{Task} is intended to be minimal. To avoid
inheriting methods that do not fit for some applications, it does
not extend \code{java.lang.Thread}. However, \code{Task} can be used
to \emph{implement} \code{java.lang.Thread}.
\begin{lstlisting}[float,caption=A basic schedulable object,
label=lst:arch:rt:user:task, emph={Task, start, enterMemory,
exitMemory,run,getFirstTask,getNextTask}]
public class Task {
public Task()
public Task(Memory mem)
void start()
public void enterMemory()
public void exitMemory()
public void run()
static Task getFirstTask()
static Task getNextTask()
}
\end{lstlisting}
The methods \code{enterMemory} and \code{exitMemory} are used by the
application to provide scoped memory for temporary allocated
objects. \code{Task} provides a list of active tasks for the
scheduler.
One issue, raised by the implementation of the framework is the way
in which access rights to methods need to be defined in Java. All
methods, except \code{start()}, should be \code{private} or
\code{protected}. However, some methods, such as \code{schedule()},
are invoked by a part of the JVM, which is also written in Java but
resides in a different package. This results in defining the methods
as public and \emph{hoping} that they are not invoked by the
application code. The C++ concept of friends would greatly help in
sharing information over package boundaries without making this
information public.
\subsection{A Simple Example Scheduler}
Listing~\ref{lst:arch:rt:user:example} shows a full example of using
this framework to implement a simple round robin scheduler.
The only method that needs to be supplied is \code{schedule()}. For
a more advanced scheduler, it is necessary to provide a combination
of a user defined thread class and a scheduler class. These two
classes have to be tightly integrated, as the scheduler uses
information provided by the thread objects for its scheduling
decisions.
\pagebreak
\begin{lstlisting}[caption=A very simple scheduler,
label=lst:arch:rt:user:example]
public class RoundRobin extends Scheduler {
//
// test threads
//
static class Work extends Task {
private int c;
Work(int ch) {
c = ch;
}
public void run() {
for (;;) {
Dbg.wr(c); // debug output
// busy wait to simulate
// 3 ms workload in Work.
int ts = Scheduler.getNow();
ts += 3000;
while (ts-Scheduler.getNow()>0)
;
}
}
}
//
// user scheduler starts here
//
public void addTask(Task t) {
// we do not allow tasks to be
// added after start().
}
//
// called by the JVM
//
public void schedule() {
Task t = getRunningTask().getNextTask();
if (t==null) t = Task.getFirstTask();
dispatch(t, getNow()+10000);
}
public static void main(String[] args) {
new Work('a');
new Work('b');
new Work('c');
RoundRobin rr = new RoundRobin();
rr.start();
}
}
\end{lstlisting}
\subsection{Interaction of Task, Scheduler and the JVM}
The framework is used to re-implement the scheduler described in
Section~\ref{sec:rtprof}. In the original implementation, the
interaction between scheduling and threads was simple, as the
scheduling was part of the thread class. Using the framework, these
functions have to be split to two classes, extending \code{Task} and
\code{Scheduler}. Both classes are placed in the same package to
provide simpler information sharing with some protection from the
rest of the application. For performance reasons data structures are
directly exposed from one class to the other.
The resulting implementation is compatible with the first
definition, with the exception that \code{RtThread} now extends
\code{Task}. However, no changes in the application code are
necessary.
\figurename~\ref{fig_arch_rt_user_interaction} is an interaction
example of this scheduler within the framework. The interaction
diagram shows the message sequences between two application tasks,
the scheduler, the JVM and the hardware. The hardware represents
interrupt and timer logic. The corresponding code fragments of the
application, \code{RtThread} and \code{PriorityScheduler} are shown
in Listing~\ref{lst:arch:rt:user:app}, \ref{lst:arch:rt:user:rtthr}
and \ref{lst:arch:rt:user:prsched}. Task 2 is a periodic task with a
higher priority than Task 1.
\begin{figure*}
\centering
\includegraphics[scale=\picscale]{runtime/rt_user_interaction}
\caption[Interaction diagram of the user scheduler framework]
{Interaction and message exchange between the application,
the scheduler, the JVM and the hardware}
\label{fig_arch_rt_user_interaction}
\end{figure*}
The first event is a timer event to unblock Task 2 for a new period.
The generated timer event results in a call of the user defined
scheduler. The scheduler performs its scheduling decision and issues
a context switch to Task 2. With every context switch the timer is
reprogrammed to generate an interrupt at the next time triggered
event for a higher priority task. Task 2 performs the periodic work
and ceases execution by invocation of \code{waitForNextPeriod()}.
The scheduler is called and requests an interrupt from the hardware
resulting in the same call sequence as with a timer or other
hardware interrupt. The software generated interrupt imposes
negligible overhead and results in a single entry point for the
scheduler. Task 1 is the only ready task in this example and is
resumed by the scheduler.
Using a general scheduling framework for a real-time scheduler is
not without its costs. Additional methods are invoked from a
scheduling event until the actual dispatch takes place. The context
switch is about 20\% slower than in the original implementation. It
is the opinion of the author that the additional cost is outweighed
by the flexibility of the framework.
\begin{lstlisting}[float,caption={Code fragment oft the application},
label=lst:arch:rt:user:app]
for (;;) {
doPeriodicWork();
waitForNextPeriod();
}
\end{lstlisting}
\begin{lstlisting}[float,caption={Implementation in RtThread},
label=lst:arch:rt:user:rtthr]
public boolean waitForNextPeriod() {
synchronized(monitor) {
// ps is the instance of
// the PriorityScheduler
int nxt = ps.next[nr] + period;
int now = Scheduler.getNow()
if (nxt-now < 0) {
// missed deadline
doMissAction();
return false;
} else {
// time for the next unblock
ps.next[nr] = nxt;
}
// just schedule an interrupt
// schedule() gets called.
ps.block();
}
return true;
}
\end{lstlisting}
\begin{lstlisting}[float,caption={Implementation of the PriorityScheduler},
label=lst:arch:rt:user:prsched]
public void schedule() {
// Find the ready thread with
// the highest priority.
int nr = getReady();
// Search the list of sleeping threads
// to find the nearest release time
// in the future of a higher priority
// thread than the one that will be
// released now.
int time = getNextTimer(nr);
// This time is used for the next
// timer interrupt.
// Perform the context switch.
dispatch(task[nr], time);
// No access to locals after this point.
// We are running in the NEW context!
}
\end{lstlisting}
\subsection{Predictability}
The architecture of JOP is designed to simplify WCET analysis. Every
JVM bytecode maps to one ore more microcode instructions. Every
microcode instruction takes exactly one cycle to execute. Thus, the
execution time at the bytecode level is known cycle accurately. The
microcode contains no data dependent or unbound loops that would
compromise the WCET analysis (see Section~\ref{sec:wcet}).
The worst-case time for dispatching is known cycle accurately on
this architecture. Only the time behavior of the user scheduler
needs to be analyzed. With the known WCET of every bytecode, as
listed in Appendix~\ref{appx:bytecode}, the WCET of the scheduler
can be obtained by examining it at the bytecode level. This can be
done manually or with a WCET analysis tool.
\subsection{Related Work}
Several implementations of user-level schedulers in standard
operating systems have been proposed. In \cite{REDLinux2003}, the
Linux scheduling mechanism is enhanced. It is divided into a
dispatcher and an allocator. The dispatcher remains in kernel space;
while the allocator is implemented as a user space function. The
allocator transforms four basic scheduling parameters (priority,
start time, finish time and budget) into scheduling attributes to be
used by the dispatcher. Many existing schedulers can be supported
with this parameter set, but others that are based on different
parameters cannot be implemented. This solution does not address the
implementation of protocols for shared resources.
A different approach defines a new API to enable applications to use
application-defined scheduling in a way compatible with the
scheduling model defined in POSIX \cite{787339}. It is implemented
in the MaRTE OS, a minimal real-time kernel that provides the C and
Ada language POSIX interface. This interface has been submitted to
the Real-Time POSIX Working Group for consideration.
One approach to user-level scheduling in Java can be found in
\cite{Feizabadi:2003:UAS}. A thread \emph{multiplexor}, as part of
the FLEX ahead-of-time compiler system for Java, is used for utility
accrual scheduling. However, the underlying operating system -- in
this case Linux -- can still be seen through the framework and there
is no support for Java synchronization.
\subsection{Summary}
This section and Section~\ref{sec:rtprof} consider the
implementation of real-time scheduling on a Java processor. The
novelty of the described approach is in implementing functions
usually associated with an RTOS in Java. That means that real-time
Java is not based on an RTOS, and therefore not restricted to the
functionality provided by the RTOS. With JOP, a self-contained
real-time system in pure Java becomes possible. This system is
augmented with a framework to provide scheduling functions at the
application level. The implementation of the specification,
described in Section~\ref{sec:rtprof}, is successfully used as the
basis for a commercial real-time application in the railway
industry. Future work will extend this framework to support multiple
schedulers. A useful combination of schedulers would be: one for
standard \code{java.lang.Thread} (optimized for throughput), one for
soft real-time tasks and one for hard real-time tasks.
|
 |
Browse
