Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Sol-ejer3-planif-procesos

2011-06-14T16:12:49Z

Josvaldia:

= Ejercicio 3 =

Datos del problema:
| Pa | Pb | Pc | Pd |
--------------------------
H0 | 0 | 1 | 2 | 3 |
--------------------------
t | 4 | 4 | 12 | 12 |
--------------------------

Pa y Pb bloquean por operación de E/S tras 1 unidad de ejecución

< = 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 | | <---|---| | | | |---|---|---|---| | | | | | | | |
Pd | | | < |---|---| | | | | | |---|---|---|---| | | | |
Plnf X X X | X | X X X | | | X | | | X | | | X
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

... continuación ...

| | | | | | | | | | | | |
Pa | | | | | | | | | | | | |
Pb | | | | | | | | | | | | |
Pc |---|---|---|---| | | | |---|---> | |
Pd | | | | |---|---|---|---| | |---|--->
Plnf | | | | X | | | X | X | |
|___|___|___|___|___|___|___|___|___|___|___|___|
20 21 22 23 24 25 26 27 28 29 30 31 32

Cálculo de índices:

| Pa | Pb | Pc | Pd |
--------------------------
t | 4 | 4 | 12 | 12 |
--------------------------
T | 19 | 20 | 30 | 32 |
--------------------------
T/t |4.75| 5 | 2.5 |2.66|
--------------------------

Explicación:

Todos los procesos empiezan inicialmente en la segunda cola. Pa y Pb reciben una oportunidad de ejecución sin consumir su quantum debido a bloqueo, por tanto, permanecen en la segunda cola. Pc y Pd consumen todo su quantum, por tanto, promocionan a la primera cola. Los procesos Pa y Pb se ejecutan otra vez, pues los procesos que se encuentran en la segunda cola reciben dos oportunidades de ejecución. Tras esto, los procesos recién ascendidos a la primera cola, que son Pc y Pd, reciben su oportunidad de ejecución, en este caso con quantum de 4 unidades. De nuevo, se le da oportunidad de ejecución a los procesos de la segunda cola, que terminan su ejecución. Como no hay más procesos en la segunda cola, se le da una oportunidad de ejecución a los de la primera. --[[Usuario:Pneira|Pneira]] 18:36 22 mar 2011 (UTC)

= Dudas =

No entiendo por qué en la unidad de tiempo 18 no aparece el proceso c y d y posteriormente a b c y d.Esto es a lo que me refiero --[[Usuario:Jherrera|Jherrera]]:

| | | | | | | | | | | | |
Pa | | | | | | | | |---> | | |
Pb | | | | | | | | | |---> | |
Pc |---|---|---|---| | | | | | |------->
Pd | | | | |---|---|---|---| | | | |------>
Plnf | | | | X | | | X | X | X
|___|___|___|___|___|___|___|___|___|___|___|___|
18 19 20 21 22 23 24 25 26 27 28 29 30

Solucion: Por que en la 2ª cola estan los procesos A y B, por que nunca consumen los quantums, y la 2ª cola siempre se itera 2 veces.

¿No se supone que la cola 1 posee mayor prioridad que la 2? siendo asi, mientras C y D esten en la 1ª cola no se le debería volver a dar oportunidad a la cola 2 no?¿--[[Usuario:DvS 013|DvS 013]]

Creo que se lo que dices. Aunque C y D esten en la primera cola, se pasa a la segunda. Esto es porque la primera cola no tiene mas prioridad, sino solo un quantum más ancho. Entonces se mira la primera cola, luego 2 veces la segunda, y vuelta a empezar --[[Usuario:PCamino|PCamino]]

El problema creo yo es que el enunciado ha sido modificado de esta mañana para acá, porque yo también hice el ejercicio para subirlo a la wiki, pero se me adelantaron, y esta mañana en el enunciado ponia que la cola 1 tenia más prioridad que la 2, y ademas no ponia el tiempo que estaban en estado bloqueado los procesos, ahora si lo pone, y no pone lo de la prioridad. Yo estoy de acuerdo con la solucion propuesta arriba. --[[Usuario:Josmorgav1|Josmorgav1]] 21:42 22 mar 2011 (UTC)

Vaya caos! Podemos poner ambos ejercicios --[[Usuario:PCamino|PCamino]]

Con respecto a la prioridad de las colas multinivel realimentadas, creo que carecen de prioridad, simplemente basta con saber cuantas veces se ejecutan cada una y en cual de ellas se meten los procesos que van llegando.--[[Usuario:Jmf bsk|Jmf bsk]] 23:10 22 mar 2011 (UTC)

DUDA: Creo que este ejercicio está hecho para tiempos de bloqueo de 2 unidades, mientras que en el enunciado los tiempos de bloqueo es de 1 t. Si fuera para tiempos de bloqueo = 1 en el instante 2 Pa regresa a la cola 2 de preparados, luego pasaría a estado activo antes que Pd , por lo que en t=4 Pa pasaría a estado activo,después iría Pd y después la segunda ejecución de Pb. Lo escribo para aclararlo:

Pa y Pb bloquean cada unidad de tiempo, durante una unidad de tiempo de bloqueo.

| | | | | | | | | | | | | | | | | | | | |
Pa <---| | | |---| | | | | | | | | | | |---| |---> |
Pb | <---| | | | | |---| | | | | | | | | |---| |--->
Pc | | <---|---| | | | |---|---|---|---| | | | | | | | |
Pd | | | < | |---|---| | | | | |---|---|---|---| | | | |
Plnf X X X | X X | X X | | | X | | | X | | | X
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

¿es correcta la solución que planteo para una unidad de tiempo de bloqueo?

Sol-ejer2-planif-procesos

2011-06-13T16:36:04Z

Josvaldia: /* Turno rotatorio estricto */

= Turno rotatorio estricto =

____|_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__|

Notése que el proceso A no llega a emplear el ''quantum'' que tiene asignado, en ese caso, como indica la [[Criterios_de_planificación|teoría]], se le retira el procesador y el planificador selecciona a otro proceso. Dejar el procesador sin proceso asignado, es decir, ocioso, va contra la lógica del máximo aprovechamiento del procesador. Por ello, he retirado una solución incorrecta que aparecía en esta sección. --[[Usuario:Pneira|Pneira]] 21:15 21 mar 2011 (UTC)

Tengo una duda en este ejercicio, en la unidad de tiempo 6 cuando el planificador activa el proceso Pb, porque motivo solo le asigna una unidad de tiempo?, podria asignarle 2 no? teniendo en cuenta que el quantum = 2. Ademas el proceso B bloquea cada 3 unidades de tiempo, no entiendo porque solo le asigna una unidad y luego activa en la unidad de tiempo 7 el proceso C. LFE (Luis Fernandez Esteban)

Pues yo diría que es porque se bloquea cada 3, al igual que el A se bloquea a cada unidad. Ya llevaba 1, y con esa actividad, +2 --[[Usuario:PCamino|PCamino]]

Gracias, tienes razon ya lo entendi. LFE (Luis Fernandez Esteban)

DUDA
En t=3 llegaría el proceso Pa y el proceso Pb a la cola de estado preparado. Como dice en teroía, un proceso que se bloquea sin llegar a agotar su quantum, pasaría al final de la cola de estados preparados. Por tanto, el siguiente en ejecutarse sería Pb, puesto que Pa viene de estar bloqueado sin agotar su quantum luego pasaría al final de la cola de preparados. ¿Estoy en lo cierto?
--[[Usuario:josvaldia|josvaldia]]

= 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

| | | | | | | | | | | | | | | | | | | |
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

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

Alguien me puede explicar ¿por que de 14 a 15 no se procesa nada? AnaBarros

Creo que eso esta mal...y he visto mas fallos por ahi o eso me parece... :S Luis Fernandez Esteban

Sí lo creo como el C solo debia de empenzar en el 3 pero empienza antes. Ana Barros

Del 14 al 15 no se procesa nada porque sólo quedan los procesos A y B, pero en esa unidad de tiempo ambos están bloqueados (los bloqueos de A y B duran 2 uds. de tiempo)

= 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.

Cierto, además creo que aunque A no se bloquease, se le seguiría asignando 1 unidad de tiempo en t=1 al proceso B: Entraría el planificador, reduciría el quantum, y al no haber compensación, A pasaría de nuevo al final de la cola del turno rotatorio, dejando el procesador a B, ¿no?

- Duda: En el instante 9 no debería entrar el proceso Pb en vez de seguir el Pc??

Lo dudo, porque el bloqueo de B dura 2 unidades, así que C tiene carta libre.--[[Usuario:PCamino|PCamino]]

- Duda: ¿Por que el proceso C se ejecuta en el instante 11 habiendo sido bloqueado en el 10?,se supone que todos los procesos tienen un tiempo de bloqueo de 2 unidades

El proceso C no se bloquea nunca (o al menos en el enunciado no lo pone), por eso se ejecuta cada vez que puede. Me refiero a bloqueo por E/S, claro.

Sol-ejer2-planif-procesos

2011-06-13T16:34:05Z

Josvaldia:

= Turno rotatorio estricto =

____|_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__|

Notése que el proceso A no llega a emplear el ''quantum'' que tiene asignado, en ese caso, como indica la [[Criterios_de_planificación|teoría]], se le retira el procesador y el planificador selecciona a otro proceso. Dejar el procesador sin proceso asignado, es decir, ocioso, va contra la lógica del máximo aprovechamiento del procesador. Por ello, he retirado una solución incorrecta que aparecía en esta sección. --[[Usuario:Pneira|Pneira]] 21:15 21 mar 2011 (UTC)

Tengo una duda en este ejercicio, en la unidad de tiempo 6 cuando el planificador activa el proceso Pb, porque motivo solo le asigna una unidad de tiempo?, podria asignarle 2 no? teniendo en cuenta que el quantum = 2. Ademas el proceso B bloquea cada 3 unidades de tiempo, no entiendo porque solo le asigna una unidad y luego activa en la unidad de tiempo 7 el proceso C. LFE (Luis Fernandez Esteban)

Pues yo diría que es porque se bloquea cada 3, al igual que el A se bloquea a cada unidad. Ya llevaba 1, y con esa actividad, +2 --[[Usuario:PCamino|PCamino]]

Gracias, tienes razon ya lo entendi. LFE (Luis Fernandez Esteban)

DUDA
En t=3 llegaría el proceso Pa y el proceso Pb a la cola de estado preparado como dice en tería un proceso que se bloquea sin llegar a agotar su quantum, pasaría al final de la cola de estados preparados. Por tanto, el siguiente en ejecutarse sería Pb, puesto que Pa viene de estar bloqueado sin agotar su quantum luego pasaría al final de la cola de preparados. ¿Estoy en lo cierto?
--[[Usuario:josvaldia|josvaldia]]
= 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

| | | | | | | | | | | | | | | | | | | |
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

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

Alguien me puede explicar ¿por que de 14 a 15 no se procesa nada? AnaBarros

Creo que eso esta mal...y he visto mas fallos por ahi o eso me parece... :S Luis Fernandez Esteban

Sí lo creo como el C solo debia de empenzar en el 3 pero empienza antes. Ana Barros

Del 14 al 15 no se procesa nada porque sólo quedan los procesos A y B, pero en esa unidad de tiempo ambos están bloqueados (los bloqueos de A y B duran 2 uds. de tiempo)

= 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.

Cierto, además creo que aunque A no se bloquease, se le seguiría asignando 1 unidad de tiempo en t=1 al proceso B: Entraría el planificador, reduciría el quantum, y al no haber compensación, A pasaría de nuevo al final de la cola del turno rotatorio, dejando el procesador a B, ¿no?

- Duda: En el instante 9 no debería entrar el proceso Pb en vez de seguir el Pc??

Lo dudo, porque el bloqueo de B dura 2 unidades, así que C tiene carta libre.--[[Usuario:PCamino|PCamino]]

- Duda: ¿Por que el proceso C se ejecuta en el instante 11 habiendo sido bloqueado en el 10?,se supone que todos los procesos tienen un tiempo de bloqueo de 2 unidades

El proceso C no se bloquea nunca (o al menos en el enunciado no lo pone), por eso se ejecuta cada vez que puede. Me refiero a bloqueo por E/S, claro.

Criterios de reemplazo

2011-06-09T14:29:38Z

Josvaldia:

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].
El fallo de página se produce cuando se accede a una posición de memoria que esta descargada en disco.

nº fallos pág.
tasa fallos pág = -----------------
nº accesos pág.

También hay que tener en cuenta el contexto, si estamos en arranque en frío o en caliente, así como el cumplimiento del principio de localidad espacial y temporal.

* Arranque en frío : se dan muchos fallos de página al principio, ya que los procesos se acaban de lanzar y ninguno esta cargado en memoria principal.
* Arranque en caliente : se suponen ya cargadas las páginas de los procesos en memoria principal.

==Criterios==
Ejemplo: Secuencia de acceso a página : 2,2,3,1,1,3,4,5,1,1,2,3,4
Suponiendo arranque en frío
___1____ 2_____3_____4___
memoria principal | | | | |
de 4 marcos |_____|_____|_____|_____|

;1. Criterio de página óptima: Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.
*[[sol_1|Solución]]
;2. Criterio de página pésima: Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.
*[[sol_2|Solución]]
;3. Criterio MRU('''M'''ost '''R'''ecently '''U'''sed): Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.
*[[sol_3|Solución]]
;4. Criterio de selección estocástica (aleatoria): Consiste en seleccionar una página al azar.
;5. Criterio por orden de carga FIFO: Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

;6.Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed): Ofrece dos bits para cada página:
* bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* bit M : Se pone a 1 si la página es modificada (escritura).
Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

# R=0, M=0 .
# R=0, M=1 .
# R=1, M=0 .
# R=1, M=1 .

Claramente deben realizarse periodos de puesta a 0, que no tienen porque ser simultáneamente en R y M.

*[[sol_6|Solución]]

;7.Criterio de 2ª oportunidad: Se trata de la unión del dos criterios, FIFO más NRU sin el bit M. Tampoco se pone R a 0 periódicamente. Consiste en recorrer la cola hasta encontrar una página con R a 0 (si no hay ninguno, pues al que le toque de la cola) y los procesos que vaya encontrando con R a 1 se les pone R a 0 y se les da una segunda oportunidad poniéndolos al final de la cola (al final de todo, el nuevo elemento llegado).

*[[sol_7|Solución]]

;8.Criterio LRU ('''L'''east '''R'''ecently '''U'''sed): Criterio en contraposición al MRU. En MRU elegíamos aquella página que hubiéramos utilizado más recientemente (la primera de la pila de acceso) mientras que en LRU elegimos como página víctima lo contrario: La última página de la pila. Funciona como una FIFO (por orden de acceso) en la cual se actualizan los valores, poniéndose al final si llegan elementos que ya había en cola.

*[[sol_8|Solución]]

;Criterio del reloj: Igual que el de 2º oportunidad pero mantenemos un puntero a la ultima pagina examinada; se implementa con una lista circular, y un puntero a la ultima pagina examinada, que sera el 1º elemento que examinaremos para el reemplazo.

*[[sol_reloj|Solución]]

;9.Criterio LFU ('''L'''east '''F'''recuently '''U'''sed): Se incrementa un contador de uso por cada acceso, reseteándose si se saca el dato. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

;10.Aproximación discreta LRU: Consiste en LFU + LRU. Se usa el bit R. Se itera periódicamente sobre la lista de páginas si R = 0 entonces aumento el contador; si R está activado se desactiva y el contador se pone a cero. Ante una sustitución: prescindir de la que tiene mayor valor en el contador. Ojito! Cuando llega un elemento, el contador se inicializa a 0, puesto que solo se modifica en los checkpoints, no con cada acceso

*[[sol_9.2|Solución]]

;11.Sustitución por envejecimiento: Se emplea un registro R de n bits que se va desplazando hacia la derecha periódicamente, de forma que la página victima será la que tenga el menor valor en el registro R (en caso de empate se empleao otro criterio). Por cada acceso se pone a 1 el bit más significativo del registro R. Los LSB se pierden al desplazar.

*[[sol_10|Solución]]

En el [[Algoritmos de criterios de reemplazo|Portal de la comunidad]] se encuentran implementados algunos de los anteriores criterios como ayuda para ver su funcionamiento.
Creo que los algoritmos están bien (coinciden con las soluciones), pero si alguien decide probarlos no estaría mal que los revisase por encima. --[[Usuario:Alexrdp|Alexrdp]] 16:24 6 jun 2011 (UTC)

Error en Aproximación discreta LRU corregido--[[Usuario:josvaldia|josvaldia]]

Criterios de reemplazo

2011-06-09T14:27:36Z

Josvaldia:

Criterios de reemplazo

2011-06-07T16:56:17Z

Josvaldia:

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].
El fallo de página se produce cuando se accede a una posición de memoria que esta descargada en disco.

nº fallos pág.
tasa fallos pág = -----------------
nº accesos pág.

También hay que tener en cuenta el contexto, si estamos en arranque en frío o en caliente, así como el cumplimiento del principio de localidad espacial y temporal.

* Arranque en frío : se dan muchos fallos de página al principio, ya que los procesos se acaban de lanzar y ninguno esta cargado en memoria principal.
* Arranque en caliente : se suponen ya cargadas las páginas de los procesos en memoria principal.

==Criterios==
Ejemplo: Secuencia de acceso a página : 2,2,3,1,1,3,4,5,1,1,2,3,4
Suponiendo arranque en frío
___1____ 2_____3_____4___
memoria principal | | | | |
de 4 marcos |_____|_____|_____|_____|

;1. Criterio de página óptima: Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.
*[[sol_1|Solución]]
;2. Criterio de página pésima: Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.
*[[sol_2|Solución]]
;3. Criterio MRU('''M'''ost '''R'''ecently '''U'''sed): Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.
*[[sol_3|Solución]]
;4. Criterio de selección estocástica (aleatoria): Consiste en seleccionar una página al azar.
;5. Criterio por orden de carga FIFO: Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

;6.Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed): Ofrece dos bits para cada página:
* bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* bit M : Se pone a 1 si la página es modificada (escritura).
Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

# R=0, M=0 .
# R=0, M=1 .
# R=1, M=0 .
# R=1, M=1 .

Claramente deben realizarse periodos de puesta a 0, que no tienen porque ser simultáneamente en R y M.

*[[sol_6|Solución]]

;7.Criterio de 2ª oportunidad: Se trata de la unión del dos criterios, FIFO más NRU sin el bit M. Tampoco se pone R a 0 periódicamente. Consiste en recorrer la cola hasta encontrar una página con R a 0 (si no hay ninguno, pues al que le toque de la cola) y los procesos que vaya encontrando con R a 1 se les pone R a 0 y se les da una segunda oportunidad poniéndolos al final de la cola (al final de todo, el nuevo elemento llegado).

*[[sol_7|Solución]]

;8.Criterio LRU ('''L'''east '''R'''ecently '''U'''sed): Criterio en contraposición al MRU. En MRU elegíamos aquella página que hubiéramos utilizado más recientemente (la primera de la pila de acceso) mientras que en LRU elegimos como página víctima lo contrario: La última página de la pila. Funciona como una FIFO (por orden de acceso) en la cual se actualizan los valores, poniéndose al final si llegan elementos que ya había en cola.

*[[sol_8|Solución]]

;Criterio del reloj: Igual que el de 2º oportunidad pero mantenemos un puntero a la ultima pagina examinada; se implementa con una lista circular, y un puntero a la ultima pagina examinada, que sera el 1º elemento que examinaremos para el reemplazo.

*[[sol_reloj|Solución]]

;9.Criterio LFU ('''L'''east '''F'''recuently '''U'''sed): Se incrementa un contador de uso por cada acceso. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

;10.Aproximación discreta LRU: Consiste en LRU + LFU. Se usa el bit R. Se itera periódicamente sobre la lista de páginas si R = 0 entonces aumento el contador; si R está activado se desactiva y el contador se pone a cero.

*[[sol_9.2|Solución]]

;11.Sustitución por envejecimiento: Se emplea un registro R de n bits que se va desplazando hacia la derecha periódicamente, de forma que la página victima será la que tenga el menor valor en el registro R (en caso de empate se empleao otro criterio). Por cada acceso se pone a 1 el bit más significativo del registro R. Los LSB se pierden al desplazar.

*[[sol_10|Solución]]

En el [[Algoritmos de criterios de reemplazo|Portal de la comunidad]] se encuentran implementados algunos de los anteriores criterios como ayuda para ver su funcionamiento.
Creo que los algoritmos están bien (coinciden con las soluciones), pero si alguien decide probarlos no estaría mal que los revisase por encima. --[[Usuario:Alexrdp|Alexrdp]] 16:24 6 jun 2011 (UTC)

--[[Usuario:josvaldia|josvaldia]]Acabo de encontrar un error en los apuntes. En el libro de SS.OO: en aproximacion discreta del LRU en cada exploración, si el bit Restá desactivado, se pone el contador a cero y se desactiva el bit. Cuando hay que sacrificar una página, se elimina aquella cuyo contador tenga el valor mayor. Desde luego fallos de este tipo en los apuntes de una asignatura el dia antes del examen, no se pueden permitir.

Criterios de reemplazo

2011-06-07T16:53:15Z

Josvaldia:

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].
El fallo de página se produce cuando se accede a una posición de memoria que esta descargada en disco.

nº fallos pág.
tasa fallos pág = -----------------
nº accesos pág.

También hay que tener en cuenta el contexto, si estamos en arranque en frío o en caliente, así como el cumplimiento del principio de localidad espacial y temporal.

* Arranque en frío : se dan muchos fallos de página al principio, ya que los procesos se acaban de lanzar y ninguno esta cargado en memoria principal.
* Arranque en caliente : se suponen ya cargadas las páginas de los procesos en memoria principal.

==Criterios==
Ejemplo: Secuencia de acceso a página : 2,2,3,1,1,3,4,5,1,1,2,3,4
Suponiendo arranque en frío
___1____ 2_____3_____4___
memoria principal | | | | |
de 4 marcos |_____|_____|_____|_____|

;1. Criterio de página óptima: Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.
*[[sol_1|Solución]]
;2. Criterio de página pésima: Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.
*[[sol_2|Solución]]
;3. Criterio MRU('''M'''ost '''R'''ecently '''U'''sed): Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.
*[[sol_3|Solución]]
;4. Criterio de selección estocástica (aleatoria): Consiste en seleccionar una página al azar.
;5. Criterio por orden de carga FIFO: Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

;6.Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed): Ofrece dos bits para cada página:
* bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* bit M : Se pone a 1 si la página es modificada (escritura).
Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

# R=0, M=0 .
# R=0, M=1 .
# R=1, M=0 .
# R=1, M=1 .

Claramente deben realizarse periodos de puesta a 0, que no tienen porque ser simultáneamente en R y M.

*[[sol_6|Solución]]

;7.Criterio de 2ª oportunidad: Se trata de la unión del dos criterios, FIFO más NRU sin el bit M. Tampoco se pone R a 0 periódicamente. Consiste en recorrer la cola hasta encontrar una página con R a 0 (si no hay ninguno, pues al que le toque de la cola) y los procesos que vaya encontrando con R a 1 se les pone R a 0 y se les da una segunda oportunidad poniéndolos al final de la cola (al final de todo, el nuevo elemento llegado).

*[[sol_7|Solución]]

;8.Criterio LRU ('''L'''east '''R'''ecently '''U'''sed): Criterio en contraposición al MRU. En MRU elegíamos aquella página que hubiéramos utilizado más recientemente (la primera de la pila de acceso) mientras que en LRU elegimos como página víctima lo contrario: La última página de la pila. Funciona como una FIFO (por orden de acceso) en la cual se actualizan los valores, poniéndose al final si llegan elementos que ya había en cola.

*[[sol_8|Solución]]

;Criterio del reloj: Igual que el de 2º oportunidad pero mantenemos un puntero a la ultima pagina examinada; se implementa con una lista circular, y un puntero a la ultima pagina examinada, que sera el 1º elemento que examinaremos para el reemplazo.

*[[sol_reloj|Solución]]

;9.Criterio LFU ('''L'''east '''F'''recuently '''U'''sed): Se incrementa un contador de uso por cada acceso. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

;10.Aproximación discreta LRU: Consiste en LRU + LFU. Se usa el bit R. Se itera periódicamente sobre la lista de páginas si R = 1 entonces aumento el contador y pongo R a 0.

*[[sol_9.2|Solución]]

;11.Sustitución por envejecimiento: Se emplea un registro R de n bits que se va desplazando hacia la derecha periódicamente, de forma que la página victima será la que tenga el menor valor en el registro R (en caso de empate se empleao otro criterio). Por cada acceso se pone a 1 el bit más significativo del registro R. Los LSB se pierden al desplazar.

*[[sol_10|Solución]]

En el [[Algoritmos de criterios de reemplazo|Portal de la comunidad]] se encuentran implementados algunos de los anteriores criterios como ayuda para ver su funcionamiento.
Creo que los algoritmos están bien (coinciden con las soluciones), pero si alguien decide probarlos no estaría mal que los revisase por encima. --[[Usuario:Alexrdp|Alexrdp]] 16:24 6 jun 2011 (UTC)

--[[Usuario:josvaldia|josvaldia]]Acabo de encontrar un error en los apuntes. En el libro de SS.OO: en aproximacion discreta del LRU en cada exploración, si el bit Restá desactivado, se pone el contador a cero y se desactiva el bit. Cuando hay que sacrificar una página, se elimina aquella cuyo contador tenga el valor mayor. Desde luego fallos de este tipo en los apuntes de una asignatura el dia antes del examen, no se pueden permitir.

Sol 7

2011-06-07T15:17:46Z

Josvaldia:

La lista de paginas a la que se acceden son las siguientes :

2--2--3--1--1--3--4--5--1--1--2--3--4

___1____ 2_____3_____4___
1º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1 Cola = 2-
Pagina 2 |_R=1_|_R=0_|_R=0_|_R=0_|
2º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1 Cola = 2-
Pagina 2 |_R=1_|_R=0_|_R=0_|_R=0_|
3º Acceso | | | | |
Acceso a: | 2 | 3 | | | Nª de fallos: 2 Cola = 2-3
Pagina 3 |_R=1_|_R=1_|_R=0_|_R=0_|
4º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-3-1
Pagina 1 |_R=1_|_R=1_|_R=1_|_R=0_|
5º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-3-1
Pagina 1 |_R=1_|_R=1_|_R=1_|_R=0_|
6º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-1-3
Pagina 3 |_R=1_|_R=1_|_R=1_|_R=0_|
7º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | 4 | Nª de fallos: 4 Cola = 2-1-3-4
Pagina 4 |_R=1_|_R=1_|_R=1_|_R=1_|
8º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 1-3-4-5
Pagina 5 |_R=1_|_R=0_|_R=0_|_R=0_|
9º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 3-4-5-1
Pagina 1 |_R=1_|_R=0_|_R=1_|_R=0_|
10º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 3-4-5-1
Pagina 1 |_R=1_|_R=0_|_R=1_|_R=0_|
11º Acceso | | | | |
Acceso a: | 5 | 2 | 1 | 4 | Nª de fallos: 6 Cola = 4-5-1-2
Pagina 2 |_R=1_|_R=1_|_R=1_|_R=0_|
12º Acceso | | | | |
Acceso a: | 5 | 2 | 1 | 3 | Nª de fallos: 7 Cola = 5-1-2-3
Pagina 3 |_R=1_|_R=1_|_R=1_|_R=1_|
13º Acceso | | | | |
Acceso a: | 4 | 2 | 1 | 3 | Nª de fallos: 8 Cola = 1-2-3-4
Pagina 4 |_R=1_|_R=0_|_R=0_|_R=0_|

--[[Usuario:Fcoramlop|Fcoramlop]] 22:58 4 jun 2011 (UTC)
8
tasa fallos pág = ---- = 0,615
13

-----------------------------------------------------------------------------------------------
Segunda solución posible.
___1____ 2_____3_____4___
1º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1 Cola = 2-
Pagina 2 |_R=1_|_R=0_|_R=0_|_R=0_|
2º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1 Cola = 2-
Pagina 2 |_R=1_|_R=0_|_R=0_|_R=0_|
3º Acceso | | | | |
Acceso a: | 2 | 3 | | | Nª de fallos: 2 Cola = 2-3
Pagina 3 |_R=1_|_R=1_|_R=0_|_R=0_|
4º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-3-1
Pagina 1 |_R=1_|_R=1_|_R=1_|_R=0_|
5º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-3-1
Pagina 1 |_R=1_|_R=1_|_R=1_|_R=0_|
6º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-3-1
Pagina 3 |_R=1_|_R=1_|_R=1_|_R=0_|
7º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | 4 | Nª de fallos: 4 Cola = 2-3-1-4
Pagina 4 |_R=1_|_R=1_|_R=1_|_R=1_|
8º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 3-1-4-5
Pagina 5 |_R=1_|_R=0_|_R=0_|_R=0_|
9º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 3-1-4-5
Pagina 1 |_R=1_|_R=0_|_R=1_|_R=0_|
10º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 3-1-4-5
Pagina 1 |_R=1_|_R=0_|_R=1_|_R=0_|
11º Acceso | | | | |
Acceso a: | 5 | 2 | 1 | 4 | Nª de fallos: 6 Cola = 1-4-5-2
Pagina 2 |_R=1_|_R=1_|_R=1_|_R=0_|
12º Acceso | | | | |
Acceso a: | 5 | 2 | 1 | 3 | Nª de fallos: 7 Cola = 5-2-1-3
Pagina 3 |_R=1_|_R=1_|_R=1_|_R=1_|
13º Acceso | | | | |
Acceso a: | 4 | 2 | 1 | 3 | Nª de fallos: 8 Cola = 2-1-3-4
Pagina 4 |_R=1_|_R=0_|_R=0_|_R=0_|
--[[Usuario:josvaldia|josvaldia]] 17:17 07/06/2011

- Duda: En el acceso nº6 ¿Por que ponemos el 3 al final de la cola? se supone que solo se hace eso si recorremos la cola y el bit R se encuentra a 1, entonces ponemos el bit a 0 y colocamos la pagina al final de la cola para darle una 2º oportunidad

<[[Usuario:PCamino|pablo]]>-Respuesta a la duda: Porque asi funcionan las colas. Si llega un elemento que ya habia, pues le corresponde ponerse al final...o no?

[[Usuario:alberto|alberto]] --->En el acceso 11 , el R de 5 debería de estar a 0 , puesto que al meter 2 vamos recorriendo para encontrar algún R a 0(En este caso sustituimos 3 que tiene su R a 0) y además si durante esa búsqueda encontramos algún R=1 , debemos ponerlo a 0 y ponerlo al final de la cola para darle una segunda oportunidad. Por tanto pienso que el acceso 11 quedaría: 5(0) 2(1) 1(1) 4(0) Cola=4-1-5-2

- Respuesta 2 a duda: Pienso que en el acceso 6 no debemos tocar las posiciones de la cola, ya que la cola sólo se toca cuando ocurre un reemplazo. En este caso no es como lo hacíamos con el planificador,que teníamos que elegir según el orden para darle paso a un proceso, sino que en este caso ya tenemos un orden de páginas preestablecido. Por tanto, aunque vuelva a aparecer el 3, su posición en la cola no cambia, ya que ésta lo que indica es el orden en el que apareció por primera vez. Claro que también debemos tener en cuenta la puesta a cero cuando recorremos la cola, pero en el acceso 6 todavía no la hemos recorrido,ya que no se ha sucedido ningún reemplazo. Por favor, corríjanme si me equivoco, pero estoy bastante seguro de que lo que he escrito es cierto.[[Usuario:JCGarrido|JCGarrido]]

[[Usuario:josvaldia|josvaldia]] Con respecto a la duda en el acceso 6, en los apuntes de M.Robayo dicen que se añaden al final de la lista las paginas recintemente cargadas. En este caso, '3' ya estaba cargada desde el acceso nº 3, luego no hay que añadirla al final de la cola.

[[Usuario:Ajaest|ajaest]] 15:10 7 jun 2011 (UTC) Creo que todos coincidimos en que en el acceso 6 no hay que poner '3' al final del la cola, alguien cree que no debería cambiarse?

[[Criterios_de_reemplazo|Volver]]

Sol 7

2011-06-07T15:16:55Z

Josvaldia:

La lista de paginas a la que se acceden son las siguientes :

2--2--3--1--1--3--4--5--1--1--2--3--4

___1____ 2_____3_____4___
1º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1 Cola = 2-
Pagina 2 |_R=1_|_R=0_|_R=0_|_R=0_|
2º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1 Cola = 2-
Pagina 2 |_R=1_|_R=0_|_R=0_|_R=0_|
3º Acceso | | | | |
Acceso a: | 2 | 3 | | | Nª de fallos: 2 Cola = 2-3
Pagina 3 |_R=1_|_R=1_|_R=0_|_R=0_|
4º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-3-1
Pagina 1 |_R=1_|_R=1_|_R=1_|_R=0_|
5º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-3-1
Pagina 1 |_R=1_|_R=1_|_R=1_|_R=0_|
6º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-1-3
Pagina 3 |_R=1_|_R=1_|_R=1_|_R=0_|
7º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | 4 | Nª de fallos: 4 Cola = 2-1-3-4
Pagina 4 |_R=1_|_R=1_|_R=1_|_R=1_|
8º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 1-3-4-5
Pagina 5 |_R=1_|_R=0_|_R=0_|_R=0_|
9º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 3-4-5-1
Pagina 1 |_R=1_|_R=0_|_R=1_|_R=0_|
10º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 3-4-5-1
Pagina 1 |_R=1_|_R=0_|_R=1_|_R=0_|
11º Acceso | | | | |
Acceso a: | 5 | 2 | 1 | 4 | Nª de fallos: 6 Cola = 4-5-1-2
Pagina 2 |_R=1_|_R=1_|_R=1_|_R=0_|
12º Acceso | | | | |
Acceso a: | 5 | 2 | 1 | 3 | Nª de fallos: 7 Cola = 5-1-2-3
Pagina 3 |_R=1_|_R=1_|_R=1_|_R=1_|
13º Acceso | | | | |
Acceso a: | 4 | 2 | 1 | 3 | Nª de fallos: 8 Cola = 1-2-3-4
Pagina 4 |_R=1_|_R=0_|_R=0_|_R=0_|

--[[Usuario:Fcoramlop|Fcoramlop]] 22:58 4 jun 2011 (UTC)
8
tasa fallos pág = ---- = 0,615
13

-----------------------------------------------------------------------------------------------
Segunda solución posible.
___1____ 2_____3_____4___
1º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1 Cola = 2-
Pagina 2 |_R=1_|_R=0_|_R=0_|_R=0_|
2º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1 Cola = 2-
Pagina 2 |_R=1_|_R=0_|_R=0_|_R=0_|
3º Acceso | | | | |
Acceso a: | 2 | 3 | | | Nª de fallos: 2 Cola = 2-3
Pagina 3 |_R=1_|_R=1_|_R=0_|_R=0_|
4º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-3-1
Pagina 1 |_R=1_|_R=1_|_R=1_|_R=0_|
5º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-3-1
Pagina 1 |_R=1_|_R=1_|_R=1_|_R=0_|
6º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3 Cola = 2-3-1
Pagina 3 |_R=1_|_R=1_|_R=1_|_R=0_|
7º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | 4 | Nª de fallos: 4 Cola = 2-3-1-4
Pagina 4 |_R=1_|_R=1_|_R=1_|_R=1_|
8º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 3-1-4-5
Pagina 5 |_R=1_|_R=0_|_R=0_|_R=0_|
9º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 3-1-4-5
Pagina 1 |_R=1_|_R=0_|_R=1_|_R=0_|
10º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5 Cola = 3-1-4-5
Pagina 1 |_R=1_|_R=0_|_R=1_|_R=0_|
11º Acceso | | | | |
Acceso a: | 5 | 2 | 1 | 4 | Nª de fallos: 6 Cola = 1-4-5-2
Pagina 2 |_R=1_|_R=1_|_R=1_|_R=0_|
12º Acceso | | | | |
Acceso a: | 5 | 2 | 1 | 3 | Nª de fallos: 7 Cola = 5-2-1-3
Pagina 3 |_R=1_|_R=1_|_R=1_|_R=1_|
13º Acceso | | | | |
Acceso a: | 4 | 2 | 1 | 3 | Nª de fallos: 8 Cola = 2-1-3-4
Pagina 4 |_R=1_|_R=0_|_R=0_|_R=0_|
--[[Usuario:josvaldia|josvaldia]] 22:58 4 jun 2011 (UTC)

- Duda: En el acceso nº6 ¿Por que ponemos el 3 al final de la cola? se supone que solo se hace eso si recorremos la cola y el bit R se encuentra a 1, entonces ponemos el bit a 0 y colocamos la pagina al final de la cola para darle una 2º oportunidad

<[[Usuario:PCamino|pablo]]>-Respuesta a la duda: Porque asi funcionan las colas. Si llega un elemento que ya habia, pues le corresponde ponerse al final...o no?

[[Usuario:alberto|alberto]] --->En el acceso 11 , el R de 5 debería de estar a 0 , puesto que al meter 2 vamos recorriendo para encontrar algún R a 0(En este caso sustituimos 3 que tiene su R a 0) y además si durante esa búsqueda encontramos algún R=1 , debemos ponerlo a 0 y ponerlo al final de la cola para darle una segunda oportunidad. Por tanto pienso que el acceso 11 quedaría: 5(0) 2(1) 1(1) 4(0) Cola=4-1-5-2

- Respuesta 2 a duda: Pienso que en el acceso 6 no debemos tocar las posiciones de la cola, ya que la cola sólo se toca cuando ocurre un reemplazo. En este caso no es como lo hacíamos con el planificador,que teníamos que elegir según el orden para darle paso a un proceso, sino que en este caso ya tenemos un orden de páginas preestablecido. Por tanto, aunque vuelva a aparecer el 3, su posición en la cola no cambia, ya que ésta lo que indica es el orden en el que apareció por primera vez. Claro que también debemos tener en cuenta la puesta a cero cuando recorremos la cola, pero en el acceso 6 todavía no la hemos recorrido,ya que no se ha sucedido ningún reemplazo. Por favor, corríjanme si me equivoco, pero estoy bastante seguro de que lo que he escrito es cierto.[[Usuario:JCGarrido|JCGarrido]]

[[Usuario:josvaldia|josvaldia]] Con respecto a la duda en el acceso 6, en los apuntes de M.Robayo dicen que se añaden al final de la lista las paginas recintemente cargadas. En este caso, '3' ya estaba cargada desde el acceso nº 3, luego no hay que añadirla al final de la cola.

[[Usuario:Ajaest|ajaest]] 15:10 7 jun 2011 (UTC) Creo que todos coincidimos en que en el acceso 6 no hay que poner '3' al final del la cola, alguien cree que no debería cambiarse?

[[Criterios_de_reemplazo|Volver]]

Sol 7

2011-06-07T15:00:11Z

Josvaldia:

Usuario:Josvaldia

2011-06-07T14:58:42Z

Josvaldia: Página creada con 'José Luis Vallejo Diaz. Saludos desde mi perfil.'

José Luis Vallejo Diaz.
Saludos desde mi perfil.

Sol 7

2011-06-07T14:57:38Z

Josvaldia:

Ejercicios sincronización y comunicación

2011-05-16T19:09:34Z

Josvaldia:

= Ejercicio 1 =

Realice el cronograma temporal que represente la ejecución de dos procesos P1 y P2. El proceso P1 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
down(s1); /* #2 */
f1(); /* #3 */
if (get(s1) == 0) /* #4 */
up(s2); /* #5 */
}
</source>

Y el proceso P2 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
down(s2); /* #2 */
f2(); /* #3 */
up(s1); /* #4 */
}
</source>

Para el semáforo s1 el contador vale 1, mientras que para el semáforo s2 el contador vale 0.

Suponga que:

* El planificador emplea turno rotatorio estricto con quantum de 3 unidades de ejecución.
* Se sabe que el proceso P2 es seleccionado en primer lugar por el planificador para ejecutarse.
* La ejecución de cada línea de código representado anteriormente supone una unidad de ejecución, por tanto, todas las instrucciones toman el mismo tiempo de ejecución.
* La función get(semáforo s) devuelve el valor del contador del semáforo.

El cronograma deberá incluir qué instrucción se ejecuta en cada unidad de ejecución.

[[solución ejercicio 1|Ver solución del ejercicio 1]]

= Ejercicio 2 =

Realice el cronograma temporal que represente la ejecución de dos procesos P1 y P2. El proceso P1 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
down(s1); /* #2 */
f1(); /* #3 */
up(s2); /* #4 */
}
</source>

Y el proceso P2 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
down(s2); /* #2 */
f2(); /* #3 */
up(s1); /* #4 */
}
</source>

Para el semáforo s1 el contador vale 1, mientras que para el semáforo s2 el contador vale 0.

Suponga que:

* El planificador emplea turno rotatorio estricto con quantum de 3 unidades de ejecución.
* Se sabe que el proceso P1 es seleccionado en primer lugar por el planificador para ejecutarse.
* La ejecución de cada línea de código representado anteriormente supone una unidad de ejecución, por tanto, todas las instrucciones toman el mismo tiempo de ejecución.

El cronograma deberá incluir qué instrucción se ejecuta en cada unidad de ejecución.

[[solución ejercicio 2|Ver solución del ejercicio 2]]

= Ejercicio 3 =

En un exámen de sistemas operativos, un estudiante plantea la siguiente solución basada en dos procesos, un proceso P1 productor y un proceso P2 consumidor, en el que el contador de los semáforos s1 y s2 valen inicialmente 0.

<source lang="c">
while(1) {
down(s1);
produce();
up(s2);
}
</source>

Y el proceso P2 ejecuta el siguiente código:

<source lang="c">
while(1) {
down(s2);
consume();
up(s1);
}
</source>

Responda brevemente si la solución que propone es idónea justificando su respuesta.

[[solución ejercicio 3|Ver solución del ejercicio 3]]

= Ejercicio 4 =

Realice el cronograma temporal que represente la ejecución de dos procesos P1 y P2. El proceso P1 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
send(msg); /* #2 */
recv(msg); /* #3 */
}
</source>

Y el proceso P2 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
recv(msg); /* #2 */
send(msg); /* #3 */
}
</source>

Suponga que:

* El planificador emplea turno rotatorio estricto con quantum de 3 unidades de ejecución.
* Se sabe que el proceso P1 es seleccionado en primer lugar por el planificador para ejecutarse.
* La ejecución de cada línea de código representado anteriormente supone una unidad de ejecución, por tanto, todas las instrucciones toman el mismo tiempo de ejecución.
* El comportamiento de la primitiva send() es síncrono y el la primitiva recv() es bloqueante.
* Suponga que msg contiene un mensaje se emplea como testigo cuyo contenido no tiene relevancia.

El cronograma deberá incluir qué instrucción se ejecuta en cada unidad de ejecución.

[[solución ejercicio 4|Ver solución del ejercicio 4]]

= Ejercicio 5 =

Realice el cronograma temporal que represente la ejecución de dos procesos P1 y P2. El proceso P1 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
down(s1); /* #2 */
f1(); /* #3 */
up(s2); /* #4 */
}
</source>

Y el proceso P2 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
down(s2); /* #2 */
f2(); /* #3 */
up(s1); /* #4 */
}
</source>

Para el semáforo s1 el contador vale 1, mientras que para el semáforo s2 el contador vale 0.

Suponga que:

* El planificador emplea turno rotatorio estricto, con quantum ilimitado, por tanto, un proceso se mantiene en estado activo hasta que realice una operación bloqueante.
* Se sabe que el proceso P2 es seleccionado en primer lugar por el planificador para ejecutarse.
* La ejecución de cada línea de código representado anteriormente supone una unidad de ejecución, por tanto, todas las instrucciones toman el mismo tiempo de ejecución.

El cronograma deberá incluir qué instrucción se ejecuta en cada unidad de ejecución.

[[solución ejercicio 5|Ver solución del ejercicio 5]]

= Ejercicio 6 =

Dado dos procesos P1 y P2 cuyos códigos son los siguientes:

Código del Proceso 1:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
send(msg); /* #2 */
f(msg); /* #3 */
recv(msg); /* #4 */
}
</source>

Código del Proceso 2:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
recv(msg); /* #2 */
f(msg); /* #3 */
send(msg); /* #4 */
}
</source>

Suponga que:

* El planificador emplea turno rotatorio estricto con quantum de 3 unidades de ejecución.
* Se sabe que el proceso P1 es seleccionado en primer lugar por el planificador para ejecutarse.
* La ejecución de cada línea de código representado anteriormente supone una unidad de ejecución, por tanto, todas las instrucciones toman el mismo tiempo de ejecución.
* El comportamiento de la primitiva send() es asíncrono y el de la primitiva recv() es bloqueante.
* Suponga que msg contiene un mensaje inicialmente bien formado cuyo contenido no tiene relevancia

El cronograma deberá incluir qué instrucción se ejecuta en cada unidad de ejecución.

[[solución ejercicio 6|Ver solución del ejercicio 6]]

= Ejercicio 7 =

En base ados hilos h1 y h2 de un mismo proceso P cuyos codigos son los siguientes:

En el hilo h1 se ejecuta el siguiente código:

<source lang="c">
for (int i = 0; i<2; i++){ //#1
while(cerrojo_p2); //#2
cerrojo_p1 = 1; //#3
f(); //#4
cerrojo_p1 = 0; //#5

}
</source>

<source lang="c">
for (int i = 0; i<2; i++){ //#1
while(cerrojo_p1); //#2
cerrojo_p2 = 1; //#3
f(); //#4
cerrojo_p2 = 0; //#5

}
</source>
Proponga una solución en la que se reemplacen los cerrojos por semáforos. Realice el cronograma temporal de ejecución de la solución que propone.

Siendo cerrojo_p1 y cerrojo_p2 variables globales inicialmente a cero.
Supongamos que:
*El planificador emplea turno rotatorio estricto con quantum de 3 unidades de ejecución.
*Se sabe que el hilo h1 es seleccionado en primer lugar por el planificador para ejecutarse.
*La ejecución de cada línea de código representado anteriormente supone una unidad de ejecución, por tanto, todas las instrucciones toman el mismo tiempo de ejecución.
el planificador

[[solución ejercicio 7|Ver solución del ejercicio 7]]

Solución ejercicio 7

2011-05-16T19:08:00Z

Josvaldia:

Hilo h1
<source lang="c">
for (int i = 0; i<2; i++){ //#1
down(s) ; //#2
f(); //#3
up(s); //#4

}
</source>

Hilo h2

<source lang="c">
for (int i = 0; i<2; i++){ //#1
down(s) ; //#2
f(); //#3
up(s); //#4

}
</source>
X = El proceso pasa a estado bloqueado.
/ = El proceso pasa a estado preparado.
> = Fin de su ejecucion

| #1| #2| #3| | | #4| #1| #2| | | | #3| #4| #1| | | | | | |
h1|---|---|---| | |---|---|---X | / |---|---|---> | | | | | |
| | | | | | | | | | | | | | | | | | | | |
| | | | #1| #2| | | | #3| #4| #1| | | | #2| #3| #4| #1| | |
h2| | | |---|---X / | |---|---|---| | | |---|---|-------> | |
| | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Solución ejercicio 7

2011-05-16T18:45:03Z

Josvaldia: Página nueva: Hilo h1 <source lang="c"> for (int i = 0; i<2; i++){ //#1 down(s) ; //#2 f(); //#3 up(s); //#4 } </source> Hilo h2 <sourc...

Ejercicios sincronización y comunicación

2011-05-16T18:42:07Z

Josvaldia:

= Ejercicio 1 =

Realice el cronograma temporal que represente la ejecución de dos procesos P1 y P2. El proceso P1 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
down(s1); /* #2 */
f1(); /* #3 */
if (get(s1) == 0) /* #4 */
up(s2); /* #5 */
}
</source>

Y el proceso P2 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
down(s2); /* #2 */
f2(); /* #3 */
up(s1); /* #4 */
}
</source>

Para el semáforo s1 el contador vale 1, mientras que para el semáforo s2 el contador vale 0.

Suponga que:

* El planificador emplea turno rotatorio estricto con quantum de 3 unidades de ejecución.
* Se sabe que el proceso P2 es seleccionado en primer lugar por el planificador para ejecutarse.
* La ejecución de cada línea de código representado anteriormente supone una unidad de ejecución, por tanto, todas las instrucciones toman el mismo tiempo de ejecución.
* La función get(semáforo s) devuelve el valor del contador del semáforo.

El cronograma deberá incluir qué instrucción se ejecuta en cada unidad de ejecución.

[[solución ejercicio 1|Ver solución del ejercicio 1]]

= Ejercicio 2 =

Realice el cronograma temporal que represente la ejecución de dos procesos P1 y P2. El proceso P1 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
down(s1); /* #2 */
f1(); /* #3 */
up(s2); /* #4 */
}
</source>

Y el proceso P2 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
down(s2); /* #2 */
f2(); /* #3 */
up(s1); /* #4 */
}
</source>

Para el semáforo s1 el contador vale 1, mientras que para el semáforo s2 el contador vale 0.

Suponga que:

* El planificador emplea turno rotatorio estricto con quantum de 3 unidades de ejecución.
* Se sabe que el proceso P1 es seleccionado en primer lugar por el planificador para ejecutarse.
* La ejecución de cada línea de código representado anteriormente supone una unidad de ejecución, por tanto, todas las instrucciones toman el mismo tiempo de ejecución.

El cronograma deberá incluir qué instrucción se ejecuta en cada unidad de ejecución.

[[solución ejercicio 2|Ver solución del ejercicio 2]]

= Ejercicio 3 =

En un exámen de sistemas operativos, un estudiante plantea la siguiente solución basada en dos procesos, un proceso P1 productor y un proceso P2 consumidor, en el que el contador de los semáforos s1 y s2 valen inicialmente 0.

<source lang="c">
while(1) {
down(s1);
produce();
up(s2);
}
</source>

Y el proceso P2 ejecuta el siguiente código:

<source lang="c">
while(1) {
down(s2);
consume();
up(s1);
}
</source>

Responda brevemente si la solución que propone es idónea justificando su respuesta.

[[solución ejercicio 3|Ver solución del ejercicio 3]]

= Ejercicio 4 =

Realice el cronograma temporal que represente la ejecución de dos procesos P1 y P2. El proceso P1 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
send(msg); /* #2 */
recv(msg); /* #3 */
}
</source>

Y el proceso P2 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
recv(msg); /* #2 */
send(msg); /* #3 */
}
</source>

Suponga que:

* El planificador emplea turno rotatorio estricto con quantum de 3 unidades de ejecución.
* Se sabe que el proceso P1 es seleccionado en primer lugar por el planificador para ejecutarse.
* La ejecución de cada línea de código representado anteriormente supone una unidad de ejecución, por tanto, todas las instrucciones toman el mismo tiempo de ejecución.
* El comportamiento de la primitiva send() es síncrono y el la primitiva recv() es bloqueante.
* Suponga que msg contiene un mensaje se emplea como testigo cuyo contenido no tiene relevancia.

El cronograma deberá incluir qué instrucción se ejecuta en cada unidad de ejecución.

[[solución ejercicio 4|Ver solución del ejercicio 4]]

= Ejercicio 5 =

Realice el cronograma temporal que represente la ejecución de dos procesos P1 y P2. El proceso P1 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
down(s1); /* #2 */
f1(); /* #3 */
up(s2); /* #4 */
}
</source>

Y el proceso P2 ejecuta el siguiente código:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
down(s2); /* #2 */
f2(); /* #3 */
up(s1); /* #4 */
}
</source>

Para el semáforo s1 el contador vale 1, mientras que para el semáforo s2 el contador vale 0.

Suponga que:

* El planificador emplea turno rotatorio estricto, con quantum ilimitado, por tanto, un proceso se mantiene en estado activo hasta que realice una operación bloqueante.
* Se sabe que el proceso P2 es seleccionado en primer lugar por el planificador para ejecutarse.
* La ejecución de cada línea de código representado anteriormente supone una unidad de ejecución, por tanto, todas las instrucciones toman el mismo tiempo de ejecución.

El cronograma deberá incluir qué instrucción se ejecuta en cada unidad de ejecución.

[[solución ejercicio 5|Ver solución del ejercicio 5]]

= Ejercicio 6 =

Dado dos procesos P1 y P2 cuyos códigos son los siguientes:

Código del Proceso 1:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
send(msg); /* #2 */
f(msg); /* #3 */
recv(msg); /* #4 */
}
</source>

Código del Proceso 2:

<source lang="c">
for (int i=0; i<2; i++) { /* #1 */
recv(msg); /* #2 */
f(msg); /* #3 */
send(msg); /* #4 */
}
</source>

Suponga que:

* El planificador emplea turno rotatorio estricto con quantum de 3 unidades de ejecución.
* Se sabe que el proceso P1 es seleccionado en primer lugar por el planificador para ejecutarse.
* La ejecución de cada línea de código representado anteriormente supone una unidad de ejecución, por tanto, todas las instrucciones toman el mismo tiempo de ejecución.
* El comportamiento de la primitiva send() es asíncrono y el de la primitiva recv() es bloqueante.
* Suponga que msg contiene un mensaje inicialmente bien formado cuyo contenido no tiene relevancia

El cronograma deberá incluir qué instrucción se ejecuta en cada unidad de ejecución.

[[solución ejercicio 6|Ver solución del ejercicio 6]]

= Ejercicio 7 =

En base ados hilos h1 y h2 de un mismo proceso P cuyos codigos son los siguientes:
</source>
En el hilo h1 se ejecuta el siguiente código:

<source lang="c">
for (int i = 0; i<2; i++){ //#1
while(cerrojo_p2); //#2
cerrojo_p1 = 1; //#3
f(); //#4
cerrojo_p1 = 0; //#5

}
</source>

<source lang="c">
for (int i = 0; i<2; i++){ //#1
while(cerrojo_p1); //#2
cerrojo_p2 = 1; //#3
f(); //#4
cerrojo_p2 = 0; //#5

}
</source>
Proponga una solución en la que se reemplacen los cerrojos por semáforos. Realice el cronograma temporal de ejecución de la solución que propone.

Siendo cerrojo_p1 y cerrojo_p2 variables globales inicialmente a cero.
Supongamos que:
*El planificador emplea turno rotatorio estricto con quantum de 3 unidades de ejecución.
*Se sabe que el hilo h1 es seleccionado en primer lugar por el planificador para ejecutarse.
*La ejecución de cada línea de código representado anteriormente supone una unidad de ejecución, por tanto, todas las instrucciones toman el mismo tiempo de ejecución.
el planificador

[[solución ejercicio 7|Ver solución del ejercicio 7]]