上老師的課也快一整學年了，上學期的OS和這學期的OSII。
老實說， 上學期結束時，我覺得我什麼東西都沒學到，
腦中只有考試前硬背的一些理論。
每次上課時，即便我很認真的抄筆記，我可能還是無法理解意義。
導致後來連筆記都不想抄了，因為抄了回家還是看不懂。
我一直很疑惑到底為什麼會這樣，
或許是我課堂上理解能力和記憶能力太差吧。
原先，我一直認為是老師的授課方式不適合我，
因為我似乎都找不太到，老師每次上課的主題，
或許是因為說話習慣吧，讓我總是找不到重點。
直到這次OSII期末考前，我開始看錄影檔，雖然我知道錄影檔有缺，
但我還是只有這樣做，想說看多少算多少。
在期中考前大概看完4.5.6.7這些章節，也做了筆記。
發現，原來我要看錄影檔才抓的到重點，
因為當我沒抄到老師講某幾句話時，可以倒轉。
當然，因為我沒看完，所以期末考，後面印象都蠻模糊的，
但是前面第一大題就比較有信心了，因為那剛好是我看過的。
原本，是不喜歡老師的授課方式的，
因為感覺沒有整體的架構，會不知道剛剛理解的東西是要做什麼的。
但我現在發現，原來我感覺不到的架構，都會在老師說的話當中，
但老師這種話可能都只會講一遍。
所以我個人覺得，錄影檔真的很重要!!!
希望老師可以讓以後的錄影檔完整一點!!!
2009年6月18日 星期四
Memory Management II
※ uCOSII
1. 記憶體管理機制比較像slab(簡化版的slab)
2. 沒有buddy system，因為uCOSII沒有MMU，沒有辦法管理MMU
所以不需要buddy system。
※
系統剛啟動時，以靜態分配的方式，將記憶體分成很多partition，
每個partition有多少塊，有多大，都是一開機完就分配好的，
因為uCOSII是real time的OS，是個embedded OS，所以可以做這個假設。
※
其記憶體分配機制很有效率，time comparsity是BigO(1)，
slab幾乎是BigO(1)，有時會比較大。
利用getmem指名從哪裡拿記憶體，大小不能指定。
1. 記憶體管理機制比較像slab(簡化版的slab)
2. 沒有buddy system，因為uCOSII沒有MMU，沒有辦法管理MMU
所以不需要buddy system。
※
系統剛啟動時，以靜態分配的方式，將記憶體分成很多partition，
每個partition有多少塊，有多大，都是一開機完就分配好的，
因為uCOSII是real time的OS，是個embedded OS，所以可以做這個假設。
※
其記憶體分配機制很有效率，time comparsity是BigO(1)，
slab幾乎是BigO(1)，有時會比較大。
利用getmem指名從哪裡拿記憶體，大小不能指定。
Memory Management I
※ linux記憶體管理
1. kernel管理機制：負責配置給AP記憶體，一部分kernel主動配置，
一部份是kernel被告知有人需要多少(ex:malloc)。
使用slab和buddy system
2. user space管理機制
※ KCP：一個從頭執行到尾的動作，不管被誰驅動(一群涵式的呼叫與回傳)
※ Buddy system：最小的單位是page。
※ Slab：單位為物件，大小不定。
※
1. KCP最主要跟slab要記憶體
2. slab跟buddy system要記憶體
3. 系統裡面會有很多slab，原則上只會有一個buddy system
4. user space的管理機制不可能用slab管理記憶體，
因為硬體幫助管理記憶體最小的限制單位是page，但slab大小不定，
因此以buddy system幫助user space管理。
1. kernel管理機制：負責配置給AP記憶體，一部分kernel主動配置，
一部份是kernel被告知有人需要多少(ex:malloc)。
使用slab和buddy system
2. user space管理機制
※ KCP：一個從頭執行到尾的動作，不管被誰驅動(一群涵式的呼叫與回傳)
※ Buddy system：最小的單位是page。
※ Slab：單位為物件，大小不定。
※
1. KCP最主要跟slab要記憶體
2. slab跟buddy system要記憶體
3. 系統裡面會有很多slab，原則上只會有一個buddy system
4. user space的管理機制不可能用slab管理記憶體，
因為硬體幫助管理記憶體最小的限制單位是page，但slab大小不定，
因此以buddy system幫助user space管理。
2009年6月16日 星期二
chapter 7
※ ISR只能做 non-blocking
※ OSSemCtreate(cnt)
1. prevent -> OSEventCnt = cnt;
一次最多有cnt個人能進去critical section
2. struct第一個欄位記錄使用函式的種類
3. OS_EventWaitListInit() 把waitingQ全部清空為0
※ OSSemDel()
1. semaphore通常拿來做IPC使用
2. opt = OS_DEL_NO_PEND
有人在semaphore的waitingQ裡面，不能刪除semaphore
3. opt = OS_DEL_ALWAYS
不管有沒有人在waiting裡面，都做刪除
4. 檢查OSEventGrp來判斷裡面有沒有人
5. 將waitingQ中所有的task搬回readyQ，
否則這些task將永遠不會執行。
6. OSEventTaskRdy()每呼叫一次，就會有一個task進入readyQ，
一直呼叫到waitingQ都變0
※ 系統裡面可以有多個semaphore，
每個semaphore都會有自己的waitingQ。
系統裡面有幾各CPU就有幾各readyQm。
※ OSSemPend() lock
1. A想進入critical section，做OSSemPend()lock，
檢查OSEventCnt是否大於0，成立-1，回傳。
2. B已經進入critical section，A想進入critical section，
做OSSemPend()lock，檢查OSEventCnt，沒有大於0，
此時A將自己從readyQ擺到waitingQ，呼叫OS_Sched()。
B離開critical section，做OSSemPost()unlock，
使用EventTaskRdy()叫醒想進入critical section的A，
此時，A與B兩個都是ready的，這時看schedule決定誰執行。
若是A的priority較高，A去看自己的status是ready的，進入critical section。
3. 和2相同，多了timeout的條件。
A可能會被kernel的timer或是B其中一個叫醒。
※ OSSemCtreate(cnt)
1. prevent -> OSEventCnt = cnt;
一次最多有cnt個人能進去critical section
2. struct第一個欄位記錄使用函式的種類
3. OS_EventWaitListInit() 把waitingQ全部清空為0
※ OSSemDel()
1. semaphore通常拿來做IPC使用
2. opt = OS_DEL_NO_PEND
有人在semaphore的waitingQ裡面，不能刪除semaphore
3. opt = OS_DEL_ALWAYS
不管有沒有人在waiting裡面，都做刪除
4. 檢查OSEventGrp來判斷裡面有沒有人
5. 將waitingQ中所有的task搬回readyQ，
否則這些task將永遠不會執行。
6. OSEventTaskRdy()每呼叫一次，就會有一個task進入readyQ，
一直呼叫到waitingQ都變0
※ 系統裡面可以有多個semaphore，
每個semaphore都會有自己的waitingQ。
系統裡面有幾各CPU就有幾各readyQm。
※ OSSemPend() lock
1. A想進入critical section，做OSSemPend()lock，
檢查OSEventCnt是否大於0，成立-1，回傳。
2. B已經進入critical section，A想進入critical section，
做OSSemPend()lock，檢查OSEventCnt，沒有大於0，
此時A將自己從readyQ擺到waitingQ，呼叫OS_Sched()。
B離開critical section，做OSSemPost()unlock，
使用EventTaskRdy()叫醒想進入critical section的A，
此時，A與B兩個都是ready的，這時看schedule決定誰執行。
若是A的priority較高，A去看自己的status是ready的，進入critical section。
3. 和2相同，多了timeout的條件。
A可能會被kernel的timer或是B其中一個叫醒。
chapter 6(cont)
※ OS_EventWaitListInit()
將.OSEventGrp和OSEventTbl都填0
※ loop unrolling
※ OS_EnentTaskRdy() 執行XXXPost時就會呼叫這個
從waitingQ裡找出優先權最高的task，放到readyQ裡面
※
y = OSUnMapTbl[prevent->OSEnentGrp];
bity = OSMapTbl[y];
x = OSUnMapTbl[prevent->OSEventTbl[y]];
bitx = OSMapTbl[x];
prio = (INT8U)((y<<3)+x);
從waitingQ裡找出最高優先權的task，將之移出waitingQ。
演算法和原本readyQ是一樣的。
ptcb->OSTCBDly = 0
塞0進去，因為已經等到了，所以設為0，否則之後會再叫醒一次
ptcb->OSTCBStat &= ~msk
令task變為ready
※ OS_EventTaskRdy() 總結
從waitingQ裡找出最高優先權的task，從waitingQ搬到readyQ。
然後在TCB裡做必要的修改。
將.OSEventGrp和OSEventTbl都填0
※ loop unrolling
※ OS_EnentTaskRdy() 執行XXXPost時就會呼叫這個
從waitingQ裡找出優先權最高的task，放到readyQ裡面
※
y = OSUnMapTbl[prevent->OSEnentGrp];
bity = OSMapTbl[y];
x = OSUnMapTbl[prevent->OSEventTbl[y]];
bitx = OSMapTbl[x];
prio = (INT8U)((y<<3)+x);
從waitingQ裡找出最高優先權的task，將之移出waitingQ。
演算法和原本readyQ是一樣的。
ptcb->OSTCBDly = 0
塞0進去，因為已經等到了，所以設為0，否則之後會再叫醒一次
ptcb->OSTCBStat &= ~msk
令task變為ready
※ OS_EventTaskRdy() 總結
從waitingQ裡找出最高優先權的task，從waitingQ搬到readyQ。
然後在TCB裡做必要的修改。
chapter 6
※ Event Control Block實現waitingQ
※
Semaphore
Mutual Exclusion
Message Mainbox
Message Queue
以上這幾種機制皆會使用到waitingQ
※ ECB的資料結構和readyQ差不多
※ ECB的演算法和function設計來和readyQ之間做一些互動
※
OSXxxCreate
OSXxxDel
OSXxxPend -> wait lock，等到為止
OSXxxAccept -> 等不到就走(non-blocking)
OSXxxPost -> unlock signal
OSXxxQuery -> 把整個ECB複製一份，memcpy加上critical section。
※
1. Block System call & Nonblocking System call
ex.
kmalloc
vmalloc
2. Asynchronous System call(A I/O)
用thread可達到同樣效果，但context switch的overhead太大
※ ECB
1. 只有task可以做等待的動作，ISR不能。
2. ISR可以把task從waitingQ中拉到readyQ
3. task什麼事都可以做，ISR不能做wait的動作
4. 可以多個task去wait同一個resource
5. 所有的function都沒有處理同步的問題，所以呼叫的人要自己處理
※ ECB資料結構
1. .OSEnentType ECB的種類0.1.2....
2. .OSEventGrp 實現waitingQ，剛開始都填0
3. .OSEventCnt 取決於1
4. .OSEventPtr 取決於1
5. waitingQ，剛開始都填0
※ ECB Functions
1. OS_EventWaitListInit() 給ECB初始值
2. OS_EventTaskRdy() 呼叫signal或post時會使用到，
把task從waitingQ搬到readyQ，一定是搬最高優先權的task
3. OS_EventTaskWait()
把某個task放到waitingQ裡面
4. OS_EventTO() to = timeout
設定最多等多久，時間到了就直接設為ready
※
Semaphore
Mutual Exclusion
Message Mainbox
Message Queue
以上這幾種機制皆會使用到waitingQ
※ ECB的資料結構和readyQ差不多
※ ECB的演算法和function設計來和readyQ之間做一些互動
※
OSXxxCreate
OSXxxDel
OSXxxPend -> wait lock，等到為止
OSXxxAccept -> 等不到就走(non-blocking)
OSXxxPost -> unlock signal
OSXxxQuery -> 把整個ECB複製一份，memcpy加上critical section。
※
1. Block System call & Nonblocking System call
ex.
kmalloc
vmalloc
2. Asynchronous System call(A I/O)
用thread可達到同樣效果，但context switch的overhead太大
※ ECB
1. 只有task可以做等待的動作，ISR不能。
2. ISR可以把task從waitingQ中拉到readyQ
3. task什麼事都可以做，ISR不能做wait的動作
4. 可以多個task去wait同一個resource
5. 所有的function都沒有處理同步的問題，所以呼叫的人要自己處理
※ ECB資料結構
1. .OSEnentType ECB的種類0.1.2....
2. .OSEventGrp 實現waitingQ，剛開始都填0
3. .OSEventCnt 取決於1
4. .OSEventPtr 取決於1
5. waitingQ，剛開始都填0
※ ECB Functions
1. OS_EventWaitListInit() 給ECB初始值
2. OS_EventTaskRdy() 呼叫signal或post時會使用到，
把task從waitingQ搬到readyQ，一定是搬最高優先權的task
3. OS_EventTaskWait()
把某個task放到waitingQ裡面
4. OS_EventTO() to = timeout
設定最多等多久，時間到了就直接設為ready
chapter 5(cont)
※ OSTimeTick()
1. OSTCBList會把正在執行的task串成一列，
最後一個task一定是idle task，因為在新增刪除task時一定是從頭，
系統裡面第一個task又是idle task，造成idle task放最後一個。
2. 因此可以從頭往下找，找到idle task為止，到idle task就不執行，
因為idle task本身不會呼叫sleep，永遠都是ready。
3. (不太重要)
去判斷每個TCB裡的欄位Dly的值，數字代表要等多久。
每次執行-1，當有1變到0的時候，會把task擺到readyQ裡，
在此時，如果有人去suspend住某個task時，
他將不會變成0，至少會是1，為了避免會睡不到1個tick。
4. ptcb->OSTCBStat & OS_STAT_SUSPEND == 0x00
可能要等待多個動作(所有條件)滿足才能往下執行。
※ OSTimeDlyResume()
1. 把剩下的tick歸0
2. 把task搬到rdyQ
※ OSTimeGet() & OSTimeSet()
要包在critical section裡
※ 解決Delay a task until tx的問題 I
不可以使用第一種critical method包在critical section裡
因為要等時間中斷，但是前面卻已經把interrupt關掉，所以錯
※ 解決Delay a task until tx的問題 II
使用第二種critical method包在critical section裡，
頂多會有interrupt進來，假設ISR程式碼都很短，影響不大。
影響比較大的是high priority task，因為sched被lock住，
因此不會context switch
※ 解決Delay a task until tx的問題 III
自己寫，利用第一種critical method但是把巢狀拿掉。
※ OSTimeTick演算法的缺點
時間複雜度是系踏(n)，n是系統裡面所有task的數量。
※ BSD的實作方法
用link-list將timer control block(時間控制單元)串起來，
5 1 0 3 -> 5 6 6 9
好處：每次一個時間中斷，往上呼叫的時候，只要對第一項做-1就好
壞處：新增比較麻煩，有時OSTimeDly的時間複雜度比較高
結論：還是比uCOSII好
linux演算法更複雜，介於BSD和uCOSII之間
1. OSTCBList會把正在執行的task串成一列，
最後一個task一定是idle task，因為在新增刪除task時一定是從頭，
系統裡面第一個task又是idle task，造成idle task放最後一個。
2. 因此可以從頭往下找，找到idle task為止，到idle task就不執行，
因為idle task本身不會呼叫sleep，永遠都是ready。
3. (不太重要)
去判斷每個TCB裡的欄位Dly的值，數字代表要等多久。
每次執行-1，當有1變到0的時候，會把task擺到readyQ裡，
在此時，如果有人去suspend住某個task時，
他將不會變成0，至少會是1，為了避免會睡不到1個tick。
4. ptcb->OSTCBStat & OS_STAT_SUSPEND == 0x00
可能要等待多個動作(所有條件)滿足才能往下執行。
※ OSTimeDlyResume()
1. 把剩下的tick歸0
2. 把task搬到rdyQ
※ OSTimeGet() & OSTimeSet()
要包在critical section裡
※ 解決Delay a task until tx的問題 I
不可以使用第一種critical method包在critical section裡
因為要等時間中斷，但是前面卻已經把interrupt關掉，所以錯
※ 解決Delay a task until tx的問題 II
使用第二種critical method包在critical section裡，
頂多會有interrupt進來，假設ISR程式碼都很短，影響不大。
影響比較大的是high priority task，因為sched被lock住，
因此不會context switch
※ 解決Delay a task until tx的問題 III
自己寫，利用第一種critical method但是把巢狀拿掉。
※ OSTimeTick演算法的缺點
時間複雜度是系踏(n)，n是系統裡面所有task的數量。
※ BSD的實作方法
用link-list將timer control block(時間控制單元)串起來，
5 1 0 3 -> 5 6 6 9
好處：每次一個時間中斷，往上呼叫的時候，只要對第一項做-1就好
壞處：新增比較麻煩，有時OSTimeDly的時間複雜度比較高
結論：還是比uCOSII好
linux演算法更複雜，介於BSD和uCOSII之間
訂閱：
文章 (Atom)