Mexico, Df Diciembre De 1991 J

Transcript

- MEXICO, D.F. DICIEMBRE DE 1991 J CONTENIDO \ I INTRODUCCION l. PROCESOS Y SU CONVIVENCIA 1.1 Exclusidn Mutua 1.1.1 1.2 Secciones Criticas 7 1.3 SleepWakeup (BloqueoDespertar) 8 1.4 Abrazo Mortal 9 1.4.1 2. 2.2 1 \ c 3. característicasdelabrazomortal 9 COMUNICACION Y SINCRONIZACION ENTRE PROCESOS 2.1 3 exclusidnmutuaconespera activa 12 Memoria Compartida 13 2.1.1 semaforos 13 2.1.2 monifmes 16 Envíoy-pcidndeMensajes 19 2.2.1 implementacidn del mensaje 20 2.2.2 modelos 25 CONCLUSIONES 27 NOTAS 28 BIBLIOGRAFIA 29 ..,..-. ~ ", ." . , INTRODUCCION La programación concurrente desempeña hoy en díaun papel muy importante. Aunque no siempre nos damoscuenta, la aprovechamos, por ejemplo, cuando retiramos dinero-mediante un cajero automático. AI inicio, las computadoras eran secuenciales, es decir, el procesador central ejecutaba un programa suspendiendo ocasionalmente sus acciones cuando necesitaba transportar los datos por medio de los dispositivos de entraddsalida. El desarrollotecnológicode hardware provocó un cambioenlaorganizacióndelas computadoras, de manera que el procesador central ahora podía trabajar simultáneamente con sus periféricos. Esto implica también, que más deun programa se podíaejecutar "casi" al mismo un programa espera para el cumplimiento de la lecturalos dedatos, tiempo, pues, mientras que el procesador puede ejecutar otro programa. A este tipo de servicio se le llamó multiprogramación, es decir,cuando una computadora divide sus recursos tales como: tiempo de procesador, memoria y periféricos, entrevarios programas. Más tarde, surge un nuevo concepto (debido a la baja en el costo y tamaño de los procesadora), se trataba de tener másde un programa (o más de una parte del mismo programa) cjccutlndose verdaderamente en paralelo, compartiendo la memoria comcepto se llamó multiprocesamiento. y los periféricos; dicho La ocurrencia paralelade varios eventos dentro deun sistema de cómputo tiene consigo un buen numerosos problemas: hay que coordinar la cooperación de varias unidades, asegurar uso de la memoria compartida, distribuir el tiempo de los procesadores y periféricos, evitar bloqueo mutuo, etc. En la actualidad, a medida que disminuye tanto el tamaiio comoprecio el del hardware de lascomputadoras, se irá produciendo una tendencia haciael multiprocesamientoylamasificación delparalelismo. Si ciertasoperacionespuedenserejecutadasenparalelodeformalógica, entonces las computadoras del futuro las ejecutarán físicamente en paralelo. J PBg 1 El procesamiento en paralelo es interesante por varias razones.La gente parece más capaz de centrar su atención en una sóla actividad a la vez, que de pensar en paralelo; por ejemplo,un lector puede intentar leer dos libros al mismo tiempo, leyendo una línea de cada libro alternativamente, esto indudablemente le hará notarlo dificil que es coordinar el entendimiento. Phg 2 1. PROCESOS Y SU CONVIVENCIA El concepto de proceso está implícita o explícitamente presente en todos los sistemas operativosmultiprogramados.Es decir, sistemasoperativosqueproporcionangestiónde archivos, y gestión de memoria, además de soportar la ejecución concurrente de programas. Asimismo, su importancia ha sido reconocida por los diseiiadores de algunos lenguajes de alto nivel, como Ada y Modula; que proporcionan mecanismos de manera específica para la gestión de procesos simultáneos o concurrentes,E n esencia un PROCESO o TAREA es un caso de programa en ejecución. Es el trabajomínimo que es suceptible ser deplanificado individualmente por un sistema operativo. 1.1 E x c l u s i h Mutua En programaciónsecuencial,lacooperación entre variosmódulosdelprogramaestá En el caso de la programación concurrente generalmente basada en el uso de variables globales. donde varios procesos se ejecutan a la vez, el uso no controlado de variables globales podría llevar a resultados inesperados para los usuarios. Para evitar está ambigüedad en los resultados, hay que asegurar que elacceso a una variable compartida(u otro recurso) sea adquirido de manera exclusiva por cada proceso. Este mecanismo de programación se llama EXCLUSION MUTUA. Cuando varios procesos tienen variables compartidas, suele darse caso,el en que doso más procesos desean modificar cierta variable compartida,lo cual no pueden hacerlo al mismo tiempo, este problema puede solucionarse dándole a cada proceso acceso exclusivo a la variable compartida. Mientras un proceso accede a la variable compartida, los demás procesos que deseen hacer lo mismo al mismo tiempo deben permanecer a espera; la cuando ese proceso termine de acceder ala variable deseada, le será permitido proceder a uno los de procesos en espera. En otras palabras, enla exclusión mutua un proceso evita temporalmente alos otros usar un recurso compartido durante las operaciones críticas que puede afectar adversamente a la integridad dcl sistcma, es dccir, s61o se pcrmitiri cl acceso al rccurso compartido mcncionadoal proceso que ejecuta la sección crítica, y al resto de los procesos se les impedirá hacerlo'hastala finalización apropiada de la sección crítica. Pág 3 Por el momento, considérese que la sección crítica es la parte del programa donde se M& adelante manipula de alguna forma a las variables compartidas por los distintos programas. se da una definición más formal de este concepto. 1.1.1 exclusiiin mutua con espera activa La solución más simple consiste en hacer que cada proceso desactive todas las interrupciones justo después de entraren su sección critica y l a s vuelve a activar antes de salir de ella. Este método es poco atractivo por que es imprudente dar a los procesos del usuario el poder de desactivar interrupciones. Considérese que se tieneuna sola variable (decierre) compartida que inicialemente vale O. Cuando un proceso desea entrarsuaregión crítica, este primero prueba cerrojo. el Si elcerrojo es O, el proceso lo haceigual a 1, y entra en su sección critica. Si elcerrojo ya vale 1, el proceso simplemente espera a que se vuelva O. Por lo tanto, O significa que no hay ningún proceso en su sección crítica, y 1 quiere decir que hay algún proceso en su sección crítica. El algoritmo seria el siguiente: Cerrojo (purtu); ejecuta-sección-critica; Quita-Cerrojo (pucrtu); donde la variable compartida sería: puerta. Considérese la siguiente situación: existen dos procesos que comparten la variable puerta, el proceso 1 prueba el cerrojo y advierte que es O, en ese momento el proceso 1 entra a ser planificado (va a la cola de procesos en espera) por causa de la terminación del tiempo del procesador que le corresponde. Ahora el proceso 2 es el proceso activo;y también prueba elcerrojo, luego lo coloca en1 y entra en su sección critica. Cuando vuelve elproceso 1 a estar activo, continúa con su tarea, y ahora coloca el cerrojo en 1 y también entra en su sección crítica. Nótese que ahoraambos procesos están ejecutando sus secciones críticasal mismo tiempo, lo cual eslo que se desea evitar. PBg 4 Una solución alternativaes considerar "turnos"para entrar a la sección crítica: En esta solución, la variableentera TURNO que inicialmente vale O, lleva el control de los turnos de entrada en la seccidn críticay examina o actualiza la memoria compartida. El algoritmosería el siguiente: PROCESO-1; WHILE ( TRUE ) { WHILE ( TURNO < > O ); sección crítica; TURNO = 1; otras cosas; I* espera *I 1; PROCESO 2; WHILE (TRUE ) { WHILE ( TURNO e > 1 ); sección crílica; TURNO = O; otras cosas; I* espera *I 1; Tomar turnos no es adecuado cuando uno de los procesoses mucho más lento que el otro. Esta solución requiere que dos procesos alternen se estrictamente cuando entren ensus secciones críticas. U n algoritmo eficiente para asegurarla EXCLUSION MUTUAentre dos procesos,es el propuesto por DEKKER, donde utiliza variablespara veriricar qué proceso requiere entrar a su sección crítica y si en realidad le tocasu ''turno'' para entrar (en este caso se refiere a la variable preferencia). PROCESO-1; { while ( true ) { proceso-1 = true; while ( proceso-2 ) { if ( preferencia = = 2 ) { proceso-1 = false; while ( p r e f r e m i u = = 2 ); proceso-1 = true; }; sección-críticagroceso-1; proceso-1 = false; prefcreeniu = 2; otros; 1: I; 1; PROCESO-2: { while ( true ) { proceso-2 = true; while ( proceso-1 ) { if ( preferencia = = 1 ) { proceso-2 = false; while ( preferencia = = 1 ); proceso-2 = true; 1; sección~críticagroceso~2; proceso-2 = false; preferencia = 1 ; otros; 1; 1; 1; PROCEDIMIENTO D E K U R : { proceso-2 = false: proccso-1 = I'alsc: parbegin PROCESO-1; PROCESO-2; parend; 1; PBg 6 . -4- " * W I . - ." . .. " " " .. 1.2 Secciones Criticas La exclusión mutua necesita ser aplicada sólo cuando un proceso acceda a datos compartidos: cuando los procesos ejecutan operaciones que no estén en conflicto entre sí, debe permitirseles proceder de forma concurrente. "Cuando un proceso está accediendoadatoscompartidossedicequeelprocesose encuentra en su seccwn cririca"(1).Mientras un proceso se encuentra en su sección crítica, los demás procesos pueden continuar con su ejecución fuera desus secciones críticas. Cuando un proceso abandona su sección crítica, entonces debe permitírsele proceder a otro proceso que espera entraren su propia sccción crítica (si hubieraun proceso cn espera). Estar dentro de una sección crítica es un estado muy especial asignado a un proceso. El proceso tiene acceso exclusivo a los datos (o recursos) compartido y todos los demás proceso que necesitan acceder a esos datoso permanecen en espera. Por lo tanto las secciones críticas un progranla no debe bloquearse dentro de su sección deben ser ejecutadas más lo rápido posible, crítica, y las secciones críticas deben ser codificadas con todo cuidado,para evitar, por ejemplo, la posibilidad de incurrir en un ciclo infinito. Se necesita quc se cumplan 4 condiciones paratener una solución adecuada: 1. Nuncadosprocesospuedenencontrarsesimultáneamentedentrode sus secciones críticas. 2. No se hacen suposiciones acerca de l a s velocidadesrelativasde los procesos o del número de CPU. 3. Ningún proceso suspendido fuera de la sección crítica debe bloquearotros a procesos. 4. Nunca un proceso debe querer entrar en forma arbitraria ensu sección crítica. P6g 7 1.3 Sleeywukeup (Bloqueo/Despertur) Ahora almacenaremos algunas primitivas de comunicación entre procesos que se bloquean en vez de gastar el tiempo de CPU la cuandono tienen permiso de entrar sus ensecciones críticas. SLEEP es una llamada al sistema que hace que se desbloquee el solicitante, es decir, que se suspenda hasta que otro proceso lo desbloquee. La llamada WAKEUP tiene un parámetro, el proceso que se desbloqueará. ' Para poner un ejemplo de la forma en que se utilizan estas primitivas, consideremos el problema del PRODUCTOR-CONSUMIDOR: Dos procesos compartenun buffer común de tamaño fijo. Uno de ellos es el productor, coloca información en el b u k r y el otro, el consumidor la extrae. El problema se presenta cuando el productor quiere colocar un nuevo elemento en el y luego se desbloquee buffer, pero éste ya está lleno.La solución es que el productor se bloquee cuando el consumidor haya retirado uno o miis elementos. En forma análoga, si el consumidor desea retirar un elemento del buffer y advierte que éste está vacío, se bloquea hasta que el productor coloque algoen el buffer y lo desbloquee. PRODUCTOR ( ) { while (true) { produce-elementos ( ); I f cont==N) S EEP ( ); coloca-elementos ( ); cont = cont + 1 if (cont = = 1) WAKEUP (consumidor): I }: }; CONSUMIDOR ( ); { while (true) { if (cont == O ) SLEEP ( ): 147687 saca-elementos ( ); cont = cont - 1; if(cont == N - 1 ) WAKEUP ( productor); PBg 8 1.4 Abrazo Mortal "Se dice que un proceso dentro de un sistema de multiprogramación está en ABRAZO MORTAL (o estado de interbloqueo)si está esperando porun evento determinado queno va a ocurrir" (2). En el interbloqueo de un sistema están en situación hermética uno o más procesos. En sistemas computacionales multiprogramados, compartir los recursos es l a s una metasde principales del sistema operativo. Cuando los recursos son compartidos entre una población de usuarios, donde cada uno mantieneun control exclusivo sobre recursos determinados asignados a este usuario, pueden producirse abrazos mortales en los cuales de algunos usuarios los procesos nunca podrán llegara su término. Un ejemplo es el siguiente: Dos procesos P1 y P2 comparten los recursosR1 y R2 y que en un momento determinado, el recursoR1 ha sido asignado al proceso P1 y que R2 ha sido asignado alproceso P2. Ahora el proceso P1 solicita ademáa el recurso R2 para progresar sus acciones pero, como R2 ya esta R1, ambos procesos quedan bloqueados asignado al proceso P2 solicita el acceso al recurso mutuamente. Cuando esto sucede, ninguno de los dos puede liberar el recurso que tiene asignado, así que los dos quedan enun ABRAZO MORTALpara siempre. 1.4.1 características del abrazo mortal Existen varios criterios que caracterizan aun ABRAZO MORTAL, uno de ellos es una situaci6n ESTATICA. En este criterio se estableceque un ABRAZO MORTALpuedesurgir siy sólo si ocurren simultáneamente: - Los recursos se manejan en exclusión mutua. Pág 9 - Se genera una cadena circular de procesos, donde cada uno de ellos tienen asignados uno o más recursos requeridos porlos otros procesos. AI darsc las cuatro condicioncs se pucdc dar un ABRAZO MORTAL. Sc han diseñado políticas para resolver el problema, éstas son las siguientes: PREVENCION El interés se centra en condicionar un sistema para que elimine toda posibilidad de que abrazos mortales se produzcan. La prevención es unasolución limpia lo enque respecta al abrazo mortal propiamente dicho, pero los métodos de prevención pueden.dar como resultado una pobre utilizaci6n de los recursos. Sin embargo, los métodos de prevención del interbloqueo se utilizan con gran frecuencia. El método consiste en negaruna o más de las condiciones necesarias para que ocurra un abrazo mortal, de esta manera cualquier posibilidad de que ocurraun abrazo mortales eliminada del sistema. EVITACION La meta es imponer condiciones menos estrictas que en la prevención, para intentar lograr una mejor utilización de los recursos. La evitación no precondiciona al sistema para que evite un abrazo mortal.En su lugar, los métodos de evitación todas las posibilidades de que se produzca permiten la aparición del abrazo mortal, pero siempre que se produce una posibilidad de abrazo mortal, este se esquiva. Si las condiciones necesarias para que tenga lugar un abrazo mortal están ensu lugar, aún los recursos. Talvez el algoritmo de evitación de es posible evitarlo, teniendo cuidado al asignar interbloqueo más famoso es eldef bumper-ode Dijkstra, denominado coneste interesante nombre y recibe pagos de unafuente dada de debido a que introduce un a banquero que hace préstamos capital. P4g 10 DETECClON Estos métodos. se utilizan en sistemas que permiten que éstos ocurran, ya sea de forma voluntaria o involuntaria. La meta de la detección del abrazo mortal es determinar si ha ocurrido un abrazo y detectar precisamente aquellos procesosy recursos implicados enél. Una vez determinado, éste puede ser eliminado del sistema. RECUPERACION Estos métodos se utilizan para despejar abrazos mortales de un sistema, de manera que y losproccsos estancadosllcgucn a su tcrminaci6n, liberando pucdaseguir operando libre de ellos, así sus recursos. En el mejor de los casos, la recuperación esun problema sucioy la mayoría de los sistemas se liberan del abrazo mortal extrayendo su en totalidad a uno o varios delos procesos con bloqueados. Entonceslos procesos extraidos se reinician de forma normal desde el principio, la pérdida de la mayor parte(si no de la totalidad) del trabajo previamente realizado por éstos. 147687 PBg 11 2. COMUNICACION Y SINCRONIZACION ENTREPROCESOS Losprocesoscon frecuencia necesitan comunicarse otros con procesos. Cuandoun proceso del usuario desealeer el contenido de un archivo, este debe señalaral proceso del archivolo que desea. Después el proceso' del archivotiene que indicar'al proceso del disco que lea el bloque que se pide. En resumen, se necesita establecer comunicación entre los procesos, preferentemente en forma bien estructurada. Sin embargo, para que funcione apropiadamente un grupo de procesos, se deben sincronizar sus actividades de forma que se asegure la integridad de las relaciones de precedencia ". dictadas por el problema que se está resolviendo. La sincronización entre procesos es necesaria para preservar la integridad del sistemay prevenir problemas de tiempo producidos por el acceso concurrente a recursos compartidos por múltiples procesos. "Llamaremosproccsosccuettcial a alguna ocurrencia de instrucciones queejecuta se en una los llamaremos computadora. Cuando 'tenemos varios procesos ejecutandose al mismo tiempo, proccsos concurrc~css"(3). Los procesosconcurrentespuedencomunicarsepormediodela memoria compartida (variables globales),o enviando mensajes por medio de canales. Si los procesos concurrentes accesan.de manera segura a las variables compartidas, sin afectar a sus cooperadores (los otros procesos), los llamaremos "procesos concurrentes ajenos", pero si existe alguna afección (i.e. afecta el uso de las variables compartidas), los llamaremos ''procesos concurrentes cooperantes".' Que P1, P2, ..., Pn (Pi = Proceso i) sean ajenos quiere decir que cuando la variable com. partida es cambiada por el proceso Pi, la misma variable no puede aparecer en l a s intrucciones del proceso Pj (para cada i < > j). Esto significa 'que los procesos concurrentes ajeno pueden compartir variables globlales sin restricciones solamente cuando las usan para lecturas. Pero una vez que uno de ellos cambia el valor de la variable global, queda prohibido el acceso a ésta por los demás. PBg 12 2.1 Memoria Compartida Los procesos definidos por el sistema son creados comúnmentelos ensistemas operativos deprop6sitogeneralparasacarpartidode la posible concurrencia entre losdil'erentes programas o aplicaciones. Cuando es crítico el rendimiento, se pucdc dividir el trabajo en varios procesos un programa cooperantes definidos por el programador para explotar la posible concurrencia en o aplicación dada. Los procesos cooperantes típicamente comparten recursos que atañen al grupo entero (familia), Los recursos compartidos pueden ser los datos globales que abarca la familia o los dispositivos físicos que están permanente o temporalmente asignadosa la aplicación en cuestión. y sincronizar alos procesos que tienen memoria Analizaremos dos métodos para comunicar compartida: 2.1.1 semáforos Unade las soluciones mis fanosas y significanlesdelproblemadecooperación entre procesos paralelosfue la propuesta por Dijkstra, quien extractó las nociones clave de la exclusión mutua en suconcepto de semáforo. Un semáforo es una variable protegida cuyo valor puede ser (que P Y V como se verá más adelante). accedidoy alterado solamente por ciertas operaciones son Su solución introdujo un nuevo tipo de variables: - Un contador, - Una cola de procesos en espera (dormido)y - Dos funciones primitivas llamadasP y V. La operación P en el semáforo S, opera de la siguiente manera: P(S); { if ( D O ) S = S-1; else espcra en S: }: Pág 13 La operación V en el semáforo S, opera de la siguiente manera: V(S); { if (uno o más procesos están en espera en S ) deja proseguir a uno de estos procesos else S = s+l; }: Los semáforos y l a s operaciones de semáforos pueden implementarse en software o hardware, En general, se implementan en el núcleo del S.O., donde se controlan los cambios de estado de un proceso. La idea básica de la solución de Dijkstra esla suspensión de los procesos que no pueden entrar y su reactivación cuando algún proceso sale de la sección (5). Semiforos Binarios. Só10 pueden tomar dos valores,O y 1.Son manejadospor el proceso asociado a la siluaci6n crítica (llamados también "privados"). Semiforos Continuos. Pueden tomar valoresenteros no negativos. El entero asociado al semáforo representa el número de recursos disponibleso de procesos en la cola de espera. EXCLUSION MUTUA CON SEMAFOROS El problema de la exclusión mutua se puede resolver correctamente usando los semáforos y las operaciones P y V, pero el usuario tiene que cumplir las siguientes condiciones: 1. El valor inicial del semáforo es igual a 1 2. Entrar a la sección críticaejecutando P(S) 3. Salir de la sección critica ejecutando V(S) 147687 4. No usar operaciones P(S) y V(S) para otros propósilos El algoritmo sería el siguiente: Pág 14 SEMAFOROS (); /* El semiforo S es binario */ { S = 1; /* libre */ cobegin PROCESO-1; PROCESO-2; coend; 1; PROCESO-l(); { while (true) { P(S); sección-crítica: V(W; otras-cosas-Proceso-1 : }: }: PROCESO-20; { while (true) { P(S); sección-crítica; V(S): otras_cosas-Proceso-2; 1; 1; PROBLEMA DEL PRODUCTOR-CONSUMIDOK UTILIZAN110 SEMAFOKOS Definiciones: N es el número de runuras en el buffer S es el semábro para entrar a la sección-crítica. Se inicializa con 1. Vacío es el semáforo quecuenta las ranuras vacías del buffer.Se inicializa conN. Lleno es el semáforo quecuenta las ranuras completas del buffer. Se incializa con O. PBg 15 PRODUCTOR (); { while (true) { produce-elemento (&elem); P(Vaci0); P(S); coloca-elemento (elem); /* genera algo paracolocarlo en el buffer *I /* disminuir cl contco vacío */ /* meter la regióncrítica */ /* coloca el nvo. elemento en el buffer *I /* salir de la región critica */ /* incrementar el conteo deranuras repletas *I CONSUMIDOR (); { while (true) { 1; P (lleno); P(S); saca-elemento (&elem): V(S): V(Vacío); Consume-elem (elem): Consume-elem (elem); 1; /* disminuir el conteo repleto */ /* meter la región crítica */ /* tomar un elemento del buffer */ /* salir de la región crítica */ /* incrementar el conteo de ranuras vacías */ /* hacer algo con el elemento */ 2.1.2 monitores Otra solución no menos importante que la anterior (semáforos) para resolver el problema de la cooperaciónentre procesos paralelos esla que a continuación se presenta: MONITORES. "Un monitor es un conjunto dc procedimientos, variables y cstructuras de datos que se agrupan en un tipo especial de módulo o paquete"(6). También se considera como una con. strucción de concurrencia que contiene los datos y procedimientos necesarios para realizar la asignación de un determinado recurso compartidoo de un grupo de recursos compartidos. PBg 16 L o s procesos pueden llamar a procedimientos en un monitor siempre quelo deseen, pero no puedenaccesardirectamente l a s estructurasdedatosinternasdelmonitorapartirde procedimientos declarados fuera del monitor Los monitorcs ticnenun propiedad importante quelos hace útiles para lograr la exclusión mútua: sólo un proceso puede estar activo enun monitor en cualquier instante."Los monitores son una construcción de un lenguaje de programación, de manera que el compilador sabe que son especiales y puede manejar llamadas a procedimientos monitores en forma distinta a otras llamadas a procedimientos"(7). Comúnmente, cuando un proceso llama a un procedimiento si hay algúnotro procedimiento monitor, las primeras instrucciones del procedimientoverificarán otro proceso está utilizando el monitor, el proceso solicitante activo dentro del monitor.ningún Si puede entrar. Es tarea del compilador implementar la exclusión mutua en las captaciones del monitor, la persona que escribe el monitorno tiene que estar enterada de la forma en que el compilador se las arregla para lograr la exclusión mutua. Basta saber que al convertir todas l a s secciones críticas en procedimientos monitores, nunca dos procesos ejecutarán sus secciones críticas al mismo tiempo. MONITOR Ejemplo { i entero: c condicibn: procedimicnto PRODUCTOR (X): procedimiento CONSUMIDOR (X); Aunque los monitores ofrecen una manera sencilla de lograr la exclusión mutua, eso no los procesossebloqueencuandonopuedan basta,tambiénsenecesitaunamaneradeque l a s pruebas continuar. En el problema del productory consumidor, es bastante fiicil colocar todas -de buffer lleno y buffer vacío en procedimientos monitores, pero ¿Cómo se debe bloquear el productor cuando encuentre lleno el buffer? Pág 17 La solución yace en la introducción dc "variables dc condición", junto con dos operaciones que se realizan con ellas, WAIT y SIGNAL. Cuando un procedimiento monitor descubre que no puede proseguir (porejemplo, el productor encuentra lleno el buffer), realizauna operación WAITcon algunavariable de condición,por ejemplo,"lleno". Esta acci6n ocasionaque se bloquee el proceso solicitante. También permite que entre ahora al monitorotro proceso al que ya antes se le había negado la entrada. Este otro proceso, por ejemploel consumidor, puede desbloquear a su socio bloqueado realizando una operaciónSIGNAL con la variable de condición en la que esperasu socio. Para evitar que haya dos procesos activos en el monitor al mismo tiempo, se necesita una regla que señale lo que sucede después de una operaciónSIGNAL. Esta regla indica queun proceso que realiza una operación SIGNAL debe salir del monitor de inmediato. En otras palabras, una proposición SIGNAL sólo puede aparecer como proposición final un enprocedimiento monitor. PROBLEMA DELPRODUCTOR-CONSUM IDOR CON MONITORES MONITOR Productor-Consumidor (); { lleno, vacio condicion; cont entero; procedimien to Coloca; { if cont = = N) SJAIT (lleno); produce-elemento; cont = cont+l; il(cont = 1) SIGNAL (vacio); }; procedimiento Remueve; if (cont = = O) WAIT (vacio); saca-elemento: cont = cont - 1: if (cont == N-1) SIGNAL (lleno); 1; cont = O; 1 MONITOR; PBg 18 PRODUCTOR (); { while (true) { 1; roduce-elemento; Froductor-ConsumidorColoca; }; CONSUMIDOR (); while (true) { 1; Productor-Consumidor.Remueve; consume-elemento; }; 2.2 Envio y Recepcih de Mensajes Desde que la sincronización y comunicación entre procesos es necesaria para soportar la ejecución de procesos concurrentes, es deseable integrar las dos funciones en un mecanismo ímico. Los mensajes son un mecanismo relativamente sencillo que encaja en la sincronización y comunicación entre procesos en entornos centralizados, así como distribuidos. El envío y la recepcióndemensajeses unaformaestándardecomunicación entre puestosenredesde computadoras, haciéndolomuy atractivo para argumentar esta facilidad, así como proporcionar las funciones de comunicaciónentre procesos. En escencia,"un mensaje esuna colección de información que se puede intercambiar entre un proceso emisory uno receptor"(6). Un mensaje puedecontener datosy órdenes de ejecución o incluso algún código transmitido entre dos o más procesos. Por ejemplo los mensajes se usan I'rccucntcmcntc cnsistcnlasdistribuidosparatransferirgrandcsproporcioncs de sistcma operativo ylo programas de aplicación para modos remotos. Phg 19 En general, el formato de mensaje es flexible y negociable para cada par específico de emisor-receptor. Se puede pensar en un mensaje como caracterizado por su tipo, longitud ID del transmisor y receptor, y un campo de datos: ID del transmisor cabecera del mensaje Cuerpo del mensaje (opcional) Divide el contenido del mensaje en dos campos separados: cabecera del mensaje y cuerpo del mismo. El cuerpo opcional del mensaje, cuando está, típicamenta contiene el mensaje real, y su longitud puede variar de mensaje a mensaje. 2.2.1 implementaciiin del mensaje Las operaciones típicasde mensajes que el sistema operativo puede daro predeclarar en un lenguaje de implementación de sistema son "transmitir" un mensaje y "recibir" un mensaje. La implementación de mensajes puede diferir en una serie de detalles que, entre otras cosas, afectanal funcionamiento y parámetros de l a s operaciones transmite y recibe. Varios de los problemas importantes en la implementación de mensajes son: l. Designación 2. Copia 3. Almacenamiento Intermedio 4. Longitud PBg 20 DESIGNACION Una del a s decisiones más importantes cuando se disefia una facilidad de mensajes es si la designación seria directa o indirecta. Por "dcsignación directa", entcndercmos que siempre que se llame a una operación de mensaje, cada transmisor debe designar el recipiente específicoy, recíprocamente, cadareceptor debe nombrar la fuentedc la que desea recibirun mensaje. Por ejemplo: proceso-A; ... transmite (B, mensaje); e.. proceso-B: ... recibe (A, mensaje); La asignación unoa uno producida proporciona una comunicación segura de mensajes lejos de confundir identidades,pero puede serun incoveniente parala implementación de rutinas de servicio. Por ejemplo, un controlador de impresora4rviendo al sistema completo es de poco uso si debe saber los nombres de todos sus clientes y especificar siempre el particular desde donde viene la próxima orden de trabajo. los Unmétodoalternativoeslacomunicacióndemensajesllamada"indirecta"donde mensajes se envían y reciben desde depósitos especializados dedicados a ese propósito.Estos recipientes se llamannormalmenteBuzones,debidoa su formadefuncionamiento(9). Por ejemplo, si el proceso A deseaenviar un mensaje al proceso B a través de Buzon-1, pueden ser necesarias las siguientes sentencias: proceso A: ... transmite (Buzon-1, mensaje); ... proceso B; ... recibe (Buzon-1, mensaje); 147681 PBg 21 COPlA Por definición, "el intercambio de mensajes ente dos procesos, transfiere el contenido del tnensaje desde el espacio de direcciones del transmisor al receptor"( 10). Esto se puede conseguir copiando el mensaje completo en el espacio de direcciones receptor dcl o simplemente pasando un puntero al mensaje entre los dos procesos, en otras palabras, el paso del mensaje puede ser por valoro por referencia. Los mensajes copiados consumen memoria y ciclos de CPU.La comunicación asincrónica de mensajes ylo los esquemas de protección de memoria pueden necesitar que cada mensaje primero se copie desde el espacio del transmisor laa memoria intermediadcl sistema operativo y desde allí posteriormente se copia al espacio del proceso receptor: doble copia para enviarun solo mensaje. Una consecuencia de tener una copia única del mensaje es que mientras el proceso receptor está usando el mensaje, el transmisor no puede modificar ninguna parte de él. ALMACENAMlENTO INTERMEDIO La pregunta es si los mensajes enviados pero no recibidos todavía deberían ser almacenados o no. Es decir, si el sistema no almacena temporalmente los mensajes emitidos, el transmisor y el receptor deben estar activos y buscando intercambiar un mensaje para que tenga lugar una transferencia. La comunicación transmisor-receptor, cuandono se almacenan los mensajes, es síncrona en sentido de que puede tener lugar sólo entre dos partes que quieran el cambio activamente. un par transmisor-receptor. Consecuentemente, alo más un mensaje debe emitir a la vez por La ventaja de este mecanismo síncrono de envía-recibe mensaje son sus procesos suplementarios comparativamente bajosy la f k i l implementación. Una desventaja es la sincronización forzosa de la operación de transmisores y receptores, Unaalternativa,almacenamientointermediodemensajes,permite elfuncionamiento asíncrono de transmisoresy receptores. Si los receptores no están esperando,un emisor manda . Bu mensaje al sistema operativo para el envío posterior al reccptor. Pág 22 Como el sistema operativo aceptay almacena temporalmente los mensajes enviadospero su ejecución después de enviar un mensaje y no necesita no recibidos, un proceso puede continuar los receptores. suspenderse, despreocupándose de la actividad de Un problema relacionado, común para ambas implementaciones, es el de laposposición indefinida. Esto pasa cuando se envía un mensaje, pero nadielo recibe, es decir, debido a quiebra del receptor, o cuando un receptor está esperandoun mensaje que nunca se produce. Dos formas comunes de conducir este problema son la versión no bloqueada (sin espera) de la primitiva RECIBE y una implementación de espera temporizada deRECIBE. El no bloqueo esuna forma especial de la primitiva RECIBE que es soportada en algunos sistemas para permitirrecibir un mensaje si se está disponible,pero sin esperar si no lo está. Unaaproximaciónalproblemamásdirecta, pero más compleja, es proporcionar una facilidad de establecer un límite de tiempo durante el cual se debe complctar un intercambio concreto de mensaje. Esta necesita una secuencia modificada de llamada de las operaciones de mensaje, por ejemplo: recibe (buzón, mensaje, tiempo-límite) LONGITUD El problema es si los mensajes deberían ser de longitudfija o variable. Este problema no es de gran importancia en sistemas dondc el paso de mensajes sc hace a través de punteros, ya que se puede proporcionar un tamaño diferente de ventana para cada transmisión incluyendo un parámetro Único, "tamaño-ventana", en el propio mensaje. Usualmente los mensajesdetamaño fijo producenunamenorcantidaddeprocesos suplementarios al permitir que las memorias intermedias correspondientes del sistema sean de tamaño fijo, lo que hace muy sencilla y eficaz su asignación. El problema es que los mensajes, y dividirlosen pedazos cuando se usan paracomunicación naturalmentevienen en varios tamaños, pequeñosdetamaño fijo producefrecuentemente un procesosuplementarioadicional. La alternativa,mensajesdetamañovariable,aliviaestosproblemascreandodinámicamente memorias intermedias paraencajar el tamaño de cada mensaje. PBg 23 PROBLEMA DEL PRODUCTOR-CONSUMIDOR (VERSION DE ALMACENAMIENTO LIMITADO CON MENSAJES) En vez de tener unamemoria intermedia únicaglobal para todoslosprocesos, se distribuyen sobre los mensajes porcionesindividuales de memoria intcrrnedia. Se supone que el campo de datos está presente en cada mensaje y dimensionado de forma que sea capaz de guardar un elemento Único producido. Para intercambiarmensajesentreproductores "Puede-Prod" y "Puede-Cons''. y consumidoresseusandosbuzones, Se supone que cada proceso productor coge un mensaje del buzón "Puede-Prod". Después de llenar el mensaje con el elemento producido, el productor envia el mensaje al buzón "Puede-Cons"para su construcción. Un procesoconsumidorquita un mensajedelbuzón"Puede-Cons",consumeelelementocontenido en 61 y devuelveelmensajevacíoalbuzón "Puede-Prod". Definiciones: "mensaje" "capacidad" "nulo" llill es un registro es la capacidad de almacenamiento cs cl lncnsaje vacío es un entero MENSAJES-PRODUCTORES-CONSUMIDORES (): { Crea-Buzón (Puede-Prod); Crea-Buzón (Puede-Cons); for (i = O, i capacidad,transmite(Puedc-Prod,nulo)) cobegin PRODUCTORES (); CONSUMIDORES (): coend; 1; PBg 24 PRODUCTOR (); { while (true) { recibe (Puede-Prod, pmsg); pmsg = produce; transmite (Puede-Cons, pmsg); otrosgrocesamientos; /* pmsg es una variable local de tipo nlensajc */ }; 1; CONSUMIDOR (); { while (true) recibe (Puede-Cons, cmsg); consume (cmsg); transmite (Puede-Cons, cmsg); otrosgrocesamientos; /* cmsg es una variable local de tipo mensaje */ }; 1; 2.2.2 modelos En esta parte discutimos cuatro modelos básicos de envíoy recepción de mensajes: a) Mensajes punto a punto b) Rendezvous c) Llamada a procedimientos remotos d) Mensajes uno a muchos MENSAJES PUNTO A PUNTO Es el modelo más elemental y el más utilizado. Este modelo involucra dos partes: el emisor y el receptor. Pág 25 I I El emisor inicia la interacción explícitamente; por ejemplo, envía un mensaje o invoca a un procedimiento remoto.Por el otro lado, la recepción del mensaje puede ser implícita o explícita. Si la recepción es implícita, el receptor recibe el mensaje y qué acciones tomará cuando el mensaje llegue. Si la recepción es explícita, el receptor puede estar en diferentesy estados recibir diferentes tipos de mensaje. El envío y recepción de los mensajes puede ser síncrono o asíncrono; si es síncrono, el elnisor al enviarun mensaje se bloquea hasta que el receptor lo recibe. Si es asíncrono, el emisor no necesita bloquearse al enviar el mensaje, aún cuando elreceptor no lo haya recibido aún. RENDEZVOUS Se basa en 3 conceptos: - Declaración - Llamada Aceptación La declaración y la aceptación son parte del emisor. La declaración es sintácticamente parecida auna declaración de procedimiento,la llamada es similara llamar a un procedimiento. La aceptación puede contener una lista de sentencias que serán ejecutadas cuando la entrada sea llamada, ej.: accept incr (x:integer;y:out integer) doy:= x + 1; end: LLAMADA A PROCEDIMIENTOS REMOTOS Es similar a una llamada de procedimiento excepto que el solicitante diferentes procesos. y el receptor son Cuando un proceso S llama a un procedimiento remotoP de un proceso R,losparámetros de entradasuplantados por S son enviadosa R.Cuando R recibe la solicitud invocada, éste ejecuta el código deP y entonces pasa cualquier parámetro de salida S. a Pbg 26 3. CONCLUSIONES Se ha visto que el estudio de la programación concurrente, presenta dos aspectos importantes que debemos considerar:los procesos y sus interacciones, y la comunicación y sincronización entre los mismos. AI analizar los procesos y sus interacciones, se presentan varios problemas, tales como: la perdida de integridad de lasvariablesque comparten varios procesos, es decir, el uso incontrolado de las variables compartidas por tales procesos, así como la ocurrencia de situaciones llamadas "abrazos mortales",en los cuales los procesos se bloquean mutuamente. Por consiguiente se han desarrollado soluciones a dichos problemas; tales como la "excl- usión mutua", o "bloqueo/desbloqueo",entre otras. Por otro lado, la comunicacióny sincronización entre procesos también presenta problem a s ; los procesos necesitan establecer comunicación entre ellos y para ello seexponen dos esquemas de comunicación: memoria compartida y envío y recepci6n de mensajes. AI estudiar estos aspectos nos damos cuenta que la programación concurrente no es un tema fácil de dominar, debido a que presenta problemas de implementación algo complejos, además de serun tema de profunda investigación. Tarnbién se puede concluir que en un futuro cercano exista la tendencia hacia el multiprocesamiento, ya que el costo y el tamaño delos procesadores es cada vez menor,y Csto implica que se puedan colocar varios procesadores trabajando juntos y así llevar a cabo un verdadero paralelismo. PBg 27 NOI’AS 1. Harvey M. Deilel. Introducciona los sistemas operativos, pp. 80. 2. Milan Milenkovic. Sistemas operativos. conceptosv diseño , pp. 102. 3. Hanna Oktaba. “Programaciónconcurrente”, Comunicaciones técnicas, pp. 4. 4. Harvey M. Deitel. OD. cit. ,pp.91. 5. Milan Milenkovic. Opcit. ,pp.125. 6. Andrew S. Tanenbaum. Sistemas operalivos, diseñoe implementación ,pp. 67. 7. Ib., pp.68. 8. Henri E.Bal. ProcramminP lanrluages for distrihuited computine svstems,pp. 87. 9. Hanna Oktaba. Op. cit., pp 39. 10. Henri E. Bal. OD.cit,, pp. 101. BIBLIOGRAFIA Ba1,Henri E. (1989) Prolrrammine laneuarrcs for distributcd cotnDutinrr , svstems .Ed. ACMComputing Surveys, E.U., 356 pp. Deite1,Harvey M. (1990) Introducción a los sistemas operativos, Ed.Addison-Wesley ,México, 673 pp. Milan,Milenkovic.(l988)Sistemas Operativos. conceptosv diseño, Ed. Mc Grawn Hill ,México, 486 pp. Oktaba,Hanna.( 1985) "Programación concurrente", Comunicaciones Técnicas ,(México) IIMAS UNAM, 112 pp. Tanenbaum, AndrewS.( 1988) Sistemas Operativos. diseño e implementación, tr. J.C. Vega Fagoaga ,Ed. Prentice Hall, México, 733 pp. UNIVERSIDAD AUTONOMA METROPOLITANA IZTAPALAPA . CIENCIAS BASICAS E INGENIERIA PROYECTO DE INVESTIGACIONII DISEÑO E IMPLEMENTACION DE UN ' .MINILENGUAJE DE PROGRAMACION CONCURRENTE ALUMNA:LETICIA ILLESCAS SERRANO ASESORA: M. C. ELIZABETH PEREZ CORTES TRIMESTRF. 92-P ' MEXICO, D.F. CONTENIDO INTRODUCCION 1 1. MODELO DEL PARALELISMO 2 2. DEFINICION DE 4 3. EL COMPILADOR LA GRAMATICA 3.1 Analizador Lerricogrhfico 3.2 Analizador Sintktico 33 Analizador Semhtico 3.4Generadorde C6digo Intermedio BIBLIOGRAFIA PROGRAMAS FUENTE 7 8 14 INTRODUCCION Este proyecto tiene como objetivo principal el diseño e implantaci6n un de minilenguaje de programaci6n paralela, ademb de desarrollar todo un ambiente de ejhci6n, que consta de un editor de programas, un editor de laberintos,un compilador,un indrprete, un depurador y algunas utilerías. se parte de una idea inicial donde empezamos por definir con que Para realizar todo este trabajo, un mundo que contiene universo vamosa trabajar.Esto es: existeun robot llamadoKAREL el cual vive en laberintosy trompos, KARELpuede detectar dichos trompos,tomarlos o dejarlos,tambihpuede detectar y por último posee una brújula para orientarse. paredes (laberintos) para no chocar con ellos, La idea final es construir un mundo en el que puedan convivir = varios L.'s al mismo tiempo y aún m b que puedan comunicarseentre ellos. E n tomo al ambiente de ejecuci6n, se desea tener un conjunto de herramientas con las cualesse pueda realizar desde la edici6n del programa hasta el ejecucidn del mismo. El Editor De Programas es un editor de textos que permite al usuario introducir los programas fuente que posteriormentes e r h ejecutados. El Editor de Laberintos permiteal usuario editar sus propios laberintos para el mundo deKAREL. El Compilador verifica un programa fuente, si no ocurre algúnerror durante la verificaci6n entonces genera un archivo objeto. El Interpretetoma el archivo objeto generado por el compilador y lo ejecutainstruccidn por inStNWi6n. El Depurador permite correr paso a paso un programa del ukrio,y verificar el estado en que se encuentra dicho programa cada vez que se ejecuta una instruccibn. Ya que se tiene un panorama general de lo que se desea realizar, ahora lo primero que se debe aimplantar, una vez definido el modelo se define la gramAttica definir es el modelo del paralelismose va que del lenguaje y posteriormente se irnplementa cada parte del ambiente de ejecuci6n mencionado anteriormente. Pbg 1 1. MODELO DELPARALELISMO E n esta partese define cualser& el modelo del paralelismo que se va a implantar, para dicho modelo se deben definir las siguientes partes: 1) UNIDAD DEL PARALELISMO. E n un entorno de paralelismo existen varias unidadesejecuthdose al mismo tiempo, para nuestro modelo vamos a utilizar como unidades de paralelismoPROCESOS. a los Cuando se activen los KAREL's,cada uno dar6 origen a un proceso,estos procesos s e r h conjuntos de ordenes quese e j m t a r h al mismo tiempo. 2) SINCRONIZACION Y COMUNICACION. La comunicaci6n que establecerh los KAREL'sserl por medio de MENSAJES. Dentro delos mensajes se envian señales de tipo 16gico que cadaKAREL interpreta. Estos mensajesson 6rdenes que Forman parte del lenguaje,son dos tipos de mensajes; uno que envia y otro que recibe señales. La especificaci6n es: para tales mensajes ENVZA (receptor ;señales ) y RECIBE (emkor ;señales ) El receptor es el KAREL que recibe l a s señales y el emisor es elKAREL que envial a s señales. Las señales puedenser variables declaradas de tipo 16gic0, o l a s constantes V y F. Otro parhetro que se debe definir es la sincronía de la comunicaci6n, los mensajes s e r h sincronos, es KAREL decir,si un KAREL envia un mensaje aotro ,Qte no podrh continuar con sutarea hasta que el receptor haya recibido el mensaje completo 3) ACI'IVACION. La activaci6n en paralelo de los KAREL's se va a indicar por medio de una orden. Para nuestro modelo la orden ser& EN-PARALELO PBg 2 4) CONTROL Y EXPRESION DELNO DETERMINISMO. El no determinismo surge cuando varias partes del proceso son candidatos a ser ejecutadas y solo una de ellas debe efectuarse, para expresar el no determinism0 dentro de nuestro lenguaje introducimos una orden llamada ALTERNATIVA cuya especificaci6n es: ALT: cuerpo FIN El cuerpo es una secuencia de custodiasy acciones, dondel a s custodias son expresiones condicionales y l a s acciones son instrucciones que se deben ejecutar si la custodiase cumple. De alguna manerase debe tener control sobre el no determinismo, de tal manera que pueda elegirse una de todas l a s custodias que son candidatos a ejecutarse. El contro que se establece para nuestro modelo es el siguiente: se cumplen, Se evalúan simultheamente todas l a s custodias y luego se determinan cuales son las que y esa es la que se ejecuta. posteriormentese elige una de ellas aleatoriamente 147687 PBg 3 2. DEFINICION DE LA GRAMATICA. Programa ::= PROGRAMA id bloque-tareasprincipal I bloque-tareas ::= bloque-tareasuna-tarea una-tarea ::= KAR número una-tarea = decl-varbloque-def INICIAsecuenciaTERMINA dec-var ::= VAR lista-var Ie I una-var lista-var ::= lista-varuna-var una-var ::= SENALlista-id lista-id ::= lista-id ; , id I id principal ::= EN-PARALELO llamadas llamadas ::= llamadas . , una-llamada I una-llamada una-llamada ::= KAR número bloque-def ::= bloque-defdefinici6n I e definici6n ::= APRENDE id = secuencia FIN id I inStNcci6n secuencia ::= secuenciainStNCCi6n inst~cci6n::= inst-elem selecci6n I ciclo-mientras I ciclo-repite I id I alternativa I asignacion ENVIA(receptor ;lista-id /'A I lista-ctes) I RECIBE( emisor ;lista-id ) c&pibr eo c b , vLyJ enva5 4~d w, c ( ~ I I RELOJ ( número ) lista-ctes ::= lista-ctes ,constante I constante .~ s ~ constante ::= V IF receptor ::= KAR número emisor ::= KAR número inst-elem ::= AVANZA I WELTAIZQ I WELTADER I RECOGEOBJETO I DEJAOBJETO I PIDEOBJETO I DEVUELVE OBJETO ciclo-mientras ::= MIENTRASexp-cond HAZ secuencia bIN ciclo-repite ::= REPITE secuencia HASTAexp-cond seleccidn ::= SI exp-condENTONCESsecuencia FIN I SI exp-condENTONCESsecuencia OTROsecuenciaFIN exp-cond ::= exp-cond Y exp-cond (exp-cond) I NO--cond asignacidn ::= id I id:= I exp-cond O exp-cond I I condicion := id I id := constante I id := NOid Noconstante alternativa ::= ALT : cuerpo [ gllg,f)&$@&@~ppJFIN cuerpo ::= cuerpoaccidn acci6n ::= custodias -> secuencia [I custodias ::= custodias NO custodias I I acci6n . Y custodias I custodias O custodias I ( custodias) I una-custodia PBg 5 una-custodia ::= condici6n I RECIBE ( emisor ;lista-id ) . condici6n ::= PAREDENFRENTE PAREDIZQUIERDA PAREDDERECHA I OBJETOSUENA NINGUNOBJETO id = constante id = id I I NADAENFRENTE I I NADAIZQUIERDA I I NADADERECHA I NADASUENA I ALGUNOBJETO I I DIRECCIONNORTE I id <> constante I id <> id id ::= letra ( letra I dígito ) * constante ::= V . IF número ::= ( dlgito ) + - letra ::= [ 'a' 'z' 'A' - 'Z' ] digit0 ::= [ O - 9 ] P4g 6 3.1 Analizador Lexicográfico. El analizador lexicogr&fico esta hecho a traves de un programa llamado LEX del cual se da una explicaci6n a continuaci6n: Lex es un generador de programascapaces de realizar el procesamiento lexica de archivos texto. Lex recibe como entrada un conjunto de expresiones regulares y produce como salida un programa escrito en algún lenguaje de programacidn de prop6sito general capaz de reconocer dentro de un archivo de por cada caracteres las secuencias de slmbolos que forman cadenas pertenecientes al lenguaje denotado expresibn regular. Cada expresi6n regular tiene asociado un conjunto de acciones que deben ser realizadas cada vez que una cadena con la forma indicada por la expresi6n regular sea encontrada en la entrada. LEX es denominadoyylex() ,y esta escritoen lenguaje C. El analizador 1exicogrAfk.o generado por Este programa es quien le devuelve al analizadorsintktico unidades sintkticas llamadas tokens. 3.2 Analizador Sintáctico * .. El analizador sintktico esta hecho a traves de un programa llamado explicaci6n a continuaci6n: YACC del cual se da una YACC es un generador de analizadores sintkticos que recibe como entrada una gramAtica (almacenada en un archivo texto)y produce como salida el analizadorsintktico ascendente que reconoce las estructuras definidas por las producciones de la gramtltica. YACC transforma la especificaci6n que el usuario le proporciona en un programaescrito en lenguaje C; este programa es capaz de analizar la entrada y determinar si ;st& formada según las producciones indicadas en la especificaci6n. El analizador sintktico producido por YACC, contiene una funci6n llamadayypurse(), la cual es invocada para realizar el aniilisis sintktico de un programa fuente. 3.3 Analizador Sernántico E n esta partese realizan dos tipos de chequeo, el de tipos y el de unicidad. Mediante elchequeo de tipos se revisa que las partes que se relacionan entresí sean del mismo tipo,por ejemplo,en una asignacidnse checa que los dos identificadores sean del mismo tipo señal. Este chequeo se vuelve demasiado sencillo debido a que tenemosun solo tipo de variables. P6g 7 Mediante elchequeo de unicidad se verifica queun identificador sea utilizado para una misma funci6n dentro del programa, por ejemplo, el nombre el programa no puede ser utilizado como nombre de una tarea, de una definici6no de una variable.Este chequeo es un poco m h fuerte que el detipos, ya que se presentan mas posibilidades de utilizar los identificadores en distintas partes del programa. 3.4 Generador De Códio Intermedio En esta parte se define cual es el &digo que produce un programa fuente correctamente escrito despub de pasar por el compilador.El c6digo generado es c6digo de tres direcciones representado por cutidruplos con la siguiente estructura: ( OP, dl,d2,d3 1 Donde op es el operador quese aplica, dl es donde quedael resultado d2 es el primer operando d3 es el segundo operando se le asigna un cuAdruplo de c6digo intermedio,que se muestra a continuaci6n: A cada instrucci6n a) INSTRUCCION ELEMENTAL Jnstrucci6n Re~resentacibnen c6dino Avanza VueltaIzq VueltaDer Recogeobjeto Dejaobjeto Pideobjeto Devuelveobjeto PBg 8 b) INVOCACION (Cuando se llama a un Aprende ) Representad611 en &digo Instrucci6n Invocamos a l aprende llamadoP ( U P , - , - ) c) CICLO MIENTRAS Re~resentaci6nen &digo hStNcci611 MIENTRAS HAZ Se traduce asi: uno: (exp_cond> Si x = falso goto dos goto uno dos: - (PUNTOS,uno,-, ) (FALSOAgoto,dos) (GOTO,uno, -, ) (PUNTOS,dos,-,- ) - d) CICLO REPITE InStNcci6n Re~resentaci6nen &digo REPITE HASTA Se traduce asi: uno: Si x = falso goto uno - (PUNTOS,uno,-, ) (FALSO,x,goto,uno) PBg 9 e) RELOJ Instrucci6n Reloj ( ) Re~resentaci6nen &digo (RELOJ,num, -,- ) f) ASIGNACION x:= y x:= NOy g) SELECCION Instrucci6n Re~resentaci6nen &digo SI ENTONCES OTRO Se traduceasi: Si x = falso goto uno ; goto dos uno: dos: (FALSO,x,goto,uno) (GOTO,dos, -,- ) (PUNTOS,uno,-,- ) (PUNTOS,dos,-,- ) SI ENTONCES Se traducea i : PBg 10 Si x = falso goto uno uno: (FALSO,x,goto,uno) (PUNTOS,uno,-,- ) h) CONDICION Instrucci6n Reoresentaci6n en cddieo = (IGUAL,x,idl,id2) <> (DIST,x,idl,id2) ParedEnfrente Nadanfrente ParedIzquierda NadaIzquierda ParedDerecha NadaDerecha Objetosuena NadaSuena AlgunObjeto NingunObjeto DireccionNorte i) ENVIA Instrucci6n Envia (receptor,x,y,...4) Re~resentacidnen &digo (ENVIA,receptor,x,-) (ENVIA,receptor,y,- ) ... (ENVIA,receptor,z,- ) j) RECIBE Instrucci6n Re~resentaci6nen c6dipo Recibe (receptor,x,y,...4) (RECIBE,receptor,x,- ) (RECIBE,receptor,y,- ) ... (RECIBE,receptor,z,- ) k) ALTERNATIVA ReDresentaci6n en c6dino ... -> FIN Se traduceasi: uno: goto sigue dos: . goto sigue (PUNTOS,uno, -,- ) (GOTO,sigue,-,- ) (PUNTOS,dos, -,- ) (GOTO,sigue,-,- ) ... (PUNTOS,N,-,- ) l ... N: csecuenciaN> goto sigue ... (=Tfl, -) (FALSO,i,goto,i) (PUNTOS,sigue,-,- ) -9 ... ccustN> ALEATORIA(xl,x2,...a) Si i=falso goto i sigue: 1) PRINCIPAL Instruccidn Representacidn en &digo EN-PARALELO Karl,Kar2, ...,KarN ... (ACIIVA,KarN,- ,- ) Piig 13 i I , c BIBLIOGRAF'IA Ahofifred V. y coautores.(l990) Comoiladores. Princiuios, Flores S. y Pere tCcnicas y herramientas, tr. Pedro Botella i L.,Ed. Addison-Wesley Iberoamericana, (E.U.A.),805 pp. ' Manual de usuarioLEXv YACC; Oktaba ,Hanna.(1985) "ProgramacionConcurrente",Comunicacines t&nicas, (M6ico) 1 1 UNAM, 112 pp. PBg 14