清華大學 陳渝老師 操作系統教程

起因

• 程序規模的增長速度遠遠大于存儲器容量的增長速度
• 理想中的存儲器
• 更大、更快、更便宜的非易失性存儲器
• 實際中的存儲器
• 在計算機系統中，尤其是在多道程序運行的環境下，可能會出現内存不夠用的情況，怎麼辦?
• 如果是程序太大，超過了内存的容量，可以采用手動的覆蓋（overlay)技術，隻把需要的指令和數據保存在内存當中
• 如果是程序太多，超過了内存的容量，可以采用自動的交換（( swapping)技術，把暫時不能執行的程序送到外存中;
• 如果想要在有限容量的内存中，以更小的頁粒度為單位裝入更多更大的程序，可以采用自動的虛拟存儲技術。

覆蓋技術

• 目标
• 實在較小的可用内存中運行較大的程序
• 常用于多道程序系統，與分區存儲管理配合使用
• 原理
• 把程序按照其自身邏輯結構，劃分為若幹個功能上相對獨立的程序模塊，那些不會同時執行的模塊共享同一塊内存區域，按時間先後來運行
• 必要部分（常用功能）的代碼和數據常駐内存
• 可選部分（不常用功能）在其他程序模塊中實現，平時存放在外存中，在需要用到時才裝入内存
• 不存在調用關系的模塊不必同時裝入到内存，從而可以相互覆蓋，即這些模塊共用一個分區
• 缺點
• 由程序員來把一個大的程序劃分為若幹個小的功能模塊，并确定各個模塊之間的覆蓋關系，費時費力，增加了編程的複雜度
• 覆蓋技術從外存裝入内存，實際上是以時間延長來換取空間節省

交換技術

• 目标
• 多道程序在内存中時，讓正在運行的程序或需要運行的程序獲得更多的内存資源
• 方法
• 可将暫時不能運行的程序送到外存，從而獲取空閑内存空間
• 操作系統把一個進程的整個地址空間的内容保存到外存中（換出swap out），而将外存中的某個進程的地址空間讀入到内存中（換入swap in）。換入換出内容的大小為整個程序的地址空間
• 技術實現的問題
• 交換時機的确定
• 何時需要發生交換
• 隻有當内存空間不夠或有不夠的危險時換出
• 交換區的大小
• 必須足夠大以存放所有用戶進程的所有内存映像的拷貝
• 必須能對這些内存影響進行直接存取
• 程序換入時的重定位
• 換出後再換入的内存位置一定要在原來的位置上嗎
• 最好采用動态地址映射方法
• 覆蓋與交換的比較
• 覆蓋
• 發生在運行程序的内部
• 隻能發生在那些相互之間沒有調用關系的程序模塊之間
• 程序員必須給出程序内的各個模塊之間的邏輯覆蓋結構
• 交換
• 發生在内存中程序與管理程序或操作系統之間
• 是以内存中的程序大小為單位來進行的
• 不需要程序員給出各個模塊之間的邏輯覆蓋關系

虛存技術

• 目标
• 遇到的問題
• 在内存不夠的情形下，可以采用覆蓋技術和交換技術，但
• 覆蓋技術：需要程序員自己把整個程序劃分為若幹個小的功能模塊，并确定各個模塊之間的覆蓋關系，增加了程序員的負擔
• 交換技術：以進程作為交換的單位，需要把進程的整個地址空間都換進換出，增加了處理器的開銷
• 解決方法
• 虛拟内存管理技術（虛存技術）
• 像覆蓋技術那樣，不是把程序的所有内容都放在内存中，因而能夠運行比當前空間還要大的程序。但做得更好，由操作系統自動來完成，無需程序員的幹涉
• 像交換技術那樣，能夠實現進程在内存與外存之間的交換，因而獲得更多的空間空閑内存空間。但做得更好，隻對進程的部分内容在内存和外存之間進行交換。
• 程序局部性原理
• 指程序在執行過程中的一個較短時期，所執行的指令地址和指令的操作數地址，分别局限于一定區域。
• 時間局部性
• 一條指令的一次執行和下次執行，一個數據的一次訪問和下次訪問都集中在一個較短時期内
• 空間局部性
• 當前指令和鄰近的幾條指令，當前訪問的數據和臨近的幾條數據都集中在一個較小區域内
• 基本概念
• 可以在頁式或段式内存管理的基礎上實現
• 在裝入程序時，不必将其全部裝入到内存，而隻需要執行的部分頁面或段裝入到内存，就可讓程序開始執行
• 在程序執行過程中，如果需執行的指令或訪問的數據尚未在内存（稱為卻頁或缺段），則由處理器通知操作系統将相應的頁面或段調入到内存，然後繼續執行程序
• 另一方面，操作系統将内存中暫時不使用的頁面或段調出保存在外存上，從而騰出更多空閑空間存放将要裝入的程序以及将要調入的頁面
• 基本特征
• 大的用戶空間
• 通過把物理内存與外存相結合，提供給用戶的虛拟内存空間通常大于實際的物理内存，即實現了兩者的分離。
• 如32位虛拟地址理論上可以訪問4GB，而可能計算機上僅有256M的物理内存，但硬盤用量大于4GB
• 部分交換
• 與交換技術相比較，虛拟存儲的調入和調出是對部分虛拟地址空間進行的
• 不連續性
• 物理内存分配不連續，虛拟地址空間使用不連續
• 虛拟頁式内存管理
• 大部分虛拟存儲系統都采用虛拟頁式存儲管理技術，即在頁式存儲管理的基礎上，增加請求調頁和頁面置換功能
• 基本思路
• 當一個用戶程序要調入内存運行時，不是将該程序的所有頁面都裝入内存，而是隻裝入部分頁面，就可啟動程序運行
• 在運行過程中，如果發現要運行的程序或要訪問的數據不在内存，則向系統發出缺頁中斷請求，系統在處理這個中斷時，将外存中相應的頁面調入内存，使得該程序能夠繼續運行
• 頁表表項
• 駐留位
• 表示該頁是在内存還是在外存。如果該位等于1，表示該頁位于内存當中，即該頁表項是有效的,可以使用：如果該位等于0，表示該頁當前還在外存當中，如果訪問該頁表項,将導緻缺頁中斷；
• 保護位
• 表示允許對該頁做何種類型的訪問，如隻讀、可讀寫、可執行等；
• 修改位
• 表明此頁在内存中是否被修改過。當系統回收該物理頁面時，根據此位來決定是否把它的内容寫回外存；
• 訪問位
• 如果該頁面被訪問過（包括讀操作或寫操作），則設置此位。用于頁面置換算法。
• 缺頁中斷
• 缺頁中斷處理過程
• 1.如果在内存中有空閑的物理頁面，則分配一物理頁幀f，然後轉第4步；否則轉第2步；
• 2.采用某種頁面置換算法，選擇一個将被替換的物理員幀f，它所對應的邏輯頁幀為q。如果該頁在内存期間被修改過。則需把它寫回外存；
• 3.到q所對應的頁表項進行修改，把駐留位置為0；
• 4.将需要訪問的頁p裝入到物理頁面f當中；
• 5.修改p所對應的頁表項的内容，把駐留位置為1，把物理頁幀号置為f；
• 6.重新運行被中斷的指令。
• 後備存儲Backing Store
• 在何處保存未被映射的頁
• 能夠簡單地識别在二級存儲器中的頁
• 交換空間（磁盤或者文件）：特殊格式，用于被映射的頁面
• 概念
• 一個虛拟地址空間的頁面可以被映射到一個文件（在耳機存儲中）中的某個位置
• 代碼段
• 映射到可執行二進制文件
• 動态加載的共享庫程序段
• 映射到動态調用的庫文件
• 其他段
• 可能被映射到交換文件
• 虛拟内存性能
• 為了便于理解分頁的開銷，使用有效存儲器訪問的時間effective memory access time（EAT）
• EAT = 訪存時間 * 頁表命中幾率 page fault處理時間 * page fault幾率
• eg
• - page fault幾率：缺頁幾率 - dirty page幾率：對頁進行寫操作幾率

,