SoWiKi, sistemas operativos - Recently Updated Pages

SoWiKi, sistemas operativos Home

jercoli — Fri, 09 Oct 2009 10:16:25 CDT

Novedades !!

Ejercicio tipo "final" en página de Apuntes y TP

Notas 1er Parcial - (T.Mañana y T.Noche - 2009 - 2do.Cuat.)

Proyecto wiki sobre sistemas operativos.
Materia de Arquitectura y SO de la Tecnicatura Sup. en Programaciòn de la UTN Ctro. de estudios Mar del Plata

Desarrollado por alumnos del cursado 2008 + docente de la càtedra como administrador(Jorge Ercoli)

Objetivos del Wiki

Fomentar el trabajo colaborativo del grupo de alumnos, permitiendo mayor interacciòn con la càtedra
Centralizar la informaciòn de la materia en un ùnico punto
Permitir la discusiòn de los temas de la materia, entre los alumnos y con el docente; fuera del àmbito del aula.
Compilar el material investigado y la bùsqueda de bibliografìa, consensuar el contenido entre alumnos y docente

Importante:

Cuando hagamos comentarios que nos parecen útiles sobre tecnología actual que encuadre en temas de S.O., generemos comentarios (threads) en la página YA CREADA que corresponda
Apuntes y TP de la cátedra en su propia página (Apuntes y TP).

Bibliografía recomendada

BootLoader para Vista: EasyBCD 1.7

Notas Parciales

jercoli — Fri, 09 Oct 2009 10:15:17 CDT

SO - T.Mañana 2009-C2

		1Parcial
Antunica		2
Baroni		8
Caravajal		6
Dell		5
Diaz		7
Larroque		3
Lopez		8
Oyarzun		2
Pascua		2
Piccolini		9
Ricotti		2,5
Sanz		3
Veiga		9
Vieytes		4

Recup. 1er. Parcial: jueves 15/10

SO - T.Noche (2009 - C2)
		1er.Parcial

Ghiglione		5
Forte		5
Carballo		2
Oviedo		4
Carrizo		5
Suarez		8
Marquez		4
Bertuzzi		5
Martin		5
Gonzalez, D.		5
Corbo		3
Diaz		6
Santiago		5
Nizzi		7
Tarchini		2
Osorio		3
Drago		1
Escariz		2
Ierace		7
Leiva		5
Labrunee		7
Escalante		2
Escobar		4
Alsina		4
Dematteis		9
Trocoli		4
Seijo		4
Rollhauser		5

Recup. Lunes 19/10

Apuntes y Trabajos Prácticos

jercoli — Fri, 15 May 2009 06:53:13 CDT

Apuntes

Apunte general de la cátedra

Apunte SD-Redes I
Apunte SD-Redes II

Procesos

Cuestionario 1 (Preguntas sobre procesos en gral.)
Cuestionario 2 (TP sobre algoritmos de planificación)

Sist.Distrib.-Redes
Cuestionario

Memoria
Cuestionario

Ejercicio estilo "Final", que lo disfuten...
Sea un sistema multitarea con RR y gestión de memoria con segmentación paginada que posee las sig. características: Un total de 8 marcos de pág. de 8kb. c/u – Algoritmo NRU para reemplazo de págs. (swapping) – Tiempo de lect. ó grabación de una pág. En disco=200ns – TAM=50ns – TLB con identif. De proceso con tiempo de búsq. de 10 ns y t. de modif.. de 20 ns. (10ns X 2) – TS (tabla de segmentos) y TP (t.pág.) en memoria principal. En el sig. turno (qantum) del sistema, un proceso (id:8) emite llamadas a las sig. direcc. Lógicas para acceder a parte de sus datos: (0,4078) – (1,18738) y (0,13111) en ese orden. A continuación se muestra la asignación de los 8 marcos al comienzo del turno del proceso 8:

Marco	Seg-pág.	Proc.	R-M
0	0 – 2	8	1 – 1
1	1 – 2	8	0 – 1
2	1 – 0	8	1 - 0
3	------		----
4	1 – 1	8	1 – 1
5	1 – 2	19	1 – 1
6	1 – 0	14	1 – 1
7	0 – 0	19	1 – 1

Se solicita:
a) Direcc. Físicas a las que hace referencia el proceso 8
b) Reescriba la asignación de los marcos luego de finalizado su turno de ejecución
c) Sabiendo que, el turno del proceso 8 fue utilizado un 80% para cumplimentar los accesos a las 3 direcc. lóg. dadas y un 20% a la ejecución de código: Calcular el tiempo del turno (qantum) que otorga el planificador del s.o.

RTA:
a) 0,4078 = dl : (0,0,4078) – df: (3,4078) Asigno el 1er. y único marco libre (asignación ascendente) 1,18738= dl : (1,2,2354) – df : (1,2354) Marco 1 ya asignado a seg:1 – pág:2 0,13111= dl : (0,1,4919) – df : (2,4919) Las menor clase no vacía es la 2 (R=1-M=0), por lo que las págs. a reemplazar pueden ser la asignada al marco 2 ó al 3; pero como la 1ra. es la del marco 2 por orden se reemplaza.

b)

Marco	Seg-pág.	Proc.	R-M
0	0 – 2	8	1 – 1
1	1 – 2	8	1 – 1
2	0 – 1	8	1 - 0
3	0 – 0	8	1 – 0
4	1 – 1	8	1 – 1
5	1 – 2	19	1 – 1
6	1 – 0	14	1 – 1
7	0 – 0	19	1 – 1

c) Accesos: 1ra. dl.: 10 (búsq. TLB) + 50 (TS) + 50 (TP) + 200 (Swap. de lect.) + 50 (TAM) + 10 (modif. TLB) = 370 ns.
2da. dl: 10 (búsq. TLB) + 50 (TAM) = 60 ns.
3ra. dl.: 10 (búsq. TLB) + 50 (TS) + 50 (TP) + 200 (Swap. de lect.) + 50 (TAM) + 10 (modif. TLB) = 370 ns. (**)

80% = 800 ns y 20% = (800x20) / 80 : 200 ns (ejec. de código) entonces: Total del Qantum: 1000 ns

(**): Si la pág. a reemplazar en el marco 2 hubiera tenido el bit M(modification) en 1 habría que sumar 200 ns más para la grabación en disco de la pág. en cuestión y recién después leer la nueva de disco.

Memoria Virtual

EzequielQ22 — Fri, 20 Jun 2008 20:01:00 CDT

INTRODUCCION Y DEFINICION:

Es una técnica de gerencia de memoria, usada por un sistema operativo, donde memoria no contigua es presentada al software como memoria contigua. Esta memoria contigua es llamada VAS (virtual address space) o espacio de dirección virtual.

En términos técnicos, la memoria virtual permite a un software correr en un espacio de memoria que no necesariamente pertenece a la memoria física de una computadora. Para esto se debe emular un CPU que trate a toda la memoria (virtual y principal) como un bloque igual, y determinar cuándo se requiere de una memoria u otra.

Los programas corriendo en una computadora utilizan esta memoria como si se tratase de completamente de la memoria RAM. La memoria virtual se utiliza cuando la memoria principal (RAM) no alcanza, utilizando espacio en disco duro para extenderla. Generalmente el archivo utilizado para guardar la memoria virtual es llamado "archivo de paginación".

Fragmentacion, Paginacion y Segmentacion:

Los métodos de administración de la memoria principal, que no utilizan Memoria Virtual y esquemas de Paginación y Segmentación, es decir que llevan a las direcciones directamente al bus de la memoria, tienen un inconveniente: producen lo que se denomina fragmentación. La fragmentación, que son huecos en la memoria que no pueden usarse debido a lo pequeño de su espacio, provoca un desperdicio de memoria principal. Una posible solución para la fragmentación externa es permitir que espacio de direcciones lógicas lleve a cabo un proceso en direcciones no contiguas, así permitiendo al proceso ubicarse en cualquier espacio de memoria física que esté disponible, aunque esté dividida. Una forma de implementar esta solución es a través del uso de un esquema de paginación. La paginación evita el considerable problema de ajustar los pedazos de memoria de tamaños variables que han sufrido los esquemas de manejo de memoria anteriores. Dado a sus ventajas sobre los métodos previos, la paginación, en sus diversas formas, es usada en muchos sistemas operativos. Al utilizar la memoria virtual, las direcciones no pasan en forma directa al bus de memoria, sino que van a una unidad administradora de la memoria (MMU –Memory Management Unit). Estas direcciones generadas por los programas se llaman direcciones virtuales y conforman el hueco de direcciones virtuales. Este hueco se divide en unidades llamadas páginas. Las unidades correspondientes en la memoria física se llaman marcos para página o frames. Las páginas y los marcos tienen siempre el mismo tamaño. Comparando la paginación y segmentación simple por un lado, con la partición estática y dinámica por el otro, se establecen las bases para un avance fundamental en la gestión de memoria, y es que: Se puede cargar y descargar un proceso de la memoria principal de tal forma que ocupe regiones diferentes de la memoria principal en momentos distintos a lo largo de su ejecución. Un proceso puede dividirse en varias partes (páginas o segmentos) y no es necesario que estas partes se encuentren contiguas en la memoria principal. Si estas dos características están presentes, no será necesario que todas las páginas o todos los segmentos de un proceso estén en la memoria durante la ejecución. El término fragmento hace referencia tanto a páginas como a segmentos, dependiendo de si se emplea paginación o segmentación. Supóngase que se trae un proceso a la memoria en un momento dado, el S.O comienza trayendo sólo unos pocos fragmentos, incluido el fragmento que contiene el comienzo del programa. Se llamará conjunto residente del proceso a la parte que está realmente en la memoria principal. Si el procesador encuentra una dirección lógica que no está en la memoria principal, genera una interrupción que indica un fallo de acceso a la memoria. El S.O pone al proceso interrumpido en estado Bloqueado y toma el control. Para que la ejecución de este proceso siga más tarde, el S.O necesita traer a la memoria principal el fragmento del proceso que contiene la dirección. Para ello se emite una solicitud de Lectura de E/S al disco; luego se expide otro proceso para que se ejecute mientras se realiza la operación. Una vez que el fragmento deseado se ha traído a la memoria principal y se ha emitido la interrupción de E/S, se devuelve el control al S.O, que coloca el proceso afectado en el estado de Listo.
La ilusión de la memoria virtual está soportada por el mecanismo de traducción de memoria, junto con una gran cantidad de almacenamiento rápido en disco duro. Así en cualquier momento el espacio de direcciones virtual hace un seguimiento de tal forma que una pequeña parte de él, está en memoria real y el resto almacenado en el disco, y puede ser referenciado fácilmente.

Debido a que sólo la parte de memoria virtual que está almacenada en la memoria principal, es accesible a la CPU, según un programa va ejecutándose, la proximidad de referencias a memoria cambia, necesitando que algunas partes de la memoria virtual se traigan a la memoria principal desde el disco, mientras que otras ya ejecutadas, se pueden volver a depositar en el disco (archivos de paginación). La memoria virtual ha llegado a ser un componente esencial de la mayoría de los S.O actuales. Y como en un instante dado, en la memoria sólo se tienen unos pocos fragmentos de un proceso dado, se pueden mantener más procesos en la memoria. Es más, se ahorra tiempo, porque los fragmentos que no se usan no se cargan ni se descargan de la memoria. Sin embargo, el S.O debe saber cómo gestionar este esquema. La memoria virtual también simplifica la carga del programa para su ejecución llamado reubicación, este procedimiento permite que el mismo programa se ejecute en cualquier posición de la memoria física. En un estado estable, prácticamente toda la memoria principal estará ocupada con fragmentos de procesos, por lo que el procesador y el S.O tendrán acceso directo a la mayor cantidad de procesos posibles, y cuando el S.O traiga a la memoria un fragmento, deberá expulsar otro. Si expulsa un fragmento justo antes de ser usado, tendrá que traer de nuevo el fragmento de manera casi inmediata. Demasiados intercambios de fragmentos conducen a lo que se conoce como hiperpaginación: donde el procesador consume más tiempo intercambiando fragmentos que ejecutando instrucciones de usuario. Para evitarlo el S.O intenta adivinar, en función de la historia reciente, qué fragmentos se usarán con menor probabilidad en un futuro próximo. Los argumentos anteriores se basan en el principio de cercanía o principio de localidad que afirma que las referencias a los datos y el programa dentro de un proceso tienden a agruparse. Por lo tanto, es válida la suposición de que, durante cortos períodos de tiempo, se necesitarán sólo unos pocos fragmentos de un proceso. Una manera de confirmar el principio de cercanía es considerar el rendimiento de un proceso en un entorno de memoria virtual. El principio de cercanía sugiere que los esquemas de memoria virtual pueden funcionar. Para que la memoria virtual sea práctica y efectiva, se necesitan dos ingredientes. Primero, tiene que existir un soporte de hardware y, en segundo lugar, el S.O debe incluir un software para gestionar el movimiento de páginas o segmentos entre memoria secundaria y memoria principal. Justo después de obtener la dirección física y antes de consultar el dato en memoria principal se busca en memoria-cache, si esta entre los datos recientemente usados la búsqueda tendrá éxito, pero si falla, la memoria virtual consulta memoria principal , ó, en el peor de los casos se consulta de disco (swapping). Memoria Virtual = Memoria Física + Area de Swapping en Disco

PAGINACION

El término memoria virtual se asocia normalmente con sistemas que emplean paginación, aunque también se puede usar memoria virtual basada en la segmentación. El uso de la paginación en la memoria virtual fue presentado por primera vez en el computador Atlas. Cada proceso tiene su propia tabla de páginas y cuando carga todas sus páginas en la memoria principal, se crea y carga en la memoria principal una tabla de páginas. Cada entrada de la tabla de páginas contiene el número de marco de la página correspondiente en la memoria principal. Puesto que sólo algunas de las páginas de un proceso pueden estar en la memoria principal, se necesita un bit en cada entrada de la tabla para indicar si la página correspondiente está presente (P) en la memoria principal o no. Si el bit indica que la página está en la memoria, la entrada incluye también el número de marco para esa página. Otro bit de control necesario en la entrada de la tabla de páginas es el bit de modificación (M), para indicar si el contenido de la página correspondiente se ha alterado desde que la página se cargó en la memoria principal. Si no ha habido cambios, no es necesario escribir la página cuando sea sustituida en el marco que ocupa actualmente. Estructura de la tabla de páginas El mecanismo básico de lectura de una palabra de la memoria supone la traducción por medio de la tabla de páginas de una dirección virtual o lógica, formada por un número de página y un desplazamiento, a una dirección física que está formada por un número de marco y un desplazamiento. Con la memoria virtual, la CPU produce direcciones virtuales que son traducidas por una combinación de hardware y software a direcciones físicas, pues pueden ser utilizadas para acceder a memoria principal. Este proceso se denomina correspondencia de memoria o traducción de direcciones. Actualmente los dos niveles de la jerarquía de memoria controlados por la memoria virtual son las DRAM y los Discos magnéticos. Puesto que la tabla de páginas es de longitud variable, en función del tamaño del proceso, no es posible suponer que quepa en los registros. La figura anterior sugiere una implementación en hardware de este esquema. Cuando se está ejecutando un proceso en particular, la dirección de comienzo de la tabla de páginas para este proceso se mantiene en un registro. El número de página de la dirección virtual se emplea como índice en esta tabla para buscar el número de marco correspondiente. Este se combina con la parte de desplazamiento de la dirección virtual para generar la dirección real deseada. La mayoría de los esquemas de memoria virtual almacenan las tablas de páginas en la memoria virtual en vez de en la memoria real. Esto significa que estas tablas de páginas están también sujetas a paginación, de la misma forma que las otras páginas. Cuando un proceso se está ejecutando, al menos una parte de su tabla de páginas debe estar en la memoria principal, incluyendo la entrada de la tabla de páginas para la página actualmente en ejecución. Algunos procesadores usan un esquema de dos niveles para organizar grandes tablas de páginas, donde hay un directorio de páginas en el que cada entrada señala a una tabla de páginas. Así pues, si la longitud del directorio de páginas es X, y la longitud máxima de una tabla de páginas es Y, un proceso puede estar formado por hasta X x Y páginas. Normalmente, la longitud máxima de una tabla de páginas está limitada a una página. Por ejemplo, el procesador Pentium utiliza este método. Un enfoque alternativo al uso de tablas de páginas de uno o dos niveles es el uso de una estructura de tabla de páginas invertida. Con este método, la parte del número de página de una dirección virtual se traduce a una tabla de dispersión por medio de una función de dispersión simple. La tabla de dispersión contiene un puntero a la tabla de páginas invertida, que contiene a su vez las entradas de la tabla de páginas. Con esta estructura, hay una entrada en la tabla de dispersión y en la tabla de páginas invertida por cada página de memoria real en lugar de una por cada página virtual. Así pues, se necesita una parte fija de la memoria real para las tablas, sin reparar en el número de procesos o de páginas virtuales soportados. La técnica de dispersión genera normalmente cadenas cortas, de dos a tres entradas cada una. Buffer de traducción adelantada Cada referencia a la memoria virtual puede generar dos accesos a la memoria: uno para obtener la entrada de la tabla de páginas correspondientes y otro para obtener el dato deseado. Un esquema sencillo de memoria virtual podría tener el efecto de doblar el tiempo de acceso a la memoria. Para solucionar este problema, la mayoría de los esquemas de memoria virtual hacen uso de una cache especial para las entradas de la tabla de páginas, llamada generalmente buffer de traducción adelantada (TLB,Translation Lookaside Buffer) que contiene aquellas entradas de la tabla de páginas usadas hace menos tiempo. La organización de hardware de paginación resultante se muestra en la figura siguiente.

Tabla de Páginas

K.Ivan — Fri, 13 Jun 2008 19:43:41 CDT

Estructura de la tabla de páginas

El mecanismo básico de lectura de una palabra de la memoria supone la traducción por medio de la tabla de páginas de una dirección virtual o lógica, formada por un número de página y un desplazamiento, a una dirección física que está formada por un número de marco y un desplazamiento.
Con la memoria virtual, la CPU produce direcciones virtuales que son traducidas por una combinación de hardware y software a direcciones físicas, pues pueden ser utilizadas para acceder a memoria principal. Este proceso se denomina correspondencia de memoria o traducción de direcciones. Actualmente los dos niveles de la jerarquía de memoria controlados por la memoria virtual son las DRAM y los Discos magnéticos. Puesto que la tabla de páginas es de longitud variable, en función del tamaño del proceso, no es posible suponer que quepa en los registros.

La figura anterior sugiere una implementación en hardware de este esquema. Cuando se está ejecutando un proceso en particular, la dirección de comienzo de la tabla de páginas para este proceso se mantiene en un registro. El número de página de la dirección virtual se emplea como índice en esta tabla para buscar el número de marco correspondiente. Este se combina con la parte de desplazamiento de la dirección virtual para generar la dirección real deseada.

La mayoría de los esquemas de memoria virtual almacenan las tablas de páginas en la memoria virtual en vez de en la memoria real. Esto significa que estas tablas de páginas están también sujetas a paginación, de la misma forma que las otras páginas.

Cuando un proceso se está ejecutando, al menos una parte de su tabla de páginas debe estar en la memoria principal, incluyendo la entrada de la tabla de páginas para la página actualmente en ejecución. Algunos procesadores usan un esquema de dos niveles para organizar grandes tablas de páginas, donde hay un directorio de páginas en el que cada entrada señala a una tabla de páginas. Así pues, si la longitud del directorio de páginas es X, y la longitud máxima de una tabla de páginas es Y, un proceso puede estar formado por hasta X x Y páginas. Normalmente, la longitud máxima de una tabla de páginas está limitada a una página. Por ejemplo, el procesador Pentium utiliza este método.

Un enfoque alternativo al uso de tablas de páginas de uno o dos niveles es el uso de una estructura de tabla de páginas invertida. Con este método, la parte del número de página de una dirección virtual se traduce a una tabla de dispersión por medio de una función de dispersión simple. La tabla de dispersión contiene un puntero a la tabla de páginas invertida, que contiene a su vez las entradas de la tabla de páginas. Con esta estructura, hay una entrada en la tabla de dispersión y en la tabla de páginas invertida por cada página de memoria real en lugar de una por cada página virtual. Así pues, se necesita una parte fija de la memoria real para las tablas, sin reparar en el número de procesos o de páginas virtuales soportados. La técnica de dispersión genera normalmente cadenas cortas, de dos a tres entradas cada una.

TLB

K.Ivan — Fri, 13 Jun 2008 19:34:03 CDT

Buffer de traducción adelantada

Cada referencia a la memoria virtual puede generar dos accesos a la memoria: uno para obtener la entrada de la tabla de páginas correspondientes y otro para obtener el dato deseado.

Un esquema sencillo de memoria virtual podría tener el efecto de doblar el tiempo de acceso a la memoria. Para solucionar este problema, la mayoría de los esquemas de memoria virtual hacen uso de una cache especial para las entradas de la tabla de páginas, llamada generalmente buffer de traducción adelantada (TLB,Translation Lookaside Buffer) que contiene aquellas entradas de la tabla de páginas usadas hace menos tiempo.
La organización de hardware de paginación resultante se muestra en la figura siguiente:

Dada una dirección virtual, el procesador examinará primero la TLB. Si la entrada de la tabla de páginas buscada está presente se obtiene el número de marco y se forma la dirección real. Si no se encuentra, el procesador emplea el número de página como índice para buscar en la tabla de páginas del proceso y examinar la entrada correspondiente de la tabla de páginas. Si no se encuentra activo el bit de presencia, es que la página está en la memoria principal y el procesador puede obtener el número de marco de la entrada de la tabla de páginas para formar la dirección real. El procesador, además, actualiza la TLB para incluir esta nueva entrada de la tabla de páginas. Si el bit de presencia no está activo, es que la página buscada no está en la memoria principal y se produce un fallo en el acceso a la memoria, llamado fallo de página.

Existe una serie de detalles adicionales sobre la organización real de la TLB. Puesto que la TLB contiene sólo algunas de las entradas de la tabla de páginas completa, no se puede indexar simplemente la TLB por el número de páginas. Cada entrada debe incluir el número de página, además de la entrada completa a la tabla de páginas. El procesador estará equipado con un hardware que permita consultar simultáneamente varias entradas de la TLB para determinar si hay coincidencia en el número de página. Esta técnica se denomina correspondencia asociativa y contrasta con la correspondencia directa, que se emplea para buscar en la tabla de páginas de la figura de Búsqueda directa y asociativa. El diseñador de la TLB también debe considerar la forma en que se organiza las entradas en la TLB y que entrada reemplazar cuando se introduce una nueva.

Asignaciòn de Trabajos a Escritores

jercoli — Fri, 13 Jun 2008 18:26:55 CDT

(1 al 3 asignados el 1/4/08 - 4 al 7 asignados el 8/4/08 - 8 al 10 asig. el 11/4/08)
(11 al 16 asig. el 15/5/08) - (17 al 22 asig. el 13/6/08)

Conceptos Básicos (shadowsroy + stroppiana)
Clasificación de SO (fedeta86+lucho_86)
Generaciones de SO-Historia (deny88+matcarfer)
Procesos-Estados y mod. de 3 y 5 estados (Juan_Azar+daminablanc)
Procesos-Reg.Proc.Unix (mtesoriero+vzannoni)
Procesos-BCP, cambios modo y contexto, int. (ello_utn+martinorengia)
Procesos-Planif.Proc.-obj. y niveles+Aprop. y No aprop. (ggimenez+jcarnero)
Procesos-Planif.Proc.-FCFS y SJF (acodesal+bjona)
Procesos-Planif.Proc.-Prioridades dinàm. y estàticas (henieto+rcampagna)
Procesos-Planif.Proc.-Round Robin ò Circular (alejandroml+eze_elmac)
Modelo de Hilos (mlucchelli + german_machado)
Concurrencia-Comunicaciòn de proc.+Sincronizaciòn (mfernandez + Eldaviddd)
Concurrencia-Exclus. Mutua (ale_levy + FCastellanos)
Concurrencia-Soluc.Soft y Hard (mimarquez + leandroRomero)
Concurrencia-Soluc.SO -Semàforos (EFiorello + harroyo)
Concurrencia-Soluc.SO-Mensajes (erosani+MatiasAmas)
Memoria-Asig.Contigua-Partic. Fijas (jGiordano)
Memoria-Asig.Contigua-Partic. Variables (MIBarreyra)
Memoria-Asig.no Cont.-Memoria Virtual (EzequielQ22)
Memoria-Asig.no Cont.-Paginaciòn-T.Pàginas+TLB (jretamozo + K.Ivan)
Memoria-Asig.no Cont.-Paginaciòn-Estrat. obtenciòn y reemplazo (SSancho + hPais)
Memoria-Asig.no Cont.-Paginaciòn MultiNivel (G_Scognamillo)

Concurrencia - Soluciones Soft y Hard

jercoli — Wed, 28 May 2008 20:09:31 CDT

SOLUCIONES POR SOFTWARE
Pueden implementarse soluciones de software para los procesos concurrentes que se ejecuten en máquinas monoprocesador o multiprocesador con memoria principal compartida.

ALGORITMO DE DEKKER
La solución se desarrolla por etapas. Este método ilustra la mayoría de los errores habituales que se producen en la construcción de programas concurrentes.

Primer intento
Cualquier intento de exclusión mutua debe depender de algunos mecanismos básicos de exclusión en el hardware. El más habitual es que sólo se puede acceder a una posición de memoria en cada instante, teniendo en cuenta esto se reserva una posición de memoria global llamada turno. Un proceso que desea ejecutar su sección crítica primero evalúa el contenido de turno. Si el valor de turno es igual al número del proceso, el proceso puede continuar con su sección crítica. En otro caso el proceso debe esperar. El proceso en espera, lee repetitivamente el valor de turno hasta que puede entrar en su sección crítica. Este procedimiento se llama espera activa.
Después de que un proceso accede a su sección crítica y termina con ella, debe actualizar el valor de turno para el otro proceso.

Segundo intento:
Cada proceso debe tener su propia llave de la sección crítica para que, si uno de ellos falla, pueda seguir accediendo a su sección crítica; para esto se define un vector booleano señal. Cada proceso puede evaluar el valor de señal del otro, pero no modificarlo. Cuando un proceso desea entrar en su sección crítica, comprueba la variable señal del otro hasta que tiene el valor falso (indica que el otro proceso no está en su sección crítica). Asigna a su propia señal el valor cierto y entra en su sección crítica. Cuando deja su sección crítica asigna falso a su señal.
Si uno de los procesos falla fuera de la sección crítica, incluso el código para dar valor a las variables señal, el otro proceso no se queda bloqueado. El otro proceso puede entrar en su sección crítica tantas veces como quiera, porque la variable señal del otro proceso está siempre en falso. Pero si un proceso falla en su sección crítica o después de haber asignado cierto a su señal, el otro proceso estará bloqueado permanentemente.

Tercer intento
El segundo intento falla porque un proceso puede cambiar su estado después de que el otro proceso lo ha comprobado pero antes de que pueda entrar en su sección crítica.
Si un proceso falla dentro de su sección crítica, incluso el código que da valor a la variable señal que controla el acceso a la sección crítica, el otro proceso se bloquea y si un proceso falla fuera de su sección crítica, el otro proceso no se bloquea.
Si ambos procesos ponen sus variables señal a cierto antes de que ambos hayan ejecutado una sentencia, cada uno pensará que el otro ha entrado en su sección crítica, generando así un interbloqueo.

Cuarto intento
En el tercer intento, un proceso fijaba su estado sin conocer el estado del otro. Se puede arreglar esto haciendo que los procesos activen su señal para indicar que desean entrar en la sección crítica pero deben estar listos para desactivar la variable señal y ceder la preferencia al otro proceso.
Existe una situación llamada bloqueo vital, esto no es un interbloqueo, porque cualquier cambio en la velocidad relativa de los procesos rompería este ciclo y permitiría a uno entrar en la sección crítica. Recordando que el interbloqueo se produce cuando un conjunto de procesos desean entrar en sus secciones críticas, pero ninguno lo consigue. Con el bloqueo vital hay posibles secuencias de ejecución con éxito.

Una solución correcta
Hay que observar el estado de ambos procesos, que está dado por la variable señal, pero es necesario imponer orden en la actividad de los procesos para evitar el problema de "cortesía mutua". La variable turno del primer intento puede usarse en esta labor, indicando que proceso tiene prioridad para exigir la entrada a su sección crítica.

ALGORITMO DE PETERSON
El algoritmo de Deker resuelve el problema de la exclusión mutua pero mediante un programa complejo, difícil de seguir y cuya corrección es difícil de demostrar. Peterson ha desarrollado una solución simple y elegante. Como antes, la variable global señal indica la posición de cada proceso con respecto a la exclusión mutua y la variable global turno resuelve los conflictos de simultaneidad.
Considérese el proceso P0. Una vez que ha puesto señal[0] a cierto, P1 no puede entrar en su sección crítica. Si P1 esta aun en su sección crítica, entonces señal[1] = cierto y P0 está bloqueado en su bucle while. Esto significa que señal[1] es cierto y turno = 1. P0 puede entrar en su sección crítica cuando señal[1] se ponga a falso o cuando turno se ponga a 0. Considérense ahora los siguientes casos exhaustivos:

P1 no está interesado en entrar en su sección crítica. Este caso es imposible porque implica que señal[1] = falso.
P1 está esperando entrar en su sección crítica. Este caso es también imposible porque si turno = 1, P1 podría entrar en su sección crítica.
P1 entra en su sección crítica varias veces y monopoliza el acceso a ella. Esto no puede pasar porque P1 está obligado a dar a P0 una oportunidad poniendo turno a 0 antes de cada intento de entrar en su sección crítica.

Así pues, se tiene una solución posible al problema de la exclusión mutua para dos procesos. Es más, el algoritmo de Peterson se puede generalizar fácilmente al caso de n procesos.

ALGORITMOS DE DEKKER Y PETERSON
Combinando las filosofías de la primera y segunda aproximaciones, Dekker propuso un algoritmo que garantiza la exclusión mutua sin interbloqueo ni inanición.
Peterson, con los mismos criterios, desarrolló un algoritmo más compacto que el de Dekker, que garantiza lo mismo. Este algoritmo se muestra a continuación, para dos hilos.
turno: entero en el rango 0..1 con valor inicial cualquiera
interesado: arreglo de dos posiciones booleanas, ambas con valor inicial FALSE

*Hilo 0*	*Hilo 1*
yo = 0 ;	yo = 1 ;
(sección no crítica)	(sección no crítica)
otro = 1 – yo ;	otro = 1 – yo ;
interesado[yo] = TRUE ;	interesado[yo] = TRUE ;
turno = yo ;	turno = yo ;
while	while
(turno= =yo && interesado[otro]= =TRUE ) ;	(turno= =yo && interesado[otro]= =TRUE ) ;
(sección crítica)	(sección crítica)
interesado[yo] = FALSE ;	interesado[yo] = FALSE ;

Existen los algoritmos de Dekker y Peterson para N hilos, donde N toma cualquier valor arbitrario mayor que 2.

ESPERA ACTIVA
Si bien es cierto que con los algoritmos de Dekker y Peterson se consigue la exclusión mutua entre hilos también es cierto que estos algoritmos conllevan una espera activa de los mismos; es decir, cuando un hilo está intentando el acceso a un recurso que ya ha sido asignado a otro, continúa consumiendo tiempo de procesador en su intento de conseguir el recurso.
La espera activa está implementada en las figuras anteriores mediante la construcción
while (condición) ;
donde, al estar vacío el ciclo del while, se continúa evaluando la condición hasta que ella cambie.
FUENTE: http://bochica.udea.edu.co/~cnorena/guia-estudio/exclu-mutua.html#TURNOS_Y_OTROS

SOLUCIONES POR HARDWARE
INHABILITACIÓN (enmascaramiento) DE INTERRUPCIONES
En una máquina monoprocesador, la ejecución de procesos concurrentes no puede superponerse; los procesos solo pueden intercalarse. Es más, un proceso continuará ejecutándose hasta que solicite un servicio el sistema operativo o hasta que sea interrumpido. Por lo tanto, para garantizar la exclusión mutua, es suficiente con impedir que un proceso sea interrumpido. Esta capacidad puede ofrecerse en forma de primitivas definidas por el núcleo del sistema para habilitar o inhabilitar las interrupciones. Un proceso puede hacer cumplir la exclusión mutua del siguiente modo:
While (cierto)
{
/*inhabilitar interrupciones */;
/* sección critica */;
/* habilitar interrupciones */;
/* resto */;
}
Puesto que la sección crítica no puede ser interrumpida, la exclusión mutua está garantizada. Sin embargo, el precio de esta solución es alto. La eficiencia de la ejecución puede verse notablemente degradada debido a que se limita la capacidad del procesador para intercalar programas. Un segundo problema es que está técnica no funciona en arquitecturas de multiprocesador. Cuando el sistema tenga más de un procesador, es posible (y habitual) que haya más de un proceso ejecutándose al mismo tiempo. En este caso, inhabilitar las interrupciones no garantiza la exclusión mutua.

INSTRUCCIONES ESPECIALES DE MAQUINA
En configuraciones multiprocesador, varios procesadores comparten el acceso a una memoria principal común. En este caso, no hay relación maestro/esclavo, sino que los procesadores funcionan independientemente en una relación de igualdad. No hay un mecanismo de interrupciones entre los procesadores en el que se pueda basar la exclusión mutua.
A nivel de hardware, como se ha mencionado, los accesos a posiciones de memoria excluyen cualquier otro acceso a la misma posición. Con esta base, los diseñadores han propuesto varias instrucciones de máquina que realizan dos acciones atómicamente, tales cono leer y escribir o leer y examinar, sobre una misma posición de memoria en un único ciclo de lectura de instrucción.
Puesto que estas acciones se realizan en un único ciclo de instrucción, no están sujetas a injerencias por parte de otras instrucciones.

La instrucción COMPARAR Y FIJAR (TAS, Test and Set) puede definirse de la siguiente forma:

booleano TS(int i)
{
if (I==0)
{
I=1;
return cierto;
}
else
{
return falso;
}
}

La instrucción examina el valor de su argumento i. Si el valor es 0 , lo cambia por 1 y devuelve cierto. En otro caso, el valor no se modifica y se devuelve falso. La función Comparar y Fijar se ejecuta atómicamente en su totalidad, es decir, no esta sujeta a interrupciones.

La instrucción INTERCAMBIAR (Swap) se puede definir como sigue:

void intercambiar (int registro, int memoria)
{
int temp;
temp = memoria;
memoria = registro;
registro = temp;
}

Esta instrucción intercambia el contenido de un registro con el de una posición de memoria. Durante la ejecución de la instrucción, se bloquea el acceso a la posición de memoria de cualquier otra instrucción que haga referencia a la misma posición.

Propiedades de las soluciones con instrucciones de maquina
El uso de instrucciones especiales de la maquina para hacer cumplir la exclusión mutua tiene varias ventajas:

Es aplicable a cualquier número de procesos en sistemas con memoria compartida, tanto de monoprocesador como de multiprocesador.
Es simple y fácil de verificar.
Puede usarse para disponer de varias secciones críticas; cada sección crítica puede definirse con su propia variable.

Algunas desventajas importantes son las siguientes:

SE EMPLEA ESPERA ACTIVA. Así pues, mientras un proceso está esperando para acceder a la sección crítica, continúa consumiendo tiempo del procesador.
PUEDE PRODUCIRSE INANICIÓN. Cuando un proceso abandona la sección crítica y hay más de un proceso esperando, la selección es arbitraria. Así pues se podría denegar el acceso a algún proceso indefinidamente.
PUEDE PRODUCIRSE INTERBLOQUEO. Supóngase la siguiente escena en un sistema monoprocesador. El proceso "P1" ejecuta una instrucción especial (sea TS o Intercambiar) y entra su sección crítica. Se interrumpe a "P1" para dar el procesador a "P2", que tiene mayor prioridad. Si "P2" intenta ahora usar el mismo recurso que "P1", se le negará el acceso por el mecanismo de exclusión mutua. De este modo, "P2" entrará en un bucle de espera activa. Sin embargo, "P1" nunca será expedido porque su prioridad es menor que la del proceso listo "p2".

FUENTE: http://bochica.udea.edu.co/~cnorena/guia-estudio/herramientas-hardware.html

Concurrencia - Exclusiòn Mutua

jercoli — Wed, 28 May 2008 19:56:47 CDT

PRINCIPIOS GENERALES DE LA CONCURRENCIA
En un sistema multiprogramado con un único procesador, los procesos se intercalan en el tiempo aparentando una ejecución simultánea. Aunque no se logra un procesamiento paralelo y produce una sobrecarga en los intercambios de procesos, la ejecución intercalada produce beneficios en la eficiencia del procesamiento y en la estructuración de los programas.
La intercalación y la superposición pueden contemplarse como ejemplos de procesamiento concurrente en un sistema monoprocesador, los problemas son consecuencia de la velocidad de ejecución de los procesos que no pueden predecirse y depende de las actividades de otros procesos, de la forma en que el sistema operativo trata las interrupciones surgen las siguientes dificultades:

Compartir recursos globales es riesgoso
Para el sistema operativo es difícil gestionar la asignación óptima de recursos.

Las dificultades anteriores también se presentan en los sistemas multiprocesador.
El hecho de compartir recursos ocasiona problemas, por esto es necesario proteger a dichos recursos.
Los problemas de concurrencia se producen incluso cuando hay un único procesado

LABORES DEL SISTEMA OPERATIVO
Elementos de gestión y diseño que surgen por causa de la concurrencia:
1) El sistema operativo debe seguir a los distintos procesos activos
2) El sistema operativo debe asignar y retirar los distintos recursos a cada proceso activo, entre estos se incluyen:
_Tiempo de procesador
_Memoria
_Archivos
_Dispositivos de E/S
3) El sistema operativo debe proteger los datos y los recursos físicos de cada proceso contra injerencias no intencionadas de otros procesos.
4) Los resultados de un proceso deben ser independientes de la velocidad a la que se realiza la ejecución de otros procesos concurrentes.
Para abordar la independencia de la velocidad debemos ver las formas en las que los procesos interactúan.

INTERACCIÓN ENTRE PROCESOS
Se los puede clasificar en que interactúan los procesos en función del nivel de conocimiento que cada proceso tiene de la existencia de los demás. Existen tres niveles de conocimiento:
1) Los procesos no tienen conocimiento de los demás: son procesos independientes que no operan juntos. Ej: la multiprogramación de procesos independientes. Aunque los procesos no trabajen juntos, el sistema operativo se encarga de la "competencia" por los recursos.
2) Los procesos tienen un conocimiento indirecto de los otros: los procesos no conocen a los otros por sus identificadores de proceso, pero muestran cooperación el objeto común.
3) Los procesos tienen conocimiento directo de los otros: los procesos se comunican por el identificador de proceso y pueden trabajar conjuntamente.

Competencia entre procesos por los recursos
Los procesos concurrentes entran en conflicto cuando compiten por el uso del mismo recurso; dos o más procesos necesitan acceder a un recurso durante su ejecución .Cada proceso debe dejar tal y como esté el estado del recurso que utilice.
La ejecución de un proceso puede influir en el comportamiento de los procesos que compiten. Por Ej. Si dos procesos desean acceder a un recurso, el sistema operativo le asignará el recurso a uno y el otro tendrá que esperar.
Cuando hay procesos en competencia, se deben solucionar tres problemas de control: la necesidad de exclusión mutua. Suponiendo que dos procesos quieren acceder a un recurso no compartible. A estos recursos se les llama "recursos críticos" y la parte del programa que los utiliza es la "sección crítica” del programa. Es importante que sólo un programa pueda acceder a su sección crítica en un momento dado.
Hacer que se cumpla la exclusión mutua provoca un interbloqueo.
Otro problema es la inanición si tres procesos necesitan acceder a un recurso, P1 posee al recurso, luego lo abandona y le concede el acceso al siguiente proceso P2, P1 solicita acceso de nuevo y el sistema operativo concede el acceso a P1 Y P2 alternativamente, se puede negar indefinidamente a P3 el acceso al recurso.
El control de competencia involucra al sistema operativo, porque es el que asigna los recursos.

Cooperación entre procesos por compartimiento

Comprende los procesos que interactúan con otros sin tener conocimiento explícito de ellos. Ej. : Varios procesos pueden tener acceso a variables compartidas.
Los procesos deben cooperar para asegurar que los datos que se comparten se gestionan correctamente. Los mecanismos de control deben garantizar la integridad de los datos compartidos.

Cooperación entre procesos por comunicación

Los distintos procesos participan en una labor común que une a todos los procesos.
La comunicación sincroniza o coordina las distintas actividades, está formada por mensajes de algún tipo. Las primitivas para enviar y recibir mensajes, vienen dadas como parte del lenguaje de programación o por el núcleo del sistema operativo

REQUISITOS PARA LA EXCLUSIÓN MUTUA

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.
Un proceso que se interrumpe en una sección no crítica debe hacerlo sin interferir con los otros procesos.
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.
Si ningún proceso está en su sección crítica, cualquier proceso que solicite entrar en la suya debe poder hacerlo sin demora.
No se debe suponer sobre la velocidad relativa de los procesos o el número de procesadores.
Un proceso permanece en su sección crítica por un tiempo finito.

Mensajes

MatiasAmas — Sat, 24 May 2008 23:28:41 CDT

Paso de mensajes

El paso de mensajes es una técnica empleada en programación concurrente para aportar sincronización entre procesos y permitir la exclusión mutua, de manera similar a como se hace con los semáforos, monitores, etc. Su principal característica es que no precisa de memoria compartida, por lo que es muy importante en la programación para sistemas distribuidos. Los elementos principales que intervienen en el paso de mensajes son el proceso que envía, el que recibe y el mensaje.

1. Permite el intercambio de información entre procesos.
2. La comunicación entre mensajes necesita de un proceso emisor, de un proceso receptor y la información que debe intercambiarse.
3. Las operaciones básicas son: enviar(destino, mensaje) recibir(origen, mensaje)
4. La comunicación por mensajes requiere que se establezca un enlace entre el receptor y el emisor.
5. Fuerza la exclusión mutua.

Direccionamiento

1. Direccionamiento directo.

Se especifican emisor y receptor de forma explícita.
P envía a Q:
- P: send (Q, mensaje)
- Q: receive (Q, mensaje)

1.1. La operación enviar() incluye una identificación del proceso destino
1.2. La operación recibir() puede incluir la identificación del proceso origen del mensaje. (Procesos cooperantes)
1.3. La operación recibir() también puede no saber cuál es el proceso origen del mensaje (Como un servicio de impresoras, recibirá solicitudes de impresión de cualquier proceso). El parámetro origen se utilizara como respuesta de que el mensaje ha sido recibido.

2. Direccionamiento indirecto.

2.1. Los mensajes no se envían directamente al receptor, sino a una cola para su posterior procesamiento.
2.2. Las colas son llamadas buzones (mail box).
2.3. Los procesos envían mensajes a un buzón y es un proceso quien toma los mensajes del buzón para su procesamiento.

3. Desacoplamiento del direccionamiento indirecto.
Permite flexibilidad en el manejo de mensajes. En este tercer caso la relación puede ser (1-1) (un proceso envía a un solo buzón). También puede haber (n-1) donde varios procesos envían mensajes a un solo buzón o (1-n) donde un proceso envía mensajes a muchos buzones.

3.1. Un emisor y un receptor. Es un enlace privado de comunicación entre dos procesos.
3.2. Muchos emisores y un receptor. Un proceso ofrece un servicio a muchos procesos. En este caso el buzón se llama puerto. (programas cliente / servidor)
3.3. Un emisor y muchos receptores. Un mensaje se difunde a un conjunto de procesos receptores. (Upgrade de programas por internet).
3.4. Muchos emisores y muchos receptores. (envío de e-mails).

Sincronización

1. Emisor con bloqueo y Receptor con bloqueo. Emisor Síncrono
1.1. Ambos, tanto receptor como emisor son bloqueados hasta que el mensaje sea entregado.
1.2. Se llama rendezvous.
1.3. Permite una sincronización fuerte de procesos.
1.4. Ejemplo: Procesos cooperantes.

2. Emisor sin bloqueo y Receptor con bloqueo. Emisor Asíncrono
2.1. El emisor continua su procesamiento, enviando mensajes tan rápido como sea posible.
2.2. El receptor se bloqueo hasta que llegue el mensaje solicitado.
2.3. Es la combinación más útil de sincronización.
2.4. Ejemplo: Connect desde un programa Oracle (cliente) hacia un Listener Oracle (servidor ).

3. Emisor sin bloqueo y Receptor sin bloqueo.
3.1. Nadie debe esperar.
3.2. Ejemplo: El MS-Word continua su proceso mientras el servicio de impresión de diversos procesos continúan.

Partes de un mensaje
1. Cabecera
1.1. Tipo de mensaje
1.2. Proceso Destino (buzón, puerto)
1.3. Proceso Origen (cliente)
1.4. Longitud del mensaje
1.5. Información de control (prioridad, siguiente mensaje, contador de secuencia)
2. Cuerpo

Exclusión Mutua
1. Envío sin bloqueo, Recepción con bloqueo
2. Un conjunto de procesos comparten un buzón llamado mutex.
3. El buzón al inicio contiene un mensaje de contenido arbitrario.
4. Un proceso que desea usar la sección crítica, recibe ese mensaje (quitándose del buzón)
5. Puesto que la recepción es con bloqueo, ningún otro proceso podrá ingresar a la sección crítica (Ya que no existe mensajes en el buzón).
6. Una vez que ha usado la sección crítica, devuelve el mensaje al buzón.
7. Así el mensaje sirve como posta entre un mensaje y otro para usar la sección crítica.

/* programa exclusion mutua*/
const int n = /*numero procesos*/
void P(int i)
{
message msg;
while (true)
{
recibir(mutex,msg);
/*seccion critica*/
enviar(mutex,msg);
/*el resto de codigo*/
}
}
void main()
{
crear_mailbox(mutex);
enviar(mutex,null);
parbegin(P(1),P(2) ... P(n));
}

Concurrencia

jercoli — Thu, 15 May 2008 14:11:43 CDT

Comunicaciòn de Procesos

Sincronizaciòn de Procesos

Programaciòn Concurrente
Exclusiòn mutua

Soluciones software
Soluciones hardware

Soluciones del SO:

Semàforos
Mensajes

FCFS y SJF

acodesal — Thu, 08 May 2008 00:05:56 CDT

FCFS (First Come, First Served)

La política más simple de planificación es la FCFS. A medida que un proceso pasa al estado listo, este es agregado a la cola de listos. Cuando el proceso que actualmente está ejecutando cesa su ejecución entonces el proceso más viejo en la cola es seleccionado para correr. La implementación de esta política es a través de colas FIFO (First-In, First-Out). Cuando el CPU está libre, éste es asignado al proceso que está en la cabeza de la cola. FCFS es un algoritmo nonpreemptive ó "no apropiativo", pues una vez que el CPU es asignado a un proceso, este lo mantiene hasta que espontáneamente lo suelta, ya sea porque el proceso finalizó o por algún requerimiento de E/S. El tiempo de espera bajo esta política tiende a ser alto. Además , tiende a favorecer aquellos procesos que requieren más tiempo de CPU (CPU-bound). Consideren el caso donde tenemos una colección de procesos. Uno de ellos utiliza más CPU que los otros, y el resto de los procesos requieren más trabajo de E/S (I/O-bound). Cuando el proceso CPU-bound ejecuta, los otros procesos esperan. Algunos de estos estarán en las colas de los dispositivos de E/S pero eventualmente en algún instante pasarán a la cola de procesos listos. En este momento, muchos de los dispositivos de E/S estarán ociosos. Cuando el proceso en ejecución deje el estado Running, los procesos I/O-bound pasarán a ejecutar y rápidamente volverán a bloquearse en espera de E/S. Si el proceso CPU-bound se encuentra bloqueado, entonces el procesador estará ocioso. Por lo tanto, FCFS puede ocasionar un uso indeficiente tanto del procesador como de los dispositivos de E/S.

Proceso	Tiempo de Llegada	Tiempo de Servicio	Tiempo de Comienzo	Tiempo de Finalización	Turnaround	Tiempo de Espera
	0	1	0	1	1	0
	1	100	1	101	100	0
	2	1	101	102	100	101-2=99
	3	100	102	202	199	102-3=99
Promedio					100	49.50

Planificación en SJF

El algoritmo “primero el trabajo más corto” (shortest – job - first). Establece para la planificación una relación entre proceso y ráfaga de la CPU. Es decir, al liberarse la cpu ingresará el proceso con la menor ráfaga de tiempo, el más pequeño primero, y si existiera más de un proceso con igual valor, pues se aplicaría dentro de este el algoritmo anterior (FCFS).

Este algoritmo presenta una gran ventaja, pues el tiempo de espera será mucho menor, pues mientras los procesos de tiempo inferior terminan y ocupan tiempo en operaciones de E/S, el cpu se ocupa de resolver el proceso con mayor tiempo, un algoritmo muy óptimo.
El problema está en conocer la duración del próximo requerimiento de CPU para cada proceso. pero podemos predecirlos usando la información de los ciclos anteriores ejecutados.

Proceso	Tiempo de llegada	Tiemppo de Servicio	Tiempo de Comienzo	Tiempo de Finalización	Turnaround	Tiempo de Espera
A	0	8	0	8	8	0
B	1	4	8	12	12-1=11	8-1=7
C	2	9	17	26	26-2=24	17-2=15
D	3	5	12	1	17-3=14	12-3=9
Promedio					14.25	10.33

Round Robin

damianblanc — Fri, 02 May 2008 10:58:44 CDT

Una manera rápida de reducir la penalización que los procesos cortos sufren con FCFS es usar expropiación basada en un reloj.Una interrupción de reloj es generada a intervalos periódicos. Cuando ocurre la interrupción, el proceso en ejecución es colocado en la cola de procesos listos y el próximo trabajo es seleccionado basado en el esquema FCFS.Cada proceso tiene asignado un intervalo de tiempo de ejecución, llamado quantum o cuanto.

La principal decisión de diseño que surge con Round Robin es el tamañoquantum. Si es muy corto, entonces los procesos se moverán a través del sistema rápidamente. Por otro lado, hay un cierto overhead o desperdicio de tiempo envuelto con el manejo de la interrupción de reloj y las funciones de planificación y despacho. Por lo tanto quantums muy pequeños deberían evitarse. Una alternativa es usar un quantum de tiempo que sea un poco más grande que el tiempo promedio requerido para una interacción típica.

Round Robin es particularmente efectivo para sistemas generales de tiempo compartido. Se implementa con una cola FIFO de procesos. Nuevos procesos son agregados al final de la cola, y toma el proceso que se encuentra en la cabeza de la cola. Actualiza el timer para que interrumpa después del quantum de tiempo.

El desempeño de este algoritmo dependerá del tamaño del quantum. Si el quantum es infinito entonces degenera en FCFS. Si el quantum es muy pequeño entonces Round Robin es llamado compartición de CPU y en teoría pareciera que cada proceso tiene su propio procesador corriendo a 1/n la velocidad del procesador real.

Bajo este esquema es importante considerar el efecto del cambio de contexto.

Generaciones de SO - Historia

deny88 — Tue, 29 Apr 2008 22:03:01 CDT

Los S. O. han estado relacionados históricamente con la arquitectura de las computadoras en las cuales se ejecutan, razón por la cual su historia puede analizarse según las siguientes generaciones y sus principales características. (H. M. Deitel)

Generación Cero (década de 1940):

Carencia total de S. O.
Completo acceso al lenguaje de máquina.

Primera generación (1945-1955): bulbos y conexiones:

Carencia de S. O.
En los años cincuenta comienzan como transición entre trabajos, haciendo la misma más simple.

Segunda generación (1955-1965): transistores y sistemas de procesamiento por lotes (batch):

En los años sesenta aparecen los S. O. para sistemas compartidos con:

Multiprogramación: varios programas de usuarios se encuentran al mismo tiempo en el almacenamiento principal, cambiando el procesador rápidamente de un trabajo a otro.
Multiprocesamiento: varios procesadores se utilizan en un mismo sistema para incrementar el poder de procesamiento.

Posteriormente aparece la independencia de dispositivo:

El programa del usuario especifica las características de los dispositivos que requieren los archivos.
El S. O. asigna los dispositivos correspondientes según los requerimientos y las disponibilidades.

Tercera generación (1965-1980): circuitos integrados y multiprogramación:

Difusión de la multiprogramación:

Partición de la memoria en porciones, con trabajos distintos en cada una de ellas.
Aprovechamiento del tiempo de espera consecuencia de operaciones de e / s, para utilizar la CPU para otros procesos.

Protección por hardware del contenido de cada partición de memoria.

Aparición de técnicas de spooling:

Simultaneous Peripheral Operation On Line: operación simultánea y en línea de periféricos.
Almacenamiento de trabajos de entrada y de salida en dispositivos transitorios rápidos (discos), para disminuir el impacto de los periféricos mas lentos.

Son sistemas de modos múltiples, es decir que deben soportar sistemas de propósitos generales; son grandes y complejos pero muy poderosos.
Interponen una capa de software entre el usuario y el hardware.
Aparecen los lenguajes de control de trabajos, necesarios para especificar el trabajo y los recursos requeridos.
Soportan timesharing (tiempo compartido), variante de la multiprogramación con usuarios conectados mediante terminales en línea, permitiendo la operación en modo interactivo o conversacional.
Aparecen los sistemas de tiempo real, que requieren tiempos de respuesta muy exigentes, especialmente para usos industriales o militares.
Se difunden las computadoras de rango medio.

Cuarta generación (1980-1990): computadoras personales:

Aparición de software amigable con el usuario, destinado a usuarios no profesionales y con una interfase gráfica muy desarrollada.
Desarrollo de sistemas operativos de red y sistemas operativos distribuidos.
Sistemas operativos de red:

Los usuarios están conscientes de la existencia de varias computadoras conectadas.
Cada máquina ejecuta su propio S. O. local.
Son similares a los S. O. de un solo procesador pero con el agregado de:

Controlador de interfaz de la red y su software de bajo nivel.
Software para conexión y acceso a archivos remotos, etc.

Sistemas operativos distribuidos:

Aparece ante los usuarios como un S. O. de un solo procesador, aún cuando de soporte a varios procesadores.
Los usuarios no son conscientes del lugar donde se ejecutan sus programas o donde se encuentran sus archivos, ya que lo debe administrar el S. O. automáticamente.
Deben permitir que un programa se ejecute mediante varios procesadores a la vez, maximizando el paralelismo.

Aparición de emuladores de terminal para el acceso a equipos remotos desde computadoras personales (PC).
Gran énfasis en la seguridad, en especial por el desarrollo de los sistemas de comunicaciones de datos.
El S. O. crea un ambiente de trabajo según el concepto de máquina virtual, que lo aísla del funcionamiento interno de la máquina.
Proliferación de sistemas de bases de datos, accesibles mediante redes de comunicación.

Bibliografìa: H. M. Deitel. Introducción a los Sistemas Operativos. Addison-Wesley Iberoamericana, México, 1987.

UNIX.

La historia de UNIX se remonta desde los años 60. Este sistema operativo estuvo desarrolado originalmente para mejorar las máquinas de aquel tiempo. Fue desarrolado por investigadores del MIT (Masachusets Institute of Tecnologi), creando el primer sistema operativo de tiempo compartido, es decir, varios programas ya eran capaces de ejecutarse al mismo tiempo. El primer sistema operativo de este tipo fue el CTSS (Compatible Time Sharing System).

El mismo MIT creó, después, el sistema operativo MULTICS, el cual ya poseía las características de multifunción y multiusuario. Este sistema operativo poseia:

-Sistema de ficheros arborescente.
-Interprete de comandos (Shell).

Hacia 1969, Ken Thompon trabajó en un programa para simular la posición de los planetas del sistema solar y encargó un programa para poder pasar un programa de una máquina "grande" a una "pequeña" (la DEC PDP-7). Este trabajo fue encargado a Denis Richie (inventor del leguage C). Esta migración fue realizada en lenguage ensamblador.

En los laboratorios Bell Labs, también trabajó Brian W. Kenigham el cual se unió a los otros dos investigadores mencionados anteriormente para crear en 1971 un lenguage basado en el sistema operativo MULTICS, pero este lenguage se construyó más pequeño y más potente que el anterior. Así nació UNIX, el cual fue programado integramente en lenguaje C, siendo un sistema operativo de alto nivel. Por otra parte, este sistema operativo se puso a disposición de la comunidad universitaria que fue mejorando poco a poco UNIX hasta que llegó a la universidad de Berkeley. A partir de ese momento UNIX se dividió en varias ramas:

-AT & T (Bell Labs).
-BSD (Berkely Software Develoment) en 1977.
-UNIX System V en 1983.

Con la versión UNIX System V, comenzó la comercialización del sistema operativo modificándose este para que tuviese mayor portabilidad.

En 1984, Sun Microsystems le añadió el paquete RPC (Remote Procedure Call), que fue el primer sistema de comunicación entre ordenadores. Po r esas fechas, también fue incorpoprado el paquete NFS (Netware File System).

En la actualidad, existen las siguientes versiones de UNIX:

- HP-UX (Hewlett-Packard).
-ULTIX (DEC).
-AIX (IBM).
-SINIX (Siemens).
-SENIX (Microsoft).
-SUNOX (Sun).
-SOLARIS (Sun).

CARACTERÍSTICAS DE UNIX.

-Sistema operativo multiusuario.
-Multitarea.
-Esquema gerarquico de privilegio de ejecución.
-Sistema modular (en capas).
-Sistema de protección de memoria.
-Sistema en tiempo compartido.
-Tiene numerosas sells.
-Unix posee dos interfaces: Sell y API
-En UNIX los comandos de la Shell son crípticos.
-Al ser UNIX un sistema operativo de tiempo compartido no lo es de tiempo
real.

CARACTERÍSTICAS DE GNU / LINUX.

Linux es un sistema operativo creado por Linus Torvalds a comienzos de los años 90. Torvals era, en aquel tiempo, alumno de Andrew Tannembanm (creador del sistema operativo MINIX). A partir de MINIX, Torvals creó en 1991 el núcleo de Linux.

Antes, en 1983, Richard Stallman fundó (junto a un grupo de colaboradores a los cuales no les gustaba que el software estuviese ligado a una patente), el FSF (Free Software Fundation) para crear una versión de UNIX para usuarios de Pc's, sin embargo, no consiguieron desarrollar el núcleo de UNIX. Cuando en 1991, Torwals dispuso de un núcleo UNIX grácias a Linux, Stallman le propuso que se uniese al proyecto FSF. Así nació GNU / Linux.

Gracias a que Linus Torwals "colgó" el código fuente de Linux en internet la comunidad internauta empezó a mejorarlo, saliendo a la luz las diferentes versiones de Linux que existen hoy en día haciendo que Linux sea una de las mejores opciones que existen en la actualidad a otros sistemas operativos como Windows.

Planificación de Procesos

alejandroml — Mon, 28 Apr 2008 13:56:43 CDT

Que tiempo de procesador es asignado a cada proceso en un sistema multiprogramado?
Lo determina el PLANIFICADOR a travès del uso de algoritmos especìficos.

Objetivos de la planificación
Niveles de planificación (largo, mediano y corto plazo)

Tipo de algoritmos:

Apropiativos y No Apropiativos

FCFS (first come first served)
SJF

Prioridades

Circular o RR (Round Robin)

Objetivos y niveles

jcarnero — Wed, 23 Apr 2008 20:59:28 CDT

Necesidad de la planificación
En épocas pasadas de los sistemas de procesamiento por lotes (batch), la idea que existía sobre la planificación era bastante simple y consistía en aplicar un algoritmo secuencial. Esto producía un desaprovechamiento muy importante de las capacidades del procesador ya que la ejecución de un proceso alternaba entre dos estados de ejecución: utilizando la CPU o esperando a que se realice una operación de E/S, por lo que mientras se trabajaba con un dispositivo, el procesador se encontraba inactivo.
Más tarde, surgieron los sistemas multiprogramados, en donde se intentó maximizar la utilización de la CPU. Esto se pudo conseguir manteniendo varios procesos en la memoria, y cuando un proceso tenía que esperar, el sistema operativo le quitaba la CPU y se lo asignaba a otro proceso que se encontraba en dicha memoria. Por lo tanto, la tarea de la planificación cobró gran importancia por su incidencia directa sobre el rendimiento del sistema, ya que el sistema operativo debía decidir qué proceso esperaría y qué proceso continuaría.

Definición
Podemos definir a la planificación como un conjunto de políticas y mecanismos incorporados al sistema operativo, a través de un módulo denominado planificador, que debe decidir cuál de los procesos en condiciones de ser ejecutado conviene ser despachado primero y qué orden de ejecución debe seguirse. Esto debe realizarse sin perder de vista su principal objetivo que consiste en el máximo aprovechamiento del sistema, lo que implica proveer un buen servicio a los procesos existentes en un momento dado. Un
"buen" servicio podría traducirse en tiempo de respuesta aceptable, productividad y eficiencia del procesador.

Objetivos de la Planificación
Los objetivos de la planificación del procesador son los siguientes:

Ser justa:

Todos los procesos son tratados de igual manera.
Ningún proceso es postergado indefinidamente.

Maximizar la capacidad de ejecución:

Maximizar el número de procesos servidos por unidad de tiempo.

Maximizar el número de usuarios interactivos que reciban unos tiempos de respuesta aceptables:

En un máximo de unos segundos.

Ser predecible:

Un trabajo dado debe ejecutarse aproximadamente en la misma cantidad de tiempo independientemente de la carga del sistema.

Minimizar la sobrecarga:

No suele considerarse un objetivo muy importante.

Equilibrar el uso de recursos:

Favorecer a los procesos que utilizarán recursos infrautilizados.

Equilibrar respuesta y utilización:

La mejor manera de garantizar buenos tiempos de respuesta es disponer de los recursos suficientes cuando se necesitan, pero la utilización total de recursos podrá ser pobre.

Evitar la postergación indefinida:

Se utiliza la estrategia del “envejecimiento” .
Mientras un proceso espera por un recurso su prioridad debe aumentar, así la prioridad llegará a ser tan alta que el proceso recibirá el recurso esperado.

Asegurar la prioridad:

Los mecanismos de planificación deben favorecer a los procesos con prioridades más altas.

Dar preferencia a los procesos que mantienen recursos claves:

Un proceso de baja prioridad podría mantener un recurso clave, que puede ser requerido por un proceso de más alta prioridad.
Si el recurso es no apropiativo, el mecanismo de planificación debe otorgar al proceso un tratamiento mejor del que le correspondería normalmente, puesto que es necesario liberar rápidamente el recurso clave.

Dar mejor tratamiento a los procesos que muestren un “comportamiento deseable”:

Un ejemplo de comportamiento deseable es una tasa baja de paginación.

Degradarse suavemente con cargas pesadas:

Un mecanismo de planificación no debe colapsar con el peso de una exigente carga del sistema.
Se debe evitar una carga excesiva mediante las siguientes acciones:

No permitiendo que se creen nuevos procesos cuando la carga ya es pesada.
Dando servicio a la carga más pesada al proporcionar un nivel moderadamente reducido de servicio a todos los procesos.

Niveles de planificación
La planificación se hace en cuatro instantes de tiempo. De estas cuatro, una no la realiza el sistema operativo, sino q ue es externa al procesamiento, pero tiene una influencia enorme sobre la definición del procesamiento, dado que el sistema operativo queda determinado por las decisiones que se toman en este nivel. A esta instancia le daremos el nombre de "extra largo plazo" por ser en la escala de tiempo del ser humano.
En la administración del procesador podemos distinguir tres niveles de planificación de acuerdo a la escala de tiempo en que se realiza la misma. El largo plazo en segundos, mediano plazo en milisegundos y el corto plazo en nanosegundos o
microsegundos.

Planificación a largo plazo
El planificador a largo plazo, scheduler o planificador de trabajos, es un administrador que se encarga de organizar la ejecución con un adecuado planeamiento de recursos para que el trabajo se ejecute ordenadamente y eficientemente según la modalidad de procesamiento.
El sheduler se ejecuta con poca frecuencia, sólo cuando se necesita crear un nuevo proceso en el sistema, cuando termina un proceso, o ingresa un usuario en el sistema, por lo que tiene prioridad máxima para ejecutar. Es el responsable de controlar el nivel de multiprogramación del sistema y el balance de carga del sistema. Esto último implica la selección cuidadosa de trabajos para mantener un adecuado balance de carga de procesos que hacen uso de E/S intensivo (I/O bound) o uso de CPU intensivo (CPU bound).
Procedamos a describir un poco su accionar ante un nuevo trabajo. Un software del sistema operativo, llamado monitor, recibe al nuevo trabajo y lo carga en la memoria central. Después de haber sido recibido el trabajo, el sheduler se encarga de preparar y crear procesos con sus respectivos bloques de control del proceso (BCP) para poder ejecutarlos. Si los recursos que solicita estuvieran disponibles, se le asignan y se lo ingresa a la cola de listos para ejecutar.
Existen diferentes filosofías en el procesamiento de un trabajo. Todas ellas responden a ciertos criterios de planificación que se vuelcan en los respectivos algoritmos de planificación. Esto se conoce como la modalidad de ejecución o procesamiento. Los más importantes son:

Batch: Apunta estrictamente al exhaustivo uso del procesador en detrimento del usuario. Sus principales caracterísiticas son:

La CPU es monoprogramada.
No existe diferencia entre trabajo y proceso.
El scheduler elige el trabajo, crea el proceso y lo ejecuta.
Prácticamente hay un solo nivel de planificación.

Interactivo: Apunta al servicio del usuario en detrimento de la performance del procesador. Es multiprogramado pues se multiplexa la CPU entre varios programas.

Multiprocesado: Es un ambiente en el que existen varios procesadores para servir a los procesos en ejecución.

Procesamiento distribuido o en red: Es una forma de procesamiento en que se le presenta al usuario una máquina virtual y en que el procesamiento se realiza en distintas máquinas diseminadas geográficamente y conectadas por una red.

En conclusión y siendo un poco más precisos, podríamos decir que las tareas que involucra este nivel de planificación son:

Mantener un registro de estado de todos los trabajos en el sistema (JBC).

Establecer una estrategia para el pasaje entre las colas de suspendidos y la de listos.

Asignar recursos (memoria central, dispositivos, procesadores, etc.) a cada trabajo.

Pedir (recuperar) los recursos cuando los trabajos se han completado.

Detectar y prevenir los conflictos de abrazo mortal o deadlock.

Dar entrada a nuevos trabajos.

Asignar prioridades a los procesos. Esto genera el orden de ejecución y viene determinado básicamente por el orden de procesos en la cola de listos, o sea, el orden en el que el dispatcher los seleccionará de esta cola para ponerlos en ejecución (generalmente el primero de la cola).

Implementar las políticas de asignación de recursos, razón por la que se le otorga la máxima prioridad en el sistema para que el dispatcher lo seleccione primero si está libre el procesador y se ejecuta cuando:

1. Se pide o libera un recurso.
2. Cuando termina un proceso.
3. Cuando llega un nuevo trabajo al pool de procesos
4. Cuando llega un nuevo usuario al sistema.

Planificación a mediano plazo
Es el que decide sacar de memoria central y llevar a disco (swap-out) a aquellos procesos inactivos o a los activos cuyos estados sean bloqueado momentáneamente o temporalmente o los suspendidos y luego, cuando desaparezcan las causas de sus bloqueos, traerlos nuevamente a memoria (swap-in) para continuar su ejecución. Este tipo de planificador se encuentra solo en algunos sistemas especialmente en los de tiempo compartido, ya que permite mantener un equilibrio entre los procesos activos e inactivos.
Este planificador puede ser invocado cuando quede espacio libre de memoria por efecto de la terminación de un proceso o cuando el suministro de procesos caiga por debajo de un límite especificado.
En algunos casos suplanta al planificador de largo plazo y otros lo complementa: Por ejemplo en sistemas de tiempo compartido, el long-term scheduler puede admitir más usuarios de los que pueden caber realmente en memoria. Sin embargo, como los trabajos de estos sistemas están caracterizados por ciclos de actividad y ciclos de ociosidad, mientras el usuario piensa algunos procesos pueden ser almacenados y al recibir respuesta vueltos a poner en la cola de listos.
Este tipo de planificación solo es usado en sistemas con mucha carga de procesos, ya que el procedimiento de swapping produce mucho overhead, haciendo bajar considerablemente el desempeño general.

Planificación a corto plazo
También llamado short-term scheduler o low scheduler, es el responsable de decidir quién, cuándo, cómo y por cuánto tiempo recibe el procesador un proceso que está preparado (ready queue) para ejecutar (los recursos a esta altura ya deben estar todos disponibles para este trabajo). Además en sistemas operativos con esquemas expropiativos (se quita el recurso procesador al proceso) verifica las interrupciones.
El planificador a corto plazo es invocado cada vez que un suceso (interno o externo) hace que se modifique el estado global del sistema. Por ejemplo:
· Tics de reloj (interrupciones basadas en el tiempo).
· Interrupciones y terminaciones de E/S.
· La mayoría de las llamadas operacionales al sistema operativo (en oposición a las llamadas de consulta).
· El envío y recepción de señales.
· La activación de programas interactivos.

El low scheduler debe ser rápido y con poca carga para el procesador para que se mantenga el rendimiento, ya que se le debe sumar además el tiempo que toma el cambio de contexto. El cambio de contexto o context switch consiste en la conmutación de la CPU entre un proceso y otro y es overhead puro, por lo tanto debe ser lo más rápido posible. Algunos valores típicos oscilan entre 1 y 100 m seg que se conoce como dispatch latency.

El context switch involucra:

Preservar el estado del viejo proceso (guardar en el stack su PCB).

Recuperar el estado del nuevo proceso (recuperar su PCB).

Bifurcar a la dirección donde había sido suspendido el nuevo proceso.

Apropiativos y No Apropiativos

jcarnero — Wed, 23 Apr 2008 20:55:45 CDT

El planificador es el módulo del sistema operativo que decide qué proceso se debe ejecutar, para ello usa un algoritmo de planificación que debe cumplir con los siguientes objetivos:

Imparcialidad.

Política justa.

Eficiencia: mantener la CPU ocupada en lo posible el mayor tiempo con procesos de usuario.

Minimizar el tiempo de espera de usuarios.

Maximizar el número de procesos ejecutados. (Rendimiento: trabajos que se procesan por hora).

Tiempo de respuesta excelente (por ejemplo: minimizar el tiempo de respuesta para los usuarios interactivos).

Predecibilidad en la ejecución.

Equilibrio en el uso de los recursos.

Antes de comenzar a describir los respectivos algoritmos de planificación, es importante conocer dos conceptos relacionados. Uno de ellos es la función de selección que determina qué proceso, de entre los listos, se elige para ejecutar a continuación. El otro es el modo de decisión o esquema de planificación, que especifica los instantes de tiempo en que se aplica la función de selección. Hay dos categorías generales:

No Apropiativo (Una vez que se le ha otorgado la cpu a un proceso, no le puede ser retirada)
También conocido como cooperative multitasking. Una vez que el proceso pasa al estado de ejecución, continúa ejecutando hasta que termina, se bloquean en espera de una E/S o al solicitar algún servicio del sistema. Esta política de ejecución para terminación fue implementada en los primeros sistemas de lote (batch).

Características

Significa que los trabajos “largos” hacen esperar a los trabajos “cortos”.
Logra más equidad en el tratamiento de los procesos.
Logra hacer más predecibles los tiempos de respuesta puesto que los trabajos nuevos de prioridad alta no pueden desplazar a los trabajos en espera.

Apropiativo (Una vez que se le ha otorgado la cpu a un proceso, le puede ser retirada)
Generalmente conocida como política de planificación por torneo. El proceso que se está ejecutando actualmente puede ser interrumpido y pasado al estado de listos por el sistema operativo. La decisión de sustituirlos por otro proceso puede llevarse a cabo cuando llega un nuevo proceso, cuando se produce una interrupción que lleva a un proceso bloqueado al estado listo o periódicamente, en función de una interrupción del reloj.

Características

Es útil cuando los procesos de alta prioridad requieren atención rápida.
Es importante para garantizar buenos tiempos de respuesta en sistemas interactivos de tiempo compartido.
Tiene su costo en recursos, ya que el intercambio de contexto implica sobrecarga y además requiere mantener muchos procesos en el almacenamiento principal, en espera de la cpu, lo que también implica sobrecarga.

Prioridades

jercoli — Tue, 22 Apr 2008 15:50:31 CDT

Prioridades estáticas:

Se asigna una prioridad al proceso para toda su ``vida''.

Por ejemplo, puede reflejar distintos ``status'' de los usuarios.

Prioridades dinámicas:

La prioridad de un proceso cambia durante su vida.

El cambio de prioridad puede reflejar información nueva que se tiene sobre el comportamiento

de un proceso.

Ejemplo: favorecimiento de procesos con mucha entrada/salida.

Pueden usarse clases de prioridad, cada clase ordenada mediante una cola. Para gestionar cada

cola, puede usarse round-robin.

BCP, Cambios e Interrupciones

martinorengia — Fri, 18 Apr 2008 13:07:32 CDT

Bloque de control del proceso

El Bloque de control del proceso ó BCP o en inglés PCB (Process Control Block) es un registro especial donde el sistema operativo agrupa toda la información que necesita conocer respecto a un proceso particular. Cada vez que se crea un proceso el sistema operativo crea el BCP correspondiente para que sirva como descripción en tiempo de ejecución durante toda la vida del proceso.

Cuando el proceso termina, su BCP es borrado y el registro puede ser utilizado para otros procesos. Un proceso resulta conocido para el sistema operativo y por tanto elegible para competir por los recursos del sistema sólo cuando existe un BCP activo asociado a él. El bloque de control de proceso es una estructura de datos con campos para registrar los diferentes aspectos de la ejecución del proceso y de la utilización de recursos. La información almacenada en un BCP incluye típicamente algunos o todos los campos siguientes:

· Identificador del proceso (Process Identificator -PID-, de sus siglas en Inglés).
· Estado del proceso. Por ej. listo, en espera, bloqueado.
· Contador de Programa: Dirección de la próxima instrucción a ejecutar.
· Valores de registro de CPU. Se utilizan también en el cambio de contexto.
· Espacio de direcciones de memoria.
· Prioridad en caso de utilizarse dicho algoritmo para planificación de CPU.
· Lista de recursos asignados (incluyendo descriptores de archivos y sockets abiertos).
· Estadísticas del proceso.
· Datos del propietario (owner).
· Permisos asignados.
· Signals pendientes de ser servidos. (Almacenados en un mapa de bits)

Esta lista es simplemente indicativa, cada sistema operativo tiene su propio diseño de BCP, con el conjunto de metadatos necesarios para la administración. Puede medir desde 32 bits a 1024. Su denominación cambia según el sistema operativo, por ej. en IBM se designa PSW por palabra de estado de proceso. Difiere significativamente entre los sistemas de procesamiento por lotes (BATCH) y los sistemas interactivos.

Algunos sistemas de multiprogramación incluyen información de mantenimiento con el propósito de facturar a los usuarios individuales el tiempo de procesador, el almacenamiento, las operaciones de E/S y otras utilizaciones de recursos.
Una vez creado, el BCP se rellena con los atributos definidos como parámetros que se hallan en la plantilla del proceso o que son especificados como parámetros de la llamada al sistema operativo crear_proceso. En ese momento el sistema operativo suele asignar valores a otros campos. Por ejemplo, cuando se crea un proceso, los registros e indicadores hardware se fijan a los valores proporcionados por el cargador/enlazador. Cada vez que un proceso queda suspendido, el contenido de los registros del procesador es generalmente guardado en la pila, y el puntero al marco de la pila en cuestión se almacena en el BCP. De este modo los valores de los registros son restaurados cuando el proceso es seleccionado para ejecutarse nuevamente.

Listas de procesos

El Sistema Operativo mantiene listas de Bloque de Control de procesos para cada uno de los estados del sistema.
Cada proceso pertenece a una única lista. Posee una lista de procesos prepara dos, una lista de los bloquea dos y en el caso de sistemas multiprocesador es una lista de procesos activos.

Cambio de contexto

Un cambio de contexto consiste en la ejecución de una rutina perteneciente al núcleo del sistema operativo multitarea de una computadora, cuyo propósito es parar la ejecución de un hilo (o proceso) para dar paso a la ejecución de otro distinto.

Motivación

En principio, una computadora que dispone de un único microprocesador solamente puede ejecutar un programa al mismo tiempo. No es posible ejecutar otro programa hasta que ha finalizado el anterior.
No obstante, sería posible simular la ejecución simultánea de dos o más programas si fuera posible detener un programa en cualquier momento y renaudarlo posteriormente sin pérdida de información. Los programas alternarían su ejecución durante cortos periodo de tiempo aparentando que se ejecutan todos a la vez. Esto se denomina ejecución concurrente.
Además, durante la ejecución de un programa existen muchos tiempos muertos donde no es necesario el uso del microprocesador. Se trata de los momentos en los que el programa está esperando a que finalice una operación de entrada/salida, por ejemplo, una lectura desde el disco duro. Estos tiempos muertos podrían aprovecharse para ejecutar otro programa.

Cómo funciona

Para hacer realidad la ejecución concurrente en primer lugar es necesario que el programa en ejecución se detenga voluntariamente. Puesto que esto no va a ocurrir nunca, es imprescindible la intervención del hardware. Gracias a las interrupciones generadas por el propio ordenador, es posible expulsar el programa en ejecución para dar paso al sistema operativo.
Cuando esto ocurre, el sistema operativo ejecuta inmediatamente la rutina de cambio de contexto. Esta rutina realiza las siguientes operaciones en el orden indicado:

1. Salvar el estado del programa que se estaba ejecutando. El estado, también denominado contexto, consiste en los valores de todos los registros del microprocesador. Se copian en la memoria principal.
2. Seleccionar otro programa para ejecutar. Entre todos los programas que estén preparados para ejecutarse, la rutina selecciona uno de ellos siguiendo algún algoritmo equitativo.
3. Restaurar el estado del programa seleccionado. Para ello, se toma el estado previamente copiado en la memoria principal y se vuelca en los registros del microprocesador.
4. Ejecutar el programa seleccionado. La rutina termina su ejecución saltando a la instrucción que estaba pendiente de ejecutar en el programa seleccionado.

Este ciclo se repite bien cada vez que ocurre un evento de entrada/salida, bien cuando vence un temporizador programado en el hardware. Dicho temporizador hace saltar una interrupción cada 150 milisegundos aproximadamente (según sistema operativo).

Se denomina conmutación de contexto al mecanismo mediante el cual el sistema almacena la información del proceso que se está ejecutando y recupera la información del proceso que ejecutará enseguida. A continuación se presenta un esquema explicativo de este mecanismo:

La ejecución concurrente también es aplicable a computadoras Multiprocesador. En este caso, se llevan a cabo cambios de contexto en cada microprocesador de manera independiente. Un cambio de contexto siempre se ejecuta ante una interrupción ya sea de software o hardware. Un cambio de contexto no necesariamente implica un cambio de proceso. Cuando ocurre una interrupción que sólo genera un cambio de contexto más no un cambio de proceso, todo lo que se debe hacer es salvar la información de estado del procesador cuando se produzca la interrupción y restaurar dicha información cuando el control vuelva al programa que estaba en ejecución. Las funciones de salvar y restaurar suelen llevarse acabo en el hardware.

Cambio de Modo

Las aplicaciones no deben poder usar todas las instrucciones de la CPU. No obstante el SO, tiene que poder utilizar todo el juego de instrucciones del CPU. Por ello, una CPU debe tener (al menos) dos modos de operación diferentes:

· Modo usuario: el CPU podrá ejecutar sólo las instrucciones del juego restringido de las aplicaciones.
· Modo supervisor: la CPU debe poder ejecutar el juego completo de instrucciones.

Interrupciones y excepciones

El SO ocupa una posición intermedia entre los programas de aplicación y el hardware. No se limita a utilizar el hardware a petición de las aplicaciones ya que hay situaciones en las que es el hardware el que necesita que se ejecute código del SO. En tales situaciones el hardware debe poder llamar al sistema, pudiendo deberse estas llamadas a dos condiciones:
· Algún dispositivo de E/S necesita atención.
· Se ha producido una situación de error al intentar ejecutar una instrucción del programa (normalmente de la aplicación).

En ambos casos, la acción realizada no está ordenada por el programa de aplicación, es decir, no figura en el programa.
Según los dos casos anteriores tenemos las interrupciones y la excepciones:

· Interrupción: señal que envía un dispositivo de E/S a la CPU para indicar que la operación de la que se estaba ocupando, ya ha terminado.
· Excepción: una situación de error detectada por la CPU mientras ejecutaba una instrucción, que requiere tratamiento por parte del SO.

Al interrumpirse la ejecución de un proceso se salva su estado en el BCP, como se puede observar en la siguiente imagen:

Tratamiento de las interrupciones

Una interrupción se trata en todo caso, después de terminar la ejecución de la instrucción en curso.
El tratamiento depende de cuál sea el dispositivo de E/S que ha causado la interrupción, ante la cual debe poder identificar el dispositivo que la ha causado.

Importancia de las interrupciones

El mecanismo de tratamiento de las interrupciones permite al SO utilizar la CPU en servicio de una aplicación, mientras otra permanece a la espera de que concluya una operación en un dispositivo de E/S.
El hardware se encarga de avisar al SO cuando el dispositivo de E/S ha terminado y el SO puede intervenir entonces, si es conveniente, para hacer que el programa que estaba esperando por el dispositivo, se continúe ejecutando.
En ciertos intervalos de tiempo puede convenir no aceptar señales de interrupción. Por ello las interrupciones pueden inhibirse por programa (aunque esto no deben poder hacerlo las mismas).

Excepciones

Cuando la CPU intenta ejecutar una instrucción incorrectamente construida, la unidad de control lanza una excepción para permitir al SO ejecutar el tratamiento adecuado. Al contrario que en una interrupción, la instrucción en curso es abortada. Las excepciones al igual que las interrupciones deben estar identificadas.

Clases de excepciones

Las instrucciones de un programa pueden estar mal construidas por diversas razones:

El código de operación puede ser incorrecto.
Se intenta realizar alguna operación no definida, como dividir por cero.
La instrucción puede no estar permitida en el modo de ejecución actual.
La dirección de algún operando puede ser incorrecta o se intenta violar alguno de sus permisos de uso.

Importancia de las excepciones

El mecanismo de tratamiento de las excepciones es esencial para impedir, junto a los modos de ejecución de la CPU y los mecanismos de protección de la memoria, que las aplicaciones realicen operaciones que no les están permitidas. En cualquier caso, el tratamiento específico de una excepción lo realiza el SO.
Como en el caso de las interrupciones, el hardware se limita a dejar el control al SO, y éste es el que trata la situación como convenga.
Es bastante frecuente que el tratamiento de una excepción no retorne al programa que se estaba ejecutando cuando se produjo la excepción, sino que el SO aborte la ejecución de ese programa. Este factor depende de la pericia del programador para controlar la excepción adecuadamente.

Regiones proceso Unix

jercoli — Fri, 18 Apr 2008 07:52:06 CDT

UNIX divide (desde el punto de vista lógico) el espacio de direcciones virtuales de un proceso en zonas denominadas:
Regiones
- Son áreas contiguas del espacio de direcciones.
- Pueden ser compartidas y/o protegidas - Son independientes de la política de gestión de memoria.

*Regiones típicas
-Texto (Contiene el código de las funciones del programa. Es de solo lectura)
- Datos (Contiene los datos, variables globales, tanto inicializadas como sin inicialización explicita del proceso. El heap suele ser parte de esta región)
- Pila (o stack, usado para pasar los parámetros a las funciones y por éstas para sus variables locales)

Descripción de regiones:
* Una tabla de regiones global.
* Contiene una entrada (fila) por cada región activa en el sistema.
- Información necesaria para localizar la región en memoria física.
- Tamaño de la región.

* Una tabla de regiones por proceso (pregión).
* Apuntada desde la tabla de procesos.
* Cada entrada en esta tabla:
- Apunta a una entrada en la tabla de regiones global.
- Dirección virtual de comienzo de la región.
- Tipo de acceso permitido a la región.

*La conjunción de ambos tipos de tablas permite compartir regiones en distintas direcciones virtuales.

(*Si la arquitectura para la gestión de memoria está basada en páginas, cada entrada en la tabla de regiones apunta a una tabla de Páginas.)

Operaciones sobre regiones

Las operaciones sobre regiones que hace el kernel son :

asignar una región (fork(), exec(), shmget())
encadenar una región a un proceso (fork(), exec(), shmat())
cambiar el tamaño de una región ( brk(), sbrk(), malloc() )
cargar una región (exec())
desasignar una región (exec(), exit(), shmctl(IPC RMID, ))
desencadenar una región del espacio de direcciones de un proceso (exec(), exit(), shmdt()) duplicar una región (fork())

El espacio de direcciones de un proceso se almacena como una lista enlazada de sus segmentos (código, datos, pila . . . ). En la estructura proc hay una referencia a una estructura as (address space). La estructura as contiene la referencia a la primera de las estructuras de la lista que describe los segmentos que constituyen el espacio de direcciones. Cada segmento esta descrito por una estructura seg que contiene una referencia a una estructura segvn_data.