分成兩個部分
第一部分：基本概念综慎、處理器管理具垫、存儲管理
第二部分：設備管理、文件管理殴穴、并發(fā)程序設計

操作系統(tǒng)原理

基本概念

計算機硬件系統(tǒng)

組成

image-20200429093334026

中央處理器

中央處理器是計算機的運算核心（Core）和控制單元（ Control Unit） 柴钻，主要包括：

• 運算邏輯部件： 一個或多個運算器
• 寄存器部件： 包括通用寄存器淮韭、 控制與狀態(tài)寄存器， 以及高速緩沖存儲器（Cache）
• 控制部件： 實現(xiàn)各部件間聯(lián)系的數(shù)據(jù)贴届、 控制及狀態(tài)的內(nèi)部總線靠粪； 負責對指令譯碼、發(fā)出為完成每條指令所要執(zhí)行操作的控制信號毫蚓、 實現(xiàn)數(shù)據(jù)傳輸等功能的部件

處理器與寄存器

image-20200429093613084

主存儲器

DRAM

外圍設備

設備類型

• 輸入設備

  鍵盤 鼠標

• 輸出設備

  顯示器

• 存儲設備

  1. 硬盤 如固態(tài)硬盤 機械硬盤 U盤等

  2. 光驅

     ····

• 網(wǎng)絡通信設備

  網(wǎng)卡等

設備控制方式

• 輪詢方式： CPU忙式控制+數(shù)據(jù)交換
• 中斷方式： CPU啟動/中斷+數(shù)據(jù)交換
• DMA方式： CPU啟動/中斷庇配， DMA數(shù)據(jù)交換

總線

簡介

總線（Bus） 是計算機各種功能部件之間傳送信息的公共通信干線， 它是CPU绍些、 內(nèi)存捞慌、輸入輸出設備傳遞信息的公用通道

計算機的各個部件通過總線相連接， 外圍設備通過相應的接口電路再與總線相連接柬批， 從而形成了計算機硬件系統(tǒng)

按照所傳輸?shù)男畔⒎N類啸澡， 總線包括一組控制線、 一組數(shù)據(jù)線和一組地址線

總線的類型

內(nèi)部總線： 用于CPU芯片內(nèi)部連接各元件

系統(tǒng)總線： 用于連接CPU氮帐、 存儲器和各種I/O模塊等主要部件

系統(tǒng)總線也有分級嗅虏，如下面的圖所示

通信總線： 用于計算機系統(tǒng)之間通信

系統(tǒng)總線

馮諾依曼結構

存儲程序計算機

馮·諾伊曼等人在1946年總結并明確提出，被稱為馮·諾伊曼計算機模型存儲程序計算機在體系結構上主要特點

• 以運算單元為中心上沐， 控制流由指令流產(chǎn)生
• 采用存儲程序原理皮服， 面向主存組織數(shù)據(jù)流
• 主存是按地址訪問、 線性編址的空間
• 指令由操作碼和地址碼組成
• 數(shù)據(jù)以二進制編碼

結構

image-20200429093531395

存儲器的組織層次

存儲器包括CPU中的高速緩存、主存儲器龄广、外圍設備中的硬盤和網(wǎng)絡中的遠程存儲器等

image-20200429093738493

計算機軟件系統(tǒng)

軟件開發(fā)的不同層次

• 計算機硬件系統(tǒng)： 機器語言
• 操作系統(tǒng)之資源管理： 機器語言+廣義指令（擴充了硬件資源管理）
• 操作系統(tǒng)之文件系統(tǒng)： 機器語言+系統(tǒng)調(diào)用（擴充了信息資源管理）
• 數(shù)據(jù)庫管理系統(tǒng)： +數(shù)據(jù)庫語言（擴充了功能更強的信息資源管理）
• 語言處理程序： 面向問題的語言

計算機程序的執(zhí)行過程

image-20200429094558283

操作系統(tǒng)

操作系統(tǒng)(Operating System)硫眯， 簡稱OS

OS是計算機系統(tǒng)最基礎的系統(tǒng)軟件， 管理軟硬件資源择同、 控制程序執(zhí)行两入， 改善人機界面， 合理組織計算機工作流程敲才， 為用戶使用計算機提供良好運行環(huán)境

簡而言之裹纳， 操作系統(tǒng)是方便用戶、 管理和控制計算機軟硬件資源的系統(tǒng)程序集合

• 從用戶角度看紧武， OS管理計算機系統(tǒng)的各種資源剃氧， 擴充硬件的功能， 控制程序的執(zhí)行
• 從人機交互看阻星， OS是用戶與機器的接口朋鞍，提供良好的人機界面， 方便用戶使用計算機迫横，在整個計算機系統(tǒng)中具有承上啟下的地位
• 從系統(tǒng)結構看番舆， OS是一個大型軟件系統(tǒng)酝碳，其功能復雜矾踱， 體系龐大， 采用層次式疏哗、 模塊化的程序結構

操作系統(tǒng)的組成

• 進程調(diào)度子系統(tǒng)
• 進程通信子系統(tǒng)
• 內(nèi)存管理子系統(tǒng)
• 設備管理子系統(tǒng)
• 文件管理子系統(tǒng)
• 網(wǎng)絡通信子系統(tǒng)
• 作業(yè)控制子系統(tǒng)

類型

操作控制方式

• 多道批處理操作系統(tǒng)呛讲， 脫機控制方式
• 分時操作系統(tǒng)， 交互式控制方式
• 實時操作系統(tǒng)

應用領域

• 服務器操作系統(tǒng)返奉、 并行操作系統(tǒng)
• 網(wǎng)絡操作系統(tǒng)贝搁、 分布式操作系統(tǒng)
• 個人機操作系統(tǒng)、 手機操作系統(tǒng)
• 嵌入式操作系統(tǒng)芽偏、 傳感器操作系統(tǒng)

資源管理

計算機資源包含

• 硬件資源
  處理器雷逆、 內(nèi)存、 外設
• 信息資源
  數(shù)據(jù)污尉、 程序

屏蔽資源使用的底層細節(jié)

驅動程序： 最底層的膀哲、 直接控制和監(jiān)視各類硬件(或文件)資源的部分

職責是隱藏底層硬件的具體細節(jié)， 并向其他部分提供一個抽象的被碗、 通用的接口
比如說： 打印一段文字或一個文件某宪， 既不需知道文件信息存儲在硬盤上的細節(jié)，也不必知道具體打印機類型和控制細節(jié)

資源共享方式

• 獨占使用方式
• 并發(fā)使用方式

資源分配策略

• 靜態(tài)分配方式
• 動態(tài)分配方式
• 資源搶占方式

系統(tǒng)控制

CPU速度與I/O速度不匹配的矛盾非常突出.只有讓多道程序同時進入內(nèi)存爭搶CPU運行锐朴， 才可以夠使得CPU和外圍設備充分并行兴喂， 從而提高計算機系統(tǒng)的使用效率

image-20200429110425511

image-20200429110444095

多道程序系統(tǒng)的實現(xiàn)

• 為進入內(nèi)存執(zhí)行的程序建立管理實體： 進程

• OS應能管理與控制進程程序的執(zhí)行

• OS協(xié)調(diào)管理各類資源在進程間的使用

  • 處理器的管理和調(diào)度
  • 主存儲器的管理和調(diào)度
  • 其他資源的管理和調(diào)度

• 如何使用資源： 調(diào)用操作系統(tǒng)提供的服務例程(如何陷入操作系統(tǒng))

• 如何復用CPU： 調(diào)度程序(在CPU空閑時讓其他程序運行)

• 如何使CPU與I/O設備充分并行： 設備控制器與通道(專用的I/O處理器)

• 如何讓正在運行的程序讓出CPU： 中斷(中斷正在執(zhí)行的程序， 引入OS處理)

控制方式

脫機作業(yè)控制方式

1. OS： 提供作業(yè)說明語言

2. 用戶： 編寫作業(yè)說明書， 確定作業(yè)加工控制步驟衣迷，并與程序數(shù)據(jù)一并提交

3. 操作員： 通過控制臺輸入作業(yè)

4. OS： 通過作業(yè)控制程序自動控制作業(yè)的執(zhí)行

例： 批處理OS的作業(yè)控制方式畏鼓， UNIX的shell程序，DOS的bat文件

聯(lián)機作業(yè)控制方式

1. 計算機： 提供終端（鍵盤/顯示器）

2. 用戶： 登錄系統(tǒng)

3. OS： 提供命令解釋程序

4. 用戶： 聯(lián)機輸入命令蘑险， 直接控制作業(yè)步的執(zhí)行

例： 分時OS的交互控制方式

命令解釋程序

不管是脫機控制方式還是聯(lián)機控制方式都需要命令解釋程序

命令解釋程序： 接受和執(zhí)行一條用戶提出的對作業(yè)的加工處理命令
當一個新的批作業(yè)被啟動滴肿， 或新的交互型用戶登錄進系統(tǒng)時， 系統(tǒng)就自動地執(zhí)行命令解釋程序佃迄， 負責讀入控制卡或命令行泼差， 作出相應解釋， 并予以執(zhí)行

會話語言： 可編程的命令解釋程序

處理過程

1. OS啟動命令解釋程序呵俏， 輸出命令提示符堆缘， 等待（鍵盤中斷/鼠標點擊/多通道識別）
2. 每當用戶輸入一條命令(暫存在命令緩沖區(qū))并按回車換行時胚膊， 申請中斷
3. CPU響應后漱凝， 將控制權交給命令解釋程序，接著讀入命令緩沖區(qū)內(nèi)容叠聋， 分析命令麻车、 接受參數(shù)缀皱， 執(zhí)行處理代碼
4. 前臺命令執(zhí)行結束后， 再次輸出命令提示符动猬，等待下一條命令
5. 后臺命令處理啟動后啤斗， 即可接收下條命令

前臺命令：必須執(zhí)行完畢后，才能繼續(xù)輸入命令

后臺命令：命令啟動后赁咙，可以繼續(xù)啟動下一個命令钮莲，而命令在后臺的執(zhí)行不影響

系統(tǒng)接口

操作系統(tǒng)的程序接口——系統(tǒng)調(diào)用

操作系統(tǒng)實現(xiàn)的完成某種特定功能的過程； 為所有運行程序提供訪問操作系統(tǒng)的接口

就是操作系統(tǒng)為一些操作提供了接口彼水，應用程序需要執(zhí)行這些操作的時候就會去調(diào)用這些接口

實現(xiàn)

• 編寫系統(tǒng)調(diào)用處理程序

  操作系統(tǒng)會提前提供這些系統(tǒng)調(diào)用處理程序

• 設計一張系統(tǒng)調(diào)用入口地址表崔拥， 每個入口地址指向一個系統(tǒng)調(diào)用的處理程序， 并包含系統(tǒng)調(diào)用自帶參數(shù)的個數(shù)

  通過軟件發(fā)起凤覆，系統(tǒng)查閱系統(tǒng)調(diào)用入口地址表链瓦，找到相應的系統(tǒng)調(diào)用處理程序

• 陷入處理機制需開辟現(xiàn)場保護區(qū)， 以保存發(fā)生系統(tǒng)調(diào)用時的處理器現(xiàn)場

  在調(diào)用系統(tǒng)調(diào)用之前盯桦，將當前的處理器狀況存儲慈俯，以便調(diào)用后恢復處理器現(xiàn)場

image-20200429114141408

系統(tǒng)結構

結構設計

OS構件
內(nèi)核、 進程俺附、 線程肥卡、 管程等

內(nèi)核設計是OS設計中最為復雜的部分

設計概念
模塊化、 層次式事镣、 虛擬化

內(nèi)核

單內(nèi)核：內(nèi)核中各部件雜然混居的形態(tài)步鉴， 始于1960年代揪胃， 廣泛使用； 如Unix/Linux氛琢， 及Windows(自稱采用混合內(nèi)核的CS結構)

微內(nèi)核：1980年代始喊递， 強調(diào)結構性部件與功能性部件的分離， 大部分OS研究都集中在此

混合內(nèi)核：微內(nèi)核和單內(nèi)核的折中阳似， 較多組件在核心態(tài)中運行骚勘， 以獲得更快的執(zhí)行速度

外內(nèi)核：盡可能減少內(nèi)核的軟件抽象化和傳統(tǒng)微內(nèi)核的消息傳遞機制，使得開發(fā)者專注于硬件的抽象化撮奏，部分嵌入式系統(tǒng)使用

層次結構

處理器管理

處理器與寄存器

處理器部件

image-20200429115552592

指令譯碼器ID：負責具體的解釋指令的執(zhí)行

指令暫存器IR：負責對指令的存儲

程序計數(shù)器PC：指向下一跳要執(zhí)行指令的地址

算術邏輯單元在完成計算之后會將內(nèi)容匯總到標志寄存器Flag中

內(nèi)存地址寄存器MAR俏讹、內(nèi)存數(shù)據(jù)寄存器MDR：用于訪問內(nèi)存數(shù)據(jù)

用戶程序可見寄存器

可以使程序員減少訪問主存儲器的次數(shù)， 提高指令執(zhí)行的效率

所有程序可使用畜吊， 包括應用程序和系統(tǒng)程序

• 數(shù)據(jù)寄存器： 又稱通用寄存器
• 地址寄存器： 索引泽疆、 棧指針、 段地址等寄存器

控制與狀態(tài)寄存器

用于控制處理器的操作玲献； 主要被具有特權的操作系統(tǒng)程序使用殉疼， 以控制程序的執(zhí)行

• 程序計數(shù)器PC： 存儲將取指令的地址
• 指令寄存器IR： 存儲最近使用的指令
• 條件碼CC： CPU為指令操作結果設置的位， 標志正/負/零/溢出等結果
• 標志位： 中斷位捌年、 中斷允許位瓢娜、 中斷屏蔽位、 處理器模式位礼预、 內(nèi)存保護位眠砾、 …， 等

程序狀態(tài)字PSW

PSW既是操作系統(tǒng)的概念逆瑞， 指記錄當前程序運行的動態(tài)信息荠藤， 通常包含：

• 程序計數(shù)器伙单， 指令寄存器获高， 條件碼
• 中斷字， 中斷允許/禁止吻育， 中斷屏蔽念秧， 處理器模式， 內(nèi)存保護布疼、 調(diào)試控制

PSW也是計算機系統(tǒng)的寄存器

• 通常設置一組控制與狀態(tài)寄存器

• 也可以專設一個PSW寄存器

指令與處理機

機器指令

機器指令是計算機系統(tǒng)執(zhí)行的基本命令摊趾， 是中央處理器執(zhí)行的基本單位

指令由一個或多個字節(jié)組成， 包括操作碼字段游两、 一個或多個操作數(shù)地址字段砾层、 以及一些表征機器狀態(tài)的狀態(tài)字以及特征碼

指令完成各種算術邏輯運算、 數(shù)據(jù)傳輸贱案、 控制流跳轉

指令執(zhí)行過程

CPU根據(jù)PC（程序計數(shù)器）取出指令肛炮， 放入IR， 并對指令譯碼，然后發(fā)出各種控制命令侨糟， 執(zhí)行微操作系列碍扔，從而完成一條指令的執(zhí)行

一種指令執(zhí)行步驟如下

1. 取指： 根據(jù)PC從存儲器或高速緩沖存儲器中取指令到IR
2. 解碼： 解譯IR中的指令來決定其執(zhí)行行為
3. 執(zhí)行： 連接到CPU部件， 執(zhí)行運算秕重， 產(chǎn)生結果并寫回不同， 同時在CC里設置運算結論標志； 跳轉指令操作PC溶耘， 其他指令遞增PC值

指令執(zhí)行周期與指令流水線

image-20200429122203865

特權指令與非特權指令

用戶程序并非能夠使用全部機器指令二拐， 那些與計算機核心資源相關的特殊指令會被保護，核心資源相關的指令只能被操作系統(tǒng)程序使用

如： 啟動I/O指令凳兵、 置PC指令卓鹿、 等等

假設A程序要輸出123，同時B程序要輸出456留荔，如果將I/O控制交給計算機很有可能輸出成142536吟孙，不符合要求

所以指令被分為特權指令和非特權指令

• 特權指令： 只能被操作系統(tǒng)內(nèi)核使用的指令
• 非特權指令： 能夠被所有程序使用的指令

處理器模式

計算機通過設置處理器模式實現(xiàn)特權指令管理

計算機一般設置0、 1聚蝶、 2杰妓、 3等四種運行模式，建議分別對應： 0操作系統(tǒng)內(nèi)核碘勉、 1系統(tǒng)調(diào)用巷挥、2共享庫程序、 3用戶程序等保護級別

一般來說验靡， 現(xiàn)代操作系統(tǒng)只使用0和3兩種模式倍宾，對應于內(nèi)核模式和用戶模式

處理器模式的切換

包括“用戶模式→內(nèi)核模式”和“內(nèi)核模式→用戶模式” 的轉換

中斷、 異呈どぃ或系統(tǒng)異常等事件導致用戶程序向OS內(nèi)核切換高职， 觸發(fā)： 用戶模式→內(nèi)核模式

• 程序請求操作系統(tǒng)服務
• 程序運行時發(fā)生異常
• 程序運行時發(fā)生并響應中斷

OS內(nèi)核處理完成后， 調(diào)用中斷返回指令（如Intel的iret） 觸發(fā)： 內(nèi)核模式→用戶模式

中斷

概念

中斷是指程序執(zhí)行過程中辞州， 遇到急需處理的事件時怔锌， 暫時中止CPU上現(xiàn)行程序的運行，轉去執(zhí)行相應的事件處理程序变过， 待處理完成后再返回原程序被中斷處或調(diào)度其他程序執(zhí)行的過程

操作系統(tǒng)是“中斷驅動” 的埃元； 換言之， 中斷是激活操作系統(tǒng)的唯一方式

比如用戶程序在運行的時候只有通過中斷才能夠切換

中斷有廣義和狹義之分媚狰， 上述中斷是指廣義的中斷

中斷岛杀、 異常與系統(tǒng)異常

• 狹義的中斷指來源于處理器之外的中斷事件，即與當前運行指令無關的中斷事件崭孤， 如I/O中
  斷类嗤、 時鐘中斷衫生、 外部信號中斷等

• 異常指當前運行指令引起的中斷事件， 如地址異常土浸、 算術異常罪针、 處理器硬件故障等

• 系統(tǒng)異常指執(zhí)行陷入指令而觸發(fā)系統(tǒng)調(diào)用引起的中斷事件， 如請求設備黄伊、 請求I/O泪酱、 創(chuàng)建進程等

  系統(tǒng)異常與硬件無關

中斷源

處理器硬件故障中斷事件

由處理器、 內(nèi)存儲器还最、 總線等硬件故障引起

處理原則為： 保護現(xiàn)場墓阀， 停止設備， 停止CPU拓轻， 向操作員報告斯撮， 等待人工干預

程序性中斷事件

處理器執(zhí)行機器指令引起

• 除數(shù)為零、 操作數(shù)溢出等算術異常： 簡單處理扶叉， 報告用戶勿锅； 也可以由用戶編寫中斷續(xù)元程序處理
• 非法指令、 用戶態(tài)使用特權指令枣氧、 地址越界溢十、 非法存取等指令異常： 終止進程
• 終止進程指令： 終止進程
• 虛擬地址異常： 調(diào)整內(nèi)存后重新執(zhí)行指令

自愿性中斷事件

處理器執(zhí)行陷入指令請求OS服務引起； 在操作系統(tǒng)中达吞， 它一般又被稱作系統(tǒng)調(diào)用

• 請求分配外設张弛、 請求I/O、 等等
• 處理流程是： 陷入OS酪劫， 保護現(xiàn)場吞鸭， 根據(jù)功能號查入口地址， 跳轉具體處理程序

I/O中斷事件

來源于外圍設備報告I/O狀態(tài)的中斷事件

• I/O完成： 調(diào)整進程狀態(tài)覆糟， 釋放等待進程
• I/O出錯： 等待人工干預
• I/O異常： 等待人工干預

外部中斷事件

由外圍設備發(fā)出的信號引起的中斷事件

• 時鐘中斷刻剥、 間隔時鐘中斷： 記時與時間片處理
• 設備報到與結束中斷： 調(diào)整設備表
• 鍵盤/鼠標信號中斷： 根據(jù)信號作出相應反應
• 關機/重啟動中斷： 寫回文件， 停止設備與CPU

中斷系統(tǒng)

中斷系統(tǒng)是計算機系統(tǒng)中響應和處理中斷的系統(tǒng)搪桂， 包括硬件子系統(tǒng)和軟件子系統(tǒng)兩部分

中斷響應由硬件子系統(tǒng)完成

中斷處理由軟件子系統(tǒng)完成

中斷響應處理與指令執(zhí)行周期

在指令執(zhí)行周期最后增加一個微操作透敌， 以響應中斷

image-20200429142728623

中斷裝置

計算機系統(tǒng)中發(fā)現(xiàn)并響應中斷/異常的硬件裝置稱為中斷裝置盯滚。由于中斷源的多樣性踢械， 硬件實現(xiàn)的中斷裝置有多種， 分別處理不同類型的中斷這些中斷裝置因計算機而異魄藕， 通常有：

• 處理器外的中斷： 由中斷控制器發(fā)現(xiàn)和響應
• 處理器內(nèi)的異常： 由指令的控制邏輯和實現(xiàn)線路發(fā)現(xiàn)和響應内列， 相應機制稱為陷阱
• 請求OS服務的系統(tǒng)異常： 處理器執(zhí)行陷入指令時直接觸發(fā)， 相應機制稱為系統(tǒng)陷阱

中斷控制器

CPU中的一個控制部件背率， 包括中斷控制邏輯線路和中斷寄存器

1. 外部設備向其發(fā)出中斷請求IRQ话瞧， 在中斷寄存器中設置已發(fā)生的中斷
2. 指令處理結束前嫩与， 會檢查中斷寄存器， 若有不被屏蔽的中斷產(chǎn)生交排， 則改變處理器內(nèi)操作的順序划滋， 引出操作系統(tǒng)中的中斷處理程序

這個過程是異步的，先設置寄存器埃篓，在這條指令結束之后查看寄存器处坪，才能進行中斷

陷阱與系統(tǒng)陷阱

陷阱與系統(tǒng)陷阱： 指令的邏輯和實現(xiàn)線路的一部分

• 執(zhí)行指令出現(xiàn)異常后， 會根據(jù)異常情況轉向操作系統(tǒng)的異常處理程序
• 出現(xiàn)虛擬地址異常后架专， 需要重新執(zhí)行指令同窘，往往越過陷阱獨立設置頁面異常處理程序
• 執(zhí)行陷入指令后， 越過陷阱處理部脚， 觸發(fā)系統(tǒng)陷阱想邦， 激活系統(tǒng)調(diào)用處理程序

這個過程是同步的，是在執(zhí)行指令的過程中發(fā)生的中斷

中斷響應過程

1. 發(fā)現(xiàn)中斷源委刘， 提出中斷請求

   1. 發(fā)現(xiàn)中斷寄存器中記錄的中斷

   2. 決定這些中斷是否應該屏蔽

   3. 當有多個要響應的中斷源時丧没， 根據(jù)規(guī)定的優(yōu)先級選擇一個

2. 中斷當前程序的執(zhí)行

   保存當前程序的PSW/PC到核心棧

3. 轉向操作系統(tǒng)的中斷處理程序

中斷處理程序

操作系統(tǒng)處理中斷事件的控制程序, 主要任務是處理中斷事 件和恢復正常操作

中斷處理過程

• 保護未被硬件保護的處理器狀態(tài)

• 通過分析被中斷進程的PSW中斷碼字段，識別中斷源

• 分別處理發(fā)生的中斷事件

• 恢復正常操作

  情況一： 對于某些中斷锡移， 在處理完畢后骂铁， 直接返回剛剛被中斷的進程
  情況二： 對于其他一些中斷， 需要中斷當前進程的運行罩抗， 調(diào)整進程隊列拉庵， 啟動進程調(diào)度， 選擇下一個執(zhí)行的進程并恢復其執(zhí)行

中斷系統(tǒng)處理流程

多中斷的響應與處理

中斷屏蔽

當計算機檢測到中斷時, 中斷裝置通過中斷屏蔽位決定是否響應已發(fā)生的中斷套蒂，有選擇的響應中斷

中斷優(yōu)先級

當計算機同時檢測到多個中斷時, 中斷裝置響應中斷的順序钞支，有優(yōu)先度的響應中斷

一種可能的處理次序：

1. 處理機硬件故障中斷事件
2. 自愿性中斷事件
3. 程序性中斷事件
4. 時鐘中斷等外部中斷事件
5. 輸入輸出中斷事件
6. 重啟動和關機中斷事件

不同類型的操作系統(tǒng)有不同的中斷優(yōu)先級

中斷的嵌套處理

當計算機響應中斷后， 在中斷處理過程中操刀，可以再響應其他中斷

操作系統(tǒng)是性能攸關程序系統(tǒng)烁挟， 且中斷響應處理有硬件要求， 考慮系統(tǒng)效率和實現(xiàn)代價問題骨坑， 中斷的嵌套處理應限制在一定層數(shù)內(nèi)撼嗓，如3層

中斷的嵌套處理了改變中斷處理次序， 導致先響應的有可能后處理

image-20200429150256898

image-20200429150317597

進程

進程是一個具有一定獨立功能的程序關于某個數(shù)據(jù)集合的一次運行活動欢唾，也是操作系統(tǒng)進行資源分配和調(diào)度的一個獨立單位

一個進程包括五個實體部分

1. (OS管理運行程序的)數(shù)據(jù)結構P
2. (運行程序的)內(nèi)存代碼C
3. (運行程序的)內(nèi)存數(shù)據(jù)D
4. (運行程序的)通用寄存器信息R
5. (OS控制程序執(zhí)行的)程序狀態(tài)字信息PSW

不同程序

• 在不同數(shù)據(jù)集上運行： 構成兩個無關進程

• 在相同數(shù)據(jù)集上運行： 構成兩個共享數(shù)據(jù)的交往進程

相同程序

• 在不同數(shù)據(jù)集上運行： 構成兩個共享代碼的無關進程

進程狀態(tài)

• 運行態(tài)：進程占有處理器運行

• 就緒態(tài)：進程具備運行條件等待處理器運行

• 等待態(tài)：進程由于等待資源且警、 輸入輸出、 信號等而不具備運行條件

image-20200429152605988

1. 運行態(tài)→ 等待態(tài)：等待資源礁遣、 I/O斑芜、 信號

2. 等待態(tài)→ 就緒態(tài)：資源滿足、 I/O結束祟霍、信號完成

3. 運行態(tài)→ 就緒態(tài)：運行時間片到杏头、有更高優(yōu)先權進程

4. 就緒態(tài)→ 運行態(tài)：處理器空閑時選擇更高優(yōu)先權進程搶占

進程掛起

OS無法預期進程的數(shù)目與資源需求盈包， 計算機系統(tǒng)在運行過程中可能出現(xiàn)資源不足的情況

運行資源不足表現(xiàn)為性能低和死鎖兩種情況

解決辦法： 剝奪某些進程的內(nèi)存及其他資源，調(diào)入OS管理的對換區(qū)醇王， 不參加進程調(diào)度呢燥， 待適當時候再調(diào)入內(nèi)存、恢復資源寓娩、參與運行疮茄，這就是進程掛起

掛起態(tài)與等待態(tài)有著本質區(qū)別， 后者占有已申請到的資源處于等待根暑， 前者沒有任何資源

進程掛起的選擇與恢復

image-20200429153137896

• 一般選擇等待態(tài)進程進入掛起等待態(tài)
• 也可選擇就緒態(tài)進程進入掛起就緒態(tài)
• 運行態(tài)進程還可以掛起自己
• 等待事件結束后力试，掛起等待態(tài)進入掛起就緒態(tài)
• 一般選擇掛起就緒態(tài)進程予以恢復

數(shù)據(jù)描述

進程控制塊

進程控制塊PCB是OS用于記錄和刻畫進程狀態(tài)及環(huán)境信息的數(shù)據(jù)結構

分為標識信息、現(xiàn)場信息排嫌、控制信息

image-20200429153548426

標識信息

用于存放唯一標識該進程的信息

• 系統(tǒng)分配的標識號
• 系統(tǒng)分配的進程組標識號
• 用戶定義的進程名
• 用戶定義的進程組名

現(xiàn)場信息

用于存放該進程運行時的處理器現(xiàn)場信息

• 用戶可見寄存器內(nèi)容： 數(shù)據(jù)寄存器畸裳、 地址寄存器
• 控制與狀態(tài)寄存器內(nèi)容： PC、 IR淳地、 PSW
• 棧指針內(nèi)容： 核心棧與用戶棧指針

控制信息

用于存放與管理怖糊、 調(diào)度進程相關的信息

1. 調(diào)度相關信息： 狀態(tài)、 等待事件/原因颇象、 優(yōu)先級
2. 進程組成信息： 代碼/數(shù)據(jù)地址伍伤、 外存映像地址
3. 隊列指引元： 進程隊列指針、 父子兄弟進程指針
4. 通信相關信息： 消息隊列遣钳、 信號量扰魂、 鎖
5. 進程特權信息： 如內(nèi)存訪問權限、 處理器特權
6. 處理器使用信息： 占用的處理器蕴茴、 時間片劝评、 處理器使用時間/已執(zhí)行總時間、 記賬信息
7. 資源清單信息： 如正占有的資源倦淀、 已使用的資源

進程映像

某一時刻進程的內(nèi)容及其執(zhí)行狀態(tài)集合蒋畜，是內(nèi)存級的物理實體， 又稱為進程的內(nèi)存映像撞叽，包含：

• 進程控制塊: 保存進程的標識信息姻成、 狀態(tài)信息和控制信息
• 進程程序塊: 進程執(zhí)行的程序空間
• 進程數(shù)據(jù)塊: 進程處理的數(shù)據(jù)空間， 包括數(shù)據(jù)愿棋、 處理函數(shù)的用戶棧和可修改的程序
• 核心棧: 進程在內(nèi)核模式下運行時使用的堆棧科展， 中斷或系統(tǒng)過程使用

image-20200429154610977

進程上下文

進程的執(zhí)行需要環(huán)境支持， 包括CPU現(xiàn)場和Cache中的執(zhí)行信息初斑，OS中的進程物理實體和支持進程運行的環(huán)境合成進程上下文辛润， 包括以下：

• 用戶級上下文： 用戶程序塊/用戶數(shù)據(jù)區(qū)/用戶棧/用戶共享內(nèi)存
• 寄存器上下文： PSW/棧指針/通用寄存器
• 系統(tǒng)級上下文： PCB/內(nèi)存區(qū)表/核心棧

進程上下文刻畫了進程的執(zhí)行情況

進程的管理

關鍵的進程管理軟件包括：

• 系統(tǒng)調(diào)用/中斷/異常處理程序
• 隊列管理模塊
• 進程控制程序
• 進程調(diào)度程序（獨立進程居多）
• 進程通信程序（多個程序包）
• 終端登錄與作業(yè)控制程序、 性能監(jiān)控程序见秤、 審計程序等外圍程序

隊列管理模塊

進程實現(xiàn)的隊列模型

操作系統(tǒng)建立多個進程隊列砂竖， 包括就緒隊列和等待隊列，按需組織為先進先出隊列與優(yōu)先隊列鹃答。隊列中的進程可以通過PCB中的隊列指引元采用單/雙指引元或索引連接乎澄。進程與資源調(diào)度圍繞進程隊列展開。

控制與管理

• 進程創(chuàng)建： 進程表加一項测摔， 申請PCB并初始化置济，生成標識， 建立映像锋八， 分配資源浙于， 移入就緒隊列
• 進程撤銷： 從隊列中移除， 歸還資源挟纱， 撤銷標識羞酗，回收PCB， 移除進程表項
• 進程阻塞： 保存現(xiàn)場信息紊服， 修改PCB檀轨， 移入等待隊列财边， 調(diào)度其他進程執(zhí)行
• 進程喚醒： 等待隊列中移出搞动， 修改PCB， 移入就緒隊列（該進程優(yōu)先級高于運行進程觸發(fā)搶占）
• 進程掛起： 修改狀態(tài)并出入相關隊列酣倾， 收回內(nèi)存等資源送至對換區(qū)
• 進程激活： 分配內(nèi)存煎饼， 修改狀態(tài)并出入相關隊列
• 其他： 如修改進程特權

原語與進程控制原語

進程控制過程中涉及對OS核心數(shù)據(jù)結構(進程表/PCB池/隊列/資源表)的修改讹挎，為防止與時間有關的錯誤， 應使用原語

原語是由若干條指令構成的完成某種特定功能的程序吆玖，執(zhí)行上具有不可分割性淤袜。原語的執(zhí)行可以通過關中斷實現(xiàn)

進程控制使用的原語稱為進程控制原語，另一類常用原語是進程通信原語

進程切換

進程切換指從正在運行的進程中收回處理器衰伯，讓待運行進程來占有處理器運行 铡羡，進程切換實質上就是被中斷運行進程與待運行進程的上下文切換， 處理過程是：

1. 保存被中斷進程的上下文
2. 轉向進程調(diào)度
3. 恢復待運行進程的上下文

進程的切換必須在操作系統(tǒng)內(nèi)核模式下完成意鲸，也就必須需要模式切換

模式切換

模式切換又稱處理器狀態(tài)切換烦周， 包括：

1. 用戶模式到內(nèi)核模式
   由中斷/異常/系統(tǒng)調(diào)用中斷用戶進程執(zhí)行而觸發(fā)

   1. 處理器模式轉為內(nèi)核模式
   2. 保存當前進程的PC/PSW值到核心棧
   3. 轉向中斷/異常/系統(tǒng)調(diào)用處理程序

2. 內(nèi)核模式到用戶模式
   OS執(zhí)行中斷返回指令將控制權交還用戶進程而觸發(fā)

   1. 從待運行進程核心棧中彈出PSW/PC值
   2. 處理器模式轉為用戶模式

進程切換工作過程

1. (中斷/異常等觸發(fā))正向模式切換并壓入PSW/PC
2. 保存被中斷進程的現(xiàn)場信息
3. 處理具體中斷/異常
4. 把被中斷進程的系統(tǒng)堆棧指針SP值保存到PCB
5. 調(diào)整被中斷進程的PCB信息， 如進程狀態(tài)
6. 把被中斷進程的PCB加入相關隊列
7. 選擇下一個占用CPU運行的進程
8. 修改被選中進程的PCB信息怎顾， 如進程狀態(tài)
9. 設置被選中進程的地址空間读慎， 恢復存儲管理信息
10. 恢復被選中進程的SP值到處理器寄存器SP
11. 恢復被選中進程的現(xiàn)場信息進入處理器
12. (中斷返回指令觸發(fā))逆向模式轉換并彈出PSW/PC

進程切換的發(fā)生時機

進程切換一定發(fā)生在中斷/異常/系統(tǒng)調(diào)用，處理過程中槐雾， 常見的情況是：

• 阻塞式系統(tǒng)調(diào)用夭委、 虛擬地址異常導致被中斷進程進入等待態(tài)
• 時間片中斷、 I/O中斷后發(fā)現(xiàn)更高優(yōu)先級進程募强，導致被中斷進程轉入就緒態(tài)
• 終止用系統(tǒng)調(diào)用株灸、 不能繼續(xù)執(zhí)行的異常崇摄，導致被中斷進程進入終止態(tài)

一些中斷/異常不會引起進程狀態(tài)轉換， 不會引起進程切換慌烧， 只是在處理完成后把控制權交回給被中斷進程逐抑， 處理流程是：

1. (中斷/異常觸發(fā))正向模式切換壓入PSW/PC
2. 保存被中斷進程的現(xiàn)場信息
3. 處理中斷/異常
4. 恢復被中斷進程的現(xiàn)場信息
5. (中斷返回指令觸發(fā))逆向模式轉換彈出PSW/PC

多線程技術

傳統(tǒng)進程是單線程結構進程

image-20200429163314902

單線程結構進程在并發(fā)程序設計上存在的問題 ：

• 進程切換開銷大
• 進程通信開銷大
• 限制了進程并發(fā)的粒度
• 降低了并行計算的效率

操作系統(tǒng)會根據(jù)安全角度對進程之間的通信做一些限制，且進程之間的調(diào)度需要耗費的成本更高

多線程結構進程

image-20200429163707535

線程是進程的一條執(zhí)行路徑屹蚊， 是調(diào)度的基本單位厕氨， 同一個進程中的所有線程共享進程獲得的主存空間和資源

線程狀態(tài)有運行、 就緒和睡眠汹粤， 無掛起

掛起與是否占有資源有關命斧，而線程使用的是進程的資源

OS感知線程環(huán)境下：

• 處理器調(diào)度對象是線程
• 進程沒有三狀態(tài)（或者說只有掛起狀態(tài)）

OS不感知線程環(huán)境：

• 處理器調(diào)度對象仍是進程

• 用戶空間中的用戶調(diào)度程序調(diào)度線程

優(yōu)點

• 快速線程切換
• 減少（系統(tǒng)） 管理開銷
• （線程） 通信易于實現(xiàn)
• 并行程度提高
• 節(jié)省內(nèi)存空間

多線程的實現(xiàn)

內(nèi)核級線程KLT, Kernel-Level Threads

線程管理的所有工作由OS內(nèi)核來做

image-20200429165321052

特點

• 進程中的一個線程被阻塞了， 內(nèi)核能調(diào)度同一進程的其它線程占有處理器運行
• 多處理器環(huán)境中嘱兼， 內(nèi)核能同時調(diào)度同一進程中多個線程并行執(zhí)行
• 內(nèi)核自身也可用多線程技術實現(xiàn)国葬， 能提高操作系統(tǒng)的執(zhí)行速度和效率
• 應用程序線程在用戶態(tài)運行， 線程調(diào)度和管理在內(nèi)核實現(xiàn)遭京， 在同一進程中胃惜， 控制權從一個線程傳送到另一個線程時需要模式切換，系統(tǒng)開銷較大

用戶級線程ULT, User-Level Threads

用戶空間運行的線程庫哪雕，提供多線程應用程序的開發(fā)和運行支撐環(huán)境船殉。

線程管理的所有工作都由應用程序完成，內(nèi)核沒有意識到線程的存在斯嚎。

image-20200429165534020

特點

1. 所有線程管理數(shù)據(jù)結構均在進程的用戶空間中利虫， 線程切換不需要內(nèi)核模式， 能節(jié)省模式切換開銷和內(nèi)核的寶貴資源
2. 允許進程按應用特定需要選擇調(diào)度算法堡僻， 甚至根據(jù)應用需求裁剪調(diào)度算法
3. 能運行在任何OS上糠惫， 內(nèi)核在支持ULT方面不需要做任何工作
4. 不能利用多處理器的優(yōu)點， OS調(diào)度進程钉疫，僅有一個ULT能執(zhí)行
5. 一個ULT的阻塞硼讽， 將引起整個進程的阻塞

Jacketing技術

把阻塞式系統(tǒng)調(diào)用改造成非阻塞式的,當線程陷入系統(tǒng)調(diào)用時，執(zhí)行jacketing程序牲阁。由jacketing 程序來檢查資源使用情況固阁，以決定是否執(zhí)行進程切換或傳遞控制權給另一個線程。

image-20200429165819309

混合式多線程

單應用的多個ULT可以映射成一些KLT城菊， 通過調(diào)整KLT數(shù)目备燃，可以達到較好的并行效果

image-20200429170733555

線程混合式策略下的線程狀態(tài)

• 活躍態(tài)ULT代表綁定KLT的三態(tài)
• 活躍態(tài)ULT運行時可激活用戶調(diào)度
• 非阻塞系統(tǒng)調(diào)用可使用Jacketing啟動用戶調(diào)度， 調(diào)整活躍態(tài)ULT

image-20200429170933586

image-20200429171000147

處理器調(diào)度

調(diào)度的層次

高級調(diào)度

又稱長程調(diào)度凌唬， 作業(yè)調(diào)度決定能否加入到執(zhí)行的進程池中

分時OS中并齐， 高級調(diào)度決定：

• 是否接受一個終端用戶的連接
• 命令能否被系統(tǒng)接納并構成進程
• 新建態(tài)進程是否加入就緒進程隊列

中級調(diào)度

又稱平衡負載調(diào)度，決定主存中的可用進程集合

• 引進中級調(diào)度是為了提高內(nèi)存利用率和作業(yè)吞吐量
• 中級調(diào)度決定那些進程被允許駐留在主存中參與競爭處理器及其他資源， 起到短期調(diào)整系統(tǒng)負荷的作用
• 中級調(diào)度把一些進程換出主存况褪， 從而使之進入“掛起” 狀態(tài)撕贞， 不參與進程調(diào)度，以平順系統(tǒng)的負載

低級調(diào)度

又稱短程調(diào)度窝剖， 進程調(diào)度決定哪個可用進程占用處理器執(zhí)行

• 進程調(diào)度程序： 又稱分派程序麻掸， 操作系統(tǒng)中實現(xiàn)處理器調(diào)度的程序酥夭， 是操作系統(tǒng)的最核心部分
• 處理器調(diào)度策略的優(yōu)劣直接影響到整個系統(tǒng)的性能

主要功能

• 記住進程或內(nèi)核級線程的狀態(tài)
• 決定某個進程或內(nèi)核級線程什么時候獲得處理器赐纱， 以及占用多長時間
• 把處理器分配給進程或內(nèi)核級線程
• 收回處理器

image-20200429171403339

image-20200429171456555

調(diào)度算法

選擇處理器調(diào)度算法的原則

• 資源利用率： 使得CPU或其他資源的使用率盡可能高且能夠并行工作
• 響應時間： 使交互式用戶的響應時間盡可能小， 或盡快處理實時任務
• 周轉時間： 提交給系統(tǒng)開始到執(zhí)行完成獲得結果為止的這段時間間隔稱周轉時間熬北， 應該使周轉時間或平均周轉時間盡可能短
• 吞吐量： 單位時間處理的進程數(shù)盡可能多
• 公平性： 確保每個用戶每個進程獲得合理的CPU份額或其他資源份額

優(yōu)先數(shù)調(diào)度算法

根據(jù)分配給進程的優(yōu)先數(shù)決定運行進程

分類

• 搶占式優(yōu)先數(shù)調(diào)度算法
• 非搶占式優(yōu)先數(shù)調(diào)度算法

與進入系統(tǒng)時間相關的優(yōu)先數(shù)

• 計算時間短(作業(yè)/進程)優(yōu)先

• 剩余計算時間短進程優(yōu)先

• 響應比高者(作業(yè)/進程)優(yōu)先
  

• 先來先服務： 先進隊先被選擇

• 多用于高級調(diào)度疙描； 低級調(diào)度中， 以計算為主的進程過于優(yōu)越

時間片輪轉調(diào)度算法

• 根據(jù)各個進程進入就緒隊列的時間先后輪流占有CPU一個時間片
• 時間片中斷
• 時間片的確定： 選擇長短合適的時間片, 過長則退化為先來先服務算法, 過短則調(diào)度開銷大
• 不同進程時間片長度可調(diào)

分級調(diào)度算法

又稱多隊列策略讶隐， 反饋循環(huán)隊列

基本思想

• 建立多個不同優(yōu)先級的就緒進程隊列
• 多個就緒進程隊列間按照優(yōu)先數(shù)調(diào)度
• 高優(yōu)先級就緒進程起胰， 分配的時間片短
• 單個就緒進程隊列中進程的優(yōu)先數(shù)和時間片相同

例子：

image-20200429174252057

彩票調(diào)度算法

基本思想

為進程發(fā)放針對系統(tǒng)各種資源（如CPU時間） 的彩票； 當調(diào)度程序需要做出決策時巫延， 隨機選擇一張彩票效五，持有該彩票的進程將獲得系統(tǒng)資源

合作進程之間可以進行彩票交換

存儲管理

主要模式

邏輯地址

又稱相對地址， 即用戶編程所使用的地址空間

邏輯地址從0開始編號炉峰， 有兩種形式：

• 一維邏輯地址（地址）
• 二維邏輯地址（段號:段內(nèi)地址）

段式程序設計

• 把一個程序設計成多個段（代碼段畏妖、數(shù)據(jù)段、堆棧段疼阔、等等）
• 用戶可以自己應用段覆蓋技術擴充內(nèi)存空間使用量

物理地址

又稱絕對地址戒劫， 即程序執(zhí)行所使用的地址空間，處理器執(zhí)行指令時按照物理地址進行

主存儲器的復用

按照分區(qū)復用

• 主存劃分為多個固定/可變尺寸的分區(qū)
• 一個程序/程序段占用一個分區(qū)

按照頁架復用

• 主存劃分成多個固定大小的頁架

• 一個程序/程序段占用多個頁架

存儲管理的基本模式

將邏輯地址和物理地址相對于婆廊，就會有2*2=4個存儲管理的基本模式

• 單連續(xù)存儲管理： 一維邏輯地址空間的程序占用一個主存固定分區(qū)或可變分區(qū)
• 段式存儲管理： 段式二維邏輯地址空間的程序占用多個主存可變分區(qū)
• 頁式存儲管理： 一維邏輯地址空間的程序占用多個主存頁架區(qū)
• 段頁式存儲管理： 段式二維邏輯地址空間的程序占用多個主存頁架區(qū)

image-20200429180525340

功能

地址轉換

又稱重定位迅细， 即把邏輯地址轉換成絕對地址

靜態(tài)重定位

在程序裝入內(nèi)存時進行地址轉換

由裝入程序執(zhí)行， 早期小型OS使用

動態(tài)重地位

在CPU執(zhí)行程序時進行地址轉換

從效率出發(fā)淘邻， 依賴硬件地址轉換機構

分配與去配

分配

進程裝入主存時茵典， 存儲管理軟件進行具體的主存分配操作， 并設置一個表格記錄主存空間的分配情況

去配

當某個進程撤離或主動歸還主存資源時宾舅， 存儲管理軟件要收回它所占用的全部或者部分存儲空間统阿， 調(diào)整主存分配表信息

空間共享

多個進程共享主存儲器資源： 多道程序設計技術使若干個程序同時進入主存儲器， 各自占用一定數(shù)量的存儲空間贴浙， 共同使用一個主存儲器

多個進程共享主存儲器的某些區(qū)域： 若干個協(xié)作進程有共同的主存程序塊或者主存數(shù)據(jù)塊

存儲保護

為避免主存中的多個進程相互干擾砂吞， 必須對主存中的程序和數(shù)據(jù)進行保護

• 私有主存區(qū)中的信息： 可讀可寫
• 公共區(qū)中的共享信息： 根據(jù)授權
• 非本進程信息： 不可讀寫

這一功能需要軟硬件協(xié)同完成，CPU檢查是否允許訪問崎溃， 不允許則產(chǎn)生地址保護異常蜻直， 由OS進行相應處理。

空間的擴充

存儲擴充： 把磁盤作為主存擴充， 只把部分進程或進程的部分內(nèi)容裝入內(nèi)存

1. 對換技術： 把部分不運行的進程調(diào)出
2. 虛擬技術： 只調(diào)入進程的部分內(nèi)容

這一工作需要軟硬件協(xié)作完成

1. 對換進程決定對換概而， 硬件機構調(diào)入

2. CPU處理到不在主存的地址呼巷， 發(fā)出虛擬地址異常， OS將其調(diào)入赎瑰， 重執(zhí)指令

虛擬存儲器

提出

• 主存容量限制帶來諸多不便
  • 用戶編寫程序必須考慮主存容量限制
  • 多道程序設計的道數(shù)受到限制
• 用戶編程行為分析
  • 全面考慮各種情況王悍， 執(zhí)行時有互斥性
  • 順序性和循環(huán)性等空間局部性行為
  • 某一階段執(zhí)行的時間局部性行為

因此可以考慮部分調(diào)入進程內(nèi)容

基本思想

• 存儲管理把進程全部信息放在輔存中， 執(zhí)行時先將其中一部分裝入主存餐曼， 以后根據(jù)執(zhí)行行為隨用隨調(diào)入
• 如主存中沒有足夠的空閑空間压储， 存儲管理需要根據(jù)執(zhí)行行為把主存中暫時不用的信息調(diào)出到輔存上去

實現(xiàn)思路

需要建立與自動管理兩個地址空間

• (輔存)虛擬地址空間： 容納進程裝入
• (主存)實際地址空間： 承載進程執(zhí)行

對于用戶， 計算機系統(tǒng)具有一個容量大得多的主存空間源譬， 即虛擬存儲器集惋。虛擬存儲器是一種地址空間擴展技術，通常意義上對用戶編程是透明的

虛擬存儲器示意

存儲管理的硬件支撐

存儲管理涉及的存儲對象

• 為獲得更好的處理性能踩娘， 部分主存程序與數(shù)據(jù)（特別是關鍵性能數(shù)據(jù)） 被調(diào)入Cache刮刑， 存儲管理需要對其進行管理， 甚至包括對聯(lián)想存儲器的管理
• 為獲得更大的虛擬地址空間养渴， 存儲管理需要對存放在硬盤雷绢、 固態(tài)硬盤、 甚至網(wǎng)絡硬盤上的虛擬存儲器文件進行管理

高速緩存存儲器（Cache）

• Cache是介于CPU和主存儲器間的高速小容量存儲器理卑， 由靜態(tài)存儲芯片SRAM組成翘紊， 容量較小但比主存DRAM技術更加昂貴而快速， 接近于CPU的速度
• CPU往往需要重復讀取同樣的數(shù)據(jù)塊傻工，Cache的引入與緩存容量的增大霞溪， 可以大幅提升CPU內(nèi)部讀取數(shù)據(jù)的命中率，從而提高系統(tǒng)性能

高速緩存存儲器的構成

• 高速緩沖存儲器通常由高速存儲器中捆、 聯(lián)想存儲器鸯匹、 地址轉換部件、 替換邏輯等組成
• 聯(lián)想存儲器： 根據(jù)內(nèi)容進行尋址的存儲器
• 地址轉換部件： 通過聯(lián)想存儲器建立目錄表以實現(xiàn)快速地址轉換泄伪。 命中時直接訪問Cache殴蓬； 未命中時從內(nèi)存讀取放入Cache
• 替換部件： 在緩存已滿時按一定策略進行數(shù)據(jù)塊替換， 并修改地址轉換部件

高速緩存存儲器的組織

• 由于CPU芯片面積和成本蟋滴， Cache很小
• 根據(jù)成本控制染厅， 劃分為L1、 L2津函、 L3三級

image-20200429183335305

L1 Cache： 分為數(shù)據(jù)緩存和指令緩存肖粮；內(nèi)置； 其成本最高尔苦， 對CPU的性能影響最大涩馆； 通常在32KB-256KB之間

L2 Cache： 分內(nèi)置和外置兩種行施， 后者性能低一些； 通常在512KB-8MB之間

L3 Cache： 多為外置魂那， 在游戲和服務器領域有效蛾号； 但對很多應用來說， 總線改善比設置L3更加有利于提升系統(tǒng)性能

image-20200429183705217

單連續(xù)分區(qū)存儲管理

每個進程占用一個物理上完全連續(xù)的存儲空間(區(qū)域)

單用戶連續(xù)存儲管理

• 主存區(qū)域劃分為系統(tǒng)區(qū)與用戶區(qū)涯雅，設置一個柵欄寄存器界分兩個區(qū)域鲜结， 硬
  件用它在執(zhí)行時進行存儲保護

• 一般采用靜態(tài)重定位進行地址轉換，硬件實現(xiàn)代價低

  靜態(tài)重定位： 在裝入一個作業(yè)時活逆， 把該作業(yè)中程序的指令地址和數(shù)據(jù)地址全部轉換成絕對地址

  image-20200429201248032

• 適用于單用戶單任務操作系統(tǒng)精刷， 如DOS

固定分區(qū)存儲管理

• 支持多個分區(qū)
• 分區(qū)數(shù)量固定、大小固定
• 可用靜態(tài)重定位
• 硬件實現(xiàn)代價低
• 早期OS采用

image-20200429201511135

主存分配

主存分配表

image-20200429201601892

地址轉換

image-20200429202007910

可變分區(qū)存儲管理

按進程的內(nèi)存需求來動態(tài)劃分分區(qū)

創(chuàng)建一個進程時划乖， 根據(jù)進程所需主存量查看主存中是否有足夠的空閑空間

• 若有贬养， 則按需要量分割一個分區(qū)
• 若無挤土， 則令該進程等待主存資源

由于分區(qū)大小按照進程實際需要量來確定琴庵， 因此分區(qū)個數(shù)是隨機變化的

image-20200429202927852

已分配區(qū)表與未分配區(qū)表， 采用鏈表

image-20200429203018157

內(nèi)存分配

• 最先適應分配算法
• 鄰近適應分配算法
• 最優(yōu)適應分配算法
• 最壞適應分配算法

動態(tài)重定位

image-20200429203805356

內(nèi)存零頭

• 固定分區(qū)方式會產(chǎn)生內(nèi)存內(nèi)零頭
• 可變分區(qū)方式也會隨著進程的內(nèi)存分配產(chǎn)生一些小的不可用的內(nèi)存分區(qū)仰美， 稱為內(nèi)存外零頭
• 最優(yōu)適配算法最容易產(chǎn)生外零頭
• 任何適配算法都不能避免產(chǎn)生外零頭

移動技術（程序浮動技術）

移動分區(qū)以解決內(nèi)存外零頭迷殿，需要動態(tài)重定位支撐

image-20200429203515555

image-20200429203641069

頁式存儲管理

• 分頁存儲器將主存劃分成多個大小相等的頁架
• 受頁架尺寸限制， 程序的邏輯地址也自然分成頁
• 不同的頁可以放在不同頁架中咖杂， 不需要連續(xù)
• 頁表用于維系進程的主存完整性

頁表

頁式存儲管理中的地址

邏輯地址

頁式存儲管理的邏輯地址由兩部分組成庆寺，頁號和單元號， 邏輯地址形式：

image-20200429205234424

物理地址

頁式存儲管理的物理地址也有兩部分組成诉字，頁架號和單元號懦尝， 物理地址形式：

image-20200429205245188

地址轉換

image-20200429205348154

代價

可變分區(qū)存儲的基準地址是存儲在寄存器中的，速度很快壤圃，而頁表放在主存陵霉，每次地址轉換必須訪問兩次主存

1. 按頁號讀出頁表中的相應頁架號
2. 按計算出來的絕對地址進行讀寫

存在問題： 降低了存取速度

解決辦法： 利用Cache存放部分頁表

快表

為提高地址轉換速度， 設置一個專用的高速存儲器伍绳， 用來存放頁表的一部分踊挠，存放在高速存儲器中的頁表部分就是快表

快表表項： 頁號， 頁架號

這種高速存儲器是聯(lián)想存儲器冲杀， 即按照內(nèi)容尋址效床， 而非按照地址訪問

因為要找的是頁號對應的頁架號，知道頁號权谁，不知道地址剩檀，所以是內(nèi)容尋址

eg:假定主存訪問時間為200毫微秒， 快表訪問時間為40毫微秒旺芽， 查快表的命中率是90%

平均地址轉換代價為

比兩次訪問主存的時間（400毫微秒）下降了36%

地址轉換流程

按邏輯地址中的頁號查快表

• 若該頁已在快表中沪猴， 則由頁架號和單元號形成絕對地址
• 若該頁不在快表中卤妒， 則再查主存頁表形成絕對地址， 同時將該頁登記到快表中
• 當快表填滿后字币， 又要登記新頁時则披， 則需在快表中按一定策略淘汰一個舊登記項

多道程序環(huán)境下的進程表

進程表中登記了每個進程的頁表。進程占有處理器運行時洗出， 其頁表起始地址和長度送入頁表控制寄存器

多道程序環(huán)境下的地址轉換

image-20200429213739251

內(nèi)存分配/去配

可用一張位示圖來記錄主存分配情況士复，建立進程頁表維護主存邏輯完整性

對于每個頁使用1位去記錄該頁是否被占用

image-20200429205652984

頁的共享

頁式存儲管理能夠實現(xiàn)多個進程共享程序和數(shù)據(jù)

• 數(shù)據(jù)共享： 不同進程可以使用不同頁號共享數(shù)據(jù)頁

• 程序共享： 不同進程必須使用相同頁號共享代碼頁

  同一個程序不同的進程代碼的位置是確定的

頁式虛擬存儲管理

把進程全部頁面裝入虛擬存儲器， 執(zhí)行時先把部分頁面裝入實際內(nèi)存翩活， 然后阱洪， 根據(jù)執(zhí)行行為， 動態(tài)調(diào)入不在主存的頁菠镇， 同時進行必要的頁面調(diào)出

首次只把進程第一頁信息裝入主存冗荸， 稱為請求頁式存儲管理

頁式虛擬存儲管理的頁表

需要擴充頁表項：

• 每頁的虛擬地址、 實際地址
• 主存駐留標志利耍、 寫回標志蚌本、 保護標志、 引用標志隘梨、可移動標志

image-20200429214322339

頁式虛擬存儲管理的實現(xiàn)

CPU處理地址

• 若頁駐留程癌， 則獲得塊號形成絕對地址
• 若頁不在內(nèi)存， 則CPU發(fā)出缺頁中斷

OS處理缺頁中斷

• 若有空閑頁架轴猎， 則根據(jù)輔存地址調(diào)入頁嵌莉， 更新頁表與快表等
• 若無空閑頁架， 則決定淘汰頁捻脖， 調(diào)出已修改頁锐峭， 調(diào)入頁， 更新頁表與快表

image-20200429214740079

image-20200429214814276

頁面調(diào)度

當主存空間已滿而又需要裝入新頁時可婶，頁式虛擬存儲管理必須按照一定的算法把已在主存的一些頁調(diào)出去沿癞。選擇淘汰頁的工作稱為頁面調(diào)度。選擇淘汰頁的算法稱為頁面調(diào)度算法扰肌。

頁面調(diào)度算法設計不當抛寝， 會出現(xiàn)（剛被淘汰的頁面立即又要調(diào)入， 并如此反復）曙旭，這種現(xiàn)象稱為抖動或顛簸盗舰。

缺頁中斷率

假定進程P共n頁， 系統(tǒng)分配頁架數(shù)m個桂躏。P運行中成功訪問次數(shù)為S钻趋， 不成功訪問次數(shù)為F， 總訪問次數(shù)A=S+F剂习。缺頁中斷率定義為： f=F/A

影響缺頁中斷率的因素

• 分配給進程的頁架數(shù)： 可用頁架數(shù)越多蛮位， 則缺頁中斷率就越低
• 頁面的大薪匣Α： 頁面尺寸越大， 則缺頁中斷率就越低
• 用戶的程序編制方法： 在大數(shù)據(jù)量情況下失仁， 對缺頁中斷率也有很大影響

eg：程序將數(shù)組置為“0”尸曼， 假定僅分得一個主存頁架， 頁面尺寸為128個字萄焦， 數(shù)組元素按行存放控轿， 開始時第一頁在主存

程序1：

int A[128][128];
for(int j=0;j<128;j++)
  for(int i=0;i<128;i++)
      A[i][j]=0;

內(nèi)循環(huán)按照行進行遍歷，導致每執(zhí)行一次賦值就要產(chǎn)生一次缺頁中斷拂封， 共產(chǎn)生(128×128－ 1)次缺頁中斷

程序2：

int A[128][128];
for(int i=0;i<128;i++)
  for(int j=0;j<128;j++)
      A[i][j]=0;

內(nèi)循環(huán)按照列進行遍歷茬射，共產(chǎn)生(128－ 1)次缺頁中斷

OPT頁面調(diào)度算法

理想的調(diào)度算法是： 當要調(diào)入新頁面時， 首先淘汰以后不再訪問的頁冒签， 然后選擇距現(xiàn)在最長時間后再訪問的頁在抛。該算法由Belady提出， 稱Belady算法萧恕， 又稱最佳算法（OPT）

OPT只可模擬刚梭， 不可實現(xiàn)

先進先出FIFO頁面調(diào)度算法

總是淘汰最先調(diào)入主存的那一頁， 或者說主存駐留時間最長的那一頁(常駐的除外)

模擬的是程序執(zhí)行的順序性廊鸥， 有一定合理性

最久未使用LRU頁面調(diào)度算法

淘汰最近一段時間較久未被訪問的那一頁望浩， 即那些剛被使用過的頁面， 可能馬上還要被使用到

模擬了程序執(zhí)行的局部屬性惰说， 既考慮了循環(huán)性又兼顧了順序性

嚴格實現(xiàn)的代價大(需要維持特殊隊列)

LRU算法的模擬實現(xiàn)
每頁建一個引用標志， 供硬件使用
設置一個時間間隔中斷： 中斷時頁引用標志置0
地址轉換時缘回， 頁引用標志置1
淘汰頁面時吆视， 從頁引用標志為0的頁中間隨機選擇
時間間隔多長是個難點

最不常用LFU頁面調(diào)度算法

淘汰最近一段時間內(nèi)訪問次數(shù)較少的頁面， 對OPT的模擬性比LRU更好

基于時間間隔中斷酥宴， 并給每一頁設置一個計數(shù)器啦吧，時間間隔中斷發(fā)生后， 所有計數(shù)器清0每訪問頁1次就給計數(shù)器加1選擇計數(shù)值最小的頁面淘汰

時鐘CLOCK頁面調(diào)度算法

• 采用循環(huán)隊列機制構造頁面隊列拙寡， 形成了一個類似于鐘表面的環(huán)形表

• 隊列指針則相當于鐘表面上的表針授滓， 指向可能要淘汰的頁面

• 使用頁引用標志位

工作流程

• 頁面調(diào)入主存時， 其引用標志位置1
• 訪問主存頁面時肆糕， 其引用標志位置1
• 淘汰頁面時般堆， 從指針當前指向的頁面開始掃描循環(huán)隊列
  • 把所遇到的引用標志位是1的頁面的引用標志位清0， 并跳過
  • 把所遇到的引用標志位是0的頁面淘汰诚啃， 指針推進一步

反置頁表

內(nèi)存管理單元MMU：CPU管理虛擬/物理存儲器的控制線路淮摔， 把虛擬地址映射為物理地址， 并提供存儲保護始赎， 必要時確定淘汰頁面和橙，是為頁式存儲管理設置的專門硬件機構仔燕。

反置頁表IPT：MMU用的數(shù)據(jù)結構

為什么需要反置頁表

在分頁系統(tǒng)中，每個進程都有一個頁表∧д校現(xiàn)代系統(tǒng)中可能存在大量進程晰搀，每個進程都允許很大的邏輯地址空間，因而進程可能擁有一個很大的頁表办斑，這些頁表會占用大量的內(nèi)存空間厕隧。而通過物理頁向邏輯頁映射就可以節(jié)省很大的存儲空間。

反置頁表如何實現(xiàn)

內(nèi)存中的每一個物理頁設置一個表項俄周，表項中存放進程號和頁號吁讨，最后系統(tǒng)只維護一張反置頁表。

image-20200430104624992

反置頁表的頁表項

進程號 頁號 標志位 鏈指針

進程號：使用該物理頁的進程號

頁號： 該物理頁對應的虛擬地址頁號

標志位： 有效峦朗、 引用建丧、 修改、 保護和鎖定等標志信息

鏈指針： 哈希鏈（哈希沖突的時候波势，通過鏈表串在一起）

反置頁表的哈希表

如果是使用頁表就可以直接從該進程的頁表查詢到頁架號翎朱，而現(xiàn)在采用的是反置頁表，在頁表到頁架號的映射上需要采用哈希查詢尺铣，所以要維系一個哈希表拴曲。

哈希函數(shù)輸入：進程號和頁號

哈希函數(shù)輸出：反置頁表項的指針

地址轉換過程

1. 通過哈希表查詢到反置頁表項的指針
2. 比對指向的頁表項的進程號和頁號
   • 相同，則該頁就是所需要的物理頁
   • 不相同凛忿，沿著鏈指針繼續(xù)
     • 如果有相同的澈灼，該頁就是所需要的物理頁
     • 沒有相同的，說明頁面不在內(nèi)存中店溢，而在虛擬內(nèi)存中叁熔，需要頁面置換

image-20200430105811444

段式存儲管理

段式存儲是面向開發(fā)人員的，開發(fā)人員根據(jù)自己的需要對程序進行劃分床牧，程序的不同的部分采用不同的段進行地址管理肖方，而對內(nèi)存的物理管理是基于可變分區(qū)存儲管理的科侈，只不過可變分區(qū)存儲管理是一個進程一個段，而段式存儲管理是一個進程多個段。

它與頁式管理也不同娩怎，也是管理對于開發(fā)人員是透明的考润，系統(tǒng)自動對軟件的內(nèi)存按照也進行切割泌枪。而且頁式管理每個頁是大小相等桦山，均勻分布的。而段式管理段的大小和位置是不確定的册踩。

段式程序設計

每個程序可由若干段組成泳姐， 每一段都可以從“0”開始編址， 段內(nèi)的地址是連續(xù)的

分段存儲器的邏輯地址由兩部分組成 段號單元號

image-20200430110727777

段式存儲管理的基本思想

段式存儲管理基于可變分區(qū)存儲管理實現(xiàn)暂吉， 一個進程要占用多個分區(qū)

硬件需要增加一組用戶可見的段地址寄存器（代碼段胖秒、 數(shù)據(jù)段缎患、 堆棧段， 附加段） 阎肝， 供地址轉換使用

存儲管理需要增加設置一個段表挤渔， 每個段占用一個段表項， 包括： 段始址风题、 段限長判导， 以及存儲保護、 可移動沛硅、 可擴充等標志位

image-20200430111438522

段的共享

通過不同進程段表中的項指向同一個段基址來實現(xiàn)

對共享段的信息必須進行保護眼刃， 如規(guī)定只能讀出不能寫入， 不滿足保護條件則產(chǎn)生保護中斷

image-20200430112527632

段頁式存儲管理

段式存儲管理可以基于頁式存儲管理實現(xiàn)

對于每一段進行頁式管理

對于每一段進行頁式管理

段頁式存儲管理的地址轉換

image-20200430113258327

image-20200430113318715