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? - EduRev Computer Science Engineering (CSE) Question

Explore Courses UPSC Exam UPSC Test Series Free Notes EduRev Infinity

Open App

Computer Science Engineering (CSE) Exam > Computer Science Engineering (CSE) Questions > Fetch_And_Add(X,i) is an atomic Read-Modify-W...

Join the Discussion on the App

AcquireLock(L){
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

Test: Process- 2

Attempt Test

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.

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 }
}

View all questions of this test

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.

Answered by Gate Gurus · View profile

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).

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

View all answers Start learning for free

< Previous Question Next Question >

Explore Courses for Computer Science Engineering (CSE) exam

Similar Computer Science Engineering (CSE) Doubts

Instruction execution in a processor is divided into 5 stages.Instruction Fetch(IF), Instruction Decode (ID), Operand Fetch(OF), Execute(EX), and Write Back(WB),These stages take5,4,20, 10and3nanoseconds (ns) respectively. A pipelined implementation of the processor requires buffering between each pair of consecutive stages with a delay of2 ns. Two pipelined implementations of the processor are contemplated:(i) a nave pipeline implementation (NP) with 5 stages and(ii) an efficient pipeline (EP) where the OF stage id divided into stages OF1 and OF2 with execution times of 12 ns and 8 ns respectively.The speedup (correct to two decimals places) achieved by EP over NP in executing 20 independent instructions with no hazards is ________________.Note:This questions appeared as Numerical Answer Type.

View answer

An instruction pipeline has 4 stages Instruction Fetch(IF), Instruction Decode(ID), Execute instruction (Ex), Write Back(WB). All instructions take all stages and takes 4 clock cycles. Branch instructions are not overlapped, i.e. the instructions after the branch are not fetched till branch is known. Branch is known in the execute phase. Suppose 20% instructions are conditional and 80 % unconditional. Calculate speed up for 100 instructions (upto 2 decimal plac e). Ignore the case that the branch may not be taken.

View answer

An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the designers have decided to split theID/RF stage into three stages (ID, RF1, RF2) each of latency 2.2/3 ns. Also, the EX stage is split into two stages (EX1, EX2) each of latency 1 ns. The new design has a total of eight pipeline stages. A program has 20% branch instructions which execute in the EX stage and produce the next instruction pointer at the end of the EX stage in the old design and at the end of the EX2 stage in the new design. The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed. All instructions other than the branch instruction have an average CPI of one in both the designs. The execution times of this program on the old and the new design are P and Q nanoseconds, respectively. The value of P/Q is __________. Correct answer is '1.54'. Can you explain this answer?

View answer

An instruction pipeline has five stages where each stage take 2 nanoseconds and all instruction use all five stages. Branch instructions are not overlapped. i.e., the instruction after the branch is not fetched till the branch instruction is completed. Under ideal conditions,a. Calculate the average instruction execution time assuming that 20% of all instructions executed are branch instruction. Ignore the fact that some branch instructions may be conditional.b. If a branch instruction is a conditional branch instruction, the branch need not be taken. If the branch is not taken, the following instructions can be overlapped. When 80% of all branch instructions are conditional branch instructions, and 50% of the conditional branch instructions are such that the branch is taken, calculate the average instruction execution time. Correct answer is 'Each stage is 2 ns.'. Can you explain this answer?

View answer

Consider the following x86 machine instruction sequence:ADD EAX, EBXSUB ECX, EAXADD EBX, ECXThe first instruction adds the contents of the 32-bit registers EAX and EBX and stores the result in EAX. The second instruction subtracts the contents of EAX from ECX and stores the result in ECX. These instructions are to be executed in a pipelined instruction processor with the following 4 stages: fetch instruction (FI), decode instruction and calculate addresses (D

View answer

Top Courses for Computer Science Engineering (CSE)View all

GATE Computer Science Engineering(CSE) 2025 Mock Test Series

Question Bank for GATE Computer Science Engineering

General Aptitude for GATE

Computer Networks

Programming and Data Structures

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?

Share with a Friend

Answer this doubt

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?.

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