ビルトインパッケージ　(Std　Package)

概要

SystemVerilogには、組み込み済のライブラリパッケージがあります。この中では、以下の部品が定義されています。

メールボックス
セマフォ
プロセス
ランダム制御

上の3つは、クラスが定義されていて、その実装は、シミュレーションベンダによります。

プロセス　クラス(Fine Grain Process Control)
よく使われるのは、メールボックスだと思いますが、その実装では、セマフォが使われ、セマフォの実装には、プロセスを使っています。つまりプロセス　クラスというのは、Lowレベルなクラスになります。実際、このクラスは特殊なクラスで、newでインスタンス化することはできませんし、クラスを継承することもできません。プロセス　クラスと名前はついていますが、その実体は、シミュレータのスレッドをクラスでラップしたものです。VerilogHDLでは今まで、ユーザに生のスレッドを制御させる手段を提供してきませんでしたが、これは生のスレッドに対する制御になります。disable、wait fork、disable forkといった類では、制御しずらい場面で威力を発揮します。そういう意味で、細粒度のコントロールが可能、fine grain process control、になっています。

いずれにしても、かなり精通した人向けの上級機能だと思います。

01class process;
02    typedef enum { FINISHED, RUNNING, WAITING, SUSPENDED, KILLED } state;
03    extern local function new();    // illegal to call
04    extern static function process self();
05    extern function state status();
06    extern function void kill();
07    extern task await();
08    extern function void suspend();
09    extern function void resume();
10endclass

プロセスクラスのenumは、スレッドの状態を指します。

	状態
FINISHED	スレッドが正常終了した
RUNNING	現在、スレッドが走行中、（ブロックされていない。）
WAITING	実行待ちにある。#delayや、@(expression) ,wait等による実行待ち
SUSPENDED	resume待ち
KILLED	kill コマンドまたは、disableコマンドによりスレッドが消去された

この状態は、status()で取得することができます。プロセスクラスは、スレッドをラップしたものですが、どのようにスレッドにアクセスすればよいのでしょうか？

そのための関数が、self()で次のように使います。

01program process_test;
02 
03        std::process p1;//std::は、なしで可
04         
05        task automatic t1;
06                        p1=process::self();//現在走行中のスレッドの取得
07                        $display("%p %d",p1.status(),$time);//%pでenum表示される
08                        #100;
09                        $display("---Finished t1 task.");
10        endtask
11        initial begin
12                         
13                         
14                        fork //二つのスレッドを平行起動して
15                                #20 $display("%p %d",p1.status(),$time);//途中で、スレッドの状態を見る
16                                t1();
17                        join
18                        $display("%p %d",p1.status(),$time);//終了後にスレッドの状態を見る
19        end
20 
21endprogram

実行結果です。

1***** Veritak SV32 Engine Version 446 Build May 28 2013*****
2 
3RUNNING                    0
4WAITING                   20
5---Finished t1 task.
6FINISHED                  100
7 
8---------- シミュレーションを終了します。time=100ns

つまり、スレッドを走行させて初めて取得できる、という訳です。通常の実装では、スレッドは、initialやalways,task コール　fork- joinで実行時に生成されます。
ですから、スレッドの存在しない系( constant functionや継続的代入文）では、使用することができません。

サスペンドとリジューム
サスペンドは、一時休止状態です。resumeコマンドでのみ再開することができるので、resumeコマンドを待っている状態とも言えます。
サスペンドは、クラスハンドルを介し、自分自身でサスペンドすることが出来ますが、一旦サスペンドしてしまうと、自分自身で再開することはできません。誰かにresumeしてもらうしかありません。

01program process_test;
02 
03    std::process p1;
04     
05    task automatic t1;
06            p1=process::self();
07            $display("%p %d",p1.status(),$time);
08            p1.suspend();//自分自身をサスペンド
09            $display("%p %d",p1.status(),$time);
10            #100;
11            $display("---Finished t1 task. %d",$time);
12    endtask
13    initial begin
14             
15             
16            fork
17                #20 $display("%p %d",p1.status(),$time);
18                #40 p1.resume();//レジュームする   
19                t1();
20            join
21            $display("%p %d",p1.status(),$time);
22    end
23 
24endprogram

実行結果です。

1***** Veritak SV32 Engine Version 446 Build May 28 2013*****
2 
3RUNNING                    0
4SUSPENDED                   20
5RUNNING                   40
6---Finished t1 task.                  140
7FINISHED                  140
8 
9---------- シミュレーションを終了します。time=140ns

resumeで、次の行から実行が再開されます。suspend状態にある間は、delayや、wait, eventによる再開はありません。たとえば、delay中にsuspendされて、delay時間経って再開することはありません。delay時間前に、resumeされた場合は、delay後にスレッドが再開しますが、delay時間経過後にresumeされた場合は、resumeされた時点で、現在時刻（Activeまたは、ReActve　Region)に再スケジュールされます。

suspendは、自分自身をsuspendするときブロッキングします。それ以外はブロッキングしません。

kill

kilは、スレッドの強制終了です。強制終了したスレッドでは、waitや、delayも強制終了となります。また、起動したサブスレッドも強制終了となります。ここまでの動作は、disableと同じです。違う点は、killは、単体スレッドについて作用するのに対して、disableは、同じラベルの兄弟スレッドについても作用します。兄弟スレッドが存在しないときは、動作は同じです。
なお、自分で自分をkillすることが可能なのは、disableに同じです。

await
指定したスレッドの終了を待ちます。これは、ブロッキング命令で、指定したスレッドが終了するまで、制御は戻ってきません。ブロッキングします。また、自分自身をawaitすることはできません。

killとawaitの例

5つのスレッドを起動し、3番目に起動したスレッドの終了を待ちます。その後、未だ実行中のスレッドは、killで強制終了させます。

01program  pr24;
02    parameter int N=5;
03 
04    task do_N_jobs( );
05 
06        process job[1:N];
07        foreach( job[j]) 
08            fork
09                automatic int k = j;
10                begin
11                    job[k] = process::self();
12                    #(k);
13                    $display("k=%d time=%d",k,$time);
14                end
15            join_none
16        foreach( job[j]) begin // wait for all processes to start
17            wait( job[j] != null );
18            $display("Job[%1d]=%p started time:%d",j, job[j].status(),$time);   
19        end
20 
21        job[2].await();//wait job[2] is finishedl
22        $display("Job[2] has finished!\n");
23     
24     
25        foreach( job[k])        $display("job[%1d]=%p",k, job[k].status());
26        $display("\n");     
27 
28        foreach (job[k]) 
29            if ( job[k].status() != process::FINISHED ) begin
30                $display("Killing the job[%1d]",k);
31                job[k].kill();
32            end
33        $display("\n");
34 
35        foreach( job[k])        $display("job[%1d]=%p",k, job[k].status());
36 
37 
38    endtask
39 
40    initial begin
41        do_N_jobs();
42        $display("Finished!");
43    end
44 
45 
46 
47endprogram

01***** Veritak SV32 Engine Version 447 Build Jun  7 2013*****
02 
03Job[1]=WAITING started time:                   0
04Job[2]=WAITING started time:                   0
05Job[3]=WAITING started time:                   0
06Job[4]=WAITING started time:                   0
07Job[5]=WAITING started time:                   0
08k=          1 time=                   1
09k=          2 time=                   2
10Job[2] has finished!
11 
12job[1]=FINISHED
13job[2]=FINISHED
14job[3]=WAITING
15job[4]=WAITING
16job[5]=WAITING
17 
18 
19Killing the job[3]
20Killing the job[4]
21Killing the job[5]
22 
23 
24job[1]=FINISHED
25job[2]=FINISHED
26job[3]=KILLED
27job[4]=KILLED
28job[5]=KILLED
29Finished!
30 
31---------- シミュレーションを終了します。time=5ns

セマフォの実装

プロセスクラスを使って、セマフォの実装を行ってみましょう。

-セマフォは、std::パッケージにビルトインしているので、あえて作る必要はないのですが、VeritakSVの内部実装ということで見ていただければよいかと思います。

ここでは、my_semaphore　というクラスを作ることにします。

セマフォクラスは、次のような定義です。

1class semaphore;
2　function new(int keyCount = 0);
3　function void put(int keyCount = 1);
4　task get(int keyCount = 1);
5　function int try_get(int keyCount = 1);
6endclass

ここで、getがtaskであり、それ以外は、functionで実装されていることが分かります。つまり、putとgetでは、時間を消費しない、ブロッキングされない実装にしなくてはいけないということが分かります。一方taskであるgetは、keyを取得できなかったときは、取得できるまで待つことになります。さて、取得できるまで待つ、取得できたら再開というのは、どう書けばよいでしょうか？そんなときは、プロセスクラスの出番です。suspend()で待って、他のスレッドでresumeをしてやればよさそうです。getというのは、内部カウンタkeyが減ることを意味し、反対にputは、内部カウンタkeyが増えることになる唯一のメソッドです。ですから、putの実装でresume()してやればよいということになります。

01class my_semaphore;
02        typedef struct {
03                std::process p1;
04                int req_key_count;
05        }key_count_process;
06 
07        local key_count_process queue[$];
08        local int Count;
09 
10        function new(int keyCount);
11                this.Count = keyCount;
12         
13        endfunction
14 
15        function void put(int keyCount );
16         
17                this.Count +=keyCount;
18         
19                while (queue.size()) begin
20                        if (this.Count >=queue[0].req_key_count) begin
21                                key_count_process K;
22                                K= queue.pop_front();
23                                Count -=K.req_key_count;
24                                K.p1.resume();
25                        end else break;
26                end
27        endfunction
28 
29        task get(int keyCount );
30                if (this.Count>=keyCount) this.Count -=keyCount;
31                else begin
32                 
33                        key_count_process kp;
34                        kp.req_key_count=keyCount;
35                        kp.p1=process::self();
36         
37                        queue.push_back(kp);
38                        kp.p1.suspend();
39                end
40 
41        endtask
42        function int try_get(int keyCount );
43                        if (this.Count>=keyCount) return 1;
44                        else return 0;
45        endfunction
46endclass

メンバは、keyの個数をカウントするCountと、取得できなかったスレッドと要求数を待ち行列とするキューです。getで要求keyを取得できなかった場合には、それをUnboundedキューに貯めておきます。スレッドは、無制限に生成されることが考えられるのでこのような処理にしています。一方putでは、key数を増やしますが、その際に貯まっているキューで処理可能なものは、順番にresumeして行きます。

複数のキーを持つセマフォの問題

キーが1個の場合の動作は、mutexと動作は同じになります。複数のキーを持つ場合には、注意することがあります。

このセマフォでプログラムを次のように書きました。３つのスレッドがありますが、この実行順は分かりますでしょうか？

01program semaphore_example ;
02 
03 my_semaphore sm =new(0);
04 initial
05        fork
06                begin:Thread1
07                        sm.put(2);
08                        sm.get(4);//2個しか残っていないので取得できず、suspend
09                        $display("Thread1, completed at time %d",$time);        
10                end
11                begin:Thread2
12                        #10;
13                        sm.get(2);//取得できる。FIFO動作とならず、Thread１を追い越してしまう
14                        $display("Thread2, completed at time %d",$time);//終了
15                end
16                begin:Thread3
17                        #20;
18                        sm.put(4);//4個のキーを与えるのでThread1をresumeする
19                        $display("Thread3, completed at time %d",$time);
20                end
21        join
22 
23endprogram

実行結果は次です。

1***** Veritak SV32 Engine Version 446 Build May 28 2013*****
2 
3Thread2, completed at time                   10
4Thread3, completed at time                   20
5Thread1, completed at time                   20
6 
7---------- シミュレーションを終了します。time=20ns

DelayがないThread1から実行されます。4個のキーを取得しようとしますが、2個しか残っていないので、取得できずsuspendされます。次にThread1が実行されます。2個のキーを取得できsuspendされずに実行継続になります。結果的にThread1の実行よりも早く終了してしまいます。Thread3で4個のキーを追加していますが、このとき、Thread1をresumeしています。
Thread3の終了後にThread1が実行されます。

このように複数のキーを持つ場合は、必ずしもgetの実行順に実行される（FIFO動作）とは限らないことに注意してください。この動作は、my_semaphoreに限らず、std::semaphoreでも同じです。(LRMで、この動作の規定はないのですが他のシミュレータでも同じ結果となります。)

FIFO動作させたい場合には、getを常にget(1)で取得するとよいでしょう。

01program semaphore_example ;
02 
03 my_semaphore sm =new(0);
04 initial
05    fork
06        begin:Thread1
07            sm.put(2);
08            repeat(4) sm.get(1);//一個づつ取得すれば、FIFO動作になる
09            $display("Thread1, completed at time %d",$time);    
10        end
11        begin:Thread2
12            #10;
13            repeat(2) sm.get(1);//一個づつ取得すれば、FIFO動作になる
14            $display("Thread2, completed at time %d",$time);
15        end
16        begin:Thread3
17            #20;
18            sm.put(4);
19            $display("Thread3, completed at time %d",$time);
20        end
21    join
22 
23endprogram

あるいは、my_semaphoreを継承し、getを次のように書き換えます。(キューにデータがある場合には、常にキューイングするようにしてしまいます。)

01virtual task get(int keyCount );
02 
03                if (queue.size() || this.Count< keyCount) begin
04                        key_count_process kp;
05                        kp.req_key_count=keyCount;
06                        kp.p1=process::self();
07         
08                        queue.push_back(kp);
09                        kp.p1.suspend();
10                end else this.Count -=keyCount;
11        endtask

全体のソースです。

01class my_semaphore;
02        typedef struct {
03                std::process p1;
04                int req_key_count;
05        }key_count_process;
06 
07 
08        protected key_count_process queue[$];
09        protected int Count;
10 
11        function new(int keyCount);
12                this.Count = keyCount;
13         
14        endfunction
15 
16        function void put(int keyCount );
17         
18                this.Count +=keyCount;
19         
20                while (queue.size()) begin
21                        if (this.Count >=queue[0].req_key_count) begin
22                                key_count_process K;
23                                K= queue.pop_front();
24                                Count -=K.req_key_count;
25                                K.p1.resume();
26                        end else break;
27                end
28        endfunction
29 
30        virtual task get(int keyCount );
31                if (this.Count>=keyCount) this.Count -=keyCount;
32                else begin
33                 
34                        key_count_process kp;
35                        kp.req_key_count=keyCount;
36                        kp.p1=process::self();
37         
38                        queue.push_back(kp);
39                        kp.p1.suspend();
40                end
41        endtask
42 
43         
44 
45        function int try_get(int keyCount );
46                        if (this.Count>=keyCount) return 1;
47                        else return 0;
48        endfunction
49endclass
50 
51class my_semaphore_blocked extends my_semaphore;
52 
53        function new(int keyCount);
54                super.new (keyCount);
55         
56        endfunction
57        virtual task get(int keyCount );
58 
59                if (queue.size() || this.Count< keyCount) begin
60                        key_count_process kp;
61                        kp.req_key_count=keyCount;
62                        kp.p1=process::self();
63         
64                        queue.push_back(kp);
65                        kp.p1.suspend();
66                end else this.Count -=keyCount;
67        endtask
68endclass
69 
70program semaphore_example ;
71 
72 my_semaphore_blocked sm =new(0);
73 initial
74        fork
75                begin:Thread1
76                        sm.put(2);
77                        sm.get(4);
78                        $display("Thread1, completed at time %d",$time);        
79                end
80                begin:Thread2
81                        #10;
82                        sm.get(2);
83                        $display("Thread2, completed at time %d",$time);
84                end
85                begin:Thread3
86                        #20;
87                        sm.put(4);
88                        $display("Thread3, completed at time %d",$time);
89                end
90        join
91 
92endprogram

実行結果です。

1***** Veritak SV32 Engine Version 446 Build May 28 2013*****
2 
3Thread3, completed at time                   20
4Thread1, completed at time                   20
5Thread2, completed at time                   20
6 
7---------- シミュレーションを終了します。time=20ns

生産者と消費者問題

セマフォを参考にして、コーディングしてみましょう。Wekipediaの例のように二つのセマフォを使うとうまく行きますが、シミュレータをまともに走らせるには意外に難しいです。うまく走ると無限ループになります。デバッグ用に、イベントが枯渇すると、3番目のスレッドが効いて$stopするようにしています。ブロックするステートメント(この場合は、semaphoreのget)がどれかを意識して書かないとうまく走ってくれません。（イベントが枯渇して$stopしたりします。）

01program pr7;
02    parameter  int N=1;
03    parameter int M=N;
04    parameter int K=M;
05    my_semaphore Spaces=new(N);
06    my_semaphore Elements=new(0);
07    int value=0;    
08    int q[$];
09 
10 
11task producer;
12 
13    forever begin
14 
15     
16        repeat(M) begin
17            Spaces.get(1);
18            q.push_back(value++);
19            $display("Produced %d q.size()=%d %d",value,q.size(),$time);
20        end
21        Elements.put(M);
22 
23     
24    end
25endtask
26 
27task consumer;
28    forever begin
29        int i;
30         
31        repeat (K) begin
32            Elements.get(1);
33            i=q.pop_front();
34            $display(" Consumed %d q.size()=%d %d",i,q.size(),$time);
35        end
36        Spaces.put(K);
37 
38     
39    end
40endtask
41 
42                 
43 
44    initial        
45        fork
46            producer();
47            consumer();
48            forever #100 $stop; 
49        join_any
50     
51 
52endprogram

1***** Veritak SV32 Engine Version 446 Build May 28 2013*****
2 
3Produced           1 q.size()=          1                    0
4 Consumed           0 q.size()=          0                    0
5Produced           2 q.size()=          1                    0
6 Consumed           1 q.size()=          0                    0
7....

生産者と消費者のシミュレーション問題

上の例では、生産者と消費者が1対1の場合でした。それでは、消費者が複数いた場合は、どうなるのでしょうか？消費者が4人いたとしてシミュレーションしてみます。

起動スレッドが分かりやすいようにナンバーを渡しています。

01program pr7;
02        parameter  int N=8;
03        parameter int M=1;
04        parameter int Consumer=4;
05        my_semaphore Spaces;
06        my_semaphore Elements;
07        int value=0;    
08        int q[$];
09 
10         
11 
12task producer(int n);
13 
14        forever begin
15 
16                Spaces.get(M);
17                repeat(M) begin
18         
19                        q.push_back(value++);
20                 
21                        $display("Produced(%1d) %d q.size()=%d %d",n,value,q.size(),$time);
22                         
23                end
24                Elements.put(M);
25         
26         
27        end
28endtask
29 
30 
31task automatic consumer(int n);
32 
33        forever begin
34                 
35                 
36                process p1;
37                int i;
38 
39                p1=process::self();
40                 
41                         
42                Elements.get(1);
43                i=q.pop_front();
44                 
45                $display("      Consumed(%1d)  %d q.size()=%d %d",n,i,q.size(),$time);
46                Spaces.put(1);
47                 
48 
49         
50 
51        end
52endtask
53 
54 
55 
56        initial begin
57                Elements=new(0);
58                Spaces=new (N);
59                                         
60 
61                                 
62                fork
63                        producer(1);
64 
65                        consumer(1);
66                        consumer(2);
67                        consumer(3);
68                        consumer(4);
69                                 
70                                 
71                         
72                        forever #100 $stop;     
73                join_any
74        end
75 
76endprogram

これを走らせると、スレッド4に偏って生成されていることが分かります。この結果は、シミュレータ依存ではありますが、他のシミュレータでも似たような結果となります。シミュレータは、イベント生成の順にイベントを処理しているだけで、偏りのないスレッド生成に関しては関知しないことに注意してください。　

01***** Veritak SV32 Engine Version 446 Build May 30 2013*****
02 
03Produced(1)           1 q.size()=          1                    0
04Produced(1)           2 q.size()=          2                    0
05Produced(1)           3 q.size()=          3                    0
06Produced(1)           4 q.size()=          4                    0
07Produced(1)           5 q.size()=          5                    0
08Produced(1)           6 q.size()=          6                    0
09Produced(1)           7 q.size()=          7                    0
10Produced(1)           8 q.size()=          8                    0
11        Consumed(4)            0 q.size()=          7                    0
12        Consumed(4)            1 q.size()=          6                    0
13        Consumed(4)            2 q.size()=          5                    0
14        Consumed(4)            3 q.size()=          4                    0
15        Consumed(4)            4 q.size()=          3                    0
16        Consumed(3)            5 q.size()=          2                    0
17        Consumed(2)            6 q.size()=          1                    0
18        Consumed(1)            7 q.size()=          0                    0
19Produced(1)           9 q.size()=          1                    0
20Produced(1)          10 q.size()=          2                    0
21Produced(1)          11 q.size()=          3                    0
22Produced(1)          12 q.size()=          4                    0
23Produced(1)          13 q.size()=          5                    0
24Produced(1)          14 q.size()=          6                    0
25Produced(1)          15 q.size()=          7                    0
26Produced(1)          16 q.size()=          8                    0
27        Consumed(4)            8 q.size()=          7                    0
28        Consumed(4)            9 q.size()=          6                    0
29        Consumed(4)           10 q.size()=          5                    0
30        Consumed(4)           11 q.size()=          4                    0
31        Consumed(4)           12 q.size()=          3                    0
32        Consumed(3)           13 q.size()=          2                    0
33        Consumed(2)           14 q.size()=          1                    0
34        Consumed(1)           15 q.size()=          0                    0
35....

それでは、偏りのないように、テストベンチを書くには、どうしたらよいでしょうか？

生産者と消費者のシミュレーションの改善

なるべくならスレッド生成管理を自分で書くのがよいでしょう。イベントによるハンドシェークや、#0を使うのは、スパゲテッィプログラムになり易いので、こちらのテクニックの方が分かり易い場面があるでしょう。

下は、Consumerのスレッド起動をFIFOで管理しています。具体的には、task select_resume_threadで、起動するスレッドを選択しています。この例では、単純にFIFOで管理しています。前のソースから追加部は、この部分だけです。ランダムに起動スレッドを選択したり、分布重みで起動するスレッドを選択する追加をしても、この部分だけでよいでしょう。このように、スレッド生成に関し、resume/suspendを使って見通しがよくなる場合があります。

Windowsでは、Fiber、一般のプログラミング言語的には、コルーチンと呼ばれたりしますが、VerilogHDL自体、コルーチンの塊みたいなものなのでNative機能とも言えます。しかし、Veraでは、搭載されていませんでした。

01program pr7;
02        parameter  int N=6;
03        parameter int M=1;
04        parameter int Consumer=4;
05        my_semaphore Spaces;
06        my_semaphore Elements;
07        int value=0;    
08        int q[$];
09        process pq[$];//スレッド起動管理を追加
10         
11         
12 
13task producer(int n);
14 
15        forever begin
16 
17                Spaces.get(M);
18                repeat(M) begin
19         
20                        q.push_back(value++);
21                 
22                        $display("Produced(%1d) %d q.size()=%d %d",n,value,q.size(),$time);
23                         
24                end
25                Elements.put(M);
26         
27         
28        end
29endtask
30 
31task automatic  select_resume_thread(process p);//Conumer起動スレッド管理
32//SUSPENDしたものからresumeして行く
33 
34                if (Consumer==1) return;//Nothing to do.
35 
36                pq.push_back(p);
37//休止するスレッドをセーブ。pは、select_resume_threadのスレッドで、直接のConsumerスレッドではない。しかし復帰すれば、問題なくConsumerに継続する。
38                if (pq.size()>=Consumer) begin//シンプルFIFO
39                        process p1;
40                        p1=pq.pop_front();
41                        p1.resume();
42//suspendしたスレッドを復帰させる、一個のスレッドだけを生かせば、実行順は、常にユーザ制御可能。一個もないとイベントは枯渇する。
43                end
44                p.suspend();
45//休止状態に入る。ブロックし他のスレッドへ！
46endtask
47task automatic consumer(int n);
48 
49        forever begin
50                 
51                 
52                process p1;
53                int i;
54 
55                p1=process::self();
56                 
57                         
58                Elements.get(1);
59                i=q.pop_front();
60                 
61                $display("       Consumed(%1d)  %d q.size()=%d %d",n,i,q.size(),$time);
62                Spaces.put(1);
63                 
64                select_resume_thread(p1);//Conumer起動スレッド管理を追加
65         
66 
67        end
68endtask
69 
70 
71 
72        initial begin
73                Elements=new(0);
74                Spaces=new (N);
75                                         
76 
77                                 
78                fork
79                        producer(1);
80 
81                        consumer(1);
82                        consumer(2);
83                        consumer(3);
84                        consumer(4);
85                                 
86                                 
87                         
88                        forever #100 $stop;     
89                join_any
90        end
91 
92endprogram

下が実行結果ですが、過渡期のあと、偏りなくConsumer スレッドが順に処理されている様子が分かります。

01***** Veritak SV32 Engine Version 446 Build May 30 2013*****
02 
03Produced(1)           1 q.size()=          1                    0
04Produced(1)           2 q.size()=          2                    0
05Produced(1)           3 q.size()=          3                    0
06Produced(1)           4 q.size()=          4                    0
07Produced(1)           5 q.size()=          5                    0
08Produced(1)           6 q.size()=          6                    0
09         Consumed(4)            0 q.size()=          5                    0
10         Consumed(3)            1 q.size()=          4                    0
11         Consumed(2)            2 q.size()=          3                    0
12         Consumed(1)            3 q.size()=          2                    0
13Produced(1)           7 q.size()=          3                    0
14Produced(1)           8 q.size()=          4                    0
15Produced(1)           9 q.size()=          5                    0
16Produced(1)          10 q.size()=          6                    0
17         Consumed(4)            4 q.size()=          5                    0
18Produced(1)          11 q.size()=          6                    0
19         Consumed(3)            5 q.size()=          5                    0
20Produced(1)          12 q.size()=          6                    0
21         Consumed(2)            6 q.size()=          5                    0
22Produced(1)          13 q.size()=          6                    0
23         Consumed(1)            7 q.size()=          5                    0
24Produced(1)          14 q.size()=          6                    0
25         Consumed(4)            8 q.size()=          5                    0
26Produced(1)          15 q.size()=          6                    0
27         Consumed(3)            9 q.size()=          5                    0
28Produced(1)          16 q.size()=          6                    0
29         Consumed(2)           10 q.size()=          5                    0
30Produced(1)          17 q.size()=          6                    0
31         Consumed(1)           11 q.size()=          5                    0
32Produced(1)          18 q.size()=          6                    0
33         Consumed(4)           12 q.size()=          5                    0
34Produced(1)          19 q.size()=          6                    0
35         Consumed(3)           13 q.size()=          5                    0
36Produced(1)          20 q.size()=          6                    0
37...

食事する哲学者のシミュレーション

ダイクストラが提起した汎用的な問題ですが、SystemVerilogでシミュレーションするとどうなるのでしょうか？こちらを参考にしてCodingしてみましょう。

うまくいかない例のうまくいかないシミュレーション

各フォークをセマフォで管理した場合のシミュレーションです。

01program process23b;
02        my_semaphore sems[5];
03        int map[int];
04         
05 
06        task automatic t1(int num);
07 
08                forever begin
09                        sems[num].get(1);
10                        sems[ (num+1)%5].get(1);
11                        $display("Eating %d %d",num,$time);
12                        map[num] +=1;
13                        sems[(num+1)%5].put(1);
14                        sems[num].put(1);
15                end
16 
17        endtask
18 
19 
20        initial begin
21                foreach (sems[i]) sems[i]=new(1);
22                fork
23                                t1(0);
24                                t1(1);
25                                t1(2);
26                                t1(3);
27                                t1(4);
28                                #100000;
29                join_any
30                $display("%p",map);
31        end
32 
33 
34 
35endprogram

結果は次のように哲学者0ばかりの無限ループになり、他の哲学者(スレッド)にいきません。これは、アルゴリズムの問題ではなく、シミュレーションの仕方の問題です。 foreverループ内にブロックする命令がないのが原因です。semaphoreのgetは、取得できない場合、ブロックされますが、後行で返しているために常に取得可能でブロックされる機会がありません。

01***** Veritak SV32 Engine Version 446 Build May 31 2013*****
02 
03Eating           0                    0
04C:\Users\Public\sv_test\process\pr23b.sv(65)::Warning: 連想配列のインデックスが存在しません。default値を返します。
05Eating           0                    0
06Eating           0                    0
07Eating           0                    0
08Eating           0                    0
09Eating           0                    0
10Eating           0                    0
11Eating           0                    0
12...

そこで、次のようにブロックするステートメントを置いて他のスレッドに行くようにします。

01task automatic t1(int num);
02 
03        forever begin
04            sems[num].get(1);
05            #10;//ブロッキングステートメント
06            $display("Got Left %d",num);
07            sems[ (num+1)%5].get(1);
08            $display("Got Right %d",num);
09            #10;//ブロッキングステートメント
10            $display("Eating %d %d",num,$time);
11            map[num] +=1;
12            sems[(num+1)%5].put(1);
13            sems[num].put(1);
14        end
15 
16    endtask

これの結果は、次のように途中で止まってしまいます。うまくいかないアルゴリズムの問題、デッドロックがうまく再現できました。

***** Veritak SV32 Engine Version 446 Build May 31 2013*****

Got Left           0
Got Left           1
Got Left           2
Got Left           3
Got Left           4
'{}

---------- シミュレーションを終了します。time=100000ns

食事する哲学者のシミュレーション　解１

"1つのプロセスだけが逆順でフォークを要求"のシミュレーションです。

01program process23c;
02        my_semaphore sems[5];
03        int map[int];
04         
05 
06        task automatic t1(int num);
07 
08                forever begin
09                        sems[num].get(1);
10                        #10;//ブロッキングステートメント
11                 
12                        sems[ (num+1)%5].get(1);
13         
14                        #10;//ブロッキングステートメント
15                        $display("Eating %d %d",num,$time);
16                        map[num] +=1;
17                        sems[(num+1)%5].put(1);
18                        sems[num].put(1);
19                end
20 
21        endtask
22 
23        task automatic t2(int num);
24 
25                forever begin
26                        sems[ (num+1)%5].get(1);
27                 
28                        #10;//ブロッキングステートメント
29         
30                        sems[num].get(1);
31         
32                        #10;//ブロッキングステートメント
33                        $display("Eating %d %d",num,$time);
34                        map[num] +=1;
35                 
36                        sems[num].put(1);
37                        sems[(num+1)%5].put(1);
38                end
39 
40        endtask
41 
42 
43 
44        initial begin
45                foreach (sems[i]) sems[i]=new(1);
46                fork
47                                t1(0);
48                                t1(1);
49                                t1(2);
50                                t1(3);
51                                t2(4);//哲学者4だけ逆順に取る
52                                #100000;
53                join_any
54                $display("%p",map);
55        end
56 
57 
58 
59endprogram

こちらは、確かにうまく周っています。一つの時刻に最大2哲学者が食事しています。下の最後の行は、度数を現していますが、哲学者3だけが、倍の食事している以外は、平等に食事しています。哲学者3だけが多いのは、予想されたことではありますが、汎用的な結果なのかどうかは筆者の力では分かりません。（他のシミュレータで同じ結果になるのは確認しました。）
.

01...
02Eating           0                99850
03Eating           3                99870
04Eating           4                99880
05Eating           2                99880
06Eating           1                99890
07Eating           3                99900
08Eating           0                99900
09Eating           3                99920
10Eating           4                99930
11Eating           2                99930
12Eating           1                99940
13Eating           3                99950
14Eating           0                99950
15Eating           3                99970
16Eating           4                99980
17Eating           2                99980
18Eating           1                99990
19'{0:1999,1:2000,2:2000,3:3999,4:1999}
20 
21**** Test Done. Total 187.00[msec] ****

食事する哲学者のシミュレーション　解２

こちらを参考にしています。

01program process23a;
02        parameter int N=5;
03        parameter int THINKING= 0,
04                                 HUNGRY=1,
05                                 EATING= 2;
06        `define LEFT (i+N-1)%N /* i の左側*/
07        `define RIGHT (i+i)%N /* i の右側*/
08 
09        my_semaphore sems[N];
10        int state[N];
11        int map[int];
12 
13 
14 
15        task automatic  test(int i);
16 
17                if (  state[i] == HUNGRY &&
18                        state[`LEFT] != EATING &&
19                        state[`RIGHT] != EATING) 
20                begin
21                                state[i] = EATING;
22                                sems[i].put(1);
23                end
24        endtask
25 
26        task take_forks(int i);
27                 
28                state[i] = HUNGRY;
29                test(i);
30                sems[i].get(1);
31        endtask
32 
33        task automatic put_forks(int i);
34                state[i] = THINKING; /* 食事終了*/
35                test(`LEFT); /* 左側は食事可能? */
36                test(`RIGHT); /* 右側は食事可能? */
37        endtask
38         
39        task think;
40                #10;
41        endtask
42 
43        task automatic eat(int i);
44                map[i] +=1;
45                $display("Eating %d %d",i,$time);
46                #10;
47        endtask
48 
49 
50        task automatic t1(int i);
51 
52                forever begin
53                        think();
54                        take_forks(i); /* 2本のフォークを取るか、封鎖*/
55                        eat(i);
56                        put_forks(i); /* 2本のフォークを置く*/
57                end
58 
59        endtask
60 
61 
62 
63         
64 
65        initial begin
66                foreach (sems[i]) sems[i]=new(0);
67                fork
68                                 
69                                for (int i=0;i< N;i++) begin
70                                        fork
71                                                automatic int k=i;
72                                                begin
73                                                        t1(k);
74                                                end
75                                        join_none
76                                end
77                                #10000;
78                join
79                $display("%p",map);
80                 
81        end
82 
83 
84 
85endprogram

01....
02Eating           0                 9940
03Eating           2                 9940
04Eating           4                 9950
05Eating           1                 9950
06Eating           0                 9960
07Eating           2                 9960
08Eating           4                 9970
09Eating           1                 9970
10Eating           0                 9980
11Eating           2                 9980
12Eating           4                 9990
13Eating           1                 9990
14'{0:499,1:500,2:499,3:1,4:500}
15Info: $finishコマンドを実行します。time=10000ns
16 
17**** Test Done. Total 31.00[msec] ****

一つの時刻にきっちり2哲学者が食事をしています。しかし、哲学者3は、一回しかできていません。他のシミュレータでも結果は同じになります。最初の選択が後の結果の原因となっているので、当然と言えば当然かもしれませんが、この結果は予想できませんでした。