Python 調度算法 死鎖 靜動態鏈接 分頁分段

1 select poll epoll的區別
基本上select有3個缺點:

連接數受限
查找配對速度慢
數據由內核拷貝到用戶態
poll改善了第一個缺點

epoll改了三個缺點.

(1）select，poll實現需要自己不斷輪詢所有fd集合，直到設備就緒，期間可能要睡眠和喚醒多次交替。而epoll其實也需要調用epoll_wait不斷輪詢就緒鏈表，期間也可能多次睡眠和喚醒交替，但是它是設備就緒時，調用回調函數，把就緒fd放入就緒鏈表中，并喚醒在epoll_wait中進入睡眠的進程。雖然都要睡眠和交替，但是select和poll在“醒著”的時候要遍歷整個fd集合，而epoll在“醒著”的時候只要判斷一下就緒鏈表是否為空就行了，這節省了大量的CPU時間。這就是回調機制帶來的性能提升。

(2）select，poll每次調用都要把fd集合從用戶態往內核態拷貝一次，并且要把current往設備等待隊列中掛一次，而epoll只要一次拷貝，而且把current往等待隊列上掛也只掛一次（在epoll_wait的開始，注意這里的等待隊列并不是設備等待隊列，只是一個epoll內部定義的等待隊列）。這也能節省不少的開銷。

2 調度算法
調度算法是指：根據系統的資源分配策略所規定的資源分配算法。

先來先服務(FCFS, First Come First Serve)
短作業優先(SJF, Shortest Job First)
最高優先權調度(Priority Scheduling)
時間片輪轉(RR, Round Robin)
多級反饋隊列調度(multilevel feedback queue scheduling)
實時調度算法:

最早截至時間優先 EDF
最低松弛度優先 LLF
一、FCFS——先來先服務和短作業（進程）優先調度算法

先來先服務調度算法。
先來先服務（FCFS）調度算法是一種最簡單的調度算法，該算法既可用于作業調度， 也可用于進程調度。FCFS算法比較有利于長作業（進程），而不利于短作業（進程）。由此可知，本算法適合于CPU繁忙型作業， 而不利于I/O繁忙型的作業（進程）。

短作業（進程）優先調度算法。
短作業（進程）優先調度算法（SJ/PF）是指對短作業或短進程優先調度的算法，該算法既可用于作業調度， 也可用于進程調度。但其對長作業不利；不能保證緊迫性作業（進程）被及時處理；作業的長短只是被估算出來的。

二、FPF高優先權優先調度算法

優先權調度算法的類型。
為了照顧緊迫性作業，使之進入系統后便獲得優先處理，引入了最高優先權優先（FPF）調度算法。 此算法常被用在批處理系統中，作為作業調度算法，也作為多種操作系統中的進程調度，還可以用于實時系統中。當其用于作業調度， 將后備隊列中若干個優先權最高的作業裝入內存。當其用于進程調度時，把處理機分配給就緒隊列中優先權最高的進程，此時， 又可以進一步把該算法分成以下兩種：

1)非搶占式優先權算法

2)搶占式優先權調度算法（高性能計算機操作系統）

? 2.優先權

對于最高優先權優先調度算法，其核心在于：它是使用靜態優先權還是動態優先權， 以及如何確定進程的優先權。

? 3.動態優先權

高響應比優先調度算法為了彌補短作業優先算法的不足，我們引入動態優先權，使作業的優先等級隨著等待時間的增加而以速率a提高。 該優先權變化規律可描述為：優先權=（等待時間+要求服務時間）/要求服務時間；即 =（響應時間）/要求服務時間

三、基于時間片的輪轉調度算法

1.時間片輪轉法。

時間片輪轉法一般用于進程調度，每次調度，把CPU分配隊首進程，并令其執行一個時間片。 當執行的時間片用完時，由一個記時器發出一個時鐘中斷請求，該進程被停止，并被送往就緒隊列末尾；依次循環。

多級反饋隊列調度算法
多級反饋隊列調度算法多級反饋隊列調度算法，不必事先知道各種進程所需要執行的時間，它是目前被公認的一種較好的進程調度算法。 其實施過程如下：

1) 設置多個就緒隊列，并為各個隊列賦予不同的優先級。在優先權越高的隊列中， 為每個進程所規定的執行時間片就越小。

2) 當一個新進程進入內存后，首先放入第一隊列的末尾，按FCFS原則排隊等候調度。 如果他能在一個時間片中完成，便可撤離；如果未完成，就轉入第二隊列的末尾，在同樣等待調度…… 如此下去，當一個長作業（進程）從第一隊列依次將到第n隊列（最后隊列）后，便按第n隊列時間片輪轉運行。

3) 僅當第一隊列空閑時，調度程序才調度第二隊列中的進程運行；

僅當第1到第（ i-1 ）隊列空時， 才會調度第i隊列中的進程運行，并執行相應的時間片輪轉。

4) 如果處理機正在處理第i隊列中某進程，又有新進程進入優先權較高的隊列， 則此新隊列搶占正在運行的處理機，并把正在運行的進程放在第i隊列的隊尾。

3 死鎖
在多道程序系統中，由于多個進程的并發執行，改善了系統資源的利用率并提高了系統的處理能力。然而，多個進程的并發執行也帶來了新的問題——死鎖。所謂死鎖是指多個進程因競爭資源而造成的一種僵局，若無外力作用，這些進程都將無法向前推進。

死鎖產生的原因: 1）系統資源的競爭 2）進程推進順序非法(程序推進順序不當)

死鎖產生的條件: 互斥條件 不剝奪條件 請求和保持條件 循環等待條件

處理死鎖的基本方法:

預防死鎖(摒棄除1以外的條件)
避免死鎖(銀行家算法)
檢測死鎖(資源分配圖)
解除死鎖 : 死鎖的接觸方法 : 剝奪資源 撤銷進程 進程回退
4 程序的編譯與鏈接
Bulid過程可以分解為4個步驟:預處理(Prepressing), 編譯(Compilation)、匯編(Assembly)、鏈接(Linking)

以c語言為例:

1 預處理
預編譯過程主要處理那些源文件中的以“#”開始的預編譯指令，主要處理規則有：

將所有的“#define”刪除，并展開所用的宏定義
處理所有條件預編譯指令，比如“#if”、“#ifdef”、 “#elif”、“#endif”
處理“#include”預編譯指令，將被包含的文件插入到該編譯指令的位置，注：此過程是遞歸進行的
刪除所有注釋
添加行號和文件名標識，以便于編譯時編譯器產生調試用的行號信息及用于編譯時產生編譯錯誤或警告時可顯示行號
保留所有的#pragma編譯器指令。
2 編譯
編譯過程就是把預處理完的文件進行一系列的詞法分析、語法分析、語義分析及優化后生成相應的匯編代碼文件。這個過程是整個程序構建的核心部分。

3 匯編
匯編器是將匯編代碼轉化成機器可以執行的指令，每一條匯編語句幾乎都是一條機器指令。經過編譯、鏈接、匯編輸出的文件成為目標文件(Object File).

4 鏈接
鏈接的主要內容就是把各個模塊之間相互引用的部分處理好，使各個模塊可以正確的拼接。
鏈接的主要過程包塊 地址和空間的分配（Address and Storage Allocation）、符號決議(Symbol Resolution)和重定位(Relocation)等步驟。

5 靜態鏈接與動態鏈接
靜態鏈接方法：靜態鏈接的時候，載入代碼就會把程序會用到的動態代碼或動態代碼的地址確定下來
靜態庫的鏈接可以使用靜態鏈接，動態鏈接庫也可以使用這種方法鏈接導入庫

動態鏈接方法：使用這種方式的程序并不在一開始就完成動態鏈接，而是直到真正調用動態庫代碼時，載入程序才計算(被調用的那部分)動態代碼的邏輯地址，等到某個時候，程序又需要調用另外某塊動態代碼時，載入程序又去計算這部分代碼的邏輯地址，所以這種方式使程序初始化時間較短，但運行期間的性能比不上靜態鏈接的程序

6 虛擬內存技術與分頁分段
虛擬存儲器是指具有請求調入功能和置換功能,能從邏輯上對內存容量加以擴充的一種存儲系統.

分頁: 用戶程序的地址空間被劃分成若干固定大小的區域，稱為“頁”，相應地，內存空間分成若干個物理塊，頁和塊的大小相等。可將用戶程序的任一頁放在內存的任一塊中，實現了離散分配。

分段: 將用戶程序地址空間分成若干個大小不等的段，每段可以定義一組相對完整的邏輯信息。存儲分配時，以段為單位，段與段在內存中可以不相鄰接，也實現了離散分配。

分頁與分段的主要區別
頁是信息的物理單位,分頁是為了實現非連續分配,以便解決內存碎片問題,或者說分頁是由于系統管理的需要.段是信息的邏輯單位,它含有一組意義相對完整的信息,分段的目的是為了更好地實現共享,滿足用戶的需要.
頁的大小固定,由系統確定,將邏輯地址劃分為頁號和頁內地址是由機器硬件實現的.而段的長度卻不固定,決定于用戶所編寫的程序,通常由編譯程序在對源程序進行編譯時根據信息的性質來劃分.
分頁的作業地址空間是一維的.分段的地址空間是二維的.
頁面置換算法
最佳置換算法OPT:不可能實現
先進先出FIFO
clock算法
邊沿觸發和水平觸發

邊緣觸發是指每當狀態變化時發生一個 io 事件，條件觸發是只要滿足條件就發生一個 io 事件