Portada SISTEMAS OPERATIVOS
Conceptos y diseño

ÍNDICE

Prólogo ....XXI

PARTE I: CONCEPTOS FUNDAMENTALES

1. Introducción ....3
1.1. EVOLUCIÓN 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 EJECUCIÓN DE UNA ORDEN ....21
1.5. DISEÑO E IMPLEMENTACIÓN 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. Epílogo: 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_TRIBUTOS (IDproceso, grupo atributos); ....64
MODIFICAR_PRIORIDAD (IDproceso, nueva prioridad); ....64
2.4.1. Respuestas de error ....65
2.5 PLANIFICACIÓN ....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 múltiples colas con realimentación ....87
2.7. EVALUACIÓN DEL RENDIMIENTO ....87
2.7.1. FCFS (lotes) ....91
2.7.2. Primero el trabajo más corto ....91
2.7.3. Reparto del tiempo ....92
2.8. RESUMEN ....93
OTRAS LECTURAS ....94
EJERCICIOS ....94

3. Sincronización entre procesos ....97

3.1. NECESIDAD DE SINCRONIZACIÓN ENTRE PROCESOS ....98
3.2. EXCLUSIÓN MUTUA ....101
3.2.1. Primer algoritmo ....103
3.2.2. Segundo algoritmo ....106
3.2.3. Tercer algoritmo ....108
3.3. SEMÁFOROS ....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 EXCLUSIÓN 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. IMPLEMENTACIÓN DE SEMÁFOROS CON COLAS ....125
3.6. PROBLEMAS CLÁSICOS EN PROGRAMACIÓN CONCURRENTE ....127
3.6.1. Productores/consumidores ....127
Productores y consumidores con un búfer ilimitado ....127
Productores y consumidores con un búfer limitado ....131
3.6.2. Lectores y escritores ....134
3.7. RESUMEN ....137
OTRAS LECTURAS ....138
EJERCICIOS ....139

4. Comunicación y sincronización entre procesos ....145

4.1. REGIONES CRÍTICAS Y REGIONES CRÍTICAS 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 síncrono o asíncrono 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. SINCRONIZACIÓN Y COMUNICACIÓN 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. Gestión de memoria: asignación contigua ....203

5.1. MONITOR DE UN SOLO PROCESO ....206
5.2. ASIGNACIÓN DE MEMORIA PARTICIONADA. ESTÁTICA ....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. ASIGNACIÓN DE MEMORIA PARTICIONADA. DINÁMICA ....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. SEGMENTACIÓN ....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. Gestión de memoria: asignación no contigua ....255

6.1. PAGINACIÓN ....256
6.1.1. Principios de operación ....256
6.1.2. Asignación de páginas ....259
6.1.3. Soporte hardware para 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 página (FFP) ....288
6.2.7. Conjunto operativo: una teoría para 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
OTRAS LECTURAS ....302
EJERCICIOS ....303

7. Gestión de archivos ....307
7.1. EL SISTEMA DE ARCHIVOS DESDE LA PERSPECTIVA DEL USUARIO DEL LENGUAJE DE ÓRDENES ....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. ORGANIZACIÓN DEL DISCO ....320
7.3.1. Tiempo de acceso al disco ....321
7.4. CONTROLADOR Y RUTINA DEL DISCO ....322
I-A GESTIÓN 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 BÚFERES EN UNIX ....358
7.7. GENERALIZACIÓN DE LOS SERVICIOS DE ARCHIVOS ....363
7.8. RESUMEN ....365
OTRAS LECTURAS ....367
EJERCICIOS ....367

8. Seguridad y protección ....371
8.1. AMENAZAS Y OBJETIVOS DE SEGURIDAD ....372
8.2. INTENTOS DE PENETRACIÓN ....374
8.3. POLÍTICAS 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. VALIDACIÓN ....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. PROTECCIÓN 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 PROTECCIÓN ....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. CRIPTOGRAFÍA ....402
8.7.1. Criptografia convencional ....403
8.7.2. La norma de cifrado de datos (DES, data encryption standard) ....406
8.7.3. Criptografía con clave pública ....407
El 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: IMPLEMENTACIÓN

9. Entrada/salida: principios y programación ....423
9.1. EL PROBLEMA DE LA ENTRADA/SALIDA ....424
9.1.1. Operación asíncrona ....424
9.1.2. Diferencia de velocidad: procesador frente a periféricos ....425
9.2. INFERFACES DE ENTRADA/SALIDA ....427
9.2.1. Registros búfer ....431
9.2.2. Registros de órdenes ....432
9.2.3. Registros de estado ....433
9.3. EJEMPLOS DE PUERTOS DE E/S ....433
9.3.1. El receptor/transmisor universal síncrono/asíncrono (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 núcleo de un sistema operativo multitarea (KMOS) ....471

10.1. DEFINICIÓN DE LOS SERVICIOS DE KMOS ....473
10.2. PRINCIPALES DECISIONES DE DISEÑO ....476
10.3. TRANSICIONES DE ESTADO DE LOS PROCESOS EN KMOS ....477
10.4. ESPECIFICACIÓN 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 implementación 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. Implementación de KMOS ....509
11.1. LISTAS DEL SISTEMA KMOS ....510
11.2. LA LISTA PREPARADOS Y SU MANIPULACION ....513
11.2.1. Implementación 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. COMUNICACIÓN Y SINCRONIZACIÓN 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
11.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
CÓDIGO FUENTE DE KMOS EN PASCAL ....549

PARTE III: TEMAS AVANZADOS

12. Sistemas multiprocesadores ....573
12.1. MOTIVACIÓN Y CLASIFICACIÓN ....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 IMPLEMENTACIÓN DEL SISTEMA OPERATIVO ....588
12.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. INTRODUCCIÓN A LA PROGRAMACIÓN 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. SINCRONIZACIÓN 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. MOTIVACIÓN DE LOS SISTEMAS DISTRIBUIDOS ....610
13.1.1. ¿Por qué distribuidos? ....610
13.1.2. ¿Qué 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
13.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
13.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 distribuidos: implementación ....651

14.1. MODELOS DE SISTEMAS DISTRIBUIDOS ....652
14.1.1. El modelo basado en hosts ....653
14.1.2. El modelo depósito de procesadores ....653
14.1.3. El modelo estaciones de trabajo/servidores ....654
14.1.4. El modelo integrado ....656
14.2. DENOMINACIÓN ....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. MIGRACIÓN 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
14.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

l5. 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 TELEMETRÍA 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

Índice analítico ....813

Biblioteca de la UOC