PROCESOS
SISTEMAS
OPERATIVOS
CONTENIDO
Procesos
 Comunicación entre procesos
 Problemas clásicos
 Planificación de un proceso
 Organización de procesos en MINIX

Multiprogramación
Un contador de programa
A
B
Cuatro contadores de programa
Cambio de
proceso
proceso
A
B
C
D
D
C
B
A
C
D
tiempo
(a)
(b)
(c)
Estados de un proceso
En ejecución
2
1
3
Bloqueado
Listo
4
1. El proceso se bloquea en la entrada
2. El planificador elige otro proceso
3. El planificador elige este proceso
4. La entrada se vuelve disponible
Estrato inferior de un
sistema operativo
El estrato inferior de un sistema operativo
estructurado por procesos maneja las
interrupciones y realiza la planificación. El resto
del sistema consta de procesos secuenciales
Procesos
0
1
...
Planificador
n-2
n-1
Campos de la tabla de
procesos
Manejo de los
procesos
Registros
Contador de programa
Hora de la siguiente alarma
Palabra de condición del
programa
Apuntadores de la lista de
espera de mensajes
Apuntador de pila
Bits de señal pendientes
Estado del proceso
Id del proceso
Hora a la que el proceso inició Diversos bits de señalización
Tiempo usado de la CPU
Tiempo del derivado de la CPU
tabla de procesos
(continuación)
Administración de la
memoria
Apuntador al segmento de texto
Apuntador al segmento de datos
Apuntador al segmento bss
Condición de la salida
Condición de la señal
Id del proceso
Proceso padre
Grupo de procesos
Uid real
Uid efectivo
Gid real
Gid efectivo
Mapas de bits de señales
Diversos bits de
señalización
tabla de procesos
(continuación)
Manejo de los archivos
Máscara UMASK
Directorio raíz
Directorio de trabajo
Descriptores de los archivos
Uid efectivo
Gid efectivo
Parámetros de llamada al
sistema
Diversos bits de señalización
Interrupciones
1. El hardware apila el contador de programa, etc.
2. El hardware carga el nuevo contador de programa a partir del
vector de interrupción.
3. El procedimiento del lenguaje ensamblador guarda registros.
4. El procedimiento del lenguaje ensamblador forma una nueva
pila.
5. El procedimiento C marca como listo el proceso de servicio de la
interrupción.
6. El planificador decide que proceso ejecutar después.
7. El procedimiento C regresa al código ensamblador.
8. El procedimiento del lenguaje ensamblador da inicio al proceso
corriente.
Condiciones de concurso
Dos procesos desean acceder la memoria
compartida al mismo tiempo.
Director de programas de
cola de impresión
Proceso A
4
abc
5
prog.c
6
prog.h
7
Proceso B
out = 4
in = 7
Secciones críticas
1. Nunca dos procesos pueden encontrarse
simultáneamente dentro de sus secciones
críticas.
2. No se hacen suposiciones acerca de las
velocidades relativas de los procesos o del
número de CPU.
3. Ningún proceso suspendido fuera de su
sección crítica debe bloquear a otros
procesos.
4. Nunca un proceso debe querer entrar en
forma arbitraria en su sección crítica.
Soluciones
Exclusión mutua con espera ocupada
Una forma de implementar la exclusión mutua es mantener ocupado
a un proceso en un ciclo de espera mientras otro este en su sección
crítica.
Desactivación de interrupciones
Si un proceso desactiva las interrupciones al entrar en su sección
crítica, se evita que otro proceso pueda interrumpirlo y de esta
manera se consigue la exclusión mutua. Esto puede ser conveniente
para procesos del kernel pero no es adecuado para procesos del
usuario.
Variable de cierre
Una posible solución es el uso de un cerrojo, este es una variable que
vale 0 si se puede entrar en la sección crítica y 1 si no se puede. Sin
embargo este esquema tiene el mismo defecto que el manejo de cola
de impresión que se vio antes.
Soluciones (continuación)
Alternación estricta
El siguiente código en C muestra una forma de
obtener exclusión mutua. El proceso 0 inspecciona
la variable turn y determina que es 0 entrando en
su sección crítica. A continuación el proceso 1
inspecciona turn y permanece en el ciclo cerrado,
una vez que termine el proceso 0 hará 1 la
variable turn y el proceso 1 podrá entrar en su
sección crítica. Este esquema tiene el defecto de
fallar si los procesos transcurren a muy diferentes
velocidades. En este caso se puede llegar a violar
el principio 3 que se expresó antes.
Alternación estricta
while (TRUE) {
}
while (TRUE) {
while(turn != 0)/* espera */;
critical_secction();
while(turn != 1)/* espera */;
critical_secction();
turn = 1;
turn = 0;
noncritical_section();
noncritical_section();
}
Solución de Peterson
#define FALSE
0
#define TRUE
1
#define N
2
/* número de procesos */
int turn;
/* a quién le toca? */
int interested[N];
/* todos los valores son inicialmente 0 (FALSE) */
enter_region(process)
int process;
/* número de proceso: 0 o 1 */
{
int other;
/* número del otro proceso */
other = 1 - process; /* opuesto del proceso */
interested[process] = TRUE;
/* demuestra su interés */
turn = process;
/* colocar señal */
while (turn == process && interested[other] == TRUE);/* espera ocupada */
}
leave_region(process)
int porcess;
/* proceso que sale de la región crítica */
{
interested[process] = FALSE; /* indicar salida de la región crítica */
}
Solución con instrucción
TSL
enter_region:
tsl
register,flag
;copia la bandera en el registro y
hace la bandera igual a 1
cmp
register,#0
jnz
enter_region ;repetir hasta que sea cero
ret
;¿fue cero la bandera?
;regresar al solicitante
leave_region:
move flag,#0
;almacena cero en la bandera
ret
;regresa al solicitante
Sleep (bloqueo) y wakeup
(desbloqueo)
Considérese una llamada sleep que hace que se
bloquee el solicitante, y otra wakeup que
desbloquea un proceso.
Considérese el problema del productor y el
consumidor (o problema del buffer limitado).
Dos procesos comparten un buffer, el productor
coloca información en el buffer y el consumidor,
la extrae.
El productor
#define N 100
Int cout = 0;
/* número de ranuras en el buffer */
/* número de elementos en el buffer */
producer()
{
while (TRUE){
produce_item();
/* repetir indefinidamente */
/* generar el siguiente elemento */
if (count == N) sleep();/* si el buffer está lleno, bloquearse */
enter_item();
/* colocar un elemento en el buffer */
count = count + 1;
/* incrementar conteo de elementos */
if (count == 1) wakeup(consumer);
}
}
/* ¿estaba vacío el buffer? */
El consumidor
consumer()
{
while (TRUE){
/* repetir indefinidamente */
if (count == 0) sleep();
/* si el buffer está vacío, bloquearse */
remove_item();
/* sacar el elemento del buffer */
count = count - 1;
/* disminuir conteo de elementos */
if (count == N - 1) wakeup(producer);
consume_item();
}
}
/* ¿estaba lleno el buffer? */
/* imprimir el elemento */
Semáforos
Un semáforo es una variable entera que cuenta
el número de desbloqueos guardados para uso
futuro. Las operaciones para manejo de semáforos
son down y up. La operación down verifica un
semáforo y si es mayor que 0 lo decrementa (es
decir, utiliza el desbloqueo almacenado) sino el
procesos se bloquea. La operación up incrementa
un semáforo. Si hay más de un proceso bloqueado
por ese semáforo, se elige uno al azar para
desbloquearlo, por tanto el semáforo seguirá
siendo 0 pero habrá un proceso menos bloqueado
en él.
Implantación de semáforos
#define N
100
/* número de ranuras en el buffer */
typedef int semaphore; /* los semáforos son un tipo especial de int */
semaphore mutex = 1; /* controla el acceso a la región crítica */
semaphore empty = N; /* cuenta ranuras vacías */
semaphore full = 0;
/* cuenta ranuras completas */
Productor con semáforos
producer()
{
int item;
while (TRUE){
/* repetir indefinidamente */
produce_item(&item); /* generar el siguiente elemento */
}
}
down(empty);
/* disminuir el conteo vacío */
down(mutex);
/* entrar en región crítica */
enter_item();
/* colocar un elemento en el buffer */
up(mutex);
/* salir de la región crítica */
up(full);
/* incrementar ranuras completas */
Consumidor con semáforos
consumer()
{
int item;
while (TRUE){
/* repetir indefinidamente */
produce_item(&item); /* generar el siguiente elemento */
down(full);
/* disminuir el conteo completo */
down(mutex);
/* entrar en región crítica */
remove_item();
/* tomad un elemento del buffer */
up(mutex);
/* salir de la región crítica */
up(empty);
/* incrementar ranuras vacías */
consume_item();
/* hacer algo con el elemento */
}
}
Transmisión de mensajes
Este método hace uso de dos primitivas, send y
recieve, las cuales son llamadas al sistema. La
sintaxis es
send(destination, &message);
y
recieve(source, &message);
El primero envía un mensaje a un destino y el
segundo recibe de una fuente. Si no está
disponible un mensaje el receptor se bloquea.
Productor con mensajes
#define N
100
/* número de ranuras en el buffer */
producer()
{
int item;
message m;
/* buffer de mensajes */
while (TRUE) {
produce_item(&item);/*genera algún elemento para colocarlo en el buffer */
receive(consumer, &m);
/* espera a que llegue uno vacío */
build_message(&m, item);/* construir un mensaje para ser enviado */
send(consumer, &m); /* enviar el elemento al consumidor */
}
}
Consumidor con mensajes
consumer()
{
int item, i;
message m;
for (i = 0;i < N; i++) send(producer, &m);
/* envía N vacíos */
while (TRUE) {
receive(producer, &m);/* toma el mensaje que contiene el elemento */
extract_item(&m, &item;/* sacar el elemento del mensaje */
consume_item(item); /* hacer algo con el elemento */
send(producer, &m);
}
}
/* devolver contestación vacía */
Buffer para mensajes
Buzones
S
Ranuras repletas
S
S
Ranuras repletas
Semáforos, uno por proceso
Ranuras vacias
2
Ranuras vacias
Lista de espera
de emisión
Lista de espera
de emisión
Lista de espera
de recepción
Lista de espera
de recepción
Mensaje
Mensaje
Mensaje
Mensaje
S
Mutex
El problema de los filósofos
comensales
Cinco filósofos están sentados a una mesa
circular.
Cada uno tiene un plato de espagueti
especialmente resbaladizo.
El espagueti es tan resbaladizo que un filósofo
necesita dos tenedores para comerlo.
Entre cada plato hay un tenedor.
Hora del almuerzo en el
departamento de filosofía
Solución obvia
#define N
5
{número de filósofos}
philosopher(i)
int i
{número del filósofo}
{
while(TRUE){
think();
/* el filósofo está meditando */
take_fork(i); /*toma el tenedor de la izquierda */
take_fork((i+1) % N); /*toma el tenedor de la derecha */
}
}
eat();
/* que rico espagueti */
put_fork(i);
/*coloca el tenedor de la izquierda */
put_fork((i+1) % N);
/*coloca el tenedor de la derecha */
Solución con semáforos
#define N
5
/* número de filósofos */
#define LEFT (i-1)%N /* número del vecino de la izquierda */
#define RIGHT (i-1)%N /* número del vecino de la derecha */
#define THINKING 0
/* el filósofo está meditando */
#define HUNGRY 1 /* el filósofo intenta tomar los tenedores */
#define EATING
2 /* el filósofo está comiendo */
typedef int semaphore; /* los semáforos son entero */
int state[N];
/* estados */
semaphore mutex = 1; /*exclusión mutua de regiones críticas
*/
semaphore s[N];
/* un semáforo por filósofo */
continuación
philosopher(i);
int i;
/* número de filósofo, de 0 a N-1 */
{
while(TRUE) { /* repetir indefinidamente */
think();
/* el filósofo está meditando */
take_forks(i);/* toma los dos tenedores o se bloquea */
eat();
/* que rico espagueti */
put_forks(i); /* coloca los tenedores */
}
}
continuación
take_forks(i)
int i;
/* número de filósofo, de 0 a N-1 */
{
down(mutex);
/* meter en región crítica */
state[i] = HUNGRY; /* registrar el hecho de que el filósofo i
tiene hambre */
test(i);
/* intentar tomar los tenedores */
up(mutex);
/* salir de la región crítica */
down(s[i]); /* bloquearse si no se tomaron los tenedores */
}
Continuación
put_forks(i)
int i;
/* número de filósofo, de 0 a N-1 */
{
down(mutex);
/* meter en región crítica */
state[i] = THINKING; /* el filósofo i termina de comer */
*/
*/
test(LEFT);/* ver si ahora puede comer el vecino de la izquierda
test(RIGHT);/* ver si ahora puede comer el vecino de la derecha
up(mutex);
}
/* salir de la región crítica */
Continuación
test(i)
int i;
/* número de filósofo, de 0 a N-1 */
{
if(state[i] == HUNGRY
state[RIGHT] != EATING) {
state[i] = EATING;
up(s[i]);
}
}
&&
state[LEFT]
!=
EATING
&&
El problema de los lectores
escritores
El problema de los lectores escritores modela el
acceso a una base de datos.
Imagínese una base de datos grande, como un
sistema de reservación de líneas aéreas, con
muchos procesos competidores que desean leerla
y escribirla.
Es aceptable hacer que múltiples procesos lean la
base de datos al mismo tiempo, pero si un
proceso se encuentra escribiendo la base de
datos, ningún otro proceso puede tener acceso a
la base de datos, ni los lectores.
Solución
reader()
{
while(TRUE){
down(mutex);
/* obtener acceso exclusivo a ‘rc */
rc = rc + 1;
/* ahora un lector más */
if(rc == 1) down(db); /* si éste es el primer lector… */
up(mutex);
/* liberar el acceso exclusivo a ‘rc’ */
read_data_base(); /* acceder datos */
down(mutex);
/* obtener acceso exclusivo a ‘rc’ */
rc = rc - 1;
/* ahora un lector menos */
if(rc == 0) up(db); /* si éste es el último lector… */
up(mutex);
/* liberar el acceso exclusivo a ‘rc’ */
use_data_base(); /* sección no crítica */
}
}
Continuación
writer()
{
while(TRUE){
think_up_data();
down(db);
/*obtener acceso exclusivo */
write_data_base();
up(db);
}
}
/* sección no crítica */
/* actualizar datos */
/* liberar el acceso exclusivo */
Planificación de un proceso
Requisitos de un buen algoritmo de planificación
1. Imparcialidad: asegura que cada proceso tenga la
parte que le corresponde de la CPU.
2. Eficiencia: mantener la CPU ocupada el 100% del
tiempo.
3. Tiempo de respuesta: minimizar
respuesta para usuarios interactivos.
el
tiempo
de
4. Cambio de posición: minimizar el tiempo que los
usuarios de un lote deban esperar para obtener la
salida.
5. Rendimiento: Maximizar el número de trabajos que se
procesan por hora.
Torneo
(a) Lista de procesos ejecutables. (b) Lista
de procesos ejecutables después de que se
termina la cantidad de B.
Proceso corriente
Siguiente proceso
B
F
D
(a)
Proceso corriente
G
A
F
D
G
(b)
A
B
Planificación por prioridad
Encabezados de
la lista de espera
Prioridad 4
Procesos ejecutables
(Prioridad más alta)
Prioridad 3
Prioridad 2
Prioridad 1
(Prioridad más baja)
El primer trabajo más corto
En la figura se muestran 4 trabajos A, B; C y D, con
tiempos de ejecución de 8, 4, 4, y 4 minutos,
respectivamente. Al ejecutarlos en ese orden, el tiempo de
cambio de A es de 8 minutos, de B es de 12 minutos, de C
es de 16 y de D es de 20 minutos, para hacer un promedio
de 14 minutos. En la figura 17 (b) se muestran los trabajos
en orden de primero el más corto, los tiempos de cambio de
posición son 4, 8 , 12 y 20, para hacer un promedio de 11
minutos.
8
4
4
4
4
4
4
8
A
B
C
D
B
C
D
A
(a)
(b)
Planificación de dos niveles
a,b,
c,d
e,f,
g,h
(a)
Procesos
en la
memoria principal
Procesos
en disco
e,f,
g,h
b,c
f,g
a,b,
c,d
a,d
e,h
(b)
(c)
Planificación en MINIX
MINIX se divide en 4 estratos. Los estratos tienen las siguientes
funciones:
Estrato1:
Captura interrupciones y trampas
•planificador
•manejo de comunicación entre procesos mediante mensajes
Estrato 2:
•Procesos de E/S, uno por dispositivo: disco, terminal, reloj,
sistema, etc.
Los estratos 1 y 2 forman el kernel del sistema.
continuación
Estrato 3:
•Manejador de memoria
•Sistema de archivos
La interpretación de la llamada al sistema ocurre en el nivel 3.
Estrato 4:
•Procesos
de
usuario:
aplicaciones, etc.
shell,
editores,
compiladores,
Diagrama de estratos de
MINIX
Estrato
4
3
2
1
Inic
Proceso
del usuario
Proceso
del usuario
Proceso
del usuario
Adiminstrador
de la memoria
Tarea
del disco
...
Sistema
de archivo
Tarea
tty
Tarea
del reloj
Tarea
del sistema
Manejo de los procesos
Procesos del usuario
Procesos del servidor
...
Tareas de E/S
Proceso de carga de MINIX
El proceso de carga de minix sigue los siguientes pasos:
1. Al encender se carga un pequeño programa llamado el
“cargador”.
2. El cargador coloca todo el sistema operativo en memoria
y transfiere el control a Init.
3. Init lee /etc/ttys para conocer las terminales e inicia un
proceso derivado/terminal por cada una de ellas.
4. El proceso derivado ejecuta /bin/login para esperar a que
alguien entre al sistema.
5. Después de entrar /bin/login ejecuta un shell
especificado en /etc/passwd (generalmente /bin/sh).
Mapa de memoria de MINIX
Memoria disponible
para programas
de usuario
minix/tools/init
minix/fs/fs
minix/mm/mm
Máximo de 640K
Comúnmente de 70K a 100K, según
cuántos buffers de hayan
incluido en el sistema de archivo
Inic
Sistema de archivo
Administrador de la memoria
40K
Tarea de la memoria
25K (según el número de tareas de E/S)
Tarea de la terminal
minix/kernel/kernel
Tarea del disco
Tarea del reloj
Manejo de los procesos
Vectores de
interrupción
1536 Inicio del kernel
No se utiliza
0
Comunicación
La comunicación se realiza por medio de mensajes. Existen
tres primitivas:
send(dest,&message);
- envía un mensaje a dest
receive(source,&message);
- recibe un mensaje de source
send_rec(src_dst,&message); - envía un mensaje a src_dst y
espera respuesta del mismo
Los procesos pueden enviar y recibir mensajes de procesos
o tareas en su mismo estrato y de aquellos que estén en el
estrato localizado directamente debajo de él.
Cuando un proceso envía un mensaje y el destino no lo
espera, el emisor se bloquea hasta que el destino efectúa
un recieve (principio de cita).
Planificación en minix
MINIX utiliza una lista de espera para cada nivel
de prioridad de proceso.
En cada nivel se sigue el algoritmo del torneo.
La cantidad que se le asigna a cada proceso es de
100 ms.
Descargar

Document