進程和線程

進程和線程的區別

線程具有許多傳統進程所具有的特征，故又稱為輕型進程(Light—Weight Process)或進程元；而把傳統的進程稱為重型進程(Heavy—Weight Process)，它相當于只有一個線程的任務。在引入了線程的操作系統中，通常一個進程都有若干個線程，至少包含一個線程。

根本區別：進程是操作系統資源分配的基本單位，而線程是處理器任務調度和執行的基本單位

資源開銷：每個進程都有獨立的代碼和數據空間（程序上下文），程序之間的切換會有較大的開銷；線程可以看做輕量級的進程，同一類線程共享代碼和數據空間，每個線程都有自己獨立的運行棧和程序計數器（PC），線程之間切換的開銷小。

包含關系：如果一個進程內有多個線程，則執行過程不是一條線的，而是多條線（線程）共同完成的；線程是進程的一部分，所以線程也被稱為輕權進程或者輕量級進程。

內存分配：同一進程的線程共享本進程的地址空間和資源，而進程之間的地址空間和資源是相互獨立的

影響關系：一個進程崩潰后，在保護模式下不會對其他進程產生影響，但是一個線程崩潰整個進程都死掉。所以多進程要比多線程健壯。

執行過程：每個獨立的進程有程序運行的入口、順序執行序列和程序出口。但是線程不能獨立執行，必須依存在應用程序中，由應用程序提供多個線程執行控制，兩者均可并發執行

進程的狀態轉換

三種基本狀態：

運行態：占用CPU，并在CPU上運行

就緒態：已經具備了運行條件，但由于沒有空閑的CPU，而暫時不能運行

阻塞態：因等待某一事件而暫時不能運行

另外兩種狀態：

創建態：進程正在被創建，操作系統為進程分配資源，初始化PCB

進程正在從系統中撤銷，操作系統會回收進程擁有的資源，撤銷PCB

進程間的通信

對于同步和互斥的理解：

區別：

互斥：是指三部在不同進程之間的若干程序片斷，當某個進程運行其中一個程序片段時，其它進程就不能運行它們之中的任一程序片段，只能等到該進程運行完這個程序片段后才可以運行。

同步：是指散步在不同進程之間的若干程序片斷，它們的運行必須嚴格按照規定的 某種先后次序來運行，這種先后次序依賴于要完成的特定的任務。

聯系：

同步是一種更為復雜的互斥，而互斥是一種特殊的同步。也就是說互斥是兩個線程之間不可以同時運行，他們會相互排斥，必須等待一個線程運行完畢，另一個才能運行，而同步也是不能同時運行，但他是必須要安照某種次序來運行相應的線程（也是一種互斥）。

進程間為什么需要通信

在操作系統中，協作的進程可能共享一些彼此都能共同讀寫的一些有限資源。而這些資源是有限的，或者如一些共享內存，進程隨意讀寫可能會造成數據的順序，內容等發生錯亂，進程不能對其隨意的使用，讀寫等。從而會發生競爭。我們把對共享內存進行訪問的程序片稱為臨界資源或臨界區，對同一共享內存，任何時候兩個進程不能同時處于臨界區.

進程間通信的目的：

數據傳輸：一個進程需要將它的數據發送給另一個進程。

通知事件：一個進程需要向另一個或一組進程發送消息，通知它（它們）發生了某種事件（如進程終止時要通知父進程）。

資源共享：多個進程之間共享同樣的資源。為了做到這一點，需要內核提供互斥和同步機制。

進程控制：有些進程希望完全控制另一個進程的執行（如 Debug 進程），此時控制進程希望能夠攔截另一個進程的所有陷入和異常，并能夠及時知道它的狀態改變

進程間通信的方式

1.管道通信：

管道只能采取半雙工通信，某一時間段內只能實現單向的傳輸。如果要實現雙向同時通信，則需要設置兩個管道

各個進程要互斥的訪問管道

數據以字節流的形式寫入管道，當管道寫滿時，寫進程的write()系統調用將會被阻塞，等待讀進程將數據取走。當讀進程將數據全部取走后，管道變空，此時讀進程的read()系統調用將會被阻塞

注意：匿名管道只能用于有親緣關系間的進程，而有名管道允許無親緣關系的進程間通信

2.消息隊列MessageQueue：

消息隊列是由消息的鏈表，存放在內核中并由消息隊列標識符標識。消息隊列克服了信號傳遞信息少、管道只能承載無格式字節流以及緩沖區大小受限等缺點。

3.信號

信號是進程之間唯一的異步通信機制，信號的主要來源主要有硬件來源（入鍵盤操作ctrl + C） 和軟件來源（如kill命令），信號傳遞的信息比較少，主要用于通知進程某個時間已經發生。比如利用kill pid，可以讓系統優雅停機。

4.信號量

信號量是一個計數器，可以用來控制多個進程對資源的訪問，通常作為一種鎖機制，防止某個進程正在訪問共享資源，其他進程也訪問資源

5.共享內存

共享內存就是映射一段能被進程之間共享的內存，這段內存由一個進程創建，但是多個進程都可以共享訪問，是最快的一種進程間通信的方式（不需要從用戶態到內核態的切換），它是針對其他進程間通信方式運行效率低而專門設計的。它往往與其他通信機制，如信號量，配合使用，來實現進程間的同步和通信。

6.Socket

socket套接字，不僅僅可以用于本地進程通信，還可以用于不通主機進程之間的通信。

進程的調度和處理機調度

進程調度(低級調度)，就是按照某種算法，從就緒隊列中選擇一個進程為其分配處理機

進程調度的時機

進程主動放棄處理機：進程正常終止，發生異常終止，進程主動請求阻塞(如等待I/O)等

進程被動放棄處理機：分配的時間片用完，IO中斷，有更高的優先級進程進入就緒隊列等

調度算法

設置多級就緒隊列，各級的隊列優先級從高到低，時間片從小到大

新進程到達時先進入第一級隊列，按照先來先服務排隊等待被分配時間片，若用完時間片進程還未結束，則進程進入下一級隊列的隊尾，如果此時已經在最下級隊列，則從新放回最后一級隊列的隊尾

只有當第K級的隊列為空時，才會為K+1級的隊列隊頭的進程分配時間片

先來先服務

最短作業優先

最高響應比優先 響應比：(等待時間+服務時間)/要求服務的時間

時間片輪轉調度

優先級調度

多級反饋隊列

內存管理

內存管理的功能

內存空間的分配與回收：由操作系統完成主存儲器空間的分配和管理，使程序員擺脫存儲分配的麻煩，提高編程效率。

地址轉換：在多道程序環境下， 程序中的邏輯地址與內存中的物理地址不可能一致， 因此存儲管理必須提供地址變換功能，把邏輯地址轉換成相應的物理地址。

內存空間的擴充：利用虛擬存儲技術或自動覆蓋技術，從邏輯上擴充內存 。

存儲保護：保證各道作業在各自的存儲空間內運行，互不干擾。

內存分配方式

連續分配管理方式

連續分配方式，是指為一個用戶程序分配一個連續的內存空間，比如說某用戶需要1GB的內存空間，它就在內存空間中分配一塊連續的 1GB的空間給用戶。

單一連續分配：內存在此方式下分為系統區和用戶區，系統區僅提供給操作系統使用，通常在低地址部分；用戶區是為用戶提供的、除系統區之外的內存空間。這種方式無需進行內存保護。

固定分區分配：固定分區分配是最簡單的一種多道程序存儲管理方式，它將用戶內存空間劃分為若干個固定大小的區域，每個分區只裝入一道作業。當有空閑分區時，便可以再從外存的后備作業隊列中， 選擇適當大小的作業裝入該分區，如此循環。

動態分區分配：動態分區分配又稱為可變分區分配，是一種動態劃分內存的分區方法。這種分區方法不預先將內存劃分，而是在進程裝入內存時，根據進程的大小動態地建立分區 ，并使分區的大小正好適合進程的需要。因此系統中分區的大小和數目是可變的。

分配策略算法

首次適應 (First Fit) 算法：空閑分區以地址遞增的次序鏈接。分配內存時順序查找，找到大小能滿足要求的第一個空閑分區。

最佳適應 ( Best Fit )算法：空閑分區按容量遞增形成分區鏈，找到第一個能滿足要求的空閑分區。

最壞適應 ( Worst Fit )算法：又稱最大適應 （ Largest Fit )算法，空閑分區以容量遞減的次序鏈接。找到第一個能滿足要求的空閑分區，也就是挑選出最大的分區。

鄰近適應 ( Next Fit )算法：又稱循環首次適應算法，由首次適應算法演變而成。不同之處是分配內存時從上次查找結束的位置開始繼續查找。

非連續分配管理方式

非連續分配允許一個程序分散地裝入到不相鄰的內存分區中

分頁存儲管理方式

將內存空間分為一個個大小相等的分區(比如：每個分區4KB)，每個分區就是一個頁框(頁幀，內存塊，物理塊)，每個頁框都有一個編號，即頁框號(頁幀號，內存塊號，物理塊號)，頁框號從0開始

將用戶進程的地址空間也分為與頁框大小相等的一個個區域，稱為 "頁"或 “頁面”，每個頁面也有一個編號，即頁號，頁號也是從0開始(注意：進程最后一個頁面可能沒有頁框那么大，因此頁框不能太大，否則會產生過大的內部碎片)

操作系統以頁框為單位為各個進程分配內存空間。進程的每個頁面分別放入一個頁框中，則進程的頁面和內存的頁框產生了一一對應的關系

分段存儲管理方式

進程的地址空間：按照程序自身的邏輯關系劃分為若干個段，每個段都有一個段名(在低級語言中，程序員使用段名來編程)，每段從0開始編址

內存分配規則：以段位單位進行分配，每個段在內存中占據連續空間，但是各個段之間可以不相鄰

優點：由于是按邏輯功能劃分，用戶編程更加方便，程序的可讀性更高

分頁和分段存儲管理的區別

頁是信息的物理單位，分頁是為實現離散分配方式，提高內存利用率。分頁僅僅是由于系統管理的需要而并不是用戶的需要。而段則是信息的邏輯單位，是為了更好地滿足用戶的需要。

分段比分頁更容易實現信息的保護與共享，分段可以在某個段編寫邏輯，實現對另外一個段的保護，而分頁不行

頁的大小固定且由系統決定，而段的長度取決于用戶所編寫的程序。

頁面置換算法(追求最少的缺頁率)

最佳置換算法OPT(無法實現，作為一個標準):每次選擇淘汰的頁面將是以后永不使用，或者在最長的時間內不被使用，由于無法預知將會訪問哪些頁面，所以這種算法無法實現，只能作為一個標準

例如：需要訪問7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1，則訪問順序：

先進先出置換算法FIFO:每次選擇淘汰的頁面是最早進入內存的頁面

例如：需要訪問 3 2 1 0 3 2 4 3 2 1 0 4 ，則訪問順序

最近最久未使用置換算法(LRU)：每次淘汰的頁面是最近最久未使用的頁面

例如：需要訪問 1 8 1 7 8 2 7 2 1 8 3 8 2 1 3 1 7 1 3 7 則訪問順序

最近未用置換算法NRU(Clock算法):為每個頁面設置一個訪問位，再將內存中的頁面都通過鏈接指針鏈接成一個循環隊列。當某頁被訪問時，其訪問位置為1.當需要淘汰某個頁面時，只需要檢查頁的訪問位。如果是0，就將該頁面換出，如果是1，則將他置為0，暫不換出。繼續檢查下一個頁面，如果第一輪掃描之后全是1，則掃描完成，這些都置為0.再進行第二輪掃描，因此簡單的Clock算法選擇一個頁面淘汰最多兩輪

文件管理

文件的分配方式(物理結構)

文件塊和磁盤塊：類似于內存的分頁

磁盤塊:磁盤中的存儲單元會被分為一個個"塊/磁盤塊/物理塊"，在很多的操作系統中，磁盤塊的大小與內存塊，頁面的大小相同

文件塊：在外存管理中，為了方便對文件數據的管理，文件的邏輯地址空間被分為一個一個的文件塊，文件的邏輯地址可以表示為(邏輯塊號，塊內地址)的形式。用戶通過邏輯地址來操作自己的文件，操作

文件的分配方式

連續分配：要求每個文件在磁盤上占有一組連續的塊

優點：支持順序訪問和直接訪問(類似數組)，連續分配的文件在順序訪問時速度最快

缺點：不方便文件的擴展，存儲空間利用率低,會產生磁盤碎片

鏈接分配：采取離散分配的方式，為文件分配離散的磁盤塊。(類似鏈表數據結構)

隱式鏈接：目錄中記錄的文件的起始塊號和結束塊號。除了文件最后一個磁盤塊之外，每個磁盤塊中都會保存指向下一個盤塊的指針，這些指針對用戶是透明的,每次訪問某個磁盤塊都需從頭訪問

優點：方便文件的擴展，不會產生碎片問題，外存的利用率高

缺點：只支持順序訪問，不支持隨機訪問，查找時效率低

*顯示鏈接：把用于鏈接文件各物理塊的指針顯示的存放在一張表中，即文件分配表。文件目錄只需要記錄起始塊號。一個磁盤只需要設置一張分配表，開機時，將分配表讀入內存，并常駐內存 *優點：支持順序訪問，也支持隨機訪問，方便文件的擴展，不會產生碎片問題，地址轉換不需要訪問磁盤，因此文件的訪問效率更高 *缺點：文件分配表需要占據一定的存儲空間

索引分配：索引分配允許文件離散的分配在各個磁盤塊中，系統會為每個文件建立一張索引表，索引表中記錄了文件的各個邏輯塊對應的物理塊(索引表的功能類似于內存管理的頁表–建立邏輯頁面到物理頁面之間的映射關系)。索引表存放的磁盤塊稱為索引塊，文件數據存放的磁盤塊稱為數據塊

文件存儲空間管理

存儲空間的劃分和初始化

存儲空間的劃分：將物理磁盤劃分為一個個文件卷(邏輯卷，邏輯盤，如Windows系統下的C，D，E盤等)

有的系統支持超大型文件，可由多個物理磁盤組成一個文件卷

存儲空間的初始化：將各個文件卷劃分為目錄區，文件區

目錄區：目錄區主要存放文件的目錄信息(FCB)，用于磁盤存儲空間的管理的信息

文件區：文件區用于存放文件數據

存儲空間的管理方法

空閑表法：與內存管理中的動態分區分配很類似，為一個文件分配連續的存儲空間。同樣可以采用首次適應，最佳適應，最壞適應等算法來決定要為文件分配哪個區間

空閑鏈表法：分為—>

空閑盤塊鏈：以盤塊為單位組成一條空閑鏈

空閑盤區鏈：以盤區為單位組成一條空閑鏈

位示圖法：每個二進制位代表一個盤塊。例如可以用"0"來代表盤塊空閑 ，"1"代表盤塊已經分配

成組鏈接法：UNIX采用的策略，適合大型的文件系統。

IO管理

磁盤調度算法

一次磁盤讀/寫操作需要的時間：尋找時間+延遲時間+傳輸時間

尋找時間：在讀/寫前，將磁頭移動到指定磁道所畫的時間(啟動磁頭臂和移動磁頭臂)

延遲時間：通過旋轉磁盤，使磁頭定位到目標扇區所需要的時間

傳輸時間：從磁盤中讀出或寫入數據所經歷的時間

磁盤調度算法：

先來先服務算法(FIFO)：根據進程請求訪問磁盤的先后順序進行調度

最短尋找時間優先算法(SSTF)：優先處理的磁道是與當前磁道最近的磁道，可以保證每次的尋道時間最短，但是不能保證總的尋道時間最短(貪心算法)

掃描算法(SCAN，電梯調度算法)：SSTF算法可能會產生饑餓，磁頭有可能在一個小區域內來回移動，因此掃描算法規定，只有磁頭移動到最外側磁道的時候才能往內移動，移動到最內側磁道才能往外移動，在這個基礎上使用SSTF算法

循環掃描算法(C-SCAN)：SCAN算法對于各個位置磁道的響應頻率不平均，C-SCAN算法在SCAN算法的基礎上規定：只有磁頭朝著某個特定的方向移動時才能處理磁道的訪問請求，而返回時直接快速移動到起始端而不處理任何請求

死鎖

對死鎖的理解

如果一組進程中的每個進程都在等待一個事件，而這個事件是有這組中的某一個進程觸發，這種情況則會導致死鎖

資源死鎖的條件：發生死鎖時，以下四個條件必須全部具備

互斥條件：進程要求對所分配的資源進行排它性控制，即在一段時間內某資源僅為一進程所占用。

保持和等待條件：當進程因請求資源而阻塞時，對已獲得的資源保持不放。

不可搶占條件：進程已獲得的資源在未使用完之前，不能剝奪，只能在使用完時由自己釋放。

循環等待條件：在發生死鎖時，必然存在一個進程–資源的環形鏈。

死鎖的避免->銀行家算法

當一個進程申請使用資源的時候，銀行家算法通過先 試探 分配給該進程資源，然后通過安全性算法判斷分配后的系統是否處于安全狀態，若不安全則試探分配作廢，讓該進程繼續等待。

安全序列的判斷：

死鎖的解除

資源剝奪法：掛起(暫時放到外存上)某些死鎖的進程，并搶占他的資源，將這些資源分配給其他的死鎖進程。但是應防止被掛起的進程長時間得不到資源而饑餓

撤銷進程法：強制撤銷部分，甚至全部的死鎖進程，并剝奪這些進程的資源。雖然實現簡單，但是代價可能較大

進程回退法：讓一個或多個死鎖進程回退到足以避免死鎖的地步

簡單來說，死鎖的破壞就是對死鎖產生的四個條件進行破壞，讓其中任意一個不滿足即可。

審核編輯 ：李倩