A deep dive into Dispatch Semaphores

photo by Chuttersnap on Unsplash

This is part 2 of a series of posts on concurrency and threading in iOS. If you haven't read my first article explaining queues and tasks in iOS, I highly recommended reading it here since I would be using the analogy I used in that article in this post. However, If you have a good grasp of queues and tasks, you can continue reading this article as I would provide a brief introduction to the analogy I used in the previous article.

The Plot

In the previous article, customers in the grocery store have registered themselves with the store with the help of Katie and got the billing done with the help of Messi and the billing lane staff. Everything was going well until the COVID 19 outbreak and the store has decided not to accept cash payments, and is only accepting credit cards, however, the store manager soon realized there is a problem. The store only has one card swiping machine whereas it has multiple billing lanes. After a lot of deliberation, the store manager has decided to use the semaphore technique to solve this problem. Before we see how the store owner implemented the technique, let’s check out what a semaphore is.

Basics

This is what wiki says about semaphores in computer science

A semaphore is a variable or abstract data type used to control access to a common resource in a concurrrent system such as a multitasking operating system.

Semaphores provide synchronized access to a shared resource. How does it provide such access?

A Semaphore essentially contains a :

• Counter which lets the semaphore know how many threads can use the resource at once
• Queue to store the list of threads requiring access to a shared resource
• Wait() method to request access to the shared resource
• Signal() method to release access to the shared resource

When the semaphore receives a wait() request, it checks the value of the counter :

• if the counter is zero, it pushes the thread into the queue.
• otherwise, it provides access to shared resources and reduces the counter by 1.

When the semaphore receives a signal() request, it checks if the queue has any threads in it

• If the queue has any threads, it dequeues the thread from the queue and provides access to the shared resource.
• otherwise, it increments the counter by 1.

Dispatch Semaphore

A dispatch semaphore is an efficient implementation of a traditional counting semaphore. Dispatch semaphores call down to the kernel only when the calling thread needs to be blocked. If the calling semaphore does not need to block, no kernel call is made.

The dispatch semaphore we use in swift adds a nice wrapper around the traditional semaphore we discussed above. It calls down to kernel only when the calling thread doesn't get immediate access and is pushed into the queue

The plot continues

Ok! That's a lot of theory, Let’s see some code using our grocery store analogy

As mentioned above, the store manager employed semaphore technique to solve the billing machine problem. He allocated a buzzer to each billing lane and asked the staff to click the buzzer when they need the machine. The order in which the buzzer is pressed is noted and is used to determine the order in which the swiping machine is allocated.

Time to see this in action:

Ok! I understand that’s a lot. Let's break it down into pieces.

1. We are creating a concurrent queue using DispatchQueue
2. We are creating a semaphore using DispatchSemaphore with a value 1, which means one only thread can access the shared resource at a time
3. We are creating a billing machine. This is a closure billingMachine that accepts two parameters, the amount to be billed and lane number.
4. We then send 3 different customers to 3 different lanes and the store staff at the lanes can scan the products and tell the final amount to the customer
5. If you notice clearly I’m putting thread at lane 1 to sleep for 2 seconds just to ensure I'm providing enough time for the store staff at lane 1 to scan products worth 1000$ :)
6. I have added semaphore.wait() before calling billingMachineclosure and semaphore.signal() after calling billingMachine Closure returns

Let's see the output of the above playground before we discuss in detail.

Output

That looks nasty as well. Let me break down. We start with an empty semaphore queue and with a counter value 1

1. Customer 1 goes to lane 1 (executed on thread 4)
   Customer 2 goes to lane 2 (executed on thread 5)
   Customer 3 goes to lane 3(executed on thread 6)
2. Lane 2: wait()
   Customer 2 at lane 2 gets his products scanned quickly and the staff clicks the buzzer. Since no one else is using the billing machine, the staff at lane 2 gets the billing machine and the counter is updated to 0
3. Lane 3: wait()
   At this point, staff at lane 3 clicks the buzzer, however, since the counter is zero the semaphore puts lane 3 into the queue and now lane 3 is frozen and can perform no action until it get access to the billing machine. This is why operations such as wait() should never be performed on the Main thread
4. Lane 2: signal()
   Once lane 2 finishes the billing and releases the billing machine, semaphore provides the first item in the queue, i.e lane 3 the access to billing machine
5. Lane 3: signal ()
   Once lane 3 finishes the billing and releases the billing machine, semaphore checks the queue and there is nothing in the queue, so it just updates the counter to 1
6. Lane 1: wait()
   Staff at lane 1 clicks the buzzer. Since no one else is using the billing machine, the staff at lane 1 gets the billing machine and the counter is updated to 0
7. Lane 1: signal()
   Lane 1 finishes the billing and releases the billing machine, semaphore checks the queue and there is nothing in the queue, so it just updates the counter to 1

All the customers leave and now our staff can rest. That pretty much summarizes the usage of semaphore in a real-world scenario. Dispatch Semaphore can be used whenever synchronized access is required to a shared resource and this prevents data races.

Bonus

Ever heard of Lock or mutex? How is semaphore different from them?

Semaphore is a synchronization technique where we can control number of threads to access a resource. In lock/Mutex, only one thread can access resources at a time. But Semaphore allows multiple threads(Value of counter) to access the same resource at a time.

Conclusion

That’s all I have for this article. Follow me on twitter for more updates. Provide some claps if you liked the post as that would encourage me to write more(you can give up to 50). Don’t worry at all about being pedantic. If you see that I can improve something in my article, do let me know.