1 MINIX Administración de Memoria Cátedra: Diseño e Implementación de Sistemas Operativos UTN-FRSF Tomado de: Sistemas Operativos Diseño e Implementación - A.S.Tanenbaum

2 Estructura de MINIX Microkernel Estructura en 4 CapasGestión de Procesos Tareas de E/S Procesos Servidores Procesos de Usuario

3 Características División entre política y mecanismo.¿Qué proceso en qué sitio? (política)  MM Colocación de mapas de memoria para los procesos (mecanismo)  tarea del sistema-KERNEL Modelo de administración Particiones Dinámicas Política de asignación First fit

4 Características Dos modelos: Solicitud de MemoriaEspacio I&D combinado Espacio I&D separado Solicitud de Memoria llamada al sistema EXEC Llamada al sistema FORK

5 Después que el hijo realiza EXECCaracterísticas B A Minix Límite superior de la memoria Situación inicial B A Minix Hijo de A Después de un FORK B A Minix C Después que el hijo realiza EXEC

6 Vectores de interrupciónMapa de memoria Mapa de memoria una vez cargado el SO Espacio para programas de usuario Disco RAM INIT File System Memory Manager Kernel Tarea de terminal Tarea de disco Tarea de reloj Tarea de Hardware Manejo de los procesos Espacio sin usar Vectores de interrupción

7 Segmentos de un procesoPILA DATOS TEXTO Brecha Uso total de memoria Crecimiento de la pila Crecimiento de los datos Símbolos Datos Texto Cabecera Segmentos de un proceso Un proceso en la memoria (I&D combinados)

8 Un proceso en la memoriaTexto no compartido (segmentos T&D Combinados) Cómo aparece la información en el campo p_map de la tabla de procesos en caso de: Texto no compartido (segmentos T&D Separados)

9 Un proceso en la memoriaT&D separados (se comparte texto)

10 Manejo de mensajes Al igual que todos los componentes de MINIX, el MM es impulsado por mensajes La estructura algorítmica del MM: Inicialización while(TRUE) { Recibir un mensaje Ejecutar el procedimiento adecuado Devolver una respuesta si es necesario }

11 Manejo de mensajes TIPOS DE MENSAJESRelacionados con la asignación y desasignación de la memoria: FORK, EXIT, WAIT, BRK, EXEC Pueden afectar el contenido de la memoria KILL, ALARM, PAUSE, SIGACTION, SIGSUSPEND, SIGPENDING, SIGMASK, SGRETURN No afectan el manejo de memoria GETUID, GETGID, GETPID, SETUID, SETGID, SETSID, GETPGRP

12 Vector de procedimientos callvec[NCALLS]Manejo de mensajes Cómo sabe el MM qué hacer ante cada tipo de mensaje que le llega??? Vector de procedimientos callvec[NCALLS] Definido en table.c contiene la tabla que sirve para transformar los nros de llamada al sistema en las rutinas que las ejecutan.

13 Estructuras de datos mproc Tabla de procesos Lista de Huecos hole/usr/src/mm/mproc.h Lista de Huecos hole /usr/src/mm/alloc.c

14 Tabla de procesos src/mm/mproc.h 16307 EXTERN struct mproc {struct mem_map mp_seg[NR_SEGS]; /* ptrs a texto, datos y pila*/ char mp_exitstatus; /* estado para cuando proceso sale*/ char mp_sigstatus; /* # señal cuando un proceso reciba kill*/ pid_t mp_pid; /* id del proceso*/ pid_t mp_procgrp; /* pid para el grupo del proceso */ pid_t mp_wpid; /* pid del proceso que este está esperado*/ int mp_parent; /* índice del proceso padre*/ 16315 /* uids y gids efectivas y reales. */ uid_t mp_realuid; /* uid real del proceso */ uid_t mp_effuid; /* uid efectiva del proceso*/ gid_t mp_realgid; /* gid real del proceso*/ gid_t mp_effgid; /* gid efectiva del proceso*/ 16321 /* File identification for sharing. */ ino_t mp_ino; /* número de i-nodo del archivo */ dev_t mp_dev; /* nro. De dispositivo del file system*/ time_t mp_ctime; /* tiempo en que cambio el i-nodo*/ 16326

15 Tabla de procesos 16327 /* Información para manejo de señales*/sigset_t mp_ignore; /* 1 ignorar señal, 0 no ingnorar*/ sigset_t mp_catch; /* 1 atrapar señal, 0 no atrapar*/ sigset_t mp_sigmask; /* señales ha ser bloqueadas */ sigset_t mp_sigmask2; /* copia de mp_sigmask*/ sigset_t mp_sigpending;/* señales que están siendo bloqu.*/ struct sigaction mp_sigact[_NSIG + 1];/*as in sigaction(2)*/ vir_bytes mp_sigreturn; /* dir. de la función sigretrun */ 16335 /* Backwards compatibility for signals. */ sighandler_t mp_func; /*all sigs vectored to a sing user fcn*/ 16338 unsigned mp_flags; /* bits de bandera */ vir_bytes mp_procargs; /*ptr al argumento inic. de la pila*/ 16341 } mproc[NR_PROCS];

16 Tabla de procesos 16343 /* valores de bandera */16344 #define IN_USE /* set when 'mproc' slot in use */ 16345 #define WAITING /* set by WAIT system call */ 16346 #define HANGING /* set by EXIT system call */ 16347 #define PAUSED /* set by PAUSE system call */ 16348 #define ALARM_ON /*set when SIGALRM timer started*/ 16349 #define SEPARATE /* set is separate I&D space */ 16350 #define TRACED /*set if proc. is to be traced*/ 16351 #define STOPPED /*set if proc stopped for tracing*/ 16352 #define SIGSUSPENDED 0400 /* set by SIGSUSPEND sys. call */ 16353 16354 #define NIL_MPROC ((struct mproc *) 0)

17 La lista de huecos src/mm/alloc.c ....18820 #define NR_HOLES /* Nº DE ENTRADAS EN LA TABLA DE HUECOS*/ 18821 #define NIL_HOLE (struct hole *) 0 18822 18823 PRIVATE struct hole { phys_clicks h_base; /* DONDE COMIENZA EL HUECO? */ phys_clicks h_len; /* CUANTO OCUPA EL HUECO? */ struct hole *h_next; /* PUNTERO A LA SIG. ENTRADA EN LA LISTA*/ 18827 } hole[NR_HOLES]; 18828 18829 18830 PRIVATE struct hole *hole_head; /*PUNTERO AL PRIMER HUECO*/ 18831 PRIVATE struct hole *free_slots; /*PUNTERO A LA LISTA DE ENTRADAS LIBRES * DE LA TABLA*/ ...

18 La lista de huecos Hay dos listas:hole_head apunta a una lista enlazada de todos los bloques de memoria sin usar. free_slots apunta a una lista enlazada de las entradas de la tabla que no están siendo usadas. Inicialmente, la primera tiene una entrada por cada trozo de memoria físic, y la segunda une las restantes entradas A medida que la memoria se va fragmentando se van necesitando nuevas entradas para los nuevos huecos. Estas entradas se tomarán de la lista apuntado por free_slots

19 La lista de huecos

20 La lista de huecos Mapa de memoria y lista de huecos

21 La lista de huecos Asignación de memoria a un proceso D de 3 k

22 La lista de huecos Liberación de memoria ocupada por el proceso B

23 El programa principal Src/mm/main.c MM_init() Get_work()Reply (who, error,result2, res_ptr)

24 Src/mm/main.c 16627 PUBLIC void main() 16628 {16628 { 16629 /* Rutina principal del MM */ int error; mm_init(); /* inicializa tablas del MM */ 16635 /*loop principal del MM*/ while (TRUE) { /* espera un mensaje*/ get_work(); /* espera por una llamada la sistema */ mp = &mproc[who]; /* setea algunas banderas */ error = OK; dont_reply = FALSE; err_code = -999; /* si el nro. de llamada es válido. Ejecuta la llamada*/ if (mm_call < 0 || mm_call >= NCALLS) error = EBADCALL; else error = (*call_vec[mm_call])(); /* Devuelde resultados al usuario para indicar que terminamos*/ if (dont_reply) continue; /*no reply for EXIT and WAIT */ if (mm_call == EXEC && error == OK) continue; reply(who, error, result2, res_ptr); } 16657 }

25 Src/mm/main.c Función MM_INIT() {Crear el conjunto de señales que provocan vaciados de núcleo Obtener mapa de memoria del kernel (ver sys_getmap()) Inicializar tablas del MM Esperar que FS envie mensaje con tamaño del disco de RAM y entre en línea Inicializar listas hole_head y free_slots (ver mem_init) Imprimir información de memoria (total, minix, disco de RAM. Disponible) Indicar al FS que continue Indicar a la tarea de mem. dónde está mi tabla de proc }

26 Src/mm/main.c 16660 /*=================================*16660 /*=================================* * get_work * *=================================*/ 16663 PRIVATE void get_work() 16664 { 16665 /* Esperar por el próximo Mensaje */ 16666 if (receive(ANY, &mm_in) != OK) panic("MM receive error", NO_NUM); who = mm_in.m_source; /*origen del msg*/ mm_call = mm_in.m_type; /* # llamada al sist. */ 16670 }

27 Src/mm/main.c 16676 PUBLIC void reply(proc_nr, result, res2, respt)16677 int proc_nr; /* process to reply to */ 16678 int result; /* result of the call */ 16679 int res2; /* secondary result */ 16680 char *respt; /* result if pointer */ 16681 { 16682 /* envia una respuesta al proceso de usuario. */ 16683 register struct mproc *proc_ptr; 16685 proc_ptr = &mproc[proc_nr]; /* * Chequea si el destino esta vivo. Esta * validación debe saltearse si el que llamo es una tarea */ 16691 if ((who >=0) && ((proc_ptr->mp_flags&IN_USE) == 0 || (proc_ptr->mp_flags&HANGING))) return; 16693 reply_type = result; reply_i1 = res2; reply_p1 = respt; if (send(proc_nr,&mm_out)!= OK) panic("MM can't reply", NO_NUM); 16698 }

28 Src/mm/alloc.c Este módulo se utiliza para ubicar y liberar memoria destinada a la implementación de las llamadas FORK y EXEC Tiene la definición de la lista de huecos Los puntos de entrada al módulo son las funciones: mem_init() max_hole() alloc_mem() free_mem() Otras funciones: merge del_slot

29 Src/mm/alloc.c

30 Src/mm/alloc.c Alloc_memUbica un bloque de memoria en la lista de bloques libre usando la política First Fit. El bloque consiste en una secuencia de bytes consecutivos y su longitud viene dada en clics. Devuelve un puntero a un bloque. Es invocada cuando FORK o EXEC necesitan memoria

31 Src/mm/alloc.c 18840 PUBLIC phys_clicks alloc_mem(clicks)18841 phys_clicks clicks; /* amount of memory requested */ 18842 { register struct hole *hp, *prev_ptr; phys_clicks old_base; hp = hole_head; while (hp != NIL_HOLE) { if (hp->h_len >= clicks) { 18856/* encontramos un hueco suficientemente grande. */ old_base = hp->h_base; /*almacena el comienzo*/ hp->h_base += clicks; /* toma lo necesario*/ hp->h_len -= clicks; /* ajusta el tamaño*/ 18861/* Si el hueco se usa parcialemten, se ajusta el tamaño*/ if (hp->h_len != 0) return(old_base); /* Si se usa entero. Se lo elimina de la lista*/ del_slot(prev_ptr, hp); return(old_base); } prev_ptr = hp; hp = hp->h_next; } return(NO_MEM); 18873 }

32 Src/mm/alloc.c free_memDevuelve un bloque de memoria libre a la lista de huecos. Los parametros indican la dirección física de comienzo del bloque y su tamaño. Si el bloque es contiguo a otro anteriormente existente en la lista, el nuevo bloque es unido al bloque o bloques contiguos (ver ejemplo diapositivas 18-20)

33 Src/mm/alloc.c PUBLIC void free_mem(base, clicks)phys_clicks base; /* dirección de inicio del bloque a liberar*/ phys_clicks clicks; /* tamaño en clicks del bloque a liberar*/ { register struct hole *hp, *new_ptr, *prev_ptr; if (clicks == 0) return; if((new_ptr = free_slots)==NIL_HOLE) panic("Hole table full", NO_NUM); new_ptr->h_base = base; new_ptr->h_len = clicks; free_slots = new_ptr->h_next; hp = hole_head; /*no hay bloques en la lista o la direccion del primero es mayor?*/ if (hp == NIL_HOLE || base <= hp->h_base) { /* El bloque es el primero. */ new_ptr->h_next = hp; hole_head = new_ptr; merge(new_ptr); return; } /* Si el bloque no es el primero de la lista se busca la posición */ while (hp != NIL_HOLE && base > hp->h_base) { prev_ptr = hp; hp = hp->h_next;} /* Se encontró la posición y se inserta después de prev_ptr. */ new_ptr->h_next = prev_ptr->h_next; prev_ptr->h_next = new_ptr; merge(prev_ptr);}/* la secuencia es 'prev_ptr', 'new_ptr', 'hp' */ 

34 Src/mm/alloc.c del_Slot Borra una entrada en la lista de huecos.Se llama cuando una petición de asignación de memoria toma un hueco completo, por lo que hay que eliminar una entrada de la lista. PRIVATE void del_slot(prev_ptr, hp) register struct hole *prev_ptr; /* puntero al bloque anterior*/ register struct hole *hp; /* putnero al bloque a eliminar*/ { if (hp == hole_head) hole_head = hp->h_next; else prev_ptr->h_next = hp->h_next; hp->h_next = free_slots; free_slots = hp; }

35 Src/mm/alloc.c merge Comprueba si hay huecos contiguos y los fusiona.Los huecos contiguos aparecen después de liberar un bloque de memoria El parámetro que recibe (hp) apunta al primero de uan serie de tres huecos potencialmente fusionables

36 Src/mm/alloc.c PRIVATE void merge(hp)register struct hole *hp; /*ptr al hueco a unir */ { register struct hole *next_ptr; /*Si hp apunta al último hueco no hay fusión posible, sino se *intenta unir a su sucesor y extrae la entrada de este de la lsita*/ if ( (next_ptr = hp->h_next) == NIL_HOLE) return; if (hp->h_base + hp->h_len == next_ptr->h_base) { hp->h_len += next_ptr->h_len; /* al primer hueco se le * añade la memoria del 2do */ del_slot(hp, next_ptr); } else { hp = next_ptr; } /* Si ahora hp es ahora el último se retorna; sino se trata de unir con su sucesor*/ hp->h_len += next_ptr->h_len;

37 Src/mm/alloc.c max_hole PUBLIC phys_clicks max_hole() {/* Recorre la lista de huecos hasta encontrar el más grande*/ register struct hole *hp; register phys_clicks max; hp = hole_head; max = 0; while (hp != NIL_HOLE) { if (hp->h_len > max) max = hp->h_len; hp = hp->h_next; } return(max);

38 Src/mm/alloc.c PUBLIC void mem_init(total, free) /* Inicializa la lista de huecos*/ phys_clicks *total, *free; /* tamaños totales de memoria */ { register struct hole *hp; phys_clicks base; /* dir base del trozo de memoria*/ phys_clicks size; /* tamaños del trozo de memoria*/ message mess; /* Pone todos los huecos en la lista de huecos de memoria libres */ for (hp = &hole[0]; hp < &hole[NR_HOLES]; hp++) hp->h_next = hp + 1; hole[NR_HOLES-1].h_next = NIL_HOLE; hole_head = NIL_HOLE; free_slots = &hole[0]; /* Pide al kernel trozos de memoria y coloca cada uno de los huecos. La llamada SYS_MEM responde con la base y el tamaño del siguiente bloque y con la cantidad total de memoria. */ *free = 0; for (;;) { mess.m_type = SYS_MEM; if (sendrec(SYSTASK, &mess) != OK) panic("bad SYS_MEM?", NO_NUM); base = mess.m1_i1; size = mess.m1_i2; if (size == 0) break; /* no hay más trozos de memoria? */ free_mem(base, size); *total = mess.m1_i3; *free += size; }}