Page 3 of 10

Re: Co_Routines Support for Oberon

Posted: Fri Mar 31, 2017 12:35 pm
by Dmitry Dagaev
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

Re: Co_Routines Support for Oberon

Posted: Fri Mar 31, 2017 1:06 pm
by Dmitry Dagaev
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).

Re: Co_Routines Support for Oberon

Posted: Fri Mar 31, 2017 3:16 pm
by Dmitry Dagaev
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.
Average switching time, mcs
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.

Re: Co_Routines Support for Oberon

Posted: Fri Mar 31, 2017 3:51 pm
by Dmitry Dagaev
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.

Re: Co_Routines Support for Oberon

Posted: Fri Mar 31, 2017 4:28 pm
by Dmitry Dagaev
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 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.

Re: Co_Routines Support for Oberon

Posted: Mon Apr 03, 2017 8:14 am
by Josef Templ
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/i ... a1.834.zip.
I also added stack size parameters to Kernel.AddCoroutine.

- Josef

Re: Co_Routines Support for Oberon

Posted: Mon Apr 03, 2017 8:42 am
by Josef Templ
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

Re: Co_Routines Support for Oberon

Posted: Mon Apr 03, 2017 6:00 pm
by Ivan Denisov
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.

Re: Co_Routines Support for Oberon

Posted: Tue Apr 04, 2017 2:18 pm
by Dmitry Dagaev
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.

Re: Co_Routines Support for Oberon

Posted: Tue Apr 04, 2017 3:44 pm
by Josef Templ
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