Números topológicos en programas concurrentes para no viajar en el tiempo

Abstract

Los análisis estáticos para programas concurrentes se enfrentan a un problema particular: deben considerar todos los entrelazamientos de un conjunto de hilos, y excluir aquellas que sean imposibles. Para ello, una alternativa popular es el uso de órdenes en las sentencias de un programa. Esto permite determinar qué sentencias pueden ser ejecutadas antes o después de cuáles, de modo que cada hilo queda ordenado. Los números topológicos son uno de estos órdenes y son calculados a partir de una versión modificada de los grafos de flujo de control interprocedurales. Se utilizan para análisis estáticos, como por ejemplo la fragmentación de programas concurrentes (slicing). Nuestro trabajo define formalmente una técnica para asignar números topológicos a cualquier programa. Nuestras contribuciones son un contraejemplo al enfoque anterior, mostrando que falla en algunas situaciones; nuevas definiciones y formalismos; y una implementación de nuestra técnica en un fragmentador de programas para Java.