PDF de programación - Bloque I: Principios de sistemas operativos

UNIVERSIDAD
DE CANTABRIA

Bloque I: Principios de sistemas
operativos
Tema 1. Principios básicos de los sistemas operativos
Tema 2. Concurrencia
Tema 3. Ficheros
Tema 4. Sincronización y programación dirigida por eventos
Tema 5. Planificación y despacho
Tema 6. Sistemas de tiempo real y sistemas empotrados
Tema 7. Gestión de memoria
Tema 8. Gestión de dispositivos de entrada-salida

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS
5

© Michael González, J. Javier Gutiérrez

12/abr/11

1

Notas:

UNIVERSIDAD
DE CANTABRIA

Tema 5: Planificación y despacho

• Conceptos.
• Políticas de planificación.
• Interfaz para planificación de procesos.
• Esquemas de planificación mixta entre procesos y threads.
• Planificación en sistemas multiprocesadores.
• Interfaz para planificación de threads.

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

2

1. Introducción
Un thread puede estar en tres estados diferentes:
• en ejecución: está en ejecución en un procesador
• activo: está listo para ejecutar, pero aún no tiene un procesador

UNIVERSIDAD
DE CANTABRIA

disponible

• bloqueado o suspendido: esperando a una condición para

poder continuar ejecutando

en ejecución

suspensión

expulsión

planificación

bloqueado

activo

a ctiv a ció n

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

3

Políticas de planificación:
Conceptos básicos
Política de Planificación:
• Conjunto de reglas para determinar el orden de ejecución de los

UNIVERSIDAD
DE CANTABRIA

procesos o threads

• Afecta a la ordenación de los procesos o threads cuando:

- se suspenden
- son expulsados
- se activan
-

llaman a una función que cambia la prioridad o la política

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

4

Conceptos básicos:
Objetivos de la planificación
En sistemas de tiempo compartido
- reparto equitativo del procesador
- eficiencia: tiempos de respuesta promedio pequeños
- potencia de cálculo: procesar en promedio la mayor cantidad

UNIVERSIDAD
DE CANTABRIA

posible de actividades

En sistemas de tiempo real

- predecibilidad: tiempos de respuesta de peor caso acotados
- urgencia: tiempos de respuesta de peor caso pequeños, para

actividades muy urgentes

- criticalidad: hacer primero las actividades críticas

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

5

Conceptos básicos (cont.)
Despacho:
• Es el conjunto de acciones que se llevan a cabo para comenzar

UNIVERSIDAD
DE CANTABRIA

la ejecución de una tarea

Expulsión:
• La planificación puede ser expulsora o no
• Si es expulsora, una tarea (que tenga mayor prioridad) puede

interrumpir a otra y desalojarla de la CPU

• Si no es expulsora, cuando una tarea comienza continúa

ejecutando hasta que voluntariamente cede la CPU
- más sencilla
-

tiempos de respuesta mucho peores

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

6

Conceptos básicos (cont.)
Prioridad:
• Número asociado a cada proceso o thread y utilizado por la

UNIVERSIDAD
DE CANTABRIA

política de planificación

• A mayor valor, mayor prioridad
• prioridades fijas: número entero positivo que no cambia
• prioridades dinámicas: el valor cambia por sí solo
Plazo (Deadline):
• Instante de tiempo en el que una tarea debe haber finalizado su

actividad

• Se usa como prioridad dinámica en la planificación EDF (Earliest

Deadline First): a menor plazo, mayor prioridad

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

7

UNIVERSIDAD
DE CANTABRIA

2. Políticas de planificación
Cíclica o round-robin
• Cada tarea recibe una “rodaja” del procesador
• Puede o no ser equitativa
FIFO
• Las tareas se ejecutan en el orden que llegan: no expulsable
Basada en prioridades
• Puede ser expulsable o no
Primero el trabajo más corto
• Para trabajos en lista (batch)
• Puede sufrir inanición

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

8

Algunas políticas definidas en POSIX:
• SCHED_FIFO: planificación expulsora por prioridad, con orden
FIFO para la misma prioridad
• SCHED_RR: planificación expulsora por prioridad, con orden
rotatorio para la misma prioridad; la rodaja temporal es fija
• SCHED_OTHER: otra política de planificación por prioridad,
dependiente de la implementación

UNIVERSIDAD
DE CANTABRIA

Los parámetros de planificación definidos son:

struct sched_param {

int sched_priority; ...

}

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

9

UNIVERSIDAD
DE CANTABRIA

3. Interfaz para la planificación de
procesos
Fijar política y parámetros, o sólo parámetros:

#include <sched.h>
int sched_setscheduler (pid_t pid, int policy,

const struct sched_param *param);

int sched_setparam (pid_t pid,

const struct sched_param *param);

Leer política y leer parámetros:

int sched_getscheduler (pid_t pid);

// devuelve la política

int sched_getparam (pid_t pid,

struct sched_param *param);

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

10

Interfaz para la planificación de
procesos (cont.)
Ceder el procesador:

int sched_yield (void);

Leer los límites de los parámetros:

int sched_get_priority_max (int policy);
int sched_get_priority_min (int policy);
int sched_rr_get_interval (pid_t pid,

struct timespec *interval);

UNIVERSIDAD
DE CANTABRIA

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

11

4. Planificación mixta:
Ámbito de contención
Existen tres modelos de planificadores de threads:
• de sistema:

- un planificador para todos los threads del sistema
-

los parámetros de planificación del proceso se ignoran

• de proceso:

UNIVERSIDAD
DE CANTABRIA

- un planificador para los procesos
- otro planificador para los threads del proceso elegido
- es el más eficiente, y menos predecible: no aconsejable para aplic.

de tiempo real multi-proceso y multi-thread

• mixto:

- un planificador para procesos y threads “globales”
- otro para los threads “locales” del proceso elegido

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

12

UNIVERSIDAD
DE CANTABRIA

5. Pl. en multiprocesadores: Dominio
de asignación
Los threads están pensados para ser aplicables en
multiprocesadores
La asignación de threads a procesadores es un campo de
investigación abierto
POSIX define el dominio de asignación de un thread como el
conjunto de procesadores en los que ese thread puede ser
ejecutado
La forma de especificar el dominio de asignación es definida por
la implementación
Las reglas de planificación sólo son deterministas para dominio
de asignación de tamaño uno y estático

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

13

6. Interfaz para la planificación de
threads
Atributos de planificación:
• Son parte del objeto de atributos que se utiliza al crear el thread
• Ámbito de contención (contentionscope); valores:

UNIVERSIDAD
DE CANTABRIA

- ámbito de sistema: PTHREAD_SCOPE_SYSTEM
- ámbito de proceso: PTHREAD_SCOPE_PROCESS

• Herencia de atributos de planificación (inheritsched); muy
importante, ya que si hay herencia no se hace caso del resto de
atributos de planificación; valores:
- hereda los del padre: PTHREAD_INHERIT_SCHED
- usa los del objeto attr: PTHREAD_EXPLICIT_SCHED

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

14

Atributos de planificación (cont.)
• Política de planificación (schedpolicy); valores:

UNIVERSIDAD
DE CANTABRIA

- SCHED_FIFO
- SCHED_RR
- SCHED_OTHER

• Parámetros de planificación(schedparam); es del tipo:

struct sched_param {

int sched_priority;
...

}

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

15

Funciones para atributos de
planificación

UNIVERSIDAD
DE CANTABRIA

#include <pthread.h>
int pthread_attr_setscope
(pthread_attr_t *attr,
int contentionscope);

int pthread_attr_getscope
(const pthread_attr_t *attr,
int *contentionscope);

int pthread_attr_setinheritsched
(pthread_attr_t *attr,
int inheritsched);

int pthread_attr_getinheritsched
(const pthread_attr_t *attr,
int *inheritsched);

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

16

Funciones para atributos de
planificación (cont.)

UNIVERSIDAD
DE CANTABRIA

int pthread_attr_setschedpolicy
(pthread_attr_t *attr,
int policy);

int pthread_attr_getschedpolicy
(const pthread_attr_t *attr,
int *policy);

int pthread_attr_setschedparam
(pthread_attr_t *attr,
const struct sched_param *param);

int pthread_attr_getschedparam
(const pthread_attr_t *attr,
struct sched_param *param);

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

17

Funciones para el cambio dinámico de
atrib. de planif.

UNIVERSIDAD
DE CANTABRIA

#include <pthread.h>
int pthread_getschedparam
(pthread_t thread,
int *policy, struct sched_param *param);

int pthread_setschedparam
(pthread_t thread,
int policy,
const struct sched_param *param);

GRUPO DE COMPUTADORES Y TIEMPO REAL
FACULTAD DE CIENCIAS

© Michael González, J. Javier Gutiérrez

12/abr/11

18

Ejemplo: planificación de threads

UNIVERSIDAD
DE CANTABRIA

#include <stdio.h>
#include <unistd.h>
#include <pthread.h>
#include <sched.h>
#include <string.h>
#include "load.h"

// datos transferidos