《小记忆体软体设计》PPT课件.ppt

1、2021/1/7,1,小記憶體軟體設計,李俊宏,Outline,Introduction Small architecture Secondary storage Compression Small data structure Memory allocation,Introduction,小記憶體軟體應用 Mobile computing Embedded system Small session in server Main frame Small computer Web server JVM Limited extendibility Old PC or Server Large da

2、ta (multimedia,Mobile computing devices,Picture of AutoPC,Beaming from HPC to AutoPC,作業系統 for PDA,Linux Palm OS Win CE OS REX OS Symbian OS Android Others,Andorid Demo,記憶卡,Compact Flash (CF,Smart Media (SM,Memory Stick (MS,Multi Media Card (MMC,Secure Digital (SD,PDA OS 電源管理,Sleep mode(turn off) Sys

3、tem Clock Interrupt RAM Doze mode LCD Digitizer Main clock Processor clock Running mode(1 sec) Processor executing,程式的執行 (PALM,Preemptive multitasking User Interface Application Shell(UIAS) 一次只執行一個程式 Launch code 告知應用程式開始和顯示使用者介面 啟動事件迴圈 Event,記憶體的管理,RAM in Palm OS,記憶體的管理(storage RAM,記憶體的管理(storage RA

4、M,記憶體受限的問題的一般解法,減少靜態與全域變數的數目 減少記憶體的使用 遞迴函數可能造成堆疊空間不足 降低執行檔的體積 降低 Bitmap 解析度, 避免使用 WAV 檔案 動態配置記憶體要檢查是否配置成功 一次要足程式需要的記憶體,還有其他的方法嗎,Small architecture,Introduction Memory limit Small interfaces Partial failure Captain Oates Read only memory Hooks,Introduction,如何管理整個系統所用的記憶體 記憶體區段數量大小如果受到限制會束縛整個系統 系統由多個元

5、件組成 元件可由不同團隊完成 元件的記憶體需求量會動態改變 簡單的設計 - Monolithic Systems 只適用於簡單系統 讓每個元件管理自己的記憶體運用狀態,Introduction (cont.,Memory,module,module,module,module,module,module,Monolithic Systems,Decomposed system 組件設計 組件互相連結方式 組件共同政策,Introduction (cont.,設計組件介面須考慮之問題 記憶體的可剪裁性 (Tailorability) 不同情形下使用相同組件可能會有不同的記憶體需求 提供記憶體操控

6、的方法以精確配置記憶體 Vector v=new Vector(10) v.ensureCapacity(20) v.trimToSize() 讓客戶負責管理組件 運用callbacks管理記憶體讓客戶提供自已須要的記憶體配置函數 記憶體策略,Pattern 4: Strategy 把演算法則整個換掉,Strategy: 戰略,先提供配置記憶體的和release記憶體的函式界面, 實作時再實作出特定策略,在small architecture 中的問題,How to allocate memory? How to reduce communication load? How to proces

7、s unpredictable memory requirement? How to satisfy the most important memory requirement? How to use the read only memory (ROM)? How to modify the data in ROM,How to allocate memory,問題 如何在多個組件之間分配記憶體 解答 Memory limit (fixed sized heap, memory partitions) 為每個元件設置記憶體限額, 超出限額的請求, 予以拒絕. 描述 系統包含多個組件, 每個組件

8、有各自的記憶體需求 組件的記憶體需求隨程式的執行而動態變化 記憶體有限, 如果一個組件霸佔太多記憶體, 會妨礙其他組件工作 設計者可以為每個任務設一個合理的記憶體上限,How to allocate memory,步驟 記錄當前每個組件配置的記憶體數量 如修改組件的記憶體配置常式, 使其計算目前所使用的記憶體數目 確保組件所配置的記憶體數量不超過分配限額. 理想狀態下應當透過試驗, 檢視記憶體用量的手段來為每個組件事先設定限額,How to allocate memory,結果 因每個組件的記憶用量都有限額, 所以組件可獨立測試 (system predictability) 容易找出那些組件

9、因記憶體不足而產生問題 (localization) 可能會產生問題的情形 一個任務(task)正常工作, 但另一任務因記憶體不足而失敗 因任務大量通訊所引發的錯誤 Memory fragmentation waste,How to allocate memory,實做 攔截記憶體管理操作函式並加以修改以追蹤記憶體使用情形(如c+的 new, delete) 組件各自使用分離的heap各自管理 分離的行程,Process in Memory,Temporary data: Function parameter Return address Local variables,Global vari

10、ables,Run time memory,Example 1: 限制物件所使用記憶體總量,class MemoryRestrictedClass public: enum LIMIT_IN_BYTES=10000; static size_t totalMemoryCount; void* operator new(size_t aSize); void operator delete(void* anItem, size_t aSize); ; size_t MemoryRestrictedClass:totalMemoryCount=0,實作記憶體限制物件,Example 1: 限制物件

11、所使用記憶體總量,void* MemoryRestrictedClass:operator new(size_t aSize) if (totalMemoryCount + aSize LIMIT_IN_BYTES) throw (bad_alloc(); totalMemoryCount += aSize; return malloc(aSize); void* MemoryRestrictedClass:operator delete(void* anItem, size_t aSize) totalMemoryCount -= aSize; free(char*)anItem);,在ne

12、w 方法中檢查是否超過限制,記錄記憶體使用情形,記錄記憶體使用情形,Example 2: 限制物件實體數量,class RestrictedClass static final int maxNumberOfInstances = 5; static int numberOfInstances = 0; public RestrictedClass() nunberOfInstances+; if (numberOfInstances maxNumberOfInstances) System.gc();/確認所有的垃圾都被回收 if (numberOfInstances maxNumberOf

13、Instances) throw new OutOfMemoryError(maxNumberOfInstances5);,最大物件實體數量,再丟出異常訊號,Public void finalize() -numberOfInstances;,物件終結時要作的動作,Memory limit application,UNIX (for user process) EPOC (heap maximum size) WinCE (process usage memory upper bound, data usage memory upper bound) JVM (total heap size,

14、 java process size,練習,請設計一物件, 其有6個函式, 主程式可以呼叫這6個函式: 1: function1 2: function2 3: function3 4: closef1 5: closef2 6: closef3 假設每次呼叫前三個函式, 都會配置10, 20, 30byte的記憶體, 而呼叫後三個函式可以釋放相關記憶體. 請限制整個物件的記憶體使用在100byte內. 如果超過記憶體限制的話,物件應給主程式記憶體不足的訊息. 請撰寫此物件及其測試程式,How to reduce communication load,問題 各組件負責管理自理自身記憶體之運用

15、組件透過介面彼此溝通 如何降低組件介面溝通成本 解答 Small interfaces 設計出讓客戶端得以控制資料傳輸的介面 描述 系統包含多個組件, 每個組件有各自的記憶體需求 組件透過介面彼此進行通訊 通訊可能要配置額外的記憶體 資料提供者可能需要通用的介面, 提供不同的資料型態給不同的模組, 使記憶體需求大增,How to reduce communication load,步驟 將介面之間的資料傳輸量最小化 決定資料傳輸的品質程度,How to reduce communication load,結果 傳送用記憶體生命週期很短，可減少 Enhancing predictability,

16、 locality, design quality, and maintainability Supporting advance real time behavior 須考慮的問題 Programmer discipline Programmer effort Test cost,How to reduce communication load,實做 Pass by value vs. pass by reference Exchanging memory across interfaces Lending : 客戶出借記憶體給服務提供者 Borrowing：客戶獲服務提供者所擁有物件的存取

17、權 Stealing ：客戶接收服務提供者配置的物件，並負責歸還 Incremental interfaces 一次只傳部份資料，分多次傳完,Lending客戶出借記憶體給服務提供者,Client object,Provider object,d: Data,1. Get(d,1.1 Set(1,DocumentProperties d = new DocumentProperties(); wordProcessor.getCurrentDocumentProperties(d); . . long docsize = d.getSize(); long doctime = d.getEdi

18、tTime(); . d = null,將d借給wordProcessor 讓它進行處理,Client 對d進行處理,委託provider作一些事,釋放,Borrowing客戶獲服務提供者所擁有物件的存取權,Client object,Provider object,d: Data,1. Get():d 2. Release(d,1.1 Set(1,DocumentProperties d = wordProcessor.getDocumentProperties(); long docsize = d.getSize(); long doctime = d.getEditTime(); .

19、wordProcessor.releaseDocumentProperties(d,Stealing客戶接收服務提供者配置的物件，並負責歸還,Client object,Provider object,d: Data,1. Get():d,1.1 new(1,2. delete,DocumentProperties d = wordProcessor.getDocumentProperties(); long docsize = d.getSize(); long doctime = d.getEditTime(); . d = null,管理責任,Incremental interfaces

20、,使用情形 To pass a sequence or collection of data items Limited memory Fragmented memory 實作 Multiple calling Pass data by lending iterator Get data from writable iterator Pass data by borrow iterator,Client object,Provider object,Available space,1. Get():d,1.1 new(1,2. delete,Wanted space,Stealing: Req

21、uired space available space,Multiple calling,Client object,Provider object,d2: Data,3. new(2,d1: Data,2. take(d1) 4. take(d2) 5. doAction(,1. new(1,Multiple calling (cont.,Case A: for (int i=0;i num_new_paras;i+) wordProcessor.addParagraph(parasi); ; wordPcessAddedParagraphs(,Case B: spo

22、okivity.findGhosts(transparent|dead); While (spookivity.moreGhostsToProcess() ghostScreen.addDisplay(spoolivity.getNextGhost();,將大量圖片分批傳到wordProcessor中,再讓wordProcessor處理,Pass data by lending iterator (client,The code in client : ghostScreen.displayAllGhosts(Spookivity.ghostIterator(); The code in co

23、mponent: Void displayAllGhosts(Iterator it) while (it.hasNext() displayGhost(Ghost) it.next();,傳遞一個”指向內部群集之一”的iterator,組件憑此iterator存取客戶資訊,Iterator: a BookShelf example,Books,BookShelfIterator,Pass data by borrow iterator,Iterator it = spookivity.findGhostsIterator(transparent|dead); While (it.hasNex

24、t() ghostScreen.displayGhost(Ghost) it.next(,借入一個iterator,Memory limit application,PalmOS API EPOC API Client-server interface lending UNIX file system call read(int fid, char *buf, int nchars,How to process unpredictable memory requirement,問題 如何處理不可預見的記憶體需求 解答 Partial failure (graceful degradation)

25、 確保即使記憶體用盡也要讓系統安全運作 描述 無論如何降低程式記憶體需求還是用光了 寧可放棄非關鍵任務而不放棄關鍵任務 持續不斷執行比完美執行更重要 持續不斷執行比系統崩潰更是重要 系統中的可用記憶體數量隨著時間變化很大,How to process unpredictable memory requirement,State 1,State 2,State 3,Examples,Displaying text,Displaying more text,Displaying still more text,Processing,Processing fails,拒絕動作，回到前一安全狀態,Ou

26、t of memory state,alternative 1,alternative 2,進入降級模式,How to process unpredictable memory requirement,結果 Reduced memory requirements Enhanced software usability, quality, reliability and predictability Supporting advance real time behavior 須考慮的問題 Programmer discipline Programmer effort Software globa

27、l complexity Testing cost,How to process unpredictable memory requirement,實作 偵測記憶體耗盡 到達安全狀態 釋出資源 降級模式 未雨綢繆預防,How to process unpredictable memory requirement,範例 找出一種字型載入主記憶體 Class StrapFont static Font myDefaultFont = new Font(Dialog, Font.PLAIN, 12); /如果使用者要求之字型無法用便轉用佔較小記憶體之原始字型 . public static Font

28、 defaultFont() return myDefaultFont; Public static Font font(String name, int style, int size) Font f; try f = privateGetFont(name, style, size); catch (BadFontException e) return defaultFont(); catch (OutOfMemoryError e) return defaultFont(); return f;,Partial failure application,EPOC Degraded modes Power Point PhotoShop MFC (plotting window,How to satisfy the most important memory requirements,問題 如何滿足對記憶體的最重要需求 解答 Captain Oates (Cache release 犧牲非絕對必要之元件所使用的記憶體, 以滿足更重要的任務 描述 系統有在背景執行的元件 應用程式為了提高性能, 會以快取方存放資料 使用者有