Concurrency Flashcards
Name 3 things for every memory location from which at least 1 needs to be obayed when writing concurrent programs.
1) Thread local: Do not use the location in more than 1 thread
(How to: For example giving each thread a copy of the resource if they dont need to communicate e.g. distributed memory)
2) Immutable: Do not write to the memory location
(How to: For example by declaring variable as final)
3) Synchronized: Use synchronized access
What can a programmer do if he cant make a memory location thread-local or immutable, so that no bad interleavings happen? And how is this done?
By implementing mutual exclusion. This is done by defining critical sections (sections of code which only one thread at a time is allowed to execute)
What can a programmer do if he cant make a memory location thread-local or immutable, so that no bad interleavings happen? And how is this done?
By implementing mutual exclusion. This is done by defining critical sections (sections of code which only one thread at a time is allowed to execute)
When talking about concurrent algorithms how do we distinguish them? Hint: 2 type
blocking and non-blocking algorithms
Define blocking algorithms and name two further cases in which they are distinguished.
In blocking algorithms threads might occasionally go into a blocked state, for example when attempting to acquire a lock.
Deadlock-free: At least one thread is guaranteed to proceed into the critical section at some point.
Starvation free: All threads are guaranteed to proceed into the critical section at some point.
Define Deadlock-free and name to what type of concurrent algorithms this type belongs to.
To blocking algorithms.
Deadlock-free: At least one thread is guaranteed to proceed into the critical section at some point.
Define Starvation-Free and name to what type of concurrent algorithms this type belongs to.
To blocking algorithms.
Starvation free: All threads are guaranteed to proceed into the critical section at some point.
Define non-blocking algorithms and distinguish 2 further cases.
Threads never enter a blocked state, i.e. always continue execution. This suggests the algorithms dont use locks!
Lock-free: At least 1 thread always makes progress.
Wait-free: All threads make progress within a finite amount of time.
Define Lock-free and name the type of concurrent algorithm.
Non-Blocking concurrent algorithm.
Lock-free: At least 1 thread always makes progress.
Define Wait-free and name the type of concurrent algorithm.
Non-Blocking
Wait-free: All threads make progress within a finite amount of time.
Define the requirements for correct implementation of a critical section.
Deadlock-free: At least one thread can enter the critical section.
Mutually exclusive: At most one thread is in the critical section at a time.
