High-level Synchronization and IPC
Dinning Philosophers Problem
- Thought experiment used to understand synchronization primitives
- Five philosophers are dining at a frugal Chinese restaurant where they are only provided with one chopstick each. They need two chopsticks to pick up the noodles in order to eat.
- Whenever they are hungry they pick up two chopsticks to eat.
- When they are done eating they put down the chopsticks.
- The philosophers do not talk to each other about eating, only high-minded ideas.
- Have to define a strategy to make sure that no philosopher starves to death.
- We can think of each chopstick as a semaphore.
Problems
- Starvation
- One (or more) philosopher is never able to get two chopsticks and dies.
- Deadlock
- All philosophers have one chopstick and are waiting for another philosopher to put one down and they all starve to death.
Possible Solutions
- Could use a scheme involving timeouts, but we want a PERFECT solution
- Could use synchronization; philosophers either grab one chopstick or none, this illustrates AND synchronization
How could AND synchronization be implemented?
- Could turn multiple semaphores into one by abstracting the semaphores into 1 class.
- In general this is done by encapsulating the resources and using another process/thread/program to hand them out
Limitations of Semaphores
Semaphores are hard to use...
- If the programmer forgets to grab the semaphore this can lead to corruption.
- If the programmer never releases the semaphore this can lead to the program locking.
The underlying problem is that the down and up need to be matched, with non-standard exits this can be difficult.
But in C it's all you've got...
- Solution: write a program to check the code (eg: Stanford Checker)
- Problem: not reliable, can produce many false positives
How about building synchronization into the language as a base level construct?
- Java's synchronized
- Hides semaphores from developer
- Developer still has to decide where to synchronize
- Don't want to synchronize all your code, this leads to single threaded behaviour
General idea: Monitor Object
- An object instance where only one thread can be executing certain pieces of code at once.
- Provides exclusive access to variables
Events and Message Passing
Message Passing
- Uses buffers
- Message passing is used in large contexts
Events
- Message queue
- When do they occur?
- User does something
- Device does something
- Synchronization can be based around waiting for an event to occur.
When an event occurs:
- It has to be stored (in a buffer)
- It might not be processed right away
- What if the event is no longer relevant?
- Could implement events with timeouts
- What if no one's listening for the event?
- Could drop the event
- The challenge is determining which events should be dropped and which should be queued.
- In the case of a file open if the event is dropped there will be a leak
- In the case of mouse movement when no application is listening we want to drop it so that if an application starts listening to mouses events the mouse doesn't go crazy
- What if the event is no longer relevant?
Message passing in a WAN
Message passing in a WAN is unreliable. Packets can be dropped.
In some cases it is acceptable to lose the data
- Streaming video
- VOIP
- Cell phones
In others we need a reliable transmission
- Downloading content
TCP/IP
- A mechanism to resend dropped packets
- If we build on top of TCP/IP we can assume reliable transmission
NAT (Network Address Translation)
- Used in local networks, to the outside world the whole network appears as a single address, NAT devices remember outgoing requests to route the response to the correct party.
- Firewalls will automatically drop messages that do not have a corresponding outgoing request
- Firewalls will often only let certain types of traffic through, often only TCP/IP
- Application developers may want to use UDP but may be forced to use TCP/IP to get through the firewall
- Firewalls will often only let certain types of traffic through, often only TCP/IP