概述

什么是操作系統

管理計算機硬件和軟件資源的系統軟件

管理計算機系統的硬軟件分配調度資源的系統軟件

操作系統的目標

方便性、有效性、可擴充性、開放性

提高系統資源的利用率，提高系統的吞吐量

(資料圖片僅供參考)

基本功能

統一管理計算機資源處理器資源IO設備資源存儲器資源文件資源實現計算機資源的抽象IO設備管理軟件提供讀寫接口、文件管理軟件提供操作文件接口提供用戶與計算機之間的接口GUI命令行事系統調用形式

特征

最基本的特征，互為存在的條件：并發、共享

并發：指兩個和多個事件可以在同一時間間隔發生（同一時間段，但這個事件段很短），宏觀的同時，實際交替執行并行：指兩個或多個事件可以在同一時刻（同一個時間點）發生，多個CPU可以實現并行，一個CPU同一時刻只有一個程序在運行，同理可以在單個CPU上實現并發共享：OS中的資源可以共多個并發的程序共同使用 - 互斥共享：當資源被占用時，其他想使用的程序智能等待 - 同時訪問：某種資源并發的被多個程序訪問虛擬把一個物理實體轉變為若干個邏輯實體 - 時分復用技術：資源在時間上進行復用，不同程序并發使用，多道程序分時使用計算機的硬件資源，提高資源的利用率。 - 空分復用技術：用來實現虛擬磁盤（物理磁盤虛擬為邏輯磁盤，電腦上的C盤、D盤等）、虛擬內存（在邏輯上擴大程序的存儲容量）等，提高資源的利用率，提高編程效率。異步在多道程序環境下，允許多個進程并發執行，但由于資源等因素的限制，使進程的執行以“停停走走”的方式運行，而且每個進程執行的情況（運行、暫停、速度、完成）也是未知的。

中斷處理

中斷機制的作用：為了在多道批處理系統中讓用戶進行交互；

一.單道批處理系統

1.概念

2.特點

自動：作業自動運行，無需干預批量：磁帶上的各個作業按順序地進入內存，先調入先完成單道：內存中僅有一道程序運行，可以看成是串行的

3.CPU的利用情況

分析：外設和CPU交替空閑和忙碌，CPU和外設利用效率低

4.缺點

從單道批處理系統對CPU的利用情況可看出，作業運行過程中若發生IO請求，高速的CPU要等待低速的I/O操作完成，導致CPU資源利用率和系統吞吐量降低。

二. 多道批處理系統

1.概念

內存中存放多道程序，當某道程序因某種原因如執行I/O操作時而不能繼續運行放棄CPU時，操作系統便調度另一程序運行，這樣CPU就盡量忙碌，達到提高系統效率的目的。

2.特點

多道：內存同時存放多道程序宏觀上并行：進入系統的多道程序先后開始了自己的運行，但都未運行完畢微觀上串行：內存中多道程序輪流占有CPU，交替執行

3.CPU的利用情況

分析：程序A要通過操作系統的調度進行磁盤操作，B則進行磁帶操作。當程序A執行I/O請求時，A放棄了CPU，操作系統接著調度B，B開始占用CPU（紅寬線）,此時程序A的磁盤操作也在同時進行。

結論：A,B兩道程序相互穿插運行，使CPU和外設都盡量忙碌。

4.缺點

作業處理時間長交互能力差運行過程不確定

其他

中斷產生：

發生中斷時，CPU立馬切換到管態，開展管理工作；（管態又叫特權態，系統態或核心態，是操作系統管理的程序執行時，機器所處的狀態。）發生中斷后，當前運行的進程回暫停運行，由操作系統內核對中斷進行處理；對于不同的中斷信號，會進行不同的處理。

中斷的分類：

內中斷（也叫“異常”、“例外”、“陷入”）------- 信號來源：CPU內部，與當前執行指令有關；外中斷（中斷）----------信號來源：CPU外部，與當前執行指令無關。

外中斷的處理過程：

每執行完一個指令后，CPU都需要檢查當前是否有外部中斷信號；如果檢查到外部中斷信號，則需要保護被中斷進程的CPU環境（如程序狀態字PSW，程序計數器PC、各種通用寄存器）把他們存儲在PCB（進程控制塊中）；根據中斷信號類型轉入相應的中斷處理程序；恢復原進程的CPU環境并退出中斷，返回原進程繼續執行。

其他概念

指令

特權指令:不允許用戶程序使用(只允許操作系統使用)。如IO指令、置中斷指令非特權指令:普通的運算指令

程序

內核程序:系統的管理者，可執行—切指令、運行在核心態應用程序:普通用戶程序只能執行非特權指令，運行在用戶態

處理機狀態

用戶態(目態):CPU只能執行非特權指令核心態(又稱管態、內核態):可以執行所有指令用戶態到核心態:通過中斷（是硬件完成的)核心態到用戶態:特權指令psw的標志位 0用戶態 1核心態

原語

處于操作系統的最低層，是最接近硬件的部分。這些程序的運行具有原子性，其操作只能一氣呵成這些程序的運行時間都較短，而且調用頻繁。

中斷和異常

內中斷(異常，信號來自內部)自愿中斷指令中斷強迫中斷硬件中斷軟件中斷外中斷（中斷，信號來著外部)外設請求人工干預

系統調用

系統給程序員(應用程序)提供的唯一接口，可獲得OS的服務。在用戶態發生，核心態處理

體系結構

大內核微內核

進程管理

進程實體

引入進程目的

為了更好地描述和控制程序并發執行，實現操作系統的并發性和共享性（進程是動態的，程序是靜態的)

進程的定義

是計算機中的程序關于某數據集合上的一次運行活動，是系統進行資源分配和調度的基本單位（沒有引入線程時 ）

為什么需要進程：

進程是系統進行資源分配和調度的基本單位；進程作為程序獨立運行的載體保障程序正常執行；進程的存在使得操作系統資源的利用率大幅提升。

進程控制塊（PCB）

用于描述和控制進程運行的通用數據結構,記錄進程當前狀態和控制進程運行的全部信息，是進程存在的唯一標識。

進程（Process）與線程（Thread）：

線程：操作系統進行運行調度的最小單位。進程：系統進行資源分配和調度的基本單位。

區別與聯系：

一個進程可以有一個或多個線程；線程包含在進程之中，是進程中實際運行工作的單位；進程的線程共享進程資源；一個進程可以并發多個線程，每個線程執行不同的任務。

進程管理五狀態模型

創建狀態：創建進程時擁有PCB但其它資源尚未就緒。就緒狀態：其它資源（進程控制塊、內存、棧空間、堆空間等）都準備好、只差CPU的狀態。執行狀態：進程獲得CPU，其程序正在執行。阻塞狀態：進程因某種原因放棄CPU的狀態，阻塞進程以隊列的形式放置。終止狀態：進程結束由系統清理或者歸還PCB的狀態。

經典問題

生產者-消費者問題

有一群生產者進程在生產產品，并將這些產品提供給消費者進程進行消費，生產者進程和消費者進程可以并發執行，在兩者之間設置了一個具有n個緩沖區的緩沖池，生產者進程需要將所生產的產品放到緩沖區中（+1操作），消費者進程可以從緩沖區取走產品消費（-1操作）。

(感覺有點微服務的意思了)

產生問題：當兩者并發執行時可能出差錯，導致預期的結果與真實的結果不相符：當執行生產者+1和消費者-1操作之后，緩沖區的值從10變為了11。

問題解決

在緩沖區為空時，消費者不能再進行消費在緩沖區為滿時，生產者不能再進行生產在一個線程進行生產或消費時，其余線程不能再進行生產或消費等操作，即保持線程間的同步注意條件變量與互斥鎖的順序

由于前兩點原因，因此需要保持線程間的同步，即一個線程消費（或生產）完，其他線程才能進行競爭CPU，獲得消費（或生產）的機會。對于這一點，可以使用條件變量進行線程間的同步：生產者線程在product之前，需要wait直至獲取自己所需的信號量之后，才會進行product的操作；同樣，對于消費者線程，在consume之前需要wait直到沒有線程在訪問共享區（緩沖區），再進行consume的操作，之后再解鎖并喚醒其他可用阻塞線程。

哲學家進餐問題

有5個哲學家，他們的生活方式是交替的思考和進餐，哲學家們共同使用一張圓桌，分別坐在5張椅子上，圓桌上有5只碗和5只筷子。平時哲學家們只進行思考，饑餓時則試圖取靠近他們的左右兩只筷子，只有兩只筷子都被拿到的時候才能進餐，否則等待，進餐完畢后，放下左右筷子進行思考。

這會導致以下的問題，筷子就相當于臨界資源：

臨界資源指的是一些雖作為共享資源卻又無法同時被多個線程共同訪問的共享資源。當有進程在使用臨界資源時，其他進程必須依據操作系統的同步機制等待占用進程釋放該共享資源才可重新競爭使用共享資源。

問題解決

方法一：當兩邊的叉子都可用時才拿

當某一個哲學家能夠同時拿起左右兩只叉子時，才讓他拿，這樣就能夠保證不會因為每個科學家都只拿了一只叉子而導致死鎖。

為了保證能夠同時拿起，我們需要對拿叉子這一步驟進行加鎖，保證哲學家能夠同時拿起一雙叉子，而不會拿了一邊后另一邊被人搶走

class DiningPhilosophers {public:    DiningPhilosophers()     {}    void wantsToEat(int philosopher,                    function pickLeftFork,                    function pickRightFork,                    function eat,                    function putLeftFork,                    function putRightFork)     {        //對拿叉子進行這一流程進行加鎖，保證其能同時拿起一雙，而不會被其他人搶走        _lock.lock();        _fork[philosopher].lock();        _fork[(philosopher + 1) % 5].lock();_lock.unlock();//拿起左右叉子        pickLeftFork();        pickRightFork();        eat();//吃飯        //放下左右叉子        putLeftFork();        putRightFork();                //解鎖，讓其他人獲取叉子        _fork[philosopher].unlock();        _fork[(philosopher + 1) % 5].unlock();    }private:    mutex _lock;    mutex _fork[5];};

復制

方法二：限制就餐的哲學家數量(或者說，多加一支筷子)

如果要保證至少有一個哲學家能夠進餐，那么我們可以采用最簡單粗暴的方法，限制人數，只要同時進餐的哲學家不超過四人時，即使在最壞情況下，也至少有一個哲學家能夠拿到多出來的那一個叉子。

我們需要用到一個計數器來表示當前就餐的人數，為了保證線程安全我們需要用到一個互斥鎖和一個條件變量對其進行保護

class DiningPhilosophers {public:    DiningPhilosophers()        :_count(0)    {}    void wantsToEat(int philosopher,                    function pickLeftFork,                    function pickRightFork,                    function eat,                    function putLeftFork,                    function putRightFork)     {                unique_lock lock(_mtx);        _cond.wait(lock, [this]()->bool{            return _count < 4;        });    //當就餐人數不超過四人的時候允許拿叉子        ++_count;        _fork[philosopher].lock();        _fork[(philosopher + 1) % 5].lock();        pickLeftFork();        pickRightFork();        eat();        putLeftFork();        putRightFork();        _fork[philosopher].unlock();        _fork[(philosopher + 1) % 5].unlock();        --_count;        _cond.notify_one();//就餐完成，讓下一個人進來就餐    }private:    mutex _fork[5];    mutex _mtx;    condition_variable _cond;    int _count;};

復制

方法三：奇數先左后右，偶數先右后左

由于餐桌是一個如下圖的圓環，如果我們此時規定奇數位的哲學家先拿左邊的叉子，再拿右邊的叉子。而偶數位的哲學家先拿右邊的再拿左邊的，此時競爭情況如下圖所示

此時2號和3號哲學家爭搶3號叉子，4號和5號哲學家爭搶5號叉子，1號沒有競爭對手，直接獲取叉子1。

可以看到，在第一輪中所有哲學家先去爭搶奇數叉子，搶到偶數叉子后再去爭搶偶數叉子，這樣就能夠保證至少有一個科學家能夠獲得兩只叉子

class DiningPhilosophers {public:    DiningPhilosophers()    {}    void wantsToEat(int philosopher,                    function pickLeftFork,                    function pickRightFork,                    function eat,                    function putLeftFork,                    function putRightFork)     {        //如果是奇數則先搶左后搶右        if(philosopher & 1)        {            _fork[philosopher].lock();            _fork[(philosopher + 1) % 5].lock();            pickLeftFork();            pickRightFork();        }        //如果是偶數則先搶右后搶左        else        {            _fork[(philosopher + 1) % 5].lock();            _fork[philosopher].lock();            pickRightFork();            pickLeftFork();                    }        eat();  //吃飯        putLeftFork();  //放下叉子        putRightFork();        _fork[philosopher].unlock();        _fork[(philosopher + 1) % 5].unlock();    }private:    mutex _fork[5];};

復制

進程通信

管道/匿名管道(Pipes)：用于具有親緣關系的父子進程間或者兄弟進程之間的通信。

有名管道(Named Pipes): 匿名管道由于沒有名字，只能用于親緣關系的進程間通信。為了克服這個缺點，提出了有名管道。有名管道嚴格遵循先進先出(first in first out)。有名管道以磁盤文件的方式存在，可以實現本機任意兩個進程通信。

信號(Signal)：信號是一種比較復雜的通信方式，用于通知接收進程某個事件已經發生；

消息隊列(Message Queuing)：消息隊列是消息的鏈表,具有特定的格式,存放在內存中并由消息隊列標識符標識。管道和消息隊列的通信數據都是先進先出的原則。與管道（無名管道：只存在于內存中的文件；命名管道：存在于實際的磁盤介質或者文件系統）不同的是消息隊列存放在內核中，只有在內核重啟(即，操作系統重啟)或者顯式地刪除一個消息隊列時，該消息隊列才會被真正的刪除。消息隊列可以實現消息的隨機查詢,消息不一定要以先進先出的次序讀取,也可以按消息的類型讀取.比 FIFO 更有優勢。消息隊列克服了信號承載信息量少，管道只能承載無格式字 節流以及緩沖區大小受限等缺點。

信號量(Semaphores)：信號量是一個計數器，用于多進程對共享數據的訪問，信號量的意圖在于進程間同步。這種通信方式主要用于解決與同步相關的問題并避免競爭條件。

共享內存(Shared memory)：使得多個進程可以訪問同一塊內存空間，不同進程可以及時看到對方進程中對共享內存中數據的更新。這種方式需要依靠某種同步操作，如互斥鎖和信號量等。可以說這是最有用的進程間通信方式。

套接字(Sockets): 此方法主要用于在客戶端和服務器之間通過網絡進行通信。套接字是支持 TCP/IP 的網絡通信的基本操作單元，可以看做是不同主機之間的進程進行雙向通信的端點，簡單的說就是通信的兩方的一種約定，用套接字中的相關函數來完成通信過程。

進程同步

進程同步的作用

對競爭資源在多進程間進行使用次序的協調，使得并發執行的多個進程之間可以有效使用資源和相互合作。

進程間同步的四原則：

空閑讓進：資源無占用，允許使用；忙則等待：資源被占用，請求進程等待；有限等待：保證有限等待時間能夠使用資源；讓權等待：等待時，進程需要讓出CPU。

進程同步的方法

使用fork系統調用創建進程

使用fork系統調用無參數，fork會返回兩次，分別返回子進程id和0，返回子進程id的是父進程，返回0的是子進程。

如果創建失敗，返回-1

fork系統調用是用于創建進程的；fork創建的進程初始化狀態與父進程一樣；系統會為fork的進程分配新的資源

子進程一般繼承父進程：用戶信息、權限、目錄信息、信號信息、環境表、共享存儲段和資源限制。(86條消息) 子進程和父進程的關系和示例_xujiali5172923的博客-CSDN博客【Linux 進程】fork父子進程間共享數據分析 - 我得去圖書館了 - 博客園 (cnblogs.com)進程——父子進程共享 - _程序兔 - 博客園 (cnblogs.com)（1）父子進程子進程通過父進程創建，子進程的結束和父進程的運行是一個異步過程，即父進程永遠無法預測子進程什么時候結束。當子進程退出的時候，內核會釋放子進程所有資源，包括打開的文件，占用的內存等。但是依然會保留部分信息（進程id，退出狀態，運行時間），直到父進程通過wait/waitpid來調用獲取子進程狀態信息后才釋放(86條消息) 面試中常被問到的（18）父子進程，孤兒進程及僵尸進程_HT . WANG的博客-CSDN博客

孤兒進程

一個父進程退出，而它的一個或多個子進程還在運行，那么那些子進程將成為孤兒進程，孤兒進程將被init進程（1號進程）托管，由init進程負責完成狀態收集工作

IDEA啟動SpringBoot項目，關掉IDEA后，SpringBoot（未終止沒有斷開連接），仍在后臺

僵尸進程

通常情況下，子進程退出后，父進程會使用 wait或 waitpid函數進行回收子進程的資源，并獲得子進程的終止狀態。（如果父進程在子進程結束之前退出，則子進程由init接管。init將會以父進程身份對僵尸狀態的子進程進行處理）

但是，如果父進程先于子進程結束，則子進程成為孤兒進程。孤兒進程將被 init 進程（進程號為1）領養，并由 init 進程對孤兒進程完成狀態收集工作。

而如果子進程先于父進程退出，同時父進程太忙了，無瑕回收子進程的資源，子進程殘留資源（PCB）存放于內核中，變成僵尸（Zombie）進程，如下圖所示：

Linux系統僵尸進程詳解 - 良許Linux - 博客園 (cnblogs.com)

共享內存

在某種程度上，多進程是共同使用物理內存的，但是由于操作系統的進程管理，進程間的內存空間是獨立的，因此進程默認是不能訪問進程空間之外的內存空間的。

共享存儲允許不相關的進程訪問同一片物理內存；共享內存是兩個進程之間共享和傳遞數據最快的方式；共享內存未提供同步機制，需要借助其他機制管理訪問；

Unix域套接字

域套接字是一種高級的進程間通信的方法，可以用于同一機器進程間通信。

套接字（socket）：為網絡通信中使用的術語。

Unix系統提供的域套接字提供了網絡套接字類似的功能，如Nfinx、uWSGI等。

服務端和客戶端分別使用Unix域套接字的過程：

線程同步

線程同步的方法

互斥鎖

互斥鎖是最簡單的線程同步的方法，也稱為互斥量，處于兩態之一的變量：解鎖和加鎖，兩個狀態可以保證資源訪問的串行。原子性：指一系列操作不可被中斷的特性，要么全部執行完成，要么全部沒有執行。

自旋鎖

自旋鎖是一種多線程同步的變量，使用自旋鎖的線程會反復檢查鎖變量是否可用，自旋鎖不會讓出CPU，是一種忙等待狀態，即死循環等待鎖被釋放，自旋鎖的效率遠高于互斥鎖。特點：避免了進程或者線程上下文切換的開銷，但是不適合在單核CPU使用。

常見的例子：分布式鎖設計

讀寫鎖

是一種特殊的自旋鎖，允許多個讀操作同時訪問資源以提高讀性能，但是對寫操作是互斥的，即對多讀少寫的操作效率提升很顯著。

條件變量

是一種相對比較復雜的線程同步方法，條件變量允許線程睡眠，直到滿足某種條件，當滿足條件時，可以給該線程信號通知喚醒。

線程同步方法的對比

Linux的進程管理

進程類型

前臺進程：具有終端，可以和用戶交互；后臺進程：沒有占用終端，基本不和用戶交互，優先級比前臺進程低（將需要執行的命令以“&”符號結束）；守護進程：特殊的后臺進程，在系統引導時啟動，一直運行直到系統關閉（進程名字以“d”結尾的一般都是守護進程），如crond、sshd、httpd、mysqld…

(86條消息) 帶你了解Docker背后的守護進程_董哥的黑板報的博客-CSDN博客

進程標記

進程ID：非負整數，進程的唯一標記，每個進程擁有不同的ID；進程的狀態標記：R表示進程處于運行狀態，S表示進程處于睡眠狀態…

操作Linux進程的相關命令：

ps命令：列出當前的進程，結合-aux可以打印進程的詳細信息（ps -aux）；top命令：查看所有進程的狀態；kill命令：給進程發送信號。

作業管理(處理機調度)

處理機是什么？

簡單來說，處理機指的是硬件，它包含cpu在內（早期CPU由運算器和控制器組成，稱為中央處理機），而內核是操作系統中的概念，是操作系統的核心，是屬于軟件部分。

處理機包括中央處理器，主存儲器，輸入-輸出接口，加接外圍設備就構成完整的計算機系統。 處理機是處理計算機系統中存儲程序和數據，并按照程序規定的步驟執行指令的部件。程序是描述處理機完成某項任務的指令序列。 指令則是處理機能直接解釋、執行的信息單位。

概念

是對處理機進行分配，即從就緒隊列中按照定的算法(公平、高效)選擇一個進程并將處理機分配給它運行，以實現進程并發地執行。

分類

高級調度（作業調度）

按一定的原則從外存上處于后備隊列的作業中挑選一個（或多個）作業，給他們分配內存等必要資源，并建立相應的進程(建立PCB),以使它（們）獲得竟爭處理機的權利。

高級調度是輔存（外存）與內存之間的調度。每個作業只調入一次，調出一次。作業調入時會建立相應的PCB,作業調出時才撤銷PCB。高級調度主要是指調入的問題，因為只有調入的時機需要操作系統來確定，但調出的時機必然是作業運行結束才調出。

中級調度（內存調度）

為了使內存中的內存不至于太多，有時需要把某些進程從內存中調到外存。在內存使用情況緊張時，將一些暫時不能運行的進程從內存中對換到外存中等待。當內存有足夠的空閑空間時，再將合適的進程重新換入內存。

低級調度（進程調度）

主要任務是按照某種方法和策略從就緒隊列中選取一個進程，將處理機分配給它。進程調度是操作系統中最基本的一種調度，在一般的操作系統中都必須配置進程調度。進程調度的頻率很高，一般幾十毫秒一次。

(86條消息) 三級調度： 高級調度、中級調度、低級調度彭嘭嘭的博客-CSDN博客高級調度中級調度低級調度高級調度（作業調度）、低級調度（進程調度）、中級調度 - 簡書 (jianshu.com)

調度方式

剝奪式（搶占式）：進程1在運行，進程2優先級比進程1高，進程2直接上處理器原則1：優先級原則，允許優先級高的并且是新到的進程可以搶占當前進程的處理機。原則2：短進程原則原則3：時間片原則非剝奪式（非搶占式）：進程1在運行，即使進程2優先級比進程1高，進程2也得等待進程1執行完上處理器

非搶占式調度：只能由當前運行的進程主動放棄CPU；處理器一旦分配給某個進程，就讓該進程一直使用下去；調度程序不以任何原因搶占正在被使用的處理器；調度程序不以任何原因搶占正在被使用的處理器；搶占式調度：可由操作系統剝奪當前進程的CPU使用權。允許調度程序以一定的策略暫停當前運行的進程；保存好舊進程的上下文信息，分配處理器給新進程；

進程調度的三大機制

就緒隊列排隊

為了提高進程調度的效率，將就緒進程按照一定的方式排成隊列，以便調度程序可以最快找到就緒進程。

選擇運行進程委派

調度程序以一定的策略，選擇就緒進程，將CPU資源分配給它。

新老進程上下文切換

存當前進程的上下文信息，裝入被委派執行進程的運行上下文

調度準則

CPU利用率系統吞吐量

單位時間內cpu完成作業的數目

周轉時間

作業的完成時間-提交時間

等待時間

進程與等待處理機的時間之和

響應時間

從提交到第一次開始運行的時間

算法

先來先服務（FCFS）：

算法原理：按照作業（進程）到達的先后次序來進行調度，誰先來，誰就先被調度。缺點：忽略了作業的運行時間

短作業優先（SJF)：

算法原理：以作業的長短來計算優先級，作業越短優先級越高，作業長短以所要求的運行時間來衡量。缺點：必須預先知道作業的運行時間、對長作業不利，未考慮作業的緊迫程度。

例題：

解：“作業被調度進入運行后不再退出"意為非搶占式調用，job2到來時也得等待job1執行完

①job1最先達到，運行60分鐘，此時job2-6已經全部提交，此時從job2-6中挑選運行時間最短的，那么順序依次為1→5→6→3→4→2

標準流程如圖（要寫出作業號、提交時間、運行時間、開始時刻、完成時刻、周轉時間）：

②周轉時間=完成時間-提交時間

平均周轉時間=1/n *(N1+N2+……+Nn）

(n為作業過程總數，N1、N2為周轉時間）

優先級調度算法：

算法原理：FCFS、SJF兩種算法都不能反映進程的緊迫程度。而優先級調度算法是外部賦予進程相應的優先級，來體現出進程的緊迫程度，緊迫性進程優先運行

（如何確定優先級：

1、利用某一范圍內的一個整數，優先數

2、響應比的大小，誰響應比大，誰優先級就大——高響應比優先調度算法）

高響應比優先調度算法

響應比=作業周轉時間/作業處理時間=（作業處理時間+作業等待時間）/作業處理時間=1+（作業等待時間/作業處理時間）

時間片輪轉

適合系統：分時系統

算法原理：基于時間片的輪轉，非常公平，就緒隊列中的每一個進程每次僅僅運行一個時間片，并且每個進程是輪流運行。

首先按照FCFS策略把就緒進程排成一個就緒隊列，設置時間片，從第一個進程開始分配處理機，第一個進程的時間片執行完后，再從就緒隊列中新的隊首進程開始。若進程已經運行完，注意此時第一個進程就已經不在就緒隊列的隊首，而是從就緒隊列中刪除。若未執行完只是時間片完了，則是調度程序把它送往末尾去了。

多級反饋隊列調度算法

算法原理（調度機制）：

設置多個就緒隊列，每個隊列賦予不同的優先級，第一個隊列優先級最高，并且首先調度最高優先級，也就是第一個隊列里面的所有進程，僅當第一個隊列空閑時，才開始調度第二個隊列中的進程運行。優先級越高的隊列，時間片越小。

總結

先來先服務算法：按照在就緒隊列中的先后順序執行。短進程優先調度算法：優先選擇就緒隊列中估計運行時間最短的進程，不利于長作業進程的執行。高優先權優先調度算法：進程附帶優先權，優先選擇權重高的進程，可以使得緊迫的任務優先處理。時間片輪轉調度算法：按照FIFO的原則排列就緒進程，每次從隊列頭部取出待執行進程，分配一個時間片執行，是相對公平的調度算法，但是不能保證就是響應用戶。

死鎖

進程死鎖、饑餓、死循環的區別

死鎖：兩個或兩個以上的進程在執行過程中，由于競爭資源或者由于彼此通信而造成的一種阻塞的現象，若無外力作用，它們都將無法推進下去。永遠在互相等待的進程稱為死鎖進程。饑餓：由于長期得不到資源導致進程無法推進；死循環：代碼邏輯BUG。

死鎖的產生

競爭資源（共享資源數量不滿足各進程需求）、進程調度順序不當，當調度順序為A->B->C->D時會產生死鎖，但改為A->D->B->C則不會產生。

死鎖的必要條件

互斥條件：資源是獨占的且排他使用，進程互斥使用資源，即任意時刻一個資源只能給一個進程使用，其他進程若申請一個資源，而該資源被另一進程占有時，則申請者等待直到資源被占有者釋放。不可剝奪條件：進程所獲得的資源在未使用完畢之前，不被其他進程強行剝奪，而只能由獲得該資源的進程資源釋放。請求和保持條件：進程每次申請它所需要的一部分資源，在申請新的資源的同時，繼續占用已分配到的資源。循環等待條件：在發生死鎖時必然存在一個進程等待隊列{P1,P2,…,Pn},其中P1等待P2占有的資源，P2等待P3占有的資源，…，Pn等待P1占有的資源，形成一個進程等待環路，環路中每一個進程所占有的資源同時被另一個申請，也就是前一個進程占有后一個進程所申請地資源。

以上給出了導致死鎖的四個必要條件，只要系統發生死鎖則以上四個條件至少有一個成立。事實上循環等待的成立蘊含了前三個條件的成立，似乎沒有必要列出然而考慮這些條件對死鎖的預防是有利的，因為可以通過破壞四個條件中的任何一個來預防死鎖的發生。

死鎖的處理策略

預防死鎖的方法

破壞四個必要條件的中一個或多個。

破壞互斥條件：將臨界資源改造成共享資源（Spooling池化技術）；（可行性不高，很多時候無法破壞互斥條件）破壞請求保持條件：系統規定進程運行之前，一次性申請所有需要的資源；（資源利用率低，可能導致別的線程饑餓）

第一種方法靜態分配即每個進程在開始執行時就申請他所需要的全部資源。第二種是動態分配即每個進程在申請所需要的資源時他本身不占用系統資源。

破壞不可剝奪條件：當一個進程請求新的資源得不到滿足時，必須釋放占有的資源；（實現復雜，剝奪資源可能導致部分工作失效，反復申請和釋放造成額外的系統開銷）

一個進程不能獲得所需要的全部資源時便處于等待狀態，等待期間他占有的資源將被隱式的釋放重新加入到 系統的資源列表中，可以被其他的進程使用，而等待的進程只有重新獲得自己原有的資源以及新申請的資源才可以重新啟動，執行。

破壞環路等待條件：可用資源線性排序，申請必須按照需要遞增申請；（進程實際使用資源順序和編號順序不同，會導致資源浪費）

采用資源有序分配其基本思想是將系統中的所有資源順序編號，將緊缺的，稀少的采用較大的編號，在申請資源時必須按照編號的順序進行，一個進程只有獲得較小編號的進程才能申請較大編號的進程

銀行家算法

檢查當前資源剩余是否可以滿足某個進程的最大需求；如果可以，就把該進程加入安全序列，等待進程允許完成，回收所有資源；重復1，2，直到當前沒有線程等待資源；

(85條消息) 銀行家算法詳解（C語言）Sparky*的博客-CSDN博客銀行家算法數據結構

死鎖的檢測和解除

死鎖檢測算法，資源剝奪法，撤銷進程法（終止進程法），進程回退法；

存儲管理

存儲管理為了確保計算機有足夠的內存處理數據；確保程序可以從可用內存中獲取一部分內存使用；確保程序可以歸還使用后的內存以供其他程序使用。

內存分配的過程

單一連續分配（已經過時）固定分區分配動態分區分配（根據實際需要，動態的分配內存）

動態分配算法

首次適應算法（First Fit）：該算法從空閑分區鏈首開始查找，直至找到一個能滿足其大小要求的空閑分區為止。然后再按照作業的大小，從該分區中劃出一塊內存分配給請求者，余下的空閑分區仍留在空閑分區鏈中。特點： 該算法傾向于使用內存中低地址部分的空閑區，在高地址部分的空閑區很少被利用，從而保留了高地址部分的大空閑區。顯然為以后到達的大作業分配大的內存空間創造了條件。

> [(85條消息) 什么是高地址，什么是低地址，舉舉例說明？_高地址和低地址_方園幾里的博客-CSDN博客](https://blog.csdn.net/CSDNmilu/article/details/123095988)

復制缺點：低地址部分不斷被劃分，留下許多難以利用、很小的空閑區，而每次查找又都從低地址部分開始，會增加查找的開銷。最佳適應算法（Best Fit）：該算法總是把既能滿足要求，又是最小的空閑分區分配給作業。為了加速查找，該算法要求將所有的空閑區按其大小排序后，以遞增順序形成一個空白鏈。這樣每次找到的第一個滿足要求的空閑區，必然是最優的。孤立地看，該算法似乎是最優的，但事實上并不一定。因為每次分配后剩余的空間一定是最小的，在存儲器中將留下許多難以利用的小空閑區。同時每次分配后必須重新排序，這也帶來了一定的開銷。特點：每次分配給文件的都是最合適該文件大小的分區。缺點：內存中留下許多難以利用的小的空閑區。最壞適應算法（Worst Fit）：最壞適應算法是將輸入的作業放置到主存中與它所需大小差距最大的空閑區中。空閑區大小由大到小排序。特點：盡可能地利用存儲器中大的空閑區。缺點：絕大多數時候都會造成資源的嚴重浪費甚至是完全無法實現分配。

內存回收的過程

回收區在空閑區下方：不需要新建空閑鏈表節點；只需要把空閑區1的容量增大即可；回收區在空閑區上方：將回收區與空閑區合并；新的空閑區使用回收區的地址；回收區在空閑區中間方：將空閑區1、空閑區2和回收區合并；新的空閑區使用空閑區1的地址；僅僅剩余回收區：為回收區創建新的空閑節點；插入到相應的空閑區鏈表中去；

分區存儲管理

固定分區存儲管理

這一部分是內存分配過程的詳細介紹，可以簡單看一下

把主存中可分配的用戶區域預先劃分成若干個連續的分區，每個連續區的大小可以相同，也可以不同。但是，一旦劃分好分區之后，主存中分區的個數就固定了，且每個分區的大小也固定不變。這是一種靜態分區法。

在固定分區方式管理下，每個分區用來裝入一個作業。由于主存中有多個分區，就可同時在每個分區中裝入一個作業。所以，這種存儲管理方式適用于多道程序系統。

主存空間的分配與釋放

了管理主存空間的使用，必須設置一張“主存分配表”（分區說明表），以說明各分區的分配情況。主存分配表中應指出各分區的起始地址和長度，并為每個分區設一個標志位。當標志位為“0”時，表示對應的分區是空閑分區，當標志位為非“0”時，表示對應的分區已被某作業占用。空閑分區可以用來裝作業。

當作業隊列中有作業要裝入主存時，存儲管理可采用“順序分配算法”進行主存空間的分配。

順序查看主存分配表，找到一個標志為“0”的并且長度大于或等于欲裝入作業的地址空間長度的分區，則把此分區分配給該作業，相應表目的標志位改成作業名的標識；若找不到一個這樣的空閑分區，則該作業暫時不能裝入主存。

主存空間的釋放很簡單。某作業執行結束后必須歸還所占的分區，這時存儲管理根據作業名查看主存分配表，找到相應的表目后，把其中的標志位重新置成“0”即可。

地址轉換

固定分區管理方式下作業的地址轉換常采用靜態重定位技術。

(74條消息) 靜態重定位和動態重定位阿肆_Maggie的博客-CSDN博客靜態重定位

存儲保護

固定分區管理方式下只考慮判斷其物理地址即可。常采用“界限寄存器對”法。

If 下限地址<=物理地址<=上限地址

Then   繼續

復制

Else 產生“越界中斷” ，轉越界中斷的處理子程序

內存擴充

采用覆蓋技術

覆蓋技術是指一個程序的若干程序段和幾個程序的某些部分共享一個存儲空間。

固定分區的優缺點

優點：實現簡單，無外部碎片

缺點：

當用戶程序太大時，可能所有的分區都不能滿足需求，此時不得不采用覆蓋技術解決，但這又會降低性能會產生內部碎片，碎片大，存在小分區占用大作業的情況，內存利用率低。

解決辦法：采用可變分區存儲管理

可變分區存儲管理

內存管理的可變分區模式，又稱變長分區模式、動態分區分配模式。這種分配方式不會預先劃分內存分區，而是在進程裝入內存時，根據進程的大小動態地建立分區，并使分區的大小正好適合進程的需要。因此系統分區的大小和數目是可變的。

與固定分區的區別就是：動態的劃分分區。

克服固定分區管理的“內碎片”問題。

可變分區模式下，剛開始，OS就緒，但任何用戶程序未進入內存前整個用戶內存區是一大空間。已占用區和空閑分區并不是絕對的。必須有表來記錄分區的情況。程序進入內存時的例行工作就是分配空閑區和裝入程序，并修改相應的空閑表和已分配區表。一旦一個內存分區被分配給一個進程，該進程可以被裝入該塊中執行，裝入時需重定位。

可變分區分配的數據結構

可變分區分配算法

把一個新作業裝入內存時，需要按照一定的可變分區分配算法，從空閑分區表（或空閑分區鏈）中選出一個分區分配給該作業。

在可變分區分配方式中，當有很多空閑分區都滿足需求時，應該使用哪個分區進行分配?

這里介紹三種可變分區分配算法

算法思想：每次都從低地址開始查找，找到第一個能滿足大小的空閑分區。

實現步驟：

空閑區地址由低到高排序

=>1.順序查找各個空閑區，把第一個找到能容納申請要求的內存區分配給申請者.（若空閑區比作業長度大，則分割該空閑區。一部分分配給作業一部分空閑。）

=>2.調整相應的空閑分區表和已分配分區表。

評價：性能一般但實現比較簡單直接，易于釋放時合并相鄰空間分區。比較容易的滿足大作業的需要。完成一次分配平均需要的搜索次數較大，影響了工作效率。

盡可能地利用存儲器中低地址的空閑區，而盡量保存高地址的空閑區。

最佳適應算法

算法思想：由于可變分區分配是一種連續分配方式，為各進程分配的空間必須是連續的一整片區域。因此為了保證當“大進程”到來時能有連續的大片空間，優先使用更小的空閑區。

實現步驟：

空閑分區按容量遞增次序鏈接。每次分配內存時順序查找空閑分區表，找到大小能夠滿足要求的第一個空閑分區。

評價：盡可能地保留了較大的空間。 產生大量的不能被使用的很小的空閑區。因此這種方法會產生很多的外部碎片。所以該算法分配效果不一定是最佳的。

盡可能地利用存儲器中小的空閑區，而盡量保存大的空閑區。

最壞適應算法

算法思想：為了解決最佳適應算法的問題——即留下太多難以利用的小碎片，可以在每次分配時，優先使用最大的連續空閑區，這樣分配后的空閑區就不會太小，更方便使用。

實現步驟：

空閑分區按照容量遞減次序鏈接。每次分配內存時順序查找空閑分區表，找到大小能滿足要求的第一個空閑分區。

評價：分割后產生的空閑區一般仍可以供以后分配使用。工作一段時間后，不能滿足大作業對空閑區的請求。

盡可能地利用存儲器中大的空閑區。

三種算法的比較：

可變分區內存回收

只比固定分區管理增加了合并相鄰空閑區的操作。

主要是為了及時減少“外碎片”，利于今后大作業的到來。

實現回收內存空間，關鍵是修改空閑分區表和已分配分區表。

回收內存分區時可能會遇到的四種情況：

(a)若釋放區R既有上鄰空閑區，又有下鄰空閑區。將三個空閑區合并成一個大空閑區。

先將R與F2合并記為F2,

再將F2與F1合并記為F1,并將F2從鏈中刪除。

IF (B+H1=C) AND (C+L2=D)

THEN 修改空閑表，分配表。

(b)若釋放區R只有上鄰空閑區F1。

則只修改空閑區F1大小即可。

IF (D+H2=E)

THEN 修改空閑表，分配表。

(c)只有下鄰空閑區

修改空閑區F2的首地址。

F2的大小＝F2的大小＋R的大小

(d)既無上鄰又無下鄰空閑區

Else 修改釋放區的首地址為空閑區的起始地址

地址轉換

動態重定位

(74條消息) 靜態重定位和動態重定位阿肆_Maggie的博客-CSDN博客靜態重定位

分區的存儲保護

If 下限地址<=物理地址<=上限地址

Then 繼續

Else 產生“越界中斷” ，轉越界中斷的處理子程序

內存擴充

消除了固定分區管理造成的“內碎片”，但是不可避免的在內存空間造成“外碎片”。

采用移動（緊縮）技術。定時的或在內存緊張時，將內存中所有作業移到內存的一端，使其相鄰。

經過緊縮后的進程在內存中的位置發生了變化，若不對程序和數據的地址進行修改，在進程就無法運行。

要使其運行，必須進行“動態重定位”

注意：

＝》緊縮的時機：

（1）一旦有歸還的分區便進行緊縮，系統開銷大。

（2）分配算法發現各空閑區不夠用，但其和夠用時。此法緊縮開銷小，更實用。因此，實際的可變分區分配算法比固定分區分配算法主要增加了“緊縮”操作

頁式存儲管理

分頁存儲管理的思想：把內存分為一個個相等的小分區，再按照分區大小把進程拆分成一個個小部分。分頁存儲管理分為：實分頁存儲管理和虛分頁存儲管理

實分頁式存儲管理

實分頁式存儲最大的優點是內存利用率高，與目前流行的虛分頁存儲管理相比，具有實現簡單，程序運行快的優點。

基本原理

假設一個大型飯店，所有的客房都是標準的雙人間，部分客房已經住進客人，現在又有一個旅游團要求入住。接待員統計了一下，對旅游團領隊說：“貴團全體成員都能住下，兩人一個房間，但是不能住在同一樓層了，因為每層空著的客房不夠，更沒有幾個挨著的。請原諒！”。對于這樣的安排，一般人不會感到奇怪。因為旅游團本來就是由一位位個人或夫妻等組成的，而飯店的客房本來也是兩人一間的，兩人一組正好可住在一個客房里；另外，飯店幾乎每天都有入住的和退房的客人，想在同一樓層找幾間挨著的客房實在不容易。

將整個系統的內存空間劃分成一系列大小相等的塊，每一塊稱為一個物理塊、物理頁或實頁，頁架或頁幀（frame），可簡稱為塊（block）。所有的塊按物理地址遞增順序連續編號為0、1、2、……。

這里的塊相當于飯店的客房，系統對內存分塊相當于飯店把大樓所有的客房都設計成標準的雙人間。

每個作業的地址空間也劃分成一系列與內存塊一樣大小的塊，每一塊稱為一個邏輯頁或虛頁，也有人叫頁面，可簡稱為頁（page）。所有的頁按照邏輯地址遞增順序連續編號為0、1、2、……。

這里，對作業地址空間分頁就相當于把旅游團成員分成兩人一組。

一個作業，只要它的總頁數不大于內存中的可用塊數，系統就可以對它實施分配。系統裝入作業時，以頁為單位分配內存，一頁分配一個塊，作業所有的頁所占的塊可以不連續。系統同時為這個作業建立一個頁號與塊號的對照表，稱為頁表。

這就像飯店有個記錄客戶入住情況的客戶登記表一樣。另外，飯店安排客戶入住是要查看全部客房的使用情況一覽表，相應地系統給作業分配內存時要查看主存分配表或者內存塊說明表。

每個塊的大小是固定的，一般是個1/2KB～4KB之間的數值（請讀者思考：塊尺寸為什么太大或太小都不好），而且必須是個2的冪次。

對塊尺寸這樣規定相當于飯店規定客房是雙人間。可以設想一下，如果上例中飯店所有的客房都是十人間的話，效益肯定不如全是雙人間的好

實模式下分頁存儲管理的基本原理：

操作系統以頁框為單位為各個進程分配內存空間。系統自動地將作業的地址空間分頁，將系統的主存空間分塊，頁與塊等大小，在作業運行時，一次性把作業的全部頁面裝入內存，各個頁所占的內存塊可以不連續，也不必按先后順序，可以放到不相鄰的各個頁框中。

這實際是個把作業從地址空間映射到存儲空間的過程

(75條消息) 操作系統 頁式存儲 頁與塊之間的關系詳解marsggbo的博客-CSDN博客塊和頁

頁表

頁面的劃分完全是一種系統硬件的行為，一個邏輯地址放到這種地址結構中，自然就分成了頁號和頁內單元號兩部分。

頁面大小為：4KB

在分頁系統中，允許將作業（進程）的任一頁裝入到內存中的任一可用的物理塊中，但進程的地址空間本來是連續的，若把他分頁后裝入到不相鄰的物理塊中，要保證系統仍能正確運行，就要實現從進程的邏輯地址變換為內存的物理地址。

所以，系統為每個進程建立一張頁面映射表，簡稱頁表。

地址映射

在系統中設置地址變換機構，能將用戶進程地址空間中的邏輯地址變為內存空間中的物理地址。

由于頁面和物理塊的大小相等，頁內偏移地址和塊內偏移地址是相同的。無須進行從頁內地址到塊內地址的轉換。

地址變換機構的任務，關鍵是將邏輯地址中的頁號轉換為內存中的物理塊號。物理塊號內的偏移地址就是頁內偏移地址。

頁表的作用就是從頁號到物理塊號的轉換，所以地址變換的任務借助于頁表來完成的。

如果題目中是用十進制數表示邏輯地址，則：

例題1：有一系統采用頁式存儲管理，有一作業大小是8KB，頁大小為2KB，依次裝入內存的第7、9、10、5塊，試將虛地址7145，3412轉換成內存地址。

虛地址 3412

P＝3412 ％ 2048＝1

W＝3412 mod 2048＝1364

MA=9*2048+1364=19796

虛地址3412的內存地址是19796

虛地址 7145

P＝7145 ％ 2048 ＝3

W＝7145 mod 2048 ＝1001

MA=5*2048+1001=11241

虛地址7145的內存地址是：11241

快表

因為頁表是存放在內存中的，CPU要存取一個數據，需訪問主存兩次。

第一次：訪內存中的頁表，找到該頁的的物理塊號，將此塊號與頁內地址拼結形成物理地址；

第二次：真正訪問該物理地址，存取其中的內容。

這樣就把程序的執行速度降低一倍。

為了提高存取速度，在地址變換機構中增設一組寄存器，用來存放訪問的那些頁表。

快表是一種訪存速度比內存快很多的高速緩沖器。

把存放在高速緩沖寄存器中的頁表叫快表，這個高速緩沖寄存器又叫聯想存貯器（TLB）。與此對應，內存中的頁表稱為慢表。

當進程訪問一頁時，系統將頁號與快表中的所有項進行并行比較。若訪問的頁在快表中，即可立即進行地址轉換。

當被訪問的頁不在快表中時，去內存中查詢頁表，同時將頁表找到的內存塊號與虛頁號填入快表中

例題2：

快表命中率98%，訪問時間是10ns，內存訪問時間是100ns，平均訪問時間？

平均訪問時間=98%(10+100)+（1-98%）（10+100+100）

若快表命中

聯想寄存器檢索時間：10ns

訪問內存1次取數據時間：100ns

取數據總時間：110ns

若快表中未命中

聯想寄存器檢索時間：10ns

訪問內存1次檢索頁表時間：100ns

訪問內存1次取數據時間：100ns

取數據總時間：210ns

兩級和多級頁表

現代的大多數計算機系統，都支持非常大的邏輯地址空間(232~264)。頁表就變得非常大，要占用相當大的內存空間。可采用兩個方法來解決這一問題：

① 采用離散分配方式來解決難以找到一塊連續的大內存空間的問題：

② 只將當前需要的部分頁表項調入內存，其余的頁表項仍駐留在磁盤上，需要時再調入。

二級頁表如何實現地址變換？

頁的分配與回收

用一張“位示圖”構成主存分配表。位示圖的每一位與一個主存塊對應，其值為0，表示對應的主存塊空閑，其值為1，表示對應的主存塊已分配。

位示圖優點是占用內存空間小，可常駐內存，加快分配進程，但缺點是不夠直觀。

內存分配過程：

計算一個作業所需要的總塊數N

查位示圖，看看是否還有N個空閑塊

如果有足夠的空閑塊，則頁表長度設為N，可填入PCB中；申請頁表區，把頁表始址填入PCB

依次分配N個空閑塊，將塊號和頁號填入頁表

修改位示圖

存在的問題

為每個進程配置一張頁表，進程邏輯空間非常大，帶來的問題？

可以引入Inverted page tables(反置頁表)

反置頁表 – 按物理塊號排序

IBM RT; HP Spectrum…

反置頁表很大，使用Hash表加快檢索

所有在內存中的并發進程只有一張頁表

除了Hash表，聯想寄存器也被用來存放最近使用過的頁表項

分頁存儲管理方案的評價

優點：

較好地解決了碎片問題

打破了存儲分配的連續性要求

提高了主存的利用率

缺點：

頁內碎片

動態地址變換、方案實施需耗用額外的系統資源

存儲擴充問題沒有解決——作業大小受到限制，可用塊數小于作業需求時需等待

虛擬頁式存儲

虛擬存儲器

局部性原理(principle of locality)

指程序在執行過程中的一個較短時期，所執行的指令地址和指令的操作數地址，分別局限于一定區域。還可以表現為：

時間局部性：一條指令的一次執行和下次執行，一個數據的一次訪問和下次訪問都集中在一個較短時期內；空間局部性：當前指令和鄰近的幾條指令，當前訪問的數據和鄰近的數據都集中在一個較小區域內。

局部性原理的具體體現：

程序在執行時，大部分是順序執行的指令，少部分是轉移和過程調用指令。過程調用的嵌套深度一般不超過5，因此執行的范圍不超過這組嵌套的過程。程序中存在相當多的循環結構，它們由少量指令組成，而被多次執行。程序中存在相當多對一定數據結構的操作，如數組操作，往往局限在較小范圍內。

引入虛擬存儲技術的好處

大程序：可在較小的可用內存中執行較大的用戶程序；

大的用戶空間：提供給用戶可用的虛擬內存空間通常大于物理內存(real memory)

并發：可在內存中容納更多程序并發執行；

易于開發：與覆蓋技術比較，不必影響編程時的程序結構

虛擬存儲技術的特征

不連續性：物理內存分配的不連續，虛擬地址空間使用的不連續（數據段和棧段之間的空閑空間，共享段和動態鏈接庫占用的空間）

部分交換：與交換技術相比較，虛擬存儲的調入和調出是對部分虛擬地址空間進行的；

大空間：通過物理內存和快速外存相結合，提供大范圍的虛擬地址空間

虛擬存儲技術的種類

虛擬頁式虛擬段式虛擬段頁式

虛擬頁式存儲管理

基本原理

系統自動地將作業的地址空間分頁，將系統的主存空間分塊，頁與塊等大小，在作業運行前，只把初始需要的一部分頁面裝入內存塊里，運行中需要訪問自己地址空間中的但當前不在內存的頁面時產生缺頁中斷，由缺頁中斷服務程序將所需的頁面調入內存，若此時內存中沒有空閑物理塊安置請求調入的新頁面，則系統按預定的置換策略自動選擇一個或一些在內存的頁面，把它們換出到外存。

虛擬頁式存儲管理實際是實分頁技術與虛擬存儲技術相結合的產物，其分頁思想與實分頁是一樣的。

這里的請求調入和置換功能都是比實分頁存儲管理增加的內容，是實現虛擬存儲的主要功能。

為實現虛擬頁式存儲管理:

需要置換技術、請求裝入技術和大硬盤支持，另外：

頁表表目需要增加外存塊號、狀態位、訪問位或訪問字段、修改位、存取控制字段等。外存塊號指出該頁在外存的地址，供調入該頁時用；狀態位指示該頁是否在內存；訪問位或訪問字段則是該頁被訪問過的標志或被訪問過的次數；修改位表示該頁是否被修改過；存取控制字段則是用來限制頁面被安全共享的。

作業1在請求分頁系統中的存儲映像

當執行 “mov r1，[2120］”時

CPU產生的虛地址為2120

分頁機構得 p=2，w=72（每頁1K）

查頁表。該頁中斷位i=1，發生缺頁中斷

如主存中有空白塊，直接調入

如主存中無空白塊，則需淘汰該作業在主存中的一頁

主存頁面分配策略

在虛擬頁式存儲管理中，內存分配似實分頁方式，但還必須考慮解決下面兩個問題：

（1）是否對各進程采用平均分配策略？a、平均分配。b、按進程長度比例分配。c、按進程優先級分配。d、按進程長度和優先級別分配。（2）發生缺頁中斷時，如何為所缺的頁面分配內存？a、固定分配局部置換。b、可變分配全局置換。

頁面調入策略

（1）請求調入

當發生頁面故障時進行調度，即當進程訪問不在內存的頁面引發缺頁中斷時，由系統根據這種訪問請求把所缺頁面裝入內存。

優點：由請求調入策略裝入的頁一定會被訪問，再加之比較容易實現，故在目前的虛擬存儲器中，大多采用此策略。

缺點：每次僅調入一頁，增加了磁盤I/O的啟動頻率。

（ 2）預調入

=>也稱先行調度，即一頁面被訪問前就已經預先置入內存，以減少今后的缺頁率。

=>主要適于進程的許多頁存放在外存的連續區域中的情況。有的系統結合請求調入使用，即每次缺頁時裝入多個頁面。

優點：提高調頁的I/O效率。

缺點：基于預測，若調入的頁在以后很少被訪問，則效率低。常用于程序裝入時的調頁。

調入頁面的來源：

通常對外存交換區的I/O效率比文件區的高。

進程裝入時，將其全部頁面復制到交換區，以后總是從交換區調入。執行時調入速度快，要求交換區空間較大。

凡是未被修改的頁面，都直接從文件區讀入，而被置換時不需調出；已被修改的頁面，被置換時需調出到交換區，以后從交換區調入。

存儲分配的安全性考慮:

把一個頁面分配給進程之前，先要清除頁面中的數據（如全部填充為0），以免該進程讀取前一進程遺留在頁面中的數據；

頁面調度算法

由缺頁中斷服務程序將所需的頁面調入內存，若此時內存中沒有空閑物理塊安置請求調入的新頁面，則系統按預定的策略自動選擇一個（請求調入策略）或一些（預調入策略）在內存的頁面，把它們換出到外存。

a、什么是淘汰策略（置換策略）？

用來選擇淘汰哪一頁的規則就叫做置換策略，或稱淘汰算法。如何決定淘汰哪一頁？根據頁面在系統中的表現（如：使用的頻繁程度、進入系統時間的長短）

b、顛簸

顛簸(thrashing)，又稱為“抖動”。

簡單地說，導致系統效率急劇下降的主存和輔存之間的頻繁頁面置換現像稱為“抖動”。

現象？淘汰的頁面恰好是不久又要訪問的頁面。

缺頁率 = (頁面置換次數+分配給該進程的物理塊數)/要訪問的頁面總數(75條消息) 缺頁率的計算方法水中魚自由的博客-CSDN博客_缺頁率怎么算

（1）最佳淘汰算法——OPT(Optimal)

這是Belady貝萊迪于1966年提出的一種理論上的算法。該算法每次都淘汰以后永不使用的，或者過最長的時間后才會被訪問的頁面。

顯然，采用這種算法會保證最低的缺頁率，但它是無法實現的，因為它必須知道頁面“將來”的訪問情況。不過，該算法仍有一定意義，可作為衡量其他算法優劣的一個標準。

假定系統為某個進程分配了三個物理塊，進程的訪問順序為7，0，1，2，0，3，0，4，2，3，0，3，2，1，2

采用OPT淘汰算法：

這是最早出現的淘汰算法。

總是淘汰最先進入內存的頁面。它實現簡單，只需把進程中已調入內存的頁面，按先后次序鏈成一個隊列，并設置一個所謂的替換指針，使它總是指向內存中最老的頁面。

缺點：效率不高，因為它與進程實際的運行規律不相適應，比如常用的全局變量所在的頁面或者循環體所在頁面都可能被它選為淘汰對象。出現bleady現象。

頁面進入主存的先后次序：

2->4->5->1

當要調入第6頁時：

置換第2頁

將第2頁改為6

替換指針指向第4頁4->5->1->6

Belady現象：采用FIFO算法時，如果對一個進程未分配它所要求的全部頁面，有時就會出現分配的頁面數增多，缺頁率反而提高的異常現象。

Belady現象的描述：一個進程P要訪問M個頁，OS分配N個內存頁面給進程P；對一個訪問序列S，發生缺頁次數為PE（S,N）。當N增大時，PE(S, N)時而增大，時而減小。

Belady現象的原因：FIFO算法的置換特征與進程訪問內存的動態特征是非常不一致的，即被置換的頁面通常并不是進程不會訪問的。

采用FIFO淘汰算法：

（3） 最近最久未使用算法(LRU, Least Recently Used）

根據頁面調入內存后的使用情況，選擇內存中最久未使用的頁面被置換。這是局部性原理的合理近似，性能接近最佳算法。

OPT算法使用頁面將要被訪問的時間，LRU算法使用頁面最后一次被訪問的時間。二者唯一的差別是：OPT是向前看的，而LRU是向后看的。

下面給出LRU的實現算法：

a、計時法：對于每一頁面增設一個訪問時間計時器，每當一個頁面被訪問時，當時的絕對時鐘內容被拷貝到對應的訪問時間計時器中，這樣系統記錄了內存中所有頁面最后一次被訪問的時間。淘汰時，選取訪問時間計時器的值最小的頁面。

b、堆棧法：每當進程訪問某頁面時，便將該頁面的頁號從棧中移出，將它壓入棧頂。棧頂始終是最新被訪問的頁面的編號。棧底則是最近最久未被使用的頁面的頁面號。

c、多位寄存器法

為每頁設置一個R位的寄存器

每次訪問一頁時，將該頁所對應的寄存器最左位置1

每隔時間間隔T，所有寄存器右移一位。

選擇R值最小的頁淘汰。

例如，r寄存器共有四位，頁面P0、P1、P2在T1、T2、T3時刻的r寄存器內容如下：

頁面 時刻

T1      T2      T3    

復制

P0 1000 0100 1010

P1 1000 1100 0110

P2 0000 1000 0100

給某作業分配了三塊主存，該作業依次訪問的頁號為：4，3，0，4，1，1，2，3，2。當訪問這些頁時，頁面淘汰序列變化情況如下

LRU的開銷是很大的，必須有硬件的支持，完全由軟件實現其速度至少會減少10倍，因此LRU近似算法更實用些

（4）二次機會淘汰算法——SC(Second Chance)淘汰算法

這是一種LRU的近似算法，是通過對FIFO算法進行簡單改造，結合頁表中的訪問位而得來一種淘汰算法。

該算法首先檢查位于FIFO鏈鏈首的頁，如果它的訪問位為0，則選擇該頁淘汰；如果它的訪問位為1，則清除其訪問位，將它移至FIFO鏈的鏈尾，重復此算法的查找過程，直至遇到新鏈首頁是一個訪問位為0的較早進入內存的頁為止，把它選為被淘汰的頁。

為每一個存儲塊（存儲分塊表）或頁面（頁表）設立一個引用位。

當訪問某頁時，就將該頁引用位置1

頁面管理軟件周期性地（設周期為T）將所有引用位重新置0

在T內，被訪問過的頁面引用位為1，否則為0

選擇引用位為0的頁面淘汰。

（5）時鐘(Clock)淘汰算法

二次機會淘汰算法缺點：就是需要把訪問位為1的處于鏈首的頁移至鏈尾，這需要一定的開銷。

改進的方法：就是把進程所訪問的頁面鏈成一個環形鏈表，再設一個指針指向最老的頁面，于是形成了一種簡單實用的LRU近似算法——時鐘淘汰算法。

該算法首先檢測指針所指的頁面，如果它的訪問位為0，則淘汰該頁，新裝入的頁插入到此位置，然后指針前進一個位置；如果它的訪問位為1，則清除為0，并將指針前進一個位置，繼續檢查訪問位。重復此過程，直到找到訪問位為0的頁面為止。

訪問頁號727

引發缺頁

（6）最近未用淘汰算法——NRU(Not Used Recently)淘汰算法

它把FIFO算法的思想與頁面的訪問位和修改位結合起來確定一個接近LRU算法的淘汰對象。

該算法每次都盡量選擇最近最久未被寫過的頁面淘汰，這種干凈的頁面可以不被寫回到磁盤。在實現時，為每一個頁面設置初始值0的訪問位和修改位。當對某頁面執行寫操作時，其修改位和訪問位均由硬件置成1；當對某頁面執行讀操作時，只有其訪問位被硬件置成1。系統每隔固定時間將所有訪問位都清0。

按照下列次序選擇被淘汰的頁面：

①訪問位＝０，修改位＝０；直接淘汰；

②訪問位＝０，修改位＝１；寫回外存后淘汰；

③訪問位＝１，修改位＝０；直接淘汰；

④訪問位＝１，修改位＝１；寫回外存后淘汰；

頁面請求序列為：2，3，2，1，5，2，4，5，3，2，5，2

內存分配3塊

用OPT、LRU、FIFO、Clock算法寫出頁面置換過程

時鐘clock算法中的箭頭是當前指針的位置！

影響缺頁中斷率的因素

（1）頁面調度算法不合理

抖動又叫顛簸，是指一段時間里，頁面在內存與外存之間頻繁地調度或換入換出，以至于系統用于調度頁面所需要的時間比進程實際運行所占用的時間還要多。

顯然，抖動是由于缺頁中斷率很高而引起的一種壞現象，它將嚴重影響系統的效率，甚至可能使系統全面崩潰。

（2）分配給作業的內存塊數太少

作業的缺頁中斷率與作業所占內存塊數成反比。分配給作業的內存塊數太少是導致抖動現象發生的最主要的原因，實驗分析表明：對所有的程序來說，要使其有效地工作，它在內存中的頁面數不應少于它的總頁面數的一半。

（3）頁面大小的選擇不合理

雖然缺頁中斷率與頁面尺寸成反比，但頁面尺寸卻不能一味地求大，它一般在0.5KB~4KB之間，是個實驗統計值。因為頁面大時，頁表較小，占空間少，查表速度快，缺頁中斷次數少，但頁面調度時間長，頁內碎片較大。頁面小時，恰恰相反。

（4）用戶程序編制的方法不合適

作業的缺頁中斷率與程序的局部化（包括時間局部化和空間局部化）程度成反比。用戶程序編制的方法不合適可能導致程序運行的時空復雜度高，缺頁次數多。

段式存儲管理

分段

進程的地址空間：按照程序自身的邏輯關系劃分為若干個段，每個段都有一個段名（在低級語言中，程序員使用段名來編程），每段從0開始編址。內存分配規則：以段為單位進行分配，每個段在內存中占連續空間，但各段之間可以不相鄰。

分段系統的邏輯地址結構由段號（段名）和段內地址（段內偏移量）所組成。

段表

每一個程序設置一個段表，放在內存,屬于進程的現場信息

地址變換

段的保護

越界中斷處理

進程在執行過程中，有時需要擴大分段，如數據段。由于要訪問的地址超出原有的段長，所以發越界中斷。操作系統處理中斷時 ，首先判斷該段的“擴充位”，如可擴充，則增加段的長度；否則按出錯處理

缺段中斷處理

檢查內存中是否有足夠的空閑空間

復制①若有，則裝入該段，修改有關數據結構，中斷返回②若沒有，檢查內存中空閑區的總和是否滿足要求，是則應采用緊縮技術，轉 ① ；否則，淘汰一（些）段，轉①

段的動態連接

為何要進行段的動態鏈接？

大型程序由若干程序段，若干數據段組成，進程的某些程序段在進程運行期間可能根本不用，互斥執行的程序段沒有必要同時駐留內存，有些程序段執行一次后不再用到，靜態鏈接花費時間，浪費空間

在一個程序運行開始時，只將主程序段裝配好并調入主存。其它各段的裝配是在主程序段運行過程中逐步進行的。每當需要調用一個新段時，再將這個新段裝配好，并與主程序段連接。

頁式存儲管理：難以完成動態鏈接，其邏輯地址是一維的

信息的保護與共享

這里主要與頁式存儲管理進行一下對比。

分段比分頁更容易實現信息的共享和保護。

只讀代碼共享

純代碼舉例：比如，有一個代碼段只是簡單的輸出“Hello World!”。

頁式系統與段式系統的對比

段長是可變的，頁的大小是固定的。

分段存儲：段內地址W字段溢出將產生越界中斷。

分頁存儲：段內地址W字段溢出會自動加入到頁號中。

總結

段頁式存儲管理

分頁、分段的有缺點分析

基本思想

用戶程序劃分：按段式劃分（對用戶來講，按段的邏輯關系進行劃分；對系統講，按頁劃分每一段）

邏輯地址：

內存劃分：按頁式存儲管理方案內存分配：以頁為單位進行分配

邏輯地址結構

段表頁表

地址轉換

評價

優點：

保留了分段和請求分頁存儲管理的全部優點

提供了虛存空間，能更有效利用主存

缺點：

增加了硬件成本

系統復雜度較大

總結

虛擬內存

這一部分在虛擬頁式存儲管理講過了

虛擬內存概述：是操作系統內存管理的關鍵技術，使得多道程序運行和大程序運行成為現實，把程序使用內存劃分，將部分暫時不使用的內存放置在輔存，實際是對物理內存的擴充。

局部性原理：指CPU訪問存儲器時，無論是存取指令還是存取數據，所訪問的存儲單元都趨于聚集在一個較小的連續區域中。??虛擬內存的置換算法：先進先出（FIFO）、最不經常使用（LFU）、最近最少使用（LRU）...

虛擬內存的特征：

多次性：無需再作業運行時一次性全部裝入內存，而是允許被分成多次調入內存；對換性：無需在作業運行時一直常駐內存，而是允許在作業運行過程中，將作業換入、換出；虛擬性：從邏輯上擴充了內存的容量，使用戶看到的內存用來，遠大于實際的容量；

Linux的存儲管理

Buddy內存管理算法：經典的內存管理算法，為解決內存外碎片的問題，算法基于計算機處理二進制的優勢具有極高的效率。

Linux交換空間：交換空間（Swap）是磁盤的一個分區，Linux內存滿時，會把一些內存交換至Swap空間，Swap空間是初始化系統時配置的。

Swap空間與虛擬內存的對比：

文件管理

文件的邏輯結構：

邏輯結構的文件類型：有結構文件（文本文件，文檔，媒體文件）、無結構文件（二進制文件、鏈接庫）。順序文件：按順序放在存儲介質中的文件，在邏輯文件當中存儲效率最高，但不適合存儲可變長文件。索引文件：為解決可變長文件存儲而發明，需要配合索引表存儲。

輔存的存儲空間分配：

輔存的分配方式：連續分配（讀取文件容易，速度快）、鏈接分配（隱式鏈接和顯式鏈接）、索引分配輔存的存儲空間管理：空閑表、空閑鏈表、位示圖。

目錄樹：使得任何文件或目錄都有唯一的路徑。

設備管理

基本概念：將數據輸入輸出計算機的外部設備；

廣義的IO設備：

按照使用特性分類：存儲設備（內存、磁盤、U盤）和交互IO設備（鍵盤、顯示器、鼠標）；按照信息交換分類：塊設備（磁盤、SD卡）和字符設備（打印機、shell終端）；按照設備共享屬性分類：獨占設備，共享設備，虛擬設備；按照傳輸速率分類：低速設備，高速設備；IO設備的緩沖區：減少CPU處理IO請求的頻率，提高CPU與IO設備之間的并行性。

SPOOLing技術：虛擬設備技術，把同步調用低速設備改為異步調用，在輸入、輸出之間增加了排隊轉儲環節(輸入井、輸出井)，SPoOLing負責輸入（出）井與低速設備之間的調度，邏輯上，進程直接與高速設備交互，減少了進程的等待時間。

實現支持異步任務的線程池

線程池：線程池是存放多個線程的容器，CPU調度線程執行后不會銷毀線程，將線程放回線程池重新利用。

使用線程池的原因：

線程是稀缺資源 ，不應該頻繁創建和銷毀；架構解耦，業務創建和業務處理解耦，更加優雅；線程池是使用線程的最佳實踐。

實現線程安全的隊列Queue

隊列：用于存放多個元素，是存放各種元素的“池”。實現的基本功能：獲取當前隊列元素數量，往隊列放入元素，往隊列取出元素。注意：隊列可能有多個線程同時操作，因此需要保證線程安全，如下兩種情況：

實現基本任務對象Task實現的基本功能：任務參數，任務唯一標記（UUID），任務具體的執行邏輯實現任務處理線程ProcessThread：任務處理線程需要不斷地從任務隊列里取任務執行，任務處理線程需要有一個標記，標記線程什么時候應該停止。實現的基本功能：基本屬性（任務隊列、標記），線程執行的邏輯（run），線程停止（stop）。實現任務處理線程池Pool：存放多個任務處理線程，負責多個線程的啟停，管理向線程池的提交任務，下發給線程去執行。實現的基本過程：基本屬性，提交任務（put，batch_put），線程啟停（start，join），線程池大小（size）。實現異步任務處理AsyncTask：給任務添加一個標記，任務完成后，則標記為完成；任務完成時可直接獲取任務運行結果；任務未完成時，獲取任務結果，會阻塞獲取線程。主要實現的兩個函數：設置運行結果（set_result），獲取運行結果（get_result)

本文有對以下文章進行參考：

計算機操作系統知識點總結（有這一篇就夠了！！！）原來如此呀的博客-CSDN博客操作系統

操作系統常見面試題總結 | JavaGuide(Java面試+學習指南)

【操作系統】生產者消費者問題niliushall.的博客-CSDN博客生產者消費者問題

哲學家進餐問題的三種解決方法(C++11)凌桓丶的博客-CSDN博客哲學家進餐問題3種代碼

死鎖的四個必要條件Hyacinth_Dy的博客-CSDN博客死鎖的四個必要條件

首次適應算法和最佳適應算法莫顧爾在的博客-CSDN博客首次適應

操作系統——段式存儲管理、段頁式存儲管理 - 王陸 - 博客園 (cnblogs.com)

操作系統——頁式存儲管理 - 王陸 - 博客園 (cnblogs.com)

缺頁率的計算方法水中魚自由的博客-CSDN博客_缺頁率怎么算

操作系統 三小時速成課 課時2 進程調度_嗶哩嗶哩_bilibili

編輯：qysb005