Page 2 of 5

Re: Operating System Interest Group for XMOS devices (XOSIG)

Posted: Wed Dec 30, 2009 11:02 am
by jhrose
Hei,

[Jason: would it be possible to attach files to group emails, for people who are actually interested, instead of broadcasting on the forums - or did I miss how to do this?]

Anyway, please find attached the XOSIG Index of Ideas which aims to outline substantive ideas within XOSIG, providing a first port-of-call to locate projects and those involved with them.
XOSIG IoI.pdf
(141.1 KiB) Downloaded 798 times
XOSIG IoI.pdf
(141.1 KiB) Downloaded 798 times
IoI is issued under FDL and so any of you [meaning XOSIG members] can change it. The source is written using OpenOffice 3.1.1. However, I suggest we [XOSIG members] nominate an IoI maintainer, to make changes in a consistent way. It's not a role I desire, but will act until someone volunteers to take over... The idea is for people to contribute to the IoI, and come up with ideas in XOSIG. And someone can always pick up the uCLinux thing...to sketch out a route, and identify resource needs, etc.

Regards...

Re: Operating System Interest Group for XMOS devices (XOSIG)

Posted: Wed Dec 30, 2009 11:20 am
by jhrose
Hei,

Folknology wrote:
I did think about porting Fred Barnes RMoX http://www.cs.kent.ac.uk/research/groups/sys/rmox.html using XC/C on XMOS but even this seems a little old school in its approach and goals.
I agree it seems RMoX uses *NIX-like methods, including the way it goes about implementing services for Occam, and I wouldn't see it [the "operating system"] as an obvious port to the XS-1. However, the papers "Communicating Mobile Processes" http://www.cs.kent.ac.uk/pubs/2004/1969/content.pdf and "A CSP Model for Mobile Channels" http://www.cs.kent.ac.uk/projects/ofa/k ... pa2008.pdf, and the general-ness of Occam-pi, do contain interesting ideas even if the models are blurred somewhat.

What interests me is 1/ whether Pi is well-suited for modelling a dynamic operating system, whose very architecture changes dynamically to fulfil the state transitions of its processes. The dynamic creation of channels and processes, together with their communication through channels, enables network topology to evolve in response to run-time events. Can we capture these ideas with C libraries; not so easy with XC and the lack of pointers maybe?

And 2/ whether we can provide Operating System facilities to hide complexities of programming communicating processes, bringing a comparable benefit to the way traditional operating systems hide virtualisation of resources?

Re: Operating System Interest Group for XMOS devices (XOSIG)

Posted: Sun Jan 03, 2010 7:15 pm
by DrFingersSchaefer
Having done a bit of casting about and thinking of the memory limitations of the current xcore offerings, I can't help but think that a Forth based OS is probably going to be about the best option.

The stack orientation and block based storage together with the ability to load running code from storage would work rather well in the current hardware and memory.

It should be possible to develop code in situ on the actual target as well.

:ugeek:

Re: Operating System Interest Group for XMOS devices (XOSIG)

Posted: Mon Jan 04, 2010 11:28 am
by trousers
That's an interesting conclusion.

I would have thought that Forth and threads were uneasy bedfellows when there's no memory remapping hardware and limited RAM. One would have to arrange the stacks very carefully so that each thread has a reasonably small amount of stack space (to avoid wasting precious memory) whilst also avoiding overruns. A tricky problem ISTM.

The last time I tinkered with forth it was strictly single threaded. How do modern forths deal with concurrency?

Re: Operating System Interest Group for XMOS devices (XOSIG)

Posted: Wed Jan 06, 2010 7:49 pm
by jhrose
Hei,
a Forth based OS
I think Forth on XMOS is an interesting idea. As ANSI-standard language X3J14 you have a decent specification to work with, and numerous implementations like GNUForth should provide source code for you to explore. And of course the transputer architecture and instruction set used a stack model, though it had an external memory interface unlike the XS-1; perhaps you can form some ideas for concurrent threads/stacks. There are numerous examples of Forth OS, and I'll watch with interest to see what your new group comes up with for the XS-1.

XOSIG:
I've attached version 0.2 of XOSIG IoI.
XOSIG IoI 0_2.pdf
(129.98 KiB) Downloaded 867 times
XOSIG IoI 0_2.pdf
(129.98 KiB) Downloaded 867 times
PiXC:
And I've attached version 0.1 of PiXC. PiXC is a proposal to extend the XC programming language with mobility, using Milner's pi-calculus as a model. These ideas should lead towards a dynamic Operating System Architecture for XMOS processors.
PiXC 0_1.pdf
(172.06 KiB) Downloaded 860 times
PiXC 0_1.pdf
(172.06 KiB) Downloaded 860 times
Thanks for any feedback on these ideas, here or in XOSIG http://www.xcore.com/groups/xmos-operat ... roup-xosig

Re: Operating System Interest Group for XMOS devices (XOSIG)

Posted: Fri Jan 08, 2010 2:17 am
by DrFingersSchaefer
Forth has the wonderful property of being savagely ram efficient.

Because of the threaded code properties it isn't bad with rom either.

Admittedly FLASH is much better then ROM these days.

So if ram is in short supply Forth will do what other languages and OS's fail to do.

Granted it is possible to use the exceptions generated by out of range memory accesses (plus side on the Xcore) to try and patch in paging of RAM exchange with external memory. The port interfaces on the Xcores are even configurable as Ram U Like interfaces (SRAM, DRAM take your pick)

The problem actually isn't when you ask for RAM beyond the + range of internal ram (as this generates an exception you can trap for in your code), it is when you ask for ram that is an undershoot of the area you have put aside for paging. This doesn't generate an exception you can trap for. (I would rather like to be proved wrong on this one as I want a Transputer replacement)

In forth you can use the Block commands and structure to load in extra instructions and threaded code. whilst using the (arguably discontinued but useful in this context) forget instructions to purge areas of threaded code you no longer need for the application in hand.

Hope this explains some fo the rational.

:ugeek:

Re: Operating System Interest Group for XMOS devices (XOSIG)

Posted: Sat Jan 09, 2010 11:33 pm
by Folknology
Julian I really, really like what you have done with the PiXC idea, the documentation you have produced is great work. I am on my second read through and will likely read it through several more time yet but would like to make a few comments

1) You mention the mobile prefix of providing 'Class-Like' structure i.e. function and encapsulated data, I can see where you coming from but would be hesitant to imply class like analogies. I strongly believe in externalising state where possible instead of encapsulating it. Also names spaces describe your suggested access to static variables 'Mob::var'. I would also be worried about access to variables outside of their mobile function which is where this names-spacing would be required. It is dangerous in threaded and multi process environment to let this happen, channels should be the only method for data sharing by different threads. Perhaps I am also getting the wrong end of the stick on where your taking this, please correct me if I'm wrong here.

2) On the roaming pattern you show the following :

Code: Select all

void roam0( chanend c, chanend ) 
{ 
  int t = 1; // initially assume task 1 
  c :> p1; // wait to receive mobile process p1 
  for( ; t > 0; ) 
  { 
  // calculate next task, t, on p1 state 
    switch( t ) 
    { 
     case 1: 
       { 
       // perform task t1, interacting with p1 
      } 
      break; 
      ... 
      default : 
      { 
        // not a task for roam0 in this context 
        c <: p1; // give mobile process p1 to new context 
        t = 0; // exit loop 
       }
    } 
  } 
} 
Should this be

Code: Select all

void roam0( chanend c, chanend d) 
{ 
  int t = 1; // initially assume task 1 
  c :> p1; // wait to receive mobile process p1 
  for( ; t > 0; ) 
  { 
  // calculate next task, t, on p1 state 
    switch( t ) 
    { 
     case 1: 
       { 
       // perform task t1, interacting with p1 
      } 
      break; 
      ... 
      default : 
      { 
        // not a task for roam0 in this context 
        d <: p1; // give mobile process p1 to new context 
        t = 0; // exit loop 
       }
    } 
  } 
} 
3) I like the 3 different patterns that you enumerate, but each could do with a practical example perhaps using I/O to illustrate appropriate usage in action. It would help reinforce the benefit offered using the mobile construct.

4) The patterns that you show appear to be sequential in nature (I could be misunderstanding),I would like to see how a number of concurrent processing patterns would fit in.

regards
Al

Re: Operating System Interest Group for XMOS devices (XOSIG)

Posted: Mon Jan 11, 2010 4:39 pm
by jhrose
Hei,
Thanks for the feedback once more.
1/ function and encapsulated data
I do not intend to draw heavily on the 'class-like' analogy, but aim to paint the picture of data and function encapsulation, constructors and destructors. I'll try to clarify my intent and issues of encapsulation for mobile processes.
1.1/ Intent.
1.1.a/ Firstly a class-like structure, like Mob::var, is not a syntax the programmer would write; I will re-colour-code such references to signify this more clearly. It intends to draw attention to semantics the compiler needs to apply to mobile processes.
1.1.b/ Secondly PiXC extends XC, and not C or C++. Neither classes nor namespaces are supported in XC. (And there is no Occam-like 'PROC' declaration, which could otherwise be developed.)
1.1.c/ Thirdly PiXC should impose the minimal set of changes on XC, that do what is needed. Section A.3 of Programming XC, names and storage, helps to estimate the likely cost of extensions. (However, we ought to debate conveniences that go a bit further than the barest need, such as namespaces, to test their usefulness or expressiveness, but I wouldn't want to end up with a complete language/compiler re-write.)

Your suggestion to use namespaces instead of a class-like analogy would seem to achieve a similar end, but implementing either namespaces or classes more fully increases what the XC compiler would have to do anew, when I intend to implement neither. Namespaces provide a context for symbols, and group related functions and data spread over several source files or libraries. I don't think the XC compiler maintains seperate contexts or searches multiple source files extensively.

To avoid different interpretations, perhaps we'd best avoid borrowing class or namespace terms at all and instead refer to mobile contexts. But whatever the form (internal to the compiler), issues remain that mobile process encapsulation resolves.

1.2/ Issues.
Encapsulation is needed for the XC compiler to allocate storage space for mobile processes, which are i/ long-lived, and ii/ can migrate. Encapsulation solves several implementation issues, including memory map, liveness, coherency and scalability, amongst others.
1.2.a/ Memory Maps (per processor).
The PiXC compiler should generate code for (mobile) processes exactly once. During compilation global variables (or memory allocated to hold them) are fixed offset from dp (register 13). If external variables were used for mobile member variables, then either:
1.2.ai/ the memory maps of different processors would have to be made the same, in order for the common mobile process object code to access member variables, which is wasteful, or
1.2.aii/ the object code would need to be compiled seperately for each processor,in order to access member variables in the different memory maps, which is also wasteful.
1.2.a.iii/ By using encapsulation, the compiler could offset process member variables with respect to another register, say r11, per thread. Or the compiler could treat member variables like far pointers, and go through a jump table. Or another method could be used.

(Also for the memory-map reason, I don't think mobiles would access other global variables, and channels should be preferred for data exchange. However, XC allows global variable access, so I'm moot.)

1.2.b/ Liveness. A mobile process comes into being (is constructed, or initialised, or run) when it is received by a process. Similarly it deceases (is destructed, or terminated) when it is sent by a process. So if external (non-static) data were used, each variable would need a 'lifetime' guard, which would need testing on each and every access by a non-mobile process.

1.2.c/ Coherency (touched on in 2.2.1.3.4).
1.2.ci/ When a process migrates from a source to a destination processor, its destination data members need to store the values already calculated in the source processor. But if external (non-static) data were used, overwriting them would appear as a corruption to other processes running on the destination processor.
1.2.cii/ And running on the new destination processor, changes written by the mobile process to global data would not be visible to other processes running on the original source processor.
1.2.ciii/ The Hoare/Dijkstra multiple-update problem requires a guard on shared global data; accessing a global from parallel processes is guarded in XC at compile time, so only one process is permitted to write to a global. This places restrictions I don't want to impose on mobile member variables.

1.2.d/ Scalability. If in the future mobility is extended to heterogenous networks then we wouldn't want to change/break existing programs or language features. And encapsulation solves mobility problems in a general way, which I expect will scale up to heterogenous processor networks.
2/ On the roaming pattern
Thanks for the bug fix. It should read

Code: Select all

void roam0( chanend c )
{
  int t = 1; // initially assume task 1
  c :> p1; // wait to receive mobile process p1
  for( ; t > 0; )
  {
      // calculate next task, t, on p1 state
    switch( t )
    {
      case 1:
      {
        // perform task t1, interacting with p1
      }
      break;
      ...
      default :
      {
          // not a task for roam0 in this context
        c <: p1; // migrate mobile process p1
        t = 0; // exit loop
      }
    }
  }
}
I prefer just the one chanend as channels are not the focus of this pattern. But you could use 2 channels as you suggested.
3/ ..a practical example perhaps using I/O
The examples do remain simple, to communicate concepts while the ideas are still very new. Also it's hard to program in PiXC without a compiler to correct me ;)

With regard to IO (ports) and mobile processes in general, there isn't a concept of a mobile port like there is a mobile channel, as a port is a fixed hardware pin. Rather, I envisage an Operating System selecting on port cases and using mobile processes to service inputs. By way of example, using traditional OS, I often write 'input ready' code in which a device driver handles some input and passes data (pointers) to several application threads. In my vision for a dynamic operating system, a mobile process can be passed between the application threads, instead of using a semaphore.

I will try to think about more detailed examples, while avoiding obfuscation.
4/ concurrent processing patterns
I wouldn't call it a design pattern, but

Code: Select all

select
  case c :> void:
    PAR
    {
      proca( );
      procb( );
    }
is similar to receiving a mobile process procb,

Code: Select all

void proca( chanend c )
{
  c :> procb;
    // rest of proca
  c <: procb;
}
in which proca and procb run concurrently.

Please respond if I've got something wrong or it remains unclear, or any other comments.

Re: Operating System Interest Group for XMOS devices (XOSIG)

Posted: Tue Jan 19, 2010 8:07 pm
by jhrose
Hei,

Please find attached version 0.2 of PiXC.
PiXC 0_2.pdf
(255.37 KiB) Downloaded 837 times
PiXC 0_2.pdf
(255.37 KiB) Downloaded 837 times
3) ...a practical example...
Following the suggestion of Folknology there is a new case study section in version 0.2. This includes an ethernet program that extends chapter 6.5 of the Programming XC book. And for convenience I've attached 3 versions of the XC source code for people to try out in the XMOS IDE: the basic (with a small main program), one with mobile processes, and one with mobile channels. Of course the PiXC versions don't compile, but the compiler errors highlight the extensions usefully (though admittedly not so clearly for the mobile channel version).
ethernet_case_study.zip
(10.88 KiB) Downloaded 770 times
ethernet_case_study.zip
(10.88 KiB) Downloaded 770 times
Of course as I don't have a PiXC compiler there may be mistakes in the code, so please let me know if you think to find any.

Other new inclusions in PiXC version 0.2 is a notation for initially binding mobile channel endpoints and mobile processes, and for selecting which endpoint (0,1) to bind. And please continue to give feedback on these ideas.

Thanks

Re: Operating System Interest Group for XMOS devices (XOSIG)

Posted: Tue Jan 19, 2010 9:33 pm
by Folknology
Julian I'm having trouble opening the PDF can you (or anyone else here) double check the uploaded version 0.2.