OS基礎知識

• 程序和線程
  • 程序和線程有什麼差別？
  • 程序間通信有哪些方式？
  • 程序同步問題
  • 程序有哪幾種狀态？
  • 程序排程政策有哪些？
  • 什麼是僵屍程序？
  • 線程同步有哪些方式？
  • 什麼是協程？
  • 程序的異常控制流：陷阱、中斷、異常和信号
  • 什麼是IO多路複用？怎麼實作？
  • 什麼是使用者态和核心态？
• 死鎖
  • 什麼是死鎖？
  • 死鎖産生的必要條件？
  • 死鎖有哪些處理方法？
• 記憶體管理
  • 分頁和分段有什麼差別？
  • 什麼是虛拟記憶體？
  • 有哪些頁面置換算法？
  • 緩沖區溢出問題
• 磁盤排程
  • 什麼是檔案系統挂載
  • cpu緩存
• 回調是什麼
• 轉載：圖文并茂，一文帶你掌握作業系統(含大廠面試題，萬字長文，建議收藏) https://blog.csdn.net/FlyingFish868/article/details/118666884
• 轉載：整理了一套作業系統常見的面試題，不管你是面試大廠還是小廠都足夠了 https://blog.51cto.com/u_15082402/2592024

程序和線程有什麼差別？

程序是系統進行資源配置設定和排程的基本機關，線程是cpu排程和配置設定的基本機關。

線程依賴于程序而存在，一個程序至少有一個線程。程序有自己獨立的位址空間，線程之間共享程序的位址空間。

程序是擁有作業系統資源的獨立機關，而線程自己基本不擁有系統資源，僅僅擁有一些基本資源，例如程式計數器，一組寄存器和棧，和其他線程共享所屬程序的系統資源，cpu，io，記憶體等等

程序切換時，涉及到整個目前程序的cpu環境的儲存和新被排程的程序的cpu環境設定，而線程切換時隻需儲存和設定少量的cpu寄存器的内容，不涉及存儲器的管理方面的操作，是以程序切換的開銷遠大于線程切換的開銷

線程之間通信的方式更友善：可以通過共享同一程序下全局變量等資料進行通信

程序間通信方式：通過程序間通信IPC進行

多線程程式中一個線程崩潰會導緻整個程式崩潰，多程序程式中一個程序崩潰不會導緻其他程序崩潰，因為程序有自己獨立的記憶體位址空間，更加健壯。

同一程序中的線程可以共享哪些資料？

程序代碼段，程序的公有資料例如全局變量，靜态變量等等。程序打開的檔案描述符，程序目前目錄，程序ID，程序組ID

線程獨占哪些資源？

線程ID。一組寄存器和棧。線程産生的錯誤傳回碼。

程序間通信有哪些方式？

管道：半雙工，如果需要雙向通信需要兩個管道。寫程序在管道的緩沖區末尾寫入，讀程序在管道的緩沖區頭部讀出。

共享記憶體，消息隊列，信号量

信号量：pv操作，p操作信号量減一，v操作信号量加一。檢測信号量是否小于零，小于零則進行阻塞，大于零則從等待隊列中喚醒一個程序進入就緒狀态。

程序同步問題

管程将共享變量和對共享變量的操作封裝起來，形成一個具有一定接口的功能子產品，當一個程序需要對共享變量進行操作的時候，必須通過管程的某個過程才能通路管程中的資源，程序隻能互斥的使用，使用完之後必須釋放管程并喚醒在入口等待隊列中的程序。

MESA管程：java中使用的管程模型就是MESA管程，他将HOARE中的signal換成了notify，進行通知而不是立刻交換管程的使用權，在合适的時候條件隊列中的首位程序可以進入，進入前使用while檢查條件是否合适。

優點：沒有額外程序切換。

生産者-消費者：使用一個緩沖區存放資料，不為滿時生産者可以寫入，不為空時消費者可以讀出。

初始狀态，full為0，empty為n
semaphore full = 0, empty = n, mutex = 1;
void producer(){
    p(mutex);
    p(empty);
    生産
        v(full);
    v(mutex);
}
void consumer(){
    p(mutex)
        p(full)
        消費
        v(empty)
        v(mutext)
}
           

哲學家就餐：五個哲學家五個筷子，哲學家要麼思考要麼吃飯。如何避免死鎖。

semaphore int[] chopstick, mutex;
int[] state;
void philosopher(int i){
    think()
        take_c()
        eat()
        put_c()
}
void take_c(){
    p(mutext)
        if((chopstick[i] & chopstick[i+1]) == 1) //左右兩個筷子都在
            chopstick[i] = 0 
            chopstick[i+1]) = 0
            state[i] = EATING
       v(mutext)
}
void put_c(){
    p(mutext)
        if(state[i] == EATING)
            chopstick[i] = 1 
            chopstick[i+1]) = 1
            state[i] == THANKING
       v(mutext)
}
           

臨界區的概念？

本質就是一段代碼塊，在這個代碼塊中會有多個程序通路共享的資源和變量，但各個程序直接隻能互斥的通路。

同步與互斥的概念？

同步：各個程序間按照順序執行

互斥：多個程序在同一時刻隻有一個程序進入臨界區

并發、并行、異步的差別？

并發：一個時間段内有多個程式同時運作，但在某一時刻隻有一個程式在真正運作，宏觀上是通過不斷進行切換程序實作的。

并行：在某一時刻，有多個程式在真正同時運作

異步：異步是指各個程式之間并不一定按照一定的順序先後執行，可能通過并發，并行的手段同時執行多個任務

程序有哪幾種狀态？

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-PwPdzUou-1633588896366)(D:\包\New folder\test\Waking-Up-master_v_images\20191202090217863_1873.png)]

就緒：有權限無時間片

運作：有權限有時間片

阻塞：程序等待某種條件，隻有條件滿足後才能繼續執行

程序排程政策有哪些？

先來先服務：非搶占式

最高響應比優先：1+等待時間/處理時間，很好的平衡了長短程序，非搶占式

時間片輪轉；就緒程序按照先來先服務原則排成一個隊列，用完時間片的程序排到最後，搶占式，無饑餓問題

優先級：為每個程序配置設定一個優先級，按照優先級的順序執行，為了避免饑餓問題可以将等待時間久的程序提升優先級。

多級回報隊列：按照優先級遞減，時間片遞增，設定多個就緒隊列，隻有當高優先級的隊列中沒有待執行任務時，才從低優先級隊列中取出任務進行執行。如果高優先級隊列中的一個程序用完了時間片還沒有被執行完，那麼就将它移入下一個隊列。搶占式。

什麼叫優先級反轉？如何解決？

當一個高優先級任務通過信号量機制通路共享資源時，信号量已經被一些低優先級任務占有，導緻高優先級任務被低優先級任務阻塞，實時性無法得到保證。

1.優先級天花版，當某任務申請資源時把這個任務優先級提高到所有可以通路這個資源的任務當中的最進階。

2.優先級繼承：進階别任務通路資源時，若該資源正在被低級别任務通路，則把低級别任務的級别調整到和進階别任務相同。

什麼是僵屍程序？

一個子程序結束後他的父程序并沒有等待他（wait或者waitpid），那麼這個子程序将成為僵屍程序，僵屍程序是死亡的程序，但并沒有被真正銷毀。有如下特點：放棄了幾乎所有記憶體空間，沒有可執行代碼，不可被排程，僅在程序表中保留一個位置，可能會一隻保留直到系統重新開機。

危害：占用程序号，占用記憶體

什麼是孤兒程序？

一個程序的父程序已經結束，但子程序依然在運作，那麼這些子程序将成為孤兒程序，孤兒程序會被lnit接管，lnit會在孤兒程序結束時完成狀态收集工作

線程同步有哪些方式？

互斥鎖：mutex是核心對象，擁有互斥鎖的程序才能通路互斥資源，互斥鎖隻有一個，線程在結束通路互斥資源後必須釋放互斥鎖。

信号量：信号量是核心對象，允許同一時刻多個線程通路同一個資源，但要控制最大線程數量。儲存了最大資源計數和目前可用資源計數。隻要目前資源計數大于零，就可以發出信号量信号，如果為0，則将線程放入一個等待隊列中等待。

事件：EVENT，一個線程在處理完任務後主動喚醒另一個線程執行任務。手動重置事件：手動重置事件被設定為激發态之後，會喚醒所有等待線程，并且一直保持激發狀态，直到程式重新把它設定為未激發狀态。自動重置事件：自動重置事件被設定為激發态後會喚醒一個等待中的線程，然後自動進入未激發狀态。

臨界區：任意時刻隻允許一個線程對臨界資源進行通路，擁有臨界區對象的線程可以通路該臨界資源，其他試圖通路該資源的線程将被挂起，直到臨界區對象被釋放。

互斥量和臨界區有什麼差別？

互斥量是可以命名的，可以用于不同程序之間的同步，臨界區隻能用于同一程序中線程的同步。建立互斥量需要消耗資源，臨界區的優勢是速度快，省資源。

什麼是協程？

由使用者完全控制的，使用者态的輕量級線程，擁有自己的寄存器和上下文棧。協程排程切換時，将寄存器上下文和棧儲存到其他地方，切換回來的時候恢複先前儲存的寄存器上下文和棧，直接操作棧則基本沒有核心切換的開銷，可以不加鎖的通路全局變量，是以上下文切換非常快。

協程多與線程進行比較？

線程可以擁有多個協程，程序可以單獨擁有多個協程

線程程序都是同步機制，而協程是異步機制

協程能保留上一次調用時的狀态，每次過程重入時，相當于進入上一次調用狀态

程序的異常控制流：陷阱、中斷、異常和信号

陷阱是有意造成的異常，是指令執行的結果。主要作用是實作系統調用，程序可以執行syscall n 指令向核心請求服務，中斷目前控制流并陷入到核心态，執行完成後會将結果傳回給程序，同時退回到使用者态，繼續執行下一條指令。

中斷由處理器外部硬體産生，不是執行某條指令的結果，也無法預測發生時機。中斷獨立于目前運作的程式，是以中斷是異步事件，中斷包括IO裝置發出的IO中斷，定時器引發的時鐘中斷，調試程式設定斷點等引起調試中斷。

異常是一種錯誤情況，是執行目前指令的結果，可被錯誤處理程式修正也有可能直接終止應用程式。異常是同步的，特指因為執行目前指令而産生的錯誤情況。如除法異常缺頁異常等。

信号是更高層的軟體形式的異常，同樣會中斷程序的控制流，可由程序進行處理，一個信号代表一個消息，信号作用是通知程序發生了某種系統事件。

什麼是IO多路複用？怎麼實作？

IO多路複用：單個程序或者線程就可以同時處理多個IO請求

實作原理：使用者将想要監視的檔案描述符添加到select epoll函數中，由核心監視，函數阻塞，一旦有檔案描述符就緒（讀就緒或者寫就緒），或者逾時，函數就會傳回，然後程序可以進行相應的讀寫操作。

select模式：将檔案描述符放入一個集合中，調用select時，将該集合從使用者空間拷貝到核心空間。核心根據就緒狀态修改集合内容，采用水準觸發機制，select函數傳回後，需要通過周遊（輪詢）集合找到就緒的檔案描述符。檔案描述符數量增加時，效率會線性下降。

epoll：使用者和核心共享記憶體，避免不斷複制的問題，支援連接配接數上限高，檔案描述符就緒時采用回調機制，避免輪詢。（回調函數将就緒的檔案描述符添加到一個連結清單中，執行epoll_wait時，傳回這個連結清單），支援水準觸發和邊緣觸發，采用邊緣觸發時，隻有活躍的描述符才會觸發回調函數。

兩者主要差別：

支援最大連接配接數不同

檔案描述符的傳遞方式不同（是否複制）

水準觸發和邊緣觸發

查詢就緒描述符時，輪詢還是回調

select 和 epoll的使用場景：

連接配接數多，且大多數連接配接都不活躍時，epoll效率高。連接配接數少，且都比較活躍的情況下，由于epoll需要很多回調，是以性能可能低于其他兩者。

檔案描述符是什麼？

檔案描述符形式上是一個非負整數，實際上是一個索引值，指向核心為每一個程序維護的，該程序打開或建立的記錄表，程式打開或建立一個檔案時，核心向程序傳回一個檔案描述符。

核心通過檔案描述符通路檔案，檔案描述符指向一個檔案。

什麼是水準觸發？什麼是邊緣觸發？

水準觸發：如果檔案描述符已經就緒，就可以非阻塞的執行IO操作了，此時會觸發通知，允許在任意時刻重複檢測IO狀态，沒有必要每次描述符就緒後盡可能多的執行IO。（當被監控的檔案描述符上有可讀寫的事件發生時，會通知使用者去讀寫，如果使用者一讀寫沒取完資料，會一直通知使用者，如果這個描述符是使用者不關心的，他每次都傳回通知使用者，會導緻使用者對關心的描述符處理效率變低）

邊緣觸發：如果檔案描述符自上次狀态改變之後有新的IO到達，此時會觸發通知，在收到一個IO事件通知後要盡可能多的執行IO操作，因為如果在一次通知中沒有執行完IO操作，就需要等待下一次新的IO活動到來時才能擷取到就緒的描述符。（有可讀寫事件發生時會通知使用者讀寫，但隻會通知使用者程序一次，需要一次把内容讀取完，比水準觸發效率高，如果沒讀完再次請求時不會傳回，要等下一次新資料到來才傳回）

有哪些常見的IO模型？

同步阻塞IO：使用者線程發起IO讀寫之後，線程阻塞，直到可以開始處理資料

同步非阻塞IO：使用者線程發起IO之後立刻傳回，如果沒有就緒的資料，就不算發起IO請求直到資料就緒，不算重複消耗大量資源

IO多路複用

異步IO：使用者線程發起IO請求之後，繼續執行，由核心讀取資料并放在使用者指定緩沖區内，IO完成之後通知使用者線程使用

什麼是使用者态和核心态？

為了限制不同程式的通路能力，防止一些程式通路敏感資料或指令，cpu劃分了使用者态和核心态兩個不同的權限等級。

使用者态：受限地通路記憶體，不允許通路外圍裝置，沒有占用cpu能力，cpu資源可被其他程式擷取

核心态：核心态可以通路記憶體所有資料以及外圍裝置，也可以進行程式切換

所有使用者程式都運作在使用者态，有時需要進行一些核心态的操作，從硬碟或者鍵盤讀取資料，就需要進行系統調用，使用陷阱指令，切換到核心态，執行相應服務，再切換回使用者态并傳回調用結果。

為什麼要分使用者态和核心态？

安全性，保護系統資源。封裝性，使用者程式無需實作底層代碼。利于排程，多個使用者程式等待鍵盤輸入時交給作業系統排程更友善。

如何從使用者态切換到核心态？

系統調用：讀取指令行輸入，本質通過中斷實作

使用者程式發生異常：如缺頁異常

外圍裝置中斷：外圍裝置完成使用者請求操作後向cpu發送中斷信号，這時cpu會轉去處理對應中斷處理程式。

什麼是死鎖？饑餓？

死鎖：兩個及以上程序之間，由于競争資源産生，導緻程序無限等待，可以檢測出來

饑餓：由于資源政策配置設定不公平引起，不一定處于等待狀态，可能處于忙等或就緒态

死鎖産生的必要條件？

互斥，占有并等待，非搶占（已配置設定的資源不能被強占隻能自願釋放），循環等待

死鎖有哪些處理方法？

死鎖預防：破壞死鎖形成的四個必要條件

死鎖避免：動态監測資源配置設定狀态，隻有確定系統處于安全狀态時，才進行資源配置設定。安全狀态是指即使所有程序突然請求需要的所有資源，也能存在某種對程序的資源配置設定順序，使得每一個程序運作完畢。（銀行家算法）

死鎖解除：

強占程序資源，設定程序還原點在需要時復原程序使其資源釋放資源，殺死程序。

分頁和分段有什麼差別？

頁式存儲：使用者空間劃分為大小相等的部分稱為頁，記憶體空間劃分為同樣大小的區域稱為頁框。配置設定時以頁為機關按照程序需要的頁數配置設定，邏輯相鄰的頁在實體上不一定相鄰。

段式存儲：使用者程序位址空間按照自身邏輯關系劃分為若幹段（代碼段，資料段，堆棧段），記憶體空間被動态劃分為長度不同的區域，配置設定時以段為機關，每段在記憶體中占據連續空間，各段可以不相鄰。

段頁式存儲：使用者程序先按段劃分，段内再按頁劃分，記憶體劃分和配置設定頁。

分段和分頁的差別：

目的不同：分頁目的是管理記憶體，分段目的是滿足使用者需要，使得程式和資料可以被邏輯上劃分為獨立的位址空間。

大小不同：段大小不固定，由其所完成的功能決定。頁大小固定，由系統決定。

位址空間次元不同：分段是二維位址空間（段号+段内偏移），分頁是一維位址空間（每個程序一個頁表/多級頁表，通過一個邏輯位址就能找到對應的實體位址）

分段便于資訊的保護和共享，分頁的共享受到限制。

碎片：分段沒有碎片，但會産生外部碎片，分頁沒有外部碎片，但一頁填不滿時會産生内部碎片

什麼是虛拟記憶體？

每個程式都有自己的位址空間，位址空間被分成大小相等的頁，這些頁被映射到實體記憶體，但不需要所有的頁都在實體記憶體之中。程式引用到不在實體記憶體中的頁時，作業系統将缺失的部分裝入實體記憶體，這樣對程式來說邏輯記憶體上似乎有很大的空間，但實際上有一部分存儲在磁盤上。

虛拟記憶體讓程式可以獲得更多可用記憶體，虛拟記憶體有多種實作方式，頁表多級頁表，缺頁中斷，頁面淘汰算法等

如何進行位址空間到實體記憶體的映射？

記憶體管理單元：管理着邏輯位址和實體位址的轉換。

頁表：存儲頁（邏輯位址）和頁框（實體位址）的映射關系的表。包含有效位（是否在磁盤），通路位（是否被通路過），修改位（記憶體是否被修改過），保護位（隻讀還是可寫）。

邏輯位址：頁号+頁内偏移

每個程序一個頁表放在記憶體，頁表起始位址在程序寄存器中（PCB/寄存器中）

有哪些頁面置換算法？

最佳頁面置換：置換以後不需要或者最遠将來才需要的頁面

先進先出：置換記憶體中駐留時間最長的頁面，缺點：可能置換出經常被通路的頁面使缺頁率升高

第二次機會算法scr：按先進先出選擇一個頁面，如果通路位為1，給第二次機會并将通路位置零。

**時鐘算法：**scr需要将頁面從連結清單頭移動到連結清單尾，時鐘算法使用環形連結清單，再用一個指針指向最老頁面，避免移動頁面開銷

最近未使用算法：檢查通路位R，修改位M，優先置換R=M=0，其次是（R=0,M=1）

**最近最少使用算法LRU：**置換出未使用時間最長的一頁，實作方式是維護時間戳。或者維護一個所有頁面的連結清單，頁面被通路到時将該頁面移動到連結清單表頭，就能保證連結清單表尾頁面時最近最久未被使用的。

局部性原理：

空間：記憶體中被通路的頁面周圍的頁面也很可能被通路

時間：最近被通路的頁面不久的将來還會被通路

颠簸：

本質上是頻繁的頁面排程行為，記憶體裡所有的頁都在使用，置換一個頁，又立刻再次需要這個頁，是以不斷産生缺頁中斷，導緻系統效率下降。稱為颠簸。

修改頁面置換算法，降低程序數量，增加實體記憶體容量。

緩沖區溢出問題

緩沖區溢出是什麼？

資料被添加到配置設定給該緩沖區的記憶體塊之外。

防範緩沖區攻擊的方法：随機化（随機配置設定棧空間+将代碼段資料段棧堆等加載到記憶體不同區域），棧保護（棧幀局部變量和棧狀态間存儲一個随機産生的特殊值，檢測該值是否變化），限制可執行代碼區域（記憶體頁通路形式有三種：可讀，可寫，可執行，隻有編譯器産生那部分代碼的記憶體才可執行，其他隻允許讀和寫）。

磁盤排程

磁頭：找到對應的盤面。磁道：一個盤面上的同心圓環，尋道時間。扇區：旋轉時間。

為了減少尋道時間的排程算法。

先來先服務：

最短尋道時間優先：

電梯算法：電梯總是保持一個方向運作，直到該方向沒有請求為止，然後改變運作方向。

檔案系統挂載

linux中一切皆檔案，包括硬體裝置也是檔案，所有檔案放置在/ 為根目錄的樹形目錄檔案結構中，任何裝置也有一套自己的檔案目錄系統。

在使用任何硬體裝置時，硬體裝置本身有一套檔案系統，linux本身也有一套檔案系統，需要把這兩個系統合二為一才我們才能在linux中使用硬體裝置的檔案系統，這個過程就是挂載，感覺是建立硬體裝置系統到linux檔案系統的映射。就是将裝置檔案的根目錄映射到linux根目錄/下的某一個目錄（最好為空）。挂載到根目錄下的硬體裝置就成為linux根目錄下的一個子目錄，通路這個子目錄就是通路硬體的檔案系統。

在linux中使用任何硬體裝置都必須将硬體裝置和已有的檔案系統進行挂載。

cpu緩存

程式優化：CPU緩存基礎知識：https://zhuanlan.zhihu.com/p/80672073

為什麼cpu需要用到緩存：http://www.dnpz.net/diannaoyingjian/diannaoyingjianzhishi/2805.html

我的了解是這樣的，一般來說cpu讀取緩存中資料很快，讀取記憶體中資料很慢，此時如果cpu要使用一個記憶體中的資料，如果直接從記憶體中讀取，則必須等待很久，和處理這個資料需要的時間相比太久了，是以先将資料從記憶體讀取到緩存中，此時cpu可以幹别的事情，等到記憶體資料完全讀取到緩存中後，cpu再從緩存讀取該資料，由于緩存和cpu速度接近，可以很快的讀到cpu中而不必過多等待，節省了cpu對資料io的時間，提高cpu使用率。

在查找需要使用的資料時，現在緩存裡查找，如果有則直接使用，沒有再去記憶體中找，不然每次都去記憶體中找會浪費大量時間。

回調是什麼

有些函數要求傳入一個函數作為他的參數，好在合适的時候進行調用，這個被傳入的，後又被調用的函數就稱為回調函數。

一個觀點是：回調函數通常和應用處于同一抽象層（傳入什麼樣的回調函數是在應用級别決定的），回調就形成了一個高層調用底層，底層在傳回來調用高層的過程。這應該是回調最早的應用之處。

更廣義的，把底層函數改為中間函數，任何兩個程序之間想獲得類似上面的靈活性，都可以利用回調。