RTOSを手を動かしながら理解する(スケジューリング編)

2022/06/30に公開

RTOSを手を動かしながら理解する(スケジューリング編)

以下の本の内容を整理するため、自分なりに手を動かしたものを副読的にまとめていきます。
実装は Aruduino Uno/C で行っています。

Real-time Operating Systems Book 1: The Theory Dr. Jim Cooling
https://www.amazon.co.jp/dp/1795340657/ref=cm_sw_r_tw_dp_2ZKTRZAAPVV3MH36F5P1

制御系の組み込みシステムで採用されるリアルタイムOSでは、システムに課せられる時間制約(deadline)を満たす必要があります。
このために重要となる考え方が スケジューリング(scheduling) です。

スケジューリングは、OSのプロセスを実行するタイミング、及び実行時間を制御する スケジューラー としてカーネルに組み込まれます。
スケジューリング機能の中で、プロセスの状態に応じてCPU使用権の切替操作を行うものをディスパッチャと呼びます。
ディスパッチャにより実行中のプロセスが中断されたとき、CPUの状態(context)は READYキュー と呼ばれる実行待ち行列の末尾に加わります。

ここでは、リアルタイムOSに採用されるスケジューリングアルゴリズムをいくつか紹介します。

ラウンドロビン・スケジューリング

一定時間のタイムテーブルごとにプロセスを実行していくやり方です。
以下の例では、一定周期ごとにstateの信号を変化させ、任意のピンのLEDを点滅させています。

unsigned long tickTime, taskXpreviousTime, taskYpreviousTime, currentTime;
volatile int state = LOW;

void setup() {
  taskXpreviousTime = 0;
  taskYpreviousTime = 0;
  pinMode(13, OUTPUT);
  pinMode(2, OUTPUT);
  blink();
}

int blink(void) {
  for (;;) {
    currentTime = micros();

    // TaskX
    if (currentTime - taskXpreviousTime > 500000) {
      taskXpreviousTime = currentTime;
      digitalWrite(13, digitalRead(13) == state ? 1 : 0);
    }
    // TaskY
    if (currentTime - taskYpreviousTime > 1000000) {
      taskYpreviousTime = currentTime;
      digitalWrite(2, digitalRead(2) == state ? 1 : 0);
    }
  }
}

void loop() {
}

RoundRobinScheduringImage

RoundRobinSchedulingGraph

優先度先取り(Priority pre-emptive)方式

全てのプロセスに固定の優先度を付与する方式です。高い優先度の処理は、低い優先度の処理からプロセスの実行権を強制的に奪うことができます。
以下の例を見てみましょう。

#include <Servo.h>
unsigned long tickTime, taskXpreviousTime, taskYpreviousTime, currentTime;
volatile int state = LOW;
int buttonState;
Servo servo;

void setup() {
  taskXpreviousTime = 0;
  taskYpreviousTime = 0;
  pinMode(4, INPUT_PULLUP);
  pinMode(13, OUTPUT);
  pinMode(2, OUTPUT);
  servo.attach(9);
  blink();
}

int blink(void) {
  for (;;) {
    currentTime = micros();
    buttonState = digitalRead(4);

    // TaskX
    if (currentTime - taskXpreviousTime > 500000) {
      taskXpreviousTime = currentTime;
      digitalWrite(13, digitalRead(13) == state ? 1 : 0);
    }
    // TaskY
    if (currentTime - taskYpreviousTime > 1000000) {
      taskYpreviousTime = currentTime;
      digitalWrite(2, digitalRead(2) == state ? 1 : 0);
    }
    // TaskZ
    if (buttonState == LOW) {
      servoRun();
    }
  }
}

void servoRun () {
  int angle;
  for ( angle = 0; angle <= 180; angle += 30 ) {
    servo.write(angle);
    delay(1000);
  }
  buttonState = !buttonState;
}

void loop() {
}

デモ

https://drive.google.com/file/d/16GbJ7gHpIKu-HHP99WCFMPIFoasaL6cZ/view?usp=sharing

PreEmptiveSchedulingGraph

TaskZ(サーボモーターの回転)のタイマー割り込みにより、実行中のTaskXとTaskYは中断されます。
割り込みは優先順位が高く設定されているため、今回はタクトスイッチの入力をトリガーに、TaskZによる先取りを実現しています。
サーボモーターの制御にはServoライブラリを使用しています。

Arduino UNOに代表されるAVRマイコンには、TimerやAD変換などの複数の割り込みが搭載されています。
AVRのTimerには下記の三種類が用意されています。

bit数 PWMピン function
Timer0 8bit 5,6 delay(),mills()
Timer1 16bit 9,10 -
Timer2 8bit 3,11 tone()

AVRの割り込み優先度表は下記になります。
アドレスが若いほど優先度が高く(RESETが最も高く)設定されています。
AVR_Interrupts
Basics of AVR Interruptsより

参考文献

https://exploreembedded.com/wiki/Basics_of_AVR_Interrupts
https://w.atwiki.jp/kumikomi-yitjc/pages/127.html
https://kurobekoblog.com/timer0_attiny13
https://qiita.com/suzukinori/items/939cc9f49e535c4eadd7
https://ja.wikipedia.org/wiki/スケジューリング#top-page
https://www.tron.org/ja/onwebseminar/chap3/

Discussion