|
24
|
1 title: Gears OS
|
|
|
2 author: Tatsuki IHA
|
|
|
3 profile:
|
|
|
4 lang: Japanese
|
|
|
5 code-engine: coderay
|
|
|
6
|
|
|
7 ## 研究目的
|
|
|
8 - 当研究室では 処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している
|
|
|
9 - Gears OS では Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される。 Input Data Gear/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う.
|
|
|
10 - 依存関係の解決やモデル検査等の本論の計算を行うためのメタな計算を Meta Code Gear で行う.
|
|
|
11 - 現在の Gears では Stack や Queue の operatation の API が存在しなため, 記述が困難になっている. そのため, この研究では Gears OS における API の記述方法を設計し, 実装する
|
|
|
12
|
|
|
13 ## 今週
|
|
|
14 - しゅうかつ！()
|
|
|
15 - SynchronizedQueue のインターフェースをとりあえず作った
|
|
|
16 - slack に \#times_innparusu作った, 多分やっていることと愚痴をつぶやく用
|
|
|
17 - \#gears 作らなきゃ -> 既にあった
|
|
|
18
|
|
|
19 ## SynchronizedQueue のインターフェース
|
|
|
20 - 中身はSingleLinkedQueue
|
|
|
21
|
|
|
22 ``` c
|
|
|
23 union Data* createSynchronizedQueue(struct Context* context) {
|
|
|
24 struct Queue* queue = &ALLOCATE(context, Queue)->queue;
|
|
|
25 struct SingleLinkedQueue* singleLinkedQueue = &ALLOCATE(context, SingleLinkedQueue)->singleLinkedQueue;
|
|
|
26 queue->queue = (union Data*)singleLinkedQueue;
|
|
|
27 singleLinkedQueue->top = NULL;
|
|
|
28 singleLinkedQueue->last = NULL;
|
|
|
29 queue->take = C_takeSynchronizedQueue;
|
|
|
30 queue->put = C_putSynchronizedQueue;
|
|
|
31 queue->isEmpty = C_isEmptySynchronizedQueue;
|
|
|
32 queue->clear = C_clearSynchronizedQueue;
|
|
|
33 return (union Data*)(queue);
|
|
|
34 }
|
|
|
35 ```
|
|
|
36
|
|
|
37 ## SynchronizedQueue の CS
|
|
|
38 - SingleLinkedQueue の take と put と違って CAS を挟んでいる
|
|
|
39 - まだ 何回かtry したら諦めるコード入れていない
|
|
|
40
|
|
|
41 ``` c
|
|
|
42 __code putSynchronizedQueue(struct Context* context, struct SingleLinkedQueue* queue, struct Element* element, union Data* data, enum Code next) {
|
|
|
43 element->next = NULL;
|
|
|
44 element->data = data;
|
|
|
45 if (queue->last) {
|
|
|
46 Element* last = queue->last;
|
|
|
47 if (__sync_bool_compare_and_swap(&queue->last, last, element)) {
|
|
|
48 last->next = element;
|
|
|
49 } else {
|
|
|
50 goto meta(context, C_putSynchronizedQueue);
|
|
|
51 }
|
|
|
52 } else {
|
|
|
53 if (__sync_bool_compare_and_swap(&queue->top, NULL, element)) {
|
|
|
54 queue->last = element;
|
|
|
55 } else {
|
|
|
56 goto meta(context, C_putSynchronizedQueue);
|
|
|
57 }
|
|
|
58 }
|
|
|
59 goto meta(context, next);
|
|
|
60 }
|
|
|
61
|
|
|
62 __code takeSynchronizedQueue(struct Context* context, struct SingleLinkedQueue* queue, union Data** data, enum Code next) {
|
|
|
63 if (queue->top) {
|
|
|
64 struct Element* top = queue->top;
|
|
|
65 if (__sync_bool_compare_and_swap(&queue->top, top, top->next)) {
|
|
|
66 *data = top->data;
|
|
|
67 } else {
|
|
|
68 goto meta(context, C_takeSynchronizedQueue);
|
|
|
69 }
|
|
|
70 } else {
|
|
|
71 *data = NULL;
|
|
|
72 }
|
|
|
73 goto meta(context, next);
|
|
|
74 }
|
|
|
75 ```
|
|
|
76
|
|
|
77 ## SynchronizedQueue のput の呼び出し
|
|
|
78 - meta_spawnTask で格納する Queue を入れ替えている
|
|
|
79 - Queue が複数あった場合, どうやって入れるQueue を選択するか?
|
|
|
80
|
|
|
81 ``` c
|
|
|
82 __code meta_spawnTask(struct Context* context, struct Queue* queue, enum Code next) {
|
|
|
83 context->data[D_Queue] = (union Data *)queue;
|
|
|
84 goto meta(context, context->next);
|
|
|
85 }
|
|
|
86
|
|
|
87 __code spawnTask(struct Context* context, struct Task* task, struct Element* element, struct Queue* activeQueue, struct Queue* waitQueue) {
|
|
|
88 struct Queue* queue;
|
|
|
89 if (task->idsCount == 0) {
|
|
|
90 // enqueue activeQueue
|
|
|
91 queue = activeQueue;
|
|
|
92 } else {
|
|
|
93 // enqueue waitQueue
|
|
|
94 queue = waitQueue;
|
|
|
95 }
|
|
|
96 queue->data = element->data;
|
|
|
97 queue->next = context->next;
|
|
|
98 goto meta_spawnTask(context, queue, queue->put);
|
|
|
99 }
|
|
|
100 ```
|
|
|
101
|
