Version2chapter4.v2

第四章 儲存管理 嵌入式系統與一般電腦系統中所使用的儲存管理 (storage management) 有著明顯的差異。在一般電腦系統中，因為有硬碟的支援，再加上記憶體容量的擴充性相當大，通常都使用硬碟做為儲存系統 (storage system) 中的後備儲存體 (backup storage) 來儲存包括作業系統和應用程式在內的檔案，記憶體則用來儲存執行程式及所需資料。在嵌入式系統中，因其所強調的是輕便性與可攜性，一般沒有硬碟的支援，且記憶體容量的擴充性相對而言相當有限。因此，如何設計一個高效能的儲存管理，對有限的記憶體資源進行公平有效的管理，在嵌入式系統中就顯得更為重要。在本章中，我們將對Windows CE中，儲存管理採用的記憶體分配、回收、虛擬記憶體映射、調頁等機制一一作深入的探討。 4.1 實體記憶體結構 在Windows CE系統中，記憶體的實體結構大致可分為RAM和ROM二種記憶體。 RAM RAM的全名為Random Access Memory。在一般電腦系統中，所謂記憶體容量即指RAM的大小而言。如前所述，RAM在一般電腦系統中，專用來儲存執行程式及所需資料。在程式執行的 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 中，作業系統先將程式從硬碟裡載入到RAM中，CPU即執行存放在RAM中的程式，程式執行時所需的heap和stack，也都分別位在RAM中不同的位址上。 在Windows CE系統中，RAM被分為程式空間 (program memory) 和物件空間 (object store)。程式空間和一般電腦系統中RAM的使用類似，用來儲存執行程式及所需資料。物件空間則類似一般電腦系統中的硬碟，用來儲存應用程式及檔案。物件空間中存放的資料可分為三大類 : (1) 檔案系統 (file system)，(2) 註冊資訊(registry)，(3) Windows CE資料庫 (Windows CE database)。程式空間和物件空間的大小是可以調整的。若是Windows CE發現處理程序 (process) 的記憶體空間不敷使用的情況下，Windows CE會 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 使用者釋放一些物件空間的記憶體來滿足程式空間的需求。圖4.1是Windows CE 3.0在Compaq iPAQ H3850所提供的記憶體空間配置畫面，此系統中可使用之RAM大小為63.14 MB，其中34.65 MB為程式空間，剩餘的28.49 MB則用做物件空間。程式空間的使用部分為7.27 MB，而物件空間的使用部分則為0.52 MB。 圖4.1 Compaq iPAQ H3850 記憶體空間配置程式 RAM記憶體既是電子裝置，其所儲存的資料則須靠電力來維持。換言之，電力來源一但中斷，儲存在RAM中的資料就消失了。一般電腦系統中電力的供應來自外接電源，一但停電或是關機，電力供應中斷，RAM中儲存的執行程式及資料馬上消失。至於筆記型電腦，其電力雖靠電池提供，但在關機狀態時，電池的電力供應是完全切斷的，因此儲存在RAM中的程式及資料，也會隨著關機而消失。 在Windows CE系統中，RAM既被用來當作物件空間使用，電力的來源則靠電池提供，因此有效的使用有限的電力來維持RAM中所儲存的資料，則顯的更為重要。Windows CE系統的電源管理機制，即使在關機狀態時，仍舊有少量的電力供應RAM，以保留儲存在其中的資料。只有在電池電力完全耗盡時，RAM中儲存的資料才會消失，而當系統重新獲得電力時，一切的資料與軟體都必需新載入。市場上常見的Compaq iPAQ，當電池電力完全耗盡而重獲電力啟動後，使用者都必需重新輸入使用者資料，或是做一些校正的動作，就是一個明顯的例子。 ROM ROM的全名為Read Only Memory，又稱唯讀記憶體，故名思義，ROM中儲存的內容只能被讀取，而不能有寫入或更改的動作。因為ROM不需電力的供應，仍然能保有儲存的內容，因此在嵌入式系統中，常被用來儲存作業系統，或是重要且不會更改的資料 (如開機時需要的資料)。 在Windows CE系統中，ROM儲存了包含作業系統在內相關的檔案。系統程式執行則分為兩種模式 : RAM執行模式和ROM執行模式。一般的系統程式執行採用RAM執行模式，作業系統會先把程式從ROM中取出，載入RAM中執行。RAM執行模式因為牽涉到程式拷貝，有執行效率差及佔用RAM記憶體空間等缺點。為此，Windows CE提供XIP　(Execute in Place)，也就是ROM執行模式，使得儲存在ROM中的系統程式，可以在指定的ROM位址中直接執行，而不用載入RAM中。 ROM的唯讀特性，使得更改其中內容這個動作，變的相當複雜。舉例來說，若Compaq iPAQ只具有ROM作為作業系統的儲存工具，要升級一個Compaq iPAQ的作業系統，必需先有一顆新的ROM，利用特殊的設備將新的作業系統寫入，再用此ROM更換iPAQ中原有的ROM。因為此特殊的設備甚為昂貴且不易取得，近年來便有Flash ROM的產生。Flash ROM不僅保有原本ROM在電源消失後仍保有資料的好處，並且擁有RAM可寫入的特性，因此我們可以用它來保存作業系統，並利用軟體的方式來升級或更換作業系統。Compaq iPAQ H3600系統的PDA中所配有的ROM即是Flash ROM。使用者可以到Compaq或相關網站取得Flash ROM寫入程式，並利用此程式來進行作業系統升級或更換 (例如Windows CE (( Linux) 的動作，而完全無需更換硬體。 4.2 虛擬記憶體管理 Windows CE系統的記憶體管理是建構在虛擬記憶體機制上。在本節中，我們將介紹Windows CE的虛擬記憶體機制、其中所使用的分頁機制、及提供多工作業的slot結構。 虛擬記憶體 電腦程式的運算大多是在迴圈 (loop) 結構內完成。迴圈執行時所 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 現出來的位址侷限性 (address locality) 及空間侷限性 (space locality)，使得執行程式所需的實體記憶體空間遠比程式碼本身小，且同一時段內，只需載入一小部分的資料結構即可。為了程式設計師撰寫程式方便，作業系統一般都將程式記憶體空間與實體記憶體空間分開。這裡所稱的程式記憶體即是虛擬記憶體。實體記憶體內所使用的位址稱為實體位址 (physical address)，而虛擬記憶體內所使用的位址稱為虛擬位址 (virtual address)。 虛擬記憶體的大小可以遠大於實體記憶體的大小。在一般作業系統中，虛擬記憶體的大小決定於所使用的位址位元長度。舉例而言，在一個32-bit位址長度的作業系統，其虛擬記憶體的大小為4GB (232 Bytes)，而系統所配備的實體記憶體可能只有32MB或64MB。虛擬記憶體的設計，使得程式設計師撰寫程式時，不必顧慮到系統的實體記憶體的大小。另外，虛擬記憶體允許不同程式共用相同的檔案和程式碼。圖4.2為虛擬記憶體的概述圖，其中說明了虛擬位址和實體位址的轉換。 圖4.2　　虛擬記憶體與實體記憶轉換概述圖 分頁機制 Windows CE系統所使用的位址位元長度為32-bit。換言之，其虛擬記憶體的大小為4GB (232 Bytes) 。Windows CE將這4GB虛擬位址空間分為低位址2GB及高位址2GB。應用程式使用的位址空間為低位址2GB，高位址2GB專供Windows CE核心模組使用。Windows CE作業系統使用KDataStruct資料結構來存放低位址2GB內的資料。程式碼4.1列出KDataStruct整個資料結構。 程式碼4.1 KDataStruct資料結構 struct KDataStruct { LPDWORD lpvTls; /* 0x000 Current thread local storage pointer */ HANDLE ahSys[NUM_SYS_HANDLES]; /* 0x004 If this moves, change kapi.h */ char bResched; /* 0x084 reschedule flag */ char cNest; /* 0x085 kernel exception nesting */ char bPowerOff; /* 0x086 TRUE during "power off" processing */ char bProfileOn; /* 0x087 TRUE if profiling enabled */ ulong ptDesc; /* 0x088 Page Table Descriptor */ ulong rsvd2; /* 0x08c was DiffMSec */ PPROCESS pCurPrc; /* 0x090 ptr to current PROCESS struct */ PTHREAD pCurThd; /* 0x094 ptr to current THREAD struct */ DWORD dwKCRes; /* 0x098 */ ulong handleBase; /* 0x09c handle table base address */ PSECTION aSections[64]; /* 0x0a0 section table for virutal memory */ LPEVENT alpeIntrEvents[SYSINTR_MAX_DEVICES]; /* 0x1a0 */ LPVOID alpvIntrData[SYSINTR_MAX_DEVICES]; /* 0x220 */ ulong pAPIReturn; /* 0x2a0 direct API return address for kernel mode */ uchar *pMap; /* 0x2a4 ptr to MemoryMap array */ DWORD dwInDebugger; /* 0x2a8 !0 when in debugger */ PTHREAD pCurFPUOwner; /* 0x2ac current FPU owner */ PPROCESS pCpuASIDPrc; /* 0x2b0 current ASID proc */ long alPad[19]; /* 0x2b4 - padding */ DWORD aInfo[32]; /* 0x300 - misc. kernel info */ /* 0x380 - interlocked api code */ /* 0x400 - end */ }; /* KDataStruct */ 在KDataStruct資料結構中，又利用PSECTION aSections[64] 將低位址2GB分割成64個32MB大小的空間，稱之為Section。一個Section再被分割成512個64KB大小的空間，稱之為MemBlock，如程式碼4.2所示。一個MemBlock再被分割成數個頁 (Page)。頁的大小 (PAGE_SIZE) 在不同的系統中略有不同。ARM4處理器的PAGE_SIZE為4096，ARM920的PAGE_SIZE為1024，MIPS及x86處理器的PAGE_SIZE則為4096。若以PAGE_SIZE = 4096，一個MemBlock可被分割成16個頁。程式碼4.3列出MemBlock整個資料結構，其中aPages[PAGES_PER_BLOCK] 欄位紀錄虛擬記憶體中每一個頁所對應到的實體記憶體位址。 程式碼4.2 BLOCK、SECTION資料結構 #define BLOCK_MASK 0x1FF typedef MEMBLOCK *SECTION[BLOCK_MASK+1]; //每一個SECTION指向512個BLOCK typedef SECTION *PSECTION; 程式碼4.3 MemBlock資料結構 #define PAGE_SIZE 4096 /* page size */ #define PAGES_PER_BLOCK (0x10000 / PAGE_SIZE) struct MemBlock { ACCESSLOCK alk; /* 00: key code for this set of pages */ uchar cUses; /* 04: # of page table entries sharing this leaf */ uchar flags; /* 05: mapping flags */ short ixBase; /* 06: first block in region */ short hPf; /* 08: handle to pager */ short cLocks; /* 0a: lock count */ ulong aPages[PAGES_PER_BLOCK]; }; /* MemBlock */ 我們以CEPC為例子來說明虛擬記憶體到實體記憶體的對映關係。CEPC是將Windows CE作業系統在個人電腦上執行。在這個以x86處理器的平台上，虛擬記憶體到實體記憶體對映，可以用圖4.5及圖4.6來解釋。應用程式執行時所送出的位址，即虛擬位址，長為32個位元 (編號第31-0個位元)。一個虛擬位址可以如圖4.5所示切割成五大區段 : · 第一區段只有一個位元，即第31個位元，因應用程式只能使用低位址2GB，第31個位元一定是0。 · 第二區段有六個位元，即第30-25個位元，紀錄此位址所屬的Section號碼。 · 第三區段有九個位元，即第24-16個位元，紀錄此位址所屬的MemBlock號碼。 · 第四區段有四個位元，即第15-12個位元，紀錄此位址所屬的頁號碼。 · 第五區段有十二個位元，即第11-0個位元，紀錄此位址在所對映的實體記憶體頁內的相對位址。 31 30 　24 　 15 　11 0 0 Section number 6位元 Block number 9位元 Page number 4位元 Offset 12位元 圖4.5 x86處理器虛擬位址的劃分 Windows CE作業系統在收到一個虛擬位址後，即根據圖4.5所示將此位址切割，並根據每區段內的值，從程式碼4.1的KDataStruct開始，依Section、MemBlock、頁的順序，來找到此虛擬位址所對映到的實體記憶體位址。整個對映的流程圖示在圖4.6中。 圖4.6 虛擬記憶體與實體記憶體的對映關係 Windows CE從低位址的2GB起始位址開始的連續位址，劃分出33個32MB的記憶體空間，稱之為”slot”，等同於前述的前33個SECTION，當處理程序要執行前，Windows CE將處理程序載入至slot中執行，特別需要注意的是，slot 0保留給目前正在執行的處理程序使用，其餘的slot則留給非正在執行的處理程序使用。因此，Windows CE系統中，最多只能有32個處理程序同時進行。圖4.３是記憶體的配置情形，稍後將介紹memory mapping的細節及其它的記憶體空間。 2GB slot 0 slot 1 slot 2 … slot 32 For Memory Mapping 為作業系統保留的記憶體空間 圖4.３ 於Windows CE PlatformBuilder使用mi指令可獲得CEPC記憶體資訊，圖4.4為mi指令的使用方式及結果。 圖4.4 mi指令的使用方式及結果 程式碼4.4為mi指令執行後的片段結果: 程式碼4.4 CEPC記憶體資訊 Windows CE Kernel Memory Usage Tool 0.2 Page size=4096, 4958 total pages, 4544 free pages. 4517 MinFree pages (1806336 MaxUsed bytes) 90 pages used by kernel, 0 pages held by kernel, 414 pages consumed. Memory usage for Process 81791560: 'NK.EXE' pid 0 SECURE SECTION: Slot base c2000000 Section ptr 81749d00 //為系統保留的 Page summary: code=0(0) data r/o=0 r/w=2 stack=3 reserved=315 //SECURE SECTION ROM DLL CODE SECTION: Slot base 02000000 Section ptr 83ffc000 //Slot 1 的使用情形 Page summary: code=508(0) data r/o=68 r/w=1 stack=0 reserved=2672 Memory usage for Process 81791614: 'filesys.exe' pid 1 //Slot 2被filesys.exe Slot base 04000000 Section ptr 83ff1000 //使用情形 Page summary: code=31(0) data r/o=1 r/w=20 stack=5 reserved=334 Memory usage for Process 817916c8: 'shell.exe' pid 2 //Slot 3被shell.exe Slot base 06000000 Section ptr 83fcf000 //使用情形 Page summary: code=10(0) data r/o=0 r/w=7 stack=2 reserved=330 Memory usage for Process 8179177c: 'device.exe' pid 3 //Slot 4被 Slot base 08000000 Section ptr 83fc9000 //device.exe使用 Page summary: code=6(1) data r/o=0 r/w=113 stack=40 reserved=958 //情形 SLOT 0 由於在Windows CE系統中，許多處理程序都會擁有相同的DLLs (dynamic link libraries) 檔，若是每一個處理程序都在實體記憶體找出一塊空間放置相同的DLLs檔，由於DLLs的程式碼是唯讀性且不可變更的，若是重覆放置將會是實體記憶體的一大浪費，因此Windows CE系統將不同處理程序的相同DLLs對應到同樣的實體記憶體位址，如此減少了記憶體的浪費，雖然DLLs檔是相同的，每個處理程序仍舊必需擁有一些自己的DLLs變數資料，因為DLLs變數資料並不是相同的。此時，產生了一個問題，DLLs檔如何知道目前是哪一個處理程序在呼叫它?Windows CE為了解決這個問題，規定DLLs檔只能對slot 0的變數做變動，也就是目前正在執行的處理程序，這也是slot 0存在的原因。 圖4.5 DLL檔對應關係圖:slo1和slot2相同的DLLs檔，對應至相同的實體記憶體 DoVirtualAlloc() 函式 Windows CE系統配置記憶體有兩種方式 : 保留(MEM_RESERVE) 和提交(MEM_COMMIT)。這兩種方式的差別在於保留只會保留虛擬頁給處理程序，而提交不僅給予處理程序虛擬頁，更會於實體記憶體取得對應頁。 DoVirtualAlloc() 函式可以根據使用者對記憶體的要求，如保留、提交，執行保留虛擬記憶體或是抓取實體頁並填入頁表 (page table) ，由於原始碼非常複雜，本章節提供流程圖 (圖4.6) 供讀者參考，其原始碼的位置在於 : WINCEROOT\PRIVATE\WINCEOS\COREOS\NK\KERNEL\virtmem.c 有興趣的讀者可以查閱。 圖4.6虛擬位址分配流程 4.3實體記憶體管理 可用記憶體鏈結串列 可用記憶體串列用以記錄目前系統中尚可使用的記憶體，可由LogPtr->pKList找到串列。可用記憶體串列採用簡單的雙向鏈結串列形式。所以鏈結串列的管理極為簡單。程式碼4.5是插入可用記憶體鏈結串列的程式碼： 程式碼4.5 插入可用記憶體鏈結串列程式碼 void LinkPhysPage( LPBYTE pMem ) { KCALLPROFON(32); *(LPBYTE *)((DWORD)pMem + 0x20000000) = LogPtr->pKList; *(LPBYTE *)((DWORD)pMem + 0x20000004) = 0; if (LogPtr->pKList) *(LPBYTE *)((DWORD)LogPtr->pKList + 0x20000004) = pMem; LogPtr->pKList = pMem; PageFreeCount++; LogPhysicalPages(PageFreeCount); KCALLPROFOFF(32); } 其中KCALLPROFON() 和KCALLPROFOFF() 分別是開啟、關閉與加入可用記憶體串列相關的系統記錄。 取得實體記憶體 圖4.6中，取得實體記憶體是利用GetHeldPage函式呼叫GrabFirstPhysPage函式取得實體頁，程式碼4.6是GetHeldPage函式，程式碼4.7是GrabFirstPhysPage()函式部分程式碼。 程式碼4.6 GetHeldPage函式 PHYSICAL_ADDRESS GetHeldPage(void) { PHYSICAL_ADDRESS paRet; LPBYTE pMem; if (pMem = (LPBYTE)KCall((PKFN)GrabFirstPhysPage,1)) { //GrabFirstPhysPage取得 PageFreeCount++; // since we already reserved it //實體頁回傳 LogPhysicalPages(PageFreeCount); paRet = GetPFN(pMem); } else paRet = 0; DEBUGMSG(ZONE_PHYSMEM,(TEXT("GetHeldPage: Returning %8.8lx\r\n"), paRet)); return paRet; } 程式碼4.7 GrabFirstPhysPage函式 LPBYTE GrabFirstPhysPage( DWORD dwCount ) { PFREEINFO pfi; uint ix; PHYSICAL_ADDRESS paRet; LPBYTE pMem; KCALLPROFON(33); //檢查PageFreecount （可用實體頁）的值是否不小於0，而不是檢測LogPtr->pKList //是否為空，因為後者可能導致PageFreecount<0 if (PageFreeCount) { pMem = LogPtr->pKList; paRet = GetPFN(pMem); //從實體頁框得到系統可用記憶體區域指標 pfi = GetRegionFromAddr(paRet); if (pfi) { // // 從可用記憶體鏈結串列中取出一頁 // 不經過Cache // if (LogPtr->pKList = *(LPBYTE *)((DWORD)pMem + 0x20000000)) { *(LPBYTE *)((DWORD)LogPtr->pKList + 0x20000004) = 0; } // //去掉可用記憶體鏈結串列的資訊，得到空白頁 *(LPDWORD)(pMem + 0x20000000) = 0; *(LPDWORD)(pMem + 0x20000004) = 0; //修改系統中的FREEINFO變量的值，將引用數目改為dwCount ix = (paRet - pfi->paStart) / PFN_INCR; DEBUGCHK(pfi->pUseMap[ix] == 0); DEBUGCHK(dwCount && (dwCount <= 0xff)); pfi->pUseMap[ix] = (BYTE)dwCount; if (-- PageFreeCount < (long) KInfoTable[KINX_MINPAGEFREE]) { KInfoTable[KINX_MINPAGEFREE] = PageFreeCount; } ……………………………… return pMem; } 偏移量0x20000000定義了一個映射，因為系統核心(kernel)也工作在虛擬記憶體模式下，該映射就將可用記憶體鏈結串列，保存在kernel的工作空間之中。所以，可用記憶體鏈結串列只是保留的實體值的指標。回收的過程與此類似，定義在FreePhysPage()中。 獲得連續實體頁的分配策略定義在GetContiguousPages中，其基本策略是掃描各個區域（Region），找到第一個滿足條件的連續實體塊。這個函數在執行時需要佔用實體記憶體的臨界區很長時間，嚴重影響其它要進入該臨界區的處理程序的運行。 實體頁抓取流程 在虛擬記憶體的映射過程中，要進行實體頁的抓取，這個過程分為兩個步驟，第一步是檢查實體記憶體是否滿足需求，如果配置導致實體記憶體極度減少，則啟動CleanUp執行緒，並向系統發出警報。如果配置後實體頁數低於某個閾值，則削減執行緒PthScavTarget的堆積(stack)，如果可以滿足，那麼標記配置並警告GWE記憶體不足，這部分原始碼定義在函數HoldPages中。該函數的流程見圖4.7。 第二步，標記之後，由GetHeldPage函數得到所需的實體頁，該函數主要呼叫GrabFirstPhysPage從可用記憶體鏈結串列中摘出一個實體頁。 圖4.7 實體頁面抓取流程 ProcessPageFault函式 ProcessPageFault函式處理存取頁記憶體時發生的錯誤，產生的原因可能為: ．虛擬記憶體位址沒有實體頁映射 ．存取權限不允許此動作 ．無效虛擬記憶體位址 在ProcessPageFault函式定義了這幾種情況下相應的處理方法。首先檢查該虛擬記憶體位址是否有效，再檢查當前處理程序是否對該位址有權限，最後根據該block的類型決定呼叫函式，如果是mapper則呼叫MapperPageIn，如果是處理程序位址空間則調用LoadPageIn，每次呼叫若不成功，則重複，2秒鐘以後超時，傳出錯誤訊息。 頁錯誤處理的部分程式碼： 程式碼4.8 頁錯誤處理的部分程式碼 retryPagein: EnterCriticalSection(&VAcs); pscn = IsSecureVa (addr)? &NKSection : SectionTable[addr >> VA_SECTION]; if ((pscn != NULL_SECTION) && ((pmb = (*pscn)[ixBlock]) != NULL_BLOCK)) { /*虛擬記憶體位址有效性檢查*/ if (pmb == RESERVED_BLOCK) { pmb = (*pscn)[FindFirstBlock(pscn, ixBlock)]; pagerType = pmb->flags & MB_FLAG_PAGER_TYPE; } else { if (pmb->aPages[ixPage] & PG_VALID_MASK) { if (!bWrite || IsPageWritable(pmb->aPages[ixPage])) bRet = TRUE; else pagerType = pmb->flags & MB_FLAG_PAGER_TYPE; } else if (pmb->aPages[ixPage] != BAD_PAGE) pagerType = pmb->flags & MB_FLAG_PAGER_TYPE; } if (TestAccess(&pmb->alk, &CurAKey)) { /*處理程序對該虛擬記憶體位址的可存取性檢查*/ if (pagerType != MB_PAGER_NONE) { /*若該頁沒有分配，則傳出錯誤訊息，退出*/ LeaveCriticalSection(&VAcs); dwLast = KGetLastError(pCurThread); pageresult = PageInFuncs[pagerType-MB_PAGER_FIRST](bWrite, addr0); //根據該虛擬記憶體段的類型確定調頁函數MappedPageIn或者 //LoaderPageIn KSetLastError(pCurThread,dwLast); if (pageresult == PAGEIN_RETRY) { Sleep(250); bRet = FALSE; pagerType = MB_PAGER_NONE; goto retryPagein; goto FailPageInNoCS; } bRet = (BOOL)pageresult; EnterCriticalSection(&VAcs); } } else { bRet = FALSE; // Thread not allowed access, return failure. } } LeaveCriticalSection(&VAcs); 4.2 堆疊(Heap) 當處理程序執行時，需要靜態或動態配置記憶體，如宣告變數或宣告指標，此時所需的記憶體小，不應配置一個頁面而造成記憶體的浪費，堆疊因此而生，系統可以利用堆疊對處理程序做較少的記憶體配置，而使用者不需了解系統的記憶體配置。處理程序可以利用堆疊申請大小比頁小很多的記憶體，一旦申請了堆疊，系統會根據處理程序的需要自動增加堆疊的大小，而釋放堆疊的時候，堆疊的削減也是由系統自動完成的。在Windows CE中，系統對堆疊的管理只允許申請固定大小的塊。這樣做的好處是簡化了對堆疊中各個塊的管理，代價是在程序運行過程中不斷的分配和釋放會出現很多碎片，會導致只要堆疊沒有被完全釋放，還會保留大量的虛擬頁的情況。在Windows CE中，每個堆疊都有一個信號(signal)來控制順序存取，兩個處理程序同時對堆疊執行動作是不允許的。 本地堆疊（Local Heap）和獨立堆疊（Separate Heap） 在缺頁情況下，系統保留384個頁作為本地堆疊，這些頁只有在分配的時候才會被提交，如果應用程式需要的本地堆疊超過384頁，系統會自動分配其餘的空間，不過這些空間可能在虛擬地址上並不相鄰而產生碎裂，因為系統的堆疊分配只支持固定大小的塊。 為了避免碎裂的出現，在申請要反復分配和回收的儲存空間時，使用者最好對每個申請使用獨立堆疊。獨立堆疊的分配是以slot為界限的，系統不允許應用程序申請的堆疊耗盡其它處理程序所擁有的32MB虛擬地址空間。 堆疊的邏輯結構 邏輯位址是虛擬記憶體位址的名稱，而邏輯結構就是虛擬位址的結構。處理程序分配儲存空間的基本單位是堆疊。每個堆疊維護著一個虛擬地址項（VAitem）和區域（region）的鏈結串列。項的大小可變，是實際進行分配時的最小單位。項和項之間在虛擬地址上是相鄰的，所以項只在鏈結串列頭記錄該項的大小，下一個項就可以順著這個值找到。為了便於對項的管理，系統還定義了單位更高的區域，區域是一段連續的項的空間，也是虛擬地址分配和回收的基本單位，記錄了區域中最大的項的大小以及所屬的堆疊，這樣在查找可用記憶體項的時候可以提高效率，並且可以用很大的單位申請虛擬地址空間和提交已保留的空間。虛擬地址項是為了在分配大空間時直接使用的，因為單位大，所以不必包含在區域中，而直接由堆疊來維護 下面是結構的定義： 程式碼4.9 struct region { pitem pitFree; // 00: 下一個可用記憶體項 pregion prgnLast; // 04: 區域串列上最後一個區域指標(只對第一個區域有效) int cbMaxFree; // 08: 該區域中最大可用記憶體項的尺寸 pitem pitLast; // 0C: 鄰接結束標誌的最後一個可用記憶體項 pheap phpOwner; // 10: 所屬堆疊 pregion prgnNext; // 14: 該堆疊中下一個區域的指標 }; // 18: 區域大小 struct heap { DWORD dwSig; // 00: 堆疊的符號“Heap” pvaitem pvaList; // 04: vaitem的鏈結串列 pheap phpNext; // 08:堆疊鏈結串列中下一個堆疊 WORD flOptions; // 0C: 創立堆疊的參數 #ifdef MEMTRACKING WORD wMemType; // 0E: 註冊的記憶體類型 #else WORD wPad; // 0E: 填充位元，用作對齊 #endif DWORD cbMaximum; // 10: 堆疊大小的上限 (0表示可增長) CRITICAL_SECTION cs; // 14: 管理該堆疊使用的臨界區 region rgn; // 28: 該堆疊中第一個儲存區域 }; // Item structure: // 區域中的項有如下幾種類型： // busy items: size > 0 prgn 指向item所屬的區域 // free items: size < 0 // hole items: size > 0 and prgn == NULL // end maker: size == 0 cbTail 表示尾部之前的字節數 // 最後一種表示項是由虛擬地址映射的。 // virtual item: size > 0 並且size為奇數 struct item { int size; // 項的大小（包含頭部和尾部） union { pregion prgn; // 項所屬區域的指標 pheap php; // 或是指向包含虛擬儲存項的堆疊指標 int cbTail; // 該區域中尾部前邊的字節數 }; #if HEAP_SENTINELS int cbTrueSize ; // 實際需要的字節數 DWORD dwSig; // 項頭的統計訊息 #endif }; struct vaitem { pvaitem pvaFwd; // 堆疊中下一個虛擬地址項的指標 pvaitem pvaBak; // 堆疊中前一個虛擬地址項的指標 item it; // 項訊息 }; 堆疊的創建和初始化 堆疊的創建和初始化定義在HeapCreate(DWORD flOptions, DWORD dwInitialSize, DWORD dwMaximumSize)函數中，flOptions是創建方式，dwInitialSize是初始分配尺寸，dwMaximumSize是堆疊的尺寸上限，如果為零，說明堆疊是可以增長的。在創建的過程中，系統先將dwInitialSize，dwMaximumSize都對齊到頁的大小，然後呼叫VirtulAlloc保留dwMaximumSize個虛擬頁，然後再呼叫InitNewHeap分配dwInitialSize個虛擬頁並對這個堆疊進行初始化。初始化部分的程式碼如下： 程式碼4.10 堆疊初始化部分程式碼 InitializeCriticalSection(&php->cs); /*初始化該堆疊的存取臨界區*/ // 初始化堆疊中第一個可用記憶體項 pit = FIRSTITEM(&php->rgn); php->rgn.pitFree = php->rgn.pitLast = pit; dwTemp = (dwInitialSize - SIZE_HEAP_HEAD - sizeof(item)) & ~(ALIGNBYTES-1); pit->size = -(int)dwTemp; //將項大小置為整個分配空間的大小， //並標記為可用記憶體（<0） pit->prgn = &php->rgn; pit = (pitem)((char*)pit + dwTemp); /*找到下一個項的起始地址*/ pit->size = 0; /*標記為結尾標識*/ pit->cbTail = cbRegion - dwInitialSize; php->rgn.cbMaxFree = dwTemp; /*初始化該堆疊的第一個區域*/ php->rgn.phpOwner = php; php->rgn.prgnLast = &php->rgn; /*設置鏈結串列指標*/ 堆疊的分配和回收 堆疊的分配過程首先計算堆疊所在的slot，如果分配方式為可增長且分配空間大於188k，那麼直接從該slot分配虛擬地址給pVAitem。否則在已有區域中找出滿足條件的項，如果找不到則創建一個新的區域，將整個區域的空間細化，使之成為一個剛好滿足條件的項。程式碼4.11為堆疊分配過程的部分程式碼: 程式碼4.11 堆疊分配過程的部分程式碼 if (!php->cbMaximum && (dwBytes+sizeof(vaitem) >= CE_VALLOC_MINSIZE)) { pitRet = DoLargeHeapAlloc (lpSlot, php, dwBytes); //如果分配的空間大於188k，則直接從虛擬記憶體分配空間給虛擬地址項。 } else { int cbSeek = ALIGNSIZE(dwBytes + sizeof(item) + HEAP_SENTINELS); // 進入該堆疊的臨界區以控制存取的順序性 EnterCriticalSection (&php->cs); if (!(pitRet = FindFreeItem (lpSlot, php, cbSeek, &prgn)) && !php->cbMaximum && (prgn = CreateNewRegion (lpSlot, php, cbSeek))) { // 如果不能在已有的區域內找到，則創建一個新的區域 pitRet = FIRSTITEM (prgn); } if (pitRet) { // 將得到的可用記憶體項細化 pitRet = CarveItem (prgn, pitRet, cbSeek, dwBytes, NULL); } LeaveCriticalSection (&php->cs); FindFreeItem是尋找第一個可用項的函數主要呼叫FindFreeItemInRegion，使用的演算法描述如下。 do { while ((cbItem = pit->size) > 0) { /*該項在使用中？*/ pit = (pitem)((char*)pit + cbItem); } pit = MergeFreeItems (prgn, pitRet = pit); /*如果有相鄰可用記憶體項，則合併之*/ cbItem = -pitRet->size; // 判斷這個塊是否夠大 if (cbItem >= cbSeek) { if (cbItem - cbSeek > cbMax) cbMax = cbItem - cbSeek; break; } if (cbMax < cbItem) cbMax = cbItem; if (fEndReached && (pit >= pitStart)) break; /*如果到區域末尾還沒有找到足夠大的塊，則設置結尾標識 但是在分配額外實體記憶體之前還不能使用*/ if (!pit->size) { fEndReached = TRUE; pitEnd = pitRet; pit = FIRSTITEM (prgn); } }while (!fEndReached || (pit < pitStart)); CarveItem做的是將得到的項細化成所需空間大小的項，並盡可能的向左對齊。下面是其在實際映射空間不足的情況下將空間補齊的程式碼。 if (cbItem < cbSeek) { pitem pitEnd = (pitem) ((char *) pit + cbItem); int cbEx; // 計算需要補齊的頁數目 // 注意補齊之後要標記一個新的結尾標識 cbEx = (cbSeek - cbItem + sizeof(item) + PAGE_SIZE-1) & -PAGE_SIZE; if (!VirtualAlloc ((char *)pitEnd + sizeof(item), cbEx, MEM_COMMIT, PAGE_READWRITE)) { return NULL; // 記憶體不足，報錯返回 } //創建一個新的結尾標識 pitNext = (pitem)((char*)pitEnd + cbEx); pitNext->size = 0; pitNext->cbTail = pitEnd->cbTail - cbEx; 堆疊的回收 堆疊的回收也有兩種情況。如果是直接分配虛擬地址給項，那麼只要將該項從pVAitem鏈結串列上摘出，並將虛擬地址釋放。如果是通過區域，那麼合併可能出現的相鄰可用記憶體項。 程式碼4.12 堆疊的回收 if (size & 1) { /*虛擬地址映射到項的標記*/ if (php == pit->php) { pvaitem pva = (pvaitem)((char*)lpMem - sizeof(vaitem)); EnterCriticalSection(&php->cs); if (pva->pvaBak == NULL) { DEBUGCHK(php->pvaList == pva || (pvaitem)ZeroPtr(php->pvaList) == pva); if ((php->pvaList = pva->pvaFwd) != NULL) php->pvaList->pvaBak = NULL; } else { // Item in the middle or end of the list. DEBUGCHK(php->pvaList != pva); if ((pva->pvaBak->pvaFwd = pva->pvaFwd) != NULL) pva->pvaFwd->pvaBak = pva->pvaBak; } /*找到虛擬地址所在的項，並將其從鏈結串列上摘出*/ LeaveCriticalSection(&php->cs); lpMem = (LPVOID)((DWORD)lpMem & -PAGE_SIZE); VirtualFree(lpMem, size, MEM_DECOMMIT); VirtualFree(lpMem, 0, MEM_RELEASE); /*將這段虛擬地址與實際實體地址的映射脫離，仍然保留虛擬地址*/ bRet = TRUE; } } else if ((prgn = pit->prgn)->phpOwner == php) { EnterCriticalSection (&php->cs); pit->size = -size; MergeFreeItems (prgn, pit); /*合併可能出現的可用記憶體項*/ if (prgn->cbMaxFree < -pit->size) prgn->cbMaxFree = -pit->size; prgn->cbMaxFree |= REGION_MAX_IS_ESTIMATE; LeaveCriticalSection (&php->cs); bRet = TRUE; } } 4.3 Windows CE的保護和共享機制 頁表的內容 在頁表中，每個項目的長度都是32位元。事實上，頁表中並不需要儲存offset的資訊，因此Windows CE利用offset的12位元作為保護的機制，這也代表Windows CE對記憶體的保護是以頁為單位，並且可利用TestAccess函式作安全性的檢查，及VirtualProtect 函式得到或設置一個虛擬位址區域的存取權限。下表4.1是頁表保護機制中，各個權限所代表的值及含義: 表4.1 頁表保護機制權限設定值 權限 值 含義 PAGE_NOACCESS 0x01 不允許任何類型的存取（讀，寫，執行）任何試圖存取該頁的操作都會產生General Protection錯誤 PAGE_READWRITE 0x02 允許讀寫已提交的頁 PAGE_READONLY 0x04 只允許讀已提交的頁 PAGE_WRITECOPY 0x08 頁可以通過寫時拷貝共享數據 PAGE_EXECUTE 0x10 允許執行已經提交的頁 PAGE_EXECUTE_READ 0x20 可以讀，執行該頁 PAGE_EXECUTE_READWRITE 0x40 允許讀寫執行該頁 PAGE_EXECUTE_WRITECOPY 0x80 可讀寫執行，共享該頁。 PAGE_GUARD 0x100 設置標記哨，在第一次存取該頁的時候產生STATUS_GUARD_PAGE異常，並將該哨清除，通常用於第一次要特殊處理的頁的存取中。 PAGE_NOCACHE 0x200 強制聲明所在實體頁不進入cache，重要用於設備驅動程序中。 PAGE_PHYSICAL 0x400 PAGE_WRITECOMBINE 0x400 Windows CE的共享機制 在Windows CE中頁的共享在兩個層次實現。在邏輯儲存層，實現處理程序之間的記憶體共享，通過建立共享堆疊來實現。在虛擬記憶體管理的層次，系統通過直接將不同的虛擬地址映射到同一實體地址來實現記憶體共享，主要實現一些處理程序間通訊的系統呼叫。 堆疊共享 堆疊共享的實現比較簡單，只是在系統堆疊中分配一個新的堆疊儲存區域建立一個堆疊的資料結構，然後將共享堆疊中的item鏈結串列穿起來。程式碼4.13為其程式碼。 程式碼4.13 InitSharedHeap函式程式碼 LPBYTE InitSharedHeap(LPBYTE pMem, DWORD size, DWORD reserve) { pheap php; pitem pit; LPBYTE pbAlloc; php = (pheap)pMem; pit = FIRSTITEM(&php->rgn); if (size) { InitNewHeap(php, HEAP_IS_SHARED, PAGE_SIZE, size, size); pbAlloc = HeapAlloc((HANDLE)php, 0, reserve); //在系統堆疊中為共享堆疊分配儲存空間 DEBUGCHK(pbAlloc == (LPBYTE)(pit+1)); //將原有堆疊中的數據結構鏈直接掛到共享堆疊中。 } return (LPBYTE)(pit+1); } 虛擬記憶體共享 虛擬記憶體共享的實現要稍微複雜一些，由於要直接讀取頁表，所以要進入虛擬記憶體臨界區。首先在系統堆疊中分配一塊空間建立共享虛擬記憶體的頁表，然後讀出頁表中的每個實體頁數編號，填入目標虛擬地址的頁表中。在映射的過程中，要將目標虛擬地址的存取權限加到虛擬地址的頁表中。 圖4.8 虛擬地址拷貝流程 Current Process slot 0 退出臨界區 將頁目錄定義為系統源頁目錄 掃描這個共享的虛擬儲存區的頁表，將實體頁框號拷貝到目標頁表 掃描整個共享的實體記憶體區域，將頁框號填入目標頁表 根據位移找到源頁目錄 是否直接映射實體記憶體 源地址是否在安全區 進入臨界區域 合法性檢查 地址是否已經保留? 是否為安全地址? 配置數大於低閾值並且配置後剩餘實體頁面小於低閾值？ 配置數大於警戒閾值並且配置後剩餘實體頁面小於警戒值 slot 2 slot 1 實體記憶體 虛擬記憶體 DLL Code DLL xxx DLL xxx 回傳錯誤退出 否 檢查所有塊都已保留 是 是否找到 對齊地址到64K邊界 將得到的實體 頁框填入頁表 是 是 報錯退出 成功？ 否 按給定的方式掃描可用記憶體區尋找滿足條件的可用記憶體塊 否 合法性檢查 是否需要提交？ 是 抓取足夠的實體頁 將頁表項 標記為保留 是 分配系統保留段 是 否，在堆疊增長時 自動提交 頁面是否需要映射到實體地址？ 已在分配段 否 地址? 將當前處理程序的存取 控制訊息填入頁表 進入臨界區 通過 在系統堆疊中分配頁表 (MEMBLOCK)空間 不通過 合法性檢查 報錯 失敗退出 進入PHY臨界區 否 否 是 剩餘實體頁是否小於觸發臨界值？ 否 是 設置頁面換出標誌 是 否 設置換頁執行緒優先級 修改可用記憶體頁數 PageFreeCount 向系統發出警報 削減PthScavTarget堆積 否 否 設置GweOOM事件通知系統實體記憶體不足 強制配置？ 是 能否滿足需求？ 成功退出 成功退出 是 PAGE 14 _1095248038.vsd � �����x�s��� 0� 1� 2� �K�K�K�K�K�K�K�K�K�K� 3� 4� 5� 6� 0� � �K�K�K�K�K�K�K�K�K�K� 1� Page m-1� 2� � 3� � 4� Page 1� �K�K�K�K�K�K� Page 0� � Page 1� 4� v� Page 2� � k-1� Page 3� �����O����� k� � Page 3� k-1� v� �K�K� � Page m-1� 1� v� Page Table� Page m� � �������}� Valid Bit� 0� � �����O����� 1� � 2� � 3� � 4� � 5� � 4GB� � �K�K�K�K� � m-1� � m� � m-1� � �K�K�K�K� �������}�������������}� _1097907625.vsd � � SectionTable[0]� SectionTable[1]� SectionTable[63]� . . .� � � SectionTable� Section� Section[0]� Section[1]� Section[511]� Section� . . . . � Section[0]� Section[511]� . . � � � Memblock� Memblock� . .� . .� � . . . � . . . � . . . � aPages[0]� aPages[0]� aPages[0]� aPages[15]� aPages[15]� aPages[15]� � �����O����� � . . . . . . � PFN� PFN� PFN� PFN� PFN� PFN� � � Memblock� � 4GB� 2GB� � Section[0]� 0� Section[0]� Section[63]� Memory Mapping� Section[1]� �����O�����