Concurrencia y Distribuciónformella.webs.uvigo.es/doc/cdg18/cdi.pdfprofesorado (prácticas)...

Concurrencia y Distribución2018/2019

Tercero, Grado

Dr. Arno Formella

Departamento de InformáticaEscola Superior de Enxeñaría Informática

Universidade de Vigo

18/19

CDI Dr. Arno Formella 1 / 278

profesorado (teoría)

Profesor: Arno FORMELLA

Web: http://formella.webs.uvigo.es

Correo: [email protected]ías Ma: 09.30–13.30 y 16.30–18.30Despacho 309

usamos: FAITIC/TEMA

Observa: hay cambios respecto a la guía docente.


http://formella.webs.uvigo.es

http://faitic.uvigo.es

profesorado (prácticas)

Profesora: Anália GARCÍA LOURENÇO

Correo: [email protected]ías Me: 10.00–12.00, Ju: 10.00–13.00, y Ve: 10.00–11.00Despacho 411

Profesor: Hugo LÓPEZ FERNÁNDEZ

Correo: [email protected]ías Lu: 16:30–18:30Despacho 306

Profesor: David OLIVIERI CECCHI

Correo: [email protected]ías Me: 10.00–14.00 y 16.00–18.00Despacho 305


tutorías

Cambios puntuales de tutorías via aviso web(yo en mi página principal, y/o aviso via FaiTIC)

Idiomas: Galego, Castellano, English, Deutsch

Las transparencias serán en castellano con pinceladas en inglés(sobre todo todos los programas).


horas de dedicación (planificación según guía)

pres. no-pres. sumaActividades introductorias 0.50 – 0.50Sesión magistral 18.00 9.00 27.00Estudios/actividades previos – 17.00 17.00Prácticas en aulas de informática 26.00 26.00 52.00Resolución de problemas y/o exercicios 1.50 19.50 21.00Presentacións/exposicións – 1.75 1.75Tutoría en grupo 1.25 1.25 2.50Pruebas de respuesta corta 1.00 – 1.00Pruebas de respuesta larga 2.00 – 2.00Informes/memorias de prácticas – 12.00 12.00Probas prácticas 1.00 – 1.00Resolución de problemas y/o exercicios – 12.00 12.00Otras 0.25 – 0.25Suma 51.50 98.50 150.00


horas presenciales

Teoría: los lunes (13 sesiones), 09.00-10:30 horas,Aula 2.2

Prácticas: 6 grupos, Lab. 31B, 13 sesionesa partir del lunes 21/01/20192 sem. Anália, 6 sem. Hugo, 5 sem. David

Están organizados los grupos de prácticas.


horas presenciales


horas en aula presenciales

21.02. actividad introductoria (más un poco chicha)

12 sesiones magistrales + pruebas de respuestas corta

20.05. prueba final (10:00-14:00, 2++ horas)

03.07. prueba terminal (09:00-12:00)

13 sesiones prácticas con entregas de trabajos en clase y algunau otra prueba corta

en concreto: previsto pruebas cortas (que cubren las prácticas) el25.03. y el 29.04.


horas de trabajo (este curso)

Actividad pres. no-pres. horas (guía)Actividades introductorias 0.5 T – 0.5 (0.5)Sesión magistral 18.0 T 6.5 24.5 (27.0)Estudios/actividades previos – 6.5 6.5 (17.0)Resolución de problemas/exercicios – T 13.0 13.0 (21.0)Tutoría en grupo 2.0 – 2.0 (2.5)Pruebas de respuesta corta 3.0 T – 3.0 (1.0)Pruebas de respuesta larga 2.0 T – 2.0 (2.0)Prácticas en aulas de informática 24.0 P 26.0 50.0 (52.0)Informes/memorias de prácticas – P 19.5 19.5 (12.0)Probas prácticas 1.0 P 1.0 (1.0)Presentacións/exposicións – P 1.0 1.0 (1.7)Resolución de problemas y/o exercicios – 13.0 13.0 (12.0)Otras – 5.0 5.0 (0.3)Suma 50.5 90.5 141.0segunda oportunidad +9.0 +9.0 150.0


horas del profesor (yo, aproximado, optimista)

244 horas anuales de docencia/2 fracción para CDI

122 −19.5 horas presenciales teoría102.5 −19.5 horas preparación clases teoría

83 −3 horas preparación/gestión clases prácticas80 −104/4−4 horas y corrección exámenes teoría50 /104/16 media por estudiante por semana

0.03 horas1.8 minutos por estudiante por semana


prerrequisitos

matemáticas

algoritmos y estructuras de datos

todo sobre programación

arquitectura de computadoras

redes

sistemas operativos

lenguajes de programación (Java, C++)


contexto en el plan de estudio


evaluación continua

(P1) preguntas cortas[ A4 A5 A7 A8 A12 A13 A14 A15 A16 A19 A20 A22 A25 A26 A27 A28 A30 A31 A33 A35 A36 B1 B2 B5 B6 B8 B10 ]

(P2) preguntas largas (hay que aprobar ≥ 4)[ A4 A5 A7 A8 A12 A13 A14 A15 A16 A19 A20 A22 A25 A26 A27 A28 A30 A31 A33 A35 A36 B1 B2 B5 B6 B8 B10 ]

(P3) informes[ A4 A5 A7 A8 A12 A13 A14 A15 A16 A19 A20 A22 A25 A26 A27 A28 A30 A31 A33 A35 A36 B1 B2 B3 B5 B6 B8 B10 ]

(P4) programación (hay que aprobar ≥ 4)[ A4 A5 A7 A8 A12 A13 A14 A15 A16 A19 A20 A22 A25 A26 A27 A28 A30 A31 A33 A35 A36 B1 B2 B5 B6 B8 B10 ]

(P5) análisis[ A4 A5 A7 A8 A12 A13 A14 A15 A16 A19 A20 A22 A25 A26 A27 A28 A30 A31 A33 A35 A36 B1 B2 B5 B6 B8 B10 ]

(P6) presentaciones[ A4 A5 A7 A8 A12 A13 A14 A15 A16 A19 A20 A22 A25 A26 A27 A28 A30 A31 A33 A35 A36 B1 B2 B3 B5 B6 B8 B10 ]

min(10,0.1P1+0.4P2+0.25P3+0.25P4+0.05P5+0.05P6)≥ 5

pero P2 ≥ 4 y P4 ≥ 4


evaluación no-asistentes

examen (20.05.) de 3.5 horas (entre 10:00-14:00) que cubre todoel contenido de la asignatura (teoría y prácticas)

y/o examen (03.07.) de 3.0 horas (entre 9:00-12:00) que cubretodo el contenido de la asignatura (teoría y prácticas)

un alumno o bien se autodeclara no-asistente o lo muestra porno asistir a por lo menos 80% de las actividades presenciales(como mucho se puede faltar a 9 horas de las 19.5+26=45.5horas de presencialidad principal)

control mediante firmas en clase y/o entregas en FaiTIC


vos y nos

¿Quién soy yo?

página web de docenciahttp://formella.webs.uvigo.es

página web de investigaciónhttp://lia.esei.uvigo.es


http://formella.webs.uvigo.es

http://lia.esei.uvigo.es

al espacio...participación en 4 satélites:

XaTcobeo, 14/02/2012

HumSAT, 21/11/2013

Serpens, 20/08–17/09/2015

Lume, 27/12/2018


HumSAT software evolution (lines of code)


reconocimiento de formas

investigación y desarrollo en el ámbito de reconocimiento deformas

reconocer formasaprender formas

uso en aplicaciones deeducación infantil,educación matemática,interfaces amigablesinterfaces para motores de búsqueda

miramos un poco el prototipo Shapewiz...


trazado de rayos

descripción de un modelado de una escena(objecto, colores, texturas, luces, etc.)

simulación de una cámara digital

obtención de una imágen foto-realista


trazado de rayos


simulación de partículas

descripción de un modelado de partículas(tamaño, propiedades pre/pos-colisión, otros objetos, etc.)

simulación según modelado física(p.ej. con gravitación)

simulación basado en eventos discretos

o simulación basado en monte carlo

estudio de efectos en materiales granulares y gases


pemd


pemd

pemd_g -Ri 0.5 -Ra 3.0 -c 1000000 -en 0.75 -icdi.pemd -g 2 -pn 343 -ps 343


procesamiento de imágenesbio-nanotubos (original)


procesamiento de imágenesbio-nanotubos (menos ruido)


procesamiento de imágenesbio-nanotubos (más contraste)


procesamiento de imágenesbio-nanotubos (binarizado)


procesamiento de imágenesbio-nanotubos (esqueleto)


procesamiento de imágenesbio-nanotubos (original)


posible colaboración, ejemplos durante el curso

Todas estas aplicaciones se usarán como vehículos de ejemplopara mostrar aspectos de concurrencia y distribución.

Quien quiere colaborar, por ejemplo en su TFG, puede ponerseen contacto conmigo.


contenido (optimista)

Tema ContenidoSistemas concurrentes ydistribuidos

Concepto de la programación concu-rrente y distribuida, Introducción al mo-delado de sistemas concurrentes y dis-tribuidos, Arquitecturas hardware parala concurrencia y distribución, Herra-mientas para el desarrollo de aplicacio-nes concurrentes y distribuidos

Procesos Concepto de procesos, Planificador,Atomicitad y exclusión mutua, Concu-rrencia transactional, Reloj y estadodistribuido


contenido (optimista)

Tema ContenidoSincronización y comuni-cación

Sincronización y comunicación en sis-temas concurrentes y distribuidos, Sin-cronización y comunicación a nivel bajoy alto, Seguridad y vivacidad en siste-mas concurrentes y distribuidos

Herramientas de progra-mación y desarrollo deaplicaciones

Programación concurrente y distribuidacon JAVA (y C/C++), Patrones de di-seño para el desarrollo de aplicacionesconcurrentes y distribuidos, Herramien-tas y metodologías de diseño, verifica-ción y depuración de aplicaciones con-currentes y distribuidos


Nota

Prácticamente todas las asignaturas optativas en uno u otro aspectorequieren del concepto de concurrencia y distribución en sistemasmodernos para lograr sus objetivos específicos.


documento de transparencias

Este documento crecerá durante el curso,ojo, no necesariamente solamente al final.

Habrá más documentos (capítulos de libros, manuales, etc.)con que trabajar durante el curso.

Los ejemplos de programas y algoritmos serán en inglés.

Las transparencias no están (posiblemente/probablemente)ni correctos ni completos.

Las transparencias no son suficientes (incluso çhapadas") paraaprobar la asignatura.


competencias, un intento...

Competencias Tipo Cod.Que os estudantes demostren posuír e comprender coñece-mentos nunha área de estudo que parte da base da educa-ción secundaria xeral e adoita atoparse a un nivel que, maliase apoiar en libros de texto avanzados, inclúe tamén algúnsaspectos que implican coñecementos procedentes da van-garda do seu campo de estudo.

facer CB1

Que os estudantes saiban aplicar os seus coñecementos óseu traballo ou vocación dunha forma profesional e posúanas competencias que adoitan demostrarse por medio da ela-boración e defensa de argumentos e a resolución de proble-mas dentro da súa área de estudo.

facer CB2

Que os estudantes teñan a capacidade de reunir e interpre-tar datos relevantes (normalmente dentro da súa área deestudo) para emitir xuízos que inclúan unha reflexión sobretemas relevantes de índole social, científica ou ética.

facer CB3

Que os estudantes desenvolvan aquelas habilidades deaprendizaxe necesarias para emprender estudos posterio-res cun alto grao de autonomía.

facer CB4



Competencias Tipo Cod.Capacidade para concebir, redactar, organizar, planificar,desenvolver e asinar proxectos no ámbito da enxeñaría eninformática que teñan por obxecto, de acordo cos coñece-mentos adquiridos , a concepción, o desenvolvemento ou aexplotación de sistemas, servizos e aplicacións informáticas.

facer CG1

Capacidade para dirixir as actividades obxecto dos proxec-tos do ámbito da informática de acordo cos coñecementosadquiridos.

saber CG2

Capacidade para deseñar, desenvolver, avaliar e asegurara accesibilidade, ergonomía, usabilidade e seguridade dossistemas, servizos e aplicacións informáticas, así como dainformación que xestionan.

facer CG3

Capacidade para definir, avaliar e seleccionar plataformashardware e software para o desenvolvemento e a execuciónde sistemas, servizos e aplicacións informáticas, de acordocos coñecementos adquiridos.

facer CG4



Competencias Tipo Cod.Capacidade para concebir, desenvolver e manter sistemas,servizos e aplicacións informáticas empregando os métodosda enxeñería de software como instrumento para o asegura-mento de sua calidade, de acordo cos coñecementos adqui-ridos.

facer CG5

Capacidad para concebir e desenvolver sistemas ou arqui-tecturas informáticas centralizadas ou distribuidas integran-do hardware, software e redes de acordo cos coñecementosadquiridos.

facer CG6

Capacidade para coñecer, comprender e aplicar a lexis-lación necesaria durante o desenvolvemento da profesiónde Enxeñeiro Técnico en Informática e manexar especifica-cións, regulamentos e normas de obrigado cumprimento.

saber CG7

Coñecemento das materias básicas e tecnoloxías, que ca-paciten para a aprendizaxe e desenvolvemento de novosmétodos e tecnoloxías, así como as que lles doten dunhagran versatilidade para adaptarse a novas situacións.

facer CG8



Competencias Tipo Cod.Capacidade para resolver problemas con iniciativa, toma dedecisións, autonomía e creatividade. Capacidade para sa-ber comunicar e transmitir os coñecementos, habilidades edestrezas da profesión de Enxeñeiro Técnico en Informática.

saber CG9

Capacidade para analizar e valorar o impacto social e me-dioambiental das solucións técnicas, comprendendo a res-ponsabilidade ética e profesional da actividade de EnxeñeiroTécnico en Informática.

saber CG11

Coñecemento e aplicación de elementos básicos de econo-mía e de xestión de recursos humáns, organización e pla-nificación de proxectos, así como a lexislación, regulacióne normalización no ámbito dos proxectos informáticos, deacordo cos coñecementos adquiridos.

saber CG12



Competencias Tipo Cod.Coñecementos básicos sobre o uso e programación dos or-denadores, sistemas operativos, bases de datos e progra-mas informáticos con aplicación na enxeñería

facer CE4

Coñecemento da estrutura, organización, funcionamento einterconexión dos sistemas informáticos, os fundamentos dasúa programación, e a súa aplicación para a resolución deproblemas propios da enxeñería

saber CE5

Capacidade para deseñar, desenvolver, seleccionar e ava-liar aplicacións e sistemas informáticos, asegurando a súafiabilidade, seguridade e calidade, conforme aos principioséticos e á lexislación e normativa vixente

saber CE7



Competencias Tipo Cod.Capacidade para planificar, concibir, despregar e dirixir pro-xectos, servizos e sistemas informáticos en tódolos ámbitos,liderando a súa posta en marcha e mellora continua e valo-rando o seu impacto económico e social

saber CE8

Coñecemento e aplicación dos procedementos algorítmicosbásicos das tecnoloxías informáticas para deseñar soluciónsa problemas, analizando a idoneidade e complexidade dosalgoritmos propostos

facer CE12



Competencias Tipo Cod.Coñecemento, deseño e utilización de forma eficiente dostipos e estruturas de datos máis axeitados á resolución dunproblema

facer CE13

Capacidade para analizar, deseñar, construír e manter apli-cacións de forma robusta, segura e eficiente, elixindo o pa-radigma e as linguaxes de programación máis axeitadas

facer CE14

Capacidade de coñecer, comprender e avaliar a estrutura earquitectura dos computadores, así como os compoñentesbásicos que os conforman

facer CE15



Competencias Tipo Cod.Coñecemento das características, funcionalidades e estru-tura dos Sistemas Operativos e deseñar e implementar apli-cacións baseadas nos seus servizos

saber CE16

Coñecemento e aplicación das ferramentas necesarias parao almacenamento, procesamento e acceso aos Sistemas deinformación, incluídos os baseados en web

saber CE19

Coñecemento e aplicación dos principios fundamentais etécnicas básicas da programación paralela, concurrente, dis-tribuída e de tempo real

facer CE20



Competencias Tipo Cod.Coñecemento e aplicación dos principios, metodoloxías e ci-clos de vida da enxeñería de software

saber CE22

Capacidade para desenvolver, manter e avaliar servizos esistemas software que satisfagan todos os requisitos dousuario e se comporten de forma fiable e eficiente, sexanasequibles de desenvolver e manter e cumpran normas decalidade, aplicando as teorías, principios, métodos e prácti-cas da Enxeñería do Software

saber CE25



Competencias Tipo Cod.Capacidade para valorar as necesidades do cliente e espe-cificar os requisitos software para satisfacer estas necesida-des, reconciliando obxectivos en conflito mediante a procurade compromisos aceptables dentro das limitacións deriva-das do custo, do tempo, da existencia de sistemas xa desen-volvidos e das propias organizacións

saber CE26

Capacidade de dar solución a problemas de integración enfunción das estratexias, estándares e tecnoloxías dispoñi-bles

saber CE27

Capacidade de identificar e analizar problemas e deseñar,desenvolver, implementar, verificar e documentar soluciónssoftware sobre a base dun coñecemento axeitado das teo-rías, modelos e técnicas actuais

facer CE28



Competencias Tipo Cod.Capacidade para deseñar solucións apropiadas nun ou máisdominios de aplicación utilizando métodos da enxeñería dosoftware que integren aspectos éticos, sociais, legais e eco-nómicos

saber CE30

Capacidade para comprender a contorna dunha organiza-ción e as súas necesidades no ámbito das tecnoloxías dainformación e as comunicacións

saber CE31

Capacidade para empregar metodoloxías centradas nousuario e a organización para o desenvolvemento, avaliacióne xestión de aplicacións e sistemas baseados en tecnoloxíasda información que aseguren a accesibilidade, ergonomía eusabilidade dos sistemas

saber CE33



Competencias Tipo Cod.Capacidade para seleccionar, despregar, integrar e xestio-nar sistemas de información que satisfagan as necesidadesda organización, cos criterios de custo e calidade identifica-dos

saber CE35

Capacidade de concibir sistemas, aplicacións e servizosbaseados en tecnoloxías de rede, incluíndo Internet, web,comercio electrónico, multimedia, servizos interactivos ecomputación móbil

saber CE36



Competencias Tipo Cod.Capacidade de análise, síntese e avaliación ser CT1Capacidade de organización e planificación ser CT2Comunicación oral e escrita na lingua nativa ser CT3Capacidade de abstracción: capacidade de crear e utilizarmodelos que reflictan situacións reais

ser CT5

Capacidade de deseñar e realizar experimentos sinxelos eanalizar e interpretar os seus resultados

ser CT6

Capacidade de buscar, relacionar e estruturar informaciónproveniente de diversas fontes e de integrar ideas e coñece-mentos

ser CT7

Resolución de problemas ser CT8



Competencias Tipo Cod.Capacidade de tomar decisións ser CT9Capacidade para argumentar e xustificar loxicamente as de-cisións tomadas e as opinións

ser CT10

Capacidade de actuar autonomamente ser CT11Capacidade de traballar en situacións de falta de informacióne/ou baixo presión

ser CT12

Capacidade de relación interpersoal ser CT15Razoamento crítico ser CT16Aprendizaxe autónoma ser CT18Creatividade ser CT20Ter iniciativa e ser resolutivo ser CT22Ter motivación pola calidade e a mellora continua ser CT24


Bibliografía (de interés) I

1 J.T. Palma Méndez, M.C. Garrido Carrera, F. Sánchez Figueroa,A. Quesada Arencibia. Programación Concurrente. Thomson,ISBN 84-9732-184-7, 2003.

2 G. Coulouris, J. Dollimore, T. Kindberg. Sistemas Distribuidos,Conceptos y Diseño. Addison Wesley, ISBN 84-7829-049-4,2001.

3 M.L. Liu. Computación Distribuida Peason/Addison Wesley, ISBN84-7829-066-4, 2004.

4 C. Breshears. The Art of Concurrency. O’Reilly, ISBN978-0-596-52153-0, 2009.


Bibliografía (de interés) II

5 M. Herlihy, N. Shavit. The Art of multiprocessor programming.Elsevier-Morgan Kaufmann Publishers, ISBN 978-0-12-370591-4,2008 (978-0-12-397337-5, 2012 revised edition).

6 D. Schmidt, M. Stal, H. Rohnert, F. Buschmann. Pattern-OrientedSoftware Architecture, Pattern for Concurrent and NetworkedObjects. John Wiley & Sons, ISBN 0-471-60695-2, 2000.


Bibliografía (Java)

1 K. Arnold et.al. The Java Programming Language.Addison-Wesley, 3rd Edition, ISBN 0-201-70433-1, 2000.

2 B. Eckel. Piensa en Java. Prentice Hall, 2002.3 D. Lea. Programación Concurrente en Java. Addison-Wesley,

ISBN 84-7829-038-9, 2001.

cualquier libro sobre Java que cubre programación con hilos


Bibliografía (on–line)

Apuntes de esta asignatura:http://formella.webs.uvigo.es/doc/cdg18/index.html

Concurrency JSR-166 Interest Site (antiguado)http://gee.cs.oswego.edu/dl/concurrency-interest/

index.html

El paquete de Doug Lea que funciona con Java 1.4 (antiguado)http://formella.webs.uvigo.es/doc/concurrent.tar.gz

(.tar.gz [502749 Byte])

The Java memory model (antiguado)http://www.cs.umd.edu/%7Epugh/java/memoryModel


http://formella.webs.uvigo.es/doc/cdg18/index.html

http://gee.cs.oswego.edu/dl/concurrency-interest/index.html

http://gee.cs.oswego.edu/dl/concurrency-interest/index.html

http://formella.webs.uvigo.es/doc/concurrent.tar.gz

http://www.cs.umd.edu/%7Epugh/java/memoryModel

introducción

Existen diversas definiciones de los términos en la literatura:

programación concurrente

programación paralela

programación distribuida


definición

Una posible distinción (según mi opinión) es:

la programación concurrente se dedica más a desarrollar yaplicar conceptos para el uso de recursos en paralelo (desde elpunto de vista de varios actores)

la programación en paralelo se dedica más a solucionar yanalizar problemas bajo el concepto del uso de recursos enparalelo (desde el punto de vista de un sólo actor)


definición

Otra posibilidad de separar los términos es:

un programa concurrente define las acciones que se puedenejecutar simultaneamente, es decir, están en progreso

un programa paralelo es un programa concurrente diseñado deser ejecutado en hardware paralelo

un programa distribuido es un programa paralelo diseñado de serejecutado en hardware distribuido, es decir, donde variosprocesadores no tengan memoria compartida, tienen queintercambiar la información mediante de transmisión demensajes/datos.


intuición

Intuitivamente, todos tenemos una idea básica de lo que significa elconcepto de concurrencia.


ordenamos

©http://kartenspiel.org/knack-kartenspiel/


ordenamos

Formamos ordenadores.

Cada uno tiene procesadores que se pueden comunicar entreellos (sabeis hablar y escuchar...).

Cada procesador tiene un neipe.

Queremos que al final la barraja esté ordenada.

¿Cómo procedemos?

¿Cuáles son los aspectos/problemas a tratar?

¿Cómo lo trasladamos a un entorno programable?


ordenamos

Creative Common: Sönke Kraft aka Arnulf zu Linden


ordenamos

Creative Common: Sönke Kraft aka Arnulf zu Linden


desafios

¿Con qué desafios nos enfrentamos?

selección del algoritmo(RAE: Conjunto ordenado (?!) y finito (?!) de operaciones quepermite hallar la solución de un problema.)

división del trabajo

distribución de los datos

sincronización necesaria

comunicación de los datos entre participantes

comunicación de los resultados


desafios

Y también con:

medición de características

depuración del programa

(fiabilidad de los componentes)

(fiabilidad de la comunicación)

(detección de la terminación)

Programar aplicaciones concurrentes puede ser divertido y frustante ala vez :-)


ordenación

La ordenación de datos es una tarea muy usada en muchasaplicaciones.

¿Cómo se ordena de forma concurrente (y eficiente)?

En general no es nada trivial desarrollar algoritmos deordenación paralelos, eficientes, escalables, etc.

Miramos un caso especial (counting sort):ordenación de muchos datos (aquí enteros positivos) en ciertorango no demasiado grande, pero más grande que el número deprocesos disponibles.

Es parecido como hemos visto para ordenar los neipes.


ordenación

parallel counting sort (ordenación contando en paralelo)(mira: counting sort, radix sort, bucket sort)

implementamos en C++ con OpenMP

medimos el tiempo de ejecución en diferentes sistemas

realizamos primero todo lo necesario alrededor, luego el propioalgoritmo


comprobación de la ordenación

// Checks whether data is sorted.// Note the standard library provides such a function,// but we do our own...

bool IsSorted(const std::vector<unsigned>& data

) {const unsigned data_size(data.size());bool sorted(true);

#pragma omp parallel \default(none) \shared(data) \shared(sorted){

#pragma omp for schedule(static)for(unsigned i=1; i<data_size; ++i) {if(data[i-1]>data[i]) sorted=false;

}}return sorted;

}


medición de tiempo de ejecución (ejemplo en C++)

// Shortcut for complex timer type.typedef std::chrono::high_resolution_clock::time_point

TimePoint;

// Starts our timer clock.TimePoint StartClock() {return std::chrono::high_resolution_clock::now();

}

// Stops our timer clock. Returns the elapsed time.double StopClock(TimePoint start

) {const auto duration(

std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now()-start

));return static_cast<double>(duration.count());

}


bucle principal de medición

std::vector<unsigned> V(nValues);MakeRandom(V,minValue,maxValue);std::vector<unsigned> W(nValues);TimePoint start;

// Measure the runtime of our counting sort algorithm// in a measuring loop to smooth measuring fluctuations.

double time_countingsort(0.0);for(unsigned i(0); i<measuringLoops; ++i) {W=V;start=StartClock();CountingSort(W);time_countingsort+=StopClock(start);if(!IsSorted(W)) std::cerr<<"Error: not sorted?\n";

}


lo que falta...

paso de parámetros via línea de comando

ayuda y información de copyright

inicialización de los datos con valores aleatorios

visualización de los datos (uso durante depuración)

miramos estas funciones y la implementación del propioalgoritmo directamente en el fichero de código


un breve análisis del tiempo de ejecución

acordamos:n número de datos, v rango de valores, p número de procesosel algoritmo usa 8 bucles:

1 copia y min/max-búsqueda (en paralelo): O(n/p)2 inicialización de tamaños (en paralelo): O(v/p)3 contar ocurrencias (en paralelo): O(n/p)4 cálculo de tamaños (en paralelo): O(v/p ∗p) = O(v)5 prefix-sum para tamaños (secuencial): O(v)6 inicialización de índices (en paralelo): O(v/p)7 prefix-sum para índices (en paralelo): O(v/p ∗p) = O(v)8 copia de datos (en paralelo): O(n/p)

entonces tiempo de ejecución: O(n/p+ v)


un breve análisis del uso de memoria

estructuras de datos principales:1 array de copia de dato: O(n)2 array para tamaños: O(v)3 arrays para contadores/índices: O(v ∗p)

entonces uso de memoria: O(n+ v ∗p)


herramientas de producción

compilación para depuración:

g++ -std=gnu++11 -DDEBUG Sort.cpp -fopenmp -o cdi_sort_g

compilación para pruebas:

g++ -std=gnu++11 -O3 -DNDEBUG Sort.cpp \-fopenmp -o cdi_sort

visualización de resultados de medición con gnuplot:

plot "sort_hp.gdt" u 1:2 w l lw 2 t "count", \"sort_hp.gdt" u 1:3 w l lw 2 t "std"

todos estos comandos agrupamos en scripts correspondientes


herramientas de producción

script para ejecución con parámetros en línea de comando:

./cdi_sort -i 0 -x 499 -n 100000000 -p 1 > sort.gdt

./cdi_sort -i 0 -x 499 -n 100000000 -p 2 >> sort.gdt












resultados de medición

datos tal como el programa escribe el fichero:

1 532 4130.82 434.2 2543.23 407.4 20804 285 1859.65 333.2 2031.88 313.2 197610 312.2 2012.816 311 1952.420 307.2 198532 308 195940 308.2 199764 306.8 1995.2


resultados de medición (portátil i7)

0

500

1000

1500

2000

2500

3000

3500

4000

4500

0 10 20 30 40 50 60 70

bucketstd


resultados de medición (portátil i7) ampliación

0

500

1000

1500

2000

2500

3000

3500

4000

4500

0 2 4 6 8 10 12

bucketstd


resultados de medición (estación i9)

0

500

1000

1500

2000

2500

3000

3500

0 10 20 30 40 50 60 70

bucketstd


resultados de medición (estación i9) ampliación

0

500

1000

1500

2000

2500

3000

3500

0 5 10 15 20 25 30

bucketstd


interpretamos lo que vemos en la gráfica del i7

0

500

1000

1500

2000

2500

3000

3500

4000

4500

0 2 4 6 8 10 12

bucketstd

el algoritmo de counting sort es más rápido que el algoritmo de lalibrería estándar (que implementa una ordenación en tiempoO(n/p ∗ log(n)+ ...) )

el mínimo de ambos curvas está en 4, eso sugiere que hay 4procesadores en el sistema

miramos el comportamiento de acceleración (speedup) en detallemás en adelante



0

500

1000

1500

2000

2500

3000

3500

0 5 10 15 20 25 30

bucketstd

el algoritmo de counting sort aquí también es más rápido que elalgoritmo de la librería estándar

pero parece no se gana tanto

el mínimo de ambos curvas está en 20, eso sugiere que hay 20procesadores en el sistema

miramos el comportamiento de acceleración en detalle


factor de acceleración (speedup)

sea Ts el tiempo de ejecución del programa secuencial

sea Tp el tiempo de ejecución del programa paralelo/concurrente

la fracción Ts/Tp se llama factor de acceleración o speedup

Notas:

para medir Ts se debe usar el mejor programa secuencialconocido para caracterizar el algoritmo paralelo

si se usa para Ts el programa paralelo con un solo proceso,solamente se caracteriza la paralelizabilidad del algoritmo

el tamaño del problema por resolver (n, en nuestro caso) influyeen la acceleración alcanzable

un factor de acceleración de p es lo más deseable, es decir, conp procesos el cálculo se realiza p-veces más rápido


factor de acceleración entre sistemas

sea TS1 el tiempo de ejecución en un sistema S1

sea TS2 el tiempo de ejecución en un sistema S2 (más potente)

la fracción TS2/TS1 se llama factor de acceleración entresistemas (o factor de ganancia)

Notas:

para medir TS1 y TS2 se debe fijar el tamaño del problema porresolver (n, en nuestro caso)

se debe usar el mejor algoritmo para cada sistema paracaracterizar la ganancia de un sistema respecto al otro

si se usa para ambos sistemas el mismo algoritmo, solamente secaracteriza la ganancia para un algoritmo en concreto


análisis de acceleración (speedup) (i7)

1

2

3

4

5

6

7

8

9

0 10 20 30 40 50 60 70

countstd

countvsstd


análisis de acceleración (speedup) (i7) ampliación

1

2

3

4

5

6

7

8

9

0 5 10 15 20

countstd

countvsstd


análisis de acceleración (speedup) (i9)

1

2

3

4

5

6

7

8

9

10

11

0 10 20 30 40 50 60 70

countstd

countvsstd


análisis de acceleración (speedup) (i9) ampliación

1

2

3

4

5

6

7

8

9

10

11

0 5 10 15 20 25 30

countstd

countvsstd



1

2

3

4

5

6

7

8

9

0 5 10 15 20

countstd

countvsstd

el sistema alcanza un speedup de 2 para el algoritmo de lalibrería estándar

el sistema alcanza un speedup de 1.5 para el algoritmo decounting sort

en ambos casos se alcanza el máximo a partir de 4 procesos

el sistema alcanza una acceleración de por lo menos 6comparando los dos algoritmos de ordenación

este mínimo (o peor ganancia) se da justamente en el momentode mejor speedup



1

2

3

4

5

6

7

8

9

10

11

0 5 10 15 20 25 30

countstd

countvsstd

el sistema alcanza un speedup de 10 para el algoritmo de lalibrería estándar

el sistema alcanza un speedup de 2 (y pico) para el algoritmo decounting sort

en ambos casos se alcanza el máximo a partir de 20 procesos

el sistema alcanza una acceleración de por lo menos 2comparando los dos algoritmos de ordenación

este mínimo (o peor ganancia) se da justamente en el momentode mejor speedup


interpretamos lo que vemos comparando los dos sistemas

0

500

1000

1500

2000

2500

3000

3500

4000

4500

0 2 4 6 8 10 12

bucketstd

0

500

1000

1500

2000

2500

3000

3500

0 5 10 15 20 25 30

bucketstd

fijamos un punto en el cual ambos sistemas son lo más rápido(+o-)

es cuando se usan unos 20 procesos

el speedup del i9 respecto al i7 en este punto es 307/172 ≈ 1.8para counting sort y 1985/328 ≈ 6 para el algoritmo de librería

es decir, el sistema del i9 es solamente dos veces mejor que elsistema del i7 si usamos el mejor algoritmo para resolver nuestroproblema específico


¿y ...?

¿hemos entendido todo?

pensamos que el i7 tiene 4 núcleos y el i9 tiene 20 núcleos,¿por qué no vemos un speedup de 4 (respectivamente 20) en elalgoritmo de counting sort cuyo compartamento es deO(n/p+ v) con el v muy pequeño respecto a n/p?

¿por qué vemos un speedup de 2 (respectivamente 10) en elalgoritmo de la librería estándar, pero un 1.5 (respectivamentesolo un 2) en el algoritmo de counting sort?

os dejo pensando...

precisamos ciertas cosas más en adelante...


retornamos a los desafios

selección del algoritmo




comunicación de los datos entre participantes



¿cómo los hemos afrontado?


selección del algoritmo

hemos usado un algoritmo que en principio nos permite unspeedup lineal en el número de procesos(aunque en realidad mediendo no lo hemos visto...)

el algoritmo es más rápido para nuestro problema que elalgoritmo de la librería estándar

hemos visto que el algoritmo de la librería tiene un buen speedup(si nuestro problema fuese la ordenación general)

Hay que seleccionar el algoritmo adecuado para la situación. Si se usalibrarías (trabajos de otros), hay que mirar si usan las característicasconcurrentes del sistema, sino se pierde mucha eficiencia.



hemos dividido, con la ayuda del compilador con OpenMP, todoslos bucles largos#pragma omp for schedule(static)

en trozos de igual tamaño para todos los procesos participantes

algún código hemos ejecutado con un único proceso cualquiero#pragma omp single



estamos en arquitecturas con memoria común

hemos declarado por defecto ninguna variable compartida y losque nos interesan como compartidas

constantes están implicitamente compartidas (en OpenMP)

variables declaradas en el bloque paralelo son automáticamentelocal al proceso (en OpenMP)

hemos diseñado el algoritmo de tal manera que los procesosescriben en memoria exclusiva, es decir, (casi) nunca escribenen el mismo sitio a la vez



OpenMP facilita bastante la sincronización simple

al comienzo del bloque paralelo se crean los procesos cuyonúmero se ha fijado previamente en algún momento

al comienzo de un bucle for se lanza todos los procesos con ladivisión del trabajo establecido

al final de un bucle for se sincroniza automáticamente con unaespera a que todos los participantes hayan terminado(nota: eso es cambiable!)

algunas partes del algoritmo hemos ejecutado a propósito con unúnico proceso

al final del bloque paralelo se terminan automáticamente todoslos procesos


comunicación de los datos

no sabemos todavía como el compilador (con OpenMP) consigueque todos los procesos saben que trozos tienen que calcular,por ejemplo, hallar los valores locales de k para cada proceso,

esta comunicación implícita es una de las grandes ventajas deusar OpenMP

no sabemos todavía como funciona la operación de reduccióndonde todos los procesos participantes consiguen el resultadototal de sus valores locales en una variable ompartida

esta técnica implícita es una de las grandes ventajas de usarOpenMP

hemos usado una variable booleana compartida sorted conmodificación posiblemente concurrente

en este caso no se manifestan problemas de escriturasconcurrentes porque si los procesos escriben algo, entoncesescriben lo mismo.



el resultado de la ordenación se almacena en una variablecompartida

los paramétros de entrada gestiona un solo proceso y secomunica mediante variables compartidas con los demás

el resultado del programa (podemos considerar, por ejemplo, lamedición del tiempo), escribe un único proceso


los CPUs que hemos usado: i7


los CPUs que hemos usado: i9


endendemos las mediciones

el i7 tiene 2 núcleos pero 4 hilos (físicos)

el i9 tiene 10 núcleos pero 20 hilos (físicos)

el speedup visto en el algoritmo de la librería refleja el número denúcleos presentes

el sppedup entre sistemas (i7 vs. i9) refleja el doble de velocidaddel bus

la ventaja de los hilos físicos no observamos con esta prueba


Búcle de cálculo (compara con prácticas)

#pragma omp parallel forfor(unsigned i=0; i<nIter; ++i) {double d(std::tan(std::atan(

std::tan(std::atan(std::tan(std::atan(std::tan(std::atan(

std::tan(std::atan(123456789.123456789))))

))))

)));d=std::cbrt(d);

}


Optimizaciones del compilador)

si compilamos el código con optimización activado

medimos un tiempo de ejecución casi 0

dado que el compilador es capaz de detectar que no se realizaninguna operación con la variable d fuera del bucle

y elimina básicamente todo el bucle (dead code elimination,eliminación de código innecesario)


Búcle de cálculo con variable no eliminable

#pragma omp parallel forfor(unsigned i=0; i<nIter; ++i) {double d(std::tan(std::atan(

std::tan(std::atan(std::tan(std::atan(std::tan(std::atan(

std::tan(std::atan(123456789.123456789))))

))))

)));some+=std::cbrt(d);

}


tiempo de ejecución observado en i7

20

30

40

50

60

70

80

90

100

110

0 10 20 30 40 50 60 70

atan


tiempo de ejecución observado en i9

0

10

20

30

40

50

60

70

80

90

100

0 10 20 30 40 50 60 70

atan


speedup observado en ambos sistemas

0

2

4

6

8

10

12

14

16

18

0 10 20 30 40 50 60 70

atani9atani7


interpretación de las mediciones

en este programa atan domina el cálculo

ambos sistemas alzanzan su mejor rendimiento cuando setrabaja con el número de hilos físicamente disponibles

en el sistema del i9 baja el rendimiento si superamos con elnúmero de hilos lógicos el número de hilos físicos(seguramente el acoplamiento de los 10 núcleos (20 hilos físicos)a la memoria/cachés no es tan escalable comparado con el i7)

el speedup entre sistemas comparando en el punto de mejorrendimiento llega a un factor de 5.27, es decir, más o menos unfactor debido al aumento de hilos físicos y al aumento del reloj dela CPU


reglas del desconfiado...

Si alguien os vende speedups (paralelo a secuencial) muygrandes: quizá su algoritmo secuencial no es el más adecuadopara comparar.

Si veis un speedup muy pequeño, pero el algoritmo sugiere más,hay que mirar en el cuadro de comunicación (haciamemoria/almacenamiento o interproceso).

Hay que tener en cuenta la jerarquia de la memoria en el sistemapara decidir la división del trabajo y la distribución de los datos.

Hay que reducir la necesidad de sincronización a un mínimoposible.

Hay que intentar solapar cómputo con comunicación de formaequilibrada.



hemos medido solamente el tiempo global de la parte algorítmicadel programa desde antes de la creación de los procesos(pragma omp parallel) hasta después del bloque enparalelo.

no sabemos nada en cuanto al tiempo que se necesita para lacreación, conmutación, y sincronización de los procesos(observa que a veces tenemos más procesos que procesadores(núcleos))

miramos como podemos medir el tiempo transcurridoindividualmente para cada proceso (Thread) en Java...


medición de tiempo de ejecución (ejemplo en Java)

class Timer {private long[] startTime;private long[] stopTime;

Timer(int n) {startTime=new long[n];stopTime=new long[n];

}public void Start(int i) {startTime[i]=System.nanoTime();

}public void Stop(int i) {stopTime[i]=System.nanoTime();

}public double Elapsed() {

long minTime=startTime[0];for(int i=1; i<startTime.length; ++i)if(startTime[i]<minTime) minTime=startTime[i];

long maxTime=stopTime[0];for(int i=1; i<stopTime.length; ++i)if(stopTime[i] > maxTime) maxTime=stopTime[i];

return (maxTime-minTime)/1000000.0;}

}CDI Dr. Arno Formella 109 / 278

hola mundo

El famoso hola mundo se programa en Java así:

class Hello {public static void main(String[] args) {

System.out.println("Hello world, this is "+args[0]

);}

}

El programa principal se llama main() y tiene que ser declaradopúblico y estático. No devuelve ningún valor (por eso se declara comovoid).Los parámetros de la línea de comando se pasan como un vector decadenas de letras (String).javac Hello.javajava Hello primero segundo tercero


¿Qué se comenta?

Se usa doxygen (o javadoc, u otro bueno) para generarautomáticamente la documentación. Todos tienen unoscomandos para aumentar la documentación.

Existen varias posibilidades de escribir comentarios:

// comentario de línea/// ... comentario de documentación/* ... */ comentario de bloque/** ... */ comentario de documentación

Se documenta sobre todo lo que no es obvio, las interfaces (en elsentido amplio de la palabra), y los casos límite.

Es decir: Los comentarios son las respuestas a preguntas del¿Cómo? y del ¿Por qué?.


Hilos

Se usan los hilos para ejecutar varias secuencias deinstrucciones de modo cuasi–paralelo.

Es decir, la ejecución parece ser en paralelo, pero si esrealmente paralelo (y no secuencial) depende del hardware (máspreciso, del número de CPUs involucrados) que se está usandoen cada momento.


creación de un hilo (para empezar)

Se crea un hilo conThread worker = new Thread()

Se inicializa el hilo y se define su comportamiento.

Normalmente se usa una clase derivada o la interfazRunnable.

Se lanza el hilo conworker.start()

Pero en esta versión simple no hace nada. Hace faltasobreescribir el método run() especificando algún código útil.

¿Cuándo arranca de verdad este nuevo hilo?


la interfaz Runnable

A veces no es conveniente extender la clase Thread porque sepierde la posibilidad de extender otro objeto.

Es una de las razones por que existe la interfaz Runnable quedeclara nada más que el método public void run() y quese puede usar fácilmente para crear hilos trabajadores.


resumen Java respecto a concurrencia

Thread, Runnable

join, isAlive, activeCount

try-catch-finally

volatile

synchronized

wait, notify, notifyAll

finalize

transient

java.util.concurrent

java.util.concurrent.atomic

etc.


try’n’catch

Para facilitar la programación de casos excepcionales Java usa elconcepto de lanzar excepciones.

Una excepción es una clase predefinida y se accede con lasentencia

try { ... }catch(SomeExceptionObject e) { ... }catch(AnotherExceptionObject e) { ... }finally { ... }


orden de ejecución I

El bloque try contiene el código normal por ejecutar.

Un bloque catch(ExceptionObject) contiene el códigoexcepcional por ejecutar en caso de que durante la ejecución delcódigo normal (que contiene el bloque try) se produzca laexcepción del tipo adecuado.

Pueden existir más de un (o ningún) bloque catch parareaccionar directamente a más de un (ningún) tipo de excepción.

Hay que tener cuidado en ordenar las excepcionescorrectamente, es decir, las más específicas antes de las másgenerales.


orden de ejecución II

El bloque finally se ejecuta siempre una vez terminado obien el bloque try o bien un bloque catch o bien unaexcepción no tratada o bien antes de seguir un break, uncontinue o un return hacia fuera de la sentenciatry-catch-finally.

Por eso es un buen punto donde ejecutar código en aplicacionesconcurrentes que deben realizar cierto trabajo final, incluso encasos excepcionales.


construcción de clases de excepción

Normalmente se extiende la clase Exception para implementarclases propias de excepciones, aún también se puede derivardirectamente de la clase Throwable que es la superclase (interfaz)de Exception o de la clase RuntimeException.

class MyException extends Exception {public MyException() { super(); }public MyException(String s) { super(s); }

}


declaración de excepciones lanzables

Entonces, una excepción no es nada más que un objeto que secrea en el caso de aparición del caso excepcional.

La clase principal de una excepción es la interfaz Throwableque incluye un String para mostrar una línea de error legible.

Para que un método pueda lanzar excepciones con lassentencias try-catch-finally, es imprecindible declararlas excepciones posibles antes del bloque de código del métodocon throws ....public void myfunc(...) throws MyException {...}

En C++ es al revés, se declara lo que se puede lanzar comomucho.


propagación de excepciones

Durante la ejecución de un programa se propagan lasexcepciones desde su punto de aparición subiendo lasinvocaciones de los métodos hasta que se haya encontrado unbloque catch que se ocupa de tratar la excepción.

En el caso de que no haya ningún bloque responsable, laexcepción será tratada por la máquina virtual con el posibleresultado de abortar el programa.


lanzar excepciones

Se pueden lanzar excepciones directamente con la palabrathrow y la creación de un nuevo objeto de excepción, porejemplo:throw new MyException("this is an exception");

También los constructores pueden lanzar excepciones que tienenque ser tratados en los métodos que usan dichos objetosconstruidos.


excepciones de ejecución

Además de las excepciones así declaradas existen siempreexcepciones que pueden ocurrir en qualquier momento de laejecución del programa, por ejemplo, RuntimeException oError o IndexOutOfBoundException.

La ocurrencia de dichas excepciones refleja normalmente unflujo de control erróneo del programa que se debe corrigir antesde distribuir el programa a posibles usuarios.


excepciones de ejecución

Recomendación: Se usan excepciones solamente para casosexcepcionales, es decir, si pasa algo no esperado.

Excepciones en programas concurrentes se conviertenrápidamente en pesadillas.Ya que aflorece el problema que hacer si muchos procesosempiezan a lanzar excepciones individualmente...Mirad Safe (Disciplined) Exception Handling principle con susdos posibilidades de acción

fallo: re-establecer una invariante necesariare-intentar: re-hacer la operación con (quizá) cierta modificación


multiplicamos

837649587637 * 984758392081 = ?


multiplicamos otra vez

837649587637 * 984758392081 = ?824882461048724816302597


algoritmo secuencial

Asumimos que tengamos solamente las operaciones aritméticassumar y subtraer disponibles en un procesador ficticio yqueremos multiplicar dos números positivos.

Un posible algoritmo sequencial que multiplica el número p conel número q produciendo el resultado r es:

Initially: set p and q to positive numbers

a: set r to 0b: loopc: if q equal 0 exitloopd: set r to r+pe: set q to q-1f: endloopg: ...


¿Cómo se comprueba si el algoritmo es correcto?

Primero tenemos que decir que significa correcto.El algoritmo (secuencial) es correcto si

una vez se llega a la instrucción g: el valor de la variable rcontiene el producto de los valores de las variables p y q (serefiere a sus valores que han llegado a la instrucción a:)se llega a la instrucción g: en algún momentoy la entrada habia sido la correcta.


¿Cómo se comprueba si el algoritmo es correcto?

Tenemos que saber que las instrucciones atómicas soncorrectas,

es decir, sabemos exactamente su significado, incluyendo todoslos efectos segundarios posibles.

Luego usamos el concepto de inducción para comprobar el bucle.


Invariante e inducción

Sean pi , qi , y ri los contenidos de los registros p, q, y r, despuésde la iteración i del bucle.

Una invariante cuya corrección hay que comprobar con elconcepto de inducción es entonces:

ri +pi ·qi = p ·q

¿Cómo encontrar una invariante adecuada?

usar ingenio...(RAE: Facultad del ser humano para discurrir o inventar conprontitud y facilidad.)

Además, si comprobramos que qi al final (saliendo del bucle) escero, entonces, obviamente, el registro r contendrá el producto.


algoritmo concurrente

Re-escribimos el algoritmo secuencial para que “funcione” con dosprocesos:

Initially: set p and q to positive numbers

a: set r to 0P0 P1

b: loop loopc: if q equal 0 exit if q equal 0 exitd: set r to r+p set r to r+pe: set q to q-1 set q to q-1f: endloop endloopg: ...


Implementamos la multiplicación con Java

Realizamos una clase para valores enteros.

Implementamos el bucle que realiza la multiplicación.

Colocamos todo en un programa completo.


Enteros como objectos

Realizamos una clase para tener los enteros como clase propia(Integer no nos vale):

class Int {int i;Int(int i) { this.i=i; }void Add(Int I) { i=i+I.i; }int Get() { return i; }

}


Preparar trabajador

Preparamos los hilos trabajadores con acceso a las variablescomunes:

class Mul implements Runnable {private int id; // thread identityprivate Int p; // reference to shared first factorprivate Int q; // reference to shared second factorprivate Int r; // reference to shared result

Mul(int id, Int p, Int q, Int r) {this.id=id;this.p=p;this.q=q;this.r=r;

}


El trabajo del trabajador

Implementamos el método run() para realizar el bucle demultiplicación:

public void run() {synchronized(p) {try {System.out.println("starting worker... "+id);Int minusOne=new Int(-1);while(q.Get()!=0) {

r.Add(p);q.Add(minusOne);

}}catch(Exception E) { System.out.println("??? "+id); }finally { System.out.println("exiting... "+id); }}


El programa principal I

Tratar la entrada:

}

class Multi {static Int p,q,r; // our shared variables for r=p*q

public static void main(String[] args) {try {

if(args.length!=3) {System.out.println("please 3 arg's: p q n");System.exit(1);

}

p=new Int(Integer.parseInt(args[0]));


El programa principal II

Crear, lanzar, y sincronizar los trabajadores:

r=new Int(0);

final int n=Integer.parseInt(args[2]);final Thread[] threads=new Thread[n];

for(int i=0; i<threads.length; ++i) {threads[i]=new Thread(new Mul(i,p,q,r));

}

for(int i=0; i<threads.length; ++i) {threads[i].start();

}

for(int i=0; i<threads.length; ++i) {


El programa principal III

Visualización del resultado:

}

System.out.println(args[0]+"*"+args[1]+"="+r.Get()+" ??"

);}catch(Exception E) {

System.out.println("catched an exception...");System.exit(1);

}finally {

System.out.println("exiting...");}

}}


¿Qué es que observamos?

El algoritmo es no-determinista,

en el sentido que no se sabe de antemano en qué orden (en unprocesador o en un conjunto de procesadores) se van a ejecutarlas instrucciones,

o más preciso, cómo se van a intercalar las instruccionesatómicas de ambos procesos.

El no-determinismo puede provocar situaciones con errores, esdecir, el fallo ocurre solamente si las instrucciones se ejecutan enun orden específico.

El resultado del programa no es predecible, y lo peor es, a veceses correcto.

Desde el punto de vista de concurrencia tiene varios problemas.


Linearizabilidad

usamos aquí la noción de atomicidad

es decir, asumimos que una operación (transacción) se ejecutaen un instante, y el resultado de la operación no depende de losdemás actores

si tenemos tal propiedad podemos decir que las operaciones(transacciones) son linearizables

es una propiedad de sistemas concurrentes (y distribuidos): latienen o no la tienen

para conseguirlo se necesita necesariamente algún tipo decoordinación


Linearizabilidad (en bases de datos)

es un concepto importante también en el mundo de las bases dedatos (de hecho viene de ahí)por ejemplo: pensad en un servicio de ficheros con accesoconcurrente,

¿qué transacciones con el servidor serían interesantes y cualesserían sus semánticas por implementar?¿Podemos implementar linearizabilidad de las transacciones?¿incluso en caso de ciertos tipos de fallos?seguramente depende del tipo de aplicación que usa tal servicio...


Serializabilidad

es el concepto de que las operaciones (transacciones) de unsistema concurrente son equivalentes a un orden en un sistemasecuencial

si la semántica de la ejecución en serie está bien conocida y sesabe que concurrentemente pasa lo mismo, entonces es másfácil de argumentar sobre la corrección

pero en ciertas aplicaciones quizá es demasiado restrictivo...

por ejemplo: por qué multiplicar correcto si al final se rondea?

serializabilidad suele estar presentes en bases de datos(clásicos) sobre todo si tratan con dinero


funcionamiento correcto I

Generalmente se dice que un programa es correcto, si dada unaentrada, el programa produce los resultados deseados.Más formal:

Sea P(x) una propiedad de una variable x de entrada (aquí elsímbolo x refleja cualquier conjunto de variables de entradas).

Sea Q(x ,y) una propiedad de una variable x de entrada y deuna variable y de salida.


funcionamiento correcto II

Se define dos tipos de funcionamiento correcto de un programa:

funcionamiento correcto parcial:dada una entrada a, si P(a) es verdadero, y si se lanzael programa con la entrada a, entonces si el programatermina habrá calculado b y Q(a,b) también esverdadero.

funcionamiento correcto total:dado una entrada a, si P(a) es verdadero, y si se lanzael programa con la entrada a, entonces el programatermina y habrá calculado b con Q(a,b) siendo tambiénverdadero.


funcionamiento correcto III

Para un programa secuencial existe solamente un orden total de lasinstrucciones atómicas (en el sentido que un procesador secuencialsiempre sigue el mismo orden de las instrucciones... bueno, esmentira..., hay out-of-order and speculative execution), mientras quepara un programa concurrente puedan existir varios órdenes.Por eso se tiene que exigir:

funcionamiento correcto concurrente:un programa concurrente funciona correctamente, si elresultado Q(x ,y) no depende del orden de lasinstrucciones atómicas entre todos los órdenesposibles.


Funcionamiento correcto IV

Entonces:

Se debe asumir que los hilos pueden intercalarse en cualquierpunto en cualquier momento.

Los programas no deben estar basados en la suposición de quehabrá un intercalado específico entre los hilos por parte delplanificador (que conmuta los procesos).


funcionamiento correcto V

Para comprobar si un programa concurrente es incorrecto bastacon encontrar una sola intercalación de instrucciones que noslleva en un fallo.

Para comprobar si un programa concurrente es correcto hay quecomprobar que no se produce ningún fallo en ninguna de lasintercalaciones posibles.


comprobación exhaustiva no es práctico

El número de posibles intercalaciones de los procesos en unprograma concurrente crece exponencialmente con el número deunidades que maneja el planificador y líneas por intercalar.

¿Cuántos son? (Ayuda: calcular las combinaciones posibles deuna lista dentro de otra)

Por eso es prácticamente imposible comprobar con la meraenumeración si un programa concurrente es correcto bajo todaslas ejecuciones posibles.

En la argumentación hasta ahora era muy importante que lasinstrucciones se ejecutaran de forma atómica, es decir, sininterrupción ninguna.

Por ejemplo, se observa una gran diferencia si el procesadortrabaja directamente en memoria o si trabaja con registros.


dependencia de atomicidad I

Si increment es atómico:

P1: inc NP2: inc N

P2: inc NP1: inc N

Se observa: las dos intercalaciones posibles producen el resultadocorrecto.


dependencia de atomicidad II

Si increment no es atómico:

P1: load R1,NP2: load R2,NP1: inc R1P2: inc R2P1: store R1,NP2: store R2,N

Es decir, existe una intercalación que produce un resultado falso.Ejemplos de Java:

accesos a variables con más de 4 bytes no son atómicos.

el operador ++ no es atómico.

o en otras palabras: lectura y escritura de flotantes no eslinearizable en Java


¿Y?

¿El algoritmo concurrente de multiplicación con dos hilos dearriba es correcto? (correcto parcial? correcto total?)

¿Cómo lo compruebas?

¿Te ocurre un algoritmo concurrente correcto que funcione convarios hilos?

¿Te ocurre un algoritmo concurrente correcto y eficiente, esdecir, donde varios hilos juntos son más rápido que uno sólo?


Sincronización

A veces se quiere que un hilo actua sin que otros interfieran ensu tarea.

Es decir, se quiere una ejecución con exclusión mutua del código.

Dicho concepto se llama también atomicidad de las operaciones,

o también ejecución segura con hilos (threadsafe).

En Java existen diferentes posibilidades para conseguir exclusiónmutua.


Atomicidad en Java

Solo las asignaciones a variables de tipos simples de 32 bits sonatómicas.

long y double no son simples en este contexto porque son de64 bits.

Hay que declarar esas variables como volatile para obteneracceso atómico.


synchronized

En Java es posible forzar la ejecución del código en un bloque demodo sincronizado, es decir, como mucho un hilo, que tengaacceso compartido a obj, puede ejecutar el código dentro dedicho bloque.synchronized(obj) { ... }

La expresión entre paréntesis obj tiene que evaluar a unareferencia a un objeto o a un vector.

Declarando un método con el modificador synchronizedgarantiza que dicho método se ejecuta por un sólo hilo (y ningúnotro método sincronizado del mismo objeto tampoco).

La máquina virtual instala un cerrojo (mejor dicho, un monitor, yaveremos dicho concepto más adelante) que se cierra de formaatómica antes de entrar en la región crítica y que se abre antesde salir.


Métodos syncronizados

Declarar un método comosynchronized void f(...) { ... }es equivalente a usar un bloque sincronizado en su interior:void f(...) { synchronized(this) { ... } }

Los monitores (implementados en la MVJ) permiten que elmismo hilo puede acceder a otros métodos o bloquessincronizados del mismo objeto sin problema.

Se libera el cerrojo sea el modo que sea que termine el método.

Los constructores no se pueden declarar synchronized.


Uso de clases de java.util.concurrent

Java proporciona el paquete java.util.concurrentSe puede implementar el algoritmo de multiplicación de antes con, porejemplo:

métodos sincronizados

AtomicInteger

LongAdder (a partir de Java8)

LongAccumulator (a partir de Java8)

semáforos (semaphores)

cerrojos (locks)

Hay diferencias en eficiencia.


Enteros con int y método sincronizado

// Implementation of out integer with a simple int// and synchronized Add.class Int {

public int i;Int(int i) { this.i=i; }synchronized void Add(Int I) { i=i+I.i; }// void Add(Int I) { i=i+I.i; }int Get() { return i; }

}


Enteros con Integer y método sincronizado

// Implementation of our integer with an Integer// and synchronized Add.class Int {

private Integer i;Int(int i) { this.i=i; }synchronized void Add(Int I) { i=i+I.i; }int Get() { return i; }

}


Enteros con AtomicInteger

import java.util.concurrent.atomic.*;

// Implementation of our integer with an AtomicInteger.class Int {

private AtomicInteger i;Int(int i) { this.i=new AtomicInteger(i); }void Add(Int I) { i.getAndAdd(I.Get()); }int Get() { return i.get(); }

}


Enteros con LongAdder


// Implementation of our integer with a LongAdder.class Int {

private LongAdder i;Int(int i) {this.i=new LongAdder();this.i.add(i);

}void Add(Int I) { i.add(I.Get()); }int Get() { return i.intValue(); }

}


Enteros con LongAccumulator


// Implementation of our integer with a LongAccumulator.class Int {

private LongAccumulator i;Int(int i) {this.i=new LongAccumulator(Long::sum, i);

}void Add(Int I) { i.accumulate(I.Get()); }int Get() { return i.intValue(); }

}


Enteros con semáforo

import java.util.concurrent.Semaphore;

// Implementation of our integer with a semaphore.class Int {

private int i;private Semaphore semaphore;Int(int i) {this.i=i;semaphore=new Semaphore(1);

}void Add(Int I) {try {

semaphore.acquire(); // Entrance protocol.i+=I.i;

}catch(InterruptedException E) {System.out.println("got interrupted...??");

}finally {semaphore.release(); // Exit protocol.

}}int Get() { return i; }


Enteros con lock

import java.util.concurrent.locks.*;

// Implementation of out integer with a reentrant lock.class Int {

private int i;private ReentrantLock lock;Int(int i) {this.i=i;lock=new ReentrantLock();

}void Add(Int I) {lock.lock(); // Entrance protocol.try {i+=I.i;

} finally {lock.unlock(); // Exit protocol.


}


Multiplicación concurrente correcto

Cuidado que los hilos no hagan nada "demás"... comparamos conq > n:

public void run() {try {final Int minusOne=new Int(-1);

// Here, we check "greater than n" to avoid negative q !!while(q.Get()>n) {r.Add(p);q.Add(minusOne);

}}catch(Exception E) {

System.out.println("some error..."+id);}// We don't write final message, so we don't disturb measurement.



Cuidado que se realiza todo lo que hay que hacer... realizamos losposibles remanentes en el hilo principal.

for(int i=0; i<threads.length; ++i) {threads[i].join();

}// Here we take care of the left-overs.

final Int minusOne=new Int(-1);while(q.Get()>0) {

r.Add(p);q.Add(minusOne);

}



El algoritmo no es eficiente, ya que hay mucha congestión accediendoa las variable compartidas q y r con exclusión mutua:

0

10

20

30

40

50

60

70

80

90

1 2 4 8 16 32 64 128 256 512 1024

"multic_int.gdt""multic_Integer.gdt"

"multic_AtomicInteger.gdt""multic_LongAdder.gdt"

"multic_LongAccumulator.gdt""multic_sema.gdt""multic_lock.gdt"

"multic_mysema.gdt"


Multiplicación concurrente correcto y eficiente

class Mul implements Runnable {private final int id;private final int n;private int p;private int q;private Int r;

Mul(int id, int n, Int p, Int q, Int r) {this.id=id;this.n=n;this.p=p.Get();this.q=q.Get()/n;this.r=r;

}



public void run() {try {

// Here, we run on local variables.int local_r=0;while(q>0) {

local_r+=p;--q;

}final Int My_r=new Int(local_r);r.Add(My_r);

}catch(Exception E) {

System.out.println("some error..."+id);}

}



}for(int i=0; i<threads.length; ++i) {threads[i].start();

}// Here we help with the left-overs.

int local_p=p.Get();int local_q=q.Get()%n;int local_r=0;while(local_q>0) {

local_r+=local_p;--local_q;

}

for(int i=0; i<threads.length; ++i) {threads[i].join();

}final Int My_r=new Int(local_r);



Ahora hay mucho menos congestión... (unos 1000 veces más rápido,aumentamos q por un factor de 100)

0

10

20

30

40

50

60

70

80

90

1 2 4 8 16 32 64 128 256 512 1024

"multip_int.gdt""multip_Integer.gdt"

"multip_AtomicInteger.gdt""multip_LongAdder.gdt"

"multip_LongAccumulator.gdt""multip_sema.gdt""multip_lock.gdt"


Ojo, si no hacemos las cosas bien...

0

100

200

300

400

500

600

700

1 2 4 8 16 32 64 128 256 512 1024




"multic_mysema.gdt"


el sistema más potente se convierte en el más lento!

0

100

200

300

400

500

600

700

1 2 4 8 16 32 64 128 256 512 1024




"multic_mysema.gdt"

0

100

200

300

400

500

600

700

1 2 4 8 16 32 64 128 256 512 1024




"multic_mysema.gdt"

es decir, si el programa concurrente está mal hecho, es posible que unsistema nuevo incluso es más lento que el viejo!(Este efecto observé la primera vez en el año 2018.)


Sincronización y herencia

No hace falta mantener el modo sincronizado sobre-escribiendométodos síncronos mientras se extiende una clase.

No se puede forzar un método sincronizada en una interfaz.

Sin embargo, una llamada al método de la clase súperior (consuper.) sigue funcionando de modo síncrono.

Los métodos estáticos también se pueden declararsynchronized garantizando su ejecución de maneraexclusiva entre varios hilos.


Protección de miembros estáticos

En ciertos casos se tiene que proteger el acceso a miembrosestáticos con un cerrojo. Para conseguir eso es posible sincronizarcon un cerrojo de la clase, por ejemplo:

class MyClass {static private int nextID;...MyClass() {synchronized(MyClass.class) {idNum=nextID++;

}}...

}


¡Ojo con el concepto!

Declarar un bloque o un método como síncrono solo prevee queningún otro hilo pueda ejecutar al mismo tiempo dicha regióncrítica (u otra sincronizada con el mismo objeto),

sin embargo, cualquier otro código asíncrono puede serejecutado mientras tanto y su acceso a variables críticas puededar como resultado fallos o efectos inesperados en el programa.


Objetos síncronos

Se obtienen objetos totalmente sincronizados siguiendo las reglas:

todos los métodos son synchronized,

no hay miembros/atributos públicos,

todos los métodos son final,

se inicializa siempre todo bien,

el estado del objeto se mantiene siempre consistente incluyiendolos casos de excepciones.


Limitaciones para la programación concurrente

no se puede interrumpir la espera a un cerrojo(una vez llegado a un synchronized no hay vuelta atrás)

no se puede influir mucho en la política del cerrojo(distinguir entre lectores y escritores, diferentes justicias, etc.)

no se puede confinar el uso de los cerrojos(en cualquier línea se puede escribir un bloque sincronizado decualquier objeto)

no se puede adquirir/liberar un cerrojo en diferentes flujos decontrol, se está obligado a una estructura de bloques


Paquete especial para la programación concurrente

Por eso, y otros motivos, se ha introducido desde Java 5 unpaquete especial para la programación concurrente.

java.util.concurrent

Hay que leer/estudiar todo su manual.

Partes mencionaremos en clase en su momento.


Páginas del manual

Se recomienda estudiar detenidamente las páginas del manual deJava que estén relacionados con el concepto de hilo (mira también lasreferencias en el boletín de prácticas).


un programa concurrente

Asumimos que tengamos un programa concurrente que quiererealizar acciones con recursos.(por ejemplo, los factores de la multiplicacion, o mirad lasprácticas)

Si los recursos de los diferentes procesos son diferentes no hayproblema (mira por ejemplo la práctica de filtrado de matriz),

Si dos (o más procesos) quieren manipular el mismo recurso¿Qué hacemos?

Vimos ya ayudas Java como AtomicInteger, o elsynchronized, o los otros...

Levantamos el nivel a algo más abstracto, revisamos los yamencionados y luego implementamos a nivel bajo.


un programa concurrente

Tenemos básicamente tres opciones para tratar posibles escriturasconcurrentes:

se implementa exclusión mutua, es decir, solamente un procesotiene acceso, los demás esperan;

se implementa comportamiento idéntico, es decir, desde elalgoritmo se garantiza que todos los procesos actuan igual(sobre todo: escriben lo mismo en caso que escribanconcurrentemente);

se implementa comportamiento transaccional, es decir, solo unproceso gana, lo que hacen los demás no influe en su resultado(con la opción que los demás se notifiquen en caso de fracaso)(con la opción que cualquiera o uno específico gana).


¿Qué es exclusión mutua?

Para evitar el acceso concurrente a recursos compartidos hacefalta instalar un mecanismo de control

que permite la entrada de un proceso si el recurso está disponibleyque prohibe la entrada de un proceso si el recurso está ocupado.

Es importante entender cómo se implementan los protocolos deentrada y salida para realizar la exclusión mutua.

Obviamente no se puede implementar exclusión mutua usandoexclusión mutua: se necesita algo más básico.

Un método es usar un tipo de protocolo de comunicación basadoen las instrucciones básicas disponibles en el hardware.(Eso veremos más adelante.)


estructura general basada en protocolos

Entonces el protocolo para cada uno de los participantes refleja unaestructura como sigue (si protegemos código):

P0 ... Pi... ...entrance protocol entrance protocolcritical section critical sectionexit protocol exit protocol... ...


Enteros con lock

import java.util.concurrent.locks.*;

// Implementation of out integer with a reentrant lock.class Int {private int i;private ReentrantLock lock;Int(int i) {

this.i=i;lock=new ReentrantLock();

}void Add(Int I) {

lock.lock(); // Entrance protocol.try {i+=I.i;

} finally {lock.unlock(); // Exit protocol.


}


conceptos

El concepto de usar estructuras de datos a nivel alto libera al/aprogramador/a de los detalles de su implementación.

Se puede asumir que las operaciones están implementadascorrectamente y se puede basar el desarrollo del programaconcurrente en un funcionamiento correcto de las operacionesde los tipos de datos abstractos.

Para que se puedan utilizar con provecho hay que entender endetalle las propiedades de tales estructuras de datos.


región crítica

Un lenguaje de programación puede realizar directamente unaimplementación de una región crítica.

Así parte de la responsabilidad se traslada desde el programadoral compilador.

De alguna manera (depende del lenguaje de programación enconcreto) se identifica que algún bloque de código se debe tratarcomo región crítica(así funciona Java con sus bloques sincronizados):

V is shared variableregion V docode of critical region


observaciones

El compilador asegura que la variable V tenga un protocolo deentrada y salida adjunto que se usa para controlar el accesoexclusivo de un solo proceso a la región crítica.

De este modo no hace falta que el programador usedirectamente las operaciones de los protocolos para controlar elacceso con el posible error de olvidarse de alguna parte esencial.

Adicionalmente es posible que dentro de la región crítica se llamea otra parte del programa que a su vez contenga una regióncrítica. Si ésta está controlada por la misma variable V el procesoobtiene automáticamente también acceso a dicha región.


regiones críticas condicionales

En muchas situaciones es conveniente controlar el acceso devarios procesos a una región crítica por una condición.

Con las regiones críticas simples, vistas hasta ahora, no sepuede realizar tal control. Hace falta otra construcción, porejemplo:

V is shared variableC is boolean expressionregion V when C do

code of critical region


detalles de implementación I

Las regiones críticas condicionales pueden funcionar internamente dela siguiente manera:

Un proceso que quiere entrar en la región crítica espera hastaque tenga permiso.

Una vez obtenido permiso comprueba el estado de la condición,si la condición lo permite, entra en la región, en caso contrario,libera el cerrojo y se pone de nuevo esperando en la cola deacceso.


detalles de implementación II

Se implementa una región crítica normalmente con dos colasdiferentes.

Una cola principal controla los procesos que quieren acceder a laregión crítica, una cola de eventos controla los procesos que yahan obtenido una vez el cerrojo pero que han encontrado lacondición en estado falso.

Si un proceso sale de la región crítica todos los procesos quequedan en la cola de eventos pasan de nuevo a la cola principalporque tienen que recomprobar la condición.


detalles de implementación III

Nota que esta técnica puede derivar en muchas comprobacionesde la condición, todos en modo exclusivo, y puede causarpérdidas de eficiencia.

En ciertas circunstancias puede ser interesante realizar uncontrol más sofisticado del acceso a la región crítica dando pasodirecto de un proceso a otro.


semáforo

Un semáforo es un tipo de datos abstracto que permite el uso de unrecurso de manera exclusiva cuando varios procesos estáncompetiendo y que cumple la siguiente semántica:

El estado interno del semáforo cuenta cuantos procesos todavíapueden utilizar el recurso. Se puede realizar, por ejemplo, con unnúmero entero que nunca debe llegar a ser negativo.

Existen tres operaciones con un semáforo: init(), wait(), ysignal() que realizan lo siguiente:


operaciones del semáforo I

init():

Inicializa el semáforo antes de que cualquier proceso hayaejecutado ni una operación wait() ni una operaciónsignal() al límite de número de procesos que tengan derechoa acceder el recurso.

Si se inicializa con 1, se ha construido un semáforo binario.

En lenguajes orientados a objectos, la operación init() sesuele realizar en la construcción del objeto correspondiente.


operaciones del semáforo II

wait():

Si el estado indica cero, el proceso se queda atrapado en elsemáforo hasta que sea despertado por otro proceso.

Si el estado indica que un proceso más puede acceder el recursose decrementa el contador y la operación termina con exito.

La operación wait() tiene que estár implementada como unainstrucción atómica. Sin embargo, en muchas implementacionesla operación wait() puede ser interrumpida.

Normalmente existe una forma de comprobar si la salida delwait() es debido a una interrupción o porque se ha dadoacceso al semáforo.

Importante: esta comprobación se debe hacer!


operaciones del semáforo III

signal():

Una vez se ha terminado el uso del recurso, el proceso loseñaliza al semáforo. Si queda algún proceso bloqueado en elsemáforo, uno de ellos sea despertado, sino se incrementa elcontador.

La operación signal() también tiene que estár implementadacomo instrucción atómica. En algunás implementaciones esposible comprobar si se ha despertado un proceso con exito encaso que había alguno bloqueado.

Para despertar los procesos se pueden implementar variasformas que se destinguen en su política de justicia (p.ej. FIFO).


uso del semáforo

El acceso mutuo a secciones críticas se arregla con un semáforo quepermita el acceso a un sólo proceso

S.init(1)

P1 P2a: loop loopb: S.wait() S.wait()c: critical section critical sectiond: S.signal() S.signal()e: non-critical section non-critical sectionf: endloop endloop


Enteros con Semaphore

import java.util.concurrent.Semaphore;

// Implementation of our integer with a semaphore.class Int {

private int i;private Semaphore semaphore;Int(int i) {this.i=i;semaphore=new Semaphore(1);

}void Add(Int I) {try {

semaphore.acquire(); // Entrance protocol.i+=I.i;

}catch(InterruptedException E) {System.out.println("got interrupted...??");

}finally {semaphore.release(); // Exit protocol.



semáforos binarios/generales

Si existen en un entorno solamente semáforos binarios, se puedesimular un semáforo general usando dos semáforos binarios y uncontador, por ejemplo, con las variables delay, mutex y count.

La operación init() inicializa el contador al número máximopermitido.

El semáforo mutex asegura acceso mutuamente exclusivo alcontador.

El semáforo delay atrapa a los procesos que superan elnúmero máximo permitido.


detalles de la implementación I

La operación wait() se implementa de la siguiente manera:

delay.wait()mutex.wait()decrement countif count greater 0 then delay.signal()mutex.signal()


detalles de la implementación II

La operación signal() se implementa de la siguiente manera:

mutex.wait()increment countif count equal 1 then delay.signal()mutex.signal()


Implementación de este semáforo en Java

class MySemaphore {private int cnt;private ReentrantLock mutex;private ReentrantLock delay;MySemaphore(int n) {cnt=n;mutex=new ReentrantLock();delay=new ReentrantLock();

}public void acquire() {delay.lock();mutex.lock();--cnt;if(cnt>0) delay.unlock();mutex.unlock();

}public void release() {mutex.lock();++cnt;if(cnt==1) delay.unlock();mutex.unlock();

}}


principales desventajas de semáforos

No se puede imponer el uso correcto de las llamadas a loswait()s y signal()s.

No existe una asociación entre el semáforo y el recurso.

Entre wait() y signal() el usuario puede realizar cualquieroperación con el recurso.


observaciones II

Las regiones críticas no son lo mismo que los semáforos, porqueno se tiene acceso directo a las operaciones init(), wait()y signal().

Con semáforos se puede emular regiones críticas pero no alrevés.


monitor

Un monitor es un tipo de datos abstracto que contiene

un conjunto de procedimientos de control de los cualessolamente un subconjunto es visible desde fuera,

un conjunto de datos privados, es decir, no visibles desde fuera.


detalles de implementación de un monitor

El acceso al monitor está permitido solamente a través de losmétodos públicos y el compilador garantiza exclusión mutua paratodos los accesos.

La implementación del monitor controla la exclusión mutua concolas de entrada que contengan todos los procesos bloqueados.

Pueden existir varias colas y el controlador del monitor elige decual cola se va a escoger el siguiente proceso para actuar sobrelos datos.

Un monitor no tiene acceso a variables exteriores con elresultado de que su comportamiento no puede depender deellos.

Una desventaja de los monitores es la exclusividad de su uso, esdecir, la concurrencia está limitada si muchos procesos hacenuso del mismo monitor.


sincronización condicional

Un aspecto que se encuentra en muchas implementaciones demonitores es la sincronización condicional, es decir, mientras unproceso está ejecutando un procedimiento del monitor (conexclusión mutua) puede dar paso a otro proceso liberando elcerrojo. (Estas operaciones se suele llamar wait o delay).

El proceso que ha liberado el cerrojo se queda bloqueado hastaque otro proceso le despierta de nuevo. Este bloqueo temporalestá realizado dentro del monitor.

Dicha técnica se refleja en Java con wait() ynotify()/notifyAll().

La técnica permite la sincronización entre procesos porqueactuando sobre el mismo recurso los procesos pueden cambiarel estado del recurso y pasar así información de un proceso aotro.


disponibilidad de monitores

Lenguajes de alto nivel que facilitan la programación concurrentesuelen tener monitores implementados dentro del lenguaje (porejemplo en Java: todos los objetos derivan de Object quecontiene los métodos wait() y notify/notifyAll().

El uso de monitores es bastante costoso, porque se puedeperder eficiencia por bloquear los procesos innecesariamente yel trabajo adicional por el uso del monitor.

Por eso se intenta aprovechar de primitivas más potentes paraaliviar este problema (alternativas libres de cerrojos (lock free)y/o libres de espera (wait free)).


Java máquina de estados de hilos


desventajas de uso de sincronización a alto nivel

No se distingue entre accesos de solo lectura y de escritura quelimita la posibilidad de accesos en paralelo.

Cualquier interrupción (p.ej. por falta de página de memoria)relantiza el avance de la aplicación,

por eso las MVJ usan los procesos del sistema operativo paraimplementar los hilos, así el S.O. puede conmutar a otro hilo.

Sigue presente el problema de llamar antes a notify(), onotifyAll() que a wait()(condición de carrera o race condition).


un caso ...www.flexcoin.com

Update (March 4 2014): During the investigation into stolen funds wehave determined that the extent of the theft was enabled by a flawwithin the front-end (???). The attacker logged into the flexcoin frontend from IP address XXX under a newly created username anddeposited to address XXX. The coins were then left to sit until they hadreached 6 confirmations.The attacker then successfully exploited a flaw in the code whichallows transfers between flexcoin users. By sending thousands ofsimultaneous requests, the attacker was able to move coins from oneuser account to another until the sending account was overdrawn,before balances were updated. This was then repeated throughmultiple accounts, snowballing the amount, until the attacker withdrewthe coins.


www.flexcoin.com

un caso recientewww.flexcoin.com

Flexcoin has made every attempt (???) to keep our servers as secureas possible, including regular testing. In our approx. 3 years ofexistence we have successfully repelled thousands of attacks. But inthe end, this was simply not enough.Having this be the demise of our small company, after the endlesshours of work we’ve put in, was never our intent. We’ve failed ourcustomers, our business, and ultimatley the Bitcoin community.


www.flexcoin.com

un caso recientewww.flexcoin.com

Look and smile:

mybalance = database.read("account-number")newbalance = mybalance - amountdatabase.write("account-number", newbalance)dispense_cash(amount) // or send bitcoins to customer

(taken from http://hackingdistributed.com/2014/04/06/

another-one-bites-the-dust-flexcoin/)


www.flexcoin.com

http://hackingdistributed.com/2014/04/06/another-one-bites-the-dust-flexcoin/

http://hackingdistributed.com/2014/04/06/another-one-bites-the-dust-flexcoin/

instrucciones básicas

obviamente tenemos que asumir que ciertas acciones de unproceso se puede realizar correctamente independientemente delas acciones de los demás procesos

dichas acciones se llaman atómicas (porque son indivisibles) yse garantizan por hardware

asumimos que podemos acceder a variables de cierto tipo (p.ej.enteros) de forma atómica con lectura y escritura(load y store)


Un posible protocolo (asimétrico)

P0 P1a: loop loopb: non-critical section non-critical sectionc: set v0 to true set v1 to trued: wait until v1 equals false while v0 equals truee: set v1 to falsef: wait until v0 equals falseg: set v1 to trueh: critical section critical sectioni: set v0 to false set v1 to falsej: endloop endloop


principio de la bandera

Si ambos procesos primero levantan sus banderas

y después miran al otro lado

por lo menos un proceso ve la bandera del otro levantado.


comprobación con contradicción

asumimos P0 era el último en mirar

entonces la bandera de P0 está levantada

asumimos que P0 no ha visto la bandera de P1

entonces P1 ha levantado la bandera después de la mirada deP0

pero P1 mira después de haber levantado la bandera

entonces P0 no era el último en mirar


propiedades de interés del protocolo

Normalmente, un protocolo de entrada y salida debe cumplir con lassiguientes condiciones:

sólo un proceso debe obtener acceso a la sección crítica(garantía del acceso con exclusión mutua)

por lo menos un proceso debe obtener acceso a la seccióncrítica después de un tiempo de espera finito.

Obviamente se asume que ningún proceso ocupa la seccióncrítica durante un tiempo infinito.


propiedades de interés del protocolo

La propiedad de espera finita se puede analizar según los siguientescriterios:

justicia:hasta que medida influyen las peticiones de los demásprocesos en el tiempo de espera de un proceso

espera:hasta que medida influyen los protocolos de los demásprocesos en el tiempo de espera de un proceso

tolerancia a fallos:hasta que medida influyen posibles errores de losdemás procesos en el tiempo de espera de un proceso.


análisis del protocolo asimétrico

Analizamos el protocolo de antes respecto a dichos criterios:

¿Está garantizado la exclusión mutua?

¿Influye el estado de uno (sin acceso) en el acceso del otro?

¿Quién gana en caso de peticiones simultaneas?

¿Qué pasa en caso de error?


soporte hardware

Dependiendo de las capacidades del hardware laimplementación de los protocolos de entrada y salida es másfácil o más difícil, además las soluciones pueden ser más omenos eficientes.

Vimos y veremos que se pueden realizar protocolos segurossolamente con las instrucciones load y store de unprocesador.

Las soluciones no suelen ser muy eficientes, especialmente simuchos procesos compiten por la sección crítica. Pero: sudesarrollo y la presentación de la solución ayuda en entender elproblema principal.

A veces no hay otra opción disponible.

Todos los microprocesadores modernos proporcionaninstrucciones básicas que permiten realizar los protocolos deforma más directo y en muchas ocaciones más eficiente.


protocolo simple: primer intento

Usamos una variable v que nos indicará cual de los dos procesostiene su turno.

P0 P1a: loop loopb: wait until v equals P0 wait until v equals P1c: critical section critical sectiond: set v to P1 set v to P0e: non-critical section non-critical sectionf: endloop endloop


primer intento: propiedades

Está garantizada la exlusión mutua porque un proceso llega a sulínea c: solamente si el valor de v corresponde a suidentificación (que asumimos siendo única).

Obviamente, los procesos pueden acceder al recurso solamentealternativamente, que puede ser inconveniente porque acopla losprocesos fuertemente.

Un proceso no puede entrar más de una vez seguido en lasección crítica.

Si un proceso termina el programa o no llega más por algunarazón a su línea d:, el otro proceso puede resultar bloqueado.

La solución se puede ampliar fácilmente a más de dos procesos.


primer intento en Java (comenzar es fácil)

El protocolo del primer intento para implementar un ping pong.

public class PingPong {volatile static int turn; // It's v.

public static void main(String[] args) {Thread ping1 = new Player(1);Thread ping2 = new Player(2);

ping1.start();ping2.start();

turn=1;}



class Player extends Thread {private int id;public Player(int id) { this.id=id; }public void run() {while(true) { // a:

while(id!=PingPong.turn // b:

);System.out.print("ping"+id+" ");// c:PingPong.turn=id%2+1; // d:

} // f:}

}


Excurso: primer intento en Java (terminar no tanto)

un método para abreviar:

static void Wait(int us) {try {Thread.sleep(us);

} catch(InterruptedException e) {System.out.println("sleeping interrupted");

}}

}



public class PingPong {volatile static int turn; // It's v.public static void main(String[] args) {

Thread ping1 = new Player(1);Thread ping2 = new Player(2);ping1.start();ping2.start();System.out.println("playing some seconds");turn=1;Wait(2000);System.out.println("waiting for players");turn=3; // Try to stop :-)try {ping1.join();ping2.join();

}catch(InterruptedException e) {System.out.println("got interrupted");

}System.out.println("finished");



class Player extends Thread {private int id;public Player(int id) { this.id=id; }public void run() {while(true) { // a:

while(id!=PingPong.turn // b:

);System.out.print("ping"+id+" ");// c:PingPong.turn=id%2+1; // d:

} // f:}

}



class Player extends Thread {private int id;public Player(int id) { this.id=id; }public void run() {while(PingPong.turn!=3) {while(

id!=PingPong.turn &&PingPong.turn!=3

);System.out.print("ping"+id+" ");if(PingPong.turn==id) {

PingPong.turn=id%2+1;}

}}

}



class Player extends Thread {private int id;public Player(int id) { this.id=id; }public void run() {while(PingPong.turn!=3) {while(

id!=PingPong.turn &&PingPong.turn!=3

);System.out.print("ping"+id+" ");if(PingPong.turn==id) {

PingPong.Wait(100); // And blocking!!!PingPong.turn=id%2+1;

}}

}}


segundo intento

Intentamos evitar la alternancia. Usamos para cada proceso unavariable, v0 para P0 y v1 para P1 respectivamente, que indican si elcorrespondiente proceso está usando el recurso.

P0 P1a: loop loopb: wait until v1 equals false wait until v0 equals falsec: set v0 to true set v1 to trued: critical section critical sectione: set v0 to false set v1 to falsef: non-critical section non-critical sectiong: endloop endloop


segundo intento: propiedades

Ya no existe la situación de la alternancia.

Sin embargo: el algoritmo no es correcto, porque los dosprocesos pueden alcanzar sus secciones críticassimultáneamente.

El problema está escondido en el uso de las variables de control.v0 se debe cambiar a verdadero solamente si v1 sigue siendofalso.

¿Cuál es la intercalación maligna?


tercer intento

Cambiamos el lugar donde se modifica la variable de control:

P0 P1a: loop loopb: set v0 to true set v1 to truec: wait until v1 equals false wait until v0 equals falsed: critical section critical sectione: set v0 to false set v1 to falsef: non-critical section non-critical sectiong: endloop endloop


tercer intento: propiedades

Está garantizado que ambos procesos no entren al mismotiempo en sus secciones críticas.

Pero se bloquean mutuamente en caso que lo intentensimultaneamente que resultaría en una espera infinita.



cuarto intento

Modificamos la instrucción c: para dar la oportunidad que el otroproceso encuentre su variable a favor.

P0 P1a: loop loopb: set v0 to true set v1 to truec: repeat repeatd: set v0 to false set v1 to falsee: set v0 to true set v1 to truef: until v1 equals false until v0 equals falseg: critical section critical sectionh: set v0 to false set v1 to falsei: non-critical section non-critical sectionj: endloop endloop


cuarto intento: propiedades

Está garantizado la exclusión mutua.

Se puede producir una variante de bloqueo: los procesos hacenalgo pero no llegan a hacer algo útil (livelock)



algoritmo de Dekker: quinto intento

Initially: v0,v1 are equal to false, v is equal to P0 o P1

P0 P1a: loop loopb: set v0 to true set v1 to truec: loop loopd: if v1 equals false exit if v0 equals false exite: if v equals P1 if v equals P0f: set v0 to false set v1 to falseg: wait until v equals P0 wait until v equals P1h: set v0 to true set v1 to truei: fi fij: endloop endloopk: critical section critical sectionl: set v0 to false set v1 to falsem: set v to P1 set v to P0n: non-critical section non-critical sectiono: endloop endloop


quinto intento: propiedades

El algoritmo de Dekker resuelve el problema de exclusión mutua en elcaso de dos procesos, donde se asume que la lectura y la escritura deun valor íntegro de un registro se puede realizar de forma atómica.


algoritmo de Peterson

P0 P1a: loop loopb: set v0 to true set v1 to truec: set v to P0 set v to P1d: wait while wait whilee: v1 equals true v0 equals truef: and v equals P0 and v equals P1g: critical section critical sectionh: set v0 to false set v1 to falsei: non-critical section non-critical sectionj: endloop endloop


algoritmo de Lamport

o algoritmo de la panadería:

cada proceso tira un ticket (que están ordenados en ordenascendente)

cada proceso espera hasta que su valor del ticket sea el mínimoentre todos los procesos esperando

el proceso con el valor mínimo accede la sección crítica


algoritmo de Lamport: observaciones

ya se necesita un cerrojo (acceso con exclusión mutua) paraacceder a los tickets,

el número de tickets no tiene límite,

los procesos tienen que comprobar continuadamente todos lostickets de todos los demás procesos.

El algoritmo no es verdaderamente practicable dado que senecesita un número infinito de tickets y un número elevado decomprobaciones.

Si se sabe el número máximo de participantes basta con unnúmero fijo de tickets.


otros algoritmos

Como vimos, el algoritmo de Lamport (algoritmo de la panadería)necesita muchas comparaciones de los tickets para n procesos.

Existe una versión de Peterson que usa solamente variablesconfinadas a cuatro valores.

Existe una generalización del algoritmo de Peterson para nprocesos (filter algorithm).

Se puede evitar la necesidad de un número infinito de tickets, sise conoce antemano el número máximo de participantes(uso de grafos de precedencia).

Otra posibilidad es al algoritmo de Eisenberg–McGuire(que garantiza una espera mínima para n procesos).


límites

Se puede comprobar que se necesita por lo menos n campos enla memoria común para implementar un algoritmo (con loadand store) que garantiza la exclusión mutua entre n procesos.


Operaciones en la memoria

Si existen instrucciones más potentes (que los simples load ystore) en el microprocesador se puede realizar la exclusiónmutua más fácil.

Hoy (casi) todos los procesadores implementan un tipo deinstrucción atómica que realiza algún cambio en la memoria almismo tiempo que devuelve el contenido anterior de la memoria.

La idea principal es implementar ciclos de read-modify-write deforma atómica directamente en memoria compartida.


TAS

La instrucción test-and-set (TAS) implementa

una comprobación a cero del contenido de una variable en lamemoria

al mismo tiempo que varía su contenido

en caso que la comprobación se realizó con el resultadoverdadero.


TAS

Initially: vi is equal falseC is equal true

a: loopb: non-critical sectionc: loopd: if C equals true ; atomic

set C to false and exite: endloopf: set vi to trueg: critical sectionh: set vi to falsei: set C to truej: endloop


TAS: propiedades

En caso de un sistema multi-procesador hay que tener cuidadoque la operación test-and-set esté realizada en la memoriacompartida.

Teniendo solamente una variable para la sincronización de variosprocesos el algoritmo arriba no garantiza una espera limitada detodos los procesos participando.¿Por qué?

¿Cómo se puede garantizar una espera limitada?

Para conseguir una espera limitada se implementa un protocolode paso de tal manera que un proceso saliendo de su seccióncrítica da de forma explícita paso a un proceso esperando (encaso que tal proceso exista).


EXCH

La instrucción exchange:

intercambia un registro del procesador

con el contenido de una dirección de la memoria

en una instrucción atómica.


EXCH

Initially: vi is equal falseC is equal true

a: loopb: non-critical sectionc: loopd: exchange C and vi ; atomic exchangee: if vi equals true exitf: endloopg: critical sectionh: exchange C and vii: endloop


EXCH: propiedades

Se observa lo mismo que en el caso anterior de TAS, no segarantiza una espera limitada.

¿Cómo se consigue?


F&A

La instrucción fetch-and-increment o fetch-and-add

aumenta el valor de una variable en la memoria

y devuelve el resultado

en una instrucción atómica.

Con dicha instrucción se puede realizar los protocolos de entraday salida.

¿Cómo?

También existe en la versión fetch-and-add que en vez deincrementar suma un valor dado de forma atómica.


CAS

La instrucción compare-and-swap (CAS) es unageneralización de la instrucción test-and-set.

La instrucción trabaja con dos variables, les llamamos C (decompare) y S (de swap).

Se intercambia el valor en la memoria por S si el valor en lamemoria es igual que C.

Es la operación que se usa por ejemplo en los procesadores deIntel y es la base para facilitar la concurrencia en la máquinavirtual de Java 1.5 para dicha familia de procesadores.

Con CAS se pueden realizar los protocolos de entrada y salida.¿Cómo?


double CAS

Existen también unas mejoras del CAS, llamadodouble-compare-and-swap DCAS (Motorola), que realiza dos CASnormales a la vez, o double-wide compare-and-swap (Intel/AMD x86),que opera con dos punteros a la vez para el intercambio, osingle-compare double-swap (Intel itanium), que compara un valor(puntero) pero escribe dos punteros en memoria adyacente.El código, expresado a alto nivel, para DCAS sería:

if C1 equal to V1 and C2 equal to V2then

swap S1 and V1swap S2 and V2return true

elsereturn false


Uso de memoria común

como hemos visto todos los protocolos necesitan variables conacceso atómico en memoría común.

Tal hecho puede resultar en pérdidas de rendimiento, si existeuna jerarquía de memoria con diferentes niveles de cachés.

Muchos compiladores ofrecen acceso directo a las instruccionesde nivel bajo, por ejemplo la gama de compiladores GCC con susatomic builtins,(https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html)

Nuevas versiones ya lo hacen diferente(https://gcc.gnu.org/onlinedocs/gcc-8.3.0/gcc/)

Mirad por ejemplo: https://gcc.gnu.org/onlinedocs/gcc-8.3.0/libstdc++/manual/

y su cuaderno de bitácora que menciona los cambios a lo largode los años


https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html

https://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html

https://gcc.gnu.org/onlinedocs/gcc-8.3.0/gcc/

https://gcc.gnu.org/onlinedocs/gcc-8.3.0/libstdc++/manual/

https://gcc.gnu.org/onlinedocs/gcc-8.3.0/libstdc++/manual/

ABA problemno se transmite information

los protocolos de entrada y salida como implementados hastaahora no transmiten información de un hilo al otro

en el sentido que si un hilo entra en su sección crítica dos veces

no puede averiguar si otro hilo ha (o otros hilos han) entradomientras tanto

este problema se conoce como ABA-problema (la secuenciaprimero A, luego B, después A, no se puede distinguir del simplehecho solo A)

el problema es, por ejemplo, relevante si se compara solopunteros o referencias para averiguar posibles cambios deestado

por ejemplo en acciones sobre listas compartidas (secuencias deborrar e insertar)


problema

Un bloqueo se produce cuando un proceso está esperando algo quenunca se cumple.Ejemplo:Cuando dos procesos P0 y P1 quieren tener acceso simultaneamentea dos recursos r0 y r1, es posible que se produzca un bloqueo deambos procesos. Si P0 accede con éxito a r1 y P1 accede con éxito ar0, ambos se quedan atrapados intentando tener acceso al otrorecurso.


condiciones necesarias

Se tienen que cumplir cuatro condiciones para que sea posible que seproduzca un bloqueo entre procesos:

1 los procesos tienen que compartir recursos con exclusión mutua2 los procesos quieren acceder a un recurso más mientras ya

tienen acceso exclusivo a otro3 los recursos solo permiten ser usados por menos procesos que

lo intentan al mismo tiempo4 existe una cadena circular entre peticiones de procesos y

asignaciónes de recursos


funcionamiento parcial

Un problema adicional con los bloqueos es que es posible que elprograma siga funcionando correctamente según la definición, esdecir, el resultado obtenido es el resultado deseado, pero algunos desus procesos están bloqueados durante la ejecución (es decir, seprodujo solamente un bloqueo parcial).


técnicas de actuar

Existen algunas técnicas que se pueden usar para que no seproduzcan bloqueos:

Detectar y actuar

Evitar

Prevenir


detectar y actuar

Se implementa un proceso adicional que vigila si los demás formanuna cadena circular.Más preciso, se define el grafo de asignación de recursos:

Los procesos y los recursos representan los nodos de un grafo.

Se añade cada vez una arista entre un nodo tipo recurso y unnodo tipo proceso cuando el proceso ha obtenido accesoexclusivo al recurso.

Se añade cada vez una arista entre un nodo tipo recurso y unnodo tipo proceso cuando el proceso está pidiendo accesoexclusivo al recurso.

Se eliminan las aristas entre proceso y recurso y al revés cuandoel proceso ya no usa el recurso.


actuación

Cuando se detecta en el grafo resultante un ciclo, es decir, cuando yano forma un grafo acíclico, se ha producido una posible situación deun bloqueo.Se puede reaccionar de dos maneras si se ha encontrado un ciclo:

No se da permiso al último proceso de obtener el recurso.

Sí, se da permiso, pero una vez detectado el ciclo se abortatodos o algunos de los procesos involucrados.


desventaja

Sin embargo, las técnicas pueden dar como resultado que elprograma no avance, incluso, el programa se puede quedar atrapadohaciendo trabajo inútil: crear situaciones de bloqueo y abortarprocesos continuamente.


evitar

El sistema no da permiso de acceso a recursos si es posible que elproceso se bloquee en el futuro.Un método es el algoritmo del banquero (Dijkstra) que es un algoritmocentralizado y por eso posiblemente no muy practicable en muchassituaciones.Se garantiza que todos los procesos actuan de la siguiente manera endos fases:

1 primero se obtiene todos los cerrojos necesarios para realizaruna tarea, eso se realiza solamente si se puede obtener todos ala vez,

2 después se realiza la tarea durante la cual posiblemente seliberan recursos que no son necesarias.


prevenir

Se puede prevenir el bloqueo siempre y cuando se consiga quealguna de las condiciones necesarias para la existencia de un bloqueono se produzca.

1 los procesos tienen que compartir recursos con exclusión mutua2 los procesos quieren acceder a un recurso más mientras ya

tienen acceso exclusivo a otro3 los recursos no permiten ser usados por más de un proceso al

mismo tiempo4 existe una cadena circular entre peticiones de procesos y

alocación de recursos


prevenir exclusión mutua

los procesos tienen que compartir recursos con exclusión mutua:

No se de a un proceso directamente acceso exclusivo al recurso,si no se usa otro proceso que realiza el trabajo de todos losdemás manejando una cola de tareas (por ejemplo, un demoniopara imprimir con su cola de documentos por imprimir).


prevenir accesos consecutivos

los procesos quieren acceder a un recurso más mientras ya tienenacceso exclusivo a otro:

Se exige que un proceso pida todos los recursos que va a utilizaral comienzo de su trabajo


prevenir uso único

los recursos no permiten ser usados por más de un proceso al mismotiempo:

Se permite que un proceso aborte a otro proceso con el fin deobtener acceso exclusivo al recurso. Hay que tener cuidado deno caer en livelock

(Separar lectores y escritores alivia este problema también.)


prevenir ciclos

existe una cadena circular entre peticiones de procesos y alocaciónde recursos:

Se ordenan los recursos línealmente y se fuerza a los procesosque accedan a los recursos en el orden impuesto. Así esimposible que se produzca un ciclo.


Bloqueo en Java

Un ejemplo de un bloqueo en Java muestra el siguiente trozo decódigo, incluso si se asume que un hilo ya está durmiendo. ¿Por qué?

hilo0: hilo1:

synchronized(A) { synchronized(B) {... ...synchronized(B) { synchronized(A) {... ...A.notify(); B.notify();B.wait(); A.wait();

} }} }


seguridad y vivacidad/viveza

Un programa concurrente puede fallar por varias razones, las cualesse pueden clasificar entre dos grupos de propiedades:

seguridad: Esa propiedad indica que no está pasando nada maloen el programa, es decir, el programa no ejecutainstrucciones que no deba hacer (“safety property”).

vivacidad: Esa propiedad indica que está pasando continuamentealgo bueno durante la ejecución, es decir, el programaconsigue algún progreso en sus tareas o en algúnmomento en el futuro se cumple una cierta condición(“liveness property”).


propiedades de seguridad

Las propiedades de seguridad suelen ser algunas de las invariantesdel programa que se tienen que introducir en las comprobaciones delfuncionamiento correcto.

Corrección: El algoritmo usado es correcto.

Exclusión mutua: El acceso con exclusión mutua a regiones críticasestá garantizado

Sincronización: Los procesos cumplen con las condiciones desincronización impuestos por el algoritmo

Interbloqueo: No se produce ninguna situación en la cual todos losprocesos participantes quedan atrapados en unaespera a una condición que nunca se cumpla.


propiedades de vivacidadinanición

Un proceso puede “morirse” por inanición (starvation), es decir,un proceso o varios procesos siguen con su trabajo pero otrosnunca avanzan por ser excluidos de la competición por losrecursos (por ejemplo en Java el uso de suspend() yresume() no está recomendado por esa razón).

Existen problemas donde la inanición no es un problema real oes muy improbable que ocurra, es decir, se puede aflojar lascondiciones a los protocolos de entrada y salida.


propiedades de vivacidad

Bloqueo activo: Puede ocurrir el caso que varios procesos estáncontinuamente competiendo por un recurso de formaactiva, pero ningúno de ellos lo consigue (“livelock”).

Cancelación: Un proceso puede ser terminado desde fuera sin motivocorrecto, dicho hecho puede resultar en un bloqueoporque no se ha considerado la necesidad que elproceso debe realizar tareas necesarias para liberarrecursos (por ejemplo, en Java el uso del stop() noestá recomendado por esa razón).

Espera activa: Un proceso está comprobando continuamente unacondición malgastando de esta manera tiempo deejecución del procesador.


justicia entre procesos

Cuando los procesos compiten por el acceso a recursos compartidosse pueden definir varios conceptos de justicia, por ejemplo:

justicia débil: si un proceso pide acceso continuamente, le será dadoen algún momento,

justicia estricta: si un proceso pide acceso infinitamente veces, leserá dado en algún momento,

espera limitada: si un proceso pide acceso una vez, le será dadoantes de que otro proceso lo obtenga más de una vez,

espera ordenada en tiempo: si un proceso pide acceso, le será dadoantes de todos los procesos que lo hayan pedido mástarde.


comentarios

Los dos primeros conceptos son conceptos teóricos porquedependen de términos infinitamente o en algún momento, sinembargo, pueden ser útiles en comprobaciones formales.

En un sistema distribuido la ordenación en tiempo no es tan fácilde realizar dado que la noción de tiempo no está tan clara.

Normalmente se quiere que todos los procesos manifesten algúnprogreso en su trabajo (pero en algunos casos inanicióncontrolada puede ser tolerada).


espera activa de procesos

El algoritmo de Dekker y sus parecidos provocan una esperaactiva de los procesos cuando quieren acceder a un recursocompartido. Mientras están esperando a entrar en su regióncrítica no hacen nada más que comprobar el estado de algunavariable.

Normalmente no es aceptable que los procesos permanezcan enestos bucles de espera activa porque se está gastando potenciadel procesador inútilmente.

Un método mejor consiste en suspender el trabajo del proceso yreanudar el trabajo cuando la condición necesaria se hayacumplido. Naturalmente dichos técnicas de control son máscomplejas en su implementación que la simple espera activa.


evitar espera infinita o inanición de procesos

Se implementa, por ejemplo, el acceso a recursos compartidossiguiendo un orden FIFO, es decir, los procesos tienen acceso enel mismo orden en que han pedido vez.

Se asignan prioridades a los procesos de tal manera que cuantomás tiempo un proceso tiene que esperar más alto se pone suprioridad con el fin que en algún momento su prioridad sea lamás alta.

¡Ojo! ¿Qué se hace si todos tienen la prioridad más alta?

Existen más técnicas... ¿Cuáles?


algunas herramientas para C/C++ (no exhaustivas)

ACE (Adaptive Communications Environment)http://www.cs.wustl.edu/~schmidt/ACE.html(usa patrones de diseño de alto nivel, p.ej.; proactor)

Intel Concurrent Collections (C++, 2012, versión 0.7)http://software.intel.com/en-us/articles/intel-concurrent-collections-for-cc/ (lenguajede preprocesado para expresar concurrencia)

Cilk/Cilk++/Cilk Plus (2011)http://software.intel.com/en-us/articles/intel-cilk-plus/(extensión de C/C++ para expresar concurrencia)

Intel Thread Building Blocks (2012, version 4.0)http://threadingbuildingblocks.org/(C++ template librería para expresar concurrencia)


http://www.cs.wustl.edu/~schmidt/ACE.html

http://software.intel.com/en-us/articles/intel-concurrent-collections-for-cc/

http://software.intel.com/en-us/articles/intel-concurrent-collections-for-cc/

http://software.intel.com/en-us/articles/intel-cilk-plus/

http://software.intel.com/en-us/articles/intel-cilk-plus/

http://threadingbuildingblocks.org/

algunas herramientas para C/C++ (no exhaustivas)

OpenMPhttp://openmp.org/wp/(C-preprocessor (+librería embebido) para expresarconcurrencia)

Noble (www.non-blocking.com)

Qt threading library (http://doc.qt.nokia.com/)

pthreads, boost::threads, Zthreads(uso directo de programación multi-hilo)

próximo/ya estándar de C++ (C++11, 2011)(http://www.open-std.org/jtc1/sc22/wg21/)

Usa la Red para buscar más información, aquí unos ejemplos.


http://openmp.org/wp/

www.non-blocking.com

http://doc.qt.nokia.com/

http://www.open-std.org/jtc1/sc22/wg21/

Date post:	26-Jul-2020
Category:	Documents
Upload:	others
View:	0 times
Download:	0 times

Concurrencia y Distribuciónformella.webs.uvigo.es/doc/cdg18/cdi.pdfprofesorado (prácticas)...

Documents