PDF de programación - Núcleo Educativo Basado en Linux

CENTRO DE INVESTIGACI ÓN Y DE ESTUDIOS AVANZADOS

DEL INSTITUTO POLITÉCNICO NACIONAL
DEPARTAMENTO DE INGENIERÍA ELÉCTRICA

SECCI ÓN DE COMPUTACI ÓN

Núcleo Educativo Basado en Linux

Tesis que presenta

Domínguez Hernández Rogelio

Para obtener el grado de

Maestro en Ciencias

En la especialidad de

Ingeniería Eléctrica

Opción Computación

Director de la Tesis: Dr. Jorge Buenabad Chávez

México, D.F., Enero de 2006

CINVESTAV-IPN

Esta tesis fue realizada con ayuda de KOMA - Script, LATEX y GNU/Linux

Resumen

En la actualidad existen varios sistemas operativos que pueden ser usados
en cursos prácticos de Sistemas Operativos. Sin embargo, creemos que Linux
es el sistema operativo ideal para este propósito debido a su robustez, con-
fiabilidad, estabilidad, disponibilidad del código fuente y su amplio uso en
los ámbitos académico e industrial. En particular, su amplio uso en distintos
ámbitos, implica que nuevas ideas implementadas en Linux serán evaluadas
y, posiblemente, usadas y mejoradas por mucha gente. Desafortunadamente,
su soporte para distintas arquitecturas de procesador y una gran cantidad
de dispositivos han hecho que Linux creciera tanto en tamaño como en com-
plejidad. Por lo tanto, un curso de Sistemas Operativos basado en Linux
podría ser muy demandante para los estudiantes.

En esta tesis presentamos eLinux, un núcleo basado en Linux que ha
sido reducido tanto en código como en complejidad de tal manera que es
conveniente de usar en un curso completo y práctico de Sistemas Operativos.
Dicho curso permitiría a los estudiantes determinar si el área de Sistemas
Operativos es uno de sus intereses de investigación. Para los estudiantes que
así lo decidieran, eLinux proveería los conocimientos y habilidades básicas
para que inicien sus desarrollos.

Abstract

Nowadays there are several operating systems that can be used to teach a
practical course on Operating Systems. However, we think Linux is the most
suitable for this purpose because of its robustness, wide-spread use in dif-
ferent contexts, and its support for various and varied hardware platforms.
Its wide-spread use, particularly, means that new ideas developed in Linux
will be evaluated and possibly used and enhanced by many people. Unfor-
tunately, its support to many hardware platforms has meant a considerable
increase in size and complexity. Hence a course on Operating Systems based
on Linux is now a rather demanding task on students.

This thesis presents a Linux kernel reduced both in code and complexity
that is suitable to teach a practical and comprehensive course on Operating
Systems. Such course should allow students to realise whether operating
systems is one of their research interests. And for those that is, it would
have provided the base knowledge and skills to move further.

iv

Agradecimientos

Quiero agradecer a mis padres, Clara y Raúl, por todo el apoyo que me han brindado
durante toda mi vida. Quiero agradecerles no sólo por ser mis mejores amigos y mis
mejores maestros sino, además, por concederme el honor de ser su hijo.

A mis hermanos Raúl, Roberto y Ricardo por todo lo que me han enseñado y por
todos los invaluables momentos que hemos compartido juntos. También a mis cuñadas
Miriam Iliana, Miriam y Yaneth por hacer de mis hermanos mejores personas.

A Karen, quien más que mi sobrina la considero como mi hermanita, por ser la alegría

de toda la familia.

Al Dr. Jorge Buenabad por su amistad y asesoría en el desarrollo de la presente tesis.

A todos mis amigos que, con su ejemplo, su apoyo, sus consejos y su compañía,
siempre son un aliciente para seguir adelante. Evitaré hacer una lista incómoda, ustedes
saben quiénes son.

A todos los profesores que he tenido, pues considero que el hecho de compartir cono-
cimientos es uno de los más grandes actos de humildad que un ser humano puede
realizar.

A todos ustedes les prometo seguir siempre adelante.

Al CONACyT por la beca otorgada para realizar mis estudios de maestría.

Al CINVESTAV por la beca otorgada para finalizar la presente tesis.

vi

Índice general

1. Introducción

1.1. Terminología
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2. Organización General de Linux . . . . . . . . . . . . . . . . . . . . . .
1.3. Panorama General de la Simplificación de Linux . . . . . . . . . . . . .

2. Administrador de Procesos

2.1. Administración de Procesos en Linux . . . . . . . . . . . . . . . . . . .
2.1.1. Diagrama de Estados de Procesos . . . . . . . . . . . . . . . . .
2.1.2. El Algoritmo de Planificación . . . . . . . . . . . . . . . . . . .
2.1.3. El Descriptor de Proceso . . . . . . . . . . . . . . . . . . . . . .
2.1.4.
Inicialización . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Simplificación de la Administración de Procesos en eLinux . . . . . . .
2.3. Tareas y Proyectos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3. Administrador de Memoria

3.1. Organización de la Administración de Memoria en Linux . . . . . . . .
3.1.1. Organización de la Memoria Física . . . . . . . . . . . . . . . .
3.1.2. Tablas de Páginas . . . . . . . . . . . . . . . . . . . . . . . . . .
Inicialización . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.3.
3.1.4. Boot Memory Allocator
. . . . . . . . . . . . . . . . . . . . . .
3.1.5. Tablas Maestras de Páginas del Núcleo . . . . . . . . . . . . . .
3.1.6. Binary Buddy Allocator
. . . . . . . . . . . . . . . . . . . . . .
3.1.7. Slab Allocator . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1.8. Espacio de Direcciones de Proceso(Process Address Space) . . .
3.1.9. Administración del Espacio de Direcciones de Proceso en Linux
3.2. Simplificación de la Administración de Memoria en eLinux . . . . . . .
3.3. Tareas y Proyectos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4. Administración de Entrada/Salida

4.1. Administración de la Entrada/Salida en Linux . . . . . . . . . . . . . .
4.1.1. Representación de dispositivos . . . . . . . . . . . . . . . . . . .

1
5
5
13

17
17
17
19
24
28
31
32

35
36
36
36
37
37
40
41
43
46
46
49
51

53
53
53

vii

Índice general

4.1.2. Tipos de dispositivos . . . . . . . . . . . . . . . . . . . . . . . .
4.1.3. Capa de Entrada/Salida para Dispositivos de Bloque . . . . . .
Inicialización . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.4.
4.2. Simplificación de la Administración de Entrada/Salida de Linux . . . .
4.3. Tareas y Proyectos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5. Administración de Archivos

5.2.1.

5.1. Sistemas de Archivos en Linux . . . . . . . . . . . . . . . . . . . . . . .
5.1.1. Los sistemas de archivos tipo Unix . . . . . . . . . . . . . . . .
5.1.2. Sistemas de Archivos Soportados por Linux . . . . . . . . . . .
5.2. La capa VFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Inicialización . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3. Simplificación de la Administración de Archivos de Linux . . . . . . . .
5.4. El Sistema de Archivos Xinu sobre eLinux . . . . . . . . . . . . . . . .
5.4.1. Estructura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.2.
Implementación . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.3. Registro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.4.4. Manejo de archivos (inodes) . . . . . . . . . . . . . . . . . . . .
5.4.5. Lectura y Escritura de Directorios . . . . . . . . . . . . . . . . .
5.4.6. Lectura y Escritura de Archivos . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5.5. Tareas y Proyectos

54
55
58
59
62

67
67
68
69
72
74
76
78
78
81
81
86
91
94
99

6. Conclusiones

101
6.1. Verificación del Núcleo . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

A. Entorno de Desarrollo del Núcleo de eLinux

A.1. Entorno de Desarrollo Normal

107
. . . . . . . . . . . . . . . . . . . . . . . 107
A.1.1. Compilando el código de eLinux . . . . . . . . . . . . . . . . . . 107
A.1.2. Configurando el Cargador de Arranque . . . . . . . . . . . . . . 110
A.1.3. Desventajas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
A.2. Entorno de Desarrollo con QEMU . . . . . . . . . . . . . . . . . . . . . 112
A.2.1. Instalación y Configuración de QEMU . . . . . . . . . . . . . . 112
A.2.2. Instalación de Linux dentro de QEMU . . . . . . . . . . . . . . 113
A.2.3. Ejecutando QEMU . . . . . . . . . . . . . . . . . . . . . . . . . 114
A.2.4. Ejecutando eLinux en QEMU . . . . . . . . . . . . . . . . . . . 114
A.2.5. Copiando archivos al disco duro virtual de QEMU . . . . . . . . 115

viii

Índice general

B. Estructuras del Administrador de Procesos

117
B.1. prio array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
B.2. runqueue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
B.3. task struct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

C. Estructuras del Administrador de Memoria

125
C.1. vm area struct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
C.2. mm struct . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

D. Estructuras de la Capa de Entrada/Salida para Dispositivos de Bloque

129
D.1. buffer head . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
D.2. Estructura bio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

E. Estructuras de la capa VFS

133
E.1. file system type . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
E.2. super block . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
E.3. super operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
E.4. inode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
E.5. inode operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
E.6. dentry .