概述

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

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

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

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

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

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

(相關(guān)資料圖)

基本功能

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

特征

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

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

中斷處理

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

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

1.概念

2.特點(diǎn)

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

3.CPU的利用情況

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

4.缺點(diǎn)

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

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

1.概念

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

2.特點(diǎn)

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

3.CPU的利用情況

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

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

4.缺點(diǎn)

作業(yè)處理時(shí)間長(zhǎng)交互能力差運(yùn)行過(guò)程不確定

其他

中斷產(chǎn)生：

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

中斷的分類：

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

外中斷的處理過(guò)程：

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

其他概念

指令

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

程序

內(nèi)核程序:系統(tǒng)的管理者，可執(zhí)行—切指令、運(yùn)行在核心態(tài)應(yīng)用程序:普通用戶程序只能執(zhí)行非特權(quán)指令，運(yù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):通過(guò)中斷（是硬件完成的)核心態(tài)到用戶態(tài):特權(quán)指令psw的標(biāo)志位 0用戶態(tài) 1核心態(tài)

原語(yǔ)

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

中斷和異常

內(nèi)中斷(異常，信號(hào)來(lái)自內(nèi)部)自愿中斷指令中斷強(qiáng)迫中斷硬件中斷軟件中斷外中斷（中斷，信號(hào)來(lái)著外部)外設(shè)請(qǐng)求人工干預(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)程實(shí)體

引入進(jìn)程目的

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

進(jìn)程的定義

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

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

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

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

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

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

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

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

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

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

創(chuàng)建狀態(tài)：創(chuàng)建進(jìn)程時(shí)擁有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)程以隊(duì)列的形式放置。終止?fàn)顟B(tài)：進(jìn)程結(jié)束由系統(tǒng)清理或者歸還PCB的狀態(tài)。

經(jīng)典問(wèn)題

生產(chǎn)者-消費(fèi)者問(wèn)題

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

(感覺(jué)有點(diǎn)微服務(wù)的意思了)

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

問(wèn)題解決

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

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

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

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

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

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

問(wèn)題解決

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

當(dāng)某一個(gè)哲學(xué)家能夠同時(shí)拿起左右兩只叉子時(shí)，才讓他拿，這樣就能夠保證不會(huì)因?yàn)槊總€(gè)科學(xué)家都只拿了一只叉子而導(dǎo)致死鎖。

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

class DiningPhilosophers {public:    DiningPhilosophers()     {}    void wantsToEat(int philosopher,                    function pickLeftFork,                    function pickRightFork,                    function eat,                    function putLeftFork,                    function putRightFork)     {        //對(duì)拿叉子進(jìn)行這一流程進(jìn)行加鎖，保證其能同時(shí)拿起一雙，而不會(huì)被其他人搶走        _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ù)量(或者說(shuō)，多加一支筷子)

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

我們需要用到一個(gè)計(jì)數(shù)器來(lái)表示當(dāng)前就餐的人數(shù)，為了保證線程安全我們需要用到一個(gè)互斥鎖和一個(gè)條件變量對(duì)其進(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ù)不超過(guò)四人的時(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();//就餐完成，讓下一個(gè)人進(jìn)來(lái)就餐    }private:    mutex _fork[5];    mutex _mtx;    condition_variable _cond;    int _count;};

復(fù)制

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

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

此時(shí)2號(hào)和3號(hào)哲學(xué)家爭(zhēng)搶3號(hào)叉子，4號(hào)和5號(hào)哲學(xué)家爭(zhēng)搶5號(hào)叉子，1號(hào)沒(méi)有競(jìng)爭(zhēng)對(duì)手，直接獲取叉子1。

可以看到，在第一輪中所有哲學(xué)家先去爭(zhēng)搶奇數(shù)叉子，搶到偶數(shù)叉子后再去爭(zhēng)搶偶數(shù)叉子，這樣就能夠保證至少有一個(gè)科學(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): 匿名管道由于沒(méi)有名字，只能用于親緣關(guān)系的進(jìn)程間通信。為了克服這個(gè)缺點(diǎn)，提出了有名管道。有名管道嚴(yán)格遵循先進(jìn)先出(first in first out)。有名管道以磁盤(pán)文件的方式存在，可以實(shí)現(xiàn)本機(jī)任意兩個(gè)進(jìn)程通信。

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

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

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

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

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

進(jìn)程同步

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

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

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

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

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

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

使用fork系統(tǒng)調(diào)用無(wú)參數(shù)，fork會(huì)返回兩次，分別返回子進(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)會(huì)為fork的進(jìn)程分配新的資源

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

孤兒進(jìn)程

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

IDEA啟動(dòng)SpringBoot項(xiàng)目，關(guān)掉IDEA后，SpringBoot（未終止沒(méi)有斷開(kāi)連接），仍在后臺(tái)

僵尸進(jìn)程

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

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

而如果子進(jìn)程先于父進(jìn)程退出，同時(shí)父進(jìn)程太忙了，無(wú)瑕回收子進(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)存空間是獨(dú)立的，因此進(jìn)程默認(rèn)是不能訪問(wèn)進(jìn)程空間之外的內(nèi)存空間的。

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

Unix域套接字

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

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

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

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

線程同步

線程同步的方法

互斥鎖

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

自旋鎖

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

常見(jiàn)的例子：分布式鎖設(shè)計(jì)

讀寫(xiě)鎖

是一種特殊的自旋鎖，允許多個(gè)讀操作同時(shí)訪問(wèn)資源以提高讀性能，但是對(duì)寫(xiě)操作是互斥的，即對(duì)多讀少寫(xiě)的操作效率提升很顯著。

條件變量

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

線程同步方法的對(duì)比

Linux的進(jìn)程管理

進(jìn)程類型

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

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

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

進(jìn)程ID：非負(fù)整數(shù)，進(jìn)程的唯一標(biāo)記，每個(gè)進(jìn)程擁有不同的ID；進(jìn)程的狀態(tài)標(biāo)記：R表示進(jìn)程處于運(yù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ā)送信號(hào)。

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

處理機(jī)是什么？

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

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

概念

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

分類

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

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

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

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

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

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

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

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

調(diào)度方式

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

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

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

就緒隊(duì)列排隊(duì)

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

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

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

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

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

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

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

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

周轉(zhuǎn)時(shí)間

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

等待時(shí)間

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

響應(yīng)時(shí)間

從提交到第一次開(kāi)始運(yùn)行的時(shí)間

算法

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

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

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

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

例題：

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

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

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

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

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

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

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

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

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

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

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

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

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

時(shí)間片輪轉(zhuǎn)

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

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

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

多級(jí)反饋隊(duì)列調(diào)度算法

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

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

總結(jié)

先來(lái)先服務(wù)算法：按照在就緒隊(duì)列中的先后順序執(zhí)行。短進(jìn)程優(yōu)先調(diào)度算法：優(yōu)先選擇就緒隊(duì)列中估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，不利于長(zhǎng)作業(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)先處理。時(shí)間片輪轉(zhuǎn)調(diào)度算法：按照FIFO的原則排列就緒進(jìn)程，每次從隊(duì)列頭部取出待執(zhí)行進(jìn)程，分配一個(gè)時(shí)間片執(zhí)行，是相對(duì)公平的調(diào)度算法，但是不能保證就是響應(yīng)用戶。

死鎖

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

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

死鎖的產(chǎn)生

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

死鎖的必要條件

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

以上給出了導(dǎo)致死鎖的四個(gè)必要條件，只要系統(tǒng)發(fā)生死鎖則以上四個(gè)條件至少有一個(gè)成立。事實(shí)上循環(huán)等待的成立蘊(yùn)含了前三個(gè)條件的成立，似乎沒(méi)有必要列出然而考慮這些條件對(duì)死鎖的預(yù)防是有利的，因?yàn)榭梢酝ㄟ^(guò)破壞四個(gè)條件中的任何一個(gè)來(lái)預(yù)防死鎖的發(fā)生。

死鎖的處理策略

預(yù)防死鎖的方法

破壞四個(gè)必要條件的中一個(gè)或多個(gè)。

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

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

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

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

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

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

銀行家算法

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

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

死鎖的檢測(cè)和解除

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

存儲(chǔ)管理

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

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

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

動(dòng)態(tài)分配算法

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

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

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

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

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

分區(qū)存儲(chǔ)管理

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

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

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

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

主存空間的分配與釋放

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

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

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

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

地址轉(zhuǎn)換

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

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

存儲(chǔ)保護(hù)

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

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

Then   繼續(xù)

復(fù)制

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

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

采用覆蓋技術(shù)

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

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

優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，無(wú)外部碎片

缺點(diǎn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

實(shí)現(xiàn)步驟：

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

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

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

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

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

最佳適應(yīng)算法

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

實(shí)現(xiàn)步驟：

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

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

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

最壞適應(yīng)算法

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

實(shí)現(xiàn)步驟：

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

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

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

三種算法的比較：

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

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

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

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

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

(a)若釋放區(qū)R既有上鄰空閑區(qū)，又有下鄰空閑區(qū)。將三個(gè)空閑區(qū)合并成一個(gè)大空閑區(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的大小＝F2的大?。玆的大小

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

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

地址轉(zhuǎn)換

動(dòng)態(tài)重定位

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

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

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

Then 繼續(xù)

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

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

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

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

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

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

注意：

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

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

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

頁(yè)式存儲(chǔ)管理

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

實(shí)分頁(yè)式存儲(chǔ)管理

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

基本原理

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

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

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

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

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

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

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

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

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

實(shí)模式下分頁(yè)存儲(chǔ)管理的基本原理：

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

這實(shí)際是個(gè)把作業(yè)從地址空間映射到存儲(chǔ)空間的過(guò)程

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

頁(yè)表

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

頁(yè)面大小為：4KB

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

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

地址映射

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

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

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

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

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

例題1：有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁(yè)大小為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

快表

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

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

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

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

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

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

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

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

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

例題2：

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

平均訪問(wèn)時(shí)間=98%(10+100)+（1-98%）（10+100+100）

若快表命中

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

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

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

若快表中未命中

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

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

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

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

兩級(jí)和多級(jí)頁(yè)表

現(xiàn)代的大多數(shù)計(jì)算機(jī)系統(tǒng)，都支持非常大的邏輯地址空間(232~264)。頁(yè)表就變得非常大，要占用相當(dāng)大的內(nèi)存空間。可采用兩個(gè)方法來(lái)解決這一問(wèn)題：

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

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

二級(jí)頁(yè)表如何實(shí)現(xiàn)地址變換？

頁(yè)的分配與回收

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

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

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

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

查位示圖，看看是否還有N個(gè)空閑塊

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

依次分配N(xiāo)個(gè)空閑塊，將塊號(hào)和頁(yè)號(hào)填入頁(yè)表

修改位示圖

存在的問(wèn)題

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

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

反置頁(yè)表 – 按物理塊號(hào)排序

IBM RT; HP Spectrum…

反置頁(yè)表很大，使用Hash表加快檢索

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

除了Hash表，聯(lián)想寄存器也被用來(lái)存放最近使用過(guò)的頁(yè)表項(xiàng)

分頁(yè)存儲(chǔ)管理方案的評(píng)價(jià)

優(yōu)點(diǎn)：

較好地解決了碎片問(wèn)題

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

提高了主存的利用率

缺點(diǎn)：

頁(yè)內(nèi)碎片

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

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

虛擬頁(yè)式存儲(chǔ)

虛擬存儲(chǔ)器

局部性原理(principle of locality)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

虛擬頁(yè)式虛擬段式虛擬段頁(yè)式

虛擬頁(yè)式存儲(chǔ)管理

基本原理

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

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

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

為實(shí)現(xiàn)虛擬頁(yè)式存儲(chǔ)管理:

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

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

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

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

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

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

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

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

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

主存頁(yè)面分配策略

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

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

頁(yè)面調(diào)入策略

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

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

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

缺點(diǎn)：每次僅調(diào)入一頁(yè)，增加了磁盤(pán)I/O的啟動(dòng)頻率。

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

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

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

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

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

調(diào)入頁(yè)面的來(lái)源：

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

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

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

存儲(chǔ)分配的安全性考慮:

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

頁(yè)面調(diào)度算法

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

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

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

b、顛簸

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

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

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

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

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

這是Belady貝萊迪于1966年提出的一種理論上的算法。該算法每次都淘汰以后永不使用的，或者過(guò)最長(zhǎng)的時(shí)間后才會(huì)被訪問(wèn)的頁(yè)面。

顯然，采用這種算法會(huì)保證最低的缺頁(yè)率，但它是無(wú)法實(shí)現(xiàn)的，因?yàn)樗仨氈理?yè)面“將來(lái)”的訪問(wèn)情況。不過(guò)，該算法仍有一定意義，可作為衡量其他算法優(yōu)劣的一個(gè)標(biāo)準(zhǔn)。

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

采用OPT淘汰算法：

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

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

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

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

2->4->5->1

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

置換第2頁(yè)

將第2頁(yè)改為6

替換指針指向第4頁(yè)4->5->1->6

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

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

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

采用FIFO淘汰算法：

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

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

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

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

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

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

c、多位寄存器法

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

每次訪問(wèn)一頁(yè)時(shí)，將該頁(yè)所對(duì)應(yīng)的寄存器最左位置1

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

選擇R值最小的頁(yè)淘汰。

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

頁(yè)面 時(shí)刻

T1      T2      T3    

復(fù)制

P0 1000 0100 1010

P1 1000 1100 0110

P2 0000 1000 0100

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

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

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

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

該算法首先檢查位于FIFO鏈鏈?zhǔn)椎捻?yè)，如果它的訪問(wèn)位為0，則選擇該頁(yè)淘汰；如果它的訪問(wèn)位為1，則清除其訪問(wèn)位，將它移至FIFO鏈的鏈尾，重復(fù)此算法的查找過(guò)程，直至遇到新鏈?zhǔn)醉?yè)是一個(gè)訪問(wèn)位為0的較早進(jìn)入內(nèi)存的頁(yè)為止，把它選為被淘汰的頁(yè)。

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

當(dāng)訪問(wèn)某頁(yè)時(shí)，就將該頁(yè)引用位置1

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

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

選擇引用位為0的頁(yè)面淘汰。

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

二次機(jī)會(huì)淘汰算法缺點(diǎn)：就是需要把訪問(wèn)位為1的處于鏈?zhǔn)椎捻?yè)移至鏈尾，這需要一定的開(kāi)銷(xiāo)。

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

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

訪問(wèn)頁(yè)號(hào)727

引發(fā)缺頁(yè)

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

它把FIFO算法的思想與頁(yè)面的訪問(wèn)位和修改位結(jié)合起來(lái)確定一個(gè)接近LRU算法的淘汰對(duì)象。

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

按照下列次序選擇被淘汰的頁(yè)面：

①訪問(wèn)位＝０，修改位＝０；直接淘汰；

②訪問(wèn)位＝０，修改位＝１；寫(xiě)回外存后淘汰；

③訪問(wèn)位＝１，修改位＝０；直接淘汰；

④訪問(wèn)位＝１，修改位＝１；寫(xiě)回外存后淘汰；

頁(yè)面請(qǐng)求序列為：2，3，2，1，5，2，4，5，3，2，5，2

內(nèi)存分配3塊

用OPT、LRU、FIFO、Clock算法寫(xiě)出頁(yè)面置換過(guò)程

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

影響缺頁(yè)中斷率的因素

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

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

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

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

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

（3）頁(yè)面大小的選擇不合理

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

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

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

段式存儲(chǔ)管理

分段

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

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

段表

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

地址變換

段的保護(hù)

越界中斷處理

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

缺段中斷處理

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

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

段的動(dòng)態(tài)連接

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

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

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

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

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

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

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

只讀代碼共享

純代碼舉例：比如，有一個(gè)代碼段只是簡(jiǎn)單的輸出“Hello World!”。

頁(yè)式系統(tǒng)與段式系統(tǒng)的對(duì)比

段長(zhǎng)是可變的，頁(yè)的大小是固定的。

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

分頁(yè)存儲(chǔ)：段內(nèi)地址W字段溢出會(huì)自動(dòng)加入到頁(yè)號(hào)中。

總結(jié)

段頁(yè)式存儲(chǔ)管理

分頁(yè)、分段的有缺點(diǎn)分析

基本思想

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

邏輯地址：

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

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

段表頁(yè)表

地址轉(zhuǎn)換

評(píng)價(jià)

優(yōu)點(diǎn)：

保留了分段和請(qǐng)求分頁(yè)存儲(chǔ)管理的全部?jī)?yōu)點(diǎn)

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

缺點(diǎn)：

增加了硬件成本

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

總結(jié)

虛擬內(nèi)存

這一部分在虛擬頁(yè)式存儲(chǔ)管理講過(guò)了

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

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

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

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

Linux的存儲(chǔ)管理

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

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

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

文件管理

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

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

輔存的存儲(chǔ)空間分配：

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

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

設(shè)備管理

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

廣義的IO設(shè)備：

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

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

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

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

使用線程池的原因：

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

實(shí)現(xiàn)線程安全的隊(duì)列Queue

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

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

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

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

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

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

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

死鎖的四個(gè)必要條件Hyacinth_Dy的博客-CSDN博客死鎖的四個(gè)必要條件

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

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

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

缺頁(yè)率的計(jì)算方法水中魚(yú)自由的博客-CSDN博客_缺頁(yè)率怎么算

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

標(biāo)簽： 文件存儲(chǔ)