Planificación de procesos por lotería - sistemas operativos

[pic]

FACULTAD DE CIENCIAS QUIMICAS, FISICAS Y MATEMATICAS

CCPP INGENIERIA INFORMATICA Y DE SISTEMAS

DOCUMENTACION DEL PROYECTO
PLANIFICACION POR LOTERÍA

Curso : Sistemas de Operaciones I

Docente : Edwin Carrasco Poblete

Alumno : Conza Berrocal Mary Helen 051687-E

Cusco - Perú

2008

INTRODUCCION

La planificación de procesos es un área de exhaustivainvestigación, su desarrollo ha llegado a ser muy determinante en cuanto a la flexibilidad y eficiencia de ejecución del proceso, los diversos tipos de planificaciones generalmente traen consigo cálculos que suelen entretener al procesador a dedicarse a desarrollar los procesos, esta doctrina de planificación puede desarrollar por igual cada uno de los procesos, claro preocupándose también por losprocesos que tienen mas tiempo de espera sin ser ejecutados y hasta por la prioridad.

Vale la pena un método de planificación que maximiza el tiempo de ejecución del procesador, y en el cual ninguno de los procesos puede morir de inanición.

Si bien hacer promesas a los usuarios y después complicarlas es una idea admirable, es difícil de implementar. Podemos usar otro algoritmo paraobtener resultados igualmente predecibles con una implementación mucho más sencilla. El algoritmo se llama planificación por lotería (Waldspurger y Weihl, 1994).

La idea básica consiste en dar a los procesos boletos de lotería para los diversos recursos del sistema, como el tiempo de CPU: Cada vez que se hace necesario tomar una decisión de planificación, se escoge al azar un boleto delotería, y el proceso poseedor de este boleto obtiene el recurso. Cuando se aplica a la planificación del tiempo de CPU, el sistema podría realizar una lotería 50 veces por segundo, concediendo a cada ganador 20ms de tiempo de CPU como premio.

Parafraseando a George Orwell, “todos los procesos son iguales, pero algunos son más iguales que otros”. Podemos dar más boletos a los procesos másimportantes, a fin de aumentar sus posibilidades de ganar. Si hay 100 boletos pendientes, y un proceso tiene 20 de ellos, tendrá una posibilidad del 20% de ganar cada lotería. A largo plazo, obtendrá cerca del 20% del tiempo de CPU. En contraste con los planificadores por prioridad, donde es muy difícil establecer qué significa realmente tener una prioridad de 40, aquí la regla es clara: un procesoposee una fracción f de los boletos obtendrá aproximadamente una f del recurso en gestión.

La planificación por lotería tiene varias propiedades interesantes. Por ejemplo, si aparece un proceso nuevo y se le conceden algunos boletos, en la siguiente lotería ya tendrá una probabilidad de ganar que será proporcional al número de boletos que recibió. En otras palabras, la planificación porlotería es de respuesta muy rápida.

MARCO TEORICO

En un sistema de tiempo compartido monoprocesador, se pretende utilizar un algoritmo de planificación expulsor conocido como algoritmo de “la lotería”, cuyo funcionamiento se describe a continuación: cuando se crea un proceso se le asigna un número de papeletas en blanco. Por ejemplo, si hay 3 procesos preparados P1, P2 y P3, que cuentanrespectivamente con 3, 1 y 5 papeletas, estarán ordenados en la cola como P3, P1 y P2. Cuando hay que elegir un nuevo proceso a planificar, el sistema realiza un sorteo generando un número aleatorio entre 1 y el número total de papeletas repartidas.

Tras el sorteo, encontraremos al ganador si contamos papeletas desde el principio de la cola de preparados. Por ejemplo, si sale ganadora lapapeleta séptima, el ganador será el proceso P1.

El proceso ganador tomará control de la CPU hasta que se bloquee voluntariamente o el sistema le expulse porque haya consumido una porción de tiempo preestablecida. El sorteo se repite siempre que haya que elegir un nuevo proceso a planificar, teniendo en cuenta que, en cada sorteo, el número de procesos preparados puede ser distinto y por...
tracking img