Marco van de Voort wrote:
> On 2008-04-28, Scott Moore <samiam@[EMAIL PROTECTED]
> wrote:
>>> My main problems involve threading. However not the base primitives,
but
>>> actually splitting out algorithms over multiple cores.
>>>
>>> Fix that, and more people than just me will be interested.
>> Sounds a lot like IP Pascal :-)
>
> Can you give an example? My interests mostly stem from the fact that for
non
> trivially paralellizable tasks, I manually have to program merging the
> datastructures.
>
> And the trade is one of the few where a bit of performance doesn't hurt
> (surface defect detection at 100MB/s)
The overview of IP Pascal is here:
http://www.moorecad.com/ippas/index.html
Under the "language" button, third down on the left.
IP Pascal features monitors and processes. The normal "program" module,
along with the modules it can use ("module" = TP "unit") form the main
main or default thread. Another thread can be set up with a "process":
process mythread;
uses mymonitor;
var x, y, z: integer;
procedure q;
begin
end;
begin
<code for thread to run>
end.
Ie., it has the exact syntax of a program, but is actually executed
in its own thread. A process module cannot appear in a "uses" statement
for another module, and a process module can only use "monitor" or
"share" modules. Any number of threads can be created by adding more
process modules.
A monitor module appears as a normal module:
monitor x(input, output);
private
var y: integer;
procedure x(var a: integer);
begin
y := a
end;
begin
{ initialization }
end;
begin
{ finalization }
end.
Except that monitors must have all of their global variables
declared as private. Any call of a monitor procedure or function
from the outside is multitask locked on entry to the procedure
or function, and unlocked on exit. There is one lock for the
entire monitor that locks all of the data in the monitor.
As normal modules do, a monitor can contain both startup and
shutdown sections, or just a startup section. A ';' following
the main block instead of a '.' introduces the shutdown
section.
Globally accessible monitor routines also have the characteristic
that their parameters, and function results, cannot be or contain
pointers. The so called "pointer barrier" prevents the monitor
from breaking its locking mechanisms by effectively ex****ting
addresses.
In addition, a monitor cannot call an external procedure or
function with a var (call by reference) parameter, but it can
be called by an external module with var parameters. This, again,
prevents the monitor from ex****ting references to its data.
Monitors can call other monitors, or share modules.
Finally, a "share" module" is simply a module that has no
global variables at all:
share stuff;
procedure x;
begin
end;
..
It has no initialization or finalization block at all, since it
has nothing to initialize. A share module can be called by anyone,
and serves as a place to put routines that can be used by any
thread, since they have no global data to be in conflict.
As described above, a monitor would allow two threads to
communicate, but it would require polling. The final key to
multithreading is the "semaphore" variable:
var mysignal: semaphore;
And the standard functions:
procedure signal(s: semaphore);
procedure signalone(s: semaphore);
procedure wait(s: semaphore);
These standard procedures all must be executed from a monitor
only (because they are associated with the lock a monitor
provides).
Semaphores are FIFO queues for threads awaiting signals between
threads. A thread enters the queue by executing a "wait", and
will hold there until signaled.
Executing signal() or signalone() will cause either all of the
threads awaiting a queue, or just one thread, to be released.
When a thread waits for a signal, it effectively exits the
monitor lock that it was called in on entry to the wait, then
reasserts the lock on exit from the wait.
PUTTING IT ALL TOGETHER
The standard "demo" app for IP Pascal threading is the "marco
polo" program:
monitor linecontrol(output);
type string = array of char;
private
procedure writeline(view s: string);
begin
writeln('Task output: ', s);
end;
begin
end.
process thread1;
begin
while true do writeline('I am process A')
end.
program thread2;
begin
while true do writeline('I am process B')
end.
Which would print:
Task output: I am process A
Task output: I am process B
Task output: I am process A
Task output: I am process B
Task output: I am process A
Task output: I am process B
Task output: I am process A
Task output: I am process B
....
Etc., forever. If the threads wrote directly to the output
themselves, the characters would be mixed at random. The linecontrol
monitor only allows one line to print at a time, and serves as
a line output controller.
The output is interleaved as a/b/a/b... not as a coincidence, but
because the monitor locks are fair, that is, the first come to the
lock is the first served. This is an essential property to avoid
defacto deadlock.
Monitor locks have the property that if they are recursively called,
they will not deadlock. That is, if a monitor calls itself, either
directly or indirectly, it will not deadlock.
However, IP Pascal, although it prevents data corruption via multiple
threads, is not deadlock proof. It is possible to deadlock via two
monitors that call each other.
DATA QUEUING EXAMPLE
monitor queue;
type byte = 0..255; { data type for queue }
procedure inqueue(b: byte); forward;
procedure outqueue(var b: byte); forward;
private
const maxque = 100; { maximum length of queue }
type queinx = 1..maxque; { pointers for queue }
var fifo: array [queinx] of byte; { fifo for queue }
inptr: queinx; { in pointer }
outptr: queinx; { out pointer }
notempty: semaphore; { not empty signal }
notfull: semaphore; { not full signal }
{ queue pointer iterator }
function next(i: queinx): queinx;
begin
if i = maxque then i := 1 { queue has wrapped }
else i := i+1; { next location }
next := i { return result }
end;
{ test queue is full }
function empty: boolean;
begin
empty := inptr = outptr { pointers are equal }
end;
{ test queue is empty }
function full: boolean;
begin
full := next(inptr) = outptr { next input location is out location }
end;
{ place byte in queue }
procedure inqueue(b: byte);
begin
{ if full, wait until a byte clears }
while full do wait(notfull);
{ place input byte }
fifo[inptr] := b;
{ set next input location }
inptr := next(inptr);
{ signal queue is now not empty }
signal(notempty)
end;
{ get byte from queue }
procedure outqueue(var b: byte);
begin
{ if empty, wait until a byte is available }
while empty do wait(notempty);
{ get output byte }
b := fifo[outptr];
{ set next output location }
outptr := next(outptr);
{ signal queue is now not full }
signal(notfull)
end;
begin { constructor }
{ set input = output, and queue is empty }
inptr = 1;
outptr = 1
end.
This basic monitor allows two threads to exchange data. Of course,
the data could actually be any size, including structured types.
So this is the basic outline of a message passing monitor.
CONCLUSION
Besides offering multiple threads, the tasking mechanisim in
IP Pascal offers protection because it unites type security with
the monitor concept, as was outlined by Per Brinch Hansen in the
1970's. Because monitors, semaphores and the rest are built in
language contructs, IP Pascal does not need to have the equivalent
of a C "volatile" statement to declare variables as multitaskable.
IP Pascal knows when and when not to cache variables.
Per Brinch Hansen talked about Java Parallelism in "Java's insecure
parallelisim", which was basically about the fact that Java
implemented monitors as being optional for the user, ie., the
user could create multithreaded programs and easily bypass the
protections of the monitor.
This kind of thing (fortunately or unfortunately) gives the current
advantage in multithread/multicore to type secure languages like
original Pascal and Ada. You can add monitors to an insecure language,
but monitors will then themselves fail to be secure. Java represents
the odd case of a fairly secure language implementing monitors
without their security.
IP Pascal features the ideas of Concurrent Pascal, but is backwards
compatible with general Pascal. For example, CP does not allow pointers,
whereas IP Pascal simply restricts them with respect to monitor use.
Also, CP is designed to prevent deadlock by source level verification,
whereas IP Pascal is not inherently deadlock proof, it it up to the
user to avoid deadlock, although using the monitor concept, instead
of simple user called lock and unlock statements tends to avoid
deadlock by avoiding the need to track when and where such locks are
used. The reason IP is not restricted to the point of deadlock avoidance
is that we found on applying monitors to sample problems in
multitasking, that if the monitors were made deadlock proof, the system
would be unable to solve certain problems, and would be forced to
use the deadlock proof monitors to implement a second level locking
system that could, itself, deadlock.
Scott Moore
|
