36
votes
Why must uncommitted transactions be undone in backwards order?
Original transactions:
Insert record $r$.
Update some field $f$ of $r$.
Forward undo:
Delete record $r$.
Reverse the update to $r$ - oh wait, $r$ no longer exists! This causes an error.
- 865
17
votes
Accepted
Is it possible for a stack-based programming language to be concurrent?
So, can stack-based programming languages be concurrent?
Sure.
Could they achieve concurrency by using multiple stacks at the same time or something alike?
Already for normal languages multi-...
13
votes
Accepted
Why is quiescent consistency compositional, but sequential consistency is not
Sorry for the late reply, but I've just found the question (questions, indeed). I am studying concurrency as well and I'll try to share some ideas with you.
First, let's start with sequential ...
- 186
12
votes
Why must uncommitted transactions be undone in backwards order?
To add to DylanSp's answer, trying to update a field in a non-existing record will fail, but the result will still be the expected result: record r does not exist.
However, consider a situation where ...
- 276
8
votes
Is it possible for a stack-based programming language to be concurrent?
I know a bit about FORTH so I will confine myself to that. It is a low level language, giving you as programmer access to all the hardware resources. So you can do whatever you like.
Concurrency
In ...
- 416
7
votes
Accepted
Why there must be a relationship between user threads and kernel threads?
This section of the book appears to be talking about how the details of the threading and scheduling are implemented for a user mode program.
When threading first became popular, most operating ...
- 751
7
votes
Why are multi-threading programs more prone to errors?
Overview
Multi-threaded programs are more prone to errors than single-threaded programs because of the problem of concurrency bugs. Concurrency is hard for most developers to reason about, which ...
D.W.♦
- 154k
7
votes
Why must uncommitted transactions be undone in backwards order?
Let's go by analogy: say you're going out for dinner.
Put socks on.
Put shoes on.
Stand up.
Walk to door.
Then you get a phone call. Dinner plans cancelled.
Take socks off.
Take shoes off.
Sit ...
- 171
7
votes
Write Serialization for Cache Coherence in the presence of Store Buffers
From a coherence perspective, I think your example is coherent. All processors believe that the write and read from A happened first, then the write and read from B happened later.
From a ...
- 17.6k
7
votes
Accepted
Does mutual exclusion hold in this case?
Your friend is correct. In your context, mutual exclusion holds if at most one process is at a critical section at any given time.
You state that you feel that this interpretation is wrong, but you ...
- 274k
7
votes
Accepted
Why $e(C_i) = D_i$ is correct assumption? (FLP Impossibility 1985 - Lemma 3)
The paper says
By an easy induction, there exist neighbors $C_0, C_1 \in \mathscr{C}$ such that $D_i = e(C_i)$ is $i$-valent, $i = 0, 1$
Here is a proof:
The set of configurations forms the nodes ...
- 3,290
7
votes
Accepted
Why are most mutex implementations unfair?
Jim Sawyer's answer points to one answer: When you have threads with differing priorities, "fair" behaviour would be incorrect. When you have multiple threads which could run, the highest priority ...
- 21.3k
6
votes
Accepted
User level threads are transparent to the kernel?
As, the linked answers and the explanations provided by your textbooks describe that, user level threads are transparent to the kernel, yes they are indeed.
Kernel Level threads are not transparent ...
- 429
6
votes
Accepted
example for weakly fair v.s. strongly fair scheduling in concurrency
If you are familiar with temporal logic, the difference is quite easy to demonstrate:
Weak fairness is $FGp\to Fq$. That is, if $p$ holds from some point and on, then $q$ will hold eventually.
...
- 17k
6
votes
Accepted
Lamport’s fast mutual exclusion algorithm intuition
In what sense are this locks fast/slow?
Lamport optimizes for a very specific scenario, as pointed out in the paper:
The current belief among operating system designers is that contention
for a ...
- 294
6
votes
Accepted
What does synchronous and asynchronous mean in computer science?
As Discrete lizard suggests, there is not some precise CS-wide definition for these terms. Generally, you should not expect terms and notation to always mean the same thing even within a single field.
...
5
votes
What is the difference between user-level threads and kernel-level threads?
Think of kernel level threads as "virtual processors" and user level threads as simply threads (Let's call them as such for now). Now, for a thread to be executed, it has get assigned on to a ...
- 429
5
votes
Accepted
Good snapshottable data structure for an in-memory index
Use any kind of persistent/immutable (i.e., functional) tree-based data structure. The key is getting the locking right, as @Raphael pointed out in the comments.
The nice thing about functional/...
- 17.6k
5
votes
Difference between Parallel and Concurrent programming?
A slightly idealised answer, perhaps...
Concurrency is a property of how a program is written. If a program is written using constructions like forks/joins, locks, transactions, atomic compare-and-...
- 151
5
votes
Accepted
How does lack of deadlock relate to computability in process calculi?
I think you are asking about expressivity of concurrent programming languages. This is a deep and not well-understood field. For example you say that "the $\pi$-calculus [...] has the power to ...
- 8,308
5
votes
Write Serialization for Cache Coherence in the presence of Store Buffers
Situations like the one you describe are the reason why processor manuals for architectures with store buffers such as intel tend to state that two stores by cores i and j are seen in the same order ...
- 616
5
votes
Accepted
What is the abstract idea of a semaphore and how can we use it to implement mutual exclusion?
A semaphore is a counter, that counts the number of processes that have access to a resource. If a resource can service n processes, n is decremented each time a process accesses the resource, and ...
- 249
5
votes
Are Test and set primitives as powerful as semaphores?
Your hunch is correct, they aren't equivalent. Test-and-set has a consensus number of 2, which means, roughly speaking, that it is only able to efficiently synchronize between 2 processes. See Why is ...
5
votes
Cache coherence is worthless and does nothing?
It is false to assume that a write to a cache-line will cause a flush to main memory. Caches on modern CPUs are always coherent. Modern caches are also write behind caches meaning that in theory they ...
- 299
4
votes
Who needs linearizability?
First, linearizability and serializability are not directly comparable. As the table below shows, the main difference is that on the left hand side, all individual operations are atomic (like having a ...
4
votes
Contrasting Peterson’s and Dekker’s algorithms
In the following paper we give formal models for Peterson’s and Dekker’s algorithms (and some others) and we used model checker to prove their properties. Please, find our results in the table below (...
- 143
4
votes
Accepted
Using a counting semaphore as a binary semaphore
A binary semaphore is just a semaphore whose values are limited to 0 and 1 (locked and unlocked; when locked there can be an unlimited queue of tasks waiting). When using such a semaphore you have to ...
- 13.9k
4
votes
Accepted
Origin of the terms "safety" and "liveness" for concurrent algorithm properties?
Lamport commented on his paper "Proving the Correctness of Multiprocess Programs" as follows:
This paper introduced the concepts of safety and liveness as the proper generalizations of partial ...
- 9,461
4
votes
When do deadlocks occur?
All 4 conditions must be satisfied at the same time.
Hold and Wait
Non-preemption of resources
Mutual Exclusion
Circular wait
In case of single instance of resources:
Cycle in resource allocation ...
4
votes
How probable is a deadlock in the dining philosophers problem
the dining philosopher problem seems to be somewhat of a pedagogical "toy" example of concurrency and (dead)locking concepts for educational purposes. however it is studied seriously in some ...
- 11k
Only top scored, non community-wiki answers of a minimum length are eligible