Soma-notes - User contributions [en]

Proposal Meeting Schedule

2007-10-26T04:41:01Z

Dan: /* Wednesday, Nov. 7th */

==Tuesday, Oct. 30th==

{| class="wikitable"
| 10:00 AM
|
|-
| 10:10 AM
|
|-
| 10:20 AM
|
|-
| 10:30 AM
|
|-
| 10:40 AM
|
|-
| 10:50 AM
|
|-
| 2:30 PM
|
|-
| 2:40 PM
|
|-
| 2:50 PM
|
|-
| 3:00 PM
|
|-
| 3:10 PM
|
|-
| 3:20 PM
|
|}

==Wednesday, Oct. 31st==

{| class="wikitable"
| 10:30 AM
|
|-
| 10:40 AM
|
|-
| 10:50 AM
|
|-
| 11:00 AM
|
|-
| 11:10 AM
|
|-
| 11:20 AM
|
|-
| 11:30 AM
|
|-
| 11:40 AM
|
|-
| 11:50 AM
|
|-
| 12:00 PM
| Neil Dickson
|-
| 12:10 PM
|
|-
| 12:20 PM
| Richard Gould
|}

==Thursday, Nov. 1st==

{| class="wikitable"
| 1:30 PM
|
|-
| 1:40 PM
|
|-
| 1:50 PM
|
|-
| 2:00 PM
|
|-
| 2:10 PM
|
|-
| 2:20 PM
|
|}

==Tuesday, Nov. 6th==

{| class="wikitable"
| 10:00 AM
|
|-
| 10:10 AM
|
|-
| 10:20 AM
|
|-
| 10:30 AM
| David Tremayne
|-
| 10:40 AM
|
|-
| 10:50 AM
|
|-
| 2:30 PM
| Maria Krol
|-
| 2:40 PM
| Adam Becevello
|-
| 2:50 PM
| Jeff Snell
|-
| 3:00 PM
|
|-
| 3:10 PM
|
|-
| 3:20 PM
|
|}

==Wednesday, Nov. 7th==

{| class="wikitable"
| 10:30 AM
| Kenneth Chan
|-
| 10:40 AM
|
|-
| 10:50 AM
| Adrian Batos Parac
|-
| 11:00 AM
| Dan Edmunds
|-
| 11:10 AM
| Adam McNamara
|-
| 11:20 AM
|
|-
| 11:30 AM
|
|-
| 11:40 AM
| Geoffrey Johnson
|-
| 11:50 AM
|
|-
| 12:00 PM
|
|-
| 12:10 PM
|
|-
| 12:20 PM
| Roy Hooper
|}

==Thursday, Nov. 8th==

{| class="wikitable"
| 1:30 PM
|
|-
| 1:40 PM
|
|-
| 1:50 PM
|
|-
| 2:00 PM
|
|-
| 2:10 PM
|
|-
| 2:20 PM
|
|}

Proposal Meeting Schedule

2007-10-26T04:33:10Z

Dan: /* Wednesday, Nov. 7th */

==Tuesday, Oct. 30th==

{| class="wikitable"
| 10:00 AM
|
|-
| 10:10 AM
|
|-
| 10:20 AM
|
|-
| 10:30 AM
|
|-
| 10:40 AM
|
|-
| 10:50 AM
|
|-
| 2:30 PM
|
|-
| 2:40 PM
|
|-
| 2:50 PM
|
|-
| 3:00 PM
|
|-
| 3:10 PM
|
|-
| 3:20 PM
|
|}

==Wednesday, Oct. 31st==

{| class="wikitable"
| 10:30 AM
|
|-
| 10:40 AM
|
|-
| 10:50 AM
|
|-
| 11:00 AM
|
|-
| 11:10 AM
|
|-
| 11:20 AM
|
|-
| 11:30 AM
|
|-
| 11:40 AM
|
|-
| 11:50 AM
|
|-
| 12:00 PM
| Neil Dickson
|-
| 12:10 PM
|
|-
| 12:20 PM
| Richard Gould
|}

==Thursday, Nov. 1st==

{| class="wikitable"
| 1:30 PM
|
|-
| 1:40 PM
|
|-
| 1:50 PM
|
|-
| 2:00 PM
|
|-
| 2:10 PM
|
|-
| 2:20 PM
|
|}

==Tuesday, Nov. 6th==

{| class="wikitable"
| 10:00 AM
|
|-
| 10:10 AM
|
|-
| 10:20 AM
|
|-
| 10:30 AM
| David Tremayne
|-
| 10:40 AM
|
|-
| 10:50 AM
|
|-
| 2:30 PM
| Maria Krol
|-
| 2:40 PM
| Adam Becevello
|-
| 2:50 PM
| Jeff Snell
|-
| 3:00 PM
|
|-
| 3:10 PM
|
|-
| 3:20 PM
|
|}

==Wednesday, Nov. 7th==

{| class="wikitable"
| 10:30 AM
| Kenneth Chan
|-
| 10:40 AM
|
|-
| 10:50 AM
|
|-
| 11:00 AM
| Dan Edmunds
|-
| 11:10 AM
| Adam McNamara
|-
| 11:20 AM
|
|-
| 11:30 AM
|
|-
| 11:40 AM
| Geoffrey Johnson
|-
| 11:50 AM
|
|-
| 12:00 PM
|
|-
| 12:10 PM
|
|-
| 12:20 PM
| Roy Hooper
|}

==Thursday, Nov. 8th==

{| class="wikitable"
| 1:30 PM
|
|-
| 1:40 PM
|
|-
| 1:50 PM
|
|-
| 2:00 PM
|
|-
| 2:10 PM
|
|-
| 2:20 PM
|
|}

High-level Synchronization and IPC

2007-10-21T23:30:12Z

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

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

Computer Organization

2007-10-21T17:09:47Z

Dan: /* SIMD Processors */ fix a small mistake, wrote "introduction" instead of instruction

==Computer Organization==

===Introduction===

* Information has been posted on the [http://homeostasis.scs.carleton.ca/os/index.php/Main_Page class website] regarding running a Linux distribution on your own home machine (or a virtual desktop environment). Students are encouraged to familiarize themselves with the linux/unix environment as it is far less restricted and more robust than Windows/OSX.
* Our research paper (ie. Operating Systems) should be well on its way. Students should have key words and topics narrowed down.

===Stored Program Computer===

The concept of a stored program computer began in the early 1800s with Charles Babbage and his "''Difference Engine''". Since then it has evolved into what we now consider '''Von Neumann Architecture'''. Although Von Neumann was only a piece of the puzzle of modern day computer architecture, we still refer to the architecture as being named after him. In more recent times, the overall Von Neumann model has changed, but conceptually, it is still the same. Several different components talk to each other (via buses) all at the same time - this scenario can be very complicated at times.

[[Image:Neumann.jpg]]

===Central Processing Unit===

The '''central processing unit''' (CPU) is made up of an Arithmetic Logic Unit (ALU) and Control Unit (CU).

====Arithmetic Logic Unit====

The '''ALU''' can perform all arithmetic (addition, subtraction, multiplication, division) and logical (AND, OR, NOT ... ) calculations at a very rapid rate.

====Control Unit====

The '''CU''' is made up of several components and duties :

* ''Program counter'' or PC is the address of the currently executing instruction.
* ''Status word'' is used to store information regarding the current state of the control unit. Information such as overflows and execution status can be stored. A word is typically what the processor natively deals with in terms of data size. Most modern processors are 32 or 64 - bits. That is, their registers store data segments that are 32 or 64 bits wide - which we collectively call a word. The size of the word will vary from CPU to CPU.
* Responsible for the ''fetch-decode cycle'' which is an algorithm that grabs information from main memory, reads it, decodes it and then hands it off to the specific part of the processor to handle the instruction (oftentimes in involving the ALU).

The above description of the control unit is very simplified. It is actually a reflection of a CPU in the early to mid 1980s. For instance, '''Moore's Law''' states that that every 18 months, the number of transistors that sit on a CPU chip will double. This "law" was introduced in the 1960s and currently still holds true. '''Why?''' Mainly because the industry targets themselves towards this figure. Given '''Moore's Law''', you can imagine how much CPU architecture has changed since the 1980s.

====Transistors====

With all of these extra transistors, what can we do with all of them? One (or both) of two things :

=====Integration=====

'''Integration''' refers to more and more components getting packed into the CPU. Devices such as :

* ''Memory Controller'' (circuitry needed to drive the RAM)
* ''Math Co-Processor'' (handles floating point values)
* ''Memory'' Management Unit (MMU - used for virtualization)
* ''L1 & L2 Cache'' (used for fast memory access when we don't want to go all the way to main memory. L1 cache is small but fast. L2 cache is large but slower).
* ''Systems on a Chip'' : systems that have all transistors incorporated into a single chip. These currently exist, but are fairly slow in regards to overall performance.

=====Duplication=====

'''Why have one ALU when we can have 10?''' Modern processors use this technology quite a bit. Certain components can only be duplicated so much. '''Why?''' Aside from hardware constraints, we also have bottlenecks. For instance, a CPU has only one PC (program counter). What is the point of having several ALUs if the program counter can not keep up?

The most common forms of '''duplication''' include :

* ''Pipelining'' : In pipelined CPUs a specific function unit of a CPU is partitioned into K smaller parts, called '''pipelined stages'''. When an operation is to be executed, it goes through the K stages of execution. The stages can execute independently and in parallel because they are separate units of hardware. The operation can be broken up into pieces where each stage can work on a particular piece so no part of the CPU is left idle. What happens if two instructions need the same piece of hardware? The CPU can guess which way the instruction will go afterwards and continue on its way. If it later learns that the path it took was incorrect, it can roll back its changes and carry on with the correct path. If the guesses are constantly wrong, the system is slowed down to a crawl. This entire process of 'guessing' is known as '''speculative execution'''.

[[Image:Pipeline.jpg]]

* ''Thread Level Parallelism'' : if we can't get a single instruction stream parallelized, we can just have several separate threads. This means we can share all of the address space information such as cache because the threads will be running in the same process.

* ''Multi core'' : the most current technology in practice. After several years of packing CPUs with more and more features, bottlenecks began to arise. '''Solution?''' Duplicate the CPU! As the industry currently shows, more and more computers are being released with '''dual''' or even '''quad core''' processors. What are some bottlenecks that can arise with '''multi core processors'''? The bus is one obvious answer. If we increase the amount of information the buses can handle, we can accommodate multiple CPUs.

* ''CPU cache'' : Why not get rid of RAM altogether and simply put all of it on the CPU as L1 or L2 cache? Cache memory is known as '''static memory''', whereas RAM is known as '''dynamic memory''' or '''DRAM'''. DRAM can store information using about 1/4 of the amount of transistors as static memory. This is why there is only around 4MB of CPU cache available in most modern day processors. What RAM lacks in speed it makes up in size and parallelism.

The book " [http://books.google.ca/books?id=R7Frpn3g9AEC&dq=&pg=PP1&ots=f0kVd8_wKX&sig=66x6OTPMjfzJneY-mOHyQJOC1iM&prev=http://www.google.ca/search%3Fhl%3Den%26client%3Dfirefox-a%26rls%3Dorg.mozilla:en-US:official%26hs%3DdDa%26sa%3DX%26oi%3Dspell%26resnum%3D0%26ct%3Dresult%26cd%3D1%26q%3DComputer%2BArchitecture%2BHennessy%2BPAtterson%26spell%3D1&sa=X&oi=print&ct=title#PPP1,M1 Computer Architecture : A Quantitative Approach] " by Hennessy and Patterson is an excellent book on CPU Architecture.

What does all of this have to do with Operating Systems? If the OS does not understand resources (underlying hardware), then the system is doomed. We have to design the OS around the architecture (especially important with multi-core systems).

===Latency & Bandwidth===

Imagine the following situation : We have two facilities, A & B. A very large amount of information has to be transfered between the locations. We can do it in one of two ways :

* Load up a semi-truck full of hard drives that are full of the information needed.
* Connect the locations together via fiber optical cable to transfer the information.

'''Q''' : What method will allow the most information to be transported?

'''A''' : Obviously the truck full of hard drives, especially with modern day drives being capable of storing up to a Tera-bye of information. The amount of information to be transfered is known as '''bandwidth'''.

'''Q''' : What is the quickest way to get one single bit of information from location B to location A?

'''A''' : This time, the answer is the fiber optic cable. How quickly information is transfered is known as '''latency'''.

[[Image:Hds.jpg]]

The above situation is also apparent when dealing with RAM. RAM is known as high-latency, high bandwidth. Moving large amounts of data to the CPU can sometimes be sped up using the cache. This issue is a very commonly studied topic in the world of RAM - CPU connections.

Other devices and their latency :

* CPU registers : lowest latency
* L2 & L1 Cache : low latency
* Hard disk : highest latency

====I/O====

There are several different ways '''Input/Output''' devices can communication to the CPU and RAM :

* ''Polled I/O'' : Think of it as giving a person a task. You can poke the person every 5 minutes to see if they have completed the task. If the person has finished the task, they have to respond with a 'yes', otherwise 'no'. In this scenario, one party has to poke every 5 seconds and another party has to respond every 5 seconds as they get poked. Obviously, not the most efficient solution.

* ''Interrupt I/O'' : In this situation, when giving the person the task, we simply ask them to tell us when they have completed it. Much more efficient than polling.

If we have a '''small''' amount of data being processed by the I/O device, then our system runs relatively efficient. If the data is a large in size, the communication involved between the I/O device, the CPU and the RAM is frequent. There are two solutions to this problem:

* ''Memory Mapped I/O'' : devices are associated with logical primary memory addresses rather than having a specialized device address table.

* ''Direct Memory Access (DMA)'' is when devices and their controllers are able to read and write information directly from the primary memory without any CPU getting in the way. The DMA contains the same algorithms the CPU uses, except conceptually it does not need any registers. This direct access can increase the speed significantly.

* ''Intelligent Devices'' : a final alternative is to have memory and chip sets that act in a way the CPU does on the I/O device itself. This means we do not need to talk to the CPU or RAM at all (it can all be done on the device itself).

===SIMD Processors===

'''Single Instruction Multiple Data (SIMD)''' processors handle one instruction accompanied with an entire array of data. This type of architecture is quite efficient at processing large amounts of data that all need to be operated on using the same instruction. Processing speeds are increased significantly because the processor does not have to decode every single instruction(since all pieces of data are only using one single instruction). Multimedia devices like MP3 players and gaming consoles all take advantage of this technology, these machines are also known as vector machines.

The Sony PS3 has one MIMD (multiple instruction, multiple data) processor and several SIMD processors. Compilers need to be adjusted and game programmers need to adapt their writing skills in favor of this new technology. Someone eventually has to slave over a library of machine language instructions in order to optimize the particular application to SIMD technology (not the most exciting task).

===Boot Process===

How is the OS started? How does the computer go from powering on to running the Operating Systems (Windows, OSX ...). This process takes a really long time when you consider how fast computers have become, '''why''' is this? This occurs because the system must determine all of the hardware present in the machine, each hardware's manufacturer, specifications, requirements etc. It can become a real mess! Before the OS can even begin to start, all of the hardware in the system must be properly configured. This all begins with the BIOS.

====BIOS====

'''BIOS (basic input/output system)''' is the code that runs before any other code runs. It is built into the system. In older times, the BIOS was burned into the machine and never changed. Nowadays, it can be flashed and reprogrammed. This can occur when bugs in the BIOS are so troublesome, that an update is needed (typically when the OS does not work well with the hardware). The BIOS configures all the hardware by running diagnostics etc. After hardware is configured, how is the OS launched? This process is not direct, mainly because the BIOS has limited capabilities because of legacy issues. The BIOS is configured in a way that it believes your computer's hardware is reflective of the year 1982. This means it believes you only have several megabytes of RAM, an 8086 processor, limited disk space and so on. It does however, know how to load information of up to 512 bytes. This is where bootstrapping comes into play.

====Bootstrapping====

After hardware is configured, the BIOS runs a small amount of code (approx 400 bytes, while the remaining amount is used to store partition tables) known as the '''boot block'''. The BIOS loads this algorithm into memory where it is executed. The '''boot block''' is just enough code to load another algorithm that makes the machine reflect more of what it really is (not an 8086). From here we can initialize RAM, hard disk and eventually start the OS.

Macintosh computers, run a next generation, more sophisticated BIOS called '''EFI'''. The EFI allows the computer to go from BIOS to OS startup more easily and direct. This is because the EFI recognizes the hardware of the computer for what it truly is. Older macs use '''open boot''', which is a BIOS that allows the user to enter commands via a prompt.

High-level Synchronization and IPC

2007-10-13T04:33:30Z

Dan: some quick formatting fixes

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

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

High-level Synchronization and IPC

2007-10-13T04:31:58Z

Dan: finished "wiki-izing"

=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

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

High-level Synchronization and IPC

2007-10-13T04:04:33Z

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

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)

File:Structs.jpg

2007-10-13T04:03:28Z

Dan:

File:DiningPhilosophers.jpg

2007-10-13T04:01:37Z

Dan: