OS
* 內(nèi)核態(tài) vs 用戶態(tài)
* 進(jìn)程 vs 線程
* 進(jìn)程調(diào)度算法
* 進(jìn)程間通信的幾種方式
* OS死鎖相關(guān)的問題
* 什么是死鎖？哲學(xué)家就餐問題
* 死鎖的必要條件
* 死鎖的應(yīng)對方法
* 死鎖的檢測與恢復(fù)
* 死鎖的動態(tài)避免：銀行家算法
* 死鎖的靜態(tài)防止：破壞死鎖的必要條件之一
* 段頁式內(nèi)存管理
* 頁面置換算法
* 磁盤調(diào)度算法
* Linux系統(tǒng)常用的命令有哪些？是否會Shell,Python?*

內(nèi)核態(tài) vs 用戶態(tài)

進(jìn)程VS線程

• 根本區(qū)別：進(jìn)程是操作系統(tǒng)資源分配的基本單位，而線程是任務(wù)調(diào)度和執(zhí)行的基本單位

• 在開銷方面：每個(gè)進(jìn)程都有獨(dú)立的代碼和數(shù)據(jù)空間（程序上下文），程序之間的切換會有較大的開銷；線程可以看做輕量級的進(jìn)程，同一類線程共享代碼和數(shù)據(jù)空間，每個(gè)線程都有自己獨(dú)立的運(yùn)行棧和程序計(jì)數(shù)器（PC），線程之間切換的開銷小。

• 內(nèi)存分配方面：系統(tǒng)在運(yùn)行的時(shí)候會為每個(gè)進(jìn)程分配不同的內(nèi)存空間；而對線程而言，除了CPU外，系統(tǒng)不會為線程分配內(nèi)存（線程所使用的資源來自其所屬進(jìn)程的資源），線程組之間只能共享資源。

• 包含關(guān)系：沒有線程的進(jìn)程可以看做是單線程的，如果一個(gè)進(jìn)程內(nèi)有多個(gè)線程，則執(zhí)行過程不是一條線的，而是多條線（線程）共同完成的；線程是進(jìn)程的一部分，所以線程也被稱為輕權(quán)進(jìn)程或者輕量級進(jìn)程。

進(jìn)程調(diào)度算法

• 先來先服務(wù)調(diào)度算法FCFS：既可以作為作業(yè)調(diào)度算法也可以作為進(jìn)程調(diào)度算法；按作業(yè)或者進(jìn)程到達(dá)的先后順序依次調(diào)度；因此對于長作業(yè)比較有利；

• 短作業(yè)優(yōu)先調(diào)度算法SJF：作業(yè)調(diào)度算法，算法從就緒隊(duì)列中選擇估計(jì)時(shí)間最短的作業(yè)進(jìn)行處理，直到得出結(jié)果或者無法繼續(xù)執(zhí)行；缺點(diǎn)：不利于長作業(yè)；未考慮作業(yè)的重要性；運(yùn)行時(shí)間是預(yù)估的，并不靠譜 ；

• 高響應(yīng)比算法HRN：響應(yīng)比=(等待時(shí)間+要求服務(wù)時(shí)間)/要求服務(wù)時(shí)間；
  當(dāng)作業(yè)等待時(shí)間相同，服務(wù)時(shí)間少的優(yōu)先權(quán)高，短作業(yè)的優(yōu)先權(quán)越高，類似SJF
  當(dāng)服務(wù)時(shí)間相同，等待時(shí)間越長的優(yōu)先權(quán)高，類似FCFS
  長作業(yè)的優(yōu)先級隨著等待時(shí)間增加而增加，可以保證長作業(yè)一定會被運(yùn)行。

• 時(shí)間片輪轉(zhuǎn)調(diào)度RR：按到達(dá)的先后對進(jìn)程放入隊(duì)列中，然后給隊(duì)首進(jìn)程分配CPU時(shí)間片，時(shí)間片用完之后計(jì)時(shí)器發(fā)出中斷，暫停當(dāng)前進(jìn)程并將其放到隊(duì)列尾部，循環(huán) ;

• 多級反饋隊(duì)列調(diào)度算法：目前公認(rèn)較好的調(diào)度算法；設(shè)置多個(gè)就緒隊(duì)列并為每個(gè)隊(duì)列設(shè)置不同的優(yōu)先級，第一個(gè)隊(duì)列優(yōu)先級最高，其余依次遞減。優(yōu)先級越高的隊(duì)列分配的時(shí)間片越短，進(jìn)程到達(dá)之后按FCFS放入第一個(gè)隊(duì)列，如果調(diào)度執(zhí)行后沒有完成，那么放到第二個(gè)隊(duì)列尾部等待調(diào)度，如果第二次調(diào)度仍然沒有完成，放入第三隊(duì)列尾部…。只有當(dāng)前一個(gè)隊(duì)列為空的時(shí)候才會去調(diào)度下一個(gè)隊(duì)列的進(jìn)程。

進(jìn)程間通信的幾種方式

• 共享存儲
  進(jìn)程間存在一塊可直接訪問的共享空間，通過對這塊共享空間進(jìn)行讀/寫操作實(shí)現(xiàn)進(jìn)程之間的信息交換。

• 消息傳遞
  直接通信：發(fā)送進(jìn)程直接將消息發(fā)送給接收進(jìn)程
  間接通信：發(fā)送進(jìn)程把消息發(fā)送給某個(gè)中間實(shí)體，接收進(jìn)程從中間實(shí)體取得消息

• 管道通信
  連接一個(gè)寫進(jìn)程和一個(gè)讀進(jìn)程以實(shí)現(xiàn)進(jìn)程間通信的共享文件。

OS死鎖相關(guān)的問題

多進(jìn)程（線程）與死鎖，哲學(xué)家就餐問題

死鎖是指兩個(gè)或兩個(gè)以上的進(jìn)程（線程）在執(zhí)行過程中，因爭奪資源而造成的一種互相等待的現(xiàn)象，若無外力作用，它們都將無法推進(jìn)下去。

產(chǎn)生死鎖的原因：

• 因?yàn)橄到y(tǒng)資源不足。
• 進(jìn)程運(yùn)行推進(jìn)的順序不合適。
• 資源分配不當(dāng)。

死鎖的必要條件

• 互斥條件：所謂互斥就是進(jìn)程在某一時(shí)間內(nèi)獨(dú)占資源。
• 請求與保持條件：一個(gè)進(jìn)程因請求資源而阻塞時(shí)，對已獲得的資源保持不放。
• 不剝奪條件:進(jìn)程已獲得資源，在末使用完之前，不能強(qiáng)行剝奪。
• 循環(huán)等待條件:若干進(jìn)程之間形成一種頭尾相接的循環(huán)等待資源關(guān)系。

死鎖的應(yīng)對方法

死鎖的檢測與恢復(fù)

采用算法檢測死鎖，當(dāng)檢測到產(chǎn)生死鎖的進(jìn)程則強(qiáng)行剝奪資源，實(shí)現(xiàn)難度大

死鎖的動態(tài)避免：銀行家算法

預(yù)防死鎖的靜態(tài)防止：破壞死鎖的必要條件之一

• 打破互斥條件。即允許進(jìn)程同時(shí)訪問某些資源。但是，有的資源是不允許被同時(shí)訪問的，像打印機(jī)等等，這是由資源本身的屬性所決定的。所以，這種辦法并無實(shí)用價(jià)值。
• 打破不可搶占條件。即允許進(jìn)程強(qiáng)行從占有者那里奪取某些資源。就是說，當(dāng)一個(gè)進(jìn)程已占有了某些資源，它又申請新的資源，但不能立即被滿足時(shí)，它必須釋放所占有的全部資源，以后再重新申請。它所釋放的資源可以分配給其它進(jìn)程。這就相當(dāng)于該進(jìn)程占有的資源被隱蔽地強(qiáng)占了。這種預(yù)防死鎖的方法實(shí)現(xiàn)起來困難，會降低系統(tǒng)性能。
• 打破占有且申請條件?？梢詫?shí)行資源預(yù)先分配策略。即進(jìn)程在運(yùn)行前一次性地向系統(tǒng)申請它所需要的全部資源。如果某個(gè)進(jìn)程所需的全部資源得不到滿足，則不分配任何資源，此進(jìn)程暫不運(yùn)行。只有當(dāng)系統(tǒng)能夠滿足當(dāng)前進(jìn)程的全部資源需求時(shí)，才一次性地將所申請的資源全部分配給該進(jìn)程。由于運(yùn)行的進(jìn)程已占有了它所需的全部資源，所以不會發(fā)生占有資源又申請資源的現(xiàn)象，因此不會發(fā)生死鎖。
• 打破循環(huán)等待條件，實(shí)行資源有序分配策略。采用這種策略，即把資源事先分類編號，按號分配，使進(jìn)程在申請，占用資源時(shí)不會形成環(huán)路。所有進(jìn)程對資源的請求必須嚴(yán)格按資源序號遞增的順序提出。進(jìn)程占用了小號資源，才能申請大號資源，就不會產(chǎn)生環(huán)路，從而預(yù)防了死鎖。

段頁式內(nèi)存管理

頁面置換算法

• 最佳置換算法：淘汰最長未來時(shí)間不被訪問的頁面，只具有理論意義的算法，用來評價(jià)其他頁面置換算法。置換策略是將當(dāng)前頁面中在未來最長時(shí)間內(nèi)不會被訪問的頁置換出去。

  
  
  image.png

• 先進(jìn)先出置換算法：簡單粗暴的一種置換算法，沒有考慮頁面訪問頻率信息。每次淘汰最早調(diào)入的頁面。

• 最近最久未使用算法LRU：算法賦予每個(gè)頁面一個(gè)訪問字段，用來記錄上次頁面被訪問到現(xiàn)在所經(jīng)歷的時(shí)間t，每次置換的時(shí)候把t值最大的頁面置換出去(實(shí)現(xiàn)方面可以采用寄存器或者棧的方式實(shí)現(xiàn))。

  
  
  image.png

• 最近最少使用算法NRU

  
  
  image.png

• 改進(jìn)型Clock算法：在Clock算法的基礎(chǔ)上添加一個(gè)修改位，替換時(shí)根究訪問位和修改位綜合判斷。優(yōu)先替換訪問位和修改位都是0的頁面，其次是訪問位為0修改位為1的頁面。

• 最少使用算法LFU：設(shè)置寄存器記錄頁面被訪問次數(shù)，每次置換的時(shí)候置換當(dāng)前訪問次數(shù)最少的。