Procesos e Hilos

Grupo ARCOS
Universidad Carlos III de Madrid
Lección 3
Procesos, hilos y planificación
Diseño de Sistemas Operativos

Grado en Ingeniería Informática
Lecturas recomendadas
Base Recomendada
1. Carretero 2007: 1. Tanenbaum 2006(en):

1. Cap.3 1. Cap.2
2. Stallings 2005:
1. Parte dos. Procesos.
3. Silberschatz 2006:
1. Cap.2
2 ARCOS @ UC3M
Alejandro Calderón Mateos
A recordar…
1. Estudiar la teoría asociada.

 Estudiar el material asociado a la bibliografía:
las transparencias solo no son suficiente.
 Crear cuestiones con sus respuestas y justificación.
2. Repasar lo visto en clase.

 Realizar el cuaderno de prácticas progresivamente.
3. Ejercitar las competencias.

 Realizar las prácticas progresivamente.
 Realizar todos los ejercicios posibles.
3 ARCOS @ UC3M
Contenidos
 Introducción
 Concepto de proceso
 Modelo ofrecido
 Implicaciones en el sistema operativo
 Aspectos de diseño e implementación

 Estructuras de datos
 Multiprogramación
 Multitarea
 Planificador
 Llamadas al sistema
4 ARCOS @ UC3M
Contenidos
 Introducción
 Modelo ofrecido

 Multitarea
 Planificador
5 ARCOS @ UC3M
Introducción
Proceso  Modelo ofrecido
 Implicaciones en S.O.
kernel
6 ARCOS @ UC3M
Introducción
Proceso
7 ARCOS @ UC3M
Concepto de proceso 2
1
App 1
CPU
Memoria Disco
 Proceso
 Programa en ejecución
 Unidad de procesamiento gestionada por el S.O.
8 ARCOS @ UC3M
Hilo (thread): Concepto
 Un proceso puede tener múltiples flujos de ejecución
 thread: cada flujo de ejecución de un proceso
 thread = hilo = proceso ligero
 Aspectos de la relación entre hilos de un proceso:

 Threads de un mismo proceso comparten:
 Mapa de memoria y regiones compartidas código código
 Otros recursos asociados al proceso datos datos
 Cada thread tiene en propiedad: ficheros ficheros
 Regiones de memoria especificas registros regs. regs.
 thread stack pila pila pila
 Contenido de los registros de la CPU
single-threaded multithreaded
9 ARCOS @ UC3M
Hilo (thread): Estrategias de implementación
 Thread de biblioteca
 Implementado en una biblioteca de espacio de usuario
para ofrecer la semántica a las aplicaciones
 Usado cuando el sistema operativo no ofrece la abstracción de hilo
 [I] Llamada bloqueante de un hilo bloquea todo el proceso
 [V] Gestión de hilo no implica al S.O.: más ligeros, más hilos, etc.
 Thread de sistema
 Disponible como abstracción en el núcleo (espacio de kernel) y
ofrecida la gestión a través de un conjunto de llamadas al sistema
 [I] Sobrecarga al sistema operativo la elevada creación de hilos
 [V] Mayor paralelismo, si un hilo se bloquea otro puede continuar
sin necesidad de un pesado cambio de contexto de proceso
(cambio de contexto de un hilo es más ligero)
10 ARCOS @ UC3M
Hilo (thread): Estrategias de implementación (2)
Hilos de Espacio Espacio Biblioteca Espacio

de usuario de usuario de hilos de usuario
biblioteca
Espacio Espacio Espacio
de núcleo de núcleo de núcleo
P P P
(a) Nivel de usuario puro (N-1) (b) Nivel de núcleo puro (1-1) (c) Combinado (N-M)
Hilo a nivel de usuario Hilo a nivel de núcleo P Proceso
11 ARCOS @ UC3M
Introducción
12 ARCOS @ UC3M
Modelo ofrecido
CPU
Memoria Disco
 Recursos asociados
 Zonas de memoria
 Al menos: código, datos y pila
 Archivos abiertos
 Señales
13 ARCOS @ UC3M
App2
App1
Modelo ofrecido App3
App 1
CPU
App 2
App 3
Memoria
 Tener varias aplicaciones en memoria
 Si una aplicación se bloquea por E/S, entonces
se ejecuta mientras otra hasta que quede bloqueada
 Cambio de contexto voluntario (C.C.V.)
 Eficiencia en el uso del procesador
 Grado de multiprogramación = número de aplicaciones en RAM
14 ARCOS @ UC3M
Modelo ofrecido
App 1
CPU
App 2
App 3
Memoria
 Protección / Compartición
 El espacio de direcciones privado por aplicación, pero
 Posibilidad de comunicar datos entre dos aplicaciones
 Paso de mensajes
 Compartición de memoria
15 ARCOS @ UC3M
App0
Modelo ofrecido
App 1
CPU
App 2
App1 App2
App 3
App3
Memoria
 Jerarquía de procesos
 Creación de proceso
 Como copia de otro proceso existente
 A partir del programa en disco
 Como proceso en el arranque
 Grupo de procesos que comparten mismo tratamiento
16 ARCOS @ UC3M
App1
Modelo ofrecido
App2 App3
App 1
CPU
App 2
App 3
Memoria
 Multitarea
 Cada proceso se ejecuta un quantum de tiempo (Ej.: 5 ms) y
se rota el turno para ejecutar procesos no bloqueados
 Cambio de contexto involuntario (C.C.I.)
 Reparto del uso del procesador
 Parece que todo se ejecuta a la vez
17 ARCOS @ UC3M
App1
Modelo ofrecido
App2 App3
App 1
CPU
App 2
App 3
Memoria
 Multiproceso
 Se dispone de varios procesadores (multicore/multiprocesador)
 Además del reparto de cada CPU (multitarea)
hay paralelismo real entre varias tareas (tantas como
procesadores)
 Se suele usar planificador y estructuras de datos separadas por
procesador con algún mecanismo de equilibrio de carga
18 ARCOS @ UC3M
Introducción
kernel
19 ARCOS @ UC3M
Implicaciones en el sistema operativo
1. Estructuras de datos
De los recursos utilizados

 Zonas de memoria:
 Al menos:
Para la planificación de la CPU
 código, datos y pila
 Estado de ejecución  Zonas compartidas
 Contexto  Archivos abiertos

 Información necesaria para guardar  Señales
el estado del proceso y poder restaurar  Cola de mensajes
más tarde para continuar la ejecución.
 de recepción
 Principalmente: registros de la CPU
 Locks y conditions
 Quantum restante  …
 Prioridad
 Afinidad
 Evitar saltar de un core a otro core
(continuar en el mismo)  Relación de parentesco
Más
 Conjuntos de procesos
 Procesos de una sesión
 ...
20 ARCOS @ UC3M
1. Estructuras de datos
kernel
21 ARCOS @ UC3M
2. Funciones: de gestión internas
 Estados y
cambios de contexto
 Colas de procesos
 Planificación
 Etc.
kernel
22 ARCOS @ UC3M
2. Funciones: de servicio
 Destrucción de proceso
 Cambio de imagen
 Espera por el fin de otro proceso
 Etc.
 Estados y
cambios de contexto
 Planificación
 Etc.
kernel
23 ARCOS @ UC3M
2. Funciones: API de servicio
 fork, exit, exec, wait, …
 pthread_create, pthread…
 Etc.
 Estados y
cambios de contexto
 Planificación
 Etc.
kernel
24 ARCOS @ UC3M
Introducción
resumen
 …
 …
 …
 …
 …
 …
kernel
25 ARCOS @ UC3M
Introducción
aspectos de diseño e implementación
 Modelo ofrecido
Proceso Análisis de requisitos
Diseño, implementación,
 …
implantación y pruebas
 …
 …
 …
 …
 …
kernel
26 ARCOS @ UC3M
Introducción
aspectos de diseño e implementación
 Modelo ofrecido
Análisis de requisitos
Diseño, implementación,
implantación y pruebas
Información Funciones
Requisitos
(estructuras de datos) (internas, servicio y API)
Recursos
Multiprogramación
Comunicación
Multiproceso
27 ARCOS @ UC3M
Contenidos
 Introducción
 Modelo ofrecido

 Multitarea
 Planificador
28 ARCOS @ UC3M
Información para cumplir con los requisitos…
Requisitos Información (en estructuras de datos) Funciones (internas, servicio y API)
• Zonas de memoria (código, datos y pila) • Diversas funciones internas

Recursos • Archivos abiertos • Diversas funciones de servicio para
• Señales activas memoria, ficheros, etc.
• Estado de ejecución • Int. hw/sw de dispositivos

Multiprogramación • Contexto: registros de CPU… • Planificador
• Lista de procesos • Crear/Destruir/Planificar proceso
• Paso de mensajes • Envío/Recepción mensaje y gestión
o Protección / • Cola de mensajes de recepción de la cola de mensaje
Compartición • Memoria compartida • API concurrencia y gestión de
• Zonas, locks y conditions estructuras de datos
• Relación de parentesco • Clonar/Cambiar imagen de proceso
o Jerarquía de
• Conjuntos de procesos relacionados • Asociar procesos e indicar proceso
procesos
• Procesos de una misma sesión representante
• Int. hw/sw de reloj
• Quantum restante
Multitarea • Planificador
• Prioridad
• Crear/Destruir/Planificar proceso
Multiproceso • Afinidad • Planificador
29 ARCOS @ UC3M
Información en el sistema operativo
App 1
App 2
Tabla de procesos
App 3 Tabla de memoria
Tabla de E/S
Tabla de ficheros
Tablas del S.O.
Memoria física
30 ARCOS @ UC3M
Información para un proceso
App 1 Tabla de procesos
App 2
BCP BCP BCP …
(1) (2) (3)
Tabla de procesos
App 3 Tabla de memoria
Tabla de E/S
Tabla de ficheros
Tablas del S.O.
Memoria física
31 ARCOS @ UC3M
BCP: entrada de la tabla de procesos
 Gestión de proceso
 Registros generales
Tabla de procesos
estado
 Contador de programa
 Registro de estado
 Puntero de pila
BCP BCP BCP …
 Identificador del proceso (1) (2) (3)
Proceso padre
Id.
 Grupo de proceso
 Prioridad  Process Control Block (PCB / BCP)
 Parámetros del planificador  Estructura de datos con la información necesaria para
gestionar un proceso en particular
gestión
 Señales
 Manifestación de un proceso en el kernel
 Instante inicio de ejecución
 Tiempo de uso de CPU
 Thread Control Block (TCB / BCT)
 Tiempo hasta siguiente alarma
 Similar al BCP para cada hilo de un proceso
32 ARCOS @ UC3M
BCP: entrada de la tabla de procesos
 Gestión de proceso
 Registros generales
Tabla de procesos
estado
 Contador de programa
 Registro de estado
 Puntero de pila
BCP BCP BCP …
 Identificador del proceso (1) (2) (3)
Proceso padre
Id.
 Prioridad  Process Identification (PID)
 Parámetros del planificador  Identificador de cara a los usuarios
gestión
 Señales  Número positivo de 16 bits (32767)

dinámicamente asignado, reusado no de forma inmediata
 Instante inicio de ejecución
 Address of process descriptor (APD)
 Identificación dentro del kernel
 Existe mecanismo PID -> APD (Ej.: hash)
33 ARCOS @ UC3M
Dónde: información del proceso
 La información de cada proceso está en el BCP…

 Información fuera del BCP: Tabla de procesos
 Por razones de eficiencia

 Para compartir información entre procesos
BCP BCP BCP …
(1) (2) (3)
Tabla de procesos
Tabla de memora
Tabla de E/S
Tabla de ficheros
 Ejemplos:
 Tabla de segmentos y páginas de memoria
 Tabla de punteros de posición de ficheros
 Lista de peticiones a dispositivos
34 ARCOS @ UC3M
Dónde: información del proceso
 Tabla de punteros de
posición de ficheros:
BCP 4
Tabla de
BCP 7
Tabla de
BCP 23
Tabla de
 Describe la posición de
ficheros
0 23
ficheros
0 23
ficheros
0 54
lectura/escritura de los ficheros
fd 1 4563
2 56
fd 1 4563
2 56
fd 1 633
2 5368
abiertos
3 4 3 4 3 33
4 678 4 0 4 2  La compartición de estado del
fichero entre procesos obliga a
IDFF PP que sea externa al BCP
1 24456 0
2
3
34512
28
2345
5566
 El BCP contiene el índice del
4 34512 10000 elemento de la tabla que
contiene la información del
fichero abierto: el i-nodo y la
posición de lectura/escritura.
35 Sistemas operativos: una visión aplicada ARCOS @ UC3M

Información del proceso
 Gestión de proceso  Gestión de ficheros  Gestión de memoria

 Registros generales  Directorio raíz  Puntero al segmento de código
estado
 Contador de programa  Directorio de trabajo  Puntero al segmento de datos

 Registro de estado  Descriptores de ficheros  Puntero al segmento de pila
 Puntero de pila  Identificador de usuario
 Identificador del proceso  Identificador de grupo
Proceso padre
Id.
 Prioridad
 Parámetros del planificador
gestión
 Señales
 Instante inicio de ejecución BCP

36 ARCOS @ UC3M
Información del proceso
Linux
state (runability)
stack
stack + thread_info (low_level scheduling)
scheduling info
debugging support
state (exit status) mm_struct (memory)
pid and tgid
mm fs_struct (directory name space)
process hierarchy info
pid hash table
credentials files_struct (Open Files)
fs
files
tty_struct (communications)
signal
sighand signal_struct (signals)
…
sighand_struct (signal handers)
task_struct (Process Descriptor)
37 Understanding the Linux Kernel (O'Really) ARCOS @ UC3M

http://www.eecs.harvard.edu/~margo/cs161/videos/sched.h.html Alejandro Calderón Mateos
Contenidos
 Introducción
 Modelo ofrecido

 Multitarea
 Planificador
38 ARCOS @ UC3M
Multiprogramación (datos y funciones)


o Jerarquía de
procesos
• Prioridad
39 ARCOS @ UC3M
Multiprogramación
Memoria App2
App1
App3
App 1
App 2
se ejecuta otra (hasta que quede bloqueada)
App 3
40 ARCOS @ UC3M
Multiprogramación (datos)
Estados de un proceso (c.c.v.)
BCP5
finalización
Running
creación fin E/S

Ready Blocked
Memoria App2
App1
App3
App 1
App 2
App 3
41 ARCOS @ UC3M
Estados de un proceso (c.c.v.)
BCP5
finalización
Running
creación fin E/S

Ready Blocked
 En ejecución: con CPU asignada

 Listo para ejecutar: no procesador disponible para él
 Bloqueado: esperando un evento
 Suspendido y listo: expulsado pero listo para ejecutar
 Suspendido y bloqueado: expulsado y esperando evento
42 ARCOS @ UC3M
Lista/Colas de procesos (c.c.v.)
BCP5
finalización
Running
creación fin E/S

Ready Blocked
BCP7 BCP2 BCP1 BCP3 BCP4
Memoria App2
App1
App3
App 1
App 2
App 3
43 ARCOS @ UC3M
Lista/Colas de procesos (c.c.v.)
BCP5
finalización
Running
creación fin E/S

Ready Blocked
 Cola de listos: procesos esperando a ejecutar en CPU

 Cola de bloqueados por recurso: procesos a la espera de
finalizar una petición bloqueante al recurso asociado
o Un proceso solo puede estar en una cola (como mucho)
44 ARCOS @ UC3M
Implementación de las colas de procesos
Proceso 0 Proceso 1 Proceso n
Estado del proceso Estado del proceso Estado del proceso
Registros Registros Registros
…
Límites de memoria Límites de memoria Límites de memoria
Tabla de procesos
Lista de ficheros abiertos Lista de ficheros abiertos Lista de ficheros abiertos
... ... ...
cabeza
Cola de listos cola
cabeza
Cola de … cola
 Cola de listos: procesos esperando a ejecutar en CPU

 Cola de bloqueados por recurso: procesos a la espera de
finalizar una petición bloqueante al recurso asociado
o Un proceso solo puede estar en una cola (como mucho)
45 ARCOS @ UC3M
Contexto de un proceso
finalización
Running
creación fin E/S

Ready Blocked
Memoria App2
App1
App3
App 1
App 2
App 3
46 ARCOS @ UC3M
Contexto de un proceso
finalización
Running
creación fin E/S

Ready Blocked
 Registros generales: PC, RE, etc.

 Registros específicos: Registros de coma flotante, etc.
 Referencias a recursos: puntero a código, datos, etc.
47 ARCOS @ UC3M
Multiprogramación: ejemplo de ejecución
proceso P0 sistema operativo proceso P1
ejecutando
listo
48 ARCOS @ UC3M
ejecutando
1 llamada bloqueante listo
49 ARCOS @ UC3M
ejecutando
salvar estado en el BCP0 listo
50 ARCOS @ UC3M
ejecutando
bloqueado
51 ARCOS @ UC3M
ejecutando
bloqueado
cargar estado en el BCP1
ejecutando
52 ARCOS @ UC3M
ejecutando
bloqueado
ejecutando
2 interrupción
listo
53 ARCOS @ UC3M
ejecutando
bloqueado
ejecutando
listo 3 llamada bloqueante

(petición de lectura
a disco, esperar en
una pipe, etc.)
54 ARCOS @ UC3M
ejecutando
bloqueado
ejecutando
salvar estado en el BCP1

listo
55 ARCOS @ UC3M
ejecutando
bloqueado
ejecutando

listo
cargar estado en el BCP0 bloqueado
ejecutando
56 ARCOS @ UC3M
ejecutando
1 llamada bloqueante
bloqueado
ejecutando
2 interrupción

listo 3 llamada bloqueante
cargar estado en el BCP0 bloqueado
ejecutando
57 ARCOS @ UC3M
1
Pseudocódigo de ejemplo (P0)
planificador()
• return extraer(CPU_Listo);
Teclado_LeerTecla() Running
• Si (no hay tecla) Blocked

• procesoActual->estado = BLOQUEADO;
• Insertar(Teclado_Procesos, procesoActual); BCP1 BCP3
• proceso = procesoActual;
• procesoActual = planificador();
salvar estado en BCP0 • procesoActual->estado = EJECUCION;
• cambio_contexto( &(proceso->contexto),
&(procesoActual->contexto));
cargar estado en BCP1
• return extraer(Teclado_Teclas) ;
BCP7 BCP2
58 ARCOS @ UC3M
2
Teclado_Interrupción_Hardware ()
• T = in (TECLADO_HW_ID);
• proceso = insertar (T, Teclado_Teclas);
• Insertar (Teclado_interrupción_software);
• Activar_Interrupción_Software();
Teclado_Interrupción_Software ()
• proceso = primero (Teclado_Procesos);
• SI (proceso != NULL)
• eliminar (Teclado_Procesos);
• proceso->estado = LISTO; fin E/S
• insertar (CPU_Listos, proceso); Ready Blocked
• return ok; BCP7 BCP2
59 ARCOS @ UC3M
2
Teclado_Interrupción_Hardware ()
• T = in (TECLADO_HW_ID);
• proceso = insertar (T, Teclado_Teclas);
• Insertar (Teclado_interrupción_software);
Teclado_Interrupción_Software ()
• proceso = primero (Teclado_Procesos);
• SI (proceso != NULL)
• eliminar (Teclado_Procesos);
• proceso->estado = LISTO; fin E/S
• insertar (CPU_Listos, proceso); Ready Blocked
• return ok; BCP7 BCP2
• Un proceso solo puede estar en una cola (como mucho):

[correcto] eliminar + insertar
[incorrecto] insertar + eliminar
60 ARCOS @ UC3M
3
planificador()
Teclado_LeerBloqueDisco() Running
• Si (no hay bloque en caché) Blocked

• Insertar(Disco_Procesos, procesoActual); BCP1 BCP3
salvar estado en BCP1 • procesoActual->estado = EJECUCION;
• return extraer(Disco_caché, bloque) ; BCP7 BCP2
61 ARCOS @ UC3M
3
Teclado_LeerTecla()
• Si (no hay tecla)
• Insertar(Teclado_Procesos, procesoActual);
• procesoActual->estado = EJECUCION;
• return extraer(Teclado_Teclas) ;
62 ARCOS @ UC3M
El reloj: tratamiento con solo c.c.v.
proceso P0 sistema operativo
ejecutando
Reloj_Interrupción_Hardware ()
interrupción o llamada al sistema
• Ticks++
• Ticks++
• Ticks++
63 ARCOS @ UC3M
Colas/Listas de procesos
Linux
"sched.h"
…
task_struct init_task
"current.h"
task_struct *current
"sched.c"
struct rq runqueues
…
"wait.h"
DEFINE_WAIT(wq1)
…
64 ARCOS @ UC3M
Colas/Listas de procesos
Linux
a. atomic_t is_blocking_mode = ATOMIC_INIT(0);
DECLARE_WAIT_QUEUE_HEAD(dso_wq1);
sched.h sched.h
init_task …
b. atomic_set(&is_blocking_mode,
task_struct 0);
task_struct
wait_event_interruptible(dso_wq1,
(atomic_read(&is_blocking_mode) == 1));
current
c. atomic_set(&is_blocking_mode, 1);
wake_up_interruptible(&dso_wq1);
kernel/sched.c
runqueues
struct rq
"wait.h"
DEFINE_WAIT(wq1)
…
65 ARCOS @ UC3M
Colas/Listas de• procesos
DEFINE_WAIT, DECLARE_WAIT_QUEUE_HEAD(wq)
• wq->flags &= ~WQ_FLAG_EXCLUSIVE
Linux
wq->flags |= WQ_FLAG_EXCLUSIVE
a. atomic_t is_blocking_mode = ATOMIC_INIT(0);
DECLARE_WAIT_QUEUE_HEAD(dso_wq1);
sched.h sched.h
init_task …
b. atomic_set(&is_blocking_mode,
task_struct 0);
task_struct
wait_event_interruptible(dso_wq1,
(atomic_read(&is_blocking_mode) == 1));
current
c. atomic_set(&is_blocking_mode, 1);
wake_up_interruptible(&dso_wq1);
kernel/sched.c
runqueues
struct rq
wait_event, wait_event_interruptible (wq, condition)
…
wait_event_timeout,
wait_event_interruptible_timeout (wq, condition, timeout)
"wait.h"
wake_up, wake_up_nr,
DEFINE_WAIT(wq1)wake_up_all, wake_up_interruptible,
wake_up_interruptible_nr, wake_up_interruptible_all,
…
wake_up_interruptible_sync, wake_up_locked(queue)
66 ARCOS @ UC3M
Contenidos
 Introducción
 Modelo ofrecido

 Multitarea y multiproceso
 Planificador
67 ARCOS @ UC3M
Multitarea (datos y funciones)


o Jerarquía de
procesos
• Prioridad
68 ARCOS @ UC3M
Estados de un proceso
finalización
Running
C.C.V.
creación fin E/S
Ready Blocked
finalización
Running
C.C.V. + C.C.I.
creación fin E/S
Ready Blocked
69 ARCOS @ UC3M
El reloj: tratamiento con c.c.v. + c.c.i.
ejecutando

listo cargar estado en el BCP1
ejecutando
70 ARCOS @ UC3M
• Ticks++;
• Insertar (Reloj_Planificar_Rodaja);
Reloj_Planificar_Rodaja ()
Running
• pActual->rodaja = pActual->rodaja - 1; Ready
• SI (pActual->rodaja == 0)
BCP7 BCP2
• pActual->estado = LISTO;
planificador() • insertar (CPU_Listos, pActual);
• proceso = pActual;
• pActual = planificador();
salvar estado en BCP0 • pActual->estado = EJECUCIÓN;
• cambio_contexto(
&(proceso->contexto),
&(pActual->contexto));
BCP2 BCP5
• return ok;
71 ARCOS @ UC3M
Linux
Stopped
Signal Signal
Termination
Creation
Ready Scheduling Executing Zombie
Uninterruptible
Event Event
Interruptible
72 ARCOS @ UC3M
Windows 2000
73 ARCOS @ UC3M
Temporización
Linux
• void process_timeout (unsigned long __data) {

wake_up_process((task_t *)__data);
}
• timespec t;
unsigned long expire;
struct timer_list timer;
"timer.h"
timer_list …
…
74 Understanding the Linux kernel (250) ARCOS @ UC3M

Temporización
Linux
• expire = timespec_to_jiffies(&t) + 1 + jiffies;
init_timer(&timer);
timer.expires = expire;
timer.data = (unsigned long) current;
timer.function = process_timeout;
add_timer(&timer);
current->state = TASK_INTERRUPTIBLE;
schedule(); /* ejecutar mientras otro proceso */
del_singleshot_timer_sync(&timer);
"timer.h"
timer_list …
…
75 Understanding the Linux kernel (250) ARCOS @ UC3M

Multiproceso


o Jerarquía de
procesos
• Prioridad
76 ARCOS @ UC3M
Multiproceso
 Afinidad:
 Los procesos tienen ‘afinidad’ (affinity) a una CPU: «mejor volver a la misma CPU»
 Simetría:
 Los procesos se ejecutan en la CPU que tienen unas capacidades específicas
77 ARCOS @ UC3M
Contenidos
 Introducción
 Modelo ofrecido

 Multitarea
 Planificador
78 ARCOS @ UC3M
Planificación de procesos
niveles de planificación
finalización
 A largo plazo
Running
 añadir procesos a ejecutar
 Invocado con baja frecuencia
 puede ser algo lento
creación fin E/S
Ready Blocked  A medio plazo
 añadir procesos a RAM
Planificación a corto plazo
 A corto plazo
Ready & Blocked &  qué proceso tiene la UCP
Suspend Suspend
 Invocado frecuentemente
Planificación a medio plazo  rápido
Planificación a largo plazo

Planificación de procesos (a corto plazo)
 Planificador: cabeza
BCP7 BCP2
Selecciona el proceso a ser cola registros registros
… …
ejecutado entre los que están
listos para ejecutar
 Activador: Running
finalización
Da control al proceso que el

planificador ha seleccionado
creación fin E/S
(cambio de contexto - restaurar) Ready Blocked
Ready & Blocked &

Suspend Suspend
80 ARCOS @ UC3M
objetivos de los algoritmos de planificación (según sistema)
 Todos los sistemas:

 Equitativo – ofrece a cada proceso una parte equitativa de la CPU
 Expeditivo – cumplimiento de la política emprendida de reparto
 Balanceado – mantener todas las partes del sistema ocupadas
 Sistemas batch:
 Productividad – maximizar el número de trabajos por hora
 Tiempo de espera – minimizar el tiempo entre emisión y terminación del trabajo
 Uso de CPU – mantener la CPU ocupada todo el tiempo
 Sistemas Interactivos:
 Tiempo de respuesta – responder a las peticiones lo más rápido posible
 Ajustado – satisfacer las expectaciones de los usuarios
 Sistemas de tiempo real:

 Cumplimiento de plazos – evitar la pérdida de datos
 Predecible – evitar la degradación de calidad en sistemas multimedia
81 ARCOS @ UC3M
características de los algoritmos de planificación (1/2)
 Preemption:
 Sin expulsión:
 El proceso conserva la CPU mientras desee.
 Cambios de contexto voluntarios (C.C.V.)
 [v/i] Un proceso puede bloquear al resto pero solución fácil a la compartición de recursos
 Windows 3.1, Windows 95 (16 bits), NetWare, MacOS 9.x.
 Con expulsión:
 Exige un reloj que interrumpe periódicamente:
 cuando pasa el quantum de un proceso se cambia a otro
 (Se añade) Cambios de contexto involuntarios (C.C.I.)
 [v/i] Mejora la interactividad pero precisa de mecanismos para condiciones de carrera
 AmigaOS (1985),Windows NT-XP-Vista-7, Linux, BSD, MacOS X
82 ARCOS @ UC3M
características de los algoritmos de planificación (2/2)
 Clasificación de elementos en las colas:
 Por prioridad A B C D
 Por tipo
 CPU-bound (más ‘rachas’ –burst– de tiempo usando CPU)
 IO-bound (más ‘rachas’ de tiempo esperando E/S)
 CPU-aware:
 Afinidad:
 Los procesos tienen ‘afinidad’ (affinity) a una CPU: «mejor volver a la misma CPU»
 Simetría:
 Los procesos se ejecutan en la CPU que tienen unas capacidades específicas a dicha CPU
83 ARCOS @ UC3M
principales algoritmos de planificación (1/3)
 Cíclico o Round Robin: • Grande:

• menos cambios de contexto
• Peor reactividad
 Asignación rotatoria del procesador
 Se asigna un tiempo máximo de procesador (rodaja o quantum)
A B C D B C D A
 Equitativo pero interactivo:

 Mejor por UID que por proceso
 En Linux:
 Aparición en 11/2010 de un parche para el kernel que automáticamente crea
un grupo de tareas por TTY para mejorar la interactividad en sistemas cargados.
 Son 224 líneas de código que modifican el planificador del kernel que en las primeras pruebas
muestra que la latencia media cae a una 60 veces (1/60).
 Uso en sistemas de tiempo compartido
84 http://www.phoronix.com/scan.php?page=article&item=linux_2637_video&num=1 ARCOS @ UC3M

 Por prioridad:
 Asignación a procesos más prioritarios el procesador
 Se puede combinar con cíclica. Ejemplo con tres clases de prioridad
Prioridad 3
Prioridad 2
Prioridad 1
 Características:
 Uso de prioridades fijas: problema de inanición
 No fijas: uso de algún algoritmo de envejecimiento
 Uso en sistemas de tiempo compartido con aspectos de tiempo real
85 ARCOS @ UC3M
 Primero el trabajo más corto:

 Dado un conjunto de trabajo del que se sabe la duración total de la ejecución
de cada uno de ellos, se ordenan de la menor a la mayor duración.
 [v] Produce el menor tiempo de respuesta (medio)
 [i] Penaliza los trabajos largos.
 Uso en sistemas batch.
 FIFO:
 Ejecución por el estricto orden de llegada.
 [v] Simple de implantar.
 [i] Penaliza los trabajos prioritarios.
 Uso en sistemas batch.
86 ARCOS @ UC3M
Política vs mecanismo
 Separación de lo qué se puede hacer

de cómo se puede hacer
 Normalmente, un proceso conoce cuál es el hilo más prioritario,
el que más E/S necesitará, etc.
 Uso de algoritmos de planificación parametrizados

 Mecanismo en el kernel
 Parámetros rellenados por los procesos de usuarios

 Política establecida por los procesos de usuario
87 ARCOS @ UC3M
Planificación multipolítica
Windows 2000 y Linux
Windows 2000 Linux
Prioridades de RT
16 niveles de RT 31-16 0-99
I/O I/O
Prioridades procs.
CPU convencionales CPU
15-1
15 niveles variables 100-139
1 nivel del sistema 0

Planificación multipolítica
Windows 2000
Windows 2000
16 niveles de RT 31-16
I/O
CPU
15-1
15 niveles variables
1 nivel del sistema 0

Planificación: estructuras de datos
Windows 2000
 Dispatcher database:
 base de datos de hilos esperando
para ejecutar y a qué proceso
pertenecen
 Dispatcher ready queue

 Una cola por nivel de prioridad
 Ready summary
 Un bit por nivel
 Si biti =1  un hilo en ese nivel
 Aumenta velocidad de búsqueda
 Idle summary
 Un bit por procesador
 Si bit =1  procesador libre
90 Inside Microsoft Windows 2000 (Microsoft Programming Series) ARCOS @ UC3M

Planificación: escenarios (1/3)
Windows 2000
 Cambio de contexto voluntario:
 Entra en el estado de espera por algún objeto:
 evento, mutex, semáforo, operación de E/S, etc.
 Al terminar pasa al final de la cola de listos + temporary priority boost.
 Rodaja de T: se mantiene
Priority
Running Ready
20
19
18
17
16
15
14
To wait state

Windows 2000
 Expulsión:
 Un hilo T de menor prioridad es expulsado cuando otro de mayor prioridad se
vuelve listo para ejecutar
 T se pone a la cabeza de la cola de su prioridad
 Rodaja de T: si RT entonces se reinicia en caso contrario se mantiene
Priority
Running Ready
18 From wait state
17
16
15
14
13

Windows 2000
 Fin de rodaja:
 Un hilo T agota su rodaja de tiempo (quantum)
 Acciones del planificador:
 Reducir la prioridad de T  otro hilo pasa a ejecutar
 No reducir la prioridad  T pasa al último de la cola de su nivel (si vacía, vuelve de nuevo)
 Rodaja de T: se reinicia
Priority
Running Ready
15
14
13
12
11

Planificación: aumento de prioridad
Windows 2000
 Priority boost:
 Se aumenta la prioridad en ciertas ocasiones (solo en los niveles 0-15):
 Cuando se completa una operación de E/S
 Al salir del estado de una operación wait
 Cuando el hilo lleva «mucho tiempo» en la cola de listo sin ejecutar:
 El hilo de kernel balance set manager aumenta la prioridad por «envejecimiento»
 Muestrea 1 vez por segundo la cola de listos y si T.estado=READY más de 300 ticks (~3 ó 4 segundos) entonces
T.prioridad =15
T.rodaja = 2*rodaja_normal

Planificación: estructura de datos
Linux
 Kernel/sched.c
runqueue
 Cada procesador tiene
140
su propio runqueue
active
…
1
 Cada runqueue tiene
140
dos vectores de prioridad:
CPU
expired
#0 …  Activo y Expirado
1
 Cada vector de prioridad tiene
140 listas:
…  Una por nivel de prioridad
 Incluye 100 niveles de tiempo real
95 CS 6560 Operating System Design (clase 4) ARCOS @ UC3M

Planificación: gestión
Linux
 El planificador elige los procesos de

la lista de activos de acuerdo a su
prioridad
runqueue
140  Cuando expira la rodaja de un

active
… proceso, lo mueve a la lista de

1 Expirado
 Se recalcula prioridad y rodaja
CPU 140
expired
#0 …  Cuando la lista de activos está vacía,

1
el planificador intercambia las listas
de activo y expirados
…  Si un proceso es suficientemente
interactivo permanecerá en la lista
de activos
96 CS 6560 Operating System Design (clase 4) ARCOS @ UC3M

Contenidos
 Introducción
 Modelo ofrecido

 Multitarea
 Planificador
97 ARCOS @ UC3M
Implicaciones en el sistema operativo…


o Jerarquía de
procesos
• Prioridad
98 ARCOS @ UC3M
Servicios del sistema operativo
inicialización y finalización de procesos

 Cambiar propiedad X
 Etc.
 Estados y
cambios de contexto
 Planificación
 Etc.
kernel
99 ARCOS @ UC3M
Creación de procesos
 Un proceso se crea:
 Durante el arranque del sistema
 Hilos del kernel + primer proceso (Ej.: init, swapper, etc.)
 Cuando un proceso existe hace una llamada al sistema

para crear otro:
 Cuando el sistema operativo comienza un nuevo trabajo
 Cuando un usuario arranca un nuevo programa
 Cuando durante la ejecución de un programa se necesite
100 CS 6560 Operating System Design (clase 4: procesos) ARCOS @ UC3M

Finalización de procesos
 Un proceso termina:
 De forma voluntaria:
 Finalización normal
 Finalización con error
 De forma involuntaria:
 Finalizado por el sistema (Ej.: excepción, sin recursos necesarios)
 Finalizado por otro proceso (Ej.: a través de llamada al sistema)
 Finalizado por el usuario (Ej.: control-c por teclado)
 En Unix/Linux se usan señales como mecanismo
 Se pueden capturar y tratar (salvo SIGKILL) para evitar finalizar involuntariamente
101 CS 6560 Operating System Design (clase 4: procesos) ARCOS @ UC3M

Creación y terminación de procesos
Llamadas al sistema
 Linux
clone() wait()
padre
exec() exit()
hijo
 Windows
CreateProcess() GetExitCodeProcess()
padre
ExitProcess()
hijo

Creación de procesos
Linux: clone
Obtener entrada libre en Tabla de Procesos

clone:
Copiar PCB del padre
“Clona al proceso padre Duplicar* mapa de M del

y da una nueva padre (incluyendo pilas)
identidad al hijo”
Apila PC inicial
Estado  listo Otras actualizaciones:

Contexto  end_fork() p.ej., limpiar señales,
PCB en cola de listos eventos y mensajes
pendientes
Devuelve PID al Devuelve 0 al

padre hijo
103 ARCOS @ UC3M

Cambio de imagen de un proceso
Linux: exec
Liberar imagen de M
exec: del proceso
Leer ejecutable
“Cambia la imagen de
memoria de un proceso Crear nueva imagen
usando como M  BCP
‘recipiente’ uno previo”
Cargar secciones
.texto y .datos
Crear pila inicial U Otras acciones:

Crear pila S: dir. gestión de señales,
principio programa SETUID, etc
Inicio BCP: regs.;

PC  dir SO: RETI
104 ARCOS @ UC3M

Terminación de procesos
Linux: exit
Finaliza todos los hilos menos uno

exit:
Limpia operaciones asíncronas,
temporizadores y señales pendientes
“Termina la ejecución
de un proceso y libera Cierra todos los descriptores de archivo
los recursos”
Libera semáforos y cerrojos activos
Reasigna huérfanos a init
Estado proceso <- zombie
Trata de enviar señal SIGCLD al padre:
si responde: NO responde:
freeproc(): libera P y M mantener señal
105 ARCOS @ UC3M

Servicios del sistema operativo
repaso de la asignatura de sistemas operativos

 Etc.
 Estados y
cambios de contexto
 Planificación
 Etc.
kernel
106 ARCOS @ UC3M

Servicios en POSIX
Fork
 Crea un “clon” de un proceso
 Iguales salvo pequeñas diferencias:
al padre se le devuelve el PID del hijo, y el hijo cero.
Pid 200 Pid 201
pid = fork( ) ; pid = fork( ) ;

201 0
ARCOS @ UC3M
Servicios en POSIX
Exec
 Cambia la imagen de un proceso
 Si todo va bien no
se vuelve de esta Pid 201
función (el código se
sustituye por otro) execlp("ls",
"ls","-l",NULL);
Pid 201
/* código de /bin/ls */
ARCOS @ UC3M
Servicios en POSIX
Exit
 Finalizar la ejecución de un proceso
 El parámetro es un valor entero que se suele usar como
código de diagnóstico: si se ha ejecutado todo bien, ha
habido algún problema leve, algún error grave, etc.
Pid 201
exit( 10 ) ;
ARCOS @ UC3M
Servicios en POSIX
Wait
 Tiene tres efectos:
1. Bloque la ejecución del padre hasta que alguno de sus
hijos termine su ejecución.
2. Guarda en su parámetro el valor devuelto por el hijo.
3. Devuelve el pid del hijo que ha terminado.
Pid 200 Pid 201
pid != wait(&status) ;
exit( 10 );
1
3 2
pid != wait(&status) ;
201 10
ARCOS @ UC3M
Ejemplos de uso
 fork+exec+wait
simple
111 ARCOS @ UC3M

Repaso
fork() + exec()
/* ejecutar el mandato ls -l */
#include <sys/types.h>
#include <stdio.h>
main() {
pid_t pid;
int status;
pid = fork();
if (pid == 0)
{
execlp("ls","ls","-l",NULL);
exit(-1);
}
else
{
while (pid != wait(&status));
}
exit(0);
}
112 ARCOS @ UC3M

Repaso
fork() + exec()
#include <stdio.h>
main() {
pid_t pid;
int status;
pid = fork();
if (pid == 0)
{
exit(-1);
}
else
{
}
exit(0);
}
113 ARCOS @ UC3M

Repaso
fork() + exec()
/* ejecutar el mandato ls -l */ /* ejecutar el mandato ls -l */

#include <sys/types.h> #include <sys/types.h>
#include <stdio.h> #include <stdio.h>
main() { main() {
pid_t pid; pid_t pid;
int status; int status;
pid = fork(); pid = fork();

if (pid == 0) if (pid == 0)
{ {
execlp("ls","ls","-l",NULL); execlp("ls","ls","-l",NULL);
exit(-1); exit(-1);
} }
else else
{ {
while (pid != wait(&status)); while (pid != wait(&status));
} }
exit(0); exit(0);
} }
114 ARCOS @ UC3M

Repaso
fork() + exec()

main() { main() {

if (pid == 0) if (pid == 0)
{ {
exit(-1); exit(-1);
} }
else else
{ {
} }
exit(0); exit(0);
} }
115 ARCOS @ UC3M

Repaso
fork() + exec()

main() { main() {

if (pid == 0) if (pid == 0)
{ {
exit(-1); exit(-1);
} }
else else
{ {
} }
exit(0); exit(0);
} }
116 ARCOS @ UC3M

Repaso
fork() + exec()

main() { main() {

if (pid == 0) if (pid == 0)
{ {
exit(-1); exit(-1);
} }
else else
{ {
} }
exit(0); exit(0);
} }
117 ARCOS @ UC3M

Repaso
fork() + exec()
/* ejecutar el mandato ls -l */ /* código del mandato ls */

main() { main() {
pid_t pid;
int status; /* código del ls */
pid = fork(); exit( 0 );

if (pid == 0) }
{
exit(-1);
}
else
{
}
exit(0);
}
118 ARCOS @ UC3M

Repaso
wait() + exit()

main() { main() {
pid_t pid;

if (pid == 0) }
{
exit(-1);
}
else
{
}
exit(0);
}
119 ARCOS @ UC3M

Repaso
wait() + exit()

main() { main() {
pid_t pid;

if (pid == 0) }
{
exit(-1);
}
else
{
}
exit(0);
}
120 ARCOS @ UC3M

Repaso
wait() + exit()

main() { main() {
pid_t pid;

if (pid == 0) }
{
exit(-1);
}
else
{
}
exit(0);
}
121 ARCOS @ UC3M

Repaso
wait() + exit()
#include <stdio.h>
main() {
pid_t pid;
int status;
pid = fork();
if (pid == 0)
{
exit(-1);
}
else
{
0
}
exit(0);
}
122 ARCOS @ UC3M

Repaso
wait() + exit()
#include <stdio.h>
main() {
pid_t pid;
int status;
pid = fork();
if (pid == 0)
{
exit(-1);
}
else
{
}
exit(0);
}
123 ARCOS @ UC3M

Repaso
wait() + exit()
124 ARCOS @ UC3M

Lección 3
Procesos, hilos y planificación
Grupo ARCOS
Diseño de Sistemas Operativos

Grado en Ingeniería Informática
Universidad Carlos III de Madrid

Procesos e Hilos

Cargado por

Copyright:

Formatos disponibles

Procesos e Hilos

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Procesos e Hilos

Cargado por

Copyright:

Formatos disponibles

Grupo ARCOS

Universidad Carlos III de Madrid

Diseño de Sistemas Operativos

1. Carretero 2007: 1. Tanenbaum 2006(en):

1. Estudiar la teoría asociada.

2. Repasar lo visto en clase.

3. Ejercitar las competencias.

 Aspectos de diseño e implementación

 Aspectos de diseño e implementación

 Aspectos de la relación entre hilos de un proceso:

 Cada thread tiene en propiedad: ficheros ficheros

 Regiones de memoria especificas registros regs. regs.

 thread stack pila pila pila

 Contenido de los registros de la CPU

Hilos de Espacio Espacio Biblioteca Espacio

Hilo a nivel de usuario Hilo a nivel de núcleo P Proceso

Modelo ofrecido App3

De los recursos utilizados

 código, datos y pila

 Estado de ejecución  Zonas compartidas

 Contexto  Archivos abiertos

 Aspectos de diseño e implementación

Requisitos Información (en estructuras de datos) Funciones (internas, servicio y API)

• Zonas de memoria (código, datos y pila) • Diversas funciones internas

• Estado de ejecución • Int. hw/sw de dispositivos

App 1 Tabla de procesos

 Señales  Número positivo de 16 bits (32767)

 La información de cada proceso está en el BCP…

 Por razones de eficiencia

35 Sistemas operativos: una visión aplicada ARCOS @ UC3M

 Gestión de proceso  Gestión de ficheros  Gestión de memoria

 Contador de programa  Directorio de trabajo  Puntero al segmento de datos

 Tiempo de uso de CPU

37 Understanding the Linux Kernel (O'Really) ARCOS @ UC3M

 Aspectos de diseño e implementación

• Zonas de memoria (código, datos y pila) • Diversas funciones internas

• Estado de ejecución • Int. hw/sw de dispositivos

creación fin E/S

creación fin E/S

 En ejecución: con CPU asignada

creación fin E/S

BCP7 BCP2 BCP1 BCP3 BCP4

creación fin E/S

BCP7 BCP2 BCP1 BCP3 BCP4

 Cola de listos: procesos esperando a ejecutar en CPU

Estado del proceso Estado del proceso Estado del proceso

Registros Registros Registros

 Cola de listos: procesos esperando a ejecutar en CPU

creación fin E/S

BCP7 BCP2 BCP1 BCP3 BCP4

creación fin E/S

BCP7 BCP2 BCP1 BCP3 BCP4

 Registros generales: PC, RE, etc.

proceso P0 sistema operativo proceso P1

proceso P0 sistema operativo proceso P1

1 llamada bloqueante listo

proceso P0 sistema operativo proceso P1

salvar estado en el BCP0 listo

proceso P0 sistema operativo proceso P1

salvar estado en el BCP0 listo