Wiki de Sistemas Operativos - Contribuciones del usuario [es]

Hilos

2018-09-20T04:42:59Z

Ferguatol:

Un hilo es una línea de ejecución de un proceso. Todo procesos inicialmente parte con un único hilo principal, aunque el sistema operativo ofrece llamadas al sistema que permiten al programador crear y destruir hilos. Por tanto, un proceso está compuesto por uno o más hilos.

Los estados de un hilo son iguales a los de un proceso, por tanto, un hilo puede estar en estado preparado, bloqueado o activo en un cierto instante de tiempo. La conmutación entre hilos de un proceso es menos costosa que la conmutación de procesos, por tanto, el planificador tiende a conmutar entre hilos de un proceso siempre que el proceso en su conjunto no haya agotado el tiempo máximo de asignación del procesador.

Los hilos nos permiten aprovechar la existencia de más de un procesador en el sistema, puesto que podemos asignar un hilo a cada uno de los procesadores que haya disponibles. Si hay más de un procesador, dos hilos de un mismo proceso pueden estar en estado activo simultáneamente. Por tanto, la programación con hilos nos permite sacar partido de las arquitecturas de multiprocesador que predominan en la actualidad.

Cuando se crea un hilo, el programador indica qué código ejecuta. Los hilos de un mismo proceso comparten el mismo espacio de memoria, por tanto, dos hilos del mismo proceso pueden compartir estructuras de datos y variables.

Veamos un ejemplo diseñado para un solo procesador:

[[Archivo:Uso_del_procesador_hilos.svg]]

Con multiprocesamiento podemos ejecutar diferentes procesos a la vez. Si tenemos uno solo podemos desdoblarlo en hilos, usando técnicas de programación apoyadas en APIS (como POSIX threads).

Para aumentar su eficiencia, un programa en ejecución debe crear tantos hilos como el doble del número de procesadores de los que disponga el sistema. Por ejemplo: 4 hilos para un programa ejecutado con 2 procesadores.

Las principales ventajas del uso de hilos son:

*'''Menor penalización''' en cuanto a conmutación. Ya que sólo se produce un salto en la ejecución de código del proceso, no interviene el planificador de procesos.

*Dos hilos de un mismo proceso '''comparten memoria''' aprovechando mejor los recursos y eliminando los mecanismos de comunicación necesarios para soluciones implementadas en varios procesos.

*Con un solo procesador es posible que una línea de proceso haga uso de una llamada al sistema que haga que el proceso pase a estado bloqueado. En este caso se puede llamar a otro hilo del mismo proceso en lugar de conmutar a otro proceso externo, ahorrando así tiempo de conmutación asociado a la ejecución del planificador de procesos.

= Ejemplo =

El siguiente es un código en C de ejemplo en el que se muestra la creación de dos hilos. Se hace uso de la llamada al sistema ''sleep'' que hace que el proceso pase a estado bloqueado durante N segundos. Nótese que al compartir la variable ''a'', ambos hilos modifican su valor.

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

int a = 10;

void *codigo_hilo1(void *arg)
{
sleep(10);
a = a - 2;
printf("Soy el hilo 1 y la variable a vale %d\n", a);
return NULL;
}

void *codigo_hilo2(void *arg)
{
sleep(5);
a++;
printf("Soy el hilo 2 y la variable a vale %d\n", a);
return NULL;
}

int main(void)
{
pthread_t hilo1, hilo2;

pthread_create(&hilo1, NULL, codigo_hilo1, NULL);
pthread_create(&hilo2, NULL, codigo_hilo2, NULL);

pthread_join(hilo1, NULL);
pthread_join(hilo2, NULL);
}
</source>

Este ejemplo se compila en un terminal escribiendo: '''gcc archivo.c -lpthread'''

[[Ejercicios_Procesos | Ejercicios]]

5.1.[[Planificación de procesos| La planificación de procesos]]

Modelos de Diseño de Sistemas Operativos

2018-09-19T20:53:41Z

Ferguatol: /* Sistemas operativos Monolíticos */ Errata

= 3.1. Modelos de Diseño de SSOO =

== Modos de operación del procesador ==

Para entender los diseños de sistemas operativos existentes, tenemos que hacer referencia a los modos de ejecución del procesador. El modo de ejecución del procesador determina qué conjunto de instrucciones y a qué recursos del procesador se puede acceder.

Los procesadores ofrecen, como mínimo, dos modos de funcionamiento del procesador:

* '''Modo privilegiado''', que permite la ejecución de todo el conjunto de instrucciones que ofrece el procesador. Es el modo en el que se ejecuta el núcleo de un sistema operativo.

* '''Modo no privilegiado''', que permite acceder a un subconjunto de las instrucciones que ofrece el procesador, es el modo en el que se ejecutan los procesos.

== Núcleo del sistema operativo ==

El núcleo del sistema operativo, también conocido por la terminología inglesa ''kernel'', es la parte más esencial del sistema operativo. Es la parte del código del sistema operativo que se ejecuta en modo privilegiado del procesador.

Al operar en dicho modo, un error de programación en el núcleo del sistema operativo resulta en un error fatal del cual el sistema sólo puede recuperarse mediante el reinicio del sistema. A tal error fatal también se le conoce en los sistemas operativos UNIX por la locución inglesa ''[http://es.wikipedia.org/wiki/Kernel_panic kernel panic]'' y en los sistemas operativos Windows por el nombre de ''[http://www.google.es/url?sa=t&source=web&cd=1&ved=0CCwQFjAA&url=http%3A%2F%2Fes.wikipedia.org%2Fwiki%2FPantalla_azul_de_la_muerte&ei=s02WTqvCCMjHtAaxuJyBBA&usg=AFQjCNE2tZra15VdohxjrhSogTQZOVedKg Pantallazo azul o BSOD]''.

== Tipos de Sistemas Operativos ==

Los sistemas operativos se pueden clasificar en base a la cantidad de funcionalidades propias del sistemas operativo que se implementan en su núcleo. En general distinguimos dos tipos de sistemas operativos:

* '''Monolíticos:''' gestionan los cuatro componentes fundamentales del sistema operativo en modo supervisor, esto incluye, la planificación de procesos, la administración de la memoria principal, la gestión de E/S y el administrador de ficheros.

* '''Micronúcleos:''' implementan en su núcleo únicamente la planificación de procesos, la gestión de interrupciones (la parte básica fundamental de la gestión de E/S que necesariamente se tiene que realizar en modo privilegiado) y la comunicación entre procesos. Por tanto, la administración de memoria principal, la gestión de la E/S y la gestión de ficheros se realiza en modo usuario. En este tipo de sistema operativo hay procesos especiales propios del sistema operativo que implementan dichas funcionalidades en modo usuario y se denominan ''proceso servidor''.

Además, contamos con una clasificación intermedia:

* '''Híbrido:''' a mitad de camino entre monolítico y micronúcleo, incluyen la gestión de dispositivos de E/S en modo supervisor con el fin de mejorar el rendimiento del sistema.

En número de líneas de código, el núcleo monolítico es mayor que el micronúcleo, al implementar más componentes del sistema operativo que permiten la gestión del computador en el espacio del núcleo, es decir, en modo privilegiado.

Los sistemas operativo monolíticos ofrecen mejor rendimiento que los micronúcleos, pero los micronúcleos son más fiables, pues un fallo de programación en el núcleo lleva al traste con la ejecución del sistema.



=== Sistemas operativos Monolíticos ===

Los sistemas operativos monolíticos se caracterizan por implementar en el núcleo los cuatro componentes fundamentales del sistema operativo, que son la planificación de procesos, la administración de la memoria principal, la administración de ficheros y la gestión de los dispositivos de entrada/salida.

Los sistemas operativos de propósito general son predominantemente monolíticos hoy día, algunos ejemplos son:
el sistema
* Sistemas operativos UNIX, tales como FreeBSD, NetBSD y OpenBSD.
* Sistemas operativos GNU/Linux, y por tanto, Android también.
* DOS, tales como MS-DOS y DR-DOS.

Como inconveniente, este tipo de sistemas de operativo dispone de un alto número de líneas de código ejecutándose en modo privilegiado. Por ello, un error de programación en el núcleo puede provocar un ''kernel panic''. Además, el hecho de añadir nuevas funcionalidades provocaría una nueva recompilación del núcleo llevando a reiniciar el sistema para que se apliquen los nuevos cambios. Por ejemplo, un bug en el núcleo de un sistema operativo monolítico obliga a tener que reiniciar el sistema. En un sistema operativo monolítico, el código del núcleo se incluye en un único fichero binario que se carga en memoria principal en tiempo de arranque, por tanto, si se instala una nueva imagen, es necesario reiniciar el sistema operativo para que se inicie con la nueva versión que incluye la imagen actualizada.

Como principal ventaja, los sistemas operativos monolíticos ofrecen un alto rendimiento puesto que las peticiones entre los diferentes componentes se reducen a invocaciones de funciones.

=== Sistemas operativos Micronúcleo ===

Se caracterizan por disponer de un núcleo que implementa únicamente:

* Planificación de procesos
* Mecanismo de comunicación entre procesos
* Gestión de interrupciones

Además, existen procesos servidores que se ejecutan en modo no privilegiado del procesador - que, por supuesto, se ejecutan fuera del espacio del núcleo del sistema operativo - y que implementan los siguientes componentes:

* Administración de memoria principal
* Administración de ficheros
* Gestión de dispositivos de entrada/salida.

Siguiendo este esquema, cuando un proceso cualquiera solicita un servicio a través de una llamada al sistema, el micronúcleo canaliza la petición al proceso servidor correspondiente. Dicha comunicación se realiza mediante mensajería.

La principal ventaja de los sistemas operativos micronúcleo es que, al ejecutar menos líneas de código en modo privilegiado, de manera intuitiva son más fiables. Otras ventajas son que se garantiza el aislamiento de las partes que están fuera del núcleo. Generalmente, si un proceso servidor tiene un bug en su código que hace que entre en una condición de error, se puede relanzar sin tener que reiniciar el sistema por completo.

Sin embargo, el principal problema que presentan es el rendimiento, puesto que cualquier petición requiere mensajería, que lleva consigo un coste extra debido a la construcción de los mensajes, el reparto y la interpretación. Son estos problemas relacionados con el rendimiento los que hacen que no existan sistemas operativos micronúcleo, y que generalmente únicamente tiene propósitos educativos y/o propósitos muy específicos.

Algunos ejemplos de sistemas operativos micronúcleos son:

* Symbian OS, hoy día en desuso.
* Minix, en sus versiones 2 y 3.

=== Sistemas operativos Híbridos ===

«Híbrido» implica que el núcleo en cuestión usa conceptos de arquitectura tanto del diseño monolítico como del micronúcleo, específicamente el paso de mensajes y la ejecución de ciertos componentes del sistema operativo en espacio de usuario.

Algunos ejemplos de núcleos híbridos:

* Microsoft Windows NT, usado en todos los sistemas que usan el código base de Windows NT.
* XNU (usado en Mac OS X), es un micronúcleo modificado, debido a la inclusión de código del núcleo de FreeBSD en el núcleo basado en Mach.
* DragonFlyBSD, es el primer sistema BSD que adopta una arquitectura de núcleo híbrido sin basarse en Mach.
* ReactOS.

No hay que confundir el concepto «núcleo híbrido» con el soporte de módulos cargables después del arranque que está disponible en núcleos monolíticos.

=== Unikernel ===

Las aplicaciones se ejecutan en modo supervisor, dentro del espacio del núcleo del Sistema Operativo. Por tanto, la totalidad del código se ejecuta en modo privilegiado. Los procesos no invocan llamadas al sistema pues tienen acceso directo a los recursos del computador. El argumento para este diseño es el rendimiento a cambio de sacrificar la fiabilidad. Sólo es aplicable a sistemas de propósito muy específico.

== Otro material a consultar ==

El estudiante puede encontrar el siguiente material de interés para complementar sus conocimientos:

* Debate entre Linus Torvalds, creador del núcleo Linux, que sigue el paradigma monolítico y Andrew S. Tanembaum, creador de Minux, que sigue el modelo micronúcleo: http://oreilly.com/catalog/opensources/book/appa.html (en inglés).

3.2.[[Virtualización | Virtualización]]

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

2017-06-29T17:56:19Z

Ferguatol: /* SFJ no apropriativo con multiprocesamiento */ Errata corregida

= 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

[[Archivo:GRAFICA.svg]]

_____|_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 (Ip)

= SFJ no apropiativo 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

Criterios de reemplazo

2012-01-31T17:35:00Z

Ferguatol: Deshecha la edición 2448 de Jesgonbel (disc.)

La evaluación se hace en base a la '''tasa de fallos de página''', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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

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

== Criterio de página óptima ==

Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

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

*[[sol_1|Solución]]

== Criterio de página pésima ==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

*[[sol_2|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Se trata también de un criterio teórico, serviría para aproximar la cota media de la ''tasa de fallos de página''. Consiste en seleccionar una página al azar.

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

*[[sol_3|Solución]]

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

Ofrece dos bits para cada página:
* Bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* Bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, siempre se pone a 1 el bit R, y solo se toca M cuando se accede a escritura.

Para seleccionar la página víctima iteramos sobre los marcos cargados en memoria (comenzando por el primero de ellos) buscando el que cumpla lo siguiente, en este orden:

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

Periódicamente se pone a cero el bit R.

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

Se trata de la combinación de los criterios FIFO y NRU, pero sin emplear el bit M de NRU. Cuando hay que seleccionar una página víctima, se recorre la lista de páginas por orden de carga en memoria hasta encontrar alguna que tenga el bit R a 0. Durante la iteración, si se encuentra una cuyo bit R valga 1, se pone a 0, se retira de la lista y se añade al final (para darle una segunda oportunidad). Cuando se añade una nueva página, se añade al final de la cola con el bit R a 1.

*[[sol_7|Solución]]

;Criterio del reloj: Es una variante en la manera de implementar la 2ª oportunidad. Se emplea una lista circular. En lugar de eliminar y añadir elementos al final de la FIFO, mantenemos un puntero a la página siguiente a la última página víctima seleccionada.

*[[sol_reloj|Solución]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

Es justamente el criterio contrario al MRU. En LRU elegimos la página que más tiempo lleve sin ser accedida. Se implementa mediante una FIFO que mantiene el '''orden de acceso''' a las páginas. Es decir, cada vez que se accede a una página, en caso de estar ya en la FIFO, se retira de la cola y se añade al final.

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se selecciona a la página que haya sido accedida con menor frecuencia. Se implementa mediante un contador. Básicamente, por cada acceso se incrementa el contador de uso de la página. La página víctima será aquella con menor contador. Cuando una página es expulsada a disco su contador pasa a ser cero.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

Se tiene un bit R y un contador por cada marco. Cuando una página es cargada a un marco, se carga con su bit R a 1 y su contador inicial a 0. Cuando pasa un período determinado de tiempo (viene dado en el enunciado) se itera sobre toda la lista de páginas, y pueden ocurrir dos cosas:
* '''Si su bit R está a 1''': Se ponen su bit R a cero y su contador se incrementa.
* '''Si su bit R está a 0''': No se hace nada.

Cuando hay que seleccionar una página víctima, se escoge aquella cuyo contador sea más pequeño. En caso de empate, habrá que establecer un criterio de desempate.

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

== Sustitución por envejecimiento ==

Se emplea un registro R de N bits. Por cada acceso se pone a 1 el bit más significativo. Periódicamente se desplaza hacia la derecha el registro R. La página víctima será la que tenga el menor valor en el registro R (en caso de empate se emplea otro criterio). La información que contienen los bits menos significativos se pierden al realizar desplazamientos. Este criterio permite mantener un historial de acceso a las páginas, para seleccionar como víctima aquella que lleve más tiempo sin ser accedida.

*[[sol_10|Solución]]

= Implementaciones =

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

Página con listado de personas que han contribuido

2012-01-26T21:39:53Z

Ferguatol:

A continuación, la lista de usuarios/as de la Universidad de Sevilla que han contribuido a la wiki. Si ponéis tu usuario/a estás solicitando al profesor que evalúe tus contribuciones a la wiki para la subida de notas de hasta 2 puntos posible:

* luigarhor
* rafperper
* sergaralo
* josalgrod1
* felgaroje
* luimunlei
* [https://1984.lsi.us.es/wiki-ssoo/index.php/Usuario:Lorruimor Lorruimor]
* albsolnog
* framorexp
* javgarang
* FerGuaTol

Usuario:Jesdiamar

2012-01-22T21:27:19Z

Ferguatol: Página creada con 'Jesús Díaz Martín'

Jesús Díaz Martín

Solución de los ejercicios de administración de ficheros

2012-01-22T17:04:29Z

Ferguatol: Reescrita la solución del ejercicio 2 de forma más clara

== Ejercicio 1 ==

A) '''Incoherencia nº1:''' Fichero2.txt está asociado a un bloque corrupto, el número 4.

'''Incoherencia nº2:''' Cuando se accede al bloque 7 (correspondiente al archivo Imagen2.jpg), el siguiente en ser accedido es el número 4, que además de estar asociado a otro archivo, está corrupto.

B)
Entrada al directorio raíz E: 1 acceso al bloque 2
Entrada a Imagen.jpg: 1 acceso al bloque 3
Siguiente bloque de Imagen.jpg: 1 acceso al bloque 5
Siguiente bloque de Imagen.jpg: 1 acceso al bloque 6 y final de fichero.
Total: 4 accesos

Mejorada explicación del primer apartado y corregida la del segundo. --[[Usuario:Ferguatol|fernandoenzo]] 16:27 22 ene 2012 (UTC)

== Ejercicio 2 ==

Bloque del i-nodo: 1 acceso
Camino hacia el bloque del doble indirecto: 2 accesos
Acceso al bloque del doble indirecto: 1 acceso
Total: 4 accesos

Solución de los ejercicios de administración de ficheros

2012-01-22T16:30:34Z

Ferguatol: /* Ejercicio 1 */

== Ejercicio 1 ==

A) '''Incoherencia nº1:''' Fichero2.txt está asociado a un bloque corrupto, el número 4.

'''Incoherencia nº2:''' Cuando se accede al bloque 7 (correspondiente al archivo Imagen2.jpg), el siguiente en ser accedido es el número 4, que además de estar asociado a otro archivo, está corrupto.

B)
Entrada al directorio raíz E: 1 acceso al bloque 2
Entrada a Imagen.jpg: 1 acceso al bloque 3
Siguiente bloque de Imagen.jpg: 1 acceso al bloque 5
Siguiente bloque de Imagen.jpg: 1 acceso al bloque 6 y final de fichero.
Total: 4 accesos

Mejorada explicación del primer apartado y corregida la del segundo. --[[Usuario:Ferguatol|fernandoenzo]] 16:27 22 ene 2012 (UTC)

== Ejercicio 2 ==

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

Total: 4 accesos

Solución de los ejercicios de administración de ficheros

2012-01-22T16:27:25Z

Ferguatol: /* Ejercicio 1 */ Reescrita y corregida la solución completamente

== Ejercicio 1 ==

A) '''Incoherencia nº1:''' Fichero2.txt está asociado a un bloque corrupto, el número 4.

'''Incoherencia nº2:''' Cuando se accede al bloque 7 (correspondiente al archivo Imagen2.jpg), el siguiente en ser accedido es el número 4, que además de estar asociado a otro archivo, está corrupto.

B.
Entrada al directorio raíz E: 1 acceso al bloque 2
Entrada a Imagen.jpg: 1 acceso al bloque 3
Siguiente bloque de Imagen.jpg: 1 acceso al bloque 5
Siguiente bloque de Imagen.jpg: 1 acceso al bloque 6 y final de fichero.
Total: 4 accesos

Mejorada explicación del primer apartado y corregida la del segundo. --[[Usuario:Ferguatol|fernandoenzo]] 16:27 22 ene 2012 (UTC)

== Ejercicio 2 ==

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

Total: 4 accesos

Usuario:Antdomflo

2012-01-22T15:18:20Z

Ferguatol: Página creada con 'Antonio Domínguez Flores'

Antonio Domínguez Flores

Introducción en la administración de archivos

2012-01-22T14:42:09Z

Ferguatol: /* Propietario, grupo y permisos */

= Administrador de ficheros =

Se trata de la parte del sistema operativo que se encarga de la organización de los ficheros en el sistema operativo.

= Bloque =

La memoria disponible en un dispositivo de almacenamiento masivo se divide en porciones de igual tamaño denominados '''bloques'''. Dichos bloques se asignan completamente y en exclusividad a un fichero de manera que un fichero está compuesto por un conjunto de bloques.

El tamaño de bloque es una parámetro que se establece en el tiempo de formateo. Por lo general, se emplean bloques de 4 KB y 8 KB dependiendo del tamaño de palabra del procesador. No obstante, es un parámetro configurable. En el caso de un sistema que tenga que alojar gran cantidad de fichero muy pequeños, podría reducirse el tamaño de bloque para hacer un mejor aprovechamiento del espacio de almacenamiento en disco.

*Aspectos relevantes en la elección del tamaño de los bloques:

Podemos destacar los siguientes 4 aspectos:

'''Desperdicio interno:'''
Cuanto mayor sean los bloques mayor desperdicio interno se producirá en el último bloque del fichero.

'''Tiempos de espera:'''
Cuanto mayor sea el bloque menos bloques formarán los ficheros con lo que se reduce el numero de accesos al soporte y, en consecuencia, los tiempos de espera.

'''Espacio intermedio:'''
Cuanto mayor sean los bloques mayor será el espacio necesario para mantenerlos cargados en memoria mientras se opera con ellos.

'''Aprovechamiento de las operaciones de lectura y escritura:'''
Si el proceso no realiza accesos a memoria secuenciales, sino que son aleatorios, es muy probable que solo necesite unos pocos octetos de cada bloque del fichero. Sin embargo en cada lectura y escritura los bloques se leen o escriben completamente, lo que significa un desaprovechamiento de las operaciones de lectura y escritura.

= Fichero =

Un fichero es un contenedor de información que consta como mínimo de un nombre, además de una serie de atributos (llamados [http://www.alegsa.com.ar/Dic/metadato.php metadatos]) como la fecha de creación, última actualización, propietario, grupo entre otros; y un número de bloques asignados.

= Directorio =

Un directorio o carpeta es una contenedor de ficheros. Por lo general, disponen a su vez de dos pseudodirectorios denominados "." y ".." que sirven como referencia al propio directorio y al directorio padre. De esta manera, los directorios se organizan en una estructura arbórea con una cierta raíz.

= Organización de los directorios y ficheros =

La organización de los directorios y ficheros en los sistemas operativos modernos emplea una estructura arbórea en la que existe un directorio raíz del que penden todos los demás directorios y ficheros.

raíz
/\
/ \
d1 d2
/ \ \
f1 f2 d3
/\
/ \
f3 f4

En el caso de sistemas operativos tipo Unix, la raíz se identifica con el directorio /. Para sistemas operativos de tipo-Microsoft, existe un directorio raíz por unidad. Cada unidad se trata de un sistema de fichero independiente que se identifica mediante una letra seguida de dos puntos, por ejemplo '''C:\''' .

== Propietario, grupo y permisos ==

Todo fichero o directorio en un sistema operativo moderno dispone de al menos un propietario que define las acciones que se pueden realizar sobre los ficheros. Por lo general son las siguientes:

* Lectura: Es posible leer el contenido del fichero.
* Modificación: Es posible modificar el contenido del fichero.
* Ejecución: Es posible ejecutar el fichero.

En general, este esquema se aplica al propietario, al grupo y al resto del mundo, de manera que el propietario de cualquier fichero o directorio establece los permisos. Por ejemplo, un fichero con un documento ofimático puede ser leído y modificado por el propietario y por el grupo, pero no por el resto del mundo.

Ejemplo:

propietario grupo resto del mundo
rwx rwx rwx

fichero.odt: rw------- (fichero openoffice con sólo lectura y escritura para el propietario)
sudoku: rwxr-xr-x (fichero ejecutable con permisos de lectura, modificación y ejecución para el propietario)

== Tabla de entrada de ficheros ==

Todo directorio dispone de una tabla de entrada de ficheros. Por cada entrada existe al menos una referencia al primer bloque que forma parte de dicho fichero, así como otros atributos como el propietario del fichero, la fecha de último acceso, modificación, etc.

[[Archivo:Directorios2.png]]

Cada tabla de entrada de ficheros ocupa como mínimo un bloque. Por cada entrada se almacena la siguiente información:

* Nombre del fichero o directorio (tamaño variable)
* Fecha de creación y último acceso (entero sin signo de 64-bits)
* Propietario (entero sin signo de 32-bits para el identificador de usuario)
* Grupo (entero sin signo de 32-bits para el identificador de grupo)
* Permisos (entero sin signo de 16 bits que codifican los permisos).

De esta manera, cada entrada ocupa un número de bytes. Suponiendo que toda entrada requiera 64 bytes, si se emplea un tamaño de bloque de 4 KB, con un bloque se podrían mantener hasta 64 entradas. En caso de que un directorio tuviera más entradas, serían necesarios más bloques para la tabla de entrada de ficheros.

= Sistema de ficheros =

Un sistema de fichero se trata de la estructura lógica (mediante un tipo abstracto de datos como una tabla, una lista o un árbol) y el conjunto de mecanismos que se emplean para gestionar los bloques asignados a ficheros y los bloques libres.

Introducción en la administración de archivos

2012-01-22T14:38:29Z

Ferguatol: /* Organización de los directorios y ficheros */

= Administrador de ficheros =

Se trata de la parte del sistema operativo que se encarga de la organización de los ficheros en el sistema operativo.

= Bloque =

La memoria disponible en un dispositivo de almacenamiento masivo se divide en porciones de igual tamaño denominados '''bloques'''. Dichos bloques se asignan completamente y en exclusividad a un fichero de manera que un fichero está compuesto por un conjunto de bloques.

El tamaño de bloque es una parámetro que se establece en el tiempo de formateo. Por lo general, se emplean bloques de 4 KB y 8 KB dependiendo del tamaño de palabra del procesador. No obstante, es un parámetro configurable. En el caso de un sistema que tenga que alojar gran cantidad de fichero muy pequeños, podría reducirse el tamaño de bloque para hacer un mejor aprovechamiento del espacio de almacenamiento en disco.

*Aspectos relevantes en la elección del tamaño de los bloques:

Podemos destacar los siguientes 4 aspectos:

'''Desperdicio interno:'''
Cuanto mayor sean los bloques mayor desperdicio interno se producirá en el último bloque del fichero.

'''Tiempos de espera:'''
Cuanto mayor sea el bloque menos bloques formarán los ficheros con lo que se reduce el numero de accesos al soporte y, en consecuencia, los tiempos de espera.

'''Espacio intermedio:'''
Cuanto mayor sean los bloques mayor será el espacio necesario para mantenerlos cargados en memoria mientras se opera con ellos.

'''Aprovechamiento de las operaciones de lectura y escritura:'''
Si el proceso no realiza accesos a memoria secuenciales, sino que son aleatorios, es muy probable que solo necesite unos pocos octetos de cada bloque del fichero. Sin embargo en cada lectura y escritura los bloques se leen o escriben completamente, lo que significa un desaprovechamiento de las operaciones de lectura y escritura.

= Fichero =

Un fichero es un contenedor de información que consta como mínimo de un nombre, además de una serie de atributos (llamados [http://www.alegsa.com.ar/Dic/metadato.php metadatos]) como la fecha de creación, última actualización, propietario, grupo entre otros; y un número de bloques asignados.

= Directorio =

Un directorio o carpeta es una contenedor de ficheros. Por lo general, disponen a su vez de dos pseudodirectorios denominados "." y ".." que sirven como referencia al propio directorio y al directorio padre. De esta manera, los directorios se organizan en una estructura arbórea con una cierta raíz.

= Organización de los directorios y ficheros =

La organización de los directorios y ficheros en los sistemas operativos modernos emplea una estructura arbórea en la que existe un directorio raíz del que penden todos los demás directorios y ficheros.

raíz
/\
/ \
d1 d2
/ \ \
f1 f2 d3
/\
/ \
f3 f4

En el caso de sistemas operativos tipo Unix, la raíz se identifica con el directorio /. Para sistemas operativos de tipo-Microsoft, existe un directorio raíz por unidad. Cada unidad se trata de un sistema de fichero independiente que se identifica mediante una letra seguida de dos puntos, por ejemplo '''C:\''' .

== Propietario, grupo y permisos ==

Todo fichero o directorio en un sistema operativo moderno dispone de al menos un propietario que define las acciones que se pueden realizar sobre el ficheros. Por lo general son las siguientes:

* Lectura: Es posible leer el contenido del fichero.
* Modificación: Es posible modificar el contenido del fichero.
* Ejecución: Es posible ejecutar el fichero.

En general, este esquema se aplica al propietario, al grupo y al resto del mundo, de manera que el propietario de cualquier fichero o directorio establece los permisos. Por ejemplo, un fichero con un documento ofimático puede ser leído y modificado por el propietario y por el grupo, pero no por el resto del mundo.

Ejemplo:

propietario grupo resto del mundo
rwx rwx rwx

fichero.odt: rw------- (fichero openoffice con sólo lectura y escritura para el propietario)
sudoku: rwxr-xr-x (fichero ejecutable con permisos de lectura, modificación y ejecución para el propietario)

== Tabla de entrada de ficheros ==

Todo directorio dispone de una tabla de entrada de ficheros. Por cada entrada existe al menos una referencia al primer bloque que forma parte de dicho fichero, así como otros atributos como el propietario del fichero, la fecha de último acceso, modificación, etc.

[[Archivo:Directorios2.png]]

Cada tabla de entrada de ficheros ocupa como mínimo un bloque. Por cada entrada se almacena la siguiente información:

* Nombre del fichero o directorio (tamaño variable)
* Fecha de creación y último acceso (entero sin signo de 64-bits)
* Propietario (entero sin signo de 32-bits para el identificador de usuario)
* Grupo (entero sin signo de 32-bits para el identificador de grupo)
* Permisos (entero sin signo de 16 bits que codifican los permisos).

De esta manera, cada entrada ocupa un número de bytes. Suponiendo que toda entrada requiera 64 bytes, si se emplea un tamaño de bloque de 4 KB, con un bloque se podrían mantener hasta 64 entradas. En caso de que un directorio tuviera más entradas, serían necesarios más bloques para la tabla de entrada de ficheros.

= Sistema de ficheros =

Un sistema de fichero se trata de la estructura lógica (mediante un tipo abstracto de datos como una tabla, una lista o un árbol) y el conjunto de mecanismos que se emplean para gestionar los bloques asignados a ficheros y los bloques libres.

Introducción en la administración de archivos

2012-01-22T14:24:27Z

Ferguatol: /* Bloque */

= Administrador de ficheros =

Se trata de la parte del sistema operativo que se encarga de la organización de los ficheros en el sistema operativo.

= Bloque =

La memoria disponible en un dispositivo de almacenamiento masivo se divide en porciones de igual tamaño denominados '''bloques'''. Dichos bloques se asignan completamente y en exclusividad a un fichero de manera que un fichero está compuesto por un conjunto de bloques.

El tamaño de bloque es una parámetro que se establece en el tiempo de formateo. Por lo general, se emplean bloques de 4 KB y 8 KB dependiendo del tamaño de palabra del procesador. No obstante, es un parámetro configurable. En el caso de un sistema que tenga que alojar gran cantidad de fichero muy pequeños, podría reducirse el tamaño de bloque para hacer un mejor aprovechamiento del espacio de almacenamiento en disco.

*Aspectos relevantes en la elección del tamaño de los bloques:

Podemos destacar los siguientes 4 aspectos:

'''Desperdicio interno:'''
Cuanto mayor sean los bloques mayor desperdicio interno se producirá en el último bloque del fichero.

'''Tiempos de espera:'''
Cuanto mayor sea el bloque menos bloques formarán los ficheros con lo que se reduce el numero de accesos al soporte y, en consecuencia, los tiempos de espera.

'''Espacio intermedio:'''
Cuanto mayor sean los bloques mayor será el espacio necesario para mantenerlos cargados en memoria mientras se opera con ellos.

'''Aprovechamiento de las operaciones de lectura y escritura:'''
Si el proceso no realiza accesos a memoria secuenciales, sino que son aleatorios, es muy probable que solo necesite unos pocos octetos de cada bloque del fichero. Sin embargo en cada lectura y escritura los bloques se leen o escriben completamente, lo que significa un desaprovechamiento de las operaciones de lectura y escritura.

= Fichero =

Un fichero es un contenedor de información que consta como mínimo de un nombre, además de una serie de atributos (llamados [http://www.alegsa.com.ar/Dic/metadato.php metadatos]) como la fecha de creación, última actualización, propietario, grupo entre otros; y un número de bloques asignados.

= Directorio =

Un directorio o carpeta es una contenedor de ficheros. Por lo general, disponen a su vez de dos pseudodirectorios denominados "." y ".." que sirven como referencia al propio directorio y al directorio padre. De esta manera, los directorios se organizan en una estructura arbórea con una cierta raíz.

= Organización de los directorios y ficheros =

La organización de los directorios y ficheros en los sistemas operativos modernos emplea una estructura arbórea en la que existe un directorio raíz del que penden todos los demás directorios y ficheros.

raíz
/\
/ \
d1 d2
/ \ \
f1 f2 d3
/\
/ \
f3 f4

En el caso de sistemas operativos tipo Unix, la raíz se identifica con el directorio /. Para sistemas operativos de tipo-Microsoft, existe un directorio raíz por unidad. Cada unidad se trata de un sistema de fichero independiente que se identifica mediante una letra seguida de dos puntos, por ejemplo '''c:'''.

== Propietario, grupo y permisos ==

Todo fichero o directorio en un sistema operativo moderno dispone de al menos un propietario que define las acciones que se pueden realizar sobre el ficheros. Por lo general son las siguientes:

* Lectura: Es posible leer el contenido del fichero.
* Modificación: Es posible modificar el contenido del fichero.
* Ejecución: Es posible ejecutar el fichero.

En general, este esquema se aplica al propietario, al grupo y al resto del mundo, de manera que el propietario de cualquier fichero o directorio establece los permisos. Por ejemplo, un fichero con un documento ofimático puede ser leído y modificado por el propietario y por el grupo, pero no por el resto del mundo.

Ejemplo:

propietario grupo resto del mundo
rwx rwx rwx

fichero.odt: rw------- (fichero openoffice con sólo lectura y escritura para el propietario)
sudoku: rwxr-xr-x (fichero ejecutable con permisos de lectura, modificación y ejecución para el propietario)

== Tabla de entrada de ficheros ==

Todo directorio dispone de una tabla de entrada de ficheros. Por cada entrada existe al menos una referencia al primer bloque que forma parte de dicho fichero, así como otros atributos como el propietario del fichero, la fecha de último acceso, modificación, etc.

[[Archivo:Directorios2.png]]

Cada tabla de entrada de ficheros ocupa como mínimo un bloque. Por cada entrada se almacena la siguiente información:

* Nombre del fichero o directorio (tamaño variable)
* Fecha de creación y último acceso (entero sin signo de 64-bits)
* Propietario (entero sin signo de 32-bits para el identificador de usuario)
* Grupo (entero sin signo de 32-bits para el identificador de grupo)
* Permisos (entero sin signo de 16 bits que codifican los permisos).

De esta manera, cada entrada ocupa un número de bytes. Suponiendo que toda entrada requiera 64 bytes, si se emplea un tamaño de bloque de 4 KB, con un bloque se podrían mantener hasta 64 entradas. En caso de que un directorio tuviera más entradas, serían necesarios más bloques para la tabla de entrada de ficheros.

= Sistema de ficheros =

Un sistema de fichero se trata de la estructura lógica (mediante un tipo abstracto de datos como una tabla, una lista o un árbol) y el conjunto de mecanismos que se emplean para gestionar los bloques asignados a ficheros y los bloques libres.

Introducción en la administración de archivos

2012-01-22T14:24:18Z

Ferguatol: /* Bloque */

= Administrador de ficheros =

Se trata de la parte del sistema operativo que se encarga de la organización de los ficheros en el sistema operativo.

= Bloque =

La memoria disponible en un dispositivo de almacenamiento masivo se divide en porciones de igual tamaño denominados '''bloques'''. Dichos bloques se asignan completamente y en exclusividad a un fichero de manera que un fichero está compuesto por un conjunto de bloques.

El tamaño de bloque es una parámetro que se establece en el tiempo de formateo Por lo general, se emplean bloques de 4 KB y 8 KB dependiendo del tamaño de palabra del procesador. No obstante, es un parámetro configurable. En el caso de un sistema que tenga que alojar gran cantidad de fichero muy pequeños, podría reducirse el tamaño de bloque para hacer un mejor aprovechamiento del espacio de almacenamiento en disco.

*Aspectos relevantes en la elección del tamaño de los bloques:

Podemos destacar los siguientes 4 aspectos:

'''Desperdicio interno:'''
Cuanto mayor sean los bloques mayor desperdicio interno se producirá en el último bloque del fichero.

'''Tiempos de espera:'''
Cuanto mayor sea el bloque menos bloques formarán los ficheros con lo que se reduce el numero de accesos al soporte y, en consecuencia, los tiempos de espera.

'''Espacio intermedio:'''
Cuanto mayor sean los bloques mayor será el espacio necesario para mantenerlos cargados en memoria mientras se opera con ellos.

'''Aprovechamiento de las operaciones de lectura y escritura:'''
Si el proceso no realiza accesos a memoria secuenciales, sino que son aleatorios, es muy probable que solo necesite unos pocos octetos de cada bloque del fichero. Sin embargo en cada lectura y escritura los bloques se leen o escriben completamente, lo que significa un desaprovechamiento de las operaciones de lectura y escritura.

= Fichero =

Un fichero es un contenedor de información que consta como mínimo de un nombre, además de una serie de atributos (llamados [http://www.alegsa.com.ar/Dic/metadato.php metadatos]) como la fecha de creación, última actualización, propietario, grupo entre otros; y un número de bloques asignados.

= Directorio =

Un directorio o carpeta es una contenedor de ficheros. Por lo general, disponen a su vez de dos pseudodirectorios denominados "." y ".." que sirven como referencia al propio directorio y al directorio padre. De esta manera, los directorios se organizan en una estructura arbórea con una cierta raíz.

= Organización de los directorios y ficheros =

La organización de los directorios y ficheros en los sistemas operativos modernos emplea una estructura arbórea en la que existe un directorio raíz del que penden todos los demás directorios y ficheros.

raíz
/\
/ \
d1 d2
/ \ \
f1 f2 d3
/\
/ \
f3 f4

En el caso de sistemas operativos tipo Unix, la raíz se identifica con el directorio /. Para sistemas operativos de tipo-Microsoft, existe un directorio raíz por unidad. Cada unidad se trata de un sistema de fichero independiente que se identifica mediante una letra seguida de dos puntos, por ejemplo '''c:'''.

== Propietario, grupo y permisos ==

Todo fichero o directorio en un sistema operativo moderno dispone de al menos un propietario que define las acciones que se pueden realizar sobre el ficheros. Por lo general son las siguientes:

* Lectura: Es posible leer el contenido del fichero.
* Modificación: Es posible modificar el contenido del fichero.
* Ejecución: Es posible ejecutar el fichero.

En general, este esquema se aplica al propietario, al grupo y al resto del mundo, de manera que el propietario de cualquier fichero o directorio establece los permisos. Por ejemplo, un fichero con un documento ofimático puede ser leído y modificado por el propietario y por el grupo, pero no por el resto del mundo.

Ejemplo:

propietario grupo resto del mundo
rwx rwx rwx

fichero.odt: rw------- (fichero openoffice con sólo lectura y escritura para el propietario)
sudoku: rwxr-xr-x (fichero ejecutable con permisos de lectura, modificación y ejecución para el propietario)

== Tabla de entrada de ficheros ==

Todo directorio dispone de una tabla de entrada de ficheros. Por cada entrada existe al menos una referencia al primer bloque que forma parte de dicho fichero, así como otros atributos como el propietario del fichero, la fecha de último acceso, modificación, etc.

[[Archivo:Directorios2.png]]

Cada tabla de entrada de ficheros ocupa como mínimo un bloque. Por cada entrada se almacena la siguiente información:

* Nombre del fichero o directorio (tamaño variable)
* Fecha de creación y último acceso (entero sin signo de 64-bits)
* Propietario (entero sin signo de 32-bits para el identificador de usuario)
* Grupo (entero sin signo de 32-bits para el identificador de grupo)
* Permisos (entero sin signo de 16 bits que codifican los permisos).

De esta manera, cada entrada ocupa un número de bytes. Suponiendo que toda entrada requiera 64 bytes, si se emplea un tamaño de bloque de 4 KB, con un bloque se podrían mantener hasta 64 entradas. En caso de que un directorio tuviera más entradas, serían necesarios más bloques para la tabla de entrada de ficheros.

= Sistema de ficheros =

Un sistema de fichero se trata de la estructura lógica (mediante un tipo abstracto de datos como una tabla, una lista o un árbol) y el conjunto de mecanismos que se emplean para gestionar los bloques asignados a ficheros y los bloques libres.

Mejoras de tiempos de desplazamiento

2012-01-22T12:44:48Z

Ferguatol: /* SSTF (Shortest Seek Time First) */

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

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

== SSTF (Shortest Seek Time First) ==

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

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

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

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

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

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

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

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

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

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

== Ejemplos ==

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

=== Solución FCFS ===

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

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

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

Gestión de Entrada/Salida

2012-01-22T11:59:42Z

Ferguatol: /* Gestión de E/S por interrupciones */

El sistema operativo puede gobernar el dispositivo E/S a través del gestor de dispositivos de tres maneras posibles:

* Gestión de E/S por programas.
* Gestión de E/S por interrupciones.
* Gestión híbrida de E/S.

= Gestión de E/S por programas =

El gestor de dispositivo periódicamente comprueba el estado del dispositivo. Para ello comprueba mediante los registros de estado del puerto de E/S si hay datos provenientes del dispositivo que deben ser tratados.

= Gestión de E/S por interrupciones =

Una interrupción por hardware es una señal proveniente de un dispositivo de E/S para notificar al procesador de un cierto evento que debe ser tratado. Por ejemplo, un proceso hace uso de la llamada al sistema ''read'' para solicitar información que se encuentra en disco magnético. Una vez que la información está disponible, la interrupción es empleada para que se ejecute el gestor de dispositivos y obtenga los datos para dicho proceso, que ya están disponibles.

Las interrupciones son un mecanismo que ofrece la arquitectura para conectar los dispositivos de E/S con el procesador. No obstante, los datos provenientes del dispositivo de E/S se obtienen a través del bus.

El dispositivo de E/S emplea una de las líneas de interrupción que conectan al dispositivo con el procesador. Cada una de estas líneas corresponden con un cierto dispositivo o una familia de dispositivos de naturaleza similar. La signación de líneas y dispositivo es estática y sucede en tiempo de arranque, por tanto, no cambia a lo largo del tiempo. En caso de que haya datos a tratar en el dispositivo, se notifica al procesador mediante la línea de interrupción. Ante esto, el planificador debe apartar el proceso que esté en estado activo para conmutar al gestor de dispositivo, el cual realizará el tratamiento de la interrupción, obteniendo los datos del dispositivo de E/S que están pendientes de ser tratados.

Por tanto, por cada interrupción se debe [[Conmutación_de_procesos|conmutar]] al gestor de dispositivos.

Las interrupciones no son reentrantes, esto quiere decir que cuando se está realizando el tratamiento de una interrupción se desactiva temporalmente la notificación por interrupciones. Por tanto, una interrupción se ejecuta hasta fin de tratamiento, y en ningún caso es interrumpida por otra interrupción.

= Gestión de E/S híbrida =

Esta aproximación consiste en emplea una combinación de las soluciones anteriores. Básicamente, tras recibir una interrupción, se comprueba de nuevo si hay datos en el dispositivo a ser tratado. En caso afirmativo, se realiza de nuevo el tratamiento de dichos datos. De esta manera, se reduce el número de conmutaciones.

Gestión de Entrada/Salida

2012-01-22T11:02:49Z

Ferguatol: /* Gestión de E/S por interrupciones */

El sistema operativo puede gobernar el dispositivo E/S a través del gestor de dispositivos de tres maneras posibles:

* Gestión de E/S por programas.
* Gestión de E/S por interrupciones.
* Gestión híbrida de E/S.

= Gestión de E/S por programas =

El gestor de dispositivo periódicamente comprueba el estado del dispositivo. Para ello comprueba mediante los registros de estado del puerto de E/S si hay datos provenientes del dispositivo que deben ser tratados.

= Gestión de E/S por interrupciones =

Una interrupción por hardware es una señal proveniente de un dispositivo de E/S para notificar al procesador de un cierto evento que debe ser tratado. Por ejemplo, un proceso hace uso de la llamada al sistema ''read'' para solicitar información que se encuentra en disco magnético. Una vez que la información está disponible, la interrupción es empleada para que se ejecute el gestor de dispositivos y obtenga los datos para dicho proceso, que ya están disponibles.

Las interrupciones se tratan de un mecanismo que ofrece la arquitectura para conectar los dispositivos de E/S con el procesador. No obstante, los datos provenientes del dispositivo de E/S se obtienen a través del bus.

El dispositivo de E/S emplea una de las líneas de interrupción que conectan al dispositivo con el procesador. Cada una de estas líneas corresponden con un cierto dispositivo o una familia de dispositivos de naturaleza similar. La signación de líneas y dispositivo es estática y sucede en tiempo de arranque, por tanto, no cambia a lo largo del tiempo. En caso de que haya datos a tratar en el dispositivo, se notifica al procesador mediante la línea de interrupción. Ante esto, el planificador debe apartar el proceso que esté en estado activo para conmutar al gestor de dispositivo, el cual realizará el tratamiento de la interrupción, obteniendo los datos del dispositivo de E/S que están pendientes de ser tratados.

Por tanto, por cada interrupción se debe [[Conmutación_de_procesos|conmutar]] al gestor de dispositivos.

Las interrupciones no son reentrantes, esto quiere decir que cuando se está realizando el tratamiento de una interrupción se desactiva temporalmente la notificación por interrupciones. Por tanto, una interrupción se ejecuta hasta fin de tratamiento, y en ningún caso es interrumpida por otra interrupción.

= Gestión de E/S híbrida =

Esta aproximación consiste en emplea una combinación de las soluciones anteriores. Básicamente, tras recibir una interrupción, se comprueba de nuevo si hay datos en el dispositivo a ser tratado. En caso afirmativo, se realiza de nuevo el tratamiento de dichos datos. De esta manera, se reduce el número de conmutaciones.

Estructura típica de dispositivo E/S

2012-01-10T12:10:55Z

Ferguatol:

En general, la estructura típica de un dispositivo de entrada/salida está dividida en tres partes:

* '''Adaptador de Entrada/Salida del ordenador, o interfaz del bus:''' Se encarga de traducir las señales al dialecto empleado por el bus del ordenador. Algunos ejemplos de interfaces de este tipo son los buses PCI, PCMCIA, USB, PCI-express o SATA entre muchos otros.
* '''Adaptador de Entrada/Salida del dispositivo, o interfaz del dispositivo:''' Se encarga de traducir las señales al dialecto empleado por el dispositivo.
* '''Control del dispositivo, o puerto de lectura/escritura:''' Ofrece una interfaz que es empleada por el gestor de dispositivos para gobernar el dispositivo, que dispone de:
**Registros de órdenes
**Registros de estado
**Registros de lectura/escritura, o alternativamente una pequeña memoria propia.

Cuanto más elaborado sea el puerto de lectura/escritura, mayor rendimiento se puede llegar a alcanzar, puesto que el gestor de dispositivo será más sencillo (y eso implica menor número de instrucciones a ejecutar en el gestor de dispositivo).

La conexión existente entre el procesador y el dispositivo de E/S queda resumida de la siguiente manera:

Procesador <==> BUS <==> [Interfaz del bus <==> Puerto de lectura/escritura <==> Interfaz del dispositivo

= Arquitecturas de ordenadores típicas =

* Arquitectura de Von Neumann (http://es.wikipedia.org/wiki/Arquitectura_de_von_Neumann)
* Arquitectura de Harvard (http://es.wikipedia.org/wiki/Arquitectura_Harvard)

= Gestor de dispositivos =

El gestor de dispositivo, popularmente conocido por la palabra inglesa ''driver'', es la parte del sistema operativo que se encarga de gobernar un cierto dispositivo o una familia de dispositivos de naturaleza similar. El gestor de dispositivo se trata de una pieza de software que conoce los detalles de bajo nivel del dispositivo.

Estructura típica de dispositivo E/S

2012-01-10T12:10:17Z

Ferguatol:

En general, la estructura típica de un dispositivo de entrada/salida está dividida en tres partes:

* '''Adaptador de Entrada/Salida del ordenador, o interfaz del bus:''' Se encarga de traducir las señales al dialecto empleado por el bus del ordenador. Algunos ejemplos de interfaces de este tipo son los buses PCI, PCMCIA, USB, PCI-express o SATA entre muchos otros.
* '''Adaptador de Entrada/Salida del dispositivo, o interfaz del dispositivo:''' Se encarga de traducir las señales al dialecto empleado por el dispositivo.
* '''Control del dispositivo, o puerto de lectura/escritura:''' Ofrece una interfaz que es empleada por el gestor de dispositivos para gobernar el dispositivo, que dispone de:
**Registros de órdenes
**Registros de estado
**Registros de lectura/escritura, o alternativamente una pequeña memoria propia.

Cuanto más elaborado sea el puerto de lectura/escritura, mayor rendimiento se puede llegar a alcanzar, puesto que el gestor de dispositivo será más sencillo (y eso implica menor número de instrucciones a ejecutar en el gestor de dispositivo).

La conexión existente entre el procesador y el dispositivo de E/S queda resumida de la siguiente manera:

Procesador ←→ BUS ←→ [Interfaz del bus ←→ Puerto de lectura/escritura ←→ Interfaz del dispositivo

= Arquitecturas de ordenadores típicas =

* Arquitectura de Von Neumann (http://es.wikipedia.org/wiki/Arquitectura_de_von_Neumann)
* Arquitectura de Harvard (http://es.wikipedia.org/wiki/Arquitectura_Harvard)

= Gestor de dispositivos =

El gestor de dispositivo, popularmente conocido por la palabra inglesa ''driver'', es la parte del sistema operativo que se encarga de gobernar un cierto dispositivo o una familia de dispositivos de naturaleza similar. El gestor de dispositivo se trata de una pieza de software que conoce los detalles de bajo nivel del dispositivo.

SSH

2011-12-28T23:26:49Z

Ferguatol: /* Instalando y Configurando SSH */

'''SSH''' ('''S'''ecure '''SH'''ell, en español: intérprete de órdenes seguro) es el nombre de un protocolo y del programa que lo implementa, y sirve para acceder a máquinas remotas a través de una red, ya sea local o pública.

Permite manejar por completo el ordenador mediante un intérprete de comandos, y también puede redirigir el tráfico de aplicaciones gráficas si tenemos un Servidor X (en sistemas tipo Unix y Windows) corriendo.

== Seguridad ==
SSH funciona de manera similar a Telnet con la diferencia de que aquí la información viaja cifrada, lo cual hace inútil la intercepción de un paquete al ser éste ilegible.

Además de conectarnos a otros dispositivos para manejarlos remotamente, SSH también nos permite crear túneles a través de los cuales podemos redirigir tráfico, o enviar y recibir ficheros de forma totalmente segura, fiable y simple gracias a su gestión de claves RSA, como si se tratase de un servidor FTP.

Por lo tanto, podemos concluir que la seguridad está presente en todo momento.

== Tunneling ==
[[Imagen:Tunneling.png|thumb|130px|right|Esquema Tunneling]]

Por lo general, los protocolos envían sus datos «en claro» (sin encriptar), por lo que cualquier persona con acceso físico a nuestra red y un sniffer (programa de captura de tramas de red) es capaz de interceptar nuestros paquetes y verlos libremente.
Si tenemos información sensible en circulación, la
seguridad estará seriamente comprometida, obviando usuarios y contraseñas como en los casos de Telnet o FTP.

El tunneling nos permitirá salvar este problema fácilmente sin dejar de usar los protocolos que necesitemos. Esta técnica consiste en abrir conexiones entre dos máquinas por medio de un protocolo seguro, como puede ser el SSH, a través de las cuales realizaremos las transferencias inseguras, que pasarán de este modo a ser seguras.

== Aplicaciones del SSH ==
Resumiendo, las principales aplicaciones del SSH que en esta página se van a explicar son:

* Redirigir el tráfico de algunos puertos, por ejemplo de un cliente de correo (Thunderbird). Es decir, encriptar nuestras conexiones para evitar miradas «ajenas» gracias a que creamos un túnel seguro entre el puerto del servidor de correo (ej. 110) y uno local (ej. 1110).
* Saltarse un cortafuegos.
* Enviar y descargar archivos de manera segura.
* Acceso total a una computadora remota por Terminal.

Todo lo vamos a hacer desde el punto de vista de una distribución Linux, en nuestro caso y por ser la más extendida a nivel de usuario, Ubuntu.

== Instalando y Configurando SSH ==
Abrimos un terminal de Ubuntu y escribimos:

<code>'''sudo apt-get install openssh-server'''</code>

Seguidamente, pasamos a configurar nuestro servidor ya instalado. Para ello usaremos el editor de textos '''nano''', aunque también podríamos usar '''gedit''' o '''vim''':

<code>'''sudo nano /etc/ssh/sshd_config'''</code>

Claves para aumentar la seguridad de nuestro servidor:
* Cambiar el puerto estándar de conexión (22) a otro cualquiera para evitar ataques es una buena forma de permanecer invisibles a los molestos bots que, a pesar de no representar una amenaza sin tener nuestra contraseña de acceso, es mejor evitar. Para ello, en la quinta línea, cambiamos el puerto a, por ejemplo:
<code>Port 443 (Estándar HTTPS)</code>

* No permitir el logueo como Root es algo básico y esencial para la seguridad de nuestro sistema. Así que buscamos la línea siguiente y cambiamos el valor de "yes" a "no":
<code>PermitRootLogin no</code>

* Imponer un número máximo de intentos fallidos de autentificación es una buena estrategia, sobre todo si nuestro servidor está escuchando en una red pública. De ésta forma podremos evitar que un posible atacante intente averiguar una contraseña por un método de fuerza bruta. En este caso, '''crearemos una nueva instrucción dentro del archivo''', de la siguiente forma:
<code>MaxAuthTries 2 (si fallamos dos veces la contraseña, el servidor nos desconecta y hay que volver a establecer la conexión)</code>

* Definir exactamente quién puede o no acceder a nuestro servidor puede ser útil especialmente si trabajamos a nivel local, aunque es extensible a la red externa. Para ello, basta con configurar los archivos hosts.allow (permitir) y hosts.deny (denegar) añadiendo las IP's que nos interese administrar (un buen paranoico, denegaría todas las conexiones y configuraría solo las que fueran absolutamente necesarias):
<code>'''sudo nano /etc/hosts.allow'''
'''sudo nano /etc/hosts.deny'''</code>

== Arranque y parada del servidor ==
* Arrancar el servidor SSH:
<code>'''sudo service ssh start'''</code>

* Detener el servicio:
<code>'''sudo service ssh stop'''</code>

* Reiniciar el servicio:
<code>'''sudo service ssh restart'''</code>

== Clientes DNS ==
Si tenemos intención de usar nuestro servidor SSH externamente a nuestra red local, necesitaremos un cliente DNS que nos permita olvidar nuestra dirección IP; más aún en el caso de ser dinámica, y sustituirla por un nombre de dominio.

Aquí vamos a trabajar con dos servicios distintos y gratuitos: [http://www.no-ip.com No-IP.com] y [http://www.dyndns.com DynDNS.com]

----

=== No-IP ===
Nos registramos en su [http://www.no-ip.com página web], y cuando hayamos accedido al menú principal, clickeamos en Add a Host.

Seguidamente, escribiremos el nombre que le queramos dar al host, que irá seguido de un subdominio obligatorio que nos impone No-IP, aunque podremos elegir entre varios.

*El «Host Type» ha de ser siempre «DNS Host (A)» No debemos rellenar nada más, así que pulsamos en Create Host.

Una vez hecho esto, instalaremos el programa cliente en nuestro ordenador, que mandará periódicamente a nuestro dominio de No-IP la dirección IP que
tengamos en ese momento.
<code>'''sudo apt-get install noip2'''</code>
Durante la instalación, el programa nos hará preguntas para configurarse. No obstante, podremos reconfigurarlo sin problemas si algo ha ido mal con la siguiente instrucción:
<code>'''sudo noip2 -C'''</code>

Por último, solo nos queda por saber las instrucciones para arrancar, parar y reiniciar el servicio. Cabe decir que este servicio, al igual que el propio SSH, arrancará automáticamente con el ordenador una vez instalado.

* Arrancar el cliente noip2:
<code>'''sudo service noip2 start'''</code>

* Detener el servicio:
<code>'''sudo service noip2 stop'''</code>

* Reiniciar el servicio:
<code>'''sudo service noip2 restart'''</code>

----

=== DynDNS ===
Nos registramos en su [http://www.dyndns.com página web], y cuando hayamos accedido al menú principal, clickeamos en Add Host Services.
Seguidamente, escribiremos el nombre que le queramos dar al host, que irá seguido de un subdominio obligatorio que nos impone DynDNS, aunque podremos elegir entre varios.

*El «Service Type» ha de ser siempre «Host with IP adress».
*En el apartado IP Adress, pinchamos donde veamos nuestra IP y finalmente en Add to Cart.

Una vez hecho esto, instalaremos el programa cliente en nuestro ordenador, que mandará periódicamente a nuestro dominio de DynDNS la dirección IP que
tengamos en ese momento.
<code>'''sudo apt-get install ddclient'''</code>
Durante la instalación, el programa nos hará preguntas para configurarse. No obstante, podremos reconfigurarlo sin problemas si algo ha ido mal con la siguiente instrucción:
<code>'''sudo dpkg-reconfigure ddclient'''</code>

Si usamos ddclient, solo tendremos la opción de reiniciar el servicio, ni arrancarlo ni pararlo, y lo haremos de la siguiente forma:

<code>'''sudo service ddclient restart'''</code>

== Notas ==
* No olvidar nunca abrir correctamente el puerto que vayamos a usar en el SSH tanto en nuestro router como en el cortafuegos.

* Los servicios de No-Ip y DynDNS nos enviarán aproximadamente cada sesenta días un e-mail pidiéndonos que confirmemos que queremos mantener nuestros dominos activos (al usarlos como SSH no se registran visitas a los mismos y por lo tanto parece que están inactivos)

== Accediendo remotamente ==
Lo más básico de todo consiste en realizar una conexión simple que nos permita acceder y loguearnos remotamente a nuestro ordenador con el servidor SSH ya activo. Para ello, abrimos un terminal y tecleamos:
<code>'''ssh -p puerto usuario@host'''</code>

Si el puerto es el 22 (por defecto) podemos omitir la opción -p. Un ejemplo práctico del comando anterior:
<code>'''ssh -p 443 fernando@micasa.dyndns.org</code>

Con esta simple instrucción, automáticamente el terminal pasará a tener nuestro usuario y equipo, y podremos usarlo como si estuviésemos en nuestro propio PC: instalar programas, eliminar archivos, reiniciar el sistema...

[[Imagen:FileZilla.png|thumb|130px|right|Esquema FileZilla]]
Una buena forma, cómoda y rápida de traspasar archivos entre el servidor y el ordenador utilizado en ese momento, es el programa FileZilla (libre y en los repositorios de Ubuntu), que nos permite conectarnos del mismo modo que si fuese una conexión FTP.

Se puede comprobar en la captura de la derecha cómo configurar correctamente el programa para acceder a nuestro sistema remotamente.

Si lo que buscamos es redireccionar puertos para aumentar la seguridad en nuestras conexiones Web o SMPT (encriptándolas), o sencillamente saltarnos un cortafuegos, podremos hacerlo de dos formas:

* Redireccionamiento estático

* Redireccionamiento dinámico

----

=== Redireccionamiento estático ===
Este tipo de redireccionamiento nos permite conectarnos a '''un puerto de un servidor''', a través de un puerto local que le ordenemos.
Especialmente útil para clientes de correo por ejemplo, como se ha dicho anteriormente.

La sintaxis es la siguiente:
<code>'''ssh -L puerto.local:servidor:puerto.remoto usuario@host'''</code>

Un ejemplo práctico, en el caso de querer conectarnos a Gmail por ejemplo:
<code>'''ssh -L 10993:imap.googlemail.com:993 fernando@micasa.dyndns.org'''</code>

[[Imagen:Thunderbird.png|thumb|130px|right|Configuración de Thunderbird para redireccionamiento de puertos estático]]
Lo que estamos haciendo con la sintaxis anterior es decirle al ordenador: «cuando me conecte en local al puerto '''10993''' (debemos poner '''siempre un valor por encima de 1024''', que son los puertos reservados), quiero que me devuelvas la
información que hay en '''imap.googlemail.com''' por el puerto '''993''' a través del servidor de SSH '''fernando@micasa.dyndns.org'''»

Seguidamente, debemos configurar nuestra cuenta de Thunderbird por ejemplo, tal y como aparece en la captura de la derecha (en Editar → Configuración de las cuentas).

----

=== Redireccionamiento dinámico ===
Este tipo de redireccionamiento nos permite conectarnos a '''cualquier puerto de cualquier servidor''' a través de un puerto local que le ordenemos.

A esto se le denomina túneles dinámicos, ya que se crean y se destruyen conforme los vamos necesitando, automáticamente.

La sintaxis es la siguiente:
<code>'''ssh -D puerto.local usuario@host'''</code>

Muy útil para saltarnos cortafuegos y capados:
<code>'''ssh -D 10000 fernando@micasa.dyndns.org'''</code>

Podemos ver un esquema de lo que ocurre cuando se establece un túnel SSH en la siguiente imagen:
[[Archivo:Cortafuegos.png|400px|center|none]]

[[Imagen:Socks.png|thumb|130px|right|Configuración de Firefox para redireccionamiento de puertos dinámico]]
Lo que estamos haciendo con la sintaxis anterior
<code>'''ssh -D 10000 fernando@micasa.dyndns.org'''</code>
es decirle al ordenador: «quiero que todas mis conexiones pasen por el puerto '''10000''' a través del servidor de SSH '''fernando@micasa.dyndns.org''' (que es el
ordenador que tiene acceso a la red sin restricciones)».

Seguidamente, debemos configurar el programa que queremos que se conecte a la red con un proxy '''SOCKS''' del siguiente modo. Tenemos una captura de pantalla a la derecha a modo de ejemplo con Mozilla Firefox (en Preferencias → Avanzadas → Red → Configuración)

También podemos colocar la misma configuración de conexión en nuestro cliente de correo, de modo que no sería ya necesario hacer túneles «manualmente».
Este proceso de creación de túneles está especialmente recomendado en entornos de redes no fiables, como puede ser una cafetería o un aeropuerto.

== Algunas opciones de utilidad ==
Las opciones con las que podemos conectarnos a nuestro servidor SSH son múltiples y muy variadas. Aquí una pequeña lista de las más reseñables:

* '''-C''' Comprime los datos para ahorrar ancho de banda.

* '''-f''' Manda todo el SSH a un segundo plano tras ejecutarse.

* '''-n''' Evita que muestre output; todo lo que sale lo manda a /dev/null.

* '''-N''' Evita que se ejecute una shell, útil si lo único que queremos es redireccionar puertos.

* '''-v''' Muestra en pantalla todas las operaciones realizadas por el SSH. Muy útil para identificar problemas de conexión.

* '''-X''' Activa la posibilidad de ejecutar aplicaciones gráficas remotamente (X11). Con esto es posible ejecutar un programa que no se tiene instalado en la máquina cliente pero sí en el servidor, aunque la velocidad no es muy elevada.

Como curiosidad extra, cabe destacar que si al realizar la conexión SSH está activada la opción '''-X''', al escribir la siguiente instrucción una vez logueados en el ordenador remoto:
<code>'''DISPLAY=:0.0'''</code>
si tratamos de ejecutar un programa cualquiera, éste lo hará en el ordenador remoto y no en el que estemos utilizando en ese momento, como sería de esperar.

Esto ocurre porque estamos modificando una variable llamada «de entorno», que altera el normal funcionamiento de la impresión en pantalla. La variable dejará de funcionar en el momento en que finalicemos la conexión al sistema remoto. No obstante, si se desea volver a la opción por defecto sin reiniciar la conexión, basta con escribir esto:
<code>'''DISPLAY=localhost:10.0'''</code>

Para preguntar en cualquier momento por el estado de la display, haremos:
<code>'''$echo DISPLAY'''</code>

== Enlaces externos ==
* [http://www.mediafire.com/?73s418y5qrtoh3t Manual de SSH] sobre el que se basa toda esta página de Wiki, realizado por Fernando-Enzo Guarini para el taller de SSH de la asociación [http://sugus.eii.us.es/web/ SUGUS] de la ETSII del 15 de Diciembre de 2010.
* [http://www.openssh.org Sitio Oficial de OpenSSH] (en inglés)
* [http://security.debian.org Seguridad de Debian] Sitio oficial. (en inglés)
* [http://www.guia-ubuntu.org/index.php?title=Servidor_ssh Guía documentada para Ubuntu] (en español)
* [http://www.howtoforge.com/secure_mysql_connection_ssh_tunnel Securing the connection between MySQL and MySQL Administrator using an SSH tunnel] Crear un túnel SSH al servidor MySQL. (en inglés)
* [http://webssh.cz.cc Cliente SSH en un sitio web] (en inglés)
* [http://crysol.org/es/ssh-public-key SSH y SCP sin contraseña] (en español)

Estructura típica de dispositivo E/S

2011-12-20T13:17:35Z

Ferguatol: /* Arquitecturas de ordenadores típicas */

Criterios de reemplazo

2011-12-20T00:25:22Z

Ferguatol: EXPLICACIÓN ACLARADA

La evaluación se hace en base a la '''tasa de fallos de página''', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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

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

== Criterio de página óptima ==

Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

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

*[[sol_1|Solución]]

== Criterio de página pésima ==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

*[[sol_2|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Se trata también de un criterio teórico, serviría para aproximar la cota media de la ''tasa de fallos de página''. Consiste en seleccionar una página al azar.

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

*[[sol_3|Solución]]

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

Ofrece dos bits para cada página:
* Bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* Bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, siempre se pone a 1 el bit R, y solo se toca M cuando se accede a escritura.

Para seleccionar la página víctima iteramos sobre los marcos cargados en memoria (comenzando por el primero de ellos) buscando el que cumpla lo siguiente, en este orden:

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

Periódicamente se pone a cero el bit R.

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

Se trata de la combinación de los criterios FIFO y NRU, pero sin emplear el bit M de NRU. Cuando hay que seleccionar una página víctima, se recorre la lista de páginas por orden de carga en memoria hasta encontrar alguna que tenga el bit R a 0. Durante la iteración, si se encuentra una cuyo bit R valga 1, se pone a 0, se retira de la lista y se añade al final (para darle una segunda oportunidad). Cuando se añade una nueva página, se añade al final de la cola con el bit R a 1.

*[[sol_7|Solución]]

;Criterio del reloj: Es una variante en la manera de implementar la 2ª oportunidad. Se emplea una lista circular. En lugar de eliminar y añadir elementos al final de la FIFO, mantenemos un puntero a la página siguiente a la última página víctima seleccionada.

*[[sol_reloj|Solución]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

Es justamente el criterio contrario al MRU. En LRU elegimos la página que más tiempo lleve sin ser accedida. Se implementa mediante una FIFO que mantiene el '''orden de acceso''' a las páginas. Es decir, cada vez que se accede a una página, en caso de estar ya en la FIFO, se retira de la cola y se añade al final.

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se selecciona a la página que haya sido accedida con menor frecuencia. Se implementa mediante un contador. Básicamente, por cada acceso se incrementa el contador de uso de la página. La página víctima será aquella con menor contador. Cuando una página es expulsada a disco su contador pasa a ser cero.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

Se tiene un bit R y un contador por cada marco. Cuando una página es cargada a un marco, se carga con su bit R a 1 y su contador inicial a 0. Cuando pasa un período determinado de tiempo (viene dado en el enunciado) se itera sobre toda la lista de páginas, y pueden ocurrir dos cosas:
* '''Si su bit R está a 1''': Se ponen su bit R y su contador a 0.
* '''Si su bit R está a 0''': Se incrementa el contador una unidad.

Cuando hay que seleccionar una página víctima, se escoge aquella cuyo contador sea mayor. En caso de empate, habrá que establecer un criterio de desempate.

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

== Sustitución por envejecimiento ==

Se emplea un registro R de N bits. Por cada acceso se pone a 1 el bit más significativo. Periódicamente se desplaza hacia la derecha el registro R. La página víctima será la que tenga el menor valor en el registro R (en caso de empate se emplea otro criterio). La información que contienen los bits menos significativos se pierden al realizar desplazamientos. Este criterio permite mantener un historial de acceso a las páginas, para seleccionar como víctima aquella que lleve más tiempo sin ser accedida.

*[[sol_10|Solución]]

= Implementaciones =

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

Criterios de reemplazo

2011-12-20T00:00:48Z

Ferguatol: /* Aproximación discreta LRU */

La evaluación se hace en base a la '''tasa de fallos de página''', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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

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

== Criterio de página óptima ==

Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

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

*[[sol_1|Solución]]

== Criterio de página pésima ==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

*[[sol_2|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Se trata también de un criterio teórico, serviría para aproximar la cota media de la ''tasa de fallos de página''. Consiste en seleccionar una página al azar.

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

*[[sol_3|Solución]]

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

Ofrece dos bits para cada página:
* Bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* Bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, siempre se pone a 1 el bit R, y solo se toca M cuando se accede a escritura.

Para seleccionar la página víctima iteramos sobre los marcos cargados en memoria (comenzando por el primero de ellos) buscando el que cumpla lo siguiente, en este orden:

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

Periódicamente se pone a cero el bit R.

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

Se trata de la combinación de los criterios FIFO y NRU, pero sin emplear el bit M de NRU. Cuando hay que seleccionar una página víctima, se recorre la lista de páginas por orden de carga en memoria hasta encontrar alguna que tenga el bit R a 0. Durante la iteración, si se encuentra una cuyo bit R valga 1, se pone a 0, se retira de la lista y se añade al final (para darle una segunda oportunidad). Cuando se añade una nueva página, se añade al final de la cola con el bit R a 1.

*[[sol_7|Solución]]

;Criterio del reloj: Es una variante en la manera de implementar la 2ª oportunidad. Se emplea una lista circular. En lugar de eliminar y añadir elementos al final de la FIFO, mantenemos un puntero a la página siguiente a la última página víctima seleccionada.

*[[sol_reloj|Solución]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

Es justamente el criterio contrario al MRU. En LRU elegimos la página que más tiempo lleve sin ser accedida. Se implementa mediante una FIFO que mantiene el '''orden de acceso''' a las páginas. Es decir, cada vez que se accede a una página, en caso de estar ya en la FIFO, se retira de la cola y se añade al final.

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se selecciona a la página que haya sido accedida con menor frecuencia. Se implementa mediante un contador. Básicamente, por cada acceso se incrementa el contador de uso de la página. La página víctima será aquella con menor contador. Cuando una página es expulsada a disco su contador pasa a ser cero.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

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

¿Se supone que esto es una explicación de nada?--[[Usuario:Ferguatol|fernandoenzo]] 00:00 20 dic 2011 (UTC)

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

== Sustitución por envejecimiento ==

Se emplea un registro R de N bits. Por cada acceso se pone a 1 el bit más significativo. Periódicamente se desplaza hacia la derecha el registro R. La página víctima será la que tenga el menor valor en el registro R (en caso de empate se emplea otro criterio). La información que contienen los bits menos significativos se pierden al realizar desplazamientos. Este criterio permite mantener un historial de acceso a las páginas, para seleccionar como víctima aquella que lleve más tiempo sin ser accedida.

*[[sol_10|Solución]]

= Implementaciones =

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

SO multiprogramables con particiones variables

2011-12-19T22:18:32Z

Ferguatol: /* Siguiente ajuste */

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.

Ejemplo: Suponiendo una memoria principal de 32 KB.

| H0 | t | M |
-------------------
P1 | 0 | 5 | 6 |
P2 | 1 | 3 | 6 |
P3 | 2 | 5 | 8 |
P4 | 3 | 1 | 7 |
P5 | 4 | 2 | 7 |
P6 | 5 | 2 | 5 |

Solución:
0-5
P1 <---|---|---|---|---> | | | | | | | | | | | | | | |
6-11
P2 | <---|---|---> | | | | | | | | | | | | | | | |
12-19
P3 | | <---|---|---|---|---> | | | | | | | | | | | | |
20-26
P4 | | | <---> | | | | | | | | | | | | | | | |
20-26
P5 | | | | <---|---> | | | | | | | | | | | | | |
0-4
P6 | | | | | <---|---> | | | | | | | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

Ejemplo: Suponiendo una memoria principal de 32 KB.

| H0 | t | M |
-------------------
P1 | 0 | 5 | 6 |
P2 | 1 | 3 | 6 |
P3 | 2 | 5 | 8 |
P4 | 3 | 1 | 7 |
P5 | 4 | 2 | 7 |
P6 | 5 | 2 | 5 |

Solución:

0-5
P1 <---|---|---|---|---> | | | | | | | | | | | | | | |
6-11
P2 | <---|---|---> | | | | | | | | | | | | | | | |
12-19
P3 | | <---|---|---|---|---> | | | | | | | | | | | | |
20-26
P4 | | | <---> | | | | | | | | | | | | | | | |
20-26
P5 | | | | <---|---> | | | | | | | | | | | | | |
27-31
P6 | | | | | <---|---> | | | | | | | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

'''DUDA:'''

Es evidente que cuando llega el P5 se necesitan 7 unidades de memoria, y éstas no están disponibles en el hueco de 27 a 31 (ahí solo hay 4) por lo que da la vuelta, vuelve a comenzar y lo asigna al primero que encuentra, que resulta ser casualmente, el 20-26. --[[Usuario:Ferguatol|fernandoenzo]] 22:14 19 dic 2011 (UTC)

== Mejor ajuste ==

Consiste en asignarle al proceso el hueco con menor ajuste interno, i.e, el hueco el cual al serle asignado el proceso deja menos espacio sin utilizar. 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, i.e, el hueco el cual al serle asignado el proceso deja más espacio sin utilizar. 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.

SO multiprogramables con particiones variables

2011-12-19T22:17:55Z

Ferguatol: /* Siguiente ajuste */

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.

Ejemplo: Suponiendo una memoria principal de 32 KB.

| H0 | t | M |
-------------------
P1 | 0 | 5 | 6 |
P2 | 1 | 3 | 6 |
P3 | 2 | 5 | 8 |
P4 | 3 | 1 | 7 |
P5 | 4 | 2 | 7 |
P6 | 5 | 2 | 5 |

Solución:
0-5
P1 <---|---|---|---|---> | | | | | | | | | | | | | | |
6-11
P2 | <---|---|---> | | | | | | | | | | | | | | | |
12-19
P3 | | <---|---|---|---|---> | | | | | | | | | | | | |
20-26
P4 | | | <---> | | | | | | | | | | | | | | | |
20-26
P5 | | | | <---|---> | | | | | | | | | | | | | |
0-4
P6 | | | | | <---|---> | | | | | | | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

Ejemplo: Suponiendo una memoria principal de 32 KB.

| H0 | t | M |
-------------------
P1 | 0 | 5 | 6 |
P2 | 1 | 3 | 6 |
P3 | 2 | 5 | 8 |
P4 | 3 | 1 | 7 |
P5 | 4 | 2 | 7 |
P6 | 5 | 2 | 5 |

Solución:

0-5
P1 <---|---|---|---|---> | | | | | | | | | | | | | | |
6-11
P2 | <---|---|---> | | | | | | | | | | | | | | | |
12-19
P3 | | <---|---|---|---|---> | | | | | | | | | | | | |
20-26
P4 | | | <---> | | | | | | | | | | | | | | | |
20-26
P5 | | | | <---|---> | | | | | | | | | | | | | |
27-31
P6 | | | | | <---|---> | | | | | | | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

'''DUDA:'''
En este ejercicio, en el instante 4, el proceso 5 vuelve a entrar en las posiciones de memoria 20-26, pero se supone que en este criterio se usan los espacios siguientes a los que ya se han usado, que, en este caso, serían 27-33. Si no se hace así estaríamos en el mismo criterio que antes (primer ajuste). ¿No? --[[Usuario:Juamenmor|Juamenmor]]

Tengo la misma duda; además, ¿Qué es lo que ocurre cuando llega al final de la memoria?¿vuelve a empezar? por ejemplo si fuera 27-33... ¿no entraría el proceso en la memoria?(un poco absurdo) ¿o volvería al principio desde 0 y se saltaría esos últimos huecos?...--[[Usuario:Danplaseg|Danplaseg]] 19:08 18 dic 2011 (UTC)

Es evidente que cuando llega el P5 se necesitan 7 unidades de memoria, y éstas no están disponibles en el hueco de 27 a 31 (ahí solo hay 4) por lo que da la vuelta, vuelve a comenzar y lo asigna al primero que encuentra, que resulta ser casualmente, el 20-26. --[[Usuario:Ferguatol|fernandoenzo]] 22:14 19 dic 2011 (UTC)

== Mejor ajuste ==

Consiste en asignarle al proceso el hueco con menor ajuste interno, i.e, el hueco el cual al serle asignado el proceso deja menos espacio sin utilizar. 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, i.e, el hueco el cual al serle asignado el proceso deja más espacio sin utilizar. 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.

SO multiprogramables con particiones variables

2011-12-19T22:14:50Z

Ferguatol: /* Siguiente ajuste */

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.

Ejemplo: Suponiendo una memoria principal de 32 KB.

| H0 | t | M |
-------------------
P1 | 0 | 5 | 6 |
P2 | 1 | 3 | 6 |
P3 | 2 | 5 | 8 |
P4 | 3 | 1 | 7 |
P5 | 4 | 2 | 7 |
P6 | 5 | 2 | 5 |

Solución:
0-5
P1 <---|---|---|---|---> | | | | | | | | | | | | | | |
6-11
P2 | <---|---|---> | | | | | | | | | | | | | | | |
12-19
P3 | | <---|---|---|---|---> | | | | | | | | | | | | |
20-26
P4 | | | <---> | | | | | | | | | | | | | | | |
20-26
P5 | | | | <---|---> | | | | | | | | | | | | | |
0-4
P6 | | | | | <---|---> | | | | | | | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

Ejemplo: Suponiendo una memoria principal de 32 KB.

| H0 | t | M |
-------------------
P1 | 0 | 5 | 6 |
P2 | 1 | 3 | 6 |
P3 | 2 | 5 | 8 |
P4 | 3 | 1 | 7 |
P5 | 4 | 2 | 7 |
P6 | 5 | 2 | 5 |

Solución:

0-5
P1 <---|---|---|---|---> | | | | | | | | | | | | | | |
6-11
P2 | <---|---|---> | | | | | | | | | | | | | | | |
12-19
P3 | | <---|---|---|---|---> | | | | | | | | | | | | |
20-26
P4 | | | <---> | | | | | | | | | | | | | | | |
20-26
P5 | | | | <---|---> | | | | | | | | | | | | | |
27-31
P6 | | | | | <---|---> | | | | | | | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

'''DUDA:'''
En este ejercicio, en el instante 4, el proceso 5 vuelve a entrar en las posiciones de memoria 20-26, pero se supone que en este criterio se usan los espacios siguientes a los que ya se han usado, que, en este caso, serían 27-33. Si no se hace así estaríamos en el mismo criterio que antes (primer ajuste). ¿No? --[[Usuario:Juamenmor|Juamenmor]]

Tengo la misma duda; además, ¿Qué es lo que ocurre cuando llega al final de la memoria?¿vuelve a empezar? por ejemplo si fuera 27-33... ¿no entraría el proceso en la memoria?(un poco absurdo) ¿o volvería al principio desde 0 y se saltaría esos últimos huecos?...--[[Usuario:Danplaseg|Danplaseg]] 19:08 18 dic 2011 (UTC)

Yo creo que como la memoria es de 32kb (nuestro intervalo iría entonces de 0-31) en caso de superar el 31, no cabería en la memoria y tendríamos que empezar a buscar empezando desde la primera posición.

Es evidente que cuando llega el P5 se necesitan 7 unidades de memoria, y éstas no están disponibles en el hueco de 27 a 31 (ahí solo hay 4) por lo que da la vuelta, vuelve a comenzar y lo asigna al primero que encuentra, que resulta ser casualmente, el 20-26. --[[Usuario:Ferguatol|fernandoenzo]] 22:14 19 dic 2011 (UTC)

== Mejor ajuste ==

Consiste en asignarle al proceso el hueco con menor ajuste interno, i.e, el hueco el cual al serle asignado el proceso deja menos espacio sin utilizar. 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, i.e, el hueco el cual al serle asignado el proceso deja más espacio sin utilizar. 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.

SO multiprogramables con particiones fijas

2011-12-19T21:57:05Z

Ferguatol: /* Métodos de colocación en memoria */

En la administración de memoria con particiones de tamaño fijo consideramos que la memoria se encuentra dividida en porciones fijas de diferente tamaño. La división se realizaría durante la instalación del sistema operativo, y para modificar el esquema de particionamiento necesitaríamos reiniciar el sistema para que surtan efecto los cambios. Por cada partición sólo puede haber un único proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

Esta aproximación tiene dos limitaciones importantes, que son:

* Si un proceso necesita más memoria que la partición más grande puede ofrecer, entonces éste no se puede ejecutar.
* Alto desperdicio de memoria, particularmente en el caso de que un proceso ocupe una partición de tamaño mayor al que necesita.

= Criterios de asignación =

Cuando se lanza un programa, el administrador de memoria tiene que decidir en qué partición de memoria va a cargar el proceso recién creado. Para ello se emplean diferentes criterios.

== Mejor ajuste estático ==

Se adjudica a cada proceso a la menor partición en la que quepa. Si la menor partición en la que cabe estuviera ocupada, dicho proceso tiene que esperar a que se libere. Esta estrategia evita el desperdicio de memoria. Sin embargo, puede retrasar la ejecución de un proceso estando libre otras particiones sin usarse. Este mecanismo se puede implementar con una cola por partición. El orden de complejidad computacional sería <math>O(1)</math>.

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M2
P3 | | < | | |---|---|---|---|---> | | | | | | | | | | P3-->M2
M3
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M3
M1
P5 | | | | < | | |---|---|---> | | | | | | | | | | P5-->M1
M4
P6 | | | | | <---|---> | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

=== Otro ejemplo ===

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:

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

== Primer ajuste ==

Igual que el anterior, sólo que nuestro proceso pasa a la primera partición libre en la que menor desperdicio de memoria se produzca. Por tanto, los procesos nunca esperan siempre que hay alguna partición libre. Complejidad: O(1)

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

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M3
P3 | | <---|---|---|---|---> | | | | | | | | | | | | | P3-->M3
M4
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M4
M2
P5 | | | | < |---|---|---> | | | | | | | | | | | | P5-->M2
M4
P6 | | | | | < | | |---|---> | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico ==

De entre todos los procesos que pueden asignarse a una partición, se asigna el mayor proceso que quepa en ella. Por tanto, se itera sobre todos los procesos que se quieren cargar en memoria para ver cuál de ellos es el que menor desperdicio produce. Tal y como sucedía con el mejor ajuste estático, los procesos tienen que esperar a que quede libre la partición en la que menor desperdicio se produce. --[[Usuario:Pneira|Pneira]] 13:40 13 dic 2011 (UTC)

El principal inconveniente de este criterio es que los procesos que mayor desperdicio generan van a ser postergados indefinidamente. Complejidad: O(n).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 15 |
P5 | 1 | 3 | 3 |
P6 | 1 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 < | | | | |---|---|---|---|---|---|---> | | | | | | | | P1-->M1
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | | P2-->M2
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | | P3-->M1
M3
P4 | <---|---|---|---|---> | | | | | | | | | | | | | | P4-->M3
M2
P5 | < | | |---|---|---> | | | | | | | | | | | | | P5-->M2
M4
P6 | <---|---> | | | | | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 6 |
P5 | 1 | 3 | 7 |
P6 | 1 | 2 | 5 |

Suponiendo que todo proceso puede ser aplazado como máximo una sola vez.

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M2
P1 < | | | |---|---|---|---|---|---|---> | | | | | | | | |
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | |
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | |
M1
P4 | < | | | | | | |---|---|---|---|---> | | | | | | |
M1
P5 | < | | | |---|---|---> | | | | | | | | | | | |
M2
P6 | < | | | | | | | | | |---|---> | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== 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 hasta que haya sitio para ellos y se asigna la partición madre al proceso grande.

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 =

En el momento de lanzamiento hay que realizar la carga del código del proceso en memoria. Hay diferentes estrategias de colocación, que son:

*'''Montaje absoluto''': El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.

* '''Carga con reubicación''': Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.

* '''Reubicación dinámica''': Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En '''tiempo de ejecución''' se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.

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

* '''Bits de protección''' : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura

* '''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. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.

Introducción

2011-12-19T17:42:10Z

Ferguatol:

El administrador de memoria se trata de la parte del sistema operativo que se encarga de gestionar la memoria principal existente en el sistema. Para ello, asigna zonas de memoria principal a cada uno de los procesos existentes en base a sus necesidades.

Todo proceso, desde el punto de vista de la memoria, está compuesto de tres secciones:

* ''Código'': Se trata de la sección de memoria que contiene el código de nuestro proceso, entendido como la sección de instrucciones que componen nuestro programa.
* ''Variables globales y constantes'': Esta sección incluye las constantes definidas en el código del programa. Además, incluyen también las variable globales, que se trata de aquellas que son accesibles desde cualquier función.
* ''Pila'': Se trata de la sección de memoria que se emplea para reservar espacio a las variables locales, y en la invocación de funciones (en las que se carga la dirección de retorno con respecto al código, la dirección de memoria en la que se encuentra definida la función y los parámetros de dicha función).

Cuando se lanza un programa desde el lanzador de aplicaciones se hace uso de las llamadas al sistema ''fork'' y ''exec''. La llamada ''fork'' crea un proceso clon del lanzador de aplicaciones, mientras que la llamada al sistema ''exec'' reemplaza el código del proceso clon recién creado por el de un programa que se encuentra almacenado en un fichero. El administrador de memoria actúa ante estas llamadas al sistema reservando memoria para el nuevo proceso que se acaba de lanzar.

En este tema, por razones de simplicidad, vamos a considerar que la administración de memoria se realiza de manera que '''todo''' el espacio de memoria ocupa una zona de memoria contigua. Es decir, no vamos a poder dividir las diferentes secciones de manera que se repartan en diferentes zonas de memoria que cuyo espacio de direccionamiento no sea consecutivo. No obstante, los sistemas operativos modernos '''no''' emplean las estrategias de asignación que vamos a ver a continuación:

* [[SO monoprogramables|Administración de memoria en sistemas operativos monoprogramables]]
* [[SO multiprogramables con particiones fijas|Administración de memoria en sistemas operativos multiprogramables con particiones fijas]]
* [[SO multiprogramables con particiones variables|Administración de memoria en sistemas operativos multiprogramables con particiones variables]]

Usuario:Juamenmor

2011-12-18T16:39:30Z

Ferguatol: Página creada con 'Juan Miguel Mendoza Moreno'

Juan Miguel Mendoza Moreno

SO multiprogramables con particiones fijas

2011-12-18T15:58:47Z

Ferguatol: /* Ejemplo */

En la administración de memoria con particiones de tamaño fijo consideramos que la memoria se encuentra dividida en porciones fijas de diferente tamaño. La división se realizaría durante la instalación del sistema operativo, y para modificar el esquema de particionamiento necesitaríamos reiniciar el sistema para que surtan efecto los cambios. Por cada partición sólo puede haber un único proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

Esta aproximación tiene dos limitaciones importantes, que son:

* Si un proceso necesita más memoria que la partición más grande puede ofrecer, entonces éste no se puede ejecutar.
* Alto desperdicio de memoria, particularmente en el caso de que un proceso ocupe una partición de tamaño mayor al que necesita.

= Criterios de asignación =

Cuando se lanza un programa, el administrador de memoria tiene que decidir en qué partición de memoria va a cargar el proceso recién creado. Para ello se emplean diferentes criterios.

== Mejor ajuste estático ==

Se adjudica a cada proceso a la menor partición en la que quepa. Si la menor partición en la que cabe estuviera ocupada, dicho proceso tiene que esperar a que se libere. Esta estrategia evita el desperdicio de memoria. Sin embargo, puede retrasar la ejecución de un proceso estando libre otras particiones sin usarse. Este mecanismo se puede implementar con una cola por partición. El orden de complejidad computacional sería <math>O(1)</math>.

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M2
P3 | | < | | |---|---|---|---|---> | | | | | | | | | | P3-->M2
M3
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M3
M1
P5 | | | | < | | |---|---|---> | | | | | | | | | | P5-->M1
M4
P6 | | | | | <---|---> | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

=== Otro ejemplo ===

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:

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

== Primer ajuste ==

Igual que el anterior, sólo que nuestro proceso pasa a la primera partición libre en la que menor desperdicio de memoria se produzca. Por tanto, los procesos nunca esperan siempre que hay alguna partición libre. Complejidad: O(1)

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

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M3
P3 | | <---|---|---|---|---> | | | | | | | | | | | | | P3-->M3
M4
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M4
M2
P5 | | | | < |---|---|---> | | | | | | | | | | | | P5-->M2
M4
P6 | | | | | < | | |---|---> | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico ==

De entre todos los procesos que pueden asignarse a una partición, se asigna el mayor proceso que quepa en ella. Por tanto, se itera sobre todos los procesos que se quieren cargar en memoria para ver cuál de ellos es el que menor desperdicio produce. Tal y como sucedía con el mejor ajuste estático, los procesos tienen que esperar a que quede libre la partición en la que menor desperdicio se produce. --[[Usuario:Pneira|Pneira]] 13:40 13 dic 2011 (UTC)

El principal inconveniente de este criterio es que los procesos que mayor desperdicio generan van a ser postergados indefinidamente. Complejidad: O(n).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 15 |
P5 | 1 | 3 | 3 |
P6 | 1 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 < | | | | |---|---|---|---|---|---|---> | | | | | | | | P1-->M1
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | | P2-->M2
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | | P3-->M1
M3
P4 | <---|---|---|---|---> | | | | | | | | | | | | | | P4-->M3
M2
P5 | < | | |---|---|---> | | | | | | | | | | | | | P5-->M2
M4
P6 | <---|---> | | | | | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 6 |
P5 | 1 | 3 | 7 |
P6 | 1 | 2 | 5 |

Suponiendo que todo proceso puede ser aplazado como máximo una sola vez.

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M2
P1 < | | | |---|---|---|---|---|---|---> | | | | | | | | |
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | |
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | |
M1
P4 | < | | | | | | |---|---|---|---|---> | | | | | | |
M1
P5 | < | | | |---|---|---> | | | | | | | | | | | |
M2
P6 | < | | | | | | | | | |---|---> | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== 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 hasta que haya sitio para ellos y se asigna la partición madre al proceso grande.

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 =

En el momento de lanzamiento hay que realizar la carga del código del proceso en memoria. Hay diferentes estrategias de colocación, que son:

*'''Montaje absoluto''': El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.

* '''Carga con reubicación''': Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.

* '''Reubicación dinámica''': Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En '''tiempo de ejecución''' se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.

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

* '''Bits de protección''' : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura

* '''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. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.

SO multiprogramables con particiones fijas

2011-12-18T15:58:33Z

Ferguatol: /* Ejemplo */

En la administración de memoria con particiones de tamaño fijo consideramos que la memoria se encuentra dividida en porciones fijas de diferente tamaño. La división se realizaría durante la instalación del sistema operativo, y para modificar el esquema de particionamiento necesitaríamos reiniciar el sistema para que surtan efecto los cambios. Por cada partición sólo puede haber un único proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

Esta aproximación tiene dos limitaciones importantes, que son:

* Si un proceso necesita más memoria que la partición más grande puede ofrecer, entonces éste no se puede ejecutar.
* Alto desperdicio de memoria, particularmente en el caso de que un proceso ocupe una partición de tamaño mayor al que necesita.

= Criterios de asignación =

Cuando se lanza un programa, el administrador de memoria tiene que decidir en qué partición de memoria va a cargar el proceso recién creado. Para ello se emplean diferentes criterios.

== Mejor ajuste estático ==

Se adjudica a cada proceso a la menor partición en la que quepa. Si la menor partición en la que cabe estuviera ocupada, dicho proceso tiene que esperar a que se libere. Esta estrategia evita el desperdicio de memoria. Sin embargo, puede retrasar la ejecución de un proceso estando libre otras particiones sin usarse. Este mecanismo se puede implementar con una cola por partición. El orden de complejidad computacional sería <math>O(1)</math>.

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M2
P3 | | < | | |---|---|---|---|---> | | | | | | | | | | P3-->M2
M3
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M3
M1
P5 | | | | < | | |---|---|---> | | | | | | | | | | P5-->M1
M4
P6 | | | | | <---|---> | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

=== Otro ejemplo ===

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:

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

== Primer ajuste ==

Igual que el anterior, sólo que nuestro proceso pasa a la primera partición libre en la que menor desperdicio de memoria se produzca. Por tanto, los procesos nunca esperan siempre que hay alguna partición libre. Complejidad: O(1)

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

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M3
P3 | | <---|---|---|---|---> | | | | | | | | | | | | | P3-->M3
M4
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M4
M2
P5 | | | | < |---|---|---> | | | | | | | | | | | | P5-->M2
M4
P6 | | | | | < | | |---|---> | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico ==

De entre todos los procesos que pueden asignarse a una partición, se asigna el mayor proceso que quepa en ella. Por tanto, se itera sobre todos los procesos que se quieren cargar en memoria para ver cuál de ellos es el que menor desperdicio produce. Tal y como sucedía con el mejor ajuste estático, los procesos tienen que esperar a que quede libre la partición en la que menor desperdicio se produce. --[[Usuario:Pneira|Pneira]] 13:40 13 dic 2011 (UTC)

El principal inconveniente de este criterio es que los procesos que mayor desperdicio generan van a ser postergados indefinidamente. Complejidad: O(n).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 15 |
P5 | 1 | 3 | 3 |
P6 | 1 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 < | | | | |---|---|---|---|---|---|---> | | | | | | | | P1-->M1
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | | P2-->M2
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | | P3-->M1
M3
P4 | <---|---|---|---|---> | | | | | | | | | | | | | | P4-->M3
M2
P5 | < | | |---|---|---> | | | | | | | | | | | | | P5-->M2
M4
P6 | <---|---> | | | | | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 6 |
P5 | 1 | 3 | 7 |
P6 | 1 | 2 | 5 |

Suponiendo que todo proceso puede ser aplazado como máximo una sola vez.

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M2
P1 < | | | |---|---|---|---|---|---|---> | | | | | | | | |
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | |
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | |
M1
P4 | < | | | | | | |---|---|---|---|---> | | | | | | |
M1
P5 | < | | | |---|---|---> | | | | | | | | | | | |
M2
P6 | < | | | | | | | | | |---|---> | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== 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 hasta que haya sitio para ellos y se asigna la partición madre al proceso grande.

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 =

En el momento de lanzamiento hay que realizar la carga del código del proceso en memoria. Hay diferentes estrategias de colocación, que son:

*'''Montaje absoluto''': El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.

* '''Carga con reubicación''': Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.

* '''Reubicación dinámica''': Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En '''tiempo de ejecución''' se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.

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

* '''Bits de protección''' : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura

* '''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. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.

SO multiprogramables con particiones fijas

2011-12-18T15:58:21Z

Ferguatol: /* Ejemplo */

En la administración de memoria con particiones de tamaño fijo consideramos que la memoria se encuentra dividida en porciones fijas de diferente tamaño. La división se realizaría durante la instalación del sistema operativo, y para modificar el esquema de particionamiento necesitaríamos reiniciar el sistema para que surtan efecto los cambios. Por cada partición sólo puede haber un único proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

Esta aproximación tiene dos limitaciones importantes, que son:

* Si un proceso necesita más memoria que la partición más grande puede ofrecer, entonces éste no se puede ejecutar.
* Alto desperdicio de memoria, particularmente en el caso de que un proceso ocupe una partición de tamaño mayor al que necesita.

= Criterios de asignación =

Cuando se lanza un programa, el administrador de memoria tiene que decidir en qué partición de memoria va a cargar el proceso recién creado. Para ello se emplean diferentes criterios.

== Mejor ajuste estático ==

Se adjudica a cada proceso a la menor partición en la que quepa. Si la menor partición en la que cabe estuviera ocupada, dicho proceso tiene que esperar a que se libere. Esta estrategia evita el desperdicio de memoria. Sin embargo, puede retrasar la ejecución de un proceso estando libre otras particiones sin usarse. Este mecanismo se puede implementar con una cola por partición. El orden de complejidad computacional sería <math>O(1)</math>.

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M2
P3 | | < | | |---|---|---|---|---> | | | | | | | | | | P3-->M2
M3
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M3
M1
P5 | | | | < | | |---|---|---> | | | | | | | | | | P5-->M1
M4
P6 | | | | | <---|---> | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

=== Otro ejemplo ===

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:

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

== Primer ajuste ==

Igual que el anterior, sólo que nuestro proceso pasa a la primera partición libre en la que menor desperdicio de memoria se produzca. Por tanto, los procesos nunca esperan siempre que hay alguna partición libre. Complejidad: O(1)

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

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M3
P3 | | <---|---|---|---|---> | | | | | | | | | | | | | P3-->M3
M4
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M4
M2
P5 | | | | < |---|---|---> | | | | | | | | | | | | P5-->M2
M4
P6 | | | | | < | | |---|---> | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico ==

De entre todos los procesos que pueden asignarse a una partición, se asigna el mayor proceso que quepa en ella. Por tanto, se itera sobre todos los procesos que se quieren cargar en memoria para ver cuál de ellos es el que menor desperdicio produce. Tal y como sucedía con el mejor ajuste estático, los procesos tienen que esperar a que quede libre la partición en la que menor desperdicio se produce. --[[Usuario:Pneira|Pneira]] 13:40 13 dic 2011 (UTC)

El principal inconveniente de este criterio es que los procesos que mayor desperdicio generan van a ser postergados indefinidamente. Complejidad: O(n).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 15 |
P5 | 1 | 3 | 3 |
P6 | 1 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 < | | | | |---|---|---|---|---|---|---> | | | | | | | | P1-->M1
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | | P2-->M2
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | | P3-->M1
M3
P4 | <---|---|---|---|---> | | | | | | | | | | | | | | P4-->M3
M2
P5 | < | | |---|---|---> | | | | | | | | | | | | | P5-->M2
M4
P6 | <---|---> | | | | | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 6 |
P5 | 1 | 3 | 7 |
P6 | 1 | 2 | 5 |

Suponiendo que todo proceso puede ser aplazado como máximo una sola vez.

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M2
P1 < | | | |---|---|---|---|---|---|---> | | | | | | | | |
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | |
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | |
M1
P4 | < | | | | | | |---|---|---|---|---> | | | | | | |
M1
P5 | < | | | |---|---|---> | | | | | | | | | | | |
M2
P6 | < | | | | | | | | | |---|---> | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== 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 hasta que haya sitio para ellos y se asigna la partición madre al proceso grande.

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 =

En el momento de lanzamiento hay que realizar la carga del código del proceso en memoria. Hay diferentes estrategias de colocación, que son:

*'''Montaje absoluto''': El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.

* '''Carga con reubicación''': Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.

* '''Reubicación dinámica''': Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En '''tiempo de ejecución''' se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.

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

* '''Bits de protección''' : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura

* '''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. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.

SO multiprogramables con particiones fijas

2011-12-18T15:57:56Z

Ferguatol: /* Ejemplo */

En la administración de memoria con particiones de tamaño fijo consideramos que la memoria se encuentra dividida en porciones fijas de diferente tamaño. La división se realizaría durante la instalación del sistema operativo, y para modificar el esquema de particionamiento necesitaríamos reiniciar el sistema para que surtan efecto los cambios. Por cada partición sólo puede haber un único proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

Esta aproximación tiene dos limitaciones importantes, que son:

* Si un proceso necesita más memoria que la partición más grande puede ofrecer, entonces éste no se puede ejecutar.
* Alto desperdicio de memoria, particularmente en el caso de que un proceso ocupe una partición de tamaño mayor al que necesita.

= Criterios de asignación =

Cuando se lanza un programa, el administrador de memoria tiene que decidir en qué partición de memoria va a cargar el proceso recién creado. Para ello se emplean diferentes criterios.

== Mejor ajuste estático ==

Se adjudica a cada proceso a la menor partición en la que quepa. Si la menor partición en la que cabe estuviera ocupada, dicho proceso tiene que esperar a que se libere. Esta estrategia evita el desperdicio de memoria. Sin embargo, puede retrasar la ejecución de un proceso estando libre otras particiones sin usarse. Este mecanismo se puede implementar con una cola por partición. El orden de complejidad computacional sería <math>O(1)</math>.

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_____
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M2
P3 | | < | | |---|---|---|---|---> | | | | | | | | | | P3-->M2
M3
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M3
M1
P5 | | | | < | | |---|---|---> | | | | | | | | | | P5-->M1
M4
P6 | | | | | <---|---> | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

=== Otro ejemplo ===

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:

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

== Primer ajuste ==

Igual que el anterior, sólo que nuestro proceso pasa a la primera partición libre en la que menor desperdicio de memoria se produzca. Por tanto, los procesos nunca esperan siempre que hay alguna partición libre. Complejidad: O(1)

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

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M3
P3 | | <---|---|---|---|---> | | | | | | | | | | | | | P3-->M3
M4
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M4
M2
P5 | | | | < |---|---|---> | | | | | | | | | | | | P5-->M2
M4
P6 | | | | | < | | |---|---> | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico ==

De entre todos los procesos que pueden asignarse a una partición, se asigna el mayor proceso que quepa en ella. Por tanto, se itera sobre todos los procesos que se quieren cargar en memoria para ver cuál de ellos es el que menor desperdicio produce. Tal y como sucedía con el mejor ajuste estático, los procesos tienen que esperar a que quede libre la partición en la que menor desperdicio se produce. --[[Usuario:Pneira|Pneira]] 13:40 13 dic 2011 (UTC)

El principal inconveniente de este criterio es que los procesos que mayor desperdicio generan van a ser postergados indefinidamente. Complejidad: O(n).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 15 |
P5 | 1 | 3 | 3 |
P6 | 1 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 < | | | | |---|---|---|---|---|---|---> | | | | | | | | P1-->M1
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | | P2-->M2
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | | P3-->M1
M3
P4 | <---|---|---|---|---> | | | | | | | | | | | | | | P4-->M3
M2
P5 | < | | |---|---|---> | | | | | | | | | | | | | P5-->M2
M4
P6 | <---|---> | | | | | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

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

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 6 |
P5 | 1 | 3 | 7 |
P6 | 1 | 2 | 5 |

Suponiendo que todo proceso puede ser aplazado como máximo una sola vez.

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M2
P1 < | | | |---|---|---|---|---|---|---> | | | | | | | | |
M2
P2 <---|---|---|---> | | | | | | | | | | | | | | | |
M1
P3 <---|---|---|---|---> | | | | | | | | | | | | | | |
M1
P4 | < | | | | | | |---|---|---|---|---> | | | | | | |
M1
P5 | < | | | |---|---|---> | | | | | | | | | | | |
M2
P6 | < | | | | | | | | | |---|---> | | | | | | |
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== 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 hasta que haya sitio para ellos y se asigna la partición madre al proceso grande.

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 =

En el momento de lanzamiento hay que realizar la carga del código del proceso en memoria. Hay diferentes estrategias de colocación, que son:

*'''Montaje absoluto''': El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.

* '''Carga con reubicación''': Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.

* '''Reubicación dinámica''': Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En '''tiempo de ejecución''' se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.

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

* '''Bits de protección''' : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura

* '''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. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.

Criterios de reemplazo

2011-12-16T11:32:06Z

Ferguatol: /* Sustitución por envejecimiento */

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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

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

== Criterio de página óptima ==

Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

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

*[[sol_1|Solución]]

== Criterio de página pésima ==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

*[[sol_2|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Se trata también de un criterio teórico. Consiste en seleccionar una página al azar.

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

*[[sol_3|Solución]]

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

Ofrece dos bits para cada página:
* Bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* Bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, siempre se pone a 1 el bit R, y solo se toca M cuando se accede a escritura.

Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

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

Periódicamente se pone a cero el bit R.

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

Se trata de la unión del dos criterios, FIFO más NRU sin el bit M. Tampoco se pone R a 0 periódicamente. Cuando se añaden los procesos a los marcos, se añaden con el bit R a 1. Cuando se da un fallo de página, se recorre la lista de marcos hasta encontrar alguno que tenga R a 0. Si no encuentra ninguno que cumpla ésto, coloca todos los bits R a 0 y los pone en una cola. Se vuelve a iterar siguiendo el orden de la cola implementada. Es decir, cuando se encuenta un elemento con R a 1, se pone a 0 y se añade al final de la cola. Cuando se añade una nueva página, se añade al final de la cola con R a 1.

*[[sol_7|Solución]]

;Criterio del reloj: Es una variante en la manera de implementar la 2ª oportunidad. Se emplea una lista circular. En lugar de eliminar y añadir elementos al final de la FIFO, mantenemos un puntero a la página siguiente a la última página víctima seleccionada.

*[[sol_reloj|Solución]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

Es justamente el criterio contrario al MRU. En LRU elegimos la página que más tiempo lleve sin ser accedida. Se implementa mediante una FIFO que mantiene el '''orden de acceso''' a las páginas. Es decir, cada vez que se accede a una página, en caso de estar ya en la FIFO, se retira de la cola y se añade al final.

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se selecciona a la página que haya sido accedida con menor frecuencia. Se implementa mediante un contador. Básicamente, por cada acceso se incrementa el contador de uso de la página. La página víctima será aquella con menor contador. Cuando una página es expulsada a disco su contador pasa a ser cero.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

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

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

== Sustitución por envejecimiento ==

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

*[[sol_10|Solución]]

= Implementaciones =

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

Criterios de reemplazo

2011-12-16T11:15:52Z

Ferguatol: /* Criterio de 2ª oportunidad */ corrección

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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

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

== Criterio de página óptima ==

Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

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

*[[sol_1|Solución]]

== Criterio de página pésima ==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

*[[sol_2|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Se trata también de un criterio teórico. Consiste en seleccionar una página al azar.

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

*[[sol_3|Solución]]

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

Ofrece dos bits para cada página:
* Bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* Bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, siempre se pone a 1 el bit R, y solo se toca M cuando se accede a escritura.

Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

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

Periódicamente se pone a cero el bit R.

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

Se trata de la unión del dos criterios, FIFO más NRU sin el bit M. Tampoco se pone R a 0 periódicamente. Cuando se añaden los procesos a los marcos, se añaden con el bit R a 1. Cuando se da un fallo de página, se recorre la lista de marcos hasta encontrar alguno que tenga R a 0. Si no encuentra ninguno que cumpla ésto, coloca todos los bits R a 0 y los pone en una cola. Se vuelve a iterar siguiendo el orden de la cola implementada. Es decir, cuando se encuenta un elemento con R a 1, se pone a 0 y se añade al final de la cola. Cuando se añade una nueva página, se añade al final de la cola con R a 1.

*[[sol_7|Solución]]

;Criterio del reloj: Es una variante en la manera de implementar la 2ª oportunidad. Se emplea una lista circular. En lugar de eliminar y añadir elementos al final de la FIFO, mantenemos un puntero a la página siguiente a la última página víctima seleccionada.

*[[sol_reloj|Solución]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

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

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se puede implementar mediante una pila o cola situando la página más frecuentemente usada en la base de la pila o cabeza de la cola.La página víctima será la quede al final de la estructura. Otra variante de implementación es mediante un contador. Se incrementa un contador de uso por cada acceso, reseteándose si se reemplaza la página. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

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

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

== Sustitución por envejecimiento ==

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

*[[sol_10|Solución]]

= Implementaciones =

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

Criterios de reemplazo

2011-12-16T11:15:24Z

Ferguatol: /* Criterio de 2ª oportunidad */

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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

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

== Criterio de página óptima ==

Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

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

*[[sol_1|Solución]]

== Criterio de página pésima ==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

*[[sol_2|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Se trata también de un criterio teórico. Consiste en seleccionar una página al azar.

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

*[[sol_3|Solución]]

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

Ofrece dos bits para cada página:
* Bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* Bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, siempre se pone a 1 el bit R, y solo se toca M cuando se accede a escritura.

Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

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

Periódicamente se pone a cero el bit R.

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

Se trata de la unión del dos criterios, FIFO más NRU sin el bit M. Tampoco se pone R a 0 periódicamente. Cuando se añaden los procesos a los marcos, se añaden con el bit R a 1. Cuando se da un fallo de página, se recorre la lista de marcos hasta encontrar alguno que tenga R a 0. Si no encuentra ninguno que cumpla ésto, coloca todos los bits R a 0 y los pone en una cola. Se vuelve a iterar siguiendo el orden de la cola implementada. Es decir, cuando se encuenta un elemento con R a 0, se pone a 1 y se añade al final de la cola. Cuando se añade una nueva página, se añade al final de la cola con R a 1.

*[[sol_7|Solución]]

;Criterio del reloj: Es una variante en la manera de implementar la 2ª oportunidad. Se emplea una lista circular. En lugar de eliminar y añadir elementos al final de la FIFO, mantenemos un puntero a la página siguiente a la última página víctima seleccionada.

*[[sol_reloj|Solución]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

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

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se puede implementar mediante una pila o cola situando la página más frecuentemente usada en la base de la pila o cabeza de la cola.La página víctima será la quede al final de la estructura. Otra variante de implementación es mediante un contador. Se incrementa un contador de uso por cada acceso, reseteándose si se reemplaza la página. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

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

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

== Sustitución por envejecimiento ==

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

*[[sol_10|Solución]]

= Implementaciones =

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

Criterios de reemplazo

2011-12-16T11:03:00Z

Ferguatol: /* Criterio de 2ª oportunidad */ Explicación mejorada

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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

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

== Criterio de página óptima ==

Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

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

*[[sol_1|Solución]]

== Criterio de página pésima ==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

*[[sol_2|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Se trata también de un criterio teórico. Consiste en seleccionar una página al azar.

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

*[[sol_3|Solución]]

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

Ofrece dos bits para cada página:
* Bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* Bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, siempre se pone a 1 el bit R, y solo se toca M cuando se accede a escritura.

Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

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

Periódicamente se pone a cero el bit R.

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

Se trata de la unión del dos criterios, FIFO más NRU sin el bit M. Tampoco se pone R a 0 periódicamente. Cuando se añaden los procesos a los marcos, se añaden con el bit R a 1. Cuando se da un fallo de página, se recorre la lista de marcos hasta encontrar alguno que tenga R a 0. Si no encuentra ninguno que cumpla ésto, coloca todos los bits R a 0 y los pone en una cola. Se vuelve a iterar siguiendo el orden de la cola implementada. Cuando se añade una nueva página, se añade al final de la cola.

*[[sol_7|Solución]]

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

*[[sol_reloj|Solución]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

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

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se puede implementar mediante una pila o cola situando la página más frecuentemente usada en la base de la pila o cabeza de la cola.La página víctima será la quede al final de la estructura. Otra variante de implementación es mediante un contador. Se incrementa un contador de uso por cada acceso, reseteándose si se reemplaza la página. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

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

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

== Sustitución por envejecimiento ==

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

*[[sol_10|Solución]]

= Implementaciones =

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

Criterios de reemplazo

2011-12-16T10:47:20Z

Ferguatol: /* Criterio de 2ª oportunidad */

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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

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

== Criterio de página óptima ==

Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

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

*[[sol_1|Solución]]

== Criterio de página pésima ==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

*[[sol_2|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Se trata también de un criterio teórico. Consiste en seleccionar una página al azar.

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

*[[sol_3|Solución]]

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

Ofrece dos bits para cada página:
* Bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* Bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, siempre se pone a 1 el bit R, y solo se toca M cuando se accede a escritura.

Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

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

Periódicamente se pone a cero el bit R.

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

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

*[[sol_7|Solución]]

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

*[[sol_reloj|Solución]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

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

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se puede implementar mediante una pila o cola situando la página más frecuentemente usada en la base de la pila o cabeza de la cola.La página víctima será la quede al final de la estructura. Otra variante de implementación es mediante un contador. Se incrementa un contador de uso por cada acceso, reseteándose si se reemplaza la página. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

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

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

== Sustitución por envejecimiento ==

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

*[[sol_10|Solución]]

= Implementaciones =

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

Criterios de reemplazo

2011-12-16T10:46:30Z

Ferguatol: /* Criterio NRU (Not Recently Used) */

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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

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

== Criterio de página óptima ==

Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

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

*[[sol_1|Solución]]

== Criterio de página pésima ==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

*[[sol_2|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Se trata también de un criterio teórico. Consiste en seleccionar una página al azar.

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

*[[sol_3|Solución]]

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

Ofrece dos bits para cada página:
* Bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* Bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, siempre se pone a 1 el bit R, y solo se toca M cuando se accede a escritura.

Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

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

Periódicamente se pone a cero el bit R.

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

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

*[[sol_7|Solución]]

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

*[[sol_reloj|Solución]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

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

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se puede implementar mediante una pila o cola situando la página más frecuentemente usada en la base de la pila o cabeza de la cola.La página víctima será la quede al final de la estructura. Otra variante de implementación es mediante un contador. Se incrementa un contador de uso por cada acceso, reseteándose si se reemplaza la página. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

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

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

== Sustitución por envejecimiento ==

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

*[[sol_10|Solución]]

= Implementaciones =

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

Criterios de reemplazo

2011-12-16T10:38:05Z

Ferguatol: /* Criterio NRU (Not Recently Used) */ Pequeña aclaración de los Bits

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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

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

== Criterio de página óptima ==

Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

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

*[[sol_1|Solución]]

== Criterio de página pésima ==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

*[[sol_2|Solución]]

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

*[[sol_3|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Consiste en seleccionar una página al azar.

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

Ofrece dos bits para cada página:
* bit R : Se pone a 1 si la página ha sido usada (tanto para lectura como para escritura).
* bit M : Se pone a 1 si la página es modificada (escritura).

En resumen, siempre se pone a 1 el bit R, y solo se toca M cuando se accede a escritura.

Para seleccionar la página victima buscamos que cumpla uno de los siguientes criterios de bits si no hay ninguno se utiliza el siguiente:

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

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

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

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

*[[sol_7|Solución]]

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

*[[sol_reloj|Solución]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

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

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se puede implementar mediante una pila o cola situando la página más frecuentemente usada en la base de la pila o cabeza de la cola.La página víctima será la quede al final de la estructura. Otra variante de implementación es mediante un contador. Se incrementa un contador de uso por cada acceso, reseteándose si se reemplaza la página. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

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

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

== Sustitución por envejecimiento ==

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

*[[sol_10|Solución]]

= Implementaciones =

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

Criterios de reemplazo

2011-12-16T10:17:55Z

Ferguatol: /* Criterio de página óptima */

La evaluación se hace en base a la ''tasa de fallos de página'', que es el número de fallos de página entre el número de accesos totales a página, con lo que su valor oscila en el rango [0,1].

El fallo de página se produce cuando se accede a una posición de memoria que pertenece a una página de memoria que esta descargada en disco.

<math>tasa fallos pagina = \frac{total fallos de pagina}{total accesos a pagina}</math>

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

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

== Criterio de página óptima ==

Este es un criterio teórico que viene a establecer la cota inferior de la ''tasa de fallos de página''. Consiste en escoger la página que mayor tiempo va a tardar en utilizarse. Este es el mejor caso, pero se necesita conocimiento de futuro, de ahí que sea un criterio teórico.

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

*[[sol_1|Solución]]

== Criterio de página pésima ==

Este también es teórico y viene a establecer la cota superior de la ''tasa de fallos de página'', para ver lo peor que podría comportarse un criterio. Consiste en seleccionar la página que menor tiempo tardará en usarse.

*[[sol_2|Solución]]

== Criterio MRU('''M'''ost '''R'''ecently '''U'''sed) ==

Se selecciona la última página a la que se ha accedido. Podría implementarse con una LIFO por orden de acceso.

*[[sol_3|Solución]]

== Criterio de selección estocástica (aleatoria) ==

Consiste en seleccionar una página al azar.

== Criterio por orden de carga FIFO ==

Se selecciona la página que más tiempo lleva cargada en memoria principal. Se implementa con una FIFO por orden de carga, es decir, a medida que se cargan en memoria principal las páginas son añadidas a la cola. Un problema es que suele suceder que las páginas más usadas tienden a estar mucho tiempo en memoria principal y este criterio va contra eso.

*[[sol_5|Solución]]

== Criterio NRU ('''N'''ot '''R'''ecently '''U'''sed) ==

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

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

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

*[[sol_6|Solución]]

== Criterio de 2ª oportunidad ==

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

*[[sol_7|Solución]]

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

*[[sol_reloj|Solución]]

== Criterio LRU ('''L'''east '''R'''ecently '''U'''sed) ==

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

*[[sol_8|Solución]]

== Criterio LFU ('''L'''east '''F'''recuently '''U'''sed) ==

Se puede implementar mediante una pila o cola situando la página más frecuentemente usada en la base de la pila o cabeza de la cola.La página víctima será la quede al final de la estructura. Otra variante de implementación es mediante un contador. Se incrementa un contador de uso por cada acceso, reseteándose si se reemplaza la página. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

== Aproximación discreta LRU ==

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

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

== Sustitución por envejecimiento ==

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

*[[sol_10|Solución]]

= Implementaciones =

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

Ejercicios administración de memoria contigua

2011-12-13T13:12:14Z

Ferguatol: /* Ejercicio 1 */

=Ejercicios Clase=

==Ejercicio 1==
Ejercicio visto el martes 29 de Noviembre de 2011 en clase.

Dada la siguiente configuración de procesos:

| H0 | t | M |
---------------------
P1 | 0 | 4 | 3 |
P2 | 1 | 4 | 1 |
P3 | 2 | 5 | 2 |
P4 | 3 | 2 | 9 |
P5 | 4 | 1 | 15 |

Y la siguiente configuración de memoria:
_____
|_____| A = 4kB
|_____| B = 4kB
| |
|_____| C = 8kB
| |
| |
| | D = 16kB
|_____|

a) Determina el cronograma del Mejor Ajuste Estático [[solución Ejercicio clase Mejor Ajuste Estático|Ver solución]]

b) Determina el cronograma Primer ajuste [[Solución Ejercicio clase Primer Ajuste|Ver solución]]

c) Determina el cronograma del Mejor Ajuste Dinámico [[solución Ejercicio clase Mejor Ajuste Dinámico|Ver solución]]

==Ejercicio 2==
Segundo ejercicio visto el martes 29 de Noviembre de 2011 en clase.

Dada la siguiente configuración de procesos:

| H0 | t | M |
---------------------
P1 | 0 | 4 | 2 |
P2 | 0 | 4 | 1 |
P3 | 0 | 5 | 3 |
P4 | 0 | 2 | 8 |
P5 | 0 | 1 | 7 |

Y la siguiente configuración de memoria:
_______
|_____| A = 4kB
|_____| B = 4kB
| |
|_____| C = 8kB
| |
| |
| | D = 16kB
|_____|

Calcula los cronogramas tal y como se hizo en el ejercicio anterior.

PD: Ejercicio NO resuelto en clase.

Condiciones para el interbloqueo y estrategias de resolución

2011-12-08T14:40:14Z

Ferguatol: /* Condiciones para que se produzca interbloqueo */

== Condiciones para que se produzca interbloqueo ==

Según [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman], para que se pueda producir un interbloqueo se tienen que dar la siguientes cuatro condiciones:

* '''Exclusión mutua''': cada recurso está asignado a un único proceso de manera exclusiva.
* '''Retención y espera''': los procesos que tienen, en un momento dado, recursos asignados con anterioridad, pueden solicitar nuevos recursos y esperar a que se le asignen sin liberar antes alguno de los recursos que ya tenia asignados.

* '''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. Ni siquiera el sistema operativo puede expropiarselo.

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

Existen diversas estrategias frente a los interbloqueos, que se pueden agrupar en:

* Omisión
* Detección y recuperación
* Prevención
* Predicción

Que se detallan a continuación.

=== Omisión ===

Considera que la probabilidad de un interbloqueo es muy baja, de modo que se confía en que no se van a producir. Por sorprendente que parezca, los sistemas operativos modernos convencionales suelen aplicar esta estrategia. Por justificar la decisión de los fabricantes de sistemas operativos cabe incidir en que las estrategias de resolución y prevención de interbloqueos tienen un coste alto desde el punto de vista del consumo de recursos de procesamiento y memoria.

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

Esta estrategia permite la detección de una situación de interbloqueo y su consiguiente resolución. De entre las medidas de detección consideramos las siguientes:

* ''Grafo de relación recursos-procesos'': Consiste en la representación gráfica de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.

* ''Matrices de relación recursos-procesos'': Consiste en la representación matricial de los recursos asignados a los procesos y los recursos que dichos procesos requieren para finalizar su ejecución.

Tras la detección de un interbloqueo, se pueden aplicar algunas de las siguientes estrategias para resolverlo:

* ''Eliminación'': El sistema operativo selecciona a uno de los procesos que forma parte del interbloqueo y elimina el ciclo acabando con la ejecución de dicho proceso, si no es suficiente se eliminarán procesos hasta que se rompa el ciclo. La selección del proceso se realiza en base a un cierto criterio, por ejemplo, aquel proceso que lleve menos tiempo en ejecución o aquel que sea más voraz consumiendo recursos. Aunque parezca una medida drástica, es la empleada en sistemas operativos convencionales. Aplicar el criterio de selección y eliminar procesos cuando el número de procesos es relativamente bajo puede solucionar el interbloqueo, pero si se da un bloqueo de por ejemplo, centenares de procesos, es una situación prácticamente inmanejable.

* ''Apropiación temporal'': Se retira la asignación de un recurso a un proceso (durante el tiempo necesario) para deshacer el interbloqueo.Por ejemplo, supongamos que el recurso es una impresora: podríamos retirarle la asignación a un proceso P1 cuando este terminase de imprimir una página, asignarle la impresora a otro proceso P2 y volver a asignársela a P1 cuando P2 haya terminado su ejecución.

* ''Puntos de conformidad'' o ''checkpoints'': Consiste en tomar una imagen del estado del proceso, ya sea periódicamente o a instancia del propio proceso, de manera que si se produce un interbloqueo se vuelve a un estado de la ejecución anterior. Son muy poco usados ya que tienen un elevado coste en memoria y existe la posibilidad de que un proceso permanezca indefinidamente sin progresar.

=== Prevención ===

La prevención apunta a una serie de estrategias que eviten el interbloqueo. Concretamente, son cuatro las estrategias de prevención posibles en base a los principios que [http://en.wikipedia.org/wiki/Edward_G._Coffman,_Jr. Coffman] estableció como interbloqueo. Dichas estrategias son:

* ''Supresión de exclusión mutua'': un proceso no puede tener acceso exclusivo a un recurso.
* ''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. El aprovechamiento de recursos puede mejorarse mediante una programación más elaborada, dividiendo la ejecución del proceso en distintas fases y gestionando los recursos para cada una de ellas.
* ''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, y predice una posible situación de interbloqueo. Si detecta una alta probabilidad de que suceda, adopta una trayectoria de ejecución nueva para los procesos involucrados de manera que se garantice que no va a suceder un interbloqueo.

Mensajería

2011-12-04T11:03:09Z

Ferguatol:

Un mensaje es un contenedor que se emplea para intercambiar información entre dos o más procesos. Los mensajes tienen un cierto formato generalmente compuesto por una cabecera, que contiene información sobre la fuente y el destinatario, y un cuerpo, que contiene información específica.

Los mecanismos de mensajería se refiere al conjunto de funcionalidades que permiten al sistema operativo realizar la entrega de un mensaje a uno o varios procesos. Mediante dicho mecanismo también es posible resolver problemas de concurrencia.

Los sistemas operativos generalmente ofrecen dos llamadas al sistema para que un proceso pueda enviar y recibir mensajes:

* '''send(mensaje, destino)''': Para enviar un mensaje
* '''recv(mensaje)'''': Para recibir un mensaje

Cualquier proceso que necesita comprobar si tiene mensajes para ser procesados por él debe invocar la llamada al sistema '''recv'''.

== Formas de identificación ==

Para identificar la fuente y el destino de nuestro mensaje se pueden emplear dos estrategias.

=== Denominación Directa ===

En este caso se emplea un ID que permite identificar a la fuente y al destinatario de manera unívoca en el sistema, por ejemplo, el PID de un proceso. La denominación directa permite tres configuraciones:

* ''Unicast'', de manera que la comunicación sucede entre una fuente y un destinatario.
* ''Broadcast'', el emisor envía un mensaje a '''todos''' los procesos existentes en el sistema.
* ''Multicast'', el emisor envía un mensaje a un grupo de procesos, siendo un grupo un subconjunto de procesos existentes en el sistema. El sistema operativo debe ofrecer llamadas al sistema que permitan a los procesos crear grupos y suscribirse a ellos. Un proceso puede suscribirse a tantos grupos como le sea necesario.

El principal inconveniente de la denominación directa es que se pierde el mensaje si el destino no se encuentra.

=== Denominación Indirecta ===

Se emplea un elemento intermediario denominado ''buzón''. El sistema operativo ofrece llamadas al sistema que permiten la creación y destrucción de buzones, por ejemplo, '''CreateMailbox''' y '''DestroyMailbox'''. Una vez creado el buzón, se emplea éste para realizar la comunicación entre procesos.

El sistema operativo debe de comprobar que la identidad de la fuente de un mensaje es correcta, de lo contrario un proceso podría suplantar la identidad de otro.

== Formas de transmisión ==

Distinguimos tres formas de transmisión: Transmisión por copia, transmisión por referencia y transmisión por copia en caso de escritura.

=== Transmisión por copia ===

Si se emplea ''denominación directa'', al invocar el receptor la llamada ''recv'', el mensaje se copia de espacio de memoria del emisor al espacio de receptor. Esta forma de implementar la transmisión tiene un coste de orden lineal <math>O(n)</math>.

Si se emplea ''denominación indirecta'', al invocar ''send'' el emisor, el mensaje se copia del espacio de emisor al espacio del buzón, que se encuentra en el espacio de memoria del sistema operativo. Una vez que el receptor invoca ''receive'', se copia el mensaje al espacio de memoria que el receptor ha habilitado para almacenar el mensaje.

=== Transmisión por referencia ===

Es una mejora frente al mecanismo de transmisión por copia. Básicamente, en lugar de copiar el mensaje, lo que supone un coste de <math>O(n)</math>, se le devuelve al receptor una dirección de memoria en la que se encuentra el mensaje, lo que supone únicamente 4 u 8 bytes dependiendo del tamaño de palabra del procesador (si es de 32-bits o 64-bits).

Si se emplea junto a la '''denominación directa''', el sistema operativo le devuelve al receptor un puntero a la dirección en la que se encuentra el mensaje. Si el mensaje está en el espacio del emisor, son necesarios mecanismos explícitos de compartición de memoria entre procesos, ya que dos procesos cualquiera no comparten memoria. Si el mensaje está en el espacio del sistema operativo, éste debe ofrecer a los procesos mecanismos para acceder a su espacio de memoria-

Si se emplea junto a la '''denominación indirecta''', el emisor crea un mensaje en el espacio del sistema operativo y se le ofrece un puntero al receptor.

=== Transmisión por copia de escritura ===

El mensaje sólo se copia si se modifica por emisor o receptor.

== Formas de comunicación ==

* Comportamiento del emisor, '''send()'''
** ''Síncrona'': el proceso emisor que realiza el send() queda bloqueado hasta que el receptor llama a recv()
** ''Asíncrona'': suponemos una estructura de datos con capacidad de almacenamiento limitada, dependiente del proceso destinatario o en el buzón del SO. Al ser enviados, los mensajes irán encolándose para que el proceso receptor pueda gestionarlos cuando pueda. De esta manera se aumenta el rendimiento pero se requiere de políticas adicionales de tratamiento de los mensajes si la capacidad de almacenamiento de la estructura de datos se ve sobrepasada(PE, eliminación de mensajes, realocalización de memoria, etc..)

* Comportamiento del receptor, '''recv()'''
** ''Bloqueante'': una llamada a recv() sin mensajes a procesar pasa el proceso llamante a estado bloqueado. Un send() de otro proceso que añada un mensaje a la cola del proceso bloqueado hace que éste pase a estado preparado.
** ''No bloqueante'': una llamada a recv() sin mensajes a procesar devuelve un mensaje de error, pero la ejecución del proceso llamante continúa.

Entendemos por proceso llamante a aquel que hace uso de las llamadas send() y recv().

== Formato de los mensajes ==

=== Fijo ===

Los procesos acuerdan emplear un formato fijo para sus mensajes.

'''Ejemplo''': Simple Network Time Protocol.<ref> Véase http://tools.ietf.org/html/rfc4330, sección 4, Message Format.</ref>

1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|LI | VN |Mode | Stratum | Poll | Precision |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Delay |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Root Dispersion |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reference Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Reference Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Originate Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Receive Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| Transmit Timestamp (64) |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Key Identifier (optional) (32) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
| |
| Message Digest (optional) (128) |
| |
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

=== Variable ===

* Type-Length-Value

'''Ejemplo''': Usado en Netlink para la codificación de atributos de un mensaje.<ref>Ver Communicating between the kernel and user-space in Linux using Netlink Sockets (http://1984.lsi.us.es/~pablo/docs/spae.pdf)</ref>
{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
|+ align="center" style="background:DarkSlateBlue; color:white"|'''Type-Length-Value'''
! width="15 px" style="background:#efefef;" | 0
! width="15 px" style="background:#efefef;" | 1
! width="15 px" style="background:#efefef;" | 2
! width="15 px" style="background:#efefef;" | 3
! width="15 px" style="background:#efefef;" | 4
! width="15 px" style="background:#efefef;" | 5
! width="15 px" style="background:#efefef;" | 6
! width="15 px" style="background:#efefef;" | 7
! width="15 px" style="background:#efefef;" | 8
! width="15 px" style="background:#efefef;" | 9
! width="15 px" style="background:#efefef;" | 10
! width="15 px" style="background:#efefef;" | 11
! width="15 px" style="background:#efefef;" | 12
! width="15 px" style="background:#efefef;" | 13
! width="15 px" style="background:#efefef;" | 14
! width="15 px" style="background:#efefef;" | 15
! width="15 px" style="background:#efefef;" | 16
! width="15 px" style="background:#efefef;" | 17
! width="15 px" style="background:#efefef;" | 18
! width="15 px" style="background:#efefef;" | 19
! width="15 px" style="background:#efefef;" | 20
! width="15 px" style="background:#efefef;" | 21
! width="15 px" style="background:#efefef;" | 22
! width="15 px" style="background:#efefef;" | 23
! width="15 px" style="background:#efefef;" | 24
! width="15 px" style="background:#efefef;" | 25
! width="15 px" style="background:#efefef;" | 26
! width="15 px" style="background:#efefef;" | 27
! width="15 px" style="background:#efefef;" | 28
! width="15 px" style="background:#efefef;" | 29
! width="15 px" style="background:#efefef;" | 30
! width="15 px" style="background:#efefef;" | 31

|-
| colspan=16, align="center"| Length
| colspan=16, align="center"| Type
|-
| colspan=32, align="center"| Value
|}

* Text-based human-readable.

#Comma-Separated Value (CSV). http://en.wikipedia.org/wiki/Comma-separated_values
#Extensible Markup Language (XML). http://en.wikipedia.org/wiki/XML
#JavaScript Object Notation (JSON). http://en.wikipedia.org/wiki/JSON

=== Mixto ===

Los procesos acuerdan emplear mensaje con partes cuyo formato es fijo, como por ejemplo una cabecera inicial, seguido de partes de tamaño variable.

'''Ejemplo''': Internet Protocol (IPv4).<ref>Ver http://www.ietf.org/rfc/rfc791.txt, sección 3.1.</ref>

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Version| IHL |Type of Service| Total Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identification |Flags| Fragment Offset |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Time to Live | Protocol | Header Checksum |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Options | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/ /
/ Payload /
/ /
/////////////////////////////////////////////////////////////////

== Mensajería a través de la red ==

* Unicidad del destinatario
* Fiabilidad en la transmisión
* Formato de los datos (http://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Data/endian.html): Enviar un entero a través de la red puede ser un problema debido a la forma en el que se representan los datos en la memoria dependiente de la arquitectura. Por ejemplo, un PC con arquitectura Intel x86 emplea formato little-endian, mientras que un SPARC de Sun Microsystems (ahora Oracle) emplea big-endian.

** Little Endian: Bytes menos significativo al principio.

<source lang="c">
int main(void)
{
int a = 10, i;
char *p = &a;

for (i=0; i<sizeof(a); i++) {
printf("posición %d: %.2x\n", i, p[i]);
}
}
</source>

Muestra el siguiente resultado en un PC:

posición 0: 0a (n+3)
posición 1: 00 (n+2)
posición 2: 00 (n+1)
posición 3: 00 (n)

** Big Endian: Bytes menos significativo al final.

posición 0: 00 (n)
posición 1: 00 (n+1)
posición 2: 00 (n+2)
posición 3: 0a (n+3)

En Internet se sigue la convención de expresar datos en Big Endian, habría que hacer la conversión. Habría que usar '''ntohl''' (network to host long).

En little-endian, la implementación de ntohl es la siguiente:

#define __constant_ntohl(x) ___constant_swab32((__be32)(x)

Ver /usr/include/linux/byteorder/little_endian.h

mientras que en big-endian es:

#define __constant_ntohl(x) ((__u32)(__be32)(x))

Si empleamos formato textuales, como CSV, XML o JSON, que codifican la información en bytes, no tenemos este problema.

==Referencias==
<references/>

Monitores

2011-12-04T10:27:54Z

Ferguatol: /* Definición */

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 {

private int recursoCompartido;
private Semaforo s = 1;

public int get(void){
int ret; #1
down(s); #2
ret = recursoCompartido; #3
up(s); #4
return ret; #5
}

public void set(int valor){
down(s); #1
recursoCompartido = valor; #2
up(s); #3
}
}
</source>

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

== Ejemplo del funcionamiento de una clase monitor ==

Dado un cierto recurso compartido protegido por una clase monitor denominada ''RecursoCompartido'' con los siguientes métodos:

* '''get''', permite obtener el valor del recurso compartido, devuelve un entero.
* '''set''', permite establecer el valor del recurso compartido.

Suponga ya creada un objeto RecursoCompartido para dos hilos h1 y h2:

<source lang="java">
RecursoCompartido r = new RecursoCompartido();
</source>

Dichos hilos tienen el siguiente código:

* Lector (h1):

<source lang="java">
int valor;
for(int j=0; j<2; j++) { #1
valor=r.get(); #2
print(valor); #3
}
</source>

* Escritor (h2):

<source lang="java">
int i=0;
for(int j=0; j<2; j++) { #1
r.set(); #2
i++; #3
}
</source>

Suponiendo turno rotatorio estricto con quantum de 4 unidades de tiempo y que el planificador da paso en primer lugar al hilo h1. El cronograma con la representación de la ejecución sería el siguiente:

< = lanzamiento del proceso
> = finalización del proceso
x = indica que el proceso está asignado al procesador en ese momento.
B = el proceso pasa a estado bloqueado
P = el proceso pasa a estado preparado

Asignación del recurso procesador

| 1 |2.1|2.2|2.3| | |2.4|2.5| 3 | 1 | | | | |2.1|2.2|2.3|2.4| | | | |2.5| 3 | 1 | |
h1 <---|---|---|---P | |---|---|---|---P | | | |---|---|---|---| | | | |---|---|---> |
| | | | | 1 |2.1| | | | |2.2|2.3| 3 | 1 | | | | |2.1|2.2|2.3| 3 | | | | 1 |
h2 | | | | <---|---B P | | |---|---|---|---P | | | |---|---|---|---| | | |--->
----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Nota: Los números de la parte superior a los guiones, indican el número de instrucción que
se está ejecutando en dicho momento. En el caso de los 2.1, 2.2 y sucesivos se
refieren al número de instrucción qué internamente se ejecutan en el get() y set()
del monitor (Ver la implementación de la clase monitor de RecursoCompartido vista en clase).

En la página de [https://1984.lsi.us.es/wiki-ssoo/index.php/Discusi%C3%B3n:Monitores discusión] hay un ejemplo en java.

== Fuentes ==
<references/>

Monitores

2011-12-03T16:22:39Z

Ferguatol: /* Definición */

SO multiprogramables con particiones fijas

2011-12-02T10:26:20Z

Ferguatol: /* Mejor ajuste dinámico */ Ampliación de la definición

En la administración de memoria con particiones de tamaño fijo consideramos que la memoria se encuentra dividida en porciones fijas de diferente tamaño. La división se realizaría durante la instalación del sistema operativo, y para modificar el esquema de particionamiento necesitaríamos reiniciar el sistema para que surtan efecto los cambios. Por cada partición sólo puede haber un único proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

Esta aproximación tiene dos limitaciones importantes, que son:

* Si un proceso necesita más memoria que la partición más grande puede ofrecer, entonces éste no se puede ejecutar.
* Alto desperdicio de memoria, particularmente en el caso de que un procesos ocupe una partición de tamaño mayor a lo que necesita.

= Criterios de asignación =

Cuando se lanza un programa, el administrador de memoria tiene que decidir en qué partición de memoria va a cargar el proceso recién creado. Para ello se emplean diferentes criterios.

== Mejor ajuste estático ==

Se adjudica a cada proceso a la menor partición en la que quepa. Si la menor partición en la que cabe estuviera ocupada, dicho proceso tiene que esperar a que se libere. Esta estrategia evita el desperdicio de memoria. Sin embargo, puede retrasar la ejecución de un proceso estando libre otras particiones sin usarse. Este mecanismo se puede implementar con una cola por partición. El orden de complejidad computacional sería <math>O(1)</math>.

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M2
P3 | | < | | |---|---|---|---|---> | | | | | | | | | | P3-->M2
M3
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M3
M1
P5 | | | | < | | |---|---|---> | | | | | | | | | | P5-->M1
M4
P6 | | | | | <---|---> | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

=== Otro ejemplo ===

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:

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

== Primer ajuste ==

Igual que el anterior, sólo que nuestro proceso pasa a la primera partición libre en la que menor desperdicio de memoria se produzca. Por tanto, los procesos nunca esperan siempre que hay alguna partición libre. Complejidad: O(1)

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

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M3
P3 | | <---|---|---|---|---> | | | | | | | | | | | | | P3-->M3
M4
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M4
M2
P5 | | | | < |---|---|---> | | | | | | | | | | | | P5-->M2
M4
P6 | | | | | | | | <---|---> | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico ==

Se asigna el proceso a la partición en la que menor desperdicio produzca. Se itera sobre la lista de procesos pendientes de ser colocados en memoria (en lugar de aplicar orden de llegada como hace el mejor ajuste estático) para examinar cuáles cumplen dicho criterio.

El principal inconveniente de este criterio es que los procesos pequeños que van a producir más desperdicio, tienden a ser postergados indefinidamente. Complejidad: O(n).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 15 |
P5 | 1 | 3 | 3 |
P6 | 1 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

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

En el momento de lanzamiento hay que realizar la carga del código del proceso en memoria. Hay diferentes estrategias de colocación, que son:

*'''Montaje absoluto''': El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.

* '''Carga con reubicación''': Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método es más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.

* '''Reubicación dinámica''': Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En '''tiempo de ejecución''' se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.

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

* '''Bits de protección''' : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura

* '''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. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.

=Ejercicios Clase=

==Ejercicio 1==
Aquí está el ejercicio visto el martes 29 de Noviembre de 2011 en clase [[Ejercicio clase 291111|Ver Ejercicio]], junto con las soluciones también vistas en clase.

==Ejercicio 2==
Segundo ejercicio visto el martes 29 de Noviembre de 2011 en clase [[2º Ejercicio clase 29/11/11|Ver Ejercicio]]
(Por resolver).

SO multiprogramables con particiones fijas

2011-12-02T10:24:00Z

Ferguatol: /* Ejemplo */

En la administración de memoria con particiones de tamaño fijo consideramos que la memoria se encuentra dividida en porciones fijas de diferente tamaño. La división se realizaría durante la instalación del sistema operativo, y para modificar el esquema de particionamiento necesitaríamos reiniciar el sistema para que surtan efecto los cambios. Por cada partición sólo puede haber un único proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

Esta aproximación tiene dos limitaciones importantes, que son:

* Si un proceso necesita más memoria que la partición más grande puede ofrecer, entonces éste no se puede ejecutar.
* Alto desperdicio de memoria, particularmente en el caso de que un procesos ocupe una partición de tamaño mayor a lo que necesita.

= Criterios de asignación =

Cuando se lanza un programa, el administrador de memoria tiene que decidir en qué partición de memoria va a cargar el proceso recién creado. Para ello se emplean diferentes criterios.

== Mejor ajuste estático ==

Se adjudica a cada proceso a la menor partición en la que quepa. Si la menor partición en la que cabe estuviera ocupada, dicho proceso tiene que esperar a que se libere. Esta estrategia evita el desperdicio de memoria. Sin embargo, puede retrasar la ejecución de un proceso estando libre otras particiones sin usarse. Este mecanismo se puede implementar con una cola por partición. El orden de complejidad computacional sería <math>O(1)</math>.

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M2
P3 | | < | | |---|---|---|---|---> | | | | | | | | | | P3-->M2
M3
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M3
M1
P5 | | | | < | | |---|---|---> | | | | | | | | | | P5-->M1
M4
P6 | | | | | <---|---> | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

=== Otro ejemplo ===

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:

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

== Primer ajuste ==

Igual que el anterior, sólo que nuestro proceso pasa a la primera partición libre en la que menor desperdicio de memoria se produzca. Por tanto, los procesos nunca esperan siempre que hay alguna partición libre. Complejidad: O(1)

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

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M3
P3 | | <---|---|---|---|---> | | | | | | | | | | | | | P3-->M3
M4
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M4
M2
P5 | | | | < |---|---|---> | | | | | | | | | | | | P5-->M2
M4
P6 | | | | | | | | <---|---> | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico ==

Se asigna el proceso a la partición en la que menor desperdicio produzca. Se itera sobre la lista de procesos pendientes de ser colocados en memoria para examinar cuáles cumplen dicho criterio. Complejidad: O(n).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 15 |
P5 | 1 | 3 | 3 |
P6 | 1 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

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

En el momento de lanzamiento hay que realizar la carga del código del proceso en memoria. Hay diferentes estrategias de colocación, que son:

*'''Montaje absoluto''': El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.

* '''Carga con reubicación''': Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método es más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.

* '''Reubicación dinámica''': Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En '''tiempo de ejecución''' se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.

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

* '''Bits de protección''' : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura

* '''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. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.

=Ejercicios Clase=

==Ejercicio 1==
Aquí está el ejercicio visto el martes 29 de Noviembre de 2011 en clase [[Ejercicio clase 291111|Ver Ejercicio]], junto con las soluciones también vistas en clase.

==Ejercicio 2==
Segundo ejercicio visto el martes 29 de Noviembre de 2011 en clase [[2º Ejercicio clase 29/11/11|Ver Ejercicio]]
(Por resolver).

SO multiprogramables con particiones fijas

2011-12-02T10:23:54Z

Ferguatol: /* Ejemplo */

En la administración de memoria con particiones de tamaño fijo consideramos que la memoria se encuentra dividida en porciones fijas de diferente tamaño. La división se realizaría durante la instalación del sistema operativo, y para modificar el esquema de particionamiento necesitaríamos reiniciar el sistema para que surtan efecto los cambios. Por cada partición sólo puede haber un único proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

Esta aproximación tiene dos limitaciones importantes, que son:

* Si un proceso necesita más memoria que la partición más grande puede ofrecer, entonces éste no se puede ejecutar.
* Alto desperdicio de memoria, particularmente en el caso de que un procesos ocupe una partición de tamaño mayor a lo que necesita.

= Criterios de asignación =

Cuando se lanza un programa, el administrador de memoria tiene que decidir en qué partición de memoria va a cargar el proceso recién creado. Para ello se emplean diferentes criterios.

== Mejor ajuste estático ==

Se adjudica a cada proceso a la menor partición en la que quepa. Si la menor partición en la que cabe estuviera ocupada, dicho proceso tiene que esperar a que se libere. Esta estrategia evita el desperdicio de memoria. Sin embargo, puede retrasar la ejecución de un proceso estando libre otras particiones sin usarse. Este mecanismo se puede implementar con una cola por partición. El orden de complejidad computacional sería <math>O(1)</math>.

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m-
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M2
P3 | | < | | |---|---|---|---|---> | | | | | | | | | | P3-->M2
M3
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M3
M1
P5 | | | | < | | |---|---|---> | | | | | | | | | | P5-->M1
M4
P6 | | | | | <---|---> | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

=== Otro ejemplo ===

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:

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

== Primer ajuste ==

Igual que el anterior, sólo que nuestro proceso pasa a la primera partición libre en la que menor desperdicio de memoria se produzca. Por tanto, los procesos nunca esperan siempre que hay alguna partición libre. Complejidad: O(1)

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

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M3
P3 | | <---|---|---|---|---> | | | | | | | | | | | | | P3-->M3
M4
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M4
M2
P5 | | | | < |---|---|---> | | | | | | | | | | | | P5-->M2
M4
P6 | | | | | | | | <---|---> | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico ==

Se asigna el proceso a la partición en la que menor desperdicio produzca. Se itera sobre la lista de procesos pendientes de ser colocados en memoria para examinar cuáles cumplen dicho criterio. Complejidad: O(n).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 15 |
P5 | 1 | 3 | 3 |
P6 | 1 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

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

En el momento de lanzamiento hay que realizar la carga del código del proceso en memoria. Hay diferentes estrategias de colocación, que son:

*'''Montaje absoluto''': El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.

* '''Carga con reubicación''': Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método es más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.

* '''Reubicación dinámica''': Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En '''tiempo de ejecución''' se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.

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

* '''Bits de protección''' : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura

* '''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. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.

=Ejercicios Clase=

==Ejercicio 1==
Aquí está el ejercicio visto el martes 29 de Noviembre de 2011 en clase [[Ejercicio clase 291111|Ver Ejercicio]], junto con las soluciones también vistas en clase.

==Ejercicio 2==
Segundo ejercicio visto el martes 29 de Noviembre de 2011 en clase [[2º Ejercicio clase 29/11/11|Ver Ejercicio]]
(Por resolver).

SO multiprogramables con particiones fijas

2011-12-02T10:23:48Z

Ferguatol: /* Ejemplo */

En la administración de memoria con particiones de tamaño fijo consideramos que la memoria se encuentra dividida en porciones fijas de diferente tamaño. La división se realizaría durante la instalación del sistema operativo, y para modificar el esquema de particionamiento necesitaríamos reiniciar el sistema para que surtan efecto los cambios. Por cada partición sólo puede haber un único proceso. Por lo tanto, se pueden ejecutar tantos procesos como particiones haya.

Esta aproximación tiene dos limitaciones importantes, que son:

* Si un proceso necesita más memoria que la partición más grande puede ofrecer, entonces éste no se puede ejecutar.
* Alto desperdicio de memoria, particularmente en el caso de que un procesos ocupe una partición de tamaño mayor a lo que necesita.

= Criterios de asignación =

Cuando se lanza un programa, el administrador de memoria tiene que decidir en qué partición de memoria va a cargar el proceso recién creado. Para ello se emplean diferentes criterios.

== Mejor ajuste estático ==

Se adjudica a cada proceso a la menor partición en la que quepa. Si la menor partición en la que cabe estuviera ocupada, dicho proceso tiene que esperar a que se libere. Esta estrategia evita el desperdicio de memoria. Sin embargo, puede retrasar la ejecución de un proceso estando libre otras particiones sin usarse. Este mecanismo se puede implementar con una cola por partición. El orden de complejidad computacional sería <math>O(1)</math>.

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m-
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M2
P3 | | < | | |---|---|---|---|---> | | | | | | | | | | P3-->M2
M3
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M3
M1
P5 | | | | < | | |---|---|---> | | | | | | | | | | P5-->M1
M4
P6 | | | | | <---|---> | | | | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

=== Otro ejemplo ===

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:

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

== Primer ajuste ==

Igual que el anterior, sólo que nuestro proceso pasa a la primera partición libre en la que menor desperdicio de memoria se produzca. Por tanto, los procesos nunca esperan siempre que hay alguna partición libre. Complejidad: O(1)

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

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 1 | 4 | 7 |
P3 | 2 | 5 | 8 |
P4 | 3 | 5 | 15 |
P5 | 4 | 3 | 3 |
P6 | 5 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m-
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

La solución sería:

M1
P1 <---|---|---|---|---|---|---> | | | | | | | | | | | | | P1-->M1
M2
P2 | <---|---|---|---> | | | | | | | | | | | | | | | P2-->M2
M3
P3 | | <---|---|---|---|---> | | | | | | | | | | | | | P3-->M3
M4
P4 | | | <---|---|---|---|---> | | | | | | | | | | | | P4-->M4
M2
P5 | | | | < |---|---|---> | | | | | | | | | | | | P5-->M2
M4
P6 | | | | | | | | <---|---> | | | | | | | | | | P6-->M4
-----|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

== Mejor ajuste dinámico ==

Se asigna el proceso a la partición en la que menor desperdicio produzca. Se itera sobre la lista de procesos pendientes de ser colocados en memoria para examinar cuáles cumplen dicho criterio. Complejidad: O(n).

=== Ejemplo ===

Dada la siguiente configuración de procesos:

| H0 | t | m(P)|
---------------------
P1 | 0 | 7 | 2 |
P2 | 0 | 4 | 7 |
P3 | 0 | 5 | 8 |
P4 | 1 | 5 | 15 |
P5 | 1 | 3 | 3 |
P6 | 1 | 2 | 17 |

Y la siguiente configuración de memoria:
_______
|_____| M1 = 8 u.m.
|_____| M2 = 8 u.m.
| |
|_____| M3 = 16 u.m.
| |
| |
| | M4 = 32 u.m.
|_____|

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

En el momento de lanzamiento hay que realizar la carga del código del proceso en memoria. Hay diferentes estrategias de colocación, que son:

*'''Montaje absoluto''': El compilador genera un ejecutable que sólo pueda ser cargado en una cierta posición de memoria. Básicamente, las instrucciones de memoria emplean direccionamiento fijo. Se asigna una dirección de memoria fija en tiempo de compilación de manera que cuando se lance el programa tiene que cargarse obligatoriamente en la posición de memoria para la que fue compilada. Por tanto, se trata de un método poco flexible pues requiere la recompilación del programa para ejecutar el proceso en una posición de memoria diferente. Se emplea para la carga del ejecutable en el que se encuentra el sistema operativo nada más comenzar el arranque.

* '''Carga con reubicación''': Es un mecanismo más flexible al anterior. Básicamente, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Luego, en el momento de lanzamiento, se reajustan las instrucciones de acceso a memoria que hay en el código del proceso al cargarlo en una cierta partición. Este reajuste consiste en sumar a la dirección de memoria que hay en el código de cada instrucción de memoria la dirección de comienzo de la partición en la que se va a cargar el procesos. Aunque es un método es más flexible que el anterior, no permite migrar de una partición a otra una vez cargado el proceso en memoria.

* '''Reubicación dinámica''': Es el mecanismo más flexible de los tres. De nuevo, en tiempo de compilación se genera un ejecutable que supone que la posición de memoria de comienzo del proceso va a ser la dirección 0. Se supone la existencia de un registro en la arquitectura en el que se carga la posición de memoria de comienzo de la partición. En '''tiempo de ejecución''' se va a sumar a la posición de memoria a la que se quiere acceder la dirección de memoria del registro que contiene el lugar en el que comienza la partición. A diferencia de la carga con reubicación, permite la migración de un proceso de una partición a otra, para ello lo que hay que hacer es modificar el registro y mover el código del proceso a la nueva partición en la que se quiere colocar.

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

* '''Bits de protección''' : Se le asigna a cada zona/partición de la memoria principal una zona con información sobre el propietario y los permisos de lectura/escritura

* '''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. Los registros de posición inicial y final sólo pueden ser modificados en modo supervisor, por tanto, es el sistema operativo en que durante la conmutación de procesos establece el valor de estos registros.

=Ejercicios Clase=

==Ejercicio 1==
Aquí está el ejercicio visto el martes 29 de Noviembre de 2011 en clase [[Ejercicio clase 291111|Ver Ejercicio]], junto con las soluciones también vistas en clase.

==Ejercicio 2==
Segundo ejercicio visto el martes 29 de Noviembre de 2011 en clase [[2º Ejercicio clase 29/11/11|Ver Ejercicio]]
(Por resolver).