title: Gears OS
author: Tatsuki IHA
profile:
lang: Japanese
code-engine: coderay

## 研究目的
- 当研究室では  処理の単位を Code Gear、 データの単位を Data Gear を用いて 信頼性が高い並列処理を行う Gears OS を開発している
- Gears OS では Task を Code Gear と実行するときに必要な Input Data Gear と出力するための Output Data Gear の組で表現される。 Input Data Gear/Output Data Gear によって依存関係が決定し、それにそって並列実行を行う.
- 信頼性の確保はモデルチェック、検証等を使用して行う。この信頼性のための計算は通常の計算とは別の階層のメタ計算として記述する。
- また、 メタ計算は信頼性の他に CPU, GPU などの実行環境の切り替え, データ拡張等の柔軟性を提供する。
- 本研究では、 Gears OS の並列処理機構の実装を行う。また、並列処理の実行を検証をメタ計算として記述することで、 並列処理の信頼性を保証する。

## 今週
- synchornized Queue のバグ

## synchornized Queue のバグ
- たとえば要素が一つだけの場合で事故る ↓ が同時に動くとtopが null になる
    - take は top を top->next に cas する(つまりnull)
    - put は last を element に cas し, last->next に element をいれる
    - putもtakeも１つの変数をcasするようにしたほうが良いか

``` c
__code putSynchronizedQueue(struct SynchronizedQueue* queue, union Data* data, __code next(...)) {
    Element* element = new Element();
    element->next = NULL;
    element->data = data;
    if (queue->top) {
        Element* last = queue->last;
        if (__sync_bool_compare_and_swap(&queue->last, last, element)) {
            last->next = element;
        } else {
            goto meta(context, C_putSynchronizedQueue);
        }
    } else {
        if (__sync_bool_compare_and_swap(&queue->top, NULL, element)) {
            queue->last = element;
        } else {
            goto meta(context, C_putSynchronizedQueue);
        }
    }
    goto meta(context, C_putSynchronizedQueue1);
}

__code putSynchronizedQueue1(struct SynchronizedQueue* queue, struct Semaphore* semaphore, __code next(...)) {
    semaphore->semaphore = (union Data*)queue->queueCount;
    semaphore->next = next;
    goto meta(context, queue->queueCount->v);
}
```

``` c
__code takeSynchronizedQueue(struct SynchronizedQueue* queue, struct Semaphore* semaphore) {
    semaphore->semaphore = (union Data*)queue->queueCount;
    semaphore->next = C_takeSynchronizedQueue1;
    goto meta(context, queue->queueCount->p);
}

__code takeSynchronizedQueue1(struct SynchronizedQueue* queue, __code next(union Data* data, ...)) {
    struct Element* top = queue->top;
    if (__sync_bool_compare_and_swap(&queue->top, top, top->next)) {
        data = top->data;
    } else {
        goto meta(context, C_takeSynchronizedQueue);
    }
    goto next(data, ...);
}
```

## synchornized Queue のバグ

https://www.research.ibm.com/people/m/michael/podc-1996.pdf とりあえず