- Mutexes and semaphores are used to control access to resources (such as variables) shared by many threads running concurrently. The order in which the threads run is unknown to the programmer and and funny things can happen if shared resources are not properly protected.
A classic is example of this is a simple program in which you initialize a simple counter variable (say int count = 0) and have two threads each run the following loop: ( for(int i = 0; i < 1000; i++) count++; ). If two threads run, we would expect that ‘count’ will have the value of 2000. However, this may very well not happen because of a “race condition.” The statement count++ is not “atomic” i.e. it takes multiple steps to execute this command. More specifically, the value from count is read, incremented, and then this new value is stored back into count. However, say thread 1 reads the value 100 from count, but at this moment, the scheduler decides to preempt thread 1 and allow thread 2 to run for a while. In this time, thread 2 increments count to say, 200. Thread 2 is now stopped and thread 1 is allowed to run. It increments the value 100 it previously read to 101 and assigns this to the value of count (therefore count goes from the value 200 to 101). Notice we just lost 100 increments. This can be fixed by “locking” access to the count variable. Locking is often done with mutexes or semaphores.
A semaphore is effectively a counter that can be incremented/decremented atomically. Upon construction, it is given a max value it is allowed to take. Semaphores are commonly used in “producer-consumer models.” An example of this is people queuing up for an amusement park ride. Say the ride can only accommodate 10 people, then it would be bad if more then 10 people tried to get on the ride at the same time. What we can do is have the riders increment a semaphore as they get on the ride, and decrement it as they get off the ride. If the semaphore is already at 10 when a rider wants to board, make them wait in line.
A mutex is effectively a key that allows a thread to use a resource. Consider a key to a door to a bathroom with a single stall. If you have the key, lock the door behind you, then another thread can’t barge in when the bathroom is in use.
There is a also a notion of a “binary semaphore” which I think the Google question is alluding to. A binary semaphore is a semaphore that can take the values of either 0 or 1. I’ve heard mutexes described as being equivalent to a binary semaphore, which is wrong. I think this is really the heart of the Google question. A big differences is that mutexes have the concept of “ownership.” Only the thread that owns the mutex (i.e. was the thread that originally claimed the mutex) can give it up. If another thread tries to free the mutex, this will cause an error. With semaphores, basically any thread is allowed to manipulate them.
I’d use a mutex to protect the increment operation.
- I think I’ve already explained briefly what multithreaded programming is above. Deadlock (in multi-threaded programming) is the case where you have multiple threads, work still needs to be done, but the threads can’t make any significant progress for some reason. Often the cause is improper locking. Say you have two threads (t1,t2), one resource ®, and two mutexes (m1, m2). Say in order that the tasks assigned to each thread require the resource R at some points and that for a thread to access R, it needs both the mutexes m1 and m2. Consider the case when t1 and t2 simultaneously want to access R, t1 claims m1 and t2 claims t2. They still need the other mutex so the wait for it to become available, except that it never will. We now have a case of deadlock.
Multi-threading is often quite hard to get right. It also can be quite hard to debug as the order of execution of threads is in essence quite random from the viewpoint of the programmer and maybe you have a bug that only shows up 1 in 100 times the program is executed.
- As far as I know, Java doesn’t have “const” (a C++ thing). Java’s equivalent is final. A variable assigned the property of final must be initialized to some value and can’t be changed by the program during runtime.
That being said, the style of questions I was asked for when I interviewed with Google were quite different then those that were in the list (I applied for both program manager and software engineer).