軟考流水線的一個(gè)典型題：

某指令流水線由5段組成半哟，各段所需要的時(shí)間如下圖所示呜达。

--> t --> 3t --> t --> 2t --> t -->

連續(xù)輸入10條指令時(shí)的吞吐率為（ ）却音。

A.10/70t B.10/49t C.10/35t D.10/30t

解答：

第一條指令』醭－（ －－－）－（－－）－

第二條指令　　　　　 －（－－－）－（－－）－

第三條指令??????????????????????　　　∏陡佟－（－－－）－（－－）－

因?yàn)椤∈橇魉€笔诵，所以時(shí)間為3t的指令不能重疊（小馬認(rèn)為可以理解為就一個(gè)3t的執(zhí)行單元），所以每隔3t時(shí)間開始一條指令萧恕，當(dāng)?shù)谝粭l指令花費(fèi)8t時(shí)間后刚梭，每隔3t完成一條指令，第10條指令完成的時(shí)間是：8+3*9=35t.

吞吐率為:10條指令/花費(fèi)時(shí)間35t＝10/35

弄懂兩個(gè)概念就好做了：流水線時(shí)間和吞吐率

流水線時(shí)間計(jì)算有個(gè)公式：一條指令所需時(shí)間+（指令條數(shù)-1）*時(shí)間最長的指令的一段 // 8t+9*3t=35t

吞吐率也有個(gè)公式：指令條數(shù)除以流水線時(shí)間 // 10/35t

原文

PV和前趨圖

概念：

信號量 ： 信號量(Semaphore)票唆，以下簡寫為S朴读，有時(shí)被稱為信號燈，是在多線程環(huán)境下使用的一種設(shè)施走趋，是可以用來保證兩個(gè)或多個(gè)關(guān)鍵代碼段不被并發(fā)調(diào)用衅金。

當(dāng)S>0時(shí)，表示當(dāng)前可用資源的數(shù)量簿煌。

當(dāng)S<0時(shí)氮唯，其絕對值表示等待使用該資源的進(jìn)程個(gè)數(shù)。

注意姨伟，信號量的值僅能由PV操作來改變惩琉。

PV操作： PV操作與信號量的處理相關(guān)，P表示通過的意思夺荒，V表示釋放的意思瞒渠。PV原語中P是荷蘭語的Passeren良蒸，相當(dāng)于英文的pass， V是荷蘭語的Verhoog伍玖，相當(dāng)于英文中的increment嫩痰。

? P操作可以看作是獲得或者請求、消耗一個(gè)信號量窍箍。

將信號量S的值減1串纺，即S=S-1；

如果S>=0仔燕，則該進(jìn)程繼續(xù)執(zhí)行造垛；否則該進(jìn)程置為等待狀態(tài)，排入等待隊(duì)列晰搀。

? V操作可以看作是釋放或者發(fā)送一個(gè)信號量五辽。

將信號量S的值加1，即S=S+1外恕；

如果S>0杆逗，則該進(jìn)程繼續(xù)執(zhí)行；否則釋放隊(duì)列中第一個(gè)等待信號量的進(jìn)程鳞疲。

下面來看幾道例題：

1.（2016年下半年例題）假設(shè)系統(tǒng)中有n個(gè)進(jìn)程共享3臺掃描儀罪郊，并采用PV操作實(shí)現(xiàn)進(jìn)程同步與互斥。若系統(tǒng)信號量S的當(dāng)前值為-1尚洽，進(jìn)程P1悔橄、P2又分別執(zhí)行了一次P(S)操作，那么信號量S的值應(yīng)為___腺毫。

解答：

根據(jù)PV操作概念中P操作公式癣疟，S=S-1，這里發(fā)生兩次P操作潮酒，那么當(dāng)前S的值應(yīng)該為-1減2次操作后等于-3睛挚。

【小馬認(rèn)為，這個(gè)根據(jù)公式急黎，是屬于比較簡單的一個(gè)送命題扎狱，啊不是，送分題】

2.（2016年上半年例題) 進(jìn)程P1勃教、P2淤击、P3、P4和P5的前趨圖如下圖所示：

若用PV操作控制進(jìn)程P1故源、P2遭贸、P3、P4和P5的并發(fā)執(zhí)行過程心软，則需要設(shè)置5個(gè)信號量S1壕吹、S2、S3删铃、S4和S5耳贬，且信號量S1～S5的初值都等于零。下圖中a和b處應(yīng)分別填入___;c和d處應(yīng)分別填入___;e和f處應(yīng)分別填入___猎唁。

解答：

根據(jù)前趨圖咒劲，P1進(jìn)程執(zhí)行完需要通知P2和P3進(jìn)程，所以需要利用V(S1)和V(S2)操作通知P2和P3進(jìn)程诫隅，所以空a應(yīng)該填V(S1)和V(S2)腐魂，P2進(jìn)程執(zhí)行完要通知P4進(jìn)程，所以空b應(yīng)該填V(S3)逐纬。P3進(jìn)程運(yùn)行前需要等待P1進(jìn)程的結(jié)果蛔屹，所以執(zhí)行程序前要先利用1個(gè)P操作，所以空c應(yīng)該填P(S2)豁生，而P3進(jìn)程運(yùn)行結(jié)束需要利用一個(gè)V操作通知P5進(jìn)程兔毒，所以空d應(yīng)該填V(S4)。P4進(jìn)程執(zhí)行結(jié)束需要利用一個(gè)V操作通知P5進(jìn)程甸箱，所以空e處應(yīng)該填V(S5)育叁，P5進(jìn)程執(zhí)行前需要等待P3和P4進(jìn)程的結(jié)果，所以空f處需要兩個(gè)P操作芍殖，那應(yīng)該填P(S4)和P(S5)豪嗽。

【小馬認(rèn)為，這種解題技巧可以這樣理解：既然是參考前趨圖那就充分利用前趨圖豌骏，在前趨圖上的每一個(gè)箭頭畫上信號燈龟梦，如下圖，問題便可迎刃而解肯适”淝兀】

3.(2015年下半年例題) 某企業(yè)的生產(chǎn)流水線上有2名工人P1和P2，1名質(zhì)檢員P3框舔。P1將初步加工的半成品放入半成品箱B1蹦玫；P2從半成品箱B1取出繼續(xù)加工，加工好的產(chǎn)品放入成品箱B2刘绣；P3從成品箱P2取出產(chǎn)品檢驗(yàn)樱溉。假設(shè)B1可存放n件半成品，B2可存放m件產(chǎn)品纬凤，并設(shè)置6個(gè)信號量S1福贞、S2、S3停士、S4挖帘、S5和S6完丽，且S3和S6的初值都為0。采用PV操作實(shí)現(xiàn)P1拇舀、P2和P3的同步模型如下圖所示逻族，則信號量S1和S5初始值分別為___，S2骄崩、S4的初始值分別為___聘鳞。

解答：

根據(jù)題意可以看出這是一道很典型的生產(chǎn)者消費(fèi)者問題，P1為生產(chǎn)者要拂，P2即是消費(fèi)者又是生產(chǎn)者抠璃，P3為消費(fèi)者，B1和B2為緩存區(qū)脱惰。

因?yàn)樾盘柫縎1是一個(gè)互斥信號量搏嗡，表示半成品箱B1當(dāng)前有無生產(chǎn)者使用，所以初值為1枪芒。信號量S5也是一個(gè)互斥信號量彻况，表示成品箱B2當(dāng)前有無生產(chǎn)者使用，所以初始值為1舅踪。

信號量S2表示半成品箱B1的容量纽甘，所以S2的初值為n。當(dāng)生產(chǎn)者P1不斷將半成品放入B1時(shí)抽碌，應(yīng)該先測試B1是否有空位悍赢，所以生產(chǎn)者P1使用P(S2)，當(dāng)消費(fèi)者P2從B1取出一件半成品時(shí)货徙，B1就空出一個(gè)空位左权，所以消費(fèi)者P2使用V(S2)釋放空間。

同理痴颊，信號量S4表示半成品箱B2當(dāng)容量赏迟，所以S4的初值為m。當(dāng)生產(chǎn)者P2完成一件產(chǎn)品放入B2時(shí)蠢棱，應(yīng)先測試B2是否有空位锌杀，所以生產(chǎn)者P2使用P(S4)，當(dāng)消費(fèi)者P3從B2取出一件產(chǎn)品時(shí)泻仙，B2就空出一個(gè)空位糕再，所以消費(fèi)者P3使用V(S4)釋放空間。

程序執(zhí)行圖如下所示：

經(jīng)典問題玉转，如：生產(chǎn)者與消費(fèi)者突想，哲學(xué)家進(jìn)餐，讀者與作家等等。

操作系統(tǒng)相關(guān)知識-死鎖-銀行家算法

死鎖：

兩個(gè)以上的進(jìn)程互相都要求對方已經(jīng)占有的資源猾担，導(dǎo)致無法繼續(xù)繼續(xù)執(zhí)行下去的現(xiàn)象袭灯。

死鎖產(chǎn)生的條件：

環(huán)路等待，互斥绑嘹，保持和等待妓蛮，不剝奪。

打破死鎖的的條件：

死鎖預(yù)防圾叼，死鎖避免，死鎖檢測捺癞，死鎖解除夷蚊。

考點(diǎn)為死鎖避免的銀行家算法：

銀行家算法：像借貸一樣，安全才審批額度髓介。

對于進(jìn)程發(fā)出的每一個(gè)系統(tǒng)可以滿足的資源請求命令加以檢測惕鼓，如果發(fā)現(xiàn)分配資源后系統(tǒng)進(jìn)入不安全狀態(tài)，則不予分配唐础。

若分配資源后系統(tǒng)仍處于安全狀態(tài)箱歧，則實(shí)施分配。

與死鎖預(yù)防相比一膨，提高了資源利用率呀邢，但檢測分配后系統(tǒng)是否安全增加了系統(tǒng)開銷。

此題的結(jié)題思路為：

先找到各資源未被分配的數(shù)量豹绪，看看哪個(gè)進(jìn)程的需求量滿足就可以執(zhí)行該進(jìn)程价淌，進(jìn)程執(zhí)行完會將該進(jìn)程的已分配資源數(shù)釋放，累加到之前未分配的數(shù)量上瞒津，繼續(xù)看哪個(gè)進(jìn)程滿足蝉衣，依次執(zhí)行。

【比如根據(jù)已分配資源得到巷蚪，R1-R3未分配的資源是2,1,0病毡；根據(jù)最大需求量，給P1資源也不夠執(zhí)行屁柏，給P2的話是可以執(zhí)行的啦膜，則P2執(zhí)行后將占有的資源釋放到未分配的資源中，繼續(xù)類推前联。小馬認(rèn)為該算法理解后不難】

存儲管理（內(nèi)存）之頁式存儲（虛擬存儲）

存儲管理

? ? ? ?操作系統(tǒng)中的存儲有很多種功戚，分別是頁式存儲，段式存儲似嗤，段頁式存數(shù)啸臀，磁盤存儲等。分這么多種存儲方式，無非是讓我們在操作計(jì)算機(jī)的時(shí)候乘粒，計(jì)算機(jī)內(nèi)存和用戶操作之間的作業(yè)變的更加清楚和簡單豌注，并且能夠保證數(shù)據(jù)不會丟失。接下來具體看下什么是頁式存儲灯萍。

基本原理：

? ? ? ?把用戶數(shù)據(jù)加載到內(nèi)存中進(jìn)行處理轧铁，這個(gè)時(shí)候就會出現(xiàn)兩種數(shù)據(jù)，一種是加載到內(nèi)存中的數(shù)據(jù)旦棉，另一種是用戶作業(yè)數(shù)據(jù)齿风，為了合理利用內(nèi)存的空間，并且使作業(yè)能夠連續(xù)绑洛，這個(gè)時(shí)候?qū)?nèi)存劃分為大小相同的塊救斑，同樣的，將用戶作業(yè)空間劃分為大小相同的頁真屯。

? ? ? ? 所以： 頁=塊（大小相同）

說明：

注意理解一個(gè)概念脸候，編程空間和頁+頁內(nèi)偏移地址? 是邏輯地址，塊號和偏移地址是 物理地址绑蔫。

p先計(jì)算每個(gè)數(shù)字（地址訪問）大小用幾位01可表示运沦。? ?B KB MB.....1024=進(jìn)制，? ? ? ? ??1字節(jié)=8bit

為什么每次要用2的幾次方來運(yùn)算配深，因?yàn)?B代表的是兩位携添，組合起來為01,10，或者11凉馆，所以當(dāng)每次計(jì)算的時(shí)候薪寓，用的就是2的冪次方來計(jì)算頁內(nèi)地址。

本題內(nèi)存16KB數(shù)字是沒用的嗎澜共？

【虛擬地址=頁號+頁內(nèi)偏移向叉；物理地址=塊號+偏移，根據(jù)邏輯地址和位數(shù) 定位頁號和偏移嗦董，根據(jù)頁表查塊號母谎，拼接偏移得物理地址。小馬覺得教材書上的那個(gè)圖比這個(gè)圖好理解】

虛設(shè)備與SPOOLing技術(shù)

為緩和CPU和高速性與I/O設(shè)備低速性的矛盾而引入了脫機(jī)輸入京革、脫機(jī)輸出技術(shù)奇唤。該技術(shù)是利用專門的外圍控制機(jī)，將低速設(shè)備上的數(shù)據(jù)傳送到高速磁盤上匹摇；或者相反咬扇。

這樣就可以在主機(jī)的直接控制下實(shí)現(xiàn)脫機(jī)輸入輸出。此時(shí)外圍操作與CPU對數(shù)據(jù)的處理同時(shí)進(jìn)行廊勃，我們把這種來聯(lián)機(jī)情況下實(shí)現(xiàn)的同時(shí)外圍操作稱為SPOOLing,或稱為假脫機(jī)操作懈贺。

SPOOLing系統(tǒng)的有三大部分組成：

輸入井和輸出井经窖。是磁盤上開辟的兩大存儲空間。

輸入緩沖區(qū)和輸出緩沖區(qū)梭灿。在內(nèi)存中開辟兩個(gè)緩沖區(qū)画侣，輸入緩沖區(qū)暫存由輸入設(shè)備送來的數(shù)據(jù)，后送輸入井來輸出緩沖區(qū)暫存從輸出井送來的數(shù)據(jù)堡妒，后送輸出設(shè)備配乱。

輸入進(jìn)程和輸出進(jìn)程。利用兩個(gè)進(jìn)程模擬脫機(jī)I/O時(shí)的外圍處理機(jī)皮迟。

SPOOLing系統(tǒng)的特點(diǎn)：

提高了I/O的速度搬泥。利用輸入輸出井模擬成脫機(jī)輸入輸出，緩和了CPU和I/O設(shè)備速度不匹配的矛盾伏尼。

將獨(dú)占設(shè)備改造成共享設(shè)備佑钾。

實(shí)現(xiàn)了虛擬設(shè)備功能。多個(gè)進(jìn)程同時(shí)使用一臺獨(dú)占設(shè)備烦粒，虛擬成了多臺設(shè)備。

【用一個(gè)類似隊(duì)列排隊(duì)的過程代赁，就可以所有進(jìn)程同時(shí)處理了】