Previous

[ 12.html ]

Preparation

Study pp158-168 Concurrency

Topics

Demo Message Passing Concurrency

Java

Concurrent structures

Concurrent means: faking the effect of using many computers on a single one.

The book has a small error. You don't have to extend Thread to create a Thread. All you need to do implement the 'Runnable' interface. For example,

 		class ThreadedApplet extends Applet implements Runnable {

The Runnable interface requires that you define a

 		public void run(){...}

function.

Task Parallelisms

Data Parallelisms

Difficulties

. . . . . . . . . ( end of section Topics) <<Contents | Index>>

Questions

What are the important features for automatically generated programs

The bottom line is the total cost, over the whole life time of the software. This includes the cost of research, development, production, run time, and maintenance. The running costs include the size of the produced program and its speed. If the hardware is big enough and the fast enough the cost of running the software is the smallest item of the all the factors. So, given that an automatically generated program is fast enough on the existing hardware then it will probably pay off.

So far, no automatic programming tool has ever become mainstream since the invention of high level imperative languages: FORTRAN, LISP, COBOL.

One of the dreams of tool developers is a program that accepts requirements and generates programs from it. If such a tool existed then we could feed it the requirements:

1. Input a program and report correctly if it halts or not on all data.

   This would produce a program that solves the Halting problem. Since no such program exists, we can be sure that most automatic programming tools and techniques are in some way or other limited.

   Surat2.java has problems

   Yes. This is why I abandoned it and moved on to Surat3, Surat4, and so on.

   On page 161 explain (n[L]-N[t])+1

   The example in the book is finding "test" (n[t]=4) inside "here is a test string" (n[L]=21), so there are 21-4+1 places "test" might appear in "here...string".

    		<--------n[L]------->

    		here is a test string

    		test

    		.test

    		..test

    		...test

    	[...]

   		.................test

   The target string can be in the 0th, 1st, 2nd,..... (n[L]-n[t])th place. THe result follows.

   Is there any systematic way, like Petri Nets, for handling task and data parallelism

   Handling task and data parallelism in real problems is still a research topic. You had best talk to Mr. Gomez who is doing a Ph.D. on the topic.

   Petri Nets are one of those elegant, intriguing, powerful bits of mathematics that has been used for many toy problems, but few real ones. They are even part of the UML!

   I see one catch with handling general task/data parallelism with Petri Nets. A Petri Net can not be parameterized by the amount of data and we nearly always need a solution not for 200 items but for n.

   For more on Petri Nets see the end of our text and [ Petri%20Nets in math_76_Concurency ] my rough notes on them.

   Note: Petri Nets and the last chapter is a topic available for a Presentation/Paper at the end of the term.

   How do we get the formula on page 165

   The formula states that n sequences of L instructions, and the sequences are interleaved in any way possible then there are
2. I(n,L) = (n*L)!/(L!)^n

   I'll bet the author looked it up in a text or reference. It looks like a number of standard bits of combinatorics.

   I don't see a short proof at this time.... let me mull this over.

   Why does it say that "test alone might reveal errors in concurrent programs

   A test is when we run a program with a given set of data. If the program is non-deterministic then it does different things each time it is run, on the same data. Typically we have no control over the precise interleaving of steps in a concurrent program. So run it as many times as you like... it may never execute the one sequence that break the code.

   When there are many possibilities it becomes almost certain that a small number of test runs (say 1,000) with each set of data will not find a single hidden flaw.

   This is nice theory.

   In practice this is what happens.

   Concurrent programs are tested for months, they are released, and shortly an unexpected sequence occurs and the program fails. Classic examples include the Galileo space probe and a bank accounting system.

   What should we do? We should apply "Model Checking" which uses computer power to help assure that every possible sequence of events does not lead to requirements being broken. Take Csci656 for more on this topic.

   Shouldn't Java classes have names that start with CAPITAL letters?

   Yes. This is the accepted style. But, I don't think that it is part of the syntax. I'm sure, that most compilers don't care. The style dates back to SmallTalk and has now taken over.

   Does the JVM use special machine code instructions to handle parallelism?

   I'm sure that the JVM, like all concurrent programs is forced to rely on machine code instructions that implement atomic P and V semaphore operations. I have no information on whether they us other features as well. However I would guess they do.

   What problems happen in concurrency?

   The problems were first seen on railways where it is vital to make sure that two trains do not get onto the same piece of track at one time. This was 150 years ago. But today railway software must meet the same requirments.

   A Classic problem is getting the wrong answer when two or more processes access the same data at the same time. For example, if two people go to the bank and both take out $40 from the same account at the same time the data may not show that $80 has been removed. Each thread executes:

    		{ get bal; bal=bal-40; put bal;}

   If the execute one after the other all is well, but suppose they execute in this order:

    	{ get bal;      bal=bal-40;            put bal;}

    	     {    get bal;           bal=bal-40;       put bal;}

   These are a form of Race Hazzard.

   We can avoid these problems by using locks and these depend on semaphores. When we have locks we can have deadlock.

   Even without deadlock we can have starvation.

   What is the difference between deadlock and starvation?

   In deadlock, two or more processes are all stopped and waiting for another process to do something.

   In starvation, no process is waiting for another one, but some processes never get to do anything. Typically a low priority process never gets the CPU time to do any work.

   This all comes under the topic of fairness and liveness.

   There was a nice Java demonstration of the Dining Philosophers on the web a year or two ago.

   How do you get a deadlock in Java?

   Very easily. Have two threads and two other objects. Thread 1 needs to synchronize on both objects A and B. Thread 1 needs them but asks in the reverse order: B then A.

   Consequence: Thread 1 waits for B and is synchronized on A. Thread 2 is synchronized on B (stopping Thread 1) and waiting for Thread 1 to get out of A.

   There is a paper in ACM SIGPLAN that showed how difficult it was to avoid deadlock! This is a suitable paper to summarize and present at the end of this class. ACM SIGPLAN is in the library.

   How do start() and join() in Java know which functions to execute?

   They look for the void function called run with no arguments. This is why all Threads and Runnable classes must implement the

    		public void run();

   function.

   What is a Race Hazzard?

   When there are several parallel processes and the result depends on which does an operation first then we have a race hazzard.

   These first emerged when digital logic circuits were first built and would fail because a pulse would arrive at the wrong time relative to another pulse.

   The image is of a horse race.... several pulses racing towards the finishing post and were the first one to arrive has a powerful effect on the result.

   Does multithreading in object-oriented programming reduce information hiding and reuse.

   The book says this in the last paragraph of the chapter.

   The only case I know of where this occurred was when Grady Booch designed a large library of data structures in Ada. Each data structure had 2 or more variations depending on whether the programmer believed that the program was multi-threaded or not. They had the same interfaces but different implementations. One could not unplug an inefficient version because the inefficiency might be caused by a need to handle threads.

   I don't think this a very important point in terms of reuse.

   How does extensibility let you corrupt the design of software?

   A little creative stupidity does the trick:

    	class A{ .... int i;  void fun(){ i++; } ....}

    	class B extends A{ void fun(){ i--; } ...}

   Now objects of type A and type B are use in the same way but the B's behave subtley different.

   Conclusion: if we have extension then we need programming by contract to keep functions from breaking the parental code.

. . . . . . . . . ( end of section Questions) <<Contents | Index>>

Laboratory

Experiments with writing and publishing Applets: [ lab13.html ]

Next

Study pages 169..178 and the LISP handout. Prepare questions on both LISP and the reading in the text. Outline: [ 14.html ]

. . . . . . . . . ( end of section CS620 Session 13 Java103) <<Contents | Index>>

Glossary