OS心得系列 Memory Management --補充

Using memory partitions

圖 F7.5 是一個演示如何使用 uC/OS-II 中的動態分配記憶體功能，以及利用它進行消息傳遞的例子。程式清單 L7.8 是這個例子中兩個 task 的 pseudo-code，其中一些重要程式的標號和圖 F7.5 中括弧內用數位標識的動作是相對應的。

第一個 task 讀取並檢查類比輸入量的值 (如氣壓、溫度、電壓等) ，如果其超過了一定的臨界值，就向第二個 task 發送一個消息。該消息中含有時間資訊、出錯的通道號和錯誤程式等可以想像的任何可能的資訊。

錯誤處理程式是該例子的中心。任何 task 、 ISR 都可以向該 task 發送出錯消息。錯誤處理程式則負責在顯示設備上顯示出錯資訊，在磁片上登記出錯記錄，或者啟動另一個 task 對錯誤進行糾正等



Figure 7.5 Using dynamic memory allocation



程式清單 L7.8 Scanning analog inputs and reporting errors

AnalogInputTask()
{
for (;;) {
for (所有的類比量都有輸入) {
讀入類比量輸入值; (1)

if (類比量超過臨界值) {
得到一個記憶體塊; (2)
得到當前系統時間 (以時鐘節拍為單位); (3)
將下列各項存入記憶體塊: (4)
系統時間 (時間戳記);
超過臨界值的通道號;
錯誤程式;
錯誤等級;
等.
向錯誤佇列發送錯誤消息; (5)
(一個指向包含上述各項的記憶體塊的指標)
}
}
延時 task, 直到要再次對類比量進行採樣時為止;
}
}


ErrorHandlerTask()
{
for (;;) {
等待錯誤佇列的消息; (6)
(得到指向包含有關錯誤資料的記憶體塊的指標)
讀入消息, 並根據消息的內容執行相應的操作; (7)
將記憶體塊放回到相應的記憶體分割區中; (8)
}
}

OS心得系列Memory Control Blocks--PART 2

Obtaining a memory block, OSMemGet()

應用程式可以呼叫 OSMemGet() 函式從已經建立的記憶體分割區中申請一個記憶體塊。該函式的唯一參數是指向特定記憶體分割區的指標，該指標是在建立記憶體分割區時，由 OSMemCreate() 函式所返回。顯然的，應用程式必須知道記憶體塊的大小，並且在使用時不能超過該容量。例如，如果一個記憶體分割區內的記憶體塊為 32 位元組，那麼，應用程式最多只能使用該記憶體塊中的 32 位元組。當應用程式不再使用這個記憶體塊後，必須及時把它釋放，重新放回相對應的記憶體分割區中 [見 OSMemPut()]。

程式清單 L7.4 是 OSMemGet() 函式的程式碼。參數中的指標pmem 指向使用者希望從其中分配記憶體塊的記憶體分割區[L7.4(1)] 。OSMemGet() 首先檢查記憶體分割區中是否有未使用的的記憶體塊[L7.4(2)] 。如果有，從未使用的記憶體塊鏈表中刪除第一個記憶體塊[L7.4(3)] ，並對未使用的記憶體塊鏈表作相應的修改 [L7.4(4)] 。這包括將鏈表頭指標後移一個元素和未使用的記憶體塊數減1[L7.4(5)] 。最後，返回指向被分配記憶體塊的指標[L7.4(6)] 。

程式清單 L7.4 OSMemGet()


void *OSMemGet (OS_MEM *pmem, INT8U *err) (1)
{
void *pblk;


OS_ENTER_CRITICAL();

if (pmem->OSMemNFree > 0) { (2)
pblk = pmem->OSMemFreeList; (3)
pmem->OSMemFreeList = *(void **) pblk; (4)
pmem->OSMemNFree--; (5)

OS_EXIT_CRITICAL();

*err = OS_NO_ERR;
return (pblk); (6)

} else {
OS_EXIT_CRITICAL();

*err = OS_MEM_NO_FREE_BLKS;
return ((void *) 0);
}
}


值得注意的是，使用者可以在 ISR 中呼叫 OSMemGet()，因為在暫時沒有記憶體塊可用的情況下，OSMemGet() 不會等待，而是馬上返回 NULL 指標。

Returning a memory block, OSMemPut()

當使用者應用程式不再使用一個記憶體塊時，必須及時地把它釋放並放回到原本的記憶體分割區中。這個操作由 OSMemPut() 函式完成。必須注意的是，OSMemPut() 並不知道一個記憶體塊是屬於哪個記憶體分割區的。例如，使用者的 task 從一個包含 32 位元組記憶體塊的分區中分配了一個記憶體塊，用完後，把它返還給了一個包含 120 位元組記憶體塊的記憶體分割區。當使用者應用程式下一次申請 120 位元組分區中的一個記憶體塊時，它會只得到 32 位元組的可用空間，其他 88 位元組屬於其他的 task，這就有可能使系統崩潰。

程式清單 L7.5 是 OSMemPut() 函式的程式碼。它的第一個參數 pmem 是指向 MCB 的指標，也即記憶體塊屬於的記憶體分割區 [L7.5(1)]。OSMemPut() 首先檢查記憶體分割區是否已滿 [L7.5(2)]。如果已滿，說明系統在分配和釋放記憶體時出現了錯誤。如果未滿，要釋放的記憶體塊被插入到該分區的未使用的 MCB link list 中 [L7.5(3)]。最後，將分區中未使用的記憶體塊總數加 1 [L7.5(4)]。

程式清單 L7.5 OSMemPut()


INT8U OSMemPut (OS_MEM *pmem, void *pblk) (1)
{
OS_ENTER_CRITICAL();

if (pmem->OSMemNFree >= pmem->OSMemNBlks) { (2)
OS_EXIT_CRITICAL();
return (OS_MEM_FULL);
}

*(void **) pblk = pmem->OSMemFreeList; (3)
pmem->OSMemFreeList = pblk;
pmem->OSMemNFree++; (4)

OS_EXIT_CRITICAL();
return (OS_NO_ERR);
}


Obtaining status about memory partition, OSMemQuery()

在 uC/OS-II 中，可以使用 OSMemQuery() 函式來查詢一個特定記憶體分割區的有關消息。透過該函式可以知道特定記憶體分割區中記憶體塊的大小、可用記憶體塊數和正在使用的記憶體塊數等資訊。所有這些資訊都放在一個叫 OS_MEM_DATA 的資料結構中，如程式清單 L7.6。

程式清單 L7.6 Data structure used to obtain status from a partition


typedef struct {
void *OSAddr; /* 指向記憶體分割區第一個位址的指標 */
void *OSFreeList; /* 指向未使用的 MCB link list 第一個位址的指標 */
INT32U OSBlkSize; /* 每個記憶體塊所含的位元組數 */
INT32U OSNBlks; /* 記憶體分割區總的記憶體塊數 */
INT32U OSNFree; /* 未使用的記憶體塊總數 */
INT32U OSNUsed; /* 正在使用的記憶體塊總數 */
} OS_MEM_DATA;


程式清單 L7.7 是 OSMemQuery() 函式的程式碼，它將指定記憶體分割區的資訊複製到 OS_MEM_DATA 定義的相對應變數中。在此之前，程式首先禁止了外部中斷，防止複製過程中某些變數值被修改 [L7.7(1)]。由於正在使用的記憶體塊數是由 OS_MEM_DATA 中的局部變數計算得到的，所以，可以放在 critical section 的外面。

程式清單 L7.7 OSMemQuery()


INT8U OSMemQuery (OS_MEM *pmem, OS_MEM_DATA *pdata)
{
OS_ENTER_CRITICAL();

pdata->OSAddr = pmem->OSMemAddr; (1)
pdata->OSFreeList = pmem->OSMemFreeList;
pdata->OSBlkSize = pmem->OSMemBlkSize;
pdata->OSNBlks = pmem->OSMemNBlks;
pdata->OSNFree = pmem->OSMemNFree;

OS_EXIT_CRITICAL();

pdata->OSNUsed = pdata->OSNBlks - pdata->OSNFree; (2)
return (OS_NO_ERR);
}

OS心得系列Memory Control Blocks--PART 1

為了便於記憶體的管理，在 uC/OS-II 中使用記憶體控制塊 (Memory Control Blocks, MCB) 的資料結構來跟蹤每一個記憶體分割區，系統中的每個記憶體分割區都有它自己的 MCB。程式清單 L7.1 是 memory control blocks (MCB) 的定義。

程式清單 L7.1 Memory Control Block (MCB) data structure
typedef struct {
void *OSMemAddr;
void *OSMemFreeList;
INT32U OSMemBlkSize;
INT32U OSMemNBlks;
INT32U OSMemNFree;
} OS_MEM;

.OSMemAddr 是指向記憶體分割區起始位址的指標。它在建立記憶體分割區 [見 OSMemCreate()] 時被初始化，在此之後就不能更改了。

.OSMemFreeList 是指向下一個未使用的記憶體控制塊或者下一個未使用的的記憶體塊的指標，具體含義要根據該記憶體分割區是否已經建立來決定。

.OSMemBlkSize 是記憶體分割區中記憶體塊的大小，是使用者建立該記憶體分割區時指定的。

.OSMemNBlks 是記憶體分割區中總的記憶體塊數量，也是使用者建立該記憶體分割區時指定的。

.OSMemNFree 是記憶體分割區中當前可以得未使用的記憶體塊數量。

如果要在 uC/OS-II 中使用記憶體管理，需要在 OS_CFG.H 檔案中將常數定義 OS_MEM_EN 設為 1。這樣 uC/OS-II 在啟動時就會對 memory manager 進行初始化 [由 OSInit() 呼叫 OSMemInit() 來實現]。該初始化主要建立一個如圖 F7.3 所示的 MCB link list，其中的常數定義 OS_MAX_MEM_PART (見檔案 OS_CFG.H) 定義了最大的記憶體分割區數，該常數值至少要為 2。



Creating a partition, OSMemCreate()

在使用一個記憶體分割區之前，必須先建立該記憶體分割區。這個操作可以透過呼叫 OSMemCreate() 函式來完成。程式清單 L7.2 說明了如何建立一個含有 100 個記憶體塊、每個記憶體塊 32 位元組的記憶體分割區。

程式清單 L7.2 Creating a memory partition


OS_MEM *CommTxBuf;
INT8U CommTxPart[100][32];

void main (void)
{
INT8U err;


OSInit();
.
.
CommTxBuf = OSMemCreate(CommTxPart, 100, 32, &err);
.
.
OSStart();
}

程式清單 L7.3 是 OSMemCreate() 函式的程式碼。該函式共有 4 個參數：記憶體分割區的起始位址、分區內的記憶體塊總塊數、每個記憶體塊的位元組數和一個指向錯誤資訊程式的指標。如果 OSMemCreate() 操作失敗，它將返回一個 NULL 指標。否則，它將返回一個指向記憶體控制塊的指標。對記憶體管理的其他操作，像 OSMemGet() ，OSMemPut()，OSMemQuery() 函式等，都需要透過該指標進行。

每個記憶體分割區必須含有至少兩個記憶體塊 [L7.3(1)]，每個記憶體塊至少為一個指標的大小，因為同一分區中的所有未使用的記憶體塊是由指標串聯起來的 [L7.3(2)]。接著，OSMemCreate() 從系統中的未使用的 MCB list 中取得一個 MCB [L7.3(3)]，該 MCB 包含相對應記憶體分割區的程式執行期的資訊。 OSMemCreate() 必須在有未使用的 MCB 可用的情況下才能建立一個記憶體分割區 [L7.3(4)]。在上述條件均得到滿足時，所要建立的記憶體分割區內的所有記憶體塊被鏈結成一個單向 link list [L7.3(5)]。然後，在相對應的 MCB 中填寫相對應的資訊 [L7.3(6)]。完成上述各動作後，OSMemCreate() 返回指向該記憶體塊的指標。使該指標在以後對記憶體塊的操作中使用[L7.3(6)] 。


程式清單 L7.3 OSMemCreate()
OS_MEM *OSMemCreate (void *addr, INT32U nblks, INT32U blksize, INT8U *err)
{
OS_MEM *pmem;
INT8U *pblk;
void **plink;
INT32U i;


if (nblks < 2) { (1)
*err = OS_MEM_INVALID_BLKS;
return ((OS_MEM *) 0);
}

if (blksize < sizeof(void *)) { (2)
*err = OS_MEM_INVALID_SIZE;
return ((OS_MEM *) 0);
}

OS_ENTER_CRITICAL();

pmem = OSMemFreeList; (3)

if (OSMemFreeList != (OS_MEM *) 0) {
OSMemFreeList = (OS_MEM *) OSMemFreeList->OSMemFreeList;
}

OS_EXIT_CRITICAL();

if (pmem == (OS_MEM *) 0) { (4)
*err = OS_MEM_INVALID_PART;
return ((OS_MEM *) 0);
}

plink = (void **) addr; (5)
pblk = (INT8U *) addr + blksize;

for (i = 0; i < (nblks - 1); i++) {
*plink = (void *) pblk;
plink = (void **) pblk;
pblk = pblk + blksize;
}

*plink = (void *) 0;

OS_ENTER_CRITICAL();

pmem->OSMemAddr = addr; (6)
pmem->OSMemFreeList = addr;
pmem->OSMemNFree = nblks;
pmem->OSMemNBlks = nblks;
pmem->OSMemBlkSize = blksize;

OS_EXIT_CRITICAL();

*err = OS_NO_ERR;
return (pmem); (7)
}


圖 F7.4 是 OSMemCreate() 函式執行完成後，MCB 及對應的記憶體分割區和分割區內的記憶體塊之間的關係。在程式執行期間，經過多次的記憶體分配和釋放後，同一分區內的各記憶體塊之間的鏈結順序會發生很大的變化。

OS心得系列 Memory Management

在ANSIC 中可以用 malloc() 和 free() 兩個函式動態地分配記憶體和釋放記憶體是大部分學習資工的人都知道的事情。但是，在嵌入式即時操作系統中，多次這樣做會把原來很大的一塊連續記憶體區域，逐漸地分割成許多非常小而且彼此又不相鄰的記憶體區域，也就是記憶體破碎(fragment)。由於這些碎片的大量存在，使得程式到後來連非常小的記憶體也分配不到。我們曾在前面的 Task Stack 提過，用 malloc() 函式來分配堆疊時，曾經討論過記憶體破碎的問題。另外，由於記憶體管理演算法的原因，malloc() 和 free() 函式執行時間是不確定的。

而在uC/OS-II 中，kernel 把連續的大塊記憶體按分區來管理。每個分區中包含有整數個大小相同的記憶體塊，如同圖 F7.1。利用這種機制，uC/OS-II 對 malloc() 和 free() 函式進行了改變，使得它們可以分配和釋放固定大小的記憶體塊。這樣一來，malloc() 和 free() 函式的執行時間也是固定的了。


如圖 F7.2，在一個系統中可以有多個記憶體分割區。這樣，使用者的應用程式就可以從不同的記憶體分割區中得到不同大小的記憶體塊。但是，特定的記憶體塊在釋放時必須重新放回它以前所屬於的記憶體分割區。顯然，採用這樣的記憶體管理演算法，上面的記憶體破碎問題就得到了解決。

OS心得系列 Critical Section --補充

知道了Critical Section的概念後，那要如何實際解決它的問題呢?可以用下面的程式碼來實作之:

a. Solution using TestAndSet:

while (true)
{
while ( TestAndSet (&lock ))
; // do nothing

// critical section

lock = FALSE;

// remainder section
}

b. Solution using Swap:

while (true)
{
key = TRUE;
while ( key == TRUE)
Swap (&lock, &key );

// critical section

lock = FALSE;

// remainder section
}

然而此類方法通常用在多CPU之系統中，若用在單CPU之系統中，則可能會很浪費CPU time，而顯得不適當，因為假如某個process執行while(TestAndSet(&lock))時，因lock為true而在此while作迴路等待時，一定會等待耗盡其所分配的CPU time slice(因為此時必定是有其他process在critical section中鎖住lock)，直到目前正在critical section中之process搶到CPU繼續執行，離開critical section後，此process才有機會結束等待。

再來看看用另一方法，在單CPU系統中，其實還可以可利用Disable_Interrupt及Enable_Interrupt指令作為控制critical section執行之機制，如下圖所示：




當process 1執行Disable_Interrupt指令後，此CPU暫時不接受Interrupt(中斷)之請求，process 1之執行權就不會被別的process搶走，因此可保証process 1可一口氣執行完其critical section;而此解法只能適用在單CPU系統，在多CPU系統中，process 1執行Disable_Interrupt指令只是暫時阻斷執行process 1之CPU的中斷回應，可能另外一個CPU會在process 1執行其critical section時也同時執行process 2之critical section，再者，用此方法時，若critical section執行時間很長，須考慮是否系統會有中斷被遺失的問題。(例如，網路卡以中斷方式告知CPU封包的來臨，若中斷被阻斷太長，可能造成網路卡要求CPU之中斷訊息遺失，意味著網路卡所收的封包無法即時被CPU傳送到Memory)。

最後提供二張圖片來幫助了解Critical Section:

OS心得系列 Critical Section

Critical Section這一詞也是從我修習作業系統這門課後，常常聽到的名詞之一，有此可見它的重要性也是不容忽視的，首先要介紹他的概念:

到底什麼是Critical Section?它是指當多個thread可能同時存取的記憶體、變數或函數的情況，它的作用是用於在多執行緒環境中保護資源，而通常這種要受保護的程式區段稱為 Critical Section 。

至於為什麼要保護這個區段呢呢？因為在程式裡有可能有兩個 thread (可看成一個小小的function)同時存取一個global variable(全域變數)(或函數)，這時後，因為程式的需要，thread 不想被其他程式中斷(不被其他thread插入影響)，所以必須要一口起執行完畢，而該需要一口氣執行完的程式區段，所以需要設定
Critical Section,以保護目前執行的thread不被其他thread影響。

因此可以歸類出以下重點:

1.Critical Section是一程式區段, 而這個程式區段必須擁有某共用資源的權限才能執。

2.可以放心的執行 Critical Section 的程式碼,絕不會有其他的 thread 同時執行你所在的code。

3.thread 會被 preempt 換其他的thread 執行, 但是想要進入 Critical Section 的thread 是不會被 排進schedule裡。

4.系統不保證進入Critical Section thread 的順序,但OS保證公平對待所有要進入的thread。

另外，還有一個值得注意的地方是，若要控制critical section執行之機制必須滿足下列三個要求：

(1)Mutual exclusion：不允許兩個以上的process同時在對應的critical section中執行。

(2)Progress：若沒有process在對應的critical section中執行，則控制的機制不能阻擋請求進入critical section之process進入critical section。

(3)Bounded waiting：控制機制必須使等待進入critical section之process在有限時間內進入critical section。

如果都無法同時滿足三個的需求，那Critical Section也無法發揮它的效用了。

OS心得系列 Process & Thread--PART 3

緊接著來探討Thread，我們可以把一個thread看成是一個控制流程，再引入thread觀念後，就可能需要重新修改傳統process之觀念;一個傳統process只代表一個控制流程，也就是一個傳統process中只存在一個thread，而引入thread觀念後，一個process中可存在多個threads。

Thread是執行的單元，而process是資源配置的單元，支援thread之作業系統核心分配一個CPU給一個thread，再分配一個記憶體空間給一個process，接著分配I/O及檔案資源給一個process。

而在同一個process中的所有threads則共享這些記憶體空間及資源，如下圖(左邊)所示，傳統的process為single-threaded process;一個process擁有一套registers、stack、code、data及所開的檔案。

在引入thread觀念後，一個process可以有多個thread，每個thread都有各自的register與stack，如下圖(右邊)所示，但code、data、files則是配置給一個process且供其中之threads共用。



了解Thread的概念後，接著來看看它還具備了什麼用途:

Thread常被運用在網路伺服器之設計上，以Web server為例，Web server常需服務大量用戶請求，若以一個傳統single-thread的process來實現web server，當web server在服務某個請求而需讀取網頁之檔案時，可能會導致web server進入等待狀態(假如web server用synchronous I/O讀檔案)。

此時雖有許多用戶等待服務，web server卻也不能去服務，導致用戶較長的等待時間，Web server之服務效能不佳，如下圖(1)。

若web server以create_process方式，在每次有用戶請求時產生一個process以服務一個用戶，此方法可以使web server同時服務多個用戶，但create_process ,及 切換prcoess執行之overheads很高，因此不見得有好效能，如下圖(2)。

若web server以create_thread方式，在每次有用戶請求時產生一個thread以服務一個用戶，此方法可以使web server的服務效能增加，因create_thread ,及在同一個process中切換thread執行之overheads較低，如下圖(3)。





由此可知，現在thread在應用上多採用多工的處理方式，其實不僅僅是thread而已，目前許多與電腦相關的概念也大多採取多工的方法，雖然可能會有一些未知的錯誤情況產生，不過技術的進步相信也同時能夠對其作良好的改進，達到處理效能極至的境界。