資訊安全系統設計基礎第十三周學習總結

第十一章 網絡程式設計

1.用戶端-伺服器程式設計模型

2.網絡

1. 對于主機，網絡是一種I/O裝置，作為資料源和資料接收方。
2. 實體上而言，網絡是一個按照地理遠近組成的層次系統。最底層是LAN。

3. 一個以太網段，包括電纜和集線器；每根電纜都有相同的最大位帶寬；集線器不加分辯地将一個端口上收到的每個位複制到其他所有的端口上。是以，每台主機都能看到每個位。

   使用電纜和網橋，多個以太網段可以連接配接成較大的區域網路，稱為橋接以太網。這些電纜的帶寬可以是不同的。

   

4. 網際網路絡如何實作跨過不相容發送資料？

   協定。

   具備兩種基本能力：命名機制、傳送機制。

3.全球IP網際網路

• TCP/IP協定（協定族）。
• 網際網路的用戶端和伺服器混合使用套接字接口函數和Unix I/O函數進行通信。

  

3.1 IP位址

1. 一個IP位址就是一個32位無符号整數。
2. IP位址通常以點分十進制表示法來表示。 如，128.2.194.242就是位址0x8002c2f2的點分十進制表示

3.2 網際網路域名

• 網際網路應用程式通過調用gethostbyname函數和gethostbyaddr函數，從DNS資料庫中檢索任意的主機條目。

  gethostbyname函數：傳回和域名name相關的主機條目。

  gethostbyaddr函數：傳回和IP位址相關聯的主機條目。

3.3 網際網路連結

1. 套接字是連接配接的端點。
2. 每個套接字都有相應的套接字位址，由一個網際網路位址和一個16位的整數端口組成的，用“位址：端口”來表示。
3. 一個連接配接是由它兩端的套接字位址惟一确定的。這對套接字位址叫做套接字對。

4.套接字接口

• 套接字接口是一組用來結合unit I/O函數建立網絡應用的函數。

4.1套接字位址結構

• 從unit核心的角度來看，套接字就是通信的端點；從unix程式的角度來看，套接字就是一個有相應描述符的打開檔案。

4.2 函數

• sockte函數 建立一個套接字描述符。
• connect函數 建立和伺服器的連接配接。
• open_clientfd函數 将socket和connect函數包裝而成。用戶端可以用它來和伺服器建立連接配接。
• bind函數
• listen函數
• accept函數 均被伺服器用于和用戶端建立連接配接。
• open_listenfd函數 socket、bind和listen函數結合。用于伺服器建立一個監聽描述符。

5.Web伺服器

5.1Web基礎

1.用戶端和伺服器之間一個互動用的是基于文本的應用級協定——HTTP

2.Web服務和正常檔案檢索服務差別

Web内容可以用一個叫做HTML的語言來編寫。           

5.2Web内容

• 以兩種不同方式向用戶端提供内容

  服務靜态内容

  服務動态内容

5.3HTTP事務

響應

• HTTP請求（方法：GET POST OPTIONS HEAD PUT DELETE TRACE）
• HTTP響應

5.4服務動态内容

用戶端如何将程式參數傳遞給伺服器

伺服器如何将參數傳遞給子程序

伺服器如何将其他資訊傳遞給子程序

第12章 并發程式設計

到目前為止，我們主要将并發看做是一種作業系統核心用來運作多個應用程式的機制。但是，并發不僅僅局限于核心。它也可以在應用程式中扮演重要角色。例如，我們已經看到Unix信号處理程式如何允許應用響應異步事件，例如使用者鍵入。或者程式通路虛拟存儲器的個未定義的區域．應用級并發在其他情況下也是很有用的，例如：

1.通路慢速I/O裝置：當一個應用正在等待來自慢速I/O裝置（例如磁盤）的資料到達時，内I/O請求和其他有用的工作來使用并發。
2.與人互動。和計算機互動的人要求計算機有同時執行多個任務的能力，例如，他們在列印個文檔時，可能想要調整一個視窗的大小。現代視窗系統利用并發來提供這種能力，每次使用者請求某種操作（比如通過單擊滑鼠時，一個獨立的并發邏輯流被建立來執行這個操作。
3.���過推遲工作以降低延遲。有時，應用程式能夠通過推遲其他操作和并發地執行它們利用并發來降低某些操作的延遲。比如，一個動态存儲配置設定器可以通過推遲合并．把它放到個運作在較低優先級上的并發“合并”流中在有空閑的CPU周期時充分利用這些空閑周期進而降低單個free操作的延遲
4.服務多個網絡用戶端。我們在第U章中學習的疊代網絡伺服器是不現實的，因為它們次隻能為一個用戶端提供服務。是以一個慢速的用戶端可能會導緻伺服器拒絕為所有其他用戶端服務。對于一個真正的伺服器來說，可能期望它每秒為成百上千的用戶端提供服務，由于一個慢速用戶端導緻拒絕為其他用戶端服務，這是不能接受的一個更好的方法是建立一個并發伺服器，它為每個用戶端建立一個單獨的邏輯流。這就允許伺服器同時為多個用戶端服務并且這也避免了慢速用戶端獨占伺服器。
5.在多核機器上進行并行計算 多核處理器，多核處理器中包含多個CPU。被劃分成并發流的應用程式通常在多核機器上比在單處理器機器上運作理器中包含多個這些流會并行執行，而不是交錯執行
6.現代作業系統提供了三基本的構造并發程式的方法：程序、I/O多路複用、線程。           

12.1 基于程序的并發程式設計

1. 在接受連接配接請求之後，伺服器派生一個子程序，這個子程序獲得伺服器描述符表的完整拷貝。子程序關閉它的拷貝中的監聽描述符3，而父程序關閉它的已連接配接描述符4的拷貝，因為不再需要這些描述符了。這就得到了圖中的狀态，其中子程序正忙于為用戶端提供服務。因為父子程序中的已連接配接描述符都指向同一個檔案表表項，是以父程序關閉它的已連接配接描述符的拷貝是至關重要的。否則，将永遠不會釋放已連接配接描述符4的檔案表條目，而且由此引起的存儲器洩漏将最終消耗盡可用的存儲器，使系統崩潰。
2. 現在假設在父程序為用戶端1建立了子程序之後，它接受一個新的用戶端2的連接配接請求，并傳回一個新的已連接配接描述符（比如描述符5）如圖所示。然後，父程序又派生另一個子程序，這個子程序用已連接配接描述符5為它的用戶端提供服務，如圖所示。此時，父程序正在等待下一個連接配接請求，而兩個子程序正在形地為它們各自的用戶端提供服務。

12.1.1 基于程序的并發伺服器

• 一個基于程序的并發的echo伺服器的代碼，重要說明：

  首先，通常伺服器會運作很長時間，是以我們必須包括一個SIGCHLD處理程式，來回收僵死子程序資源。

  其次，父子程序必須關閉他們的connfd拷貝。

  最後，因為套接字的檔案表表項的引用計數，直到父子程序的connfd都關閉了，到用戶端的連接配接才會終止。

12.1.2 關于程序的優劣

• 關于程序的優劣，對于在父、子程序間共享狀态資訊，程序有一個非常清晰的模型：共享檔案表，但是不共享使用者位址空間。程序有獨立的位址控件愛你既是優點又是缺點。由于獨立的位址空間，是以程序不會覆寫另一個程序的虛拟存儲器。但是另一方面程序間通信就比較麻煩，至少開銷很高。

12.2 基于i/o多路複用的并發程式設計

1. 比如一個伺服器，它有兩個I/O事件：1）網絡用戶端發起連接配接請求，2）使用者在鍵盤上鍵入指令行。我們先等待那個事件呢？沒有那個選擇是理想的。如果accept中等待連接配接，那麼無法相應輸入指令。如果在read中等待一個輸入指令，我們就不能響應任何連接配接請求（這個前提是一個程序）。
2. 針對這種困境的一個解決辦法就是I/O多路複用技術。基本思想是：使用select函數，要求核心挂起程序，隻有在一個或者多個I/O事件發生後，才将控制返給應用程式。如圖所示：橫向的方格可以看作是一個n位的描述符向量。現在，我們定義第0位描述是“标準輸入”，第3位描述符是“監聽描述符”。

12.2.1 基于i/o多路複用的并發事件驅動伺服器

• I/O多路複用可以用做并發事件驅動程式的基礎，在事件驅動程式中，流是因為某種事件而前進的，一般概念是将邏輯流模型化為狀态機，不嚴格地說，一個狀态機就是一組狀态，輸入事件和轉移，其中轉移就是将狀态和輸入事件映射到狀态，每個轉移都将一個（輸入狀态，輸入事件）對映射到一個輸出狀态，自循環是同一輸入和輸出狀态之間的轉移，通常把狀态機畫成有向圖，其中節點表示狀态，有向弧表示轉移，而弧上的标号表示輸人事件，一個狀态機從某種初始狀态開始執行，每個輸入事件都會引發一個從目前狀态到下一狀态的轉移，對于每個新的用戶端k，基于I/O多路複用的并發伺服器會建立一個新的狀态機S，并将它和已連接配接描述符d聯系起來。

12.2.2 i/o多路複用技術的優劣

1. 事件驅動設計的一個優點是，它比基于程序的設計給了程式員更多的對程式行為的控制。例如我們可以設想編寫一個事件驅動的并發伺服器，為某些客戶提供他們需要的服務，而這對于新程序的并發伺服器來說，是很困難的
2. 另一個優點是，一個基于I/O多路複用的事件驅動器是運作在單一程序上下文中的，是以每個邏輯流都能通路該程序的全部位址空間。這使得在流之間共享資料變得很容易，一個與作為單個程序運作相關的優點是，你可以利用熟悉的調試工具，例如GDB，來調試你的并發伺服器，就像對順序程式那樣。最後，事件驅動設計常常比基于進利的設計要高效得多，因為它們不需要程序上下文切換來排程新的流。
3. 事件驅動設計的一個明顯的缺點就是編碼複雜，我們的事件驅動的并發伺服器需要的代度是指每個邏輯流每個時間片執行的指令數量。基于事件的設計的另一個重大缺點是它們不能充分利利用多核處理器。

12.3 基于線程的并發程式設計

• 每個線程都有自己的線程上下文，包括一個線程ID、棧、棧指針、程式計數器、通用目的寄存器和條件碼。所有的運作在一個程序裡的線程共享該程序的整個虛拟位址空間。由于線程運作在單一程序中，是以共享這個程序虛拟位址空間的整個内容，包括它的代碼、資料、堆、共享庫和打開的檔案。

12.3.1 線程執行模型

• 線程執行的模型。線程和程序的執行模型有些相似。每個程序的聲明周期都是一個線程，我們稱之為主線程。但是大家要有意識：線程是對等的，主線程跟其他線程的差別就是它先執行。

12.3.2 posix線程

• POSIX線程是在C程式中處理線程的一個标準接口。它最早出現在1995年，而且在大多數Unix系統上都可用。Pthreads定義了大約60個函數，允許程式建立、殺死和回收線程，與對等線程安全地共享資料，還可以通知對等線程系統狀态的變化。

12.3.3 建立線程

• 線程通過調用pthread_create函數來建立其他程序。

  

  

12.3.4 終止線程

• 一個線程是以下列方式之一來終止的。
• 當頂層的線程例程傳回時，線程會隐式地終止
• 通過調用pthread_exit函數，線程會顯它會等待所有其他對等線程終止，然後再終止式地終止。
• 某個對等線程調用Unix的e×it函數，該函數終止程序以及所有與該程序相關的線程

12.3.5 回收已終止線程的資源

12.3.6 分離線程

12.3.7 初始化線程

12.3.8 一個基于線程的并發伺服器

12.4 多線程程式中的共享變量

• 全局變量和static 變量 是存儲在資料段，是以，多線程共享之！
• 由于線程的棧是獨立的，所有線程中的自動變量是獨立的。即使多個線程運作同一段代碼總的自動變量，那麼他們的值也是根據線程的不同而不同。
• 比如C++中，類屬性不是在使用者棧中的。是以線程共享之！

12.4.1 線程存儲器模型

1. 一組并發線程運作在一個程序的上下文中。每個線程都有它自己獨立的線程上下文，包括線程ID、棧、棧指針、程式計數器、條件碼和通用目的寄存器值。每個線程和其他線程一起共享程序上下文的剩餘部分。這包括整個使用者虛拟位址空間，它是由隻讀文本代碼、讀／寫資料、堆以及所有的共享庫代碼和資料區域組成的。線程也共享同樣的打開檔案的集合。
2. 從實際操作的角度來說，讓一個線程去讀或寫另一個線程的寄存器值是不可能的。另一方面，任何線程都可以通路共享虛拟存儲器的任意位置。如果某個線程修改了一個存儲器位置，那麼其他每個線程最終都能在它讀這個位置時發現這個變化。是以，寄存器是從不共享的，而虛拟存儲器總是共享的。
3. 各自獨立的線程棧的存儲器模型不是那麼整齊清楚的。這些棧被儲存在虛拟位址空間的棧區域中，并且通常是被相應的線程獨立地通路的。我們說通常而不是總是，是因為不同的線程棧是不對其他線程設防的是以，如果個線程以某種方式得到個指向其他線程棧的指慧：那麼它就可以讀寫這個棧的任何部分。

12.4.2 将變量映射到存儲器

線程化的C程式中變量根據它們的存儲類型被映射到虛拟存儲器：

1. 全局變量。全局變量是定義在函數之外的變量，在運作時，虛拟存儲器的讀／寫區域域隻包含每個全局變量的一個執行個體，任何線程都可以引用。例如第5行聲明的全局變量ptr在虛拟存儲器的讀／寫區域中有個運作時執行個體，我們隻用變量名（在這裡就是ptr）來表示這個執行個體。
2. 本地自動變量，本地自動變量就是定義在函數内部但是沒有static屬性的變量，在運作時，每個線程的棧都包含它自己的所有本地自動變量的執行個體。即使當多個線程執行同一個線程例程時也是如此。例如，有個本地變量tid的執行個體，它儲存在主線程的棧中。我們用tid.m來表示這個執行個體
3. 本地靜态變量

12.4.3 共享變量

我們說一個變量V是共享的，當且僅當它的一個執行個體被一個以上的線程引用。例如，示例程式中的變量cnt就是共享的，因為它隻有一個運作時執行個體，并且這個執行個體被兩個對等線程引用在另一方面，myid不是共享的，因為它的兩個執行個體中每一個都隻被一個線程引用。然而，認識到像msgs這樣的本地自動變量也能被共享是很重要的。

12.5 用信号量同步線程

• 信号量通常稱之為PV操作，雖然它的思想是将臨界代碼保護起來，達到互斥效果。這裡面作業系統使用到了線程挂起。
• 将線程i的循環代碼分解成五個部分：

  

12.5.1 進度圖

• 程序圖将n個并發程序的執行模型化為一條n維笛卡爾空間中的軌迹線。

12.5.2 信号量

• 信号量s是具有非負整數值的全局變量，隻能由兩種特殊的操作來處理，這兩種操作稱為P和V
• P(s):如果s是非零的，那麼P将s減1并且立即傳回。如果s為零，那麼就挂起這個線程，直到s變為非零，而一個y操作會重新開機這個線程。在重新開機之後，P操作将s減1并将控制傳回給調用者
• V(s):V操作将s加1。如果有任何線程阻塞在P操作等待s變成非零，那麼V操作會重新開機這些線程中的一個，然後該線程将s減1，完成它的P操作，P中的測試和減1操作是不可分割的，也就是說，一旦預測信号量s變為非零，就會将s減1,不能有中斷。V中的加1操作也是不可分割的，也就是加載、加和存儲信号量的過程中沒有中斷。注意，V的定義中沒有定義等待線程被重新啟動的順序。唯—的要求是V必須隻能重新開機一個正在等待的程序。

12.5.3 使用信号量來實作互斥

• 信号量提供了一種很友善的方法來確定對共享變量的互斥通路。基本思想是将每個共享變量（或者一組相關的共享變量）與一個信号量聯系起來 。以這種方式來保護共享變量的信号量叫做二進制信号量，因為它的值總是0或者1。以提供互斥為目的的二進制信号量常常也稱為互斥鎖。在一個互斥鎖上執行P操作稱為對互斥鎖加鎖。類似地，執行V操作稱為對互斥鎖解鎖。對一個互斥鎖加了鎖但是還沒有解鎖的線程稱為占用這個互斥鎖。一個被用作一組可用資源的計數器的信号量稱為計數信号量。關鍵思想是這種P和V操作的結合建立了一組狀态，叫做禁止區。因為信号量的不變性，沒有實際可行的軌迹線能夠包含禁止區中的狀态。而且，因為禁止區完全包括了不安全區，是以沒有實際可行的軌迹線能夠接觸不安全區的任何部分。是以，每條實際可行的軌迹線都是安全的，而且不管運作時指令順序是怎樣的，程式都會正确地增加計數器的值。

12.5.4 利用信号量來排程共享資源

1. 生産者-消費者問題。

1. 讀者-寫者問題。

12.5.5 綜合:基于預線程化的并發伺服器

• 在如圖所示的并發伺服器中，我們為每一個新用戶端建立了一個新線程這種方法的缺點是我們為每一個新用戶端建立一個新線程，導緻不小的代價。一個基于預線程化的伺服器試圖通過使用如圖所示的生産者-消費者模型來降低這種開銷。伺服器是由一個主線程和一組工作者線程構成的。主線程不斷地接受來自用戶端的連接配接請求，并将得到的連接配接描述符放在一個不限緩沖區中。每一個工作者線程反複地從共享緩沖區中取出描述符，為用戶端服務，然後等待下一個描述符。

  

12.6 使用線程提高并行性

• 到目前為止，在對并發的研究中，我們都假設并發線程是在單處許多現代機器具有多核處理器。并發程式通常在這樣的機器上運理器系統上執行的。然而，在多個核上并行地排程這些并發線程，而不是在單個核順序地排程，在像繁忙的Web伺服器、資料庫伺服器和大型科學計算代碼這樣的應用中利用這種并行性是至關重要的。

12.7 其他并發問題

12.7.1 線程安全

1. 我們程式設計過程中，盡可能編寫線程安全函數，即一個函數當且僅當被多個并發線程反複調用時，它會一直産生正确的結果。如果做不到這個條件我們稱之為線程不安全函數。下面介紹四類線程不安全函數：

   ●不保護共享變量的函數。解決辦法是PV操作。

   ●保持跨越多個調用的狀态函數。比如使用靜态變量的函數。解決方法是不要使用靜态變量或者使用可讀靜态變量。

   ●傳回指向靜态變量的指針的函數。解決方法是lock-and-copy(枷鎖-拷貝)

   ●調用線程不安全函數的函數

   死鎖。

2. 由于PV操作不當，可能造成死鎖現象。這在程式中也會出現。

12.7.2 可重入性

1. 有一類重要的線程安全函數，叫做可重入函數。其特點在于他們具有這樣一種屬性：當它們被多個線程調用時，不會引用任何共享資料。盡管線程安全和可重入有時會（正确地）被用做同義詞，但是它們之間還是有清晰的技術差别的，值得留意。圖展示了可重入函數、線程安全函數和線程不安全函數之間的集合關系。所有函數的集合被劃分成不相交的線程安全和線程不安全函數集合。可重入函數集合是線程安全函數的一個真子集。

1. 可重入函數通常要比不可重入的線程安全的函數高效一些，因為它們不需要同步操作。更進一步來說，将第2類線程不安全函數轉化為線程安全函數的唯一方法就是重寫它，使之變為可重入的。

12.7.3 線上程化的程式中使用已存在的庫函數

12.7.4 競争

• 當一個程式的正确性依賴于一個線程要在另一個線程到達y點之前到達它的控制流中的X點時，就會發生競争。通常發生競争是因為程式員假定線程将按照某種特殊的軌迹正确工作忘記了另一條準則規定：線程化的程式必須對任何可行的軌迹線都正确工作。

12.7.5 死鎖

1. 信号量引入了一種潛在的令人厭惡的運作時錯誤，叫做死鎖。它指的是一組線程被阻塞了，等待一個永遠也不會為真的條件。進度圖對于了解死鎖是一個無價的工具。
2. 關于死鎖的重要知識：
3. 程式員使用P和V操作漏序不當，以至于兩個信号量的禁止區域重疊。如果某個執行軌迹線碰巧到達了死鎖狀态d那麼就不可能有進一步的進展了，因為重疊的禁止區域阻塞了每個合法方向上的進展。換句話說，程式死鎖是因為每個線程在等待一個根本不可能發生的V操作
4. 重疊的禁止區域引起了一組稱為死鎖區域的狀态。軌迹線可以進入死鎖區域，但是它們不可能離開。
5. 死鎖是個相當困難的問題，因為它不總是可預測的。一些幸運的執行軌迹線将繞開死鎖區域，而其他的将會陷入這個區域。

• 第十二章 并發程式設計簡單介紹了并發程式設計的内容，主要包括：

  1. 程序級别的并發，各子程序擁有不同的虛拟位址空間，需要IPC(InterProcess Communication)機制共享資料，切換開銷大。
  2. I/O複用，事件驅動，單程序運作，共享虛拟位址空間，并發效果不理想。
  3. 線程，介于上述兩種中間，各子線程共享程序的虛拟位址空間，切換開銷較小。
  4. 另外介紹了并發程式設計中通路共享變量的信号量機制，并給出了4類容易引起線程不安全的函數。

參考資料

1. 教材：第十一、十二章，詳細學習指導：http://group.cnblogs.com/topic/73069.html
2. 課程資料：https://www.shiyanlou.com/courses/413 實驗十，課程邀請碼：W7FQKW4Y
3. 教材中代碼運作、思考一下，讀代碼的學習方法：http://www.cnblogs.com/rocedu/p/4837092.html。