Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Solución ejercicio 1 memoria virtual

2011-06-14T09:37:52Z

Alexrdp: /* 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 | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | = | 0 | 1 | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | 4 | = | = | 2 | = | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | | 1 | 0 | = | = | 1 | = | 0 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | | X |
página -------------------------------------------------------------------------------------------------
contenido | 1 | 1 | 1 | 1-2 | 1-2-3 |1-2-3-4|2-3-4-5|2-3-4-5|3-4-5-1|5-1-3-2|5-1-3-2|1-3-2-4|
de la cola -------------------------------------------------------------------------------------------------

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

Una Dudilla : la FIFO es por orden de carga o por orden de acceso?¿ Según veo en el ejercicio lo hace por orden de acceso --[[Usuario:DvS 013|DvS 013]]
--
Respuesta : La fifo almacena el tiempo que una página lleva cargada en memoria, por lo que es por orden de carga. [[Usuario : JCGarrido|JCGarrido]]

He puesto el orden de la cola para que se vea más claro. Cuando el candidato tiene R=1 se pone a 0 y se inserta al final. Es por eso que cuando se accede por última vez a la página 2, al estar 3 la primera, se pone su bit R a 0 se inserta al final (no estaba en la solución anterior) y la siguiente (4, con R=0) es la página víctima.--[[Usuario:Alexrdp|Alexrdp]] 09:37 14 jun 2011 (UTC)

Entonces, sería asi:

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 | = | 5 | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | 1 | = | = | = | = | = | 1 | = | 0 | = | = | 1 |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 2 | = | 1 | 1 | = | 1 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | 1 | = | = | 0 | = | 1 | 0 | = | 0 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | 3 | 3 | 3 | 2 | 2 | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | 0 | 1 | 0 | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | 4 | = | = | = | 3 | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | | 1 | 0 | = | = | = | 1 | 0 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | X | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

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

Esta segunda solución creo que no está del todo correcta.
Cuando llega el cuarto acceso a 1 (donde se produce el sexto fallo de página), el contenido de la cola es el siguiente:

2 (R=0) - 3 (R=1) - 4 (R=0) - 5 (R=1)

Con lo cual, la víctima es el 2, pero sin poner a 0 el resto de los bits R, ya que el primer elemento de la cola tiene el bit R=0 y no hace falta seguir iterando sobre ésta.

= 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 | = | = | 4 |
|100| = | = | = ||010| = |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 1 memoria virtual

2011-06-14T09:29:17Z

Alexrdp: /* 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 | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | = | 0 | 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]]

Una Dudilla : la FIFO es por orden de carga o por orden de acceso?¿ Según veo en el ejercicio lo hace por orden de acceso --[[Usuario:DvS 013|DvS 013]]
--
Respuesta : La fifo almacena el tiempo que una página lleva cargada en memoria, por lo que es por orden de carga. [[Usuario : JCGarrido|JCGarrido]]

Entonces, sería asi:

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 | = | 5 | = | = | 4 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | 1 | = | = | = | = | = | 1 | = | 0 | = | = | 1 |
---------------------------------------------------------------------------------------------------------
marcos | 2 | | | | 2 | = | = | 2 | = | 1 | 1 | = | 1 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | 1 | = | = | 0 | = | 1 | 0 | = | 0 |
---------------------------------------------------------------------------------------------------------
| 3 | | | | | 3 | = | 3 | 3 | 3 | 2 | 2 | 2 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | 1 | = | 0 | 1 | 0 | 1 | 0 | 0 |
---------------------------------------------------------------------------------------------------------
| 4 | | | | | | 4 | 4 | = | = | = | 3 | 3 |
| |-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|-------|
| R | | | | | | 1 | 0 | = | = | = | 1 | 0 |
---------------------------------------------------------------------------------------------------------
fallo | X | | | X | X | X | X | | X | X | X | X |
página -------------------------------------------------------------------------------------------------

tiempo ->

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

Esta segunda solución creo que no está del todo correcta.
Cuando llega el cuarto acceso a 1 (donde se produce el sexto fallo de página), el contenido de la cola es el siguiente:

2 (R=0) - 3 (R=1) - 4 (R=0) - 5 (R=1)

Con lo cual, la víctima es el 2, pero sin poner a 0 el resto de los bits R, ya que el primer elemento de la cola tiene el bit R=0 y no hace falta seguir iterando sobre ésta.

= 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 | = | = | 4 |
|100| = | = | = ||010| = |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 de los ejercicios de administración de ficheros

2011-06-13T17:33:25Z

Alexrdp: Añadir respuesta ejercicio 2

== Ejercicio 1 ==

A. Los archivos Fichero2.txt e Imagen2.jpg están corruptos, ya que ambos tienen (o envían) a una etiqueta 'BAD'.

B.
Entrada a directorio raíz E: 1 acceso
Entrada a Imagen.jpg: 1 acceso
Llegada a etiqueta EOF: 3 accesos
Total: 5 accesos

¿No serían 4 accesos? A los bloques 2, 3, 5 y 6. Cuando se llega a la etiqueta EOF no hacen falta más accesos, ¿no?--[[Usuario:Alexrdp|Alexrdp]] 17:33 13 jun 2011 (UTC)

== Ejercicio 2 ==

1º: Acceso al bloque del i-nodo.
2 y 3º: Acceso a los bloques para alcanzar el bloque del doble indirecto.
4º: Acceso al bloque del doble indirecto.

Total: 4 accesos

Algoritmos de criterios de reemplazo

2011-06-10T12:28:26Z

Alexrdp: Añadir LRU y LFU

= Criterios de reemplazo =

Algoritmos en Python para comprobar los ejercicios de [[Criterios de reemplazo|criterios de reemplazo]] del tema de [[Página Principal#Memoria virtual|memoria virtual]]. El contenido mínimo que debe tener el script es el siguiente:

<source lang="python">
from collections import deque
from random import choice

class Memoria:
def imprime_cabecera(self):
s = ' '
for i in range(len(self.marcos)):
s+= '___%s___ ' % (i+1)
return s
def __repr__(self):
s = '|'
for programa in self.marcos:
if programa:
s+= ' %s ' % programa
else:
s+= ' '
s+= '|'
s += '\n' + len(s)*'-'
return s

def ejecuta(memoria, secuencia):
fallos = 0
res = memoria.imprime_cabecera()
for programa in secuencia:
hay_fallo = memoria.add(programa)
if hay_fallo:
print(res + ' Fallo de %s!'%programa)
fallos += 1
else:
print(res + ' Acceso a %s'%programa)
res = str(memoria)
print(res)
print('\nTasa de fallos = %s/%s\n\n' % (fallos, len(secuencia)))

secuencia = [2,2,3,1,1,3,4,5,1,1,2,3,4]
</source>

== Criterio MRU (Most Recently Used) ==

<source lang="python">
class MemoriaMRU(Memoria):
def __init__(self, i):
self.pila = []
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
# Borramos el de lo alto de la pila
indice = self.marcos.index(self.pila.pop())
self.marcos[indice] = False
self.marcos[self.marcos.index(False)] = programa
# Insertamos el programa en la pila actualizando
if programa in self.pila:
self.pila.remove(programa)
self.pila.append(programa)

return fallo
</source>

Código de prueba:

<source lang="python">
>>> m1 = MemoriaMRU(4)
>>> ejecuta(m1, secuencia)
</source>

== Criterio de selección estocástica ==

<source lang="python">
class MemoriaEstocastica(Memoria):
def __init__(self, i):
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
# Elegimos uno aleatorio
rand = choice(range(len(self.marcos)))
self.marcos[rand] = programa
else:
# Hay un marco vacio
self.marcos[self.marcos.index(False)] = programa
return fallo
</source>

Código de prueba:

<source lang="python">
>>> m2 = MemoriaEstocastica(4)
>>> ejecuta(m2, secuencia)
</source>

== Criterio por orden de carga FIFO ==

<source lang="python">
class MemoriaFIFO(Memoria):
def __init__(self, i):
self.cola = deque([])
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
# Borramos el primero de la cola
indice = self.marcos.index(self.cola.popleft())
self.marcos[indice] = False

self.marcos[self.marcos.index(False)] = programa

# Insertamos el programa en la cola
if not programa in self.cola:
self.cola.append(programa)

return fallo
</source>

Código de prueba:

<source lang="python">
>>> m3 = MemoriaFIFO(4)
>>> ejecuta(m3, secuencia)
</source>

== Criterio LRU ==

<source lang="python">
class MemoriaLRU(Memoria):
def __init__(self, i):
self.cola = deque([])
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
# Borramos el primero de la cola
indice = self.marcos.index(self.cola.popleft())
self.marcos[indice] = False

self.marcos[self.marcos.index(False)] = programa

# Insertamos el programa en la cola actualizando
if programa in self.cola:
self.cola.remove(programa)
self.cola.append(programa)

return fallo
</source>

Código de prueba:

<source lang="python">
>>> m4 = MemoriaLRU(4)
>>> ejecuta(m4, secuencia)
</source>

== Criterio LFU ==

<source lang="python">
class MemoriaLFU(Memoria):
def __init__(self, i):
self.marcos = [False] * i
self.contadores = [0] * i

def add(self, programa):
fallo = 0
if not programa in self.marcos:
# Fallo de pagina
fallo = 1
if False in self.marcos:
# Seleccionamos un marco vacio
indice_false = self.marcos.index(False)
self.contadores[indice_false] = 1
self.marcos[indice_false] = programa
else:
# Seleccionamos el de menor contador
indice = self.contadores.index(min(self.contadores))
self.marcos[indice] = programa
self.contadores[indice] = 1
else:
# Exito, incrementamos contador
indice = self.marcos.index(programa)
self.contadores[indice] += 1
return fallo

def __repr__(self):
s = '|'
i = 0
for programa in self.marcos:
if programa:
s+= ' %s {%s} ' % (programa, self.contadores[i])
else:
s+= ' '
s += '|'
i += 1
s += '\n' + len(s)*'-'
return s
</source>

Código de prueba:

<source lang="python">
>>> m5 = MemoriaLFU(4)
>>> ejecuta(m5, secuencia)
</source>

== Criterio de Sustitución por envejecimiento ==

<source lang="python">
class Marco:
def __init__(self, tam):
self.programa = False
self.tam = tam
self.registro = [0] * tam
def inserta(self, programa):
self.programa = programa
self.registro = [1] + ([0] * (self.tam-1))
def actualiza(self):
self.registro[0] = 1
def desplaza(self):
self.registro = [0] + self.registro[:-1]
def __gt__(self,marco):
for i in range(self.tam):
if self.registro[i] > marco.registro[i]:
return True
return False
def __repr__(self):
if self.programa:
return '%s %s' %(self.programa, self.registro)
else:
return ' ' * (self.tam*3 + 2)

class Tabla:
def __init__(self, cantidad, tam_registros):
self.lista = []
for i in range(cantidad):
self.lista.append(Marco(tam_registros))

def addPrograma(self, programa):
esta = False
indice = 0
for marco in self.lista:
if programa == marco.programa:
esta = True
break
indice += 1
if esta:
self.lista[indice].actualiza()
return 0
else:
print("Fallo!")
indice = self.lista.index(self.minimo())
self.lista[indice].inserta(programa)
return 1

def minimo(self):
res = self.lista[0]
for marco in self.lista[1:]:
if res > marco:
res = marco
return res

def __repr__(self):
s = ''
for marco in self.lista:
s += '| %s ' % marco
s += '|\n' + '-'*(len(s)+1)
return s

class AproximacionDiscretaLRU:
def __init__(self, cantidad, periodo, tam_registros = 3):
self.tabla = Tabla(cantidad, tam_registros)
self.periodo = periodo

def ejecuta(self, lista_programas):
i = 0
fallos = 0
for programa in lista_programas:
if i%self.periodo == 0:
for marco in self.tabla.lista:
marco.desplaza()
i+=1
fallos += self.tabla.addPrograma(programa)
print(self.tabla)
print("\nTasa de fallos: %s/%s" % (fallos, len(lista_programas)))

</source>

Si ejecutamos el ejemplo visto en clase mostraría:

<source lang="python">
>>> alg = AproximacionDiscretaLRU(4, 4)
>>> alg.ejecuta([2,2,3,1,1,3,4,5,1,1,2,3,4])
Fallo!
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | 1 [1, 0, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [0, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 4 [1, 0, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 5 [1, 0, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [1, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [0, 1, 1] | 1 [0, 1, 1] | 4 [1, 0, 0] |
---------------------------------------------------------

Tasa de fallos: 6/13
</source>

La diferencia con respecto a la solución de clase es que la resolución en caso de empate es elegir el marco con índice menor.

Mejoras de tiempos de desplazamiento

2011-06-07T21:28:41Z

Alexrdp: MejorasTiempoBusqueda trasladada a Mejoras de tiempos de búsqueda

== FCFS (por orden de llegada "FIFO") ==

Las peticiones se atienden en el mismo orden en que se reciben. Tiene el inconveniente de que se realizan muchos desplazamientos del cabezal, especialmente si se realizan accesos consecutivos a bloques muy alejados entre sí.

== SSTF (Shortest Seek Time First) ==

También conocido como atención por menor tiempo de búsqueda: Ordena todas las solicitudes y selecciona el lote de las ''n'' primeras. Si no se llega a las ''n'' peticiones tras un tiempo se realiza la búsqueda. Su mayor desventaja es que aplaza las peticiones lejanas indefinidamente cuando ''n'' tiende a ifinito (''n'' -> ∞).

== N-SCAN (criterio del ascensor) ==

Dentro de cada lote de la lista de accesos, escogemos aquellos sectores que nos permita ascender y descender en la tabla, dando de esta manera prioridad a los sectores que se encuentren en la parte central de la pista.

|
| /\ | /\
| / \ | / \
| / \ | / \
___|/______\|/______\__
|
Nota: La gráfica resultante no tiene por qué ser simétrica, dependerá de los sectores a los que accedamos.

Nota2: El número de sectores integrantes de cada lote será el indicado por la N, ejemplo: 3-SCAN, 4-SCAN, etc.

== C-SCAN (Circular-Scan) ==

Da preferencia al ascenso o descenso, y se mantiene. Así se elimina el trato favorable a las partes centrales.

| |
| /| /| /| |\ |\ |\ |
| / | / | / | ó | \ | \ | \ |
| / | / | / | | \ | \ | \ |
___|/___|/___|_/___|_ ___|___\|__ \|___\|_
| |

Algún alma caritativa sube los ejemplos de clase antes del parcial??

No copié los datos, pero eran algo similar a esto:

== Ejemplos ==

Orden de acceso: 3, 80, 15, 45, 1, 79, 4

=== Solución FCFS ===

80 x
| / \ x
| / \ / \
50 / \ / \
| / \ x / \
| / \ / \ / \
20 / x \ / \
| x \ / x
___|/___________________x______________
|
| 3 80 15 45 1 79 4

=== Solución 3N-SCAN ===

80 x| |
| / |x |
| / | \ |
50 / | \ |
| / | x |
| / | \ |
20 x | \ |
| x | \ |x
___|/________|_______x|__
|
| 3 15 80|79 45 1|4

MejorasTiempoBusqueda

2011-06-07T21:28:41Z

Alexrdp: MejorasTiempoBusqueda trasladada a Mejoras de tiempos de búsqueda

#REDIRECCIÓN [[Mejoras de tiempos de búsqueda]]

Mejoras de tiempos de desplazamiento

2011-06-07T21:27:05Z

Alexrdp: /* Ejemplos */

Mejoras de tiempos de desplazamiento

2011-06-07T21:25:16Z

Alexrdp: Completar y ejemplos

== FCFS (por orden de llegada "FIFO") ==

Las peticiones se atienden en el mismo orden en que se reciben. Tiene el inconveniente de que se realizan muchos desplazamientos del cabezal, especialmente si se realizan accesos consecutivos a bloques muy alejados entre sí.

== SSTF (Shortest Seek Time First) ==

También conocido como atención por menor tiempo de búsqueda: Ordena todas las solicitudes y selecciona el lote de las ''n'' primeras. Si no se llega a las ''n'' peticiones tras un tiempo se realiza la búsqueda. Su mayor desventaja es que aplaza las peticiones lejanas indefinidamente cuando ''n'' tiende a ifinito (''n'' -> ∞).

== N-SCAN (criterio del ascensor) ==

Dentro de cada lote de la lista de accesos, escogemos aquellos sectores que nos permita ascender y descender en la tabla, dando de esta manera prioridad a los sectores que se encuentren en la parte central de la pista.

|
| /\ | /\
| / \ | / \
| / \ | / \
___|/______\|/______\__
|
Nota: La gráfica resultante no tiene por qué ser simétrica, dependerá de los sectores a los que accedamos.

Nota2: El número de sectores integrantes de cada lote será el indicado por la N, ejemplo: 3-SCAN, 4-SCAN, etc.

== C-SCAN (Circular-Scan) ==

Da preferencia al ascenso o descenso, y se mantiene. Así se elimina el trato favorable a las partes centrales.

| |
| /| /| /| |\ |\ |\ |
| / | / | / | ó | \ | \ | \ |
| / | / | / | | \ | \ | \ |
___|/___|/___|_/___|_ ___|___\|__ \|___\|_
| |

Algún alma caritativa sube los ejemplos de clase antes del parcial??

No copié los datos, pero eran algo similar a esto:

== Ejemplos ==

Orden de acceso: 3, 80, 15, 45, 1, 79, 4

=== Solución FCFS ===

80 x
| / \ x
| / \ / \
50 / \ / \
| / \ x / \
| / \ / \ / \
20 / x \ / \
| x \ / x
___|/___________________x_____________
|

=== Solución 3N-SCAN ===

80 x| |
| / |x |
| / | \ |
50 / | \ |
| / | x |
| / | \ |
20 x | \ |
| x | \ |x
___|/________|_______x|__
| | |

Discusión:Paginación

2011-06-07T13:47:13Z

Alexrdp:

¿Los mapas de bits no son de O(n) frente a las listas que son de O(1)? Lo digo porque:
*Para encontrar un espacio libre en el mapa de bits hay que recorrer toda la lista hasta encontrar una página libre, en cuyo caso hemos recorrido n elementos
*Para encontrar una página libre en la lista solo hay que hacer un pull sobre el FIFO de páginas libres, por lo tanto orden constante O(1)

Si lo pregunto y no lo corrijo directamente es porque en los apuntes que tomé en clase también tengo que los mapas de bits son de O(1)
[[Usuario:Ajaest|ajaest]] 11:51 7 jun 2011 (UTC)

Ambas son de orden constante: El número de elementos de un mapa de bits es siempre el mismo. Sería O(n) en el caso de que el número de bits fuese variable.
Por ejemplo, cuando se recorre un array en el que se sabe que el tamaño es 10, ese bucle se considera de orden constante. Por el contrario, en una lista enlazada, como no se sabe de antemano cuantos elementos se van a recorrer, el algoritmo resultante es de orden lineal --[[Usuario:Alexrdp|Alexrdp]] 13:47 7 jun 2011 (UTC)

Criterios de reemplazo

2011-06-06T16:24:10Z

Alexrdp:

= '''Criterios de reemplazo''' =

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

*[[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.

*[[sol_8|Solución]]

;Criterio del reloj: Igual que el de 2º oportunidad (FIFO + NRU sin bit M) pero mantenemos un puntero a la ultima pagina examinada.

*[[sol_reloj|Solución]]

;9.Criterio LFU ('''L'''east '''F'''recuently '''U'''sed): Hay dos variantes: una con bit R, estando este a 1 se incrementa un contador de uso, y otra en la que se aumenta dicho contador de uso por cada acceso.

*[[sol_9|Solución]]

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

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

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

*[[sol_10|Solución]]

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

Algoritmos de criterios de reemplazo

2011-06-06T16:13:19Z

Alexrdp:

= Criterios de reemplazo =

Algoritmos en Python para comprobar los ejercicios de [[Criterios de reemplazo|criterios de reemplazo]] del tema de [[Página Principal#Memoria virtual|memoria virtual]]. El contenido mínimo que debe tener el script es el siguiente:

<source lang="python">
from collections import deque
from random import choice

class Memoria:
def imprime_cabecera(self):
s = ' '
for i in range(len(self.marcos)):
s+= '__%s__ ' % (i+1)
print(s)
def __repr__(self):
s = '|'
for programa in self.marcos:
if programa:
s+= ' %s ' % programa
else:
s+= ' '
s+= '|'
s += '\n' + len(s)*'-'
return s

def ejecuta(memoria, secuencia):
fallos = 0
memoria.imprime_cabecera()
for programa in secuencia:
fallos += memoria.add(programa)
print(memoria)
print('\nTasa de fallos = %s/%s\n\n' % (fallos, len(secuencia)))

secuencia = [2,2,3,1,1,3,4,5,1,1,2,3,4]
</source>

== Criterio MRU (Most Recently Used) ==

<source lang="python">
class MemoriaMRU(Memoria):
def __init__(self, i):
self.pila = []
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
indice = self.marcos.index(self.pila.pop())
self.marcos[indice] = False

self.marcos[self.marcos.index(False)] = programa

# Insertamos el programa en la pila
if programa in self.pila:
self.pila.remove(programa)
self.pila.append(programa)

return fallo
</source>

Código de prueba:

<source lang="python">
>>> m1 = MemoriaMRU(4)
>>> ejecuta(m1, secuencia)
</source>

== Criterio de selección estocástica ==

<source lang="python">
class MemoriaEstocastica(Memoria):
def __init__(self, i):
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
rand = choice(range(len(self.marcos)))
self.marcos[rand] = programa
else:
self.marcos[self.marcos.index(False)] = programa
return fallo
</source>

Código de prueba:

<source lang="python">
>>> m2 = MemoriaEstocastica(4)
>>> ejecuta(m2, secuencia)
</source>

== Criterio por orden de carga FIFO ==

<source lang="python">
class MemoriaFIFO(Memoria):
def __init__(self, i):
self.cola = deque([])
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
indice = self.marcos.index(self.cola.popleft())
self.marcos[indice] = False

self.marcos[self.marcos.index(False)] = programa

# Insertamos el programa en la cola
if not programa in self.cola:
self.cola.append(programa)

return fallo
</source>

Código de prueba:

<source lang="python">
>>> m3 = MemoriaFIFO(4)
>>> ejecuta(m3, secuencia)
</source>

== Criterio de Sustitución por envejecimiento ==

<source lang="python">
class Marco:
def __init__(self, tam):
self.programa = False
self.tam = tam
self.registro = [0] * tam
def inserta(self, programa):
self.programa = programa
self.registro = [1] + ([0] * (self.tam-1))
def actualiza(self):
self.registro[0] = 1
def desplaza(self):
self.registro = [0] + self.registro[:-1]
def __gt__(self,marco):
for i in range(self.tam):
if self.registro[i] > marco.registro[i]:
return True
return False
def __repr__(self):
if self.programa:
return '%s %s' %(self.programa, self.registro)
else:
return ' ' * (self.tam*3 + 2)

class Tabla:
def __init__(self, cantidad, tam_registros):
self.lista = []
for i in range(cantidad):
self.lista.append(Marco(tam_registros))

def addPrograma(self, programa):
esta = False
indice = 0
for marco in self.lista:
if programa == marco.programa:
esta = True
break
indice += 1
if esta:
self.lista[indice].actualiza()
return 0
else:
print("Fallo!")
indice = self.lista.index(self.minimo())
self.lista[indice].inserta(programa)
return 1

def minimo(self):
res = self.lista[0]
for marco in self.lista[1:]:
if res > marco:
res = marco
return res

def __repr__(self):
s = ''
for marco in self.lista:
s += '| %s ' % marco
s += '|\n' + '-'*(len(s)+1)
return s

class AproximacionDiscretaLRU:
def __init__(self, cantidad, periodo, tam_registros = 3):
self.tabla = Tabla(cantidad, tam_registros)
self.periodo = periodo

def ejecuta(self, lista_programas):
i = 0
fallos = 0
for programa in lista_programas:
if i%self.periodo == 0:
for marco in self.tabla.lista:
marco.desplaza()
i+=1
fallos += self.tabla.addPrograma(programa)
print(self.tabla)
print("\nTasa de fallos: %s/%s" % (fallos, len(lista_programas)))

</source>

Si ejecutamos el ejemplo visto en clase mostraría:

<source lang="python">
>>> alg = AproximacionDiscretaLRU(4, 4)
>>> alg.ejecuta([2,2,3,1,1,3,4,5,1,1,2,3,4])
Fallo!
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | 1 [1, 0, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [0, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 4 [1, 0, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 5 [1, 0, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [1, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [0, 1, 1] | 1 [0, 1, 1] | 4 [1, 0, 0] |
---------------------------------------------------------

Tasa de fallos: 6/13
</source>

La diferencia con respecto a la solución de clase es que la resolución en caso de empate es elegir el marco con índice menor.

Algoritmos de criterios de reemplazo

2011-06-06T16:07:31Z

Alexrdp: Criterio por orden de carga FIFO

Algoritmosen Python para comprobar los ejercicios de [[Criterios de reemplazo|criterios de reemplazo]] del tema de '''Memoria Virtual'''. El contenido mínimo que debe tener el script es el siguiente:

<source lang="python">
from collections import deque
from random import choice

class Memoria:
def imprime_cabecera(self):
s = ' '
for i in range(len(self.marcos)):
s+= '__%s__ ' % (i+1)
print(s)
def __repr__(self):
s = '|'
for programa in self.marcos:
if programa:
s+= ' %s ' % programa
else:
s+= ' '
s+= '|'
s += '\n' + len(s)*'-'
return s

def ejecuta(memoria, secuencia):
fallos = 0
memoria.imprime_cabecera()
for programa in secuencia:
fallos += memoria.add(programa)
print(memoria)
print('\nTasa de fallos = %s/%s\n\n' % (fallos, len(secuencia)))

secuencia = [2,2,3,1,1,3,4,5,1,1,2,3,4]
</source>

== Criterio MRU (Most Recently Used) ==

<source lang="python">
class MemoriaMRU(Memoria):
def __init__(self, i):
self.pila = []
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
indice = self.marcos.index(self.pila.pop())
self.marcos[indice] = False

self.marcos[self.marcos.index(False)] = programa

# Insertamos el programa en la pila
if programa in self.pila:
self.pila.remove(programa)
self.pila.append(programa)

return fallo
</source>

Código de prueba:

<source lang="python">
>>> m1 = MemoriaMRU(4)
>>> ejecuta(m1, secuencia)
</source>

== Criterio de selección estocástica ==

<source lang="python">
class MemoriaEstocastica(Memoria):
def __init__(self, i):
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
rand = choice(range(len(self.marcos)))
self.marcos[rand] = programa
else:
self.marcos[self.marcos.index(False)] = programa
return fallo
</source>

Código de prueba:

<source lang="python">
>>> m2 = MemoriaEstocastica(4)
>>> ejecuta(m2, secuencia)
</source>

== Criterio por orden de carga FIFO ==

<source lang="python">
class MemoriaFIFO(Memoria):
def __init__(self, i):
self.cola = deque([])
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
indice = self.marcos.index(self.cola.popleft())
self.marcos[indice] = False

self.marcos[self.marcos.index(False)] = programa

# Insertamos el programa en la cola
if not programa in self.cola:
self.cola.append(programa)

return fallo
</source>

Código de prueba:

<source lang="python">
>>> m3 = MemoriaFIFO(4)
>>> ejecuta(m3, secuencia)
</source>

----

== Criterio de Sustitución por envejecimiento ==

<source lang="python">
class Marco:
def __init__(self, tam):
self.programa = False
self.tam = tam
self.registro = [0] * tam
def inserta(self, programa):
self.programa = programa
self.registro = [1] + ([0] * (self.tam-1))
def actualiza(self):
self.registro[0] = 1
def desplaza(self):
self.registro = [0] + self.registro[:-1]
def __gt__(self,marco):
for i in range(self.tam):
if self.registro[i] > marco.registro[i]:
return True
return False
def __repr__(self):
if self.programa:
return '%s %s' %(self.programa, self.registro)
else:
return ' ' * (self.tam*3 + 2)

class Tabla:
def __init__(self, cantidad, tam_registros):
self.lista = []
for i in range(cantidad):
self.lista.append(Marco(tam_registros))

def addPrograma(self, programa):
esta = False
indice = 0
for marco in self.lista:
if programa == marco.programa:
esta = True
break
indice += 1
if esta:
self.lista[indice].actualiza()
return 0
else:
print("Fallo!")
indice = self.lista.index(self.minimo())
self.lista[indice].inserta(programa)
return 1

def minimo(self):
res = self.lista[0]
for marco in self.lista[1:]:
if res > marco:
res = marco
return res

def __repr__(self):
s = ''
for marco in self.lista:
s += '| %s ' % marco
s += '|\n' + '-'*(len(s)+1)
return s

class AproximacionDiscretaLRU:
def __init__(self, cantidad, periodo, tam_registros = 3):
self.tabla = Tabla(cantidad, tam_registros)
self.periodo = periodo

def ejecuta(self, lista_programas):
i = 0
fallos = 0
for programa in lista_programas:
if i%self.periodo == 0:
for marco in self.tabla.lista:
marco.desplaza()
i+=1
fallos += self.tabla.addPrograma(programa)
print(self.tabla)
print("\nTasa de fallos: %s/%s" % (fallos, len(lista_programas)))

</source>

Si ejecutamos el ejemplo visto en clase mostraría:

<source lang="python">
>>> alg = AproximacionDiscretaLRU(4, 4)
>>> alg.ejecuta([2,2,3,1,1,3,4,5,1,1,2,3,4])
Fallo!
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | 1 [1, 0, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [0, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 4 [1, 0, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 5 [1, 0, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [1, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [0, 1, 1] | 1 [0, 1, 1] | 4 [1, 0, 0] |
---------------------------------------------------------

Tasa de fallos: 6/13
</source>

La diferencia con respecto a la solución de clase es que la resolución en caso de empate es elegir el marco con índice menor.

Algoritmos de criterios de reemplazo

2011-06-06T16:01:04Z

Alexrdp: Añadir algoritmos MRU y estocástico

Algoritmosen Python para comprobar los ejercicios de [[Criterios de reemplazo|criterios de reemplazo]] del tema de '''Memoria Virtual'''. El contenido mínimo que debe tener el script es el siguiente:

<source lang="python">
from collections import deque
from random import choice

class Memoria:
def imprime_cabecera(self):
s = ' '
for i in range(len(self.marcos)):
s+= '__%s__ ' % (i+1)
print(s)
def __repr__(self):
s = '|'
for programa in self.marcos:
if programa:
s+= ' %s ' % programa
else:
s+= ' '
s+= '|'
s += '\n' + len(s)*'-'
return s

def ejecuta(memoria, secuencia):
fallos = 0
memoria.imprime_cabecera()
for programa in secuencia:
fallos += memoria.add(programa)
print(memoria)
print('\nTasa de fallos = %s/%s\n\n' % (fallos, len(secuencia)))

secuencia = [2,2,3,1,1,3,4,5,1,1,2,3,4]
</source>

== Criterio MRU (Most Recently Used) ==

<source lang="python">
class MemoriaMRU(Memoria):
def __init__(self, i):
self.pila = []
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
indice = self.marcos.index(self.pila.pop())
self.marcos[indice] = False

self.marcos[self.marcos.index(False)] = programa

# Insertamos el programa en la pila
if programa in self.pila:
self.pila.remove(programa)
self.pila.append(programa)

return fallo
</source>

Código de prueba:

<source lang="python">
>>> m1 = MemoriaMRU(4)
>>> ejecuta(m1, secuencia)
</source>

== Criterio de selección estocástica ==

<source lang="python">
class MemoriaEstocastica(Memoria):
def __init__(self, i):
self.marcos = [False] * i
def add(self, programa):
fallo = 0
# Fallo de pagina
if not programa in self.marcos:
fallo = 1
if not False in self.marcos:
rand = choice(range(len(self.marcos)))
self.marcos[rand] = programa
else:
self.marcos[self.marcos.index(False)] = programa
return fallo
</source>

Código de prueba:

<source lang="python">
>>> m2 = MemoriaEstocastica(4)
>>> ejecuta(m2, secuencia)
</source>

----

== Criterio de Sustitución por envejecimiento ==

<source lang="python">
class Marco:
def __init__(self, tam):
self.programa = False
self.tam = tam
self.registro = [0] * tam
def inserta(self, programa):
self.programa = programa
self.registro = [1] + ([0] * (self.tam-1))
def actualiza(self):
self.registro[0] = 1
def desplaza(self):
self.registro = [0] + self.registro[:-1]
def __gt__(self,marco):
for i in range(self.tam):
if self.registro[i] > marco.registro[i]:
return True
return False
def __repr__(self):
if self.programa:
return '%s %s' %(self.programa, self.registro)
else:
return ' ' * (self.tam*3 + 2)

class Tabla:
def __init__(self, cantidad, tam_registros):
self.lista = []
for i in range(cantidad):
self.lista.append(Marco(tam_registros))

def addPrograma(self, programa):
esta = False
indice = 0
for marco in self.lista:
if programa == marco.programa:
esta = True
break
indice += 1
if esta:
self.lista[indice].actualiza()
return 0
else:
print("Fallo!")
indice = self.lista.index(self.minimo())
self.lista[indice].inserta(programa)
return 1

def minimo(self):
res = self.lista[0]
for marco in self.lista[1:]:
if res > marco:
res = marco
return res

def __repr__(self):
s = ''
for marco in self.lista:
s += '| %s ' % marco
s += '|\n' + '-'*(len(s)+1)
return s

class AproximacionDiscretaLRU:
def __init__(self, cantidad, periodo, tam_registros = 3):
self.tabla = Tabla(cantidad, tam_registros)
self.periodo = periodo

def ejecuta(self, lista_programas):
i = 0
fallos = 0
for programa in lista_programas:
if i%self.periodo == 0:
for marco in self.tabla.lista:
marco.desplaza()
i+=1
fallos += self.tabla.addPrograma(programa)
print(self.tabla)
print("\nTasa de fallos: %s/%s" % (fallos, len(lista_programas)))

</source>

Si ejecutamos el ejemplo visto en clase mostraría:

<source lang="python">
>>> alg = AproximacionDiscretaLRU(4, 4)
>>> alg.ejecuta([2,2,3,1,1,3,4,5,1,1,2,3,4])
Fallo!
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | 1 [1, 0, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [0, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 4 [1, 0, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 5 [1, 0, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [1, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [0, 1, 1] | 1 [0, 1, 1] | 4 [1, 0, 0] |
---------------------------------------------------------

Tasa de fallos: 6/13
</source>

La diferencia con respecto a la solución de clase es que la resolución en caso de empate es elegir el marco con índice menor.

Sol 3

2011-06-06T15:50:28Z

Alexrdp:

Solución:
6/13 = 0'4615
--[[Usuario:Jorcalmar|Jorcalmar]] 16:52 2 jun 2011 (UTC)

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

___1____ 2_____3_____4___
1º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1
Pagina 2 |_____|_____|_____|_____|
2º Acceso | | | | |
Acceso a: | 2 | | | | Nª de fallos: 1
Pagina 2 |_____|_____|_____|_____|
3º Acceso | | | | |
Acceso a: | 2 | 3 | | | Nª de fallos: 2
Pagina 3 |_____|_____|_____|_____|
4º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3
Pagina 1 |_____|_____|_____|_____|
5º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3
Pagina 1 |_____|_____|_____|_____|
6º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | | Nª de fallos: 3
Pagina 3 |_____|_____|_____|_____|
7º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | 4 | Nª de fallos: 4
Pagina 4 |_____|_____|_____|_____|
8º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | 5 | Nª de fallos: 5
Pagina 5 |_____|_____|_____|_____|
9º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | 5 | Nª de fallos: 5
Pagina 1 |_____|_____|_____|_____|
10º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | 5 | Nª de fallos: 5
Pagina 1 |_____|_____|_____|_____|
11º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | 5 | Nª de fallos: 5
Pagina 2 |_____|_____|_____|_____|
12º Acceso | | | | |
Acceso a: | 2 | 3 | 1 | 5 | Nª de fallos: 5
Pagina 3 |_____|_____|_____|_____|
13º Acceso | | | | |
Acceso a: | 2 | 4 | 1 | 5 | Nª de fallos: 6
Pagina 4 |_____|_____|_____|_____|

Tasa de fallos = 6/13 = 0'4615
--[[Usuario:Fcoramlop|Fcoramlop]] 21:38 4 jun 2011 (UTC)

Usuario: lcarlosp (jejeje, que no se como se pone el enlace)

Yo diría que son 6 fallos -- [[Usuario:PCamino|pablo]]

Cuando en un criterio de reemplazo se usa una pila (MRU) o una cola (orden de carga), si se vuelve a acceder a una página que ya está en la lista, ¿se borra la página y se vuelve a insertar, o se deja como está?.

Por ejemplo, para la secuencia: 1,2,3,1,4; la cola del criterio FIFO sería así?
<pre>
Acceso a 1 -> Cola = [1]
Acceso a 2 -> Cola = [1,2]
Acceso a 3 -> Cola = [1,2,3]
Acceso a 1 -> Cola = [1,2,3]
Acceso a 4 -> Cola = [1,2,3,4]
</pre>
--[[Usuario:Alexrdp|Alexrdp]] 15:50 6 jun 2011 (UTC)

[[Criterios_de_reemplazo|Volver]]

Algoritmos de criterios de reemplazo

2011-06-06T14:25:51Z

Alexrdp: /* Criterio de Sustitución por envejecimiento */

Scripts en Python para comprobar los ejercicios de criterios de reemplazo

== Criterio de Sustitución por envejecimiento ==

<source lang="python">
class Marco:
def __init__(self, tam):
self.programa = False
self.tam = tam
self.registro = [0] * tam
def inserta(self, programa):
self.programa = programa
self.registro = [1] + ([0] * (self.tam-1))
def actualiza(self):
self.registro[0] = 1
def desplaza(self):
self.registro = [0] + self.registro[:-1]
def __gt__(self,marco):
for i in range(self.tam):
if self.registro[i] > marco.registro[i]:
return True
return False
def __repr__(self):
if self.programa:
return '%s %s' %(self.programa, self.registro)
else:
return ' ' * (self.tam*3 + 2)

class Tabla:
def __init__(self, cantidad, tam_registros):
self.lista = []
for i in range(cantidad):
self.lista.append(Marco(tam_registros))

def addPrograma(self, programa):
esta = False
indice = 0
for marco in self.lista:
if programa == marco.programa:
esta = True
break
indice += 1
if esta:
self.lista[indice].actualiza()
return 0
else:
print("Fallo!")
indice = self.lista.index(self.minimo())
self.lista[indice].inserta(programa)
return 1

def minimo(self):
res = self.lista[0]
for marco in self.lista[1:]:
if res > marco:
res = marco
return res

def __repr__(self):
s = ''
for marco in self.lista:
s += '| %s ' % marco
s += '|\n' + '-'*(len(s)+1)
return s

class AproximacionDiscretaLRU:
def __init__(self, cantidad, periodo, tam_registros = 3):
self.tabla = Tabla(cantidad, tam_registros)
self.periodo = periodo

def ejecuta(self, lista_programas):
i = 0
fallos = 0
for programa in lista_programas:
if i%self.periodo == 0:
for marco in self.tabla.lista:
marco.desplaza()
i+=1
fallos += self.tabla.addPrograma(programa)
print(self.tabla)
print("\nTasa de fallos: %s/%s" % (fallos, len(lista_programas)))

</source>

Si ejecutamos el ejemplo visto en clase mostraría:

<source lang="python">
>>> alg = AproximacionDiscretaLRU(4, 4)
>>> alg.ejecuta([2,2,3,1,1,3,4,5,1,1,2,3,4])
Fallo!
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | 1 [1, 0, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [0, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 4 [1, 0, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 5 [1, 0, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [1, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [0, 1, 1] | 1 [0, 1, 1] | 4 [1, 0, 0] |
---------------------------------------------------------

Tasa de fallos: 6/13
</source>

La diferencia con respecto a la solución de clase es que la resolución en caso de empate es elegir el marco con índice menor.

Buffer Overflow y bit NX

2011-06-02T20:48:23Z

Alexrdp: /* Solución */

= Buffer Overflows =

== Definición y causa ==
Los desbordamientos de búfer es una vulnerabilidad presente cuando se escribe en un búfer sin validar el tamaño del contenido.
Esto puede hacer que si se introduce un dato lo suficientemente grande, el búfer se desborde, dando como resultado que se sobreescriba con código del atacante.
Lo cual constituye un gran problema de seguridad cuando el programa se ejecuta con privilegios de superusuario.

Este error de programación de encuentra comúnmente en programas que gestionan su propio uso de la memoria (P. ej, C/C++).
Según la OWASP (Proyecto de código abierto sobre seguridad web) es una de las vulnerabilidades más comunes, con un riesgo de explotación muy alto y variado, aún siendo una de las más antiguas y conocidas.

== Ejemplo ==
<source lang="c">
#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[])
{
char buffer[5];
if(argc != 2)
{
fprintf(stderr, "USO: %s cadena\n", argv[0]);
return -1;
}
strcpy(buffer, argv[1]); // Cadenas de 5 o más caracteres causarán desbordamiento
return 0;
}
</source>

== Otro tipo de buffer overflow: Stack buffer overflow ==

=== Ejemplo modificando el código anterior ===
<source lang="c">
#include <stdio.h>
#include <string.h>

void mi_funcion(char *param)
{
char buffer[5];
strcpy(buffer, param);
}

int main(int argc, char *argv[])
{
if(argc != 2)
{
fprintf(stderr, "USO: %s cadena\n", argv[0]);
return -1;
}
mi_función(argv[1]);
return 0;
}
</source>

=== Funcionamiento del exploit ===
Contenido de la pila:
<pre>
_______
| |
|_______| <- vbles. locales mi_funcion (char buffer[] y char *param)
|_______| <- dirección de retorno (dir. siguiente instrucción después de mi_funcion)
| |
|_______| <- vbles. locales main
</pre>
Si se desborda el contenido de buffer:
<pre>
_______
|xxxxxxx|
|xxxxxxx| <- vbles. locales mi_funcion
|xxxxxxx| <- dirección de retorno
| |
|_______| <- vbles. locales main
</pre>
x = Código introducido por el atacante

Con lo cual, se han sobreescrito las variables de mi_funcion y la dirección de retorno, que es a la que se hará un jump después de ejecutar el código de mi_funcion.
Es decir, estamos permitiendo al atacante saltar a una dirección arbitraria y ejecutar el código que contenga.

No confundir esta vulnerabilidad con un desbordamiento de pila o stack overflow, esto último ocurre cuando la pila de
invocaciones se desborda por errores como recursión infinita o parámetros de retorno de demasiado tamaño.

== Solución ==
Una máxima en seguridad informática es validar siempre los datos introducidos por el usuario. En este caso, bastaría con sustituir la línea de strcpy por:
<pre>
...
strncpy(buffer, argv[1], sizeof(buffer));
buffer[sizeof(buffer) - 1] = '\0'; // Caracter nulo
...
</pre>
De esta forma, nos aseguramos que el contenido del buffer no se desborde al copiar argv[1] en él.

= Bit NX =
La tecnología NX (No eXecutable) se introdujo para establecer determinadas zonas de memoria como no ejecutables, y así prevenir los ataques de tipo buffer overflow.
Este bit es el último de cada entrada de la tabla de páginas, y si se encuentra puesto a 1 significa que el contenido de dicha página se considerará como datos y por tanto no podrá ser ejecutado.
En el caso de arquitecturas como IA32, al basar inicialmente la protección de memoria en el mecanismo de segmentación, hizo que sus servidores sufrieran muchos ataques de buffer overflow
hasta que se dió mayor control al mecanismo de paginación incluyendo esta tecnología (En el caso de Intel, llamada XD bit-Executing Disabled).

El núcleo de Linux soporta esta tecnología para arquitecturas IA-32 e IA-64. Si el hardware no proporciona la tecnología NX, el kernel para la arquitectura de 32 bits permite emularla por software.

= Fuentes =

* Securing Ajax Applications (O'Reilly)
* http://en.wikipedia.org/wiki/Buffer_overflow
* https://www.owasp.org/index.php/Buffer_Overflow
* http://en.wikipedia.org/wiki/NX_bit
* Apartados 2.11 y 4.4 de los apuntes de teoría de TPBN

Buffer Overflow y bit NX

2011-06-02T20:34:21Z

Alexrdp: Artículo propuesto en clase

= Buffer Overflows =

== Definición y causa ==
Los desbordamientos de búfer es una vulnerabilidad presente cuando se escribe en un búfer sin validar el tamaño del contenido.
Esto puede hacer que si se introduce un dato lo suficientemente grande, el búfer se desborde, dando como resultado que se sobreescriba con código del atacante.
Lo cual constituye un gran problema de seguridad cuando el programa se ejecuta con privilegios de superusuario.

Este error de programación de encuentra comúnmente en programas que gestionan su propio uso de la memoria (P. ej, C/C++).
Según la OWASP (Proyecto de código abierto sobre seguridad web) es una de las vulnerabilidades más comunes, con un riesgo de explotación muy alto y variado, aún siendo una de las más antiguas y conocidas.

== Ejemplo ==
<source lang="c">
#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[])
{
char buffer[5];
if(argc != 2)
{
fprintf(stderr, "USO: %s cadena\n", argv[0]);
return -1;
}
strcpy(buffer, argv[1]); // Cadenas de 5 o más caracteres causarán desbordamiento
return 0;
}
</source>

== Otro tipo de buffer overflow: Stack buffer overflow ==

=== Ejemplo modificando el código anterior ===
<source lang="c">
#include <stdio.h>
#include <string.h>

void mi_funcion(char *param)
{
char buffer[5];
strcpy(buffer, param);
}

int main(int argc, char *argv[])
{
if(argc != 2)
{
fprintf(stderr, "USO: %s cadena\n", argv[0]);
return -1;
}
mi_función(argv[1]);
return 0;
}
</source>

=== Funcionamiento del exploit ===
Contenido de la pila:
<pre>
_______
| |
|_______| <- vbles. locales mi_funcion (char buffer[] y char *param)
|_______| <- dirección de retorno (dir. siguiente instrucción después de mi_funcion)
| |
|_______| <- vbles. locales main
</pre>
Si se desborda el contenido de buffer:
<pre>
_______
|xxxxxxx|
|xxxxxxx| <- vbles. locales mi_funcion
|xxxxxxx| <- dirección de retorno
| |
|_______| <- vbles. locales main
</pre>
x = Código introducido por el atacante

Con lo cual, se han sobreescrito las variables de mi_funcion y la dirección de retorno, que es a la que se hará un jump después de ejecutar el código de mi_funcion.
Es decir, estamos permitiendo al atacante saltar a una dirección arbitraria y ejecutar el código que contenga.

No confundir esta vulnerabilidad con un desbordamiento de pila o stack overflow, esto último ocurre cuando la pila de
invocaciones se desborda por errores como recursión infinita o parámetros de retorno de demasiado tamaño.

== Solución ==
Una máxima en seguridad informática es validar siempre los datos introducidos por el usuario. En este caso, bastaría con sustituir la línea de strcpy por:
<pre>
...
strcpy(buffer, argv[1], sizeof(buffer));
buffer[sizeof(buffer) - 1] = '\0'; // Caracter nulo
...
</pre>
De esta forma, nos aseguramos que el contenido del buffer no se desborde al copiar argv[1] en él.

= Bit NX =
La tecnología NX (No eXecutable) se introdujo para establecer determinadas zonas de memoria como no ejecutables, y así prevenir los ataques de tipo buffer overflow.
Este bit es el último de cada entrada de la tabla de páginas, y si se encuentra puesto a 1 significa que el contenido de dicha página se considerará como datos y por tanto no podrá ser ejecutado.
En el caso de arquitecturas como IA32, al basar inicialmente la protección de memoria en el mecanismo de segmentación, hizo que sus servidores sufrieran muchos ataques de buffer overflow
hasta que se dió mayor control al mecanismo de paginación incluyendo esta tecnología (En el caso de Intel, llamada XD bit-Executing Disabled).

El núcleo de Linux soporta esta tecnología para arquitecturas IA-32 e IA-64. Si el hardware no proporciona la tecnología NX, el kernel para la arquitectura de 32 bits permite emularla por software.

= Fuentes =

* Securing Ajax Applications (O'Reilly)
* http://en.wikipedia.org/wiki/Buffer_overflow
* https://www.owasp.org/index.php/Buffer_Overflow
* http://en.wikipedia.org/wiki/NX_bit
* Apartados 2.11 y 4.4 de los apuntes de teoría de TPBN

Wiki de Sistemas Operativos:Portal de la comunidad

2011-06-02T20:29:27Z

Alexrdp:

En esta página se añadirá contenido relacionado con la asignatura, que no se encuentre dentro del temario.

== Material complementario ==

* [[Algoritmos de criterios de reemplazo]]
* [[Buffer Overflow y bit NX|Seguridad informática: Buffer Overflow y bit NX]]

Algoritmos de criterios de reemplazo

2011-06-02T20:26:50Z

Alexrdp: /* Criterio de Aproximacion discreta LRU */

Scripts en Python para comprobar los ejercicios de criterios de reemplazo

== Criterio de Aproximacion discreta LRU ==

<source lang="python">
class Marco:
def __init__(self, tam):
self.programa = False
self.tam = tam
self.registro = [0] * tam
def inserta(self, programa):
self.programa = programa
self.registro = [1] + ([0] * (self.tam-1))
def actualiza(self):
self.registro[0] = 1
def desplaza(self):
self.registro = [0] + self.registro[:-1]
def __gt__(self,marco):
for i in range(self.tam):
if self.registro[i] > marco.registro[i]:
return True
return False
def __repr__(self):
if self.programa:
return '%s %s' %(self.programa, self.registro)
else:
return ' ' * (self.tam*3 + 2)

class Tabla:
def __init__(self, cantidad, tam_registros):
self.lista = []
for i in range(cantidad):
self.lista.append(Marco(tam_registros))

def addPrograma(self, programa):
esta = False
indice = 0
for marco in self.lista:
if programa == marco.programa:
esta = True
break
indice += 1
if esta:
self.lista[indice].actualiza()
return 0
else:
print("Fallo!")
indice = self.lista.index(self.minimo())
self.lista[indice].inserta(programa)
return 1

def minimo(self):
res = self.lista[0]
for marco in self.lista[1:]:
if res > marco:
res = marco
return res

def __repr__(self):
s = ''
for marco in self.lista:
s += '| %s ' % marco
s += '|\n' + '-'*(len(s)+1)
return s

class AproximacionDiscretaLRU:
def __init__(self, cantidad, periodo, tam_registros = 3):
self.tabla = Tabla(cantidad, tam_registros)
self.periodo = periodo

def ejecuta(self, lista_programas):
i = 0
fallos = 0
for programa in lista_programas:
if i%self.periodo == 0:
for marco in self.tabla.lista:
marco.desplaza()
i+=1
fallos += self.tabla.addPrograma(programa)
print(self.tabla)
print("\nTasa de fallos: %s/%s" % (fallos, len(lista_programas)))

</source>

Si ejecutamos el ejemplo visto en clase mostraría:

<source lang="python">
>>> alg = AproximacionDiscretaLRU(4, 4)
>>> alg.ejecuta([2,2,3,1,1,3,4,5,1,1,2,3,4])
Fallo!
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | 1 [1, 0, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [0, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 4 [1, 0, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 5 [1, 0, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [1, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [0, 1, 1] | 1 [0, 1, 1] | 4 [1, 0, 0] |
---------------------------------------------------------

Tasa de fallos: 6/13
</source>

La diferencia con respecto a la solución de clase es que la resolución en caso de empate es elegir el marco con índice menor.

Wiki de Sistemas Operativos:Portal de la comunidad

2011-06-02T20:26:22Z

Alexrdp: Página creada con 'En esta página se añadirá contenido relacionado con la asignatura, que no se encuentre dentro del temario. == Material complementario == * [[Algoritmos de criterios de reem…'

En esta página se añadirá contenido relacionado con la asignatura, que no se encuentre dentro del temario.

== Material complementario ==

* [[Algoritmos de criterios de reemplazo]]
* [[Stack Overflow y bit NX|Seguridad informática: Stack Overflow y bit NX]]

Algoritmos de criterios de reemplazo

2011-06-02T20:19:56Z

Alexrdp: Algoritmo aproximacion discreta LRU

== Criterio de Aproximacion discreta LRU ==

<source lang="python">
class Marco:
def __init__(self, tam):
self.programa = False
self.tam = tam
self.registro = [0] * tam
def inserta(self, programa):
self.programa = programa
self.registro = [1] + ([0] * (self.tam-1))
def actualiza(self):
self.registro[0] = 1
def desplaza(self):
self.registro = [0] + self.registro[:-1]
def __gt__(self,marco):
for i in range(self.tam):
if self.registro[i] > marco.registro[i]:
return True
return False
def __repr__(self):
if self.programa:
return '%s %s' %(self.programa, self.registro)
else:
return ' ' * (self.tam*3 + 2)

class Tabla:
def __init__(self, cantidad, tam_registros):
self.lista = []
for i in range(cantidad):
self.lista.append(Marco(tam_registros))

def addPrograma(self, programa):
esta = False
indice = 0
for marco in self.lista:
if programa == marco.programa:
esta = True
break
indice += 1
if esta:
self.lista[indice].actualiza()
return 0
else:
print("Fallo!")
indice = self.lista.index(self.minimo())
self.lista[indice].inserta(programa)
return 1

def minimo(self):
res = self.lista[0]
for marco in self.lista[1:]:
if res > marco:
res = marco
return res

def __repr__(self):
s = ''
for marco in self.lista:
s += '| %s ' % marco
s += '|\n' + '-'*(len(s)+1)
return s

class AproximacionDiscretaLRU:
def __init__(self, cantidad, periodo, tam_registros = 3):
self.tabla = Tabla(cantidad, tam_registros)
self.periodo = periodo

def ejecuta(self, lista_programas):
i = 0
fallos = 0
for programa in lista_programas:
if i%self.periodo == 0:
for marco in self.tabla.lista:
marco.desplaza()
i+=1
fallos += self.tabla.addPrograma(programa)
print(self.tabla)
print("\nTasa de fallos: %s/%s" % (fallos, len(lista_programas)))

</source>

Si ejecutamos el ejemplo visto en clase mostraría:

<source lang="python">
>>> alg = AproximacionDiscretaLRU(4, 4)
>>> alg.ejecuta([2,2,3,1,1,3,4,5,1,1,2,3,4])
Fallo!
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
| 2 [1, 0, 0] | | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | | |
---------------------------------------------------------
Fallo!
| 2 [1, 0, 0] | 3 [1, 0, 0] | 1 [1, 0, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [0, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 4 [1, 0, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [1, 1, 0] | 1 [1, 1, 0] | 5 [1, 0, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [0, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [0, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
| 2 [1, 0, 1] | 3 [1, 1, 1] | 1 [1, 1, 1] | 5 [0, 1, 0] |
---------------------------------------------------------
Fallo!
| 2 [0, 1, 0] | 3 [0, 1, 1] | 1 [0, 1, 1] | 4 [1, 0, 0] |
---------------------------------------------------------

Tasa de fallos: 6/13
</source>

La diferencia con respecto a la solución de clase es que la resolución en caso de empate es elegir el marco con índice menor.

SO multiprogramables con particiones variables

2011-05-16T15:57:35Z

Alexrdp: /* Definición */

== Definición ==

En este tipo de sistemas, las particiones para cada proceso se van creando a medida que son asignadas al procesador. Como ventaja principal tiene 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 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. 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 correspondiente. 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

SO multiprogramables con particiones variables

2011-05-16T15:48:40Z

Alexrdp:

== Definición ==

En este tipo de sistemas, las particiones para cada proceso se van creando a medida que son asignadas al procesador. Como ventaja principal tiene 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 para poder unificar todas las partes que han quedado libres y así reciclar las particiones que quedaron huérfanas.

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

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

SO multiprogramables con particiones fijas

2011-05-16T15:40:20Z

Alexrdp:

La memoria se encuentra dividida en particiones, en cada una habrá un proceso.

=Estrategias=
*Cancelación: "no hay memoria, prueba luego"
*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'''

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

SO multiprogramables con particiones fijas

2011-05-16T15:30:01Z

Alexrdp: /* Criterios de asignación */

SO multiprogramables con particiones variables

2011-05-16T14:59:47Z

Alexrdp: /* Criterios de asignació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. 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 correspondiente. 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

SO multiprogramables con particiones variables

2011-05-16T14:54:06Z

Alexrdp:

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

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

SO multiprogramables con particiones variables

2011-05-16T14:47:18Z

Alexrdp:

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

- '''Ajuste rápido'''

- '''Método de los compañeros'''

SO multiprogramables con particiones variables

2011-05-16T14:35:29Z

Alexrdp: Página nueva: Esto es un esbozo. == Criterios de asignación == - Primer ajuste Consiste en Las dos principales desventajas son su alto desperdicio interno, y el elevado uso de las primeras posi...

Esto es un esbozo.

== Criterios de asignación ==

- Primer ajuste
Consiste en
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 por la posición de la última asignación

- Mejor ajuste

- Peor ajuste

- Ajuste rápido

- Método de los compañeros

Algoritmo para averiguar interbloqueo

2011-04-27T15:04:10Z

Alexrdp: /* Algoritmo en Python */

== Algoritmo en C# ==

<source lang="csharp">
int nRecursos;
int nProcesos;
List<List<int>> asignados = new List<List<int>>();
List<List<int>> maximos = new List<List<int>>();
List<int> disponibles = new List<int>();

Random r = new Random();

//Generamos las matrices aleatoriamente
for (int j1 = 0; j1 < nRecursos;j1++)
{
disponibles.Add(r.Next(0, nRecursos));
}
for (int i = 0; i < nProcesos; i++)
{
asignados.Add(new List<int>());
maximos.Add(new List<int>());
for (int j = 0; j < nRecursos; j++)
{
asignados[i].Add(r.Next(0, nRecursos));
maximos[i].Add(r.Next(0, nRecursos));
}
}

bool aux = true;
for (int proc = 0; proc < nProcesos; proc++)
{
aux = true;
for (int recur = 0; recur < nRecursos; recur++)
{
// comprobamos que haya recursos suficientes
aux = (maximos[proc][recur] - asignados[proc][recur] - disponibles[recur]) <= 0;
if (!aux)
{
break;
}
}
if (aux)
{
añadirYeliminar(ref disponibles, ref asignados, proc);
maximos.RemoveAt(proc);
nProcesos--;
proc = -1;
if (nProcesos == 0)
{
Console.WriteLine("Es estado seguro");
Console.ReadLine();
return;
}
}
}
Console.WriteLine("Es interbloqueo");
Console.ReadLine();

}

private static void añadirYeliminar(ref List<int> disponibles, ref List<List<int>> asignados, int proc)
{
for (int k = 0; k < asignados[proc].Count; k++)
{
disponibles[k] += asignados[proc][k];
}
asignados.RemoveAt(proc);
}
</source>

Faltaria solamente leer por consola el numero de procesos y de recursos que queremos testear, o introduccirlos manualmente

== Algoritmo en Python ==

<source lang="python">
def comprueba_configuracion(asignados, maximos, disponibles):
finalizados = []
i = 0
while(i < len(asignados)):
if not i in finalizados and puede_progresar(asignados[i], disponibles, maximos[i]):
print('Finaliza P%s\nDisponibles: %s' % (i,disponibles))
libera_recursos(asignados[i], disponibles)
finalizados.append(i) # Marca el proceso Pi como finalizado
i = 0
else:
i += 1

if(len(asignados) == len(finalizados)): # Si todos los procesos finalizan
print('\nEstado seguro para la configuracion de procesos-recursos dada')
else:
print('\nSe produce un interbloqueo')

# Incrementamos la lista de disponibles con los que tenia asignados
def libera_recursos(asignados, disponibles):
for i in range(len(disponibles)):
disponibles[i] += asignados[i]

# Devuelve True si el nº de elementos asignados mas los disponibles son mayores o iguales a los requeridos para continuar
def puede_progresar(asignados, disponibles, maximos):
resultado = True
for i in range(len(maximos)):
if(asignados[i] + disponibles[i] < maximos[i]):
resultado = False
break
return resultado

asignados = [
[1,0,2,1,1],
[2,0,1,1,0],
[1,1,0,1,0],
[1,1,1,1,0]
]
maximos = [
[1,2,2,1,2],
[2,2,2,1,0],
[2,1,3,1,0],
[1,1,2,2,1]
]
disponibles = [0,0,2,1,1]
</source>

Para este ejemplo (visto en clase) la salida sería:

<source lang="python">
>>> comprueba_configuracion(asignados, maximos, disponibles)
Finaliza P3
Disponibles: [0, 0, 2, 1, 1]
Finaliza P2
Disponibles: [1, 1, 3, 2, 1]
Finaliza P0
Disponibles: [2, 2, 3, 3, 1]
Finaliza P1
Disponibles: [3, 2, 5, 4, 2]

Estado seguro para la configuracion de procesos-recursos dada
</source>

Algoritmo para averiguar interbloqueo

2011-04-27T15:03:09Z

Alexrdp: /* Algoritmo en Python */

== Algoritmo en C# ==

<source lang="csharp">
int nRecursos;
int nProcesos;
List<List<int>> asignados = new List<List<int>>();
List<List<int>> maximos = new List<List<int>>();
List<int> disponibles = new List<int>();

Random r = new Random();

//Generamos las matrices aleatoriamente
for (int j1 = 0; j1 < nRecursos;j1++)
{
disponibles.Add(r.Next(0, nRecursos));
}
for (int i = 0; i < nProcesos; i++)
{
asignados.Add(new List<int>());
maximos.Add(new List<int>());
for (int j = 0; j < nRecursos; j++)
{
asignados[i].Add(r.Next(0, nRecursos));
maximos[i].Add(r.Next(0, nRecursos));
}
}

bool aux = true;
for (int proc = 0; proc < nProcesos; proc++)
{
aux = true;
for (int recur = 0; recur < nRecursos; recur++)
{
// comprobamos que haya recursos suficientes
aux = (maximos[proc][recur] - asignados[proc][recur] - disponibles[recur]) <= 0;
if (!aux)
{
break;
}
}
if (aux)
{
añadirYeliminar(ref disponibles, ref asignados, proc);
maximos.RemoveAt(proc);
nProcesos--;
proc = -1;
if (nProcesos == 0)
{
Console.WriteLine("Es estado seguro");
Console.ReadLine();
return;
}
}
}
Console.WriteLine("Es interbloqueo");
Console.ReadLine();

}

private static void añadirYeliminar(ref List<int> disponibles, ref List<List<int>> asignados, int proc)
{
for (int k = 0; k < asignados[proc].Count; k++)
{
disponibles[k] += asignados[proc][k];
}
asignados.RemoveAt(proc);
}
</source>

Faltaria solamente leer por consola el numero de procesos y de recursos que queremos testear, o introduccirlos manualmente

== Algoritmo en Python ==

<source lang="python">
def comprueba_configuracion(asignados, maximos, disponibles):
finalizados = []
i = 0
while(i < len(asignados)):
if not i in finalizados and puede_progresar(asignados[i], disponibles, maximos[i]):
print('Finaliza P%s\nDisponibles: %s' % (i,disponibles))
libera_recursos(asignados[i], disponibles)
finalizados.append(i) # Marca el proceso Pi como finalizado
i = 0
else:
i += 1

if(len(asignados) == len(finalizados)): # Si todos los procesos finalizan
print('\nEstado seguro para la configuracion de procesos-recursos dada')
else:
print('\nSe produce un interbloqueo')

# Incrementamos la lista de disponibles con los que tenia asignados
def libera_recursos(asignados, disponibles):
for i in range(len(disponibles)):
disponibles[i] += asignados[i]

# Devuelve True si el nº de elementos asignados mas los disponibles son mayores o iguales a los requeridos
def puede_progresar(asignados, disponibles, maximos):
resultado = True
for i in range(len(maximos)):
if(asignados[i] + disponibles[i] < maximos[i]):
resultado = False
break
return resultado

asignados = [
[1,0,2,1,1],
[2,0,1,1,0],
[1,1,0,1,0],
[1,1,1,1,0]
]
maximos = [
[1,2,2,1,2],
[2,2,2,1,0],
[2,1,3,1,0],
[1,1,2,2,1]
]
disponibles = [0,0,2,1,1]
</source>

Para este ejemplo (visto en clase) la salida sería:

<source lang="python">
>>> comprueba_configuracion(asignados, maximos, disponibles)
Finaliza P3
Disponibles: [0, 0, 2, 1, 1]
Finaliza P2
Disponibles: [1, 1, 3, 2, 1]
Finaliza P0
Disponibles: [2, 2, 3, 3, 1]
Finaliza P1
Disponibles: [3, 2, 5, 4, 2]

Estado seguro para la configuracion de procesos-recursos dada
</source>

Algoritmo para averiguar interbloqueo

2011-04-27T14:50:09Z

Alexrdp: Algoritmo en Python

== Algoritmo en C# ==

<source lang="csharp">
int nRecursos;
int nProcesos;
List<List<int>> asignados = new List<List<int>>();
List<List<int>> maximos = new List<List<int>>();
List<int> disponibles = new List<int>();

Random r = new Random();

//Generamos las matrices aleatoriamente
for (int j1 = 0; j1 < nRecursos;j1++)
{
disponibles.Add(r.Next(0, nRecursos));
}
for (int i = 0; i < nProcesos; i++)
{
asignados.Add(new List<int>());
maximos.Add(new List<int>());
for (int j = 0; j < nRecursos; j++)
{
asignados[i].Add(r.Next(0, nRecursos));
maximos[i].Add(r.Next(0, nRecursos));
}
}

bool aux = true;
for (int proc = 0; proc < nProcesos; proc++)
{
aux = true;
for (int recur = 0; recur < nRecursos; recur++)
{
// comprobamos que haya recursos suficientes
aux = (maximos[proc][recur] - asignados[proc][recur] - disponibles[recur]) <= 0;
if (!aux)
{
break;
}
}
if (aux)
{
añadirYeliminar(ref disponibles, ref asignados, proc);
maximos.RemoveAt(proc);
nProcesos--;
proc = -1;
if (nProcesos == 0)
{
Console.WriteLine("Es estado seguro");
Console.ReadLine();
return;
}
}
}
Console.WriteLine("Es interbloqueo");
Console.ReadLine();

}

private static void añadirYeliminar(ref List<int> disponibles, ref List<List<int>> asignados, int proc)
{
for (int k = 0; k < asignados[proc].Count; k++)
{
disponibles[k] += asignados[proc][k];
}
asignados.RemoveAt(proc);
}
</source>

Faltaria solamente leer por consola el numero de procesos y de recursos que queremos testear, o introduccirlos manualmente

== Algoritmo en Python ==

<source lang="python">
def comprueba_configuracion(asignados, maximos, disponibles):
finalizados = []
i = 0
while(i < len(asignados)):
if not i in finalizados and puede_progresar(asignados[i], disponibles, maximos[i]):
print('Finaliza P%s\nDisponibles: %s' % (i,disponibles))
libera_recursos(asignados[i], disponibles)
finalizados.append(i)
i = 0
else:
i += 1

if(len(asignados) == len(finalizados)): # Si todos los procesos finalizan
print('\nEstado seguro para la configuracion de procesos-recursos dada')
else:
print('\nSe produce un interbloqueo')

# Incrementamos la lista de disponibles con los que tenia asignados
def libera_recursos(asignados, disponibles):
for i in range(len(disponibles)):
disponibles[i] += asignados[i]

# Devuelve True si el nº de elementos asignados mas los disponibles son mayores o iguales a los requeridos
def puede_progresar(asignados, disponibles, maximos):
resultado = True
for i in range(len(maximos)):
if(asignados[i] + disponibles[i] < maximos[i]):
resultado = False
break
return resultado

asignados = [
[1,0,2,1,1],
[2,0,1,1,0],
[1,1,0,1,0],
[1,1,1,1,0],
]
maximos = [
[1,2,2,1,2],
[2,2,2,1,0],
[2,1,3,1,0],
[1,1,2,2,1],
]
disponibles = [0,0,2,1,1]
</source>

Para este ejemplo (visto en clase) la salida sería:

<source lang="python">
>>> comprueba_configuracion(asignados, maximos, disponibles)
Finaliza P3
Disponibles: [0, 0, 2, 1, 1]
Finaliza P2
Disponibles: [1, 1, 3, 2, 1]
Finaliza P0
Disponibles: [2, 2, 3, 3, 1]
Finaliza P1
Disponibles: [3, 2, 5, 4, 2]

Estado seguro para la configuracion de procesos-recursos dada
</source>

Condiciones para el interbloqueo y estrategias de resolución

2011-04-27T12:47:03Z

Alexrdp: /* Estrategias */

== Condiciones ==

En la política del sistema operativo deben darse una serie de condiciones para que se produzca un interbloqueo.

* '''Exclusión mutua''': cada recurso está asignado a un único proceso o está disponible.

* '''Detención y espera''': los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos.

* '''No apropiación''': los recursos otorgados con anterioridad no pueden ser forzados a dejar un proceso. El proceso que los posee debe liberarlos en forma explícita.

* '''Espera circular''': debe existir una cadena circular de dos o más procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena. Esta condición es una consecuencia potencial de las tres primeras, es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un círculo vicioso de espera irresoluble.

Las tres primeras condiciones son necesarias, pero no suficientes para que exista interbloqueo. Sólo las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo.

== Estrategias ==

=== Omisión ===

Consiste en suponer que los programadores lo han hecho bien, y obviar las posibles situaciones de interbloqueo. Es la más usada.

=== Detección y Recuperación ===

* '''Detección'''
** '''Grafo de relación recursos-procesos'''
** '''Matrices de relación recursos-procesos'''

* '''Recuperación'''
** '''Apropiación temporal'''
** '''Checkpoints''': Durante la ejecución de los procesos se toma una "foto" del estado de éstos, de manera que si se produce un interbloqueo se vuelve al estado anterior. Son muy poco usados ya que tienen un elevado coste en memoria y existe la posibilidad de que un proceso esté indefinidamente sin progresar.
** '''Eliminación''': El SO elimina un proceso en base a unos determinados criterios. Aunque parezca una medida drástica, es usada con frecuencia.

=== Prevención ===

* '''Supresión de exclusión mutua'''
* '''Supresión de retención y espera''': El proceso debe tener asignado todos los recursos necesarios al inicio y no liberarlos hasta que éste finalice. Esto hace que si por ejemplo un recurso sólo se utiliza al final, esté ocupado durante toda la ejecución, no permitiendo ser usado por otros procesos.
* '''Supresión de no apropiación''': El proceso libera todos los recursos que está usando y espera a que todos los que necesita estén disponibles
* '''Supresión de espera circular'''

=== Predicción ===

El sistema operativo observa la evolución que siguen los procesos, e intenta anticiparse a los futuros conflictos

Condiciones para el interbloqueo y estrategias de resolución

2011-04-27T12:37:54Z

Alexrdp: /* Ampliar estrategias */

== Condiciones ==

En la política del sistema operativo deben darse una serie de condiciones para que se produzca un interbloqueo.

* '''Exclusión mutua''': cada recurso está asignado a un único proceso o está disponible.

* '''Detención y espera''': los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos.

* '''No apropiación''': los recursos otorgados con anterioridad no pueden ser forzados a dejar un proceso. El proceso que los posee debe liberarlos en forma explícita.

* '''Espera circular''': debe existir una cadena circular de dos o más procesos, cada uno de los cuales espera un recurso poseído por el siguiente miembro de la cadena. Esta condición es una consecuencia potencial de las tres primeras, es decir, dado que se producen las tres primeras condiciones, puede ocurrir una secuencia de eventos que desemboque en un círculo vicioso de espera irresoluble.

Las tres primeras condiciones son necesarias, pero no suficientes para que exista interbloqueo. Sólo las cuatro condiciones en conjunto constituyen una condición necesaria y suficiente para el interbloqueo.

== Estrategias ==

* '''Omisión''': consiste en suponer que los programadores lo han hecho bien, y obviar las posibles situaciones de interbloqueo. Es la más usada.

* '''Detección y Recuperación'''

** Detección
*** Grafo de relación recursos-procesos
*** Matrices de relación recursos-procesos

** Recuperación
*** Apropiación temporal
*** Checkpoints
*** Eliminación

* '''Prevención'''
** Supresión de exclusión mutua
** Supresión de retención y espera:
** Supresión de no apropiación: El proceso libera todos los recursos que está usando y espera a que todos los que necesita estén disponibles
** Supresión de espera circular

* '''Predicción''': el SO observa la evolución que siguen los procesos, e intenta anticiparse a los futuros conflictos

Cerrojos

2011-03-30T13:22:38Z

Alexrdp: Títulos y correcciones

= Ejemplo de implementación =

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

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

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

... // Sección crítica

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

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

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

= Cerrojos mediante instrucciones atómicas =

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

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

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

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

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

Cerrojos

2011-03-30T13:13:37Z

Alexrdp: Añadir anotaciones y ejemplo de clase

Esto es un esbozo.

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

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

... // Sección crítica

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

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

De esta forma, tenemos a dos hilos ejecutando código de la sección crítica.

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

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

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

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

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

Concurrencia de procesos

2011-03-28T16:05:36Z

Alexrdp:

=Formas de interacción entre procesos=
Hay dos formas de interacción entre los procesos :
* '''Relaciones de Concurrencia''': los procesos A y B tienen objetivos diferentes y compiten por los recursos para conseguirlos.

* '''Relaciones de Cooperación''': los procesos A y B tienen un mismo objetivo y ''se ponen de acuerdo'' a la hora de emplear los recursos existentes para alcanzarlos.

El sistema operativo ofrece mecanismos que los procesos pueden emplear para arbitrar el acceso a los recursos.

=Mecanismos de arbitraje=
Los mecanismos de arbitraje que ofrece el sistema operativo son :
* '''Sincronización''': el sistema operativo ofrece mecanismos que permiten a los procesos coordinar la ejecución para conseguir su objetivo en armonía (y no de manera indeseada).
* '''Mensajería''': el sistema operativo ofrece mecanismos de comunicación basados en mensaje.

=Programación concurrente=
La programación concurrente consiste en el conjunto de técnicas que nos permite la elaboración de programas que emplean alguno de los mecanismos de arbitraje, basados en sincronización o mensajería, para resolver situaciones de concurrencia o cooperación.

=Tipos de mecanismos de sincronización=
*[[Mecanismos de sincronización#Optimista|Optimista]]: se considera que la frecuencia de acceso a un recurso compartido es ''baja''.
*[[Mecanismos de sincronización#Pesimista|Pesimista]]: se considera que la frecuencia de acceso a un recurso compartido es ''alta''.

Es el programador el que tiene que elegir uno de estos mecanimos a la hora de realizar su programa, y no el sistema operativo. Se debe tener en cuenta que el uso de un mecanismo inadecuado puede llevar a que el programa no responda de la manera esperada.

Concurrencia de procesos

2011-03-28T16:03:35Z

Alexrdp: Añadir enlaces

=Formas de interacción entre procesos=
Hay dos formas de interacción entre los procesos :
* Relaciones de Concurrencia : los procesos A y B tienen objetivos diferentes y compiten por los recursos para conseguirlos.

* Relaciones de Cooperación : los procesos A y B tienen un mismo objetivo y ''se ponen de acuerdo'' a la hora de emplear los recursos existentes para alcanzarlos.

El sistema operativo ofrece mecanismos que los procesos pueden emplear para arbitrar el acceso a los recursos.

=Mecanismos de arbitraje=
Los mecanismos de arbitraje que ofrece el sistema operativo son :
* Sincronización: el sistema operativo ofrece mecanismos que permiten a los procesos coordinar la ejecución para conseguir su objetivo en armonía (y no de manera indeseada).
* Mensajería: el sistema operativo ofrece mecanismos de comunicación basados en mensaje.

=Programación concurrente=
La programación concurrente consiste en el conjunto de técnicas que nos permite la elaboración de programas que emplean alguno de los mecanismos de arbitraje, basados en sincronización o mensajería, para resolver situaciones de concurrencia o cooperación.

=Tipos de mecanismos de sincronización=
*[[Mecanismos de sincronización#Optimista|Optimista]]: se considera que la frecuencia de acceso a un recurso compartido es ''baja''.
*[[Mecanismos de sincronización#Pesimista|Pesimista]]: se considera que la frecuencia de acceso a un recurso compartido es ''alta''.

Es el programador el que tiene que elegir uno de estos mecanimos a la hora de realizar su programa, y no el sistema operativo. Se debe tener en cuenta que el uso de un mecanismo inadecuado puede llevar a que el programa no responda de la manera esperada.

Mecanismos de sincronización

2011-03-28T15:56:45Z

Alexrdp: /* Optimista */

=Mecanismos de sincronización=
'''Tipos de mecanismos de sincronización :'''
== Optimista==
Se considera que la frecuencia de acceso a un recurso compartido es baja, es decir, suponemos que la probabilidad de acceso simultanea a un recurso compartido es baja.
Ejemplo de control optimista suponiendo 2 hilos, hx y hy.

int compartida = 1, tmp;
retry:
tmp = compartida; /* anoto */
tmp++; /* actualizo temporal */
if(compartida+1 != tmp)
goto retry; /* compruebo si la variable compartida ha sido modificada mientras operaba con el temporal */

Los inconvenientes de este tipo de mecanismo es su elevado recurso de memoria, ya que se debe tener una copia del recurso compartido y efectuar la comprobación, y su alto recurso de procesamiento, al tener que volver a realizar la operación. Por esto último, puede darse el caso de que un hilo esté sin progresar durante un tiempo indefinido, si se da el caso de que siempre que se le agote el tiempo de procesador asignado debido a que otro hilo modifique el recurso compartido.

==Pesimista==
Se considera que la frecuencia de acceso al recurso compartido es alta.
En este mecanismo disponemos de tres partes :
*Un protocolo de entrada : en el cual se restringe el permiso de acceso para las variables compartidas.
*Una sección crítica : donde se realizan todas las operaciones con las variables compartidas.
*Un protocolo de salida : en el cual se restablece el permiso de acceso para las variables compartidas.

(Toda operación con una variable compartida necesita un protocolo de entrada y otro de salida)
Ejemplo de control pesimista suponiendo 2 hilos, hx y hy.

int compartida = 1;
no_permito_acceso_variable_compartida(); /* protocolo de entrada */
compartida++; /* sección crítica */
permito_acceso_a_variable_compartida(); /* protocolo de salida */
'''¿Cómo implementamos el protocolo de E/S en el control de concurrencia pesimista?'''

Interrumpiendo la conmutación, desactivando las interrupciones, seguidamente ejecutando la sección crítica y finalmente permitiendo el acceso a las variables compartidas y activando las interrupciones.

'''¿Cómo implementar el control de concurrencia pesimista?'''

*Espera ocupada/activa : cerrojos. Se comprueba continuamente la condición que permite franquear el protocolo de entrada
*Espera no ocupada/no activa : semáforos, monitores y mensajes. Se pasa a estado bloqueado cuando no se puede franquear el protocolo de entrada.

Ejercicios otros aspectos de la planificación/Solucion del ejercicio 1

2011-03-23T08:27:07Z

Alexrdp: /* = */

= FIFO no apropiativo con multiprocesamiento =
Para este caso disponemos de 2 Procesadores, y supondremos que el planificador se ejecuta en uno de ellos
____|_PA_|_PB_|_PC_|_PD_|_PE__|
Datos del _H0_|_0__|_1__|_2__|_3__|_4__|
problema _t__|_5__|_3__|_1__|_6__|_2__|

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
+++ = procesador 1
--- = procesador 2

| | | | | | | | | | | | |
Pa <+++|+++|+++|+++|+++> | | | | | | |
Pb | <---|---|---> | | | | | | | |
Pc | | < | |---> | | | | | | |
Pd | | | < | |+++|+++|+++|+++|+++|+++> |
Pe | | | | < |---|---> | | | | |
Planificador X X X X X X | | | | | X |
|___|___|___|___|___|___|___|___|___|___|___|___|___> t
0 1 2 3 4 5 6 7 8 9 10 11 12

_____|_PA_|_PB_|_PC_|_PD_|_PE__|
Cálculos __t__|_5__|_3__|_1__|_6__|_2__|
de tiempos __T__|_5__|_3__|_3__|_8__|_3__|
_T/t_|_1__|_1__|_3__|1.33|_1.5|
|
|_> Indice de penalización

= SFJ no apropriativo con multiprocesamiento =

La solución es igual que el FIFO no apropiativo con multiprocesamiento.

= SFJ apropiativo con multiprocesamiento =

Para este caso disponemos de 2 Procesadores, y supondremos que el planificador se ejecuta en uno de ellos
____|_PA_|_PB_|_PC_|_PD_|_PE__|
Datos del _H0_|_0__|_1__|_2__|_3__|_4__|
problema _t__|_5__|_3__|_1__|_6__|_2__|

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
+++ = procesador 1
--- = procesador 2

| | | | | | | | | | | | |
Pa <+++|+++| |+++|+++|+++> | | | | | |
Pb | <---|---|---> | | | | | | | |
Pc | | <+++> | | | | | | | | |
Pd | | | < | | |+++|+++|+++|+++|+++|+++>
Pe | | | | <---|---> | | | | | |
Planificador X X X X X | X | | | | | X
|___|___|___|___|___|___|___|___|___|___|___|___|___> t
0 1 2 3 4 5 6 7 8 9 10 11 12

_____|_PA_|_PB_|_PC_|_PD_|_PE__|
Cálculos __t__|_5__|_3__|_1__|_6__|_2__|
de tiempos __T__|_6__|_3__|_1__|_9__|_2__|
_T/t_|_1.2|_1__|_1__|_1.5|_1__|
|
|_> Indice de penalización

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

-En este caso, pd podría haberse procesado en cualquiera de los dos procesadores,¿no?. ¿O hay que suponer que cuando ambos procesadores están ociosos se utiliza el primero?.

- Creo que si. En clase dijeron que se suponen las mismas características para ambos procesadores, por lo que no hay preferencia por uno en concreto.

Sol-ejer2-planif-procesos

2011-03-23T08:06:50Z

Alexrdp: /* Por prioridades */

= Turno rotatorio estricto =

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

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

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

_____|_Pa_|_Pb_|_Pc_|
Cálculos __t__|_3__|_5__|_6__|
de tiempos __T__|_10_|_11_|_12_|
_T/t_|3.3_|2.2_|_2__|

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

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

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

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

= Por prioridades =

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

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

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

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

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

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

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

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

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

= Turno rotatorio proporcional al número de procesos =

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

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

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

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

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

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

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

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

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

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

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

El proceso C no se bloquea nunca (o al menos en el enunciado no lo pone), por eso se ejecuta cada vez que puede.

Sol-ejer2-planif-procesos

2011-03-22T09:07:59Z

Alexrdp: /* = */

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

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

Criterios de planificación

2011-03-07T14:52:19Z

Alexrdp: Enlaces internos

= Métodos no apropiativos =

El procesador es asignado al proceso hasta fin de ejecución. Suele darse en sistemas operativos monoprogramables y sistemas de tiempo real.

== Estocástico ==

Se selecciona aleatoriamente un procesos. No cumple varios [[Planificación de procesos#Aspectos para diseñar un buen planificador|aspectos de diseño de un buen planificador]], como repetitibilidad o predecibilidad. Su uso es establecer una cota inferior a la hora de diseñar un planificador: Si éste presenta peores resultados que el método estocástico, significa que estará mal diseñado.

== Con conocimiento del futuro ==

En base al conocimiento del futuro se asignan los procesos. Representa una cota superior, es decir, mientras un planificador tenga un comportamiento más parecido a este método, mejor diseñado estará.

== Por orden de llegada (First In, First Out: FIFO) ==

Se selecciona el procesa por orden de lanzamiento. Su principales ventajas son su facilidad de implementación, y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración presentarán un alto índice de penalización.

== El siguiente, el más corto (Shortest Job First: SJF) ==

Se selecciona el proceso que requiera menos tiempo de ejecución. Para procesos largos puede presentar un índice de penalización elevado: Si se tienen muchos procesos cortos, el de mayor duración puede quedar en espera indefinidamente. Su orden de complejidad es O(n).

== Basado en índice de penalización ==

Se selecciona el proceso que lleva más tiempo sin estar en estado activo. Estima los índices de penalización y elige el de mayor valor.

= Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos [[Multiprogramación|multiprogramables]].

== El siguiente, el más corto (Shortest Job First: SJF) ==

Se selecciona el proceso que requiera menos tiempo de ejecución. Si hay un proceso en estado preparado que requiere menos tiempo de ejecución, se le asigna el procesador.

== Por prioridades ==

Se establecen índices de prioridad a cada proceso:

* Índice estático: Establecido por el usuario.
* Índice dinámico: Establecido por el planificador, inicialmente basado en el índice estático.

En el caso de Linux, como sucede con otros sistemas tipo-Unix, se dispone de una índice denominado ''nice value'' cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).

== Turno rotatorio (Round Robin: RR) ==

== Colas multinivel ==

Planificación de procesos

2011-03-07T14:42:45Z

Alexrdp: /* Aspectos para diseñar un buen planidicador */

El objetivo de la planificación de procesos es estudiar los posibles criterios de selección que puede emplear el planificador de procesos. La función de estos criterios es elegir el proceso que va a ser asignado al procesador. Para el iiestudio vamos a definir los siguientes criterios.

==Indices de evaluacion==

*Tiempo de ejecución : hace referencia al tiempo que el proceso está asignado al procesador. ('''t'''ejecución)
*Tiempo de terminación : es la diferencia entre el momento de llegada y el momento de terminación del un proceso. ('''T'''terminación)
*Tiempo perdido : es la diferencia entre el tiempo de ejecución y el tiempo de terminación. (T-t)
*Índice de penalización : indica cuanto más ha dado un proceso en ejecutarse respecto a si hubiera tenido el procesador en exclusividad. ((T/t)=x , tarda (x-1) veces más)
*Índice de respuesta : es el inverso del índice de penalización. (t/T)
*Tiempo del sistema : es el tiempo empleado por el planificador de procesos.
*Tiempo de inactividad : es el tiempo durante el cual el procesador está ocioso, es decir, no hace nada (idle).
*Tiempo de espera : es el tiempo desde el lanzamiento a estado preparado.

==Aspectos para diseñar un buen planificador==

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

Usuario:Alexrdp

2011-03-07T14:18:11Z

Alexrdp: Página nueva: Alejandro Rodas de Paz

Alejandro Rodas de Paz

Criterios de planificación

2011-03-07T14:12:55Z

Alexrdp: Añadir usos y ventajas explicadas en clase

= Métodos no apropiativos =

El procesador es asignado al proceso hasta fin de ejecución. Suele darse en sistemas operativos monoprogramables y sistemas de tiempo real.

== Estocástico ==

Se selecciona aleatoriamente un procesos. No cumple varios aspectos de diseño de un buen planificador, como repetitibilidad o predecibilidad. Su uso es establecer una cota inferior a la hora de diseñar un planificador: Si éste presenta peores resultados que el método estocástico, significa que estará mal diseñado.

== Con conocimiento del futuro ==

En base al conocimiento del futuro se asignan los procesos. Representa una cota superior, es decir, mientras un planificador tenga un comportamiento más parecido a este método, mejor diseñado estará.

== Por orden de llegada (First In, First Out: FIFO) ==

Se selecciona el procesa por orden de lanzamiento. Su principales ventajas son su facilidad de implementación, y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración presentarán un alto índice de penalización.

== El siguiente, el más corto (Shortest Job First: SJF) ==

Se selecciona el proceso que requiera menos tiempo de ejecución.

== Basado en índice de penalización ==

Se selecciona el proceso que lleva más tiempo sin estar en estado activo.

= Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos multiprogramables.

== El siguiente, el más corto (Shortest Job First: SJF) ==

Se selecciona el proceso que requiera menos tiempo de ejecución. Si hay un proceso en estado preparado que requiere menos tiempo de ejecución, se le asigna el procesador.

== Por prioridades ==

Se establecen índices de prioridad a cada proceso:

* Índice estático: Establecido por el usuario.
* Índice dinámico: Establecido por el planificador, inicialmente basado en el índice estático.

En el caso de Linux, como sucede con otros sistemas tipo-Unix, se dispone de una índice denominado ''nice value'' cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).

== Turno rotatorio (Round Robin: RR) ==

== Colas multinivel ==

Archivo:Grafica ind evaluacion1.png

2011-03-02T14:58:57Z

Alexrdp:

Índices de evaluación

2011-03-02T14:39:27Z

Alexrdp:

* '''Tiempo de ejecución''' (tejecución): tiempo total asignado al procesador.
* '''Tiempo de terminación''' (Tterminación): diferencia entre el momento de llegada y de terminación.
* '''Tiempo perdido''': T-t . Es el tiempo en que no hace nada útil.
* '''Tiempo de inactividad''': tiempo durante el cual el procesador está ocioso, no hace nada (idle). Este tiempo puede deberse a un mal diseño del planificador.
* '''Tiempo del sistema''': tiempo empleado por el planificador.
* '''Tiempo de espera''': tiempo desde el lanzamiento hasta el estado preparado
* '''Índice de penalización''': T/t = x. El proceso ha tardado x-1 veces más en ejecutarse que si hubiera tenido el procesador para él solo.
* '''Índice de respuesta''': inverso al anterior.

Ej:

| . . . . . .
Px |---. .---. .--|. .
| . . . . . .
| . . . . . .
|___.___.___.___.___.___.___>t
0 1 2 3 4 5 6

* t = 3 : los 3 intervalos en los que se procesa
* T = 5 : unidades de tiempo desde que se inicia hasta que se finaliza el proceso
* T-t = 2 : huequitos en los que el proceso está abierto sin estar procesándose
* x = 5/3 = 1.67 : el proceso ha tardado un 67% más que si hubiese tenido el procesador exclusivamente

Índices de evaluación

2011-03-02T14:13:26Z

Alexrdp:

* '''Tiempo de ejecución''' (tejecución): tiempo total asignado al procesador.
* '''Tiempo de terminación''' (Tterminación): diferencia entre el momento de llegada y de terminación.
* '''Tiempo perdido''': T-t . Es el tiempo en que no hace nada útil.
* '''Tiempo de inactividad''': tiempo durante el cual el procesador está ocioso, no hace nada (idle)
* '''Tiempo del sistema''': tiempo empleado por el planificador
* '''Tiempo de espera''': tiempo desde el lanzamiento hasta el estado preparado
* '''Índice de penalización''': T/t = x. El proceso ha tardado x-1 veces más en ejecutarse que si hubiera tenido el procesador para él solo.
* '''Índice de respuesta''': inverso al anterior

Ej:

| . . . . . .
Px |---. .---. .--|. .
| . . . . . .
| . . . . . .
|___.___.___.___.___.___.___>t
0 1 2 3 4 5 6

* t = 3 : los 3 intervalos en los que se procesa
* T = 5 : unidades de tiempo desde que se inicia hasta que se finaliza el proceso
* T-t = 2 : huequitos en los que el proceso está abierto sin estar procesándose

Archivo:Grafica ind evaluacion.jpg

2011-03-02T14:11:49Z

Alexrdp: Gráfica para los índices de evaluación

Gráfica para los índices de evaluación