1 馮諾伊曼體系

1.1 馮諾伊曼體系簡介

現(xiàn)代計算機之父馮諾伊曼最先提出程序存儲的思想，并成功將其運用在計算機的設計之中，該思想約定了用二進制進行計算和存儲，還定義計算機基本結構為 5 個部分，分別是中央處理器（CPU）、內存、輸入設備、輸出設備、總線。

1. 存儲器：代碼跟數(shù)據(jù)在RAM跟ROM中是線性存儲， 數(shù)據(jù)存儲的單位是一個二進制位。最小的存儲單位是字節(jié)。

2. 總線：總線是用于 CPU 和內存以及其他設備之間的通信，總線主要有三種：

1. 地址總線：用于指定 CPU 將要操作的內存地址。

2. 數(shù)據(jù)總線：用于讀寫內存的數(shù)據(jù)。

3. 控制總線：用于發(fā)送和接收信號，比如中斷、設備復位等信號，CPU 收到信號后響應，這時也需要控制總線。

1. 輸入/輸出設備：輸入設備向計算機輸入數(shù)據(jù)，計算機經(jīng)過計算后，把數(shù)據(jù)輸出給輸出設備。比如鍵盤按鍵時需要和 CPU 進行交互，這時就需要用到控制總線。

2. CPU：中央處理器，類比人腦，作為計算機系統(tǒng)的運算和控制核心，是信息處理、程序運行的最終執(zhí)行單元。CPU用寄存器存儲計算時所需數(shù)據(jù)，寄存器一般有三種：

1. 通用寄存器：用來存放需要進行運算的數(shù)據(jù)，比如需進行加法運算的兩個數(shù)據(jù)。

2. 程序計數(shù)器：用來存儲 CPU 要執(zhí)行下一條指令所在的內存地址。

3. 指令寄存器：用來存放程序計數(shù)器指向的指令本身。

在馮諾伊曼體系下電腦指令執(zhí)行的過程：

1. CPU讀取程序計數(shù)器獲得指令內存地址，CPU控制單元操作地址總線從內存地址拿到數(shù)據(jù)，數(shù)據(jù)通過數(shù)據(jù)總線到達CPU被存入指令寄存器。

2. CPU分析指令寄存器中的指令，如果是計算類型的指令交給邏輯運算單元，如果是存儲類型的指令交給控制單元執(zhí)行。

3. CPU 執(zhí)行完指令后程序計數(shù)器的值通過自增指向下個指令，比如32位CPU會自增4。

4. 自增后開始順序執(zhí)行下一條指令，不斷循環(huán)執(zhí)行直到程序結束。

CPU位寬：32位CPU一次可操作計算4個字節(jié)，64位CPU一次可操作計算8個字節(jié)，這個是硬件級別的。平常我們說的32位或64位操作系統(tǒng)指的是軟件級別的，指的是程序中指令多少位。
線路位寬：CPU操作指令數(shù)據(jù)通過高低電壓變化進行數(shù)據(jù)傳輸，傳輸時候可以串行傳輸，也可以并行傳輸，多少個并行等于多少個位寬。

1.2 CPU 簡介

Central Processing Unit 中央處理器，作為計算機系統(tǒng)的運算和控制核心，是信息處理、程序運行的最終執(zhí)行單元。

1. CPU核心：一般一個CPU會有多個CPU核心，平常說的多核是指在一枚處理器中集成兩個或多個完整的計算引擎。核跟CPU的關系是：核屬于CPU的一部分。

2. 寄存器：最靠近CPU對存儲單元，32位CPU寄存器可存儲4字節(jié)，64位寄存器可存儲8字節(jié)。寄存器訪問速度一般是半個CPU時鐘周期，屬于納秒級別，

3. L1緩存：每個CPU核心都有，用來緩存數(shù)據(jù)跟指令，訪問空間大小一般在32～256KB，訪問速度一般是2～4個CPU時鐘周期。

   cat /sys/devices/system/cpu/cpu0/cache/index0/size # L1 數(shù)據(jù)緩存 cat /sys/devices/system/cpu/cpu0/cache/index1/size # L1 指令緩存 

4. L2緩存：每個CPU核心都有，訪問空間大小在128KB～2MB，訪問速度一般是10～20個CPU時鐘周期。

   cat /sys/devices/system/cpu/cpu0/cache/index2/size # L2 緩存容量大小 

5. L3緩存：多個CPU核心共用，訪問空間大小在2MB～64MB，訪問速度一般是20～60個CPU時鐘周期。

   cat /sys/devices/system/cpu/cpu0/cache/index3/size # L3 緩存容量大小 

6. 內存：多個CPU共用，現(xiàn)在一般是4G～512G，訪問速度一般是200～300個CPU時鐘周期。

7. 固體硬盤SSD：現(xiàn)在臺式機主流都會配備，上述的寄存器、緩存、內存都是斷電數(shù)據(jù)立馬丟失的，而SSD里不會丟失，大小一般是128G～1T，比內存慢10～1000倍。

8. 機械盤HDD：很早以前流行的硬盤了，容量可在512G～8T不等，訪問速度比內存慢10W倍不等。

9. 訪問數(shù)據(jù)順序：CPU在拿數(shù)據(jù)處理的時候幾乎也是按照上面說得流程來操縱的，只有上面一層找不到才會找下一層。

10. Cache Line:  CPU讀取數(shù)據(jù)時會按照 Cache Line 方式把數(shù)據(jù)加載到緩存中，每個Cacheline = 64KB，因為L1、L2是每個核獨有到可能會觸發(fā)偽共享，就是 所以可能會將數(shù)據(jù)劃分到不同到CacheLine中來避免偽共享，比如在JDK8 新增加的 LongAdder 就涉及到此知識點。

1. 偽共享：緩存系統(tǒng)中是以緩存行（cache line）為單位存儲的，當多線程修改互相獨立的變量時，如果這些變量共享同一個緩存行，就會無意中影響彼此的性能，這就是偽共享。

1. JMM: 數(shù)據(jù)經(jīng)過種種分層會導致訪問速度在不斷提升，同時也帶來了各種問題，多個CPU同時操作相同數(shù)據(jù)可能會造成各種BU個，需要加鎖，這里在JUC并發(fā)已詳細探討過。

1.3 CPU 訪問方式

1. Cache Line Index ：CPU緩存讀取數(shù)據(jù)時不是按照字節(jié)來讀取的，而是按照CacheLine方式存儲跟讀取數(shù)據(jù)的。

2. Valid Bit : 有效位標志符，值為0時表示無論 CPU Line 中是否有數(shù)據(jù)，CPU 都會直接訪問內存，重新加載數(shù)據(jù)。

3. Tag：組標記，用來標記內存中不同BLock映射到相同CacheLine，用Tag來區(qū)分不同的內存Block。

4. Data：真實到內存數(shù)據(jù)信息。

CPU真實訪問內存數(shù)據(jù)時只需要指定三個部分即可。

1. Cache Line Index ：要訪問到Cache Line 位置。

2. Tag：表示用那個數(shù)據(jù)塊。

3. Offset：CPU從CPU Cache 讀取數(shù)據(jù)時不是直接讀取Cache Line整個數(shù)據(jù)塊，而是讀取CPU所需的數(shù)據(jù)片段，稱為Word。如何找到Word就需要個偏移量Offset。

1.4 CPU 訪問速度

1. 指令緩存：盡可能的提供有規(guī)律的條件分支語句，讓 CPU 的分支預測器發(fā)揮作用，進一步提高執(zhí)行的效率，因為CPU是自帶分支預測器，自動提前將可能需要的指令放到指令緩存區(qū)。

2. 線程綁定到CPU：一個任務A在前一個時間片用CPU核心1 運行，后一個時間片用CPU核心2 運行，這樣緩存L1、L2就浪費了。因此操作系統(tǒng)提供了將進程或者線程綁定到某一顆 CPU 上運行的能力。如 Linux 上提供了 sched_setaffinity 方法實現(xiàn)這一功能，其他操作系統(tǒng)也有類似功能的 API 可用。當多線程同時執(zhí)行密集計算，且 CPU 緩存命中率很高時，如果將每個線程分別綁定在不同的 CPU 核心上，性能便會獲得非?？捎^的提升。

1.5  操作系統(tǒng)

2 內存管理

你的電腦是32位操作系統(tǒng)，那可支持的最大內存就是4G，你有沒有好奇為什么可以同時運行2個以上的2G內存的程序。應用程序不是直接使用的物理地址，操作系統(tǒng)為每個運行的進程分配了一套虛擬地址，每個進程都有自己的虛擬內存地址，進程是無法直接進行物理內存地址的訪問的。至于虛擬地址跟物理地址的映射，進程是感知不到的！操作系統(tǒng)自身會提供一套機制將不同進程的虛擬地址和不同內存的物理地址進行映射。

2.1  MMU

Memory Management Unit 內存管理單元是一種負責處理CPU內存訪問請求的計算機硬件。它的功能包括虛擬地址到物理地址的轉換、內存保護、中央處理器高速緩存的控制?，F(xiàn)代 CPU 基本上都選擇了使用 MMU。

當進程持有虛擬內存地址的時候，CPU執(zhí)行該進程時會操作虛擬內存，而MMU會自動的將虛擬內存的操作映射到物理內存上。

2.2  內存管理方式

操作系統(tǒng)主要采用內存分段和內存分頁來管理虛擬地址與物理地址之間的關系，其中分段是很早前的方法了，現(xiàn)在大部分用的是分頁，不過分頁也不是完全的分頁，是在分段的基礎上再分頁。

2.2.1 內存分段

我們以上圖的JVM內存模型舉例，程序員會認為我們的代碼是由代碼段、數(shù)據(jù)段、棧段、堆段組成。不同的段是有不同的屬性的，用戶并不關心這些元素所在內存的位置，而分段就是支持這種用戶視圖的內存管理方案。邏輯地址空間是由一組段構成。每個段都有名稱和長度。地址指定了段名稱和段內偏移。因此用戶段編號和段偏移來指定不同屬性的地址。而虛擬內存地址跟物理內存地址中間是通過段表進行映射的，口說無憑，看圖吧。

如上虛擬地址有 5 個段，各段按如圖所示來存儲。每個段都在段表中有一個條目，它包括段在物理內存內的開始的基地址和該段的界限長度。例如段 2 為 400 字節(jié)長，開始于位置 4300。因此對段 2 字節(jié) 53 的引用映射成位置 4300 + 53 = 4353。對段 3 字節(jié) 852 的引用映射成位置 3200 + 852 = 4052。

分段映射很簡單，但是會導致內存碎片跟內存交互效率低。這里先普及下在內存管理中主要有內部內存碎片跟外部內存碎片。

1. 內部碎片：已經(jīng)被分配出去的的內存空間不經(jīng)常使用，并且分配出去的內存空間大于請求所需的內存空間。

2. 外部碎片：指可用空間還沒有分配出去，但是可用空間由于大小太小而無法分配給申請空間的新進程的內存空間空閑塊。

以上圖為例，現(xiàn)在系統(tǒng)空閑是1400 +  800 + 600 = 2800。那如果有個程序想要連續(xù)的使用2000，內存分段模式下提供不了??！上述三個是外部內存碎片。當然可以使用系統(tǒng)的Swap空間，先把段0寫入到磁盤，然后再重新給段0分配空間。這樣可以實現(xiàn)最終可用，可是但凡涉及到磁盤讀寫就會導致內存交互效率低。

2.2.2 內存分頁

內存分頁，整個虛擬內存和物理內存切成一段段固定尺寸的大小。每個固定大小的尺寸稱之為頁Page，在 Linux 系統(tǒng)中Page = 4KB。然后虛擬內存跟物理內存之間通過頁表來實現(xiàn)映射。

采用內存分頁時內存的釋放跟使用都是以頁為單位的，也就不會產(chǎn)生內存碎片了。當空間還不夠時根據(jù)操作系統(tǒng)調度算法，可能將最少用的內存頁面 swap-out換出到磁盤，用時候再swap-in換入，盡可能的減少磁盤刷寫量，提高內存交互效率。

分頁模式下虛擬地址主要有頁號跟頁內偏移量兩部分組成。通過頁號查詢頁表找到物理內存地址，然后再配合頁內偏移量就找到了真正的物理內存地址。

32位操作系統(tǒng)環(huán)境下進程可操作的虛擬地址是4GB，假設一個虛擬頁大小為4KB，那需要4GB/4KB =2^20個頁信息。一行頁表記錄為4字節(jié)，2^20等價于4MB頁表存儲信息。這只是一個進程需要的，如果10個、100個、1000個呢？僅僅是頁表存儲都占據(jù)超大內存了。

為了解決這個問題就需要用到多級頁表，核心思想就是局部性分配。在32位的操作系統(tǒng)中將將4G空間分為 1024 行頁目錄項目(4KB)，每個頁目錄項又對應1024行頁表項。如下圖所示：

分頁后一級頁就等價于4G虛擬地址空間，并且如果一級頁表中那些地址沒有就不需要再創(chuàng)建二級頁表了！核心思想就是按需創(chuàng)建，當系統(tǒng)給每個進程分配4G空間，進程不可能占據(jù)全部內存的，如果一級目錄頁只有10%用到了，此時頁表空間 = 一級頁表4KB + 0.1 * 4MB  。這比單獨的每個進程占據(jù)4M好用多了！

多層分頁的弊端就是訪問時間的增加。

1. 使用頁表時讀取內存中一頁內容需要2次訪問內存，訪問頁表項 + 并讀取的一頁數(shù)據(jù)。

2. 使用二級頁表的話需要三次訪問，訪問頁目錄項 + 訪問頁表項 + 訪問并讀取的一頁數(shù)據(jù)。訪存次數(shù)的增加也就意味著訪問數(shù)據(jù)所花費的總時間增加。

而對于64位系統(tǒng)，二級分頁就無法滿足了，Linux 從2.6.11開始采用四級分頁模型。

1. Page Global Directory 全局頁目錄項

2. Page Upper Directory 上層頁目錄項

3. Page Middle Directory 中間頁目錄項

4. Page Table Entry 頁表項

5. Offset 偏移量。

2.2.2 TLB

Translation Lookaside Buffer 可翻譯為地址轉換后援緩沖器，簡稱為快表，屬于CPU內部的一個模塊，TLB是MMU的一部分，實質是cache，它所緩存的是最近使用的數(shù)據(jù)的頁表項（虛擬地址到物理地址的映射）。他的出現(xiàn)是為了加快訪問數(shù)據(jù)（內存）的速度，減少重復的頁表查找。當然它不是必須要有的，但有它，速度就更快。

1. 全部刷新：很簡單，但花銷大，很多不必刷新的數(shù)據(jù)也進行刷新，增加了無畏的花銷。

2. 部分刷新：根據(jù)標志位，刷新需要刷新的數(shù)據(jù)，保留不需要刷新的數(shù)據(jù)。

2.2.3 段頁式管理

內存分段跟內存分頁不是對立的，這倆可以組合起來在同一個系統(tǒng)中使用的，那么組合起來后通常稱為段頁式內存管理。段頁式內存管理實現(xiàn)的方式：

1. 先對數(shù)據(jù)不同劃分出不同的段，也就是前面說的分段機制。

2. 然后再把每一個段進行分頁操作，也就是前面說的分頁機制。

3. 此時 地址結構 = 段號 + 段內頁號 + 頁內位移。

每一個進程有一張段表，每個段又建立一張頁表，段表中的地址是頁表的起始地址，而頁表中的地址則為某頁的物理頁號。

1. 邏輯地址：指的是沒被段式內存管理映射的地址。

2. 線性地址：通過段式內存管理映射且頁式內存管理轉換前的地址，俗稱虛擬地址。

目前 Intel X86 CPU 采用的是內存分段 +  內存分頁的管理方式，其中分頁的意思是在由段式內存管理所映射而成的的地址上再加上一層地址映射。

2.2.4 Linux 內存管理

先說結論：Linux系統(tǒng)基于X86 CPU 而做的操作系統(tǒng)，所以也是用的段頁式內存管理方式。

1. 內核空間：操作系統(tǒng)內核訪問的區(qū)域，獨立于普通的應用程序，是受保護的內存空間。內核態(tài)下CPU可執(zhí)行任何指令，可自由訪問任何有效地址。

2. 用戶空間：普通應用程序可訪問的內存區(qū)域。被執(zhí)行代碼會受到CPU眾多限制，進程只能訪問映射其地址空間的頁表項中規(guī)定的在用戶態(tài)下可訪問頁面的虛擬地址。

那為啥要搞倆空間呢?現(xiàn)在嵌入式環(huán)境跟以前的WIN98系統(tǒng)是沒有區(qū)分倆空間的，須知倆空間是CPU分的，而操作系統(tǒng)是在上面運行的，單一用戶、單一任務服務的操作系統(tǒng)，是沒有分所謂用戶態(tài)和內核態(tài)的必要。用戶態(tài)和內核態(tài)是因為有多用戶，多任務的需求，然后在CPU硬件廠商配合之后，產(chǎn)生的一個操作系統(tǒng)解決多用戶多任務需求的方案。方案就是限制，通過硬件手段（也只能硬件手段才能做到），限制某些代碼，使其無法控制整個物理硬件，進而使各個不同用戶，不同任務的代碼，無權修改整個物理硬件，再進而保護操作系統(tǒng)的核心底層代碼和其他用戶的數(shù)據(jù)不被無意或者有意地破壞和盜取。

用戶態(tài)想要使用計算機設備或IO需通過系統(tǒng)調用完成sys call，系統(tǒng)調用就是讓內核來做這些操作。而系統(tǒng)調用是影響整個當前進程上下文的，ＣＰＵ提供了個軟中斷來是實現(xiàn)保護線程，獲取系統(tǒng)調用號跟參數(shù)，交給內核對應系統(tǒng)調用函數(shù)執(zhí)行。

3 進程管理

3.1 進程基礎知識

進程是程序的一次執(zhí)行，是一個程序及其數(shù)據(jù)在機器上順序執(zhí)行時所發(fā)生的活動，是具有獨立功能的程序在一個數(shù)據(jù)集合上的一次運行過程，是系統(tǒng)進行資源分配和調度的一個基本單位。進程的調度狀態(tài)如下：

1. 阻塞一般是當系統(tǒng)執(zhí)行IO操作時，此時進程進入阻塞狀態(tài)，等待某個事件的返回。

2. 掛起是指進程沒有占有物理內存，被寫到磁盤上了。這時進程狀態(tài)是掛起狀態(tài)。

1. 阻塞掛起：進程被寫入硬盤并等待某個事件的出現(xiàn)。

2. 就緒掛起：進程被寫入硬盤，進入內存可直接進入就緒狀態(tài)。

3.2 PCB

為了描述跟控制進程的運行，系統(tǒng)為每個進程定義了一個數(shù)據(jù)結構——進程控制塊 Process Control Block，它是進程實體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結構。

PCB 的作用是使一個在多道程序環(huán)境下不能獨立運行的程序，成為一個能獨立運行的基本單位，一個能與其它進程并發(fā)執(zhí)行的進程 :

1. 作為獨立運行基本單位的標志

2. 實現(xiàn)間斷性的運行方式

3. 提供進程管理所需要的信息

4. 提供進程調度所需要的信息

5. 實現(xiàn)與其他進程的同步與通信

3.2.1 PCB 信息

PCB為實現(xiàn)上述功能，內部包含眾多信息：

1. 進程標識符：用于唯一地標識一個進程，一個進程通常有兩種標識符：

1. 內部進程標識符：標識各個進程，每個進程都有一個并且唯一的標識符，設置內部標識符主要是為了方便系統(tǒng)使用。

2. 外部進程標識符：它由創(chuàng)建者提供，可設置用戶標識，以指示擁有該進程的用戶。往往是由用戶進程在訪問該進程時使用。一般為了描述進程的家族關系，還應設置父進程標識及子進程標識。

1. 處理機狀態(tài)：由各種寄存器組成。包含許多信息都放在寄存器中，方便程序restart。

1. 通用寄存器、指令計數(shù)器、程序狀態(tài)字PSW、用戶棧指針等信息。

1. 進程調度信息

1. 進程狀態(tài)：指明進程的當前狀態(tài)，作為進程調度和對換時的依據(jù)。

2. 進程優(yōu)先級：用于描述進程使用處理機的優(yōu)先級別的一個整數(shù)，優(yōu)先級高的進程應優(yōu)先獲得處理機

3. 進程調度所需的其它信息：與所采用的進程調度算法有關，如進程已等待CPU的時間總和、進程已執(zhí)行的時間總和等。

4. 事件：指進程由執(zhí)行狀態(tài)轉變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因。

1. 資源清單

有關內存地址空間或虛擬地址空間的信息，所打開文件的列表和所使用的 I/O 設備信息。

3.2.2 PCB 組織方式

操作系統(tǒng)中有太多 PCB，如何管理是個問題，一般有如下方式。

1. 線性方式：

1. 將系統(tǒng)所有PCB都組織在一張線性表中，將該表首地址存在內存的一個專用區(qū)域

2. 實現(xiàn)簡單，開銷小，但是每次都需要掃描整張表，適合進程數(shù)目不多的系統(tǒng)

1. 索引方式：

1. 將同一狀態(tài)的進程組織在一個索引表中，索引表項指向相應的 PCB，不同狀態(tài)對應不同的索引表。

1. 鏈接方式：

1. 把同一狀態(tài)的PCB鏈接成一個隊列，形成就緒隊列、阻塞隊列、空白隊列等。對其中的就緒隊列常按進程優(yōu)先級的高低排列，優(yōu)先級高排在隊前。

2. 因為進程創(chuàng)建、銷毀、調度頻繁，所以一般采用此模式。

3.3 進程控制

進程控制是進程管理最基本的功能，主要包括創(chuàng)建新進程，終止已完成的進程，將發(fā)生異常的進程置于阻塞狀態(tài)，將進程喚醒等。

3.3.1 進程創(chuàng)建

父進程可創(chuàng)建子進程，父進程終止后子進程也會被終止。子進程可繼承父進程所有資源，子進程終止需將自己所繼承的資源歸還父進程。接下來看下創(chuàng)建的大致流程。

1. 為新進程分配唯一進件標識號，然后創(chuàng)建一個空白PCB，需注意PCB數(shù)量是有限的，所以可能會創(chuàng)建失敗。

2. 嘗試為新進程分配所需資源，如果資源不足進程會進入等待狀態(tài)。

3. 初始化PCB，有如下幾個操作。

1. 標識信息：將系統(tǒng)分配的標識符和父進程標識符填入新PCB

2. 處理機狀態(tài)信息：使程序計數(shù)器指向程序入口地址，使棧指針指向棧頂

3. 處理機控制信息：將進程設為就緒/靜止狀態(tài)，通常設為最低優(yōu)先級

1. 如果進程調度隊列能接納新進程，就將進程插入到就緒隊列，等待被調度運行。

3.3.2 進程終止

進程終止情況一般分為正常結束、異常結束、外界干預三種。

1. 正常結束

2. 異常結束

1. 越界錯：訪問的存儲區(qū)越出該進程的區(qū)域

2. 保護錯：試圖訪問不允許訪問的資源，或以不適當?shù)姆绞皆L問（寫只讀）

3. 非法指令：試圖執(zhí)行不存在的指令（可能是程序錯誤地轉移到數(shù)據(jù)區(qū)，數(shù)據(jù)當成了指令）

4. 特權指令出錯：用戶進程試圖執(zhí)行一條只允許OS執(zhí)行的指令

5. 運行超時：執(zhí)行時間超過指定的最大值

6. 等待超時：進程等待某件事超過指定的最大值

7. 算數(shù)運算錯：試圖執(zhí)行被禁止的運算（被0除）

8. I/O故障

1. 外界干預

1. 操作員或OS干預（死鎖）

2. 父進程請求，子進程完成父進程指定的任務時

3. 父進程終止，所有子進程都應該結束

終止過程：

1. 根據(jù)被終止進程的標識符，從PCB集合中檢索出該PCB，讀取進程狀態(tài)

2. 若處于執(zhí)行狀態(tài)則立即終止執(zhí)行，將CPU資源分配給其他進程。

3. 若進程有子孫進程則將其所有子孫進程終止。

4. 全部資源還給父進程或操作系統(tǒng)。

5. 該進程的PCB從所在隊列/鏈表中移出。

3.3.3 進程阻塞

意思是該進程執(zhí)行半路被阻塞，必須由某個事件進程喚醒該進程。常見的就是IO讀取操作。常見阻塞時機/事件如下：

1. 請求共享資源失敗，系統(tǒng)無足夠資源分配

2. 等待某種操作完成

3. 新數(shù)據(jù)尚未到達（相互合作的進程）

4. 等待新任務

阻塞流程：

1. 找到要被阻塞進程標識號對應的 PCB。

2. 將該進程由運行狀態(tài)轉換為阻塞狀態(tài)。

3. 將該 進程PCB 插入的阻塞隊列中去。

3.3.4 進程喚醒

喚醒 原語 wake up，一般和阻塞成對使用。喚醒過程如下：

1. 從阻塞隊列找到所需PCB。

2. PCB從阻塞隊列溢出，然后變?yōu)榫途w狀態(tài)。

3. 從阻塞隊列溢出該PCB然后插入到就緒狀態(tài)隊列等待被分配CPU資源。

3.4 進程調度

進程數(shù)一般會大于CPU個數(shù)，進程狀態(tài)切換主要由調度程序進行調度。一般情況下CPU調度時主要分為搶占式調度跟非搶占式調度。

1. 非搶占式：讓進程運行直到結束或阻塞的調度方式， 容易實現(xiàn)，適合專用系統(tǒng)。

2. 搶占式：每個進程獲得時間片才可以被CPU調度運行， 可防止單一進程長時間獨占CPU 系統(tǒng)開銷大。

3.4.1 進程調度原則

1. CPU 利用率

1. CPU利用率 = 忙碌時間 / 總時間。

2. 調度程序應該盡量讓 CPU 始終處于忙碌的狀態(tài)，這可提高 CPU 的利用率。比如當發(fā)生IO讀取時候，不要傻傻等待，去執(zhí)行下別的進程。

1. 系統(tǒng)吞吐量

1. 系統(tǒng)吞吐量 = 總共完成多少個作業(yè) / 總共花費時間。

2. 長作業(yè)的進程會占用較長的 CPU 資源導致降低吞吐量，相反短作業(yè)的進程會提升系統(tǒng)吞吐量。

1. 周轉時間

1. 周轉時間 = 作業(yè)完成時間 - 作業(yè)提交時間。

2. 平均周轉時間 = 各作業(yè)周轉時間和 / 作業(yè)數(shù)

3. 帶權周轉時間 = 作業(yè)周轉時間 / 作業(yè)實際運行時間

4. 平均帶權周轉時間 = 各作業(yè)帶權周轉時間之和 / 作業(yè)數(shù)

5. 盡可能使周轉時間降低。

1. 等待時間

1. 指的是進程在等待隊列中等待的時間，一般也需要盡可能短。

2. 響應時間
   響應時間 = 系統(tǒng)第一次響應時間 - 用戶提交時間，在交互式系統(tǒng)中響應時間是衡量調度算法好壞的主要標準。

3.4.2 調度算法

FCFS 算法

1. First Come First Severd 先來先服務算法，遵循先來后端原則，每次從就緒隊列拿等待時間最久的，運行完畢后再拿下一個。

2. 該模式對長作業(yè)有利，適用 CPU 繁忙型作業(yè)的系統(tǒng)，不適用 I/O 型作業(yè)，因為會導致進程CPU利用率很低。

SJF 算法

1. Shortest Job First 最短作業(yè)優(yōu)先算法，該算法會優(yōu)先選擇運行所需時間最短的進程執(zhí)行，可提高吞吐量。

2. 跟FCFS正好相反，對長作業(yè)很不利。

SRTN 算法

1. Shortest Remaining Time Next 最短剩余時間優(yōu)先算法，可以認為是SJF的搶占式版本，當一個新就緒的進程比當前運行進程具有更短完成時間時，系統(tǒng)搶占當前進程，選擇新就緒的進程執(zhí)行。

2. 有最短的平均周轉時間，但不公平，源源不斷的短任務到來，可能使長的任務長時間得不到運行。

HRRN 算法

1. Highest Response Ratio Next 最高響應比優(yōu)先算法，為了平衡前面?zhèn)z而生，按照響應優(yōu)先權從高到低依次執(zhí)行。屬于前面?zhèn)z的折中權衡。

2. 優(yōu)先權 = (等待時間 + 要求服務時間) / 要求服務時間

RR 算法

1. Round Robin 時間片輪轉算法，操作系統(tǒng)設定了個時間片Quantum，時間片導致每個進程只有在該時間片內才可以運行，這種方式導致每個進程都會均勻的獲得執(zhí)行權。

2. 時間片一般20ms~50ms，如果太小會導致系統(tǒng)頻繁進行上下文切換，太大又可能引起對短的交互請求的響應變差。

HPF 算法

1. Highest Priority First 最高優(yōu)先級調度算法，從就緒隊列中選擇最高優(yōu)先級的進程先執(zhí)行。

2. 優(yōu)先級的設置有初始化固定死的那種，也有在代碼運轉過程中根據(jù)等待時間或性能動態(tài)調整 這兩種思路。

3. 缺點是可能導致低優(yōu)先級的一直無法被執(zhí)行。

MFQ 算法

1. Multilevel Feedback Queue 多級反饋隊列調度算法 ，可以認為是 RR 算法 跟 HPF 算法 的綜合體。

2. 系統(tǒng)會同時存在多個就緒隊列，每個隊列優(yōu)先級從高到低排列，同時優(yōu)先級越高獲得是時間片越短。

3. 新進程會先加入到最高優(yōu)先級隊列，如果新進程優(yōu)先級高于當前在執(zhí)行的進程，會停止當前進程轉而去執(zhí)行新進程。新進程如果在時間片內沒執(zhí)行完畢需下移到次優(yōu)先級隊列。

   多級反饋隊列調度算法

3.5 線程

3.5.1 線程定義

早期操作系統(tǒng)是沒有線程概念的，線程是后來加進來的。為啥會有線程呢？那是因為以前在多進程階段，經(jīng)常會涉及到進程之間如何通訊，如何共享數(shù)據(jù)的問題。并且進程關聯(lián)到PCB的生命周期，管理起來開銷較大。為了解決這個問題引入了線程。

線程是進程當中的一個執(zhí)行流程。同一個進程內的多個線程之間可以共享進程的代碼段、數(shù)據(jù)段、打開的文件等資源。同時每個線程又都有一套獨立的寄存器和棧來確保線程的控制流是獨立的。

進程有個PCB來管理，同理操作系統(tǒng)通過Thread Control Block線程控制塊來實現(xiàn)線程的管控。

3.5.2 線程優(yōu)缺點

優(yōu)點

1. 一個進程中可以同時存在1~N個線程，這些線程可以并發(fā)的執(zhí)行。

2. 各個線程之間可以共享地址空間和文件等資源。

缺點

1. 當進程中的一個線程奔潰時，會導致其所屬進程的所有線程奔潰。

2. 多線程編程，讓人頭大的東西。

3. 線程執(zhí)行開銷小，但不利于資源的隔離管理和保護，而進程正相反。

3.5.3 進程跟線程關聯(lián)

進程：

1. 是系統(tǒng)進行資源分配和調度的一個獨立單位.

2. 是程序的一次執(zhí)行，每個進程都有自己的地址空間、內存、數(shù)據(jù)棧及其他輔助記錄運行軌跡的數(shù)據(jù)

線程：

1. 是進程的一個實體，是CPU調度和分派的基本單位,它是比進程更小的能獨立運行的基本單位

2. 所有的線程運行在同一個進程中，共享相同的運行資源和環(huán)境

3. 線程一般是并發(fā)執(zhí)行的，使得實現(xiàn)了多任務的并行和數(shù)據(jù)共享。

進程線程區(qū)別：

1. 一個線程只能屬于一個進程，而一個進程可以有多個線程，但至少有一個線程。

2. 線程的劃分尺度小于進程(資源比進程少)，使得多線程程序的并發(fā)性高。

3. 進程在執(zhí)行過程中擁有獨立的內存單元，而多個線程共享內存，從而極大地提高了程序的運行效率。

4. 資源分配給進程，同一進程的所有線程共享該進程的所有資源。

5. CPU分配資源給進程，但真正在CPU上運行的是線程。

6. 線程不能夠獨立執(zhí)行，必須依存在進程中。

線程快在哪兒？

1. 線程創(chuàng)建的時有些資源不需要自己管理，直接從進程拿即可，線程管理寄存器跟棧的生命周期即可。

2. 同進程內多線程共享數(shù)據(jù)，所以進程數(shù)據(jù)傳輸可以用zero copy技術，不需要經(jīng)過內核了。

3. 進程使用一個虛擬內存跟頁表，然后多線程共用這些虛擬內存，如果同進程內兩個線程進行上下文切換比進程提速很多。

3.5.4 線程實現(xiàn)

在前面的內存管理中說到了內核態(tài)跟用戶態(tài)。相對應的線程的創(chuàng)建也分為用戶態(tài)線程跟內核態(tài)線程。

3.5.4.1 用戶態(tài)線程

在用戶空間實現(xiàn)的線程，由用戶態(tài)的線程庫來完成線程的管理。操作系統(tǒng)按進程維度進行調度，當線程在用戶態(tài)創(chuàng)建時應用程序在用戶空間內要實現(xiàn)線程的創(chuàng)建、維護和調度。操作系統(tǒng)對線程的存在一無所知！操作系統(tǒng)只能看到進程看不到線程。所有的線程都是在用戶空間實現(xiàn)。在操作系統(tǒng)看來，每一個進程只有一個線程。

好處：

1. 及時操作系統(tǒng)不支持線程模式也可以通過用戶層庫函數(shù)來支持線程模式，TCB 由用戶級線程庫函數(shù)來維護。

2. 使用庫函數(shù)模式實現(xiàn)線程可以避免用戶態(tài)到內核態(tài)的切換。

壞處：

1. CPU不知道線程存在，CPU的時間片切換是以進程為維度的，某個線程因為IO等操作導致線程阻塞，操作系統(tǒng)會阻塞整個進程，即使這個進程中其它線程還在工作。

2. 用戶態(tài)線程沒法打斷正在運行中的線程，除非線程主動交出CPU使用權。

3.5.4.2 內核態(tài)線程

在內核中實現(xiàn)的線程，是由內核管理的線程，線程對應的 TCB 在操作系統(tǒng)里，這樣線程的創(chuàng)建、終止和管理都是由操作系統(tǒng)負責。內線程模式下一個用戶線程對應一個內核線程。

優(yōu)點：

1. 一個進程中某個線程阻塞不會影響其他內核線程運行。

2. 用戶態(tài)模式一個時間片分給多個線程，內核態(tài)模式直接分配給線程的時間片增加。

缺點：

1. 內核級線程調度開銷較大。調度內核線程的代價可能和調度進程差不多昂貴，代價要比用戶級線程大很多。一個線程默認棧=1M，線程多了會導致內存消耗很大。

2. 線程表是存放在操作系統(tǒng)固定的表格空間或者堆?？臻g里，所以內核級線程的數(shù)量是有限的。

3.4.4.3 輕量級進程

最初的進程定義都包含程序、資源及其執(zhí)行三部分，其中程序通常指代碼，資源在操作系統(tǒng)層面上通常包括內存資源、IO資源、信號處理等部分，而程序的執(zhí)行通常理解為執(zhí)行上下文，包括對CPU的占用，后來發(fā)展為線程。在線程概念出現(xiàn)以前，為了減小進程切換的開銷，操作系統(tǒng)設計者逐漸修正進程的概念，逐漸允許將進程所占有的資源從其主體剝離出來，允許某些進程共享一部分資源，例如文件、信號，數(shù)據(jù)內存，甚至代碼，這就發(fā)展出輕量進程的概念。

Light-weight process 輕量級進程是內核支持的用戶線程，它是基于內核線程的高級抽象，系統(tǒng)只有先支持內核線程才能有 LWP。一個進程可有1~N個LWP，每個 LWP 是跟內核線程一對一映射的，也就是 LWP 都是由一個內核線程支持。

輕量級進程本質還是進程，只是跟普通進程相比LWP跟其他進程共享大部分邏輯地址空間跟系統(tǒng)資源，LWP輕量體現(xiàn)在它只有一個最小的執(zhí)行上下文和調度程序所需的統(tǒng)計信息。他是進程的執(zhí)行部分，只帶有執(zhí)行相關的信息。

Linux特性：

1. Linux中沒有真正的線程，因為Linux并沒有為線程準備特定的數(shù)據(jù)結構。在內核看來只有進程而沒有線程，在調度時也是當做進程來調度。Linux所謂的線程其實是與其他進程共享資源的進程。但windows中確實有線程。

2. Linux中沒有的線程，線程是由進程來模擬實現(xiàn)的。

3. 所以在Linux中在CPU角度看，進程被稱作輕量級進程LWP。

3.5.5 協(xié)程

3.5.5.1 協(xié)程定義

大多數(shù)web服務跟互聯(lián)網(wǎng)服務本質上大部分都是 IO 密集型服務，IO 密集型服務的瓶頸不在CPU處理速度，而在于盡可能快速的完成高并發(fā)、多連接下的數(shù)據(jù)讀寫。以前有兩種解決方案：

1. 多進程：存在頻繁調度切換問題，同時還會存在每個進程資源不共享的問題，需要額外引入進程間通信機制來解決。

2. 多線程：高并發(fā)場景的大量 IO 等待會導致多線程被頻繁掛起和切換，非常消耗系統(tǒng)資源，同時多線程訪問共享資源存在競爭問題。

此時協(xié)程出現(xiàn)了，協(xié)程 Coroutines 是一種比線程更加輕量級的微線程。類比一個進程可以擁有多個線程，一個線程也可以擁有多個協(xié)程?？梢院唵蔚陌褏f(xié)程理解成子程序調用，每個子程序都可以在一個單獨的協(xié)程內執(zhí)行。

3.5.5.2 協(xié)程注意事項

協(xié)程運行在線程之上，并且協(xié)程調用了一個阻塞IO操作，此時操作系統(tǒng)并不知道協(xié)程的存在，它只知道線程，因此在協(xié)程調用阻塞IO操作時，操作系統(tǒng)會讓線程進入阻塞狀態(tài)，當前的協(xié)程和其它綁定在該線程之上的協(xié)程都會陷入阻塞而得不到調度。

因此在協(xié)程中不能調用導致線程阻塞的操作，比如打印、讀取文件、Socket接口等。協(xié)程只有和異步IO結合起來才能發(fā)揮最大的威力。并且協(xié)程只有在IO密集型的任務中才會發(fā)揮作用。

3.6 進程通信

進程的用戶地址空間是相互獨立的，不可以互相訪問，但內核空間是進程都共享的，所以進程之間要通信必須通過內核。進程間通信主要通過管道、消息隊列、共享內存、信號量、信號、Socket編程。

3.6.1 管道

管道主要分為匿名管道跟命名管道兩種，可以實現(xiàn)數(shù)據(jù)的單向流動性。使用起來很簡單，但是管道這種通信方式效率低，不適合進程間頻繁地交換數(shù)據(jù)。

匿名管道：

1. 日常Linux系統(tǒng)中的|就是匿名管道。指令的前一個輸入是后一個指令的輸出。

命名管道：

1. 一般通過mkfifo SoWhatPipe創(chuàng)建管道。通過echo "sw" > SoWhatPipe跟cat < SoWhatPipe實現(xiàn)輸入跟輸出。

匿名管道的實現(xiàn)依賴int pipe(int fd[2])函數(shù)，其中fd[0]是讀取斷描述符，fd[1]是管道寫入端描述符。它的本質就是在內核中創(chuàng)建個屬于內存的緩存，從一端輸入無格式數(shù)據(jù)一端輸出無格式數(shù)據(jù)，需注意管道傳輸大小是有限的。

1. 父進程關閉讀取的 fd[0]，只保留寫入的 fd[1]。

2. 子進程關閉寫入的 fd[1]，只保留讀取的 fd[0]。

3.6.2 消息隊列

3.6.3 共享內存

3.6.4 信號量

既然共享內存容易造成數(shù)據(jù)紊亂，那為了簡單的實現(xiàn)共享數(shù)據(jù)在任意時刻只能被一個進程訪問，此時需要信號量。

信號量其實是一個整型的計數(shù)器，主要用于實現(xiàn)進程間的互斥與同步，而不是用于緩存進程間通信的數(shù)據(jù)。

信號量表示資源的數(shù)量，核心點在于原子性的控制一個數(shù)據(jù)的值，控制信號量的方式有PV兩種原子操作：

1. P 操作會把信號量減去 -1，相減后如果信號量 < 0，則表明資源已被占用，進程需阻塞等待。相減后如果信號量 >= 0，則表明還有資源可使用，進程可正常繼續(xù)執(zhí)行。

2. V 操作會把信號量加上 1，相加后如果信號量 <= 0，則表明當前有阻塞中的進程，于是會將該進程喚醒運行。相加后如果信號量 > 0，則表明當前沒有阻塞中的進程。

3.6.5 信號

對于異常狀態(tài)下進程工作模式需要用到信號工作方式來通知進程。比如Linux系統(tǒng)為了響應各種事件提供了很多異常信號kill -l，信號是進程間通信機制中唯一的異步通信機制，可以在任何時候發(fā)送信號給某一進程。比如：

1. kill -9 1412 ，表示給 PID 為 1412 的進程發(fā)送 SIGKILL 信號，用來立即結束該進程。

2. 鍵盤 Ctrl+C 產(chǎn)生 SIGINT 信號，表示終止該進程。

3. 鍵盤 Ctrl+Z 產(chǎn)生 SIGTSTP 信號，表示停止該進程，但還未結束。

有信號發(fā)生時，進程一般有三種方式響應信號：

1. 執(zhí)行默認操作：Linux操作系統(tǒng)為眾多信號配備了專門的處理操作。

2. 捕捉信號：給捕捉到的信號配備專門的信號處理函數(shù)。

3. 忽略信號：專門用來忽略某些信號，但 SIGKILL 和 SEGSTOP是無法被忽略的，為了能在任何時候結束或停止某個進程而存在。

3.6.6 Socket編程

前面提到的管道、消息隊列、共享內存、信號量和信號都是在同一臺主機上進行進程間通信，那要想跨網(wǎng)絡與不同主機上的進程之間通信，就需要 Socket 通信。

int socket(int domain, int type, int protocal) 

[sowhat@localhost ~]$ ln [選項] 源文件 目標文件
選項：
-s：建立軟鏈接文件。如果不加 "-s" 選項，則建立硬鏈接文件；
-f：強制。如果目標文件已經(jīng)存在，則刪除目標文件后再建立鏈接文件；

buf = mmap(file, len);
write(sockfd, buf, len);

ssize_t sendfile(int out_fd, int in_fd, off_t *offset, size_t count);
out_fd : 目的文件描述符
in_fd:源文件描述符
offset:源文件內偏移量
count:打算復制數(shù)據(jù)長度 ssize_t:實際上復制數(shù)據(jù)的長度

$ ethtool -k eth0 | grep scatter-gather
scatter-gather: on