Parametric specifications of dynamic memory utilization

En los últimos años se ha visto un gran interés en las comunidades de sistemas de tiempo real y embebidos en el uso de de lenguajes orientados a objetos tipo Java. Los motivos de este interés se deben en parte a que este tipo de tecnologías facilitan la encapsulación de abstracciones y la comunicación mediante interfaces bien de_nidas. Otro aspecto importante es la gran comunidad de desarrolladores y la cantidad de bibliotecas y herramientas de desarrollo disponible. Sin embargo, para poder adoptar lenguajes de este tipo en ambientes embebidos y de tiempo real hay que solucionar al menos dos grandes problemas: la impredictibilidad temporal dada por las interrupciones relacionadas con la colección de objetos (garbage collector) y poder analizar requerimientos de memoria de las aplicaciones. Ha habido un número importante de trabajos donde se intenta atacar el problema de impredictibilidad temporal de los administradores de memoria automáticos desde distintos enfoques tales como garbage collectors con ciertas garantías temporales o directamente utilizando modelos alternativos de administración de memoria. Sin embargo, no ha habido muchos avances con respecto al estudio cuantitativo de requisitos de memoria. En esta tesis abordamos el problema de predecir automáticamente certi_cados de utilización y requisitos de memoria. Para ellos presentamos primero una técnica que permite obtener expresiones paramétricas de las solicitudes de memoria dinámica sin considerar ningún mecanismo de colección de objetos. Luego proponemos un esquema alternativo de administración de memoria junto con una técnica que permite la transformación de código Java convencional en otro con la misma funcionalidad pero adaptado para la nueva política de manejo de la memoria. Bajo este nuevo esquema, proponemos una técnica que permite determinar de manera paramétrica la cantidad de memoria necesaria para correr el programa o parte de él. Todas estas técnicas fueron implementadas en un prototipo que nos permitió analizar automaticamente un conjunto interesante de aplicaciones siendo los resultados iniciales bastante promisorios.Current trends in the embedded and real-time software industry are leading towards the use of object-oriented programming languages such as Java. From the software engineering perspective, one of the most attractive issues in objectoriented design is the encapsulation of abstractions into objects that communicate through clearly de_ned interfaces. However, in order to be able to successfully adopt languages with object oriented features like Java in embedded and real-time systems, is necessary to solve at least two problems: eliminate execution unpredictability due to garbage collection and automatically analyze memory requirements. There has been some work trying to deal with the _rst problem but the problem of computing memory requirements is still challenging. In this thesis we present our approach to tackle both problems by presenting solutions towards more predictable memory management and predicting memory requirements. The e_ort is mainly focused in the latter problem as we found it hard, less explored, strongly relevant for all kinds of embedded systems and its applicability and usefulness is beyond real-time applications. This thesis presents a series of techniques to automatically compute dynamic memory utilization certi_cates. We start by computing a technique that produces parametric speci_cations of memory allocations without consider any memory reclaiming mechanism. Then, we approximate object lifetime using escape analysis and synthesize a scoped-based memory organization where objects are organized in regions that can be collected as a whole. We propose a technique to automatically translate conventional Java code into code that safely adopts this memory management mechanism. Under this new setting we infer parametric speci_cations of the size of each memory regions. Finally, we predict the minimum amount of dynamic memory required to run a method (or program) in the context of scoped memory management by computing parametric speci_cations of the size of memory regions and by modeling the potential con_gurations of the regions in run time. We develop a prototype tool that implemented the complete chain of techniques and allow us to experimentally evaluate the e_ciency and accuracy of the method on several Java benchmarks. The results are very encouraging.Fil:Garbervetsky, Diego. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina