Questions about the concurrency-control requirement of ensuring that no two processes are simultaneously in a critical section (a period when the process is accessing a shared resource). Failing to achieve mutual exclusion leads to the problem of data races.

learn more… | top users | synonyms

3
votes
0answers
41 views

Orient edges in a mixed graph to minimize the critical path

A mixed graph is a graph that has directed and undirected edges. Is there an efficient algorithm that allows the orientation of undirected edges in a mixed graph in such a way that no cycle is ...
3
votes
1answer
83 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 ...
4
votes
0answers
43 views

Lamport's Bakery algorithm with other > relation

i'm reading an old exam and one question was: Which property of the Bakery algorithm is violated with the following change? ...
1
vote
1answer
28 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
0answers
86 views

Proof of Manna-Pnueli algorithm for mutual exclusion being incorrect

Suppose we have the Manna-Pnueli algorithm for mutual exclusion: I was trying to find a sequence that violates mutual exclusion and I came up with this: ...
1
vote
2answers
50 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 ...
1
vote
1answer
56 views

Why do we need $k \geq n$ in Dijkstra's token ring self-stabilizing system?

Let's say I have a ring with four nodes $n=\{0;1;2;3\}$ and three possible states $k=\{0;1;2\}$. A transient failure happens and the system ends up in an illegal state. I know from the restriction ($...
0
votes
0answers
33 views

What differs in the message passing model?

Doing a very basic course in distributed computing. I just went through Dijkstra's self-stabilizing mutual exclusion in the shared memory model. We where encouraged to think about what would change in ...
1
vote
1answer
47 views

Mutex-/semaphore-/locking-algorithm using atomic reads/writes with data-propagation delays

Is there a mutual exclusion or semaphore or locking algorithm that only relies on atomic reads and atomic writes of shared memory and can tolerate a delay in propagation of the written data between ...
3
votes
1answer
96 views

Mutual exclusion algorithm using only atomic reads and writes for unknown number of processes and robust to process abortion

I am trying to come up with a mutual exclusion algorithm that is based only on atomic reads and atomic writes of shared memory (i.e. no compare-and-swap or similar). Apart from mutual exclusion and ...
8
votes
3answers
328 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 ...
1
vote
1answer
94 views

Deadlock Solutions: Lock Ordering

This is from a textbook on operating systems. This is not homework, just part of the chapter on deadlocks. ...
2
votes
1answer
54 views

Disabeling interrupts to solve critical section issue on multiprocessor system

Assume I have a multicore system and a critical section. I understand how disableling interrupts on a single core systems solves the critical section problem. So assume I could disable interrupts on ...
4
votes
0answers
34 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
449 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 ...
6
votes
1answer
87 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 ...
-1
votes
1answer
46 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 ...
3
votes
0answers
66 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: ...
1
vote
1answer
575 views

What is the difference between consensus and mutual exclusion in Distributed Systems?

If we can achieve consensus, does it imply we can achieve mutual exclusion? Is there a difference? Example : Paxos solves the consensus problem, can it also be used to solve mutual exclusion?
11
votes
1answer
395 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 ...
3
votes
1answer
203 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: ...
3
votes
1answer
96 views

Finding issues in concurrent implementation of carpark overflow control

Firstly, I am revising for my Concurrent Programming exam and have come across the following question from a previous exam paper. I have attempted to answer it, and will try and convey this effort; I'...
6
votes
3answers
1k views

Solutions to synchronization problem need to be executed in critical section

I was reading about synchronization problems for cooperating processes and i learned that only hardware solutions like test_and_wait() and ...
24
votes
1answer
11k views

Contrasting Peterson’s and Dekker’s algorithms

I am trying to understand the algorithms by Peterson and Dekker which are very similar and display a lot of symmetries. I tried to formulate the algorithms in informal language like follows: ...
5
votes
2answers
282 views

Mutual exclusion for n processes

I want to implement mutual exclusion for $n$ processes. Critical section code: ...
8
votes
2answers
788 views

Does Peterson's 2-process mutual exclusion algorithm account for dying processes?

I think that in Peterson's algorithm for mutual exclusion, if the process first to enter the critical section were to die or be cancelled, the other process would loop forever, waiting to enter the ...