2017-2018-1 20155222 《資訊安全系統設計基礎》第十四周學習總結

2017-2018-1 20155222 第十四周 深入了解計算機系統第十二章--并發程式設計

知識點總結

• 并發的定義

  如果邏輯控制流在時間上重疊，那麼他們就是并發的。

• 應用級并發的作用

  • 通路慢速I/O裝置。

    當一個應用正在等待來自慢速I/U裝置(例如磁盤)的資料到達時，核心會運作其他程序，使CPU保持繁忙。每個應用都可以按照類似的方式，通過交替執行I/O請求和其他有用的工作來利用并發。

  • 與人互動。

    和計算機互動的人要求計算機有同時執行多個任務的能力。例如，他們在列印一個文檔時，可能想要調整一個視窗的大小。現代視窗系統利用并發來提供這種能力。每次使用者請求某種操作(比如通過單擊滑鼠)時，一個獨立的并發邏輯流被建立來執行這個操作。

  • 通過推遲工作以降低延遲。

    有時，應用程式能夠通過推遲其他操作和并發地執行它們，利用并發來降低某些操作的延遲。比如，一個動态記憶體配置設定器可以通過推遲合并，把它放到一個運作在較低優先級上的并發“合并”流中，在有空閑的CPU周期時充分利用這些空閑周期，進而降低單個free操作的延遲。

  • 服務多個網絡用戶端。

    我們在第11章中學習的疊代網絡伺服器是不現實的，因為它們一次隻能為一個用戶端提供服務。是以，一個慢速的用戶端可能會導緻伺服器拒絕為所有其他用戶端服務。對于一個真正的伺服器來說，可能期望它每秒為成百上千的用戶端提供服務，由于一個慢速用戶端導緻拒絕為其他用戶端服務，這是不能接受的。一個更好的方法是建立一個并發伺服器，它為每個用戶端建立一個單獨的邏輯流。這就允許伺服器同時為多個用戶端服務，并且也避免了慢速用戶端獨占伺服器。

  • 在多核機器上進行并行計算。

    許多現代系統都配備多核處理器，多核處理器中包含有多個CPU。被劃分成并發流的應用程式通常在多核機器上比在單處理器機器上運作得快，因為這些流會并行執行，而不是交錯執行。使用應用級并發的應用程式稱為并發程式(concurrent program)。現代作業系統提供了三種基本的構造并發程式的方法:

  • 程序。

    用這種方法，每個邏輯控制流都是一個程序，由核心來排程和維護。因為程序有獨立的虛拟位址空間，想要和其他流通信，控制流必須使用某種顯式的程序間通信(interprocess communication, IPC)機制。

  • I/O多路複用。

    在這種形式的并發程式設計中，應用程式在一個程序的上下文中顯式地排程它們自己的邏輯流。邏輯流被模型化為狀态機，資料到達檔案描述符後，主程式顯式地從一個狀态轉換到另一個狀态。因為程式是一個單獨的程序，是以所有的流都共享同一個位址空間。

  • 線程。

    線程是運作在一個單一程序上下文中的邏輯流，由核心進行排程。你可以把線程看成是其他兩種方式的混合體，像程序流一樣由核心進行排程，而像I/O多路複用流一樣共享同一個虛拟位址空間。本章研究這三種不同的并發程式設計技術。為了使我們的讨論比較具體，我們始終以同一個應用為例—11. 4. 9節中的疊代ech。伺服器的并發版本。

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

  構造并發程式最簡單的方法就是用程序，使用那些大家都很熟悉的函數，像fork,exec和waitpid。例如，一個構造并發伺服器的自然方法就是，在父程序中接受用戶端連接配接請求，然後建立一個新的子程序來為每個新用戶端提供服務。

  

  

• 基于I/O多路複用的并發程式設計

  假設要求你編寫一個echo伺服器，它也能對使用者從标準輸人鍵人的互動指令做出響應。在這種情況下，伺服器必須響應兩個互相獨立的I/O事件:1>網絡用戶端發起連接配接請求，2)使用者在鍵盤上鍵人指令行。
             

  • 使用以前學過的阻塞socket()

    大緻代碼如下

    while(1)
    {
    	accept();  //調用accept()函數阻塞的等待請求連接配接事件
    	read();     //調用read函數阻塞的等待輸入事件
    }
               

    或者

    while(1)
    {
    	read();     //調用read函數阻塞的等待輸入事件
    	accept();  //調用accept()函數阻塞的等待請求連接配接事件
    }
               

    這麼做會産生一個問題，在使用第一段代碼的情況下，如果有一個輸入事件先到來，那麼伺服器将不能響應處理，因為它被阻塞在accept()函數了。而如果使用第二段代碼的情況下，如果一個用戶端請求連接配接，那麼伺服器将無法處理，因為它被阻塞在read()函數。

  • 使用I/O多路複用技術

    大緻代碼如下：

    /*将所有可能被改變的描述符放到一個集合中，你隻能對描述符進行三種操作：1）配置設定他們 ；2）将一個此種類型的變量複制給另一個變量；3）用FD_ZERO、FD_SET、FD_CLR、FD_ISSET宏指令來修改他們*/
    fd_set read_set ;    //定義一個“讀集合”
    fd_set ready_set;   //定義讀集合的一個子集“就緒集合”
    FD_ZERO(&read_set); //将讀集合清空
    FD_SET(STDIN_FILENO,&read_set); //将标準輸入描述符加入“讀集合”
    FD_SET(listenfd,&read_set); //将監聽描述符加入“讀集合”
    while(1)
    {
    	ready_set=read_set;
    	
    	/*先将read_set的内容複制到ready_set中，因為接下來的Select函數會修改其中一個參數——描述符集合的指針，轉而指向他的一個子集稱為“就緒集合”，這個集合是由“讀集合”中準備好可以讀的描述符組成的，是以不能直接把“讀集合”的指針作為參數放到函數Select中，否則将失去這個集合，并且我們還要在每次循環的開始将它重置給ready_set;*/
    	
    	Select(listenfd+1,&ready_set,NULL,NULL,NULL);
    	
    	/*Select函數的作用是訓示核心阻塞等待一段時間，在這段時間裡可能會有某些事件的到來使得讀集合中相應的描述符變為就緒狀态。
    	第一個參數為待測試的描述符的個數，即最大的描述符加一，因為描述符是從0開始依次計數的。核心将對“讀集合”中的描述符0、1、2……maxfd-1依次測試其是否可讀，測試的方法是嘗試讀取一個位元組，能讀取表示可讀，也即有相應時間到來，若讀取一個位元組的請求阻塞，說明不可讀，即沒有相應事件到來。
    	第二個參數為待測試的讀集合的指針，函數傳回後指針指向一個就續集合，由可讀的描述符組成。
    	第三個參數為待測試的寫集合的指針，這裡為空，不做詳細說明
    	第四個參數為待測試的異常集合的指針，這裡為空，不做詳細說明（其實是不會，嘿嘿）
    	第五個參數為阻塞等待的時間，類型為一個時間結構體
    	struct timeval{
               long tv_sec;   //秒
               long tv_usec;  //微秒
    	};
    		1）若為NULL，Select會永遠阻塞等待，直到有一個描述符就緒。
    		2）等待不超過timeval中的時間，有一個描述符準備好時立即傳回。
    		3）timeval中時間為0，則不等待，檢查所有描述符後立即傳回，稱為輪詢。
    		
    	傳回值：就緒描述符的數目，逾時傳回0，出錯傳回-1
    */
    
    if(FD_ISSET(STDIN_FILENO,&ready_set)) //用FD_ISSET函數判斷描述符是否可讀
    	commed();  //處理事件
    if(FD_ISSET(listenfd,&ready_set)){
    	connfd=accept(……)；
               

  }

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

  線程(thread)就是運作在程序上下文中的邏輯流。在本書裡迄今為止，程式都是由每個程序中一個線程組成的。但是現代系統也允許我們編寫一個程序裡同時運作多個線程的程式。線程由核心自動排程。每個線程都有它自己的線程上下文(thread context)，包括一個唯一的整數線程ID(Thread ID, TID)、棧、棧指針、程式計數器、通用目的寄存器和條件碼。所有的運作在一個程序裡的線程共享該程序的整個虛拟位址空間。

  基于線程的邏輯流結合了基于程序和基于I/O多路複用的流的特性。同程序一樣，線程由核心自動排程，并且核心通過一個整數ID來識别線程。同基于I/O多路複用的流一樣，多個線程運作在單一程序的上下文中，是以共享這個程序虛拟位址空間的所有内容，包括它的代碼、資料、堆、共享庫和打開的檔案。

• 線程的分離與結合

  在任何一個時間點上，線程是可結合的（joinable），或者是分離的（detached）。一個可結合的線程能夠被其他線程收回其資源和殺死；在被其他線程回收之前，它的存儲器資源（如棧）是不釋放的。相反，一個分離的線程是不能被其他線程回收或殺死的，它的存儲器資源在它終止時由系統自動釋放。

  線程的分離狀态決定一個線程以什麼樣的方式來終止自己。在預設情況下線程是非分離狀态的，這種情況下，原有的線程等待建立的線程結束。隻有當pthread_join（）函數傳回時，建立的線程才算終止，才能釋放自己占用的系統資源。而分離線程不是這樣子的，它沒有被其他的線程所等待，自己運作結束了，線程也就終止了，馬上釋放系統資源。程式員應該根據自己的需要，選擇适當的分離狀态。是以如果我們在建立線程時就知道不需要了解線程的終止狀态，則可以pthread_attr_t結構中的detachstate線程屬性，讓線程以分離狀态啟動。

  設定線程分離狀态的函數為pthread_attr_setdetachstate（pthread_attr_t *attr, int detachstate）。第二個參數可選PTHREAD_CREATE_DETACHED（分離線程）和 PTHREAD _CREATE_JOINABLE（非分離線程）。這裡要注意的一點是，如果設定一個線程為分離線程，而這個線程運作又非常快，它很可能在pthread_create函數傳回之前就終止了，它終止以後就可能将線程号和系統資源移交給其他的線程使用，這樣調用pthread_create的線程就得到了錯誤的線程号。要避免這種情況可以采取一定的同步措施，最簡單的方法之一是可以在被建立的線程裡調用pthread_cond_timewait函數，讓這個線程等待一會兒，留出足夠的時間讓函數pthread_create傳回。設定一段等待時間，是在多線程程式設計裡常用的方法。但是注意不要使用諸如wait（）之類的函數，它們是使整個程序睡眠，并不能解決線程同步的問題。

  如果不關心一個線程的結束狀态，那麼也可以将一個線程設定為 detached 狀态，進而讓作業系統在該線程結束時來回收它所占的資源。将一個線程設定為detached 狀态可以通過兩種方式來實作。一種是調用 pthread_detach() 函數，可以将線程 th 設定為 detached 狀态。另一種方法是在建立線程時就将它設定為 detached 狀态，首先初始化一個線程屬性變量，然後将其設定為 detached 狀态，最後将它作為參數傳入線程建立函數 pthread_create()，這樣所建立出來的線程就直接處于 detached 狀态。

  建立 detach 線程：

  pthread_t tid;
  pthread_attr_t attr;
  pthread_attr_init(&attr);
  pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
  pthread_create(&tid, &attr, THREAD_FUNCTION, arg);
             

  總之為了在使用 pthread 時避免線程的資源線上程結束時不能得到正确釋放，進而避免産生潛在的記憶體洩漏問題，在對待線程結束時，要確定該線程處于 detached 狀态，否着就需要調用 pthread_join() 函數來對其進行資源回收。

• 線程同步與互斥：互斥鎖

  互斥鎖是一種簡單的加鎖的方法來控制對共享資源的通路，互斥鎖隻有兩種狀态,即上鎖( lock )和解鎖( unlock )。

  互斥鎖的操作流程如下：

  1）在通路共享資源後臨界區域前，對互斥鎖進行加鎖。

  2）在通路完成後釋放互斥鎖導上的鎖。

  3）對互斥鎖進行加鎖後，任何其他試圖再次對互斥鎖加鎖的線程将會被阻塞，直到鎖被釋放。

  互斥鎖的資料類型是： pthread_mutex_t。

  互斥鎖基本操作

  

  以下函數需要的頭檔案：

  #include <pthread.h>
             

  • 1）初始化互斥鎖

    int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);
               

    功能：初始化一個互斥鎖。

    參數：

    mutex：互斥鎖位址。類型是 pthread_mutex_t 。

    attr：設定互斥量的屬性，通常可采用預設屬性，即可将 attr 設為 NULL。

    可以使用宏 PTHREAD_MUTEX_INITIALIZER 靜态初始化互斥鎖，比如：

    pthread_mutex_t  mutex = PTHREAD_MUTEX_INITIALIZER;
               

    這種方法等價于使用 NULL 指定的 attr 參數調用 pthread_mutex_init() 來完成動态初始化，不同之處在于 PTHREAD_MUTEX_INITIALIZER 宏不進行錯誤檢查。

    傳回值：

    成功：0，成功申請的鎖預設是打開的。

    失敗：非 0 錯誤碼

  • 2）上鎖

    int pthread_mutex_lock(pthread_mutex_t *mutex);
               

    功能：對互斥鎖上鎖，若互斥鎖已經上鎖，則調用者一直阻塞，直到互斥鎖解鎖後再上鎖。

    參數：mutex：互斥鎖位址。

    成功：0

    int pthread_mutex_trylock(pthread_mutex_t *mutex);
               

    調用該函數時，若互斥鎖未加鎖，則上鎖，傳回 0；若互斥鎖已加鎖，則函數直接傳回失敗，即 EBUSY。
  • 3）解鎖

    int pthread_mutex_unlock(pthread_mutex_t * mutex);
               

    功能：對指定的互斥鎖解鎖。
  • 4）銷毀互斥鎖

    int pthread_mutex_destroy(pthread_mutex_t *mutex);
               

    功能：

    銷毀指定的一個互斥鎖。互斥鎖在使用完畢後，必須要對互斥鎖進行銷毀，以釋放資源。

練習題解析

• 12.1

  在圖12-5中，并發伺服器的第33行上，父程序關閉了已連接配接描述符後，子程序仍然能夠使用該描述符和用戶端通信。為什麼?

  解析：當父程序派生子程序時，它得到一個已連接配接描述符的副本，并将相關檔案表中的引用計數從1增加到2。當父程序關閉它的描述符副本時，引用計數就從2減少到1。因為核心不會關閉一個檔案，直到檔案表中它的引用計數值變為零，是以子程序這邊的連接配接端将保持打開。

• 12.2

  如果我們要删除圖12-5中關閉已連接配接描述符的第30行，從沒有記憶體洩漏的角度來說，代碼将仍然是正确的。為什麼?

  解析：當一個程序因為某種原因終止時，核心将關閉所有打開的描述符。是以，當子程序退出時，它的已連接配接檔案描述符的副本也将被自動關閉。

• 12.3

  在Linux系統裡，在标準輸入上鍵入Ctrl+D表示EOF。圖12-6中的程式阻塞在對select的調用上時，如果你鍵入Ctrl-D會發生什麼?

  解析：回想一下，如果一個從描述符中讀一個位元組的請求不會阻塞，那麼這個描述符就準備好可以讀了。假如EOF在一個描述符上為真，那麼描述符也準備好可讀了，因為讀操作将立即傳回一個零傳回碼，表示EOF。是以，鍵人Ctrl+ D會導緻select函數傳回，準備好的集合中有描述符O。

• 12.4

  重新初始化圖12-8所示的伺服器中，我們在每次調用select之前都立即小心地pool.ready_ set變量。為什麼?

  解析：因為變量pool.read_set既作為輸人參數也作為輸出參數，是以我們在每一次調用select之前都重新初始化它。在輸人時，它包含讀集合。在輸出，它包含準備好的集合。

• 12.5

  在圖12-5中基于程序的伺服器中，我們在兩個位置小心地關閉了已連接配接描述符:父程序和子程序。然而，在圖12-14中基于線程的伺服器中，我們隻在一個位置關閉了已連接配接描述符:對等線程。為什麼?

  解析：因為線程運作在同一個程序中，它們都共享相同的描述符表。無論有多少線程使用這個已連接配接描述符，這個已連接配接描述符的檔案表的引用計數都等于1。是以，當我們用完它時，一個close操作就足以釋放與這個已連接配接描述符相關的記憶體資源了。

• 12.6

  A.利用12. 4節中的分析，為圖12-15中的示例程式在下表的每個條目中填寫“是”或者“否”。在第一列中，符号v. t表示變量二的一個執行個體，它駐留線上程t的本地棧中，其中t要麼是m(主線程)，要麼是p0(對等線程0)或者p1(對等線程1)。

  變量執行個體	主線程引用的？	對等線程0引用的	對等線程1引用的
  ptr	是
  cnt	否
  i.m
  msgd.m
  myid.po
  myid.pI
  說明:
  ptr:一個被主線程寫和被對等線程讀的全局變量。
  cnt:一個靜态變量，在記憶體中隻有一個執行個體，被兩個對等線程讀和寫。
  i.m:一個存儲在主線程棧中的本地自動變量。雖然它的值被傳遞給對等線程，但是對等線程也絕不會在棧中引用它，是以它不是共享的。
  msgs.m:一個存儲在主線程棧中的本地自動變量，被兩個對等線程通過ptr間接地引用。
  myid.0和myid.1:一個本地自動變量的執行個體，分别駐留在對等線程。和線程1的棧中。

  B.根據A部分的分析，變量ptr,cnt、i、msgD和myid哪些是共享的?

  解析：變量ptr, cnt和msgs被多于一個線程引用，是以它們是共享的。

• 12.7根據badcn七.c的指令順序完成下表:

  步驟	線程	指令	%rdx1	%rdx2
  1		H1
  2		L1
  3		H2
  4		L2
  5		U2
  6		S2
  7		U1
  8		S1
  9		T1
  10		T2
  這種順序會産生一個正确的cnt值嗎?
  解析：變量cnt最終有一個不正确的值1。

• 12.8使用圖12-21中的進度圖，将下列軌迹線劃分為安全的或者不安全的。

  A. H1，L1，U1，S1，H2，L2，U2，S2，T2，T1

  B. H2，L2，H1，L1，U1，S1，T1，U2，S2，T2

  C. H1，H2，L2，U2，S2，L1，U1，S1，T1，T2

  

  安全和不安全軌迹線。臨界區的交集形成了不安全區。

  繞開不安全區的軌迹線能夠正确更新計數器變量

  解析：

  A. H1 , L1 , U1 , S1 , H2 , L2 , U2 , S2 , T2 , T1:安全的

  B. H2 , L2 , H1 , L1 , U1 , S1 , T1 , U2 , S2 ,T2:不安全的

  C. H1，H2，L2，U2，S2，L1，U1，S1，T1 , T2:安全的

• 12.9設p表示生産者數量，c表示消費者數量，而n表示以項目單元為機關的緩沖區大小。對于下面的每個場景，指出sbuf_insert和sbuf_remove中的互斥鎖信号量是否是必需的。

  A. p=1，c=1，n>1

  B. p =1，c=1，n=1

  C. p>1，c>1，n=1

  A. p=1,c=1, n>1:是，互斥鎖是需要的，因為生産者和消費者會并發地通路緩沖區。

  B. p=1, c=1, n=1:不是，在這種情況中不需要互斥鎖信号量，因為一個非空的緩沖區就等于滿的緩沖區。當緩沖區包含一個項目時，生産者就被阻塞了。當緩沖區為空時，消費者就被阻塞了。是以在任意時刻，隻有一個線程可以通路緩沖區，是以不用互斥鎖也能保證互斥。

  C. p>1, c>1, n=1:不是，在這種情況中，也不需要互斥鎖，原因與前面一種情況相同。

• 12.10圖12-2 6所示的對第一類讀者一寫者問題的解答給予讀者較高的優先級，但是從某種意義上說，這種優先級是很弱的，因為一個離開臨界區的寫者可能重新開機一個在等待的寫者，而不是一個在等待的讀者。描述出一個場景，其中這種弱優先級會導緻一群寫者使得一個讀者饑餓。

  解析：假設一個特殊的信号量實作為每一個信号量使用了一個LIFO的線程棧。當一個線程在P操作中阻塞在一個信号量上，它的ID就被壓人棧中。類似地，V操作從棧中彈出棧頂的線程ID，并重新開機這個線程。根據這個棧的實作，一個在它的臨界區中的競争的寫者會簡單地等待，直到在它釋放這個信号量之前另一個寫者阻塞在這個信号量上。在這種場景中，當兩個寫者來回地傳遞控制權時，正在等待的讀者可能會永遠地等待下去。注意，雖然用FIFO隊列而不是用LIFO更符合直覺，但是使用LIFO)的棧也是對的，而且也沒有違反屍和V操作的語義。

• 12.11對于下表中的并行程式，填寫空白處。假設使用強擴充。

  線程(t)
  核(p)
  運作時間(Tp)	12
  加速比(Sp)		1.5
  效率比(Ep)	100%	75%	50%

• 12.12圖12-38中的come is函數是線程安全的，但不是可重入的。請解釋說明。

  解析：ctime_ts函數不是可重人函數，因為每次調用都共享相同的由gethostbyname函數傳回的static變量。然而，它是線程安全的，因為對共享變量的通路是被屍和V操作保護的，是以是互斥的。

• 12.13在圖12-43中，我們可能想要在主線程中的第14行後立即釋放已配置設定的記憶體塊，而不是在對等線程中釋放它。但是這會是個壞注意。為什麼?

  解析：如果在第14行調用了pthread_ create之後，我們立即釋放塊，那麼将引人一個新的競争，這次竟争發生在主線程對free的調用和線程例程中第24行的指派語句之間。

• 12.14

  A.在圖12-43中，我們通過為每個整數ID配置設定一個獨立的塊來消除競争。給出一個不調用malloc或者free函數的不同的方法。

  B.這種方法的利弊是什麼?

  A.

  for(i=0;i<N,i++)
  	Pthread_create(&tid[i],NULL,thread,(void *)i);
             

  線上程例程中，我們将參數強制轉換成一個int類型，并将它指派給myid：

  int myid = (int) vargp;
             

  B.優點是它通過消除對malloc和free的調用降低了開銷。一個明顯的缺點是，它假設指針至少和int一樣大。即便這種假設對于所有的現代系統來說都為真，但是它對于那些過去遺留下來的或今後的系統來說可能就不為真了。

• 12.15思考下面的程式，它試圖使用一對信号量來實作互斥。

  初始時:s=1, t=0.

  線程1: 線程2:

  P(s); P(s);

  V(s); V(s);

  P(t); P(t);

  V(t); v(t);

  A.畫出這個程式的進度圖。

  B.它總是會死鎖嗎?

  C.如果是，那麼對初始信号量的值做哪些簡單的改變就能消除這種潛在的死鎖呢?

  D.畫出得到的無死鎖程式的進度圖。

  

  B.因為任何可行的軌迹最終都陷人死鎖狀态中，是以這個程式總是會死鎖。

  C.為了消除潛在的死鎖，将二進制信号量t初始化為1而不是0。

  D.改成後的程式的進度圖如圖12-49所示。