第七章
1、簡(jiǎn)述緊耦合和松耦合的多機(jī)系統(tǒng)結(jié)構(gòu)
各處理機(jī)之間通過互連網(wǎng)絡(luò)共享主存的緊耦合多處理機(jī)。緊耦合系統(tǒng)由P臺(tái)處理機(jī)，m個(gè)存儲(chǔ)器模塊，d個(gè)I/O通道和3個(gè)互連網(wǎng)絡(luò)構(gòu)成。處理機(jī)-存儲(chǔ)器網(wǎng)絡(luò)實(shí)現(xiàn)處理機(jī)與各存儲(chǔ)模塊的連接。處理機(jī)中斷信號(hào)網(wǎng)絡(luò)實(shí)現(xiàn)多處理機(jī)之間的互連。處理機(jī)-I/O互連網(wǎng)絡(luò)實(shí)現(xiàn)處理機(jī)與外設(shè)的連接。每個(gè)處理機(jī)可自帶局部存儲(chǔ)器，也可自帶Cache.存儲(chǔ)器模塊可采用流水工作方式。緊耦合系統(tǒng)多用于并行作業(yè)中的多任務(wù)，一般處理機(jī)是同構(gòu)的。
各處理機(jī)間通過共享I/O子系統(tǒng)、通道或通信線路實(shí)現(xiàn)機(jī)間通信，不共享主存的是松耦合系統(tǒng)。松散耦合多處理機(jī)由P個(gè)處理機(jī)，一個(gè)通道，一個(gè)仲裁開關(guān)和消息傳送系統(tǒng)。每個(gè)處理機(jī)帶有一個(gè)局部存儲(chǔ)器和一組I/O設(shè)備。在仲裁開關(guān)的通道中有高速通信存儲(chǔ)，用來緩沖傳送的信息塊。松散耦合多處理機(jī)較適合粗粒度的并行計(jì)算。
2、簡(jiǎn)述對(duì)樹形結(jié)構(gòu)進(jìn)行變換的過程
首先利用交換律把相同的運(yùn)算集中在一起。然后利用結(jié)合律把參加這些運(yùn)算的操作數(shù)配對(duì)，盡可能并行運(yùn)算，從而組成樹高最小的子樹。最后再把這些子樹結(jié)合起來，用分配律進(jìn)一步降低樹高。
3、試比較3種類型的多處理機(jī)操作系統(tǒng)
主從型：管理程序只在一臺(tái)處理機(jī)上運(yùn)行。硬件結(jié)構(gòu)簡(jiǎn)單，控制簡(jiǎn)單，但對(duì)主機(jī)可靠性要求高，靈活性差。為目前大多數(shù)多處理機(jī)操作系統(tǒng)采用，工作負(fù)荷固定，從處理機(jī)能力明顯低于主處理機(jī)，或由功能差別大的多個(gè)處理機(jī)組成的異構(gòu)型系統(tǒng)。
各自獨(dú)立型：控制分散到多臺(tái)處理機(jī)，共同完成對(duì)整個(gè)系統(tǒng)的控制工作。適合分布計(jì)算模式，對(duì)主機(jī)依賴性差，可靠性高；但實(shí)現(xiàn)復(fù)雜，共享表格訪問沖突，處理機(jī)負(fù)荷平衡較困難。適用于松耦合處理機(jī)系統(tǒng)。
浮動(dòng)型：管理程序在處理機(jī)間浮動(dòng)。靈活性高，但發(fā)生訪問表格沖突，設(shè)計(jì)較困難。適合緊耦合多處理機(jī)系統(tǒng)，特別是共享主存和I/O子系統(tǒng)的同構(gòu)多處理機(jī)系統(tǒng)。
4、比較多處理機(jī)系統(tǒng)中數(shù)據(jù)相關(guān)的處理方式
并行 順序串行 交換串行
“先讀后寫” 可以（有條件） 可以 不可以
“寫-寫” 可以（有條件） 可以 不可以
“先寫后讀” 不允許 可以 特殊情況可以
“先讀后寫”和“先寫后讀” 必須 不允許 不允許
無任何相關(guān) 可以 可以 可以
5、多處理機(jī)系統(tǒng)與并行處理機(jī)的主要差別是什么？多處理機(jī)系統(tǒng)主要解決的技術(shù)問題是什么？
有差別的原因是并行性等級(jí)不同，多處理機(jī)系統(tǒng)是任務(wù)級(jí)并行，并行處理機(jī)是操作級(jí)并行。具體講：
1）結(jié)構(gòu)靈活性不同。
2）程序并行性等級(jí)不同。軟硬件支持不同。
3）并行任務(wù)派生的方式不同。并行處理機(jī)能否并行工作由指令決定；多處理機(jī)必須有專門指令指明程序段能否并行執(zhí)行，派生的任務(wù)數(shù)是動(dòng)態(tài)變化的。
4）進(jìn)程同步。并行處理機(jī)工作同步是自然的，而多處理機(jī)必須采取同步措施。
5）資源分配和任務(wù)調(diào)度，多處理機(jī)比并行處理機(jī)任務(wù)調(diào)度復(fù)雜。
多處理機(jī)必須解決的技術(shù)問題：
1）硬件結(jié)構(gòu)上多處理機(jī)、主存、I/O子系統(tǒng)之間應(yīng)有高帶寬、低價(jià)格、靈活無規(guī)則的互連，盡可能不發(fā)生信息傳送的路徑?jīng)_突。
2）從并行語言、并行算法、編譯等上，限度地開發(fā)出程序的并行性，實(shí)現(xiàn)多處理機(jī)各級(jí)的全面并行。
3）大的任務(wù)如何細(xì)分成多個(gè)子任務(wù)、任務(wù)的粒度選擇。
4）從操作系統(tǒng)上解決好多處理機(jī)間、并行任務(wù)的分配、調(diào)度和資源分配；任務(wù)或進(jìn)程間的同步死鎖和競(jìng)爭(zhēng)等問題的解決。
5）系統(tǒng)的重組及良好的編程環(huán)境。
6、簡(jiǎn)述JOIN語句和FORK語句的基本功能。
FORK m的功能：
1）準(zhǔn)備好新進(jìn)程啟動(dòng)和執(zhí)行的必須信息。
2）將空閑處理機(jī)分配給派生的新進(jìn)程，若沒有，則排隊(duì)等待。
3）繼續(xù)在原處理機(jī)上執(zhí)行FORK m語句的原進(jìn)程。
JOIN n的功能：
1）JOIN語句將計(jì)數(shù)器初始化為0；
2）執(zhí)行一次JOIN語句，計(jì)數(shù)器+1，并與n比較。
3）若相等，則允許進(jìn)程通過JOIN語句，計(jì)數(shù)器清0，進(jìn)程繼續(xù)執(zhí)行。
4）若不相等，則執(zhí)行JOIN語句的進(jìn)程結(jié)束，釋放處理機(jī)。
7、試比較機(jī)間互連的幾種形式。
總線形式：處理機(jī)與外部存儲(chǔ)器模塊通過總線相連。結(jié)構(gòu)簡(jiǎn)單、成本低、擴(kuò)展性好；但總線失效敏感，存在總線爭(zhēng)用。適合處理機(jī)較少、系統(tǒng)信息流量少、機(jī)數(shù)可擴(kuò)充情況。
環(huán)形互連：各處理機(jī)點(diǎn)點(diǎn)相加成環(huán)。結(jié)構(gòu)簡(jiǎn)單、成本低、不爭(zhēng)用總線；但信息傳輸有延遲。適合處理機(jī)較少、使用高寬帶的光纖通信、系統(tǒng)流量高、機(jī)數(shù)可擴(kuò)充的情況。
交叉開關(guān)：用縱橫開關(guān)陣列將存儲(chǔ)器模塊、I/O通道相連。不爭(zhēng)用開關(guān)；但開關(guān)陣列復(fù)雜，設(shè)備量較大。適合處理機(jī)數(shù)較多（但不超過16）、系統(tǒng)流量大、處理機(jī)數(shù)可擴(kuò)充的情況。
多端口存儲(chǔ)器：將交叉開關(guān)移到存儲(chǔ)器接口中。不爭(zhēng)用總線，但存儲(chǔ)器接口復(fù)雜，較難控制。適合處理機(jī)數(shù)少、不能擴(kuò)充（一般是2臺(tái)），系統(tǒng)流量高的情況。
開關(guān)樞紐結(jié)構(gòu)：把交叉開關(guān)設(shè)置在各處理機(jī)或接口內(nèi)部。所有開關(guān)樞紐數(shù)量少，可用較短路徑與處理機(jī)連接；但開關(guān)樞紐較復(fù)雜。適合處理機(jī)數(shù)多、可擴(kuò)充、分布結(jié)構(gòu)情況。
8、多處理機(jī)在結(jié)構(gòu)與并行性方面與陣列處理機(jī)有什么不同？
結(jié)構(gòu)方面：陣列處理機(jī)的互連較規(guī)整，有一定專用性，互連的處理單元數(shù)量大；多處理機(jī)要采用更靈活多變的結(jié)構(gòu)，實(shí)現(xiàn)復(fù)雜的互連模式，互連的處理機(jī)數(shù)量少。
并行性方面：陣列處理機(jī)是操作級(jí)并行，是并行性的同時(shí)性；多處理機(jī)是作業(yè)、程序、任務(wù)級(jí)的并行，同時(shí)包含指令內(nèi)部操作間的并行，是并行性的并發(fā)性。
9、多處理機(jī)中的并行性表現(xiàn)在哪些方面？開發(fā)多處理機(jī)的并行性有哪些途徑？
多處理機(jī)主要實(shí)現(xiàn)作業(yè)之間、程序段之間、任務(wù)之間的并行，也可包含有指令級(jí)、指令內(nèi)部各微操作之間的并行。
多處理機(jī)的并行性可利用并行算法、并行程序設(shè)計(jì)語言、并行編譯、并行操作系統(tǒng)以及指令硬件等多種途徑來開發(fā)和實(shí)現(xiàn)。
1、簡(jiǎn)述緊耦合和松耦合的多機(jī)系統(tǒng)結(jié)構(gòu)
各處理機(jī)之間通過互連網(wǎng)絡(luò)共享主存的緊耦合多處理機(jī)。緊耦合系統(tǒng)由P臺(tái)處理機(jī)，m個(gè)存儲(chǔ)器模塊，d個(gè)I/O通道和3個(gè)互連網(wǎng)絡(luò)構(gòu)成。處理機(jī)-存儲(chǔ)器網(wǎng)絡(luò)實(shí)現(xiàn)處理機(jī)與各存儲(chǔ)模塊的連接。處理機(jī)中斷信號(hào)網(wǎng)絡(luò)實(shí)現(xiàn)多處理機(jī)之間的互連。處理機(jī)-I/O互連網(wǎng)絡(luò)實(shí)現(xiàn)處理機(jī)與外設(shè)的連接。每個(gè)處理機(jī)可自帶局部存儲(chǔ)器，也可自帶Cache.存儲(chǔ)器模塊可采用流水工作方式。緊耦合系統(tǒng)多用于并行作業(yè)中的多任務(wù)，一般處理機(jī)是同構(gòu)的。
各處理機(jī)間通過共享I/O子系統(tǒng)、通道或通信線路實(shí)現(xiàn)機(jī)間通信，不共享主存的是松耦合系統(tǒng)。松散耦合多處理機(jī)由P個(gè)處理機(jī)，一個(gè)通道，一個(gè)仲裁開關(guān)和消息傳送系統(tǒng)。每個(gè)處理機(jī)帶有一個(gè)局部存儲(chǔ)器和一組I/O設(shè)備。在仲裁開關(guān)的通道中有高速通信存儲(chǔ)，用來緩沖傳送的信息塊。松散耦合多處理機(jī)較適合粗粒度的并行計(jì)算。
2、簡(jiǎn)述對(duì)樹形結(jié)構(gòu)進(jìn)行變換的過程
首先利用交換律把相同的運(yùn)算集中在一起。然后利用結(jié)合律把參加這些運(yùn)算的操作數(shù)配對(duì)，盡可能并行運(yùn)算，從而組成樹高最小的子樹。最后再把這些子樹結(jié)合起來，用分配律進(jìn)一步降低樹高。
3、試比較3種類型的多處理機(jī)操作系統(tǒng)
主從型：管理程序只在一臺(tái)處理機(jī)上運(yùn)行。硬件結(jié)構(gòu)簡(jiǎn)單，控制簡(jiǎn)單，但對(duì)主機(jī)可靠性要求高，靈活性差。為目前大多數(shù)多處理機(jī)操作系統(tǒng)采用，工作負(fù)荷固定，從處理機(jī)能力明顯低于主處理機(jī)，或由功能差別大的多個(gè)處理機(jī)組成的異構(gòu)型系統(tǒng)。
各自獨(dú)立型：控制分散到多臺(tái)處理機(jī)，共同完成對(duì)整個(gè)系統(tǒng)的控制工作。適合分布計(jì)算模式，對(duì)主機(jī)依賴性差，可靠性高；但實(shí)現(xiàn)復(fù)雜，共享表格訪問沖突，處理機(jī)負(fù)荷平衡較困難。適用于松耦合處理機(jī)系統(tǒng)。
浮動(dòng)型：管理程序在處理機(jī)間浮動(dòng)。靈活性高，但發(fā)生訪問表格沖突，設(shè)計(jì)較困難。適合緊耦合多處理機(jī)系統(tǒng)，特別是共享主存和I/O子系統(tǒng)的同構(gòu)多處理機(jī)系統(tǒng)。
4、比較多處理機(jī)系統(tǒng)中數(shù)據(jù)相關(guān)的處理方式
并行 順序串行 交換串行
“先讀后寫” 可以（有條件） 可以 不可以
“寫-寫” 可以（有條件） 可以 不可以
“先寫后讀” 不允許 可以 特殊情況可以
“先讀后寫”和“先寫后讀” 必須 不允許 不允許
無任何相關(guān) 可以 可以 可以
5、多處理機(jī)系統(tǒng)與并行處理機(jī)的主要差別是什么？多處理機(jī)系統(tǒng)主要解決的技術(shù)問題是什么？
有差別的原因是并行性等級(jí)不同，多處理機(jī)系統(tǒng)是任務(wù)級(jí)并行，并行處理機(jī)是操作級(jí)并行。具體講：
1）結(jié)構(gòu)靈活性不同。
2）程序并行性等級(jí)不同。軟硬件支持不同。
3）并行任務(wù)派生的方式不同。并行處理機(jī)能否并行工作由指令決定；多處理機(jī)必須有專門指令指明程序段能否并行執(zhí)行，派生的任務(wù)數(shù)是動(dòng)態(tài)變化的。
4）進(jìn)程同步。并行處理機(jī)工作同步是自然的，而多處理機(jī)必須采取同步措施。
5）資源分配和任務(wù)調(diào)度，多處理機(jī)比并行處理機(jī)任務(wù)調(diào)度復(fù)雜。
多處理機(jī)必須解決的技術(shù)問題：
1）硬件結(jié)構(gòu)上多處理機(jī)、主存、I/O子系統(tǒng)之間應(yīng)有高帶寬、低價(jià)格、靈活無規(guī)則的互連，盡可能不發(fā)生信息傳送的路徑?jīng)_突。
2）從并行語言、并行算法、編譯等上，限度地開發(fā)出程序的并行性，實(shí)現(xiàn)多處理機(jī)各級(jí)的全面并行。
3）大的任務(wù)如何細(xì)分成多個(gè)子任務(wù)、任務(wù)的粒度選擇。
4）從操作系統(tǒng)上解決好多處理機(jī)間、并行任務(wù)的分配、調(diào)度和資源分配；任務(wù)或進(jìn)程間的同步死鎖和競(jìng)爭(zhēng)等問題的解決。
5）系統(tǒng)的重組及良好的編程環(huán)境。
6、簡(jiǎn)述JOIN語句和FORK語句的基本功能。
FORK m的功能：
1）準(zhǔn)備好新進(jìn)程啟動(dòng)和執(zhí)行的必須信息。
2）將空閑處理機(jī)分配給派生的新進(jìn)程，若沒有，則排隊(duì)等待。
3）繼續(xù)在原處理機(jī)上執(zhí)行FORK m語句的原進(jìn)程。
JOIN n的功能：
1）JOIN語句將計(jì)數(shù)器初始化為0；
2）執(zhí)行一次JOIN語句，計(jì)數(shù)器+1，并與n比較。
3）若相等，則允許進(jìn)程通過JOIN語句，計(jì)數(shù)器清0，進(jìn)程繼續(xù)執(zhí)行。
4）若不相等，則執(zhí)行JOIN語句的進(jìn)程結(jié)束，釋放處理機(jī)。
7、試比較機(jī)間互連的幾種形式。
總線形式：處理機(jī)與外部存儲(chǔ)器模塊通過總線相連。結(jié)構(gòu)簡(jiǎn)單、成本低、擴(kuò)展性好；但總線失效敏感，存在總線爭(zhēng)用。適合處理機(jī)較少、系統(tǒng)信息流量少、機(jī)數(shù)可擴(kuò)充情況。
環(huán)形互連：各處理機(jī)點(diǎn)點(diǎn)相加成環(huán)。結(jié)構(gòu)簡(jiǎn)單、成本低、不爭(zhēng)用總線；但信息傳輸有延遲。適合處理機(jī)較少、使用高寬帶的光纖通信、系統(tǒng)流量高、機(jī)數(shù)可擴(kuò)充的情況。
交叉開關(guān)：用縱橫開關(guān)陣列將存儲(chǔ)器模塊、I/O通道相連。不爭(zhēng)用開關(guān)；但開關(guān)陣列復(fù)雜，設(shè)備量較大。適合處理機(jī)數(shù)較多（但不超過16）、系統(tǒng)流量大、處理機(jī)數(shù)可擴(kuò)充的情況。
多端口存儲(chǔ)器：將交叉開關(guān)移到存儲(chǔ)器接口中。不爭(zhēng)用總線，但存儲(chǔ)器接口復(fù)雜，較難控制。適合處理機(jī)數(shù)少、不能擴(kuò)充（一般是2臺(tái)），系統(tǒng)流量高的情況。
開關(guān)樞紐結(jié)構(gòu)：把交叉開關(guān)設(shè)置在各處理機(jī)或接口內(nèi)部。所有開關(guān)樞紐數(shù)量少，可用較短路徑與處理機(jī)連接；但開關(guān)樞紐較復(fù)雜。適合處理機(jī)數(shù)多、可擴(kuò)充、分布結(jié)構(gòu)情況。
8、多處理機(jī)在結(jié)構(gòu)與并行性方面與陣列處理機(jī)有什么不同？
結(jié)構(gòu)方面：陣列處理機(jī)的互連較規(guī)整，有一定專用性，互連的處理單元數(shù)量大；多處理機(jī)要采用更靈活多變的結(jié)構(gòu)，實(shí)現(xiàn)復(fù)雜的互連模式，互連的處理機(jī)數(shù)量少。
并行性方面：陣列處理機(jī)是操作級(jí)并行，是并行性的同時(shí)性；多處理機(jī)是作業(yè)、程序、任務(wù)級(jí)的并行，同時(shí)包含指令內(nèi)部操作間的并行，是并行性的并發(fā)性。
9、多處理機(jī)中的并行性表現(xiàn)在哪些方面？開發(fā)多處理機(jī)的并行性有哪些途徑？
多處理機(jī)主要實(shí)現(xiàn)作業(yè)之間、程序段之間、任務(wù)之間的并行，也可包含有指令級(jí)、指令內(nèi)部各微操作之間的并行。
多處理機(jī)的并行性可利用并行算法、并行程序設(shè)計(jì)語言、并行編譯、并行操作系統(tǒng)以及指令硬件等多種途徑來開發(fā)和實(shí)現(xiàn)。