Co_Routines Support for Oberon

http://www.zinnamturm.eu/downloadsAC.htm#Co_ http://sourceforge.net/projects/ta1/files/co2.0

Re: Co_Routines Support for Oberon

Postby Dmitry Dagaev » Fri Mar 31, 2017 12:35 pm

ObxPhilosophers - dining philosophers example

Famous Edsger Dijkstra competing for access problem.

Code: Select all
   PROCEDURE Left (i: INTEGER): INTEGER;
   BEGIN RETURN (i+N-1) MOD N END Left;

   PROCEDURE Right (i: INTEGER): INTEGER;
   BEGIN RETURN (i+1) MOD N END Right;
   
   PROCEDURE Print;
      VAR j: INTEGER;
   BEGIN
      FOR j := 0 TO N-1 DO
         CASE philosopher[j].state OF
         | THINKING: Log.String("THINKING");
         | HUNGRY: Log.String("HUNGRY");
         | EATING: Log.String("EATING");
         END;
         IF j < N-1 THEN Log.Char('.') END
      END;
      Log.Ln
   END Print;

   PROCEDURE Test (i: INTEGER);
   BEGIN
      IF (philosopher[i].state = HUNGRY) & (philosopher[Left(i)].state # EATING)
      & (philosopher[Right(i)].state # EATING) THEN
         philosopher[i].state := EATING;
         Print;
         Co.SemUp(philosopher[i].sem)
      END
   END Test;
   
   PROCEDURE TakeForks (i: INTEGER);
   BEGIN
      philosopher[i].state := HUNGRY;
      Print;
      Test(i);
      Co.SemDown(philosopher[i].sem);
   END TakeForks;

   PROCEDURE PutForks (i: INTEGER);
   BEGIN
      philosopher[i].state := THINKING;
      Print;
      Test(Left(i));
      Test(Right(i));
   END PutForks;
   
   PROCEDURE Do (t: Ct.Task) ;
      VAR ph: Philosopher;
   BEGIN
      ph := t(Philosopher);
      WHILE ~ph.eor DO
         Co.Sleep(ph.t_thinking);
         TakeForks(ph.i);
         Co.Sleep(ph.t_eating);
         PutForks(ph.i);
      END
   END Do;

The forks are limited resource, each philosopher can eat having both of them. The forks are protected by semaphores.

Console listing is as following:

THINKING.THINKING.THINKING.THINKING.HUNGRY
THINKING.THINKING.THINKING.THINKING.EATING
THINKING.THINKING.THINKING.HUNGRY.EATING
THINKING.THINKING.HUNGRY.HUNGRY.EATING
THINKING.THINKING.EATING.HUNGRY.EATING
THINKING.HUNGRY.EATING.HUNGRY.EATING
HUNGRY.HUNGRY.EATING.HUNGRY.EATING
HUNGRY.HUNGRY.EATING.HUNGRY.THINKING
EATING.HUNGRY.EATING.HUNGRY.THINKING
EATING.HUNGRY.THINKING.HUNGRY.THINKING
EATING.HUNGRY.THINKING.EATING.THINKING
Dmitry Dagaev
 
Posts: 65
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Postby Dmitry Dagaev » Fri Mar 31, 2017 1:06 pm

ObxActions ObxTActions

Running Co_Routine (ObxActions) and Co_Task (ObxTActions) in background.

Cooperative multi-tasking via coroutines implements the ObxActions  docu example from BlackBox Obx. Since original example is the simplest one, it makes one iteration per cycle for primes calculation. In order to reach sensable processor load it is necessary to repeat the same example for 400000 times in the scheduler.

Running example with recommended parameters results in Upper Bound= 256
N Attempts= 400000(In my computer it is the similar time 15sec for ObxActions with one attempt and Co_ObxActions with 400000).
Dmitry Dagaev
 
Posts: 65
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Postby Dmitry Dagaev » Fri Mar 31, 2017 3:16 pm

Context switching masurements.

In my article, mentioned above, I performed some qualitative tests, demonstrating Scheduler context switching time in comparison with threads context switching, implemented in C language. The test example consisting of 100 tasks, was checked on various implementation.
Дагаев ДВ_Pic2.png
Average switching time, mcs

Pic: Average switching time, mcs.

The best results were achieved with XDS Modula-2 COROUTINES implementation. BlackBox implementation on Windows Fibers is slightly better, then the thread context switch. Linux ucontext_t implementation is slightly worse. The best way to achieve maximum performance seems to be assembly implementation to switch registers.
Dmitry Dagaev
 
Posts: 65
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Postby Dmitry Dagaev » Fri Mar 31, 2017 3:51 pm

Josef Templ wrote:The distinction between directed and undirected coroutines is not very well established in the community.

The terminology is not well established, there are a lot of various term of the same. Moreover, coroutines itself introduce GOTO-style control transfer which makes us think of a more specific constructs.
1. Anonymous coroutines (without direct calling, called by scheduler in unpredictable manner).
2. Directed coroutines - called by other routine with parameters passing.
Generators are of type 2 with additional compiler support.
Actor model is 1 type with messaging supported by system.
Flow base programming is of type 1.
Pipes are of type 2.

There are a lot of low-level solutions but not a clear vision, which syntaxic constructs must be introduced in languages.
Dmitry Dagaev
 
Posts: 65
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Postby Dmitry Dagaev » Fri Mar 31, 2017 4:28 pm

Josef Templ wrote:Removing the directed transfer at all because it can be used erroneously seems quite radical to me.
It is much like removing recursion because it can lead to stack overflow.
This is probably the reason why I couldn't get started with the Co_ package easily.

Co_ uses directed Transfer to entry type 2 coroutine and Yield as exit point.

Josef Templ wrote:Every coroutine (except main) has exactly one coroutine that started it and usually, but not necessarily,
the starting coroutine survives the started coroutine.
.
In Co_ directed coroutines the caller always survive the callee. Why? Reentrace to caller is prohibited (no Transfer as exit point). So you can only Yield from child to the caller, when the child exists.

Josef Templ wrote:Many coroutine packages don't allow a RETURN at all but require an explicit transfer at the end of the coroutine.

The Co.Stop is the explicit operator, RETURN can avoid stop, so it is prohibited.
If RETURN fits with the coroutine's need, the Yield integer value can be passed with RETURN, but for more complicated Generators support we need changing a language as above https://community.blackboxframework.org/viewtopic.php?f=54&t=164&start=10#p958

I have seen Kernel implementation and met Kernel.TransferCoroutine, Kernel.RemoveCoroutine, etc. These routines are incompatible for Co_. I approved the version, where Kernel.*Coroutine were excluded.
Dmitry Dagaev
 
Posts: 65
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Postby Josef Templ » Mon Apr 03, 2017 8:14 am

I have found a non-trivial bug in the Kernel's GC strategy.
Unterminated but unreferenced coroutines survived forever.
This is fixed in the latest build at http://blackboxframework.org/unstable/issue-%23156/blackbox-1.7.1-a1.834.zip.
I also added stack size parameters to Kernel.AddCoroutine.

- Josef
Josef Templ
 
Posts: 255
Joined: Tue Sep 17, 2013 6:50 am

Re: Co_Routines Support for Oberon

Postby Josef Templ » Mon Apr 03, 2017 8:42 am

Dmitry Dagaev wrote:
Josef Templ wrote:Removing the 'Transfer' procedure looks quite radical to me.

I succeeded to use Yield instead of Transfer as an exit point.
Removing Transfer as an Entry point is impossible without extending the language (see above).


In my latest design there is no need for using Coroutines.Transfer for the special patterns
Task and Iterator. The special patterns provide their own transfer wrappers.
I think this could also be done for other special patterns.
Coroutines.Transfer is then basically a tool for defining special patterns
and it is easy to see if any application code uses an unrestricted and potentially
dangerous Coroutines.Transfer anywhere outside the definition of special patterns.

- Josef
Josef Templ
 
Posts: 255
Joined: Tue Sep 17, 2013 6:50 am

Re: Co_Routines Support for Oberon

Postby Ivan Denisov » Mon Apr 03, 2017 6:00 pm

If I understand Dmitry correct:
- Transfer should be forbidden in not main coroutine (now this has effect of GOTO operator)
- To return control to main coroutine Yeild procedure without arguments should be used...
- we should move WinApi calls to HostCoroutines module to provide "Equal opportunities" for realizations.
User avatar
Ivan Denisov
 
Posts: 299
Joined: Tue Sep 17, 2013 12:21 am
Location: Krasnoyarsk, Russia

Re: Co_Routines Support for Oberon

Postby Dmitry Dagaev » Tue Apr 04, 2017 2:18 pm

RETURN transfers to parent? I dislike the idea, it changes semantics. Yield saves context as next entry point and transfers to parent. RETURN means next entry starts from the beginning of routine.
Dmitry Dagaev
 
Posts: 65
Joined: Wed Mar 29, 2017 3:58 pm

Re: Co_Routines Support for Oberon

Postby Josef Templ » Tue Apr 04, 2017 3:44 pm

Dmitry Dagaev wrote:RETURN transfers to parent? I dislike the idea, it changes semantics. Yield saves context as next entry point and transfers to parent. RETURN means next entry starts from the beginning of routine.


There may be a misunderstanding here.
RETURN is not a LOOP. RETURN means that the coroutine is terminated.
It cannot be transferred to after it has returned.
This is exactly what you would expect from a background task or an iterator.
It terminates when it returns. The only meaningful default transfer target for RETURN
is the parent coroutine, i.e. the coroutine that started the terminating coroutine.
If this is not what you need you have to do something else at the end.
Of course you can also put a LOOP END around a coroutine body if the application requires that.
Then it never returns. Very simple.
In addition, the current behavior allows arbitrarily nested iterators, for example.
An iterator implemented as a coroutine can use another iterator for its implementation.
Or a background task can use an iterator in its Run method.
For example, if you want to solve the SameFringe problem for a big tree it can be done in a
background task that uses the Fringe iterators.
These are perfectly meaningful use cases.

And it should be noted that the Co_ package can do something else, of course.
The Co_ package is not affected by this behavior.

- Josef
Josef Templ
 
Posts: 255
Joined: Tue Sep 17, 2013 6:50 am

PreviousNext

Return to Co_

Who is online

Users browsing this forum: No registered users and 1 guest

cron