Download Notas de clase

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]