# QEMU-FreeRTOS & Scheduler Tracing
###### tags: `learning`
## Outline
:::info
1. Basic steps for environment set-up
- QEMU installation
- Build up RTOS on QEMU emulator
- Tracing Original RTOS scheduler
- Implement FCFS algo
2. Advanced implementations on scheduler
- Multi-level Feedback Queue
- Schedulability Analysis - Checking Deadline Missed
:::
## Basic Steps for Environment Set-upupup
### QEMU installation
- 使用`Ubuntu 20.04`, 首先更新到最新版本
`$ sudo apt update; sudo apt upgrade`
- 安裝開發工具&QEMU emulator
```bash
$ sudo apt install git vim make
gcc gcc-arm-none-eabi gdb gdb-multiarch
make net-tools
qemu-system universal-ctags -y
```
- 可以再為gdb裝個插件`gef`
`$ wget -q -O- https://github.com/hugsy/gef/raw/master/scripts/gef.sh | sh
`
### Build RTOS
- 從github上面把完整的FreeRTOS下載下來
`$ git clone https://github.com/FreeRTOS/FreeRTOS.git`
- 因為有些source code是以submodule的方式存在
因此要再進到`FreeRTOS`的目錄把source code拉下來
`$ cd FreeRTOS; git submodule update --init --recursive`
- 接著進到`FreeRTOS/Demo`
裡面有不同對應不同架構的code跟`Makefile`
這邊選擇模擬`CORTEX_LM3S811_GCC`
- 進到`FreeRTOS/Demo/CORTEX_LM3S811_GCC`目錄底下
因為我們之後要做source code的debug
所以compile時,gcc的指令應該要加上`-g`才能在debug時產生symbol table
因此需要修改`Makefile`中的`CFLAGS`,加上`-g`參數
- 接著就可以`make`進行編譯
編譯成功之後，在會在`gcc`目錄下產生兩個檔案
1. `RTOSDemo.axf` : 這個檔案是給 gdb 看的
2. `RTOSDemo.bin` : 這個檔案是要丟進去`QEMU`執行
- 然後就可以用下面指令用`QEMU`把FreeRTOS的kernel跑起來
```c
$ qemu-system-arm
-machine lm3s811evb //選擇要模擬的機器
-kernel gcc/RTOSDemo.bin //指定kernel image
-s //shorthand for -gdb tcp::1234
-S //freeze CPU at startup (use 'c' to start execution)
-nographic //disable graphical output and redirect serial I/Os to console
```
- 打開另一個terminal
進到`FreeRTOS/Demo/CORTEX_LM3S811_GCC`目錄
此時可以用以下指令連上`QEMU`的gdb server
`$ gdb-multiarch -ex="target remote localhost:1234" gcc/RTOSDemo.axf`
會斷在`startup.c`中
### Tracing Original RTOS scheduler
- FreeRTOS使用<font color='red'>`Prioritized Preemptive Scheduling with Time Slicing`</font>
- `#define configUSE_PREEMPTION 1`
- 定義在`FreeRTOSConfig.h`內
- 代表優先權高的可以馬上插隊
- `#define configUSE_TIME_SLICING 1`
- 定義在`FreeRTOS.h`內
- 相同優先權的task可以共享processing time
- `#define configMAX_PRIORITIES ( 5 )`
- 定義在`FreeRTOSConfig.h`內
- 代表優先權分成5個等級(0-4)
- 一個task為執行的基本單位,可以用`xTaskCreate`函數來建立task
```c=
BaseType_t xTaskCreate( TaskFunction_t pxTaskCode,
const char * const pcName,
const configSTACK_DEPTH_TYPE usStackDepth,
void * const pvParameters,
UBaseType_t uxPriority,
TaskHandle_t * const pxCreatedTask )
```
1. `pxTaskCode`: 每個task都由一個函數組成,並將function name當成參數傳入`xTaskCreate`,一個典型的task function如下
```c=
void ATaskFunc(void *pvParameters)
{
int i = 0;
while(1)
{
//do_sth
}
/* 如果該task需要離開loop結束(ex loop中執行錯誤要跳出來)
* 需要用vTaskDelete來刪除自己而非使用return或自然結束
*/
vTaskDelete(NULL); //NULL是指自己
}
```
2. `pcName`: 這名稱是用來debug時識別用的,task不會用到
3. `usStackDepth`: 每個task會有自己的stack,這個值用來告訴kernel應該要分配多少stack空間(<font color='red'>多少個word</font>)給這個task
4. `pvParameters`: 要傳給這個task的argumemt vector
5. `uxPriority`: 定義這個task的優先權值(0~`configMAX_PRIORITIES`-1)
6. `pxCreatedTask`: 代表這個task的handle,相當於fd的概念
- `xTaskCreate`實作如下
```c=
BaseType_t xTaskCreate(...)
{
TCB_t * pxNewTCB;
BaseType_t xReturn;
#if ( portSTACK_GROWTH > 0 )
{
/* Allocate space for the TCB. Where the memory comes from depends on
* the implementation of the port malloc function and whether or not static
* allocation is being used. */
pxNewTCB = ( TCB_t * ) pvPortMalloc( sizeof( TCB_t ) );
if( pxNewTCB != NULL )
{
/* Allocate space for the stack used by the task being created.
* The base of the stack memory stored in the TCB so the task can
* be deleted later if required. */
pxNewTCB->pxStack = ( StackType_t * ) pvPortMalloc( ( ( ( size_t ) usStackDepth ) * sizeof( StackType_t ) ) ); /*lint !e961 MISRA exception as the casts are only redundant for some ports. */
if( pxNewTCB->pxStack == NULL )
{
/* Could not allocate the stack. Delete the allocated TCB. */
vPortFree( pxNewTCB );
pxNewTCB = NULL;
}
}
}
...
if( pxNewTCB != NULL )
{
#if ( tskSTATIC_AND_DYNAMIC_ALLOCATION_POSSIBLE != 0 ) /*lint !e9029 !e731 Macro has been consolidated for readability reasons. */
{
/* Tasks can be created statically or dynamically, so note this
* task was created dynamically in case it is later deleted. */
pxNewTCB->ucStaticallyAllocated = tskDYNAMICALLY_ALLOCATED_STACK_AND_TCB;
}
#endif /* tskSTATIC_AND_DYNAMIC_ALLOCATION_POSSIBLE */
prvInitialiseNewTask( pxTaskCode, pcName, ( uint32_t ) usStackDepth, pvParameters, uxPriority, pxCreatedTask, pxNewTCB, NULL );
prvAddNewTaskToReadyList( pxNewTCB );
xReturn = pdPASS;
}
else
{
xReturn = errCOULD_NOT_ALLOCATE_REQUIRED_MEMORY;
}
return xReturn;
}
```
- 前面先是為這個task建立了一個`pxNewTCB`,TCB大概結構如下
```c
//task.c
typedef struct tskTaskControlBlock
{
volatile StackType_t * pxTopOfStack //stack ptr
...
ListItem_t xStateListItem; //相同state的task會用這邊串起來
ListItem_t xEventListItem;
UBaseType_t uxPriority; //task的優先值(永遠不會變)
StackType_t * pxStack; //指向stack base
char pcTaskName[...];
...
}tskTCB;
typedef tskTCB TCB_t;
```
- 然後第40行呼叫了`prvInitialiseNewTask`進行TCB的初始化,最後第41行呼叫`prvAddNewTaskToReadyList`把目前task丟到Ready list中等待排程
- `prvAddNewTaskToReadyList`
```c=
static void prvAddNewTaskToReadyList(TCB_t * pxNewTCB)
{
taskENTER_CRITICAL();
{
uxCurrentNumberOfTask++;
if (pxCurrentTCB == NULL) //如果目前沒有其他ready或正在run的task
{
pxCurrentTCB = pxNewTCB;
...
}
else
{
if (xSchedulerRunning == pdFalse) //如果scheduler還未啟動
{
if (pxCurrentTCB->uxPriority <= pxNewTCB->uxPriority) //目前這個task的優先值最高
{
pxCurrentTCB = pxNewTCB;
}
...
}
}
uxTaskNumber++;
...
prvAddTaskToReadyList( pxNewTCB );
}
taskEXIT_CRITICAL();
}
```
- 由此可以知道,要把某個task放回ready list時
相關的function(其他例如`xTaskResume`.`xTaskResumeAll`等等)
應該都會先去檢查他的`tcb->uxPriority`是否比`pxCurrentTCB->uxPriority`大(上面第16行的code)
如果較大表是優先權更高,可以插隊(檢查`configUSE_PREEMITION`的值)
如果沒有則在呼叫`prvAddTaskToReadyList`(第25行)
```c=
//task.c
#define prvAddTaskToReadyList( pxTCB ) \
traceMOVED_TASK_TO_READY_STATE( pxTCB ); \
taskRECORD_READY_PRIORITY( ( pxTCB )->uxPriority ); \
vListInsertEnd( &( pxReadyTasksLists[ ( pxTCB )->uxPriority ] ), &( ( pxTCB )->xStateListItem ) ); \
tracePOST_MOVED_TASK_TO_READY_STATE( pxTCB )
```
- FreeRTOS使用`ready list`去管理準備好要執行的task,而`ready list`的資料儲存方式如下圖
- OS進行context switch(`vTaskSwitchContext`)時會去選出下一個要執行的task
```c=
//vTaskSwitchContext from task.c
if( uxSchedulerSuspended != ( UBaseType_t ) pdFALSE )
{
/* The scheduler is currently suspended - do not allow a context
* switch. */
xYieldPending = pdTRUE;
}
else
{
xYieldPending = pdFALSE;
traceTASK_SWITCHED_OUT(); //switch out current task
...
taskSELECT_HIGHEST_PRIORITY_TASK(); //選出下一個要執行的task
traceTASK_SWITCHED_IN(); //switch in 要執行的task
...
}
}
```
- `taskSELECT_HIGHEST_PRIORITY_TASK`
```c=
#define taskSELECT_HIGHEST_PRIORITY_TASK() \
{ \
UBaseType_t uxTopPriority = uxTopReadyPriority; \
\
/* Find the highest priority queue that contains ready tasks. */ \
while( listLIST_IS_EMPTY( &( pxReadyTasksLists[ uxTopPriority ] ) ) ) \
{ \
configASSERT( uxTopPriority ); \
--uxTopPriority; \
} \
\
/* listGET_OWNER_OF_NEXT_ENTRY indexes through the list, so the tasks of \
* the same priority get an equal share of the processor time. */ \
listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &( pxReadyTasksLists[ uxTopPriority ] ) ); \
uxTopReadyPriority = uxTopPriority; \
} /* taskSELECT_HIGHEST_PRIORITY_TASK */
```
- 建立好task之後,`main`還需要呼叫`vTaskStartScheduler`來啟動scheduler
1. 第6行先建立了一個`idle task`,這個task會在沒有其他task時執行(priority為0)
2. 第23行如果有config timer,通過`xTimerCreateTimerTask`建立timer
3. 如果scheduler建立成功,(第39行)就把`xSchedulerRunning`設為true
4. 第41行,呼叫`xPortStartScheduler`
- 裡面會呼叫`vPortStartFirstTask`來執行第一個task
```c=
void vTaskStartScheduler( void )
{
BaseType_t xReturn;
...
xIdleTaskHandle = xTaskCreateStatic( prvIdleTask,
onfigIDLE_TASK_NAME,
ulIdleTaskStackSize,
( void * ) NULL, /*lint !e961. The cast is not redundant for all compilers. */
portPRIVILEGE_BIT, /* In effect ( tskIDLE_PRIORITY | portPRIVILEGE_BIT ), but tskIDLE_PRIORITY is zero. */
pxIdleTaskStackBuffer,
pxIdleTaskTCBBuffer ); /*lint !e961 MISRA exception, justified as it is not a redundant explicit cast to all supported compilers. */
if( xIdleTaskHandle != NULL )
{
xReturn = pdPASS;
}
else
{
xReturn = pdFAIL;
}
#if ( configUSE_TIMERS == 1 )
{
if( xReturn == pdPASS )
{
xReturn = xTimerCreateTimerTask();
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
#endif /* configUSE_TIMERS */
...
if( xReturn == pdPASS )
{
...
xSchedulerRunning = pdTRUE;
...
if( xPortStartScheduler() != pdFALSE )
}
}
...
```
-
### Implement FCFS algo
- 還要再把`FreeRTOSConfig.h`中的`#define configUSE_PREEMPTION 1`改成`0`
- 最後準備撰寫`main.c`
建立3個task(`A`,`B`,`C`),每個task分別print出`This is the A/B/C function`
並且將priority亂調(`A=4`, `B=1`, `C=3`)
```c=
void vTaskAfunc(void *pvParameters)
{
while(1)
{
printf('This is the A function\n');
break;
}
vTaskDelete(NULL);
}
void vTaskBfunc(void *pvParameters)
{
while(1)
{
printf('This is the B function\n');
break;
}
vTaskDelete(NULL);
}
void vTaskCfunc(void *pvParameters)
{
while(1)
{
printf('This is the C function\n');
break;
}
vTaskDelete(NULL);
}
int main( void )
{
...
xTaskHandle a, b, c;
xTaskCreate(vTaskAfunc, "A", configMINIMAL_STACK_SIZE, NULL, 4, a);
xTaskCreate(vTaskBfunc, "B", configMINIMAL_STACK_SIZE, NULL, 1, b);
xTaskCreate(vTaskCfunc, "C", configMINIMAL_STACK_SIZE, NULL, 3, c);
/* Start the scheduler. */
vTaskStartScheduler();
/* Will only get here if there was insufficient heap to start the
scheduler. */
return 0;
}
```
- 照原本的scheduler,執行順序應該是(`A->C->B`)
FCFS則應該是(`A->B->C`)
Sign in with Wallet
Connect another wallet