Summary
Summary Summar of the course 'Concurrency'
- Course
- Institution
Summary of the course Concurrency at Utrecht University, based on the lectures.
[Show more]
Seller
Follow
pactasuntservanda
Reviews received
Content preview
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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller pactasuntservanda. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $5.53. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
78075 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now