Samenvatting
Samenvatting van Concurrency
- Instelling
- Universiteit Utrecht (UU)
Samenvatting van het vak Concurrency aan de Universiteit Utrecht, gebaseerd op de hoorcolleges.
[Meer zien]Voorbeeld 3 van de 18 pagina's
Voorbeeld 3 van de 18 pagina's
In winkelwagengesponsord bericht van onze partner
Voorbeeld van de inhoud
Basic definitionsConcurrency: composition of independently executing processes. Tasks are concurrent with respect to each other if they
may be executed out-of-order (which implies they could be executed at the same time).
Parallelism: simultaneous execution of (possibly related) computations. Tasks are parallel if they are executed
simultaneously. Parallelism requires multiple processing elements. Primary motivation is to reduce the overall running time
of the program.
A computation is embarrassingly parallel if each element of the computation is independent of the others (and thus
little or no effort is needed to separate the problem into multiple parallel tasks).
A program can be:
Concurrent, not parallel: Makes progress on more than one task seemingly at the same time (concurrently), but the
application switches between making progress on each of the tasks.
Parallel, not concurrent: The application only works on one task at a time, but this task is broken into multiple
subtasks which can be executed simultaneously.
Neither concurrent nor parallel: Works on one task at a time, which is never broken down in subtasks.
Concurrent and parallel: Making progress simultaneously at multiple tasks.
Threads and sharing state
Shared (mutable) states make concurrency challenging: multiple threads can access the same memory location at the
same time.
Threads of a process usually do not compete, but cooperate:
Compete for resources.
Processes may not be aware of each other.
Executing must not be affected by each other.
OS is responsible for controlling access.
Cooperate by sharing a common recourse.
Programmer responsible for controlling access.
Hardware / OS / programming language may provide support.
,Concurrency control properties
Linearisability / atomic operation: Operations are atomic if they run completely independently from any other processes,
where no other process must be able to interrupt the function mid-execution. Effects, thus, become visible to other threads
all at once.
Fairness: When we consider fairness, we consider a process gets a fair chance of acquiring the lock when it is set free.
Problems
Deadlock: each member of a group of processes is waiting for another process to take action (e.g. to release a
resource/lock).
Livelock: the 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 it fails).
Starvation: when a process is constantly denied access to necessary resources to process its work.
Non-blocking algorithms
An algorithm is non-blocking, if failure or suspension of any thread cannot cause suspension of another thread.
Wait-freedom: Guaranteed per-thread progress.
Every method will finish in a finite number of steps – regardless of other processes.
Wait-freedom lock-freedom.
Lock-freedom: Guaranteed system-wide progress.
Some method will finish in a finite number of steps.
Allows individual threads to starve but guarantees system-wide throughput.
Obstruction-freedom.
From any point after a thread begins executing in isolation, it finishes in a finite number of steps.
A thread will be able to finish if no other thread makes progress.
Blocking algorithms
Starvation-freedom.
When starvation is impossible, thus if a process wants to execute the critical section code, then that process
eventually executes it.
Starvation-freedom deadlock-freedom.
Deadlock-freedom.
, Mutual exclusion (Mutex)
Critical resources critical sections. Idea is to protect shared resources:
Only one process at the time should be allowed access to a critical section (e.g. only one process at the time is
allowed to send commands to the GPU).
Modification to the resource should appear to happen atomically.
Approaches to mutual exclusion
Approach 1: Using a shared variable turn and letting a thread loop until it is in turn.
Provides mutual exclusion, but causes threads to always be busy waiting (spin lock) and requires processes to
alternate access to the critical section.
If one process fails anywhere in the program, the others are permanently blocked.
Approach 2: Store for each process whether it is in the critical section right now, accessible using flag[i] .
If a process fails outside critical sections, then the other is not blocked.
If process fails inside critical sections, then the others are blocked.
This method does also not guarantee exclusive access, because of the gap between checking status of other
thread and setting their own flag to true.
1st fix to approach 2: Move setting the thread’s flag to before checking whether we can enter.
Does not work either, because now the gap can cause a deadlock.
2nd fix to approach 2: Let a process retract its decision if it cannot enter.
This approach is close, but now we might cause a livelock.
Combining the 1st approach with the last fix may solve the previous problem: in addition to the flag s, we use a variable
indicating whose turn it is to have precedence in entering the critical section. This is Peterson’s algorithm.
Provides mutual exclusion: For both and to be in the critical section: flag[0] AND flag[1] AND turn=0
AND turn=1 , which is not possible as turn is their shared variable.
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 pactasuntservanda. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €5,09. Je zit daarna nergens aan vast.
Is Stuvia te vertrouwen?
4,6 sterren op Google & Trustpilot (+1000 reviews)
Afgelopen 30 dagen zijn er 77988 samenvattingen verkocht
Opgericht in 2010, al 14 jaar dé plek om samenvattingen te kopen