Procesos

TEMA 1 PROCESOS Cambio de Contexto: El proceso deja de ejecutarse y era necesario almacenarlo y luego cuando la reanudáramos comenzar en ese punto. Cuando llega una interrupción ( altera la secuencia de ejecución en el procesador) el sistema operativo toma el control y analiza que interrupción ha llegado y llama a la rutina de tratamiento de interrupción adecuada y esta hará alguna cosa. Operaciones sobre procesos. • Crear un proceso: El sistema operativo le asignará un identificador, un bloque de control de proceso libre, y un campo de prioridad. • Destruir un proceso: Tienen un identificador de proceso que es el que se elimina y hay que liberar el bloque de control correspondiente. Si tiene recursos hay que liberarlos antes de liberar el espacio de bloque de control. • Modificar la prioridad del proceso: Solo se puede modificar la prioridad hacia abajo. • Suspender y reanudar un proceso: Un proceso, suspendido sigue estando en el sistema sigue estando en el bloque de control de proceso, a diferencia del que está eliminado. • Retardar un proceso: Un tiempo determinado, útil cuando queremos cumplir plazos de tiempo. • Leer los atributos de un proceso: • Dividir y unir un proceso: ( ForK − Join ) Un proceso es la unidad a la que se le asignan los recursos del sistema, unidad de expedición de trabajos al procesador. Por debajo del proceso hay una parte más pequeña que la denominamos HILO o HEBRA. El hilo o la hebra se conoce como proceso ligero. La unidad de asignación es el proceso pero la unidad de expedición son los hilos o las hebras. Un proceso consta de varios hilos. Al cargar un proceso cargo el contexto de ese proceso, y tengo varios hilos al ejecutarse el proceso se ejecutan los hilos y si se interrumpe un hilo continuamos con otro hilo y así no es necesario hacer un cambio de contexto. HILO 1 HILO 2 HILO 3 Proceso Cuando se interrumpe el hilo 1 seguimos ejecutando el hilo 2. La ventaja de tener uno o más hilos es como tener varios caminos al ejecutar un proceso. Si uno se bloquea, ejecutamos otros hilos que no estén bloqueados, así no tenemos que manejar tanta información en un cambio de contexto. Al proceso se le denomina normalmente TAREA y esta consta de 1 o más hilos de ejecución. Una tarea con un hilo solo se le denomina proceso. 1

La tarea la vamos a asignar un espacio de direcciones que contienen la imagen de la tarea y le asignamos un acceso protegido. A cada uno de los hilos le asignamos un estado de ejecución, contexto, pila de ejecución, variables locales, acceso a la memoria y los recursos de la tarea. La unidad de expedición de la CPU es ahora los hilos o sea que le mandamos los hilos a la CPU. Y la unidad de asignación de recursos es ahora la TAREA. Ej: Tenemos un sistema de adquisición de datos que supervisa de forma continua un proceso físico para registrar su comportamiento y para identificar e informar sobre cambios significativos a un operador. El programa toma datos de entrada los archiva en disco, efectúa alguna operación sobre ellos e informa mediante su impresión. Primera tarea Segunda Tarea Tercera Tarea En caso de haber variación Significativa lo notifica mediante Impresión. Cuarta tarea. Otra forma de hacerlo sería ver si puedo solapar algunas tareas así tardaría menos tiempo. La operación de guardar y la operación de calculo son independientes por lo que se pueden hacer independientemente. Por lo que se pueden ejecutar de forma concurrente. R = leer G = guardar C = calcular I = imprimir Vamos con otro ejemplo: Tenemos a= x + y b=z+1 c=a−b Nos imaginamos que es un programa. ¿ Qué partes se pueden ejecutar a la vez?, a simple vista el tercero no se 2

puede ejecutar con ninguno de los anteriores a la vez ya que necesita de ellos para obtener su resultado, y los dos primeros se pueden realizar a la vez. Para verlo más fiablemente veremos cuando dos procesos pueden ejecutarse a la vez de forma concurrente. Antes de esto definiremos : Conjunto de lectura de una sentencia: ( R ( Si)) Conjunto de todas las variables cuyos valores son referenciados durante la ejecución de la instrucción (Si). R ( Si) a1, a2,.., an Conjunto de escritura de una sentencia: ( W ( Si)) Conjunto de todas las variables cuyos valores cambian en la instrucción (Si) durante su ejecución. W ( Si) b1, b2,.., bn Ej: tenemos a = x + y. R ( a= x + y ) = sería la ( x, y) W(a= x + y ) = sería la ( a) Puede haber términos que aparezcan en el conjunto de lectura y en el de escritura. Ej: W ( a = a+1) = sería la ( a) R( a = a+1) = sería la ( a ) El conjunto de lectura puede ser vacío. Como por ejemplo Read (a ) será vacío porque no está referenciada antes. Pues con esto podemos definir lo que propuso BERNSTEIN. BERNSTEIN propuso que para saber si 2 instrucciones eran concurrentes o no debían cumplirse 3 condiciones y todas ellas que son: • La intersección del conjunto de lectura de la primera instrucción con el conjunto de escritura de la segunda tenía que ser el conjunto vacío. R ( S1) " W ( S2) = " • La intersección del conjunto de escritura de la primera instrucción con el conjunto de lectura de la segunda tenía que ser el conjunto vacío. W ( S1) " R ( S2) = " • La intersección del conjunto de escritura de las 2 instrucciones tenía que ser igual al conjunto vacío. W ( S1) " W ( S2) = "

3

Tienen que cumplirse las 3 instrucciones para que sean concurrentes. Ejemplo: Tenemos S1) a = a + y ; S2) b = z + 1; S3) c = a − b Hacemos los conjuntos de lectura y escritura. 1º ) R ( S1) = ( x , y ) W ( S2) = ( b) 2º ) W ( S1) = ( a ) R ( S1) = ( z ) 3º ) W ( S1) = ( a ) W ( S2) = ( b ) Ahora aplicamos las leyes de Bernstein. 1º ) nos da el conjunto vacío (") 2º ) nos da el conjunto vacío (") 3º ) nos da el conjunto vacío (") Por lo tanto S1 y S2 podían ejecutarse de forma concurrente. Otro ejemplo: Tenemos ahora los conjuntos de escritura y de lectura siguientes que correspondes a S1 y a S3 .Después aplicamos la intersección.( " ). 1º ) R ( S1) = ( x , y ) " W ( S3) = ( c) 2º ) W ( S1) = ( a ) " R ( S3) = ( a,b ) 3º ) W ( S1) = ( a ) " W ( S2) = ( c ) Al hacer la intersección nos queda: 1º ) nos da el conjunto vacío (") 2º ) nos da ( a) 3º ) nos da el conjunto vacío (") Por lo que no pueden ejecutarse de forma concurrente estas 2 tareas. GRAFOS DE PREFERENCIA. Los grafos de preferencia es un grafo acíclico orientado cuyos nodos corresponden a sentencias individuales. Un arco desde una sentencia Si hasta el nodo que representa el nodo Sj significa que Sj solamente puede ejecutarse cuando halla finalizado Si . Tiene que ser acíclico ya que en este caso ocurriría que Sj no se puede ejecutar hasta que no se haya ejecutado 4

SK pero SK no se ejecuta hasta que Sj no se haya ejecutado y este caso es imposible. Instrucciones FORK / JOIN. Fork : nos sirve para generar 2 instrucciones ( ejecuciones) concurrentes en un programa. Join: nos permite recombinar 2 computaciones diferentes en una sola. Tenemos el siguiente grafo: Dibujo 1. S2 depende de S1 y S3 depende de S1 pero S2 no depende de S3 . Necesito una sentencia para generar 2 instrucciones concurrentes. Si quiero dividir tengo que utilizar la sentencia FORK y si quiero unir tengo que utilizar la sentencia JOIN. El FORK lleva una etiqueta asociada por ejemplo L y cuando el sistema encuentra el FORK ejecuta por un lado la instrucción que se encuentra asociada a la etiqueta L, y por otro lado ejecuta de forma concurrente ( a la vez ) la instrucción siguiente a la instrucción. Ejemplo de sentencia FORK. En el ( dibujo 1) sería: S1 ( Quiero generar 2 caminos, por lo que pongo el fork) Fork L1 ( La L1 es la etiqueta) S2 ( es la sentencia siguiente a la de S1 ) L1 : S3 Supongamos que tenemos el grafo siguiente: Un hilo Otro hilo Donde s1, s2 etc son sentencias de un proceso. Y las dos ramas pueden ser hilos. Dibujo 2 El programa quedaría:

S1 Fork L1 S2

5

S4 L1 : S3 S5 Ejecuto el programa y tengo S1 me encuentro con un Fork y cojo el de la etiqueta por lo que ejecuto el S3 y S5 y a continuación se toma la sentencia siguiente al fork S2 y S4. El JOIN lleva asociado siempre un contador que se inicializa a un valor que es igual al número de computaciones concurrentes que queremos unir. Necesitamos que las 2 bifurcaciones lleguen a la vez para poder ejecutarse y así utilizamos el contador y de esta manera desecha el proceso que llegue antes. La variable contador la decrementamos en una unidad y eso lo hace el Join y a continuación comprobamos el valor del contador. Si el cont " 0 el proceso que ejecuta es Join termina. Cont = cont − 1 todo esto forma parte del Join. If cont " 0 then quit. Suponemos que llegamos antes por la izquierda que por la derecha inicializamos el contador a 2 porque queremos unir 2 caminos o ramas diferentes, y así cuando llegue cont=0 se destruye o se quita el proceso y así la última rama que llegue finalizará el programa En el caso del (dibujo 2) ejecutará el proceso S6. Tenemos el dibujo 2 de antes que no estaba acabado, yo tengo que colocar un Join en el programa ya que tengo que unir S4 y S5, imaginamos que le ponemos después de la instrucción S4 por lo que el S4 será quien ejecute la sentencia S6 ya que tengo que saltar del S4 al J1 y después se ejecutará el S6 y para esto tengo que poner un go to. El contador se inicializa al principio. Ejercicio de ejemplo. L1 L2 J1 El contador de este grafo será tres porque tengo que unir tres flechas. Cont = 3 S1 Fork L1 S2 S4 Fork L2 S5 Go to J1 cont = 2 6

L1 : S3 Go to J1 cont = 1 L2 : S6 con = 0 J1 : join cont S7 Ejemplo 2: Cont 1 = 2 Cont 2 = 2 S1 Fork L1 S2 S4 Fork J1 S5 Go to J2 L1 : S3 J1 : join cont 1 S6 J2 : join cont 2 S7 Tenemos el siguiente grafo: Cont 1 = 2 Cont 2 = 2 Cont 3 = 2 Fork L1 S1

7

For J1 S3 Go to J2 L1 : S2 Fork L2 J1 : join cont 1 S4 Fork J3 J2 : join cont 2 S6 Go to fin L2 : S5 J3 : join cont 3 S7 Fin Tenemos ahora el siguiente grafo: S1 Fork L1 Fork L2 S2 Go to L1 : S3 Go to L2 : S4 Donde le estamos diciendo con el Fork L1 que a la vez que hace S3 haga el Fork L2 y a su vez este fork L2 dice que haga S4 y también la siguiente instrucción que es S2. EJERCICIO PROPUESTO. 8

Cont 1 = 2 OTRA FORMA Cont 2 = 2 Cont 1 = 2 Cont 3 = 2 Cont 2 = 2 Cont 4 = 2 Cont 3 = 2 Fork L1 Cont 4 = 2 S1 Fork L1 Fork L2 S1 S3 Fork L2 Go to J1 S3 L1 : S2 Go to J1 S5 L2 : S4 Fork L3 S6 Fork L4 J1 : join cont 1 SA S9 Go to J2 Go to J2 L2 : S4 L1 : S2 S6 S5 Go to J1 Fork L3 L3 : S8 Fork L4 Go to J3 SA L4 : S7 Go to J3 J3 : join cont 3 L3 : S8 SB Go to J4 Go to J4 L4 : S7 J1 : join cont 1 J4 : join cont 2 S9

9

SB J4 : join cont 4 J3 : join cont 3 SD SC J2 : join cont 4 SD EJERCICIOS. L1 L2 L3 C1 C2 C3 J1 J2 J3 L4 C4 J4 C5 J5 C6 Tenemos seis contadores: Cont1 = cont2 = cont 3 = cont6 = 2 Cont 4 = con5 = 3 A Fork L1 B Fork L2 D Fork J1 H Go to J4 L2 : G Fork J2 J1 : Join Cont1 I

10

Go to J4 L1 : C Fork L3 F Fork J3 J2 : Join Cont2 J Fork J5 J4 : Join Cont4 M Go to J6 L3 : G Fork L4 J3 : Join Cont 3 K Go to J5 L4 : L J5 : Join cont5 N J6 : Join Cont6 O OTRO EJERCICIO HACERLO Instrucción concurrente de DijKstra ( Parbegin / Parend) Tiene la siguiente forma: Parbegin

11

S1 S2

Sn Parend. Todas las instrucciones entre Parbegin y Parend se ejecutan de forma concurrente ( a la vez ). El grafo quedaría: .. Si tenemos por ejemplo las instrucciones: a= x + y b=z+1 c = a − b nos quedaría. Parbegin A = x + y Se ejecutan de forma concurrente. B=z+1 Parend C=a−b No todo lo que se puede hacer con Fork / join se puede hacer con parbegin, parend. E Parbegin F G Parend H El programa sería: Begin A Parbegin 12

B C Begin D E Parbegin F G Parend H End Parend I End Ejercicio: Hacerle primero así y después con la línea de trazos. Sin flecha: Con flecha quedaría: Begin Begin Parbegin Parbegin Begin Begin S1 S1 Parbegin Parbegin S3 S3 Begin Begin S4 S4 S6 S6

13

End Parbegin Parend SA S9 S9 End . Begin End S2 . S5 . Parbegin Parend SA Ahora tendría que venir el S9 pero Begin también tendría que estar arriba como Parbegin se ve, por lo tanto no puede estar en dos S7 en los 2 lados por lo que no se puede hacer. S8 Si mezclamos varias ramas ya no se puede Parend hacer con Parbegin y Parend. SB End Parend SC End Parend SD End Vamos a emular el parbegin y el Parend con Join y Fork Esto con Fork y Join sería: Cont = n S0 Fork L1 Fork L2 . .. .. Fork Ln − 1 Sn L1 : S1 go to Jn L2 : S2 Go to Jn

14

Jn : join cont Sn + 1 Siempre tendremos un Fork menos del número de sentencias que ejecutemos. a) Nos imaginamos que tenemos que hacer: − b + " b2 − 4ac 2a Donde −4ac son dos operaciones. Tenemos que ver el mayor grado de concurrencia posible. Lo hacemos con Fork / Join y Parbegin, Parend. L1 L2 L3 J2 J3 J1 Donde S1 = −1 * b S6 = "( b * b ) − 4 a c S2 = b * b S7 = − b + "( b * b ) − 4 a c S3 = 4 * a S8 = (− b + "( b * b ) − 4 a c) ) / 2 S4 = 4 * a * c S9 = 2 * a S5 = ( b * b ) − 4 a c Cont1= cont2 = cont3 = 2 Fork L1 Fork L2 Fork L3 S9 Go to J1 L1: S3 S4 Go to J2 15

L2 : S2 J2 : Join cont1 S5 S6 Go to J3 L3 : S1 J3 : join cont2 S7 J1 : join cont3 S8 b) Tenemos un programa que lee en un fichero y lo copia en otro. ¿Qué concurrencia podría conseguir ahí ?. Si pongo Read ( f . s ) . . Write ( g . s ) De esta forma no podría hacer las cosas a la vez porque hasta que no haya escrito el contenido no puedo volver a leer. Pero si pongo una variable adicional lo que leo lo almaceno en esa variable y luego lo paso al fichero si puedo leer y escribir a la vez. Read ( f . s ) T=s Write ( g . t ) La solución sería: Begin Read ( f . x ) While not eof ( f ) Begin Y=x

16

Parbegin Write ( g . y ) Read ( f . x ) Parend End Write ( g . x ) End. c) Lo hacemos con Parbegin y Parend. Begin Parbegin Begin Parbegin S1 Begin Parbegin S2 Begin S3 S4 End Parend S5 S6 End Parend S7

17

End S8 Parend S9 End Exclusión mutua Imaginamos que tenemos un Spool de impresión, un lugar donde tenemos los trabajos de impresión. Y en algún lugar tengo una variable ( Entrada ) para ver que sitio tengo libre y otra variable ( salida ) para ver donde voy imprimiendo. 4567 Al meter el trabajo en el Spool entonces la variable entrada que tiene la siguiente estructura: ENTRADA = ENTRADA + 1 . Leo ENTRADA lo incremento en uno y vuelvo a la variable ENTRADA y escribo el valor. Pero que ocurre si hay un proceso que llega y le asigna el 5 mediante la variable, y cuando llega el trabajo 5 que era el número que le había asignado se interrumpe ( por cualquier motivo ) y en ese momento llega otro trabajo y se coloca en 5 entonces el anterior se borrará. Este problema se denomina condiciones de carrera, dos o más procesos leen o escriben en un área compartida y el resultado final depende de los instantes de ejecución de cada uno. El problema se soluciona impidiendo que más de un proceso lea o escriba simultáneamente datos compartidos. Relentizando la exclusión mutua. La exclusión mutua es que un solo proceso excluye a todos los demás de utilizar un recurso compartido, con el fin de garantizar la integridad del sistema . A estos recursos se les denomina recursos críticos y la pare del programa en la que acede a estos recursos se la denomina sección crítica. La solución a la exclusión mutua debe tener unas pautas: • Debe garantizar la exclusión mutua ( no debe haber 2 procesos que se encuentren de forma simultánea dentro de sus secciones críticas). • No tenemos que hacer suposiciones con respecto a la velocidad de los procesos en conflicto ni con respecto a su número. • Debemos garantizar que ningún proceso fuera de su sección crítica, pueda bloquear a otro proceso. • Debemos garantizar que cuando un proceso quiera obtener la entrada en su sección crítica se la conceda en un tiempo finito. • Debemos garantizar que no se produzca inalición, que no haya ningún proceso que no entre en la sección crítica. Podemos distinguir tres partes:

18

Sección residual de entrada ( El resto de programa que está antes de la sección crítica que nos plantea problemas). • Negociación del protocolo. ( se establecen los mecanismos que nos permiten garantizar que los demás no entren en la sección crítica) • Sección crítica. • Protocolo de liberación. ( los mecanismos anteriores se eliminan para continuar con el programa. Sección residual de salida ( El resto de programa que está después) Soluciones al problema : Alternancia de procesos : La ejecución de un proceso condiciona la ejecución del otro. No es una solución válida ya que la sección residual del proceso p1 y la del p2 no tienen por qué ejecutarse al mismo tiempo o ser iguales por lo que en este aspecto falla. Indicadores de ocupación: Nos indican si uno u otro proceso están en su sección crítica. Para que P1 y P2 estén a la vez en su sección crítica las variables P1enuso y P2enuso tienen que ser Falso. No es una solución válida ya que ambos procesos pueden estar a la vez en su sección crítica. Tercera solución : Si alternamos la ejecución de los procesos en el planificador puede que ocurra que ambos se queden esperando. Solución de cortesía: No es válida porque puede ocurrir que alternando los procesos, ocurra lo mismo de antes, que están dando vueltas sin acceder a la sección crítica. Solución de Peterson: ¿ Garantiza la exclusión mutua? Que ambos procesos no estén en su sección crítica a la vez. En esta solución no existe la posibilidad de que ambos procesos estén a la vez en su sección crítica. El que P2 esté en su sección residual no impide a P1 entrar en su sección crítica. ESTA SOLUCIÓN ES VALIDA. Solución de Dekker: También es una solución válida. Método de la panadería : También es valido. Todos estos métodos que hemos visto que eran válidos tienen un problema es que retardan la ejecución de los procesos, debido al WHILE que llevan por lo que consumimos recursos y no es bueno para el sistema. Vamos a ver ahora soluciones para la exclusión mutua que son soluciones hardware, no dependen de programas hechos por nosotros. Hay dos soluciones: • Pesimistas: Suponen siempre el peor caso posible y actúan bloqueando todo lo que pueda interferir un proceso a continuación actualizan la variable y después desbloquean lo que habrían bloqueado. • Optimistas: Consideran que no hay conflictos o que hay my pocos, por lo que permiten el acceso a los datos compartidos. En el caso de que haya conflicto mantienen la integridad del sistema descartando las actualizaciones que han sido invalidadas por los procesos concurrentes contendientes. Lo primero leen el valor de la variable global y preparan la actualización local tentativa. En el caso de no haber cambiado, entonces se aplica la actualización local tentativa a la variable global y si ha cambiado se descarta la actualización tentativa y se vuelve al paso primero. Este caso no obliga a la serialización de procesos, no existe noción de sección crítica y no se precisa la exclusión mutua, salvo en la comparación. MÉTODOS. 19

• Habilitar_inhabilitar interrupciones. Es pesimista, y no es válido para sistemas multiprocesadores, con más de un procesador, ya que sólo afecta a un solo procesador. Un programa Otro programa −−−−−−−−−−−−− −−−−−−−−−−−−−−−−−−−− −−−−−−−−−−−−− −−−−−−−−−−−−−−−−−−−− −−−−−−−−−−−−−− inhabilito −−−−−−−−−−−−−−−−−−−−− variable variable −−−−−−−−−−−−−− habilito −−−−−−−−−−−−−−−−−−−−− −−−−−−−−−−−−−− −−−−−−−−−−−−−−−−−−−−−− Lo que hace es que hasta que no se actualice la variable bloqueo todas las interrupciones y después habilito lo que haya inhabilitado. • Comprobar y fijar ( Test and Set). Vamos a tener una función que es la de ( Test and Set) que devuelve un valor de tipo booleano. Funcion TS ( Var i: entero) : Bouleano Begin If i = 0 then Begin I=1 TS = cierto End Else TS = falso End Desde dentro de un programa tenemos un programa de exclusión mutua. Proceso P ( i : entero) Begin

20

Repeat Repeat ( nada) until TS ( lock) SC Lock = 0 Resto del Programa .. . Forever End Este programa llama a la función de antes TS. La expresión Repeat ( nada) until TS ( lock) quiere decir que no hacemos nada hasta que TS nos devuelva algo verdadero. SC ( sección crítica). Inicialmente la variable Lock la ponemos a o (lock = 0), que esta variable iría declarada en algún sitio. Todos los procesos tienen una variable lock que vale 0. Los demás procesos no entrarán hasta que el primero acabe la sección crítica y coloque la variable lock a cero. ( lock =0). Esta solución sí vale para sistemas multiprocesadores siempre que las operaciones de lectura, modificación, escritura se realicen de forma indivisible ( dentro de un ciclo de ejecución). Es una solución pesimista. Método de Comparar e intercambiar. Es útil para variables simples de variables compartidas. Se copia el valor de la variable global al espacio local, se utiliza ese valor para realizar una actualización tentativa y esa actualización será correcta si ningún otro proceso ha modificado la variable global, mientras se modifica la variable local. Si es así hay que repetir la secuencia. Lo que sería la función quedaría de la siguiente forma : CS ( VIEJOREG, NUEVOREG, VARGLOBAL) VIEJOREG = VARGLOBAL NUEVOREG = VIEJOREG Actualizamos nuevo reg SI ( VIEJOREG 0 VARGLOBAL )

21

VARGLOBAL = NUEVOREG SINO VIEJOREG = VARGLOBAL Donde el ( CS ) significa : comparar e intercambiar ( compare and swap). Es un método optimista, es válido para sistemas multiprocesadores. SEMÁFOROS. Son variables enteras ( s ) que pueden ser accedidas solamente en 2 momentos: A ) en el momento de su inicialización . B) Por medio de 2 operaciones que actúan sobre la variable, son operaciones atómicas ( de forma indivisible) hacemos referencia a ellas como P y V se llaman wait y signal. ( verificar e incrementar). WAIT ( S ) la operación decrementa el valor del argumento semáforo en tanto que el resultado no sea negativo. Sería algo como : Wait ( s ) While s < = 0 do Esperar S=s−1; SIGNAL ( S ) la operación aumenta el valor. Signal ( s ) S=s+1; Con esto se resuelve la exclusión mutua. Hay dos tipos de SEMÁFOROS. • Semáforos binarios : solo pueden tomar valor 0 o 1 • Semáforos generales : cualquier otro valor. Los semáforos generales son útiles cuando tengamos varias instancias de un mismo recurso. Los semáforos se utilizan para sincronizar procesos. Ejemplo: Tengo dos procesos P1 y P2 y quiero que hasta que S1 no se ejecute no se ejecute S2. Por lo tanto tengo que poner: s1 Wait ( m ) Signal ( m ) s2 22

Yo inicializo a cero el valor del semáforo ( m ). Imaginamos que el proceso 2 va más rápido que el proceso 1, llegará a wait y esperará hasta que no se ejecute S1 y después el signal ( m ) que equivale a decir m = m+1 dará paso a que el otro proceso pueda pasar y pondrá m = m−1 y así aseguramos que S1 se ha ejecutado. Programa Principal Mutex = 1 Parbegin P1 P2 P3 Parend Var Mutex : semáforo ( binario) Proceso P1 Proceso P2 Begin Begin While true do While true do Begin Begin Wait ( mutex) Wait ( mutex ) Sección Crítica Sección Crítica Signal ( mutex ) Signal ( mutex ) SR P1 SR P2 End End End End Proceso P3 Begin While true do Begin

23

Wait ( mutex ) Sección Crítica Signal ( mutex ) SR P3 End End; Garantiza la exclusión mutua. Cuando un proceso está en su SECCIÓN CRÍTICA los otros procesos no pueden entrar en su sección crítica ya que tienen el wait ( mutex) y como el mutex = 0 no pueden entrar y cuando acaba el P1 tienen un signal ( mutex ) que aumenta el valor de mutex que ahora valdrá 1 y así puede entrar otro proceso. Cuando un proceso ejecuta la operación WAIT y encuentra que el valor del semáforo no es positivo, el proceso se bloquea a sí mismo y el proceso es colocado en una cola de espera asociada al semáforo donde no consume ciclos del procesador. Posteriormente el proceso debe ser despertado en algún momento por alguien y este será el SIGNAL que hará que se reanude alguno de los procesos suspendidos. Es parecido al esperar pero aquí no consumimos recursos. La implementación será : Wait ( S ) Si ( S < = 0 ) then Suspender y enviar a la cola Sino S = S − 1. En el caso del Signal ( s ). Signal ( S ) Si cola no está vacía Then reanudamos un proceso de cola Sino S = S + 1 No es posible interrumpir estos procesos son indivisibles. Ahora podemos utilizar semáforos para hacer grafos que no eran posibles hacerlos con Parbegin y Parend pero con semáforos , Parbegin y Parend si lo podemos hacer. Begin Parbegin Begin P1 24

Parbegin S2 Begin S3 Signal ( S3−7) End Parend S4 End Begin S6 Wait ( S3−7) S7 End Parend S5 End Ejemplo: Las flechas conflictivas. Begin Parbegin Begin S1, Parbegin, Signal ( a ), signal ( b ), Parend, End Begin Wait ( a ) , S2, signal ( c ) End Begin Wait ( b ), S3, signal ( d ) End Begin Wait ( c ) , S4 , Parbegin , signal ( e ),Parend, signal ( f ) End Begin Wait ( e ), S5, signal ( g ) End

25

Begin , Parbegin Wait ( f ), wait ( d ) ,Parend, S6, signal ( h ) End Begin , Parbegin Wait ( g ), wait ( h ), Parend, S7 End Parend End. Estamos utilizando 8 semáforos ( está bien ) pero no del todo ya que se puede utilizar solo uno. Begin Begin S1 S1 Parbegin Parbegin Begin Begin S3 Parbegin Signal ( S3−6) S3 End Wait ( S4−6) Begin Parend S2 End S4 Begin Parbegin S2 S5 S4 Begin Parbegin Wait ( S3−6 ) S5 S6 Signal ( S4−6) End Parend Parend End S7 Parend End S7 Parend End End

26

UNIX El SHELL en UNIX hace una personalización del entorno. Los shell en UNIX también son lenguajes de programación, son lenguajes interpretados. Los más importantes en Unix son: C_Shell , Bourne, Koin Shell, nosotros veremos el BOURNE. Con shell podemos escribir pequeños programas que se llaman Scripts, consiste en editar un fichero que contiene los comandos que se van a ejecutar. El Scripts se puede ejecutar de dos formas: • Como un fichero ejecutable: para lo cual necesitamos dar al fichero un permiso de ejecución. Por ejemplo al fichero program1. • Invocar un nuevo Shell: pasándole como argumento el archivo que queremos ejecutar. Por ejemplo sh program1. El Shell del programa es otro programa, puede tener tantos entornos como quiera con shell. Cuando entro en Unix ya estoy en el shell de Unix al tener el prom $ si pongo ahora −ch ya tengo otro entorno de Shell y si pongo otro −ch tendría otro entorno de shell y para salir pongo exit y saldría del ultimo entorno de shell creado. También puedo invocar al shell como ./program1. Por lo tanto tenemos que coger el vi y editaremos el primer script, le ponemos un nombre significativo. Ejemplo de script. CLEAR PWD (limpiar la pantalla ) Si dentro del script deseamos poner comentarios tendremos que utilizar # (almohadillas). Los argumentos que se le pasan por ejemplo al program1 como puede ser: Program1 A B se hacen referencia dentro del script poniendo el símbolo de dólar y el argumento que es. Ejemplo: $1, $2,.,$9 ( con el dólar accedemos al contenido de una variable) De esta forma podemos tener en el script. CLEAR (limpiamos la pantalla) PWD ECHO $1 me saca la A ECHO $2 me saca la B Otras variables pueden ser $# que contiene el número de argumentos que se le han pasado al Script. Si pusiésemos ECHO $# en el Script me sacaría un 2 en el ejemplo anterior. 27

La variable $* contiene todos los argumentos, no su número sino su valor. Si pusiésemos ECHO $* en el Script nos aparecería A y B. En el caso de que desease utilizar más de 9 argumentos está el comando SHIFT que produce un desplazamiento de los argumentos, y este desplazamiento se realiza hacia la izquierda. Ejemplo: Tenemos en el Script: ECHO $1 me saca una A ECHO $2 me saca una B SHIFT Si pusiese ahora ECHO $1 me saca una B ECHO $2 no me aparece nada La A se pierde debido al desplazamiento a la izquierda. Para leer entradas de teclado se hace a través del comando READ. Pongo el comando y una variable donde quedará almacenado lo que escribo y si quiero visualizarlo pongo ECHO $ (valor de la variable). Ejemplo: READ (valor) ECHO $(valor) Ej: ECHO Introduzca fichero a borrar READ nombre RM $nombre Sentencias de control. IF condición IF condición THEN THEN Comando / os Comando / os FI (indica el final) ELSE

28

Comando / os FI Para poner 2 comandos en una misma línea tengo que poner el símbolo de punto y coma ( ; ). Para evaluar las condiciones hay un comando que es TEST y puede evaluar condiciones de 3 tipos: • Valores numéricos. Para evaluar la condición puedo hacerlo de 2 formas: • TEST condición • TEST [ condición ] Y entre corchetes antes de condición y después hay que dejar un espacio en blanco. −Eq comprueba si 2 variables que contienen valores numéricos son iguales. Ejemplo: PROGRAM1 ECHO Introduce un número A READ A ECHO Introduce un número B READ B IF TEST $A −eq $B IF TEST [ $A − eq $B ] Es lo mismo una expresión que otra. − gt Sirve para ver si un número es mayor que otro. − lt Sirve para ver si un número es menor que otro. − ne Sirve para ver si los números son iguales. − ge Sirve para ver si son mayores o iguales los números. − le Sirve para ver si los números son iguales o menores. • Tipos de ficheros. Para el caso de ficheros tenemos: − f Si existe y es un fichero ordinario − d Si existe y es un directorio. 29

− r Si existe y tiene permiso de lectura. −w Si existe y tiene permiso de escritura. −x Si existe y tiene permiso de ejecución. −a Si existe el archivo. Ejemplo: PROGRAM1 Echo Introduce un fichero Read A Echo Introduce un directorio Read B If Test − f $A ( compruebo que existe) Then If test − d $B (compruebo que es un directorio) Then Cp $A $B (copio A en B) El AND se especifica con el comando −a El ejemplo anterior lo podía haber puesto como: If test − f $A −a −d $B Then Cp $A $B El OR se especifica con el comando −o El NOT se especifica con el comando ! Para la comparación de cadenas de caracteres, tenemos el comando − z , comprueba si la cadena es o no nula. Si es nula devuelve verdadero. El comando − n comprueba que no es nula. El comando = comprueba que una cadena es igual a la otra. El comando != comprueba que las cadenas son distintas. 30

Podía crear un Script como: PROGRAM1 If test $# − eq 0 Then Read fichero Rm $fichero Else Rm $ 1 Fi Lo que hace es que borra un fichero pero comprueba que se le ha pasado el parámetro. Ejemplo: PROGRAM1 If test $# − eq 0 Then Read fichero Else Fichero = $1 se lo asigna la fichero Fi Tenemos el Script Tenemos la función sh program1 1 2 3 4 PROGRAM1 Echo $* me sacaría el 1, 2,, 3, 4 Echo $# me sacaría el número 4 de los 4 valores que tengo. Echo $0 me sacaría el Program1 Shift Echo $* ahora me sacaría el 2,3,4

31

Echo $# me saca 3 ya que tengo solo ahora 3 variables Echo $0 me sacaría el Program1 Los Bucles FOR tienen la siguiente forma: FOR variable IN lista DO Sentencias DONE La variable va tomando cada uno de los valores que hay en la lista y por cada uno se ejecutan las sentencias comprendidas entre el DO y el DONE. Ej: FOR v IN lunes, martes, miercoles DO Echo $v Sacaría lunes, martes, miercoles DONE La v el primer valor que toma es lunes y ejecuta el conjunto de sentencias y luego tomaría martes y ejecutaría el conjunto de sentencias y así sucesivamente. Otra forma de usar el For y las variables que le pasas sería utilizando por ejemplo un fichero y en el poner las variables y cuando haces el bucle for llamas a ese fichero para que tome las variables del fichero. Ej: tengo un fichero con : Si pongo: FOR v IN ` CAT fichero ` Esto quiere decir que v toma el valor de lo que contenga Contenga el fichero. La instrucción cat te muestra el contenido del fichero. El cat fichero produce una salida y para que cat fichero se sustituya por la salida debemos ponerlo en comillas invertidas. BUCLES WHILE Su estructura es la siguiente: WHILE condición tenemos un símil que es UNTIL condición DO DO Sentencias sentencias

32

DONE DONE El while es que mientras se cumple la condición estamos en el bucle y el Until es que hasta que no se cumpla la condición estaremos en el bucle. Tenemos las sentencias BREAK que provocan un salto a la siguiente instrucción fuera del bucle. Tenemos las sentencia CONTINUE que saltan a la siguiente instrucción del bucle, o sea dentro de él a la siguiente donde aparezca. Ej: WHILE true DO Me estaría pidiendo valores hasta Read valor que no pulsara nada, hasta que IF $valor = pulsara intro. Pero si pongo Break CONTINUE sería un bucle infinito FI DONE SENTENCIA CASE Su sintaxis es la siguiente: CASE variable IN Valor 1 ) sentencia . .. . Sentencia n ; ; Valor 2) Sentencia * ) sirve para cualquier otro caso que no hemos especificado anteriormente. ESAC Los dos puntos y comas nos especifican el final de la última sentencia. Si ponemos Valor1 Valor 2 es lo mismo a decir que valor2 o valor 3 El es lo mismo que un OR. 33

La instrucción ESAC sirve para finalizar el CASE. ¿Cómo se definen funciones? Se emplea la palabra FUNCTION < nombre función> Y entre llaves va el cuerpo de la función. Otra forma de declarar funciones sería: Nombre_función ( ) A la función se la invoca con el nombre. Se recomienda poner a las funciones al principio del Script. A las funciones se les puede pasar parámetros que son internos a la función. Ejemplo de función. Una función que suma: Suma ( ) a = ` expr $a + 1 ` Return a Echo introduzca un valor Read a b = ` suma ` Cuando quiero evaluar una expresión matemática tengo que poner la expresión EXPR. Las funciones devuelven el valor mediante RETURN pero solo valores numéricos entre 0 y 255, si devuelvo una cadena me dará error. EJERCICIOS. • Realizar un Script que presente un menú por pantalla con 3 opciones. Mostrar, Borrar, renombrar un fichero ( pidiendo el nuevo nombre). Si se pasa el fichero como argumento no lo solicitará si se pasa como argumento lo solicitará. If [ $# − eq 0 ]; then Echo Introduce el nombre del fichero Read fichero 34

Else Fichero = $1 Fi Echo 1. Mostrar fichero Echo 2. Borrar fichero Echo 3. Renombrar fichero Read var Case $var in 1) cat $fichero ;; 2) rm $fichero ;; 3) echo fichero destino read destino mv $fichero $ destino;; *) echo debes introducir (1 / 2 / 3 ) • Realizar un Script al que se le pasen como parámetros 2 cadenas la primera el nombre del fichero y la segunda el nombre del directorio. Tras comprobar que el fichero existe y tiene permiso de escritura lo copiará en el directorio comprobando previamente que no exista el fichero en el directorio y que tenga permiso de escritura en el directorio. Si no se le pasa alguno de los parámetros los solicitará. If test $# −eq 2 Then fich = $1 dir = $2 else echo Introduce un fichero read fich echo Introduce un directorio read dir fi 35

if test −f $fich −a ! −f $dir / $fich then if test −c $ dir −a −eq $dir then cp $fich $dir else echo El directorio no existe o no tiene permiso. Echo de escritura Fi Else Echo El fichero no existe o no es un fichero de escritura. Fi EJERCICIOS. • Tenemos un directorio /FUENTE y otro /DESTINO, se pide copiar al directorio destino aquellos ficheros ordinarios del directorio fuente que no existan en l directorio destino. SCRIPT 1 For a in ` ls / FUENTE ` Do If [ −f $a ] Then If [ ! −f /DESTINO/ $a ] Then Cp /FUENTE / $a /DESTINO Fi Fi Done • Sabiendo que en el fichero \ etc\passwd la primera columna contiene el nombre de cada usuario dado de 36

alta en el sistema realizar un script que muestre aquellos usuarios que están dados de alta en el sistema pero que no están en sesión de ejecutar el script. Who > fichero For V in `cut −d : −f1 / etc/passwd/ ` Do Grep ^$V fichero If [ $? ! −eq 0 ] $? Sirve para hacer comprobaciones. Then Echo $V no está conectado fi done • Crear un Shell script que permita saber si un número está comprendido entre otros 2. Los 3 números ( limite inferior, limite superior, número que se comprueba) deben ser pasados en ese orden. Si alguno no se pasa se solicitará. If test $# −lt 2 comprobamos si nos han pasado 2 parámetros Then If test $# −eq 1 si nos han pasado menos leemos el primero Then Read sup Inf = $1 Else Read inf Read sup Fi Else Superior = $1 Inferior = $2 Fi 37

While [ $inf −le $sup ] mientras el valor inferior sea menor o menor_igual que el Do valor superior. Lo sacamos por pantalla. Y aumentamos Echo $ inf el valor inferior. Inf = ` expr $ inf + 1 ` Done • Crear un Script que reciba como parámetro 2 números y muestre los números comprendidos entre ambos. HACERLO. EJERCICIOS: • En una oficina tenemos 4 impresoras ( láser, matricial, tinta, color) a las que referenciamos con estos nombre. Realizar un script que nos permita imprimir un fichero en una de las 4 impresoras diferentes de la manera siguiente. El fichero a imprimir se pasa como parámetro y si no es así se mostrará un error y se finalizará la ejecución del script. En caso de suministrarlo se comprobará que es un fichero ordinario y se mostrará un menú que permita elegir la impresora donde se imprimirá, luego se imprime y se termina. If [ $# −eq 1 ] Then If test −f $1 Then Echo 1. Impresora de Láser Echo 2. Impresora de tinta Echo 3. Impresora matricial Echo 4. Impresora de color Read num Case $num in 1) lpr −p Láser $1 2) lpr −p Tinta $1 3) lpr −p matricial $1 4) lpr −p color $1 esac

38

else echo No es un archivo ordinario fi else echo Faltan o sobran parámetros fi • Crear un Script al que se le pase un número cualquiera de parámetros ( es desconocido, y puede ser mayor de 9 ) y los muestre uno a uno por pantalla. While [ $# ! −eq 0 ] Probar a ver si funciona: For V in $* Do do Echo $1 echo $V Shift t done Done El operado << . Si pongo cat << cadena el sistema muestra por pantalla desde ese punto hasta que se encuentre con la cadena. Lo de antes se puede poner: Cat << EOF 1. Impresora de Láser 2. Impresora de tinta 3. Impresora matricial 4. Impresora de color EOF PROBLEMAS DE LOS PRODUCTORES / CONSUMIDORES Tenemos un conjunto de procesos operativos y algunos de ellos producen datos que otros consumen. Existiendo posible disparidad entre las velocidades de producción y consumo. Se trata de idear un protocolo que permita a productores y consumidores operar de forma conjunta ( concurrente ) de manera que los datos producidos se consuman en el orden exacto en el que son producidos. El primero caso es que suponemos que el buffer es ilimitado ( fotocopia 2).

39

Se trata de que cuando produzca tengo que incrementar algo para saber que se ha producido, y cuando consuma tengo que decrementar algo para saber que se ha consumido. El segundo de los casos suponemos que el buffer es limitado. Se trata de que para que el productor pueda producir tiene que haber sitio en el buffer y para que el consumidor consuma tiene que haber algo en el buffer. Ahora tenemos que saber que espacios hay libres en el buffer. Tendremos 2 semáforos uno para llevar cuenta de los espacios libres y otro para los elementos consumidos. PROBLEMA DE LOS FILOSOFOS COMIENDO Tenemos unos filósofos que piensan y luego comen. Cuando un filosofo quiere comer necesita 2 tenedores y el que los tiene no los soltaba. La solución a este problema debe asegurar que no se produce interbloqueo, y que no hay ninguna conspiración que impida comer a algún filósofo. Vamos a ver una solución que no es valida: FILOSOFO (i ) Int i ; While true do Begin Meditar ; Coger_tenedor (i ) Suponemos que son 5 filósofos. Coger_tenedor ((i+1) mod 5 ) Comer Elegir_tenedor ( i ) Dejar_tenderor ( (i+1) mod 5 ) End; La función comprobar es una función que comprueba el estado del filósofo a la izquierda y el de la derecha. PROBLEMA DE LOS LECTORES/ESCRITORES. Es un universo de lectores que leen una estructura de datos. Un universo de escritores que modifican esa estructura de datos comunes. Se trata de idear un protocolo de sincronización entre lectores y escritores que asegure la consistencia de los datos comunes y mantenga un grado de concurrencia tan elevado como sea posible. La solución es que tantos 40

lectores como sean posible accedan a recursos compartidos, lecturas simultáneas y los de escritura solo puedan llevar a cabo su función cuando acabe el último lector. Este método favorece a los lectores y perjudica a los escritores. Un proceso industrial de fabricación de vigas de madera, consiste en pelar troncos de madera, darles forma de paralelepípedo y estamparlos con un número de serie para luego ser retirados, para ello se utilizan 3 máquinas y 2 depósitos intermedios de capacidad limitada, siendo la capacidad del de troncos pelados 100 unidades y el de vigas sin estampar 200 unidades. AB Escribe un programa con 3 procesos concurrentes utilizando semáforos que imiten el comportamiento de las máquinas. Siempre hay troncos y cuando depositamos las vigas en el deposito esto no tiene límite. Es necesario controlar que no accedan los dos a la vez. Este problema es parecido al de los PRODUCTORES_CONSUMIDORES. Necesitamos 2 semáforos para que no choquen las máquinas cuando acceden a los depósitos. Necesitamos controlar el número de espacio libre y el de vigas del depósito. Ponemos 2 semáforos binarios MUTEX A y MUTEX B. Para esto ponemos inicialmente: Troncos ocupados = 0 Primer depósito. Troncos libres = 100 Semáforos Generales. Vigas ocupadas = 0 Segundo depósito Vigas libres = 200 Proceso Peladora Proceso Cortadora Proceso Estampadora Begin begin seguimos abajo While true do while true do Begin begin Coger_tronco; wait (troncos_ocupados); Pelamos_tronco; wait( mutex A); Wait(troncos_libres); Coger_tronco_pelado; 41

Evita chocar Wait ( mutex A); signal ( mutex A); las máquinas Dejar_tronco; signal (troncos_libres); Signal (mutex a); hacer_paralelepipedo; Signal ( troncos_ocupados); wait ( vigas_libres); End; wait ( mutex B); End; Dejar_viga; Signal (mutex B); signal ( vigas_ocupadas); end; end; Proceso Estampadora Begin While true do CUERPO DEL PROGRAMA Begin for i = 1 to 100 Wait ( Vigas_ocupadas); signal ( troncos_libres) Wait ( mutex B); for i = 1 to 200 Coger_Viga; signal ( vigas_libres) Signal ( mutex B); signal ( mutex A) Signal ( Vigas_libres); signal ( mutex B) Estampar la Viga Dejar_viga_estampada; PARBEGIN End; Peladora End; Cortadora Estampadora PAREND EJERCICIO 3 DE LAS HOJAS. Tenemos 3 fumadores y un agente.

42

Tenemos las posibilidades : a) Tabaco y papel 1. Si el agente genera un uno equivale a b) Papel y fuego 2. Poner en la mesa fuego • Fuego y papel 3 Si genera un do equivale a poner tabaco, y así sucesivamente. Sem [ ] es un array de semáforos para controlar los fumadores. Proceso fumador ( i ) Begin While true do Begin Wait ( sem [ i ] ); espero a que coloque algún ingrediente. Fumar ( ) ; Signal mesa; el agente tiene libre la mesa para colocar un objeto. End; es un semáforo binario. End; Proceso Agente Begin While true do Begin x= random ( ) signal ( sem [ x] ); wait ( mesa ); end; end; EJERCICIO 6 DE LAS HOJAS. TEORIA PRACTICA

43

Begin Begin While true do while true do Begin begin Wait ( sobres) wait Mesa_llena Coger_sobre_vacío wait Mesa Signal ( sobres) Coger_sobre For i = 1 to 20 do Signal ( mesa ) Coger_examen Signal ( mesa_vacía) Guardar_examen For i = 1 to 20 do Done coger_examen Wait ( mesa_vacía) corregir_examen Wait ( mesa) dejar_examen Dejar_sobre done Signal ( mesa) wait ( sobres ) Signal ( mesa_llena) dejar_sobre End signal ( sobres ) End end end Cuerpo del programa: Signal ( sobres ) Signal ( mesa ) For i = 1 to 20 do Signal ( mesa_vacía) Done Parbegin Teoría

44

Practica Parend EJERCICIO 5 DE LAS HOJAS. N Vamos a tener el proceso COCHE_NORTE ( i ) S • PRIMERA PARTE. Proceso coche_norte ( i ) Proceso coche_sur ( i ) Begin begin While true do while true do Begin begin Llegar hasta el puente wait ( puente ) Wait ( puente ) Pasar_hacia_sur Pasar hacia el norte Signal ( puente ) Signal ( puente) end End end End • SEGUNDA PARTE. Proceso coche_norte ( i ) Proceso coche_sur ( i ) Begin begin While true do while true do Begin begin Wait ( norte ) wait ( sur ) Wait ( puente ) Pasar_hacia_sur Pasar_hacia_norte signal ( puente) Signal ( puente ) signal ( sur )

45

Signal ( norte ) end End end end EJERCICIO 4 DE LAS HOJAS. Proceso CLIENTE Begin While true do Begin Wait ( Sala_espera) Wait ( mutex ) Cli = cli + 1 Signal ( mutex ) Wait ( barbero ) If not despierto then despierto = true X = ( a lo que hace el barbero ) Wait ( mutex ) Cli = cli − 1 If cli = 0 then despierto = falso Signal ( mutex ) Signal ( barbero ) Signal ( sala _ espera ) End End La inicialización sería FOR i = 1 to n + 1 Signal ( sala_espera ) EJERCICIO 1 DE LAS HOJAS.

46

No es valido porque puede haber 2 procesos que accedan a su sección crítica a la vez. Comunicación y sincronización de procesos. Si ponemos : Signal ( mutex ) SECCIÓN CRÍTICA Wait ( mutex ) En este caso acceden todos los procesos a la sección crítica a la vez. Si ponemos : Wait ( mutex ) SECCION CRITICA Wait ( mutex ) En este caso entra un proceso y bloquea todo el mecanismo. Región crítica: Es lo mismo que un semáforo, pero es el compilador el que se encarga de controlar los accesos a la sección crítica, en vez del programador. Ejemplo: Tenemos el siguiente procedimiento. Procedure Begin While true do begin REGION x DO Begin Sección Crítica End End end El compilador se encarga de traducirlo a : 47

Procedure Begin While true do begin REGION x DO ( a partir de aquí empieza a traducir) Wait ( X . S ) semáforo Sección crítica Signal ( X. S ) End End Este resultado resuelve el problema de la exclusión mutua pero no nos vale para problemas de sincronización. ( antes de hacer la y , hacer la x ) Región Crítica Condicional: Su funcionamiento es igual que la Región Crítica, pero esta permite una condición que debe cumplirse para ejecutarse la sección crítica. REGION x WHEN < B > DO Begin Sección crítica End Donde B es la condición. Si no se cumple la condición el proceso se queda esperando, asociado a una cola de esa región. Cuando un proceso sale de la sección Crítica comprueba la condición de los procesos que están esperando y si se cumple alguna condición alguno de los procesos es activado. Solamente dejaremos entrar nuevos procesos en la región crítica cuando no se cumpla ninguna condición o cuando no quede ningún proceso en la cola. Implementación: Wait ( X . S ) If not < B > Signal ( X . S )

48

Wait ( X mutex ) Tengo un proceso y quiero que la instrucción x se ejecute antes que y . ¿Cómo se puede hacer? x Region x mutex b = verdadero Region z when b do y Monitores. Son mecanismos que nos garantizan la exclusión mutua. La estructura garantiza que solo se esté ejecutando un procedimiento a la vez. Un monitor tiene una estructura formada por una cabecera que lo identifica, un conjunto de variables globales, un conjunto de procedimientos y un bloque de inicialización que se ejecutará una sola vez cuando se crea el monitor. Cabecera MONITOR Variables Procedimientos o rutinas

.. < inicialización > En el recurso compartido ( requiere un acceso exclusivo para los procesos ) se declara como monitor y dentro de los procedimientos del monitor se incluyen todas las operaciones que se puedan llevar a cabo con dicho recurso. Los procesos que utiliza el monitor se sitúan de forma independiente de tal manera que se encapsulan los datos y procedimientos y quedan al margen de dichos procesos. Cuando alguno de los procesos necesita acceder al recurso compartido, llamará al monitor correspondiente y dentro del monitor al procedimiento específico que implementa la operación deseada. Es necesario garantizar que todos los accesos al recurso compartido se realizan a través de procedimientos implementados en el monitor. Para conseguir sincronizar procesos vamos a utilizar 2 operaciones. CWAIT ( variable_condición ): El proceso que realiza la operación siempre es suspendido en una cola asociada a la variable_condición, hasta que otro proceso haga Csignal. CSIGNAL( variable_condición): Si la cola asociada a la variable_condición no está vacía entonces despierta al proceso que se encuentra en la cabeza de la cola y si está vacía no hace nada. La variable_condición no tiene valor son simplemente colas donde albergamos procesos suspendidos. 49

ISEMPTY(variable_condición) NON_EMPTY(variable_condición) determinan si la cola está o no vacía. El monitor permite que mientras un proceso está esperando en un CWAIT entre otro procedimiento para ejecutarse. Cuando un proceso se despierta dentro del monitor tiene preferencia sobre uno que entre. La operación CSIGNAL debería ser la última del proceso que la ejecuta. Ejemplo: P1 CWAIT .. Si no fuera la última instrucción en este caso no se cumpliría la exclusión mutua, ya que al hacer Csignal P2 habilitaría a P1 que estaba esperando en el Cwait y CSIGNAL estaría el P1 y el P2 a la vez en el monitor. A=a+1 El proceso 2 quedaría de la siguiente forma: P2 A=a+1 CSIGNAL Como se implementa un Monitor Wait_signal : monitor Begin Ocupado : boolean ; Disponible:condition; Declaración de Variables Procedure Mon_wait begin if ocupado then disponible . wait Aquí nunca se puede poner directamente ocupado = true ; CWAIT 50

end; Procedure Mon_signal Begin Ocupado= false ; Disponible . signal ; End Begin Ocupado = false End. Disponible . wait se puede poner como CWAIT ( disponible) Disponible . signal se puede poner como CSIGNAL( disponible) • PRODUCTORES/CONSUMIDORES con MONITORES • LECTORES/ESCRITORES con MONITORES • FILÓSOFOS con MONITORES. EJERCICIO Por un canal circulan barca y por la carretera vehículos y en ambos casos solo circulan en un sentido. Escribir un tipo monitor que planifique el uso de los puentes con los vehículos y las barcas como procesos. Las barcas tienen prioridad de paso frene a los vehículos. Barcas Coches Consideramos que los puentes se bajan indiferentemente. Vamos a utilizar 2 variables condición : Barcas y coches Variables booleanas : Llevar cuenta de los barcos Llevar cuenta de los coches Puente Monitor Begin Num_coches integer

51

Pasa barca boolean Hay_barcas, hay_coches : condition Procedure Entra_coche ( ) Begin If pasa_barca or Non_empty ( hay_barcas) Hay_coches . Wait Num_coches = num . coches + 1 Hay_coches . signal End; Procedure Sale_coche ( ) Begin If Pasa_barca or Non Empty ( Hay_barcas) Hay_coches . wait Num_coches = num_coches − 1 If num_coche = 0 Hay barcas . signal End Procedure Entra_barca ( ) Begin If Pasa_barca or Non Empty ( hay_coches) Hay_barca . wait Pasa_barca = true end Procedure Sale_barca ( ) Begin Pasa_barca = False

52

If Nom_empty ( hay_barca) Hay_barca . signal Else Hay_coche . signal End_if End MENSAJES. Son un mecanismo que sirve para sincronización y intercomunicación entre procesos, es válida para entornos centralizados y en entornos distribuidos. Un mensaje es una colección de información que se intercambia entre un proceso emisor y un proceso receptor. Un mensaje puede contener datos, ordenes de ejecución o incluso código. Para enviar o recibir mensajes tenemos: • Send ( enviamos un mensaje) Send ( destinatario, mensaje) • Receive ( recibimos un mensaje) Receive ( origen, mensaje) Aspectos Direccionamiento. • Direccionamiento Directo: Cada proceso que desea enviar un mensaje tiene que especificar explícitamente el receptor del mensaje y a su vez el receptor del mensaje tienen que especificar la fuente o el remitente desde el cual desea recibir el mensaje. • Direccionamiento Implícito: Unicamente el emisor especifica quien va ha ser el receptor del mensaje. Ej: un servidor de impresión. • Direccionamiento Indirecto: Los mensajes se envían a una estructura denominada buzón o Mail_box, no especificamos quien es el receptor del mensaje, luego habrá un proceso que recoja los mensajes del buzón. Se pueden hacer relaciones: • Relación 1 : 1 un proceso envía un mensaje a otro mensaje mediante el buzón. • Relación N : 1 Muchos procesos envían mensajes a un buzón ( Ejemplo: Sistema Cliente / servidor) • Relación 1 : N Envío un mensaje y este es recibido por varios procesos. • Relación N : N Esta relación no es muy común. Propiedad de los Buzones. • Los buzones sean propiedad del proceso que los crea: El buzón tienen existencia mientras tenga existencia el proceso 53

• Los buzones sean propiedad del Sistema Operativo: Se proporciona algún tipo de primitiva para crear o destruir el buzón. Formato de los mensajes. • Tamaño fijo: Son más fáciles de implementar, ya que tendrán que ser en un buffer y como sabemos el tamaño del mensaje podemos saber el tamaño del buffer. Si el tamaño del mensaje es mayor que el tamaño establecido , se divide el mensaje y lo envío como varios mensajes, esto implica el secuenciamiento de mensajes. • Tamaño Variable: Son más difíciles de implementar, ya que no conocemos el tamaño de los buffer. Peor no tenemos que dividir el mensaje por lo que es más rápido. Sincronización Cuando enviamos un mensaje tenemos 2 posibilidades: • Bloqueante : El emisor se bloquea hasta que el receptor recibe el mensaje. • No bloqueante: Que el emisor no se bloquee. Cuando recibimos un mensaje puede ocurrir: • Que haya algún mensaje: procesamos el mensaje y continuamos. • Que no haya ningún mensaje B1) Esperar a que llegue algún mensaje B2) No bloquearnos y continuar. Pero si el mensaje tarda un poco más en ser recibido puede ocurrir que el mensaje se pierda para que no ocurra esto se hace el B3. B3) Esperar el mensaje durante un determinado tiempo. Las combinaciones más comunes son: Envío bloqueante Rendezvous o Cita Recepción bloqueante Envío no bloqueante Servidor Recepción bloqueante Envío no bloqueante En los demonios de Unix

54

Recepción no bloqueante Capacidad del canal o de los buzones. Capacidad Cero ( 0 ): No puede haber mensajes esperando , el emisor tienen que esperar a que el receptor reciba el mensaje. Capacidad Limitada: Tengo una cola de longitud finita en la que se almacenan los mensajes y si el número de mensajes es menor que la capacidad de la cola puedo enviar un mensaje y si está llena no puedo enviar el mensaje. Capacidad Ilimitada: Puedo enviar cuantos quiera. Son buenos los tres y los utilizo dependiendo de la situación en la que estemos. Ejemplo: Proc 1 Proc 2 . .. . .. . A. Send ( P2, m) receive ( P1, m) .b .. En la fotocopia ( Pag 1) el receive del exclusión mutua tienen que ser bloqueante. La fotocopia ( Pag 3 ) Este método favorece a los escritores. Proceso Controlador: Da servicio a los lectores y a los escritores. Vamos a utilizar un controlador y lo vamos a inicializar a un número mayor que el número máximo de lectores posibles. Si contador > 0 : quiere decir que no hay escritores esperando y puede haber o no lectores activos, en este caso servimos todos los mensajes TERMINADO antes de eliminar los lectores activos, a continuación servimos las solicitudes de escritura y luego las de lectura. Si contador = 0 : Quiere decir que la única solicitud pendiente es de escritura, y lo que nos hace es permitir al escritor continuar y esperamos un mensaje TERMINADO. Si contador < 0 : Indica que un escritor ha realizado una solicitud y se le ha hecho esperar para despejar a todos los lectores activos. En este caso solo deben servirse mensajes TERMINADO. EJERCICIO.

55

Maquina A Máquina C Máquina B La Máquina C solamente coge pieza del depósito que hay pieza. En los depósitos ( A y B ) solamente puede haber una pieza. Utilizando semáforos y pasos de mensajes implementar una solución. Proceso Máquina A Proceso Máquina B Begin begin While true do While true do Begin begin Coger_pieza Coger_pieza Wait( señal ( A ) ) wait ( señal B) Dejar_pieza en A Dejar_pieza en B Send ( buzón, A ) Send ( buzón, B) End End End End Proceso Máquina C Begin While true do Begin Receive ( buzón, msj ) If msj : A then Coger pieza A Signal ( señal A) Dejar pieza A Else Begin Coger pieza B 56

Signal ( señal B) Dejar_pieza B End End End INTERBLOQUEO O ABRAZO MORTAL. Es una situación en la que un grupo de procesos están permanentemente bloqueados como consecuencia de que cada proceso ha adquirido un subconjunto de los recursos necesarios para su operación y está esperando la liberación de los restantes recursos mantenidos por otros procesos del mismo grupo haciendo imposible que ninguno de los procesos puede continuar. Tenemos 2 procesos A y B que utilizan los recursos de imprimir y el de disco. Proceso A Proceso B Imprimir_dato Leer_disco Leer_disco Imprimir_dato Imprimir_dato Leer_disco El proceso A solicita al Sistema Operativo imprimir_dato este se lo concede y el proceso B solicita Leer_disco que también se lo concede, pero cuando quieren seguir ejecutándose se encuentran que el siguiente recurso que van ha utilizar está ocupado por el otro proceso por lo no pueden avanzar y ninguno suelta el suyo hasta que no tenga el otro, por lo que se produce un interbloqueo. El interbloqueo se produce en : • Recursos reutilizables : Se caracterizan porque pueden ser utilizados por seguridad solamente por un proceso de forma simultánea. Ej : caso de la impresora. • Recursos consumibles : Son recursos producidos y consumidos por procesos activos, de tal manera que su número puede variar a lo largo del tiempo . Ejemplo: un mensaje. Condiciones para que ocurra interbloqueo. Son cuatro condiciones: • Exclusión mutua : Los recursos compartidos son adquiridos y utilizados de forma exclusiva. • Retener y esperar : Cada proceso retiene los recursos que ya le han sido asignados mientras espera la asignación de los restantes. • No expropiación : Un recurso solamente puede ser liberado de forma voluntaria pro el proceso al cual se le ha concedido su uso. • Espera Circular : Los procesos interbloquedos forman una cadena circular de tal manera que cada proceso retiene uno o más recursos que son solicitados pro el siguiente proceso de la cadena. Ejemplo: P1P2 P3 . Pn donde significa esperar. 57

Para que se produzca interbloqueo tienen que cumplirse las 4 a la vez. Ejemplo: Hay dos soluciones para resolver la exclusión mutua : • Garantizar que nunca se produzca interbloqueo. • Prevención de interbloqueos : Asegurar que en cada momento una de las 4 condiciones no se cumple. • Evitación de interbloqueos : Examinar las consecuencias de asignar un recurso solicitado por parte de un proceso y evitar aquellas situaciones que se consideran inseguras y podrían conducir a un interbloqueo. • Detección y recuperación: Conceder los recursos con libertad y periódicamente examinamos el estado del sistema y en caso de que haya interbloqueo se toman las medidas oportunas para solucionarlo. Grafo de Asignación de Recursos Es el grafo en el que representamos los procesos ,recursos , la asignación de recursos a procesos y la solicitud. Una flecha de un proceso a un recurso significa que el proceso solicita ese recurso. Una flecha de un recurso a un proceso significa que ese recurso está asignado a ese proceso. Asignación Solicitud En el caso de tener varia instancias a un recurso entonces se dibuja círculos dentro del recurso tantos como instancias tenga. Asignación Solicitud En este caso no hay Interbloqueo. Se sabe si hay o no interbloqueo si dentro del grafo hay un ciclo, esto significa que puede o no haber interbloqueo. La existencia de un ciclo en el grafo es condición necesaria para la existencia de interbloqueo pero puede no existir. En el caso de que solo tengamos una unidad de cada recurso entonces es condición necesaria y suficiente para la existencia de interbloqueo. Nudo: Es un ciclo en el cual de ninguno de los nodos que lo forman sale un camino que no sea ciclo. Tenemos: Los círculos son instancias. . 58

En este dibujo tenemos interbloqueo no existe ningún camino que no me lleve al mismo sitio. Empezamos en P1 Primer camino: P1 R1 P2 R2 P3 R3 P2 Segundo camino: P1 R1 P2 R2 P3 R3 P1 Otro ejemplo: . No se produce interbloqueo porque habrá un momento en el que acabe P2 porque tiene todo para ejecutarse, y el recurso que ocupa se lo asignará a P1. P4 como también tienen todo para acabar , cuando termine liberará el recurso y se lo asignaremos a P3. Prevención Se encarga de negar alguna de las cuatro condiciones para que no haya interbloqueo. • Un proceso antes de empezar a ejecutarse solicite todos los recursos que vaya a necesitar, si estos están disponibles se le asignan todos y si alguno no está disponible no se le asigna ninguno. A veces esto no es posible porque muchos procesos a priori no conocen los recursos que van a utilizar y otro motivo es que no conduce a una utilización óptima de los recursos ya que algún recurso solicita algún recurso y este igual no lo usa hasta el final y le tiene retenido y no lo puede usar nadie. • Se solicitan los recursos de forma incremental, pero antes de solicitar un recurso se le obliga a dejar temporalmente los que ya tiene, si el nuevo recurso está disponible se le devuelven los que ya tenían, si no está disponible no se le devuelven y evitamos la retención. Si existe la línea de puntos entonces habrá interbloqueo pero si no existe y A solicita el recurso R1 obligamos a que deje R2 así B tiene asignada los dos recursos que le hacen falta y acabará en algún momento y el recurso R1 podrá ser asignado al proceso A. Como R1 antes no estaba disponible la solicitud se mantiene hasta que R1 si esté libre y se pueda asignar. Esperará hasta que esté libre el recurso R1 La línea azul es que hace petición del Esta recurso 2 y como A ya línea desaparece no lo usa entonces se porque obligamos a A a lo concede que es la dejarla ya que no se le ha línea negra. asignado el recurso R1. Los problemas son que hay recursos que no son fácilmente liberados o adquiridos en un instante posterior.

59

SEGUNDA CONDICIÓN PARA NO INTERBLOQUEO. No expropiación: Lo prevehemos si el Sistema Operativo forzara al proceso a liberar el recurso Quito esta línea y así obligamos a liberar R2 obligatoriamente. El problema es que esto es posible con determinado tipo de recursos y con otros no. NOTA: Rollback: Retroceder todos los cambios hechos en un proceso. TERCERA CONDICIÓN PARA NO INTERBLOQUEO. Espera Circular. Los tipos de recursos se ordenan de forma lineal de tal manera que cada proceso solo puede solicitar recursos en orden creciente y todos los recursos de un mismo tipo se deben solicitar de forma simultánea. Ejemplo: tenemos : R1 Los recursos están ordenados de ! Asigna forma creciente y lineal, primero P2 tenemos recursos de R1 a P2 que si ! Solicita necesita varios de R1 los pide R2 todos a la vez, luego tengo P2 y ! Asigna hago petición de recursos de R2 P3 pero ahora y ano puedo pedir ! Solicita recursos de R1, los que he cogido R3 los mantengo pero no puedo ! Asigna solicitar más. Por lo tanto una vez P4 que tengamos recursos de R3 como ya no puedo tomar de R1 la flecha que va de P4 a R1 desaparece y también 60

interbloqueo. PROBLEMAS: Los recursos deben ser adquiridos en el orden previsto y no en el orden en el que realmente se necesitan. El rendimiento cae por lo mismo de antes, ya que los procesos toman recursos que igual no los utilizan hasta el final y les tienen retenidos. CUARTA SOLUCIÓN AL INTERBLOQUEO. Exclusión Mutua. Esta característica no se puede prevenir. EVITACIÓN DE INTERBLOQUEO. Solamente se van a conceder aquellas peticiones de recursos que no puedan dar lugar a un estado inseguro. Cada proceso va ha especificar de antemano las necesidades máximas. Se mira a ver si el estado es seguro. Un estado se considera seguro si todos los procesos que ya tienen concedidos los recursos, tienen la posibilidad de ser completados en algún orden determinado, incluso si cada uno de los procesos utiliza todos los recursos a los que está autorizado. Vamos a utilizar un Algoritmo que es el del BANQUERO para saber si es seguro o no el sistema. Este algoritmo comprueba si la solicitud de un recurso produce un estado seguro. Tenemos un vector que lo llamamos disponibles que representa el número de unidades disponibles de cada recurso. P1

P2

P3

Tengo una Matriz de asignado en la que cada fila es un proceso y cada columna un recurso, y esta matriz representa cada uno de los recursos asignados a cada proceso. R1 R2 R3 P1 P2 P3 Tengo una Matriz necesidades, la misma estructura que la de matriz asignado, y nos da las unidades del recurso que necesita para su ejecución. Los totales van ha ser: TOTALES = necesidades + asignados. Un estado seguro implica que no hay interbloqueo. Un estado inseguro no implica que haya interbloqueo, puede haberlo o no puede haberlo. La función del algoritmo. 61

Primer Paso: Buscamos una fila en la matriz de necesidades cuyos valores sean menores o iguales al vector D ( disponibles), si no existe el estado es no seguro y si existe pasamos al punto 2. Segundo Paso: El proceso de la fila seleccionada solicita todos los recursos que necesita para su finalización y termina, en ese caso se marca el proceso y todos los recursos que tenían asignados se añaden al vector D. Tercer Paso: Se repiten las etapas 1 y 2 hasta que todos los procesos estén marcados ( el estado seguro) o hasta que lleguemos a una situación en la que no podamos continuar en cuyo caso el estado no es seguro. EJEMPLO. Tenemos 4 procesos, e inicialmente tenemos 10 unidades de recurso R1. R1 R1 P1 P1 P2 P2 P3 P3 P4 P4 Mat. Asignación Mat. Necesidades. Lo primero es hacer el vector disponibles, para ello sumamos la matriz asignación: ( 1 + 1 + 2 + 4) = 8 hay asignadas 8 al recurso R1, y tenemos un 10 unidades del recurso R1 por lo que el vector disponibles tendrá 10 − 8 = 2 unidades. D = 2. Se trata de buscar una entrad en la Mat. Necesidades que sea menor o igual que el vector D, y tenemos el P3, si solicitara todos los recursos de golpe se le podría atender, cuando acabe liberará los recursos asignados por lo tanto se lo sumamos a disponibles. D = 2 + asignados a P3 que son 2.(tabla asignación). D = 2 + 2 = 4. Hacemos el mismo proceso buscamos alguno. En este caso tenemos P2. Lo marcamos y le sumamos 1 al disponibles. D= 5, ahora sería o P1 o P4 , nos da igual uno que otro, cogemos P1 y D valdrá D=6, después cogemos el P4 y D valdrá 10, si nos fijamos tiene el mismo valor que el que nos daban al principio ( 10). Por lo tanto la secuencia nos queda: P3P2P1P4. ¿Qué ocurriría si P2 solicita una unidad de R1. Habría que sumar un 1 a la matriz asignados en P2 y restar en la de necesidades a P2 un 1. Nos quedaría: R1 R1 P1 P1 P2 P2 P3 P3 P4 P4 Mat. Asignación Mat. Necesidades Y volveríamos a hacer todo el proceso. ¿Sería seguro el sistema ahora? Lo comprobamos: Sumamos la Mat. 62

Asignación tenemos 9 le restamos los totales de la de disponibles que nos daban y que era 10. D = 10 − 9 = 1, miramos si hay algún proceso que necesite menos de 1 y no hay ninguno, por lo que no si algún proceso solicitase todos los recursos a la vez sería imposible satisfacerle, por lo que es un sistema no seguro, aunque no implica interbloqueo. Por lo tanto debemos retroceder y posponer la solicitud. Ejercicio: Asignados Necesidades R1 R2 R3 R4 R1 R2 R3 R4 P1 P1 P2 P2 P3 P3 P4 P4 P5 P5 5322 Nos dan los totales: 6 3 4 2 Totales 6 3 4 2 Asignad 5 3 2 2 Disponi 1 0 2 0 (P4) + 1 1 0 1 Disponi 2 1 2 1 (P1)+ 3 0 1 1 Disponi 5 1 3 2 (P3)+ 1 1 1 0 Disponi 6 2 4 2 (P2)+ 0 1 0 0 Disponi 6 3 4 2 (P5)+ 0 0 0 0 Disponi 6 3 4 2 Por lo tanto podemos decir que es un sistema seguro. Los totales = Disponibles. 63

¿Qué ocurre si P2 solicita una unidad de R3? ¿Qué ocurre si P5 solicita una unidad de R3? Primero comprobamos que ocurre si P2 solicita una unidad de R3. Asignados Necesidades R1 R2 R3 R4 R1 R2 R3 R4 P1 P1 P2 P2 P3 P3 P4 P4 P5 P5 5332 Cuando P2 solicita una unidad de R3 le sumamos uno en la casilla de asignado a P2, en R3 y se la restamos en el mismo lado en la matriz de necesidades.(negrita). Totales : 6 3 4 2 Disponi: 1 0 1 0 (P4) : 1 1 0 1 Disponi: 2 1 1 1 (P1) : 3 0 1 1 Disponi: 5 1 2 2 (P2) : 0 1 1 0 Disponi: 5 2 3 2 (P3) : 1 1 1 0 Este estado va ha ser seguro. Disponi: 6 3 4 2 (P5) : 0 0 0 0 Disponi: 6 3 4 2 Vamos a ver cuando cuando P5 solicita una unidad de R3. Y dejamos los cambios de antes también. Nos quedará.

64

Asignados Necesidades R1 R2 R3 R4 R1 R2 R3 R4 P1 P1 P2 P2 P3 P3 P4 P4 P5 P5 5342 Totales : 6 3 4 2 Disponi: 1 0 0 0 Como en la matriz necesidades no hay ningún proceso que pueda satisfacerse ya que ninguno tiene todas las necesidades por debajo de los disponibles, entonces si algún proceso los solicitase todos a la vez no se podría cumplir su petición, por lo que es un Sistema no seguro. Ejercicio Asignados Necesidades R1 R2 R3 R1 R2 R3 P1 P1 P2 P2 P3 P3 P4 P4 764 Totales: 8 8 7 Dispon: 1 2 3 (P2) : 1 2 1 Dispon: 2 4 4 (P4) : 0 1 2 Podemos decir que es un Sistema Seguro. Dispon: 2 5 6

65

(P3) : 2 0 1 Dispon: 4 5 7 (P1) : 4 3 0 Dispon: 8 8 7 Que ocurre si P3 solicita una unidad de R1. Asignados Necesidades R1 R2 R3 R1 R2 R3 P1 P1 P2 P2 P3 P3 P4 P4 864 Totales: 8 8 7 Dispon: 0 2 3 Ocurre que es un sistema no seguro ya que si algún proceso solicita todas las unidades de los recursos a la vez no se le puede atender. DETECCIÓN. Consiste en ver si se ha producido interbloqueo. Se conceden libremente los recursos disponibles a los procesos que lo soliciten y periódicamente se comprueba si hay un interbloqueo. Para detectarlo hay que conocer los recursos que hay asignados a los procesos. Necesitamos saber las solicitudes y también de algún algoritmo que con esta información detectar o no el interbloqueo. Algoritmos: ciclos a) Algoritmo de detección de nudos grafos. b) Algoritmo : no tiene nombre y funciona de igual forma que el del banquero. Solicitudes: Número de recursos de un tipo que ya ha solicitado al sistema, aunque puede que necesite más. Si no podemos continuar quiere decir ahora que si hay interbloqueo y los procesos que se encuentran en esa situación son los no marcados.

66

R1 Aquí hay Interbloqueo. R2 Vamos a comprobar que hay interbloqueo. Asignados Necesidades R1 R2 R1 R2 P1 P1 P2 P2 12 Totales 1 2 Dispon: 0 0 Hay interbloqueo y los que están interbloqueados son P1 y P2. R1 R2 R3 R4 En este ejercicio habrá interbloqueo en el P2, y P4 vamos a comprobarlo. Asignados Solicitudes R1 R2 R3 R4 R1 R2 R3 R4 P1 P1 P2 P2 P3 P3 P4 P4 2011 Totales: 2 2 1 1 Dispon: 0 2 0 0 ( P3) : 1 0 0 0 hay interbloqueo en el P2 y P4. Dispon: 1 2 0 0

67

(P1) : 1 0 0 0 Dispon: 2 2 0 0 Otro ejercicio. R3 R4 R1 R2 R5 Asignados Necesidades R1 R2 R3 R4 R5 R1 R2 R3 R4 R5 P1 P1 P2 P2 P3 P3 P4 P4 P5 P5 11111 Totales: 1 1 1 1 1 Dispon: 0 0 0 0 0 Hay interbloqueo en P1, P2, P3, P4. (P5) 0 0 1 0 0 Dispon: 0 0 1 0 0 Frecuencia de invocación de esos algoritmos. Si es alta tienen unas ventajas por ejemplo antes detectaremos la existencia de interbloqueo y la desventaja puede ser que ese algoritmo consume tiempo. Si es baja la frecuencia tardaremos mucho en detectar el estado de interbloqueo, la ventaja es que ese tiempo no lo consumimos. El sistema no hace nada y todos están en interbloqueo si la frecuencia de invocación es muy baja. Para ver las frecuencias de detección haremos: • Cada vez que un proceso necesite un recurso invoque al recurso. • Invoque cada vez que solicita un recurso y este no le es asignado. • Invocarlo a intervalos regulares de tiempo. • Invocarlo cuando el rendimiento del sistema cae.

68

Recuperación del interbloqueo. • Ir abandonando procesos, de esta manera se liberan los recursos que este tenía y así se mira si el sistema sigue con interbloqueo y si sigue bloqueado se sigue abandonando procesos. • Abandonar todos de golpe. • Vuelta atrás consiste en ir a un estado anterior en el cual no hubiera interbloqueo, obliga a guardar en un registro todos los estados seguros y poder regresar a uno de estos estados. • El sistema se apropie de recursos, se van quitando recursos a procesos para volver a una situación segura. Estrategia para tratar interbloqueos. Algoritmos del Avestruz : Ignoran los interbloqueos, no hacen nada ante un interbloqueo. CUENTAS DE USUARIO. Se gestionan a través de unos ficheros específicos, son editables y visibles por cualquiera. Existen varios mecanismos para dar de alta a un usuario: • Con el comando USERADD o con el comando ADDUSER. Nos pedirá el Login que es el nombre del usuario en el sistema . Va a tener un UID, es único e internamente maneja ese número o identificador. Además debemos utilizar una contraseña un password, y un GID identificador de grupo. El sistema nos pide el directorio HOME del usuario, nos solicitará el shell para dicho usuario. Y nos solicitará el nombre completo del usuario. • Se puede dar de alta también a través de algún tipo de herramienta gráfica como pueden ser las X_WINDOWS. Nota: Para montar un sistema de fichero se hace con MOUNT. • También se puede hacer a mano: Existe un fichero /etc/passwd que contiene las cuentas de usuario, y existe una línea en el fichero por cada usuario que esté dado de alta en el sistema , tiene un formato definido y vienen separados los campos por ( : ) los dos puntos y estos campos son la información que se debe dar para dar de alta un usuario. La línea de entrada contiene: Login : passwd : UID : GID : nombre completo del usuario : Directorio Home : : Shell del usuario En el caso de que el campo passwd esté vacío es que no tiene contraseña y si el nombre no aparece, no pasa nada. Todos los campos son obligatorios menos el passwd y el nombre completo del usuario. El login no puede ser igual en dos entradas del fichero. Tampoco puede haber dos UID iguales. Lo que si puede haber son 2 contraseñas iguales. Las contraseñas aparecen en el fichero encriptadas, tienen que ser de 6 caracteres, contener números y letras y que no deben coincidir con datos pertenecientes al usuario y no deben estar en el diccionario del sistema, pluralistas. La contraseña puede cambiarse con passwd, y el administrador o superusuario puede cabmiar todas las contraseñas. Con : !passwd : poniendo el cierre de admiración en el campo password se deshabilita una cuenta. 69

Hay otro fichero / etc / shadow , y este es el que contiene las contraseñas del usuario, ya que en el fichero de password se podían ver las contraseñas aunque estén encriptadas , solo tiene permiso de lectura para el administrador y tiene una entrada pro cada uno de los usuarios y permite almacenar en el otro tipo de información relativa a la cuenta del usuario. Edad mínima , el tiempo que tiene que transcurrir antes que pueda cambiar la contraseña. Edad máxima, el tiempo máximo que puedo tener una contraseña. Pwconv crea el fichero shadow con la contraseña con * Pwunconv aparece la contraseña encriptada. . profile se ejecuta siempre que entra en el fichero. Cuando damos de alta un usuario no solo hay que poner la línea si no que hay que crear el directorio HOME, y copiar algún fichero como el . profile y algún otro y todos ellos se encuentran en el directorio / etc / skel es necesario copiarlos al directorio de usuario. Si quiero dar de baja un usuario : USERDEL Herramienta gráfica A mano. Eliminar la línea correspondiente / etc/passwd y también debería borrar el directorio del usuario. Los grupos de usuario también se gestionan. Con newgrp puedo cambiarme de grupo y tendrás los permisos asignados a ese grupo, cuando entro pertenezco al grupo que aparece a al entrada / etc / passwd . : : : GID : Es posible que un usuario pertenezca a más de un grupo, pero en un determinando momento solo perteneceré a un determinado grupo. También tenemos el fichero /etc/group que contiene los grupos que están dados de alta en el sistema y otra información relativa a esos grupos. Hay 4 campos: Nombre grupo: Password : GID : lista de usuarios pertenecientes al grupo. Este último campo va separado por comas. No es común que exista el campo contraseña. Existe un tipo de Shell que se denomina Shell restringido que se suele llamar RSH, las restricciones son : que no se puede utilizar comandos como CD, no se puede cambiar el valor de la variable PATH, no se pueden utilizar rutas completas, no se puede dirigir la salida con los comandos >, >>. Nota: para eliminar los ficheros de un usuario se hace: Find / − user ( username ) −exec. Etapas del Shell:

70

Sustituciones de History : a medida que vamos introduciendo comandos lo almacena en un fichero que se denomina como . HISTORY, y si visualizo, veo los comandos que he utilizado durante su uso, si pulso la tecla de cursor ! se van viendo. Si ejecuto el comando HISTORY me aparece todos los comandos que hemos ejecutado. • instrucción • instrucción . • Instrucción • .. • Y si quiero hacer referencia a alguno tengo que poner : !número etiqueta. Si pongo ! − n ejecuto el enésimo comando anterior, equivaldría a: !−1=! ! − 2 = ! ! a pulsar 2 veces la tecla de cursor. También es útil el comando para parámetros. ! el primero. ! $ el último. ! * todos los parámetros. Ejemplo: Si pusiese CAT PEPE y luego pongo RM ! $ haría referencia del último parámetro del comando. Cuando pongo rm ! $ me sustituye esto por el parámetro, luego me sustituirá el alias si lo hay. Si quiero ver los alias definidos basta con poner ALIAS y si quiero quitar alguno UNALIAS nombre. Para asignarle : Alias dir = `ls ` Ejemplo: dir ! $, traduce como dir y el parámetro, luego lo transforma como ls y el parámetro. Lo tercero es la sustitución de las variables: Ejemplo: $HOME lo sustituye por / home / alumnos / segundo/ gr2ges /37671 Ejemplo: Copy ! $ $HOME Primero se sustituye el !$ luego el comando Copy y lo tercero $HOME por la dirección que sea. Lo cuarto que se traduce es la expansión de ficheros: *, ? , [ ]. ~ Hace referencia al directorio HOME del usuario. La quinto es la sustitución de comandos. Ejemplo : a = ` date'. Lo sexto es la redirección. Si tiene que crear un fichero u otra cosa. 71

Todos estos pasos se realizan antes de ejecutar los comandos. Si ponemos PS1 contiene el valor del prom del sistema. Ejemplo: PS1 = Hola buenos días Ejemplo: si pongo cad = hola. PS1 = $cad Cad = adiós En este ejemplo PS1 seguirá valiendo Hola, para que valiera adiós hay que poner: PS1 = `echo $ cad ` Las comillas dobles ( ) desactivan la generación de nombre y archivos, pero mantienen la sustitución de comandos y variables. Ejemplo: echo $ term sigue manteniendo el valor. Si pongo ls * lo anula y me mostraría un fichero cuyo nombre sea el asterisco. La comilla simple ( ` ) no realiza nada, desactiva toda función de análisis. Si pongo echo ` $HOME ` me sacará por pantalla $HOME. El apóstrofe ( ` ) implica la sustitución de comandos. Entrada Estándar : podemos hacer referencia con un número que es el 0. Salida Estándar : hacemos referencia con el número 1. Error Estándar : cuando escribo un comando y no especifico nada, los errores que se producen van a salir por el error estándar. El error estándar está referenciado a la pantalla y nos referiremos a este error con el número 2. El error estándar lo puedo redirigir y así no me aparece por pantalla. Ejemplo: En este ejemplo suponemos que el fichero1 no existe. Cat fichero1 2 > fichero2 Donde el 2 sirve para que en vez de sacarlo por pantalla lo pase al fichero. Si quiero redirigir la Salida y el error estándar tengo que poner. Cat f1 1> f2 2> ficheroerror. Si quiero redirigir la salida y error estándar al mismo fichero. Cat f1 1 > f2 2 > &1 donde el &1 hace referencia a la salida estándar. Con set − o noclobber impedimos que una redirección con un operador > sobreescriba el fichero existente.

72

Con >! forzamos a la sobreescritura del fichero ignorando el noclobber. Con set + o noclobber sirve para desactivar Con noglob desactivamos los caracteres especiales como *, ? , etc. GESTIÓN DE PROCESOS. Ps muestra los procesos que hay en el sistema, nos muestra el PID ( identificación del proceso ), el TTY ( terminal asociado desde el que se ha ejecutado el proceso ), el comando que ha motivado la aparición del proceso, la hora, el estado del proceso si aparece una r ( ejecución) si aparece una s ( dormido ) y si aparece una z ( zombie ). El directorio / proc contienen muchos ficheros y cada uno de estos son las imágenes de los procesos que hay en memoria. Modo habitual es: FOREGROUND. Cuando metemos un comando en el shell hace un Fork y crea un shell hijo y es el que ejecuta el comando y el shell padre espera a que acabe para que tome otra vez el mando. Modo inmediato es : BACKGROUND. El comando se ejecuta y el shell padre crea un hijo pero no espera a que acabe el shell hijo, podemos continuar introduciendo comandos. Se utiliza para aquellos trabajos que no tengan una característica interactiva con el usuario. Cuando ejecuto alguno en background se añade el aspersand al final del comando. Ejemplo : find . −name $ logname & Si no especifico nada la salida es por pantalla y a continuación trato de editar un fichero. Vi practica5 en la pantalla me aparecerán los datos del find. Lo normal es redirigirlo o mandar a background aquellos trabajos que no necesitan salida por pantalla. Normalmente me aparece [ ] que es el número de proceso que luego lo puedo utilizar poniendo: Background numproceso. Foreground numproceso. ¿Qué pasa cuando me salgo del Sistema? Los comandos tienen un terminal asociado, en el cuál van ha producir la salida. Si pongo exit finalizo la sesión. Si pongo Exit en foreground no tengo trabajos. Si pongo Exit en background esos trabajos son interrumpidos por el sistema. NOHUP manda un trabajo en backgroung y no será interrumpido cuando finalice la sesión en el sistema.

73

Ejemplo : nohup nombre comando & No tiene ningún terminal asociado, las salidas de esos comandos van a pasar a un fichero que se llama nohup. Out KILL : sirve para enviar señales a un proceso, entre estas señales está la de terminación que hace que concluya un proceso y es ( KILL − 9 ) . La instrucción se pone: Kill número_señal número_proceso. Ejemplo: Kill −9 23456 Solo podemos matar procesos propios no de otros usuarios. Cuando se arranca el sistema operativo se crea 2 procesos. Antes hay un proceso 0 que hace una llamada a fork y se crean el proceso 0 y el nuevo proceso 1. El proceso 0 es el planificador y el proceso 1 es el INIT. PROCESO 0 Fork Proceso 0 Proceso 1 Planificador Init Cuando arrancamos leemos un fichero que es /etc/ inittab que contiene una serie de campos que sirven para el arranque. Identificador : Secuencia de 2 caracteres que identifican la línea. Runlevels : Estados INIT en los que se debe ejecutar las acciones correspondientes. Acción : La que se ejecuta. Proceso: El que se va ha ejecutar. Ident : runlevels: acción : proceso En Unix se puede arrancar en diferentes niveles, pero solamente puede estar en uno de esos niveles y dependiendo de ese estado el estado de la máquina va ha ser diferente. NIVEL 0 : desenchufado de la máquina ( halt ) NIVEL 1 : Modo monousuario, el administrador solamente puede conectarse a la máquina y tiene que hacerlo de forma local.

74

NIVEL 2 : Multiusuario sin red, es posible abrir varias sesiones con el sistema pero no está disponible la red. NIVEL 3 : Multiusuario con red, se puede conectar cualquier usuario de cualquier tipo. NIVEL 4: No se usa normalmente. NIVEL 5 : Se conoce como X_Window, la consola aparece en modo gráfico. NIVEL 6: Nivel de desconexión y arranque ( es como reiniciarlo). NIVEL s : NIVEL S : son monousuarios, peor permiten conectarse desde una consola remota. El administrador puede pasar de un nivel a otro a través del comando INIT y el número de nivel. Ejemplo: INIT 0 para apagar la máquina. Si : : sysinit : etc / rc . d / rc . sysinit Cuando ponemos en ese campo : : quiere decir que es para todos los niveles. Sysinit es la acción y se va ha ejecutar durante el arranque del sistema. Rc . sysinit es el Script que se ejecuta siempre durante el arranque del sistema. Hay otros tipos de acciones: • Respawn : el proceso que se ejecuta a continuación será arrancado una vez termine el proceso. Ejemplo: Respawn : getty • Wait : El proceso es arrancado al ejecutar el nivel de ejecución especificado y el proceso INIT espera a la terminación del proceso antes de terminar. • Once : Especifica que solo se ejecutará una vez. • Boot : Se ejecutará durante el arranque. • Initdefault : Especifica el nivel de ejecución por defecto en el que se arrancará el sistema, y no lleva ningún tipo de proceso. Ejemplo : in : 3 : intitdefault : Nos podemos encontrar cosas como: Id : 12345 : wait : / etc / rc . d / rc . local De tal forma que INIT no continua hasta que el script rc . local no se ejecute. Donde rc . d contiene una serie de directorios como por ejemplo ( rc0 . d ; rc1 . d rc2 .d) que a su vez contienen scripts que se ejecutarán cuando el sistema entre en el nivel correspondiente. Nos encontraremos Scripts que empiezan por S o por K, tendrán una serie de números y a continuación el nombre del servicio al que afecta. Los que empiezan por S son Scripts que arrancan el servicio 75

correspondiente. Los que empiezan por K finalizan el servicio correspondiente. Los números del medio ayudan a determinar el orden en el que se ejecutan cada uno de los scripts. ( Los Unix modernos utilizan START para arrancar y STOP para parar). INIT . d es un fichero que realmente contiene los archivos que reinician y cierran los demonios. En Rc1 . d, rc2 . d vemos enlaces simbólicos (especie de punteros ) a ficheros que están el directorio int . d . Por lo tanto el fichero INIT . d es el más importante. Tenemos 2 variables: • $$ que contiene el PID del shell actual. • $! Que contiene el PID del último trabajo enviado en background. NOTA : para conectar 2 ordenadores por puerto serie es: S1 : 3 : respawn/ sbin / mingetty 38400 ttyS0 linux. En el fichero . / etc / rc . d / init . d / functions están definidas la funciones que utilizan los scripts de arranque y finalización de servicios. El sistema en vez de incluirlos en cada scripts de arranque los almacena en este fichero y después lee el fichero functions y los carga en memoria y así facilitará su invocación desde un script. Ejemplo: Function borrar ( ) { clear este script lo metemos en un fichero y lo echo Borro la pantalla llamamos . fun. } Y en otro script pongo . fun y así leo las funciones que tengo en el fichero fun . . fun echo voy a borrar read a borrar Si pongo en prom $ . fun también valdría, luego pongo $ Borrar y me borraría la pantalla. El operador punto carga el script en el propio script en el que estamos. IMPRESIÓN EN UNIX.

76

Utilizamos una cola de impresión llamada Spool para almacenar los trabajos y después con el demonio ( lpd) que es el que se encarga de enviar los datos a la impresora. La cola es un directorio /var / spool / lpd / lp0 Lp1. En este fichero de impresión vamos a tener 4 ficheros: • Lock : Sirve para que 2 procesos no utilicen la impresora a la vez. • Status: Manejas el estado de la impresora. • Errors: Ves los errores generados durante impresión. • . seq : Asignas una secuencia a cada uno de los trabajos. El fichero / etc / printcap contiene todos las definiciones d todas las impresoras lógicas que tenemos. Dentro del fichero tienen campos y utiliza los : para separar los campos. Nombre impresora : : Siempre conviene tener una impresora por defecto y se hace con lp a no ser que tuviésemos la variable PRINTER. Comandos que Utilizamos. LPR : manda el trabajo a la cola de impresión. LPR − P nombreimpresora: nos dice sobre que impresora deseamos imprimir. LPRM : elimina un trabajo de la cola de impresión. LPQ : nos muestra el contenido de una cola de impresión. LPC: Podemos controlar el proceso de imprimir trabajos (start/ stop) o admitir o no trabajos en la cola de impresión ( Enable / disable). Con ( up / down ) equivale a tener los otros dos juntos ( enable y el start / disable y el stop ). SISTEMAS DE FICHEROS. Directorio Raíz. Punto de entrada, el más importante. Tenemos 2 formas : forma absoluta ( parte del directorio raíz), forma relativa. El Kernel está en el directorio Raíz o bien en el BOOT. Directorio BOOT. Contiene archivos estáticos del cargador de arranque. Las tablas de particiones del disco se encuentran en el boot. Directorio BIN. Contiene comandos esenciales de usuarios. Comandos como ls, cat, chmod etc.

77

Directorio DEV Contiene un archivo por cada dispositivo que el kernel puede soportar. Ejemplo: • lp0 ( impresora ) • fd0 ( disquetera) • hda ( primer disco duro) • hdb ( segundo disco duro) Directorio ETC. Contiene configuración del sistema local. Hay ficheros que se encargan de la configuración de impresoras ( printcap ), de usuarios ( passwd ), de la máquina ( inittab). Directorio HOME. Directorio hogar que contiene el de cada usuario. Directorio LIB. Contiene librerías compartidas. Directorio MNT. Es el punto de montaje para sistemas de archivos montados temporalmente. Directorio PROC. Contiene información sobre procesos. Directorio ROOT. Es el directorio del superusuario. Directorio SBIN Contiene comandos que solamente pueden ser ejecutados por el superusuario. Ejemplo: Mkswap Shutdown Swapon Directorio USR Contiene subdirectorios y son de solo lectura, dentro de los subdirectorios hay 2 que son: • BIN : Comandos que los ejecuta cualquier usuario. • SBIN: comandos que solo los puede ejecutar el administrador. c) Directorio MAN. 78

Contiene todas las páginas del manual. Directorio VAR. Contiene archivos con información variable , la información no es permanente, va a variar. • Catman : es utilizada por nroff a la hora de visualizar páginas del manual. • Lock : archivos de bloqueo. • Log : Contiene archivos de bitácora es decir de registro. • Spool: Contiene trabajos para su procesamiento posterior. Sistemas de Ficheros. El montaje del sistema de ficheros. Ejemplo: / bin Si quiero montar un disco este tiene que poseer un sistema de ficheros (un estilo al formateado), y montar ese árbol sobre mi sistema de ficheros. / disco. Ejemplo: / / bin mnt ope Edi Mat fd0 cdrom Esto es lo que quiero montar. ope Edi Mat El comando MOUNT sirve para montar un sistema de ficheros, y hay que especificar el dispositivo donde está esos archivos ( el sistema de ficheros) y especificar el punto donde lo voy a montar en mi sistema de ficheros. Ejemplo: MOUNT opciones /dev / fd0 / mnt / fd0 (En las opciones es necesario a veces especificar el tipo de sistemas de ficheros que voy a montar). Los CD_ROM en Linux es ISO 9660. Ejemplo: mount −t ISO 9660 / dev / cd_rom /mnt/cd_rom

79

El −t sirve para el tipo MSDos. Para desmontar el sistema de ficheros se utiliza el comando AMOUNT dispositivo punto de montaje. Para desmontar el sistema de ficheros no puede haber nadie en ese sistema de ficheros. Existe un fichero que se llama fstab que se encuentra en \etc \ fstab que contiene información sobre el sistema de ficheros que el sistema Operativo montará de forma automática al arrancar. Ejemplo: /dev / hda2 /home / alumnos opciones Donde el HD es el disco duro Donde la a es uno de los discos duros Donde el 2 es la segunda partición. Se montará en alumnos y las opciones es si es posible la lectura, escritura sobre el sistema de ficheros. Dentro de las opciones la más común es tener default, se monta como escritura / lectura, se montará como bloque, los usuarios ordinarios no pueden hacer montajes en ese punto y se pueden ejecutar programas en él. El NFS es un sistema de fichero que se llama Network File System y es el fichero de sistema de red. El fichero /proc/filesystems contiene el nombre de los sistemas de ficheros que es capaz de soportar el Sistema Operativo. Con el comando MKFS permite crear un sistema de ficheros, es parecido a formatear un disco. Ejemplo: mkfs /dev / fd0 /440 El comando MKDEV sirve para añadir un fichero de dispositivo. Es un script que se encarga de solicitar la información que necesita. El comando FSCK chequea un sistema de ficheros y en caso de encontrarlo lo repara. El comando DF muestra el nivel de ocupación de un sistema de ficheros. Enlaces duros y enlaces simbólicos. Enlace: Es como una referencia a otro fichero, esta referencia se guardan en el inodo correspondiente. Enlaces duros: Ocurre que dentro de cada información asociada a cada fichero ( ls − l ) , está el número de enlaces que hay al fichero, al borrar un fichero solo borramos la unión entre la entrada de directorio y el inodo correspondiente. Solamente al borrar el fichero con número de enlaces uno es en realidad cuando se borra el archivo del disco. Es posible que yo borre un fichero al que se tenga enlace y los demás que tuvieran el enlace puedan seguir accediendo al fichero, no importa de quien sea el fichero, sino que el fichero estará en un inodo del disco que es el que contiene la información del fichero. Los inodos apuntan al fichero en disco y los enlaces duros apuntan a dichos inodos.

80

• Desventajas: • No pueden atravesar sistemas de ficheros. Enlaces simbólico: En el caso del enlace simbólico se guarda la ruta completa del fichero al que enlazo, es equivalente a crear un fichero cuyo contenido es la dirección donde se encuentra el fichero. El tamaño del enlace es igual al número de caracteres de la ruta del fichero. • Desventajas: • Si se borra el fichero original, ya no se puede acceder a ese fichero. • Ventajas: • Si son capaces de atravesar sistemas de ficheros. El comando que permite hacer enlaces es LN. Ejemplo de Enlace duro: Ln fichero_viejo fichero_nuevo Donde el fichero_viejo es el fichero apuntado y el fichero_nuevo es el fichero que apunta. Ejemplo de Enlace simbólico: Ln −s fichero_viejo fichero_nuevo Al hacer un ls − l nos aparecerá en el primer carácter: − fichero d directorio l enlace simbólico. El comando DD permite hacer copias exactas de discos flexibles, presenta la ventaja de que el disco sobre el que hacemos la copia no necesita tener ningún sistema de ficheros previamente. Se necesita especificar el dispositivo de origen ( < ) y el primer paso es almacenar temporalmente los datos en el disco duro y en un segundo paso hay que: If = / dev / fd0 of = /tmp/fd0 dd /tmp / fd0 dd < / tmp / fd0 > /dev / fd0 Donde /dev/fd0 es el fichero de entrada Donde /tmp/fd0 es el fichero de salida No es necesario montar la unidad de disco. Existen 3 opciones: • if = especifica fichero de entrada 81

• of = especifica fichero de salida • bs = especifica el número de bloques que es capaz de leer a la vez. El comando TAR ( tape archivo ) permite archivar archivos en cinta, hoy en día permite agrupar una serie de ficheros en un solo fichero y después podemos reemplazar o extraer ficheros del fichero grande pudiendo tratar los ficheros del fichero grande de manera individual. Sintaxis: TAR opciones: C crea un fichero V Modo verbose aparece información F Fichero de entrada o de Salida X Extraer R Reemplazar T Lista. Ejemplos: Tar cvf dir.tar directorio Donde dir.tar es el fichero a crear Donde directorio es el nombre del directorio del que voy a hacer el tar incluye los subdirectorios. Tar xvf dir.tar Extrae todos los ficheros y directorios incluidos en el archivo dir.Tar. El comando GZIP es capaz de comprimir un fichero Gzip nombre_fichero Si queremos comprimir varios ficheros pues lo haríamos primero con TAR y luego con GZIP. El comando GUNZIP descomprime un fichero. El GZIP tiene grados de compresión ( − 1 y − 9 ), según sea un grado será mayor grado de compresión y tardará más. En el comando TAR está la opción z con la cual podemos trabajar a través de ficheros comprimidos por gzip. Ejemplo : tar xvfz dir.tar.gz descomprime y hace el tar Tenemos otros comandos como COMPRESS y UNCOMPRESS que se mantiene por compatibilidad y generan archivos con extensión . Z . 82

El gzip y el gunzip borran el fichero que comprimieron o descomprimieron. El comando CPIO acepta una lista de ficheros y copia estos ficheros en un único fichero de salida además inserta cabecera entre cada uno de los ficheros para su posterior recuperación. Ejemplo: | ls ¦ cpio o find . −name fiche * − print ¦ cpio Siempre habrá un comando antes de cpio que proporcione una lista de fichero. La opción para crear el fichero es la opción − O, este comando no comprime los ficheros, solo los une. La opción − i es para leer ficheros de un único fichero. El comando SHUTDOWN permite realizar un apagado ordenado del sistema , las opciones son: −r Apaga y reinicia ( init 6 ) −h Hace un Halt o apagado de la maquina ( init 0 ) − Aparece en el terminal de todos los usuarios. Es un mensaje. − tiempo Especifica cuando se va a apagar la maquina. • now Apagarse ahora • + n Tardará n minutos. − k Amaga un shutdown pero no lo hace Si se está haciendo un SHUTDOWN ( por ejemplo de 5 minutos 9 pues ningún usuario se puede conectar al sistema. OTROS COMANDOS ( no estudiar) Mail Permite enviar correo. Mesg Con la opción − n se deshabilita la opción de que otro usuario pueda escribir en nuestro terminal. SISTEMAS MULTIPROCESADORES. Quiere decir varios procesadores. Proporcionan una alternativa arquitectónica para mejorar el rendimiento de los sistemas informáticos, mediante la reunión de varios procesadores. Vamos a ganar en fiabilidad o tolerancia a fallos. Ejemplo es que si tengo 2 procesadores y me falla uno todavía puedo hacer algún trabajo. Esto puede servir para adaptar el sistema a mis necesidades, un tipo de trabajos a un procesador y otro tipo a otro procesador.

83

Clasificaciones de sistemas multiprocesadores según FLYNN, que se basa en como se relacionan los datos o las secuencias de datos y secuencias de instrucciones. • Relación SISD ( single instruction single data): una secuencia de instrucciones o una sola, un solo dato o una secuencia de datos. Solamente podemos estar ejecutando una instrucción en un determinado momento y solo un dato. • Relación SIMD : una sola instrucción, varios datos. Esta instrucción la puedo aplicar a un conjunto de datos diferente. • Relación MISD: múltiples instrucciones sobre un solo dato, tengo varios procesadores y cada uno realiza una operación diferente sobre un único dato. • Relación MIMD: múltiples instrucciones sobre múltiples datos. Hay n procesos, n conjuntos de datos y cada uno realiza operaciones diferentes sobre datos diferentes. La relación de procesadores_memoria es : • Sistemas débilmente acoplados ( sistemas distribuidos) Los procesadores individuales tienen memorias privadas y no existe una memoria globalmente compartida los sistemas funcionan independientemente y se comunican entre sí a través de un enlace de comunicación. • Sistemas fuertemente acoplados Los multiprocesadores contienen memoria globalmente compartida a la que todos los procesadores tienen acceso. Tienen una memoria y ambos Acceden a la misma memoria. Un sistema multiprocesador no tiene porque ser un sistema distribuido pero un sistema distribuido si es un sistema multiprocesador ya que un sistema distribuido tiene varios procesadores, pero si es un sistema fuertemente acoplado ya no cumple que sea distribuido ya que el sistema distribuido tiene su propia memoria en los procesadores. Sistemas operativos multiprocesadores. Vamos a ver tres tipos: • Maestro_satélite: Sencillo de implementar, solo un procesador que va ha ser el maestro el que puede ejecutar el sistema operativo y los demás se van a encargar de ejecutar programas de usuario. Todo lo que necesite el sistema operativo se hace dentro del procesador Maestro. El maestro planifica los diferentes procesadores satélites. Ventajas: • Sencillo de implementar. Desventajas: • Si falla el maestro no podemos continuar. • Dependiendo de la carga del sistema se pueden formar cuellos de botella en el procesador maestro.

84

Este tipo permite paralelismo dentro de una aplicación, pero no es posible paralelismo a nivel del sistema operativo porque es el maestro el único que puede ejecutar instrucciones del sistema operativo. • Ejecutivos separados: Cada procesador tienen su propio sistema operativo, este gestiona la memoria, recursos de Entrada/Salida de forma que ese sistema operativo responde a las interrupciones de los usuarios que operan en ese procesador. Los procesos son asignados a los procesadores lo que hace que un proceso se tenga que ejecutar hasta su finalización en el procesador correspondiente. Desventajas : • No es posible el equilibrado de las cargas de trabajo entre los diferentes procesadores ya que los procesos son asignados por el sistema. Aquí no existe paralelismo dentro de una misma aplicación. Lo normal es que haya algún procesador encargado de asignar los trabajos a los procesadores. • Organización Simétrica: Todos los procesadores son idénticos y el sistema operativo es simétrico en el sentido de que cualquier procesador puede ejecutar el sistema operativo pero el sistema operativo en un momento determinado solo va a estar en un procesador. Se suele llamar Sistema flotante. Así cualquier procesador gestiona la entrada / salida del sistema operativo y cuando un procesador necesite ejecutar algún tipo de operación que necesite el sistema operativo este flotará a este procesador. Los procesos no están asignados a procesadores, se pueden ejecutar en cualquier procesador. Ventajas: • Cuando falla un procesador no ocurre nada. • El sistema operativo solo está en un procesador. • El equilibrado de cargas se encarga el procesador que disponga del sistema operativo en ese momento. Aquí si puede haber paralelismo en la aplicación. Tengo que explicar en que momento la aplicación se va ha ejecutar por separado, cuales se ejecutan concurrentemente y cuales no. Con multiprocesadores no tarda menos una aplicación, no se ejecuta en menos tiempo. La planificación por parte del Sistema operativo : tiene un planificador que asigna procesos a cada uno de los procesadores. Nos imaginamos que tenemos: P1 P2 P3 P4 0ABCD ¿Qué pasa si A y V son procesos operativos? 1VXYZ 2ABCD 85

3VXYZ Tenemos RR(20) y tenemos el proceso A que vale ( 2 ) y ahora necesitamos sincronizar con V , lo que pasa es que tendríamos que durante 18 periodos estaría parado. Por lo tanto procesos que cooperan entre sí deben sincronizarse evitando estas operaciones y planificados para que se ejecuten de forma simultánea. En los sistemas débilmente acoplados tenemos un proceso que se ejecuta en P1 y queremos cambiarlo a P2, lo que pasa es que tenemos que poner una serie de variables adicionales que son las que especifican donde estaba el proceso en el procesador primero, por lo que hay veces que no nos interesa cambiar los procesos. Afinidad entre procesos y procesadores. En el caso de los sistemas débilmente acoplados al ser máquinas diferentes es más difícil que los procesadores sean diferentes de tal forma que las operaciones pesadas (de muchos cálculos) se ejecuten en los procesadores más potentes aunque tengan que esperar ( habiendo un procesador menos potente libre). Sistema Distribuido. Colección de sistemas informáticos autónomos capaces de comunicarse y cooperar a través de interconexiones hardware y software. Necesito algún enlace par unir los sistemas. Características: • Son débilmente acoplados ( Carecen de memoria globalmente compartida). • Si tengo sistemas autónomos, pero son capaces de comunicarse. Va a aparecer un retardo en la comunicación entre los elementos. • Falta de un estado global. Ventajas : • Compartir recursos y equilibrado de cargas. • Comunicación y compartición de información. • Fiabilidad y tolerancia a fallos. • Rendimiento. • Posibilidad de crecimiento integral. • Disponibilidad. Desventajas. • Complicada la gestión de recursos de memoria entre nodos distintos. • Aumento de la dependencia con respecto al rendimiento y fiabilidad del enlace de comunicación. • Debilidad en la seguridad. • Administración y mantenimiento más complejo. Concepto de transparencia. Da una idea de perfección del sistema como un todo en vez de cómo una colección de elementos individuales 86

independientes. Es la ocultación al usuario y programas de la separación de componentes en un sistema distribuido. Tipos: • De acceso: Permite a los usuarios o los programas acceder a los objetos locales y remotos utilizando las mismas operaciones. • De localización: Permite acceder a los objetos sin necesidad de conocer su ubicación. • De concurrencia: Permite a varios procesos ejecutarse de forma concurrente utilizando información compartida sin interferirse entre ellos. • De replicación: Permite la utilización de diferentes instancias de un objeto sin necesidad de conocimiento de las mismas por parte de los usuarios o de los programas de aplicación. • De migración: Permite mover elementos e información de un sistema a otro sin que esto afecte a los usuarios o a los programas. • De tolerancia a fallos: Permite ocultar fallos a usuarios y programas permitiendo que estos puedan continuar su ejecución a pesar de los fallo Hardware o software. • De rendimiento: Permite reconfigurar el sistema para mejorar el rendimiento a medida que la carga de trabajo varía. • De escalabilidad: Permite añadir nuevos elementos sin necesidad de cambiar el sistema ( cambiar su estructura o los algoritmos de los programas). Los tipos de acceso y de localización se llaman de transparencia de red. Coordinación en Sistemas Distribuidos ( SSDD). En un sistema distribuido no existe ni memoria , ni relojes comunes, por lo tanto es difícil determinar entre 2 sucesos cuál ha ocurrido primero. Para esto se definen una relación que se llama sucedió antes o primero que es una ordenación parcial de sucesos en sistemas distribuidos. Todos los sucesos de un mismo proceso están ordenados. >Un mensaje solo puede ser recibido si antes ha sido enviado. La relación se define de la siguiente forma: Si A y B son sucesos del mismo proceso y A se ejecutó antes que B entonces esto se expresa de la siguiente forma: AB Si A es el suceso consistente en enviar un mensaje por parte de un proceso y B es el suceso de recibir ese mismo mensaje pro parte de otro proceso esto lo expresamos como A sucedió antes que B. AB Si A sucedió antes que B y B antes que C podemos decir que A sucedió antes que C. AB y BC entonces A C. No es posible que A suceda antes que A. En cualquier otro caso si 2 sucesos A y B no están relacionados por la relación sucedió antes AB, BA diremos que esos procesos se ejecutan concurrentemente. Ejemplo:

87

P4 Q4 R1 P3 Q3 P2 Q2 P1 Q1 P0 Q0 R0 Proceso(P) Proceso(Q) Proceso(R) En el eje vertical especificamos sucesos. Tenemos 3 procesos en 3 procesadores y tenemos envíos de mensajes. P0 P1 ( P0 ocurre antes que P1) P1P2 Q1Q2 Aquí tenemos que P1P2 Q1P4 Q3R1 R0Q4 Si existe un camino entre 2 sucesos podemos afirmar que uno ha ocurrido antes que otro. Dos procesos son concurrentes si no existe ningún camino entre ellos. A cada uno de los sucesos le vamos asociar un registro de tiempo llamado TIMSTAMP. Esto quiere decir que si AB la marca de tiempo de A tiene que ser menor que la de B. Para asociar esas marcas a los procesos vamos a utilizar relojes lógicos, por ejemplo un contador. Los sucesos ocurren en diferentes procesadores. Py recibe un mensaje con una marca de tiempo superior a la suya , entonces avanza su reloj lógico de tal manera que el nuevo valor del reloj es igual a la marca de tiempo recibida más uno. LCi ( B ) < t LCi ( B ) = T + 1 Hay una circunstancia en la que el reloj lógico: LCi ( B ) = LCi ( A ) entonces la ordenación la hacemos a través de la identidad del proceso. 10

88

recibe instante con marca 10 ¿Qué pasa si A y B solicitan el recurso a la vez? B solicita el recurso y se le asocia una marca de tiempo. A dos eventos no se les puede asignar la misma marca de tiempo A y B tienen identidad, no hay necesidad de considerar las marcas de tiempo. Podría ocurrir que envío un mensaje en un instante de tiempo 10 lo recibo y lo pongo una marca de tiempo 10. ¿ Incremento la marca y se lo asigno al mensaje recibido? Tengo que incrementarlo ya que tiene que ser una marca de tiempo posterior, lo incremento. Como reloj lógica " T reloj lógico = t + 1. Problema de la Exclusión mutua en Multiprocesadores. Existen 3 procesadores: • Solución centralizada. Se centraliza todas las solicitudes del recurso a través de un nodo que es el que concede la utilización de dicho recurso. Podemos tener tres tipos de mensaje: • Solicitud • Concesión ( asignación). • Liberación Cuando desea utilizar un recurso envía un mensaje de solicitud al nodo central, este nodo entre todas las solicitudes asignará el recurso a una de ellas a través de un mensaje de concesión y quedará a la espera de recibir un mensaje de liberación por parte del proceso al cuál había enviado el mensaje de concesión. La concesión del recurso se hace en base a marcas de tiempo incluidas en la solicitud. Solicitud concesión liberar Problemas: • Si falla el nodo central entonces falla todo lo demás. • Paso de testigo Tenemos un tipo especial de mensaje llamado testigo, el cual vamos hacer circular a través de todos los nodos del sistema, los nodos van a estar dispuestos en forma de anillo lógico y ese anillo va a ser unidireccional. Solamente aquel proceso que disponga del testigo podrá utilizar el recurso compartido. Es importante que el anillo sea unidireccional porque así antes o después el testigo pasará por cualquiera de 89

los nodos. Si no se desea ningún recurso el testigo continúa. Problemas que plantea este enfoque: • Perdida de testigo • Si falla alguno de los nodos del anillo es necesario reconstruir dicho anillo. • Si nosotros añadimos alguna máquina hay que reconstruir también el anillo. • Solución distribuida Vemos el algoritmo de Ricart y Agrawala que funciona de la siguiente forma: Cuando un proceso Pi quiere ingresar en su Sección Crítica genera una marca de tiempo y envía un mensaje con su identidad y marca de tiempo a todos los demás procesos. Cualquier proceso al recibir un mensaje puede contestar de inmediato o diferir la contestación. Un proceso que ha recibido contestación por parte de todos los demás procesos, podrá ingresar entonces en su Sección Crítica. Los mensajes que reciba mientras está en su Sección Crítica los encolará y diferirá ( retrasará) su contestación, una vez finalizada su Sección Crítica, responderá a todos los mensajes diferidos. La decisión de responder a un mensaje depende de varias circunstancias: • Si un proceso está en su Sección Crítica cuando recibe el mensaje entonces diferirá la contestación. • Si un proceso no quiere entrar en su Sección Crítica entonces responderá de inmediato. • Un proceso quiere entrar en su Sección Crítica en cuyo caso comparará la marca de tiempo del mensaje recibido con su propia marca de tiempo, si su marca de tiempo es mayor enviará una respuesta, si no diferirá la respuesta. A=10 B=4 A contestación de C (A, 10) (B,4) (A, 10 ) diferir a A B C (B,4) contestación de C En este ejemplo suponemos que C no quiere acceder a su Sección Crítica, C contesta inmediatamente el mensaje enviado por A y por B. B difiere su respuesta a A ya que su marca de tiempo es menor que la de A. A contesta a B ya que su marca de tiempo es mayor que la de B, luego contestará a todos los mensajes que tenía diferidos. Miramos que pasaría si: C ahora quiere acceder a su sección crítica y B está en su Sección Crítica.

90

C=12 Cuando acaba B contesta a A y contesta a C y entre A y B miran a ver quien tiene menor marca. Difiere C contesta A (A, 10) (B,4) (A, 10 ) (C,12) BC contestación de C Todo proceso pasa por los siguientes estados. Petición de Excl. Mútua Para esto envía mensajes y se queda a la espera Entra en su S.C, aquí Se genera el evento De ha recibido todos. Sale de la S.C. Esta solución es valida ya que: • Garantiza la exclusión mútua pro que mientras un proceso está en su S.C diferirá todos los mensajes que reciba mientras tanto. • La solución no produce bloqueos; garantizamos que no hay inanición puesto que utilizamos marcas de tiempo. Problemas que presenta este algoritmo: • Es obligatorio que cada nodo conozca la existencia de todas los demás nodos. • Que pasa si uno de los nodos falla, lo lógica es que desaparezca de la lista de nodos de los cuales tenemos que enviar mensajes. El problema es después de enviar el mensaje si falla, ya que no tendremos respuesta. Por lo tanto es adecuado para sistemas pequeños. Gestión de Interbloqueos. Las soluciones que se dan a los interbloqueos son las que se dan a los interbloqueos son las que se dan a las bases de datos. Como se gestionan:

91

Siguen siendo válidas algunas de la soluciones para sistemas monoprocesadores. • Detección • Evitación • Prevención • Ordenar de forma global todos los recursos de forma que un proceso que solicite un recurso de una determinada clase ya no pueda solicitar recursos de una clase inferior. Esta solución es sencilla de implementar pero no es muy útil. • Esperar_Morir: Es una solución no apropiativa, si un proceso Pi solicita un recurso que tiene Pj , Pi esperará la concesión del recurso si su marca de tiempo es menor que la de Pj . En cualquier otro caso Pi muere ( ser reinicia pero manteniendo la misma marca de tiempo que tenía antes. • Herir_Esperar: Es una solución apropiativa, se concede inmediatamente la petición a los procesos más antiguos, si Pi solicita un recurso que tiene Pj , Pi espera si su marca de tiempo es mayor que la de Pj . En otro caso Pj es herido (reiniciado) y Pi pasa a utilizar el recurso. • Utilizar una versión distribuida del Algoritmo del banquero. • El número de mensajes intercambiado entre los nodos se incrementa notablemente. • Dos nodos podrían determinar que un estado es seguro, si tienen en cuenta peticiones diferentes pero esas peticiones de forma conjunta si podrían ocasionar interbloqueo. • Implica un algoritmo largo y complejo, por que añadimos procesos de otros nodos, etc. UTILIZAR UNA VERSIÓN DISTRIBUIDA DEL ALGORITMO DEL BANQUERO. • El número de mensajes intercambiados entre los nodos se incrementa notablemente. • Dos nodos podrían determinar que un estado es seguro si tienen en cuenta peticiones diferentes, pero esas peticiones de forma conjunta si podrían ocasionar interbloqueo. • Implica un algoritmo largo y complejo porque añadimos procesos de todos nodos, etc Detección de Interbloqueos en Sistemas Distribuidos. • Se usan también grafos, pero va a variar la forma, se denominan grafos locales. • Los nodos ( procesos ) se van a representar en el grafo sean o no sean locales, cada máquina va a tener su propio grafo y cuando un proceso P, en una maquina A, precisa un recurso Q, en una máquina B, envía un mensaje de solicitud y el caso correspondiente se dibuja en el grafo de la máquina B. • A partir de cada uno de los grafos locales de cada máquina nosotros pretendemos construir un grafo global en el sistema. • Hay 3 aproximaciones. • Centralizado • Jerárquica • Distribuida CENTRALIZADO. Construimos un grafo global en uno de los nodos de forma que ese nodo, en base al examen de ese grafo global que ha construido, sea el encargado de la detección de los interbloqueos. Tenemos que hacer distinción entre el grafo real y el construido. El Real describe el estado real pero desconocido en cualquier instante.

92

El global construido es una aproximación generado por el nodo coordinador durante la ejecución de su algoritmo. NODO A NODO B No hay interbloqueo de forma local. El grafo global sería así: Existe un ciclo entre P2 ,P3 y P4 y podemos determinar que existe interbloqueo. El mayor problema que tiene esto es la aparición de interbloqueos fantasma o falsos interbloqueos, son debidos al retraso de la comunicación entre los nodos y se producen cuando el algoritmo detecta en base al grafo que tienen un interbloqueo que no existe. Nodo A Nodo B Nodo Coordinado. P2 Libera el recurso y pide un recurso P3 . La flecha entre P1 y P2 desaparece y aparece una de P2 a P3 , si debido a retardo la petición de recursos de P2 llega antes que la de liberación. El grafo cambia siempre que cambia algún nodo coordinador estaría en interbloqueo sin estarlo realmente hasta que llegue realmente el mensaje liberar recurso de P2 . Hay 3 posibilidades para construir el grafo: • Construirlo cada vez que se inserta o elimina una arista en uno de los grafos de espera locales. • De forma periódica cada vez que hay un cierto número de cambios en un grafo. • Cada vez que el coordinador necesita invocar el algoritmo de detección. JERARQUICO. Existe una jerarquía de nodos de forma que un nodo no hoja construye el grafo de los nodos que están por debajo suyo, evalúa si existe o no interbloqueo en ese grafo y opera en consecuencia. ESTRATEGIA DISTRIBUIDA Todos los nodos comparten igualmente la responsabilidad de detectar bloques mutuos y cada nodo construye un grafo de espera que representa una parte del grafo total. La idea es que si hay un ciclo este aparecerá por lo menos en alguno de los grafos parciales. Al grafo de espera local añadimos un elemento extra que denominamos Pex de forma que existirá en el grafo una arista Pi Pex si Pi está esperando pro un recurso de otro sitio que está en posesión de cualquier otro proceso. Aparecerá una arista Pex Pi si algún otro proceso en otro nodo está esperando un recurso que actualmente está en poder de Pi . • Si encontramos un ciclo en el grafo que no involucre a Pex entonces podemos afirmar que el sistema está en un estado de interbloqueo. • Si encontramos un ciclo en el grafo que involucre a Pex implica que hay la posibilidad de interbloqueo. Para determinar si realmente existe interbloqueo es preciso invocar un algoritmo para su detección. En ese caso mandamos a alguno de los nodos información sobre nuestro grafo y con ella él construirá un nuevo grafo local, y volvemos otra vez hacer loso pasos. Ej:

93

Nodo a) P1 P2 Pex P5 P3 Existe un ciclo: P2 − P3 − Pex − P2 hay una posibilidad de interbloqueo. Este grafo envía información al grafo B y se añade la línea azul. Nodo b ) Pex P2 P4 P3 Pex − P3 − P4 − P2 − Pex Y con la línea azul tenemos: P2 − P3 − P4 y como no interviene el nodo P1 podemos afirmar que hay interbloqueo. VENTAJAS Y DESVENTAJAS DE LOS ALGORITMOS. En el caso de algoritmos centralizados ventajas: • Los algoritmos son simples y fáciles de implementar. • El nodo central dispone de información completa y puede resolver óptimamente los interbloqueos. Desventajas: • Es vulnerable a fallos en el nodo central. • Se produce una carga considerable de comunicaciones. En el caso de algoritmos jerárquicos. Ventajas: • No son vulnerables a fallos en un solo nodo • La actividad de resolución del interbloqueo se ve limitada si la mayor parte de los posibles interbloqueos están relativamente localizados. Desventajas: • Es difícil configurar el sistema para que estos interbloqueos estén localizados. En el caso de Algoritmos Distribuidos. Ventajas: • No son vulnerables a fallos en un nodo. • Ningún nodo recibe el peso específico de la detección del interbloqueo.

94

Desventajas: • Los algoritmos son difíciles de diseñar debido a las consideraciones de tiempo. • La resolución del interbloqueo es complicada porque se pueden detectar los interbloqueos sin darse cuenta de que hay otros nodos que están involucrados en el interbloqueo. Recuperación de Interbloqueo: Son los mismos que los de Sistemas Monoprocesadores. TRATAMIENTO DE FALLOS: Hay algoritmos que tratan los fallos y se denominan algoritmos de lección de sucesores y determinan lo que ocurre cuando un nodo coordinador falla, estos algoritmos suponen que existe un número de prioridad único asociado a cada proceso activo del sistema de forma que el nodo coordinador será el que tenga el número de prioridad más alto. Estos algoritmos deben garantizar que el nodo seleccionado como nuevo nodo coordinador es único. Algoritmo del matón. Es adecuado para sistemas donde cada proceso puede enviar un mensaje a todos los demás, si un proceso Pi envía una solicitud y no recibe respuesta en un intervalo de tiempo T supone que el coordinador ha fallado y trata de establecerse como nuevo coordinador, en ese caso envía un mensaje de elección a todos los procesos que tengan un número de prioridad mayor y espera nuevamente un tiempo de espera T. Si no recibe respuesta en ese tiempo supone que todos los demás nodos han fallado y se establece como coordinador, entonces envía un mensaje a todos los procesos indicando que es el coordinador. Si hubiera recibido algún mensaje de los nodos de más prioridad espera un tiempo T' la recepción de un mensaje en el cuál otro nodo indique que es coordinador, si no llegara en ese tiempo T' reinicia el algoritmo. En un momento determinado un proceso Pi puede recibir 2 mensajes o bien un mensaje en el que se especifica que Pj es el nuevo coordinador ( entonces la prioridad j > i ) o bien que el proceso responda a un inicio de elección ( j < i ). En ese caso Pi responde a Pj y además inicia el algoritmo de elección. Elección Elección Elección En este ejemplo se supone que falla P1 P1 P2 P3 P4 Respuesta Coordinador Coordinador Algoritmo de Chang y Roberts. Supone que los procesos no conocen la identidad de otros procesos a priori y a su vez los procesos están conectados a través de un anillo lógico, cada nodo únicamente conoce como comunicarse con su vecino del anillo. El nodo coordinador será el nodo con el identificador más alto y el algoritmo asume que todos los nodos 95

permanecen activos y alcanzables durante la operación. Inicialmente cada nodo se marca como no participante y cualquier proceso puede comenzar la elección del coordinador. Cuando un nodo detecta el fallo del coordinador se maca así mismo como participante, coloca su identificador en un mensaje y manda este mensaje a su vecino. Cuando un proceso recibe un mensaje de elección compara su identificador con el del mensaje. Si el identificador recibido es mayor que el suyo, entonces reenvía el mensaje al siguiente nodo del anillo, si es menor y el que la recibe es no participante, entonces sustituye el identificador recibido por el propio , se marca como participante y lo reenvía. Si previamente ya estaba como participante entonces no hace nada. Si el mensaje recibido contiene su identificador entonces se convierte en coordinador, se marca como no participante y envía un mensaje al vecino avisando que es el nuevo coordinador, cuando los demás procesos reciban el mensaje se marcan como no participantes y lo reenvían. Sentido Como el identificador es mayor que 2 se marca como participante y reenvía se reenvía sucesivamente Falla Envía Detecta el fallo y se pone como participante P y envía la marca de tiempo 2 . Si detectan 2 procesos el fallo envía su identificador cada uno y se marcan como participante y cuando llega a ellos el identificador lo califican y si es menor que el suyo quitan el suyo y envían ese mensaje hasta que llegue alguno de los que localizó el fallo su identificador, y se marque como coordinador. Algoritmo de REGENERACIÓN DE UN TESTIGO PERDIDO. El que inventó este algoritmo se llama MISRA , este algoritmo también se llama algoritmo del PING PONG. No requiere conocer las identidades de los procesos ni tampoco conocer los retardes de comunicación, supone que todos los nodos del sistema forman un anillo lógico, utiliza 2 testigos circulando de forma independiente, de forma que cada uno de ellos puede detectar la ausencia del otro , esto se detecta si un nodo ve el mismo testigo 2 veces in haber visto el otro. Una ver detectada la perdida se genera el que falta. Nping − pong =0 Tenemos para identificarlos 1 Ping, y − 1 Pong. Si el ultimo recibido es Ping y a continuación llega Pong 1 + (− 1) = 0 es correcto pero si recibimos otra vez Ping, 1 + 1 = 2 ha pasado dos veces Ping antes de que pase una vez Pong por lo que diremos que el testigo Pong se ha perdido y lo regeneramos.

96

Este paso de testigo no Afecta a lo de la exclusión mutua. Tenemos que poner la orden que solo puede acceder a su sección crítica aquel que tenga el testigo Ping o aquel que tenga el testigo pong. Pero no pueden acceder los 2. CONSECUCIÓN DE ACUERDOS. • Problema de los Generales Bizantinos. A la hora de comunicar diferentes nodos entre sí a través de mensajes hay que asegurar que el mensaje es recibido y que es recibido de forma correcta. Existen pro tanto 2 tipos de problemas: • Consiste en la perdida de mensajes. Puede resolverse mediante envío de mensajes de confirmación que indiquen que se ha recibido el mensaje. Se establecen periodos de tiempo, dentro de los cuales debemos recibir la confirmación de que el mensaje enviado ha sido recibido. Si transcurrido ese periodo no hemos recibido dicha confirmación entonces suponemos que el mensaje original no fue recibido y lo enviamos de nuevo. AB • El problema de los mensajes erróneos. Lo primero un nodo envía un mensaje V, luego los nodos que reciben el mensaje lo reenvían a los otros nodos que no son ellos ni al nodo que se lo envió por primera vez así se comprueba si el mensaje es correcto. A Vv BvC V Si M es el número de nodos que fallan entonces el número total de nodos del sistema debe ser al menos mayor o igual a 3m + 1 pro que así podremos utilizar una función mayoría. v P0 v v P1 P2 P3 V v X vdef v v P2 P3 P1 P3 P1 P2 Suponemos que P2 falla, envía x a P1 y P3 no recibe nada por lo que asume un valor por defecto P3 que es vdef . Los mensajes que han recibido son: P0 P2 P3 97

P1 ( v, x , v ) selecciona a v ya que es mayoría. P0 P1 P3 P1 ( v, v , v ) selecciona a v ya que es mayoría P0 P1 P2 P1 ( v, x , vdef) selecciona a v ya que es mayoría M va a valer uno ya que solo hay un nodo que falla. M = 1. Pues la fórmula nos da entonces: 3M + 1 = 4 se cumple este acuerdo ya que tenemos 4 nodos. RPC ( Remote Procedure Call ) Llamadas a procedimientos remotos. Método alternativo al paso de mensajes y permite que programas de máquinas diferentes interactúen a través de llamadas a estos procedimientos. Cuando se invoca un procedimiento el entorno que lo invoca queda suspendido y se transfieren los parámetros al nodo donde se ejecuta el procedimiento, cuando este finaliza su ejecución se le devuelve el resultado al nodo invocador y este continua su ejecución. SEGURIDAD Y PROTECCIÓN ( lo vemos en fotocopias). Día 3 − 5 − 00 WINDOWS NT Multiusuario, multiprocesador, es ampliable, escalable. Es capaz de trabajar con varios procesadores ( multiprocesador) la asignación a los procesadores es estática. CONCEPTOS. Dominio. La unidad administrativa básica del Sistema Operativo. Grupo de ordenadores que comparten una base de datos y tienen una política de seguridad común. La base de datos que comparte es la que contiene las cuentas de usuario. PDC ( controlador de Dominio Primario) Solo hay uno: Es el ordenador más importante del dominio y es el que contiene la copia maestra de la Base de Datos que contiene información sobre los grupos y usuarios del dominio es el que impone las políticas de seguridad para el dominio. Registra todos los cambios que se realizan en la Base de Datos y es el único que recibe estos cambios. BDC hay varios controladores de dominio secundario o BACKUP: Contienen una copia de la Base de Datos de las cuentas de usuario, pueden validar a los usuarios, cuando inician una sesión en el sistema y autorizar el acceso a los recursos. Si un PDC falla entonces un BDC promociona y pasa a actuar de PDC.

98

Servidores independientes: no contienen copias de las Bases de Datos de los usuarios por lo que no participan en la autentificación de usuarios. Normalmente se destinan a aplicaciones pesadas en las que requieren tiempos de respuesta pequeños. Para que los dominios puedan trabajar entre ellos es necesario que halla relaciones de confianza. Puede ser en ambos sentidos la relación. Cuando establezco una relación de confianza unidireccional hay un dominio que confía y otro en el que se confía. El que confía, confía en que el otro autentifique al usuario apropiadamente. En las relaciones de confianza bidireccional un usuario que se conecte con éxito a uno de los dominios será considerado auténtico por el otro dominio, tendrá acceso a los recursos de ambos dominios hasta el punto concedido por el administrador. Una relación bidireccional necesita 2 unidireccionales. Es necesario que el usuario tenga cuenta en ambos dominios. Según esto podemos tener varios modelos de dominio: • Modelo de Dominio Único: Solo hay un único Dominio y a él pertenecen todos los servidores y todas las cuentas de usuario. No hay relaciones de confianza. Nota: Los grupos Globales y locales son lo mismo. • Modelo de dominio Maestro único: Consiste en designar un único dominio donde se administran todas las cuentas de usuario y grupos globales, el resto de dominios confía en el maestro y tiene definidos grupos locales, la función principal del dominio maestro es ser el núcleo de la administración central de cuentas. • Modelo de múltiples dominios maestros: hay un pequeño número de dominios maestros, cada uno de los cuales confía en todos los otros dominios maestros. Las cuentas de usuario están localizadas en los dominios maestros de forma que cada cuenta solo está en un dominio maestro. Cada dominio secundario confía en todos los dominios maestros y los dominios secundarios pueden establecer relaciones de confianza entre sí aunque no es necesario. • Modelo de múltiples dominios maestros con confianza total: Cada uno de los dominios confía en los demás y una cuenta de usuario se crea en el dominio en el que el usuario comienza la sesión por defecto. Es necesario establecer relaciones de confianza bidireccional con todos los dominios. Promoción de controladores: Si falla el controlador primario cogemos el controlador de dominio secundario (BDC) y le promocionamos a controlador primario, y puede hacer las funciones que hacía antes ese servidor. CUENTAS DE USUARIO. • Usuarios Globales: Las cuentas son creadas en un servidor y se pueden utilizar tanto en el dominio en el que han sido creadas como en los dominios que confían en ese dominio. • Usuarios Locales: Solamente pueden ser utilizados en el dominio donde se crearon, pueden ser añadidos a grupos locales y a grupos globales. • Grupos Globales: Residen en un dominio pero mantienen sus permisos a lo largo de los dominios que confíen en ese domino . Solo pueden tener cuentas de usuario y no de grupo. • Grupos Locales: Existe y mantiene sus permisos solo dentro del dominio donde fueron creados. Pueden contener usuarios y grupos globales pero no locales. Dominio A Dominio B Pueden 99

estar en los dos dominios Un grupo global no puede tener otro grupo global. Cuentas de Usuario Predefinidas. • Cuenta de Administrador. Permite la administración del servidor en el cuál ha sido creada la cuenta y no se puede borrar, ni deshabilitar, ni bloquear. El administrador es miembro de los siguientes grupos. • Grupo Local de Administradores. • Grupo Global de administradores de dominio • Grupo de usuarios del dominio. • Cuenta de Invitado Normalmente desactivada y que se utiliza para aquellos usuarios que no tienen una cuenta en el equipo o pertenecen a un dominio en el que no se confía. Cuentas de Grupo Predefinidas. • Cuentas Globales. • Administradores del dominio: Tienen permiso en el dominio inicial del usuario, en todas las administraciones de trabajo de dominio inicial y en los dominios en que se confían. • Usuarios del dominio. • Grupos Locales: • Grupo de administradores: Se crea en servidores y en estaciones de trabajo • Operadores de cuenta: Operaciones con usuarios y grupos, salvo las relacionadas con el grupo de administradores. • Operadores de copia de seguridad • Operadores impresión. • Operadores Servidores • Operadores Duplicadores • Usuarios avanzados: se da en estaciones con work station o en servidores que no sean controladores de dominio. • Usuarios • Invitados. Existe una herramienta que es el administrador de usuarios que permite realizar las siguientes tareas. • Crear, cambiar y eliminar cuentas de usuario en un dominio. • Crear un perfil de usuario • Asignar archivos de ordenes de inicio de sesión a las cuentas de usuario. • Crear directorios particulares para los usuarios. • Estableces reglas de contraseña a nivel de dominio.

100

TIPOS DE PERFILES EN WINDOWS NT. • Personal Local: Este perfil está disponible solo en la maquina de usuario. • Perfil personal de usuario móvil: En este caso se almacena en un servidor y esta disponible para el usuario en cualquier máquina Windows Nt de la red. Los ajustes son establecidos pro el usuario sin ningún tipo de restricción impuesta pro el administrador. • Obligatorio de usuario móvil. En este caso el perfil se almacena en un servidor y está disponible para el usuario desde cualquier máquina de Windows NT. Algunos o todos los ajustes están determinados por el administrador y no les puede cambiar el usuario. Directorio Activo: Servicio que proporciona Windows 2000 Server que almacena información acerca de objetos de la red y facilita la búsqueda y utilización de esa información pro parte de usuarios y administradores. El servicio de directorios utiliza un almacén de datos que están estructurados como una base jerárquica y contiene la información de ellos. El echo de que esté de forma jerárquica permite establecer diferentes contextos a los cuales se aplicará las directivas. Las directivas : tiene como finalidad aplicar un conjunto de reglas sobre un grupo concreto de elementos. El directorio Activo se almacena en un fichero llamado NTDS. Dit. Este fichero contiene 3 tipos de datos: • Datos del dominio: Información sobre los objetos que hay en el dominio • Datos de configuración: Topología del directorio activo. • Datos del esquema: Son metadatos, Datos que explican lo que son otros datos. El control de acceso se lleva a cabo mediante los controladores de dominio y se puede realizar para cada objeto del directorio y también para cada una de las propiedades del objeto. Directivas de Grupo: • Permiten determinar el acceso a objetos y recursos del dominio. • Que recursos del dominio están disponibles para los usuarios. • Como se pueden utilizar los recursos del dominio. Dentro de cada dominio los usuarios se van a identificar a través de un nombre de usuario y el nombre de dominio. Usuario @ Dominio Eui.upsa.es Dominio \ usuario Eui.upsa.es \ pepe Bosque Conjunto de uno o varios dominios que comparten un esquema , configuración y catálogos comunes. Entre los elementos existe relaciones de confianza bidireccional. Microsoft. Com Dominio 101

Secundario. Microsoft.com Subdominio Terciario.secundario.Microsoft.com Subdominio Un árbol de dominios es un conjunto de dominios que tienen nombres de dominios contiguos. Dentro de un domino existe replicación de información entre los diferentes controladores del dominio. Controladores maestros de operaciones: Tienen asignados funciones que no pueden ocurrir en diferentes lugares al mismo tiempo. El controlador maestro de operaciones no tiene que ser continuamente el mismo ordenador. 1.1 Nota: Nosotros teníamos antes un proceso con un solo hilo ahora tenemos un proceso con varios hilos. Recoger Guardar Cálculos Imprimir Si Sj Sk S1 S3 S2 S1 S4 S2 S3 S6 S5 S1 S3 102

S2 S4 S6 S5 S7 S7 S5 S6 S4 S2 S3 S1 S6 S3 S4 S1 S7 J2 S5 S2 J3 J1 S4 S2 S3 S1

103

S7 S5 S6 R1 S3 S4 S1 S2 Sa Sb S8 S9 Sd Sc G1 R2 I1 C1 R3 C2 G2 I2 O M H G

104

K I B J F D C E A L N Sn S0 S2 P1 P8 S1 P2 P3 Sn+1 P9 P7 P4 P5 P6 F

105

G C D E A I H B Si quiero por ejemplo la zona gris que se ejecute en el programa tengo que hacerlo con un Begin y un End . Es como si dentro de uno principal nos encontramos un subprograma. Sc Sd S9 S8 Sb Sa S2 S7 S5 S6 S3 S4 S1 S1 S2 Sn+1 Sn 106

S0 S2 S1 S2 S1 S9 S8 S7 S5 S6 S3 S4 S2 S1 S8 S7 S6 S4 S5 S3 S9 NOTA : no puedo hacer IF S = 0. Lo que sea P1 P4 P3 P2

107

P7 P6 P5 P5 P6 P7 P2 P3 P4 P1 NOTA : Los if pueden ir anidados. LUNES MARTES MIERCOLES Las condiciones se agrupan con IF anidadas o con paréntesis, pero antes del paréntesis ponemos la barra invertida. Test \ ( a o b \) c 100 100 Peladora Cortadora Marcadora x y NOTA : Esto sirve para solucionar problemas de exclusión mutua y de sincronización de procesos. Deposito A Deposito 108

B Deposito B' Deposito A' P principal Crear Buzón C Signal ( señal A ) Signal ( señal B) Parbegin Máquina A Máquina B Máquina C Parend Recurso R1 P1 P2 Recurso R2 R1 Recurso P2 P1 Recurso R2

109

R3 Recurso P3 P1 Recurso R1 P2 Recurso R2 NOTA: 1 instancia y un ciclo implica interbloqueo n instancias y un nodo implica condición necesaria para interbloqueo n instancias 1 ciclo no implica interbloqueo. R1 Recurso R1 P3 P2 P1 R2 Recurso P4 R2 A B A

110

B R2 R1 R1 R1 A B R2 R1 A B R2 1 1 2 4 5 4 2 5 5 3 2 5 1 2

111

2 4 3011 0100 1110 1101 0000 1100 0112 3100 0010 2110 1100 0102 3100 0010 2110 3011 0110 1110 1101 0000 1100 0102 3100 0010

112

2100 3011 0110 1110 1101 0010 335 111 224 123 430 121 201 012 335 111 124 123 430 121 301 012 P1 P1 O O

113

O •1 01 •1 10 P1 P3 P4 0100 0110 0100 0001 1000 0001 1000 0010 P2 P4 P1 P3 P5 10000 01111 11001 01000 00000

114

01000 10000 00010 00001 00100 Procesador Memoria Procesador Memoria Procesador Memoria Procesador Memoria A B C B A Computo Solicitud de Exclu. Mutua Espera S.C Contestar a los mensajes diferidos 2

115

2B 3C 4D 5E 1A P1 P5 P3 P2 P4 P3 P2 P4 P2 P3 P5 P1 P2 P1 P3 P1 P2 P1 P3 B D

116

C A Usuario Local Juan Grupo Local Informática Usuario Local Pepe Usuario Global Juan Grupo Local Teología Grupo Global Informática

117