Questiont about issues of concurrency such as synchronization and deadlocks.

learn more… | top users | synonyms

1
vote
0answers
19 views

Bounded waiting and progress requirements of critical section problem solution based on exchange instruction

Atomic exchange instruction is given as follows: void exchange (int *a, int *b) { int temp; temp = *b; *b = *a; *a = temp; } Now consider the ...
4
votes
0answers
46 views

Is this solution to the dining philosopher's problem entirely valid?

In a question on Stack Overflow, the answer by Patrick Trentin lists the following solution to the dining philosopher's problem: A possible approach for avoiding deadlock without incurring ...
18
votes
5answers
3k views

Why must uncommitted transactions be undone in backwards order?

I have a database log where some transactions win (they are committed before crash) and some lose (not committed yet). We learned in class that the losers' actions have to be undone backwards. Is ...
4
votes
0answers
33 views

Deadlock free process calculi

So when programming with locks as a synchronization primitives you can ensure no deadlock by ensuring that an ordering exists on the locks and that all acquires of the locks happen in that order (...
4
votes
2answers
39 views

Is bounded waiting ensured in given version of Dekker's solution for critical section problem?

William Stallings discuss various step by step process in developing Dekker's algorithm in his Operating Systems book. In process, he reaches to following version of algorithm (which is incomplete as ...
0
votes
1answer
24 views

Concurrency: Is it order-independability or interruptibility of tasks?

After researching concurrency I am unable to discern if it is either of these specifically or it encapsulates both? I was also wondering if someone could provide some programming applications/real ...
4
votes
1answer
92 views

Lamport's Bakery algorithm

I have problems understanding Lamport's bakery algorithm. The thing I do understand is that each thread ask all other threads what number they have.Then the thread takes the maximum number and add 1 ...
0
votes
1answer
59 views

What does it mean that a core supports 2 threads?

I understand that a process may have multiple threads, and that a processor may have multiple cores to run processes in parallel. But I can't understand how a core may allow multiple threads, what ...
4
votes
0answers
84 views

What techniques could be used to support thread-local contexts and resources in a language?

I am interested in the subject of thread-local contexts, which is a feature that I use quite often in solutions, but seems to lack first-class support in any languages I have used. Quite often in ...
4
votes
2answers
75 views

How probable is a deadlock in the dining philosophers problem

I created this simulation of the dining philosophers problem, but did not manage to initialize it with four philosophers without running into a deadlock: *Philosophers are represented by black ...
2
votes
1answer
55 views

Exclusive queue problem

There is the exclusive queue problem in The Little Book of Semaphores, which is stated as follows: Imagine that threads represent ballroom dancers and that two kinds of dancers, leaders and followers,...
5
votes
1answer
123 views

Why is quiescent consistency compositional, but sequential consistency is not

I'm having trouble in comparing these two memory consistency models. Essentially for sequential consistency I think of real code like this: ...
1
vote
1answer
30 views

Confusion in the solution to first readers-writers synchronization

I am studying the solution to “First Readers-Writers Problem” from the book Operating System Concepts (9th edition) and it describes: First readers–writers problem, requires that no reader be kept ...
1
vote
1answer
32 views

Does the following modified Two-Phase Locking protocol ensure serializability and freedom from deadlock?

Consider the following variant of the two phase locking protocol. Suppose a transaction $T$ accesses (for read or write operations), a certain set of objects ${O_1,...,O_k}$. The modified algorithm ...
1
vote
1answer
52 views

example for weakly fair v.s. strongly fair scheduling in concurrency

I am having difficult time understanding the difference between weakly fair and strongly fair schedulers. Can someone provide an example and explain how they are different? for reference, here are ...
-2
votes
1answer
44 views

Which process comes first?

Let's say we have 3 processes: Process 1 service time 6 arrival time 0 Process 2 service time 2 arrival time 1 Process 3 service time 5 arrival time 3 We know that: after 1 time, process 2 will ...
2
votes
2answers
41 views

How can another process call $signal()$ when one process is executing $wait()$ in its busy waiting loop?

A semaphore is a variable that, apart from initialization is accessed through only two standard atomic operations wait(s) and signal(s). ...
1
vote
2answers
51 views

Question on synchronisation

The following two functions P1 and P2 that share a variable B with an initial value of 2 execute concurrently. ...
1
vote
1answer
56 views

Does the conservative two phase locking protocol produce cascadeless schedules?

Let us consider the following schedule : \begin{array}{lcr} \mbox{$T_1$} & \mbox{$T_2$}\\ \\ \mbox{lock-exclusive(a)} \\ \mbox{lock-exclusive(b)} \\ \mbox{read(a)} \\ \mbox{a=a+50} \\ \mbox{...
0
votes
1answer
118 views

User level threads are transparent to the kernel?

Find whether given statement True or False? Explain. User level threads are transparent to the kernel? My attempt : False. Since, user level threads are managed by a user level library ...
1
vote
1answer
43 views

Synchronisation and ordering in distributed systems

I have been wondering, what are some ways to handle synchronisation and/or sequencing issues in distributed systems. For example, assume multiple homogeneous nodes listening on a stream of messages ...
5
votes
2answers
161 views

Why are multi-threading programs more prone to errors?

Why are multi-threading programs more prone to errors than single threaded programs ? or why is multi-threading programming one of the areas where developers are (more) prone to errors? Is this in ...
1
vote
1answer
28 views

Proof for Transitivity of Weak Bisimulation ≈

I have already posted this question on the other page, but I was suggested to post it here as it might be more relevant. I am currently following a course in concurrency theory and I am currently ...
4
votes
3answers
156 views

When do deadlocks occur?

I was reading about deadlocks in Operating Systems. Where I came across two examples below. Circles with label $P_x$ are processes. Squares with label $R_x$ are resources. Each dot in the square ...
1
vote
0answers
38 views

Why use coroutines instead of mutable objects?

What scenarios would cause coroutines to be a better (i.e. more robust, easier to modify) answer than simple mutable objects? For example, in Fluent Python, the following running average example is ...
0
votes
0answers
61 views

How to express r-bounded waiting for $r=0,1,2$ in LTL and Promela?

How to express $r$-bounded waiting for $r=0,1,2$ in LTL? I'm having trouble expressing the above in LTL and translating it to Promela. I've already expressed starvation-free and mutual exclusion. ...
2
votes
2answers
52 views

Help understanding this algorithm that's supposed to solve the critical section problem through mutual exclusion

Our professor gave us the following algorithm that's supposed to solve the critical section problem. I'm guessing the code is just pseudocode so I'm not trying to focus on the strange syntax and just ...
2
votes
2answers
143 views

Why there must be a relationship between user threads and kernel threads?

The following is an excerpt from OS concepts by galvin.Here is the book. Multithreading Models Our discussion so far has treated threads in a generic sense. However, support for threads ...
0
votes
1answer
44 views

How do threads decide when to 'go'? [closed]

I have written some code that animates two boxes using HTML5 and JavaScript threads. I set them up to move at a fixed rate, which is the same: ...
2
votes
1answer
29 views

Operating Systems TestAndSet instruction

I was reading operating systems concurrency control topics where I came across TestAndSet() intruction. I first referred this book. But it has got very less ...
3
votes
0answers
33 views

Original proof that orders eliminate deadlocks?

A well-known approach to eliminate the possibility of a deadlock when accessing exclusive ressources is enforcing a partial (or total) order in which the ressources may be requested. Which ...
1
vote
1answer
120 views

Origin of the terms “safety” and “liveness” for concurrent algorithm properties?

Properties of concurrent algorithms are usually divided into two categories: Safety - something must not happen. Properties in this category are for example partial correctness and sometimes ...
8
votes
0answers
156 views

Are CPU architectures biased towards procedural runtimes?

Are there any changes that could be made to CPUs to make them perform better for concurrent runtimes like Rust? For instance, are there changes to branch prediction implementations or cache sizes ...
1
vote
2answers
80 views

How to prove if an algorithm is reentrant?

I think, maybe some formalism could exist for the task which makes it significantly easier. My problem to solve is that I invented a reentrant algorithm for a task. It is relative simple (its pure ...
2
votes
1answer
594 views

Understanding the one-writer, many-readers problem?

I need some help understanding the implementation of the one-writer many-readers problem shown below as I am new to this concept: I have a rough idea that there will be starvation/deadlock among ...
3
votes
1answer
337 views

Using a counting semaphore as a binary semaphore

Are there any methods, so that I can use a counting semaphore as a binary semaphore? A binary semaphore should have two possible states: 0 and ...
0
votes
1answer
100 views

A schedule is not conflict-serializable. Is it serializable?

While reading this solved quiz on concurrency control, I got stuck on exercise 2, which reads as follows: 2) Consider the following schedule: S: r1(X), w2(X), r3(X), r1(Y), w2(Z), r3(Y), w3(Z)...
2
votes
1answer
125 views

Difference between SRSW and MRSW safe Boolean registers

I'm reading The Art of Multiprocessor Programming and am currently trying to understand Chapter 4 — The Foundations of Shared Memory. In section 4.2 it is shown how to build a multi-reader, single-...
10
votes
2answers
188 views

Good snapshottable data structure for an in-memory index

I'm designing an in-memory object database for a very specific use case. It is single writer, but must support efficient concurrent reads. Reads must be isolated. There is no query language, the ...
5
votes
1answer
72 views

For a given certain situation how to prove that the system will never get into the state of Deadlock

The situation is as follows 'm' process shares 'n' resources of same type. The maximum need of each process does not exceed 'n' and the sum all their maximum needs is always less than m+n. In ...
8
votes
3answers
335 views

Why would you use a monitor instead of a semaphore?

I am currently attending the concurrent programming course in my university and we recently started talking about the concept of a monitor. While I understand the necessity of mutual exclusion, I do ...
3
votes
2answers
424 views

Implementing wait-free consensus with queues

Using Herlihy's model and definition of the wait-free hierarchy, a queue (a shared object with enqueue and dequeue) has consensus number 2, because we can initialize the queue with some value, and the ...
0
votes
1answer
406 views

Chandy/Misra dining philosophers solution

So based on the Chandy/Misra section in this Wikipedia article we've got 5 philosophers numbered P1-P5. Based on this quote: For every pair of philosophers contending for a resource, create a ...
1
vote
0answers
53 views

Processes concurrency

I am getting ready for my end of year exams and I got stuck on this question. Consider the following 3-process concurrent program which uses semaphores S1, ...
3
votes
2answers
253 views

Linearizability and Serializability in context of Software Transactional Memory

I've been trying to grasp serializability and linearizability in the context of software transactional memory. However, I think both notions can be applied to transactional memory in general. At this ...
3
votes
0answers
138 views

How to generate globally unique timestamps for transactions in distributed database systems?

According the paper [1] (Section 4), timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the following,...
4
votes
3answers
230 views

Why doesn't parallelism necessarily imply non-determinism?

I'm a student reading a book on threads. And I got when I got to non-deterministic and parallel programs, I got a bit confused. I hope you can help me out. I understand the difference between ...
2
votes
1answer
149 views

Rollback and Timestamp Ordering in Database

If we use the Timestamp Ordering for concurrency control in following scheduling: My TA says T2,T3,T5 is Run and T4,T5 is Rollback. I think it's false. any expert could help us?
2
votes
1answer
40 views

Question about 'Software Transactional Memory' by Shavit and Touitou

I've been reading the paper Software Transactional Memory by Shavit and Touitou. I understand how STM works in general but I need to understand this paper as it is ...
2
votes
1answer
102 views

Generating symbol matrices that satisfy regular expressions row- and column-wise

I have a program that fills a matrix of size N with characters such that all words formed by each row satisfy one regular expression, and all the words formed by each column satisfies a second one. ...