Algoritmos de planificación de la CPU.

La multiprogramación es la capacidad del Sistema Operativo de cargar varios programas en la memoria principal los cuales se van alternando el uso de la CPU.
La forma como el Sistema Operativo va alternando la CPU define la eficiencia en el manejo de la CPU respecto a la satisfacción de la ejecución de dichos programas (en realidad procesos).

Algoritmos de planificación.

Imaginemos que tenemos un CPU y un conjunto de procesos que desean ocupar dicho CPU, los algoritmos de planificación nos indican cual proceso y bajo qué condiciones va a ocupar la CPU.

FCFS (First Come First Served):

El primero que llega es atendido, es el algoritmo de planificación más sencillo ya que consiste solamente en ir sirviendo la CPU a los procesos en el orden como van llegando. Cada proceso que llega se forma en una cola al pasar su turno el proceso satisface su requerimiento del CPU y termina su ejecución. Este algoritmo por su comportamiento es del tipo FIFO (First In First Out) para explicar el comportamiento de dicho algoritmo imaginemos que tenemos 3 procesos el proceso P1 que ocupe 24 unidades de tiempo, el proceso P2 que ocupe 4 y el proceso P3 que ocupe 4, y que hayan llegado de forma correspondiente.

FCFS

Como podemos ver la eficiencia del algoritmo FCFS depende del orden en el que van llegando los procesos.

Mayor información:
https://en.wikipedia.org/wiki/First-come,_first-served

SJF (Shortest Job First):

Entonces si la eficiencia del algoritmo FCFS depende del orden esto implica que existe un orden en el cual la eficiencia es óptima, pero… ¿cuál es ese orden optimo?, lo ideal es atender primero a los procesos que requieran menos unidades de tiempo. El algoritmo SJF es una mejora del algoritmo FCFS al ordenar los procesos en la cola en orden ascendente de tal forma que se ejecuten los procesos más ligeros al principio y con esto mejoramos la eficiencia. Como se puede ver en la siguiente imagen:

SJF (Shortest Job First)

SJF (Shortest Job First)

El algoritmo SJF es óptimo, el problema de este algoritmo consiste en el que el Sistema Operativo no siempre sabe cuánto tiempo va a requerir cada proceso, una solución consiste en que el programador de aplicaciones estimule los tiempos de los procesos lo cual a su vez representa ciertas complicaciones.

Round Robin:

Reparte el CPU en unidades de tiempo denominada quantum de tal manera que cada proceso tiene a su disposición el CPU durante un quantum al terminar este tiempo le sede el CPU al siguiente proceso. Si un proceso no concluye su ejecución durante un quantum al finalizar se forma en la cola nuevamente para continuar su ejecución en la siguiente ronda. El concepto de ronda refiere a una iteración en la que a cada proceso se le asigna un quantum. La eficiencia de Round Robin depende en gran medida en el tamaño del quantum que se elija.

Algoritmo de RoundRobin

Algoritmo de RoundRobin

La imagen anterior muestra una implementación de Round Robin en donde cada proceso ocupa un quantum completo sin importar si el proceso ocupa mas o menos tiempo del CPU, siempre se ele asigna un quantum.

Ejercicio:

Calcular el tiempo promedio(tp) para los algoritmos FCFS, SJF y RR(use quantums de 4 unidades), para los siguientes procesos:

  • p0  (15)
  • p1  (25)
  • p2  (3)
  • p3  (10)
  • p4  (8)

Solución:

Veamos la solución:

Código fuente:

Dejo una implementación desarrollada en lenguaje C.

Inyecciones SQL, (como prevenir)

sql_injection_vulnerable
Es común encontrarnos con aplicaciones vulnerables a inyecciones SQL, estos ataques se deben a que los desarrolladores omiten la tarea de validar los datos introducidos por los usuarios, veamos un ejemplo de una aplicación vulnerable y luego veamos como prevenir inyecciones, usted puede descargar el código fuente desde:
https://gist.github.com/fitorec/9b8312d83a2b4aa902b38aee4a067962

La aplicación consta de la siguiente estructura:

src/
`-- inyeccionsql
    |-- BD.java
    |-- InyeccionSQL.java
    |-- LoginVista.fxml
    |-- LoginVistaController.java
    |-- base_datos.sql
    `-- style.css

El archivo de base_datos.sql contiene el esquema la cual contiene una sola tabla con nombre usuarios:

CREATE TABLE `usuarios` (
	`id` INT NOT NULL AUTO_INCREMENT PRIMARY KEY,
	`username` VARCHAR(15) NOT NULL UNIQUE KEY,
	`password` CHAR(32) NOT NULL ,
	`fecha_nacimiento` DATE NOT NULL
) ENGINE = InnoDB;

-- Agregando dos usuarios

INSERT INTO `usuarios`
	(`id`, `username`, `password`, `fecha_nacimiento`) VALUES
	(NULL, 'fitorec', 'ABC123456...', NOW()),
	(NULL, 'pepe_grillo', 'ABC123456...', NOW());

BD.java Es una clase singletón que se encarga de la conexión a la base de datos, mientras que InyeccionSQL.java es la clase principal y solo se encarga de iniciar la aplicación, mandando abrir una escena con el contenido de LoginVista.fxml de la cual su controlador es LoginVistaController.java  esta tiene el método accionLogin encargado de validar el login como podemos ver en el siguiente código:

    @FXML
    private TextField username;
    @FXML
    private PasswordField password;
    @FXML
    private void accionLogin(ActionEvent event) {
        try {
            String sql = "SELECT * FROM usuarios "
                + "WHERE username='"+username.getText() + "'"
                + " AND password='"+password.getText()+"'";
            PreparedStatement ps = BD.getConexion().prepareStatement(sql);
            ResultSet r =  ps.executeQuery();
            if (r.next()) {
                String uname = r.getString("username");
                label.setText("Bienvenido: " + uname);
            } else {
                label.setText("Login invalido");
            }
        } catch(Exception e){
            label.setText("Error SQL");
        }
    }

En el ejemplo podemos ver como concatenamos literalmente el contenido de los inputs username y password, ¿pero que pasa si un usuario mal intencionado agrega los siguientes datos, para el username x y para el password x' OR 1='1?, esto nos genera la consulta:

SELECT * FROM usuarios
       WHERE username='x' AND password='x' OR 1='1';

login_correcto

Dicha consulta es conocida como “siempre cierta” y nos dará un acceso correcto al sistema,incluso podríamos concatenar la consulta con un DROP o TRUNCATE, como se muestra en la siguiente imagen =).
exploits_of_a_mom.png

Pero.. como evitar esto

private void accionLogin(ActionEvent event) {
        try {
            String sql = "SELECT * FROM usuarios "
                + "WHERE username=?"
                + " AND password=?;";
            PreparedStatement ps = BD.getConexion().prepareStatement(sql);
            ps.setString(1, username.getText());
            ps.setString(2, password.getText());
            ResultSet r =  ps.executeQuery();
            if (r.next()) {
                String uname = r.getString("username");
                label.setText("Bienvenido: " + uname);
            } else {
                label.setText("Login invalido");
            }
        } catch(Exception e){
            label.setText("Error SQL");
        }
    }

Del código previo podemos ver como creamos la consulta dejando el valor de los parámetros username y password como argumentos que posteriormente pasaremos(ver ? en las lineas 4,5) luego posteriormente en las lineas 7 y 8 pasamos los valores por medio de los métodos setText este metodo realiza los escapes adecuados y si agregamos como password el valor x' OR 1='1 al realizar los escapes se convertirá en algo como :

SELECT * FROM usuarios
      WHERE username='x' AND password='x\' OR 1=\'1';

Como conclusión en general debemos de limpiar todos los datos introducidos por el usuario ya que este es el medio por el cual las aplicaciones suelen fallar.

cmdchallenge.com Desafios en el CLI BASH

Hace un tiempo  un amigo @root_w33d me aviso que existia un proyecto conocido como “cmd challenge” (reto en comandos):

Cuando vi el mensaje me puse a revisar el proyecto el cual se me hizo muy interesante, tras una larga noche de bastante café, complete los desafíos:

cmdchallenger
https://cmdchallenge.com

Como no es mi intensión spoolear las respuestas, solo voy a poner las que considere interesantes, cabe mencionar que si revisas el repositorio del proyecto en github puedes ver las respuestas de cada desafió en la URL:

https://github.com/jarv/cmdchallenge/blob/master/challenges.yaml

remove_duplicate_lines

Description:

Print the file faces.txt, but only print the first instance of each
duplicate line, even if the duplicates don't appear next to each other.
Note that order matters so don't sort the lines before removing duplicates.

Consiste en imprimir las lineas de un archivo faces.txt(de 31 lineas) sin imprimir las lineas repetidas manteniendo el orden.

Fue entonces que de inmediato pensé en el comando uniq el cual en teoría elimina las lineas repetidas sin embargo, creo que no funciona del todo correcto cuando existen caracteres especiales, de tal forma que el resultado de:

uniq faces.txt

Nos devuelve 28 lineas lo cual me indicaba que eliminaba 3 lineas.

Cabe mencionar que el resultado esperado consta de 24 lineas, por un momento pensé que quizás el problema es que como las lineas repetidas no estaban continuas pues por eso el uniq no funcionaba bien, asi que pensé en ordenar y luego eliminar los elementos repetidos para ver que pasaba:

sort faces.txt | uniq

lo cual ya me genera las 24 lineas el problema ahora es que al ordenar, se pierde la secuencia, así que opte por ejecutar:

cat -n faces.txt | sort -k2 -u | sort | cut  -f2- 

el cual realiza el siguiente procedimiento:

  • cat -n faces.txt imprime las lineas agregando el numero de linea (algo similar a ejecutar nl faces.txt)
  • sort -k2 -uOrdena eliminando las lineas repetidas(-u) a partir del 2do parametro(-k2)
  • sortSimplemente ordena, regresando el orden del archivo.
  • cut -f2-Corta la salida a partir del parámetro 2.

Cabe mencionar que la respuesta oficial del repositorio es awk '!x[$0]++' faces.txt pero como todos sabemos en bash podemos hacer las cosas de muchas maneras 😉

Por otra parte hoy que escribí el post me doy cuenta que hay nuevos desafíos, así que asta aquí los dejo, ya que me pondré a jugar un ratito, esperando posteriormente escribir nuevas soluciones que me parecieron interesante =).

INVITACIÓN AL IX SIMPOSIUM DE SOFTWARE LIBRE DE LA MIXTECA

simposium_de_la_Mixteca

Hola,  les quiero compartir, que he sido invitado al “IX Simposium de Software Libre de la Mixteca“, dicho evento se realizará en la Universidad Tecnológica de la Mixteca (UTM), en la ciudad de Huajuapan de León Oaxaca, los días 26, 27 y 28 del presente mes.

Mi participación será el día 28,  en una mesa redonda, formada por egresados de esta universidad los cuales tenemos tenemos relación con el Software Libre.

Espero nos vaya muy bien en este evento, posteriormente, por este medio subiré la información del cómo nos fue, así como el servo fotográfico que generé.

 

Para mayor información consultar el sitio oficial: http://www.utm.mx/~simposio/IX/

Introducción a JavaFX

logoFX

Las tecnologías web llegaron para revolucionar a la Ingeniería de Software, ya hace un tiempo las webapps al ser cada vez mas complejas tendieron a dividir la complejidad en 3 partes:

  1. lógica de la aplicación(JavaScript y lenguajes del lado del servidor p.e. php,python, ruby, perl, asp, etc…)
  2. El contenido de la aplicación (El marcado HTML)
  3. El diseño (CSS).

JavaFX es una implementación de esto, diviendo los elementos en:

  1. lógica de la aplicación(Java)
  2. El contenido de la aplicación (El marcado FXML)
  3. El diseño (CSS).

En otras palabras javaFX es un conjunto de librerías que utiliza Java para el manejo de la lógica de la aplicación, FXML para el marcado de contenido(botones, etiquetas, textos de entrada, etc..) y CSS para darle estilo o diseño a estos elementos de contenidos, la siguiente imagen ilustra como se comporta las tecnologías JavaFX en un patrón MVC.

Vista:

La parte de la vista son escenas las cuales el contenido están descritas por archivos con extensión .FXML estos son modificados desde la aplicación JavaFX Scene Builder por otra parte el diseño de la ventana(escena) se realiza mediante archivos de descripción de estilo .CSS

Controlador:

La vista previamente tiene la capacidad de definir un controlador el cual hace referencia a una clase en Java que se va a encargar de controlar la lógica de la ventana.

Modelo:

El modelo es el responsable de la recuperación de datos convirtiéndolos en conceptos significativos para la aplicación, así como su procesamiento, validación, asociación y cualquier otra tarea relativa a la manipulación de dichos datos.

En los siguiente contenido de esta categoría javaFX se va a vamos a explicar mas el funcionamiento de las vistas.

Le recomiendo descargar y revisar el código de la calculadora con JavaFX para que se vaya contextualizando con esta forma de crear aplicaciones.

Calculadora con JavaFX

Vamos a crear la siguiente calculadora:

calculadora_estructura

Ejemplo del funcionamiento

calculadora

Estructura:

Vamos a crear una calculadora, la cual tiene la siguiente estructura:

  • Calculadora.java
  • Controller.java
  • Evaluar.java
  • Vista.fxml
  • Style.css

Vista

La vista de la aplicación es el archivo Vista.fxml el cual describe una ventana divida en dos partes la parte superior contiene el texto de entrada y la parte inferior es una rejilla(GridPane) de 4×4 que contiene los botones (4 renglones de 4 columnas), como se puede ver a continuación.

calculadora_estructura_detalle

Controlador:

El archivo Controller se encarga de “controlar la lógica de la vista”, el cual contiene los métodos:

  • Evaluar: es ejecutada cuando se presiona el Enter en la “#entrada” o el botón con símbolo “=”
  • Borrar: Es ejecutada cuando se presiona el botón con símbolo “c”(clear)
  • OtroBoton: Es ejecutada cuando se presiona cualquier otro botón(0-9*/+-) y simplemente concatena el símbolo contenido en el botón a #entrada..

Evaluar.java se encarga de realizar las operaciones detectando errores de aritmética como la división entre cero.

Código:

Dejo el enlace del código fuente:

https://github.com/fitorec/calculadora_javaFX