SEGMENTACIÓN Y SEGMENTACIÓN CON PAGINACIÓN

Segmentación

· Esquema de administración de memoria que  soporta la visión del usuario de la memoria

      · Un programa es una colección de segmentos.

      · Un segmento es una unidad lógica como por ejemplo:

BIT residencia de segmento

Dirección auxiliar  no está en Memoria real

Longitud del segmento

Bits de protección

Arquitectura de la segmentación

Las direcciones lógicas dse conforman por una dupla:

Numero de segmento

Segmentación con Paginación

      

        · INTENTA aunar lo mejor de los dos esquemas.

        · La segementacion proporciona soporte directo a las regiones del proceso y la paginación permite un mejor       aprovechamiento de la memoria y una base para construir un esquema de memoria virtual

El Pentium soporta hasta 16K segmentos, cada uno hasta 2 ala 32 bytes de direccionamiento virtual. Puede determinarse por SO usar solo segemntacion, solo paginación o ambos.

Política de recuperacion

       · Determina cuando una pagina se debería traer a la memoria principal

       · Con paginación bao demanda(demand paging), solo se trae a memoria cuando se hace referencia  una     posición en dicha pagina

Algoritmos de reemplazo de paginas

Las faltas de pagina forzan el cambio:

      · Que pagina debe ser removida

      · Establecer espacio para ña pagina que entra

       Las paginas modificadas deben ser guardadas las otras pueden sobrescribirse

      · Es aconsejable no sobrescribir una pagina que se utiliza muy a menudo.

Algoritmo optimo de reemplazo de pagina

Reemplaza la pagina que se requerirá en el punto mas lejano

      · Optimo pero no lograble.

Algoritmo de pagina no recientemente utilizada(NRU)

Cada pagina tien un bit de referencia, un bit de modificación:

Las paginas se clasifican:

1.       No referenciadas no modificadas

2.       No referenciadas, modificadas

3.       Referencidas, no modificadas

4.       Referenciadas, modificadas

FIFO

Conservar una lista encadenada de todas las paginas en el orden en que llegaron a memoria


·Trata los marcos de pagina ocupados como se se tratase de un buffer.

Este método sufre de la anomalía de Belady (mayor numero de marcos de pagina mayor es la cantidad de fallos de pagina)

Reloj, segunda oporunidad

Lista circular. Si la pagina tien el bit de referenci en uno lo desmarca y lo pone en cero y si no ha sido usada se saca de memoria y se reemplaza por una nueva pagina.

LRU(least recently used)

Envejece las paginas menos usadas para sacrlas de primero cuando sea necesario.

Algoritmo del conjunto de trabajo

Historial de paginas por un current time, y cuano se hace una solicitud de pagina se reccoren todas las paginas, y si el bit de referenci esta en uno se colocan al final, como protegidas, si esta en cero y supera un tiempo determinado de tiempo es la pagina estimada para salir. Se le asigna un numero y entre mas peuqño mas es sensible  a salir.

Reloj mejorado

Utiliza dos bits de referenciado o no y modificada o no según eso se hace el reloj.

Otros algoritmos de reemplazo:

El aleatorio: saca cualquier pagina al azar.

No frecuente mente usada: un contador cuando se reinicia se cuenta en el contador. 

Envejecimiento: compensación por recientemente utilizada. 

Menos usada recientemente: un contador de menos usadas.

Reemplazo de paginas mas lejanas (fpr): 

en un árbol la que este mas alejada de la raíz, reemplazante

Windows XP

Utiliza una paginación por demanda con clustering. Trae las paginas alrededor de la pagina fallada.

A  los otros proceso se les asigna un workering set mínimum y un working set maximun.

Alejo carepinga

El minimo garantiza que el proceso se puede tener en memoria.

A un proceso se le puede asignar tantas paginas hats alcanzar su conjunto máximo de paginas.

SOLARIS

Mantien una lista de paginas libres para asignarle a los proceso con faltas de pagina.

Lots free limite o umbral para empezar a paginar

Des free limite umbral para aumentar la paginacion

Min free. El otro no me acuerdo.

LINUX

Utiliza el algoritmo del reloj con una variante.

Con una lista de activas e inactivas y solo saca de la lista de inactivas.

PAGINACIÓN

PAGINACIÓN 

División de páginas de los espacios de memoria

El espacio virtual se divide en páginas.

Algunas páginas están en memoria principal.

· El SO se encarga de que estén en memoria principal las paginas necesarias

· Para ello trata los fallos de página producidos por la MMU.

A

B

C

D

E

F

G

H

Memoria lógica

 Marco

4	V
	I
6	V
	I
	I
9	V
	I
	I

 Bit valido invalido

Esquema de traducción de direcciones

· Las direcciones generadas por la CPU se dividen en

· Numero de pagina (p)- utilizado en la tabla de páginas que contiene las direcciones base de cada página en la memoria física.

· El desplazamiento de página (d)- combinado con la dirección base definen la dirección de memoria física que es enviada a la unidad de memoria.

· traducción: proceso referencia (p,d), se busca en la tabla de correspondencia de páginas para ver la p’ (p real), la dirección real es p’+d. por agilidad tabla



Elementos de la tabla de páginas

Desactivada cache

Referenciada

Modificada

Protección

Presente /ausente

N° de marco/swap

Otras informaciones

· Copia en escritura

· Edad

· No pagina (fija en memoria fija)

· Rellenar a ceros



Buffer de traducción anticipada (TBL)

· la tabla de páginas se mantiene en memoria principal.

· El registro base de la tabla de páginas (PTBR) señala la tabla de paginas

· El registro de longitud de la tabla de páginas (PRLR) indica el tamaño de la tabla de páginas.

· Toda memoria virtual puede causar dos accesos a memoria física

· Uno para buscar en la tabla de pagina apropiada

· Uno para buscar los datos solicitados

· Para solventar este problema, la mayoría de esquemas de memoria virtual utilizan una cache especial de alta velocidad para las entradas de la tabla de pagina

· Se le denomina buffer de traducción anticipada [traslation lookaside buffer (TBL)], también llamado registros asociativos.

· Contiene aquellas entradas de la tabla de páginas ue han sido usadas de forma más reciente

· Dada una dirección virtual, el procesador primero examina la TLB

· Si la entrada de la tabla de páginas solicitada está presente (acierto en TLB), entonces se recupera el numero de marco y se construye la dirección real

· Si la entrada de la tabla de paginas solicitada no se encuentra (fallo en la TLB), el procesador utiliza el numero de pagina para indexar la tabla de páginas del proceso

· Primero comprueba si la página solicitada está todavía en la memoria principal

· Si no se encuentra en la memoria principal, se produce un fallo en la memoria, llamado fallo de pagina

· La TLB se actualiza para incluir esta nueva entrada de tabla de paginas

ASIGNACIÓN Y PLANIFICACIÓN DE MEMORIA

 Planeación de tiempo real dinámica

Ajusta las prioridades en respuesta a condiciones cambiantes, puede tener una significativa sobre carga, pero debe asegurarse que  ella no genere incumplimiento en los tiempos.

·         Dinámica basada en un plan: la factibilidad se determina en tiempo de ejecución.

·         Dinámica basada en el mejor esfuerzo: no se realiza análisis de factibilidad. El sistema trata de cumplir con todos los plazos y abandona cualquier proceso ya iniciado y cuyo plazo no se haya cumplido.

Información utilizada: tiempo de activación, plazo de inicio, plazo de conclusión, tiempo de proceso, recursos requeridos, prioridad, estructura de subtareas

Las prioridades en general se basan en los tiempos límites de procesos.

·         El tiempo límite más temprano primero(EDF) earliest-deadline-first

·         Mínima laxitud primero

•       Similar EDF, pero la prioridad se basa en laxitud, la cual se basa  en tiempo límite de procesos y su tiempo restante para completar su objetivo.

La memoria principal es un dispositivo de datos a los que se puede acceder rápidamente y que son compartidos por la CPU y los dispositivos de E/S

Funciones: que memoria se está usando, quien la usa, que procesos pueden cargarse, asignación, y liberación de memoria

Vinculación de las instrucciones y los datos de memoria.

Tiempo de ejecución: la vinculación se retarda hasta el tiempo de corrida de los procesos pueden ser movidos durante su ejecución de una posición de memoria a otra.

Tiempo de carga: si se conocen las direcciones en tiempo de compilación, debe generarse código reubicable.

Tiempo de compilación: se conoce previamente la ubicación de memoria, puede generarse código absoluto, el código debe ser recompilando si la dirección de inicio cambia.

Asignación contigua

Generalmente la memoria principal tiene dos particiones.

Para el SO residente que puede ser colocado en memoria alta o baja.

Los proceso de los usuarios se colocan  el la otra partición

Asignación de partición única

Se usa el esquema de registro de reubicación áraproteger los procesos.

Asignación con múltiples particiones fijas

Particiones configuradas por usuario, predeterminadas, se uso en OS/360/MFT (multiprogramación con un numero dijo de tareas)

Recolocación: el enlazador debe determinar que direcciones recolocarse. Vs carga absoluta x parte.

Protección: bloques de 2k con clave, o registro de base y limite. Fragmentación

Asignación dinámica de las particiones,

Compresión (garbage collection): ciber CDC 40mb/seg, micro 1mb/seg.

Fragmentación: huecos después de ejecución.

Condensación: fusión de dos huecos contiguos.

Fragmentación externa: memoria que sobra (mejor  la fragmentación Externa que la interna).

Compresión: es cuando se unen dos fragmentos que no están contiguos. (solo supercomputadoras anteriormente).

Problema de la asignación dinámica de memoria

Como satisfacer la solicitud de un tamaño n a partir de huecos libres.

Estrategias de colocación:

·         Mejor ajuste: hueco que mejor quepa y < desperdicio. Busca en toda la lista (puede estar ordenada)

·         Primer ajuste: el primer hueco que le sirva. Búsqueda al principio o a partir de este punto.

·         Peor ajuste: hueco mas grande .

·         Siguiente ajuste.

·         Estrategia mas sofisticada.

Almacenamiento virtual

·         Capacidad de obtener acceso de direcciones en un espacio de almacenamiento mucho mayor que el disponible en el almacenamiento primario del sistema.

·         SO atlas, Manchester 1960.

Intercambio /swap

·         Un proceso puede intercambiarse temporalmente de memoria a un almacenamiento de respaldo y luego puede ser retornado hacia la memoria para continuar su ejecución.

·         El almacenamiento de respaldo se hace en el disco, que debe ser rápido y tener suficiente espacio para ubicar copia de todas las imágenes de memoria para todos los usuarios; debe proveer acceso directo a estas imágenes de memoria.

·         Descargar (swap out), cargar (swap in) – variante de intercambio den algoritmos de planificación por prioridad.

Fundamentos de la memoria virtual

·         El procesador utiliza y genera direcciones virtuales

·         Parte del mapa de memoria (virtual) está en disco (swap) y parte en memoria principal

·         La MMU(memory management unit) traduce las direcciones virtuales en físicas

·         La MMU produce un fallo de página(trap) cuando la dirección no está en memoria principal

·         El SO trata el fallo de página, haciendo un transvase entre la memoria principal y el área de intercambio (swap disco)

       Paginación

·         El espacio de direcciones lógicas de un proceso no necesariamente es contiguo; los procesos se ubican en memoria física donde luego quedan disponibles.

·         Se divide la memoria física en bloques de tamaño fijo llamados marcos (los tamaños son potencias de 2, entre 512 bytes y 8192 bytes).

·         Se divide la memoria lógica en bloques del mismo tamaño llamados páginas.

·         Se mantiene el rastro de todos los marcos.

·         Para correr un programa de tamaño n páginas, se requiere encontrar n marcos libres y cargar el programa.

PLANIFICACIÓN DE PROCESOS

Latencia de despacho:

El tiempo que se toma el despachador para gaparar o iniciar un proceso.

Criterios de planificación

Utilización de CPU

Rendimiento

Tiempo de entrega/estancia/retorno (turnaround time)

Tiempo de espera: tiempo que se gasta un proceso en la cola de listos

Tiempo de respuesta: tiempo desde que se manda la orden de ejecucion.

Previsibilidad: el sistema debe ser determinístico, el sistema se tiene que comportar de una manera prevista.

Ningún proceso se muere por inanición, todo proceso debe progresar

Criterios de optimización

Maximización de CPU

Máximo rendimiento

Maximizar el tiempo de entrega

Minimizar el tiempo de espera

Minimizar el tiempo de respuesta

Algoritmos de planificación

Fcfs/peps: cortos sufren, justa predecible

Sjf/spn: el siguiente proceso el más corto.

Srtn: el menor  tiempo restante, compensa cortos.

Round-robbin,rr,asignacion ciclica/turno. Equilibra fcfs/srtn, usa cola circular con fcfs/prioridades con slice/quantum para cada proceso.

Prioridad, siempre se elige de menor prioridad, compensada x prioridad envejecimiento.

Hrn, tasa de respuesta mas alta, es costosa prioridad= (w+s)/s

Mlq,colas multinivel: combinar, proceso del sistema(x prioridad), interactivos(rr), lotes(fcfs/srtn)

Mlq con retroalimentación: los procesos se pueden reubicar en diferentes colas de acuerdo a comportamiento. Los procesos limitados por procesador se envían a la cola de < prioridad, los interactivos se ubican con mayor prioridad.

Fss(fair share schedule): porción justa, o reparto equitativo, los grupos de porción juta obtiene prioridades de acuerdo a su proximidad al logro de sus metas en la utilización de recursos. Los grupos que van mal tiene > prioridad.

Planificacion fcfs

Ejemplo: proceso            tiempo de espera

                               p1           24

                               p2           3

                               p3           3

Si los proceso llegan en el orden p1,p2p3. El diagrama de gantt de ejecucion es

P1

P2

P3

0                                                                                                                                                                24          27     30

Tiempo de espera para p1=0; p2=24; p3=27

Tiempo de espera promedio= (0+24+27)/3=17

Planificación (sjf)

Hay 2 esquemas :

No expropiativo: una vez la CPU es asignada al proceso no puede ser expropiado hasta que termine su ráfaga de CPU.

Expropiativo: si llega un nuevo proceso con una longitud de ráfaga menor, que el tiempo restante del proceso en ejecución, este es expropiado. El menor tiempo restante.

Sjf/spn no expropiativo

Proceso               tiempo llegada tiempo de ráfaga

P1                                          0.0                                         7            

P2                                          2.0                                         4            

P3                                          4.0                                         1            

P4                                          5.0                                         4

Sjf/spn (no expropiativo)

P1

P2

P3

P4

0                                                                                     7      8                                                 12                                        16

Tiempo promedio de espera = (0+6+3+7)/4=4

Sjf(expropiativo)

P1

P2

P3

P2

P4

P1

0             2                   4                5                      7                                    11                                16

Tiempo promedio de espera= (9+1+0+2)/4=3

Ejemplo de rr con quantum de 20

Proceso               ráfaga de tiempo

P1                                          53          

P2                                          17          

P3                                          68

P4                                          24