Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Untitled Prezi

No description
by

Alexandra Libreros

on 29 May 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Untitled Prezi

Multiprogramación con particiones variables Sebastian Betancourt
Hanner Delgado
Alexandra Libreros
Alejandro Montenegro
Iván Morán
Erick Palacios
Fredy Salazar Esquema de memoria
La memoria se asigna mediante dos mecanismos, cuando un proceso se ramifica y mediante una llamada a exec. *La memoria se divide en bloques de diferente tamaño de acuerdo a las necesidades del proceso.
*Define bloques del tamaño requerido.
*Termina con la fragmentación interna.
*Permite un mejor uso de la memoria. Archivos de cabecera El programa principal ADMINISTRACIÓN DE LA MEMORIA Estructuras de datos y algoritmos que administran la memoria La tabla de procesos del administrador de memoria se llama mproc. El campo más importante es el arreglo mp_seg, el cual tiene tres captaciones, para los segmentos de texto, datos y pila. Consiste en traer a la memoria todo un proceso en ejecución durante un tiempo y después de la ejecución volverlo al disco duro. Memoria Virtual El S.O. mantiene en memoria aquellas partes del programa que se deben permanecer en memoria y el resto lo deja en disco, las partes entre el disco y la memoria se intercambian de modo que se vayan necesitando. Administración de la Memoria Algoritmos de Sustitución de Páginas Panorama General de la Administración de la Memoria en MINIX Intercambio La administración de memoria se refiere a los distintos métodos y operaciones que se encargan de obtener la máxima utilidad de la memoria, organizando los procesos y programas que se ejecutan de manera tal que se aproveche de la mejor manera posible el espacio disponible. Distribución del espacio para intercambio Se refiere a la asignación de espacio en disco para un proceso. Usados por el sistema operativo cuando ocurre una falla de página, para escoger qué página se sacará de la memoria y pueda entrar una nueva. La memoria se asigna mediante dos mecanismos: Cuando se hace una llamada Fork o Exec Esquema de la memoria Manejo de mensajes La creación de un proceso se efectúa por Fork, que se ejecuta como una serie de pasos, como se muestra: Llamada al sistema FORK Cuando el proceso padre realiza una llamada a WAIT, se libera la ranura de la tabla de procesos, y se informa al sistema de archivo y al kernel. Llamada al sistema EXEC Permite alistar la memoria para la ejecución del proceso. Ésta ejecuta su trabajo en una serie de pasos, como se muestra: Llamada al sistema EXIT Esta llamada permite liberar los recursos de la memoria usados por el proceso y alistar el proceso para ser eliminado. Administración de memoria con mapas de bits *Con un mapa de bits, la memoria se convierte en una unidad de asignación.
*Ofrece un método sencillo para contabilizar las palabras en una cantidad fija de memoria. Administración de memoria con listas enlazadas *Lista enlazada de segmentos en ejecución y libres.
*Cuando se ejecuta o termina un proceso la lista se actualiza fácilmente. Administración de la memoria con Sistema Compañero Es un algoritmo para el direccionamiento con el objeto de acelerar la unión de cavidades adyacentes cuando un proceso termina o se intercambia. * Fragmentación interna.
* Tamaño de página óptimo: El modelo del conjunto de trabajo Está diseñado para reducir considerablemente la tasa de fallas de página.

* Paginación por demanda:
Se arrancan los procesos sin ninguna página en memoria.
Cuando se inicia, se produce un fallo de página.
Transcurrido cierto tiempo, el proceso tiene en memoria todas las páginas que le hace falta.

* Localidad de referencia.
* Conjunto de trabajo. Políticas de asignación local versus global Algoritmos de reemplazo de paginas:

* Local: asignan a cada proceso una fracción fija de la memoria.
* Global: asignan marcos de paginas de manera dinámica entre los procesos ejecutables. Tamaño de la página Aspectos de la implementación * Participación del sistema operativo en la paginación:

Al crear un proceso
Al ejecutar un proceso
Al ocurrir un fallo de página
Al terminar un proceso * Respaldo de instrucción

* Bloqueo de páginas en memoria * Almacén de respaldo * Separación de política y mecanismo

Un manejador de la MMU de bajo nivel.
Un manejador de fallos de página que forma parte del kernel.
Un paginador externo que se ejecuta en espacio de usuario. Llamada al sistema WAIT Consiste en ejecutar un solo programa a la vez, repartiendo la memoria entre ese programa y el sistema operativo. Monoprogramación sin intercambio ni paginación Multiprogramación con particiones fijas Consiste en dividir la memoria principal en n partes posiblemente de distinto tamaño pero aún así se obtiene el desperdicio de particiones grandes con una tarea pequeña. Llamada al sistema BRK Los procedimientos de biblioteca brk y sbrk se utilizan para ajustar el límite superior del segmento de datos. Manejo de señales El administrador de la memoria también maneja algunas otras llamadas al sistema simple:

Getpid Getuid

Getgid Setuid

Setgid Segmentación Los archivos de encabezado contienen las declaraciones de constantes, variables y funciones de las que consta el módulo, asi como llamadas a otros archivos de encabezado necesarios.

Los archivos dentro de los directorios include/ e include/sys/ se llaman de cabecera o encabezado (header files) y tienen extensión .h; se los incluye mediante la sentencia #include en los fuentes C. La segmentación organiza la memoria virtual como una colección de unidades de tamaño variable llamadas segmentos.
Los distintos segmentos son independientes y pueden agrandarse o encogerse sin afectarse entre si. Tablas de página

Realiza las traducciones de direcciones de memoria virtual a memoria física y en general el sistema operativo mantiene una por cada proceso corriendo en el sistema. Tablas de página multinivel Consiste en evitar mantener todas las tablas de página en la memoria en particular, las tablas que no se necesiten no deben estar ahí.
Su objetivo es superar el problema de tablas de páginas enormes en la memoria todo el tiempo. Ventajas de un espacio de direcciones segmentado: * A la estructura de datos se le puede asignar a su propio segmento y el S.O expandirá o reducirá el segmento cuando se necesite.
* Permite modificar y recopilar los programas independientemente, sin que sea necesario recopilar o volver a montar el conjunto de programas por completo.
* Se presta a la compartición entre procesos.
* Se presta a la protección. Otras llamadas al sistema Implementación de la Administración de la Memoria en MINIX El administrador de memoria se compila y enlaza de manera independiente, por lo tanto tiene un programa que lo inicializa.

El administrador de memoria se inicializa llamando a mm_init. Implementación de FORK, EXIT y WAIT Las llamadas al sistema fork, wait y exit se implementan con los procedimientos do_fork, do_mm__exit y do_wait que están en el archivo forkexit.c. Pasos que se siguen para hacer un FORK EXIT Pasos que sigue un WAIT 1. Iniciación del WAIT.
2. Examinar la tabla de procesos para saber si tiene hijos.
2.1. Si tiene hijos.
2.1.1. Verifica si son zombies.
2.1.1.1. (Si son zombies) se limpian y se envía respuesta que el hijo se ha detenido.
2.1.1.2. (Si no son zombies) se mira si el padre no quiere esperar, si no es así se espera a que el hijo termine.
3. Se despierta al padre del wait.
4. Se libera el espacio que ocupaba el hijo. Implementación de EXEC Implementación al sistema BRK Tabla de cavidades del administrador de memoria, HOLE. Cada captación de la lista de cavidades tiene tres campos: la dirección de base de la cavidad, en pulsos; la longitud de la cavidad, en pulsos; y el apuntador a la siguiente captación de la lista. Estructuras de datos y algoritmos que administran la memoria Paginación Consiste en dividir los programas en pequeñas partes o páginas. Del mismo modo, la memoria es dividida en trozos del mismo tamaño que las páginas llamados marcos de página.

El sistema operativo mantiene una lista de los marcos disponibles y una tabla por cada proceso, donde consta en qué marco se encuentra cada página del proceso. Paginación en memoria virtual La forma de llamarlo es la siguiente:

intbrk(void*end_data_segment) Consiste en guardar algunas paginas de un proceso en la memoria secundaria para asi liberar espacio en la memoria principal. estas paginas se van intercambiando entre la memoria fisica y la memoria virtual segun de vayan necesitando. Evento que interrumpe la ejecución normal de un proceso
Pueden manejarse (es decir, programarlas para obtener un comportamiento diferente)
La mayoría de las señales pueden filtrarse mediante una máscara Las señales son un mecanismo para comunicar eventos a los procesos
Cuando un proceso recibe una señal, la procesa inmediatamente
Cuando un proceso recibe una señal puede:
Ignorar a la señal
Invocar la rutina de tratamiento por defecto
Invocar una rutina de tratamiento propia Implementación de Utilería Hay ocho tipo de llamadas relacionadas con señales las cuales son:

* SIGACTION: Modifica la respuesta de una señal futura
* SIGPROCMASK: Cambia el conjunto de señales bloqueadas
* KILL: Envía una señal a otro proceso
* ALARM: Se envía a si mismo la llamada alarm después de un retardo
* PAUSE: Se suspende a si misma hasta una señal futura
* SIGSUSPEND: Cambia el conjunto de señales bloqueadas, luego PAUSE
* SIGPENDING: Examina el conjunto de señales pendientes (bloqueadas)
*SEGRETURN: Hace aseo al terminar el manejador de señales Implementación de Manejo de Señales Pasos que realiza un FORK Aspectos de Diseño para Sistemas de Paginación MMU La unidad de gestión de memoria o unidad de manejo de memoria (Memory Management Unit), es un dispositivo hardware que tiene como principal función convertir las direcciones virtuales a direcciones fisicas. Detalles de una entrada de la tabla de paginas Numero de marco de pagina: hace referencia a la ubicación de la pagina en la memoria .
Bit presente/ausente: si este es 1 la entrada es valida y puede usarse y si es 0 la pagina no esta ubicada actualmente en la memoria.
Bit modificada: 1- cuando se ha escrito en ella (pagina "sucia") 0- cuando No (Pagina "limpia").
Bit protección: 1- solo lectura y 0- lectura/escritura.
Referida: su propósito es ayudar al sistema a escoger la pagina que desalojara la memoria cuando ocurre un fallo de pagina. Asignación de un PID.
*calcula la oscilación del proceso* Translation Lookaside Buffer TLB (buffer de consulta para traducción) es un dispositivo hardware ubicado generalmente en la MMU, que transforma direcciones virtuales en físicas sin pasar por la tabla de paginas Tablas de pagina invertida Consiste en tener una entrada por cada marco de pagina, en vez de una entrada por cada pagina, por lo tanto habrá solo una tabla de paginas y no una por cada proceso.

Ventaja: Ahorra enormes cantidades de espacio.

Desventaja: aumenta el tiempo de búsqueda de páginas ya que se debe explorar cada entrada de la tabla cada vez que hay una referencia a una página.
Su solución es usar el TLB para contener las paginas que se usan mucho. Setuid y setgid:
"Set User ID" y "Set Group ID"
*permisos de acceso a los directorios* Algoritmo de sustitución de páginas First In, First Out (FIFO) Se mantiene una lista de todas las páginas que están en la memoria. Cuando hay una falla de página, se elimina la página que está a la cabeza de la lista y se agrega la nueva página al final. Control de Página Cuando se da la sobrepaginación la única solución real es deshacerse temporalmente de algunos procesos.

Se usa el intercambio para reducir la demanda potencial de memoria. Simulación de LRU en software Para cada página, el bit R, que es O o 1, se suma a un contador en software asociado a cada página y que inicialmente vale 0 (NFU). Una modificación de NFU llamada maduración hace que pueda simular LRU, la cual consta en que todos los contadores se desplazan a la derecha un bit, antes de sumarles el bit R y luego el bit R se suma al bit del extremo izquierdo. Cuando ocurre una falla de página, se elimina la página que tiene el contador más bajo. Espacios separados de instrucciones de datos Segmentación con paginación: Multics Es la combinación de estos dos métodos, se trata de ver a cada segmento como una memoria virtual y paginarla.combinando así sus ventajas
Tamaño de pagina uniforme si necesidad de mantener todo el segmento en memoria.
Facilidad de programación, protección y compartición.

Cada proceso maneja una tabla de segmentos.
La tabla de segmentos tiene una entrada llamada descriptor de segmento.
Cada descriptor(o entrada) contiene información si el segmento están en memoria principal. Páginas compartidas * Si hay varios usuarios ejecutando el mismo programa a la vez, es más eficiente compartir las páginas para evitar tener dos copias de la misma página en memoria al mismo tiempo.
* No todas las páginas se pueden compartir. Algoritmo de sustitución de páginas usadas menos recientemente (LRU) Hay diferentes formas de implementar LRU, consideremos dos de estas:
La primera consiste en utilizar una tabla de páginas donde se almacena un contador de 64 bits (C) que se incrementa automáticamente después de cada instrucción. En un instante dado, el contador de la tabla de páginas más bajo será la página menos recientemente utilizada. La segunda consiste en utilizar una matriz de n x n bits, que inicialmente son cero. Cada vez que se hace referencia al marco de página k, el hardware pone primero en 1 todos los bits de la fila k, y luego pone en O todos los bits de la columna k. En un instante dado, la fila cuyo valor binario sea el más bajo, será la de la página menos recientemente utilizada. Así, cuando ocurra una falla de pagina en ambos casos, se desalojara la pagina menos recientemente utilizada. Política de limpieza DEMONIO DE PAGINACIÓN:

*Proceso en segundo plano que asegura una provisión abundante de marcos de página libres.

*Se despierta en forma periódica para inspeccionar el estado de la memoria.

*Recuerda el contenido anterior de la página. Segmentación pura Difiere de la paginación en que las paginas son de tamaño fijo en cambio en la segmentación no.
Disminuye la fragmentación externa Algoritmo de sustitución de páginas óptimas (OPT, MIN) Teóricamente perfecto, imposible de implementar, el algoritmo plantea que las páginas pueden rotularse con el número de instrucciones que se ejecutarán antes de que se haga referencia a esa página, entonces cuando ocurre un fallo de pagina, se debe eliminar la página que tenga el rótulo más alto. Algoritmo de sustitución de páginas no usadas recientemente (NRU) o Segunda oportunidad mejorada El algoritmo NRU cuando ocurre una falla de página, examina todas las páginas y las divide en cuatro categorías con base en los valores actuales de sus bits R y M:

(0, 0) - No ha sido utilizado ni modificado recientemente. Candidata ideal para su reemplazo.
(0,1) - No ha sido utilizada recientemente, pero está modificada. No es tan buena opción, porque es necesario escribir la página a disco antes de reemplazarla, pero puede ser elegida.
(1,0) -El marco está limpio, pero fue empleado recientemente, por lo que probablemente se vuelva a requerir pronto.
(1,1) -Empleada recientemente y sucia — Sería necesario escribir la página a disco antes de reemplazar, y probablemente vuelva a ser requerida pronto. Hay que evitar reemplazarla. Paginación maneja un esquema de
direcciones virtuales lineales.

Su direccionamiento es por numero de segmento y direccion dentro del segmento
1. Se usa el número de segmento para encontrar el descriptor de segmento.
2. Se verifica si la tabla de página está en la memoria. Si es así, se le localiza; si no, ocurre una falla de segmento.
3. Se examina la entrada de tabla de páginas que corresponde a la página virtual solicitada. Si la página no está en la memoria, ocurre una falla de página; si está en la memoria, se extrae la dirección (se extrae el marco de pagina)
4. Se agrega a la dirección del marco el desplazamiento dentro de la página virtual.
5. Finalmente se efectúa la lectura o el almacenamiento. Al ocurrir una referencia en memoria son llamadas a procesos muy utilizados (utileria) y estas son 4:

* alloc_mem: solicita un bloque de memoria de cierto tamaño

* free_mm: liberar memoria que no esta siedo utilizada

* max_hole: calcula el agujero mas grande disponible

* mem_init: inicializa la lista libre cuando el adm. comienza a ejecutarse Las interrupciones de reloj no borran el bit M esta información se necesita para determinar si hay que reescribir en disco la página o no. (El algoritmo del reloj es una modificación al de segunda oportunidad) El algoritmo de segunda oportunidad es una modificación sencilla de FIFO que evita el problema de desalojar una página muy utilizada consiste en inspeccionar el bit R de la página más vieja. Si es O, sabremos que la página, además de ser vieja, no ha sido utilizada recientemente, así que la reemplazamos de inmediato. Si el bit R es 1, se apaga el bit, se coloca la página al final de la lista de páginas, y se actualiza su tiempo de carga como si acabara de ser traída a la memoria. Luego continúa la búsqueda. El algoritmo dice que se desalojará la página que haya estado más tiempo sin usarse.
Full transcript