Proyecto Unidad Ii

Sistemas Operativos

ESCUELA DE INFORMATICA

UNIVERSIDAD NACIONAL DE TRUJILLO

Objetivos 1. COMPRENDER el problema de la sincronización y el interbloqueo 2. INTEGRAR los conceptos sobre sincronización e interbloqueos para evitar los abrazos mortales. 3. Integrar conceptos sobre Hilos

Proyecto Unidad II Algoritmo del Banquero e Hilos En este proyecto deberás implementar el algoritmo del banquero que se presenta en la sección 7.5.3 del libro. El algoritmo del banquero recibe peticiones de clientes que quieren utilizar los recursos del sistema. El banquero accede a la petición del cliente solamente cuando esto deje al sistema en un estado seguro. Las peticiones que dejan al sistema en un estado inseguro son rechazadas. Una vez implementado el algoritmo, deberás crear una aplicación con múltiples hilos de ejecución para probar tu implementación. Es importante que leas todo el proyecto antes de comenzar a programar, para asegurarte que comprendes bien todos los puntos. Algoritmo del Banquero Esta hecha toda la implementación del algoritmo. Lo que falta es que utilices las clases y métodos definidos en las clases Sistema.java y Banco.java para implementar los dos algoritmos (el algoritmo de seguridad y el algoritmo del banquero propiamente) de la sección 7.5.3 del libro. En particular debes extender la clase Banco.java implementando los métodos abstractos que en ella se definen. Esta clase abstracta te proporciona además un par de métodos auxiliares que puedes utilizar en tu implementación. Las características del sistema (número de recursos y clientes, asignación y disponibilidad de recursos a los clientes, etc.) han sido abstraídas en la clase Sistema.java, la cual tiene toda la funcionalidad necesaria para administrar las estructuras de datos requeridas por el algoritmo del banquero. Revisa su documentación para mayores detalles.

Ms Edwin Raúl Mendoza Torres

Sistemas Operativos Aplicación de Prueba Para probar tu implementación te pedimos que crees la siguiente aplicación. Usaremos el algoritmo del banquero en dos instancias diferentes: una para resolver una variante del problema de los filósofos comensales; la otra para resolver la problemática que tienen los cocineros de una cocina al crear sus platillos. Juntaremos ambos problemas en uno solo. El restaurante "El Abrazo Mortal" se encuentra a un costado de la Facultad de Filosofía de la Universidad y es el lugar favorito para comer de algunos profesores y alumnos de la facultad. Como sus dueños son algo excéntricos, insisten en tener siempre una sola mesa en el restaurante, cuyo tamaño varían día con día. La mesa del restaurante alberga no menos de 5 filósofos. Al centro de la mesa hay dos platos grandes, uno con alimentos y otro con palillos de madera. Siempre se coloca 1 palillo por cada lugar que haya en la mesa, de forma que si hay 5 lugares, en el plato habrá 5 palillos. Todos los filósofos comensales comparten los palillos y cada uno requiere dos de ellos para comer. Como son compartidos y tienen muchos temas intersantes en que filosofar, todo el tiempo realizan los siguientes pasos en orden y luego se repiten: si hay al menos un platillo y dos palillos en la mesa, los toman y comen, luego devuelven los palillos y se ponen a pensar. Si un filósofo no pudo comer porque no habían palillos o comida, no puede volver a pensar hasta que haya saciado su apetito, por lo que en cuanto alguien devuelve sus palillos o traen mas comida a la mesa vuelve a intentar comer, hasta que lo consiga. Solo entonces pasa nuevamente a filosofar. Dado que los filósofos son muy moderados, solo toman un palillo a la vez, y no toman comida sino hasta que ya tienen los dos palillos que requieren. La cocina de este peculiar lugar es también un lugar extraño, los cocineros que ahí trabajan son muy ideáticos. En la cocina hay dos tipos de personas: los cocineros y sus ayudantes. Los cocineros son los que dictan lo que se debe hacer y los ayudantes no hacen nada hasta que un cocinero les pide que hagan algo. Los cocineros no toman ordenes de los clientes, sino que cada uno hace lo que se le antoja. Además son muy malos para delegar trabajo, por lo que cuando requieren que alguno de los ayudantes trabaje ellos mismos no hacen nada sino observar que el ayudante haga todo bien. Por esa razón cada uno sigue la siguiente rutina. 1. Elige una receta 2. Comienza a preparar la receta 3. Conforme prepara la receta, va sacando ingredientes de las reservas de la cocina 4. Si durante la preparación el cocinero requiere que algún ayudante haga algo, le asigna la tarea y espera a que termine. 5. Cuando termina de preparar la receta el cocinero va a la bodega y vuelve a traer a las reservas de la cocina todos los ingredientes que utilizó, de tal forma

Ms Edwin Raúl Mendoza Torres

Sistemas Operativos que parece que "devuelve" todos los ingredientes que fue requiriendo durante la preparación. 6. La comida se sirve en cuanto está lista a la mesa de los filósofos y el cocinero vuelve a empezar su ciclo. Los ayudantes no hacen nada mas que esperar a que les asignen trabajo. Cuando esto ocurre, actuan como mini-cocineros: solicitan los ingredientes que necesitan (de los que se indican en la receta) y laboran durante un tiempo hasta que terminan con la tarea que se les asignó. Si un cocinero necesita un ayudante pero todos están ocupados, entonces el mismo hace el trabajo. Implementación de la Aplicación En este restaurante hay dos sistemas que se deben controlar mediante el algoritmo del banquero: la cocina y la mesa del comedor. La mesa del comedor tiene solo 2 tipos de recursos (palillos y comida), mientras que la cocina tiene un número variable de recursos (los ingredientes; para tus pruebas usa al menos 5 ingredientes distintos, aunque fácilmente puedes crecer este número lo que quieras). El comedor tiene un solo tipo de cliente, los filósofos. Todas las peticiones de recursos por parte de los filósofos se deben hacer a través de tu implementación del algoritmo del banquero y se deben hacer un recurso a la vez (cada palillo cuenta como un recurso distinto). La cocina tiene dos tipos de clientes, los cocineros y los ayudantes. El número de ingredientes y la cantidad disponible de cada uno se especifican desde el momento en que se crea la cocina y no se modifican con el tiempo. La "bodega" no existe realmente, sino que es un recurso que utilizamos para justificar que los cocineros "devuelven" todos los ingredientes que utilizaron al terminar de hacer su receta, por lo que no lo tienes que programar. Los cocineros solo regresan los ingredientes una vez que terminaron su receta, nunca antes (ni siquiera parcialmente). Los cocineros pueden pedir varios ingredientes de una sola vez, pero por lo general no piden todos los ingredientes desde el principio, sino solo subconjuntos de estos. Cuando un cocinero está cocinando una receta realiza una de 3 acciones: pedir ingredientes (recursos), delegar tareas en un ayudante, o cocinar. Al pedir recursos lo hace a través de tu implementación del algoritmo del banquero y solo pide recursos cuando no tiene todos los que su receta dice que necesita. Si su petición es rechazada, se espera a que algún otro cocinero "regrese" sus ingredientes y entonces vuelve a hacer su solicitud, repitiendo hasta que finalmente se le concede su solicitud. Cuando el cocinero delega tareas elige a alguno de los ayudantes que estén inactivos y lo pone a trabajar. El cocinero realiza una petición de ingredientes (según los que falten todavía para hacer la receta), se los pasa al ayudante y espera hasta que este termine para continuar con su trabajo. El ayudante toma los ingredientes, los procesa durante algún tiempo y cuando termina regresa a su estado de inactividad. Cuando el cocinero cocina no interactua con el sistema, sino que procesa los ingredientes que ya tiene durante algún tiempo y luego vuelve a realizar alguna de las tres acciones.

Ms Edwin Raúl Mendoza Torres

Sistemas Operativos Las siguientes son algunas restricciones e indicaciones generales: • • • • •

Cada filósofo, cocinero y ayudante debe correr como un Thread (http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Thread.html ) distinto. Debe haber 2 instancias de Sistema, una para la cocina y otra para el comedor. Debe haber 1 sola instancia del algoritmo del banquero que atienda a los dos sistemas. En el comedor debe haber el mismo número de filósofos que de palillos en la mesa, y este número debe ser al menos 5. En la cocina debe haber al menos 3 cocineros y 2 ayudantes.

Concurrencia Es importante que notes que las funciones que te proporcionamos no son seguras para ser usadas por distintos threads. Si por ejemplo un cliente utiliza el algoritmo del banquero y su tiempo de procesador termina cuando estáa a la mitad del proceso, luego otro cliente del mismo sistema usa el algoritmo para pedir recursos y le son otorgados, cuando el primer proceso recupera el uso del procesador los chequeos que había hecho quedan invalidados porque el estado del sistema ha cambiado sin que se diera cuenta. Por esta razón es muy importante que cuando programes el algoritmo del banquero hagas que se eviten este tipo de situaciones, i.e. tu implementación debe ser segura en términos de concurrencia. Los clientes compiten por los recursos de cada sistema, por lo que tendrás que evitar situaciones de concurso, administrar el acceso a la memoria compartida (los arreglos que mantienen el estado del sistema), evitar la hambruna, etc. Puedes utilizar toda la funcionalidad del API de Java para sincronización. En particular cuando tus clientes tengan que esperar porque sus peticiones han sido rechazadas, no uses spinlocks, utiliza alguno de los mecanismos que te proporciona Java para esperar. Cuando tus cocineros tengan que esperar a que algún ayudante termine su labor te conviene utilizar los métodos join e interrupt de la clase Thread. Checa la documentación para mas detalles.

Ms Edwin Raúl Mendoza Torres