1
Download sistemas_operativos_..
Document related concepts
Transcript
SILBERSCHATZ GALVIN GAGNE de sistemas SÉPTIMA EDICIÓN Fundamentos de sistemas operativos Séptima edición Fundamentos de sistemas operativos Séptima edición ABRAHAM SILBERSCHATZ Yale University PETER BAER GALVIN Corporate Technologies, Inc. GREG GAGNE Westminster College Traducción VUELAPLUMA, S. L. Revisión técnica JESÚS SÁNCHEZ ALLENDE Doctor Ingeniero de Telecomunicación Dpto. de Electrónica y Sistemas Universidad Alfonso X El Sabio Me Graw Hill MADRID BOGOTA • BUENOS AIRES • CARACAS • GUATEMALA • LISBOA MÉXICO • NUEVA YORK • PANAMÁ • SAN JUAN • SANTIAGO • SAO PAULO AUCKLAND • HAMBURGO • LONDRES • MILÁN • MONTREAL • NUEVA DELHI • PARÍS SAN FRANCISCO • SIDNEY • SINGAPUR • ST. LOUIS • TOKIO • TORONTO La información contenida en este libro procede de una obra original publicada por John Wiley & Sons, Inc. No obstante, McGraw-Hill/Interamericana de España no garantiza la exactitud oThe McGraw-HiU Companies m5-- perfección de la información publicada. Tampoco asume ningún tipo de garantía sobre los contenidos y las opiniones vertidas en dichos textos. Este trabajo se publica con el reconocimiento expreso de que se está proporcionando una información, pero no tratando de prestar ningún tipo de servicio profesional o técnico. Los procedimientos y la información que se presentan en este libro tienen sólo la intención de servir como guía general. McGraw-Hill ha solicitado los permisos oportunos para la realización y el desarrollo de esta obra. FUNDAMENTOS DE SISTEMAS OPERATIVOS, 7" EDICIÓN No está permitida la reproducción total o parcial de este libro/ni su tratamiento informático, ni la transmisión de ninguna forma o por cualquier medio, ya sea electrónico, mecánico, por fotocopia, por registro u otros métodos, sin el permiso previo y por escrito de los titulares del Copyright. McGraw-Hill / Interamericana de España, S. A. U. DERECHOS RESERVADOS © 2006, respecto a la séptima edición en español, por McGRAW-HILL/lNTERAMERICANA DE ESPAÑA, S. A. U. Edificio Valrealty, I a planta Basauri, 17 28023 Aravaca(Madrid) http://www. mcgraw-hill. es universidad&mcgraw-hill.com Traducido de la séptima edición en inglés de OPERATING SYSTEM CONCEPTS ISBN: 0-471-69466-5 Copyright © 2005 por John Wiley & Sons, Inc. ISBN: 84-481-4641-7 Depósito legal: M. 7.957-2006 Editor: Carmelo Sánchez González Compuesto por: Vuelapluma, S. L. Impreso en: Cofas. S. A. IMPRESO EN ESPAÑA - PRINTED IN SPAIN A mi hijos, Lemor, Sivan y Aaron Avi Silberschatz A mi esposa Carla, y a mis hijos, Gwen Owen y Maddie Peter Baer Galvin A la memoria del tío Sonny, Robert Jon Heileman 1933 -2004 Greg Gagne Abraham Stibersehafz es catedrático de Informática en la Universidad de Yale. Antes de entrar en esa universidad, fue vicepresidente del laboratorio Information Sciencies Research Center de Bell Laboratories, Murray Hill, New Jersey, Estados Unidos. Con anterioridad, fue profesor en el Departamento de Ciencias de la Computación de la Universidad de Texas, en Austin. Entre sus intereses de investigación se incluyen los sistemas operativos, los sistemas de bases de datos, los sistemas de tiempo real, los sistemas de almacenamiento, la gestión de red y los sistemas distribuidos. Además de los puestos que ha ocupado dentro del mundo académico e industrial, el profesor Silberschatz ha sido miembro del Panel de Biodiversidad y Ecosistemas del Comité de Asesores Científicos y Tecnológicos del Presidente Clinton, además de ser Consejero de la organización National Science Foundation y consultor para diversas empresas industriales. El profesor Silberschatz es socio de ACM y del IEEE. En 2002, recibió el premio IEEE Taylor L. Booth Education Award, en 1998 el ACM Karl V. Karlstom Outstanding Educator Award y en 1997 el ACM SIGMOND Contribution Award; también ha sido galardonado por la organi-zación IEEE Computer Society por el artículo "Capability Manager" que apareció en la revista IEEE Transactions on Software Engineering. Sus escritos han sido publicados en numerosas revistas de ACM y del IEEE, además de en otras revistas y conferencias de carácter profesional. Es coautor del libro de texto Fundamentos de bases de datos publicado también en castellano por McGraw-Hill. Greg Gúgne es jefe del departamento de Informática y Matemáticas de Westminster College en Salt Lake City (Estados Unidos), donde ha estado impartiendo clases desde 1990. Además de enseñar sistemas operativos, también imparte clases sobre redes informáticas, sistemas distribuidos, programación orientada a objetos y estructuras de datos. También imparte seminarios a profesores de informática y profesionales de la industria. Los intereses de investigación actuales del profesor Gagne incluyen los sistemas operativos de nueva generación y la informática distribuida. Pefer Baer GaMrt es Director técnico de Corporate Technologies (www.cptech.com). Con anterioridad, Peter era administrador de sistemas del Departamento de Informática de la Universidad de Brown. También es editor asociado de la revista SysAdmin. Peter Galvin ha escrito artículos para Byte y otras revistas y, anteriormente, se encargaba de las columnas sobre seguridad y administración de sistemas en ITWorld. Como consultor y forma- dor, Peter ha impartido numerosas conferencias y cursos en todo el mundo sobre seguridad y administración de sistemas. Prefacio Los sistemas operativos son una parte esencial de cualquier sistema informático. Del mismo modo, un curso sobre sistemas operativos es una parte esencial de cualquier carrera de Informática. Este campo está cambiando muy rápidamente, ya que ahora las computadoras se encuentran prácticamente en cualquier aplicación, desde juegos para niños hasta herramientas de planificación extremadamente sofisticadas para los gobiernos y las grandes multinacionales. Sin embargo, los conceptos fundamentales siguen siendo bastante claros y es en ellos en los que se basa este libro. Hemos escrito esta obra como libro de texto para un curso de introducción a los sistemas operativos para estudiantes universitarios de primer y segundo ciclo. Esperamos asimismo que los profesionales también lo encuentren útil, ya que proporciona una clara descripción de los conceptos que subyacen a los sistemas operativos. Como prerrequisitos, suponemos que el lector está familiarizado con las estructuras de datos básicas, la organización de una computadora y algún lenguaje de alto nivel, como por ejemplo C. En el Capítulo 1 se han incluido los conceptos sobre hardware necesarios para poder comprender los sistemas operativos. En los ejemplos de código se ha utilizado fundamentalmente el lenguaje C, con algo de Java, pero el lector podrá comprender los algoritmos sin tener un conocimiento profundo de estos lenguajes. Los conceptos se presentan mediante descripciones intuitivas. El libro aborda algunos resultados teóricos importantes, aunque las demostraciones se han omitido. Las notas bibliográficas proporcionan información sobre los libros o artículos de investigación en la aparecieron y se demostraron los conceptos por primera vez, así como referencias a material de lectura adicional. En lugar de demostraciones, se han utilizado figuras y ejemplos para indicar por qué debemos esperar que el resultado en cuestión sea cierto. Los conceptos y algoritmos fundamentales cubiertos en el libro están basados, a menudo, en aquéllos que se emplean en los sistemas operativos comerciales existentes. Nuestro objetivo ha sido presentar estos conceptos y algoritmos para una configuración general que no estuviera ligada a un sistema operativo concreto. Hemos presentado gran cantidad de ejemplos que pertenecen a los más populares e innovadores sistemas operativos, incluyendo Solaris de Sun Microsystems; Linux; Mach; MS-DOS, Windows NT, Windows 2000 y Windows XP de Microsoft; VMS y TOPS-20 de DEC; OS/2 de IBM y Mac OS X de Apple. En este texto, cuando utilizamos Windows XP como sistema de operativo de ejemplo, queremos hacer referencia tanto a Windows XP como a Windows 2000. Si existe una característica en Windows XP que no está disponible en Windows 2000, se indica de forma explícita. Si una característica existe en Windows 2000 pero no en Windows XP, entonces hacemos referencia específicamente a Windows 2000. viii Prefacio Organización de este libro La organización de este texto refleja nuestros muchos años de impartición de cursos sobre sistemas operativos. También hemos tenido en cuenta las aportaciones proporcionadas por los revisores del texto, así como los comentarios enviados por los lectores de las ediciones anteriores. Además, el contenido -del tekto se corresponde con las sugerencias de la recomendación Computing Curricula 2001 para la enseñanza de sistemas operativos, publicado por la Joint Task Forcé de la sociedad IEEE Computing Society y la asociación ACM (Association for Computing Machinery). En la página web en inglés complementaria de este texto proporcionamos diversos planes de estudios que sugieren varios métodos para usar el texto, tanto en cursos de introducción como avanzados sobre sistemas operativos. Como regla general, animamos a los lectores a avanzar de forma secuencial en el estudio de los sistemas operativos. Sin embargo, utilizando un plan de estudios de ejemplo, un lector puede seleccionar un orden diferente de los capítulos (o de las sub- secciones de los capítulos). Contenido del libro El texto está organizado en ocho partes: • Introducción. Los Capítulos 1 y 2 explican lo que son los sistemas operativos, lo que hacen y cómo se diseñan y construyen. Se explican las características comunes de un sistema operativo, lo que un sistema operativo hace por el usuario y lo que hace para el operador del sistema informático. La presentación es de naturaleza motivadora y explicativa. En estos capítulos hemos evitado exponer cómo ocurren las cosas internamente. Por tanto, son adecuados para lectores individuales o para estudiantes de primer ciclo que deseen aprender qué es un sistema operativo sin entrar en los detalles de los algoritmos internos. • Gestión de procesos. Los Capítulos 3 a 7 describen los conceptos de proceso y de concurrencia como corazón de los sistemas operativos modernos. Un proceso es la unidad de trabajo de un sistema. Un sistema consta de una colección de procesos que se ejecutan concurrentemente, siendo algunos de ellos procesos del sistema operativo (aquéllos que ejecutan código del sistema) y el resto, procesos de usuario (aquéllos que ejecutan código del usuario). Estos capítulos exponen los métodos para la sincronización de procesos, la comunicación interprocesos y el tratamiento de los interbloqueos. También se incluye dentro de este tema una explicación sobre las hebras. • Gestión de memoria. Los Capítulos.8 y 9 se ocupan de la gestión de la memoria principal durante la ejecución de un proceso. Para mejorar tanto la utilización de la CPU como su velocidad de respuesta a los usuarios, la computadora debe mantener varios procesos en memoria. Existen muchos esquemas diferentes de gestión de memoria, que se reflejan en diversas técnicas de gestión de memoria. Además, la efectividad de cada algoritmo concreto depende de la situación. • Gestión de almacenamiento. Los Capítulos 10 a 13 describen cómo se gestionan el sistema de archivos, el almacenamiento masivo y las operaciones de E/S en un sistema informático moderno. El sistema de archivos proporciona el mecanismo para el almacenamiento y el acceso en línea a los datos y programas que residen en los discos. Estos capítulos describen los algoritmos y estructuras clásicos internos para gestión del almacenamiento. Proporcionan un firme conocimiento práctico de los algoritmos utilizados, indicando las propiedades, las ventajas y las desventajas. Puesto que los dispositivos de E/S que se conectan a una computadora son muy variado?, el sistema operativo tiene que proporcionar un amplio rango de funcionalidad a las aplicaciones, para permitirlas controlar todos los aspectos de los dispositivos. Se expone en profundidad la E/S del sistema, incluyendo el diseño del sistema de E/S, las interfaces y las estructuras y funciones internas del sistema. En muchos sentidos, los dispositivos de E/S también constituyen los componentes más lentos de la computadora. Puesto que son un cuello de botella que limita las prestaciones del sistema, abordamos también estos problemas de prestaciones. También se explican los temas relativos a los almacenamientos secundario y terciario. • Protección y seguridad. Los Capítulos 14 y 15 se ocupan de los procesos de un sistemá operativo que deben protegerse frente a otras actividades. Con propósitos de protección y seguridad, utilizamos mecanismos que garanticen que sólo los procesos que hayan obtenido la apropiada autorización del sistema operativo puedan operar sobre los archivos, la memoria, la CPU y otros recursos. La protección es un mecanismo que permite controlar el acceso de procesos, programas o usuarios a los recursos Prefacio ix definidos por el sistema informático. Este mecanismo debe proporcionar un medio de especificar los controles que se han de imponer, asi como un medio de imponerlos. Los mecanismos de seguridad protegen la información almacenada en el sistema (tanto los datos como el código) y los recursos físicos del sistema informáticos frente a accesos no autorizados, destrucción o modificación maliciosas e introducción accidental de incoherencias. • Sistemas distribuidos. Los Capítulos 16 a 18 se ocupan de una colección de procesadores que no comparten la memoria, ni tampoco un reloj: un sistema distribuido. Proporcionando al usuario acceso a los diversos recursos que mantiene, un sistema distribuido puede aumentar la velocidad de cálculo y la disponibilidad y Habilidad de los datos. Una arquitectura de este tipo también proporciona al usuario un sistema de archivos distribuido, que es un sistema del servicio de archivos cuyos usuarios, servidores y dispositivos de almacenamiento se encuentran distribuidos por los distintos nodos de un sistema distribuido. Un sistema distribuido debe proporcionar diversos mecanismos para la sincronización y comunicación de procesos y para tratar el problema de los interbloqueos y diversos tipos de fallos que no aparecen en los sistemas centralizados. • Sistemas de propósito especial. Los Capítulos 19 y 20 se ocupan de los sistemas utilizados para propósitos específicos, incluyendo los sistemas de tiempo real y los sistemas multimedia. Estos sistemas tienen requisitos específicos que difieren de los de los sistemas de propósito general, en los que se centra el resto del texto. Los sistemas de tiempo real pueden necesitar no sólo que los resultados calculados sean "correctos", sino que también se obtengan dentro de un plazo de tiempo especificado. Los sistemas multimedia requieren garantías de calidad de servicio, para garantizar que los datos multimedia se entreguen a los clientes dentro de un periodo de tiempo específico. • Casos de estudio. Los Capítulos 21 a 23 del libro y los Apéndices A y C (disponibles en inglés en el sitio web), integran los conceptos descritos en el libro abordando el estudio de sistemas operativos reales. Entre estos sistemas se incluyen Linux, Windows XP, FreeBSD, Mach y Windows 2000. Hemos elegido Linux y FreeBSD porque UNIX (en tiempos) resultaba lo suficientemente pequeño como para resultar comprensible, sin llegar a ser un sistema operativo "de juguete". La mayor parte de sus algoritmos internos fueron seleccionados por su simplicidad, en lugar de por su velocidad o su sofisticación. Tanto Linux como FreeBSD pueden obtenerse fácilmente y a un bajo coste, por lo que puede que muchos estudiantes tengan acceso a estos sistemas. Hemos seleccionado Windows XP y Windows 2000 porque nos proporcionan una oportunidad de estudiar un sistema operativo moderno con un diseño y una implementación drásticamente diferentes a los de UNIX. El Capítulo 23 describe de forma breve algunos otros sistemas operativos que han tenido históricamente cierta influencia. Entornos de sistemas operativos Este libro utiliza ejemplos de muchos sistemas operativos del mundo real para ilustrar los conceptos fundamentales. Sin embargo, se ha puesto una atención especial en la familia de sistemas operativos de Microsoft (incluyendo Windows NT, Windows 2000 y Windows XP) y varias versiones de UNIX (Solaris, BSD y Mac). También hemos cubierto una parte significativa del sistema operativo Linux, utilizando la versión más reciente del kernel, que era la versión 2.6 en el momento de escribir este libro. El texto también proporciona varios programas de ejemplo escritos en C y en Java. Estos programas pueden ejecutarse en los siguientes entornos de programación: • Sistemas Windows. El entorno de programación principal para los sistemas Windows es la API (application programming interface) Win32, que proporciona un amplio conjunto de funciones para gestionar los procesos, las hebras, la memoria y los dispositivos periféricos. Facilitamos varios programas en C que ilustran el uso de la API Wiri32. Los programas de ejemplo se han probado en sistemas Windows 2000 y Windows XP. • POSIX. POSIX (Portable Operating System Interface, interfaz portable de sistema operativo) representa un conjunto de estándares implementados principalmente en sistemas operativos basados en UNIX. Aunque los sistemas Windows XP y Windows 2000 también pueden ejecutar ciertos programas POSIX, aquí nos hemos ocupado de POSIX principalmente centrándonos en los sistemas UNIX y Linux. Los sistemas compatibles con POSIX deben imple- mentar el estándar fundamental de POSIX (POSIX .1); Linux, Solaris y Mac son ejemplos de sistemas compatibles con POSIX. POSIX también define varias extensiones de los estándares, Prefacio xiii incluyendo extensiones de tiempo real (POSIX l.b) y una extensión para una biblioteca de hebras (POSIX l.c, más conocida como Pthreads). Proporcionamos también varios ejemplos de programación escritos en C con el fin de ilustrar la API básica de POSIX, así como Pthreads y las extensiones para programación de tiempo real. Estos programas de ejemplo se han probado en sistemas Debian Linux 2.4 y 2.6, Mac OS X y Solaris 9 utilizando el compilador gcc 3.3. • Java. Java es un lenguaje de programación ampliamente utilizado con una rica API y soporte integrado de lenguaje para la creación y gestión de hebras. Los programas Java se ejecutan sobre cualquier sistema operativo que permita el uso de una máquina virtual Java (JVM, Java virtual machine). Hemos ilustrado los diversos sistemas operativos y los conceptos de redes con varios programas Java que se han probado utilizando la JVM Java 1.4. Hemos elegido tres entornos de programación porque, en nuestra opinión, son los que mejor representan los dos modelos más populares de sistemas operativos: Windows y UNIX/Linux, junto con el popular entorno Java. La mayor parte de los ejemplos de programación están escritos en C, y esperamos que los lectores se sientan cómodos con este lenguaje; los lectores familiarizados con ambos lenguajes, C y Java, deberían comprender con facilidad la mayor parte de los programas proporcionados en este texto. En algunos casos, como por ejemplo con la creación de hebras, ilustramos un concepto específico utilizando todos los entornos de programación, lo que permite al lector comparar el modo en que las tres bibliotecas diferentes llevan a cabo una misma tarea. En otras situaciones, sólo hemos empleado una de las API para demostrar un concepto. Por ejemplo, hemos ilustrado el tema de la memoria compartida usando sólo la API de POSIX; la programación de sockets en TCP/IP se expone utilizando la API de Java. séptima edición A la hora de escribir la séptima edición de Fundamentos de sistemas operativos nos hemos guiado por los muchos comentarios y sugerencias que hemos recibido de los lectores de las ediciones anteriores; también hemos procurado reflejar los cambios tan rápidos que se están produciendo en los campos de los sistemas operativos y las comunicaciones por red. Hemos reescrito el material de la mayor parte de los capítulos, actualizando el material más antiguo y eliminando aquél que actualmente ya no tiene interés o es irrelevante. Se han hecho importantes revisiones y cambios en la organización de muchos capítulos. Los cambios más destacables son la completa reorganización del material de introducción de los Capítulos 1 y 2 y la adición de dos capítulos nuevos sobre los sistemas de propósito especial (los Prefacio xi sistemas integrados de tiempo real y los sistemas multimedia). Puesto que la protección y la seguridad han cobrado una gran relevancia en los sistemas operativos, hemos decidido incluir el tratamiento de estos temas más al principio del texto. Además, se ha actualizado y ampliado sustancialmente el estudio de los mecanismos de seguridad. A continuación se proporciona un breve esquema de los principales cambios introducidos en los distintos capítulos: --- . • El Capítulo 1, Introducción, se ha revisado por completo. En las versiones anteriores, el capítulo abordaba desde un punto de vista histórico el desarrollo de los sistemas operativos. Ahora, el capítulo proporciona una exhaustiva introducción a los componentes de un sistema operativo, junto con información básica sobre la organización de un sistema informático. • El Capítulo 2, Estructuras de los sistemas operativos, es una versión revisada del antiguo Capítulo 3 en la que se ha incluido información adicional, como una exposición mejorada sobre las llamadas al sistema y la estructura del sistema operativo. También se proporciona información actualizada sobre las máquinas virtuales. • El Capítulo 3, Procesos, es el antiguo Capítulo 4. Incluye nueva información sobre cómo se representan los procesos en Linux e ilustra la creación de procesos usando las API de POSIX y Win32. El material dedicado a la memoria compartida se ha mejorado mediante un programa que ilustra la API de memoria compartida disponible para los sistemas POSIX. • El Capítulo 4, Hebras, se corresponde con el antiguo Capítulo 5. El capítulo presenta y amplía el tema de las bibliotecas de hebras, incluyendo las bibliotecas de hebras de POSIX, la API Win32 y Java. También proporciona información actualizada sobre las hebras en Linux. • El Capítulo 5, Planificación, es el antiguo Capítulo 6. El capítulo ofrece una exposición significativamente actualizada sobre temas de planificación en sistemas multiprocesador, incluyendo los algoritmos de afinidad del procesador y de equilibrado de carga. También se ha incluido una nueva sección sobre la planificación de hebras, incluyendo Pthreads e información actualizada sobre la planificación dirigida por tablas en Solaris. La sección dedicada a la planificación en Linux se ha revisado para incluir el planificador utilizado en el kerncl 2.6. • El Capítulo 6, Sincronización de procesos, se corresponde con el antiguo Capítulo 7. Se han - eliminado las soluciones para dos procesos y ahora sólo se explica la solución de Peterson, ya que los algoritmos para dos procesos no garantizan su funcionamiento en los procesadores modernos. El capítulo también incluye nuevas secciones sobre cuestiones de sincronización en el kernel de Linux y en la API de Pthreads. • El Capítulo 7, Interbloqueos, es el antiguo Capítulo 8. El nuevo material incluye un programa de ejemplo que ilustra los interbloqueos en un programa multihebra Pthread. • El Capítulo 8, Memoria principal, se corresponde con el antiguo Capítulo 9.E1 capítulo ya no se ocupa del tema de las secciones de memoria superpuestas. Además, el material dedicado a la segmentación se ha modificado considerablemente, incluyendo una explicación mejorada sobre la segmentación en los sistemas Pentium y una exposición sobre el diseño en Linux para tales sistemas segmentados. • El Capítulo 9, Memoria virtual, es el antiguo Capítulo 10. El capítulo amplía el material dedicado a la memoria virtual, asi como a los archivos mapeados en memoria, incluyendo un ejemplo de programación que ilustra la memoria compartida (a través de los archivos mapeados en memoria) usando la API Win32. Los detalles sobre el hardware de gestión de memoria se han actualizado. Se ha añadido una nueva sección dedicada a la asignación de memoria dentro del kemel, en la que se explican el algoritmo de descomposición binaria y el asignador de franjas. • El Capítulo 10, Interfaz del sistema de archivos, se corresponde con el antiguo Capítulo 11. Se ha actualizado y se ha incluido un ejemplo sobre las listas ACL de Windows XP. • El Capítulo 11, Implementación de los sistemas de archivos, es el antiguo Capítulo 12. Se ha añadido una descripción completa sobre el sistema de archivos WAFL y se ha incluido el sistema de archivos ZFS de Sun. • El Capítulo 12, Estructura de almacenamiento masivo, se corresponde con el antiguo Capítulo 14. Se ha añadido un tema nuevo, las matrices de almacenamiento modernas, incluyendo la nueva tecnología RAID y características tales como las redes de área de almacenamiento. xii Prefacio • El Capítulo 13, Sistemas de E/S, es el antiguo Capítulo 13 actualizado, en el que se ha incluido material nuevo. • El Capítulo 14, Protección, es el antiguo Capítulo 18, actualizado con información sobre el principio de mínimo privilegio. • El Capítulo 15, Seguridad, se corresponde con el antiguo Capítulo 19. El capítulo ha experimentado una revisión importante, habiéndose actualizado todas las secciones. Se ha incluido un ejemplo completo sobre el ataque por desbordamiento de búfer y se ha ampliado la información sobre herramientas de seguridad, cifrado y hebras. • Los Capítulos 16 a 18 se corresponden con los antiguos Capítulos 15 a 17, y se han actualizado con material nuevo. • El Capítulo 19, Sistemas de tiempo real, es un capítulo nuevo centrado en los sistemas informáticos integrados de tiempo real, sistemas que tienen requisitos diferentes a los de los sistemas tradicionales. El capítulo proporciona una introducción a los sistemas informáticos de tiempo real y describe cómo deben construirse estos sistemas operativos para cumplir los plazos de temporización estrictos de estos sistemas. • El Capítulo 20, Sistemas multimedia, es un capítulo nuevo que detalla los desarrollos en el área, relativamente nueva, de los sistemas multimedia. Los datos multimedia se diferencian de los datos convencionales en que los primeros, como por ejemplo imágenes de vídeo, deben suministrarse de acuerdo con ciertas restricciones de tiempo. El capítulo explora cómo afectan estos requisitos al diseño de los sistemas operativos. • El Capítulo 21, El sistema Linux se corresponde con el antiguo Capítulo 20. Se ha actualizado para reflejar los cambios en el kernel 2.6, el kernel más reciente en el momento de escribir este libro. • El Capítulo 22, Windows XP, se ha actualizado también en esta versión. • El Capítulo 23, Sistemas operativos influyentes, se ha actualizado. El antiguo Capítulo 21 (Windows 2000) se ha transformado en el Apéndice C. Al igual que en las versiones anteriores, los apéndices están disponibles en línea, aunque solamente en su versión original en inglés. Proyectos y ejercicios de programación Para reforzar los conceptos presentados en el texto, hemos añadido diversos proyectos y ejercicios de programación que utilizan las API de POSIX y Win32, así como Java. Hemos añadido 15 nuevos ejercicios de programación que se centran en los procesos, las hebras, la memoria compartida, la sincronización de procesos y las comunicaciones por red. Además, hemos añadido varios proyectos de programación que son más complicados que los ejercicios de programación estándar. Estos proyectos incluyen la adición de una llamada al sistema al kernel de Linux, la creación de una shell de UNIX utilizando la llamada al sistema f ork ( ) , una aplicación multihebra de tratamiento de matrices y el problema del productor-consumidor usando memoria compartida. Suplementos y página web La página web (en inglés) asociada al libro contiene material organizado como un conjunto de diapositivas para acompañar al libo, planes de estudios para el curso modelo, todo el código fuente en C y Java y una relación actualizada de las erratas. La página web también contiene los apéndices de los tres casos de estudio del libro y un apéndice dedicado a la comunicación distribuida. La URL es: http://www.os-book.com Lista de correo Hemos cambiado el sistema de comunicación entre los usuarios de Fundamentos de sistemas operativos. Si desea utilizar esta función, visite la siguiente URL y siga las instrucciones para suscribirse: http://mailman.cs.yale.edu/mailman/listinfo/os-book-list Prefacio xiii El sistema de lista de correo proporciona muchas ventajas, como un archivo de mensajes y varias opciones de suscripción, incluyendo suscripciones con envío de resúmenes o con acceso Web. Para mandar mensajes a la lista, envíe un mensaje de correo electrónico a: [email protected] Dependiendo del mensaje, le responderemos personalmente o enviaremos el mensaje a toda la lista de correo. La lista está moderada, por lo que no recibirá correo inapropiado. Los estudiantes que utilicen este libro como texto en sus clases no deben utilizar la lista para preguntar las respuestas a los ejercicios, ya que no se les facilitarán. Sugerencias Hemos intentado eliminar todos los errores en esta nueva edición pero, como ocurre con los sistemas operativos, es posible que queden algunas erratas. Agradeceríamos que nos comunicaran cualquier error u omisión en el texto que puedan identificar. Si desea sugerir mejoras o contribuir con ejercicios, también se lo agradecemos de antemano. Puede enviar los mensajes a [email protected]. Agradecimientos Este libro está basado en las ediciones anteriores y James Peterson fue coautor de la primera de ellas. Otras personas que ayudaron en las ediciones anteriores son Hamid Arabnia, Rida Bazzi, Randy Bentson, David Black, Joseph Boykin, Jeff Brumfield, Gael Buckley, Roy Campbell, P. C. Capón, John Carpenter, Gil Carrick, Thomas Casavant, Ajoy Kumar Datta, Joe Deck, Sudarshan K. Dhall, Thomas Doeppner, Caleb Drake, M. Racsit Eskicioglu, Hans Flack, Robert Fowler, G. Scott Graham, Richard Guy, Max Hailperin, Rebecca Hartman, Wayne Hathaway, Christopher Haynes, Bruce Hillyer, Mark Holliday, Ahmed Kamel, Richard Kieburtz, Carol Kroll, Morty Kwestel, Thomas LeBlanc, John Leggett, Jerrold Leichter, Ted Leung, Gary Lippman, Carolyn Miller, Michael Molloy, Yoichi Muraoka, Jim M. Ng, Banu Ózden, Ed Posnak, Boris Putañee, Charles Qualline, John Quarterman, Mike Reiter, Gustavo Rodriguez-Rivera, Carolyn J. C. Schauble, Thomas P. Skinner, Yannis Smaragdakis, Jesse St. Laurent, John Stankovic, Adam Stauffer, Steven Stepanek, Hal Stern, Louis Stevens, Pete Thomas, David Umbaugh, Steve Vinoski, Tommy Wagner, Larry L. Wear, John Werth, James M. Westall, J. S. Weston y Yang Xiang Partes del Capítulo 12 están basadas en un artículo de Hillyer y Silberschatz [1996], Partes del Capítulo 17 están basadas en un artículo de Levy y Silberschatz [1990], El Capítulo 21 está basado en un manuscrito no publicado de Stephen Tweedie. El Capítulo 22 esta Dasaao en un marius~ crito no publicado de Dave Probert, Cliff Martin y Avi Silberschatz. El Apéndice C está basado en un manuscrito no publicado de Cliff Martin. Cliff Martin también ha ayudado a actualizar el apéndice sobre UNIX para cubrir FreeBSD. Mike Shapiro, Bryan Cantrill y Jim Mauro nos han ayudado respondiendo a diversas cuestiones relativas a Solaris. Josh Dees y Rob Reynolds han contribuido al tratamiento de Microsoft .NET. El proyecto de diseño y mejora de la interfaz shell de UNIX ha sido aportado por John Trono de St. Michael's College, Winooski, Vermont. Esta edición contiene muchos ejercicios nuevos, con sus correspondientes soluciones, los cuales han sido proporcionadas por Arvind Krishnamurthy. Queremos dar las gracias a las siguientes personas que revisaron esta versión del libro: Bart Childs, Don Heller, Dean Hougen Michael Huangs, Morty Kewstel, Eurípides Montagne y John Sterling. Nuestros editores, Bill Zobrist y Paul Crockett, han sido una experta guía a medida que íbamos preparando esta edición. Simón Durkin, ayudante de nuestros editores, ha gestionado muy amablemente muchos de los detalles de este proyecto. El editor de producción sénior ha sido Ken Santor. Susan Cyr ha realizado las ilustraciones de la portada y Madelyn Lesure es la diseñadora de la misma. Beverly Peavler ha copiado y maquetado el manuscrito. Katrina Avery es la reviso- ra de estilo externa que ha realizado la corrección de estilo del texto y la realización del índice ha corrido a cargo de la colabora externa Rosemary Simpson. Marilyn Turnamian ha ayudado a generar las figuras y las diapositivas de presentación. Por último, nos gustaría añadir algunas notas personales. Avi está comenzando un nuevo capítulo en su vida, volviendo al mundo universitario e iniciando una relación con Valerie. Esta combinación le ha proporcionado la tranquilidad de espíritu necesaria para centrarse en la escritura de este libro. Pete desea dar las gracias a su familia, a xiv Prefacio sus amigos y sus compañeros de trabajo por su apoyo y comprensión durante el desarrollo del proyecto. Greg quiere agradecer a su familia su continuo interés y apoyo. Sin embargo, desea dar las gracias de modo muy especial a su amigo Peter Ormsby que, no importa lo ocupado que parezca estar, siempre pregunta en primer lugar "¿Qué tal va la escritura del libro?". Abraham Silberschatz, New Haven, CT, 2004 Peter Baer Galvin, Burlington, MA, 2004 Greg Gagne, Salt Lake City, UT, 2004 Contenido PARTE UNO ■ INTRODUCCIÓN Capítulo 1 Introducción í.i ¿Qué hace un sistema operativo? 3 1.9 Protección y seguridad 24 1.2 1.3 1.4 1.5 1.6 1.7 1.8 Organización de una computadora 6 Arquitectura de un sistema informático 11 Estructura de un sistema operativo 14 Operaciones del sistema operativo 16 Gestión de procesos 19 Gestión de memoria 19 Gestión de almacenamiento 20 1.10 1.11 1.12 1.13 Sistemas distribuidos 25 Sistemas de propósito general 26 Entornos informáticos 28 Resumen 31 Ejercicios 32 Notas bibliográficas 34 Capítulo 2 Estructuras de sistemas 2.1 Servicios del sistema operativo 35 2.2 2.3 2.4 2.5 2.6 Interfaz de usuario del sistema operativo Llamadas al sistema 39 Tipos de llamadas al sistema 42 Programas del sistema 49 Diseño e implementación del sistema operativo 50 operativos 37 2.7 Estructura del sistema operativo 52 2.8 2.9 2.10 2.11 Máquinas virtuales 58 Generación de sistemas operativos 63 Arranque del sistema 64 Resumen 65 Ejercicios 65 Notas bibliográficas 70 3.6 Comunicación en los sistemas clienteservidor 96 Resumen 103 Ejercicios 104 Notas bibliográficas 111 PARTE DOS ■ GESTIÓN DE PROCESOS Capítulo 3 Procesos 3.1 3.2 3.3 3.4 3.5 Concepto de proceso 73 Planificación de procesos 77 Operaciones sobre los procesos 81 Comunicación interprocesos 86 Ejemplos de sistemas ipc 92 3.7 Capítulo 4 Hebras 4.1 4.2 4.3 4.4 Introducción 113 Modelos multihebra 115 Bibliotecas de hebras 11/ Consideraciones sobre las hebras ' 4.5 4.6 Ejemplos de sistemas operativos 128 Resumen 130 Ejercicios 130 Notas bibliográficas 135 16 Contenido Capítulo 5 Planificación de la CPU 5.1 5.2 5.3 5.4 Conceptos básicos 137 Criterios cié planificación 140 Algoritmos de planificación 142 Planificación de-sistemas'multiproeesador 151 5.5 5.6 5.7 5.8 Planificación de hebras 153 Ejemplos de sistemas operativos 156 Evaluación de algoritmos 161 Resumen 165 Ejercicios 166 Notas bibliográficas 169 6.7 6.8 6.9 6.10 Monitores 186 Ejemplos de sincronización 194 Transacciones atómicas 197 Resumen 204 Ejercicios 205 Notas bibliográficas 214 Capítulo 6 Sincronización de procesos 6.1 6.2 6.3 6.4 6.5 6.6 Fundamentos 171 El problema de la sección crítica 173 Solución de Peterson 174 Hardware de sincronización 175 Semáforos 17S Problemas clásicos de sincronización Capítulo 7 Interbloqueos 7.1 7.2 7.3 7.4 Modelo de sistema 217 Caracterización de los interbloqueos 219 Métodos para tratar los interbloqueos 223 Prevención de interbloqueos 224 182 7.5 7.6 7.7 7.8 Evasión de interbloqueos 226 Detección de interbloqueos 232 Recuperación de un interbloqueo 235 Resumen 236 Ejercicios 237 Notas bibliográficas 239 8.6 8.7 8.8 Segmentación 269 Ejemplo: Intel Pentium 271 Resumen 275 Ejercicios 276 Notas bibliográficas 278 9.8 9.9 9.10 9.11 Asignación de la memoria del kemel 314 Otras consideraciones 317 Ejemplos de sistemas operativos 323 Resumen 325 Ejercicios 326 Notas bibliográficas 330 PARTE TRES ■ GESTION DE MEMORIA Capítulo 8 Memoria principal Fundamentos 243 Intercambio 249 Asignación de memoria contigua 252 Paginación 255 Estructura de la tabla de paginas 264 s.i S 2 j 4 5 Capítulo 9 Memoria virtual Fundamentos 279 Paginación bajo demanda 282 Copia durante la escritura 289 Sustitución de páginas 2°Ü Asignación de marcos 302 Sobrepagir.ación 305 Archivos rr.apeados en memoria 9.1 9.2 9.3 9.4 9.5 9.6 9.7 309 PARTE CUATRO ■ GESTION DE ALMACENAMIENTO Capítulo 10 Interfaz del sistema de archivos 10.1 10.2 10.3 10.4 10.5 10.6 Concepto ¿e archivo 33? Métodos ce acceso 342 Estructura Je directorios 545 Montaje de sistemas de archivos 354 Compartición de archivos 555 Protección 361 10.7 Resumen 365 Ejercicios 366 Notas bibliográficas 367 Contenido 17 Capítulo 11 Implementación de sister de archivos 11.1 11.2 11.3 11.4 11.5 11.6 11.7 11.8 Estructura de un sistema de archivos 369 Implementación de sistemas de archivos 371 Implementación de directorios 377 Métodos de asignación 378 Gestión del espacio libre 386 Eficiencia y prestaciones 388 Recuperación 392 11.9 11.10 11.11 Sistemas de archivos con estructura de registro 393 NFS 395 Ejemplo: el sistema de archivos WAFL 400 Resumen 402 Ejercicios 403 Notas bibliográficas 405 Capítulo 12 Estructura de almacenamiento masivo 12.1 12.2 12.3 12.4 12.5 12.6 12.7 Panorámica de la estructura de almacena-12.8 miento masivo 407 Estructura de un disco 409 12.9 Conexión de un disco 410 Planificación de disco 412 12.10 Gestión del disco 418 Gestión de espacio de intercambio 421 Estructuras RAID 423 Implementación de un almacenamiento estable 432 Estructura de almacenamiento terciario 433 Resumen 442 Ejercicios 444 Notas bibliográficas 447 Capítulo 13 Sistemas de E/S 13.1 13.2 13.3 13.4 13.5 Introducción 449 Hardware de E/S 450 Interfaz de E/S de las aplicaciones 458 Subsistema de E/S del kernel 464 Transformación de las solicitudes de E/S en operaciones hardware 471 13.6 13.7 13.8 Streams 473 Rendimiento 475 Resumen 478 Ejercicios 478 Notas bibliográficas 479 PARTE CINCO ■ PROTECCION Y SEGURIDAD Capítulo 14 Protección 14.1 14.2 14.3 14.4 14.5 Objetivos de la protección 483 Principios de la protección 484 Dominio de protección 485 Matriz de acceso 489 Implementación de la matriz de acceso 493 Capítulo 15 Seguridad 15.1 15.2 15.3 15.4 15.5 15.6 El problema de la seguridad 509 Amenazas relacionadas con los programas 513 Amenazas del sistema y de la red 520 La criptografía como herramienta de seguridad 525 Autenticación de usuario 535 Implementación de defensas de 14.6 14.7 14.8 14.9 14.10 15.7 15.8 15.9 15.10 Control de acceso 495 Revocación de derechos de acceso 496 Sistemas basados en capacidades 497 Protección basada en el lenguaje 500 Resumen 505 Ejercicios 505 Notas bibliográficas 506 seguridad 539 Cortafuegos para proteger los sistemas y redes 546 Clasificaciones de seguridad informática 547 Un ejemplo: Windows XP >49 Resumen 550 Ejercicios 551 Notas bibliográficas 552 18 Contenido 16.1 Motivación 557 .16.2 Tipos de sistemas 16.5 PARTE SEIS ■ SISTEMAS DISTRIBUIDOS Capítulo 16 Estructuras de los sistemas distribuidos distribuidos 559 16.3 Estructura de una red 563 16.4 Topología de red 565 Estructura de comunicaciones 567 16.6 Protocolos de comunicaciones 572 16.7 Robustez 575 16.8 Cuestiones de diseño 577 16.9 Un ejemplo: conexión en red 579 16.10 Resumen 581 Ejercicios 581 Notas bibliográficas 583 Capítulo 17 Sistemas de archivos distribuidos 17.1 17.2 17.3 17.4 17.5 Conceptos esenciales 585 Nombrado y transparencia 586 Acceso remoto a archivos 590 Servicios con y sin memoris del estado 594 Replicación de archivos 597 17.6 17.7 Un ejemplo: AFS 598 Resumen 602 Ejercicios 603 Notas bibliográficas 604 18.6 18.7 18.8 Algoritmos de elección 623 Procedimientos de acuerdo 625 Resumen 627 Ejercicios 627 Notas bibliográficas 629 Capítulo 18 Coordinación distribuida 18.1 18.2 18.3 18.4 18.5 Ordenación de sucesos 605 Exclusión mutua 607 Atomicidad 610 Control de concurrencia 612 Gestión de interbloqueos 616 PARTE SIETE ■ SISTEMAS DE PROPÓSITO ESPECIAL Capítulo 19 Sistemas de tiempo real 19.1 19.2 19.3 19.4 Introducción 633 Características del sistema 634 Características de un kernel de tiempo real 636 Implementación de sistemas operativos de 19.5 19.6 19.7 tiempo real 637 Planificación de la CPU en tiempo real 641 VxWorks 5.x 645 Resumen 648 Ejercicios 649 Notas bibliográficas 650 Capítulo 20 Sistemas multimedia 20.1 20.2 20.3 20.4 20.5 ¿Qué es la multimedia? 651 Compresión 654 Requisitos de los kernels multimedia 655 Planificación de la CPU 658 Planificación de disco 658 PARTE OCHO ■ CASOS DE ESTUDIO Capítulo 21 El sistema Linux 21.1 21.2 21.3 21.4 21.5 21.6 21.7 Historia de Linux 671 Principios de diseño 675 Módulos del kernel 678 Gestión de procesos 681 Planificación 684 Gestión de memoria 6SS Sistemas de archivos 696 20.6 20.7 20.8 Gestión de red 660 Un ejemplo: CineBlitz 663 Resumen 665 Ejercicios 666 Notas bibliográficas 667 Contenido 21.8 Entrada y salida 702 21.9 Comunicación interprocesos 704 21.10 Estructura de red 705 21.11 Seguridad 707 Capítulo 22 Windows XP 22.1 22.2 22.3 22.4 Historia 713 Principios de diseño 714 Componentes del sistema 717 Subsistemas de entorno 739 21.12 Resumen 709 Ejercicios 710 Notas bibliográficas 711 22.5 22.6 22.7 22.8 Sistema de archivos 742 Conexión de red 749 Interfaz de programación 756 Resumen 763 Ejercicios 763 Notas bibliográficas 764 Capítulo 23 Sistemas operativos influyentes 23.1 23.2 23.3 23.4 23.5 23.6 Sistemas pioneros Atlas 771 XDS-940 771 THE 772 RC 4000 773 CTSS 773 Bibliografía 779 Créditos 803 índice 805 765 23.7 MULTICS .774 23.8 IBM OS/360 774 23.9 Mach 776 23.10 Otros sistemas 777 Ejercicios 777 Parte Uno Introducción Un sistema operativo actúa como un intermediario entre el usuario de una computadora y el hardware de la misma. El propósito de un sistema operativo es proporcionar un entorno en el que el usuario pueda ejecutar programas de una manera práctica y eficiente. Un sistema operativo es software que gestiona el hardware de la computadora. El hardware debe proporcionar los mecanismos apropiados para asegurar el correcto funcionamiento del sistema informático e impedir que los programas de usuario interfieran con el apropiado funcionamiento del sistema. Internamente, los sistemas operativos varían enormemente en lo que se refiere a su configuración, dado que están organizados según muchas líneas diferentes. El diseño de un nuevo sistema operativo es una tarea de gran envergadura. Es fundamental que los objetivos del sistema estén bien definidos antes de comenzar el diseño. Estos objetivos constituyen la base para elegir entre los distintos algoritmos y estrategias. Dado que un sistema operativo es un software grande y complejo, debe crearse pieza por pieza. Cada una de estas piezas debe ser una parte perfectamente perfilada del sistema, estando sus entradas, salidas y funciones cuidadosamente definidas. / CAWTULO Introducción Un sistema operativo es un programa que administra el hardware de una computadora. También proporciona las bases para los programas de aplicación y actúa como un intermediario entre el usuario y el hardware de la computadora. Un aspecto sorprendente de los sistemas operativos es la gran variedad de formas en que llevan a cabo estas tareas. Los sistemas operativos para main- frame están diseñados principalmente para optimizar el uso del hardware. Los sistemas operativos de las computadoras personales (PC) soportan desde complejos juegos hasta aplicaciones de negocios. Los sistemas operativos para las computadoras de mano están diseñados para proporcionar un entorno en el que el usuario pueda interactuar fácilmente con la computadora para ejecutar programas. Por tanto, algunos sistemas operativos se diseñan para ser prácticos, otros para ser eficientes y otros para ser ambas cosas. Antes de poder explorar los detalles de funcionamiento de una computadora, necesitamos saber algo acerca de la estructura del sistema. Comenzaremos la exposición con las funciones básicas del arranque, E/ S y almacenamiento. También vamos a describir la arquitectura básica de una computadora que hace posible escribir un sistema operativo funcional. Dado que un sistema operativo es un software grande y complejo, debe crearse pieza por pieza. Cada una de estas piezas deberá ser una parte bien diseñada del sistema, con entradas, salida y funciones cuidadosamente definidas. En este capítulo proporcionamos una introducción general a los principales componentes de un sistema operativo. OBJETIVOS DEL CAPÍTULO • Proporcionar una visión general de los principales componentes de los sistemas operativos. • Proporcionar una panorámica sobre la organización básica de un sistema informático. 1.1 ¿Qué hace un sistema operativo? Comenzamos nuestra exposición fijándonos en el papel del sistema operativo en un sistema informático global. Un sistema informático puede dividirse a grandes rasgos en cuatro componentes: el hardware, el sistema operativo, los programas de aplicación y los usuarios (Figura 1.1). El hardware, la unidad central de procesamiento, UCP o CPU (central processing unit), la memoria y los dispositivos de ^S (entrada/salida), proporciona los recursos básicos de cómputo al sistema. Los programas de aplicación, como son los procesadores de texto, las hojas de cálculo, los compiladores y los exploradores web, definen las formas en que estos recursos se emplean para resolver los problemas informáticos de los usuarios. El sistema operativo controla y coordina ei uso del hardware entre los diversos programas de aplicación por parte de los distintos usuarios. 24 Capítulo 1 Introducción Figura 1.1 Esquema de los componentes de un sistema informático. También podemos ver un sistema informático como hardware, software y datos. El sistema operativo proporciona los medios para hacer un uso adecuado de estos recursos durante el funcionamiento del sistema informático. Un sistema operativo es similar a un gobierno. Como un gobierno, no realiza ninguna función útil por sí mismo: simplemente proporciona un entorno en el que otros programas pueden llevar a cabo un trabajo útil. Para comprender mejor el papel de un sistema operativo, a continuación vamos a abordar los sistemas operativos desde dos puntos de vista: el del usuario y el del sistema. 1.1.1 Punto de vista del usuario La visión del usuario de la computadora varía de acuerdo con la interfaz que utilice. La mayoría de los usuarios que se sientan frente a un PC disponen de un monitor, un teclado,