Simulación del Algoritmo SJF

A continuación pongo en consideración una pequeña simulación del algoritmo “primero el trabajo más corto” (shortest – job – first).

La aplicación esta desarrollada en Java bajo el IDE NetBeans 6.0 y permite crear procesos(en realidad son solo objetos no hilos) que ocuparán cada uno un tiempo de ejecución o uso de CPU determinado por el usuario.

Esto funciona de la siguiente manera al establecer cuantos procesos se realizarán el usuario deberá especificar que tiempo tardará cada uno en terminar, para luego la aplicación planifique su ejecución empezando por el más pequeño.

Una vez encontrado el orden exacto cada proceso ocupará el thread(hilo) central de la aplicación haciéndola detener para que nadie pueda ocuparlo mientras él se ejecuta, además cabe recalcar que por ser una demostración se estima el tiempo en segundos(el hacerlo unidades menores no daría mucha idea de lo que sucede). Luego abandonará el control del hilo y pasará al siguiente. Al terminar todos los procesos la aplicación también terminará.

Puedo decir que este algoritmo presenta varias ventajas pues al realizar los procesos con menor tiempo primero el tiempo de espera disminuye considerablemente aunque en una situación real la única dificultad es el cálculo de la ráfaga de CPU que como mencioné en un post anterior es aproximada.

Pueden descargar la aplicación desde  aquí 

Saludos,

Actualización: Si el link de descarga presenta problemas accede desde aquí o desde el widget que se encuentra en la parte izquierda del blog.

Introducción a la Sociedad de la Información

A lo largo de los tiempos todas las sociedades que conocemos se formaron de revoluciones que generaron en sus habitantes desarrollo.

Y la Sociedad de la información no fue la excepción, pues sus orígenes están dentro de la revolución de la tecnología para tratar la información y difundirla.

Se remonta al auge y terminación de la Sociedad Industrial, una Sociedad que logró concentrarse en los medios de producción donde las máquinas unidas a la inteligencia humana crearon el cambio, una sociedad en donde todo lo producido se podía palpar. Pero al terminar sobrevino luego una Sociedad conocida como la Post-Industrial(Sinónimo de Sociedad de Información) que se desprendería de la anterior y empezaría a tomar como parte importante a la información. Pues, se logra consolidar a la información como la base fundamental del desarrollo, pero puede la información ser por sí misma generadora de Avances??? A decir verdad la única forma para que la información genere desarrollo es transformarla en conocimiento, pero como??? Y es aquí en donde la Sociedad de la Información toma lugar.

Se registra una gran evolución en cuanto a como tratar la información(medios), la comunicación se vuelve el principal medio de transmisión del conocimiento y se usa como medio principal a la gran Red “Internet”. Ahora esta Sociedad a diferencia de las anteriores ya no tiene un espacio físico reducido donde avanzar, pues a logrado que las barreras físicas desaparezcan, la información ya no es reducida y acaparada, sino libre!!!! Los avances de la tecnología han logrado que la cooperación sea la gran aliada para que esto se realice, con la creación de redes Sociales que contribuyen a generar espacios en donde no hay las barreras físicas.

En definitiva puedo decir que la Sociedad de la Información ha sido muy significativa, pues a pesar de su poco tiempo ha avanzado a pasos agigantados gracias a que cualquiera puede formar parte del desarrollo.

Saludos,

ALGORITMOS DE PLANIFICACIÓN EN LA CPU

Planificación FCFS

El algoritmo FCFS(first come – first-served), conocido como primero en llegar, primero en  ser atendido.

Dentro de este campo de planificación es el más sencillo, pues es similar a una cola de estructura (FIFO)

Este algoritmo trabaja de la siguiente manera, al entrar un proceso al estado de “listo”,  el bloque de control de proceso se ubica en el final de la cola, entonces el cpu al estar libre retirará de esta cola el primer elemento(cabeza).

Es decir, en este algoritmo el tiempo de espera par que un proceso se ejecute es incierto y no mínimo. Pudiendo así ejecutarse dentro de la cpu un proceso que consuma demasiado tiempo, atrasando a otros procesos y dejando la cpu sin trabajo por lapsos de tiempo.

En definitiva este algoritmo hace que los procesos pequeños esperen a que un grande abandone la cpu. Una gran desventaja.

Planificación en SJF

El algoritmo “primero el trabajo más corto” (shortest – job – first). Establece para la planificación una relación entre proceso y ráfaga de la CPU. Es decir, al liberarse la cpu ingresará el proceso con la menor ráfaga de tiempo, el más pequeño primero, y si existiera más de un proceso con igual valor, pues se aplicaría dentro de este el algoritmo anterior(FCFS)

Este algoritmo presenta una gran ventaja, pues el tiempo de espera será mucho menor, pues mientras los procesos de tiempo inferior terminan y ocupan tiempo en operaciones de E/S, el cpu se ocupa de resolver el proceso con mayor tiempo, un algoritmo muy óptimo.

Pero, el mayor problema radica en como saber el tiempo de ráfaga para cada proceso???? Pues no existe manera de saber cual será la siguiente. Pero podemos aproximarnos, diciendo que será similar a las anteriores, que mediante una fórmula matemática podríamos decir que:

Tn +1  = a Tn + (1 – a)Tn

De donde Tn es la ráfaga anterior y a es el peso relativo de la historia reciente. Lo que garantiza una aproximación mas considerable.

 

Planificación por Prioridad

Esta clase de algoritmo utiliza como relación entre proceso, tiempo de la cpu y prioridad. De donde el proceso con mayor ráfaga tendrá la menor prioridad y viceversa.

Y donde la cpu podrá ser utilizada por el proceso con mayor prioridad.

Dentro de este algoritmo la prioridad es asignada ya sea interna o externamente. Pero, uno de los problemas que puede presentar esta planificación es la de un bloqueo indefinido. Es decir, pudiera darse el caso que existan procesos de prioridad alta que harían que los procesos de prioridad baja queden bloqueados hasta que logren colocarse en la cpu o perderse cuando nuestro sistema se caiga, es decir una espera indefinida.

Es aquí donde se puede aplicar una técnica conocida como envejecimiento, que ira incrementando la prioridad de los procesos en espera cada determinado tiempo hasta que estos se ejecuten. Y a mi parecer este es una de las mejores soluciones.

 

Planificación con RR

La planificación por turnos o Round Robin, se basa en una estructura FIFO de forma circular, en donde se asigna a los procesos un intervalo de tiempo para la cpu, conocido como quantum. En donde se establece la regla de que un proceso no podrá estar dos veces seguidas en la cpu a menos que sea el único en el estado de listo.

Este algoritmo trabaja de la siguiente manera, al ingresar el proceso a utilizar la cpu, este estará dentro del tiempo(quantum), si al terminar este tiempo el proceso no ha terminado es colocado al final y se ingresará otro proceso. Pero si el proceso pasa ha estado terminado antes de terminar su quantum, también será extraído de la cpu.

En cambio este algoritmo presenta complicaciones pues el tiempo de entrega de un proceso dependerá mucho más del tiempo(quantum) que de la magnitud del proceso.

 

Saludos,

La CPU y los algoritmos de Planificación

La planificación de uso de la CPU, es la base de todo sistema operativo, ya que una planificación correcta permitirá un uso máximo, lo que causaría un rendimiento “optimo”.
Pero, como hace un Sistema Operativo para planificar sus procesos???

Partamos pues de que un proceso necesita una cantidad de tiempo para ser realizado(cambiar de estado a terminado), pero como un mismo proceso no puede ocupar la cpu hasta que termine se permitirá a cada proceso un tiempo de uso de cpu, también conocido como “ráfaga de la cpu”, y para esto se almacenara toda la información del proceso, (como su estado, tiempo de espera, entre otros) dentro de un “bloque de control del proceso” (PCB) que determinará todo el estado de un proceso.

Pero, como “sabe”(literalmente) el Sistema Operativo que proceso es el correcto  o más necesario para que utilice la cpu???

Pues a decir verdad cada sistema operativo implementa criterios de planificación, basados en algoritmos que intentan que la cpu no este ociosa(en tiempo de espera Ej. E/S)

Entre los criterios que se emplean para la planificación puedo mencionar:

  • Utilización de la CPU.- Tenerla tan ocupada como sea posible. Esto es un 40% en Sistemas ligeros y 90% en sistemas pesados.
  • Rendimiento.- Calculado mediante el número de procesos que es capaz de terminar en una unidad de tiempo.
  • Tiempo de Entrega.- Se considera como el tiempo desde que un proceso inicia hasta que termina.
  • Tiempo de espera.- Lo considero como la suma de periodos de tiempo en la cola de listos.
  • Tiempo de Respuesta.- Es el tiempo que se requiere para que un proceso empiece a responder y no el tiempo para dicha respuesta.

Siguiendo estos criterios, se deduce que lo más deseable es que aumenten los dos primeros puntos(Utilización – rendimiento) y disminuyan todos los demás.

Para conseguir este fin se utilizan algoritmos que distribuyen o planifican procesos, por ahora solo los enunciaré para en un próximo post detallarlos:

  • FCFS
  • SJF
  • Procesos por Prioridad
  • RR

Saludos,

OTRO JUEGO EN GREENFOOT

Y aún sigo en la aventura del mundo Greenfoot, y vaya que es súper divertido a parte de fácil, pues en esta ocasión he estado trabajando en un juego basado en un laberinto, de dos jugadores en donde el objetivo es recolectar la mayor cantidad de puntos, el juego termina cuando cualquiera de los jugadores tome el hongo central del escenario que tiene un valor de 200 !!!! puntos.

Bueno ahora vamos a la parte interesante(el bajo mundo –> código….), pues está por demás decir que la aplicación es creada con el IDE Greenfoot y por supuesto Java, como el laberinto utiliza elementos como paredes, los tipos de puntos y los jugadores, cada uno de estos serán un OBJETO dentro del programa( en un próximo post hablaré sobre la POO programación orientada a objetos) lo que hacemos es crear una clase para cada objeto encapsulando todos sus atributos y claro agrupándolos en clases comunes en donde se pueda aplicar herencia, como los puntos.

Muy bien, ahora el juego reconoce 4 clases de puntos con diferentes valores que aumentarán el puntaje del jugador, para implementar esto en código utilizamos las sentencias:

if(getOneIntersectingObject( NombreClasePuntos.class)!=null){

}

Lo que localizará todos los objetos que “choquen” con el jugador.

Al final, lo que queda por hacer es tomar los marcadores de los dos jugadores y encontrar quien tiene el puntaje más alto, o si hay un empate.

 

Claro, el juego implementa algunos métodos importantes como movimientos, la puesta de marcadores para los puntos, por eso les colocó el link de descarga de la aplicación como proyecto de GreeFoot. Aquí unas capturas de pantalla de la aplicación ya terminada.

Inicio de Juego
Pantalla de Incio
Pantalla si resulta el juego empatado…
Pantalla Final al ganar un jugador…

Si quieres más detalles de la aplicación, escribe un comentario.

Saludos,