PDF de programación - Diseño e Implementación de múltiples planificadores de disco para el sistema operativo Linux

Diseño e Implementación de múltiples

planificadores de disco para el sistema operativo

Linux

J. Fernández, F. García, J. Carretero

Depto. de Arquitectura y Tecnología de Sistemas Informáticos

Universidad Politécnica de Madrid,

28660 Madrid, España

e-mail: {jfernand,fgarcia,jcarrete}@laurel.datsi.fi.upm.es

Octubre 1999

Resumen

El uso creciente de sistemas operativos de propósito general, como Linux, para
dar soporte a aplicaciones de propósito específico, como las de multimedia, vídeo
bajo demanda o tiempo real no crítico, hace necesario introducir en dichos sistemas
operativos mecanismos de control de la entrada/salida que permitan asignar los
recursos de forma adecuada. Entre estos mecanismos, el sistema de ficheros y los
planificadores de disco son elementos clave a modificar.

En este articulo se presenta el diseño e implementación de mecanismos para
cambiar de forma fácil y rápida el planificador de disco del S.O. Linux. Dichos
mecanismos se acompañan de una propuesta de modificación del interfaz de E/S
para permitir peticiones al disco con parámetros adicionales que puedan usar los
nuevos planificadores de disco. Para demostrar la viabilidad de las soluciones
propuestas, se presenta también una evaluación comparativa de algunas políticas
de planificación implementadas a modo de ejemplo.
Palabras Clave: E/S, planificación, disco, Linux.

1 Introducción

En los últimos años se se ha despertado un gran interés en el campo de la arquitec-
tura de los computadores por los métodos de planificación [Ghandeharizadeh95] de
los dispositivos de entrada/salida. Las técnicas genéricas de planificación usadas y
desarrolladas dentro de los sistemas de tiempo real [Lehoczky89][Liu73] funcionan
adjudicando con antelación las prioridades de los distintos procesos. Sin embargo en
el caso de la planificación en los dispositivos de entrada/salida esta prioridad no puede
ser conocida con antelación, así la prioridad de cada flujo de datos debe ser calculada
de forma dinámica. Los métodos de planificación más usados incluyen las técnicas
FIFO, SCAN y CSCAN. Ninguno de ellos permite especificar parámetros adicionales
procedentes de los programas de usuario, puesto que sólo dependen de la geometría
del disco. Ejemplos de técnicas de planificación basadas en parámetros adicionales
procedentes de los programas de usuario pueden ser la planificación basada en priori-
dades, en plazos de respuesta o en políticas mixtas de planificación [Carretero99-2]. El

paso de parámetros adicionales desde los programas de usuario hasta el planificador de
disco implica, en muchos casos, modificar el interfaz de entradas/salida del sistema.

En este articulo se describe una implementación de Linux [Beck98, Rusling98]
que permite al usuario cambiar de forma dinámica el planificador de disco del sistema
y que, además, expande el interfaz de entrada/salida para incluir parámetros adicionales
en las peticiones al disco de los programas de usuario. En la sección 2 se describe el
diseño del sistema. La sección 3 muestra someramente la implementación realizada.
La sección 4 muestra una evaluación comparativa de algunos algoritmos de planifi-
cación de disco. Por ultimo, en la sección 5 se exponen las conclusiones extraídas y
los futuros trabajos a realizar.

2 Diseño del sistema

Para poder describir adecuadamente los puntos de que consta el diseño del sistema es
importante empezar con una breve introducción al funcionamiento del subsistema de
E/S en Linux [Beck98], para después comentar los cambios a realizar para la consecu-
ción del sistema final.

A modo de reseña, indicar que Linux es una sistema operativo similar a UNIX
desarrollado por miles de voluntarios en todo el mundo conectados vía Internet. La
primera versión de este sistema operativo fue publicada en la red por Linus Torvald
en 1991. Actualmente hay millones de computadores con Linux instalado, con una
previsión de crecimiento anual del 25% durante los próximos años. Su principal ven-
taja es que su código fuente es de libre distribución, tanto para estudiarlo, como para
modificarlo o distribuirlo sin limitaciones [Card97].

Sistema de E/S de Linux

Interfaz de llamadas al sistema

Sistema de ficheros virtual

Sistema de ficheros

Controlador del disp.

[alto nivel]

Cache de
páginas de
memoria

Cache de bloques

Gestor de peticiones del disco

Planificador de disco

Controlador del dispositivo

[bajo nivel]

Figura 1: Arquitectura del subsistema de E/S en Linux

La Figura 1 expone el esquema básico del subsistema de E/S de Linux. En ella
se pueden distinguir las distintas partes que lo componen. Entre estas partes hay que

destacar el gestor de peticiones al disco y el planificador del disco. El gestor de peti-
ciones al disco se encarga de recoger las peticiones de lectura o escritura en forma de
bloques de cache listos para transferir datos desde o hacia el disco. Además se encarga
de juntar las transferencias del mismo tipo, cuyos bloques sean contiguos, para que se
realicen como una sola petición. Cuando tiene una nueva petición, llama al planificador
de disco para que éste la introduzca de forma ordenada en la cola de peticiones. En Lin-
ux existe una cola de peticiones por cada tipo de dispositivo. El planificador instalado
en Linux por defecto implementa una política de planificación de tipo CSCAN.

Para poder diseñar un sistema que cumpla los objetivos previamente marcados hay

que resolver dos problemas fundamentales:

Descubrir un método que permita cambiar de planificador de disco de la forma

menos traumática posible.

Modificar la interfaz de E/S de Linux para permitir que las peticiones al disco

incluyan parámetros adicionales a los habituales.

Para resolver el problema planteado en el primer punto existen dos posibles solu-

ciones.

Incorporar el nuevo planificador dentro del código fuente que compone el núcleo
principal de Linux.
Esta solución es la más sencilla de implementar. Su principal desventaja, sin em-
bargo, es la dificultad que impone a la hora de incorporar nuevos planificadores
de disco al sistema. Para realizar nuevas incorporaciones es necesario recompilar
todo el núcleo y reiniciar el sistema completamente.

Modificar el núcleo de Linux para permitir la incorporación de nuevos planifi-

cadores de disco en forma de módulos externos [Pomerantz98].
Para conseguir esta funcionalidad nos basamos en la capacidad que tiene Linux
desde su versión 2.0.X para incluir parte del código del núcleo en módulos com-
pilados de forma independiente y que luego son instalados en el sistema mientras
este está en funcionamiento. Su principal ventaja consiste en poder efectuar todo
el proceso de desarrollo de los nuevos planificadores de disco de forma indepen-
diente del resto del código de Linux e incluirlos después en el sistema sin tener
que reiniciarlo. Para que esto sea posible es necesario modificar el núcleo de
Linux para que admita la inclusión de nuevos planificadores a partir de módulos
externos.

La opción que se ha elegido para implementar el sistema ha sido la segunda. Tal
como muestra la figura 2 de esta forma es posible tener los planificadores de disco
desarrollados fuera del sistema e incluirlos sólo cuando sea necesario. Además, y dado
que la planificación de las peticiones de E/S es una tarea indispensable del sistema, es
necesario incluir en el sistema un planificador de disco por defecto para cuando no se
haya especificado ningún otro planificador. Este planificador sera el mismo que incluye
Linux por defecto, que usa la política CSCAN.

En cuanto al segundo problema a tratar, modificar la interfaz de E/S para permitir
peticiones al disco con parámetros adicionales, hay que tener en cuenta los siguientes
puntos.


Cambio del Planificador

Programas de
Programas de

usuario
usuario

Módulos intercambiables
Módulos intercambiables

Núcleo de Linux
Núcleo de Linux

Planificador alternativo 1
Planificador alternativo 1

Planificador por defecto

Planificador de disco

Planificador alternativo 2
Planificador alternativo 2

Planificador alternativo 3
Planificador alternativo 3

Figura 2: Esquema de inclusión de planificadores alternativos en el sistema

En primer lugar, las peticiones de E/S de los programas de usuario deben ser
realizadas a través de llamadas al sistema. Para la realización de peticiones
con parámetros adicionales se ha optado por sobrecargar la llamada al sistema
ioctl. Esta llamada se usa generalmente para operaciones de control sobre los
dispositivos físicos. La interfaz de que dispone la llamada ioctl es muy versátil,
pudiendo implementarse con ella cualquier tipo de llamada. Nuestra idea es im-
plementar dos nuevas funcionalidades a la llamada ioctl: una de lectura y otra
de escritura. Además de los parámetros de lectura y escritura habituales, estas
funciones incorporan los parámetros adicionales necesarios para controlar las
nuevas políticas de planificación de disco.

Otro aspecto a tener en cuenta es cómo pasar los parámetros extra a través de la
cache del sistema. La forma más fácil es incluir estos parámetros en la estructura
de control de cada bloque de cache. De esta forma, cuando un bloque de cache
sea enviado al gestor de peticiones al disco y éste lo pase al planificador de disco,
se podrán consultar todos estos parámetros adicionales y realizar la planificación
en función de estos datos. Es importante destacar que cuando un bloque de cache
está asociado a una petición de E/S sin parámetros adicionales, su estructura por
defecto debe incluir un valor por defecto para estos parámetros adicionales.

3 Implementación del sistema

A la hora de realizar la implementación de un sistema como este hay que considerar
que partes es necesario incluir dentro del fichero principal del núcleo de Linux y cuáles
se pueden implementar como módulos independientes.

En el primer grupo se encuentran los siguientes cambios:

Modificación de la estructura de control de los buffers de la cache de Linux
para que incluyan parámetros extra. Además se han incluido funciones p