Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Sol reloj

2011-06-15T13:40:15Z

Jherrera:

Sol reloj

2011-06-14T10:26:54Z

Jherrera:

Solución de los ejercicios de memoria virtual

2011-06-14T09:46:58Z

Jherrera: /* NRU */

= NRU =

En caso de empate, se emplea LRU.
accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 3 | 3 | 3 | 4 | 5 | 1 | 2 | 5 | 1 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | = | = | = | = | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | 1 | 0 | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | 3 | 3 | = | = | = | = | = | = | = | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | 1 | 0 | 1 | 1 | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 4 | = | = | 2 | = | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | | | 1 | 0 | = | = | = | = | 1 | 1 | = | = | = | = | = | = | 1 | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 5 | = | = | 5 | = | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | | | | | 1 | 0 | = | = | = | = | 1 | 1 | = | = | = | = | = | = |
---------------------------------------------------------------------------------------------------------
fallo | X | X | | | X | X | | X | | | | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

6
talla de fallos de página = ------ = 0,5
12

= Sustitución por envejecimiento =
Periodo de 4, registro R de 3 bits, desempate: LRU

_________________accesos a página__________________
|_2_|_3_|_3_|_1_||_4_|_5_|_4_|_1_||_5_|_2_|_3_|_4_|
======================================================
1 | 2 | = | = | = || 2 | 5 | = | = || 5 | = | = | = |
|100| = | = | = ||010|100| = | = ||110| = | = | = |
m---|---|---|---|---||---|---|---|---||---|---|---|---|
a 2 | | 3 | = | = || 3 | = | = | = || 3 | 2 | = | = |
r | |100| = | = ||010| = | = | = ||001|100| = | = |
c---|---|---|---|---||---|---|---|---||---|---|---|---|
o 3 | | | | 1 || 1 | = | = | 1 || 1 | = | = | 4 |
s | | | |100||010| = | = |110||011| = | = |100|
---|---|---|---|---||---|---|---|---||---|---|---|---|
4 | | | | || 4 | = | = | = || 4 | = | 3 | = |
| | | | ||100| = | = | = ||010| = |100| = |
--------------------------------------------------------> t
x x x x x x x x

8
tasa fallos pág = ----
12

Sol 7

2011-06-14T09:34:17Z

Jherrera:

___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=0_|_R=1_|
13º Acceso | | | | |
Acceso a: | 5 | 2 | 4 | 3 | Nª de fallos: 8 Cola = 2-1-3-4
Pagina 4 |_R=0_|_R=0_|_R=1_|_R=1_|

--[[Usuario:Jherrera|Jherrera]] 09:34 14 jun 2011 (UTC)

Nota:la cola que se utiliza es por orden de carga como una FIFO.

[[Criterios_de_reemplazo|Volver]]

Criterios de reemplazo

2011-06-13T19:27:54Z

Jherrera: /* Criterios */

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 puede implementar mediante una pila o cola situando la página más frecuentemente usada en la base de la pila o cabeza de la cola.La página víctima será la quede al final de la estructura. Otra variante de implementación es mediante un contador. 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-13T19:26:48Z

Jherrera: /* Criterios */

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 puede implementar mediante una pila o cola situando la página más frecuentemente usada en la base de la pila o cabeza de la cola. Otra variante de implementación es mediante un contador. 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]]

Solución de los ejercicios de memoria virtual

2011-06-13T15:05:26Z

Jherrera: /* NRU */

= NRU =

En caso de empate, se emplea LRU.
accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 3 | 3 | 3 | 4 | 5 | 1 | 2 | 5 | 1 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | = | = | = | = | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | 1 | 0 | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | 3 | 3 | = | = | = | = | = | = | = | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | 1 | 0 | 1 | 1 | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 4 | = | = | 2 | = | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | | | 1 | 0 | = | = | = | = | 1 | 1 | = | = | = | = | = | = | 1 | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 5 | = | = | 5 | = | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | | | | | 1 | 0 | = | = | = | = | 1 | 1 | = | = | = | = | = | = |
---------------------------------------------------------------------------------------------------------
fallo | X | X | | | X | X | | X | | | | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

6
talla de fallos de página = ------ = 0,4615
12

= Sustitución por envejecimiento =
Periodo de 4, registro R de 3 bits, desempate: LRU

_________________accesos a página__________________
|_2_|_3_|_3_|_1_||_4_|_5_|_4_|_1_||_5_|_2_|_3_|_4_|
======================================================
1 | 2 | = | = | = || 2 | 5 | = | = || 5 | = | = | = |
|100| = | = | = ||010|100| = | = ||110| = | = | = |
m---|---|---|---|---||---|---|---|---||---|---|---|---|
a 2 | | 3 | = | = || 3 | = | = | = || 3 | 2 | = | = |
r | |100| = | = ||010| = | = | = ||001|100| = | = |
c---|---|---|---|---||---|---|---|---||---|---|---|---|
o 3 | | | | 1 || 1 | = | = | 1 || 1 | = | = | 4 |
s | | | |100||010| = | = |110||011| = | = |100|
---|---|---|---|---||---|---|---|---||---|---|---|---|
4 | | | | || 4 | = | = | = || 4 | = | 3 | = |
| | | | ||100| = | = | = ||010| = |100| = |
--------------------------------------------------------> t
x x x x x x x x

8
tasa fallos pág = ----
12

Solución de los ejercicios de paginación y segmentación

2011-06-13T14:26:05Z

Jherrera: /* Apartado c) */

El tamaño de página es de 8KB = 2^13 B --> 13 bits para la zona de offset.

El tamaño de palabra del procesador es de 64 bits.

Conocido el offset y el tamaño de la palabra podemos obtener los bits que ocupan la zona de nº página (64 bits - 13bits).

'''DIRECCIÓN LÓGICA'''
--------------------------------------
| nº página (51 bits) | offset(13 bits)|
--------------------------------------

=Apartado a)=
Nuestra tabla de páginas tendrá tantas entradas como páginas tenga, por lo que tiene 2^51 entradas.
Si sabemos que cada entrada ocupa 128 bits (16 B =2^4 B) el tamaño de la tabla de páginas será 2^51 * 2^4 = 2^55 B

=Apartado b)=
Sabiendo el tamaño de la tabla de páginas y del tamaño de página, podemos saber cuántas páginas hay.

2^55 B / 2^13 B = 2^42 páginas = 4 Tera Páginas

=Apartado c)=

Si el proceso ocupa 7*2^20 B y cada página de la tabla de páginas ocupa 8 KB (2^13 B) tendremos :
7*2^20 B / 2^13 B = 7 * 2^7 entradas de la tabla de páginas están siendo ocupadas.

Ejercicios de paginación y segmentación

2011-06-13T14:22:18Z

Jherrera: /* Ejercicio 2 */

==Ejercicio 1==

El proceso ocupa: 1 KB de código, 4 KB de pila, 5KB ctes+globales

*Paginación pura (4KB de páginas) = 4 páginas -> 16 KB
El código requiere 1 página
La pila otra al completo
Las globales necesitan 2

*Segmentación pura = 3 segmentos, ocupan 10KB
El codigo ocupa un segmento de 1 KB
La pila uno de 4 KB
Para globales es otro de 5KB

*Combinado = 1 segmento de 4 páginas -> 16 KB

== Ejercicio 2==
''[Este ejercicio formó parte del tercer Control de Evaluación Continua del curso 2010/11, del 8 de junio de 2011]''

Suponga un sistema operativo con un administrador de memoria paginada cuyo tamaño de página es de 8KB. Se conoce que el sistema operativo funciona sobre un procesador cuyo tamaño de palabra es de 64 bits.

'''A)''' Calcule el tamaño máximo que puede llegar a alcanzar la tabla de página de un proceso, suponiendo que cada entrada de la tabla de páginas ocupa 128 bits.

'''B)''' Calcule cuántas páginas puede llegar a ocupar como máximo la tabla de páginas.

'''C)''' Dado un proceso en ejecución que requiere 7 Mbytes, calcule cuántas entradas de la tabla de páginas están siendo empleadas por dicho proceso en el sistema descrito anteriormente.

(''[[Solución de los ejercicios de paginación y segmentación#Ejercicio 2|Ver solución]]'')

PD: Podrían colocar todos los ejercicios del examen C3, y aquel que sepa las soluciones que las coloque si es tan amable.

Solución de los ejercicios de memoria virtual

2011-06-13T14:19:32Z

Jherrera: Página creada con '= NRU = En caso de empate, se emplea LRU. accesos a páginas | r | r | w | r | r | r | r …'

Ejercicios memoria virtual

2011-06-13T13:07:42Z

Jherrera: /* Ejercicio 3 */

== Ejercicio 1 ==

Dada la siguiente secuencia de accesos a páginas:

1, 1, 1, 2, 3, 4, 5, 3, 1, 2, 3, 4
r, r, w, r, r, r, r, w, w, w, r, r

Suponiendo un sistema con un administrador de memoria teórico con cuatro marcos disponibles.

Elabore el cronograma que represente la evolución de la relación páginas/marcos a lo largo del tiempo. Además, calcule la tasa de fallo de página para los siguientes criterios:

* FIFO
* NRU (considere que el periodo de puesta a cero del bit R tiende a infinito, es decir, nunca se pone a cero)
* NRU con segunda oportunidad
* LRU
* LFU
* Sustitución por envejecimiento

Ver [[solución ejercicio 1 memoria virtual|Solución]] de este ejercicio.

== Ejercicio 2 ==

Dada la siguiente secuencia de accesos a páginas:

1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6

Suponiendo un sistema con un administrador de memoria teórico con cuatro marcos disponibles.

Elabore el cronograma que represente la evolución de la relación páginas/marcos a lo largo del tiempo. Además, calcule la tasa de fallo de página para los siguientes criterios:

* MRU
* LRU

Responda brevemente, ¿cuál de los dos ofrece mejor solución en este caso? ¿por qué?

Ver [[solución ejercicio 2 memoria virtual|Solución]] de este ejercicio.

== Ejercicio 3 ==
''[Este ejercicio formó parte del tercer Control de Evaluación Continua del curso 2010/11, del 8 de junio de 2011]''

Suponga un sistema con un administrador de memoria teórico con cuatro marcos disponibles. Elabore el cronograma que represente la evolución de la relación páginas/marcos a lo largo del tiempo. Considere una situación de arranque en frío. Además, calcule la tasa de fallo de página. Todo ello para los siguientes criterios:

'''A)''' NRU (en caso de empate LRU).

{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
|+ align="center" style="background:DarkSlateBlue; color:white"|'''Acceso a página'''
!Marco
!1(r)
!3(r)
!3(w)
!3(r)
!4(r)
!5(r)
!1(r)
!2(w)
!5(w)
!1(w)
!3(r)
!4(r)
|-
|1
|
|
|
|
|
|
|
|
|
|
|
|
|-
|2
|
|
|
|
|
|
|
|
|
|
|
|
|-
|3
|
|
|
|
|
|
|
|
|
|
|
|
|-
|4
|
|
|
|
|
|
|
|
|
|
|
|
|-
|FP
|
|
|
|
|
|
|
|
|
|
|
|
|}

tasa de fallo de página=

'''B)''' Sustitución por envejecimiento (En caso de empate LRU). Úsese 3 bits de historia y considere el periodo de 4 t.

{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; width:500px; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
|+ align="center" style="background:DarkSlateBlue; color:white"|'''Acceso a página'''
!Marco
!2
!3
!3
!1
!4
!5
!4
!1
!5
!2
!3
!4
|-
|1
|
|
|
|
|
|
|
|
|
|
|
|
|-
|2
|
|
|
|
|
|
|
|
|
|
|
|
|-
|3
|
|
|
|
|
|
|
|
|
|
|
|
|-
|4
|
|
|
|
|
|
|
|
|
|
|
|
|-
|FP
|
|
|
|
|
|
|
|
|
|
|
|
|}

tasa de fallos de página=

(''[[Solución de los ejercicios de memoria virtual#Ejercicio 3|Ver solución]]'')

PD: Podrian colocar todos los ejercicios del examen C3, y aquel que sepa las soluciones que las coloque si es tan amable

Sol reloj

2011-06-13T13:03:14Z

Jherrera:

Sol reloj

2011-06-13T10:44:44Z

Jherrera:

_________________accesos a página____________________
|_2_|_2_|_3_|_1_|_1_|_3_|_4_|_5_|_1_|_1_|_2_|_3_|_4_|
========================================================
1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 5 | 5 | 5 | 5 | 5 | 5 |
| | | | | | | | | | | | | |
m---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a 2 | | | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 |
r | | | | | | | | | | | | | |
c---|---|---|---|---|---|---|---|---|---|---|---|---|---|
o 3 | | | | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 4 |
s | | | | | | | | | | | | | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
4 | | | | | | | 4 | 4 | 4 | 4 | 4 | 3 | 3 |
| | | | | | | | | | | | | |
------------------------------------------------------------> t

7
tasa fallos pág = ---- = 0,615
13
Esta solución es la correcta aunque habría que añadirle el estado del bit R. Según en los apuntes de M.Rovayo se implementa como una cola circular con un puntero que señala a la última exploración realizada (NO A LA ÚLTIMA PÁGINA EXAMINADA). En esta cola solo se desplaza el puntero(que indica la página víctima). En el momento que llega la página 5 ,la cola está de la siguiente forma :
----
2(R=1)->3(R=1)->1(R=1)->4(R=1)
^ luego da una vuelta cambiando todos los bits R a 0 y el primero
| que se encuentra es de nuevo el 2, luego lo cambia por el 5.--[[Usuario:Jherrera|Jherrera]] 10:44 13 jun 2011 (UTC)

Creo que la tasa es de 8/13, que coincidiría con el criterio de segunda oportunidad. --[[Usuario:Lcarlosp|Lcarlosp]] 12:26 6 jun 2011 (UTC)

¿Está bien esta solución? Si el puntero señala el último marco utilizado (el 4), cuando viene el 5 habría que quitar el 4:

2(R=1)->3(R=1)->1(R=1)->4(R=1) Se implementa con una lista circular y el puntero señala el 4,
^ | luego da una vuelta cambiando todos los bits R a 0 y el primero
| | que se encuentra es de nuevo el 4, luego lo cambia por el 5.
-------------------------
--[[Usuario:Robertomartin|Robertomartin]] 08:29 7 jun 2011 (UTC)

----
_________________accesos a página____________________
|_2_|_2_|_3_|_1_|_1_|_3_|_4_|_5_|_1_|_1_|_2_|_3_|_4_|
========================================================
1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
R=| 1 | = | = | = | = | = | = | = | = | = | 1 | = | 0 |
m---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a 2 | | | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 4 |
r R=| | | 1 | = | = | = | = | 0 | = | = | = | 1 | 1 |
c---|---|---|---|---|---|---|---|---|---|---|---|---|---|
o 3 | | | | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
s R=| | | | 1 | = | = | = | 0 | 1 | = | = | = | 0 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
4 | | | | | | | 4 | 5 | 5 | 5 | 5 | 5 | 5 |
R=| | | | | | | 1 | 1 | = | = | = | = | 0 |
------------------------------------------------------------> t
creo que esta seria la solucion correcta, el puntero, en las situaciones criticas, esta apuntando a 4 que como dice Roberto se recorre la lista poniendo los bits a 0 y despues se sustituye por el 5, con bit a 1; y en la otra situación critica, cuando llega el ultimo 4, el puntero apunta a 3 y repitiendo la misma operacion de antes se sustituye por el 3.--[[Usuario:Jmf bsk|Jmf bsk]] 16:09 7 jun 2011 (UTC)

[[Criterios_de_reemplazo|Volver]]

Sol reloj

2011-06-13T10:44:00Z

Jherrera:

_________________accesos a página____________________
|_2_|_2_|_3_|_1_|_1_|_3_|_4_|_5_|_1_|_1_|_2_|_3_|_4_|
========================================================
1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 5 | 5 | 5 | 5 | 5 | 5 |
| | | | | | | | | | | | | |
m---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a 2 | | | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 2 | 2 | 2 |
r | | | | | | | | | | | | | |
c---|---|---|---|---|---|---|---|---|---|---|---|---|---|
o 3 | | | | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 4 |
s | | | | | | | | | | | | | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
4 | | | | | | | 4 | 4 | 4 | 4 | 4 | 3 | 3 |
| | | | | | | | | | | | | |
------------------------------------------------------------> t

7
tasa fallos pág = ---- = 0,615
13
Esta solución es la correcta aunque habría que añadirle el estado del bit R. Según en los apuntes de M.Rovayo se implementa como una cola circular con un puntero que señala a la última exploración realizada (NO A LA ÚLTIMA PÁGINA EXAMINADA). En esta cola solo se desplaza el puntero(que indica la página víctima). En el momento que llega la página 5 ,la cola está de la siguiente forma :
----
2(R=1)->3(R=1)->1(R=1)->4(R=1)
^ luego da una vuelta cambiando todos los bits R a 0 y el primero
| que se encuentra es de nuevo el 2, luego lo cambia por el 5.

Creo que la tasa es de 8/13, que coincidiría con el criterio de segunda oportunidad. --[[Usuario:Lcarlosp|Lcarlosp]] 12:26 6 jun 2011 (UTC)

¿Está bien esta solución? Si el puntero señala el último marco utilizado (el 4), cuando viene el 5 habría que quitar el 4:

2(R=1)->3(R=1)->1(R=1)->4(R=1) Se implementa con una lista circular y el puntero señala el 4,
^ | luego da una vuelta cambiando todos los bits R a 0 y el primero
| | que se encuentra es de nuevo el 4, luego lo cambia por el 5.
-------------------------
--[[Usuario:Robertomartin|Robertomartin]] 08:29 7 jun 2011 (UTC)

----
_________________accesos a página____________________
|_2_|_2_|_3_|_1_|_1_|_3_|_4_|_5_|_1_|_1_|_2_|_3_|_4_|
========================================================
1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
R=| 1 | = | = | = | = | = | = | = | = | = | 1 | = | 0 |
m---|---|---|---|---|---|---|---|---|---|---|---|---|---|
a 2 | | | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 3 | 4 |
r R=| | | 1 | = | = | = | = | 0 | = | = | = | 1 | 1 |
c---|---|---|---|---|---|---|---|---|---|---|---|---|---|
o 3 | | | | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
s R=| | | | 1 | = | = | = | 0 | 1 | = | = | = | 0 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
4 | | | | | | | 4 | 5 | 5 | 5 | 5 | 5 | 5 |
R=| | | | | | | 1 | 1 | = | = | = | = | 0 |
------------------------------------------------------------> t
creo que esta seria la solucion correcta, el puntero, en las situaciones criticas, esta apuntando a 4 que como dice Roberto se recorre la lista poniendo los bits a 0 y despues se sustituye por el 5, con bit a 1; y en la otra situación critica, cuando llega el ultimo 4, el puntero apunta a 3 y repitiendo la misma operacion de antes se sustituye por el 3.--[[Usuario:Jmf bsk|Jmf bsk]] 16:09 7 jun 2011 (UTC)

[[Criterios_de_reemplazo|Volver]]

Solución de los ejercicios de paginación y segmentación

2011-06-12T22:17:26Z

Jherrera: Página creada con 'El tamaño de página es de 8KB = 2^13 B --> 13 bits para la zona de offset. El tamaño de palabra del procesador es de 64 bits. Conocido el offset y el tamaño de la palabra …'

El tamaño de página es de 8KB = 2^13 B --> 13 bits para la zona de offset.

El tamaño de palabra del procesador es de 64 bits.

Conocido el offset y el tamaño de la palabra podemos obtener los bits que ocupan la zona de nº página (64 bits - 13bits).

'''DIRECCIÓN LÓGICA'''
--------------------------------------
| nº página (51 bits) | offset(13 bits)|
--------------------------------------

=Apartado a)=
Nuestra tabla de páginas tendrá tantas entradas como páginas tenga, por lo que tiene 2^51 entradas.
Si sabemos que cada entrada ocupa 128 bits (16 B =2^4 B) el tamaño de la tabla de páginas será 2^51 * 2^4 = 2^55 B

=Apartado b)=
Sabiendo el tamaño de la tabla de páginas y del tamaño de página, podemos saber cuántas páginas hay.

2^55 B / 2^13 B = 2^42 páginas = 4 Tera Páginas

=Apartado c)=

Si el proceso ocupa 7*2^20 B y cada entrada de la tabla de páginas ocupa 128 bits (16 B =2^4 B) tendremos :
7*2^20 B / 2^4 B = 7 * 2^16 entradas de la tabla de páginas están siendo ocupadas.

Solución ejercicio 1 memoria virtual

2011-06-07T15:38:33Z

Jherrera: /* NRU con 2º oportunidad */

= FIFO =
accesos a páginas
-------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 |
---------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | = | = | 1 | = | = | = |
--------------------------------------------------------------------------------
| 3 | | | | | 3 | = | = | = | = | 2 | = | = |
---------------------------------------------------------------------------------
| 4 | | | | | | 4 | = | = | = | = | 3 | = |
---------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | X | X |
página -------------------------------------------------------------------------

tiempo ->

9
talla de fallos de página = ------ = 0.75
12

= NRU =

En caso de empate, se emplea LRU.
accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | = | = | = | = | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | 1 | 0 | = | = | 1 | 1 | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 5 | = | = | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | 1 | 0 | = | = | = | = | 1 | 0 | = | = | = | = | = | = | = | = | 1 | 0 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | = | 3 | = | = | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | | | 1 | 0 | = | = | = | = | 1 | 1 | = | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | = | = | = | 2 | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | | | | | 1 | 0 | = | = | = | = | = | = | 1 | 1 | = | = | = | = |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | | X | | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

7
talla de fallos de página = ------ = 0.583
12

= NRU con 2º oportunidad =

accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | 1 | = | = | = | = | = | 1 | = | = | = | = | 1 |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 2 | = | 1 | = | = | 1 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | 1 | = | = | 0 | = | 1 | = | = | 0 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | 3 | 3 | = | = | 3 | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | = | = | 1 | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | 4 | = | = | 2 | = | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | | 1 | 0 | = | = | 1 | = | 0 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

8
talla de fallos de página = ------
12

Creo que es asi, pero no me lo tomeis a pies juntillas que no estoy muy seguro.

Por favor que alguien explique bien este criterio, que en cada ejercicio se aplica de una forma diferente.Gracias

Explicación:

El criterio se basa en combinar el NRU (sin bit M) con FIFO. En la cola se van añadiendo las páginas según se cargan con su respectivo valor del bit R. A la hora de sustituir se mira el candidato de la cabecera de la cola. Si su R=1, se le da una segunda oportunidad desplazándolo al final de la cola y poniendo su bit R=0. Si hubiera tenido el R=0, se hubiera tomada esa página como víctima. Eso es lo que sucede cuando llega la página 5. En ese momento la cola es 1 2 3 4 con su bit R=1 en todas las páginas. Se va mirando el candidato si tiene el bit R=0 como no es así, pasa al final de la cola. Llega un momento en el que la página 1 vuelve a la cabecera(en este caso con R=0),por lo que ahora si es sustituida por la página 5.[[Usuario:Jherrera|Jherrera]]

= LRU =

accesos a páginas
-------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 |
---------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | = | = | 1 | = | = | = |
--------------------------------------------------------------------------------
| 3 | | | | | 3 | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------
| 4 | | | | | | 4 | = | = | = | 2 | = | = |
---------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | | X |
página -------------------------------------------------------------------------

tiempo ->

8
talla de fallos de página = ------
12

= LFU =

accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 1 | = | = | = | = | = | 1 | = | = | 1 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| C | 1 | 2 | 3 | = | = | = | = | = | 4 | = | = | 4 |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 5 | = | = | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| C | | | | 1 | = | = | 1 | = | = | = | = | 1 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | = | 3 | = | = | 3 | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| C | | | | | 1 | = | = | 2 | = | = | 3 | 3 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | = | = | = | 2 | = | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| C | | | | | | 1 | = | = | = | 1 | = | 1 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | | X | | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

7
talla de fallos de página = ------
12

Observación: al quitar un elemento se resetea su contador

= Sustitución por envejecimiento =
Periodo de 4, registro R de 3 bits, desempate: FIFO (por orden de carga)

_________________accesos a página__________________
|_1_|_1_|_1_|_2_||_3_|_4_|_5_|_3_||_1_|_2_|_3_|_4_|
======================================================
1 | 1 | = | = | = || 1 | = | 5 | 5 || 5 | = | = | 4 |
|100| = | = | = ||010| = |100|100||010| = | = |100|
m---|---|---|---|---||---|---|---|---||---|---|---|---|
a 2 | | | | 2 || 2 | = | = | = || 1 | = | = | = |
r | | | |100||010| = | = | = ||100| = | = | = |
c---|---|---|---|---||---|---|---|---||---|---|---|---|
o 3 | | | | || 3 | = | = | = || 3 | 2 | = | = |
s | | | | ||100| = | = | = ||010|100| = | = |
---|---|---|---|---||---|---|---|---||---|---|---|---|
4 | | | | || | 4 | = | = || 4 | = | 3 | = |
| | | | || |100| = | = ||010| = |100| = |
--------------------------------------------------------> t
x x x x x x x x x

9
tasa fallos pág = ----
12

Solución ejercicio 2 memoria virtual

2011-06-07T10:56:36Z

Jherrera: /* LRU */

==MRU==
accesos a páginas
-------------------------------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 3 | 4 | 5 | 6 |
---------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | = | = | = | = | = | 1 |
---------------------------------------------------------------------------------
marcos | 2 | | 2 | = | = | = | = | = | = | = | = | = | 2 |
--------------------------------------------------------------------------------
| 3 | | | 3 | = | = | = | = | = | = | 4 | 5 | 5 |
---------------------------------------------------------------------------------
| 4 | | | | 4 | 5 | 6 | = | = | = | = | = | 6 |
---------------------------------------------------------------------------------
fallo | X | X | X | X | X | X | | | | X | X | |
página -------------------------------------------------------------------------

tiempo ->

8
talla de fallos de página = ------
12

==LRU==
accesos a páginas
-------------------------------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 1 | 2 | 3 | 4 | 5 | 6 |
---------------------------------------------------------------------------------
| 1 | 1 | = | = | = | 5 | = | = | = | 3 | = | = | 3 |
---------------------------------------------------------------------------------
marcos | 2 | | 2 | = | = | = | 6 | = | = | = | 4 | = | 4 |
--------------------------------------------------------------------------------
| 3 | | | 3 | = | = | = | 1 | = | = | = | 5 | 5 |
---------------------------------------------------------------------------------
| 4 | | | | 4 | = | = | = | 2 | = | = | = | 6 |
---------------------------------------------------------------------------------
fallo | X | X | X | X | X | X | X | X | X | X | X | X |
página -------------------------------------------------------------------------

tiempo ->

12
talla de fallos de página = ------ = 1
12

Ofrece mejor resultado el MRU en esta caso porque las páginas vienen de forma secuencial. Esto repercute negativamente en el LRU porque supone que la página menos recientemente usada no va a volver a ser pedida, hecho que no ocurre en la secuencia de páginas. Por lo que estamos descargando las páginas que en futuro cercano va a volver a ser utilizado.[[Usuario:Jherrera|Jherrera]]

Solución ejercicio 2 memoria virtual

2011-06-07T10:56:11Z

Jherrera: /* LRU */

Solución ejercicio 1 memoria virtual

2011-06-07T10:36:09Z

Jherrera: /* Sustitución por envejecimiento */

= FIFO =
accesos a páginas
-------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 |
---------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | = | = | 1 | = | = | = |
--------------------------------------------------------------------------------
| 3 | | | | | 3 | = | = | = | = | 2 | = | = |
---------------------------------------------------------------------------------
| 4 | | | | | | 4 | = | = | = | = | 3 | = |
---------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | X | X |
página -------------------------------------------------------------------------

tiempo ->

9
talla de fallos de página = ------ = 0.75
12

= NRU =

En caso de empate, se emplea LRU.
accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | = | = | = | = | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | 1 | 0 | = | = | 1 | 1 | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 5 | = | = | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | 1 | 0 | = | = | = | = | 1 | 0 | = | = | = | = | = | = | = | = | 1 | 0 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | = | 3 | = | = | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | | | 1 | 0 | = | = | = | = | 1 | 1 | = | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | = | = | = | 2 | = | = |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | M | | | | | | | | | | | 1 | 0 | = | = | = | = | = | = | 1 | 1 | = | = | = | = |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | | X | | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

7
talla de fallos de página = ------ = 0.583
12

= NRU con 2º oportunidad =

accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | 1 | = | = | = | = | = | 1 | = | = | = | = | 1 |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 2 | = | 1 | = | = | 1 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | 1 | = | = | 0 | = | 1 | = | = | 0 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | 3 | 3 | = | = | 3 | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | = | = | 1 | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | 4 | = | = | 2 | = | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | | 1 | 0 | = | = | 1 | = | 0 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

8
talla de fallos de página = ------
12

Creo que es asi, pero no me lo tomeis a pies juntillas que no estoy muy seguro.

= LRU =

accesos a páginas
-------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------
| 1 | 1 | = | = | = | = | = | 5 | = | = | = | = | 4 |
---------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | = | = | 1 | = | = | = |
--------------------------------------------------------------------------------
| 3 | | | | | 3 | = | = | = | = | = | = | = |
---------------------------------------------------------------------------------
| 4 | | | | | | 4 | = | = | = | 2 | = | = |
---------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | | X |
página -------------------------------------------------------------------------

tiempo ->

8
talla de fallos de página = ------
12

= LFU =

accesos a páginas

| r | r | w | r | r | r | r | w | w | w | r | r |
-------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 2 | 3 | 4 | 5 | 3 | 1 | 2 | 3 | 4 |
---------------------------------------------------------------------------------------------------------
| 1 | 1 | 1 | 1 | = | = | = | = | = | 1 | = | = | 1 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| C | 1 | 2 | 3 | = | = | = | = | = | 4 | = | = | 4 |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 5 | = | = | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| C | | | | 1 | = | = | 1 | = | = | = | = | 1 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | = | 3 | = | = | 3 | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| C | | | | | 1 | = | = | 2 | = | = | 3 | 3 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | = | = | = | 2 | = | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| C | | | | | | 1 | = | = | = | 1 | = | 1 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | | X | | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

7
talla de fallos de página = ------
12

Duda!! Al quitar un elemento, se resetea su contador? yo he tomado que no..alguien sabe si debe permanecer su valor anterior?

Debería resetearse, no vamos a tener una estructura para guardar el contador de todas las páginas borradas, es una locura. --[[Usuario:Joscamsos|Joscamsos]] 08:47 7 jun 2011 (UTC)

= Sustitución por envejecimiento =

Periodo de 4, registro R de 3 bits, desempate: FIFO

_________________accesos a página__________________
|_1_|_1_|_1_|_2_||_3_|_4_|_5_|_3_||_1_|_2_|_3_|_4_|
======================================================
1 | 1 | = | = | = || 1 | = | 5 | 5 || 5 | = | = | = |
|100| = | = | = ||010| = |100|100||010| = | = | = |
m---|---|---|---|---||---|---|---|---||---|---|---|---|
a 2 | | | | 2 || 2 | = | = | = || 1 | = | = | = |
r | | | |100||010| = | = | = ||100| = | = | = |
c---|---|---|---|---||---|---|---|---||---|---|---|---|
o 3 | | | | || 3 | = | = | = || 3 | 2 | 3 | = |
s | | | | ||100| = | = | = ||010|100|100| = |
---|---|---|---|---||---|---|---|---||---|---|---|---|
4 | | | | || | 4 | = | = || 4 | = | = | 4 |
| | | | || |100| = | = ||010| = | = |110|
--------------------------------------------------------> t
x x x x x x x x

8
tasa fallos pág = ----
13

El fallo está en las dos últimas páginas. A la hora de cargar la página 3, las candidatas son 4 y 5 (ya que tienen el menor número) y por orden de carga se tendría que sustituir la página 4. Luego en la última tendría que ser sustituida la 5. Resumiendo, lo correcto es como está hecho en el de abajo.[[Usuario:Jherrera|Jherrera]]

= Sustitución por envejecimiento 1=
Periodo de 4, registro R de 3 bits, desempate: FIFO

_________________accesos a página__________________
|_1_|_1_|_1_|_2_||_3_|_4_|_5_|_3_||_1_|_2_|_3_|_4_|
======================================================
1 | 1 | = | = | = || 1 | = | 5 | 5 || 5 | = | = | 4 |
|100| = | = | = ||010| = |100|100||010| = | = |100|
m---|---|---|---|---||---|---|---|---||---|---|---|---|
a 2 | | | | 2 || 2 | = | = | = || 1 | = | = | = |
r | | | |100||010| = | = | = ||100| = | = | = |
c---|---|---|---|---||---|---|---|---||---|---|---|---|
o 3 | | | | || 3 | = | = | = || 3 | 2 | = | = |
s | | | | ||100| = | = | = ||010|100| = | = |
---|---|---|---|---||---|---|---|---||---|---|---|---|
4 | | | | || | 4 | = | = || 4 | = | 3 | = |
| | | | || |100| = | = ||010| = |100| = |
--------------------------------------------------------> t
x x x x x x x x

9
tasa fallos pág = ----
13
Creo que está solución es correcta, la victima es el menor R, y he aplicado FIFO en caso de empate.
--[[Usuario:Marmaclar|Marmaclar]] 09:15 7 jun 2011 (UTC)

Estoy de acuerdo --[[Usuario:Robertomartin|Robertomartin]] 09:15 7 jun 2011 (UTC)
Estoy de acuerdo con esta solución. --[[Usuario:David|David]] 10:16 7 jun 2011 (UTC)

Sol reloj

2011-06-05T18:16:49Z

Jherrera:

Sol 6

2011-06-05T14:22:12Z

Jherrera: en el último acceso estaba escrito M=0 para la página 3 teniendo que ser M=1

La lista de paginas a la que se acceden son las siguientes :
''' 2(R)--2(W)--3(R)--1(R)--1(W)--3(R)--4(W)--5(R)--1(R)--1(W)--2(R)--3(W)--4(R)'''

El bit R se pone a 0 cada 4 accesos
___1__ __ 2__ __3___ __4___
1º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1
Pagina 2 |R=1M=0|R=0M=0|R=0M=0|R=0M=0|
|______|______|______|______|
2º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1
Pagina 2 |R=1M=1|R=0M=0|R=0M=0|R=0M=0|
|______|______|______|______|
3º Acceso | | | | |
Acceso a: | 2 | 3 | | | Nª de fallos: 2
Pagina 3 |R=1M=1|R=1M=0|R=0M=0|R=0M=0|
|______|______|______|______|
4º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3
Pagina 1 |R=1M=1|R=1M=0|R=1M=0|R=0M=0|
|______|______|______|______|<------------------- EL BIT R SE PONE A 0
5º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3
Pagina 1 |R=0M=1|R=0M=0|R=1M=1|R=0M=0|
|______|______|______|______|
6º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3
Pagina 3 |R=0M=1|R=1M=0|R=1M=1|R=0M=0|
|______|______|______|______|
7º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | 4 | Nª de fallos: 4
Pagina 4 |R=0M=1|R=1M=0|R=1M=1|R=1M=1|
|______|______|______|______|
8º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5
Pagina 5 |R=1M=0|R=1M=0|R=1M=1|R=1M=1|
|______|______|______|______|<------------------- EL BIT R SE PONE A 0
9º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 5
Pagina 1 |R=0M=0|R=0M=0|R=1M=1|R=0M=1|
|______|______|______|______|
10º Acceso | | | | |
Acceso a: | 5 | 3 | 1 | 4 | Nª de fallos: 6
Pagina 1 |R=0M=0|R=0M=0|R=1M=1|R=0M=1|
|______|______|______|______|
11º Acceso | | | | |
Acceso a: | 5 | 2 | 1 | 4 | Nª de fallos: 7
Pagina 2 |R=0M=0|R=1M=0|R=1M=1|R=0M=1|
|______|______|______|______|
12º Acceso | | | | |
Acceso a: | 3 | 2 | 1 | 4 | Nª de fallos: 8
Pagina 3 |R=1M=1|R=1M=0|R=1M=1|R=0M=1|
|______|______|______|______|<------------------- EL BIT R SE PONE A 0
13º Acceso | | | | |
Acceso a: | 3 | 2 | 1 | 4 | Nª de fallos: 8
Pagina 4 |R=0M=1|R=0M=0|R=0M=1|R=1M=1|
|______|______|______|______|

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

[[Criterios_de_reemplazo|Volver]]

SO multiprogramables con particiones variables

2011-05-30T09:35:52Z

Jherrera: /* Definición */

== Definición ==

En este tipo de sistemas, las particiones para cada proceso se van creando a medida que son asignadas al procesador. Tiene como ventaja principal que evitamos el desperdicio de memoria dentro de cada bloque ya que cada uno está hecho a medida para el proceso que contiene. Por el contrario, una vez que un proceso ha concluido, su partición se queda en desuso y sería necesario aplicar algoritmos de desfragmentación de memoria(supone un alto coste de rendimiento) para poder unificar todas las partes que han quedado libres y así reciclar las particiones que quedaron huérfanas. Otra forma de obtener particiones de mayor tamaño es unificar dos o más huecos adyacentes en uno sólo.

''Ejemplo:''
_ _
|_| P1 = 3KB |_| P1 = 3KB
|_| P2 = 1KB |_| P2 = 1KB
|_| P3 = 6KB => Finaliza P3 => |_| Libre = 6KB
| | | |
|_| P4 = 31KB |_| P4 = 31KB
| | | |
|_| Libre = 21KB |_| Libre = 21KB

Si un nuevo proceso P5 requiriese 24KB de memoria, no podrían serle asignados, ya que los huecos no son contiguos y para disponer de los 27KB libres en total habría que realizar previamente una desfragmentación.

== Elementos de administración ==

* '''Mapas de bits''': Dividiendo la memoria en bloques, se utiliza un bit para representar si dicho bloque está libre o asignado.

* '''Listas de control''': Se almacena en una lista el tamaño de los huecos y las posiciones de memoria entre las que se encuentran comprendidos.

== Criterios de asignación ==

* '''Primer ajuste''': Consiste en asignar el primer hueco disponible que tenga un espacio suficiente para almacenar el programa. Las dos principales desventajas son su alto desperdicio interno, y el elevado uso de las primeras posiciones de memoria. Este último inconveniente repercute negativamente en la circuitería, debido a que se produce un mayor desgaste en dichas posiciones.

* '''Siguiente ajuste''': Se continúa a partir de la posición de la última asignación realizada.Es muy probable que haya un hueco a partir de esa posición, reduciendo la longitud de la búsqueda. De esta forma se resuelve el inconveniente de usar en exceso las primeras posiciones de la memoria.

* '''Mejor ajuste''': Consiste en asignarle al proceso el hueco con menor ajuste interno. Su mayor inconveniente es su orden de complejidad (orden lineal, ''O(n)'')

* '''Peor ajuste''': Al contrario que el criterio anterior, se asigna a cada proceso el hueco con mayor ajuste interno. Tiene el mismo inconveniente en cuanto a orden de complejidad que el mejor ajuste.

* '''Ajuste rápido''': Mediante listas de control, se agrupan los huecos disponibles según su tamaño (0 < t < 10, 10 < t < 20, etc.). De esta manera, cuando se necesite un hueco, se seleccionarán los del grupo del tamaño que corresponda. En el caso de que haya varios huecos disponibles, se seleccionará uno en base a cualquiera de los criterios anteriores.

* '''Método de los compañeros''': Es una variante del ajuste rápido, en el que los huecos se dividen en potencias de 2: 21, 22, ..., 2k. No es un método usado en la práctica, ya que al realizar redondeos a potencias de 2, se produce un elevado desperdicio interno

Otro ejemplo

2011-05-30T08:42:17Z

Jherrera:

Ej: tenemos los siguientes procesos: m(P1)=6KB,m(P2)=1KB,m(P3)=3KB,m(P4)=31KB,m(P5)=30KB,m(P6)=2KB,m(P7)=4KB,m(P8)=1KB;
y una memoria de 64 KB divididos en 4 huecos como sigue:
_____
|_____| H1 = 8KB | m(P1)=6KB | H0(P1)=0 | t(P1)=8
|_____| H2 = 8KB | m(P2)=1KB | H0(P2)=0 | t(P2)=8
| | | m(P3)=3KB | H0(P3)=1 | t(P3)=2
|_____| H3 = 16KB | m(P4)=31KB | H0(P4)=0 | t(P4)=2
| | | m(P5)=30KB | H0(P5)=0 | t(P5)=2
| | | m(P6)=2KB | H0(P6)=0 | t(P6)=2
| | H4 = 32KB | m(P7)=4KB | H0(P7)=2 | t(P7)=2
|_____| | m(P8)=1KB | H0(P8)=0 | t(P8)=2

solución:
>: fin del proceso.

| P1| P1| P1| P1| P1| P1| P1| P1| |
H1|---|---|---|---|---|---|---|---> |
| | | | | | | | | |
| P6| P6| P7| P7| P3| P3| | | |
H2|---|--->---|--->---|---> | | |
| | | | | | | | | |
| P2| P2| P2| P2| P2| P2| P2| P2| |
H3|---|---|---|---|---|---|---|---> |
| | | | | | | | | |
| P4| P4| P5| P5| P8| P8| | | |
H4|---|--->---|--->---|---> | | |
|___|___|___|___|___|___|___|___|___|__>
0 1 2 3 4 5 6 7 8 9 t

Solución mejor ajuste estático

2011-05-30T08:34:34Z

Jherrera: Erratas

Solución: P1->H1, P2->H2, P3->H1/H2, P4->H4, P5->H4

P3 podrá ir a H1 o H2, la que se libere antes.
P5 se pondrá a esperar a que termine P4, mientras que este se pondrá a la cola.

SO multiprogramables con particiones fijas

2011-05-23T07:08:16Z

Jherrera:

La memoria se encuentra dividida en particiones, en cada una habrá un proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

=Estrategias=
*Cancelación: "lo siento, no hay memoria libre, prueba más tarde"
*Espera: añadir a la cola

=Limitaciones=
*Procesos partición máxima -> No se ejecuta
*Desperdicio de memoria. Por ejemplo, si los procesos son muy pequeños y las particiones grandes

=Criterios de asignación=
Se lanza un proceso, y hay que elegir a que partición va (estrategia de espera). Puede haber una cola por partición, o una sola para todas las particiones.

Ej: tenemos los siguientes procesos: m(P1) = 6KB, m(P2) = 1KB, m(P3) = 3KB, m(P4) = 31KB, m(P5) = 30KB;
y una memoria de 64 KB divididos en 4 huecos como sigue:
_
|_| H1 = 8KB
|_| H2 = 8KB
| |
|_| H3 = 16KB
| |
| |
| | H4 = 32KB
|_|

*'''Mejor ajuste estático''': se adjudica cada proceso a la menor partición que quepa. Complejidad: O(1)

[[solución mejor ajuste estático|Ver solución]]

*'''Primer ajuste''': cuando una partición queda libre, se asigna el primer proceso que quepa en ella. Complejidad: O(1)

[[solución primer ajuste|Ver solución]]

*'''Mejor ajuste dinámico''': cuando una partición queda libre, se asigna el mayor proceso que queda en ella. Complejidad: O(nlog(p))

[[solución ajuste dinámico|Ver solución]]

*'''Mejor que quepa con aplazamiento limitado''': Cuando queda una partición libre, se selecciona el mayor proceso que quepa en ella, pero se cuenta el nº de veces que un proceso se aplaza. Si se superan esas '''n''' veces (umbral), se le da paso.

*'''Subparticiones''': Si no hay un proceso que pueda aprovechar partición madre: se asignan las subparticiones a procesos pequeños. Si llega un proceso grande: los procesos pequeños se vuelcan a disco y se asigna partición madre.
''Partición madre'': tipo especial de partición que se puede dividir en múltiples particiones menores.

= Métodos de colocación en memoria =

*'''Montaje absoluto''': Se asigna una dirección de memoria constante, siendo por tanto este método muy restrictivo. Se utiliza para la carga del sistema operativo.

* '''Carga con reubicación''': Al realizar la carga, se le aplica a las direcciones lógicas del programa un ''offset'' o desplazamiento asociada. Este desplazamiento es establecido por el programador antes de que se ejecute el programa.

* '''Reubicación dinámica''': A diferencia de la carga con reubicación, el desplazamiento se asigna en tiempo de ejecución.
** '''Reubicación dinámica parcial''': Es una variante del anterior, en la que existe también un registro límite.

= Mecanismos de protección de memoria =

Es necesario proteger el SO frente a procesos; y proteger frente a procesos entre sí.

* '''Ampliación bits de protección'''

* '''Ampliación registros valla'''

Introducción

2011-05-23T06:46:36Z

Jherrera: Introducción

Ahora desde el punto de vista de la memoria principal se van a ver el código,variables locales y globales. También se va a hacer referencia a la organización de memoria. Por ejemplo, a los sistemas operativos se les da una posición fija de memoria contigua mientras que a los procesos de forma fragmentada(páginas).

Esta administración de memoria se va a tratar en:

* [[SO monoprogramables|SO monoprogramables]]
* [[SO multiprogramables con particiones fijas|SO multiprogramables con particiones fijas]]
* [[SO multiprogramables con particiones variables|SO multiprogramables con particiones variables]]

Página Principal

2011-05-23T06:37:19Z

Jherrera: /* BLOQUE II: Administración de memoria contigua */

Bienvenido al wiki de la asignatura de Sistemas Operativos del departamento de Lenguajes y Sistemas Informáticos de la Universidad de Sevilla. ¡Regístrate y contribuye!

= Unidades didácticas =

A continuación encontrarás las unidades didácticas que forman parte de la asignatura.

== Introducción a los Sistemas Operativos ==

* [[Qué es un Sistema Operativo|Qué es un sistema operativo]]
* [[Introducción histórica|Una introducción histórica a los sistemas operativos]]
* [[Tipos de Sistemas Operativos|Tipos de sistemas operativos]]

== Fundamentos de Sistemas Operativos ==

* [[Conceptos básicos|Conceptos básicos]]
* [[Componentes básicos de un sistema operativo|Componentes básicos de un sistema operativo]]
* [[Llamadas al sistema|Llamadas al sistema]]
* [[Modelos de Diseño de Sistemas Operativos|Modelos de diseño de sistemas operativos]]
* [[Ejercicios fundamentos Sistemas Operativos|Ejercicios]]

== Procesos ==
* [[Multiprogramación|La multiprogramación]]
* [[Estados de los procesos|Estados de los procesos]]
* [[Planificador de procesos|El planificador de procesos]]
* [[Comportamiento de los procesos|El comportamiento de los procesos según el planificador]]
* [[Bloque de control de procesos|El bloque de control del proceso]]
* [[Conmutación de procesos|La conmutación de procesos]]
* [[Hilos|Hilos]]
* [[Ejercicios Procesos|Ejercicios]]

== Planificación de Procesos ==
* [[Planificación de procesos|La planificación de procesos]]
* [[Índices de evaluación|Índices de evaluación de la planificación de procesos]]
* [[Criterios de planificación|Criterios de planificación]]
* [[Planificadores de sistemas operativos existentes|Planificadores de sistemas operativos existentes]]
* [[Ejercicios planificación de procesos|Ejercicios]]

== Otros aspectos relacionados con la planificación de procesos ==

* [[Planificación de procesos de tiempo real|La planificación de procesos de tiempo real]]
* [[Planificación en sistemas multiprocesadores|La planificación de procesos en sistemas multiprocesadores]]
* [[Ejercicios otros aspectos de la planificación|Ejercicios]]

== Concurrencia de procesos ==

* [[Concurrencia de procesos|Concurrencia de procesos]]
* [[Mecanismos de sincronización|Control optimista y pesimista de la concurrencia]]
* [[Cerrojos|Cerrojos]]
* [[Ejercicio de concurrencia de procesos|Ejercicios]]

== Semáforos y comunicación ==

* [[Semáforos|Semáforos]]
* [[Monitores|Monitores]]
* [[Mensajería|Mensajería]]
* [[Ejercicios sincronización y comunicación|Ejercicios]]

== Interbloqueo ==

* [[Definición de interbloqueo|Definición]]
* [[Condiciones para el interbloqueo y estrategias de resolución|Modelado y Estrategias]]
* [[Algoritmo para averiguar interbloqueo]]
* [[Ejercicios]]

== BLOQUE II: Administración de memoria contigua ==

* [[Introducción|Introducción]]
* [[SO monoprogramables|SO monoprogramables]]
* [[SO multiprogramables con particiones fijas|SO multiprogramables con particiones fijas]]
* [[SO multiprogramables con particiones variables|SO multiprogramables con particiones variables]]

Solución ejercicio 3

2011-05-09T16:12:17Z

Jherrera: solución

La solución no es correcta, ya que se bloquearía el proceso que ejecuta el while del productor y también el del consumidor, y no se avanzaría en la ejecución.
Sería correcto si el semáforo del productor se inicializara a 1.

También habría que asegurar que el proceso P1 comenzará antes que P2, no??
Por lo que seguro que funcionaria con el contador de P1 igual a 1, y contador de P2 igual a 0, no??

R:Creo que no, ya que en caso de que empieze por P2 bloquea a la espera de que algún proceso haga un UP sobre dicho semáforo.

Los procesos son lanzados y tu no sabes a priori qué proceso se va a ejecutar, por lo que tienes que asegurarte que si se ejecuta el consumidor antes que el productor pase a estado bloqueado. Creo que la solución ,tal y como se dice el compañero al principio, es modificar el contador del productor poniendolo a 1.--[[Usuario:Jherrera|Jherrera]]

Solución de los ejercicios de concurrencia

2011-05-09T16:04:10Z

Jherrera:

| #1| #2| #3| | | | #4| #1| #2| | | | #3| #4|#1-El programa ya termina
H1 |---|---|---| | | |---|---|---| | | |---|---|---| | | | | |
| | | | | | | | | | | | | | | | | | | | |
| | | | #1| #2| #2| | | | #2| #2| #2| | | | #2| #3| #4| #1| #2| #3| #4| El programa termina.
H2 | | | |---|---|---| | | |---|---|---| | | |---|---|---|---| |
| | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

En este ejercicio, el hilo 2 se queda esperando continuamente a que el hilo 1 libere el cerrojo para poder acceder a la función.
El programa finaliza en el hilo 1 cuando llega dos veces a la instrucción 4 (bucle for).

Modificación:

Solución:

| #1| #2| #3| | | | #4| #1| #2| | | | #3| #4| > | | | | | | | |
H1 |---|---|---| | | |---|---|---| | | |---|---|---| | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | |
| | | | #1| __| __| | | | __| __| __| | | | #2| #3| #4| #1| #2| #3| #4|
H2 | | | |---|---|---| | | |---|---|---| | | |---|---|---|---|---|---|---|
| | | | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Posible solución:

Los hilos comparten variables por lo que la variable i está siendo compartida por ambos hilos. Además, al ser los cerrojos un control de concurrencia de espera activa, tiene que comprobar continuamente la condición que me permite acceder a la sección crítica. En un bucle for, el incremento se hace una vez realizada la iteración, por lo que tendrá que comprobar en la instrucción 1 si el contador cumple la condición o no. Dicho esto y si no me equivoco la solución sería la siguiente--[[Usuario:Jherrera|Jherrera]]:

| #1| #2| #3| | | | #4| #1| #2| | | | #3| #4| #1| | | | | |
H1 |---|---|---| | | |---|---|---| | | |---|---|---| | | | | |
| | | | | | | | | | | | | | | | | | | | |
| | | | #1| #2| #2| | | | #2| #2| #2| | | | #2| #3| #4| #1| |
H2 | | | |---|---|---| | | |---|---|---| | | |---|---|---|---| |
| | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Posible solución2: Lo que explicas esta muy bien, pero creo que la condición que expones en tu apartado es i=<2, cuando el ejercicio pide i<2. Por lo que habria que cortar un trozo, ¿no?

| #1| #2| #3| | | | #4| #1| #1| | | | | | | | | | | |
H1 |---|---|---| | | |---|---|---| | | |---|---|---| | | | | |
| | | | | | | | | | | | | | | | | | | | |
| | | | #1| #2| #2| | | | #2| #3| #4| | | | | | | | |
H2 | | | |---|---|---| | | |---|---|---| | | |---|---|---|---| |
| | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Yo creo que esta bien ya que es i<2 y empieza con i = 0 --[[Usuario:Luidela1|Luidela1]] 15:35 9 may 2011 (UTC)

Solución ejercicio 1

2011-05-09T15:36:23Z

Jherrera: aclaración

X = El proceso pasa a estado bloqueado.
/ = El proceso pasa a estado preparado.

| | | #1| #2| #3| #4| #5| #1| | | | #2| #3| #4| | | | #5| fin de ejecucion
p1| | |---|---|---|---|---|---| | | |---|---|---| | | |---| | |
| | | | | | | | | | | | | | | | | | | | |
| #1| #2| | | | | | | #3| #4| #1| | | | #2| #3| #4| fin de ejecucion
p2|---|---X | | | | / |---|---|---| | | |---|---|---| | | |
| | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

El proceso P2 comienza su ejecucion y al hacer el down al semaforo s2 que vale 0 bloquea , ya que los semaforo es un sincronizacion bloqueante, p1 comienza su ejecucion hasta que se hace up(s2) y agota su ventana de tiempo y p2 puede comenzar su ejecucion.

--[[Usuario:DvS 013|DvS 013]] 15:09 9 may 2011 (UTC) : había conflicto cuando le he dado a subir así que pongo debajo lo que yo estaba editando antes de que se subiera nada
p1: <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>
P2: <source lang="c">
for (int i=0; i<2; i++) { #1
down(s2); #2
f2(); #3
up(s1); #4
} </source>

X : se ejecuta el planificador
> : fin del proceso
#nº : número de insturcción

|i2=0 |i1=0 | i2=1 | i1=1 | | i2=2|i1=2 |
| | | | #1| #2| #3| | | | #4| #1| #2| #3| #4| #5| | | | #1| |
P1 | | | |---|---|---| | | |---|---|---|---|---|---| | | |---> |
s1 | 1 | 0 | 1 | 0 | 1 | |
| #1| #2| #3| | | | #4| #1| #2| | | | | | | #3| #4| #1| | |
P2 |---|---|---| | | |---|---|---| | | | | | |---|---|---> | |
s2 | 1 | 0 | 0 | | | | | |
planif 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

Nueva solución:
Con respecto a la primera, una simple aclaración --[[Usuario:David|David]] 15:26 9 may 2011 (UTC)
X = El proceso pasa a estado bloqueado.
/ = El proceso pasa a estado preparado.

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

Como aclaración: cuando se realiza el up de un semáforo que vale 0, si hay procesos en su lista de semáforos, se coge el primero y se pasa a estado preparado, valiendo el contador del semáforo 0, por eso en el instante 15 al hacer el down de s2 vuelve a bloquear.

--[[Usuario:Josmorgav1|Josmorgav1]] 15:32 9 may 2011 (UTC)
Una aclaración al compañero David Martin, el contador de semáforo s2, en un principio vale 0, y como el primer proceso en ejecutar es P2, al hacer el down(s2); bloquea, creo que en tu solución consideras que s2 vale 1.
Desde mi punto de vista, la solución por ahora más correcta, es la del compañero David Suárez

--[[Usuario:Jherrera|Jherrera]]
Con respecto a la solución de Dvs no es correcta a partir del instante 2, ya que interpreto que el proceso 2 ejecuta la instrucción nº3 en vez de pasar a bloqueado. He realizado el ejercicio al igual que David (última solución propuesta) y pienso que está totalmente correcto.

Solución de los ejercicios de concurrencia

2011-05-09T14:43:53Z

Jherrera: posible solución

| #1| #2| #3| | | | #4| #1| #2| | | | #3| #4|El programa ya termina |
H1 |---|---|---| | | |---|---|---| | | |---|---|---| | | | | |
| | | | | | | | | | | | | | | | | | | | |
| | | | #1| #2| #2| | | | #2| #2| #2| | | | #2| #3| #4| #1| #2| #3| #4| El programa termina.
H2 | | | |---|---|---| | | |---|---|---| | | |---|---|---|---| |
| | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

En este ejercicio, el hilo 2 se queda esperando continuamente a que el hilo 1 libere el cerrojo para poder acceder a la función.
El programa finaliza en el hilo 1 cuando llega dos veces a la instrucción 4 (bucle for).

Modificación:

Solución:

| #1| #2| #3| | | | #4| #1| #2| | | | #3| #4| > | | | | | | | |
H1 |---|---|---| | | |---|---|---| | | |---|---|---| | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | |
| | | | #1| __| __| | | | __| __| __| | | | #2| #3| #4| #1| #2| #3| #4|
H2 | | | |---|---|---| | | |---|---|---| | | |---|---|---|---|---|---|---|
| | | | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

Posible solución:

Los hilos comparten variables por lo que la variable i está siendo compartida por ambos hilos. Además, al ser los cerrojos un control de concurrencia de espera activa, tiene que comprobar continuamente la condición que me permite acceder a la sección crítica. En un bucle for, el incremento se hace una vez realizada la iteración, por lo que tendrá que comprobar en la instrucción 1 si el contador cumple la condición o no. Dicho esto y si no me equivoco la solución sería la siguiente:

| #1| #2| #3| | | | #4| #1| #2| | | | #3| #4| #1| | | | | |
H1 |---|---|---| | | |---|---|---| | | |---|---|---| | | | | |
| | | | | | | | | | | | | | | | | | | | |
| | | | #1| #2| #2| | | | #2| #2| #2| | | | #2| #3| #4| #1| |
H2 | | | |---|---|---| | | |---|---|---| | | |---|---|---|---| |
| | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Definición de interbloqueo

2011-05-04T16:11:53Z

Jherrera: erratas

También conocido como '''bloqueo mutuo''' o '''deadlock'''.

Es el bloqueo permanente de un conjunto de procesos que compiten por los recursos del sistema o bien se comunican unos con otros. Existen una serie de [[Condiciones para el interbloqueo y estrategias de resolución#condiciones|condiciones]] para que se produzca dicho bloqueo y una serie de [[Condiciones para el interbloqueo y estrategias de resolución#estrategias|estrategias]] para resolverlos.

* Ejemplo simple:

[[Imagen:GrafoDeadlock.jpg]]

Se aprecian dos procesos (P1 y P2), cada uno con un recurso diferente asociado (R1 y R2). Llega un punto en el que el proceso P1 ha adquirido el recurso R1 y el proceso P2 ha adquirido el recurso R2 y cada proceso necesita el otro recurso. Este es el punto de interbloqueo.

Monitores

2011-04-19T12:04:10Z

Jherrera: /* Definición */ errata en codigo

Idea desarrollada en los años 70 Brinch-Hansen y Hoare <ref>http://java.sun.com/developer/Books/performance2/chap4.pdf</ref>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.
* No hay nada que obligue a usarlos. Puede suceder que el programador los necesite y lo desconozca
* Son independientes del recurso compartido

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 = valor;
up(s);
}
}

</source>

Como vemos, los monitores se implementan con semáforos, son una abstracción de los mismos.

== Fuentes ==
<references/>

Concurrencia de procesos

2011-04-18T11:40:57Z

Jherrera: /* Tipos de mecanismos de sincronización */ ampliación

La concurrencia de procesos se refiere a las situaciones en las que dos o más procesos puedan coincidir en el acceso a un recurso compartido o, dicho de otra forma, que requieran coordinarse en su ejecución. Para evitar dicha coincidencia, el sistema operativo ofrece mecanismos de arbitraje que permiten coordinar la ejecución de los procesos.

Un ejemplo de un problema de concurrencia sería el siguiente: Dados dos procesos A y B, suponiendo que ambos se ejecutan indefinidamente en el tiempo, el proceso A debe recibir tiempo de ejecución antes que B, tras esto, el proceso B debe recibir su oportunidad de ejecución, dando paso de nuevo al proceso A y así sucesivamente.

proceso A |-- -- --
|
proceso B | -- -- --
|_____________

Recuerde que el planificador de procesos, al desconocer la naturaleza de los procesos y sus objetivos, no dispone de información suficiente como para garantizar la secuencia de ejecución descrita en el ejemplo anterior. Por tanto, suponiendo que ambos procesos se encuentran en estado preparado, podría seleccionar al proceso B para pasar a estado activo antes de seleccionar al proceso A, situación que no es deseada.

Recuerde que el planificador de procesos, como hemos visto en capítulos anteriores, emplea [[Criterios de planificación|criterios de planificación]] que no tienen en consideración el objetivo de los procesos. Podemos decir que el planificador de procesos '''desconoce''' cuál es el propósito de los procesos, únicamente puede observar su comportamiento, es decir, si presentan un comportamiento más o menos interactivo.

Por tanto, el programador, a la hora de modelar los procesos, debe emplear mecanismos de arbitraje que ofrece el sistema operativo y que permiten resolver el problema de concurrencia que se plantee.

= Formas de interacción entre procesos =

Hay dos formas básicas de interacción entre los procesos:

* '''Relaciones de competencia''': Dados dos procesos A y B, ambos procesos tienen objetivos diferentes y compiten por los recursos para conseguirlos. Por ejemplo, dos procesos desean modificar el contenido de un mismo fichero, pero no deben hacerlo de manera simultánea o quedará en un estado incoherente.

* '''Relaciones de cooperación''': Dados dos procesos A y B, ambos con un mismo objetivo, ''se ponen de acuerdo'' a la hora de emplear los recursos existentes para alcanzarlos. Por ejemplo, el proceso A produce un objeto que es consumido por el proceso B, hasta que el proceso A no produzca, el proceso B no debe consumir y viceversa.

= Mecanismos de arbitraje =

Los mecanismos de arbitraje que ofrece el sistema operativo son básicamente dos:

* Mecanismos de '''sincronización''': el sistema operativo ofrece mecanismos que permiten a los procesos coordinar su ejecución para conseguir el objetivo sin que sucedan situaciones no deseadas, como por ejemplo que dos o más procesos coincidan simultáneamente en el acceso a un cierto recurso que no se puede compartir.

* Mecanismos de '''mensajería''': el sistema operativo ofrece mecanismos de comunicación entre procesos mediante mensajes. El intercambio de mensajes entre procesos permite coordinarlos.

= Programación concurrente =

La programación concurrente se trata del conjunto de técnicas que nos permiten elaborar programas que resuelven situaciones de concurrencia. En programación concurrente, el programador emplea alguno de los mecanismos de arbitraje que ofrece el sistema operativo, ya sean los de sincronización o mensajería, para resolver el problema de concurrencia.

= Tipos de mecanismos de sincronización =

Los mecanismos de sincronización los podemos catalogar en dos categorías:

*[[Mecanismos de sincronización#Optimista|Optimistas]]: Este mecanismo considera que la frecuencia de acceso a un cierto recurso compartido es ''baja''.
*[[Mecanismos de sincronización#Pesimista|Pesimistas]]: Este mecanismo permite coordinar la ejecución de dos o más procesos que acceden al recurso compartida con una frecuencia ''alta''.

Dependerá del criterio del programador el tipo de mecanismo que utilize ya que puede que no elija el tipo correcto. Por ejemplo, puede que la frecuencia de acceso a un cierto recurso sea baja y el programador le asigna un mecanismo optimista. Esto provoca no obtener el resultado esperado.

Concurrencia de procesos

2011-04-18T10:24:11Z

Jherrera: /* Formas de interación entre procesos */

Concurrencia de procesos

2011-04-18T10:23:12Z

Jherrera: /* Formas de interacción entre procesos */

La concurrencia de procesos se refiere a las situaciones en las que dos o más procesos puedan coincidir en el acceso a un recurso compartido o, dicho de otra forma, que requieran coordinarse en su ejecución. Para evitar dicha coincidencia, el sistema operativo ofrece mecanismos de arbitraje que permiten coordinar la ejecución de los procesos.

Un ejemplo de un problema de concurrencia sería el siguiente: Dados dos procesos A y B, suponiendo que ambos se ejecutan indefinidamente en el tiempo, el proceso A debe recibir tiempo de ejecución antes que B, tras esto, el proceso B debe recibir su oportunidad de ejecución, dando paso de nuevo al proceso A y así sucesivamente.

proceso A |-- -- --
|
proceso B | -- -- --
|_____________

Recuerde que el planificador de procesos, al desconocer la naturaleza de los procesos y sus objetivos, no dispone de información suficiente como para garantizar la secuencia de ejecución descrita en el ejemplo anterior. Por tanto, suponiendo que ambos procesos se encuentran en estado preparado, podría seleccionar al proceso B para pasar a estado activo antes de seleccionar al proceso A, situación que no es deseada.

Recuerde que el planificador de procesos, como hemos visto en capítulos anteriores, emplea [[Criterios de planificación|criterios de planificación]] que no tienen en consideración el objetivo de los procesos. Podemos decir que el planificador de procesos '''desconoce''' cuál es el propósito de los procesos, únicamente puede observar su comportamiento, es decir, si presentan un comportamiento más o menos interactivo.

Por tanto, el programador, a la hora de modelar los procesos, debe emplear mecanismos de arbitraje que ofrece el sistema operativo y que permiten resolver el problema de concurrencia que se plantee.

= Formas de interación entre procesos =

Hay dos formas básicas de interacción entre los procesos:

* '''Relaciones de competencia''': Dados dos procesos A y B, ambos procesos tienen objetivos diferentes y compiten por los recursos para conseguirlos. Por ejemplo, dos procesos desean modificar el contenido de un mismo fichero, pero no deben hacerlo de manera simultánea o quedará en un estado incoherente.

* '''Relaciones de cooperación''': Dados dos procesos A y B, ambos con un mismo objetivo, ''se ponen de acuerdo'' a la hora de emplear los recursos existentes para alcanzarlos. Por ejemplo, el proceso A produce un objeto que es consumido por el proceso B, hasta que el proceso A no produzca, el proceso B no debe consumir y viceversa.

= Mecanismos de arbitraje =

Los mecanismos de arbitraje que ofrece el sistema operativo son básicamente dos:

* Mecanismos de '''sincronización''': el sistema operativo ofrece mecanismos que permiten a los procesos coordinar su ejecución para conseguir el objetivo sin que sucedan situaciones no deseadas, como por ejemplo que dos o más procesos coincidan simultáneamente en el acceso a un cierto recurso que no se puede compartir.

* Mecanismos de '''mensajería''': el sistema operativo ofrece mecanismos de comunicación entre procesos mediante mensajes. El intercambio de mensajes entre procesos permite coordinarlos.

= Programación concurrente =

La programación concurrente se trata del conjunto de técnicas que nos permiten elaborar programas que resuelven situaciones de concurrencia. En programación concurrente, el programador emplea alguno de los mecanismos de arbitraje que ofrece el sistema operativo, ya sean los de sincronización o mensajería, para resolver el problema de concurrencia.

= Tipos de mecanismos de sincronización =

Los mecanismos de sincronización los podemos catalogar en dos categorías:

*[[Mecanismos de sincronización#Optimista|Optimistas]]: Este mecanismo considera que la frecuencia de acceso a un cierto recurso compartido es ''baja''.
*[[Mecanismos de sincronización#Pesimista|Pesimistas]]: Este mecanismo permite coordinar la ejecución de dos o más procesos que acceden al recurso compartida con una frecuencia ''alta''.

Concurrencia de procesos

2011-04-18T10:20:14Z

Jherrera:

Concurrencia de procesos

2011-04-18T09:52:49Z

Jherrera: errata

La concurrencia de procesos se refiere a las situaciones en las que dos o más procesos puedan coincidir en el acceso a un recurso compartido o, dicho de otra forma, que requieran coordinarse en su ejecución. Para evitar dicha coincidencia, el sistema operativo ofrece mecanismos de arbitraje que permiten coordinar la ejecución de los procesos.

Un ejemplo de un problema de concurrencia sería el siguiente: Dados dos procesos A y B, suponiendo que ambos se ejecutan indefinidamente en el tiempo, el proceso A debe recibir tiempo de ejecución antes que B, tras esto, el proceso B debe recibir su oportunidad de ejecución, dando paso de nuevo al proceso A y así sucesivamente.

proceso A |-- -- --
|
proceso B | -- -- --
|_____________

Recuerde que el planificador de procesos, al desconocer la naturaleza de los procesos y sus objetivos, no dispone de información suficiente como para garantizar la secuencia de ejecución descrita en el ejemplo anterior. Por tanto, suponiendo que ambos procesos se encuentran en estado preparado, podría seleccionar al proceso B para pasar a estado activo antes de seleccionar al proceso A, situación que no es deseada.

Recuerde que el planificador de procesos, como hemos visto en capítulos anteriores, emplea criterios de planificación que no tienen en consideración el objetivo de los procesos. Podemos decir que el planificador de procesos '''desconoce''' cuál es el propósito de los procesos, únicamente puede observar su comportamiento, es decir, si presentan un comportamiento más o menos interactivo.

Por tanto, el programador, a la hora de modelar los procesos, debe emplear mecanismos de arbitraje que ofrece el sistema operativo y que permiten resolver el problema de concurrencia que se plantee.

= Formas de interacción entre procesos =

Hay dos formas básicas de interacción entre los procesos:

* '''Relaciones de competencia''': Dados dos procesos A y B, ambos procesos tienen objetivos diferentes y compiten por los recursos para conseguirlos. Por ejemplo, dos procesos desean modificar el contenido de un mismo fichero, pero no deben hacerlo de manera simultánea o quedará en un estado incoherente.

* '''Relaciones de cooperación''': Dados dos procesos A y B, ambos con un mismo objetivo, ''se ponen de acuerdo'' a la hora de emplear los recursos existentes para alcanzarlos. Por ejemplo, el proceso A produce un objeto que se consumido por el proceso B, hasta que el proceso A no produzca, el proceso B no debe consumir y viceversa.

= Mecanismos de arbitraje =

Los mecanismos de arbitraje que ofrece el sistema operativo son básicamente dos:

* Mecanismos de '''sincronización''': el sistema operativo ofrece mecanismos que permiten a los procesos coordinar su ejecución para conseguir el objetivo sin que sucedan situaciones no deseadas, como por ejemplo que dos o más procesos coincidan simultáneamente en el acceso a un cierto recurso que no se puede compartir.

* Mecanismos de '''mensajería''': el sistema operativo ofrece mecanismos de comunicación entre procesos mediante mensajes. El intercambio de mensajes entre procesos permite coordinarlos.

= Programación concurrente =

La programación concurrente se trata del conjunto de técnicas que nos permiten elaborar programas que resuelven situaciones de concurrencia. En programación concurrente, el programador emplea alguno de los mecanismos de arbitraje que ofrece el sistema operativo, ya sean los de sincronización o mensajería, para resolver el problema de concurrencia.

= Tipos de mecanismos de sincronización =

Los mecanismos de sincronización los podemos catalogar en dos categorías:

*[[Mecanismos de sincronización#Optimista|Optimistas]]: Este mecanismo considera que la frecuencia de acceso a un cierto recurso compartido es ''baja''.
*[[Mecanismos de sincronización#Pesimista|Pesimistas]]: Este mecanismo permite coordinar la ejecución de dos o más procesos que acceden al recurso compartida con una frecuencia ''alta''.

Concurrencia de procesos

2011-04-18T09:29:36Z

Jherrera: errata

La concurrencia de procesos se refiere a las situaciones en las que dos o más procesos puedan coincidir en el acceso a un recurso compartido o, dicho de otra forma, que requieran coordinarse en su ejecución. Para evitar dicha coincidencia, el sistema operativo ofrece mecanismos de arbitraje que permiten coordinar la ejecución de los procesos.

Un ejemplo de un problema de concurrencia sería el siguiente: Dados dos procesos A y B, suponiendo que ambos se ejecutan indefinidamente en el tiempo, el proceso A debe recibir tiempo de ejecución antes que B, tras esto, el proceso B debe recibir su oportunidad de ejecución, dando paso de nuevo al proceso A y así sucesivamente.

proceso A |-- -- --
|
proceso B | -- -- --
|_____________

Recuerde que el planificador de procesos, al desconocer la naturaleza de los procesos y sus objetivos, no dispone de información suficiente como para garantizar la secuencia de ejecución descrita en el ejemplo anterior. Por tanto, suponiendo que ambos procesos se encuentran en estado preparado, podría seleccionar al proceso B para pasar a estado activo antes de seleccionar al proceso B, situación que no es deseada.

Recuerde que el planificador de procesos, como hemos visto en capítulos anteriores, emplea criterios de planificación que no tienen en consideración el objetivo de los procesos. Podemos decir que el planificador de procesos '''desconoce''' cuál es el propósito de los procesos, únicamente puede observar su comportamiento, es decir, si presentan un comportamiento más o menos interactivo.

Por tanto, el programador, a la hora de modelar los procesos, debe emplear mecanismos de arbitraje que ofrece el sistema operativo y que permiten resolver el problema de concurrencia que se plantee.

= Formas de interacción entre procesos =

Hay dos formas básicas de interacción entre los procesos:

* '''Relaciones de competencia''': Dados dos procesos A y B, ambos procesos tienen objetivos diferentes y compiten por los recursos para conseguirlos. Por ejemplo, dos procesos desean modificar el contenido de un mismo fichero, pero no deben hacerlo de manera simultánea o quedará en un estado incoherente.

* '''Relaciones de cooperación''': Dados dos procesos A y B, ambos con un mismo objetivo, ''se ponen de acuerdo'' a la hora de emplear los recursos existentes para alcanzarlos. Por ejemplo, el proceso A produce un objeto que se consumido por el proceso B, hasta que el proceso A no produzca, el proceso B no debe consumir y viceversa.

= Mecanismos de arbitraje =

Los mecanismos de arbitraje que ofrece el sistema operativo son básicamente dos:

* Mecanismos de '''sincronización''': el sistema operativo ofrece mecanismos que permiten a los procesos coordinar su ejecución para conseguir el objetivo sin que sucedan situaciones no deseadas, como por ejemplo que dos o más procesos coincidan simultáneamente en el acceso a un cierto recurso que no se puede compartir.

* Mecanismos de '''mensajería''': el sistema operativo ofrece mecanismos de comunicación entre procesos mediante mensajes. El intercambio de mensajes entre procesos permite coordinarlos.

= Programación concurrente =

La programación concurrente se trata del conjunto de técnicas que nos permiten elaborar programas que resuelven situaciones de concurrencia. En programación concurrente, el programador emplea alguno de los mecanismos de arbitraje que ofrece el sistema operativo, ya sean los de sincronización o mensajería, para resolver el problema de concurrencia.

= Tipos de mecanismos de sincronización =

Los mecanismos de sincronización los podemos catalogar en dos categorías:

*[[Mecanismos de sincronización#Optimista|Optimistas]]: Este mecanismo considera que la frecuencia de acceso a un cierto recurso compartido es ''baja''.
*[[Mecanismos de sincronización#Pesimista|Pesimistas]]: Este mecanismo permite coordinar la ejecución de dos o más procesos que acceden al recurso compartida con una frecuencia ''alta''.

Solución de los ejercicios de fundamentos

2011-03-31T11:46:03Z

Jherrera: resolucion

La principal diferencia reside en la estructura que toman ambos sistemas operativos. Los monolíticos como Windows o Linux se caracterizan por tener en el kernel una gran cantidad de funcionalidades como puede ser la gestión de dispositivos de E/S,planificación de procesos, sistema de comunicación de procesos y la administración de ficheros y memoria. En cambio los micronúcleos parten de un kernel que implementan algunas funciones como la planificación de procesos,mecanismos de comunicación de procesos y gestión de interrupciones; añadiendo para el resto de funciones procesos servidores en módulos externos al kernel.

Usuario:Jherrera

2011-03-22T22:55:21Z

Jherrera: Página nueva: Javier Herrera Copano

Javier Herrera Copano

Sol-ejer3-planif-procesos

2011-03-22T19:49:25Z

Jherrera: /* Ejercicio 3 */

= 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

Sol-ejer3-planif-procesos

2011-03-22T19:47:40Z

Jherrera: /* Ejercicio 3 */ dudas

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

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:

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

Sol-ejer2-planif-procesos

2011-03-21T22:33:09Z

Jherrera: /* Por prioridades */ Correción

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

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

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

Sol-ejer2-planif-procesos

2011-03-21T22:03:06Z

Jherrera: /* Por prioridades */ correción ejercicio

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

= 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__|_14_|_12_|_6_|
_T/t_|4.66|_2.4|_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.

Sol-ejer2-planif-procesos

2011-03-21T17:59:33Z

Jherrera: /* Turno rotatorio */ Realizacion ejercicio por prioridades

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

Discusión:Sol-ejer2-planif-procesos

2011-03-21T17:31:38Z

Jherrera:

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?

Sol-ejer2-planif-procesos

2011-03-21T17:29:55Z

Jherrera: /* Turno rotatorio */

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

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

Discusión:Sol-ejer2-planif-procesos

2011-03-21T17:29:01Z

Jherrera: Dudas referentes al ejercicio 1

Creo que la solución al ejercicio 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?

Ejercicios otros aspectos de la planificación

2011-03-21T16:01:45Z

Jherrera: /* Ejercicio de clase sobre SO de tiempo real */ correción indice de penalizacion

== Ejercicio de clase sobre SO de tiempo real ==

____|_PA_|_PB_|_PC_|_PD_|
Datos del _H0_|_0__|_1__|_2__|_3*n|
problema _t__|_2__|_4__|_2__|_1__|
plazo|_3__|_5__|_7__|_10_|
prioridad|_-20|_0__|_10_|_15_|
(-20 a 19)
UNIX
< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
* = el proceso se aborta

| | | | | | | | | | | | | | | | | | | | |
PA <___|___> | | | | | | | | | | | | | | | | | |
PB | < |___|___|___* | | | | | | | | | | | | | | |
PC | | < | | |___|___> | | | | | | | | | | | | |
PD | | | < | * < |___> <___> | <___> | <___> | | | |
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

_____|_PA_|_PB_|_PC_|_PD_|
Cálculos __t__|_2__|_3__|_2__|_1_|
de tiempos __T__|_2__|_4__|_4__|_1_|
_T/t_|_1__|0.75|_2__|_1_|
|
|_> Indice de penalización