Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Monitores

2011-04-06T14:21:31Z

Aliciammf: /* Definición */

Idea desarrollada en los años 70 Brinch-Hansen y Hoare que notaron los siguientes problemas con respecto al uso de los semáforos:

* Los semáforos son difíciles de usar. Es frecuente que el programador cometa errores al emplearlos.
* El compilador no asiste al programador en el desarrollo de programas concurrentes mediante semáforos, pues no ofrece ningún tipo de validación en tiempo de compilación.

Los monitores tienen que estar integrados en el lenguaje de programación.

== Definición ==
Un monitor es una estructura del lenguaje cuyas principales características son:

* Los datos son privados.
* Ofrecen una serie de métodos públicos para acceder a dichos datos.
* En cada momento sólo puede haber un proceso activo en algún método del monitor, es decir, ejecutando código de esos métodos públicos del monitor.

Permiten organizar procesos en espera mediante:

* Variables de condición: lista de procesos inicialmente vacía.
* Primitivas: ''wait(c)'', añade el proceso p invocante a c y proceso p bloquea; ''signal(c)'', selecciona a uno de los procesos en c y lo pone en preparado.

<source lang="java">

class recursoCompartido {

public int get(void);
public void set(int valor);
private int recursoCompartido;
private Semaforo s = 1;

public int get(void){
int ret;
down(s);
ret = recursoCompartido;
up(s);
return ret;
}

public void set(int valor){
down(s);
recursoCompartido = v;
up(s);
}
}

</source>

== Fuentes ==
http://java.sun.com/developer/Books/performance2/chap4.pdf

Cerrojos

2011-04-06T14:15:55Z

Aliciammf: /* Cerrojos mediante instrucciones atómicas */

= Ejemplo de implementación =

El siguiente código sería un posible ejemplo del uso de control de concurrencia mediante cerrojos:

<source lang="c">
int cerrojo = 1; /* Inicializamos la variable cerrojo. Esto sería sólo válido para
hilos, ya que los procesos no comparten espacio de memoria */

while(cerrojo == 0); // Protocolo de
cerrojo = 0; // entrada

... // Sección crítica

cerrojo = 1; // Protocolo de salida
</source>

Sin embargo, esto es problemático: Supongamos que tenemos únicamente un proceso con dos hilos (Hx y Hy) y el planificador retire al proceso Hx justo antes de ejecutarse la instrucción ''cerrojo = 0;''. El proceso Hy ejecuta su código, entra en la sección crítica (Esto puede ocurrir ya que cerrojo sigue a 1) y el planificador le retira el uso del procesador dentro de ésta. A continuación, se le vuelve a asignar el procesador a Hx.

De esta forma, tenemos a dos hilos ejecutando código de la sección crítica. Para evitar este problema, debemos implementar los protocolos de entrada y salida de forma que se ejecuten en una sola instrucción, con lo cual o el planificador retira el uso del procesador antes de esta instrucción, o sino lo retira después de haberla ejecutado.

= Cerrojos mediante instrucciones atómicas =

Podemos implementar cerrojos mediante instrucciones especiales de comprobación y puesta a 0 y 1.

<source lang="c">
int cerrojo = 0;

void lock() {
while (__sync_lock_test_and_set(&cerrojo, 1));
}

void unlock() {
__sync_lock_release(&cerrojo);
}
</source>

El método lock comprueba mediante __sync_locktest_and_set(&cerrojo,1) el valor del cerrojo: si es 0, cambia el valor del cerrojo a 1 y devuelve 0, por tanto, se sale del while y entra en sección crítica; si es 1, devuelve 1 y continúa comprobando el valor, por tanto, no entra en situación crítica hasta que cambie el valor del cerrojo.

El método unlock simplemente, mediante _sync_lock_release(&cerrojo) cambia el valor del cerrojo a 0.

* http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html
* http://stackoverflow.com/questions/1383363/is-my-spin-lock-implementation-correct-and-optimal

Cerrojos

2011-04-06T14:14:54Z

Aliciammf: /* Cerrojos mediante instrucciones atómicas */

= Ejemplo de implementación =

El siguiente código sería un posible ejemplo del uso de control de concurrencia mediante cerrojos:

<source lang="c">
int cerrojo = 1; /* Inicializamos la variable cerrojo. Esto sería sólo válido para
hilos, ya que los procesos no comparten espacio de memoria */

while(cerrojo == 0); // Protocolo de
cerrojo = 0; // entrada

... // Sección crítica

cerrojo = 1; // Protocolo de salida
</source>

Sin embargo, esto es problemático: Supongamos que tenemos únicamente un proceso con dos hilos (Hx y Hy) y el planificador retire al proceso Hx justo antes de ejecutarse la instrucción ''cerrojo = 0;''. El proceso Hy ejecuta su código, entra en la sección crítica (Esto puede ocurrir ya que cerrojo sigue a 1) y el planificador le retira el uso del procesador dentro de ésta. A continuación, se le vuelve a asignar el procesador a Hx.

De esta forma, tenemos a dos hilos ejecutando código de la sección crítica. Para evitar este problema, debemos implementar los protocolos de entrada y salida de forma que se ejecuten en una sola instrucción, con lo cual o el planificador retira el uso del procesador antes de esta instrucción, o sino lo retira después de haberla ejecutado.

= Cerrojos mediante instrucciones atómicas =

Podemos implementar cerrojos mediante instrucciones especiales de comprobación y puesta a 0 y 1.

<source lang="c">
int cerrojo = 0;

void lock() {
while (__sync_lock_test_and_set(&cerrojo, 1));
}

void unlock() {
__sync_lock_release(&cerrojo);
}
</source>

El método lock comprueba mediante __sync_locktest_and_set(&cerrojo,1) el valor del cerrojo, si es 0, cambia el valor del cerrojo a 1 y devuelve 0, por tanto, se sale del while, si es 1, devuelve 1 y continúa comprobando el valor, por tanto, no entra en situación crítica.

El método unlock simplemente, mediante _sync_lock_release(&cerrojo) cambia el valor del cerrojo a 0.

* http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html
* http://stackoverflow.com/questions/1383363/is-my-spin-lock-implementation-correct-and-optimal

Sol-ejer2-planif-procesos

2011-03-21T18:11:26Z

Aliciammf: /* = */

= Turno rotatorio =

____|_PA_|_PB_|_PC_|
Datos del _H0_|_0__|_1__|_2__|
problema _t__|_3__|_5__|_6__|

PA bloquea por E/S cada 1 unidad de tiempo
PB bloquea por E/S cada 3 unidades de tiempo
< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador

| | | | | | | | | | | | | | | | | | | |
PA <---| | | | |---| | | |---> | | | | | | | | |
PB | <---|---| | | |---| | | |---|---> | | | | | | |
PC | | < |---|---| | |---|---| | | |---|---> | | | | |
Planificador X X | X | X X X | X X | X | X | | | | |
____|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|__> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

_____|_PA_|_PB_|_PC_|
Cálculos __t__|_3__|_5__|_6__|
de tiempos __T__|_10_|_11_|_12_|
_T/t_|3.3_|2.2_|_2__|

DEBERIAS PONER ESTO EN LA ZONA DE DISCUSIÓN

Sigue estando mal, el quantum no se reduce a 1 en el proceso A, el quantum se debe respetar siempre(en el articulo de la wiki sobre turno rotatorio lo explican).

Pd: No pises las otras soluciones propuestas, pon la tuya debajo para que todos podamos discutirlo.

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
/ = Tiempo desaprovechado bien por bloqueo de E/S o por finalización del proceso.

| | | | | | | | | | | | | | | | | | | |
PA <---|///| | | | |---|///| | | | |---|///> | | | | |
PB | | |---|---| | | | |---|---| | | | |---|///> | | |
PC | | < | |---|---| | | | |---|---| | | | |---|---> |
Planificador X X | X | X X X | X X | X | X | | | | |
____|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|__> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

= Por prioridades =

Suponiendo que la prioridad de los procesos es la siguiente: A<B<C

____|_PA_|_PB_|_PC_|
Datos del _H0_|_0__|_1__|_2__|
problema _t__|_3__|_5__|_6__|

PA bloquea por E/S cada 1 unidad de tiempo
PB bloquea por E/S cada 3 unidades de tiempo
< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
/ = Tiempo desaprovechado por bloqueo de E/S.

| | | | | | | | | | | | | | | | | | | |
PA <---| | | | | | | | | | | | | |---|///|///|---|///|///>
PB | <---| | | | | | |---|---|///|///|---|---> | | | | | |
PC | | <---|---|---|---|---|---> | | | | | | | | | | | |
Planificador X X X | | | | | X X X | X | X | | | | | |
____|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|__ | t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

_____|_PA_|_PB_|_PC_|
Cálculos __t__|_3__|_5__|_6__|
de tiempos __T__|_20_|_13_|_6_|
_T/t_|6.66|_2.6|_1__|

= Turno rotatorio proporcional al número de procesos =

____|_PA _|_PB_|_PC _|
Datos del _H0_|_0__|_1__|_2__|
problema _t__|_3__|_5__|_6__|

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador

 | | | | | | | | | | | | | | | | | | | | |
PA <---| | |---| | |---> | | | | | | | | | | | | |
PB | <---| | |---| | |---| | |---| |---> | | | | | | |
PC | | <---| | |---| | |---|---| |---| |---> | | | | | |
Planificador X X X X X X X X X | X X X X | | | | | | |
 -----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

_____|_PA_|_PB_|_PC_|
Cálculos __t__|_3__|_5__|_6__|
de tiempos __T__|_7__|_12_|_12_|
_T/t_|2.3_|2.4_|_2__|

=============
Observaciones
=============

- Al no existir en el instante de tiempo 0 problemas de concurrencia de procesos, ¿no debería el proceso A tener derecho a sus dos unidades de tiempo de quantum, aunque este solo utilice una unidad de tiempo debido al bloqueo por E/S?. Esto dejaría al procesador con dos procesos en estado preparado (B y C) en el instante de tiempo 2, donde ya se reduciría el quantum a 1 debido a la existencia de 2 o más procesos en estado preparado. ¿Cómo lo veis?

Creo que no, porque ya en el instante 1 hay dos procesos en el planificador, por lo que el quantum ya se reduce.

Discusión:Sol-ejer2-planif-procesos

2011-03-21T18:07:12Z

Aliciammf:

Creo que la solución al ejercicio 2.1 es la siguiente :
< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
/ = Tiempo del quantum desaprovechado bien por bloqueo de E/S o por finalización del proceso.

| | | | | | | | | | | | | | | | | | | |
PA <---|///| | | | |---|///| | | | |---|///> | | | | |
PB | < |---|---| | | | |---|///| | | | |---|---> | | |
PC | | < | |---|---| | | | |---|---| | | | |---|---> |
Planificador X X | X | X X X | X X | X | X | | | | |
____|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|__> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

Tengo dudas referente a lo que dice el enunciado de que se producirá un bloqueo por E/S en el pA por cada unidad de tiempo. En la unidad de tiempo 6 se han ejecutado dos unidades de tiempo por lo que se producirán dos bloqueos por E/S, por lo tanto, tras ejecutarse esa unidad de tiempo se tendrán que bloquear dos unidades de tiempo más.Pero como el quantum es de 2 unidades,únicamente se bloquea una unidad. Y así ocurre con todas las veces que se ejecuta el Pa. Estoy en lo cierto?
En el criterio de planificación del RR dice que cuando el proceso pasa a estado bloqueado antes de la finalización del quantum pasa al final de la cola,¿eso quiere decir que en el momento que esté en estado bloqueado termina directamente su ejecución dándole opción al planificador de aplicador de nuevo el criterio utilizado,o por el contrario tiene que estar las unidades de tiempo necesarias en estado bloqueado hasta la finalización del quantum?

Creo que sí estás en lo cierto en lo referente al bloqueo del Pa. Por Round Robin estricto el quantum se debe de hacer entero, aunque esté en bloqueado o haya finalizado el proceso que lo ocupa. Es distinto que pase al final de la cola a que se termine el quantum.

Por cierto, creo que la solución de prioridades está mal, aquí la que creo es la solución:

| | | | | | | | | | | | | | | | | | | |
PA <---| | | | | | | | | |---|///| | |---> | | | |
PB | <---| | | | | | |---|---|///|///|---|---> | | | | | |
PC | | <---|---|---|---|---|---> | | | | | | | | | | | |
Planificador X X X | | | | | X X | X | X | | | | | |
____|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|__ | t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Supongo que al no ser quantums fijos en el instante 10 que PB pasa a bloqueado, Pa puede ejecutarse. Lo pongo en discusión porque no se si estoy equivocada.

Discusión:Sol-ejer2-planif-procesos

2011-03-21T18:02:08Z

Aliciammf:

Conceptos básicos

2011-03-19T12:04:23Z

Aliciammf: /* Fichero */

A continuación se desarrollan conceptos básicos que se emplearan a los largo de la asignatura.

= Programa =

Se trata de una secuencia de instrucciones que desarrolla algún tipo de actividad útil.

= Proceso =

Un proceso es una instancia de un programa que está en ejecución. Todo proceso dispone como mínimo de una línea de ejecución.

Queda definido por: {programa, estado}

= Usuario =

Puede ser un humano o un autómata.

En sistemas UNIX encontramos un código único para cada uno, el UID (User IDentifier). A su vez debe pertenecer a un grupo, definido por el GID (Group IDentifier).

= Fichero =

Estructura de datos que almacena información.

Conceptos básicos

2011-03-19T12:02:39Z

Aliciammf:

Planificación de procesos

2011-03-17T12:46:53Z

Aliciammf: /* Aspectos para diseñar un buen criterio de planificación */

Todo planificador de procesos emplea uno o varios criterios (''scheduling policy'', en inglés) que determinan el criterio de selección del proceso que empleará el procesador.

== Aspectos para diseñar un buen criterio de planificación ==

Además de ofrecer un alto rendimiento y una baja latencia propia de un buen planificador, debe cumplir las siguientes características:

*'''Repetitividad''' : con cargas de trabajo (cantidad de procesos a atender) similares, el procesador debe tener comportamientos similares.
*'''Predecibilidad''' : hace referencia la tiempo de terminación de un proceso para cierta carga de trabajo, deben ser similares con cargas de trabajo parecidas.
*'''Eficiencia''' : debe tomar decisiones rápidas para aumentar el rendimiento.
*'''Reducir el número de conmutaciones''' : de nuevo, para aumentar el rendimiento y reducir la penalización asociada.
*'''Atender prioridades'''.
* A mayores cargas de trabajo el rendimiento debe '''degradar uniformemente'''.