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. 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

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 takes care of semaphores

   - 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: - message queue - when do they occur?

   - user does something
   - device does something

- synchronization based on waiting for an event

Message Passing - uses buffers - message passing is used in large contexts

When an event occurs: - it has to be stored (in a buffer) - 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
            - In the case of a file open if the event is dropped there will be a leak

Message passing in a WAN

Message passing in a WAN is unreliable. Packets can be dropped.

In some cases we can lose the data - streaming video - VOIP - cell phones

In others we need a reliable transmission - downloading content

TCP/IP - a mechanism to resent dropped packets - if we build on top of TCP/IP we can assume reliable tranmission

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

Further Reading: http://en.wikipedia.org/wiki/Dining_philosophers_problem http://en.wikipedia.org/wiki/Monitor_(synchronization)