PDF de programación - Computación distribuida basada en Objetivos

UNIVERSITAT POLIT `ECNICA DE VAL `ENCIA

Dept. Sistemes Inform`atics i Computaci´o

TESIS DOCTORAL

PROGRAMA DE DOCTORADO EN INFORM ´ATICA

Computaci´on Distribuida

basada en Objetivos

Autor:

Javier Palanca C´amara

Supervisado por:

Dra. Ana Garc´ıa Fornes
Dr. Vicente Juli´an Inglada

AUTOR:

JAVIER PALANCA C ´AMARA

DIRECTORES: DR. VICENTE J. JULIAN INGLADA

DRA. ANA M. GARC´IA FORNES

T´ITULO: COMPUTACI ´ON DISTRIBUIDA BASADA EN OBJETIVOS

DEPARTAMENTO: SISTEMAS INFORM ´ATICOS Y COMPUTACI ´ON

UNIVERSIDAD: UNIVERSIDAD POLIT ´ECNICA DE VALENCIA

GRADO: DOCTOR MES: OCTUBRE A ˜NO:

2012

Grupo de Tecnolog´ıa Inform´atica - Inteligencia Artificial

Departament de Sistemes Inform`atics i Computaci´o

UNIVERSITAT POLIT `ECNICA DE VAL `ENCIA

Camino de Vera, s/n
46020 Val`encia, Spain

A mi madre y a mi padre.

Pr ´ologo

Cuando Javier me pidi´o que le escribiera el pr´ologo lo primero que
me vino a la mente fue la m ´usica. No entend´ı por qu´e fue mi primer
pensamiento hasta que empec´e a leer el libro. Fue la intuici´on de aque-
llo que me iba a encontrar entre las p´aginas de aquel documento sin
encuadernar y lleno de ilusi´on que me lleg´o a las manos.

La m ´usica es muy importante en todas las fases de la vida. Hay
miles de estilos, de sonidos, que marcan nuestro estado de ´animo. Po-
demos ir desde la calma provocada por un adagio interpretado por
una orquesta hasta el en´ergico furor de una canci´on punk. Cada estilo
tiene sus instrumentos, las secciones de cuerda en la m ´usica barroca,
los vientos en las formaciones de blues, la guitarra en el rock, etc, pe-
ro todos los estilos tienen algo en com ´un, algo que los une y que es
fundamental a la hora de interpretar cualquier melod´ıa, la percusi´on.
Cada uno de los m ´usicos tiene un objetivo dentro de la formaci´on pero
todos, unidos, persiguen un objetivo com ´un, que la melod´ıa suene, y
suene correctamente. Dentro de esta organizaci´on el percusionista de-
be de crear los huecos donde los dem´as interpretes tienen que enlazar
sus notas, si la percusi´on se acelera o disminuye su cadencia todo so-

V

nar´a diferente. Da igual el estilo, da igual el resto de instrumentos, sin
percusi´on todo es m´as ca´otico.

A medida que avanc´e en la lectura del manuscrito apreci´e que Ja-
vier, como buen percusionista, ha sabido plasmar c´omo entidades con
diferentes objetivos pueden trabajar conjuntamente por un bien mayor
o, simplemente, para que la m ´usica suene bien. El sistema creado aporta
al usuario de forma transparente mecanismos que gestionan eficiente-
mente el trabajo de las entidades, teniendo en cuenta que cada una de
ellas dispondr´a de sus propios objetivos, ordenando el plan de ejecu-
ci´on de las entidades, dando paso a aquellas m´as prioritarias, deter-
minando cual es su tempo correcto, y finalmente marcando un ritmo
arm´onico a cada ejecuci´on de cada una de ellas.

Su trabajo aporta un nuevo paradigma de dise ˜no y programaci´on
que facilita la creaci´on y gesti´on de sistemas multi-agentes de forma
trasparente al usuario final, y ofrece un sistema de planificaci´on de ta-
reas basada en los objetivos que se desean alcanzar y no en los servicios
que se ofrecen. Busca los huecos donde deben sonar cada uno de los
instrumentos para que el objetivo, la melod´ıa, sea correctamente alcan-
zado.

Puede que un sistema con varias entidades heterog´eneas trabajan-
do conjuntamente sea capaz de encontrar soluciones complejas sin ne-
cesidad de una mano que las dirija, incluso el caos en alg ´un momento
tiende al orden, pero de lo que estoy seguro es que con un percusionis-
ta, todo ir´a mejor.

Dr. Mart´ı Navarro

´Indice general

XXIII

XXXV

Resumen

Agradecimientos

I Motivaci´on y Objetivos

1. Motivaci´on y Objetivos

1.1. Motivaci´on .

1.2. Objetivos .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . .

1.3. Estructura de la memoria . . . . . . . . . . . . . . . . . .

II Estado del Arte

2. El Paradigma de Computaci´on Orientada a Objetivos

VII

1

3

3

6

8

11

13

2.1. Paradigmas de Programaci´on . . . . . . . . . . . . . . . . 14

2.2. El Paradigma de Computaci´on Orientada a Objetivos . . 16

2.3. Agentes BDI .

.

2.4. Servicios Web .

2.5. Discusi´on .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . 17

. . . . . . . . . . . . . . . . . . 19

. . . . . . . . . . . . . . . . . . 21

3. Representaci´on de Objetivos

23

3.1. Lenguajes de Representaci´on de Objetivos . . . . . . . . . 25

3.2. Razonamiento sobre Objetivos

. . . . . . . . . . . . . . . 28

3.2.1. Goal Models .

3.2.2. 2APL .

.

.

.

.

.

.

.

.

.

.

.

.

3.2.3. C´alculo Situacional .

.

.

.

. . . . . . . . . . . . . . . . 30

. . . . . . . . . . . . . . . . 31

. . . . . . . . . . . . . . . . 32

3.3. Discusi´on .

.

.

.

.

.

.

.

.

.

. . . .

. . . . . . . . . . . . . . 33

4. T´ecnicas de planificaci´on para paradigmas orientados a obje-

tivos

35

4.1. Composici´on de Servicios Web . . . . . . . . . . . . . . . 36

4.1.1. Orquestaci´on de Servicios . . . . . . . . . . . . . . 37

4.1.2. Coreograf´ıa de Servicios . . . . . . . . . . . . . . . 37

4.1.3. Algoritmos de Composici´on de Servicios . . . . . 38

4.2. Planificaci´on en Inteligencia Artificial

. . . . . . . . . . . 39

4.3. Sistemas de Planificaci´on Basada en Casos . . . . . . . . . 42

4.3.1. Razonamiento Basado en Casos

. . . . . . . . . . 42

4.3.2. Planificaci´on Basada en Casos . . . . . . . . . . . . 46

4.4. Discusi´on .

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . 48

5. Abstracciones y Planificadores en Sistemas Operativos

51

5.1. Qu´e es un Sistema Operativo . . . . . . . . . . . . . . . . 52

5.2. Clasificaci´on de los Sistemas Operativos . . . . . . . . . . 53

5.2.1. Clasificaci´on revisada . . . . . . . . . . . . . . . . 54

5.3. Algoritmos de planificaci´on . . . . . . . . . . . . . .

. . . 59

5.4. Abstracciones de los Sistemas Operativos . . . . . . . . . 64

5.5. Discusi´on .

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . 67

III Propuesta

6. An´alisis de un Sistema Operativo orientado a Agentes

71

73

6.1. Misi´on de la Organizaci´on . . . . . . . . . . . . . . . . . . 76

6.2. Objetivos .

6.3. Servicios .

.

.

.

.

.

.

6.4. Actores y Roles

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

6.5. Consideraciones finales .

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . 77

. . . . . . . . . . . . . . . . 78

. . . . . . . . . . . . . . . . . . 79

.

.

. . . . . . . . . . . . . . . . 86

7. Computaci´on Distribuida basada en Objetivos

89

7.1. Definici´on .

7.2. Servicios .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . 90

. . . . . . . . . . . . . . . . . . 96

7.2.1. Descubrimiento de Servicios

. . . . . . . . . . . . 97

7.3. Lenguaje de Objetivos

.

7.4. Consideraciones finales .

.

.

. . . . . . . . . . . . . . . . . . 98

. . . . . . . . . . . . . . . . . . 101

8. Dise ˜no de un Sistema Operativo orientado a Objetivos

105

8.1. Una arquitectura orientada a la ejecuci´on de objetivos . . 106

8.2. Deliberation Engine .

.

.

8.2.1. On-line Planner .

.

.

. . . . . . . . . . . . . . . . . . 113

. . . . . . . . . . . . . . . . . . 114

8.2.2. Commitment Manager . . . . . . . . . . . . . . . . 122

8.3. Runtime Engine .

.

.

.

.

.

. . . . . . . . . . . . . . . . . . 125

8.3.1. Traza de ejecuci´on . . . . . . . . . . . . .

. . . . . 129

8.4. Experimentos y Resultados

. . . . . . . . . . . . . . . . . 134

8.4.1. El simulador .

.

.

.

.

.

. . . . . . . . . . . . . . . . 135

8.4.2. Experimentos del Deliberation Engine . . . . . . . 138

8.4.3. Experimento 6: Pruebas de rendimiento distribui-

das .

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . 150

8.4.4. Experimento 7: Ratio de aceptaci´on de planes

. . 153

8.5. Consideraciones finales .

.

.

.

. . . . . . . . . . . . . . . . 156

9. Planificaci´on con Predicci´on del Deadline basada en Benefi-

cios

157

9.1. Deadline Prediction Scheduler

. . . . . . . . . . . . . . . 159

9.1.1. El problema de la planificaci´on con predicci´on

del deadline .

.

.

.

.

.

. . . . . . . . . . . . . . . . 160

9.1.2. Deadline Prediction Scheduler con Reserva de CPU

(DPS) .

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . 162

9.1.3. DPS con Reserva de CPU utilizando Promoci´on

de Prioridades Din´amica (DPS-Dy) . . . . . . . . . 166

9.1.4. DPS con Razonamiento basado en Beneficios (BDPS)172

9.2. Experimentos y Resultados

. . . . . . . . . . . . . . . . . 178

9.2.1. El simulador .

.

.

.

.

.

. . . . . . . . . . . . . . . . 178

9.2.2. Experimento 1: Precisi´on de la predicci´on del dead-

line .

.

.

.

.

.

.

.

.

. . . .

. . . . . . . . . . . . . . 181

9.2.3. Experimento 2: Beneficios . . . . . . . . . . . . . . 184

9.2.4. Experimento 3: M´etricas de planificaci´on . . . . . 188

9.2.5. Experimento 4: Puesta a punto del planificador

BDPS .

.

.

.

.

.

.

9.3. Consideraciones finales .

.

.

. . . . . . . . . . . . . . . . . . 195

.

.

. . . . . . . . . . . . . . . . 199

10. Caso de Uso

201

10.1. Descripci´on del Caso de Uso . . . .

. . . . . . . . . . . . . 202

10.2. Objetivo del Caso de Uso .

. . . . . . . . . . . . . . . . . . 204

10.3. Planificaci´on del Caso de Uso . . . . . . . . . . . . . . . . 207

10.4. Traza de ejecuci´on .

.

.

.

10.5. Consideraciones finales .

.

.

. . . . . . . . . . . . . . . . . . 219

.

. . . . . . . . . . . . . . . . . 226

IV Conclusiones

11. Conclusiones y Trabajo Futuro

229

231

11.1. Contribuci´on .

.

11.2. Trabajo Futuro .

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . 231

. . . . . . . . . . . . . . . . . . 234

11.3. Publicaciones relacionadas .

.

. . . . . . . . . . . . . . . . 237

A. SPADE: Un sistema multiagente basado en XMPP

245

A.1. Modelo de Comunicac