Sistemas operativos modernos / Andrew S. Tanenbaum.

CONTENIDO
PARTE 1: SISTEMAS OPERATIVOS TRADICIONALES
1 INTRODUCCION 1
1.1 ¿QUE ES UN SISTEMA OPERATIVO? 3
1.1.1 El sistema operativo como una máquina extendida 3
1.1.2 El sistema operativo como controlador de recursos 4
1.2 HISTORIA DE LOS SISTEMAS OPERATIVOS 5
1.2.1 La primera generación 6
1.2.2 La segunda generación 6
1.2.3 La tercera generación 8
1.2.4 La cuarta generación 12
1.3 CONCEPTOS DE LOS SISTEMAS OPERATIVOS 13
1.3.1 Procesos 14
1.3.2 Archivos 14
1.3.3 Llamadas al sistema 18
1.3.4 El Shell 20
1.4 ESTRUCTURA DE LOS SISTEMAS OPERATIVOS 21
1.4.1 Sistemas monolíticos 21
1.4.2 Sistemas con capas 23
1.4.3 Máquinas virtuales 24
1.4.4 Modelo cliente-servidor 25
1.5 BOSQUEJO DEL RESTO DEL LIBRO 27
1.6 RESUMEN 28
2 PROCESOS 31
2.1 INTRODUCCION A LOS PROCESOS 31
2.1.1 El modelo de procesos 32
2.1.2 Implantación de los procesos 36
2.2 COMUNICACION ENTRE PROCESOS 38
2.2.1 Condiciones de competencia 38
2.2.2 Secciones críticas 39
2.2.3 Exclusión mutua con espera ocupada 40
2.2.4 Dormir y despertar 44
2.2.5 Semáforos 47
2.2.6 Contadores de eventos 50
2.2.7 Monitores 51
2.2.8 Transferencia de mensajes 56
2.2.9 Equivalencia de primitivas 59
2.3 PROBLEMAS CLASICOS DE LA COMUNICACION ENTRE PROCESOS 64
2 3.1 El problema de la cena de los filósofos 64
2 3.2 El problema de los lectores y los escritores 66
2.3.3 El problema del barbero dormilón 68
2.4 PLANIFICACION DE PROCESOS 71
2.4.1 Planificación tipo round robin 72
2.4.2 Planificación por prioridad 73
2.4.3 Colas múltiples 75
2.4.4 Primero el trabajo más corto 76
2.4.5 Planificación garantizada 77
2.4.6 Política vs. Mecanismo 78
2.4.7 Planificación de dos niveles 79
2.5 RESUMEN 80
3 ADMINISTRACION DE LA MEMORIA 85
3.1 ADMINISTRACION DE LA MEMORIA SIN INTERCAMBIO O PAGINACION 81
3.1.1 Monoprogramación sin intercambio o paginación 86
3.1.2 Multiprogramación y uso de memoria 87
3.1.3 Multiprogramación con particiones fijas 90
3.2 INTERCAMBIO 93
3.2.1 Multiprogramación con particiones variables 93
3.2.2 Administración de la memoria con mapas de bits 95
3.2.3 Administración de la memoria con listas ligadas 96
3.2.4 Administración de la memoria con el sistema de los asociados 98
3.2.5 Asignación del hueco de intercambio 100
3.2.6 Análisis de sistemas con intercambio 101
3.3 MEMORIA VIRTUAL 102
3.3.1 Paginación 102
3.3.2 Tablas de páginas 105
3.3.3 Ejemplos de hardware de paginación 111
3.3.4 Memoria asociativa 116
3.3.5 Tablas de páginas invertidas 121
3.4 ALGORITMOS DE REEMPLAZO DE PAGINAS 123
3.4.1 El algoritmo de reemplazo de páginas óptimo 123
3.4.2 El algoritmo de reemplazo de páginas según el uso no tan reciente 124
3.4.3 El algoritmo de reemplazo "Primero en entrar, primero en salir" (FIFO) 125
3.4.4 El algoritmo de reemplazo de páginas de la segunda oportunidad 126
3.4.5 El algoritmo de reemplazo de páginas del reloj 127
3.4.6 El algoritmo de reemplazo de páginas "la de menor uso reciente" 127
3.4.7 Simulación del algoritmo del uso más reciente en software 128
3.5 MODELACION DE ALGORITMOS DE PAGINACION 130
3.5.1 Anomalía de Belady 130
3.5.2 Algoritmos de pilas 131
3.5.3 La distancia de la cadena 134
3.5.4 Predicción de la tasa de fallos de página 135
3.6 ASPECTOS DE DISEÑO PARA LOS SISTEMAS DE PAGINACION 136
3.6.1 El modelo del conjunto de trabajo 136
3.6.2 Políticas de asignación locales vs globales 137
3.6.3 Tamaño de página 140
3.6.4 Aspectos de implantación 141
3.7 SEGMENTACION 146
3.7.1 Implantación de la segmentación pura 149
3.7.2 Segmentación con paginación: MULTICS 150
3.7.3 Segmentación con paginación: Intel 386 154
3.8 RESUMEN 160
4 SISTEMAS DE ARCHIVO 165
4.1 ARCHIVOS 166
4.1.1 Nombre de los archivos 166
4.1.2 Estructura de un archivo 168
4.1.3 Tipos de archivos 169
4.1.4 Acceso a un archivo 172
4.1.5 Atributos de archivo 172
4.1.6 Operaciones con archivos 174
4.1.7 Archivos mapeados a memoria 178
4.2 DIRECTORIOS 179
4.2.1 Sistemas jerárquicos de directorios 179
4.2.2 Nombre de las rutas de acceso 181
4.2.3 Operaciones con directorios 183
4.3 IMPLANTACION DEL SISTEMA DE ARCHIVOS 184
4.3.1 Implantación de archivos 185
4.3.2 Implantación de directorios 188
4.3.3 Archivos compartidos 191
4.3.4 Administración del espacio en disco 193
4.3.5 Confiabilidad del sistema de archivos 197
4.3.6 Desempeño del sistema de archivos 202
4.4 SEGURIDAD 206
4.4.1 El ambiente de seguridad 206
4.4.2 Fallas famosas de seguridad 207
4.4.3 El gusano de Internet 210
4.4.4 Ataques genéricos a la seguridad 212
4.4.5 Principios del diseño para la seguridad 214
4.4.6 Autentificación del usuario 215
4.5 MECANISMOS DE PROTECCION 219
4.5.1 Dominios de protección 219
4.5.2 Listas pare control de acceso 222
4.5.3 Posibilidades 224
4.5.4 Modelos de protección 225
4.5.5 Canales ocultos 227
4.6 RESUMEN 229
5 ENTRADA / SALIDA 233
5.1 PRINCIPIOS DE HARDWARE DE E/S 233
5.1.1 Dispositivos de E/S 234
5.1.2 Controladores de dispositivos 235
5.1.3 Acceso directo a memoria (DMA) 237
5.2 PRINCIPIOS DEL SOFTWARE DE E/S 239
5.2.1 Objetivos del software de E/S 239
5.2.2 Manejadores de interrupciones 241
5.2.3 Manejadores de dispositivos 241
5.2.4 Software de E/S independiente del dispositivo 242
5.2.5 Software de E/S en el espacio del usuario 244
5.3 DISCOS 246
5.3.1 Hardware para discos 246
5.3.2 Algoritmos de programación del brazo del disco 247
5.3.3 Manejo de errores 250
5.3.4 Ocultamiento de una pista a la vez 251
5.3.5 Discos en RAM 252
5.4 RELOJES 253
5.4.1 Relojes 253
5.4.2 Software para relojes 254
5.5 TERMINALES 257
5.5.1 Hardware para terminales 257
5.5.2 Terminales mapeadas a memoria 259
5.5.3 Software para la Entrada 262
5.5.4 Software para la Salida 267
5.6 RESUMEN 268
6 BLOQUEOS 271
6.1 RECURSOS 273
6.2 BLOQUEOS 274
6.2.1 Condiciones para un bloqueo 274
6.2.2 Modelación de bloqueos 275
6.3 EL ALGORITMO DEL AVESTRUZ (Ostrich) 278
6.4 DETECCION Y RECUPERACION DE BLOQUEOS 279
6.4.1 Detección de bloqueos de forma un recurso de cada tipo 279
6.4.2 Detección de bloqueos de forma varios recursos de cada tipo 281
6.4.3 Recuperación de un bloqueo 284
6.5 EVASION DE BLOQUEOS 286
6.5.1 Trayectorias de recursos 286
6.5.2 Estados seguros e inseguros 287
6.5.3 El algoritmo del banquero para sólo un recurso 289
6.5.4 El algoritmo del banquero para varios recursos 290
6.6 PREVENCION DE BLOQUEOS 291
6.6.1 Prevención de la condición de exclusión mutua 292
6.6.2 Prevención de la condición Detenerse y esperar 292
6.6.3 Prevención de la condición de no apropiación 293
6.6.4 Prevención de la condición de espera circular 293
6.7 OTROS ASPECTOS 294
6.7.1 Cerradura de dos fases 294
6.7.2 Bloqueos sin recursos 295
6.7.3 Inanición 295
6.8 RESUMEN 296
7 ESTUDIO 1: UNIX 299
7.1 HISTORIA DE UNIX 300
7.1.1 UNICS 300
7.1.2 UNIX en la PDP-II 301
7.1.3 UNIX portable 302
7.1.4 UNIX de Berkeley 303
7.1.5 UNIX estándar 303
7.2 PANORAMA DE UNIX 305
7.2.1 Objetivos de UNIX 306
7.2.2 Interfaces de UNIX 307
7.2.3 Entrada a UNIX 308
7.2.4 El Shell de UNIX 309
7.2.5 Archivos y directorios en UNIX 311
7.2.6 Programas de utilerías en UNIX 312
7.3 CONCEPTOS FUNDAMENTALES EN UNIX 314
7.3.1 Procesos en UNIX 316
7.3.2 El modelo de memoria de UNIX 320
7.3.3 El sistema de archivos en UNIX 323
7.3.4 Entrada/Salida en UNIX 326
7.4 LLAMADAS AL SISTEMA EN UNIX 330
7.4.1 Llamadas al sistema para la administración de procesos en UNIX 330
7.4.2 Llamadas al sistema para la administración de la memoria en UNIX 334
7.4.3 Llamadas al sistema relacionadas con archivos y directorios en UNIX 335
7.4.4 Llamadas al sistema relacionadas con Entrada/Salida en UNIX 337
7.5 IMPLANTACION DE UNIX 337
7.5.1 Implantación de procesos en UNIX 338
7.5.2 Implantación del control de la memoria en UNIX 342
7.5.3 Implantación del sistema de archivos en UNIX 347
7.5.4 Implantación de la Entrada/Salida en UNIX 350
7.6 RESUMEN 352
8 ESTUDIO 2: MS-DOS 356
8.1 HISTORIA DE MS-DOS 356
8.1.1 La IBM-PC 357
8.1.2 MS-DOS Versión 1.0 359
8.1.3 MS-DOS Versión 2.0 359
8.1.4 MS-DOS Versión 3.0 360
8.1.5 MS-DOS Versión 4.0 361
8.1.6 MS-DOS Versión 5.0 362
8.2 PANORAMA DE MS-DOS 363
8.2.1 Uso de MS-DOS 363
8.2.2 El Shell de MS-DOS 367
8.2.3 Configuración de MS-DOS 369
8.3 CONCEPTOS FUNDAMENTALES EN MS-DOS 370
8.3.1 Procesos en MS-DOS 371
8.3.2 El modelo de memoria de MS-DOS 375
8.3.3 El sistema de archivos en MS-DOS 385
8.3.4 Entrada/Salida en MS-DOS 387
8.4 LLAMADAS AL SISTEMA EN MS-DOS 388
8.4.1 Llamadas al sistema para la administración de procesos en MS-DOS 390
8.4.2 Llamadas al sistema para la administración de la memoria en MS-DOS 390
8.4.3 Llamadas al sistema relacionadas con archivos y directorios en MS-DOS 391
8.4.4 Llamadas al sistema relacionadas con Entrada/Salida en MS-DOS 391
8.5 IMPLANTACION DE MS-DOS 392
8.5.1 Implantación de procesos en MS-DOS 393
8.5.2 Implantación de la administración de la memoria en MS-DOS 395
8.5.3 Implantación del sistema de archivos en MS-DOS 397
8.5.4 Implantación de la Entrada/Salida en MS-DOS 402
8.6 RESUMEN 405
PARTE 2: SISTEMAS OPERATIVOS DISTRIBUIDOS
9 INTRODUCCION A LOS SISTEMAS DISTRIBUIDOS 411
9.1 OBJETIVOS 412
9.1.1 Ventajas de los sistemas distribuidos con respecto de los centralizados 412
9.1.2 Ventajas de los sistemas distribuidos con respecto de las PC independientes 414
9.1.3 Desventajas de los sistemas distribuidos 415
9.2 CONCEPTOS DE HARDWARE 416
9.2.1 Multiprocesadores con base en buses 419
9.2.2 Multiprocesadores con conmutador 420
9.2.3 Multicomputadoras con base en buses 422
9.2.4 Multicomputadoras con conmutador 422
9.3 CONCEPTOS DE SOFTWARE 423
9.3.1 Sistemas operativos de redes y NFS 424
9.3.2 Sistemas realmente distribuidos 433
9.3.3 Sistemas de multiprocesador con tiempo compartido 434
9.4 ASPECTOS DEL DISEÑO 437
9.4.1 Transparencia 437
9.4.2 Flexibilidad 440
9.4.3 Confiabilidad 442
9.4.4 Desempeño 443
9.4.5 Escalabilidad 444
9.5 RESUMEN 446
10 COMUNICACION EN LOS SISTEMAS DISTRIBUIDOS 449
10.1 PROTOCOLOS CON CAPAS 450
10.1.1 La capa física 453
10.1.2 La capa de enlace de los datos 453
10.1.3 La capa de la red 455
10.1.4 La capa de transporte 455
10.1.5 La capa de sesión 456
10.1.6 La capa de presentación 456
10.1.7 La capa de aplicación 457
10.2 EL MODELO CLIENTE-SERVIDOR 457
10.2.1 Clientes y servidores 457
10.2.2 Un ejemplo cliente-servidor 457
10.2.3 Direccionamiento 461
10.2.4 Primitivas de bloqueo vs. no bloqueo 465
10.2.5 Primitivas almacenadas en buffer vs. no almacenadas 468
10.2.6 Primitivas confiables vs. no confiables 470
10.2.7 Implantación del modelo cliente-servidor 472
10.3 LLAMADA A UN PROCEDIMIENTO REMOTO (RPC) 474
10.3.1 Operación básica de RPC 475
10.3.2 Transferencia de parámetros 479
10.3.3 Conexión dinámica (Dynamic Binding) 484
10.3.4 Semántica de RPC en presencia de fallos 487
10.3.5 Aspectos de la implantación 492
10.3.6 Áreas de problemas 503
10.4 COMUNICACION EN GRUPO 506
10.4.1 Introducción a la comunicación en grupo 506
10.4.2 Aspectos del diseño 508
10.4.3 Comunicación en grupo en ISIS 518
10.5 RESUMEN 522
11 SINCRONIZACION EN SISTEMAS DISTRIBUIDOS 525
11.1 SINCRONIZACION DE RELOJES 526
11.1.1 Relojes lógicos 528
11.1.2 Relojes físicos 531
11.1.3 Algoritmos para la sincronización de relojes 534
11.2 EXCLUSION MUTUA 540
11.2.1 Un algoritmo centralizado 540
11.2.2 Un algoritmo distribuido 541
11.2.3 Un algoritmo de anillo de fichas (Token Ring) 544
11.2.4 Comparación de los tres algoritmos 546
11.3 ALGORITMOS DE ELECCION 547
11.3.1 El algoritmo del grandulón 547
11.3.2 Un algoritmo de anillo 549
11.4 TRANSACCIONES ATOMICAS 550
11.4.1 Introducción a las transacciones atómicas 550
11.4.2 El modelo de transacción 552
11.4.3 Implantación 556
11.4.4 Control de concurrencia 560
11.5 BLOQUEOS EN SISTEMAS DISTRIBUIDOS 564
11.5.1 Detección distribuida de bloqueos 566
11.5.2 Prevención distribuida de bloqueos 569
11.6 RESUMEN 572
12 PROCESOS Y PROCESADORES EN SISTEMAS DISTRIBUIDOS 575
12.1 HILOS (THREADS) 575
12.1.1 Introducción a los hilos 576
12.1.2 Uso de hilos 577
12.1.3 Aspectos del diseño de un paquete de hilos 580
12.1.4 Implantación de un paquete de hilos 584
12.1.5 Hilos y RPC 587
12.1.6 Un ejemplo de paquete de hilos 589
12.2 MODELOS DE SISTEMAS 593
12.2.1 El modelo de estación de trabajo 594
12.2.2 Uso de estaciones de trabajo inactivas 597
12.2.3 El modelo de la pila de procesadores 601
12.2.4 Un modelo híbrido 605
12.3 ASIGNACION DE PROCESADORES 605
12.3.1 Modelos de asignación 606
12.3.2 Aspectos del diseño de algoritmos de asignación de procesadores 608
12.3.3 Aspectos de la implantación de algoritmos de asignación de procesadores 610
12.3.4 Ejemplo de algoritmos de asignación de procesadores 612
12.4 PLANIFICACION EN SISTEMAS DISTRIBUIDOS 618
12.5 RESUMEN 620
13 SISTEMAS DISTRIBUIDOS DE ARCHIVOS 623
13.1 DISEÑO DE SISTEMAS DISTRIBUIDOS DE ARCHIVOS 624
13.1.1 La interfaz del servicio de archivos 624
13.1.2 La interfaz del servidor de directorios 626
13.1.3 Semántica de los archivos compartidos 631
13.2 IMPLANTACION DE UN SISTEMA DISTRIBUIDO DE ARCHIVOS 634
13.2.1 Uso de archivos 635
13.2.2 Estructura del sistema 637
13.2.3 Ocultamiento 640
13.2.4 Réplica 646
13.2.5 Un ejemplo: el sistema de archivos Andrew 651
13.2.6 Lecciones aprendidas 657
13.3 TENDENCIAS EN LOS SISTEMAS DISTRIBUIDOS DE ARCHIVOS 658
13.3.1 Hardware reciente 659
13.3.2 Escalabilidad 661
13.3.3 Redes en un área amplia 662
13.3.4 Usuarios móviles 663
13.3.5 Tolerancia de fallos 664
13.4 RESUMEN 664
14 ESTUDIO 3: AMOEBA 667
14.1 INTRODUCCION A AMOEBA 667
14.1.1 Historia de Amoeba 667
14.1.2 Objetivos de la investigación 668
14.1.3 La arquitectura del sistema Amoeba 669
14.1.4 El micronúcleo (microkernel) de Amoeba 671
14.1.5 Los servidores de Amoeba 673
14.2 OBJETOS Y POSIBILIDADES EN AMOEBA 675
14.2.1 Posibilidades 675
14.2.2 Protección de objetos 676
14.2.3 Operaciones usuales 678
14.3 ADMINISTRACION DE PROCESOS EN AMOEBA 679
14.3.1 Procesos 680
14.3.2 Hilos 682
14.4 ADMINISTRACION DE LA MEMORIA EN AMOEBA 683
14.4.1 Segmentos 684
14.4.2 Segmentos mapeados 684
14.5 COMUNICACION EN AMOEBA 684
14.5.1 Llamada a un procedimiento remoto (RPC) 685
14.5.2 Comunicación en grupo en Amoeba 689
14.5.3 El protocolo Internet Fast Local (FLIP) 698
14.6 LOS SERVIDORES DE AMOEBA 706
14.6.1 El servidor de archivos 707
14.6.2 El servidor de directorios 711
14.6.3 El servidor de réplicas 717
14.6.4 El servidor de ejecución 717
14.6.5 El servidor de arranque 719
14.6.6 El servidor TCP/IP 719
14.6.7 Otros servidores 720
14.7 RESUMEN 720
15 ESTUDIO 4: MACH 723
15.1 INTRODUCCION A MACH 723
15.1.1 Historia de Mach 723
15.1.2 Objetivos de Mach 724
15.1.3 El micronúcleo (microkernel) de Mach 725
15.1.4 El servidor BSD UNIX de Mach 727
15.2 ADMINISTRACION DE LOS PROCESOS EN MACH 728
15.2.1 Procesos 728
15.2.2 Hilos 731
15.2.3 Planificación 734
15.3 ADMINISTRACION DE LA MEMORIA EN MACH 737
15.3.1 Memoria virtual 738
15.3.2 Memoria compartida 741
15.3.3 Administradores de la memoria externa 744
15.3.4 Memoria compartida distribuida en Mach 748
15.4 COMUNICACION EN MACH 749
15.4.1 Puertos 749
15.4.2 Envío y recepción de mensajes 756
15.4.3 El servidor de mensajes de la red 761
15.5 EMULACION DE BSD UNIX EN MACH 763
15.6 COMPARACION DE AMOEBA Y MACH 765
15.6.1 Filosofía 765
15.6.2 Objetos 766
15.6.3 Procesos 767
15.6.4 Modelo de memoria 768
15.6.5 Comunicación 769
15.6.6 Servidores 770
15.7 RESUMEN 770
A LISTA DE LECTURAS Y BIBLIOGRAFIA 774
A.1 SUGERENCIAS PARA LECTURA POSTERIOR 774
A.1.1 Introducción y obras generales 774
A.1.2 Procesos 775
A.1.3 Administración de la memoria 776
A.1.4 Sistemas de archivos 776
A.1.5 Entrada/Salida 777
A.1.6 Bloqueos 778
A.1.7 UNIX 778
A.1.8 MS-DOS 779
A.1.9 Introducción a los sistemas distribuidos 780
A.1.10 Comunicación en sistemas distribuidos 781
A.1.11 Sincronización en sistemas distribuidos 781
A.1.12 Procesos y procesadores en sistemas distribuidos 782
A.1.13 Sistemas distribuidos de archivos 782
A.1.14 Amoeba 783
A.1.15 Mach 784
A.2 BIBLIOGRAFIA EN ORDEN ALFABETICO 784
B INTRODUCCION A C 798
B.1 FUNDAMENTOS DE C 798
B.2 TIPOS BASICOS DE DATOS 799
B.3 TIPOS CONSTRUIDOS 800
B.4 ENUNCIADOS 802
B.5 EXPRESIONES 805
B.6 ESTRUCTURA DE UN PROGRAMA 807
B.7 EL PREPROCESADOR DE C 807
B.8 EXPRESIONES IDIOMATICAS 808