Wiki de Sistemas Operativos - Contribuciones del usuario [es]

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

2012-01-29T19:38:24Z

Jesgonbel: solución detallada

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

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

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

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

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

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

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

=Apartado c)=

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

[[Solución detallada de los ejercicios de paginación y segmentación]]

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

2012-01-29T19:37:27Z

Jesgonbel: explicacion detallada del ejercicio 2 del tema 10

Datos del problema:
* Tamaño de página= 8KB (expresado en Bytes es 2^13 B)
* Tamaño de palabra del procesador= 64 bits

Con estos datos podemos hallar la distribución de los bits de la dirección lógica:
Como máximo la dirección lógica tendrá 64 bits (el tamaño de palabra del procesador),
observando el tamaño de página expresado en bits hallamos que el numero de bits necesarios
para indicar el desplazamiento dentro de cada página es 13 (pues tiene 2^13 posiciones de memoria).
El resto de bits (51) se utiliza para representar los indicadores de página (luego se podrán
diferenciar 2^51 páginas distintas).

La dirección de memoria queda estructurada de la siguiente manera:

__________________________________________________
| | |
| identificador | Desplazamiento |
|_______________________________|__________________|
0 51 64

== Apartado A ==

Como hemos averiguado antes, en una misma tabla de páginas pueden haber hasta 2^51 páginas.
Si cada una de esas páginas pesa 128 bits (16 Bytes) el tamaño total de la tabla de páginas será:
16 * 2^51 = 2^55 Bytes

==Apartado B==
Conociendo el tamaño total de la tabla y el tamaño de las páginas podemos hallar el numero
de páginas que caben en una tabla como máximo:

2^55 / 2^13 = 2^42 páginas caben en una tabla (cabe notar que podríamos diferenciar hasta 2^51 paginas, algo mas de las que caben realmente)

== Apartado C==
Podemos calcular cuantas páginas ocupará un proceso, conocido el tamaño del proceso (7 MB, que equivale a 7*2^20 B) y el tamaño de las páginas
(8 KBytes, que equivale a 2^13 B). El cálculo es el siguiente:

7*2^20 / 2^13 = 7*2^7 páginas ocupadas (al igual que sus entradas en la tabla de páginas)

Solución ejercicio2Mejor Ajuste Dinámico

2012-01-29T17:49:00Z

Jesgonbel: duda

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

Revisado --[[Usuario:Pneira|Pneira]] 16:01 22 dic 2011 (UTC)

-Una duda: ¿Por qué se ejecuta antes P3 que P2? [[Usuario:jesgonbel|jesgonbel]]

Criterios de reemplazo

2012-01-28T18:12:59Z

Jesgonbel: /* Criterio de página óptima */ ampliació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.
La única forma de poner en práctica este criterio es, una vez se haya ejecutado un programa por primera vez, guardar el orden en el que ha ido pidiendo que se cargasen las páginas para que en la próxima ejecución de ese programa se determine la secuencia óptima de sustituciones, luego solo podría utilizarse con programas que se ejecutasen periódicamente y sin variaciones.

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-26T23:14:10Z

Jesgonbel:

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

EXT2

2012-01-22T17:23:28Z

Jesgonbel: Ampliación

Ext2 (extended second filesystem) es un sistema de ficheros originalmente diseñado para el kernel linux.
Comparado con FAT es un sistema eficiente, pero al igual que este está obsoleto para el tamaño de los ficheros actuales.

== Estructura ==

En Ext2, al contrario que en FAT, las entradas de la tabla de entrada de ficheros apuntan a un bloque especial llamado i-nodo el cual incluye información de tamaño, permisos, propietario y localización en disco, es decir, los metadatos del fichero.
Además de los metadatos los i-nodos contienen dos tipos de referencias a los bloques del fichero:
**'''10 referencias directas a bloques.'''

**'''3 tipos de referencias indirectas''': simple, doble y triple (en base al numero de tablas de bloques de cada referencia, desde 1 hasta 3).
Mediante estas referencias indirectas podemos aumentar el numero de bloques asignados a un fichero en el caso de que este no quepa en los
10 bloques referenciados directamente.

[[Archivo:Ext2-inode.gif]]

=Sucesores y expectativas=

Ext2 fue el sistema por defecto en distribuciones GNU/Linux durante los años 90, que evolucionó en ext3, el cual añadía journaling, manteniendo compatibilidad hacia atrás.

Desde 2008 es habitual el uso de ext4, que supone una reestructuración completa basada en árboles del sistema ext original.

En los últimos meses, las distribuciones más innovadoras están implementando la opcion de usar con una alta estabilidad/compatibilidad el sistema [http://en.wikipedia.org/wiki/Btrfs Btrfs].

FAT

2012-01-22T05:17:15Z

Jesgonbel: /* Estructura */ ampliación

El sistema de archivos FAT (File Allocation Table, tabla de asignación de archivos) utiliza junto a la tabla de entrada de ficheros una tabla, llamada tabla de asignación de ficheros (o tabla FAT).
FAT es un sistema de archivos sencillo, lo que lo hace muy popular en la gestión de discos y otras memorias secundarias externas y que sea aceptado por todos los sistemas operativos existentes (por lo que también es utilizado como mecanismo de intercambio de ficheros entre sistemas operativos distintos y coexistentes en el mismo equipo).
Sin embargo FAT tiene bastantes desventajas:
*Tiende a dejar fragmentos de los ficheros tras borrarlos, lo que con el tiempo ralentiza las operaciones L/E.
*No es redundante a fallos (ante fallos, como fallos eléctricos, puede dejar el sistema en un estado incongruente).
*Fue diseñado para ficheros de tamaño reducido.
*No soporta permisos de seguridad.

==Estructura==

Se dispone de la tabla de asignación de ficheros (File Allocation Table, de ahí las siglas FAT) en la que cada entrada de la tabla representa un bloque del disco. Cada entrada puede tener uno de los siguientes valores:

*Bloque libre: FREE
*Bloque defectuoso: BAD
*Último bloque de un archivo: EOF
*Cualquier otro número: bloque asignado, y el número es el número del siguiente bloque
*Entradas 0 y 1: reservadas

[[Archivo:Fat.png|Estructura FAT|center|border|600px]]

Nota: Si alguien quiere editar la imagen para mejorarla: [[https://docs.google.com/drawings/d/1CJlmPagvZl989yUOR41GBqZBL2afKt3gxxvYVkf57NU/edit?hl=en_US| Editar imagen]] --[[Usuario:Robertomartin|Robertomartin]] 12:19 6 jun 2011 (UTC)

==FAT 32==

FAT32 fue la respuesta para superar el límite de tamaño de FAT16 al mismo tiempo que se mantenía la compatibilidad con MS-DOS en modo real. Microsoft decidió implementar una nueva generación de FAT utilizando direcciones de cluster[http://es.wikipedia.org/wiki/Cl%C3%BAster_%28sistema_de_archivos%29] de 32 bits (aunque sólo 28 de esos bits se utilizaban realmente).

En teoría, esto debería permitir aproximadamente 268.435.538 clusters, arrojando tamaños de almacenamiento cercanos a los ocho terabytes. Sin embargo, debido a limitaciones en la utilidad ScanDisk de Microsoft, no se permite que FAT32 crezca más allá de 4.177.920 clusters por partición (es decir, unos 124 gigabytes). Posteriormente, Windows 2000 y XP situaron el límite de FAT32 en los 32 gigabytes. Microsoft afirma que es una decisión de diseño, sin embargo, es capaz de leer particiones mayores creadas por otros medios.

FAT32 apareció por primera vez en Windows 95 OSR2. Era necesario reformatear para usar las ventajas de FAT32. Curiosamente, DriveSpace 3 (incluido con Windows 95 y 98) no lo soportaba. Windows 98 incorporó una herramienta para convertir de FAT16 a FAT32 sin pérdida de los datos. Este soporte no estuvo disponible en la línea empresarial hasta Windows 2000.

El '''tamaño máximo de un archivo en FAT32''' es 4 gigabytes (2^32−1 bytes), lo que resulta engorroso para aplicaciones de captura y edición de video, ya que los archivos generados por éstas superan fácilmente ese límite.

http://www.pjrc.com/tech/8051/ide/fat32.html

Introducción en la administración de archivos

2012-01-22T05:06:52Z

Jesgonbel: /* Tabla de entrada de ficheros */ Cambio de ASCII a imagen

= 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 instalación. 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.

Archivo:Directorios2.png

2012-01-22T05:05:53Z

Jesgonbel: Imagen ilustrativa para la tabla de entrada de ficheros

Imagen ilustrativa para la tabla de entrada de ficheros

Archivo:DiseñoModularSVG.svg

2012-01-22T04:46:46Z

Jesgonbel: subió una nueva versión de «Archivo:DiseñoModularSVG.svg»

Imagen del diseño modular de E/S en version SVG.

Archivo:DiseñoModularSVG.svg

2012-01-22T04:04:00Z

Jesgonbel: subió una nueva versión de «Archivo:DiseñoModularSVG.svg»: Resubida de la imagen por problemas con la wiki

Imagen del diseño modular de E/S en version SVG.

Archivo:DiseñoModularSVG.svg

2012-01-22T04:03:05Z

Jesgonbel: Imagen del diseño modular de E/S en version SVG.

Imagen del diseño modular de E/S en version SVG.

Introducción en la administración de archivos

2012-01-22T02:52:36Z

Jesgonbel: /* Fichero */ Referencia al concepto de metadatos

= 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 instalación. 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.

raíz
. ,-------> .
.. , ..
d1 ------ f1
d2 ------, f2
\ ,------> .
-----------------> . , ..
.. , f3
d3 -------- f4

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-22T02:39:34Z

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

= 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 instalación. 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 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.

raíz
. ,-------> .
.. , ..
d1 ------ f1
d2 ------, f2
\ ,------> .
-----------------> . , ..
.. , f3
d3 -------- f4

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.

Diseño modular E/S

2012-01-17T02:03:37Z

Jesgonbel: Incluir imagenes

La idea clave de esta arquitectura en capas es hacer independiente al proceso del dispositivo. Por lo general, en ingeniería del software, la independencia del proveedor es una propiedad muy deseable.

[[Archivo:DiseñomodularES.jpg‎]]

Esta abstracción permite:

* Hacer a los procesos independientes de los dispositivos de E/S. Esto es deseable en cuanto a que el fabricante del dispositivo podría dejar de fabricar el dispositivo, por tanto, el proceso tendría que ser reescrito para soportar el nuevo dispositivo. De igual manera, si el dispositivo para el que está diseñado el proceso que conoce los detalles de bajo nivel no está disponible en el sistema, nuestro proceso quedaría inservible.
* Forzar a que un proceso tenga que pasar por el sistema operativo, que es quien garantiza que el reparto de recursos es equitativo. Si un proceso dispone de acceso directo a un dispositivo, podría adoptar un comportamiento ''abusón'' de manera que no permitiera a otros procesos emplearlo.

Archivo:DiseñomodularES.jpg

2012-01-17T02:02:45Z

Jesgonbel: Imagen del diseño modular de E/S (para sustituir al dibujo ASCII)

Imagen del diseño modular de E/S (para sustituir al dibujo ASCII)

Discos Magnéticos

2012-01-14T01:53:19Z

Jesgonbel: /* Partes importantes de los discos magnéticos: */ añadido concepto de clúster

== Arquitectura de los discos magnéticos ==

Los discos magnéticos están formados por varios discos (desde 2 hasta 7) de material magnético montados sobre el mismo eje, los cuales se mantienen girando a una velocidad constante. Estos discos están recorridos, cada uno, por 2 cabezales magnéticos que no llegan a tocar el disco (están separados unos 3 nanómetros debido a una delgada capa de aire formada por la rotación del disco, de hecho si lo tocan se produce un error conocido como aterrizaje del cabezal) y que leen y escriben datos en el disco creando puntos de campo magnético.

En esta imagen se muestran los componentes de un disco duro magnético:

[[Archivo:componentes_HD.png]]

=Partes importantes de los discos magnéticos:=

*Cabezal: sección que se mueve por un plato para leer la información.
*Pista (track): zona a la que accede el cabezal si este se queda fijo en una posición y el disco sigue girando. Hay que tener en cuenta que las pistas más cercanas al centro del disco son de menor tamaño.
*Sector: es un punto concreto de una pista.
*Cilindro: Conjunto de sectores a los que los cabezales pueden acceder en un momento.
*[http://es.wikipedia.org/wiki/Cl%C3%BAster_(sistema_de_archivos), Clúster]: Conjunto de sectores contiguos que forman la unidad más pequeña de almacenamiento en disco.

[[Archivo:Sin_título.png]][[Archivo:Estructura_disco.png|Estructura de un disco óptico|right]]

=Prestaciones a tener en cuenta de los discos duros magnéticos:=

*Capacidad
*rpm (revoluciones por minuto)
*Tiempo de arranque del motor
*Tiempo de accesos (lectura/escritura):
**Tiempo de búsqueda: tiempo en desplazarse de una pista a otra.
**Demora de rotación: tiempo en desplazarse de un sector a otro.
**Tiempo de transmisión: tiempo desde la lectura de los datos hasta que pasa la información al gestor de dispositivo correspondiente.

= Otros recursos =
http://www.youtube.com/watch?v=Wiy_eHdj8kg&feature=player_embedded

Discos Magnéticos

2012-01-14T01:45:49Z

Jesgonbel: corrección de erratas

== Arquitectura de los discos magnéticos ==

Los discos magnéticos están formados por varios discos (desde 2 hasta 7) de material magnético montados sobre el mismo eje, los cuales se mantienen girando a una velocidad constante. Estos discos están recorridos, cada uno, por 2 cabezales magnéticos que no llegan a tocar el disco (están separados unos 3 nanómetros debido a una delgada capa de aire formada por la rotación del disco, de hecho si lo tocan se produce un error conocido como aterrizaje del cabezal) y que leen y escriben datos en el disco creando puntos de campo magnético.

En esta imagen se muestran los componentes de un disco duro magnético:

[[Archivo:componentes_HD.png]]

=Partes importantes de los discos magnéticos:=

*Cabezal: sección que se mueve por un plato para leer la información.
*Pista (track): zona a la que accede el cabezal si este se queda fijo en una posición y el disco sigue girando. Hay que tener en cuenta que las pistas más cercanas al centro del disco son de menor tamaño.
*Sector: es un punto concreto de una pista.
*Cilindro: Conjunto de sectores a los que los cabezales pueden acceder en un momento.

[[Archivo:Sin_título.png]][[Archivo:Estructura_disco.png|Estructura de un disco óptico|right]]

=Prestaciones a tener en cuenta de los discos duros magnéticos:=

*Capacidad
*rpm (revoluciones por minuto)
*Tiempo de arranque del motor
*Tiempo de accesos (lectura/escritura):
**Tiempo de búsqueda: tiempo en desplazarse de una pista a otra.
**Demora de rotación: tiempo en desplazarse de un sector a otro.
**Tiempo de transmisión: tiempo desde la lectura de los datos hasta que pasa la información al gestor de dispositivo correspondiente.

= Otros recursos =
http://www.youtube.com/watch?v=Wiy_eHdj8kg&feature=player_embedded

Discos Magnéticos

2012-01-14T01:43:47Z

Jesgonbel: Discos magnéticos: ampliación.

== Arquitectura de los discos magnéticos ==

Los discos magnéticos están formados por varios discos de material magnético montados sobre el mismo eje, los cuales se mantienen girando a una velocidad constante. Estos discos están recorridos, cada uno, por 2 cabezales magnéticos que no llegan a tocar el disco (están separados unos 3 nanómetros debido a una delgada capa de aire formada por la rotación del disco, de hecho si lo tocan se produce un error conocido como aterrizaje del cabezal) y que leen y escriben datos en el disco creando puntos de campo magnético.

En esta imagen se muestran los componentes de un disco duro magnético:

[[Archivo:componentes_HD.png]]

=Partes importantes de los discos magnéticos:=

*Cabezal: sección que se mueve por un plato para leer la información.
*Pista (track): zona a la que accede el cabezal si este se queda fijo en una posición y el disco sigue girando. Hay que tener en cuenta que las pistas más cercanas al centro del disco son de menor tamaño.
*Sector: es un punto concreto de una pista.
*Cilindro: Conjunto de sectores a los que los cabezales pueden acceder en un momento.

[[Archivo:Sin_título.png]][[Archivo:Estructura_disco.png|Estructura de un disco óptico|right]]

=Prestaciones a tener en cuenta de los discos duros magnéticos:=

*Capacidad
*rpm (revoluciones por minuto)
*Tiempo de arranque del motor
*Tiempo de accesos (lectura/escritura):
**Tiempo de búsqueda: tiempo en desplazarse de una pista a otra.
**Demora de rotación: tiempo en desplazarse de un sector a otro.
**Tiempo de transmisión: tiempo desde la lectura de los datos hasta que pasa la información al gestor de dispositivo correspondiente.

= Otros recursos =
http://www.youtube.com/watch?v=Wiy_eHdj8kg&feature=player_embedded

Archivo:Componentes HD.png

2012-01-14T01:38:18Z

Jesgonbel: partes de un disco magnético.

partes de un disco magnético.

Paginación

2012-01-06T04:38:31Z

Jesgonbel: /* Definición */ corrección de erratas

=Definición=
La paginación es una estrategia de organización de la memoria similar a la segmentación pero con ciertas diferencias, por ejemplo la memoria se considera un espacio continuo dividido en porciones de igual tamaño fijo (frente a la división en segmentos de tamaño variable de la segmentación), a dichas porciones se las conoce como marcos de pagina o simplemente como páginas.
Las páginas están definidas por un número de página, que identifica de forma única a cada página (dentro del espacio de memoria de un proceso). Cada página se asigna en exclusividad a un proceso.

=Funcionamiento=

Desde el punto de vista de la paginación la traducción de las direcciones de memoria se basa en dos conceptos:

1. El dispositivo traductor divide las direcciones lógicas en 2 partes de la siguiente forma: los n bits mas significativos identifican la página mientras que el resto identifica el desplazamiento.

2. Cuando el traductor dinámico de páginas recibe, en una dirección lógica, un numero de página este examina una tabla (llamada tabla de páginas) en la cual se relacionan las páginas lógicas con las páginas físicas y obtiene la dirección real de la siguiente forma:

[[Archivo:Paginas.png]]

Al igual que en la segmentación al intentar acceder a una página ausente se produce un fallo (llamado en este caso '''fallo de página''').

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

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

El dispositivo de traducción de direcciones paginadas debe ser un dispositivo muy rápido, ya que se usa con cada acceso a memoria que se realiza.El tamaño de la tabla de páginas es uno de los aspectos que mas influye en el diseño del dispositivo e incluso en la organización de la propia tabla. Otro aspecto relevante es la localización de dicha tabla, la cual puede encontrarse en el traductor o guardada en memoria:
*'''Tabla de páginas en el traductor:'''

Se usa en equipos cuyo espacio de direcciones es de pocas páginas.
El dispositivo de traducción contiene un conjunto de registros organizados como una memoria en los cuales almacena la tabla de páginas.
Dicha página debe sustituirse (lo cual aumenta el tiempo de conmutación) en dos situaciones distintas: al cambiar de proceso y al cambiar del proceso al ss.oo. (en este caso se reduce el tiempo de conmutación utilizando dos tablas separadas, una para los procesos y otra para el ss.oo., las cuales se utilizan dependiendo del modo de uso de la cpu, supervisor o usuario).

*'''Tabla de páginas en memoria:'''

Se usa en equipos con mucha memoria, en los cuales el numero de páginas puede llegar a ser muy alto con lo que el tiempo necesario para cargar las páginas en el traductor es demasiado alto.
La tabla de páginas es guardada en la memoria principal y el dispositivo traductor tiene la dirección de comienzo y el tamaño de la tabla, debido a que la tabla esta en la memoria principal se necesita, por cada acceso a memoria, un acceso a memoria adicional para obtener el numero de página física asociado a la página lógica. Para mantener un tiempo de acceso aceptable se establece una memoria asociativa que conserva las parejas página lógica-página física utilizadas recientemente.

También hay dispositivos traductores que no utilizan tablas de páginas, buscan directamente la información en una memoria asociativa.

==Tabla de páginas multinivel==
El objetivo es paginar la tabla de páginas lo que permite que esta no esté cargada completa en memoria y que no ocupe direcciones consecutivas.
En los ss.oo. con tablas de páginas multinivel los número de página se dividen en dos partes: los bits más significativos indican el directorio de páginas correspondiente y con los bits menos significativos el índice del directorio en el que se encuentra la página buscada:

[[Archivo:PaginacionMultinivel.jpg‎ ]]

==Elementos de administración==
La administración es sencilla ya que todas las porciones de memoria son de igual tamaño (se limita a comprobar si hay suficientes marcos libres para ejecutar el proceso).

Se pueden usar:

*Tabla o mapa de bits: ocupa poca memoria, de orden O(1)
*2 listas encadenadas(colas): páginas libres, páginas ocupadas. Tiene mejor rendimiento (aunque ocupa más memoria), de orden O(1)
*Una tabla con una entrada para cada marco, esta contiene un 0 si el marco está libre o el numero de referencia al proceso si el marco esta adjudicado.

Paginación

2012-01-06T04:07:36Z

Jesgonbel: Paginación: ampliación de contenido.

=Definición=
La paginación es una estrategia de organización de la memoria similar a la segmentación pero con ciertas diferencias, por ejemplo la memoria se considera un espacio continuo divide en porciones de igual tamaño fijo (frente a la división en segmentos de tamaño variable de la segmentación), a dichas porciones se las conoce como marcos de pagina o simplemente como páginas.
Las páginas están definidas por un número de página, que identifica de forma única a cada página (dentro del espacio de memoria de un proceso). Cada página se asigna en exclusividad a un proceso.

=Funcionamiento=

Desde el punto de vista de la paginación la traducción de las direcciones de memoria se basa en dos conceptos:

1. El dispositivo traductor divide las direcciones lógicas en 2 partes de la siguiente forma: los n bits mas significativos identifican la página mientras que el resto identifica el desplazamiento.

2. Cuando el traductor dinámico de páginas recibe, en una dirección lógica, un numero de página este examina una tabla (llamada tabla de páginas) en la cual se relacionan las páginas lógicas con las páginas físicas y obtiene la dirección real de la siguiente forma:

[[Archivo:Paginas.png]]

Al igual que en la segmentación al intentar acceder a una página ausente se produce un fallo (llamado en este caso '''fallo de página''').

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

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

El dispositivo de traducción de direcciones paginadas debe ser un dispositivo muy rápido, ya que se usa con cada acceso a memoria que se realiza.El tamaño de la tabla de páginas es uno de los aspectos que mas influye en el diseño del dispositivo e incluso en la organización de la propia tabla. Otro aspecto relevante es la localización de dicha tabla, la cual puede encontrarse en el traductor o guardada en memoria:
*'''Tabla de páginas en el traductor:'''

Se usa en equipos cuyo espacio de direcciones es de pocas páginas.
El dispositivo de traducción contiene un conjunto de registros organizados como una memoria en los cuales almacena la tabla de páginas.
Dicha página debe sustituirse (lo cual aumenta el tiempo de conmutación) en dos situaciones distintas: al cambiar de proceso y al cambiar del proceso al ss.oo. (en este caso se reduce el tiempo de conmutación utilizando dos tablas separadas, una para los procesos y otra para el ss.oo., las cuales se utilizan dependiendo del modo de uso de la cpu, supervisor o usuario).

*'''Tabla de páginas en memoria:'''

Se usa en equipos con mucha memoria, en los cuales el numero de páginas puede llegar a ser muy alto con lo que el tiempo necesario para cargar las páginas en el traductor es demasiado alto.
La tabla de páginas es guardada en la memoria principal y el dispositivo traductor tiene la dirección de comienzo y el tamaño de la tabla, debido a que la tabla esta en la memoria principal se necesita, por cada acceso a memoria, un acceso a memoria adicional para obtener el numero de página física asociado a la página lógica. Para mantener un tiempo de acceso aceptable se establece una memoria asociativa que conserva las parejas página lógica-página física utilizadas recientemente.

También hay dispositivos traductores que no utilizan tablas de páginas, buscan directamente la información en una memoria asociativa.

==Tabla de páginas multinivel==
El objetivo es paginar la tabla de páginas lo que permite que esta no esté cargada completa en memoria y que no ocupe direcciones consecutivas.
En los ss.oo. con tablas de páginas multinivel los número de página se dividen en dos partes: los bits más significativos indican el directorio de páginas correspondiente y con los bits menos significativos el índice del directorio en el que se encuentra la página buscada:

[[Archivo:PaginacionMultinivel.jpg‎ ]]

==Elementos de administración==
La administración es sencilla ya que todas las porciones de memoria son de igual tamaño (se limita a comprobar si hay suficientes marcos libres para ejecutar el proceso).

Se pueden usar:

*Tabla o mapa de bits: ocupa poca memoria, de orden O(1)
*2 listas encadenadas(colas): páginas libres, páginas ocupadas. Tiene mejor rendimiento (aunque ocupa más memoria), de orden O(1)
*Una tabla con una entrada para cada marco, esta contiene un 0 si el marco está libre o el numero de referencia al proceso si el marco esta adjudicado.

Archivo:PaginacionMultinivel.jpg

2012-01-06T03:51:40Z

Jesgonbel: Procedimiento para obtener la página física usando tablas de páginas multinivel.

Procedimiento para obtener la página física usando tablas de páginas multinivel.

Segmentación

2012-01-06T02:00:58Z

Jesgonbel: /* Enlazado estático VS enlazado dinámico: */ ampliación.

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

=Funcionamiento=

[[Archivo:Segmentos.png|725px]]

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

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

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

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

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

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

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

*No se redimensionan.

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

=Mecanismos=
Los diferentes mecanismos que nos ofrece la segmentación de memoria son los siguientes.
==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio (ver [[Intro | Memoria virtual]]).

Esta zona de intercambio puede ser:

* Un lugar fijo en el disco (Linux, Unix). El administrador de memoria decide qué segmento se va a descargar

* Un fichero oculto de tamaño fijo o variable dependiendo de la configuracion dada por el usuario (Windows).

==Enlace dinámico==
Uso de llamadas a funciones que están en disco.

El uso de esta técnica nos aporta ventajas como reducir el trabajo del montador de enlaces (y por tanto el tiempo necesario para sus operaciones) además de que podemos tener referencias a funciones o bibliotecas que no estén en memoria principal (permite ir cargando bajo demanda los segmentos que contengan el código necesario).

=== Enlazado estático VS enlazado dinámico: ===

Los montadores de enlaces convencionales (estáticos) deben enlazar en tiempo de compilación todos los módulos, segmentos y referencias de un
programa para completar sus instrucciones (si el número de instrucciones es muy elevado la cantidad de trabajo del montador será enorme)
mientras que los montadores de enlaces dinámicos realizarán el enlazado durante la ejecución o durante la carga del programa.

*'''Pros y contras:'''
La ventaja de usar enlaces dinámicos es que los programas serán más livianos, aunque se crea una cierta dependencia del programa el cual no
funcionará correctamente si se modifica algún módulo, segmento o referencia (en windows los errores debidos a actualizaciones de librerías
dinámicas .dll son bastante comunes [http://www.http://es.wikipedia.org/wiki/Infierno_de_las_DLL]). Por otro lado la ventaja de usar enlaces estáticos es que los programas son totalmente independientes,
lo que facilita su distribución.

*'''Enlazado dinámico durante la carga:'''
En los ss.oo. de este tipo los ejecutables incluyen una relación de los objetos externos que necesita. Al cargar el programa se buscan los
segmentos ya cargados y los que se necesitan y se resuelven los enlaces.

*'''Enlazado dinámino durante la ejecución:'''
El enlazado dinámico durante la ejecución se basa en emplear referencias indirectas (la referencia apunta a una dirección de memoria la cual
contiene la referencia al objeto) y en dotar al procesador de un tipo especial de interrupción llamado excepción de enlace.
El compilador establece de forma indirecta las referencias a elementos de otros segmentos, utilizando como objeto intermedio un puntero con el
bit de excepción de enlace activado y que apunta hacia el identificador del elemento referido. Cuando se alcanza una referencia de este tipo
se lanza la excepción de enlace y el ss.oo. la atrapa el cual busca el objeto y localiza su dirección segmentada, con esa información el
ss.oo. modifica el puntero asignandole la dirección hallada y desactivando el bit de excepción (el enlace especial se reduce a una referencia
indirecta normal).
Para facilitar la ejecución las referencias a un mismo objeto se concentran en un único puntero (así la excepción de enlace se producirá
una sola vez) y todos los enlaces se concentran en un segmento especial llamado segmento de enlace.

Segmentación

2012-01-06T01:44:14Z

Jesgonbel: /* Enlazado estático VS enlazado dinámico: */ corrección de erratas.

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

=Funcionamiento=

[[Archivo:Segmentos.png|725px]]

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

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

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

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

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

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

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

*No se redimensionan.

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

=Mecanismos=
Los diferentes mecanismos que nos ofrece la segmentación de memoria son los siguientes.
==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio (ver [[Intro | Memoria virtual]]).

Esta zona de intercambio puede ser:

* Un lugar fijo en el disco (Linux, Unix). El administrador de memoria decide qué segmento se va a descargar

* Un fichero oculto de tamaño fijo o variable dependiendo de la configuracion dada por el usuario (Windows).

==Enlace dinámico==
Uso de llamadas a funciones que están en disco.

El uso de esta técnica nos aporta ventajas como reducir el trabajo del montador de enlaces (y por tanto el tiempo necesario para sus operaciones) además de que podemos tener referencias a funciones o bibliotecas que no estén en memoria principal (permite ir cargando bajo demanda los segmentos que contengan el código necesario).

=== Enlazado estático VS enlazado dinámico: ===

Los montadores de enlaces convencionales (estáticos) deben enlazar en tiempo de compilación todos los módulos, segmentos y referencias de un
programa para completar sus instrucciones (si el número de instrucciones es muy elevado la cantidad de trabajo del montador será enorme)
mientras que los montadores de enlaces dinámicos realizarán el enlazado durante la ejecución o durante la carga del programa.

*'''Pros y contras:'''
La ventaja de usar enlaces dinámicos es que los programas serán más livianos, aunque se crea una cierta dependencia del programa el cual no
funcionará correctamente si se modifica algún módulo, segmento o referencia (en windows los errores debidos a actualizaciones de librerías
dinámicas .dll son bastante comunes). Por otro lado la ventaja de usar enlaces estáticos es que los programas son totalmente independientes,
lo que facilita su distribución.

*'''Enlazado dinámico durante la carga:'''
En los ss.oo. de este tipo los ejecutables incluyen una relación de los objetos externos que necesita. Al cargar el programa se buscan los
segmentos ya cargados y los que se necesitan y se resuelven los enlaces.

*'''Enlazado dinámino durante la ejecución:'''
El enlazado dinámico durante la ejecución se basa en emplear referencias indirectas (la referencia apunta a una dirección de memoria la cual
contiene la referencia al objeto) y en dotar al procesador de un tipo especial de interrupción llamado excepción de enlace.
El compilador establece de forma indirecta las referencias a elementos de otros segmentos, utilizando como objeto intermedio un puntero con el
bit de excepción de enlace activado y que apunta hacia el identificador del elemento referido. Cuando se alcanza una referencia de este tipo
se lanza la excepción de enlace y el ss.oo. la atrapa el cual busca el objeto y localiza su dirección segmentada, con esa información el
ss.oo. modifica el puntero asignandole la dirección hallada y desactivando el bit de excepción (el enlace especial se reduce a una referencia
indirecta normal).
Para facilitar la ejecución las referencias a un mismo objeto se concentran en un único puntero (así la excepción de enlace se producirá
una sola vez) y todos los enlaces se concentran en un segmento especial llamado segmento de enlace.

Segmentación

2012-01-06T01:33:24Z

Jesgonbel: /* Enlace dinámico */ ampliación contenido.

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

=Funcionamiento=

[[Archivo:Segmentos.png|725px]]

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

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

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

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

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

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

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

*No se redimensionan.

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

=Mecanismos=
Los diferentes mecanismos que nos ofrece la segmentación de memoria son los siguientes.
==Carga de segmentos a petición==
Es un mecanismo que permite a un proceso no disponer de todos sus segmentos en memoria principal, se pueden descargar a disco (en la zona de intercambio o swap) segmentos en base a un cierto criterio (ver [[Intro | Memoria virtual]]).

Esta zona de intercambio puede ser:

* Un lugar fijo en el disco (Linux, Unix). El administrador de memoria decide qué segmento se va a descargar

* Un fichero oculto de tamaño fijo o variable dependiendo de la configuracion dada por el usuario (Windows).

==Enlace dinámico==
Uso de llamadas a funciones que están en disco.

El uso de esta técnica nos aporta ventajas como reducir el trabajo del montador de enlaces (y por tanto el tiempo necesario para sus operaciones) además de que podemos tener referencias a funciones o bibliotecas que no estén en memoria principal (permite ir cargando bajo demanda los segmentos que contengan el código necesario).

=== Enlazado estático VS enlazado dinámico: ===

Los montadores de enlaces convencionales (estáticos) deben enlazar en tiempo de compilación todos los módulos, segmentos y referencias de un
programa para completar sus instrucciones (si el número de instrucciones es muy elevado la cantidad de trabajo del montador será enorme)
mientras que los montadores de enlaces dinámicos realizarán el enlazado durante la ejecución o durante la carga del programa.

*'''Pros y contras:'''
La ventaja de usar enlaces dinámicos es que los programas serán más livianos, aunque se crea una cierta dependencia del programa el cual no
funcionará correctamente si se modifica algún módulo, segmento o referencia (en windows los errores debidos a actualizaciones de librerías
dinámicas .dll son bastante comunes). Por otro lado la ventaja de usar enlaces estáticos es que los problemas son totalmente independientes,
lo que facilita su distribución.

*'''Enlazado dinámico durante la carga:'''
En los ss.oo. de este tipo los ejecutables incluyen una relación de los objetos externos que necesita. Al cargar el programa se buscan los
segmentos ya cargados y los que se necesitan y se resuelven los enlaces.

*'''Enlazado dinámino durante la ejecución:'''
El enlazado dinámico durante la ejecución se basa en emplear referencias indirectas (la referencia apunta a una dirección de memoria la cual
contiene la referencia al objeto) y en dotar al procesador de un tipo especial de interrupción llamado excepción de enlace.
El compilador establece de forma indirecta las referencias a elementos de otros segmentos, utilizando como objeto intermedio un puntero con el
bit de excepción de enlace activado y que apunta hacia el identificador del elemento referido. Cuando se alcanza una referencia de este tipo
se lanza la excepción de enlace y el ss.oo. la atrapa el cual busca el objeto y localiza su dirección segmentada, con esa información el
ss.oo. modifica el puntero asignandole la dirección hallada y desactivando el bit de excepción (el enlace especial se reduce a una referencia
indirecta normal).
Para facilitar la ejecución las referencias a un mismo objeto se concentran en un único puntero (así la excepción de enlace se producirá
una sola vez) y todos los enlaces se concentran en un segmento especial llamado segmento de enlace.

SO multiprogramables con particiones variables

2011-12-28T16:22:38Z

Jesgonbel: /* Ajuste rápido */ corrección de errores.

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 (llamados unidades de asignación), se utiliza un bit para representar si dicho bloque está libre o asignado. El tamaño de los bloques tiene una cierta importancia ya que cuanto mayores sean menos bloques cabrán en memoria con lo que serán necesarios menos bits para controlar todos los bloques y el mapa de bits será de menor tamaño.

* '''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, así como su estado (asignado o libre).

= 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. Cuando se alcanza el final de la memoria se vuelve a comenzar la búsqueda desde el principio (por ello este criterio es también conocido como primer ajuste circular).

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)'') debido a que hay que recorrer todo el mapa de bits o toda la lista de control (una posible solución seria usar una lista de control encadenada que mantenga los huecos ordenados por tamaño creciente).
Otro problema es la fragmentación externa, debido a que se asigna el menor hueco posible, el espacio sobrante sera del menor tamaño posible lo que da lugar a huecos de tamaño normalmente insuficiente para contener programas.

== Peor ajuste ==

Al contrario que el criterio anterior, se busca el hueco con mayor ajuste interno, i.e, el hueco el cual al serle asignado el proceso deja más espacio sin utilizar, y se corta de él el trozo necesario (así la porción sobrante será del mayor tamaño posible y será más aprovechable). Tiene el mismo inconveniente en cuanto a orden de complejidad que el mejor ajuste (debido a la longitud de las búsquedas) y la fragmentación no resulta demasiado eficiente.

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

Organización de los huecos en el ajuste rápido:

Punteros a listas Lista de huecos
según tamaño
__________________
| | _____ _____ _____
| 0 < t < 10 |--->|_____|-->|_____|-->|_____|
|__________________|
| | _____ _____
| 10 < t < 20 |--->|_____|-->|_____|
|__________________|
| |
| ... |
|__________________|
| | _____
| t < 200 |--->|_____|
|__________________|

== 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. Es un método rápido tanto en la asignación como en la liberación de bloques.
El funcionamiento es el siguiente:
Cuando se necesita un bloque de tamaño T se busca en la lista de la 1ª potencia mayor o igual a T (por ejemplo 2^k), si no hay ninguno se busca en la lista de la siguiente potencia (2^k+1), si encontramos un bloque libre se retira y se divide por la mitad: una parte se le asigna al proceso y la otra se almacena en la lista de los huecos de tamaño 2^k.

''Organización de los bloques:''

__________________
| | _____ _____ _____
| 2^(k+1) |--->|_____|-->|_____|-->|_____|
|__________________|
| | _____ _____
| 2^k |--->|_____|-->|_____|
|__________________|
| |
| ... |
|__________________|
| | _____
| 1 |--->|_____|
|__________________|

Debido a la forma de dividir los bloques al liberarse uno de ellos solamente podrá fusionarse con sus compañeros (bloques del mismo tamaño) con los que formará un bloque de tamaño superior.

''Divisiones sucesivas de los bloques:''
_______________________________________________
|0 |2 |
|_______________________|_______________________|
_______________________________________________
|0 |2 |4 |6 |
|___________|___________|___________|___________|
_______________________________________________
|0 |2 |4 |6 |8 |10 |12 |14 |
|_____|_____|_____|_____|_____|_____|_____|_____|
________________________________________________
|0 | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|
|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

SO multiprogramables con particiones variables

2011-12-27T19:08:56Z

Jesgonbel: /* Método de los compañeros */ correción

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

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

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

== Elementos de administración ==

* '''Mapas de bits''': Dividiendo la memoria en bloques (llamados unidades de asignación), se utiliza un bit para representar si dicho bloque está libre o asignado. El tamaño de los bloques tiene una cierta importancia ya que cuanto mayores sean menos bloques cabrán en memoria con lo que serán necesarios menos bits para controlar todos los bloques y el mapa de bits será de menor tamaño.

* '''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, así como su estado (asignado o libre).

= 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. Cuando se alcanza el final de la memoria se vuelve a comenzar la búsqueda desde el principio (por ello este criterio es también conocido como primer ajuste circular).

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)'') debido a que hay que recorrer todo el mapa de bits o toda la lista de control (una posible solución seria usar una lista de control encadenada que mantenga los huecos ordenados por tamaño creciente).
Otro problema es la fragmentación externa, debido a que se asigna el menor hueco posible, el espacio sobrante sera del menor tamaño posible lo que da lugar a huecos de tamaño normalmente insuficiente para contener programas.

== Peor ajuste ==

Al contrario que el criterio anterior, se busca el hueco con mayor ajuste interno, i.e, el hueco el cual al serle asignado el proceso deja más espacio sin utilizar, y se corta de él el trozo necesario (así la porción sobrante será del mayor tamaño posible y será más aprovechable). Tiene el mismo inconveniente en cuanto a orden de complejidad que el mejor ajuste (debido a la longitud de las búsquedas) y la fragmentación no resulta demasiado eficiente.

== 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. Cuando se encuentre un hueco lo suficientemente grande se cortará la parte necesaria y se deja el resto en la lista que le corresponda.

Organización de los huecos en el ajuste rápido:

Punteros a listas Lista de huecos
según tamaño
__________________
| | _____ _____ _____
| 0 < t < 10 |--->|_____|-->|_____|-->|_____|
|__________________|
| | _____ _____
| 10 < t < 20 |--->|_____|-->|_____|
|__________________|
| |
| ... |
|__________________|
| | _____
| t < 200 |--->|_____|
|__________________|

== 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. Es un método rápido tanto en la asignación como en la liberación de bloques.
El funcionamiento es el siguiente:
Cuando se necesita un bloque de tamaño T se busca en la lista de la 1ª potencia mayor o igual a T (por ejemplo 2^k), si no hay ninguno se busca en la lista de la siguiente potencia (2^k+1), si encontramos un bloque libre se retira y se divide por la mitad: una parte se le asigna al proceso y la otra se almacena en la lista de los huecos de tamaño 2^k.

''Organización de los bloques:''

__________________
| | _____ _____ _____
| 2^(k+1) |--->|_____|-->|_____|-->|_____|
|__________________|
| | _____ _____
| 2^k |--->|_____|-->|_____|
|__________________|
| |
| ... |
|__________________|
| | _____
| 1 |--->|_____|
|__________________|

Debido a la forma de dividir los bloques al liberarse uno de ellos solamente podrá fusionarse con sus compañeros (bloques del mismo tamaño) con los que formará un bloque de tamaño superior.

''Divisiones sucesivas de los bloques:''
_______________________________________________
|0 |2 |
|_______________________|_______________________|
_______________________________________________
|0 |2 |4 |6 |
|___________|___________|___________|___________|
_______________________________________________
|0 |2 |4 |6 |8 |10 |12 |14 |
|_____|_____|_____|_____|_____|_____|_____|_____|
________________________________________________
|0 | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|
|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

SO multiprogramables con particiones variables

2011-12-27T19:07:22Z

Jesgonbel: /* Método de los compañeros */ ampliación

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

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

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

== Elementos de administración ==

* '''Mapas de bits''': Dividiendo la memoria en bloques (llamados unidades de asignación), se utiliza un bit para representar si dicho bloque está libre o asignado. El tamaño de los bloques tiene una cierta importancia ya que cuanto mayores sean menos bloques cabrán en memoria con lo que serán necesarios menos bits para controlar todos los bloques y el mapa de bits será de menor tamaño.

* '''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, así como su estado (asignado o libre).

= 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. Cuando se alcanza el final de la memoria se vuelve a comenzar la búsqueda desde el principio (por ello este criterio es también conocido como primer ajuste circular).

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)'') debido a que hay que recorrer todo el mapa de bits o toda la lista de control (una posible solución seria usar una lista de control encadenada que mantenga los huecos ordenados por tamaño creciente).
Otro problema es la fragmentación externa, debido a que se asigna el menor hueco posible, el espacio sobrante sera del menor tamaño posible lo que da lugar a huecos de tamaño normalmente insuficiente para contener programas.

== Peor ajuste ==

Al contrario que el criterio anterior, se busca el hueco con mayor ajuste interno, i.e, el hueco el cual al serle asignado el proceso deja más espacio sin utilizar, y se corta de él el trozo necesario (así la porción sobrante será del mayor tamaño posible y será más aprovechable). Tiene el mismo inconveniente en cuanto a orden de complejidad que el mejor ajuste (debido a la longitud de las búsquedas) y la fragmentación no resulta demasiado eficiente.

== 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. Cuando se encuentre un hueco lo suficientemente grande se cortará la parte necesaria y se deja el resto en la lista que le corresponda.

Organización de los huecos en el ajuste rápido:

Punteros a listas Lista de huecos
según tamaño
__________________
| | _____ _____ _____
| 0 < t < 10 |--->|_____|-->|_____|-->|_____|
|__________________|
| | _____ _____
| 10 < t < 20 |--->|_____|-->|_____|
|__________________|
| |
| ... |
|__________________|
| | _____
| t < 200 |--->|_____|
|__________________|

== 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. Es un método rápido tanto en la asignación como en la liberación de bloques.
El funcionamiento es el siguiente:
Cuando se necesita un bloque de tamaño T se busca en la lista de la 1ª potencia mayor o igual a T (por ejemplo 2^k), si no hay ninguno se busca en la lista de la siguiente potencia (2^k+1), si encontramos un bloque libre se retira y se divide por la mitad: una parte se le asigna al proceso y la otra se almacena en la lista de los huecos de tamaño 2^k.

''Organización de los bloques:''

__________________
| | _____ _____ _____
| ... |--->|_____|-->|_____|-->|_____|
|__________________|
| | _____ _____
| 2^(k+1) |--->|_____|-->|_____|
|__________________|
| |
| 2^k |
|__________________|
| | _____
| 1 |--->|_____|
|__________________|

Debido a la forma de dividir los bloques al liberarse uno de ellos solamente podrá fusionarse con sus compañeros (bloques del mismo tamaño) con los que formará un bloque de tamaño superior.

''Divisiones sucesivas de los bloques:''
_______________________________________________
|0 |2 |
|_______________________|_______________________|
_______________________________________________
|0 |2 |4 |6 |
|___________|___________|___________|___________|
_______________________________________________
|0 |2 |4 |6 |8 |10 |12 |14 |
|_____|_____|_____|_____|_____|_____|_____|_____|
________________________________________________
|0 | 1| 2| 3| 4| 5| 6| 7| 8| 9|10|11|12|13|14|15|
|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|__|

SO multiprogramables con particiones variables

2011-12-27T18:38:53Z

Jesgonbel: /* Ajuste rápido */ ampliación

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

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

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

== Elementos de administración ==

* '''Mapas de bits''': Dividiendo la memoria en bloques (llamados unidades de asignación), se utiliza un bit para representar si dicho bloque está libre o asignado. El tamaño de los bloques tiene una cierta importancia ya que cuanto mayores sean menos bloques cabrán en memoria con lo que serán necesarios menos bits para controlar todos los bloques y el mapa de bits será de menor tamaño.

* '''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, así como su estado (asignado o libre).

= 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. Cuando se alcanza el final de la memoria se vuelve a comenzar la búsqueda desde el principio (por ello este criterio es también conocido como primer ajuste circular).

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)'') debido a que hay que recorrer todo el mapa de bits o toda la lista de control (una posible solución seria usar una lista de control encadenada que mantenga los huecos ordenados por tamaño creciente).
Otro problema es la fragmentación externa, debido a que se asigna el menor hueco posible, el espacio sobrante sera del menor tamaño posible lo que da lugar a huecos de tamaño normalmente insuficiente para contener programas.

== Peor ajuste ==

Al contrario que el criterio anterior, se busca el hueco con mayor ajuste interno, i.e, el hueco el cual al serle asignado el proceso deja más espacio sin utilizar, y se corta de él el trozo necesario (así la porción sobrante será del mayor tamaño posible y será más aprovechable). Tiene el mismo inconveniente en cuanto a orden de complejidad que el mejor ajuste (debido a la longitud de las búsquedas) y la fragmentación no resulta demasiado eficiente.

== 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. Cuando se encuentre un hueco lo suficientemente grande se cortará la parte necesaria y se deja el resto en la lista que le corresponda.

Organización de los huecos en el ajuste rápido:

Punteros a listas Lista de huecos
según tamaño
__________________
| | _____ _____ _____
| 0 < t < 10 |--->|_____|-->|_____|-->|_____|
|__________________|
| | _____ _____
| 10 < t < 20 |--->|_____|-->|_____|
|__________________|
| |
| ... |
|__________________|
| | _____
| t < 200 |--->|_____|
|__________________|

== 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-27T18:24:53Z

Jesgonbel: /* Peor ajuste */ ampliación.

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

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

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

== Elementos de administración ==

* '''Mapas de bits''': Dividiendo la memoria en bloques (llamados unidades de asignación), se utiliza un bit para representar si dicho bloque está libre o asignado. El tamaño de los bloques tiene una cierta importancia ya que cuanto mayores sean menos bloques cabrán en memoria con lo que serán necesarios menos bits para controlar todos los bloques y el mapa de bits será de menor tamaño.

* '''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, así como su estado (asignado o libre).

= 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. Cuando se alcanza el final de la memoria se vuelve a comenzar la búsqueda desde el principio (por ello este criterio es también conocido como primer ajuste circular).

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)'') debido a que hay que recorrer todo el mapa de bits o toda la lista de control (una posible solución seria usar una lista de control encadenada que mantenga los huecos ordenados por tamaño creciente).
Otro problema es la fragmentación externa, debido a que se asigna el menor hueco posible, el espacio sobrante sera del menor tamaño posible lo que da lugar a huecos de tamaño normalmente insuficiente para contener programas.

== Peor ajuste ==

Al contrario que el criterio anterior, se busca el hueco con mayor ajuste interno, i.e, el hueco el cual al serle asignado el proceso deja más espacio sin utilizar, y se corta de él el trozo necesario (así la porción sobrante será del mayor tamaño posible y será más aprovechable). Tiene el mismo inconveniente en cuanto a orden de complejidad que el mejor ajuste (debido a la longitud de las búsquedas) y la fragmentación no resulta demasiado eficiente.

== 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-27T18:21:03Z

Jesgonbel: /* Mejor ajuste */ ampliacion contenido

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 (llamados unidades de asignación), se utiliza un bit para representar si dicho bloque está libre o asignado. El tamaño de los bloques tiene una cierta importancia ya que cuanto mayores sean menos bloques cabrán en memoria con lo que serán necesarios menos bits para controlar todos los bloques y el mapa de bits será de menor tamaño.

* '''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, así como su estado (asignado o libre).

= 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. Cuando se alcanza el final de la memoria se vuelve a comenzar la búsqueda desde el principio (por ello este criterio es también conocido como primer ajuste circular).

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)'') debido a que hay que recorrer todo el mapa de bits o toda la lista de control (una posible solución seria usar una lista de control encadenada que mantenga los huecos ordenados por tamaño creciente).
Otro problema es la fragmentación externa, debido a que se asigna el menor hueco posible, el espacio sobrante sera del menor tamaño posible lo que da lugar a huecos de tamaño normalmente insuficiente para contener programas.

== 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-27T18:10:44Z

Jesgonbel: /* Siguiente ajuste */ pequeña ampliación en siguiente ajuste.

SO multiprogramables con particiones variables

2011-12-27T18:08:25Z

Jesgonbel: /* Elementos de administración */ ampliación de los elementos de administración (SO multiogramables con particiones variables)

SO monoprogramables

2011-12-15T11:24:44Z

Jesgonbel: /* Admon. de memoria en SO monoprogramables */ Ampliación.

En los sistemas operativos monoprogramables la administración de memoria es muy sencilla ya que solo hay un proceso en ejecución que puede usar todo el espacio disponible, la gestión de memoria se limita casi a comprobar si el proceso cabe en el espacio libre en la memoria. El SO se coloca como bloque al principio o al final de la memoria (memoria del sistema), y el resto para el proceso a ejecutar (memoria del proceso):
_______________________ _______________________
/| | 0 0| |\
| | zona de memoria del | | zona del S.O en RAM | |
| | sistema operativo | |_______________________| |
| |_______________________| | |\|
|/| | | zona de memoria del | |
Sistema \ | | | | usuario (ejecución | | < IBM PC
clásico / | | zona de memoria del | | de procesos) | |
| | usuario | |_______________________| |
| | (ejecución de | | |\|
| | procesos) | | zona de Lectura | |
| | | | | |
\|_______________________| N N|_______________________|/

*Solapamiento:
Si el proceso no cabe en el espacio libre en memoria puede recurrirse a 2 estrategias para ejecutarlo:
**Ejecución en cadena:
El programa se divide en varios "subprogramas" y se ejecutan en cadena. Esto se consigue haciendo que cada programa termine su ejecución
solicitando que se ejecute el siguiente.
**Fragmentar el programa en módulos de solapamiento o recubrimiento:
Dichos módulos se van cargando en memoria según se necesite, algunos S.O. permiten que los submodulos también se dividan, dando lugar a una
estructura en árbol.

'''______'''
''' | |'''
'''| |''' Datos permanentes: Datos globales,
'''| |''' programa principal y subprogramas comunes
'''| |
'''| |'''
''' |______|'''_______________________________________________________
| | __|__ __|__ __|__ __|__ /
| | ''' | | | | | | | |''' |
| | '''| A | | | | C | | D |''' |
| | '''|_____| | | | | |_____|''' < Módulos de solapamiento o recubrimiento (A, B, C, D)
| | '''| D | |_____|''' |
| | '''| |''' |
|______| '''|_____|''' \

*Protección de memoria:

Los sistemas operativos monoprogramables tienen debilidades en cuanto a protección de memoria. Para evitar que un proceso entre en el área del SO, se puede recurrir al uso de:
**'''bits de protección''': se le asocia a cada palabra un bit (1 para S.O. y 0 para proceso) para comprobar si la posición de memoria es de SO o del proceso. Este sistema no exige que la región protegida sea contigua, con lo que el sistema operativo puede marcar como suyas algunas posiciones de memoria de subprocesos especiales lo que permite que los mismos accedan de forma controlada a datos y subprogramas del núcleo.

**'''Registros valla o registros límite''': En el limite entre la zona del sistema operativo y la zona para la ejecución de procesos se carga un registro con la primera posición de memoria que ocupa el proceso. Este sistema es mas sencillo y barato que el anterior, pero solo protege una zona (entre la posición de memoria 0 y la posición de memoria del registro) y son necesarios circuitos comparadores rápidos para evitar retrasar la ejecución de las instrucciones. Su funcionamiento es el siguiente: al intentar acceder a una posición de memoria se comprueba si esta dirección es menor que la dirección del registro valla, si es así se lanza un mensaje de error y si no es así se accede a la posición de memoria deseada.

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

Criterios de reemplazo

2011-12-13T18:25:17Z

Jesgonbel: /* Criterios */

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

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

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

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

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

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

*[[sol_5|Solución]]

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

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

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

*[[sol_6|Solución]]

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

*[[sol_7|Solución]]

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

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

*[[sol_8|Solución]]

;9.Criterio LFU ('''L'''east '''F'''recuently '''U'''sed):Se puede implementar mediante una pila o cola situando la página más frecuentemente usada en la base de la pila o cabeza de la cola.La página víctima será la quede al final de la estructura. Otra variante de implementación es mediante un contador. Se incrementa un contador de uso por cada acceso, reseteándose si se reemplaza la página. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

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

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

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

*[[sol_10|Solución]]

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

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

Criterios de reemplazo

2011-12-13T18:24:31Z

Jesgonbel: /* Criterios */ Colocación del apartado criterio de reloj

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

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

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

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

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

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

*[[sol_5|Solución]]

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

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

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

*[[sol_6|Solución]]

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

*[[sol_7|Solución]]

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

;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]]
*[[sol_8|Solución]]

;9.Criterio LFU ('''L'''east '''F'''recuently '''U'''sed):Se puede implementar mediante una pila o cola situando la página más frecuentemente usada en la base de la pila o cabeza de la cola.La página víctima será la quede al final de la estructura. Otra variante de implementación es mediante un contador. Se incrementa un contador de uso por cada acceso, reseteándose si se reemplaza la página. La víctima será la que tenga el contador menor.

*[[sol_9|Solución]]

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

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

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

*[[sol_10|Solución]]

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

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

Condiciones para el interbloqueo y estrategias de resolución

2011-12-08T01:59:10Z

Jesgonbel: /* Prevención */

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

Condiciones para el interbloqueo y estrategias de resolución

2011-12-08T01:35:31Z

Jesgonbel: /* Detección y Recuperación */ corrección de erratas.

== 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 si quiera 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.
* ''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.

Condiciones para el interbloqueo y estrategias de resolución

2011-12-08T01:30:50Z

Jesgonbel: /* Detección y Recuperación */ Ampliación del concepto de estrategia eliminación

== 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 si quiera 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 solucionarse, 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.
* ''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.

Condiciones para el interbloqueo y estrategias de resolución

2011-12-08T01:24:21Z

Jesgonbel: /* Detección y Recuperación */ ejemplo de estrategia de apropiación temporal

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

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

Condiciones para el interbloqueo y estrategias de resolución

2011-12-07T23:47:12Z

Jesgonbel: /* 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 si quiera 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. 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.

* ''Apropiación temporal'': Se retira la asignación de un recurso a un proceso para deshacer el interbloqueo.

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

Solución ejercicio 7

2011-12-07T02:12:07Z

Jesgonbel: Ejercicio 7 (Semáforos y comunicación) propuesta de solución

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

}
</source>

Hilo h2

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

}
</source>

> = Fin de su ejecucion

| #1| #2| #3| | | | #4| #5| #1| | | | #2| #2| #2| | | | #2| #3| #4| | | | #5| #1| |
h1|---|---|---| | | |---|---|---| | | |---|---|---| | | |---|---|---| | | |---|---> |
| | | | | | | | | | | | | | | | | | | | | | | | | | | |
| | | | #1| #2| #2| | | | #2| #3| #4| | | | #5| #1| #2| | | | #3| #4| #5| | | #1|
h2| | | |---|---|---| | | |---|---|---| | | |---|---|---| | | |---|---|---| | |--->
| | | | | | | | | | | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Nota: La solución que estaba antes propuesta no tenia relación con el ejercicio 7.Esta solucion todavía no ha sido revisada por Pablo.

[[Usuario:jesgonbel|jesgonbel]] Esta es la solución que he obtenido al cambiar los cerrojos por semáforos:

Inicialmente s1=1 y s2=0

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

Hilo 2:
<source lang="c">
for (int i = 0; i<2; i++){ //#1
down(s2); //#2
f(); //#3
up(s1); //#4
}
</source>
X: El proceso es bloqueado por el semáforo.
/: El proceso pasa a estado preparado.
>: El proceso termina su ejecución.

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

Sol-ejer-planif-procesos-3

2011-11-11T05:17:50Z

Jesgonbel: Propuesta de corrección y solución al apartado B

APARTADO 1

Traza de los procesos A y B

Proceso A
---------
1, 2, 3, 4, 3, 4, 3, 5
| | | | |
i=0 Bloquea i=1 Bloquea i=2

Por tanto tenemos t=8

Proceso B
---------
1, 2, 3, 2, 3, 2, 4
| | | |
i=0 i=1 i=2 Bloquea

Por tanto t=7

Proceso H0 t Plazo
-------- -- -- -----
PA 0 8 16
PB 0 7 18

| 1 | | | | | | | | 2 | 3 | 4 | | | | 3 | 4 | | |
Pa <---| | | | | | | |---|---|---B | | P---|---B ABORTAR
| | | | | | | | | |i=0| | | | |i=1| | | |
| | | | | | | | | | | | | | | | | | |
| | 1 | 2 | 3 | 2 | 3 | 2 | 4 | | | | | | | | | | |
Pb | <---|---|---|---|---|---|---B | P FIN | | | | | |
| | |i=0| |i=1| |i=2| | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | |
Planificador X X | | | | | | X | | X | | X | X | |
| | | | | | | | | | | | | | | | | | |
|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___|___> t
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

--Creo que esa solución no es correcta (el enunciado dice que los 2 procesos se lanzan a la vez y en este cronograma se lanza Pa antes que Pb. Yo he llegado a las siguientes soluciones:

a)

& = El proceso realiza una llamada bloqueante.
+ = El proceso se ejecuta en el procesador 1.
- = El proceso se ejecuta en el procesador 2.
< = Instante de llegada del proceso.
> = Instante de finalización del proceso.
* = El proceso es abortado.

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

--Duda: yo he supuesto que aunque el planificador le de paso primero a A al aplicar el criterio y al tener B mayor prioridad de ejecuta B en t=0. --[[Usuario:jesgonbe|jesgonbel]]

b) Suponiendo que solo se ejecutan procesos en el procesador 2 si esta ocupado el procesador 1

& = El proceso realiza una llamada bloqueante.
+ = El proceso se ejecuta en el procesador 1.
- = El proceso se ejecuta en el procesador 2.
< = Instante de llegada del proceso.
> = Instante de finalización del proceso.

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

Ejercicios otros aspectos de la planificación

2011-11-11T04:40:17Z

Jesgonbel: /* Ejercicio 2 */ aclaración

== Ejercicio 1 ==

Dada la siguiente configuración de procesos:
{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
! width="50" style="background:#efefef;" | Proceso
! width="50" style="background:#efefef;" | H0
! width="50" style="background:#efefef;" | t
|-
| PA
| 0
| 5
|-
| PB
| 1
| 3
|-
| PC
| 2
| 1
|-
| PD
| 3
| 6
|-
| PE
| 4
| 2
|}

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

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

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

== Ejercicio 2 ==
''[Este ejercicio fue parte del primer Control de Evaluación Contínua del Curso 2010/11, del 23 de marzo de 2011]''

Dada la siguiente configuracion de procesos:

{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
! width="50" style="background:#efefef;" | Proceso
! width="50" style="background:#efefef;" | H0
! width="50" style="background:#efefef;" | t
|-
| PA
| 0
| 3
|-
| PB
| 1
| 5
|-
| PC
| 2
| 6
|}

Teniendo en cuenta el siguiente comportamiento:

* El proceso A cada 1 unidad de tiempo de ejecución bloquea .
* El proceso B cada 3 unidades de tiempo de ejecución bloquea.

Suponga que el tiempo de bloqueo de todos los procesos es de 2 unidades de tiempo debido al tiempo de acesso al dispositivo de E/S.

Realice la traza de ejecución de dichos procesos y los índices de penalización para los siguientes criterios de planificación:

#El siguiente, el más corto apropiativo en un sistema multiprocesador con dos procesadores, solo se ejecutaran procesos en el procesador 2 si el procesador 1 está ocupado. No olvide los tiempos de bloqueo de los procesos A y B. Considere asignación dinámica. (''[[sol-ejer2-1-otros-aspectos|Ver solución]]'')
#Por prioridades apropiativo en tiempo real, suponiendo que C < B < A. No olvide los tiempos de bloqueo de los procesos A y B. (''[[sol-ejer2-2-otros-aspectos|Ver solución]]'')

{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
! width="50" style="background:#efefef;" | Proceso
! width="50" style="background:#efefef;" | Plazo
|-
| PA
| 6
|-
| PB
| 15
|-
| PC
| 15
|}

== Ejercicio 3 ==
''[Este ejercicio formó parte del Primer Parcial de Evaluación Contínua del curso 2011/12 del 8 de Noviembre de 2011]''

Dado el código de los siguientes procesos:

'''Código proceso A:'''
<source lang="c">
int fd; #1
fd = open("fichero.txt", O_WRONLY, 0600); #2
for(int i=0;i<2;i++) { #3
write(fd, "%d", sizeof(int)); #4
}
close(fd); #5
</source>

'''Código proceso B:'''
<source lang="c">
int fd, contador = 0; #1
for(int i=0;i<2;i++) { #2
contador+=2; #3
}
printf("el contador vale: %d\n", contador); #4
</source>

De manera teórica, suponga que la ejecución de cada línea de código toma una unidad de tiempo. Considere que las llamadas '''write''' y '''printf''' son bloqueantes puesto que suponen accesos a dispositivos de E/S, siendo los tiempos de bloqueo de 3 unidades de tiempo. Suponga que ambos procesos se lanzan a la vez, pero el planificador da paso en primer lugar al proceso A.

Realize la traza temporal de ejecución de dichos procesos y los índices de penalización para los siguientes criterios de planificación:

#Por prioridades apropiativo en tiempo real, suponiendo que B>A. No olvide los tiempos de bloqueo de los procesos A y B. Considere que los plazos de ejecucion de proceso A es 16 y de proceso B es 18

#Suponiendo un sistema multiprocesador con dos procesadores. No olvide los tiempos de bloqueo de los procesos A y B. Considere asignación dinámica

[[sol-ejer-planif-procesos-3|Ver solución del ejercicio 3]]

Sol-ejer6-planif-procesos

2011-11-11T01:56:24Z

Jesgonbel: /* Apartado a */

= Apartado a =

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

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
& = el proceso bloquea debido a una llamada bloqueante
# = el proceso bloquea debido a que ha consumido su cuanto
X = se ejecuta el código del planificador
p = el proceso pasa a estado preparado

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

-Respuesta: debido a que el quantum tiene un tamaño muy pequeño el planificador de tareas se ejecuta continuamente (tiempo del sistema alto) con lo que el rendimiento se verá afectado.

DUDA: En t=5 ¿por qué se inicia PC en vez de PD? Si entra PD en t=5 se debería ejecutar porque en RR estricto los procesos recién lanzados deben ejecutarse, similar a lo de orden de llegada. He pensado que puede ser por la prioridad pero esque aquí en la tabla no viene las prioridades, solo H0 y t. --Luisa Mª.

- En t=4 se han ejecutado Pa,Pb y Pc, entonces le tocaría el turno a Pd pero como en ese momento no está preparado se le pasa el turno a Pa otra vez, después de ejecutarse este se le pasa el turno a Pb pero como ya ha terminado de ejecutarse se salta al proceso siguiente: Pc. ¡Aunque también es posible que me haya equivocado! --[[Usuario:jesgonbel|jesgonbel]].

= Apartado b =

En ambos casos la solución es la misma.

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

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
& = el proceso bloquea debido a una llamada bloqueante
# = el proceso bloquea debido a que ha consumido su cuanto
X = se ejecuta el código del planificador
p = el proceso pasa a estado preparado

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

= Apartado c =

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

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
& = el proceso bloquea debido a una llamada bloqueante
# = el proceso bloquea debido a que el planificador le retira el procesador
X = se ejecuta el código del planificador
p = el proceso pasa a estado preparado

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

Indices de penalizacion: PA=9 PB=1 PC=7/4 PD=9/6

Sol-ejer6-planif-procesos

2011-11-11T01:50:30Z

Jesgonbel: /* Apartado a */ Respuesta.

= Apartado a =

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

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
& = el proceso bloquea debido a una llamada bloqueante
# = el proceso bloquea debido a que ha consumido su cuanto
X = se ejecuta el código del planificador
p = el proceso pasa a estado preparado

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

-Respuesta: debido a que el quantum tiene un tamaño muy pequeño el planificador de tareas se ejecuta continuamente (tiempo del sistema alto) con lo que el rendimiento se verá afectado.

DUDA: En t=5 ¿por qué se inicia PC en vez de PD? Si entra PD en t=5 se debería ejecutar porque en RR estricto los procesos recién lanzados deben ejecutarse, similar a lo de orden de llegada. He pensado que puede ser por la prioridad pero esque aquí en la tabla no viene las prioridades, solo H0 y t. --Luisa Mª.

- En t=4 se han ejecutado Pa,Pb y Pc, entonces le tocaría el turno a Pd pero como en ese momento no está preparado se le pasa el turno a Pa otra vez, después de ejecutarse este se le pasa el turno a Pb pero como ya ha terminado de ejecutarse se salta al proceso siguiente: Pc. ¡Aunque también es posible que me haya equivocado!

= Apartado b =

En ambos casos la solución es la misma.

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

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
& = el proceso bloquea debido a una llamada bloqueante
# = el proceso bloquea debido a que ha consumido su cuanto
X = se ejecuta el código del planificador
p = el proceso pasa a estado preparado

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

= Apartado c =

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

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
& = el proceso bloquea debido a una llamada bloqueante
# = el proceso bloquea debido a que el planificador le retira el procesador
X = se ejecuta el código del planificador
p = el proceso pasa a estado preparado

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

Indices de penalizacion: PA=9 PB=1 PC=7/4 PD=9/6

Planificación de procesos de tiempo real

2011-11-11T01:43:06Z

Jesgonbel: /* Métodos de planificación */ ampliación de "planificación dinámica del mejor resultado"

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

Proceso de tiempo real se trata de un proceso cuya actividad tiene un plazo de finalización.

== ¿Qué es un sistema operativo de tiempo real? ==

Un sistema operativo de tiempo real dispone de un planificador de procesos que tiene mecanismos para hacer lo máximo posible para garantizar que sus procesos de tiempo real cumplan los plazos de finalización que tienen establecidos.

== Clasificación ==

Podemos clasificar los procesos de tiempo real de diferentes maneras:

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

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

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

Según la periodicidad:

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

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

== Métodos de planificación ==

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

*'''Planificación apropiativa con prioridad estática''': Cada proceso tiene asociado un índice de prioridad y el procesador elige aquel proceso de la lista de preparados con mayor prioridad, es el más tradicional y puede ser llevado a cabo por el procesador de un sistema que no sea de tiempo real.

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

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

*'''Planificación dinámica con un mejor resultado''':Se utiliza para aplicaciones compuestas mayormente por actividades aperiódicas.El planificador intenta cumplir el plazo de todas las actividades asignandole a cada actividad una prioridad en base a sus características (las actividades fuera de plazo se abortan). Es muy similar a la anterior, la diferencia más notable es que en la anterior existe un análisis previo aceptando actividades aperiódicas y en ésta no existe tal análisis.
Es un método fácil de implementar, sin embargo, no podremos saber de antemano si una actividad cumplirá su plazo o no (sabremos que no lo cumple si es abortada, y viceversa).

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

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

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

_____|_PA_|_PB_|_PC_|PD1ª_|PD2ª_|_PD_|
Cálculos __t__|_2__|_3__|_2__|_1__|_1__|_1__|
de tiempos __T__|_2__|_*__|_4__|_*__|_2__|_1__|
_T/t_|_1__|_*__|_2__|_*__|_2__|_1__|
|
|_> Indice de penalización

Si alguna actividad entrante tiene más prioridad que la que se está ejecutando, ésta última pasa a estado preparado y se da paso a la nueva.

Ejercicios planificación de procesos

2011-11-10T04:20:38Z

Jesgonbel:

= Ejercicio 1 =

Dada la siguiente configuración de procesos:

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

Realice la traza de la ejecución de dichos procesos para los siguientes criterios de planificación:

* FIFO (no apropiativo)
* SJF (apropiativo y no apropiativo)
* Índice de penalización (no apropiativo)
[[sol-ejer1-planif-procesos|Ver solución ejercicio 1]]

= Ejercicio 2 =

Dada la siguiente configuración de procesos:

H0 t
PA 0 3
PB 1 5
PC 2 6

Teniendo en cuenta el siguiente comportamiento:

* El proceso A cada 1 unidad de tiempo de ejecución bloquea por operación de E/S
* El proceso B cada 3 unidades de tiempo de ejecución bloquea por operación de E/S

Suponga que el tiempo de bloqueo de todos los procesos es de 2 unidades de tiempo debido al tiempo de acceso al dispositivo de E/S.

Realice la traza temporal de ejecución de dichos procesos para los siguientes criterios de planificación:

* Turno rotatorio estricto, suponiendo que el quantum es de 2 unidades de tiempo.
* Por prioridades, suponiendo que A < B < C.
* Turno rotatorio proporcional al número de procesos en estado preparado, suponiendo que el quantum es de 2 unidades de tiempo. Si hay dos o más procesos preparados el quantum pasa a ser de una unidad de tiempo.

[[sol-ejer2-planif-procesos|Ver solución ejercicio 2]]

= Ejercicio 3 =

En un planificador multinivel con realimentación se dispone de dos colas:

* La primera cola tiene procesos que reciben un ''quantum'' de 4 unidades de tiempo.
* La segunda cola tiene procesos que reciben un ''quantum'' de 2 unidades de tiempo. Los procesos en esta cola reciben dos oportunidades de ejecución. Por tanto, se itera dos veces sobre esta cola antes de pasar a la primera cola.

Los procesos que acaban de ser lanzados pasan inicialmente a la segunda cola. Si consumen completamente el ''quantum'' una vez, promocionan a la primera cola. Si dejan de consumir completamente el ''quantum'' una vez, descienden a la segunda.

Dada la siguiente configuración de procesos:

H0 t
Pa 0 4
Pb 1 4
Pc 2 12
Pd 3 12

Suponga que los procesos A y B bloquean por operación de E/S tras 1 unidad de ejecución. Los procesos C y D no bloquean. Los tiempos de bloqueo por E/S son de 1 unidad de tiempo. Represente graficamente la evolución temporal de la asignación del procesador.

[[sol-ejer3-planif-procesos|Ver solución ejercicio 3]]

=Ejercicio 4 =
''[Este ejercicio formó parte del Primer Parcial de Evaluación Contínua del curso 2010/11 del 23 de marzo de 2011]''

Dada la siguiente configuracion de procesos:

{| border="2" cellpadding="4" cellspacing="0" style="margin: 1em 1em 1em 0; background: #f9f9f9; border: 1px #aaa solid; border-collapse: collapse; font-size: 95%;"
! width="50" style="background:#efefef;" | Proceso
! width="50" style="background:#efefef;" | H0
! width="50" style="background:#efefef;" | t
|-
| PA
| 0
| 3
|-
| PB
| 1
| 5
|-
| PC
| 2
| 6
|}

Teniendo en cuenta el siguiente comportamiento:

* El proceso A cada 1 unidad de tiempo de ejecución bloquea .
* El proceso B cada 3 unidades de tiempo de ejecución bloquea.

Suponga que el tiempo de bloqueo de todos los procesos es de 2 unidades de tiempo debido al tiempo de acesso al dispositivo de E/S.

Realice la traza de ejecución de dichos procesos y los índices de penalización para los siguientes criterios de planificación:

#Turno rotatorio con compensacion con quantum de 2 unidades de tiempo.

*En caso de que un proceso haya consumido el 50% de su quantum y en la cola de procesos preparados haya un unico proceso, insertelo delante de este.

*Si dos o mas procesos pasan de estado preparado a la vez, considere que el orden de insercion en la cola de preparados es el siguiente: 1ºA 2ºB 3ºC

*Recuerde que un proceso en estado bloqueado se inserta en la cola de preparados una vez que pasa el tiempo de bloqueo ( que en este ejercicio se trata de 2 unidades de tiempo)

*En toda decisión del planificador tenga en cuenta a los procesos que justo acaban de pasar a estado preparado tras un bloqueo.

''[[sol-ejer4-planif-procesos|Ver solución ejercicio 4]]''

=Ejercicio 5 =
''[Este ejercicio formó parte del Primer Parcial de Evaluación Contínua del curso 2011/12 del 8 de Noviembre de 2011]''

Dado el código de los siguientes procesos:

'''Código proceso A:'''
<source lang="c">
int fd; #1
fd = open("fichero.txt", O_WRONLY, 0600); #2
for(int i=0;i<2;i++) { #3
write(fd, "%d", sizeof(int)); #4
}
close(fd); #5
</source>

'''Código proceso B:'''
<source lang="c">
int fd, contador = 0; #1
for(int i=0;i<2;i++) { #2
contador+=2; #3
}
printf("el contador vale: %d\n", contador); #4
</source>

De manera teórica, suponga que la ejecución de cada línea de código toma una unidad de tiempo. Considere que las llamadas '''write''' y '''printf''' son bloqueantes puesto que suponen accesos a dispositivos de E/S, siendo los tiempos de bloqueo de 3 unidades de tiempo. Suponga que ambos procesos se lanzan a la vez, pero el planificador da paso en primer lugar al proceso A.

Realice la traza temporal de ejecución de dichos procesos y los índices de penalización suponiendo planificación por turno rotatorio con compensación con ''quantum'' de 2 unidades de tiempo:

* En caso de que un proceso haya consumido el 50% de su quantum y en la cola de procesos preparados haya un único proceso, insértelo delante de éste.
* Si dos o más procesos pasan a estado preparado a la vez, considere que el orden de inserción de preparados en la cola es el siguiente: 1º-A, 2º-B.
* Recuerde que un proceso en estado bloqueado se inserta en la cola de preparados una vez que pasa el tiempo de bloqueo (que en este ejercicio se trata de 3 unidades de tiempo.
* En toda decisión del planificador tenga en cuenta los procesos que justo acaban de pasar a estado preparado tras un bloqueo.

[[sol-ejer-planif-procesos-5|Ver solución del ejercicio 5]]

=Ejercicio 6=

Dada la siguiente configuración de procesos:

H0 t p
PA 0 3 -20
PB 2 1 0
PC 3 4 5
PD 5 6 10

Realice la traza de la ejecución de dichos procesos para los siguientes criterios de planificación:

* Round Robin estricto (quantum de 1 unidad de tiempo)
¿Puede realizar alguna observacion respecto al planificador de procesos en base al rendimiento?
* SJF (apropiativo y no apropiativo)
* Indice de penalización apropiativo (si se da un empate aplicar SJF), calcule los indices de penalizacion resultantes

[[Sol-ejer6-planif-procesos|Ver solución del ejercicio 6]]

IMPORTANTE: Este ejercicio aún no ha sido revisado por ningún profesor.

Sol-ejer6-planif-procesos

2011-11-10T04:18:13Z

Jesgonbel: correccion de erratas

= Apartado a =

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

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
& = el proceso bloquea debido a una llamada bloqueante
# = el proceso bloquea debido a que ha consumido su cuanto
X = se ejecuta el código del planificador
p = el proceso pasa a estado preparado

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

-Respuesta: debido a que el quantum tiene un tamaño muy pequeño el planificador de tareas se ejecuta continuamente (tiempo del sistema alto) con lo que el rendimiento se verá afectado.

= Apartado b =

En ambos casos la solución es la misma.

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

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
& = el proceso bloquea debido a una llamada bloqueante
# = el proceso bloquea debido a que ha consumido su cuanto
X = se ejecuta el código del planificador
p = el proceso pasa a estado preparado

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

= Apartado c =

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

< = indica el instante de lanzamiento del proceso
> = indica el instante de finalización del proceso
& = el proceso bloquea debido a una llamada bloqueante
# = el proceso bloquea debido a que el planificador le retira el procesador
X = se ejecuta el código del planificador
p = el proceso pasa a estado preparado

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

Indices de penalizacion: PA=9 PB=1 PC=7/4 PD=9/6