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

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

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