Monografias.com > Sin categoría
Descargar Imprimir Comentar Ver trabajos relacionados

Diseño de sistemas operativos. Gestión de procesos (página 2)




Enviado por Pablo Turmero



Partes: 1, 2

Monografias.com

Tratamiento de excepciones
Rutina en ensamblador: vector contiene dirección de comienzo
Estructura típica: similar al tratamiento de interrupciones
Se debe comprobar nivel previo de procesador:
Si era sistema:
Pánico: Error en el código del S.O.
Se muestra mensaje e info. de depuración y S.O. se para
Si era usuario:
Error en programa de usuario
Tratamiento dependiente de S.O.
En UNIX manda señal a proceso
No siempre error: Puede tratarse de un fallo de página

Monografias.com

Tratamiento de llamadas (1/2)
Típicamente un único vector de int. para todas las llamadas
Cada llamada tiene asignado un número
S.O. tiene definido un vector con direcciones de rutinas que llevan a cabo cada servicio
S.O. recibe nº de llamada (normalmente en un registro):
S.O. indexa con él en el vector
Parámetros de la llamada normalmente en pila de usuario
Linux usa registros (como mucho 6 parámetros)
Resultado de la llamada se suele devolver en un registro

Monografias.com

Tratamiento de llamadas (2/2)
Rutina en ensamblador: vector contiene dirección de comienzo
Estructura típica similar a anteriores:
Salvar registros en pila de núcleo
Obtener número de llamada (N).
Invocar función indexando en tabla de llamadas
resultado=(*tabla_servicios[N])();
la función obtiene y valida los parámetros de la llamada recibidos en pila de usuario
Devuelve resultado (puede devolverlo en un registro)
Restaurar registros de pila del núcleo del proceso
RETI

Monografias.com

Invocación de llamadas al sistema
Interfaz a los programas: rutina de biblioteca
read(f, buf, tam)
Programa se enlaza con biblioteca de llamadas
Rutina de llamada codificada en ensamblador:
read(){
PUSH parámetro1
………………………..
MOVE R0, #NUM_READ
INT 0x80
Valor devuelto está en R0
………………………..
RET
}

Monografias.com

Multiplexación de procesos
Cambio de modo:
De usuario a núcleo (excepción, llamada o interrupción)
De sistema a usuario (RETI)
No hay c. de contexto: Mismo proceso en distinto modo
Multiprogramación implica reasignar el procesador cuando:
Proceso se bloquea
Es conveniente ejecutar otro proceso en vez del actual
Necesidad salvar/restaurar información de los procesos
Info. del proceso ? Contexto del proceso

Monografias.com

Contexto de un proceso
Información asociada con el proceso
Almacenada en el Bloque de Control del Proceso (BCP)
Tabla de procesos: Vector de BCPs (mejor lista de BCPs)
Contenido típico:
Estado del proceso
Copia del contenido de los registros del procesador
Información de planificación (p.e. prioridad)
Información sobre el mapa de memoria del proceso
Información de ficheros y E/S
Información de contabilidad (p.e. tiempo de UCP usado)
"Dueño" del proceso (uid y gid en UNIX)
Punteros para construir listas de BCPs
Y muchos más: Relaciones entre procs., pid, señales, etc.

Monografias.com

Definición de BCP
S.O. es sólo otro programa: Usa definiciones convencionales
struct task_struct {
long state;
long priority;
unsigned long signal;
struct task_struct *next_run, *prev_run;
/* filesystem information */
struct fs_struct *fs;
/* open file information */
struct files_struct *files;
/* memory management info */
struct mm_struct *mm;
…………………..
}

Monografias.com

Estado de un proceso
Elemento del contexto del proceso
Durante su vida el proceso pasa por varios estados:
En ejecución: UCP asignada
Núm. Procesos en ejecución ? Núm. Procesadores
Listo para ejecutar: No hay procesador disponible para él
Bloqueado: Esperando un evento
En sistemas con suspensión de procesos, estados adicionales:
Suspendido y listo: Expulsado pero listo para ejecutar
Suspendido y bloqueado: Expulsado y esperando un evento

Monografias.com

Transiciones entre estados
Transición disparada siempre por activación del S.O.
No toda activación del S.O. implica c. de estado de un proceso.
Posibles transiciones para modelo con 3 estados:

Monografias.com

Cambio de contexto
Cambio del proceso asignado al procesador
Activación del S.O. que cambia estado de dos procesos:
Proceso P pasa de en ejecución a listo o bloqueado
Proceso Q pasa de listo a en ejecución
C. contexto: Cambio de proceso
Sólo cuando proceso está en modo núcleo
El propio proceso (P):
cambia su estado
activa el planificador ? selecciona Q
salva su contexto en BCP
restaura contexto de Q del BCP ? ya está ejecutando Q

Monografias.com

Cambio de contexto
Cuando proceso P vuelva a ejecutar:
Seguirá en el punto donde estaba (después de c. contexto)
Dificultad para entender el código de gestión de procesos
No toda activación del S.O. implica c. contexto
No es "trabajo útil". Duración típica: decenas de microsegs.
Código del c. contexto depende de arquitectura:
Escrito en ensamblador
En Linux switch_to(prev,next)

Monografias.com

Tipos de c. de contexto
Cambio "voluntario":
Proceso realiza llamada al sistema que implica esperar por evento
Transición de en ejecución a bloqueado
Ejemplos: leer del terminal o bajar un semáforo cerrado
Motivo: Eficiencia en el uso del procesador
Cambio "involuntario":
S.O. le quita la UCP al proceso
Transición de en ejecución a listo
Ejemplos: fin de rodaja de ejecución o pasa a listo proceso bloqueado de mayor prioridad
Motivo: Reparto del procesador

Monografias.com

Colas de procesos
S.O. enlaza BCPs en colas
BCP contiene punteros para permitir formar colas
Algunos ejemplos:
Cola de procesos listos
en muchos sistemas, proceso en ejecución también está en ella
Cola de procesos bloqueados esperando operación sobre un disco
Cola de procesos bloqueados en un semáforo
Cola de procesos esperando que transcurra un plazo de tiempo
En Linux, colas de bloqueados: wait queues
Un BCP debería estar en una sola cola en cada instante
Cambio de estado implica pasar el BCP de una cola a otra

Monografias.com

Bloqueo de un proceso
Bloquear (cola de bloqueo) {
Estado de proceso actual = BLOQUEADO;
NivelUCPPrevio = FijarNivelIntUCP(máximo); /* Prohibir interrupciones */
Mover BCP de cola de listos a cola del evento;
nuevo_proceso = planificador( );
Cambio_contexto(proceso_actual, nuevo_proceso);
FijarNivelIntUCP(NivelUCPPrevio); /* Por aquí continuará, restaurando nivel int. de UCP, cuando se desbloquee y sea elegido por planificador, mientras habrán ejecutado otros procesos */
}

Bloquear no debe invocarse desde rutina de interrupción
Proceso actual no está relacionado con la interrupción

Monografias.com

Desbloqueo de un proceso

Desbloquear (cola de bloqueo) {
NivelUCPPrevio = FijarNivelIntUCP(máximo); /* Prohibir interrupciones */
Seleccionar proceso en la cola (primero si política FIFO);
Estado de proceso elegido = LISTO;
Mover BCP de proceso elegido de cola del evento a cola de listos;
FijarNivelIntUCP(NivelUCPPrevio);
}

Desbloquear puede invocarse desde rutina de interrupción (p.e. del terminal) o desde llamada (p.e. subir un semáforo)

Monografias.com

C. de contexto voluntario
Proceso en modo usuario invoca llamada con posible bloqueo
sis_llamada_X () {
………
Si (condición_1) Bloquear(cola de evento 1);
……… ? Cuando se desbloquee seguirá por aquí
………
Mientras ( ! condición_2)
Bloquear(cola de evento 2);
……… ? Cuando se desbloquee y se cumpla la
condición seguirá por aquí
………
}

Monografias.com

C. de contexto involuntario
Rutina de int. o llamada puede desbloquear proceso más importante o indicar que proceso actual ha consumido su turno
Situación puede ocurrir dentro de anidamiento de interrup.
Hay que esperar a que terminen
Puede estar activa una llamada al sistema
Mayoría de SS.OO. esperan a que termine
Véase "sincronización dentro del S.O."
Necesidad de diferir c. contexto hasta terminar trabajo de S.O.
Se indica que replanificación pendiente (need_resched en Linux)
Se activa interrupción software
Si UCP no tiene int. SW, se puede simular por software
Cuando termina actividad del S.O. (justo antes de volver proceso a modo usuario) se trata int. SW que realiza c. contexto

Monografias.com

C. c. involuntario por desbloqueo
Llamada o rutina de int. que causa desbloqueo
rutina_X () {
………
Si (condición) Desbloquear(cola de evento);
Si proceso desbloqueado más prioridad que actual {
replanificación_pendiente = verdadero;
Activar interrupción SW;
}
………
}
Int. SW se tratará cuando acabe rutina_X y otras rutinas del S.O. anidadas, si las hay

Monografias.com

C. c. involuntario por fin de rodaja
Interrupción de reloj que indica final de rodaja de p. actual
rutina_int_reloj () {
………
Si (–rodaja == 0) {
replanificación_pendiente = verdadero;
Activar interrupción SW;
}
………
}

Int. SW se tratará cuando acabe rutina_int_reloj y otras rutinas del S.O. anidadas, si las hay

Monografias.com

Replanificación
Tratamiento de int. SW
rutina_int_SW () {
………
Si (replanificación_pendiente) {
replanificación_pendiente = falso;
NivelUCPPrevio = FijarNivelIntUCP(máximo); /* Prohibir int. */
nuevo_proceso = planificador( );
Cambio_contexto(proceso_actual, nuevo_proceso);
FijarNivelIntUCP(NivelUCPPrevio); /* Por aquí continuará
cuando sea elegido de nuevo por planificador,
mientras habrán ejecutado otros procesos */
}
}

Monografias.com

Sincronización dentro del S.O. (1/2)
S.O. es un programa con alto grado de concurrencia:
Varias llamadas al sistema pueden ejecutarse concurrentemente
Puede activarse una interrupción mientras se sirve una llamada
Problemas de sincronización complejos:
Es muy difícil asegurar que un S.O. funciona correctamente
Ejemplos de problemas de sincronización:
Dos llamadas concurrentes para crear un proceso podrían elegir el mismo BCP para los dos nuevos procesos
Mientras una llamada manipula la cola de listos, se puede activar rutina de interrupción que también la cambie
Es necesario secciones críticas dentro del S.O.

Monografias.com

Sincronización dentro del S.O. (2/2)
Solución usada en la mayoría de sistemas (Linux, Windows, …):
Sincronización entre una llamada y una rutina de interrupción:
código de la llamada prohíbe interrupciones durante s. crítica
P.e. cuando manipula cola procesos listos (bloquear/desbloquear)
Sincronización entre llamadas concurrentes:
Limitar concurrencia dentro del S.O.
Mientras proceso en modo núcleo no c. contexto involuntario:
Se difieren a que termine trabajo en modo núcleo (int SW)
Se tratan int. mientras proc. en modo núcleo pero sin c. contexto
No hay concurrencia entre llamadas:
Más sencillo pero no apropiado para multiprocesadores o s. de tiempo real
Para dar soporte SMP (Symmetric MultiProcessing)
Se debe permitir paralelismo en llamadas
Se usan spin-locks y semáforos para sincronización

Monografias.com

Aplazamiento de operaciones de int.
Se debe minimizar duración de rutina de interrupción
Mientras prohibidas int. de ese nivel e inferiores
En rutina de int. se realizan operaciones urgentes
Resto de operaciones (menos urgentes y más largas) se difieren
Las realiza rutina que ejecuta con int. habilitadas
Se suele usar el mecanismo de int. SW
S.O. mantiene una lista de operaciones diferidas
Rutina de int. realiza operaciones urgentes, encola operaciones pendientes en la lista y activa interrupción SW
El tratamiento de int. SW realiza operaciones diferidas
En Linux: bottom halves y task queues
En Windows: DPCs (Deferred Procedure Calls)

Monografias.com

Tratamiento ampliado de int. SW
Tratamiento de int. SW
rutina_int_SW () {
Mientras (tareas pendientes)
Ejecutar siguiente tarea:
Si (replanificación_pendiente) {
Realiza c.c. involuntario (como se vio previamente)
}
}

Las tareas diferidas se ejecutan con ints. habilitadas, pero de manera asíncrona (p. actual no relacionado con ellas)
No deben llamar a bloquear ni acceder a mapa de proceso actual

Monografias.com

Creación de un proceso
Operaciones típicas para modelo convencional (Win32)
Buscar entrada libre en tabla de procesos
Leer fichero ejecutable
Crear mapa de memoria a partir del ejecutable
Crear pila inicial de usuario con el entorno del proceso
Crear pila del núcleo con dir. del punto de arranque del programa
Proceso comienza en modo núcleo haciendo RETI
Crear contexto inicial en BCP: Fijar valores iniciales de regs.
PC inicial=dirección de código de S.O. que contiene RETI
Estado = LISTO
Incluir BCP en cola de listos
En UNIX estas operaciones están repartidas entre:
FORK
EXEC

Monografias.com

Operaciones en la creación (UNIX)
Operaciones en FORK
Buscar entrada libre en tabla de procesos
Copiar BCP del padre
Duplicar mapa de memoria del padre (incluyendo pilas)
Estado = LISTO + Incluir BCP en cola de listos
Otras: actualización de filp, etc.
Operaciones en EXEC
Leer fichero ejecutable
Liberar mapa de memoria del proceso
Crear nuevo mapa de memoria a partir del ejecutable
Crear pila inicial de usuario con el entorno del proceso
Crear pila del núcleo con dir. del punto de arranque del programa
Crear contexto inicial en BCP: Fijar valores iniciales de regs.
PC inicial= dirección de código de S.O. que contiene RETI
Otras: Gestión de señales, SETUID, CLOSE_ON_EXEC, etc.

Monografias.com

Terminación de un proceso
Tipo de terminación:
Voluntaria: invoca llamada al sistema (EXIT en UNIX)
Error de ejecución: excepciones (división por cero, …)
Abortado: por un usuario u otro proceso
UNIX unifica los dos últimos mediante el uso de señales
¿Qué ocurre con procesos hijos?
En UNIX pasan a depender del proceso init
Influencia de la jerarquía:
UNIX: proceso terminado pasa a estado Zombie
Proceso no desaparece hasta que padre espera por él (WAIT)

Monografias.com

Operaciones implicadas en la terminación
Operaciones típicas:
liberar mapa de memoria
cerrar ficheros y liberar otros recursos
eliminar BCP de cola de procesos listos
liberar entrada de tabla de procesos
activa planificador y realiza c. de contexto al proceso elegido
En UNIX estas operaciones están repartidas entre:
EXIT: realiza la mayor parte de las operaciones
WAIT: libera entrada de tabla de procesos

Monografias.com

Threads
Concepto moderno de proceso:
Contiene múltiples flujos de ejecución (threads o procs. ligeros)
El proceso se corresponde con un entorno de ejecución:
Un mapa de memoria
Un conjunto de recursos asociados (ficheros, semáforos, …)
Un conjunto de threads
Proceso tiene un thread implícito: el flujo de ejecución inicial
Threads de un mismo proceso comparten:
Mapa de memoria (código, datos, zonas de mem. compartida, …)
Recursos asociados al proceso (ficheros, semáforos, …)
Cada thread tiene recursos propios:
Una pila, un estado y una copia del contenido de los regs.
Colas de listos y bloqueo contienen threads en vez de procesos

Monografias.com

Threads
BCP sólo contiene info. gral. del proceso + lista de threads
BCT (Bloque de Control de Thread):
Info. específica del thread (estado, copia de regs., pilas de usuario y núcleo, prioridad, puntero a BCP del proceso, etc.)
Creación de un thread:
Crear pila de usuario con argumentos
Crear pila del núcleo con dir. inicial del thread
Crear contexto inicial en BCT: Fijar valores iniciales de regs.
PC inicial=dirección de código de S.O. que contiene RETI
Incluir BCT en cola de listos
Ventajas del uso de threads vs. procesos convencionales:
Permiten expresar concurrencia "ligera" y fuertemente acoplada
Ligera: C. de contexto más rápido
Fuertemente acoplada: Mayor grado de compartición

Monografias.com

Threads de biblioteca
Threads creados por biblioteca: S.O. no conoce su existencia
Desventajas:
Llamada bloqueante de thread bloquea todo el proceso
No sacan provecho de múltiples procesadores
Ventaja: gestión de threads no implica al S.O.
Más ligeros
BCTs no consumen memoria del S.O.
Posibilidad de crear programas con nº muy elevado de threads
Existen esquemas híbridos (Solaris)

Monografias.com

Threads en Solaris
S.O. gestiona LWPs
Usuario crea threads de biblioteca
Biblioteca se encarga de correspondencia entre LWPs y threads
En cada momento un LWP ejecuta thread asociado
Biblioteca multiplexa threads entre LWPs
Nº de threads > Nº de LWPs
Cuando thread hace llamada bloqueante, LWP asociado se bloquea
Biblioteca puede crear nuevo LWP
Biblioteca ajusta dinámicamente nº de LWPs de manera que:
Sean suficientes para ejecutar threads activos
No gasten muchos recursos del S.O.

Monografias.com

Procesos de "peso variable"
En Linux y UNIX BSD no hay soporte directo de threads, pero:
Se permite especificar qué recursos comparten padre/hijo
Extensión de FORK
Peso variable: Más compartimiento ? más ligeros
En Linux, CLONE permite especificar si comparten:
Info. sobre ficheros (directorio actual, ficheros abiertos, …)
Info. de mapa de memoria
Info. de manejo de señales
BCP incluye punteros en vez de la propia información:
No hay BCTs, un BCP por proceso

Monografias.com

Planificación del procesador
¿Cómo seleccionar el "mejor" algoritmo?
Diferentes criterios (incluso contrapuestos): Buscar compromiso
Maximizar grado de utilización de UCP
Maximizar rendimiento: nº de procesos terminados/u. de tiempo
Minimizar tiempo de espera de cada proceso:
tiempo gastado esperando en cola de listos
Minimizar tiempo de respuesta de procesos interactivos:
tiempo desde que usuario realiza petición hasta que el proceso empieza a responder
Tendencia general: Favorecer trabajos más interactivos
Teoría de colas: servir primero peticiones más cortas
Racha de UCP de un proceso: tiempo que va a usar la UCP hasta que se bloquee
Mayoría de SS.OO. favorecen procs. con mucha E/S aunque no sean interactivos

Monografias.com

Escenarios de c. de contexto
Potenciales: Depende del algoritmo de planificación
Posibles escenarios:
1) Proceso en ejecución finaliza
2) Proceso realiza llamada al sistema que lo bloquea
3) Proceso realiza llamada al sistema que desbloquea proceso "más importante"
4) Interrupción desbloquea proceso "más importante"
5) Se crea un proceso "más importante" que el que está en ejecución
6) Interrupción de reloj marca fin de rodaja de ejecución
Dos tipos de algoritmos:
no expulsivos: sólo c. de contexto voluntarios (1 y 2)
expulsivos: además c. de contexto involuntarios (3, 4, 5 y/o 6)

Monografias.com

Algoritmos de planificación
FIFO (o FCFS)
Primero el más corto (SJF)
Prioridad
Round-Robin
Colas multinivel
Planificación por lotería
Planificación en Linux

Monografias.com

Algoritmo FIFO
Selección: Proceso que lleva más tiempo en cola de listos
Algoritmo no expulsivo:
sólo se activa cuando proceso en ejecución se bloquea o termina
Fácil de implementar:
Cola de listos gestionada en modo FIFO
No válido para procesos interactivos
Mal tiempo medio de espera en cola de listos:
Proceso con rachas de UCP más pequeñas puede tener que esperar
Mejor realizar antes "servicios" más cortos:
Algoritmo "primero el más corto" (SJF, Shortest Job First)

Monografias.com

Algoritmo SJF
Selección: Proceso en la cola de listos que tenga una próxima racha de UCP más corta
Versión no expulsiva:
sólo se activa cuando proceso en ejecución se bloquea o termina
Versión expulsiva:
también se activa cuando aparece un nuevo proceso en cola de listos (escenarios 3, 4 y 5)
Se favorecen los procesos con más E/S
¿Cómo se conoce a priori la duración de la próxima racha?
Estimaciones a partir de las anteriores
Puede producir inanición:
A un proceso con rachas muy largas se le "cuelan" todos

Monografias.com

Planificación por prioridad
Cada proceso tiene asignada una prioridad
Selección: Proceso en cola de listos que tenga mayor prioridad
SJF es de este tipo: Prioridad depende de tamaño de racha
Como SJF, existe versión no expulsiva y expulsiva
Las prioridades pueden ser estáticas o dinámicas
La prioridad de un proceso puede venir dada por factores:
externos: ¿quién es el usuario? ¿qué importancia asigna el usuario a este proceso (en UNIX nice)?
internos: comportamiento del proceso
Puede producir inanición:
A un proceso con baja prioridad se le "cuelan" todos
"Envejecimiento": Prioridad aumenta con el tiempo

Monografias.com

Algoritmo Round-Robin
Algoritmo FIFO + cuanto de tiempo
Cuando se asigna UCP a proceso se le da un cuanto de tiempo
Si lo gasta (racha>cuanto) es expulsado al final de cola de listos
Algoritmo expulsivo pero sólo con fin del cuanto (escenario 6)
Tiempo de respuesta acotado:
Si cuanto igual a C y N procesos listos:
proceso no esperará más de (N-1)*C u. de tiempo
Tamaño del cuanto:
grande: tiende a FIFO. Mal tiempo de respuesta
pequeño: demasiada sobrecarga
Debe ser grande con respecto al tiempo de c. de contexto
Típico: 10-100 milisegundos

Monografias.com

Colas multinivel
Modelo más general:
Cola de listos organizada en múltiples niveles
P.ej. Dependiendo de la interactividad de los procesos
Cada nivel puede tener su propio algoritmo:
P.ej. RR para niveles más interactivos y FIFO para los menos
Existe un algoritmo para seleccionar entre niveles:
P.ej. Por prioridades, mayor los niveles más interactivos
Realimentación:
Posibilidad de que los procesos cambien de nivel
Deben existir criterios de cambio de nivel:
P.ej. Mover de nivel un proceso si tiende a aumentar o disminuir su interactividad

Monografias.com

Planificación por lotería
Carácter aleatorio
Cada proceso posee un "billete" de lotería
Planificador: escoge billete y selecciona al premiado
Procesos "importantes" pueden tener varios billetes
Procesos cooperantes pueden intercambiarse billetes:
Proceso cliente una vez hecha la petición puede ceder sus billetes al servidor

Monografias.com

Planificación en Linux (1/2)
Cumple estándar POSIX: soporta clases de planificación
Clase de tiempo real (no crítico):
Proceso tiene asignada una prioridad
Dos clases de planificación:
FIFO: ejecuta hasta que se bloquea
Round-Robin: reparto UCP entre procesos de igual prioridad
Clase de tiempo compartido:
Procesos de esta clase sólo ejecutan si no hay de tiempo real
Cada proceso tiene una prioridad estática (nice)
Algoritmo basado en créditos
En cada interrup. de reloj: proceso en ejecución pierde un crédito
Si se queda sin créditos: se le revoca la UCP

Monografias.com

Planificación en Linux (2/2)
Planificador selecciona proceso con más créditos
Si ningún proceso tiene créditos -> Reasignación de créditos.
Reasignación de créditos: Para todo proceso del sistema:
créditos = créditos/2 + prioridad

Propiedades:
Compagina la "historia" del proceso con su prioridad
Procesos que usan mucha UCP pierden rápido sus créditos
Procesos con mucha E/S acumulan créditos
Se favorecen procesos interactivos

Partes: 1, 2
 Página anterior Volver al principio del trabajoPágina siguiente 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter