Summary
Summary Concurrency (INFOB3CC)
- Course
- Institution
All subjects that are discussed in the Concurrency course, clearly summarized in a structured way. Based on the lectures and the slides.
[Show more]
2 reviews
By: rowinschouten1 • 2 year ago
By: cardriver44 • 2 year ago
Seller
Follow
Suniht
Reviews received
Content preview
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
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 Suniht. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $9.77. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
64438 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now