They asked me this question — what’s the difference between mutex and semaphore during an interview

It seems hard for my friend who is a self-taught developer.

Beginning

“Last week they asked me what is multi-threading and if have I ever done anything with that, I answered the question”. my friend said.

“Okay sounds good, hope you will pass it”. I told him.

“But then he asked me how to make sure resources safely be accessed in multi-threading situations”. he said.

“You should know lock right?” I told him.

“Yes I answered him lock but then he asked what is semaphore and what is the difference I have no idea what is semaphore so I told the interviewer I don’t know could you tell me what is that ?”. he said.

“then did he tell you the answer?” I asked.

“Yes, he said semaphore is a signal mechanism which is used for thread synchronization; and the purpose of a mutex is to protect resource access from other threads while only allowing one thread to use it,” he said.

“So you got it?” I asked.

“No…can you explain to me how it works under the hood without too many CS terms?” he asked.

Well, sure let me try.

Mutex

Okay, let’s forget about all these words signal, thread synchronization, and resource access.

Look at my 2 cats they want to eat something for dinner today. so below picture is how mutex works:

So let’s say you are the cat’s owner and you have 2 cats, and there is a special room for cats to eat the food, must go to the room and eat. and these 2 cats don’t share plates, yes they don’t like each other let’s say.

• #1 cat1 got hungry and found food inside the eating room. (you already dropped the food there)
• #2 It walked in and start eating then locked the room.
• #3 owner put cat2 into sleep and watch when cat1 will finish. every 10 seconds to see if cat1 finished eating or no

So far good? let’s continue.

• #4 so finally cat1 finished. it walked out and unlocked the door.
• #5 owner saw that. then he prepares the cat 2 plate and shifts the leftover food from cat1’s plate into cat2’s plate.
• #6 owner wakes up cat 2.
• #7 It walked in and locked the room door then started to enjoy its meal!

This is what happens in mutex. let’s map to CS lanaguge.

cat1 and cat2 both are threads, and the cat Owner is the OS scheduler. so when one thread accesses some resource it uses a mutex object to lock it so that no other thread can access it (#1 and #2); when other threads come trying to access it, OS put them on the “wait list” (#3); OS reschedule thread2 to start when it knows thread1 finished processing and unlocked the resource, then OS also copying the required execution context (register state, program counter, etc) from thread1 into thread2 (#5, #6, #7).

So wait, why need copying context (context switching)? because this information is needed when instruction is being executed by the CPU. you may refer to my explanation here, it is a complicated process sorry but I hope 10 minutes is enough to go through.

So let’s talk about Semaphore.

Semaphore

So there could be different cases.

1. when semaphore=1

• #1 Owner dropped food inside the room and “told” cat1 to eat (let’s say both cats are very smart and can understand human language)
• #2 cat1 walked into the room and ate. without locking the room (it trusts the owner will not let other cats disturb it)
• #3 cat1 finished eating and walked out.
• #4 owner changed the plate and shift the leftover food from the cat1 plate into the cat2 plate
• #5 cat2 walked into the room and continue eating cat1’s food in its own plate

Repeat the story In CS language.

cat1 and cat2 both are threads. but the owner is not an OS scheduler this time, it could be another process as well (yes, can be a cat, so cats “sending signal” to each other is also possible).

So thread1 has been signaled by another process (or main thread) to execute to access some resource until the finish, without locking(#1, #2, #3); Context switch happened(#4), Thread2 was then signaled by the main thread to start accessing the same resource execute until it finishes executing(#5).

2. then what about semaphore>1

Good question. that is one key differentiator between Mutex and Semaphore as well.

So let’s say you have 3 cats this time. and all are friends now (but they still do not share the same plate). they are willing to eat together in the same room, but the room space is limited they can only afford 2 cats to eat at the same time.

It will be looks like this.

• #1 Owner dropped some food, prepared 2 plates(cat1’s and cat2’s) inside the room
• #2 Owner “told” cat1 and cat2 at the same time to go in the room and eat
• #3 cat1 and cat2 both walked in and started eating
• #4 cat1 finished faster and walked out of the room.
• #5 owner changed the plate and then moved the food from cat1’s plate into cat3’s
• #6 owner “told” cat3 to go into the room and eat
• #7 cat3 walked in and started eating

CS language.

We have 3 threads this time. and semaphore=2. which means we only want max 2 threads accessing the shared resource. so the main thread signaled thread1 and thread2 both accessing the resource see which one finish faster (#1, #2, #3); thread1 finished (#4); main thread then signal thread3 to start execute(#6), and context switch happened (#5); thread3 accessing the shared resource (#7).

Well, I believe you understood the difference now, both the what and how. let’s recap.

Semaphore

• It uses signals to do threads coordination or synchronization.
• It allows multiple threads to access the same resource at the same time.
• semaphore’s focus is to figure out threads’ dependencies and schedule them in the correct order.

Mutex

• Only allows one thread to access the shared resource at one time
• The focus is to handle resource access race conditions in multi-threading situations.

So there is one more — Spinlock

Let’s compare this one as well.

Again, use our cats to simplify.

• #1 So the owner dropped both cat’s food inside the room to see who is hungry first then can walk in and started eating
• #2 cat1 was hungry, and walked in. but cat2 also hungry after a minute.
• #3 cat1 is faster, walked into the room and ate locked room
• #4 cat2 is waiting outside, counting seconds until cat1 finish then it will go in
• #5 finally cat1 finished.
• #6 owner goes and changes the plate and moves the leftover food
• #7 cat2 immediately walked in as soon as the food is moved over into its plate.

CS language.

2 cats are 2 threads. Room is a folder, food is a file.

So 2 threads are racing to access 2 different files under the same folder; thread1 is faster, started processing and locked the folder; thread2 is constantly checking(engaging other cores) until thread1 finishes; thread1 finished, context switch happened (by OS); thread2 started executing.

Let's see the difference from mutex.

Spinlock

• Unlike Mutex, it does not require OS to “sleep” and “wake up” itself. it saves some cost from here.
• Only in a multi-core system, in the single-core system doesn’t make much sense, spinning in a tight loop consumes CPU resources without allowing other tasks or threads to make progress, and using mutex is a better choice.

Last

Well, that’s all guys. I hope you find it simple to understand.

Thanks for reading!