Solution to Critical State Problem: Progress Requirement

  • Thread starter Thread starter prashantgolu
  • Start date Start date
  • Tags Tags
    State
Click For Summary

Discussion Overview

The discussion revolves around the critical state problem in concurrent programming, specifically analyzing an algorithm proposed by Galwin for two processes. Participants explore the algorithm's compliance with the "progress" condition required for critical section management.

Discussion Character

  • Technical explanation
  • Debate/contested

Main Points Raised

  • One participant describes an algorithm that involves a turn variable and a critical section, questioning how it fails to meet the progress condition.
  • Another participant points out the lack of context regarding the variable 'i' and the processes 'p0' and 'p1', suggesting that the algorithm's completeness is unclear.
  • A participant clarifies that 'turn' is initially set to 0 and that 'p0' and 'p1' represent two processes, indicating that the algorithm is designed for two processes only.
  • Another participant agrees that the algorithm does not satisfy the progress condition, providing a scenario where one process could indefinitely prevent the other from entering its critical section.
  • A later reply suggests the need for an atomic operation and introduces the concept of using a flag variable alongside the turn variable, referencing established algorithms like Dekker's and Peterson's for context.

Areas of Agreement / Disagreement

Participants generally agree that the algorithm does not satisfy the progress condition, but there is no consensus on the implications or potential solutions, as some participants introduce alternative approaches without resolving the initial concerns.

Contextual Notes

The discussion highlights limitations in the provided algorithm, including missing assumptions about process behavior and the need for atomic operations to ensure proper synchronization.

prashantgolu
Messages
50
Reaction score
0
i read this as a solution to critical state problem in galwin

repeat
while turn!= i do no-op;
critical section
turn := j;
remainder section
until false;


now this algo does not meet the "progress" conditiion...
the book states the reason as...this requires strict alteration of processed in execution of their critical state
for ex...if turn =0 and p1 is ready to enter its critical section,it cannot do so...even though p0 maybe in its remainder section...

how can p1 be in its remainder section and turn still be 0...

how does this algo not meet the reqirement of progress?
 
Technology news on Phys.org
prashantgolu said:
i read this as a solution to critical state problem in galwin

repeat
while turn!= i do no-op;
critical section
turn := j;
remainder section
until false;
As stated here, this doesn't make much sense. Is this just a part of an algorithm and you haven't shown us the rest? We don't know the value of i, so can't tell whether turn != i is true or false.
prashantgolu said:
now this algo does not meet the "progress" conditiion...
the book states the reason as...this requires strict alteration of processed in execution of their critical state
for ex...if turn =0 and p1 is ready to enter its critical section,it cannot do so...even though p0 maybe in its remainder section...

how can p1 be in its remainder section and turn still be 0...

how does this algo not meet the reqirement of progress?
What are p0 and p1? They aren't mentioned in the algorithm you showed.
 
sorry...my fault...turn=0 initaially...and p0 and p1 are two processes...this algorithm is for 2 processes only...so turn can be 0 or 1...
 
Ya, it is true that the algorithm does not satisfy the condition of progress...

Imagine a case when p1 has entered its critical section. After executing, it turns the value of turn to 0 and exits. But the process p0 does not want to enter its critical section. So the value of turn would be set to 0 for ever. Even though if process p1 wants to enter its critical section again, it cannot do so, until process p0 wishes to enter its critical section.
Hence the condition of progress is not satisfied.

I hope I was able to explain you. Do let me know...:approve:
 
thanks a lot :)
 

Similar threads

Comp Sci How to test progress and bounded waiting in Peterson's algorithm?
  • · Replies 2 ·
Replies
2
Views
2K
Understanding a rudimentary solution to Critical Section Problem
  • · Replies 2 ·
Replies
2
Views
2K
Critical-Section Problem. (Dekker)
  • · Replies 1 ·
Replies
1
Views
6K
Does this code satisfy mutual exclusion, progress, and bounded waiting?
  • · Replies 4 ·
Replies
4
Views
2K
Spin-1 particle states as seen by different observers: Wigner rotation
  • · Replies 5 ·
Replies
5
Views
4K
High School Are Inverse Problems More Complex Than Direct Problems in Mathematics?
  • · Replies 13 ·
Replies
13
Views
3K
Graduate Dasgupta et al., What is the alternative to a unique dS vacua?
  • · Replies 14 ·
Replies
14
Views
4K
Graduate Understanding Scattering and Bound State Solutions in Quantum Mechanics
  • · Replies 1 ·
Replies
1
Views
3K
Undergrad Cosmic Censorship: Does it Hold?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Progress In Calculating The HLbL Contribution To Muon g-2
  • · Replies 0 ·
Replies
0
Views
3K