Sistemas operativos: una visión aplicada
Capítulo 10
Introducción a los sistemas distribuidos
Contenido
•
•
•
•
•
•
•
Sistemas distribuidos
Sistemas operativos distribuidos
Comunicación de procesos
Sincronización de procesos
Gestión de procesos
Sistemas de archivos
Gestión de memoria
Sistemas operativos: una visión aplicada
1
© J. Carretero, F. García, P. de Miguel, F. Pérez
Conceptos previos
• Un programa es un conjunto de instrucciones.
• Un proceso es un programa en ejecución.
• Una red de computadores es un conjunto de computadores
conectados por una red de interconexión.
• Un sistema distribuido (SD)
– Modelo físico: conjunto de nodos (procesadores sin memoria
ni reloj común) conectados por una red.
– Modelo lógico: conjunto de procesos que ejecutan
concurrentemente en uno o más computadores que colaboran
y comunican intercambiando mensajes.
• Un protocolo es un conjunto de reglas e instrucciones que
gobiernan la comunicación en un sistema distribuido, es decir,
el intercambio de mensajes.
Sistemas operativos: una visión aplicada
2
© J. Carretero, F. García, P. de Miguel, F. Pérez
Características
• Compartir recursos (HW, SW, datos).
– Acceso a recursos remotos.
• Modelo cliente-servidor
• Modelo basado en objetos
• Ofrecen una buena relación coste/rendimiento
• Capacidad de crecimiento
• Tolerancia a fallos, disponibilidad
– Replicación
• Concurrencia
• Velocidad
– Paralelismo
Sistemas operativos: una visión aplicada
3
© J. Carretero, F. García, P. de Miguel, F. Pérez
Desventajas
• Necesidad de software más complejo
• Problemas de fiabilidad
• Problemas de seguridad y confidencialidad
Sistemas operativos: una visión aplicada
4
© J. Carretero, F. García, P. de Miguel, F. Pérez
Arquitectura de un sistema distribuido
Red de interconexión
Sistemas operativos: una visión aplicada
5
© J. Carretero, F. García, P. de Miguel, F. Pérez
Redes e interconexión
• Paquete: tipo de mensaje que se intercambia entre dos
dispositivos de comunicación.
– Tamaño limitado por el hardware
• Mensaje: objeto lógico que se intercambian entre dos o más
procesos.
– Su tamaño puede ser bastante grande.
– Un mensaje se descompone en paquetes.
• Subsistema de comunicación: conjunto de componentes
HW y SW que proporcionan servicios de comunicación en un
sistema distribuido.
• Protocolo: conjunto de reglas e instrucciones que gobiernan el
intercambio de paquetes y mensajes
Sistemas operativos: una visión aplicada
6
© J. Carretero, F. García, P. de Miguel, F. Pérez
Propiedades de un subsistema de comunicación
• Tasa de transferencia: velocidad de transferencia
• Latencia: tiempo necesario para transferir un mensaje vacío
• Tiempo de transferencia = latencia + tamaño/tasa de
trasferencia
• Paquetes/segundo
• Capacidad de crecimiento. Aumento en el nº de nodos
• Calidad de servicio
– Importante en aplicaciones multimedia y de tiempo real
• Fiabilidad del subsistema
– Mecanismos de detección de errores
• Seguridad: protección de los paquetes
• Confidencialidad: proteger la identidad de los emisores
Sistemas operativos: una visión aplicada
7
© J. Carretero, F. García, P. de Miguel, F. Pérez
Tipos de redes de computadores
• Redes de área local (LAN, Local Area Network)
– Redes que enlazan sistemas cercanos
– Posibilidad de difusión de mensajes (broadcast)
• Redes de área extensa (WAN, Wide Area Network)
– Poco ancho de banda (20-500 Kbps)
– Bajas latencias
– Redes telefónicas, redes públicas de datos, fiabra óptica
RDSI, B-RDSI, ATM
• Nuevos desarrollos en telecomunicaciones (ATM y RDSI)
– Diferencias entre LAN y WAN cada vez más borrosas
Sistemas operativos: una visión aplicada
8
© J. Carretero, F. García, P. de Miguel, F. Pérez
Protocolos de comunicación
• Protocolo: conjunto de reglas y formatos que permiten la
comunicación entre procesos.
• La definición de un protocolo tiene dos parte:
– Especificación de la secuencia de mensajes que deben
intercambiarse.
– Especificación del formato de mensajes.
• El software de red se organiza en niveles
Sistemas operativos: una visión aplicada
9
© J. Carretero, F. García, P. de Miguel, F. Pérez
Funciones de una pila de protocolos
• Segmentación y ensamblado de mensajes
• Encapsulado: incorporación de información de control a los
datos
– Dirección del emisor y receptor
– Código de detección de errores
• Control de conexión
– Protocolos orientados a conexión
– Protocolos no orientados a conexión:
• No se asegura el orden secuencial de los datos transmitidos
• Entrega ordenada en protocolos orientados a conexión
– Números de secuencia
Sistemas operativos: una visión aplicada
10
© J. Carretero, F. García, P. de Miguel, F. Pérez
Funciones de una pila de protocolos II
• Control de flujo: función realizada en el receptor para limitar la
cantidad o tasa de datos que envía el emisor.
• Control de errores: se basan en el uso de una secuencia de
comprobación y reenvío.
• Direccionamiento, conseguir que los mensajes alcancen al
receptor
• Multiplexación: necesario para un uso más eficiente de los
servicios
• Servicios de transmisión:
– Prioridad
– Calidad de servicio
– Seguridad
Sistemas operativos: una visión aplicada
11
© J. Carretero, F. García, P. de Miguel, F. Pérez
Ejemplos de protocolos
• Protocolos internet:
– Originados por el trabajo de DARPA en los 70
– Muy utilizados en la actualidad
– Gran crecimiento durante los 90 debido al uso del Web
• Protocolos OSI (open system interconection)
– Estándar desarrollado por ISO
• Estándares propietarios
– SNA de IBM (años 70)
– DECnet desarrollado por DEC
– NetWare: red de Novell para redes de PC
Sistemas operativos: una visión aplicada
12
© J. Carretero, F. García, P. de Miguel, F. Pérez
Protocolos TCP/IP
• Resultado de la investigación y desarrollo llevados a cabo en la
red ARPANET (financiada por DARPA) en los años 70
• Familia de protocolos utilizados en Internet
• En los 90 se ha establecido como la arquitectura comercial
dominante:
– Se especificaron y utilizaron antes de OSI
– Independiente de la tecnología de red utilizada
– Internet está construida sobre un conjunto de protocolos
TCP/IP.
– Espectacular desarrollo de World Wide Web
Sistemas operativos: una visión aplicada
13
© J. Carretero, F. García, P. de Miguel, F. Pérez
Protocolos TCP/IP
Receptor
Emisor
Sistemas operativos: una visión aplicada
14
© J. Carretero, F. García, P. de Miguel, F. Pérez
Protocolo Internet (nivel IP)
• La transmisión no es fiable (no se asegura la recepción de los
paquetes IP). Los paquetes se pueden descartar por:
– Expiración del tiempo de vida
– Congestión
– Error en la suma de comprobación
• Control de flujo muy limitado
• Calidad de servicio muy limitado
– Seguridad: normal o alto
– Retardo: normal o bajo
– Rendimiento: normal o alto
Sistemas operativos: una visión aplicada
15
© J. Carretero, F. García, P. de Miguel, F. Pérez
Protocolos de transporte
• Protocolo TCP
– Orientado a conexión
– Garantiza que los datos se entregan en el orden en el que se
envían
– Las conexiones TCP se ven como un flujo de bytes
– La transmisión se considera “fiable”. Pueden perderse
mensajes (sobrecarga en la red, fallos en encaminadores, etc.)
– Cuando los mensajes son muy pequeños, TCP los retrasa
hasta conseguir uno más grande
• Esta opción debe desactivarse si es necesario
– Escrituras concurrentes sobre una misma conexión TCP
pueden provocar que los datos se entremezclen.
Sistemas operativos: una visión aplicada
16
© J. Carretero, F. García, P. de Miguel, F. Pérez
Protocolos de transporte
• Protocolo UDP
– Protocolo de datagramas no orientado a conexión.
– Protocolo no fiable
• Los paquetes se pueden perder, duplicar, recibir en orden
distinto al enviado
– Tamaño máximo del mensaje: 64 KB
Sistemas operativos: una visión aplicada
17
© J. Carretero, F. García, P. de Miguel, F. Pérez
Encaminamiento
• Permite que los paquetes viajen del proceso emisor al receptor.
• Algoritmo:
– Un programa de aplicación genera un paquete, o bien se lee
un paquete de la interfaz de red.
– Si el paquete es para la máquina, se acepta.
– En caso contrario, se incrementa el contador de saltos, si se
excede el máximo, el paquete se descarta.
– Si el paquete no es para la máquina se busca en la tabla de
encaminamiento y se retransmite a la interfaz adecuada.
• Tablas estáticas, las más utilizadas
• Tablas dinámicas
Sistemas operativos: una visión aplicada
18
© J. Carretero, F. García, P. de Miguel, F. Pérez
Papel del sistema operativo
• El SW de comunicación de un sistema operativo se organiza
como un conjunto de componentes con tareas concretas
– Subsistema de almacenamiento: buffers donde almacenar los
paquetes que llegan y se envían (limitado)
• En implementaciones UNIX típicas
– TCP reserva para cada puerto (socket) un buffer de 8 KB y
UDP 2 buffers de 8KB. El tamaño se puede incrementar
hasta 64 KB.
– Los mensajes a enviar se copian a estos buffers
– El contenido de estos buffers se fragmenta y se copian a
nuevos bloques de memoria a utilizar por IP
– IP envía finalmente los paquetes por la interfaz de red
correspondiente
Sistemas operativos: una visión aplicada
19
© J. Carretero, F. García, P. de Miguel, F. Pérez
Papel del sistema operativo
• Un sistema operativo puede perder paquetes cuando la tasa de
envíos y de recepción es muy grande.
• En sistemas operativos multiusuario la pérdida de paquetes suele
producirse a ráfagas debido a los algoritmos de planificación.
• La latencia del SO
40
ha crecido en términos
35
relativos
30
25
20
15
10
5
0
1985-1990
Sistemas operativos: una visión aplicada
20
1990-1995
1995-2000
2000-20005
© J. Carretero, F. García, P. de Miguel, F. Pérez
¿Dónde se pierde el tiempo?
• Códigos de corrección (Checksum)
– Sobre datos TCP y UDP
– Sobre cabeceras IP
• Copias de datos
– Entre usuario y kernel
• Estructura de datos
– Gestión de los buffers, colas de defragmentación de paquetes
IP,
• Sistema Operativo
– Sobrecarga impuesta por las operaciones del SO
Sistemas operativos: una visión aplicada
21
© J. Carretero, F. García, P. de Miguel, F. Pérez
Contenido
• Sistemas distribuidos
• Sistemas operativos distribuidos
•
•
•
•
•
Comunicación de procesos
Sincronización de procesos
Gestión de procesos
Sistemas de archivos
Gestión de memoria
Sistemas operativos: una visión aplicada
22
© J. Carretero, F. García, P. de Miguel, F. Pérez
Sistema operativo en red (SOR)
Aplicaciones
Aplicaciones
Lenguajes de programación
Lenguajes de programación
Sistema operativo
Sistema operativo
Hardware
Hardware
Red de interconexión
• El usuario ve un conjunto de máquinas independientes
– No hay transparencia
• Se debe acceder de forma explícita a los recursos de otras
máquinas
• Difíciles de utilizar para desarrollar aplicaciones distribuidas
Sistemas operativos: una visión aplicada
23
© J. Carretero, F. García, P. de Miguel, F. Pérez
Sistema operativo distribuido (SOD)
Aplicaciones
Lenguajes de programación
Sistema operativo distribuido
Hardware
Hardware
Red de interconexión
• Se comporta como un SO único (visión única)
– Distribución. Transparencia
• Se construyen normalmente como micronúcleos que ofrecen
servicios básicos de comunicación
– Mach, Amoeba, Chorus.
• Todos los computadores deben ejecutar el mismo SOD
Sistemas operativos: una visión aplicada
24
© J. Carretero, F. García, P. de Miguel, F. Pérez
Transparencia
• Acceso: acceso a recursos remotos y locales de igual forma
• Posición: acceso a los recursos sin necesidad de conocer su
situación
• Concurrencia: acceso concurrente a recursos compartidos sin
interferencias
• Replicación: Acceso a recursos replicados sin conocimiento de
que lo son
• Fallos: mantenimiento del servicio en presencia de fallos.
• Migración: permite que los recursos y objetos se muevan sin
afectar a la operación de los programas.
• Capacidad de crecimiento: facilidad para crecer sin afectar a la
estructura del sistema
Sistemas operativos: una visión aplicada
25
© J. Carretero, F. García, P. de Miguel, F. Pérez
Middleware y entornos distribuidos
Aplicaciones
Lenguajes de programación
Middleware
Sistema operativo
Sistema operativo
Hardware
Hardware
Red de interconexión
• Servicios y protocolos estándarizados: Sistemas abiertos
• Ofrecen servicios no incluidos en el SO (servicios de ficheros
distribuidos, servicios de nombres, ...)
• Facilitan el desarrollo de aplicaciones distribuidas
• Independientes del HW y del SO subyacente.
• DCE, CORBA, DCOM, Legion, Globe, Globus
Sistemas operativos: una visión aplicada
26
© J. Carretero, F. García, P. de Miguel, F. Pérez
Servicios de un sistema operativo distribuido
•
•
•
•
•
Servicios de comunicación
Servicios de sincronización
Gestión distribuida de procesos
Sistemas de archivos distribuidos
Memoria compartida distribuida
Sistemas operativos: una visión aplicada
27
© J. Carretero, F. García, P. de Miguel, F. Pérez
Contenido
• Sistemas distribuidos
• Sistemas operativos distribuidos
• Comunicación de procesos
•
•
•
•
Sincronización de procesos
Gestión de procesos
Sistemas de archivos
Gestión de memoria
Sistemas operativos: una visión aplicada
28
© J. Carretero, F. García, P. de Miguel, F. Pérez
Comunicación en sistemas distribuidos
• La comunicación de procesos es fundamental en cualquier
sistema distribuido
• Existen diferentes posibilidades todas ellas basadas en el paso de
mensajes
– Mecanismos de bajo nivel, el programador debe preocuparse
de establecer los protocolos de comunicación, representación
de datos, etc.
• Colas de mensajes
• Sockets
– Mecanismo de alto nivel, ofrecen abstracciones donde el
programador no debe preocuparse de establecer protocolos
• Llamadas a procedimientos remotos
• Invocación de métodos remotos (entornos orientados a objetos)
Sistemas operativos: una visión aplicada
29
© J. Carretero, F. García, P. de Miguel, F. Pérez
Comunicación cliente-sevidor
• Muy utilizada en entornos distribuidos (más del 90% de los
sistemas distribuidos utilizan la arquitectura cliente-servidor)
Máquina A
petcición
cliente
NÚCLEO
Máquina B
servidor
respuesta
NÚCLEO
RED
• Protocolo típico: petición-respuesta
Sistemas operativos: una visión aplicada
30
© J. Carretero, F. García, P. de Miguel, F. Pérez
Comunicación de grupos
• Utiliza mensajes multicast
• Útil para:
– Ofrecer tolerancia a fallos basado en servicios replicados
– Localizar objetos en sistemas distribuidos
– Mejor rendimiento mediante datos replicados
– Actualizaciones múltiples
– Operaciones colectivas en cálculo paralelo
Sistemas operativos: una visión aplicada
31
© J. Carretero, F. García, P. de Miguel, F. Pérez
Sockets
• Aparecieron en 1981 en UNIX BSD 4.2
– Intento de incluir TCP/IP en UNIX
– Diseño independiente del protocolo de comunicación
• Un socket es punto final de comunicación (dirección IP y
puerto)
• Abstracción que:
– Ofrece interfaz de acceso a los servicios de red en el nivel de
transporte
• Protocolo TCP
• Protocolo UDP
– Representa un extremo de una comunicación bidireccional
con una dirección asociada
Sistemas operativos: una visión aplicada
32
© J. Carretero, F. García, P. de Miguel, F. Pérez
Sockets: introducción
• Sujetos a proceso de estandarización dentro de POSIX (POSIX
1003.1g)
• Actualmente
– Disponibles en casi todos los sistemas UNIX
– En prácticamente todos los sistemas operativos
• WinSock: API de sockets de Windows
– En Java como clase nativa
Sistemas operativos: una visión aplicada
33
© J. Carretero, F. García, P. de Miguel, F. Pérez
Sockets UNIX
•
•
•
•
•
•
•
•
•
Dominios de comunicación
Tipos de sockets
Direcciones de sockets
Creación de un socket
Asignación de direcciones
Solicitud de conexión
Preparar para aceptar conexiones
Aceptar una conexión
Transferencia de datos
Sistemas operativos: una visión aplicada
34
© J. Carretero, F. García, P. de Miguel, F. Pérez
Dominios de comunicación
•
•
•
•
Un dominio representa una familia de protocolos
Un socket está asociado a un dominio desde su creación
Sólo se pueden comunicar sockets del mismo dominio
Algunos ejemplos:
– PF_UNIX (o PF_LOCAL): comunicación dentro de una
máquina
– PF_INET: comunicación usando protocolos TCP/IP
• Los servicios de sockets son independientes del dominio
Sistemas operativos: una visión aplicada
35
© J. Carretero, F. García, P. de Miguel, F. Pérez
Tipos de sockets
• Stream (SOCK_STREAM)
– Orientado a conexión
– Fiable, se asegura el orden de entrega de mensajes
– No mantiene separación entre mensajes
– Si PF_INET se corresponde con el protocolo TCP
• Datagrama (SOCK_DGRAM)
– Sin conexión
– No fiable, no se asegura el orden en la entrega
– Mantiene la separación entre mensajes
– Si PF_INET se corresponde con el protocolo UDP
• Raw (SOCK_RAW)
– Permite el acceso a los protocolos internos como IP
Sistemas operativos: una visión aplicada
36
© J. Carretero, F. García, P. de Miguel, F. Pérez
Direcciones de sockets
• Cada socket debe tener asignada una dirección única
• Las direcciones se usan para:
– Asignar una dirección local a un socket (bind)
– Especificar una dirección remota (connect o sendto)
• Dependientes del dominio
• Se utiliza la estructura genérica struct sockaddr
• Cada dominio usa una estructura específica
– Direcciones en PF_UNIX (struct sockaddr_un)
• Nombre de fichero
– Direcciones en PF_UNIX (struct sockaddr_in)
– Uso de conversión de tipos (casting) en las llamadas
Sistemas operativos: una visión aplicada
37
© J. Carretero, F. García, P. de Miguel, F. Pérez
Direcciones de sockets en PF_INET
• Host (32 bits) + puerto (16 bits)
• Una dirección IP se almacena en una estructura de tipo:
– struct in_addr
• Estructura struct sockaddr_in
– Debe iniciarse a 0
– sin_family: dominio (AF_INET)
– sin_port: puerto
– sin_addr: dirección del host
• Función que facilita el nombre de la máquina en la que se
ejecuta:
int gethostname(char *name, int namelen);
Sistemas operativos: una visión aplicada
38
© J. Carretero, F. García, P. de Miguel, F. Pérez
Obtención de la dirección de host
• Usuarios manejan direcciones en forma de texto:
– decimal-punto: 138.100.8.100
– dominio-punto: laurel.datsi.fi.upm.es
• Algunas funciones para trabajar con direcciones:
– char *inet_ntoa(struct in_addr in);
• Devuelve una dirección en notación decimal-punto.
– struct hostent *gethostbyname(char *str);
• Convierte una dirección en notación dominio-punto a
una estructura que describe máquina.
• Algunos campos de la estructura struct hostent:
– char *name
nombre oficial de la máquina
– char **h_addr_list lista de direcciones
Sistemas operativos: una visión aplicada
39
© J. Carretero, F. García, P. de Miguel, F. Pérez
Ejemplo
• Programa que obtiene la dirección en formato decimal-punto a
partir de un formato dominio-punto.
void main(int argc, char **argv) {
struct hostent *hp;
struct in_addr in;
hp = gethostbyname(argv[1]);
if (hp == NULL) {
printf(“Error en gethostbyname\n”);
exit(0);
}
memcpy(&in.s_addr,*(hp->h_addr_list),sizeof(in.s_addr));
printf(“%s es %s\n”, hp->h_name, inet_ntoa(in));
}
Sistemas operativos: una visión aplicada
40
© J. Carretero, F. García, P. de Miguel, F. Pérez
Direcciones de sockets II
• En TCP/IP los números se emplean con formato big-endian.
• En computadores que no utilicen este formato es necesario
emplear funciones para traducir números entre el formato que
utiliza TCP/IP y el empleado por el propio computador:
u_long htonl (u_long hostlong)
u_short htons (u_short hostshort)
u_long ntohl (u_long netlong)
u_short ntohs (u_short netshort)
• Las primera traduce un número de 32 bits representado en el
formato del computador al formato de red (TCP/IP).
Sistemas operativos: una visión aplicada
41
© J. Carretero, F. García, P. de Miguel, F. Pérez
Creación de un socket
• int socket(int dominio, int tipo, int protocolo)
– Crea un socket devolviendo un descriptor de fichero
– dominio: PF_XXX
– tipo: SOCK_XXX
– protocolo: dependiente del dominio y tipo
• 0 elige el más adeucado
• Especificados en /etc/protocols
• El socket creado no tiene dirección asignada
Sistemas operativos: una visión aplicada
42
© J. Carretero, F. García, P. de Miguel, F. Pérez
Asignación de direcciones
• int bind(int sd, struct sockaddr *dir, int long)
– sd: descriptor devuelto por socket
– dir: dirección a asignar
– long: longitud de la dirección
• Si no se asigna dirección (típico en clientes)
– Se le asigna automáticamente (puerto efímero) en la su
primera utilización (connect o sendto)
• Direcciones en dominio PF_INET
– Puertos en rango 0..65535. Reservados: 0..1023. Si 0, el
sistema elige uno
– Host: una dirección local IP
• INNADDR_ANY: elige cualquiera de la máquina
• El espacio de puertos para streams y datagramas es indendiente
Sistemas operativos: una visión aplicada
43
© J. Carretero, F. García, P. de Miguel, F. Pérez
Solicitud de conexión
• Realizada en el cliente
• int connect(int sd, struct sockaddr *dir, int long)
– sd: descriptor devuelto por socket
– dir: dirección del socket remoto
– long: longitud de la dirección
• Si el socket no tiene dirección asignada, se le asigna una
automáticamente
• Normalmente se usa con streams
Sistemas operativos: una visión aplicada
44
© J. Carretero, F. García, P. de Miguel, F. Pérez
Preparar para aceptar conexiones
• Realizada en el servidor stream después de socket y bind
• int listen(int sd, int baklog)
– sd: descriptor devuelto por socket
– backlog:
• Número máximo de peticiones pendientes de aceptar que se
encolarán (algunos manuales recomiendan 5)
• Hace que el socket quede preparado para aceptar conexiones.
Sistemas operativos: una visión aplicada
45
© J. Carretero, F. García, P. de Miguel, F. Pérez
Aceptar una conexión
• Realizada en el servidor stream después de socket, bind y listen
• Cuando se produce la conexión, el servidor obtiene:
– La dirección del socket del cliente
– Un nuevo descriptor que queda conectado al socket del
cliente
• Después de la conexión quedan activos dos sockets en el
servidor:
– El original para aceptar nuevas conexiones
– El nuevo para enviar/recibir datos por la conexión
Sistemas operativos: una visión aplicada
46
© J. Carretero, F. García, P. de Miguel, F. Pérez
Aceptar una conexión
• int accept(int sd, struct sockaddr *dir, int *long)
– sd: descriptor devuelto por socket
– dir: dirección del socket del cliente devuelta
– long: parámetor valor-resultado
• Antes de la llamada: tamaño de dir
• Después de la llamada: tamaño de la dirección del cliente que
se devuelve.
Sistemas operativos: una visión aplicada
47
© J. Carretero, F. García, P. de Miguel, F. Pérez
Obtener la dirección de un socket
• Obtener la dirección a partir del descriptor
– int getsockname(int sd, struct sockaddr *dir, int *long)
• sd: descriptor devuelto por socket
• dir: dirección del socket devuelta
• long: parámetro valor-resultado (igual que en accept)
• Obtener la dirección del socket en el toro extremo de la
conexión:
– int gerpeername(int sd, struct sockaddr *dir, int *long)
• sd: descriptor devuelto por socket
• dir: dirección del socket remoto
• long: parámetro valor-resultado
Sistemas operativos: una visión aplicada
48
© J. Carretero, F. García, P. de Miguel, F. Pérez
Transferencia de datos con streams
• Una vez realizada la conexión, ambos extremos puede
transferir datos.
• Envío:
– int write(int sd, char *mem, int long);
• Devuelve el nº de bytes enviados
– También puede utilizarse el servicio send.
• Recepción:
– int read(int sd, char *mem, int long);
• Devuelve el nº de bytes recibidos
– También puede utilizarse el servicio recv
• Es importante comprobar siempre el valor que devuelven estas
llamadas: pueden no transferirse todos los datos.
Sistemas operativos: una visión aplicada
49
© J. Carretero, F. García, P. de Miguel, F. Pérez
Transferencia de datos con streams II
•
Función que envía un bloque de datos con reintentos:
int enviar(int socket, char *mensaje, int longitud)
{
int r;
int l = longitud;
do {
r = write(socket, mensaje, l);
l = l – r;
mensaje = mensaje + r;
} while ((l>0) && (r>=0));
if (r < 0)
return (-1);
else
return(0);
/* fallo */
}
Sistemas operativos: una visión aplicada
50
© J. Carretero, F. García, P. de Miguel, F. Pérez
Transferencia de datos con datagramas
• No hay conexión real
• Para usar un socket para transferir basta con:
– Crearlo: socket
– Asignarle una dirección: bind (si no, lo hará el sistema)
• Envío:
– int sendto(int sd, char *men, int long, int flags,
struct sockaddr *dir, int long)
• Devuelve el nº de bytes enviados
• dir: dirección del socket remoto y long la longitud
• Rccepción:
– int recvfrom(int sd, char *men, int long, int flags,
struct sockaddr *dir, int long)
• Devuelve el nº de bytes enviados
• dir: dirección del socket remoto y long la longitud
Sistemas operativos: una visión aplicada
51
© J. Carretero, F. García, P. de Miguel, F. Pérez
Cerrar un socket
• Se usa close para cerrar ambos tipos de sockets
• Si el socket es de tipo stream, close cierra la conexión en ambos
sentidos
• Se puede cerrar un único extremo:
– int shutdown(int st, int modo)
• sd: descriptor devuelto por socket
• modo: SHUT_RD, SHUT_RW o SHUT_RDWR
Sistemas operativos: una visión aplicada
52
© J. Carretero, F. García, P. de Miguel, F. Pérez
Configuración de opciones
• Existen varios niveles dependiendo del protocolo afectado como
parámetro
– SOL_SOCKET: opciones independientes del protocolo
– IPPROTO_TCP: nivel de protocolo TCP
– IPPTOTO_IP: nivel de protocolo IP
• Consultar opciones asociadas a un socket
– int getsockopt(int sd, int nivel, int opc, char *val, int *long)
• Modificar las opciones asociadas a un socket
– int setsockopt(int sd, int nivel, int opc, char *val, int long)
• Ejemplos (nivel SOL_SOCKET):
– SO_REUSEADDR: permite reutilizar direcciones
Sistemas operativos: una visión aplicada
53
© J. Carretero, F. García, P. de Miguel, F. Pérez
Escenario típico con sockets streams
Proceso servidor
socket()
Proceso cliente
bind()
listen()
socket()
Abrir conexión
connect()
accept()
Crear
thread
accept()
write()
read()
Petición
read()
Respuesta
write()
close()
Sistemas operativos: una visión aplicada
close()
54
© J. Carretero, F. García, P. de Miguel, F. Pérez
Ejemplo (TCP)
Máquina A
cliente
Máquina B
sumar(5,2)
servidor
5+2
NÚCLEO
Restulado = 7
NÚCLEO
RED
Sistemas operativos: una visión aplicada
55
© J. Carretero, F. García, P. de Miguel, F. Pérez
Servidor (TCP)
void main(int argc, char *argv[])
{
struct sockaddr_in server_addr,
int sd, sc;
int size, val;
int size;
int num[2], res;
client_addr;
sd = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP);
val = 1;
setsockopt(sd, SOL_SOCKET, SO_REUSEADDR, (char *) &val, sizeof(int));
bzero((char *)&server_addr, sizeof(server_addr));
server_addr.sin_family = AF_INET;
server_addr.sin_addr.s_addr = INADDR_ANY;
server_addr.sin_port = 4200;
bind(sd, &server_addr, sizeof(server_addr));
Sistemas operativos: una visión aplicada
56
© J. Carretero, F. García, P. de Miguel, F. Pérez
Servidor (TCP)
listen(sd, 5);
size = sizeof(client_addr);
while (1)
{
printf("esperando conexion\n");
sc = accept(sd, (struct sockaddr *)&client_addr,&size);
read(sc, (char *) num, 2 *sizeof(int));
// recibe la petición
res = num[0] + num[1];
write(sc, &res, sizeof(int));
// se envía el resultado
close(sc);
}
close (sd);
exit(0);
}
Sistemas operativos: una visión aplicada
57
© J. Carretero, F. García, P. de Miguel, F. Pérez
Cliente (TCP)
void main(void)
{
int sd;
struct sockaddr_in server_addr;
struct hostent *hp;
int num[2], res;
sd = socket(AF_INET, SOCK_STREAM, IPPROTO_TCP);
bzero((char *)&server_addr, sizeof(server_addr));
hp = gethostbyname ("arlo.datsi.fi.upm.es");
memcpy (&(server_addr.sin_addr), hp->h_addr, hp->h_length);
server_addr.sin_family = AF_INET;
server_addr.sin_port = 4200;
Sistemas operativos: una visión aplicada
58
© J. Carretero, F. García, P. de Miguel, F. Pérez
Cliente (TCP)
// se establece la conexión
connect(sd, (struct sockaddr *) &server_addr,
sizeof(server_addr));
num[0]=5;
num[1]=2;
write(sd, (char *) num, 2 *sizeof(int));
read(sd, &res, sizeof(int));
// envía la petición
// recibe la respuesta
printf("Resultado es %d \n", res);
close (sd);
exit(0);
}
Sistemas operativos: una visión aplicada
59
© J. Carretero, F. García, P. de Miguel, F. Pérez
Servidor (datagramas)
void main(void)
{
int num[2];
int s, res, clilen;
struct sockaddr_in server_addr, client_addr;
s =
socket(AF_INET, SOCK_DGRAM, 0);
bzero((char *)&server_addr, sizeof(server_addr));
server_addr.sin_family = AF_INET;
server_addr.sin_addr.s_addr = INADDR_ANY;
server_addr.sin_port = 7200;
bind(s, (struct sockaddr *)&server_addr, sizeof(server_addr));
Sistemas operativos: una visión aplicada
60
© J. Carretero, F. García, P. de Miguel, F. Pérez
Servidor (datagramas)
clilen = sizeof(client_addr);
while (1)
{
recvfrom(s, (char *) num, 2* sizeof(int), 0,
(struct sockaddr *)&client_addr, &clilen);
res = num[0] + num[1];
sendto(s, (char *)&res, sizeof(int), 0,
(struct sockaddr *)&client_addr,
clilen);
}
}
Sistemas operativos: una visión aplicada
61
© J. Carretero, F. García, P. de Miguel, F. Pérez
Cliente (datagramas)
void main(int argc, char *argv[]){
struct sockaddr_in server_addr, client_addr;
struct hostent *hp;
int s, num[2], res;
if (argc != 2){
printf("Uso: client <direccion_servidor> \n");
exit(0);
}
s = socket(AF_INET, SOCK_DGRAM, 0);
hp = gethostbyname (argv[1]);
bzero((char *)&server_addr, sizeof(server_addr));
server_addr.sin_family = AF_INET;
memcpy (&(server_addr.sin_addr), hp->h_addr, hp->h_length);
server_addr.sin_port = 7200;
Sistemas operativos: una visión aplicada
62
© J. Carretero, F. García, P. de Miguel, F. Pérez
Cliente (datagramas)
bzero((char *)&client_addr, sizeof(client_addr));
client_addr.sin_family = AF_INET;
client_addr.sin_addr.s_addr = INADDR_ANY;
client_addr.sin_port = htons(0);
bind (s, (struct sockaddr *)&client_addr, sizeof(client_addr));
num[0] = 2;
num[1] = 5;
sendto(s, (char *)num, 2 * sizeof(int), 0,
(struct sockaddr *) &server_addr, sizeof(server_addr));
recvfrom(s, (char *)&res, sizeof(int), 0, NULL, NULL);
printf("2 + 5 = %d\n", res);
close(s);
}
Sistemas operativos: una visión aplicada
63
© J. Carretero, F. García, P. de Miguel, F. Pérez
Llamadas a procedimientos remotos (RPC)
• RPC (remote procedure call): llamadas a procedimiento remoto
(Birrel y Nelson 1985)
• Híbrido entre llamadas a procedimientos y paso de mensajes
• Las RPC constituyen el núcleo de muchos sistemas distribuidos
• Llegaron a su culminación con DCE (Distributed Computing
Environment)
• Han evolucionado hacia orientación a objetos
– Invocación de métodos remotos (CORBA, RMI)
Sistemas operativos: una visión aplicada
64
© J. Carretero, F. García, P. de Miguel, F. Pérez
Funcionamiento de las RPC
• El proceso que realiza la llamada empaqueta los argumentos en
un mensaje, se los envía a otro proceso y espera el resultado
• El proceso que ejecuta el procedimiento extrae los argumentos
del mensaje, realiza la llamada de forma local, obtiene el
resultado y se lo envía de vuelta al proceso que realizó la
llamada
• Objetivo: acercar la semántica de las llamadas a procedimiento
convencional a un entorno distribuido (transparencia).
Sistemas operativos: una visión aplicada
65
© J. Carretero, F. García, P. de Miguel, F. Pérez
Llamadas y mensajes en una RPC
SISTEMA CLIENTE
SISTEMA SERVIDOR
PROCEDIMIENTOS
CÓDIGO DE LA APLICACIÓN
INICIO
FIN
LLAMADA LLAMADA = 7
suma(5,2)
EJECUTA
PROCEDIMIENTO
REMOTO
1
RESGUARDO
CLIENTE
2
PREPARA
ENTRADA
CONVIERTE
SALIDA
Sistemas operativos: una visión aplicada
5
RESGUARDO
SERVIDOR
CONVIERTE
ENTRADA
4
6
7
PREPARA
SALIDA
66
3
© J. Carretero, F. García, P. de Miguel, F. Pérez
Suplentes (stubs)
• Se generan automáticamente por el software de RPC
• En el cliente:
– Localizan al servidor
– Empaquetan los parámetros y construyen los mensajes
– Envían el mensaje al servidor
– Espera la recepción del mensaje y devuelven los resultados
• En el servidor
– Realizan tareas similares
• Los suplentes son independientes de la implementación que se
haga del cliente y del servidor. Sólo dependen de la interfaz.
Sistemas operativos: una visión aplicada
67
© J. Carretero, F. García, P. de Miguel, F. Pérez
RPC: protocolo básico
“enlaza con
el servidor”
servidor
cliente
Se registra con un
servicio de nombres
prepara
parámetros,
envía petición
recibe petición
Ejecuta el
procedimiento
envía petición
Desempaqueta
la respuesta
Sistemas operativos: una visión aplicada
68
© J. Carretero, F. García, P. de Miguel, F. Pérez
Aspectos de diseño de las RPC
•
•
•
•
Lenguaje de definición de interfaces. Generador de suplentes.
Transferencia de parámetros
Enlace dinámico (binding)
Semántica de las RPC en presencia de fallos
Sistemas operativos: una visión aplicada
69
© J. Carretero, F. García, P. de Miguel, F. Pérez
Lenguaje de definición de interfaces
• Una interfaz especifica un nombre de servicio que utilizan los
clientes y servidores
• Nombres de procedimientos y parámetros (entrada y salida).
• Los compiladores pueden diseñarse para que los clientes y
servidores se escriban en lenguajes diferentes.
• Tipos de RPC
– Integrado con un lenguaje de programación (Cedar, Argus)
– Lenguaje de definición de interfaces específico para describir
las interfaces entre los clientes y los servidores (RPC de Sun
y RPC de DCE)
Sistemas operativos: una visión aplicada
70
© J. Carretero, F. García, P. de Miguel, F. Pérez
Transferencia de parámetros
• Una de las funciones de los resguardos es empaquetar los
parámetros en un mensaje: aplanamiento (marshalling)
• Problemas en la representación de los datos
– Servidor y cliente pueden ejecutar en máquinas con
arquitecturas distintas
– Transmisión con un formato estándar:
• XDR (external data representation) es un estándar que define
la representación de tipos de datos
– El receptor se encarga de la conversión (CORBA).
• Problemas con los punteros
– Una dirección sólo tiene sentido en un espacio de direcciones
Sistemas operativos: una visión aplicada
71
© J. Carretero, F. García, P. de Miguel, F. Pérez
Aplanamiento
SISTEMA CLIENTE
SISTEMA SERVIDOR
PROCEDIMIENTOS
CÓDIGO DE LA APLICACIÓN
Procedimiento(”ABC”, 123, 12.34)
Procedimiento(”ABC”, 123, 12.34)
RESGUARDO
SERVIDOR
RESGUARDO
CLIENTE
aplanamiento
mensaje
A
B
C
A
123 12.34
C
123 12.34
Extrae los
parámetros
Tira de bytes
Sistemas operativos: una visión aplicada
B
72
© J. Carretero, F. García, P. de Miguel, F. Pérez
Enlace dinámico (Binding)
• Enlace dinámico: permite localizar objetos con nombre en un
sistema distribuido, en concreto, servidores que ejecutan las
RPC.
• Tipos de enlace:
– Enlace no persistente: la conexión entre el cliente y el
servidor se establece en cada RPC.
– Enlace persistente: la conexión se mantiene después de la
primera RPC.
• Útil en aplicaciones con muchas RPC repetidas
• Problemas si lo servidores cambian de lugar
Sistemas operativos: una visión aplicada
73
© J. Carretero, F. García, P. de Miguel, F. Pérez
Enlazador dinámico
• Enlazador dinámico (binder): Es el servicio que mantiene una
tabla de traducciones entre nombres de servicio y direcciones.
Incluye funciones para:
– Registrar un nombre de servicio
– Eliminar un nombre de servicio
– Buscar la dirección correspondiente a un nombre de servicio
• Como localizar al enlazador dinámico:
– Ejecuta en una dirección fija de un computador fijo.
– El sistema operativo se encarga de indicar su dirección
– Difundiendo un mensaje (broadcast) cuando los procesos
comienzan su ejecución.
Sistemas operativos: una visión aplicada
74
© J. Carretero, F. García, P. de Miguel, F. Pérez
Establecimiento de la comunicación en una RPC
Máquina A
1. Registrar
procedimiento
Servidor
de nombres
Máquina B
servidor
5. Dar de baja
procedimiento
3. Dirección
del servidor
2. Buscar
servidor
Máquina C
4. Ejecutar
procedimiento
servidor
Sistemas operativos: una visión aplicada
75
© J. Carretero, F. García, P. de Miguel, F. Pérez
Semántica de las RPC en presencia de fallos
• Problemas que pueden plantear las RPC
– El cliente no es capaz de localizar al servidor
– Se pierde el mensaje de petición del cliente al servidor
– Se pierde el mensaje de respuesta del servidor al cliente
– El servidor falla después de recibir una petición
– El cliente falla después de enviar una petición
Sistemas operativos: una visión aplicada
76
© J. Carretero, F. García, P. de Miguel, F. Pérez
Cliente no puede localizar al servidor
•
•
•
•
El servidor puede estar caído
El cliente puede estar usando una versión antigua del servidor
La versión ayuda a detectar accesos a copias obsoletas
Cómo indicar el error al cliente
– Devolviendo un código de error (-1)
• No es transparente
– Ejemplo: sumar(a,b)
– Elevando una excepción
• Necesita un lenguaje que tenga excepciones
Sistemas operativos: una visión aplicada
77
© J. Carretero, F. García, P. de Miguel, F. Pérez
Pérdida de mensajes del cliente
• Es la más fácil de tratar
• Se activa una alarma (timeout) después de enviar el mensaje
• Si no se recibe una respuesta se retransmite
Sistemas operativos: una visión aplicada
78
© J. Carretero, F. García, P. de Miguel, F. Pérez
Pérdidas en los mensajes de respuesta
• Más difícil de tratar
• Se pueden emplear alarmas y retransmisiones, pero:
– ¿Se perdió la petición?
– ¿Se perdió la respuesta?
– ¿El servidor va lento?
• Algunas operaciones pueden repetirse sin problemas
(operaciones idempotentes)
– Una transferencia bancaria no es idempotente
• Solución con operaciones no idempotentes es descartar
peticiones ya ejecutadas
– Un nº de secuencia en el cliente
– Un campo en el mensaje que indique si es una petición
original o una retransmisión
Sistemas operativos: una visión aplicada
79
© J. Carretero, F. García, P. de Miguel, F. Pérez
Fallos en los servidores
• El servidor no ha llegado a ejecutar la operación
– Se podría retransmitir
• El servidor ha llegado a ejecutar la operación
• El cliente no puede distinguir los dos
• ¿Qué hacer?
– No garantizar nada
– Semántica al menos una vez
• Reintentar y garantizar que la RPC se realiza al menos una vez
• No vale para operaciones no idempotentes
– Semántica a lo más una vez
• No reintentar, puede que no se realice ni una sola vez
– Semántica de exactamente una
• Sería lo deseable
Sistemas operativos: una visión aplicada
80
© J. Carretero, F. García, P. de Miguel, F. Pérez
Fallos en los clientes
• La computación está activa pero ningún cliente espera los
resultados (computación huérfana)
– Gasto de ciclos de CPU
– Si cliente rearranca y ejecuta de nuevo la RPC se pueden
crear confusiones
Sistemas operativos: una visión aplicada
81
© J. Carretero, F. García, P. de Miguel, F. Pérez
Aspectos de implementación
• Protocolos RPC
– Orientados a conexión
• Fiabilidad se resuelve a bajo nivel, peor rendimiento
– No orientados a conexión
– Uso de un protocolo estándar o un específico
• Algunos utilizan TCP o UDP como protocolos básicos
Sistemas operativos: una visión aplicada
82
© J. Carretero, F. García, P. de Miguel, F. Pérez
Programación con un paquete de RPC
• El programador debe proporcionar:
– La definición de la interfaz (idl)
• Nombres de las funciones
• Parámetros que el cliente pasa al servidor
• Resultados que devuelve el servidor al cliente
– El código del cliente
– El código del servidor
• El compilador de idl proporciona:
– El resguardo del cliente
– El resguardo del servidor
Sistemas operativos: una visión aplicada
83
© J. Carretero, F. García, P. de Miguel, F. Pérez
Programación con RPC
DESARROLLO
DE LA
INTERFAZ
FICHERO
DE DEFINICIÓN
DE INTERFAZ
COMPILADOR IDL
CABECERA
SUPLENTE
EN CLIENTE
FICHEROS
FUENTE DEL
CLIENTE
COMPILADOR C
CABECERA
CABECERA
COMPILADOR C
OBJETO
SUPLENTE
EN CLIENTE
DESARROLLO
DEL
CLIENTE
Sistemas operativos: una visión aplicada
FICHEROS
OBJETO DEL
CLIENTE
SUPLENTE
EN SERVIDOR
FICHEROS
FUENTE DEL
SERVIDOR
COMPILADOR C
COMPILADOR C
BIBLIOT.
RPC
BIBLIOT.
RPC
FICHEROS
OBJETO DEL
SERVIDOR
MONTADOR
MONTADOR
EJECUTABLE
DEL
CLIENTE
EJECUTABLE
DEL
SERVIDOR
84
OBJETO
SUPLENTE
EN SERVIDOR
DESARROLLO
DEL
SERVIDOR
© J. Carretero, F. García, P. de Miguel, F. Pérez
Ejemplos de paquetes de RPC
• RPC de Sun (1990) utilizado en NFS
• RPC del proyecto ANSA (1989) desarrollado por Architecture
Project Management Ltd. (Cambridge, Inglaterra)
• RPC de DCE (1990), estándar desarrollado por Open Software
Foundation
Sistemas operativos: una visión aplicada
85
© J. Carretero, F. García, P. de Miguel, F. Pérez
RPC de Sun
• Utiliza como lenguaje de definición de interfaz XDR:
– Una interfaz contiene un nº de programa y un nº de versión.
– Cada procedimiento específica un nombre y un nº de
procedimiento
– Los procedimientos sólo aceptan un parámetro.
– Los parámetros de salida se devuelven mediante un único
resultado
– El lenguaje ofrece una notación para definir:
•
•
•
•
constantes
definición de tipos
estructuras, uniones
programas
Sistemas operativos: una visión aplicada
86
© J. Carretero, F. García, P. de Miguel, F. Pérez
RPC de Sun
• rpcgen es el compilador de interfaces que genera:
– Suplente del cliente
– Suplente del servidor y procedimiento principal del servidor.
– Procedimientos para el aplanamiento (marshalling)
– Fichero de cabecera (.h) con los tipos y declaración de
prototipos.
• Enlace dinámico
– El cliente debe especificar el host donde ejecuta el servidor
– El servidor se registra (nº de programa, nº de versión y nº de
puerto) en el portmapper local
– El cliente envía una petición al portmapper del host donde
ejecuta el servidor
Sistemas operativos: una visión aplicada
87
© J. Carretero, F. García, P. de Miguel, F. Pérez
Ejemplo
Máquina A
cliente
Máquina B
sumar(5,2)
servidor
5+2
NÚCLEO
Restulado = 7
NÚCLEO
RED
Sistemas operativos: una visión aplicada
88
© J. Carretero, F. García, P. de Miguel, F. Pérez
Esquema de la aplicación
cliente.c
Archivos para
el cliente
suma_clnt.c
suma_xdr.c
repcgen
Archivos
comunes
suma.x
suma.h
suma_svc.c
Archivos para
el servidor
servidor.c
Sistemas operativos: una visión aplicada
89
© J. Carretero, F. García, P. de Miguel, F. Pérez
suma.x
struct peticion {
int a;
int b;
};
program SUMAR {
version SUMAVER {
int SUMA(peticion) = 1;
} = 1;
} = 99;
Sistemas operativos: una visión aplicada
90
© J. Carretero, F. García, P. de Miguel, F. Pérez
suma.h
#ifndef _SUMA_H_RPCGEN
#define _SUMA_H_RPCGEN
#include <rpc/rpc.h>
struct peticion {
int a;
int b;
};
#define
#define
extern
extern
SUMAVER ((u_long)99)
SUMA ((u_long)1)
int * suma_1(peticion *, CLIENT *);
int * suma_1_svc(peticion *, struct svc_req *);
#endif /* !_SUMA_H_RPCGEN */
Sistemas operativos: una visión aplicada
91
© J. Carretero, F. García, P. de Miguel, F. Pérez
servidor.c
#include "suma.h"
int *suma_1_svc(peticion *argp, struct svc_req *rqstp)
{
static int result;
result = argp->a + argp->b;
return(&result);
}
Sistemas operativos: una visión aplicada
92
© J. Carretero, F. García, P. de Miguel, F. Pérez
cliente.c
#include "suma.h"
main( int argc, char* argv[] )
{
CLIENT *clnt;
int *res;
peticion suma_1_arg;
char *host;
if(argc < 2) {
printf("usage: %s server_host\n", argv[0]);
exit(1);
}
host = argv[1];
Sistemas operativos: una visión aplicada
93
© J. Carretero, F. García, P. de Miguel, F. Pérez
cliente.c II
/* localiza al servidor */
clnt = clnt_create(host, SUMAR, SUMAVER, "udp");
if (clnt == NULL) {
clnt_pcreateerror(host);
exit(1);
}
suma_1_arg.a = 5;
suma_1_arg.b = 2;
res = suma_1(&suma_1_arg, clnt);
if (res == NULL) {
clnt_perror(clnt, "call failed:");
}
printf("La suma es %d\n", *res);
clnt_destroy( clnt );
}
Sistemas operativos: una visión aplicada
94
© J. Carretero, F. García, P. de Miguel, F. Pérez
Contenido
• Sistemas distribuidos
• Sistemas operativos distribuidos
• Comunicación de procesos
• Sincronización de procesos
• Gestión de procesos
• Sistemas de archivos
• Gestión de memoria
Sistemas operativos: una visión aplicada
95
© J. Carretero, F. García, P. de Miguel, F. Pérez
Relojes lógicos
• En ausencia de un reloj global la relación causa-efecto (precede
a) es la única posibilidad de ordenar eventos
• Relación de precedencia (Lamport)
– Si a y b son dos eventos del mismo proceso y a ocurrió antes
que b, entonces a Y b
– Si a=send(m) y b=receive(m), entonces a Y b
– La relación es transitiva
• Dos eventos son concurrentes (a || b) si no se puede deducir
entre ellos una relación de causalidad potencial
Sistemas operativos: una visión aplicada
96
© J. Carretero, F. García, P. de Miguel, F. Pérez
Relojes lógicos (algoritmo de Lamport)
•
•
•
•
•
Útiles para ordenar eventos en ausencia de un reloj común.
Algoritmo de Lamport (1978)
Cada proceso P mantiene una variable entera RLp (reloj lógico)
Cuando un proceso P genera un evento, RLp=RLp+1
Cuando un proceso envía un mensaje m a otro le añade el valor
de su reloj
• Cuando un proceso Q recibe un mensaje m con un valor de
tiempo t, el proceso actualiza su reloj, RLq=max(RLq,t)
• El algoritmo asegura que si a Y b entonces RL(a) < RL(b)
Sistemas operativos: una visión aplicada
97
© J. Carretero, F. García, P. de Miguel, F. Pérez
Mantenimiento de los relojes lógicos
Sistemas operativos: una visión aplicada
98
© J. Carretero, F. García, P. de Miguel, F. Pérez
Relojes lógicos totalmente ordenados
• Los relojes lógicos de Lamport imponen sólo una relación de
orden parcial:
– Eventos de distintos procesos pueden tener asociado una
misma marca de tiempo.
• Se puede extender la relación de orden para conseguir una
relación de orden total añadiendo el nº de proceso
– (Ta, Pa): marca de tiempo del evento a del proceso P
• (Ta, Pa) < (Tb, Pb) sí y solo si
– Ta < Tb o
– Ta=Tb y Pa<Pb
Sistemas operativos: una visión aplicada
99
© J. Carretero, F. García, P. de Miguel, F. Pérez
Problemas de los relojes lógicos
• No bastan para caracterizar la causalidad
– Dados RL(a) y RL(b) no podemos saber:
• si a precede a b
• si b precede a a
• si a y b son concurrentes
• Se necesita una relación (F(e), <) tal que:
– a Y b si y sólo si F(a) < F(b)
– Los relojes vectoriales permiten representar de forma precisa
la relación de causalidad potencial
Sistemas operativos: una visión aplicada
100
© J. Carretero, F. García, P. de Miguel, F. Pérez
Relojes vectoriales
• Desarrollado independientemente por Fidge, Mattern y Schmuck
• Todo proceso lleva asociado un vector de enteros RV
• RVi[a] es el valor del reloj vectorial del proceso i cuando
ejecuta el evento a.
• Mantenimiento de los relojes vectoriales
– Inicialmente RVi= 0
– Cuando un proceso i genera un evento
• RVi[i ] = RVi[i ] +1
– Todos los mensajes llevan el RV del envío
– Cuando un proceso j recibe un mensaje con RV
• RVj = max(RVj , RV ) (componente a componente)
• RVj[j ] = RVj[j ] +1 (evento de recepción)
Sistemas operativos: una visión aplicada
101
© J. Carretero, F. García, P. de Miguel, F. Pérez
Relojes vectoriales
P0
(1,0,0)
(2,1,0)
(3,1,2)
(4,1,2)
(5,1,2)
(1,2,3)
P1
(4,3,3)
(0,1,0)
P2
(1,0,1)
Sistemas operativos: una visión aplicada
(1,0,2)
102
(1,0,3)
(1,0,4)
(5,1,5)
© J. Carretero, F. García, P. de Miguel, F. Pérez
Propiedades de los relojes vectoriales
• RV < RV´ si y solo si
– RV  RV´ y
– RV[i ]  RV´[i ],  i
• Dados dos eventos a y b
– a precede a b si y solo si RV(a) < RV(b)
• Si a es un evento del proceso i y b es un evento del proceso j
(con i  j)
– a precede a b si y solo si RV(a)[i ]  RV(b)[i ]
• RV(a)[i ] = RV(b)[i ] cuando a es el evento de envío a j y b es
el evento de recepción.
– a y b son concurrentes si y solo si
• RV(a)[i ] > RV(b)[i ]
Sistemas operativos: una visión aplicada
y RV(b )[j ] > RV(b)[j ]
103
© J. Carretero, F. García, P. de Miguel, F. Pérez
Exclusión mutua distribuida
• Los procesos ejecutan el siguiente fragmento de código
entrada()
SECCIÓN CRÍTICA
salida()
• Requisitos para resolver el problema de la sección crítica
– Exclusión mutua
– Progreso
– Espera acotada
• Algoritmos
– Algoritmo centralizado
– Algoritmo distribuido
– Anillo con testigo
Sistemas operativos: una visión aplicada
104
© J. Carretero, F. García, P. de Miguel, F. Pérez
Algoritmo centralizado
• Existe un proceso coordinador
0
2
1
0
1
2
0
salida
entrada
entrada
OK
C
Sistemas operativos: una visión aplicada
1
2
OK
No hay respuespuesta
(bloquea al cliente)
C
105
C
© J. Carretero, F. García, P. de Miguel, F. Pérez
Anillo con testigo
• Los procesos se ordenan conceptualmente como un anillo.
• Por el anillo circula un testigo.
• Cuando un proceso quiere entrar en la SC debe esperar a recoger
el testigo
• Cuando sale de la SC envía el testigo al nuevo proceso del anillo
testigo
1
2
6
3
5
4
Sistemas operativos: una visión aplicada
106
© J. Carretero, F. García, P. de Miguel, F. Pérez
Algoritmo distribuido
• Algoritmo de Ricart y Agrawala requiere la existencia un orden
total de todos los mensajes en el sistema
• Un proceso que quiere entrar en una sección crítica (SC) envía
un mensaje a todos los procesos (y a él mismo)
• Cuando un proceso recibe un mensaje
– Si el receptor no está en la SC ni quiere entrar envía OK al
emisor
– Si el receptor ya está en la SC no responde
– Si el receptor desea entrar, compara la marca de tiempo del
mensaje. Si el mensaje tiene una marca menor envía OK. En
caso contrario entra y no envía nada.
• Cuando un proceso recibe todos los mensajes puede entrar
Sistemas operativos: una visión aplicada
107
© J. Carretero, F. García, P. de Miguel, F. Pérez
Contenido
•
•
•
•
Sistemas distribuidos
Sistemas operativos distribuidos
Comunicación de procesos
Sincronización de procesos
• Gestión de procesos
• Sistemas de archivos
• Gestión de memoria
Sistemas operativos: una visión aplicada
108
© J. Carretero, F. García, P. de Miguel, F. Pérez
Modelos de sistema
• Conjunto de estaciones de trabajo
– El sistema consta de estaciones de trabajo a las que tienen
acceso los usuarios.
• Pool de procesadores
– Los usuarios con terminales.
– Los procesos se envían a procesadores de un pool.
• Modelo híbridos
– Trabajos interactivos en las estaciones de trabajo.
– Trabajos no interactivos en en el pool de procesadores.
Sistemas operativos: una visión aplicada
109
© J. Carretero, F. García, P. de Miguel, F. Pérez
Asignación de procesadores
• Objetivo: decidir en qué procesador se debería ejecutar un
proceso para equilibrar la carga y optimizar el rendimiento.
– Evitar que un nodo esté inactivo mientras hay procesos
esperando a ejecutar.
• Suposiciones:
– Todos los procesadores son compatible en el código.
– La velocidad de los procesadores puede ser distinta.
– Conectividad total: cualquier procesador puede comunicarse
con cualquier otro.
Sistemas operativos: una visión aplicada
110
© J. Carretero, F. García, P. de Miguel, F. Pérez
Estaciones de trabajo inactivas
• En entornos típicos con estaciones de trabajo se desperdicia
cerca del 80% de ciclos totales de CPU.
• Uso de estaciones de trabajo inactivas:
– Ejecutar procesos de forma totalmente transparente en
máquinas remotas que se encuentran inactivas .
– Los usuarios de las estaciones de trabajo inactivas no
deberían observar una degradación del rendimiento como
consecuencia de la ejecución de procesos remotos.
Sistemas operativos: una visión aplicada
111
© J. Carretero, F. García, P. de Miguel, F. Pérez
Empleo de estaciones de trabajo inactivas
• ¿Qué es una estación de trabajo inactiva?
– Una que lleva varios minutos sin recibir entrada del teclado o
ratón y que no está ejecutando procesos interactivos.
• ¿Cómo localizar estaciones inactivas?
– Dirigidas por el servidor: la estación inactiva anuncia su
disponibilidad.
– Dirigida por el cliente: un cliente envía un mensaje al resto
para localizar una estación inactiva.
Sistemas operativos: una visión aplicada
112
© J. Carretero, F. García, P. de Miguel, F. Pérez
Estrategias para localizar una estación inactiva
Tengo poca carga.
Podéis mandarme procesos
Tengo mucha carga.
Busco estación inactiva
Nodo
Nodo
(a)
Sistemas operativos: una visión aplicada
(b)
113
© J. Carretero, F. García, P. de Miguel, F. Pérez
Algoritmos de distribución de la carga
•
•
•
•
Política de transferencia: determina cuando transferir.
Política de selección: selecciona el proceso a transferir.
Política de ubicación: selecciona el nodo al que transferir.
Política de información: decide cuándo, desde dónde y qué
información sobre otros nodos recoger.
Sistemas operativos: una visión aplicada
114
© J. Carretero, F. García, P. de Miguel, F. Pérez
Planificación de procesos en sistemas distribuidos
• Definición del problema:
– Dado un conjunto de tareas con ciertas restricciones de
precedencia y requisitos de cálculo y comunicación,
– Dado un conjunto de procesadores conectados por una red de
interconexión,
– Encontrar la asignación de tareas a procesadores y el orden
de ejecución con el objetivo de minimizar el tiempo de
ejecución total.
Sistemas operativos: una visión aplicada
115
© J. Carretero, F. García, P. de Miguel, F. Pérez
Planificación de procesos
Sistemas operativos: una visión aplicada
116
© J. Carretero, F. García, P. de Miguel, F. Pérez
Complejidad del problema
• El problema en su forma general es NP-completo
• Algoritmos con complejidad polinomial:
– Cuando sólo hay dos procesadores.
• En el caso general se utilizan heurísticas.
• Los planificadores se eligen por 2 métricas:
– El rendimiento del plan generado.
– La eficacia del planificador: tiempo tomado por el
planificador para generar un plan.
Sistemas operativos: una visión aplicada
117
© J. Carretero, F. García, P. de Miguel, F. Pérez
Contenido
•
•
•
•
•
Sistemas distribuidos
Sistemas operativos distribuidos
Comunicación de procesos
Sincronización de procesos
Gestión de procesos
• Sistemas de archivos
• Gestión de memoria
Sistemas operativos: una visión aplicada
118
© J. Carretero, F. García, P. de Miguel, F. Pérez
Sistema de archivos distribuido
• Objetivo principal: compartir datos entre usuarios ofreciendo
transparencia
• Objetivos secundarios:
– rendimiento (debería ser comparable al de un sistema
tradicional)
– tolerancia a fallos
– disponibilidad
Sistemas operativos: una visión aplicada
119
© J. Carretero, F. García, P. de Miguel, F. Pérez
Arquitectura
......................
Cliente
Cliente
RED DE INTERCONEXIÓN
Servidor
CTR
........
.....
Sistemas operativos: una visión aplicada
Servidor
......................
CTR
CTR
.....
.....
120
........
CTR
.....
© J. Carretero, F. García, P. de Miguel, F. Pérez
Componentes
• Servicio de directorio:
– Gestión de los nombres de los archivos
– Objetivo: ofrecer un espacio de nombres único
• Servicio de archivos:
– Proporciona acceso a los datos de los archivos
Sistemas operativos: una visión aplicada
121
© J. Carretero, F. García, P. de Miguel, F. Pérez
Métodos de accesos remotos
• Modelo carga/descarga
– Transferencias completas del fichero
– Localmente se almacenan en memoria o discos locales
– Normalmente utilizan semántica de sesión
– Eficiencia en las transferencias
– Llamada open con mucha latencia
– Múltiples copias de un fichero
• Modelo de servicios remotos
– El servidor debe proporcionar todas las operaciones sobre el fichero.
– Acceso por bloques
– Modelo cliente/servidor
• Empleo de cache en el cliente
– Combina los dos modelos anteriores.
Sistemas operativos: una visión aplicada
122
© J. Carretero, F. García, P. de Miguel, F. Pérez
Tipos de servidores
• Servidores con estado
– Cuando se abre un fichero, el servidor almacena información
y da al cliente un identificador único a utilizar en las
posteriores llamadas
– Cuando se cierra un fichero se libera la información
• Servidores sin estado
– Cada petición es autocontenida (fichero y posición)
Sistemas operativos: una visión aplicada
123
© J. Carretero, F. García, P. de Miguel, F. Pérez
Tipos de servidores II
• Ventajas de los servidores con estado
– Mensajes de petición más cortos
– Mejor rendimiento (se mantiene información en memoria)
– Facilita la lectura adelantada. El servidor puede analizar el
patrón de accesos que realiza cada cliente
– Es necesario en invalidaciones iniciadas por el servidor
• Ventajas de los servidores sin estado
– Más tolerante a fallos
– No son necesarios open y close. Se reduce el nº de mensajes
– No se gasta memoria en el servidor para almacenar el estado
Sistemas operativos: una visión aplicada
124
© J. Carretero, F. García, P. de Miguel, F. Pérez
Cache de bloques
• El empleo de cache de bloques permite mejorar el rendimiento
– Explota el principio de proximidad de referencias
• Proximidad temporal
• Proximidad espacial
– Lecturas adelantadas
• Mejora el rendimiento de las operaciones de lectura, sobre todo
si son secuenciales
– Escrituras diferidas
• Mejora el rendimiento de las escrituras
• Otros tipos de cache
– Cache de nombres
– Cache de metadatos del sistema de ficheros
Sistemas operativos: una visión aplicada
125
© J. Carretero, F. García, P. de Miguel, F. Pérez
Localización de las cache en un SFD
• Cache en los servidores
– Reducen los accesos a disco
• Cache en los clientes
– Reducen el tráfico por la red
– Reducen la carga en los servidores
– Mejora la capacidad de crecimiento
– Dos posibles localizaciones
• En discos locales
– Más capacidad,
– Más lento
– No volátil, facilita la recuperación
• En memoria principal
– Menor capacidad
– Más rápido
– Memoria volátil
Sistemas operativos: una visión aplicada
126
© J. Carretero, F. García, P. de Miguel, F. Pérez
Tamaño de la unidad de cache
• Mayor tamaño puede incrementar la tasa de aciertos y mejorar la
utilización de la red pero
– Aumentan los problemas de coherencia
• Depende de las características de las aplicaciones
• En memoria cache grandes
– Es beneficioso emplear bloques grandes (8 KB y más)
• En memorias pequeñas
– El uso de bloques grandes es menos adecuado
Sistemas operativos: una visión aplicada
127
© J. Carretero, F. García, P. de Miguel, F. Pérez
Políticas de actualización
• Escritura inmediata (write-through)
– Buena fiabilidad
– En escrituras se obtiene el mismo rendimiento que en el
modelo de accesos remotos
– Las escrituras son más lentas
• Escritura diferida (write-back)
– Escrituras más rápidas. Se reduce el tráfico en la red
– Los datos pueden borrarse antes de ser enviados al servidor
– Alternativas
• Volcado (flush) periódico (Sprite)
• Write-on-close
Sistemas operativos: una visión aplicada
128
© J. Carretero, F. García, P. de Miguel, F. Pérez
Problema de la coherencia de cache
• El uso de cache en los clientes de un sistema de ficheros
introduce el problema de la coherencia de cache:
– Múltiples copias.
• El problema surge cuando se coutiliza un fichero en escritura:
– Coutilización en escritura secuencial
• Típico en entornos y aplicaciones distribuidas.
– Coutilización en escritura concurrente
• Típico en aplicaciones paralelas.
Sistemas operativos: una visión aplicada
129
© J. Carretero, F. García, P. de Miguel, F. Pérez
Soluciones al problema de la coherencia
• No emplear cache en los clientes.
– Solución trivial que no permite explotar las ventajas del uso de
cache en los clientes (reutilización, lectura adelantada y escritura
diferida)
• No utilizar cache en los clientes para datos compartidos en escritura
(Sprite).
– Accesos remotos sobre una única copia asegura semántica UNIX
• Mecanismos de cache sin replicación de datos
– Basado en esquemas cooperativos que definen un único espacio
global formado por la unión de todas las cache del sistema.
– Los datos fluyen a través de las caches sin replicación
• Empleo de protocolos de coherencia de cache
Sistemas operativos: una visión aplicada
130
© J. Carretero, F. García, P. de Miguel, F. Pérez
Contenido
•
•
•
•
•
•
Sistemas distribuidos
Sistemas operativos distribuidos
Comunicación de procesos
Sincronización de procesos
Gestión de procesos
Sistemas de archivos
• Gestión de memoria
Sistemas operativos: una visión aplicada
131
© J. Carretero, F. García, P. de Miguel, F. Pérez
Uso de paginadores externos
Nodo A
Nodo B
Paginador externo
Transferir página
Espacio de
direcciones
del proceso
Fallos de página
Mensajes
Núcleo
Sistemas operativos: una visión aplicada
Núcleo
132
© J. Carretero, F. García, P. de Miguel, F. Pérez
Memoria compartida distribuida
Nodo A
Nodo B
Nodo C
proceso
proceso
proceso
Memoria compartida distribuida
Memoria
física
Memoria
física
Memoria
física
Red de interconexión
Sistemas operativos: una visión aplicada
133
© J. Carretero, F. García, P. de Miguel, F. Pérez
Características
• Se construye utilizando paso de mensajes.
• Modelo de programación más sencillo, no es necesario el paso
de mensajes.
• Sincronización utilizando construcciones tradicionales
(semáforos, mutex, ...).
• ¿Rendimiento?
– Los accesos a memoria no son siempre locales
• Modelos:
– Basado en hardware (arquitectura NUMA).
– Basado en páginas.
– Basado en objetos
Sistemas operativos: una visión aplicada
134
© J. Carretero, F. García, P. de Miguel, F. Pérez
Implementación
• Replicación y caching (igual que los sistemas de ficheros)
• Las escrituras se realizan localmente
• Aparece un problema en el acceso a variables compartidas (en
escritura).
• Problema idéntico a la coherencia de cache
Sistemas operativos: una visión aplicada
135
© J. Carretero, F. García, P. de Miguel, F. Pérez
Descargar

Sistemas Distribuidos - General | Universidad de Congreso