12_Semaphores

1 .Lecture 12 – Semaphores Describe a semaphore and distinguish from a mutex Give examples of applications of semaphores Use semaphores for process/thread synchronization with the help of the course library Design and implement the solution to the roller coaster problem Learning Goals Semaphores 1 © Paul Davies, C. Antonio Sanchez. Not to be copied, used, or revised without explicit written permission from the copyright owner.

2 .Semaphores Let’s say you have a resource that can support up to N simultaneous users Computer login system that allows 10 users Concert ticket sales with only 200 tickets Roller coaster that only allows 10 people per cart We want some way to allow N multiple users to access a resources before forcing the n+1 th user to wait Semaphores 2 Semaphore : a counting synchronization primitive that supports two main operations: wait() – waits until the next resource is available notify() – notifies all waiting threads that one resource has become available

3 .Semaphores Semaphores 3 Resource Semaphore ‘ S ’ Protecting Resource Resource A A S.Wait() To Gain Entry S = 1: Resource is FREE S = 0 : Resource is BUSY Access S.Notify () to Leave A B B C D B C C D D Blocked Note Resource Stays Busy (S=0) when a thread leaves and there was one waiting Resource Becomes Free when a thread leaves and there are no more waiting outside

4 .Binary Semaphore A binary semaphore has a single resource. They can be used to enforce mutual exclusion. In fact, this is how Dijkstra originally solved the mutual exclusion problem He observed that railway lines were partitioned into critical sections so that the track could be shared, but only one train was allowed to enter each section at a time. A mechanical signal was used to indicate when a section of single track was free. Semaphores 4 Critical Section 1 Critical Section 2 Critical Section 3 Wait Wait Wait Occupied Occupied Occupied Free Free Free Notify Notify Notify

5 .Semaphores Any thread can notify a semaphore (i.e. does not need to have previously waited) Allows you to initialize a semaphore to a particular value The wait() and notify() operations are guaranteed to be thread-safe Semaphores 5 Q: What is the difference between a mutex and a binary semaphore? a mutex must be unlocked by the thread that locked it a semaphore can be notified by any thread for ( int i= 0 ; i<val; ++i) { semaphore.notify(); }

6 .Semaphores in C++ Unfortunately, modern C++ does not define any semaphore synchronization primitives, but we have built one in the course library Semaphores 6 class semaphore { public : semaphore(size_t count = 1 ) ; // starts semaphore with initial count void notify(); // releases resource, wakes up waiters void wait; // acquires resource bool try_wait(); // tries to acquire resource, // returns immediately }; Q: Why is there no method to return the internal count?

7 .Semaphores in C++ Semaphores 7 #include <cpen333/thread/semaphore.h> void car( cpen333 :: thread :: semaphore & pumps, int id) { pumps.wait(); // wait for pump to be free // ... use pump ... pumps.notify(); // let others know the pump is now free } int main() { // create a gas station with 3 pumps cpen333 :: thread :: semaphore pumps( 3 ); // create 100 cars to go through pumps std :: vector < std :: thread > cars; for ( int i= 0 ; i< 100 ; ++i) { cars.push_back( std ::thread(car, std ::ref(pumps), i+ 1 )); } // wait for all threads to terminate for ( std :: thread & car : cars) { car.join(); } return 0 ; } Issues?

8 .Semaphore Guards To ensure exception-safety , we should use the RAII pattern to ensure our semaphore is notified when we are done with it Semaphores 8 template < typename SemaphoreType> class semaphore_guard { public : semaphore_guard(SemaphoreType& sem); // waits for semaphore ~semaphore_guard(); // notifies semaphore }; #include <cpen333/thread/semaphore.h> void car( cpen333 :: thread :: semaphore & pumps, int id) { cpen333 :: thread :: semaphore_guard< decltype (pumps) > guard(pumps) // wait for pump // ... use pump ... }

9 .Interprocess Semaphores Semaphores 9 Windows: https://msdn.microsoft.com/en-us/library/windows/desktop/ms686946(v=vs.85).aspx CreateSemaphore(...) WaitForSingleObject(...) ReleaseSemaphore(...) Linux/Mac: http://pubs.opengroup.org/onlinepubs/009695399/basedefs/semaphore.h.html sem_open(...) sem_wait(...) sem_post(...) sem_unlink(...) We can create interprocess semaphores using operating system kernel calls .

10 .Interprocess Semaphores Semaphores 10 Rather than working directly with operating system calls, we provide a uniform interface in the CPEN 333 course library: class semaphore : public named_resource { public : semaphore( const std::string& name, size_t value = 1 ); // initialize name and value void wait(); // acquire resource bool try_wait(); // try to acquire resource, return immediately void notify(); // release resource bool unlink(); // unlink name from semaphore (Mac/Linux) }; On Windows semaphores have process persistence , on POSIX systems they have kernel persistence .

11 .Interprocess Semaphores Semaphores 11 #include <iostream> #include <thread> #include <cpen333/process/semaphore.h> int main( int argc, char * argv[]) { // connect to semaphore, make sure same name cpen333 :: process :: semaphore pumps( "gas_station_pumps" , 3 ); std ::cout << "Car waiting for gas pump to be free" << std ::endl; // wait for pump to be free { cpen333 :: process :: semaphore_guard< decltype (pumps) > guard(pumps); std ::cout << "Car at pump, filling up..." << std ::endl; std :: this_thread ::sleep_for( std :: chrono :: milliseconds ( 1000 )); } return 0 ; } Up to 3 simultaneous threads

12 .The Roller-Coaster Problem Semaphores 12 Design the synchronization mechanism for multiple passenger threads plus a rollercoaster thread such that Only 2 passengers can get on the rollercoaster at a time i.e. wait their turn The rollercoaster will wait until 2 passengers have boarded before leaving Each passenger will wait until they have been taken for a ride before getting off New passengers will wait until the previous 2 passengers are off before boarding How many semaphores do you need?

13 .Semaphores 13 Only 2 passengers can get on the rollercoaster at a time. Create a semaphore called Entry to act as a gate/turnstile, initialized to 0 so nobody can get on Passengers perform a Wait() on Entry in order to board the rollercoaster When the rollercoaster starts it can Notify() Entry twice to allow passengers to board A Rollercoaster must wait until 2 new passengers are seated before leaving. Create a semaphore called Full , initialized to 0 The rollercoaster will perform two Wait() operations on this semaphore before departing to ensure it is full Each passenger who boards the rollercoaster will Notify() this semaphore A Passenger must wait until they have taken a ride before getting off. Create a semaphore called Exit , initialized to 0 Passengers will perform a Wait() on Exit before getting off When the rollercoaster returns after a ride, it will Notify () this semaphore twice to let off the passengers New passengers will wait until the 2 previous passengers have got off, before boarding. Create a semaphore called Empty , initialized to 0 Passengers will perform a Notify() on this semaphore when they have actually got off The rollercoaster will perform a Wait() on this semaphore twice to ensure that the passengers have left before letting new passengers on (step 1 above)

14 .Charlie Free to get off Full= 0 Entry= 0 Empty= 0 Exit= 0 Roller Coaster Notify() Entry= 1 Entry= 2 Wait() Coaster Blocked trying to Ride Wait() Notify() Notify() Wait() Charlie Blocked Trying to Get Off Wait() Charlie Blocked Trying to Get On Wait() Charlie Blocked Trying to Get On Notify() Empty= 1 Empty= 2 Notify() Wait() Coaster Free to Ride Incremented Decremented Incremented Decremented Unchanged as Coaster is waiting Unchanged as Charlie is waiting x 2

15 .Homework Use Case Diagrams 15 https://www.youtube.com/watch?v=tLJXJLfLCCM&list=PL05DE2D2EDDEA8D68 Go through the tutorial on Use Case Diagrams in Visual Paradigm Go through the course library examples in: examples/q6_socket examples/q8_semaphore Quiz 4 next week on pipes, sockets, semaphores