Concurrent systems are systems where several threads of computation are potentially executing simultaneously and interacting.

learn more… | top users | synonyms

1
vote
1answer
40 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 ...
2
votes
1answer
41 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
44 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
17 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
85 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 ...
3
votes
0answers
35 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 ...
7
votes
3answers
138 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
186 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
65 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
33 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, ...
2
votes
2answers
87 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 ...
2
votes
0answers
65 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
76 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
77 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
24 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
79 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. ...
3
votes
0answers
23 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 ...
4
votes
1answer
195 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
42 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
87 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
33 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
215 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
24 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}$. ...
5
votes
1answer
70 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 ...
3
votes
2answers
422 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 ...
-2
votes
1answer
40 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
111 views

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

I'm studying the bakery algorithm. ...
-1
votes
1answer
47 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. ...
2
votes
0answers
53 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: ...
2
votes
1answer
63 views

Is concurrent language CCS or CSP turing-equivalent in language power?

Does the concurrent language CSP (or CCS, $pi$-calculus) model interacting machines? Is CSP (or CCS, $pi$-calculus) Turing-equivalent to other programming languages like C?
0
votes
0answers
11 views

Does Optimistic Concurrency per object imply Serializability if a transaction will never span multiple objects?

Given a system which provides: Optimistic concurrency control / versioning per object (using CAS - Check-and-Set) Transactions that never need to span more then a single object. Snapshot Isolation ...
1
vote
1answer
89 views

Use a Monitor like a Semaphore?

When using monitors for most concurrency problems, you can just put the critical section inside a monitor method and then invoke the method. However, there are some multiplexing problems wherein up to ...
0
votes
0answers
50 views

Using two separate mutexes for the Exclusive Queue Problem (Little Book of Semaphores)

I recently read the exclusive queue (exclusive ballroom dancers) problem on the "Little Book of Semaphores" by Allen Downey. His solution included a single mutex for both the leaders and the ...
1
vote
0answers
20 views

(semaphore y=1; int x=5) vs (semaphore x=5)?

Last time, I was asked to solve a concurrency problem involving 100 similar processes constrained to fit into 5 buffers. (I'm talking about the Dining Savages problem.) I thought that it was alright ...
0
votes
0answers
86 views

Solution Patterns Involving Semaphores

There are a lot of synchronization problems that can be solved using semaphores. Some of these include the Producer-Consumer Problem, Readers-Writers Problem and the Dining Savages Problem. I see a ...
2
votes
0answers
42 views

Mesa Semantics without Starvation?

When a process inside a monitor with Mesa semantics finishes, another process can acquire the monitor. Now there can be starvation here when there is a thread with a lower priority. Are there ...
0
votes
0answers
39 views

Describing monitors and semaphores in terms of the three properties of critical section problem solutions

Solutions to the critical section problem exhibit three properties: mutual exclusion, progress, and bounded waiting. When do we say, or do we at least say, that operating system-implemented semaphores ...
4
votes
0answers
76 views

Concurrent priority queue with lazy increase-key

I could use a priority queue supporting the find-and-delete-min, and lazy-increase-key operations. The last term is my ...
9
votes
1answer
334 views

Are there hardware lock implementations without test-and-set or swap?

Locks are usually implemented thru test-and-set and swap machine-level instructions. Are there other implementations that do not use these? Also, can we say that all hardware level solutions to the ...
2
votes
1answer
120 views

Is it possible to solve the critical section problem with an atomic subtract operation?

In my Operating Systems class, our professor asked us to solve the critical section problem with the following atomic operation: ...
5
votes
2answers
79 views

Emulations of atomic registers and read-modify-write (RMW) primitives in message-passing systems

The ABD algorithm in paper: Sharing Memory Robustly in Message-Passing Systems can emulate single-writer multi-reader atomic registers in message-passing systems, in the presence of processor or link ...
4
votes
0answers
54 views

Model Join calculus as hypergraphs

I'm not sure if this is the right site to ask, but I couldn't find a another one. Some time ago I found out about the join calculus. It is based on constructs called joins to support concurrency. For ...
-3
votes
1answer
30 views

Determining execution times of a concurrent system with exclusive resources

A certain system consists of 2 CPUs. The CPU that is not being used is assigned to a task whose execution is requested. On this system, two tasks, A and B, are executed.These tasks both use a common ...
2
votes
1answer
306 views

Why is a program with only atomics in SC-DRF but not in HRF-direct?

In the paper "Heterogeneous-Race-Free Memory Models" [1], the authors state that a program consisting only of atomic is race free in SC-DRF but it is not in HRF-direct. I am not able to understand why ...
3
votes
1answer
185 views

How do locks work?

Suppose I have an application with two threads, which both use the same resource. Normally, a synchronized block keeps these threads from messing with the resource in a way the user doesn't expect. I ...
1
vote
1answer
91 views

Build a scheduler, to simulate parallel game flow [closed]

I am building a strategy game where units can interact with each other. As input I am getting a list of actions. I need to output a scheduler, that will tell when to start each action. The goal is to ...
0
votes
1answer
52 views

Simulating a sequence of events concurrently subject to a happened-before partial order

I am building a strategy game where multiple units(5 - 20) is fighting each other in the same time. I have a logic part that calculate those actions for each turn, and than pass it to the game ...
1
vote
3answers
110 views

Additional clarification about Simultaneous Multithreading

I was looking for comments about SMT and got several responses. The last one looks strange: Simultaneous multithreading, which can only be implemented on a multicore system, executes the ...
2
votes
1answer
124 views

Superscalar processors and complex instructions

I read that a supercalar processor has redundant functional units. One can read this e.g. on Wikipedia. How do such redundant units work? Is a complex instruction (for accelerating heavy process, ...
6
votes
1answer
168 views

Inconsistent state of a lock

I'm reading The Art of Multiprocessor programming and trying to understand their concept of inconsistent locks. Specifically, on page 37, the definition 2.8.1 of an inconsistent lock is not clear to ...