【正文】 edu. 并行編譯器 ? 流分析 要使程序并行地執(zhí)行，首先要進行 相關性分析 （Dependency Analysis） ? 四種相關形式： ? 流相關 ：從 Si～ Sj存在執(zhí)行通路，且 Si至少有一個輸出被用作 Sj的輸入 ? 反相關 ： Sj緊接 Si，且 Sj的輸出被作為 Si的輸入 ? 輸出相關 ：兩條語句往相同的變量里寫 ? 控制相關 ：語句 Sj的執(zhí)行與否依賴于語句 Si 長春工業(yè)大學計算機科學與工程學院 ://.edu. 并行編譯器 ? 代碼優(yōu)化 ? 代碼向量化 （ Code Vectorization） : 把標量程序中的由一種可向量化循環(huán)完成的操作變換成向量操作。 ? 代碼并行化 （ Code Parallelization） :并行代碼的優(yōu)化是將一個程序展開成多線程以同時供多臺處理機并行執(zhí)行，其目的是要減少總的執(zhí)行時間。 ? 代碼生成 ? 并行代碼生成（ Code Generation）涉及到將優(yōu)化后的中間形式的代碼轉換程可執(zhí)行的具體的機器目標代碼。包括執(zhí)行次序、指令選擇、寄存器分配、負載平衡、并行粒度、代碼調度以及后優(yōu)化（ Postoptimization）等問題。 多核程序設計 第三章 多線程編程方法綜述 長春工業(yè)大學計算機科學與工程學院 ://.edu. 進程 ? 定義 ：進程是具有一定獨立功能的程序關于一個數據集合的一次運行活動 ?？杀硎境伤脑M （ P, C, D, S） ，其中 P是程序代碼， C是進程的控制狀態(tài)， D是進程的數據， S是進程的執(zhí)行狀態(tài)。 ? 狀態(tài) ： ? 運行態(tài) (Run): 進程占有處理機資源 , 正在運行 。 ? 就緒態(tài) (Ready): 進程本身具備運行條件 , 但由于處理機的個數少于可運行進程的個數 , 暫未投入運行 。 ? 等待態(tài) (Wait): 進程本身不具備運行條件，即使分給它處理機也不能運行 . 進程正等待某一個事件的發(fā)生 , 如等待某一資源被釋放，等待與該進程相關的 I/O傳輸的完成信號等 。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 進程 ? 狀態(tài)間轉換 ? 當一個就緒進程獲得處理機時 , 其狀態(tài)由就緒變?yōu)檫\行； ? 當一個運行進程被剝奪處理機時 , 其狀態(tài)由運行變?yōu)榫途w； ? 當一個運行進程因某事件受阻時 , 如所申請資源被占用 , 啟動 I/O傳輸未完成 , 其狀態(tài)由運行變?yōu)榈却? ? 當所等待事件發(fā)生時 , 如得到申請資源 , I/O傳輸完成 , 其狀態(tài)由等待變?yōu)榫途w。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 進程 ? 進程控制塊 (Process Control Block， PCB):標志進程存在的數據結構，其中包含系統(tǒng)對進程管理需要的全部信息。 進程標識 用戶標識 進程狀態(tài) 調度參數 現(xiàn)場信息 家族聯(lián)系 程序地址 當前打開文件 消息隊列指針 資源使用情況 進程隊列指針 長春工業(yè)大學計算機科學與工程學院 ://.edu. 進程 ? 進程的組成 ? 進程控制塊 ：由于進程控制塊中包含程序的地址信息，通過它可以找到程序在內存或外存的存放地址，也就找到了整個進程 . PCB存于系統(tǒng)空間，只有操作系統(tǒng)能夠對其存取，用戶程序不能訪問 . 實際上用戶甚至感覺不到 PCB的存在； ? 程序 ：進程的 “ 軀體 ” ，其中包括代碼和數據兩個部分 . 現(xiàn)代操作系統(tǒng)都支持程序共享的功能，這就要求代碼是 “ 純 ” 的，即在運行期間不修改自身。數據一般包括靜態(tài)變量、動態(tài)堆和動態(tài)棧。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 進程 ? 進程的表示 PCB 程序 PCB 代碼 數據 + 堆棧 系統(tǒng)空間 用戶空間 （ a） （ b） 長春工業(yè)大學計算機科學與工程學院 ://.edu. 進程 ? 進程的隊列 為實現(xiàn)對進程的管理，系統(tǒng)需要按照某種策略將進程排成若干隊列，由于 PCB是進程的代表，因而進程隊列實際上是由進程 PCB構成的隊列 . 因為該隊列通常由鏈的形式實現(xiàn)的，所以也稱 PCB鏈 。 系統(tǒng)中的進程隊列分為如下三類：就緒隊列 、 等待隊列 、 運行隊列 。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 進程 ? 進程的隊列 ? 就緒隊列 ? 整個系統(tǒng)一個。所有處于就緒狀態(tài)的進程按照某種組織方式排在這一隊列中。 ? 等待隊列 ? 每個等待事件一個，當進程等待某一事件時，進入與該事件相關的等待隊列中；當某事件發(fā)生時，與該事件相關的一個或多個進程離開相應的等待隊列，進入就緒隊列。 ? 運行隊列 ? 在單 CPU系統(tǒng)中只有一個，在多 CPU系統(tǒng)中每個 CPU各有一個，每個隊列中只有一個進程，指向運行隊列頭部的指針被稱作運行指示字。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 進程 ? 進程的類型 ? 系統(tǒng)進程 ——運行操作系統(tǒng)程序，完成操作系統(tǒng)的某些功能 ； ? 用戶進程 ——運行用戶程序，直接為用戶服務 。 ? 進程的特性 ? 并發(fā)性：與其它進程一道在宏觀上同時向前推進 ； ? 動態(tài)性：進程是執(zhí)行中的程序 . 此外進程的動態(tài)性還體現(xiàn)在如下兩個方面：首先，進程是動態(tài)產生、動態(tài)消亡的；其次，在進程的生存期內，其狀態(tài)處于經常性的動態(tài)變化之中 ； ? 獨立性：進程是調度的基本單位，它可以獲得處理機并參與并發(fā)執(zhí)行 ； ? 交往性：進程在運行過程中可能會與其它進程發(fā)生直接或間接的相互作用 ； ? 異步性：每個進程都以其相對獨立、不可預知的速度向前推進 ； ? 結構性：每個進程有一個控制塊 PCB 。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 進程 ? 兩個特征 ? 資源特征，包括程序執(zhí)行所必需的計算資源，例如程序代碼、內存地址空間、文件系統(tǒng)、 I/O設備、程序計數器、寄存器、?？臻g等 ? 執(zhí)行特征，包括在進程執(zhí)行過程中動態(tài)改變的特征，例如指令路徑（即進程執(zhí)行的指令序列）、進程的控制與執(zhí)行狀態(tài)等。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 進程間通信 ? 現(xiàn)代操作系統(tǒng)提供基本的系統(tǒng)調用函數，允許位于同一臺處理機或不同處理機的多個進程之間相互交流信息 ? 三種表現(xiàn)形式 ： ? 通信：進程間的數據傳遞稱為進程間通信。 兩個進程間傳遞的數據稱為 消息 ；這種操作稱為 消息傳遞 ? 同步：同步是使位于相同或不同處理機中的多個進程之間相互等待的操作，它要求進程的所有操作均必須等待到達某個控制狀態(tài)之后才進行。 ? 聚集（或規(guī)約）：聚集將位于相同或不同處理機中的多個進程的局部結果綜合起來，通過某種操作，產生一個新的結果，存儲在某個指定的或者所有的進程的變量中。 ? 具體實現(xiàn) ： ? 在共享存儲環(huán)境中，通過讀 /寫操作系統(tǒng)通過的共享數據緩存區(qū)來實現(xiàn) ? 在分布式存儲網絡環(huán)境中，通過網絡通信來實現(xiàn) 長春工業(yè)大學計算機科學與工程學院 ://.edu. 進程的創(chuàng)建與撤銷 ? 進程創(chuàng)建 ? 建立一個 PCB， 并對其內容進行初始化； ? 為該進程分配必要的存儲空間，并加載所要執(zhí)行的程序 (在 UNIX系統(tǒng)中需要通過另外一個系統(tǒng)調用 execl實現(xiàn) )； ? 將 PCB送入就緒隊列。 ? 進程撤銷 ? 完成使命的進程需要終止自己并告知操作系統(tǒng)，系統(tǒng)將對進程進行善后處理 (收集進程狀態(tài)信息、通知其父進程等 )，之后將收回進程所占有的所有資源 (打開文件、內存等 )，最后撤銷其 PCB 。，非正常終止也將進入操作系統(tǒng)進行善后處理 。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 線程的概念 ? 進程不適合細粒度的共享存儲并行程序設計。 ? 線程（ thread）是進程上下文（ context）中執(zhí)行的代碼序列 ，又被稱為輕量級進程（ light weight process）， 是進程內的一個相對獨立的執(zhí)行流。 ? 進程可由單個線程來執(zhí)行，即通常所說的串行執(zhí)行；或者由多個線程來并行執(zhí)行，此時，多個線程將共享該進程的所有資源特征，并可以使用不同的 CPU，對不同的數據進行處理，從而達到提高進程執(zhí)行速度的目的。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 線程的概念 ? 在支持多線程的系統(tǒng)中： ? 進程成為資源分配和保護的實體 ? 線程是被調度執(zhí)行的基本單元。 ? 進程的資源 ? 包括進程的地址空間，打開的文件和 I/O等 ? 屬于同一個進程的線程 ? 共享該進程的代碼段和數據段，打開的文件，信號等 ? 還包含各自的線程 ID， 線程執(zhí)行狀態(tài)， CPU寄存器狀態(tài)和棧 長春工業(yè)大學計算機科學與工程學院 ://.edu. 線程的概念 ? 進程和線程的區(qū)別 ? 進程 ——是指程序在一個數據集合上運行的過程，是系統(tǒng)進行資源分配和調度運行的一個獨立單位，有時也稱為活動、路徑或任務。 ? 操作系統(tǒng)中引入進程的目的，是為了使多個程序并發(fā)執(zhí)行，以改善資源利用率及提高系統(tǒng)的吞吐量。 ? 操作系統(tǒng)中再引入線程則是為了減少程序并發(fā)執(zhí)行時所付出的時空開銷，使操作系統(tǒng)具有更好的并發(fā)性。進程是資源的分配單位 。 ? 線程 ——是進程中的一個實體，是被系統(tǒng)調度和分配的基本單元。每個程序至少包含一個線程，那就是主線程。 ? 線程自己只擁有很少的系統(tǒng)資源（如程序計數器、一組寄存器和棧），但它可與同屬一個進程的其他線程共享所屬進程所擁有的全部資源。 ? 同一進程中的多個線程之間可以并發(fā)執(zhí)行，從而更好地改善了系統(tǒng)資源的利用率。 ? 線程是 CPU的調度單位 。 代碼 數據 文件寄存器 棧線程代碼 數據 文件寄存器棧寄存器棧寄存器棧線程長春工業(yè)大學計算機科學與工程學院 ://.edu. ? 線程是“進程中的一條執(zhí)行路徑或線索”或“進程中的一個可調度實體” 線程的概念 長春工業(yè)大學計算機科學與工程學院 ://.edu. ? 單線程與多線程處理器模型 線程的概念 長春工業(yè)大學計算機科學與工程學院 ://.edu. 線程的概念 ? 線程的優(yōu)點 ? 上下文切換速度快 ：由同一進程中的一個線程切換到另一個線程只需改變寄存器和棧，包括程序和數據在內的地址空間不變； ? 系統(tǒng)開銷小 ：創(chuàng)建線程比創(chuàng)建進程所需完成的工作少，因而對于客戶請求，服務器動態(tài)創(chuàng)建線程比動態(tài)創(chuàng)建進程具有更高的響應速度； ? 通訊容易 ：由于同一進程中的多個線程地址空間共享，一個線程寫到數據空間的信息可以直接被該進程中的另一線程讀取，方便快捷 ； ? 終止 一個線程比終止一個進程的 代價 要 小 。 長春工業(yè)大學計算機科學與工程學院 ://.edu. 線程的概念 ? 調度 ? 在傳統(tǒng)的操作系統(tǒng)中， CPU調度和分派的基本單位是進程。而在引入線程的操作系統(tǒng)中，則把線程作為 CPU調度和分派的基本單位，進程則作為資源擁有的基本單位，從而使傳統(tǒng)進程的兩個屬性分開，線程便能輕裝運行，從而顯著地提高系統(tǒng)的并發(fā)性。 ? 同一進程中線程的切換不會引起進程切換，從而避免了昂貴的系統(tǒng)調用。但是在由一個進程中的線程切換到另一進程中的線程時，依然會引起進程切換。 長春工業(yè)大學計算機