Samenvatting
Summary Concurrency (INFOB3CC)
- Instelling
- Universiteit Utrecht (UU)
All subjects that are discussed in the Concurrency course, clearly summarized in a structured way. Based on the lectures and the slides.
[Meer zien]Voorbeeld 3 van de 34 pagina's
Voorbeeld 3 van de 34 pagina's
In winkelwagengesponsord bericht van onze partner
2 beoordelingen
Door: rowinschouten1 • 2 jaar geleden
Door: cardriver44 • 2 jaar geleden
Voorbeeld van de inhoud
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
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper Suniht. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €8,99. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 66579 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen