Planificacin de Procesos: Planificacin por lotera

Sistemas de Operaciones I

FACULTAD DE CIENCIAS QUIMICAS, FISICAS Y MATEMATICAS

CCPP INGENIERIA INFORMATICA Y DE SISTEMAS

DOCUMENTACION DEL PROYECTO

PLANIFICACION POR LOTERACurso

:

Sistemas de Operaciones IDocente :

Edwin Carrasco PobleteAlumno:

Conza Berrocal Mary Helen

051687-E

Cusco - Per

2008INTRODUCCION

La planificacin de procesos es un rea de exhaustiva investigacin, su desarrollo ha llegado a ser muy determinante en cuanto a la flexibilidad y eficiencia de ejecucin del proceso, los diversos tipos de planificaciones generalmente traen consigo clculos que suelen entretener al procesador a dedicarse a desarrollar los procesos, esta doctrina de planificacin puede desarrollar por igual cada uno de los procesos, claro preocupndose tambin por los procesos que tienen mas tiempo de espera sin ser ejecutados y hasta por la prioridad.Vale la pena un mtodo de planificacin que maximiza el tiempo de ejecucin del procesador, y en el cual ninguno de los procesos puede morir de inanicin.

Si bien hacer promesas a los usuarios y despus complicarlas es una idea admirable, es difcil de implementar. Podemos usar otro algoritmo para obtener resultados igualmente predecibles con una implementacin mucho ms sencilla. El algoritmo se llama planificacin por lotera (Waldspurger y Weihl, 1994).La idea bsica consiste en dar a los procesos boletos de lotera para los diversos recursos del sistema, como el tiempo de CPU: Cada vez que se hace necesario tomar una decisin de planificacin, se escoge al azar un boleto de lotera, y el proceso poseedor de este boleto obtiene el recurso. Cuando se aplica a la planificacin del tiempo de CPU, el sistema podra realizar una lotera 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 ms iguales que otros. Podemos dar ms boletos a los procesos ms importantes, 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 lotera. A largo plazo, obtendr cerca del 20% del tiempo de CPU. En contraste con los planificadores por prioridad, donde es muy difcil establecer qu significa realmente tener una prioridad de 40, aqu la regla es clara: un proceso posee una fraccin f de los boletos obtendr aproximadamente una f del recurso en gestin.La planificacin por lotera tiene varias propiedades interesantes. Por ejemplo, si aparece un proceso nuevo y se le conceden algunos boletos, en la siguiente lotera ya tendr una probabilidad de ganar que ser proporcional al nmero de boletos que recibi. En otras palabras, la planificacin por lotera es de respuesta muy rpida. MARCO TEORICO

En un sistema de tiempo compartido monoprocesador, se pretende utilizar un algoritmo de planificacin expulsor conocido como algoritmo de la lotera, cuyo funcionamiento se describe a continuacin: cuando se crea un proceso se le asigna un nmero de papeletas en blanco. Por ejemplo, si hay 3 procesos preparados P1, P2 y P3, que cuentan respectivamente con 3, 1 y 5 papeletas, estarn 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 nmero aleatorio entre 1 y el nmero 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 la papeleta sptima, 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 porcin 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 nmero de procesos preparados puede ser distinto y por tanto, el nmero total de papeletas a considerar tambin.

Proporcionar a los procesos boletos de lotera para los diversos recursos del sistema (tiempo de CPU). Cada vez que sea necesario tomar una decisin de planificacin se escoge al azar un boleto de lotera y el proceso que tiene el boleto obtiene el recurso.En el caso de tiempo de CPU el sistema puede realizar un sorteo 50 veces por segundo, otorgando al ganador 20 ms de tiempo de CPU.Debido a que unos procesos son mas importantes que otros, se les da mas boletos para aumentar sus posibilidades (tendr una probabilidad de 20 % de ganar tendr cerca del 20% del tiempo de CPU) Si un proceso tiene una fraccin de boletos, obtendr una fraccin del recurso en cuestin. Si aparece un proceso nuevo se le conceden algunos boletos, en la siguiente vuelta ya tendr la posibilidad de ganar (con una probabilidad proporcional al # de boletos que recibi). COOPERACION ENTRE PROCESOSLos procesos cooperativos pueden intercambiar boletos si as lo desean EJEMPLO:Si un proceso cliente enva un mensaje a un proceso servidor y luego se bloquea, puede regalarle sus boletos al servidor (aumentar sus probabilidades de ejecucin inmediata).Una vez que el servidor termina devuelve los boletos para que el cliente pueda ejecutarse otra vez.Los procesos cooperativos pueden intercambiar boletos si as lo desean. Por ejemplo, si un proceso cliente enva un mensaje a un proceso servidor y luego ese bloque, puede regalarle todos sus boletos al servidor, a fin de incrementar la probabilidad de que el servidor se ejecute a continuacin. Una vez que el servidor termina, devuelve los boletos para que el cliente pueda ejecutarse otra vez. De hecho, en ausencia de clientes los servidores no necesitan boletos.

En esta metodologa de planificacin el usuario es el que ingresa los procesos que es algo que el programa requiere necesariamente.

Luego, el microprocesador es otro actor que se encarga de sortear el tickets (sin realizar clculos que no pueden ocuparle lo mnimo de tiempo) y, ejecutar el proceso, que por contener el ticket sorteado, es el que pasa a ejecutar. Claro que mientras se este ejecutando el proceso no se puede realizar el sorteo, a menos que si hubiera un proceso de entrada/salida, en ese caso el proceso que se estaba ejecutando es llevado nuevamente a la cola de listos (pues es expulsivo).

El sistema es el que asigna las papeletas a los procesos en cada ciclo de reloj beneficiando a los que estn ms tiempo sin ejecutarse y a tambin de acuerdo a la prioridad.

PROCESO DE DESARROLLO

Los modelos presentados a continuacin corresponden al proceso de desarrollo basado en el trabajo que hace ms de un lustro vienen realizando los three amigos, Grady Booch, James Rumbauh e Ivar Jacobson, y ha tomado forma en el proceso unificado (United Process UP), como gua metodolgica y el lenguaje Unificado de Modelado(United Modeling Language,UML), como notacin para los modelos.

DISEO DE LAS CLASES

Se implementaron dos clases:

La ClaseLista consta de procesos que el algoritmo proporciona aleatoriamente

ClaseLista:

Atributos:

protected ClaseProceso aProceso;

//Es el primer elemento de la lista

protected ClaseLista aSubLista;

//Es la lista sin considerar el aProceso

Constructores:

public ClaseLista()

//Inicializa con los atributos en null

public ClaseLista(ClaseProceso aProceso, ClaseLista aSubLista) //Inicializa con los parmetros sealadosConstructores:

public ClaseProceso(int aIdentificador, int aNroPapeletas, int aTInicio, int aServidor, int aPrioridad)

//crea el proceso con esos parmetros ingresados

public ClaseProceso(int aTInicio) //crea proceso inicializando todo en 0 excepto el Tiempo de Inicio

Mtodos y propiedades:

get y set de cada atributo;

public boolean EsVacia();

//retorna true si la lista esta vacia

public void Insertar(ClaseProceso Proceso) //inserta Proceso en la lista

boolean ExisteElemento(ClaseProceso Proceso) //retorna true si existe elemento

public void Eliminar(int posicion) //elimina elemento que ocupa una determinada posicin en la lista

public int Longitud() //retorna el numero de procesos que contiene la lista

public ClaseProceso Iesimo(int i) //retorna proceso en la posicin i

public int Posicion(ClaseProceso Proceso) //devuelve la posicin del Proceso

ClaseProceso:Constructores:

public ClaseProceso(int aIdentificador, int aNroPapeletas, int aTInicio, int aServidor, int aPrioridad)

//crea el proceso con esos parmetros ingresados

public ClaseProceso(int aTInicio) //crea proceso inicializando todo en 0 excepto el Tiempo de Inicio

Atributos:

protected int aIdentificador;

//Es el identificador del proceso,

protected int aNroPapeletas;

//El nmero de papeletas del proceso, es el nico atributo que asignado por el //sistema, es el nico que se modifica en cada ciclo de reloj protected int aTInicio;

//tiempo en el que inicio, asignado por time t protected int aServidor;

//Indica su proceso servidor protected int aPrioridad;

-//Indica la prioridad de ejecucin

protected int aServ;

//Indica el proceso servidor que aun no se ingresa en la cola de listos, este //atributo sirve para retornarlos tickets al cliente cuando su servidor ya se //ejecut

Mtodos y propiedades:

get y set de cada atributo

NOTA: Todos los atributos son aleatorios, excepto el ID (que asume su valor en orden secuencial), y el aTInicio (que toma su valor del time t).

DISEO DE LA APLICACIN

La aplicacin tendr los siguientes mdulos:

public void CrearProceso()public void DaPapeletas()public ClaseProceso ProcesoGanador(int k)public int ProcesoNormal()private void DevolverPapeletas(ClaseProceso Proceso)

Variables Globales:

Como se ha podido ver hay variables que se tienen que actualizar con cada ciclo de reloj, pero otras no, aqu vemos las variables que tienen que actualizarse y que estn en disposicin para todos los modulos.int ID=0;

//Variable contador, para asignar identificador a cada proceso al rato de crearse

int tiempo=0;

//Variable contador de ciclos de reloj, cada ciclo aumenta en 1; int TiempoEntroProcesador=0;

//Tiempo en el que el proceso ingresa al estado ejecutandoint TotalPapeletas=0; //Variable acumulador de ticket en total, se va actualizndose al crear procesos, al //ejecutar procesos y en cada ciclo de relojRandom Aleatorio=new Random(); //Para realizar todo aleatoriamente como papeleta ganadora, tiempo para crear //procesos y tiempo para eliminar procesos por pasar al estado ejecutando. ClaseProceso Proceso=new ClaseProceso(0);

//Crea el objeto proceso con tiempo inicial 0;ClaseLista Lista=new ClaseLista();

//Crea el objeto Lista con aProceso=null y aSubLista=null;

INTERFAZ

Se puede observar:

Nuevo:Es el proceso que se guardar en la cola de Listos o si esta libre el procesador va al procesador directamente.

Cola de listos:

Es la cola donde esperan los procesos para ser ejecutados.

Ticket Sorteado:Es el ticket que ejecuta el microprocesador.

Proceso Ganador: Proceso poseedor del tickets, pasa al microprocesador para ejecutarse.

Ingrese funcin de Entrada y Salida:

Boton que sirve para simular un proceso de entrada/salida, al proceso que esta ejecutando lo lleva nuevamente a la cola de listos.A continuacin, se va a explicar los procesos Cliente/servidor y Entrada/Salida mediante esta interfaz;

CLIENTE/SERVIDOR

Primero la lista esta vaca, proceso 0 se est ejecutando.

Segundo, ingresa a la cola de listos los procesos 1 y 2, observar que ambos no pueden ejecutarse por ser clientes (debido la tercera fila).

Tercero, ingresa el proceso tres la cola de listos, y su servidor 3 le presta sus tickets a su servidor..

Luego, 2 gana pero es cliente; entonces, se realiza un nuevo sorteo, en el que gana 3 y es atendido, al estarse ejecutando este da permiso para que su cliente se pueda ejecutar, adems le devuelve sus tickets que este le haba prestado para que se ejecute.

ENTRADA/SALIDAPara que este proceso se ejecute se debe presionar el botn que dice Ingrese Funcin de Entrada y salida

Antes de que se presione el botn, el proceso 3 se estaba ejecutando.

Despus de que se presiona el botn, el proceso 3 es expulsado y vuelve a la cola de listos, para concursar otra vez por el sorteo para ser ejecutado.

REFERENCIASBIBLIOGRAFA[1]TANENBAUH A.; "Sistemas de Operaciones Modernos". Prentice-Hall. 1992.[2] ECKEL BRUCE; Piensa en Java. Pearson Educacion.S.A Madrid 2002.

WEBGRAFA[1]http://www.dia.eui.upm.es/asignatu/sis_op1S/Examenes%20SOI/examenes/0304de2.doc

[2]http://www.ldc.usb.ve/~spd/Docencia/sop1.html[3]http://www.planificacionprocesos.usb.ve/~spd/Docencia/sop1.html[4]http://www.notasinformaticas/sop1.html[5]http://www.sistemasoperativostodos/sop1.html HYPERLINK "http://en.wikipedia.org/wiki/Image:UNSAAC.jpg" \o "Seal of the Universidad Nacional de San Antonio Abad del Cusco" INCLUDEPICTURE "http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/UNSAAC.jpg/150px-UNSAAC.jpg" \* MERGEFORMAT

P3

P1

P2

Papeletas

Pgina 17 de 17