Resume
Summary Concurrency (INFOB3CC)
- Cours
- Établissement
All subjects that are discussed in the Concurrency course, clearly summarized in a structured way. Based on the lectures and the slides.
[Montrer plus]
2 revues
Par: rowinschouten1 • 2 année de cela
Par: cardriver44 • 2 année de cela
Vendeur
S'abonner
Suniht
Avis reçus
Aperçu du contenu
ConcurrencyGeneral 1
Mutual exclusion 2
Software approach 3
Hardware approach 4
State sharing 5
Dataflow computations 6
Software Transactional Memory 8
Parallelism 12
Hardware perspective 13
SIMD 13
Software perspective 15
Speedup 16
GPGPU 18
GPU architecture 18
Execution model 19
Programming model 20
Accelerate 24
Data parallelism 25
Patterns 25
Performance analysis 30
,General
Concurrency Composition of independently executing processes
Multiple tasks occurring at the same time in any given order without conflict
- Dealing with lots of things at once
- Collection of independently executing processes
- Two or more threads are making progress
- How to structure your program
Parallelism Simultaneous execution of (possibly related) computations
- Doing lots of things at once
- At least two threads are executing simultaneously
- Parallelism can be achieved through the use of concurrency
Concurrency Concurrency + parallelism
(Single-Core CPU) (Multi-Core CPU)
___ ___ ___
|th1| |th1|th2|
| | | |___|
|___|___ | |___
|th2| |___|th2|
___|___| ___|___|
|th1| |th1|
|___|___ | |___
|th2| | |th2|
Tasks are concurrent with respect to each other if:
- They may be executed out-of-order
- Implies they can be executed at the same time (but this is not required)
Tasks are parallel if they are executed simultaneously:
- Requires multiple processing elements
- The primary motivation for parallel programming is to reduce the overall running time of
the program: parallel execution
Multithreading: concurrent threads share an address space
Multiprogramming: concurrent processes execute on a uniprocessor
Multiprocessing: concurrent processes on a multiprocessor
Distributed processing: concurrent processes executing on multiple nodes connected by a
network
Atomic action A set of instructions that needs to be executed at once, and treated as if they
were just one instruction
- This can be enforced using a critical section, which forces processes to get a lock on the
section to be able to use it (only one thread gets access at a time)
- For example: appending a new node to the end of a linked list
1
, Access/Concurrency control
- Compete for resources
- Processes may not be aware of each other
- Execution must not be affected by each other
- OS is responsible for controlling access
- Cooperate by sharing a common resource
- Programmer responsible for controlling access
- Hardware/OS/programming language may provide support
Control problems
- Mutual exclusion: only one process at a time is allowed in a critical section
- Modifications to critical sections should appear to happen atomically
- Deadlock: processes need multiple resources and are dependant on each other to give
up (some of) the resources they need
- A lock is deadlock free if threads want to get the lock, and it is not currently being
used, they can can acquire it
- If failure of a process anywhere (outside critical section) causes other processes
to deadlock (cannot access lock anymore), then the lock is not deadlock free
- For example, attempt 1 of mutual exclusion, where one processes always
passes control to the other process and is dependant on that one passing
it back to obtain the lock again
- Livelock: states of the group of processes are constantly changing with regard to each
other, but none are progressing (e.g. trying to obtain a lock, but backing off if that fails to
give another thread the opportunity to obtain it, but the other thread is doing the same)
- Starvation: a process is trying to access a resource but is never allowed to
- Livelock can be a form of starvation
Properties required for concurrency control:
- Starvation-freedom: no starvation
- Deadlock-freedom: no deadlocking
- Mutual exclusion: only one thread allowed in some
block of code
- For example, the code on the right does not
provide mutual exclusion, because it is
possible for two threads to reach the
writeIORef ref True part
Mutual exclusion
→ Only one thread at a time is allowed in the critical
section for a resource
- This needs to be implemented without causing a deadlock or starvation on attempting to
enter or leave the critical section
Implementation requirements
- A thread must not be delayed access to a critical section when there is no other thread
using it
2
Les avantages d'acheter des résumés chez Stuvia:
Qualité garantie par les avis des clients
Les clients de Stuvia ont évalués plus de 700 000 résumés. C'est comme ça que vous savez que vous achetez les meilleurs documents.
L’achat facile et rapide
Vous pouvez payer rapidement avec iDeal, carte de crédit ou Stuvia-crédit pour les résumés. Il n'y a pas d'adhésion nécessaire.
Focus sur l’essentiel
Vos camarades écrivent eux-mêmes les notes d’étude, c’est pourquoi les documents sont toujours fiables et à jour. Cela garantit que vous arrivez rapidement au coeur du matériel.
Foire aux questions
Qu'est-ce que j'obtiens en achetant ce document ?
Vous obtenez un PDF, disponible immédiatement après votre achat. Le document acheté est accessible à tout moment, n'importe où et indéfiniment via votre profil.
Garantie de remboursement : comment ça marche ?
Notre garantie de satisfaction garantit que vous trouverez toujours un document d'étude qui vous convient. Vous remplissez un formulaire et notre équipe du service client s'occupe du reste.
Auprès de qui est-ce que j'achète ce résumé ?
Stuvia est une place de marché. Alors, vous n'achetez donc pas ce document chez nous, mais auprès du vendeur Suniht. Stuvia facilite les paiements au vendeur.
Est-ce que j'aurai un abonnement?
Non, vous n'achetez ce résumé que pour €8,99. Vous n'êtes lié à rien après votre achat.
Peut-on faire confiance à Stuvia ?
4.6 étoiles sur Google & Trustpilot (+1000 avis)
84669 résumés ont été vendus ces 30 derniers jours
Fondée en 2010, la référence pour acheter des résumés depuis déjà 14 ans