Dispositivos de Entrada y Salida

 Modulos de entrada y salida   

• Bus de datos: de 8, 16, 32 ´o 64 bits dependiendo del modelo (64 bits para los Pentiums de ultima generación). El número de bits se usa, en general, para determinar el tamaño(size) del procesador.​ 

• Bus de direcciones: para poder conectar la CPU con la memoria y con los dispositivos de entrada/salida.  

• Bus de control: para enviar señales que determinan cómo se comunica el CPU con el resto del sistema (por ejemplo, las líneas de lectura (read) y escritura (write) especifican qué es lo que se está haciendo en la memoria).​

Una de las funciones principales de un sistema operativo consiste en controlar todos los dispositivos de entrada y salida de la computadora. Este debe emitir comandos a los dispositivos, capturar interrupciones y manejar errores.

También debe proporcionar una interfaz entre los dispositivos y el resto del sistema que sea simple y fácil de utilizar.  El código de e/s representa una fracción significativa del sistema operativo en su totalidad.​

Los dispositivos de E/S se pueden clasificar en dos categorías: dispositivos de bloque y dispositivos de caracteres.

Dispositivos de bloque 

Es aquel dispositivo que almacena información en bloques de tamaño fijo, cada uno con su dirección, los tamaños comunes de bloques vas de 128 bytes a 1024 bytes. ​

La propiedad esencial de un dispositivo de bloque es que es posible leer o escribir cada bloque de forma independiente de los demás, es decir que el programa en cualquier momento puede  leer o escribir en cualquiera de los bloques.​

Es un dispositivo de bloque por que no importa donde este el brazo del lector, siempre es posible buscar otro cilindro y esperar a que el bloque requerido se encuentre debajo de la cabeza. Ahora si se considera una cinta magnética que contenga bloques de 1K bytes.

Disco Si la unidad de cinta le da un comando de leer el bloque N, esta siempre puede regresar la cinta y adelantarla asta que encuentre el bloque N. 

 

Dispositivos de caracter

Este envía y recibe  un flujo de caracteres, sin sujetarse a una estructura de bloques. No se puede utilizar direcciones ni tienen una operación de búsqueda. 
Las terminales, impresoras de línea, cintas de papel, tarjetas perforadoras, interfaces de una red, ratones y los otros dispositivos no parecidos a los discos son dispositivos de carácter.

 

 Interrupciones

En la E/S programada el procesador tiene que esperar un tiempo considerable a que el  módulo de E/S esté preparado para realizar la operación. El procesador espera comprobando  repetidamente el estado del módulo de E/S, degradándose significativamente el rendimiento de la  CPU. Para evitar este inconveniente se introdujo el sistema de interrupciones en los procesadores.  Básicamente una interrupción viene determinada por la ocurrencia de una señal externa que  provoca la bifurcación a una dirección especifica de memoria, interrumpiendo momentáneamente  la ejecución del programa.

En el caso de la entrada/salida por interrupciones, es el dispositivo quien establece el momento en que se realiza la transferencia de los datos, avisando a la CPU de que ha ocurrido un evento (por ejemplo, que el usuario haya presionado una tecla). En este punto, debemos aclarar que en la familia 80x86 existen tres tipos de interrupciones, que a veces producen confusión por la nomenclatura empleada en diversos textos:

1. Las traps o interrupciones software son interrupciones invocadas por el usuario desde programa. En este caso, la CPU pasa a ejecutar el manejado de trap asociado (su rutina de atención a la interrupción o ISR2).

2. Las excepciones son traps generadas automaticamente en respuesta a alguna condición excepcional producida al intentar ejecutar una instrucción: división por cero, codigo de

operación ilegal. . . También en este caso se ejecuta la ISR asociada, decidiendo, en su caso, que hacer con la situación anómala.

3. Las interrupciones hardware, a las que llamaremos simplemente “interrupciones”, se basan en un evento hardware externo a la CPU y no relacionado con la secuencia de instrucciones que se este ejecutando en ese momento. Son las que un ingeniero electrónico mas intuitivamente relacionarıa con el termino “interrupción”, y con las que vamos a tratar en este proyecto.

Para cada tipo de interrupción, por tanto, se puede instalar una rutina de atención o servicio de interrupción. Cuando la CPU recibe notificación de la interrupción detiene el programa en ejecución, ejecuta la ISR (es decir, sirve al dispositivo haciendo que cese su petición de interrupción (si es necesario, se accede al controlador de interrupciones para hacer lo mismo)) y finalmente devuelve el control al programa, restaurando su estado anterior.

Comunicación entre procesos

La comunicación es una función básica de los sistemas operativos que provee un mecanismo que permite a los procesos comunicarse y sincronizarse entre ellos, normalmente a través de un sistema de bajo nivel.

En un sistema, los procesos pueden ejecutarse independientemente o cooperando entre sí. Los intérpretes de comandos son ejemplos típicos de procesos que no precisan la cooperación de otros para realizar sus funciones. En cambio, los procesos que sí cooperan necesitan comunicarse entre sí para poder completar sus tareas.

La comunicación entre procesos puede estar motivada por la competencia o el uso de recursos compartidos o porque varios procesos deban ejecutarse sincronizadamente para completar una tarea.

Características:

La comunicación puede ser:

• Síncrona: Quien envía permanece bloqueado esperando a que llegue una respuesta del receptor antes de realizar cualquier otro ejercicio.
• Asíncrona: Quien envía continúa con su ejecución inmediatamente después de enviar el mensaje al receptor.
• Persistente: El receptor no tiene que estar operativo al mismo tiempo que se realiza la comunicación, el mensaje se almacena tanto tiempo como sea necesario para poder ser entregado (por ejemplo, un e-mail). 
• Momentánea (transient): El mensaje se descarta si el receptor no está operativo al tiempo que se realiza la comunicación. Por lo tanto no será entregado.
• Directa: Las primitivas “enviar” y “recibir” especifican el nombre del proceso con el que se comunican.
• Indirecta: Es aquella donde la comunicación está basada en una herramienta o instrumento ya que el emisor y el perceptor están a distancia.
• Simétrica: Todos los procesos pueden enviar o recibir. También llamada bidireccional para el caso de dos procesos.
• Asimétrica: Un proceso puede enviar, los demás procesos sólo reciben. También llamada unidireccional. Suele usarse para hospedar servidores en Internet.
• Uso de búfer automático: El transmisor se bloquea hasta que el receptor recibe el mensaje (capacidad cero).

Funciones:

Se puede utilizar distintos mecanismos de comunicación entre procesos:

• Pipes anónimos: Permite redireccionar las entradas o salidas de un proceso utilizando la línea de comandos.
• Sockets: Usan la familia de protocolos TCP/IP(utilizada en internet). Su diseño proviene de Unix.
• Estándares de paso de mensajes MPI: interface, muy utilizada en clusters y supercomputadosas o PVM utilizada en los multiprocesadores.
• Llamadas o procedimientos remotos RPC: permiten realizar las comunicaciones entre procesos como si se tratase de simples llamadas a funciones.
• Middleware: software que se utiliza para conectar los componentes de un sistema distribuido.

Subprocesos

Subprocesos y procesos son conceptos relacionados en informática. Los dos representan secuencias de instrucciones que se deben ejecutar en un orden concreto. Sin embargo, las instrucciones de subprocesos o procesos independientes se pueden ejecutar en paralelo.

Los procesos existen en el sistema operativo y corresponden a lo que los usuarios consideran programas o aplicaciones. Por otra parte, un subproceso existe dentro de un proceso. Por esta razón, los subprocesos se denominan a veces procesos ligeros. Cada proceso está compuesto por uno o más subprocesos.

La existencia de varios procesos permite a un equipo realizar más de una tarea a la vez. La existencia de varios subprocesos permite a un proceso dividir el trabajo que se va a realizar en paralelo. En un equipo con multiprocesadores, los procesos o subprocesos pueden ejecutarse en procesos diferentes, lo que habilita el verdadero procesamiento paralelo.

El procesamiento paralelo perfecto no siempre es posible. Los subprocesos necesitan a veces sincronizarse. Un subproceso tiene que esperar al resultado de otro subproceso o puede necesitar acceso exclusivo a un recurso que otro subproceso está utilizando. Los problemas de sincronización son una causa común de errores en las aplicaciones multiproceso. A veces los subprocesos pueden acabar esperando un recurso que nunca está disponible y se produce una condición denominada interbloqueo.

Modelo de subprocesos

Sección critica

La sección crítica es la parte que debe protegerse de interferencias de otros procesos. También se define como a la porción de código de un programa de computador el cual accede a un recurso compartido (estructura de datos ó dispositivo) que no debe de ser accedido por más de un hilo en ejecución (thread). La sección crítica por lo general termina en un tiempo determinado y el hilo, proceso ó tarea solo tendrá que esperar un período determinado de tiempo para entrar.

Se necesita de un mecanismo de sincronización en la entrada y salida de la sección crítica para asegurar la utilización exclusiva del recurso.

Problemas de la sección critica:

El problema de la sección crítica es uno de los problemas que con mayor frecuencia aparece cuando se ejecutan procesos concurrentes.

Para entender un poco mejor el concepto se presenta el siguiente ejemplo: Se tiene un Sistema Operativo que debe asignar un identificador de proceso (PID) a dos procesos en un sistema multiprocesador.

Cuando el SO realiza esta acción en dos procesadores de forma simultánea sin ningún tipo de control, se pueden producir errores, ya que se puede asignar el mismo PID a dos procesos distintos.

Este problema se debe a que constituyen una sección crítica que debe ejecutarse en forma atómica, es decir, de forma completa e indivisible y ningún otro proceso podrá ejecutar dicho código mientras el primero no haya acabado su sección.

Solución a la sección crítica:

Para resolver el problema de la sección crítica es necesario utilizar algún mecanismo de sincronización que permita a los procesos cooperar entre ellos sin problemas. Este mecanismo debe proteger el código de la sección crítica y su funcionamiento básico es el siguiente:

Cada proceso debe solicitar permiso para entrar en la sección  crítica, mediante algún      fragmento de código que se denomina de  forma genérica entrada en la sección crítica.

Cuando un proceso sale de la sección critica debe indicarlo  mediante otro fragmento de código que se denomina salida de la

Sección crítica. Este fragmento permitirá que otros procesos  entren a ejecutar el código de la sección crítica.

Cualquier solución que se utilice para resolver este problema debe cumplir los tres requisitos siguientes:

Exclusión mutua: Si un proceso está ejecutando código de la  sección crítica, ningún otro proceso lo podrá hacer.

Progreso: Si ningún proceso está ejecutando dentro de la sección crítica, la decisión de qué proceso entra en la sección se hará  sobre los procesos que desean entrar.

Espera acotada: Debe haber un límite en el número de veces que se  permite que los demás procesos entren a ejecutar código de la

Sección crítica después de que un proceso haya efectuado una  solicitud de entrada y antes de que se conceda la suya.

Para solucionar las condiciones de competencia se implementó un modelo para prohibir que dos procesos accedan al mismo recurso.

El modelo en cuestión se denomina exclusión mutua.

Exclusión mutua de espera ocupada

Los algoritmos de exclusión mutua se usan en programación concurrente para evitar el uso simultáneo de recursos comunes, como variables globales, por fragmentos de código conocidos como secciones críticas.

La mayor parte de estos recursos son las señales, contadores, colas y otros datos que se emplean en la comunicación entre el código que se ejecuta cuando se da servicio a una interrupción y el código que se ejecuta el resto del tiempo. Se trata de un problema de vital importancia porque, si no se toman las precauciones debidas, una interrupción puede ocurrir entre dos instrucciones cualesquiera del código normal y esto puede provocar graves fallos.

La técnica que se emplea por lo común para conseguir la exclusión mutua es inhabilitar las interrupciones durante el conjunto de instrucciones más pequeño que impedirá la corrupción de la estructura compartida (la sección crítica). Esto impide que el código de la interrupción se ejecute en mitad de la sección crítica.

Requisitos para la exclusión mutua:

1. Sólo un proceso, de todos los que poseen secciones críticas por el mismo recurso compartido, debe tener permiso para entrar en ella en un momento dado.
2. Un proceso que se interrumpe en una sección no crítica debe hacerlo sin interferir con los otros procesos.
3. Un proceso no debe poder solicitar acceso a una sección crítica para después ser demorado indefinidamente, no puede permitirse el interbloqueo o la inanición.
4. Si ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin demora.
5. No se debe suponer sobre la velocidad relativa de los procesos o el número de procesadores.
6. Un proceso permanece en su sección crítica por un tiempo finito.
7. Una manera de satisfacer los requisitos de exclusión mutua es dejar la responsabilidad a los procesos que deseen ejecutar concurrentemente. Tanto si son programas del sistema como de aplicación, los procesos deben coordinarse unos con otros para cumplir la exclusión mutua, sin ayuda del lenguaje de programación o del sistema operativo. Estos métodos se conocen como soluciones por software.

Para solucionar el problema de la exclusión mutua vamos a tener tres tipos de soluciones:

• Soluciones software.
• Soluciones hardware.
• Soluciones aportadas por el Sistema Operativo

Algunos ejemplos de algoritmos clásicos de exclusión mutua son:

• El algoritmo de Dekker.
• El algoritmo de Peterson.

Bloqueo y Desbloqueo

Los bloqueos pueden ser resueltos por el sistema operativo aunque en ocasiones pueden parar la maquina. Un conjunto de procesos se bloquea si cada proceso del conjunto espera un evento que solo puede ser provocado por otro proceso del mismo conjunto. Puesto que todos los procesos están esperando ninguno de ellos realizará el evento que pueda despertar a los demás y todos los procesos esperaran por siempre.

Cuando los recursos son compartidos entre usuarios: 

Pueden producirse interbloqueos en los cuales los procesos de algunos usuarios nunca podrán llegar a su término. Se debe considerar la prevención, evitación, detección y recuperación del interbloqueo y la postergación indefinida, que se da cuando un proceso, aunque no esté interbloqueado, puede estar esperando por un evento que probablemente nunca ocurrirá. 

En algunos casos:

• El precio de liberar interbloqueos en un sistema es demasiado alto.
• El precio de liberar interbloqueos en un sistema es demasiado alto. Permitir el interbloqueo podría resultar catastrófico.

Los sistemas de cómputos tienen muchos recursos que solo pueden ser utilizados por un proceso a la vez: Ej.: impresoras, unidades de cinta, espacio de la tabla de nodos-i.

Los S. O. tienen la capacidad de otorgar temporalmente a un proceso el acceso exclusivo a ciertos recursos.

Frecuentemente un proceso necesita el acceso exclusivo no solo a un recurso, sino a varios.  

Los recursos pueden ser de dos tipos:

Apropiables.

Este tipo de recurso, es aquel que si no esta siendo utilizado por un proceso, el sistema operativo en caso de que otro proceso lo necesite se lo asigna a este proceso. Un ejemplo de este recurso es la memoria.

No apropiables.

Este tipo de recurso, es aquel es si un proceso lo esta necesitando, en este caso no se libera a menos que el proceso lo libere. Un ejemplo de este es la impresora.

Semáforo

Un semáforo es un tipo abstracto de dato, y como tal, su definición requiere especificar sus dos atributos básicos:

• Conjunto de valores que puede tomar.
• Conjunto de operaciones que admite.

Un semáforo tiene también asociada una lista de procesos, en la que se incluyen todos los procesos que se encuentra suspendidos a la espera de acceder al mismo.

Los semáforos admiten dos operaciones:

• Operación Wait: Si el valor del semáforo no es nulo, esta operación decrementa en uno el valor del semáforo. En el caso de que su valor sea nulo, la operación suspende el proceso que lo ejecuta y lo ubica en la lista del semáforo a la espera de que deje de ser nulo el valor.
• Operación Signal: Incrementa el valor del semáforo, y en caso de que haya procesos en la lista de espera del semáforo, se activa uno de ellos para que concluya su operación Wait.

Lo importante del semáforo es que se garantiza que la operación de chequeo del valor del semáforo, y posterior actualización según proceda, es siempre segura respecto a otros accesos concurrentes.

Semáforo binario

Podemos usar semáforos binarios para abordar el problema de la sección crítica en el caso de múltiples procesos. Los procesos comparten un semáforo, mutex, inicializado con el valor 1. Cada proceso P.

Semáforo de conteo

Los semáforos contadores se pueden usar para controlar el acceso a un determinado recurso formado por un número finito de instancias. El semáforo se inicializa con el número de recursos disponibles. Cada proceso que desee usar un recurso ejecuta una operación wait () en el semáforo (con decremento en la cuenta). Cuando un proceso libera un recurso, ejecuta una operación signal() (incrementando la cuenta). Cuando la cuenta del semáforo llega a 0, todos los recursos estarán en uso. Después, los procesos que deseen usar un recurso se bloquearan hasta que la cuenta sea mayor que 0.

Monitor

Un monitor es una colección de procedimientos, variables y estrucuturas de datos que se agrupan en un tipo especial de módulo o paquete. Los procesos pueden invocar los procedimientos de un monitor en el momento en que deseen, pero no pueden acceder directamente a las estrucuturas de datos internas del monitor desde procedimientos declarados afuera del mismo. 

Los monitores poseen una propiedad especial que los hace útiles para lograr la exclusión mutua: solo un proceso puede estar activo en un monitor en un momento dado. Los monitores son una construcción de lenguaje de programación, asi que el compilador sabe que son especiales y puede manejar las llamadas a procedimientos de monitos de una forma diferente a como maneja otras llamadas a procedimientos. Por lo regular, cuando un proceso invoca un procedimiento de monitor, las primeras instrucciones del procedimiento verifican si hay algun otro proceso activo en ese momento dentro del monitor. Si así es, el proceso invocador se suspende hasta que el otro proceso abandona el monitor. Si ningún otro proceso está usando el monitor, el proceso invocador puede entrar. 

Es responsabilidad del compilador implementar la exclusión mutua en las entradas a monitores, pero una forma común es usar un semáforo binario. Puesto que el compilador, no el programador, se esta encargando de la exclusion mutua, es mucho menos probable que algo salga mal. En cualquier caso, la persona que escribe el monitor no tiene que saber como el compilador logra la exclusión mutua; le basta con saber que si convierte todas las regiones criticas en procedimientos de monitor, dos procesos nunca podrán ejecutar sus regiones criticas al mismo tiempo. 

Cuando un procedimiento de monitor descubre que no puede continuar (por ejemplo, si encuentra lleno el buffer) ejecuta WAIT (esperar) con alguna variable de condición digamos full! (lleno). Esta acción hace que el proceso invocador se bloquee, y también permite la entrada de otro proceso al que antes se le había impedido entrar en el monitor.

Este otro proceso puede despertar a su "compañero" dormido ejecutando SIGNAL (señal) con la variable de condición que su compañero está esperando. A fin de evitar la presencia de dos procesos activos en el monitor al mismo tiempo, necesitamos una regla que nos diga qué sucede después de ejecutarse SIGNAL. Hoare propuso dejar que el proceso recién despertado se ejecute, suspendiendo el otro. Brinch Hansen propuso sortear el problema exigiendo al proceso que ejecutó SIGNAL salir inmediatamente del monitor. Dicho de otro modo, una instrucción SIGNAL sólo puede aparecer como última instrucción de un procedimiento de monitor. 

Transmisión de mensajes 

Cuando los procesos interactúan unos con otros, se deben satisfacer dos requisitos básicos: la sincronización y la comunicación. Un método posible para ofrecer ambas funciones es el paso de mensajes. Su funcionalidad real se ofrece, normalmente, por medio de las primitivas send (destino, mensaje) y receive (origen, mensaje).

Un proceso envía información en forma de un mensaje a otro proceso designado como destino. Un proceso recibe información ejecutando la primitiva receive, que indica el proceso emisor (origen) y el mensaje.

Formato de mensajes

Depende de los objetivos del servicio de mensajería y de si el servicio ejecuta en un ordenador independiente o en un sistema distribuido. Para algunos S.O., los diseñadores han elegido mensajes cortos y de tamaño fijo para minimizar el procesamiento y el coste de almacenamiento. Si se va a pasar una gran cantidad de datos, los mismos pueden ponerse en un archivo y el mensaje simplemente hará referencia a este archivo. Una solución más flexible es permitir mensajes de longitud variable con un formato que incluya los campos: origen, destino, longitud del mensaje, información de control, tipo de mensaje y contenido del mensaje.

Problemas de la comunicación de procesos

Los 5 filósofos

En 1965 Dijkstra planteó y resolvió un problema de sincronización llamado el problema de la cena de los filósofos, que se puede enunciar como sigue. Cinco filósofos se sientan a la mesa, cada uno con un plato de espaghetti. El espaghetti es tan escurridizo que un filósofo necesita dos tenedores para comerlo. Entre cada dos platos hay un tenedor.

La vida de un filósofo consta de periodos alternos de comer y pensar. Cuando un filósofo tiene hambre, intenta obtener un tenedor para su mano derecha, y otro para su mano izquierda, cogiendo uno a la vez y en cualquier orden. Si logra obtener los dos tenedores, come un rato y después deja los tenedores y continúa pensando.

Lectores y escritores 

Hay un objeto de datos(fichero de texto) que es utilizado por varios procesos, unos leen y otro que escribe.

Solo puede utilizar el recurso un proceso y solo uno, es decir, o bien un proceso estará escribiendo o bien leyendo, pero nunca ocurrirá simultáneamente (teniendo en cuenta que si no lo esta utilizando nadie, tendrá preferencia el escritor ante el lector).

Se considera a cada usuario (lector y escritor) como dos procesos y al fichero en cuestión como un recurso. De modo que, para que un proceso acceda al recurso que necesita, tenemos que considerar a cada usuario (lector y escritor) como dos semáforos. Estos semáforos son binarios y valen 0 si el recurso (fichero) está siendo utilizado por otro proceso y 1 si dicho recurso está disponible.

Memoria en un Sistema Operativo

Memoria

La memoria es uno de los principales recursos de la computadora, la cual debe de administrarse con mucho cuidado. Aunque actualmente la mayoría de los sistemas de cómputo cuentan con una alta capacidad de memoria, de igual manera las aplicaciones actuales tienen también altos requerimientos de memoria, lo que sigue generando escasez de memoria en los sistemas multitarea y/o multiusuario.

La parte del sistema operativo que administra la memoria se llama administrador de memoria y su labor consiste en llevar un registro de las partes de memoria que se estén utilizando y aquellas que no, con el fin de asignar espacio en memoria a los procesos cuando éstos la necesiten y liberándola cuando terminen, así como administrar el intercambio entre la memoria principal y el disco en los casos en los que la memoria principal no le pueda dar capacidad a todos los procesos que tienen necesidad de ella.

Los sistemas de administración de memoria se pueden clasificar en dos tipos: los que desplazan los procesos de la memoria principal al disco y viceversa durante la ejecución y los que no.

El propósito principal de una computadora es el de ejecutar programas, estos programas, junto con la información que accesan deben de estar en la memoria principal (al menos parcialmente) durante la ejecución.

Para optimizar el uso del CPU y de la memoria, el sistema operativo debe de tener varios procesos a la vez en la memoria principal, para lo cual dispone de varias opciones de administración tanto del procesador como de la memoria. La selección de uno de ellos depende principalmente del diseño del hardware para el sistema.

Jerarquía de la memoria.

 Una jerarquía de memoria es una reacción natural a la localidad y tecnología. Una jerarquía en memoria está organizada en varios niveles, cada uno más pequeño, más rápido y más caro por byte que el siguiente. Los niveles de la jerarquía están contenidos en el siguiente: todos los datos de un nivel se encuentran también en el nivel siguiente y así sucesivamente hasta que alcancemos el extremo inferior de la jerarquía.

Conceptos básicos

Nivel (level)

Bloque o línea (block or line): mínima unidad de información que puede estar presente o no en la jerarquía de dos niveles (tamaño fijo o variable)

Acierto/Fallo (hit/miss)

Frecuencia de aciertos/fallos(hit rate/miss rate)

Tiempo de acierto (hit time)

Penalización por fallo (miss penalty)

• Tiempo de acceso (access time): tiempo para acceder a la primera palabra de un bloque en un fallo
• Tiempo de transferencia (transfer time): tiempo adicional para transferir las restantes palabras del bloque.

Jerarquía de memoria

Registros de procesador: Estos registros interaccionan continuamente con la CPU (porque forman parte de ella). Los registros tienen un tiempo de acceso muy pequeño y una capacidad mínima, normalmente igual a la palabra del procesador (1 a 8 bytes).

Registros intermedios: Constituyen un paso intermedio entre el procesador y la memoria, tienen un tiempo de acceso muy breve y muy poca capacidad.

Memorias caché: Son memorias de pequeña capacidad. Normalmente una pequeña fracción de la memoria principal. y pequeño tiempo de acceso. Este nivel de memoria se coloca entre la CPU y la memoria central. Hace algunos años este nivel era exclusivo de los ordenadores grandes pero actualmente todos los ordenadores lo incorporan. Dentro de la memoria caché puede haber, a su vez, dos niveles denominados caché on chip, memoria caché dentro del circuito integrado, y caché on board, memoria caché en la placa de circuito impreso pero fuera del circuito integrado, evidentemente, por razones físicas, la primera es mucho más rápida que la segunda. Existe también una técnica, denominada Arquitectura Harvard, en cierto modo contrapuesta a la idea de Von Newmann, que utiliza memorias caché separadas para código y datos. Esto tiene algunas ventajas como se verá en este capítulo.

Memoria central o principal: En este nivel residen los programas y los datos. La CPU lee y escribe datos en él aunque con menos frecuencia que en los niveles anteriores. Tiene un tiempo de acceso relativamente rápido y gran capacidad.

Extensiones de memoria central: Son memorias de la misma naturaleza que la memoria central que amplían su capacidad de forma modular. El tiempo de similar, a lo sumo un poco mayor, al de la memoria central y su capacidad puede ser algunas veces mayor.

Memorias de masas o auxiliares: Son memorias que residen en dispositivos externos al ordenador, en ellas se archivan programas y datos para su uso posterior. También se usan estas memorias para apoyo de la memoria central en caso de que ésta sea insuficiente (memoria virtual). Estas memorias suelen tener gran capacidad pero pueden llegar a tener un tiempo de acceso muy lento. Dentro de ellas también se pueden establecer varios niveles de jerarquía.

Asignación de memoria.

Memoria contigua

En los sistemas de ejecución en lotes, así como en las primeras computadoras personales, sólo un programa se ejecutaba a la vez, por lo que, más allá de la carga del programa y la satisfacción de alguna eventual llamada al sistema solicitando recursos, el sistema operativo no tenía que ocuparse de la asignación de memoria.

Al nacer los primeros sistemas operativos multitarea, se hizo necesario resolver cómo asignar el espacio en memoria a diferentes procesos.

Memoria contigua simple

este esquema de gestión consiste en situar a los procesos en la memoria en direcciones consecutivas. existen varios métodos basados en la asignación contigua.

Bare Machine

Se trata de tener solo un proceso en la memoria y permitir que use toda la memoria. el usuario accede a cualquier parte de la memoria. Es la denominada BM. El método tiene máxima flexibilidad y prácticamente toda la responsabilidad recae sobre el usuario. Éste tiene, a su vez todos los derechos y todos los deberes.

Monitor residente

En este esquema se utilizan mecanismos de protección porque distingue una parte de la memoria destinada al monitor o sistema operativo y otra dedicada al usuario. ]En mecanismo de protección nuega al usuario el acceso a la zona de memoria destinada al sistema operativo; de esta manera se evitara que pueda ser modificado. Esta técnica es frecuentemente en microcomputadoras simples. El sistema operativo puede encontrarse en la parte baja de la memoria RAM, o bien puede estar en ROM en la parte alta. Cuando el sistema se organiza de esta forma, sólo puede estar en ejecución un único proceso(monoprogramación).

Memoria particionada

Es el primer mecanismo que puede ser compartida por varios usuarios. A cada una de las zonas asignadas a los distintos usuarios se les denomina partición . Existen varias razones fundamentales para su empleo que pueden quedar resumidas en los siguientes puntos:

• Facilitar la creación de procesos para simplificar una aplicación.
•  Proporcionar servicio interactivo a varios usuarios.
• Mejorar la utilización de la UCP.

Es evidente que el uso de la multiprogramación complica el diseño del sistema operativo, puesto que añade mayor complejidad. 

Algoritmos de planificación de procesos

Proceso

Un proceso es un programa en ejecución. Existen 3 estados en los que puede encontrarse un proceso, estos son: "Listo", "Bloqueado" y "En ejecución". Para el control de los mismos internamente son almacenados en una lista, cada uno de los nodos guarda información de un proceso. En esa información se almacena, entre otros aspectos, el estado en que se encuentra el proceso, el tiempo que el proceso ha usado el CPU, e información de E/S (entrada/salida). Los sistemas operativos cuentan con un componente llamado planificador, que se encarga de decidir cuál de los procesos hará uso del procesador. La toma de esta decisión, así como el tiempo de ejecución del proceso, estará dada por un algoritmo, denominado Algoritmo de Planificación.

Objetivo de la planificación de procesos

La Planificación de procesos tiene como principales objetivos la equidad, la eficacia, el tiempo de respuesta, el tiempo de regreso y el rendimiento.

• Equidad: Todos los procesos deben ser atendidos.
• Eficacia: El procesador debe estar ocupado el 100% del tiempo.
• Tiempo de respuesta: El tiempo empleado en dar respuesta a las solicitudes del usuario debe ser el menor posible.
• Tiempo de regreso: Reducir al mínimo el tiempo de espera de los resultados esperados por los usuarios por lotes.
• Rendimiento: Maximizar el número de tareas que se procesan por cada hora.

Ejemplos

• Primero en llegar primero en ser servido: Conocido como FCFS (First Come First Served). Este algoritmo emplea una cola de procesos, asignando un lugar a cada proceso por el orden de llegada. Cuando el proceso llega es puesto en su lugar en la cola después del que llegó antes que él y se pone en estado de listo. Cuando un proceso comienza a ejecutarse no se interrumpe su ejecución hasta que termina de hacerlo.
• Prioridad al más corto: Su nombre es SJF (Shortest Job First). El proceso que se encuentra en ejecución cambiará de estado voluntariamente, o sea, no tendrá un tiempo de ejecución determinado para el proceso. A cada proceso se le asigna el tiempo que usará cuando vuelva a estar en ejecución, y se irá ejecutando el que tenga un menor tiempo asignado. Si se da el caso de que dos procesos tengan igual valor en ese aspecto emplea el algoritmo FCFS. 
• Round Robin: A cada proceso se le asigna un tiempo determinado para su ejecución, el mismo tiempo para todos. En caso de que un proceso no pueda ser ejecutado completamente en ese tiempo se continuará su ejecución después de que todos los procesos restantes sean ejecutados durante el tiempo establecido. Este es un algoritmo basado en FCFS que trata la cola de procesos que se encuentran en estado de listos como una cola circular. 
• Planificación por prioridad: En este tipo de planificación a cada proceso se le asigna una prioridad siguiendo un criterio determinado, y de acuerdo con esa prioridad será el orden en que se atienda cada proceso.
• Planificación garantizada: Para realizar esta planificación el sistema tiene en cuenta el número de usuarios que deben ser atendidos. Para un número "n" de usuarios se asignará a cada uno un tiempo de ejecución igual a 1/n.
• Planificación de Colas Múltiples: El nombre se deriva de MQS (Multilevel Queue Schedulling). En este algoritmo la cola de procesos que se encuentran en estado de listos es dividida en un número determinado de colas más pequeñas. Los procesos son clasificados mediante un criterio para determinar en qué cola será colocado cada uno cuando quede en estado de listo. Cada cola puede manejar un algoritmo de planificación diferente a las demás.

Paginación simple

Es un método para resolver el problema de la fragmentación externa. Este método se basa en dividir el espacio de memoria asignado a cada proceso en páginas de memoria. Las unidades correspondientes en la memoria física se denomina marcos de página. Las páginas y los marcos son del mismo tamaño, y tienen que ser una potencia de  2. De esta forma se proporciona una memoria superior a la memoria física, al hacer desaparecer la diferencia aparente entre memoria principal y memoria secundaria y no tener que utilizar zonas de memoria contiguas.

Segmentación simple

Al desarrollar un programa, el programador no ve a la memoria como un sólo arreglo plano, en el que todas las direcciones son iguales (si bien está consciente de que la realidad es así). El uso que damos a la memoria sigue una lógica de distintos segmentos: En vez de dar una dirección lineal, damos al procesador una dirección de segmento y un desplazamiento dentro de dicho segmento. Podemos tener segmentos de distintos tamaños presentes en memoria, y la resolución de direcciones de cada uno de ellos se realizará por mecanismos análogos al descrito en el apartado anterior (registro base y desplazamiento). Claro está, esto debe también hacerse con apoyo del MMU.

Paginación por demanda

Un sistema de paginación por demanda es similar a un sistema de paginación con intercambios. Los procesos residen en memoria secundaria (en el disco). Cuando queremos ejecutar un proceso, lo metemos en memoria. Sin embargo, en vez de intercambiar todo el proceso hacia la memoria, utilizamos un intercambiador perezoso. Un intercambiador perezoso nunca reincorpora una página a memoria a menos que se necesite. Como ahora consideramos un proceso como una secuencia de páginas, en vez de un gran espacio contiguo de direcciones, el término intercambio es técnicamente incorrecto. Un intercambiador manipula procesos enteros, mientras que un paginador trata con las páginas individualmente de un proceso.

Servicios de Gestión de Memoria

Servicio Posix

El estándar POSIX define servicios de gestión de memoria para realizar la proyección y desproyección de archivos (mmap, munmap). El servicio mmap tiene el siguiente prototipo: 

caddr_t mmap (caddr_t direc, size_t longitud, int protec, 

int indicador, int descriptor, off_t despl); 

El primer parámetro indica la dirección del mapa donde se quiere que se proyecte el archivo. Generalmente, se especifica un valor nulo para indicar que se prefiere que sea el sistema el que decida donde proyectar el archivo. En cualquier caso, la función devolverá la dirección de proyección utilizada. El parámetro descriptor se corresponde con el descriptor del archivo que se pretende 

proyectar (que debe estar previamente abierto) y los parámetros despl y longitud establecen qué zona del archivo se proyecta: desde la posición despl hasta desp + longitud. El argumento protec establece la protección sobre la región que puede ser de lectura (PROT_READ), de escritura (PROT_WRITE), de ejecución (PROT_EXEC) o cualquier combinación de ellas. Esta protección debe ser compatible con el modo de apertura del archivo. Por último, el parámetro indicador permite establecer ciertas 

propiedades en la región: 

• MAP_SHARED. La región es compartida. Las modificaciones sobre la región afectarán al archivo. Un proceso hijo compartirá esta región con el padre. 
• MAP_PRIVATE. La región es privada. Las modificaciones sobre la región no afectarán al archivo. Un proceso hijo no compartirá esta región con el padre, sino que obtendrá un duplicado de la misma
• MAP_FIXED. El archivo debe proyectarse justo en la dirección especificada en el primer parámetro, siempre que éste sea distinto de cero. 

En el caso de que se quiera proyectar una región sin soporte (región anónima), en algunos sistemas se puede especificar el valor MAP_ANOM en el parámetro indicador. Otros sistemas UNIX no ofrecen esta opción pero permiten proyectar el dispositivo /dev/zero para lograr el mismo objetivo.

Cuando se quiere eliminar una proyección previa o parte de la misma, se usa el servicio munmap cuyo prototipo es:

 int munmap (caddr_t direc, size_t longitud); 

Los parámetros direc y longitud definen una región (o parte de una región) que se quiere desproyectar.

Procesos en los sistemas operativos

Proceso

Es un programa en ejecución. Tiene un conjunto de registros que esta usando,  un contador de programa que indica las instrucciones que se deben ejecutar, y una pila. Esto significa que tiene un flujo de control que ejecuta una instrucción tras otra.

Un proceso es una serie de sentencias asignadas a una tarea, una vez que contribuye la tarea con el programa. Un programa es un conjunto de sentencias que pueden incluir varios procesos.

Programa	Proceso
Requiere compilador o interprete	Valores
Cuando se ejecutan se presenta como un proceso	Información de su estado
Se desarrolla por lenguaje de alto nivel	Asigna recursos

Modelo del proceso

Todo el software ejecutable, inclusive el Sistema Operativo, se organiza en varios procesos secuenciales. Un proceso incluye al programa en ejecución y a los valores que están activados en el contador, registros y variables del mismo programa. Conceptualmente cada proceso tiene su propia CPU virtual.

Si la CPU se alterna entre los procesos, la velocidad a la que se ejecuta un proceso no será uniforme, por lo que es necesario anclar lo siguiente:

• Que los procesos no deben programarse con hipótesis implícitas acerca del tiempo.
• Que la mayoría de los procesos no son afectados por la multiprogramación inferior de la CPU o las velocidades de un proceso distinto.
• Un proceso es una actividad que tiene un programa, entrada, salida y estado.
• Un solo procesador puede ser compartido entre varios procesos con cierto “algoritmo de planificación”, el cual determina cuando detener el trabajo de proceso y dar servicio a otro distinto.

Estado del proceso

Nuevo: Se dice que un proceso está en estado de nuevo cuando apenas se encuentra en proceso de crearse.

Listo: Un proceso está en estado de listo, cuando podría usar una CPU, si hubiera una disponible.

En ejecución: Se dice que un proceso está estado de ejecución, si en ese momento tiene esta ocupando la CPU.

Bloqueado: Se dice que un proceso está en estado de bloqueado, si espera que ocurra algo, como por ejemplo, la terminación de una E/S, para así poder ponerse en marcha.

Terminado: Cuando un proceso se ha completado su ejecución pasa a ser un proceso terminado.

Bloque de control de procesos

Es la estructura de datos con la que el sistema operativo administra los procesos. Contiene la información acerca del proceso y su estado. Además la información que el Sistema Operativo precisa para manejarlo como:

• Identificador, estado, recursos, historia.

Niveles de planificación

La planificación es el conjunto de mecanismos incorporados al sistema operativo, gobierna el orden en que se deben ejecutar los trabajos. El objetivo de la planificación es optimizar el rendimiento del sistema: 

• Planificación de largo plazo: se encarga de llevar procesos de disco a memoria y viceversa. Seleccionando los trabajos que deben admitirse en el sistema. Se determina a que trabajos se les va a permitir competir activamente por los recursos del sistema, lo cual determina planificación de admisión. 
• Planificación de mediano plazo: En algunos casos, en especial cuando el sistema esta sobrecargado, el planificador encuentra ventajas al retirar trabajos activos en la memoria para reducir el grado de multiprogramación. Equilibra la administración de procesos en el sistema con la asignación del CPU a dichos procesos
• Planificación de corto plazo: Se encarga de pasar de un proceso a otro en memoria principal, determinando a cual proceso listo se le asignara el CPU cuando este se encuentra disponible. Determina que proceso se le asigna al CPU cuando este se encuentra disponible y asigna la CPU al mismo proceso.

Políticas de planificación

Los algoritmos de planificación no se limitan a un plazo de planificación concreto. Aunque en general la planificación de corto plazo es la entrada de procesos al CPU, algunos algoritmos pueden implementarse también a largo plazo o distribuirse en más de un tipo de planificación.

Consideraciones para la planificación:

• Como se seleccionar el proceso que entra a ejecución. De entre los procesos que se están procesando, se elige uno de acuerdo a criterios como: prioridad, tiempo que lleva en la cola de preparados.
• Cuándo se lleva a cabo la planificación de corto plazo. Hay dos alternativas básicas: si únicamente se planifica cuando un proceso abandona al CPU por que se acaba o se bloquea (políticas no expulsoras), o si se puede forzar al proceso que esta usando al CPU a abandonarla para planificar otro proceso (políticas expulsoras).

 Información de un proceso

Despacho de procesos

Algoritmos de planificación de procesos

FCFS

Se elige el proceso a entrar en la CPU según el tiempo que lleva esperando; es decir, en el orden de entrada al estado de preparados. 

La implementación de esta política es sencilla: la cola de procesos preparados se gestiona con disciplina FIFO. 

Presenta el problema del efecto convoy. La existencia de programas muy largos dispara el tiempo de finalización, la latencia y el tiempo de espera medios. En el ejemplo se muestra el orden de ejecución de acuerdo a FCFS de tres procesos que llegan en el orden P1, P2, P3. La latencia media, Tr, es (0+10+11)/3= 7 unidades de tiempo, frente a una Tr mínima de 1 que se obtendría si los procesos se 

planificasen en orden P2, P3, P1. 

Planificación FCFS convoy

SJF (el más corto primero) 

Se selecciona para entrar a ejecutarse el proceso de menor duración. Esta planificación es (teóricamente) óptima para los tiempos medios de respuesta, finalización y espera. 

Es necesario estimar la duración de un proceso. Esta estimación dependerá del plazo 

de la planificación. 

• Largo plazo. El usuario proporciona la estimación. 
• orto plazo. El scheduler puede predecir la duración del próximo intervalo de CPU en función de las duraciones de los intervalos de CPU anteriores. Así, la duración prevista para el instante n+1, τn+1, se calcula a partir de una media ponderada de la duración del intervalo n, tn, y predicciones anteriores: 

τn+1 = αtn + (1−α)τn 

 donde 0≤α≤1. 

Al trabajar con estimaciones en lugar de duraciones reales, el éxito de la planificación dependerá de lo adecuado que sea el modelo de estimación. 

Prioridades

A cada proceso se le asocia una prioridad, a partir de las cual se establece su orden para la planificación. Para igual prioridad, suele tomarse orden FCFS. 

Habitualmente, la prioridad de un proceso se almacena como un entero positivo dentro de su PCB, que se inserta en la cola de preparados de acuerdo a ella para facilitar la labor del scheduler (en planificación de corto plazo). 

La prioridad se establece inicialmente en función de determinados parámetros, como el propietario del proceso, el tipo del proceso (por ejemplo, procesos del sistema, de tiempo real, batch), su tamaño, los recursos que requiere, etc. La prioridad inicial puede usarse para planificar a largo plazo. 

Si la prioridad inicial no cambia durante la ejecución del proceso y ésta se usa para planificar a corto plazo, se obtiene una política de prioridades estáticas. Un problema de las prioridades estáticas es que algunos parámetros, fundamentalmente los referidos al consumo de recursos, y en particular al tiempo de CPU y duración de sus intervalos, no se conocen a priori, por lo que la prioridad puede no ser indicativa de comportamiento del programa. Otro problema es el riesgo de inanición para los procesos de prioridad baja, lo que además puede tener consecuencias para el propio sistema operativo: si un proceso de prioridad alta realiza espera activa para entrar en una sección crítica ocupada por un proceso de prioridad menor, la sección crítica nunca se liberará. 

En general, resulta más adecuada una planificación por prioridades dinámicas. Un proceso se crea con una prioridad base inicial, y su prioridad dinámica se recalcula periódicamente, fundamentalmente de acuerdo al gasto de CPU del proceso. La prioridad de los procesos que más tiempo de CPU han gastado disminuye en relación a la prioridad de los procesos que han gastado menos.

Existen fundamentalmente dos formas de ajustar la prioridad: 

• Periódicamente, como por ejemplo UNIX System V, UNIX 3.2BSD y Linux, que ajustan conjuntamente las prioridades de todos los procesos cada cierto tiempo. 
• Aperiódicamente, como por ejemplo Windows NT y UNIX SVR4, que aprovecha, la transición de estado de un proceso para recalcular la prioridad.

Concurrencia

La concurrencia de procesos se refiere a las situaciones en las que dos o más procesos puedan coincidir en el acceso a un recurso compartido o, dicho de otra forma, que requieran coordinarse en su ejecución. Para evitar dicha coincidencia, el sistema operativo ofrece mecanismos de arbitraje que permiten coordinar la ejecución de los procesos.

Un ejemplo de un problema de concurrencia sería el siguiente: Dados dos procesos A y B, suponiendo que ambos se ejecutan indefinidamente en el tiempo, el proceso A debe recibir tiempo de ejecución antes que B, tras esto, el proceso B debe recibir su oportunidad de ejecución, dando paso de nuevo al proceso A y así sucesivamente.

Programación concurrente

Es la simultaneidad en la ejecución de múltiples tareas interactivas, Estas tareas pueden ser un conjunto de procesos o hilos de ejecución creados por un único programa. Las tareas se pueden ejecutar en una sola CPU, en varios procesadores o en una red de computadoras distribuidas. La programación concurrente está relacionada con la programación paralela, pero enfatiza más la interacción entre tares. Así, la correcta secuencia de interacciones o comunicaciones entre los procesos y el acceso coordinado de recursos que se comparten por todos los procesos o tareas son las claves de esta disciplina.

Ventajas

• No dependen de la arquitectura o n° de elementos de proceso.
• Menos necesidad de compartir el trabajo.
• Menos necesidad de resoluciones de errores.
• Permite resolver problemas que no sería posible con un procesamiento secuencial.

Características

• Orden: orden en que se ejecutan las instrucciones.
• Parcial: no se conoce exactamente la secuencia en la que serán ejecutadas las instrucciones.
• Total: se conoce exactamente el orden en el que se deben ejecutar todas las instrucciones.
• Requisitos para la programación concurrente:
• Sincronización: Capacidad de informar de la situación de un proceso a otro.
• Objetivo: Establecer la secuencialidad correcta de un programa.
• Exclusión mutua.  Asegurar que un solo proceso tiene acceso a un recurso compartido único.
• Por condición. Asegurar que un proceso no progrese hasta que se cumpla una determinada condición
• Comunicación: Capacidad de transmitir información desde un proceso a otro.
• Prioridad: Capacidad de establecer una ordenación de importancia en los procesos.

Multitareas

Es el modo de funcionamiento disponible en algunos sistemas operativos, mediante el cual una computadora procesa varias tareas al mismo tiempo. Existen varios tipos de multitareas. La conmutación de contextos (context Switching) es un tipo muy simple de multitarea en el que dos o más aplicaciones se cargan al mismo tiempo, pero en el que solo se esta procesando la aplicación  que se encuentra en primer plano (la que ve el usuario). Para activar otra tarea que se encuentre en segundo plano, el usuario debe traer al primer plano la ventana o pantalla que contenga esa aplicación. En la multitarea cooperativa, la que se utiliza en el sistema operativo Macintosh, las tareas en segundo plano reciben tiempo de procesado durante los tiempos muertos de la tarea que se encuentra en primer plano (por ejemplo, cuando esta aplicación esta esperando información del usuario), y siempre que esta aplicación lo permita. En los sistemas multitarea de tiempo compartido, como OS/2, cada tarea recibe la atención del microprocesador durante una fracción de segundo. Para mantener el sistema en orden, cada tarea recibe un nivel de prioridad o se procesa en orden secuencial. Dado que el sentido temporal del usuario es mucho más lento que la velocidad de procesamiento del ordenador, las operaciones de multitarea en tiempo compartido parecen ser simultáneas.

Clasificación de la Multitarea

• Nula: Es aquel sistema que carece de multitarea. Puede simular que la implementa en un espacio de usuario. MSDOS.
• Cooperativa: Es el tipo de multitarea en donde los procesos de usuario son quienes ceden la CPU al sistema operativo a intervalos regulares. Windows antes del 95.
• Preferente: es en donde el sistema operativo se encarga de administrar uno o más procesadores, repartiendo el tiempo de uso del mismo ente los distintos procesos que esperan utilizarlo. AmigaOS.
• Real: Es en donde los sistemas operativos ejecutan los procesos al mismo tiempo haciendo uno de múltiples procesadores. La ejecución realmente se realiza en distintos procesadores para cada proceso o tarea. Unix, Mac OS X.

Multiproceso

Las computadoras que tienen mas de un CPU son llamadas multiproceso. Un sistema operativo multiproceso coordina las operaciones de la computadoras multiprocesadoras. Ya que cada CPU en una computadora de multiproceso puede estar ejecutando una instrucci ón, el otro procesador queda liberado para procesar otras instrucciones simultáneamente. Al usar una computadora con capacidades de multiproceso incrementamos su velocidad de respuesta y procesos. Casi todas las computadoras que tienen capacidad de multiproceso ofrecen una gran ventaja. Los primeros Sistemas Operativos Multiproceso realizaban lo que se conoce como: Multiproceso asimétrico: Una CPU principal retiene el control global de la computadora, así como el de los otros procesadores. Esto fue un primer paso hacia el multiproceso pero no fue la dirección ideal a seguir ya que la CPU principal podía conv ertirse en un cuello de botella. Multiproceso simétrico: En un sistema multiproceso simétrico, no existe una CPU controladora única. La barrera a vencer al implementar el multiproceso simétrico es que los SO tienen que ser rediseñados o diseñados desde el principio para trabajar en u n ambiente multiproceso. Las extensiones de Unix, que soportan multiproceso asimétrico ya están disponibles y las extensiones simétricas se están haciendo disponibles. Windows NT de Microsoft soporta multiproceso simétrico.