Questiont about issues of concurrency such as synchronization and deadlocks.

learn more… | top users | synonyms

1
vote
1answer
23 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
19 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 ...
-1
votes
1answer
30 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
36 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
48 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
28 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} \\ ...
0
votes
1answer
58 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
32 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
3answers
119 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
19 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
107 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
22 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
56 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 ...
1
vote
2answers
38 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 ...
0
votes
1answer
82 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
42 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
22 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
77 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 ...
7
votes
0answers
129 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
62 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
311 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
183 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
80 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), ...
2
votes
1answer
69 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, ...
9
votes
2answers
135 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
60 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
253 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
267 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
205 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
41 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
149 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
97 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 ...
4
votes
3answers
125 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
0answers
102 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
31 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
93 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. ...
4
votes
0answers
26 views

Mutex implementation on top of a preemptive scheduler that does not guarantee liveness

I'm implementing some synchronization primitives in the standard library of an operating system. Specifically, I want to implement mutexes and condition variables. This is on top of a microkernel with ...
5
votes
1answer
368 views

Mutex implementation on top of a minimalistic preemptive scheduler

In this question, I'm implementing some synchronization primitives in the standard library of an operating system. Specifically, I want to implement mutexes and condition variables. This is on top of ...
4
votes
2answers
53 views

Modeling concurrent algorithms

I'm working on a class library (C++) that can be thought of as a producer/consumer queue of producer/consumer queues. There are many queues of data, and the goal is to assign worker threads to process ...
2
votes
1answer
143 views

When should you disable all interrupts in a program?

Consider a machine that has nested interrupts (a higher priority interrupt can interrupt a lower priority one, the current instruction's address is saved and later restored). Why would a programmer ...
1
vote
0answers
41 views

Using sephamores to solve happens-before requirements [closed]

I have a practice problem that I'm not sure how to solve: Use sephamores to solve the following synchronization requirement. We have 4 processes: P1, P2,P3 and P4. P1 must run before any of the ...
3
votes
1answer
337 views

Can a schedule with cyclic precedence graph still be serialisable?

We know Every conflict serializable schedule is serializable, but not all serializable schedules conflict-serializable. (*) so it means there is at least one serializable schedule that not conflict ...
1
vote
0answers
32 views

1-serializability theorem in database theory

In the paper "MVCC@TODS'1983 by Bernstein et al.", 1-serializability ($1$-$\text{SR}$) problem is defined as a decision problem: To decide whether an MV (multi-version) log $L$ is $1$-$\text{SR}$. ...
6
votes
1answer
80 views

What is the practical relevance of textbook mutual exclusion algorithms?

There's been a fair amount of research on mutual exclusion algorithms - e.g. a lot of it is presented in classic textbooks such as The Art of Multiprocessor Programming, where an entire chapter is ...
8
votes
2answers
790 views

Why is the consensus number for test-and-set, 2?

According to Wikipedia, The test-and-set operation can solve the wait-free consensus problem for no more than two concurrent processes. Why can't it solve the problem for more than two ...
-1
votes
1answer
44 views

What happens if the holder of a lock tries to acquire a lock? [closed]

In a system, suppose there is a process and a resource with only one instance. Let us assume that the process holds the instance and requests the same instance of that resource. Will there be a ...
2
votes
1answer
237 views

Bakery algorithm: what is the choosing[] boolean array for?

I'm studying the bakery algorithm. ...
-1
votes
1answer
62 views

Cocurrent programming language being Turing-equivalent and difference between Turing-complete and equivalent

In Is concurrent language CCS or CSP turing-equivalent in language power?, the answer says that CCS or CSP is Turing-complete. But that does not seem to answer whether CCS or CCP is Turing-equivalent. ...
3
votes
0answers
63 views

Concurrent Programming Bar Problem

I have been posed a question by my lecturer and I'm trying to figure the right way to go about it. They want me to ensure mutual exclusion for n processes. The code provided is as follows: ...