FACULTAD DE INFORMATICA UNIVERSIDAD COMPLUTENSE DE MADRID PROYECTO DE SISTEMAS INFORMATICOS ProsymbABS Perfilador simbólico para objetos concurrentes Nícolas Paolo Bueno Cavero Javier Gómez Edo Curso 2013-2014 Directora: Elvira Albert Albiol FACULTAD DE INFORMATICA UNIVERSIDAD COMPLUTENSE DE MADRID PROYECTO DE SISTEMAS INFORMATICOS ProsymbABS Perfilador simbólico para objetos concurrentes Nícolas Paolo Bueno Cavero Javier Gómez Edo Curso 2013-2014 Directora: Elvira Albert Albiol Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo     II    Los alumnos abajo firmantes autorizan a la Universidad Complutense de Madrid  a  difundir  y  utilizar  solo  con  fines  académicos,  no  comerciales, mencionando  expresamente  a  sus  autores,  tanto  la  propia  memoria,  como  el  código,  los  contenidos  audiovisuales  incluso  si  incluyen  imágenes  de  los  autores,  la  documentación y/o el prototipo desarrollado.  Madrid, 23 de Junio de 2014.  Nícolas Paolo Bueno Cavero                                      Javier Gómez Edo  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo     III    Agradecimientos   En primer lugar quisiéramos agradecer a nuestra tutora Elvira Albert Albiol por la guía  y la ayuda prestada durante el desarrollo del proyecto.    A mi familia por todo el apoyo que me han dado durante toda la carrera y que me han  ayudado a ser la persona que soy hoy en día. A mis amigos, tanto las nuevas amistades  que me han  ayudado  a  sobrellevar  la  carrera de  la mejor manera posible  como  las  amistades de toda la vida que siempre han estado ahí conmigo.  Javier    A todos mis seres queridos que siempre han estado conmigo, en especial a mi madre  que  siempre  me  ha  soportado  y  que  sin  ella  no  habría  sido  esto  posible.  A  mis  hermanos y amigos, que me han brindado su apoyo.    Nícolas    A todos ellos muchas gracias.                    Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo     IV    Resumen   ProsymbABS  es  una  aplicación  desarrollada  para  computar  el  consumo  de  recursos  simbólicos  obtenidos  tras  ejecutar  programas  ABS,  los  cuales  están  basados  en  el  paradigma de los objetos concurrentes.   Es simbólico puesto que ofrece una representación simbólica del consumo de recursos,  contando, para ello, el número de objetos creados  (incluyendo sus  tipos), el número  de llamadas a métodos y el número de instrucciones ejecutadas.  La aplicación recibe el árbol sintáctico del código ABS compilado y trabaja sobre dicho  árbol para  calcular  los distintos  recursos  consumidos por  la ejecución del programa,  como  el  número  de  objetos  creados,  los métodos  ejecutados  por  cada  objeto,  el  número de instrucciones ejecutadas y el tiempo de ejecución.  Para facilitar el manejo de la herramienta hemos desarrollado un entorno basado en el  banco de trabajo de “Eclipse” donde el programador puede escribir el código ABS y ver  los resultados de la ejecución de ProsymbABS sobre ese código fácilmente.      Palabras clave:  - Concurrencia.  - Compilación.  - Consumo de recursos.  - Banco de trabajo.  - ABS.        Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo     V    Abstract   ProsymbABS is an application developed to compute the symbolic resources consumed  by the execution of ABS programs, based on the paradigm of concurrent objects.  It  is  symbolic  because  it  provides  a  symbolic  representation  of  the  resource  consumption, by counting  the number of objects created  (including  their  types),  the  number of method calls and the number of instructions executed.  The application receives the ABS syntax tree, from the compiled code, and executes it  to  calculate  the  different  resources  consumed  by  the  program  execution,  as  the  number  of  objects  created,  the methods  executed  by  each  object,  the  number  of  instructions executed and the execution time.  To facilitate the use of the tool, we have developed an execution environment based  on “Eclipse’s” workbench where the programmer can write the ABS code and see the  result of the execution of that code with the ProsymbABS tool.   Keywords:  - Concurrence.  - Compiling.  - Resource consumption.  - Workbench.  - ABS.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo     VI    Tabla de figuras Figura 1.1: Sintaxis del nivel de ABS para objetos concurrentes ................................... 10  Figura 2.1: Ejemplo código MainClass ............................................................................ 13  Figura 2.2: Ejemplo código ObjetoConcurrente ............................................................. 14  Figura 2.3: Ejemplo código Contexto ............................................................................. 15  Figura 2.4: Diagrama de clases del paquete Main ......................................................... 15  Figura 2.5: Ejemplo código Interfaz ................................................................................ 16  Figura 2.6: Diagrama de clases del paquete Interfaz ..................................................... 17  Figura 2.7: Ejemplo de código ComandoAwait .............................................................. 18  Figura 2.8: Diagrama de clases del paquete Comandos................................................. 18  Figura 2.9: Ejemplo código Booleano ............................................................................. 19  Figura 2.10: Ejemplo código Futuro ............................................................................... 20  Figura 2.11: Diagrama de clases del paquete TipoValue ............................................... 20  Figura 2.12: Ejemplo código AsyncCall ........................................................................... 22  Figura 2.13: Ejemplo código ConstObjConcurrente ....................................................... 23  Figura 2.14: Ejemplo código ConstInt ............................................................................. 23  Figura 2.15: Ejemplo código ExprGet ............................................................................. 24  Figura 2.16: Diagrama de clases del paquete Expresiones ............................................ 24  Figura 3.1: Programa de fibonacci ABS .......................................................................... 25  Figura 3.2: Diagrama secuencial de ejecución ABS ........................................................ 26  Figura 3.3: Resultado ejecución total en ProsymbABS................................................... 27  Figura 3.4: Ejecución parcial en ProsymbABS ................................................................ 29  Figura 3.5: Resultado ejecución parcial en ProsymbABS ............................................... 30  Figura 4.1: Interfaz de la aplicación ................................................................................ 31  Figura 4.2: Pestaña Archivo ............................................................................................ 32  Figura 4.3: Selección de archivo ABS .............................................................................. 32  Figura 4.4: Interfaz con código compilado ..................................................................... 33  Figura 4.5: Error en el código ABS .................................................................................. 33  Figura 4.6: Panel de planificaciones ............................................................................... 34  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo     VII    Figura 4.7: Interfaz de la aplicación con código ............................................................. 35  Figura 4.8: Botón play ..................................................................................................... 36  Figura 4.9: Panel de clases .............................................................................................. 37  Figura 4.10: Panel de método ........................................................................................ 38  Figura 4.11: Consola de la interfaz ................................................................................. 39  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo     VIII      INDICE  Agradecimientos .............................................................................................................. III  Resumen .......................................................................................................................... IV  Abstract ............................................................................................................................ V  Tabla de figuras ............................................................................................................... VI  1.  Introducción .............................................................................................................. 1  2.  Estado del arte .......................................................................................................... 3  2.1.  Profiling .............................................................................................................. 3  2.2.  Concurrencia ...................................................................................................... 3  2.2.1.  Beneficios de la programación concurrente .............................................. 4  2.2.2.  Problemas inherentes a la programación concurrente.............................. 5  2.3.  Lenguaje ABS ...................................................................................................... 6  2.3.1.  Abstract Behavioral Specification ............................................................... 7  2.3.2.  Diseño y estructura de ABS ........................................................................ 7  2.3.3.  Modelo de concurrencia de ABS ................................................................ 8  2.3.4.  Nivel de objetos concurrentes del núcleo ABS ........................................... 8  2.3.4.1.  Suspend ............................................................................................... 9  2.3.4.2.  Await ................................................................................................... 9  2.3.4.3.  Llamadas síncronas y asíncronas ........................................................ 9  2.3.4.4.  Operaciones para variables futuras .................................................... 9  2.4.  Motivación ....................................................................................................... 10  3.  Implementación ...................................................................................................... 12  3.1.  Organización de ProsymbABS .......................................................................... 12  3.1.1.  Main .......................................................................................................... 13  3.1.2.  Interfaz ...................................................................................................... 15  3.1.3.  Comandos ................................................................................................. 17  3.1.4.  TipoValues ................................................................................................ 18  3.1.5.  Expresiones ............................................................................................... 21  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo     IX    4.  Resultados obtenidos .............................................................................................. 25  5.  Manual del usuario.................................................................................................. 31  5.1.  Inicio ................................................................................................................. 31  5.2.  Edición .............................................................................................................. 32  5.3.  Errores .............................................................................................................. 33  5.4.  Planificación ..................................................................................................... 34  5.5.  Ejecución .......................................................................................................... 35  5.5.1.  Ejecución total del programa ABS ............................................................ 35  5.5.2.  Ejecución parcial del código ABS .............................................................. 36  5.6.  Resultados ........................................................................................................ 38  6.  Conclusiones............................................................................................................ 40  6.1.  Trabajos futuros ............................................................................................... 41  7.  Referencias y bibliografía ........................................................................................ 42  8.  Apéndice .................................................................................................................. 44    Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       1 1. Introducción   Durante  los  primeros  años  del  desarrollo  de  los  ordenadores,  el  hardware  representaba  el  coste  dominante  de  los  sistemas  y  debido  a  ello  los  estudios  de  rendimiento  se  concentraban  en  el  hardware.  Actualmente,  según  la  tendencia  apreciable, el  software  representa una porción  cada  vez mayor de  los presupuestos  informáticos,  incluye  el  sistema  operativo  de  multiprogramación/multiproceso,  sistemas de comunicaciones de datos, sistemas de administración de bases de datos,  sistemas de apoyo a varias aplicaciones. Por lo tanto, la necesidad de evaluación de las  prestaciones  es  una  consecuencia  natural  del  aumento  de  la  potencia  y  de  la  complejidad de los sistemas.   En  los primeros tiempos  los ordenadores eran concebidos para que  fuesen utilizados  en  su  totalidad  por  el  programador  (prácticamente  no  existía  el  software),  y  los  elementos  fundamentales  para  la  medición  eran  la  longitud  de  la  palabra  del  ordenador, el  conjunto de  instrucciones y  su  implementación, el  ciclo de base de  la  CPU,  el  tiempo  de  ejecución  de  una  instrucción  característica  (Por  ejemplo  la  instrucción sumar).   La  aparición  del  software,  de  los  periféricos  cada  vez  más  sofisticados,  y  de  las  unidades  centrales  más  complejas  (multiprocesadores,  pipelines,  memorias  cache,  etc.) con sistemas de interrupciones muy sofisticados, el aumento de la dimensión de  las memorias,  todo  ello  ha  hecho  que  la  evaluación  del  comportamiento  se  haya  convertido  en  un  cuerpo  de  doctrina  en  el  que  no  sólo  se  ha  de  considerar  el  hardware,  sino  también  las  facilidades  proporcionadas  por  el  software  al  acercar  la  máquina a los usuarios, provocando entonces la aparición del “overhead” (es decir, de  los  gastos  generales  de  la  máquina  para  repartir  los  recursos  entre  los  distintos  usuarios) que lleva asociado todo software.   Todas estas consideraciones hacen comprender que la evaluación del comportamiento  no  es  tarea  sencilla,  ya que ha de  tener en  cuenta muchos  y  variados  aspectos del  hardware, del software y de las aplicaciones que se han de llevar a cabo en el sistema  informático.  En  consecuencia,  evaluamos  un  sistema  para  comprobar  que  su  funcionamiento es el correcto, es decir, el esperado.   El  análisis  de  software es  el  proceso  automatizado  de  analizar  el  comportamiento  del software. Existen dos tipos principales de análisis, el análisis estático de software y  el análisis  dinámico  de  software.  Estas  técnicas  de  análisis  intentan  encontrar  y  mejorar en un software cuestiones de correctitud, optimización y seguridad.   Análisis estático de software: se realiza sin ejecutar el programa. En la mayoría  de los casos, el análisis se realiza en alguna versión del código fuente y en otros  casos  se  realiza en el  código objeto. El  término  se  aplica generalmente  a  los  análisis realizados por una herramienta automática, el análisis realizado por un  humano  es  llamado comprensión  de  programas como  también revisión  de  código.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       2  Análisis  dinámico  de  software:  supone  la  ejecución  del  programa  y  observación  de  su  comportamiento.  Para  que  el  análisis  dinámico  resulte  efectivo el programa a ser analizado se debe ejecutar con los suficientes casos  de prueba como para producir un comportamiento interesante, se pueden usar  varias  estrategias  de pruebas  de  software para  lograr  esto  tales  como  cobertura de código o  simplemente programas conocidos como “fuzzers” que  ayudan  a  asegurar  que  una  porción  adecuada  del  conjunto  de  posibles  comportamientos del programa ha sido observada.                                            Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       3   2. Estado del arte   2.1. Profiling   El  análisis  de  rendimiento,  comúnmente  llamado profiling,  es  la  investigación  del  comportamiento de un programa de computadora usando  información reunida desde  el análisis  dinámico del  mismo.  El  objetivo  es  averiguar  el  consumo  de  recursos  obtenidos tras la ejecución de diferentes partes del programa para detectar los puntos  problemáticos  y  las  áreas  donde  sea  posible  llevar  a  cabo  una optimización  del  rendimiento (ya  sea  en  velocidad  o  en  consumo  de  recursos). Un  profiler  puede  proporcionar distintas salidas, como una traza de ejecución o un resumen estadístico  de los eventos observados.  Normalmente el profiling es utilizado durante el desarrollo de software como método  para la depuración y optimización de los algoritmos, esta práctica vista de esta manera  es  buena,  pero  es  vista  más  como  una  actividad  interna  que  suele  carecer  de  información  cuando  no  es  evaluado  por  personal  realmente  especializado  y  en  el  entorno adecuado para ello.  El profiling  se puede  llevar a  cabo en el código  fuente o  sobre un binario ejecutable  mediante una herramienta llamada “profiler”.  En 1994, Amitabh Srivastava y Alan Eustace de Digital Equipment Corporation publican  un artículo describiendo ATOM. ATOM es una plataforma para convertir un programa  en  su  propio  profiler.  Es  decir,  en tiempo  de  compilación,  inserta  el  código  en  el  programa a ser analizado. Ese código introducido produce salidas de datos de análisis.  “Las  herramientas  de  análisis  de  programas  son  extremadamente  importantes  para  entender  el  comportamiento  de  los  programas.  Los  arquitectos  informáticos necesitan esas herramientas para evaluar cómo  rendirán  los programas en nuevas arquitecturas.  Los desarrolladores de  software  necesitan  herramientas  para  analizar  sus  programas  e  identificar  secciones  críticas  de  código.  Los  desarrolladores  de  compiladores  a  menudo  utilizan  herramientas  para  saber  cómo  funcionará el algoritmo de predicción de  saltos o  la planificación de  las  instrucciones.”  ‐  Amitabh Srivastava y Alan Eustace – ATOM, 1994    2.2. Concurrencia   El  paradigma  de  la  concurrencia  consiste  en dos  o más  procesos  que  entrelazan  su  ejecución. No tienen por qué ejecutarse exactamente al mismo tiempo, simplemente  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       4 es  suficiente  con  el  hecho  de  que  existe  un  intercalado  entre  la  ejecución  de  sus  instrucciones. Si se ejecutan al mismo tiempo los dos procesos, entonces tenemos una  situación de programación paralela.  Un programa, al ponerse en ejecución, puede dar lugar a más de un proceso, cada uno  de ellos ejecutando una parte del programa. Podemos definir un proceso como una  actividad  asíncrona  susceptible  de  ser  asignada  a  un  procesador.  Cuando  varios  procesos se ejecutan concurrentemente puede haber procesos que colaboren para un  determinado  fin, mientras que puede haber otros que compitan por  los recursos del  sistema. Para llevar a cabo estas tareas de colaboración y competencia por los recursos  se  hace  necesaria  la  introducción  de mecanismos  de comunicación y sincronización  entre procesos.  2.2.1. Beneficios de la programación concurrente Existen diversos motivos por los que la programación concurrente es útil. Por ejemplo:   Velocidad  de  ejecución: Cuando  la  ejecución  de  un  programa  conlleva  la  creación  de  varios  procesos  y  el  sistema  consta  de más  de  un  procesador,  existe la posibilidad de asignar un proceso a cada procesador de tal forma que  el programa se ejecuta de una forma más rápida.   Solución  de  problemas  inherentemente  concurrentes: Hay  problemas  cuya  solución es más fácil de abordar mediante el uso de programación concurrente.  Destacamos los que se nombran a continuación:  o 1. Sistemas de control: Los sistemas de control son aquellos sistemas en  los  que  hay  una  captura  de  datos.  La  recolección  de  datos  se  puede  estar  haciendo  de  diversas  entidades  físicas  como  por  ejemplo  en  edificios  o  en  estancias  dentro  de  un  edificio.  No  sería  tolerable  un  sistema  secuencial  que  vaya  capturando  los  datos  uno  a  uno  de  las  distintas estancias. Podría haber un incendio en el edificio y si los datos  se tomarán de forma secuencial, mientras que se capturan los datos de  la última estancia, podría haberse quemado la primera. Por ello, tanto la  captura  de  los  datos  como  su  tratamiento  y  posterior  actuación  son  candidatos a ser procesos distintos y de naturaleza concurrente.  o 2.  Tecnologías Web: La mayoría de  los programas  relacionados  con  la  web  son  concurrentes.  Servidores  web  que  son  capaces  de  atender  concurrentemente múltiples conexiones de usuarios, programas de chat  que permiten mantener  la conversación de varios usuarios, servidores  de correo que permiten que múltiples usuarios puedan mandar y recibir  mensajes al mismo tiempo, navegadores que permiten que un usuario  pueda estar haciendo una descarga mientras navega por otras páginas,  etc.  o 3.  Aplicaciones  basadas  en  interfaces  de  usuarios: La  concurrencia  en  este  tipo  de  aplicaciones  va  a  permitir  que  el  usuario  pueda  interaccionar con la aplicación aunque ésta esté realizando alguna tarea  que  consume mucho  tiempo  de  procesador.  Un  proceso  controla  la  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       5 interfaz mientras otro hace la tarea que requiere un uso intensivo de la  CPU. Esto facilitará que tareas  largas puedan ser abortadas a mitad de  ejecución.  o 4.  Simulación: Los  programas  secuenciales  encuentran  problemas  al  simular  sistemas  en  los  que  existen  objetos  físicos  que  tienen  un  comportamiento  autónomo  independiente.  La  programación  concurrente  permitirá  modelar  esos  objetos  físicos  y  ponerlos  en  ejecución de forma independiente y concurrente, sincronizándolos de la  forma apropiada.  o 5. SGBD: En Sistemas Gestores de Bases de Datos la concurrencia juega  un  papel muy  importante  cuando  se  va  a  permitir  a  varios  usuarios  interactuar  con  el  sistema.  Cada  usuario  puede  ser  visto  como  un  proceso. Obviamente  hay  que  implementar  la  política  adecuada  para  evitar situaciones en las que dos usuarios modifican al mismo tiempo un  registro.  Sin  embargo,  a  varios  usuarios  que  quieran  acceder  a  un  mismo registro para consultarlo y no modificarlo, debe permitírseles un  acceso concurrente.   Mejor rendimiento.    2.2.2. Problemas inherentes a la programación concurrente Hay tres problemas inherentes a la programación concurrente que son:   EXCLUSIÓN MUTUA  Cuando dos procesos P1 y P2 se ejecutan concurrentemente están accediendo al  mismo  tiempo  a  una  variable  compartida  entre  los  dos  para  actualizarla.  Nos  interesa que todas las líneas de código de un proceso se ejecuten en un solo paso  sin ningún tipo de intercalado con las otras líneas del otro proceso. A la porción de  código que queremos que se ejecute de  forma  indivisible se  le denomina sección  crítica. Nos interesa asegurarnos que las secciones críticas se ejecuten en exclusión  mutua, es decir,  sólo uno de  los procesos debe estar en  la  sección  crítica en un  instante dado.   La programación concurrente debe proporcionarnos mecanismos para especificar  que partes del código han de ejecutarse en exclusión mutua con otras partes. La  exclusión mutua es un problema derivado de la abstracción en los lenguajes de alto  nivel. Una  instrucción de alto nivel  se  convierte en un  conjunto de  instrucciones  máquina.  Estas  instrucciones  máquina  son  las  que  realmente  se  ejecutan  concurrentemente. En el paradigma secuencial este hecho carece de  importancia  pero  en  ejecuciones  concurrentes  de  instrucciones  el  resultado  puede  ser  incorrecto.   CONDICIÓN DE SINCRONIZACIÓN  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       6 Hay situaciones en las que el recurso compartido por varios procesos, se encuentra  en un estado en el que un proceso no puede hacer una determinada acción con él  hasta que no cambie su estado. A esto se le denomina condición de sincronización.  La programación  concurrente ha de proporcionarnos mecanismos para bloquear  procesos que no puedan hacer algo en un momento determinado a  la espera de  algún  evento,  pero  también  permita  desbloquearlos  cuando  ese  evento  haya  ocurrido.   VERIFICACION  En los últimos años, la demanda de software fiable y de calidad ha crecido mucho  más  rápido que  la  tecnología  necesaria  para  su  producción.  La  complejidad  y  el  tamaño de  los programas actuales exigen el uso de herramientas  formales ágiles  que aseguren  la construcción de software correcto. Asimismo, con el crecimiento  explosivo  de  la  “tecnología  de  la  información”,  cobran  enorme  relevancia  los  análisis  y  demostraciones  de  propiedades  de  seguridad,  que  puedan  ayudar  a  evitar, por ejemplo, graves errores en protocolos de comunicación y servicios web.  Los  lenguajes  utilizados  en  este  ámbito  (XML,  HTML,  etc.)  plantean  el  reto  de  adaptar  convenientemente  las  técnicas  clásicas de  verificación, depuración, para  abordar este tipo de problemas.  Las  técnicas de  verificación de programas permiten demostrar que un programa  satisface sus especificaciones. Las técnicas de depuración de programas permiten  detectar las causas que introducen discrepancias entre el comportamiento real y el  comportamiento que se espera de un programa ayudando a corregir, en su caso,  las disfunciones encontradas. Puesto que tanto la verificación como la depuración  de programas necesitan considerar algún tipo de representación computable de la  semántica de  los sistemas considerados,  la  interpretación abstracta, como marco  general que permite diseñar, aproximar y comparar semánticas de programas que  expresan varios tipos de propiedades observables aporta una componente esencial  que añadir a las técnicas de verificación y depuración.  El propósito de este proyecto se va a centrar en resolver  los problemas derivados del  último punto. Es  interesante observar el comportamiento de  los programas a  la hora  de  repartir  el  consumo  de  recursos  entre  los  distintos  procesadores  ya  que  puede  haber  procesadores  que  reciban  una  alta  carga  de  trabajo  y  otros  que  no  estén  trabajando. Se puede conseguir una gran optimización en el código de  los programas  concurrentes conociendo su consumo de recursos.  ProsymbABS  es  un  perfilador  dedicado  al  estudio  del  consumo  de  recursos  de  aplicaciones concurrentes, basados en el lenguaje ABS.  2.3. Lenguaje ABS ABS  (“Abstract  behavioral  specification”)  es  un  lenguaje    para  los  el  modelado  y  desarrollo de sistemas distribuidos y concurrentes. ABS permite una especificación de  alto nivel de un sistema,  incluyendo su concurrencia y mecanismos de sincronización,  así como  las actualizaciones de estados  locales. Los modelos de ABS capturan el flujo  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       7 de control concurrente abstrayendo varios detalles de  implementación que resultaría  ser  ignorado  a  nivel  de  modelado,  tales  como  la  representación  concreta  de  estructuras  de  datos  internas,  la  planificación  de  las  activaciones  de método  y  las  propiedades de los entornos de comunicación.  ABS  está  dirigido  a  sistemas  distribuidos.  En  un  entorno  distribuido,  los  detalles  de  implementación de  los demás objetos del sistema no son necesariamente conocidos.  En vez de ello, ABS utiliza  interfaces como tipos para  los objetos, abstrayendo el tipo  de sistema de las clases que implementan la funcionalidad de los distintos objetos. ABS soporta llamadas asíncronas a métodos, las cuales pueden mandar tareas a otros  objetos sin transferir el control de  la  llamada, usando para ello  los tipos futuros. Una  característica  de  este  modelo  de  concurrencia  es  la  planificación  cooperativa  de  activaciones de métodos para controlar de forma explícita el intercalado interno de las  tareas dentro de los objetos concurrentes.  2.3.1. Abstract Behavioral Specification Los lenguajes de especificación se pueden dividir en tres categorías:   Lenguajes orientados al diseño: se centran en los aspectos estructurales de los  sistemas, así como en  la  relación entre clases y el control de mensajes entre  objetos.  Ejemplos  de  lenguajes  orientados  al  diseño  son  UML/OCL,  FDL  y  lenguajes de descripción arquitectural.   Lenguajes declarativos: se basan es aspectos funcionales como concurrencia e  interacción,  identificando un pequeño  conjunto de primitivas  y  su  semántica  formal. Ejemplos de lenguajes declarativos son los modelos de autómatas.   Lenguajes orientados a  la  implementación: se centran en  las propiedades del  comportamiento  de  sistemas  implementados.  Ejemplos  de  lenguajes  orientados a la implementación son JML y Spec#.  ABS  se  sitúa  en  esas  tres  categorías.  Comparte  con  los  lenguajes  orientados  a  la  implementación que está diseñado para que se acerque a la manera de pensar de los  programadores, es decir, es un  lenguaje de alto nivel, ya que mantiene una  sintaxis  parecida a  la de  Java. Por otro  lado, el  lenguaje  tiene unas  semánticas  formalmente  definidas, al estilo de  los  lenguajes declarativos, que permiten al modelador abstraer  detalles de  implementación  innecesarios debido a definiciones hechas por el usuario  de tipos de datos y funciones.  2.3.2. Diseño y estructura de ABS El modelo de concurrencia de ABS se divide en dos niveles y separa  la comunicación  local, síncrona y memoria compartida en el nivel inferior, de la comunicación asíncrona  sólo con paso de mensaje en el nivel superior.  El nivel inferior está basado en JCoBox [1] el cual generaliza el modelo de concurrencia  de  Creol  [2]  sobre  los  grupos  de  objetos  concurrentes  llamados  cogs.  Los  cogs  se  pueden  interpretar  como  componentes  de  ejecución  basados  en  objetos  con  sus  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       8 propios  heaps.  El  comportamiento  del  cog  se basa  en  una multitarea  de  peticiones  externas  y  activaciones  de  métodos  internos.  Únicamente  las  llamadas  asíncronas  pueden ocurrir entre diferentes cogs, los cuales no comparten el mismo heap.  Aparte  del  lenguaje  de  objetos  concurrentes,  ABS  soporta  tipos  definidos  por  el  usuario con funciones de primer orden. Se utilizan los tipos funcionales para simplificar  significativamente la especificación y verificación de programas ABS.  2.3.3. Modelo de concurrencia de ABS Conceptualmente,  cada  cog  tiene  un  procesador  dedicado  y  está  ubicado  en  un  entorno distribuido con comunicación asíncrona y desordenada.   El conjunto de objetos está ubicado dentro del cog. En el nivel superior del modelo de  concurrencia  de  ABS  toda  la  comunicación  se  realiza  entre  los  objetos  creados,  los  cuales están tipificados por interfaces, mediante llamadas asíncronas de métodos. Las  llamadas son asíncronas hasta que el objeto  llamante decide en tiempo de ejecución  cuando sincronizar la respuesta de tal llamada. Las llamadas asíncronas de métodos se  pueden  ver  como  disparadores  de  actividad  concurrente,  creando  nuevas  tareas  (también llamados procesos) en el objeto llamado.  ABS mezcla un comportamiento activo, caracterizado por un método principal, con un  comportamiento  pasivo,  caracterizado  por  llamadas  asíncronas  de  métodos.  Por  consiguiente, un objeto con un conjunto de procesos a ejecutar, originado por varias  llamadas asíncronas. Entre todos esos procesos al menos uno de los procesos de entre  todos los objetos del cog está activo y el resto están en suspensión en un inventario de  procesos.  El nivel de concurrencia de un programa ABS se refleja directamente en el número de  cogs introducidos en el programa. Un modelo Creol de concurrencia corresponde a un  programa ABS donde cada objeto tiene su propio cog.  2.3.4. Nivel de objetos concurrentes del núcleo ABS La  sintaxis  del  nivel  de  objetos  concurrentes  del  núcleo  ABS  se  puede  observar  a  continuación:  Syntactic categories Definitions C, I, m in Names P ::= Dd F IF CL {T x ; s} g in Guard IF ::= interface I { Sg } s in Statement CL ::= class C [(T x )] [implements I ] {T x ; M } Sg ::= T m (T x ) M ::= Sg {T x ; s} g ::= b | e? | g  g s ::= s; s | x = rhs | suspend | await g | skip | if b {s} [else {s}] | while b {s} | return e rhs ::= e | new [cog] C[( e )] | e!m( e ) | e.m( e ) | x.get   Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       9 El  bloque  principal  de  un  programa  equivale  a  la  especificación  del  cuerpo  de  un  método ({T x ; s}). Las expresiones de ABS incluyen la creación de objetos en el mismo  cog (escrito “new C (e )”), creación de objetos en nuevos cogs (escrito “new cog C(e )”),  llamadas a métodos, expresiones de asignación (booleanas, enteras, cadenas).  2.3.4.1. Suspend La primitiva suspend incondicionalmente libera al procesador suspendiendo el proceso  activo.   2.3.4.2. Await En  la expresión “await g”  la guarda g controla  la  liberación del proceso. Consiste en  una  condición  booleana  que  cuando  se  evalúa  a  falso,  el  procesador  se  libera  y  el  proceso  activo  se  suspende.    Cuando  el  procesador  se  encuentra  libre,  un  proceso  disponible en el conjunto de procesos suspendidos se ejecutará.  2.3.4.3. Llamadas síncronas y asíncronas La comunicación de ABS se basa en  llamadas asíncronas, denotadas por  la expresión  “o!m(e)”  y  en  llamadas  síncronas,  denotadas  por  la  expresión  “o.m(e)”,  donde  “o”  corresponde al objeto  llamante, el signo “!” denota una  llamada asíncrona y el signo  “.”  denota  una  llamada  asíncrona,  “m”  corresponde  al  nombre  del método  que  se  quiere  llamar y “e” corresponde a  los parámetros de entrada del método. Cualquier  método se puede llamar tanto síncrona como asíncronamente.  Tras realizar  la  llamada asíncrona “x = o!m(e)”, el procesador  llamante seguirá con su  ejecución  sin  parar  para  realizar  la  llamada.  Aquí  “x”  corresponde  a  una  variable  futura, es decir, una variable que corresponde al retorno de un valor el cual aún no se  ha calculado.  2.3.4.4. Operaciones para variables futuras Existen dos  tipos de operaciones que  se  realizan en  variables  futuras que  controlan  explícitamente la sincronización externa de ABS.   La primera operación  corresponde  a un  test de  retorno que  se ejecuta mediante el  comando “?”. Siendo “e” una expresión que denota una variable  futura,  la expresión  “e?”  se  evaluará  a  falso  hasta  que  se  responda  a  la  llamada  que  devuelva  el  valor  calculado  de  “e”  (estos  test  de  retorno  se  utilizan  principalmente  en  las  guardas  (comando await)).  La segunda operación  recupera el valor de  retorno de  la variable  futura mediante  la  expresión, en este caso, “e.get”, la cual bloquea la ejecución del procesador hasta que  el valor de retorno esté disponible.  En la página de HATS (http://tools.hats‐project.eu/) [5], podemos encontrar un manual  [6] más detallado de la sintaxis de ABS.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       10   Figura 1.1: Sintaxis del nivel de ABS para objetos concurrentes 2.4. Motivación El  hardware  ha  seguido  durante  años  la Ley  de Moore.  Las  velocidades  de  reloj  se  incrementaron y el software se escribía para explotar este crecimiento incesante en el  rendimiento,  a menudo  por  delante  de  la  curva  de  los  equipos  físicos.  Esa  relación  simbiótica entre hardware y software continuó sin cesar hasta hace muy poco. La Ley  de  Moore  sigue  vigente,  pero  se  ha  obviado  la  ley  no  escrita  que  dice  que  las  velocidades de reloj seguirán aumentando proporcionalmente siempre.  Las mejoras en el rendimiento de la memoria se quedan cada vez más por detrás de la  productividad del procesador, haciendo que el número de ciclos necesario de  la CPU  para acceder a  la memoria principal no pare de crecer continuamente. Esto es  lo que  se conoce como “Pared de memoria” (Memory Wall).  Los  ingenieros  de  hardware  han mejorado  el  rendimiento  del  software  secuencial  haciendo que las instrucciones se ejecuten antes de que se conozcan los resultados de  las  instrucciones  anteriores,  una  técnica  conocida  como  Paralelismo  a  nivel  de  instrucción (ILP son sus siglas en inglés). Las novedades en ILP son difíciles de predecir,  y su complejidad aumenta el consumo de energía. Como resultado de ello, las mejoras  en ILP también se han estancado, lo que resulta en la llamada “Pared ILP” (Wall ILP).  Hemos  llegado,  pues,  a  un punto  de  inflexión.  El  ecosistema  de  software  debe  evolucionar  para  apoyar mejor  y  adaptarse  correctamente  a  los  sistemas  de  varios  núcleos, y esta evolución  llevará  tiempo. Para beneficiarse de  la  rápida mejora en el  rendimiento  de  los  equipos  deberá  ejecutarse  cada  vez más  rápido  en  cada  nuevo  hardware.  La  comunidad  de  desarrolladores debe  aprender  a  construir  aplicaciones  simultáneas  multi‐hilo.  La  importancia  de la  arquitectura  y  el  diseño  limpio es  fundamental para la reducción de la complejidad del software, y mejora la capacidad y  facilidad  de mantenerlo.  Hay  que  poner  énfasis  en  la  comprensión,  no  sólo  de  las  capacidades de la plataforma, sino también de las mejores prácticas emergentes.  Para  el  desarrollo  de  ProsymbABS  se  ha  tenido  en  cuenta  todos  los  aspectos  relacionados  con el profiling en  sistemas  concurrentes. Puesto que el desarrollo del  hardware está  llegando a su  límite  físico, se postula como necesidad  la optimización  del software para mejorar el rendimiento de los programas. En concreto hay que tener  en cuenta la importancia de la concurrencia en el desarrollo software debido a que una  óptima  implementación  del  código  puede  aprovechar  todos  los  recursos  proporcionados por el ordenador.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       11 En  Java existen perfiladores  como  JProfiler  [3] o el  JBoss  [4], pero el  análisis de  los  programas  concurrentes  nos  llamó  bastante  la  atención  para  desarrollar  desde  el  principio un perfilador con las características y la estructura de datos más cómoda para  nosotros de obtener y guardar  la  información a estudiar. Con ello se pueden ampliar  los campos que abarca ProsymbABS.  ProsymbABS se va a centrar en el análisis del rendimiento (o consumo de recursos) del  software. Se tratará de un análisis dinámico ya que necesitamos ejecutar el programa  para  observar  el  comportamiento  de  su  ejecución  para  calcular  los  recursos  consumidos.  Como  el  proyecto  consiste  en  un  perfilador  simbólico,  guardaremos  la  información  que  recojamos  como  información  simbólica,  como  el  número  de  los  objetos  creados  (y  sus  respectivos  tipos),  el  número  de  llamadas  a  métodos  y  el  número de instrucciones ejecutadas.                                        Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       12   3. Implementación   Para desarrollar nuestro proyecto partimos del parser de ABS, el cual nos devuelve:   Detalle de  las  Interfaces,  clases  y métodos: A  partir  de  esta  información  se  pueden  crear  las  clases  de  las  que  se  compone  el  programa  ABS.  Con  esta  información obtenemos:  o Nombre de la clase.  o La interfaz que implementa.  o Atributos de clase.  o Sus método, de los método obtenemos:   Nombre del método.   Parámetros de entrada.   Atributos de método.   Tipo y atributo de retorno.   Instrucciones que representamos cada una como comandos.   Detalle del bloque principal (método Main): Aquí se recoge la información de  las  instrucciones que se ejecutan en el bloque principal, o método Main. Para  ello  se  crea  un  Objeto  Concurrente  que  reúne  todas  las  instrucciones  y  las  variables  que  se  declaren  en  este  método  (incluidos  los  nuevos  Objetos  Concurrentes que se declaren).   Los  errores  Sintácticos  y  Semánticos  del  programa:  Se  obtienen  los  errores  que  el  parser  de  ABS  encuentra  en  el  código.  Devuelve  la  línea  donde  se  produce el error y un comentario de error.   Librerías:  Al  igual  que  en  Java,  ABS  puede  importar  distintas  librerías.  Sin  embargo, no hemos diseñado esta funcionalidad para nuestra aplicación.  ProsymbABS está diseñado en lenguaje Java y se compone de varias clases en las que  organizamos toda la información que nos devuelve el parser de ABS.   3.1. Organización de ProsymbABS La primera tarea de la aplicación es interpretar la información obtenida del parser por  lo  que,  básicamente,  la  aplicación  se  podría  definir  como  un  intérprete  del  árbol  sintáctico de ABS. Para ello, el código del proyecto se divide en 5 paquetes principales,  uno de ellos correspondiente a la interfaz de ProsymbABS y los demás se dedican a la  organización de la información recogida y a la funcionalidad de la aplicación. La ventaja  de  este  parser  es  que  gracias  a  que  hace  la  compilación  del  código  se  sabe  si  hay  errores en el código ABS, por  lo que no se ejecutará el programa hasta que se hayan  corregido.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       13 3.1.1. Main En  este  paquete  se  encuentran  las  clases  principales  de  la  aplicación.  La  clase  MainClass realiza  la  interpretación del parser ABS, obteniendo  los errores, si hay, del  programa  ABS,  las  diferentes  clases  con  sus  métodos,  los  objetos  y  objetos  concurrentes que  se  van  creando.  Los objetos  concurrentes  se guardan en una  lista  que será la que se ejecute cuando se ejecute la aplicación.      Figura 2.1: Ejemplo código MainClass Los Objetos Concurrentes son las piezas en torno a las que gira la aplicación. Cada uno  de estos objetos guarda  la  información de  la clase a  la que pertenecen y una cola de  los  métodos  que  van  a  ejecutar  en  el  programa  ABS.  Estos  métodos  los  hemos  identificado  como  la  clase  Tarea,  donde  se  guarda  el  método  a  ejecutar  y  sus  parámetros  de  entrada.  El método  a  ejecutar  es  una  clase  de  tipo Metodo  el  cual  guarda la información sobre la clase a la que pertenece, los parámetros de entrada del  método  y  la  cola  de  comandos  de  la  que  se  compone  dicho método.  Las  Tareas  ejecutan  los  comandos  que  contiene  el  método,  los  cuales  pueden  crear  nuevos  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       14 Objetos Concurrentes, crear tareas asíncronas en  los otros objetos concurrentes o en  el mismo que lo invoca.      Figura 2.2: Ejemplo código ObjetoConcurrente Clase guarda  la  información de  las clases declaradas en el programa ABS. Cada clase  define sus propios métodos, por  lo que nuestra estructura de datos guarda en Clase  una  tabla  con  los métodos y  los atributos de  las  clases que el usuario declara en el  programa ABS.  Por  último,  este  paquete  se  compone  de  la  clase  Contexto,  el  cual  es  la  principal  característica del perfilador. Contexto es una estructura de datos que guarda toda  la  información  que  la  clase MainClass  va  interpretando  del  parser  ABS.  Contexto  se  desarrollo  para  guardar  esta  información  de  forma  que  después  del  compilado  del  código ABS fuera relativamente sencilla  la ejecución del programa y  la recolección de  los  datos  del  consumo  de  recursos  de  ABS  por  parte  del  perfilador.  En  esta  clase  guardamos  todas  las  clases  creadas,  todos  los  objetos  concurrentes  creados  y  gran  variedad de variables para controlar el hilo de ejecución definido por  la planificación  que se haya definido antes de la ejecución de la aplicación.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       15   Figura 2.3: Ejemplo código Contexto   Figura 2.4: Diagrama de clases del paquete Main 3.1.2. Interfaz Este paquete  se  compone de  las  clases que  se encargan de diseñar  la  interfaz de  la  aplicación.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       16 Las  clases  LinePainter  y  LinePainterError  son  básicamente  el  mismo  código,  la  diferencia  es  que  el    primero  se  encarga  en  colorear  la  línea  donde  está  el  cursor  apuntando,  y  el  segundo  se  encarga  de  colorear  las  líneas  donde  el  parser  ABS  ha  encontrado errores.  La  clase  Interfaz  tiene  como  atributo  un  objeto  de  tipo  MainClass,  el  cuál  es  el  intérprete que estará compilando el código con cada cambio que se haga en el panel  central, donde aparece el código ABS. El usuario podrá ejecutar el código compilado en  el botón con  la  imagen de play  siempre y cuando  la compilación no haya producido  errores, o ejecutando un método en particular, utilizando el panel de  la derecha, y el  resultado de la información del consumo de recursos se mostrará en el panel inferior.    Figura 2.5: Ejemplo código Interfaz Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       17   Figura 2.6: Diagrama de clases del paquete Interfaz 3.1.3. Comandos Cada una de  las  instrucciones que se ejecutan en el programa ABS y que el parser de  ABS nos devuelve, se clasifica como comando dependiendo del tipo de comando que  sea (asignación, llamada asíncrona, if, while, etc).  El paquete se compone de una clase abstracta Comando con un método ejecutar que  definirán  todas  las  clases  que  hereden  de  la  misma.  De  entre  todos  los  tipos  de  comandos  que  se  han  diseñado  para  el  proyecto  (Asignación,  ComandoAsyncCall,  ComandoAwait,  ComandoIf,  ComandoSyncCall,  ComandoWhile,  Return)  cabe  destacar los siguientes:   ComandoAsyncCall:  se encarga de hacer  las  llamadas asíncronas que  realizan  los objetos concurrentes. Para ello crea una nueva tarea en la cola de tareas del  objeto concurrente que realice la llamada.   ComandoAwait:  realiza  las mismas  funciones  que  la  primitiva  await  de ABS.  Consta de una expresión booleana que para la ejecución del objeto concurrente  que lance este comando hasta que la expresión se evalúe a cierto.   ComandoSyncCall:  se encarga de  realizar una  llamada  síncrona a un método,  pero no realiza ninguna espera ni lo añade como tarea al objeto concurrente.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       18   Figura 2.7: Ejemplo de código ComandoAwait   Figura 2.8: Diagrama de clases del paquete Comandos 3.1.4. TipoValues Todos los tipos que la aplicación va a evaluar se encuentran en este paquete. La clase  abstracta TipoValue es el padre de  las demás clases que aparecen en el paquete. De  entre  todos  los  tipos especificados  (Booleano, Cadena, Concurrente, Entero, Futuro,  Objeto, Operador) cabe destacar los siguientes:  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       19  Booleano,  Cadena,  Entero:  son  los  tipos más  comunes  que  aparecen  en  los  programas  ABS.  Heredan  de  TipoValue  el  método  ejecutar  donde,  dependiendo del operador que se  le pase al método como parámetro, realiza  una función u otra, como por ejemplo, la suma o la resta, la concatenación de  cadenas, las operaciones or y and.   Futuro: este tipo se encarga de tratar los tipos futuros de ABS. Constan de dos  atributos, el valor y un booleano de acabado, de  forma que  cuando  valor  se  rellene, el booleano pasará a  ser cierto por  lo que  se podrá obtener  su valor  con la instrucción get.   Operador:  se  encarga  de  guardar  el  operador  de  las  operaciones  unarias  y  binarias que se ejecutan en el código ABS.        Figura 2.9: Ejemplo código Booleano Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       20 Figura 2.10: Ejemplo código Futuro   Figura 2.11: Diagrama de clases del paquete TipoValue Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       21 3.1.5. Expresiones El último paquete de  la  implementación corresponde al de Expresiones. Al  igual que  en Comandos y TipoValue existe una clase padre Expr de  la que heredan el resto de  clases. Las expresiones  implementan el método eval en vez del ejecutar   de  los otros  paquetes ya que se evalúa la expresión y se devuelve un objeto de tipo TipoValue tras  la  evaluación.  De  todas  ellas  (AsyncCall,  BinOp,  ConstBool,  ConstInt,  ConstObjConcurrente,  ConstObjeto,  ConstString,  ExprAwait,  ExprGet,  SyncCall,  UniOp, Var) cabe destacar los siguientes:   AsyncCall: se encarga de recoger la información de una llamada asíncrona. Tras  evaluarse la expresión asíncrona se devolverá un objeto de tipo Futuro por ser  una llamada asíncrona.   BinOp:  se  encarga  de  evaluar  las  expresiones  de  operaciones  binarias  para  devolver una expresión que se asignará a una variable.   ConstBool,  ConstInt,  ConstString:  evalúan  las  expresiones  de  tipo  Booleano,  Entero y Cadena.   ConstObjConcurrente:  evalúa  la  expresión  “new  cog”  para  asignar  a  una  variable un objeto de tipo ObjetoConcurrente.   ExprGet:  es  el  encargado  de  determinar  si  un  objeto  de  tipo  Futuro  ha  conseguido ya su valor o no. Si no tiene valor el objeto, ExprGet mandará una  petición de parada al objeto  llamante para que ceda el control de flujo a otro  objeto concurrente.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       22   Figura 2.12: Ejemplo código AsyncCall Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       23   Figura 2.13: Ejemplo código ConstObjConcurrente     Figura 2.14: Ejemplo código ConstInt Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       24   Figura 2.15: Ejemplo código ExprGet   Figura 2.16: Diagrama de clases del paquete Expresiones Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       25   4. Resultados obtenidos   Para  probar  el  funcionamiento  de  ProsymbABS  realizamos  una  prueba  para  el  algoritmo  de  Fibonacci  en  el  que  realizamos  llamadas  asíncronas  por  cada  llamada  recursiva  que  realiza  el  programa. De  este modo  repartimos  las  tareas  entre  varios  procesadores.   Cargando el programa ABS en la interfaz de ProsymbABS podemos ver lo siguiente:          Figura 3.1: Programa de fibonacci ABS Como  ABS  no  tiene  ningún  perfilador  desarrollado  por  el  momento,  probamos  la  ejecución del programa en ABS puro que nos proporciona el plugin de ABS Tools. Este  plugin  cuenta  con  la  posibilidad  de  ejecutar  el  código  dibujando  un  diagrama  de  secuencias, con lo que se puede ver cómo ha funcionado la ejecución.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       26                                                     F ig u ra 3 .2 : D ia g ra m a se cu en ci al d e e je cu ci ó n A B S Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       27 El  programa  ABS  realiza  una  ejecución  del  algoritmo  de  Fibonacci  para  el  número  cuatro. Debido a  la  recurrencia y a que, como hemos explicado antes, cada  llamada  recursiva  corresponde  a una  llamada  asíncrona,  se  crean un  total de nueve objetos  concurrentes de tipo AImpl, hecho que se puede ver en la figura anterior.  Una vez cargado nuestro código en el panel central, automáticamente ProsymbABS se  encargará de  llamar al parser de ABS para que compile el código y, si no hay errores,  devolverá  el  árbol  sintáctico  resultante.  Una  vez  compilado  el  código  se  realiza  el  parseado  del  árbol  sintáctico  para  guardar  toda  la  información  en  la  variable  de  Contexto de la aplicación como las diferentes clases definidas, la lista de comandos de  cada método, preparar la lista de ejecución de los objetos concurrentes (en este caso  al  principio  sólo  contamos  con  el objeto  concurrente  “Main”). Con  ello  ya  tenemos  todo  listo para  iniciar  la ejecución del programa y  realizar el análisis de consumo de  recursos sobre el mismo.  La  ejecución  del  código  se  puede  realizar  de  dos maneras.  La  primera  consiste  en  realizar  la  ejecución  completa  del  programa,  es  decir,  partiremos  desde  el  bloque  principal del programa ABS y obtendremos la siguiente salida por consola:    Figura 3.3: Resultado ejecución total en ProsymbABS Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       28   ProsymbABS muestra  la  información simbólica recogida de  la ejecución del programa  ABS. Debido a que ejecutamos el programa ABS desde el método principal, creamos  una  clase  “Main”  donde  empezará  a  ejecutarse  el  código  del  programa ABS. Desde  esta  clase  se  realiza  una  llamada  asíncrona  al  algoritmo  de  fibonacci mediante  la  creación de un cog nuevo “a” previamente. Al tratarse de una  llamada asíncrona, se  crea una variable futura para reservar el valor del resultado que devolverá la llamada a  fibonacci.  Dentro  de  su  cog  el  objeto  “a”  ejecutará  el  código  del  algoritmo  de  fibonacci. Como el parámetro que recibe es mayor que uno (cuatro), toma el camino  por  la  parte  recursiva  del  algoritmo  y  realiza  dos  llamadas  asíncronas  para  que  continúen la ejecución.   Por lo tanto se seguirán creando nuevos cogs hasta que el valor del parámetro sea 0 o  1, por  lo que habremos  llegado al caso base del algoritmo y  la  llamada retornará un  valor  de  resultado.  En  el  algoritmo  de  fibonacci  crea  ocho  cogs  nuevos  para  esta  ejecución, más  la  llamada del bloque principal  se  crean un  total de nueve  cogs que  coincide  con  el  número  de  cogs  creados  en  la  ejecución  realizada  anteriormente  únicamente del código ABS.  Cada cog que se crea se le asigna un identificador para diferenciar los distintos cogs, ya  que  se puede dar el  caso de que  se  creen  cogs  con el mismo nombre. Mostramos,  además, las diferentes llamadas a métodos provenientes de los cogs creados. De cada  llamada  a  método  se  muestra  información  referente  al  número  de  instrucciones  ejecutadas en cada método y el número de llamadas asíncronas que se realizan.  Aparte  de  mostrar  los  datos  correspondientes  a  cada  método  ejecutado  en  el  programa, se muestra, además, la cuenta total del número de instrucciones que se han  ejecutado  en  el  programa  ABS  (asignaciones,  creación  de  objetos,  operaciones  binarias,  llamadas  asíncronas,  operaciones  de  retorno).  En  total,  como  se  puede  observar  en  la  imagen  anterior,  se  ejecutan  74  instrucciones  (comandos)  en  la  aplicación.  Por  último  calculamos  el  tiempo  que  ha  tardado  ProsymbABS  en  realizar  esta  ejecución,  para  ello marcamos  con  una  variable  el  punto  de  inicio  y  el  punto  final,  dentro del código de nuestra aplicación, con la que se calculará el tiempo transcurrido  entre  ambos  puntos.  Comenzamos  a  contar  justo  antes  de  lanzar  la  ejecución  del  programa ABS  y  paramos  de  contar  cuando  termina  de  ejecutarse  el  último  objeto  concurrente que queda en la lista de objetos concurrentes.  El  segundo  tipo de ejecución  con el que  se puede  trabajar en ProsymbABS es el de  ejecutar  únicamente  el método  deseado,  para  ello  se  selecciona  el método  en  el  diagrama de  la  izquierda. Con ello  se actualiza el panel derecho  con  los parámetros  que tiene el método para definirles su valor inicial:  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       29   Figura 3.4: Ejecución parcial en ProsymbABS   Una  vez  rellenados  los  campos,  al  hacer  click  en  el  botón  Ejecutar  obtendremos  el  siguiente resultado por pantalla:  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       30   Figura 3.5: Resultado ejecución parcial en ProsymbABS Se observan unos pequeños cambios con respecto a la ejecución anterior. En este caso  la ejecución no comienza desde el bloque principal por lo que no hay creado un objeto  concurrente  “Main”.  En  vez  de  ello,  se  crea  directamente  como  primer  objeto  concurrente el de la clase que implementa el método elegido.  Por lo tanto se crean un total de ocho cogs que corresponde a la ejecución del método  de fibonacci, y no nueve como ocurre en  la ejecución anterior debido a que no se ha  creado ese objeto concurrente “Main”.  Por la misma razón, el tiempo de ejecución y el número de instrucciones ejecutadas ha  bajado  levemente con respecto a  la ejecución anterior. El bloque principal ejecuta un  total de siete instrucciones las cuales son:    Creación del objeto.   Asignación.   Llamada asíncrona.   Asignación.   Método get (variable de terminado evaluada a falso).   Método get (variable de terminado evaluada a cierto).   Asignación.  Se ejecutan, por lo tanto 67 instrucciones frente a las 74 de la ejecución anterior.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       31   5. Manual del usuario A  continuación  presentamos  el manual  de  la  aplicación.  Como  requisito  previo  a  la  ejecución es necesario tener  instalado  la última versión de Java en el ordenador para  que  la  aplicación  funcione  correctamente  con  todos  los  plugins  con  los  que  se  ha  implementado.  5.1. Inicio Tras  iniciar  la  aplicación  nos  aparecerá  la  siguiente  pantalla,  correspondiente  a  la  interfaz de la aplicación:    Figura 4.1: Interfaz de la aplicación La  interfaz consta de varios paneles con distintas  funcionalidades. El panel  izquierdo  mostrará un diagrama de clases del programa ABS que se ha compilado y las distintas  planificaciones que se  le asignan a cada clase. El panel central contiene el código ABS  del cual se realizará  la compilación y posterior ejecución del mismo. El panel derecho  nos permite ejecutar un método concreto pasándole  los valores a sus parámetros de  entrada. Por último, el panel  inferior corresponde a  la consola de  la aplicación donde  se muestra  los  resultados  obtenidos  por  el  perfilador  (métrica,  número  de  objetos  creados, número de llamadas asíncronas, tiempo de ejecución).  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       32 5.2. Edición Podemos empezar a editar nuestro código directamente en el área de texto del panel  central,  o  bien,  podemos  abrir  un  archivo  en  formato  ABS.  Para  elloo  le  damos  a  Archivo (barra superior) y luego a Abrir.    Figura 4.2: Pestaña Archivo Una  vez  le  hayamos  dado  a  abrir  aparecerá  un  explorador  de  archivos  de  nuestro  ordenador desde donde podemos seleccionar uno para abrir.    Figura 4.3: Selección de archivo ABS Después  de abrir tendremos el código ABS en el panel central, desde donde podemos  editar o ejecutar la aplicación.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       33   Figura 4.4: Interfaz con código compilado 5.3. Errores El  código  del  panel  central  se  podrá  ir  editando  y,  al  igual  que  Java,  el  compilador  seguirá funcionando con cada cambio que registre el código. Podremos ver los errores  que  aparecerán marcados  con  una  línea  roja  facilitándonos  su  depuración. Una  vez  corregido el error la línea roja desaparecerá.  Figura 4.5: Error en el código ABS Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       34 5.4. Planificación En  la  pestaña  planificación  (en  el  panel  izquierdo),    es  donde  podremos  elegir  las  planificaciones que queremos para nuestras clases:   Azar: se selecciona una Tarea de la lista de Tareas   FIFO: se seleccionan las Tareas por orden de llegada   LIFO: se seleccionan primero la tarea que se ha añadido recientemente   Round  Robin:  ejecuta  n  Tareas  elegidas  al  azar  y  pasa  al  siguiente  Objeto  Concurente.   Prioridades: Para este caso tendremos que añadir prioridades a los métodos de  las clases, para así saber que tarea será la siguiente.  Estas planificaciones serán las encargadas de elegir el orden de ejecución de las tareas  en los distintos Objetos Concurrentes.    Figura 4.6: Panel de planificaciones Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       35 5.5. Ejecución Una vez que nuestro programa está compilado correctamente,  libre de errores y tras  haber elegido una planificación para cada clase podremos ejecutar nuestro código de  las siguientes maneras:    Figura 4.7: Interfaz de la aplicación con código 5.5.1. Ejecución total del programa ABS Esta opción es  la encargada de ejecutar nuestro código ABS de manera convencional,  esto quiero decir que empecerá  la ejecución desde el bloque principal del programa  ABS, creando un proceso principal. Para realizar esta ejecución tendremos que darle al  símbolo de play que aparece en la barra superior.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       36   Figura 4.8: Botón play   5.5.2. Ejecución parcial del código ABS Otra  posibilidad  para  ejecutar  ProsymbABS  es  seleccionando  un  solo  método  pasándole los valores de los parámetros de entrada del método seleccionado.  Desde el panel izquierdo podremos explorar las clases y los métodos que tenemos en  nuestro código. Este panel se actualizará a la vez que vamos editamos nuestro código.  Desde este panel podemos seleccionar el método que queremos ejecutar.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       37   Figura 4.9: Panel de clases Una  vez  seleccionado  el método  se  refrescará  el  panel  que  tenemos  a  la  derecha,  desde donde podemos inicializar los parámetros de entrada. Si no recordamos el tipo  de los atributo, podemos saberlo poniendo el cursor encima del nombre del atributo,  donde  aparecerá  un  tooltip  con  el  tipo  del  parámetro  seleccionado.  Una  vez  inicializados los parámetros, solo tenemos que pulsar el botón Ejecutar.            Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       38   Figura 4.10: Panel de método 5.6. Resultados Una vez ejecutado el  código  (tanto  total  como parcialmente),  se podrá observar  los  resultados que devuelve nuestro perfilador sobre la ejecución del programa ABS en el  panel inferior de la interfaz, correspondiente a la consola.                        Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       39       Figura 4.11: Consola de la interfaz               Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       40   6. Conclusiones   Hemos  conseguido  ejecutar  el  ABS  de  forma  secuencial,  de modo  que  siempre  se  ejecuta un  solo Objeto Concurrente o proceso  a  la  vez,  lo que nos hecho más  fácil  contabilizar  los  datos  del  perfilador,  ya  que  no  tenemos  que  tener  en  cuenta  la  concurrencia.  Cuando un objeto  concurrente ejecuta  todas  las  tareas que  tiene pendiente, pasa a  ejecutar  otro Objeto  Concurrente,  la  selección  del  siguiente Objeto  Concurrente  en  nuestro caso es al azar. El objeto concurrente que finaliza sus tareas pasa a la lista de  Objetos Concurrente  inactivos, a  la espera de que otro objeto  concurrente  le añada  una nueva tarea con una llamada asíncrona.  Las  tareas  que  tiene  un  objeto  concurrente  se  ejecutan  según  la  planificación  que  hayamos elegido, la cual puede ser una de las siguientes:   Azar: se selecciona una Tarea de la lista de Tareas   FIFO: se seleccionan las Tareas por orden de llegada   LIFO: se seleccionan primero la tarea que se ha añadido recientemente   Round  Robin:  ejecuta  n  Tareas  elegidas  al  azar  y  pasa  al  siguiente  Objeto  Concurente.   Prioridades: Para este caso tendremos que añadir prioridades a los métodos de  las clases, para así saber qué tarea será la siguiente.  Aunque esta planificación no es parte del lenguaje ABS, desarrollamos esta parte como  una  ayuda  para  la  depuración  de  programas  ABS  ya  que  vimos  como  prioritario  la  comparación  de  la  ejecución  de  un mismo  código  con  distintas  planificaciones  para  entender de mejor manera su comportamiento.  El  método  get  en  ABS  puro  hace  una  espera  activa  en  el  Proceso  del  Objeto  Concurrente mientras  la variable futura no tenga su valor, pero en nuestra aplicación  no  podemos  hacer  una  espera  ya  que  sólo  utilizamos  un  proceso  (las  instrucciones  get). Por eso nuestro intérprete puede contabilizar más de una vez esta instrucción ya  que,  al  volver  a  ejecutar  el  Objeto  Concurrente  donde  está  declarado,  tendrá  que  volver a comprobar si el método get ya devuelve el valor de la variable futura.  El método await, al igual que el método get, puede ser contabilizado más de una vez,  aunque  en  este  caso  la  espera  solo  le  corresponde  a  la  Tarea,  ya  que  el  objeto  Concurrente pasa a ejecutar otra tarea.  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       41 Cuando ejecutamos un  solo método  se  crea un objeto  concurrente principal que  lo  nombramos de la siguiente manera: ‘nombre de la clase’  ‐  ‘nombre del método’ (p.e.  AImpl ‐ fibo) y se le pasará los parámetros que hayamos especificado.   En ejecuciones muy largas y sobre todo donde se crean muchos Objetos Concurrentes,  hemos pensado que no es necesario escribir todos  los datos del número de  llamadas  asíncronas  de  cada  uno,  ya  que  será  imposible  su  visualización  en  el  panel  de  la  Consola, por lo que limitamos el número de objetos concurrentes que se visualizarán.  No obstante, estos objetos seguirán contando para los datos generales de la ejecución  (número  de  instrucciones,  número  de  objetos  concurrentes,  número  de  llamadas  asíncronas).    6.1. Trabajos futuros   Mucha parte de nuestro código está comentada de manera que pueda ser más sencillo  su entendimiento. También, como se indica en la sección de implementación, tenemos  nuestras  clases  divididas  en  paquetes  para  ayudar  a  facilitar  la  estructuración  del  proyecto y que sea fácil el acceso a las distintas clases.  Creemos que nuestro  intérprete de ABS podría tener un plugin para eclipse, para no  tener que estar ejecutando cada vez  la aplicación, pero manteniendo muchas de  las  características que tiene actualmente: errores que se van indicando mientras editas el  código, ejecución de un solo método. También se podría añadir coloreado especial de  palabras claves de ABS para mejorar la visualización del código  Otra  cosa pendiente es  la  implementación de  la parte  funcional de ABS. Para dicha  implementación se podría empezar diseñando las clases que se necesitarán, ya que no  debería  de  interferir  con  el  diseño  de  las  clases  que  usamos  actualmente. Ademas,  habría que  añadir métodos  en  clase MainClass para que  reciban  la  información del  parser  de  ABS  y  la  interpreten  a  estas  nuevas  clases.  Al  igual  que  con  la  parte  secuencial, se puede calcular el consumo de recursos de la parte funcional de ABS.  Otra  opción  que  se  podría  añadir  sería  opción  gráfica  donde  se  podría  explicar  con  gráficos  la  recopilación  de  datos  que  realiza  el  perfilador,  para  facilitar  la  interpretación de los mismos.  Como  la  ejecución  de  los  Objetos  concurrentes  se  hace  de manera  secuencial,  se  podría  añadir  que  cada  Objeto  Concurrente  sea  un  thread  distinto,  con  esto  ahorraríamos bastante tiempo en la ejecución, sobre todo cuando hay muchos objetos  concurrentes creados. La concurrencia entre los objetos implicaría que la recopilación  de  la  información  como  numero  de  instrucciones  totales,  número  de  objetos  concurrentes creados o número de llamadas asíncronas tenga que hacerse de manera  atómica para proteger su acceso mientras estamos contabilizándolas.    Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       42   7. Referencias y bibliografía   [1] JCoBox, disponible en https://softech.informatik.uni‐ kl.de/Homepage/JCoBox  [2] E. Broch Johnsen, O. Owe, I. Chieh Yu. Creol: A type‐safe object‐ oriented model for distributed concurrent systems,  http://www.sciencedirect.com/science/article/pii/S0304397506004804  [3] JProfiler, disponible en https://www.ej‐ technologies.com/products/jprofiler/features.html  [4] JBoss, disponible en http://www.jboss.org/technology/  [5] Página de herramientas ABS del proyecto HATS, http://tools.hats‐ project.eu/  [6] Manual de la sintaxis de ABS, http://tools.hats‐ project.eu/download/absrefmanual.pdf  Profiling:   http://exa.unne.edu.ar/depar/areas/informatica/SistemasOperativ os/Analisis%20Comparativo%20del%20Rendimiento.pdf   http://es.wikipedia.org/wiki/An%C3%A1lisis_de_rendimiento_de_s oftware   http://es.wikipedia.org/wiki/An%C3%A1lisis_din%C3%A1mico_de_s oftware   http://es.wikipedia.org/wiki/An%C3%A1lisis_est%C3%A1tico_de_so ftware  Concurrencia:   http://cala.unex.es/cala/epistemowikia/index.php?title=Verificaci% C3%B3n_de_Programas_Concurrentes_(versi%C3%B3n_1)/Introduc i%C3%B3n_a_la_Concurrencia  Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       43  http://www.teknoplof.com/2013/10/10/la‐programacion‐ concurrente‐es‐el‐futuro‐inmediato‐o‐deberia‐serlo/  Lenguaje ABS:   http://tools.hats‐project.eu/   http://einarj.at.ifi.uio.no/Papers/johnsen10fmco.pdf                                            Sistemas informáticos 2013‐2014                                            Nícolas Paolo Bueno Cavero Perfilador simbólico para objetos concurrentes                                      Javier Gómez Edo       44   8. Apéndice   En este apartado hemos querido adjuntar un artículo que explica la semántica de ABS y  que nos ha sido bastante útil para entender el funcionamiento de la ejecución de ABS  y, por tanto, ha facilitado la realización del proyecto.  8 ELVIRA ALBERT et al.2.3 Operational Semanti sAn obje t is of the form ob(o, C, h, 〈tv , s〉,Q), where o is the obje t identi�er, Cis its lass name, h is its lo al heap, 〈tv , s〉 is the exe ution ontext of the urrenttask, being tv the table of lo al variables and s the sequen e of instru tions tobe exe uted by the urrent task, and Q is the set of pending tasks, being ea hof them an exe ution ontext. In the following we use ǫ to denote either anempty sequen e of instru tions or an empty exe ution ontext. A heap h maps�eld names (de lared in C) to V = Z∪{null}∪Objects, where Objects denotesthe set of obje t identi�ers. A table of variables tv maps lo al variables to V. It ontains the spe ial entry r to asso iate the return variable of a method to the orresponding future variable. Future events have the form fut(fn, v) where v ∈ V ∪ ⊥. The symbol ⊥ indi ates that fn does not have a value yet. Forsimpli ity, we assume that all methods return a value. An exe ution state (or on�guration S) has the form {|a1, . . . , an|}, where ai an be either an obje t ora future event. Exe ution states are in fa t represented as multisets of obje tsand future events. In the following, we use the notation {|a|S|} to stand for thenew multiset {|a|} ∪ S.The operational semanti s is given in a rewriting-based style, where, at ea hstep, a subset of the state is rewritten a ording to the rules in Fig. 3. Letus intuitively explain the semanti s. Fun tion evale evaluates an expression ewith respe t to a heap h and a table of variables in the standard way. Note thatthe heap is required to evaluate expressions of the form this .f , what returns(rule 1) h(f) as result. Fun tion evalguard(guard , tv) in rule 4 returns truei� guard ≡ true or guard ≡ x1 opR x2 and tv(x1) opR tv(x2). Finally theevaluations of onditions in await instru tions is done by fun tion eval g. Inparti ular, for the ase of future variables x? in rules 9 and 10, this fun tionbehaves as follows: evalg(x?, tv , h,S) = true i� tv(x) = fn and fut(fn, v) ∈ S, v 6= ⊥. The notation tv [x 7→ v] (resp. h[f 7→ v]) stands for storing v in thelo al variable x (resp. �eld f).Rules 1 and 2 operate in the expe ted way. In rule 3, it an be observedthat the table of variables tv maps x to o1. Fun tion newRef () is in harge ofgenerating fresh obje t identi�ers.In rule 4, a all to a blo k is resolved by �nding a mat hing rule andadding its body to the sequen e of instru tions to be exe uted. The notation r ≡ p(this ′, x̄′, y′) ← b1, . . . , bn ≪ P stands for a fresh renaming of a rule in P . newenv(r) reates a new mapping for variables in r, where ea h variableis initialized to either 0 or null. When the exe ution of a blo k �nishes (rule6) the state is prepared to later apply rule 11 to sele t a new task from thequeue.Rule 5 deals with asyn hronous method invo ations. When an obje t o1 alls to a method p(x̄), the information required to exe ute the all is storedin the queue of the obje t represented by o1. Observe that tv2 has the spe ialentry r to store the relation between the future variable fn where storing theresult and the output parameter y′. This future variable is initially unde�ned,thus fut(fn,⊥) is added to the state. When the method returns a value (rule Obje t-Sensitive Cost Analysis for Con urrent Obje ts⋆ 9(1) v = evale(e, h, tv), x ∈ dom(tv) {|ob(o, C, h, 〈tv , x := e · s〉,Q)|S|}; {|ob(o, C, h, 〈tv [x 7→ v], s〉,Q)|S|}(2) v = tv(y) {|ob(o, C, h, 〈tv , this.f := y · s〉,Q)|S|}; {|ob(o, C, h[f 7→ v], 〈tv , s〉,Q)|S|}(3) o1 = newRef (), h1 and tv1 are empty mappings {|ob(o, C, h, 〈tv , x := new D · s〉,Q)|S|}; {|ob(o,C, h, 〈tv [x 7→ o1], s〉,Q), ob(o1, D, h1, 〈tv1, ǫ〉, ∅)|S|}(4) r ≡ p(o′, x̄′, ȳ′)← guard ′, b′1 , . . . , b ′ n ≪ P ,newenv(r) = tv1 tv1(o′) = tv(o), tv1(x̄′) = tv(x̄), tv1(ȳ′) = tv(ȳ), evalguard (guard , tv) = true {|ob(o, C, h, 〈tv , call(b, p(o, x̄, ȳ)) · s〉,Q)|S|}; {|ob(o, C, h, 〈tv ∪ tv1, b ′ 1 · · · b′n · s〉,Q)|S|}(5) r ≡ p(this′, x̄′, y′)← b′ 1 , . . . , b′n ≪ P, tv(o1) = o2, fn is a fresh future name newenv(r) = tv1, tv2 = tv1[this ′ 7→ o2, x̄ ′ 7→ tv(x̄), r 7→ (y′, fn)] {|ob(o, C, h, 〈tv , call(m, p(o1, x̄, y)) · s〉,Q), ob(o2,D, h1, 〈tv3, s1〉,Q′)|S|}; {|ob(o, C, h, 〈tv [y 7→ fn], s〉,Q), ob(o2, D, h1, 〈tv3, s1〉, {〈tv2, b ′ 1 · · · b′n〉} ∪ Q ′), fut(fn,⊥)|S|}(6) r 6∈ dom(tv) {|ob(o, C, h, 〈tv , ǫ〉,Q)|S|}; {|ob(o,C, h, ǫ,Q)|S|}(7) r ∈ dom(tv), (y, fn) = tv(r), v = tv(y) {|ob(o, C, h, 〈tv , ǫ〉,Q), fut(fn,⊥)|S|}; {|ob(o, C, h, ǫ,Q), fut(fn, v)|S|}(8) fn = tv(y), v 6= ⊥ {|ob(o, C, h, 〈tv , x := y.get · s〉,Q), fut(fn, v)|S|};{|ob(o, C, h, 〈tv [x 7→ v], s〉,Q), fut(fn, v)|S|}(9) evalg(g, h, tv ,S) = true {|ob(o,C, h, 〈tv , await g · s〉,Q)|S|}; {|ob(o, C, h, 〈tv , s〉,Q)|S|}(10) evalg(g, h, tv ,S) = false {|ob(o, C, h, 〈tv , await g · s〉, q)|S|}; {|ob(o, C, h, ǫ, {〈tv , await g · s〉} ∪ Q)|S|}(11) s ∈ Q {|ob(o, C, h, ǫ,Q)|S|}; {|ob(o, C, h, s,Q− {s})|S|}Fig. 3 Operational Semanti s7), the entry r is used to look for the orresponding future variable in order toupdate the ⊥ value with the one whi h is returned. Note that rule 9 he ks ifa future variable is ready. In su h ase the omputation pro eeds. Otherwise,in rule 10, the await task in introdu ed is the orresponding queue, and thepro essor is released.The instru tion get blo ks the exe ution until the future variable has avalue in 8. If the evaluation of the guard in an await instru tion su eeds,the exe ution ontinues in rule 9. Otherwise, in rule 10, the await task inintrodu ed is the orresponding queue, and the pro essor is released. In rule 11another task is dequeued (be ause the urrent one terminated or released thepro essor). Note that this rule is appli able thanks to rules 6 (resp. 7) whi h orresponds to the omplete exe ution of a blo k (resp. a method). 10 ELVIRA ALBERT et al.We assume that exe utions start from a main method. Thus, the initial on�guration is of the form {|ob(main,⊥,⊥, 〈tv , s〉, ∅)|}, where lo al variablesin tv are initialized to their default values. The exe ution then pro eeds non-deterministi ally by applying the exe ution steps in Fig. 3. The exe ution�nishes in a �nal on�guration in whi h all events are either future eventsor obje ts of the forms ob(o, C, h, ǫ, ∅) or ob(o, C, h, 〈tv , ǫ〉, ∅). Exe utions anbe regarded as tra es of the form S0 ; S1 ; · · · ; Sn where Sn is a �nal on�guration.Example 3 Consider the main method of the running example (Figure 1).After exe uting the onstru tors we rea h a on�guration with three obje ts: {|ob(main,⊥,⊥, 〈tvmain, bc〉, ∅), ob(o1,FileIS , ho1 , ǫ, ), ob(o2 ,FileIS , ho2 , ǫ, )|}where bc orresponds to the sequen e of instru tions from (*) on. After pro- essing both asyn hronous alls (rule 5) onse utively, the new state takes theform: {| ob(o1,FileIS , ho1 , ǫ, {〈tvo1 , bodyo1 〉}), fut(fn1 ,⊥), ob(o2,FileIS , ho2 , ǫ, {〈tvo2 , bodyo2 〉}), fut(fn2 ,⊥), ob(main,⊥,⊥, 〈tvmain[f1 7→ fn1, f2 7→ fn2], bc ′〉, ∅) |}where bodyo1 (resp. bodyo2 ) is the renamed body of method readOnce (resp. readBlock). Furthermore, tvo1 (resp. tvo2 ) stores the assignment tvo1(r) = (f1, fn1) (resp. tvo2(r) = (f2, fn2)). When the event 〈tvo1 , bodyo1 〉 is extra tedfrom the queue of o1 (rule 11), its omplete pro essing will repla e fut(fn1,⊥)by fut(fn1, v) (rule 7), where v is the value returned by the method readOnce.Note then that rule 9 an be used to pro ess the instru tion await f1? of theobje t main. At this point the new state will take this form: {| ob(o1,FileIS , ho1 , ǫ, ∅), fut(fn1 , v), ob(o2,FileIS , ho2 , ǫ, {〈tvo2 , bodyo2 〉}), fut(fn2 ,⊥), ob(main,⊥,⊥, 〈tvmain[f1 7→ fn1, f2 7→ fn2], bc ′′〉, ∅) |}3 Cost and Cost Models for Con urrent ProgramsWe now de�ne the notion of ost we aim at approximating by stati analysis.An exe ution step is annotated as S ; b o S ′, whi h denotes that we move froma state S to a state S ′ by exe uting instru tion b in obje t o. Note that froma given state there may be several possible exe ution steps that an be takensin e we have no assumptions on task s heduling. In order to quantify the ostof an exe ution step, we use a generi ost model M : Ins 7→ R whi h mapsinstru tions built using the grammar in Se tion 2.2 to real numbers. The ostof an exe ution step is de�ned asM(S ; b o S ′) =M(b).In the exe ution of sequential programs, the umulative ost of a tra e isobtained by applying a given ost model to ea h step of the tra e. In our set-ting, this has to be extended be ause, rather than onsidering a single ma hinein whi h all steps are performed, we have a potentially distributed setting, with ProsymbABS. Memoria.pdf ProsymbABS.Memo-apéndice.pdf ProsymbABS.Memo-apéndice.pdf 8 ELVIRA ALBERT et al.2.3 Operational Semanti sAn obje t is of the form ob(o, C, h, 〈tv , s〉,Q), where o is the obje t identi�er, Cis its lass name, h is its lo al heap, 〈tv , s〉 is the exe ution ontext of the urrenttask, being tv the table of lo al variables and s the sequen e of instru tions tobe exe uted by the urrent task, and Q is the set of pending tasks, being ea hof them an exe ution ontext. In the following we use ǫ to denote either anempty sequen e of instru tions or an empty exe ution ontext. A heap h maps�eld names (de lared in C) to V = Z∪{null}∪Objects, where Objects denotesthe set of obje t identi�ers. A table of variables tv maps lo al variables to V. It ontains the spe ial entry r to asso iate the return variable of a method to the orresponding future variable. Future events have the form fut(fn, v) where v ∈ V ∪ ⊥. The symbol ⊥ indi ates that fn does not have a value yet. Forsimpli ity, we assume that all methods return a value. An exe ution state (or on�guration S) has the form {|a1, . . . , an|}, where ai an be either an obje t ora future event. Exe ution states are in fa t represented as multisets of obje tsand future events. In the following, we use the notation {|a|S|} to stand for thenew multiset {|a|} ∪ S.The operational semanti s is given in a rewriting-based style, where, at ea hstep, a subset of the state is rewritten a ording to the rules in Fig. 3. Letus intuitively explain the semanti s. Fun tion evale evaluates an expression ewith respe t to a heap h and a table of variables in the standard way. Note thatthe heap is required to evaluate expressions of the form this .f , what returns(rule 1) h(f) as result. Fun tion evalguard(guard , tv) in rule 4 returns truei� guard ≡ true or guard ≡ x1 opR x2 and tv(x1) opR tv(x2). Finally theevaluations of onditions in await instru tions is done by fun tion eval g. Inparti ular, for the ase of future variables x? in rules 9 and 10, this fun tionbehaves as follows: evalg(x?, tv , h,S) = true i� tv(x) = fn and fut(fn, v) ∈ S, v 6= ⊥. The notation tv [x 7→ v] (resp. h[f 7→ v]) stands for storing v in thelo al variable x (resp. �eld f).Rules 1 and 2 operate in the expe ted way. In rule 3, it an be observedthat the table of variables tv maps x to o1. Fun tion newRef () is in harge ofgenerating fresh obje t identi�ers.In rule 4, a all to a blo k is resolved by �nding a mat hing rule andadding its body to the sequen e of instru tions to be exe uted. The notation r ≡ p(this ′, x̄′, y′) ← b1, . . . , bn ≪ P stands for a fresh renaming of a rule in P . newenv(r) reates a new mapping for variables in r, where ea h variableis initialized to either 0 or null. When the exe ution of a blo k �nishes (rule6) the state is prepared to later apply rule 11 to sele t a new task from thequeue.Rule 5 deals with asyn hronous method invo ations. When an obje t o1 alls to a method p(x̄), the information required to exe ute the all is storedin the queue of the obje t represented by o1. Observe that tv2 has the spe ialentry r to store the relation between the future variable fn where storing theresult and the output parameter y′. This future variable is initially unde�ned,thus fut(fn,⊥) is added to the state. When the method returns a value (rule Obje t-Sensitive Cost Analysis for Con urrent Obje ts⋆ 9(1) v = evale(e, h, tv), x ∈ dom(tv) {|ob(o, C, h, 〈tv , x := e · s〉,Q)|S|}; {|ob(o, C, h, 〈tv [x 7→ v], s〉,Q)|S|}(2) v = tv(y) {|ob(o, C, h, 〈tv , this.f := y · s〉,Q)|S|}; {|ob(o, C, h[f 7→ v], 〈tv , s〉,Q)|S|}(3) o1 = newRef (), h1 and tv1 are empty mappings {|ob(o, C, h, 〈tv , x := new D · s〉,Q)|S|}; {|ob(o,C, h, 〈tv [x 7→ o1], s〉,Q), ob(o1, D, h1, 〈tv1, ǫ〉, ∅)|S|}(4) r ≡ p(o′, x̄′, ȳ′)← guard ′, b′1 , . . . , b ′ n ≪ P ,newenv(r) = tv1 tv1(o′) = tv(o), tv1(x̄′) = tv(x̄), tv1(ȳ′) = tv(ȳ), evalguard (guard , tv) = true {|ob(o, C, h, 〈tv , call(b, p(o, x̄, ȳ)) · s〉,Q)|S|}; {|ob(o, C, h, 〈tv ∪ tv1, b ′ 1 · · · b′n · s〉,Q)|S|}(5) r ≡ p(this′, x̄′, y′)← b′ 1 , . . . , b′n ≪ P, tv(o1) = o2, fn is a fresh future name newenv(r) = tv1, tv2 = tv1[this ′ 7→ o2, x̄ ′ 7→ tv(x̄), r 7→ (y′, fn)] {|ob(o, C, h, 〈tv , call(m, p(o1, x̄, y)) · s〉,Q), ob(o2,D, h1, 〈tv3, s1〉,Q′)|S|}; {|ob(o, C, h, 〈tv [y 7→ fn], s〉,Q), ob(o2, D, h1, 〈tv3, s1〉, {〈tv2, b ′ 1 · · · b′n〉} ∪ Q ′), fut(fn,⊥)|S|}(6) r 6∈ dom(tv) {|ob(o, C, h, 〈tv , ǫ〉,Q)|S|}; {|ob(o,C, h, ǫ,Q)|S|}(7) r ∈ dom(tv), (y, fn) = tv(r), v = tv(y) {|ob(o, C, h, 〈tv , ǫ〉,Q), fut(fn,⊥)|S|}; {|ob(o, C, h, ǫ,Q), fut(fn, v)|S|}(8) fn = tv(y), v 6= ⊥ {|ob(o, C, h, 〈tv , x := y.get · s〉,Q), fut(fn, v)|S|};{|ob(o, C, h, 〈tv [x 7→ v], s〉,Q), fut(fn, v)|S|}(9) evalg(g, h, tv ,S) = true {|ob(o,C, h, 〈tv , await g · s〉,Q)|S|}; {|ob(o, C, h, 〈tv , s〉,Q)|S|}(10) evalg(g, h, tv ,S) = false {|ob(o, C, h, 〈tv , await g · s〉, q)|S|}; {|ob(o, C, h, ǫ, {〈tv , await g · s〉} ∪ Q)|S|}(11) s ∈ Q {|ob(o, C, h, ǫ,Q)|S|}; {|ob(o, C, h, s,Q− {s})|S|}Fig. 3 Operational Semanti s7), the entry r is used to look for the orresponding future variable in order toupdate the ⊥ value with the one whi h is returned. Note that rule 9 he ks ifa future variable is ready. In su h ase the omputation pro eeds. Otherwise,in rule 10, the await task in introdu ed is the orresponding queue, and thepro essor is released.The instru tion get blo ks the exe ution until the future variable has avalue in 8. If the evaluation of the guard in an await instru tion su eeds,the exe ution ontinues in rule 9. Otherwise, in rule 10, the await task inintrodu ed is the orresponding queue, and the pro essor is released. In rule 11another task is dequeued (be ause the urrent one terminated or released thepro essor). Note that this rule is appli able thanks to rules 6 (resp. 7) whi h orresponds to the omplete exe ution of a blo k (resp. a method). 10 ELVIRA ALBERT et al.We assume that exe utions start from a main method. Thus, the initial on�guration is of the form {|ob(main,⊥,⊥, 〈tv , s〉, ∅)|}, where lo al variablesin tv are initialized to their default values. The exe ution then pro eeds non-deterministi ally by applying the exe ution steps in Fig. 3. The exe ution�nishes in a �nal on�guration in whi h all events are either future eventsor obje ts of the forms ob(o, C, h, ǫ, ∅) or ob(o, C, h, 〈tv , ǫ〉, ∅). Exe utions anbe regarded as tra es of the form S0 ; S1 ; · · · ; Sn where Sn is a �nal on�guration.Example 3 Consider the main method of the running example (Figure 1).After exe uting the onstru tors we rea h a on�guration with three obje ts: {|ob(main,⊥,⊥, 〈tvmain, bc〉, ∅), ob(o1,FileIS , ho1 , ǫ, ), ob(o2 ,FileIS , ho2 , ǫ, )|}where bc orresponds to the sequen e of instru tions from (*) on. After pro- essing both asyn hronous alls (rule 5) onse utively, the new state takes theform: {| ob(o1,FileIS , ho1 , ǫ, {〈tvo1 , bodyo1 〉}), fut(fn1 ,⊥), ob(o2,FileIS , ho2 , ǫ, {〈tvo2 , bodyo2 〉}), fut(fn2 ,⊥), ob(main,⊥,⊥, 〈tvmain[f1 7→ fn1, f2 7→ fn2], bc ′〉, ∅) |}where bodyo1 (resp. bodyo2 ) is the renamed body of method readOnce (resp. readBlock). Furthermore, tvo1 (resp. tvo2 ) stores the assignment tvo1(r) = (f1, fn1) (resp. tvo2(r) = (f2, fn2)). When the event 〈tvo1 , bodyo1 〉 is extra tedfrom the queue of o1 (rule 11), its omplete pro essing will repla e fut(fn1,⊥)by fut(fn1, v) (rule 7), where v is the value returned by the method readOnce.Note then that rule 9 an be used to pro ess the instru tion await f1? of theobje t main. At this point the new state will take this form: {| ob(o1,FileIS , ho1 , ǫ, ∅), fut(fn1 , v), ob(o2,FileIS , ho2 , ǫ, {〈tvo2 , bodyo2 〉}), fut(fn2 ,⊥), ob(main,⊥,⊥, 〈tvmain[f1 7→ fn1, f2 7→ fn2], bc ′′〉, ∅) |}3 Cost and Cost Models for Con urrent ProgramsWe now de�ne the notion of ost we aim at approximating by stati analysis.An exe ution step is annotated as S ; b o S ′, whi h denotes that we move froma state S to a state S ′ by exe uting instru tion b in obje t o. Note that froma given state there may be several possible exe ution steps that an be takensin e we have no assumptions on task s heduling. In order to quantify the ostof an exe ution step, we use a generi ost model M : Ins 7→ R whi h mapsinstru tions built using the grammar in Se tion 2.2 to real numbers. The ostof an exe ution step is de�ned asM(S ; b o S ′) =M(b).In the exe ution of sequential programs, the umulative ost of a tra e isobtained by applying a given ost model to ea h step of the tra e. In our set-ting, this has to be extended be ause, rather than onsidering a single ma hinein whi h all steps are performed, we have a potentially distributed setting, with