Diseño de Sistemas Operativos

Manuel García García

7 de junio de 2012

1

Índice

I Introducción 5

1. Introducción: 51.1. historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2. Distribuciones Linux . . . . . . . . . . . . . . . . . . . . . . . . . 6

2. Características de los Sistemas Operativos 6

3. Fases de diseño de un S.O. 73.1. Estructura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.2. Fases de arranque del S.O. . . . . . . . . . . . . . . . . . . . . . . 73.3. Plani�cación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.3.1. Los plani�cadores pueden ser: . . . . . . . . . . . . . . . . 73.3.2. Para evitar tocar cosas en el mismo sitio tenemos: . . . . 8

3.4. Direccionamiento virtual: . . . . . . . . . . . . . . . . . . . . . . 83.5. Llamadas al sistema . . . . . . . . . . . . . . . . . . . . . . . . . 83.6. Decisiones a tomar en el diseño de un kernel . . . . . . . . . . . . 9

3.6.1. Tolerancia a fallos y seguridad . . . . . . . . . . . . . . . 93.6.2. Protección basada en hardware vs protección basada en

software . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.6.3. Microkernels y kernels monolíticos . . . . . . . . . . . . . 11

II Dispositivos, bu�ers y cachés 13

4. Caché de datos. 14

5. Organización de un bu�er-caché. 14

6. Algoritmos del kernel para manejo del bu�er-caché. 15

7. Lectura/escritura de bloques en dispositivos 157.1. Elementos básicos . . . . . . . . . . . . . . . . . . . . . . . . . . 157.2. Plani�cador de E/S . . . . . . . . . . . . . . . . . . . . . . . . . . 16

7.2.1. Conceptos básicos . . . . . . . . . . . . . . . . . . . . . . 167.2.2. Tipos de plani�cadores . . . . . . . . . . . . . . . . . . . . 16

III Sistemas de Ficheros 18

8. Representación interna y almacenamiento de los sistemas de�cheros 18

9. Llamadas al sistema para el sistema de �cheros 19

2

IV Procesos 23

10.Organización y gestión de procesos 24

11.Estados y transiciones de estado de los procesos 24

12.Memoria para la gestión de procesos 25

13.Llamadas al sistemas para la gestión de procesos 25

14.Plani�cación de procesos 26

V Memoria 30

15.Hardware 3015.1. Modo real . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3015.2. Modo protegido . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3015.3. Modo PAE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3115.4. Long mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3115.5. Modo page . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

16.Memoria en el kernel y zonas de memoria 32

17.SLAB 32

18.El espacio direccionable de proceso 34

19.SWAP 3519.1. Paginación bajo demanda (lazy loading) . . . . . . . . . . . . . . 3619.2. Paginación anticipatoria . . . . . . . . . . . . . . . . . . . . . . . 36

VI Comunicación entre procesos 36

20.Traza de procesos 36

21.Paso de mensajes. SYSTEM V IPC 3721.1. Deadlock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3821.2. Livelock . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3921.3. SYSTEM V IPC . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

22.Memoria compartida 40

23.Semáforos 40

3

Índice de �guras

1. Arquitectura de anillos . . . . . . . . . . . . . . . . . . . . . . . . 102. inodos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193. Estados de los procesos . . . . . . . . . . . . . . . . . . . . . . . 254. Slab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335. Uso de ptrace . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4

Parte I

Introducción

1. Introducción:

1.1. historia

1965 Laboratorios Bell: sistemas operativos multiusuario.

1969 Multics.

Ken Thompson y Dennis Ritchie PDP-7

1971 PDP-11

Fortran y BCPL → B → C

1973 Implementaron UNIX en C

1977 500 sistemas UNIX (125 eran universidades)

1977-82 Bell Unix System III

1977-86 ATT y Universidad de California Berkeley: desarrollo de BSD (Berke-ley Software Distribution)

1980 Richard Stallman estaba en el MIT y la impresora (Xerox 9700) veníasin código fuente y se pilló un rebote y entonces empezó con el movimientodel software libre.

1983 Stallman inicia el proyecto GNU

1984 Stallman abandona el MIT

1985 Stallman publica el mani�esto GNU

1985 Unix System V

1987 Tannenbaum crea Minix (con �nes educativos)

1989 Stallman crea la licencia GPL (aplicado a editores de texto, compi-ladores y debugers)

1989 La universidad de California crea NET/1 (reescribiendo el código de4.3 BSD que era de ATT)

1991 La universidad de California saca Net/2 y ATT les demanda

1991 Linus Torvalds inicia el desarrollo de Linux a partir de herramientaslibres

5

1994 4.4 BSD Enumbered (para los que quisieran pagar a ATT) y 4.4 BSDLite

1995 4.4 BSD Lite Release 2 (ya continuando sin ATT)

De ahí salieron FreeBSD, NetBSD, OpenBSD, Dragon�yBSD, ...

Las licencias de BSD permiten coger código de ahí y cerrarlo, comopor ejemplo:

Windows: TCP/IP

Darwin (kernel de OS/X, antiguo MacOS) está basado en 4.4 BSDLite 2 y FreeBSD

Solaris utiliza código BSD

1.2. Distribuciones Linux

Slackware (1993 - )

Debian (1993 - ) Muy puristas y muy libres

Ubuntu (2004 - )

Linux Mint

SuSE (1994 - )

openSuSE (2005 - ) comprada por Novell (2003)

RedHat (1995 - )

Fedora (2003 - )

Mandriva (2005 - ) / [Mandrake (1998 - ) / Conectiva (1995 - 2005)]

Knoppix (2000 - )

2. Características de los Sistemas Operativos

Un S.O. es el responsable de gestionar y coordinar la compartición de re-cursos limitada de que se disponen através de llamadas al sistema. Un usuarioaccede a la UI (User Interface), ya sea GUI (Graphical User Interface) o CLI(Command Line Interface). Entre los servicios que provee un kernel:

Controlar la ejecución de procesos permitiendo:

• Creación

• Terminación

6

• Suspensión

• Comunicación

• ...

Plani�car los procesos de forma adecuada para su ejecución en la CPU

Reservar memoria principal para un proceso en ejecución.

• Si el kernel escribe procesos enteros a swap, el sistema operativo sedice que es un SO �con swapeo�

• Si escribe páginas a memoria swap, se llama un sistema paginable(paging system)

Reservar memoria secundaria para almacenamiento y obtención e�cientede datos de usuario: sistema de �cheros.

Permite a los procesos controlar los dispositivos perifericos terminales,unidades de cinta/disco, interfaces de red, usb, etc...

3. Fases de diseño de un S.O.

3.1. Estructura

AplicacionesResto del S.O.

KernelFirmwareHardware

3.2. Fases de arranque del S.O.

El boot loader empieza ejecutando el kernel en modo supervisor.

El kernel se inicializa y ejecuta el proceso init en espacio de usuario. init Xlanza los scripts que hay en /etc/rcX.d/.

El kernel prepara un espacio de direcciones para el proceso, carga el códigode la aplicación en memoria, reserva una pila y pasa la ejecución a unadirección dentro del proceso para ser ejecutado.

3.3. Plani�cación

3.3.1. Los plani�cadores pueden ser:

expropiativos: ceden el control de la CPU a los procesos durante un tiempo.

no expropiativos: esperan a que los procesos acaben.

7

3.3.2. Para evitar tocar cosas en el mismo sitio tenemos:

mutex: lo que ya sabemos to el mundo

spinlock: igual que un mutex, pero se queda en un bucle activo

3.4. Direccionamiento virtual:

Paginación: memoria virtual / swap, paginación por demanda...

Segmentación

El kernel del sistema operativo está rulando en un espacio de memoria distintode los procesos de usuario. Estos dos espacios son:

Espacio de kernel

Espacio de usuario

No obstante, cuando un proceso quiere acceder a un dispositivo, esto ha deejecutarse en el espacio de kernel, donde se ejecutarán los módulos (drivers) deLinux.

3.5. Llamadas al sistema

El sistema operativo provee de librerías para ser llamadas por los programasde usuario. Estos, han de linkar las librerías proveidas por el sistema:

Linkado estático: se copian las funciones de la librería al programa, de estaforma el ejecutable �nal tiene las funciones de la librería. En linux: .a

Linkado dinámico: se pone una referencia de dónde está la librería, y se poneen memoria dinámicamente. En tiempo de compilación, será más lento,ya que hay que ir a buscar la librería y cargarla en memoria. Sin embar-go, la corrección de errores en la librería no implica la recompilación delprograma, y también el programa ocupa menos. En linux: .so (libc.so)

Formas de hacer una llamada al sistema

Usar una interrupción por software (como la int 21 en MSDOS).

Usar una puerta de enlace (call gate).

Usar una instrucción especial de la CPU para hacer system call.

Usar una cola de peticiones.

8

3.6. Decisiones a tomar en el diseño de un kernel

Es muy importante la protección frente a fallos (tolerancia a fallos) y com-portamientos maliciosos (seguridad)

Mecanismo (mechanism): es el soporte que permite la implementación devarias políticas diferentes.

Política (policy): es un modo de funcionamiento concreto, el cómo se com-porta el sistema ante un determinado problema.

Ejemplo: el sistema de acceso a un ordenador pregunta user/password. Elmecanismo es el que se encarga de validar ese user/password. La políti-ca es el cómo se hace eso, por ejemplo: comprobandolo en el archivo/etc/password, o comprobándolo en un servidor ldap, o comprobándoloen un servidor mysql. Estas son distintas políticas.

Los mecanismos y políticas pueden ser:

Estáticos: vienen puestos �de fábrica� y no se pueden cambiar a menos quese reconstruya todo el sistema.

Dinámicos: pueden añadirse o sustituir nuevos una vez instalados el sis-tema.

También pueden ser clasi�cados en:

Preventivos

Post-detección del problema

3.6.1. Tolerancia a fallos y seguridad

Concéptos básicos:

Principio de mínimo privilegio dada una capa de abstracción, cada módulo(proceso, usuario, etc) debe ser capaz de acceder sólo y exclusivamente ala información y recursos necesarios para su propósito legítimo, ni más, nimenos.

TCB (Trusted Computing Base) es el conjunto de componentes (HW, �rmware,SW) que son críticos para la seguridad del sistema.

Arquitectura de anillo

Direccionamiento basado en capacidades (capabilities based addressing)

System 250 (1969) de Plessey Corportation

System/38 (1978) de IBM

9

Figura 1: Arquitectura de anillos

Los privilegios de uso de la memoria están divididos en capas o anillos:

El anillo 0 es el �kernel mode� o �espacio de kernel�Aunque los SO deberían tener 4 anillos, los sistemas operativos usan menos:

Windows y Linux usan solo:

• Anillo 0 para kernel y drivers

• Anillo 3 para aplicaciones

OS/2 usa:

• Anillo 0 para kernel y drivers

• Anillo 2 para código privilegiado (accesos de entrada/salida y de red)

• Anillo 3 para aplicaciones

Hypervisor: controla el acceso HW desde el anillo 0 o desde el anillo -1 (ahícon to la potencia de ser kernel) (Intel Vanderpool, AMD Pací�ca). Algunos deellos:

vmware

virtualbox

xeni

qemu

kvm

10

3.6.2. Protección basada en hardware vs protección basada en soft-ware

Protección basada en software: El kernel sólo ejecuta código compilado�able.

Ventajas:

No necesita espacios de direcciones separados

Flexibilidad en

Desventajas:

El tiempo que tarda en ejecutarse una aplicación crece.

Tipado in�exible

3.6.3. Microkernels y kernels monolíticos

En unmicrokernel se incluyen mecanismos para abstraer el mayor númerode comportamientos posibles, e implementa las políticas en módulos o enespacio de usuario. Consisten en una capa de abstracción para el HW conun conjunto (pequeño) de syscalls para implementar los servicios (gestiónde memoria, multitarea, comunicación entre procesos, ...).

• Ventajas:◦ Es más modular, se pueden hacer cambios con facilidad.

◦ Es más seguro, los fallos estarán localizados en sitios concretos.

◦ Se pueden programar partes del kernel en distintos lenguajes (porejemplo en lenguajes de alto nivel).

◦ Se podría actualizar el kernel sin tener que pararlo.

• Inconvenientes:◦ Hay más cambios de contexto, es más �lento�.

El diseño monolítico está inducido por la protección basada en la sepa-ración de espacio de usuario/kernel. Pechá de código en plan pelotera ahía muerte.

• Ventajas:◦ Como es un tocho de código mu grande, no hay tantos cambiosde contexto.

• Inconvenientes:◦ Es un tocho de código y hacer cambios puede ser muy di�cil.

11

◦ Programación en un solo lenguaje, como por ejemplo, el kernelde Linux está hecho en C, y punto.

La solución basada en un modo privilegiado mezcla el mecanismo de pro-tección con las políticas de seguridad mientras que en un sistema basadoen capabilities se distinguen claramente y esto lleva de forma intuitiva aun sistema microkernel.

12

Parte II

Dispositivos, bu�ers y cachés

Los dispositivos se pueden categorizar en 3 tipos:

Bloques

Discos duros

Se trabaja por bloques de datos (open, read, write, close, seek).

E/S en bruto, ls.

Caracteres

Teclados, ratones, algunos dispositivos.

Se trabaja de caracter en caracter (getc, putc) (librerías para trabajarcon lineas)

Red

Ethernet, wireless, bluetooth.

Hay que usar su propio interfaz.

Si haces ls /dev/ -l verás que salen to los dispositivos que hay en el orde-nador. Los que tienen al principio una c son dispositivos de caracteres, comopor ejemplo /dev/tty0 o /dev/usbmon0

Las interfaces que un usuario puede usar para acceder a un dispositivo tam-bién se divide en 3 categorías:

Interfaz bloqueante → El SO bloquea el proceso hasta que no termine elacceso a los datos. Es lo más usado, ya que si normalmente haces unalectura, va a ser para trabajar con eso que has leido... así pues, hay queesperar a que el SO me devuelva lo que quiero

Interfaz no-bloqueante→ El SO no bloquea los procesos que quieren ac-ceder a los datos.

Interfaz asíncrona→ El proceso hace la petición al SO, el cual le da el datocuando ya haya acabado, interrumpiendo al proceso de forma asíncrona.

De�niciones

Bu�er se suele de�nir como una región de memoria que almacena datos tem-poralmente mientras son transferidos de un sitio a otro

13

Caché es un conjunto de datos que duplican unos valores originales guardadosen algún sitio o calculados con anterioridad donde los originales son cos-tosos de obtener (teniendo en cuenta el tiempo de acceso) o de calcular denuevo.

Se generan muchas peticiones de E/S.Todas las peticiones de E/S se pasan a los drivers de dispositivos con la

estructura de datos del bu�er que contiene todo lo necesario para realizar laoperación

Todos los dispositivos tienen un id. Si haces ls -l /dev/sda te sale dondedebería estar el tamaño, dos números.

brw-rw---- 1 root disk 8, 0 2012-03-14 22:07 /dev/sda

Donde aparecen los dos números debería aparecer el tamaño del archivo, perodado que /dev/sda es un dispositivo, 8, 0 es el id del dispositivo. /dev/sda1tiene como id 8, 1, /dev/sda2 tiene como id 8, 2, /dev/sdb tiene como id 8,

16...

4. Caché de datos.

5. Organización de un bu�er-caché.

El bu�er-caché se compone de dos partes funcionales:

Bu�ers libres 512 bytes, 1024, 2048, 2096, 8192

La caché una tabla hash que es un vector de punteros a cadena de bu�ers quetienen todos el mismo índice hash

Hay un LRU (Last Recently Used) por cada tipo de bu�er:

Estado de un bu�er:

BH_update Tiene datos correctos y ninguna operación pendiente.

BH_new Bu�er vacío (recién creado).

BH_lock Bu�er que está bloqueado para evitar accesos concurrentes.

BH_dirty Contiene datos nuevos que serán escritos pero cuya escritura no hasido plani�cada aún.

BH_mapped El bu�er está mapeado en memoria.

BH_Req El bu�er se está usando en una petición de E/S.

BH_Async_Read Se está haciendo uan petición asíncrona de lectura.

BH_Async_Write Se está haciendo uan petición asíncrona de escritura.

14

6. Algoritmos del kernel para manejo del bu�er-caché.

El kernel siempre trabaja con páginas. Una página unidad mínima de memo-ria con la que el kernel trabaja.

Para sistemas operativos de 32 bits → 4 KB

Para sistemas operativos de 64 bits → 8 KB

Las páginas están divididas en bloques (un bu�er está relacionado con unbloque).

Posibles situaciones de caché de página:

1) Cuando la memoria libre baja de un límite.

dirty_background_ratio (en mi caso = 5) indica la proporción de búf-feres a dirty del total. Cuando se alcanza esa proporción, hay una opcióndel kernel llamada wakeup_flusher_thread, que se encarga de llamaral proceso flush-maj:min (en mi caso al hacer ps aux | grep flush

aparece [flush-8:0]). [flush-8:0] para sda y [flush-8:0] para sdb.El proceso termina cuando:

a) Se ha escrito el número mínimo de páginas especi�cado

b) La cantidad de memoria libre es superior a dirty_background_ratio.

2) Cuando los datos a dirty crecen más de un límite. Los procesos que hacen�ush van poco a poco escribiendo todas las páginas que se hayan mod-i�cado hace mas de dirty_expire_centisecs (en mi caso = 3000). Eltemporizador expira cada dirty_expire_centisecs.

Todas estas cosicas (dirty_background_ratio , dirty_expire_centisecs)están en /proc/sys/vm.

7. Lectura/escritura de bloques en dispositivos

7.1. Elementos básicos

En el kernel 2.6 (3.x) el contenedor básico para E/S es la estructura bio.

sctruct bio {

sector_t bi_sector;

struct bio * bi_next;

struct block_device * bi_bdev;

struct bio_vec * bio_io_vec;

unsigned short bi_vent;

15

unsigned short bi_idx;

...

};

sctruct bio_vec {

struct page * bv_page;

unsigned int bi_vent;

unsigned short bi_idx;

};

request_queue es la cola de peticiones pendientes de E/S de bloques a undispositivo. Está compuesta por struct_request, que contienen struct_bio.

7.2. Plani�cador de E/S

El objetivo principal es mejorar el rendimiento, reducir los posicionamientosde la aguja de disco.

7.2.1. Conceptos básicos

Combinación Cuando hay dos peticiones a dos bloques contiguos de disco, elplani�cador lo pone como si fuera una sola petición a un bloque (los dos bloquesjuntos) de disco.

Reordenación Que la cola de peticiones (request_queue) esté ordenada deforma ascendente o descendente en la misma pista para que la aguja no tengaque moverse pechá

7.2.2. Tipos de plani�cadores

El elevador de Linus (Torvalds) Estuvo en el kernel hasta la versión 2.4. Esun algoritmo de combinación y reordenación. El unico problema es que reordenapor el �principio� del disco y deja to tirao a peticiones que pertenecen a cachos�más del �nal� del disco.

Plani�cador Deadline Algo muy importante es que las lecturas accedan adisco antes que las escrituras (pa que no pase eso de que las escrituras maten dehambre a las lecturas...). Al recibir una petición, se le asigna un deadline: 500ms para lecturas y 5 s para escrituras. Hay 3 colas:

Por un lado está la cola ordenada (SORTED-FIFO-QUEUE), que tiene todalas peticiones que llegan ordenadas por orden de sector (para optimizarlos movimientos de aguja).

Hay una cola de lectura (READ-FIFO-QUEUE) ordenada por tiempo de dead-line

16

(o de llegada, que es el mismo).

Y una cola de escritura (WRITE-FIFO-QUEUE) ordenada por tiempo dedeadline (o de llegada, que es el mismo).

Cuando va a plani�car una petición, compara las cabezas de las 3 colas,

SI se ha cumplido la hora de la de la cabeza de READ-FIFO-QUEUE

coge la cabeza de READ-FIFO-QUEUE

SINOSI se ha cumplido la hora de la de la cabeza de WRITE-FIFO-QUEUE

coge la cabeza de WRITE-FIFO-QUEUE

SINO

coge la cabeza de SORTED-FIFO-QUEUE

Plani�cador Anticipatorio Tiene las tres mismas colas que el plani�cadoranterior, que funcionan de manera similar. Tras hacer una lectura, espera sinhacer nada dirante 6 ms. Así, se le da tiempo a la aplicación a que realice otrapetición de lectura, que generalmente será de una posición de disco contigüa,consiguiendo de este modo un ahorro en el desplazamiento del cabezal de disco.

Plani�cador CFQ (Complete Fair Queueing) [este es el que se usa pordefecto en las distribuciones Linux hoy en día] Tiene una lista por cadabloque de disco, y reordena las colas de cada lista (también combina peticionesde disco contiguas) para que las agujas de disco se muevan de forma óptima.

Plani�cador NOOP Tiene solo una lista FIFO y ni reordena ni recombina, loque llegue antes, se ejecuta antes. Tiene sentido a la hora de hacer entrada/salidaen discos de estado /sólido (SSD), ya que no tenemos el tema de que las agujasse vayan a mover mucho y tal. para cambiar el plani�cador, en el arranque se

pone elevator=noop, hacemos que utilice este plani�cador

17

Parte III

Sistemas de Ficheros

Un sistema de �cheros es un almacenamiento jerárquico de datos con unaestructura bien de�nida. Un �chero es una cadena ordenada de bytes a los quese le asigna un nombre.

8. Representación interna y almacenamiento delos sistemas de �cheros

VFS (Virtual File Sistem) Es el subsistema de Linux que se encarga de ab-straer todas las operaciones que pueden realizarse sobre un sistema de�cheros. Por defecto estos sistemas de �cheros en Linux son ext4 para losdiscos duros, ext2 para los dispositivos USB y vFAT para las tarjetas SD.

En un sistema de �cheros hay cuatro conceptos básicos:

�chero

inodo

entrada de directorio

punto de montaje

En unix las operaciones solbre un sistema de �chero son:

creación

borrado

montaje/desmontaje

lectura/escritura

etc...

Los �cheros se organizan en directorios, por ejemplo:

/home/manolo/asd.ods Donde home y manolo son entradas de directorio

(dentry).

En Unix, los directorios son �cheros que listan los �cheros que contiene.

Además, se separa el concepto del contenido de �chero de su metadatos (per-misos, propietario, fecha de creación/modi�cación/acceso, etc...). Estos metadatosse almacenan en una estructura de datos distinta: el inodo. El superbloque con-

tiene información sobre el sistema de �cheros en general. En los sistemas de

18

Figura 2: inodos

�cheros de Unix (ext2, ext3, ext4, xfs, jfs, reiferfs, ...), se implementan estos con-ceptos de forma nativa. El VFS interactúa con todos estos sistemas de �cheros,haciendo de interfaz para el usuario. Sin embargo, para sistemas de �cheros co-mo vFAT, ntfs (Windows), hfs (Apple) que no están basados en inodos, el VFS�simula� como si lo fueran. Por ejemplo, en vFAT no existen permisos, por loque cuando se monta un sistema de �cheros en vFAT en Linux, se le da unaserie de permisos por defecto. Hay 4 objetos básicos con sus operaciones:

superbloque (superblock, superblock_operations)

inodo (inode, inode_operations)

entrada de directorio (dentry, dentry_operations)

�chero (file, file_operations)

Normalmente al formatear (mkfs.ext4 /dev/sdb), se crean un número deter-minado de inodos (el que se cree conveniente), si se le pone además -N 4000

entonces crea 4000 inodos (si sabes que no se van a utilizar tantos...) También,al formatear un disco se reserva un% para el usuario root, pero en un disco duroexterno esto no sirve pa na... asi que mejor le pones -m 0 y esto hace que nose reserve nada para root.

Los inodos contienen una lista de bloques de disco que componen el �chero.

El superbloque tiene un puntero a la entrada directorio raiz (s_root), quees /. AHORA VIENE LA IMAGEN TO POTEN DE LOS INODOS Y LOSBLOQUES

9. Llamadas al sistema para el sistema de �cheros

Operaciones sobre �cheros:

ssize_t read(int fd, void *buf, size_t count);

ssize_t write(int fd, const void *buf, size_t count);

19

int open(const char *pathname, int flags);

int open(const char *pathname, int flags, mode_t mode);

int creat(const char *pathname, mode_t mode);

int close(int fd);

int stat(const char *path, struct stat *buf);

int fstat(int fd, struct stat *buf);

int lstat(const char *path, struct stat *buf); (funciona sobre elenlace, no sobre lo que está apuntando)oldstat

oldfstat

statfs

off_t lseek(int fd, off_t offset, int whence) (posiciona el pun-tero en un punto del �chero)llseek

void *mmap(void *addr, size_t length, int prot, int flags, int

fd, off_t offset);

int munmap(void *addr, size_t length); (mapear/desmapear en memoria

el fichero)

mkdir

readdir

rmdir

chdir

fchdir

chown

fchown

lchown

chmod

fchmod

lchmod

link

symlink

readlink

ulink

int mknod(const char *pathname, mode_t mode, dev_t dev);

mount

umount

utime

access

20

sync

fsync

msync

ldatasync

rename

int dup(int oldfd)

int dup2(int oldfd, int newfd)

truncate

ftruncate

quotactl

bdflush

setfsuid (cambia el UID con el que se accede al sistema de �cheros enlugar de usar el actual; hay que ser root para esto)setfsgid (cambia el GID con el que se accede al sistema de �cheros enlugar de usar el actual; hay que ser root para esto)

getdents

flock

readv

writev

pread64

pwrite64

getcwd (get current working directory)

readahead

ACLs:setxattr

fsetxattr

lsetxattr

getxattr

fgetxattr

lgetxattr

listxattr

inotify (para enviar noti�caciones acerca de eventos relacionados con �cheros):inotify_init

inotify_init1

inotify_add_watch

inotify_rm_watch

21

Llamadas al sistema con direcciones relativas (path por un lado y descrip-tor por otro):openat

mkdirnat

mknodeat

lchownat

futimesat

unlinkat

renameat

linkat

symlinkat

readlinkat

fhmodat

facessat

int sync_file_range(int fd, off64_t offset, off64_t nbytes, unsigned

int flags) (sirve para sincronizar una parte de un �chero especí�co

La misma llamada puede venir en 3 �formatos�:

funcion→ coge el path del �chero

�uncion→ coge el descriptor del �chero

lfuncon → tiene en cuenta que el �chero es un enlace

22

Parte IV

Procesos

Proceso

un conjunto de instrucciones plani�cable por el plani�cador

la unidad mínima de asignación de recursos.

un programa en ejecución.

el código ejecutable de un programa más los recursos usados:

• �cheros abiertos

• señales pendientes

• estado del procesador

• datos internos del kernel

• espacio de memoria direccionable

• sección de datos

• etc...

Thread, hilo, LWP (Light Weight Process)

Un thread es un tipo especial de proceso. Dos threads del mismo proceso sonsolo dos procesos que están en el mismo grupo de hilos. Cada thread incluye:

un contador de programa (PC, program counter)

una pila

el conjunto de registros del procesador

Los threads se pueden implementar de 3 formas:

Totalmente en espacio de usuario:

• Más rápido

• Problema ya que no se pueden ejecutar 2 hilos de un mismo procesoa la vez

• Menos estable

Totalmente en espacio de kernel:

• Menos rápido

• Más estable

De forma híbrida

En Linux existen los lpthreads (con la NPTL, Native POSIX Thread Library)

23

10. Organización y gestión de procesos

Creación de procesos:

Nueva pila (stack), estructura, thread_info, task_struct

Se chequea el número máximo de procesos para dicho usuario

Algunos miembros de la estrctura de proceso se diferencian (estadísticas)

La tarea se pone a TASK_UNINTERRUPTIBLE

Se llama a copy_flags que actualiza las los �ags de task_struct:

• PF_SUPERPRIV

• PF_FORKNOEXEC

get_pid()

Duplica o copia �cheros abiertos, información del fs, signal handlers, es-pacio direccionable de memoria, etc...

Reporta el timeslice entre los procesos padre e hijo

copy_proccess acaba y devuelve un puntero al nuevo hijo

¾Quien se pone a ejecución despues de hacer un fork? ¾El padre o el hijo?El hijo porque...

11. Estados y transiciones de estado de los pro-cesos

El kernel guarda la lista de procesos en una lista circular doblemente enlazada(tasklist, struct task_struct, <linux/sched.h>)

Hay un proceso que se ejecuta al arrancar el sistema operativo: init.

24

Figura 3: Estados de los procesos

12. Memoria para la gestión de procesos

13. Llamadas al sistemas para la gestión de pro-cesos

fork() (crea una copia del proceso con clone())vfork()

execvp() (reemplaza el proceso por otro)execv()

exec..

exit(int)(salir de un proceso proceso)

getpid() (obtiene el id del proceso)getppid() (obtiene el id del padre del proceso)getgid() (obtiene el id del grupo del proceso)getpgid() (obtiene el id grupo del padre del proceso)getegid() ()getregid() ()getuid() (obtiene el id del usuario del proceso)getpuid() (obtiene el id del usuario padre del proceso)getegid() ()getregid() ()getsid() (obtiene el id de la sesión del proceso)getfsuid() ()

25

setuid() (cambiar el id del usuario del proceso, solo lo puede hacer root)setgid() (cambiar el id del grupo del proceso, solo lo puede hacer root)seteuid() ()setegid() ()setreuid() ()setregid() ()setfsuid() ()

wait() (para esperar a procesos)wait4()

waitpid()

kill() (mandar una señal a procesos)

sigaction()

sigsuspend()

sigpending()

sigreturn()

sigprocpask()

ptrace()

strace()

ltrace()

gdb()

nice()

getpriority()

setpriority()

sched_getscheduler()

sched_setscheduler()

sched_getparam()

sched_setparam()

sched_get_priority_max()

sched_get_priority_min()

sched_rr_get_interval()

sched_getaffinity()

sched_setaffinity()

sched_yield()

14. Plani�cación de procesos

El plani�cador es el que se encarga de poner procesos en ejecución paraque estos se ejecuten (aparentemente) de forma paralela. Entonces, el sistemaoperativo es multitarea.

Multitarea cooperativa (Mac OS, Windows 9x)

26

Multitarea expropiativa (O(1))

Los procesos limitados por E/S o por procesador.

Prioridad de procesos: Un algoritmo es usar la prioridar, (+ prioridad→ +timeslice). La prioridad puede ser modi�cada por el proceso, el SO o el usuario.

+ E/S → + prioridad

+ CPU → - prioridad

Rango de prioridad estandar: [-20 (máximo timeslice) ... 0 (estándar) ...+19 (mínimo)]

• Mínima prioridad (+19) → 5 ms

• Prioridad por defecto (0) → 100 ms

• Máxima prioridad (-20) → 800 ms

• Recién creado → 1/2 de la del padre

• 0 ms → tiempo del proceso ha expirado

Rango de prioridad en tiempo real: [1 (máximo) ... 99 (mínimo) 100 ...140]

Con un timeslice alto:

+ rendimiento

+ latencia

Con un timeslice alto:

- rendimiento

- latencia

Cada quantum de tiempo que el proceso puede ejecutarse y el plani�cador se loniega, se incrementa la prioridad dinámica

El plani�cador de Linux:

Es O(1): el algoritmo de plani�cación se ejecuta en un tiempo independi-ente del número de procesos.

Perfecta escalabilidad: cada proceso es independiente.

Buena a�nidad SMP: se pueden agrupar tareas por CPU.

Buen rendimiento interactivo.

Es justo.

27

runqueue→ por procesador, contiene procesos RUNNABLEs, contiene 2 prio_array(activos y expirados). Cada prio_array contiene una cola de procesos RUN-ABLEs por nivel de prioridad (contiene un bitmap de prioridad)

struct prio_array{

int nr_active,

unsigned long bitmap[BITMAP_SIZE],

struct list_head queue[MAX_PRIO]

};

donde BITMAP_SIZE es 5 (25 = 32, tamaño de un long) y MAX_PRIO

es 140

Podría tardar mucho O(n)

El recálculo de timeslice requiere bloquear la lista (lock)

El recálculo no es determinista (ocurre aleatoriamente)

Es feo

struct task_struct * prev = current;

prio_array * array = rq->active;

int idx = sched_load_first_bit(array->bitmap);

list_head * queue = array->queue + idx;

next = list_entry(queue->next, struct task_struct, run_list);

sleep_avg guarda la media de 0 a MAX_SLEEP_AVG (10 ms). Después de dormirse incrementa sleep_avq. Por cada tick que el proceso usa CPU, se decre-menta.

sleep_avg calcua el nuevo timeslice (-20→ 800 ms, 0→ 100 ms, +19→ 5 ms)

Balanceador de carga 1 runqueueSi no hay SMP, ni siquiera se compilaSi un runqueue se queda vacío, se llama a load_balance.El otro caso en que se llama es con un timer. Cada 1 ms si está en idle, cada

200 ms en otro caso.

1. field_busiest_queue, devuelve la runqueue más grande si tiene al menosun 25% más procesos que la actual.

2. Se decide de qué prio_array. Se pre�ere el de procesos expirados (ya queesos no se están ejecutando en este momento, aunque si está vacío, se cogeel prio_array de procesos activos.

28

3. Busca la lista con más prioridad con tareas

4. Se mira cada proceso de esa prio_array que no estécorriendo que se puedamigrar y no esté en la caché de la CPU. Si se encuentra → pull_task

5. Mientras no estén balanceados, se repiten 3 y 4.

29

Parte V

Memoria

15. Hardware

15.1. Modo real

Memoria convencional 0 → 640 KBMemoria superior (Upper Memory Area) 640 KB → 1 MB

Memoria extendida 1 MB →...Area de memoria alta (High Memory Area) 64 KB a partir de 1 MB menos 16 bytes

15.2. Modo protegido

En los 386 y posteriores se usan direcciones lógicas de 48 bits. En la unidadde segmentación se comprueban y traducen a direcciones lineales de 32 bits.

Una dirección lógica (48 bits) se compone de:

16 bits: selector de segmento

• 2 bits: RPC (Request Privilege Level)

• 1 bit: TI (Table Indicator)

• 13 bits: índice

32 bits: o�set

* Se podría decir que en realidad las direcciones lógicas son de 46 bits en vez de48, ya que 2 bits son para el RPC (el cual no es dirección sino permisos).

La dirección se calcula de la siguiente forma:

1. Se mira el indicador de tabla:

a) Global Description Table (si TI = 0)

b) Local Description Table (si TI = 1)

2. Se checkean los privilegios:

a) Si DPL < max (CPL, RPL)→ General Protection Fault (GPF, SIG-NAL 11)

3. Se compara el o�set con el tamaño del segmento, si se sale → GPF

4. Se suma la dirección base con el o�set.

30

5. Los 32 bits se dividen en 3 partes:

a) 10 bits que direccionan en el primer nivel de páginas

b) 10 bits que direccionan en el segundo nivel de páginas.

c) 12 bits que apuntan a un MB concreto del tercel nivel de páginas.

Así, con 32 bits podemos direccionar 4 GB.

* DPL = Descriptor Privilege Level

* CPL = Current Privilege Level (viene dado por los 2 bits más bajos de CS)

* RPL = Request Privilege Level

__KERNEL_CS base = 0 size = 4 GB DPL = 0__KERNEL_DS base = 0 size = 4 GB DPL = 0__USER_CS base = 0 size = 4 GB DPL = 3__USER_DS base = 0 size = 4 GB DPL = 3

15.3. Modo PAE

1. Para activar el modo PAE, hay que activar el bit 5 del CR4.

2. Los 32 bits de la dirección se dividen ahora en 4 partes:

a) 2 bits para seleccionar dentro de la tabla de punteros del directoriode páginas

b) 9 bits que direccionan en el primer nivel de páginas

c) 9 bits que direccionan en el segundo nivel de páginas.

d) 12 bits que apuntan a un MB concreto del cuarto nivel de páginas.

15.4. Long mode

1. Aunque los punteros son de 64 bits, en la actualidad se usan solo 48 bits,ya que no hay gente que tenga 16 EB (exabyte) de memoria.

2. Los 64 bits de la dirección se dividen ahora en 5 partes:

a) 9 bits que direccionan en el primer nivel de páginas

b) 9 bits que direccionan en el segundo nivel de páginas

c) 9 bits que direccionan en el tercer nivel de páginas.

d) 9 bits que direccionan en el cuarto nivel de páginas.

e) 12 bits que apuntan a un MB concreto del quinto nivel de páginas.

31

15.5. Modo page

40 bytes de struct page:

struct page {

page_flags_t flags;

atomic_t _count;

atomic_t _mapcount;

unsigned long private;

struct address_space * mapping;

pgoff_t index;

struct list_head lru;

void * virtual;

}

16. Memoria en el kernel y zonas de memoria

Hay varias zonas de memoria:

ZONE_DMA [0 - 16 MB] Los antiguos dispositivos ISA iban (a la fuerza)aquí, aunque hoy en día cualquier dispositivo puede ir aquí.

ZONE_NORMAL [0 ~ 1GB (896 MB)] Zona de memoria a la que accede elkernel

ZONE_HIGHMED [896→ ] Zona de memoria que no se mapea por el kernel

17. SLAB

El struct SLAB y sus funcioncitas

Se trata de una capa que gestiona estructuras de datos genéricos.

Las estructuras de datos usadas frecuentemente se reservan / liberan amenudo, así que se cachean.

La lista de libres mejora enormemente la velocidad.

Si el allocator conoce conceptos como el tamaño del objeto, de la páginay del total de caché puede tomar decisiones más inteligentes.

Si parte de la caché se hace por el procesador (cada procesador tiene unacaché), no hace falta hacer un lock SMP

Si el allocator entiende de NUMA, puede hacer reservas en el mismo nodoque los pide

UnCada caché se encuentra dividida en slabs que se componen de una o máspáginas físicamente contiguas. Las slabs contienen los objetos. Además, cadaslab está en uno de los siguientes estados:

32

Figura 4: Slab

lleno

parcial

vacío

struct kmem_cache_s {

list slabs_full, slabs_partial, slabs_emptystored }

struct slab {

struct list_head list;

unsigned long colouroff;

void *s_mem;

unsigned int inuse;

kmem_bufctl_t free;

}

static void * kmem_getpages {

(kmem_cache_t * cachep, int lags, int nodeid);

kmem_freepages(..)

kmem_cache_create(const char * name, size_t size, size_t align,

unsigned long flags,

void (*ctor) (void *, kmem_cache_t *, unsigned

long),

33

void (*dtor) (void *, kmem_cache_t *, unsigned

long));

Una llamada sería así:

kmem_cache_create(.., construye_estructura, destruye_estructura)

Los posibles �ags serían:

SLAB_NO_READ

SLAB_HWCACHE_ALIGN

SLAB_MUST_HWCACHE_ALIGN

SLAB_POISON ( a5a5a5a5)16 = 1010010110100101101001011010101)2)

SLAB_RED_ZONE

SLAB_PANIC (Fallo de memoria en la zona del kernel, Kernel Panic)

kmem_cache_destry(kmem_cache_t * cachep)

La pila del kernel

Se usan 2 páginas por proceso para la pila del kernel.

Si la página es de 4 KB → 8 KB ocupados

Si la página es de 8 KB → 16 KB ocupados

18. El espacio direccionable de proceso

Una dirección de memoria es un valor del espacio de direcciones, general-mente se presenta en hexadecimal. A veces se prepresentan intervalos de di-recciones al que un proceso puede acceder (se le llama área de memoria), y seescriben como 08048000-0804c000.

Las áreas de memoria tienen permisos asociados: de lectura, escritura, eje-cución, ... Si un proceso se sale de ese área → Fallo de Segmento (SegmentationFault).

Mapa de memoria de un proceso (ejecutable, archivo binario):

Un mapa de memoria del código ejecutable del binario → sección detexto.

Un mapa de memoria de las variables globales inicializadas del binario →sección de datos.

Un mapa de memora de la página cero, con variables globales sin inicializar→ sección bss (block started by symbol).

34

Un mapa de memora de la página cero, usado por la pila de espacio deusuario del proceso.

Una nueva sección de texto, datos y bss por cada librería compartida conla que el proceso enlace (libc, ld, etc...).

Cualquier �chero mapeado en memoria.

Cualquier segmento de memoria compartida.

Cualquier mapeo de memoria anónima (por ejemplo de un malloc).

Las zonas de memoria de un proceso pueden verse haciendo cat /proc/<pid>/maps.vm_area_structmm_structtask_struct

unsigned long do_mmap(struct file, unsigned long addr,

unsigned long len, unsigned long prot,

unsigned long flag, unsigned long offset);

PROT_READPROT_WRITEPROT_EXECPROT_NONE

MAP_SHAREDMAP_PRIVATEMAP_FIXEDMAP_ANONYMOUSMAP_GROWSDOWNMAP_DENYWRITEMAP_EXECUTABLEMAP_LOCKEDMAP_NORESERVEMAP_POPULATEMAP_NONBLOCK

mmap2 (void * start, size_t length, int prot, int �ags, int fd, o�_tpyo�)

19. SWAP

Es una parte del disco duro a donde se copia memoria principal cuando estaestá to petá y hay que meter más cosas.

El proceso para hacer swap es el siguiente.

Se decide qué proceso que se va meter en memoria SWAP.

Se determina la localización del dato (lo que se va a mover) en el almace-namiento auxiliar.

35

Se obtiene una página vacía de RAM.

Se cargan los datos en la página.

Se actualiza la tabla de páginas para mostrar la nueva página.

Se devuelve el control al programa reintentando transparentemente la in-strucción que provocó el fallo de página.

19.1. Paginación bajo demanda (lazy loading)

Las páginas se van cargando conforme van haciendo falta.

Ventajas

Optimiza el uso de la memoria, ya que no se cargan páginas que no se vana usar.

El inicio del programa es más rápido.

Menor carga del disco.

Desventajas

Ejecución más lenta, ya que cada vez que se pide una página hay quecargarla.

19.2. Paginación anticipatoria

Las páginas cargan antes al principio de la ejecución del programa.

Ante un fallo de página, quizás luego se pidan las siguientes de direccionesvirtuales.

Si un programa acaba, dejando memoria libre, quizás se ejecute algún otrodesde SWAP.

Parte VI

Comunicación entre procesos

20. Traza de procesos

Para que un padre pueda recibir la traza de un hijo se usa la llamadaptrace():

long ptrace(enum __ptrace_request request, pid_t pid, void

* addr, void * data);

36

Se puede utilizar antes de llamar a exec(), para que el padre trace al hijo:

fork(..);

ptrace(PTRACE_TRACEME, ..)

exec(..);

O también, para trazar un pid concreto:

ptrace(PTRACE_ATTACH, pid, ..);

Tipos de request (los SET son principalmente para procesos como el gdb y tal):

PTRACE_TRACEME: para trazar al propio proceso .

PTRACE_PEEKTEXT, PTRACE_PEEKDATA: para cogeque llamar de memoria.

PTRACE_POKETEXT, PTRACE_POKEDATA: para poner en memoria.

PTRACE_GETREGS, PTRACE_GETFPREGS: para coger los valores de los reg-istros.

PTRACE_GETSIGINFO: para coger información acerca de las señales.

PTRACE_SETREGS, PTRACE_SETFPREGS: para cambiar los valores de losregistros.

PTRACE_SETSIGINFO: para cambiar información acerca de las señales.

PTRACE_CONT: para hacer continuar al proceso.

PTRACE_SYSCALL: para hacer una llamada al sistema.

PTRACE_SINCLESTEP: para que se ejecute una sola instrucción.

PTRACE_KILL: para hacer terminar el proceso.

PTRACE_ATTACH: para trazar un determinado proceso.

PTRACE_DETACH: para dejar de trazar un determinado proceso.

21. Paso de mensajes. SYSTEM V IPC

Hay un límite N de cantidad de mensajes.

send(destino, mensaje)

recv(origen, &mensaje)

37

Figura 5: Uso de ptrace

21.1. Deadlock

�Cuando dos trenes se aproximan a un cruce, ambos se quedarán

completamente parados y no arrancarán hasta que el otro se haya

ido�

Ley de Kansas

Condiciones de Co�man para que aparezca un deadlock :

1. Condición de exclusión mutua: un recurso no puede ser usado por más deun proceso a la vez.

2. Condición de Hold & Wait : procesos que ya tienen recursos piden nuevosrecursos.

3. Condición de no expropiación: los recursos no pueden ser expropiados.

4. Condición de espera circular: 2 o más procesos forman una cadena circulardonde cada proceso espera un recurso poseido por el siguiente proceso dela cadena.

Cómo solucionar las situaciones de las condiciones de Co�man (1971):

1. Condición de exclusión mutua: tener un daemon que serializa el acceso alrecurso.

2. Condición de Hold & Wait : pedir todos los recursos que se necesitaránantes de empezar. Otra opción sería lliberar los recursos que se tienenantes de pedir nuevos.

3. Condición de no expropiación: no existe solución en general...

4. Condición de espera circular: petición de los recursos de acuerdo a unorden establecido.

38

21.2. Livelock

Problema de los �lósofos

La solución de Dijkstra: aisgnando prioridades a los tenedores.

La solución por jerarquía/orden (Chandy/Misra - 1984):

Para cada par de �lósofos que comparten un recurso, se crea un tenedory se le asigna al �lósofo con menor ID. Cada tenedor está en estado su-cio/limpio. Inicialmente sucio, cuando un �lósofo necesita un tenedor, selo pide al vecino. Si el tenedor está limpio, lo mantiene, y si está sucio, lolimpia y se lo da.

21.3. SYSTEM V IPC

Usos principales de System V IPC:

Sincronizarse con otros procesos mediante semáforos.

Enviar mensajes y recibirlos.

Compartir un área de memoria.

Un recurso IPC es persistente (semáforos, colas de mensajes, memoria compar-tida) y contiene:

IPC key (id/nombre del �chero/objeto)

Identi�cador IPC (descriptor de �chero)

Ambos (IPC key e identi�cador IPC son enteros de 32 bits).

Para obtener estos recursos hay que hacer uso de las llamadas de sys/ipc.h:

Semáforo: int semget(key_t key, int nsems, int semflg); (sys/sem.h)

Cola de mensajes: int msgget(key_t key, int msgflg); (sys/msg.h)

Área de memoria compartida: int shmget(key_t key, size_t size,

int shmflg); (sys/shm.h)

key puede ser IPC_CREAT e IPC_EXCL.

Otras funcioncitas y structs interesantes:

void *shmat(int shmid, const void *shmaddr, int shmflg);

void *shmat(int shmid, const void *shmaddr, int shmflg);

struct shmid_ds {

struct ipc_perm shm_perm; /* operation perms */

int shm_segsz; /* size of segment (bytes)

*/

time_t shm_atime; /* last attach time */

39

time_t shm_dtime; /* last detach time */

time_t shm_ctime; /* last change time */

unsigned short shm_cpid; /* pid of creator */

unsigned short shm_lpid; /* pid of last operator */

short shm_nattch; /* no. of current attaches

*/

};

struct ipc_perm {

key_t key;

ushort uid; /* owner euid and egid */

ushort gid;

ushort cuid; /* creator euid and egid */

ushort cgid;

ushort mode; /* access modes see mode flags below */

ushort seq; /* slot usage sequence number */

};

22. Memoria compartida

23. Semáforos

40