20145203 《信息安全系统设计基础》第十三周学习总结
20145203 《信息安全系統設計基礎》第十三周學習總結
第十二章 并發編程
教材學習內容總結
緒論
三種基本的構造并發程序的方法：
①進程：
每個邏輯控制流是一個進程，由內核進行調度，進程有獨立的虛擬地址空間
②I/O多路復用：
邏輯流被模型化為狀態機，所有流共享同一個地址空間
③線程：
運行在單一進程上下文中的邏輯流，由內核進行調度，共享同一個虛擬地址空間
第一節 基于進程的并發編程
構造并發程序最簡單的方法——用進程
1、常用函數如下：
- fork
- exec
- waitpid
2、構造并發服務器
在父進程中接受客戶端連接請求，然后創建一個新的子進程來為每個新客戶端提供服務。
需要注意的事情：
①父進程需要關閉它的已連接描述符的拷貝（子進程也需要關閉）
②必須要包括一個SIGCHLD處理程序來回收僵死子進程的資源
③父子進程之間共享文件表，但是不共享用戶地址空間。
3、進程的獨立地址空間
①優點：防止虛擬存儲器被錯誤覆蓋
②缺點：開銷高，共享狀態信息才需要IPC機制
第二節 基于I/O多路復用的并發編程
就是使用select函數要求內核掛起進程，只有在一個或多個I/O事件發生后，才將控制返回給應用程序。
1、select函數：select函數處理類型為fd_set的集合，即描述符集合，并在邏輯上描述為一個大小為n的位向量，每一位b[k]對應描述符k，但當且僅當b[k]=1，描述符k才表明是描述符集合的一個元素。
2、描述符能做的三件事：
- 分配他們
- 將一個此種類型的變量賦值給另一個變量
- 用FD_ZERO、FD_SET、FD_CLR和FD_ISSET宏指令來修改和檢查它們
3、什么時候可以讀？
當且僅當一個從該描述符讀取一個字節的請求不會阻塞時
注意：
每次調用select函數時都需要更新讀集合
4、基于I/O多路復用的并發事件驅動服務器
事件驅動程序：將邏輯流模型化為狀態機。
狀態機：
- 狀態：等待描述符d[k]準備好可讀
- 輸入事件：描述符d[k]準備好，可以讀了
- 轉移：從描述符d[k]讀一個文本行
整體的流程是：
- select函數檢測到輸入事件
- add_client函數創建新狀態機
- check_clients函數執行狀態轉移（在課本的例題中是回送輸入行），并且完成時刪除該狀態機。
用到的函數：
- init_pool：初始化客戶端池
- add_client：添加一個新的客戶端到活動客戶端池中
- check_clients：回送來自每個準備好的已連接描述符的一個文本行
5、I/O多路復用技術的優劣
①優點
- 相較基于進程的設計，給了程序員更多的對程序程序的控制
- 運行在單一進程上下文中，所以每個邏輯流都可以訪問該進程的全部地址空間，共享數據容易實現
- 可以使用GDB調試
- 高效
②缺點
- 編碼復雜
- 不能充分利用多核處理器
第三節 基于線程的并發編程
這種模式混合了以上兩種方法：像進程流一樣由內核進行調度，又像I/O多路復用流一樣共享同一個虛擬地址空間
線程：就是運行在進程上下文中的邏輯流。
1、每個線程都有它自己的線程上下文：
- 一個唯一的整數線程ID——TID
- 棧
- 棧指針
- 程序計數器
- 通用目的寄存器
- 條件碼
2、線程執行模型
①主線程
在每個進程開始生命周期時都是單一線程——主線程，與其他進程的區別僅有：它總是進程中第一個運行的線程。
②對等線程
某時刻主線程創建，之后兩個線程并發運行。每個對等線程都能讀寫相同的共享數據。
3、主線程切換到對等線程的原因：
①主線程執行一個慢速系統調用，如read或sleep
② 被系統的間隔計時器中斷
注意：
①切換方式：上下文切換
②對等線程執行一段時間后會控制傳遞回主線程
4、線程和進程的區別
- 線程的上下文切換比進程快得多
- 組織形式：
進程：嚴格的父子層次
線程：一個進程相關線程組成對等（線程）池，和其他進程的線程獨立開來。一個線程可以殺死它的任意對等線程，或者等待他的任意對等線程終止。
5、Posix線程
Posix線程是C程序中處理線程的一個標準接口。基本用法是：
- 線程的代碼和本地數據被封裝在一個線程例程中
- 每個線程例程都以一個通用指針為輸入，并返回一個通用指針。
這里需要提到一個萬能函數的概念。
************************************************************************************************
萬能函數：
void func(void parameter)
typedef void (uf)(void para)
使用思想：即輸入的是指針，指向真正想要傳到函數里的數據，如果只有一個就直接讓指針指向這個數據，如果是很多就將它們放到一個結構體中，讓指針指向這個結構體。
線程例程也是這樣的。
************************************************************************************************
6、創建線程
①.創建線程：pthread_create函數
#include <pthread.h>
typedef void (func)(void );
創建一個新的線程，帶著一個輸入變量arg，在新線程的上下文運行線程例程f。
attr默認為NULL
參數tid中包含新創建線程的ID
7、查看線程ID——pthread_self函數
#include <pthread.h>
pthread_t pthread_self(void);返回調用者的線程ID（TID）8、終止線程
①終止線程的幾個方式：
- 隱式終止：頂層的線程例程返回
- 顯示終止：調用pthread_exit函數
*如果主線程調用，會先等待所有其他對等線程終止，再終止主線程和整個進程，返回值為pthread_return - 某個對等線程調用Unix的exit函數，會終止進程與其相關線程
- 另一個對等線程通過以當前線程ID作為參數調用pthread_cancle來終止當前線程
②pthread_exit函數
#include <pthread.h>void pthread_exit(void *thread_return);若成功返回0，出錯為非0③pthread_cancle函數
#include <pthread.h>void pthread_cancle(pthread_t tid);若成功返回0，出錯為非09、回收已終止線程的資源：pthread_join函數
#include <pthread.h>int pthread_join(pthread_t tid,void **thrad_return);這個函數會阻塞，直到線程tid終止，將線程例程返回的(void*)指針賦值為thread_return指向的位置，然后回收已終止線程占用的所有存儲器資源
10、分離線程
在任何一個時間點上，線程是可結合的，或是分離的。
①可結合的線程
- 能夠被其他線程收回其資源和殺死
- 被收回錢，它的存儲器資源沒有被釋放
- 每個可結合線程要么被其他線程顯式的收回，要么通過調用pthread_detach函數被分離
②分離的線程
- 不能被其他線程回收或殺死
- 存儲器資源在它終止時由系統自動釋放
③pthread_detach函數
#include <pthread.h>void pthread_detach(pthread_t tid);若成功返回0，出錯為非0這個函數可以分離可結合線程tid。
線程能夠通過以pthread_self()為參數的pthread_detach調用來分離他們自己。
11、初始化線程：pthread_once函數
#include <pthread.h> pthread_once_t once_control = PTHREAD_ONCE_INIT;int pthread_once(pthread_once_t *once_control, void (*init_routine)(void));總是返回012、基于線程的并發服務器中的注意事項
①調用pthread_create時，如何將已連接描述符傳遞給對等進程？
傳遞一個指向這個描述符的指針。
②競爭問題？
見第七節。
③避免存儲器泄露？
必須分離每個線程，使它終止時它的存儲器資源能被收回。
第四節 多線程程序中的共享變量
一個變量是共享的，當且僅當多個線程引用這個變量的某個實例。
1、線程存儲器模型
注意：寄存器從不共享，虛擬存儲器總是共享的。
2、將變量映射到存儲器
3、共享變量
變量v是共享的——當且僅當它的一個實例被一個以上的線程引用。
第五節 用信號量同步線程
一般而言，沒有辦法預測操作系統是否將為你的線程選擇一個正確的順序。
所以——進度圖
1、進度圖
進度圖是將n個并發線程的執行模型化為一條n維笛卡爾空間中的軌跡線，原點對應于沒有任何線程完成一條指令的初始狀態。
當n=2時，狀態比較簡單，是比較熟悉的二維坐標圖，橫縱坐標各代表一個線程，而轉換被表示為有向邊
①轉換規則：
- 合法的轉換是向右或者向上，即某一個線程中的一條指令完成
- 兩條指令不能在同一時刻完成，即不允許出現對角線
- 程序不能反向運行，即不能出現向下或向左
而一個程序的執行歷史被模型化為狀態空間中的一條軌跡線。
②線程循環代碼的分解：
- H：在循環頭部的指令塊
- L：加載共享變量cnt到線程i中寄存器%eax的指令。
- U：更新（增加）%eax的指令
- S：將%eax的更新值存回到共享變量cnt的指令
- T：循環尾部的指令塊
③幾個概念：
- 臨界區：對于線程i，操作共享變量cnt內容的指令L,U,S構成了一個關于共享變量cnt的臨界區。
- 不安全區：兩個臨界區的交集形成的狀態
- 安全軌跡線：繞開不安全區的軌跡線
2、信號量
需要注意的是，每個信號量在使用前必須初始化。
3、使用信號量來實現互斥
①基本思想
將每個共享變量（或者一組相關的共享變量）與一個信號量s（初始為1）聯系起來，然后用P和V操作將相應的臨界區包圍起來。
②幾個概念
- 二元信號量：用這種方式來保護共享變量的信號量叫做二元信號量，取值總是0或者1.
- 互斥鎖：以提供互斥為目的的二元信號量
- 加鎖：對一個互斥鎖執行P操作
- 解鎖；對一個互斥鎖執行V操作
- 計數信號量：被用作一組可用資源的計數器的信號量
- 禁止區：由于信號量的不變性，沒有實際可能的軌跡能夠包含禁止區中的狀態。
4、利用信號量來調度共享資源
①信號量的物理意義
- s.count >0表示還可執行wait(s)而不會阻塞的進程數（可用資源數）。每執行一次wait(s)操作，就意味著請求分配一個單位的資源。
- 當s.count ≤0時，表示已無資源可用，因此請求該資源的進程被阻塞。此時，s.count的絕對值等于該信號量阻塞隊列中的等待進程數。執行一次signal操作，就意味著釋放一個單位的資源。若s.count<0，表示s.queue隊列中還有被阻塞的進程，需要喚醒該隊列中的第一個進程，將它轉移到就緒隊列中。
②常見問題
這里的常見問題有生產者-消費者問題，和讀者-寫者問題。詳見課本P.670
第七節 其他并發問題
1、線程安全性
一個線程是安全的，當且僅當被多個并發線程反復的調用時，它會一直產生正確的結果。
2、四個不相交的線程不安全函數類以及應對措施：
- 不保護共享變量的函數——用P和V這樣的同步操作保護共享變量
- 保持跨越多個調用的狀態的函數——重寫，不用任何static數據。
- 返回指向靜態變量的指針的函數——①重寫；②使用加鎖-拷貝技術。
- 調用線程不安全函數的函數——參考之前三種
3、可重入性
①顯式可重入的：
所有函數參數都是傳值傳遞，沒有指針，并且所有的數據引用都是本地的自動棧變量，沒有引用靜態或全劇變量。
②隱式可重入的：
調用線程小心的傳遞指向非共享數據的指針。
4、競爭
①競爭發生的原因：
一個程序的正確性依賴于一個線程要在另一個線程到達y點之前到達它的控制流中的x點。也就是說，程序員假定線程會按照某種特殊的軌跡穿過執行狀態空間，忘了一條準則規定：線程化的程序必須對任何可行的軌
跡線都正確工作。
②消除方法：
動態的為每個整數ID分配一個獨立的塊，并且傳遞給線程例程一個指向這個塊的指針
5、死鎖：
一組線程被阻塞了，等待一個永遠也不會為真的條件。
①條件
②解決死鎖的方法
a.不讓死鎖發生：
- 靜態策略：設計合適的資源分配算法，不讓死鎖發生---死鎖預防；
- 動態策略：進程在申請資源時，系統審查是否會產生死鎖，若會產生死鎖則不分配---死鎖避免。
b.讓死鎖發生：
進程申請資源時不進行限制，系統定期或者不定期檢測是否有死鎖發生，當檢測到時解決死鎖----死鎖檢測與解除。
教材學習中的問題和解決過程
問題一：為什么要用結構體來存放標量IP地址？
解決：把一個標量地址存放在結構中，是套接字早期實現的不幸產物。位IP地址定義一個標量類型應該跟更有意義，但是現在更該已經太遲了，因為已經有大量的應用是基于此的了。
問題二：臨界區使用原則（互斥條件）
使用原則：
- 有空讓進：如果臨界區空閑，則只要有進程申請就立即讓其進入；
- 無空等待：每次只允許一個進程處于臨界區；
- 多中擇一：當沒有進程在臨界區，而同時有多個進程要求進入臨界區，只能讓其中之一進入臨界區，其他進程必須等待；
- 讓權等待：進入臨界區的進程，不能在臨界區內長時間阻塞等待某事件，使其它進程在臨界區外無限期等待；
不能限制進程的并發數量和執行進度。
問題三：信號量實現互斥的基本原理
基本原理：
- 兩個或多個進程通過傳遞信號進行合作，可以迫使進程在某個位置暫時停止執行（阻塞等待），直到它收到一個可以“向前推進”的信號（被喚醒）；
- 將實現信號燈作用的變量稱為信號量，常定義為記錄型變量s，其一個域為整型，另一個域為隊列，其元素為等待該信號量的阻塞進程(FIFO)。
信號量定義：
type semaphore=recordcount: integer;queue: list of process end; var s:semaphore;
定義對信號量的兩個原子操作——P和V
P（wait）
wait(s)
s.count :=s.count-1;
if s.count<0 then
begin
進程阻塞；
進程進入s.queue隊列；
end;
V（signal）
signal(s)
s.count :=s.count+1;
if s.count ≤0 then
begin
喚醒隊首進程；
將進程從s.queue阻塞隊列中移出;
end;
其它（思想、感悟）
本周內容中有很多在操作系統課程和java web編程課程中已經詳細講，但是需要注意的是，課本中講述問題的方式與操作系統課程中有些不同，本課更多是從代碼角度，兩者需要相輔相成，互相促進理解，這樣使得學習起來更輕松，也更全面。
本周代碼托管截圖
代碼鏈接
學習進度條
| 目標 | 5000行 | 30篇 | 400小時 | |
| 第一周 | 150/150 | 1/2 | 20/20 | |
| 第二周 | 200/350 | 1/2 | 24/44 | |
| 第三周 | 150/500 | 1/3 | 20/64 | |
| 第五周 | 300/800 | 1/4 | 15/79 | |
| 第六周 | 500/1300 | 1/5 | 20/99 | |
| 第七周 | 200/1500 | 1/6 | 21/120 | |
| 第九周 | 210/1710 | 1/9 | 10/130 | |
| 第十周 | 530/2240 | 2/11 | 20/150 | |
| 第十一周 | 900/3140 | 1/12 | 30/180 | |
| 第十三周 | 1100/4240 | 1/17 | 30/210 |
參考資料
- 《深入理解計算機系統V2》學習指導
- ...
轉載于:https://www.cnblogs.com/GZSdeboke/p/6160947.html
總結
以上是生活随笔為你收集整理的20145203 《信息安全系统设计基础》第十三周学习总结的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： XidianOJ 1176 ship
- 下一篇： Python自动化之django的ORM