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

Imágen de pdf Computación distribuida basada en Objetivos

Computación distribuida basada en Objetivosgráfica de visualizaciones

Actualizado el 29 de Agosto del 2018 (Publicado el 11 de Marzo del 2018)
459 visualizaciones desde el 11 de Marzo del 2018
4,9 MB
331 paginas
Creado hace 7a (02/10/2012)
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
  • Links de descarga
http://lwp-l.com/pdf9450

Comentarios de: Computación distribuida basada en Objetivos (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad