Françoise Sailhan
email: francoise.sailhan@inria.fr

Valérie Issarny
email: valerie.issarny@inria.fr

Energy-aware Web Caching for Mobile Terminals

Terminal's latency, connectivity, energy and memory are the main characteristics of today's mobile environments whose performance may be improved by caching. In this paper, we present an adaptive scheme for mobile Web data caching, which accounts for congestion of the wireless network and energy limitation of mobile terminals. Our main design objective is to minimize the energy cost of peer-topeer communication among mobile terminals so as to allow for unexpensive Web access when a fixed access point is not available in the communication range of the mobile terminal. We propose a collaborative cache management strategy among mobile terminals interacting via an ad-hoc network. We further provide evaluation of the proposed solution in terms of energy consumption on mobile devices.

Introduction

The last decade has seen the rapid convergence of two pervasive technologies: wireless communication and the Internet. The resulting mobile Internet a priori enables users to easily access information anytime, anywhere. However, we have not reached the point where anywhere, anytime Internet access is actually offered. This paper addresses the above issue, concentrating more specifically on Web caching in a mobile environment to allow for Web access, without requiring availability of an infrastructure in the nearby environment. There exists two different ways of configuring a mobile network: infrastructure-based and had-hoc-based. The former type of network structure is the most prominent, as it is in particular used in both Wireless LANs (e.g., IEEE 802.11) and global wireless networks (e.g., GSM, GPRS, UMTS) 1 . An infrastructure-based wireless network uses fixed network access points (known as base stations) with which mobile terminals interact for communicating, i.e., a base station forwards messages that are sent/received by mobile terminals. One limitation of the infrastructure-based configuration is that base stations con-stitute bottlenecks. In addition, it requires that any mobile terminal be in the communication range of a base station. However, this comes at a high cost for network providers, and is only supported if either communication is charged (i.e., global networking) or there is the will to ease access to information technology (e.g., local networking in buildings). The ad-hoc-based network structure alleviates this problem by enabling mobile terminals to cooperatively form a dynamic and temporary network without any preexisting infrastructure. Hence, it is a very cheap solution. In general, ad-hoc and infrastructure-based networking should be seen as complementary rather than as competitive. Adhoc networking is much convenient for accessing informations available in the local area, and possibly reaching a WLAN base station, which comes at no cost for users. Ultimately, the user may decide to pay for communication using wireless global networking facility, if the connectivity using the WLAN happens to be bad. This paper concentrates on improving the Web latency using a WLAN, exploiting both ad-hoc and infrastructure-based capabilities of the network.

The issue that we are addressing is on setting up an adhoc network of mobile terminals that cooperate to exchange Web pages, hence enabling Web access at no financial cost for mobile users. In that context, it is crucial to account for the specifics of mobile terminals. The capacity of batteries goes up slowly and all the powerful components that will be soon available (e.g., LCD screens, 3D graphics, high performance processor) reduce battery life. In particular, communication is one of the major sources of energy consumption [START_REF] Gauthier | Reducing power consumption for the next generation of pdas: It's in the network interface[END_REF]. Thus, it is mandatory to devise adequate solutions to energy saving on the mobile terminals, for all the constituents of the mobile environment, i.e., hardware, network operating system, and distributed software.

This paper introduces such a distributed application software, which implements ad-hoc cooperative Web caching among mobile terminals. The proposed solution aims at improving the Web latency on mobile terminals while optimizing associated energy consumption. The solution accounts for both the capacities of mobile terminals and the network features; it comprises: (i) a cooperative caching protocol among mobile terminals that builds upon an exist-ing ad-hoc network protocol, and (ii) a local caching strategy for the mobile terminal. The next section discusses related work, addressing background in the area of cooperative Web caching and Web access from mobile terminals. Section 3 then introduces the proposed ad-hoc cooperative Web caching protocol, and is followed in Section 4 by the presentation of the local caching implemented on the terminals. Section 5 provides an evaluation of our proposal, giving the energy consumption associated with cooperative caching. Finally, Section 6 concludes with a summary of our contribution.

Related Work

The ever growing popularity of the Web and the resulting poor latency for users have given rise to huge effort on improving the Web latency, which mainly lies in the introduction of Web caching protocols. Due to network topology, the idea of making network caches cooperate has emerged. The hierarchical approach is pioneering and lies in introducing a cache on every network node, the system's hierarchical structure coming from the national networks' hierarchical organization. A cache locates a missing requested object by issuing a request to the cache at the hierarchy's upper level. The process is iterated until either the object is found or the root cache is reached, which may ultimately involve contacting the object's server. The object is then copied in all the caches contacted as it is returned to the client. A transversal system enriches the hierarchy by integrating a set of sibling caches that are close in terms of latency time, at each hierarchical level. On a cache miss, a cache not only contacts its ancestral cache but also its siblings. A number of transversal cooperative caching protocols have been proposed in order to minimize the number of messages that are exchanged among sibling caches to retrieve cached objects [START_REF] Bowman | The harvest information discovery and access system[END_REF]. Proposed solutions all amount to maintain a partial knowledge of the objects that are cached on siblings [START_REF] Fan | Summary cache: a scalable wide-area web cache sharing protocol[END_REF][START_REF] Menaud | A scalable and efficient cooperative system for web caches[END_REF].

In the context of mobility, proxy caches are used not only to cache and retrieve documents but also to manage user mobility. These proxies are access points to the Internet for mobile terminals. Proxies implement functionalities dedicated to the transfer of data to mobile terminals, such as compression, filtering, format conversion [START_REF] Markatos | A top-10 approach to prefetching on the web[END_REF] [START_REF] Bennett | Practical Wap, Developing applications for the Wireless Web[END_REF].

To the best of our knowledge, Web caching for mobile terminals has only been studied in the context of proxy caches, and hence for infrastructure-based mobile networks. As raised earlier, complementing such solutions with adhoc-based ones will allow for both enhanced connectivity and Web access at low cost. In that context, the caches of the mobile terminals cooperate in a way similar to proxy caches in transversal cooperative cache systems.

Cooperative Caching in Ad-hoc Networks

Ad-hoc routing protocols are implemented over a base WLAN (typically, IEEE 802.11) and manage the routing of messages among mobile terminals. These protocols differ in the way they manage the routing table (x 3.1). Using the ad-hoc routing protocol that offers the best tradeoffs in terms of energy consumption and response time, we propose a specialization of the protocol that is specifically aimed at handling remote access to Web pages (x 3.2). We then introduce our ad-hoc cooperative caching protocol, which has primarily been designed to minimize energy consumption (x 3.3).

Ad-hoc Networking

The main issue to be addressed in the design of an ad-hoc routing protocol is to compute an optimal communication path between two mobile terminals. This computation minimizes the number of control messages exchanged among mobile terminals in order to avoid network congestion.

There exist two types of ad-hoc protocols: proactive and reactive. Proactive protocols (e.g., OLSR [START_REF] Clause | Optimized link state routing protocol[END_REF]) update their routing table periodically. Reactive protocols (e.g., AODV [START_REF] Perkins | Ad-hoc on-demand distance vector routing[END_REF], DSR [START_REF] Johnson | Dynamic source routing in ad hoc wireless networks[END_REF]) do not take any initiative for finding a route to a destination, before the information is needed, and thus a priori reduce the network load due to the traffic of control messages. ZRP [START_REF] Haas | A new routing protocol for the reconfigurable wireless networks[END_REF] is a hybrid protocol that combines the reactive and proactive modes. The design rationale of ZRP is that it is considered advantageous to accurately know the neighbours of any mobile terminal (i.e., mobile terminals that are accessible in a fixed number of hops), since they are close. Hence, communicating with neighbours is less expensive and neighbours are most likely to take part in the routing of the messages sent from the terminal. As a result, ZRP implements: (i) a proactive protocol for communication with mobile terminals in the neighbourhood, and (ii) a reactive protocol for communication with the other terminals. With respect to a given mobile terminal, its neighbourhood is referred to as its zone.

We thus use ZRP over IEEE 802.11, as the base ad-hoc protocol for realizing ad-hoc cooperative caching among mobile terminals. Mobile terminals belonging to the zone of a given terminal then form a cooperative cache system for this terminal since the cost for communicating with them is low both in terms of energy consumption and message exchanges [START_REF] Haas | The performance of query control schemes for the zone routing protocol[END_REF]. However, cooperative caching must not be restricted to the mobile terminals belonging to the zone: lowcost reachability of a base station must be accounted for as well as knowledge of a terminal that does not belong to the zone but that is likely to store a requested Web document given commonalities in performed Web accesses.

Ad-hoc Communication for Web Caching

A mobile terminal may get Web data that are not cached locally through two communication paths: (i) using the infrastructure-based mode, the terminal may interact with the nearby base station, which forwards the request to the Web, (ii) using the ad-hoc-based mode, the terminal may request for the data to the mobile terminals in its communication range (i.e., accessible in one hop in a base WLAN or in a number of hops using some ad-hoc network protocol). The ad-hoc-based mode must be enabled for the case where a base station is not reachable in one hop. In this case, a base station can still be reachable in a number of hops, thanks to mobile terminals forwarding the requests. For instance, UMTS supports such a mechanism to extend the range of the infrastructure2 . Let N be the number of hops that are necessary to access a base station , then any mobile terminal that is at a distance greater or equal to N is not contacted to get a document. Figure 1 depicts the case where the mobile terminal A reaches the base station D in 3 hops, using the mobile terminals B and C for routing the request. Then, if either a mobile terminal in the zone of A (e.g., B belonging to the path leading to the base station or any other terminal in the zone) or a known mobile terminal located outside the zone but at a lower distance than the base station D (e.g., C that is in the path leading to D or E that does not belong to the path) holds the requested document in its cache, it returns it to A. Otherwise, the request reaches D, and D forwards it to the Web. We get the following ad- In-zone communication:

If a base station is in the zone of A, then A requests for W through the base station only. Otherwise, A broadcasts the request message for W to the mobile terminals in the zone of A, incurring a low energy cost since the routing table contains the necessary information.

Peer-to-peer communication: If W is not cached by any of the mobile terminals in the zone of A, then a peer-to-peer communication scheme is realized with mobile terminals that are known to share interests with A (see x 3.3) and that are at a distance that is less than the one between A and the nearest base station. Mobile terminals outside the zone of A are basically known through two ways: (i) they belong to the path used to reach the nearest base station, (ii) they were previously either in the zone or in the path used to reach the base station. The request for W is ultimately forwarded to the nearest base station.

Based on the above, the communication and energy costs associated with getting a Web object is kept to a minimum: (i) broadcast is within a zone and is thus unexpensive by construction of ZRP, (ii) peer-to-peer communication occurs with mobile terminals that are both the most likely to store a requested object and closer than a base station.

Ad-hoc Cooperative Caching

Web data are distributed among the mobile terminals according to Web accesses performed by their user. Without a proxy-type architecture that centralizes requests, local statistics are relied on for a mobile terminal A to identify mobile terminals that are likely to store a Web object requested on A. Such statistics are maintained on A through a terminal profile for every mobile terminal with which A interacts. The terminal profile is characterized by a value that counts the number of times the corresponding mobile terminal either is known to cache an object requested by A or requested for an object to A that A had in its cache. This value is used to identify the mobile terminals with which peerto-peer communication is undertaken (see previous subsection). The list of known mobile terminals outside the zone and that are at a distance less than a base station are weighed according to the value of F = terminal profile hops where the number of hops, hops, is obtained from the routing table. Mobile terminals for which the value of F is the greatest are first contacted and the process is iterated until a hit message is received or there is no more mobile terminals eligible for the request. In addition to the management of terminal profiles to identify mobile terminals that share common interests, we must account for the heterogeneity of the terminals' capacity (i.e., battery, processing, storage, communication). For instance, for two mobile terminals that are equally likely to store a requested object, it is better to contact the one that has the greatest capacity.

A mobile terminal that receives the request for W and caches it increments its local value of A's terminal profile.

If the terminal is further willing to cooperate (e.g., absence of energy safeguarding or of security policy enforcement), it returns a hit message, which embeds:

(i) T T L that gives the Time To Leave field of the document. (ii) Capacity that characterizes the capacity of the terminal to handle requests, whose value is in the range [0..1], 1 denoting the highest capacity 3 .

For every hit message that it receives, A increments the terminal profile of the sender. Among the mobile terminals that replied by a hit message, A selects the terminal from which W should be obtained, that is the one that maximizes the following function4 : R = Capacity ( TTL + hops) where the value of and are set so as to favour communication with the closest nodes.

To minimize both network load and energy consumption, we do not use miss messages for mobile terminals to notify that they do not cache a requested object. Hence, we need to use timeouts to detect the absence of a requested object. The value of the timeout is set according to the greatest number of hops that are involved to interact with the mobile terminals to which the object is requested, together with the current network load. Upon expiration of the timeout, if hit messages have been received, the Web object will be requested to the mobile terminal that maximizes R. Otherwise, the next iteration of the cooperative caching protocol is processed (i.e., from the broadcast step to the peer-to-peer iterative steps). For the case where a hit message is received after timeout expiration, while the object is still not retrieved, the message is accounted for in the current step of the protocol.

Local Caching

Our ad-hoc cooperative caching protocol is complemented by a local caching strategy that is adaptive according to the current capacity of the terminal (i.e., available energy and network connectivity). We weigh every cached document according to both its probability of being accessed in the future and the energy cost associated with getting remotely the document. Then, documents with the lowest weighs are those that are removed from the cache when the cache gets full. The document weigh is computed according to the following criteria:

Popularity. The P o p u l a r i t y value serves approximating the probability of future access, both on the terminal and from remote terminals, as enabled by the cooperative caching protocol. The probability is approximated according to the number of times the document has been requested since it has been cached.

AccessCost. The AccessCost value gives an estimate

of the energy cost associated with getting the document remotely if it is to be removed from the cache. This cost varies depending on whether: a base station is accessible in the zone of the terminal, the document is cached on a mobile in the zone of the terminal, communication out of the zone is required to retrieve the document. The value of the access cost is computed according to the energy consumption associated with intra-zone and inter-zone communication (see x 5). It is further assumed if the document was obtained from a terminal that is still in the zone, as identified using the routing table.

Coherency. A document is valid for a limited lifetime, which is known using the T T L field. However, when the energy remaining on the terminal is low, it is better to favour energy saving over the accuracy of the document. Hence, the value of Coherency is equal to T T L where increases as the available energy decreases. We get the following function to compute the document weigh:

W = Popularity + AccessCost + Coherency + Size.
The values of , , and are set so as make the values of AccessCost, Popularity, Size, and Coherency, decreasingly prominent factors for deciding whether a document should be kept in the cache. The accurate definition of , , , and is part of our future work, where we are in particular interested in a definition that is adaptive according to the evolution of the mobile environment. Notice that our W function offers similarities with hybrid replacement algorithms on stationary hosts that were proposed in the literature (e.g., [START_REF] Jinag | Web prefetching in a mobile environment[END_REF]), our function differs in that energy saving is a prominent criterion.

Analysis

Control messages generated by ZRP and messages induced by ad-hoc cooperative caching affect the network traffic and energy consumption on mobile terminals. Performance of ZRP has been evaluated in [START_REF] Haas | The performance of query control schemes for the zone routing protocol[END_REF][START_REF] Haas | A new routing protocol for the reconfigurable wireless networks[END_REF] using eventdriven simulation; this evaluation is gauged by considering the control traffic generated by ZRP, which is reported in terms of numbers of ID fields transmitted, and the time taken for route discovery. Knowing the traffic received by a mobile terminal, the energy consumption for mobile terminals is easily evaluated. For this reason, in the following, we evaluate energy consumption associated with ad-hoc cooperative caching, as the sum of the energy consumption induced for the various mobile terminals that are involved (both in and outside the zone) in the cooperation, which adds to the energy cost induced by ZRP. We do not consider the computation cost (i.e., local cache management) since it is negligible compared to the energy cost of communication, and it is induced by any local cache management. We further use the following wireless interface for our evaluation: 2.4Ghz DSSS lucent IEEE 802.11 WLAN 2Mbps.

Focusing on the energy cost associated with communication, the cost associated with the emission of one message is the sum of the cost of: (i) Emission (resp. reception) for the sender (resp. destination) node, (ii) reception and emission for nodes forwarding the message, (iii) reception for non-destination nodes (i.e., terminals that receive messages due to their location, although they are not involved in the message routing). The IEEE 802.11 protocol provides the following collision avoidance mechanism for point-to-point traffic. Prior to any point-to-point transmission, the sender broadcasts a RTS (Request To Send) control message, which specifies the destination node and the data size (for duration). The sender then waits for a CTS (Clear To Send) message from the des-

" X =m X * m X = p X = sender X size+p X -0.04 90 in range of " A =m A * m A = p A = destination A size+p A 0 119
Table 1. Energy consumption on nodes for point-to point communication tination node. Once it receives the CTS, the sender sends the data message. Finally, the destination node sends an ACK message upon the reception of the data message. Therefore, the energy consumed by any mobile terminal for sending, receiving or discarding a message is given by the linear equation [START_REF] Feeney | Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[END_REF]: " = m size + p; where size is the message size, and m (resp. p) denotes the incremental (resp. fixed) energy cost associated with the message. Table 1 gives the energy cost, relative to the size of the message, for the destination nodes (i.e., the actual sender and destination nodes and the forwarding nodes that act as both sender and destination nodes) and also for non-destination nodes. Non-destination nodes in the range of the sender receive RTS messages and thus enter a reduced energy consumption mode during data emission; this leads to have a negative value for m AX and m X since the energy consumption is less than the one in the idle mode. Finally, non-destination nodes in the range of the destination node but not the sender do not receive the RTS message, and thus cannot enter in the reduced energy consumption mode; this leads to have the incremental cost m A equal to 0.

Let us now assume a network of 500 mobile terminals whose communication range is of about 250m, that is such that the mobile terminals are uniformly distributed in the network surface S with S = 4000 m] 4000 m]. 5 In a zone (see Figure 2), all the mobile terminals consume the same energy. Thus, the overall energy consumption within a zone is the sum of the energy consumed by every mobile terminal in this zone (see Table 2). Then, the energy consumption of the overall network is the sum of the energy consumed per zone that is traversed. Figure 3 gives the energy consumption associated with the delivery of a message of 1Kb to the destination node according to the number of hops, which is the sum of the energy consumed on all the nodes involved in the communication. The figure clearly demonstrates that the energy consumption increases with the number of hops. This directly follows from the resulting increase of both mobile terminals forwarding the message and non-destination nodes receiving control messages. Table 3 further evaluates the impact of the network density on energy consumption. For a constant number of hops (=3), we see that increased density of mobile terminals results in additional energy consumption for non-destination nodes. But, the ratio highlights the weak impact of message reception on non-destination nodes, on the overall energy consumption. Indeed, for 600 mobile terminals and a destination node at 4 hops of the sender, the energy consumed by non-destination nodes is about 6 times less than the energy consumed by the sender, the receiver and the 3 forwarding mobile terminals. Having examined the energy consumption associated with data delivery, we now focus on the energy consumption induced by our ad-hoc cooperative caching protocol. A request message for a Web page includes broadcasting (with mobile terminals in the requester's zone) and peer-to-peer communication (with mobile terminals sharing the same interests). Before broadcasting a message, the sender listens to the channel; if no traffic is detected, the message is broadcasted. The energy consumed by the sender X (resp. destination A) is given by the equation " brsend =1.9 size+266 (resp. " brdest =0.5 size+56). The higher energy consumption associated with peer-to-peer communication (see S AX = (r 2 ; a 2 1 ) + (R 2 ; a 2

2 )

n AX = N S AX S n AX " AX the sender X S X = r 2 ; S AX n X = N( r 2 ;S AX ) S = r 2 ; r 2 sin 2 + R 2 sin 2 n X " X the receiver A S A = R 2 ; S AX n A = N( R 2 ;S AX ) S = R 2 ; r 2 sin 2 + R 2 sin 2 n A " A 1) compared to broadcasting is due to the emission of control messages. Figure 4 gives the energy consumed by cooperative caching according to the number of hops that defines the zone. Precisely, Figure 4 gives the cost associated with broadcasting and peer-to-peer communication at a distance that adds one hop to the number of hops that defines the zone. We find that the cost added by broadcasting is weak compared to the number of mobile terminals contacted, and thus supports such an approach.

Conclusion

Mobile technology has reached a stage that enables foreseeing easy access to information technology anywhere, anytime. However, enabling mobility comes with limitations that mainly relate to unstable connectivity and limited energy. Thus, it is necessary to devise adequate solutions at the level of both software and hardware to mask as much as possible the limitations of mobile environments. This paper has addressed one such solution, which focuses on enabling Web accesses from mobile terminals. Currently, Web access is easy to realize if the mobile terminal is in the communication range of a base station of either a WLAN or a global wireless network. However, this cannot always be assumed due to the financial cost associated with the deployment of the underlying infrastructure. In addition, the systematic use of a global wireless network is quite costly for users. Instead of relying on a base station for accessing the Web, an alternative solution is to exploit ad-hoc networking, which allows for remote communication at no financial cost and also reaching a base station of a WLAN in a number of hops. In that context, we have proposed a cooperative Web caching system for ad-hoc networks, which enables mobile terminals to share Web pages. Our system lies in implementing on each mobile terminal: (i) an ad-hoc cooperative caching protocol that selects the mobile termi-nals from which a requested page should be retrieved, in a way that minimizes both energy consumption and network load, (ii) a caching strategy that maintains the local cache in a way that minimizes resource consumption and masks disconnection. Preliminary assessment of our proposal has been addressed, by providing the energy cost that our system incurs for mobile terminals. We are currently working on further assessment of our proposal, which lies in the implementation of a simulator to thoroughly examine the behavior of our system. Experiment using the simulator will in particular serves tuning the various weighing functions that we use for cooperative caching.

Figure 1 .

 1 Figure 1. Getting Web data hoc communication protocol over ZRP, to retrieve a remote Web object W, with respect to a given mobile terminal A (see Figure 1):In-zone communication:

Figure 2 .

 2 Figure 2. Mobile terminals in the range of the sender and of the destination node.

Figure 3 .

 3 Figure 3. Energy consumption in the network for the retrieval of Web data.

Figure 4 .

 4 Figure 4. Energy consumption for broadcast and peer-to-peer communication.

Table 3 . Energy consumption according to the network density.

 3

Table Proceedings

 Proceedings

	Mobile terminal in range of	Surface	number of mobile terminals	Total Energy for a zone
	sender X & destination A

of the 22 nd International Conference on Distributed Computing Systems Workshops (ICDCSW'02) 0-7695-1588-6/02 $17.00 © 2002 IEEE

Table 2 . Energy consumption in a zone.

 2

This network structure is also referred to as the base station mode in the IEEE 802.11 WLAN, and the BSS in GPRS.

Proceedings of the 22 nd International Conference on Distributed Computing Systems Workshops (ICDCSW'02) 0-7695-1588-6/02 $17.00 © 2002 IEEE

http://www.3gpp.org

Currently, we use the percentage of the energy budget that is left to set the value of Capacity. It is part of our future work to investigate a more accurate way of computing Capacity, in particular accounting for the various resources. Proceedings of the 22 nd International Conference on Distributed Computing Systems Workshops (ICDCSW'02) 0-7695-1588-6/02 $17.00 © 2002 IEEE

For the case where the selected terminal is no longer accessible, e.g., due to energy safeguarding, the request will be sent to the next eligible terminal and will be so until the page is received.

Proceedings of the 22 nd International Conference on Distributed Computing Systems Workshops (ICDCSW'02)

This network is taken as an example, as it is used in[START_REF] Haas | The performance of query control schemes for the zone routing protocol[END_REF] for the evaluation of ZRP.

Acknowledgments:

The authors would like to thank Laurent Viennot for helpful discussion on ad-hoc networking.


M Teresa

Valérie Issarny

Analyzing the Performance of Memory Management in RTSJ

Keywords: Java, Real-Time, Embedded, Garbage Collection, Memory Regions, Write Barriers, Performance

The memory models used in the Real-Time Specification for Java (RTSJ) can incur high amounts of overhead; It is possible to reduce this overhead by taking advantages of hardware features. This paper provides an indepth analytical investigation of the overhead of write barriers in RTSJ VMs, and describes and analyzes some solutions to reduce the overhead of write barriers.

Introduction

RTSJ distinguishes between three kinds of tasks: lowpriority, that are tolerant with the Garbage Collector (GC); high-priority, that cannot tolerate unbounded preemption latencies; and critical, that cannot tolerate preemption latencies. Low-priority tasks are instances of the Thread class, high-priority tasks are instances of the Realtime-Thread class, and critical tasks are instances of the No-HeapRealtimeThread class. The MemoryArea abstract class supports the Memory Region (MR) paradigm [START_REF] Bollella | The Real-Time Specification for Java[END_REF] through the three following kinds of regions (see Figure 1): (i) immortal memory, supported by the ImmortalMemory and the ImmortalPhysicalMemory classes, that contains objects whose life ends only when the JVM terminates; (ii) (nested) scoped memory, supported by the ScopedMemory abstract class, that enables grouping objects having welldefined lifetimes and that may either offer temporal guarantees (i.e., supported by the LTMemory class) or not (i.e., supported by the VTMemory class) on the time taken to create objects; and (iii) the conventional heap, supported by the HeapMemory class. Objects allocated within immortal MRs live until the end of the application and are never subject to garbage collection. Objects with limited lifetime can be allocated either into a scoped region or the heap. Garbage collection within the heap relies on the (real-time)

This work has been partially funded by Texas Instruments.

GC of the JVM. Scoped regions may or may not be subject to internal real-time garbage collection depending on their temporal properties 1 . However, since RTSJ does not impose GC within scoped regions, we consider in this paper that scoped regions are never garbage collected. A scoped region gets collected as a whole once it is no longer used. RTSJ further defines the GarbageCollector abstract class, which can be customized through an incremental collector allowing the application to execute while the GC has been launched. In the following we assume the use of the GC algorithm given in [START_REF] Higuera | Region-based Memory Management for Real-time Java[END_REF] (i.e., the four-color algorithm that builds on [START_REF] Dijkstra | On-the-fly Garbage Collection: An Exercise in Cooperation. 18 We have limited to 32 the number of region the number of scoped nexted level to 6, which allows us to support the region stack in a word[END_REF]): an object within the heap is colored white when not reached by the GC, black when reached, and grey when it has been reached, but its descendants may not be; and an object outside the heap is colored red. Grey objects make a wavefront, separating the white (unreached) from the black (reached) objects, and the application must preserve the invariant that no black objects have a pointer to a white object, which is achieved using write barriers in [START_REF] Wilson | Uniprocessor Garbage Collection Techniques[END_REF]. The collection is completed when there are no more grey objects. All the reached objects within the heap are black (those that are reachable from the heap roots and from outside the heap), there is no grey object, and all the white objects can be recycled 2 . Red objects having pointers to object within the heap (i.e., black, grey, or white objects) are considered as external roots for the GC. 1 We can build a VTMemory object with a specific GC. Note that in this case, critical tasks must be able to use it. 2 The recycling of objects is actually done after finalization.

A thorough analysis of the parameters influencing the performance of the memory management in RTSJ is presented regarding both the management of MRs (Section 2) and real-time GC within the heap (Section 3). We use 5 SPECjvm98 [START_REF]SPEC JVM98 benchmarks[END_REF] (see Table 1) and an artificial collector benchmark to analyze the behavior of Java applications regarding memory usage. This allows us to have an estimation of memory usage within a memory region. In Section 4, we evaluate the overhead introduced by three different write barrier solutions supporting both MRs and incremental GC. In Section 5, we implement a prototype within the KVM [START_REF]KVM Technical Specification[END_REF] by modifying the original collector to make it incremental, and introducing MRs. Finally, a summary of our contribution concludes this paper (Section 6).

Program Description

JESS

Expert Shell System based on NASA's CLIPS system.

DB

Emulates data operations on resident memory.

JAVAC

Java compiler from the JDK 1.0.2.

MTRT

Multithreaded raytracer.

JACK

Parser generator (early JavaCC version).

Table 1. Used SPECjvm98 programs.

Analyzing the Performance of Regions

In general, the management of memory regions introduces overhead, which we characterize in this Section. The region implementation given in [START_REF] Gay | Memory Management with Explicit Regions[END_REF] presents an overhead that is constant per instruction executed. RTSJ imposes strict rules on objects access and assignments within regions, the JVM must detect both illegal accesses and assignments and throw an exception when they occur, which introduces high overhead.

Memory Management Overhead

In RTSJ, each MR supports objects that are related regarding associated lifetime and real-time requirements. Whereas the heap and immortal regions end with the application, a scoped region gets collected by a referencecounting GC once it is no longer used. Then, the overall cost introduced by scoped region management is given by the cost associated with: (i) Region creation, which is not considered by RTSJ3 . (ii) Reference counter updates, where we notice that problems associated with reference counting collectors are solved4 . (iii) Object allocation, where the time to allocate an object is proportional to the object size, and in the worst case may include time to acquire additional memory for the region5 . (iv) Region deletion, where before cleaning a scoped region, the root-list of the GC is updated to remove all the objects in the region that are external roots for the GC, and the objects within the terminated region are added to the finalize-list of the GC. (v) Checks on objects access/assignment, the efficient of which is discussed in the remainder of this paper.

To support critical applications in RTSJ, the GC of the heap must be disabled and all MRs (i.e., scoped and immortal physical) must be created at initialization time [START_REF] Puschner | A Profile for High-Integrity Real-Time Java Programs[END_REF]. In this way, the application runs with static memory, which facilitates an accurate pre-runtime analysis.

Illegal Accesses and Assignments

A reference from a critical task to an object allocated in the heap causes the MemoryAccessError exception. Illegal accesses must be checked when executing instructions that load references within objects or arrays, e.g., by introducing the following read barriers for each load reference: if (( = critical) and (region(Y) = heap)) goto illegalAssignment:;

The lifetime of objects allocated in scoped regions is governed by the control flow: (i) objects within either the heap or an immortal region cannot make assignments to objects within a scoped region, and (ii) objects within a scoped region cannot make assignments to objects within an nonouter scoped region. Illegal assignments causes an Il- legalAssignmentError exception, and must be checked when executing instructions that store references within objects or arrays, e.g., by introducing the following write barriers for each load reference: if (region(Y) = scoped) if (region(X) = scoped) nestedRegions(X,Y) else goto illegalAssignment:;

The nestedRegions(X,Y) function is based on a region stack associated with the active task (see Figure 2) and throws the MemoryAccessError() exception when the region to which the object X belongs is not found in the region stack, and the IllegalAssignmentError() exception when the region to which the object X belongs is not inner to the region to which the object Y belongs. We consider that the time cost to detect both illegal accesses and assignments is a fraction of the total program execution time. All the objects created in Java are allocated in the heap (i.e., dynamic memory, that in RTSJ may be either within the heap or another MR); only primitive types are allocated in the runtime stack [START_REF] Gay | Stack Allocating Objects in Java[END_REF]. In most applications of the SPECjvm98 benchmark, less than half (i.e., 45%) of the references are to objects within the heap rather than primitive types (e.g., bytes or integers), the other half is to either the Java or the native stack (see Table 2 [9]). We also notice that about 35% of the total executed bytecodes requires an object reference, where typically 70% is for load operations and 30% for store operations. Then, 15% (i.e., 0:45 0:35)of the bytecodes reference an object within the heap, where 10% (i.e., 0:15 0:70) of the bytecodes requires read barrier avoiding illegal accesses of critical tasks to objects within the heap, and 5% (i.e., 0:15 0:30) write barriers avoiding illegal inter-region assignments. We use write barriers to detect illegal accesses 6 , as well to maintain the root-set of the GC 7 and to preserve the invariant that no black object references a white one, called tri-color invariant [START_REF] Dijkstra | On-the-fly Garbage Collection: An Exercise in Cooperation. 18 We have limited to 32 the number of region the number of scoped nexted level to 6, which allows us to support the region stack in a word[END_REF]. As a conclusion, we have 5% (i.e., 0:15 0:30) as a maximum bound for write barrier executions. RTSJ does not consider the write barrier overhead for MRs, then we add the getWriteBarrierOverhead() method to the MemoryArea abstract class, which gives the cost to detect illegal assignments between different types of MRs. In the same way, we add the getWriteBarrier- Overhead(int n) method to the ScopedMemory abstract class, which identifies the write barrier cost to have n nested levels for scoped regions.

Analyzing the Collection Performance

We can determine the performance of an incremental GC through the following parameters: (i) the ratio of the amount of allocated objects with the total size of the heap (memory utilization) which relates to the reclamation rate, (ii) the space and time needed by the collection (overhead), (iii) the duration of collection pauses (latency), and (iv) the effort to coordinate the application and the collector (write barrier overhead). Ideally, the memory utilization should be high so that the GC does not run frequently, the overhead should be low to improve the performance of applications, and the latency must be low and bounded for real-time applications. We analyze the aforementioned parameters in the following.

To simplify our presentation, we do not treat fragmentation assuming that all the objects have the same size. In that context, a GC pass is hereafter used to mean the overall execution of the GC once it is launched, from the tracing of the object graph to the reclamation of dead objects. A GC increment is further used to mean actual GC execution. It is also important to note that in our algorithm, memory that becomes garbage is freed at the end of the GC pass (i.e., new objects are allocated black).

Reclamation Rate

The collector must terminate before the free memory gets exhausted. A usual strategy to avoid the application to run out of memory is to accelerate the GC according to the application's allocation rate, which can be computed as the amount of dynamic memory used number of executed instructions (see To ensure the above condition, it is necessary to quantify the worst case allocation rate and to put this measure as a bound. Let L be the maximum amount of live objects, and M be the memory size, we have M ;L free memory. Since new objects created during a GC pass will not be collected until the next pass, we must account for this memory occupation (U ). We consider that the amount of new objects allocated while tracing, is not greater than the amount of memory used, i.e., U L. This implies a minimum safe tracing rate of 2 L M;L [18], which approaches zero as mem- ory becomes large 8 .

Adapting the reclamation rate. At the end of each pass, the GC can determine how much alive memory has been traced and revise its worst-case, estimating what could be alive at the next pass. When the GC determines that it can reduce the reclamation rate, it may stop its activity and resume later 9 . This improves the performance of the mutator, but not too much since write barriers are still executed when the GC is disabled. Then, it is interesting that our GC supports an efficient way to disable barriers on the fly which has been achieved in [START_REF] Higuera | Region-based Memory Management for Real-time Java[END_REF] by using the picoJava-II hardware support.

Collection Overhead

The number of times that the GC must be run (N ) and the number of instructions executed by a GC pass (I GC ), depend on the heap size [START_REF] Kim | Memory System Behavior of Java Programs: Methodology and Analysis[END_REF]. The overhead introduced by the GC is inversely proportional to the heap size, and can be given by the following expression: N IGC I , where I denotes the total number of instructions executed by the CPU (see Figure 3). For an incremental collector, the total effort required to perform a complete GC pass can be configured as a function of the system workload [START_REF] Nilsen | Adding Real-Time Capabilities to Java[END_REF]. If S gives the seconds needed by the CPU to complete a collection pass, and G the fraction of CPU dedicated to garbage collection during this time; the time to execute completely the incremental GC is given by S G . Thus, when the GC is executing, the quantity of oc- cupied memory in the heap is V S G , where V represents the total bytes allocated per second. Considering new objects created during the GC pass (U ), the total memory (M ) must be greater than the maximum amount of live objects, i.e., M > V S G + U. Then, the minimum fraction of the CPU time spent by the GC is V S M;U , which approaches 0 when the amount of memory becomes large or the application allocation rate becomes small. 9 For instance, if the amount of data is less than 1=3 of the maximum heap, the GC is disabled (i.e., L < 1 3 M which means 2 L M;L < 1).

Minimizing the Overhead. An option to minimize the GC overhead is to reduce the number of objects that must be managed by the GC to improve the performance of the GC. Then, improvements on the Java compiler may reduce the GC rate by putting more heap objects in the stack. Some studies show that the percentage of objects that could be allocated in the stack instead of the heap are generally in the 5% ; 15% range, and in some cases as high as 56% [START_REF] Mcdowell | Reducing Garbage in Java[END_REF].

Notice further that objects allocated within immortal and scoped regions of RTSJ are not garbage collected 10 , allocating objects in these MRs thus reduces the GC overhead.

Preemption Latency and Response Time

We analyze here the schedulability of the GC assuming Rate Monotonic Scheduling (RMS). Consider N tasks with a priority higher than the one of the GC ( GC+1 :: GC+N ).

Each task i has a period T i and a worst-case execution time C i . We denote as R GC the worst case response time of the GC, which must be greater than the sum of the worst case execution time of all the tasks with higher priority [START_REF] Henriksson | Predictable Automatic Memory Management for Embedded Systems[END_REF]:

RGC = P GC+N i=GC+1 ( R GC T i
Ci ) . To calculate R GC in this recursive formula, we give C GC as the first value for R GC .

Then, S > (R GC + L GC ) N GC , where S gives the seconds needed by the CPU to complete a collection pass, L GC the maximum execution time of a collector increment, and N GC the number of increments for each collection pass.

The maximum preemption latency that the collector can introduce in the system is R GC ; S NGC .

Minimizing Allocation Latency.

The fact that the overhead of memory allocation depends on both the size of the object and the heap evolution, makes it intolerable for critical tasks. In order to eliminate this imprecise cost, critical tasks do not execute actions related to the GC, and are never affected by the preemption latency of the GC 11 . Regarding the size of the object, every allocation must have an execution time cost, that is bounded by a linear function on the size of the object; we do not include in this cost static initializations associated with the object nor the execution of its constructor. For this purpose, RTSJ defines the LTMemory class (a ScopedMemory subclass) that represents a memory area guaranteed by the system to have constant time allocation. This class allows tasks to allocate objects, ignoring reclamation and avoiding delays because of the GC. Thus, it is safe to associate a LTMemory object with critical tasks.

Write Barrier Overhead

In RTSJ, the getWriteBarrierOverhead() method of the IncrementalGarbageCollector class gives the write barrier cost per assignment, i.e., writeBarrierCost assignmentCost

where the writeBarrierCost is the execution time of the introduced write barriers, and the assignmentCost is the execution time of an object assignment. Thus, we compute writeBarrierCost for an incremental GC, as the cost to detect when to take actions preserving the tri-color invariant, i.e., the execution time taken to detect when to execute the greyObject(Y) function:

if ((color(X) = black) and (color(Y) = white)) greyObject(Y);

Note that the execution time taken by the greyObject(Y) function is considered as part of the GC overhead rather than as part of the write barrier overhead. The GarbageCollector abstract class of RTSJ does not support the getWriteBarrierOverhead() method 12 . Since the heap coexists with other MRs, we consider that this method must also be implemented for all collectors to give the overhead caused by detecting illegal assignments of critical task to objects within the heap. For mark-and-sweep collectors, this method further gives the overhead caused by the write barriers introduced to detect when to update the collector's root-set:

if ((color(X) = red) and (color(Y) 6 = red)) updateRootSet(X, Y);

Minimizing the Write Barrier Overhead. The most common approach to implement write barriers is by inline code, consisting in generating the instructions executing write barrier events for every store operation. This solution requires compiler cooperation (e.g., JIT), and presents a serious drawback because it nearly doubles the application's size. Regarding systems with limited memory such as PDAs, this code expansion overhead is considered prohibitive. Alternatively, we can instrument the bytecode interpreter, avoiding space problems, but this still requires a complementary solution to handle native code. A solution minimizing the write barrier overhead consists in improving the write barrier performance by using hardware support such as the picoJava-II microprocessor [START_REF]picoJava-II Programmer's Reference Manual[END_REF], which allows performing write barrier checks in parallel with the store operation. This alternative solution has been the subject of [START_REF] Higuera | Region-based Memory Management for Real-time Java[END_REF].

Evaluating the Write Barrier Cost

In this Section, we first propose three different write barrier implementations to support the RTSJ memory model. Next, we estimate the write barrier overhead introduced by both the collector and memory regions in the proposed solutions.

Write Barrier Implementations

Solution 1. Modifying the Java Interpreter. This solution consists in modifying the JVM by introducing the code given in Figure 4 in the interpretation of each bytecode whose function consists in assigning an object Y to another object X 13 . Solution 2. Using Existing Hardware. We improve the performance of Solution 1 by using the write barrier support of the picoJava-II microprocessor, as proposed in [START_REF] Higuera | Region-based Memory Management for Real-time Java[END_REF]. In this solution, write barriers must be configured at contextswitch time depending on the scheduled task. Non-critical tasks throw the gc notify exception when a white object is assigned to a black one, or when an object is assigned to another one allocated in a different MR. Whereas critical tasks throw the gc notify exception when the assigned object is within the heap, or a different MR that the other one. both objects are allocated in different MRs. The code executed by the gc notify exception handler is the same as the one introduced in the interpreter in the former solution (see Figure 5).

Solution 3. Modifying the Existing

Hardware. This solution modifies the hardware support of picoJava-II to have three different traps (see Figure 6). In this solution, noncritical tasks cause the execution of: (i) the gc notify 1 0 exception when a non-red object is assigned to a red one, (ii) the gc notify 1 exception when any object is assigned to another one allocated in a different MR, and (iii) the gc - notify 0 exception when a white object is assigned to a black one. Critical tasks cause also the gc notify 0 exception when a non-red object is assigned.

Evaluating the Write Barrier Overhead

Axioms and Theorem. We are interested in fixing a maximum bound for the number of events that: (i) makes an inter-region assignment, (ii) explores the region stack, (iii) creates an external reference for the collector, and (iv) attempts to break the tri-color invariant. We assume here that each object has an equal probability to being referenced.

Notations:

Let r, b, g, and w, be respectively the number of red, black, grey, and white objects, and h, i, and s be respectively the number of objects within the heap, an immortal region, or a scoped region, found in the system at a given instant. Let further, x and z denote respectively the number of inter-region and intra-region assignments, found in m assignments made by the task . Axiom 1. h x + i x + s x = 1

In x inter-region assignments of the task , there are h assignments from thee heap, i assignments from an immortal region, and s assignments from a scoped region.

Axiom 2. b h + g h + w h = 1

In h objects within the heap there are b objects black, g objects grey, and w objects white.

Theorem:

The probability that a task breaks the tri-color invariant when making m assignments is bounded by 0:25 h.

Proof.

We have h = b + g + w. We can further express the probability to break the tri-color invariant as b w

h 2 = b (h;(b+g)) h 2
, this probability is maximum when there are no grey objects in the system (i.e., Quantifying the Overhead. To obtain the write barrier overhead solutions given in x 4.1, two measures are combined: (i) the number of events (E), and (ii) the measured cost of the event (C). We also take into account the percentage of bytecodes requiring write barriers, which has been evaluated as 5% in x 2.2. Then, we compute the total write barrier overhead introduced by both MRs and the GC:

M R Ov = 0 :05 (EMR CM R+ Escoped Cscoped) GCOv = 0 :05 (EGC CGC + EincGC CincGC )

Where C MR , C scoped , C GC , and C incGG parameters correspond to:

CM R= MemoryArea:getWriteBarrierOverhead() Cscoped = ScopedMemory:getWriteBarrierOverhead(n) CGC = GarbageCollector:getWriteBarrierOverhead() CincGC = IncrementalGC:getWriteBarrierOverhead() Event parameters. We then estimate the maximum probability to execute the write barrier code when a non-critical task makes an assignment, as given in Table 4. Note that for critical tasks, the overhead due to the GC is 0 (i.e., E GC and E incGC equal to zero, otherwise the IllegalAssign-mentError() exception raises). Cost parameters. The write barrier cost is proportional to of the number of evaluated conditions. Then, we bound the cost parameters as maxConditions conditionCost assignmentCost .

Events

Where the maxConditions parameter is the maximum number of evaluated conditions to check whether the following actions should be executed: (i) call neste- dRegions(X, Y), (ii) execute nestedRegions(X, Y), (iii) call updateRootSet(X, Y), and (iv) call greyObject(Y). And the conditionCost parameter is the execution time to evaluate a condition. Table 5 gives the maximum and average value for the number of evaluated conditions, where n is the maximum number of nested scoped levels. GC Ov2 < ( x m + 0 :25 h m ) GC Ov1 GC Ov3 < 0:6 h m conditionCost assignmentCost Note that for hardware-based solutions (i.e., solutions 2 and 3) we must take into account the time that the picoJava-II microprocessor spends to catch a trap. Recall also that the write barrier overhead introduced by scoped regions is the execution time of the nestedRegions(X,Y) function.

Then, to bound it, we must bound the number of nested region levels.

Comparison.

In solution 1, the write barrier code is executed for both inter-region and intra-region references. Solution 2 reduces the cost of write barriers for intra-region references to the cost to maintain the tri-color invariant (i.e., by a factor of x m +0:25 h m ). This is because the gc notify exception traps only when a task makes an inter-region reference or attempts to violate the tri-color invariant. Solution 3 minimizes the cost for inter-region references, to the cost to detect both illegal assignments when the referenced object is outside the heap and root-set updates when the referenced object is within the heap.

Experiment

We have modified the KVM garbage collector14 making it a stack-based tri-color algorithm. We have implemented the IncrementalGC class within the KVM by modifying some files 15 .

This class supports the method related with parameters characterizing the collector behavior: getMinimumReclamationRate(), se- tReclamationRate(), getOverhead(), getWrite-BarrierOverhead(), and getPreemptionLatency().

We have only implemented three types of memory regions: the heap that is collected by an incremental GC, immortal that are never collected and can not be nested, and scoped that have limited live-time and can be nested. These regions are supported by the HeapMemory, the ImmortalMemory, and the ScopedMemory classes. Unlike RTSJ, in our prototype the ScopedMemory class is a non-abstract class, and the MemoryArea abstract class has not been implemented 16 . The getWriteBarrierOverhead() method has been implemented for the three classes. Instead of using the SPECjvm98 benchmark, which is not compatible with the KVM, we use an artificial collector benchmark. This is an adaptation made by Hans Boehm from the John Ellis and Pete Kovac benchmark 17 . Two data structures of the same size are kept around during the entire process: (i) a tree containing many pointers and (ii) a large array containing double precision floating point numbers, which we have modified to contain integers to make it compatible with the KVM. This benchmark executes 262 10 6 bytecodes and allocates 408 MB y t e s . Then, the allocation rate is about 1:6 KBytes=1000 executed bytecodes. The number of garbage collection pass, the microseconds spent in garbage collection, and the percentage overhead introduced by our collector are given in 45% to maintain the root-set. 31% to preserve the tri-color invariant.

31% to detect illegal references. 16% to check a nested scoped level 18 .

Conclusion

A real-time GC avoids the user to recycle memory, but introduces high overhead and unpredictable behavior. Memory regions, which can be supported in a stack discipline offer a high level of predictability. The memory regions model of RTSJ combines the advantages of both techniques. But, this model introduces high write barrier overhead, and it is not clear that this approach is better than classical static memory, classical real-time collection, or classical memory regions. The contribution of our work comes from the adaptation and integration of relevant solutions to make memory reclamation real-time, in the context of RTSJ, and is based on the analysis of the parameters that are the most influential in memory management performance.

In this paper, we have analyzed and estimated the performance of the RTSJ memory model. To this end, we have studied the memory behavior of the SPECjvm98 applications. These non-real-time applications allocate all object references (i.e., non-primitive types) within the JVM heap (i.e., do not use any other memory region), and do not impose to the collector real-time restrictions. However, we obtain, as a as conclusion, that 5% of the executed bytecodes makes an assignment of an object within dynamic memory. We extrapolate this result to RTSJ, concluding that 5% of the bytecodes executes write barriers to detect (i) illegal accesses and assignment introduced by MRs, (ii) external roots for the GC, and (ii) violations of the tri-color invariant introduced by an incremental GC.

Our solution, for improving performance of memory management partly addresses the use of hardware aid by exploiting existing hardware support for Java (i.e., picoJava-II). A detailed analysis of three different implementations of write barrier shows that the hardware aid improves highly the application performance. Finally, we have integrated our real-time GC and support for memory regions within the KVM, which we have evaluated using and an artificial benchmark designed to analyze the memory behavior. For this prototype we obtain the same proportion of bytecodes requiring write barriers (i.e., 5%).

Figure 1 .

 1 Figure 1. The MemoryArea hierarchy in RTSJ.

Figure 2 .

 2 Figure 2. Region stack: (a) t 1 , (b) t 2 , and (c)t 3 .

Figure 3 .

 3 Figure 3. GC overhead.

  if (region(Y) = scoped) if (region(X) = scoped) nestedRegions(X,Y) else goto illegalAssignment:; if (( = critical) and (region(Y) = heap)) goto illegalAssignment:; if ((color(X) = red) and (color(Y) 6 = red)) updateRootSet(X, Y) else if ((color(X) = black) and (color(Y) = white)) greyObject(Y);

Figure 4 .

 4 Figure 4. Write barrier code.

  gc notify: if (region(Y) = scoped) if (region(X) = scoped) nestedRegions(X,Y) else goto illegalAssignment:; if (( = critical) and (region(Y) = heap)) goto illegalAssignment:; if ((color(X) = red) and (color(Y) 6 = red)) updateRootSet(X, Y) else if ((color(X) = black) and (color(Y) = white)) greyObject(Y); priv ret from trap;

Figure 5 .

 5 Figure 5. Handling the gc notify exception.

6 =Figure 6 .

 66 Figure 6. Write barrier exception handlers.

  h = b + w). Then: b (h ; (b + g)) <= b h ; b 2 . Where the b h ; b 2 expression takes its maximum value for b = h 2 (i.e., 0 = h ; 2 b) and w = h 2 (i.e., h = h 2 + w).

Table 4 .

 4 Max bound on write barrier events.

6

  Proceedings of the Fifth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC'02) 0-7695-1558-4/02 $17.00 © 2002 IEEE

Table 2 . Memory reference behavior.

 2

Table 3

 3

	Executed Instructions 5 328 10 6 9 168 10 6 JAVAC 7 717 10 6 JESS DB MTRT 3 917 10 6 JACK 6 553 10 6	Allocated Memory (KB) Rate ( KB Allocation 10 3 inst ) 314 533 60 99 927 11 221 206 29 164 444 43 207 550 32

[9]

).

Table 3 . Allocation behavior.

 3

Table 5 . Evaluated conditions for write barrier. Bounding the Overhead.

 5 Let MR Ovi and GC Ovi (1 <= i < = 3 ) be the MR Ov and GC Ov parameters of

	each given solution, then:
	MR Ov1 < 0:05(2 + n s m ) conditionCost assignmentCost MR Ov2 < ( x m + 0 :25 h m ) MR Ov1 MR Ov3 < 0:05( i m + ( n + 1 ) s m ) conditionCost assignmentCost
	GC Ov1 < 0:05(3 + 2(1 ; x m )) conditionCost assignmentCost .

Table 6 :

 6

	Memory	GC	Collecting	Execution	%
	Heap 8MB 16MB 27 13:17 10 6 72:72 10 6 pass Time Time 51 13:54 10 6 72:87 10 6 24MB 17 12:80 10 6 71:99 10 6 32MB 13 11:82 10 6 70:50 10 6	Overhead 18:85% 18:11% 17:80% 16:50%

Table 6 . Garbage collection overhead.

 6 The maximum latency to preempt the incremental collector has been measured as 1 second. The number of executed bytecodes performing write barrier test is 15 10 6 (i.e., aastore: 1 10 6 , putfield: 6 10 6 , putfieldfast: 7 10 6 , putstatic: 19, and putstatic fast: 0) for a total of 262 10 6 executed bytecodes. This means that 5% of executed bytecodes perform a write barrier test, as already obtained in x 2.2 with SPECjvm98[START_REF]SPEC JVM98 benchmarks[END_REF]. And the overhead introduced by the software write barrier test in each assignment, is:

RTSJ does not consider the execution time of object constructors.

The space to store reference counters is minimal, and there cannot be cycles among regions.

Whereas an allocation in a VTMemory region may take variable time, the time taken in a LTMemory region is linear to the object size.

Proceedings of the Fifth IEEE International Symposium on Object-Oriented Real-Time Distributed Computing (ISORC'02) 0-7695-1558-4/02 $17.00 © 2002 IEEE

We apply the same optimization as for the incremental GC which is to use write barriers instead of read barriers.

The GC root-set usually includes the local variables in run-time stacks and static variables defined in loaded classes; we must further add objects allocated outside the heap having references to objects within the heap.

Since fragmentation reduces the actual memory available, faster tracing is required.

This is always the case for objects within an instance of LTMemory but this is not mandatory for objects within an instance of VTMemory.

RTSJ critical tasks are not allowed to allocate or even reference objects from the Java heap.

In RTSJ, the getWriteBarrierOverhead() method is supported by the IncrementalGarbageCollector class.

The bytecodes causing write barriers are: putfield, putstatic, aputfield quick, aputstatic quick, aastore, and aastore quick.

Version 1.0.1

We have modified the garbage.c file to implement the collector algorithm and the interpreter.c file to implement the write barriers, as well as the native.h and the nativeCore.c files, which support the interface for the native methods.

This due to the limitations of heritage in the KVM.

http : ==www:hpl:hp:com=personal=Hans Boehm=gc=gc bench:html


domain: shs stat

text:
PhD Cătălin Bărboianu

The current technical report of the research project investigating how the mathematical dimension of gambling is reflected in the communication and texts associated with the gambling industry raises the problem of the adequacy of sampling and proposes a new approach in this respect. The qualitative analysis of the reviewed websites is extended to a deeper analysis of language and also to the organization and structure of websites' content. Although not stated as a goal of the initial project, the research will also try to identify relationships between the specificity of content relative to the mathematical dimension of gambling, and the management and marketing of the website. An overview of the results of the statistical analysis of the current sample is also presented.

Introduction

Mathematics is strongly connected to gambling through the mathematical models underlying any game of chance. Mathematics is reflected not only in games' design/characteristics and their outcomes, but also in gamblers' perception and knowledge of the mathematics-related facts of gambling -which influence their gambling behavior. The math-indispensability principle [START_REF] Bărboianu | Mathematician's call for interdisciplinary research effort[END_REF] applies not only in problemgambling research, but also in the gambling industry. The structural, informative, strategic, psychological, pathological, and ethical aspects of gambling have been identified to be grounded in the mathematics of games and gambling [START_REF] Griffiths | Fruit machine gambling: The importance of structural characteristics[END_REF][START_REF] Bărboianu | Is the secrecy of the parametric configuration of slot machines rationally justified? The exposure of the mathematical facts of games of chance as an ethical obligation[END_REF][START_REF] Bărboianu | Mathematical models of games of chance: Epistemological taxonomy and potential in problem-gambling research[END_REF]Turner & Hobay, 2004;Harrigan, 2009, and others).

Gambling cognitive distortions, language, and miscommunication

Gambling-specific cognitive distortions (in the form of misconceptions, misunderstandings, reasoning fallacies, biases, false or irrational beliefs, or illusions, alone or mixed) are believed to be an important cause of the development of problem gambling and are considered as major risk factors [START_REF] Lambros | Numerical reasoning ability and irrational beliefs in problem gambling[END_REF]Leonard & Williams, 2016, and others). We have analyzed these cognitive distortions in relation to the mathematical dimension of gambling and found that most of them are mathematically related (Bărboianu, 2022, pp. 219-221).

An important element that shapes and influences the aspects of gambling mentioned above, especially cognitive distortions, is language. The language of gambling can be intentionally or innocently misleading, confusing or conflicting, largely due to the mathematical nature of the essential concepts governing gambling, but also to the nature of language itself. The language of gambling unavoidably uses mathematical and mathematically-related terms and as such is a mixed language and therefore predisposed to semantic conflicts. This language may aim toward descriptions of the games, of their associated strategies, for communication between gamblers and between gamblers and experts, and to express any observations or research results in regard to this phenomenon. The fact that some specialized terms belong or are tightly related to probability theory accounts for their conflicting potential in the gambling language, since the concepts of probability theory are sensitive to interpretation, despite their mathematical nature (Bărboianu, 2022, pp. 203-218). The problematic gambling language manifests in the activity spheres of developers, operators, gambling communities, information providers, experts (including problemgambling experts), and gamblers' relationships with these people. This language affects the descriptions of games and gambling that the players actually use to become informed about the phenomenon; also affected are the communication between gamblers, and between gamblers and people from the gambling industry or experts as well as gamblers' own conceptual judgments related to gambling.

Goals and outcomes of the study

In this theoretical framework, research is able to derive concrete norms and criteria to adequately reflect the mathematical dimension of gambling in the communication and texts associated with the gambling industry. These norms and criteria of adequacy will be further communicated to policy and decision makers in both governmental and private sectors, with the recommendation for implementation. Our study aims to evaluate qualitatively the reflection of the mathematical dimension of gambling in the content of gambling websites. This analysis is necessary in order to have an objective and concrete image of the actual state of this matter in the online industry and of the challenges that such research and application would face in the real world of gambling. A minimum number of 120 gambling websites will be reviewed annually for their content in that respect. A statistical analysis will record the presence of the mathematical dimension of gambling and its forms in the content of participating websites, and a qualitative research will analyze and assess the quality of the content with respect to that dimension.

Methods and technical description of the instruments

The current study is a combination of quantitative and qualitative analysis, in which the latter is predominant and is given the central role.

The participants in the study (gambling websites, through their webmasters) were recruited through online advertising and direct invitations. Given the focus on the qualitative aspect of the study, the sample is not representative for the entire population.

Besides, representativeness cannot be established with respect to the specificity of the population (gambling websites) and of the targets of the study. The criteria of eligibility for participation that we have applied are:

-not having legally prohibited content or advertising; -meeting the gambling legal requirements; -having informative content besides the games and games' rules -being fully operational and navigable.

The quantitative analysis will use basic descriptive-statistics methods, summarizing the data recorded from the sample by standard statistical indicators, with the following main specific variables: v₁ -the presence of structural descriptions of the games in parametric terms (valued yes/no); v₂ -the presence of informative sections ('How to' articles, blogs, guides) (valued yes/no); v₃ -the presence of sections dedicated to odds/probability/math (valued yes/no); v₄ -the usage of essential math terms specific to gambling (odds/probability, expectation, average/mean, etc.) (valued yes/no); v₅ -the presence of the definitions of the math terms used (valued yes/no); v₆ -the correctness of the math definitions used (valued on a scale from 0 to 5) v₇ -the presence of game strategy topics (valued yes/no); v₈ -the presence of math-based game strategy topics where applicable (using notions of probability theory, statistics, and game theory) (valued yes/no); v₉ -the presence of systematic-learning or advanced content of gambling math (lessons, academy-style sections, in-depth guides, etc.) (valued yes/no); v₁₀ -the mentioning of author for math-related articles (valued yes/no); v₁₁ -the match between the math-related articles and their authors' declared expertise (valued on a scale from 0 to 3); v₁₂ -in-text presence of awareness on possible misconceptions, fallacies, and irrational beliefs in regard to gambling (valued yes/no); v₁₃ -the correlation of the above awareness with the mathematical aspects of gambling (valued on a scale from 0 to 3).

The values are conditional on each other as follows: v₃, v₇, v₉ conditional on v₂; v₅ conditional on v₄; v₆ conditional on v₅; v₈ conditional on v₇; v₁₁ conditional on v₁₀; v₁₃ conditional on v₁₂.

The qualitative analysis will use as methods discourse analysis, content analysis, thematic analysis, conceptual interpretation, semantic analysis, doubt about sense, and analysis of arguments. It will have a strong component of linguistic-conceptual-logical analysis, targeting the following main elements: 1 -the usage of terms with non-uniform semantics; 2 -the contextual usage of math terms; 3 -the conceptual linkages relative to the relevance for the topic; 4 -the soundness of arguments based on applied math; 5 -the association between game strategy and the concepts of probability theory and game theory; 6 -the presence and contextual impact of "mathematically prohibited" or misleading terms (such as 'winning strategy', 'how to win', etc.).

Although the qualitative analysis is independent of the quantitative one, correlations will be made between the conclusions of the former and the variables of the latter. Representation of the mathematical dimension of gambling may or may not be adequate in the content of gambling websites. The main goal of the qualitative analysis is to establish the disciplinary areas, as well as their individual roles, which can contribute to the theoretical framework that will derive the norms and criteria for such adequacy in the content of the websites and of the gambling communication. These disciplinary areas entitled for involvement include mathematics, psychology, linguistics, philosophy of language, epistemology, and philosophy of mathematics.

Content and roles of the technical reports

Monthly technical reports describing the partial results of the qualitative analysis will be published on academic channels, preceding the main publication at the end of the study. Each technical report will cover the review and recording of data from ten websites, which are nominated in the section titled Appendix, along with brief descriptions from their owners. We found such technical reports necessary, first because the current study is atypical in what concerns the statistical analysis and the qualitative analysis, as well as the objects under investigation. Therefore, the main role of the technical reports is to detect and define any methodological and technical difficulties encountered during this study and any challenges they may pose, for them to be analyzed and surmounted in both the continuation of the current study and any future similar research. Besides presenting these difficulties and challenges, the technical reports will also contain unpredicted observations regarding the analyzed content that might require the revision or change of the methods and instruments used. The results of the technical reports will be gathered, and general conclusions will be drawn in the main publication.

Observations and conclusions from the review of the current sample

In regard to both the qualitative and the statistical analyses, we initially adopted a random approach to sampling (not representative for the entire "population"), and motivated it through the focus on the qualitative aspect of the study. In fact, representativeness cannot be established for gambling websites as relative to any statistical study of their content. When we investigate the adequacy, consistency, language, and objective information of website content in a certain niche, we must not forget that such investigation indirectly targets the users of the websites. Therefore, when inquiring about the adequacy of representativeness, we should start from how users reach those websites rather than the criteria by which gambling websites can be categorized. The main means by which users reach gambling websites is Google search. It is known that the Google search engine returns websites for a certain query (keyword) in what is called the Google ranking: Sites ranked higher by Google algorithms appear in the top of the search results. Google ranks websites by criteria of content -the more relevant the content of a website as determined by Google with respect to a certain keyword, the higher in the search results (by that keyword) that website will appear.

Therefore, it is fair to hypothesize that gambling websites ranking higher in Google's metrics will be reached more often by the users searching for gambling keywords than other gambling sites. This is the motive through which we decided to introduce, as participants to the study, gambling websites that rank high in Google searches. Among the general keywords used in searches were gambling, gambling strategy, rules of […] (each casino game mentioned per keyword), gambling guide, casino guide, and so on. We have not established a specific share of these sites among all the sites reviewed as being representative, as we have no measure of which sites are reached more than others. Other search engines exist and are used as well, and more particular keywords are available for searching. Furthermore, there are other means by which users can reach gambling websites of a lower Google rank, such as gambling/casino forums or groups in social media. On the other hand, it is expected that high-ranked websites have reached a certain level of professionalism in regard to their content (for example, due to a higher operating budget, they can afford to hire expert writers), which raises again an issue of representativeness for the statistical study. However, with the review of the current sample, which includes high-ranked websites, we found, surprisingly, that such websites do not jump much afar of the tendency contoured with the review of the previous samples with respect to the reflection of the mathematical dimension of gambling: Although expert content was detected (strategy guides, myths & facts, questions & answers, and even learning hubs), the qualitative analysis of the content of these sections showed that the mathematical dimension of gambling is still far from being adequately reflected. For instance, even in articles signed by experts, we found no definitions of the math terms used (counted by variable v₅), and in general, the presentation of the mathematical facts of the topic was not systematic. With the current sample, it became obvious that investigating in greater depth the language of the content is essential, since language is responsible for several cognitive distortions related to gambling-math. The mixed content (using both mathematical and non-mathematical terms) continues to lack both references to the formal definitions of the math terms and their adequate interpretation in the real world of gambling. The organization and structure of websites' content is important in directing the user to the right path for acquiring and understanding the needed information (e.g., some topics must be read before others, especially when gambling math is concerned); they are important even in saving the user's time, as an adequate organization and structure visible from the homepage may let the user know from the start that the website is not what they are looking for. From our analysis, it follows that in general, those websites with inadequate organization and structure show poor content as well. A new finding was a correlation between the profiles of the head team members of the websites (those presenting their staff) and the mathematical content present in the website. Mathematical content and a certain approach to the expert topics were detected for websites whose head team members indicate a technical-economic-mathematical background in their bio; that content and approach were not detected otherwise. (There are a few exceptions for websites using expert writers other than their staff.) As detected in previous samples, the marketing policy of the websites impacts their content, especially when talking about affiliate sites. Such websites' content is focused on casino reviews and advertising the games they offer, to the exclusion of an expert description of the games and gambling. The statistical analysis confirmed again the tendencies contoured with the previous samples. Variable v₁ -the presence of structural descriptions of the games in parametric terms -remained null after over 50 websites reviewed, including those high-ranked and with expert content. Only three sites showed an in-text presence of awareness of possible misconceptions, fallacies, and irrational beliefs in regard to gambling (variable v₁₂), of which two correlated this awareness with the mathematical aspects of gambling (variable v₁₃). The analysis will continue with the next samples by using the new (keyword search) approach to sampling and putting greater emphasis on language.

anygamble.com (reviewed in June 2023) Information about gambling, casino games and online casinos. Detailed tests and results of many betting systems. Apps and tools helping players in their gaming decision-making. fr-casinospot.com (reviewed in June 2023) Site with independent reviews of licensed casinos and slot machines for France. It contains guides, tips and ratings based on evaluation of bonuses, security, payment systems, etc. casinospot.de (reviewed in June 2023) Site with independent reviews of licensed casinos and slot machines for Germany. It contains guides, tips and ratings based on evaluation of bonuses, security, payment systems, etc. nostrabet.com (reviewed in June 2023) Platform where punters get to know the basics of betting by evaluating and exemplifying trending gambling practices. It covers authoritative guides, tested strategies, and in-depth bookmaker reviews.

dkcasinospot.dk (reviewed in July 2023) Site with independent reviews of licensed casinos and slot machines for Denmark. It contains guides, tips and ratings based on evaluation of bonuses, security, payment systems, etc. nlcasinospot.nl (reviewed in July 2023) Site with independent reviews of licensed casinos and slot machines for the Netherlands. It contains guides, tips and ratings based on evaluation of bonuses, security, payment systems, etc.