1. 基礎(chǔ)知識

1.1、 基本概念、 功能

• 馮諾伊曼體系結(jié)構(gòu)
  1拿撩、計算機處理的數(shù)據(jù)和指令一律用二進制數(shù)表示
  2、順序執(zhí)行程序
  計算機運行過程中如蚜，把要執(zhí)行的程序和處理的數(shù)據(jù)首先存入主存儲器（內(nèi)存）压恒，計算機執(zhí)行程序時，將自動地并按順序從主存儲器中取出指令一條一條地執(zhí)行错邦，這一概念稱作順序執(zhí)行程序探赫。
  3、計算機硬件由運算器撬呢、控制器伦吠、存儲器、輸入設(shè)備和輸出設(shè)備五大部分組成。
• 原碼
  原碼就是符號位加上真值的絕對值,即用第一位表示符號,其余位表示值.比如如果是8位二進制:
  [+1]原=0000 0001
  [-1]原=1000 0001
  第一位是符號位.因為第一位是符號位,所以8位二進制數(shù)的取值范圍就是:
  [1111 1111,0111 1111]
  [-127,127]
  原碼是人腦最容易理解和計算的表示方式
• 反碼
  反碼的表示方法是:
  正數(shù)的反碼是其本身
  負數(shù)的反碼是在其原碼的基礎(chǔ)上,符號位不變毛仪，其余各個位取反.
  [+1]=[00000001]原=[00000001]反
  [-1]=[10000001]原=[11111110]反
  可見如果一個反碼表示的是負數(shù),人腦無法直觀的看出來它的數(shù)值.通常要將其轉(zhuǎn)換成原碼再計算
• 補碼
  補碼的表示方法是:
  正數(shù)的補碼就是其本身
  負數(shù)的補碼是在其原碼的基礎(chǔ)上,符號位不變,其余各位取反,最后+1搁嗓。(即在反碼的基礎(chǔ)上+1)
  [+1]=[00000001]原=[00000001]反=[00000001]補
  [-1]=[10000001]原=[11111110]反=[11111111]補
  對于負數(shù),補碼表示方式也是人腦無法直觀看出其數(shù)值的.通常也需要轉(zhuǎn)換成原碼在計算其數(shù)值.
• 定點數(shù)與浮點數(shù)
  定點數(shù)是小數(shù)點固定的數(shù)。在計算機中沒有專門表示小數(shù)點的位箱靴，小數(shù)點的位置是約定默認的腺逛。一般固定在機器數(shù)的最低位之后，或是固定在符號位之后刨晴。前者稱為定點純整數(shù)屉来，后者稱為定點純小數(shù)。
  定點數(shù)表示法簡單直觀狈癞，但是數(shù)值表示的范圍太小茄靠，運算時容易產(chǎn)生溢出。
  浮點數(shù)是小數(shù)點的位置可以變動的數(shù)蝶桶。為增大數(shù)值表示范圍慨绳，防止溢出，采用浮點數(shù)表示法真竖。浮點表示法類似于十進制中的科學計數(shù)法脐雪。
  在計算機中通常把浮點數(shù)分成階碼和尾數(shù)兩部分來表示，其中階碼一般用補碼定點整數(shù)表示恢共，尾數(shù)一般用補碼或原碼定點小數(shù)表示战秋。為保證不損失有效數(shù)字，對尾數(shù)進行規(guī)格化處理讨韭，也就是平時所說的科學記數(shù)法脂信，即保證尾數(shù)的最高位為
  1.實際數(shù)值通過階碼進行調(diào)整
  階符表示指數(shù)的符號位、階碼表示冪次透硝、數(shù)符表示尾數(shù)的符號位狰闪、尾數(shù)表示規(guī)格化后的小數(shù)值。
  N=尾數(shù)×基數(shù)階碼（指數(shù)）
  位(Bit)濒生、字節(jié)(Byte)柑潦、字(Word)
  Bit最小單位
  1 Byte=8 Bit
  Word數(shù)據(jù)處理運算的基本單位如果是一臺16位機润绎，那么谭跨，它的1個字就由2個字節(jié)構(gòu)成蜕衡，字長為16位
• 大端小端模式
  小端字節(jié)序指低字節(jié)數(shù)據(jù)存放在內(nèi)存低地址處，高字節(jié)數(shù)據(jù)存放在內(nèi)存高地址處觉义；
  大端字節(jié)序是高字節(jié)數(shù)據(jù)存放在低地址處恒序，低字節(jié)數(shù)據(jù)存放在高地址處。
  Big Endian
  低地址高地址
  ---------------------------------------------------->
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |12|34|56|78|
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  Little Endian
  低地址高地址
  ---------------------------------------------------->
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |78|56|34|12|
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
• 字節(jié)對齊
  現(xiàn)代計算機中內(nèi)存空間都是按照byte劃分的谁撼，從理論上講似乎對任何類型的變量的訪問可以從任何地址開始歧胁，但實際情況是在訪問特定類型變量的時候經(jīng)常在特定的內(nèi)存地址訪問滋饲，這就需要各種類型數(shù)據(jù)按照一定的規(guī)則在空間上排列，而不是順序的一個接一個的排放喊巍，這就是對齊崭参。
• • 為什么要進行字節(jié)對齊奄喂？
    效率問題，字節(jié)對齊能提?存取數(shù)據(jù)的速度域帐。
    比如有的平臺每次都是從偶地址處讀取數(shù)據(jù),對于一個int型的變量,若從偶地址單元處存放,則只需一個讀取周期即可讀取該變量，但是若從奇地址單元處存放,則需要2個讀取周期讀取該變量是整。
    字節(jié)對齊的原則
    數(shù)據(jù)成員對齊規(guī)則：結(jié)構(gòu)(struct)(或聯(lián)合(union))的數(shù)據(jù)成員肖揣，第一個數(shù)據(jù)成員放在offset為0的地方，以后每個數(shù)據(jù)成員存儲的起始位置要從該成員大小或者成員的子成員大懈∪搿（只要該成員有子成員龙优，比如說是數(shù)組，結(jié)構(gòu)體等）的整數(shù)倍開始(比如int在32位機為4字節(jié),則要從4的整數(shù)倍地址開始存儲事秀。
    結(jié)構(gòu)體作為成員:如果一個結(jié)構(gòu)里有某些結(jié)構(gòu)體成員,則結(jié)構(gòu)體成員要從其內(nèi)部最大元素大小的整數(shù)倍地址開始存儲陋率。(struct a里存有struct b,b里有char,int,double等元素,那b應該從8的整數(shù)倍開始存儲。)
    收尾工作:結(jié)構(gòu)體的總大小秽晚，也就是sizeof的結(jié)果赴蝇，必須是其內(nèi)部最大成員的整數(shù)倍，不足的要補齊。
• 中斷
  中斷是指在計算機執(zhí)行程序的過程中，由于出現(xiàn)了某些特殊事情，使得CPU暫停對程序的執(zhí)行宙帝，轉(zhuǎn)而去執(zhí)行處理這一事件的程序沪编。等這些特殊事情處理完之后再回去執(zhí)行之前的程序
  1腿时、內(nèi)部中斷
  2、軟中斷
  3、外部中斷
• • 中斷優(yōu)先級
    機器錯誤>時鐘>磁盤>網(wǎng)絡(luò)設(shè)備>終端>軟件中斷
• • 系統(tǒng)調(diào)用
    在講系統(tǒng)調(diào)用之前，先說下進程的執(zhí)行在系統(tǒng)上的兩個級別：用戶級和核心級，也稱為用戶態(tài)和系統(tǒng)態(tài)(user mode and kernel mode)。
    程序的執(zhí)行一般是在用戶態(tài)下執(zhí)行的溜嗜，但當程序需要使用操作系統(tǒng)提供的服務時捎琐，比如說打開某一設(shè)備籽御、創(chuàng)建文件、讀寫文件等，就需要向操作系統(tǒng)發(fā)出調(diào)用服務的請求稚虎，這就是系統(tǒng)調(diào)用程奠。
    發(fā)生系統(tǒng)調(diào)用時距境，進程不做工作诬滩，由內(nèi)核做相應操作。
• • 用戶態(tài)：
    用戶態(tài)的進程能存取它們自己的指令和數(shù)據(jù)，但不能存取內(nèi)核指令和數(shù)據(jù)（或其他進程的指令和數(shù)據(jù)）茴厉。然而，核心態(tài)下的進程能夠存取內(nèi)核和用戶地址
• • 核心態(tài)：
    某些機器指令是特權(quán)指令，在用戶態(tài)下執(zhí)行特權(quán)指令會引起錯誤

• 整體結(jié)構(gòu)
  1） 處理器管理
  在多道程序環(huán)境下被丧，處理器的分配和運行都是以進程為基本單位，因而對處理器的管理可歸結(jié)為對進程的管理。進程管理的主要功能有：
  * 進程控制，進程同步辱揭，進程通信，死鎖處理庵朝，處理器調(diào)度等。
  2） 存儲器管理
  存儲器管理的主要任務是位多通道程序的運行提供良好的環(huán)境，方便用戶使用以及提高內(nèi)存的利用率偿短。因此，存儲器管理應具備：內(nèi)存分配、地址映射坪创、內(nèi)存保護與共享和內(nèi)存擴充等谈飒。
  3） 文件管理
  文件管理主要包括文件的存儲空間管理、目錄管理及文件讀寫管理及保護等奖年。
  4） 設(shè)備管理
  設(shè)備管理的主要任務就是完成用戶的IO請求，方便用戶使用各種設(shè)備褪储，并提高設(shè)備的利用率揖庄，主要包括混充管理市怎、設(shè)備分配、設(shè)備處理和虛擬設(shè)備等功能颅夺。

1.2、操作系統(tǒng)的發(fā)展與分類

1其爵、手工操作階段
2冒冬、脫機輸入輸出階段
3、批處理階段
批處理技術(shù)是指計算機系統(tǒng)對一批作業(yè)自動進行處理的一種技術(shù)摩渺。批處理階段的特點是：用戶不用與計算機直接打交道简烤，而是通過專門的操作員來完成作業(yè)的輸入輸出。隨著外圍設(shè)備的迅速發(fā)展摇幻，后來又出現(xiàn)了脫機批處理系統(tǒng)横侦，即主機直接與磁盤通信挥萌。
（1） 單道批處理系統(tǒng)
主要特點：自動性、順序性丈咐、單道性瑞眼。
（2） 多道批處理系統(tǒng)
多道程序設(shè)計技術(shù)是指在計算機內(nèi)存中同時存放幾道相互獨立的程序，它們在管理程序的控制下相互交替的運行棵逊。其特征是：多道伤疙，宏觀上并行，微觀上串行辆影。
4徒像、分時操作系統(tǒng)
所謂分時系統(tǒng)就是把處理器的運行時間分成很短的時間片，按時間片輪流把處理器分配給各聯(lián)機作業(yè)使用蛙讥。若某個作業(yè)再分配給他的時間片內(nèi)不能完成其計算锯蛀，則改作業(yè)暫時停止運行，把處理器讓給其他作業(yè)使用次慢，等待下一輪再繼續(xù)運行旁涤，由于計算機速度很快，作業(yè)運行輪轉(zhuǎn)的很快迫像，給每個用戶的感覺好像是自己獨占一臺計算機劈愚。
分時操作系統(tǒng)十多個用戶通過終端同事共享一臺主機，這些終端連接在主機上闻妓，用戶可以同時與主機進行交互操作而不互相干擾菌羽。所以，實現(xiàn)分時系統(tǒng)最關(guān)鍵的問題由缆，是如何使用戶能與自己的作業(yè)進行交互注祖，即當用戶在自己的中斷上輸入命令時，系統(tǒng)應能及時接收并及時處理該命令均唉，再將結(jié)果返回用戶是晨。分時系統(tǒng)也是支持多道程序設(shè)計的系統(tǒng)，但它不同于多道批處理系統(tǒng)舔箭。多道批處理是實現(xiàn)作業(yè)自動控制而無需人工干預的系統(tǒng)署鸡，而分時系統(tǒng)是實現(xiàn)人機交互的系統(tǒng)，這使得分時系統(tǒng)具有與批處理系統(tǒng)不同的特征限嫌，其主要特征如下：
同時性靴庆，交互性，獨立性怒医，及時性炉抒。
5、實時操作系統(tǒng)
實時系統(tǒng)的主要特點是：實時性和可靠性稚叹。
6焰薄、網(wǎng)絡(luò)操作系統(tǒng)和分布式計算機系統(tǒng)
7拿诸、個人計算機操作系統(tǒng)

1.3、 操作系統(tǒng)運行機制

計算機系統(tǒng)中塞茅，通常CPU執(zhí)行兩種不同性質(zhì)的程序亩码，一種是操作系統(tǒng)內(nèi)核程序；另一種是用戶自編程序或系統(tǒng)外城的應用程序野瘦。對操作系統(tǒng)而言描沟，這兩種程序的作用不同，前者是后者的管理者和控制者鞭光，因此“管理程序”要執(zhí)行一些特權(quán)指令吏廉，而“被管理程序”出于安全性考慮，不能執(zhí)行這些指令惰许。所謂特權(quán)指令席覆，是指計算集中不允許用戶直接使用的指令，如IO指令汹买、置中斷指令佩伤。
操作系統(tǒng)在具體實現(xiàn)上劃分了用戶態(tài)和核心態(tài)，以嚴格區(qū)分兩種類程序晦毙。
一些與硬件關(guān)聯(lián)交緊密的模塊生巡，諸如時鐘管理程序、中斷處理程序结序、設(shè)備驅(qū)動程序等處于最底層障斋。其次是運行頻率較高的程序纵潦，諸如金城關(guān)里徐鹤、存儲器管理和設(shè)備管理等。這兩部分內(nèi)容構(gòu)成了操作系統(tǒng)的內(nèi)核邀层。這部分內(nèi)容的指令操作工作在核心態(tài)返敬。
內(nèi)核是計算機上配置的最底層軟件，是計算機功能的延伸寥院。不同系統(tǒng)對內(nèi)核的定義稍有區(qū)別劲赠，大多數(shù)操作系統(tǒng)內(nèi)核包括四個方面的內(nèi)容。

• （1） 時鐘管理
  在計算機外部設(shè)備中秸谢，時鐘是最關(guān)鍵的設(shè)備凛澎。時鐘的第一功能是計時，操作系統(tǒng)需要通過時鐘管理估蹄，向用戶提供標準的系統(tǒng)時間塑煎。另外，通過時鐘中斷的管理臭蚁，可以實現(xiàn)京城的切換最铁。諸如：在分時操作系統(tǒng)中讯赏，采用時間片輪轉(zhuǎn)調(diào)度的實現(xiàn)；在實時系統(tǒng)中冷尉，按截止時間控制運行的實現(xiàn)漱挎；在批處理系統(tǒng)中，通過時鐘管理來衡量一個作業(yè)的運行程度等雀哨。因此磕谅，系統(tǒng)管理的方方面面無不依賴于它。
• （2） 中斷機制
  引入中斷技術(shù)的初衷是提高多道程序運行環(huán)境中CPU的利用率震束，而且主要是針對外部設(shè)備的怜庸。后來的到發(fā)展，形成了多種類等垢村，成為操作系統(tǒng)各項操作的基礎(chǔ)割疾。例如鍵盤或鼠標信息的輸入、進程的管理和調(diào)度嘉栓、系統(tǒng)功能的調(diào)用宏榕、設(shè)備驅(qū)動、文件訪問等侵佃，無不依賴于中斷機制麻昼。可以說馋辈，現(xiàn)代計算機系統(tǒng)是靠中斷驅(qū)動的軟件抚芦。
• （3） 原語
  按層次結(jié)構(gòu)涉及的操作系統(tǒng)，底層必然是一些可被調(diào)用的公用小程序迈螟，他們各自完成一個規(guī)定的操作叉抡。其特點是：1.他們處于操作系統(tǒng)的最底層，是最接近硬件的部分答毫。2.這些程序的運行具有原子性——其操作只能一起合成褥民。3.這些程序的運行時間都較短，而且調(diào)用頻繁洗搂。
  通常把具有這些特點的程序成為原語消返。定義源于的直接方法是關(guān)閉中斷，讓她的所有動作不可分割的進行完再打開中斷耘拇。
  系統(tǒng)中的設(shè)備驅(qū)動撵颊、CPU切換、進程通信等功能中的部分操作都可以定義為原語惫叛，是他們呢成為內(nèi)核的組成部分倡勇。
• （4） 系統(tǒng)控制的數(shù)據(jù)結(jié)構(gòu)及處理
  系統(tǒng)中用來登記狀態(tài)信息的數(shù)據(jù)結(jié)構(gòu)很多。比如作業(yè)控制塊挣棕、進程控制塊译隘、設(shè)備控制塊亲桥、各類鏈表、消息隊列固耘、緩沖區(qū)题篷、空閑區(qū)登記表、內(nèi)存分配表等厅目。為了實現(xiàn)有效地管理 番枚，系統(tǒng)需要一些基本的操作，常見的操作有以下三種：
  1） 進程管理：進程狀態(tài)管理损敷、進程調(diào)度和分配葫笼、創(chuàng)建與撤掉進程控制塊的隊列維護操作等。
  2） 存儲器管理：存儲器的空間分配和回收管理拗馒、內(nèi)存信息保護程序路星、代碼對換程序等。
  3） 設(shè)備管理：緩沖區(qū)管理诱桂、設(shè)備分配和回收等洋丐。
  從上述內(nèi)容可以了解告嘲，核心態(tài)指令實際上包括系統(tǒng)調(diào)用類指令和一些針對時鐘廓握、中斷和原語的操作指令顶吮。

2. 進程管理

• 多任務（Multi-tasking）系統(tǒng)标锄。
  操作系統(tǒng)從最底層接管了所有硬件資源。所有的應用程序在操作系統(tǒng)之上以 進程（Process） 的方式運行突雪，每個進程都有自己獨立的地址空間交播，相互隔離摔敛。CPU 由操作系統(tǒng)統(tǒng)一進行分配辞槐。每個進程都有機會得到 CPU掷漱，同時在操作系統(tǒng)控制之下，如果一個進程運行超過了一定時間催蝗，就會被暫停掉切威，失去 CPU 資源育特。這樣就避免了一個程序的錯誤導致整個系統(tǒng)死機丙号。如果操作系統(tǒng)分配給各個進程的運行時間都很短，CPU 可以在多個進程間快速切換缰冤，就像很多進程都同時在運行的樣子犬缨。幾乎所有現(xiàn)代操作系統(tǒng)都是采用這樣的方式支持多任務，例如 Unix棉浸，Linux怀薛，Windows 以及 macOS。
• 進程
  進程是一個具有獨立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活動迷郑。它可以申請和擁有系統(tǒng)資源枝恋，是一個動態(tài)的概念创倔，是一個活動的實體。它不只是程序的代碼焚碌，還包括當前的活動畦攘，通過程序計數(shù)器的值和處理寄存器的內(nèi)容來表示。
  進程的概念主要有兩點：第一十电，進程是一個實體知押。每一個進程都有它自己的地址空間，一般情況下鹃骂，包括文本區(qū)域（text region）台盯、數(shù)據(jù)區(qū)域（data region）和堆棧（stack region）。文本區(qū)域存儲處理器執(zhí)行的代碼畏线；數(shù)據(jù)區(qū)域存儲變量和進程執(zhí)行期間使用的動態(tài)分配的內(nèi)存静盅；堆棧區(qū)域存儲著活動過程調(diào)用的指令和本地變量。第二寝殴，進程是一個“執(zhí)行中的程序”温亲。程序是一個沒有生命的實體，只有處理器賦予程序生命時杯矩，它才能成為一個活動的實體栈虚，我們稱其為進程。
• 進程狀態(tài)轉(zhuǎn)換
  1史隆、等待態(tài)：等待某個事件的完成魂务；
  2、就緒態(tài)：等待系統(tǒng)分配處理器以便運行泌射；
  3粘姜、運行態(tài)：占有處理器正在運行。
  運行態(tài)→等待態(tài) 往往是由于等待外設(shè)熔酷，等待主存等資源分配或等待人工干預而引起的孤紧。
  等待態(tài)→就緒態(tài) 則是等待的條件已滿足，只需分配到處理器后就能運行拒秘。
  運行態(tài)→就緒態(tài) 不是由于自身原因号显，而是由外界原因使運行狀態(tài)的進程讓出處理器，這時候就變成就緒態(tài)躺酒。例如時間片用完押蚤，或有更高優(yōu)先級的進程來搶占處理器等。
  就緒態(tài)→運行態(tài) 系統(tǒng)按某種策略選中就緒隊列中的一個進程占用處理器羹应，此時就變成了運行態(tài)
• 進程調(diào)度
• • 調(diào)度種類
    高級揽碘、中級和低級調(diào)度作業(yè)從提交開始直到完成，往往要經(jīng)歷下述三級調(diào)度：

1. 高級調(diào)度：(High-Level Scheduling)又稱為作業(yè)調(diào)度，它決定把后備作業(yè)調(diào)入內(nèi)存運行雳刺；
2. 中級調(diào)度：(Intermediate-Level Scheduling)又稱為在虛擬存儲器中引入劫灶，在內(nèi)、外存對換區(qū)進行進程對換掖桦。
3. 低級調(diào)度：(Low-Level Scheduling)又稱為進程調(diào)度浑此，它決定把就緒隊列的某進程獲得CPU；

• 非搶占式調(diào)度與搶占式調(diào)度

1. 非搶占式
   分派程序一旦把處理機分配給某進程后便讓它一直運行下去滞详，直到進程完成或發(fā)生進程調(diào)度進程調(diào)度某事件而阻塞時凛俱，才把處理機分配給另一個進程。
2. 搶占式
   操作系統(tǒng)將正在運行的進程強行暫停料饥，由調(diào)度程序?qū)PU分配給其他就緒進程的調(diào)度方式蒲犬。

• 調(diào)度策略的設(shè)計
  1） CPU利用率
  CPU是計算機系統(tǒng)中最重要的資源之一，所以應盡可能使CPU保持在忙狀態(tài)岸啡，是這一資源利用率最高原叮。
  （2） 系統(tǒng)吞吐量
  系統(tǒng)吞吐量表示單位時間內(nèi)CPU完成作業(yè)的數(shù)量。長作業(yè)需要消耗較長的處理器時間巡蘸，因此會降低系統(tǒng)的吞吐量奋隶。而對于短作業(yè)，他們所需要消耗的處理器時間端悦荒，因此能提高系統(tǒng)的吞吐量唯欣。調(diào)度算法和方式的不同，也會對系統(tǒng)的吞吐量產(chǎn)生較大的影響搬味。
  （3） 周轉(zhuǎn)時間
  從任務開始到任務結(jié)束的時間作業(yè)的周轉(zhuǎn)時間=作業(yè)完成時間-作業(yè)提交時間
  （4） 等待時間
  等待時間是指進程處于等處理器狀態(tài)時間之和境氢，等待時間越長，用戶滿意度越低碰纬。處理器調(diào)度算法實際上并不影響作業(yè)執(zhí)行或輸入輸出操作時間萍聊，只影響作業(yè)在就緒隊列中等待所花的時間。因此悦析，衡量一個調(diào)度算法優(yōu)劣常常只需簡單地考察等待時間寿桨。
  （5） 響應時間
  從用戶輸入到產(chǎn)生反應的時間

CPU任務可以分為交互式任務和批處理任務，調(diào)度最終的目標是合理的使用CPU强戴，使得交互式任務的響應時間盡可能短亭螟，用戶不至于感到延遲，同時使得批處理任務的周轉(zhuǎn)時間盡可能短酌泰，減少用戶等待的時間媒佣。

• 調(diào)度算法
• • FIFO或First Come, First Served (FCFS)
    調(diào)度的順序就是任務到達就緒隊列的順序匕累。
    公平陵刹、簡單(FIFO隊列)、非搶占、不適合交互式衰琐。未考慮任務特性也糊，平均等待時間可以縮短
• • Shortest Job First (SJF)
    最短的作業(yè)(CPU區(qū)間長度最小)最先調(diào)度。
    可以證明羡宙，SJF可以保證最小的平均等待時間狸剃。
• • Shortest Remaining Job First (SRJF)
    SJF的可搶占版本，比SJF更有優(yōu)勢狗热。
• • SJF(SRJF): 如何知道下一CPU區(qū)間大谐佟？根據(jù)歷史進行預測: 指數(shù)平均法匿刮。
• • 優(yōu)先權(quán)調(diào)度
    每個任務關(guān)聯(lián)一個優(yōu)先權(quán)僧凰，調(diào)度優(yōu)先權(quán)最高的任務。
    注意：優(yōu)先權(quán)太低的任務一直就緒熟丸，得不到運行训措，出現(xiàn)“饑餓”現(xiàn)象。
• • FCFS是RR的特例光羞，SJF是優(yōu)先權(quán)調(diào)度的特例绩鸣。這些調(diào)度算法都不適合于交互式系統(tǒng)。
• • Round-Robin(RR)
    設(shè)置一個時間片纱兑，按時間片來輪轉(zhuǎn)調(diào)度（“輪叫”算法）
    優(yōu)點: 定時有響應呀闻，等待時間較短；缺點: 上下文切換次數(shù)較多潜慎；
• • • 如何確定時間片总珠？
      時間片太大，響應時間太長勘纯；吞吐量變小局服，周轉(zhuǎn)時間變長；當時間片過長時驳遵，退化為FCFS淫奔。
• • 多級隊列調(diào)度
    按照一定的規(guī)則建立多個進程隊列
    不同的隊列有固定的優(yōu)先級（高優(yōu)先級有搶占權(quán)）
    不同的隊列可以給不同的時間片和采用不同的調(diào)度方法
    存在問題1：沒法區(qū)分I/O bound和CPU bound；
    存在問題2：也存在一定程度的“饑餓”現(xiàn)象堤结；
• • 多級反饋隊列
    在多級隊列的基礎(chǔ)上唆迁，任務可以在隊列之間移動，更細致的區(qū)分任務竞穷。
    可以根據(jù)“享用”CPU時間多少來移動隊列唐责，阻止“饑餓”。
    最通用的調(diào)度算法瘾带，多數(shù)OS都使用該方法或其變形鼠哥，如UNIX、Windows等。

• 進程同步

• 臨界資源與臨界區(qū)
  在操作系統(tǒng)中朴恳，進程是占有資源的最小單位（線程可以訪問其所在進程內(nèi)的所有資源抄罕，但線程本身并不占有資源或僅僅占有一點必須資源）。但對于某些資源來說于颖，其在同一時間只能被一個進程所占用呆贿。這些一次只能被一個進程所占用的資源就是所謂的臨界資源。典型的臨界資源比如物理上的打印機森渐，或是存在硬盤或內(nèi)存中被多個進程所共享的一些變量和數(shù)據(jù)等(如果這類資源不被看成臨界資源加以保護做入，那么很有可能造成丟數(shù)據(jù)的問題)。
  對于臨界資源的訪問同衣，必須是互斥進行母蛛。也就是當臨界資源被占用時，另一個申請臨界資源的進程會被阻塞乳怎，直到其所申請的臨界資源被釋放彩郊。而進程內(nèi)訪問臨界資源的代碼被成為臨界區(qū)。
  對于臨界區(qū)的訪問過程分為四個部分：
  進入?yún)^(qū):查看臨界區(qū)是否可訪問蚪缀，如果可以訪問秫逝，則轉(zhuǎn)到步驟二，否則進程會被阻塞
  臨界區(qū):在臨界區(qū)做操作
  退出區(qū):清除臨界區(qū)被占用的標志
  剩余區(qū)：進程與臨界區(qū)不相關(guān)部分的代碼
• 解決臨界區(qū)問題可能的方法：
  一般軟件方法
  關(guān)中斷方法
  硬件原子指令方法
  信號量方法
  信號量
  信號量是一個確定的二元組（s询枚，q）违帆，其中s是一個具有非負初值的整形變量，q是一個初始狀態(tài)為空的隊列金蜀，整形變量s表示系統(tǒng)中某類資源的數(shù)目：
  當其值 ≥ 0 時刷后，表示系統(tǒng)中當前可用資源的數(shù)目
  當其值 ＜ 0 時，其絕對值表示系統(tǒng)中因請求該類資源而被阻塞的進程數(shù)目
  除信號量的初值外渊抄，信號量的值僅能由P操作和V操作更改尝胆，操作系統(tǒng)利用它的狀態(tài)對進程和資源進行管理
  P操作：
  P操作記為P(s)，其中s為一信號量护桦，它執(zhí)行時主要完成以下動作：
  s.value = s.value - 1含衔； /可理解為占用1個資源，若原來就沒有則記帳“欠”1個/
  若s.value ≥ 0二庵，則進程繼續(xù)執(zhí)行贪染，否則（即s.value < 0），則進程被阻塞催享，并將該進程插入到信號量s的等待隊列s.queue中
  說明：實際上杭隙，P操作可以理解為分配資源的計數(shù)器，或是使進程處于等待狀態(tài)的控制指令
  V操作：
  V操作記為V(s)因妙，其中s為一信號量痰憎，它執(zhí)行時票髓，主要完成以下動作：
  s.value = s.value + 1；/可理解為歸還1個資源信殊，若原來就沒有則意義是用此資源還1個欠帳/
  若s.value > 0炬称，則進程繼續(xù)執(zhí)行汁果，否則（即s.value ≤ 0）,則從信號量s的等待隊s.queue中移出第一個進程涡拘，使其變?yōu)榫途w狀態(tài)，然后返回原進程繼續(xù)執(zhí)行
  說明：實際上据德，V操作可以理解為歸還資源的計數(shù)器鳄乏，或是喚醒進程使其處于就緒狀態(tài)的控制指令
  信號量方法實現(xiàn)：生產(chǎn)者 ? 消費者互斥與同步控制

semaphore fullBuffers = 0; /*倉庫中已填滿的貨架個數(shù)*/
semaphore emptyBuffers = BUFFER_SIZE;/*倉庫貨架空閑個數(shù)*/
semaphore mutex = 1; /*生產(chǎn)-消費互斥信號*/
Producer() 
{ 
while(True)
{  
/*生產(chǎn)產(chǎn)品item*/
emptyBuffers.P(); 
mutex.P(); 
/*item存入倉庫buffer*/
mutex.V();
fullBuffers.V();
}
}
Consumer() 
{
while(True)
{
fullBuffers.P(); 
mutex.P();    
/*從倉庫buffer中取產(chǎn)品item*/
mutex.V();
emptyBuffers.V();
/*消費產(chǎn)品item*/
}
}
使用pthread實現(xiàn)的生產(chǎn)者－消費者模型：
#include <pthread.h>#include <stdio.h>
#include <stdlib.h>#define BUFFER_SIZE 10
static int buffer[BUFFER_SIZE] = { 0 };static int count = 0;
pthread_t consumer, producer;pthread_cond_t cond_producer, cond_consumer;pthread_mutex_t mutex;
void* consume(void* _){
while(1){
pthread_mutex_lock(&mutex);
while(count == 0){
printf("empty buffer, wait producer\n");
pthread_cond_wait(&cond_consumer, &mutex); 
}
count--;
printf("consume a item\n");
pthread_mutex_unlock(&mutex);
pthread_cond_signal(&cond_producer);
//pthread_mutex_unlock(&mutex);
}
pthread_exit(0);
}
void* produce(void* _){
while(1){
pthread_mutex_lock(&mutex);
while(count == BUFFER_SIZE){
printf("full buffer, wait consumer\n");
pthread_cond_wait(&cond_producer, &mutex);
}
count++;
printf("produce a item.\n");
pthread_mutex_unlock(&mutex);
pthread_cond_signal(&cond_consumer);
//pthread_mutex_unlock(&mutex);
}
pthread_exit(0);
}
int main() {
pthread_mutex_init(&mutex, NULL);
pthread_cond_init(&cond_consumer, NULL);
pthread_cond_init(&cond_producer, NULL);
int err = pthread_create(&consumer, NULL, consume, (void*)NULL);
if(err != 0){
printf("consumer thread created failed\n");
exit(1);
}
err = pthread_create(&producer, NULL, produce, (void*)NULL);
if(err != 0){
printf("producer thread created failed\n");
exit(1);
}
pthread_join(producer, NULL);
pthread_join(consumer, NULL);  
//sleep(1000);
pthread_cond_destroy(&cond_consumer);
pthread_cond_destroy(&cond_producer);
pthread_mutex_destroy(&mutex);
return 0;
}

• 死鎖
  死鎖: 多個進程因循環(huán)等待資源而造成無法執(zhí)行的現(xiàn)象。
  死鎖會造成進程無法執(zhí)行棘利，同時會造成系統(tǒng)資源的極大浪費(資源無法釋放)橱野。
• • 死鎖產(chǎn)生的4個必要條件：
    互斥使用(Mutual exclusion)
    指進程對所分配到的資源進行排它性使用，即在一段時間內(nèi)某資源只由一個進程占用善玫。如果此時還有其它進程請求資源水援，則請求者只能等待，直至占有資源的進程用畢釋放茅郎。
    不可搶占(No preemption)
    指進程已獲得的資源蜗元，在未使用完之前，不能被剝奪系冗，只能在使用完時由自己釋放奕扣。
    請求和保持(Hold and wait)
    指進程已經(jīng)保持至少一個資源，但又提出了新的資源請求掌敬，而該資源已被其它進程占有惯豆，此時請求進程阻塞，但又對自己已獲得的其它資源保持不放奔害。
    循環(huán)等待(Circular wait)
    指在發(fā)生死鎖時楷兽，必然存在一個進程——資源的環(huán)形鏈，即進程集合{P0华临，P1拄养，P2，···银舱，Pn}中的P0正在等待一個P1占用的資源瘪匿；P1正在等待P2占用的資源，……寻馏，Pn正在等待已被P0占用的資源棋弥。
• 死鎖避免——銀行家算法
  思想: 判斷此次請求是否造成死鎖若會造成死鎖，則拒絕該請求
• 進程間通信

1. 本地進程間通信的方式有很多诚欠，可以總結(jié)為下面四類：
2. 消息傳遞（管道顽染、FIFO漾岳、消息隊列）
3. 同步（互斥量、條件變量粉寞、讀寫鎖尼荆、文件和寫記錄鎖、信號量）
4. 共享內(nèi)存（匿名的和具名的）
5. 遠程過程調(diào)用（Solaris門和Sun RPC）
6. 文件

• 線程
  多進程解決了前面提到的多任務問題唧垦。然而很多時候不同的程序需要共享同樣的資源（文件福也，信號量等）漆撞，如果全都使用進程的話會導致切換的成本很高秧饮，造成 CPU 資源的浪費檬果。于是就出現(xiàn)了線程的概念。
  線程坊秸，有時被稱為輕量級進程(Lightweight Process麸祷，LWP），是程序執(zhí)行流的最小單元褒搔。一個標準的線程由線程ID阶牍，當前指令指針(PC），寄存器集合和堆棧組成星瘾。

• • 線程具有以下屬性：
    輕型實體 線程中的實體基本上不擁有系統(tǒng)資源走孽，只是有一點必不可少的、能保證獨立運行的資源死相。線程的實體包括程序融求、數(shù)據(jù)和TCB。線程是動態(tài)概念算撮，它的動態(tài)特性由線程控制塊TCB（Thread Control Block）描述生宛。
• • 獨立調(diào)度和分派的基本單位。
    在多線程OS中肮柜，線程是能獨立運行的基本單位陷舅，因而也是獨立調(diào)度和分派的基本單位。由于線程很“輕”审洞，故線程的切換非常迅速且開銷欣痴觥（在同一進程中的）。
    可并發(fā)執(zhí)行芒澜。 在一個進程中的多個線程之間仰剿，可以并發(fā)執(zhí)行，甚至允許在一個進程中所有線程都能并發(fā)執(zhí)行痴晦；同樣南吮，不同進程中的線程也能并發(fā)執(zhí)行，充分利用和發(fā)揮了處理機與外圍設(shè)備并行工作的能力誊酌。
• • 共享進程資源部凑。 在同一進程中的各個線程露乏，都可以共享該進程所擁有的資源，這首先表現(xiàn)在：所有線程都具有相同的地址空間（進程的地址空間）涂邀，這意味著瘟仿，線程可以訪問該地址空間的每一個虛地址；此外比勉，還可以訪問進程所擁有的已打開文件劳较、定時器、信號量等敷搪。由于同一個進程內(nèi)的線程共享內(nèi)存和文件兴想，所以線程之間互相通信不必調(diào)用內(nèi)核幢哨。
    線程共享的環(huán)境包括：進程代碼段赡勘、進程的公有數(shù)據(jù)(利用這些共享的數(shù)據(jù)，線程很容易的實現(xiàn)相互之間的通訊)捞镰、進程打開的文件描述符闸与、信號的處理器、進程的當前目錄和進程用戶ID與進程組ID岸售。

• 線程和進程的比較
  1） 調(diào)度：在引入線程的操作系統(tǒng)中践樱，線程是獨立調(diào)度的基本單位，進程是資源擁有的基本單位凸丸。
  2） 擁有資源：進程是擁有資源的基本單位拷邢，而線程不擁有系統(tǒng)資源，單線程可以防偽其隸屬進程的系統(tǒng)資源屎慢。
  3） 并發(fā)性：在引入線程的操作系統(tǒng)中瞭稼，不僅進程之間可以并發(fā)執(zhí)行，線程之間也可以并發(fā)執(zhí)行腻惠，從而是操作系統(tǒng)具有更好的并發(fā)性环肘，大大提高了系統(tǒng)的吞吐量。
  4） 系統(tǒng)開銷：線程開銷極小集灌。
  5） 地址空間和其他資源：進程的地址空間之間相互獨立悔雹，同一進程的各線程間共享進程的資源，進程內(nèi)的線程對進程外的其他進程不可見欣喧。
  6） 通信方面：進程間通信需要進程同步和互斥手段的輔助腌零，以保證數(shù)據(jù)的一致性，而線程間可以直接讀寫進程數(shù)據(jù)段來進行通信唆阿。

• 協(xié)程
  協(xié)程益涧，又稱微線程，纖程酷鸦。英文名Coroutine饰躲。
  協(xié)程可以理解為用戶級線程牙咏，協(xié)程和線程的區(qū)別是：線程是搶占式的調(diào)度，而協(xié)程是協(xié)同式的調(diào)度嘹裂，協(xié)程避免了無意義的調(diào)度妄壶，由此可以提高性能，但也因此寄狼，程序員必須自己承擔調(diào)度的責任丁寄，同時，協(xié)程也失去了標準線程使用多CPU的能力泊愧。

• IO多路復用
  基本概念
  IO多路復用是指內(nèi)核一旦發(fā)現(xiàn)進程指定的一個或者多個IO條件準備讀取伊磺，它就通知該進程。IO多路復用適用如下場合：
  當客戶處理多個描述字時（一般是交互式輸入和網(wǎng)絡(luò)套接口）删咱，必須使用I/O復用屑埋。
  當一個客戶同時處理多個套接口時，而這種情況是可能的痰滋，但很少出現(xiàn)摘能。
  如果一個TCP服務器既要處理監(jiān)聽套接口，又要處理已連接套接口敲街，一般也要用到I/O復用团搞。
  如果一個服務器即要處理TCP，又要處理UDP多艇，一般要使用I/O復用逻恐。
  如果一個服務器要處理多個服務或多個協(xié)議，一般要使用I/O復用峻黍。
  與多進程和多線程技術(shù)相比复隆，I/O多路復用技術(shù)的最大優(yōu)勢是系統(tǒng)開銷小，系統(tǒng)不必創(chuàng)建進程/線程奸披，也不必維護這些進程/線程昏名，從而大大減小了系統(tǒng)的開銷。
  常見的IO復用實現(xiàn)
  select(Linux/Windows/BSD)
  epoll(Linux)
  kqueue(BSD/Mac OS X)

2.2 疑難問題

• 1阵面、進程與程序的區(qū)別與聯(lián)系
• 2轻局、死鎖與饑餓
  具有等待隊列的信號量的實現(xiàn)可能導致這樣的情況：兩個或多個進程無限的等待一個事件，而該事件只能由這些等待進程之一來產(chǎn)生样刷。這里的事件是V操作的執(zhí)行仑扑，當出現(xiàn)這樣的狀態(tài)時，這些進程成為死鎖置鼻。
  說一組集成處于死鎖狀態(tài)是指：組內(nèi)的每個進程都等待一個事件镇饮，而該事件只可能由組內(nèi)的另一個進程產(chǎn)生。這里關(guān)心的主要事件是資源的獲取和釋放箕母。
  與死鎖相關(guān)的另一個問題是無限期阻塞或“饑餓”储藐，即進程在信號量內(nèi)無窮等待的情況俱济。
  產(chǎn)生饑餓的主要原因是：在一個動態(tài)系統(tǒng)中，對于每類系統(tǒng)資源钙勃，操作系統(tǒng)需要確定一個分配策略蛛碌，當多個進程同時申請某類資源是，由分配策略確定資源分配給進程的次序辖源。有的時候資源分配策略可能是不公平的蔚携，既不能保證等待時間上界的存在。在這種情況下克饶，及時系統(tǒng)沒有發(fā)生死鎖酝蜒，某些進程也可能會長時間等待。當?shù)却龝r間給進程推薦和響應帶來明顯影響時矾湃，城發(fā)生了進程“饑餓”亡脑，當“饑餓”到一定程度的進程所賦予的任務即使完成也不再具有實際意義時就成該進程被“餓死”。
  “饑餓”并不表示系統(tǒng)一定死鎖洲尊。但至少有一個進程的執(zhí)行被無限期的推遲远豺，“饑餓”與死鎖的主要區(qū)別有：
  1）進入饑餓狀態(tài)的進程可以只有一個奈偏，但由于循環(huán)等待條件進入死鎖狀態(tài)的進程卻必須大于或等于兩個坞嘀。
  2）處于饑餓狀態(tài)的進程可以處于就緒狀態(tài)，而處于死鎖狀態(tài)的進程則必定是處于阻塞狀態(tài)惊来。
• 3丽涩、銀行家算法的工作原理
  銀行家算法的主要思想是避免系統(tǒng)進入不安全狀態(tài)。在每次進行資源分配時裁蚁，它首先檢查系統(tǒng)是否有足夠的資源滿足要求矢渊，如果有，則先進行分配枉证，并對分配后的新狀態(tài)進行安全性檢查矮男。如果新狀態(tài)安全，則正式分配上述資源室谚，否則就拒絕分配上述資源毡鉴。這樣，它保證系統(tǒng)始終處于安全狀態(tài)秒赤，從而避免死鎖現(xiàn)象的發(fā)生猪瞬。
• 4、進程同步入篮、互斥的區(qū)別和聯(lián)系
  并發(fā)進程的執(zhí)行會產(chǎn)生想制約的關(guān)系：一種是進程之間競爭使用臨界資源陈瘦，只能讓它們逐個使用，這種現(xiàn)象稱為互斥潮售，是一種競爭關(guān)系痊项；另一種是進程之間協(xié)同完成任務锅风，在關(guān)鍵點上等待另一個進程發(fā)來的消息，以便協(xié)同一致鞍泉，是一種協(xié)作關(guān)系遏弱。
• 5、作業(yè)和進程的關(guān)系
  進程是系統(tǒng)資源的使用者塞弊，系統(tǒng)的資源大部分都是以進程為單位分配的漱逸。而用戶使用計算機是為了實現(xiàn)一串相關(guān)的任務，通常把用戶要求計算機完成的這一串任務稱為作業(yè)游沿。
  批處理系統(tǒng)中的可以通過磁記錄設(shè)備或系統(tǒng)提交作業(yè)饰抒，由系統(tǒng)的SPOOLLing輸入進程將作業(yè)放入磁盤的輸入井中，作為后備作業(yè)诀黍。作業(yè)調(diào)度程序（一般也作為獨立的進程運行）每選擇一刀后備作業(yè)運行時袋坑，首先為該作業(yè)創(chuàng)建一個進程（稱為該作業(yè)的根進程）。該進程將執(zhí)行作業(yè)控制語言解釋程序

3. 內(nèi)存管理

程序可執(zhí)行文件的結(jié)構(gòu)

一個程序的可執(zhí)行文件在內(nèi)存中的結(jié)果眯勾，從大的角度可以分為兩個部分：

只讀部分

.text只讀部分包括程序代碼

.rodata程序中的常量

可讀寫部分（也就是變量）

.data： 初始化了的全局變量和靜態(tài)變量

.bss： 即 Block Started by Symbol枣宫， 未初始化的全局變量和靜態(tài)變量

heap： 堆，使用 malloc, realloc, 和 free 函數(shù)控制的變量吃环，堆在所有的線程也颤，共享庫，和動態(tài)加載的模塊中被共享使用

stack： 棧郁轻，函數(shù)調(diào)用時使用棧來保存函數(shù)現(xiàn)場翅娶，自動變量（即生命周期限制在某個 scope 的變量）也存放在棧中。

• 答疑一 靜態(tài)變量和全局變量

這兩個概念都是很常見的概念好唯，又經(jīng)常在一起使用竭沫，很容易造成混淆。

全局變量：在一個代碼文件當中骑篙，一個變量要么定義在函數(shù)中蜕提，要么定義在在函數(shù)外面。當定義在函數(shù)外面時靶端，這個變量就有了全局作用域谎势，成為了全局變量。全局變量不光意味著這個變量可以在整個文件中使用躲查，也意味著這個變量可以在其他文件中使用（這種叫做 external linkage）它浅。當有如下兩個文件時；

a.c
#include <stdio.h>
int a;
int compute(void);
int main(){
    a = 1;
    printf("%d %d\n", a, compute());
    return 0;
}
b.c
int a;
int compute(void){
    a = 0;
    return a;
}

在 Link 過程中會產(chǎn)生重復定義錯誤镣煮，因為有兩個全局的 a 變量姐霍，Linker 不知道應該使用哪一個。為了避免這種情況，就需要引入 static镊折。

靜態(tài)變量： 指使用 static 關(guān)鍵字修飾的變量胯府，static 關(guān)鍵字對變量的作用域進行了限制，具體的限制如下：

<u>在函數(shù)外定義：全局變量恨胚，但是只在當前文件中可見（叫做 internal linkage）</u>

<u>在函數(shù)內(nèi)定義：全局變量骂因，但是只在此函數(shù)內(nèi)可見（同時，在多次函數(shù)調(diào)用中赃泡，變量的值不會丟失）</u>

<u>（C++）在類中定義：全局變量寒波，但是只在此類中可見</u>

對于全局變量來說，為了避免上面提到的重復定義錯誤升熊，我們可以在一個文件中使用 static俄烁，另一個不使用。這樣使用 static 的就會使用自己的 a 變量级野，而沒有用 static 的會使用全局的 a 變量页屠。當然，最好兩個都使用 static蓖柔，避免更多可能的命名沖突辰企。

注意：'靜態(tài)'這個中文翻譯實在是有些莫名其妙，給人的感覺像是不可改變的况鸣，而實際上 static 跟不可改變沒有關(guān)系牢贸，不可改變的變量使用 const 關(guān)鍵字修飾，注意不要混淆懒闷。

Bonus 部分 —— extern： extern 是 C 語言中另一個關(guān)鍵字十减，用來指示變量或函數(shù)的定義在別的文件中，使用 extern 可以在多個源文件中共享某個變量愤估，例如這里的例子。 extern 跟 static 在含義上是“水火不容”的速址，一個表示不能在別的地方用玩焰，一個表示要去別的地方找。如果同時使用的話芍锚，有兩種情況昔园，一種是先使用 static，后使用 extern 并炮，即：

static int m;extern int m;

這種情況默刚，后面的 m 實際上就是前面的 m 。如果反過來：

extern int m;static int m;

這種情況的行為是未定義的逃魄，編譯器也會給出警告荤西。

• 答疑二 程序在內(nèi)存和硬盤上不同的存在形式

這里我們提到的幾個區(qū)，是指程序在內(nèi)存中的存在形式。和程序在硬盤上存儲的格式不是完全對應的邪锌。程序在硬盤上存儲的格式更加復雜勉躺，而且是和操作系統(tǒng)有關(guān)的，具體可以參考這里觅丰。一個比較明顯的例子可以幫你區(qū)分這個差別：之前我們提到過未定義的全局變量存儲在 .bss 區(qū)饵溅，這個區(qū)域不會占用可執(zhí)行文件的空間（一般只存儲這個區(qū)域的長度）棋凳，但是卻會占用內(nèi)存空間咐扭。這些變量沒有定義，因此可執(zhí)行文件中不需要存儲（也不知道）它們的值路呜，在程序啟動過程中冠句，它們的值會被初始化成 0 糖赔，存儲在內(nèi)存中。

棧

棧是用于存放本地變量轩端，內(nèi)部臨時變量以及有關(guān)上下文的內(nèi)存區(qū)域放典。程序在調(diào)用函數(shù)時，操作系統(tǒng)會自動通過壓棧和彈棧完成保存函數(shù)現(xiàn)場等操作基茵，不需要程序員手動干預奋构。

棧是一塊連續(xù)的內(nèi)存區(qū)域，棧頂?shù)牡刂泛蜅５淖畲笕萘渴窍到y(tǒng)預先規(guī)定好的拱层。能從棧獲得的空間較小弥臼。如果申請的空間超過棧的剩余空間時，例如遞歸深度過深根灯，將提示stackoverflow径缅。

棧是機器系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)，計算機會在底層對棧提供支持：分配專門的寄存器存放棧的地址烙肺，壓棧出棧都有專門的指令執(zhí)行纳猪，這就決定了棧的效率比較高。

堆

堆是用于存放除了棧里的東西之外所有其他東西的內(nèi)存區(qū)域桃笙，當使用malloc和free時就是在操作堆中的內(nèi)存氏堤。對于堆來說，釋放工作由程序員控制搏明，容易產(chǎn)生memory leak鼠锈。

堆是向高地址擴展的數(shù)據(jù)結(jié)構(gòu)，是不連續(xù)的內(nèi)存區(qū)域星著。這是由于系統(tǒng)是用鏈表來存儲的空閑內(nèi)存地址的购笆，自然是不連續(xù)的，而鏈表的遍歷方向是由低地址向高地址虚循。堆的大小受限于計算機系統(tǒng)中有效的虛擬內(nèi)存同欠。由此可見样傍，堆獲得的空間比較靈活，也比較大行您。

對于堆來講铭乾，頻繁的new/delete勢必會造成內(nèi)存空間的不連續(xù)，從而造成大量的碎片娃循，使程序效率降低炕檩。對于棧來講，則不會存在這個問題捌斧，因為棧是先進后出的隊列笛质，永遠都不可能有一個內(nèi)存塊從棧中間彈出。

堆都是動態(tài)分配的捞蚂，沒有靜態(tài)分配的堆妇押。棧有2種分配方式：靜態(tài)分配和動態(tài)分配。靜態(tài)分配是編譯器完成的姓迅，比如局部變量的分配敲霍。動態(tài)分配由alloca函數(shù)進行分配，但是棧的動態(tài)分配和堆是不同的丁存，他的動態(tài)分配是由編譯器進行釋放肩杈，無需我們手工實現(xiàn)。

計算機底層并沒有對堆的支持解寝，堆則是C/C++函數(shù)庫提供的扩然，同時由于上面提到的碎片問題，都會導致堆的效率比棧要低聋伦。

3.1 內(nèi)存分配

內(nèi)存管理基礎(chǔ)

• 1夫偶、內(nèi)存管理的概念
  內(nèi)存管理是操作系統(tǒng)設(shè)計中最重要和最復雜的內(nèi)容之一。計算機硬件一直在發(fā)展觉增，內(nèi)容容量也在不斷增長兵拢，但是仍然不可能將所有用戶進程和系統(tǒng)所需要的全部程序和數(shù)據(jù)全部放入主存中，所以操作系統(tǒng)必須將內(nèi)存空間進行合理的化肥和有效的動態(tài)分配抑片。操作系統(tǒng)對內(nèi)存的劃分和動態(tài)分配卵佛，就是內(nèi)存管理的概念。
  有效的內(nèi)存管理在多道程序設(shè)計中非常重要敞斋，不僅方便用戶使用存儲器、提高內(nèi)存利用率疾牲，還可以通過虛擬技術(shù)從邏輯上擴充存儲器植捎。
• 內(nèi)存管理的功能有：
  l 內(nèi)存空間的分配與回收，包括內(nèi)存的分配和共享阳柔。
  l 地址轉(zhuǎn)換焰枢，把邏輯地址轉(zhuǎn)換成相應的物理地址。
  l 內(nèi)存空間的擴充，利用虛擬技術(shù)或自動覆蓋技術(shù)济锄，從邏輯上擴充內(nèi)存暑椰。
  l 存儲保護，保證各道作業(yè)在各自存儲空間內(nèi)運行荐绝，互不干擾一汽。
  在進行具體的內(nèi)存管理之前，需要了解進程運行的基本原理和要求低滩。
• 創(chuàng)建進程首先要將程序和數(shù)據(jù)裝入內(nèi)存召夹。將用戶原程序變成可在內(nèi)存中執(zhí)行的程序，通常需要以下幾個步驟恕沫。
  l 編譯监憎，由編譯程序?qū)⒂脩粼创a編譯成若干個目標模塊。
  l 鏈接婶溯，由鏈接程序?qū)⒕幾g后形成的一組目標模塊鲸阔，以及所需庫函數(shù)鏈接，形成完整的裝入模塊迄委。
  l 裝入褐筛，由裝入程序?qū)⒀b入模塊裝入內(nèi)存。
• 程序的鏈接有以下三種方式：
  l 靜態(tài)鏈接：在程序運行之前跑筝，先將各目標模塊及它們所需的庫函數(shù)鏈接成一個完整的可執(zhí)行程序死讹，以后不再拆開。
  l 裝入時動態(tài)鏈接：將用戶源程序編譯后所得到的一組目標模塊曲梗，再裝入內(nèi)存時赞警，采用邊裝入變鏈接的方式。
  l 運行時動態(tài)鏈接：對某些目標模塊的連接虏两，是在程序執(zhí)行中需要該目標模塊時愧旦，才對她進行鏈接。其優(yōu)點是便于修改和更新定罢，便于實現(xiàn)對目標模塊的共享笤虫。
• 內(nèi)存的裝入模塊再裝入內(nèi)存時，同樣有以下三種方式：
  1）絕對裝入祖凫。在編譯時琼蚯，如果知道程序?qū)Ⅰv留在內(nèi)存的某個位置，編譯程序?qū)a(chǎn)生絕對地址的目標代碼惠况。絕對裝入程序按照裝入模塊的地址遭庶，將程序和數(shù)據(jù)裝入內(nèi)存。裝入模塊被裝入內(nèi)存后稠屠，由于程序中的邏輯地址與實際地址完全相同峦睡，故不需對程序和數(shù)據(jù)的地址進行修改翎苫。
  絕對裝入方式只適用于單道程序環(huán)境。另外榨了，程序中所使用的絕對地址煎谍，可在編譯或匯編時給出，也可由程序員直接賦予龙屉。
  2）可重定位裝入呐粘。在多道程序環(huán)境下，多個目標模塊的起始地址通常都是從0開始叔扼，程序中的其他地址都是相對于起始地址的事哭，此時應采用可重定位裝入方式。根據(jù)內(nèi)存的當前情況瓜富，將裝入模塊裝入到內(nèi)存的適當位置鳍咱。裝入時對目標程序中指令和數(shù)據(jù)的修改過程稱為重定位，地址變換通常是裝入時一次完成与柑，所以成為靜態(tài)重定位谤辜。
  其特點是在一個作業(yè)裝入內(nèi)存時，必須分配器要求的全部內(nèi)存空間价捧，如果沒有足夠的內(nèi)存丑念，就不能裝入，此外一旦作業(yè)進入內(nèi)存后结蟋，在整個運行期間脯倚，不能在內(nèi)存中移動，也不能再申請內(nèi)存空間嵌屎。
  3）動態(tài)運行時裝入推正，也成為動態(tài)重定位，程序在內(nèi)存中如果發(fā)生移動宝惰，就需要采用動態(tài)的裝入方式植榕。
  動態(tài)運行時的裝入程序在把裝入模塊裝入內(nèi)存后，并不立即把裝入模塊中的相對地址轉(zhuǎn)換為絕對地址尼夺，而是把這種地址轉(zhuǎn)換推遲到程序真正要執(zhí)行時才進行尊残。因此，裝入內(nèi)存后的所有地址均為相對地址淤堵，這種方式需要一個重定位寄存器的支持寝衫。
  其特點是可以將程序分配到不連續(xù)的存儲區(qū)中；在程序運行之前可以只裝入它的部分代碼即可運行拐邪，然后在程序運行期間竞端，根據(jù)需要動態(tài)申請分配內(nèi)存；便于程序段的共享庙睡，可以向用戶提供一個比存儲空間大得多的地址空間事富。
  編譯后，一個目標程序所限定的地址范圍稱為改程序的邏輯地址空間乘陪。編譯程序在對一個源程序進行編譯時统台，總是從0號單元開始為期分配地址，地址空間中的所有地址都是相對起始地址0的啡邑，因而邏輯地址也稱為相對地址贱勃。用戶程序和程序員只需要知道邏輯地址，而內(nèi)存管理的具體機制則是透明的谤逼，這些只有系統(tǒng)編程人員才會涉及贵扰。不同進程可以有相同的邏輯地址，因為這些相同的邏輯地址可以映射到主存的不同位置流部。
  物理地址空間實質(zhì)內(nèi)存中物理單位的集合戚绕，它是地址轉(zhuǎn)換的最終地址，進程在運行時執(zhí)行指令和訪問數(shù)據(jù)最后都要通過物理地址來存取主存枝冀。當裝入程序?qū)⒖蓤?zhí)行代碼裝入內(nèi)存時舞丛，必須通過地址轉(zhuǎn)換將邏輯地址轉(zhuǎn)換成物理地址，這個過程稱為地址重定位果漾。
  內(nèi)存分配前球切，需要保護操作系統(tǒng)不受用戶進程的影響，同時保護用戶進程不受其他用戶進程的影響绒障。通過采用重定位寄存器和界地址寄存器來實現(xiàn)這種保護吨凑。重定位寄存器含最小的物理地址值，界地址寄存器含邏輯地址值户辱。每個邏輯地址值必須小于界地址寄存器鸵钝。內(nèi)存管理機構(gòu)動態(tài)地將邏輯地址加上重定位寄存器的值后映射成物理地址，再送交內(nèi)存單元焕妙。
  當CPU調(diào)度程序選擇進程執(zhí)行時蒋伦，派遣程序會初始化重定位寄存器和界地址寄存器。每個地址都需要與寄存器進行核對焚鹊，可以保證操作系統(tǒng)和其他用戶程序及數(shù)據(jù)不被該進程運行所影響痕届。
• 2、覆蓋與交換
  覆蓋與交換技術(shù)是在多道程序環(huán)境下用來擴充內(nèi)存的兩種方法末患。覆蓋技術(shù)主要用在早期的操作系統(tǒng)中研叫，而交換技術(shù)則在現(xiàn)代操作系統(tǒng)中仍具有較強的生命力。
  早期的計算機系統(tǒng)中璧针，主存容量很小嚷炉，雖然住村中僅存放一道用戶程序，但是存儲空間放不下用戶進程的現(xiàn)象也經(jīng)常發(fā)生探橱，這一矛盾可以用覆蓋技術(shù)來解決申屹。其基本思想是：由于程序運行時并非任何時候都要訪問程序和數(shù)據(jù)的各個部分绘证，因此可以把用戶空間分成一個固定區(qū)和若干個覆蓋區(qū)。將經(jīng)郴┘ィ活躍的部分放在固定區(qū)嚷那，其余部分按調(diào)用關(guān)系分段。首先將那些將要訪問的段放入覆蓋區(qū)杆煞，其他段放在外存中魏宽，在需要調(diào)用時，系統(tǒng)再將其掉入覆蓋區(qū)决乎，替換其中原有的段队询。
  交換的基本思想是：把處于等待狀態(tài)（或在CPU調(diào)度原則下被剝奪運行權(quán)利）的進程從內(nèi)存移到輔存，把內(nèi)存空間騰出來构诚，這一過程又叫換出蚌斩；把準備好競爭CPU運行的進程從輔存移到內(nèi)存，這一過程又稱為換入唤反。
  例如凳寺，有一個CPU采用時間片輪轉(zhuǎn)調(diào)度算法的多道程序環(huán)境。時間片到彤侍，內(nèi)存管理器將剛剛執(zhí)行過的進程換出肠缨，將另一進程換入到剛剛釋放的內(nèi)存空間中。同時盏阶，CPU調(diào)度器可以將時間片分配給其他已在內(nèi)存中的進程晒奕。每個進程用完時間片都與另一進程交換。理想情況下名斟。內(nèi)存管理器的交換過程速度足夠快脑慧，總有進程在內(nèi)存中可以執(zhí)行。
  有關(guān)交換需要注意以下幾個問題：
  l 交換需要備份存儲砰盐，通常是快速磁盤闷袒。它必須足夠大，并且提供對這些內(nèi)存影響的直接訪問岩梳。
  l 為了有效使用CPU囊骤，需要每個進程的執(zhí)行時間比交換時間長，而影響交換時間的主要是轉(zhuǎn)移時間冀值。轉(zhuǎn)移時間與所見換的內(nèi)存空間成正比也物。
  l 如果換出進程，必須確保該進程是完全處于空閑狀態(tài)列疗。
  l 交換空間通常作為磁盤的一整塊滑蚯，且獨立與文件系統(tǒng)，因此使用就可能很快。
  l 交換通常在有許多進程運行且內(nèi)存空間吃緊的時候開始啟動告材，而系統(tǒng)負荷降低就暫停坤次。
  l 普通的交換使用不多，但交換策略的某些變種在許多系統(tǒng)中仍發(fā)揮作用创葡。
  交換技術(shù)主要是在不同進程之間進行浙踢，而覆蓋則用于同一個程序中。由于覆蓋技術(shù)要求給程序段之間的覆蓋結(jié)構(gòu)灿渴，使得其對用戶和程序員不透明，所以對于主存無法存放用戶程序的矛盾胰舆，現(xiàn)在操作系統(tǒng)是通過虛擬內(nèi)存技術(shù)來解決的骚露，覆蓋技術(shù)則已成為歷史；而交換技術(shù)在現(xiàn)代操作系統(tǒng)中仍具有較強的生命力缚窿。

3.1.2棘幸、虛擬內(nèi)存的基本概念

• 1）一次性：作業(yè)必須一次性全部裝入內(nèi)存后，方可運行倦零。這會導致兩種情況發(fā)生：
• • 當作業(yè)很大误续，不能全部被裝入內(nèi)存時，將使該作業(yè)無法運行扫茅；
• • 當大量作業(yè)要求運行時蹋嵌，由于內(nèi)存不足以容納所有作業(yè)税迷，只能使少數(shù)作業(yè)先運行凡恍，導致系統(tǒng)難以運行多道程序尉尾。
• 2） 駐留性：作業(yè)被裝入內(nèi)存后梗搅，就一直駐留在內(nèi)存中挠说，其任何部分都不會被換出扬霜，直至作業(yè)運行結(jié)束腕扶。運行中的進程逆瑞，會因等待IO而被阻塞糟描，可能處于長期等待狀態(tài)怀喉。

由上分析可知，許多在程序運行中不用或暫時不用的程序（數(shù)據(jù)）占據(jù)了大量的內(nèi)存空間船响，而一些需要運行的作業(yè)又無法裝入運行躬拢，顯然浪費了寶貴的內(nèi)存空間。
要真正理解虛擬內(nèi)存技術(shù)的思想灿意，首先必須了解計算機中著名的局部性原理估灿。著名的Bill Joy說過：“在研究所的時候， 我經(jīng)常開玩笑的說高速緩存是計算機科學中唯一重要的思想缤剧。事實上馅袁，高速緩存技術(shù)確實極大地影響了計算機系統(tǒng)的設(shè)計』脑”快表汗销、頁高速緩存以及虛擬內(nèi)存技術(shù)從廣義上講犹褒，都是屬于高速緩存技術(shù)。這個技術(shù)所依賴的原理就是局部性原理弛针。局部性原理既適用于程序結(jié)構(gòu)叠骑，也適用于數(shù)據(jù)結(jié)構(gòu)。

局部性原理表現(xiàn)在以下兩個方面：
1）時間局部性削茁。如果程序中的某條指令一旦執(zhí)行宙枷，則不久以后該指令可能再次執(zhí)行；如果某數(shù)據(jù)被訪問過茧跋，則不久以后該數(shù)據(jù)可能再次被訪問慰丛。產(chǎn)生時間局部性的典型原因，是由于在程序中存在著大量的循環(huán)操作瘾杭。
2）空間局部性诅病。一旦程序訪問量某個存儲單元，在不久之后粥烁，其附近的存儲單元也將被訪問贤笆，即程序在一段時間內(nèi)所訪問的地址，可能集中在一定的范圍之內(nèi)讨阻，其典型情況便是程序的順序執(zhí)行芥永。

時間局部性是通過將進來使用的指令和數(shù)據(jù)保存到高速緩存存儲器中，并使用高速緩存的層次結(jié)構(gòu)實現(xiàn)变勇⌒糇螅空間局部性通常是使用較大的高速緩存，并將預取機制集成到高速緩存控制邏輯中實現(xiàn)搀绣。虛擬內(nèi)存技術(shù)實際上就是建立了“內(nèi)存-外存”的兩級存儲器的結(jié)構(gòu)飞袋，利用局部性原理實現(xiàn)高速緩存。
基于局部性原理链患，在程序裝入時巧鸭，可以將程序的一部分裝入內(nèi)存，而將其與部分留在外存麻捻，就可以啟動程序執(zhí)行纲仍。在程序執(zhí)行過程中，當所訪問的信息不在內(nèi)存時贸毕，由操作系統(tǒng)將所需要的部分調(diào)入內(nèi)存郑叠，然后繼續(xù)執(zhí)行程序。另一方面明棍，操作系統(tǒng)將內(nèi)存中暫時不使用的內(nèi)容換到外存上乡革，從而騰出空間存放將要調(diào)入內(nèi)存的信息。這樣，計算機好像為用戶提供了一個比實際內(nèi)存大的多的存儲器沸版，成為虛擬存儲器嘁傀。
之所以將其稱為虛擬存儲器，是因為這種存儲器實際上并不存在视粮，只是由于系統(tǒng)提供了部分裝入细办、請求調(diào)入和置換功能后，給用戶的感覺是好像存在一個比實際物理內(nèi)存大得多的存儲器蕾殴。虛擬存儲器有以下三個主要特征：
1）多次性笑撞，是指無需在作業(yè)運行時一次性地全部裝入內(nèi)存，而是允許被分成多次調(diào)入內(nèi)存運行区宇。
2）對換性娃殖，是指無需在作業(yè)運行時一直常駐內(nèi)存，而是允許在作業(yè)的運行過程中议谷，進行換進和換出。
3）虛擬性 堕虹，是指從邏輯上擴充內(nèi)存的容量卧晓，是用戶所看到的內(nèi)存容量，遠大于實際的內(nèi)存容量赴捞。
虛擬內(nèi)存中逼裆，允許將一個作業(yè)分多次調(diào)入內(nèi)存。采用連續(xù)分配方式時赦政，會是相當一部分內(nèi)存空間都處于暫時或永久的空閑狀態(tài)胜宇，造成內(nèi)存資源的嚴重浪費，而且也無法從邏輯上擴大內(nèi)存容量恢着。因此桐愉，虛擬內(nèi)存的實現(xiàn)需要建立在離散分配的內(nèi)存管理方式的基礎(chǔ)上。
虛擬內(nèi)存的實現(xiàn)有以下三種方式：
l 請求分頁存儲管理
l 請求分段存儲管理
l 請求段頁式存儲管理
不管哪種方式掰派，都需要有一定的硬件支持从诲。一般需要的支持有以下幾個方面：
l 一定容量的內(nèi)存和外存。
l 頁表機制或段表機制靡羡，作為主要的數(shù)據(jù)結(jié)構(gòu)系洛。
l 中斷機構(gòu)，當用戶程序要訪問的部分尚未調(diào)入內(nèi)存略步，則產(chǎn)生中斷描扯。
l 地址變換機構(gòu)，邏輯地址到物理地址的變換趟薄。

3.2绽诚、連續(xù)分配管理方式

連續(xù)分配方式，是指為一個用戶程序分配一個連續(xù)的內(nèi)存空間。它主要包括單一連續(xù)分配憔购、固定分區(qū)分配和動態(tài)分區(qū)分配宫峦。
內(nèi)存在此方式下分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)僅提供給操作系統(tǒng)使用玫鸟，通常在低地址部分导绷；用戶區(qū)是為用戶提供的除系統(tǒng)外的內(nèi)存空間。這種方式無需進行內(nèi)存保護屎飘。
這種方式的優(yōu)點是簡單妥曲、無外部碎片，可以采用覆蓋技術(shù)钦购，不需要額外的技術(shù)支持檐盟。缺點是只能用于單用戶、單任務的操作系統(tǒng)中押桃，有內(nèi)部碎片葵萎，存儲器的利用率極低。

• • 固定分區(qū)
    固定分區(qū)分配是最簡單的一種多道程序存儲管理方式唱凯，它將內(nèi)存用戶空間劃分為若干個固定大小的區(qū)域羡忘，每個分區(qū)只裝入一道作業(yè)。當有空閑分區(qū)時磕昼，便可以再從外存的后備隊列中選擇適當大小的作業(yè)裝入該分區(qū)卷雕。如此循環(huán)。
    固定分區(qū)分配在劃分分區(qū)時票从，有兩種不同的方法：
    l 分區(qū)大小相等：用于利用一臺計算機去控制多個相同對象的場合漫雕。
    l 分區(qū)大小不等：劃分為含有多個較小的分區(qū)、適量的中等分區(qū)及少量的大分區(qū)峰鄙。
    為了便于內(nèi)存分配浸间，通常將分區(qū)按大小排隊，并為之建立一張分區(qū)使用表先馆，其中個表項包括每個分區(qū)的起始地址发框、大小及狀態(tài)。當有用戶程序要裝入時煤墙，便檢索該表梅惯，已找到合適的分區(qū)給與分配并將其狀態(tài)置為“已分配“。未找到合適分區(qū)則拒絕為該用戶程序分配內(nèi)存仿野。
    這種分區(qū)方式存在兩個問題：一個程序可能太大而放不進任何一個分區(qū)中铣减，這是用戶不得不使用覆蓋技術(shù)來使用內(nèi)存空間；二是主存利用率低脚作，當程序小于固定分區(qū)大小時葫哗，也占用了一個完整的內(nèi)存分區(qū)空間缔刹，這樣分區(qū)內(nèi)部有空間浪費。這種現(xiàn)象成為內(nèi)部碎片劣针。
• • 動態(tài)分區(qū)
    動態(tài)分區(qū)分配又稱為可變分區(qū)分配校镐，是一種動態(tài)劃分內(nèi)存的分區(qū)方法。這種分區(qū)方法預先將內(nèi)存劃分捺典，而是在進程裝入內(nèi)存時鸟廓，根據(jù)進程的大小動態(tài)的建立分區(qū)，并使分區(qū)的大小正好適合進程的需要襟己。因此系統(tǒng)中分區(qū)的大小和數(shù)目是可變的引谜。
    動態(tài)分區(qū)在開始分配時是很好的，但是之后會導致內(nèi)存中出現(xiàn)許多小的內(nèi)存塊擎浴。隨著時間的推移员咽，內(nèi)存中會產(chǎn)生越來越多的碎片，內(nèi)存的利用率隨之下降贮预。這種現(xiàn)象稱之為外部碎片現(xiàn)象贝室，指在所有分區(qū)外的存儲空間會變成越來越多的碎片，這與固定分區(qū)中的內(nèi)部碎片正好相對仿吞〉挡＃克服外部碎片可以通過緊湊技術(shù)來解決，就是操作系統(tǒng)不時地對進程進行移動和整理茫藏。但是這需要動態(tài)定位的支持，且相對費時霹琼。緊湊的過程實際上類似于windows系統(tǒng)中的磁盤整理程序务傲，只不過后者是對外存空間的緊湊。
• 動態(tài)分區(qū)的分配策略

1）首次適應算法：空閑分區(qū)以地址遞增的次序鏈接枣申。分配內(nèi)存時順序查找售葡，找到大小能滿足要求的第一個空閑分區(qū)。
2）最佳適應算法：空閑分區(qū)按容量遞增形成分區(qū)鏈忠藤，找到第一個能滿足要求的空閑分區(qū)挟伙。
3）最壞適應算法：有稱最大適應算法，空閑分區(qū)以容量遞減次序鏈接模孩。找到第一個能滿足要求的空閑分區(qū)尖阔，也就是挑選最大的分區(qū)。
4）臨近適應算法：又稱循環(huán)首次適應算法榨咐，由首次適應算法演變而成介却。不同之處是分配內(nèi)存時從此查找結(jié)束的位置開始繼續(xù)查找。

在這幾種方法中块茁，首次適應算法不僅是最簡單的齿坷，而且通常是最好和最快的桂肌。在UNIX系統(tǒng)的最初版本中，就是使用首次適應算法為進程分配內(nèi)存空間永淌，其中使用數(shù)組的數(shù)據(jù)結(jié)構(gòu)（而非鏈表）來實現(xiàn)崎场。不過，首次適應算法會使得內(nèi)存的低地址部分出現(xiàn)很多小的空閑分區(qū)遂蛀，而每次分配查找時谭跨，都要經(jīng)過這些分區(qū)。
臨近適應算法試圖解決這一問題答恶，但實際上饺蚊，它常常會導致在內(nèi)存的末尾分配空間，分裂成小碎片悬嗓。它通常比首次適應算法的結(jié)果要差污呼。
最佳適應算法雖然稱為最佳，但是性能通常很差包竹，因為每次最佳的分配會留下最小的內(nèi)存塊燕酷，它會產(chǎn)生最多的碎片。
最壞適應算法與最佳適應算法相反周瞎，選擇最大的可用塊苗缩，這看起來最不容易產(chǎn)生碎片，但是卻把最大的連續(xù)內(nèi)存劃分開声诸，會很快導致沒有可用的大的內(nèi)存塊酱讶，因此性能非常差。
以上內(nèi)存分區(qū)管理方法有一共同特點彼乌，即用戶進程在主存中都是連續(xù)存放的泻肯。

3.3、非連續(xù)分配管理方式

非連續(xù)分配方式允許一個程序分散的裝入不相鄰的內(nèi)存分區(qū)中慰照，根據(jù)分區(qū)的大小是否固定分為分頁存儲管理方式和分段存儲管理方式灶挟。
分頁存儲管理方式中，又根據(jù)運行作業(yè)時是否要把作業(yè)的所有頁面都裝入內(nèi)存才能運行分為基本分頁存儲管理和請求分頁存儲管理方式毒租。
固定分區(qū)會產(chǎn)生內(nèi)部碎片稚铣，動態(tài)分區(qū)會產(chǎn)生外部碎片，兩種技術(shù)對內(nèi)存的利用率都比較低墅垮。我們希望內(nèi)存的使用能盡量避免碎片的產(chǎn)生惕医，這就引出了分頁思想：把主存空間劃分為大小相等且固定的塊，塊相對較小噩斟，作為主存的基本單位曹锨。每個進程也以塊為單位進行劃分，進程在執(zhí)行時剃允，以塊為單位逐個申請主存中的塊空間沛简。

3.3.1齐鲤、 分頁存儲

• 1）分頁存儲的幾個基本概念
• • 1. 頁面和頁面大小。
       進程中的塊稱為頁椒楣，內(nèi)存中的塊稱為頁框给郊。外存也以同樣單位劃分，直接稱為塊捧灰。進程在執(zhí)行時需要申請主存空間淆九，就是要為每個頁面分配主存中的可用頁框，這就產(chǎn)生了頁和頁框的一一對應毛俏。
       為了方便地址轉(zhuǎn)換炭庙，頁面大小應是2的整數(shù)冪。同時頁面大小應當適中煌寇。如果頁面太小焕蹄，會是進程的頁面數(shù)過多，這樣頁表就過長阀溶，占用大量內(nèi)存腻脏，而且也會增加硬件地址轉(zhuǎn)換的開銷，降低頁面換入換出的效率银锻。頁面過大又會是頁面碎片過大永品，降低內(nèi)存利用率。所以頁面的大小應該適中击纬，考慮到空間效率和時間效率鼎姐。
• • 2. 地址結(jié)構(gòu)。
       分頁存儲管理的地址結(jié)構(gòu)包含兩部分：前一部分為頁號更振，后一部分為頁內(nèi)偏移量W症见。地址長度為32位，其中0~11為頁內(nèi)地址殃饿，即每頁大小為4kB；12~31位為頁號芋肠，地址空間最多允許有2^20頁乎芳。
• • 3.頁表。
    為了便于在內(nèi)存中找到進程的每個頁面所對應的物理塊帖池，系統(tǒng)為每個進程建立一張頁表奈惑，記錄頁面在內(nèi)存中對應的物理塊號，頁表一般存放在內(nèi)存中睡汹。
    在配置了頁表后肴甸，進程執(zhí)行時，通過查找該表囚巴，即可找到每頁在內(nèi)存中中的物理塊號原在∮讶牛可見，頁表的作用是實現(xiàn)從頁號到物理塊號的地址映射士败。
• 2）基本地址變換機構(gòu)
  地址變換機構(gòu)的任務是將邏輯地址中的頁號矢炼，轉(zhuǎn)換為內(nèi)存中物理塊號剩彬，地址變換是借助于頁表實現(xiàn)的。
  在系統(tǒng)中通常設(shè)置一個頁表寄存器PTR甚负，存放頁表在內(nèi)存的初值和頁表長度。
  邏輯地址到物理地址的變換過程如下：

1. 地址變換機構(gòu)自動將有效地址分為頁號和頁內(nèi)偏移量兩部分审残，再用頁號去檢索頁表梭域。在執(zhí)行檢索之前，先將頁號與頁表長度比較搅轿，如果頁號大于或等于頁表長度病涨，則表示地址越界并中斷。
2. 若未越界介时，則將頁表始址與頁號和頁表項長度的乘積相加没宾，便得到該表項在頁表中的位置，于是可從中得到該頁的物理塊號沸柔。
3. 與此同時循衰，在將有效地址中的頁內(nèi)偏移量送入物理地址寄存器的塊內(nèi)地址字段中。
   以上整個地址變換過程均是由硬件自動完成的褐澎。
   下面討論分頁管理方式存在的兩個主要問題：1每次訪存操作都需要進行邏輯地址到物理地址的轉(zhuǎn)換会钝，地址轉(zhuǎn)換過程必須足夠快，否則訪存速度會降低工三；2每個進程引入了頁表迁酸，用于存儲映射機制，頁表不能太大俭正，否則內(nèi)存利用率會降低奸鬓。

• 3）具有快表的地址變換機構(gòu)
  由上面介紹的地址變換過程可知，若頁表全部放在內(nèi)存中掸读，則要存取一個數(shù)據(jù)或一條指令至少要訪問兩次內(nèi)存：一次是訪問頁表串远，確定要存取的數(shù)據(jù)或指令的物理地址，第二次才根據(jù)該地址存取數(shù)據(jù)或指令儿惫。顯然澡罚，這種方法比通常執(zhí)行指令的速度慢了一半。
  為此肾请，在地址變換機構(gòu)中增設(shè)了一個具有并行查找能力的高速緩沖存儲器——快表留搔，又稱聯(lián)想寄存器TLB，用以存放當前訪問的若干頁表項铛铁。與此對應隔显，主存中的頁表也常稱為慢表却妨。
  在具有快表的分頁機制中，地址的變換過程：
• • 1 荣月、CPU給出有效地址后管呵，由硬件進行地址轉(zhuǎn)換，并將頁號送入高速緩存寄存器哺窄，并將此頁號與快表中的所有頁號同時進行比較捐下。
• • 2、如果有找到匹配的頁號萌业，說明索要訪問的頁表項在快表中坷襟，則可以直接從中讀出該頁對應的頁框號，送到屋里地址寄存器生年。這樣存取數(shù)據(jù)可以直接一次訪存實現(xiàn)婴程。
• • 3、如果沒有找到抱婉，則需要訪問主存中的頁表档叔，在讀出頁表項后，應同時將其存入快表中蒸绩，以供后面可能的再次訪問衙四。但是如果快表已滿，就必須按照一定的算法對其中舊的頁表項進行替換患亿。注意传蹈，有些處理器設(shè)計為快表和主存同時查找，如果在快表中匹配成功則終止主存中的查找步藕。
    一般快表的命中率可以達到90%惦界，這樣，分頁帶來的速度損失就降到10%咙冗≌赐幔快表的有效性是基于著名的局部性原理。這在后面的虛擬內(nèi)存中將會具體討論雾消。
• 4）兩級頁表
  第二個問題：由于引入了分頁管理瞬逊，進程在執(zhí)行時不需要將所有頁調(diào)入內(nèi)存頁框中，而只要將保存有映射關(guān)系的頁表調(diào)入內(nèi)存即可仪或。但是我們?nèi)匀恍枰紤]頁表的大小。如果頁表太大士骤，肯定是降低了內(nèi)存利用率的范删；從另一方面來說，程序所有的頁表項也并不需要同時保存在內(nèi)存中拷肌，因為在大多數(shù)情況下到旦，映射所需要的頁表都再也表的同一個頁面中旨巷。
  我們將頁表映射的思想進一步延伸，就可以得到二級分頁：將頁表的10頁空間也進行地址映射添忘，建立上一級頁表采呐，所以上一級頁表只需要一頁就足夠。在進程執(zhí)行時搁骑，只需要將這一頁上一級頁表調(diào)入內(nèi)存即可斧吐，進程的頁表和進程本身的頁面，可以在后面的執(zhí)行中再調(diào)入內(nèi)存仲器。
  分頁管理方式是從計算機的角度考慮設(shè)計的煤率，以提高內(nèi)存的利用率，提升計算機的性能乏冀，且分頁通過硬件機制實現(xiàn)蝶糯，對用戶完全透明；而分段管理方式的提出則考慮了用戶和程序員辆沦，以滿足方便編程昼捍、信息保護和共享、動態(tài)增長及動態(tài)鏈接等多方面的需要肢扯。

3.3.2 分段存儲

系統(tǒng)按照用戶進程中的自然段劃分邏輯空間妒茬。例如，用戶進程由主程序鹃彻、兩個字程序郊闯、棧和一段數(shù)據(jù)組成，于是可以把這個用戶進程劃分為5個段蛛株，每段從0開始編址团赁，并采用一段連續(xù)的地址空間（段內(nèi)要求連續(xù)，段間不要求連續(xù)）谨履，其邏輯地址由兩部分組成：段號與段內(nèi)偏移量欢摄，分別記為S、W笋粟。
段號為16位怀挠，段內(nèi)偏移量為16位，則一個作業(yè)最多可有2*16=65536個段害捕，最大段長64KB绿淋。
在頁式系統(tǒng)中，邏輯地址的頁號和頁內(nèi)偏移量對用戶是透明的尝盼；但在段式系統(tǒng)中吞滞，段號和段內(nèi)偏移量必須由用戶顯示提供，在高級程序設(shè)計語言中，這個工作由編譯程序完成裁赠。

• 2）段表殿漠。
  每個進程都有一張邏輯空間與主存空間映射的段表，其中每一段表項對應進程的一個段佩捞，段表項紀錄路該段在內(nèi)存中的起始地址和段的長度绞幌。
  在配置了段表后，執(zhí)行中的進程可通過查找段表一忱，找到每個段所對應的內(nèi)存區(qū)莲蜘。可見掀潮，段表用于實現(xiàn)從邏輯端段到物理內(nèi)存區(qū)的映射菇夸。
• 3）地址變換機構(gòu)
  為了實現(xiàn)進程從邏輯地址到物理地址的變換功能，在系統(tǒng)中設(shè)置了段表寄存器仪吧，用于存放段表始址和段表長度TL庄新。在進行地質(zhì)變換時，系統(tǒng)將邏輯地址中的段號薯鼠，與段表長度TL比較择诈。若段號大雨段表長度，表示短號太大出皇，訪問越界羞芍，于是產(chǎn)生越界中斷信號。若未越界郊艘，則根據(jù)段表的始址和該段的段號荷科，計算出該段對應段表項的位置，從中讀出該段在內(nèi)存中的起始地址纱注。然后畏浆，在檢查段內(nèi)地址W是否超過該段的段長SL。若超過狞贱，同樣發(fā)出越界中斷信號刻获。若未越界，則將該段的基址d與段內(nèi)地址相加瞎嬉，即可得到要訪問的內(nèi)存物理地址蝎毡。

頁式存儲管理能有效的提高內(nèi)存利用率，而分段存儲管理能反應程序的邏輯結(jié)構(gòu)并有利于段的共享氧枣。如果將這兩種存儲管理方法結(jié)合起來沐兵，就形成了段頁式存儲管理方式。

• 段頁式系統(tǒng)
  在段頁式系統(tǒng)中便监，作業(yè)的地址空間首先被分成若干個邏輯段扎谎，每段都有自己的段號，然后再將每一段分成若干個大小固定的頁。對內(nèi)存空間的管理仍然和分頁存儲管理一樣簿透，將其分成若干個和頁面大小相同的存儲塊，對內(nèi)存的分配以存儲塊為單位解藻。
  在段頁式系統(tǒng)中老充，作業(yè)的邏輯地址分為三部分：段號、頁號和頁內(nèi)偏移量螟左。
  為了實現(xiàn)地址變換啡浊，系統(tǒng)為每個進程建立一張段表，而每個分段有一張頁表胶背。段表表項中至少包括段號巷嚣、頁表長度和頁表起始地址，頁表表項中至少包括頁號和塊號钳吟。此外廷粒，系統(tǒng)中還應有一個段表寄存器，指出作業(yè)的段表起始地址和段表長度红且。
  在進行地址變換時坝茎，首先通過段表查到頁表起始地址，然后通過頁表找到幀號暇番，最后形成物理地址嗤放。進行一次訪問實際需要三次訪問主存，這里同樣可以使用快表提供加快速度壁酬，其關(guān)鍵字由段號次酌、頁號組成，值是對應的頁幀號和保護碼舆乔。

3.3.3 各種地址的定義

• 虛擬地址：用戶編程時將代碼（或數(shù)據(jù)）分成若干個段岳服，每條代碼或每個數(shù)據(jù)的地址由段名稱 + 段內(nèi)相對地址構(gòu)成，這樣的程序地址稱為虛擬地址
• 邏輯地址：虛擬地址中蜕煌，段內(nèi)相對地址部分稱為邏輯地址
• 物理地址：實際物理內(nèi)存中所看到的存儲地址稱為物理地址
• 邏輯地址空間：在實際應用中派阱，將虛擬地址和邏輯地址經(jīng)常不加區(qū)分，通稱為邏輯地址斜纪。邏輯地址的集合稱為邏輯地址空間
• 線性地址空間：CPU地址總線可以訪問的所有地址集合稱為線性地址空間
• 物理地址空間：實際存在的可訪問的物理內(nèi)存地址集合稱為物理地址空間
• MMU(Memery Management Unit內(nèi)存管理單元)：實現(xiàn)將用戶程序的虛擬地址（邏輯地址） → 物理地址映射的CPU中的硬件電路
• 基地址：在進行地址映射時贫母，經(jīng)常以段或頁為單位并以其最小地址（即起始地址）為基值來進行計算
• 偏移量：在以段或頁為單位進行地址映射時，相對于基地址的地址值
  虛擬地址先經(jīng)過分段機制映射到線性地址盒刚，然后線性地址通過分頁機制映射到物理地址腺劣。

虛擬內(nèi)存

· 請求調(diào)頁，也稱按需調(diào)頁因块，即對不在內(nèi)存中的“頁”橘原，當進程執(zhí)行時要用時才調(diào)入，否則有可能到程序結(jié)束時也不會調(diào)入

頁面置換算法

• FIFO算法
  先入先出，即淘汰最早調(diào)入的頁面趾断。

• OPT(MIN)算法
  選未來最遠將使用的頁淘汰拒名，是一種最優(yōu)的方案，可以證明缺頁數(shù)最小芋酌。
  可惜增显，MIN需要知道將來發(fā)生的事，只能在理論中存在脐帝，實際不可應用同云。

• LRU(Least-Recently-Used)算法
  用過去的歷史預測將來，選最近最長時間沒有使用的頁淘汰(也稱最近最少使用)堵腹。
  LRU準確實現(xiàn)：計數(shù)器法炸站，頁碼棧法。
  由于代價較高疚顷，通常不使用準確實現(xiàn)旱易，而是采用近似實現(xiàn)，例如Clock算法荡含。

內(nèi)存抖動現(xiàn)象：頁面的頻繁更換咒唆，導致整個系統(tǒng)效率急劇下降，這個現(xiàn)象稱為內(nèi)存抖動（或顛簸）释液。抖動一般是內(nèi)存分配算法不好全释，內(nèi)存太小引或者程序的算法不佳引起的。

Belady現(xiàn)象：對有的頁面置換算法误债，頁錯誤率可能會隨著分配幀數(shù)增加而增加浸船。

FIFO會產(chǎn)生Belady異常。

棧式算法無Belady異常寝蹈，LRU李命，LFU（最不經(jīng)常使用），OPT都屬于棧式算法

image.png

• Clock：時鐘替換算法（Clock）,
  給每個頁幀關(guān)聯(lián)一個使用位箫老。當該頁第一次裝入內(nèi)存或者被重新訪問到時封字，將使用位置為1。每次需要替換時耍鬓，查找使用位被置為0的第一個幀進行替換阔籽。在掃描過程中，如果碰到使用位為1的幀牲蜀，將使用位置為0笆制，在繼續(xù)掃描。如果所謂幀的使用位都為0涣达，則替換第一個幀在辆。
  總結(jié)：
  1.內(nèi)存中不存在頁面n证薇，而內(nèi)存中有空閑位置時，直接加入頁面n(1)匆篓，p加1
  2.內(nèi)存中不存在頁面n浑度，且內(nèi)存中沒有空閑位置時，發(fā)生替換n(1), p加1
  3.內(nèi)存中存在頁面n,p不變鸦概，將頁面n重置為n(1)（不管頁面n之前使用位為1或0）
• 改進后的時鐘算法：設(shè)置使用位u,修改位m
  1.最近未被訪問俺泣，未被修改(u=0,m=0)
  2.最近被訪問，未被修改(u=1,m=0)
  3.最近未被訪問完残，被修改(u=0,m=1)
  4.最近被訪問，被修改(u=1,m=1)
  a.從指針當前位置開始掃描横漏，不修改使用位谨设，對找到的第一個(u=0,m=0)進行替換
  b.如果a失敗，找到第一個（u=0,m=1）進行替換缎浇，掃描過程中扎拣，將使用位u置為0
  c,如果b失敗，此時指針回到起始位置素跺，且所有幀的使用位為0二蓝，重復步驟a,如果有必要，重復步驟b,直到找到為止

4. 文件管理

4.4指厌、本章疑難點
1刊愚、磁盤結(jié)構(gòu)
引導控制塊（Boot Control Block）包括系統(tǒng)從該分區(qū)引導操作系統(tǒng)所需要的信息。如果磁盤沒有操作系統(tǒng)踩验，那么這塊內(nèi)容為空鸥诽。它通常為分區(qū)的第一塊。UFS稱之為引導塊箕憾；NTFS稱之為分區(qū)引導扇區(qū)牡借。
分區(qū)控制塊包括分區(qū)詳細信息，如分區(qū)的塊數(shù)袭异、塊的大小钠龙、空閑塊的數(shù)量和指針、空閑FCB的數(shù)量和指針等御铃。UFS稱之為超級塊碴里；而NTFS稱之為主控文件表。
2畅买、內(nèi)存結(jié)構(gòu)
內(nèi)存分區(qū)表包含所有安裝分區(qū)的信息并闲。
內(nèi)存目錄結(jié)構(gòu)用來保存近來訪問過的目錄信息。對安裝分區(qū)的目錄谷羞，可以包括一個指向分區(qū)表的指針帝火。
系統(tǒng)范圍的打開文件表溜徙，包括每個打開文件的FCB復制和其他信息。
單個進程的打開文件表犀填，包括一個指向系統(tǒng)范圍內(nèi)已打開文件表中適合條目和其他信息的指針蠢壹。
3、文件系統(tǒng)實現(xiàn)概述
為了創(chuàng)建一個文件九巡，應用程序調(diào)用邏輯文件系統(tǒng)图贸。邏輯文件系統(tǒng)知道目錄結(jié)構(gòu)形勢，它將分配一個新的FCB給文件冕广，把相應目錄讀入內(nèi)存疏日，用新的文件名更新該目錄和FCB，并將結(jié)果寫回到磁盤撒汉。
一旦文件被創(chuàng)建沟优，它就能用于IO，不過首先要打開文件睬辐。調(diào)用open將文件名傳給文件系統(tǒng)挠阁，文件系統(tǒng)根據(jù)給定文件名搜索目錄結(jié)構(gòu)。部分目錄結(jié)構(gòu)通常緩存在內(nèi)存中以加快目錄操作溯饵。找到文件后侵俗，其FCB復制到系統(tǒng)范圍的打開文件表。該表不但存儲FCB丰刊，也有打開該文件的進程數(shù)量的條目隘谣。
然后，單個進程的打開文件表中會增加一個條目啄巧，并通過指針將系統(tǒng)范圍的打開文件表的條目同其他域（文件當前位置的指針和文件打開模式等）相連洪橘。調(diào)用open返回的是一個指向單個進程的打開文件表中合適條目的指針。所以文件操作都是通過該指針進行棵帽。
文件名不必是打開文件表的一部分喘鸟，因為一旦完成對FCB在磁盤上的定位任内，系統(tǒng)就不再使用文件名了。對于訪問打開文件表的索引，UNIX稱之為文件描述符导街；而Windows稱之為文件句柄漓库。因此吧黄，只要文件沒有被關(guān)閉柬帕，所有文件操作通過打開文件表來進行。
當一個進程關(guān)閉文件铅搓，就刪除一個相應的單個進程打開文件表的條目瑟押，系統(tǒng)范圍內(nèi)打開文件表的打開數(shù)也會遞減。當打開文件的所有用戶都關(guān)閉了一個文件時星掰，更新的文件信息會復制到磁盤的目錄結(jié)構(gòu)中多望，系統(tǒng)范圍打開的文件表的條目也將刪除嫩舟。
在實際中，系統(tǒng)調(diào)用open會首先搜索系統(tǒng)范圍的打開文件表以確定某文件是否已被其他進程使用怀偷。如果是家厌，就在單個進程的打開文件表中創(chuàng)建一項，并指向現(xiàn)有系統(tǒng)范圍的打開文件表的相應條目椎工。該算法在文件已打開時饭于，能節(jié)省大量開銷。
4维蒙、混合索引分配的實現(xiàn)
混合索引分配已在UNIX系統(tǒng)中采用掰吕。在UNIX System V的索引結(jié)點中，共設(shè)置了13個地址項颅痊，即iaddr（0）~iaddr（12）畴栖。在BSD UNIX的索引結(jié)點中，共設(shè)置了13個地址項八千，它們把所有的地址項分成兩類，即直接地址和間接地址燎猛。
（1）直接地址
為了提高對文件的檢索速度恋捆，在索引結(jié)點中可設(shè)置10個直接地址項，即用iaddr（0）~iaddr（9）來存放直接地址重绷。換言之沸停，在這里的每項中所存放的是該文件數(shù)據(jù)所在盤塊的盤塊號。假如每個盤塊的大小為4KB昭卓，當文件不大于40KB時愤钾，便可直接從索引節(jié)點中讀出該文件的全部盤塊號。
（2）一次間接地址
對于大候醒、中型文件能颁，只采用直接地址并不現(xiàn)實〉挂可再利用索引節(jié)點中的地址項iaddr（10）來提供一次間接地址伙菊。這種方式的實質(zhì)就是一級索引分配方式。一次間址塊就是索引塊敌土，系統(tǒng)將分配給文件的多個盤塊號記入其中镜硕。在一次間址塊中可存放1024個盤塊號，因而允許文件長達4MB返干。
（3）多次間接地址
當文件長度大于4MB+40KB時兴枯，系統(tǒng)還須采用二次間址分配方式。這是用地址項iaddr（11）提供二次間接地址矩欠。該方式的實質(zhì)是二級索引分配方式财剖。系統(tǒng)此時是在二次間址塊中記入所有一次間址塊的盤號悠夯。在采用二次間址方式時，文件最大長度可達4GB峰伙。同理疗疟，地址項iaddr（12）作為三次間接地址，其所允許的文件最大長度可達4TB瞳氓。

5. 輸入輸出系統(tǒng)

5.1策彤、IO管理概述

• 1、IO設(shè)備
  IO設(shè)備管理是操作系統(tǒng)設(shè)計中最凌亂也最具挑戰(zhàn)性的部分匣摘。由于它包含了很多領(lǐng)域的不同設(shè)備以及與設(shè)備相關(guān)的應用程序店诗，因此很難有一個通用且一直的設(shè)計方案。所以在理解設(shè)備管理之前音榜，應該先了解具體的IO設(shè)備類型庞瘸。
  計算機系統(tǒng)中的IO設(shè)備按使用特性可以分為一下類型：
  1）人機交互類外部設(shè)備，又稱慢速IO設(shè)備赠叼，用于桶計算機用戶之間交互的設(shè)備擦囊，如打印機、顯示器嘴办、鼠標瞬场、鍵盤等。這類設(shè)備數(shù)據(jù)交換速度相對較慢涧郊，通常是以字節(jié)為單位進行數(shù)據(jù)交換贯被。
  2）存儲設(shè)備，用于存儲程序和數(shù)據(jù)的設(shè)備妆艘，如磁盤彤灶、磁帶、光盤等批旺。這類設(shè)備用于數(shù)據(jù)交換幌陕，速度較快，通常以多字節(jié)組成的塊為單位進行數(shù)據(jù)交換汽煮。
  3）網(wǎng)絡(luò)通信設(shè)備苞轿，用于與遠程設(shè)備通信的設(shè)備，如各種網(wǎng)絡(luò)接口逗物、調(diào)制解調(diào)器等搬卒。其數(shù)據(jù)交換速度介于外部設(shè)備與存儲設(shè)備之間。網(wǎng)絡(luò)通信設(shè)備在使用和管理上與前兩者設(shè)備有很大的不同翎卓。
  1）低速設(shè)備契邀，傳輸速率僅為每秒鐘幾個字節(jié)至數(shù)百個字節(jié)的一類設(shè)備，如鍵盤失暴、鼠標等坯门。
  2）中速設(shè)備微饥，傳輸速率在每秒數(shù)千個字節(jié)至數(shù)萬個字節(jié)的一類設(shè)備，如行式打印機古戴、激光打印機等欠橘。
  3）高速設(shè)備，傳輸速率在數(shù)百個千字節(jié)至千兆字節(jié)的一類設(shè)備现恼，如磁帶機肃续、磁盤機、光盤機等叉袍。
  （2）按信息交換的單位分類
  1）塊設(shè)備
  由于信息的存取總是以數(shù)據(jù)塊為單位始锚，所以存儲信息的設(shè)備稱為塊設(shè)備。它屬于有結(jié)構(gòu)設(shè)備喳逛，如磁盤等瞧捌。磁盤設(shè)備的基本特征是傳輸速率高，以及可尋址润文，即對他可隨機地讀寫任意塊姐呐。
  2）字符設(shè)備
  用于數(shù)據(jù)輸入輸出的設(shè)備為字符設(shè)備，因為其傳輸?shù)幕締挝皇亲址潋颉Ｋ鼘儆跓o結(jié)構(gòu)類型曙砂，如交互式終端機、打印機等赠法。他們的傳輸速率低、不可尋址乔夯、并且在輸入輸出時常采用中斷驅(qū)動方式砖织。
  對于IO設(shè)備，有以下三種不同類型的使用方式：
  獨占式使用設(shè)備末荐。獨占式使用設(shè)備是指在申請設(shè)備是侧纯，如果設(shè)備空閑，就將其獨占甲脏，不再允許其他進程申請使用眶熬，一直等到該設(shè)備被釋放才允許其他進程申請使用。例如：打印機块请。
  分時式共享使用設(shè)備娜氏。獨占式使用設(shè)備時，設(shè)備利用率低墩新，當設(shè)備沒有獨占使用的要求時贸弥，可以通過分時共享使用，提高利用率海渊。例如：對磁盤設(shè)備的IO操作绵疲，各進程每次IO操作請求可以通過分時來交替進行哲鸳。
  以SPOOLing方式使用外部設(shè)備。SPOOLing技術(shù)是在批處理操作系統(tǒng)時代引入的盔憨，即假脫機IO技術(shù)徙菠。這種技術(shù)用于對設(shè)備的操作，實質(zhì)上就是對IO操作進行批處理郁岩。具體的內(nèi)容后面有單獨講解婿奔。
  采用上面三種使用方式的設(shè)備分別稱為獨占設(shè)備、共享設(shè)備和虛擬設(shè)備驯用。
• 2脸秽、IO管理目標
  IO設(shè)備管理的主要目標有以下三個方面。
  方便使用：方便用戶使用外部設(shè)備蝴乔，控制設(shè)備工作完成用戶的輸入輸出要求记餐。
  提高效率：提高系統(tǒng)的并行工作能力，提高設(shè)備的使用效率薇正。
  方便控制：提高外圍設(shè)備和系統(tǒng)的可靠性和安全性片酝，以使系統(tǒng)能正常工作。
• 3挖腰、IO管理功能
  IO設(shè)備管理的功能是按照輸入輸出子系統(tǒng)的結(jié)構(gòu)和設(shè)備類型制定分配和使用設(shè)備的策略雕沿，主要包括：
  設(shè)備的分配和回收。
  外圍設(shè)備的啟動猴仑。
  對磁盤的驅(qū)動調(diào)度审轮。
  外部設(shè)備中斷處理。
  虛擬設(shè)備的實現(xiàn)辽俗。
• 4疾渣、IO應用接口
  IO應用接口就是從不同的輸入輸出設(shè)備中抽象出一些通用類型。每個類型都可以通過一組標準函數(shù)（即接口）來訪問崖飘。具體的差別被內(nèi)核模塊（也稱設(shè)備驅(qū)動程序）所封裝榴捡。這些設(shè)備驅(qū)動程序一方面可以定制，以設(shè)和各種設(shè)備朱浴，另一方面也提供了一些標準接口吊圾。
  IO應用接口的具體實現(xiàn)方式是：先把IO設(shè)備劃分為若干種類的通用類型；然后對每一種類型提供一組標準函數(shù)來訪問翰蠢，這里的標準函數(shù)就是接口项乒；為每個IO設(shè)備提供各自的設(shè)備驅(qū)動程序，各種設(shè)備間的差異就體現(xiàn)在設(shè)備驅(qū)動程序的不同之中梁沧，而對于訪問這些設(shè)備的接口卻是按照該設(shè)備分數(shù)的類型而統(tǒng)一板丽。
  劃分IO設(shè)備所屬的通用類型的依據(jù)：
  l 字符設(shè)備還是塊設(shè)備。
  l 順序訪問還是隨機訪問。
  l IO傳輸是同步還是異步埃碱。
  l 共享設(shè)備還是獨占設(shè)備猖辫。
  l 操作速度的高低。
  l 訪問模式是讀寫砚殿、只讀還是只寫啃憎。
• 5、設(shè)備控制器（IO部件）
  IO設(shè)備通常包括一個機械部件和一個電子部件似炎。為了達到設(shè)計的模塊性和通用性辛萍，一般將其分開。電子部件成為設(shè)備控制器（或適配器）羡藐，在個人計算機中贩毕，通常是一塊插入主板擴充槽的印制電路板；機械部件即設(shè)備本身仆嗦。
  由于具體的設(shè)備操作涉及硬件接口辉阶，且不同的設(shè)備有不同的硬件特性和參數(shù)，所以這些復雜的操作交由操作系統(tǒng)用戶編寫程序來操作是不實際的瘩扼。引入控制器后谆甜，系統(tǒng)可以通過幾個簡單的參數(shù)完成對控制器的操作，而具體的硬件操作則由控制器調(diào)用相應的設(shè)備接口完成集绰。設(shè)備控制器的引入大大簡化了操作系統(tǒng)的設(shè)計规辱，特別是有利于計算機系統(tǒng)和操作系統(tǒng)對各類控制器和設(shè)備的兼容；同時也實現(xiàn)了主存和設(shè)備之間的數(shù)據(jù)傳輸操作栽燕，使CPU從繁重的設(shè)備控制操作中解放出來罕袋。
  設(shè)備控制器通過寄存器與CPU通信，在某些計算機上碍岔，這些寄存器占用內(nèi)存地址的一部分浴讯，稱為內(nèi)存映像IO；另一些計算機則采用IO專用地址付秕，寄存器獨立編址兰珍。操作系統(tǒng)通過想控制器寄存器寫命令字來執(zhí)行IO功能侍郭⊙猓控制器收到一條命令后，CPU可以轉(zhuǎn)向進行其他工作亮元，而讓設(shè)備控制器自行完成具體IO操作猛计。當命令執(zhí)行完畢后，控制器發(fā)出一個中斷信號爆捞，操作系統(tǒng)重新獲得CPU的控制權(quán)并檢查執(zhí)行結(jié)果奉瘤，此時，CPU仍舊是從控制器寄存器中讀取信息來獲得執(zhí)行結(jié)果和設(shè)備的狀態(tài)信息。
  設(shè)備控制器的主要功能為：
  l 接收和識別CPU或通道發(fā)來的命令盗温，如磁盤控制器能就收讀藕赞、寫、查找卖局、搜索等命令斧蜕。
  l 實現(xiàn)數(shù)據(jù)交換，包括設(shè)備和控制器之間的數(shù)據(jù)傳輸砚偶；通過數(shù)據(jù)總線或通道批销，控制器和主存之間的數(shù)據(jù)傳輸。
  l 發(fā)現(xiàn)和記錄設(shè)備及自身的狀態(tài)信息染坯，供CPU處理使用均芽。
  l 設(shè)備地址識別。
  為實現(xiàn)上述功能单鹿，設(shè)備控制器必須包含以下組成部分：
  該接口有三類信號線：數(shù)據(jù)線掀宋、地址線和控制線。數(shù)據(jù)線通常與兩類寄存器相連接：數(shù)據(jù)存儲器（存放從設(shè)備送來的輸入數(shù)據(jù)或從CPU送來的輸出數(shù)據(jù)）和控制/狀態(tài)寄存器（存放從CPU送來的控制信息或設(shè)備的狀態(tài)信息）羞反。
  設(shè)備控制器鏈接設(shè)備需要相應數(shù)量的接口布朦，一個借口鏈接一臺設(shè)備。每個接口中都存在數(shù)據(jù)昼窗、控制和狀態(tài)三種類型的信號是趴。
  用于實現(xiàn)對設(shè)備的控制。它通過一組控制線與處理器交互澄惊，對從處理器收到的IO命令進行譯碼唆途。CPU啟動設(shè)備時，將啟動命令發(fā)送給控制器掸驱，并同時通過地址線吧地址發(fā)送給控制器肛搬，由控制器的IO邏輯對地址進行譯碼，并相應地對所選設(shè)備進行控制毕贼。
• 6温赔、IO控制方式
  設(shè)備管理的主要任務之一是控制設(shè)備和內(nèi)存或處理器之間的數(shù)據(jù)傳送，外圍設(shè)備和內(nèi)存之間的輸入輸出控制方式有四種鬼癣，下面分別介紹陶贼。
  計算機從外部設(shè)備讀取數(shù)據(jù)到存儲器，每次讀一個字的數(shù)據(jù)待秃。對讀入的每個字拜秧，CPU需要對狀態(tài)循環(huán)檢查，知道確定該字已經(jīng)在IO控制器的數(shù)據(jù)寄存器中章郁。在程序IO方式中枉氮，由于CPU的高速型和IO設(shè)備的低速性，致使CPU的絕大部分時間都處于等待IO設(shè)備完成數(shù)據(jù)IO的循環(huán)測試中，造成CPU的極大浪費聊替。在該方式中楼肪，CPU之所以要不斷地測試IO設(shè)備的狀態(tài)，就是因為在CPU中無中斷機構(gòu)惹悄，使IO設(shè)備無法向CPU報告它已完成了一個字符的輸入操作淹辞。
  程序直接控制方式雖然簡單易于實現(xiàn)，但是其缺點也是顯然的俘侠，由于CPU和外部設(shè)備只能串行工作象缀，導致CPU的利用率相當?shù)汀?br> 中斷驅(qū)動方式的思想是：允許IO設(shè)備主動打斷CPU的運行并請求服務，從而“解放”CPU爷速，使得其向IO控制器發(fā)送命令后可以繼續(xù)做其他有用的工作央星。我們從IO控制器和CPU兩個角度分別來看中斷驅(qū)動方式的工作過程： 從IO控制器的角度來看，IO控制器從COU接受一個讀命令惫东，然后從外圍設(shè)備讀數(shù)據(jù)莉给。一旦數(shù)據(jù)讀入到該IO控制器的數(shù)據(jù)寄存器，便通過控制線給CPU發(fā)出一個中斷信號廉沮，表示數(shù)據(jù)已準備好颓遏，然后等待CPU請求該數(shù)據(jù)。IO控制器收到CPU發(fā)出的取數(shù)據(jù)請求后滞时，將數(shù)據(jù)放到數(shù)據(jù)總線上叁幢，傳到CPU的寄存器中。至此坪稽，本次IO操作完成曼玩，IO控制器又可以開始下一次IO操作。
  從CPU的角度來看窒百，CPU發(fā)送讀命令黍判，然后保存當前運行程序的上下文（現(xiàn)場，包括程序計數(shù)器及處理器寄存器）篙梢，轉(zhuǎn)去執(zhí)行其他程序顷帖。在每個指令周期的末尾，CPU檢查中斷渤滞。當有來自IO控制器的中斷時贬墩，CPU保存當前正在運行程序的上下文，轉(zhuǎn)去執(zhí)行中斷處理程序處理該中斷蔼水。這時震糖，CPU從IO控制器讀一個字的數(shù)據(jù)傳送到寄存器录肯，并存入主存趴腋。接著，CPU恢復發(fā)出IO命令的程序（或其他程序）的上下文，然后繼續(xù)運行优炬。
  中斷驅(qū)動方式比程序直接控制方式有效颁井，但由于數(shù)據(jù)中的每個字在存儲器與IO控制器之間的傳輸都必須通過CPU處理，這就導致了中斷驅(qū)動方式仍然會花費較多的CPU時間蠢护。
  中斷驅(qū)動方式中雅宾，CPU仍然需要主動處理在存儲器和IO設(shè)備之間的數(shù)據(jù)傳送，所以速度還是受限葵硕，而直接內(nèi)存存让继А（DMA）方式的基本思想是在外圍設(shè)備和內(nèi)存之間開辟直接的數(shù)據(jù)交換通路，徹底解放CPU懈凹。該方式的特點是：
  l 基本單位是數(shù)據(jù)塊蜀变。
  l 所傳誦的數(shù)據(jù)，是從設(shè)備直接送入內(nèi)存的介评，或者相反库北。
  l 僅在傳送一個或多個數(shù)據(jù)塊的開始和結(jié)束時，才需CPU干預们陆，整塊數(shù)據(jù)的傳送是在DMA控制器的控制下完成的寒瓦。
  為了實現(xiàn)在主機與控制器之間成塊數(shù)據(jù)的直接交換，必須在DMA控制器中設(shè)置如下四類寄存器：
  l 命令/狀態(tài)寄存器（CR）坪仇。用于接收從CPU發(fā)來的IO命令或有關(guān)控制信息杂腰，或設(shè)備的狀態(tài)。
  l 內(nèi)存地址寄存器（MAR）椅文。在輸入時颈墅，它存放把數(shù)據(jù)從設(shè)備傳送到內(nèi)存的起始目標地址；在輸出時雾袱，它存放由內(nèi)存到設(shè)備的內(nèi)存源地址恤筛。
  l 數(shù)據(jù)寄存器（DR）。用于暫存從設(shè)備到內(nèi)存或從內(nèi)存到設(shè)備的數(shù)據(jù)芹橡。
  l 數(shù)據(jù)計數(shù)器（DC）宜鸯。存放本次CPU要讀或?qū)懙淖止?jié)數(shù)。
  DMA的工作過程是：CPU讀寫數(shù)據(jù)時贺辰，他給IO控制器發(fā)出一條命令蔼卡，啟動DMA控制器，然后繼續(xù)其他工作腿箩。之后CPU就把這個操作委托給DMA控制器豪直，由該控制器負責處理。DMA控制器直接與存儲器交互珠移，傳送整個數(shù)據(jù)塊弓乙，這個過程不需要CPU參與末融。當傳送完成后，DMA控制器發(fā)送一個中斷信號給處理器暇韧。因此勾习，只有在傳送開始和結(jié)束時才需要CPU的參與。
  DMA控制方式與中斷驅(qū)動方式的主要區(qū)別是中斷驅(qū)動方式在每個數(shù)據(jù)傳送玩后中斷CPU懈玻，而DMA控制方式則是在所要求傳送的一批數(shù)據(jù)全部傳送結(jié)束時中斷CPU巧婶；此外，中斷驅(qū)動方式數(shù)據(jù)傳送的是在中斷處理時由CPU控制完成涂乌，而DMA控制方式則是在DMA控制器的控制下完成的艺栈。
  IO通道方式是DMA方式的發(fā)展，它可以進一步減少CPU的干預湾盒，即把對一個數(shù)據(jù)塊的讀或?qū)憺橐粋€單位的干預眼滤，減少為對一組數(shù)據(jù)塊的讀或?qū)懠坝嘘P(guān)的控制盒管理為單位的干預。同時历涝，又可以實現(xiàn)CPU诅需、通道和IO設(shè)備三者的并行操作，從而更有效的提高整個系統(tǒng)的資源利用率荧库。
  例如堰塌，當CPU要完成一組相關(guān)的讀或?qū)懖僮骷坝嘘P(guān)控制時，只需向IO通道發(fā)送一條IO指令分衫，已給出其所要執(zhí)行的通道程序的首址和要訪問的IO設(shè)備场刑，通道接到該指令后，通過執(zhí)行通道程序便可完成CPU指定的IO任務蚪战。
  IO通道和一般處理器的區(qū)別是：通道指令的類型單一牵现，沒有自己的內(nèi)存，通道所執(zhí)行的通道程序釋放在主機內(nèi)存中的邀桑，也就是說通道與CPU共享內(nèi)存瞎疼。
  IO通道與DMA的區(qū)別是：DMA方式需要CPU來控制傳輸?shù)臄?shù)據(jù)塊大小、傳輸?shù)膬?nèi)存位置壁畸，而通道方式中這些信息是由通道控制的贼急。另外，每個DMA控制器對應一臺設(shè)備與內(nèi)存?zhèn)鬟f數(shù)據(jù)捏萍，而一個通道可以控制多臺設(shè)備與內(nèi)存的數(shù)據(jù)交換太抓。

5.2、IO核心子系統(tǒng)

• 1令杈、IO層次結(jié)構(gòu)
  IO實現(xiàn)普遍采用了層次式的結(jié)構(gòu)走敌。其基本思想與計算機網(wǎng)絡(luò)中的層次結(jié)構(gòu)相同：將系統(tǒng)IO的功能組織成一系列的層次，每一層完成整個系統(tǒng)功能的一個子集逗噩，其實現(xiàn)依賴于下層完成更原始的功能掉丽，并屏蔽這些功能的實現(xiàn)細節(jié)跌榔，從而為上層提供各種服務。
  一個比較合理的層次劃分為四個層次的系統(tǒng)結(jié)構(gòu)机打，各層次及其功能如下：
  1）用戶層IO軟件：實現(xiàn)與用戶交互的接口，用戶可直接調(diào)用在用戶層提供的片迅、與IO操作有關(guān)的庫函數(shù)残邀，對設(shè)備進行操作。
  2）設(shè)備獨立性軟件：用于實現(xiàn)用戶程序與設(shè)備驅(qū)動器的統(tǒng)一接口柑蛇、設(shè)備命令芥挣、設(shè)備保護，以及設(shè)備分配與釋放等耻台，同時為設(shè)備管理和數(shù)據(jù)傳送提供必要的存儲空間空免。
  3）設(shè)備驅(qū)動程序：與硬件直接相關(guān)，用于具體實現(xiàn)系統(tǒng)對設(shè)備發(fā)出的操作指令盆耽，驅(qū)動IO設(shè)備工作的驅(qū)動程序蹋砚。
  4）中斷處理程序：用于保存被中斷進程的CPU環(huán)境，轉(zhuǎn)入相應的中斷處理程序進行處理摄杂，處理完并回復被中斷進程的現(xiàn)場后坝咐，返回到被中斷進程。
• 2析恢、IO調(diào)度概念
  調(diào)度一組IO請求就是確定確定一個好的順序來執(zhí)行這些請求墨坚。應用程序所發(fā)布的系統(tǒng)調(diào)用的順序不一定總是最佳選擇，所以需要調(diào)度來改善系統(tǒng)整體性能映挂，是進程之間公平的共享設(shè)備訪問泽篮，減少IO完成所需要的平均等待時間。
  操作系統(tǒng)開發(fā)人員通過為每個設(shè)備維護一個請求隊列來實現(xiàn)調(diào)度柑船。當一個應用程序執(zhí)行阻塞IO系統(tǒng)調(diào)用時帽撑，該請求就加到相應設(shè)備的隊列上。IO調(diào)度會重新安排隊列順序以改善系統(tǒng)總體效率和應用程序的平均響應時間鞍时。
  IO子系統(tǒng)還可以使用主存或磁盤上的存儲空間的技術(shù)油狂，如緩沖、高速緩沖寸癌、假脫機等专筷。
• 3、高速緩存與緩沖區(qū)
  操作系統(tǒng)總是用磁盤高速緩存技術(shù)來提高磁盤的IO速度蒸苇，對高速緩存復制的訪問要比原始數(shù)據(jù)訪問更為高效磷蛹。例如，正在運行的進程的指令即存儲在磁盤上溪烤，也存儲在物理內(nèi)存上味咳，也被復制到CPU的二級和一級高速緩存中庇勃。
  不過，磁盤高速緩存技術(shù)不同于通常意義下的介于CPU與內(nèi)存之間的小容量高速存儲器槽驶，而是利用內(nèi)存中的存儲空間來暫存從磁盤中讀出的一系列盤塊中的信息责嚷，因此，磁盤高速緩存在邏輯上屬于磁盤掂铐，物理上則是駐留在內(nèi)存中的盤塊罕拂。
  高速緩存在內(nèi)存中分為兩種形式：一種是在內(nèi)存中開辟一個單獨的存儲空間作為磁盤高速緩存，大小固定全陨；另一種是把未利用的內(nèi)存空間作為一個緩沖池爆班，共請求分頁系統(tǒng)和磁盤IO時共享。
  在設(shè)備管理子系統(tǒng)中辱姨，引入緩沖區(qū)的目的有：
  1）緩和CPU與IO 設(shè)備間速度不匹配的矛盾柿菩。
  2）減少對CPU的中斷頻率，放寬對CPU 中斷響應時間的限制雨涛。
  3）解決基本數(shù)據(jù)單元大小不匹配的問題枢舶。
  4）提高CPU和IO設(shè)備之間的并行性。
  其實現(xiàn)方法有：
  1）采用硬件緩沖器替久，但由于成本太高祟辟，出一些關(guān)鍵部位外，一般情況下不采用硬件緩沖器侣肄。
  2）采用緩沖區(qū)（位于內(nèi)存區(qū)域）
  根據(jù)系統(tǒng)設(shè)置緩沖器的個數(shù)旧困，緩沖技術(shù)可以分為：
  1）單緩沖。在設(shè)備和處理器之間設(shè)置一個緩沖區(qū)稼锅。設(shè)備和處理器交換數(shù)據(jù)時吼具，先把被交換數(shù)據(jù)寫入緩沖區(qū)，然后把需要數(shù)據(jù)的設(shè)備或處理器從緩沖區(qū)取走數(shù)據(jù)矩距。
  在塊設(shè)備輸入時拗盒，假定從磁盤把一塊數(shù)據(jù)輸入到緩沖區(qū)的時間為T，操作系統(tǒng)將該緩沖區(qū)中的數(shù)據(jù)局傳送到用戶區(qū)的時間為M锥债，而CPU對這一塊數(shù)據(jù)處理的時間為C陡蝇。由于T和C是可以并行的，所以可把系統(tǒng)對每一塊數(shù)據(jù)的處理時間表示為Max（C,T）+M哮肚。
  2）雙緩沖登夫。雙緩沖區(qū)機制又稱緩沖對換。IO設(shè)備輸入數(shù)據(jù)時先輸入到緩沖區(qū)1允趟，直到緩沖區(qū)1滿后才輸入到緩沖區(qū)2恼策，此時操作系統(tǒng)可以從緩沖區(qū)1中取出數(shù)據(jù)放入用戶進程，并由CPU計算潮剪。雙緩沖的使用提高了處理器和輸入設(shè)備的并行操作的程度涣楷。
  系統(tǒng)處理一塊數(shù)據(jù)的時間可以粗略地認為是Max（C,T）分唾。如果CT，則可使CPU不必等待設(shè)備輸入狮斗。對于字符設(shè)備绽乔，若采用行輸入方式，則采用雙緩沖可使用戶再輸入完第一行之后碳褒，在CPU執(zhí)行第一行中的命令的同事折砸，用戶可繼續(xù)向第二緩沖區(qū)輸入下一行數(shù)據(jù)。而單緩沖情況下則必須等待一行數(shù)據(jù)被提取完畢才可輸入下一行的數(shù)據(jù)骤视。
  如果兩臺機器之間通信僅配置了單緩沖鞍爱，那么鹃觉，他們在任意時刻都只能實現(xiàn)單方向的數(shù)據(jù)傳輸专酗。為了實現(xiàn)雙向數(shù)據(jù)傳輸，必須在兩臺機器中都設(shè)置兩個緩沖區(qū)盗扇，一個用作發(fā)送緩沖區(qū)祷肯，另一個用作接收緩沖區(qū)。
  3）循環(huán)緩沖：包含多個大小相等的緩沖區(qū)疗隶，每個緩沖區(qū)中有一個緩沖區(qū)佑笋，最后一個緩沖區(qū)指針指向第一個緩沖區(qū)，多個緩沖區(qū)構(gòu)成一個環(huán)形斑鼻。用于輸入輸出時蒋纬，還需要有兩個指針in和out。對輸入而言坚弱，首先要從設(shè)備接收數(shù)據(jù)到緩沖區(qū)中蜀备，in指針指向可以輸入數(shù)據(jù)的第一個空緩沖區(qū)；當運行進程需要數(shù)據(jù)時荒叶，從循環(huán)緩沖去中去一個裝滿數(shù)據(jù)的緩沖區(qū)碾阁，并從此緩沖區(qū)中提取數(shù)據(jù)，out指針指向可以提取數(shù)據(jù)的第一個滿緩沖區(qū)些楣。輸出正好相反脂凶。
  4）緩沖池：由多個系統(tǒng)共用的緩沖區(qū)組成，緩沖區(qū)按其使用狀況可以形成三個隊列：空緩沖隊列愁茁、裝滿輸入數(shù)據(jù)的緩沖隊列（輸入隊列）和裝滿輸出數(shù)據(jù)的緩沖隊列（輸出隊列）蚕钦。還應具有四種緩沖區(qū)：用于收容輸入數(shù)據(jù)的工作緩沖區(qū)、用于提取輸入數(shù)據(jù)的工作緩沖區(qū)鹅很、用于收容輸出數(shù)據(jù)的工作緩沖區(qū)冠桃、用于提取輸出數(shù)據(jù)的工作緩沖區(qū)。
  （4）高速緩存與緩沖區(qū)的對比
  高速緩存是可以保存復制數(shù)據(jù)的高速存儲器道宅。訪問高速緩存比訪問原始數(shù)據(jù)更高效食听，速度更快胸蛛。
• 4、設(shè)備的分配與回收
  設(shè)備分配的基本任務是根據(jù)用戶的IO請求樱报，為他們分配所需的設(shè)備葬项。設(shè)備分配的總原則是充分發(fā)揮設(shè)備的使用效率，盡可能地讓設(shè)備忙碌迹蛤，又要避免由于不合理的分配方法造成進程死鎖民珍。從設(shè)備的特性來看，可以把設(shè)備分成獨占設(shè)備盗飒、共享設(shè)備和虛擬設(shè)備三類嚷量。
  對于獨立設(shè)備，講一個設(shè)備分配給某進程后逆趣，便有改進成都站蝶溶，直至該進程完成或釋放該設(shè)備。對于共享設(shè)備宣渗，可以同時分配給多個進程使用抖所，但需要對這些進程訪問該設(shè)備的先后次序進程合理的調(diào)度。虛擬設(shè)備屬于可共享設(shè)備痕囱，可以將它同時分配給多個進程使用田轧。
  設(shè)備分配依據(jù)的主要數(shù)據(jù)結(jié)構(gòu)有設(shè)備控制表（DCT）、控制器控制表（COCT）鞍恢、通道控制表（CHCT）和系統(tǒng)設(shè)備表（SDT）傻粘，各數(shù)據(jù)結(jié)構(gòu)功能如下：
  設(shè)備控制表：系統(tǒng)為每一個設(shè)備配置一張DCT，它用于記錄設(shè)備的特性以及與IO控制器連接的情況帮掉。DCT包括設(shè)備標示符弦悉、設(shè)備類型、設(shè)備狀態(tài)旭寿、指向COUCT的指針等警绩。其中，設(shè)備隊列指針指向等待使用該設(shè)備的進程組成的等待隊列盅称，控制表指針指向于該設(shè)備相連接的設(shè)備控制器肩祥。
  控制器控制表：每個控制器都配有一張COCT，它反應設(shè)備控制器的使用狀態(tài)以及和通道的連接情況等缩膝。
  通道控制表：每個通道配有一張CHCT混狠。
  系統(tǒng)設(shè)備表：整個系統(tǒng)只有一張SDT，它記錄已連接到系統(tǒng)中的所有物理設(shè)備的情況疾层，每個物理設(shè)備占一個表目将饺。
  由于在多道程序系統(tǒng)中，進程數(shù)多于資源數(shù)，會引起資源的競爭予弧。因此刮吧，要有一套合理的分配原則，主要考慮的因素有：IO設(shè)備的固有屬性掖蛤，IO設(shè)備的分配算法杀捻，設(shè)備分配的安全性，以及設(shè)備獨立性蚓庭。
  1）設(shè)備分配原則致讥。設(shè)備的分配原則應根據(jù)設(shè)備特性、用戶要求和系統(tǒng)配置的情況來決定器赞。設(shè)備分配的總原則既要充分發(fā)揮設(shè)備的使用效率垢袱，又要避免造成進程死鎖，還要將用戶程序和具體設(shè)備隔離開港柜。
  2）設(shè)備分配方式请契。設(shè)備分配方式有靜態(tài)分配和動態(tài)分配兩種。
  靜態(tài)分配主要用于對獨占設(shè)備的分配潘懊，它在用戶作業(yè)開始執(zhí)行前姚糊，有系統(tǒng)一次性分配該作業(yè)所要求的全部設(shè)備贿衍、控制器（和通道）授舟。一旦分配后，這些設(shè)備贸辈、控制器（和通道）就一直為高作業(yè)所占用释树，知道該作業(yè)被撤銷。靜態(tài)分配方式不會出現(xiàn)死鎖擎淤，但設(shè)備的使用效率較低奢啥。因此，靜態(tài)分配方式并不符合分配的總原則嘴拢。
  動態(tài)分配是在進程執(zhí)行過程中根據(jù)執(zhí)行需要進行桩盲。當進程需要設(shè)備時，通過系統(tǒng)調(diào)用命令向系統(tǒng)提出設(shè)備請求席吴，由系統(tǒng)按照事先規(guī)定的策略給進程分配所需要的設(shè)備赌结、IO控制器，一旦用完之后孝冒，便立即釋放柬姚。動態(tài)分配方式有利于提高設(shè)備的利用率，但如果分配算法使用不當庄涡，則有可能造成進程死鎖量承。
  3）設(shè)備分配算法。常用的動態(tài)設(shè)備分配算法有先請求先分配、優(yōu)先級高者優(yōu)先等撕捍。
  對于獨占設(shè)備拿穴，即可以采用動態(tài)分配方式也可以靜態(tài)分配方式，往往采用靜態(tài)分配方式忧风，即在作業(yè)執(zhí)行前贞言，將作業(yè)所要用到的這一類設(shè)備分配給它。共享設(shè)備可被多個進程所共享阀蒂，一般采用動態(tài)分配方式该窗，但在每個IO傳輸?shù)膯挝粫r間內(nèi)只被一個進程所占有，通常采用先請求先分配和優(yōu)先級高者先分的分配算法蚤霞。
  設(shè)備分配的安全性是指設(shè)備分配中應防止發(fā)生進程死鎖酗失。
  1）安全分配方式。每當進程發(fā)出IO請求后便進入阻塞狀態(tài)昧绣，直到其IO操作完成時才被喚醒规肴。這樣，一旦進程已經(jīng)獲得某種設(shè)備后便阻塞夜畴，不嫩再請求任何資源拖刃，而且在它阻塞時也不保持任何資源。有點事設(shè)備分配安全贪绘；缺點是CPU和IO設(shè)備是串行工作的兑牡。
  2）不安全分配方式。進程在發(fā)出IO請求后繼續(xù)運行税灌，需要時發(fā)出第二個均函、第三個IO請求等。僅當進程所請求的設(shè)備已被另一進程占用時菱涤，才進入阻塞狀態(tài)苞也。有點事一個進程可以同時操作幾個設(shè)備，從而市金城推進迅速粘秆；缺點是這種設(shè)備分配有可能產(chǎn)生死鎖如迟。
  為了提高設(shè)備分配的靈活性和設(shè)備的利用率、方便實現(xiàn)IO重定向攻走，因此引入了設(shè)備獨立性殷勘。設(shè)備獨立性是指應用程序獨立于具體使用的物理設(shè)備。
  為了實現(xiàn)設(shè)備獨立性陋气，在應用程序中使用邏輯設(shè)備名來請求使用某類設(shè)備劳吠，在系統(tǒng)中設(shè)置一張邏輯設(shè)備表（LUT），用于將邏輯設(shè)備名映射為物理設(shè)備名巩趁。LUT表項包括邏輯設(shè)備名痒玩、物理設(shè)備名和設(shè)備驅(qū)動程序入口地址淳附；當進程用邏輯設(shè)備名來請求分配設(shè)備時，系統(tǒng)為他分配相應的物理設(shè)備蠢古，并在LUT中建立一個表項奴曙，以后進程再利用邏輯設(shè)備名請求IO操作時，系統(tǒng)通過查找LUT來尋找相應的物理設(shè)備和驅(qū)動程序草讶。
  在系統(tǒng)中可采取兩種方式建立邏輯設(shè)備表：
  1）在整個系統(tǒng)中只設(shè)置一張LUT表洽糟。這樣，所有進程的設(shè)備分配情況都記錄在這張表中堕战，故不允許有相同的邏輯設(shè)備名坤溃，主要適用于單用戶系統(tǒng)中。
  2）為每個用戶設(shè)置一張LUT嘱丢。當用戶登錄時薪介，系統(tǒng)便為用戶建立一個進程，同時也位置建立一張LUT越驻，并肩改變放入進程的PCB中汁政。
• 5、SPOOLing（假脫機技術(shù)）
  為了緩和CPU的高速型與IO設(shè)備低速性之間的矛盾而引入了脫機輸入缀旁、脫機輸出技術(shù)记劈。該技術(shù)是利用專門的外圍控制機，將低速IO設(shè)備上的數(shù)據(jù)傳送到高速磁盤上并巍；或者相反目木。SPOOLing的意思是外部設(shè)備同時聯(lián)機操作，又稱為假脫機輸入輸出操作履澳，是操作系統(tǒng)中采用的一項將獨占設(shè)備改造成共享設(shè)備的技術(shù)嘶窄。
  再次攀上開辟出的兩個存儲區(qū)域怀跛。輸入井模擬脫機輸入時的磁盤距贷，用于收容IO設(shè)備輸入的數(shù)據(jù)。輸出井模擬脫機輸出的磁盤吻谋，用于收容用戶程序的輸出數(shù)據(jù)忠蝗。
  在內(nèi)存中開辟的兩個緩沖區(qū)。出入緩沖區(qū)用于暫存由輸入設(shè)備送來的數(shù)據(jù)漓拾，以后再傳送到輸入井阁最。輸出緩沖區(qū)用于暫存從輸出井送來的數(shù)據(jù)，以后再傳送到輸出設(shè)備骇两。
  輸入進程模擬脫機輸入時的外圍控制機速种，將用戶要求的數(shù)據(jù)從輸入機通過輸入緩沖區(qū)再送到輸入井。當CPU需要輸入數(shù)據(jù)時低千，直接將數(shù)據(jù)從輸入井讀入內(nèi)存配阵。輸入進程模擬脫機輸出時的外圍控制機，把用戶要求輸出的數(shù)據(jù)先從內(nèi)存送到輸出井，待輸出設(shè)備空閑時棋傍，再將輸出井中的數(shù)據(jù)經(jīng)過輸出緩沖區(qū)送到輸出設(shè)備救拉。
  共享打印機是使用SPOOLing技術(shù)的一個實例，這項技術(shù)已被廣泛的用于多用戶系統(tǒng)和局域網(wǎng)絡(luò)中瘫拣。當用戶進程請求打印輸出時亿絮，SPOOLing系統(tǒng)同意為它打印輸出，但并不真正立即把打印機分配給該用戶進程麸拄，而只為她做兩件事：
  1）由輸出進程在輸出井中為之申請一個空閑磁盤塊區(qū)派昧，并將要打印的數(shù)據(jù)送入其中。
  2）輸出進程再為用戶進程申請一張空白的用戶請求打印表拢切，并將用戶的打印要求填入其中斗锭，再將該表掛到請求打印隊列中让禀。
  SPOOLing系統(tǒng)的特點是：提高了IO速度免姿；將獨占設(shè)備改造為共享設(shè)備；實現(xiàn)了虛擬設(shè)備功能溜宽。
• 6实苞、出錯處理
  操作系統(tǒng)可以采用內(nèi)存保護豺撑，這樣一來就可以預防許多 硬件和應用程序的錯誤，即便有一些設(shè)備硬件上的適齡也不回導致系統(tǒng)的完全崩潰黔牵。
  IO設(shè)備傳輸中出現(xiàn)的錯誤很多聪轿，如網(wǎng)絡(luò)上的堵塞和傳輸過載等。操作系統(tǒng)可以對一些短暫的出錯進行處理猾浦，比如讀取磁盤出錯陆错，那么可以選擇重新常識對磁盤進行read操作；再比如在網(wǎng)絡(luò)上發(fā)送數(shù)據(jù)出錯金赦，那么只要網(wǎng)絡(luò)通信協(xié)議允許音瓷，就可以做resend操作。但是夹抗，如果計算機系統(tǒng)中的重要組件出現(xiàn)了永久性錯誤绳慎，那么操作系統(tǒng)將無法恢復。
  作為一個規(guī)則漠烧，IO系統(tǒng)調(diào)用通常返回一位調(diào)用狀態(tài)信息杏愤，以表示成功或失敗。在UNIX系統(tǒng)中已脓，用一個名為errno的全局變量來表示出錯代碼珊楼，以表示出錯原因。
  注意：read度液、send和resend都是操作系統(tǒng)的基本輸入輸出命令厕宗，分別用來讀邓了、發(fā)送和重發(fā)數(shù)據(jù)。

5.3媳瞪、本章疑難點

1）分配設(shè)備骗炉。首先根據(jù)IO請求中的物理設(shè)備名查找系統(tǒng)設(shè)備表（SDT），從中找出該設(shè)備的DCT蛇受，再根據(jù)DCT中的設(shè)備狀態(tài)字段句葵，可知該設(shè)備是否正忙。若忙兢仰，便將請求IO進程的PCB掛在設(shè)備隊列上乍丈；空閑則按照一定算法計算設(shè)備分配的安全性，安全則將設(shè)備分配給請求進程把将，否則仍將其PCB掛到設(shè)備隊列轻专。
2）分配控制器。系統(tǒng)把設(shè)備分配給請求IO的進程后察蹲，再到其DCT中找出與該設(shè)備連接的控制器的COCT请垛，從COCT中的狀態(tài)字段中可知該控制器是否忙碌。若忙洽议，便將請求IO進程的PCB掛在該控制器的等待隊列上宗收；空閑便將控制器分配給進程。
3）分配通道亚兄。在該COCT中又可找到與該控制器連接的通道CHCT混稽，再根據(jù)CHCT內(nèi)的狀態(tài)信息，可知該通道是否忙碌审胚。若忙匈勋，便將請求IO的進程掛在該通道的等待隊列上；空閑便將該通道分配給進程膳叨。只有在上述三者都分配成功時洽洁，這次設(shè)備分配才算成功。然后懒鉴，便可啟動該IO設(shè)備進行數(shù)據(jù)傳送诡挂。
為使獨占設(shè)備的分配具有更強的靈活性，提高分配的成功率临谱，還可以從以下兩方面對基本的設(shè)備分配程序加以改進：
1）增加設(shè)備的獨立性。進程使用邏輯設(shè)備名請求IO奴璃。這樣悉默，系統(tǒng)首先從SDT中找出第一個該類設(shè)備的DCT。若該設(shè)備忙苟穆，又查找出第二個該設(shè)備的DCT抄课。僅當所有該類設(shè)備都忙時唱星，才把進程掛在該類設(shè)備的等待隊列上；只要有一個該類設(shè)備可用跟磨，系統(tǒng)便進一步計算分配該設(shè)備的安全性间聊。
2）考慮多通路情況。為防止IO系統(tǒng)的“瓶頸”現(xiàn)象抵拘，通常采用多通路的IO系統(tǒng)結(jié)構(gòu)哎榴。此時對控制器和通道的分配同樣要經(jīng)過幾次反復，即若設(shè)備（控制器）所連接的第一個控制器（通道）忙時僵蛛，應查看其所連接的第二個控制器（通道）尚蝌，僅當所有的控制器（通道）都忙時，此次的控制器（通道）分配才算失敗充尉，才把進程掛在控制器（通道）的等待隊列上飘言。而只要有一個控制器（通道）可用，系統(tǒng)便可將它分配給進程驼侠。

6. 常見考點

6.1 進程的平均周轉(zhuǎn)時間

有4個進程A,B,C,D,設(shè)它們依次進入就緒隊列姿鸿，因相差時間很短可視為同時到達。4個進程按輪轉(zhuǎn)法分別運行11,7,2,和4個時間單位倒源，設(shè)時間片為1般妙。四個進程的平均周轉(zhuǎn)時間為 （）？

結(jié)果：詳細如圖 （7+14+20+24）/4=16.25

進程的堆棧相速、數(shù)據(jù)區(qū)碟渺、代碼區(qū)在內(nèi)存的映射

棧 存放局部變量 傳遞參數(shù) 存儲函數(shù)的返回地址
堆 malloc 和new進行分配時 所得的地址就在堆中 程序員負責申請和銷毀
數(shù)據(jù)區(qū) 全局、靜態(tài)突诬、常量是分配到數(shù)據(jù)區(qū)中的 數(shù)據(jù)區(qū)包括bbs 未初始化數(shù)據(jù)區(qū) 初始化數(shù)據(jù)區(qū)
堆向高內(nèi)存地址生長 棧向高內(nèi)存地址生長 兩者相向而生

C語言中堆和棧的區(qū)別

一.前言：

C語言程序經(jīng)過編譯連接后形成編譯苫拍、連接后形成的二進制映像文件由棧，堆旺隙，數(shù)據(jù)段（由三部分部分組成：只讀數(shù)據(jù)段绒极，已經(jīng)初始化讀寫數(shù)據(jù)段，未初始化數(shù)據(jù)段即BBS）和代碼段(文本常量區(qū))組成蔬捷，如下圖所示：

image.png

1.棧區(qū)(stack):由編譯器自動分配釋放垄提，存放函數(shù)的參數(shù)值，局部變量等值周拐。其操作方式類似于數(shù)據(jù)結(jié)構(gòu)中的棧铡俐。

2.堆區(qū)(heap):一般由程序員分配釋放，若程序員不釋放妥粟，則可能會引起內(nèi)存泄漏审丘。注堆和數(shù)據(jù)結(jié)構(gòu)中的堆棧不一樣，其類是與鏈表勾给。

3.程序代碼區(qū)：存放函數(shù)體的二進制代碼滩报。

4.數(shù)據(jù)段：由三部分組成：

1>只讀數(shù)據(jù)段：

只讀數(shù)據(jù)段是程序使用的一些不會被更改的數(shù)據(jù)锅知，使用這些數(shù)據(jù)的方式類似查表式的操作，由于這些變量不需要更改脓钾，因此只需要放置在只讀存儲器中即可售睹。一般是const修飾的變量以及程序中使用的文字常量一般會存放在只讀數(shù)據(jù)段中。

2>已初始化的讀寫數(shù)據(jù)段：

已初始化數(shù)據(jù)是在程序中聲明可训，并且具有初值的變量昌妹，這些變量需要占用存儲器的空間，在程序執(zhí)行時它們需要位于可讀寫的內(nèi)存區(qū)域內(nèi)沉噩，并且有初值捺宗，以供程序運行時讀寫。在程序中一般為已經(jīng)初始化的全局變量川蒙，已經(jīng)初始化的靜態(tài)局部變量(static修飾的已經(jīng)初始化的變量)

3>未初始化段（BSS）：

未初始化數(shù)據(jù)是在程序中聲明蚜厉，但是沒有初始化的變量，這些變量在程序運行之前不需要占用存儲器的空間畜眨。與讀寫數(shù)據(jù)段類似昼牛，它也屬于靜態(tài)數(shù)據(jù)區(qū)。但是該段中數(shù)據(jù)沒有經(jīng)過初始化康聂。未初始化數(shù)據(jù)段只有在運行的初始化階段才會產(chǎn)生贰健，因此它的大小不會影響目標文件的大小。在程序中一般是沒有初始化的全局變量和沒有初始化的靜態(tài)局部變量恬汁。

二.堆和棧的區(qū)別

1.申請方式

(1)棧（satck）:由系統(tǒng)自動分配伶椿。例如，聲明在函數(shù)中一個局部變量int b;系統(tǒng)自動在棧中為b開辟空間氓侧。

(2)堆（heap）:需程序員自己申請（調(diào)用malloc,realloc,calloc）,并指明大小脊另，并由程序員進行釋放。容易產(chǎn)生memory leak.

eg:char p;

  p = (char *)malloc(sizeof(char));

但是约巷，p本身是在棧中偎痛。

2.申請大小的限制

（1）棧：在windows下棧是向底地址擴展的數(shù)據(jù)結(jié)構(gòu)，是一塊連續(xù)的內(nèi)存區(qū)域(它的生長方向與內(nèi)存的生長方向相反)独郎。棧的大小是固定的踩麦。如果申請的空間超過棧的剩余空間時，將提示overflow氓癌。

（2）堆：堆是高地址擴展的數(shù)據(jù)結(jié)構(gòu)（它的生長方向與內(nèi)存的生長方向相同）谓谦，是不連續(xù)的內(nèi)存區(qū)域。這是由于系統(tǒng)使用鏈表來存儲空閑內(nèi)存地址的顽铸，自然是不連續(xù)的茁计，而鏈表的遍歷方向是由底地址向高地址。堆的大小受限于計算機系統(tǒng)中有效的虛擬內(nèi)存谓松。

3.系統(tǒng)響應：

（1）棧：只要棧的空間大于所申請空間星压，系統(tǒng)將為程序提供內(nèi)存，否則將報異常提示棧溢出鬼譬。

（2）堆：首先應該知道操作系統(tǒng)有一個記錄空閑內(nèi)存地址的鏈表娜膘，但系統(tǒng)收到程序的申請時，會遍歷該鏈表优质，尋找第一個空間大于所申請空間的堆結(jié)點竣贪，然后將該結(jié)點從空閑鏈表中刪除，并將該結(jié)點的空間分配給程序巩螃，另外演怎，對于大多數(shù)系統(tǒng)，會在這塊內(nèi)存空間中的首地址處記錄本次分配的大小避乏，這樣爷耀，代碼中的free語句才能正確的釋放本內(nèi)存空間。另外拍皮，找到的堆結(jié)點的大小不一定正好等于申請的大小歹叮，系統(tǒng)會自動的將多余的那部分重新放入空閑鏈表中。

說明：對于堆來講铆帽，對于堆來講咆耿，頻繁的new/delete勢必會造成內(nèi)存空間的不連續(xù)，從而造成大量的碎片爹橱，使程序效率降低萨螺。對于棧來講，則不會存在這個問題愧驱，

4.申請效率

（1）棧由系統(tǒng)自動分配慰技，速度快。但程序員是無法控制的

（2）堆是由malloc分配的內(nèi)存冯键，一般速度比較慢惹盼，而且容易產(chǎn)生碎片，不過用起來最方便惫确。

5.堆和棧中的存儲內(nèi)容

（1）棧：在函數(shù)調(diào)用時手报，第一個進棧的主函數(shù)中后的下一條語句的地址，然后是函數(shù)的各個參數(shù)改化，參數(shù)是從右往左入棧的掩蛤，然后是函數(shù)中的局部變量。注：靜態(tài)變量是不入棧的陈肛。

當本次函數(shù)調(diào)用結(jié)束后揍鸟，局部變量先出棧，然后是參數(shù)句旱，最后棧頂指針指向最開始存的地址阳藻，也就是主函數(shù)中的下一條指令晰奖，程序由該點繼續(xù)執(zhí)行。

（2）堆：一般是在堆的頭部用一個字節(jié)存放堆的大小腥泥。

6.存取效率

（1）堆：char *s1=”hellow tigerjibo”;是在編譯是就確定的

（2）棧：char s1[]=”hellow tigerjibo”;是在運行時賦值的匾南；用數(shù)組比用指針速度更快一些，指針在底層匯編中需要用edx寄存器中轉(zhuǎn)一下蛔外，而數(shù)組在棧上讀取蛆楞。

補充：

棧是機器系統(tǒng)提供的數(shù)據(jù)結(jié)構(gòu)，計算機會在底層對棧提供支持：分配專門的寄存器存放棧的地址夹厌，壓棧出棧都有專門的指令執(zhí)行豹爹，這就決定了棧的效率比較高。堆則是C/C++函數(shù)庫提供的矛纹，它的機制是很復雜的臂聋，例如為了分配一塊內(nèi)存，庫函數(shù)會按照一定的算法（具體的算法可以參考數(shù)據(jù)結(jié)構(gòu)/操作系統(tǒng)）在堆內(nèi)存中搜索可用的足夠大小的空間崖技，如果沒有足夠大小的空間（可能是由于內(nèi)存碎片太多）逻住，就有可能調(diào)用系統(tǒng)功能去增加程序數(shù)據(jù)段的內(nèi)存空間，這樣就有機會分到足夠大小的內(nèi)存迎献，然后進行返回瞎访。顯然，堆的效率比棧要低得多吁恍。

7.分配方式：

（1）堆都是動態(tài)分配的扒秸，沒有靜態(tài)分配的堆。

（2）棧有兩種分配方式：靜態(tài)分配和動態(tài)分配冀瓦。靜態(tài)分配是編譯器完成的伴奥，比如局部變量的分配。動態(tài)分配由alloca函數(shù)進行分配翼闽，但是棧的動態(tài)分配和堆是不同的拾徙。它的動態(tài)分配是由編譯器進行釋放，無需手工實現(xiàn)感局。

image.png

//main.cpp 
int a = 0; 全局初始化區(qū) 
char *p1; 全局未初始化區(qū) 
int main() 
{ 
int b; 棧 
char s[] = "abc"; 棧 
char *p2; 棧 
char *p3 = "123456"; 123456在常量區(qū)尼啡，p3在棧上。 
static int c =0询微； 全局（靜態(tài)）初始化區(qū) 
p1 = (char *)malloc(10); 
p2 = (char *)malloc(20); 
分配得來得10和20字節(jié)的區(qū)域就在堆區(qū)崖瞭。 
strcpy(p1, "123456"); 123456放在常量區(qū)，編譯器可能會將它與p3所指向的"123456"優(yōu)化成一個地方撑毛。 
}

死鎖

所謂死鎖：是指兩個或兩個以上的進程在執(zhí)行過程中书聚，由于競爭資源或者由于彼此通信而造成的一種阻塞的現(xiàn)象，若無外力作用，它們都將無法推進下去雌续。此時稱系統(tǒng)處于死鎖狀態(tài)或系統(tǒng)產(chǎn)生了死鎖斩个，這些永遠在互相等待的進程稱為死鎖進程。

（1）因為系統(tǒng)資源不足西雀。（2）進程運行推進的順序不合適萨驶。（3）資源分配不當?shù)惹复荨Ｈ绻到y(tǒng)資源充足艇肴，進程的資源請求都能夠得到滿足，死鎖出現(xiàn)的可能性就很低叁温，否則就會因爭奪有限的資源而陷入死鎖再悼。其次，進程運行推進順序與速度不同膝但，也可能產(chǎn)生死鎖冲九。（1）互斥條件：一個資源每次只能被一個進程使用。（2）請求與保持條件：一個進程因請求資源而阻塞時跟束，對已獲得的資源保持不放莺奸。（3）不剝奪條件:進程已獲得的資源，在末使用完之前冀宴，不能強行剝奪灭贷。（4）循環(huán)等待條件:若干進程之間形成一種頭尾相接的循環(huán)等待資源關(guān)系。這四個條件是死鎖的必要條件略贮，只要系統(tǒng)發(fā)生死鎖甚疟，這些條件必然成立，而只要上述條件之一不滿足逃延，就不會發(fā)生死鎖览妖。

進程狀態(tài)

image.png