Priority Inversion

‍‍‍‍‍‍ ‍‍ ‍‍‍‍‍‍ ‍‍‍‍‍‍ ‍‍

บทความนี้กล่าวถึงปัญหาหรือสถานการณ์ที่เรียกว่า Priority Inversion ในการทำงานเมื่อต้องใช้ RTOS ที่ทำงานในโหมด Preemptive Scheduling และสาธิตการทำงานโดยใช้ FreeRTOS สำหรับ Arduino (ใช้ไลบรารี Arduino_FreeRTOS สำหรับ AVR)

ก‍‍‍ารเขียนโปรแกรมโดยใช้ RTOS หรือระบบปฏิบัติการเวลาจริง จะต้องมีการแบ่งการทำงานของโปรแกรมออกเป็นงานย่อย หรือที่เราเรียกว่า ทาส์ก (Tasks) หรือบางทีก็เรียกว่า Threads สามารถทำงานได้อิสระจากกัน แต่จะต้องแชร์การใช้งานซีพียูร่วมกัน และมีระดับความสำคัญที่แตกต่างกันได้ (Priority Level)

วิธีการจัดลำดับการทำงานของทาส์กโดย Task Scheduler ที่พบเห็นได้บ่อยคือ รูปแบบที่เรียกว่า Priority-based, Preemptive Scheduling ทาส์กที่พร้อมจะทำงานและมีระดับความสำคัญสูงกว่า จะได้ทำงานเป็นลำดับถัดไป และสามารถเข้ามาแทรกขณะที่ทาส์กอื่นที่กำลังทำงานอยู่แต่มีความสำคัญต่ำกว่าได้

ปัญหา Priority Inversion เป็นอย่างไร

‍‍‍‍‍‍ ‍‍ ‍‍‍‍‍‍ ‍‍‍‍‍‍ ‍‍

ก่อนอื่นจะต้องกำหนดสถานการณ์ดังนี้ ให้การทำงานของโปรแกรมแบ่งออกเป็น 3 ทาส์กที่มีระดับความสำคัญต่างกัน นอกเหนือจากทาสก์ Idle ที่จะต้องมีและจัดการโดย Real-Time Kernel

• Higher Priority Task (HPT) หรือ ทาส์กที่มีความสำคัญระดับสูงกว่า
• Medium Priority Task (MPT) หรือ ทาส์กที่มีความสำคัญระดับกลาง
• Lower Priority Task (LPT) หรือ ทาส์กที่มีความสำคัญระดับต่ำกว่า
• Idle Task หรือ ทาส์กที่มีความสำคัญต่ำสุด และจะต้องทำงานเมื่อไม่มีทาส์กใดเลยพร้อมที่จะทำงาน

นอกจากนั้น มีการกำหนดให้ทาส์ก HPT และ LPT จะต้องมีการใช้งาน Binary Semaphore เหมือนกัน

ช่วงเริ่มต้น ให้ HPT และ MPT อยู่ในสถานะที่ยังไม่พร้อมทำงาน (เช่น Waiting หรือ Blocked) และ LPT อยู่ในสถานะพร้อมทำงาน (Ready) ดังนั้น LPT จะถูกเลือกโดย Task Scheduler ให้ทำงานในสถานะ Running

เมื่อทำงาน LPT จะมีการเข้าถึง Semaphore และทำได้สำเร็จ และก็ทำงานไปเรื่อย ๆ ในสถานะ Running ในเวลาต่อมา HPT พร้อมที่จะทำงาน และอยู่ในสถานะ Ready แล้ว เนื่องจากมีระดับความสำคัญสูงกว่า LPT ทาส์ก HPT จึงได้ทำงานในสถานะ Running และ LPT จะถูกหยุดชั่วคราวอยู่ในสถานะ Ready

ถัดไป HPT พยายามจะเข้าใช้ Semaphore แต่จะทำไม่ได้เนื่องจาก LPT ได้เข้าใช้และถือครองไปก่อนหน้าแล้ว ดังนั้นทาส์ก HPT จึงต้องถูกเปลี่ยนจากสถานะ Running เป็น Blocked และทาส์ก LPT จะได้กลับมาทำงานต่อ (สมมุติว่า ทาส์ก MPT ในช่วงเวลานั้น ยังไม่อยู่ในสถานะ Ready)

ในเวลาต่อมาเมื่อ MPT ได้เปลี่ยนเป็นสถานะ Ready พร้อมจะทำงานบ้างแล้ว และเนื่องจากมีระดับความสำคัญสูงกว่า LPT ทาส์ก MPT จะได้ทำงานในสถานะ Running และทำให้ทาส์ก LPT หยุดรอชั่วคราวในสถานะ Ready (ในขณะที่ทาส์ก HPT ก็ยังไม่พร้อมจะทำงาน เพราะจะต้องรอ Semaphore จากทาส์ก LPT)

เมื่อทาส์ก MPT ทำงานไปได้สักระยะ ก็จบการทำงานและลบตัวเองออกไป (Task Deletion) จากนั้นทาส์ก LPT จะได้กลับมาทำงานต่อ และเมื่อ LPT ทำงานเสร็จแล้ว ก็จะคืน Semaphore แล้วจบการทำงานและลบตัวเองออกไป

สุดท้ายทาส์ก MPT จะได้ทำงานต่อเพราะสามารถเข้าใช้ Semaphore ได้แล้ว และเมื่อจบการทำงาน ก็ลบตัวเองออกไปเช่นกัน จากนั้นเมื่อไม่มีทาส์กใดเหลืออยู่ ทาส์ก Idle ที่จัดการโดย RTOS จะรับหน้าที่ต่อ

ในกรณีนี้จะเห็นได้ว่า HPT ที่มีระดับความสำคัญสูงกว่า จะต้องรอเข้าใช้ Semaphore ต่อจากทาส์ก LPT ที่มีความสำคัญน้อยกว่า และยิ่งไปกว่านั้น HPT จะต้องใช้เวลารอนานขึ้นอีก เพราะว่ามี MPT ซึ่งเป็นทาส์กที่มีความสำคัญน้อยกว่า HPT เข้ามาแทรกระหว่างการทำงานของ LPT ได้ สถานการณ์ในลักษณะนี้ เรียกว่า Priority Inversion (MPT ได้ทำงานก่อน HPT ทั้ง ๆ ที่ลำดับความสำคัญต่ำกว่า)

การแก้ปัญหานี้ สามารถทำได้โดยเปลี่ยนไปใช้ Mutex แทน Binary Semaphore และ Mutex มีการใช้วิธีที่เรียกว่า Priority Inheritance หรือ “การสืบทอดระดับความสำคัญ” (จาก HPT ไปสู่ LPT ชั่วคราว)

ในกรณีนี้ HPT จะต้องรอ Semaphore จาก LPT แต่จะไม่ยอมให้ MPT มาแทรกกลางในระหว่างการทำงานของ LPT เนื่องจากในช่วงเวลานั้น ทาส์ก LPT จะได้รับการยกระดับความสำคัญเท่ากับทาส์ก HPT ดังนั้น MPT จึงไม่สามารถเข้ามาแทรกกลางระหว่างการทำงานของ LPT ได้

เมื่อ LPT ได้ปล่อย Semaphore แล้ว ระดับความสำคัญที่ถูกเพิ่มขึ้นไป ก็จะถูกลดลงมาเป็นปรกติ และ HPT ก็จะได้ทำงานเป็นลำดับถัดไป แล้วตามด้วย MPT

โค้ดสาธิตการทำงาน

‍‍‍‍‍‍ ‍‍ ‍‍‍‍‍‍ ‍‍‍‍‍‍ ‍‍

เราลองมาดูตัวอย่างการเขียนโค้ด Arduino ให้เป็นไปตามสถานการณ์ตามที่ได้กล่าวไป การทำงานของโค้ดนี้ จะใช้ขาเอาต์พุตของ Arduino จำนวน 4 ขา (หมายเลข 5 ถึง 8) เพื่อแสดงสถานะการทำงานของทาส์ก ได้แก่ {IDLE, LPT, MPT, HPT} เรียงตามระดับความสำคัญจากน้อยไปมาก (จาก 0 ถึง 3)

ระยะเวลาในการทำงานของแต่ละทาส์ก (ในช่วงดังกล่าว ถ้าได้ทำงานต่อเนื่อง และไม่ถูกหยุดชั่วคราว) จะสามารถสังเกตเห็นได้ว่า มี Output Level Toggle เกิดขึ้นที่ขาของ I/O ของทาส์กที่เกี่ยวข้อง

• LPT ประมาณ 200 msec
• MPT ประมาณ 100 msec
• HPT ประมาณ 50 msec

#include <Arduino_FreeRTOS.h>
#include <semphr.h>
#define HPT_START_DELAY 
//#define USE_MUTEX
// constants
const uint8_t LED_PINS[] = { 5, 6, 7, 8 };
// global variables
SemaphoreHandle_t semaphore = NULL;
void process( uint8_t id, uint8_t n ) {
   for ( uint8_t i=0; i < n; i++ ) {
      digitalWrite( LED_PINS[id], HIGH );  
      delay(1);
      digitalWrite( LED_PINS[id], LOW );  
   }
}
void LPT_task( void* pvParameters ) {
  int id = (int)pvParameters;
  pinMode( LED_PINS[id], OUTPUT );
  digitalWrite( LED_PINS[id], LOW );
  if (xSemaphoreTake(semaphore, portMAX_DELAY)==pdTRUE) {
    process( id, 200 );
    xSemaphoreGive(semaphore);
  }
  vTaskDelete(NULL); // delete this task
}
void MPT_task( void* pvParameters ) {
  int id = (int)pvParameters;
  pinMode( LED_PINS[id], OUTPUT );
  digitalWrite( LED_PINS[id], LOW );
  vTaskDelay( 1 ); 
  process( id, 100 );
  digitalWrite( LED_PINS[id], LOW );
  vTaskDelete(NULL); // delete this task
}
void HPT_task( void* pvParameters ) {
  int id = (int)pvParameters;
  pinMode( LED_PINS[id], OUTPUT );
  digitalWrite( LED_PINS[id], LOW );
  
#ifdef HPT_START_DELAY
  vTaskDelay( 1 /* tick */ );
#endif
  if (xSemaphoreTake(semaphore, portMAX_DELAY)==pdTRUE) {
    process( id, 50 );
    xSemaphoreGive(semaphore);
  }
  vTaskDelete(NULL); // delete this task
}
void setup() {  
   Serial.begin(115200);  
   Serial.println( "Arduino FreeRTOS Demo..." );
   pinMode( LED_PINS[0], OUTPUT );
   digitalWrite( LED_PINS[0], LOW );
#ifdef USE_MUTEX
   semaphore = xSemaphoreCreateMutex(); 
#else 
   // Create a binary semaphore
   semaphore = xSemaphoreCreateBinary(); 
   xSemaphoreGive( semaphore );
#endif
   
   // Create a lower priority task
   xTaskCreate( LPT_task, "LPT", 100, (void *)1, 1, NULL );
   // Create a medium priority task
   xTaskCreate( MPT_task, "MPT", 100, (void *)2, 2, NULL );
   // Create a higher priority task
   xTaskCreate( HPT_task, "HPT", 100, (void *)3, 3, NULL );
}
void loop() {
  digitalWrite( LED_PINS[0], HIGH );
  delay(1);
  digitalWrite( LED_PINS[0], LOW );
}

ถ้าได้นำโค้ดตัวอย่างไปทดสอบการทำงานโดยใช้บอร์ด Arduino และวัดสัญญาณเอาต์พุต จำนวน 4 ช่อง พร้อมกัน (ช่อง 1–4 ตรงกับขา 5–8 ตามลำดับ) ก็จะสามารถสังเกตพฤติกรรมการทำงานได้ดังนี้

รูปคลื่นสัญญาณ (time/div = 100 msec): เมื่อใช้ Binary Semaphore

รูปคลื่นสัญญาณ (time/div = 100 msec): เมื่อใช้ Mutex (Priority Inheritance)

เมื่อเราได้เปลี่ยนจากการใช้ Binary Semaphore มาเป็น Mutex จะเห็นได้ว่า ระยะเวลาที่ทาส์ก HPT จะต้องรอนั้นลดลง การทำงานของทาส์ก LPT จะไม่ถูกแทรกในเวลาการทำงานโดยทาส์ก MPT

Creative Commons, Attribution-Non Commercial-Share Alike 4.0 International (CC BY-NC-SA 4.0)