Transcript Real-Time

Design Real-Time Java Remote Method Invocation:
A Server-Centric Approach
Sangig Rho (Samsung Electronics, Korea),
Byung Choi (Michigan Tech),
Riccardo Bettati (Texas A&M)
Nov 14, 2005
1
Overview
•
•
•
•
•
Background
Research Objective
Related Work
Proposed Methodology
Conclusions and Future Work
2
Background 1:
• Distributed open real-time systems?
– Scheduling parameters (workload, deadline, priority)
– Release parameters (arrival time, arrival pattern)
– Bursty arrival of client’s requests
• Implementation vehicle?
 Component-based (CORBA, DCOM, .NET, EJB)
 Java …?
3
Background 2:
• Server declared?
– Server defined priority
• Client propagated?
– Inherit global priority
• Real-Time guarantee with admission Control!
4
Research Objectives:
• Providing real-time Java RMI which supports:
– Temporal isolation from other components’ CPU
demand
– So, predictable RMI execution time in various
conditions
• Solutions?
– Server declared real-time property model
5
Related Work 1:
• Real-time extensions for component-based
systems
 TAO (The ACE ORB) project [Schmidt: 2000?]
 A CORBA preserving the priority levels of calls across
component boundaries
 The Specification for Real-Time CORBA [Schmidt 2000]
 Management of CPU, network, and memory resources
 Server declared or client propagated model for fixed
priority scheduling between client and server
• No isolation due to static priority scheduling
6
Related Work: 2
• Java RMI system
 Simplicity, security, portability
 Middleware for distributed systems
• The Real-Time Specification for Java (RTSJ)
 Provide standards for real-time Java APIs except
real-time RMI [Bollella 2000]
• The Distributed Real-Time Specification for Java
(DRTSJ)
 Not released, rather complicated, no isolation in
timing domain because of using static priority
scheduling [Jensen 2001]
7
Related Work 3:
• TimeSys RTSJ Reference Implementation
(RI)
 Based on J2ME (Java Micro Edition) source
 No RMI support
 Our implementation base
 jRate [Corsaro 2002]
 JTime
 Commercialized product
 RTSJ-compliant Java for embedded systems
 No RMI support
8
Research Objectives Revisited
• Real-time guarantees in form of deadline guarantees to remote
method invocations
 Bounded maximum response time of remote method
• Hard real-time guarantees
 Contingent upon
 The real-time capabilities of the underlying OS and
runtime environment
 Well-known number of clients
 Well-behaved clients
 Well-known worst case execution of each method of
components
• At best soft real-time guarantees if fails to meet one of above
conditions
• Timing isolation through a guaranteed-rate scheduler
 The worst case response time of jobs in a component does not
depend on the processor-time demands of other components
9
Our Methodology
• Real-time capability for component-based distributed systems
 Real-time scheduling of tasks in Java Virtual Machine
 Provide predictable executions of sporadic tasks of software components
 Extension of the Real-Time Specification for Java (RTSJ)
 Real-Time Java RMI
 Deadline-driven EDF scheduler
 Total Bandwidth server mechanism
 A server-centric execution environment in terms of holder of real-time
properties
 Server declared model for real-time properties
 No need for delivering and inheriting real-time properties between
client and server for scheduling purposes
10
Probabilistic Approach for Characterizing
Total Bandwidth Servers
•
How to allocate a utilization for a remote method RMij
 Maximum budget
 Given worst case execution time of the remote method RMij
 Period
 Unknown
•
How to decide the period of Total Bandwidth server TBij
 Assumption
 Given distribution function of interarrival times of client requests for RMij
 By using minimum interarrival time of client requests
 Hard real-time guarantees
 Overallocate system resources
 By using a probabilistic approach
 Proof of a G/D/1 queue model for Total Bandwidth server
 Lower allocated resources due to a larger period than that of the above
 Efficiently utilize system resources
 Soft real-time guarantees
11
Experimental Evaluation
• Experimental Evaluation
 Determine overhead of local method
 Determine overhead of real-time RMI
 Predictable latency of remote method invocation
 Under overloaded condition
 With CPU-bound tasks, two Java applications for
file compression
12
Latency of Remote Method Invocation
•
•
Real-Time RMI performance
 Measure latency and jitter
 Dell 930 MHz with memory of 256
Megabytes
 An Agilent Technologies Network
Analyzer
 Capture all packets
 Nanosecond timer resolution
 Windows 2000 Pro Embedded
with two CPUs
Latency of a remote method invocation
 Measure time difference between
 Moment of client’s sending of the
first packet of RMI request
 Moment of server’s sending of the
last packet of the result
 Ethereal
 Network Protocol Analyzer
 Refined data display by using
display filter
Server Host
Dell Dimension 4100 Pentium III
Fast Ethernet
100-Mbps Link
Fast Ethernet
100-Mbps Link
Agilent Technologies
Network Analyzer
Client Host
Dell Dimension 4100 Pentium III
13
Local Method Execution Time on TimeSys 3.1-RT
14
RMI Latency with Two Running Java Applications
for File Compression
15
Standard Deviation of RMI Latency
16
Conclusions and Future Work
• One step toward distributed open real-time systems with Java RMI
 Predictable end-to-end latency
• Further investigation on this methodology with the Distributed Real-Time
Specification for Java (DRTSJ) needed
• Real-time CORBA vs. DRTSJ?
17
Real-Time Infrastructure:
Guaranteed-Rate Scheduling
• Feasible scheduling for isolation
in time domain
• Guaranteed-rate scheduling in
deadline-driven real-time systems
• Total Bandwidth server
Better responsiveness of
budget replenishment
• At time 1:
•
Budgetserver = 1.0;
Deadlineserver = 1 + (1.0 / 0.25);
= 5;
At time 4:
Budgetserver = 2.0;
Deadlineserver = 5 + (2.0 / 0.25);
= 13;
• At time 12:
Budgetserver = 3.0;
Deadlineserver = 13 + (3.0 / 0.25);
= 25;
Periodic Task (Period of 3 Time Units, Execution Time of 1 Time Unit)
0
3
6
9
12
15
18
21
24
27
Periodic Task (Period of 4 Time Units, Execution Time of 1 Time Unit)
0
4
8
12
16
20
24
Total Bandwidth Server of Size 0.25
0 1
4 5
12 13
1.0
2.0
28
25
3.0
Budget of Total Bandwidth Server
3
2
1
0 1
3 4
8
12
20
18
Time
Real-Time Infrastructure:
Earliest Deadline First Scheduler
Processing Newly
Admitted
Real-Time Threads
Waking
• EDF scheduling algorithm
 Feasible scheduling for a system
Independent
Preemptive
Periodic
Sporadic tasks
 If ∑ (instantaneous utilization) ≤ 1
• No support in the RTSJ RI
• Higher priority over RealtimeThreads
Expiration of The
Timer for Next
Wake-Up
Or
Notification from
a Real-Time
Thread
Waiting
Updating The Status of
RT-Threads
Processing Inactive
RT-Threads
Calculating Next
Wake-Up Time
Sorting RT-Threads
by Deadline
Processing Released
RT-Threads
Assigning Priorities
to RT-Threads
19
Real-Time Infrastructure:
Adjustment of Priorities of Real-Time Worker
Threads Based on Admitted Utilization
• Update properties of
public class AOUnicastServerRef extends UnicastRef {
…
javax.realtime.ReleaseParameters instance
Cost (worst case execution time)
Relative Deadline
public void dispatch(Remote obj, StreamRemoteCall call, ObjID id)
throws IOException
{
…
if (obj instanceof Migratable) {
Executing at the
Maximum
Priority
Regardless of
the Requested
Remote Method
isAO = true;
bandwidthMonitor = ((Migratable) obj).getBandwidthMonitor();
defaultAdmissionControl = AdmissionControl.getDefaultAdmissionControl();
MethodWorkloadInfo methodWorkloadInfo = \
defaultAdmissionControl.findMethodWorkloadInfo(aoID, methodName);
…
/*
* For BandwidthMonitor
*/
long relativeDeadlineNanos = bandwidthMonitor.getServerPeriodNanos();
/*
* We will wake up EDF Scheduler.
* Cost and deadline should be adjusted for SchedulableData.
*/
RealtimeThread.setTotalBandwidthParameters(costNanos, \
relativeDeadlineNanos);
Executing at the
Adjusted Priority
Based on the
Requested Remote
Method
• Reflect updated deadline into scheduling
…
/*
* For BandwidthMonitor
*/
bandwidthMonitor.acquire();
Wake up EDF scheduler
Reschedule tasks
}
…
}
…
}
20
Real-Time Infrastructure:
Guaranteed-Rate Scheduling
•
•
•
Feasible scheduling algorithms for isolation in time domain
Guaranteed-rate scheduling in deadline-driven real-time systems
 Better responsiveness of server’s budget replenishment in Total Bandwidth server
Total Bandwidth Server
 A Initial state
 Budgetserver = 0;
 Deadlineserver = 0;
 A job queue with no backlogged jobs
 At time t, arrival of a job with workload of ExecutionTimeJob_1
 Budgetserver = ExecutionTimeJob_1 ;
 Deadlineserver = max(Deadlineserver , t) + (ExecutionTimeJob_1 / Utilizationserver ) ;
 Current job’s completion with backlogged jobs
 Budgetserver = ExecutionTimeJob_2 ;
 Deadlineserver = Deadlineserver + (ExecutionTimeJob_2 / Utilizationserver ) ;
 Current job’s completion with no backlogged jobs
 Do nothing;
 Suspend the thread of Total Bandwidth server, a worker thread, by EDF scheduler
21
A Model for Distributed
Component-Based Applications
•
•
•
•
•
•
A collection of
 n clients, C1, C2, …, Cn
 m components, A1, A2, …, Am
Each component Ai
 k remote methods, RMi1, RMi2, …, RMik
Client
 Execute outside of our resource control
Execution environments
 A client execution environment
 No further consideration
 A component execution environment
Component execution environment
 h hosts, H1, H2, …, Hh
A uniform processing environment
 Relative speed Δℓ for each host Hℓ
 Execution of ε time units on reference host takes ε / Δℓ time
units on a host with relative speed Δℓ
22
The Task Model
Ji(4) Ji(3) Ji(2) Job Ji(1)
Task Ti
Ji1
Component A1
•
•
•
•
Ji2
Component A2
Jim
Component Am
Synchronous invocation of remote methods
 Migration of the thread of control between caller and callee
Model workload as a set of tasks
Each task Ti
 A sequence of jobs, Ji(1), Ji(2), …, Ji(k)
Each job Ji
 The execution of each job is triggered by an invocation of a remote
method by a client
 Consists of a set of subjobs, Ji = {Ji1, Ji2, … , Jim}
 Workload of each job Ji
 Σ (Workload of each subjob Jij)
23
Real-Time Infrastructure:
Decomposition of RMI Latency
24
Admission Control Policy
for Components
• Utilization-based admission feasibility tests
 Check required utilization demands of migrating
components
Single resource
 Assign real-time properties to each remote method
Worst case execution time
Utilization
25
Motivation & Introduction:
What is Real-Time?
• Being Fast as much as possible?
• Meeting deadlines!
– How?
• Hard real-time vs. soft real-time systems
• Applications: job scheduling, packet scheduling, etc..
26
Typical Real-Time Systems
• Admission Control
– Schedulability Test
• Client Request
– Timing constraints: release time, execution time, deadline
• (Job) Scheduling
– EDF, priority?
• Real-Time Tasks:
– Periodic, Aperiodic, Sporadic
• Overload?
– Out of scope!
27
Background:
Component-Based Design
• Component-based technology
 Increasing popularity in software systems development
 Modularity allows to easily build and test parts of large
system
 Reusability enables realization of new software
systems as assemblies of existing software components
28
Background:
Characteristics of Components
• Opaqueness
 Do not make internal state available to component’s environment
• Composability
 Provide well-defined services either to a client or to other
components
• Isolation
 The behavior of a component does not depend on the state, even in
presence of another component
• Isolation requirement
 Decoupling of the component implementation from the communication
infrastructure
 Given sufficiently effective communication infrastructure, components
can be decoupled from their execution platform
29
Real-Time Infrastructure:
Java for Distributed Real-Time Systems
•
•
Models for distributed systems
 Control flow of remote method invocation
 Point-to-point flow of data through object serialization
 Message passing mechanism
The Distributed Real-Time Specification for Java (DRTSJ)
 Extend the RTSJ for real-time RMI
 Distributed thread model
 System-wide ID
 Transparent propagation of real-time properties over execution environments
•
 Provide predictability of end-to-end timeliness in distributed real-time
systems
The DRTSJ under development
 No consideration for sporadic real-time tasks of real-time Java RMI
 Non-server-centric execution environment
30
Real-Time Infrastructure:
Sun’s Java RMI Implementation
• Three layers to implement transparent remote method invocations
 The stub layer
 A proxy for client side
 Stub classes generated by rmic, RMI compiler
 Marshall and unmarshall parameters and returned values
 The remote reference layer
 Support semantics of reference and invocation (unicast, multicast)
 Translate between local and remote object references using remote
object tables
 The transport layer
 Establish connections to remote address spaces by using TCP
connection related classes
31
Real-Time Infrastructure:
A Solution for Creation of
Real-Time Worker Threads for RMI
•
•
The association of the RTSJ
javax.realtime.RealtimeThread class
 sun.rmi.transport.RMIThreadAction class
 ao.realtor.scheduler.TotalBandwidthParameters
class
 javax.realtime.AperiodicParameters class
 Workload, deadline, overrun handler,
deadline miss handler
 Unknown real-time properties for requested
up-call
 Initially assign highest priority to avoid priority
inversion
The Deadline-driven Earliest Deadline First (EDF)
scheduling
32
Challenges for Real-Time RMI
• Create real-time Java threads
 Real-time worker threads for handling client requests
 Schedule the worker threads to meet their real-time
properties
• Propagation of real-time timing constraints between client and
server
 Guarantee to meet deadline of client’s real-time
applications
• Provide real-time guarantees for sporadic tasks
 Aperiodic arrivals of client requests
33
Real-Time Infrastructure:
A Solution for Propagating Real-Time
Constraints Between Client and Server
• A server-centric execution environment
 A server declared model for real-time properties
 Isolation in real-time domain
Save network bandwidth for delivering and
inheriting real-time properties between client and
server
Effective admission negotiation for migrating
components by using utilization-based admission
control
34