---
tags: 嵌入式作業系統分析與實作
---
# Lab4
contributed by <`RusselCK` >
###### tags: `RusselCK`
## 作業要求
### Step 1
* Use Uart to show Free linked list.
* Create a task to call `vPrintFreeList()`.
* Implement your `vPrintFreeList()` in **`heap_2.c`**.
**Example**
### Step 2
* Modifying `prvInsertBlockIntoFreeList` code in **`heap_2.c`** to implement memory merge.
**Example**
## Pinout & Configuration
### 測試準備
* Create six tasks in **`main.c`**
> `RedLEDTask`、`GreenLEDTask`、`Task1`、`Task2`、`Task3`、`PrintTask`
* `Task1`、`Task2`、`Task3` will delete themselves.
* `PrintTask` will call `vPrintFreeList()` to show free list information.
```c
/* USER CODE BEGIN Includes */
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "FreeRTOS.h"
#include "task.h"
/* USER CODE END Includes */
```
```c
/* USER CODE BEGIN */
void RedLEDTask(void const * argument)
{
for(;;)
{
HAL_GPIO_TogglePin(GPIOD, GPIO_PIN_14);
vTaskDelay(500);
}
}
void GreenLEDTask(void const * argument)
{
for(;;)
{
HAL_GPIO_TogglePin(GPIOD, GPIO_PIN_12);
vTaskDelay(1000);
}
}
void Task1(void const * argument)
{
for(;;)
{
vTaskDelete( NULL );
}
}
void Task2(void const * argument)
{
for(;;)
{
vTaskDelete( NULL );
}
}
void Task3(void const * argument)
{
for(;;)
{
vTaskDelete( NULL );
}
}
void PrintTask(void const * argument)
{
for(;;)
{
vPrintFreeList();
vTaskDelay(3000);
}
}
/* USER CODE END */
```
```c
int main(void)
{
...
/* USER CODE BEGIN 2 */
xTaskCreate(RedLEDTask,"RedLEDTask",100,NULL,0,NULL);
xTaskCreate(Task1,"Task1",50,NULL,0,NULL);
xTaskCreate(Task2,"Task2",30,NULL,0,NULL);
xTaskCreate(GreenLEDTask,"GreenLEDTask",130,NULL,0,NULL);
xTaskCreate(Task3,"Task3",40,NULL,0,NULL);
xTaskCreate(PrintTask,"PrintTask",130,NULL,0,NULL);
vTaskStartScheduler();
/* USER CODE END 2 */
...
}
```
## `Heap_2`
### `Heap_2` Introduction
* Uses a **best fit algorithm** and allows previously allocated blocks to be freed.
* Heap (with size `configTOTAL_HEAP_SIZE`) is statically allocated.
* Split (the best-fit) free memory when allocation, but **No merge when free**
* May cause fragmentation
* Suitable for an application that creates and deletes tasks repeatedly, given that the tasks have the same sizes of stack
* TCB and task stacks can be reused repeatedly
### `Heap_2` Free
```c
/* A few bytes might be lost to byte aligning the heap start address. */
#define configADJUSTED_HEAP_SIZE ( configTOTAL_HEAP_SIZE - portBYTE_ALIGNMENT )
```
```c
/* Define the linked list structure. This is used to link free blocks in order
* of their size. */
typedef struct A_BLOCK_LINK
{
struct A_BLOCK_LINK * pxNextFreeBlock; /*<< The next free block in the list. */
size_t xBlockSize; /*<< The size of the free block. */
} BlockLink_t;
/* Create a couple of list links to mark the start and end of the list. */
static BlockLink_t xStart, xEnd;
```
```c
/* Keeps track of the number of free bytes remaining, but says nothing about
* fragmentation. */
static size_t xFreeBytesRemaining = configADJUSTED_HEAP_SIZE;
```
> 僅列出 Lab4 會用到的部分
* FreeList 是一條起點為 `xStart`，終點為 `xEnd` 的一條 linked-list
也就是說，`vPrintFreeList()` 只需要走訪這條 FreeList 並取出我們需要的數值，再透過 UART 輸出即可
## `vPrintFreeList()`
```c
void Uint32ConvertHex(volatile StackType_t pStack, char *charTxScanTaskStack)
{
uint32_t remainder,quotient;
int index = 0;
quotient = pStack;
charTxScanTaskStack[index++] = 48; // ascii number 0
charTxScanTaskStack[index++] = 120; // ascii alphabet x
while (quotient != 0)
{
remainder = quotient & 0xf; // quotient % 16
if (remainder < 10)
charTxScanTaskStack[index++] = '0' + remainder;
else
charTxScanTaskStack[index++] = 55 + remainder; // A = 65;
quotient = quotient >> 4; // quotient / 16
}
/* reverse */
int end = index-1;
for(int reversal = 2;reversal <= end; ++reversal, --end)
{
charTxScanTaskStack[end] ^= charTxScanTaskStack[reversal];
charTxScanTaskStack[reversal] ^= charTxScanTaskStack[end];
charTxScanTaskStack[end] ^= charTxScanTaskStack[reversal];
}
charTxScanTaskStack[index++] = 0;
}
```
```c
void vPrintFreeList( void )
{
/* Output Title */
char *title="StartAddress |heapSTRUCT_SIZE |xBlockSize |EndAddress \n\r";
HAL_UART_Transmit(&huart2,(uint8_t *)title,strlen(title),0xffff);
BlockLink_t* pxIterator = &xStart;
while (pxIterator->pxNextFreeBlock != &xEnd) {
BlockLink_t* current = pxIterator->pxNextFreeBlock;
/* Get current FreeBlock info and tanslate it to char */
char StartAddress[10];
char BlockSize[10];
char HeapStructSize[10];
char EndAddress[10];
memset(StartAddress,'\0',sizeof(StartAddress));
memset(BlockSize,'\0',sizeof(BlockSize));
memset(HeapStructSize, '\0', sizeof(HeapStructSize));
memset(EndAddress,'\0',sizeof(EndAddress));
Uint32ConvertHex((StackType_t) current, StartAddress);
itoa (current->xBlockSize, BlockSize, 10);
itoa (heapSTRUCT_SIZE, HeapStructSize, 10);
StackType_t endaddress = (StackType_t) current + (StackType_t) (current->xBlockSize);
Uint32ConvertHex((StackType_t) endaddress, EndAddress);
/* Output current FreeBlock info */
char Monitor[150];
memset(Monitor,'\0',sizeof(Monitor));
strcat(Monitor,StartAddress); strcat(Monitor, " ");
strcat(Monitor,HeapStructSize); strcat(Monitor," ");
strcat(Monitor,BlockSize); strcat(Monitor," ");
strcat(Monitor,EndAddress); strcat(Monitor," ");
strcat(Monitor, "\n\r");
HAL_UART_Transmit(&huart2,(uint8_t *)Monitor,strlen(Monitor),0xffff);
pxIterator = current;
}
/* Output configADJUSTED_HEAP_SIZE and xFreeBytesRemaining */
char data[50];
char AdjustedHeapSize[10];
char FreeBytesRemaining[10];
memset(data,'\0',sizeof(data));
memset(AdjustedHeapSize,'\0',sizeof(AdjustedHeapSize));
memset(FreeBytesRemaining,'\0',sizeof(FreeBytesRemaining));
itoa (configADJUSTED_HEAP_SIZE, AdjustedHeapSize, 10);
itoa (xFreeBytesRemaining, FreeBytesRemaining, 10);
strcat (data, "configADJUSTED_HEAP_SIZE: ");
strcat (data, AdjustedHeapSize);
strcat (data, " xFreeBytesRemaining: ");
strcat (data, FreeBytesRemaining);
strcat (data, "\n\r");
HAL_UART_Transmit(&huart2,(uint8_t*)data,strlen(data),0xffff);
}
```
## `prvInsertBlockIntoFreeList`
**No Merge**
```c
/*
* Insert a block into the list of free blocks - which is ordered by size of
* the block. Small blocks at the start of the list and large blocks at the end
* of the list.
*/
#define prvInsertBlockIntoFreeList( pxBlockToInsert ) \
{ \
BlockLink_t * pxIterator; \
size_t xBlockSize; \
\
xBlockSize = pxBlockToInsert->xBlockSize; \
\
/* Iterate through the list until a block is found that has a larger size */ \
/* than the block we are inserting. */ \
for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock ) \
{ \
/* There is nothing to do here - just iterate to the correct position. */ \
} \
\
/* Update the list to include the block being inserted in the correct */ \
/* position. */ \
pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock; \
pxIterator->pxNextFreeBlock = pxBlockToInsert; \
}
```
**Implement Memory Merge**
```c
#define prvInsertBlockIntoFreeList( pxBlockToInsert ) \
{ \
BlockLink_t * pxIterator; \
size_t xBlockSize; \
\
xBlockSize = pxBlockToInsert->xBlockSize; \
\
/* merge begin */ \
_Bool merge = 0; \
for (pxIterator = &xStart; pxIterator->pxNextFreeBlock != &xEnd; pxIterator = pxIterator->pxNextFreeBlock) \
{ \
BlockLink_t* tmp = pxIterator->pxNextFreeBlock; \
StackType_t endaddress = (StackType_t) pxBlockToInsert + (StackType_t) xBlockSize; \
StackType_t tmpstartaddress = (StackType_t) tmp; \
if (endaddress == tmpstartaddress) \
{ \
pxBlockToInsert->pxNextFreeBlock = tmp->pxNextFreeBlock; \
pxBlockToInsert->xBlockSize += tmp->xBlockSize; \
pxIterator->pxNextFreeBlock = pxBlockToInsert; \
\
merge = 1; \
break; \
} \
\
StackType_t startaddress = (StackType_t) pxBlockToInsert; \
StackType_t tmpendaddress = (StackType_t) tmp + (StackType_t) (tmp->xBlockSize); \
if (startaddress == tmpendaddress) \
{ \
tmp->xBlockSize += pxBlockToInsert->xBlockSize; \
\
merge = 1; \
break; \
} \
} \
\
if (!merge) { \
/* Iterate through the list until a block is found that has a larger size */ \
/* than the block we are inserting. */ \
for( pxIterator = &xStart; pxIterator->pxNextFreeBlock->xBlockSize < xBlockSize; pxIterator = pxIterator->pxNextFreeBlock ) \
{ \
/* There is nothing to do here - just iterate to the correct position. */ \
} \
\
/* Update the list to include the block being inserted in the correct */ \
/* position. */ \
pxBlockToInsert->pxNextFreeBlock = pxIterator->pxNextFreeBlock; \
pxIterator->pxNextFreeBlock = pxBlockToInsert; \
} \
}
```
Sign in with Wallet
Connect another wallet