Mercurial > hg > Members > nobuyasu > CbC
annotate DPP/tableau2.cbc @ 33:3946f8d26710 draft default tip
add benchmarck/binary-trees
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 09 Apr 2013 16:41:30 +0900 |
parents | 6695c97470f3 |
children |
rev | line source |
---|---|
0 | 1 /* |
2 ** Dining Philosophers Problem's scheduler | |
3 ** with state developper as a tableau method | |
4 | |
5 ** 連絡先: 琉球大学情報工学科 河野 真治 | |
6 ** (E-Mail Address: kono@ie.u-ryukyu.ac.jp) | |
7 ** | |
8 ** このソースのいかなる複写,改変,修正も許諾します。ただし、 | |
9 ** その際には、誰が貢献したを示すこの部分を残すこと。 | |
10 ** 再配布や雑誌の付録などの問い合わせも必要ありません。 | |
11 ** 営利利用も上記に反しない範囲で許可します。 | |
12 ** バイナリの配布の際にはversion messageを保存することを条件とします。 | |
13 ** このプログラムについては特に何の保証もしない、悪しからず。 | |
14 ** | |
15 ** Everyone is permitted to do anything on this program | |
16 ** including copying, modifying, improving, | |
17 ** as long as you don't try to pretend that you wrote it. | |
18 ** i.e., the above copyright notice has to appear in all copies. | |
19 ** Binary distribution requires original version messages. | |
20 ** You don't have to ask before copying, redistribution or publishing. | |
21 ** THE AUTHOR DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE. | |
22 | |
23 */ | |
24 #include <stdlib.h> | |
25 #include <time.h> | |
26 #include "dpp2.h" | |
27 #include "queue.h" | |
28 #include "memory.h" | |
29 #include "state_db.h" | |
30 #include "ltl.h" | |
31 | |
32 int NUM_PHILOSOPHER = 5; /* A number of philosophers must be more than 2. */ | |
33 | |
1
6695c97470f3
modify some files.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
34 //static code (*ret)(int); |
6695c97470f3
modify some files.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
35 code (*ret)(int,void*); |
0 | 36 static void *env; |
37 | |
1
6695c97470f3
modify some files.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
38 #define __environment _CbC_environment |
6695c97470f3
modify some files.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
39 #define __return _CbC_return |
6695c97470f3
modify some files.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
40 |
6695c97470f3
modify some files.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
41 |
0 | 42 static PhilsPtr phils_list = NULL; |
43 | |
44 static int max_step = 100; | |
45 | |
46 static StateDB state_db; | |
47 static MemoryPtr mem; | |
48 static StateNode st; | |
49 static int always_flag; // for LTL | |
50 | |
51 int | |
52 list_length(TaskPtr list) | |
53 { | |
54 int length; | |
55 TaskPtr t; | |
56 | |
57 if (!list) return 0; | |
58 t = list->next; | |
59 | |
60 for (length = 1; t && t != list; length++) { | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
61 t = t->next; |
0 | 62 } |
63 return length; | |
64 } | |
65 | |
66 TaskPtr | |
67 get_task(int num, TaskPtr list) | |
68 { | |
69 while (num-- > 0) { | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
70 list = list->next; |
0 | 71 } |
72 return list; | |
73 } | |
74 | |
75 | |
76 static TaskIteratorPtr task_iter; | |
77 static int depth,count; | |
78 | |
79 /* | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
80 Performe depth frist search |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
81 Possible task iterleave is generated by TaskIterator |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
82 (using task ring) |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
83 State are recorded in StateDB |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
84 all memory fragments are regsitered by add_memory_range() |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
85 including task queue |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
86 */ |
0 | 87 |
88 | |
89 code tableau(TaskPtr list) | |
90 { | |
91 StateDB out; | |
92 | |
93 st.hash = get_memory_hash(mem,0); | |
94 if (lookup_StateDB(&st, &state_db, &out)) { | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
95 // found in the state database |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
96 //printf("found %d\n",count); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
97 while(!(list = next_task_iterator(task_iter))) { |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
98 // no more branch, go back to the previous one |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
99 TaskIteratorPtr prev_iter = task_iter->prev; |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
100 if (!prev_iter) { |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
101 printf("All done count %d\n",count); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
102 memory_usage(); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
103 show_result(always_flag); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
104 goto ret(0,env); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
105 } |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
106 //printf("no more branch %d\n",count); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
107 depth--; |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
108 free_task_iterator(task_iter); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
109 task_iter = prev_iter; |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
110 } |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
111 // return to previous state |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
112 // here we assume task list is fixed, we don't have to |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
113 // recover task list itself |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
114 restore_memory(task_iter->state->memory); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
115 //printf("restore list %x next %x\n",(int)list,(int)(list->next)); |
0 | 116 } else { |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
117 // one step further |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
118 depth++; |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
119 task_iter = create_task_iterator(list,out,task_iter); |
0 | 120 } |
121 //printf("depth %d count %d\n", depth, count++); | |
122 count++; | |
123 goto list->phils->next(list->phils,list); | |
124 } | |
125 | |
126 code get_next_task_fifo(TaskPtr list) | |
127 { | |
128 TaskPtr t = list; | |
129 TaskPtr e; | |
130 | |
131 if (max_step--<0) goto die("Simuration end."); | |
132 | |
133 list = list->next; | |
134 goto list->phils->next(list->phils,list); | |
135 } | |
136 | |
137 code scheduler(PhilsPtr phils, TaskPtr list) | |
138 { | |
139 goto check(&always_flag, phils, list); | |
140 // goto next_next_task_fifo(list); | |
141 } | |
142 | |
143 code task_entry1(int count, PhilsPtr self, TaskPtr list, TaskPtr last); | |
144 | |
145 code task_entry2(int count,PhilsPtr self, TaskPtr list,TaskPtr last, TaskPtr q) | |
146 { | |
147 if (!q) { | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
148 goto die("Can't allocate Task\n"); |
0 | 149 } else { |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
150 add_memory_range(q,sizeof(Task),&mem); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
151 goto enqueue(count, self, list, last, q, task_entry1); |
0 | 152 } |
153 } | |
154 | |
155 code task_entry1(int count, PhilsPtr self, TaskPtr list, TaskPtr last) | |
156 { | |
157 StateDB out; | |
158 /* | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
159 printf("int count %d, PhilsPtr self %x, TaskPtr list %x, TaskPtr last %x\n", |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
160 count, self, list, last); |
0 | 161 */ |
162 | |
163 if (count++ < NUM_PHILOSOPHER) { | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
164 self = self->left; |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
165 goto create_queue(count,self,list,last,task_entry2); |
0 | 166 } else { |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
167 // make circular task list |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
168 last->next = list; |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
169 st.memory = mem; |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
170 st.hash = get_memory_hash(mem,0); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
171 lookup_StateDB(&st, &state_db, &out); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
172 task_iter = create_task_iterator(list,out,0); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
173 // start first task |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
174 goto list->phils->next(list->phils,list); |
0 | 175 } |
176 } | |
177 | |
178 code task_entry0(int count, PhilsPtr self, TaskPtr list, TaskPtr last, TaskPtr q) | |
179 { | |
180 add_memory_range(q,sizeof(Task),&mem); | |
181 goto task_entry1(count, self, q, q); | |
182 } | |
183 | |
184 code init_final(PhilsPtr self) | |
185 { | |
186 self->right = phils_list; | |
187 phils_list->left = self; | |
188 self->right_fork = phils_list->left_fork; | |
189 always_flag = 1; | |
190 //add_memory_range(&always_flag, sizeof(int), &mem); | |
191 //printf("init all\n"); | |
192 | |
193 goto create_queue(1, self, 0, 0, task_entry0); | |
194 } | |
195 | |
196 code init_phils2(PhilsPtr self, int count, int id) | |
197 { | |
198 PhilsPtr tmp_self; | |
199 | |
200 tmp_self = (PhilsPtr)malloc(sizeof(Phils)); | |
201 if (!tmp_self) { | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
202 goto die("Can't allocate Phils\n"); |
0 | 203 } |
204 self->right = tmp_self; | |
205 tmp_self->id = id; | |
206 tmp_self->right_fork = NULL; | |
207 tmp_self->left_fork = self->right_fork; | |
208 tmp_self->right = NULL; | |
209 tmp_self->left = self; | |
210 tmp_self->next = thinking; | |
211 add_memory_range(tmp_self,sizeof(Phils),&mem); | |
212 | |
213 count--; | |
214 id++; | |
215 | |
216 if (count == 0) { | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
217 goto init_final(tmp_self); |
0 | 218 } else { |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
219 goto init_fork2(tmp_self, count, id); |
0 | 220 } |
221 } | |
222 | |
223 code init_fork2(PhilsPtr self, int count, int id) | |
224 { | |
225 ForkPtr tmp_fork; | |
226 | |
227 tmp_fork = (ForkPtr)malloc(sizeof(Fork)); | |
228 if (!tmp_fork) { | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
229 goto die("Can't allocate Fork\n"); |
0 | 230 } |
231 tmp_fork->id = id; | |
232 tmp_fork->owner = NULL; | |
233 self->right_fork = tmp_fork; | |
234 add_memory_range(tmp_fork,sizeof(Fork),&mem); | |
235 | |
236 goto init_phils2(self, count, id); | |
237 } | |
238 | |
239 code init_phils1(ForkPtr fork, int count, int id) | |
240 { | |
241 PhilsPtr self; | |
242 | |
243 self = (PhilsPtr)malloc(sizeof(Phils)); | |
244 if (!self) { | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
245 goto die("Can't allocate Phils\n"); |
0 | 246 } |
247 phils_list = self; | |
248 self->id = id; | |
249 self->right_fork = NULL; | |
250 self->left_fork = fork; | |
251 self->right = NULL; | |
252 self->left = NULL; | |
253 self->next = thinking; | |
254 add_memory_range(self,sizeof(Phils),&mem); | |
255 | |
256 count--; | |
257 id++; | |
258 | |
259 goto init_fork2(self, count, id); | |
260 } | |
261 | |
262 code init_fork1(int count) | |
263 { | |
264 ForkPtr fork; | |
265 int id = 1; | |
266 | |
267 fork = (ForkPtr)malloc(sizeof(Fork)); | |
268 if (!fork) { | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
269 goto die("Can't allocate Fork\n"); |
0 | 270 } |
271 fork->id = id; | |
272 fork->owner = NULL; | |
273 add_memory_range(fork,sizeof(Fork),&mem); | |
274 | |
275 goto init_phils1(fork, count, id); | |
276 } | |
277 | |
278 code die(char *err) | |
279 { | |
280 printf("%s\n", err); | |
1
6695c97470f3
modify some files.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
281 goto ret(1, env); |
0 | 282 } |
283 | |
284 int main(int ac, char *av[]) | |
285 { | |
1
6695c97470f3
modify some files.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
286 ret = __return; |
6695c97470f3
modify some files.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
287 env = __environment; |
0 | 288 // srand((unsigned)time(NULL)); |
289 // srandom((unsigned long)time(NULL)); | |
290 srandom(555); | |
291 | |
292 if (ac==2) { | |
33
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
293 NUM_PHILOSOPHER = atoi(av[1]); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
294 if (NUM_PHILOSOPHER >10 ||NUM_PHILOSOPHER < 2) { |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
295 printf("illegal number of philosopher = %d\n", NUM_PHILOSOPHER ); |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
296 return 1; |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
297 } |
3946f8d26710
add benchmarck/binary-trees
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
1
diff
changeset
|
298 printf("number of philosopher = %d\n", NUM_PHILOSOPHER ); |
0 | 299 } |
300 | |
301 goto init_fork1(NUM_PHILOSOPHER); | |
302 } | |
303 | |
304 /* end */ |