Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Tipos de errores en discos magnéticos

2011-06-07T23:00:46Z

JCGarrido: corregidos errores ortográficos

Los errores típicos relacionados con los discos duros magnéticos pueden ser:

* Relacionados con el <ins>material</ins>:
** '''Permanentes''': La unidad se encuentra mal en algún sentido. No existe forma “tradicional” de acceder a ellos. En los discos magnéticos existen dos estrategias para tratar estos errores:
# Archivo que contiene todos los sectores defectuosos.
# Mantener en una tabla aquellos bloques defectuosos (p.e. FAT).
** '''Transitorios''': Errores temporales del dispositivo. Por ejemplo, caídas de tensión. La solución consiste en reintentar acceder al dispositivo un nº finito de veces, antes de declarar el error permanente. También existen rutinas de checksum (dispersión, como CRC) para detectarlos.
*<ins>Errores de software</ins>:
**Errores de '''programación''':Cuando el error se encuentra en el propio código del programa. Por ejemplo, un acceso a un cilindro, sector o pista inexistente, o a un fichero inexistente. Para solucionarlo, se devuelve un código de error para indicar al usuario lo que ha ocurrido.

Solución ejercicio 1 memoria virtual

2011-06-07T21:44:27Z

JCGarrido: /* NRU con 2º oportunidad */

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

tiempo ->

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

= NRU =

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

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

tiempo ->

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

= NRU con 2º oportunidad =

accesos a páginas

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

tiempo ->

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

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

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

Explicación:

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

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

= LRU =

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

tiempo ->

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

= LFU =

accesos a páginas

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

tiempo ->

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

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

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

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

9
tasa fallos pág = ----
12
----------------------------------
En este ejercicio hay un error cuando en la iteraccion 8 entra el 3, se ha puesto 5 100

_________________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 || 3 | = | 3 | = |
s | | | | ||100| = | = |110||011| = |111| = |
---|---|---|---|---||---|---|---|---||---|---|---|---|
4 | | | | || | 4 | = | = || 4 | 2 | = | = |
| | | | || |100| = | = ||010|100| = | = |
--------------------------------------------------------> t
x x x x x x x x x

Esta seria la solucion creo --[[Usuario:Luidela1|Luidela1]] 19:07 7 jun 2011 (UTC)

Yo creo que esta solución no es correcta, la correcta es la de arriba. En el segundo acceso al 3, se activaría el bit más significativo del registro R que ya está activado, luego no se activa. No entiendo porqué se activa el bit 2 del registro.
--[[Usuario:Robertomartin|Robertomartin]] 19:17 7 jun 2011 (UTC)

Exacto, en el segundo periodo, cuando hace el segundo acceso al 3, este ya tenia 100, por lo cual se queda igual (100) y al pasar el 3 periodo el 3 ya pasaria a ser 010, y al hacer el desempate con 4 (010), como 3 está cargado antes que el cuatro, 3 es la página elegida. --[[Usuario:Fergaliay|Fergaliay]]

Solución ejercicio 1 memoria virtual

2011-06-07T21:43:54Z

JCGarrido: /* NRU con 2º oportunidad */ Respuesta

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

tiempo ->

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

= NRU =

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

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

tiempo ->

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

= NRU con 2º oportunidad =

accesos a páginas

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

tiempo ->

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

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

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

Explicación:

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

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

= LRU =

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

tiempo ->

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

= LFU =

accesos a páginas

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

tiempo ->

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

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

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

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

9
tasa fallos pág = ----
12
----------------------------------
En este ejercicio hay un error cuando en la iteraccion 8 entra el 3, se ha puesto 5 100

_________________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 || 3 | = | 3 | = |
s | | | | ||100| = | = |110||011| = |111| = |
---|---|---|---|---||---|---|---|---||---|---|---|---|
4 | | | | || | 4 | = | = || 4 | 2 | = | = |
| | | | || |100| = | = ||010|100| = | = |
--------------------------------------------------------> t
x x x x x x x x x

Esta seria la solucion creo --[[Usuario:Luidela1|Luidela1]] 19:07 7 jun 2011 (UTC)

Yo creo que esta solución no es correcta, la correcta es la de arriba. En el segundo acceso al 3, se activaría el bit más significativo del registro R que ya está activado, luego no se activa. No entiendo porqué se activa el bit 2 del registro.
--[[Usuario:Robertomartin|Robertomartin]] 19:17 7 jun 2011 (UTC)

Exacto, en el segundo periodo, cuando hace el segundo acceso al 3, este ya tenia 100, por lo cual se queda igual (100) y al pasar el 3 periodo el 3 ya pasaria a ser 010, y al hacer el desempate con 4 (010), como 3 está cargado antes que el cuatro, 3 es la página elegida. --[[Usuario:Fergaliay|Fergaliay]]

Solución ejercicio 2 memoria virtual

2011-06-07T19:26:05Z

JCGarrido: Corrección ortográfica

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

tiempo ->

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

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

tiempo ->

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

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

Sol 7

2011-06-07T13:22:36Z

JCGarrido: cambiado el volver de sitio

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

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

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

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

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

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

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

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

[[Criterios_de_reemplazo|Volver]]

Sol 7

2011-06-07T13:21:58Z

JCGarrido: Respuesta 2 a duda

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

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

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

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

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

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

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

[[Criterios_de_reemplazo|Volver]]

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

SO multiprogramables con particiones fijas

2011-06-06T11:47:59Z

JCGarrido: /* Mecanismos de protección de memoria */ Reescrito "Ampliación bits de proteccion"

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

=Estrategias=
Las estrategias a seguir cuando no hay memoria suficiente para otro proceso son dos:
*Cancelación: "lo siento, no hay memoria libre, prueba más tarde".
*Espera: añadir el proceso a una cola hasta que haya memoria disponible.

=Limitaciones=
*Si un proceso necesita mayor memoria que la partición más grande, entonces éste 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 qué 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;
suponemos que la decisión sobre la asignación de procesos a particiones se hace ordenadamente de manera consecutiva según el número del proceso
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 según el orden de la cola 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 quepa en ella. Complejidad: O(nlog(p))

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

*'''Mejor ajuste dinámico con aplazamiento limitado''': Es una variante del criterio anterior que evita el aplazamiento indefinido. 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''': No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar la partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco y se asigna partición madre.
''Partición madre'': tipo especial de partición que se puede dividir en múltiples particiones menores.

[[Otro ejemplo|Otro ejemplo]]

= 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. Este desplazamiento es establecido por el programador antes de que se ejecute el programa.

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

= Mecanismos de protección de memoria =

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

* '''Ampliación bits de protección''' : Se le asocia a cada palabra de la memoria principal un bit para saber si pertenece al SO o al proceso.

* '''Ampliación registros valla''' : De esta manera se conocen la posición inicial y final, de manera que si no está entre esas dos posiciones no se permite el acceso a memoria.

SO multiprogramables con particiones fijas

2011-06-06T11:35:49Z

JCGarrido: /* Criterios de asignación */ Corrección ortográfica

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

=Estrategias=
Las estrategias a seguir cuando no hay memoria suficiente para otro proceso son dos:
*Cancelación: "lo siento, no hay memoria libre, prueba más tarde".
*Espera: añadir el proceso a una cola hasta que haya memoria disponible.

=Limitaciones=
*Si un proceso necesita mayor memoria que la partición más grande, entonces éste 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 qué 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;
suponemos que la decisión sobre la asignación de procesos a particiones se hace ordenadamente de manera consecutiva según el número del proceso
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 según el orden de la cola 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 quepa en ella. Complejidad: O(nlog(p))

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

*'''Mejor ajuste dinámico con aplazamiento limitado''': Es una variante del criterio anterior que evita el aplazamiento indefinido. 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''': No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar la partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco y se asigna partición madre.
''Partición madre'': tipo especial de partición que se puede dividir en múltiples particiones menores.

[[Otro ejemplo|Otro ejemplo]]

= 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. Este desplazamiento es establecido por el programador antes de que se ejecute el programa.

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

= Mecanismos de protección de memoria =

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

* '''Ampliación bits de protección''' : Se le asocia a cada palabra un bit para comprobar si es de SO o del proceso.

* '''Ampliación registros valla''' : De esta manera se conocen la posición inicial y final, de manera que si no está entre esas dos posiciones no se permite el acceso a memoria.

SO multiprogramables con particiones fijas

2011-06-06T11:32:08Z

JCGarrido: /* Limitaciones */ Corrección ortográfica

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

=Estrategias=
Las estrategias a seguir cuando no hay memoria suficiente para otro proceso son dos:
*Cancelación: "lo siento, no hay memoria libre, prueba más tarde".
*Espera: añadir el proceso a una cola hasta que haya memoria disponible.

=Limitaciones=
*Si un proceso necesita mayor memoria que la partición más grande, entonces éste 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;
suponemos que la decisión sobre la asignación de procesos a particiones se hace ordenadamente de manera consecutiva según el número del proceso
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 según el orden de la cola 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 quepa en ella. Complejidad: O(nlog(p))

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

*'''Mejor ajuste dinámico con aplazamiento limitado''': Es una variante del criterio anterior que evita el aplazamiento indefinido. 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''': No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar la partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco y se asigna partición madre.
''Partición madre'': tipo especial de partición que se puede dividir en múltiples particiones menores.

[[Otro ejemplo|Otro ejemplo]]

= 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. Este desplazamiento es establecido por el programador antes de que se ejecute el programa.

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

= Mecanismos de protección de memoria =

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

* '''Ampliación bits de protección''' : Se le asocia a cada palabra un bit para comprobar si es de SO o del proceso.

* '''Ampliación registros valla''' : De esta manera se conocen la posición inicial y final, de manera que si no está entre esas dos posiciones no se permite el acceso a memoria.

Paginación

2011-06-05T15:27:41Z

JCGarrido: /* Tabla de páginas multinivel */ Corrección ortográfica

=Definición=
Toda la memoria se divide en porciones de igual tamaño fijo, definidas por un número de página, que identifica de forma única a cada página (dentro del espacio de memoria de un proceso). Cada página se asigna en exclusividad a un proceso.

=Funcionamiento=

=Otras características=
*Los valores óptimos para las porciones son: en arquitectura de 32 bits es de 4KB, y en arquitectura de 64 bits es de 8KB.
*Los criterios vistos en el tema anterior no se aplican aquí, no tiene sentido

==Dispositivo de traducción de direcciones paginadas==
Se dispone de la tabla de páginas de cada proceso en memoria para llevar a cabo la traducción. La tabla de páginas se indexa por número de página.

==Tabla de páginas multinivel==
El objetivo es paginar la tabla de páginas. Ésta no tiene porqué estar cargada completa en memoria y no tiene porqué ocupar direcciones consecutivas.

==Elementos de administración==
La administración es sencilla ya que todas las porciones de memoria son de igual tamaño.

Se puede usar:

*Tabla o mapa de bits: ocupa poca memoria, de orden O(1)
*2 listas(colas): páginas libres, páginas ocupadas. Tiene mejor rendimiento, de orden O(1)

Segmentación

2011-06-04T16:23:01Z

JCGarrido: /* Carga de segmentos a petición */ editada la memoria virtual

=Definición=
Un segmento es un espacio de memoria de tamaño variable, compuesto por:
*Descriptor: Identificador único del segmento (dentro del espacio de memoria del proceso).
*Tamaño del segmento

=Funcionamiento=

=Características=
*Cada proceso en ejecución (esté activo, bloqueado o preparado) tiene su tabla de segmentos.

*Solapamiento: 2 segmentos pueden compartir zona de memoria. Ojo! problemas de concurrencia. Habría que usar algún método para su sincronización si se intenta.

*Protección de memoria: añadir 3 bits a la tabla de descriptores de segmentos para los permisos ( r w x ).

*Aspectos materiales : Hay 2 registros que funcionan como dispositivos de traducción segmentada; uno de dirección de comienzo de la tabla de segmentos, y otro para el número de entradas en ella.

*Esto supone dos accesos a memoria física real. La tabla de segmentos ocupa memoria, siendo deseable que permanezcan en cache.

*Cuando un proceso requiere más memoria se crea un nuevo segmento.

*Dos instancias de un mismo proceso pueden compartir segmentos de memoria de instrucciones/código, pero no para datos ya que esto complicaría la gestión.

*No se redimensionan <<<--------------- ¿No eran de tamaño variable? [[Usuario: JCGarrido|JCGarrido]]

*Gestión compleja, sobretodo por su tamaño variable

==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio([[Intro | Memoria virtual]]).

Esta zona de intercambio puede ser :

*un lugar fijo en el disco(Linux, Unix)(quien decide que segmento se va a descargar es el administrador de memoria)

*o un fichero de tamaño variable y oculto (Windows).

==Enlace dinámico==
Uso de llamadas a funciones que están en disco
(Podemos tener referencias a funciones o bibliotecas que no estén en memoria principal. Permite ir cargando bajo demanda los segmentos que contengan el código necesario).

Segmentación

2011-06-04T16:22:30Z

JCGarrido: /* Carga de segmentos a petición */ editada la carga de segmentos

=Definición=
Un segmento es un espacio de memoria de tamaño variable, compuesto por:
*Descriptor: Identificador único del segmento (dentro del espacio de memoria del proceso).
*Tamaño del segmento

=Funcionamiento=

=Características=
*Cada proceso en ejecución (esté activo, bloqueado o preparado) tiene su tabla de segmentos.

*Solapamiento: 2 segmentos pueden compartir zona de memoria. Ojo! problemas de concurrencia. Habría que usar algún método para su sincronización si se intenta.

*Protección de memoria: añadir 3 bits a la tabla de descriptores de segmentos para los permisos ( r w x ).

*Aspectos materiales : Hay 2 registros que funcionan como dispositivos de traducción segmentada; uno de dirección de comienzo de la tabla de segmentos, y otro para el número de entradas en ella.

*Esto supone dos accesos a memoria física real. La tabla de segmentos ocupa memoria, siendo deseable que permanezcan en cache.

*Cuando un proceso requiere más memoria se crea un nuevo segmento.

*Dos instancias de un mismo proceso pueden compartir segmentos de memoria de instrucciones/código, pero no para datos ya que esto complicaría la gestión.

*No se redimensionan <<<--------------- ¿No eran de tamaño variable? [[Usuario: JCGarrido|JCGarrido]]

*Gestión compleja, sobretodo por su tamaño variable

==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio([[Memoria virtual | Intro]]).

Esta zona de intercambio puede ser :

*un lugar fijo en el disco(Linux, Unix)(quien decide que segmento se va a descargar es el administrador de memoria)

*o un fichero de tamaño variable y oculto (Windows).

==Enlace dinámico==
Uso de llamadas a funciones que están en disco
(Podemos tener referencias a funciones o bibliotecas que no estén en memoria principal. Permite ir cargando bajo demanda los segmentos que contengan el código necesario).

Segmentación

2011-06-04T16:20:13Z

JCGarrido: /* Carga de segmentos a petición */ corregido el enlace

=Definición=
Un segmento es un espacio de memoria de tamaño variable, compuesto por:
*Descriptor: Identificador único del segmento (dentro del espacio de memoria del proceso).
*Tamaño del segmento

=Funcionamiento=

=Características=
*Cada proceso en ejecución (esté activo, bloqueado o preparado) tiene su tabla de segmentos.

*Solapamiento: 2 segmentos pueden compartir zona de memoria. Ojo! problemas de concurrencia. Habría que usar algún método para su sincronización si se intenta.

*Protección de memoria: añadir 3 bits a la tabla de descriptores de segmentos para los permisos ( r w x ).

*Aspectos materiales : Hay 2 registros que funcionan como dispositivos de traducción segmentada; uno de dirección de comienzo de la tabla de segmentos, y otro para el número de entradas en ella.

*Esto supone dos accesos a memoria física real. La tabla de segmentos ocupa memoria, siendo deseable que permanezcan en cache.

*Cuando un proceso requiere más memoria se crea un nuevo segmento.

*Dos instancias de un mismo proceso pueden compartir segmentos de memoria de instrucciones/código, pero no para datos ya que esto complicaría la gestión.

*No se redimensionan <<<--------------- ¿No eran de tamaño variable? [[Usuario: JCGarrido|JCGarrido]]

*Gestión compleja, sobretodo por su tamaño variable

==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio[[Memoria virtual | Memoria virtual]].

Esta zona de intercambio puede ser :

*un lugar fijo en el disco(Linux, Unix)(quien decide que segmento se va a descargar es el administrador de memoria)

*o un fichero de tamaño variable y oculto (Windows).

==Enlace dinámico==
Uso de llamadas a funciones que están en disco
(Podemos tener referencias a funciones o bibliotecas que no estén en memoria principal. Permite ir cargando bajo demanda los segmentos que contengan el código necesario).

Segmentación

2011-06-04T16:18:07Z

JCGarrido: /* Características */ ¿No eran de tamaño variable?

=Definición=
Un segmento es un espacio de memoria de tamaño variable, compuesto por:
*Descriptor: Identificador único del segmento (dentro del espacio de memoria del proceso).
*Tamaño del segmento

=Funcionamiento=

=Características=
*Cada proceso en ejecución (esté activo, bloqueado o preparado) tiene su tabla de segmentos.

*Solapamiento: 2 segmentos pueden compartir zona de memoria. Ojo! problemas de concurrencia. Habría que usar algún método para su sincronización si se intenta.

*Protección de memoria: añadir 3 bits a la tabla de descriptores de segmentos para los permisos ( r w x ).

*Aspectos materiales : Hay 2 registros que funcionan como dispositivos de traducción segmentada; uno de dirección de comienzo de la tabla de segmentos, y otro para el número de entradas en ella.

*Esto supone dos accesos a memoria física real. La tabla de segmentos ocupa memoria, siendo deseable que permanezcan en cache.

*Cuando un proceso requiere más memoria se crea un nuevo segmento.

*Dos instancias de un mismo proceso pueden compartir segmentos de memoria de instrucciones/código, pero no para datos ya que esto complicaría la gestión.

*No se redimensionan <<<--------------- ¿No eran de tamaño variable? [[Usuario: JCGarrido|JCGarrido]]

*Gestión compleja, sobretodo por su tamaño variable

==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio[Memoria virtual | Memoria virtual].

Esta zona de intercambio puede ser :

*un lugar fijo en el disco(Linux, Unix)(quien decide que segmento se va a descargar es el administrador de memoria)

*o un fichero de tamaño variable y oculto (Windows).

==Enlace dinámico==
Uso de llamadas a funciones que están en disco
(Podemos tener referencias a funciones o bibliotecas que no estén en memoria principal. Permite ir cargando bajo demanda los segmentos que contengan el código necesario).

Segmentación

2011-06-04T16:08:12Z

JCGarrido: /* Características */ Correcciones en aspectos materiales

=Definición=
Un segmento es un espacio de memoria de tamaño variable, compuesto por:
*Descriptor: Identificador único del segmento (dentro del espacio de memoria del proceso).
*Tamaño del segmento

=Funcionamiento=

=Características=
*Cada proceso en ejecución (esté activo, bloqueado o preparado) tiene su tabla de segmentos.

*Solapamiento: 2 segmentos pueden compartir zona de memoria. Ojo! problemas de concurrencia. Habría que usar algún método para su sincronización si se intenta.

*Protección de memoria: añadir 3 bits a la tabla de descriptores de segmentos para los permisos ( r w x ).

*Aspectos materiales : Hay 2 registros que funcionan como dispositivos de traducción segmentada; uno de dirección de comienzo de la tabla de segmentos, y otro para el número de entradas en ella.

*Esto supone dos accesos a memoria física real. La tabla de segmentos ocupa memoria, siendo deseable que permanezcan en cache.

*Cuando un proceso requiere más memoria se crea un nuevo segmento.

*Dos instancias de un mismo proceso pueden compartir segmentos de memoria de instrucciones/código, pero no para datos ya que esto complicaría la gestión.

*No se redimensionan

*Gestión compleja, sobretodo por su tamaño variable

==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio[Memoria virtual | Memoria virtual].

Esta zona de intercambio puede ser :

*un lugar fijo en el disco(Linux, Unix)(quien decide que segmento se va a descargar es el administrador de memoria)

*o un fichero de tamaño variable y oculto (Windows).

==Enlace dinámico==
Uso de llamadas a funciones que están en disco
(Podemos tener referencias a funciones o bibliotecas que no estén en memoria principal. Permite ir cargando bajo demanda los segmentos que contengan el código necesario).

Segmentación

2011-06-04T16:03:07Z

JCGarrido: /* Características */ Editada la protección de memoria.

=Definición=
Un segmento es un espacio de memoria de tamaño variable, compuesto por:
*Descriptor: Identificador único del segmento (dentro del espacio de memoria del proceso).
*Tamaño del segmento

=Funcionamiento=

=Características=
*Cada proceso en ejecución (esté activo, bloqueado o preparado) tiene su tabla de segmentos.

*Solapamiento: 2 segmentos pueden compartir zona de memoria. Ojo! problemas de concurrencia. Habría que usar algún método para su sincronización si se intenta.

*Protección de memoria: añadir 3 bits a la tabla de descriptores de segmentos para los permisos ( r w x ).

*Aspectos materiales : hay 2 registros que funcionan como dispositivos de traducción segmentada uno de dirección de comienzo de la tabla de segmentos, y otro para el numero de entradas en ella.

*Esto supone dos accesos a memoria física real. La tabla de segmentos ocupa memoria, siendo deseable que permanezcan en cache.

*Cuando un proceso requiere más memoria se crea un nuevo segmento.

*Dos instancias de un mismo proceso pueden compartir segmentos de memoria de instrucciones/código, pero no para datos ya que esto complicaría la gestión.

*No se redimensionan

*Gestión compleja, sobretodo por su tamaño variable

==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio[Memoria virtual | Memoria virtual].

Esta zona de intercambio puede ser :

*un lugar fijo en el disco(Linux, Unix)(quien decide que segmento se va a descargar es el administrador de memoria)

*o un fichero de tamaño variable y oculto (Windows).

==Enlace dinámico==
Uso de llamadas a funciones que están en disco
(Podemos tener referencias a funciones o bibliotecas que no estén en memoria principal. Permite ir cargando bajo demanda los segmentos que contengan el código necesario).

Segmentación

2011-06-04T15:59:12Z

JCGarrido: /* Características */ Corrección ortográfica.

=Definición=
Un segmento es un espacio de memoria de tamaño variable, compuesto por:
*Descriptor: Identificador único del segmento (dentro del espacio de memoria del proceso).
*Tamaño del segmento

=Funcionamiento=

=Características=
*Cada proceso en ejecución (esté activo, bloqueado o preparado) tiene su tabla de segmentos.

*Solapamiento: 2 segmentos pueden compartir zona de memoria. Ojo! problemas de concurrencia. Habría que usar algún método para su sincronización si se intenta.

*Protección de memoria: añadir 3 bit a la tabla de descriptores de segmentos para los permisos ( r w x )permisos a los segmentos

*Aspectos materiales : hay 2 registros que funcionan como dispositivos de traducción segmentada uno de dirección de comienzo de la tabla de segmentos, y otro para el numero de entradas en ella.

*Esto supone dos accesos a memoria física real. La tabla de segmentos ocupa memoria, siendo deseable que permanezcan en cache.

*Cuando un proceso requiere más memoria se crea un nuevo segmento.

*Dos instancias de un mismo proceso pueden compartir segmentos de memoria de instrucciones/código, pero no para datos ya que esto complicaría la gestión.

*No se redimensionan

*Gestión compleja, sobretodo por su tamaño variable

==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio[Memoria virtual | Memoria virtual].

Esta zona de intercambio puede ser :

*un lugar fijo en el disco(Linux, Unix)(quien decide que segmento se va a descargar es el administrador de memoria)

*o un fichero de tamaño variable y oculto (Windows).

==Enlace dinámico==
Uso de llamadas a funciones que están en disco
(Podemos tener referencias a funciones o bibliotecas que no estén en memoria principal. Permite ir cargando bajo demanda los segmentos que contengan el código necesario).

Segmentación

2011-06-04T15:53:22Z

JCGarrido: /* Definición */ Editada la definición.

=Definición=
Un segmento es un espacio de memoria de tamaño variable, compuesto por:
*Descriptor: Identificador único del segmento (dentro del espacio de memoria del proceso).
*Tamaño del segmento

=Funcionamiento=

=Características=
*Cada proceso en ejecución (este activo, bloqueado o preparado) tiene su tabla de segmentos

*Solapamiento: 2 segmentos pueden compartir zona de memoria. Ojo! problemas de concurrencia. Habría que usar algún método para su sincronización si se intenta.

*Protección de memoria: añadir 3 bit a la tabla de descriptores de segmentos para los permisos ( r w x )permisos a los segmentos

*Aspectos materiales : hay 2 registros que funcionan como dispositivos de traducción segmentada uno de dirección de comienzo de la tabla de segmentos, y otro para el numero de entradas en ella.

*Esto supone dos accesos a memoria física real. La tabla de segmentos ocupa memoria, siendo deseable que permanezcan en cache.

*Cuando un proceso requiere más memoria se crea un nuevo segmento.

*Dos instancias de un mismo proceso pueden compartir segmentos de memoria de instrucciones/código, pero no para datos ya que esto complicaría la gestión.

*No se redimensionan

*Gestión compleja, sobretodo por su tamaño variable

==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio[Memoria virtual | Memoria virtual].

Esta zona de intercambio puede ser :

*un lugar fijo en el disco(Linux, Unix)(quien decide que segmento se va a descargar es el administrador de memoria)

*o un fichero de tamaño variable y oculto (Windows).

==Enlace dinámico==
Uso de llamadas a funciones que están en disco
(Podemos tener referencias a funciones o bibliotecas que no estén en memoria principal. Permite ir cargando bajo demanda los segmentos que contengan el código necesario).

SO multiprogramables con particiones variables

2011-06-03T18:10:49Z

JCGarrido: /* Criterios de asignación */ peticion

== Definición ==

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

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

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

== Elementos de administración ==

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

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

== Criterios de asignación ==

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

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

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

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

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

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

Petición:Por favor,alguien que entienda bien el mejor ajuste y el peor ajuste, que explique lo que significa que tenga menor o mayor ajuste interno, que no se entiende bien.
Gracias.

SO multiprogramables con particiones variables

2011-06-03T18:09:57Z

JCGarrido: /* Criterios de asignación */ Peticion

== Definición ==

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

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

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

== Elementos de administración ==

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

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

== Criterios de asignación ==

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

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

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

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

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

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

''Petición:''
Por favor,alguien que entienda bien el mejor ajuste y el peor ajuste, que explique lo que significa que tenga menor o mayor ajuste interno, que no se entiende bien.
Gracias.

SO multiprogramables con particiones variables

2011-06-03T18:09:05Z

JCGarrido: /* Criterios de asignación */ Petición

== Definición ==

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

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

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

== Elementos de administración ==

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

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

== Criterios de asignación ==

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

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

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

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

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

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

Petición:
Por favor,alguien que entienda bien el mejor ajuste y el peor ajuste, que explique lo que significa que tenga menor o mayor ajuste interno, que no se entiende bien.
Gracias.

SO multiprogramables con particiones fijas

2011-06-03T17:25:40Z

JCGarrido: /* Mecanismos de protección de memoria */ tildes

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

=Estrategias=
Las estrategias a seguir cuando no hay memoria suficiente para otro proceso son dos:
*Cancelación: "lo siento, no hay memoria libre, prueba más tarde".
*Espera: añadir el proceso a una cola hasta que haya memoria disponible.

=Limitaciones=
*Si un procesos necesita mayor memoria que la partición más grande, entonces este 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;
suponemos que la decisión sobre la asignación de procesos a particiones se hace ordenadamente de manera consecutiva según el número del proceso
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 quepa 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''': No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar la partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco y se asigna partición madre.
''Partición madre'': tipo especial de partición que se puede dividir en múltiples particiones menores.

[[Otro ejemplo|Otro ejemplo]]

= 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. Este desplazamiento es establecido por el programador antes de que se ejecute el programa.

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

= Mecanismos de protección de memoria =

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

* '''Ampliación bits de protección''' : Se le asocia a cada palabra un bit para comprobar si es de SO o del proceso.

* '''Ampliación registros valla''' : De esta manera se conocen la posición inicial y final, de manera que si no está entre esas dos posiciones no se permite el acceso a memoria.

SO multiprogramables con particiones fijas

2011-06-03T17:22:21Z

JCGarrido: /* Criterios de asignación */ Corrección en una frase

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

=Estrategias=
Las estrategias a seguir cuando no hay memoria suficiente para otro proceso son dos:
*Cancelación: "lo siento, no hay memoria libre, prueba más tarde".
*Espera: añadir el proceso a una cola hasta que haya memoria disponible.

=Limitaciones=
*Si un procesos necesita mayor memoria que la partición más grande, entonces este 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;
suponemos que la decisión sobre la asignación de procesos a particiones se hace ordenadamente de manera consecutiva según el número del proceso
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 quepa 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''': No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar la partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco y se asigna partición madre.
''Partición madre'': tipo especial de partición que se puede dividir en múltiples particiones menores.

[[Otro ejemplo|Otro ejemplo]]

= 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. Este desplazamiento es establecido por el programador antes de que se ejecute el programa.

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

= Mecanismos de protección de memoria =

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

* '''Ampliación bits de protección''' : Se le asocia a cada palabra un bit para comprobar si es de SO o del proceso.

* '''Ampliación registros valla''' : De esta manera se conocen la posición inicial y final, de manera que si no esta entre esas dos posiciones no se permite el acceso a memoria.

SO multiprogramables con particiones fijas

2011-06-02T17:44:42Z

JCGarrido: /* Mecanismos de protección de memoria */ Explicación de "Ampliación bits de protección"

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

=Estrategias=
Las estrategias a seguir cuando no hay memoria suficiente para otro proceso son dos:
*Cancelación: "lo siento, no hay memoria libre, prueba más tarde".
*Espera: añadir el proceso a una cola hasta que haya memoria disponible.

=Limitaciones=
*Si un procesos necesita mayor memoria que la partición más grande, entonces este 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;
suponemos que la decisión sobre la asignación de procesos a particiones se hace ordenadamente de manera consecutiva según el número del proceso
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 quepa 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''': No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco y se asigna partición madre.
''Partición madre'': tipo especial de partición que se puede dividir en múltiples particiones menores.

[[Otro ejemplo|Otro ejemplo]]

= 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. Este desplazamiento es establecido por el programador antes de que se ejecute el programa.

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

= Mecanismos de protección de memoria =

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

* '''Ampliación bits de protección''' : Se le asocia a cada palabra un bit para comprobar si es de SO o del proceso.

* '''Ampliación registros valla''' : De esta manera se conocen la posición inicial y final, de manera que si no esta entre esas dos posiciones no se permite el acceso a memoria.

SO multiprogramables con particiones fijas

2011-06-02T17:37:36Z

JCGarrido: /* Métodos de colocación en memoria */ Eliminada una palabra innecesaria.

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

=Estrategias=
Las estrategias a seguir cuando no hay memoria suficiente para otro proceso son dos:
*Cancelación: "lo siento, no hay memoria libre, prueba más tarde".
*Espera: añadir el proceso a una cola hasta que haya memoria disponible.

=Limitaciones=
*Si un procesos necesita mayor memoria que la partición más grande, entonces este 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;
suponemos que la decisión sobre la asignación de procesos a particiones se hace ordenadamente de manera consecutiva según el número del proceso
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 quepa 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''': No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco y se asigna partición madre.
''Partición madre'': tipo especial de partición que se puede dividir en múltiples particiones menores.

[[Otro ejemplo|Otro ejemplo]]

= 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. Este desplazamiento es establecido por el programador antes de que se ejecute el programa.

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

= Mecanismos de protección de memoria =

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

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

* '''Ampliación registros valla''' : De esta manera se conocen la posición inicial y final, de manera que si no esta entre esas dos posiciones no se permite el acceso a memoria.

SO multiprogramables con particiones fijas

2011-06-02T16:06:34Z

JCGarrido: /* Limitaciones */ corrección de la frase.

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

=Estrategias=
Las estrategias a seguir cuando no hay memoria suficiente para otro proceso son dos:
*Cancelación: "lo siento, no hay memoria libre, prueba más tarde".
*Espera: añadir el proceso a una cola hasta que haya memoria disponible.

=Limitaciones=
*Si un procesos necesita mayor memoria que la partición más grande, entonces este 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;
suponemos que la decisión sobre la asignación de procesos a particiones se hace ordenadamente de manera consecutiva según el número del proceso
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 quepa 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''': No es un criterio como tal sino que viene a complementar a los anteriores. Si no hay un proceso que pueda aprovechar partición madre: se asignan las subparticiones a procesos pequeños (para que el desperdicio interno sea lo menor posible). Si llega un proceso grande: los procesos pequeños se vuelcan a disco y se asigna partición madre.
''Partición madre'': tipo especial de partición que se puede dividir en múltiples particiones menores.

[[Otro ejemplo|Otro ejemplo]]

= Métodos de colocación en memoria =

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

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

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

= Mecanismos de protección de memoria =

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

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

* '''Ampliación registros valla''' : De esta manera se conocen la posición inicial y final, de manera que si no esta entre esas dos posiciones no se permite el acceso a memoria.

SO monoprogramables

2011-06-02T16:00:05Z

JCGarrido: Apmpliación de una frase.

La administración de memoria es muy sencilla. El SO se coloca como bloque al principio de la memoria (memoria del sistema), y el resto para el proceso a ejecutar (memoria del proceso). Si el proceso no cabe, podría recurrirse al solapamiento o a la ejecución en cadena.

Tiene debilidades en cuanto a protección de memoria. Para evitar que un proceso entre en el área del SO, se puede recurrir al uso de bits de protección (se le asocia a cada palabra un bit para comprobar si es de SO o del proceso) o a los registros valla (se conoce el limite de la dirección entre SO y proceso).

Ejemplo práctico:
Pablo tiene una computadora cuya memoria principal tiene una capacidad de 640KB. El SO (MS-DOS) ocupa el principio de la memoria, dejando libre una
zona de 512KB para el proceso conveniente.
Esto nos impide jugar al Sensible Soccer, por ejemplo, ya que ocupa 560KB. Una posible solución seria instalar un SO menos pesado, como una version
más antigua de MS-DOS.

Monitores

2011-05-10T15:23:24Z

JCGarrido: /* Definición */ corregidos errores ortográficos

Idea desarrollada en los años 70 Brinch-Hansen y Hoare <ref>http://java.sun.com/developer/Books/performance2/chap4.pdf</ref>que notaron los siguientes problemas con respecto al uso de los semáforos:

* Los semáforos son difíciles de usar. Es frecuente que el programador cometa errores al emplearlos.
* El compilador no asiste al programador en el desarrollo de programas concurrentes mediante semáforos, pues no ofrece ningún tipo de validación en tiempo de compilación.
* No hay nada que obligue a usarlos. Puede suceder que el programador los necesite y lo desconozca
* Son independientes del recurso compartido

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

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

* Los datos son privados.
* Ofrecen una serie de métodos públicos para acceder a dichos datos.
* En cada momento sólo puede haber un proceso activo en algún método del monitor, es decir, ejecutando código de esos métodos públicos del monitor. Seria equivalente a decir que el recurso que queremos compartir se declara como monitor. Los procesos que usan el monitor son independientes unos de otros y cuando deseen usar el recurso, llamarán a los métodos del monitor que implementen la operación que se desea ejecutar.

Permiten organizar procesos en espera mediante:

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

<source lang="java">

class recursoCompartido {

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

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

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

</source>

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

== Fuentes ==
<references/>

Solución de los ejercicios de concurrencia

2011-05-09T16:32:52Z

JCGarrido: Corregido Observación

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

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

Modificación:

Solución:

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

Posible solución:

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

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

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

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

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

Observación:
--> Me parece que al ser dos hilos diferentes,aunque compartan el mismo código, las variables son individuales para cada hilo, con lo que cada hilo hace el bucle for completo,quedando la siguiente solución:

| #1| #2| #3| | | | #4| #1| #2| | | | #3| #4| #1| | | | | | | | |
H1 |<--|---|---| | | |---|---|---| | | |---|---|-->| | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | |
| | | | #1| #2| #2| | | | #2| #2| #2| | | | #2| #3| #4| #1| #2| #3| #4| #1|
H2 | | | |<--|---|---| | | |---|---|---| | | |---|---|---|---|---|---|---|-->|
| | | | | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
[[Usuario:JCGarrido|JCGarrido]]

Solución de los ejercicios de concurrencia

2011-05-09T16:31:12Z

JCGarrido: Observación

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

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

Modificación:

Solución:

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

Posible solución:

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

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

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

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

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

Observación:
--> Me parece que al ser dos hilos diferentes,aunque compartan el mismo código, las variables son individuales para cada hilo, con lo que cada hilo hace el bucle for completo,quedando la siguiente solución:

| #1| #2| #3| | | | #4| #1| #2| | | | #3| #4| #1| | | | | | | | |
H1 |---|---|---| | | |---|---|---| | | |---|---|---| | | | | | | | |
| | | | | | | | | | | | | | | | | | | | | | | |
| | | | #1| #2| #2| | | | #2| #2| #2| | | | #2| #3| #4| #1| #2| #3| #4| #1|
H2 | | | |---|---|---| | | |---|---|---| | | |---|---|---|---|---|---|---|---|
| | | | | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
[[Usuario:JCGarrido|JCGarrido]]

Ejercicios sincronización y comunicación

2011-05-09T11:31:09Z

JCGarrido: Corregidor errores ortográficos.

= Ejercicio 1 =

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

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

Y el proceso P2 ejecuta el siguiente código:

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

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

Suponga que:

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

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

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

= Ejercicio 2 =

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

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

Y el proceso P2 ejecuta el siguiente código:

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

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

Suponga que:

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

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

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

= Ejercicio 3 =

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

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

Y el proceso P2 ejecuta el siguiente código:

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

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

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

= Ejercicio 4 =

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

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

Y el proceso P2 ejecuta el siguiente código:

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

Suponga que:

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

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

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

Ejercicio de concurrencia de procesos

2011-05-09T11:06:22Z

JCGarrido: /* Ejercicio 1 */ Corrección ortográfica.

= Ejercicio 1 =

Realice el cronograma temporal que represente la ejecución de un proceso P1 que dispone de dos hilos, h1 y h2. Ambos hilos sincronizan su ejecución mediante cerrojos y ejecutan el mismo código:

<source lang="c">
for (int i=0; i<2; i++) { /* instrucción 1 */
lock_down(); /* instrucción 2 */
funcion(); /* instrucción 3 */
lock_up(); /* instrucción 4 */
}
</source>

Suponga que:

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

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

[[solucion ejercicio 1|Solución Ejercicio 1]]

Condiciones para el interbloqueo y estrategias de resolución

2011-05-08T17:17:31Z

JCGarrido: /* Prevención */ tildes

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

* '''Retenció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''': Se retira la asignación de un recurso a un proceso para deshacer el interbloqueo.
** '''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''' (1ª estrategia de Havender): El proceso debe tener asignado todos los recursos necesarios al inicio y no liberarlos hasta que éste finalice. Esto presenta un inconveniente: si un recurso sólo se utiliza al final, estará ocupado durante toda la ejecución, no permitiendo ser usado por otros procesos.
* '''Supresión de no apropiación''' (2ª estrategia de Havender): Si un proceso está en ejecución y no puede obtener un recurso, dicho proceso libera todos los recursos que está usando y espera a que todos los que necesita estén disponibles. Problemas: se puede perder trabajo, además de presentar una carga extra la realización de peticiones
* '''Supresión de espera circular''' (3ª estrategia de Havender): Si todos los recursos comunes a varios procesos se solicitan siempre en el mismo orden no se producen interbloqueos.

=== Predicción ===

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

Semáforos

2011-05-07T14:19:18Z

JCGarrido: tildes

= Planificador de procesos: Diagrama de estados simplicado =

Para comprender apropiadamente cómo funcionan los semáforos vamos a recordar el diagrama de estados simplificado que emplea el planificador de procesos del sistema operativo.

|---------------|
pendiente | | recibido
evento ---------> | bloqueado |----------- evento
externo | | | | externo
| |---------------| |
| |
| planificador \/
|--------------| retira CPU |---------------|
| | -------------------> | |
| activo | | preparado |
| | <------------------- | |
|--------------| |---------------|
planificador
asigna CPU

La vida de un proceso pasa por tres estados:

* Activo: el proceso está empleando la CPU, por tanto, está ejecutándose. Hay tantos procesos activos como recurso de procesamiento disponible. Por tanto, si el sistema dispone de un único procesador, únicamente puede haber un proceso activo a la vez.
* Preparado: el proceso no está ejecutándose pero es candidato a pasar a estado activo. Es el planificador el que, en base a un criterio de planificación, decide qué proceso selecciona de la lista de procesos preparados para pasar a estado activo.
* Bloqueado: el proceso está pendiente de un evento externo, tales como la espera de finalización de un proceso hijo, una señal, una operación sobre un semáforo o una operación de lectura/escritura.

La transición de activo a preparado y viceversa depende de decisiones tomadas por el planificador del sistema operativo (que emplea algún criterio visto en clases teóricas, tales como el turno rotatorio), el programador no puede interferir en estas decisiones. Mientras que la transición de activo a bloqueado, y de bloqueado a preparado pueden ser controladas por el programador mediante llamadas al sistema.

= Semáforos =

Los semáforos son un mecanismo de sincronización de procesos inventados por [http://es.wikipedia.org/wiki/Edsger_Dijkstra Edsger Dijkstra]. Los semáforos nos permiten '''asistir al planificador del sistema operativo en su toma de decisiones''' de manera que nos permiten sincronizar la ejecución de dos o más procesos.

Los semáforos son un tipo de datos (TAD) que están compuestos por dos atributos:

* Un contador, que siempre vale >= 0.
* Una lista de procesos, inicialmente vacía.

Son usados para controlar el acceso a ciertas partes de un programa llamadas '''secciones críticas''', en la que se manipulan recursos que deben ser tratados de forma especial.

El valor del semáforo, tanto en su inicialización como a lo largo de la ejecución del proceso, es muy importante ya que será lo que controle el número de procesos accediendo al recurso compartido de manera simultánea.

El tipo más simple de semáforo es el binario. Pueden tomar como valor 0 o 1 y sólo permite el acceso a un único proceso a la vez.

Los semáforos disponen de dos operaciones básicas que pasamos a describir en pseudocódigo:

<source lang="c">
down(semáforo s)
{
si s.contador == 0:
proceso a estado bloqueado
añade proceso a s.lista
sino:
s.contador--
}
</source>

Nótese que siempre que queramos forzar una transición de un proceso a estado bloqueado, tenemos que hacer que dicho proceso realice una operación ''down'' sobre un semáforo cuyo contador vale cero.

<source lang="c">
up(semáforo s)
{
si hay procesos en s.lista
retira proceso de s.lista
proceso a estado preparado
sino:
s.contador++
}
</source>

Nótese que una operación ''up'' sobre un semáforo en el que hay procesos en su lista resulta en que se retire uno de los procesos (el que más tiempo lleva en la lista), realizando éste la transición a estado preparado. Es un error frecuente pensar que una operación ''up'' resulte en que el proceso retirado de la lista pase a estado activo. Recuerde que las transiciones de estado activo a preparado y viceversa son siempre controladas por el planificador del sistema operativo.

Los semáforos son un mecanismo de esperas no ocupadas, lo que significa que permite sincronizar a los procesos de forma que no se desperdician recursos de CPU cuando un cierto no proceso no tiene actividad a realizar (la espera ocupada, también conocida como espera activa, es en la que se queda comprobando la condición hasta verificarla, como el caso de los cerrojos).

'''Granularidad''': número de recursos controlados por un semáforo

'''Problemas''': El uso de semáforos también tiene algunos inconvenientes, entre los que destacan:

* Facilidad para emplearlos incorrectamente.
* Son independientes del lenguaje de programación, y por tanto no hay comprobación ninguna en tiempo de compilación.
* No hay nada que obligue a usarlos.
* Son independientes del recurso compartido al que intentan regular.

Debido a ellos fueron desarrollados los [[Monitores]].

'''Ejemplo productor-consumidor''': Supongamos un proceso que produce y otro que consume lo producido. Lo deseable es que el productor actúe primero, y no más de 1 vez consecutiva, puesto que el consumidor consume de 1 en 1.

{|cellpadding="4"
!style="border-style: solid; border-width: 0 1px 1px 1px"|Inicializacion
!style="border-style: solid; border-width: 0 1px 1px 0"|Productor
!style="border-style: solid; border-width: 0 1px 1px 0"|Consumidor
|-
|width="200"|semaforo prod,cons;
|width="90"|while(1){
|width="90"|while(1){
|-
|semaforo_create(cons,0);
|align="center"| down (prod);
|align="center"| down (cons);
|-
|semaforo_create(prod,1);
|align="center"| produce();
|align="center"| consume();
|-
|
|align="center"| up(cons);
|align="center"| up(prod);
|-
|
| }
| }
|}

Semáforos

2011-05-07T13:51:17Z

JCGarrido: tildes

= Planificador de procesos: Diagrama de estados simplicado =

Para comprender apropiadamente cómo funcionan los semáforos vamos a recordar el diagrama de estados simplificado que emplea el planificador de procesos del sistema operativo.

|---------------|
pendiente | | recibido
evento ---------> | bloqueado |----------- evento
externo | | | | externo
| |---------------| |
| |
| planificador \/
|--------------| retira CPU |---------------|
| | -------------------> | |
| activo | | preparado |
| | <------------------- | |
|--------------| |---------------|
planificador
asigna CPU

La vida de un proceso pasa por tres estados:

* Activo: el proceso está empleando la CPU, por tanto, está ejecutándose. Hay tantos procesos activos como recurso de procesamiento disponible. Por tanto, si el sistema dispone de un único procesador, únicamente puede haber un proceso activo a la vez.
* Preparado: el proceso no está ejecutándose pero es candidato a pasar a estado activo. Es el planificador el que, en base a un criterio de planificación, decide qué proceso selecciona de la lista de procesos preparados para pasar a estado activo.
* Bloqueado: el proceso está pendiente de un evento externo, tales como la espera de finalización de un proceso hijo, una señal, una operación sobre un semáforo o una operación de lectura/escritura.

La transición de activo a preparado y viceversa depende de decisiones tomadas por el planificador del sistema operativo (que emplea algún criterio visto en clases teóricas, tales como el turno rotatorio), el programador no puede interferir en estas decisiones. Mientras que la transición de activo a bloqueado, y de bloqueado a preparado pueden ser controladas por el programador mediante llamadas al sistema.

= Semáforos =

Los semáforos son un mecanismo de sincronización de procesos inventados por [http://es.wikipedia.org/wiki/Edsger_Dijkstra Edsger Dijkstra]. Los semáforos nos permiten '''asistir al planificador del sistema operativo en su toma de decisiones''' de manera que nos permiten sincronizar la ejecución de dos o más procesos.

Los semáforos son un tipo de datos (TAD) que están compuestos por dos atributos:

* Un contador, que siempre vale >= 0.
* Una lista de procesos, inicialmente vacía.

Son usados para controlar el acceso a ciertas partes de un programa llamadas '''secciones críticas''', en la que se manipulan recursos que deben ser tratados de forma especial.

El valor del semáforo, tanto en su inicialización como a lo largo de la ejecución del proceso, es muy importante ya que será lo que controle el número de procesos accediendo al recurso compartido de manera simultánea.

El tipo mas simple de semáforo es el binario. Pueden tomar como valor 0 o 1 y sólo permite el acceso a un único proceso a la vez.

Los semáforos disponen de dos operaciones básicas que pasamos a describir en pseudocódigo:

<source lang="c">
down(semáforo s)
{
si s.contador == 0:
proceso a estado bloqueado
añade proceso a s.lista
sino:
s.contador--
}
</source>

Nótese que siempre que queramos forzar una transición de un proceso a estado bloqueado, tenemos que hacer que dicho proceso realice una operación ''down'' sobre un semáforo cuyo contador vale cero.

<source lang="c">
up(semáforo s)
{
si hay procesos en s.lista
retira proceso de s.lista
proceso a estado preparado
sino:
s.contador++
}
</source>

Nótese que una operación ''up'' sobre un semáforo en el que hay procesos en su lista resulta en que se retire uno de los procesos (el que más tiempo lleva en la lista), realizando éste la transición a estado preparado. Es un error frecuente pensar que una operación ''up'' resulte en que el proceso retirado de la lista pase a estado activo. Recuerde que las transiciones de estado activo a preparado y viceversa son siempre controladas por el planificador del sistema operativo.

Los semáforos son un mecanismo de esperas no ocupadas, lo que significa que permite sincronizar a los procesos de forma que no se desperdician recursos de CPU cuando un cierto no proceso no tiene actividad a realizar (la espera ocupada, también conocida como espera activa, es en la que se queda comprobando la condición hasta verificarla, como el caso de los cerrojos).

'''Granularidad''': número de recursos controlados por un semáforo

'''Problemas''': El uso de semáforos también tiene algunos inconvenientes, entre los que destacan:

* Facilidad para emplearlos incorrectamente.
* Son independientes del lenguaje de programación, y por tanto no hay comprobación ninguna en tiempo de compilación.
* No hay nada que obligue a usarlos.
* Son independientes del recurso compartido al que intentan regular.

Debido a ellos fueron desarrollados los [[Monitores]].

'''Ejemplo productor-consumidor''': Supongamos un proceso que produce y otro que consume lo producido. Lo deseable es que el productor actúe primero, y no más de 1 vez consecutiva, puesto que el consumidor consume de 1 en 1.

{|cellpadding="4"
!style="border-style: solid; border-width: 0 1px 1px 1px"|Inicializacion
!style="border-style: solid; border-width: 0 1px 1px 0"|Productor
!style="border-style: solid; border-width: 0 1px 1px 0"|Consumidor
|-
|width="200"|semaforo prod,cons;
|width="90"|while(1){
|width="90"|while(1){
|-
|semaforo_create(cons,0);
|align="center"| down (prod);
|align="center"| down (cons);
|-
|semaforo_create(prod,1);
|align="center"| produce();
|align="center"| consume();
|-
|
|align="center"| up(cons);
|align="center"| up(prod);
|-
|
| }
| }
|}

Cerrojos

2011-05-06T16:45:11Z

JCGarrido: Corregido un pequeño error en la frase.

= 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 hilo Hx justo antes de ejecutarse la instrucción ''cerrojo = 0;''. El hilo Hy ejecuta su código, entra en la sección crítica (Esto puede ocurrir ya que cerrojo sigue a 1) y el planificador le retira el uso del procesador dentro de ésta. A continuación, se le vuelve a asignar el procesador a Hx.

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

= Cerrojos mediante instrucciones atómicas =

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

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

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

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

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

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

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

Cerrojos

2011-05-06T15:59:32Z

JCGarrido: Corregida la última frase.

= Ejemplo de implementación =

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

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

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

... // Sección crítica

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

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

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

= Cerrojos mediante instrucciones atómicas =

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

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

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

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

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

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

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

Mecanismos de sincronización

2011-05-06T10:10:41Z

JCGarrido: Pequeña corrección en una frase(No se ha modificado el significado de la misma).

= Optimistas =

Este mecanismo debe emplearse si el programador considera que la frecuencia de acceso a un recurso compartido es baja, es decir, que supone que la probabilidad de coincidencia de dos o más procesos al recurso compartido es baja.

El siguiente ejemplo muestra el código ejecutado por dos hilos: hx y hy de un mismo proceso.

<source lang="c">
int compartida = 1, tmp;
retry:
tmp = compartida; /* almaceno el valor de la variable compartida en una temporal. */
tmp++; /* actualizo la varible temporal. */
if (compartida+1 != tmp) /* compruebo si la variable compartida ha sido modificada */
goto retry; /* mientras operaba con la variable temporal. */
</source>

La principal ventaja es el mayor grado de paralelismo.

Los inconvenientes de este tipo de mecanismo son dos:

* Se consume más memoria, pues hay que realizar una copia del recurso compartido para efectuar la comprobación.
* En situaciones de coincidencia, se tiene que volver a realizar la operación, por tanto, se desperdician recursos de procesamiento.

Por último, si el programador ha empleado una aproximación optimista para una situación en la que la frecuencia de coincidencia es alta, podría darse el caso de que un hilo no progrese en su ejecución de manera indefinida, al tener que volver a reintentar la actualización una y otra vez hasta conseguirlo sin que haya concurrencia.

= Pesimista =
Este mecanismo debe emplearse si se considera que la frecuencia de acceso al recurso compartido es alta.

En este mecanismo disponemos de tres partes:

* El protocolo de entrada, en el que se emplea un mecanismo que no permite continuar con la ejecución si otro u otros procesos están accediendo al recurso compartido.
* La sección crítica, en el que se se realizan las operaciones pertinentes con el recurso compartido.
* El protocolo de salida, en el que se vuelve a permitir el acceso al recurso compartido.

El siguiente ejemplo muestra como se implementa el control de concurrencia pesimista para 2 hilos, hx y hy:

<source lang="c">
int compartida = 1;
protocolo_de_entrada(); /* no permito acceso a variable compartida. */
compartida++; /* sección crítica: actualización de la variable compartidad. */
protocolo_de_salida(); /* vuelvo a permitir acceso a la variable compartida. */
</source>

Los protocolos de entrada y salida son, generalmente, operaciones costosas en términos de recursos de procesamiento.

El inconveniente de este mecanismo es:

*Que aunque siempre se pueda implementar, se fuerzan esperas que pueden llegar a ser innecesarias.

Por último, se podría emplear un control de concurrencia pesimista para resolver un problema que se resuelve con un control de concurrencia optimista, pero no al revés.

== Implementación del control de concurrencia pesimista ==

El control de concurrencia pesimista se puede implementar de dos formas mediante:

* Espera ocupada o activa, mediante cerrojos. En este mecanismo se comprueba continuamente la condición que permite franquear en el protocolo de entrada, por tanto, el proceso permanece en estado activo comprobando continuadamente la condición que le permite progresar en su ejecución, tiempo que está siendo desaprovechado por el procesador.
* Espera no ocupada o bloqueante, mediante semáforos, monitores y mensajes. Estos mecanismos hacen que el proceso pase a estado bloqueado cuando no se puede franquear el protocolo de entrada, por tanto, al quedar un proceso que no puede progresar en estado bloqueado, el planificador de procesos tiene que seleccionar a otro proceso.

Llamadas al sistema

2011-03-23T09:08:32Z

JCGarrido: /* Compatibilidad hacia atrás y hacia delante */ errores ortográficos corregidos

Las llamadas al sistema son el conjunto de instrucciones de medio-bajo nivel pertenecientes al sistema operativo que proveen a los programas de recursos y funciones de software y hardware que generalmente necesitan de una gestión especial por ser recursos compartidos por otros programas y procesos.

=Compatibilidad hacia atrás y hacia delante=

En un sistema operativo bien diseñado, la interfaz de las llamadas al sistema han de ser ser estables a lo largo del tiempo, de forma que la modificación de su funcionamiento interno no repercuta en el funcionamiento externo de éstas para asegurar la compatibilidad hacia atrás([http://en.wikipedia.org/wiki/Backward_compatibility Backward compatibility]). Además, aquellas llamadas que queden obsoletas o en desuso han de ser conservadas para, de la misma manera, asegurar el funcionamiento de programas antiguos ([http://en.wikipedia.org/wiki/Legacy_system?=Legacy_support Legacy Support]).

En ocasiones los sistemas operativos pueden incluir en su diseño criterios de compatibilidad hacia adelante([http://en.wikipedia.org/wiki/Forward_compatibility Fordward compatibility]). Un ejemplo de este tipo de sistemas son aquellos capaces de mostrar información detallada al usuario de aquello que no pueden comprender o los sistemas ignorantes, que son aquellos que solo ejecutan lo que pueden comprender y obvian el resto.

Conceptos básicos

2011-03-23T09:03:51Z

JCGarrido: /* Proceso */ tilde

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

= Programa =

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

= Proceso =

Un proceso es una instancia de un programa que está en ejecución. Todo proceso dispone como mínimo de una línea de ejecución. También se puede entender como la vista dinámica de un programa en ejecución.Se conoce también como la imagen del estado de la CPU y la memoria durante la ejecución de un programa.

Queda definido por: {programa, estado}

= Usuario =

Puede ser un humano o un autómata(software).

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

= Fichero =

Estructura de datos que almacena información.

Criterios de planificación

2011-03-23T08:21:11Z

JCGarrido: /* Por prioridades */ tilde

= 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 el proceso a ser asignado al procesador. No cumple varios [[Planificación de procesos#Aspectos para diseñar un buen planificador|aspectos de diseño de un buen planificador]], como repetitividad o predecibilidad. Es un criterio de planificación teórico que sirve de referencia, si se emplea un criterio de planificación que ofrece resultados peores que la planificación de procesos estocástica, entonces es que no se trata de un buen criterio de planificación.

No se ofrece un ejemplo, puesto que para un conjunto de procesos existen tantas trazas de ejecución como posible combinaciones aleatorias.

== Con conocimiento del futuro ==

En base al conocimiento del futuro se asignan los procesos. Se trata también de un criterio de planificación teórico. Si un criterio de planificación se acerca al criterio de planificación con conocimiento de futuro, entonces es que se trata de un buen planificador.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_6__|_7__|
problema _t__|_3__|_5__|_2__|_3__|_1__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|---|
Pe |---|---|---|---|---|---|---<---|---|---|xxx>---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_3__|_1__|
de tiempos _T__|_3__|_9__|_2__|_8__|_4__| z = índice de penalización
_z__|_1__|_9/5|_1__|_8/3|_4/1|

En este ejemplo, al conocer los tiempos en los que llegará cada proceso, y el tiempo de proceso, podemos buscar la forma de asignarlos de forma que, por ejemplo, consigamos la mínima penalización.

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

Se selecciona el proceso por orden de llegada al sistema, cuando un proceso está preparado se añade al final de la cola y se ejecuta según el orden de incorporacion. Su principales ventajas son su facilidad de implementación, consume muy poco tiempo de procesador (casi ninguno) y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración pueden quedar a la espera de procesos muy prolongados, así que presentarán un alto índice de penalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

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

Se selecciona el proceso que requiera menos tiempo de ejecución de entre todos los que están listos para ejecutarse. Se necesita conocer con antelación el tiempo de ejecucion de cada proceso, algo que es muy dificil en muchas ocasiones.
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. Otro inconveniente es que todo trabajo corto que llegue cuando ya ha comenzado un trabajo largo tiene un gran retraso. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
& = se ejecuta el planficador
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
planif. &---|---|---&---|---&---|---|---|---|---&---|---|---|---|---&---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_9__|_2__|_6__|_8__| z = índice de penalización
_z__|_1__|_9/5|_1__|_6/5|_8/5|

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

Se selecciona el proceso que tendrá el índice de penalización (P=T/t=(w+t)/t) de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_7__|_6__|
problema _t__|_3__|_5__|_4__|_3__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
& = se ejecuta el planficador

|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---<---|---|---|---|---|---|---|---|---|xxx|xxx|xxx|xxx|xxx>
planif.&---|---|---&---|---|---|---|---&---|---|---|---&---|---|---&---|---|---|---|---|
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''7/5'''|_1__|____|____|
z(8)|_1__|_7/5|_'''9/4'''|_4/3|_7/5|
z(12)|_1__|_7/5|_9/4|_'''8/3'''|11/5| z = índice de penalización
z(15)|_1__|_7/5|_9/4|_8/3|'''14/5'''|
z(20)|_1__|_7/5|_9/4|_8/3|14/5|

= Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos [[Multiprogramación|multiprogramables]]. Este metodo es necesario si existen procesos de alta prioridad.

== 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 del que le falta al actual, se le retira el procesador al actual proceso y se le asigna al nuevo. Su orden de complejidad es O(n), pero, a diferencia del no apropiativo, cuando entra un proceso en la lista de procesos, se ejecuta código de planificador.Con este método los procesos más largos se ven perjudicados, pues se puede retrasar tanto su tiempo de inicio, como el de finalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_4__|_6__|_12_|
problema _t__|_3__|_5__|_1__|_8__|_3__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---|---<xxx>---|---|---|---|---|---|---$---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|---|---|---|xxx|xxx|xxx|xxx|xxx>
Pe |---|---|---|---|---|---|---|---|---|---|---|---<xxx|xxx|xxx>---|---|---|---|---|
Planif.|---&---|---&---&---&---&---|---|---&---|---|---&---|---|---&---|---|---|---|---|
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_1__|_8__|_3__|
de tiempos _T__|_3__|_8__|_1__|_14_|_3__| z = índice de penalización
_z__|_1__|_8/5|_1__|14/8|_1__|

== Por prioridades ==

Se establecen índices de prioridad a cada proceso:

* '''Índice estático''': Establecido por el usuario. En el caso de sistemas operativos tipo Unix, se dispone de una índice denominado ''nice value'' cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).
* '''Índice dinámico''': Establecido por el planificador, inicialmente basado en el índice estático, después se va recalculando en base a las observaciones que realiza el planificador sobre el comportamiento de los procesos, aumentándola cuando un proceso está a la espera o disminuyéndola cuando tiene adjudicado el procesador.

El método funciona de la siguiente manera: El planificador mantiene ordenada la cola de procesos preparados, según prioridades decrecientes. Si el proceso en ejecución se bloquea, el planificador selecciona el primero de la lista. Cuando un proceso pasa a la situación de preparado, comprueba si su prioridad es mayor que la del proceso activo. En tal caso, suspende la ejecución de éste, colocándolo al principio de la cola de preparados, y elige al recién llegado; si no, lo inserta en la cola según su prioridad.
Cuando hay varios procesos con la misma prioridad se pueden aplicar diversos criterios, como seguir el orden de llegada a la cola de preparados, o el que necesite menos tiempo para acabar entre otros.

El orden es siempre O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| p = prioridad estática
_p__|_0__|-20_|_4__|_10_|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador
|---$---|---|---|---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---<---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Planif. |---&---&---&---|---&---&---|---&---|---|---|---|---|---|---|---|---|---|---|---|
-------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_6__|_4__|_6__|_12_| z = índice de penalización
_z__|_3__|_1__|_3__|12/7|

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

En este criterio, todo proceso es asignado al procesador durante un tiempo establecido denominado ''quantum'', tras el cual se le retira y se asigna a otro proceso rotatoriamente. De esta manera, los procesos acceden al procesador por turnos.

El tamaño del ''quantum'' es fundamental para determinar el comportamiento de este criterio de planificación.
Si el ''quantum'' empleado es pequeño, por ejemplo de 10 ms, suponiendo que la conmutación de procesos requiere 10ms, el 50% del tiempo se empleará el procesador para ejecutar el código que permite conmutar entre procesos. Sin embargo, si el ''quantum'' empleado es grande, por ejemplo de 5 s, la latencia será mayor, degradando la experiencia del usuario que notará como sus procesos progresan ''a saltos'', puesto que, en el peor de los casos, hasta pasados 5 s no se le asignará el procesador a otro proceso .

Si un proceso bloquea antes de consumir su ''quantum'' '''se le retira el procesador''' y se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador, pues se pasan más tiempo asignados al procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). Nótese que a mayor número de procesos preparados, mayor tiempo tardará un proceso en volver a pasar a estado activo.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| quantum = 1 unidad de tiempo

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|---|---|---|xxx|---|---|xxx|---|xxx>---|---|---|---|---|---|---|---|---|
Pc |---|---<xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<xxx|---|---|---|xxx|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|
$ $---$---$---$---$---$---$---$---$---$---$---$---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_5__|_10_|_5__|_12_| z = índice de penalización
_z__|_5/2|10/4|_5/2|12/7|

== Turno rotatorio con compensación ==

Es una variante del anterior. Para no perjudicar a los procesos cuyo comportamiento está limitado por operaciones de entrada/salida, se reinsertan en la cola en proporción al tiempo consumido. Es decir, que si un cierto proceso ha consumido el 25% de su '''quantum''', se reinserta en el 25% de la cola, contando desde el principio (dispondrá de otro quantum completo).
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== Turno rotatorio con quantum dependiente del número de procesos ==

Otra variante se trata de emplear un '''quantum''' proporcional al número de procesos que haya en estado preparado. De esta forma se obtiene una progresión más uniforme, y por tanto una mejor experiencia para el usuario. Sin embargo, esto aumenta el número de conmutaciones entre procesos. Para evitar la degradación del rendimiento por un exceso de conmutaciones, se establece un mínimo de manera que el quantum no puede ser menor a éste.

== Colas multinivel ==

En este tipo de criterio se mantienen múltiples colas con los procesos en estado preparado. Los procesos se clasifican en las colas según sus características, cada cola recibe un tratamiento distinto.

Un ejemplo sería el siguiente, compuesto de cuatro colas:

# Esta primera cola es para procesos que poseen mayor tiempo de ejecución, son los gestores de interrupción y los gestores de dispositivos (drivers). Hay que tomar los datos y almacenarlos en memoria lo antes posible para poder recoger más, aunque se posponga el procesamiento de dichos datos.
# En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
# Esta cola esta reservada a los procesos de usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
## Cola de procesos interactivos, limitados por E/S.
## Cola de procesos por lotes, limitados por el procesador.

Las colas tienen prioridad según su número, por ejemplo mientras que haya procesos preparados en la primera cola, no se mira la segunda. Esto puede dar lugar a que si hay muchos procesos de gestión de dispositivos se degrade la eficiencia del sistema.

La primera cola esta implementada con una FIFO(no apropiativo), mientras que las colas 2 y 3 se basan en un sistema de RR (turno rotatorio).

== Colas multinivel con realimentación (feedback)==

Es una variante de las colas multinivel en las que los procesos pasan de una cola a otra según su comportamiento, de manera que:

* Los procesos interactivos tienen más oportunidades de emplear el procesador.
* Los procesos por lotes disponen del procesador durante más tiempo.

Los procesos se asignan al procesador por turnos rotatorios, empleando un ''quantum'' dependiente de la cola en la que se encuentren. Los procesos que consumen el ''quantum'' asignado completamente un número determinado de veces pasan a colas en las que se asignan ''quantum'' mayores. Nótese que los procesos que no consumen su ''quantum'' muestran un comportamiento interactivo. Para no discriminar a los procesos que se encuentran en las colas con ''quantum'' menores, se les dan más oportunidades de ejecución.

Por ejemplo, en un sencillo planificador de colas multinivel con realimentación compuesto por dos colas:

* En la primera cola se le asignan un ''quantum'' de 2 unidades de tiempo a los procesos.
* En la segunda cola se le asignan un ''quantum'' de 1 unidad de tiempo a los procesos.

Si un proceso no consume el ''quantum'' asignado dos veces, pasa a la cola en la que en la se le asignan ''quantum'' de 1 unidad de tiempo.

Para que los procesos interactivos no salgan perjudicados, en aras de hacer un reparto del procesador más equitativo, se le dan dos oportunidades de ejecución a los procesos situados en la cola con ''quantum'' de 1 unidad de tiempo. De esta manera, los procesos de la primera cola reciben una oportunidad de ejecución con un ''quantum'' de 2 unidades de tiempo y los de la segunda reciben dos oportunidades de ejecución con un ''quantum'' de 1 unidad de tiempo.

Criterios de planificación

2011-03-23T08:19:46Z

JCGarrido: /* El siguiente, el más corto (Shortest Job First: SJF) */ editada de nuevo la frase para que sea más comprensible.

= 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 el proceso a ser asignado al procesador. No cumple varios [[Planificación de procesos#Aspectos para diseñar un buen planificador|aspectos de diseño de un buen planificador]], como repetitividad o predecibilidad. Es un criterio de planificación teórico que sirve de referencia, si se emplea un criterio de planificación que ofrece resultados peores que la planificación de procesos estocástica, entonces es que no se trata de un buen criterio de planificación.

No se ofrece un ejemplo, puesto que para un conjunto de procesos existen tantas trazas de ejecución como posible combinaciones aleatorias.

== Con conocimiento del futuro ==

En base al conocimiento del futuro se asignan los procesos. Se trata también de un criterio de planificación teórico. Si un criterio de planificación se acerca al criterio de planificación con conocimiento de futuro, entonces es que se trata de un buen planificador.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_6__|_7__|
problema _t__|_3__|_5__|_2__|_3__|_1__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|---|
Pe |---|---|---|---|---|---|---<---|---|---|xxx>---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_3__|_1__|
de tiempos _T__|_3__|_9__|_2__|_8__|_4__| z = índice de penalización
_z__|_1__|_9/5|_1__|_8/3|_4/1|

En este ejemplo, al conocer los tiempos en los que llegará cada proceso, y el tiempo de proceso, podemos buscar la forma de asignarlos de forma que, por ejemplo, consigamos la mínima penalización.

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

Se selecciona el proceso por orden de llegada al sistema, cuando un proceso está preparado se añade al final de la cola y se ejecuta según el orden de incorporacion. Su principales ventajas son su facilidad de implementación, consume muy poco tiempo de procesador (casi ninguno) y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración pueden quedar a la espera de procesos muy prolongados, así que presentarán un alto índice de penalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

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

Se selecciona el proceso que requiera menos tiempo de ejecución de entre todos los que están listos para ejecutarse. Se necesita conocer con antelación el tiempo de ejecucion de cada proceso, algo que es muy dificil en muchas ocasiones.
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. Otro inconveniente es que todo trabajo corto que llegue cuando ya ha comenzado un trabajo largo tiene un gran retraso. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
& = se ejecuta el planficador
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
planif. &---|---|---&---|---&---|---|---|---|---&---|---|---|---|---&---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_9__|_2__|_6__|_8__| z = índice de penalización
_z__|_1__|_9/5|_1__|_6/5|_8/5|

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

Se selecciona el proceso que tendrá el índice de penalización (P=T/t=(w+t)/t) de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_7__|_6__|
problema _t__|_3__|_5__|_4__|_3__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
& = se ejecuta el planficador

|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---<---|---|---|---|---|---|---|---|---|xxx|xxx|xxx|xxx|xxx>
planif.&---|---|---&---|---|---|---|---&---|---|---|---&---|---|---&---|---|---|---|---|
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''7/5'''|_1__|____|____|
z(8)|_1__|_7/5|_'''9/4'''|_4/3|_7/5|
z(12)|_1__|_7/5|_9/4|_'''8/3'''|11/5| z = índice de penalización
z(15)|_1__|_7/5|_9/4|_8/3|'''14/5'''|
z(20)|_1__|_7/5|_9/4|_8/3|14/5|

= Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos [[Multiprogramación|multiprogramables]]. Este metodo es necesario si existen procesos de alta prioridad.

== 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 del que le falta al actual, se le retira el procesador al actual proceso y se le asigna al nuevo. Su orden de complejidad es O(n), pero, a diferencia del no apropiativo, cuando entra un proceso en la lista de procesos, se ejecuta código de planificador.Con este método los procesos más largos se ven perjudicados, pues se puede retrasar tanto su tiempo de inicio, como el de finalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_4__|_6__|_12_|
problema _t__|_3__|_5__|_1__|_8__|_3__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---|---<xxx>---|---|---|---|---|---|---$---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|---|---|---|xxx|xxx|xxx|xxx|xxx>
Pe |---|---|---|---|---|---|---|---|---|---|---|---<xxx|xxx|xxx>---|---|---|---|---|
Planif.|---&---|---&---&---&---&---|---|---&---|---|---&---|---|---&---|---|---|---|---|
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_1__|_8__|_3__|
de tiempos _T__|_3__|_8__|_1__|_14_|_3__| z = índice de penalización
_z__|_1__|_8/5|_1__|14/8|_1__|

== Por prioridades ==

Se establecen índices de prioridad a cada proceso:

* '''Índice estático''': Establecido por el usuario. En el caso de sistemas operativos tipo Unix, se dispone de una índice denominado ''nice value'' cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).
* '''Índice dinámico''': Establecido por el planificador, inicialmente basado en el índice estático, después se va recalculando en base a las observaciones que realiza el planificador sobre el comportamiento de los procesos, aumentándola cuando un proceso está a la espera o disminuyendola cuando tiene adjudicado el procesador.

El método funciona de la siguiente manera: El planificador mantiene ordenada la cola de procesos preparados, según prioridades decrecientes. Si el proceso en ejecución se bloquea, el planificador selecciona el primero de la lista. Cuando un proceso pasa a la situación de preparado, comprueba si su prioridad es mayor que la del proceso activo. En tal caso, suspende la ejecución de éste, colocándolo al principio de la cola de preparados, y elige al recién llegado; si no, lo inserta en la cola según su prioridad.
Cuando hay varios procesos con la misma prioridad se pueden aplicar diversos criterios, como seguir el orden de llegada a la cola de preparados, o el que necesite menos tiempo para acabar entre otros.

El orden es siempre O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| p = prioridad estática
_p__|_0__|-20_|_4__|_10_|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador
|---$---|---|---|---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---<---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Planif. |---&---&---&---|---&---&---|---&---|---|---|---|---|---|---|---|---|---|---|---|
-------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_6__|_4__|_6__|_12_| z = índice de penalización
_z__|_3__|_1__|_3__|12/7|

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

En este criterio, todo proceso es asignado al procesador durante un tiempo establecido denominado ''quantum'', tras el cual se le retira y se asigna a otro proceso rotatoriamente. De esta manera, los procesos acceden al procesador por turnos.

El tamaño del ''quantum'' es fundamental para determinar el comportamiento de este criterio de planificación.
Si el ''quantum'' empleado es pequeño, por ejemplo de 10 ms, suponiendo que la conmutación de procesos requiere 10ms, el 50% del tiempo se empleará el procesador para ejecutar el código que permite conmutar entre procesos. Sin embargo, si el ''quantum'' empleado es grande, por ejemplo de 5 s, la latencia será mayor, degradando la experiencia del usuario que notará como sus procesos progresan ''a saltos'', puesto que, en el peor de los casos, hasta pasados 5 s no se le asignará el procesador a otro proceso .

Si un proceso bloquea antes de consumir su ''quantum'' '''se le retira el procesador''' y se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador, pues se pasan más tiempo asignados al procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). Nótese que a mayor número de procesos preparados, mayor tiempo tardará un proceso en volver a pasar a estado activo.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| quantum = 1 unidad de tiempo

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|---|---|---|xxx|---|---|xxx|---|xxx>---|---|---|---|---|---|---|---|---|
Pc |---|---<xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<xxx|---|---|---|xxx|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|
$ $---$---$---$---$---$---$---$---$---$---$---$---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_5__|_10_|_5__|_12_| z = índice de penalización
_z__|_5/2|10/4|_5/2|12/7|

== Turno rotatorio con compensación ==

Es una variante del anterior. Para no perjudicar a los procesos cuyo comportamiento está limitado por operaciones de entrada/salida, se reinsertan en la cola en proporción al tiempo consumido. Es decir, que si un cierto proceso ha consumido el 25% de su '''quantum''', se reinserta en el 25% de la cola, contando desde el principio (dispondrá de otro quantum completo).
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== Turno rotatorio con quantum dependiente del número de procesos ==

Otra variante se trata de emplear un '''quantum''' proporcional al número de procesos que haya en estado preparado. De esta forma se obtiene una progresión más uniforme, y por tanto una mejor experiencia para el usuario. Sin embargo, esto aumenta el número de conmutaciones entre procesos. Para evitar la degradación del rendimiento por un exceso de conmutaciones, se establece un mínimo de manera que el quantum no puede ser menor a éste.

== Colas multinivel ==

En este tipo de criterio se mantienen múltiples colas con los procesos en estado preparado. Los procesos se clasifican en las colas según sus características, cada cola recibe un tratamiento distinto.

Un ejemplo sería el siguiente, compuesto de cuatro colas:

# Esta primera cola es para procesos que poseen mayor tiempo de ejecución, son los gestores de interrupción y los gestores de dispositivos (drivers). Hay que tomar los datos y almacenarlos en memoria lo antes posible para poder recoger más, aunque se posponga el procesamiento de dichos datos.
# En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
# Esta cola esta reservada a los procesos de usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
## Cola de procesos interactivos, limitados por E/S.
## Cola de procesos por lotes, limitados por el procesador.

Las colas tienen prioridad según su número, por ejemplo mientras que haya procesos preparados en la primera cola, no se mira la segunda. Esto puede dar lugar a que si hay muchos procesos de gestión de dispositivos se degrade la eficiencia del sistema.

La primera cola esta implementada con una FIFO(no apropiativo), mientras que las colas 2 y 3 se basan en un sistema de RR (turno rotatorio).

== Colas multinivel con realimentación (feedback)==

Es una variante de las colas multinivel en las que los procesos pasan de una cola a otra según su comportamiento, de manera que:

* Los procesos interactivos tienen más oportunidades de emplear el procesador.
* Los procesos por lotes disponen del procesador durante más tiempo.

Los procesos se asignan al procesador por turnos rotatorios, empleando un ''quantum'' dependiente de la cola en la que se encuentren. Los procesos que consumen el ''quantum'' asignado completamente un número determinado de veces pasan a colas en las que se asignan ''quantum'' mayores. Nótese que los procesos que no consumen su ''quantum'' muestran un comportamiento interactivo. Para no discriminar a los procesos que se encuentran en las colas con ''quantum'' menores, se les dan más oportunidades de ejecución.

Por ejemplo, en un sencillo planificador de colas multinivel con realimentación compuesto por dos colas:

* En la primera cola se le asignan un ''quantum'' de 2 unidades de tiempo a los procesos.
* En la segunda cola se le asignan un ''quantum'' de 1 unidad de tiempo a los procesos.

Si un proceso no consume el ''quantum'' asignado dos veces, pasa a la cola en la que en la se le asignan ''quantum'' de 1 unidad de tiempo.

Para que los procesos interactivos no salgan perjudicados, en aras de hacer un reparto del procesador más equitativo, se le dan dos oportunidades de ejecución a los procesos situados en la cola con ''quantum'' de 1 unidad de tiempo. De esta manera, los procesos de la primera cola reciben una oportunidad de ejecución con un ''quantum'' de 2 unidades de tiempo y los de la segunda reciben dos oportunidades de ejecución con un ''quantum'' de 1 unidad de tiempo.

Criterios de planificación

2011-03-23T08:18:23Z

JCGarrido: /* El siguiente, el más corto (Shortest Job First: SJF) */ Modificada la explicación sin modificar el contexto.

= 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 el proceso a ser asignado al procesador. No cumple varios [[Planificación de procesos#Aspectos para diseñar un buen planificador|aspectos de diseño de un buen planificador]], como repetitividad o predecibilidad. Es un criterio de planificación teórico que sirve de referencia, si se emplea un criterio de planificación que ofrece resultados peores que la planificación de procesos estocástica, entonces es que no se trata de un buen criterio de planificación.

No se ofrece un ejemplo, puesto que para un conjunto de procesos existen tantas trazas de ejecución como posible combinaciones aleatorias.

== Con conocimiento del futuro ==

En base al conocimiento del futuro se asignan los procesos. Se trata también de un criterio de planificación teórico. Si un criterio de planificación se acerca al criterio de planificación con conocimiento de futuro, entonces es que se trata de un buen planificador.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_6__|_7__|
problema _t__|_3__|_5__|_2__|_3__|_1__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|---|
Pe |---|---|---|---|---|---|---<---|---|---|xxx>---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_3__|_1__|
de tiempos _T__|_3__|_9__|_2__|_8__|_4__| z = índice de penalización
_z__|_1__|_9/5|_1__|_8/3|_4/1|

En este ejemplo, al conocer los tiempos en los que llegará cada proceso, y el tiempo de proceso, podemos buscar la forma de asignarlos de forma que, por ejemplo, consigamos la mínima penalización.

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

Se selecciona el proceso por orden de llegada al sistema, cuando un proceso está preparado se añade al final de la cola y se ejecuta según el orden de incorporacion. Su principales ventajas son su facilidad de implementación, consume muy poco tiempo de procesador (casi ninguno) y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración pueden quedar a la espera de procesos muy prolongados, así que presentarán un alto índice de penalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

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

Se selecciona el proceso que requiera menos tiempo de ejecución de entre todos los que están listos para ejecutarse. Se necesita conocer con antelación el tiempo de ejecucion de cada proceso, algo que es muy dificil en muchas ocasiones.
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. Otro inconveniente es que todo trabajo corto que llegue cuando ya ha comenzado un trabajo largo tiene un gran retraso. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
& = se ejecuta el planficador
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
planif. &---|---|---&---|---&---|---|---|---|---&---|---|---|---|---&---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_9__|_2__|_6__|_8__| z = índice de penalización
_z__|_1__|_9/5|_1__|_6/5|_8/5|

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

Se selecciona el proceso que tendrá el índice de penalización (P=T/t=(w+t)/t) de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_7__|_6__|
problema _t__|_3__|_5__|_4__|_3__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
& = se ejecuta el planficador

|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---<---|---|---|---|---|---|---|---|---|xxx|xxx|xxx|xxx|xxx>
planif.&---|---|---&---|---|---|---|---&---|---|---|---&---|---|---&---|---|---|---|---|
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''7/5'''|_1__|____|____|
z(8)|_1__|_7/5|_'''9/4'''|_4/3|_7/5|
z(12)|_1__|_7/5|_9/4|_'''8/3'''|11/5| z = índice de penalización
z(15)|_1__|_7/5|_9/4|_8/3|'''14/5'''|
z(20)|_1__|_7/5|_9/4|_8/3|14/5|

= Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos [[Multiprogramación|multiprogramables]]. Este metodo es necesario si existen procesos de alta prioridad.

== 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 del que le falta al actual, se le retira el procesador al anterior proceso y se le asigna al nuevo. Su orden de complejidad es O(n), pero, a diferencia del no apropiativo, cuando entra un proceso en la lista de procesos, se ejecuta código de planificador.Con este método los procesos más largos se ven perjudicados, pues se puede retrasar tanto su tiempo de inicio, como el de finalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_4__|_6__|_12_|
problema _t__|_3__|_5__|_1__|_8__|_3__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---|---<xxx>---|---|---|---|---|---|---$---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|---|---|---|xxx|xxx|xxx|xxx|xxx>
Pe |---|---|---|---|---|---|---|---|---|---|---|---<xxx|xxx|xxx>---|---|---|---|---|
Planif.|---&---|---&---&---&---&---|---|---&---|---|---&---|---|---&---|---|---|---|---|
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_1__|_8__|_3__|
de tiempos _T__|_3__|_8__|_1__|_14_|_3__| z = índice de penalización
_z__|_1__|_8/5|_1__|14/8|_1__|

== Por prioridades ==

Se establecen índices de prioridad a cada proceso:

* '''Índice estático''': Establecido por el usuario. En el caso de sistemas operativos tipo Unix, se dispone de una índice denominado ''nice value'' cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).
* '''Índice dinámico''': Establecido por el planificador, inicialmente basado en el índice estático, después se va recalculando en base a las observaciones que realiza el planificador sobre el comportamiento de los procesos, aumentándola cuando un proceso está a la espera o disminuyendola cuando tiene adjudicado el procesador.

El método funciona de la siguiente manera: El planificador mantiene ordenada la cola de procesos preparados, según prioridades decrecientes. Si el proceso en ejecución se bloquea, el planificador selecciona el primero de la lista. Cuando un proceso pasa a la situación de preparado, comprueba si su prioridad es mayor que la del proceso activo. En tal caso, suspende la ejecución de éste, colocándolo al principio de la cola de preparados, y elige al recién llegado; si no, lo inserta en la cola según su prioridad.
Cuando hay varios procesos con la misma prioridad se pueden aplicar diversos criterios, como seguir el orden de llegada a la cola de preparados, o el que necesite menos tiempo para acabar entre otros.

El orden es siempre O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| p = prioridad estática
_p__|_0__|-20_|_4__|_10_|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador
|---$---|---|---|---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---<---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Planif. |---&---&---&---|---&---&---|---&---|---|---|---|---|---|---|---|---|---|---|---|
-------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_6__|_4__|_6__|_12_| z = índice de penalización
_z__|_3__|_1__|_3__|12/7|

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

En este criterio, todo proceso es asignado al procesador durante un tiempo establecido denominado ''quantum'', tras el cual se le retira y se asigna a otro proceso rotatoriamente. De esta manera, los procesos acceden al procesador por turnos.

El tamaño del ''quantum'' es fundamental para determinar el comportamiento de este criterio de planificación.
Si el ''quantum'' empleado es pequeño, por ejemplo de 10 ms, suponiendo que la conmutación de procesos requiere 10ms, el 50% del tiempo se empleará el procesador para ejecutar el código que permite conmutar entre procesos. Sin embargo, si el ''quantum'' empleado es grande, por ejemplo de 5 s, la latencia será mayor, degradando la experiencia del usuario que notará como sus procesos progresan ''a saltos'', puesto que, en el peor de los casos, hasta pasados 5 s no se le asignará el procesador a otro proceso .

Si un proceso bloquea antes de consumir su ''quantum'' '''se le retira el procesador''' y se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador, pues se pasan más tiempo asignados al procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). Nótese que a mayor número de procesos preparados, mayor tiempo tardará un proceso en volver a pasar a estado activo.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| quantum = 1 unidad de tiempo

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|---|---|---|xxx|---|---|xxx|---|xxx>---|---|---|---|---|---|---|---|---|
Pc |---|---<xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<xxx|---|---|---|xxx|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|
$ $---$---$---$---$---$---$---$---$---$---$---$---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_5__|_10_|_5__|_12_| z = índice de penalización
_z__|_5/2|10/4|_5/2|12/7|

== Turno rotatorio con compensación ==

Es una variante del anterior. Para no perjudicar a los procesos cuyo comportamiento está limitado por operaciones de entrada/salida, se reinsertan en la cola en proporción al tiempo consumido. Es decir, que si un cierto proceso ha consumido el 25% de su '''quantum''', se reinserta en el 25% de la cola, contando desde el principio (dispondrá de otro quantum completo).
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== Turno rotatorio con quantum dependiente del número de procesos ==

Otra variante se trata de emplear un '''quantum''' proporcional al número de procesos que haya en estado preparado. De esta forma se obtiene una progresión más uniforme, y por tanto una mejor experiencia para el usuario. Sin embargo, esto aumenta el número de conmutaciones entre procesos. Para evitar la degradación del rendimiento por un exceso de conmutaciones, se establece un mínimo de manera que el quantum no puede ser menor a éste.

== Colas multinivel ==

En este tipo de criterio se mantienen múltiples colas con los procesos en estado preparado. Los procesos se clasifican en las colas según sus características, cada cola recibe un tratamiento distinto.

Un ejemplo sería el siguiente, compuesto de cuatro colas:

# Esta primera cola es para procesos que poseen mayor tiempo de ejecución, son los gestores de interrupción y los gestores de dispositivos (drivers). Hay que tomar los datos y almacenarlos en memoria lo antes posible para poder recoger más, aunque se posponga el procesamiento de dichos datos.
# En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
# Esta cola esta reservada a los procesos de usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
## Cola de procesos interactivos, limitados por E/S.
## Cola de procesos por lotes, limitados por el procesador.

Las colas tienen prioridad según su número, por ejemplo mientras que haya procesos preparados en la primera cola, no se mira la segunda. Esto puede dar lugar a que si hay muchos procesos de gestión de dispositivos se degrade la eficiencia del sistema.

La primera cola esta implementada con una FIFO(no apropiativo), mientras que las colas 2 y 3 se basan en un sistema de RR (turno rotatorio).

== Colas multinivel con realimentación (feedback)==

Es una variante de las colas multinivel en las que los procesos pasan de una cola a otra según su comportamiento, de manera que:

* Los procesos interactivos tienen más oportunidades de emplear el procesador.
* Los procesos por lotes disponen del procesador durante más tiempo.

Los procesos se asignan al procesador por turnos rotatorios, empleando un ''quantum'' dependiente de la cola en la que se encuentren. Los procesos que consumen el ''quantum'' asignado completamente un número determinado de veces pasan a colas en las que se asignan ''quantum'' mayores. Nótese que los procesos que no consumen su ''quantum'' muestran un comportamiento interactivo. Para no discriminar a los procesos que se encuentran en las colas con ''quantum'' menores, se les dan más oportunidades de ejecución.

Por ejemplo, en un sencillo planificador de colas multinivel con realimentación compuesto por dos colas:

* En la primera cola se le asignan un ''quantum'' de 2 unidades de tiempo a los procesos.
* En la segunda cola se le asignan un ''quantum'' de 1 unidad de tiempo a los procesos.

Si un proceso no consume el ''quantum'' asignado dos veces, pasa a la cola en la que en la se le asignan ''quantum'' de 1 unidad de tiempo.

Para que los procesos interactivos no salgan perjudicados, en aras de hacer un reparto del procesador más equitativo, se le dan dos oportunidades de ejecución a los procesos situados en la cola con ''quantum'' de 1 unidad de tiempo. De esta manera, los procesos de la primera cola reciben una oportunidad de ejecución con un ''quantum'' de 2 unidades de tiempo y los de la segunda reciben dos oportunidades de ejecución con un ''quantum'' de 1 unidad de tiempo.

Criterios de planificación

2011-03-23T08:13:50Z

JCGarrido: /* Basado en índice de penalización */ Modificada la explicación,eliminada la primera frase, porque no se elige el proceso con más t preparado, sino el que va a tener mayor índice d p.contrdecia al ej

= 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 el proceso a ser asignado al procesador. No cumple varios [[Planificación de procesos#Aspectos para diseñar un buen planificador|aspectos de diseño de un buen planificador]], como repetitividad o predecibilidad. Es un criterio de planificación teórico que sirve de referencia, si se emplea un criterio de planificación que ofrece resultados peores que la planificación de procesos estocástica, entonces es que no se trata de un buen criterio de planificación.

No se ofrece un ejemplo, puesto que para un conjunto de procesos existen tantas trazas de ejecución como posible combinaciones aleatorias.

== Con conocimiento del futuro ==

En base al conocimiento del futuro se asignan los procesos. Se trata también de un criterio de planificación teórico. Si un criterio de planificación se acerca al criterio de planificación con conocimiento de futuro, entonces es que se trata de un buen planificador.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_6__|_7__|
problema _t__|_3__|_5__|_2__|_3__|_1__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|---|
Pe |---|---|---|---|---|---|---<---|---|---|xxx>---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_3__|_1__|
de tiempos _T__|_3__|_9__|_2__|_8__|_4__| z = índice de penalización
_z__|_1__|_9/5|_1__|_8/3|_4/1|

En este ejemplo, al conocer los tiempos en los que llegará cada proceso, y el tiempo de proceso, podemos buscar la forma de asignarlos de forma que, por ejemplo, consigamos la mínima penalización.

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

Se selecciona el proceso por orden de llegada al sistema, cuando un proceso está preparado se añade al final de la cola y se ejecuta según el orden de incorporacion. Su principales ventajas son su facilidad de implementación, consume muy poco tiempo de procesador (casi ninguno) y su orden de complejidad, O(1). Su desventaja es que los procesos de corta duración pueden quedar a la espera de procesos muy prolongados, así que presentarán un alto índice de penalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_7__|_7__|_6__|_8__| z = índice de penalización
_z__|_1__|_7/5|_7/2|_6/5|_8/5|

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

Se selecciona el proceso que requiera menos tiempo de ejecución de entre todos los que están listos para ejecutarse. Se necesita conocer con antelación el tiempo de ejecucion de cada proceso, algo que es muy dificil en muchas ocasiones.
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. Otro inconveniente es que todo trabajo corto que llegue cuando ya ha comenzado un trabajo largo tiene un gran retraso. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_9__|_12_|
problema _t__|_3__|_5__|_2__|_5__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
& = se ejecuta el planficador
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---|---|---<---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---|---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|xxx|xxx>
planif. &---|---|---&---|---&---|---|---|---|---&---|---|---|---|---&---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_2__|_5__|_5__|
de tiempos _T__|_3__|_9__|_2__|_6__|_8__| z = índice de penalización
_z__|_1__|_9/5|_1__|_6/5|_8/5|

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

Se selecciona el proceso que tendrá el índice de penalización (P=T/t=(w+t)/t) de mayor valor. Este método puede producir aplazamientos de ejecución de procesos,pero no son indefinidos. Su orden de complejidad es O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_3__|_7__|_6__|
problema _t__|_3__|_5__|_4__|_3__|_5__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
& = se ejecuta el planficador

|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---|---<---|---|---|---|---|xxx|xxx|xxx>---|---|---|---|---|
Pe |---|---|---|---|---|---<---|---|---|---|---|---|---|---|---|xxx|xxx|xxx|xxx|xxx>
planif.&---|---|---&---|---|---|---|---&---|---|---|---&---|---|---&---|---|---|---|---|
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_4__|_3__|_5__|
de tiempos _T__|_3__|_7__|_9__|_13_|_11_|
z(3)|_1__|_'''7/5'''|_1__|____|____|
z(8)|_1__|_7/5|_'''9/4'''|_4/3|_7/5|
z(12)|_1__|_7/5|_9/4|_'''8/3'''|11/5| z = índice de penalización
z(15)|_1__|_7/5|_9/4|_8/3|'''14/5'''|
z(20)|_1__|_7/5|_9/4|_8/3|14/5|

= Métodos apropiativos =

El planificador puede retirar el procesador en cualquier momento al proceso activo. Suele darse en sistemas operativos [[Multiprogramación|multiprogramables]]. Este metodo es necesario si existen procesos de alta prioridad.

== 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, sólo si el proceso nuevo necesita menos tiempo del que le falta al actual. Su orden de complejidad es O(n), pero, a diferencia del no apropiativo, cuando entra un proceso en la lista de procesos, se ejecuta código de planificador.Con este método los procesos más largos se ven perjudicados, pues se puede retrasar tanto su tiempo de inicio, como el de finalización.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Datos del _H0_|_0__|_1__|_4__|_6__|_12_|
problema _t__|_3__|_5__|_1__|_8__|_3__|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<---|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---|---|---<xxx>---|---|---|---|---|---|---$---|---|---|---|---|---|---|---|
Pd |---|---|---|---|---|---<---|---|---|xxx|xxx|xxx|---|---|---|xxx|xxx|xxx|xxx|xxx>
Pe |---|---|---|---|---|---|---|---|---|---|---|---<xxx|xxx|xxx>---|---|---|---|---|
Planif.|---&---|---&---&---&---&---|---|---&---|---|---&---|---|---&---|---|---|---|---|
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|_Pe_|
Cálculos _t__|_3__|_5__|_1__|_8__|_3__|
de tiempos _T__|_3__|_8__|_1__|_14_|_3__| z = índice de penalización
_z__|_1__|_8/5|_1__|14/8|_1__|

== Por prioridades ==

Se establecen índices de prioridad a cada proceso:

* '''Índice estático''': Establecido por el usuario. En el caso de sistemas operativos tipo Unix, se dispone de una índice denominado ''nice value'' cuyos valores están entre -20 (máxima prioridad) y 19 (mínima prioridad).
* '''Índice dinámico''': Establecido por el planificador, inicialmente basado en el índice estático, después se va recalculando en base a las observaciones que realiza el planificador sobre el comportamiento de los procesos, aumentándola cuando un proceso está a la espera o disminuyendola cuando tiene adjudicado el procesador.

El método funciona de la siguiente manera: El planificador mantiene ordenada la cola de procesos preparados, según prioridades decrecientes. Si el proceso en ejecución se bloquea, el planificador selecciona el primero de la lista. Cuando un proceso pasa a la situación de preparado, comprueba si su prioridad es mayor que la del proceso activo. En tal caso, suspende la ejecución de éste, colocándolo al principio de la cola de preparados, y elige al recién llegado; si no, lo inserta en la cola según su prioridad.
Cuando hay varios procesos con la misma prioridad se pueden aplicar diversos criterios, como seguir el orden de llegada a la cola de preparados, o el que necesite menos tiempo para acabar entre otros.

El orden es siempre O(n).

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| p = prioridad estática
_p__|_0__|-20_|_4__|_10_|

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
& = se ejecuta el código del planificador
|---$---|---|---|---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|xxx|xxx|xxx>---$---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pc |---|---<---|---|---|---|xxx|xxx>---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<---|---|---|---|---|xxx|xxx|xxx|xxx|xxx|xxx|xxx>---|---|---|---|---|
Planif. |---&---&---&---|---&---&---|---&---|---|---|---|---|---|---|---|---|---|---|---|
-------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_6__|_4__|_6__|_12_| z = índice de penalización
_z__|_3__|_1__|_3__|12/7|

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

En este criterio, todo proceso es asignado al procesador durante un tiempo establecido denominado ''quantum'', tras el cual se le retira y se asigna a otro proceso rotatoriamente. De esta manera, los procesos acceden al procesador por turnos.

El tamaño del ''quantum'' es fundamental para determinar el comportamiento de este criterio de planificación.
Si el ''quantum'' empleado es pequeño, por ejemplo de 10 ms, suponiendo que la conmutación de procesos requiere 10ms, el 50% del tiempo se empleará el procesador para ejecutar el código que permite conmutar entre procesos. Sin embargo, si el ''quantum'' empleado es grande, por ejemplo de 5 s, la latencia será mayor, degradando la experiencia del usuario que notará como sus procesos progresan ''a saltos'', puesto que, en el peor de los casos, hasta pasados 5 s no se le asignará el procesador a otro proceso .

Si un proceso bloquea antes de consumir su ''quantum'' '''se le retira el procesador''' y se añade al final de la cola. Esto beneficia a los procesos cuyo comportamiento está limitado por el procesador, pues se pasan más tiempo asignados al procesador.

Este criterio se puede implementar con una cola, de manera que la complejidad de la selección de un proceso es O(1). Nótese que a mayor número de procesos preparados, mayor tiempo tardará un proceso en volver a pasar a estado activo.

Ejemplo:

____|_Pa_|_Pb_|_Pc_|_Pd_|
Datos del _H0_|_0__|_1__|_2__|_3__|
problema _t__|_2__|_4__|_2__|_7__| quantum = 1 unidad de tiempo

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento
$ = indica la ejecución del planificador para retirar un
proceso y establecer otro según el criterio
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pa <xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Pb |---<xxx|---|---|---|xxx|---|---|xxx|---|xxx>---|---|---|---|---|---|---|---|---|
Pc |---|---<xxx|---|---|---|xxx>---|---|---|---|---|---|---|---|---|---|---|---|---|
Pd |---|---|---<xxx|---|---|---|xxx|---|xxx|---|xxx|xxx|xxx|xxx>---|---|---|---|---|
$ $---$---$---$---$---$---$---$---$---$---$---$---|---|---|---|---|---|---|---|---|
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

____|_Pa_|_Pb_|_Pc_|_Pd_|
Cálculos _t__|_2__|_4__|_2__|_7__|
de tiempos _T__|_5__|_10_|_5__|_12_| z = índice de penalización
_z__|_5/2|10/4|_5/2|12/7|

== Turno rotatorio con compensación ==

Es una variante del anterior. Para no perjudicar a los procesos cuyo comportamiento está limitado por operaciones de entrada/salida, se reinsertan en la cola en proporción al tiempo consumido. Es decir, que si un cierto proceso ha consumido el 25% de su '''quantum''', se reinserta en el 25% de la cola, contando desde el principio (dispondrá de otro quantum completo).
Este tipo de criterio tiene un problema y es que se pueden posponer indefinidamente algunos procesos si hay varios procesos que bloqueen.

== Turno rotatorio con quantum dependiente del número de procesos ==

Otra variante se trata de emplear un '''quantum''' proporcional al número de procesos que haya en estado preparado. De esta forma se obtiene una progresión más uniforme, y por tanto una mejor experiencia para el usuario. Sin embargo, esto aumenta el número de conmutaciones entre procesos. Para evitar la degradación del rendimiento por un exceso de conmutaciones, se establece un mínimo de manera que el quantum no puede ser menor a éste.

== Colas multinivel ==

En este tipo de criterio se mantienen múltiples colas con los procesos en estado preparado. Los procesos se clasifican en las colas según sus características, cada cola recibe un tratamiento distinto.

Un ejemplo sería el siguiente, compuesto de cuatro colas:

# Esta primera cola es para procesos que poseen mayor tiempo de ejecución, son los gestores de interrupción y los gestores de dispositivos (drivers). Hay que tomar los datos y almacenarlos en memoria lo antes posible para poder recoger más, aunque se posponga el procesamiento de dichos datos.
# En esta cola se almacenan los procesos del servidor, tales como : proceso administrador de memoria, administrador de ficheros, administrador de red, etc.
# Esta cola esta reservada a los procesos de usuario (procesos útiles para el usuario). Esta se divide a su vez en dos colas:
## Cola de procesos interactivos, limitados por E/S.
## Cola de procesos por lotes, limitados por el procesador.

Las colas tienen prioridad según su número, por ejemplo mientras que haya procesos preparados en la primera cola, no se mira la segunda. Esto puede dar lugar a que si hay muchos procesos de gestión de dispositivos se degrade la eficiencia del sistema.

La primera cola esta implementada con una FIFO(no apropiativo), mientras que las colas 2 y 3 se basan en un sistema de RR (turno rotatorio).

== Colas multinivel con realimentación (feedback)==

Es una variante de las colas multinivel en las que los procesos pasan de una cola a otra según su comportamiento, de manera que:

* Los procesos interactivos tienen más oportunidades de emplear el procesador.
* Los procesos por lotes disponen del procesador durante más tiempo.

Los procesos se asignan al procesador por turnos rotatorios, empleando un ''quantum'' dependiente de la cola en la que se encuentren. Los procesos que consumen el ''quantum'' asignado completamente un número determinado de veces pasan a colas en las que se asignan ''quantum'' mayores. Nótese que los procesos que no consumen su ''quantum'' muestran un comportamiento interactivo. Para no discriminar a los procesos que se encuentran en las colas con ''quantum'' menores, se les dan más oportunidades de ejecución.

Por ejemplo, en un sencillo planificador de colas multinivel con realimentación compuesto por dos colas:

* En la primera cola se le asignan un ''quantum'' de 2 unidades de tiempo a los procesos.
* En la segunda cola se le asignan un ''quantum'' de 1 unidad de tiempo a los procesos.

Si un proceso no consume el ''quantum'' asignado dos veces, pasa a la cola en la que en la se le asignan ''quantum'' de 1 unidad de tiempo.

Para que los procesos interactivos no salgan perjudicados, en aras de hacer un reparto del procesador más equitativo, se le dan dos oportunidades de ejecución a los procesos situados en la cola con ''quantum'' de 1 unidad de tiempo. De esta manera, los procesos de la primera cola reciben una oportunidad de ejecución con un ''quantum'' de 2 unidades de tiempo y los de la segunda reciben dos oportunidades de ejecución con un ''quantum'' de 1 unidad de tiempo.

Planificación de procesos

2011-03-23T07:47:14Z

JCGarrido: Reescritura de una frase(en esencia dice lo mismo)

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

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

Además de ofrecer una alta ''tasa de transferencia'' (throughput) y una baja latencia (latency), es deseable que un planificador implemente las siguientes características:

*'''Repetitividad''' : con cargas de trabajo similares(cantidad de procesos a atender) , el procesador debe tener comportamientos similares.
*'''Predecibilidad''' : hace referencia al tiempo de terminación de un proceso para cierta carga de trabajo, que debe ser similar para cargas de trabajo parecidas.
*'''Eficiencia''' : debe tomar decisiones rápidas para aumentar el rendimiento.
*'''Reducción del número de conmutaciones''' : de nuevo, para aumentar el rendimiento y reducir la penalización asociada.
*'''Atención de prioridades''': uso de criterios de selección basados en prioridades
*'''Degradación uniforme del rendimiento''': a mayores cargas de trabajo el rendimiento debe degradarse uniformemente.
*'''Capacidad de respuesta instantánea''': los tiempos de espera para atender a un proceso deben ser aceptables de cara al usuario, generalmente <100ms para seres humanos.

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

2011-03-22T23:31:50Z

JCGarrido: Retocadas las observaciones

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

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

2011-03-22T23:30:02Z

JCGarrido: Observaciones

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

Ejercicios otros aspectos de la planificación

2011-03-22T23:14:20Z

JCGarrido: He escrito un poco mejor la frase "suponiendo..."

== Ejercicio 1 ==

Dada la siguiente configuración de procesos:

H0 t
PA 0 5
PB 1 3
PC 2 1
PD 3 6
PE 4 2

Suponiendo un sistema operativo multiprocesador sobre dos procesadores, realice la traza de la ejecución de dichos procesos para los siguientes criterios de planificación:

* FIFO (no apropiativo)
* SJF (apropiativo y no apropiativo)

[[sol-ejer1-otros-aspectos|Ver solución ejercicio 1]]

Planificación de procesos de tiempo real

2011-03-22T23:01:27Z

JCGarrido: tildes

== ¿Qué es un proceso de tiempo real? ==

Proceso de tiempo real se denomina a aquella actividad que debe ser realizada en un plazo de tiempo, si la actividad no es realizada en dicho plazo de tiempo carece de sentido realizarla. Ej: Actividades industriales, videoconferencias, etc

== Clasificación ==

Podemos clasificar los procesos de tiempo real de diferentes maneras:

Segun el plazo de tiempo:
*'''Rígidos(''hard-realtime'')''' : se debe realizar en un plazo de tiempo determinado. Si no lo hace, deja de tener sentido. Si el plazo de tiempo para realizarla es superado el proceso se aborta. Ejemplo: Industriales ( sensores, activadores,...).

*'''Flexibles(''soft-realtime'')''' : es deseable que se cumpla el plazo de tiempo. Ej: Videoconferencia.(Mientras más rapido vaya mejor sera la comunicacion , pero si no , nos adaptamos a ella)

*'''Opcionales''' : conviene hacerla en el plazo de tiempo, pero si no es posible se puede posponer. Ej: actualización de una aplicacion/programa instalada en el ordenador.

Según la periodicidad:

*'''Aperiódicas''' : se deben a sucesos externos que deben ser atendidos. El sistema operativo no sabe, a priori, cuándo van a llegar ni el tiempo que va a durar. Ej: Notificaciones de errores, Sensores de emergencia en un coche, Ventiladores para refrigeración.

*'''Periódicas''' : se realizan cada cierto tiempo (actividad repetitiva).A diferencia del anterior el sistema operativo conoce a priori cuándo van a llegar y su tiempo de duración Ej: leer una temperatura de un sensor.

== Métodos de planificación ==

Los métodos de planificación a utilizar en SSOO de tiempo real son:

*'''Planificación apropiativa con prioridad estática''': Cada proceso tiene asociado un índice de prioridad y el procesador elige aquel proceso de la lista de preparados con mayor prioridad.

*'''Planificación de tablas estáticas''': se conocen las actividades a realizar y se elabora un plan fijo de ejecución.

*'''Planificación dinámica''': Es muy parecida a la de tablas estáticas , pero también admite actividades aperiódicas. Cuando se presenta una actividad aperiódica , el planificador intenta construir un nuevo plan de ejecución que incluya a todas las actividades. Si no encuentra la solución que las englobe a todas, rechaza la actividad, que debe ser flexible u opcional. También puede retrasar alguna actividad flexible/opcional.

*'''Planificación dinámica con un mejor resultado''': Las actividades fuera de plazo se abortan. Es muy similar a la anterior, la diferencia más notable es que en la anterior existe un análisis previo aceptando actividades aperiódicas y en ésta no existe tal análisis.

El siguiente ejemplo emplea planificación apropiativa por prioridades estática con actividades periódicas y aperiódicas:

____|__PA__|_PB__|_PC__|_PD___|
Datos del _H0_|__0___|_1___|_2___|_3*n__|
problema _t__|__2___|_4___|_2___|_1____|
plazo|__3___|_5___|_7___|_3*n+2|
prioridad|__-20_|_0___|_10__|_15___|
(-20 a 19)
UNIX
< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
* = el proceso se aborta

| | | | | | | | | | | | | | | | | | | | |
PA <___|___> | | | | | | | | | | | | | | | | | |
PB | < |___|___|___* | | | | | | | | | | | | | | |
PC | | < | | |___|___> | | | | | | | | | | | | |
PD | | | < | * < |___> <___> | <___> | <___> | | | |
Planificador X X X X | X X X | 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_|PD1ª_|PD2ª_|_PD_|
Cálculos __t__|_2__|_3__|_2__|_1__|_1__|_1__|
de tiempos __T__|_2__|_*__|_4__|_*__|_2__|_1__|
_T/t_|_1__|_*__|_2__|_*__|_2__|_1__|
|
|_> Indice de penalización

Planificación de procesos de tiempo real

2011-03-22T22:56:21Z

JCGarrido: tildes

== ¿Qué es un proceso de tiempo real? ==

Proceso de tiempo real se denomina a aquella actividad que debe ser realizada en un plazo de tiempo, si la actividad no es realizada en dicho plazo de tiempo carece de sentido realizarla. Ej: Actividades industriales, videoconferencias, etc

== Clasificación ==

Podemos clasificar los procesos de tiempo real de diferentes maneras:

Segun el plazo de tiempo:
*'''Rígidos(''hard-realtime'')''' : se debe realizar en un plazo de tiempo determinado. Si no lo hace, deja de tener sentido. Si el plazo de tiempo para realizarla es superado el proceso se aborta. Ejemplo: Industriales ( sensores, activadores,...).

*'''Flexibles(''soft-realtime'')''' : es deseable que se cumpla el plazo de tiempo. Ej: Videoconferencia.(Mientras más rapido vaya mejor sera la comunicacion , pero si no , nos adaptamos a ella)

*'''Opcionales''' : conviene hacerla en el plazo de tiempo, pero si no es posible se puede posponer. Ej: actualización de una aplicacion/programa instalada en el ordenador.

Según la periodicidad:

*'''Aperiódicas''' : se deben a sucesos externos que deben ser atendidos. El sistema operativo no sabe, a priori, cuándo van a llegar ni el tiempo que va a durar. Ej: Notificaciones de errores, Sensores de emergencia en un coche, Ventiladores para refrigeración.

*'''Periódicas''' : se realizan cada cierto tiempo (actividad repetitiva).A diferencia del anterior el sistema operativo conoce a priori cuándo van a llegar y su tiempo de duración Ej: leer una temperatura de un sensor.

== Métodos de planificación ==

Los métodos de planificación a utilizar en SSOO de tiempo real son:

*'''Planificación apropiativa con prioridad estática''': Cada proceso tiene asociado un indice de prioridad y el procesador elige aquel proceso de la lista de preparados con mayor prioridad.

*'''Planificación de tablas estáticas''': se conocen las actividades a realizar y se elabora un plan fijo de ejecución.

*'''Planificación dinámica''': Es muy parecida a la de tablas estaticas , pero tambien admite actividades aperiodicas. Cuando se presenta una actividad aperiodica , el planificador intenta construir un nuevo plan de ejecucion que incluya a todas las actividades. Si no encuentra la solucion que las englobe a todas, rechaza la actividad, que debe ser flexible u opcional. Tambien puede retrasar alguna actividad flexible/opcional.

*'''Planificación dinámica con un mejor resultado''': Las actividades fuera de plazo se abortan. Es muy similar a la anterior, la diferencia mas notable es que en la anterior existe un análisis previo aceptando actividades aperiodicas y en ésta no existe tal analisis.

El siguiente ejemplo emplea planificación apropiativa por prioridades estática con actividades periódicas y aperiódicas:

____|__PA__|_PB__|_PC__|_PD___|
Datos del _H0_|__0___|_1___|_2___|_3*n__|
problema _t__|__2___|_4___|_2___|_1____|
plazo|__3___|_5___|_7___|_3*n+2|
prioridad|__-20_|_0___|_10__|_15___|
(-20 a 19)
UNIX
< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
X = se ejecuta el código del planificador
* = el proceso se aborta

| | | | | | | | | | | | | | | | | | | | |
PA <___|___> | | | | | | | | | | | | | | | | | |
PB | < |___|___|___* | | | | | | | | | | | | | | |
PC | | < | | |___|___> | | | | | | | | | | | | |
PD | | | < | * < |___> <___> | <___> | <___> | | | |
Planificador X X X X | X X X | 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_|PD1ª_|PD2ª_|_PD_|
Cálculos __t__|_2__|_3__|_2__|_1__|_1__|_1__|
de tiempos __T__|_2__|_*__|_4__|_*__|_2__|_1__|
_T/t_|_1__|_*__|_2__|_*__|_2__|_1__|
|
|_> Indice de penalización