理想のＲＴＯＳを自作する (１)

今年の目標は理想のＲＴＯＳ（リアルタイムＯＳ）の自作だ。って、いうか、もう２月なんですけど。遅！(笑)

【タイマー粒度の問題】

ＲＴＯＳは覚えきれないほど沢山の物があるが、共通する一番の問題はタイマー粒度がせいぜい１ｍｓ程度と荒すぎることだと思っている。調べる気力もないので不確かではあるが恐らく全てのＲＴＯＳがそうなっていると思われる。これはタイマー処理の実装の問題である。

例えば、マイクロ秒間隔で正確な制御がしたい。そんな単純なことがＲＴＯＳでは出来ない。出来ないというよりも作法的にＲＴＯＳでやってはいけないと言うべきかもしれない。タイマー粒度より細かい時間ではタイマーウェイトが使えないため優先度の高いタスクでループ処理にて時間待ちさせるしか方法はない。数１０マイクロ秒程度ならまだ許せるかもしれないがループ待ちの間は他のタスクの実行を妨げることになるため数百マイクロ秒以上もの長い期間をループ待ちすることは良いこととは言えないし他のタスクと協調動作させようとすると今度は時間が不正確になる。あっちを立てればこっちが立たずみたいになり最終的には奥の手（ＨＷタイマー割り込み）を使ってしまうことになるだろう。

リアルタイムという言葉に惹かれＲＴＯＳを導入したがタイマー粒度の問題でうまく実装できなかったり割り込み管理のオーバーヘッドで割り込みレスポンスも悪くなったりで一体どこがリアルタイムなんだってガッカリしてしまった人も多くいるのではないだろうか。ＲＴＯＳでは必然的により高速なＣＰＵとより多量なＲＡＭが求められるためターゲットはメリットが出やすい（逆に言えばデメリットが分かりにくくなる）上位ＣＰＵとなる。下位ＣＰＵにも対応するＲＴＯＳもあるが開発規模も大きくならないことから下位ＣＰＵで使うメリットはあまりないと思った方が良いのかもしれない．．．が、望むものが無ければ自分で作ればいい。ってことで、理想のＲＴＯＳを考えてみた。

【理想のＲＴＯＳ】☆は必須機能

１．☆タイマー粒度に依存しない高分解能なタイマー同期機能。
２．☆ＧＰＩＯピン変化／キャプチャー同期機能。
３．☆優先順位によるプリエンプティブ・スケジューリング。
４．☆関数呼び出しによるラウンドロビン・スケジューリング。
５．タイムスライスは正確な時間制御を損なうためあえて実装しない。
６．優先度数は多くても使いこなせないので数レベルもあれば十分。
７．下位ＣＰＵでも使えるコンパクトなＲＴＯＳを目指す。
８．当初のターゲットは、ＡＶＲシリーズの１６ＭＨｚとする。
９．将来的には、Raspberry Pi Pico(rp2040)等のマルチ・コアＣＰＵ対応。<--妄想？(/・ω・)/

【優先度の実装】

一般的な優先順位別にタスクリストを持つ方法では最優先のタスクを検索するために優先順位の高いほうから低い方へ向かって順番に検索しなければならず低優先度タスクほどオーバーヘッドは大きくなる。さらに低優先度タスクは常態的にレディ状態にあると想定できることから低優先度タスクほど検索回数が多くなるとも考えられる。これらのことから優先度検索のオーバーヘッドを回避するため優先度別のリストを連結したオーダードリスト構造を考えてみた。リスト操作時に通常の線形リストよりも数ステップ程度の追加処理が必要になるが先頭が常に最優先タスクとなるため優先度検索しなくて済むようになる。

【空のリスト状態】

【優先度０のタスクだけが登録されている状態】

【優先度３のタスクだけが登録されている状態】

【全ての優先度のタスクが登録されている状態】

タスクの追加は簡単である。まず追加するタスクの優先度に対応するtailポインターから優先度の高いほう(小さな数字)に向かって(null)でないtailポインターを探す。(null)でないtailポインターが見つかった場合は、そのtailポインターが示すタスクの次に挿入し、見つからなればリストの先頭に挿入する。最後に追加タスクの優先度に対応するtailポインターに追加したタスクを登録して完了である。
また、tailポインターの検索については優先度ビットマップにより優先順位に関わらず同一コストで検索が可能だ。

最優先タスクは常にリスト先頭となることから削除についてはリスト先頭のみ考えれば良い。削除タスクの優先度に対応するtailポインターが削除タスク自身を示す場合は削除後にその優先度のリストが空になるのでtailポインターを(null)にする。

【enqueue/dequeue処理の抜粋】

#define TASK_PRIO_LOW   7
#define TASK_PRIO_HIGH  0

typedef struct TASK
{
  struct TASK *next;
  struct TASK **tail;
  uint8_t pbit;
  uint8_t pmsk;
  ...
] TASK_T;

TASK_T *_tail[TASK_PRIO_LOW + 1];
TASK_T *_head;
uint8_t _prio;

uint8_t Task::msbpos(uint8_t val)
{
  static const uint8_t MSBPOS[] PROGMEM =
  {
    0xFF, 0x00, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02,
    0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03
  };
  uint8_t off = 0;
  if (val >= 0x10)
  {
    off = 4;
    val = __builtin_avr_swap(val);
  }
  return pgm_read_byte(MSBPOS + (val & 0x0F)) + off;
}

void Task::enqueue(TASK_T *task)
{
  uint8_t last = msbpos(_prio & task->pmsk);
  if (last <= TASK_PRIO_LOW)
  {
    TASK_T **tail = &_tail[last];
    task->next = (*tail)->next;
    *task->tail = (*tail)->next = task;
  }
  else
  {
    task->next = _head;
    _head = *task->tail = task;
  }
  _prio |= task->pbit;
}

TASK_T *Task::dequeue(void)
{
  TASK_T *task = _head;
  if (task)
  {
    TASK_T **tail = task->tail;
    if (task == *tail)
    {
      *tail = 0;
      _prio &= ~task->pbit;
    }
    _head = task->next;
  }
  return task;
}

#define TASK_PRIO_LOW 7

#define TASK_PRIO_HIGH 0

typedef struct TASK

{

struct TASK *next;

struct TASK **tail;

uint8_t pbit;

uint8_t pmsk;

...

] TASK_T;

TASK_T *_tail[TASK_PRIO_LOW + 1];

TASK_T *_head;

uint8_t _prio;

uint8_t Task::msbpos(uint8_t val)

{

static const uint8_t MSBPOS[] PROGMEM =

{

0xFF, 0x00, 0x01, 0x01, 0x02, 0x02, 0x02, 0x02,

0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03, 0x03

};

uint8_t off = 0;

if (val >= 0x10)

{

off = 4;

val = __builtin_avr_swap(val);

}

return pgm_read_byte(MSBPOS + (val & 0x0F)) + off;

}

void Task::enqueue(TASK_T *task)

{

uint8_t last = msbpos(_prio & task->pmsk);

if (last <= TASK_PRIO_LOW)

{

TASK_T **tail = &_tail[last];

task->next = (*tail)->next;

*task->tail = (*tail)->next = task;

}

else

{

task->next = _head;

_head = *task->tail = task;

}

_prio |= task->pbit;

}

TASK_T *Task::dequeue(void)

{

TASK_T *task = _head;

if (task)

{

TASK_T **tail = task->tail;

if (task == *tail)

{

*tail = 0;

_prio &= ~task->pbit;

}

_head = task->next;

}

return task;

}

【コンテキスト・スイッチング】

タスク切替時のＣＰＵの全レジスタ保存は必須？でもない。一見改善の余地がなさそうに思えても改善の余地はあるものだ。Ｃ／Ｃ＋＋言語を前提にするならコンパイラの関数コールのレジスタ・ルールに従い保存が必要なレジスタだけを保存すれば良い。これは、標準関数でもあるsetjmp()/logjmp()を使うことで汎用的に実装できて関数コールによるスイッチング速度を改善させる効果がある。割り込み処理からのスイッチングにも対応できる。これは言語仕様をうまく利用したアイデアだ。

【タスク・スタック領域】

簡易的なＲＴＯＳのスタック領域は、スタック・ポインター～ヒープ・エンドまでの空きヒープ領域を適当に区切って利用したりするがその方法だとヒープ管理領域を壊してしまうためメモリ管理(malloc)と共存することができなくなる。メモリ管理と共存するにはメモリ管理機能を使ってスタック領域を割り当てるのが正しいやり方だ。但し、スタック・オーバーフローさせないことが大前提ではあるが。

次回は問題のタイマー処理かな．．．って、まだ続くのか？(笑)

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル