Download Descarga - CodeGaia
Document related concepts
Transcript
SISTEMAS OPERATIVOS Introduccion Definicion: Sistema operativo. Un sistema operativo es un programa o un conjunto de programas que tornan productivo, amigable y eficiente el uso del hardware de un computador, permitiendo ejecutar aplicaciones de usuario sobre este. Es el intermediario entre estas aplicaciones y el hardware. Es complicado en principio definir que es lo que forma parte de este. Una vision es incluir dentro del sistema operativo todo el paquete de software que es entregado por un fabricante cuando se compra un “sistema operativo”, pero esta vision es problemática, ya que lo que viene incluido en ese paquete varia mucho según el fabricante (Algunos fabricantes incluyen hasta navegadores de internet en el paqute mientras otros apenas proveen una interfaz de linea de comandos). La vision mas aceptada es que el sistema operativo es el programa presente en todo momento residente en memoria (el nucleo o “kernel”). Metas de un sistema operativo: • • • • Brindar un ambiente donde ejecutar los programas de usuario. Proveer un entorno sin interferencias para cada usuario. Administrar de forma equitativa los recursos de hardware y software del sistema. Hacer que el uso del sistema sea tan amigable, intuitivo y expresivo como lo permita la tecnologia actual. Tareas de un sistema operativo: Todas las aplicaciones de usuario requieren un conjunto de operaciones comunes, las que son incorporadas al sistema operativo. Por lo tanto, las tareas seran: • Proveer uno o mas entornos donde se ejecuten estas aplicaciones de usuario, • Proveer una o mas interfaces expresivas e intuitivas para el usuario (que pueden ser graficas, con ventanas, linea de comandos, web, ...), • Proveer un conjunto de operaciones accesibles a las aplicaciones de usuario a traves de una interfaz conocida como “system services”, • Administrar los recursos del computador eficiente y equitativamente. • Controlar la ejecucion de las aplicaciones de usuario para evitar errores y mal uso del sistema. La parte del sistema operativo que se encuentra residente en memoria en forma permanente es llamada “nucleo del sistema” (kernel). PERSPECTIVA HISTORICA 1. Sistemas Batch (70). Epoca en la que los ordenadores eran grandes y costosos. Tenian una entrada de trabajos y una impresora para imrpimir el resultado, no habia casi interaccion con el usuario. El sistema procesa los trabajos de a uno, y eran agrupados en batches (conjuntos de trabajos, o lotes). Las funciones comunes en este sistema eran cargar un nuevo trabajo (mediante el loader), y el trabajo con la E/S. 2. Sistemas Batch con Multiprogramacion (80). Mas adelante se incluyo soporte para multiprogramacion, para aprovechar mejor el recurso procesador. Para realizar esto, se guardaban trabajos en memoria secundaria, desde la que el sistema operativo cargaba un subconjunto de estos para ser ejecutados. Se iniciaba la ejecucion de uno de ellos, y cuando este se quedaba esperando por alguna razon (por ejemplo, la realizacion de una E/S), se otorgaba el procasador a otro proceso. Este cambio aumento el porcentaje de uso del procesador, pero implico el desarrollo de rutinas de manejo de la memoria. 3. Sistemas de tiempo compartido. Los sistemas Batch multiprogramados seguian teniendo muy baja interaccion con el usuario. Este nuevo tipo de sistemas intento mejorar este aspecto, para lo que se penso en ejecutar muchos procesos concurrentemente, realizando cambios en la asignacion del procesador muy frecuentemente, de manera que todos los usuarios que ejecutan procesos tienen la percepcion de que son los unicos presentes en el sistema. El costo de estos nuevos sistemas es la incorporacion de algoritmos de planificacion (scheduling) para asegurar una reparticion equitativa del procesador entre los procesos. La ejecucion concurrente de aplicaciones de distintos usuarios produjo la necesidad de mejorar el sistema de archivos para soportar accesos concurrentes, serializando los pedidos y incorporando tecnicas de proteccion. 4. Computadoras personales (80). El abaratamiento de los componentes de hardware hizo posible la creacion de computadores para el uso exclusivo de un usuario. Las interfaces fueron mejoradas para ser mas amigables al usuario, priorizando estas frente a la eficiencia en uso de CPU. Mas adelante las computadoras personales fueron adoptadas en el ambito empresarial, donde se generaron redes que proveen servicios a traves de servidores especializados para un uso especifico (servidor de impresion, de base de datos, etc). Se genera de esta manera una modalidad en la que las aplicaciones son desarrolladas en la modalidad cliente-servidor. 5. Sistemas Paralelos (90). Estos son sistemas donde se disponen de varios procesadores que permiten la ejecucion simultanea y sincronizada de varios procesos. Se reconocen dentro de estos sistemas dos tipos, los “sistemas altamente integrados” (tightly coupled), donde los canales de comunicación entre los procesadores son rapidos (bus comun), y “sistemas poco integrados” (loosely coupled), donde los canales de comunicación son mucho mas lentos (a traves de una red). La idea detras de estos sistemas es que al incrementar la cantidad de procesadores se podra aumentar la cantidad de trabajo hecho por cantidad de tiempo. /sin embargo, el aumento de la cantidad de trabajo realizado no es lineal respecto a la cantidad de procesadores, ya que al tener mas de un procesador se pierde cierto tiempo en la sicronizacion entre estos, y el acceso a recursos comunes. Flynn definio una clasificacion de los sistemas en funcion de cuantas instrucciones se ejecutan en simultaneo y sobre que datos. Las categorias según esta clasificacion son: • SISD (Single instruction, single data). Se ejecuta una instrucción en cada momento (no hay concurrencia). • SIMD (Single instruction, multiple data). Se ejecuta una unica instrucción pero sobre distintos conjuntos de datos simultaneamente. • MISD (Multiple instruction, sigle data). Se ulitiza para agregar paralelismo reduntante. • MIMD (Multiple Instruction, multiple data). Se ejecutan distintas instrucciones en paralelo sobre distintos conjuntos de datos. Dentro de estos sistemas existen dos variantes: ◦ Sistemas de memoria compartida: Los procesadores se encuentran en un unico nodo altamente integrado (todos comparten el bus que los conecta con la memoria). Son pocos escalables ya que con muchos procesadores el acceso a memoria (o cualquier accion que involucre el acceso al bus del sistema) se transforma en un cuello de botella. ◦ Sistemas de memoria distribuida: Los nodos son independientes (con bus y memoria independientes), y estan conectados a traves de redes de alta velocidad. Pueden abarcar miles de procesadores. 6 Sistemas Paralelos Multiprocesadores. Para estos sistemas fue necesario adaptar los nucleos de los sistemas operativos para soportar la existencia de mas de un procesador. 6.1 Sistemas multiprocesadores asimetricos: La primer solucion propuesta fue la asignacion de un procesador para ejecutar de forma exclusiva el codigo del nucleo. Esta solucion tenia la ventaja de evitar problemas de concurrencia en el codigo del sistema operativo, ya que este se ejecuta siempre en el mismo procesador. Mas adelante se fue delegando tareas del sistema operativo entre los restantes procesadores, generando una jerarquia entre estos. 6.2 Sistemas multiprocesadores simetricos (SMP): En esta solucion el codigo del nucleo se encuentra en memoria principal, y cualquier procesador es capaz de ejecutarlo. La jerarquia existente anteriormente es eliminada, llegando a un sistema en que todos los procesadores son simetricos (indistinguibles en cuanto a la capacidad de ejecutar codigo del nucleo). Esta simetria genero que el codigo del nucleo fuera escrito de manera de poder ser reentrante, para lo que los fabricantes de sistemas operativos debieron cambiar totalmente sus sistemas existentes. El acceso al codigo y a la memoria se transformaron en los cuellos de botella del sistema, y por lo tanto en el obstaculo para escalar los sistemas. Dentro de estos sistemas podemos hacer una clasificacion tambien por la manera en que se accede a la memoria. Se distinguen dos tipos: ▪ Sistemas UMA (Uniform Memory Access). Todos los procesadores tienen acceso a toda la memoria con la misma velocidad. ▪ Sistemas NUMA (Non-Uniform Memoty Access). Los procesadores tienen conjuntos de memoria a la que acceden mas rapido que el resto. 7. Sistemas Cluster. Son sistemas donde existen varios nodos fuertemente conectados, que trabajan juntos para proveer alta disponibilidad, y para distribuir la carga entre si. Los nodos se comunican para monitorear el estado de los demas. Los cluster pueden ser simetricos o asimetricos. En un cluster activo, todos los nodos realizan tareas y suplen la falla de uno de ellos, mientras que en un cluster asimetrico los nodos se dividen en dos grupos, los activos, que ejecutan las tareas, y los pasivos, que no realizan tareas hasta que suplen la falla de uno de los nodos activos. 8. Sistemas de Tiempo Real. En estos sistemas, es importante (ademas de la correctitud del resultado obtenido) que las tareas sean terminadas antes de cierto tiempo limite. Los sistemas de proposito general pueden ser adaptados para asimilar estos requerimientos (mediante el uso de prioridades dinamicas para las tareas, y despacho preemptivo). 9. Sistemas Multimedia. En estos sistemas es necesario que cierto contenido multimedia (audio y/o video) sea entregado al usuario dentro de cierto margen temporal. 10. Sistemas de Mano. (Handheld) Se especializan en entregar un conjunto importante de prestaciones al usuario contando con recursos de hardware muy limitados. ESTRUCTURA DE LOS SISTEMAS DE COMPUTACION Los sistemas tienen 3 componentes principales: CPU, Memoria, y dispositivos de E/S. • CPU. Es la encargada de de ejecutar las instrucciones de los programas. Dentro de estas instrucciones se distingue un conjunto de instrucciones privilegiadas, que solamente deberan ser ejecutadas por el sistema operativo. Dentro de este conjunto se encuentran las instrucciones de acceso a la E/S, proteccion de memoria, y memoria virtual. El procesador mantiene un bit que indica si este se encuentra en condiciones de ejecutar dichas operaciones o no. Se define un protocolo seguro para evitar que los programas de usuario puedan ejecutar con este bit activado. Este protocolo consiste en que siempre que se quiere elevar el nivel de acceso a las instrucciones se transfiere el control a codigo autenticado (trusted) que sera provisto por el sistema operativo. Concretamente, para pasar de modo usuario a modo monitor, se ejecuta un a unterrupcion a nivel de software, que provoca que el control sea transferido a la rutina de atencion de la interrupcion correspondiente. Otra medida que se implementa para evitar el mal uso (accidental o intencionado) de la CPU es el agregado de un timer que interrumpe a la CPU cada cierto tiempo. La rutina de interrupcion lleva registro de la cantidad de tiempo que estuvo activo cierto proceso, y si este supera un limite preestablecido por el sistema operativo, se quita el procesador a ese proceso y se lo entrega a otro. • Memoria. Existe una jerarquia definida sobre la memoria. En la parte superior se encuentran los registros del procesador, que poseen una velocidad alta, pero un tamanio pequenio, mientras que en la parte inferior se encuentran las cintas magneticas (que poseen un tamanio muy grande pero una velocidad de acceso muy lenta). En posiciones intermedias se encuentran (de arriba hacia abajo): Caches, Memoria Principal, y Discos Magneticos. ◦ Caches: El concepto de cache es muy importante en varios contextos distintos. La idea es mantener temporalmente una copia del contenido de una memoria en otra memoria de acceso mas rapido. El tamanio que puede almacenar la cache es menor al tamanio de la memoria mas lenta, por lo que el algoritmo elegido para poblar la cache tiene un efecto marcado sobre la performance del sistema. Un problema que se genera cuando se manejan caches en sistemas multiprocesadores es la coherencia de la cache (que la copia temporal que se mantiene de la memoria sea efectivamente lo que la memoria contiene). Este problema esta presente tambien en sistemas monoprocesador ya que un dispositivo puede cambiar el contenido de memoria, pero con mas de un procesador el problema es agravado. Tecnicas aplicadas para solucionar este problema son las denominadas write-update (todas las caches escuchan en el bus del sistema y actualizan su valor cuando otro agente realiza un cambio sobre alguna de las palabras de memoria contenidas en ellos), y write-invalidated (todos los caches escuchan el bus y marcan como no validas las palabras que son escritas por otros agentes, provocando que el siguiente acceso a esta direccion por ese procesador implique un nuevo acceso a la memoria que lo contiene). El acceso de un proceso a la memoria esta controlado de manera que un proceso solo pueda acceder a su memoria propia, y no a la correspondiente al nucleo o a otros procesos. Esto se realiza llevando un registro de las direcciones fisicas asignadas a cada proceso. • Sistema de E/S. Los dispositivos generalmente se componen de dos partes, una controlador y el dispositivo en si. El controlador es un chip que recibe ordenes del sistema operativo y envia los impulsos electricos correspondientes al dispositivo para ejecutar esas ordenes. La interfaz entre el sistema operativo y al controladora es mas simple que la presente entre la controladora y el dispositivo fisico. Dentro de un sistema existen controladores para muchos tipos de dispositivos, por lo que el sistema operativo debe implementar componentes de sotfware (drivers) para comunicarse con todas las interfaces generadas por estos controladores. Los drivers forman parte del codigo del sistema operativo. Para cargarlos existen dos alternativas: que esten ensamblados estaticamente junto al nucleo, que el sistema lea durante el arranque un archivo con los drivers a cargar, y que los drivers sean cargados en el sistema a demanda (como los modulos en linux). Los controladores tienen un conjunto de registros utilizados en la comunicación con el sistema a traves del driver. Para acceder a estos registros existen dos alternativas: Memorymapped-IO (el acceso a estos registros se realiza accediendo a direcciones especiales de la memoria principal (las que pueden ser protegidas contra el acceso no autorizado), para escribir en estas direcciones se utilizan las mismas instrucciones que para un acceso normal a la memoria), y Direct IO instructions (existen instrucciones especificas (que estaran dentro del grupo de instrucciones privilegiadas) para acceder a la informacion de los dispositivos, los que son asignados a una direccion de puerto). Para realizar una operación de de E/S existen varios metodos: Espera Activa (Polling), en que el procesador realiza un pedido y queda en un busy-waiting hasta que llega la respuesta, Interrupciones (Interrupts), en que el procesador envia el pedido y se libera para realizar otras tareas hasta ser interrumpido por el controlador indicando que este termino el trabajo, y Acceso directo a memoria (DMA), en que los dispositivos escriben directamente en la memoria principal sin la intervencion del procesador, y generan una interrupcion cuando se termino de escribir en la memoria. DMA es especialmente util en dispositivos que realizan grandes transferencias de datos (por ejemplo un disco duro), ya que el controlador puede cargar toda la informacion en RAM y luego interrumpir al procesador en lugar de interrumpirlo para copiar cada byte a la memoria, habilitando a este continuar con otras tareas. ESTRUCTURA DE LOS SISTEMAS OPERATIVOS En funcion de las tareas que el sistema debe realizar, hay algunos componentes que deben estar definidos en el sistema: • Administracion de procesos • Administracion de memoria • Subsistema de E/S • Administracion de almacenamiento secundario • Subsistema de archivos • Subsistema de red • Subsistema de proteccion Relacionado con estos componentes, el sistema debera proveer ciertos servicios (system services). Los programas seran escritos para el entorno de ejecucion que estos servicios definen. Los servicios tipicos incluyen: • Ejecucion de programas (El sistema debe ser capaz de cargar programas en memoria y ejecutarlos, reconocer su estado al momento de terminacion (terminacion normal o erronea)) • Operaciones de E/S • Manipulacion de sistemas de archivos (Operaciones para crear, borrar, leer y escribir) • • Comunicación entre procesos (Mecanismos para posibilitar la comunicación entre los procesos, a traves de memoria compartida o a traves del envio de mensajes) Manipulacion de errores (Fallos de hardware (en algun dispositivo, la memoria, la fuente de energia,...), fallos de programas, etc) El sistema puede proveer tambien servicios de asignacion de recursos, contabilizacion (accounting para llevar un registro de como es utilizado el sistema), y proteccion. System Calls La interfaz del nucleo que permite a las aplicaciones acceder a los servicios del sistema son las system calls. Por lo general, para invocar un system call, un proceso de usuario sigue los siguientes pasos: 1. Carga los parametros en un lugar apropiado. (generalmente el stack) 2. Cargar el numero de system call en un registro especifico. 3. Realizar una interrupcion por software (trap). Cuando se culmina el ultimo paso, el bit de modo del procesador es seteado en modo monitor, y el control es transferido al codigo de atencion de la interrupcion, que chequea que el numero de system call sea apropiado y llama a la rutina correspondiente a ese system call. Al culminar la ejecucion del system call, el resultado es escrito en un registro especifico, para ser leido por el proceso. Para pasar los parametros al system call, (paso 2) existen varias variantes. Estas son: • • • Los parametros se pasan a traves de los registros (se limita el tamanio y cantidad de los parametros) Los parametros se encuentran en un bloque de memoria apuntado por un registro. El proceso hace push's en el stack para guardar los parametros, mientras que el sistema operativo realiza pop's sobre el mismo stack para recuperar lo escrito por el usuario. Existen llamadas del sistema para cada uno de los servicios proporcionados por el so. Estructura del sistema Una vez que se tienen los componentes y servicios deseados bien definidos, se inicia el disenio de la estructura del sistema que dara soporte a dichos requrimientos. Desde el punto de vista de un usuario, el sistema debe ser amigable, rapido, facil de aprender y usar, seguro, etc.. Desde el punto de vista de quien debe implementar el sistema, las cualidades deseadas son que sea facil de diseniar, implementar y mantener, asi como ser confiable y eficiente. Existen varias maneras de estructurar un sistema, estas son: 1. Sistema monolitico. El nucleo no tiene una estructura bien definida, este es escrito como una colección de procedimientos accesibles globalmente. No existe “ocultacion de informacion”, ya que cualquier procedimiento del nucleo puede acceder a cualquier otra parte de este. A pesar de esta falta de compartimentacion, es posible lograr un buen disenio que genere un sistema eficiente. Ejemplos de este tipo de sistemas son MS-DOS y linux (que es un sistema monolitico con un buen disenio orientado a objetos). 2. Sistema en capas. Se organizan las funciones del sistema en capas. Cada capa define una interfaz para responder a estos servicios. En la atencion de un servicio por una capa, esta puede llamar unicamente a funciones de la capa inferior. Ademas, las funciones de una capa solo pueden ser llamadas por la capa inmediatamente superior. Dentro de esta abstraccion, la “capa 0” representa al hardware del computador, mientra que la capa mas exterior corresponde a las aplicaciones de usuario. Las ventajas de este enfoque es la modularidad obtenida, y la posibilidad de depurar cada capa por separado (iniciando por la capa mas interior, y siguiendo con el resto alejandose del centro, asumiendo en todo momento que la capa inferior funciona correctamente. Las desventajas son la complicacion en el disenio que implica la definicion de las capas y que contendra cada una, y el overhead generado por la necesidad de pasar los mensajes ente las distintas capas para atender el pedido del usuario. Un ejemplo de sistema operativo en capas es OS/2. 3. Sistema con micronucleo. Estos sistemas se componen un nucleo que provee un conjunto minimo de servicios de administracion de procesos, memoria, y comunicación entre procesos. El resto de los servicios del sistema son implementados como procesos separados del nucleo que ejecutan en modo usuario. El acceso de estos procesos al sistema se realiza a traves del envio de mensajes. Las ventajas son que aumenta la portabilidad y escalabilidad ya que encapsula las caracteristicas fisicas del sistema, para incorporar nuevos servicios no es necesario modificar el nucleo, es mas seguro ya que los servicios del sistema ejecutan en modo usuario, y que el disenio simple y funcional generalmente aumenta la confiabilidad del sistema. Un ejemplo de sistema con micronucleo es Windows. Sistemas con modulos. Los sistemas actuales utilizan modulos del nucleo. Este desarrollo aporta las ventajas de que el sistema es desarrollado con un enfoque orientado a objetos, con componentes separados de forma clara y con interfaces conocidas, y que los modulos pueden ser cargados en el modulo en tiempo de ejecucion según sea necesario. Un sistema que refleja esta idea es el sistema operativo Solaris. PROCESOS Definicion Un proceso es un programa en ejecucion. Esto incluye, pero no es igual, al codigo del programa correspondiente. Ademas de este codigo, un proceso comprende el estado de la ejecucion (el instruction pointer, el estado de la memoria). Es importante la afirmacion de que un proceso no es unicamente el codigo del programa. Un programa es una entidad pasiva, por lo general un archivo conteniendo las instrucciones a ejecutar (archivo ejecutable), mientras que un proceso es una entidad activa, con una instrucción a ser ejecutada y un conjunto de recursos asignados. Un programa se transforma en un proceso al ser cargado en memoria. Tambien para enfatizar esta diferencia, cuando se ejecuta mas de una copia de un mismo programa (se abre un mismo programa dos veces) el sistema los trata como dos procesos distintos (podran compartir codigo pero tienen memoria e instruction pointer distintos). Estado de un proceso A lo largo de la ejecucion de un proceso, este cambia de estado. El estado esta definido por la actividad actual del proceso. Los posibles estados de un proceso son: 1. New: El proceso esta siendo creado. 2. Running: Hay instrucciones del proceso siendo ejecutadas. 3. Waiting: El proceso esta esperando a que algo ocurra (una operación sobre la E/S, la recepcion de una senial, …). 4. Ready: El proceso se encuentra esperando a que le asignen el procesador para continuar ejecutando. 5. Terminated: El proceso ha terminado su ejecucion. Los nombres varian entre los distintos sistemas, y existen sistemas que definen estados mas finos que estos. Es importante notar que solo un proceso puede estar en estado Running en cada procesador, mientras que pueden existir muchos procesos en los estados Ready y Waiting. El flujo de un proceso entre estos estados viene dado por el siguiente diagrama: Process Control Block Dentro del kernel, cada proceso es representado mediante una estructura de datos llamada process control block (PCB). Dentro de esta estructura se encuentran datos sobre la ejecucion del proceso, entre los cuales se encuentran: • El estado del proceso • El valor del program counter • El valor de los registros de la CPU (El contenido de este campo es indefinido mientras el proceso se encuentra en estado running) • Valores usados por el algoritmo de scheduling • Valores referentes a la utilizacion de memoria del proceso • Informacion de accounting (informacion sobre el uso de CPU y memoria, tiempo que lleva ejecutando) • Informacion sobre el estado de la E/S (informacion sobre los dispositivos asignados al proceso, los archivos abiertos, etc) • Informacion sobre quien es el proceso que creo a este proceso • Informacion sobre los procesos creados por este proceso Creacion de procesos Todos los procesos del sistema son creados a partir de otros procesos (salvo casos especiales, como el proceso init en sistemas linux). Al proceso creador se le denomina padre y al creado hijo, la relacion padre-hijo define una jerarquia entre los procesos del sistema. Existen varias opciones respecto a que recursos comparten padre e hijo al momento de la creacion del hijo, puede ser que estos procesos compartan todo, algo, o nada. Cuando un proceso es creado, el hijo tiene un hilo de ejecucion independiente al del padre, con un program counter independiente. El sistema operativo crea un nuevo PCB para el proceso hijo. Por ejemplo, en sistemas UNIX existe un system call llamado fork que es la encargada de crear nuevos procesos. Esta llamada hace dos copias identicas del proceso salvo en el valor de retorno de la funcion (que es 0 para el hijo, y el pid del hijo para el padre). Esta llamada en combinacion con el system call exec (que borra el espacio de memoria de un proceso y carga un nuevo programa en este) permiten cargar cualquier programa en memoria. Listas de procesos Los procesos son agrupados en listas y colas dependiendo de su estado. Listas comunmente encontradas son: • job queue. Contiene TODOS los procesos del sistema. • Ready queue. Contiene los procesos que estan esperando a ser asignados el procesador. • Device queue (Cola de espera de dispositivos). Existe una de estas colas por cada uno de los dispositivos en el sistema. En ellas, se encuentran los pcb de los procesos que se encuentran esperando por una operación sobre el dispositivo. Cambios de contexto Cuando un proceso deja de ser ejecutado por la CPU (ya sea porque realizo un system call o porque la CPU fue asignada a otro proceso), el estado del procesador (y posiblemente de otros componentes relacionados) debe ser preservado hasta el momento en que el proceso resuma la ejecucion. Dentro de los valores que deben ser preservados, se encuentran los valores de los registros de la CPU, y la asignacion de memoria que tiene el proceso (La tecnica usada por el sistema operativo para mantener esta asignacion define cuales son los datos que deben ser preservados). Esta informacion es guardada en el PCB del proceso. Antes de volver a la ejecucion del proceso, el sistema operativo debe tomar los valores presentes en el PCB y enviarlos a los lugares correspondientes de manera que el proceso pueda ejecutar normalmente como si nada hubiese pasado. Threads Existen situaciones en que mas de un proceso necesitan compartir recursos para cumplir su funcion. Los sistemas operativos proveen servicios de IPC para suplir esta necesidad, pero a veces es mas conveniente usar otra herramienta para resolver el problema, los threads. Con este enfoque, ya no tenemos varios procesos sino que existe un unico proceso con varios hilos de ejecucion. De esta manera, existe un unico proceso, pero es posible aprovechar las ventajas de los sistemas que poseen mas de un procesador. Los distintos threads comparten su espacio de memoria, pero tienen stack, program counter, y registros indepentientes (los threads comparten entonces el codigo y los datos). La ventaja de desarrollar una aplicación utilizando threads es la mejora en el tiempo que esto supone, sobretodo en sistemas multiprocesadores. Ademas, los threads pueden compartir recursos sin que sea necesario comunicarse con el kernel como intermediario para obtener ese resultado. La otra ventaja que tiene el uso de threads frente a el uso de procesos independientes es que el cambio de contexto necesario cuando una cpu pasa de ejecutar un thread a otro es mas liviano que el cambio necesario al cambiar un proceso por otro, ya que hay muchos campos comunes entre ambos threads (por ejemplo, la asignacion de memoria es identica). Por ultimo, el costo de crear un thread es menor que el costo de crear un nuevo proceso. Los threads pueden ser implementados tanto en espacio de usuario como en espacio de kernel. Ambas soluciones presentan ventajas y desventajas. • • Hilos a nivel de usuario (user threads): En esta implementacion el manejo de las threads (creacion, destruccion, planificacion de la ejecucion, y administracion) es implementado por una librería de la aplicación (sin ningun apoyo del sistema operativo). El nucleo reconoce solamente un proceso ejecutando. Hilos a nivel de nucleo (kernel threads): En esta implementacion el manejo de las threads es implementado por el kernel del sistema operativo, que reconoce tantos hilos de ejecucion como threads existen. Ventajas de los hilos a nivel de usuario: • • • Pueden ser implementados independientemente de si el sistema operativo soporta la creacion de threads. El cambio de contexto es mas eficiente ya que no deben ser guardados los registros. La planificacion de las ejecucion de las threads puede seguir un algoritmo distinto al del scheduler del sistema operativo. (DEBE existir necesariamente un planificador a nivel de usuario) Ventajas de los hilos a nivel de nucleo: • • • Mejor aprovechamiento de sistemas con mas de un procasador (ya que el nucleo puede asignar threads distintas de un mismo proceso a ejecutar en procesadores distintos al mismo tiempo). La panificacion de todos los threads se efectua de manera independiente. (NO existe planificador a nivel de usuario) Si un thread se bloque esperando una operación de E/S, el sistema no bloquea a todos los threads del proceso sino que permite que otros hilos continuen la ejecucion. En general, los sistemas proveen ambos tipos de threads. Tambien surgen variantes de las anteriores, estas son: • • • Mx1: (Many to one) Varios threads de espacio de usuario se corresponden a un unico thread en el kernel. (El soporte a threads esta implementado a nivel de usuario) 1x1: (one to one) Cada thread de espacio de usuario es un thread en el kernel. (El soporte a threads esta implementado a nivel de nucleo) MxM: (Many to Many) Varias threads de espacio de usuario (pero no todos los threads existentes para el proceso) se agrupan en un thread en el kernel. En el kernel existen varios threads para un proceso, cada uno de los cuales se corresponde con varias threads en espacio de usuario. (En este caso, existen planificadores a nivel de usuario y a nivel de nucleo. Un thread se ejecuta cuando el Scheduler del sistema le da el control al proceso, y el planificador a nivel de usuario asigna ese thread para ejecutar. SCHEDULING La tarea de plainificar que procesos seran ejecutados por la CPU en un momento dado es fundamental en sistemas multiprogramados, ya que esta tarea influye mucho en la performance del sistema. Esta tarea surge de la situacion en que mas de un proceso estan esperando por el recurso procesador, y es necesario elegir uno para ejecutar. En esta situacion, se llama al planificador (scheduler) del sistema operativo. Clases de procesos Se pueden definir dos clases de procesos: Los I/O bound y los CPU bound. Los I/O bound son aquellos que realizan un uso intensivo de la entrada/salida, y por lo tanto se encuentran la mayoria del tiempo esperando a que alguna operación sobre esta se termine, mientras que los CPU bound no realizan muchas operaciones sobre la entrada salida, por lo que la mayoria del tiempo se encuentran o ejecutando o esperando en la ready queue. Como regla general, un proceso debe acceder a un recurso con prioridad inversamente proporcional al uso que haga de este. 1. 2. 3. 4. Expropiativo vs. No Expropiativo El planificador puede ser llamado en 4 momentos: El proceso que estaba ejecutando realiza una operación sobre la E/S y debe bloquearse. El proceso es interrumpido, o el proceso crea un hijo (En ambos casos se ejecuta un system call que pasa el estado del proceso de running a ready). Culmina una operación de E/S que como efecto cambia el estado de un proceso de blocked a ready. El proceso que estaba ejecutando termina su ejecucion. El planificador debe ejecutar forzosamente en los casos 1 y 4. Un planificador sera expropiativo o no dependiendo de cual es su comportamiento en los casos 2 y 3. Si en estos casos el sistema llama al planificador entonces este sera expropiativo, en caso contrario sera no expropiativo. La idea es que en los planificadores expropiativos, la ejecucion de un proceso puede ser cortada en cualquier momento, mientras que en un planificador no expropiativo la ejecucion de un proceso se efectua sin interrupciones mientras no efectue operaciones sobre la E/S (el proceso puede mantener el CPU todo el tiempo que desee). Los sistemas expropiativos implementan tambien un timer, de manera que la ejecucion de un proceso es cortada automaticamente despues de cierto intervalo de tiempo. La utilizacion de planificadores expropiativos o no expropiativos depende de las caracteristicas del sistema que se esta desarrollando: • Sistemas por lotes: Como no existe interaccion con el usuario, los planificadores no expropiadores son ideales. • Sistemas interactivos: Dado que existen varios procesos de usuario ejecutando concurrentemente, los planificadores expropiativos son ideales ya que mejoran el tiempo de respuesta al usuario. • Sistemas de tiempo real: No es necesario tener planificadores expropiativos, ya que los procesos pueden estar mucho tiempo sin ejecutarse, pero cuando lo hacen es por un periodo corto. Evaluacion de Algoritmos de Planificacion Existen varias maneras de evaluar los algoritmos de planificacion. Las medidas utilizadas para evaluarlos son: • Utilizacion de CPU. Es el porcentaje de tiempo que la CPU se encuentra ejecutando codigo de los procesos de usuario. • Rendimiento (Throughput). Es la cantidad de procesos que culminan su ejecucion por unidad de tiempo. • Tiempo de retorno. Es el tiempo desde que un proceso es cargado en memoria hasta que termina su ejecucion. • Tiempo de espera. Es la suma de los tiempos que un proceso se encuentra en estado ready. • Tiempo de respuesta. Es el tiempo entre que un proceso es cargado y da su primer respuesta. Es una medida util en sistemas interactivos. Algoritmos de Planificacion. Existen varios modelos de algoritmos de planificacion: 1. First Come First Served (FCFS). Los procesos son ejecutados en el orden en que llegan a la lista de procesos listos. Es un algoritmo no exporpiativo. Su ventaja es la facilidad de su implementacion, es apropiado para sistemas batch. Su desventaja es que el tiempo promedio de espera es alto. 2. Shortest Job First (SJF). El algoritmo asocia a cada proceso el largo de su proximo CPU-burst (seccion de codigo a ejecutar sin hacer llamadas a la E/S). Cuando el procesador queda libre, se le asigna el proceso con menor largo. El problema que tiene es que en el momento de decidir el planificador no tiene conocimiento sobre cual sera el largo del proximo CPU-bust, el que deberia estimar de alguna manera. Si se pudiera saber en todo momento el valor del largo del proximo CPU-burst, este algoritmo seria el optimo en cuanto a tiempos de espera. Este elgoritmo admite variantes expropiativas y no expropiativas: La version expropiativa se implementa de forma que si aparece un proceso en la ready queue con menor CPU-burst que lo que queda por ejecutar del proceso que esta ejecutando, entonces se realiza el cambio, mientras que la version expropietiva continuaria con la ejecucion del proceso actual hasta que este libere la CPU por alguna razon. 3. Basados en Prioridad. A cada proceso se le asigna un numero entero que representa su prioridad. Al elegir un proceso para ser ejecutado, se elige siempre al proceso con mayor prioridad dentro de la ready queue. Por lo general se implementa expriopiativamente, de manera que si un proceso con prioridad mayor a la del proceso siendo ejecutado entra en la ready queue este pasa a ejecutar sacando al proceso que estuviera antes. El SJF puede ser visto como un algoritmo basado en prioridad donde la prioridad viene dada por el valor del largo del proximo CPU-burst. Este algoritmo es adecuado para sistemas interactivos. La desventaja que posee es la pospocision indefinida, ya que procesos con baja priopridad pueden no ser ejecutados nunca si siempre aparecen procesos con mayor prioridad. Para evitar este problema se puede pasar a un sistema con prioridades dinamicas, de manera que la prioridad de un proceso va aumentando a medida que pasa el tiempo, asegurando que en algun momento tendra una prioridad lo suficientemente alta como para ser ejecutado. Por lo general, un proceso que es I/O-bound deberia tener mayor prioridad que un proceso CPU-bound. 4. Round Robin. A cada proceso se le da un periodo fijo de tiempo (llamado quantum) para que use el procesador, al fin del cual el proceso es interrumpido y el scheduler es llamado para asignar el procesador a otro proceso. El proceso que sale del procesador es agregado al final de la cola. Este algoritmo es relativamente sencillo de implementar. Para que sea efectivo, el tamanio del quantum debe ser el adecuado. Si es muy pequenio, de tamanio comparable al tiempo que lleva un cambio de contexto, la mayoria del tiempo del sistema se utiliza haciendo cambios de contexto, y por lo tanto poco tiempo haciendo tareas “utiles”. Si el quantum es muy grande, el sistema degenera en un FCFS. Por lo general tiene un tiempo de respuesta mejor que el SJF, pero tiene un tiempo de retorno mayor. 5. Multilevel Queue. Si los procesos pueden ser clasificados en distintos grupos, es posible dividir la lista de procesos en espera (ready queue) en varias listas independientes (una para cada grupo). Un proceso pertence a una unica cola, y no puede cambiar de cola durante su ejecucion. Cada cola podra tener entonces un algoritmo de planificacion propio, al que se le debe sumar un algoritmo de planificacion que determine de que cola se debe elegir el proximo proceso a ejecutar (por ejemplo, que haya colas con prioridad sobre otras). 6. Multilevel Feedback Queue. Es igual al anterior salvo que los procesos pueden cambiar de cola durante su ejecucion. La idea es categorizar a los procesos según su CPU-burst, de manera que la cola con mayor prioridad sea aquella con los procesos I/O-bound, mientras que los procesos con menor prioridad sean aquellos con alto CPU-bound. De esta forma, los procesos con menor uso de procesador son los primeros en ser atendidos cuando lo necesitan. A lo largo de la historia de los procesos estos son movidos entre las colas dependiendo de que uso hagan del procesador. Para definir un Multilevel Feedback Queue es necesario saber: 1. El numero de colas 2. El algoritmo de planificacion de cada cola 3. El metodo para subir a un proceso de una cola a una cola superior 4. El metodo para bajar un proceso a una cola inferior 5. El metodo para saber a que cola enviar a un proceso cuando cambia su estado a pronto Sistemas Multiprocesadores En sistemas multiprocesadores, cualquier procesador podra ejecutar procesos de usuario. Una posibilidad es que cada uno de estos procesadores mantenga su propia ready-queue. Esto tiene la ventaja que se aprovecha al maximo la cache del procesador, ya que cuando un proceso la poblo con sus datos, cuando vuelva algunos de esos datos puede que todavia esten presentes en la cache, aumentando la cantidad de “cache hit”, mejorando entonces la performance del sistema. La desventaja es que pueden desbalancearse las colas, dandole mucho trabajo a un mismo procesador mientras los demas no hacen nada. Para esto se implementan algoritmos que cada tanto chequean que la carga este balanceada entre los procesadores, y en caso de que no sea asi redistribuye procesos de un procesador a otro para lograr ese objetivo. Dispatcher. Una vez que es elegido el proceso a ser ejecutado a continuacion, se invoca al dispatcher, cuyas tareas son: 1. Cambiar el contexto (guardar datos en el PCB actual y restaurar los datos del PCB del proceso entrante) 2. Cambiar el bit a modo usuario 3. Saltar a al instrucción donde habia sido interrumpido el proceso (program counter) RECURSOS Es necesario incluir una estructura de datos para modelar los distintos recursos presentes en el sistema. Esta estructura incluira los siguientes datos (para un recurso generico R): • Un identificador unico para el recurso (ID) • Una lista de los recursos disponibles de tipo R. • Una lista con los procesos que se encuentran esperando por operaciones relacionadas al recurso R (Cada nodo contendra un puntero al PCB corerspondiente, mas informacion sobre el pedido, y sobre que esta esperando dentro del recurso para ser desbloqueado). • Un puntero al codigo administrador del recurso, y un puntero para realizar altas y bajas de las listas. SINCRONIZACION DE PROCESOS En un principio, los procesos en ejecucion dentro de un sistema operativo ejecutan de manera independiente entre ellos y los problemas de concurrencia son manejados exclusivamente por el sistema operativo, pero para hacer un mejor uso de los recursos del sistema se pueden definir conjuntos de procesos que ejecutan concurrentemente para lograr un mismo resultado. Si estos procesos deben compartir datos, hay que tener cuidado en que un proceso no afecte la ejecucion de otro proceso. Existen varias maneras de declarar procesos concurrentes. Grafos de precedencia Los grafos de precedencia son una herramienta utilizada para modelar la ejecucion de procesos concurrentes. Los nodos se corresponden a las sentencias que deben ser ejecutadas (eventualmente un nodo puede representar un conjunto de sentencias que deben ser ejecutadas secuencialmente), y las aristas se corresponden a las dependencias entre estas sentencias (es decir, cuales sentencias deben ser completadas antes del inicio de una sentencia en particular. Esta representacion se corresponde a un grafo aciclico (si hubiera dependencias circulares no seria posible la ejecucion de ninguna tarea), y dirigido (para una arista interesa saber cual de las dos tareas involucradas depende de la otra). Concurrencia basada en declaraciones COBEGIN – COEND Para declarar procesos concurrentes con este esquema se sigue una sintaxis como la siguiente: FACTORIAL (N: integer) BEGIN COBEGIN a=SemiFact(1, N/2) //1 b=SemiFact(N/2+1,N) //2 COEND return a*b // 3 END En este caso, las instrucciones 1 y 2 se ejecutan concurrentemente, y cuando ambas se terminan se pasa a la instrucción 3. LIMITACIONES DEL COBEGIN-COEND Se observa que hay grafos de precedencia para los que es imposible encontrar una representacion siguiendo un esquema COBEGIN – COEND. Uno de estos grafos es el que aparece al costado derecho. Concurrencia basada en FORK-JOIN. En este esquema se utilizan 3 sentencias para crear y unir hilos de ejecucion (En este contexto “hilo” no tiene porque tener que relacionarse directamente con un thread del sistema operativo). Estas sentencias son FORK, GOTO, y JOIN. La definicion de cada una de estas sentencias es: • FORK. Sintaxis: FORK etiqueta. Comportamiento: En el momento de ejecutar la sentencia FORK, el proceso se divide en dos. Uno de los procesos resultantes continua ejecutando en la linea inmediatamente posterior a la que contiene al FORK, mientras que el otro proceso resultante continua su ejecucion en la linea marcada por la etiqueta (eventualmente ambos procesos pueden continuar ejecutando en la misma linea si es que la etiqueta apunta a la instrucción despues del fork). • JOIN. Sintaxis: JOIN contador,etiqueta Comportamiento: contador es una variable entera global. Al momento de ejecutar el JOIN, el contador es decrementado. Si el valor del contador resultante es 0, el proceso salta a la instrucción indicada por etiqueta, de lo contrario el proceso termina. La intencion es que el contador este inicializado con la cantidad de procesos que deberian llegar al JOIN, de forma que todos los procesos salvo el ultimo terminen, y el ultimo pase a ejecutar la siguiente tarea, que debera estar en la posicion indicada por etiqueta. • GOTO. Sintaxis: GOTO etiqueta Comportamiento: El proceso salta a la direccion indicada por etiqueta. Mediante este esquema es posible representar cualquier grafo de precedencia. Sincronizacion entre procesos La ejecucion concurrente de procesos implica la necesidad de coordinar estos procesos para asegurar su correcto funcionamiento (por ejemplo, el acceso a recursos comunes debe ser controlado). Un problema comun es el problema de la mutua-exclusion, donde 2 o mas procesos deben ejecutar una seccion de codigo (llamada seccion critica) sin que ninguno de los otros procesos este simultaneamente ejecutando esa seccion critica. La seccion critica entre varios procesos no necesariamente es igual, por ejemplo, en una situacion determinada, una seccion critica puede ser escribir en una region de memoria para un proceso, mientras para otro proceso es leer de esa misma direccion de memoria. Para que un algoritmo sea solucion a este problema debe cumplir con tres requisitos: • • • Mutua exclusion: Si un proceso se encuentra ejecutando su seccion critica, ningun otro proceso debe estar ejecutando su seccion critica. Espera limitada: Se debe evitar la posposicion indefinida, es decir, que un proceso se mantenga esperando un tiempo indefinido para entrar a su seccion critica. Progreso: Se deben evitar dos situaciones. La primera es la situacion de deadlock, donde un proceso espera a que otro termine una operación, mientras que este espera a que el primero termine una operación. La segunda situacion que se debe evitar es la alternacion entre los procesos, osea, no se puede obligar que siempre se ejecute primero un proceso, luego el siguiente, luego el primero, y asi eternamente. Existe una solucion general para este problema para dos procesos, y otra para mas de dos procesos. La primera es el algoritmo de Becker, y la segunda el algoritmo de Peterson. El algoritmo de Becker es el siguiente (adaptado al problema de Alicia y Bernardo, donde existen dos personajes ficticios, Alicia y Bernardo, que desean pasear sus perros en un patio comun, pero deben hacerlo por separado para evitar problemas): Sincronizacion mediante hardware En algunas arquitecturas, se proveen primitivas en hardware para lograr la implementacion de secciones criticas. Estas tienen la ventajas de ser mas eficientes que soluciones basadas en software, y que simplifican la tarea del programador en lo relacionado a la mutua exclusion. En un entorno uniprocesador, una solucion al problema de mutua exclusion es inhibir las interrupciones mientras se ejecuta la seccion critica, pero en sistemas multiprocesadores esto no es suficiente, ya que mas de un procesador podrian estar ejecutando secciones criticas e distintos procesos. Una de las primitivas por hardware que es proporcionada es la primitiva test_and_set, que setea una bandera booleana en true y retorna su valor anterior en una unica operación ejecutada atomicamente (es decir, si un procesador esta ejecutando esta instrucción, todo otro procesador espera a que este termine antes de poder ejecutar esa misma instrucción). Otra primitiva por hardware proporcionada es la operación swap, que intercambia los contenidos de dos palabras de memoria atomicamente. En algunas arquitecturas, para que una operación sea ejecutada en forma atomica, se puede realizar un lock sobre el bus del sistema, de manera que ningun procesador pueda acceder al bus (y por lo tanto a la memoria) mientras se ejecuta la instrucción. Generalmente para implementar soluciones al problema de mutua exclusion mediante hardware se realiza busy-waiting, situacion no muy deseable ya que los procesos en espera continuan utilizando la CPU, que podria ser asignada a otros procesos mientras el primero espera. Primitivas de sincronizacion entre procesos Las herramientas anteriores son muy complicadas para ser utilizadas por los programadores de aplicaciones, y ademas tienen el problema de que siempre hacen busy-waiting para lograr su objetivo. Es por esta razon que los sistemas operativos incluyen en general primitivas de mas alto nivel que proveen maneras de sincronizar procesos. Estas primitivas tienen la ventaja adicional de ser independientes de la arquitectura y la implementacion de bajo nivel que estas puedan tener. Semaforos Un semaforo es una variable entera a la que se le asigna un valor (al ser creada), y que luego puede ser utilizada solamente mediante dos operaciones, la operación P y la operación V, cuyo comportamiento es el que sigue: • operación P. P(s){ while(s<=0); s--; } • operación V. V(s){ s++; } Para que el semaforo funcione correctamente, el acceso a las operaciones P y V debe ser mutuoexcluido (usando alguno de los metodos anteriores). El busy-waiting en este caso es aceptable ya que el tiempo que un proceso debe esperar es pequenio (ya que el codigo de las operaciones P y V es corto). La definicion de las operaciones dada antes es ulil para entender el funcionamiento, pero poco representativa de la implementacion real del semaforo. El problema con esta implementacion es el busy-waiting presente en la operación P. Lo que hacen los sistemas operativos es quitar este busywaiting, y agregar codigo en las operaciones para dormir y despertar procesos, de manera que la semantica de las operaciones permanezca igual pero evitando el problema del busy-waiting. Una implementacion mas apropiada seria: • P(s){ if(s>0) then s--; else bloquear_proceso; } • V(s){ if(hay procesos esperando por el semaforo) despierto_un_proceso else s++; } Deadlocks e inanicion En la implementacion y uso de los semaforos hay que tener cuidado de no generar los problemas de Deadlocks y starvation. Los deadlocks pueden venir dados por el uso incorrecto de los semaforos en el que dos procesos piden semaforos en distinto orden y quedan esperando a que el otro realice un V sobre el semaforo que posee. La inanicion puede ocurrir dependiendo de la politica con la que se elige en la operación V cual proceso despertar, ya que si es incorrecta algunos procesos podrian permanecer esperando eternamente por el semaforo. Monitores Otra primitiva de sincronizacion disponible son los monitores. En este caso, se define un data type con su conjunto de datos privados, y ciertas operaciones publicas. La particularidad de este tipo de datos es que se asegura por definicion que nunca habra mas de dos procesos ejecutando el codigo de las operaciones publicas del monitor, de manera que la mutua exclusion en este tramo esta asergurada. Los monitores asi definidos no sirven para resolver todos los problemas de sincronizacion que pueden aparecer, sino que en algunos casos es necesaria una herramienta mas. Esta herramienta son las condiciones. A las condiciones solo se les pueden aplicar las operaciones wait y signal. Cuando un proceso realiza un wait sobre una condicion, este se bloquea hasta que otro proceso realice un signal sobre esa misma condicion. Si un proceso realiza un signal sobre una condicion y no hay ningun proceso esperando a que ello ocurra, entonces es como si nunca se hubiera ejecutado esa instrucción. Se puede mostrar que es posible implementar semaforos usando monitores, y monitores usando semaforos, por lo que estas dos herramientas pueden resolver los mismos problemas. Un problema que surge de la incorporacion de las condiciones y el uso de wait y signal, es que cuando se despierta un proceso que estaba esperando por una condicion, surge el problema de cual de los dos procesos (el despertado o el despertador) debe continuar su ejecucion primero. Lo que es inadmisible es que ambos procesos continuen, ya que de hacerse esto se violaria la condicion que establece que solo un proceso puede ejecutar el codigo del monitor en cualquier momento dado. Por lo tanto, o sigue su ejecucion el despertador o el despertado. La razon a favor de que siga la ejecucion el despertador (llamada signal-and-continue), es que es logico que este proceso no sea interrumpido en su ejecucion, ya que nunca se bloqueo esperando una condicion y ya se encontraba ejecutando codigo del monitor. La razon para que el despertado sea quien continua su ejecucion primero (signal-and-wait), es que en caso contrario, la razon por la que el proceso fue despertado puede haber caducado al momento en que realmente llega a ejecutar. Lo ideal es implementar la solucion de manera que funcione sin importar si los semaforos actuan según una conducta o la otra (idea: si es posible ubicar los signal al final de un procedimiento del monitor, entonces esta condicion se cumple). En caso de no ser posible, alcarar en la solucion cual de las dos conductas es la apropiada para que funcione. Sincronizacion en ADA El enfoque para lograr concurrencia en ADA es a traves de encuentros entre tareas, es decir, momentos en que dos hilos de ejecucion se encuentran. Las tareas solicitan encuntros, y existen otras tareas que aceptan estos encuentros. Estos pedidos de encuentro son vistos como llamadas a subrutinas desde la tarea que los llama. El intercambio de datos entre procesos se da entonces en estos puntos especificos en que los procesos se encuentran. Cuando un proceso pide un encuentro, este se bloquea hasta que sea atendido ese encuentro. Un proceso puede quedarse esperando tambien hasta recibir a alguien que quiera tener un encuentro con el. Las citas son atendidas siguiendo un algoritmo FCFS. El codigo de procesamiento de un encuentro es la seccion de codigo que ejecutan “en comun” los procesos. Por lo tanto, este codigo debe ser lo mas corto posible, ya que durante la ejecucion de este el proceso que solicito la cita se queda esperando a que termine. El uso de los encuentros sirve tanto para la sincronizacion como para el intercambio de informacion entre los procesos. IMPORTANTE: ES INCORRECTO USAR VARIABLES GLOBALES EN ADA! Sintaxis La sintaxis en general es de la forma: PROCEDURE Proc() TASK nombre ENTRY entrada1 ENTRY entrada2 … END nombre TASK BODY nombre BEGIN …. …. ACCEPT entrada1 …. END ACCEPT …. ACCEPT entrada2 …. END ACCEPT …. END nombre A, B : nombre BEGIN // Principal A.entrada1 B.entrada2 END //Principal Con esta sintaxis, se define una tarea “nombre”, que tiene las entradas “entrada1” y “entrada2”. Se definen dos tareas, A y B, de tipo nombre. Luego, en el programa principal aparecen las llamadas a los encuentros definidos para A y B. Existe una construccion mas del lenguaje que permite declaraciones mas complejas. Esta es la construccion SELECT, que puede ser incluida en el codigo de la tarea para esperar por mas de una entrada a la vez. Esta sentencia tiene la forma: SELECT [WHEN cond =>] ACCEPT entrada1 END ACCEPT OR [WHEN cond2 =>] ACCEPT entrada2 END ACCEPT … [OR [WHEN cond3] DELAY s] \n END SELECT | ELSE instrucciones END SELECT La ultima linea quiere decir que o bien hay un OR DELAY o un ELSE. En caso de que hay un OR DELAY el END SELECT aparece en la linea inmediatamente posterior a esa instrucción, en caso de que haya un ELSE, se incluye el codigo a ejecutar en este caso y despues viene el END SELECT. La sintaxis asociada a esta construccion es: En el caso en que hay un ELSE en la declaracion del SELECT evaluo_guardas(); if(hay_guarda_verdadera()){ if(hay_proc_esperando_en_accept_con_guarda_verdadera()){ proceso_encuentro(); sigo_con_siguiente_instruccion(); }else{ if(hay_else()){ ejecuto_codigo_else(); sigo_con_siguiente_instruccion(); }else{ espero_que_llegue_proceso(); proceso_encuentro(); sigo_con_siguiente_instruccion(); } } }else{ if(hay_else()){ ejecuto_codigo_else(); sigo_con_siguiente_instruccion(); }else{ Error! } } En caso que haya un OR DELAY evaluo_guardas(); if(hay_guarda_verdadera()){ if(hay_proc_esperando_en_accept_con_guarda_verdadera()){ proceso_encuentro(); sigo_con_siguiente_instruccion(); }else{ esperar_la_cantidad_que_diga_el_ordelay_por_si_llegan(); } }else{ ERROR! } Sincronizacion mediante el envio de mensajes. En este paradigma se utilizan dos operaciones basicas, send(destino,mensaje) y receive(origen,mensaje). Estas operaciones tienen variantes en su semantica, las mas comunes son: • Envio bloqueante, recepcion bloqueante: Tanto el emisor como el receptor se bloquean hasta que se transmite el mensaje. Permite una fuerte sincronizacion entre procesos. • Envio no bloqueante, recepcion bloqueante: El emisor puede continuar luego de haber mandado un mensaje (el que queda “esperando” ser leido). Sin embargo, si un receptor quiere leer un mensaje y no hay ningun mensaje disponible, entonces se bloquea hasta que haya uno. • Envio no bloqueante, recepcion no bloqueante. Nadie se bloquea. Tiene la desventaja que pueden perderse mensajes si estos llegan despues de que el receptor ejecuto el receive (en cuyo momento no habia ningun mensaje disponible). Direccionamiento. Los procesos deben de tener una manera de identificar hacia donde y desde donde van los mensajes. Para este problema existen dos soluciones: • Direccionamiento directo. Con este direccionamiento los procesos especifican directamente a que proceso se envia un mensaje (en la operación send), y de que proceso quieren leer mensajes (en la operación receive). Esto implica que cada proceso debe saber de antemano que procesos le enviaran mensajes y cuando. En algunos casos esto no es posible porque no se sabe de antemano que procesos se comunicaran con el proceso que espera en un receive. En este caso puede usarse un direccionamiento implicito, en el que el proceso que envio el mensaje es retornado en el parametro origen de la operación receive. • Direccionamiento indirecto. En este caso los mensajes no se envian directamente de emisor a receptor, sino que se definen unas estructuras de datos intermedias llamadas mailboxes, que pueden mantener una cola de mensajes en memoria temporalmente hasta ser leidos. Para realizar la comunicación, los procesos realizan las operaciones send y release dirigidas a mailboxes especificos. Una ventaja de este tipo de direccionamiento es que desacopla al emisor del receptor, de manera que estos deben conocer menos del otro. Ademas, la relacion entre los procesos emisores y receptores en un mailbox puede ser uno a uno, uno a muchos, muchos a uno, o muchos a muchos. Una relacion de muchos a uno puede ser util en sistemas cliente/servidor, donde el mailbox puede ser llamado puerto. Una cuestion a definir por el sistema operativo en este caso es quien sera el propietario del mailbox. En caso de que el mailbox sea poseido por un proceso especifico, este debe ser borrado en el momento en que el proceso es borrado. En caso de que el mailbox sea compartido, el sistema debera proveer system calls para crear y eliminar mailboxes. En caso en que el direccionamiento sea dinamico, el sistema debe mantener una cola de los mensajes en espera. Esta cola puede ser finita o infinita, y la extraccion de esta cola puede ser usando un esquema FIFO o siguendo un algoritmo basado en prioridad. IMPORTANTE: Al resolver un problema debe especificarse el comportamiento de las operaciones send y receive, y si corresponde tambien especificar el tamanio y propiedades de la cola. ADMINISTRACION DE MEMORIA Es una de las tareas mas importantes del sistema operativo. Las maneras de implementar esta tarea dependen del soporte en hardware que tenga el sistema para ayudarse en su objetivo. Esta tarea comprende las subtareas de: • Mantener un registro de que memoria esta siendo usada y que proceso(s) la esta(n) usando. • Decidir que procesos seran cargados a memoria cuando haya espacio disponible. • Asignar y quitar memoria de los procesos según sea necesario. Antes de empezar: Los programas son escritos en lenguajes de alto nivel, y luego son compilados, linkeditados, y cargados en memoria para su ejecucion. La compilacion pasa del lenguaje de alto nivel a codigo objeto, que todavia no esta pronto para ser ejecutado (tiene “agujeros” en las llamadas a rutinas que no estan presentes en el archivo que se compilo), en la linkeditacion se unen varios codigos objeto para formar un unico ejecutable. En la carga del programa, se coloca a este en la memoria, se prepara su ejecucion y se inicia. La linkeditacion se introduce como una manera de reutilizar codigo, varios programas pueden ser linkeditados frente a una librería en comun. Las computadoras tienen (por lo general) mas espacio en disco que en memoria. Entonces, a Fotheringham (sisi, ese es el nombre) se le ocurrio hacer que los procesos pudieran tener mas memoria asignada que la disponible en la RAM, guardando la parte que no entra en esta en el disco duro, y volviendola a cargar en RAM cuando fuera necesario usarla. De esta manera, el programador se olvida de cuanta memoria tiene el sistema, y asume que la memoria es un arreglo de bytes muy grande que puede acceder cuando quiera. El sistema operativo se va a ocupar de cargar las partes de la memoria que esten en disco cuando estas sean necesitadas. Se genera asi una diferencia entre lo que el programador piensa que es la memoria y como esta se encuentra fisicamente en el sistema. Se define entonces el concepto de “memoria virtual”. Por ejemplo, en un sistema de 32 bits, un proceso puede actuar como si tuviera 4GB de memoria para el solo (cada direccion se refiere a un espacio de 1 byte, como hay 2^32 direcciones posibles, se puede acceder a 2^32 bytes distintos, osea, a 4GB). Se agrega un componente de hardware, que se llama MMU, para traducir entre lo que ve el proceso (direcciones logicas) y la realidad fisica en el sistema (direcciones fisicas). A los programas hay que asignarles las direcciones de memoria que les corresponden en algun momento. Esto implica la traduccion de direcciones logicas a direcciones fisicas (address binding), y se puede hacer en 3 momentos: • Tiempo de compilacion: Sirve cuando se sabe de antemano donde en la memoria se va a ubicar el programa. Las direcciones de memoria son ubicadas estaticamente en el ejecutable en el momento de compilacion • Tiempo de carga: Los ejecutables contienen direcciones relativas, y en el momento de carga estas direcciones relativas son transforamdas en direcciones absolutas. (El programa no puede ser movido de lugar en la memoria una vez cargado) • Tiempo de ejecucion: Un programa pude ser movido de lugar en tiempo de ejecucion, y sus direcciones logicas son traducidas a direcciones fisicas en el momento de ser utilizadas. Clasificacion de las direcciones de memoria. Se distinguen 3 tipos de direcciones de memoria, dependiendo de donde son usadas. Las direcciones logicas son todas aquellas que salen del procesador. Las direcciones fisicas son aquellas que salen de la MMU (y entran en la memoria principal). Las direcciones virtuales son las que salen del procesador cuando se efectua la traduccion en tiempo de ejecucion. Para las traducciones en tiempo de compilacion y en tiempo de carga, las direcciones logica y fisica coinciden. Carga Dinamica El tamanio de un proceso esta limitado por la cantidad de memoria disponible en el sistema. Para aprovechar mejor esta memoria se utiliza la carga dinamica, en la que una rutina es cargada en el momento en que va a ser invocada. De esta manera, las rutinas no utilizadas no ocupan espacio innecesariamente. Ensamblaje dinamico En el proceso de linkeditacion, las librerias utilizadas por el usuario pueden ser incorporadas al ejecutable. Otra opcion es no incluirlas, y en el lugar donde se invocan funciones de esa librería dejar un codigo que carga la librería y luego ejecuta el codigo de la funcion. De esta manera, la memoria que ocuparia la librería queda libre hasta que el proceso decide invocar alguna funcion de esta. Esto tiene otras ventajas. Una es que actualizaciones en la librería afectan automaticamente a todos los procesos que la utilizan, otra es que el codigo de una librería compartida por varios procesos puede ser cargada una sola vez en memoria fisica y hacer que todos los procesos que la utilizan direccionen en su espacio virtual a la misma region en la memoria fisica. Overlays Otra opcion para hacer un uso mas eficiente de la memoria es el uso de overlays, en el que el compilador divide el codigo en partes, y en la memoria se encuentra unicamente la parte que esta siendo utilizada. Se incluye ademas una seccion de codigo que es mantenida siempre en memoria y se encarga de cargar y sacar las distintas partes del codigo de la memoria. Swapping En sistemas multiprogramados mas de un proceso debe estar cargado en memoria principal. Para obtener mejores resutlados, aquellos procesos que no estan ejecutando pueden ser sacados de la memoria principal y guardados en un dispositivo mas lento (disco duro) hasta que pasen a ejecutar, de manera de tener mas memoria disponible para los procesos que si se encuentran ejecutando. La accion de pasar un proceso de memoria a disco se denomina swap-out, y su opuesto se denomina swap-in. Como se mueven procesos enteros de memoria a disco, se utiliza mucho tiempo en la transferencia. Dependiendo de como fue la asignacion de direcciones logicas a fisicas, un proceso al ser restaurado podra quedar en cualquier lugar (si la asignacion fue en tiempo de ejecucion), o siempre en un mismo lugar fijo (si la asignacion fue en tiempo de compilacion o carga). Asignacion de memoria En los sistemas generalmente se divide a la memoria en dos grupos, la memoria del kernel y la memoria de los procesos de usuario. Es necesario asegurar que un proceso no puede acceder a la memoria del kernel o de algun otro proceso. Para esto se incluyen dos registros, el relocation register y el limit register. El relocation register indica “donde empieza” el espacio de memoria del proceso, y el limit register cuanta memoria tiene asignada a partir de ese comienzo. Por lo tanto, todo acceso a memoria fuera del rango [relocation register, relocation register+limit register] sera no valida y ocasionara un trap al sistema operativo (que abortara el proceso). Multiprogramacion con particiones fijas En estos sistemas la memoria se divide en pedazos, cada uno de los cuales puede ser utilizado por un proceso, generando una cota a la cantidad de procesos concurrentes que pueden existir. Cuando termina un proceso se carga un nuevo proceso en el espacio que este libero. Multiprogramacion con particiones variables En estos sistemas se van cargando los procesos de forma contigua en la memoria, pero el espacio que ocupan puede variar de acuerdo al proceso. Cuando estos terminan, van dejando “agujeros” en la memoria. El sistema tiene que llevar un registro de la memoria usada y no usada. Cuando llega un proceso nuevo y se debe buscar un agujero de memoria libre para asignarle existen 3 estrategias para elegir cual darle: 1. First fit: le doy el primer agujero lo suficientemente grande para que entre. 2. Best fit: le doy el agujero mas chico entre los agujeros que pueden contenerlo. 3. Worst fit: le doy el agujero mas grande que pueda contenerlo. En la practica se comprueba que best y first fit funcionan mejor en velocidad y porcentaje de utilizacion de la memoria que worst fit. Cualquiera de las estrategias de asignacion presenta el problema de la fragmentacion externa (quedan agujeros muy chiquitos entre regiones de memoria usadas que no sirven para nada, pero que sumados pueden ser una cantidad importante de memoria). Entonces tenemos el problema de que “hay” memoria libre como para asignar procesos nuevos, pero esta memoria esta inutilizable. Paginacion Una manera completamente distinta de ver el problema es la paginacion. Esta no tiene el problema de la fragmentacion externa, pero requiere hardware especial para ser soportada. La idea es dividir el espacio de memoria de un proceso en paginas (pages), y la memoria fisica del sistema en marcos (frames). El tamanio de las paginas y las frames es igual dentro de un sistema, y debe ser una potencia de 2. En lugar de realizar swapping con procesos enteros, se realiza swapping pagina por pagina (se mueven las paginas entre la memoria principal y el disco, en una region especial de este llamada swap, que tiene frames del mismo tamanio que aquellos de la memoria principal). El direccionamiento cuando se utiliza paginacion se realiza de la siguiente manera: Las direcciones virtuales se dividen en dos partes, el numero de pagina y el offset dentro de esa pagina. El numero de pagina es ingresado a una tabla que tiene las direcciones fisicas de las bases de las paginas, y el offset es la distancia desde la direccion base de la pagina en la que se encuentra el byte que se quiere direccionar. Si una direccion se divide en n bytes para la pagina y m bytes para el offset, el tamanio de la pagina debe ser 2^m para aprovechar todas las direcciones posibles (por esta razon es que el tamanio de pagina debe ser potencia de 2). Entonces, para acceder a una posicion de memoria el sistema debe buscar en la tabla cual es la direccion fisica donde empieza la pagina y sumarle el offset. La tabla de paginas es propia del proceso. Lo mas comun es que esta tabla este guardada en memoria del kernel (podria estar almacenada en registros, pero esto tiene dos desventajas: aumenta el tiempo de cambio de contexto porque se deben cargar y descargar los registros correspondientes a la tabla, y la cantidad de entradas de la tabla es muy limitada), y que un puntero a esta tabla sea guardado en el PCB del proceso correspondiente. Durante un camibo de contexto se actualiza un registro (PTBR) que contiene el puntero a la tabla (mediante una operación privilegiada). La desventaja de tener la tabla en memoria es que se precisan 2 accesos a memoria para obtener el resultado (una para obtener la direccion del frame deseado, y otra para acceder al byte buscado). Para acelerar el proceso se agrega la TLB (Translation Look-aside buffer). Esta es una cache asociativa, en la que cada entrada tiene el numero de pagina, y la direccion fisica del frame. Si la clave se encuentra en el TLB (TLB hit) se evita la busqueda en la memoria y se accede directamente al frame correspondiente, en caso contrario se busca el valor correspondiente en memoria, se accede al frame deseado y se guarda el valor en el TLB para acelerar los proximos accesos. La TLB puede guardar tambien un ASID (Address space identifier), que permite identificar a que proceso corresponde la entrada. Si no se cuenta con este campo, se debe limpiar la TLB cada vez que hay un cambio de contexto para evitar que un proceso entre a memoria de otro proceso por error. Se puede calcular el tiempo efectivo de acceso a memoria (EAT), de la siguiente manera: EAT=(hit_ratio)*(tiempo_acceso_memoria+tiempo_busqueda_tlb)+ (1-hit_ratio)*(2*tiempo_acceso_memoria+tiempo_busqueda_tlb) Con esta formula, se puede calcular la efectividad de la TLB en funcion del hit ratio obtenido en el sistema. Proteccion de memoria Para proteger la memoria se puede incluir un valor dentro de la tabla de pagina que indique si esa pagina es valida o no. Si se intenta realizar un acceso a una pagina no valida, se genera un trap. Tambien puede utilizarse un mecanismo similar para definir paginas de solo lectura (por ejemplo para contener codigo) y paginas de lectura-escritura. Estructura de la tabla de paginas En un sistema de 32 bits con paginas de 4KB, la tabla de paginas tiene un millon de entradas, lo que implica que cada tabla de paginas ocuparia 4 MB (suponiendo que cada entrada ocupa 4 bytes). De ese millon de entradas no se utilizan todas en todo momento, mas bien lo contrario. Es necesario entonces utilizar alguna manera mas eficiente de guardar la tabla, para no desperdiciar tanta memoria. Las soluciones propuestas son: • Jerarquica: La idea es paginar la tabla de paginas (!). Mas concretamente, se divide la tabla en tablas mas pequenias, que contienen la informacion de un rango de paginas. Se agrega tambien una tabla que indica donde se encuentra la tabla para cada rango. Entonces, se crean solamente las tablas correspondientes a los rangos que estan siendo utilizados, evitando ocupar toda la memoria necesaria si se guardara toda la tabla. Se puede generalizar esta idea usando cualquier cantidad de niveles. Agregando niveles se puede ahorrar mas memoria, pero aumenta el tiempo necesario para resolver la direccion fisica de una direccion logica, ya que se deben hacer tantos accesos a memoria como niveles existan. • Hash: Se implementa un hash abierto (con listas para resolver las colisiones) en el que se guardan las entradas correspondientes a las paginas validas. • Tabla invertida: En lugar de tener una tabla por proceso indizada por el numero de pagina, se tiene una unica tabla global indizada por numero de frame. Cuando un proceso intenta acceder a una pagina, busca entrada correspondiente a ese proceso y esa pagina en la tabla. (Aumenta mucho el tiempo de busqueda, pero al tener una unica tabla disminuye mucho el espacio en memoria utilizado). Compartimiento Al utilizar frames, se simplifica el compartir memoria entre procesos. Para hacerlo, se hace que las tablas de paginas de distintos procesos apunten a una misma direccion fisica. De esta manera se puede compartir tanto codigo como datos, aumentando la eficiencia del uso de la memoria. Fragmentacion interna La paginacion tiene la desventaja de generar fragmentacion interna. Esto sucede cuando un proceso requiere un tamanio de memoria que no es multiplo del tamanio de pagina del sistema, ya que las paginas se asignan enteras (no se puede dar “media” pagina a un proceso). Por ejemplo, si el tamanio de pagina es 4 MB y un proceso requiere 5 MB, se deberan asignar 2 paginas, desaprovechando 3 MB de memoria. Asignacion de memoria En este sistema la asignacion de memoria es sencilla y rapida. Se mantiene un arreglo de bits con la informacion de si un frame esta siendo utilizado o no. Para asignar memoria a un proceso se buscan frames libres en el arreglo y son asignados individualmente. Segmentacion En este sistema se asignan segmentos de memoria contigua a los procesos, lo que se corresponde mas con la vision de memoria que tiene el usuario. Cada segmento tiene un numero y un largo asociado. Las direcciones se componen del numero de segmento y el offset dentro de este segmento, que debe ser menor al largo de este. El soporte en harware se implementa medinante una tabla que contiene, para cada segmento, la direccion base del segmento, y el largo del mismo. De manera similar a la paginacion, la tabla se guarda en memoria principal y se guarda un puntero a esta en un registro. La proteccion de memoria se implementa asignando permisos sobre los segmentos, que son guardados en la tabla de segmentos y el hardware controla al momento de acceder al segmento. La segmantacion, de manera similar a la multiprogramacion con particiones variables, sufre de fragmentacion externa. En la segmentacion compartir memoria es mas simple, ya que se comparte todo un segmento como una unidad, mientras que al compartir paginas se debe compartir cada pagina por separado. En este caso la asignacion de memoria es mas complicada ya que es necesario buscar un espacio de memoria lo suficientemente grande para almacenar el segmento pedido. Es posible combinar Paginacion con Segmentacion para potenciar las ventajas de cada uno de los sistemas. Una arquitectura que implementa esta solucion es la arquitectura Intel. Memoria Virtual (Asumo en esta parte que el sistema usa paginacion, asi esta en el libro, no se si hay maneras de tener memoria vitual en sistemas sin paginacion) La memoria virtual es el mecanismo descripto antes por el que un proceso tiene la “ilusion” de que la memoria es un arreglo uniforme de bytes que puede acceder en cualquier momento, y cuyo tamanio puede ser mayor a la capacidad fisica de la memoria del sistema. Para implementar esto se usa un sistema de paginacion bajo demanda. La idea es que cuando un proceso es iniciado no toda la memoria de este se encuentra en memoria, sino que las paginas se van cargando a medida que el proceso hace referencia a palabras contenidas en ellas. (Esta implementacion es denominada “lazy swapper”). A su vez, el sistema posee en almacenamiento secundario una region reservada para ser usada como memoria swap, que permite guardar mas datos que los disponibles en la memoria RAM. En paginacion se implementaba un sistema en que la tabla de paginas poseia un campo indicando si esa pagina era valida o no, en cuyo caso se producia un trap al sistema operativo que abortaba el programa por hacer un acceso no autorizado a memoria. Este mecanismo es ahora completado, y el sistema no aborta directamente el proceso, sino que cuando recibe un trap de que una pagina era invalida, se fija cual es la razon de esta situacion. Que no sea valida implica que no esta en memoria, pero esto puede ser porque el proceso no tiene acceso a esa pagina (ahi tira un segmentation fault y aborta el proceso) o porque la pagina se encuentra actualmente en swap, y debe ser cargada en RAM para continuar la ejecucion del proceso (en este caso carga la pagina a algun frame y sigue como si nada). Para implementar el lazy swapper, la memoria virtual de un proceso es inicializada con todas sus paginas como invalidas. Entonces, cada acceso a memoria producira un trap que implicara que la pagina involucrada sea cargada a algun frame en la memoria RAM. Para cargar una nueva pagina en memoria el sistema debe seguir los siguientes pasos: 1. Encontrar un frame libre (o elegir uno para ser reemplazado) 2. Mandarle al disco el pedido de lectura de la pagina contenida en el 3. Copiar el resultado de la operación 2 en el resultado de la operación 1 4. Marcar la pagina como valida en la tabla del proceso 5. Reumir el proceso en la instrucción donde habia dejado Mientras se espera el resultado del disco duro la CPU puede ser asignada a ejecutar otros procesos. En este caso se aumenta la cantidad de pasos ya que hay que considerar los cambios de contexto involucrados. Estudio de la performance de la memoria virtual El mecanismo de paginacion por demanda puede tener un gran impacto sobre la eficiencia del sistema. Para calcular el tiempo medio que demora en ser atendida una operación sobre la memoria se utiliza la formula: EAT=(1-p)*ma + p*TPRF Donde p es la probabilidad de que ocurra un page fault, ma es el tiempo medio de acceso a la memoria RAM, y TPRF es el tiempo medio que demora en atenderse un page fault. Algoritmos de reemplazo Si no hay frames libres donde guardar la pagina que estamos recuperando del almacenamiento secundario, entonces debemos elegir un frame para sacarle lo que tiene actualmente y reemplazarlo con el contenido de la pagina a cargar (El contenido actual de ese frame es preservado en memoria swap, y la tabla de pagina del proceso que poseia ese frame es actualizada para reflejar el cambio). Si el frame que acabamos de pasar a swap llega a ser referenciado, necesitaremos cargarlo de nuevo a memoria. Los algoritmos para seleccionar el proximo frame a reemplazar son: • FIFO. Los frames son puestos en una cola cuando son asignados, y en caso de no haber mas frames libres el sistema el sistema elige como victima al primer frame en la cola. Es facil de implementar, pero no es bueno ya que capaz que el frame elegido es muy “viejo” pero es usado continuamente por su duenio, por lo que dentro de poco va a tener que ser cargado de nuevo en memoria. Ademas, este algoritmo sufre de una falla denominada anomalia de Belady, que es que la cantida de page fault aumenta al existir mas frames en el sistema. • Second Chance. En la tabla de pagina se incluye un bit que es seteado en 1 cada vez que se realiza un acceso sobre esa pagina. Cuando se va a reemplazar un frame, el sistema hace lo mismo que en el caso FIFO, pero verifica el valor del bit. Si este es 0 realiza el cambio, si es 1 lo setea en 0 y lo envia al fin de la lista • Optimal. Es un algoritmo que se prueba que es el optimo para resolver el problema. Pero para variar, es imposible de implementar. La idea seria reemplazar el frame que no se va a utilizar por mas tiempo. Como no se sabe de antemano cuando se va a acceder a algun frame, esto es imposible. • Not Recently Used. A los bits se les asigna dos bits, uno de referencia y otro de modificacion. El de referencia se activa cuando alguien lee algo del frame, y el de modificacion se activa cuando alguien escribe algo en el frame. Estos bits son seteados en 0 periodicamente por una interrupcion. Cuando hay que reemplazar un frame hay 4 cases de frames en el sistema: ◦ No referenciado, no modificado ◦ No referenciado, modificado ◦ referenciado, no modificado ◦ referenciado, modificado Se reemplaza un frame al azar de la clase mas baja que no este vacia. Es sencillo de • implementar, pero requiere que el hardware actualice los bits de referencia y modificacion Least Recently Used. Este algoritmo se acerca mucho al optimo. La idea es que cada frame tiene en la tabla de pagina un registro del tiempo en que fue accedido por ultima vez, que es actualizado por el hardware. Se reemplaza el frame que hace mas tiempo que no se accede. Este algoritmo no es muy usado porque requiere hardware muy especializado. Estrategias de asignacion de frames En un sistema existen muchos procesos usando memoria, los cuales ademas pediran y liberaran memoria. Si el sistema no implementa un algoritmo de asignacion de memoria equitativo para todos los procesos el sistema puede colapsar si un proceso pide demasiada memoria. Una primera solucion es asignar a todos los procesos la misma cantidad de memoria, pero esto es ineficiente porque las necesidades de memoria de un proceso son muy distintas a las necesidades de otro proceso. La idea entonces es ponderar la memoria que se va a otorgar a un proceso según la cantidad de memoria virtual que este esta usando. Cuando se busca un frame para reemplazar, el sistema puede o bien buscar en todos los frames del sistema (global replacement) o solamente aquellos frames que ya estan asignados al proceso (local replacement). Si se busca globalmente, la cantidad de frames asignados a un proceso varia respecto al tiempo. Ademas, como un proceso le puede sacar frames a otro, el segundo proceso puede empezar a ejecutar mas lentamente como consecuencia. El reemplazo local, por su parte, independiza los fallos de pagina entre los procesos, pero mantiene frames poco usados en memoria, razon por la cual el reemplazo global es mas utilizado. Hiperpaginacion La cantidad de frames que posee un proceso es administrada por el sistema, si un proceso tiene mas paginas activas que las que las frames asignadas por el sistema, el proceso tendra un alto porcentaje de page faults. Si un proceso pasa mas tiempo paginando que ejecutando se dice que esta sufriendo de Hiperpaginacion (Thrashing). La hiperpaginacion afecta muchisimo la performance. La multiprogramacion aumenta el uso de la CPU, pero si se aumenta mucho la multiprogramacion, los procesos pasan a sufrir Hiperpaginacion, por lo que pasan mas tiempo esperando a que el disco lea sus datos de swap que ejecutando, lo que termina en que la CPU es utilizada poco. Para atacar el problema de la hiperpaginacion, se propone el modelo del Working Set. La idea es que cada proceso en un periodo de tiempo trabaja con un working set, es decir, un conjunto de paginas (llamadas activas). Si este conjunto puede ser colocado en memoria entonces no se sufrira hiperpaginacion. A medida que pasa el tiempo el conjunto de paginas activas cambia, pero lo importante es que siempre existe ese conjunto en periodos de tiempo relativamente cortos. Para tener un aproximacion del working set se guardan las paginas accedidas en un lapso definido de tiempo. Si este lapso es pequenio, no se logra captar la idea de cual es el conjunto siendo utilizado, pero si es muy grande el conjunto pasa a ser el conjunto de todas las paginas accedidas por el proceso en su historia. Una vez que se sabe el tamanio del working set de cada proceso, si se suman todos podemos obtener la cantidad de frames necesarias en el sistema para evitar el thrashing. Si esta cantidad es menor a la cantidad de frames disponibles en memoria principal, entonces el sistema debe suspender procesos y despertarlos una vez que se liberen frames como para darles a todos lo necesario. ESTRUCTURA DE LOS DISPOSITIVOS MASIVOS DE DATOS El sistema operativo es el responsable de utilizar el hardware de manera eficiente. Aplicado al disco, se debe intentar aprovechar al maximo el ancho de banda del disco. Por esta razon, el planificador de disco se torna importante. El tiempo que lleva acceder a un dato en el disco tiene dos componentes importantes. El tiempo de posicionamiento (seek), que es el que demora el cabezal del disco en llegar a la posicion en la que debe leer, y el tiempo correspondiente a la latencia de rotacion (rotational latency), que es el tiempo que el cabezal debe esperar en esa posicion hasta que el disco gire hasta donde esta el dato deseado. La idea del planificador es minimizar la suma de estos tiempos, para hacerlo se intenta minimizar el tiempo de posicionamiento. Los algoritmos dados en el curso son: • FCFS. No optimiza nada, solamente manda los pedidos al disco en el orden en que van llegando. Es muy ineficiente, ya que para algunas combinaciones de pedidos la cabeza debe recorrer muchos cilindros del disco para completar el pedido (si mandas leer alternadamente dos cilindros que se encuentran muy separados el tipo se pasa la mayoria del tiempo moviendo el cabezal). • SSTF. Shortest Seek Time First. La idea es optimizar el acceso haciendo que los movimientos del cabezal sean minimos. Dado un conjunto de pedidos, se atiende aquel que implique un seek time menor. Es mejor que el anterior, pero no perfecto. (Capaz que es porque evalua optimos locales, pero no se) • SCAN – C-SCAN. En el algoritmo SCAN, el brazo se posiciona en el principio del disco, y se va moviendo hacia el fin. En ese camino va leyendo los pedidos a medida que llega al cilindro correspondiente. Al final realiza el camino inverso, de nuevo leyendo los datos que correspondientes a los cilindros por los que va pasando. El algoritmo SCAN es igual, salvo que cuando llega al final del disco vuelve al principio sin leer ningun dato en el camino. • LOOK. Es parecido a C-SCAN, solo que en lugar de arrancar siempre para el mismo sentido arranca para el sentido donde haya pedidos. SSTF y LOOK son los algoritmos mas utilizados. SCAN y C-SCAN esta comprobado que funcionan muy bien en ambientes donde se usa mucho el disco. Estructuras RAID RAID es una tecnica utilizada para mejorar la confiabilidad y la velocidad de acceso a datos de un sistema. El concepto central es la redundancia de informacion en distintos discos. Esta redundancia puede lograrse implementando una solucion en que se tienen dos discos identicos, o utilizando discos para guardar bits de control para detectar y corregir errores en los otros discos. El tiempo de respuesta es mejorado por la distribucion de los datos en los discos, y la posibilidad de realizar lecturas y/o escrituras en paralelo en los discos. Las configuraciones RAID se orientan en este sentido. Se definen varios niveles de RAID, que son: • RAID-0. La informacion puede ser stripped (dividida en) varios discos, pero no se provee ninguna redundancia, por lo que la falla de un disco provoca la perdida de la informacion contenida en el. • RAID-1. La informacion puede estar en varios discos, pero ademas cada uno de estos discos esta espejado en otro disco, de manera que si se pierde la informacion de un disco esta puede ser accedida a traves de su “gemelo”. • RAID-2. En este caso, la redundancia se efectua agragando discos que guardan bits de codigos correctores de errores como los que pueden ser usados en la memoria RAM (algo del estilo de los codigos de Hamming). Si un disco falla su informacion puede ser restaurada usando el codigo corrector de errores. • RAID-3. En este caso se agrega un unico disco extra para contener la paridad de los bits contenidos en los otros discos. Un disco puede informar cuando un bloque esta defectuoso, por lo que si se sabe que la paridad fue incorrecta para un bit, se sabe que el bit que ocasiono el error es el conenido en el bloque defectuoso. Esta configuracion es tan potente como la RAID- • • • • • 2, pero es mucho mas barata por lo que es mas utilizada. RAID-4. Los bloques son escritos distribuidamente en los discos, y se mantiene un disco para guardar la paridad de los bloques guardados en los discos, para poder recuperarlos si hay errores. RAID-5. Es lo mismo que el 4, solo que la paridad no esta guardada en un disco especial sino que esta distribuida entre los discos. RAID-6. En este nivel se agrega mas informacion redudante de manera de estar cubierto contra fallas simultaneas de mas de un disco. Se aplican codigos de Reed-Solomon. RAID 0+1. Es una combinacion de los niveles 0 y 1. En eficiente y confiable, pero es muy cara, porque requiere aumentar mucho la cantidad de discos. Se tienen dos conjuntos de discos funcionando en modo RAID-0, espejados entre ellos. RAID 1+0. Es otra configuracion de los niveles 0 y 1. En este caso, se tienen N discos espejados de a pares (RAID-1), que se incorporan (como si fueran un unico disco logico) en una configuracion RAID-0 Sistemas de archivos Los dispositivos masivos de la parte anterior permiten almacenar informacion de forma no volatil. El sistema operativo, abstrae las propiedades fisicas de los distintos dispositivos y presenta a usuario una unidad uniforme de almacenamiento, el archivo. El sistema se ocupa de traducir los archivos a la forma en que son almacenados en los dispositivos masivos. Los archivos poseen atributos, como: Nombre (una manera de dar a los usuarios una manera facil de identificar a los archivos. Pueden estar duplicados si el sistema de archivos soporta directorios), Identificador (que identifica al archivo de forma unica dentro de todo el sistema de archivos), tipo (ejecutable, datos, etc), ubicación (puntero a la ubicación donde se encuentra el archivo en disco), tamanio (en bytes o cantidad de bloques), proteccion (Indica como puede ser utilizado el archivo por los distintos usuarios), informacion de conteo (fecha de creacion, ultimo acceso, etc). El sistema provee servicios para la manipulacion de archivos: • Abrir y crear: Se provee una manera de crear nuevos archivos, y “entrar” a estos para leer o modificar su contenido. • Escribir: Para escribir en el archivo. • Leer: Para leer desde el archivo. • Reposicionar dentro del archivo: Para cambiar la posicion donde se lee o escribe en el archivo. • Eliminar: Para quitar el archivo del sistema. • Truncar: Para vaciar el archivo sin borrarlo del sistema. Por lo general, el sistema mantiene una tabla con los archivos abiertos por los procesos. Estos abren procesos cuando desean hacer operaciones sobre ellos, y cierran el archivo antes de terminar su ejecucion. Un archivo abierto implica que el sistema debe maneter informacion sobre esta apertura (por lo menos debe ser guardado el file pointer, puntero en donde se escribira o leera del archivo). Ademas, el sistema puede guardar la informacion de cuantos archivos hay abiertos (en total y por proceso), cuantos procesos tienen abierto un archivo particular, ubicación del archivo dentro del dispositivo de almacenamiento, y derechos de acceso. En algunos sistemas, se proveen maneras de mutuoexcluir el acceso a los archivos, de manera que un solo proceso sea capaz de manipular cada archivo por vez. Muchos sistemas mapean el contenido del archivo en el espacio de memoria de un proceso, de manera de no tener que usar operaciones especiales para trabajar con ellos sino que es suficiente modificar el contenido de la memoria correspondiente. Esto tiene el beneficio de evitar llamadas al sistema para modificar el archivo. • • Existen varias maneras de acceder a los archivos: Secuencial: La informacion es accedida en orden, cada vez que se lee algo se incrementa el file pointer. (Se corresponde con la manera de acceder los archivos en una cinta). Directo: Es posible leer y escribir en cualquier posicion del archivo en cualquier momento. (Se corresponde con la manera de acceder a un disco, que puede acceder a lugares distintos en cualquier momento). Directorios En los sistemas de acrhivos generalmente los archivos se encuentran agrupados dentro de directorios, los que permiten a los usuarios tener una organización logica del sistema. Las operaciones sobre directorios son: • Buscar: Para buscar archivos dentro de los sirectorios. • Crear un archivo: Para crear un archivo dentro del directorio. • Eliminar: Para eliminar un archivo de un directorio. • Listar: Para listar todos los archivos contenidos en el directorio. • Renombrar un archivo: Cambiar el nombre de un archivo dentro de un directorio. • Permitir la navegacion: Operaciones para permitir la navegacion entre los directorios del sistema de archivos. Los sistemas mas sencillos soportan un unico nivel de directorios. Cuando los sistemas se van agrandando esto resulta poco practico ya que , por ejemplo, es imposible tener dos archivos con el mismo nombre dentro de un directorio. Sistemas mas complejos permiten tener estructuras arborecentes para almacenar los directorios. La manera de lograr esto es haciendo que los directorios puedan contener archivos de “tipo directorio”, y asi recursivamente. Se denomina ruta absoluta (path) de un archivo al camino desde la raiz del arbol hasta el archivo. Sistemas aun mas avanzados permiten estructuras con forma de grafo para representar los directorios y los archivos. Esto se logra mediante la implementacion de soft links y hard links. Los soft links son una manera de incluir enlaces simbolicos a una ruta dentro de otro directorio. Los hard links permiten que un archivo se encuentre simultaneamente en mas de un directorio. Proteccion de archivos En sistemas multiusuario, es necesario incluir funciones para proteger el acceso de los usuarios a los archivos. En muchos sistemas los usuarios pueden clasificarse en grupos según el rol que tienen en el sistema (eventualmente un usuario puede pertenecer a mas de un perfil). Es posible definir permisos sobre un archivo a nivel de usuarios y/o a nivel de grupos. Los permisos mas comunes son leer, escribir, ejecutar, listar, eliminar. Implementacion de un sistema de archivos La implementacion debe preocuparse de dos cosas: Cual sera la interfaz para que un usuario pueda acceder al sistema de archivos, y cuales seran los algoritmos y estructuras de datos usadas para representar los archivos y directorios. La implementacion de los sistemas de archivos se realiza en capas • Los dispositivos fisicos proveen la siguietne estructura: Bloque de control para el boot (boot control block): Contiene la informacion necesaria para • • • • • • • bootear el sistema operativo. Bloque de control de la particion (partition control block): Contiene la cantidad de particiones en el disco, los bloques utilizados y libres, etc. Estructura de directorios: Contiene la informacion de los directorios para organizar los archivos Bloque de control del archivo: Contienen la informacion de los archivos contenidos en el sistema. Este bloque contiene: ◦ Los permisos del archivo ◦ Fechas (creacion, modificacion, ultimo acceso) ◦ usuario propietario, grupo propietario ◦ tamanio ◦ bloques de datos asignados al archivo El sistema mantiene en memoria: La tabla de particiones de los sistemas de archivos en el disco La estructura de directorios de los directorios accedidos recientemente File descriptors de los archivos abiertos en el sistema File descriptors abiertos por un proceso especifico Sistema de archivos virtual Es comun que un mismo sistema acceda a varios sistemas de archivos, con implementaciones distintas. Se utilizan tecnicas orientadas a objetos para uniformizar el acceso a los sistemas. Esto genera una estructura en tres capas: Interfaz del sistema de archivos (que provee las operaciones), Sistema de archivos virtual (Virtual File Server), y las implementaciones especificas de los sistemas de archivos. Este sistema provee dos funcionalidades importantes: Abstrae las implementaciones particulares y provee una interfaz unica a sistema para acceder a los archivos. Permite tener bloques de control de archivo virtuales que pueden ser mapeados a archivos locales o a traves de una red. Estructura de los directorios Para organizar la informacion de los archivos contenidos en un directorio existen varias alternativas: • Lista encadenada (cada nodo guarda el nombre del archivo y el puntero al bloque de control del archivo). Las bajas y busquedas se realizan en tiempo lineal. • Hash abierto (con clave igual al nombre del archivo) • • • Metodos de asignacion Para alocar los archivos en el disco, existen varias maneras: Asignacion continua: Toda la informacion se encuentra contigua en el disco, se guarda la informacion de donde comienza el archivo y su largo. Sufre de fragmentacion externa, y es ineficiente ya que si los archivos crecen es necesario moverlos a espacios libres mas grandes. Para evitar esto se asignan espacios mas grandes para minimizar este problema. Asignacion en forma de lista: Los bloques forman una lista encadenada. Es necesario guardar punteros al primer y ultimo bloque. No sufre fragmentacion externa. El acceso a los bloques es lineal, y en cada bloque se mantiene la informacion del bloque siguiente. La perdida de la informacion de un bloque provoca la perdida de la informacion de todos los bloques sucesores. Ej: FAT. Se crea una tabla al inicio de la particion con la informacion, para cada bloque, de cual es el bloque siguiente en la lista. Asignacion indexada: Se mantiene una tabla indicando la posicion de todos los bloques utilizados por el archivo. Esta tabla ocupa lugar, por lo que se intenta minimizarla, aunque esta minimizacion implica la limitacion de la cantidad de bloques usados por un archivo. Una posibilidad es tener indexacion con varios niveles, donde una referencia puede ser referida directamente a un bloque del archivo o a un nuevo bloque de indexacion. Administracion del espacio libre Es necesario que el sistema sepa donde esta el espacio libre del sistema. Para esto hay alternativas: • Vector de bits (un bit por bloque, 1 ocupado 0 libre o viceversa) • Lista de bloques libres: Lista encadenada con los bloques libres en el disco • Agrupacion: Lista encadenada con las regiones contiguas de disco libres (uno o mas bloques). • Conteo: Se mantiene una lista de bloques que indica cuantos bloques a partir de este estan libres. ENTRADA/SALIDA Una de als tareas fundamentales del sistema operativo es controlar las operaciones sobre los dispositivos de E/S. El nucleo del sistema es estructurado para aceptar modulos para tratar con los distintos dispositivos. Estos modulos, los device drivers proporcionan una manera uniforme de acceder a los dispositivos. Los dispositivos se comunican con la computadora a traves de puertos, los que usualmente tienen un conjunto de registros para este fin. Si muchos dispositivos iguales se quieren comunicar con la computadora entonces lo hacen mediante un bus, un conjunto de cables con reglas (un protocolo) de como deben ser usados para comunicar las distintas partes. Los dispositivos tienen controladores, que son chips electronicos que tienen implementada parte de la logica de como funciona el dispositivo, por lo que su complejidad depende de que dispositivo tenga que controlar. La comunicación entre la CPU y los dispositivos se puede dar de varias maneras. Una de ellas es la incorporacion de instrucciones especificas para este fin (las instrucciones envian seniales apropiadas a los puertos de E/S correspondientes), y otra es la definicion de algunas posiciones de memoria y realizar la comunicación a traves de estas direcciones (los registros de los dispositivos son mapeados a la memoria principal). Un puerto de E/S generalmente consta de los siguientes registros: Estado (indica el estado del dispositivo (listo, realizando operaciones, operaciones terminadas, etc), el sistema solo puede leer este registro), Control (Es escrito por el sistema operativo para enviar comandos al dispositivo), Datos de entrada (son leidos por el sistema para obtener la entrada), datos de salida (son escritos por el sistema para enviar salida al dispositivo) Una operación de entrada/salida puede ser realizada de varias maneras, sobre todo la parte relacionada a la espera hasta que la operación es terminada. Una alternativa es la E/S programada, en la que el procesador se queda haciendo busy-waiting hasta que llega el resutlado, otra es E/S basada en interrupciones, en la que la CPU es destinada a otros trabajos hasta que el dispositivo termina y interrumpe al procesador para que atienda su pedido, y la ultima es la basada en DMA, en que el sistema envia el pedido al dispositivo y luego asigna la CPU a otras tareas. Mientras tanto, el dispositivo va cargando en memoria principal el resultado de la operación, e interrumpe al procesador cuando termina la transferencia. (Existe un componente de hardware, llamado controlador DMA, que se ocupa de esto) Esto es util en dispositivos que hacen grandes transferencias de datos. En los ultimos dos casos es necesario escribir rutinas de atencion de la interrupcion para atender las interrupciones que indican que los dispositivos terminaron, y hacer lo que corresponda con el proceso que pidio la E/S. El sistema ofrece estructuras e interfaces apropiadas para comunicarse con la E/S. Con esto se abstrae el hardware del sistema y se generan capas en el software. La transferencia puede darse de a bloques (grandes volumentes de datos) o de a caracteres (volumenes de datos pequenios). Las operaciones pueden ser bloqueantes, en cuyo caso cuando un proceso pide algo se bloquea hasta que se termina de atender la operación, o no bloqueantes, en las que el proceso puede continuar su ejecucion mientras se realiza el pedido. Las operaciones ademas pueden ser sincronicas o asincronicas. En el primer caso es una operación bloqueante, y el proceso queda esperando a que termine la operación, en el segundo caso la operación es ejecutada en paralelo y cuando termina una senial es enviada al proceso para indicarle esto. Son dificiles de utilizar. El nucleo del sistema operativo provee servicios relacionados a la E/S, estos estan relacionados a las siguientes operaciones: Planificacion de E/S, Buffering, Caching, Spooling, y Manejo de Errores. Planificacion de E/S Los pedidos que llegan para un dispositivo no tienen porque llegar en un orden que permita ejecutarlos a todo de forma eficiente. Por esta razon, se implementan algoritmos que cuando llega un nuevo pedido ordenan de nuevo los pedidos de manera de lograr una mayor eficiencia en el uso del dispositivo. Buffering Hay tres razones para usar buffering: 1. Hacer de intermediario para dos dispositivos con velocidades distintas. 2. Unificar la transferencias entre dispositivas que transmiten de a bloques con tamanios distintos. 3. Uniformizar las interfaces del sistema: En el comando write el sistema copia de la memoria del proceso a un buffer interno, independizandose de la aplicación. Caching Es utilizado para acelerar el acceso a la informacion, guardando una copia de los datos en memoria mas rapida que la memoria que lo contiene, aunque genera el problema de mantener la consistencia de la informacion. Spooling Es un buffer que mantiene la informacion de salida de un dispositivo que no se puede intercalar. Esto sirve para atender pedidos concurrentes sin alterar el orden en que salen los pedidos. El proceso no se bloquea, y el sistema envia la informacion al dispositivo cuando lo crea conveniente. (Caso impresora) Manejo de Errores El hardware informa al sistema operativo si la ultima operación tuvo éxito o no. En caso de que no tenga éxito, el sistema puede informar al proceso de este error (en UNIX la variable errno se ocupa de esto)