Transcript task - IDL

Concurrent issues in Java,
Ada and Posix
Y Kermarrec
Ecole Temps Réel 2011
Aims
 To
present various forms of concurrency
expression
 To present issues when integrating concurrency
units in programming languages
• Support at run time
• Integration in the semantics
 To compare language approaches (with Java, Ada)
and POSIX and to (try to) explain why things are
getting complex
 … but not to cover everthing !
page 2
Dpt/Auteur
ETR 2011
Agenda
 Concurrency
based on API or integrated in
languages
 Concurrency expression and issues
• In Ada, Java and POSIX
 Conclusions
 References to know more
page 3
Dpt/Auteur
ETR 2011
Why do we need concurrency ?
 Because
of the inherent parallelism in the real
world
 And real-time systems are inherently concurrent
and their “sequential programming” is a difficult
alternative
• An alternative is the design of the cyclic execution of a program
sequence to handle the various concurrent activities
• This is difficult and when changes occur, everything must be
fixed and redesigned
• The resulting programs are confusing, obscure and complex
 Operating
system have made available processes
(at first) and then thread ... for a long time
Dpt/Auteur
A typical thread life cycle
Non-existing
Non-existing
Created
Initializing
Executable
Dpt/Auteur
Terminated
How to program threads ?
 Library
approach :
• a standard sequential language, e.g. C
• a set of packages that provide concurrency
• The C program makes calls to the library units
 With a dedicated concurrent programming
language
• Syntax and semantics to deal with concurrency,
synchronization and communication
• Tasks are independent, competing and
cooperative/communication (initial proposal with T.
Hoare’s CSP)
page 6
Dpt/Auteur
Nom du cours - Notes de cours
POSIX thread library
 The
original Pthreads API was defined in the
ANSI/IEEE POSIX 1003.1 - 1995 standard.
 The POSIX standard has continued to evolve
through revisions (eg version of 2004)
 The subroutines which comprise the Pthreads API
can be informally organized into four major
groups:
• Thread management
• Mutexes
• Condition variables
• Synchronization : barriers, locks, ..
page 7
Dpt/Auteur
ETR 2011
One API subroutine: Thread creation
 pthread_create
•
•
•
•
page 8
arguments:
thread: An opaque, unique identifier for the new
thread returned by the subroutine.
attr: An opaque attribute object that may be used to
set thread attributes. You can specify a thread
attributes object, or NULL for the default values.
start_routine: the C routine that the thread will
execute once it is created.
arg: A single argument that may be passed to
start_routine. It must be passed by reference. NULL
may be used if no argument is to be passed.
Dpt/Auteur
ETR 2011
A simple program (extracted from C)
void *PrintHello(void *threadid) {
long tid;
tid = (long)threadid;
printf("Hello World! It's me, thread #%ld!\n", tid);
pthread_exit(NULL);
}
int main(int argc, char *argv[]) {
pthread_t threads[NUM_THREADS];
int rc; long t;
for(t=0;t<NUM_THREADS;t++){
printf("In main: creating thread %ld\n", t);
rc = pthread_create(&threads[t], NULL, PrintHello, (void *)t);
if (rc){ printf("ERROR; return code from pthread_create() is %d\n", rc); exit(-1); }
/* Last thing that main() should do */
pthread_exit(NULL); }
Dpt/Auteur
A more advanced program (extracted from
Blaise Barney’s tutorial)
int main (int argc, char *argv[]) {
pthread_t thread[NUM_THREADS];
pthread_attr_t attr; int rc; long t; void *status;
/* Initialize and set thread detached attribute */
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
for(t=0; t<NUM_THREADS; t++) {
printf("Main: creating thread %ld\n", t);
rc = pthread_create(&thread[t], &attr, BusyWork, (void *)t);
if (rc) { printf("ERROR; return code from pthread_create() is %d\n", rc); exit(-1); }
}
/* Free attribute and wait for the other threads */
pthread_attr_destroy(&attr);
for(t=0; t<NUM_THREADS; t++) {
rc = pthread_join(thread[t], &status);
if (rc) { printf("ERROR; return code from pthread_join() is %d\n", rc); exit(-1); }
printf("Main: completed join with thread %ld having a status of %ld\n",t,(long)status);
}
printf("Main: program completed. Exiting.\n"); pthread_exit(NULL); }
Dpt/Auteur
Issues
 Posix
thread API : around 100 subroutines
• Simple and subtile …
• Tough for teaching and labs : do not present the
details!
 Default values :
• Eg attribute value set to NULL for pthread_create
 Who is testing return values and error codes ?
 Implementation dependency and portability ?
 Semantics ?
page 11
Dpt/Auteur
ETR 2011
Concurrent programming language
• “Concurrent computing is a form of computing in
which programs are designed as collections of
interacting computational processes that may be
executed in parallel” (BenAri)
• Concurrent Pascal : (begin A, B end)
• CSP (and then Occam) with processes and
channels
• ... And numerous contributions (Ada, Java, ....)
• The emergence of tasks / threads (that may be
implicit or explicit) as units for programmers....
• A main program is more or less a process / thread
page 12
Dpt/Auteur
ETR 2011
Concurrent execution unit
 From
fine grained (Occam at the instruction level)
to coarse granularity (Ada with tasks, Java with
threads …)
 Initialization with parameter passing when creating
the new unit or ‘initial’ communication…
 Termination
• completion of execution (reaching the end
statement)
• suicide
• abortion, through the explicit action of another task;
• occurrence of an unhandled error
•Dpt/Auteur
“End” on condition (eg for servers which are
implemented as never ending loops)
Towards hierarchies of concurrent units
 Concurrent
units are considered as ‘normal’
programming units and therefore can be nested
(similar to nested procedures / functions)
 Relationships
• Creation: Parent/Child - the parent may be delayed
while the child is being created and initialized
• Termination: Guardian/Dependant - a task may
depend on a specific unit and this latter cannot
terminate before all its dependents are terminated
 Very nice for the developer but very strong impact
on the run time !!!
Dpt/Auteur
A typical thread life cycle (from A Wellings)
Non-existing
Non-existing
Created
Waiting Child
Initialization
Dpt/Auteur
Initializing
Terminated
Executable
Waiting Dependent
Termination
Concurrency unit coding
 Fork
and Join
• Inspired from OS features directly
• Synchronization between the parent and the
dependant unit
 Co-begin / Co-end
• Transition from the “;” to the “,” and towards
concurrency syntactic expression
 Explicit Task / Thread construction
• Integration of the task in the programming language
features - combination with other features : type,
data structures, OO
•Dpt/Auteur
Integration into theETRsemantics
page 16
2011
Variations in the Task Model
 structure
• static, dynamic
 level
 granularity
• fine or coarse grain
 termination
• Flat or nested
 initialization
• with or without parameter passing
• natural, suicide
• abortion, untrapped error
• never, when no longer needed
 representation
• fork/join, cobegin, explicit task
declarations
• => impact at run time
Dpt/Auteur
Overview of Ada Concurrency Support (1)
 Ada
95 preliminaries
• Software engineering and real time features from the very
beginning (Ada 83) ; ISO approved ; compiler “validation”
• A core language + optional annexes
• “Specialized Needs Annexes” to address specific issues:
real time systems, distributed systems, numerics, safety …
 Basic concurrency model
• Unit of concurrency is the task
- Task specification = interface to other tasks
- Task body = implementation (algorithm) + own storage area
- Task type serves as a template for tasks which perform the same algorithm
- Task may be declared or dynamically allocated
Dpt/Auteur
-18-
Overview of Ada Concurrency Support (2)
 Example
of a declared task
with Ada.Text_IO;
procedure Example1 is
Count : Integer := 60;
task Writer; -- Specification
task body Writer is – Body
-- private declarations
begin
for I in 1..Count loop
Ada.Text_IO.Put_Line( "Hello" & Integer'Image(I));
delay 1.0; -- Suspend for at least 1.0 second
end loop;
end Writer;
begin
-- Writer activated
null;
-- Main procedure suspended until Writer terminates
end Example1;
Dpt/Auteur
Overview of Ada Concurrency Support (3)
with Ada.Text_IO;
procedure Example2 is
task type Writer(Count : Natural);
-- Specification
type Writer_Ref is access Writer;
Ref : Writer_Ref;
task body Writer is -- Body
begin
for I in 1..Count loop
Ada.Text_IO.Put_Line( "Hello" & I'Img);
delay 1.0; -- Suspend for at least 1.0 second
end loop;
end Writer;
begin
Ref := new Writer(60); -- activates new Writer task object
-- Main procedure suspended until Writer object terminates
end Example2;
Dpt/Auteur
Overview of Ada Concurrency Support (4)
 Lifetime
•
•
•
•
•
page 21
properties
Declared task starts (is activated) implicitly at the
begin of parent unit
Allocated task (dynamic with new) starts at the point
of allocation
Task statements execute “concurrently” with
statements of parent
Task completes when it reaches its end
“Master” is suspended when it reaches its end, until
each child task terminates (this is to prevent
dangling references to local data)
Dpt/Auteur
ETR 2011
Overview of Ada Concurrency Support (5)
 Mutual
•
•
•
•
page 22
exclusion
Shared data, pragma Volatile / Atomic
Protected objects / type : Data + “protected”
operations that are executed with mutual exclusion
(multiple readers or single writer)
“Passive” task that sequentializes access to a data
structure via explicit communication (rendezvous) :
only solution with Ada 83
Explicit mutex-like mechanism (definable as
protected object/type) that is locked and unlocked
Dpt/Auteur
ETR 2011
Overview of Ada Concurrency Support (6)
 Coordination
/ communication
• Pass data to task via discriminant (at creation) or
rendezvous
• Suspension_Object : A single task can await a given
Suspension_Object becoming “true” and will suspend until another task sets
that state.
• Rendezvous model : inter-task communication
• Implicit wait for dependent tasks
 Asynchrony
• Event handling via dedicated task, interrupt handler
• abort statement:
• Asynchronous transfer of control via timeout or
Dpt/Auteur
rendezvous request
-23-
Overview of Ada Concurrency Support (7)
 Interaction
with exception handling
• Tasking_Error raised at language-defined points
• Task that propagates an (unhandled) exception
terminates silently
 More features which are extremely powerful:
• Select, accept, requeue, …
page 24
Dpt/Auteur
ETR 2011
Task States in Ada (from A Wellings)
non-existing
non-existing
terminated
created
finalising
dependent tasks terminate
create child task
activating
completed
exit a master block
child task
activation complete
waiting child
activation
create child task
child task activation complete
exit a master block
executable
dependent tasks
terminate
Dpt/Auteur
dependent tasks
terminate
waiting dependent
termination
Real time system annex











page 26
Task Priorities
priority Scheduling
• TheTask Dispatching Model
• The Standard Task Dispatching Policy
priority Ceiling Locking
entry Queuing Policies
dynamic Priorities
preemptive Abort
Tasking Restrictions
monotonic Time
delay Accuracy
Synchronous Task Control (suspend_until_true, suspension obj)
Asynchronous Task Control (hold, resume on task id)
Dpt/Auteur
ETR 2011
Ravenscar : when too much is too much

pragma Task_Dispatching_Policy (FIFO_Within_Priorities);

 The
Ravenscar profile
is a subset of the Ada
tasking features
designed for safetycritical efficient hard
real-time computing
 pragma Profile
(Ravenscar);


























page 27
Dpt/Auteur
pragma Locking_Policy (Ceiling_Locking);

pragma Restrictions (
No_Abort_Statements,
No_Dynamic_Attachment,
No_Dynamic_Priorities,
No_Implicit_Heap_Allocations,
No_Local_Protected_Objects,
No_Local_Timing_Events,
No_Protected_Type_Allocators,
No_Relative_Delay,
No_Requeue_Statements,
No_Select_Statements,
No_Specific_Termination_Handlers,
No_Task_Allocators,
No_Task_Hierarchy,
No_Task_Termination,
Simple_Barriers,
Max_Entry_Queue_Length => 1,
Max_Protected_Entries => 1,
Max_Task_Entries
=> 0,
No_Dependence => Ada.Asynchronous_Task_Control
No_Dependence => Ada.Calendar,
No_Dependence => Ada.Execution_Time.Group_Budg
No_Dependence => Ada.Execution_Time.Timers,
No_Dependence => Ada.Task_Attributes);
More with Ada for real time
 The
Ada rationale : A great document for
understanding issues with Ada and real time
systems in general
• http://www.adahome.com/LRM/95/Rationale/rat95ht
ml/rat95-contents.html
page 28
Dpt/Auteur
ETR 2011
Overview of Java Concurrency Support (1)
 Java
Preliminaries
• OO language with built-in support for concurrency,
exception handling
• Dynamic data model
 Basic concurrency model
• Unit of concurrency is the thread
• Dynamically allocated
- an instance of the class java.lang.Thread or one of its subclasses
-
run()
method = algorithm performed by each instance of the class
- If implementing Runnable, construct a Thread object passing a
Runnable as parameter
Dpt/Auteur
-29-
Overview of Java Concurrency Support (2)
 Example
of simple thread
public class Writer extends Thread{
final int count;
public Writer(int count){this.count=count;}
public void run(){
for (int i=1; i<=count; i++){
System.out.println("Hello " + i);
}
}
public static void main( String[] args )
throws InterruptedException{
Writer w = new Writer(60);
w.start(); // New thread of control invokes w.run()
w.join();
// Wait for w to terminate
}
}
Dpt/Auteur
-30-
Overview of Java Concurrency Support (3)
 Lifetime
•
•
•
•
•
properties
Constructing a thread creates the resources that the
thread needs (stack, etc.)
“Activation” is explicit, by invoking start()
Started thread runs “concurrently” with parent
Thread terminates when its run method returns
Parent does not need to wait for children to
terminate
- Restrictions on “up-level references” from inner classes
prevent dangling references to parent stack data
page 31
Dpt/Auteur
ETR 2011
Overview of Java Concurrency Support (4)
 Mutual
exclusion
• Shared data (volatile fields)
• synchronized blocks/methods
 Thread coordination/communication
• Pass data to new thread via constructor
• Single event - wait() / notify()
• Broadcast event - wait() / notifyAll()
• join() suspends caller until the target thread completes
Dpt/Auteur
-32-
Overview of Java Concurrency Support (5)
 Asynchrony
sets a bit that can be polled
• Asynchronous termination
• event / interrupt handling, ATC
 Interaction with exception handling
• No asynchronous exceptions
• Various thread-related exceptions
• Thread propagating an unhandled exception
 Other functionality
• Thread group, dæmon threads, thread local data
• interrupt()
page 33
Dpt/Auteur
ETR 2011
Overview of Java Concurrency Support (6)
 Standard
Java is not enough to handle real-time
constraints.
 Java (and JVM) lacks semantic for standard realtime programming techniques.
 The lack of confidence in real-time garbage
collection is one of the main inhibitors to the
widespread use of Java in real-time and embedded
systems
 Eg, he RTSJ has introduced an additional memory
management facility based on the concept of
memory areas
page 34
Dpt/Auteur
ETR 2011
Real-time Spec. for Java (RTSJ)
 IBM,
Sun and other partners formed Real-time for
Java Expert Group sponsored by NIST in 1998.
 It came up with RTSJ to fill this gap for real-time
systems.
 http://www.rtsj.org/
 RTSJ proposed seven areas of enhancements to
the standard Java.
page 35
Dpt/Auteur
ETR 2011
Real-time Spec. for Java (RTSJ)
1.
2.
3.
4.
5.
6.
7.
page 36
Thread scheduling and dispatching.
Memory management.
Synchronization and Resource sharing.
Asynchronous Event Handling.
Asynchronous Transfer of Control.
Asynchronous Thread Termination.
Physical Memory Access.
Dpt/Auteur
ETR 2011
Overview of POSIX Concurrency Support (1)
 Basic
concurrency model
• A thread is identified by an instance of (opaque) type
pthread_t
• Threads may be allocated dynamically or declared locally
(on the stack) or statically
• Program creates / starts a thread by calling pthread_create,
passing an “attributes” structure, the function that the
thread will be executing, and the function’s arguments
Dpt/Auteur
-37-
Overview of POSIX Concurrency Support (2)
 Lifetime
properties
• Thread starts executing its thread function as result of
pthread_create, concurrent with creator
• Termination
– A thread terminates via a return statement or by invoking
pthread_exit - cleanup handlers are
– Here is how to lock a mutex mut in such a way that it will be
unlocked if the thread is canceled while mut is locked:
» pthread_cleanup_push(pthread_mutex_unlock, (void *) &mut);
pthread_mutex_lock(&mut); /* do some work */
pthread_mutex_unlock(&mut);
pthread_cleanup_pop(0);
Dpt/Auteur
-38-
Overview of POSIX Concurrency Support (3)
• Detachment and recycling
– A thread is detachable or joinable
– A terminated detachable thread is recycled, releasing all
system resources
• No hierarchical relationship among threads
» Created thread has a pointer into its creator’s memory
 danger of dangling references
• Main thread is special in that when it returns it
terminates the process, killing all other threads
- To avoid this mass killings, main thread can pthread_exit
rather than return
page 39
Dpt/Auteur
ETR 2011
Overview of POSIX Concurrency Support (4)
 Mutual
exclusion
• Shared (volatile) data
• Mutexes (pthread_mutex_t type) with lock/unlock
functions
 Coordination / communication
• Condition variables (pthread_cond_t type) with pulsed
and broadcast events
• Semaphores
• Data passed to thread function at pthread_create,
result delivered to “joining” thread at return or
pthread_exit
Dpt/Auteur
-40-
Overview of POSIX Concurrency Support (5)
 Asynchrony
• Thread cancellation with control over immediacy and
ability to do cleanup
 Interaction with exception handling
• Complicated relationship with signals
• Consistent error-return conventions
– The result of each pthread function is an int error code (0
 normal)
– If the function needs to return a result, it does so in an
address (“&”) parameter
page 41
Dpt/Auteur
ETR 2011
Agenda
 Concurrency
based on API or integrated in
languages
 Concurrency expression and issues
• In Ada, Java and POSIX
 Conclusions
 References to know more
page 42
Dpt/Auteur
ETR 2011
Comparison: Basic Model / Lifetime
 Points
of difference
• Nature of unit of concurrency: class, task, function
• Implicit versus explicit activation
• How parameters / results are passed
• What the programmer should perform and
understand !!!
 Methodology / reliability
• Ada and Java provide type checking, prevent
dangling references
Dpt/Auteur
-43-
Comparison: Basic Model / Lifetime
 Flexibility
/ generality
• All three provide roughly the same expressive power
• POSIX allows a new thread to be given its
parameters explicitly on thread creation
• POSIX allows a thread to return a value to a “joining
thread
 Efficiency
• Ada requires run-time support to manage task
dependence hierarchy
page 44
Dpt/Auteur
ETR 2011
Comparison:
communication/synchronization
A
wide spectrum of features:
• Locks, semaphores, monitors
• Protected objects and rendez-vous for Ada
• Various forms of interactions with threads
 Returns of experiences
• Major changes from Ada 83 to Ada 95 : from
rendezvous to lighter mechanisms
• Similar for the definition of RTS Java
page 45
Dpt/Auteur
ETR 2011
Final words ?
 Hard
to compare! And the selection of criteria is
arguable
• Clarity / precision of the concepts
• Teaching and use
• Assumed programmer expertise
• Assumed programmer actions
 => I am back with Ada for teaching concurrency
• Rules and issues can be raised and discussed
• Ada provides several paradigms … and the
transition to Java is straightforward
• GNAT and RTEMS to connect to POSIX
page 46
Dpt/Auteur
ETR 2011
To know more …
A
more complete comparison of features
• http://cs.nyu.edu/courses/fall02
 A. Wellings’ courseware material
• http://www.cs.york.ac.uk/rts/books/RTSbookFourthE
dition/slides/
 POSIX tutorial : B Barney from L Livermore labs
• https://computing.llnl.gov/tutorials/pthreads/
 RTEMS and GNAT
• http://rtems.org/
page 47
Dpt/Auteur
ETR 2011
Great books ...
page 48
Dpt/Auteur
ETR 2011
Web site
 http://public.enst-bretagne.fr/~kermarre/Ada/
 http://public.enst-bretagne.fr/~kermarre/ETR2011
page 49
Dpt/Auteur
ETR 2011