為了使不同計算機廠家生產(chǎn)的計算機能夠相互通信,以便在更大的范圍內(nèi)建立計算機網(wǎng)絡(luò),國際標準化組織(ISO)在1978年提出了“開放系統(tǒng)互聯(lián)參考模型”,即著名的OSI/RM模型(Open System Interconnection/Reference Model)。它將計算機網(wǎng)絡(luò)體系結(jié)構(gòu)的通信協(xié)議劃分為七層,自下而上依次為:物理層(Physics Layer)、數(shù)據(jù)鏈路層(Data Link Layer)、網(wǎng)絡(luò)層(Network Layer)、傳輸層(Transport Layer)、會話層(Session Layer)、表示層(Presentation Layer)、應用層(Application Layer)。其中第四層完成數(shù)據(jù)傳送服務(wù),上面三層面向用戶。
除了標準的OSI七層模型以外,常見的網(wǎng)絡(luò)層次劃分還有TCP/IP四層協(xié)議以及TCP/IP五層協(xié)議,它們之間的對應關(guān)系如下圖所示:
TCP/IP協(xié)議是Internet最基本的協(xié)議、Internet國際互聯(lián)網(wǎng)絡(luò)的基礎(chǔ),由網(wǎng)絡(luò)層的IP協(xié)議和傳輸層的TCP協(xié)議組成。通俗而言:TCP負責發(fā)現(xiàn)傳輸?shù)膯栴},一有問題就發(fā)出信號,要求重新傳輸,直到所有數(shù)據(jù)安全正確地傳輸?shù)侥康牡?。而IP是給因特網(wǎng)的每一臺聯(lián)網(wǎng)設(shè)備規(guī)定一個地址。
TCP協(xié)議中有著名的三次握手和四次握手規(guī)則,如下圖所示:
注:seq:''sequance''序列號;ack:''acknowledge''確認號;SYN:''synchronize''請求同步標志;;ACK:''acknowledge''確認標志'';FIN:''Finally''結(jié)束標志。
TCP連接建立過程
首先Client端發(fā)送連接請求報文,Server段接受連接后回復ACK報文,并為這次連接分配資源。Client端接收到ACK報文后也向Server段發(fā)生ACK報文,并分配資源,這樣TCP連接就建立了。
TCP連接斷開過程
假設(shè)Client端發(fā)起中斷連接請求,也就是發(fā)送FIN報文。Server端接到FIN報文后,意思是說''我Client端沒有數(shù)據(jù)要發(fā)給你了'',但是如果你還有數(shù)據(jù)沒有發(fā)送完成,則不必急著關(guān)閉Socket,可以繼續(xù)發(fā)送數(shù)據(jù)。所以你先發(fā)送ACK,''告訴Client端,你的請求我收到了,但是我還沒準備好,請繼續(xù)你等我的消息''。這個時候Client端就進入FIN_WAIT狀態(tài),繼續(xù)等待Server端的FIN報文。當Server端確定數(shù)據(jù)已發(fā)送完成,則向Client端發(fā)送FIN報文,''告訴Client端,好了,我這邊數(shù)據(jù)發(fā)完了,準備好關(guān)閉連接了''。Client端收到FIN報文后,''就知道可以關(guān)閉連接了,但是他還是不相信網(wǎng)絡(luò),怕Server端不知道要關(guān)閉,所以發(fā)送ACK后進入TIME_WAIT狀態(tài),如果Server端沒有收到ACK則可以重傳?!?,Server端收到ACK后,''就知道可以斷開連接了''。Client端等待了2MSL后依然沒有收到回復,則證明Server端已正常關(guān)閉,那好,我Client端也可以關(guān)閉連接了。Ok,TCP連接就這樣關(guān)閉了!
為什么要三次握手?
在只有兩次“握手”的情形下,假設(shè)Client想跟Server建立連接,但是卻因為中途連接請求的數(shù)據(jù)報丟失了,故Client端不得不重新發(fā)送一遍;這個時候Server端僅收到一個連接請求,因此可以正常的建立連接。但是,有時候Client端重新發(fā)送請求不是因為數(shù)據(jù)報丟失了,而是有可能數(shù)據(jù)傳輸過程因為網(wǎng)絡(luò)并發(fā)量很大在某結(jié)點被阻塞了,這種情形下Server端將先后收到2次請求,并持續(xù)等待兩個Client請求向他發(fā)送數(shù)據(jù)...問題就在這里,Cient端實際上只有一次請求,而Server端卻有2個響應,極端的情況可能由于Client端多次重新發(fā)送請求數(shù)據(jù)而導致Server端最后建立了N多個響應在等待,因而造成極大的資源浪費!所以,“三次握手”很有必要!
為什么要四次握手?
試想一下,假如現(xiàn)在你是客戶端你想斷開跟Server的所有連接該怎么做?第一步,你自己先停止向Server端發(fā)送數(shù)據(jù),并等待Server的回復。但事情還沒有完,雖然你自身不往Server發(fā)送數(shù)據(jù)了,但是因為你們之前已經(jīng)建立好平等的連接了,所以此時他也有主動權(quán)向你發(fā)送數(shù)據(jù);故Server端還得終止主動向你發(fā)送數(shù)據(jù),并等待你的確認。其實,說白了就是保證雙方的一個合約的完整執(zhí)行!
進程是具有一定獨立功能的程序關(guān)于某個數(shù)據(jù)集合上的一次運行活動,進程是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位.
線程:當一個進程內(nèi)有多個線程時,線程的程序是其所屬進程的一部分,表示進程中的一個控制點,執(zhí)行一系列的指令。同屬一個進程的其他的線程共享進程所擁有的全部資源(包括地址空間)。它是比進程更小的能獨立運行的基本單位.線程自己基本上不擁有系統(tǒng)資源,只擁有一點在運行中必不可少的資源(如程序計數(shù)器,一組寄存器和棧),因此,它的創(chuàng)建、撤銷、切換所需要的時空開銷比進程要小。線程的引入可進一步提高系統(tǒng)的并發(fā)性。
進程和線程的主要差別在于它們是不同的操作系統(tǒng)資源管理方式。進程有獨立的地址空間,一個進程崩潰后,在保護模式下不會對其它進程產(chǎn)生影響,而線程只是一個進程中的不同執(zhí)行路徑。線程有自己的堆棧和局部變量,但線程之間沒有單獨的地址空間,一個線程死掉就等于整個進程死掉,所以多進程的程序要比多線程的程序健壯,但在進程切換時,耗費資源較大,效率要差一些。但對于一些要求同時進行并且又要共享某些變量的并發(fā)操作,只能用線程,不能用進程。
調(diào)度分派:線程是可調(diào)度分派的工作單元,它包括處理器上下文環(huán)境和棧中自己的數(shù)據(jù)區(qū)域。線程順序執(zhí)行,并且可以中斷,這樣處理器可以轉(zhuǎn)到另一個線程。在有線程的系統(tǒng)中,進程不再是可調(diào)度分派的工作單元。
資源擁有:進程是一個或多個線程和相關(guān)資源的集合。線程基本不擁有資源,它的運行資源取決于其所屬的進程。
地址空間:不同進程的地址空間是相互獨立的,而同一個進程的各線程共享同一地址空間。
一個進程可包含一個或多個線程,反過來則不然。一個進程中的線程在另一個進程中時不可見的。
通信關(guān)系:進程間的通信必須使用操作系統(tǒng)提供的進程間通信機制,而同一個進程中的各線程間可以通過直接讀寫數(shù)據(jù)段來進行通信。當然,同一個進程中的各線程間的通信也需要同步和互斥手段的輔助,以確保數(shù)據(jù)一致性。
(1)先來先服務(wù)(FCFS,F(xiàn)irst-Come-First-Served): 此算法的原則是按照作業(yè)到達后備作業(yè)隊列(或進程進入就緒隊列)的先后次序來選擇作業(yè)(或進程)。
(2)短作業(yè)優(yōu)先(SJF,Shortest Process Next):這種調(diào)度算法主要用于作業(yè)調(diào)度,它從作業(yè)后備隊列中挑選所需運行時間(估計值)最短的作業(yè)進入主存運行。
(3)時間片輪轉(zhuǎn)調(diào)度算法(RR,Round-Robin):當某個進程執(zhí)行的時間片用完時,調(diào)度程序便停止該進程的執(zhí)行,并將它送就緒隊列的末尾,等待分配下一時間片再執(zhí)行。然后把處理機分配給就緒隊列中新的隊首進程,同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進程,在一給定的時間內(nèi),均能獲得一時間片處理機執(zhí)行時間。
(4)高響應比優(yōu)先(HRRN,Highest Response Ratio Next): 按照高響應比((已等待時間+要求運行時間)/ 要求運行時間)優(yōu)先的原則,在每次選擇作業(yè)投入運行時,先計算此時后備作業(yè)隊列中每個作業(yè)的響應比RP然后選擇其值最大的作業(yè)投入運行。
(5)優(yōu)先權(quán)(Priority)調(diào)度算法: 按照進程的優(yōu)先權(quán)大小來調(diào)度,使高優(yōu)先權(quán)進程得到優(yōu)先處理的調(diào)度策略稱為優(yōu)先權(quán)調(diào)度算法。
(6) 多級隊列調(diào)度算法:多隊列調(diào)度是根據(jù)作業(yè)的性質(zhì)和類型的不同,將就緒隊列再分為若干個子隊列,所有的作業(yè)(或進程)按其性質(zhì)排入相應的隊列中,而不同的就緒隊列采用不同的調(diào)度算法。
在兩個或多個并發(fā)進程中,如果每個進程持有某種資源而又都等待別的進程釋放它或它們現(xiàn)在保持著的資源,在未改變這種狀態(tài)之前都不能向前推進,稱這一組進程產(chǎn)生了死鎖。通俗地講,就是兩個或多個進程被無限期地阻塞、相互等待的一種狀態(tài)。
死鎖產(chǎn)生的原因主要是:1、 系統(tǒng)資源不足;2、進程推進順序非法。
產(chǎn)生死鎖有四個必要條件:
(1)互斥:一個資源每次只能被一個進程使用;
(2)不可搶占進程已獲得的資源,在未使用完之前,不能強行剝奪;
(3)占有并等待一個進程因請求資源而阻塞時,對已獲得的資源保持不放;
(4)環(huán)形等待若干進程之間形成一種首尾相接的循環(huán)等待資源關(guān)系。
這四個條件是死鎖的必要條件,只要系統(tǒng)發(fā)生死鎖,這些條件必然成立,而只要上述條件之一不滿足,就不會發(fā)生死鎖。
理解了死鎖的原因,尤其是產(chǎn)生死鎖的四個必要條件,就可以最大可能地避免、預防和解除死鎖。所以,在系統(tǒng)設(shè)計、進程調(diào)度等方面注意如何不讓這四個必要條件成立,如何確定資源的合理分配算法,避免進程永久占據(jù)系統(tǒng)資源。此外,也要防止進程在處于等待狀態(tài)的情況下占用資源。因此,對資源的分配要給予合理的規(guī)劃。
下面介紹幾種常見的死鎖解決方法:
設(shè)置加鎖順序
當多個線程需要相同的一些鎖,但是按照不同的順序加鎖,死鎖就很容易發(fā)生。如果能確保所有的線程都是按照相同的順序獲得鎖,那么死鎖就不會發(fā)生??聪旅孢@個例子:
如果一個線程(比如線程3)需要一些鎖,那么它必須按照確定的順序獲取鎖。它只有獲得了從順序上排在前面的鎖之后,才能獲取后面的鎖。例如,線程2和線程3只有在獲取了鎖A之后才能嘗試獲取鎖C(譯者注:獲取鎖A是獲取鎖C的必要條件)。因為線程1已經(jīng)擁有了鎖A,所以線程2和3需要一直等到鎖A被釋放。然后在它們嘗試對B或C加鎖之前,必須成功地對A加了鎖。
按照順序加鎖是一種有效的死鎖預防機制。但是,這種方式需要你事先知道所有可能會用到的鎖,但總有些時候是無法預知的。
加鎖時限
另外一個可以避免死鎖的方法是在嘗試獲取鎖的時候加一個超時時間,這也就意味著在嘗試獲取鎖的過程中若超過了這個時限該線程則放棄對該鎖請求。若一個線程沒有在給定的時限內(nèi)成功獲得所有需要的鎖,則會進行回退并釋放所有已經(jīng)獲得的鎖,然后等待一段隨機的時間再重試。這段隨機的等待時間讓其它線程有機會嘗試獲取相同的這些鎖,并且讓該應用在沒有獲得鎖的時候可以繼續(xù)運行。
死鎖檢測
死鎖檢測是一個更好的死鎖預防機制,它主要是針對那些不可能實現(xiàn)按序加鎖并且鎖超時也不可行的場景。每當一個線程獲得了鎖,會在線程和鎖相關(guān)的數(shù)據(jù)結(jié)構(gòu)中(map、graph等等)將其記下。除此之外,每當有線程請求鎖,也需要記錄在這個數(shù)據(jù)結(jié)構(gòu)中。
當一個線程請求鎖失敗時,這個線程可以遍歷鎖的關(guān)系圖看看是否有死鎖發(fā)生。例如,線程A請求鎖7,但是鎖7這個時候被線程B持有,這時線程A就可以檢查一下線程B是否已經(jīng)請求了線程A當前所持有的鎖。如果線程B確實有這樣的請求,那么就是發(fā)生了死鎖(線程A擁有鎖1,請求鎖7;線程B擁有鎖7,請求鎖1)。
當然,死鎖一般要比兩個線程互相持有對方的鎖這種情況要復雜的多。線程A等待線程B,線程B等待線程C,線程C等待線程D,線程D又在等待線程A。線程A為了檢測死鎖,它需要遞進地檢測所有被B請求的鎖。從線程B所請求的鎖開始,線程A找到了線程C,然后又找到了線程D,發(fā)現(xiàn)線程D請求的鎖被線程A自己持有著。這是它就知道發(fā)生了死鎖。
下面是一幅關(guān)于四個線程(A,B,C和D)之間鎖占有和請求的關(guān)系圖。像這樣的數(shù)據(jù)結(jié)構(gòu)就可以被用來檢測死鎖。
那么當檢測出死鎖時,這些線程該做些什么呢?
一個可行的做法是釋放所有鎖,回退,并且等待一段隨機的時間后重試。這個和簡單的加鎖超時類似,不一樣的是只有死鎖已經(jīng)發(fā)生了才回退,而不會是因為加鎖的請求超時了。雖然有回退和等待,但是如果有大量的線程競爭同一批鎖,它們還是會重復地死鎖(編者注:原因同超時類似,不能從根本上減輕競爭)。
一個更好的方案是給這些線程設(shè)置優(yōu)先級,讓一個(或幾個)線程回退,剩下的線程就像沒發(fā)生死鎖一樣繼續(xù)保持著它們需要的鎖。如果賦予這些線程的優(yōu)先級是固定不變的,同一批線程總是會擁有更高的優(yōu)先級。為避免這個問題,可以在死鎖發(fā)生的時候設(shè)置隨機的優(yōu)先級。
Cache,即高速緩存,是介于CPU和內(nèi)存之間的高速小容量存儲器。在金字塔式存儲體系中它位于自頂向下的第二層,僅次于CPU寄存器。其容量遠小于內(nèi)存,但速度卻可以接近CPU的頻率。
當CPU發(fā)出內(nèi)存訪問請求時,會先查看 Cache 內(nèi)是否有請求數(shù)據(jù)。
如果存在(命中),則直接返回該數(shù)據(jù);
如果不存在(失效),再去訪問內(nèi)存 —— 先把內(nèi)存中的相應數(shù)據(jù)載入緩存,再將其返回處理器。
提供“高速緩存”的目的是讓數(shù)據(jù)訪問的速度適應CPU的處理速度,通過減少訪問內(nèi)存的次數(shù)來提高數(shù)據(jù)存取的速度。
Cache 技術(shù)所依賴的原理是”程序執(zhí)行與數(shù)據(jù)訪問的局部性原理“,這種局部性表現(xiàn)在兩個方面:
時間局部性:如果程序中的某條指令一旦執(zhí)行,不久以后該指令可能再次執(zhí)行,如果某數(shù)據(jù)被訪問過,不久以后該數(shù)據(jù)可能再次被訪問。
空間局部性:一旦程序訪問了某個存儲單元,在不久之后,其附近的存儲單元也將被訪問,即程序在一段時間內(nèi)所訪問的地址,可能集中在一定的范圍之內(nèi),這是因為指令或數(shù)據(jù)通常是順序存放的。
時間局部性是通過將近來使用的指令和數(shù)據(jù)保存到Cache中實現(xiàn)??臻g局部性通常是使用較大的高速緩存,并將 預取機制 集成到高速緩存控制邏輯中來實現(xiàn)。
Cache的容量是有限的,當Cache的空間都被占滿后,如果再次發(fā)生緩存失效,就必須選擇一個緩存塊來替換掉。常用的替換策略有以下幾種:
(1)最佳置換算法(Optimal):即選擇那些永不使用的,或者是在最長時間內(nèi)不再被訪問的頁面置換出去。(它是一種理想化的算法,性能最好,但在實際上難于實現(xiàn))。
(2)先進先出置換算法FIFO:該算法總是淘汰最先進入內(nèi)存的頁面,即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。
(3)最近最久未使用置換算法LRU(Least Recently Used):該算法是選擇最近最久未使用的頁面予以淘汰,系統(tǒng)在每個頁面設(shè)置一個訪問字段,用以記錄這個頁面自上次被訪問以來所經(jīng)歷的時間T,當要淘汰一個頁面時,選擇T最大的頁面。
(4)Clock置換算法:也叫最近未用算法NRU(Not RecentlyUsed)。該算法為每個頁面設(shè)置一位訪問位,將內(nèi)存中的所有頁面都通過鏈接指針鏈成一個循環(huán)隊列。當某頁被訪問時,其訪問位置“1”。在選擇一頁淘汰時,就檢查其訪問位,如果是“0”,就選擇該頁換出;若為“1”,則重新置為“0”,暫不換出該頁,在循環(huán)隊列中檢查下一個頁面,直到訪問位為“0”的頁面為止。由于該算法只有一位訪問位,只能用它表示該頁是否已經(jīng)使用過,而置換時是將未使用過的頁面換出去,所以把該算法稱為最近未用算法。
(5)最少使用置換算法LFU:該算法選擇最近時期使用最少的頁面作為淘汰頁。
之前面頭條的暑期實習生時曾經(jīng)考過這道題,因此這里整理一下。
對一個Cache的操作無非三種:插入(insert)、替換(replace)、查找(lookup)。
為了能夠快速刪除最久沒有訪問的數(shù)據(jù)項和插入最新的數(shù)據(jù)項,我們使用 雙向鏈表 連接Cache中的數(shù)據(jù)項,并且保證鏈表維持數(shù)據(jù)項從最近訪問到最舊訪問的順序。
插入:當Cache未滿時,新的數(shù)據(jù)項只需插到雙鏈表頭部即可。時間復雜度為O(1).
替換:當Cache已滿時,將新的數(shù)據(jù)項插到雙鏈表頭部,并刪除雙鏈表的尾結(jié)點即可。時間復雜度為O(1).
查找:每次數(shù)據(jù)項被查詢到時,都將此數(shù)據(jù)項移動到鏈表頭部。
經(jīng)過分析,我們知道使用雙向鏈表可以保證插入和替換的時間復雜度是O(1),但查詢的時間復雜度是O(n),因為需要對雙鏈表進行遍歷。為了讓查找效率也達到O(1),很自然的會想到使用 hash table 。
具體的實現(xiàn)代碼如下:
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
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:執(zhí)行刪除一個頁面的操作,此時要判斷刪除的key是頭部節(jié)點和尾部節(jié)點的兩種情況。
setHead:設(shè)置頭節(jié)點。要注意的情況是當鏈表為空時,要同時設(shè)置head和end的值
set:更新緩存,如果key已經(jīng)存在,則進行替換并放到鏈表的頭部,如果key不存在,則插入到鏈表中,此時又要區(qū)分緩存的容量是否已滿兩種情況。