Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Fetch_And_Add(X,i) is an atomic Read-Modify-W...
Start Learning for Free
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.
AcquireLock(L){
while (Fetch_And_Add(L,1))
L = 1;
}
ReleaseLock(L){
L = 0;
}
while (Fetch_And_Add(L,1))
L = 1;
}
ReleaseLock(L){
L = 0;
}
This implementation
- a)fails as L can overflow
- b)fails as L can take on a non-zero value when the lock is actually available
- c)works correctly but may starve some processes
- d)works correctly without starvation
Correct answer is option 'B'. Can you explain this answer?
| FREE This question is part of | Download PDF Attempt this Test |
Verified Answer
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that rea...
Take closer look the below while loop.
while (Fetch_And_Add(L,1))
L = 1; // A waiting process can be here just after
// the lock is released, and can make L = 1.
L = 1; // A waiting process can be here just after
// the lock is released, and can make L = 1.
Consider a situation where a process has just released the lock and made L = 0. Let there be one more process waiting for the lock, means executing the AcquireLock() function. Just after the L was made 0, let the waiting processes executed the line L = 1. Now, the lock is available and L = 1. Since L is 1, the waiting process (and any other future coming processes) can not come out of the while loop. The above problem can be resolved by changing the AcuireLock() to following.
AcquireLock(L){
while (Fetch_And_Add(L,1))
{ // Do Nothing }
}
while (Fetch_And_Add(L,1))
{ // Do Nothing }
}
Most Upvoted Answer
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that rea...
Explanation:
The given implementation of the busy-wait lock using the Fetch_And_Add instruction has a flaw that can lead to incorrect behavior.
AcquireLock(L) Function:
- The AcquireLock function is used to acquire the lock.
- It uses a busy-wait loop that repeatedly calls the Fetch_And_Add function with L and 1 as parameters.
- The Fetch_And_Add function reads the value of L, increments it by 1, and returns the old value of L.
- The while loop continues until the Fetch_And_Add function returns a non-zero value, indicating that the lock is not available.
- Once the lock is available (Fetch_And_Add returns 0), the while loop exits, and the function returns.
ReleaseLock(L) Function:
- The ReleaseLock function is used to release the lock.
- It simply sets the value of L to 0, indicating that the lock is available.
Flaw in the Implementation:
The flaw in this implementation is that the Fetch_And_Add function is not atomic with respect to the while loop in the AcquireLock function.
- This means that there can be a race condition between multiple processes trying to acquire the lock simultaneously.
- Consider the scenario where two processes, P1 and P2, are simultaneously executing the AcquireLock function.
- Both processes read the value of L using the Fetch_And_Add function and get the same value (let's say 0).
- Both processes then increment the value of L by 1 and get the old value (0) as the return value of the Fetch_And_Add function.
- Now, both processes think that they have acquired the lock and exit the while loop.
- This leads to a situation where the lock is actually available, but both processes think they have acquired it.
Option B Explanation:
The correct answer is option B: the implementation fails because L can take on a non-zero value when the lock is actually available.
- This flaw in the implementation can lead to multiple processes mistakenly acquiring the lock simultaneously, resulting in incorrect behavior.
- The correct behavior of a lock is that only one process should be able to acquire it at a time.
- However, in this implementation, multiple processes can simultaneously acquire the lock when L is incremented by 1 but not yet set to 1.
- This can cause unexpected issues and can lead to race conditions and data inconsistencies.
- Therefore, the implementation fails as L can take on a non-zero value when the lock is actually available.
The given implementation of the busy-wait lock using the Fetch_And_Add instruction has a flaw that can lead to incorrect behavior.
AcquireLock(L) Function:
- The AcquireLock function is used to acquire the lock.
- It uses a busy-wait loop that repeatedly calls the Fetch_And_Add function with L and 1 as parameters.
- The Fetch_And_Add function reads the value of L, increments it by 1, and returns the old value of L.
- The while loop continues until the Fetch_And_Add function returns a non-zero value, indicating that the lock is not available.
- Once the lock is available (Fetch_And_Add returns 0), the while loop exits, and the function returns.
ReleaseLock(L) Function:
- The ReleaseLock function is used to release the lock.
- It simply sets the value of L to 0, indicating that the lock is available.
Flaw in the Implementation:
The flaw in this implementation is that the Fetch_And_Add function is not atomic with respect to the while loop in the AcquireLock function.
- This means that there can be a race condition between multiple processes trying to acquire the lock simultaneously.
- Consider the scenario where two processes, P1 and P2, are simultaneously executing the AcquireLock function.
- Both processes read the value of L using the Fetch_And_Add function and get the same value (let's say 0).
- Both processes then increment the value of L by 1 and get the old value (0) as the return value of the Fetch_And_Add function.
- Now, both processes think that they have acquired the lock and exit the while loop.
- This leads to a situation where the lock is actually available, but both processes think they have acquired it.
Option B Explanation:
The correct answer is option B: the implementation fails because L can take on a non-zero value when the lock is actually available.
- This flaw in the implementation can lead to multiple processes mistakenly acquiring the lock simultaneously, resulting in incorrect behavior.
- The correct behavior of a lock is that only one process should be able to acquire it at a time.
- However, in this implementation, multiple processes can simultaneously acquire the lock when L is incremented by 1 but not yet set to 1.
- This can cause unexpected issues and can lead to race conditions and data inconsistencies.
- Therefore, the implementation fails as L can take on a non-zero value when the lock is actually available.
Attention Computer Science Engineering (CSE) Students!
To make sure you are not studying endlessly, EduRev has designed Computer Science Engineering (CSE) study material, with Structured Courses, Videos, & Test Series. Plus get personalized analysis, doubt solving and improvement plans to achieve a great score in Computer Science Engineering (CSE).
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Similar Computer Science Engineering (CSE) Doubts
Top Courses for Computer Science Engineering (CSE)View all
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer?
Question Description
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer?.
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer? for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Question and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer? covers all topics & solutions for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, meanings, examples, exercises and tests below for Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer?.
Solutions for Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer? in English & in Hindi are available as part of our courses for Computer Science Engineering (CSE).
Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free.
Here you can find the meaning of Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer? defined & explained in the simplest way possible. Besides giving the explanation of
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer?, a detailed solution for Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer? has been provided alongside types of Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer? theory, EduRev gives you an
ample number of questions to practice Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location X, increments it by the value i, and returns the old value of X. It is used in the pseudocode shown below to implement a busy-wait lock. L is an unsigned integer shared variable initialized to 0. The value of 0 corresponds to lock being available, while any non-zero value corresponds to the lock being not available.AcquireLock(L){ while (Fetch_And_Add(L,1)) L = 1;}ReleaseLock(L){ L = 0;}This implementationa)fails as L can overflowb)fails as L can take on a non-zero value when the lock is actually availablec)works correctly but may starve some processesd)works correctly without starvationCorrect answer is option 'B'. Can you explain this answer? tests, examples and also practice Computer Science Engineering (CSE) tests.
|
|
Explore Courses for Computer Science Engineering (CSE) exam
|
|
Suggested Free Tests
Signup for Free!
Signup to see your scores go up within 7 days! Learn & Practice with 1000+ FREE Notes, Videos & Tests.
|
© EduRev
|
Education Revolution
|
Follow Us
|
Signup to see your scores
go up within 7 days!
Access 1000+ FREE Docs, Videos and Tests
Takes less than 10 seconds to signup