PDF de programación - Tesis: Jose Olmedo - PL/M-86 CONCURRENTE

CENTRO DE INVESTiG* CION Y DE

ESTUDIOS *VANZrtDOS DEL

I. P. N.

B I B L I O T E C A
INGENIERIA ELECTRICA

CENTRO DE INVESTIGACION Y DE ESTUDIOS AVANZADOS

INSTITUTO POLITECNICO NACIONAL

DEPARTAMENTO DE INGENIERIA ELECTRICA

SECCION DE COMPUTACION

PL/M-86 CONCURRENTE

Tesis que presenta el Lic. José Oscar Olmedo Aguirre para obtener el grado
de MAESTRO EN CIENCIAS en la especialidad de INGENIERIA ELECTRICA.

Trabajo dirigido por el Dr- Manuel E. Guzmán Renteria

México D.F. Junio de 1988

DEDICADO A MI FAMILIA

MI MAMA

MARIA DE LOS ANGELES AGUIRRE BARRIOS

MI TIA

GLORIA AGUIRRE BARRIOS

Y MI HERMANO

JORGE ALBERTO OLMEDO AGUIRRE

EN MEMORIA DE

MI ABUELA

MARIA EDUVIGES BARRIOS

CONTENIDO

PREFACIO ....................................................

INDICE DE CONTRIBUCIONES ....................................

CAPITULO I: PROGRAMACION CONCURRENTE ........................
LOS ELEMENTOS DEL LENGUAJE ............................
MODULARIZACION ....................................
SINCRONIZACION ....................................

CAPITULO II: EL LENGUAJE PL/M-86 ............................

CAPITULO III: EL NUCLEO DEL SISTEMA OPERATIVO X I N U .......... 14

1

3

4
6
6
7

8

ADMINISTRADOR DE MEMORIA .............................. 16
ADMINISTRADOR DE PROCESOS .............................. 22

LISTAS DE PROCESOS................................ 23
CAMBIO DE CONTEXTO................................ 24
OPERACIONES SOBRE PROCESOS ........................ 27
CALIFICADORES ........................................... 29
EL CALIFICADOR DOPROCESS .......................... 36
SINCRONIZACION Y COMUNICACION .......................... 40

S E M A F O R O S .........................................40
COMUNICACION DIRECTA .............................. 43
COMUNICACION INDIRECTA: PUERTOS .................. 44
MENSAJES COMPARTIDOS .............................. 47

CLASES Y M O N I T O R E S .....................................55
INTERRUPCIONES ......................................... 62
ADMINISTRADOR DEL RELOJ .......................... 63
INICIACION DEL SISTEMA ................................ 65

CAPITULO IV: APLICACIONES .................................. 67
PROBLEMAS CLASICOS DE CONCURRENCIA .................... 67
LA RELACION PRODUCTOR CONSUMIDOR USANDO CLASES . . . 67
LA RELACION PRODUCTOR CONSUMIDOR USANDO MENSAJES . . 71
LOS F I L O S O F O S .....................................72
LOS LECTORES Y E S C R I T O R E S ........................ .74
LOS F U M A D O R E S .....................................77
PASCAL C O N C U R R E N T E .............. . .................... 80

CONCLUSIONES ..................................................87

CENTRO DE INVESTIGACION Y BE

ESTUDIOS ■' V a KZ • DOS DEL

S. P. N.

B I B L I O T E C A
INGENIERIA ELECTRICA

BIBLIOGRAFIA ................................................ 88

APENDICE I: EXTENSIONES AL LENGUAJE ........................ 91

T I P O S .................................................. 92
OPERACIONES............................................ 93
S E N T E N C I A S .................................... ..

105

APENDICE II: LISTADOS .......................................108

DEFINICIONES Y VARIABLES GLOBALES: CONF.DEC ............ 109
LISTAS DE PROCESOS: Q . . ......... ..................... 111
ADMINISTRADOR DE MEMORIA: M E M .......................... 115
ADMINISTRADOR DE PROCESOS: P R O C ........................ 119
SEMAFOROS Y COMUNICACION DIRECTA: SEM .................. 126
ADMINISTRADOR DE RELOJ: CLOCK .......................... 131
COMUNICACION POR PUERTOS: PORTS ........................ 135
CLASES Y OBJETOS: D A T A ................................ 141
INICIACION: SYSINIT .................................... 146
ENTRADA Y SALIDA: E S .................................. 149
CLASES Y MONITORES: CLASS .............................. 154
OPERACIONES EN XINU: XINU.EXT .......................... 154

APENDICE III: MENSAJES DE ERROR ............................ 155

PREFACIO

En

la

de
programación para tratar problemas que involucran múltiples actividades que
se desarrollan con un paralelismo potencial.

programación concurrente se incluyen las

técnicas

Aun cuando tiene sus orígenes en el estudio de los sistemas operativos
es necesario distinguirlos.
de
abstracción de estos conceptos hasta convertirlos en construcciones de un
lenguaje de programación.

La tendencia es aumentar el grado

En .la actualidad existen varios lenguajes de programación para la

escritura de programas concurrentes en ambientes centralizados: Pascal
Concurrente [Brinch Hansen, 1975], Modula [Wirth, 1977], Pascal-Plus [Welsh
y Bustard, 1979] son extensiones al Pascal secuencial y CSP/k [Holt, 1978]
está basado en PL/I. Otros lenguajes de alto nivel se han propuesto para
ambientes distribuidos: Communicating Sequential Process [Hoare, 1978] y
Ada [1980] entre los mas conocidos, se distinguen por las facilidades que
ofrecen para la comunicación entre procesos.

El propósito de esta tesis es extender el lenguaje de desarrollo PL/M-
86 para facilitar la programación concurrente en un ambiente centralizado.
El resultado es el lenguaje PL/M-86 CONCURRENTE.

La ampliación del lenguaje consiste en definir un conjunto de
estructuras de datos, procedimientos y construcciones en los propios
términos del lenguaje de desarrollo. A este conjunto se le llama núcleo. El
núcleo fué tomado del sistema operativo XINU [Colmer, 1981] por su claridad
y sencillez de diseño.

El material está organizada de la siguiente forma. El capitulo I es
una introducción a la programación concurrente donde se introducen algunos
de los términos usados en este trabajo. El capitulo II describe las
El capitulo III es la
características del lenguaje de desarrollo.

1

descripción del núcleo de XINU. Incluye los temas de administración de bajo
nivel de memoria, procesos, sincronización y comunicación. Se describen
construcciones adicionales como las clases y los monitores. El manejo de
interrupciones se muestra con un administrador de reloj en tiempo real. El
capitulo IV ilustra el uso del lenguaje con algunos problemas clásicos de
concurrencia. Por último, se describe cómo llevar este trabajo para
extender otro lenguaje de programación como Pascal, ejemplificándolo con la
construcción de rutinas de servicio de interrupción.

Esta tesis no es solo el trabajo de implantación del núcleo de
concurrencia. Presenta también conceptos y técnicas originales que nacieron
con este trabajo. Se encuentran a lo largo de la exposición y sólo aquellos
que considero más importantes se les hace referencia en un Índice especial
de contribuciones.

PL/M-86 CONCURRENTE tiene aplicaciones en las áreas de lenguajes de
programación, sistemas operativos, comunicaciones, simulación e ingeniería
de software.
de
investigación actual.

La programación concurrente

es un tema importante

Para

comprender

mejor este trabajo, el lector

debe

poseer

conocimientos de sistemas operativos y estar familiarizado con
la
arquitectura del procesador 8086/8088, asi como de un lenguaje estructurado
como PL/I, Pascal o C.

Deseo agradecer al Dr. Manuel Guzmán Rentería el interés que despertó
en mí por la programación concurrente, y su apoyo para la realización de
este trabajo. Al Dr. Renato Barrera y al M.
en C. César Galindo por la
cuidadosa lectura y acertadas observaciones que realizaron.

A mi amigo, M. en C. Feliú Sagols no sólo por la revisión de este
material,
sino también, por su valioso ejemplo durante los estudios de
maestría. A mi hermano, Ing. Jorge Olmedo por la lectura y sugerencias
hechas a este trabajo.

2

INDICE DE CONTRIBUCIONES

Las aportaciones o puntos de mayor interés de este trabajo son los

siguientes:

1. El núcleo de concurrencia de XINU está escrito completamente en el
lenguaje PL/M-86. No existe ninguna parte producida en un lenguaje de bajo
nivel.

2. La estructura del descriptor de procesos se ha modificado de manera
que no se requiere guardar todos los registros del procesador; solo se
conservan dos registros que permiten guardar y restaurar el ambiente del
proceso. En consecuencia, se propone un método para realizar el cambio de
contexto [pp. 24-27],

3. Se describe una técnica muy versátil para obtener la información de
un procedimiento a tiempo de ejecución como la dirección del código, sus
parámetros actuales, etc. Esta técnica, que llamo "calificadores", permite
extender el lenguaje agregando nuevas sentencias [pp. 29-36].

4. Se describe una nueva forma de crear y destruir procesos [pp. 36­

39].

5. Posee la capacidad de encapsular los datos y sus operaciones

mediante clases (tipos abstractos de datos) [pp. 55-60].

6. Proporciona una construcción muy frecuente en la solución de

problemas de concurrencia: el monitor [pp. 60-61].

7. La comunicación indirecta entre procesos usa mensajes cuyo tipo es

definido por el programador [pp. 44-46].

8. Provee un método muy poderoso para la comunicación entre procesos
por medio de los mensajes compartidos. Como una ilustración de este método,
presento una solución al problema clásico de concurrencia debido a Patil
[1971]: los fumadores [pp. 47-54],

9. Las ideas de este trabajo se pueden llevar a cualquier otro
lenguaje de programación. La sentencia adicional IOBEGIN/IOUNTIL, convierte
a un procedimiento en una rutina dé servicio de interrupción en el lenguaje
Pascal [pp. 80-86].

3

CAPITULO I

PROGRAMACION CONCURRENTE