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

learn more… | top users | synonyms

2
votes
2answers
62 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 ...
1
vote
0answers
26 views

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

According to Section 4 in the paper [1], 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
49 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
51 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?
1
vote
1answer
20 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
67 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
20 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
79 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
35 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
62 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
23 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
161 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
21 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
67 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
263 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
39 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 ...
1
vote
1answer
69 views

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

I'm studying the bakery algorithm. ...
-1
votes
1answer
27 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
51 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
50 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
75 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
38 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
71 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
41 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
35 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
65 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 ...
8
votes
1answer
266 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
93 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
69 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
48 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
156 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
175 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
89 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
51 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
105 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
111 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
146 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 ...
4
votes
2answers
159 views

Why is there readonly (const) in C++, but not writeonly (sink)?

C++ initially had "readonly" and "writeonly" qualifiers, before "readonly" was renamed to "const", and "writeonly" removed. My question is: What are the problems with "writeonly" (or a "sink" ...
2
votes
1answer
28 views

Deadlock prevention by killing a victim

In our operating systems class, the teacher told us about deadlocks prevention methods. One of them is that to select as a victim the process which requires the CPU time or one that requires a lot of ...
4
votes
0answers
49 views

Extending the causal memory model to wide-area distributed storage systems

In the seminal paper "Causal memory: definitions, implementations, and programming", distributed causal memory is defined to ensures that all the processes in a system agree on the relative ordering ...
2
votes
0answers
26 views

How can I talk about priority inversion if it's impossible to specify priority?

In the paper: Leslie Lamport: What It Means for a Concurrent Program to Satisfy a Specification: Why No One Has Specified Priority; ACM Symp Principles of Programming Languages, (POPL-12):78-83, ...
3
votes
1answer
71 views

Session Memory in the Windows Kernel

While reading the paper Effective Data-Race Detection for the Kernel by John Erickson and Madanlal Musuvathi. I was stuck on a slightly tricky sentence. "Similarly, a range of kernel-address space, ...
2
votes
1answer
74 views

Does “serializable” also mean that it's lockable

Here's an final exam question for a Database Fundamentals class. I've read the book, stuff online.. I can't figure out if "serializable" also means that the schedule is ...
2
votes
3answers
328 views
5
votes
1answer
98 views

Question about threads and locks

I am currently reading Fuss, Futexes and Furwocks: Fast Userland Locking in Linux and came across this quote: In a fair locking scheme the lock is granted in the order it was requested. This can ...
1
vote
1answer
36 views

If a thread containing main terminates, can another thread do anything?

I'm studying threads in C and I have this theoretical question in mind that is driving me crazy. Assume the following code: ...
2
votes
0answers
29 views

Why is this execution happens-before consistent?

In section 17.4.5 "Happens-before Order" of Java Language Specification, a trace is examined for the notion of happens-before consistency. The trace is shown in the figure in which $A$ and $B$ are ...