PDF de programación - Diseño e implementación de una máquina virtual para el cálculo de ambientes

Centro de Investigación y Estudios

Avanzados

del Instituto Politécnico Nacional
Departamento de Ingeniería Eléctrica

Sección de Computación

Diseño e implementación de una máquina virtual para

el cálculo de ambientes.

En la especialidad de Ingeniería Eléctrica con opción en

Tesis que presenta

Luis Rodrigo Gallardo Cruz

Para obtener el grado de
Maestro en Ciencias

Computación

Dr. José Oscar Olmedo Aguirre

Directores de tesis:
Dr. Alberto Oliart Ros

México, D.F.

Septiembre, 2005

ii

Agradecimientos

El autor de este trabajo desea agradecer su apoyo a las siguientes per-

sonas e instituciones:
A CINVESTAV.

A CONACyT, por el apoyo económico recibido a través de la beca 165921.

A LANIA, por el uso de sus instalaciones.

A mis asesores, por el tiempo invertido en este trabajo.

Al Dr. Carlos Artemio Coello.

A mi familia.

A Adriana.

Este trabajo fue realizado como parte del proyecto Ambiente de Pro-
gramación Distribuida y Móvil bajo nanciamiento de CONACyT (Ref:
37476-A).

iii

iv

Resumen

El cómputo móvil estudia los problemas peculiares al uso de dispositivos
de cómputo móviles, conectados entre sí por redes inalámbricas. A pesar
de las similitudes con el cómputo distribuido la investigación en el área ha
mostrado que existen diferencias sustanciales entre las dos disciplinas. Co-
mo resultado, las herramientas teóricas y prácticas del cómputo distribuido
no pueden ser usadas para el cómputo móvil.

Hay una gran cantidad de trabajo realizado en el desarrollo de mode-
los formales para el cómputo móvil, incluyendo en particular al cálculo de
ambientes, pero poco de este trabajo se ha trasladado hacia el desarro-
llo de lenguajes de programación para cómputo móvil, lo cual inhibe la
experimentación y el uso práctico.

Este trabajo describe el diseño e implementación de una máquina abs-
tracta para ejecutar el cálculo de ambientes, a la que hemos llamado MAC.
La implementación de esta máquina incluye una herramienta que ayuda a
visualizar los pasos de reducción en el cálculo de ambientes, para propósitos
educativos o de experimentación. La contribución principal de este trabajo
consiste en que la disponibilidad de esta máquina ayudará en la búsqueda
de lenguajes de programación adecuados para el cómputo móvil.

v

vi

Abstract

Mobile computing studies the problems associated with the use of mo-
bile computing devices interconnected by wireless networks.
In spite of
similarities with distributed computing, research in the area has shown
that there are substantial dierences between these two disciplines. As a
result, theoretical and practical tools from distributed computing can not
be used in mobile computing.

There is a great body of work in the area of formal models for mobile
computing, including in particular the Ambient Calculus, but little of this
work has been translated into the development of programming languages
for mobile computing, which inhibits experimentation and practical use.

This work describes the design and implementation of an abstract ma-
chine for execution of the Ambient Calculus, which we call MAC. The
implementation of the machine includes a tool to help visualize reduction
steps in the ambient calculus, for experimental or educational purposes.
The contribution of this work is that the availability of this machine will
aid in the search for adequate programming languages for mobile comput-
ing.

vii

viii

Índice general

Introducción

1. Modelos teóricos para cómputo móvil

1.1. Modelos previos . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1. Cálculo π . . . . . . . . . . . . . . . . . . . . . . . .
1.1.2. Join calculus . . . . . . . . . . . . . . . . . . . . . .
1.1.3. Mobile UNITY . . . . . . . . . . . . . . . . . . . .
1.1.4. Cálculo de ambientes . . . . . . . . . . . . . . . . . .
1.2. Lenguajes de programación . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .

1.2.1. Compiladores e intérpretes

2. El cálculo de ambientes

3. Máquina abstracta

3.1. Lenguaje fuente . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Estado interno . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Reglas de transición . . . . . . . . . . . . . . . . . . . . . .
3.4. Validez . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4.1. Completez . . . . . . . . . . . . . . . . . . . . . . . .
3.4.2. Ausencia de bloqueos
. . . . . . . . . . . . . . . . .

4. Implementación

5. Conclusiones y trabajo futuro

5.1. Conclusiones
. . . . . . . . . . . . . . . . . . . . . . . . . .
5.2. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . .

XIII

1
1
2
5
8
8
9
10

11

17
17
19
20
27
31
31

33

37
37
38

ix

x

A. Ejemplos

ÍNDICE GENERAL

A.1. RPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2. Firewall
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

B. Código fuente

B.1. Analizador sintáctico . . . . . . . . . . . . . . . . . . . . . .
B.2. Núcleo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.2.1. Máquina . . . . . . . . . . . . . . . . . . . . . . . . .
B.2.2. Ambientes . . . . . . . . . . . . . . . . . . . . . . . .
B.2.3. Procesos . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . .
B.2.4. Árboles
B.3. Bibliotecas de apoyo . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . .
B.3.1. Listas
B.3.2. Heaps . . . . . . . . . . . . . . . . . . . . . . . . . .
B.3.3. Boxes
. . . . . . . . . . . . . . . . . . . . . . . . . .
B.4. Interfaz con la línea de comandos . . . . . . . . . . . . . . .
B.4.1. boxed . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
B.4.2. cli

C. Manual de usuario

Bibliografía

Índice alfabético

39
39
48

55
55
59
59
78
80
83
86
86
87
90
92
92
92

95

97

103

Notación

!
N

Operador de replicación

El conjunto de nombres de ambientes

(ν n)P Introducción de n como un nuevo nombre privado al proceso P
P

El conjunto de los procesos de la máquina virtual

Composición paralela de procesos

(n).P Un proceso que recibe una comunicación, la asigna al nombre n y

continúa como el proceso P

hMi Un proceso que emite M sobre el canal anónimo implícito a un

ambiente

Un estado de la máquina virtual

Σ
A B El ambiente que resulta de eliminar a B como hijo de A
A ⊕ B El ambiente que resulta de añadir a B como hijo de A
H(c) Si H es un heap, la lista de procesos asociada a c

M.P Proceso que ejecuta la capacidad M, y luego se comporta como P

M[P] Un ambiente de nombre M y contenido P

P, Q, . . . Procesos en un cálculo de procesos

T

Una función que traduce estados de la máquina virtual al cálculo de
ambientes

xi

xii

ÍNDICE GENERAL

Top El nombre especial del ambiente de nivel superior en la máquina

virtual

0

El proceso nulo

heap Una colección de listas de espera de procesos que aún no se pueden

ejecutar

Introducción

El cómputo móvil es una disciplina relativamente nueva, pero que pro-
mete aumentar de importancia en el futuro cercano debido a la presencia
cada vez más común de dispositivos móviles. La naturaleza de estos disposi-
tivos es el origen del nombre: nodos pequeños, generalmente con capacida-
des de cómputo limitadas, con conexiones inalámbricas y que se desplazan
físicamente entre una red y otra.

La tendencia general en los sistemas de cómputo distribuido es ocultar a
los programas que se ejecutan en ellos la existencia de la red. En efecto, su
objetivo último es presentar la ilusión de ser una única máquina paralela,
de preferencia una semánticamente equivalente a una máquina secuencial,
pero más rápida.

Esta solución no es factible en el ambiente del cómputo móvil. La supo-
sición básica de una red de alcance global, mantenida en buena medida por
medio de comunicaciones inalámbricas que unen entre sí a redes tecnológica
y administrativamente independientes, invalida muchas de las suposiciones
básicas que permiten el modelo tradicional del cómputo distribuido.

Algunas de las diferencias más notables son [7, 34]:

En una red de área local se supone que ésta no fallará durante la eje-
cución de un programa. En general los errores son pocos y espaciados
y pueden ser manejados por el ambiente de cómputo sin necesidad de
que los programas se enteren. En cambio, en una red móvil los errores
son más frecuentes, y es posible que los programas necesiten tomar
acción explícita en presencia de éstos.

La extensión geográca de estas redes, por citar sólo un factor, impone
límites en la velocidad de comunicación, que son insuperables sin

xiii

xiv

INTRODUCCIÓN

importar el grado de avance tecnológico. El desempeño futuro de la
red no puede ser pronosticado a partir de lo observado en el presente.

La conguración de la red es dinámica. Nodos y subredes enteras
pueden añadirse o desaparecer sin previo aviso. Además, debido al
punto anterior, estos sucesos son indistinguibles de fallas transitorias.
El ancho de banda disponible puede variar de forma dramática e
impredecible.

La red consta de dominios administrativos separados, que de hecho
desconfían unos de otros. Por este motivo la comunicación entre ellos
está severamente limitada y se requieren permisos especiales para
migrar de uno a otro. El cómputo móvil es inherentemente peligroso,
puesto que los nodos están expuestos a riesgos, como el que un equipo
pueda perderse, sufrir daño físico o ser robado.

La realización plena del potencial del cómputo móvil depende de te-
ner herramientas que nos permitan atacar directamente las limitaciones
especícas del medio. La investigación ha producido modelos teóricos que
prometen un mejor entendimiento de los fenómenos relevantes. Es necesario
ahora probar estos modelos por medio de la experimentación, para conocer
sus fallos y aciertos desde el punto de vista de la ingeniería de software.
Un modelo formal para el cómputo móvil debe ser expresivo, pero también
fácil de entender y de usar. Además, para que