a.i.f

Recuerda postear como 'apuntesum' que luego tienes que volver a escribirlo todo dos veces, jojoy.

[apuntesum-blog]

Compiladores: Bison

DEFINICION Y USO: BISON

Bisón es un generador de analizadores sintacticos LALR. Si la gramatica es ambigüa Bison es capaz de tratar de solucionarla siguiendo una cierta prioridad en las reglas que conoceremos mas adelante.

La estructura del fichero sera:

Programa file.y ->(bison)-> file.tab.c file.tab.c ->(compilador de C)->a.out entrada ->(a.out)-> salida

FORMATO Y DECLARACIONES

Al igual que FLEX, Bison se divide en tres partes en un fichero.y:

{declaraciones}

%%

{reglas}

%%

{rutinas de apoyo en C}

Declaraciones

Las declaraciones en C: Se realizan entre los simbolos '%{' y '}%'. Todo lo que esté en dichos simbolos se tratan como codigo C puro.

Declaraciones de componentes lexicos: El simbolo inicial, los tokens...

Otras declaraciones: Asociatividad y precedencia para que, en caso de una gramatica ambigüa puedan definirse que reglas van antes que otras.

Reglas: Cada una de ellas consta de una produccion de la gramatica y una accion semantica a dicha regla.

Si definimos una regla como <lado_izquierdo> -> <p1>|<p2> en bisón se traduciría como

<lado_izquierdo>: <p1>   {accion semantica 1}  | <p2>;   {accion semantica 2}

En la seccion de reglas, un caracter simple entre comillas 'c' se considera como un simbolo terminal. No obstante es mejor hacer uso de declaraciones de tokens para poder devolverlos por la salida y seguir la traza de ejecución. Un caracter sin comillas de letras y digitos y no declarados como componentes lexicos, son simbolos no terminales.

El primer simbolo no terminal del lado izquierdo se considera el inicial, pero podria declararse en la parte de declaraciones cualquier otro como %start simbolo.

Asi pues: E: E '+' E; podria verse como E: E MAS E si tenemos el token MAS. Bison, además, con los tokens genera el fichero .h con todos los defines que necesitaria el léxico y el propio sintáctico por lo que podemos ahorrarnos ese fichero simplemente haciendo usando el fichero "nom.tab.h"

ACCIONES SEMANTICAS

Las acciones semánticas se realizan en C, donde $$ se refiere al valor del atributo asociado con el simbolo que este en el <lado_izquierdo>. Por otra parte $i hace referencia al numero de otros simbolos que estan en la parte derecha. Asi para la regla:

T: E '+' D;

$$ Hace referencia al valor de T

$1 Hace referencia al valor de E

$3 hace referencia al valor de D

$2 Hace referencia al valor de '+', al ser un token, no se tiene en cuenta porque no nos hace falta en este caso.

Si dijeramos que es una regla para sumar dos numeros podriamos decir que:

T: E '+' D; {$$ = $1+$3;}

Por defecto, si no ponemos nada, estamos diciendo $$=$1; no obstante pueden colocarse reglas en medio de una declaracion si fuera necesario. Pero esto 'crea' un nuevo estado intermedio vacio.

T: E {$$=$1;} '+' E {$$=$1;}; T: E A'{$$=$1;} '+' EB'{$$=$1;} A': λ {$$=$1;} B': λ {$$=$1;}

RUTINAS DE APOYO EN C

Hay que proporcionar un analizador lexico (yylex()) que produzca los componentes lexicos, cuyos valores (de los que hablamos anteriormente) se comunican con la variable yylval.

Los blancos, tabuladores y saltos de linea son ignorados, y pueden haber comentarios entre /* */.

EJEMPLO DE FICHERO BISON

Dada la gramatica siguiente gramatica, construir las reglas basicas para que sea valido por bison.

%token digito mas por pi pd

%%

entrada : /*vacio*/

| entrada linea /*empiezo*/

;

linea: E /*leo la linea y traduzco la gramatica*/

;

E: E mas T

| T

;

T: T por F

| F

;

F: pi E pd

| digito

;

FLEX Y BISON

Flex genera una funcion yylex(), que es llamada por el programa principal de Bison, por lo tanto, cada regla flex que devuelva tokens validos tiene que terminar con "return(token);". La interaccion se realiza de la siguiente forma:

Tambien puede compilarse el fichero de salida de Bison poniendo "#include "lex.yy.c" " en la primera seccion de Bison entre '%{' y '}%'. Sería importante usar la opcion -d para que bison genere el 'fichero.tab.h' que contiene los defines de todos los tokens, por lo que tendriamos que poner en el fichero lex '%{ #include "fichero.tab.h" }%'

EL PARSER

Bison trabaja como una maquina de estados finitos con una pila. El analizador léxico es capaz de leer y recordar el siguiente token de entrada. El estado actual es siempre el tope d ela pila, los estados vienen etiquetados con enteros pequeños e inicialmente está el 0.

La maquina puede hacer cuatro acciones: desplaza (shift), reduce (reduce), acepta (accept) y error(error).

Ademas nos diría los errores que se producen, si hay conflictos y todo. Respecto a las ambiguedades hay de dos tipos, la que se basan en precedencias y las que se basan en conflictos en la tabla.

CONFLICTOS EN LA TABLA

Cuando hay conflictos shift/reduce Bison siempre trata de desplazar, pues reducir no solucionara el conflicto. Sin embargo, ante reduce/reduce escogerá la regla primera que tenga.

Por lo que tecnicamente no tenemos que preocuparnos de estos errores pero si de la ambigüedad por preferencia. Si tuvieramos una gramatica que dado un termino  puede ser una suma, una resta, una multiplicacion o una división y todas tienen las mismas prioridades, nos daremos cuenta de que nos interesa (cuando hacemos el arbol sintáctico) que la precedencia va por el lado izquierdo por convenio.

Asi pues si tengo operaciones de suma, resta, multiplicacion, division...

%left MAS MENOS %left POR DIV

Asi pues las que estan mas abajo son las que mas prioridad tienen, ¿pero que pasaria si tuviera un menos pero que no fuera una regla?

E: MENOS E;

Tendria que tener mas prioridad porque segun nuestras reglas aritmeticas el -3 ha de arrastrarse. Pero no podemos cambiar la gramatica, asi que podemos darle, manualmente mas precedencia.

%left MAS MENOS %left POR DIV %left UMENOS

E: MENOS E; %prec UMENOS;

Al leer si bison encuentra la misma precedencia, se fija en su asociatividad. Si la precedencia es por la izquierda, reduzco, si es por la derecha desplazo. Si la entrada tiene mas preferencia desplazo y si no, reduzco.

Las declaraciones de asociatividad eliminan los fallos de Bison por la salida por lo que, si hay fallos, no lo sabremos.

CARACTERITICAS AVANZADAS

Dada la sentencia X=4+3 bison analiza y ve que es correcta, sin embargo, si no se definió antes el identificador, es capaz de devolver el error con yyerror o abortar con yyabort.

ACCESO A LAS VARIABLES DESDE LAS REGLAS

Suponiendo que tengo una gramatica para el lenguaje tal que:

sent: adj noun verb adj noun

Y quiero prohibir que el adjetivo "young" vaya con el nombre "crowe" (es decir, que una bruja no pueda ser joven) puede manipularse el contenido de la pila con un puntero. Si sabemos exactamente que hay en la pila podemos saber que puntero usar. El actual es siempre $1 pues es el primero de la regla, si quisiera referirme a lo que hay tras el tendria que ver cuantos hay en la pila, el segundo sería $0, el tercero $-1...

Asi que suponiendo que la pila está vacio y meto YOUNG CROWE tendriamos:

YOUNG -> adj(YOUNG) -> CROWE adj(YOUNG) -> noun(CROWE) adj(YOUNG)-> ...

Podria ponerlo en bison como:

noun: CROWE | {if ($0==YOUNG) printf("A crowe cannot be young\n"); $$=CROWE;}

TIPOS ARBITRARIOS

Por defecto bison acpeta en el valor de los atributos yylval enteros. Pero podriamos poner lo que quisieramos. Para eso está el tipo %union.

En la seccion de declaraciones podemos decir:

%union { char * nombre; int ent;} %%

Si quisieramos declarar los tokens 'CADENA' 'NUM' 'C' y 'B' habria que especificar, o bien en la declaracion del token o bien en la regla, el tipo particular que tendrá, no obstante para $$ siempre habra que especificarlo:

%union { char * nombre; int ent;} %token<nombre> CADENA %token<ent> NUM %token<ent> C %token<ent> B %% A: B C; {printf("Cadena %s, numero %d", $2, $1} B: NUM; {$<ent>$= $<ent>1;} c: CADENA; {$<cad>$= $<cad>1;}

[roikansuirius-blog]

PCD: Sesion 4

MONITORES EN JAVA

No existe una clase monitor en java, sin embargo se construyen de una forma que hemos visto anteriormente. En una clase cualquiera podemos definir cerrojos en base a la existencia de un metodo ‘synchronized’ pues solo puede ejecutarse un metodo sincronizado a la vez y ademas se bloquean el resto de procesos que entran asociados a la cola del objeto de la clase.

Sin embargo, no existe una cola crítica a la que van los procesos cuando se desbloquean. Existen varios procesos propios dentro de la sintaxis del monitor:

wait() -> Equivalente al delay() en un monitor, bloquea a un proceso si no se cumple una condicion que ha de estar encerrada entre 'while’. Esto se debe a que los monitores, en java, no tienen espera urgente y no entran al instante en ejecución sino que se despiertan y vuelven a pelear por la exclusión mutua pues la condición podría haber cambiado antes.

notify() -> Equivalente al resume(), despierta a un proceso aleatorio, de todos los bloqueados, esto significa que, si hay mas d euno que pueda bloquearse existe la posibilidad (por como está implementada la maquina virtual de java) de que nunca se desbloquee, lo cual lleva al proceso en inanición y no es recomendable.

notifyAll() -> Equivalente al resume(), despierta a todos los procesos, esto significa que, si tuvieramos un consumidor-productor y se tiene que consumir un elemento, los productores se despiertan tambien para pelear por la exclusión mutua (y vuelven a bloquearse) lo que hace que sea menos eficiente pero es aconsejable siempre usarlo.

Dentro de un método synchronized el formato ha de ser:

while(condicion)

try wait()

catch InterruptedException e

Codigo del método

notify();

De igual modo, cuando tenemos variables condition se pueden inicializar en la creación del objeto con su constructor. Veamos un ejemplo de un monitor que permite que cuatro hilos pueda imprimir entre ellos “hola amigos del mundo.” diez veces.

El monitor tendrá 4 procedimientos, cada uno de ellos permitirá que el hilo 1-4 escriban. El segundo no podrá escribir si el primero no lo hizo y para ello lo controlaremos con una variable entera para los turnos. Solo pondré el hilo encargado de escribir “hola” pues el resto son exactamente iguales salvo que cambiando el procedimiento al que llaman.

Por si hubiera confusión, en el proyecto se encuentra la version simplificada en la que cada método dicta el turno de que hilo es. Como podemos ver al ejecutar 10 veces los hilos, sale el formato turno1-turno2-turno3-turno4. Por lo que siempre se cumple.

[apuntesum-blog]

MONITORES CON REENTRANTLOCK

Un monitor no es mas que un cerrojo, que se bloquea inmediatamente cuando alguien hace un método sobre él y que se desbloquea una vez termine dicho método o si se bloquea por una condicion y va a una cola especifica de esa condicion dejando el monitor libre. Si definimos dentro de una clase un cerrojo reentrantlock podemos emular un monitor mucho mas flexible que un metodo synchroniced.

cerrojo.lock()

try{

while(condition)

---OPERACIONES---

}finally{

cerrojo.unlock()}

Si bien con metodos públicos sincronizados no teniamos como tal una variable de tipo CONDITION (en el ejemplo de escribir cuatro palabras lo haciamos con un entero cualquiera) ahora podemos tener mas de una cola de espera para cada variable condition. Definidas como:

private Condition condicion = cerrojo.newCondition();

Tienen que ser usadas dentro del mismo bucle while que hemos visto (justo tras el bloqueo del cerrojo) mientras no se cumpla esa condicion hacemos un 'await()' sobre la condicion (por lo que el proceso se bloquea, va a la cola de la condicion del cerrojo) y sale del cerrojo, permitiendo que otro proceso pueda entrar mientras él está bloqueado.

Si puede actuar hará ciertas cosas y al final hará un 'signal()' o 'signalAll()' sobre una condicion para liberar a uno o a todos los procesos bloqueados, que tendran que volver a pelear por el cerrojo y si su condicion no se cumple, volveran a ser bloqueados.

Si ademas queremos saber si hay procesos bloqueados en una cola de condicion podemos usar el método 'hasWaiters(Condition c)'

[apuntesum-blog]

Compiladores: Análisis Sintáctico

EJERCICIOS PRIMERO, SIGUIENTE Y PREDICT

S->Xd X->C|Ba C->λ B->d

Primero(S) = Primero(X) -> C|Ba -> λ|b -> Salió lambda-> {d,d} -> {d}

//S nunca será λ pues habra una d como poco.

Primero(X) = C|Ba -> {λ,d}

Primero(C) = {λ}

Primero(B) = {d}

Siguiente(S) = $ + reglas S a la derecha -> {$}

Siguiente(X) = S->Xd -> {d}

Siguiente(C) = X->C|Ba -> Si C=λ entonces Siguiente(X) -> {d}

Siguiente(B) = {a}

Predict(1) = Primero(S->Xd) = Primero(X) = {d}

Predict(2) = Primero(X->C) = Primero(C) -> Si Primero(C)=λ entonces Siguiente(X) -> {d}

Predict(3) = Primero(X->Ba) = Primero(B) -> {d}

Predict(4) = Primero(C->λ) si λ entonces Siguiente(C) = {d}

Predict(5) = Primero(B->d) = {d}

A->dA|dB|f B->g

---Factorizo--- A->dA'|f A'->A|B B->g

Primero(A) = {d,f} Primero(A') = Primero(A)∪Primero(B)= {d,f,g} Primero(B) = {g} Siguiente(A) = Siguiente(A')+$ = Siguiente(A)+$....= {$} Siguiente(A') = Siguiente(A) = {$} Siguiente(B) = Siguiente(A') = Siguiente(A)= {$} Predict(1) = Primero(A->dA') = {d} Predict(2) = Primero(A->f) = {f} Predict(3) = Primero(A'->A) = {d} Predict(4) = Primero(A'->B) = {g} Predict(5) = Primero(B->g) = {g}

ANÁLISIS DESCENDENTE PREDICTIVO NO RECURSIVO

El análisis descendendente predictio utiliza la tabla generada por el predict para establecer un algoritmo manual (de ahí que no sea recursivo) por el cual leyendo la entrada, el tope de la pila y la tabla de transiciones podemos determinar una serie de cosas:

Si el símbolo de la pila es terminal y coincide con el de la entrada, se eliminan ambos.

Si el simbolo de la pila no es terminal y el de la entrada pertenece a la tabla de análisis sintáctico se añade a la pila la regla que la generaria.

Si el simbolo de la pila es terminal y no coincide con el terminal de la entrada se lanza un error1().

Si el simbolo de la pila no es terminal y el de la entrada no pertenece a la tabla de analisis (la celda está vacia) se lanza un error2().

Suponiendo: S-> id|(SR R-> ,SR|) w=(id,id)

Primero(S) = {id,(}

Primero(R) = {,,)}

Siguiente(S) = $ + Primero(R) = {$,),,}

Siguiente(R) = Siguiente(S) = {$,),,}

Predict(1) = Primero(S->id) = {id}

Predict(2) = Primero(S->(SR) = {(}

Predict(3) = Primero(R->,SR) = {,}

Predict(4) = Primero(R->)) = {)}

Por lo cual tendriamos la siguiente tabla, donde el color rojo simboliza lo que está en el tope de la pila y en el puntero de la entrada:

Además tenemos que para cada paso podemos sacar una forma secuencial, que no es mas que lo que se ha leido, y lo que queda en la pila:

S =2> (SR =1> (idR =3> (id,SR =1> (id,idR =4> (id,id)

M -> (F FS) F -> num NS; FS -> F FS|λ NS -> num NS|λ

Primero(M)->{(}

Primero(F)->{num}

Primero(FS)->Primero(F)Uλ -> {num,λ}

Primero(NS) -> {num,λ}

Siguiente(M) -> $ -> {$}

Siguiente(FS) -> {)}

Siguiente(F) -> [M->(F FS)] -> Primero(FS)-λ+siguiente(FS) -> {),num}

Siguiente(NS) -> {;}

Predict(1)->Primero[M->(F FS)]->{(}

Predict(2)->Primero[F->num NS;]->{num}

Predict(3)->Primero[FS->F FS|λ]->Primero(F)->{num}

Predict(4)->Primero[NS-> num NS|λ]->{num}

Ahora supongamos que tenemos la entrada, (num num;;), ¿se validaria?

Ahora hagamos un analisis descendente recursivo, supongamos que hemos de construir un algoritmo que valide la anterior cadena, ¿como sería? Bueno, necesitamos las operaciones de error1(), error2(), coincide(token) y una funcion para cada simbolo no terminal. Donde el puntero estará en la variable preanalisis.

M() {if preanalisis∈predict(1) {coincide('('), F(), FS(), coincide(')')} else error2('M')}

F() {if preanalisis∈predict(2) {coincide('num'), NS(), coincide(;)} else error2('F')}

FS() {if preanalisis∈predict(3) {coincide('num'), FS()} else error2('FS')}

NS() {if preanalisis∈predict(4) {coincide('num'), FS()} else error2('NS')}

coincide(token) {if token=preanalisis preanalisis++ else error1()}

METODO LR

Para realizar el metodo LR tenemos que tener una tabla LSRA compuesta por estados, acciones y 'ir_a'. Sin embargo verificaremos la entrada '(num num;)' para la siguiente gramática:

M -> (F FS)

F -> num N;

FS -> F FS | λ

n -> num N | λ

Para operar con la tabla tendremos que tener en cuenta:

desplazarX -> Implica añadir a la parte derecha de la cola el simbolo actual de la entrada, quitarlo de la entrada, y poner el numero X en la pila.

reducirX -> Implica eliminar por la parte derecha los 2*simbolos (terminales y no terminales) de la regla que lo invoca(numeroX) (F-> num N; = 3), añadir el estado indicado en el apartado IR_A seguido del simbolo X.

Con dicha tabla:

Ahora procederemos a testear la entrada:

FORMA SENTENCIAL DERECHA, PREFIJOS VALIDOS E ITEMS

Como ocurria con el metodo LL, el metodo LR permite, en cualquier paso de la tabla anterior, mirando lo que hay en la pila mas lo que queda por leer, formar una forma sentencial derecha, donde partiendo del simbolo inicial M somos capaces de llegar a dicho estado haciendo derivaciones por la derecha. Un prefijo válido es por tanto solo lo que hay en la pila.

Un item válido es aquel que, usando un prefijo valido siempre se verifica. Decimos que este item LR(0) es una regla con un punto que simboliza 'parte que espero reconocer'. Asi pues podriamos tener una serie de items como:

A->·xyz | A->x·yz | A->xy·z | A->xyz·

Cada conjunto de items es una colección LR(0) dichos conjuntos son el estado de un automata finito determinista y nos servira para identificar los prefijos viables. Para construir la colección hay que aumentar la gramatica y utilizar las operaciones 'clausura' y 'goto'.

[apuntesum-blog]

PCD: Monitores

CONTEXTO

Los monitores se utilizan en sistemas basados de memoria compartida con aplicaciones compuestas por procesos que acceden a recursos no compartibles y requieren de reglas de sincronización. Necesitamos garantizar la exclusión mutua (que no se comparten cosas cuyo uso simultaneo generaría errores) y garantizar las condiciones de sincronización.

Hemos visto que la inhibicion de interrupciones es solo válida en los monoprocesadores, y pueden causar graves fallos, las basadas en espera ocupada son muy ineficientes y las basadas en semáforos son complejas, dificiles de mantener y hay que tener el codigo de sincronizacion distribuido entre todos los procesos.

Un monitor permite encapsular la representación de los recursos no compartidos mediante la encapsulación de datos junto a las operaciones que acceden a los mismos y permiten el control de la exclusion mutua y condiciones de sincronizacion. Al utilizar monitores podemos distinguir dos tipos de procesos:

Pasivos: Implementan los monitores y esperan a que los procesos activos utilicen sus operaciones.

Activos: Interaccionan entre si a través de las operaciones de los procesos pasivos.

DEFINICION

Un monitor está formado por:

Un nombre.

Un conjunto de variables privadas (o permanentes): Almacenan el estado del recurso en sucesivos usos, sólo se pueden acceder a través de los procedimientos públicos y mantienen los valores entre las distintas llamadas al monitor.

Procedimientos (públicos o privados): Manipulan el recurso a través de la modificación de las variables privadas, estos procedimientos pueden tener variables locales y parámetros. Además garantizan la integrdad de las variables privadas.

Un cuerpo de inicialización para inicializar las variables permanentes.

Colas de espera.

Por ejemplo para hacer uso del monitor diríamos:

nombre_monitor.nombre_procedimiento(párametros);

contador.inc();

Invocar a un procedimiento implica intentar entrar al monitor. Solo un  procedimientos se puede ejecutar dentro del monitor en cada momento. Existe una gestion automática de una cola FIFO (first-input-first-output) de espera de procesos que quieren entrar para ejecutar algun procedimiento del monitor mientras este está en uso, por lo tanto, la ejecución de los procedimientos de un monitor se lleva a cabo en exclusión mutua.

EXCLUSIÓN MUTUA CON MONITORES

Si el recurso se compone por una o mas variables lo declararemos dentro del monitor.

Si el recurso no es software, haremos un monitor que ofrezca las operaciones necesarias para utiliar el recurso.

Si el numero de operaciones a ofrecer es demasiado alto, es mejor usar el monitor para implementar un protocolo de entrada y otro de salida que sirva para cualquier sección crítica (semáforo binario).

Por ejemplo, sabemos que para escribir en pantalla, tiene que haber exclusión mútua, asi que podemos hacerlo con un monitor:

Monitor mutexPantalla; export print;

procedure print(msg: string) begin writeln(msg); end; begin //No hace falta inicializar nada end;

Del mismo modo podriamos implementar un semáforo binario, donde solo quedaría la duda de saber como se hace una funcion que bloquee un proceso o lo desbloquee.

CONDICION DE SINCRONIZACIÓN EN MONITORES

Necesitamos bloquear un proceso cuando no se cumple una condicion. Necesitamos que un proceso activo pueda desbloquear un proceso bloqueado al hacer que se cumpla la condicion que éste esperaba.

Dentro de un monitor se pueden declarar y usar variables de tipo CONDITION que permiten gestionar colas FIFO de procesos bloqueados.

Variables CONDITION:

Sus valores no son accesibles por el programador.

Son colas FIFO, inicializadas de forma vacía.

Se utilizan para desbloquear y bloquear procesos en espera de una determinada condición.

VARIABLES DE CONDICIÓN

Son variables de tipo condition;

Solo pueden declararse dentro de un monitor: var cond: condition;

Solo tienen las siguientes operaciones: delay(cond), resume(cond), empty(cond).

Delay(cond): Similar a la operacion wait sobre un semáforo. Bloquea el proceso en la cola asociada a la variable condición. El esquema sería:

Si hay un proceso esperando por acceder al monitor, entonces cederle la exclusión mutua del monitor, sino liberar la exclusión mutua del monitor, en cualquier caso bloquear el proceso en la variable condición.

Resume(cond): Similar a la opracion signal sobre un semáforo. Desbloquea el primer proceso en la cola asociada a la variable condición. Si no hay procesos en espera se transforma en una operacion nula.

Podriamos hacer un monitor que usara una variable privada (cond1) y que un proceso tuviera que hacer un procedimiento para que el otro pudiera hacer el suyo.

monitor Ejemplo: export proc1, proc2 var cond1:condition;

procedure proc1; begin delay(cond1); end;

procedure proc2; begin resume(cond1); end;

end

En algun punto se hará 'ejemplo.proc1();' que bloqueará al proceso que lo invoque y en algun punto se hará 'ejemplo.proc2();' que o bien desbloquea al otro o se ejecutó en primer lugar y por tanto el otro proceso se ejecutó tras la condicion de sincronización.

La operación resume desbloquea y pone dicho proceso en espera urgente de una cola de cortesía, donde los procesos bloqueados tienen preferencia sobre los que se bloquean en la cola del monitor.

Empty(cond): Se utiliza para saber si la cola asociada a la variable condición está vacía o no.

Los procesos se comunican/sincronizan a través de los datos protegidos por el monitor. Una variable Condition por condicion lógica.

Las distintas condiciones serán relativas a los datos privados del monitor o el estado del recurso presentado para garantizar el acceso en exclusión mutua.

Los distintos procesos ejecutan procedimientos en los que pueden quedar bloqueados o desbloquear a otros procesos.

Nota: NO USAR LOS DELAY DE FORMA INCONDICIONAL.

ANALISIS DE BUFFER LIMITADO

Recursos no compartibles:

Cola.

Se insertan y se extraen elementos.

Condiciones de sincronización:

Solo se inserta si hay espacio.

Solo se extrae si hay elementos.

Por tanto:

Cola será una variable dentro del monitor.

Habrá dos procedimientos: insertar y extraer.

Dos variables Condition, una para cada condicion: nolleno, novacio.

[apuntesum-blog]

AED2: Análisis de Algoritmos P2

EJERCICIOS NOTACIONES ASINTÓTICAS

Ejercicio 1: tm(n)=n² y tM(n)=2n², ¿que podemos decir de tp(n)?

a) ((tm(n)+tM(n))/2 = (n²+2n²)/2 = 3/2*n²

b) tp(n) tiene forma de parábola

c) a y b

d) no sabemos nada

a) es falsa, pues la funcion promedio NO se puede calcular haciendo la media aritmetica. Otra cosa sería hablar de los ordenes y ni aun así sería cierto. b) La funcion promedio está entre la funcion del mejor tiempo posible y el peor, caso por lo que tiene que tener la misma forma. Si vemos la imagen del final la linea superior sería tM, la inferior tm y en algun punto del medio debe de estar tp(n). c) Falsa, pues a es falsa. d) Falsa pues sabemos quen o es a, y que es b.

Ejercicio2: tm(n)∈O(n²) y tM(n)∈Ω(n³), ¿que podemos decir de t(n)?

Por definicion, el orden de complejidad indica que todo lo que ocurra pasa debajo del limite que impone. La cota inferior indica que todo lo demas se encuentra superiormente, y el orden de complejidad lo opuesto. Si tM es la marca roja, y tm la marca azul, donde las otras dos marcas son n³ y n². Sabemos que t(n) no es mejor que tm(n) y no es peor que tM(n), como mucho será igual, asi que está contenido entre dichas dos áreas.

Ejercicio 3: Si tm(n)∈Ω(n²) y tM(n)∈Θ(n³), ¿que podemos decir de tp(n)?

Sabemos que el mejor (de los mejores) tiempo mejor, como poco será de orden n², además el peor tiempo será exactamente siempre de orden n³, no puedo calcular exactamente cual es el tiempo promedio, pero si que es de orden O(n³) [como muy malo] y Ω(n²) como muy bueno.

Ejercicio 4: Contesta verdadero o falso y justifica la respuesta.

tp(n)∈O(tM(n)): Verdadero, el tiempo peor (tM) acota superiormente al tiempo promedio, si el peor tiempo es lo peor que pueda suceder, un caso promedio es un resultado o igual de malo o mejor lo cual quiere decir que está acotado siempre.

tm(n)∈Ω(tM(n)): La cota inferior significa que todo lo que hay en el peor tiempo está por encima de él, pero el tiempo mejor siempre está por debajo

tm(n)∈O(tM(n)): Siempre se cumple, es como decir que la cota superior del mejor tiempo es el peor, lo cual es evidente pues o siempre es igual, o siempre es peor el peor tiempo.

Si tm(n)∈Θ(tM(n))->tp(n)∈Θ(tm(n)): Sí. Si ambos ordenes coinciden de forma exacta, se deduce que el tiempo promedio es exactamente igual que el del mejor tiempo (y que el del peor).

Si tm(n)∈Ω(tM(n))->tM(n)∈O(tm): Que se cumpla lo primero implica que el peor tiempo acota inferiormente al mejor, esto quiere decir que el  mejor tiempo tiene que coincidir con el peor tiempo, pues todo tiene ue quedar por encima del peor tiempo. Y si eso se cumple es evidente que lo que acote al mejor tiempo, acotará tambien al peor tiempo.

En cualquier algoritmo tm(n)=/=tM(n): Falso, si t(n)=k > k=cte, significa que tm(n)=tM(n)=t(n)=k.

(tM(n))²∈Ω(tM(n)): Cierto, si la cota inferior es x, y haces el cuadrado de la misma funcion se va a ir hacia arriba, lo que implica que si, que el limite se mantiene y sigue siendo cotai nferior.

tp(n)+tm(n)+tM(n)∈Θ(tM(n)): Θ(tp(n)+tm(n)+tM(n)) -> Θ(maximo(tp(n)+tm(n)+tM(n)) -> Θ(tM(n)).

NOTACIONES ASINTÓTICAS CON PARÁMETROS

A veces un algoritmo depende de mas de un parametro, esto significa que nuestra funcion de tiempo en vez de ser t(n) pudiera ser t(n,a) por lo que tendriamos dos variables que codifican el tamaño del problema. Inicialmente no se trata de forma diferente.

Suponiendo listas el algoritmo bpp tenia un orden de complejidad O(n+a). Y podía ir desde n hasta n². No existe diferencia entre el orden de complejidad, la cota inferior, u orden exacto de como los vimos antes.

¿Que orden de complejidad es mayor?

O(n+m), O(n^m) -> Suponiendo valores grandes, es evidente que el orden de complejidad segundo contiene (y por mucho) al primero. O(n+m)⊂O(n^m)

O(n²), O(n+2^m) -> ¿Que es m en el primer orden? Si debemos de suponer grandes valores 2^m ganará, pero falta informacion. No puedo firmar nada.

NOTACIONES ASINTÓTICAS CONDICIONALES

Algunos resultados pueden simplificarse con la suposición de que se cumple cierta condicion para generalizar. Si se supone dicha condicion somos capaces de encontrar un O(f|P) -> t(n)<=c f(n) e igual para la cota inferior pero no para el orden exacto.

Generalmente podemos hacer dos suposiciones:

t(n)∈O(f|n=2^k) -> Potencia de 2.

t(n)∈O(f|n=2k) -> Múltiplo de 2.

Esto viene por un teorema donde: Si b>=2 es un entero y f:N->R+ creciente a partir de cierto umbral (f termina creciendo sí o si) si f(b*n)∈O(f(n)), f es b-armonica. Y si t:N->R+ es creciente a partir de cierto umbral tal que t(n)∈O(f|n es potencia de b). Existe t(n)∈O(f(n))

Ejemplo: Busqueda binaria suponiendo 2^k. t(n) = 2 + 4log(n+1) ∈ O(log(n)|n=2^k)

2+4log(n+1) -> es creciente.

logn -> es creciente

b->2

log(2n)∈log(n) ->cierto -> log(2)+log(n)∈log(n).

Conclusion: Cierto.

ECUACIONES DE RECURRENCIA

A veces se nos puede presentar una ecuación que depende de n término que se calculó a priori. Hay multiples técnicas pero alguna solo deben de ejecutarse bajo ciertas condiciones.

EXPANSION DE RECURRENCIA

Cuando una funcion depende de UNA SOLA RECURRENCIA podemos utilizar la expansion de la recurrencia que consiste, básicamente en desglosar una a una todas las posibilidades sin agrupar términos, al final se verá un patrón en un numero de k-pasos.

t(1)=1 t(n)=2*t(n-1)+1 t(n-1)=2*t(n-2)+1 t(n-2)=2*t(n-3)+1

t(n)=2*(2*t(n-2)+1)+1 = 2*2*t(n-2)+2+1

t(n)=2*2*(2*t(n-3)+1)+2+1 = 2*2*2*t(n-3)+4+2+1...

K pasos -> t(n)=2^k*t(n-k)+2^(k) + 2^(k-1)+...+2^(k-k)

Pero no podemos en base a k pues en el algoritmo inicial solo teniamos una incognita. Asi que hay que llevarla hasta el punto donde sepamos resolvera. Conocemos t(1) asi que k=n-1.

ECUACIONES CARACTERISTICAS: LINEALES HOMOGENEAS

Utilizadas cuando una funcion de recurrencia depende de VARIAS recurrencias y se dividen en varios pasos.

Inicialmente: t(n) = K*t(n-1)+J*t(n-2)....

Pasamos terminos a la izq e igualamos: t(n) - K*t(n-1)...=0

Sustituimos t(n) -> x^n, t(n-1) -> x^(n-1).

Dividimos todo por el termino de menor grado.

La soluciones (S1,S2..) se sutituyen como: C1*S1^n + C2*S2^n +...

Hacemos un sistema de ecuaciones con los casos bases.

Resolvemos.

Sustituimos finalmente C1, C2...

Ahora procedemos a crear la ecuacion carecteristica e intentar resolverla.

ECUACIONES CARACTERISTICAS: CON SOLUCIONES IGUALES

Con la anterior tecnica hemos visto que al dividir entre el termino de menor grado, nos sale una ecuacion de grado (k), donde dicha k determina las soluciones que salen. Pero, ¿que pasa si dos de esa soluciones son iguales?

La tecnica consiste, en la ecucacion caracteristica poner despues de todas las soluciones que no se repiten, las que coinciden con el formato C+n*Srepetida^n.

El resto de los pasos permanecen igual.

Una vez hagamos Ruffini, veremos que nos sale 1 (x=1) y con la ecuación de segundo grado tendriamos las soluciones (2,2).Y la diferencia con la ecuacion caracteristica homogénea sin soluciones iguales:

ECUACIONES CARACTERISTICAS NO HOMOGÉNEAS

Los pasos a realizar son los mismos, teniendo en cuenta que pasamos a un lado los terminos que dependen de t(n-k) y dejamos en el otro lado aquellos terminos que no dependen: constantes, terminos en base a n... Aquellos que no dependen de t(n-k) se verán de la forma b^p*(polinomio). La solución será (b)^(grado_polinomio+1)

CAMBIO DE VARIABLE

A veces interesa que una ecuación presuponga que dada cierta forma de los datos que se introducen genera un resultado entero. Por ejemplo si la funcion hace algo como t(n/2)+t(n/4)... podriamos presuponer que n es multiplo de 2 -> n=2k (k=n/2) ó es potencia de 2 -> n=2^k (k=log2(n)).

CONDICIONES DE VARIABLE

En el ultimo paso de la ecuación caracteristica, generalmente hay que usar los casos base para resolverlos. Pero a veces, tenemos que construir los nuestros. Cuando los construimos, casi siempre usamos la funcion general t(n), pero es posible que nos pidan 3 terminos, y que ninguno use la formula general. Lo cual está mal.

Si dijimos que la condicion es que n=2*k el término que calculemos debera de ser, en este caso (0,2,4,6...).

Si tenemos tres numeros (0,1,2) y ellos salen de los casos base, necesitamos calcular uno que utilice la formula general t(n) si fuera necesario.

EJERCICIOS FINALES

RELACIONES DE ORDEN

Podemos comparas los órdenes de magnitud en base a limites de sus diferencias. Por tanto si vemos que sale una indeterminacion (infinito/infinito) tendriamos que proceder a hacer L'Hopital y/o usar otras técnicas.

Esto signfica que ambos ordenes son iguales, lo que implica:

O(f(n))=O(g(n))

Ω(f(n))=Ω(g(n))

θ(f(n))=θ(g(n))

No obstante garantizar que o(f(n))=o(g(n)) dependería de que no se hubieran hecho aproximaciones en el límite.

El orden de arriba es inferior al de abajo, lo que implica.

O(f(n))⊂O(g(n))

Ω(g(n))⊂Ω(f(n))

El orden de arriba es superior al de abajo, lo que implica:

O(g(n))⊂O(f(n))

Ω(f(n))⊂Ω(g(n))

PROPIEDADES DE LOS LOGARITMOS

En base a esto podemos hacer unos cuantos ejercicios:

O(n),O(n²):

O(n²/n)=>O(n)=>Infinito

Esto significa que O(n)⊂O(n²) y Ω(n²)⊂Ω(n)

O(log3(n)), O(log5(n)), O(ln(n)):

O(log3(n)/log5(n))=O([log5(n)*1/log3(5)]/log5(n))=O(log5(n)*cte/log5(n))=O(log5(n)/log5(n))=1.

Esto significa que O(log3(n))=O(log5(n)), Ω(log3(n))=Ω(log5(n)), θ(log3(n))=θ(log5(n))

O(log5(n)/ln(n))=O([ln(n)*1/log3(e)]/ln(n))=O(ln(n)*cte/ln(n))=O(ln(n)/ln(n)=1.

Esto significa que O(log5(n))=O(ln(n)), Ω(log5(n))=Ω(ln(n)), θ(log5(n))=θ(ln(n)).

O(5^(√4n)), O(2^n): Si intento hacer limites no conseguiré nada. Si 2^n es de orden de complejidad mayor, entonces podria encontrar un c a partir de un n0 que cumpla la definicion de un orden de complejidad.

5^(√4n) <= c*2^n

log(5^(√4n)) <= log(c*2^n)

(√4n)*log(5) <= log(c)* log(2^n)

//quito las constantes, y supongo un c=1//

(√4n) <= n*log(2)

(√4n) <= n

Cierto por definicion.

O(5^(√4n))⊂O(2^n) y Ω(2^n)⊂Ω(5^(√4n)).

RECURRENCIA

Una funcion recurrente solo cuenta el numero de veces que se llama a un procedimiento de si mismo, por ejemplo si hago cosa(n-1)+cosa(n-1)*6, solo contaria 2t(n-1), aunque podria simplificarse a cosa(n-1)*7 y por tanto t(n-1).

if p<3 return 2

else

result=cosa(p-1)+cosa(p-1)*6-cosa(p-3)

return resul

endif

Caso base (n=0,1,2,3): 1(if)+1(return) = 2. Caso recursivo (n>3): t(n)=1(if)+1(result)+1(return)+2t(n-1)+t(n-2)=3+2t(n-1)+t(n-2)

[apuntesum-blog]

PCD: Practica 2

PROTECCION DE LA SC CON ESPERA PROTEGIDA

Usando la espera ocupada protegeremos la seccion crítica de un programa que lo unico que hace es escribir cuando entra en la seccion crítica. Para ello en el hilo "HiloPrimerIntento" en la funcion run haremos un bucle hasta diez, si la condicion es uno, entonces dormimos n cierto numero de tiempo, volvemos a poner la misma condición a uno, escribimos que está en la sección critica y luego volvemos a hacer otra esera antes de bloquear la condicion.

El problema es que ambos hilos son caaces de entrar simultaneamente en la seccion crítica lo que casi siempre resulta en desastre.

EXCLUSIÓN MUTUA CON SYNCHRONIZED

Decir que un método es synchronized significa que solo este metodo puede ejecutarse, es mas, si hubieran dos métodos synchronized solo uno de ellos podría ejecutarse (lo que hace que entre ellos haya una exclusión mutúa). Un ejemplo sería la clase "Sincronizados" en la que o se ejecuta el método m2, o el método m4 pero nunca ambos simultaneamente.

Utilizad synchronized es a efectos prácticos poner un semaforo binario, cuando un hilo ejecuta un metodo sincronizado, el cerrojo asociado a ese objeto se cierra y ningun otro hilo puede ejecutar otro método sincronizado. El siguiente ejemplo utiliza synchronized para que dos hilos incrementen una variable compartida "volatile" en mil unidades cada uno.

En el siguiente ejemplo crearemos una variable compartida con un metodo sincronizado para su incremento. Luego crearemos un hilo y un main para hacer la suma y veremos al final que resultado sale.

SYNCHRONIZED SOBRE UNA PARTE DEL CODIGO

Usar sycnrhonized sobre un metodo entero es muy puntual, si queremos proteger la seccion crítica de un hilo podemos utilizar la funcion 'synchronized(objeto){ SC }'. Eso si, el objeto debe de ser vacío y ser compartible entre todos los hilos.

En la anterior practica hicimos un ejercicio que simulaba un cajero, aunque podriamos hacerlo de nuevo no tiene mucho caso, podemos hacer un contador que suma de 1 en 1 y se hace por hilo 10 veces. Recordando que hemos de crear un objeto volatil vacío:

SEMÁFORO BINARIO 'REENTRANTLOCK'

En el paquete java.util.concurrent.locks se puede encontrar la clase ReentrantLock como la interfaz que ésta implement y se llama Lock (cerrojo) que proporcionan mas funcionalidad que la obtenida por el método synchronized.

Un cerrojo permite controlar el acceso en exclusion mutua a recursos compartidos por multiples hilos, donde solo uno puede entrar al cerrojo y para poder entrar tiene que adquirir en primer lugar el cerrojo. El objeto de tipo ReentrantLock es el semaforo binario.

Los métodos y bloques synchronized proporcionan un cerrojo asociado con cada objeto, pero la forma de adquirirlo y liberarlo es de una forma estructurada. Si debemos adquirir varios cerrojos, estos deben de ser liberados en el orden opuesto y dentro del ambito en el que fueron adquiriros. Aunque esta forma de programar evita muchos errores típicos de programacion usando cerroos, a veces es conveniente poder trabajar con cerrojos de una forma mas flexible. Por ejemplo adquirimos el cerrojo del objeto A, despues del objeto B, liberamos A, adquirimos C, liberamos C,...

Las implementaciones de la interfaz Lock permiten que las operaciones de adquirir y liberar un cerrojo estén en diferentes ambitos y permiten que varios cerrojos sean adquiridos y liberados en cualquier orden. Dicha estructura comun de trabajo es:

De nuevo veremos el siguiente ejemplo de la variable compartida por dos hilos usando la clase ReentrantLock. Recordando que siempre hay que mandar al hilo a dormir para que sea posible el que se interrumpan si sale mal.

EXCLUSION MUTUA Y SINCRONIZACION CON SEMAPHORE

La clase Semaphore se define en el paquete java.util.concurrent. Cuando creamos un objeto de tipo Semaphore, indicamos su valor inicial. Las operaciones wait se traduce a (acquire) y signal como (release). Veamos el ejemplo de la variable compartida como:

Podemos hacer sincronización usando semáforos generales implementados con Semaphore. Por ejemplo una serie de hilos que han de escribir Hola-Mundo por pantalla pero una palabra cada uno.

¿Y si quisieramos imprimir, 'hola mundo querido'? Bueno, Habria que cambiar un poco el asunto empezando por añadir otro semáforo, el primero abierto, los otros dos bloqueados. Cuando el primero termina, abre el segundo, que se ejecuta, cuando termina abre el tercero y luego este abre el primero. Por lo cual, dentro del proyecto se cambiarán dichas clases ademas de añadir otra para resolver el problema:

Para mas informacion visitad: http://www.mediafire.com/download/j32uou236zl4y7h/PCD.rar

[apuntesum-blog]

Compiladores: FLEX

Flex es una herramienta que analiza expresiones regulares, utiliza un lenguaje muy parecido a los patrones de java, donde en concreto, estas ER o patrones son llamados reglas. Usaremos FLEX con tres ficheros:

Fichero cabecera (extension.h)

Fichero lenguaje flex (extension.l)

Fichero lenguaje c (extension.c)

La estructura de un fichero con extension .l es l a siguiente:

%{

#include "ficherocabereza.h"

%}

//Definiciones//

script [rango];

%%

//Reglas//

ER accion;

//Condiciones//

%%

Ficherocabecera.h debería contener una serie de #defines con un nombre y un numero asignado, por ejemplo para un lenguaje podriamos tener en la cabecera.h lo siguiente:

Y un ejemplo de lo que podría contener el fichero.l podria ser:

Por ahora no prestaremos atencion a que contiene el fichero c.

REGLAS DE EXPRESIONES REGULARES

Flex utiliza una serie de reglas para formar las expresiones regularas, una de las más importantes es que FLEX intenta rellenar la expresión mas grande. Por lo tanto si una expresión regular confirma 'a' y otra confirma 'abc' tomará la mas grande.

La barra \ seguida de un simbolo, elimina el significado especial del simbolo y lo toma literalmente.

a* -> λ, a, aa, aaa...

a\* -> a*

Las comillas “ ”eliminan el significado de cualquier caracter (o mas de un caracter) y lo toman literalmente.

a* -> λ, a, aa, aaa...

"a*" -> a*

Una cadena de caracteres entre corchetes [ ], es un solo posible simbolo. Además, todos los caracteres salvo '-' y '^' pierden su significado, también se puede llamar a nombres de clases definidos con [:nombre:].

[abc] -> (a|b|c)

[^abc] -> (^a|^b|^c) //complementario (opuesto)

[a-z] -> (a|b|c|...|z)

[[:digito:]] -> (0..9)

El . simboliza cualquier caracter salvo el retorno de carro \n.

La ? expresa la posibilidad de que el simbolo ANTERIOR aparezca o no.

ab?c -> ac ó abc

a(bc)?d -> ad ó abcd

Los operadores de clausura * o clausura positiva + siguen funcionando igual.

a* -> λ, a, aa, aaa...

a+ -> a, aa, aaa...

Las llaves {,} representan repeticiones y tienen diferentes usos.

digito [0-9]  ||  {digito}

a{1,3} -> a, aa, aaa.

a{2} = aa

a{2,} = aa, aaa, aaaa...

El simbolo ^ es un operador de contexto que obliga a, fuera del corchete, a aparecer en primer lugar.

El simbolo $, situado al final de una cadena obliga a que aparezca en ultimo lugar.

El simbolo / obliga a que solo se verifique la parte de atrás si aparece la de delante.

abc/d -> abcd

abc/(d|c) -> abcd ó abcc

CONDICIONES

El uso de condiciones se divide en tres partes:

Una expresión regular confirma el inicio de una condicion (activa).

Otra expresión regular cierra la condicion con un end.

Una accion solo puede realizarse si la condicion a la que invoca a través de <nombrecondicion> está activa, o si simplemente tiene <initial>.

Supongamos que quiero una condicion para detectar un comentario que empieza con '(*' y termina con '*)' pudiendo tener cualquier cosa en mitad. Para ello imaginemonos la cadena mas complicada, por ejemplo:

(****holasoyuncomentario**todobien**)

%x comentario

%%

"(*" BEGIN comentario

<comentario>[^*]* ;  todo lo que no sea un comentario

<comentario>[*]+[^)*]* ;   uno o mas asteriscos y otra cosa que no sea ni cerrar corchete ni asterisco.

<comentario > "*)" BEGIN 0

VARIABLES DE FLEX

Existe una serie de variables que tienen un uso muy potente en Flex, por ejemplo si queremos contar el numero de lineas, podriamos poner la opcion '%option yylineno' que permite, usando yylineno, el saber en que linea ha saltado una regla (y si identificamos que era un error, entonces podemos decir en que linea fue).

yymore() -> Permite concatenar a la varible yytext la cadena que verificó una expresión regular. ¿Que pasaría si quisieramos imprimir en pantalla el comentario?

"(*" BEGIN comentario; yymore();

<comentario> [^*]* ;yymore();

<comentario> [*]+[^)*]* ;yymore();

<comentario> [*]+[)] Begin 0; yymore();Printf("%%",yytext);

EJERCICIO 1: Reconocer frases que no utilizen letras minusculas en ningun lugar.

^[^a-z]*$ -> Esta expresion regular cogería cualquier cosa que no tenga letras minusculas, pero claro, si todo el fichero está en mayusculas, cogería todo el fichero y no cada frase. Asi que podemos obligarle a que no coja el salto de linea. ^[^a-z\n]*$

EJERCICIO 2: Una expresión que reconozca algo entre comillas y dentro, lo que sea.

\".*\" -> El problema, de nuevo es que sería capaz de coger otras comillas de cierre porque busca la expresión mas grande. Por tanto hay que poner como limite que, dentro de cualquier simbolo, no puede coger la comilla, ya que esa sería la de cierre. \"[.^"]\"

EJERCICIO 3: Una expresion que reconozca la palabra reservada SELECT sin sensibilidad a mayusculas o minusculas.

(S|s)(E|e)(L|l)(E|e)(C|c)(T|t) ó [Ss][Ee][Ll][Ee][Cc][Tt]

[apuntesum-blog]

PCD: Semáforos

No existe separación entre las variables usadas para la sincronización y para la computación. Los semaforos buscan bloquear procesos pasandolos a una inactividad y sacándolos de la lista de procesos activos hasta que reciban una señal que les permita volver a la disputa por el control de la CPU.

Un semáforo es un TAD que tiene las siguientes caracteristicas:

Valores permitidos: 0 o 1 (binario) ó cualquier número positivo (general). Operaciones:

Inicialización: initial(nombre_señal, valorinicial) Señalización: signal(nombre_señal) Espera de señales: wait(nombre_señal)

El funcionamiento de las operaciones son simples, la inicialización otorga un valor 's' inicial para el semaforo, a veces 1, a veces 0 y a veces otra cosa. La señal de signal o bien incrementa el contador o, si hay un proceso o mas bloqueados, desbloquea uno. La señal de wait bloquea un proceso si s=0 y si no, reduce en uno el valor 's'. Internamente las dos ultimas operaciones, que son atómicas por defecto, ejecutarían:

wait(s):

if  s>0 then s:=s-1 else bloquear_proceso

signal(s)

if algun_proceso_bloqueado then desbloquear_proceso else s:=s+1

EXCLUSION MUTUA

Garantizar la exclusión mutua con un semaforo que por convenio llamaremos "mutex". Basicamente, si un proceso tiene una sección crítica antes la bloquearemos con un wait(mutex) y despues con un signal(mutex), es evidente que hay que inicializar siempre el mutex=1 para que si es la primera vez que un proceso se mete, no se queden todos bloqueados al infinito.

P1:

Precondicion: wait(mutex)

Seccion critica: SC

Postcondicion: signal(mutex)

CONDICION DE SINCRONIZACION

Garantizar que un proceso se ejecute cuando sucede un evento, es lo mismo que, antes de que se inicie la parte que requiere dicho evento, bloquearlo con un wait(s) y que el proceso que realiza dicho evento cuando termine de hacerlo, envie un signal(s) asi si se ejecuta el primero, se bloquea y va al segundo que envia la seal al final y termina el primero ó se hace el segundo y despues el primero.

Ejemplo 1: P2 no debe ejecutar d hasta que P1 no haya ejecutado a.

s=0;

P1              |   P2

a                |   c

signal(s)     |   wait(s)

b                |   d

Ejemplo 2: P1 y P2 no puede ejecutar b antes de que P2 haya ejecutado c y P2 no puede ejecutar d hasta que P1 haya ejecutado a.

s=0; t=0;

P1           |   P2

a             |   c

signal(s)  |   wait(s)

wait(t)      |   signal(t)

b             |   d

Ejemplo 3: Solo se ejecuta d en P2 si P1 ha ejecutado a o si P3 ha ejecutado f. ¿Y como podría hacerse para que en bucle P2 no ejecutara operaciones incorrectas?

s=0;

P1            |   P2          | P3

a              |   c            | e

wait(t)       |   wait(s)   | signal(s)

b              |   d            | f

               |   wait(s)     |

EJERCICIO 2: Suponiendo que hay una serie de t terminales e i impresoras, cada terminal puede utilizar cualquier impresora pero solo aquellas que estan libres. ¿Como se haría de forma concurrente?

process type terminal(id:integer) //type indica que se instanciara muchas veces var: k:integer; initial(impresora,i) initial(mutex,1) libre: array[1..i] of boolean (true [libre], false [ocupada]) begin Repeat Operaciones buscar_impresora_libre marcar_ocupada usar_impresora liberar_impresora end;

//Si garantizamos que siempre hay una impresora libre se puede hacer un bucle simple. wait(impresora) //A partir de aqui, empieza la SC que hay que proteger. wait(mutex) k=1 while not libre[k] do k++ libre[k]:=false signal(mutex) usar_impresora //Uso K de nuevo, ¡he de protegerla! wait(mutex) libre[k]=true; signal(mutex) signal(impresora)

EJERCICIO 3: Dos procesos leen de un fichero a un buffer, luego ordenan y un tercer proceso toma ambos bufferes y los fusiona.

process type lector(id:integer) var buffer: array[1..n] of integer initial(mutex,1) initial(listo,0) begin i:=1 //Aunque leer dos variables puede realizarse concurrentemente no es lo mismo leer de un fichero, asi que tenemos que protegerlo. wait(mutex) while not eof(fichero) do begin read(fichero, buffer[i]) //Al incrementar el contador tenemos que protegerlo de tal modo que el primero lea, avance y permita al siguiente leer el termino anterior. signal(mutex) i++ wait(mutex) signal(mutex) signal(listo)                                                                                                  end

process fusionador() wait(listo) wait(listo) fusionar(buffer1, buffer2)

PRODUCTOR CONSUMIDOR

Existen dos procesos, el productor genera un recurso y el consumidor lo consume. Para facilitar esta tarea el productor mete el recurso en un buffer y el consumidor lo saca del buffer. El buffer tiene un formato FIFO por lo cual hay dos punteros, uno para el frente y otro para la cola. Por tanto existen ciertas condiciones como:

La generación del recurso siempre se realiza.

La consumición del recurso siempre se realiza.

El recurso ha de introducirse al buffer intemedio si este no está lleno.

El recurso ha de obtenerse si el buffer no está vacío.

Ahora bien, lo mas simple sería suponer que el bufer es ilimitado. Lo que daría a una serie de procesos donde el consumidor ha de esperar a que el productor meta en el buffer un elemento, o mas.:

Process Productor:

Begin

Repeat

recurso:= producir();

buffer[frente]:=recurso;

frente++;

signal(producido);

Forever

Process Consumidor

Begin

Repeat

wait(producido);

recurso:=buffer[cola];

cola++;

consumir(recurso);

Forever

Begin

cola:=0;

frente:=0;

initial(producido, 0); //hasta N//

cobegin

Productor1;

Consumidor1;

coend;

End.

Ahora supongamos que el buffer no es ilimitado (será de tamaño N y daremos vueltas sobre su tamaño (mod N)), con lo cual tendremos que saber si hay huecos o no para meter o no el recurso.

Process Productor:

Begin

Repeat

recurso=producir();

wait(huecos);

buffer[frente]=recurso;

frente=(frente+1)MOD N;

signal(producido);

signal(lleno)

Forever

Process Consumidor

Begin

Repeat

wait(lleno);

recurso=buffer[cola];

cola=(cola+1)MOD N;

signal(huecos);

consumir(recurso);

Forever

Begin

cola:=0;

frente:=0;

initial(lleno,0); //hasta N

initial(huecos,N); //hasta 0

cobegin

Productor1;

Consumidor1;

coend;

End.

Ahora veamos el ultimo ejemplo, donde hay varios productores y varios consumidores. Esto implica que varios procesos tienen acceso a la variable 'frente' y 'cola' lo que obliga a que haya que protegerlos con exclusión mutua.

Process type Productor

Begin

Repeat

recurso=producir();

wait(huecos);

wait(mutex);

buffer[frente]=recurso;

frente=(frente+1)MOD N;

signal(mutex);

signal(lleno);

Forever

Process type Consumidor

Begin

Repeat

wait(lleno);

wait(mutex);

recurso:=buffer[cola];

cola:=(cola+1)MOD N;

signal(mutex);

signal(huecos);

consumir(recurso);

Begin

cola:=0;

frente:=0;

initial(mutex,1);

initial(huecos,N); //hasta 0

initial(lleno,0); //hasta n

cobegin

Productor1;...;ProductorN;

Consumidor1;...;ConsumidorN;

coend;

End.

LECTORES-ESCRITORES

En este problema un recurso no compartible es solicitado desde uno, o mas procesos. En general se aplica a la lectura, escritura. Donde hay una serie de reglas:

Las lecturas pueden ser concurrentes (esto significa que la operacion de lectura no tiene que estar protegido por ningun semáforo).

Una lectura no puede producirse si se está haciendo una escritura.

Una escritura no puede producirse si se está haciendo una lectura.

La escritura no puede ser concurrente.

Además hay que elegir una prioridad:

Prioridad Escritura: Si se están realizando lecturas, una vez terminen las actuales se lanza la escritura.

Prioridad Lectura: No se lanzan las escrituras hasta que todos los lectores hayan usado el recurso.

Supongamos prioridad lectura, empezaremos por lo mas facil que es la escritura y luego iremos con la lectura y supondremos que solo habrá una escritura y cualquier lectura:

Process Escritura

Begin

Repeat

wait(escritura)

ESCRITURA

signal(escritura)

Forever

Process type Lectura

Begin

Repeat

wait(mutex)

numero_lecturas=numero_lecturas+1;

//uso numero_lecturas a continuacion, he de protegerlas.

if numero_lecturas=1 then wait(escritura);

//si estoy leyendo, no intento escribir

signal(mutex)

LECTURA

wait(mutex)

numero_lecturas=numero_lecturas-1;

//vuelvo a usar numero_lecturas dos veces, he de protegerlas

if numero_lectura=0 then signal(escritura)

//si no hay lecturas, entonces permito la escritur

signal(mutex);

Begin

numero_lectura:=0;

initial(escritura,1); //hasta 0

initial(mutex,0); //hasta 1

End.

Ahora supongamos que tenemos mas de una escritura y prioridad de escritura. Para poder solucionar esto tenemos un código de como se haría usando la tecnica de espera ocupada, (que no es mas que hacer un bucle que libera la exclusion mutua y la vuelve a bloquear, quedandose atrapado infinitamente). Usaremos la tecnica de la cesion de la exclusión mutua que consiste en que el proceso que invoca al wait() posee un else segun una condicion y la tecnica del despertar encadenado.

Aprenderemos a sustituir la espera ocupada rompiendo el bucle de una forma eficaz y que permitira simplificar algunos problemas. "condicion -> ordenes entre mutex-while -> ordenes del while -> resto". El esquema mental sería:

Cojo la exclusión mutua (mutex).

Pongo la condicion del bucle.

Si no se cumple aumento los procesos bloqueados.

Libero la exclusión mutua.

Se bloquea el semáforo.

Actualizo la variable si se desbloqueó.

Process type escritor

Begin

Repeat

wait(mutex)

if numero_lectores>0 or escribiendo then begin

numero_escritores=numero_escritores+1;

signal(mutex);

wait(escritura);

end;

escribiendo:=true;

numero_escritores=numero_escritores-1;

signal(mutex)

ESCRIBIR

---PS---

Forever

Process type lector

Begin

Repeat

wait(mutex)

if escribiendo or numero_escritores>0 then begin

numero_lectores:=numero_lectores+1;

signal(mutex);

wait(lectura);

end;

numero_lectores:=numero_lectores+1;

signal(mutex);

LEER

---PS---

Forever

Bien, ahora solo queda el protocolo de salida. Donde para el Lector necesitamos lanzar un signal para que en la seccion donde antes se hacia (numero_escritores=numero_escritores-1) en el proceso de escritura le transfiera el signal que le hacía falta, lo que transfiere la exclusión mutua.

PS(Lector):

wait(mutex)

numero_lectores:=numero_lectores-1;

if numero_lectores=0 ^ numero_escritores>0 then signal(escritura)

else(mutex)

PS(Escritor):

wait(mutex)

escritura:=false;

if numero_lectores>0 ^ numero_escritores>0 wait(escritura)

else if numero_lectores>0 then signal(lectura)

else signal(mutex);

//Tras esto habria que modificar antes de la lectura el poner las instrucciones 'if numero_lectores>0 then signal(lector) else signal(mutex)'//

COMIDA DE FILOSOFOS

El problema reside cuando varios procesos requieren recursos que pueden estar utilizando otros procesos y al final se produce un bloqueo pasivo porque todos esperan a que se libere algo que no sueltan. Imaginemos una mesa con N palillos y N filosofos. Cada filosofo piensa o come, y para comer toma el palillo de su numero y el siguiente, (lo que implica que nos movemos circulamente por el numero de N palillos).

process type filosofo(id:Integer)

Begin

Repeat

pensar();

wait(palillo[id]);

wait(palillo[(id+1)mod N]);

comer();

signal(palillo[id]);

signal(palillos[(id+1)mod N]);

Forever

¿Pero que pasa si entran todos al mismo tiempo? Que todos consiguen un palillo pero no avanzan. Asi que hay que obligar a que se sienten como mucho n-1.

process type filosofo(id:Integer)

Begin

Repeat

pensar();

wait(sitio);

wait(palillo[id]);

wait(palillo[(id+1)mod N]);

comer();

signal(palillo[id]);

signal(palillos[(id+1)mod N]);

signal(sitio);

Forever

Begin

palillo: array [1..N] of semaphore;

initial(palillo[i],1);

initial(sitio, N-1);

End.

[apuntesum-blog]

Compiladores: Analizador Sintáctico

INTRODUCCIÓN

El análizador sintactico (AS) recibe una serie de secuencias de tokens desde el analizador léxico (AL) y ha de comprobar si ese orden es correcto. Tiene que informar y repararse de los errores sintácticos que ocurren frecuentemente pero no solucionarlos. La salida suele ser un árbol sintáctico. Realiza otras tareas para recoger la informacion sobre tokens y la tabla de simbolos, realizar el analisis semántico y generar codigo intermedio.

MANEJO DE ERRORES

La mayoría de errores son sintácticos y se pueden solucionar muy facilmente, pero siempre han de seguir el mismo patrón:

Informar con claridad y exactitud.

Recuperarse con rapidez (generalmente con modo pánico).

No retrasar el procesamiento de programas correctos.

GRAMÁTICA LIBRE DE CONTEXTO Y ARBOL DE DERIVACION.

El AS se basa en una gramatica que se define como una serie de reglas que derivan finalmente en una serie de nodos terminales (o símbolos de la gramatica). Al final se genera un arbol de derivación segun si tomamos la mano izquierda o la derecha.

E-> E+E E-> E*E E-> -E E-> (E) E-> id

Donde podriamos representar -(id+id) como una serie de normas: E -> -E -> -(E -> -(E+E) -> -(id+E) -> -(id+id).

Una GLC puede ser ambigua si hay mas de un arbol de derivaciónd istinto o si una sentencia por la mano izquierda y la derecha es diferente. Decimos además que la derivacion acaba en una forma sentencial segun si tomamos primero los simbolos mas a la izquierda o mas a la derecha.

El pivote se utiliza generalmente en un análisis descendente (mano derecha), donde tomamos el simbolo no terminal mas a la derecha que haya y aplicmaos reglas con él hasta que desaparezca.

S => zABz => zAbBbz => zAbbbz => zaAabbbz => zaaabbbz.

En el siguiente ejemplo puede verse como además el pivote puede no ser unico en una misma forma sentencial.

Con el analizador sintáctico necesitamos el uso de automatas con pila pues el AS recibe una gramatica libre de contexto (GLC). Donde un automata con pila para un simbolo de la entrada, con un simbolo en el tope de la pila puede pasar a una serie de estados. El automata podrá terminar correctamente o bien en un estado final o bien agotando la entrada segun el modelo que se considere.

Suponiendo un automata con pila con la siguiente gramatica podriamos llegar a comprobar la cadena a+a*a.

(q,λ,S) -> (q,λ,S+A) -> (q,λ,A+A) -> (q,λ,B+A) -> (q,λ,a+A) -> (q,λ,+A) -> (q,λ,A) -> (q,λ,A+B) -> (q,λ,a+B) -> (q,λ,+B) -> (q,λ,B) -> (q,λ,a) -> (q,λ,λ)

Hay muchas otras combinaciones pero no verifican dicha cadena y por eso mismo, porque se hacen calculos paralelos no merece la pena usarlos para simular. Además hay otros problemas segun hagamos una derivacion por la izquierda o por la derecha, por ejemplo con la siguiente gramatica, el calculo a+a*a se realiza ambigüamente:

Aplicaremos la regla para nuestra gramatica: suma, resta, division empiezan por asociatividad izquierda, el resto de operadores por la derecha.

En cuanto a problemas con la ambiguedad el caso mas importante será la sentencia if-else. Los lenguajes son sensibles al contexto y por tanto no podremos representar todos los lenguajes con este analizar sintáctico.

ANALISIS ASCENDENTE Y DESCENDENTE

El análisis descendente parte del simbolo inicial (raiz) y hace todas las operaciones que puede con el simbolo no terminal mas a la izquierda, seguidamente pasara al segundo mas a la izquierda y así sucesivamente. Al final llegará a todos los nodos hoja (simbolos terminales) de la gramatica.

El análisis ascendente hace lo opuesto. Partiendo de los nodos hoja (simbolos terminales) se intenta construir hacia arriba el arbol hasta llegar al simbolo inicial (raiz) de la gramatica.

Los metodos ascendentes y descendentes suelen ser generales y los mas eficientes son:

LL (análisis descendente): Devuelve un conjunto de dereivaciones por la izquierda.

LR (análisis ascendente): Devuelve un conjunto de derivaciones por la derecha.

ALGORITMOS DE LA TRANSFORMACION DE GRAMÁTICAS

Para utilizar una gramática propia, primero tenemos que asegurarnos que es una gramática λ-libre, luego se quitan los ciclos (S->A y A->S), luego eliminamos las variables improductivas (aquellas que no llevan a simbolos terminales) y los simbolos inaccesibles (simbolos no terminales a los que no puedo llegar nunca) y tendría una gramatica propia.

Con una gramática propia podemos eliminar la recursividad por la izquierda, lo que nos devuelve una gramatica no recursiva (algo que neceistamos pues los bucles infinitos son muy malos). Aparte podríamos hacer la factorización que no es necesaria pero suele aliviar problemas.

ELIMINACION DE LA RECURSIVIDAD INMEDIATA IZQUIERDA

La recursividad inmediata sucede cuando un simbolo no terminal se descompone en él mismo y otra cosa mas, asi que podrian hacerse bucles infinitos sobre sí mismo:

E -> E+T | T

T -> T*F | F

F -> a

La recursividad: E -> E+T -> E+T+T -> ...

Comprobar que es una gramatica al menos λ-libre.

Analizar cada símbolo y ver si tiene recursividad.

Si tiene tendremos dos tipos de variables α (aquellos simbolos que acompañan al no-terminal que provoca la recursividad) y β (cualquier otro numero que no provoque recursividad).

El recursivo ahora será cada una de las variables β ó cada una de las variables β concatenadas con un estado K'.

El nuevo estado K' tiene de nuevo cada una de las variables α ó cada una de las variables α concatenadas con el estado K'.

E-> E+T | T (α1=+T)(β1=T) E-> T | TE' E'-> +T | +TE'

ELIMINACION DE LA RECURSIVIDAD IZQUIERDA

La recursividad izquierda es la recursividad inmediata más la que se produce al intentar solucionar la inmediata. Las variables se ordenan con un valor creciente y hay que evitar que se produzcan transiciones a estados de menor valor. Se divide en varios pasos:

Ordenar todos los simbolos no terminales.

Para i=1 hasta n: Eliminar la recursividad inmediata izquierda.

Para i=1 hasta i: Fijandonos en el siguiente, si hay recursividad en las anteriores se soluciona.

EJEMPLO

E = E+T | T

T = T*F | F

F = a | Ea

i=1

Eliminar recursividad inmediata izquierda.

E = T | TE'

E' = +T | +TE'

Reglas que transiten de i=2 a i<2 (T->E)

No existen, paso abortado.

i=2

Eliminar recursividad inmediata izquierda.

T = F | FT'

T' = *F | *FT'

Reglas que transiten de i=3 a i<3 (F->E)

F = a | Ea -> F = a | Ta | TE'a

Reglas que transiten de i=3 a i<3 (F->T)

F = a | Fa | FT'a | FE'a | F'E'a | FT'E'a

i=3

Eliminar recursividad inmediata izquierda.

F = a | aF'

F' = a | T'a | E'a | T'E'a | aF' | T'aF' | E'aF' | T'E'aF'

FACTORIZACION IZQUIERDA

La factorizacion izquierda reside en coger la parte diferente en un simbolo no terminal y sustituirlo por un simbolo nuevo que contenga las diferencias. Como ya hemos visto no es necesario que sea λ-libre por lo que puede hacerse en cada momento.

I -> id | id()

Si recibo id, ¿espero un parentesis o no?

I -> idI'

I' -> λ | ()

En el siguiente ejemplo veremos como si usamos una gramatica que no es propia (lambda-libre, sin simbolos innecesarios y sin ciclos) el algoritmo de eliminación de la recursividad izquierda no funciona. Nuestro ejemplo es una gramatica con ciclos:

A -> B|a B -> C|b C -> A|c

i:=1

Eliminacion de la recursividad inmediata en A (A->A_) No tiene. Combinaciones de i=2 que generen recursion (B->A) No tiene

i:=2

Eliminacion de la recursividad inmediata en B (B->B_) No tiene Combinaciones de i=3 que generen recursion (C->A) C = B|a|c Combinaciones de i=3 que generen recursion (C->B) C = C|b|a|c

i:=3

Eliminacion de la recursividad inmediata en C (C->C_) C = b|a|c|bC'|aC'|cC' C'= C' //ERROR.

METODO LL

El metodo LL es un analisis descendente de derivaciones izquierdas. Que se aplica sobre autómatas con pilas. Ya vimos como se derivaba en un automata con pila, sin embargo volveremos a verlo para el problema de la indeterminacion de caminos.

Supongamos una gramatica que verifique la cadena 'cabd' con las siguientes reglas de produccion:

S->cAd

A->ab|a

Automata: un solo estado q, que se verifica con la cadena vacía. Tiene una serie de funciones de transiciones δ, y el simbolo de la pila es el inicial de la gramatica S.

M={{q},{a,b,c,d},{a,b,c,d,A,S},δ,q,S,λ}

Las funciones de transición serían:

δ(q,λ,S) -> (q,cAd)

δ(q,λ,A) -> (q,ab)

δ(q,λ,A) -> (q,a)

δ(q,a,a) -> (q,λ)

δ(q,b,b) -> (q,λ)

δ(q,c,c) -> (q,λ)

δ(q,d,d) -> (q,λ)

La simulacion sería:

(q,cabd,S) -R.1-> (q,cabd,cAd) -R.6-> (q,abd,Ad) -R.4-> (q,abd,abd) -R.4-> (q,bd,bd) -R.5-> (q,d,d) -R.7-> (q,λ,λ)

Pero podriamos haber tomado otras decisiones. El metodo LL busca hacer un solo camino que no cometa errores, por lo que tiene que tener la capacidad de saber mirando lo que hay en la pila, lo que hay en la entrada y las reglas que tiene, cual ha de coger. Por lo que nunca ha de poder dudar entre dos o mas opciones.

En nuestro ejemplo la regla A->ab|a es la que nos permite tomar varios caminos, pero, ¿que pasa si sacamos factor comun?

A->aA'

A'->b|λ

Dado el simbolo de la entrada, lo que hay en la pila y un unico siguiente token podemos tener la LL(1) donde solo hay una eleccion posible. Aunque haga la eliminacion de la recursividad por la izquierda, la factorización y elimine la ambigüedad NO ES SEGURO que genere un lenguaje LL(1).

CONJUNTO PRIMERO

El conjunto primero(x) se define con las reglas:

Si x es un simbolo terminal, es él mismo: primero(a) -> a.

Si x es λ entonces se añade a primero(x).

Si x deriva en algo como (y1y2y3...) su primero será primero(y1) y si este puede ser λ en algun momento, entonces será primero(y2) y asi hasta que alguno no sea λ.

Calculo de primero para la siguiente gramática libre de contexto

CONJUNTO SIGUIENTE

El conjunto siguiente(x) solo se calcula para los no terminales. Son todos los siguientes tokens que me permitirian escoger entre un camino y otro. De forma pre-definida, para el primer simbolo no terminal $ (marcador de final) pertenece siempre.

Siguiente(Bb) -> b.

Si una regla de produccion encontramos una lambda, NO se añade, se hace el primero del termino que lo invoca sin lambda.

El siguinte de una regla de produccion es el ultimo terminal, o, si es un no-terminal, las reglas donde E aparezca a la derecha y tomamos el símbolo que tenga a su derecha, terminal o no.

TABLA DE ANALISIS CON PREDICT

Para realizar una tabla de análisis necesitamos la funcion predict, esta consiste en una matriz de simbolos terminales y simbolos no terminales y su construccion es la siguiente:

E-> TE'

E' -> +TE'|λ

T-> FT'

T' -> *FT'|λ

F -> ( E )|id

Numeramos las reglas: 1(E->TE'), 2(E'->+TE), 3(E'->λ)...

Aplicamos Primero(regla1), Primero(regla2)...

Rellenamos la tabla con los predicts, donde en caso de toparnos con un lambda, invocamos al siguiente del simbolo no-terminal sobre el que estamos:

Predict(1)=primero(TE') = Primero(T) = Primero(F) = {(,id} Predict(2)=primero(+TE') = {+} Predict(3)=primero(λ) -> Siguiente(E')={$,)} Predict(4)=primero(FT') = {(,id Predict(5)=primero(*FT') = {*} Predict(6)=primero(λ) -> Siguiente(T')={),$,+} Predict(7)=primero((E)) -> {(} Predict(8)=primero(id) -> {id}

[apuntesum-blog]

PCD: PROGRAMAS CONCURRENTES

PROGRAMAS CONCURRENTES

En un programa concurrente no sabemos cual es el orden de ejecucion de las instrucciones (si un programa tiene dos procesos P1, P2 con 2 instrucciones cada uno, el orden puede ser el usual, alternados, inversos...) con lo cual hay que considerar todas las posibilidades.

Supongamos los siguientes procesos:

Y de forma interna, cada proceso hace, de forma secuencial, lo siguiente:

Bien, si el proceso uno se ejecuta primero y luego el proceso dos, no pasaría nada (o al revés) pero si ejecutamos simultaneamente ambas instrucciones. Veríamos lo siguiente:

x = 0 (inicialmente)

Reg1 = 0

Reg2 = 0

Reg1 = 1

Reg2 = 1

x = 1

x = 1

Con lo cual la ejecución resulta fallida, y nosotros tenemos que garantizar que esto jamás ocurra. Para eso tenemos que hacer que se ejecute la operacion de incremento de forma ininterrumpida (cuando la haga uno el otro se espere) y es lo que llamamos ejecución atómica.

CARACTERISTICAS DE LOS SISTEMAS CONCURRENTES

Si tenemos dos conjuntos L(Sk) = {a1, a2,..., ak} que representa las variables que son accedidas en modo lectura y E(Sk) = {b1,b2,...,bk}, dos instrucciones Sm y Sn se pueden ejecutar concurrentemente si y solo si:

L(Sm) ∩ E(Sn) = ø

E(Sm) ∩ L(Sn) = ø

E(Sm) ∩ E(Sn) = ø

Dicho de otro modo, o leemos-escribimos cosas diferentes, o escribimos cosas diferentes. Lo unico que no importa es la lectura-lectura que siempre puede hacerse, en cualquier otro caso hay que poner dicha sentencia en ejecución atómica.

SINCRONIZACIÓN: EXCLUSIÓN MUTUA

Dado un recurso no compartible (un recurso que varios procesos utilizan pero no simultaneamente, como la pantalla, el disco duro, memoria...) se conoce como exclusión mutua a una sincronización necesaria para que los procesos utilicen el recurso pero no simultaneamente.

La zona de código donde se lleva a cavo la exclusión mutua es la 'seccion crítica'. Si un proceso está en la sección crítica ningún otro proceso debe de estar en la suya.

Segun la siguiente imagen, podemos ver que hay varias secciones críticas donde aparecen problemas por el indeterminismo:

Writeln(n) <-> Writeln(i)

Writeln(n) <-> Writeln("ok")

i:=0 <-> i:=2;

i<n <-> n:=5

r:=r+1 <-> r>3

PROTECCION DE LA SECCIÓN CRÍTICA

La sección crítica (SC) estará protegida por una serie de instrucciones que, previamente, formaran el protocolo de entrada (PE)para permitir que un proceso accceda cuando deba a la seccion crítica (y bloquee a los demas) y unas instrucciones posteriores que permitiran que otros recursos sean notificados de que la sección crítica ya está libre llamado protocolo de salida (PS).

Siempre, siempre, han de garantizarse tres fases:

Exclusión mutua: Un solo proceso accede al mismo tiempo al recurso (R). Mientras un proceso está en su sección critica relativa a R ningun otro puede estar ejecutando dicha seccion critica (no simultaneidad). Cuando R está siendo utilizado por un proceso, los demas se quedan bloqueados a la espera de que R quede libre.

Progreso de la ejecución: Si R está libre, cualquier proceso podrá entrar a su sección critica relativa a R.

Limitación en la espera: Ningun proceso esperará ilimitadamente por acceder a R.

CONDICIONES DE SINCRONIZACION

La condicion de sincronización es una propiedad de que un proceso NO realice un evento hasta que otro proceso haya realizado una accion determinada. Suponiendo el siguiente esquema de impresora, podemos ver que hay una serie de condiciones de sincronización:

El lector ha de parar cuando el buffer esté lleno.

El gestor ha de evitar tomar la imagen del buffer si el buffer está vacío.

El gestor ha de evitar meter imagenes a la cola de impresión si está llena.

El impresor no ha de imprimir si no hay nada en la cola de impresion.

TIPOS DE SINCRONIZACIÓN: INHIBICION DE INTERRUPCIONES

La mas antigua de las soluciones (además es via hardware) consiste en bloquear todas las interrupciones (lo que incluye la señal de reloj del procesador que hace el cambio de contexto) asi se obliga a que la instruccion se realice sí o si, por lo que la seccion crítica quedaría tal que así:

Pero esto está mal, primero porque los usuarios controlan la habilitacion/deshabilitacion de interrupciones y si se olvidaran de activarlos el SO muere. Además no es valido para los multiprocesadores. Asi que hay que hacer otras técnicas via software.

ESPERA OCUPADA: ALGORITMO DE PETERSON

Los procesos esperan para entrar en la seccion crítica mediante una comprobacion continua del valor de algunas variables, ocupando el tiempo de la CPU (estan en un bucle infinito hasta que les dicen que pueden pasar a la seccion critica), no obstante aunque es funcional se añaden tantas lineas que no es rentable. Lo idoneo sería un sistema de turnos (para saber a que proceso le toca) y además una inicialización de la comprobación para que se garantice que algun proceso entra en la Sección Crítica por primera vez.

EJERCICIOS

El siguiente programa se espera que, como resultado de su ejecución se imprima 110 o 50. ¿Es correcto el algoritmo?

En efecto, no. Como podemos ver está la operacion x:=x+10 y la comprobacion x>100. Asi que puede pasar algo como esto que haría que no saliera ni 110, ni 50.

x=100;

if x>100 -> false

x:=x+10 (110)

write(x-50) -> 60

Supongamos la instruccion atomica TAS donde x es una variable local y c una variable global que simbolica si la Seccion Crítica está libre (0) o si está ocupada (1).

Utilizando la instruccion anterior, construir los protocolos de entrada, de salida y la inicializacion de las variables para dar una solución al problema de la exclusión mútua de las secciones criticas siguientes:

Inicialización: c=0;

PE: do TAS(x) until x==0 //asi sabre que c=0

SECCION CRITICA

PS: c=0;

EJERCICIO 1: Supongamos que tengo un proceso que cuando recibe una señal, hace 'n=n+1' y que otro proceso, cuando pasa una hora, escribe y resetea dicho contador 'write(n)-n=0' y que trabajan en armonía. ¿Que puede pasar?

n:=n+1 -> write(n) -> n:=0 write(n) -> n:=n+1 -> n:=0 write(n) -> n:=0 -> n:=n+1

El primer caso es el correcto, pues escribimos el numero de señales recibidas. El segundo está mal pues se pierde una señal y el tercero aunque podría parecer que está bien si suponemos que las operaciones tendrian que realizarse de forma secuencial, primero se añade y luego se escribe, no al reves (aunque no se pierde la seal sino que se añade al siguiente ciclo).

EJERCICIO 2: Supongamos que tenemos que leer en la posicion de memoria 20 y en la posicion de memoria 88 escribir, suponiendo que no son instrucciones atomicas y que se componen de saltar(direccion) y leer/escribir. ¿Qué puede pasar?

Saltar(20) -> Leer -> Saltar(88) -> Escribir Saltar(20) -> Saltar(88) -> Leer -> Escribir Saltar(20) -> Saltar(88) -> Escribir -> Leer Saltar(88) -> Escribir -> Saltar(20) -> Leer Saltar(88) -> Saltar(20) -> Escribir -> Leer Saltar(88) -> Saltar(20) -> Leer -> Escribir

La primera y la cuarta estan bien pues sería la ejecución secuencial de ambos procesos en un orden u otro, el resto son erroneas.

[apuntesum-blog]

AEDII: Análisis de Algoritmos

ANÁLISIS DE ALGORITMOS

Un algoritmo es un conjunto de reglas para resolver un problema. Su ejecución requiere de unos recursos (tiempo, memoria...) para resolver un problema (de forma exacta o aproximada) o solo unos determinados casos de dicho problema.

RECURSOS CONSUMIDOS

Los recursos consumidos son variables y no son aplicables entre diferentes programas, algunas veces un recurso depende del numero de datos que entran, otras de como se representa dicha entrada (su tipo)...Supongamos el siguiente algoritmo, ¿Que hace? ¿Cuántos recursos de tiempo y memoria consume el siguiente algoritmo?

i:=0 a[n+1]:=x repetir i:= i+1 hasta a[i]==x

Este algoritmo es una busqueda secuencial que va desde la posicion [1] hasta la posicion [n+1] como máximo. Ademas se conoce como búsqueda secuencial con centinela pues gracias a la sentencia 'a[n+1]:=x' el algoritmo tiene fin y dará un resultado válido.

En cuanto a los recursos que gasta, depende. Depende del valor de n (que codifica cuan grande es el array) y de x (de donde se encuentre), además de que tipo sea el array (no ocupa lo mismo un array de strings ni hacer la operacion de strings que la de enteros).

Podemos calificar los recursos de varias formas:

Factores externos: No se tendrán en cuenta a la hora de operar pues no son medibles en nuestros ejercicios, dependen del ordenador donde se ejecute, que lenguaje de programación, la implementacion del algoritmo...

Tamaño de los datos de entrada: Cuanto mas grande sean es posible que haya que utilizar otras estructuras que consumiran memoria y tiempo.

Contenido de los datos de entrada: Existen tres casos importantes, el promedio (tp), el mejor caso (tm) y el peor caso (tM).

La media aritmetica NO es el tiempo promedio de un algoritmo sino que es un sumatorio de cada caso sobre el tiempo que realmente tarda y la probabilidad de que surja dicho caso: Σ[t(α)·p(α)]. Debido a que conocer el mejor y el peor tiempo con exactitud es imposible, lo mejor sería acotar el tiempo del algotirmo en cotas inferior y superior. El peor-peor caso no podrá ser empeorado nunca, y el mejor-mejor caso nunca podrá ser mas breve, asi se puede acotar el algoritmo entre unos valores correctos.

¿Cual es el tamaño de la entrada?

Ordenar numeros: Numero de datos introducidos.

Calcular el factorial: El valor de dicho numero.

Sumar numeros demasiado grandes: El numero de cifras (codifica el tamaño de la estructura a usar) y el numero de numeros a sumar.

Multiplicar matrices rectangulares: El tamaño de la matriz a, el de la b, y el del resultado c.

Ejemplo: Algoritmo de busqueda secuencial con centinela. Mejor caso (Encontramos x en la 1ª posicion): tm(n)=a. Peor caso (no se encuentra x hasta el centinela): tM(n)=b·n+c

NOTACION

La notacion t(n) puede significar varias cosas:

Tiempo de ejecución en segundos t(n)=b·n+c suponiendo que b y c son constantes, con los segundos que tardan las operaciones básicas corresondientes.

Instrucciones ejecutadas por el algoritmo t(n)=2n+4

Ejecuciones del bucle principal t(n)=n+1 dado que generalmente el bucle es lo mas importante de un algoritmo.

El proceso básico de análisis de la eficiencia es conocido como el conteo de instrucciones (o de memoria). Para las instrucciones se sigue la ejeucción del algoritmo sumando todas las instrucciones que se ejecutan al igual que la memoria aunque en estos casos solo interesa cual es el pico mas alto de memoria usado (recordando que en la recurrencia la memoria sube y cuando se vuelve, alcanza el nivel que tenía antes de meterse).

CONTEO DE INSTRUCCIONES

Numero de instrucciones t(n) -> sumar 1 por cada instrucción o linea de código de ejecución constante.

Tiempo de ejecución t(n) -> sumar una constante (c1,c2) por cada tipod e instruccion o grupo de instrucciones secuenciales.

Bucles FOR: Se pueden expresar como un sumatorio con os límites del bucle como límites del sumatorio.

While & repeat: Si no pueden transformarse a un for, tendremos que saber que probabilidad tienen de que se ejecuten.

Llamadas de procedimientos: Intentamos calcular el procedimiento que no llame a otros.

If, case: Precedir.

EJEMPLOS:

Donde podemos ver que el segundo sumatorio es para el incremento de k:=1 y para la suma, que las otras 3 son para el incremento de j:=1, la inicialización de la suma y la escritura en c[i,j] y la otra operación es para el incremento de i.

Aqui podemos apreciar que el algoritmo principal se divide en varios casos, por lo que podríamos decir que t(<0) = 2 (if+error), t(0|1) = 3 (if+case+return). Las tres primeras instrucciones son (fnm2+fnm1+fn) aunque en cualquier caso el if deberia de estar contemplado tambien.

El truco de esta funcion es considerar que el while no es mas que un for que vá desde key a n*n incrementandose de uno en uno. Ahora bien, hay un if que no siempre se cumple, no sabemos la probabilidad que tiene de darse pero en el mejor caso se cumple (y solo hacemos dos instrucciones (if+i)) y en el peor no (if+i+j). No obstante hay un truco, en el while, se incrementa el contador una vez pero se comprueba dos veces si se ha llegado al limite, lo que hace que tenga una instruccion dentro en su interior y otra que añade uno a 'key' y que ya se sale del bucle.

Por lo que entre el mejor caso tm(n) y tM(n):

Antes de poder calcular el tiempo tenemos que saber que ocurre en el if, no hay mejor caso ni peor pues en términos de instrucciones ambos ejecutan lo mismo, sin embargo ¿que ocurre si el numero n es par o impar? Podriamos decir que si n par tiene un numero de instrucciones mayor es el peor caso, y si no, es el mejor.

Para un n par:

t(n) -> [i=1] i:=1~n(2)

t(n) -> [i=2] j:=1~2(2)

t(n) -> [i=3] i:=2~n(2)

t(n) -> [i=n] i:=n~n(2)

t(n) -> [i=n-1] i:=1~n(2)

Como vemos tenemos un sumatorio completo cuando i:=1 y despues, cada 2 sumatorios tenemos otro [1-2][3-n]...[1-(n-1)][n-n] lo que quiere decir que tenemos 1 + (n-1)/2 sumatorios completos.

Para un n impar:

t(n) -> [i=1] i:=1~n(2)

t(n) -> [i=2] j:=1~2(2)

t(n) -> [i=3] i:=2~n(2)

t(n) -> [i=n] i:=1~n(2)

Sucede algo muy parecido salvo que la ultima transición es completa, es decir en vez de 1 tenemos 2 completas y el resto son semicompletas. Asi que 2 + n-1/2. Asi que hay un 50% de probabilidades de que tomemos una instruccion extra en las del bucle o no.

La probabilidad con la que un numero es mas grande que otro es, suponiendo una cantidad infinita de numeros, el 50%. Lo mismo que de ser igual o mayor pues ser ugual es de 1/n lo que hace que sea proxima a 0. Bien, el problema es que aquí se hace la sobreescritura de dicho numero a[n] lo que hace que la probabilidad no sea fija. Si el primero es mas grande que el ultimo (entramos por primera vez en el bucle) quiere decir que un numero es mas grande que otro 1/2. Si la segunda vez, vuelve a entrar, significa que el segundo numero es mas grande que el primero (y que el ultimo). Lo que implica que un numero es mas grande que otros tres (1/3). Al final, acumulativamente la probabilidad para n numeros es de 1/2 + 1/3 + 1/4 +...+1/n. Pero esto no es ninguna sucesión aritmética o geometrica, con lo cual necesitamos integrales (donde 1/i+1 es ln(i+1)).

El bucle for va desde i:=i hasta el log2(n) (porque vamos multiplicando por 2 el indice). En el mejor caso, no entramos nunca en el if, en el peor, entramos siempre.

A diferencia del problema anterior la probabilidad es siempre del 50% de tomar una instruccion (no entrar en el if) o tomar dos.

NOTACIONES ASINTÓTICAS

Indican como crece t para varoles suficientemente grandes, podemos diferenciar cuatro tipos de operadores:

Orden de complejidad (f(n)->O(f)): O(f) es el conjunto de todas las funciones que pueden ser acotadas superiormente a partir de una constante real 'c' tras cierto entero n. El orden de complejidad permite simplificar el comportamiento de la funcion del algoritmo que ha de ser la más optima y cercana posible.

t(n) < c·f(n)

Por ejemplo para la funcion t(n)=n+2 -> O(n) porque si multiplicara n*2 ya tendría acotada la funcion t(n) para n=3.

n²-8 ∈ O(n²) //cierto

(n+1)²∈ O(n²) //cierto

3^n ∈ 2^n // falso pues (3/2)^n es mayor que cualquier c

3n ∈ O(n²) //cierto

Si f(n) = O(n), ¿k^(2(fn)) = O(2n)? No. Porque 2^(2n) = (2²)^n = 4^n.

Cota inferior (f(n)-> Ω(f)): Ω(f) es el conjunto de todas las funciones que pueden ser acotadas inferiormente a partir de una constante real 'c' tra cierto entero n. La cota inferior permite detectar cual es la cantidad mínima de recursos que se necesitan para ejecutar correctamente el algoritmo.

tm(n) = 3n  -> tm(n)∈Ω(n)

tM(n) = 7n+8 -> tM(n)∈O(n)

t(n)∈θ(n)

Orden exacto (f(n) -> θ(f)): θ(f) es el crecimiento exacto de una funcion, solo se puede usar si la cota inferior y el orden de complejidad son iguales. O si por ejemplo el algoritmo siempre hace un numero fijo de instrucciones no dependientes.

tm(n) = 3n

tM(n) = n²

θt(n) -> no puede calcularse.

O pequeña (f(n) -> o(f)): o(f) busca comparar algoritmos del mismo orden para saber cual de ellos es mejor. Si en el orden de complejidad cojemos el termino de mayor grado a secas, aqui preservaremos la constante multiplicativa que tenga.

f(n) = 7n² ~> O(n²) ~> o(7n²).

t(n) = 3.2n²+8n-9 ∈ o(3.2n²)

Ojo: o(f)⊆O(f) cierta si no estuviera el igual, pues O(f) contiene cualquier funcion o(f) pero no al reves. Por lo tanto que o(f) está contenida en O(f) es cierto pero no lo opuesto.

PROPIEDADES DE LAS NOTACIONES

Transitividad: Si f∈O(g) y g∈O(h) entonces f∈O(h), lo mismo para Ω.

f<=c*g

g<=c'*h

f<=c*g<=c*c'*h

2(n+1)∈O(n) y n∈O(n²) == 2(n+1)∈O(n²)

Pertenencia: O(f)=O(g) <-> f∈O(g) y g∈O(f) que es lo mismo que O(f)⊆O(g) <-> f∈O(g). No obstante, dadas dos funciones f y g se cumple O(f)⊆O(g) ó la opuesta, pero no ambas.

Maximo: Tanto con el orden de complejidad como en el límite inferior, cojemos siempre el término de máximo grado y se le quita el resto de constantes. Además esto permite que cosas como el logartimo puedan solucionarse muy rápidamente.

O(2^n+ n⁶+n!) -> O(n!)

log10(n) = log10(2) * log2(n) -> O(log2(n)) | o(log10(2)*log2(n))

EJERCICIOS

p:=0

para i=1...n hacer

p:=p+i*i

para j=i...h hacer

escribir(a[p,j])

finpara

finpara

El problema es que con cada iteración del segundo para se ejecuta de formas diferentes porque se modifica el valor de p en base al valor de i, asi que hay que intentar ver como predecir el valor de p:

i=1 -> p=0+1²

i=2 -> p=0+1²+2²

i=3 -> p=0+1²+2²+3²

i=n -> p=0+1²+2²+3²+...*n²

Que es lo mismo que un sumatorio desde k=1 hasta i de k² que al no ser una sucesión aritmética ni geometrica hay que aproximar por una integral

Calcular el orden de complejidad, cota inferior y orden exacto del siguiente algoritmo

j:=1

para i:=1...n hacer

escribe(j+i)

j:=j+1

finpara

En este algoritmo no existen ni peores ni mejores casos porque para un n el que sea siempre se ejecutara el mismo numero de veces por loq ue lo que calculemos será el orden exacto que debe de ser lo mismo que la cota inferior y el orden de complejidad.

Con lo cual: t(n)∈θ(n) -> O(n) y Ω(n).

Calcular el orden de complejidad, cota inferior y orden exacto del siguiente algoritmo:

i:=1

j:=1

mientras i<=n y j<=n hacer

si a[i,j+1]<a[i+1,j] entonces

j=j+1

sino

i=i+1

finsi

finmientras

Antes de nada, ni el peor caso o el mejor caso se van a diferenciar por el numero de instrucciones que hacen dado que siempre se ejecuta el mientras, luego el si y depende de lo que ocurra, o el j=j+1 o el i=i+1 pero siempre hara 3 por iteracion. Ahora bien, el mejor caso sería que creciera una de las dos variables lo mas rapido posible (o que siempre se cumpla el si o que no) asi en n pasos tendriamos un i=n+1 o j=n+1. ¿Y el peor? Podria ser ir alternando entre las condiciones o incrementar una de las dos variables hasta que seai gual a n y luego hacer que la otra se salga, lo que sería hacer 2n operaciones. ¿Puede hacerse?

Vamos el peor caso para una matriz (n=3) de 4x4.

Como podemos ver con la condicion la primera fila es siempre mas grande que la segunda salvo el ultimo elemento (para evitar que j>n) y luego se invierte dicha condicion (para que i>n) en 2n pasos tenemos el peor de todos. Y al mismo tiempo, la mejor sería solo el primer paso. Asi que es posible y hemos demostrado que tanto el peor como el mejor caso han ocurrido.

Por lo que:

tm(n) -> Ω(n)

tM(n) -> O(n)

t(n) -> θ(n)

Calcular el orden de complejidad, la cota inferior y el orden exacto del siguiente algoritmo:

para i=1...n hacer

j=i+1

mientras j<=n y a[j]<a[i] hacer

a[i]:=a[j]

j++

finmientras

finpara

Bien, aqui tenemos que volver a ver cual es el mejor caso y cual el peor. Lo mejor sería que nunca se hiciera el mientras, la primera condicion se va a realizar casi siempre asi que, ¿hay alguna forma de que la segunda no se cumpla nunca? La condicion a garantizar es que a[i]>a[j] y esto hay que comprobarlo para un j creciente. Ergo, si a[i] es mayor que todos los que le siguen, siempre se bloqueará (o incluso si todos son iguales). Ergo un ejemplo podría ser:

10 -> 9 -> 8 -> 7. 0 -> 0 -> 0 -> 0.

La peor sería que siempre se cumpliera, no ocurre nada al sobreescribir el array pue ssi grabamos la posicion 1, empezamos la siguiente vez en la dos, al final si mi array empieza como:

3 -> 2 -> 1 || 1 -> 2 -> 1 || 1 -> 1 -> 1

Con lo cual:

tm(n) -> Ω(n)

tM(n) -> O(n²)

t(n) -> No puede calcularse.

[apuntesum-blog]

Compiladores: Analizador Léxico

INTRODUCCION AL ANALIZADOR LÉXICO

La tarea de crear nuestro compilador requerirá de varias cosas: un analizador léxico (que se encargara de identificar las palabras), un analizador sintáctico (que se encargara de las frases) y un analizador semántico (que mirara el sentido de la frase).

El analizador léxico se compone de expresiones regulares, los simbolos que se ignoraran (espacios en blanco, comentarios...) asi como los que acepta (identificadores, numeros...) seguiran las mismas propiedades, y tendran los mismos problemas, como que por ejemplo, no se permite el anidamiento.

OBJETIVO DEL ANALIZADOR LÉXICO

A grandes rasgos identificar que las palabras no tienen simbolos extraños y eliminar aquellas cosas que no nos interesen.

El analizador léxico (AL) lee los caracteres de entrada y elabora una secuencia de tokens (que son las unidades de control y serían los nodos hoja de la ER) de la gramática.

Como lee directamente del texto fuente, hace otras funciones como eliminar comentarios, el exceso de espacios...

Guarda informacion de algunos componentes léxicos en forma de atributos.

Suponiendo la siguiente ER, que validaria el siguiente lenguaje 'x = 23' :

E: E = E | id | num

Podriamos decir que cuando lee x el token sería [id,'1'], cuando lee 23 el token sería [num,'2'] el segundo atributo puede ser dos cosas dependiendo de la implementacion, o bien es una posicion en una tabla de simbolos donde 1 podría ser 'x' y la posicion 2 '23' o directamente aquello que simbolicen.

A la hora de detectar errores, lo mas efectivo es detectarlos, recuperarse del error (ignorando por ejemplo todos los simbolos no existentes y quedandonos con lo importante) y pasar a los siguientes a fin de detectar mas de un error por compilación. Esto se conoce como el módo pánico.

Generalmente relaciona mensajes de error del compilador con el programa fuente, pero no puede detectar muchos errores pues solo ve una palabra particular en un momento concreto, a diferencia del sintáctico que podría ver toda una frase o el semántico.

EXPRESIONES REGULARES Y AUTÓMATAS

A partir de un alfabeto V con las operaciones de union, concatenacion y cierre se cumple:

El simbolo ø es una ER que describe el lenguaje L(ø) = ø.

El simbolo λ es una ER que describe el lenguaje L(λ) = {λ}.

Cualquier simbolo que pertenece al alfabeto es una ER L(a) = {a}

Si R1 y R2 son ER entonces R1|R2 tambien, que describe L(R1|R2) = L(R1)∪L(R2).

Si R1 y R2 sn ER entonces R1·R2 tambien, que describe L(R1·R2) = L(R1)·L(R2)

Si R1 es una ER entonces R1* tambien, que describe L(R*) = L(R)*

Asi mismo, un automata es una quintupla formado por:

Conjunto finito de estados.

Un alfabeto.

Una funcion de transición.

Un estado inicial.

Un conjunto de estados finales.

DISEÑO DE UN ANALIZADOR LÉXICO

Aunque usaremos FLEX para crear un módulo que identifique el léxico, las siguientes tareas han de realizarse, de una forma u otra en un analizador lexico.

Especificacion y reconocimiento de componentes léxicos: Identificando los tokens del lenguaje utilizando ER. Habrá que describir los lexemas que reconoceremos como tokens y los lexemas que ignoraremos.

Tendremos que establecer las cadenas del lenguaje formal con signifificado propio (palabras clave, operadores, signos de puntuación, identificadores, constantes...) para reconocerlas mediante automatas finítos. Cuanto mas sencillos e independientes mejor.

Generalmente, para reconocerlos se suelen llevar dos apuntadores de la frase, el primero para el inicio y el segundo para los caracteres de anticipacion (seguimos avanzando el segundo apuntador hasta que lleguemos a un simbolo que no puede formar parte del anterior) devolvemos dicho simbolo no valido a la entrada y todo lo anterior es un token y dicho token puede ser:

Palabras clave no reservadas: El AL las trata como un identificador y será el sintáctico quien las identifique.

Palabras clave reservadas:  Se han de reconocer o mediant euna tabla o un automata.

Comentarios: Reconocidos y eliminarse.

Blancos: Eliminarlos y si no delimitan, agrupar los lexemas.

Token EOF: Para saber cuando se ha terminado es interesante solo para el sintáctico.

Construccion del automata finito que reconozca las ER: O bien pasamos de ER a AFND y luego de AFND a AFD o convertimos la ER directamente a AFD. Una vez tengamos un AFD podemos minimizarlo o simularlo asi como compactar las tablas que tengamos.

Implementacion del automata infinito: Podriamos hacerlo a traves de una tabla de Karnaugh, el diagrama de transicion pero nosotros la haremos con la herramienta FLEX.

Diseño de la interfaz entre la entrada y el AL: Como leeremos desde un fichero, es bastante mas eficiente leer lineas y bloques, como dijimos anteriormente, lo normal serían dos apuntadores pero se puede mejorar con un buffer dividido en dos mitades o con el uso de centinelas pero nos es indiferente.

Manejo de Errores: Han de detectarse los errores e informarse (y si se recupera para detectar otros errores, mejor) con el modo pánico se ignorn los caracteres extraños hasta encontrar un caracter válido para otro nuevo token. No obstante, a veces la recuperación genera mas fallos, lo cual sigue siendonos indiferentes, si detecta mas de uno es mucho mejor.

Al final tendriamos un gran automata que reconoce simbolos en base a los identificadores, las constantes, los numeros, los simbolos especiales y cualquier otro caracter lleva a un estado no final. Las palabras clave no suelen ponerse como estados en el propio autómata.

El código generado empezaría analizando y preguntando si el caracter es diferente del final de fichero, mientras que lo sea, si es un espacio no se hace nada, si encontramos un caracter (letra minuscula, _ ó $ hasta que no encontremos un simbolo que no sea válido lo guardamos en el buffer y al final devolvemos el ultimo caracter no valido a la entrada) si es un digito es un numero y si es un simbolo especial solo tomaremos ese caracter y devolveremos el numero.

EJEMPLO

Supongamos que hemos de analizar la siguiente funcion, ¿como sería el análisis léxico de "float limitedSquare(float x) { return (x<=-10.0 || x>=10.0) ? 100:x*x; }".

Supondremos las palabras reservadas float, ap (abrir parentesis), cp (cerrar parentesis), al (abrir llaves), cl (cerrar llaves). Y operadores como menor, menori (menorigual), mayor, mayori (mayorigual), interr (interrogacion)-

[FLOAT,][ID,1][FLOAT,][AP,][FLOAT,][ID,2][CP,][AL,][RETURN,][AP,][ID,2][MENORI,][MENOS,][CONSTFLOT,3][OR,][ID,2][MAYORI,][CONSTFLOT,3][CP,][INTERR,][CONSTENT,4][DP,][ID,2][POR,][ID,2][PC,][CL,]

Donde las palabras reservadas 'float', 'return' no tienen un numero porque son reservadas ni cosas como 'menorigual' lo tienen porque no varía. Eso si, en una tabla de lexemas tendriamos:

limitedSquare

x

10.0

100

REDUCCION DE TABLAS DE KARNAUGH

A veces tenemos un automata con muchos estados vacios, asi que existe una forma mas sencilla de reducir la tabla (en los ejercicios a mano no tiene mucho sentido pues son manejables, pero suponiendo automatas con miles de estados es bastante adecuado).

El truco consiste en tener una tabla de todos los valores que parten desde todos los estados (tabla de elementos no nulos) y otra (compacta) que diga desde un estado, tomando el elemento numero x hay y transciones.

Si quisieramos saber a que estado vamos con [q0,b] iriamos a la tabla compacta, veriamos que empieza en el numero 1 y tiene 2 transiciones, asi que nos vamos a la tabla de elementos no nulos, miramos la primera, es con a. Pasamos a la siguiente, y vemos que es una transicion con b al estado q2. Conclusion [q0,b] -> [q2].

EJERCICIO 1: Definir una expresión en letras minusculas que reconozca con todos los id salvo aquellos que tengan las letras if:

L=a|b|c|..|z LsinI= a|b|...|h|j|...|z LsinJ= a|b|...|i|j|...|z

i | LsinI·L* | LsinI·LsinF·L* | i·f·L+ | L·LsinF·L*

EJERCICIO2: Definir una expresion regular que con letras, numeros y guion bajo forme los identificadores que, empiezan por letra, numero o guion bajo pero no pueden haber dos guiones bajos o un guion bajo al final

L=a|b|...|z|A|...|Z D=0|1|...|9 LD = LUD

L(_LD+)*

[apuntesum-blog]

PCD: Introducción a la Concurrencia

INTRODUCCION A LA CONCURRENCIA

La programación concurrente surge gracias a la necesidad de hacer mas óptimo el uso de la CPU. Para esto hacen falta el concepto de hilos (threads), lenguajes como Java y al propio internet.

DIFERENCIA ENTRE PROGRAMA Y PROCESO

Un programa es un conjunto de instrucciones, que no son mas que secuencias de lineas de código estático, no hace nada por si mismo hasta su ejecución y se encuentra almacenado en disco.

Un proceso, sin embargo, es un programa en ejecución que manipula objetos abstractos llamados datos y cuyo funcionamiento lo determina el propio programa del que viene. Un proceso se compone de: contador de programa; contenido de los registros; contenido de la pila y sección de datos. Ademas, un programa puede lanzar varios procesos que compiten o colaboran para llevar a cabo una tarea comun.

Asi pues un programa llama al sistema operativo y, segun si se indica o no en el programa, pueden surgir varios procesos que se trataran de forma indeterminada, quizas en orden, quizas en orden inverso...

PROCESO E HILOS

Un hilo es cada secuencia de control dentro del proceso que ejecuta sus instrucciones de forma independiente. La introducción de hilos pretende reducir la sobrecarga introducida por la gestion de multiples procesos y facilitar la interacción.

Un proceso es una entidad pesada, es decir, cuando se interrumpe un proceso para pasar a otro los datos que hay que almacenar son muy grandes y por tanto tienen un 'cambio de contexto costoso'. Un hilo, sin embargo, es una entidad ligera porque su estructura se almacena en el espacio de usuario y todos los hilos comparten la información del proceso por lo que un cambio de contexto es menos costoso.

A la derecha veremos todo lo que habria que guardar para un proceso y a la derecha, dentro del proceso los hilos que hay y que guardarian:

PROGRAMACION Y PROCESOS CONCURRENTES

Un proceso concurrente es aquel cuya primera instruccion tiene lugar entre la primera y ultima instruccion de otro proceso. Es decir si para hacer el proceso 1 paso por el inicio del proceso 2, puedo decir que el proceso dos es concurrente con el uno o viceversa.

La programación concurrente es aquella que hace uso de estos procesos concurrentes y que a través de una notacion llamada 'pascaf-fc' se hará uso de tecnicas para resolver los problemas inherentes a la programacion concurrente.

Las ventajas de una programacion concurrente son: una mayor velocidad de ejecución, resolucion de problemas inherente concurrentes (sistema de ventanas, tecnologias web, simulación...).

Mientras que sus principales problemas son: Sincronizacion (que dos procesos se entremezclen no significa que en cierto paso un dato deba de leerse antes que escribirse) y comunicacion (depende de si la memoria se comparte o no, tenemos que asegurarnos de que reciben la informacion correcta).

CONCURRENCIA Y ARQUITECTURAS HARDWARE

Aunque ignoraremos como funciona el hardware para permitir la concurrencia, podemos ver que existen tres tipos de concurrencia segun el hardware (si es monoprocesador o multiprocesador)

Sistemas Monoprocesadores: Poseen un solo procesador donde el SO alterna el uso de este entre los diferentes procesos (multiprogramación) y como solo hay un solo procesador, se comunican y sincronizan a traves de variables compartidas.

Sistemas Multiprocesadores: Divididos entre fuertemente acoplados (si tienen memoria común a todos los procesos, como en el monoprocesador) o debilmente acoplados (si tienen que comunicarse mediante paso de mensajes).

DISTINCIONES

Cabría añadir finalmente que no es lo mismo la programación concurrente que la paralela, la programación paralela no es mas que una forma particular de programación concurrente, donde todos los procesos se realizan de forma paralea mientras que la concurrente solo implica que se inicia un proceso entre el inicio y el final del otro (no simultaneamente).

La programacion distribuida, es finalmente, aquella basada en el paso de mensajes por lo que sigue siendo una programación específica de la concurrente.

EJERCICIOS

1) Escribir un programa compuesto por varios procesos concurrentes para multiplicar matrices de 3*3

//Teniendo en cuenta que los procesos se indican entre "cobegin" y "coend". Lo mas aconsejable es hacer el menor numero de procesos pues aunque ahora no existe mucho problema si tuvieramos miles de celdas se tardaria mas en cambiar de contexto que en realizar las operaciones. Por lo que, como la multiplicacion es celda * fila haremos un proceso para cada fila.

2) Escribir un proceso compuesto por dos procesos concurrentes para el contrar el menor numero de un array de enteros.

//Partimos el array en dos, le asignamos la primera mitad al primer proceso y la segunda mitad al otro. Una vez terminen (tendremos que asegurarnos de que están sincronizados, y esto lo hacemos fuera del "coend") miramos cual de los dos numeros, que son los mas pequeños de ambos mini-array, es el mas pequeño y lo devolvemos.

3) Construir un programa concurrente que explote al maximo la concurrencia al copiar un fichero f en un fichero g.

//Copiar es leer y escribir, asi que inicialmente podriamos decir que leer(t,s) y escribir(g,s) pero el hecho de que la concurrencia pueda no copiarse en el orden deseado (no sabemos si irá antes la lectura o la escritura) podemos asegurarnos de que si primero leemos la primera linea leer(f,s) y luego hago el bucle en "coend" cambiando "escribir(g,t)".

[apuntesum-blog]

ALF: Autómatas con Pila

AUTOMATAS CON PILA

Un automata con pila (AP) es un automata finito aumentado con una memoria tipo pila. Entre lo que se recuerda mediante los distinto estados y lo que queda guardado en la pila, se dispone de una información mas completa que permiten que los AP puedan validar cadenas que no son de formato regular (a^n b^n) no forman un lenguaje regular. Los AP se usan principalmente como modelo para el diseño de algoritmo de análisis sintáctico de programas.

FUNCIONAMIENTO DE UN AP A GRANDES RASGOS

Una configuración inicial en un AP es la configuración de inicio de ejecución y se expresa como (q0, w, Z) donde q0 es un estado inicial, w es la cadena y Z es el simbolo inicial de la pila. Este Z es lo que inicialmente hay guardado en la pila (la pila no es vacía) y tiene su propio alfabeto de pila que se denota con la letra Σ.

Configuración inicial de un AP con cadena de entrada aaab, cuya representacion es (q0,aabb,Z).

Configuracion intermedia tras leer 'aa' donde la representación es (q0, bb, aaZ).

En cada instante de ejecución el AP se encuentra en cierto estado actual, ha leido cierto simbolo de la cadena (simbolo actual( y ha extraido (pop) el simbolo tope de la pila. Aplicando esos tres parámetros se aplica la regla de transición correspondiente que permite avanzar en la entrada, cambiar de estar e insertar (push) cierta cadena de simbolos en la pila.

Los cambios de estado no dependen del estado actual y el simbolo leido, sino tambien del tope de la pila. El AP lleva a cabo un bucle de procesamiento donde aplica una transición en cada paso leyendo la cadena de entrada simbolo a simbolo sin retroceder y guardando/extrayendo simbolos de la pila. La ejecución termina cuando no se pueden aplicar mas transiciones.

ACEPTACION DE UNA CADENA EN UN AP

Hay varios tipos de automatas con pila:

PV: Automata con pila que no tiene estados finales, las cadenas se aceptan cuando se ha leido toda la cadena de entrada (se detecta 'fin de entrada') y la pila está vacia.

En un AP tipo PV a una configuración de la forma (q, λ, λ) será llamada 'configuracion de aceptacion' en la que para un estado cualquiera (q) del AP, si no quedan simbolos de entrada por leer y la pila está vacía se llegó al final.

EF: Automata con pila que tiene estados finales y las cadenas se aceptan cuando se lee toda la cadena de entrada y se acaba en un estado final.

En un AP tipo EF a una configuracion de la forma (qF, λ, γ) donde qF es un estado final, no quedan simbolos de entrada por leer y en la pila hay cualquier cadena de caracteres (o ningun caracter).

DEFINICION FORMAL DE UN AP

Un autómata con pila se define matematicamente como una 7-upla M-(Q,V,Σ,σ,q0,Z,F) y, como automata, es no determinista, con lo cual es posible alcanzar multiples estados o configuraciones.

Q: Conjunto finito de estados.

V: Alfabeto de entrada.

Σ: Alfabeto de pila.

q0: Estado inicial.

Z€Σ: Simbolo inicial de la pila.

FCQ: Conjunto de estados finales (puede ser vacío)

σ: Qx(VU{λ})xΣ -> P(QxΣ*) es la fncion de transición.

TIPOS DE REGLAS DE TRANSICION Y REPRESENTACION GRÁFICA

A cada caso de la funcion de transicion σ de un AP lo llamamos regla de transición y, podemos distinguir los siguientes tipos de reglas:

Regla de lectura de símbolo: con o sin insercion en pila y una opcion para un cambio de estado

(q,aw,AB) - (q',w,αB)

Se cambia el estado q a q', se avanza una posicion en la entrada (lee/salta el simbolo a pertence a V), se extrae el tope A y se inserta la cadena α en la pila. Si α = λ no se añade simbolos.

Ejemplo: Suponiendo que V={0,1}, Σ={Z,C,1}, tenemos que σ(q3,0,C) - (q1, 11C) es una regla de este tipo y tambien la regla σ(q3,0,C) - (q1, λ) que indica que extrae C y no se insertan simbolos en la pila. Estas reglas se representan:

(q3, 0101, C1C) -Regla 1: (q1, 101, 11C1C) (q3, 0101, C1C) -Regla 2: (q1, 101, 1C)

Regla de lectura sin simbolo (transicion lambda):

Ejemplo: σ(q3,λ,C)-(q1, 11C) y σ(q3,λ,C)-(q1,λ) se representan:

(q3, 0101, C1C) -Regla 1: (q1, 0101, 11C1C) (q3, 0101, C1C) -Regla 2: (q1, 0101, 1C)

Existen variantes y en dependencia de cuales escogemos aplicar podemos llegar a posibles finales no deterministas.

LENGUAJE ACEPTADO POR UN AUTOMATA CON PILA

Vamos a deducir el lenguaje que acepta este automata, supuesto por pila vacía ya que no tiene estados finales.

Inicialmente el tope de la pila es <, por lo que la unica regla aplicable desde la configuracion inicial es la regla 1 σ(q0,a,Z) - (q0,a). De aqui deducimos que todas las cadenas que acepta tienen que comenzar por a. Ahora en la pila no hay una Z sino una a.

La regla 2 σ(q0,a,a) - (q0,aa) permite que por cada a que se lea de la entrada, se elimine la a que hay almacenada en la pila y se añadan dos (se pone una a mas en la pila).

La regla 3 σ(q0,b,a) -> (q1,λ) es aplicable cuando se lee una cadena b de la entrada y aparece un a en el tope de la pila. Al aplicar la regla quitamos esa ultima a y cambiamos al estado q1.

La regla 4 σ(q1,b,a) -> (q1,λ) epermite que por cada b que se lea de la entrada, se extraiga una a de la pila. Y desde ese punto en adelante ya no se pueden leer mas a's por lo que las cadenas aceptadas tienen que leer b's despues de haber leido a's.

Y solo vacias la pila, aplicando la cuarta regla, cuando lees tantas a's como b's. Por lo que el lenguaje del automata es: LPV(M1) = {a^n b^n | n>0}

EJEMPLOS:

(q0,aabb,Z) -Regla1-> (q0,abb,a) -Regla2-> (q0,bb,aa) -Regla3-> (q1, b, a) -Regla4-> (q1,λ,λ)

(q0,abb,Z) -Regla1-> (q0,bb,a) -Regla3-> (q1,b,λ): No existe regla b,λ no se valida.

DISEÑOS CON AUTOMATAS CON PILA

Para simular el funcionamiento de un AP (que no ha de ser ni demasiado general ni muy estricto) conviene que el automata de la pila sea determinista por cuestiones de eficiencia. El logaritmo de un AP determinista tiene un tiempo de ejecucion de O(n).

Un AP determinista no es posible que a partir de una configuracion se puedan alcanzar dos o mas configuraciones distintas en un paso de cálculo, en otro caso será no determinista. Esto hace que no puedan haber transiciones para un simbolo y para lambda simultaneamente.

EJEMPLO: Diseñar un AP llamado Mwcwr que acepte el lenguaje {wcw^R | w€{0,1}* por pila vacía.

Al leer el primer simbolo 0/1 se apila pero se extrae Z de la pila, ya no se necesita para controlar cuando se han extraido todos los simbolos apilados. Si el primer simbolo que se lee es c se extrae Z pero no se apila nada.

Si no se lee una c en la entrada, vamos introduciendo los simbolos leidos en la pila.

Cuando se lee una c cambiamos de estado, para comenzar a comparar la cadena con lo que queda en la entrada (al no meter nada ahora solo he de comprobar que lo que hay en la pila coincida con el siguiente simbolo).

Si antes de la c se lee por ejemplo 001 en la pila entra 0-0-1, luego la cadena de entrada sera aceptada si y solo si la subcadena restante coincide exactamente con la de la pila.

Si la cadena de entrada es correcta la pila se vacia, en otro caso o no se vacía o no se termina de leer la entrada.

Supongamos que la entrada es 01c10 y ya he leido la c:

Asi pues las funciones de transición serían:

Y el automata per-se:

LENGUAJES LIBRES DEL CONTEXTO NO DETERMINISTAS

No todos los lenguajes libres de contexto pueden ser aceptados por autómatas con pilas determinas. Los AP deterministas y no deterministas no son equivalentes.

Un lenguaje es libre del contexto determinista si existe un AP determinista que lo acepta (pila vacia o estado final). Si solo se acepta por un AP no determinista entonces es un lenguaje libre del contexto no determinista.

Un jemplod e un lenguaje libr del contexto no determinista es el de los palíndromos, quee s parecido al anterior salvo que no tenemos un simbolo c en medio. Lwwr = {ww^R | w€{0,1}*}

A priori no podemos saber cuando se acaba de leer la primera mitad de la cadena de la entrada asi que incluimos transiciones considerando que entra por un lado y por otro. La funcion de transicion de este AP tipo PV es:

Supongamos que queremos comprobar si una entrada 0110 se valida, esto se realiza por arboles de calculos paralelos dado el no determinismo del autómata.

AUTOMATAS CON PILA Y GRAMATICAS LIBRES DEL CONTEXTO

El metodo GLCtoAP permite pasar de una gramatica libre de contexto a un automata con pila simulando derivaciones más a la izquierda en la gramtica partida.

Entrada (GLC): (Vn,Vt,S,P).

Salida (AP): Lvp(M) - L(G).

Se incluyen dos estados: Q = {q0, q1 y no hay estados finales.

El alfabeto de entrada V coincide con el alfabeto de los simbolos terminales G(V-Vt).

El alfabeto de la pila está formado por todos los simbolos de la gramatica mas el simbolo inicial de pila (Z).

La funcion de transicion: (q0,abb,Z)

[apuntesum-blog]

ALF: Gramatica Libre de Contexto

Supongamos el lenguaje de los palindromos de los numeros 0 y 1 como Lpal={w€(0,1)*|w=w^R}.

Una posible forma de definir un lenguaje puede ser de forma recursiva, a través de uno o mas casos bases y uno o mas casos recursivos. Segun el ejemplo:

CASOS BASE:

w = λ

w = 1

w = 0

REGLA RECURSIVA Si w€Lpal, entonces:

1w1 € Lpal

0w0 € Lpal

La gramatica describe formalmente todo.

P -> λ

P -> 0

P -> 1

P -> 1P1

P -> 0P0

Donde podemos distinguir:

P: Variables libres de contexto.

->: Transformacion.

λ,0,1: Simbolos del alfabeto.

GRAMATICA LIBRE DE CONTEXTO

Definimos una gramática libre de contexxto como una tupla:

G: (Vn, Vt, S, P)

Vn: Alfabeto.

Vt: Simbolos terminales (nodos hoja).

S: Simbolo inicial (raiz).

P: Reglas de producción.

REGLAS DE PRODUCCION

Un paso de calculo P -> 1P1 -> 10P01 -> 10001 es una extension de la derivacion, que consiste en sustituir esa variable por alguno de los elementos de la gramática libre de contexto que define el lenguaje.

Esto tambien puede verse como un arbol:

    P

  1 P 1

1 0 P 0 1

1 0 0 0 1

P =>* 10001.

Supongamos que queremos expresar el lenguaje de a's y b's donde las b's son dos veces mas grandes que las a's.

CASO BASE

w=λ

CASO RECURSIVO Suponiendo que w€L

awbb€La

S = λ, S = aSbb, S=λ|aSbb

Supongamos el ejemplo de los paréntesis balanceados (han de haber tantos parentesis de cierre como los de apertura).

Caso Base = ()€Lpb

Caso Recursivo 1 = w€Lpb -> (w)€Lpb.

Caso Recursivo 2 = x,y€Lpb -> xy€Lpb.

S -> ()

S -> (S)

S -> SS

ANALISIS SINTACTICO

Comprobar si una cadena es una sentencia de la gramática (si es derivable del simbolo inicial). Sea la gramática G con reglas S->ABA, A-> aAa|λ, B-> bB|b probar que aabaaaa es sintacticamente correcto (S->*aabaaaa).

S -> ABA -> aAaBA -> aabA -> aabaAa -> aabaaAaa -> aabaaaaa.

¿Y babb?

S -> ABA -> AbBA -> bA -> b //NO fallo sintactico S -> ABA -> AbBA -> baAa -> baa // NO fallo sintactico.

El arbol sintactico puede usarse de izquierda a derecha (MI) o de derecha a izquierda (MD). Supongamos que tenemos que hacer la derivacion izquierda con la siguientes reglas de (i+i*i):

E: E+E

E: E*E

E: (E)

E: i

MI: E=E+E -> E=i+E -> E=i+E*E -> E=i+i*i

   E

 E + E

i  E * E

   i     i

AMBIGÜEDAD

Una gramatica ambiegua es una gramatica que tiene una sentencia ambigua (una con dos arboles de derivacion diferentes) si hicieramos la derivacion veremos que lo mas bajo es la suma pero ¿se hace realmente la suma antes que la multiplicacion? No.

El problema de la gramatica es que es arbitraria y ambigua.

COMBINACION DE GLC

Si tengo dos GLC la unión, concatenacion, o clausura de ambos genera otro lenguaje libre de contexto.

L1={a^n b^n | n>=1 L2={c^n d^n|n>1}

S1=ab w€S1 -> S1: aSb S2=cd w€S2 -> S2: cSd

L1ºL2 = S -> S1S2 -> ab|aS1 º cd|cS2d

L1|L2 = S -> S1|S2 -> ab|aS1 | cd|cS2d

GRAMATICAS REGULARES

Generan lenguajes que pueden ser descritos por expresiones regulares:

Reglas de produccion:

A-> bC 

A -> b

A -> λ

Supongamos que queremos obtene rel atomata que sale del lenguaje de los numeros pares. Sabiendo que la GLC es 0|2|4|6|8|1S|...|9S

ALGORITMOS DE TRANSFORMACON DE GLC

Necesitamos encontrar un GLC en otro equivalente y que mejore el análisis sintactos y que funcionen adecuadamente y mejoren la eficacia del proceso. Para ello podemos:

Eliminar simbolos inutiles.

Transformacion a gramatica λ-libre

Eliminacion de reglas unitarias

Transformacion a gramática propia

ELIMINACION DE SIMBOLOS INUTIL

Variables que nunca generan nodos hoja y hay que quitarlos, o los simbolos inalcanzables a los que no llego nunca, primero se eliminan las impoductivas y luego las inalcanzables.

S -> aAS|AA A -> AbB|ACa|a B -> ABa|Ab|λ C -> Cab|CC D -> CD|Cb|e E -> dA

Eliminacion de variables:

1) Variables productivas: A(A->a), B(b->λ), D(d->e)

2) S = AA: Se salva, puedo llegar a simbolos terminales (aa).

E=dA -> Se salva, puedo llegar a simbolos terminales (da)

3) Si ya no quedan se eliminan los sobrantes.

Vproductiva={A,B,D,E,S}

C -> desaparece;

D = e

A = AbB | a.

Eliminar simbolos inalcanzables.

1) Variables accesibles: {S} //por defecto

2) Desde S puedo llegar a A, la salvo. Vacc={S,A}

3) Desde A puedo llegar a B, la salvo. Vacc={S,A,B}

4) Desde B no llego a ningun sitio, desaaparecen el resto.

5) Finalmente quedan: S->aAS|AA, A->AbB|a, B=Aba|Ab|λ

GRAMATICA λ-LIBRE ¿Que nodos no terminales pueden quitarse? Los que lleven a lambda, aunque esto no puede aplicarse a la regla S que siempre ha de permanecer.

S -> AB|0S1

A -> 0ABC|λ

B -> B1|λ

C -> λ

Eliminamos todas las lambdas:

S -> AB | 0S1

A -> 0ABC

B -> B1

[apuntesum-blog]

ALF: Expresiones Regulares

INTRODUCCION

Supongamos que queremos conocer el lenguaje que codifica una cantidad de ceros  y de dieces. Podriamos expresarlo como L={0*10*}  || {0,10,010,1010,00...}.

  El conjunto vacío Ø se expresa como L(Ø)=Ø.

  El lenguaje formado por lambda como L(λ)={λ}

  Dado cualquier lenguaje L{ai}={ai} //cualquier simbolo del alfabeto es una expresion regular.

   V={a,b}-> a,b ER -> L(a)={a}, L(b)={b}.

OPERADORES CON EXPRESIONES REGULARES

   Concatenacion

   Union

   Clausura

   Parentesis de agrupación

CONCATENACION

R1 o R2 = R1R2 -> L(R1oR2)= L(R1) o L(R2)

L(abb) = L(ab) o L(b) = {ab} o {b} = {abb} ER L(abb|ab) = L(abb)∪L(ab) = {abb}∪{ab} = {abb, ab}

CLAUSURA

Si a es ER a* es una ER y L(a*)=(L(a)*)={a}* = {a^i|i>=0}

AGRUPACION

Si R es una ER entonces (R) es una ER. (aab)* o aa = (aab)*aa.

PRECEDENCIA DE OPERADORES

Siguiendo la regla de asociatividad por la izquierda (empezamos a agrupar lo que haya en la izquierda y vamos hacia la derecha es de:

() > * > o > |

ab*c | (ca)* -> ((a(b*))c)|(ca)* ->  a(b^i)c∨(ca)^j

ARBOLES SINTÁCTICOS

ab*c|(ca)*

ab*c --- | ---(ca)*

ab* --- c --- (ca) --- *

a --- b* --- () --- ca

b --- * --- c --- a

Para saber el lenguaje una vez hecho el arbol sintáctico vamos del nivel mas bajo de la rama derecha o izquierda y vamos hacia arriba. Ademas hay ciertos trucos para cuando nos topamos con lenguajes elevados a exponentes:

L={a^i |i>0} -> L{aa*}

L={a^i |i>1} -> L{aaa*}

COINCIDENCIAS

La  expresion regular ha de ser general, pero no demasiado general (aceptar cadenas incorrectas) ni muy poco general (hasta el punto de que no acepte aquellas dque debería de validar). Por comodidad usarémos el simbolo - para denotar un intervalo desde x-t para evitar tener que poner 0|1|2|3|4...

REGLAS IMPORTANTES

aa* = a*a

(a*)* = a*

a* = λ|(aa*)

(a|b)* = (a* o b*)*

(a|b) = (a* o b*)*(a)*

EXPRESIONES REGULARES Y  AUTÓMATAS

Supongamos que tenemos dos automatas que saben representar dos ER llamadas M1 y M2.

M1∪M2 -> Un nodo nuevo apunta a cada uno de los estados iniciales automatas M1 y M2.

M1oM2 -> Los estados finales que fueran de M1 se hacen no finales y ahora apuntan a los iniciales del automata M2.

M1* -> Se crea un nuevo estado final que apunta con lambda al inicial de M1 y los finales de M1 ahora apuntan al nuevo estado final con la transición lambda.

TEOREMA DE KLEENE

Un lenguaje puede ser descrito por un ER si y solo si puede ser aceptado por un automata finito. Podemos decir que cada nodo de un arbol sintactico es en su mismo una version mas avanzada de los anteriores.

Supongamos el lenguaje 0|10, se puede descompone en "0, |, 10" (no es necesario descomponer el 10 pues puede representarse facilmente con un automata finito).

Si llamamos M1 a 0 y M2 a 10:

Mfinal = M1 U M2;

Existen ciertas traducciones de las expresiones regulares que permiten armar estos automatas:

Ø -> Un solo estado no final.

λ -> Un estado final al que se va solo con lamda.

a1,a2,...,an -> Un estado inicial que a través de la transicion con 'a' llega a un estado final con una transicion a si mismo con 'a'.

DE AUTOMATA FORMAL A EXPRESION REGULAR

El proceso inverso es el mismo:

Un estado q no final -> Ø

Un estado q final -> λ

Un estado inicial q que va a otro por 'a' y se queda en el final con transiciones con 'a' -> a1, a2...an.

Un solo estado final a con transiciones a si mismo con el simbolo 'a'-> a*

Un solo estado final con transiciones a si mismo con el simbolo (a,b) -> (a|b)*

LENGUAJES CERRADOS

No todos los lenguajes son ER por ejemplo (^k)^k k>=0 no es regular pues las ER no tienen memoria.

DESGLOSANDO UN AUTOMATA

Suponiendo el siguiente automata podemos encontrar su ER a través de un proceso metódico.

El primer paso consiste en listar desde cada estado a cual puedo llegar haciendo solo un movimiento, recordando que, si un estado es final, per se, apunta a lambda:

q0 = aq0 | q1 | aq2

q1 = bq1 | aq2

q2 = bq2 | q1 | λ

Ahora yendo desde la q mas grande vamos retrocediendo paso a paso. Si en algun momento de la expresion encontramos la misma letra en su mismo nivel....

q2 = bq2 | q1 | λ -> q2 = b*(q1|λ)

q1 = bq1|(ab*(q1|λ)) -> q1 = bq1 | ab*q1 | ab* ->  q1 = (b*ab*)q1 | ab* -> q1 = (b|ab*)*ab*

q0 = aq0 | q1 | aq2 -> aq0|(b|ab*)*ab*|((b|ab*)*ab*|λ)

q0 = a*((b|ab*)*ab*|ab*((b|ab*)*ab*)|λ)

EJERCICIOS

1)Desglose la siguiente ER: (a|ba)*((bb)*|aab|λ)

(a|ba)*((bb)*|aab|λ)

(a|ba)* --- ((bb)*|aab|λ)

(a|ba) --- * --- () -- (bb)*|aab|λ

() --- a|ba ---- (bb)*|aab --- | --- λ

a --- ba --- (bb)* --- | --- aab

(bb) --- *

() --- bb

2) ¿Que ER acepta el automata?

q0 = aq0 | bq1 | λ q1 = aq0 | bq2 | λ q2 = aq3 | λ q3 = aq3 | bq2 | λ

q3 = a*(bq2|λ) q2 = aa*(bq2|λ)|λ -> q2 = (aa*ab)*(λ|λ) -> q2 = (a|ab)*|λ q1 = aq0 | b(a|ab)* | λ q0 = aq0 | b(aq0|b(a|ab)*|λ) | λ qo = aq0 | b(aq0|b(a|ab)*)|b|b q0 = (a|ba)*(bb(a|ab)*|b|λ)

3) Siguiendo las siguientes pautas, ¿cual es el ER que acepta el autómata?

q0 = [q1 q1 = ]q3 q2= (a|b)q2|;q4|]q3 q3 = λ q4 = (a|b)q2

i=4; q4 = (a|b)q2 q2 = (a|b)q2|;(a|b)q2|]q3 -> q2 = ((a|b)(λ|;)q2]q3 i=3 q3 = λ q2 = (a|b)(λ|;)q2|] q1 = (a|b)q2|q] i=2 q2 = ((a|b)(λ|;))*(]) q1 = (a|b)((a|b)(λ|;))*]|] i=1 q0 = [((a|b)((a|b)(λ|;)*]|])

[roikansuirius-blog]

AEC: Reduccion en Memoria y Cache

CLASIFICACION DE FALLOS DE CACHÉ

Forzosos: El primer acceso a un bloque de memoria no puede estar en la caché (poco efecto en programas grandes), llamados fallos de arranque en frío o de primera referencia.

Capacidad: La memoria caché no tiene el tamaño suficiente para contener todos los bloques necesarios. En un momento determinado uno de los bloques utilizados ha de dejar hueco a otro, se produce un fallo si se vuelve a referenciar el bloque que se quitó.

Conflicto: La memoria caché no es totalmente asociativa. Aciertos en una caché totalmente asociativa se vuelven fallos en una asociativa por conjuntos.

AUMENTO DEL TAMAÑO DEL BLOQUE

Para reducir la tasa de fallos de la caché, la manera mas sencilla es aumentar el tamaño de bloque. Reduce fallos forzosos pues aumenta la localidad espacial, la penalizacion por fallo aumenta pues cuesta mas mover un bloque as grande y como hay menos bloques en caché, aumentan los fallos por conflicto y capacidad.

El diseñador del sistema de caché debe intentar minimizar la tasa de fallos y la penalización por fallo. La selección del tamaño del bloque depende tanto de la latencia como del ancho de banda del nivel inferior:

Una gran latencia y un ancho de banda necesitan un tamaño de bloque grande, lo cual una latencia y un ancho de banda bajo necesitan un tamaño de bloque pequeño.

AUMENTO DE LA ASOCIATIVIDAD

Aumentar la asociatividad  incrementa el tiempo de servicio en caso de acierto pues el hardware se complica per se reduce la tasa de fallos. Generalmente una asociativa por conjuntos de 8 vias se comporta a efectos prácticos como una totalmente asociativa.

Una caché de correspondencia directa de tamaño N tiene aproximadamente la misma tasa de fallos que una de dos vias de tamaño N/2.

CACHÉ DE VICTIMAS

Se añade un pequeño buffer totalmente asociativo entre un  nivel de caché y el siguiente donde se queden los datos que se reemplazan en un nivel superior, intentando conseguir bajo tiempo de acierto de la correspondencia directa y reducir los fallos debido a conflictos como las asociativas.

Dependiendo de la aplicacion una caché de victimas de cuatro entradas puede llegar a evitar el 25% de los fallos de caché de una caché de 4KB de mapeo directo.

BUSQUEDA ANTICIPADA POR HARDAWARE

Si el hardware busca anticipadamente los datos antes de que los pida el procesador se intenta iniciar el acceso a memoria antes de que se ejecute una instruccion que produciría un fallo de caché. El problema es que cuando hacemos busquedas anticipadas innecesarias desperdiciamos ancho de banda.

Generalmente esta busqueda se hace con hardware externo a la caché, el procesador busca dos bloques en cada fallo, el solicitado (que se lleva a caché) y el contiguo (que se lleva a un buffer de instrucciones). Si el solicitado se encuentra en el de instrucciones, se cancela la peticion a la caché, se lee dicho blloque y se emite una peticion de prebúsqueda para el siguiente bloque.

Prebusqueda con:

Stride: En vez de prebuscar el bloque i+1 se busca el i+stride.

Etiquetada: Se asocia un bit de etiqueta a cada bloque, inicialmente a 0. Cuando una linea se trae por fallo de caché o referenciada se pone a 1. Cuando una linea es traida por prebusqueda el bit se pone a 0. La prebusqueda para la linea i+stride se inicia cuando el bit de la etiqueta de la linea i pasa de 0 a 1.

BUSQUEDA ANTICIPADA POR COMPILADOR

En vez de usar hardware para hacer prebusquedas, podemos dejar que el compilador haga instrucciones que soliciten estas prebúsquedas. Hay dos alternativas:

Register prefetch: Carga el valor en un registro (cargas normales).

Caché prefetch: Carga los datos en la caché (instrucciones especiales).

Cualquiera de las dos podría ser faulting o nonfaulting es decir, la direccion puede causar o no una excepción por un fallo en la direccion virtual y violaciones de protecciones.

Al usar la busqueda por compilador, se incrementa el numero de instrucciones. Para evitar prebusquedas innecesarias los compiladores deben concentrarse en las referencias a memoria que tienen mayor probabilidad de fallar y que provocarian mayores detenciones. La busqueda por compilador solo tiene sentido si el procesador puede continuar mientras realiza la busqueda, el objetivo es solapar la ejecución con la busqueda de los datos.

OPTIMIZACION DEL COMPILADOR

Permite reducir la tasa de fallos sin ningun cambio en el hardware, hay cuatro optimizaciones:

Combinacion de arrays (mergin arrays).

Intercambio de iteraciones (loop exchange)

Union de bucles (loop fusion)

Blocking

MERGIN ARRAYS

Reducir la tasa de fallos al mejorar la localidad espacial. Algunos programas referencian multiples arrays en la misma dimension con los mismos indices al mismo tiempo, si los combinamos en un unico array donde cada casilla contenga los elementos necesarios de cada array original estamos reduciendo la complejidad:

int val[SIZE]; int key[SIZE]; ————– struct mezcla{ int val; int key; }; struct mezcla array_combinado[size];

LOOP EXCHANGE

Intercambiando el orden de los bucles podemos hacer que se accedan a los datos en el orden en el que están almacenados en memoria, reduciendo los fallos de caché mejorando la localidad espacial.

for (j=0; j<100; j=j+1) for(i=0; i<5000; i=i+1) x[i][j]=2*x[i][j]; ———————————- for(i=0; i<5000; i=i+1) for (j=0; j<100; j=j+1) x[i][j]=2*x[i][j];

LOOP FUSION

Fusionar dos bucles en uno solo hace que los datos que se cargan en caché puedan utilizarse para las distintas operaciones antes de desalojarse.

for (i=0; i<N; i=i+1) for (j=0; j<N; j=j+1) a[i][j] = 1/b[i][j] * c[i][j]; for (i=0; i<N; i=i+1) for (j=0; j<N; j=j+1) d[i][j] = a[i][j] * c[i][j]; ———————————————- for (i=0; i<N; i=i+1) for (j=0; j<N; j=j+1){ a[i][j] = 1/b[i][j] * c[i][j]; d[i][j] = a[i][j] * c[i][j];}

BLOCKING

En vez de operar sobre olumnas o filas enteras se opere entre submatrices o bloques, maximizando el acceso a los datos de caché antes de sustituirlo.

for (i=0; i<N; i=i+1) for (j=0; j<N; j=j+1){       r = 0; for (k=0; k<N; k=k+1) r = r + y[i][k] * z[k][j]; x[i][j] = r;} ————————————————– for (jj=0; jj<N; jj=jj+B) for (kk=0; kk<N; kk=kk+B) for (i=0; i<N; i=i+1) for (j=jj; j<min(jj+B,N); j=j+1){             r = 0; for (k=kk; k<min(kk+B,N); k=k+1) r = r + y[i][k] * z[k][j]; x[i][j] = x[i][j] + r;

—————————————————

REDUCCION DE LA PENALIZACION POR FALLO DE CACHÉ

El rendimiento de la cache: Taccesomedio = Tsa + m * Tpf significa que una mejora en la penalizacion por fallo puede ser tan beneficiosa como una reduccion de esta tasa de fallos.

Para esto veremos tres posibles optimizaciones con el fin de reducir la penalizacion por fallo:

Caches multinivel

Buffer de escritura

Cachés no bloqueantes

CACHES MULTINIVEL

O hacemos caches mas rápidas para cumplir con la velocidad de la CPU o caches mas grandes para evitar ir a memoria.

La solucione es añadir un segundo de nivel de cache entre la caché original y la memoria. La de primer nivel puede ser lo sufucientemente pequeña para ser casi tan rapida como el procesador, y la del segundo nivel puede set grande para evitar la penalizacion por fallo.

Esto compica la formula:

Tam = Tsa(L2) + m(L1)*(Tsa(L2)+m(L2)*Tpf(L2));

Tasa de fallos local (local miss rate): El numero de fallos en la caché dividido por el numero total de acceso a la caché, para la del segundo nivel sería m(L2).

Tasa de fallos global (global miss rate): El numero de fallos de caché divido por el numero total de accesos a memoria generados por la CPU. Para la caché de segundo nivel sería m(L1)*m(L2).

BUFFER DE ESCRITURA

Tener un buffer de escritura tambien supone una mejora para una caché con post-escritura acelerando los reemplazos.

SW 512(R0), R3      ; M[512] <-R3 LW R1, 1024(R0)     ; R1 <- M[1024] LW R2, 512(R0)      ; R2 <- M[512]

Se produce un riesgo RAW a traves de memoria. Tras el SW el dato de R3 se situa en el buffer de escritura. El siguiente LW se usa el mismo indice de caché (se produce fallo). El segundo LW intenta poner el valor de la posicion 512 en el registro R2, lo que tambien povocaba fallo de caché.

Si el buffer de escritura no ha completado la escritura en la posicion 512 de memoria, el segundo 2º LW podría leer de memoria el valor viejo.

Para solucionar el problema podemo hacer que la lectura se espere asta que se vacie el buffer de escritura pero esto haria que aumentara el tiempo de penalizacion en caso de fallo de la lectura o bien…cuando se produzca un fallo por lectura se compruebe el buffer de escritura y si no está ahi el dato buscado, se continua con la lectura en la memoria principal.

CACHES NO BLOQUEANTES

Una caché no bloqueante (lockup-free cache) permiten que una cache de datos siga permitiendo accesos mientras se resuelve un fallo de caché de otra instruccion en vez de bloquearse. Puede permitir solo accesos que acierten (acierto bajo) o solapar varios fallos (acierto bajo múltiples fallos) lo que reducidiría la penalizacion media por fallo pero haría que la complejidad se incrementara.

REDUCCION DEL TIEMPO DE SERVICIO EN CASO DE ACIERTO

Los procesadores modernos tienen segmentado el acceso a las caches (instrucciones y datos) a lo largo de varios ciclos para poder soportar una elevada frecuencia de reloj.