1

Algoritmo de prevención que niega la condición de no apropiación:

proceso Pi solicita un recurso

si esta disponible
entonces
se le asigna el recurso al proceso Pi

en caso contrario

si asignado a proceso Pj en espera de recursos

entonces
el sistema se apropia del recurso
se asigna el recurso al proceso Pi
en caso contrario
el proceso Pi pasa a estado de espera del recurso
fin-si
fin-si

A la hora de apropiar un recurso hay que tener en cuenta si es fácil restaurar el estado del recurso y si no hay pérdida
de información. La CPU se puede apropiar, la impresora no.
 Negación de la espera circular

Se ponen dos condiciones:

1- Se establece un orden entre los recursos: r1 < r2 < ... < rn

Se establece el siguiente protocolo:
Un proceso puede solicitar ri solo
Si tiene asignados rj < ri
Si un proceso solicita ri
Tiene que liberar rj > ri

2- Se exigen a los procesos que pidan los recursos en ese orden.

Problemas:

- Escoger el orden de los recursos.

- La libertad de programador esta limitada.
- Si se añade un nuevo recurso se debe de reordenar y por lo tanto reescribir todos los programas.

Predicción.

Permite las tres primeras condiciones y evita la espera circular. Requiere una información:
- De los recursos: cuantos existen, cuales están disponibles.
- De los procesos: que recursos necesitan, que recursos tienen asignados.
2

Dos enfoques:

a) Denegar la inicialización del proceso

Para ello debemos de disponer de información sobre el sistema.
- Vector de recursos: unidades totales de cada tipo de recurso.

Recurso = [Ri] = (R1, R2,..., Rn)

- Vector de disponibles: unidades disponibles de cada tipo de recurso.

-

Disponible = [Di] = (D1, D2,..., Dm)

- Matriz demanda máxima: exigencias máximas de cada proceso. Demanda del proceso i de recurso del
tipo j.
-
DM11 ... DM1m
Demanda máxima = [DMij] = ... DMij ...
DMn1 ... DMnm

- Matriz asignación: recurso de tipo j asignado al proceso i.

A11 ... A1m

Asignación = [Aij] = ... Aij ...
An1 ... Anm

n
Ri = D i + ∑ A K , ∀ i
i
1) K =1 : la cantidad de recursos del sistema es igual a la que está disponible más la que
está asignada.

DM K ≤ Ri , ∀ i , k
2) i : la demanda de recursos nunca podrá ser mayor que los recursos del sistema.

A K ≤ DM K , ∀ i, k
3) i i : a un proceso solo se le podrá asignar como máximo lo que él solicitó.

n
V i ⇒ R i ≥ ∑ DM K + DM (n +1 )
i i
4) K =1 : para admitir a un proceso el número de recursos debe ser igual o mayor
3

Que el número de demanda máxima actual más la demanda del nuevo proceso.

Ejemplo:

R1 = 7
P1 1
P2 3
P3 2 6 + 2 = 8 no <= 7  no se inicia
P4 2

No es óptimo por que se basa en la máxima demanda

b) Denegación de asignación de recursos

Además hace falta otra matriz:

Matriz necesidad: Nij es la necesidad del proceso i respecto del recurso j.

N11 ... N1m

Necesidad = [Nij] = ... Nij ...
Nn1 ... Nnm

Necesidad = Demanda - Asignación

Algoritmo del banquero

Dijkstra (65). Si un sistema siempre está en estado seguro, nunca se va a producir interbloqueo.
Estado del sistema: se define como el estado actual de asignación de los recursos a los procesos. Viene dado por las
matrices de Demanda, Asignación y Necesidad.

Sistema seguro: existe un orden en el cual todos los procesos se pueden ejecutar hasta finalizar su ejecución sin que
se produzca interbloqueo. Si no es posible encontrar esta secuencia, el estado está inseguro. Un estado inseguro indica
una posibilidad de que se dé interbloqueo.Estos algoritmos consisten en intentar que el sistema esté siempre en estado
seguro.

Inconvenientes:
4

- Los procesos tienen que declarar por anticipado esa demanda máxima.
- El número de procesos del sistema debe ser constante.
- El número de recursos del sistema debe ser constante.
- El coste del algoritmo es bastante elevado. El número de operaciones que hay que realizar es n 2 * m, donde
n es el número de procesos y m es el número de recursos.
- El algoritmo asume el peor caso. Los procesos usan todos los recursos al mismo tiempo.
- Los procesos que requieren muchos recursos están muy castigados, al estar constantemente denegándole la
asignación de recursos.
- Los procesos del sistema deben ser independientes.
- No se sabe cuanto tiempo puede estar un proceso esperando un recurso.

Detección y recuperación.

Permite que se produzca interbloqueo. No impone condiciones a los procesos. Supone una sobrecarga del sistema.Lo
primero es ver cuando ejecutar ese algoritmo, el de comprobación de interbloqueo:

- Cada vez que se asigne un recurso a un proceso.

- Cada solicitud denegada: algoritmo más sencillos pero sobrecargan al sistema por que están constantemente
ejecutándose.
- Cada cierto tiempo: se puede ejecutar más veces de las que realmente son necesarias.
- Cuando el rendimiento del sistema cae por debajo de algún nivel.

Detección por grafos. Un grafo puede ser reducido si el proceso no espera ningún recurso o está esperando recursos
que están disponibles  desaparecen todas las aristas de petición y espera y libera todos los recursos asignados. Si el
proceso es productor de recurso, supondremos que se dispone de recursos suficientes para satisfacer todas las
peticiones.

Ejemplo:
R2  Consumible  P2, P3 productores
R1 y R3  Reutilizable

Para la recuperación existen varias técnicas:

A) Terminación de procesos:
- Todos los bloqueados: se terminan y tienen que empezar otra vez. Tiene un alto coste.
- Uno a uno: se elimina uno, si sigue habiendo interbloqueo se termina otro y así sucesivamente.
Tarda más que la anterior, hay que ejecutar el algoritmo cada vez que se termina uno. Existen
muchos criterios para terminarlos: prioridad, el que solicita más recursos, el que tiene más o menos
recursos asignados, el que lleva más o menos tiempo ejecutándose.

B) Apropiación de recursos: tiene un problema. No se puede aplicar a todos los recursos.

5

Problemas:
- Escoger la víctima: se usan criterios similares a los anteriores, pero hay que evitar la inanición, escoger
siempre a la misma víctima
- Apropiación del recurso: no todos se pueden apropiar.

Administración de la memoria.
Jerarquía del almacenamiento.

Menor tiempo de acceso, más costosos.

Registros

Caché Disminuye el coste por bit.

Interna Aumenta la capacidad.
Memoria
Aumenta el tiempo de acceso.
Volátil Principal
Disminuye la frecuencia de accesos por
Caché de disco parte del procesador.

Disco magnético

Cinta magnética Disco óptico

Mayor capacidad, menos costosos.

Principio de localidad o principio de cercanía: Durante el curso de la ejecución de un proceso, las referencias a
memoria, tanto a instrucciones como a datos, tienden a estar agrupadas.

Carga de un programa en memoria.

Dirección lógica o simbólica: referencia a una localización de memoria independiente de la asignación actual de
datos a la memoria. Habrá que traducirlo a memoria física.
Dirección relativa: caso particular de dirección lógica, en la cual la dirección se expresa como una localización
relativa a algún punto conocido.

Dirección física: localización en memoria principal.

Las direcciones simbólicas deben traducirse a relativas y absolutas. Esta traducción se puede hacer en varios
momentos:
En tiempo de compilación: el programa es poco flexible, el cargador recibe el programa con sus direcciones
absolutas. Se debe conocer el esquema de memoria del sistema a la hora de hacer el programa.
6

En tiempo de carga: el cargador se encuentra con un programa que contiene direcciones relativas y va a sumarle la
dirección de comienzo a cada dirección relativa. Pero si tuviéramos que sacar el programa de memoria, a la hora de
volver a memoria, tiene que hacerlo en el mismo sitio.

En tiempo de ejecución: A medida que van haciendo falta las direcciones se van traduciendo, estén estas expresadas
Se forma simbólica o relativa.

Funciones del administrador de la memoria.

Las funciones del administrador de la memoria son las siguientes:

- Llevar el control de toda la memoria, de las partes que están en uso y de que partes están disponibles.
- Asignar y desasignar memoria a los procesos, según la necesiten.
- Determinar donde va a situar los procesos en memoria principal.
- Gestionar el intercambio entre memoria principal y secundaria.

Requisitos del administrador de memoria:

- Proporcionar reubicación de procesos, posibilidad de que un proceso pueda cambiar a otra zona de memoria.
- Proporcionar protección de los espacios de memoria de cada proceso, no permitir que un proceso acceda a
direcciones de memoria que no le correspondan.
- Proporcionar compartición de los procesos que se ejecutan simultáneamente, a nivel de código y datos.

Esquemas de asignación de la memoria principal.

Máquina desnuda

Asignación contigua Monoprogramación

Fijas

Particiones Variables
Esquemas de gestión
Sistema compañero
de memoria.

Paginación

Asignación no contigua Segmentación

Segmentación paginación

Sistemas de monoprogramación.
7

Sólo hay que proteger el espacio de memoria del sistema operativo. Es necesario un registro límite que será protegido,
el cual posee la dirección límite a la que puede acceder el usuario.

Sistemas de multiprogramación con particiones fijas.

Requiere políticas de gestión de memoria que permitan la colocación simultánea de más de un proceso en memoria.
Se divide el espacio físico de direcciones en un número determinado de particiones de tamaño fijo. El número y
tamaño de las particiones se determina en tiempo de generación del sistema.

Selección del tamaño de las particiones.

Va a determinar el grado de multiprogramación y el tamaño máximo de los procesos.

Algoritmo de colocación.

Si son del mismo tamaño no hace falta un algoritmo. Pero si las particiones son de distintos tamaños, podemos utilizar
una cola independiente para cada partición, o una única cola para todas las particiones con los siguientes algoritmos:
- Primer ajuste.
- Siguiente ajuste.
- Mejor ajuste.
- Peor ajuste.

Protección de las particiones.

Se emplean uno de los dos métodos siguientes:

- Dos registros límites, superior e inferior.
- Registro base y longitud de la partición.

Cada vez que una dirección es traducida, el hardware del sistema comprueba que está dentro de los límites del proceso
y en caso erróneo se produce una interrupción

Fragmentación.

Es el espacio de memoria que no es utilizado por ningún proceso. Existen dos tipo de fragmentación:
- Interna: Es la memoria que tiene asignada un proceso pero no la utiliza. Es el espacio no utilizado de la
partición.
- Externa: Memoria que no está asignada a ningún proceso y que no se puede asignar por no existir un proceso
del tamaño adecuado.

En sistemas con particiones fijas, se dan ambas fragmentaciones. Un sistema con una única cola de procesos tendrá
menos probabilidad de tener fragmentación externa que un sistema con una cola de procesos por partición. En los dos
sistemas se da fragmentación interna.

Elementos de control.
8

Se usa una tabla de particiones con tres datos por entrada:

- Registro base.
- Tamaño de la partición.
- Estado: libre o asignada.

Inconvenientes.
- Restricciones de tamaño: El programa más grande que podemos ejecutar será el de la partición más grande.
- Fragmentación externa.

Multiprogramación con particiones variables o dinámicas.

Las particiones son variables en tamaño y número. Un programa no puede estar en varias particiones a la vez, es
contigua. Los programas ocupan el espacio de memoria física que realmente necesitan. No existe fragmentación
interna.

Compactación.

Consiste en agrupar todo el espacio libre en una sola zona, desplazando todos los programas a una zona de memoria.
Requiere reubicación dinámica de las direcciones. No produce fragmentación externa.

Inconvenientes:

- Durante la reubicación no se puede hacer otra cosa, el sistema se para. No es válido para STR.
- Consume muchos recursos del sistema.
- Requiere gran cantidad de tiempo.

La compactación se puede realizar según los siguientes criterios:

- Cada vez que termina un proceso. Es muy costosa.

- Cuando tengamos un porcentaje de la memoria ocupada (70-80%). Es algo menos costosa, pero puede ser
innecesaria.
- Cada cierto intervalo de tiempo. También puede ser innecesaria.
- Cuando existan procesos esperando. Es la mejor. Tiene que estar comprobando si hay procesos a la espera.

Algoritmo de colocación.

Se utilizan los mismos algoritmos que para los sistemas con particiones fijas.

Mecanismos de control del uso de la memoria.

9

Hay dos mecanismos para representarla:

Mapa de bits.

La memoria se divide en unidades de asignación. Puede variar según el sistema. A cada unidad de asignación se le
hace corresponder un bit del mapa de bit.
- bit = 0 -> Unidad libre
- bit = 1 -> Unidad ocupada.

Las operaciones de asignación y desasignación se pueden realizar rápidamente. Pero es difícil de gestionar la
búsqueda de huecos de un determinado tamaño.

Listas enlazadas.

Se usa una lista con los siguientes elementos:

- Tipo (P ó H).
- Dirección de comienzo.
- Longitud.
- Puntero al siguiente elemento.

Cuando termina un proceso hay que fusionar los huecos. Para optimizar esto se usa una lista doblemente enlaza: con
un puntero al anterior. Sigue teniendo problemas a la hora de encontrar un hueco muy lejos, hay que recorrer mucha
lista. Para solucionar esto se usan dos listas doblemente enlazadas, una para llevar el control del espacio ocupado y la
otra para llevar el control de los huecos libres. Es fácil encontrar huecos de determinado tamaño y la fusión de huecos
adyacentes.

La lista de huecos se puede ordenar por direcciones (primer ajuste), por tamaño (>: peor ajuste, <: mejor ajuste),...
Se puede aprovechar la misma memoria libre. El tamaño de la lista será sólo el de la lista de procesos.

El sistema compañero.

Se limita el tamaño de memoria asignada a los procesos.

Se busca en la lista de bloques libres, un bloque de tamaño 2 i. Si no hay ninguno, se coge uno de tamaño 2 i+1 y se
divide en 2 de 2i. A estos dos bloque se les llama bloques compañeros, a los dos que resultan de la división, cuando
uno se libere, se vuelven a unir, si el otro está libre. Posee una lista por cada tamaño de bloque posible:
- 64K
- 128K
- 256K ...

Paginación.

El espacio de direcciones lógicas del programa se divide en fracciones de igual tamaño denominadas páginas. La
memoria física también se divide en partes, del mismo tamaño que las páginas, denominados marcos de página.
10

Carga del programa.

Se realiza en varios pasos:

1- Se divide el espacio de direcciones del programa en páginas. Si P es el tamaño del marco de página, y T
el tamaño del programa, número de páginas es N=T/P. Se redondea por exceso.
2- Se buscan N marcos libres en la tabla de marcos. Tienen que estar todas las páginas en memoria aunque
no tienen por que estar contiguas.
3- Se asignan los marcos a las páginas, y se guarda en la tabla de páginas.

Tabla de marcos de página.

Contiene información de qué marcos están ocupados y cuales libres. Posee una entrada por cada marco de memoria
física. Sólo existe una tabla de marcos de página, con tamaño fijo. El número de marcos viene determinado por el
tamaño de la memoria física dividido por el tamaño de un marco.

Tabla de páginas.

Existe una tabla de páginas por cada proceso que hay en memoria. Se crea durante la carga del proceso. Tendrá tantas
entradas como marcos pueda tener.

Páginas compartidas.

Las tablas de páginas de p

rocesos distintos que apuntan a los mismos marcos de memoria física. En la tabla de marcos tenemos algún tipo de
contador que nos indica cuantos procesos están compartiendo ese marco, para saber cuando no está siendo usado por
ningún proceso y está libre para poder asignarle el marco a otro proceso distinto con otro código.

Protección.

Si la página tiene código, no se puede modificar, el acceso será en modo lectura. Si contiene datos se accederá en
modo L/E. Esto se representa mediante bits de protección en la tabla de páginas.Para evitar que el proceso intente
acceder a zonas de memoria que no le correspondan, se usan los bit de validez, para cada una de las entradas de
página. O registro de longitud de la tabla de página, contiene el número de páginas que posee ese proceso.

Fragmentación

Se puede dar fragmentación interna por que se le asignan páginas enteras. Por termino medio cada proceso tendrá
media página de fragmentación interna.

Tamaño de las páginas.

11

Viene determinado por la arquitectura, proporciona varios tamaños, el diseñador lo elige.

Factores que influyen a la hora de elegir el tamaño de la página:

- Fragmentación interna: cuanto más pequeña la página, menos fragmentación interna.

- Tamaño de la tabla de páginas: cuantas más pequeñas las páginas, más páginas y por lo tanto más grande las
tablas de páginas.

Si S es el tamaño medio de los procesos, P el tamaño de la página y E el número de bytes que ocupa una entrada en la
tabla de páginas:

- S/P número promedio de páginas que ocupa un proceso.

- E*S/P tamaño medio que ocupa la tabla de páginas.
- E*S/P + P/2 cantidad de memoria extra que se gasta por proceso en el sistema.

Si derivamos esto e igualamos a 0, obtenemos el tamaño de página óptimo ==> P= 2*S*E

Segmentación.

El proceso se divide en segmentos. Los segmentos pueden ser de tamaños diferentes. En la tabla de segmentos se
guarda la longitud y la dirección base de cada segmento. Hay una tabla de segmentos por cada proceso. Puede
contener también bits de protección (modo L o modo L/E). Cada vez que queremos acceder a memoria, accedemos
realmente 2 veces. Para ello se usan también las TLB.La gestión del espacio libre y ocupado se puede hacer a través
de los mapas de bits o de las listas enlazadas.

Traducción de direcciones.

Las direcciones lógicas vienen dadas por el número del segmento y por el desplazamiento. Registro STLR: longitud de la tabla de
segmentos, STBR: dirección base de la tabla de segmentos.

En un sistema donde las direcciones lógicas constan de m bit y el tamaño máximo del segmento es 2 n:
1- Se extrae el número de segmento de los (m-n) bits más a la izquierda de la dirección lógica.
2- Se comprueba si ... comparándolo con el registro de longitud de la tabla de segmentos.
3- Se usa el número de segmento como índice en la tabla de segmento, y
4- Se compara el desplazamiento, ... , con la longitud del segmento. Si el desplazamiento es mayor, sería
una dirección no válida.
5- La dirección física se obtiene sumando a la dirección base del segmento, el desplazamiento.

Características de la segmentación.

- Se requieren dos accesos a memoria.

- Las direcciones físicas se van a obtener en tiempo de ejecución  procesos reubicables.
- Se requiere una política de colocación de procesos en memoria.
- No se da fragmentación interna, pero sí externa.
- Los segmentos se pueden compartir
12

Segmentación paginada.

La memoria se divide en segmentos, pero a su vez estos segmentos, se dividen en páginas del mismo tamaño. Se
elimina la fragmentación externa y el algoritmo de colocación de los segmentos en memoria.

La dirección lógica está formada por tres componentes: número de segmento, número de página y desplazamiento. Se
tiene una tabla de segmentos por proceso y una tabla de páginas por cada segmento del proceso.

Memoria virtual.

Estructuras hardware y de control en la memoria principal.

Tabla de mapa de página.

Cada entrada en la tabla posee los siguientes elementos:

- Número de página.
- Número de marco.
- Bit de fallo: indica si la página se encuentra en memoria principal o no.
- Bit de modificación: indica si la página ha sido modificada o no.
- Bit de referenciado: indica si la página ha sido recientemente referenciada.
- Bit de protección: indica las operaciones permitidas.
- Bit de bloqueo: indica si el marco de página está o no bloqueado.

Tabla de mapa de fichero.

Su función es indicar al sistema en qué lugar de la memoria secundaria se encuentran las páginas de un proceso. Habrá
una entrada por cada página del proceso, con los siguientes elementos:
- Número de página.
- Posición en memoria secundaria.

Tabla de marcos de página.

Su función es llevar el control de los marcos que están libres y ocupados. Cada entrada tiene los siguientes elementos:
- Número de marco.
- Identidad del programa.
- Número de página.
- Bit de estado.
- Bit de referencia.
- Bit de cambio.

Implementación de la tabla de página.

 En conjunto de registros especializados.

Si el número de páginas es pequeño. Cada cambio de contexto hay que realizar la carga de los registros. Solo es
posible en sistemas con pequeña memoria.

 En memoria principal.
13

Si el número de páginas posibles es alto. Inconvenientes:

- Para acceder a una posición de memoria necesitamos dos accesos a memoria.
- Se ralentiza el acceso a memoria por un factor de dos

 En memoria caché (TLB).

En estas memorias no estarían las tablas completas, sino las entradas correspondientes a las páginas más usadas. El
sistema buscaría primero en esta tabla rápida la página buscada.

La búsqueda en la memoria caché no se realiza por indexación, sino que es una búsqueda por contenido. En el TLB no
están todas las páginas de cada proceso. Cada entrada en la TLB tiene que incluir el número de la página .

Métodos de reducción del tamaño de las tablas de página.

 Tablas de páginas de múltiples niveles.

Ejemplo:
un sistema con una espacio de direcciones lógicas de 32 bits y con un tamaño de página de 4kb (2 12)
necesita:
232/212 = 220 entradas en la tabla de páginas (1.048.576). Si cada entrada tiene 4 bytes, necesita 4Mb.

Para disminuir el tamaño de las tablas de página se implementan tablas de más de un nivel.