Jean-Yves Didier
email: jean-yves.didier@ibisc.univ-evry.fr

Malik Mallem
email: malik.mallem@ibisc.univ-evry.fr

A New Approach to Detect Potential Race Conditions in Component-based Systems

Keywords: D.2.11 [SOFTWARE ENGINEERING]: Software architectures-Domain specific architectures, D.2.13 [SOFTWARE ENGINEER-ING]: Reusable software-Reusable libraries, D.2.m [SOFTWARE ENGINEERING]: Miscellaneous-Rapid prototyping Components, Race conditions, Heuristic, Augmented Reality, Concrete example

When programming software applications, developers have to deal with many functional and non-functional requirements. During the last decade, especially in the augmented reality field of research, many frameworks have been developed using a component-based approach in order to fulfil the non-functional requirements. In this paper, we focus on such a specific requirement: race conditions issues in component-based systems. We present a heuristic that analyses data flows and detects components that may be subject to race conditions. A toy example introducing the problem and the solution is developed and implemented under the ARCS (for Augmented Reality Component System) framework. We also show the results of our algorithm on real size applications using up to 70 components and compare those results with some obtained by developers who had to make exactly the same work by hand.

INTRODUCTION

Augmented Reality (AR) aims at linking virtual entities with real objects through a combination of dedicated hardware and software. Programming such an application requires several skills. Some are purely related to programming techniques and execution environment. They are called non-functional requirements whereas others are related to techniques more specific to the AR field and are therefore called functional requirements (such as image and signal processing, interactions in mixed reality, virtual reality and computer graphics, content authoring, etc).

As a field of research of a growing interest, many researches have been conducted to propose software frameworks tailored to AR needs aiming at reducing the burden for developers to consider non functional requirements when developing. AR is also technology dependent and thus, piece of software piloting these technologies should be as replaceable as the used technologies. The findings of new algorithms and methods are also driving architectures to more and more modularity and genericity. Over the past decade, many software framework for AR [START_REF] Endres | A survey of software infrastructures and frameworks for ubiquitous computing[END_REF] have been proposed and they use a component-based scheme. Component based solutions are popular in AR framework since they usually propose software architectures that will address most of the non functional requirements of AR such as modularity, genericity, and reusability. To these requirements we can also add distributed computing which is raised by the current hype in cloud computing and multi-threaded computing which is the target of this paper.

Multi-threading is and has been used in the past to build AR software ( [START_REF] Azuma | A motion-stabilized outdoor augmented reality system[END_REF] is an example of such use) because it can reduce the end-to-end latency of an application in the case several input sensors are needed by the system to extract characteristics from its environment. Moreover it can profit from the multicore processor architectures that were introduced in the consumer market since several years ago. Inexperienced programmers usually have difficulties in mastering thread safety and concurrent access issues. Therefore, furnishing tools that relieves programmers from the burden of managing such issues may be an interesting added value.

The remainder of the paper is organised as followed. First, we will present some related component based systems used in the AR field and introduce our own framework named ARCS (for Augmented Reality Component System). Then, in section 3, we will focus on the problem of concurrent access management in component systems and provide some hints about how to solve the problem. The same section will also introduce some of the general purpose techniques found in the literature to detect where race conditions may occur. We will also propose a heuristic that automatically finds components for which concurrent access is an issue. Section 4 will show how such a heuristic and the associated solution can be implemented in our framework in toy case and we will finish by giving the future road-map on this research and conclude.

RELATED AND PREVIOUS WORKS

Component based AR frameworks

Modular software architectures and frameworks for AR have been addressed during these past years by almost thirty different projects of frameworks. The surveys written by Endres et al. and Huang et al. [START_REF] Endres | A survey of software infrastructures and frameworks for ubiquitous computing[END_REF][START_REF] Huang | Mobile augmented reality survey: A bottom-up[END_REF] are quite exhaustive. Therefore, we chose to cite the most prominent component based frameworks.

Amongst these frameworks some are intend to distribute components over a network and thus do not need to manage interference between threads of the same program. This is the case for the StudierStube project led by the Technical University of Vienna [START_REF] Fuhrmann | Fast calibration for augmented reality[END_REF]. Its main principle is that each user has its own workspace that may be partly shared with other users. Similarly, the DWARF [START_REF] Bauer | Design of a component-based augmented reality framework[END_REF] (Distributed Wearable Augmented Reality Framework) project uses decentralised and distributed services. This framework relies on CORBA [START_REF]ObjectManagementGroup[END_REF] (Common Object Request Broker Architecture) to provide services. As an example, each input sensor is associated to a service broadcasting data to other services (that could be filters, rendering loops,...). Each service is described by XML data and can be dynamically linked to the current application, which is seen as a distributed data flow. At start-up, applications only need one component manager. This last one discovers step by step other services in order to integrate them at execution. Some other frameworks are following the same guiding precepts such as the AMIRE (Authoring Mixed Reality) project [START_REF] Dörner | Authoring mixed reality. a component and framework-based approach[END_REF] or MORGAN [START_REF] Ohlenburg | The morgan framework: enabling dynamic multi-user ar and vr projects[END_REF].

Another class of component based frameworks for AR do not rely on distribution mechanisms and thus sometimes involves multithreading programming. For example, Tinmith [START_REF] Piekarski | An object-oriented software architecture for 3d mixed reality applications[END_REF] is a library written to develop mobile AR systems. This framework is based on data-flow description and is a library of hierarchical objects. It manages data-flow from sensors, many data filters and rendering components. Objects written in C++ rely on a callback system and data are serialised using XML. Communications between objects are managed through a data-flow graph. Other frameworks from the same category have been proposed such as VHD++ [START_REF] Ponder | Vhd++ development framework: Towards extendible, component based vr/ar simulation engine featuring advanced virtual character technologies[END_REF], MRSS [START_REF] Hughes | Mixed reality in education, entertainment, and training[END_REF] (Mixed Reality Software Suite) or Avango NG [START_REF] Kuck | Improving the avango vr/ar framework -lessons learned[END_REF].

An AR framework must cope with works in progress and future works built on the present ones. It should be able to integrate technologies of tomorrow in terms of new devices and algorithms. Works in progress would then require flexibility, future works extensibility and future works built on top of current ones reusability. One of the classical answers is to use a component based software architecture because it allows to separate an application into several components, that are, according to Szyperski [START_REF] Szyperski | Component Software -Beyond Object-Oriented Programming[END_REF], "a coherent package of software that can be independently developed and delivered as a unit, and that offers interfaces by which it can be connected, unchanged, with other components to compose a larger system". Another benefit associated to reusability is the ability to rapidly prototype applications.

Previous work: the ARCS framework

ARCS, for Augmented Reality Component System, is a project we started in 2006 [START_REF] Didier | A component model for augmented/mixed reality applications with reconfigurable data-flow[END_REF][START_REF] Didier | Arcs : Une architecture logicielle reconfigurable pour la conception des applications de réalité augmentée[END_REF][START_REF] Ibisc | Arcs: Augmented reality component system[END_REF]. As a framework, it provides several models that should be followed in order to build AR applications. Some choices are made concerning the application model as well as the component model. We describe them in order to introduce later how we will manage concurrent access in such an environment since it is our target framework.

Application model

The ARCS application model describes applications as a set of process (actually a set of threads). Each one of them is controlled by a finite state machine. When the internal state of the statemachine changes, it triggers changes in how components are connected to each other. A set of connections as well as a set of component invocations (in order to initialise them and launch data processing) is called a sheet. According to this, each thread is, at a given time, in a given state that corresponds to an active sheet. Sheets are sharing the same components instantiated from a com-ponent pool. Therefore, components do not belong to any thread in particular so they may be invoked by different threads.

As we said before, each process maintains one active sheet at a time. A sheet activation cycle follows the following steps:

• The controller (state-machine) receives a token (from a component in the active sheet) that will trigger one of its transitions and then change the controller state;

• All components from the current sheet will be disconnected from each other;

• The controller new state corresponds to another sheet. First, some invocations, called pre-connection invocations, are performed on the components to properly initialise them;

• Then connections are established according to the new sheet description;

• Post-connection invocations are finally performed in order to launch the actual processing of data.

Component model

ARCS describes components as entities having signals (outputs) and slots (inputs). The signal/slot mechanism is well known since it is commonly used in graphical user interface libraries such as Qt for instance. It is also deriving from the observer design pattern [START_REF] Gamma | Design patterns. Elements of reusable object-oriented software[END_REF]. Thus, the communication through a signal/slot connection is synchronous. Composition of components can be performed in two different ways: the first one is through connection composition, where a component emits a signal that is processed by a slot from another component. The second one is through invocation composition: a component is passed as a parameter to a slot of another component.

Amongst its specifics, ARCS provides an abstract component model that allows to introduce new component types or new component behavior as long as they respect the signal/slot scheme.

This abstract model includes the following functionalities:

• Instantiation and destruction of the actual component;

• Signal/slot and connection management;

• Serialisation/deserialisation: this is mainly used at the instantiation of the actual components. Deserialisation allows to configure the component according to string contents passed through an XML description of the application.

In order to complete the integration of other component families, the framework has also abstract type factories that parse XML descriptions and instantiate directly objects of the considered type that can be used as parameters of components invocations in order to initialise the latter ones.

These functionalities are also exposed in the dynamic libraries the ARCS engine can load at runtime by parsing XML descriptions of an application. They usually contain:

• Type factories, in order to extend ARCS with new types when needed and serialise them;

• Native component factories that instantiate components handled by the previous version of the engine and that are the privileged components in the framework;

• Family component factories in order to make ARCS compatible with other component systems.

To finish, in technical terms, ARCS is written in C++ language for performance reasons and depends on the Qt library [29].

Handling other non-functional requirements

In ARCS , we decided to develop an engine that is as lightweight as possible. Therefore, the engine in itself does not implement all the non-functional requirements that would be necessary to make all kinds of applications. Nevertheless, it is possible to explore other ways to add non-functional requirements when they are really needed. As an example, we already propose in the framework a mechanism to create distributed applications over a network [START_REF] Chouiten | Component-based middleware for distributed augmented reality applications[END_REF].

As defined here, the ARCS engine is able to create threads and perform different tasks inside these threads but there is no concurrent access management developed in component model. We will now see how it is possible to design and implement such a mechanism in a component based system behaving like ARCS.

MANAGING CONCURRENT ACCESS IN COMPONENT BASED SYSTEMS

Managing concurrent access in component based systems depends on the characteristics of components that are used and their environment. For example, in an environment using CORBA components, concurrent access is managed transparently due to the serialisation mechanisms that occur when the CORBA bus is used. Therefore, we will first outline the main characteristics of the component system on which we will work as a basis for our hypotheses.

Component system main characteristics

We are considering components as stated by Szyperski [START_REF] Szyperski | Component Software -Beyond Object-Oriented Programming[END_REF]. To sum it up, component are pieces of software that are reusable and subject to composition in order to produce the final software.

Here, we will restrain the kind of components we are using. We are interested in components having the following characteristics:

• Components have separated inputs and outputs;

• Even if components are black boxes (i.e. we do not know how it is implemented inside), they adhere to the following internal behaviour: if one an input is triggered, it will trigger outputs synchronously (none to all outputs could be triggered). We call this property internal synchronicity. However, without a thorough analysis of the behaviour of the black box, we do not known which output is triggered by which input. Therefore, we will consider that when an input is triggered, every output is triggered; • Components are communicating synchronously: outputs from a component trigger inputs from another component. Outputs then trigger function calls. This property is the external synchronicity; • Communications are supposed unidirectional: data are flowing from outputs to inputs; • Components are configured by passing arguments to some of their inputs. Inputs may also be used to start processing functions; • Components are black boxes but communication channels (or connections) between components are known and static, that is to say, persistent in time or at least for a known duration.

Such components are also working in a specific execution environment. Concerning this execution environment, we make the following suppositions:

• It is multi-threaded;

• Component configuration and initialisation may be performed by different threads;

Problem statement: concurrent access

Now that we have described the main characteristics of our component system and its execution environment, we can deduce some problems that will rapidly arise: how can we process issues concerning concurrent access or, more generally, thread-safety ?

There are at least three solutions in order to give a thread-safety property to such a system: 1. We can systematically implement thread safety mechanisms inside components. However, it is generally costly, especially if the component, in its execution context, does not require it;

2. We can implement it by hand in components that may be subject to concurrent access. The weak point here is that a component is a piece of reusable software and therefore it may be put in a situation that was not planned during the design phase of the component;

3. We implement a specific heuristic inside the execution environment that will ensure that components that are subject to concurrent access in their execution context will be guaranteed thread safe. This third way is the one we would like to investigate further in this paper.

Restated in other terms, we would like to give a thread-safe behaviour to components (that do not possess it) by analysing their execution context. We believe it has other strong advantages, one of them being that component developers would not have to worry about thread safety. This is also interesting because inexperienced programmers usually have difficulties in mastering thread safety and concurrent access issues.

Outline of our solution

The idea we will express here is just an intermediate solution that will give some hints on how the problem could be solved. We intend to give a simple, but practical solution. The main idea is to construct a wrapper component that will regulate concurrent access to the component it shelters. To achieve this, we apply the monitor object design pattern [START_REF] Schmidt | Pattern-Oriented Software Architecture, volume 2: Patterns for Concurrent and Networked Objects[END_REF] as it is done, for instance, in java with the synchronized keyword. Components prone to concurrent access are then considered as a resource that will be properly framed inside a mutual exclusion (mutex) as represented in figure 1. For each component to protect from concurrent access, a Monitor will be generated, associated to an object managing a mutual exclusion (Mutex). Therefore, each call performed on Component is rerouted to Monitor.

Mutual exclusion are known to solve partly the problem of race conditions but they are known to be sensitive to other problems such as deadlocking (where two components are waiting for each other and thus are locking each other, therefore the application cannot perform its intended task) or resource starvation (it occurs when two components are competing for the same resource and one of them is perpetually favoured over the other, thus tasks that were intended to be performed never happen). It would require another detailed analysis that we do not intend to present in this paper.

Our problem is then transformed into how to determine which component should be monitored? Before proposing a heuristic in order to solve it, we will briefly review some techniques used to solve such a problem.

Concurrent access in literature

In the literature, two complementary problems are addressed: the race detection in itself and the minimal number of places where mutual exclusion should be placed.

Race detections are detected using different approaches. The static approach enforce type systems [?], directly analyse the source code of the application [START_REF] Sterling | Warlock-a static data race analysis tool[END_REF][START_REF] Pratikakis | Locksmith: context-sensitive correlation analysis for race detection[END_REF][START_REF] Voung | Relay: static race detection on millions of lines of code[END_REF] or analyse dataflow [START_REF] Engler | Racerx: effective, static detection of race conditions and deadlocks[END_REF]. Such approach is not directly usable since we do not have access to the source code of components in every situation. The dynamic approach analyse actual execution traces. Algorithms and tools [START_REF] Savage | Eraser: A dynamic data race detector for multithreaded programs[END_REF][START_REF] Banerjee | A theory of data race detection[END_REF][START_REF] Pozniansky | Multirace: efficient on-the-fly data race detection in multithreaded c++ programs[END_REF][START_REF] Flanagan | Fasttrack: efficient and precise dynamic race detection[END_REF] developed mainly rely on Lamport's happens-before relation [START_REF] Lamport | Time, clocks, and the ordering of events in a distributed system[END_REF] or use lockset analysis (a lock set is the set of locks that protect access to a shared variable). The tools have complete access to program context but will also reduce the performances of the program actually analysed and adds to the overhead of running components. Other techniques are also used such as post-mortem analysis but they are not suitable in our case.

Finding the minimal number of places where mutual exclusion should be placed is often called the Minimum Lock Assignment (MLA) problem. Many solutions have been proposed so far to determine where to put mutual exclusions. However, they usually concern parts of the software code (the potential critical sections) and not components as defined by Szyperski as we can see in [START_REF] Sreedhar | A new framework for analysis and optimization of shared memory parallel programs[END_REF][START_REF] Halpert | Component-based lock allocation[END_REF][START_REF] Emmi | Lock allocation[END_REF][START_REF] Zhang | Minimum lock assignment: A method for exploiting concurrency among critical sections[END_REF]. In such methods, critical parts of the code are annotated. Then a special compiler will determine where to put mutual exclusion by using special heuristics. MLA is known to be a NPhard problem so other methods rely on a different approach: the idea is to determine specific use cases and associated use case scenarios and assess the behaviour of the software with respect to this scenario [START_REF] Eytani | Heuristics for finding concurrent bugs[END_REF][START_REF] Long | A method for verifying concurrent java components based on an analysis of concurrency failures[END_REF]. If an interference is detected, then a mutual exclusion will be put where it occurred. Using use-case scenarios is not a solution that suited our needs since it needs some preparations. Determining MLA is also not our primary concern: the idea is not to be optimal but to relieve the developer from the burden to review his code in order to determine where to put mutual exclusions. The method must also be lightweight, since it should be run on the fly when the description of the application is loaded by our framework's engine. Fortunately, one of the conclusions in [START_REF] Halpert | Component-based lock allocation[END_REF] is that "high accuracy in program analysis is not always necessary to achieve generally good performance". Therefore, we will provide a heuristic at component level that determines which components might be subject to interference.

A heuristic to find components subject to race conditions

To determine the solution of our problem, we construct a direct graph. Each vertex of the graph represents a component to which is associated a set of labels (the different threads in the application are also considered as components). Each time components are communicating together, a directed edge between the vertices associated to the components is drawn. The direction of the edge matches the direction of the communication.

We will now expose a heuristic that will determine what are the candidate components subject to monitoring.

Notations

• Let C be the set of components in the system. This set is also the set of vertices in the directed graph; • Let M = ∅ be the set of components that will be candidates to mutual exclusion monitoring; • Let L be a set of labels. At initialisation, there are as much labels as threads in our system. L is very likely to grow, so the easiest way is to define L as a subset of N where L = 1; n where n is the number of threads; • Let E be the set of edges of the directed graph;

• Each component c of C has a property named labels which will be noted c.labels. It is the set of labels associated to the component c. c.labels is therefore a subset of L; • Each edge e of E has two properties: e.head is the head of the edge and e.tail is the tail of the edge. Note that e.head and e.tail are elements of C; • |S| is the cardinal number of the set S;

An algorithm to find components to monitor

Our heuristic is exposed in algorithm 1. Apart from its initialisation, the heuristic is a loop iterating over three phases:

1. The propagation of labels along the edges (lines 14 to 20); 2. The marking, where candidate components subject to monitoring are marked (lines 22 to 24); 3. The pruning and label generation where some of the components are discarded because they do not need to be monitored with a mutual exclusion. Additional labels are created and labels associated to vertices are reinitialised (lines 25 to 35).

These steps are reiterated until the set of components to monitor is computed.

The initialisation consists in generating the first set of labels (noted L in the algorithm) and attach them with components considered as threads. Each component that is a thread is initialised with its own label and all other components are associated to an empty set of labels.

The propagation propagates labels along the edges until the label sets associated to each vertex is stabilised. Therefore, we know which thread can access to which component. It corresponds to the internal and external synchronicity hypothesis: if a thread accesses to an input, therefore it accesses to all corresponding outputs of the same components and inputs that are connected to these outputs.

The marking step creates a temporary set of components (noted Mc) and puts into it components that are very likely to monitor. To find such components, we look at the incoming edges. If the originating component of such an edge is not accessed by the same threads than the target component of the same edge, then it means the component is subject to concurrent accesses and is to be added to the list of components to monitor.

The pruning step removes from study the set of components that are accessed by at most one thread since they are not concerned by concurrent access issues and the edges that come along. Each component that was marked to be monitored is generating a new label (it means we consider the data sent by it thread-safe since it is monitored and therefore it behaves as the data was sent by another thread) and all other components associated labels are reset.

Then we reiterate until there is not any component left to process.

Applying the heuristic: an abstract example

Figure 2 is illustrating how our heuristic is run. At first, we consider the set of components displayed in 2(a). We introduce in figure 2(b) two new components T1 and T2 that are actually the threads that start the application by performing invocations on components A and B. The label set associated to each component is noted between braces. Therefore, components T1 and T2 are associated to labels 1 and 2 and other components are associated to an empty label set. According to our heuristic, we then perform a first propagation and marking step (see figure 2(c)). Two components are noted as being subjects to monitoring, here C and D (they are noted with a star * ). They are marked because preceding components do not share the same set of labels. Then, in the pruning phase (figure 2(d)), the components T1, T2, A and B are discarded since they all have only one label associated to them (it means they do not need to be monitored). New labels are generated for C and D that are respectively 3 and 4 whereas other components are associated to empty label sets. We then reiterate through the same steps a second (figure 2(e)) and a third time (figure 2(f)). At the end of the third iteration, since we had a cycle in the graph, all components are associated to empty label sets (figure 2(g)), therefore the algorithm completes in the next step. If we look at the set of components to monitor computed by the algorithm, we will find M = {C, D, E}. This result is consistent since components C and D can be accessed through A and B that are invoked by two different threads. The outputs of C and D can come from the first or the second thread, therefore E needs to be monitored too.

Another side effect illustrated in this example is that mutual exclusions should be re-entrant. That is to say, a thread that has locked a mutual exclusion should still be able to enter in the component it has locked a second time. If this condition is not respected, it could lead to a lock in our abstract example since we have a communication cycle between D, E, G and F . Therefore, D can be locked by a thread and the same thread may access to D later through E, G and F .

CONCURRENCY MANAGEMENT APPLIED IN ARCS 4.1 A toy case introducing a race condition

In order to understand how it works, we will not consider a real AR application but rather a toy case implementing a race condition. It is organised around three main components: two components (named loop1 and loop2), each in a separate thread, iterate from 0 to 9, and one component (named sum) adds all iteration values received from the two other components. The components are, by default, developed without any code that synchronises them (Fig. 3 is showing their pseudo-code). Therefore, our sum component, which should reach a total of 90 (2 × 9 i=0 i), does not necessarily reach the right sum in a multi-threading context (the counting slot is called from two different threads and therefore tmp and sum are in a race condition situation).

The ARCS framework strictly adheres to the component system and environment characteristics we presented in section 3.1. But, as a practical framework, it will require some adjustments and additional components in order to conform to its application model. Figure 4 represents the simplified connection graph of the toy case (as implemented using ARCS -see also figure 5) where we can find the main components as well as thread controllers (state-machines s, s1 and s2 which are mandatory in the application model 1 . Here 1 One can notice difference between the abstract data flow and the one presented in the screen capture. This is due to the fact the s,s1 and s2 are only composed of two states: one initial and one final state in order to shut down the application). Some logical glue components are also used: end which triggers the end of the application when loop1 and loop2 have finished iterating, and display which displays the final result. s, s1 and s2 are controllers that may be accessed by different threads. A first thread triggers loop1 and a second thread triggers loop2. Therefore, if we apply our heuristic, components end, sum should be monitored. To this set, we will add s, s1 and s2 since they may be accessed bu different threads.

The result of the implementation of the components without any management of concurrent accesses is shown in figure 6(a). As we can observe, the two threads are sleeping a random duration and wake up in order to send data to the sum component. In the end, it displays 92 as a result of the sum whereas it should have been 90 if there was not any race condition.

In order to implement concurrency access management, ARCS also requires some other components that are not shown: a Monitor component that acts as a wrapper component for the actual components that have been marked as to be monitored and a Concurren-cyManager component that accesses to the application structure, analyses it and compute the set of components to monitor. The application has been modified to import the ConcurrencyManager component (it results in modifying one line in the application description file).

We can verify in figure 6(b) that Monitors have been put around the right components and that the race condition was suppressed by such modifications. Indeed, the first lines of the screenshot shows the resulting list of components that should be monitored as planned by our heuristic. The last lines indicate that the resulting sum is 90 which means the race condition has been suppressed.

None of the components of the application has specific code for handling mutual exclusion, therefore the ConcurrencyManager seems viable in order to manage concurrency on components that were not specifically designed to handle it. We then have built a first step towards automated concurrency management for components in software applications. heuristic takes into account all connections in all application sheets (in ARCS terms) whereas the screen capture represents one of those sheets, therefore a subset of the connections between components. In the past, we developed for the RAXENV project [START_REF]The raxenv project[END_REF][START_REF] Zendjebil | Large scale localization for mobile outdoor augmented reality applications[END_REF] a multisensor system that relied on multi-threading capabilities. This project aimed at demonstrating the practical use of an outdoor AR system for environmental sciences and techniques, both in terms of technology development as well as end-user adoption.

The overall software architecture is depicted in figure 7. The application used data provided by three different sensors: a camera, an inertial unit and a GPS. Data sources were fused to provide a robust localisation of the system in its environment. During the development of such a system, we encountered some difficulties with multi-threading (each sensor provided data in a separate thread) and concurrency management that was implemented by hand. We would like to run our present solution over the RAXENV software in order to assess if concurrency management was implemented at the right place and see if it could eventually be performed in less components than we did and maybe raise some issues we did not see.

The RAXENV software had three nominal states (corresponding to three sheets) where multi-threading capabilities had been enabled. This means our algorithm should then be applied to these three sheets in order to determine which components should be monitored. Moreover, some of the components were composite components (components made of an assembly of components). So we ran our algorithm against two series of tests: one with composite components considered as blackbox components (annotated BB) and another one where composite components are considered as whiteboxes (annotated WB -therefore we consider that we can monitor subcomponents of composite components). The numerical results are gathered in table 1 where we also included our algorithm's result concerning the abstract example and the toy case we presented earlier. The table contains the number of components, the number of edges of the generated graph as well as the final size of the label set, the number of iterations and finally either the size of the component set to monitor or the component set itself. We also represented in Fig. 8 one of the component set (the one annotated MIBB) using the dot utility from graphviz software2 . It also shows the composite components and components that are to be monitored. One can notice that these first results show that few iterations are in fact needed in order to determine the set of components to be monitored even for datasets containing up to 70 components and 140 edges. In table 2, we regrouped the results obtained from our algorithm, especially the list of components subject to monitoring, for the three datasets RIBB, MIBB and VPBB coming from the actual implementation of the RAXENV software application. For each component, the table states if it should be monitored (Yes) or not (No) or if it was not used in the dataset (marked with a cross). It exhibits for three components in the list that they should be monitored in some datasets but not in all datasets. It means the very same instance of a component can be subject to monitoring or not depending on the actual state of the application. This is interesting because it is an actual example of a situation where an implementation by hand to make a component thread-safe would lead to a situation where the code written to solve concurrency problems may be useless therefore consuming memory and computation time for nothing.

Interestingly, we compared these results to what was really implemented at that time by developers. Data were only available for the MIBB, RIBB and VPBB dataset and we recorded the differ- ences we found out into the implementation and the results provided by our algorithm (see table 3). We counted the number of unprotected components, that is to say components our algorithm marked as subject to be monitored whereas developers did not implemented any thread-safe mechanism, the number of overprotected components (components for which developers have implemented unneeded thread-safe mechanisms) and computed the ratio of the total of such differences to the number of components used in each dataset. One of the most striking result is that we obtained a difference ratio of 25%. This may seem quite high but it does not mean that developers had made mistakes in all situations : one of the prominent problem is that, at that time, mechanisms to monitor composite components were not available whereas it was the kind of components we needed to monitor in this application (It also means that developers did not have, at that time, means to write completely thread safe applications). Another thing to take into consideration is the fact that developers have access to the internals of components and consider them as whiteboxes. Therefore, their analysis may slightly differ than the one from our algorithm because some components may not need to be monitored due to their internal structure. However, overprotected components can be considered as avoidable mistakes.

Discussion and further work

Concerning our algorithm many things may be subject to discussion. For example, a lot of formal work is still needed in order to assess the complexity of our algorithm as well as proving that it converges in all situations.

Another thing to keep in mind is that our algorithm is only indicating which components are assumed to be monitored. It raises then several other issues. The first one is about the automation of a solution to build monitors at runtime for these components. In some situations, especially if we use the monitor design pattern, we may reach a deadlock situation (when two thread lock components that are needed by each other), therefore a further analysis is needed to detect these situations or we should cast away the monitor paradigm and use another one. However, even if the tool is not fully automated at the execution, the results it produces are interesting for developers since the obtained component set indicates where developers have to focus in order to detect race conditions in their software application.

The last thing we would like to keep in mind is that it may also be interesting to adapt our algorithm in case we may have finer indications of the behaviour of components (i.e. when components are considered as white boxes instead of black boxes). We may then need to write a specific parser and decompose components in several independent vertices in order to build the graph needed by our algorithm.

CONCLUSION

We introduced in an actual component based AR framework some automated concurrency management mechanism. To achieve this, we rely on the monitor object design pattern as well as a heuristic that computesš the components that must be monitored. Applied on a toy case in the ARCS framework, it gave satisfactory result. Therefore we believe that it could be implemented in a larger scale on an actual complex AR application or, more generally, for any component based software using a similar model to the one we presented.

The algorithm was also used on actual data coming from a concrete application and exhibited some differences with the actual implementation made by developers, providing hints about the places where race conditions may occur.

In the future some loose ends associated to concurrency should also be addressed such the problem of deadlock or resource starvation in order to bring out a complete automated concurrency management system that would relieve the developer to determine it and implement it by hand. Therefore, he can focus and spend more time on the functional requirements of software applications.

Figure 1 :

 1 Figure 1: Behaviour of a monitor component wrapping the original component in a mutual exclusion.

Algorithm 1 : 5 if c represents a thread then 6 l ← l + 1 ; 7 L

 15617 Heuristic to determine components to monitor Data: C -set of components, E -set of edges Result: M -the set of components to monitor// Initialization 1 M ← ∅; 2 L ← ∅; 3 l ← 1; 4 foreach c ∈ C do

Figure 2 :For

 2 Figure 2: Iterations of our heuristic from initialization to the last step before completion

Figure 3 :Figure 4 :

 34 Figure 3: loop and sum components pseudo-code.

Figure 5 :

 5 Figure 5: Toy case in development stage using ARCS graphical editor

  (a) Execution of the toy case without concurrency access management (b) Execution of the toy case with concurrency access management

Figure 6 :

 6 Figure 6: Toy case implemented and executed using the ARCS framework

Figure 7 :

 7 Figure 7: Global interaction between ARCS and RAXENV software modules

Figure 8 :

 8 Figure 8: Components configuration in dataset labelled MIBB

Table 1 :

 1 Results gathered from our algorithm ran on different data sets

	Dataset		Components Edges |L| Iterations Duration	M / |M|
	Abstract example		9	12	6	7	3 ms	C, D, E
	Toy case		11	15	11	3	3 ms	End, Sum, s, s1, s2
	Raxenv: reinitialisation (BB) -RIBB		28	34	14	4	4 ms ss_d, widget, iBuf, gm, tc
	Raxenv: manual initialisation (BB) -MIBB	40	62	27	5	4 ms	9
	Raxenv: vision predominance (BB) -VPBB	38	53	29	5	4 ms	10
	Raxenv: reinitialisation (WB)		35	50	14	4	4 ms ss_d, widget, iBuf, gm, tc
	Raxenv: manual initialisation (WB)		72	145	71	7	20 ms	21
	Raxenv: vision predominance (WB)		59	112	44	7	12 ms	19
	Sensors
	GPS
	Camera
	Inertial
	Component libraries
	(registration)
	ARCS engine	Elkano (main loop,rendering)
	ARCS thread		Main thread
	RAXENV Software
	XML description

Table 2 :

 2 Name In M RIBB In M MIBB In M VPBB Recurring components to monitor in RIBB, MIBB and VPBB datasets.

	ss_d	Yes	Yes	Yes
	widget	Yes	Yes	Yes
	iBuf	Yes	No	Yes
	gm	Yes	Yes	Yes
	tc	Yes	Yes	Yes
	tmp1	×	Yes	Yes
	visP	×	Yes	Yes
	isa	×	Yes	×
	gm2	×	Yes	×
	rinit	No	Yes	Yes
	gm3	×	×	Yes
	alP	No	No	Yes
	chrono	×	×	Yes
	Dataset		RIBB MIBB VPBB
	Components unprotected	2	5	6
	Components overprotected	2	5	2
	Differences: total	4	10	8
	Differences ratio	14%	25%	21%

Table 3 :

 3 Comparison with implementation by hand

http://www.graphviz.org


Lova Zakariasy
email: lova.zakariasy@ist-antsiranana.mg

Issam Louhichi

Fanilo Randriamahaleo
email: fanilo.randriamahaleo@math.u-bordeaux1.fr

On the commutativity of a certain class of Toeplitz operators

Keywords:

One of the major goals in the theory of Toeplitz operators on the Bergman space over the unit disk D in the complex place C is to completely describe the commutant of a given Toeplitz operator, that is, the set of all Toeplitz operators that commute with it. Here we shall study the commutants of a certain class of quasihomogeneous Toeplitz operators de ned on the harmonic Bergman space.

Introduction

Let L = L (D, dA) denote the space of all square integrable functions in the open unit disk D with respect to the normalized Lebesgue area measure dA = rdrdθ, where (r, θ) are the polar coordinates. The harmonic Bergman space, denoted by L h , is the set of all harmonic functions on D that are in L . It is well known that L h is a closed subspace of L , hence it is a Hilbert space with an orthonormal basis { √ n + z n } ∞ n= ∪ { √ n + z n }. Let Q be the orthogonal projection of L onto L h . A Toeplitz operator T f on L h with symbol f is de ned by

T f (u) = Q(fu), for u ∈ L h .
Clearly if the symbol f is bounded then T f is bounded on L h . However, dealing only with bounded symbols is restrictive, as an unbounded function might be a symbol of bounded Toeplitz operator. So if f ∈ L (D, dA), the Toeplitz operator T f is densely de ned on L h as an integral operator T f (u) = D f (w)u(w)Rz(w)dA(w), for u ∈ P(z, z), where Rz(.) is the reproducing kernel of L h and P(z, z) is the set of polynomials in z and z. In this paper we consider the symbols in L (D, dA) for which the Toeplitz operator de ned as above can be extended to a bounded operator on L h .

A symbol f is said to be quasihomogeneous of degree p if it can be written as f (re iθ ) = e ipθ ϕ(r), where ϕ is a radial function on D. In this case, the associated Toeplitz operator T f is also called quasihomogeneous Toeplitz operator of degree p. Analogous quasihomogeneous Toeplitz operators, de ned on the analytic Bergman space, have been extensively studies over the last decade. See for example [2-5, 9, 10]. Recently in [START_REF] Louhichi | Quasihomogeneous Toeplitz operators on the harmonic Bergman space[END_REF], Louhichi and Zakariasy investigated products of quasihomogeneous Toeplitz operators on the harmonic Bergman space while generalizing the results of Dong and Zhou in [START_REF] Dong | Products of Toeplitz operators on the harmonic Bergman space[END_REF]. This paper is a continuation of the work started in [START_REF] Louhichi | Quasihomogeneous Toeplitz operators on the harmonic Bergman space[END_REF]. Here we plan to study the commutativity of the product of two quasihomogeneous Toeplitz operators whose degrees are of opposite sign.

Preliminaries

Our main tool in studying quasihomogeneous Toeplitz operators is the Mellin transform. Let f be a radial function in L ([ , ], rdr). The Mellin transform f of f is de ned by

f (z) = f (r)r z-dr = M(f )(z).
It is well known that, for these functions, the Mellin transform is well de ned on the right half-plane {z : ℜz ≥ } and is analytic on {z : ℜz > }. We also de ne the Mellin convolution of two functions f and g in L ([ , ], rdr) by

(f * M g)(r) = f (t)g( r t ) dt t .
It is easy to see that the Mellin transform converts the Mellin convolution product into a pointwise product, that is,

(f * M g)(z) = f (z) g(z).
Hereafter, the Mellin transform f is uniquely determined by its values on any arithmetic sequence of integers, according to the following Lemma [12, p.102

(pk + n ) = for all k ∈ N, then f (z) = for all z ∈ {z : ℜz > } and so f = .
We shall often use [7, Lemma 2.5 p.1767] which can be stated as follows.

Lemma 2. Let p be an integer and ϕ be a bounded radial function. For each k ∈ N,

T e ipθ ϕ (z k ) = ( k + p + ) ϕ( k + p + )z k+p if k ≥ -p (-k -p + ) ϕ(-p + )z -k-p if k < -p, T e ipθ ϕ (z k ) = ( k -p + ) ϕ( k -p + )z k-p if k ≥ p ( p -k + ) ϕ(p + )z p-k if k < p.
The next lemma is a direct application of Lemma 2.

Lemma 3. Let p, s be two positive integers and ϕ, ψ be radial functions. If

T e ipθ ϕ T e -isθ ψ = T e -isθ ψ T e ipθ ϕ , then the following equalities hold :

-For k ≤ |s -p| : p ≤ s :(k + p + ) ϕ( k + p + ) = (s -k + ) ϕ( s -k -p + ) (2.1) p > s :(k + s + ) ψ( k + s + ) = (p -k + ) ψ( p -k -s + ) (2.2)
-For max( , s -p) ≤ k < s :

(k + p + ) ϕ( k + p + ) ψ( k + p -s + ) = (s -k + ) ϕ(p + ) ψ(s + ) (2.3) -For max( , p -s) ≤ k < p (k + s + ) ϕ( k + s -p + ) ψ( k + s + ) = (p -k + ) ϕ(p + ) ψ(s + ) (2.4)
-For k ≥ s :

(k + p + ) ϕ( k + p + ) ψ( k + p -s + ) = (k -s + ) ϕ( k -s + p + ) ψ( k -s + ) (2.5)
-For k ≥ p :

(k -p + ) ϕ( k -p + ) ψ( k -p + s + ) = (k + s + ) ϕ( k + s -p + ) ψ( k + s + ) (2.6)

Results

In [START_REF] Louhichi | Quasihomogeneous Toeplitz operators on the harmonic Bergman space[END_REF], the uniqueness of the commutant is proved when both quasihomogeneous Toeplitz operators are of positive degree. A similar result is obtained by the next theorem, when the degrees of the Toeplitz operators are of opposite sign.

Theorem 1. Let p, s be two positive integers and ψ be a non-constant radial function. If there exists a nonconstant radial function ϕ such that T e ipθ ϕ commutes with T e -isθ ψ , then ϕ is unique up to a multiplicative constant.

Proof. Assume there exist two non-constant radial functions ϕ and ϕ such that both T e ipθ ϕ and T e ipθ ϕ commute with T e -isθ ψ . Then Equation (2.5) implies that for all k ≥ s :

(k + p + ) ϕ ( k + p + ) ψ( k + p -s + ) = (k -s + ) ϕ ( k -s + p + ) ψ( k -s + ), (3.1)
and

(k + p + ) ϕ ( k + p + ) ψ( k + p -s + ) = (k -s + ) ϕ ( k -s + p + ) ψ( k -s + ). (3.2)
From these equalities, we obtain

ϕ ( k + p + ) ϕ ( k -s + p + ) = ϕ ( k -s + p + ) ϕ ( k + p + ) for all k in the set Z = {k ≥ s : ψ( k + p -s + ) ψ( k -s + ) ≠ }. Clearly, k∈Z k = ∞ because ψ is not
identically null. Now using Lemma 1, we complexify the equation above and we obtain

ϕ (z + s) ϕ (z) = ϕ (z) ϕ (z + s) for ℜz > .
Therefore [8, Lemma 6 p.1468] implies that ϕ = cϕ for some constant c.

In [START_REF] Louhichi | On Toeplitz operators with quasihomogeneous symbols[END_REF], it is established that nontrivial quasihomogeneous Toeplitz operators with quasihomogeneous degrees of opposite signs do not commute on the analytic Bergman space of the unit disk. Here we shall demonstrate that it is not the case for the analogous Toeplitz operators de ned on L h . Proof. If T e ipθ ϕ commutes with T e -isθ r n , then

T e ipθ ϕ T e -isθ r n (z k ) = T e -isθ r n T e ipθ ϕ (z k ), for all k ≥ , (3.3)
and

T e ipθ ϕ T e -isθ r n (z k ) = T e -isθ r n T e ipθ ϕ (z k ), for all k ≥ . (3.4)
By Lemma 2 and since r n (z

) = z + n , equation (3.3) implies that • If k ≥ s k -s + k -s + n + ϕ( k -s + p + ) = k + p + k + p -s + n + ϕ( k + p + ), (3.5)
• If k < s s -k + s + n + ϕ(p + ) = k + p + k + p -s + n + ϕ( k + p + ). (3.6)
On the other hand, equation (3.4) implies that

• If k ≥ p k + s + k + s + n + ϕ( k + s -p + ) = k -p + k -p + s + n + ϕ( k -p + ), (3.7)
• If p -s ≤ k < p k + s + k + s + n + ϕ( k + s -p + ) = p -k + s + n + ϕ(p + ), (3.8)
• If ≤ k < p -s k + s + k + s + n + = p -k + p -k -s + n + . (3.9)
It is easy to see that equation (3.5) can be obtained from equation (3.7) by substituting k by k + p -s. So we shall proceed using equation (3.7) to determine the form of the radial symbol ϕ. By setting z = k -p + , we complexify equation (3.7) and we obtain

z + p + s z + p + s + n ϕ(z + p + s) = z z + s + n ϕ(z + p), for ℜz > .
Here, we notice that the function de ned by

f (z) = z + p + s z + p + s + n ϕ(z + p + s) - z z + s + n ϕ(z + p)
is analytic and bounded in the right-half plane and vanishes at z = k -p + for any k ≥ p. Hence, by Lemma 1, we have f (z) ≡ . Therefore, we obtain that in the right half-plane

r p ϕ(z + s) r p ϕ(z) = z(z + p + s + n) (z + s + n)(z + p + s)
, for ℜz > .

(3.10)

Since n = ( m + )s and using the well-known identity Γ(z + ) = zΓ(z), where Γ is the Gamma function, equation (3.10) can be written as

r p ϕ(z + s) r p ϕ(z) = F(z + s) F(z) for ℜz > , (3.11)
where

F(z) = Γ( z s )Γ( z s + p s + m + ) Γ( z s + m + )Γ( z s + p s + )
. Next, equation (3.11), combined with [8, Lemma 6 p. 1468], implies there exists a constant C such that r p ϕ(z) = CF(z), for ℜz > .

(3.12)

Now, we shall show that F(z) is the Mellin transform of a bounded function. Using the well-known property of the Gamma function namely

Γ(z + n) = (z + n -)(z + n -) . . . zΓ(z) for n ∈ N,
and after simpli cation, we obtain that

F(z) = ( z s + p s + m -)( z s + p s + m -) . . . ( z s + p s + ) ( z s + m)( z s + m -) . . . z s ,
which is a proper fraction in z and can be written as sum of partial fractions

F(z) = m j= a j z + js = m j= a j r js (z).
Hence, equation (3.12) and Remark 1 imply that

ϕ(r) = m j= c j r js-p .
At this point, we observe that the rst term r -p in the expression of ϕ(r) is in L (D, dA), and therefore T e ipθ ϕ is a bounded Toeplitz operator, if and only if p = . Since by hypothesis we assumed p ≥ s > , we must have p = s = . Finally, it is easy to verify that with p = s = equation (3.9) is satis ed, and also that the function

ϕ(r) = m j=
a j r j-satis es equations (

.

Remark 2.

It is well known that on the analytic Bergman space of the unit disk, non-trivial anti-analytic Toeplitz operators (resp. analytic Toeplitz operators) commute only with other such operators. Theorem 2 tells us that it is not the case in L h . In fact if we take m = , we see that T z commutes with T ϕ where ϕ(z) = z .

Moreover, the symbol ϕ is obviously not bounded, but it is the so-called "nearly bounded symbol" [1, p 204]. Hence T ϕ is bounded.

The next theorem is a slight generalization of the previous one.

Theorem 3. Let p be a positive integer and ϕ, ψ be nonzero radial functions. If T e ipθ ϕ commutes with T e -ipθ ψ , then p is equal to 1 and ϕ, ψ satisfy the following Mellin convolution equation

ϕ * M ψ = C r -r ,
where C is a constant.

Proof. If T e ipθ ϕ commutes with T e -ipθ ψ , then the equalities in Lemma 3 (with p = s) are reduced to two main equations:

-for all ≤ k < p,

(k + p + ) ϕ( k + p + ) ψ( k + p + ) = (p -k + ) ϕ(p + ) ψ(p + ); (3.13)
-for all k ≥ p,

(k -p + ) ϕ( k -p + ) ψ( k -p + ) = (k + p + ) ϕ( k + p + ) ψ( k + p + ). ( 3
M (r p ϕ * M r p ψ) (z + p) M (r p ϕ * M r p ψ) (z) = F(z + p) F(z) , (3.16)
where F is the function de ned by

F(z) = Γ z p Γ z p +
, and Γ is the Gamma function. Using the well-known identity Γ(z + ) = zΓ(z), we can write

F(z) = z(z + p) = z -z + p = ( -r p )(z),
where denotes the constant function with value one. Now, Equation 3.16 combined with [8, Lemma 6 p.1468] implies the existence of a constant C such that

M(r p ϕ * M r p ψ)(z) = CF(z) for ℜz > . Therefore ϕ * M ψ = C( r p -r p ).
Finally, it is easy to see that this Mellin convolution (as a function) is in L ([ , ], rdr) if and only if p = , and that in this case Equation (3.13) is satis es.

Remark 3. As an example one can show that, if α ≥ -is an integer and if T e -iθ r α commutes with T e iθ ϕ , then

ϕ(r) = α + r -(α -)r .
In particular, if α = we obtain the example of Remark 2.

Now we shall consider the case when p < s. where the matrix A is of size s × (m + ) and its entries are given by

a kj = k + k + js + - s -k + s -k + js ,
for ≤ k ≤ s -and ≤ j ≤ m. Clearly the s rows of the matrix A are linearly independent. Thus

• if s ≤ m + , the homogeneous system (3.18) has less equations than unknowns and therefore it has a nontrivial solution i.e., the c j are not all equal to zero. • if s > m + , (3.18) has more independent equations than unknowns and hence c j = for all ≤ j ≤ m i.e., ϕ ≡ .

Theorem 2 .

 2 Let p, s, m and n be four integers such that p ≥ s > , m ≥ and n = ( m + )s. If there exists a nonzero radial function ϕ such that T e ipθ ϕ commutes with T e -isθ r n , then p = s = and ϕ(r) = m j= c j r j-.

. 14 )

 14 We complexify Equation (3.14) by letting z = k -p + and we obtain z ϕ(z + p) ψ(z + p) = (z + p) ϕ(z + p) ψ(z + p), for ℜ(z) > .(3.15)Using the multiplicative property of the Mellin convolution, Equation (3.15) is equivalent to

Theorem 4 .

 4 Let p, s, m, and n be integers such that < p < s, m ≥ and n = ( m + )s. Assume there exists a radial function ϕ such that T e ipθ ϕ commutes with T e -isθ r n . Then p = and-ϕ(r) = m j= c j r j-if s ≤ m + , -ϕ ≡ if s > m + .Proof. Assume that T e ipθ ϕ commutes with T e -isθ r n . Then, by a similar argument as in the proof of Theorem 2, we show that p = and ϕ(r) = m j= c j r js-. Moreover, Lemma 3 implies that(k + ) ϕ( k + ) = (s -k + ) ϕ( s -k + ) for all ≤ k ≤ s -, which is equivalent to (k + ) m j= c j k + js + = (s -k + ) m j= c j s -k + js, for all ≤ k ≤ s -.(3.17) Now, the s equalities given by Equations (3.17) can be written as a homogeneous linear system in the following way

  ].

	Lemma 1. Suppose that f is a bounded analytic function on {z : ℜz > } which vanishes at the pairwise distinct points z , z • • • , where
	i) inf{|zn|} >
		and
	ii)	n≥ ℜ( zn ) = ∞.
	Then f vanishes identically on {z : ℜz > }.
	Remark 1. Now one can apply this theorem to prove that if f ∈ L ([ , ], rdr) and if there exist n , p ∈ N such that
		f

Unauthenticated | 192.139.15.33 Download Date | 6/20/14 10:42 AM

Acknowledgement:

The rst author is thankful to King Fahd University of Petroleum & Minerals for its support. The second author is grateful to Professor Michel Rajoelina and Dr Elizabeth Strouse, his PhD advisor, for their useful suggestions. The second author is supported by Agence Universitaire de la Francophonie via Horizons Francophones Fundamental Sciences Program.