View source for High-level Synchronization and IPC

==Dinning Philosophers Problem==

[[Image:DiningPhilosophers.jpg]]

* 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

From review lecture Oct 17th:

A monitor is a language construct for doing mutual exclusion.  In Java this is known as synchronized.

==Events and Message Passing==

[[image:Structs.jpg]]

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

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