版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
重要的知識(shí)點(diǎn):進(jìn)程與程序的差異。(1)進(jìn)程是動(dòng)態(tài)的,而程序是靜態(tài)的。(2)進(jìn)程有一定的生命期,而程序是指令的集合,本身無“運(yùn)動(dòng)”的含義。沒有建立進(jìn)程的程序不能作為1個(gè)獨(dú)立單位得到操作系統(tǒng)的認(rèn)可。(3)1個(gè)程序可以對(duì)應(yīng)多個(gè)進(jìn)程,但1個(gè)進(jìn)程只能對(duì)應(yīng)1個(gè)程序。進(jìn)程和程序的關(guān)系猶如演出和劇本的關(guān)系進(jìn)程的三種基本狀態(tài)及其狀態(tài)轉(zhuǎn)換。P.383.P、V操作的概念及如何用其實(shí)現(xiàn)同步和互斥。4處理機(jī)調(diào)度的概念。在多道程序設(shè)計(jì)系統(tǒng)中,內(nèi)存中有多道程序運(yùn)行,他們相互爭奪處理機(jī)這一重要的資源。處理機(jī)調(diào)度就是從就緒隊(duì)列中,按照一定的算法選擇一個(gè)進(jìn)程并將處理機(jī)分配給它運(yùn)行,以實(shí)現(xiàn)進(jìn)程并發(fā)地執(zhí)行。處理機(jī)調(diào)度是把處理機(jī)分配給就緒隊(duì)列中的一個(gè)進(jìn)程。在許多系統(tǒng)中,這個(gè)調(diào)度活動(dòng)分成三個(gè)層次:高級(jí)調(diào)度、中級(jí)調(diào)度和低級(jí)調(diào)度。5操作系統(tǒng)的基本特征和功能特征:1.并發(fā)性:平行性、引入進(jìn)程、引入線程2.共享性:是指系統(tǒng)中的資源可供內(nèi)存中多個(gè)并發(fā)執(zhí)行的進(jìn)程共同使用?;コ夤蚕?、同時(shí)訪問方式3.虛擬技術(shù):是指通過某種技術(shù)把一個(gè)物理實(shí)體變?yōu)槿舾蓚€(gè)邏輯上的對(duì)應(yīng)物。分為時(shí)分復(fù)用和空分復(fù)用技術(shù)。4.異步性:進(jìn)程是以人們不可預(yù)知的速度向前推進(jìn),此即進(jìn)程的異步性。功能:1.處理機(jī)管理功能:進(jìn)程控制,進(jìn)程同步,進(jìn)程通信,調(diào)度2.存儲(chǔ)器管理功能:內(nèi)存分配、內(nèi)存保護(hù)、地址映射、內(nèi)存擴(kuò)充3.設(shè)備管理功能:緩沖管理、設(shè)備分配、設(shè)備處理4.文件管理功能:文件存儲(chǔ)空間的管理、目錄管理、文件的讀/管理和保護(hù)。操作系統(tǒng)與用戶之間接口用戶接口、程序接口6當(dāng)前的高級(jí)通信機(jī)制有哪些?進(jìn)程通信分類:低級(jí)通信:特點(diǎn):交換的信息量少,僅僅是一些數(shù)據(jù)和狀態(tài)的變化;通信由程序員完成。如P,V原語實(shí)現(xiàn)的進(jìn)程互斥與同步。2、高級(jí)通信;特點(diǎn):每次交換的信息量可以很大;系統(tǒng)提供高效、簡捷的信息傳輸命令。1、共享存儲(chǔ)器系統(tǒng)(Shared-MemorySystem)共享數(shù)據(jù)結(jié)構(gòu)的通信方式:公用數(shù)據(jù)結(jié)構(gòu)的設(shè)置及對(duì)進(jìn)程間同步的管理,都是由程序員完成,效率低,傳遞數(shù)據(jù)量少;共享存儲(chǔ)區(qū)的通信方式:進(jìn)程可隨時(shí)向系統(tǒng)申請(qǐng)一塊存儲(chǔ)區(qū),并指定該區(qū)的關(guān)鍵字,用于進(jìn)程通信。2、管道通信(PipeCommunication)用以連接一個(gè)讀進(jìn)程和寫進(jìn)程以實(shí)現(xiàn)他們之間的通信的一個(gè)共享文件3、消息傳遞系統(tǒng)(MassagePassingSystem)格式化的消息為單位7在生產(chǎn)者和消費(fèi)者問題中,如果將兩個(gè)wait操作即wait(full)和wait(mutex)互換位置,或者將signal(mutex)和signal(full)互換位置,結(jié)果會(huì)如何?在生產(chǎn)者—消費(fèi)者問題中,如果將兩個(gè)wait操作,即wait(full)和wait(mutex)互換位置后,可能引起死鎖??紤]系統(tǒng)中緩沖區(qū)全滿時(shí),若一生產(chǎn)者進(jìn)程先執(zhí)行了wait(mutex)操作并獲得成功,則當(dāng)再執(zhí)行wait(empty)操作時(shí),它將因失敗而進(jìn)入阻塞狀態(tài),它期待消費(fèi)者進(jìn)程執(zhí)行signal(empty)來喚醒自己,在此之前,它不可能執(zhí)行signal(mutex)操作,從而使試圖通過執(zhí)行wait(mutex)操作而進(jìn)入自己的臨界區(qū)的其他生產(chǎn)者和所有消費(fèi)者進(jìn)程全部進(jìn)入阻塞狀態(tài),這樣容易引起系統(tǒng)死鎖。若signal(mutex)和signal(full)互換位置后只是影響進(jìn)程對(duì)臨界資源的釋放次序,而不會(huì)引起系統(tǒng)死鎖,因此可以互換位置。8操作系統(tǒng)中采用緩沖技術(shù)的目的是什么?//操作系統(tǒng)中采用緩沖技術(shù)的目的是為了增強(qiáng)系統(tǒng)并行操作的能力.1.緩和CPU與I/O設(shè)備間速度不匹配的矛盾(如打印機(jī)緩沖區(qū))。2.減少對(duì)CPU的中斷頻率,放寬對(duì)CPU中斷響應(yīng)時(shí)間的限制。3.提高CPU和I/O設(shè)備之間的并行性(加了打印機(jī)緩沖后打印機(jī)和CPU并行工作)。9SPOOLing系統(tǒng)由哪幾部分組成?以打印機(jī)為例說明如何利用SPOOLing技術(shù)實(shí)現(xiàn)多個(gè)進(jìn)程對(duì)打印機(jī)的共享。SPOOling系統(tǒng)的組成:SPOOLIng系統(tǒng)是對(duì)脫機(jī)I/O工作的模擬,其必須有高速隨機(jī)外存(通常采用磁盤)的支持SPOOLING系統(tǒng)有以下四個(gè)部分:1.輸入井和輸出井,為磁盤上開辟的兩大存儲(chǔ)空間,分別模擬脫機(jī)輸入/出時(shí)的磁盤并用于收容I/O設(shè)備輸入的數(shù)據(jù)和用戶程序的輸出數(shù)據(jù)2.輸入緩沖區(qū)和輸出緩沖區(qū),在內(nèi)存中開辟,分別用于暫停由輸入設(shè)備和輸出井送來的數(shù)據(jù)3.輸入進(jìn)程SPi和輸出進(jìn)程SP0分別模擬脫機(jī)輸入/出時(shí)的外圍控制機(jī),用于控制I/O過程4.I/O請(qǐng)求隊(duì)列,由系統(tǒng)為各個(gè)I/O請(qǐng)求進(jìn)程建立的I/O請(qǐng)求表構(gòu)成的隊(duì)列.廉價(jià)磁盤冗余陣列:利用一臺(tái)磁盤陣列控制器,來統(tǒng)一管理和控制一組磁盤驅(qū)動(dòng)器,組成一個(gè)高度可靠的快速的大容量磁盤系統(tǒng)??1輸入井和輸出井2輸入緩沖區(qū)和輸出緩沖區(qū)3輸入進(jìn)程SPi和輸出進(jìn)程SPo4I/O請(qǐng)求隊(duì)列10外存文件區(qū)的管理應(yīng)以什么為主要目標(biāo)?對(duì)外存對(duì)換區(qū)的管理應(yīng)以提高換入換出速度為主要目標(biāo),對(duì)外存文件區(qū)的管理應(yīng)以提高存儲(chǔ)空間的利用率為主要目標(biāo)。11什么是FCB,它包含哪些信息,作用?操作系統(tǒng)為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu),存放了為管理文件所需的所有有關(guān)信息。文件與文件控制塊一一對(duì)應(yīng)。文件控制塊是文件存在的標(biāo)志。一個(gè)FCB就是目錄表中的一個(gè)目錄項(xiàng)?;拘畔⑽募簶?biāo)識(shí)一個(gè)文件的符號(hào)名。文件物理位置:文件在外存上的存儲(chǔ)位置,包括存放文件的設(shè)備名、起始盤塊號(hào)、占用的盤塊數(shù)文件邏輯結(jié)構(gòu):流式文件還是記錄式文件、記錄數(shù);定長記錄還是變長記錄等。文件的物理結(jié)構(gòu):指示文件是順序文件,還是鏈接式文件或索引文件等。存取控制信息類:文件主的存取權(quán)限、核準(zhǔn)用戶的存取權(quán)限以及一般用戶的存取權(quán)限。使用信息類:文件的建立日期和時(shí)間、文件上一次修改的日期和時(shí)間及當(dāng)前使用信息(如已打開該文件的進(jìn)程數(shù)、是否被其它進(jìn)程鎖住、文件在內(nèi)存中是否已被修改但尚未拷貝到盤上。)12什么是地址變換?如是是操作系統(tǒng)的存儲(chǔ)器管理,則是(1)保護(hù)方式的地址轉(zhuǎn)換:處理器內(nèi)部的分段單元將邏輯地址轉(zhuǎn)換為線性地址,再由分頁單元將線性地址轉(zhuǎn)換為物理地址,物理地址通過地址總線輸出選擇存儲(chǔ)器芯片中的具體存儲(chǔ)單元。(2)實(shí)地址方式的地址轉(zhuǎn)換:實(shí)地址方式采用實(shí)地址存儲(chǔ)模型,注意其的主存空間只有1MB=220字節(jié)),僅使用地址總線的低20位,其物理地址范圍為00000H~FFFFFH。實(shí)地址存儲(chǔ)模型也進(jìn)行分段管理,但有兩個(gè)限制:?每個(gè)段最大為64KB?段只能開始于低4位地址全為0的物理地址處實(shí)地址方式的段寄存器直接保存20位段基地址的高16位,段內(nèi)的偏移地址也用16位表示。這樣將邏輯地址轉(zhuǎn)換為物理地址的方法是:將段寄存器中的數(shù)值左移二進(jìn)制4位(十六進(jìn)制一位),加上偏移地址就得到20位物理地址?;镜刂纷儞Q機(jī)制塊表地址變換機(jī)制13設(shè)備和內(nèi)存間的數(shù)據(jù)傳送控制方式有幾種?程序I/O方式中斷驅(qū)動(dòng)I/O控制方式直接存儲(chǔ)器訪問控制方式I/O通道控制方式14銀行家算法某系統(tǒng)中有10臺(tái)打印機(jī),有三個(gè)進(jìn)程P1P2P3分別需要8臺(tái)7臺(tái)4臺(tái)若P1P2,P3已申請(qǐng)到4臺(tái),2臺(tái)和2臺(tái)。試問:按銀行家算法能安全分配嗎?答:申請(qǐng)后系統(tǒng)把2臺(tái)機(jī)分配給p3,p3完成后釋放所有的資源4,再分配給p1,p1完成后釋放8,再分配給p2安全狀態(tài):指體統(tǒng)能按著某種進(jìn)程順序(p1,p2,...pu)來為每個(gè)進(jìn)程pi分配其所需資源,知道滿足每個(gè)進(jìn)程對(duì)資源的最大需求,是每個(gè)進(jìn)程都可順利的完成15分頁和分段存儲(chǔ)管理方式的地址轉(zhuǎn)換(邏輯地址轉(zhuǎn)換為物理地址),見PPT中的內(nèi)容。16給出一個(gè)進(jìn)程序列,會(huì)計(jì)算采用先來先服務(wù)、時(shí)間片輪轉(zhuǎn)(q為輪轉(zhuǎn)的時(shí)間片)調(diào)度算法的平均周轉(zhuǎn)時(shí)間、平均帶權(quán)周轉(zhuǎn)時(shí)間。(見教材92的表)17會(huì)計(jì)算FIFO、LRU兩種置換算法的缺頁次數(shù)。18死鎖產(chǎn)生的必要條件是什么?互斥條件;2.請(qǐng)求和保持條件;3.不剝奪條件;4.環(huán)路等待條件。生產(chǎn)者—消費(fèi)者問題1.利用記錄型信號(hào)量解決生產(chǎn)者—消費(fèi)者問題假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖池中,具有n個(gè)緩沖區(qū),這時(shí)可利用互斥信號(hào)量mutex實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖池的互斥使用;利用信號(hào)量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費(fèi)者相互等效,只要緩沖池未滿,生產(chǎn)者便可將消息送入緩沖池;只要緩沖池未空,消費(fèi)者便可從緩沖池中取走一個(gè)消息。Varmutex,empty,full:semaphore∶=1,n,0;buffer:array[0,…,n-1]ofitem;in,out:integer∶=0,0;beginparbeginproceducer:beginrepeat…produceranitemnextp;…wait(empty);wait(mutex);buffer(in)∶=nextp;in∶=(in+1)modn;signal(mutex);signal(full);untilfalse;endconsumer:beginrepeatwait(full);wait(mutex);nextc∶=buffer(out);out∶=(out+1)modn;signal(mutex);signal(empty);consumertheiteminnextc;untilfalse;endparendend在生產(chǎn)者—消費(fèi)者問題中應(yīng)注意:首先,在每個(gè)程序中用于實(shí)現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對(duì)地出現(xiàn);其次,對(duì)資源信號(hào)量empty和full的wait和signal操作,同樣需要成對(duì)地出現(xiàn),但它們分別處于不同的程序中。例如,wait(empty)在計(jì)算進(jìn)程中,而signal(empty)則在打印進(jìn)程中,計(jì)算進(jìn)程若因執(zhí)行wait(empty)而阻塞,則以后將由打印進(jìn)程將它喚醒;最后,在每個(gè)程序中的多個(gè)wait操作順序不能顛倒。應(yīng)先執(zhí)行對(duì)資源信號(hào)量的wait操作,然后再執(zhí)行對(duì)互斥信號(hào)量的wait操作,否則可能引起進(jìn)程死鎖。利用管程解決生產(chǎn)者——消費(fèi)者問題(1)put(item)過程。生產(chǎn)者利用該進(jìn)程將自己生成的產(chǎn)品投入到緩沖池中,并用整型變量count來表示在緩沖池中已有的產(chǎn)品數(shù)目,當(dāng)count>=n時(shí),表示緩沖池已滿。生產(chǎn)者等待。(2)get(item)過程。消費(fèi)者利用該進(jìn)程從緩沖池中取出一個(gè)產(chǎn)品,當(dāng)count<=0時(shí),表示緩沖池中已無可取用的產(chǎn)品,消費(fèi)者等待。PC管程可描述如下:typeproducer-consumer=monitorvarin,out,count:integer;buffer:array[0,….,n-1]ofitemnotfull,notempty:condition;procedureentryput(item)beginifcount>=0thennotfull.wait;buffer(in):=nextp;in:=(in+1)modn;count:=count+1;ifnotempty.queuethennotempty.signal;endprocedureentryget(item)beginifcount<=0thennotempty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1;ifnotfull.queuethennotfull.signalendbeginin:=out:=0count:=0end利用管程解決生產(chǎn)者——消費(fèi)者問題時(shí)。produce:beginrepeatproduceaniteminnextpPC.put(item)unitlfalse;endconsumer:beginrepeatPC.get(item)consumertheiteminnextcunitlfalse;endPV原語的含義
P操作和V操作是不可中斷的程序段,稱為原語。PV原語及信號(hào)量的概念都是由荷蘭科學(xué)家E.W.Dijkstra提出的。信號(hào)量sem是一整數(shù),sem大于等于零時(shí)代表可供并發(fā)進(jìn)程使用的資源實(shí)體數(shù),但sem小于零時(shí)則表示正在等待使用臨界區(qū)的進(jìn)程數(shù)。
P原語操作的動(dòng)作是:
(1)sem減1;
(2)若sem減1后仍大于或等于零,則進(jìn)程繼續(xù)執(zhí)行;
(3)若sem減1后小于零,則該進(jìn)程被阻塞后進(jìn)入與該信號(hào)相對(duì)應(yīng)的隊(duì)列中,然后轉(zhuǎn)進(jìn)程調(diào)度。
V原語操作的動(dòng)作是:
(1)sem加1;
(2)若相加結(jié)果大于零,則進(jìn)程繼續(xù)執(zhí)行;
(3)若相加結(jié)果小于或等于零,則從該信號(hào)的等待隊(duì)列中喚醒一等待進(jìn)程,然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。
PV操作對(duì)于每一個(gè)進(jìn)程來說,都只能進(jìn)行一次,而且必須成對(duì)使用。在PV原語執(zhí)行期間不允許有中斷的發(fā)生。
用PV原語實(shí)現(xiàn)進(jìn)程的互斥
由于用于互斥的信號(hào)量sem與所有的并發(fā)進(jìn)程有關(guān),所以稱之為公有信號(hào)量。公有信號(hào)量的值反映了公有資源的數(shù)量。只要把臨界區(qū)置于P(sem)和V(sem)之間,即可實(shí)現(xiàn)進(jìn)程間的互斥。就象火車中的每節(jié)車廂只有一個(gè)衛(wèi)生間,該車廂的所有旅客共享這個(gè)公有資源:衛(wèi)生間,所以旅客間必須互斥進(jìn)入衛(wèi)生間,只要把衛(wèi)生間放在P(sem)和V(sem)之間,就可以到達(dá)互斥的效果。以下例子說明進(jìn)程的互斥實(shí)現(xiàn)。
例1
生產(chǎn)圍棋的工人不小心把相等數(shù)量的黑子和白子混裝載一個(gè)箱子里,現(xiàn)要用自動(dòng)分揀系統(tǒng)把黑子和白子分開,該系統(tǒng)由兩個(gè)并發(fā)執(zhí)行的進(jìn)程組成,功能如下:
(1)進(jìn)程A專門揀黑子,進(jìn)程B專門揀白子;
(2)每個(gè)進(jìn)程每次只揀一個(gè)子,當(dāng)一個(gè)進(jìn)程在揀子時(shí)不允許另一個(gè)進(jìn)程去揀子;
分析:
第一步:確定進(jìn)程間的關(guān)系。由功能(2)可知進(jìn)程之間是互斥的關(guān)系。
第二步:確定信號(hào)量及其值。由于進(jìn)程A和進(jìn)程B要互斥進(jìn)入箱子去揀棋子,箱子是兩個(gè)進(jìn)程的公有資源,所以設(shè)置一個(gè)信號(hào)量s,其值取決于公有資源的數(shù)目,由于箱子只有一個(gè),s的初值就設(shè)為1。
實(shí)現(xiàn):
begin
s:semaphore;
s:=1;
cobegin
processA
begin
L1:P(s);
揀黑子;
V(s);
gotoL1;
end;
processB
begin
L2:P(s);
揀白子;
V(s);
gotoL2;
end;
coend;
end;
判斷進(jìn)程間是否互斥,關(guān)鍵是看進(jìn)程間是否共享某一公有資源,一個(gè)公有資源與一個(gè)信號(hào)量相對(duì)應(yīng)。確定信號(hào)量的值是一個(gè)關(guān)鍵點(diǎn),它代表了可用資源實(shí)體數(shù)。如下實(shí)例:
例2
某車站售票廳,任何時(shí)刻最多可容納20名購票者進(jìn)入,當(dāng)售票廳中少于20名購票者時(shí),廳外的購票者可立即進(jìn)入,否則需要在外面等待。每個(gè)購票者可看成一個(gè)進(jìn)程。
分析:第一步:確定進(jìn)程間的關(guān)系。售票廳是各進(jìn)程共享的公有資源,當(dāng)售票廳中多于20名購票者時(shí),廳外的購票者需要在外面等待。所以進(jìn)程間是互斥的關(guān)系。第二步:確定信號(hào)量及其值。只有一個(gè)公有資源:售票廳,所以設(shè)置一個(gè)信號(hào)量s。售票廳最多容納20個(gè)進(jìn)程,即可用資源實(shí)體數(shù)為20,s的初值就設(shè)為20。
實(shí)現(xiàn):
begin
s:semaphore;
s:=20;
cobegin
processPI(I=1,2,……)
beginP(s);
進(jìn)入售票廳;
購票;
退出;
V(s);
end;
coend
當(dāng)購票者進(jìn)入售票廳前要執(zhí)行P(s)操作,執(zhí)行后若s大于或等于零,說明售票廳的人數(shù)還未滿可進(jìn)入。執(zhí)行后若s小于零,則說明售票廳的人數(shù)已滿不能進(jìn)入。這個(gè)實(shí)現(xiàn)中同時(shí)最多允許20個(gè)進(jìn)程進(jìn)入售票廳購票,其余進(jìn)程只能等待。
用PV原語實(shí)現(xiàn)進(jìn)程的同步
與進(jìn)程互斥不同,進(jìn)程同步時(shí)的信號(hào)量只與制約進(jìn)程及被制約進(jìn)程有關(guān)而不是與整組并發(fā)進(jìn)程有關(guān),所以稱該信號(hào)量為私有信號(hào)量。利用PV原語實(shí)現(xiàn)進(jìn)程同步的方法是:首先判斷進(jìn)程間的關(guān)系為同步的,且為各并發(fā)進(jìn)程設(shè)置私有信號(hào)量,然后為私有信號(hào)量賦初值,最后利用PV原語和私有信號(hào)量規(guī)定各進(jìn)程的執(zhí)行順序。下面我們將例1增添一個(gè)條件,使其成為進(jìn)程間是同步的。
例3
在例1的基礎(chǔ)之上再添加一個(gè)功能:
(3)當(dāng)一個(gè)進(jìn)程揀了一個(gè)棋子(黑子或白子)以后,必讓另一個(gè)進(jìn)程揀一個(gè)棋子(黑子或白子)。
分析:
第一步:確定進(jìn)程間的關(guān)系。由功能(1)(2)(3)可知,進(jìn)程間的關(guān)系為同步關(guān)系。第二步:確定信號(hào)量及其值。進(jìn)程A和B共享箱子這個(gè)公有資源,但規(guī)定兩個(gè)進(jìn)程必須輪流去取不同色的棋子,因而相互間要互通消息。對(duì)于進(jìn)程A可設(shè)置一個(gè)私有信號(hào)量s1,該私有信號(hào)量用于判斷進(jìn)程A是否能去揀黑子,初值為1。對(duì)于進(jìn)程B同樣設(shè)置一個(gè)私有信號(hào)量s2,該私有信號(hào)量用于判斷進(jìn)程B是否能去揀白子,初值為0。當(dāng)然你也可以設(shè)置s1初值為0,s2初值為1。
實(shí)現(xiàn):
begin
s1,s2:semaphore;
s1:=1;s2:=0;
cobegin
processA
begin
L1:P(s1);
揀黑子;
V(s2);
gotoL1;
end;
processB
begin
L2:P(s2);
揀白子;
V(s1);
gotoL2;
end;
coend;
end;
另外一個(gè)問題就是P原語是不是一定在V原語的前面?回答是否定的。下面看一個(gè)例子。
例4
設(shè)在公共汽車上,司機(jī)和售票員的活動(dòng)分別是:司機(jī):啟動(dòng)車輛,正常行車,到站停車。售票員:上乘客,關(guān)車門,售票,開車門,下乘客。用PV操作對(duì)其控制。
分析:
第一步:確定進(jìn)程間的關(guān)系。司機(jī)到站停車后,售票員方可工作。同樣,售票員關(guān)車門后,司機(jī)才能工作。所以司機(jī)與售票員之間是一種同步關(guān)系。
第二步:確定信號(hào)量及其值。由于司機(jī)與售票員之間要互通消息,司機(jī)進(jìn)程設(shè)置一個(gè)私有信號(hào)量run,用于判斷司機(jī)能否進(jìn)行工作,初值為0。售票員進(jìn)程設(shè)置一個(gè)私有信號(hào)量stop,用于判斷是否停車,售票員是否能夠開車門,初值為0。
實(shí)現(xiàn):
beginstop,run:semaphore
stop:=0;run:=0;
cobegin
driver:begin
L1:P(run);
啟動(dòng)車輛;
正常行車;
到站停車;
V(stop);
goto
L1;
end;
conductor:begin
L2:上乘客;
關(guān)車門;
V(run);
售票;
P(stop);
開車門;
下乘客;
gotoL2;
end;
coend;
end;
用PV操作還可以實(shí)現(xiàn)進(jìn)程同步與互斥的混合問題,典型的如:多個(gè)生產(chǎn)者和多個(gè)消費(fèi)者共享容量為n的緩存區(qū)。這個(gè)例子在很多書中都有介紹,在這里就不說了。PV原語PV原語通過操作信號(hào)量來處理進(jìn)程間的同步與互斥的問題。其核心就是一段不可分割不可中斷的程序。信號(hào)量的概念1965年由著名的荷蘭計(jì)算機(jī)科學(xué)家Dijkstra提出,其基本思路是用一種新的變量類型(semaphore)來記錄當(dāng)前可用資源的數(shù)量。有兩種實(shí)現(xiàn)方式:1)semaphore的取值必須大于或等于0。0表示當(dāng)前已沒有空閑資源,而正數(shù)表示當(dāng)前空閑資源的數(shù)量;2)semaphore的取值可正可負(fù),負(fù)數(shù)的絕對(duì)值表示正在等待進(jìn)入臨界區(qū)的進(jìn)程個(gè)數(shù)。信號(hào)量是由操作系統(tǒng)來維護(hù)的,用戶進(jìn)程只能通過初始化和兩個(gè)標(biāo)準(zhǔn)原語(P、V原語)來訪問。初始化可指定一個(gè)非負(fù)整數(shù),即空閑資源總數(shù)。P原語:P是荷蘭語Proberen(測試)的首字母。為阻塞原語,負(fù)責(zé)把當(dāng)前進(jìn)程由運(yùn)行狀態(tài)轉(zhuǎn)換為阻塞狀態(tài),直到另外一個(gè)進(jìn)程喚醒它。操作為:申請(qǐng)一個(gè)空閑資源(把信號(hào)量減1),若成功,則退出;若失敗,則該進(jìn)程被阻塞;V原語:V是荷蘭語Verhogen(增加)的首字母。為喚醒原語,負(fù)責(zé)把一個(gè)被阻塞的進(jìn)程喚醒,它有一個(gè)參數(shù)表,存放著等待被喚醒的進(jìn)程信息。操作為:釋放一個(gè)被占用的資源(把信號(hào)量加1),如果發(fā)現(xiàn)有被阻塞的進(jìn)程,則選擇一個(gè)喚醒之。具體PV原語對(duì)信號(hào)量的操作可以分為三種情況:1)把信號(hào)量視為一個(gè)加鎖標(biāo)志位,實(shí)現(xiàn)對(duì)一個(gè)共享變量的互斥訪問。
實(shí)現(xiàn)過程:
P(mutex);//mutex的初始值為1訪問該共享數(shù)據(jù);
V(mutex);
非臨界區(qū)2)把信號(hào)量視為是某種類型的共享資源的剩余個(gè)數(shù),實(shí)現(xiàn)對(duì)一類共享資源的訪問。
實(shí)現(xiàn)過程:
P(resource);//resource的初始值為該資源的個(gè)數(shù)N使用該資源;
V(resource);非臨界區(qū)3)把信號(hào)量作為進(jìn)程間的同步工具
實(shí)現(xiàn)過程:
臨界區(qū)C1;
P(S);
V(S);
臨界區(qū)C2;PV原語操作信號(hào)量
信號(hào)量是最早出現(xiàn)的用來解決進(jìn)程同步與互斥問題的機(jī)制,包括一個(gè)稱為信號(hào)量的變量及對(duì)它進(jìn)行的兩個(gè)原語操作。
本節(jié)將從以下幾個(gè)方面進(jìn)行介紹--
--------------------------------------------------------------------------------一.信號(hào)量的概念
1.信號(hào)量的類型定義
2.PV原語--------------------------------------------------------------------------------二.實(shí)例
1.生產(chǎn)者-消費(fèi)者問題(有buffer)
2.第一類讀-寫者問題
3.哲學(xué)家問題--------------------------------------------------------------------------------一.信號(hào)量的概念
1.信號(hào)量的類型定義
每個(gè)信號(hào)量至少須記錄兩個(gè)信息:信號(hào)量的值和等待該信號(hào)量的進(jìn)程隊(duì)列。它的類型定義如下:(用類PASCAL語言表述)semaphore=recordvalue:integer;queue:^PCB;end;其中PCB是進(jìn)程控制塊,是操作系統(tǒng)為每個(gè)進(jìn)程建立的數(shù)據(jù)結(jié)構(gòu)。s.value>=0時(shí),s.queue為空;s.value<0時(shí),s.value的絕對(duì)值為s.queue中等待進(jìn)程的個(gè)數(shù);
返回--------------------------------------------------------------------------------2.PV原語
對(duì)一個(gè)信號(hào)量變量可以進(jìn)行兩種原語操作:p操作和v操作,定義如下:procedurep(vars:samephore);{s.value=s.value-1;if(s.value<0)asleep(s.queue);}procedurev(vars:samephore);{s.value=s.value+1;if(s.value<=0)wakeup(s.queue);}其中用到兩個(gè)標(biāo)準(zhǔn)過程:asleep(s.queue);執(zhí)行此操作的進(jìn)程的PCB進(jìn)入s.queue尾部,進(jìn)程變成等待狀態(tài)wakeup(s.queue);將s.queue頭進(jìn)程喚醒插入就緒隊(duì)列s.value初值為1時(shí),可以用來實(shí)現(xiàn)進(jìn)程的互斥。p操作和v操作是不可中斷的程序段,稱為原語。如果將信號(hào)量看作共享變量,則pv操作為其臨界區(qū),多個(gè)進(jìn)程不能同時(shí)執(zhí)行,一般用硬件方法保證。一個(gè)信號(hào)量只能置一次初值,以后只能對(duì)之進(jìn)行p操作或v操作。由此也可以看到,信號(hào)量機(jī)制必須有公共內(nèi)存,不能用于分布式操作系統(tǒng),這是它最大的弱點(diǎn)。
返回--------------------------------------------------------------------------------二.實(shí)例
1.生產(chǎn)者-消費(fèi)者問題(有buffer)
問題描述:一個(gè)倉庫可以存放K件物品。生產(chǎn)者每生產(chǎn)一件產(chǎn)品,將產(chǎn)品放入倉庫,倉庫滿了就停止生產(chǎn)。消費(fèi)者每次從倉庫中去一件物品,然后進(jìn)行消費(fèi),倉庫空時(shí)就停止消費(fèi)。解答:進(jìn)程:Producer-生產(chǎn)者進(jìn)程,Consumer-消費(fèi)者進(jìn)程共有的數(shù)據(jù)結(jié)構(gòu):buffer:array[0..k-1]ofinteger;in,out:0..k-1;—in記錄第一個(gè)空緩沖區(qū),out記錄第一個(gè)不空的緩沖區(qū)s1,s2,mutex:semaphore;—s1控制緩沖區(qū)不滿,s2控制緩沖區(qū)不空,mutex保護(hù)臨界區(qū);初始化s1=k,s2=0,mutex=1producer(生產(chǎn)者進(jìn)程):Item_Typeitem;{while(true){produce(&item);p(s1);p(mutex);buffer[in]:=item;in:=(in+1)modk;v(mutex);v(s2);}}consumer(消費(fèi)者進(jìn)程):Item_Typeitem;{while(true){p(s2);p(mutex);item:=buffer[out];out:=(out+1)modk;v(mutex);v(s1);consume(&item);}}例程演示
返回--------------------------------------------------------------------------------2.第一類讀-寫者問題
問題描述:一些讀者和一些寫者對(duì)同一個(gè)黑板進(jìn)行讀寫。多個(gè)讀者可同時(shí)讀黑板,但一個(gè)時(shí)刻只能有一個(gè)寫者,讀者寫者不能同時(shí)使用黑板。對(duì)使用黑板優(yōu)先級(jí)的不同規(guī)定使讀者-寫者問題又可分為幾類。第一類問題規(guī)定讀者優(yōu)先級(jí)較高,僅當(dāng)無讀者時(shí)允許寫者使用黑板。解答:進(jìn)程:writer-寫者進(jìn)程,reader-讀者進(jìn)程共有的數(shù)據(jù)結(jié)構(gòu):read_account:integer;r_w,mutex:semaphore;—r_w控制誰使用黑板,mutex保護(hù)臨界區(qū),初值都為1reader-(讀者進(jìn)程):{while(true){p(mutex);read_account++;if(read_account=1)p(r_w);v(mutex);read();p(mutex);read_account--;if(read_account=0)v(r_w);;v(mutex);}}writer-(寫者進(jìn)程):{while(true){p(mutex);write();v(mutex);}}例程演示
返回--------------------------------------------------------------------------------3.哲學(xué)家問題
問題描述:一個(gè)房間內(nèi)有5個(gè)哲學(xué)家,他們的生活就是思考和進(jìn)食。房間里有一張圓桌,中間放著一盤通心粉(假定通心粉無限多)。桌子周圍放有五把椅子,分別屬于五位哲學(xué)家每兩位哲學(xué)家之間有一把叉子,哲學(xué)家進(jìn)食時(shí)必須同時(shí)使用左右兩把叉子。解答:進(jìn)程:philosopher-哲學(xué)家共有的數(shù)據(jù)結(jié)構(gòu)&過程:state:array[0..4]of(think,hungry,eat);ph:array[0..4]ofsemaphore;—每個(gè)哲學(xué)家有一個(gè)信號(hào)量,初值為0mutex:semaphore;—mutex保護(hù)臨界區(qū),初值=1proceduretest(i:0..4);{if((state[i]=hungry)and(state[(i+1)mod5]<>eating)and(state[(i-1)mod5]<>eating)){state[i]=eating;V(ph[i]);}}philosopher(i:0..4):{while(true){think();p(mutex);state[i]=hungry;test(i);v(mutex);p(ph[i]);eat();p(mutex);state[i]=think;test((i-1)mod5);test((i+1)mod5);v(mutex);}}PV原語-2004上半年上午試題
若有一個(gè)倉庫,可以存放P1、P2兩種產(chǎn)品,但是每次只能存放一種產(chǎn)品.要求:
①w=P1的數(shù)量-P2的數(shù)量
②-i<w<k(i、k為正整數(shù))
若用PV操作實(shí)現(xiàn)P1和P2產(chǎn)品的入庫過程,至少需要__(23)__個(gè)同步信號(hào)量及__(24)__個(gè)互斥信號(hào)量,其中,同步信號(hào)量的初值分別為__(25)__,互斥信號(hào)量的初值分別為__(26)__。
(23)A.0B.1C.2D.3
(24)A.0B.1C.2D.3
(25)A.0B.i,k,0C.i,kD.i-1,k-1
(26)A.1B.1,1C.1,1,1D.i,k答案是CBDA系分考試知識(shí):PV操作釋疑信號(hào)量
信號(hào)量是最早出現(xiàn)的用來解決進(jìn)程同步與互斥問題的機(jī)制,
包括一個(gè)稱為信號(hào)量的變量及對(duì)它進(jìn)行的兩個(gè)原語操作。
一.信號(hào)量的概念
1.信號(hào)量的類型定義
每個(gè)信號(hào)量至少須記錄兩個(gè)信息:信號(hào)量的值和等待該信號(hào)量的進(jìn)程隊(duì)列。它的類型定義如下:(用類PASCAL語言表述)
semaphore=record
value:integer;
queue:^PCB;
end;
其中PCB是進(jìn)程控制塊,是操作系統(tǒng)為每個(gè)進(jìn)程建立的數(shù)據(jù)結(jié)構(gòu)。
s.value>=0時(shí),s.queue為空;
s.value<0時(shí),s.value的絕對(duì)值為s.queue中等待進(jìn)程的個(gè)數(shù);
2.PV原語
對(duì)一個(gè)信號(hào)量變量可以進(jìn)行兩種原語操作:p操作和v操作,定義如下:
procedurep(vars:samephore);
{
s.value=s.value-1;
if(s.value<0)asleep(s.queue);
}
procedurev(vars:samephore);
{
s.value=s.value+1;
if(s.value<=0)wakeup(s.queue);
}其中用到兩個(gè)標(biāo)準(zhǔn)過程:
asleep(s.queue);執(zhí)行此操作的進(jìn)程的PCB進(jìn)入s.queue尾部,進(jìn)程變成等待狀態(tài)wakeup(s.queue);將s.queue頭進(jìn)程喚醒插入就緒隊(duì)列
s.value初值為1時(shí),可以用來實(shí)現(xiàn)進(jìn)程的互斥。
p操作和v操作是不可中斷的程序段,稱為原語。如果將信號(hào)量看作共享變量,則pv操作為其臨界區(qū),多個(gè)進(jìn)程不能同時(shí)執(zhí)行,一般用硬件方法保證。一個(gè)信號(hào)量只能置一次初值,以后只能對(duì)之進(jìn)行p操作或v操作。
由此也可以看到,信號(hào)量機(jī)制必須有公共內(nèi)存,不能用于分布式操作系統(tǒng),這是它最大的弱點(diǎn)。
V原語的主要操作是:
(1)sem加1;
(2)若相加結(jié)果大于零,則進(jìn)程繼續(xù)執(zhí)行;
(3)若相加結(jié)果小于或等于零,則喚醒一阻塞在該信號(hào)量上的進(jìn)程,然后再返回原進(jìn)程繼續(xù)執(zhí)行或轉(zhuǎn)進(jìn)程調(diào)度。
典型理解偏差:
一,以V原語的1、2步來做,Sem不就永遠(yuǎn)大于0,那進(jìn)程不就一直循環(huán)執(zhí)行成為死循環(huán)了?
二,Sem大于0那就表示有臨界資源可供使用,為什么不喚醒進(jìn)程?
三,Sem小于0應(yīng)該是說沒有臨界資源可供使用,為什么還要喚醒進(jìn)程?
析疑:一,P操作對(duì)sem減1的。P、V原語必須成對(duì)使用!從而不會(huì)造成死循環(huán)。二,Sem大于0的確表示有臨界資源可供使用,而且這個(gè)時(shí)候沒有進(jìn)程被阻塞在這個(gè)資源上,也就是說沒有進(jìn)程因?yàn)榈貌坏竭@類資源而阻塞,所以沒有被阻塞的進(jìn)程,自然不需要喚醒。三,V原語操作的本質(zhì)在于:一個(gè)進(jìn)程使用完臨界資源后,釋放臨界資源,使Sem加1,以通知其它的進(jìn)程,這個(gè)時(shí)候如果Sem<0,表明有進(jìn)程阻塞在該類資源上,因此要從阻塞隊(duì)列里喚醒一個(gè)進(jìn)程來“轉(zhuǎn)手”該類資源。比如,有2個(gè)某類資源,三個(gè)進(jìn)程A、B、C、D要用該類資源,最開始Sem=2,當(dāng)A進(jìn)入,Sem=1,當(dāng)B進(jìn)入Sem=0,表明該類資源剛好用完,當(dāng)C進(jìn)入時(shí)Sem=-1,表明有一個(gè)進(jìn)程被阻塞了,D進(jìn)入,Sem=-2。當(dāng)A用完該類資源時(shí),進(jìn)行V操作,Sem=-1,釋放該類資源,而這時(shí)Sem<0,表明有進(jìn)程阻塞在該類資源上,于是喚醒一個(gè)。
為了進(jìn)一步加深理解,再引入二個(gè)問題:四,如果是互斥信號(hào)量的話,應(yīng)該設(shè)置信號(hào)量Sen=1,但是當(dāng)有5個(gè)進(jìn)程都訪問的話,最后在該信號(hào)量的鏈表里會(huì)有4個(gè)在等待,也是說S=-4,那么第一個(gè)進(jìn)程執(zhí)行了V操作使S加1,釋放了資源,下一個(gè)應(yīng)該能夠執(zhí)行,但喚醒的這個(gè)進(jìn)程在執(zhí)行P操作時(shí)因S〈0,也還是執(zhí)行不了,這是怎么回事呢?五,Sem的絕對(duì)值表示等待的進(jìn)程數(shù),同時(shí)又表示臨界資源,這到底是怎么回事?析疑:四,當(dāng)一個(gè)進(jìn)程阻塞了的時(shí)候,它已經(jīng)執(zhí)行過了P操作,并卡在臨界區(qū)那個(gè)地方。當(dāng)喚醒它時(shí)就立即進(jìn)入它自己的臨界區(qū),并不需要執(zhí)行P操作了,當(dāng)執(zhí)行完了臨界區(qū)的程序后,就執(zhí)行V操作。五,當(dāng)信號(hào)量Sem小于0時(shí),其絕對(duì)值表示系統(tǒng)中因請(qǐng)求該類資源而被阻塞的進(jìn)程數(shù)目.S大于0時(shí)表示可用的臨界資源數(shù)。注意在不同情況下所表達(dá)的含義不一樣。當(dāng)?shù)扔?時(shí),表示剛好用完。吸煙者問題(Patil,1971)
三個(gè)吸煙者在一間房間內(nèi),還有一個(gè)香煙供應(yīng)者。為了制造并抽掉香煙,每個(gè)吸煙者需要三樣?xùn)|西:煙草、紙和火柴。供應(yīng)者有豐富的貨物提供。三個(gè)吸煙者中,第一個(gè)有自己的煙草,第二個(gè)有自己的紙,第三個(gè)有自己的火柴。供應(yīng)者將兩樣?xùn)|西放在桌子上,允許一個(gè)吸煙者進(jìn)行對(duì)健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者,供應(yīng)者再放兩樣?xùn)|西(隨機(jī)地)在桌面上,然后喚醒另一個(gè)吸煙者。試為吸煙者和供應(yīng)者編寫程序解決問題。分析思想:
1)供應(yīng)者seller隨即產(chǎn)生兩樣?xùn)|西,提供它們,這里用普通變量來表示
2)吸煙者進(jìn)程smoker根據(jù)其排號(hào)不同,擁有不同的一件東西。假設(shè)1號(hào)吸煙者擁有煙草tobacco,2號(hào)吸煙者擁有紙paper,3號(hào)吸煙者擁有火柴match。其他號(hào)碼錯(cuò)誤返回。
3)吸煙者的序號(hào)代表他們擁有的東西,用他們的序號(hào)和供應(yīng)者產(chǎn)生的兩樣?xùn)|西比較,如果都不相等,則說明他擁有的東西和供應(yīng)者產(chǎn)生的東西匹配,它可以吸煙。如果其中一個(gè)相等,則推出,繼續(xù)排隊(duì)。
4)mutex信息量代表一個(gè)只能進(jìn)入的門,每次只有一個(gè)吸煙者可以進(jìn)入進(jìn)行比較和吸煙。
5)每個(gè)吸煙者在吸煙完畢之后出門之前要叫醒供應(yīng)者,調(diào)用seller進(jìn)程。信息量:
mutex:=1——互斥信息量,表示吸煙者進(jìn)入的門解法:
#typedefintsemaphore
semaphoremutex=1;
intthing1,thing2;voidseller(){
Randomize;
inti=random(2);
//產(chǎn)生0-2的隨機(jī)數(shù)
thing1=((i-1)%3)+1;//將thing賦值為0-2種不等于i的兩個(gè)數(shù)+1
thing2=((i+1)%3)+1;
}
voidsmoker(inti){
if((i<=0)||(i>3))
//i值應(yīng)為1-3
returnfalse;
while(true){
P(mutex)
if((i!=thing1)&&(i!=thing2)){//所擁有的物品與供應(yīng)者放出的物品不一樣
吸煙;
seller();
//喚醒供應(yīng)者
V(mutex);
}
else{
V(mutex)
}//endif
}//
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 廣東科貿(mào)職業(yè)學(xué)院《生理藥理學(xué)》2023-2024學(xué)年第一學(xué)期期末試卷
- 廣東警官學(xué)院《文學(xué)批評(píng)方法》2023-2024學(xué)年第一學(xué)期期末試卷
- 廣東江門中醫(yī)藥職業(yè)學(xué)院《智能運(yùn)輸系統(tǒng)概論》2023-2024學(xué)年第一學(xué)期期末試卷
- 廣東技術(shù)師范大學(xué)《金融企業(yè)會(huì)計(jì)》2023-2024學(xué)年第一學(xué)期期末試卷
- 廣東海洋大學(xué)《機(jī)械工程技術(shù)交流》2023-2024學(xué)年第一學(xué)期期末試卷
- 廣東工商職業(yè)技術(shù)大學(xué)《機(jī)器學(xué)習(xí)原理》2023-2024學(xué)年第一學(xué)期期末試卷
- 廣東第二師范學(xué)院《生物藥物制劑技術(shù)》2023-2024學(xué)年第一學(xué)期期末試卷
- 廣東潮州衛(wèi)生健康職業(yè)學(xué)院《城市綠地規(guī)劃》2023-2024學(xué)年第一學(xué)期期末試卷
- 廣東財(cái)經(jīng)大學(xué)《建筑設(shè)計(jì)(Ⅱ)》2023-2024學(xué)年第一學(xué)期期末試卷
- 《國際腫瘤護(hù)理進(jìn)展》課件
- 2023年河北中煙工業(yè)有限責(zé)任公司筆試試題及答案
- 物質(zhì)與意識(shí)的辯證關(guān)系
- 小學(xué)英語考試教師總結(jié)反思8篇
- (高清版)DZT 0322-2018 釩礦地質(zhì)勘查規(guī)范
- SJ-T 11798-2022 鋰離子電池和電池組生產(chǎn)安全要求
- 多智能體仿真支撐技術(shù)、組織與AI算法研究
- 2023年中考語文二輪復(fù)習(xí):詞意表達(dá) 真題練習(xí)題匯編(含答案解析)
- 安全管理中人因素
- 銅礦的選礦工藝與設(shè)備選擇
- 餐廳年度總結(jié)計(jì)劃
- 83廣東省深圳市寶安區(qū)2023-2024學(xué)年六年級(jí)上學(xué)期期末數(shù)學(xué)試卷
評(píng)論
0/150
提交評(píng)論