標籤：

整理一些計算機基礎知識！

08-10
整理一些計算機基礎知識！

來自專欄大數據分析挖掘24 人贊了文章

作者：石曉文 Python愛好者社區專欄作者

個人公眾號：小小挖掘機

博客專欄：wenwen

本文涉及的內容有：

網路層次劃分／TCP／IP協議、三次握手和四次握手／進程與線程／進程調度演算法／死鎖／高速緩存Cache／最近最久未使用置換演算法LRU的JAVA實現

1、網路層次劃分

為了使不同計算機廠家生產的計算機能夠相互通信，以便在更大的範圍內建立計算機網路，國際標準化組織（ISO）在1978年提出了「開放系統互聯參考模型」，即著名的OSI/RM模型（Open System Interconnection/Reference Model）。它將計算機網路體系結構的通信協議劃分為七層，自下而上依次為：物理層（Physics Layer）、數據鏈路層（Data Link Layer）、網路層（Network Layer）、傳輸層（Transport Layer）、會話層（Session Layer）、表示層（Presentation Layer）、應用層（Application Layer）。其中第四層完成數據傳送服務，上面三層面向用戶。

除了標準的OSI七層模型以外，常見的網路層次劃分還有TCP/IP四層協議以及TCP/IP五層協議，它們之間的對應關係如下圖所示：

2、TCP／IP協議、三次握手和四次握手

TCP/IP協議是Internet最基本的協議、Internet國際互聯網路的基礎，由網路層的IP協議和傳輸層的TCP協議組成。通俗而言：TCP負責發現傳輸的問題，一有問題就發出信號，要求重新傳輸，直到所有數據安全正確地傳輸到目的地。而IP是給網際網路的每一台聯網設備規定一個地址。

TCP協議中有著名的三次握手和四次握手規則，如下圖所示：

註：seq:"sequance"序列號；ack:"acknowledge"確認號；SYN:"synchronize"請求同步標誌；；ACK:"acknowledge"確認標誌"；FIN："Finally"結束標誌。

TCP連接建立過程

首先Client端發送連接請求報文，Server段接受連接後回復ACK報文，並為這次連接分配資源。Client端接收到ACK報文後也向Server段發生ACK報文，並分配資源，這樣TCP連接就建立了。

TCP連接斷開過程

假設Client端發起中斷連接請求，也就是發送FIN報文。Server端接到FIN報文後，意思是說"我Client端沒有數據要發給你了"，但是如果你還有數據沒有發送完成，則不必急著關閉Socket，可以繼續發送數據。所以你先發送ACK，"告訴Client端，你的請求我收到了，但是我還沒準備好，請繼續你等我的消息"。這個時候Client端就進入FIN_WAIT狀態，繼續等待Server端的FIN報文。當Server端確定數據已發送完成，則向Client端發送FIN報文，"告訴Client端，好了，我這邊數據發完了，準備好關閉連接了"。Client端收到FIN報文後，"就知道可以關閉連接了，但是他還是不相信網路，怕Server端不知道要關閉，所以發送ACK後進入TIME_WAIT狀態，如果Server端沒有收到ACK則可以重傳。「，Server端收到ACK後，"就知道可以斷開連接了"。Client端等待了2MSL後依然沒有收到回復，則證明Server端已正常關閉，那好，我Client端也可以關閉連接了。Ok，TCP連接就這樣關閉了！

為什麼要三次握手？

在只有兩次「握手」的情形下，假設Client想跟Server建立連接，但是卻因為中途連接請求的數據報丟失了，故Client端不得不重新發送一遍；這個時候Server端僅收到一個連接請求，因此可以正常的建立連接。但是，有時候Client端重新發送請求不是因為數據報丟失了，而是有可能數據傳輸過程因為網路並發量很大在某結點被阻塞了，這種情形下Server端將先後收到2次請求，並持續等待兩個Client請求向他發送數據...問題就在這裡，Cient端實際上只有一次請求，而Server端卻有2個響應，極端的情況可能由於Client端多次重新發送請求數據而導致Server端最後建立了N多個響應在等待，因而造成極大的資源浪費！所以，「三次握手」很有必要！

為什麼要四次握手？

試想一下，假如現在你是客戶端你想斷開跟Server的所有連接該怎麼做？第一步，你自己先停止向Server端發送數據，並等待Server的回復。但事情還沒有完，雖然你自身不往Server發送數據了，但是因為你們之前已經建立好平等的連接了，所以此時他也有主動權向你發送數據；故Server端還得終止主動向你發送數據，並等待你的確認。其實，說白了就是保證雙方的一個合約的完整執行！

3、進程與線程

定義

進程是具有一定獨立功能的程序關於某個數據集合上的一次運行活動,進程是系統進行資源分配和調度的一個獨立單位.

線程：當一個進程內有多個線程時，線程的程序是其所屬進程的一部分，表示進程中的一個控制點，執行一系列的指令。同屬一個進程的其他的線程共享進程所擁有的全部資源（包括地址空間）。它是比進程更小的能獨立運行的基本單位.線程自己基本上不擁有系統資源,只擁有一點在運行中必不可少的資源(如程序計數器,一組寄存器和棧)，因此，它的創建、撤銷、切換所需要的時空開銷比進程要小。線程的引入可進一步提高系統的並發性。

區別

進程和線程的主要差別在於它們是不同的操作系統資源管理方式。進程有獨立的地址空間，一個進程崩潰後，在保護模式下不會對其它進程產生影響，而線程只是一個進程中的不同執行路徑。線程有自己的堆棧和局部變數，但線程之間沒有單獨的地址空間，一個線程死掉就等於整個進程死掉，所以多進程的程序要比多線程的程序健壯，但在進程切換時，耗費資源較大，效率要差一些。但對於一些要求同時進行並且又要共享某些變數的並發操作，只能用線程，不能用進程。

調度分派：線程是可調度分派的工作單元，它包括處理器上下文環境和棧中自己的數據區域。線程順序執行，並且可以中斷，這樣處理器可以轉到另一個線程。在有線程的系統中，進程不再是可調度分派的工作單元。

資源擁有：進程是一個或多個線程和相關資源的集合。線程基本不擁有資源，它的運行資源取決於其所屬的進程。

地址空間：不同進程的地址空間是相互獨立的，而同一個進程的各線程共享同一地址空間。

一個進程可包含一個或多個線程，反過來則不然。一個進程中的線程在另一個進程中時不可見的。

通信關係：進程間的通信必須使用操作系統提供的進程間通信機制，而同一個進程中的各線程間可以通過直接讀寫數據段來進行通信。當然，同一個進程中的各線程間的通信也需要同步和互斥手段的輔助，以確保數據一致性。

4、進程調度演算法

（1）先來先服務（FCFS，First-Come-First-Served）: 此演算法的原則是按照作業到達後備作業隊列（或進程進入就緒隊列）的先後次序來選擇作業（或進程）。

（2）短作業優先（SJF,Shortest Process Next）：這種調度演算法主要用於作業調度，它從作業後備隊列中挑選所需運行時間（估計值）最短的作業進入主存運行。

（3）時間片輪轉調度演算法（RR，Round-Robin）：當某個進程執行的時間片用完時，調度程序便停止該進程的執行，並將它送就緒隊列的末尾，等待分配下一時間片再執行。然後把處理機分配給就緒隊列中新的隊首進程，同時也讓它執行一個時間片。這樣就可以保證就緒隊列中的所有進程，在一給定的時間內，均能獲得一時間片處理機執行時間。

（4）高響應比優先（HRRN，Highest Response Ratio Next）: 按照高響應比（（已等待時間＋要求運行時間）/ 要求運行時間）優先的原則，在每次選擇作業投入運行時，先計算此時後備作業隊列中每個作業的響應比RP然後選擇其值最大的作業投入運行。

（5）優先權(Priority)調度演算法: 按照進程的優先權大小來調度，使高優先權進程得到優先處理的調度策略稱為優先權調度演算法。

（6） 多級隊列調度演算法：多隊列調度是根據作業的性質和類型的不同，將就緒隊列再分為若干個子隊列，所有的作業（或進程）按其性質排入相應的隊列中，而不同的就緒隊列採用不同的調度演算法。

5、死鎖

什麼是死鎖

在兩個或多個並發進程中，如果每個進程持有某種資源而又都等待別的進程釋放它或它們現在保持著的資源，在未改變這種狀態之前都不能向前推進，稱這一組進程產生了死鎖。通俗地講，就是兩個或多個進程被無限期地阻塞、相互等待的一種狀態。

產生死鎖的原因

死鎖產生的原因主要是：1、 系統資源不足；2、進程推進順序非法。

產生死鎖有四個必要條件：

（1）互斥：一個資源每次只能被一個進程使用；

（2）不可搶佔進程已獲得的資源，在未使用完之前，不能強行剝奪；

（3）佔有並等待一個進程因請求資源而阻塞時，對已獲得的資源保持不放；

（4）環形等待若干進程之間形成一種首尾相接的循環等待資源關係。

這四個條件是死鎖的必要條件，只要系統發生死鎖，這些條件必然成立，而只要上述條件之一不滿足，就不會發生死鎖。

如何避免死鎖

理解了死鎖的原因，尤其是產生死鎖的四個必要條件，就可以最大可能地避免、預防和解除死鎖。所以，在系統設計、進程調度等方面注意如何不讓這四個必要條件成立，如何確定資源的合理分配演算法，避免進程永久佔據系統資源。此外，也要防止進程在處於等待狀態的情況下佔用資源。因此，對資源的分配要給予合理的規劃。

下面介紹幾種常見的死鎖解決方法：

設置加鎖順序

當多個線程需要相同的一些鎖，但是按照不同的順序加鎖，死鎖就很容易發生。如果能確保所有的線程都是按照相同的順序獲得鎖，那麼死鎖就不會發生。看下面這個例子：

如果一個線程（比如線程3）需要一些鎖，那麼它必須按照確定的順序獲取鎖。它只有獲得了從順序上排在前面的鎖之後，才能獲取後面的鎖。例如，線程2和線程3隻有在獲取了鎖A之後才能嘗試獲取鎖C(譯者註：獲取鎖A是獲取鎖C的必要條件)。因為線程1已經擁有了鎖A，所以線程2和3需要一直等到鎖A被釋放。然後在它們嘗試對B或C加鎖之前，必須成功地對A加了鎖。

按照順序加鎖是一種有效的死鎖預防機制。但是，這種方式需要你事先知道所有可能會用到的鎖，但總有些時候是無法預知的。

加鎖時限

另外一個可以避免死鎖的方法是在嘗試獲取鎖的時候加一個超時時間，這也就意味著在嘗試獲取鎖的過程中若超過了這個時限該線程則放棄對該鎖請求。若一個線程沒有在給定的時限內成功獲得所有需要的鎖，則會進行回退並釋放所有已經獲得的鎖，然後等待一段隨機的時間再重試。這段隨機的等待時間讓其它線程有機會嘗試獲取相同的這些鎖，並且讓該應用在沒有獲得鎖的時候可以繼續運行。

死鎖檢測

死鎖檢測是一個更好的死鎖預防機制，它主要是針對那些不可能實現按序加鎖並且鎖超時也不可行的場景。每當一個線程獲得了鎖，會在線程和鎖相關的數據結構中（map、graph等等）將其記下。除此之外，每當有線程請求鎖，也需要記錄在這個數據結構中。

當一個線程請求鎖失敗時，這個線程可以遍歷鎖的關係圖看看是否有死鎖發生。例如，線程A請求鎖7，但是鎖7這個時候被線程B持有，這時線程A就可以檢查一下線程B是否已經請求了線程A當前所持有的鎖。如果線程B確實有這樣的請求，那麼就是發生了死鎖（線程A擁有鎖1，請求鎖7；線程B擁有鎖7，請求鎖1）。

當然，死鎖一般要比兩個線程互相持有對方的鎖這種情況要複雜的多。線程A等待線程B，線程B等待線程C，線程C等待線程D，線程D又在等待線程A。線程A為了檢測死鎖，它需要遞進地檢測所有被B請求的鎖。從線程B所請求的鎖開始，線程A找到了線程C，然後又找到了線程D，發現線程D請求的鎖被線程A自己持有著。這是它就知道發生了死鎖。

下面是一幅關於四個線程（A,B,C和D）之間鎖佔有和請求的關係圖。像這樣的數據結構就可以被用來檢測死鎖。

那麼當檢測出死鎖時，這些線程該做些什麼呢？

一個可行的做法是釋放所有鎖，回退，並且等待一段隨機的時間後重試。這個和簡單的加鎖超時類似，不一樣的是只有死鎖已經發生了才回退，而不會是因為加鎖的請求超時了。雖然有回退和等待，但是如果有大量的線程競爭同一批鎖，它們還是會重複地死鎖（編者註：原因同超時類似，不能從根本上減輕競爭）。

一個更好的方案是給這些線程設置優先順序，讓一個（或幾個）線程回退，剩下的線程就像沒發生死鎖一樣繼續保持著它們需要的鎖。如果賦予這些線程的優先順序是固定不變的，同一批線程總是會擁有更高的優先順序。為避免這個問題，可以在死鎖發生的時候設置隨機的優先順序。

6、高速緩存Cache

Cache的原理

Cache，即高速緩存，是介於CPU和內存之間的高速小容量存儲器。在金字塔式存儲體系中它位於自頂向下的第二層，僅次於CPU寄存器。其容量遠小於內存，但速度卻可以接近CPU的頻率。

當CPU發出內存訪問請求時，會先查看 Cache 內是否有請求數據。

如果存在（命中），則直接返回該數據；

如果不存在（失效），再去訪問內存 —— 先把內存中的相應數據載入緩存，再將其返回處理器。

提供「高速緩存」的目的是讓數據訪問的速度適應CPU的處理速度，通過減少訪問內存的次數來提高數據存取的速度。

Cache 技術所依賴的原理是」程序執行與數據訪問的局部性原理「，這種局部性表現在兩個方面：

時間局部性：如果程序中的某條指令一旦執行，不久以後該指令可能再次執行，如果某數據被訪問過，不久以後該數據可能再次被訪問。

空間局部性：一旦程序訪問了某個存儲單元，在不久之後，其附近的存儲單元也將被訪問，即程序在一段時間內所訪問的地址，可能集中在一定的範圍之內，這是因為指令或數據通常是順序存放的。

時間局部性是通過將近來使用的指令和數據保存到Cache中實現。空間局部性通常是使用較大的高速緩存，並將 預取機制 集成到高速緩存控制邏輯中來實現。

Cache替換策略(頁面置換演算法)

Cache的容量是有限的，當Cache的空間都被佔滿後，如果再次發生緩存失效，就必須選擇一個緩存塊來替換掉。常用的替換策略有以下幾種：

（1）最佳置換演算法（Optimal）：即選擇那些永不使用的，或者是在最長時間內不再被訪問的頁面置換出去。（它是一種理想化的演算法，性能最好，但在實際上難於實現）。

（2）先進先出置換演算法FIFO：該演算法總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。

（3）最近最久未使用置換演算法LRU（Least Recently Used）：該演算法是選擇最近最久未使用的頁面予以淘汰，系統在每個頁面設置一個訪問欄位，用以記錄這個頁面自上次被訪問以來所經歷的時間T，當要淘汰一個頁面時，選擇T最大的頁面。

（4）Clock置換演算法：也叫最近未用演算法NRU（Not RecentlyUsed）。該演算法為每個頁面設置一位訪問位，將內存中的所有頁面都通過鏈接指針鏈成一個循環隊列。當某頁被訪問時，其訪問位置「1」。在選擇一頁淘汰時，就檢查其訪問位，如果是「0」，就選擇該頁換出；若為「1」，則重新置為「0」，暫不換出該頁，在循環隊列中檢查下一個頁面，直到訪問位為「0」的頁面為止。由於該演算法只有一位訪問位，只能用它表示該頁是否已經使用過，而置換時是將未使用過的頁面換出去，所以把該演算法稱為最近未用演算法。

（5）最少使用置換演算法LFU：該演算法選擇最近時期使用最少的頁面作為淘汰頁。

7、最近最久未使用置換演算法LRU的JAVA實現

之前面頭條的暑期實習生時曾經考過這道題，因此這裡整理一下。

思路分析

對一個Cache的操作無非三種：插入(insert)、替換(replace)、查找（lookup）。

為了能夠快速刪除最久沒有訪問的數據項和插入最新的數據項，我們使用 雙向鏈表 連接Cache中的數據項，並且保證鏈表維持數據項從最近訪問到最舊訪問的順序。

插入：當Cache未滿時，新的數據項只需插到雙鏈表頭部即可。時間複雜度為O(1).

替換：當Cache已滿時，將新的數據項插到雙鏈表頭部，並刪除雙鏈表的尾結點即可。時間複雜度為O(1).

查找：每次數據項被查詢到時，都將此數據項移動到鏈表頭部。

經過分析，我們知道使用雙向鏈表可以保證插入和替換的時間複雜度是O(1)，但查詢的時間複雜度是O(n)，因為需要對雙鏈表進行遍歷。為了讓查找效率也達到O(1)，很自然的會想到使用 hash table 。

具體的實現代碼如下：

import java.util.*class Node{ int key; int value; Node pre; Node next; public Node(int kye,int value){ this.key = key; this.value = value; }}public class LRUCache { int capacity; Map<Integer,Node> map = new HashMap<Integer,Node>(); Node head = null; Node end = null; public LRUCache(int capacity){ this.capacity = capacity; } public int get(int key){ if(map.containsKey(key)){ Node n = map.get(key); remove(n); setHead(n); return n.value; } return -1; } public void remove(Node n){ if(n.pre != null){ n.pre.next = n.next; } else{ head = n.next; } if(n.next != null){ n.next.pre = n.pre; } else{ end = n.pre; } } public void setHead(Node n){ n.next = head; n.pre = null; if(head!=null) head.pre = n; head = n; if(end == null){ end = head; } } public void set(int key,int value){ if(map.containsKey(key)){ Node old = map.get(key); old.value = value; remove(old); setHead(old); } else{ Node created = new Node(key,value); if(map.size() >= capacity){ map.remove(end.key); remove(end); setHead(created); } else{ setHead(created); } map.put(key,created); } }}

對於上述代碼的解釋如下：

get：通過get方法得到一個頁面之後，要將這個頁面先從鏈表中進行刪除，然後放入到鏈表的頭部。

remove：執行刪除一個頁面的操作，此時要判斷刪除的key是頭部節點和尾部節點的兩種情況。

setHead：設置頭節點。要注意的情況是當鏈表為空時，要同時設置head和end的值

set：更新緩存，如果key已經存在，則進行替換並放到鏈表的頭部，如果key不存在，則插入到鏈表中，此時又要區分緩存的容量是否已滿兩種情況。

參考文獻

1、計算機網路基礎知識總結：cnblogs.com/maybe2030/p

2、多線程死鎖的產生以及如何避免死鎖：blog.csdn.net/ls5718/ar

3、操作系統面試知識點總結：blog.csdn.net/sunxiangh

4、設計並實現一個LRU Cache (java)：blog.csdn.net/maoyeqiu/


推薦閱讀：

TAG:計算機基礎 | 計算機專業 | 基礎知識 |