Download Notas de clase
Document related concepts
no text concepts found
Transcript
Licenciatura en Ciencias de la Computación, Facultad de Ciencias, UNAM. Computación concurrente (principios de computación distribuida). Profesor: Carlos Zerón Martínez. Ayudante: Manuel Ignacio Castillo López. Notas de clase Concurrencia y sincronización en Python Como sabrá o podrá suponer, Java no es la única plataforma que implementa de forma nativa herramientas para resolver problemas de concurrencia. La mayoría de los lenguajes de programación populares cuenta con al menos implementaciones de hilos y primitivas de sincronización como semáforos. De hecho, los lenguajes orientados a objetos no son ideales para resolver todo tipo de problemas de concurrencia; ya que el uso de memorias compartidas suele ir en contra del concepto de encapsulación; propio de la POO. Veremos algunas de las herramientas que nos ofrece el lenguaje Python para resolver problemas de concurrencia. Python es un lenguaje de programación orientado a objetos (en algunas referencias se dice que es multiparadigma, ya que soporta algunas características de programación funcional e imperativa, pero esta última puede pensarse como parte de Orientación a Objetos, por la cuestión de los static). Es un lenguaje con tipos implícitos e interpretado. El uso de Python es muy amplio: desde lenguaje para principiantes, hasta cómputo científico. Sin embargo, a pesar de su popularidad; en el ámbito empresarial suele optarse por otros lenguajes (aunque tiene presencia y uso). Para trabajar con Python, es necesario contar con un intérprete/compilador (no olvide que siempre es posible compilar un lenguaje interpretado, pero se pierde la portabilidad). Instalación Debian GNU/Linux (y basados en) Python ya viene integrado con Debian ¡Yey! Si hiciera falta instalarlo o actualizar, basta con hacer $ sudo apt-get update $ sudo apt-get install python $ sudo apt-get upgrade Mac OS X Python y viene integrado con Mac OS desde la versión 10.8 Mountain Lion ¡Yey! Si hiciera falta instalarlo o actualizarlo, podemos obtener un instalador en esta liga: https://www.python.org/downloads/mac-osx/ Microsoft Windows A diferencia de los sistemas POSIX-compatibles mencionados anteriormente, Windows no cuenta con una implementación de Python integrada, por lo que estamos obligados a descargar el instalador: https://www.python.org/downloads/windows/ Afortunadamente, el instalador es bastante simple y es lo único que necesitamos para empezar a trabajar. Programación en Python A partir de ahora; salvo que se indique lo contrario, las instrucciones son las mismas independientemente de la plataforma. Ya que tenemos Python instalado, podemos iniciar un intérprete con el comando: python Para declarar una variable, basta con indicar su nombre y para hacer asignaciones, se usa el operador ‘=’ como en la mayoría de los lenguajes: num = 1 Como podrá notar, en Python no se usa ningún carácter para marcar fin de sentencia: basta con introducir un salto de línea para indicar que una sentencia termina. Python cuenta con los siguientes operadores (todos se usan con notación infija). La lista está ordenada de forma que el primer operador que aparece es el que tiene mayor precedencia y el último es el de menor precedencia. Los operadores que aparecen en el mismo renglón, tienen la misma precedencia: Operadores numéricos. 1. ** Exponenciación. 2. + Positivo (unario) - Negativo (unario). 3. * Producto / División % Módulo // Aplica la función piso al resultado de la división (cuando alguno de los operandos es un número racional. Dividir con dos números enteros produce siempre una división entera). 4. + Suma. También es sinónimo de concatenación de cadenas (depende del contexto: si ambos operandos son números o alguno de los dos es una cadena) - Resta. Todos los operadores (binarios) anteriores pueden anteponerse al operador = sin dejar espacio, para hacer una auto operación (num += 1 es equivalente a num = num +1, etc). Operadores sobre registros (variables). 1. ~ Negación de bits. 1. << Corrimiento de bits a la izquierda > > Corrimiento de bits a la derecha. 2. & AND bit a bit. 3. | OR bit a bit ^ XOR bit a bit. Operadores lógico - matemáticos. 1. > Mayor que < Menor que > = Mayor o igual que < = Menor o igual que 2. == Comparación lógica != Diferencia lógica. También soporta el operador <> como sinónimo de !=. 1. = Asignación (esto incluye las auto operaciones y asignación, como +=, /=...) Operadores sobre objetos 1. is Igualdad (comparando sus direcciones de memoria) i s not Diferencia. Operadores de colecciones. 1. in Pertenencia not in Exclusión Operadores lógicos. 1. not Negación or Disyunción a nd Conjunción. Para imprimir texto en la consola, tenemos el método print. A pesar de que en Python las cadenas son objetos, no cuentan con un método o atributo para indicar su tamaño por sí mismas. Para conocer el tamaño de una cadena, debemos pasarsela como argumento al método len: len(“Hola mundo!”) Para acceder a los atributos y métodos de un objeto, usamos el operador ‘. ’, como en JAva o Ruby. “Hola mundo!”.capitalize() Para hacer comentarios en Python tenemos los siguientes: los comentarios de una sola línea, se indican con el símbolo ‘#’; como en bash o en Ruby. # comentario unilinea Y los comentario multilínea, se encierran entre dos pares de tres comillas dobles: “””Comentario multilínea A veces siento que el intérprete ignora todos mis comentarios :( Y aquí termina””” La convención de nombrado y declaración de variables y métodos es la siguiente: ● Las variables llevan únicamente letras (y números) minúsculas en su nombre. ● Si una variable tiene un nombre compuesto por varias palabras, se separan todas estas usando un guión bajo ‘_’. ● Una colección o un método que toma muchos parámetros, prefiere delcararse o llamarse como sigue: lista = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, ] ● Se prefiere identar con espacios y no con tabulaciones. ● Python soporta “multi” importaciones como import sys, os… Pero se prefiere hacer cada importación en una línea diferente. El final de sentencia en Python se delimita con un salto de línea. Para leer texto de la consola, usamos input: leido = input(“Escribe el valor de leido: ”) En Python, los bloques de código se delimitan por los siguientes; hablando en pseudocódigo, si {indicador de bloque de código} BEGIN <instrucciones> END Es un bloque de código, en Python se vería así: <palabra reservada para bloque de código> : <instrucciones> <termina la identación> Es decir, para crear un bloque de código en Python, primero indicamos que tipo de bloque de código queremos definir; por ejemplo, un método def foo(<parámetros>) : O un control de flujo, como puede ser un IF - THEN - ELSE if <booleano> : O else : Cuando queremos usar un if dentro de un else, podemos usar una palabra reservada similar a la de Ruby elsif; en Python: elif if <booleano> : <bloque de código> elif <booleano> : <bloque de código> else : <bloque de código> Entre el elif y el else, podemos agregar tantos elif más como fuesen necesarios. En Python no existe un tipo de datos booleano como tal; sino que, todo aquello que sea diferente de 0 se interpreta como verdadero y 0 se interpreta como falso. Volviendo a los bloques de código de control de flujo, podemos usar los siguientes ciclos: while <booleano> : # whiiile M C A!!! Los for nos permiten iterar sobre estructuras como arreglo, cadenas, listas; entre otros. for <actual> in <lista> : <bloque en el que podemos hacer algo con actual en cada iteración> Podemos generar listas de números para usar con nuestros for (o para cualquier otro propósito) con range(<límite inferior inclusivo>, <límite superior excluyente>). Los límites de range deben ser números enteros. Podemos agregar al final de un ciclo un else para ejecutar un bloque de código cuando la condición de permanencia del ciclo deje de cumplirse (incluyendo el caso en el que nunca se cumpla) <ciclo> <booleano> : <bloque de código> else : <bloque de código para cuando se salga del ciclo o nunca se entre> Note que después de indicar el bloque de código, siempre se colocan dos puntos. Podemos pensar en estos dos puntos como el BEGIN del pseudocódigo (o de Pascal si lo prefiere) o la llave que abre ‘{’ en C o Java; precisamente indican que tras ellos inicia el bloque de código. El cuerpo del bloque de código se diferencia del resto del programa por estar indentado por un tabulador. Cuando termina la identación, el intérprete de Python entiende que el bloque de código ha terminado. Es decir, terminar la identación es equivalente al END del pseudocódigo (o Pascal) o la llave que cierra en C o Java ‘}’. Así, algunos ejemplos de bloques de código anidados son los siguientes (tome en cuenta que es posible añadir tantos bloques como sea necesario): def foo(repetir) : for num in range(0, 10) : aux = repetir print(“Va el for con ” +str(num)) while aux > 0 : print(“Aux vale ” +str(aux)) aux -= 1 else : print(“Sali del while”) else : print(“Sali del for”) Note que al igual que en Ruby, debemos instanciar una cadena a partir de una variable con un tipo de datos diferente para poder concatenarla en una cadena. Volviendo brevemente a los ciclos, podemos manipular sus iteraciones con las siguientes palabras reservadas: ● break - Termina el ciclo más inmediato for num in range(0, 10) : aux = repetir print(“Va el for con ” +str(num)) while aux > 0 : print(“Aux vale ” +str(aux)) aux -= 1 if aux == 5 print(“Si aux alcanza el valor 5 termino abruptamente”) break print(“Sali del while. Break no me afecta en absoluto :)”) ● continue - Se salta una iteración del ciclo más inmediato. for num in range(0, 10) : aux = repetir print(“Va el for con ” +str(num)) while aux > 0 : if aux % 2 print(“Me salto todos los pares”) aux -= 1 continue print(“Aux vale ” +str(aux)) aux -= 1 print(“Sali del while.”) Finalmente, el bloque de código más general con el que nos podemos encontrar en Python es una clase. En Python, salvo que se “declaren”, los atributos de clase son privados. El constructor se define de la siguiente manera: se escribe init rodeado de dos pares de guiones bajos. El primer atributo es self y luego podemos poner tantos como nos sea necesario. Para declarar los “atributos privados”, usamos el mismo nombre de parámetro que como atributo de self. Dentro de una clase podemos definir tantos métodos como queramos con cualesquiera nombres arbitrarios. self tiene la misma semántica en Python que this tiene en Java; es decir, es una referencia en un objeto a sí mismo. Así, una clase de ejemplo puede ser la siguiente: class foo : # un atributo “público” attr = 0 # método constructor def __init__(self, privado) : self.privado = privado “””un método arbitrario que representa el objeto como cadena; similar al toString de Java””” def muestra() : return “Attr vale ” +str(attr) +” y privado ” +str(self.privado) Para instanciar un objeto de la clase, podemos hacer lo siguiente: foo(5) También podríamos almacenarlo en una variable. Para indicar que una clase hereda de otra, se pone el nombre de la superclase entre paréntesis antes de los dos puntos que indican el inicio de la clase: class foo (bar) : Python soporta herencia múltiple, por lo que dentro de los paréntesis podemos indicar el nombre de varias clases separadas por comas. También es posible sobrecargar métodos, distinguiendo cada sobrecarga por el número de parámetros que recibe. Para instanciar un objeto en Python, simplemente hacemos algo como lo siguiente: var = foo(<parámetros de algún constructor>) Interfaz no responsiva Quizá recuerde el ejemplo al inicio del curso de la interfaz no responsiva; y quizas no lo recuerde. Vamos a hacer el mismo ejemplo en Python para introducirnos tanto a las herramientas de sincronización que nos ofrece, como a la creación de interfaces gráficas en Python. Python define un amplio API, que entre otras cosas contiene la biblioteca Tkinter. Tkinter es la biblioteca por default para construir GUIs con Python. Vamos a crear una interfaz que podría resultar muy familiar: un botón de inicio y una barra de progreso que se llena mientras el programa hace una cuenta ascendente hast un límite definido: import Tkinter count_limit = 5000 c_width = 300 c_height = 25 top = Tkinter.Tk() def count(): for counter in range(0, count_limit): canvas.create_rectangle(0, 0, c_width *counter /count_limit, c_height, fill='#0f0') canvas = Tkinter.Canvas(top, bg="white", height = c_height, width = c_width) canvas.pack() startb = Tkinter.Button(top, text = "Iniciar", command = count) startb.pack() top.mainloop() Si corremos el programa con $ python interfaz_no_responsiva.py Y damos clic en el botón “Iniciar” de la ventana que aparece… ¿qué pasa? El programa se congela y la barra de progreso no se actualiza sino hasta que la cuenta termina… Ya hemos estudiado cómo funcionan las interfaces gráficas en Java, por lo que si seguimos la misma estrategia podríamos resolver el problema de la interfaz no responsiva. La solución consistía en agregar un hilo que se encarga de refrescar la interfaz gráfica. En Python tenemos la biblioteca threading, que define hilos y operaciones para con ellos de una forma muy similar a como lo hace Java: las operaciones y su semántica es básicamente la misma. Para crear un hilo, basta con instanciarlo indicando la función que deberá de ejecutar, de manera análoga a pasarle un Runnable a un Thread de Java. Así, la interfaz se limita a poner el hilo a trabajar. import Tkinter import threading count_limit = 5000 c_width = 300 c_height = 25 thr = None top = Tkinter.Tk() def worker(): for counter in range(0, count_limit): canvas.create_rectangle(0, 0, c_width c_height, fill='#0f0') *counter /count_limit, def count(): thr = threading.Thread(target=worker) thr.start() canvas = Tkinter.Canvas(top, bg="white", height = c_height, width = c_width) canvas.pack() startb = Tkinter.Button(top, text = "Iniciar", command = count) startb.pack() top.mainloop() La próxima vez que ejecutemos el programa, la barra de progreso cambiará con el incremento de la cuenta. Ahora bien, python no requiere de una VM de ninguna naturaleza a diferencia de Java y el entorno de ejecución de un programa de Python es independiente a otro, a diferencia del de Java; donde todos los programas pueden compartir los servicios de la misma máquina virtual. Por esta razón, en Python tiene sentido hablar de procesos diferentes además de hilos. Desde un programa de Python podemos instanciar otros procesos y darles tareas a ejecutar (similar a usar fork en C; que veremos más adelante). Además de threading, Python también incluye en sus bibliotecas estándar multiprocessing. multiprocessing define un API análoga a la de threading, pero que nos permite crear y manipular procesos independientes, en lugar de solo hilos. Ahora bien, el problema de resolver o implementar problemas de concurrencia con procesos y no hilos, es que la administración de memoria se hace más difícil. Los modelos de memoria y argumentos por parte de los autores de la importancia de cuidar las memorias compartidas entre procesos, es un problema real. Python define una capa de abstracción muy elevada y a diferencia de C; aunque ambos son lenguajes de alto nivel, no nos permite manipular un espacio de memoria tan a nuestra voluntad; empezando por la carencia de apuntadores. Las únicas formas de compartir memoria en Python es usando las clases Value y Array, definidas en la biblioteca multiprocessing. Más adelante veremos como usar mmap en C y C++ para definir espacios de memoria compartida que podemos usar a nuestra completa voluntad; que desde que los sistemas operativos se implementan con lenguajes orientados a objetos, han creado vulnerabilidades de seguridad difíciles de identificar (se recomienda leer sobre windows atoms si esto le llama la atención). Así, si queremos atacar el famoso problema de encontrar primos, podemos usar dos trabajos para realizar el trabajo más rápido que con 1 de la siguiente forma: import sys from multiprocessing import Process, Value, Array if(len(sys.argv) < 2): print('ERROR\nA number must be given as a console parameter') sys.exit() num = int(sys.argv[1]) res = Array('i', range(num)); index = Value('i', 0); def search(starting, ending, arr, ind): for current in range(starting, ending): prime = True for i in range(2, current): if(current %i == 0): prime = False break if(prime): arr[ind.value] = current ind.value = ind.value +1 proc1 = Process(target = search, args=(2, num /2, res, index,)) proc2 = Process(target = search, args=(num /2, num, res, index,)) proc1.start() proc2.start() proc1.join() proc2.join() sorted(res[:]) print res[:index.value] El programa concurrente expuesto tiene un problema, ¿que pasa si el proceso 1 intenta escribir la dirección arr[ind.value] al mismo tiempo que el proceso 2? Ocurrirá una condición de competencia y perderemos un valor primo de la lista. Para esto, podemos usar alguna herramienta en la misma biblioteca multiprocessing, como Lock; un candado, para asegurar exclusión mutua en dicha sección crítica. Python nos ofrece varias primitivas de sincronización definidas en la biblioteca estándar asyncio, que define: Candados, Semáforos y una clase Condition; que podemos usar para implementar monitores como hicimos en Java. import sys from multiprocessing import Process, Value, Array, Lock, cpu_count if(len(sys.argv) < 2): print('ERROR\nA number must be given as a console parameter') sys.exit() num = int(sys.argv[1]) res = Array('i', range(num)); index = Value('i', 0); lock = Lock() cpu_num = cpu_count() def search(starting, ending, arr, ind, l): for current in range(starting, ending): prime = True for i in range(2, current): if(current %i == 0): prime = False break if(prime): l.acquire() arr[ind.value] = current ind.value = ind.value +1 l.release() print cpu_num proc1 = Process(target = search, args=(2, num /2, res, index, lock,)) proc2 = Process(target = search, args=(num /2, num, res, index, lock,)) proc1.start() proc2.start() proc1.join() proc2.join() sorted(res[:]) print res[:index.value]