CODEWITHSUNDEEP
multithreadingsemaphore
train55255
train55255

Reputation: 49

Not understanding semaphore on low level

Just watched a video on semaphores and tried digging for more information. Not quite sure how a semaphore works on an assembly level.

P(s):
    s = s - 1
    if (s < 0) {wait on s}

CRITICAL SECTION

V(s):
    s = s + 1
    if(threads are waiting on s) {wake one}

I understand what the concept is behind these function, however I am having trouble wrapping my head around this.

say S = 1 and you have 2 Threads: Thread 1 and Thread 2

Thread One                                      Thread Two
load s                                          load s
subtract s,1                                    subtract s,1                      
save s                                          save s

Then there is a context switch in between the subtract and the save for both setting s to 0 for both. Wont both threads see s as 0 entering the critical section. I am not sure how one thread becomes exclusive if it is possible on the assembly level to context switch so that both can see s = 0.

Upvotes: 0

Views: 179

Answers (1)

user1937198
user1937198

Reputation: 5348

The key thing is that the increment and decrement use atomic instructions in some way. Within x86, there is a form of the add instruction which combined with the lock prefix lets you perform an addition to a memory location atomically. Because it is a single instruction, a context switch can't happen during its execution, and the lock prefix means that the CPU ensures that no other accesses appear to happen during the increment.

If an atomic add is not available then there are other options. One common one is an atomic compare and swap instruction. Found on most systems supporting parallel or concurrent code, it is an instruction that takes two values, an old and new, and if the memory location is equal to to the old, set it to the new value. This can be used in a loop to implement an atomic add:

l:
load r0 s
mov r1 r0
add r0 -1
cas s r1 r0
jmpf l

This loads a value, then subtracts 1 from a copy of the value. we then attempt to store the the lower value, but if it has changed we fail, and start again.

Upvotes: 2

Related Questions