作業系統 第九章 虛擬記憶體.

Slides:



Advertisements
Similar presentations
渡黑水溝 郁永河. 2 戎克船:是明末清初時期往返兩岸的主要交通工具 ∗ 1. 關於台灣的開發歷史,我們到底了解多少呢?不妨試著說出 就我們所知有關台灣開發史的故事、小說、電影、音樂與大 家分享。 ∗ 2. 什麼是黑水溝?黑水溝為什麼會成為大陸移民渡海來臺時最 大的威脅? ∗ 3. 有聽過「六死三留一回頭」、「有唐山公,無唐山嬤」這兩.
Advertisements

定 格 入 格 破 格 —— 新诗仿写复习训练 仿照下列句子,再把 “ 人生 ” 比喻成 “ 大海 ”“ 天空 ” , 造两个句子。 如果说人生是一首优美的乐曲,那么痛苦则 是其中一个不可或缺的音符。 参考答案: 1 、如果说人生是一望无际的大海,那么挫折则 是其中一个骤然翻起的浪花。 2 、如果说人生是一片湛蓝的天空,那么失意则.
步步为营 面面俱到 步步为营 面面俱到 —— 高考语文首轮复习策略 章惠西 浙师大附中. [2014] 阅读下面文字,根据要求作文( 60 分) 门与路,永远相连。 门是路的终点,也是路的起点。它可以 挡住你的脚步,也可以让你走向世界。 大学的门,一边连接已知,一边通向未知。学习、探索、创 造,是它的通行证;大学的路,从过去到未来,无数脚印在此交.
大學甄選入學 個人申請面試技巧 黃仁竑 教授 中正大學資工系. 大綱 面試目的 面試流程 面試技巧 ( 注意事項 ) 結語.
------课题(一) :PLC控制系统设计
第2章 证券市场的运行与管理.
王 子 坊 《洛陽伽藍記》 主講教師:張其昀.
统计学原理 雷州市 广播电视大学 教师进修学校 陈宏渊.
上海交通大学医学院 “十二五”学科建设与科技创新规划 汇 报 科技发展处 二○一○年十一月十日 1.
古代汉语 长江大学汉语教研室.
应用型人才培养 与教学质量建设 季桂起
第四章 汇率与汇率制度 第一节 外汇与汇率 一、外汇 (一)外汇有狭义与广义之分
手太阳小肠经.
第八章 中国旅游文学知识.
第四章奴隶社会的繁荣---西周 周武王灭商建立西周,这是中国奴隶社会的繁荣时期,也是世界上较强盛的奴隶制王朝,从公元前1046年到公元前771年,前后历时276年,传12王。
5月5日——世界手卫生日 2013年5月——我院“手卫生月”
游泳四式技術分析暨初級教法.
第二章 语音 第六节 音变 轻 声1.
第二章 项目一:企业厂区与车间平面设计 1.
《学校卫生综合评价》 GB/T 解读 武汉市卫生监督所 唐 莉 二O一五年四月.
第2章:企業組織 張緯良 世新大學資訊管理系.
操作系统 Operating System.
第五章 资源分配与调度 (一) 资源管理功能 (二) 资源分配的机构和策略 (三) 死锁概念.
孟子名言 1. 幼吾幼,以及人之幼。 2.天时不如地利, 。 3. ,威武不能屈。 4.得道者多助, 。 5.穷则独善其身, 。 6.
寡人之于国也 《孟子》.
第8章 机床操作 主讲:臧红彬 博士.
第三章 处理机调度与死锁 3.1 处理机调度的基本概念 3.2 调度算法 3.3 实时调度 3.4 多处理机系统中的调度
第四章 存储器管理.
William Stallings 计算机组成与结构(第8版)
報告人:萬華國中 吳菜霞校長 中華民國103年11月27日
大连理工大学软件学院 软件工程系 赖晓晨 计算机组成与结构 大连理工大学软件学院 软件工程系 赖晓晨
社群運作& 課綱轉化教學示例分享 楠梓國中 曾怡菁 2016/03/11.
学校卫生安全管理 培 训 会 2013年12月.
小小节水员自然科普课
寫 作 教 學 6 電腦與我 時代改變,科技進步,電腦成為日常生活不可或缺的設備。我是二十一世紀的E世代少年,一隻滑鼠在手,樂趣無窮。
在山的那边 王家新.
初中獨立專題探究(文字模式) 課程規劃與教學經驗分享
主板整体维修思路 1、加电保护 现象:触发上电,风扇 转一下就停,同时能听见电源发出‘滋啦’一声异 响,再次触发,不上电。
上海市闸北区卫生信息平台 标准化成熟度测试工作汇报 上海市闸北区卫生局 2013年6月27日.
105學年度高一普通科(1~8班) 新生選修課程說明
數位邏輯的基礎.
ET200S应用问题 1、ET200S程序无法下载解决方案 2、ET200S单独使用时输入输出模块无法监控.
第二章 Modicon Micro PLC 的结构及基本指令
S 数控机床故障诊断与维修.
你 今 天 微 笑 了 嗎? 至下一張 結束放映.
作業系統 第三章 作業系統結構.
第三章 PLC基础 掌握PLC工作原理、结构特点。 熟悉基本逻辑指令、顺序控制指令及常用的功能指令。 具备PLC应用系统设计初步能力。
第四章 存储器管理 4.1 存储器的层次结构 4.2 程序的装入和链接 4.3 连续分配方式 4.4 基本分页存储管理方式
第一章.
浙江大学医学院公共技术平台 实验仪器预约管理系统系列培训 医学院公共技术平台 丁巧灵
伯乐相马的故事 相传伯乐是春秋时代人,姓孙名阳。据说,有一匹千里马拉着沉重的盐车翻越太行山。在羊肠小道上,马蹄用力挣扎,膝盖跪屈;尾巴下垂着,皮肤也受了伤;浑身冒汗,汗水淋漓,在山坡上艰难吃力地爬行还是拉不上去,伯乐遇见了,就下了自己的车,挽住千里马而对它淌眼泪,并脱下自己的麻布衣服覆盖在千里马身上。千里马于是低下头吐气,抬起头来长鸣,嘶叫声直达云霄。这是它感激伯乐了解并且体贴它啊。
-評臺北高等行政法院96年度訴更一字第00131號判決 邵瓊慧律師
第七章  事业单位支出的核算      §第一节  支出概述     §第二节  拨出款项     §第三节  各项支出     §第四节  成本费用.
消毒基本知识介绍 西城区疾病预防控制中心
第3章 PLC的结构特点及技术性能 3.1 可编程控制器的结构特点 3.2 FX2N系列PLC的主要技术性能.
第一章 緒論 1-2物理量的單位.
第五章 虚 拟 存 储 器 5.1 虚拟存储器概述 5.2 请求分页存储管理方式 5.3 页面置换算法 5.4 “抖动”与工作集
某公司基于战略地图的KPIS分解和提取.
课题1 原子的构成 独 秀 初 中 孙 长 舟.
李元金 计算机与信息工程学院 第 14 讲 存储器管理(3) 李元金 计算机与信息工程学院 1/
題目: 分散式物品搜尋器 指導教授: 黃慶祥 組員名稱: 黃偉聖 郭惠榮 楊勝凱 報告人: 黃偉聖
第十章 直接存储器存取(DMA)控制.
網路資源的應用-抓圖 李俊賢.
李元金 计算机与信息工程学院 第7讲 处理机调度与死锁(1) 李元金 计算机与信息工程学院 1/
进程调度算法和作业调度算法。 (1) 先来先服务(FCFS)调度算法
赤壁赋 苏轼. 赤壁赋 苏轼 赋是一种有韵的文体,讲求声律、押韵、对比等形式,有辞赋、骈赋和律赋等。 关于赋 赋是一种有韵的文体,讲求声律、押韵、对比等形式,有辞赋、骈赋和律赋等。     
临床试验管理平台操作指南 (申办方用) 浙江省人民医院机构办.
李元金 计算机与信息工程学院 第 17 讲 设备管理(1) 李元金 计算机与信息工程学院 1/
第8章 输入/输出设备 I/O设备是计算机系统与外界交换信息的装置。从计算机系统结构来讲,CPU和主存储器合称为主机,而输入/输出设备独立于主机之外,因此又称为外部设备。
第六章 直接成本法.
Presentation transcript:

作業系統 第九章 虛擬記憶體

第九章 虛擬記憶體 背景介紹 基本概念 需求分頁 需求分頁效能 分頁替換 頁框配置 輾轉現象 實作議題 摘要

虛擬記憶體 實體記憶體管理的目的: 行程的大小與數目受限於實體記憶體的容量 虛擬記憶體:允許程式不必完全載入到記憶體中就可以執行的機制 同時執行多個行程,並對CPU作最有效的利用 行程的大小與數目受限於實體記憶體的容量 虛擬記憶體:允許程式不必完全載入到記憶體中就可以執行的機制 能夠執行記憶體需求大於實體記憶體空間的程式 程式規劃上變得容易 頁框配置的原則與方法 使用需求分頁來探討虛擬記憶體 系統設計上需要考量的因素,如預先分頁、程式結構、分頁大小等

基本概念(1) 如果只需要部份程式在記憶體中就可以執行,會有下列優點: 程式不會被實體記憶體的容量所限制 程式設計師可以設計超過實體記憶體容量的程式;簡化程式設計的工作。 剩餘的記憶體空間可以讓更多行程同時在記憶體中執行 可增加CPU使用率與產量 反應和回覆時間並不因此增加。 置換次數會減少;每一個使用者程式平均可以更快地被執行

基本概念(2) 虛擬記憶體的基本想法: 僅把目前需要的部份程式載入到主記憶體 其餘的則儲存在磁碟中,等到有需要時再載入 程式設計師所能運用的記憶體容量,從原來的實體記憶體空間增加到整個磁碟的空間 透過記憶體管理單元的硬體支援,將邏輯位址轉換成實體位址;如果所要的資料不在實體記憶體中,會從磁碟中載入

虛擬記憶體下的位址轉換 位址匯流排 CPU MMU 記憶體 磁碟 邏輯位址 實體位址

基本概念(3) 虛擬記憶體的機制 區域性 區域性的觀點:執行時所參考到的同分頁中的指令會頻繁地被重複執行 使用需求分頁或是需求分段的方式來實作 區域性 時間區域性:最近執行過的指令經常會一再地被行程執行 空間區域性:執行過的指令,其附近的指令很快會被執行的機率相當大 區域性的觀點:執行時所參考到的同分頁中的指令會頻繁地被重複執行

需求分頁(1) 只將部份程式的分頁載入到記憶體中;只在行程需要執行某分頁時,才將此分頁載入到記憶體中 分頁表中的效用位元 被設定為 v :表示此分頁是有效的,且放在記憶體中 被設定為 i ;表示此分頁可能不是有效的 此分頁沒有用 此分頁是有效的但目前卻放在磁碟上 磁碟:儲存不在記憶體的分頁所用的置換裝置;為此目的而使用的磁碟區段稱為置換區域(較大的獨立連續區塊) 所有行程被換出的分頁會被儲存在置換區域中 在置換區域中進行需求分頁 一次將行程所需要的分頁由置換區域中置入記憶體,不是一頁一頁地置入,以增進分頁效率

效用位元、置換區域與置換裝置 A B C D 程式1 2 5 i v 分頁表 效用位元 1 3 4 6 7 主記憶體 置換裝置(磁碟) 1 3 4 6 7 主記憶體 置換裝置(磁碟) 置換區域 …

需求分頁(2) 分頁錯誤:若一個行程想要使用一個不在記憶體中的分頁(存取一個標記為無效的分頁) 作業系統產生例外中斷,此中斷之因是作業系統沒有把行程需要用的分頁載入到記憶體中,而不是企圖存取一個不合法的記憶體位址

需求分頁(3) 分頁錯誤處理的過程 參考分頁表,決定是有效或是無效的記憶體參考 若無效,則終止該行程執行;若合法,但此分頁尚未載入到記憶體中,則對作業系統發出分頁錯誤的例外中斷 作業系統在磁碟中找尋引發分頁錯誤的分頁。 在記憶體中找出一個頁框,並排定一個磁碟 I/O,把引發分頁錯誤的分頁載入到該頁框中 修改分頁表把此頁框設成有效(該分頁已經載入到記憶體中) 重新執行引發分頁錯誤的指令

分頁錯誤處理步驟 2.中斷 可用頁框 主記憶體 jump func1 move ax,bx … 作業系統 func1: i 分頁表 磁碟 4.載入產生分頁錯誤的頁 5.設定分頁表 1.參考分頁表 3.找尋產生分頁 錯誤的頁 6.重新執行指令

需求分頁(4) 分頁錯誤發生時,要儲存: 分頁錯誤處理完畢後,再把行程的狀態全都還原,並繼續執行此行程 當時被中斷的行程狀態,包含暫存器、狀態碼、程式計數器等 分頁錯誤處理完畢後,再把行程的狀態全都還原,並繼續執行此行程 執行行程的第一個指令時就會發生分頁錯誤,行程會不斷地發生分頁錯誤,直到所有目前需要的分頁都載入到記憶體為止,之後行程就可以順利執行 純粹需求分頁,就是在需要某分頁時才將那分頁載入執行

需求分頁(5) 嚴格要求在分頁錯誤發生後,要能夠重新執行任何的指令;容易達到! 分頁錯誤發生在 指令擷取的階段:藉由重新擷取指令來重新開始執行 運算元擷取時:必須重新再擷取指令,並將指令解碼,然後擷取運算元 儲存結果的階段時:要重新開始執行包含了指令擷取、運算元擷取、執行運算等步驟 主要的困難:一個指令執行時有可能會修改到很多不同的資料,導致無法重新執行指令

需求分頁效能(1) 評估需求分頁的效能:計算有效存取時間 大多數的電腦系統中,記憶體存取時間都介於 10 奈秒與 200 奈秒間 若無分頁錯誤,有效存取時間將會和記憶體存取時間相同;若發生分頁錯誤,將從磁碟中讀入相關的分頁存取想要的位元組 假設分頁錯誤發生的機率為 p, p 介於 0 與 1 之間 有效存取時間為(1–p)× t + p × 分頁錯誤處理時間 如果 p 能夠相當地接近 0,有效存取時間可以非常接近記憶體存取時間

需求分頁效能(2) 分頁錯誤時系統所進行的處理: 硬體對作業系統發出例外中斷 儲存行程的狀態及一般暫存器內容 作業系統判斷是否發生分頁錯誤 作業系統檢查邏輯位址是否有效 若沒問題,則找出所需要被載入記憶體的分頁;要求一個空的頁框 假如沒有空的頁框,則利用分頁替換演算法決定要替換那一個分頁 若所選擇的頁框資料已被更改過,則發生內文切換,暫停發生分頁錯誤的行程,直到要剔除的分頁儲存回硬碟

需求分頁效能(3) 若所選擇的分頁資料末經更改,或是資料已被寫回硬碟中,作業系統會安排一個磁碟 I/O 將所需要的分頁載入 在等待 I/O 完成時, CPU 先內文切換到別的行程 當分頁已被載入,分頁表更新,所對應的頁框也顯示有效狀態 發生分頁錯誤的行程等待重新拿回 CPU 使用權 還原暫存器、新的分頁表和其它變動的資訊,繼續執行此行程

需求分頁效能(4) 處理分頁錯誤所花費的時間分為 3 部份 第1和第3部份可藉由撰寫程式碼的技巧而降低 處理分頁錯誤所產生的中斷 讀取分頁 重新執行行程 第1和第3部份可藉由撰寫程式碼的技巧而降低 分頁的替換時間大致為 25 毫秒,一個典型的硬碟平均有 8 毫秒的旋轉延遲時間、15 毫秒的搜尋時間、與1毫秒的資料傳遞時間,因此總共的分頁時間接近 25 毫秒 這包含了硬體與軟體所需的時間

需求分頁效能(5) 假設平均 25 毫秒的分頁錯誤處理時間及 100 奈秒記憶體存取時間 有效存取時間與分頁錯誤率成正比 有效存取時間=(1-p)×100 + p × 25 毫秒 =(1-p)×100 + p × 25000000 = 100 + 24999900 × p 有效存取時間與分頁錯誤率成正比 在需求分頁的系統中,降低分頁錯誤發生的次數很重要 不然有效存取時間的增加,會大幅延遲行程的處理時間

第九章 虛擬記憶體 背景介紹 分頁替換 頁框配置 輾轉現象 實作議題 摘要 先進先出演算法 最佳演算法 最久未用演算法 最久未用近似演算法 最不常用演算法 最常用演算法 分頁緩衝演算法 頁框配置 輾轉現象 實作議題 摘要

分頁替換(1) 行程在執行時若只需要載入行程所要使用的分頁 程式多元度提高 CPU 使用率與產量提高 記憶體頁框的使用率提高 指系統同時有多個程式執行的程度 一般來說,程式多元度越高越好 CPU 使用率與產量提高 記憶體頁框的使用率提高

分頁替換(2) 發生分頁錯誤時,若記憶體中已經沒有空的頁框,解決方法如下: 可終止發生分頁錯誤的行程 不是一個好方法,因為此行程可能很重要,不允許被終止 可選擇將在記憶體中的某行程置換掉,將它所使用的頁框全部都空出來 降低程式多元度 利用分頁替換,替換出其它的分頁以載入行程目前所需要的分頁

分頁替換(3) 使用分頁替換,若無空頁框可使用,需在記憶體中選擇一個替換分頁將它寫入磁碟中修改被替換的行程分頁表把引起分頁錯誤的分頁載入到空出的頁框中修改引起分頁錯誤的行程分頁表 需要替換兩頁 一從記憶體換出到磁碟,另一從磁碟置入記憶體中 磁碟 I / O 非常花時間,故利用修改位元來減少分頁的替換次數 當有某個位元組被寫入到某分頁時,此分頁所屬的修改位元被硬體設定為 i 表示此分頁已被修改;否則對應的修改位元為 v ,表示此分頁只進行讀取沒有任何寫入 進行分頁替換時,會先選擇沒有被修改過的分頁進行替換,置入的分頁直接覆蓋該頁框即可,可以減少替換一個分頁的時間

分頁的替換 磁碟 2 8 i v 分頁表 修改位元 主記憶體 替換頁 置換區域

分頁替換(4) 評估一個分頁替換法的好壞 以分頁錯誤比率來當標準 如果一個分頁替換演算法不好 所有使用分頁的編號稱為參考字串 會增加分頁錯誤的次數 會降低程式執行的速度 並不會造成程式的執行結果不正確 所有使用分頁的編號稱為參考字串

先進先出演算法(1) 每次有新的分頁需置入時,會選擇置入記憶體時間最久的分頁換出 兩種實作的方法: 記錄每個分頁被置入到頁框的時間,當每次需要換出分頁時,會找置入時間最早的一頁 利用 FIFO 佇列來實作,當要進行分頁替換時,就把佇列最前端的分頁換出,再把要置入的分頁放到佇列的末端 Belady 反常:配置的頁框數目增加,分頁錯誤次數有可能會增加

先進先出分頁替換法 P 3 1 2 4 初始時均為空的 頁框 時間 9 次分頁失誤

先進先出演算法(2) 4 1 P 2 3 初始時均為空的 頁框 時間 10 次分頁失誤

最佳演算法(1) 分頁錯誤比率最低 替換未來最不可能被使用到的分頁 保證在頁框的數目固定之下,會得到最少的分頁錯誤次數 實際上無法實作,因為對於未來將要使用的分頁不可能完全預測成功 可提供分頁替換演算法的比較基準

最佳演算法(2) P 4 3 2 1 初始時均為空的 頁框 時間 7 次分頁失誤

最久未用演算法(1) 近似最佳演算法:把頁框中最久未被使用到的分頁替換出去 當記憶體中的某分頁被存取時,重新給予該分頁一個時間標記(不同於先進先出演算法) 對於行程的區域性而言,此方法最佳,但系統所花費的代價卻十分昂貴 在記憶體中維護一個以最近的存取時間標記排序的鏈結串列 每次行程使用過一分頁後,就必須對鏈結串列作一次更新,並可能要刪除其中一個分頁作替換,後者是最花時間的動作

最久未用演算法(2) 其它方式實作,需要硬體的支援 有了硬體的支援,可降低額外的負擔 在 CPU 中加入一個邏輯時鐘或計數器;在分頁表中的每個項目都增加時間欄位 行程每使用一分頁後,就把 CPU 的邏輯時鐘加一,並將邏輯時鐘的數值寫入時間欄位 要進行分頁替換時,系統檢查分頁表中所有項目的時間欄位值,找到最小的,並把此分頁替換掉 有了硬體的支援,可降低額外的負擔

最久未用演算法(3) P 4 3 2 1 初始時均為空的 頁框 時間 7 次分頁失誤

最久未用近似演算法(1) 使用參考位元來達到近似最久未用演算法的效果 分頁表中的每個項目都加上一個參考位元,預設為 0;當某個分頁被行程使用,參考位元會被設定為 1 利用參考位元可知哪些分頁曾被行程使用過 雖然無法得知這些分頁被行程使用的先後順序,卻是最簡單的最久未用近似演算法 其他的最久未用近似演算法:額外參考位元演算法 記憶體中,每個頁框設置一組參考位元與移位暫存器,均初始化為 0

最久未用近似演算法(2) 每經過一次計時器中斷,行程會把控制權交給作業系統。若頁框中的分頁正被該行程所使用,則將頁框的參考位元設定為 1;反之則設定為 0 每隔一段時間發出中斷,作業系統將頁框的參考位元右移入移位暫存器 作業系統比較所有頁框移位暫存器數值的大小,數值最小的分頁,就是最久未被行程所使用的分頁,便優先替換此頁框內的分頁 移位暫存器的數值可作為判斷分頁多常被行程使用的基準 如果數值很大,表示此分頁常被行程使用 可能有好幾個頁框移位暫存器的數值是相同的,它們是否要被替換,端看系統選用的方式

額外參考位元演算法 4 5 2 3 1 01000100 00100110 10110010 00001110 01101010 參考位元 移位暫存器 使用中 主記憶體

最久未用近似演算法(3) 其他的最久未用近似演算法:二次機會演算法 移位暫存器的大小設定為 0 個位元 記憶體中每個頁框均對應到一個參考位元,其初始值為 0;當某分頁被行程使用時,該參考位元會被設定為 1 進行分頁替換時,以先進先出的方式找尋被替換分頁;若找到的頁框參考位元為 0,則進行替換;若參考位元為 1,則將此分頁的參考位元設定為 0,給予此分頁第二次機會,不馬上將它替換;並把此分頁的時間標記設為目前的時間 繼續用先進先出的方式找尋被替換分頁,直到所有其它的分頁都被替換掉,或是都被給予第二次機會之後,該分頁才會被替換掉 利用鏈結串列較無效率,可換用環狀佇列方式

二次機會演算法-鏈結串列 A B C D E F G H 3 7 8 12 14 15 18 20 (a) (b) 最先載入的頁 A B C D E F G H 3 7 8 12 14 15 18 20 (a) (b) 最先載入的頁 最常參考的頁 視A如新載入的分頁 參考位元 0 參考位元 1

二次機會演算法-環狀佇列 C 參考位元 0 參考位元 1 L B D E F G H I A J K

最久未用近似演算法(4) 其他的最久未用近似演算法:加強二次機會演算法 和二次機會演算法相同,但增加了修改位元 作業系統會每隔一段時間將分頁的參考位元設定為 0(表示因太久未再參考而視為新載入的分頁) 此 2 位元有下列 4 種組合,依據順序進行替換 (0, 0):表示最近沒有被行程使用,也沒有被行程修改,是最佳的替換分頁 (0, 1):表示最近沒有被行程使用,但是已經被修改過,此分頁須先寫回磁碟後,才可進行替換 (1, 0):表示最近曾被行程使用,但是沒被修改過,由於可能再次被使用,故盡量不要替換此分頁 (1, 1):表示最近曾被行程使用,也被修改過,所以需寫回磁碟中,是最差的替換分頁選擇

最不常用演算法 參考存取頻率 每分頁均使用一個計數器來計算被行程使用過的次數,初始值為 0 ;當某分頁被行程使用或修改時,對應的計數器便加 1 進行分頁替換時,找尋計數器值最小的分頁進行替換 問題:某一分頁剛開始常常被行程使用,經過一段時間這分頁不再被使用,但因計數器的值已累加到很大,所以會被一直留在記憶體中 解決方法:系統每經過一段時間,就將分頁的計數器數值向右移動一個位元(除以 2),以降低所記錄的使用次數,讓分頁有機會被替換出去

最常用演算法 與最不常使用演算法相反:當要進行分頁替換時,找計數器值最大的分頁進行替換 原因:在記憶體中使用很頻繁的分頁,行程可能已經執行完畢了,之後不會再被使用 不一定是好方法,因為在記憶體中頻繁使用的分頁,通常都很重要,可能在不久的將來就會再次被使用

分頁緩衝演算法(1) 分頁替換的步驟: 必須先等待替換分頁寫回磁碟後,才能進行後續的動作 把被替換的分頁移出記憶體並寫回磁碟裡 將要載入的分頁,由磁碟置入到記憶體中 執行該分頁的程式或是存取資料 必須先等待替換分頁寫回磁碟後,才能進行後續的動作 將分頁寫回磁碟的動作並不緊急,所以可以等到系統有空的時候再做

分頁緩衝演算法(2) 系統內除了主記憶體的頁框外,還要有幾個可用的頁框當作分頁緩衝區 分頁錯誤發生時 行程能很快地繼續執行 先將要載入到記憶體的分頁,由磁碟載入到分頁緩衝區中 將緩衝區中的該分頁併入到主記憶體中,然後執行此分頁的程式或是存取資料 再從主記憶體中挑選被替換分頁,將它寫回到磁碟中 再把空出來的頁框併入到分頁緩衝區中 行程能很快地繼續執行

分頁緩衝區演算法 替換分頁 分頁緩衝區 置入分頁 主記憶體 磁碟 1 2 3 4

第九章 虛擬記憶體 背景介紹 分頁替換 頁框配置 最少頁框數目 配置演算法 全域與區域配置 輾轉現象 實作議題 摘要

頁框配置 多行程的記憶體環境中,重要的事是要決定一個行程能夠配置多少個頁框 好的頁框配置演算法能增進系統效能 配置過多,造成空間上的浪費,當行程更多,將會找不到可用的頁框來置入行程的分頁 配置過少,會造成行程頻繁地發生分頁錯誤 好的頁框配置演算法能增進系統效能

最少頁框數目(1) 行程能正常執行所需的最少頁框數目與 CPU 結構和指令架構有關 指令架構: 直接定址:需要一個放置頁框儲存指令的分頁,另一個存放頁框儲存資料所在的分頁每個行程至少要配置 2 個頁框 間接定址:需要一個存放頁框儲存指令所在的分頁、一個儲存頁框儲存資料位址的分頁、還有一個放置頁框儲存資料的分頁每個行程至少需要 3 三個頁框 若只分配兩個頁框,每當 CPU 處理間接定址指令時,就會發生分頁錯誤,因而降低系統效率

直接定址 運算子 記憶體位置 指令儲存頁 資料儲存頁 主記憶體 指令

間接定址 指令儲存頁 主記憶體 資料儲存頁 資料位址儲存頁 運算子 記憶體位置 指令

最少頁框數目(2) CPU 結構:有多個一般暫存器的架構下,可以把指令分成 最大的頁框數目,可由實體記憶體的容量來決定 含有 2 個運算元的系統: 假如每一個運算元都使用間接定址的方式 一個運算元會需要兩個頁框,而指令需要一個頁框,因此每個行程最少需要 1 + 2 × 2 = 5 個頁框 含有 3 個運算元的系統:若使用間接定址,每個行程最少需要 1 + 2 × 3 = 7 個頁框 最大的頁框數目,可由實體記憶體的容量來決定

二運算元指令與三運算元指令 運算子 運算元 1 運算元 2 運算元 3

配置演算法 若系統中有 m 個頁框要分配給 n 個行程: 兩種配置方法下,分配給每個行程的頁框數目都會因為程式多元度而改變 不公平,分頁錯誤發生的次數會增加 比例配置的方法:假設行程 Pi 的大小為 Si,系統中可用的頁框數目為 m,則 Pi 可分配到 Si / S × m 個頁框,其中 S 為所有行程大小的總和 兩種配置方法下,分配給每個行程的頁框數目都會因為程式多元度而改變 程式多元度提高,每個行程需釋放一些頁框給新的行程使用;程式多元度降低,要離開的行程頁框會分配給仍在執行的行程

全域與區域配置(1) 全域配置:當一個行程要進行分頁替換,可從記憶體中所有的頁框中挑選被替換分頁(一個行程可以從其它行程獲得一個頁框) 區域配置:每個行程所使用的頁框數不會改變;進行分頁替換時,由該行程所擁有的頁框中挑選出被替換分頁 全域配置的方式較好 若使用區域配置,當一個行程需要額外的頁框載入分頁,但由於配置固定頁框數目,此行程仍會頻繁地發生分頁錯誤 若使用全域配置,可以增加許多被替換分頁的選擇

全域與區域配置(2) 主記憶體 5 4 8 3 2 6 參考次數 (a) A2 A3 B1 B2 C1 C2 C3 A1 A4 (b)

第九章 虛擬記憶體 背景介紹 分頁替換 頁框配置 輾轉現象 輾轉現象的成因 工作集合模型 分頁錯誤頻率 實作議題 摘要

輾轉現象的成因(1) 不停地把之後會使用到的分頁換出,並隨後再立刻置入 造成分頁在記憶體與磁碟中來回搬動,卻做虛工 當 CPU 使用率低時,CPU 排程器為了增加 CPU 的使用率,會提高程式多元度(在輸入佇列中選擇一個行程載入) 因為此新的行程需要使用到許多頁框,系統若採用全域配置頁框,此行程可能會搶其他行程所使用的頁框, 但若其它行程在執行時也需要這些被換出的分頁,又發生分頁錯誤,造成產生分頁錯誤的行程都在等待分頁裝置將它們所需要的分頁置入更造成 CPU 使用率降低

輾轉現象的成因(2) 當 CPU 排程器又發現 CPU 使用率降低,再載入一個等待執行的行程,此新的行程又會從其他行程中搶頁框,造成分頁錯誤的現象更加頻繁,使得 CPU 使用率降更低 此現象不斷發生,會使系統效率極低 行程所有的時間都花在分頁置換上面 當程式多元度增多,CPU 使用率將成長;之後,成長的幅度會趨緩;如果程式多元度繼續增加,系統會發生輾轉現象,使得 CPU 使用率快速降低 為了解除輾轉現象,系統必須減少程式多元度,使剩餘的行程有足夠頁框可用 減輕分頁錯誤現象;再度提高 CPU使用率

輾轉現象 C P U 使 用 率 程式多元度 輾轉現象

輾轉現象的成因(3) 系統要分配給每個行程多少頁框,才不會發生輾轉現象呢? 至少要有足夠的頁框可供目前區域性所涵蓋的分頁使用 減少行程發生分頁錯誤的機會 只要發現,增加行程的數目仍無助於提高 CPU 使用率,就可能發生輾轉現象

工作集合模型(1) 隨著行程的執行,區域性的改變,又會使分頁錯誤增加 工作集合:某段時間內行程使用過分頁的集合 藉由選擇適當工作集合,可代表程式執行的區域特性 當工作集合中所有的分頁都置入記憶體後,就不會發生分頁錯誤,直到行程執行的區域性改變為止 選擇適當的工作集合不容易 若選擇的工作集合太小:無法代表行程執行的區域性 若選擇太大的工作集合,可能會橫跨數個局部區域 在多元程式的環境下,許多分頁系統會記錄每個行程的工作集合,在行程重新執行前將所有工作集合中的分頁都置入記憶體中 可減輕分頁錯誤的發生 預先分頁:在行程尚未執行前先將分頁置入記憶體中

工作集合模型(2) 實作:作業系統記錄工作集合中存在哪些分頁 定義工作集合的大小為 n 利用老化演算法決定工作集合中的分頁,將太久沒用的分頁移出工作集合 做法:行程中每一分頁會對應到一個計數器,計數器中的 n 個位元由高而低分別代表最近 n 次行程對本分頁的使用與否 設定為 1 代表被行程使用,0 表示沒有被使用 須適當選用參數 n n 太小:工作集合無法代表行程的區域性 n 太大:會橫跨許多行程使用的區域,無法確定行程目前在哪一個局部區域中執行

工作集合模式 2 5 5 4 7 7 7 5 1 1 6 2 3 4 1 5 3 4 1 5 5 5 3 4 3 4 3 3 3 1 2 3 2 3 4 4 4 3 4 4 4 … n WS(t1)={1,4,5,7} t1 WS(t2)={3,4,5} t2

工作集合模型(3) 作業系統監督每個行程的工作集合 若能給予每個行程足夠的頁框,則不會發生分頁置換的問題 若系統內所有行程的所有工作集合所需頁框的總和超過記憶體所能提供就發生輾轉現象 解決方式:給予行程更多的頁框數目;或降低程式多元度 工作集合的做法可以有效預防輾轉現象;也盡可能維持較高的程式多元度,使 CPU 有較高的使用率

分頁錯誤頻率(1) 藉由控制系統中的分頁錯誤頻率以避免發生輾轉現象 作業系統中先定義分頁錯誤頻率的上限與下限 當某行程的分頁錯誤頻率大於系統定義上限,表示此行程所需頁框數目不足,必須再配置 若分頁錯誤頻率比下限還低,表示此行程擁有過多的頁框,系統可以收回未使用頁框 若行程的分頁錯誤頻率增加但系統中已無空頁框可使用 可暫停部份行程,將其頁框收回並配置給其餘行程使用

分頁錯誤頻率(2) 分頁錯誤率 配置頁框數目 上限 下限