読者です 読者をやめる 読者になる 読者になる

bitterharvest’s diary

A Bitter Harvestは小説の題名。作者は豪州のPeter Yeldham。苦闘の末に勝ちえた偏見からの解放は命との引換になったという悲しい物語

XMOS (イベント駆動・並列スレッド)プログラミング(2)

1.ベンディングマシンを実現する

1.1 仕様

次の状態遷移図(Moore Machine)で表わされるベンディングマシンがあったとする。これを実現することを考える。
f:id:bitterharvest:20140721111217j:plain

このベンディングマシンでは、5円と10円が使えることになっている。投入金額が20円以上になるとベンディングマシンの中心で、イルミネーションが円を描いてぐるぐる回るようになっている。XMOSのXC-5を用いてベンディングマシンのシミュレーションをすることにする。

5円と10円の投入は、それぞれボタンAとBを押すものとする。また、合計金額が0,5,10,15のときは、ボタンのところにあるLEDのA,B,C,Dがそれぞれ点滅するものとする。また、20円以上になったときは、クロックとしてのLEDが点滅しながら時計回りに回転するものとする。また、20円以上になったときはいくら投入しても同じであるとする。

1.2 プログラム作成のためのヒント

イベントは、ボタンA,Bが押し下げられた時とする。これは、select, caseにより実装する。

同様にLEDを点滅回転させる作業も、一定時間ごとの時間の経過でイベントを発生させ、LEDを点滅回転できるようにするが、case文の中で、20円以上の状態以外では、点滅回転の部分を抑制する。

1.3 課題1

プログラムを完成しなさい。

1.4 課題2

この状態遷移図は、一度、20円以上になると初期状態に戻ることはない。そこで、ボタンCを押し下げれば、初期状態に戻れるようにしたい。状態遷移図を修正し、また、プログラムも作成しなさい。

2.ベンディングマシンの利用者まで考えると

2.1 仕様

ベンディングマシンの利用者まで考えると、並列処理となる。下図に示すように、人とベンディングマシンは通信路を介してやり取りしていると考える。
f:id:bitterharvest:20140721111243j:plain
人からベンディングマシンへの5円、10円の投入は、通信路を介して0,1を送っているものとする。また、ベンディングマシンからは、不足なのか充分なのかが、やはり、通信路を介して戻ってくるものとする。

このような仕様に対しては、parを用いて人とベンディングマシンをスレッドとしてプログラムを組むことができる。

2.2 課題

プログラムを作成し、その動作を確認しなさい。

3.CSP(Communicating Sequential Processes)

3.1 仕様

ここまで進めると、CSPを知っている人は、XMOSを用いれば、この手の問題を解決できるのではないかと想像するであろう。

次の問題は、CSPで記述するときれいに書くことができる。Xが上下左右に動けるとき、そのプロセスをCSPで示しなさい。

o o o
o x o

CSPでの解は以下の様になる。

αP={up, down}
P=(up->down->P)
αQ={left, right}
Q=(right->left->Q|left->right->Q)

そこで、CSPをXMOSで表すためには、CSPのプロセスをXMOSのスレッドで、またCSPでの選択|をXMOSのselect文で、CSPでのアルファベットをXMOSでのイベントとすればよいので、プログラムは次のようになる。

3.2 プログラムの概要

プログラムの概要を示す。up,down,left,rightはボタンA,B,C,Dをそれぞれ割り当て、押し下げられたとき、移動の指示があるものとする。また、ます目はクロックのLEDを用いて、

XII,I,II

VI, V, IV

で表すことにする。

in port b = PORT_BUTTON;
int main() {
 chan b1, b2, c1, c2;
 par {
  buttonListener(b, b1, b2);
  vmove(b1, c1);
  hmove(b2, c2);
  pos(c1, c2);
 }
 return 0;
}
#define PUSH_PERIOD 100000000
int buttonListener(in port b, chanend b1, chanend b2) {
 char key;
 timer tmr;
 unsigned time;
 while (1) {
  b when pinsneq(0xf) :> key; // キーのイベントが生じた。
  switch (key) {
   case 0xe: // up (Aのキーが押された)
    b1 <: 0;
    break;
   case 0xd: // down (Bのキーが押された)
    b1 <: 1;
    break;
   case 0xb: // left (Cのキーが押された)
    b2 <: 0;
    break;
   case 0x7: // right (Dのキーが押された)
    b2 <: 1;
    break;
  }
tmr :> time;
time += PUSH_PERIOD;
tmr when timerafter(time) :> void ; // ボタンが押されたかどうかの確認は、少し時間をおいてから。そうでないと、1回押している間に何回もイベントが発生してしまう。
 }
 return 0;
}
int vmove(chanend b1, chanend c1) {
 int cmd;
 int p = 0; // p0 = up -> down -> p0, p1 = down -> p0
 while (1) {
  b1 :> cmd;
  switch (p) {
   case 0: // p0 = up -> down -> p0
    if(cmd == 0) { // upのイベントが生じた
     c1 <: 0;
     p = 1;
    }
    break;
   case 1: // p1 = down -> p0
    if(cmd == 1) {// downのイベントが生じた
     c1 <: 1;
     p = 0;
    }
    break;
  }
 }
 return 0;
}
int hmove(chanend b2, chanend c2) {
 int cmd;
 int q = 0; // q0 = {right->left->q0|left->right->q0}, q1 = left->q0, q-1= right->q0
 while (1) {
  b2 :> cmd;
  switch(q) {
   case 0: // q0 = {right->left->q0|left->right->q0}
    if(cmd == 0) { // leftのイベントが生じた
     c2 <: 0;
     q = -1;
    }
    else if(cmd == 1) { // rightのイベントが生じた
     c2 <: 1;
     q = 1;
    }
    break;
   case -1: // q-1 = right->q0
    if(cmd == 1) { // rightのイベントが生じた
     c2 <: 1;
     q = 0;
    }
    break;
   case 1: // q1 = left->q0
    if(cmd == 0) { // leftのイベントが生じた
     c2 <: 0;
     q = 0;
    }
    break;
  }
 }
 return 0;
}
int pos(chanend c1, chanend c2) {
 int hm, vm;
 while(1) {
  select {
   case c1 :> hm : //c1のイベントが発生
    if(hm == 0) {//直上に移動
    }
    else if(hm == 1) {//直下に移動
    }
    break;
   case c2 :> vm : //c2のイベントが発生
    if(vm == 0) {//左隣に移動
    }
    else if(vm == 1) {//右隣に移動
    }
    break;
  }
 }
 return 0;
}

3.3 課題

プログラムを完成し、動作させなさい。

3.4 課題

CSPの仕様を状態遷移図で表しなさい。

3.5 課題

上記と同じ機能を実現する別のプログラムを作成しなさい。さらに、CSPに基づいて記述したプログラムとの違いを述べなさい。

3.6 課題

有名な問題に哲人の食事がある。これは円卓を囲んで5人の哲人が食事をとる。ただし、哲人の左右にはフォークが一本づつあり、これは両隣の人と共有している。左右のフォークを両方とも取ることができれば、円卓の真ん中に置かれているスパゲティーを食べることができるが、フォークの一方、あるいは、両方ともが隣人により使われているときはそれを待つことになる。XC-5ではスレッドが8つまでしかないので、この問題を実装することができないが、哲人を3人に減らせば可能になる。プログラムを書いて、誰もが食事をできないデッドロック状態に陥ることを示しなさい。

4.論理回路シミュレータ

4.1 仕様

CSPのような高尚な話をした後で、現実の問題に戻すようで恐縮だが、大学に入学してすぐに学んだ論理回路のシミュレーションはXMOSではどのように実現できるだろうか?例えば、D=A(B+C)はどのように実現できるか。ここで、A,B,Cはボタンとし、DはボタンDの近くにあるLEDする。

4.2 プログラム

余り難しいプログラムではないので、プログラムを作成し、動作を確認しなさい。

5.順序回路シミュレータ

5.1 仕様

組合せ回路の次に学んだのが順序回路である。これはフリップフロップをつなぎ合わせて作った。フリップフロップの動作はスレッドで表すことが可能である。また、複数フリップフロップで実現される回路は、スレッド同士の通信で実現することが可能になる。

順序回路を実現するときによく使われるフリップフロップはD型フリップフロップである。これは次のように動作する。

CLK D  R S  Q Q'
クロック(立ち上がり) 1  1 1  1 0
クロック(立ち上がり) 0  1 1 0 1
0 1  0 1
1 0  1 0

   

この動作を、スレッドを用いて示しなさい。

5.2 課題1

複数のD型フリップフロップで実現される順序回路を示し、これをXMOS上で実現しなさい。

5.3 課題2

D型フリップフロップは、その出力Q’をDに接続すると、クロックに入れた信号の周期を半分にした信号をQから得ることができる。これを示しなさい。

5.4 課題3

上記のように接続したD型フリップフロップを二つ用意し、前段のD型フリップフロップのQを後段のフリップフロップのクロックに接続すると、後段のQの出力は、前段のクロックの1/4の周期となっている。これは、四つのクロックで後段のQが繰り返すこととなるので、4進カウンターとも呼ばれる。これを示しなさい。

5.5 課題4

3つのD型フリップフロップを上記のようにつなげると8進カウンターが得られるが、5個のクロックを得た時に、全てのフリップフロップをリセットすると5進カウンターが得られる。これを示しなさい。