Sistemas operativos : conceptos y diseño / Milan Milenkovic.

Incluye diskette, nº inv. RE0222

CONTENIDO
PARTE 1: CONCEPTOS FUNDAMENTALES
1. INTRODUCCION 3
1.1. EVOLUCION DE LOS SISTEMAS OPERATIVOS 4
1.1.1. Procesamiento serie 5
1.1.2. Procesamiento por lotes 7
1.1.3. Multiprogramación 9
1.2. TIPOS DE SISTEMAS OPERATIVOS 11
1.2.1. Sistemas operativos de lotes 12
1.2.2. Sistemas operativos de multiprogramación 12
Sistemas de tiempo compartido 14
Sistemas de tiempo real 15
Sistemas operativos combinados 16
1.2.3. Sistemas operativos distribuidos 16
1.3. DIFERENTES PERSPECTIVAS DE UN SISTEMA OPERATIVO 17
1.3.1. El sistema operativo desde la perspectiva del usuario del lenguaje de órdenes 17
1.3.2. El sistema operativo desde la perspectiva del usuario de las llamadas al sistema 19
1.4. RECORRIDO DE LA EJECUCION DE UNA ORDEN 21
1.5. DISEÑO E IMPLEMENTACION DE SISTEMAS OPERATIVOS 23
1.5.1 Requisitos funcionales 23
1.5.2. Implementación 25
1.6. RESUMEN 29
OTRAS LECTURAS 29
2. PROCESOS 31
2.1. CONCEPTO DE PROCESO 32
2.1.1. División implícita y explícita en tareas 34
2.1.2. Relaciones entre procesos 35
2.2. LOS PROCESOS DESDE LA PERSPECTIVA DEL PROGRAMADOR DE SISTEMAS 36
2.2.1. Ejemplo de multitarea 37
2.2.2. Sincronización entre procesos 39
2.2.3. Comportamiento de los procesos del ejemplo 40
2.2.4. Epilogo: los procesos desde la perspectiva del programador de sistemas 48
2.3. LOS PROCESOS DESDE LA PERSPECTIVA DEL SISTEMA OPERATIVO 49
2.3.1. Bloque de control de proceso (BCP) 51
2.3.2. Estado del sistema y listas de procesos 52
2.3.3. Transiciones de estado de un proceso 53
2.3.4. Conmutación de procesos 56
2.3.5. Hebras de ejecución (threads) 58
2.4. SERVICIOS DEL SISTEMA OPERATIVO PARA GESTION DE PROCESOS 59
CREAR (IDproceso, atributos) 60
ELIMINAR (IDproceso) 61
ABORTAR (IDproceso) 61
DIVIDIR/UNIR (FORK/JOIN) 62
SUSPENDER (IDproceso) 62
REANUDAR (IDproceso) 63
RETARDAR (IDproceso, tiempo) 63
LEER_A TRIBUTOS (IDproceso, grupo-atributos) 64
MODIFICAR_PRIORIDAD (IDproceso, nueva_prioridad) 64
2.4.1. Respuestas de error 65
2.5. PLANIFICACION 65
2.5.1. Tipos de planificadores 66
Planificador a largo plazo 66
Planificador a medio plazo 67
Planificador a corto plazo 68
2.5.2. Criterios de planificación y rendimiento 69
2.5.3. Diseño del planificador 71
2.6. ALGORITMOS DE PLANIFICACION 72
2.6.1. Planificación FCFS (First-Come, First-Served) 73
2.6.2. Planificación SRTN (Shortest Remaining Time Next) 75
2.6.3. Planificación por reparto del tiempo (RR, Round Robin) 78
2.6.4. Planificación con expropiación basada en prioridades (ED, Event Driven) 84
2.6.5. Planificación MLQ (Multiple-Level Queues) 85
2.6.6. Planificación por multiples colas con reglamentación 87
2.7. EVALUACION DEL RENDIMIENTO 87
2.7.1. FCFS (loses) 91
2.7.2. Primero el trabajo mas corto 91
2.7.3. Reparto del tiempo 92
2.8. RESUMEN 93
OTRAS LECTURAS 94
EJERCICIOS 94
3. SINCRONIZACION ENTRE PROCESOS 97
3.1. NECESIDAD DE SINCRONIZACION ENTRE PROCESOS 98
3.2. EXCLUSION MUTUA 101
3.2.1. Primer algoritmo 103
3.2.2. Segundo algoritmo 106
3.2.3. Tercer algoritmo 108
3.3. SEMAFOROS 109
3.3.1. Definición de semáforo e implementación con espera activa 110
3.3.2. Propiedades y características de los semáforos 113
Disciplina de servicio de los semáforos 114
Granularidad de los semáforos 115
3.4. SOPORTE HARDWARE PARA EXCLUSION MUTUA 115
3.4.1. Control de concurrencia pesimista y optimista 116
3.4.2. Habilitar/deshabilitar interrupciones 117
3.4.3. Instrucción comprobar-y-fijar 119
3.4.4. Instrucción comparar-e-intercambiar 122
3.5. IMPLEMENTACION DE SEMAFOROS CON COLAS 125
3.6. PROBLEMAS CLASICOS EN PROGRAMACION CONCURRENTE 127
3.6.1. Productores/consumidores 127
Productores y consumidores con un bufer ilimitado 127
Productores y consumidores con un bufer limitado 131
3.6.2. Lectores y escritores 134
3.7. RESUMEN 137
OTRAS LECTURAS 138
EJERCICIOS 139
4. COMUNICACION Y SINCRONIZACION ENTRE PROCESOS 145
4.1. REGIONES CRITICAS Y REGIONES CRITICAS CONDICIONALES 146
4.2. MONITORES 148
4.3. MENSAJES 156
4.3.1. Aspectos de la implementación de mensajes 157
Denominación 158
Copia 159
Intercambio sincrono o asincrono de mensajes 161
Longitud de los mensajes 163
4.3.2. Comunicación y sincronización entre procesos mediante mensajes 163
4.3.3. Señalización de interrupciones mediante mensajes 168
4.4. SINCRONIZACION Y COMUNICACION ENTRE PROCESOS EN ADA 171
4.4.1. El mecanismo de entrada-aceptación (entry-accept) 173
4.4.2. La instrucción SELECT 176
4.5. INTERBLOQUEOS 180
4.5.1. Recursos reutilizables y consumibles 183
4.5.2. Prevención de interbloqueos 184
4.5.3. Evitación de interbloqueos 187
Petición de recurso 189
Liberación de recurso 190
4.5.4. Detección y recuperación de interbloqueos 191
4.5.5. Método combinado 195
4.6. RESUMEN 196
OTRAS LECTURAS 197
EJERCICIOS 199
5. GESTION DE MEMORIA: ASIGNACION CONTIGUA 203
5.1. MONITOR DE UN SOLO PROCESO 206
5.2. ASIGNACION DE MEMORIA PARTICIONADA. ESTATICA 209
5.2.1. Principios de operación 210
5.2.2. Intercambio (swapping) 214
5.2.3. Reubicación 217
Reubicación estática 217
Reubicación dinámica 218
5.2.4. Protección 220
5.2.5. Compartición 222
5.2.6. Comentarios finales 223
5.3. ASIGNACION DE MEMORIA PARTICIONADA. DINAMICA 224
5.3.1. Principios de operación 225
5.3.2. Compactación 231
5.3.3. Protección 234
5.3.4. Compartición 235
5.3.5. Comentarios finales 237
5.4. SEGMENTACION 238
5.4.1. Principios de operación 239
Traducción de direcciones 241
Registros descriptores de segmento 243
5.4.2. Protección 246
5.4.3. Compartición 247
5.4.4. Comentarios finales 249
5.5. RESUMEN 251
OTRAS LECTURAS 252
EJERCICIOS 252
6. GESTION DE MEMORIA: ASIGNACION NO CONTIGUA 255
6.1. PAGINACION 256
6.1.1. Principios de operación 256
6.1.2. Asignación de paginas 259
6.1.3. Soporte hardware pare paginación 260
6.1.4. Protección y compartición 264
6.1.5. Comentarios finales 266
6.2. MEMORIA VIRTUAL 266
6.2.1. Principios de operación 268
6.2.2. Posibilidad de interrumpir las instrucciones 270
6.2.3. Gestión de memoria virtual 273
6.2.4. Comportamiento de los programas 275
6.2.5. Políticas de sustitución 277
Cadenas de referencia a memoria 278
Algoritmos de sustitución 279
Políticas de sustitución globales y locales 284
6.2.6. Políticas de asignación 284
Frecuencia de fallos de pagina (FFP) 288
6.2.7. Conjunto operativo: una teoría pare la sustitución y asignación de páginas 289
6.2.8. Soporte y consideraciones hardware 291
6.2.9. Protección y compartición 293
6.2.10. Segmentación y paginación 294
6.2.11. Jerarquía de tablas de traducción de direcciones y unidades de gestión de memoria (MMU) 296
6.2.12. Consideraciones sobre Unix 299
6.2.13. Comentarios finales 300
6.3. RESUMEN 301
6.4. OTRAS LECTURAS 302
6.5. EJERCICIOS 303
7. GESTION DE ARCHIVOS 307
7.1. El sistema de archivos desde la perspectiva del usuario del lenguaje de ordenes 308
7.1.1. Servicios de archivos en el lenguaje de órdenes 313
7.2. El sistema de archivos desde la perspectiva del programador de sistemas 316
7.3. ORGANIZACION DEL DISCO 320
7.3.1. Tiempo de acceso al disco 321
7.4. CONTROLADOR Y RUTINA DEL DISCO 322
7.5. LA GESTION DE ARCHIVOS DESDE LA PERSPECTIVA DEL SISTEMA OPERATIVO 326
7.5.1. Directorios 329
7.5.2. Gestión del espacio de disco 335
Asignación contigua 336
Asignación no contigua 339
7.5.3. Anatomía de la traducción de direcciones de disco 345
7.5.4. Servicios del sistema relativos a archivos 352
7.5.5. Entrada/salida asíncrona 357
7.6. CACHES DE DISCO Y CACHE DE BUFERES EN UNIX 358
7.7. GENERALIZACION DE LOS SERVICIOS DE ARCHIVOS 363
7.7. RESUMEN 365
OTRAS LECTURAS 367
EJERCICIOS 367
8. SEGURIDAD Y PROTECCION 371
8.1. AMENAZAS Y OBJETIVOS DE SEGURIDAD 372
8.2. INTENTOS DE PENETRACION 374
8.3. POLITICAS Y MECANISMOS DE SEGURIDAD 375
8.3.1. Políticas de seguridad 376
8.3.2. Mecanismos de seguridad y principios de diseño 377
8.4. VALIDACION 378
8.4.1. Contraseñas 379
8.4.2. Validación basada en artefactos 380
8.4.3. Técnicas biométricas 381
8.5. PROTECCION Y CONTROL DE ACCESO 381
8.5.1. Protección en sistemas informáticos 382
8.5.2. Modelo de protección por matriz de accesos 383
8.5.3. Jerarquías de accesos 385
8.5.4. Listas de accesos 387
8.5.5. Capacidades 388
8.5.6. Cerraduras y llaves 392
8.6. MODELOS FORMALES DE PROTECCION 393
8.6.1. Matriz de control de accesos 393
8.6.2. Modelo Tomar-Conceder 396
8.6.3. Modelo Bell-LaPadula 397
8.6.4. Modelo Retículo de Flujo de Información 399
8.7. CRIPTOGRAFIA 402
8.7.1. Criptografía convencional 403
8.7.2. La norma de cifrado de datos (DES, data encryption standard) 406
8.7.3. Criptografía con clave publica 407
8.7.4. Algoritmo de Rivest, Shamir, Adelman (RSA) 408
Validación 410
Firmas digitales 411
8.8. GUSANOS Y VIRUS 412
8.8.1. Gusanos informáticos 412
8.8.2. Virus informáticos 414
8.9. RESUMEN 416
OTRAS LECTURAS 418
EJERCICIOS 419
PARTE II: IMPLEMENTACION
9. ENTRADA/SALIDA: PRINCIPIOS Y PROGRAMACION 423
9.1. EL PROBLEMA DE LA ENTRADA/SALIDA 424
9.1.1. Operación asincrona 424
9.1.2. Diferencia de velocidad: procesador frente a periféricos 425
9.2. INTERFACES DE ENTRADA/SALIDA 427
9.2.1. Registros bufer 431
9.2.2. Registros de ordenes 432
9.2.3. Registros de estado 433
9.3. EJEMPLOS DE PUERTOS DE E/S 433
9.3.1. El receptor/transmisor universal sincrono/asincrono (USART) 433
9.3.2. Temporizadores de intervalo programable(PIT) 437
9.4. E/S CONTROLADA POR PROGRAMA 438
9.4.1. Control de un solo dispositivo 439
9.4.2. Control de múltiples dispositivos: encuesta 444
9.5. E/S GUIADA POR INTERRUPCIONES 446
9.5.1. Control de un solo dispositivo 446
Conmutación de contexto 446
Rutina de servicio de interrupción (RSI) 448
9.5.2. Control de múltiples dispositivos 452
Vectorización de interrupciones 453
Niveles de control de interrupciones 455
Niveles de prioridad 456
Resumen del procesamiento de interrupciones 456
9.6. E/S CONCURRENTE 457
9.7. RESUMEN 463
OTRAS LECTURAS 464
EJERCICIOS 465
10. DISEÑO DEL NUCLEO DE UN SISTEMA OPERATIVO MULTITAREA (KMOS) 471
10.1. DEFINICION DE LOS SERVICIOS DE KMOS 473
10.2. PRINCIPALES DECISIONES DE DISENO 476
10.3. TRANSICIONES DE ESTADO DE LOS PROCESOS EN KMOS 477
10.4. ESPECIFICACION FUNCIONAL DE KMOS 479
10.4.1. Despacho de procesos 480
10.4.2. Comunicación y sincronización entre procesos 481
Buzones y mensajes 481
Las operaciones ENVIAR y RECIBIR 484
10.4.3. Gestión de interrupciones 487
10.4.4. Gestión de procesos 490
Creación de procesos 490
Retardar un proceso durante un tiempo especificado 491
10.4.5. Arranque del sistema 493
10.5. Consideraciones sobre la implementación 495
10.5.1. Lenguajes de implementaron de sistemas 495
Facilidades para desarrollo modular de programas 496
Acceso al hardware y a las direcciones físicas de memoria 499
10.5.2. Invocación al sistema operativo 500
Llamada a procedimiento 500
Llamada a supervisor 501
Interrupción software 502
10.6. RESUMEN 503
OTRAS LECTURAS 504
EJERCICIOS 504
11. IMPLEMENTACION DE KMOS 509
11.1. LISTAS DEL SISTEMA KMOS 510
11.2. LA LISTA PREPARADOS Y SU MANIPULACION 513
11.2.1. Implementaron de la lista Preparados en KMOS 513
11.2.2. Bloque de control de proceso 515
Gestión de las pilas de procesos 515
Estructura del bloque de control de proceso 516
11.2.3. Inserciones en la lista Preparados 517
11.2.4. El proceso nulo 519
11.3 COMUNICACION Y SINCRONIZACION ENTRE PROCESOS 521
11.3.1. Buzones y mensajes 521
11.3.2. La operación ENVIAR 523
11.3.3. La operación RECIBIR 525
11.4. GESTION DE PROCESOS 526
11.4.1. Creación de procesos 526
11.4.2. Eliminación de procesos 528
11.4.3. Despacho de procesos 528
11.4.4. Retardo de un proceso durante un tiempo especificado 531
Gestión del temporizador y lista Retardados 531
La operación RETARDAR 535
Procesamiento de interrupciones del temporizador 536
11.4.5. El procedimiento SPILA 538
11.5. GESTION DE INTERRUPCIONES 539
11.5.1. Buzones y prioridades de interrupción 539
11.5.2. Servicio de interrupciones en KMOS 541
1 1.5.3. Habilitación de los niveles de interrupción hardware 543
11.6. ARRANQUE Y CONFIGURACION INICIAL DEL SISTEMA 544
11.7. RESUMEN 544
OTRAS LECTURAS 545
EJERCICIOS 546
CODIGO FUENTE DE KMOS EN PASCAL 549
PARTE III : TEMAS AVANZADOS
12. SISTEMAS MULTIPROCESADORES 573
12.1. MOTIVACION Y CLASIFICACION 574
12.1.1. Ventajas de los multiprocesadores 574
12.1.2. Clasificación de los multiprocesadores 575
12.2. INTERCONEXIONES EN LOS MULTIPROCESADORES 577
12.2.1. Sistemas orientados a bus 577
12.2.2. Sistemas conectados por barras cruzadas 579
12.2.3. Hipercubos 580
12.2.4. Sistemas basados en conmutadores multietapa 582
12.3. TIPOS DE SISTEMAS OPERATIVOS MULTIPROCESADORES 584
12.3.1. Supervisores separados 584
12.3.2. Maestro/esclavos 585
12.3.3. Simétrico 585
12.4. FUNCIONES Y REQUISITOS DE LOS SISTEMAS OPERATIVOS MULTIPROCESADORES 586
12.5. CUESTIONES DE DISEÑO E IMPLEMENTACION DEL SISTEMA OPERATIVO 588
1 2.5.1. Gestión y planificación de los procesadores 588
Soporte para multiprocesamiento 588
Asignación de recursos de procesamiento 589
Planificación 590
12.5.2. Gestión de memoria 592
12.6. INTRODUCCION A LA PROGRAMACION PARALELA 593
12.6.1. Ganancia de velocidad 593
12.6.2. Un ejemplo de programación paralela: multiplicación de matrices 594
12.6.3. FORK (DIVIDIR) y JOIN (UNIR) en multiprocesadores 597
12.7. SINCRONIZACION EN MULTIPROCESADORES 598
12.7.1. Comprobar-y-fijar 599
12.7.2. Comparar-e-intercambiar 600
12.7.3. Acceder-y-sumar 602
12.8. RESUMEN 604
OTRAS LECTURAS 605
EJERCICIOS 606
13. SISTEMAS OPERATIVOS DISTRIBUIDOS: ALGORITMOS 609
13.1. MOTIVACION DE LOS SISTEMAS DISTRIBUIDOS 610
1.3.1.1. Por que distribuidos? 610
13.1.2. Que es distribuido? 613
13.2. REDES DE COMPUTADORES 614
13.2.1. Redes de área extensa 615
13.2.2. Redes de área local 619
1 3.2.3. Protocolos de comunicación y el modelo OSI 621
Capa física 622
Capa de enlace de datos 622
Capa de red 623
Capa de transporte 623
Capa de sesión 624
Capa de presentación 624
Capa de aplicación 624
13.3. ALGORITMOS PARA PROCESAMIENTO DISTRIBUIDO 625
13.3.1. El entorno y suposiciones habituales 626
1 3.3.2. El tiempo y la ordenación de los sucesos 628
13.3.3. La exclusión mutua en los sistemas distribuidos 630
Algoritmo de Lamport 631
Algoritmo de Ricart y Agrawala 632
13.3.4. Transacciones 633
13.3.5. Control de concurrencia distribuida e interbloqueos 634
13.4. TRATAMIENTO DE FALLOS 637
13.4.1. Fallos en sistemas distribuidos 638
13.4.2. Elección de un sucesor 639
13.4.3. Regeneración de un testigo perdido 641
13.4.4. Consecución de acuerdos 642
13.5. RESUMEN 647
OTRAS LECTURAS 648
EJERCICIOS 649
14. SISTEMAS OPERATIVOS DISTRIBUIDO: IMPLEMENTACION 651
14.1. MODELOS DE SISTEMAS DISTRIBUIDOS 652
14.1.1. El modelo basado en hosts 653
14.1.2. El modelo deposito de procesadores 653
14.1.3. El modelo estaciones de trabajo/servidores 654
14.1.4. El modelo integrado 656
14.2. DENOMINACION 657
14.2.1. Mapas estáticos 659
14.2.2. Difusión 660
14.2.3. Servidores de nombres 660
14.2.4. Tablas de prefijos 661
14.3. MIGRACION DE PROCESOS 662
14.4. LLAMADAS A PROCEDIMIENTOS REMOTOS 666
14.4.1. Transferencia de control 667
14.4.2. Vinculación 669
14.4.3. Flujo de datos 670
1 4.4.4. Aspectos del diseño de un servidor RPC 671
14.4.5. RPC frente a paso de mensajes 673
14.5. MEMORIA COMPARTIDA DISTRIBUIDA 674
14.6. SISTEMAS DE ARCHIVOS DISTRIBUIDOS 676
14.6.1. División cliente/servidor del trabajo 677
14.6.2. Caché de archivos y semántica de consistencia 681
14.6.3. Constancia del estado y rendimiento 684
14.6.4. Tolerancia a fallos 685
14.7.RESUMEN 687
OTRAS LECTURAS 688
EJERCICIOS 689
PARTE IV: ESTUDIO DE CASOS PARTICULARES
15. ESTUDIO DE CASOS PARTICULARES 693
15.1. SISTEMA OPERATIVO PC-DOS (MS-DOS) 694
15.1.1. PC-DOS desde la perspectiva del usuario del lenguaje de órdenes 694
15.1.2. PC-DOS desde la perspectiva del usuario de llamadas al sistema 696
15.1.3. Implementación de PC-DOS 698
15.1.4. Resumen de PC-DOS 701
15.2. SISTEMA OPERATIVO UNIX 702
15.2.1. UNIX desde la perspectiva del usuario del lenguaje de órdenes 703
15.2.2. UNIX desde la perspectiva del usuario de llamadas al sistema 710
15.2.3. Implementación de UNIX 713
15.2.4. Resumen de UNIX 719
15.3. SISTEMA OPERATIVO iRMX 86 719
15.3.1. iRMX 86 desde la perspectiva del usuario del lenguaje de órdenes 721
15.3.2. iRMX 86 desde la perspectiva del usuario de llamadas al sistema 722
15.3.3. Implementación de iRMX 86 730
15.3.4. Resumen de iRMX 86 733
15.4. DISEÑO DE UNA UNIDAD DE TELEMETRIA REMOTA (UTR) 734
15.4.1. Sistemas de control y adquisición de datos por computador 734
15.4.2. Misión de una unidad de telemetría remota (UTR) 737
15.4.3. Organización funcional y actividades de una UTR 740
15.4.4. Organización del software de una UTR (procesos) 744
15.4.5. Estructuras de datos y comunicación entre procesos en una UTR 746
15.4.6. Operación de los procesos de la UTR 749
15.4.7. Los procesos de la UTR y KMOS 753
15.4.8. Comentarios finales 754
OTRAS LECTURAS 756
Apéndice A. Ejemplos de uso de KMOS: Pascal 757
Apéndice B. Código fuente de KMOS: C 767
Apéndice C. Ejemplos de uso de KMOS: C 791
Bibliografía 801
Indice analítico 813