High-level Synchronization and IPC - Revision history

Dan: /* Limitations of Semaphores */ fix small formating problem

2007-10-21T23:30:12Z

Limitations of Semaphores: fix small formating problem

← Older revision		Revision as of 23:30, 21 October 2007
Line 28:		Line 28:

	Semaphores are hard to use...		Semaphores are hard to use...
	** If the programmer forgets to grab the semaphore this can lead to corruption.		* 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.		* 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.		The underlying problem is that the down and up need to be matched, with non-standard exits this can be difficult.

Rhooper: /* Limitations of Semaphores */

2007-10-17T17:14:16Z

Limitations of Semaphores

← Older revision		Revision as of 17:14, 17 October 2007
Line 46:		Line 46:
	* An object instance where only one thread can be executing certain pieces of code at once.		* An object instance where only one thread can be executing certain pieces of code at once.
	* Provides exclusive access to variables		* 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==		==Events and Message Passing==

Kchan3: /* TCP/IP */

2007-10-16T19:30:21Z

TCP/IP

← Older revision		Revision as of 19:30, 16 October 2007
Line 86:		Line 86:

	===TCP/IP===		===TCP/IP===
	* A mechanism to ~~resent~~ dropped packets		* A mechanism to resend dropped packets
	* If we build on top of TCP/IP we can assume reliable transmission		* If we build on top of TCP/IP we can assume reliable transmission

Dan: some quick formatting fixes

2007-10-13T04:33:30Z

some quick formatting fixes

← Older revision		Revision as of 04:33, 13 October 2007
Line 1:		Line 1:
	~~=High-Level Synchronization and IPC=~~

	==Dinning Philosophers Problem==		==Dinning Philosophers Problem==

Line 50:		Line 48:

	==Events and Message Passing==		==Events and Message Passing==

			[[image:Structs.jpg]]

	===Message Passing===		===Message Passing===
Line 61:		Line 61:
	** Device does something		** Device does something
	* Synchronization can be based around waiting for an event to occur.		* Synchronization can be based around waiting for an event to occur.


	When an event occurs:		When an event occurs:

Dan: finished "wiki-izing"

2007-10-13T04:31:58Z

finished "wiki-izing"

Show changes

Dan: first edit, will "wiki-ize" on preceeding edits

2007-10-13T04:04:33Z

first edit, will "wiki-ize" on preceeding edits

New page

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)