當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

poll和死锁_计算机基础知识

發(fā)布時間：2023/12/15 编程问答 22 豆豆

生活随笔收集整理的這篇文章主要介紹了 poll和死锁_计算机基础知识小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

轉(zhuǎn)自：

http://blog.csdn.net/qq_15437629/article/details/52388685

在這里只做備份

計算機網(wǎng)絡(luò)

TCP/IP

模型

TCP/IP協(xié)議集的分層實施:

為什么要給網(wǎng)絡(luò)劃分層次？

(1)各層之間相對獨立，每層都可以用最合適的技術(shù)實現(xiàn)；

(2)各層只需知道通過層間接口提供的服務(wù)，各層因技術(shù)進步而做的改動不會影響到其它層，從而保持體系結(jié)構(gòu)的穩(wěn)定性；

(3)將整個系統(tǒng)劃分為若干子系統(tǒng)，易于實現(xiàn)和維護；

(4)促進標(biāo)準(zhǔn)化工作

TCP、UDP

比較

TCP 是面向連接的，是可靠的，需要進行確認(rèn)和排序，支持流量和錯誤控制，

而 UDP是無連接的，不進行確認(rèn)和排序，不提供錯誤和流量控制功能。

UDP沒有TCP的握手、確認(rèn)、窗口、重傳、擁塞控制等機制，優(yōu)勢是它在傳遞數(shù)據(jù)時非常快，傳輸開銷小

TCP報頭中的字段包括源端口、目標(biāo)端口、序列號、確認(rèn)號、報頭長度、保留字段(保留供以后使用)、編碼位窗口大小、校驗和、緊急指針、選項和數(shù)據(jù)字段。

源端口：發(fā)送主機的應(yīng)用程序的端口號(端口將在本節(jié)后面解釋)。

目標(biāo)端口：目標(biāo)主機的應(yīng)用程序的端口號。

序列號：一個編號， TCP 用來將數(shù)據(jù)按正確的順序重新排列(稱為排序) 重傳丟失或受損的數(shù)據(jù)。

確認(rèn)號： TCP 期待接下來收到的數(shù)據(jù)段。

報頭長度：TCP 報頭的長度，以 32 位字為單位。它指出了數(shù)據(jù)的開始位置，TCP 報頭的長度為32 位的整數(shù)倍，即使包含選項時亦如此。

保留：總是設(shè)置為零。

編碼位/標(biāo)志：用于建立和終止會話的控制功能。

窗口大小：發(fā)送方愿意接受的窗口大小，單位為字節(jié)

校驗和 CRC (Cyclic Redundancy Check，循環(huán)冗余校驗)：由于 TCP 不信任低層，因此檢查所有數(shù)據(jù)。 CRC 檢查報頭和數(shù)據(jù)字段。

緊急：僅當(dāng)設(shè)置了編碼位中的緊急指針字段時，該字段才有效。如果設(shè)置了緊急指針，該字段表示非緊急數(shù)據(jù)的開頭位置相對于當(dāng)前序列號的偏移量，單位為字節(jié)。

選項：長度為 32 位的整數(shù)倍。也就是說，沒有選項時，長度為。然而，如果包含選項時導(dǎo)致該字段的長度不是 32位的整數(shù)倍，必須填充零，以確保該字段的長度為 32 位的整數(shù)倍。

數(shù)據(jù)：傳遞給傳輸層的 TCP 協(xié)議的信息，包括上層報頭。

UDP 報頭只包含字段源端口、目標(biāo)端口、長度、校驗和和數(shù)據(jù)。相對于TCP報頭，其字段更少了，但代價是不提供 TCP 的高級功能。

源端口號 : 發(fā)送主機的應(yīng)用程序的端口號。

目標(biāo)端口號 : 目標(biāo)主機上被請求的應(yīng)用程序的端口號

長度 : UDP 報頭和 UDP 數(shù)據(jù)的總長度

校驗和 : UDP 報頭和 UDP 數(shù)據(jù)的校驗和。

數(shù)據(jù) : 上層數(shù)據(jù)。

TCP、UDP 必須使用端口號與上層通信，其值不小于1024。在數(shù)據(jù)段中， TCP，UDP 將它們用作源端口和目標(biāo)端口。

小于 1024 的端口號為知名端口號。

下表列出了 TCP/IP 協(xié)議簇常用的應(yīng)用程序、它們的知名端口號以及它們使用的傳輸層協(xié)議: (DHCP->UDP)

可靠性

TCP通過下列方式來提供可靠性：

(1)需要進行確認(rèn)和排序：對于收到的請求，給出確認(rèn)響應(yīng)；對失序數(shù)據(jù)進行重新排序，然后才交給應(yīng)用層。對于重復(fù)數(shù)據(jù)，進行丟棄。

(2) TCP將保持它首部和數(shù)據(jù)的檢驗和。如果收到段的檢驗和有差錯，TCP將丟棄報文段，不給出響應(yīng)，超時會重發(fā)數(shù)據(jù)。

(3)超時重發(fā)：當(dāng)TCP發(fā)出一個段后，它啟動一個定時器，等待目的端確認(rèn)收到這個報文段。如果不能及時收到一個確認(rèn)，將重發(fā)這個報文段。

(4)TCP將數(shù)據(jù)截斷為合理的長度進行發(fā)送。而UDP程序產(chǎn)生的數(shù)據(jù)報長度保持不變。

(5)TCP還能提供流量控制。TCP連接的每一方都有固定大小的緩沖空間，防止發(fā)送速率過快導(dǎo)致接收端的緩沖區(qū)溢出。TCP使用的流量控制協(xié)議是可變大小的滑動窗口協(xié)議。

滑動窗口技術(shù)：

滑動窗口(Sliding window)是一種流量控制技術(shù)。如果發(fā)送端不考慮網(wǎng)絡(luò)情況直接發(fā)送數(shù)據(jù)包，可能會超過接收端的接收能力而產(chǎn)生丟包的情況。

滑動窗口的大小意味著接收方還有多大的緩沖區(qū)可以用于接收數(shù)據(jù)。發(fā)送方可以通過滑動窗口的大小來確定應(yīng)該發(fā)送多少字節(jié)的數(shù)據(jù)，防止發(fā)送速率過快導(dǎo)致接收端的緩沖區(qū)溢出。

滑動窗口處理過程：

(1)TCP連接階段，雙方協(xié)商窗口尺寸，同時接收方預(yù)留數(shù)據(jù)緩沖區(qū)用于接收數(shù)據(jù)。

(2)發(fā)送方根據(jù)協(xié)商結(jié)果發(fā)送符合窗口尺寸的數(shù)據(jù)字節(jié)流，并等待對方確認(rèn)信息。

(3)然后根據(jù)確認(rèn)信息，對窗口尺寸進行調(diào)整，增加或減少發(fā)送未得到確認(rèn)的字節(jié)流中的字節(jié)數(shù)。(例如：出現(xiàn)擁塞時，將發(fā)送窗口減小為原來的一半，同時將超時重傳的時間間隔擴大一倍)

TCP的擁塞控制由4個核心算法組成：

(1)“慢啟動”(Slow Start)：發(fā)送方維持一個叫做擁塞窗口cwnd(congestion window)的狀態(tài)變量。發(fā)送方讓自己的發(fā)送窗口等于擁塞窗口。慢啟動算法的思路就是，不要一開始就發(fā)送大量的數(shù)據(jù)，先探測一下網(wǎng)絡(luò)的擁塞程度，由小到大逐漸增加擁塞窗口的大小。一次傳輸輪次之后擁塞窗口就加倍。這就是乘法增長。

(2)“擁塞避免”(Congestion voidance)：擁塞避免算法讓擁塞窗口緩慢增長，即每經(jīng)過一個往返時間RTT就把發(fā)送方的擁塞窗口cwnd加1，而不是加倍。這樣擁塞窗口按線性規(guī)律緩慢增長。

(3)“快速重傳 ”(Fast Retransmit)：快重傳要求接收方在收到一個失序的報文段后就立即發(fā)出重復(fù)確認(rèn)(為的是使發(fā)送方及早知道有報文段沒有到達對方)而不要等到自己發(fā)送數(shù)據(jù)時捎帶確認(rèn)。快重傳算法規(guī)定，發(fā)送方只要一連收到三個重復(fù)確認(rèn)就應(yīng)當(dāng)立即重傳對方尚未收到的報文段，而不必繼續(xù)等待設(shè)置的重傳計時器時間到期。

(4)“快速恢復(fù)”(Fast Recovery)：①當(dāng)發(fā)送方連續(xù)收到三個重復(fù)確認(rèn)時，就執(zhí)行“乘法減小”算法，把慢開始門限ssthresh門限減半。但是接下去并不執(zhí)行慢開始算法。

②因為考慮到如果網(wǎng)絡(luò)出現(xiàn)擁塞的話就不會收到好幾個重復(fù)的確認(rèn)，所以發(fā)送方現(xiàn)在認(rèn)為網(wǎng)絡(luò)可能沒有出現(xiàn)擁塞。所以此時不執(zhí)行慢開始算法，而是將cwnd設(shè)置為ssthresh的大小，然后執(zhí)行擁塞避免算法。如下圖：

三次握手

首先服務(wù)器創(chuàng)建socket，綁定自身端口號進行監(jiān)聽。

(1)第一次握手：客戶端向服務(wù)器發(fā)送SYN包，假設(shè)序列號為x，進入SYN_SEND狀態(tài)。

(2)第二次握手：服務(wù)器收到SYN包，進行確認(rèn)，發(fā)送ACK報文，序列號為x+1，同時自己也發(fā)送一個SYN包(假設(shè)序列號為y)，此時服務(wù)器進入SYN_RECV狀態(tài)。

(3)第三次握手：客戶端收到服務(wù)器B的SYN＋ACK包，向服務(wù)器B發(fā)送確認(rèn)包ACK(確認(rèn)號為y+1)，客戶端和服務(wù)器進入ESTABLISHED狀態(tài)，完成三次握手。

四次揮手

(1)客戶端A發(fā)送一個FIN，用來關(guān)閉客戶A到服務(wù)器B的數(shù)據(jù)傳送。

(2)服務(wù)器B收到這個FIN，它發(fā)回一個ACK，確認(rèn)序號為收到的序號加1。

(3)然后服務(wù)器B也會發(fā)送一個FIN給客戶端A。

(4)客戶端A發(fā)回ACK報文確認(rèn)，確認(rèn)序號為收到序號加1。

TIME_WAIT狀態(tài)

主動關(guān)閉連接的一方會進入TIME_WAIT狀態(tài)。這樣設(shè)計主要有兩個原因：

(1)可靠地實現(xiàn)TCP連接的終止。四次揮手過程中，如果客戶端最終發(fā)送的ACK丟失，服務(wù)器會重發(fā)FIN，通過保持TIME_WAIT狀態(tài)可以允許它重發(fā)ACK，保證TCP連接正常地終止。

(2)讓舊連接的重復(fù)分組在網(wǎng)絡(luò)中消失。因為如果復(fù)用舊連接的端口馬上開啟一個新的連接，原來舊連接中的數(shù)據(jù)包可能會被這個新連接收到。處于TIME_WAIT狀態(tài)的連接就可以避免這種情況。它會持續(xù)2個最大分解生命期(MSL)，也就是一個IP數(shù)據(jù)包能在網(wǎng)絡(luò)中生存的最長時間，保證新連接建立的時候，舊連接的數(shù)據(jù)包已經(jīng)在網(wǎng)絡(luò)中消失了。

TCP/IP、Http、Socket的區(qū)別

TCP協(xié)議對應(yīng)于傳輸層，主要解決數(shù)據(jù)如何在網(wǎng)絡(luò)中傳輸，

而HTTP協(xié)議對應(yīng)于應(yīng)用層，主要解決如何包裝數(shù)據(jù)。

socket則是對TCP/IP協(xié)議的封裝和應(yīng)用。是應(yīng)用層與TCP/IP協(xié)議族通信的中間軟件抽象層，它是一組接口。

ARP協(xié)議

ARP (Address Resolution Protocol)：地址解析協(xié)議: 負(fù)責(zé)將某個IP地址解析成對應(yīng)的MAC地址。

原理：

主機會將包含目標(biāo)IP地址的ARP請求廣播到網(wǎng)絡(luò)上的所有主機，目標(biāo)主機收到ARP報文進行響應(yīng)，這樣該主機就得到目標(biāo)主機的物理地址；收到返回消息后將該IP地址和物理地址存入本機ARP緩存中并保留一定時間，下次請求時直接查詢ARP緩存以節(jié)約資源。

問題：

Arp是建立在網(wǎng)絡(luò)中各個主機互相信任的基礎(chǔ)上的，主機收到應(yīng)答報文時不會檢測該報文的真實性就會將其記入本機ARP緩存；因此攻擊者就可以通過偽造IP地址和MAC地址實現(xiàn)ARP欺騙，使主機發(fā)送的信息無法到達預(yù)期的主機或到達錯誤的主機，造成網(wǎng)絡(luò)阻塞或中斷或中斷。

解決：

殺毒軟件，安裝ARP防火墻，

將IP和MAC地址進行綁定

對于不經(jīng)常變動的網(wǎng)絡(luò)環(huán)境，可以通過靜態(tài)ARP的方式，讓ARP映射不被新的ARP數(shù)據(jù)刷新

icmp協(xié)議

ICMP是(Internet Control Message Protocol)因特網(wǎng)控制報文協(xié)議。可向主機提供有關(guān)網(wǎng)絡(luò)故障的消息，比如網(wǎng)絡(luò)通不通、主機是否可達、路由是否可用等。比如我們經(jīng)常使用的Ping命令就是基于icmp協(xié)議的。

ping的原理

Ping主要有兩種情況，一種是同一網(wǎng)段，一種是跨網(wǎng)段的。

如果在同一網(wǎng)段，主機A ping主機B，主機A會先檢查自己緩存中是否有主機B的MAC地址，如果沒有B的MAC地址，就會向外發(fā)送一個ARP廣播包。交換機有學(xué)習(xí)MAC地址的能力，它會檢索自己有沒有保存主機B的MAC地址，如果有，就直接返回給A主機，如果沒有，就會向所有端口發(fā)送ARP廣播，直到主機B收到了報文進行響應(yīng)。這時候主機A 學(xué)到了主機B的MAC地址，就把這個MAC封裝到ICMP報文中向主機B發(fā)送；當(dāng)主機B收到了這個報文后，就按同樣的格式，返回一個值給主機A，完成了同一網(wǎng)段內(nèi)的Ping過程。

如果主機A發(fā)現(xiàn)主機B不在同一個網(wǎng)段，同樣通過發(fā)送ARP廣播，先學(xué)到網(wǎng)關(guān)的MAC地址，發(fā)送ICMP報文，路由器查找路由表，找到去主機B的端口，將原來主機A的MAC地址改為自己的MAC地址向主機B轉(zhuǎn)發(fā)。這樣一來主機B也學(xué)到路由器端口MAC，通過路由器就可以完成了跨網(wǎng)段的Ping過程。

Post和Get

區(qū)別：

1、Get是從服務(wù)器端獲取數(shù)據(jù)，Post則是向服務(wù)器端發(fā)送數(shù)據(jù)。

2、在客戶端，Get方式通過URL提交數(shù)據(jù)，在URL地址欄可以看到請求消息，該消息被編碼過；Post數(shù)據(jù)則是放在Html header內(nèi)提交。

3、Get方式提交的參數(shù)及參數(shù)值會在地址欄顯示，不安全，而Post不會，比較安全。

4、對于Get方式，服務(wù)器端用Request.QueryString獲取變量的值；對用Post方式，服務(wù)器端用Request.Form獲取提交的數(shù)據(jù)值。

5、Get方式提交的數(shù)據(jù)最多1024字節(jié)，而Post則沒有限制。

Cookie和Session

比較CookieSession

儲存位置

客戶端

服務(wù)器端

目的

跟蹤會話，也可以保存用戶偏好設(shè)置或者保存用戶名密碼等

跟蹤會話

安全性

不安全

安全

session技術(shù)是要使用到cookie的，之所以出現(xiàn)session技術(shù)，主要是為了安全。

HTTP和HTTPS

基礎(chǔ)知識：Http的請求格式如下。

<request line>主要包含三個信息： 1、請求的類型(GET或POST)， 2、要訪問的資源(如\res\img\a.jif)， 3、Http版本(http/1.1) <header> 用來說明服務(wù)器要使用的附加信息 <blank line> 這是Http的規(guī)定，必須空一行 [<request-body>] 請求的內(nèi)容數(shù)據(jù)

HTTPS和HTTP的區(qū)別

一、https協(xié)議需要到ca申請證書，一般免費證書很少，需要交費。

二、http和https使用的是完全不同的連接方式，用的端口也不一樣，前者是80，后者是443。

三、http是超文本傳輸協(xié)議，信息是明文傳輸，是無狀態(tài)的；https 則是具有安全性的ssl加密傳輸協(xié)議。是由SSL+HTTP協(xié)議構(gòu)建的可進行加密傳輸、身份認(rèn)證的網(wǎng)絡(luò)協(xié)議，比http協(xié)議安全。

HTTP1.0和HTTP1.1

HTTP 1.0規(guī)定瀏覽器與服務(wù)器只保持短暫的連接，瀏覽器的每次請求都需要與服務(wù)器建立一個TCP連接，服務(wù)器完成請求處理后立即斷開TCP連接，服務(wù)器不跟蹤每個客戶也不記錄過去的請求。

HTTP1.1概括如下：

1. 長鏈接

2. 文件斷點續(xù)傳

3. 請求頭Host字段,一個服務(wù)器多個網(wǎng)站

4. 提供了身份認(rèn)證,狀態(tài)管理,Cache緩存等機制

HTTP 1.1支持持久連接，在一個TCP連接上可以傳送多個HTTP請求和響應(yīng)，減少了建立和關(guān)閉連接的消耗和延遲。

HTTP 1.1還允許客戶端不用等待上一次請求結(jié)果返回，就可以發(fā)出下一次請求，但服務(wù)器端必須按照接收到客戶端請求的先后順序依次回送響應(yīng)結(jié)果，以保證客戶端能夠區(qū)分出每次請求的響應(yīng)內(nèi)容，這樣也顯著地減少了整個下載過程所需要的時間。

HTTP 1.0不支持Host請求頭字段，HTTP 1.1中增加Host請求頭字段后，WEB瀏覽器可以使用主機頭名來明確表示要訪問服務(wù)器上的哪個WEB站點，這才實現(xiàn)了在一臺WEB服務(wù)器上可以在同一個IP地址和端口號上使用不同的主機名來創(chuàng)建多個虛擬WEB站點。

從輸入url到顯示網(wǎng)頁

后臺發(fā)生了什么？

輸入url地址

瀏覽器通過域名系統(tǒng)(DNS)查找域名的 IP 地址，包括：瀏覽器緩存->系統(tǒng)緩存->路由器緩存->ISP DNS -> 遞歸搜索你的ISP的DNS服務(wù)器從跟域名服務(wù)器開始進行遞歸搜索，

瀏覽器向 web 服務(wù)器發(fā)送一個 HTTP 請求

服務(wù)器的重定向響應(yīng)

瀏覽器跟蹤重定向地址

服務(wù)器處理請求

服務(wù)器返回一個 HTTP 響應(yīng)

瀏覽器顯示 HTML

瀏覽器發(fā)送請求獲取嵌入在 HTML 中的資源(如圖片、音頻、視頻、CSS、JS等等)

瀏覽器發(fā)送異步請求

操作系統(tǒng)

進程與線程的區(qū)別

(調(diào)度、并發(fā)性、擁有資源、開銷)

進程：是程序的一次執(zhí)行，負(fù)責(zé)一個程序運行時的內(nèi)存分配空間，是資源分配的最小單位；

線程：是進程的一個執(zhí)行單元，是cpu調(diào)度的最小單位。一個進程可以有多個線程。

不僅進程之間可以并發(fā)執(zhí)行，同一個進程的多個線程之間也可并發(fā)執(zhí)行。線程的劃分尺度小于進程，使得多線程程序的并發(fā)性高。

每個進程都有獨立的內(nèi)存地址空間；而同一進程中的所有線程共享同一塊內(nèi)存和系統(tǒng)資源，有利于提高了程序的運行效率。

概括地說：

進程速度慢，內(nèi)存占用、開銷大，但可靠性高，編譯調(diào)試簡單；

線程速度快，內(nèi)存占用、開銷小，但可靠性較差，編譯調(diào)試復(fù)雜。

故需要頻繁創(chuàng)建銷毀’或需要大量計算的優(yōu)先用線程。

注：多線程和多進程的區(qū)別

必須從cpu調(diào)度，上下文切換，數(shù)據(jù)共享，多核cup利用率，資源占用，等等各方面回答，然后有一個問題必須會被問到：哪些東西是一個線程私有的？答案中必須包含寄存器。

進程間通信方式：

進程間通信主要包括管道, 系統(tǒng) IPC(包括消息隊列,信號量,共享內(nèi)存), 信號，SOCKET.

(1) 管道包括三種:

①普通管道 pipe, 通常有限制,一是半雙工,只能單向傳輸;二是只能在父子進程間使用.

②流管道 s_pipe: 去除了第一種限制,可以雙向傳輸.

③命名管道:name_pipe, 去除了第二種限制,可以在許多并不相關(guān)的進程之間進行通訊.

(2) 消息隊列( message queue ) ：消息隊列是消息的鏈表，存放在內(nèi)核中并由消息隊列標(biāo)識符標(biāo)識。消息隊列克服了信號傳遞信息少、管道只能承載無格式字節(jié)流以及緩沖區(qū)大小受限等缺點。

(3) 信號量( semophore ) ：信號量是一個計數(shù)器，可以用來控制多個進程對共享資源的訪問。它常作為一種鎖機制，防止某進程正在訪問共享資源時，其他進程也訪問該資源。因此，主要作為進程間以及同一進程內(nèi)不同線程

之間的同步手段。

(4) 共享內(nèi)存( shared memory ) ：共享內(nèi)存就是映射一段能被其他進程所訪問的內(nèi)存，這段共享內(nèi)存由一個進程創(chuàng)建，但多個進程都可以訪問。共享內(nèi)存是最快的 IPC 方式，它是針對其他進程間通信方式運行效率低而專門設(shè)計

的。它往往與其他通信機制，如信號量，配合使用，來實現(xiàn)進程間的同步和通信。

(5) 信號 ( signal ) ：信號是一種比較復(fù)雜的通信方式，用于通知接收進程某個事件已經(jīng)發(fā)生。

(6) 套接字( socket )：套解字也是一種進程間通信機制，與其他通信機制不同的是它可用于不同機器間的進程通信。

線程間的通信方式:

● 使用全局變量：由于多個線程可能更改全局變量，因此全局變量最好聲明為violate

● 使用消息實現(xiàn)通信：在Windows程序設(shè)計中，每一個線程都可以擁有自己的消息隊列(UI線程默認(rèn)自帶消息隊列和消息循環(huán)，工作線程需要手動實現(xiàn)消息循環(huán))，因此可以采用消息進行線程間通信sendMessage,postMessage。

● 使用事件CEvent類實現(xiàn)線程間通信：Event對象有兩種狀態(tài)：有信號和無信號，線程可以監(jiān)視處于有信號狀態(tài)的事件，以便在適當(dāng)?shù)臅r候執(zhí)行對事件的操作。

注：Linux進程通信與線程通信的區(qū)別：

? linux中的進程，是由fork()系統(tǒng)調(diào)用創(chuàng)建的；進程間都有獨立的地址空間，它們之間不能之間通信，必須通過進程間通信機制(IPC)來完成。常見得有PIPE、命名管道、消息隊列、信號量、共享內(nèi)存、信號、socket等。

? linux中的線程，是由clone()系統(tǒng)調(diào)用創(chuàng)建的，同一進程中的所有線程共享同一塊內(nèi)存和系統(tǒng)資源的，故線程間可以直接訪問，但要注意并發(fā)情況，實現(xiàn)線程同步

同一進程中的所有線程共享同一塊內(nèi)存和系統(tǒng)資源的，故線程間可以直接訪問，線程間通信的主要目的用于線程同步。

線程間的同步方式:

線程間的同步方法大體可分為兩類：用戶模式和內(nèi)核模式。

內(nèi)核模式就是指利用系統(tǒng)內(nèi)核對象的單一性來進行同步，使用時需要切換內(nèi)核態(tài)與用戶態(tài)；

用戶模式就是不需要切換到內(nèi)核態(tài)，只在用戶態(tài)完成操作。

用戶模式下的方法有：原子操作(例如一個單一的全局變量)，臨界區(qū)。

內(nèi)核模式下的方法有：事件，信號量，互斥量。

(1)、臨界區(qū)( CCriticalSection)

當(dāng)多個線程訪問一個獨占性共享資源時，可以使用臨界區(qū)對象。擁有臨界區(qū)的線程可以訪問被保護起來的資源或代碼

段，其他線程若想訪問，則被掛起，直到擁有臨界區(qū)的線程放棄臨界區(qū)為止。

具體應(yīng)用方式：

1)、定義臨界區(qū)對象 CcriticalSection g_CriticalSection;

2)、在訪問共享資源(代碼或變量)之前，先獲得臨界區(qū)對象， g_CriticalSection.Lock()；

3)、訪問共享資源后，則放棄臨界區(qū)對象， g_CriticalSection.Unlock()；

(2)、事件( CEvent)

事件機制，則允許一個線程在處理完一個任務(wù)后，主動喚醒另外一個線程執(zhí)行任務(wù)。

比如在某些網(wǎng)絡(luò)應(yīng)用程序中，一個線程如 A 負(fù)責(zé)偵聽通信端口，另外一個線程 B 負(fù)責(zé)更新用戶數(shù)據(jù)，利用事件機制，則線程 A 可以通知線程 B 何時更新用戶數(shù)據(jù)。每個 Cevent 對象可以有兩種狀態(tài)：有信號狀態(tài)和無信號狀態(tài)。 Cevent 類對象有兩種類型：人工事件和自動事件。

●自動事件對象，在被至少一個線程釋放后自動返回到無信號狀態(tài)；

●人工事件對象，獲得信號后，釋放可利用線程，但直到調(diào)用成員函數(shù) ReSet()才將其設(shè)置為無信號狀態(tài)。在創(chuàng)建 Cevent

對象時，默認(rèn)創(chuàng)建的是自動事件。

(3)、互斥量( CMutex)

互斥對象和臨界區(qū)對象非常相似，只是其允許在進程間使用，而臨界區(qū)只限制與同一進程的各個線程之間使用，但是更節(jié)省資源，更有效率。

(4)、信號量( CSemphore)

使用一個計數(shù)器來限制可以使用某共享資源的線程數(shù)目。

CSemaphore 類對象保存了對當(dāng)前訪問某一個指定資源的線程的計數(shù)值，該計數(shù)值是當(dāng)前還可以使用該資源的線程數(shù)目。如果這個計數(shù)達到了零，則所有對這個 CSemaphore 類對象所控制的資源的訪問嘗試都被放入到一個隊列中等待，直到超時或計數(shù)值不為零為止。

用戶線程和內(nèi)核線程

●用戶線程(ULT)指不需要內(nèi)核支持而在用戶程序中實現(xiàn)的線程，不依賴于操作系統(tǒng)核心，應(yīng)用進程利用線程庫提供創(chuàng)建、同步、調(diào)度和管理線程的函數(shù)來控制用戶線程。不需要用戶態(tài)/核心態(tài)切換，速度快，操作系統(tǒng)內(nèi)核不知道多線程的存在，因此一個線程阻塞將使得整個進程(包括它的所有線程)阻塞。由于這里的處理器時間片分配是以進程為基本單位，所以每個線程執(zhí)行的時間相對減少。

●內(nèi)核線程(KST，也叫守護線程)：由操作系統(tǒng)內(nèi)核創(chuàng)建和撤銷。內(nèi)核維護進程及線程的上下文信息以及線程切換。一個內(nèi)核線程由于I/O操作而阻塞，不會影響其它線程的運行。Windows NT和2000/XP支持內(nèi)核線程。

內(nèi)核線程能很好的利用多核cpu，更有利于并發(fā)使用多處理器的資源，一個線程阻塞其他線程仍然可以正常運行；當(dāng)線程進行切換的時候，需要由用戶態(tài)轉(zhuǎn)化為內(nèi)核態(tài)，上下文切換開銷大。

用戶線程上下文切換開銷小，但是如果一個線程阻塞整個進程就阻塞了，不能很好的利用多核cpu。

注：通過處理器實現(xiàn)進程交錯執(zhí)行的機制稱為上下文切換。

如何創(chuàng)建守護進程

fork()創(chuàng)建子進程，父進程退出;

setsid()在子進程中創(chuàng)建新會話

Chdir(“/”)改變當(dāng)前目錄為根目錄;

umask()重設(shè)文件權(quán)限掩碼;

關(guān)閉文件描述符;

內(nèi)核態(tài)和用戶態(tài)的區(qū)別

?當(dāng)一個進程執(zhí)行系統(tǒng)調(diào)用而陷入內(nèi)核代碼中執(zhí)行時，我們就稱進程處于內(nèi)核態(tài)。此時處理器處于特權(quán)級最高的0級。當(dāng)進程處于內(nèi)核態(tài)時，執(zhí)行的內(nèi)核代碼會使用當(dāng)前進程的內(nèi)核棧。每個進程都有自己的內(nèi)核棧。

?當(dāng)進程在執(zhí)行用戶自己的代碼時，則稱其處于用戶態(tài)。即此時處理器在特權(quán)級最低的3級。當(dāng)正在執(zhí)行用戶程序而突然被中斷程序中斷時，此時用戶程序也可以象征性地稱為處于進程的內(nèi)核態(tài)。因為中斷處理程序?qū)⑹褂卯?dāng)前進程的內(nèi)核棧。

為什么需要

內(nèi)核態(tài)？

當(dāng)進程處于內(nèi)核態(tài)時，特權(quán)級最高，才能使用某些重要指令。在CPU的所有指令中，有一些指令是非常危險的，如果錯用，將導(dǎo)致整個系統(tǒng)崩潰。比如：清內(nèi)存、設(shè)置時鐘等。普通的應(yīng)用程序只能使用那些不會造成災(zāi)難的指令。

什么時候進入內(nèi)核態(tài)？

當(dāng)一個進程執(zhí)行系統(tǒng)調(diào)用而陷入內(nèi)核代碼中執(zhí)行時，我們就稱進程處于內(nèi)核態(tài)；當(dāng)正在執(zhí)行用戶程序而突然被中斷程序中斷時，此時用戶程序也可以象征性地稱為處于進程的內(nèi)核態(tài)。因為中斷處理程序?qū)⑹褂卯?dāng)前進程的內(nèi)核棧。

并行與并發(fā)

? 并行是指多個CPU可以同時單獨處理多個進程，是真正的同時進行。

? 并發(fā)是指多個進程的指令交錯執(zhí)行，宏觀上看起來，多個任務(wù)就像是同時在進行。

系統(tǒng)一次性預(yù)存很多批處理任務(wù)進入內(nèi)存，然后通過一定的調(diào)度算法來讓這些批處理任務(wù)劃分CPU的時間，這樣看起來，多個任務(wù)就像是同時在進行。這個模式，就叫做并發(fā)。

常見的調(diào)度算法

先來先服務(wù)(FCFS, First Come First Serve)：就是按照各個作業(yè)進入系統(tǒng)的自然次序來調(diào)度作業(yè)。這種調(diào)度算法的優(yōu)點是實現(xiàn)簡單，公平。其缺點是不利于短作業(yè)，因為短作業(yè)等待處理的時間可能比實際運行時間長得多；

短作業(yè)優(yōu)先(SJF, Shortest Job First)：: 就是優(yōu)先調(diào)度并處理短作業(yè)，所謂短是指作業(yè)的運行時間短。而在作業(yè)未投入運行時，并不能知道它實際的運行時間的長短，因此需要用戶在提交作業(yè)時同時提交作業(yè)運行時間的估計值。

最高優(yōu)先級調(diào)度(Priority Scheduling)：每一個作業(yè)規(guī)定一個表示該作業(yè)優(yōu)先級別的整數(shù)，當(dāng)需要將新的作業(yè)由輸入井調(diào)入內(nèi)存處理時，優(yōu)先選擇優(yōu)先數(shù)最高的作業(yè)。

4.最高響應(yīng)比優(yōu)先算法(HRN)：既利于短作業(yè)又有利于長作業(yè)，選擇響應(yīng)比最高的作業(yè)運行。響應(yīng)比=1+作業(yè)等待時間/作業(yè)處理時間。

時間片輪轉(zhuǎn)(RR, Round Robin)

多級反饋隊列調(diào)度(multilevel feedback queue scheduling)

實時調(diào)度算法:

最早截至?xí)r間優(yōu)先 EDF

最低松弛度優(yōu)先 LLF

協(xié)程

? 調(diào)度算法對于程序來說都是“被動”式的。比如調(diào)度算法會把CPU的時間分配給還在IO等待中的程序，雖然可以立即檢查并交出CPU，但是這里還是有一個切換的過程。

? 協(xié)程可以說是“主動式”的，由程序來告訴計算機，我要進行等待IO行為了，可以把CPU的控制權(quán)交給別人，這個實現(xiàn)的基礎(chǔ)是用戶態(tài)的。所以，協(xié)程就是在用戶態(tài)線程中，兩個程序協(xié)商好了，通過某種方式協(xié)作運營，共享CPU控制權(quán)的方法。一般來說，這個協(xié)商的方法通用的關(guān)鍵字就是yield。

協(xié)程與進程線程比較有什么優(yōu)勢？

協(xié)程避免了無意義的調(diào)度，由此可以提高性能，但也因此，程序員必須自己承擔(dān)調(diào)度的責(zé)任，同時，協(xié)程也失去了標(biāo)準(zhǔn)線程使用多CPU的能力

孤兒進程

一個父進程退出，而它的一個或多個子進程還在運行，那么那些子進程將成為孤兒進程。孤兒進程將被init進程(進程號為1)所收養(yǎng)，并由init進程對它們完成狀態(tài)收集工作。

僵尸進程

如果子進程已經(jīng)退出，但是父進程又沒有調(diào)用wait/waitpid獲取子進程的狀態(tài)信息，釋放它占用的資源，該子進程將成為僵尸進程。

僵尸進程怎么解除？怎么避免？

需要找到其父進程：ps -ef | grep defunct_process_pid并kill掉。

如何避免：在fork子進程之后我們都要wait它們；同時，當(dāng)子進程退出的時候，內(nèi)核都會給父進程一個SIGCHLD信號，我們可以建立一個捕獲SIGCHLD信號的處理函數(shù)，在函數(shù)體中調(diào)用wait(或waitpid)，就可以清理退出的子進程以達到防止僵尸進程的目的。

物理內(nèi)存與虛擬內(nèi)存

物理內(nèi)存就是系統(tǒng)硬件提供的內(nèi)存大小，是真正的內(nèi)存；

虛擬內(nèi)存是為了滿足物理內(nèi)存的不足而提出的策略，它是利用磁盤空間虛擬出的一塊邏輯內(nèi)存，用作虛擬內(nèi)存的磁盤空間被稱為交換空間(SwapSpace)。

linux內(nèi)存管理機制

linux的內(nèi)存管理采取的是分頁存取機制，為了保證物理內(nèi)存能得到充分的利用，內(nèi)核會在適當(dāng)?shù)臅r候?qū)⑽锢韮?nèi)存中不經(jīng)常使用的數(shù)據(jù)頁自動交換到虛擬內(nèi)存的交換空間中，而將經(jīng)常使用的信息保留到物理內(nèi)存。

Linux內(nèi)存管理相比于windows的一個優(yōu)秀特性，就是它的緩存機制，它會從內(nèi)存中劃分出一部分空間作為cache、buffers。這樣當(dāng)操作系統(tǒng)需要讀取某些文件時，會首先在buffers和cached內(nèi)存區(qū)查找，如果沒有找到需要的數(shù)據(jù)才從磁盤讀取。因為內(nèi)存的訪問速度必磁盤快很多，而且數(shù)據(jù)一旦被訪問就很有可能在短期內(nèi)被再次訪問。所以提高了Linux系統(tǒng)的數(shù)據(jù)訪問性能。

注：buffers主要用來存放目錄、文件屬性及權(quán)限等等；而cached直接用來緩存我們常用到的文件和數(shù)據(jù)。

要深入了解linux內(nèi)存運行機制，需要知道下面提到的幾個方面：

?Linux系統(tǒng)會根據(jù)系統(tǒng)配置不時地進行頁面交換操作，以保持一定量的空閑物理內(nèi)存，有些配置下即使并沒有什么事情需要內(nèi)存，Linux也會交換出暫時不用的內(nèi)存頁面。這可以避免等待交換所需的時間。

?Linux 進行頁面交換是有條件的，不是所有頁面在不用時都交換到虛擬內(nèi)存，linux內(nèi)核根據(jù)“最近最經(jīng)常使用”算法，僅僅將一些不經(jīng)常使用的頁面文件交換到虛擬內(nèi)存

?交換空間的頁面在使用時會首先被交換到物理內(nèi)存，如果此時沒有足夠的物理內(nèi)存來容納這些頁面，它們又會被馬上交換出去，如此以來，虛擬內(nèi)存中可能沒有足夠空間來存儲這些交換頁面，最終會導(dǎo)致linux出現(xiàn)假死機、服務(wù)異常等問題，linux雖然可以在一段時間內(nèi)自行恢復(fù)，但是恢復(fù)后的系統(tǒng)已經(jīng)基本不可用了。所以，需要合理規(guī)劃和設(shè)計Linux內(nèi)存的使用

注：

內(nèi)存監(jiān)控常用指令：top、free；

linux可用內(nèi)存=free+cached+buffers=total-used

內(nèi)存泄漏

指某塊內(nèi)存塊使用完后沒有及時釋放，不能被再次使用，我們就說這塊內(nèi)存泄漏了。

如何避免內(nèi)存泄漏？

1.減少不必要的全局變量或者生命周期較長的對象，像HashMap等的使用很容易出現(xiàn)內(nèi)存泄露。

2.注意程序邏輯，避免“死循環(huán)”之類的

3.避免創(chuàng)建過多的對象和臨時變量。

4，成對使用new與delete,malloc和free；用類指針對象代替原始指針，利用析構(gòu)函數(shù)自動釋放內(nèi)存資源

5，對于循環(huán)引用導(dǎo)致的內(nèi)存泄漏可以使用弱引用的智能指針來解決

6，監(jiān)聽器在釋放對象時及時刪除，數(shù)據(jù)庫連接及時關(guān)閉。

注：智能指針是一種資源管理類，通過對原始指針進行封裝，在資源管理對象進行析構(gòu)時對指針指向的內(nèi)存進行釋放，通常使用引用計數(shù)方式進行管理。

如何定位內(nèi)存泄漏？

1，如何發(fā)現(xiàn)內(nèi)存泄漏？

實際上不同的系統(tǒng)都帶有內(nèi)存監(jiān)視工具，我們可以從監(jiān)視工具收集一段時間內(nèi)的堆棧內(nèi)存信息，觀測增長趨勢，來確定是否有內(nèi)存泄漏。在 Linux 平臺可以用 ps 命令，來監(jiān)視內(nèi)存的使用，比如 ps -aux ， (觀測指定進程的VSZ值)。

我們可以使用top指令觀察進程的動態(tài)內(nèi)存總額。

程序退出時，可以使用ps、kill兩個命令檢測內(nèi)存使用情況和進行回收。

定位方法(包括靜態(tài)分析，動態(tài)實時檢測)

2, 靜態(tài)分析

包括手動檢測和靜態(tài)工具分析，這是代價最小的調(diào)試方法。

2.1 手動檢測:通過少量的實踐和適當(dāng)?shù)奈谋舅阉?#xff0c;您能夠快速驗證平衡的 malloc() 和 free() 或者 new 和 delete 的源主體。人工檢測

2.2 靜態(tài)代碼分析工具

比如 splint, PC-LINT, BEAM 等。

BEAM 可以檢測四類問題: 沒有初始化的變量；廢棄的空指針；內(nèi)存泄漏；冗余計算。而且支持的平臺比較多

3,動態(tài)運行檢測

實時檢測工具主要有 valgrind, Rational purify 等。

1、valgrind。valgrind檢測的內(nèi)存泄漏是非常準(zhǔn)的，可以精確定位到代碼行甚至是變量。valgrind基于valginrd core框架，這是個非常有強大的框架，他的作用不僅僅在于檢測內(nèi)存泄漏的，強烈建議測試新手通讀下全部的文檔。valgind自己也會有誤報和漏報，所有具體場景需要具體分析。報告中一旦出現(xiàn)definitely lost的標(biāo)記，就表示一定會有內(nèi)存泄漏，泄漏的字節(jié)數(shù)也會報告出來，可以根據(jù)泄漏的內(nèi)存大小和請求次數(shù)計算出到底是那個變量沒有釋放。

2、利用pmap+gdb，pmap可以列出特定進程的所有內(nèi)存分配的地址和大小，通過gdb就可以直接看這些地址屬于什么變量，通過統(tǒng)計這些內(nèi)存地址的大小，就可以很容易的發(fā)現(xiàn)問題。利用自動化的gdb調(diào)試工具也可以很方便的定位。

3、其他的還包括memprof、商業(yè)工具Purify IBM出品，官方宣傳說的不錯，但是這種不開放的技術(shù)，在業(yè)界得不到認(rèn)可，國內(nèi)大公司一般那都不用，只有人傻錢多的公司在用。

4、利用一些trace工具，比如ptrace，strace之類的工具，這些trace工具會追蹤特定的api，只需要統(tǒng)計malloc和free的調(diào)用次數(shù)就可以簡單的發(fā)現(xiàn)是否有泄漏，但是無法定位代碼行。另外還有一個更高深的工具，SystemTap，這個在國內(nèi)應(yīng)用還不多，但是非常厲害，可以方便hook程序的關(guān)鍵邏輯并插入探針。從而可以方便的檢測內(nèi)存泄漏。Systemtap目前還不通用，而且安裝復(fù)雜，暫時不推薦使用，可以關(guān)注下，過幾年可能會大規(guī)模應(yīng)用。

linux系統(tǒng)中找出并解決程序錯誤方法：

● 添加’print’ 打印語句

● 查詢 (/proc, /sys 等)

死鎖

死鎖：是指多個進程因競爭共享資源而造成的一種僵局，若無外力作用，這些進程都在等待對方執(zhí)行完畢才能繼續(xù)往下執(zhí)行，都陷入了無限的等待中。

原因:

系統(tǒng)資源不足后分配不當(dāng)

程序推進順序不當(dāng)

4個必要條件:

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

請求和保持條件：當(dāng)進程因請求資源而阻塞時，對已獲得的資源保持不放。

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

環(huán)路等待條件：在發(fā)生死鎖時，必然存在一個進程–資源的環(huán)形鏈。

解決死鎖的基本方法：

(1)預(yù)防死鎖：打破產(chǎn)生死鎖的4個必要條件之一

資源一次性分配：(破壞請求和保持條件)

可剝奪資源：即當(dāng)某進程新的資源未滿足時，釋放已占有的資源(破壞不可剝奪條件)

資源有序分配法：系統(tǒng)給每類資源賦予一個編號，每一個進程按編號遞增的順序請求資源，釋放則相反(破壞環(huán)路等待條件)

(2)避免死鎖(銀行家算法):

系統(tǒng)在進行資源分配之前預(yù)先計算資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，則將資源分配給進程；否則，進程等待。

(3)檢測死鎖：

系統(tǒng)檢測出死鎖發(fā)生的位置和原因，并通過外力把它從死鎖狀態(tài)中解脫出來，常采用的方法有：

1)從其他進程剝奪資源：從其它進程剝奪足夠數(shù)量的資源給死鎖進程，以解除死鎖狀態(tài)；

2)撤消死鎖進程：可以直接撤消死鎖進程或撤消代價最小的進程，直至有足夠的資源可用，死鎖狀態(tài).消除為止；所謂代價是指優(yōu)先級、運行代價、進程的重要性和價值等。

(4). 解除死鎖: 1. 剝奪資源 2. 撤銷進程

自旋鎖和互斥鎖

1，自旋鎖：線程一直是running(加鎖——>解鎖)，它是死循環(huán)檢測的，加鎖全程消耗cpu，隨著持鎖時間的增加，開銷線性增長。主要用在臨界區(qū)持鎖時間非常短且CPU資源不緊張的情況下。

2，互斥鎖：線程會從sleep(加鎖)——>running(解鎖)，過程中有上下文的切換，cpu的搶占，信號的發(fā)送等開銷。但是臨界區(qū)持鎖時間的大小并不會對互斥鎖的開銷造成影響。所以雖然互斥鎖的起始開銷可能高于自旋鎖，卻更適合用于臨界區(qū)持鎖時間比較長的操作，比如：

1 臨界區(qū)IO操作

2 臨界區(qū)代碼復(fù)雜或者循環(huán)量大

3 臨界區(qū)競爭非常激烈

4 單核處理器

分頁和分段

分頁: 用戶程序的地址空間被劃分成若干固定大小的區(qū)域，稱為“頁”，相應(yīng)地，內(nèi)存空間分成若干個物理塊，頁和塊的大小相等。可將用戶程序的任一頁放在內(nèi)存的任一塊中，實現(xiàn)了離散分配。會產(chǎn)生內(nèi)零頭。

分段: 將用戶程序地址空間分成若干個大小不等的段，每段可以定義一組相對完整的邏輯信息。存儲分配時，以段為單位，段與段在內(nèi)存中可以不相鄰接，也實現(xiàn)了離散分配。會產(chǎn)生外零頭。

分頁與分段的主要區(qū)別

頁是信息的物理單位,分頁是為了實現(xiàn)非連續(xù)分配,以便解決內(nèi)存碎片問題,是由于系統(tǒng)管理的需要.段是信息的邏輯單位,它含有一組意義相對完整的信息,分段的目的是為了更好地實現(xiàn)共享,滿足用戶的需要.

頁的大小固定,由系統(tǒng)確定,將邏輯地址劃分為頁號和頁內(nèi)地址是由機器硬件實現(xiàn)的.而段的長度卻不固定,決定于用戶所編寫的程序,通常由編譯程序在對源程序進行編譯時根據(jù)信息的性質(zhì)來劃分.

分頁的作業(yè)地址空間是一維的.分段的地址空間是二維的.

在編程的時候，如果是分頁存儲，你只需要給定一個虛擬地址，然后操作系統(tǒng)會自己去把虛擬地址劃分成虛頁號和頁內(nèi)偏移，所以是一維的。而如果是段式存儲的話，你需要給定的虛擬地址必須包括虛段號和段內(nèi)偏移量，因為分段式從程序員的角度來分的，操作系統(tǒng)并不知道，所以段式存儲是二維的。

? 什么是缺頁中斷?

(缺頁中斷就是要訪問的頁不在主存，需要操作系統(tǒng)將其調(diào)入主存后再進行訪問。)

頁面置換算法

先進先出FIFO

最近最久未使用算法LRU:最近一段時間里最久沒有使用過的頁面予以置換.

clock算法

最佳置換算法OPT:不可能實現(xiàn)

中斷和輪詢的特點

1,中斷是指在計算機執(zhí)行期間，系統(tǒng)內(nèi)發(fā)生急需處理事件，使得CPU暫時中斷當(dāng)前正在執(zhí)行的程序而轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序。待處理完畢后又返回原來被中斷處繼續(xù)執(zhí)行或調(diào)度新的進程執(zhí)行的過程。

2,輪詢是指定時地對各種設(shè)備輪流詢問一遍有無處理要求。有要求的則加以處理。在處理I/O設(shè)備的要求之后，處理機返回繼續(xù)工作。盡管輪詢需要時間，但輪詢要比I/O設(shè)備的速度要快得多，所以一般不會發(fā)生不能及時處理的問題。

當(dāng)然，再快的處理機，能處理的輸入輸出設(shè)備的數(shù)量也是有一定限度的。而且，程序輪詢畢竟占據(jù)了CPU相當(dāng)一部分處理時間，因此，程序輪詢是一種效率較低的方式，在現(xiàn)代計算機系統(tǒng)中已很少應(yīng)用。

輪詢——效率低，等待時間很長，CPU利用率不高。

中斷——容易遺漏一些問題，CPU利用率高。

中斷程序的分類

1，硬中斷就是由硬件引起的中斷。如鍵盤、定時器，以及一些硬件故障等。

硬中斷又可分為可屏蔽中斷(如鍵盤產(chǎn)生的)；非屏蔽中斷(如由微處理器產(chǎn)生的)；

2，軟中斷是由中斷指令(INT)引起的中斷。

select,poll和epoll

select，poll，epoll都是IO多路復(fù)用的機制。I/O多路復(fù)用就通過一種機制，可以監(jiān)視多個描述符，一旦某個描述符就緒(一般是讀就緒或者寫就緒)，能夠通知程序進行相應(yīng)的讀寫操作。

(但select，poll，epoll本質(zhì)上都是同步I/O，因為他們都需要在讀寫事件就緒后自己負(fù)責(zé)進行讀寫，也就是說這個讀寫過程是阻塞的，而異步I/O則無需自己負(fù)責(zé)進行讀寫，異步I/O的實現(xiàn)會負(fù)責(zé)把數(shù)據(jù)從內(nèi)核拷貝到用戶空間)

基本上select有3個缺點(poll改善了第一個缺點，epoll改了三個缺點.):

1. 連接數(shù)受限

2. 查找配對速度慢

3. 數(shù)據(jù)由內(nèi)核拷貝到用戶態(tài)

? select缺點:

1，最大并發(fā)數(shù)限制：默認(rèn)是1024個fd；

2，效率低：采用輪詢處理，每次都會線性掃描整個fd_set，集合越大速度越慢；

3，內(nèi)核/用戶空間內(nèi)存拷貝問題；

? epoll的提升：

1，本身沒有最大并發(fā)連接的限制，僅受系統(tǒng)中進程能打開的最大文件數(shù)目限制；

2，效率提升：epoll是維護一個隊列，直接看隊列是不是空就可以了，epoll只會對”活躍”的socket進行操作，只有活躍的socket才會主動的去調(diào)用fd的callback函數(shù),

3，省去不必要的內(nèi)存拷貝：epoll通過內(nèi)核與用戶空間mmap同一塊內(nèi)存實現(xiàn)。

? epoll 實現(xiàn)：

epoll是一種IO多路復(fù)用技術(shù)，可以非常高效的處理數(shù)以百萬計的socket句柄，非常適合監(jiān)視大量在線用戶，也就是長連接，少量活躍用戶的情況。

首先要調(diào)用epoll_create建立一個epoll對象。然后通過epoll_ctl可以操作建立的epoll，例如，將剛建立的socket加入到epoll中讓其監(jiān)控，或者把epoll正在監(jiān)控的某個socket句柄移出epoll，不再監(jiān)控它等等。epoll_wait在調(diào)用時，在給定的timeout時間內(nèi)，當(dāng)在監(jiān)控的句柄中有事件發(fā)生時，就返回用戶態(tài)的進程。

epoll比select的優(yōu)越之處：select每次調(diào)用時都要將用戶態(tài)的socket列表copy到內(nèi)核態(tài)，非常低效；而我們調(diào)用epoll_wait時就不用傳遞socket句柄給內(nèi)核，因為內(nèi)核已經(jīng)在epoll_ctl中拿到了要監(jiān)控的socket句柄列表。

相關(guān)問題：

? connect會阻塞，怎么解決?(提示：1，使用計時器；2，設(shè)置非阻塞，返回之后用select檢測狀態(tài))

? 如果select返回可讀，結(jié)果只讀到0字節(jié)，什么情況？(某個套接字集合沒有準(zhǔn)備好，可能select內(nèi)存用FD_CLR將該位清為0).

邊沿觸發(fā)和水平觸發(fā)

邊緣觸發(fā)是指每當(dāng)狀態(tài)變化時發(fā)生一個 io 事件，條件觸發(fā)是只要滿足條件就發(fā)生一個 io 事件

邊緣觸發(fā)(ET)：使用此種模式，只能獲取一次就緒通知，如果沒有處理完全部數(shù)據(jù)，并且再次調(diào)用epoll_wait()的時候，它將會阻塞，因為就緒事件已經(jīng)釋放出來了。ET的效能更高，但是要求也更高。在ET模式下，必須一次性處理完所有事件。ET只支持非阻塞socket)

水平觸發(fā)(LT，也叫條件觸發(fā))：使用此種模式，當(dāng)數(shù)據(jù)可讀的時候，epoll_wait()將會一直返回就緒事件。如果你沒有處理完全部數(shù)據(jù)，并且再次在該 epoll實例上調(diào)用epoll_wait()才監(jiān)聽描述符的時候，它將會再次返回就緒事件，因為有數(shù)據(jù)可讀。

概念：

同步、異步、阻塞、非阻塞

同步和異步關(guān)注的是消息通信機制。

同步是A發(fā)出一個調(diào)用后等待B完成返回結(jié)果再繼續(xù)向下執(zhí)行；

異步是A不需等待返回結(jié)果，繼續(xù)處理其他事情，等B完成后再取回結(jié)果。

阻塞和非阻塞關(guān)注的是程序在等待調(diào)用結(jié)果(消息，返回值)時的狀態(tài).

阻塞是指調(diào)用結(jié)果返回之前，當(dāng)前線程會被掛起，線程只有在得到結(jié)果之后才會返回。

非阻塞指沒有得到返回結(jié)果之前，該調(diào)用不會阻塞當(dāng)前線程。

計算機從電源加載開始的啟動過程

啟動引導(dǎo)程序BIOS-開機自檢-加載操作系統(tǒng)(從磁盤讀到RAM中)-讀取配置文件)

C/C++

關(guān)鍵字static的作用

在c語言中，static關(guān)鍵字的作用：

函數(shù)體內(nèi)static變量的作用范圍為該函數(shù)體，該變量的內(nèi)存只被分配一次，因此其值在下次調(diào)用時人維持上次的值。

在模塊內(nèi)的static全局變量可以被模塊內(nèi)的所有函數(shù)訪問，但不能被模塊外的其他函數(shù)訪問。

在模塊內(nèi)的static函數(shù)只可被這一模塊內(nèi)的其它函數(shù)調(diào)用，這個函數(shù)的使用范圍被限制在申明它的模塊內(nèi)

在類中的static成員變量屬于整個類所擁有，對類的所有對象只有一份拷貝

在類中的static成員函數(shù)屬于整個類所擁有，這個函數(shù)不接收this指針，因而只能訪問類的static成員變量

C++中：

隱藏函數(shù)，所有未加static的全局變量和函數(shù)都具有全局可見性。

保持變量內(nèi)容的持久性。共有兩種變量存儲在靜態(tài)存儲區(qū)：全局變量和static變量。存儲在靜態(tài)數(shù)據(jù)區(qū)的變量會在程序剛開始時完成唯一的一次初始化。static可以控制變量的課件范圍(隱藏)

靜態(tài)數(shù)據(jù)成員是靜態(tài)存儲的，所以必須對它進行初始化。static變量默認(rèn)默認(rèn)初始化為0.

注：C++成員函數(shù)不能同時又static和const進行修飾。因為static表示該函數(shù)是靜態(tài)成員函數(shù)，為類所有，而const是用于修飾成員函數(shù)的，兩者矛盾。

關(guān)鍵字const的作用

c語言中，const關(guān)鍵字的作用主要有以下幾點：

(1)可以定義const常量，具有不可變性。例如： const int Max=100; int Array[Max];

(2)便于進行類型檢查，使編譯器對處理內(nèi)容有更多了解，消除了一些隱患。例如： void f(const int i) { ………} 編譯器就會知道i是一個常量，不允許修改；

(3)可以避免意義模糊的數(shù)字出現(xiàn)，同樣可以很方便地進行參數(shù)的調(diào)整和修改。

(4)可以保護被修飾的東西，防止意外的修改，增強程序的健壯性。還是上面的例子，如果在函數(shù)體內(nèi)修改了i，編譯器就會報錯；例如：

void f(const int i) { i=10;//error! }

(5) 為函數(shù)重載提供了一個參考。

class A { ……

void f(int i) {……} //一個函數(shù)

void f(int i) const {……} //上一個函數(shù)的重載 ……

};

(6) 可以節(jié)省空間，避免不必要的內(nèi)存分配。例如：

#define PI 3.14159 //常量宏 const doulbe Pi=3.14159; //此時并未將Pi放入ROM中 ...... double i=Pi; //此時為Pi分配內(nèi)存，以后不再分配！ double I=PI; //編譯期間進行宏替換，分配內(nèi)存 double j=Pi; //沒有內(nèi)存分配 double J=PI; //再進行宏替換，又一次分配內(nèi)存！

const定義常量從匯編的角度來看，只是給出了對應(yīng)的內(nèi)存地址，而不是象#define一樣給出的是立即數(shù)，所以，const定義的常量在程序運行過程中只有一份拷貝，而#define定義的常量在內(nèi)存中有若干個拷貝。

(7) 提高了效率。編譯器通常不為普通const常量分配存儲空間，而是將它們保存在符號表中，這使得它成為一個編譯期間的常量，沒有了存儲與讀內(nèi)存的操作，使得它的效率也很高。

const define inline的區(qū)別

本質(zhì)：define只是字符串替換，const參與編譯運行，inline由編譯器控制。

(1)define：僅僅是宏替換，不做類型檢查；不占用內(nèi)存

(2)const：擁有類型，會執(zhí)行相應(yīng)的類型；占用內(nèi)存；(const內(nèi)存效率更高，編譯器通常將const變量保存在符號表中，使它成為一個編譯期間的常量，沒有存儲和讀取的操作)

(3)inline：會真正地編譯到代碼中；inline函數(shù)是否展開由編譯器決定，有時候函數(shù)太大時編譯器可能會選擇不展開相應(yīng)的函數(shù)。

如何

用 gdb 調(diào)試

使用編譯器(cc/gcc/g++)的 -g 參數(shù)把調(diào)試信息加到可執(zhí)行文件中。

使用gdb 指令啟動GDB。

如何調(diào)試運行中的程序

用 gdb調(diào)試運行狀態(tài)下的程序，核心的是gdb內(nèi)部的attach命令，例如 attach pid

運行了幾天的程序崩掉，如何分析錯誤

首先在調(diào)試環(huán)境的console或log文件中，根據(jù)錯誤信息的內(nèi)容初步判斷錯誤類型與位置，比如實際為null的內(nèi)存被使用，當(dāng)然也可能是其他錯誤，在這個位置加入斷點，一旦執(zhí)行該行，程序即崩潰(無法調(diào)試的環(huán)境下則加入充分的debug信息)，再次運行程序，在這一點上監(jiān)視各個變量，找到導(dǎo)致崩潰的變量值，向上追溯，找到賦值操作的根源時，錯誤的原因也就找到了，接下來就是討論對策與解決方案

程序編譯與鏈接

Bulid過程可以分解為4個步驟:預(yù)處理(Prepressing), 編譯(Compilation)、匯編(Assembly)、鏈接(Linking)

以c語言為例:

1 預(yù)處理

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

將所有的“#define”刪除，并展開所用的宏定義

處理所有條件預(yù)編譯指令，比如“#if”、“#ifdef”、 “#elif”、“#endif”

處理“#include”預(yù)編譯指令，將被包含的文件插入到該編譯指令的位置，注：此過程是遞歸進行的

刪除所有注釋

添加行號和文件名標(biāo)識，以便于編譯時編譯器產(chǎn)生調(diào)試用的行號信息以及用于編譯時產(chǎn)生編譯錯誤或警告時可顯示行號

保留所有的#pragma編譯器指令。

2 編譯

編譯過程就是把預(yù)處理完的文件進行一系列的詞法分析、語法分析、語義分析及優(yōu)化后生成相應(yīng)的匯編代碼文件。這個過程是整個程序構(gòu)建的核心部分。

3 匯編

匯編器是將匯編代碼轉(zhuǎn)化成機器可以執(zhí)行的指令，每一條匯編語句幾乎都是一條機器指令。經(jīng)過編譯、鏈接、匯編輸出的文件成為目標(biāo)文件(Object File)

4 鏈接

鏈接的主要內(nèi)容就是把各個模塊之間相互引用的部分處理好，使各個模塊可以正確的拼接。

鏈接的主要過程包塊地址和空間的分配(Address and Storage Allocation)、符號決議(Symbol Resolution)和重定位(Relocation)等步驟。

靜態(tài)鏈接

靜態(tài)鏈接就是在編譯鏈接時直接將需要的執(zhí)行代碼拷貝到調(diào)用處，優(yōu)點就是在程序發(fā)布的時候就不需要的依賴庫，也就是不再需要帶著庫一塊發(fā)布，程序可以獨立執(zhí)行，但是體積可能會相對大一些。

靜態(tài)庫的鏈接可以使用靜態(tài)鏈接，動態(tài)鏈接庫也可以使用這種方法鏈接導(dǎo)入庫

動態(tài)鏈接

動態(tài)鏈接就是在編譯的時候不直接拷貝可執(zhí)行代碼，而是通過記錄一系列符號和參數(shù)，在程序運行時將需要的動態(tài)庫加載到內(nèi)存中，當(dāng)程序運行到指定的代碼時，去執(zhí)行已加載的動態(tài)庫可執(zhí)行代碼，最終達到運行時連接的目的。優(yōu)點是多個程序可以共享同一段代碼，而不需要在磁盤上存儲多個拷貝，程序初始化時間較短，但運行期間的性能比不上靜態(tài)鏈接的程序。

什么是庫

所謂庫就是一些功能代碼經(jīng)過編譯連接后的可執(zhí)行形式：

靜態(tài)庫：在程序編譯時會被連接到目標(biāo)代碼中，程序運行時將不再依賴靜態(tài)庫。

動態(tài)庫：在程序編譯時并不會被連接到目標(biāo)代碼中，而是在程序運行是才被載入，因此在程序運行時還需要動態(tài)庫存在

? 標(biāo)準(zhǔn)庫函數(shù)和系統(tǒng)調(diào)用的區(qū)別？

庫是可重用的模塊,處于用戶態(tài);系統(tǒng)調(diào)用是os提供的服務(wù),處于內(nèi)核態(tài),是指最底層的一個調(diào)用.庫函數(shù)中有很大部分是對系統(tǒng)調(diào)用的封裝

如何生成靜態(tài)庫？如何生成動態(tài)庫？

生成靜態(tài)庫：首先由源文件編譯生成.o文件，使用ar命令將.o轉(zhuǎn)換成.a文件，生成靜態(tài)庫(以lib開頭，以.a結(jié)尾)；

動態(tài)庫的后綴是.so，編譯生成動態(tài)庫的命令為：gcc (-fpic) -shared -o libmyfunction.so myfunction.c (-fpic 使輸出的對象模塊是按照可重定位地址方式生成的。 -shared指定把對應(yīng)的源文件生成對應(yīng)的動態(tài)鏈接庫文件)

?引用動態(tài)庫時為什么編譯能通過，而運行不能通過：編譯是按你指定的路徑去編譯，而運行時是通過環(huán)境變量去找，所以這時候就要指定路徑，把路徑加到環(huán)境變量中就OK了。

? 如何查看鏈接的動態(tài)庫(ldd a 會列出a所依賴的動態(tài)庫)

makefile

文件的作用是什么？

makefile帶來的好處就是“自動化編譯”。

makefile定義了一系列的規(guī)則來指定哪些文件需要先編譯，哪些文件需要后編譯，哪些文件需要重新編譯，甚至于進行更復(fù)雜的功能操作。因為makefile就像一個Shell腳本一樣，其中也可以執(zhí)行操作系統(tǒng)的命令。一旦寫好，只需要一個make命令，整個工程完全自動編譯，極大地提高了軟件開發(fā)的效率。

如何編寫 makefile

makefile的語法:

target(目標(biāo)) : prerequisites.(依賴文件)

command(shell命令)

vim makefile hello.o:hello.c hello.h gcc –c hello.o -Lm make ./hello

Makefile的規(guī)則：

目標(biāo) ：需要的條件 (注意冒號兩邊有空格)

命令　　(注意前面用tab鍵開頭)

解釋一下：

1 目標(biāo)可以是一個或多個，可以是Object File，也可以是執(zhí)行文件，甚至可以是一個標(biāo)簽。

2 需要的條件就是生成目標(biāo)所需要的文件或目標(biāo)

3 命令就是生成目標(biāo)所需要執(zhí)行的腳本

i++

是否是原子操作？

不是。.i++分為三個階段：內(nèi)存到寄存器；寄存器自增；寫回內(nèi)存。這三個階段中間都可以被中斷分離開.而原子操作是不可分割的，不加鎖互斥是不行的

算法與數(shù)據(jù)結(jié)構(gòu)

數(shù)組和鏈表

從邏輯結(jié)構(gòu)來看：

1. 數(shù)組必須事先定義固定的長度(元素個數(shù))，不能適應(yīng)數(shù)據(jù)動態(tài)地增減的情況。當(dāng)數(shù)據(jù)增加時，可能超出原先定義的元素個數(shù)；當(dāng)數(shù)據(jù)減少時，造成內(nèi)存浪費；數(shù)組根據(jù)下標(biāo)查找方便，訪問效率高。

2. 鏈表動態(tài)地進行內(nèi)存分配，需要時可以用new分配內(nèi)存空間，不需要時用delete將已分配的空間釋放，不會造成內(nèi)存空間的浪費。且可以方便地插入、刪除操作項。(數(shù)組中插入、刪除數(shù)據(jù)項時，需要移動其它數(shù)據(jù)項，非常繁瑣；鏈表根據(jù)next指針找到下一個元素)

從內(nèi)存存儲來看：

1. (靜態(tài))數(shù)組從棧中分配空間, 對于程序員方便快速,但是自由度小

2. 鏈表從堆中分配空間, 自由度大但是申請管理比較麻煩

綜上，如果需要快速訪問數(shù)據(jù)，很少或不插入和刪除元素，就應(yīng)該用數(shù)組；相反，如果需要經(jīng)常插入和刪除元素就需要用鏈表數(shù)據(jù)結(jié)構(gòu)了。

數(shù)組和集合

數(shù)組：長度固定可以存儲基本數(shù)據(jù)類型和引用數(shù)據(jù)類型(存儲的元素必須是同一數(shù)據(jù)類型)；

集合：長度可變，只能存儲引用數(shù)據(jù)類型(數(shù)組，類，接口)(存儲的元素可以是不同數(shù)據(jù)類型)；

二叉樹

●二叉搜索/查找樹：左子樹的所有節(jié)點值均小于根節(jié)點值，右子樹的所有節(jié)點值均不小于根節(jié)點值；或是一顆空樹

●完全二叉樹：只有最下面一層的節(jié)點度可以小于2，且都集中在最左邊的若干位置

●平衡二叉樹(AVL)：左右子樹的深度差不超過1,；或為空樹。(windows對進程地址空間的管理用到了AVL樹)

●紅黑樹：是一種自平衡的二叉查找樹，追求局部平衡，通過對任何一條從根節(jié)點到葉子節(jié)點的簡單路徑上的各個節(jié)點的顏色進行約束，確保一個節(jié)點的兩顆子樹高度差不會相差兩倍，保證每次插入最多只需3次旋轉(zhuǎn)就能達到平衡。典型的應(yīng)用是關(guān)聯(lián)數(shù)組。

性質(zhì)：

1)結(jié)點或者是紅的或者是黑的；

2)根結(jié)點是黑的；

3)每個葉結(jié)點(即空節(jié)點NIL)是黑的；

4)如果一個結(jié)點是紅的，則它的兩個孩子都是黑的；

5)對每個結(jié)點，從該結(jié)點到其他子結(jié)點的所有路徑上包含相同數(shù)目的黑結(jié)點。

●B樹：是一種多路查找樹，一般用于數(shù)據(jù)庫系統(tǒng)中，分支多層數(shù)少，降低I/O耗時

●B+樹：是B樹的變種樹，數(shù)據(jù)只保存在葉子節(jié)點中，其他節(jié)點中含有關(guān)鍵字，每個關(guān)鍵字不保存數(shù)據(jù)只用來索引，為文件系統(tǒng)而生。

●Trie樹：又名單詞查找樹，主要處理字符串，將字符串的相同前綴保存在相同節(jié)點中，經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。

●哈夫曼樹(最優(yōu)二叉樹)：給定n個權(quán)值的葉子結(jié)點，構(gòu)造一棵二叉樹，若樹的帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權(quán)路徑長度最短的樹，權(quán)值較大的結(jié)點離根較近。

結(jié)點的帶權(quán)路徑長度：結(jié)點到樹根之間的路徑長度與該結(jié)點上權(quán)的乘積.

下面演示了用Huffman算法構(gòu)造一棵Huffman樹的過程：

用一個類似于樹杈的“樹枝”連接兩個最小權(quán)值。在頂點處計算出這兩個數(shù)字的和并寫在上面。然后再比較剩下的數(shù)字和這個和的大小，如果該和正好是下一步的兩個最小數(shù)的其中一個那么這個樹直接往上生長就可以了。如果該數(shù)不是下一步的兩個最小數(shù)的其中一個那么，就并列生長。

通過哈夫曼樹來構(gòu)造的編碼稱為哈弗曼編碼：

霍夫曼編碼是一種無前綴的不定長的編碼。解碼時不會混淆。其主要應(yīng)用在數(shù)據(jù)壓縮，加密解密等場合。

使用頻度較高的字符分配較短的編碼，使用頻度較低的字符分配較長的編碼。但當(dāng)信息源各符號出現(xiàn)的概率很不平均的時候，哈夫曼編碼的效果才明顯。

假如我有A,B,C,D,E五個字符，出現(xiàn)的頻率(即權(quán)值)分別為5,4,3,2,1,取兩個最小權(quán)值作為左右子樹依次建立哈夫曼樹，如下圖：

其中各個權(quán)值替換對應(yīng)的字符即為下圖：

所以各字符對應(yīng)的編碼為：A->11,B->10,C->00,D->011,E->010

排序算法與字符串匹配算法

交換排序：冒泡排序、快速排序

選擇排序：簡單選擇排序、堆排序

插入排序：直接插入排序、二分法插入排序、希爾排序

歸并排序、基數(shù)排序

最短路徑算法

1，Dijkstra(迪杰斯特拉)算法

Dijkstra算法(迪杰斯特拉)是典型的最短路徑路由算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。其采用的是貪心算法的策略，主要特點是以起始點為中心向外層層擴展，找出距起始點最近的點，直到擴展到終點為止。

Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。可以用堆優(yōu)化。

大概過程：

創(chuàng)建兩個表，OPEN, CLOSE。

OPEN表保存所有已生成而未考察的節(jié)點，CLOSED表中記錄已訪問過的節(jié)點。

1．訪問路網(wǎng)中距離起始點最近且沒有被檢查過的點，把這個點放入OPEN組中等待檢查。

2．從OPEN表中找出距起始點最近的點，找出這個點的所有子節(jié)點，把這個點放到CLOSE表中。

3．遍歷考察這個點的子節(jié)點。求出這些子節(jié)點距起始點的距離值，放子節(jié)點到OPEN表中。

4．重復(fù)第2和第3步,直到OPEN表為空，或找到目標(biāo)點。

2，Floyd算法\Floyd-Warshall算法

Floyd算法又稱為插點法，是一種利用動態(tài)規(guī)劃的思想尋找給定的加權(quán)圖中多源點之間最短路徑的算法，與Dijkstra算法類似。

優(yōu)點：容易理解，可以算出任意兩個節(jié)點之間的最短距離，代碼編寫簡單。

缺點：時間復(fù)雜度比較高，不適合計算大量數(shù)據(jù)。時間復(fù)雜度:O(n^3)；空間復(fù)雜度:O(n^2)

Floyd算法適用于APSP(All Pairs Shortest Paths，多源最短路徑)，是一種動態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法，也要高于執(zhí)行V次SPFA算法。

算法過程：

1，從任意一條單邊路徑開始。所有兩點之間的距離是邊的權(quán)，如果兩點之間沒有邊相連，則權(quán)為無窮大。

2，對于每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比已知的路徑更短。如果是更新它。

把圖用鄰接矩陣G表示出來，如果從Vi到Vj有路可達，則G[i,j]=d，d表示該路的長度；否則G[i,j]=無窮大。定義一個矩陣D用來記錄所插入點的信息，D[i,j]表示從Vi到Vj需要經(jīng)過的點，初始化D[i,j]=j。把各個頂點插入圖中，比較插點后的距離與原來的距離，G[i,j] = min( G[i,j], G[i,k]+G[k,j] )，如果G[i,j]的值變小，則D[i,j]=k。在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通路徑的信息。

比如，要尋找從V5到V1的路徑。根據(jù)D，假如D(5,1)=3則說明從V5到V1經(jīng)過V3，路徑為{V5,V3,V1}，如果D(5,3)=3，說明V5與V3直接相連，如果D(3,1)=1，說明V3與V1直接相連。

３，SPFA算法\Bellman-Ford算法

SPFA(Shortest Path Faster Algorithm)(隊列優(yōu)化)算法是求單源最短路徑的一種算法，它還有一個重要的功能是判負(fù)環(huán)(在差分約束系統(tǒng)中會得以體現(xiàn))，在Bellman-ford算法的基礎(chǔ)上加上一個隊列優(yōu)化，減少了冗余的松弛操作，是一種高效的最短路算法。

對SPFA的一個很直觀的理解就是由無權(quán)圖的BFS轉(zhuǎn)化而來。在無權(quán)圖中，BFS首先到達的頂點所經(jīng)歷的路徑一定是最短路(也就是經(jīng)過的最少頂點數(shù))，所以此時利用數(shù)組記錄節(jié)點訪問可以使每個頂點只進隊一次，但在帶權(quán)圖中，最先到達的頂點所計算出來的路徑不一定是最短路。一個解決方法是放棄數(shù)組，此時所需時間自然就是指數(shù)級的，所以我們不能放棄數(shù)組，而是在處理一個已經(jīng)在隊列中且當(dāng)前所得的路徑比原來更好的頂點時，直接更新最優(yōu)解。

SPFA算法有兩個優(yōu)化策略SLF和LLL——SLF：Small Label First 策略，設(shè)要加入的節(jié)點是j，隊首元素為i，若dist(j)< dist(i)，則將j插入隊首，否則插入隊尾； LLL：Large Label Last 策略，設(shè)隊首元素為i，隊列中所有dist值的平均值為x，若dist(i)>x則將i插入到隊尾，查找下一元素，直到找到某一i使得dist(i)<=x，則將i出隊進行松弛操作。 SLF 可使速度提高 15 ~ 20%；SLF + LLL 可提高約 50%。在實際的應(yīng)用中SPFA的算法時間效率不是很穩(wěn)定，為了避免最壞情況的出現(xiàn)，通常使用效率更加穩(wěn)定的Dijkstra算法。

4，A*算法

A*算法；A*(A-Star)算法是一種靜態(tài)路網(wǎng)中求解最短路徑最有效的直接搜索方法，也是解決許多搜索問題的有效算法。算法中的距離估算值與實際值越接近，最終搜索速度越快。

數(shù)據(jù)庫

范式

第一范式：原子性，字段不可分割

第二范式：就是完全依賴，不能部分依賴；

第三范式：不能存在傳遞依賴

第一范式(例如：學(xué)生信息表)：

學(xué)生編號姓名性別聯(lián)系方式 20080901 張三男 email:zs@126.com,phone:88886666 20080902 李四女 email:ls@126.com,phone:66668888

以上的表就不符合，第一范式：聯(lián)系方式字段可以再分，所以變更為正確的是：

學(xué)生編號姓名性別電子郵件電話 20080901 張三男 zs@126.com 88886666 20080902 李四女 ls@126.com 66668888

第二范式(例如：學(xué)生選課表):

學(xué)生課程教師教師職稱教材教室上課時間李四 Spring 張老師 java講師《Spring深入淺出》３０１ 08:00 張三 Struts 楊老師 java講師《Struts in Action》３０２ 13:30

這里通過(學(xué)生，課程)可以確定教師、教師職稱，教材，教室和上課時間，所以可以把(學(xué)生，課程)作為主鍵。但是，教材并不完全依賴于(學(xué)生，課程)，只拿出課程就可以確定教材，因為一個課程，一定指定了某個教材。這就叫不完全依賴，或者部分依賴。出現(xiàn)這種情況，就不滿足第二范式。

修改后：

選課表：學(xué)生課程教師教師職稱教室上課時間李四 Spring 張老師 java講師３０１ 08:00 張三 Struts 楊老師 java講師３０２ 13:30 課程表：課程教材 Spring 《Spring深入淺出》 Struts 《Struts in Action》

所以，第二范式可以說是消除部分依賴。可以減少插入異常，刪除異常和修改異常。

第三范式：

上例中修改后的選課表中，一個教師能確定一個教師職稱。這樣，教師依賴于(學(xué)生，課程)，而教師職稱又依賴于教師，這叫傳遞依賴。第三范式就是要消除傳遞依賴。

修改后：

選課表：學(xué)生課程教師教室上課時間李四 Spring 張老師３０１ 08:00 張三 Struts 楊老師３０２ 13:30 教師表：教師教師職稱張老師 java講師楊老師 java講師

這樣，新教師的職稱在沒被選課的時候也有地方存了，沒人選這個教師的課的時候教師的職稱也不至于被刪除，修改教師職稱時只修改教師表就可以了。

數(shù)據(jù)庫的基本鎖

(1)共享(S)鎖：多個事務(wù)可封鎖一個共享頁；通常是該頁被讀取完畢，S鎖立即被釋放。

它是非獨占的，允許其他事務(wù)同時讀取其鎖定的資源，但不允許其他事務(wù)修改它。

(2)排它(X)鎖：僅允許一個事務(wù)封鎖此頁；X鎖一直到事務(wù)結(jié)束才能被釋放，其他任何事務(wù)必須等到X鎖被釋放才能對該頁進行訪問。適用于修改數(shù)據(jù)的場合。

(3)更新(U)鎖：更新鎖在的初始化階段用來鎖定可能要被修改的資源，避免使用共享鎖造成的死鎖現(xiàn)象。

用來預(yù)定要對此頁施加X鎖，它允許其他事務(wù)讀，但不允許再施加U鎖或X鎖；當(dāng)被讀取的頁將要被更新時，則升級為X鎖；U鎖一直到事務(wù)結(jié)束時才能被釋放。

數(shù)據(jù)庫帶來的并發(fā)問題

丟失更新

當(dāng)兩個或多個事務(wù)選擇同一行，然后基于最初選定的值更新該行時，會發(fā)生丟失更新問題。每個事務(wù)都不知道其它事務(wù)的存在。最后的更新將重寫由其它事務(wù)所做的更新，這將導(dǎo)致數(shù)據(jù)丟失。

例如：事務(wù)A和事務(wù)B同時修改某行的值，事務(wù)A將數(shù)值改為1并提交,事務(wù)B將數(shù)值改為2并提交。這時數(shù)據(jù)的值為2，事務(wù)A所做的更新將會丟失。

如何解決呢？基本兩種思路，一種是悲觀鎖，另外一種是樂觀鎖；

悲觀鎖：假定并發(fā)沖突總是發(fā)生，屏蔽一切可能違反數(shù)據(jù)完整性的操作

樂觀鎖：假設(shè)不會發(fā)生并發(fā)沖突，只在提交操作時檢查是否違反數(shù)據(jù)完整性。

臟讀

當(dāng)一個事務(wù)讀取另一個事務(wù)尚未提交的修改時，產(chǎn)生臟讀。

例如：

1.Mary的原工資為1000, 財務(wù)人員將Mary的工資改為了8000(但未提交事務(wù))

2.Mary讀取自己的工資 ,發(fā)現(xiàn)自己的工資變?yōu)榱?000，歡天喜地！

3.而財務(wù)發(fā)現(xiàn)操作有誤，回滾了事務(wù),Mary的工資又變?yōu)榱?000

像這樣,Mary記取的工資數(shù)8000是一個臟數(shù)據(jù)。

解決辦法：在一個事務(wù)提交前，任何其他事務(wù)不可讀取其修改過的值，則可以避免該問題。

不可重復(fù)讀

同一查詢在同一事務(wù)中多次進行，由于其他提交事務(wù)所做的修改或刪除，每次返回不同的結(jié)果集，此時發(fā)生非重復(fù)讀。

例如：

在事務(wù)1中，Mary 讀取了自己的工資為1000,操作并沒有完成，這時財務(wù)人員修改了Mary的工資為2000,并提交了事務(wù).在事務(wù)1中，Mary 再次讀取自己的工資時，工資變?yōu)榱?000

解決辦法：只有在修改事務(wù)完全提交之后才可以讀取數(shù)據(jù)，則可以避免該問題。

幻讀

同一查詢在同一事務(wù)中多次進行，由于其他提交事務(wù)所做的插入操作，每次返回不同的結(jié)果集，此時發(fā)生幻像讀。

當(dāng)對某行執(zhí)行插入或刪除操作，而該行屬于某個事務(wù)正在讀取的行的范圍時，會發(fā)生幻像讀問題。事務(wù)第一次讀的行范圍顯示出其中一行已不復(fù)存在于第二次讀或后續(xù)讀中，因為該行已被其它事務(wù)刪除。同樣，由于其它事務(wù)的插入操作，事務(wù)的第二次或后續(xù)讀顯示有一行已不存在于原始讀中。

例如：目前工資為1000的員工有10人。

事務(wù)1,讀取所有工資為1000的員工。

這時事務(wù)2向employee表插入了一條員工記錄，工資也為1000。事務(wù)1再次讀取所有工資為1000的員工共讀取到了11條記錄。

解決辦法：在操作事務(wù)完成數(shù)據(jù)處理之前，任何其他事務(wù)都不可以添加新數(shù)據(jù)，則可避免該問題

sql基本語句

SQL (結(jié)構(gòu)化查詢語言)是用于執(zhí)行查詢的語法。但是 SQL 語言也包含用于更新、插入和刪除記錄的語法。可以把 SQL 分為兩個部分：數(shù)據(jù)操作語言 (DML) 和數(shù)據(jù)定義語言 (DDL)。

查詢和更新指令構(gòu)成了 SQL 的 DML 部分：

SELECT - 從數(shù)據(jù)庫表中獲取數(shù)據(jù)

UPDATE - 更新數(shù)據(jù)庫表中的數(shù)據(jù)

DELETE - 從數(shù)據(jù)庫表中刪除數(shù)據(jù)

INSERT INTO - 向數(shù)據(jù)庫表中插入數(shù)據(jù)

SQL 的數(shù)據(jù)定義語言 (DDL) 部分使我們有能力創(chuàng)建或刪除表格。我們也可以定義索引(鍵)，規(guī)定表之間的鏈接，以及施加表間的約束。

SQL 中最重要的 DDL 語句:

CREATE DATABASE - 創(chuàng)建新數(shù)據(jù)庫

ALTER DATABASE - 修改數(shù)據(jù)庫

CREATE TABLE - 創(chuàng)建新表

ALTER TABLE - 變更(改變)數(shù)據(jù)庫表

DROP TABLE - 刪除表

CREATE INDEX - 創(chuàng)建索引(搜索鍵)

DROP INDEX - 刪除索引

基本語法：

下面的例子是一個名為 “Persons” 的表：

注釋：SQL 語句對大小寫不敏感。SELECT 等效于 select。

1,獲取名為 “LastName” 和 “FirstName” 的列的內(nèi)容(從名為 “Persons” 的數(shù)據(jù)庫表)：

SELECT LastName,FirstName FROM Persons

2，如果有多個city相同，僅需列出一次的話(distinct)：

SELECT DISTINCT City FROM Persons

3,顯示所有姓為 “Carter” 并且名為 “Thomas” 的人：

SELECT * FROM Persons WHERE FirstName='Thomas' AND LastName='Carter'

4，以字母順序顯示

SELECT * FROM Persons ORDER BY Year SELECT * FROM Persons ORDER BY Year DESC (逆序)

5，insert；update；delete

INSERT INTO Persons VALUES ('Gates', 'Bill', 'Xuanwumen 10', 'Beijing'，'1986') INSERT INTO Persons (LastName, Address) VALUES ('Wilson', 'Champs-Elysees') #在指定列中插入 UPDATE Persons SET FirstName = 'Fred' WHERE LastName = 'Wilson' #為 lastname 是 "Wilson" 的人添加 firstname DELETE FROM Person WHERE LastName = 'Wilson'

高級語法：

1，top：

SELECT TOP 2 * FROM Persons #從"Persons" 表中選取頭兩條記錄 SELECT TOP 50 PERCENT * FROM Persons #選出前50%的記錄

2，like：

SELECT * FROM Persons WHERE City LIKE 'N%' #選取居住在以 "N" 開頭的城市里的人 SELECT * FROM Persons WHERE City LIKE '%g' #選取居住在以 "g" 結(jié)尾的城市里的人 SELECT * FROM Persons WHERE City LIKE '%lon%' #選取居住在包含 "lon" 的城市里的人 SELECT * FROM Persons WHERE City NOT LIKE '%lon%' #選取居住在不包含 "lon" 的城市里的人 SELECT * FROM Persons WHERE City LIKE '[ALN]%' #選取居住在以 "A、L或N" 開頭的城市里的人

通配符說明：

3，in：從表中選取姓氏為 Adams 和 Carter 的人：

SELECT * FROM Persons WHERE LastName IN ('Adams','Carter')

4，join：用于根據(jù)兩個或多個表中的列之間的關(guān)系，從這些表中查詢數(shù)據(jù)。

“Persons” 表：

“Orders” 表：

“Id_O” 列是 Orders 表中的的主鍵，同時，”O(jiān)rders” 表中的 “Id_P” 列用于引用 “Persons” 表中的人，而無需使用他們的確切姓名。請留意，”Id_P” 列把上面的兩個表聯(lián)系了起來。

我們可以從兩個表中獲取數(shù)據(jù)：誰訂購了產(chǎn)品，和訂購了什么產(chǎn)品

SELECT Persons.LastName, Persons.FirstName, Orders.OrderNo FROM Persons, Orders WHERE Persons.Id_P = Orders.Id_P

除了上面的方法，我們也可以使用關(guān)鍵詞 JOIN 來從兩個表中獲取數(shù)據(jù)：

SELECT Persons.LastName, Persons.FirstName, Orders.OrderNo FROM Persons INNER JOIN Orders ON Persons.Id_P = Orders.Id_P ORDER BY Persons.LastName

補充：INNER JOIN；LEFT JOIN；RIGHT JOIN：

(1)INNER JOIN 返回兩表符合匹配條件的行

(2)LEFT JOIN 關(guān)鍵字會從左表 (table_name1) 那里返回所有的行，即使在右表 (table_name2) 中沒有匹配的行。

(3)RIGHT JOIN 關(guān)鍵字會右表 (table_name2) 那里返回所有的行，即使在左表 (table_name1) 中沒有匹配的行。

1 事務(wù)

數(shù)據(jù)庫事務(wù)(Database Transaction) ，是指作為單個邏輯工作單元執(zhí)行的一系列操作，要么完全地執(zhí)行，要么完全地不執(zhí)行。

2 數(shù)據(jù)庫索引

聚集索引,非聚集索引,B-Tree,B+Tree,最左前綴原理

高并發(fā)

如何在j2ee項目中處理高并發(fā)量訪問？

1、HTML靜態(tài)化。因為純靜態(tài)化的html頁面是效率最高、消耗最小的。

2、圖片服務(wù)器分離。圖片是最消耗資源的，我們有必要將圖片與頁面進行分離，基本上大型網(wǎng)站都會有獨立的、甚至很多臺的圖片服務(wù)器。

3、在面對大量訪問的時候，數(shù)據(jù)庫的瓶頸很快就能顯現(xiàn)出來，我們可以使用數(shù)據(jù)庫集群或者庫表散列。

(數(shù)據(jù)庫集群在架構(gòu)、成本、擴張性方面都會受到所采用數(shù)據(jù)庫類型的限制，庫表散列是從應(yīng)用程序的角度來考慮改善系統(tǒng)架構(gòu)，通過在應(yīng)用程序中安裝功能模塊將數(shù)據(jù)庫進行分離，不同的模塊對應(yīng)不同的數(shù)據(jù)庫或者表，再按照一定的策略對某個頁面或者功能進行更小的數(shù)據(jù)庫散列，比如一個論壇就可以對帖子、用戶按照板塊和ID進行散列數(shù)據(jù)庫和表，這樣就能夠低成本的提升系統(tǒng)的性能并且有很好的擴展性。)

4、緩存。Linux上提供的Memory Cache是常用的緩存接口，比如用Java開發(fā)的時候就可以調(diào)用MemoryCache對一些數(shù)據(jù)進行緩存和通訊共享。

5、搭建鏡像站點，數(shù)據(jù)進行定時更新或者實時更新

6、CDN加速技術(shù)。通過在現(xiàn)有的網(wǎng)絡(luò)中增加一層新的網(wǎng)絡(luò)架構(gòu)，將網(wǎng)站的內(nèi)容發(fā)布到最接近用戶的網(wǎng)絡(luò)“邊緣”，使用戶可以就近取得所需的內(nèi)容，提高用戶訪問網(wǎng)站的響應(yīng)速度。

7、負(fù)載均衡技術(shù)，將整個區(qū)間段的業(yè)務(wù)流分配到合適的應(yīng)用服務(wù)器進行處理：

負(fù)載均衡方式

(1)、DNS負(fù)載均衡，在DNS中為多個地址配置同一個名字，查詢這個名字的客戶機將得到其中一個地址，使得不同的客戶訪問不同的服務(wù)器，達到負(fù)載均衡的目的(DNS負(fù)載均衡是一種簡單而有效的方法，但是它不能區(qū)分服務(wù)器的差異，也不能反映服務(wù)器的當(dāng)前運行狀態(tài))。

(2)、使用代理服務(wù)器，將用戶請求轉(zhuǎn)發(fā)給多臺服務(wù)器，從而達到負(fù)載均衡的目的，提升網(wǎng)頁的訪問速度。

(3)、NAT負(fù)載均衡，通過網(wǎng)絡(luò)地址轉(zhuǎn)換的網(wǎng)關(guān)，將一個外部IP地址映射為多個內(nèi)部IP地址，對每次連接請求動態(tài)使用其中一個內(nèi)部地址，達到負(fù)載均衡的目的。

(4)、協(xié)議內(nèi)部支持負(fù)載均衡，比如HTTP協(xié)議中的重定向能力等，HTTP運行于TCP連接的最高層。

(5)、對于大型網(wǎng)絡(luò)，可以采用混合型負(fù)載均衡，由于多個服務(wù)器群內(nèi)硬件設(shè)備、各自的規(guī)模、提供的服務(wù)等的差異，我們可以考慮給每個服務(wù)器群采用最合適的負(fù)載均衡方式，然后又在這多個服務(wù)器群間再一次負(fù)載均衡向外界提供服務(wù)，從而達到最佳的性能

如何設(shè)計一個高并發(fā)的系統(tǒng)

① 數(shù)據(jù)庫的優(yōu)化，包括合理的事務(wù)隔離級別、SQL語句優(yōu)化、索引的優(yōu)化

② 使用緩存，盡量減少數(shù)據(jù)庫 IO

③ 分布式數(shù)據(jù)庫、分布式緩存

④ 服務(wù)器的負(fù)載均衡

海量數(shù)據(jù)處理問題

2.5億個整數(shù)中找出不重復(fù)的整數(shù)的個數(shù)，內(nèi)存空間不足以容納這2.5億個整數(shù)

有點像鴿巢原理，整數(shù)個數(shù)為2^32,也就是，我們可以將這2^32個數(shù)，劃分為2^8個區(qū)域(比如用單個文件代表一個區(qū)域)，然后將數(shù)據(jù)分離到不同的區(qū)域，然后不同的區(qū)域在利用bitmap就可以直接解決了。也就是說只要有足夠的磁盤空間，就可以很方便

二進制文件中有2.5億個數(shù)字，其中只有10個數(shù)字重復(fù)。

解決思路如下:

采用2-Bitmap(每個數(shù)分配2bit，00表示不存在，01表示出現(xiàn)一次，10表示多次，11無意義)進行。然后掃描這2.5億個整數(shù)，查看Bitmap中相對應(yīng)位，如果是00變01，01變10，10保持不變。所描完事后，查看bitmap，把對應(yīng)位是01的整數(shù)輸出即可。

映射關(guān)系如下：

|00 00 00 00| //映射|3 2 1 0| |00 00 00 00| //映射|7 6 5 4| …… |00 00 00 00|

因此，每個char字符可表示4個數(shù)字。

代碼如下：

#include #include int n=250000000; //數(shù)據(jù)個數(shù) unsigned char flags[250000000/4];//需要n/4個字符 unsigned get_val(int idx) //獲取數(shù)字出現(xiàn)次數(shù) { int i=idx/4; int j=idx%4; unsigned ret=(flags[i]&(0x3<2*j)))>>(2*j); //位運算 return ret; } unsigned set_val(int idx,unsigned int val) //在8bit中設(shè)置數(shù)字出現(xiàn)次數(shù) { int i=idx/4; //確定數(shù)字在字符數(shù)組中的位置 int j=idx%4; //確定數(shù)字在8bit中的位置 unsigned tmp=(flags[i]&~((0x3<2*j)))) | (((val%4)<2*j))); //位運算 flags[i]=tmp; return 0; } unsigned add_one(int idx) //數(shù)字出現(xiàn)次數(shù)+1,如果大于2,不變 { int i=get_val(idx); if (i>=2) return 1; else { set_val(idx,i+1); return 0; } } int main() { FILE *fp; fp=fopen("number.bin","rb"); //讀取二進制數(shù)據(jù)文件 int i; int s=sizeof(int); memset(flags,0,sizeof(flags)); while(!feof(fp)) { fread(&i,s,1,fp); add_one(i); } int all=0; for(i=0;iif(get_val(i)==1) //出現(xiàn)次數(shù)等于1，統(tǒng)計輸出 all++; } printf("%d\n",all); fclose(fp); return 0; }

運行結(jié)果如下：

249999980 real 0m35.566s user 0m31.694s sys 0m1.300s

可見，利用位運算、二進制數(shù)據(jù)文件，可以高效地解決這個問題。

linux常用命令

lsof

lsof(list open files)：列出當(dāng)前系統(tǒng)打開文件(普通文件、目錄、管道、socket、網(wǎng)絡(luò)文件)。因為打開文件的描述符列表提供了大量關(guān)于這個應(yīng)用程序本身的信息，因此通過lsof工具能夠查看這個列表對系統(tǒng)監(jiān)測以及排錯將是很有幫助的。

在linux環(huán)境下，任何事物都以文件的形式存在，通過文件不僅僅可以訪問常規(guī)數(shù)據(jù)，還可以訪問網(wǎng)絡(luò)連接和硬件。所以如傳輸控制協(xié)議 (TCP) 和用戶數(shù)據(jù)報協(xié)議 (UDP) 套接字等，系統(tǒng)在后臺都為該應(yīng)用程序分配了一個文件描述符，無論這個文件的本質(zhì)如何，該文件描述符為應(yīng)用程序與基礎(chǔ)操作系統(tǒng)之間的交互提供了通用接口。因為應(yīng)用程序打開文件的描述符列表提供了大量關(guān)于這個應(yīng)用程序本身的信息，因此通過lsof工具能夠查看這個列表對系統(tǒng)監(jiān)測以及排錯將是很有幫助的。

netstat

Netstat 命令用于顯示各種網(wǎng)絡(luò)相關(guān)信息，如網(wǎng)絡(luò)連接，路由表，接口狀態(tài) (Interface Statistics)，masquerade 連接，多播成員 (Multicast Memberships) 等等。

一些常用的netstat選項包括：

-a : 顯示所有socke信息 -r : 顯示路由信息 -i : 顯示網(wǎng)卡借口統(tǒng)計 -s : 顯示網(wǎng)絡(luò)協(xié)議統(tǒng)計

實用命令實例：

列出所有端口 (包括監(jiān)聽和未監(jiān)聽的)

列出所有端口 netstat -a

列出所有 tcp 端口 netstat -at

列出所有 tcp 端口 netstat -au

列出所有處于監(jiān)聽狀態(tài)的 Sockets

只顯示監(jiān)聽端口 netstat -l

只列出所有監(jiān)聽 tcp 端口 netstat -lt

只列出所有監(jiān)聽 udp 端口 netstat -lu

只列出所有監(jiān)聽 UNIX 端口 netstat -lx

顯示每個協(xié)議的統(tǒng)計信息

顯示所有端口的統(tǒng)計信息 netstat -s

顯示 TCP 或 UDP 端口的統(tǒng)計信息 netstat -st 或 -su

在 netstat 輸出中顯示 PID 和進程名稱 netstat -p

strace

strace可以跟蹤到一個進程產(chǎn)生的系統(tǒng)調(diào)用,包括參數(shù)，返回值，執(zhí)行消耗的時間。

在Linux中，進程不能直接訪問硬件設(shè)備，當(dāng)進程需要訪問硬件設(shè)備(比如讀取磁盤文件，接收網(wǎng)絡(luò)數(shù)據(jù)等等)時，必須由用戶態(tài)模式切換至內(nèi)核態(tài)模式，通過系統(tǒng)調(diào)用訪問硬件設(shè)備。strace可以跟蹤到進程執(zhí)行時的系統(tǒng)調(diào)用和所接收的信號。

ptrace系統(tǒng)調(diào)用

1，功能描述：

ptrace 提供了一種機制使得父進程可以觀察和控制子進程的執(zhí)行過程，同時提供查詢和修改子進程的鏡像和寄存器的能力。主要用于執(zhí)行斷點調(diào)試和系統(tǒng)調(diào)用跟蹤。

2，ptrace 的使用流程：

父進程 fork() 出子進程，子進程中執(zhí)行我們所想要 trace 的程序，子進程需要先調(diào)用一次 ptrace，以 PTRACE_TRACEME 為參數(shù)，來告訴內(nèi)核當(dāng)前進程已經(jīng)正在被 traced，最后使用 exec 等操作來初始化一個進程跟蹤。

當(dāng)子進程執(zhí)行 execve() 之后，子進程會進入暫停狀態(tài)，把控制權(quán)轉(zhuǎn)給它的父進程(SIG_CHLD信號), 而父進程在fork()之后，就調(diào)用 wait() 等子進程停下來，當(dāng) wait() 返回后，父進程就可以去查看子進程的寄存器或者對子進程做其它的事情了。

3，用法：

#include long ptrace(enum __ptrace_request request, pid_t pid, void *addr, void *data); 參數(shù)說明： request：請求執(zhí)行的行為， pid：目標(biāo)進程標(biāo)識。 addr：執(zhí)行 peek 和 poke 操作的目標(biāo)地址。 data：對于 poke 操作，存放數(shù)據(jù)的地方。對于 peek 操作，獲取數(shù)據(jù)的地方。 request 可能的選擇有： PTRACE_TRACEME //指示父進程跟蹤某個子進程的執(zhí)行。任何傳給子進程的信號將導(dǎo)致其停止執(zhí)行，同時父進程調(diào)用 wait() 時會得到通告。之后，子進程調(diào)用 exec() 時，核心會給它傳送 SIGTRAP 信號，在新程序開始執(zhí)行前，給予父進程控制的機會。pid, addr, 和 data參數(shù)被忽略。以上是唯一由子進程使用的請求，剩下部分將由父進程使用的請求。 PTRACE_PEEKTEXT, PTRACE_PEEKDATA //從子進程內(nèi)存空間 addr 指向的位置讀取一個字，并作為調(diào)用的結(jié)果返回。Linux 內(nèi)部對文本段和數(shù)據(jù)段不加區(qū)分，所以目前這兩個請求相等。data 參數(shù)被忽略。 PTRACE_PEEKUSR //從子進程的用戶區(qū) addr 指向的位置讀取一個字，并作為調(diào)用的結(jié)果返回。 PTRACE_POKETEXT, PTRACE_POKEDATA //將 data 指向的字拷貝到子進程內(nèi)存空間由 addr 指向的位置。 PTRACE_POKEUSR //將 data 指向的字拷貝到子進程用戶區(qū)由 addr 指向的位置。 PTRACE_GETREGS, PTRACE_GETFPREGS //將子進程通用和浮點寄存器的值拷貝到父進程內(nèi)由 data 指向的位置。addr 參數(shù)被忽略。 PTRACE_GETSIGINFO //獲取導(dǎo)致子進程停止執(zhí)行的信號信息，并將其存放在父進程內(nèi)由 data 指向的位置。addr 參數(shù)被忽略。 PTRACE_SETREGS, PTRACE_SETFPREGS //從父進程內(nèi)將 data 指向的數(shù)據(jù)拷貝到子進程的通用和浮點寄存器。addr 參數(shù)被忽略。 PTRACE_SETSIGINFO //將父進程內(nèi)由 data 指向的數(shù)據(jù)作為 siginfo_t 結(jié)構(gòu)體拷貝到子進程。addr 參數(shù)被忽略。 PTRACE_SETOPTIONS //將父進程內(nèi)由 data 指向的值設(shè)定為 ptrace 選項，data 作為位掩碼來解釋，由下面的標(biāo)志指定。 PTRACE_O_TRACESYSGOOD //當(dāng)轉(zhuǎn)發(fā) syscall 陷阱 (traps) 時，在信號編碼中設(shè)置位7，即第一個字節(jié)的最高位。例如：SIGTRAP | 0x80。這有利于追蹤者識別一般的陷阱和那些由 syscall 引起的陷阱。 PTRACE_O_TRACEFORK //通過 (SIGTRAP | PTRACE_EVENT_FORK << 8) 使子進程下次調(diào)用 fork() 時停止其執(zhí)行，并自動跟蹤開始執(zhí)行時就已設(shè)置 SIGSTOP 信號的新進程。新進程的 PID 可以通過 PTRACE_GETEVENTMSG 獲取。 PTRACE_O_TRACEVFORK //通過 (SIGTRAP | PTRACE_EVENT_VFORK << 8) 使子進程下次調(diào)用 vfork() 時停止其執(zhí)行，并自動跟蹤開始執(zhí)行時就已設(shè)置 SIGSTOP 信號的新進程。新進程的 PID 可以通過 PTRACE_GETEVENTMSG 獲取。 PTRACE_O_TRACECLONE //通過 (SIGTRAP | PTRACE_EVENT_CLONE << 8) 使子進程下次調(diào)用 clone() 時停止其執(zhí)行，并自動跟蹤開始執(zhí)行時就已設(shè)置 SIGSTOP 信號的新進程。新進程的 PID 可以通過 PTRACE_GETEVENTMSG 獲取。 PTRACE_O_TRACEEXEC //通過 (IGTRAP | PTRACE_EVENT_EXEC << 8) 使子進程下次調(diào)用 exec() 時停止其執(zhí)行。 PTRACE_O_TRACEVFORKDONE //通過 (SIGTRAP | PTRACE_EVENT_VFORK_DONE << 8) 使子進程下次調(diào)用 exec() 并完成時停止其執(zhí)行。 PTRACE_O_TRACEEXIT //通過 (SIGTRAP | PTRACE_EVENT_EXIT << 8) 使子進程退出時停止其執(zhí)行。子進程的退出狀態(tài)可通過 PTRACE_GETEVENTMSG 。 PTRACE_GETEVENTMSG //獲取剛發(fā)生的 ptrace 事件消息，并存放在父進程內(nèi)由 data 指向的位置。addr參數(shù)被忽略。 PTRACE_CONT //重啟動已停止的進程。如果 data 指向的數(shù)據(jù)并非0，同時也不是 SIGSTOP 信號，將會作為傳遞給子進程的信號來解釋。那樣，父進程可以控制是否將一個信號發(fā)送給子進程。addr 參數(shù)被忽略。 PTRACE_SYSCALL, PTRACE_SINGLESTEP //如同 PTRACE_CONT 一樣重啟子進程的執(zhí)行，但指定子進程在下個入口或從系統(tǒng)調(diào)用退出時，或者執(zhí)行單個指令后停止執(zhí)行，這可用于實現(xiàn)單步調(diào)試。addr 參數(shù)被忽略。 PTRACE_SYSEMU, PTRACE_SYSEMU_SINGLESTEP //用于用戶模式的程序仿真子進程的所有系統(tǒng)調(diào)用。 PTRACE_KILL //給子進程發(fā)送 SIGKILL 信號，從而終止其執(zhí)行。data，addr 參數(shù)被忽略。 PTRACE_ATTACH //銜接到pid指定的進程，從而使其成為當(dāng)前進程的追蹤目標(biāo)。 PTRACE_DETACH // PTRACE_ATTACH 的反向操作。

gdb的使用

1、首先獲得程序的PID ： ps -ef | grep xxxxx

2、進入調(diào)試程序： gdb attach PID

3、gcore命令生成CORE文件

4、進程信息可以用info proc顯示

5、寄存器信息可以用info reg顯示

GDB命令行最基本操作：

● 程序啟動方式：

A.冷啟動：

gdb program (program是執(zhí)行文件)

gdb –p pid

B.熱啟動：

(gdb) attach pid (調(diào)試運行中的程序)

C.傳入命令行參數(shù):

GDB啟動時，可以加上一些GDB的啟動參數(shù)：

-symbols/-s : 從指定文件中讀取符號表。

-se file : 從指定文件中讀取符號表信息，并把他用在可執(zhí)行文件中。

-core/-c : 調(diào)試時core dump的core文件。

-directory/-d : 加入一個源文件的搜索路徑。默認(rèn)搜索路徑是環(huán)境變量中PATH所定義的路徑。

● 設(shè)置觀察點：

○ w Expression，當(dāng)Expression是一個變量名時，這個變量變化時會停止執(zhí)行；你也可以使用條件來限定，比如w (z>28)，當(dāng)z大于28時，程序停止。注意觀察點一般使用在更大范圍上的變量，而不是本地變量，因為在局部變量上設(shè)置的觀察點在局部結(jié)束時(比如該變量所在的函數(shù)執(zhí)行結(jié)束時)就被取消了。

○ 當(dāng)然這并不包含main的情況，因為main函數(shù)執(zhí)行結(jié)束后程序就結(jié)束了。

● 查看棧幀：

○ 棧幀指的是在一個函數(shù)調(diào)用時，該函數(shù)調(diào)用的運行信息(包含本地變量、參數(shù)以及函數(shù)被調(diào)用的位置)存儲的地方。每當(dāng)一個函數(shù)被調(diào)用時，一個新的幀就被系統(tǒng)壓入一個由系統(tǒng)維護的幀，在這個棧的頂端是現(xiàn)在正在運行的函數(shù)信息，當(dāng)該函數(shù)調(diào)用結(jié)束時被彈出并析構(gòu)。

○ 在GDB中，frame 0為當(dāng)前幀，frame 1為當(dāng)前幀的父幀，frame 2為父幀的父幀，等等，用down命令則是反向的。這是一個很有用的信息，因為在早期的一些幀中的信息可能會給你一些提示。

○ backtrace(bt/ where)查看整個幀棧

○ 注意：在幀中來回并不影響程序的執(zhí)行。

一，多線程調(diào)試可能是問得最多的。其實，重要就是下面幾個命令：

● info thread 查看當(dāng)前進程的線程。

● thread ID 切換調(diào)試的線程為指定ID的線程。

● break file.c : 100 thread all 在file.c文件第100行處為所有經(jīng)過這里的線程設(shè)置斷點。

●?set scheduler-locking off|on|step，這個是問得最多的。在使用step或者continue命令調(diào)試當(dāng)前被調(diào)試線程的時候，其他線程也是同時執(zhí)行的，怎么只讓被調(diào)試程序執(zhí)行呢？通過這個命令就可以實現(xiàn)這個需求。

○ off 不鎖定任何線程，也就是所有線程都執(zhí)行，這是默認(rèn)值。

○ on 只有當(dāng)前被調(diào)試程序會執(zhí)行。

○ step 在單步的時候，除了next過一個函數(shù)的情況(熟悉情況的人可能知道，這其實是一個設(shè)置斷點然后continue的行為)以外，只有當(dāng)前線程會執(zhí)行。

二，調(diào)試宏：

這個問題超多。在GDB下，我們無法print宏定義，因為宏是預(yù)編譯的。但是我們還是有辦法來調(diào)試宏，這個需要GCC的配合。

●在GCC編譯程序的時候，加上-ggdb3參數(shù)，這樣，就可以調(diào)試宏了。

另外，你可以使用下述的GDB的宏調(diào)試命令來查看相關(guān)的宏。

● info macro – 可以查看這個宏在哪些文件里被引用了，以及宏定義是什么樣的。

● macro – 可以查看宏展開的樣子。

性能監(jiān)控和優(yōu)化命令

內(nèi)存：top，free，sar，pmap，vmstat，mpstat，iostat，

cpu：top，vmstat，mpstat，iostat，sar

I/O：vmstat，mpstat，iostat，sar

進程：ps，top，ipcs，ipcrm

系統(tǒng)運行負(fù)載：uptime，w

●ps：列出系統(tǒng)中正在運行的進程.ps告訴我們每個進程使用的內(nèi)存量以及所消耗的CPU時間。

●top：動態(tài)顯示進程信息，對進程實時監(jiān)控

●free：顯示系統(tǒng)使用和空閑的內(nèi)存情況

●pmap：可以顯示進程占用的內(nèi)存量。可以通過pmap找到占用內(nèi)存量最多的進程。

●sar：多方面對系統(tǒng)活動進行報告，包括磁盤IO，cpu效率，內(nèi)存使用情況，系統(tǒng)調(diào)用情況，文件讀寫情況。

●ipcs：提供進程間通信方式的信息，包括消息隊列、共享內(nèi)存、信號等

●ipcrm：刪除一個消息對象(消息隊列、信號集或者共享內(nèi)存標(biāo)識)

●vmstat：是Virtual Meomory Statistics(虛擬內(nèi)存統(tǒng)計)的縮寫，可對操作系統(tǒng)的虛擬內(nèi)存、進程、CPU活動進行監(jiān)控。它是對系統(tǒng)的整體情況進行統(tǒng)計，不足之處是無法對某個進程進行深入分析。

●iostat：既可以顯示CPU使用情況，也可以看到每個磁盤的IO情況.

iostat是I/O statistics(輸入/輸出統(tǒng)計)的縮寫，iostat工具將對系統(tǒng)的磁盤操作活動進行監(jiān)視。它的特點是匯報磁盤活動統(tǒng)計情況，同時也會匯報出CPU使用情況。同vmstat一樣，iostat也有一個弱點，就是它不能對某個進程進行深入分析，僅對系統(tǒng)的整體情況進行分析

●mpstat：mpstat用在多處理器的服務(wù)器上，用來顯示每一個CPU的狀態(tài)。另外，mpstat也會顯示所有處理器的平均狀況。

mpstat是MultiProcessor Statistics的縮寫，是實時系統(tǒng)監(jiān)控工具。其報告與CPU的一些統(tǒng)計信息，這些信息存放在/proc/stat文件中。在多CPU系統(tǒng)里，其不但能查看所有CPU的平均狀況信息，而且能夠查看特定CPU的信息。

●uptime：顯示系統(tǒng)已經(jīng)運行了多長時間，它依次顯示下列信息：當(dāng)前時間、系統(tǒng)已經(jīng)運行了多長時間、目前有多少登陸用戶、系統(tǒng)在過去的1分鐘、5分鐘和15分鐘內(nèi)的平均負(fù)載。

●w：查詢登錄當(dāng)前系統(tǒng)的用戶信息，以及這些用戶目前正在做什么操作，另外load average后面的三個數(shù)字則顯示了系統(tǒng)最近1分鐘、5分鐘、15分鐘的系統(tǒng)平均負(fù)載情況

總結(jié)

以上是生活随笔為你收集整理的poll和死锁_计算机基础知识的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

上一篇：计算机的软件系统可分为什么(软件系统可分
下一篇：电影《阿凡达：水之道》延长上映至 2 月