概述

什么是操作系統(tǒng)

管理計算機(jī)硬件和軟件資源的系統(tǒng)軟件

管理計算機(jī)系統(tǒng)的硬軟件分配調(diào)度資源的系統(tǒng)軟件

操作系統(tǒng)的目標(biāo)

方便性、有效性、可擴(kuò)充性、開放性

提高系統(tǒng)資源的利用率，提高系統(tǒng)的吞吐量

(資料圖片僅供參考)

基本功能

統(tǒng)一管理計算機(jī)資源處理器資源IO設(shè)備資源存儲器資源文件資源實現(xiàn)計算機(jī)資源的抽象IO設(shè)備管理軟件提供讀寫接口、文件管理軟件提供操作文件接口提供用戶與計算機(jī)之間的接口GUI命令行事系統(tǒng)調(diào)用形式

特征

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

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

中斷處理

中斷機(jī)制的作用：為了在多道批處理系統(tǒng)中讓用戶進(jìn)行交互；

一.單道批處理系統(tǒng)

1.概念

2.特點

自動：作業(yè)自動運行，無需干預(yù)批量：磁帶上的各個作業(yè)按順序地進(jìn)入內(nèi)存，先調(diào)入先完成單道：內(nèi)存中僅有一道程序運行，可以看成是串行的

3.CPU的利用情況

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

4.缺點

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

二. 多道批處理系統(tǒng)

1.概念

內(nèi)存中存放多道程序，當(dāng)某道程序因某種原因如執(zhí)行I/O操作時而不能繼續(xù)運行放棄CPU時，操作系統(tǒng)便調(diào)度另一程序運行，這樣CPU就盡量忙碌，達(dá)到提高系統(tǒng)效率的目的。

2.特點

多道：內(nèi)存同時存放多道程序宏觀上并行：進(jìn)入系統(tǒng)的多道程序先后開始了自己的運行，但都未運行完畢微觀上串行：內(nèi)存中多道程序輪流占有CPU，交替執(zhí)行

3.CPU的利用情況

分析：程序A要通過操作系統(tǒng)的調(diào)度進(jìn)行磁盤操作，B則進(jìn)行磁帶操作。當(dāng)程序A執(zhí)行I/O請求時，A放棄了CPU，操作系統(tǒng)接著調(diào)度B，B開始占用CPU（紅寬線）,此時程序A的磁盤操作也在同時進(jìn)行。

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

4.缺點

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

其他

中斷產(chǎn)生：

發(fā)生中斷時，CPU立馬切換到管態(tài)，開展管理工作；（管態(tài)又叫特權(quán)態(tài)，系統(tǒng)態(tài)或核心態(tài)，是操作系統(tǒng)管理的程序執(zhí)行時，機(jī)器所處的狀態(tài)。）發(fā)生中斷后，當(dāng)前運行的進(jìn)程回暫停運行，由操作系統(tǒng)內(nèi)核對中斷進(jìn)行處理；對于不同的中斷信號，會進(jìn)行不同的處理。

中斷的分類：

內(nèi)中斷（也叫“異?！?、“例外”、“陷入”）------- 信號來源：CPU內(nèi)部，與當(dāng)前執(zhí)行指令有關(guān)；外中斷（中斷）----------信號來源：CPU外部，與當(dāng)前執(zhí)行指令無關(guān)。

外中斷的處理過程：

每執(zhí)行完一個指令后，CPU都需要檢查當(dāng)前是否有外部中斷信號；如果檢查到外部中斷信號，則需要保護(hù)被中斷進(jìn)程的CPU環(huán)境（如程序狀態(tài)字PSW，程序計數(shù)器PC、各種通用寄存器）把他們存儲在PCB（進(jìn)程控制塊中）；根據(jù)中斷信號類型轉(zhuǎn)入相應(yīng)的中斷處理程序；恢復(fù)原進(jìn)程的CPU環(huán)境并退出中斷，返回原進(jìn)程繼續(xù)執(zhí)行。

其他概念

指令

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

程序

內(nèi)核程序:系統(tǒng)的管理者，可執(zhí)行—切指令、運行在核心態(tài)應(yīng)用程序:普通用戶程序只能執(zhí)行非特權(quán)指令，運行在用戶態(tài)

處理機(jī)狀態(tài)

用戶態(tài)(目態(tài)):CPU只能執(zhí)行非特權(quán)指令核心態(tài)(又稱管態(tài)、內(nèi)核態(tài)):可以執(zhí)行所有指令用戶態(tài)到核心態(tài):通過中斷（是硬件完成的)核心態(tài)到用戶態(tài):特權(quán)指令psw的標(biāo)志位 0用戶態(tài) 1核心態(tài)

原語

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

中斷和異常

內(nèi)中斷(異常，信號來自內(nèi)部)自愿中斷指令中斷強(qiáng)迫中斷硬件中斷軟件中斷外中斷（中斷，信號來著外部)外設(shè)請求人工干預(yù)

系統(tǒng)調(diào)用

系統(tǒng)給程序員(應(yīng)用程序)提供的唯一接口，可獲得OS的服務(wù)。在用戶態(tài)發(fā)生，核心態(tài)處理

體系結(jié)構(gòu)

大內(nèi)核微內(nèi)核

進(jìn)程管理

進(jìn)程實體

引入進(jìn)程目的

為了更好地描述和控制程序并發(fā)執(zhí)行，實現(xiàn)操作系統(tǒng)的并發(fā)性和共享性（進(jìn)程是動態(tài)的，程序是靜態(tài)的)

進(jìn)程的定義

是計算機(jī)中的程序關(guān)于某數(shù)據(jù)集合上的一次運行活動，是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位（沒有引入線程時 ）

為什么需要進(jìn)程：

進(jìn)程是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位；進(jìn)程作為程序獨立運行的載體保障程序正常執(zhí)行；進(jìn)程的存在使得操作系統(tǒng)資源的利用率大幅提升。

進(jìn)程控制塊（PCB）

用于描述和控制進(jìn)程運行的通用數(shù)據(jù)結(jié)構(gòu),記錄進(jìn)程當(dāng)前狀態(tài)和控制進(jìn)程運行的全部信息，是進(jìn)程存在的唯一標(biāo)識。

進(jìn)程（Process）與線程（Thread）：

線程：操作系統(tǒng)進(jìn)行運行調(diào)度的最小單位。進(jìn)程：系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位。

區(qū)別與聯(lián)系：

一個進(jìn)程可以有一個或多個線程；線程包含在進(jìn)程之中，是進(jìn)程中實際運行工作的單位；進(jìn)程的線程共享進(jìn)程資源；一個進(jìn)程可以并發(fā)多個線程，每個線程執(zhí)行不同的任務(wù)。

進(jìn)程管理五狀態(tài)模型

創(chuàng)建狀態(tài)：創(chuàng)建進(jìn)程時擁有PCB但其它資源尚未就緒。就緒狀態(tài)：其它資源（進(jìn)程控制塊、內(nèi)存、?？臻g、堆空間等）都準(zhǔn)備好、只差CPU的狀態(tài)。執(zhí)行狀態(tài)：進(jìn)程獲得CPU，其程序正在執(zhí)行。阻塞狀態(tài)：進(jìn)程因某種原因放棄CPU的狀態(tài)，阻塞進(jìn)程以隊列的形式放置。終止?fàn)顟B(tài)：進(jìn)程結(jié)束由系統(tǒng)清理或者歸還PCB的狀態(tài)。

經(jīng)典問題

生產(chǎn)者-消費者問題

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

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

產(chǎn)生問題：當(dāng)兩者并發(fā)執(zhí)行時可能出差錯，導(dǎo)致預(yù)期的結(jié)果與真實的結(jié)果不相符：當(dāng)執(zhí)行生產(chǎn)者+1和消費者-1操作之后，緩沖區(qū)的值從10變?yōu)榱?1。

問題解決

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

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

哲學(xué)家進(jìn)餐問題

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

這會導(dǎo)致以下的問題，筷子就相當(dāng)于臨界資源：

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

問題解決

方法一：當(dāng)兩邊的叉子都可用時才拿

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

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

class DiningPhilosophers {public:    DiningPhilosophers()     {}    void wantsToEat(int philosopher,                    function pickLeftFork,                    function pickRightFork,                    function eat,                    function putLeftFork,                    function putRightFork)     {        //對拿叉子進(jìn)行這一流程進(jìn)行加鎖，保證其能同時拿起一雙，而不會被其他人搶走        _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];};

復(fù)制

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

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

我們需要用到一個計數(shù)器來表示當(dāng)前就餐的人數(shù)，為了保證線程安全我們需要用到一個互斥鎖和一個條件變量對其進(jìn)行保護(hù)

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;        });    //當(dāng)就餐人數(shù)不超過四人的時候允許拿叉子        ++_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();//就餐完成，讓下一個人進(jìn)來就餐    }private:    mutex _fork[5];    mutex _mtx;    condition_variable _cond;    int _count;};

復(fù)制

方法三：奇數(shù)先左后右，偶數(shù)先右后左

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

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

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

class DiningPhilosophers {public:    DiningPhilosophers()    {}    void wantsToEat(int philosopher,                    function pickLeftFork,                    function pickRightFork,                    function eat,                    function putLeftFork,                    function putRightFork)     {        //如果是奇數(shù)則先搶左后搶右        if(philosopher & 1)        {            _fork[philosopher].lock();            _fork[(philosopher + 1) % 5].lock();            pickLeftFork();            pickRightFork();        }        //如果是偶數(shù)則先搶右后搶左        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];};

復(fù)制

進(jìn)程通信

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

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

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

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

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

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

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

進(jìn)程同步

進(jìn)程同步的作用

對競爭資源在多進(jìn)程間進(jìn)行使用次序的協(xié)調(diào)，使得并發(fā)執(zhí)行的多個進(jìn)程之間可以有效使用資源和相互合作。

進(jìn)程間同步的四原則：

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

進(jìn)程同步的方法

使用fork系統(tǒng)調(diào)用創(chuàng)建進(jìn)程

使用fork系統(tǒng)調(diào)用無參數(shù)，fork會返回兩次，分別返回子進(jìn)程id和0，返回子進(jìn)程id的是父進(jìn)程，返回0的是子進(jìn)程。

如果創(chuàng)建失敗，返回-1

fork系統(tǒng)調(diào)用是用于創(chuàng)建進(jìn)程的；fork創(chuàng)建的進(jìn)程初始化狀態(tài)與父進(jìn)程一樣；系統(tǒng)會為fork的進(jìn)程分配新的資源

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

孤兒進(jìn)程

一個父進(jìn)程退出，而它的一個或多個子進(jìn)程還在運行，那么那些子進(jìn)程將成為孤兒進(jìn)程，孤兒進(jìn)程將被init進(jìn)程（1號進(jìn)程）托管，由init進(jìn)程負(fù)責(zé)完成狀態(tài)收集工作

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

僵尸進(jìn)程

通常情況下，子進(jìn)程退出后，父進(jìn)程會使用 wait或 waitpid函數(shù)進(jìn)行回收子進(jìn)程的資源，并獲得子進(jìn)程的終止?fàn)顟B(tài)。（如果父進(jìn)程在子進(jìn)程結(jié)束之前退出，則子進(jìn)程由init接管。init將會以父進(jìn)程身份對僵尸狀態(tài)的子進(jìn)程進(jìn)行處理）

但是，如果父進(jìn)程先于子進(jìn)程結(jié)束，則子進(jìn)程成為孤兒進(jìn)程。孤兒進(jìn)程將被 init 進(jìn)程（進(jìn)程號為1）領(lǐng)養(yǎng)，并由 init 進(jìn)程對孤兒進(jìn)程完成狀態(tài)收集工作。

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

Linux系統(tǒng)僵尸進(jìn)程詳解 - 良許Linux - 博客園 (cnblogs.com)

共享內(nèi)存

在某種程度上，多進(jìn)程是共同使用物理內(nèi)存的，但是由于操作系統(tǒng)的進(jìn)程管理，進(jìn)程間的內(nèi)存空間是獨立的，因此進(jìn)程默認(rèn)是不能訪問進(jìn)程空間之外的內(nèi)存空間的。

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

Unix域套接字

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

套接字（socket）：為網(wǎng)絡(luò)通信中使用的術(shù)語。

Unix系統(tǒng)提供的域套接字提供了網(wǎng)絡(luò)套接字類似的功能，如Nfinx、uWSGI等。

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

線程同步

線程同步的方法

互斥鎖

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

自旋鎖

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

常見的例子：分布式鎖設(shè)計

讀寫鎖

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

條件變量

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

線程同步方法的對比

Linux的進(jìn)程管理

進(jìn)程類型

前臺進(jìn)程：具有終端，可以和用戶交互；后臺進(jìn)程：沒有占用終端，基本不和用戶交互，優(yōu)先級比前臺進(jìn)程低（將需要執(zhí)行的命令以“&”符號結(jié)束）；守護(hù)進(jìn)程：特殊的后臺進(jìn)程，在系統(tǒng)引導(dǎo)時啟動，一直運行直到系統(tǒng)關(guān)閉（進(jìn)程名字以“d”結(jié)尾的一般都是守護(hù)進(jìn)程），如crond、sshd、httpd、mysqld…

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

進(jìn)程標(biāo)記

進(jìn)程ID：非負(fù)整數(shù)，進(jìn)程的唯一標(biāo)記，每個進(jìn)程擁有不同的ID；進(jìn)程的狀態(tài)標(biāo)記：R表示進(jìn)程處于運行狀態(tài)，S表示進(jìn)程處于睡眠狀態(tài)…

操作Linux進(jìn)程的相關(guān)命令：

ps命令：列出當(dāng)前的進(jìn)程，結(jié)合-aux可以打印進(jìn)程的詳細(xì)信息（ps -aux）；top命令：查看所有進(jìn)程的狀態(tài)；kill命令：給進(jìn)程發(fā)送信號。

作業(yè)管理(處理機(jī)調(diào)度)

處理機(jī)是什么？

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

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

概念

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

分類

高級調(diào)度（作業(yè)調(diào)度）

按一定的原則從外存上處于后備隊列的作業(yè)中挑選一個（或多個）作業(yè)，給他們分配內(nèi)存等必要資源，并建立相應(yīng)的進(jìn)程(建立PCB),以使它（們）獲得竟?fàn)幪幚頇C(jī)的權(quán)利。

高級調(diào)度是輔存（外存）與內(nèi)存之間的調(diào)度。每個作業(yè)只調(diào)入一次，調(diào)出一次。作業(yè)調(diào)入時會建立相應(yīng)的PCB,作業(yè)調(diào)出時才撤銷PCB。高級調(diào)度主要是指調(diào)入的問題，因為只有調(diào)入的時機(jī)需要操作系統(tǒng)來確定，但調(diào)出的時機(jī)必然是作業(yè)運行結(jié)束才調(diào)出。

中級調(diào)度（內(nèi)存調(diào)度）

為了使內(nèi)存中的內(nèi)存不至于太多，有時需要把某些進(jìn)程從內(nèi)存中調(diào)到外存。在內(nèi)存使用情況緊張時，將一些暫時不能運行的進(jìn)程從內(nèi)存中對換到外存中等待。當(dāng)內(nèi)存有足夠的空閑空間時，再將合適的進(jìn)程重新?lián)Q入內(nèi)存。

低級調(diào)度（進(jìn)程調(diào)度）

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

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

調(diào)度方式

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

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

進(jìn)程調(diào)度的三大機(jī)制

就緒隊列排隊

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

選擇運行進(jìn)程委派

調(diào)度程序以一定的策略，選擇就緒進(jìn)程，將CPU資源分配給它。

新老進(jìn)程上下文切換

存當(dāng)前進(jìn)程的上下文信息，裝入被委派執(zhí)行進(jìn)程的運行上下文

調(diào)度準(zhǔn)則

CPU利用率系統(tǒng)吞吐量

單位時間內(nèi)cpu完成作業(yè)的數(shù)目

周轉(zhuǎn)時間

作業(yè)的完成時間-提交時間

等待時間

進(jìn)程與等待處理機(jī)的時間之和

響應(yīng)時間

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

算法

先來先服務(wù)（FCFS）：

算法原理：按照作業(yè)（進(jìn)程）到達(dá)的先后次序來進(jìn)行調(diào)度，誰先來，誰就先被調(diào)度。缺點：忽略了作業(yè)的運行時間

短作業(yè)優(yōu)先（SJF)：

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

例題：

解：“作業(yè)被調(diào)度進(jìn)入運行后不再退出"意為非搶占式調(diào)用，job2到來時也得等待job1執(zhí)行完

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

標(biāo)準(zhǔn)流程如圖（要寫出作業(yè)號、提交時間、運行時間、開始時刻、完成時刻、周轉(zhuǎn)時間）：

②周轉(zhuǎn)時間=完成時間-提交時間

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

(n為作業(yè)過程總數(shù)，N1、N2為周轉(zhuǎn)時間）

優(yōu)先級調(diào)度算法：

算法原理：FCFS、SJF兩種算法都不能反映進(jìn)程的緊迫程度。而優(yōu)先級調(diào)度算法是外部賦予進(jìn)程相應(yīng)的優(yōu)先級，來體現(xiàn)出進(jìn)程的緊迫程度，緊迫性進(jìn)程優(yōu)先運行

（如何確定優(yōu)先級：

1、利用某一范圍內(nèi)的一個整數(shù)，優(yōu)先數(shù)

2、響應(yīng)比的大小，誰響應(yīng)比大，誰優(yōu)先級就大——高響應(yīng)比優(yōu)先調(diào)度算法）

高響應(yīng)比優(yōu)先調(diào)度算法

響應(yīng)比=作業(yè)周轉(zhuǎn)時間/作業(yè)處理時間=（作業(yè)處理時間+作業(yè)等待時間）/作業(yè)處理時間=1+（作業(yè)等待時間/作業(yè)處理時間）

時間片輪轉(zhuǎn)

適合系統(tǒng)：分時系統(tǒng)

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

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

多級反饋隊列調(diào)度算法

算法原理（調(diào)度機(jī)制）：

設(shè)置多個就緒隊列，每個隊列賦予不同的優(yōu)先級，第一個隊列優(yōu)先級最高，并且首先調(diào)度最高優(yōu)先級，也就是第一個隊列里面的所有進(jìn)程，僅當(dāng)?shù)谝粋€隊列空閑時，才開始調(diào)度第二個隊列中的進(jìn)程運行。優(yōu)先級越高的隊列，時間片越小。

總結(jié)

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

死鎖

進(jìn)程死鎖、饑餓、死循環(huán)的區(qū)別

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

死鎖的產(chǎn)生

競爭資源（共享資源數(shù)量不滿足各進(jìn)程需求）、進(jìn)程調(diào)度順序不當(dāng)，當(dāng)調(diào)度順序為A->B->C->D時會產(chǎn)生死鎖，但改為A->D->B->C則不會產(chǎn)生。

死鎖的必要條件

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

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

死鎖的處理策略

預(yù)防死鎖的方法

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

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

第一種方法靜態(tài)分配即每個進(jìn)程在開始執(zhí)行時就申請他所需要的全部資源。第二種是動態(tài)分配即每個進(jìn)程在申請所需要的資源時他本身不占用系統(tǒng)資源。

破壞不可剝奪條件：當(dāng)一個進(jìn)程請求新的資源得不到滿足時，必須釋放占有的資源；（實現(xiàn)復(fù)雜，剝奪資源可能導(dǎo)致部分工作失效，反復(fù)申請和釋放造成額外的系統(tǒng)開銷）

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

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

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

銀行家算法

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

(85條消息) 銀行家算法詳解（C語言）Sparky*的博客-CSDN博客銀行家算法數(shù)據(jù)結(jié)構(gòu)

死鎖的檢測和解除

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

存儲管理

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

內(nèi)存分配的過程

單一連續(xù)分配（已經(jīng)過時）固定分區(qū)分配動態(tài)分區(qū)分配（根據(jù)實際需要，動態(tài)的分配內(nèi)存）

動態(tài)分配算法

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

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

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

內(nèi)存回收的過程

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

分區(qū)存儲管理

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

這一部分是內(nèi)存分配過程的詳細(xì)介紹，可以簡單看一下

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

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

主存空間的分配與釋放

了管理主存空間的使用，必須設(shè)置一張“主存分配表”（分區(qū)說明表），以說明各分區(qū)的分配情況。主存分配表中應(yīng)指出各分區(qū)的起始地址和長度，并為每個分區(qū)設(shè)一個標(biāo)志位。當(dāng)標(biāo)志位為“0”時，表示對應(yīng)的分區(qū)是空閑分區(qū)，當(dāng)標(biāo)志位為非“0”時，表示對應(yīng)的分區(qū)已被某作業(yè)占用?？臻e分區(qū)可以用來裝作業(yè)。

當(dāng)作業(yè)隊列中有作業(yè)要裝入主存時，存儲管理可采用“順序分配算法”進(jìn)行主存空間的分配。

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

主存空間的釋放很簡單。某作業(yè)執(zhí)行結(jié)束后必須歸還所占的分區(qū)，這時存儲管理根據(jù)作業(yè)名查看主存分配表，找到相應(yīng)的表目后，把其中的標(biāo)志位重新置成“0”即可。

地址轉(zhuǎn)換

固定分區(qū)管理方式下作業(yè)的地址轉(zhuǎn)換常采用靜態(tài)重定位技術(shù)。

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

存儲保護(hù)

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

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

Then   繼續(xù)

復(fù)制

Else 產(chǎn)生“越界中斷” ，轉(zhuǎn)越界中斷的處理子程序

內(nèi)存擴(kuò)充

采用覆蓋技術(shù)

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

固定分區(qū)的優(yōu)缺點

優(yōu)點：實現(xiàn)簡單，無外部碎片

缺點：

當(dāng)用戶程序太大時，可能所有的分區(qū)都不能滿足需求，此時不得不采用覆蓋技術(shù)解決，但這又會降低性能會產(chǎn)生內(nèi)部碎片，碎片大，存在小分區(qū)占用大作業(yè)的情況，內(nèi)存利用率低。

解決辦法：采用可變分區(qū)存儲管理

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

內(nèi)存管理的可變分區(qū)模式，又稱變長分區(qū)模式、動態(tài)分區(qū)分配模式。這種分配方式不會預(yù)先劃分內(nèi)存分區(qū)，而是在進(jìn)程裝入內(nèi)存時，根據(jù)進(jìn)程的大小動態(tài)地建立分區(qū)，并使分區(qū)的大小正好適合進(jìn)程的需要。因此系統(tǒng)分區(qū)的大小和數(shù)目是可變的。

與固定分區(qū)的區(qū)別就是：動態(tài)的劃分分區(qū)。

克服固定分區(qū)管理的“內(nèi)碎片”問題。

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

可變分區(qū)分配的數(shù)據(jù)結(jié)構(gòu)

可變分區(qū)分配算法

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

在可變分區(qū)分配方式中，當(dāng)有很多空閑分區(qū)都滿足需求時，應(yīng)該使用哪個分區(qū)進(jìn)行分配?

這里介紹三種可變分區(qū)分配算法

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

實現(xiàn)步驟：

空閑區(qū)地址由低到高排序

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

=>2.調(diào)整相應(yīng)的空閑分區(qū)表和已分配分區(qū)表。

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

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

最佳適應(yīng)算法

算法思想：由于可變分區(qū)分配是一種連續(xù)分配方式，為各進(jìn)程分配的空間必須是連續(xù)的一整片區(qū)域。因此為了保證當(dāng)“大進(jìn)程”到來時能有連續(xù)的大片空間，優(yōu)先使用更小的空閑區(qū)。

實現(xiàn)步驟：

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

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

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

最壞適應(yīng)算法

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

實現(xiàn)步驟：

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

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

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

三種算法的比較：

可變分區(qū)內(nèi)存回收

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

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

實現(xiàn)回收內(nèi)存空間，關(guān)鍵是修改空閑分區(qū)表和已分配分區(qū)表。

回收內(nèi)存分區(qū)時可能會遇到的四種情況：

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

先將R與F2合并記為F2,

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

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

THEN 修改空閑表，分配表。

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

則只修改空閑區(qū)F1大小即可。

IF (D+H2=E)

THEN 修改空閑表，分配表。

(c)只有下鄰空閑區(qū)

修改空閑區(qū)F2的首地址。

F2的大?。紽2的大?。玆的大小

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

Else 修改釋放區(qū)的首地址為空閑區(qū)的起始地址

地址轉(zhuǎn)換

動態(tài)重定位

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

分區(qū)的存儲保護(hù)

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

Then 繼續(xù)

Else 產(chǎn)生“越界中斷” ，轉(zhuǎn)越界中斷的處理子程序

內(nèi)存擴(kuò)充

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

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

經(jīng)過緊縮后的進(jìn)程在內(nèi)存中的位置發(fā)生了變化，若不對程序和數(shù)據(jù)的地址進(jìn)行修改，在進(jìn)程就無法運行。

要使其運行，必須進(jìn)行“動態(tài)重定位”

注意：

＝》緊縮的時機(jī)：

（1）一旦有歸還的分區(qū)便進(jìn)行緊縮，系統(tǒng)開銷大。

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

頁式存儲管理

分頁存儲管理的思想：把內(nèi)存分為一個個相等的小分區(qū)，再按照分區(qū)大小把進(jìn)程拆分成一個個小部分。分頁存儲管理分為：實分頁存儲管理和虛分頁存儲管理

實分頁式存儲管理

實分頁式存儲最大的優(yōu)點是內(nèi)存利用率高，與目前流行的虛分頁存儲管理相比，具有實現(xiàn)簡單，程序運行快的優(yōu)點。

基本原理

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

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

這里的塊相當(dāng)于飯店的客房，系統(tǒng)對內(nèi)存分塊相當(dāng)于飯店把大樓所有的客房都設(shè)計成標(biāo)準(zhǔn)的雙人間。

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

這里，對作業(yè)地址空間分頁就相當(dāng)于把旅游團(tuán)成員分成兩人一組。

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

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

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

對塊尺寸這樣規(guī)定相當(dāng)于飯店規(guī)定客房是雙人間?？梢栽O(shè)想一下，如果上例中飯店所有的客房都是十人間的話，效益肯定不如全是雙人間的好

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

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

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

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

頁表

頁面的劃分完全是一種系統(tǒng)硬件的行為，一個邏輯地址放到這種地址結(jié)構(gòu)中，自然就分成了頁號和頁內(nèi)單元號兩部分。

頁面大小為：4KB

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

所以，系統(tǒng)為每個進(jìn)程建立一張頁面映射表，簡稱頁表。

地址映射

在系統(tǒng)中設(shè)置地址變換機(jī)構(gòu)，能將用戶進(jìn)程地址空間中的邏輯地址變?yōu)閮?nèi)存空間中的物理地址。

由于頁面和物理塊的大小相等，頁內(nèi)偏移地址和塊內(nèi)偏移地址是相同的。無須進(jìn)行從頁內(nèi)地址到塊內(nèi)地址的轉(zhuǎn)換。

地址變換機(jī)構(gòu)的任務(wù)，關(guān)鍵是將邏輯地址中的頁號轉(zhuǎn)換為內(nèi)存中的物理塊號。物理塊號內(nèi)的偏移地址就是頁內(nèi)偏移地址。

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

如果題目中是用十進(jìn)制數(shù)表示邏輯地址，則：

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

虛地址 3412

P＝3412 ％ 2048＝1

W＝3412 mod 2048＝1364

MA=9*2048+1364=19796

虛地址3412的內(nèi)存地址是19796

虛地址 7145

P＝7145 ％ 2048 ＝3

W＝7145 mod 2048 ＝1001

MA=5*2048+1001=11241

虛地址7145的內(nèi)存地址是：11241

快表

因為頁表是存放在內(nèi)存中的，CPU要存取一個數(shù)據(jù)，需訪問主存兩次。

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

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

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

為了提高存取速度，在地址變換機(jī)構(gòu)中增設(shè)一組寄存器，用來存放訪問的那些頁表。

快表是一種訪存速度比內(nèi)存快很多的高速緩沖器。

把存放在高速緩沖寄存器中的頁表叫快表，這個高速緩沖寄存器又叫聯(lián)想存貯器（TLB）。與此對應(yīng)，內(nèi)存中的頁表稱為慢表。

當(dāng)進(jìn)程訪問一頁時，系統(tǒng)將頁號與快表中的所有項進(jìn)行并行比較。若訪問的頁在快表中，即可立即進(jìn)行地址轉(zhuǎn)換。

當(dāng)被訪問的頁不在快表中時，去內(nèi)存中查詢頁表，同時將頁表找到的內(nèi)存塊號與虛頁號填入快表中

例題2：

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

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

若快表命中

聯(lián)想寄存器檢索時間：10ns

訪問內(nèi)存1次取數(shù)據(jù)時間：100ns

取數(shù)據(jù)總時間：110ns

若快表中未命中

聯(lián)想寄存器檢索時間：10ns

訪問內(nèi)存1次檢索頁表時間：100ns

訪問內(nèi)存1次取數(shù)據(jù)時間：100ns

取數(shù)據(jù)總時間：210ns

兩級和多級頁表

現(xiàn)代的大多數(shù)計算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。頁表就變得非常大，要占用相當(dāng)大的內(nèi)存空間?？刹捎脙蓚€方法來解決這一問題：

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

② 只將當(dāng)前需要的部分頁表項調(diào)入內(nèi)存，其余的頁表項仍駐留在磁盤上，需要時再調(diào)入。

二級頁表如何實現(xiàn)地址變換？

頁的分配與回收

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

位示圖優(yōu)點是占用內(nèi)存空間小，可常駐內(nèi)存，加快分配進(jìn)程，但缺點是不夠直觀。

內(nèi)存分配過程：

計算一個作業(yè)所需要的總塊數(shù)N

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

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

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

修改位示圖

存在的問題

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

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

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

IBM RT; HP Spectrum…

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

所有在內(nèi)存中的并發(fā)進(jìn)程只有一張頁表

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

分頁存儲管理方案的評價

優(yōu)點：

較好地解決了碎片問題

打破了存儲分配的連續(xù)性要求

提高了主存的利用率

缺點：

頁內(nèi)碎片

動態(tài)地址變換、方案實施需耗用額外的系統(tǒng)資源

存儲擴(kuò)充問題沒有解決——作業(yè)大小受到限制，可用塊數(shù)小于作業(yè)需求時需等待

虛擬頁式存儲

虛擬存儲器

局部性原理(principle of locality)

指程序在執(zhí)行過程中的一個較短時期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。還可以表現(xiàn)為：

時間局部性：一條指令的一次執(zhí)行和下次執(zhí)行，一個數(shù)據(jù)的一次訪問和下次訪問都集中在一個較短時期內(nèi)；空間局部性：當(dāng)前指令和鄰近的幾條指令，當(dāng)前訪問的數(shù)據(jù)和鄰近的數(shù)據(jù)都集中在一個較小區(qū)域內(nèi)。

局部性原理的具體體現(xiàn)：

程序在執(zhí)行時，大部分是順序執(zhí)行的指令，少部分是轉(zhuǎn)移和過程調(diào)用指令。過程調(diào)用的嵌套深度一般不超過5，因此執(zhí)行的范圍不超過這組嵌套的過程。程序中存在相當(dāng)多的循環(huán)結(jié)構(gòu)，它們由少量指令組成，而被多次執(zhí)行。程序中存在相當(dāng)多對一定數(shù)據(jù)結(jié)構(gòu)的操作，如數(shù)組操作，往往局限在較小范圍內(nèi)。

引入虛擬存儲技術(shù)的好處

大程序：可在較小的可用內(nèi)存中執(zhí)行較大的用戶程序；

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

并發(fā)：可在內(nèi)存中容納更多程序并發(fā)執(zhí)行；

易于開發(fā)：與覆蓋技術(shù)比較，不必影響編程時的程序結(jié)構(gòu)

虛擬存儲技術(shù)的特征

不連續(xù)性：物理內(nèi)存分配的不連續(xù)，虛擬地址空間使用的不連續(xù)（數(shù)據(jù)段和棧段之間的空閑空間，共享段和動態(tài)鏈接庫占用的空間）

部分交換：與交換技術(shù)相比較，虛擬存儲的調(diào)入和調(diào)出是對部分虛擬地址空間進(jìn)行的；

大空間：通過物理內(nèi)存和快速外存相結(jié)合，提供大范圍的虛擬地址空間

虛擬存儲技術(shù)的種類

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

虛擬頁式存儲管理

基本原理

系統(tǒng)自動地將作業(yè)的地址空間分頁，將系統(tǒng)的主存空間分塊，頁與塊等大小，在作業(yè)運行前，只把初始需要的一部分頁面裝入內(nèi)存塊里，運行中需要訪問自己地址空間中的但當(dāng)前不在內(nèi)存的頁面時產(chǎn)生缺頁中斷，由缺頁中斷服務(wù)程序?qū)⑺璧捻撁嬲{(diào)入內(nèi)存，若此時內(nèi)存中沒有空閑物理塊安置請求調(diào)入的新頁面，則系統(tǒng)按預(yù)定的置換策略自動選擇一個或一些在內(nèi)存的頁面，把它們換出到外存。

虛擬頁式存儲管理實際是實分頁技術(shù)與虛擬存儲技術(shù)相結(jié)合的產(chǎn)物，其分頁思想與實分頁是一樣的。

這里的請求調(diào)入和置換功能都是比實分頁存儲管理增加的內(nèi)容，是實現(xiàn)虛擬存儲的主要功能。

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

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

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

作業(yè)1在請求分頁系統(tǒng)中的存儲映像

當(dāng)執(zhí)行 “mov r1，[2120］”時

CPU產(chǎn)生的虛地址為2120

分頁機(jī)構(gòu)得 p=2，w=72（每頁1K）

查頁表。該頁中斷位i=1，發(fā)生缺頁中斷

如主存中有空白塊，直接調(diào)入

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

主存頁面分配策略

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

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

頁面調(diào)入策略

（1）請求調(diào)入

當(dāng)發(fā)生頁面故障時進(jìn)行調(diào)度，即當(dāng)進(jìn)程訪問不在內(nèi)存的頁面引發(fā)缺頁中斷時，由系統(tǒng)根據(jù)這種訪問請求把所缺頁面裝入內(nèi)存。

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

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

（ 2）預(yù)調(diào)入

=>也稱先行調(diào)度，即一頁面被訪問前就已經(jīng)預(yù)先置入內(nèi)存，以減少今后的缺頁率。

=>主要適于進(jìn)程的許多頁存放在外存的連續(xù)區(qū)域中的情況。有的系統(tǒng)結(jié)合請求調(diào)入使用，即每次缺頁時裝入多個頁面。

優(yōu)點：提高調(diào)頁的I/O效率。

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

調(diào)入頁面的來源：

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

進(jìn)程裝入時，將其全部頁面復(fù)制到交換區(qū)，以后總是從交換區(qū)調(diào)入。執(zhí)行時調(diào)入速度快，要求交換區(qū)空間較大。

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

存儲分配的安全性考慮:

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

頁面調(diào)度算法

由缺頁中斷服務(wù)程序?qū)⑺璧捻撁嬲{(diào)入內(nèi)存，若此時內(nèi)存中沒有空閑物理塊安置請求調(diào)入的新頁面，則系統(tǒng)按預(yù)定的策略自動選擇一個（請求調(diào)入策略）或一些（預(yù)調(diào)入策略）在內(nèi)存的頁面，把它們換出到外存。

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

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

b、顛簸

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

簡單地說，導(dǎo)致系統(tǒng)效率急劇下降的主存和輔存之間的頻繁頁面置換現(xiàn)像稱為“抖動”。

現(xiàn)象？淘汰的頁面恰好是不久又要訪問的頁面。

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

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

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

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

假定系統(tǒng)為某個進(jìn)程分配了三個物理塊，進(jìn)程的訪問順序為7，0，1，2，0，3，0，4，2，3，0，3，2，1，2

采用OPT淘汰算法：

這是最早出現(xiàn)的淘汰算法。

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

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

頁面進(jìn)入主存的先后次序：

2->4->5->1

當(dāng)要調(diào)入第6頁時：

置換第2頁

將第2頁改為6

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

Belady現(xiàn)象：采用FIFO算法時，如果對一個進(jìn)程未分配它所要求的全部頁面，有時就會出現(xiàn)分配的頁面數(shù)增多，缺頁率反而提高的異?，F(xiàn)象。

Belady現(xiàn)象的描述：一個進(jìn)程P要訪問M個頁，OS分配N個內(nèi)存頁面給進(jìn)程P；對一個訪問序列S，發(fā)生缺頁次數(shù)為PE（S,N）。當(dāng)N增大時，PE(S, N)時而增大，時而減小。

Belady現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動態(tài)特征是非常不一致的，即被置換的頁面通常并不是進(jìn)程不會訪問的。

采用FIFO淘汰算法：

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

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

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

下面給出LRU的實現(xiàn)算法：

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

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

c、多位寄存器法

為每頁設(shè)置一個R位的寄存器

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

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

選擇R值最小的頁淘汰。

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

頁面 時刻

T1      T2      T3    

復(fù)制

P0 1000 0100 1010

P1 1000 1100 0110

P2 0000 1000 0100

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

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

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

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

該算法首先檢查位于FIFO鏈鏈?zhǔn)椎捻摚绻脑L問位為0，則選擇該頁淘汰；如果它的訪問位為1，則清除其訪問位，將它移至FIFO鏈的鏈尾，重復(fù)此算法的查找過程，直至遇到新鏈?zhǔn)醉撌且粋€訪問位為0的較早進(jìn)入內(nèi)存的頁為止，把它選為被淘汰的頁。

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

當(dāng)訪問某頁時，就將該頁引用位置1

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

在T內(nèi)，被訪問過的頁面引用位為1，否則為0

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

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

二次機(jī)會淘汰算法缺點：就是需要把訪問位為1的處于鏈?zhǔn)椎捻撘浦伶溛?，這需要一定的開銷。

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

該算法首先檢測指針?biāo)傅捻撁?，如果它的訪問位為0，則淘汰該頁，新裝入的頁插入到此位置，然后指針前進(jìn)一個位置；如果它的訪問位為1，則清除為0，并將指針前進(jìn)一個位置，繼續(xù)檢查訪問位。重復(fù)此過程，直到找到訪問位為0的頁面為止。

訪問頁號727

引發(fā)缺頁

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

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

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

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

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

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

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

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

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

內(nèi)存分配3塊

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

時鐘clock算法中的箭頭是當(dāng)前指針的位置！

影響缺頁中斷率的因素

（1）頁面調(diào)度算法不合理

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

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

（2）分配給作業(yè)的內(nèi)存塊數(shù)太少

作業(yè)的缺頁中斷率與作業(yè)所占內(nèi)存塊數(shù)成反比。分配給作業(yè)的內(nèi)存塊數(shù)太少是導(dǎo)致抖動現(xiàn)象發(fā)生的最主要的原因，實驗分析表明：對所有的程序來說，要使其有效地工作，它在內(nèi)存中的頁面數(shù)不應(yīng)少于它的總頁面數(shù)的一半。

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

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

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

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

段式存儲管理

分段

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

分段系統(tǒng)的邏輯地址結(jié)構(gòu)由段號（段名）和段內(nèi)地址（段內(nèi)偏移量）所組成。

段表

每一個程序設(shè)置一個段表，放在內(nèi)存,屬于進(jìn)程的現(xiàn)場信息

地址變換

段的保護(hù)

越界中斷處理

進(jìn)程在執(zhí)行過程中，有時需要擴(kuò)大分段，如數(shù)據(jù)段。由于要訪問的地址超出原有的段長，所以發(fā)越界中斷。操作系統(tǒng)處理中斷時 ，首先判斷該段的“擴(kuò)充位”，如可擴(kuò)充，則增加段的長度；否則按出錯處理

缺段中斷處理

檢查內(nèi)存中是否有足夠的空閑空間

復(fù)制①若有，則裝入該段，修改有關(guān)數(shù)據(jù)結(jié)構(gòu)，中斷返回②若沒有，檢查內(nèi)存中空閑區(qū)的總和是否滿足要求，是則應(yīng)采用緊縮技術(shù)，轉(zhuǎn) ① ；否則，淘汰一（些）段，轉(zhuǎn)①

段的動態(tài)連接

為何要進(jìn)行段的動態(tài)鏈接？

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

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

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

信息的保護(hù)與共享

這里主要與頁式存儲管理進(jìn)行一下對比。

分段比分頁更容易實現(xiàn)信息的共享和保護(hù)。

只讀代碼共享

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

頁式系統(tǒng)與段式系統(tǒng)的對比

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

分段存儲：段內(nèi)地址W字段溢出將產(chǎn)生越界中斷。

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

總結(jié)

段頁式存儲管理

分頁、分段的有缺點分析

基本思想

用戶程序劃分：按段式劃分（對用戶來講，按段的邏輯關(guān)系進(jìn)行劃分；對系統(tǒng)講，按頁劃分每一段）

邏輯地址：

內(nèi)存劃分：按頁式存儲管理方案內(nèi)存分配：以頁為單位進(jìn)行分配

邏輯地址結(jié)構(gòu)

段表頁表

地址轉(zhuǎn)換

評價

優(yōu)點：

保留了分段和請求分頁存儲管理的全部優(yōu)點

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

缺點：

增加了硬件成本

系統(tǒng)復(fù)雜度較大

總結(jié)

虛擬內(nèi)存

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

虛擬內(nèi)存概述：是操作系統(tǒng)內(nèi)存管理的關(guān)鍵技術(shù)，使得多道程序運行和大程序運行成為現(xiàn)實，把程序使用內(nèi)存劃分，將部分暫時不使用的內(nèi)存放置在輔存，實際是對物理內(nèi)存的擴(kuò)充。

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

虛擬內(nèi)存的特征：

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

Linux的存儲管理

Buddy內(nèi)存管理算法：經(jīng)典的內(nèi)存管理算法，為解決內(nèi)存外碎片的問題，算法基于計算機(jī)處理二進(jìn)制的優(yōu)勢具有極高的效率。

Linux交換空間：交換空間（Swap）是磁盤的一個分區(qū)，Linux內(nèi)存滿時，會把一些內(nèi)存交換至Swap空間，Swap空間是初始化系統(tǒng)時配置的。

Swap空間與虛擬內(nèi)存的對比：

文件管理

文件的邏輯結(jié)構(gòu)：

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

輔存的存儲空間分配：

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

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

設(shè)備管理

基本概念：將數(shù)據(jù)輸入輸出計算機(jī)的外部設(shè)備；

廣義的IO設(shè)備：

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

SPOOLing技術(shù)：虛擬設(shè)備技術(shù)，把同步調(diào)用低速設(shè)備改為異步調(diào)用，在輸入、輸出之間增加了排隊轉(zhuǎn)儲環(huán)節(jié)(輸入井、輸出井)，SPoOLing負(fù)責(zé)輸入（出）井與低速設(shè)備之間的調(diào)度，邏輯上，進(jìn)程直接與高速設(shè)備交互，減少了進(jìn)程的等待時間。

實現(xiàn)支持異步任務(wù)的線程池

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

使用線程池的原因：

線程是稀缺資源 ，不應(yīng)該頻繁創(chuàng)建和銷毀；架構(gòu)解耦，業(yè)務(wù)創(chuàng)建和業(yè)務(wù)處理解耦，更加優(yōu)雅；線程池是使用線程的最佳實踐。

實現(xiàn)線程安全的隊列Queue

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

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

本文有對以下文章進(jìn)行參考：

計算機(jī)操作系統(tǒng)知識點總結(jié)（有這一篇就夠了！?。。?em style="font-style:italic">原來如此呀的博客-CSDN博客操作系統(tǒng)

操作系統(tǒng)常見面試題總結(jié) | JavaGuide(Java面試+學(xué)習(xí)指南)

【操作系統(tǒng)】生產(chǎn)者消費者問題niliushall.的博客-CSDN博客生產(chǎn)者消費者問題

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

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

首次適應(yīng)算法和最佳適應(yīng)算法莫顧爾在的博客-CSDN博客首次適應(yīng)

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

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

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

操作系統(tǒng) 三小時速成課 課時2 進(jìn)程調(diào)度_嗶哩嗶哩_bilibili

編輯：qysb005