apuntes

[roikansuirius-blog]

PCD: Sesion 4

MONITORES EN JAVA

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

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

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

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

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

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

while(condicion)

try wait()

catch InterruptedException e

Codigo del método

notify();

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

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

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

[roikansuirius-blog]

MONITORES CON REENTRANTLOCK

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

cerrojo.lock()

try{

while(condition) x.await()

---OPERACIONES---

}finally{

cerrojo.unlock()}

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

private Condition condicion = cerrojo.newCondition();

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

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

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

[roikansuirius-blog]

PCD: Sesion 4

MONITORES EN JAVA

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

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

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

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

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

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

while(condicion)

try wait()

catch InterruptedException e

Codigo del método

notify();

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

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

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

[roikansuirius-blog]

PCD: Sesion Prácticas 1

HILOS EN JAVA

Ejecutar un programa en Java significa que hay un hilo de ejecución que se encarga de todo el main (hilo principal). Desde este hilo se pueden crear más que se ejeutaran simultaneamente. La creación de hilos puede ser mediante dos formas:

Heredando la clase Thread.

Implementando la interfaz Runnable.

Aunque en apariencia no hay ninguna diferencia en cuanto a funcionalidad, la realidad es que la API de Java favorece mucho mas a la interfaz Runnable que a la clase Thread. Pero salvo que se diga lo contrario, lo mas simple es hacerlo por la clase Thread. En cualquier caso, herede Thread o implemente Runnable todos deben de tener una funcion llamada ‘public void run()’ que es la que se encarga de lo que ejecuta el hilo una vez se diga 'nombrehilo.start()’.

HEREDANDO LA CLASE THREAD Y REDEFINIENDO RUN

Cuando queremos crear una clase cuyas instancias son hilos, debemos heredar de la clase Thread y redefinir el metodo run. Supongamos el siguiente ejemplo que lo unico que hace es mostrar por pantalla el identificador del hilo.

A la hora de ejecutarlo, en el siguiente programa o podremos predecir que hilo ejecutará que instruccion antes  si el hilo del Main terminara él primero, no se puede predecir la salida y de hecho a veces termina el hilo1, luego el main y luego el hilo2 o lo opuesto o cualquier combinacion posible:

Ejercicio 1: Escribir un programa que imprima “Hola Mundo” usando dos hilos que heredan de la clase Thread, uno imprime “Hola” y otro “mundo”. El hilo principal imprime en pantalla un mensaje cuando finaliza. Repetir la ejecución varias veces.

Si queremos introducir algo de aleatoriedad en la ejecución de los hilos tendremos que hacer uso del metodo (sleep) de la clase Thread, que habrá que acotar entre un try-catch. Por el resto el problema es igual que en el ejemplo. Se ejecutaran los hilos y el hilo principal y no sabremos cual termina antes por lo que tendremos casos en los que salga CUALQUIER COMBINACION POSIBLE.

IMPLEMENTANDO LA INTERFAZ RUNNABLE

A diferencia de una clase que hereda ’Thread’ implementar la interfaz Runnable significa que sus instancias (sus objetos) no son hilos, pero si queremos que se ejecuten en hilos creamos un objeto de la clase Thread y le pasamos como parametro el objeto donde queremos que comience su ejecución ese hilo. Veremos el mismo ejemplo pero con la interfaz Runnable.

La diferencia es que creamos un objeto Runnable y un nuevo hilo en base a este objeto.

Si quisieramos que un hilo espere a que finalice otro (es decir, vayan en orden y no se adelanten, aunque su orden de ejecución será un misterio, a veces el hilo1 se ejecutara antes que el hilo2 o viceversa), podemos usar el metodo join de la clase Thread que devuelve un excepción de tipo InterruptedException si falla. Podemos modificar el programa principal de la siguiente manera.

Ejercicio 2: Escribir un programa que imprima “Hola Mundo” usando dos hilos que heredan de la clase Thread, uno imprime “Hola” y otro “mundo”. El hilo principal imprime en pantalla un mensaje cuando finaliza. Repetir la ejecución varias veces.

VARIABLE VOLATILE

Supongamos que una clase de un hilo tiene una variable compartida que devolveremos al final de una serie de operaciones. El compilador realiza una serie de operaciones que pueden llevar a errores, asi que en este caso hay que declararlas como volatiles, siempre que un hilo modifique la variable, será actualizada en memoria principal y los demás podrán acceder al valor modificado.

Ejercicio 3: Escribir  un  programa  que  use  dos  hilos  para  incrementar  en  2000  unidades  una variable  compartida  inicializada  a  0.  Cada  hilo,  por  separado,  debe  incrementar  en 1000  unidades  dicha  variable.  Seguir  los  siguientes pasos  para  el  incremento  de  esa  variable compartida:

Obtener el valor de la variable compartida en una variable local. Dejar pasar un tiempo aleatorio (entre lectura y escritura de la variable). Incrementar en uno el valor de la variable local. Pasar el valor de la variable local a la compartida

Ejercicio 4: Implementar  un  programa  en  Java  para  simule  las  operaciones  de  dos  cajeros automáticos sobre una misma cuenta corriente. Inicialmente tendremos 1000€ en dicha cuenta corriente.  Uno de los cajeros tratará de hacer 100 operaciones consistentes en sacar  10€  de  la  cuenta.  El    otro  hará  lo  contrario, 100  operaciones  consistentes  en ingresar 10€ en la cuenta. Cada operación tendrá tres partes:  

Obtener el valor actual de la cuenta.   Dejar pasar un tiempo aleatorio correspondiente a la decisión del usuario del cajero. Actualizar el valor de la cuenta según la operación realizada.

Para una visión mas detalla el proyecto se encuentra en este link: http://www.mediafire.com/download/f013gfhg1iac15t/Programaci%C3%B3n_Concurrente_y_Distribuida.rar

[roikansuirius-blog]

PCD: Sesion Prácticas 1

HILOS EN JAVA

Ejecutar un programa en Java significa que hay un hilo de ejecución que se encarga de todo el main (hilo principal). Desde este hilo se pueden crear más que se ejeutaran simultaneamente. La creación de hilos puede ser mediante dos formas:

Heredando la clase Thread.

Implementando la interfaz Runnable.

Aunque en apariencia no hay ninguna diferencia en cuanto a funcionalidad, la realidad es que la API de Java favorece mucho mas a la interfaz Runnable que a la clase Thread. Pero salvo que se diga lo contrario, lo mas simple es hacerlo por la clase Thread. En cualquier caso, herede Thread o implemente Runnable todos deben de tener una funcion llamada 'public void run()' que es la que se encarga de lo que ejecuta el hilo una vez se diga 'nombrehilo.start()'.

HEREDANDO LA CLASE THREAD Y REDEFINIENDO RUN

Cuando queremos crear una clase cuyas instancias son hilos, debemos heredar de la clase Thread y redefinir el metodo run. Supongamos el siguiente ejemplo que lo unico que hace es mostrar por pantalla el identificador del hilo.

A la hora de ejecutarlo, en el siguiente programa o podremos predecir que hilo ejecutará que instruccion antes  si el hilo del Main terminara él primero, no se puede predecir la salida y de hecho a veces termina el hilo1, luego el main y luego el hilo2 o lo opuesto o cualquier combinacion posible:

Ejercicio 1: Escribir un programa que imprima "Hola Mundo" usando dos hilos que heredan de la clase Thread, uno imprime "Hola" y otro "mundo". El hilo principal imprime en pantalla un mensaje cuando finaliza. Repetir la ejecución varias veces.

Si queremos introducir algo de aleatoriedad en la ejecución de los hilos tendremos que hacer uso del metodo (sleep) de la clase Thread, que habrá que acotar entre un try-catch. Por el resto el problema es igual que en el ejemplo. Se ejecutaran los hilos y el hilo principal y no sabremos cual termina antes por lo que tendremos casos en los que salga CUALQUIER COMBINACION POSIBLE.

IMPLEMENTANDO LA INTERFAZ RUNNABLE

A diferencia de una clase que hereda 'Thread' implementar la interfaz Runnable significa que sus instancias (sus objetos) no son hilos, pero si queremos que se ejecuten en hilos creamos un objeto de la clase Thread y le pasamos como parametro el objeto donde queremos que comience su ejecución ese hilo. Veremos el mismo ejemplo pero con la interfaz Runnable.

La diferencia es que creamos un objeto Runnable y un nuevo hilo en base a este objeto.

Si quisieramos que un hilo espere a que finalice otro (es decir, vayan en orden y no se adelanten, aunque su orden de ejecución será un misterio, a veces el hilo1 se ejecutara antes que el hilo2 o viceversa), podemos usar el metodo join de la clase Thread que devuelve un excepción de tipo InterruptedException si falla. Podemos modificar el programa principal de la siguiente manera.

Ejercicio 2: Escribir un programa que imprima "Hola Mundo" usando dos hilos que heredan de la clase Thread, uno imprime "Hola" y otro "mundo". El hilo principal imprime en pantalla un mensaje cuando finaliza. Repetir la ejecución varias veces.

VARIABLE VOLATILE

Supongamos que una clase de un hilo tiene una variable compartida que devolveremos al final de una serie de operaciones. El compilador realiza una serie de operaciones que pueden llevar a errores, asi que en este caso hay que declararlas como volatiles, siempre que un hilo modifique la variable, será actualizada en memoria principal y los demás podrán acceder al valor modificado.

Ejercicio 3: Escribir  un  programa  que  use  dos  hilos  para  incrementar  en  2000  unidades  una variable  compartida  inicializada  a  0.  Cada  hilo,  por  separado,  debe  incrementar  en 1000  unidades  dicha  variable.  Seguir  los  siguientes pasos  para  el  incremento  de  esa  variable compartida:

Obtener el valor de la variable compartida en una variable local. Dejar pasar un tiempo aleatorio (entre lectura y escritura de la variable). Incrementar en uno el valor de la variable local. Pasar el valor de la variable local a la compartida

Ejercicio 4: Implementar  un  programa  en  Java  para  simule  las  operaciones  de  dos  cajeros automáticos sobre una misma cuenta corriente. Inicialmente tendremos 1000€ en dicha cuenta corriente.  Uno de los cajeros tratará de hacer 100 operaciones consistentes en sacar  10€  de  la  cuenta.  El    otro  hará  lo  contrario, 100  operaciones  consistentes  en ingresar 10€ en la cuenta. Cada operación tendrá tres partes:  

Obtener el valor actual de la cuenta.   Dejar pasar un tiempo aleatorio correspondiente a la decisión del usuario del cajero. Actualizar el valor de la cuenta según la operación realizada.

Para una visión mas detalla el proyecto se encuentra en este link: http://www.mediafire.com/download/f013gfhg1iac15t/Programaci%C3%B3n_Concurrente_y_Distribuida.rar

[roikansuirius-blog]

AEC: Reduccion en Memoria y Cache

CLASIFICACION DE FALLOS DE CACHÉ

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

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

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

AUMENTO DEL TAMAÑO DEL BLOQUE

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

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

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

AUMENTO DE LA ASOCIATIVIDAD

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

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

CACHÉ DE VICTIMAS

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

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

BUSQUEDA ANTICIPADA POR HARDAWARE

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

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

Prebusqueda con:

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

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

BUSQUEDA ANTICIPADA POR COMPILADOR

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

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

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

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

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

OPTIMIZACION DEL COMPILADOR

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

Combinacion de arrays (mergin arrays).

Intercambio de iteraciones (loop exchange)

Union de bucles (loop fusion)

Blocking

MERGIN ARRAYS

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

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

LOOP EXCHANGE

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

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

LOOP FUSION

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

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

BLOCKING

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

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

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

REDUCCION DE LA PENALIZACION POR FALLO DE CACHÉ

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

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

Caches multinivel

Buffer de escritura

Cachés no bloqueantes

CACHES MULTINIVEL

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

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

Esto compica la formula:

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

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

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

BUFFER DE ESCRITURA

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

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

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

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

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

CACHES NO BLOQUEANTES

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

REDUCCION DEL TIEMPO DE SERVICIO EN CASO DE ACIERTO

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

[roikansuirius-blog]

AEC: Reduccion en Memoria y Cache

CLASIFICACION DE FALLOS DE CACHÉ

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

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

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

AUMENTO DEL TAMAÑO DEL BLOQUE

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

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

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

AUMENTO DE LA ASOCIATIVIDAD

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

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

CACHÉ DE VICTIMAS

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

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

BUSQUEDA ANTICIPADA POR HARDAWARE

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

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

Prebusqueda con:

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

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

BUSQUEDA ANTICIPADA POR COMPILADOR

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

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

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

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

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

OPTIMIZACION DEL COMPILADOR

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

Combinacion de arrays (mergin arrays).

Intercambio de iteraciones (loop exchange)

Union de bucles (loop fusion)

Blocking

MERGIN ARRAYS

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

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

LOOP EXCHANGE

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

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

LOOP FUSION

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

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

BLOCKING

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

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

---------------------------------------------------

REDUCCION DE LA PENALIZACION POR FALLO DE CACHÉ

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

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

Caches multinivel

Buffer de escritura

Cachés no bloqueantes

CACHES MULTINIVEL

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

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

Esto compica la formula:

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

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

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

BUFFER DE ESCRITURA

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

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

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

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

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

CACHES NO BLOQUEANTES

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

REDUCCION DEL TIEMPO DE SERVICIO EN CASO DE ACIERTO

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

[binary-risen-blog]

ETC: Memoria Virtual

                                             MEMORIA VIRTUAL

La memoria principal puede actuar como una caché para el almacenamiento secundario, esto permite:

Eliminar el inconveniente de tener un espacio de memoria principal pequeño y limitado:

Sin el sistema de memoria virtual los programadores dividian los programas en partes mutuamente exclusivas cargadas en memoria o salvadas a disco bajo.

Con el sistema de memoria virtual, un programa manejará un espacio de direcciones de memoria virtual como si se tratara de una gran memoria principal, solo una de ella estará en la memoria principal (memoria física).

Permite la compartición eficiente  sin peligros de memoria entre múltiples programas:

Varios programas se están ejecutando al mismo tiempo.

Solo una parte de la memoria de cada programa se usa activamente en un instante de tiempo.

La memoria principal solo contiene las partes activas de los programas de ejecución.

Se debe asegurar que un programa solo pueda leer y escribir las partes de memorias que tiene asignadas.

                                       CONCEPTOS GENERALES

Páginas: Bloques de memoria virtual.

Fallo de página: Fallo de memoria virtual.

Traduccion de direcciones: La CPU genera direcciones virtuales, la MMU (Memory Managment Unit) traduce las direcciones virtuales a físicas y a ememoria se accede con direcciones físicas.

Es posible que una pagina virtual no esté en la memoria principal y que solo esté en disco. Podemos ver un ejemplo en la siguiente imagen:

Desplazamiento de pagina 12 bits -> Tamaño de la página 2^12 bytes = 4KiB.

Numero de pagina física 18 bits -> 2^18 páginas físicas.

Memoria principal de 2^30 bytes = 1GiB

Memoria virtual es de 2^32 bytes = 4GiB

                                        CONSIDERACIONES

Existe un gran coste de los fallos de página debido a la gran diferencia de velocidades entre la memoria principal y la secundaria. Se utilizan páginas grandes para amortizar el tiempo de acceso.

Las páginas tienen un sistema totalmente asociativo para reducir al maximo la tasa de fallos.

Los fallos de pagina pueden gestionarse con software porque al usar direcciones virtuales se pueden usar algoritmos inteligentes, que reducen la tasa de fallos y es mucho mas rapido que hacerlo via hardware.

Ademas consta con una politica de post-escritura pues es mas rapida que la escritura directa.

                                        TABLA DE PÁGINAS

Se encuentran cargadas en memoria, y se indexan con el número de pagina virtual, esta tabla contiene el correspondiente número de página física.

Cada programa tiene su propia tabla de páginas.

Existe un registro de la tabla de páginas que apunta al inicio de la tabla de paginas del programa que esté en funcionamiento.

Un fallo de pagina provoca una excepción por fallo de pagina, el control pasa al S.O. que ha de encontrar la pagina solicitada en la memoria secundaria y decidir donde colocarla en la memoria principal.

En general, si en la tabla de paginas, la direccion de la pagina que buscamos tiene un bit de validez a 1 se puede acceder con ella a memoria fisica, en caso contrario como no está en la tabla hay que ir a buscarla al disco.

                      TRATAMIENTO DE LOS FALLOS DE PÁGINA

Los fallos de página se solucionan con la politica de reemplazo LRU (dado que es muy caro se utiliza un Pseudo LRU con un bit de uso).

Este bit se activa cuando se accede a una pagina.

Tras un tiempo periodico el S0 pone el bit a 0.

El sistema operativo puede seleccionar una pagina entre las que tengan el bit de uso apagado.

Ademas consta con una politica de escritura (post-escritura):

Las escrituras individuales se realizan en la página que hay en la memoria principal y se copia la página a memoria  secundaria cuando esta se reemplaza asi que se utiliza un bit de modificacion para conocer si una pagina ha sido modificada desde que se leyó de memoria secundaria.

                             TLB (Translation-Lookaside Buffer)

Cada lectua/escritura a memoria provoca realmente dos accesos a memoria: Acceso a la tabla de páginas para traducir la direccion virtual a dirección física. Con la dirección física obtenida, acceder físicamente a la palabra solicitada.

Para solucionarlo se utiliza la localidad de las referencias a la tabla de páginas. Cuando un programa accede a una palabra que pertenece a una página virtual X, es muy probable que se acceda a palabras de direcciones cercanas y que, por tanto, pertenezcan a la misma página X.

El TLB es una caché especial que guarda las traducciones (número.página.virtual -> número.página.física) mas frecuentemente usadas.

El TLB trata la tabla de paginas como una mini-memoria principal. El indice de la tabla de páginas (numero de pagina virtual) es como la direccion del bloque en el caso de las cachés, y el contenido de la posicion de la tabla (numero de pagina fisica y bits de control) sería el contenido del bloque.

Asi, el indice de la tabla de páginas (numero de pagina virtual) será usado para acceder al TLB:

Los bits menos significativos serán el índice.

El resto, será la etiqueta.

Asi pues si en la tabla anterior colocaramos un TLB entre la direccion virtual y la direccion física tendriamos lo siguiente, donde si la busqueda en el TLB no resulta entonces se ha de ir a la tabla de páginas a buscarla manualmente y si en la tabla de paginas no funciona, habrá que ir al disco duro.

En cada referencia a memoria:

La MMU descompone la direccion virtual en Numero.Pagina.Virtual y Desplazamiento.

Se busca el numero de página virtual en el TLB, si acierta saltamos al paso 6.

Como no está la pagina en la TLB se va a la tabla de páginas, si acierta saltamos al paso 5.

Como no está en la tabla de paginas se produce un fallo de pagina y funciona el S.O. que coloca la pagina solicitada en la memoria principal y actualiza la entrada de la tabla de paginas (el nº de pagina fisica y el bit de validez).

El contenido de la entrada de la tabla de páginas va al TLB, se actualiza entonces la etiqueta en el TLB.

Usando el TLB (numero.pagina.virtual->numero.pagina.fisica) y se actualizan los bits de control de esa pagina.

Lo mas normal es que la TLB tenga fallos mas frencuentes que la tabla de paginas por tener menos espacio para almacenar las páginas. No obstante sigue siendo un numero bajo, por lo que el TLB suele llevar una estrategia de post-escritura lo que conlleva:

La actualizacion de los bits de control se realiza solamente en el TLB, cuando una entrada en el TLB va a ser sustituida su informacion se copia en la tabla de paginas.

                          PROTECCION DE LA MEMORIA VIRTUAL

Para proteger que dos programas no accedan a zonas de memoria que no deben es necesario que, cuando el sistema operativo cambia el proceso de ejecución P1 al proceso P2:

Se cambia el valor del registro que apunt al inicio de la tabla de páginas del nuevo proceso.

Se vacía el TLB de las entradas que pertenecen a P1.

El hardware ha de poseer:

Dos modos de funcionamiento en la CPU que indiquen si un proceso es de usuario (con permisos de lectura y escritura limitado) o de sistema operativo.

Impedir que la informacion que se encuentra en la CPU pueda ser modificada por un proceso de usuario, esto incluye el bit que indica si el proceso es de usuario/S.O, el registro que apunta al inicio de la tabla de páginas, el contenido de esa tabla de páginas y el contenido del TLB.

Disponer de mecanismos que permitan a la CPU pasar del modo usuario a modo supervisor (syscall) y viceversa (retorno de excepcion).

                   SUCESOS EN TLB, MEMORIA VIRTUAL Y CACHÉ

[binary-risen-blog]

ETC: Memoria Virtual

                                             MEMORIA VIRTUAL

La memoria principal puede actuar como una caché para el almacenamiento secundario, esto permite:

Eliminar el inconveniente de tener un espacio de memoria principal pequeño y limitado:

Sin el sistema de memoria virtual los programadores dividian los programas en partes mutuamente exclusivas cargadas en memoria o salvadas a disco bajo.

Con el sistema de memoria virtual, un programa manejará un espacio de direcciones de memoria virtual como si se tratara de una gran memoria principal, solo una de ella estará en la memoria principal (memoria física).

Permite la compartición eficiente  sin peligros de memoria entre múltiples programas:

Varios programas se están ejecutando al mismo tiempo.

Solo una parte de la memoria de cada programa se usa activamente en un instante de tiempo.

La memoria principal solo contiene las partes activas de los programas de ejecución.

Se debe asegurar que un programa solo pueda leer y escribir las partes de memorias que tiene asignadas.

                                       CONCEPTOS GENERALES

Páginas: Bloques de memoria virtual.

Fallo de página: Fallo de memoria virtual.

Traduccion de direcciones: La CPU genera direcciones virtuales, la MMU (Memory Managment Unit) traduce las direcciones virtuales a físicas y a ememoria se accede con direcciones físicas.

Es posible que una pagina virtual no esté en la memoria principal y que solo esté en disco. Podemos ver un ejemplo en la siguiente imagen:

Desplazamiento de pagina 12 bits -> Tamaño de la página 2^12 bytes = 4KiB.

Numero de pagina física 18 bits -> 2^18 páginas físicas.

Memoria principal de 2^30 bytes = 1GiB

Memoria virtual es de 2^32 bytes = 4GiB

                                        CONSIDERACIONES

Existe un gran coste de los fallos de página debido a la gran diferencia de velocidades entre la memoria principal y la secundaria. Se utilizan páginas grandes para amortizar el tiempo de acceso.

Las páginas tienen un sistema totalmente asociativo para reducir al maximo la tasa de fallos.

Los fallos de pagina pueden gestionarse con software porque al usar direcciones virtuales se pueden usar algoritmos inteligentes, que reducen la tasa de fallos y es mucho mas rapido que hacerlo via hardware.

Ademas consta con una politica de post-escritura pues es mas rapida que la escritura directa.

                                        TABLA DE PÁGINAS

Se encuentran cargadas en memoria, y se indexan con el número de pagina virtual, esta tabla contiene el correspondiente número de página física.

Cada programa tiene su propia tabla de páginas.

Existe un registro de la tabla de páginas que apunta al inicio de la tabla de paginas del programa que esté en funcionamiento.

Un fallo de pagina provoca una excepción por fallo de pagina, el control pasa al S.O. que ha de encontrar la pagina solicitada en la memoria secundaria y decidir donde colocarla en la memoria principal.

En general, si en la tabla de paginas, la direccion de la pagina que buscamos tiene un bit de validez a 1 se puede acceder con ella a memoria fisica, en caso contrario como no está en la tabla hay que ir a buscarla al disco.

                      TRATAMIENTO DE LOS FALLOS DE PÁGINA

Los fallos de página se solucionan con la politica de reemplazo LRU (dado que es muy caro se utiliza un Pseudo LRU con un bit de uso).

Este bit se activa cuando se accede a una pagina.

Tras un tiempo periodico el S0 pone el bit a 0.

El sistema operativo puede seleccionar una pagina entre las que tengan el bit de uso apagado.

Ademas consta con una politica de escritura (post-escritura):

Las escrituras individuales se realizan en la página que hay en la memoria principal y se copia la página a memoria  secundaria cuando esta se reemplaza asi que se utiliza un bit de modificacion para conocer si una pagina ha sido modificada desde que se leyó de memoria secundaria.

                             TLB (Translation-Lookaside Buffer)

Cada lectua/escritura a memoria provoca realmente dos accesos a memoria: Acceso a la tabla de páginas para traducir la direccion virtual a dirección física. Con la dirección física obtenida, acceder físicamente a la palabra solicitada.

Para solucionarlo se utiliza la localidad de las referencias a la tabla de páginas. Cuando un programa accede a una palabra que pertenece a una página virtual X, es muy probable que se acceda a palabras de direcciones cercanas y que, por tanto, pertenezcan a la misma página X.

El TLB es una caché especial que guarda las traducciones (número.página.virtual -> número.página.física) mas frecuentemente usadas.

El TLB trata la tabla de paginas como una mini-memoria principal. El indice de la tabla de páginas (numero de pagina virtual) es como la direccion del bloque en el caso de las cachés, y el contenido de la posicion de la tabla (numero de pagina fisica y bits de control) sería el contenido del bloque.

Asi, el indice de la tabla de páginas (numero de pagina virtual) será usado para acceder al TLB:

Los bits menos significativos serán el índice.

El resto, será la etiqueta.

Asi pues si en la tabla anterior colocaramos un TLB entre la direccion virtual y la direccion física tendriamos lo siguiente, donde si la busqueda en el TLB no resulta entonces se ha de ir a la tabla de páginas a buscarla manualmente y si en la tabla de paginas no funciona, habrá que ir al disco duro.

En cada referencia a memoria:

La MMU descompone la direccion virtual en Numero.Pagina.Virtual y Desplazamiento.

Se busca el numero de página virtual en el TLB, si acierta saltamos al paso 6.

Como no está la pagina en la TLB se va a la tabla de páginas, si acierta saltamos al paso 5.

Como no está en la tabla de paginas se produce un fallo de pagina y funciona el S.O. que coloca la pagina solicitada en la memoria principal y actualiza la entrada de la tabla de paginas (el nº de pagina fisica y el bit de validez).

El contenido de la entrada de la tabla de páginas va al TLB, se actualiza entonces la etiqueta en el TLB.

Usando el TLB (numero.pagina.virtual->numero.pagina.fisica) y se actualizan los bits de control de esa pagina.

Lo mas normal es que la TLB tenga fallos mas frencuentes que la tabla de paginas por tener menos espacio para almacenar las páginas. No obstante sigue siendo un numero bajo, por lo que el TLB suele llevar una estrategia de post-escritura lo que conlleva:

La actualizacion de los bits de control se realiza solamente en el TLB, cuando una entrada en el TLB va a ser sustituida su informacion se copia en la tabla de paginas.

                          PROTECCION DE LA MEMORIA VIRTUAL

Para proteger que dos programas no accedan a zonas de memoria que no deben es necesario que, cuando el sistema operativo cambia el proceso de ejecución P1 al proceso P2:

Se cambia el valor del registro que apunt al inicio de la tabla de páginas del nuevo proceso.

Se vacía el TLB de las entradas que pertenecen a P1.

El hardware ha de poseer:

Dos modos de funcionamiento en la CPU que indiquen si un proceso es de usuario (con permisos de lectura y escritura limitado) o de sistema operativo.

Impedir que la informacion que se encuentra en la CPU pueda ser modificada por un proceso de usuario, esto incluye el bit que indica si el proceso es de usuario/S.O, el registro que apunta al inicio de la tabla de páginas, el contenido de esa tabla de páginas y el contenido del TLB.

Disponer de mecanismos que permitan a la CPU pasar del modo usuario a modo supervisor (syscall) y viceversa (retorno de excepcion).

                   SUCESOS EN TLB, MEMORIA VIRTUAL Y CACHÉ

[binary-risen-blog]

Memoria Caché

                                           LA MEMORIA CACHE

Debido a que los programadores quieren memorias rápidas y de gran tamaño de almacenamiento (y que actualmente no pueden conseguirse a un bajo coste) se crea la ilusión de una gran memoria rápida que actua segun diferentes jerarquías.

Cuanto mas rapida es una memoria menos capacidad de almacenamiento posee y viceversa. La memoria SRAM (Static RAM) tiene un tiempo de acceso menor que 3ns, la memoria DRAM (Dynamic RAM) tiene un tempo de acceso de 70ns, el disco duro tarda hasta 20 millones de ns.

                                       PRINCIPIO DE LOCALIDAD

Si la jerarquia de memoria funciona (o lo parece) a igual ritmo que la memoria del nivel mas alto es porque existe el principio de localidad. Los programas muchas veces pediran datos que o bien ya se han pedido antes o bien estan muy cerca de los que se han pedido.

El objetivo es detectar estas zonas de memoria (datos y código) con mas probabilidad de ser accedidas y llevarlas a la memoria más rapida (para que se ejecuten tan rapido como proporcional es su necesidad de uso).

Existen dos tipos de localidad:

Temporal: El dato que se necesita consultar será consultado mas tarde (o fue consultado anteriormente).

Espacial: El dato que he consultado está cerca de otros que consultaré en breve (o lo busco cerca del que ya consulté).

Asi pues el principio de localidad busca exprimir al máximo la localidad temporal y espacial de un programa, buscando coger los datos que mas se han solicitado y los mas cercanos a ellos.

                        CONCEPTOS DE LA JERARQUÍA DE NIVELES

Cuanto mas cercano sea un nivel al procesador, mas pequeño será en tamaño pero mas rápido será. Los datos solo se copian entre niveles adyacentes asi si hay que traer algo desde disco duro tardamos el tiempo de acceso de recorrer toda la cadena dos veces.

La unidad minima de informacion se conoce como bloque.

Se produce un acierto (hit) si el elemento que pide la CPU está en el nivel superior.

Se produce un fallo (miss) si el elemento que pide la CPU no está en el nivel superior. En tal caso se llama al nivel inferior para que lo recupere, si no lo tuviera se llamaría a su inferior…

La tasa de aciertos (hit-rate) es la fraccion de accesos a memoria encontrados en el nivel superior. La tasa de fallos será por tanto todos los accesos que fallaron al solicitar un dato (1-hit.rate).

El tiempo de acierto es el tiempo necesario para acceder al nivel superior de la memoria, incluyendo el tiempo para determinar si el acceso es un fallo o un acierto.

La penalizacion por fallo es el tiempo necesario para reemplazar un bloque del nivel superior por otro bloque del nivel inferior.

                                  VISION GENERAL DE LA CACHÉ

La caché fue el termino escogido para representar el nivel de la jerarquía de memoria entre la CPU y la memoria principal.

En general trabajaremos con 32 bits, no obstante seguiremos esta “creencia” salvo que se indique lo contrario en un ejercicio. Con 32 bits, nuestras direcciones de memoria son de 32 bits (logicamente) al mismo modo tenemos 2^32 direcciones que son 4GiB, donde en cada una de esas direcciones se graba 1 palabra (4bytes).

                         DIRECCIONES DE BYTES Y PALABRAS

Dir(palabra) = Dir(byte) DIV Tam(palabra)

Dir(palabra) = Dir(32) DIV Tam(4) -> Dir(Palabra) = 30 bits primeros.

Offset(palabra) = Dir(byte) MOD Tam(palabra)

Offset(palabra) = Dir(32) MOD Tam(4) = 2 bits ultimos.

La direccion de palabra se utiliza para localizar la palabra en la memoria, en cambio offset se utiliza para saber donde se localiza cada fragmento de la palabra. Es decir uno nos dice en que fila está y otro en que columna.

                      DIRECCIONES DE BYTES Y BLOQUES

Supongamos que tenemos un bloque de 8 bytes. Con 32 bits en MIPS.

Dir(bloque) = Dir(byte) DIV Tam(Bloque)

Dir(bloque) = Dir(32) DIV Tam(8) -> Dir(bloque) = 29 bits primeros

Offset(bloque) = Dir(byte) MOD Tam(Bloque)

Offset(bloque) = Dir(32) MOD Tam(8) = 3 ultimos bits.

La direccion de bloque se utiliza para localizar donde está el bloque de palabras, dentro de los cuales cada uno tendrá un dir-palabra y offset-palabra, en cambio el offset-bloque se utiliza para localizar donde está cada parte del bloque.

                                              TIPOS DE CACHE

La caché generalmente tiene dos caracteristicas, conjuntos y vias. Cada conjunto es el numero de “cajones” mientras que cada vía son los huecos dentro de ese cajon. Asi pues existen tres tipos de cachés:

Directa: Muchos conjuntos con solo 1 via, solo puede meterse un dato por conjunto.

Asociativa: Varios conjuntos con al menos 2 vias, pueden meterse mas de un dato por conjunto.

Totalmente asociativa: Un solo conjunto con muchas vías, pueden meterse tantos datos como vias.

Esto tiene sus ventajas, en una caché de correspondencia directa la tasa de acierto es baja pero es muy rapida. Si es totalmente asociativa es lenta pero es bastante precisa. Generalmente en los procesadores actuales las cachés de primer nivel tienen una asociatividad baja, mientras que cuanto mas bajan suelen tener hasta 16 o 32.

                                ESTRUCTURA DE LA CACHÉ

Aunque ya sabemos donde se guardan los bloques y donde se guardan las palabras en la memoria no sabemos como se organizan los conjuntos. Los conjuntos es donde almacenamos un bloque o donde los buscamos.

Conjunto = Dir(bloque) MOD Num(conjuntos)

Si queremos buscar un bloque en caché miramos en el conjunto y todas sus vías (o en la unica si es directa) para almacenar un bloque en caché habrá que calcular su conjunto y buscar alguna via libre o remplazarla si no la hay.

Ejemplo de caché de correspondencia directa con 8 entradas y una memoria principal de 32 bloques.

Conjunto = Dir(32) MOD Num(8) -> Conjunto = 3 ultimos bits. Conjunto = 00000000000000000000000000000-010 -> Conjunto = 010 Conjunto = 00000000000000011100000010001-010 -> Conjunto = 010

Para determinar la vía a la que corresponde un bloque utilizamos la etiqueta. Si el conjunto es la parte en comun de todas las direcciones de bloque, la etiqueta esl a unica parte que no tienen en comun (los otros 29 bits) en tal caso en nuestro ejemplo la etiqueta del segundo sería (00000000000000011100000010001).

Etiqueta = Dir(bloque) DIV Num(conjuntos)

Si alguna de las vias contiene un bloque valido hay un acierto, si no es un fallo. Para saber si se produce un fallo o no se añadirá un bit (V) de validez.

                        EJEMPLO DE ESTRUCTURA CON LA CACHÉ

Dirección  | Dir(byte)  | Conjunto(S) | Etiqueta(E) 0000100   | 00001         |    001              |      00 0100100   | 01001         |    001              |      01 1000100   | 10001         |    001              |      10

                              POLITICAS DE LA ESCRITURA

Generalmente para escribir en una caché hay dos politicas:

Write Through: Se sobreescribe sin importar los principios de localidad o temporalidad, es mucho mas tosco pero no requiere de una politica de sobreescritura (con un bit extra), se sustituye tanto la caché como la memoria principal.

Write Back: Las escrituras solo tienen lugar en la cache y solo cuando ese bloque tiene que ser desechado pues va a ser sustituido por otro se graba en memoria, asi solo hacemos 1 escritura en memoria. Esto requiere un bit de modificacion (M) que indica si ha de escribirse en la memoria tras sustituir el bloque en la caché.

                            POLITICA DE SOBRE-ESCRITURA

La caché ha fallado, asi que hay que traer desde memoria a la caché el bloque solicitado y colocarlo en su posicion.

Si fuera de correspondencia directa esa posición está ocupada por otro bloque y se sustiuye por el nuevo (a saco).

Si fuera asociativa, y el conjunto al que le corresponde está lleno se utiliza un algoritmo de sustitucion para decidir cual será machacado. Puede ser al azar o por LRU (least-recently-used), a través de un bit de uso (U) asi mismo esta es una pseudo-implementacion que es la mas comun.

Al final tenemos 3 bits extras (uso, modificacion y validez) que se añaden a la etiqueta y el dato en cuestion del conjunto.

                        EJEMPLOS CON CACHÉS: EJEMPLO 1.

Caché de correspondencia directa de 1024 entradas. Tamaño de bloque de 1 palabra, de 32 bits, escritura directa y 32 bits de direcciones.

Lo primero que tenemos que hacer es sacar los datos que nos da el propio enunciado:

Tamaño Caché = 1024 entradas * 32 bits = 32768 bits = 4096 bytes = 4KB.

Num.Conjuntos = 1024 (correspondencia directa).

Num vias = 1. 0 bits para vias.

Tenemos una caché que mide 1024 de largo con una sola via, tiene 1 bit de validez.

Nuestra direccion de Byte es de 32. Dado que los bloques son de 1 palabra, cada bloque tiene 4 bytes (32bits) asi que uso 2 como off-set (desplazamiento de byte), el resto (30bits) es la direccion de bloque.

Nuestra direccion de bloque es de 30. Dado que hay 1024 entradas necesito log2(1024) para redireccionarlo. 10 bits serán los que utilice para desplazamiento de bloque y el resto como etiqueta.

Conclusion, la etiqueta mide 20 bits, el off-set-bloque 10. La direccion de bloque 30 y los otros 2 bits conforman el off-set-byte. Al final nuestra caché tendra 1 bit de validez, 20 de etiqueta y los otros 32 bits de datos.

Al final tenemos:

Off-set-Byte = 2 nº de byte.

Dir.Bloque = 30 bits.

Off-set-Bloque(Indice) = 10 bits

Etiqueta = 20 bits

                                EJEMPLO CON CACHÉS: EJEMPLO 2

Caché de correspondencia directa de 64KiB, tamaño de bloque de 4 palabras de 32 bits. Direcciones de 32 bits y escritura directa.

Lo primero que tenemos que hacer es sacar los datos que nos da el propio enunciado. La unica diferencia con el enunciado anterior es que no sabemos los huecos y que las palabras tienen 4 zonas posibles en las que almacenarse en el mismo bloque.

Tamaño Caché = 64KiB.

Tamaño de Bloque = 4 palabras = 4 * 4bytes = 16 Bytes.

Numero de Entradas = 64*1024/16 = 4096 huecos.

Entonces nuestra caché mide 4096 de altura, tiene un bit de validez, una etiqueta (cuya longitud desconocemos). Y los datos que ocupan 4 bytes en cada uno de los 4 huecos.

Nuestra direccion de Byte es de 32, dado que tenemos 4 bloques y 4 bytes por palabras, necesitamos 4 bits (2 para el numero de bloque y 2 para los 4 bytes de cada palabra. Asi que nuestro off-set será de 4 y los otros 28 serán la direccion de bloque.

Nuestra direccion de bloque es de 28 bits, de los cuales utilizaremos log2(4096) para redireccionarlos, asi que 12 bits serán para el numero de la entrada y el resto (16) como etiqueta.

Al final tenemos:

Off-set-Byte = 4 | 2 nº de palabra y 2 nº de byte.

Dir.Bloque = 28 bits.

Off-set-Bloque(Indice) = 12 bits

Etiqueta = 16 bits

Tras mirar el indice (nº de entrada), si el bit de validez es 1 y coincide con la etiqueta (con un comparador entre lo que hay en la etiqueta y los n bits de la etiqueta del dato que entra) podemos saber si es un acierto o un fallo. Los 4 bits del desplazamiento 2 se utilizan para saber que palabra llamamos (de las cuatro que hay) y los ultimos dos para el byte dentro de esa palabra (de los cuatro que hay.

                           CACHES ASOCIATIVAS POR CONJUNTOS

Ya hemos visto como se organizan las direcciones de byte y de palabra dentro de las diferentes cachés, siempre dependientes del tamaño de cachés, el numero de vias y el numero de palabras.

EJERCICIO 1) Supongamos entonces que tenemos una tabla como la siguiente que corresponde a la evolución del contenido de una memoria caché de correspondencia directa de 4 posiciones:

RECORDATORIO: Posición Caché: Dir.Bloque MOD 4(nº de posiciones). Será acierto si consultamos el mismo dato que el almacenado en la posicion de la caché a la que corresponde. Si se escribe en otra posicion se mantiene lo que hubiera escrito antes, sino se sobreescribe.

Y nos dan en el orden estricto una serie de bloques cuya direccion son: 0,8,0,6,8 0000,1000,0000,0110,1000

0000:

Pos.Caché = 00

Fallo (primera consulta)

Pos(00) = 0; ponemos en memoria 0 M[0]

1000:

Pos.Caché = 00

Fallo (en memoria está el dato 0)

Pos(00) = 8; ponemos en memoria 8; M[8]

0000:

Pos.Caché = 00

Fallo (en memoria está el dato 0)

Pos(00) = 0; ponemos en memoria 0; M[0]

0110:

Pos.Caché = 10

Fallo (primera consulta)

Pos(10) = 6; ponemos en memoria 6; M[6]

1000:

Pos.Caché = 00

Fallo (en memoria estaba el dato 0)

Pos(00) = 8; ponemos en memoria 8; M[0]

Podemos ver que la caché de correspondencia directa tiene, en este caso un 0% de aciertos. Al final la tabla queda de la siguiente manera:

EJERCICIO 2) Supongamos la misma sucesión de datos en una caché asociativa de 2 conjuntos, con 2 bloques por conjunto (2 vias).

Para redireccionar 2 conjuntos solo necesitamos un bit, como podemos almacenar dos, si un dato va a un conjunto con un hueco libre, lo ocupa, si hay dos se sustituye uno ‘al azar’. El resto es la etiqueta.

0000:

Pos.Caché = 0

Fallo (primer acceso: 1ª pos)

Conjunto(0) = 0; ponemos en memoria 0; M[0]

1000:

Pos.Caché = 0

Fallo (primer acceso; 2ª pos)

Conjunto(0) = 8; ponemos en memoria 8; M[8]

0000:

Pos.Caché = 0

Acierto (M[0] está en el conjunto 0).

0110:

Pos.Caché = 0

Fallo (en memoria no está M[6] sustituyendo M[0])

Conjunto(0) = 6; pongo en memoria 6; M[6]

1000:

Pos.Caché = 0

Fallo (en memoria no está M[0])

Conjunto(0) = 0; pongo en memoria 0; M[0]

Como podemos ver, la cache asociativa de dos conjuntos y dos bloques tiene una tasa de aciertos del 20%.

EJERCICIO 3) Supongamos la misma sucesión de bloques en una caché totalmente asociativa. Como no tiene conjuntos (solo 1) toda la direccion de byte es etiqueta.

0000:

Fallo (primer acceso, 1ª pos)

Conjunto unico = 0; pongo en memoria 0; M[0]

1000:

Fallo (primer acceso, 2ª pos)

Conjunto unico = 8; pongo en memoria 8; M[8]

0000:

Acierto

0110:

Fallo (primer acceso, 3ª pos)

Conjunto único = 6; pongo en memoria 6; M[6]

1000:

Acierto

Como se puede apreciar esta cache totalmente asociativa tiene un 40% de tasa de aciertos.

CONCLUSION: Aunque los fallos en las cachés directas son mas frecuentes, son mas baratas de construir pero las asociativas, cuanto mas asociativas sean menos fallos tienden a tener pero consultar un dato es mucho mas costoso.

                                TAMAÑO UTIL DE UNA CACHÉ

Tamaño util caché = nºconjuntos x bloques.conjunto (asociatividad) x tamaño.bloque (bits).

Tamaño bloque = palabras.bloque x bits.palabra.

Tamaño total cache = nºconjuntos x bloques.conjunto x (nºbits.control + tamaño.etiqueta + tamaño.bloque).

Tamaño etiqueta = tamaño.direccion - nºbits.indice - nºbits.desplazamiento.palabra - nºbits.desplazamiento.byte.

EJEMPLO: Calcule el tamaño total de una caché de correspondencia directaque tiene las siguientes caracteristicas:

2 bits de desplazamiento de yte.

0 bits de desplazamiento de palabra (correspondencia directa, 1 bloque por conjunto).

10 Bits de indice (2^10)

Tamaño de direccion de memoria 32 bits

Bloques de 32 bits.

Nº total de cache = 2^10 x 1 x (1 + (32-10-2) + 32) = 54272 bits ) 6784 bytes.

                                      RENDIMIENTO DE LA CACHÉ

Para calcular la velocidad a la que se ejecuta la caché realizamos las siguientes operaciones. Considerando Tcpu como el tiempo de funcionamiento normal del procesador.

Tejec = Tcpu + Tbloq_mem.

Tbloq_mem = Nºaccesos_mem x Tasa.Fallo x Penalizacion.Fallo

En general, no podemos decir que la tasa de fallos y la penalizacion sea la misma dado que hay operaciones que acceden a memoria o no. Sabiendo cuantas instrucciones acceden a datos en memoria (D/I).

Tbloq_mem = Nºaccesos_mem x (TFi x PFI + D/I x TFd x PFd).

Tejec = Nºinstr x CPIreal x Tciclo.

CPIreal = CPIideal + TFi x PFi + D/I x TFd x PFx

EJEMPLO: ¿Cuanto más rapida sería una maquina con una caché perfecta (sin fallos)? Programa P:

TFinstr = 2%

36% de las instrucciones acceden a memoria.

TFdat = 4%

Máquina M:

Frecuencia del reloj 50Mhz

CPI ideal = 2 cliclos

PF = 40ciclos

CPIreal = CPIideal + TFi*PFi + D/I*TFd*PFd CPIreal = 2 + (40*2/100) + (36/100 * 4/100 + 40) = 3.376ciclos.

CPIreal/CPIideal = 1.69. La maquina con caché perfecta funcionaría 1.69 veces más rápido.

¿Que ocurriría si el procesador es mas el mismo pero la memoria mas pequeña?

Si suponemos que el CPIideal es 1 ciclo, entonces el sistema con caché perfecta sería 2.376, que tras la division, es 2.376 veces mas rapido que una maquina sin caché perfecta. No obstante, habría un tiempo mayor para tratar los bloqueos de memoria.

1.376/3.376 = 41% 1.376/2.376 = 58%

¿Que ocurriría si la memoria fuera igual pero el procesador funcionara mas rapido?

Si se dobla la velocidad del procesador a 100Mhz, manteniendo el CPIideal = 2 ciclos.

El tiempo de acceso no varía pero los ciclos de reloj serían el doble de rapidos que antes, asi que haría 80 ciclos donde antes hacía 40.

CPIreal = 2 + (2/100 * 80) + (36/100 * 4/100 * 80) = 4.75 ciclos. CPIreal/CPIideal = 1.42 -> No es mejor que la anterior.

¿Y si hubieran cachés de diferentes niveles?

CPI ideal = 1 ciclo.

Reloj a 500 MHz.

Cachés de primer nivel separadas para datos e instrucciones.

Tiempo de acceso a la memoria principal de 200 ns.

Tasa de fallos en la caché de primer nivel de instrucciones del

5%.

Tasa de fallos en la caché de primer nivel de datos del 10%.

Una de cada 4 instrucciones son accesos a memoria.

Maquina con 1 nivel de cache: La penalizacion por fallo es de 100 ciclos:

CPIreal = 1 + (5/100 * 100) + (25/100 * 10/100 * 100) = 8.5

Maquina con 2 niveles de caché: Para acceder a la cache secundaria se necesitan 10 ciclos, la penalizacion por fallo es 12 ciclos.

CPIreal = 1 + (5/100 * 12) + (25/100 * 10/100 * 12) = 1.9

CPIreal-mono-nivel/CPIreal-duo-nivel => La Caché con dos niveles funciona 4.47 veces mas rapido.

[roikansuirius-blog]

Administracion y Gestion: Sistema de Ficheros

PARTICIONES

Una particion es un numero de sectores consecutivos que pertenecen al mismo volumen físico dentro de un disco duro (dispositivo de almacenamiento) o sistema de directorios. Los sistemas UNIX usan diferentes particiones para diferentes directorios para minimizar el impacto de actualizaciones, o posible corrupción del sistema de ficheros. Por ejemplo:

La partición para el sistema operativo: la partición raíz.

La partición para los ficheros de los usuarios: HOME.

La zona de intercambio o swap.

En relación a la gestión de los dispositivos de almacenamiento secundario mediante los ficherosespeciales de dispositivo encontramos que estos ficheros están organizados también siguiendo esta estructura de particiones. Por ejemplo:

/dev/sda: primer disco duro completo.

/dev/sda1: 1a partición del primer disco duro.

/dev/sda2: 2a partición del primer disco duro.

MASTER BOOT RECORD (PARTICIONAMIENTO CLÁSICO)

Generalmente en un disco duro no pueden hacerse mas de cuatro particiones, pero estas particiones tienen cracteristicas especiales, cada una de ellas se llamaria particion extendida, mientras que el resto serían particiones primarias. Las extendidas no soportan un sistema de archivos directamente pero dentro de estas pueden crearse particiones secundarias (logicas) a las que se les puede dar datos y valores.

Si usamos el comando ’fdisk -l dispositivo’ y vemos las particiones:

El dispositivo /dev/sda tiene una particion primaria /dev/sda1 (Linux) y una extendida /dev/sda2 (extended) y dentro de la extendida una particion lógica /dev/sda5 (linux LVM).

Como dato, la primera particion se encuentra a partir del sector 2048 para mantener el gestor de arranque, los numeros de sector se empiezan a contar desde el comienzo del disco y desde 0 se denomina LBA (Logical Block Addressing) los sectores totales tienen que caber en 32 bits y su tamaño normal suele ser de 512 bytes si el disco no tiene mas de 2TB, en otro caso, el tamaño de 4K vale hasta 16TB.

GUID PARTITION TABLE (PARTICIONAMIENTO GPT)

El esquema GPT permite discos mucho mayores que su predecesor. Tambien admite un numero practicamente de particiones aunque lo normal es que lleguen a 128. Utiliza un identificador global único para identificar a los discos y particiones que son 32 digitos hexadecimales divididos en cinco campos que se asigna a un recurso para referenciarlo, pudiendo ser pseudoaleatorio o no en algunos campos.

El equema GPT tambien añade una copia de respaldo de la tabla de particiones en los ultimos sectores del disc, todos los datos donde comienza la tabla, a partir de que sector comienzan las particiones… Como se verá mas adelante, en el modo UEFI no es necesario dejar espacio entre la tabla de particiones y el comienzo de la primera particion, pero sigue orientandose en el sector 2048 (1MB) por la alineación de las particiones.

MONTAR-DESMONTAR

En Linux hay un único sistema de ficheros lógico (una única jerarquía de directorios) del que cuelgan todos los dispositivos de almacenamiento disponibles en ese momento. De manera que el proceso de montar un sistema de ficheros conlleva que el contenido esté disponible ya que con este montaje se une este sistema de ficheros al sistema de ficheros lógico global, donde se podran acceder a sus datos dentro del sistema de ficheros lógico global que hace de punto de montaje.

Al desmontar un sistema de ficheros, éste deja de estar disponible directamente desde el punto de montaje del sistema de ficheros lógico global, quedando sus datos en estado consistente, guardados en el dispositivo de almacenamiento secundario.

Por tanto el punto de montaje es el directorio en el que se monta el sistema de ficheros. El sistema de ficheros raiz, donde se instala el SO. siempre está montado en el directorio / y no se puede desmontar y es el que primero se monta al encender el ordenador.

ORDENES

mount opciones <FicheroEspecialBloque> <PtoMontaje>: Permite montar un sistema de ficheros.

mount -t tipo_sf: tipo de sistema de ficheros

mount -r: montaje en solo lectura

mount -w: montaje en modo lectura/escritura

mount -o: opciones de montaje (nosuid, exec, remount…)

mount -t iso9660-r /dev/dvd /media/dvd

mount -w /dev/sdc1 /media/disk

mount -o usquota,noexec,nosuid /dev/sda2 /home

umount: Para desmontar un sistema de ficheros, solo se puede desmontar si no está suiendo utilizado (busy)

umount <PtoMontaje>

umount <FicheroEspecialBloque>

fuser: Para saber que ficheros se usan y que procesos los usan (f: fichero abierto, c: directorio de trabajo, e: ejecutando un fichero). lsof: permite obtener un listado de todos los ficheros abiertos.

FICHERO /EYC/FSTAB

Contiene informacion sobre todos los sistemas de ficheros a montar o disponibles, asi como zonas de intercambio a activar, el formato de cada una de sus lineas de texto es:

fi_especial pto_montaje tipo opciones dump_f pass_num

fi_especial: Fichero especial de bloque. 

pto_montaje: Directorio que sirve de punto de montaje

tipo: Tipo de sistema de ficheros (Ext3, Ext4, vfat, iso9660, swap,…)

opciones: Opciones para el montaje, separadas por comas y sin espacios. 

dump_f: frecuencia para hacer una copia de seguridad del sistema de ficheros con la orden dump (este campo no se usa actualmente).

pass_num: en tiempo de arranque, en que orden hay que chequear los sistemas de ficheros (ejecutar fsck para comprobar su estado). 

0: no se chequea

1: solo se chequea el primero (la raiz)

2,3,4…

Respecto a las opciones pueden ser:

rw: Lectura-esctura

ro: Solo lectura.

suid/nosuid: Permitido o no el acceso en modo SUID si se usa nosuid se impide que los bits SETUID y SETGID tengan efecto en los ejecutables del sistema, lo que provoca que no se tome el UID del propietario al ejecutarse ni su GID.

auto/noauto: Se monta automaticamente o no (ni usand omount -a)

exec/noexec: Permitir o no la ejecucion de ficheros.

usrquota, grpquota: Permitir o no cuotas de usuario y de grupo..

user,users,owner: Permitir a los usuarios normales montar un sistema de ficheros.

uid=500, gid=100: Propietario y grupo propietario de los ficheros del SF. 

umask=137: Mascara para aplicar los permisos por defecto a los directorios y ficheros que se creen en el sistema de ficheros.

Ejemplo de lineas en el fichero /etc/fstab:

Si quiero montar un sistema de ficheros con la orden mount, puedo escoger todas las opciones de montaje:

mount -t iso9660 -r -o noexec /dev/dvd /media/dvd

o bien dejar que se utilicen las detallas para este sistema de ficheros en el fichero de configuracion /etc/fstab

mount /media/dvd

Si queremos montar todos los SF indicados en /etc/fstab ejecutaremos todos sus automáticos:

mount -a

Si queremos obtener la informacion general de los SF montados o consultamos /etc/mtab o ejecutamos sin argumentos ’mount’.

PROPIETARIOS Y PERMISOS

El permiso para acceder a los ficheros se organiza en dos grados de propiedad, usuario y grupo.

Cambio de usuario: Con la orden chown, solo el usuario root puede ejecutarla:

chown pilar fichero

chown [-R] pilar directorio

chown pilar.profesor fichero (cambiamos usuario y grupo)

Cambio de propietario: Chgrp, se cambia el grupo propietario, esto han de ejecutarlo el propietario del fichero (pero tiene que pertenecer al nuevo grupo que desee cambiar) o el propio root.

chgrp profesor fichero

chgrp [-R] profesor directorio.

Cambiar los permisos: Organizados en 3 grupos (propietaroi-grupo-resto) y pueden ser (rwx), puede especificarse con el comando chmod y siendo el root o el propietario.

chmod u+r fichero

chmod [-R] g+w directorio

chmod 740 fichero

chmod +t directorio: Si un susuario tiene permisos de escritura en el directorio puede crear ficheros en su interior pero no borrar los que no le pertenecezcan. chmod u+s fichero: Un fichero ejecutabe produce un cambio de dominio a nivel de usuario de manera que durante la ejecución el usuario efectivo del proceso es el propietario del fichero y no el usuario que lo ejecutó, lo que permite ejecutar un programa aunque no se tengan los permisos si el usuario si los tenía. chmod g+s fichero: Lo mismo que antes pero con un cambio de grupo.

LISTA DE CONTROL DE ACCESO (ACLS)

Permite asociar a un fichero una lista de usuarios y rupos junto con cada uno los permisos de acceso que tienen. Para poder usar ACLS es necesario que el SF tenga soporte y se haya montado con la opcion ‘acl’ (Ext2/Ext3/Ext4). La orden ls -l indica que ficheros tienen ACLS.

[roikansuirius-blog]

Administracion y Gestion: Sistema de Ficheros

PARTICIONES

Una particion es un numero de sectores consecutivos que pertenecen al mismo volumen físico dentro de un disco duro (dispositivo de almacenamiento) o sistema de directorios. Los sistemas UNIX usan diferentes particiones para diferentes directorios para minimizar el impacto de actualizaciones, o posible corrupción del sistema de ficheros. Por ejemplo:

La partición para el sistema operativo: la partición raíz.

La partición para los ficheros de los usuarios: HOME.

La zona de intercambio o swap.

En relación a la gestión de los dispositivos de almacenamiento secundario mediante los ficherosespeciales de dispositivo encontramos que estos ficheros están organizados también siguiendo esta estructura de particiones. Por ejemplo:

/dev/sda: primer disco duro completo.

/dev/sda1: 1a partición del primer disco duro.

/dev/sda2: 2a partición del primer disco duro.

MASTER BOOT RECORD (PARTICIONAMIENTO CLÁSICO)

Generalmente en un disco duro no pueden hacerse mas de cuatro particiones, pero estas particiones tienen cracteristicas especiales, cada una de ellas se llamaria particion extendida, mientras que el resto serían particiones primarias. Las extendidas no soportan un sistema de archivos directamente pero dentro de estas pueden crearse particiones secundarias (logicas) a las que se les puede dar datos y valores.

Si usamos el comando 'fdisk -l dispositivo' y vemos las particiones:

El dispositivo /dev/sda tiene una particion primaria /dev/sda1 (Linux) y una extendida /dev/sda2 (extended) y dentro de la extendida una particion lógica /dev/sda5 (linux LVM).

Como dato, la primera particion se encuentra a partir del sector 2048 para mantener el gestor de arranque, los numeros de sector se empiezan a contar desde el comienzo del disco y desde 0 se denomina LBA (Logical Block Addressing) los sectores totales tienen que caber en 32 bits y su tamaño normal suele ser de 512 bytes si el disco no tiene mas de 2TB, en otro caso, el tamaño de 4K vale hasta 16TB.

GUID PARTITION TABLE (PARTICIONAMIENTO GPT)

El esquema GPT permite discos mucho mayores que su predecesor. Tambien admite un numero practicamente de particiones aunque lo normal es que lleguen a 128. Utiliza un identificador global único para identificar a los discos y particiones que son 32 digitos hexadecimales divididos en cinco campos que se asigna a un recurso para referenciarlo, pudiendo ser pseudoaleatorio o no en algunos campos.

El equema GPT tambien añade una copia de respaldo de la tabla de particiones en los ultimos sectores del disc, todos los datos donde comienza la tabla, a partir de que sector comienzan las particiones... Como se verá mas adelante, en el modo UEFI no es necesario dejar espacio entre la tabla de particiones y el comienzo de la primera particion, pero sigue orientandose en el sector 2048 (1MB) por la alineación de las particiones.

MONTAR-DESMONTAR

En Linux hay un único sistema de ficheros lógico (una única jerarquía de directorios) del que cuelgan todos los dispositivos de almacenamiento disponibles en ese momento. De manera que el proceso de montar un sistema de ficheros conlleva que el contenido esté disponible ya que con este montaje se une este sistema de ficheros al sistema de ficheros lógico global, donde se podran acceder a sus datos dentro del sistema de ficheros lógico global que hace de punto de montaje.

Al desmontar un sistema de ficheros, éste deja de estar disponible directamente desde el punto de montaje del sistema de ficheros lógico global, quedando sus datos en estado consistente, guardados en el dispositivo de almacenamiento secundario.

Por tanto el punto de montaje es el directorio en el que se monta el sistema de ficheros. El sistema de ficheros raiz, donde se instala el SO. siempre está montado en el directorio / y no se puede desmontar y es el que primero se monta al encender el ordenador.

ORDENES

mount opciones <FicheroEspecialBloque> <PtoMontaje>: Permite montar un sistema de ficheros.

mount -t tipo_sf: tipo de sistema de ficheros

mount -r: montaje en solo lectura

mount -w: montaje en modo lectura/escritura

mount -o: opciones de montaje (nosuid, exec, remount...)

mount -t iso9660-r /dev/dvd /media/dvd

mount -w /dev/sdc1 /media/disk

mount -o usquota,noexec,nosuid /dev/sda2 /home

umount: Para desmontar un sistema de ficheros, solo se puede desmontar si no está suiendo utilizado (busy)

umount <PtoMontaje>

umount <FicheroEspecialBloque>

fuser: Para saber que ficheros se usan y que procesos los usan (f: fichero abierto, c: directorio de trabajo, e: ejecutando un fichero). lsof: permite obtener un listado de todos los ficheros abiertos.

FICHERO /EYC/FSTAB

Contiene informacion sobre todos los sistemas de ficheros a montar o disponibles, asi como zonas de intercambio a activar, el formato de cada una de sus lineas de texto es:

fi_especial pto_montaje tipo opciones dump_f pass_num

fi_especial: Fichero especial de bloque. 

pto_montaje: Directorio que sirve de punto de montaje

tipo: Tipo de sistema de ficheros (Ext3, Ext4, vfat, iso9660, swap,...)

opciones: Opciones para el montaje, separadas por comas y sin espacios. 

dump_f: frecuencia para hacer una copia de seguridad del sistema de ficheros con la orden dump (este campo no se usa actualmente).

pass_num: en tiempo de arranque, en que orden hay que chequear los sistemas de ficheros (ejecutar fsck para comprobar su estado). 

0: no se chequea

1: solo se chequea el primero (la raiz)

2,3,4...

Respecto a las opciones pueden ser:

rw: Lectura-esctura

ro: Solo lectura.

suid/nosuid: Permitido o no el acceso en modo SUID si se usa nosuid se impide que los bits SETUID y SETGID tengan efecto en los ejecutables del sistema, lo que provoca que no se tome el UID del propietario al ejecutarse ni su GID.

auto/noauto: Se monta automaticamente o no (ni usand omount -a)

exec/noexec: Permitir o no la ejecucion de ficheros.

usrquota, grpquota: Permitir o no cuotas de usuario y de grupo..

user,users,owner: Permitir a los usuarios normales montar un sistema de ficheros.

uid=500, gid=100: Propietario y grupo propietario de los ficheros del SF. 

umask=137: Mascara para aplicar los permisos por defecto a los directorios y ficheros que se creen en el sistema de ficheros.

Ejemplo de lineas en el fichero /etc/fstab:

Si quiero montar un sistema de ficheros con la orden mount, puedo escoger todas las opciones de montaje:

mount -t iso9660 -r -o noexec /dev/dvd /media/dvd

o bien dejar que se utilicen las detallas para este sistema de ficheros en el fichero de configuracion /etc/fstab

mount /media/dvd

Si queremos montar todos los SF indicados en /etc/fstab ejecutaremos todos sus automáticos:

mount -a

Si queremos obtener la informacion general de los SF montados o consultamos /etc/mtab o ejecutamos sin argumentos 'mount'.

PROPIETARIOS Y PERMISOS

El permiso para acceder a los ficheros se organiza en dos grados de propiedad, usuario y grupo.

Cambio de usuario: Con la orden chown, solo el usuario root puede ejecutarla:

chown pilar fichero

chown [-R] pilar directorio

chown pilar.profesor fichero (cambiamos usuario y grupo)

Cambio de propietario: Chgrp, se cambia el grupo propietario, esto han de ejecutarlo el propietario del fichero (pero tiene que pertenecer al nuevo grupo que desee cambiar) o el propio root.

chgrp profesor fichero

chgrp [-R] profesor directorio.

Cambiar los permisos: Organizados en 3 grupos (propietaroi-grupo-resto) y pueden ser (rwx), puede especificarse con el comando chmod y siendo el root o el propietario.

chmod u+r fichero

chmod [-R] g+w directorio

chmod 740 fichero

chmod +t directorio: Si un susuario tiene permisos de escritura en el directorio puede crear ficheros en su interior pero no borrar los que no le pertenecezcan. chmod u+s fichero: Un fichero ejecutabe produce un cambio de dominio a nivel de usuario de manera que durante la ejecución el usuario efectivo del proceso es el propietario del fichero y no el usuario que lo ejecutó, lo que permite ejecutar un programa aunque no se tengan los permisos si el usuario si los tenía. chmod g+s fichero: Lo mismo que antes pero con un cambio de grupo.

LISTA DE CONTROL DE ACCESO (ACLS)

Permite asociar a un fichero una lista de usuarios y rupos junto con cada uno los permisos de acceso que tienen. Para poder usar ACLS es necesario que el SF tenga soporte y se haya montado con la opcion 'acl' (Ext2/Ext3/Ext4). La orden ls -l indica que ficheros tienen ACLS.

[roikansuirius-blog]

Introduccion a los Sistemas Operativos (T2)

Un proceso es un programa en ejecución, mientras que el programa solo es contenido estático (almacenado en disco) el proceso está ‘vivo’ y su estado depende del contador de programa y que registros de CPU esté usando, sus variables…

Un proceso puede comprender a varios programas, esto es lo ocurre en Unix, y un mismo programa puede comprender varios procesos. En la multitarea el CPU alterna rápidamente entre diversos procesos (cambio de proceso). Cuando solo hay una CPU y esta se pasa rapidamente de un proceso a otro, tenemos la sensacion de que todos se ejecutan al mismo tiempo pero es falso, ademas entre que se ejecuta un proceso y se detiene el anterior hay paradas de inactividad. 

Aunque es mas costoso de implementar (y en la vida real la multitarea existe) tiene muchas ventajas:

Compartir recursos físicos: Es mejor que los programas compartan memoria a tener que tener memorias dedicadas para cada programa. 

Compartir recursos lógicos: Como bases de datos por ejemplo. 

Acelerar los calculos: Si queremos que una tarea compleja se haga de forma rápia, lo mejor es dividirla en subrpoblemas mas sencillos para que se ejecuten en paralelo (para lo cual la CPU ha de tener varios nucles o tener mas de una CPU).

Modularidad: A veces los módulos permiten construir con mas facilidad un sistema que si se tratara de construir el bloque entero y completo.

Comodidad: Los usuarios están acostumbrados a realizar diversas tareas simultaneamente, asi que hay que proporcionarles dichas herramientas.

Pero en cualquier caso los programas no deben de programarse con hipotesis de tiempo implícitas, no sabemos si pasados 10 segundos, el programa estará activo o estará bloqueado porque dependera del planificador el elegir que proceso pasa a la CPU y cual no.

CREACION Y DESTRUCCION DE PROCESOS

Como ya sabemos por las prácticas, la creacion de procesos en Unix depende de dos comandos:

La llamada al sistema fork() que lo que hace es duplicar el proceso que realiza la llamada y cuya unica diferencia con este es que en el hijo está el valor devuelto por fork() [0] y en el padre un numero que corresponde al PID de su hijo.

Para que el hijo realice una tarea distinta al padre (pues ambos son copias) se utiliza el valor que tiene este desde el fork() y hacer una cosa u otra segun una funcion condicional pero lo normal es usar un exec(). 

Al usar exec() el codigo del hijo se sustiye por los datos de otro programa pasado como argumento al sistema y comienza la ejecución desde su inicio.

Como exec() no crea un nuevo proceso hay cosas que se conservan, como los ficheros abiertos (aunque puede cambiarse), el tratamiento de las señales (generalmente referidas a las interrupciones que pueden enviarse a un proceso) y el PID del proceso y casi todas las demas propiedades del mismo.

Mientras el hijo no termine su función, el padre se encuentra parado , y cuando este termina le comunica al padre que lo ha terminado y continua la ejecución del padre. Se puede liberar en cualquier momento un proceso y si esta liberacion no resulta exitosa siempre se puede matar al proceso. 

ESTADOS DE UN PROCESO

Un proceso se encuentra en tres estados:

Ejecucion: Utiliza la CPU en el instante. 

Listo: El proceso es ejecutable pero no tiene CPU porque hay otro proceso ejecutandose antes. 

Bloqueado: No se ejecuta incluso si se diera CPU porque está esperando otro evento (recibir memoria, el resultado de otra operacion…).

Cuando un proceso se suspende se expulsa a disco y no se utiliza la RAM para almacenarlo. Eso se debe a varios posibles motivos:

El sistema está funcionando mal: puede suspenderse los procesos hasta que el problema se solucione y luego reanudarlos. 

Depuracion: si los resultados de un proceso son incerrorectos puede suspenderse dicho proceso. Si se confirma que son correctos se reanuda y si no se finaliza. 

Si el sistema está muy cargado, se pueden suspender algunos para dar prioridad a otros. 

Listado de fases posibles para un proceso:

Bloqueado -> Bloqueado suspendido: Si interesa liberar memoria.

Bloqueado suspendido -> Listo suspendido: El evento que esperaba ocurre pero no tiene CPU. 

Listo suspendido -> Listo: Si no hay procesos listos para evitar que la CPU no haga nada pueden pasarse procesos a su ejecución. Esto suele depender generalmente de su orden de prioridad. 

Listo -> Listo suspendido: Generalmente se pasa un proceso en ejecución a suspendido cuando hay bloqueado uno de alta prioridad. 

Nuevo -> Listo suspendido: Al crear un proceso no hay memoria disponible y es probable que no tenga la prioridad suficiente como para expulsar a otras. 

Bloqueado suspendido -> Bloqueado: Uno de los procesos suspendidos tiene la prioridad mas alta y el SO sospecha que el evento que espera sucedera pronto.

En ejecucion -> Listo suspendido: Si un proceso de prioridad alta despierta de bloqueado suspendido y no  hay memoria suficiente si no se pasa a disco el proceso que se está ejecutando. 

Cualquier estado -> Saliente: En cualquier momento puede expulsarse un proceso.

IMPLEMENTACION DE PROCESOS

El PCB (process control block) guarda la informacion relacionada con el proceso correspondiente. En el PCB se guarda todo aquello necesario para que el proceso pueda continuar su ejecución como si nada hubiera pasado. 

Al crear un proceso debe de guardarse al menos:

El nombre del proceso (generalmente el PID).

Insertarlo en la tabla de procesos creando su PCB. 

Determinad su prioridad inicial.

Asignarle recursos iniciales.

Mas a fondo esto se produce como:

El proceso padre realiza la llamada al sistema fork() y se pasa al nucleo del SO

El nucleo busca una entrada libre en el la tabla de procesos para el hijo y le asigna un PID. 

Toda la informacion de la tabla del padre se copia en la entrada del hijo. 

Se le asigna memoria para los segmentos de datos y de pila del hijo y se copia todo lo del padre en él. 

Se incrementan los contadores para cualquier fichero abierto por el padre para que tambien se reflejen que estan abiertos en el hijo. 

Al proceso hijo se le asigna el estado listo. Se devuelve el PID del hijo al padre y se le da el valor 0 al hijo (pues su creacion fue exitosa).

ESTRUCTURA DE UN PROCESO

En Unix cuando un proceso realiza una llamada al sistema, se considera que ese proceso pasa de modo usuario a modo núcleo y ejecuta el codigo del SO que atiende la llamada al sistema. Cada proceso tiene dos partes, la que se ejecuta como modo usuario (generalmente unica y propia) y la del modo nucleo (que es comun siempre que quiera usarse el modo núcleo).

Esto implica que la parte del núcleo de cada proceso cuente con su propio contador de programa y su propia pila.  USi un proceso se bloquea dentro del modo núcleo, provocara que se le ceda la CPU a otro proceso y cuando se desbliquee volverá a él dentro del nucleo hasta finalizar con la llamada que le invocó.

CAMBIO DE PROCESOS

Si el SO toma el control de la CPU por una llamada al sistema, los posibles pasos que se pueden dar para quitar la CPU al proceso que la tenia hasta ese momento y darsela a otro son:

El hardware almacena en una pila el contador del programa del proceso que se interrumpe (el que lo llamó).

El hardware pasa a modo nucleo y carga el nuevo contador de programa del vector de interrupciones. 

Un procedimiento en lenguaje ensamblador, cuya direccion se cargó a través del contador de programa anterior, guarda el contexto, en la tabla de procesos. Puede actualizar o no otra informacion del PCB y se elimina la informacion depositada por el hardware en la pila del proceso que se interrumpe. 

Otro procedimiento configura la nueva pila que va a utilizar el nucleo mientras se atiende la llama al sistema. 

El procedimiento en ensamblador llama al procedimiento del paso anterior para saber si existe. Durante la ejecucion este se puede bloquear por lo que su estado cambiará o no. 

Tras la llamada al SO se vuelve al procedimiento en lenguaje ensamblador, que mira si hay que ejecutal el planificador. Si el proceso se bliqueó es porque el planificador ya lo haya invocado y no tenga porque re-invocarlo. 

El planificador regrea al codigo ensamblador que restaura el contexto del proceso a ejecutar, carga en los registros del procesador los valores que habia en el momento en el que al proceso al que se le dara la CPU se le quitó. El SO entrega el control de la CPU al proceso seleccionado por el planificador. 

Se cambia a modo usuario y se regresa de la interrupcion,a si que se desapila la siguiente direccion a ejecutar elegida por el planificador.

HILOS 

Para distinguir a la unidad de planificacion y ejecución, la llamaremos hilo o proceoso ligero. y seguiremos hablando de proceso o tarea para la unidad de las propiedades de los recursos. 

Varios hilos pueden existir dentro de un único proceso. Esto significa que contiene una traza de ejecución entre uno o mas programas (los hilos funcionan para comunicar diferentes procesos). Generalmente pare crear un hijo hilo se utiliza la funcion pthread_create y cada hilo ejecuta su porcion de codigo como si fuera el principal, no obstante todos tienen un mismo PID pues se encuentran dentro del mismo proceso (si es que lo estuvieran en un principio).

El concepto de hilo y que los hilos esten en un proceso haze que se produzca una separacion entre lo que pertenece al proceso y lo que pertenece a un hilo. 

Para los procesos:

Una zona de memoria que contiene la imagen del proceso. 

Acceso protegido al procesador, otros procesos, ficheros y recursos de E/S

Variables globales, procesos hijos, señales…

Informacion contable.

Para los hilos: 

Un estado. 

Un contexto guardado del procesador cuando no se está ejecutando para poder reanudar su ejecucion cuando se le de la CPU (contador de programa independiente).

Una pila de ejecución.

Almacenamiento por hilo para las variables locales.

Acceso a la memoria y recursos de un proceso, compartido por el resto de hilos. 

APLICACIONES DE LOS HILOS

Existen varias razones por las que querer usar hilos dentro de un proceso y no al reves:

Como los hilos comparten un mismo espacio de direcciones se comunican entre si sin intervencion del núcleo. 

Los hilos se pueden bloquear en espera de que se termine una llamada al SO igual que un proceso normal, lo que permite acelerar la ejecucion de un proceso al solaparse la E/S con su propio cómputo.

Los hilos son mas faciles de crear en un proceso existente que crear un nuevo proceso, lo mismo que hacer operaciones entre hilos. 

Si hay varias CPU’s o una CPU con varios nucleos se consigue cierto paralelismo entre procesos. 

Los hilos facilitan la construccion de programas ya que cada funcion puede ser desempeñada por un hilo. 

Por ejemplo, en un procesador de texto, un hilo se puede activar cada minuto para escribir las modificaciones que hay en RAM a disco y asi evitar pérdidas si se cierra el programa o hay un fallo de corriente.

HILOS EN MODO USUARIO Y NÚCLEO

Los hilos o bien se implementan con llamadas al sistema o a través de bibliotecas a nivel de usuarios. Cada una tiene sus ventajas y desventajas. 

Empezando por el modo usuario: 

El nucleo no sabe que existen los hilos, por lo que se pueden usar en núcleos que no implementen hilos.

Los cambios de contexto entre hilos son mucho mas rápidos ya que no es necesario pasar a núcleo. 

Cada proceso puede tener su algoritmo de planificacion para los hilos. 

No obstante, como el SO no es consciente de la existencia de varios hilos. Cualquier llamada al SO por un hilo bloqueara todo el proceso y sus hilos. Por lo que no se solapa la E/S con el cómputo. 

Un fallo de página (cuando un proceso intenta acceder a una de sus páginas  y no se encuentra en memoria principal) bloquea todo el proceso y todos sus hilos.

La CPU asignada al proceso tiene que repartirse entre todos sus hilos (100MHz para dos hilos hacen 50MHz).

Si hay varias CPU’s no es posible obtener paralelismo real dentro de un mismo proceso. 

Respecto al modo nucleo:

El nucleo mantiene la tabla de hilos y reparte la CPU entre todos ellos, si hay varias CPU’s varios hilos de un mismo proceso se pueden ejecutar en CPU’s distintas, por lo que existe paralelismo real.

Las llamadas al SO no suponen ningun problema. Si un hilo se bloquea el núcleo puede dar la CPU a otro hilo del mismo proceso o de otro proceso.

Los fallos de página no representa problema pues se puede pasar a otro hilo del mismo proceso o de otro proceso.

Ahora bien, las funciones mas usadas para sincronizar hilos son llamadas al SO por lo tanto mas costosas. 

La creacion y destruccion de hilos es costosa tambien aunque si se reutilizan hilos esto puede aliviarse. 

PLANIFICACION DE PROCESOS

El orden en el que un planificador selecciona los procesos listos para su ejecución viene determinado por la meta que se pretende conseguir, algunas son:

Equidad: Cada proceso obtiene su proporción ‘justa’ de CPU.

Eficacia: Mantener ocupada la CPU al 100% realizando trabajo util (E=Tutil/Ttotal * 100).

Tiempo de espera: Minimiza el tiempo que pasa un proceso en la cola de procesos listos esperando a que se le conceda la CPU.

Tiempo de respuesta: El tiempo que transcurre desde que se solicita la ejecucción de la accion hasta que se obtienen los resultados. 

Tiempo de regreso: Es el tiempo que tanscurre desde que se entrega un trabajo hasta que se obtienen sus resultados.

Rendimiento: Maximizar el numero de tareas procesadas por unidad de tiempo.

PLANIFICACION APROPIATIVA Y NO APROPIATIVA

Para complicar la planificación los procesos son impredecibles, algunos utilizan mucha CPU otros se pasan mucho tiempo esperanod interacciones, asi que en el momento en el que el planificador cede la CPU a un proceso no sabe cuando se bloqueará o terminara. 

La estrategia a adoptar es una planificacion apropiativa (expulsar procesos ejecutables de la CPU para ejecutar otros procesos mas importantes) o no apropiativa (permitir ejecutarse un proceso hasta que termine o se bloquee). Para los procesos por lotes, donde no hay interaccion con el usuario puede usarse cualquier planificacion, en cambio para los interactivos se tiene que usar una apropiativa para cambiar rápidamente CPU de un proceso a otro.

CICLOS DE RÁFAGAS DE CPU Y E/S

La ejecución de un proceso consiste en un ciclo de ejecución en la CPU (rafaga de CPU), un ciclo de espera de E/S (rafaga de E/S), otra ráfaga de CPU…y asi sucesivamente esto se conoce como “comenzando” “esperando”.

El tiempo que dura una ráfaga no se conoce a prori aunque en algunos casos puede estimarse a partir de ejecuciones anteriores. Esta alternancia de ráfagas de CPU y de E/S de los procesos es la qu hace posible la existencia de la multiprogramacion ya que mientras unos procesos están en rafaga de E/S otros estan en ráfagas de CPU.

Un proceso limitado por E/S es aquel que pasa la mayor parte de su tiempo en espera de una operacion de E/S por lo que sus rafagas de CPU son lentas. 

Un proceso limitado por CPU es aquel que necesita usar la CPU la mayor parte de su tiempo, asi que es esperable que tenga ráfagas de E/S cortas o ninguna. 

Distribuir estos procesos hará que un algoritmo de planificacion sea adecuado y muchas veces estos algoritmos favorecen a un tipo de proceso. 

PLANIFICACION ‘FIRST-COME, FIRST-SERVED’ (FCFS)

Mas simple de todos, el proceso que primero pide la CPU es el primero que se le asigna, asi que es un algoritmo no apropiativo asi que el siguiente proceso no tendra CPU hasta que se bloquee o termine, puede implementarse con una cola FIFO (First-Input, First-Output).

El tiempo promedio de respuesta puede ser largo. Si tengo tres procesos con duraciones de la siguiente ráfaga de CPU para 3 procesos (P1, P2, P3) si el tiempo de respuesta para cada uno es de 24, 27, 30 el tiempo medio es de (24+27+30)/3 = 27. 

Sin embargo si el orden es P2, P1, P3 es (3+6+30)/3 = 13. Por lo tanto, el diagrama de Gantt coincide cone l de una planificacion SJF (Short-Job-First).

Asi que este algoritmo produce un efecto convoy que surge de la siguiente manera, un proceso Limitado por CPU la ocupa durante mucho tiempo. Los procesos limitadoes E/S terminan sus peticion pasando a la cola de listos a la espera de que la CPU quede libre. Asi que no hay mas operaciones hasta que se termine la actual. En general se desaprovechan los recursos al tener dos tareas menores esperando a que una grande termine (un gran convoy seguido de vagones).

PLANIFICACION “SHORT JOB FIRST” (SJF)

Perfecto para procesos con lotes, onde los tiempos de ejecucion se conocen de antemano (o una aproximacion). El algoritmo consiste en coger, de entre todos los que están listos, aquel que menos tiempo en ejecutarse tarda (o aquel con menor ráfaga de CPU).

Para interaccion con el usuario siguiendo el esquema “esperar->ejecutar” podemos hacer una estimacion del tiempo como:

Et = a * E(t-1) + (1-a) * T(t-1)  para t=2, 3, 4….

PLANIFICACION “SHORTEST-REMAINING-TIME FIRST” (SRTF)

Otro algoritmo no apropiativo, se puede hacer si al quitarle la CPU a otro proceso con el tiempo de ráfaga de CPU menor que el que se está ocutando. Basicamente el primero que tenga el menor tiempo restante es el primero que e hace.

[roikansuirius-blog]

PLANIFICACION ROUND ROBIN (RR)

Los procesos se atienden en el orden de llegada a la cola de procesos listos, aunque se asigna a cada proceso un tiempo de ejecución llamado “quantum”. Para el cambio de proceso se da una de tres cosas: “consume su quantum” “termina antes de consumir su quantum” o “se queda bloqueado”.

Si el quantum es pequeño, la CPU cambia mucho de proceso, por loq ue la CPU se desperdida en la tarea que supone pasar de un proceso a otro (guardar registros, cargarlos, mapas de memoria...). Si el quantum es mayor, la CPU se desperdicia poco pero los ultimos procesos de la lista tardan mucho tiempo en ser atendidos.

PLANIFICACION A CORTO, MEDIO Y LARGO PLAZO

Una forma practica de trabajar con el intercambio de procesos, cuando unos se encuentran en disco y otros en memoria principal por lo que se necesitan dos planificadores (uno a corto plazo PCP que ha sido lo que hemos visto anteriormente y otro de medio plazo PMP) que se encarga de mover procesos de memoria a disco o viceversa. 

Periodicamente se llama al PMP para eliminar de memoria los procesos que hayan permanecido en ella el tiempo suficiente (suspension de procesos) y para cargar en memoria los procesos que hayan estado en disco demasiado tiempo (reanudacion de procesos) tras esto actual el PCP hasta que se llame al PMP.

Es posible acoplar un PLP para decidir entre los procesos por letas preparados cual entra al sistema para su ejecución y cual entra a memoria o disco segun su criterio.

[roikansuirius-blog]

Programación Orientada a Objetados (T.4)

CLASES HEREDADAS

Con la siguiente definicion de las clase burbuja crearemos las siguientes sub-clases o clases heredadas. Donde todas las funciones del hijo se heredan desde el padre y si hay que modificar alguna funcion podemos simplemente sobreescribirla (overray) y, en caso de que tengamos que elegir cual de las dos funciones hacer (las que estan en el hijo porque vienen del padre o las que estan en el hijo solamente) deberemos de escoger cuidadosamente entre super (desde el padre) o this (del proceso actual).

La clase Burbuja tiene la siguiente forma: 

Region: Circulo espacial en la que se encuentra. 

velocidadMaxima: Que posee la burbuja.

velocidadActual: A cero por defecto pero puede modificarse.

explotada: Un booleano.

Y como operaciones tiene:

Burbujas: El constructor valido y sin usar referencias a la hora de crearlo (constructor de copia).

getAtributos: Para cada uno de los atributos.

explotar(): Funcion para explotar una burbuja. 

situar(Punto): Situar la burbuja en un punto determinado (generalmente x=variable y=0).

ascender(): Para hacer que la burbuja suba.

chocar(): Para saber si hay choque.

BURBUJA LIMITADA

Una burbuja limitada es como una burbuja normal, salvo que tiene un contador de cuantas veces puede moverse. Esto significa que tiene una nueva propiedad llamada ‘limiteDesplazamiento’ y que por tanto, solo afecta a la funcion ascender y es un valor fijo.

Para establecer una clase por herencia a la hora de declarar la clase deberemos de poner en el Objeto que hereda o la superclase (superclass) “Burbuja”.

De primeras tendremos que poner los atributos que tenga e inmediatamente el constructor que requerirá de usar el constructor de burbujas que está en el padre y despues inicializar el resto de valores que sean propios de la clase. Asi que en esencia, mientras que la burbuja se haya desplazado menos que su limite (cantidadDesplazamiento como un atributo auxiliar) puede seguir ascendiendo.

Nota: Aunque no se ha puesto recuerda que debes de tener la funcion getlimiteDesplazamiento.

BURBUJA DÉBIL

Una burbuja débil es una sobre la cual solo pueden hacerse x botes antes de que explote. Este número es variable asi que no es fijo como ocurre con el límite de desplazamiento.

[roikansuirius-blog]

,

[roikansuirius-blog]

Programación Orientada a Objetados (T.4)

CLASES HEREDADAS

Con la siguiente definicion de las clase burbuja crearemos las siguientes sub-clases o clases heredadas. Donde todas las funciones del hijo se heredan desde el padre y si hay que modificar alguna funcion podemos simplemente sobreescribirla (overray) y, en caso de que tengamos que elegir cual de las dos funciones hacer (las que estan en el hijo porque vienen del padre o las que estan en el hijo solamente) deberemos de escoger cuidadosamente entre super (desde el padre) o this (del proceso actual).

La clase Burbuja tiene la siguiente forma: 

Region: Circulo espacial en la que se encuentra. 

velocidadMaxima: Que posee la burbuja.

velocidadActual: A cero por defecto pero puede modificarse.

explotada: Un booleano.

Y como operaciones tiene:

Burbujas: El constructor valido y sin usar referencias a la hora de crearlo (constructor de copia).

getAtributos: Para cada uno de los atributos.

explotar(): Funcion para explotar una burbuja. 

situar(Punto): Situar la burbuja en un punto determinado (generalmente x=variable y=0).

ascender(): Para hacer que la burbuja suba.

chocar(): Para saber si hay choque.

BURBUJA LIMITADA

Una burbuja limitada es como una burbuja normal, salvo que tiene un contador de cuantas veces puede moverse. Esto significa que tiene una nueva propiedad llamada ‘limiteDesplazamiento’ y que por tanto, solo afecta a la funcion ascender y es un valor fijo.

Para establecer una clase por herencia a la hora de declarar la clase deberemos de poner en el Objeto que hereda o la superclase (superclass) “Burbuja”.

De primeras tendremos que poner los atributos que tenga e inmediatamente el constructor que requerirá de usar el constructor de burbujas que está en el padre y despues inicializar el resto de valores que sean propios de la clase. Asi que en esencia, mientras que la burbuja se haya desplazado menos que su limite (cantidadDesplazamiento como un atributo auxiliar) puede seguir ascendiendo.

Nota: Aunque no se ha puesto recuerda que debes de tener la funcion getlimiteDesplazamiento.

BURBUJA DÉBIL

Una burbuja débil es una sobre la cual solo pueden hacerse x botes antes de que explote. Este número es variable asi que no es fijo como ocurre con el límite de desplazamiento.

[roikansuirius-blog]

Programación Orientada a Objetados (T.4)

CLASES HEREDADAS

Con la siguiente definicion de las clase burbuja crearemos las siguientes sub-clases o clases heredadas. Donde todas las funciones del hijo se heredan desde el padre y si hay que modificar alguna funcion podemos simplemente sobreescribirla (overray) y, en caso de que tengamos que elegir cual de las dos funciones hacer (las que estan en el hijo porque vienen del padre o las que estan en el hijo solamente) deberemos de escoger cuidadosamente entre super (desde el padre) o this (del proceso actual).

La clase Burbuja tiene la siguiente forma: 

Region: Circulo espacial en la que se encuentra. 

velocidadMaxima: Que posee la burbuja.

velocidadActual: A cero por defecto pero puede modificarse.

explotada: Un booleano.

Y como operaciones tiene:

Burbujas: El constructor valido y sin usar referencias a la hora de crearlo (constructor de copia).

getAtributos: Para cada uno de los atributos.

explotar(): Funcion para explotar una burbuja. 

situar(Punto): Situar la burbuja en un punto determinado (generalmente x=variable y=0).

ascender(): Para hacer que la burbuja suba.

chocar(): Para saber si hay choque.

BURBUJA LIMITADA

Una burbuja limitada es como una burbuja normal, salvo que tiene un contador de cuantas veces puede moverse. Esto significa que tiene una nueva propiedad llamada ‘limiteDesplazamiento’ y que por tanto, solo afecta a la funcion ascender y es un valor fijo.

Para establecer una clase por herencia a la hora de declarar la clase deberemos de poner en el Objeto que hereda o la superclase (superclass) “Burbuja”.

De primeras tendremos que poner los atributos que tenga e inmediatamente el constructor que requerirá de usar el constructor de burbujas que está en el padre y despues inicializar el resto de valores que sean propios de la clase. Asi que en esencia, mientras que la burbuja se haya desplazado menos que su limite (cantidadDesplazamiento como un atributo auxiliar) puede seguir ascendiendo.

Nota: Aunque no se ha puesto recuerda que debes de tener la funcion getlimiteDesplazamiento.

BURBUJA DÉBIL

Una burbuja débil es una sobre la cual solo pueden hacerse x botes antes de que explote. Este número es variable asi que no es fijo como ocurre con el límite de desplazamiento.

[roikansuirius-blog]

Programación Orientada a Objetados (T.4)

CLASES HEREDADAS

Con la siguiente definicion de las clase burbuja crearemos las siguientes sub-clases o clases heredadas. Donde todas las funciones del hijo se heredan desde el padre y si hay que modificar alguna funcion podemos simplemente sobreescribirla (overray) y, en caso de que tengamos que elegir cual de las dos funciones hacer (las que estan en el hijo porque vienen del padre o las que estan en el hijo solamente) deberemos de escoger cuidadosamente entre super (desde el padre) o this (del proceso actual).

La clase Burbuja tiene la siguiente forma: 

Region: Circulo espacial en la que se encuentra. 

velocidadMaxima: Que posee la burbuja.

velocidadActual: A cero por defecto pero puede modificarse.

explotada: Un booleano.

Y como operaciones tiene:

Burbujas: El constructor valido y sin usar referencias a la hora de crearlo (constructor de copia).

getAtributos: Para cada uno de los atributos.

explotar(): Funcion para explotar una burbuja. 

situar(Punto): Situar la burbuja en un punto determinado (generalmente x=variable y=0).

ascender(): Para hacer que la burbuja suba.

chocar(): Para saber si hay choque.

BURBUJA LIMITADA

Una burbuja limitada es como una burbuja normal, salvo que tiene un contador de cuantas veces puede moverse. Esto significa que tiene una nueva propiedad llamada ‘limiteDesplazamiento’ y que por tanto, solo afecta a la funcion ascender y es un valor fijo.

Para establecer una clase por herencia a la hora de declarar la clase deberemos de poner en el Objeto que hereda o la superclase (superclass) “Burbuja”.

De primeras tendremos que poner los atributos que tenga e inmediatamente el constructor que requerirá de usar el constructor de burbujas que está en el padre y despues inicializar el resto de valores que sean propios de la clase. Asi que en esencia, mientras que la burbuja se haya desplazado menos que su limite (cantidadDesplazamiento como un atributo auxiliar) puede seguir ascendiendo.

Nota: Aunque no se ha puesto recuerda que debes de tener la funcion getlimiteDesplazamiento.

BURBUJA DÉBIL

Una burbuja débil es una sobre la cual solo pueden hacerse x botes antes de que explote. Este número es variable asi que no es fijo como ocurre con el límite de desplazamiento.

[roikansuirius-blog]

Introduccion a los Sistemas Operativos (T2)

Un proceso es un programa en ejecución, mientras que el programa solo es contenido estático (almacenado en disco) el proceso está ‘vivo’ y su estado depende del contador de programa y que registros de CPU esté usando, sus variables…

Un proceso puede comprender a varios programas, esto es lo ocurre en Unix, y un mismo programa puede comprender varios procesos. En la multitarea el CPU alterna rápidamente entre diversos procesos (cambio de proceso). Cuando solo hay una CPU y esta se pasa rapidamente de un proceso a otro, tenemos la sensacion de que todos se ejecutan al mismo tiempo pero es falso, ademas entre que se ejecuta un proceso y se detiene el anterior hay paradas de inactividad. 

Aunque es mas costoso de implementar (y en la vida real la multitarea existe) tiene muchas ventajas:

Compartir recursos físicos: Es mejor que los programas compartan memoria a tener que tener memorias dedicadas para cada programa. 

Compartir recursos lógicos: Como bases de datos por ejemplo. 

Acelerar los calculos: Si queremos que una tarea compleja se haga de forma rápia, lo mejor es dividirla en subrpoblemas mas sencillos para que se ejecuten en paralelo (para lo cual la CPU ha de tener varios nucles o tener mas de una CPU).

Modularidad: A veces los módulos permiten construir con mas facilidad un sistema que si se tratara de construir el bloque entero y completo.

Comodidad: Los usuarios están acostumbrados a realizar diversas tareas simultaneamente, asi que hay que proporcionarles dichas herramientas.

Pero en cualquier caso los programas no deben de programarse con hipotesis de tiempo implícitas, no sabemos si pasados 10 segundos, el programa estará activo o estará bloqueado porque dependera del planificador el elegir que proceso pasa a la CPU y cual no.

CREACION Y DESTRUCCION DE PROCESOS

Como ya sabemos por las prácticas, la creacion de procesos en Unix depende de dos comandos:

La llamada al sistema fork() que lo que hace es duplicar el proceso que realiza la llamada y cuya unica diferencia con este es que en el hijo está el valor devuelto por fork() [0] y en el padre un numero que corresponde al PID de su hijo.

Para que el hijo realice una tarea distinta al padre (pues ambos son copias) se utiliza el valor que tiene este desde el fork() y hacer una cosa u otra segun una funcion condicional pero lo normal es usar un exec(). 

Al usar exec() el codigo del hijo se sustiye por los datos de otro programa pasado como argumento al sistema y comienza la ejecución desde su inicio.

Como exec() no crea un nuevo proceso hay cosas que se conservan, como los ficheros abiertos (aunque puede cambiarse), el tratamiento de las señales (generalmente referidas a las interrupciones que pueden enviarse a un proceso) y el PID del proceso y casi todas las demas propiedades del mismo.

Mientras el hijo no termine su función, el padre se encuentra parado , y cuando este termina le comunica al padre que lo ha terminado y continua la ejecución del padre. Se puede liberar en cualquier momento un proceso y si esta liberacion no resulta exitosa siempre se puede matar al proceso. 

ESTADOS DE UN PROCESO

Un proceso se encuentra en tres estados:

Ejecucion: Utiliza la CPU en el instante. 

Listo: El proceso es ejecutable pero no tiene CPU porque hay otro proceso ejecutandose antes. 

Bloqueado: No se ejecuta incluso si se diera CPU porque está esperando otro evento (recibir memoria, el resultado de otra operacion…).

Cuando un proceso se suspende se expulsa a disco y no se utiliza la RAM para almacenarlo. Eso se debe a varios posibles motivos:

El sistema está funcionando mal: puede suspenderse los procesos hasta que el problema se solucione y luego reanudarlos. 

Depuracion: si los resultados de un proceso son incerrorectos puede suspenderse dicho proceso. Si se confirma que son correctos se reanuda y si no se finaliza. 

Si el sistema está muy cargado, se pueden suspender algunos para dar prioridad a otros. 

Listado de fases posibles para un proceso:

Bloqueado -> Bloqueado suspendido: Si interesa liberar memoria.

Bloqueado suspendido -> Listo suspendido: El evento que esperaba ocurre pero no tiene CPU. 

Listo suspendido -> Listo: Si no hay procesos listos para evitar que la CPU no haga nada pueden pasarse procesos a su ejecución. Esto suele depender generalmente de su orden de prioridad. 

Listo -> Listo suspendido: Generalmente se pasa un proceso en ejecución a suspendido cuando hay bloqueado uno de alta prioridad. 

Nuevo -> Listo suspendido: Al crear un proceso no hay memoria disponible y es probable que no tenga la prioridad suficiente como para expulsar a otras. 

Bloqueado suspendido -> Bloqueado: Uno de los procesos suspendidos tiene la prioridad mas alta y el SO sospecha que el evento que espera sucedera pronto.

En ejecucion -> Listo suspendido: Si un proceso de prioridad alta despierta de bloqueado suspendido y no  hay memoria suficiente si no se pasa a disco el proceso que se está ejecutando. 

Cualquier estado -> Saliente: En cualquier momento puede expulsarse un proceso.

IMPLEMENTACION DE PROCESOS

El PCB (process control block) guarda la informacion relacionada con el proceso correspondiente. En el PCB se guarda todo aquello necesario para que el proceso pueda continuar su ejecución como si nada hubiera pasado. 

Al crear un proceso debe de guardarse al menos:

El nombre del proceso (generalmente el PID).

Insertarlo en la tabla de procesos creando su PCB. 

Determinad su prioridad inicial.

Asignarle recursos iniciales.

Mas a fondo esto se produce como:

El proceso padre realiza la llamada al sistema fork() y se pasa al nucleo del SO

El nucleo busca una entrada libre en el la tabla de procesos para el hijo y le asigna un PID. 

Toda la informacion de la tabla del padre se copia en la entrada del hijo. 

Se le asigna memoria para los segmentos de datos y de pila del hijo y se copia todo lo del padre en él. 

Se incrementan los contadores para cualquier fichero abierto por el padre para que tambien se reflejen que estan abiertos en el hijo. 

Al proceso hijo se le asigna el estado listo. Se devuelve el PID del hijo al padre y se le da el valor 0 al hijo (pues su creacion fue exitosa).

ESTRUCTURA DE UN PROCESO

En Unix cuando un proceso realiza una llamada al sistema, se considera que ese proceso pasa de modo usuario a modo núcleo y ejecuta el codigo del SO que atiende la llamada al sistema. Cada proceso tiene dos partes, la que se ejecuta como modo usuario (generalmente unica y propia) y la del modo nucleo (que es comun siempre que quiera usarse el modo núcleo).

Esto implica que la parte del núcleo de cada proceso cuente con su propio contador de programa y su propia pila.  USi un proceso se bloquea dentro del modo núcleo, provocara que se le ceda la CPU a otro proceso y cuando se desbliquee volverá a él dentro del nucleo hasta finalizar con la llamada que le invocó.

CAMBIO DE PROCESOS

Si el SO toma el control de la CPU por una llamada al sistema, los posibles pasos que se pueden dar para quitar la CPU al proceso que la tenia hasta ese momento y darsela a otro son:

El hardware almacena en una pila el contador del programa del proceso que se interrumpe (el que lo llamó).

El hardware pasa a modo nucleo y carga el nuevo contador de programa del vector de interrupciones. 

Un procedimiento en lenguaje ensamblador, cuya direccion se cargó a través del contador de programa anterior, guarda el contexto, en la tabla de procesos. Puede actualizar o no otra informacion del PCB y se elimina la informacion depositada por el hardware en la pila del proceso que se interrumpe. 

Otro procedimiento configura la nueva pila que va a utilizar el nucleo mientras se atiende la llama al sistema. 

El procedimiento en ensamblador llama al procedimiento del paso anterior para saber si existe. Durante la ejecucion este se puede bloquear por lo que su estado cambiará o no. 

Tras la llamada al SO se vuelve al procedimiento en lenguaje ensamblador, que mira si hay que ejecutal el planificador. Si el proceso se bliqueó es porque el planificador ya lo haya invocado y no tenga porque re-invocarlo. 

El planificador regrea al codigo ensamblador que restaura el contexto del proceso a ejecutar, carga en los registros del procesador los valores que habia en el momento en el que al proceso al que se le dara la CPU se le quitó. El SO entrega el control de la CPU al proceso seleccionado por el planificador. 

Se cambia a modo usuario y se regresa de la interrupcion,a si que se desapila la siguiente direccion a ejecutar elegida por el planificador.

HILOS 

Para distinguir a la unidad de planificacion y ejecución, la llamaremos hilo o proceoso ligero. y seguiremos hablando de proceso o tarea para la unidad de las propiedades de los recursos. 

Varios hilos pueden existir dentro de un único proceso. Esto significa que contiene una traza de ejecución entre uno o mas programas (los hilos funcionan para comunicar diferentes procesos). Generalmente pare crear un hijo hilo se utiliza la funcion pthread_create y cada hilo ejecuta su porcion de codigo como si fuera el principal, no obstante todos tienen un mismo PID pues se encuentran dentro del mismo proceso (si es que lo estuvieran en un principio).

El concepto de hilo y que los hilos esten en un proceso haze que se produzca una separacion entre lo que pertenece al proceso y lo que pertenece a un hilo. 

Para los procesos:

Una zona de memoria que contiene la imagen del proceso. 

Acceso protegido al procesador, otros procesos, ficheros y recursos de E/S

Variables globales, procesos hijos, señales…

Informacion contable.

Para los hilos: 

Un estado. 

Un contexto guardado del procesador cuando no se está ejecutando para poder reanudar su ejecucion cuando se le de la CPU (contador de programa independiente).

Una pila de ejecución.

Almacenamiento por hilo para las variables locales.

Acceso a la memoria y recursos de un proceso, compartido por el resto de hilos. 

APLICACIONES DE LOS HILOS

Existen varias razones por las que querer usar hilos dentro de un proceso y no al reves:

Como los hilos comparten un mismo espacio de direcciones se comunican entre si sin intervencion del núcleo. 

Los hilos se pueden bloquear en espera de que se termine una llamada al SO igual que un proceso normal, lo que permite acelerar la ejecucion de un proceso al solaparse la E/S con su propio cómputo.

Los hilos son mas faciles de crear en un proceso existente que crear un nuevo proceso, lo mismo que hacer operaciones entre hilos. 

Si hay varias CPU’s o una CPU con varios nucleos se consigue cierto paralelismo entre procesos. 

Los hilos facilitan la construccion de programas ya que cada funcion puede ser desempeñada por un hilo. 

Por ejemplo, en un procesador de texto, un hilo se puede activar cada minuto para escribir las modificaciones que hay en RAM a disco y asi evitar pérdidas si se cierra el programa o hay un fallo de corriente.

HILOS EN MODO USUARIO Y NÚCLEO

Los hilos o bien se implementan con llamadas al sistema o a través de bibliotecas a nivel de usuarios. Cada una tiene sus ventajas y desventajas. 

Empezando por el modo usuario: 

El nucleo no sabe que existen los hilos, por lo que se pueden usar en núcleos que no implementen hilos.

Los cambios de contexto entre hilos son mucho mas rápidos ya que no es necesario pasar a núcleo. 

Cada proceso puede tener su algoritmo de planificacion para los hilos. 

No obstante, como el SO no es consciente de la existencia de varios hilos. Cualquier llamada al SO por un hilo bloqueara todo el proceso y sus hilos. Por lo que no se solapa la E/S con el cómputo. 

Un fallo de página (cuando un proceso intenta acceder a una de sus páginas  y no se encuentra en memoria principal) bloquea todo el proceso y todos sus hilos.

La CPU asignada al proceso tiene que repartirse entre todos sus hilos (100MHz para dos hilos hacen 50MHz).

Si hay varias CPU’s no es posible obtener paralelismo real dentro de un mismo proceso. 

Respecto al modo nucleo:

El nucleo mantiene la tabla de hilos y reparte la CPU entre todos ellos, si hay varias CPU’s varios hilos de un mismo proceso se pueden ejecutar en CPU’s distintas, por lo que existe paralelismo real.

Las llamadas al SO no suponen ningun problema. Si un hilo se bloquea el núcleo puede dar la CPU a otro hilo del mismo proceso o de otro proceso.

Los fallos de página no representa problema pues se puede pasar a otro hilo del mismo proceso o de otro proceso.

Ahora bien, las funciones mas usadas para sincronizar hilos son llamadas al SO por lo tanto mas costosas. 

La creacion y destruccion de hilos es costosa tambien aunque si se reutilizan hilos esto puede aliviarse. 

PLANIFICACION DE PROCESOS

El orden en el que un planificador selecciona los procesos listos para su ejecución viene determinado por la meta que se pretende conseguir, algunas son:

Equidad: Cada proceso obtiene su proporción ‘justa’ de CPU.

Eficacia: Mantener ocupada la CPU al 100% realizando trabajo util (E=Tutil/Ttotal * 100).

Tiempo de espera: Minimiza el tiempo que pasa un proceso en la cola de procesos listos esperando a que se le conceda la CPU.

Tiempo de respuesta: El tiempo que transcurre desde que se solicita la ejecucción de la accion hasta que se obtienen los resultados. 

Tiempo de regreso: Es el tiempo que tanscurre desde que se entrega un trabajo hasta que se obtienen sus resultados.

Rendimiento: Maximizar el numero de tareas procesadas por unidad de tiempo.

PLANIFICACION APROPIATIVA Y NO APROPIATIVA

Para complicar la planificación los procesos son impredecibles, algunos utilizan mucha CPU otros se pasan mucho tiempo esperanod interacciones, asi que en el momento en el que el planificador cede la CPU a un proceso no sabe cuando se bloqueará o terminara. 

La estrategia a adoptar es una planificacion apropiativa (expulsar procesos ejecutables de la CPU para ejecutar otros procesos mas importantes) o no apropiativa (permitir ejecutarse un proceso hasta que termine o se bloquee). Para los procesos por lotes, donde no hay interaccion con el usuario puede usarse cualquier planificacion, en cambio para los interactivos se tiene que usar una apropiativa para cambiar rápidamente CPU de un proceso a otro.

CICLOS DE RÁFAGAS DE CPU Y E/S

La ejecución de un proceso consiste en un ciclo de ejecución en la CPU (rafaga de CPU), un ciclo de espera de E/S (rafaga de E/S), otra ráfaga de CPU…y asi sucesivamente esto se conoce como “comenzando” “esperando”.

El tiempo que dura una ráfaga no se conoce a prori aunque en algunos casos puede estimarse a partir de ejecuciones anteriores. Esta alternancia de ráfagas de CPU y de E/S de los procesos es la qu hace posible la existencia de la multiprogramacion ya que mientras unos procesos están en rafaga de E/S otros estan en ráfagas de CPU.

Un proceso limitado por E/S es aquel que pasa la mayor parte de su tiempo en espera de una operacion de E/S por lo que sus rafagas de CPU son lentas. 

Un proceso limitado por CPU es aquel que necesita usar la CPU la mayor parte de su tiempo, asi que es esperable que tenga ráfagas de E/S cortas o ninguna. 

Distribuir estos procesos hará que un algoritmo de planificacion sea adecuado y muchas veces estos algoritmos favorecen a un tipo de proceso. 

PLANIFICACION ‘FIRST-COME, FIRST-SERVED’ (FCFS)

Mas simple de todos, el proceso que primero pide la CPU es el primero que se le asigna, asi que es un algoritmo no apropiativo asi que el siguiente proceso no tendra CPU hasta que se bloquee o termine, puede implementarse con una cola FIFO (First-Input, First-Output).

El tiempo promedio de respuesta puede ser largo. Si tengo tres procesos con duraciones de la siguiente ráfaga de CPU para 3 procesos (P1, P2, P3) si el tiempo de respuesta para cada uno es de 24, 27, 30 el tiempo medio es de (24+27+30)/3 = 27. 

Sin embargo si el orden es P2, P1, P3 es (3+6+30)/3 = 13. Por lo tanto, el diagrama de Gantt coincide cone l de una planificacion SJF (Short-Job-First).

Asi que este algoritmo produce un efecto convoy que surge de la siguiente manera, un proceso Limitado por CPU la ocupa durante mucho tiempo. Los procesos limitadoes E/S terminan sus peticion pasando a la cola de listos a la espera de que la CPU quede libre. Asi que no hay mas operaciones hasta que se termine la actual. En general se desaprovechan los recursos al tener dos tareas menores esperando a que una grande termine (un gran convoy seguido de vagones).

PLANIFICACION “SHORT JOB FIRST” (SJF)

Perfecto para procesos con lotes, onde los tiempos de ejecucion se conocen de antemano (o una aproximacion). El algoritmo consiste en coger, de entre todos los que están listos, aquel que menos tiempo en ejecutarse tarda (o aquel con menor ráfaga de CPU).

Para interaccion con el usuario siguiendo el esquema “esperar->ejecutar” podemos hacer una estimacion del tiempo como:

Et = a * E(t-1) + (1-a) * T(t-1)  para t=2, 3, 4….

PLANIFICACION “SHORTEST-REMAINING-TIME FIRST” (SRTF)

Otro algoritmo no apropiativo, se puede hacer si al quitarle la CPU a otro proceso con el tiempo de ráfaga de CPU menor que el que se está ocutando. Basicamente el primero que tenga el menor tiempo restante es el primero que e hace.