計算機操作系統(tǒng)

ComputerOperatingSystems秦科

Email:QQ:215462624計算機的啟動……1.上電：加電電源開關(guān)被按下時，機器就開始供電，主板的控制芯片組會向CPU發(fā)出并保持一個RESET（重置）信號，讓CPU恢復(fù)到初始狀態(tài)。當(dāng)芯片組檢測到電源已經(jīng)開始穩(wěn)定供電時就會撤去RESET信號。CPU就從0XFFFF0處開始執(zhí)行指令。這個地址屬于BIOS的地址范圍，這里只是一條跳轉(zhuǎn)指令，跳到系統(tǒng)BIOS真正的啟動代碼處。2.自檢：系統(tǒng)BIOS的啟動代碼首先做POST（上電自檢）：檢測系統(tǒng)中一些關(guān)鍵設(shè)備是否存在和能否正常工作，例如內(nèi)存、顯卡等。由于POST是最早進行的檢測過程，此時顯卡還沒有初始化，如果系統(tǒng)BIOS在POST的過程中發(fā)現(xiàn)了一些致命錯誤，那么系統(tǒng)BIOS就會直接控制喇叭發(fā)聲來報告錯誤，聲音的長短和次數(shù)代表了錯誤的類型。計算機的啟動……3.初始化設(shè)備：系統(tǒng)BIOS將查找顯卡的BIOS，存放顯卡BIOS的ROM芯片的起始地址通常設(shè)在0xC0000處，系統(tǒng)BIOS在這個地方找到顯卡BIOS之后就調(diào)用它的初始化代碼，由顯卡BIOS來初始化顯卡，此時多數(shù)顯卡都會在屏幕上顯示出一些初始化信息，介紹生產(chǎn)廠商、圖形芯片類型等內(nèi)容。系統(tǒng)BIOS接著會查找其它設(shè)備的BIOS程序，找到之后同樣要調(diào)用這些BIOS內(nèi)部的初始化代碼來初始化相關(guān)的設(shè)備。4.檢測其他設(shè)備，例如硬盤、光驅(qū)、并口串口等，分配中斷5.更新擴展系統(tǒng)配置信息，是系統(tǒng)BIOS和操作系統(tǒng)交換系統(tǒng)硬件配置信息的一種方式。計算機的啟動……6.引導(dǎo)：根據(jù)用戶指定的啟動順序從USB、硬盤或光驅(qū)啟動操作系統(tǒng)。以WindowsXP為例，系統(tǒng)BIOS將啟動盤（一般是主硬盤）的第一個扇區(qū)（BootSector，引導(dǎo)扇區(qū)）讀入到內(nèi)存的0x7C00處，并檢查0x7DFE地址的內(nèi)存，如果其內(nèi)容是0xAA55，跳轉(zhuǎn)到0x7C00處執(zhí)行MBR（MasterBootRecord，主引導(dǎo)記錄），MBR接著從分區(qū)表（PartitionTable）中找到第一個活動分區(qū)（ActivePartition，一般是C盤分區(qū)），然后按照類似方式讀取并執(zhí)行這個活動分區(qū)的引導(dǎo)扇區(qū)（PartitionBootSector），而引導(dǎo)扇區(qū)將負(fù)責(zé)讀取并執(zhí)行NTLDR（NTLoaDeR，WindowsNT的加載程序），然后主動權(quán)就移交給了Windows。如何自己動手引導(dǎo)計算機啟動所需軟件VirtualBox,VMware等虛擬機軟件Ubuntu，RedHat等Linux發(fā)行版WindowsLinux下的匯編編譯器nasm程序源文件編輯器Internet org 07c00h ;告訴編譯器程序加載到7c00處

mov ax,cs mov ds,ax mov es,ax call DispStr ;調(diào)用顯示字符串例程

jmp $ ;無限循環(huán)DispStr: mov ax,BootMessage mov bp,ax ;ES:BP=串地址

mov cx,16 ;CX=串長度

mov ax,01301h ;AH=13,AL=01h mov bx,000ch ;頁號為0(BH=0)黑底紅字(BL=0Ch,高亮) mov dl,0 int 10h ;10h號中斷

retBootMessage: db "Hello,OSworld!" times 510-($-$$) db 0;填充剩下的空間，使生成的二進制代碼恰好為512字節(jié)

dw 0xaa55 ;結(jié)束標(biāo)志程序1：來源于《自己動手寫操作系統(tǒng)》1.編寫匯編程序2.用nasm編譯上述匯編程序nasmboot.asm–oboot.bin提示:需要先安裝nasm工具，在Ubuntu環(huán)境下，使用：sudoapt-getinstallnasm即可3.將bin文件轉(zhuǎn)換成可啟動的映像文件ddif=boot.binof=boot.imgbs=512count=1ddif=/dev/zeroof=boot.imgskip=1seek=1bs=512count=28794.將生成的img文件拷貝出來用于啟動虛擬機sudomkdir/mnt/sharesudomount–tvboxsfKanbox/mnt/share前提：安裝virtualBox的附件5.新建虛擬機，用img文件啟動第二章

進程和線程ProcessesandThreads2.1進程Process進程是操作系統(tǒng)最核心的概念現(xiàn)代操作系統(tǒng)的一切都為進程而展開進程是什么？一個EXE程序？一個文本文件（*.c,*.java…）？……正在運行的程序的一個抽象（正解）2.1進程Process進程模型順序執(zhí)行并發(fā)執(zhí)行偽并行并行與并發(fā)Figure2-1.(a)具有4道程序的多道程序設(shè)計.(b)抽象為4個獨立進程.(c)在一個時刻僅有一個進程是活躍的TheProcessModel2.2進程的順序執(zhí)行1．程序的順序執(zhí)行

S1：a＝x+y；

S2：b＝a-5；

S3：c＝b+1；2.2進程的順序執(zhí)行2．程序順序執(zhí)行時的特征（1）順序性：處理機的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行。（2）封閉性：程序運行時獨占全機資源，程序一旦開始執(zhí)行，其執(zhí)行結(jié)果不受外界因素影響。（3）可再現(xiàn)性：只要程序執(zhí)行時的環(huán)境和初始條件相同，都將獲得相同的結(jié)果。（不論它是從頭到尾不停頓地執(zhí)行，還是“停停走走”地執(zhí)行）2.2進程的并發(fā)執(zhí)行2.2進程的并發(fā)執(zhí)行S1：a=x+2S2：b=y+4S3：c=a+bS4：d=c+b2.2順序執(zhí)行與并發(fā)執(zhí)行N=N+1Print（N）N=0 Print（N）N=N+1

N=0 Print（N）N=0N=N+1有兩個循環(huán)程序A和B它們共享一個變量N:A:N=N＋1B:Print(N);N=0;思考并發(fā)執(zhí)行有沒有問題？YES如果有，有什么問題？不可再現(xiàn)如何解決這樣的問題？進程的控制2.2進程的并發(fā)執(zhí)行間斷性:由于它們共享系統(tǒng)資源，以及為完成同一項任務(wù)而相互合作，致使在這些并發(fā)執(zhí)行的程序之間，形成了相互制約的關(guān)系。相互制約將導(dǎo)致并發(fā)程序具有“執(zhí)行——暫停——執(zhí)行”這種間斷性的活動規(guī)律。失去封閉性:是多個程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運行已失去了封閉性。不可再現(xiàn)性:程序在并發(fā)執(zhí)行時，由于失去了封閉性，導(dǎo)致不可再現(xiàn)性。2.2順序和并發(fā)思考：各有什么優(yōu)點與缺點？思考：適用場合？2.3進程的狀態(tài)進程的三種基本狀態(tài)就緒（Ready）狀態(tài)：當(dāng)進程已分配到除CPU以外的所有必要資源后，只要再獲得CPU，便可立即執(zhí)行。執(zhí)行狀態(tài)（Running）：進程已獲得CPU，其程序正在執(zhí)行。阻塞狀態(tài)（Blocked）：正在執(zhí)行的進程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機而處于暫停狀態(tài)，把這種暫停狀態(tài)稱為阻塞狀態(tài)，有時也稱為等待狀態(tài)。2.3進程的狀態(tài)轉(zhuǎn)換單阻塞隊列:多阻塞隊列:2.3進程的狀態(tài)New：進程已經(jīng)創(chuàng)建，但未被OS接納為可執(zhí)行進程，并且程序還在輔存，PCB在內(nèi)存Exit：因停止或取消，被OS從執(zhí)行狀態(tài)釋放2.3進程的掛起狀態(tài)掛起狀態(tài):使執(zhí)行的進程暫停執(zhí)行,靜止下來,我們把這種靜止?fàn)顟B(tài)稱為掛起狀態(tài)。2.3引入掛起狀態(tài)的原因（1）終端用戶的請求。（2）父進程請求。（3）負(fù)荷調(diào)節(jié)的需要。當(dāng)實時系統(tǒng)中的工作負(fù)荷較重，把一些不重要的進程掛起，以保證系統(tǒng)能正常運行。（4）操作系統(tǒng)的需要。操作系統(tǒng)有時希望掛起某些進程，以便檢查運行中的資源使用情況或進行記賬。2.3進程掛起狀態(tài)的轉(zhuǎn)換2.3進程狀態(tài)的轉(zhuǎn)換空白→新建系統(tǒng)調(diào)用、用戶登陸、用戶請求……新建→就緒系統(tǒng)尚有空余資源，接納進程并放入就緒隊列就緒→運行獲得了除了CPU之外的所有資源運行→完畢進程正常執(zhí)行完畢或者被KILL2.3進程狀態(tài)的轉(zhuǎn)換運行→就緒時間片用完、CPU被搶占運行→阻塞等待請求完成阻塞→就緒請求已經(jīng)完成就緒（阻塞）→退出無償?shù)乇籏ILL2.3進程狀態(tài)的轉(zhuǎn)換阻塞→阻塞掛起釋放內(nèi)存空間就緒→就緒掛起沒有阻塞進程，掛起就緒進程以釋放空間就緒掛起→就緒沒有就緒進程或者就緒進程優(yōu)先級較低阻塞掛起→阻塞阻塞掛起→就緒掛起2.3進程狀態(tài)的轉(zhuǎn)換深入理解進程的狀態(tài)轉(zhuǎn)換，有助于深入理解操作系統(tǒng)的內(nèi)部精髓！思考：哪些狀態(tài)之間是不可以相互轉(zhuǎn)換的？為什么不存在這些轉(zhuǎn)換？有沒有可能存在這些轉(zhuǎn)換？2.4進程的控制進程狀態(tài)（若干狀態(tài)之間的轉(zhuǎn)換及轉(zhuǎn)換依據(jù)）進程映像進程控制塊PCB（ProcessControlBlock）進程圖2.4進程的控制思考：如果你是操作系統(tǒng)的設(shè)計者，你如何去控制進程？進程映像進程的程序、數(shù)據(jù)、堆、棧的集合進程控制塊用于控制進程屬性的集合。2.4進程的控制原圖來源于《操作系統(tǒng)—精髓與設(shè)計原理》2.4進程的控制進程控制塊標(biāo)識符狀態(tài)優(yōu)先級程序計數(shù)器內(nèi)存指針上下文I/O狀態(tài)審計信息處理器的寄存器數(shù)據(jù)信息程序代碼和進程相關(guān)數(shù)據(jù)指針、共享內(nèi)存塊指針等下一條執(zhí)行指令的地址處理器的使用時間總和、時間限制等2.4進程的控制進程標(biāo)識標(biāo)識符處理器狀態(tài)信息用戶可見寄存器，控制和狀態(tài)寄存器，棧指針進程控制信息調(diào)度和狀態(tài)信息，進程間通信，特權(quán)、存儲管理、資源使用情況2.4進程的控制原圖來源于《操作系統(tǒng)—精髓與設(shè)計原理》2.4進程的控制進程控制塊操作系統(tǒng)維持著一個由PCB組成的鏈表，根據(jù)鏈表中的PCB來控制系統(tǒng)中的進程進程控制塊面臨的難題——安全保護執(zhí)行就緒阻塞P1P2P3P4P5P62.4進程的控制進程圖（ProcessGraph）進程圖是用于描述一個進程的家族關(guān)系的有向樹。子進程可以繼承父進程所擁有的資源。當(dāng)子進程被撤消時，應(yīng)將其從父進程那里獲得的資源歸還給父進程。Eventswhichcauseprocesscreation:系統(tǒng)初始化Systeminitialization.正在運行的進程調(diào)用了一個進程創(chuàng)建系統(tǒng)Executionofaprocesscreationsystemcallbyarunningprocess.用戶請求Auserrequesttocreateanewprocess.批處理作業(yè)的初始化Initiationofabatchjob.……2.4.1進程的創(chuàng)建ProcessCreation2.4.1進程的創(chuàng)建思考：創(chuàng)建進程時，操作系統(tǒng)需要做哪些事？2.4.1進程的創(chuàng)建調(diào)用進程創(chuàng)建原語按下述步驟創(chuàng)建一個新進程：（1）申請空白PCB。（2）為新進程分配資源。為新進程的程序和數(shù)據(jù)以及用戶棧分配必要的內(nèi)存空間。（3）初始化進程控制塊。初始化標(biāo)識信息。初始化處理機狀態(tài)信息。使程序計數(shù)器指向程序的入口地址，使棧指針指向棧頂；初始化處理機控制信息：進程的狀態(tài)、優(yōu)先級。（4）將新進程插入就緒隊列。2.4.1進程的創(chuàng)建關(guān)于Unix和Windows的不同做法Unix：fork()創(chuàng)建一個和調(diào)用進程相同的副本。相同的存儲映像、相同的環(huán)境……子進程執(zhí)行execve修改存儲映像2.4.1進程的創(chuàng)建關(guān)于Unix和Windows的不同做法Windows：CreateProcess()既負(fù)責(zé)進程的創(chuàng)建，也負(fù)責(zé)裝入正確的程序各種參數(shù)、安全屬性、優(yōu)先級信息……Eventswhichcauseprocesstermination:Normalexit(voluntary).Errorexit(voluntary).Fatalerror(involuntary).Killedbyanotherprocess(involuntary).2.4.2進程終止ProcessTermination2.4.2進程的終止利用終止原語終止進程檢索將被終止的進程PCB終止該進程的執(zhí)行（若有子進程，一并終止）回收資源將該進程PCB從當(dāng)前隊列中移除2.4.3進程的阻塞調(diào)用阻塞原語自我阻塞暫停進程的執(zhí)行，修改PCB運行狀態(tài)將PCB插入阻塞隊列調(diào)度新進程2.4.4進程的喚醒調(diào)用喚醒原語喚醒進程檢索阻塞隊列，尋找要喚醒進程的PCB修改PCB的運行狀態(tài)插入PCB到就緒隊列2.4.5進程的掛起與激活利用掛起原語掛起進程利用激活原語激活進程2.4.5進程的切換步驟保存處理器狀態(tài)信息更新當(dāng)前進程的狀態(tài)將當(dāng)前進程PCB移動到相應(yīng)的隊列選擇另一個進程PCB更新該進程的PCB更新內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)恢復(fù)當(dāng)前進程被切換前的上下文信息2.4.5模式切換模式切換可以不改變正處于運行態(tài)的進程的狀態(tài)。保存上下文環(huán)境和恢復(fù)上下文環(huán)境只需要很小的開銷2.5線程Threads回顧進程的概念每個進程有自己獨立的地址空間每個進程擁有自己資源的控制權(quán)I/O、主存、文件……進程是操作系統(tǒng)的最小調(diào)度單位進程切換2.5線程思考兩個進程，相互配合完成一件工作，執(zhí)行順序為

P1,P2,P1,P2……

可能會發(fā)生什么事情？2.5線程為了減少操作系統(tǒng)的開銷，現(xiàn)代操作系統(tǒng)引入線程的概念線程是調(diào)度的最小單位進程是資源擁有的最小單位一個進程可以有多個線程2.5線程單進程單線程單進程多線程多進程單線程多進程多線程2.5線程線程的特點同一個進程的所有線程共享該進程的資源同一個進程的所有線程共享同一個地址空間線程的優(yōu)點創(chuàng)建快（比進程大約快10倍）終止快切換快通信快，無需內(nèi)核介入2.5線程單線程進程模型PCB用戶地址空間用戶棧內(nèi)核棧多線程進程模型PCB用戶地址空間用戶棧內(nèi)核棧TCB1內(nèi)核棧用戶棧內(nèi)核棧用戶棧TCB2TCB32.5線程在支持線程的操作系統(tǒng)中，線程是調(diào)度分派的最小單位，進程是資源擁有的最小單位線程同樣具有幾種基本狀態(tài)就緒、執(zhí)行、阻塞同樣存在進程的調(diào)度對進程的操作影響到進程中的所有線程2.5線程線程的基本操作派生（Spawn)：當(dāng)產(chǎn)生一個新進程時，同時也為該進程派生了一個線程，隨后，進程中的線程可以在同一個進程中派生另一個線程，新線程被放置在就緒隊列中。阻塞（Block)：當(dāng)線程需要等待一個事件時，它將阻塞，此時處理器轉(zhuǎn)而執(zhí)行另一個就緒線程。解除阻塞（Unblock）：當(dāng)阻塞一個線程的事件發(fā)生時，該線程被轉(zhuǎn)移到就緒隊列中。結(jié)束（Finish）：當(dāng)一個線程完成時，其寄存器的信息和棧都被釋放。2.5線程線程的實現(xiàn)用戶級線程線程的管理由應(yīng)用程序完成內(nèi)核級線程線程的管理由內(nèi)核完成，應(yīng)用程序通過API訪問線程2.5線程2.5線程用戶級線程與內(nèi)核級線程的比較用戶級線程不需要模式切換用戶級線程由應(yīng)用程序?qū)崿F(xiàn)調(diào)度管理用戶級線程可以在任意操作系統(tǒng)中運行缺點用戶級線程執(zhí)行系統(tǒng)調(diào)用時，同一進程所有線程都會被阻塞不能利用多處理機技術(shù)2.5線程用戶級線程與內(nèi)核級線程的比較內(nèi)核實現(xiàn)內(nèi)核級線程的調(diào)度管理可以充分利用多處理機技術(shù)缺點有模式切換的開銷2.5線程2.6進程的并發(fā)什么是并發(fā)？并發(fā)是所有問題的基礎(chǔ)，也是操作系統(tǒng)設(shè)計的基礎(chǔ)由并發(fā)帶來的兩個問題對資源的相互制約：同步對資源的相互共享：互斥包括所有物理設(shè)備如CPU、打印機等，也包括文件、進程等虛擬概念2.6進程的并發(fā)相關(guān)的關(guān)鍵概念臨界資源臨界區(qū)死鎖互斥競爭饑餓2.6進程的并發(fā)相關(guān)的關(guān)鍵概念臨界資源一次僅允許一個進程訪問的資源為臨界資源臨界區(qū)把在每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)。代碼作為一個共享資源，一次只能允許一個進程訪問2.6進程的并發(fā)相關(guān)的關(guān)鍵概念死鎖兩個或兩個以上的進程相互等待導(dǎo)致都不能執(zhí)行互斥當(dāng)一個進程在臨界區(qū)訪問臨界資源時，其他進程不能進入該臨界區(qū)訪問共享資源2.6進程的并發(fā)相關(guān)的關(guān)鍵概念競爭多個進程讀寫一個共享數(shù)據(jù)時依賴它們執(zhí)行的相對時間饑餓一個進程已經(jīng)完全具備了執(zhí)行的條件，但是得不到CPU資源2.6進程的并發(fā)進程的并發(fā)會導(dǎo)致程序執(zhí)行結(jié)果不封閉全局資源對全局資源的訪問秩序非常重要資源分配不好的分配算法可能導(dǎo)致死鎖2.6進程的并發(fā)：生產(chǎn)者消費者問題同步——生產(chǎn)者和消費者問題生產(chǎn)者生產(chǎn)產(chǎn)品，提供給消費者去消費。為使得生產(chǎn)者進程和消費者進程能并發(fā)執(zhí)行，在兩者之間設(shè)置了具有n個緩沖區(qū)的緩沖池。生產(chǎn)者進程將他生產(chǎn)的產(chǎn)品放入緩沖池（一次一個），消費者進程從緩沖池中拿走產(chǎn)品（一次一個）。緩沖池已滿時，生產(chǎn)者不能再放，緩沖池已空時，消費者不能再拿。2.6進程的并發(fā)：生產(chǎn)者消費者問題count:緩沖區(qū)中已有的產(chǎn)品數(shù)n:緩沖區(qū)總共能容納的產(chǎn)品數(shù)in：生產(chǎn)者的緩沖區(qū)指針out：消費者的緩沖區(qū)指針2.6進程的并發(fā)reg1=counterreg1=reg1+1reg2=counterreg2=reg2-1counter=reg1counter=reg2reg1=5Counter=5reg1=6reg2=4reg2=5Counter=6Counter=42.6進程的并發(fā)臨界資源Count臨界區(qū)Count++Count—問題：如何實現(xiàn)對臨界資源和臨界區(qū)的訪問？互斥2.6進程的并發(fā)為了實現(xiàn)對臨界資源的訪問，每個進程都互斥地進入自己的臨界區(qū)：一次只有一個程序在臨界區(qū)進入臨界區(qū)之前，對預(yù)先訪問的臨界資源進行檢查若該資源尚未被訪問，則可以進入臨界區(qū)；反之則不能設(shè)置正在訪問標(biāo)志將資源恢復(fù)為未訪問標(biāo)志2.6進程的并發(fā)思考：互斥可能帶來的問題死鎖進程P1占有資源R1，等待資源R2；進程P2占有資源R2，等待資源R1思考：如何解決這個問題饑餓無限期地被推遲訪問2.6進程的并發(fā)同步機制應(yīng)該遵循的準(zhǔn)則

空閑讓進。(2)忙則等待。(3)有限等待。(4)讓權(quán)等待。2.6進程的并發(fā)思考：如何實現(xiàn)互斥訪問嚴(yán)格輪換每個進程每次都從頭執(zhí)行到尾屏蔽中斷剛剛進入臨界區(qū)時就屏蔽中斷，剛要出臨界區(qū)就打開中斷專用機器指令test_and_set、test_and_clear軟件方法信號量2.6.3軟件方法解決互斥與同步軟件方法解決互斥與同步舉例：愛斯基摩人的小屋協(xié)議（第一次賞試）。愛斯基摩人的小屋協(xié)議執(zhí)行環(huán)境：門和小屋很小，每次只能容納一個人進入，小屋內(nèi)有一個標(biāo)志黑板進程申請進入臨界區(qū)時，必須首先進入小屋并檢查黑板標(biāo)志是否能進入臨界區(qū)。是，離開小屋，進入臨界區(qū)，執(zhí)行完畢，退出臨界區(qū)，并返回小屋，修改黑板標(biāo)志為其他進程。否，反復(fù)進入小屋，檢查黑板標(biāo)志，直到標(biāo)志是自己。小黑版指示P1可進第一次賞試的算法分析（Dekker’sAlgorithm）varturn:0，1;{共享的全局變量}PROCESS0PROCESS1

…

…whileturn≠0do{nothing};whileturn≠1do{nothing};<criticalsection>;<criticalsection>turn:=1;turn:=0;

…

…解析保證了互斥，但存在問題：進程“忙等”進入臨界區(qū)；若黑板標(biāo)志修改失敗，其他進程永久阻塞為1執(zhí)行為0執(zhí)行第二次賞試

（Dekker’sAlgorithm）愛斯基摩人的小屋協(xié)議執(zhí)行環(huán)境：每個人有一個自己的小屋，但看別人的標(biāo)志，以確定是否進入臨界區(qū)。每個人只能檢查，但不能修改他人的黑板標(biāo)志若某人申請進入臨界區(qū)，首先檢查對方黑板是否為“false”是，修改自己小屋黑板值為“true”，進入臨界區(qū)執(zhí)行，執(zhí)行完畢，恢復(fù)黑板值為“false”。否，反復(fù)進入小屋，檢查黑板標(biāo)志，直到標(biāo)志是“false”。第二次賞試的算法分析（一）（Dekker’sAlgorithm）varflag:array[0，1]ofboolean:false;{共享全局變量}PROCESS0PROCESS1

…

…whileflag[1]whileflag[0]do{nothing};do{nothing};flag[0]:=true;flag[1]:=true;<criticalsection>;<criticalsection>flag[0]:=false;flag[1]:=false;

…

…第二次賞試的算法分析（二）（Dekker’sAlgorithm）分析以下執(zhí)行順序：P0：當(dāng)flag[1]=false;執(zhí)行whileflag[1];P1：當(dāng)flag[0]=false;執(zhí)行whileflag[0];P0：置flag[0]=true執(zhí)行<criticalsection>;P1：置flag[1]=true;執(zhí)行<criticalsection>;

若進程執(zhí)行完臨界區(qū)，恢復(fù)自己標(biāo)志為“false”失敗，則其他進程永久阻塞。第三次賞試

（Dekker’sAlgorithm）在檢查其他進程之前，希望進到臨界區(qū)，則設(shè)置自己flag=true。當(dāng)設(shè)置標(biāo)志為真后，如果其他進程在臨界區(qū)，則本進程阻塞，直到其他進程釋放臨界區(qū)為止。第三次賞試的算法分析（一）（Dekker’sAlgorithm）varflag:array[0，1]ofboolean:false;{共享的全局變量}PROCESS0PROCESS1

…

…flag[0]:=true; flag[1]:=true;whileflag[1] whileflag[0]do{nothing}; do{nothing};<criticalsection>; <criticalsection>flag[0]:=false; flag[1]:=false;

…

…第三次賞試的算法分析（二）

（Dekker’sAlgorithm）分析P0、P1執(zhí)行順序：P0：置flag[0]=true;P1：當(dāng)flag[1]=true;P0：執(zhí)行whileflag[1]doblocked;P1：執(zhí)行whileflag[0]doblocked;解析：如果兩個進程在執(zhí)行while之前都把flag設(shè)置成true，那么每個進程都會以為對方進入了臨界區(qū)，使自己處于阻塞，從而導(dǎo)致死鎖。第四次賞試

（Dekker’sAlgorithm）第四次賞試主要思想是將標(biāo)志重置，不會發(fā)生死鎖。實現(xiàn)過程：希望進到臨界區(qū)，則設(shè)置自己標(biāo)志為：flag=true。如果其他進程在臨界區(qū)，則將本進程標(biāo)志置為flag=false，稍后又置為true，這一過程重復(fù)到能進入臨界區(qū)為止。第四次賞試的算法分析（一）（Dekker’sAlgorithm）varflag:array[0..1]ofboolean:false;{共享的全局變量}PROCESS0PROCESS1

…

…flag[0]:=true;flag[1]:=true;whileflag[1]dowhileflag[0]dobeginbegin

flag[0]:=false;flag[1]:=false;<delayforashorttime>;<delayforashorttime>;

flag[0]:=true;flag[1]:=true;end;end;<criticalsection>;<criticalsection>flag[0]:=false;flag[1]:=false;

…

…

重置標(biāo)志試按以下順序執(zhí)行：

P0：置flag[0]=true; P1：置flag[1]=true; P0：執(zhí)行whileflag[1]; P1：執(zhí)行whileflag[0]; P0：置flag[0]=false; P1：置flag[1]=false; P0：置flag[0]=true; P1：置flag[1]=true;

…解析：檢查其它進程，然后重置，再檢查，再重置…，重置序列可以無線延伸，任何一個進程都不能進入自己的臨界區(qū)。(這種現(xiàn)象稱為:互斥禮讓)第四次賞試的算法分析（二）

（Dekker’sAlgorithm）試按以下順序執(zhí)行：

P0：置flag[0]=true; P1：置flag[1]=true; P0：執(zhí)行whileflag[1]; P1：執(zhí)行whileflag[0]; P0：置flag[0]=false; P1：置flag[1]=false; P0：置flag[0]=true; P1：置flag[1]=true;

…解析：檢查其它進程，然后重置，再檢查，再重置…，重置序列可以無線延伸，任何一個進程都不能進入自己的臨界區(qū)。(這種現(xiàn)象稱為:互斥禮讓)解決“互斥禮讓”的第一種方法：為了解決“互斥禮讓”問題的第一種算法,其主要思想是:需要兩個變量:turn和Flag，再控制執(zhí)行順序，先判flag,再判turn。1.turn:指出應(yīng)該哪一個進入臨界區(qū)

turn=0表示P0可以進入臨界區(qū)

turn=1表示P1可以進入臨界區(qū)2.Flag:指出當(dāng)前哪一個在臨界區(qū)

Flag=0表示P0當(dāng)前在臨界區(qū)

Flag=1表示P1當(dāng)前在臨界區(qū)增加一個帶準(zhǔn)許進入臨界區(qū)標(biāo)志的小屋指示P0可以進入臨界區(qū)表示沒有進程在臨界區(qū)第四次賞試的算法分析（三）

（Dekker’sAlgorithm）varflag：array[0，1]ofboolean;turn：0，1;//準(zhǔn)許進入臨界區(qū)標(biāo)志變量begin flag[0]：=false；

flag[1]：=false; turn:＝0；//設(shè)P0進程在臨界區(qū)

parbegin p0；p1; parendendprocedureP0；Beginrepeatflag[0]:＝true；//初值為真，P0希望進入臨界區(qū)。whileflag[1]do//查P1進程標(biāo)志ifturn=1then//turn為1，表明P1進程在臨界區(qū)

beginflag[0]:=false;whileturn=1//當(dāng)turn=1，表明P0進程不能進入臨界區(qū)

do{nothing}；

flag[0]：＝true;//設(shè)標(biāo)志為真，P0進入臨界區(qū)

end;

＜criticalsection＞;//如果turn=0，則P0可進入臨界區(qū)執(zhí)行

turn：=1； //執(zhí)行結(jié)束，P0退出臨界區(qū)，則P1進程可進臨界區(qū)

flag[0]：＝false;//表明P0不在臨界區(qū)＜remainder＞//P0執(zhí)行其余程序foreverendprocedureP1;beginrepeatflag[1]:=true；whileflag[0]doifturn=0thenbeginflag[1]:＝false;whileturn＝0do{nothing}；

flag[1]:＝trueend;<criticalsection＞;turn：＝0;flag[1]：＝false；<remainder>foreverend第四次賞試的算法分析（四）、（Dekker’sAlgorithm）解析（分析P0的執(zhí)行）1.置flag[0]:=true;//設(shè)自己為真2.執(zhí)行whileflag[1]語句有兩種情況:(1)當(dāng)flag[1]=false,P0進入臨界區(qū)，執(zhí)行結(jié)束，置turn:=1;flag[0]:=false;(2)當(dāng)flag[1]=true,檢查turn的值,turn的值又有兩種情況:①turn=1P1在臨界區(qū)，P0處于“忙等”②turn=0P1已退出（但還未修改flag的值），P0立即進入解決“互斥禮讓”的第二種方法：簡單的互斥方案：turn解決同時的沖突，F(xiàn)lag指示進程是否在臨界區(qū)。對兩參量同時控制，交替進入臨界區(qū)執(zhí)行。varflag：array[0，1]ofboolean；

turn：0，1;beginflag[0]:＝false;flag[1]:＝false;turn:=1; //假設(shè)P1進程可先進臨界區(qū)

parbeginP0;P1; //見下頁

parendendprocedureP0;beginrepeatflag[0]:=true; //P0進程希望進臨界區(qū)

turn：＝1；

whileflag[1]andturn＝1do{nothing}；＜criticalsection＞；

flag[0]：=false;<remainder>foreverend；procedureP1；

beginrepeat flag[1]:=true; turn:＝0; whileflag[0]andturn=0 do{nothing}；

<criticalsection>；

flag[1]:=false； ＜remainder＞

foreverend；第四次賞試的算法分析（五）分析P0的執(zhí)行：1.置flag[0]:=true;{阻止P1進入臨界區(qū)}2.執(zhí)行whileflag[1]

當(dāng)flag[1]=false時,P0進入，執(zhí)行完成，置flag[0]:=false;

當(dāng)flag[1]=true時,P0阻塞，等待P1退出2.6進程的并發(fā)：信號量1.整型信號量最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操作(AtomicOperation)wait(S)和signal(S)來訪問。這兩個操作一直被分別稱為P、V操作。wait和signal操作可描述為：

P(S):while(S≤0);S=S-1;V(S):S=S+1;2.6進程的并發(fā)：信號量整型信號量面臨的問題只要是信號量S≤0，就會不斷地測試。因此，該機制并未遵循“讓權(quán)等待”的準(zhǔn)則2.6進程的并發(fā)：信號量2.記錄型信號量一個用于代表資源數(shù)目的整型變量value外一個進程鏈表L，用于鏈接所有等待進程。2.6進程的并發(fā)：信號量記錄型信號量P(S):SemphmoreS;S.value=S.value-1;if(S.value＜0)block(S,L)V(S):SemphmoreS;S.value=S.value+1;if(S.value≤0)wakeup(S,L);2.6進程的并發(fā)：信號量S.value的初值表示系統(tǒng)中某類資源的數(shù)目，因而又稱為資源信號量，對它的每次wait操作，意味著進程請求一個單位的該類資源，因此描述為S.value=S.value-1；當(dāng)S.value＜0時，表示該類資源已分配完畢，因此進程應(yīng)調(diào)用block原語，進行自我阻塞，放棄處理機，并插入到信號量鏈表S.L中?？梢?，該機制遵循了“讓權(quán)等待”準(zhǔn)則。此時S.value的絕對值表示在該信號量鏈表中已阻塞進程的數(shù)目。2.6進程的并發(fā)：信號量

對信號量的每次signal操作，表示執(zhí)行進程釋放一個單位資源，故S.value=S.value+1操作表示資源數(shù)目加1。若加1后仍是S.value≤0，則表示在該信號量鏈表中，仍有等待該資源的進程被阻塞，故還應(yīng)調(diào)用wakeup原語，將S.L鏈表中的第一個等待進程喚醒。如果S.value的初值為1，表示只允許一個進程訪問臨界資源，此時的信號量轉(zhuǎn)化為互斥信號量。2.6進程的并發(fā)：信號量3.AND信號量AND同步機制的基本思想是：將進程在整個運行過程中需要的所有資源，一次性全部地分配給進程，待進程使用完后再一起釋放。只要尚有一個資源未能分配給進程，其它所有可能為之分配的資源，也不分配給他。亦即，對若干個臨界資源的分配，采取原子操作方式：要么全部分配到進程，要么一個也不分配。2.6進程的并發(fā)：信號量在兩個進程中都要包含兩個對Dmutex和Emutex的操作，即processA: processB:wait(Dmutex); wait(Emutex);wait(Emutex); wait(Dmutex);若進程A和B按下述次序交替執(zhí)行wait操作：processA:wait(Dmutex);于是Dmutex=0processB:wait(Emutex);于是Emutex=0processA:wait(Emutex);于是Emutex=-1A阻塞processB:wait(Dmutex);于是Dmutex=-1B阻塞2.6進程的并發(fā)：信號量Swait(S1,S2,…,Sn)if(Si≥1and…andSn≥1)for(i=1;i<=n;i++)Si=Si-1;elseplacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi＜1,andsettheprogramcountofthisprocesstothebeginningofSwaitoperationendif2.6進程的并發(fā)：信號量Ssignal(S1,S2,…,Sn)for(i=1;i<=n;i++)

｛Si=Si+1;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.

｝2.6進程的并發(fā)：信號量信號量集思考：記錄型信號量有何不便之處？當(dāng)一次需要多個資源時，需要進行多次P操作同理，要進行多次釋放V操作如何改進：2.6進程的并發(fā)：信號量Swait(S1,t1,d1,…,Sn,tn,dn)if(S1≥t1and…andSn≥tn)for(i=1;i<=n;i++)Si=Si-di;elsePlacetheexecutingprocessinthewaitingqueueofthefirstSiwithSi＜tiandsetitsprogramcountertothebeginningoftheSwaitOperation.t為下限值，d為需求值2.6進程的并發(fā)：信號量signal(S1,d1,…,Sn,dn)for(i=1;i<=n;i++){Si=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue}2.6進程的并發(fā)：信號量

一般“信號量集”的幾種特殊情況：

(1)Swait(S,d,d)。此時在信號量集中只有一個信號量S，但允許它每次申請d個資源，當(dāng)現(xiàn)有資源數(shù)少于d時，不予分配。

(2)Swait(S,1,1)。此時的信號量集已蛻化為一般的記錄型信號量(S＞1時)或互斥信號量(S=1時)。

(3)Swait(S,1,0)。這是一種很特殊且很有用的信號量操作。當(dāng)S≥1時，允許多個進程進入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進程進入特定區(qū)。換言之，它相當(dāng)于一個可控開關(guān)。1.利用信號量實現(xiàn)進程互斥利用信號量實現(xiàn)進程互斥的進程可描述如下：2.6進程的并發(fā)：信號量的應(yīng)用2.利用信號量實現(xiàn)前趨關(guān)系2.6進程的并發(fā)：信號量的應(yīng)用abcdefg2.6進程的并發(fā)：信號量的應(yīng)用abcdefg2.6進程的并發(fā)：信號量的應(yīng)用3.利用信號量解決生產(chǎn)者、消費者問題生產(chǎn)者與消費者之間的聯(lián)系互斥共享緩沖區(qū)（緩沖區(qū)作為一種臨界資源）同步相互等待（有產(chǎn)品才能消費、有消費才能不斷生產(chǎn)）思考：如何通過程序反映同步與互斥關(guān)系？信號量2.6進程的并發(fā)：信號量的應(yīng)用3.利用信號量解決生產(chǎn)者、消費者問題定義哪些信號量？如何對信號量進行初始化？生產(chǎn)者消費者1243502.6進程的并發(fā)：信號量的應(yīng)用利用記錄型信號量假定在生產(chǎn)者和消費者之間的公用緩沖池中，具有n個緩沖區(qū)，這時可利用互斥信號量Mutex實現(xiàn)諸進程對緩沖池的互斥使用；利用信號量Empty和Full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費者便可從緩沖池中取走一個消息。對生產(chǎn)者—消費者問題可描述如下：2.6進程的并發(fā)：信號量的應(yīng)用定義信號量：更正：Mutex=12.6進程的并發(fā)：信號量的應(yīng)用生產(chǎn)者進程：2.6進程的并發(fā)：信號量的應(yīng)用消費者進程：2.6進程的并發(fā)：信號量的應(yīng)用更正：Mutex=12.6進程的并發(fā)：信號量的應(yīng)用注意問題：每個程序中用于實現(xiàn)互斥的信號量Mutex的P操作和V操作必須成對地出現(xiàn)；對資源信號量Empty和Full的P操作和V操作同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中在每個程序中的多個P操作順序不能顛倒。應(yīng)先執(zhí)行對資源信號量的P操作，然后再執(zhí)行對互斥信號量的P操作，否則可能引起進程死鎖。2.6進程的并發(fā)：信號量的應(yīng)用利用AND信號量定義信號量：更正：Mutex=12.6進程的并發(fā)：信號量的應(yīng)用生產(chǎn)者進程：2.6進程的并發(fā)：信號量的應(yīng)用消費者進程：2.6進程的并發(fā)：信號量的應(yīng)用哲學(xué)家進餐問題012342.6進程的并發(fā)：信號量的應(yīng)用哲學(xué)家要進餐，須同時具備左邊和右邊的筷子一支筷子在一個時刻只允許一位使用用完之后返回原處2.6進程的并發(fā)：信號量的應(yīng)用哲學(xué)家進餐問題2.6進程的并發(fā)：信號量的應(yīng)用思考：上述算法有沒有問題？如何解決？2.6進程的并發(fā)：信號量的應(yīng)用思考題：桌上有一空盤，最多允許存放一只水果。爸爸可向盤中放一個蘋果或放一個桔子，兒子專等吃盤中的桔子，女兒專等吃蘋果。試用P、V操作實現(xiàn)爸爸、兒子、女兒三個并發(fā)進程的同步2.6進程的并發(fā)：信號量的應(yīng)用Father(){while(1){P(Empty);P(Mutex);Putfruit;if(Orange)V(So);elseV(Sa);V(Mutex)}}Son(){while(1){P(So)P(Mutex);FetchOrangeV(Empty);V(Mutex);Eating;}}Daughter(){while(1){P(Sa)P(Mutex);FetchApple;V(Mutex);V(Empty);Eating;}}Mutex=1,Empty=1,So=0,Sa=0;2.6進程的并發(fā)：信號量的應(yīng)用讀寫問題多個進程對同一個文件進行讀寫，要求不能同時寫文件不能同時讀和寫文件可以同時讀文件2.6進程的并發(fā)：信號量的應(yīng)用為實現(xiàn)Reader與Writer進程間在讀或?qū)憰r的互斥而設(shè)置了一個互斥信號量Wmutex。設(shè)置一個整型變量Readcount表示正在讀的進程數(shù)目。由于只要有一個Reader進程在讀，便不允許Writer進程去寫。因此，僅當(dāng)Readcount=0,表示尚無Reader進程在讀時，Reader進程才需要執(zhí)行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader進程便可去讀，相應(yīng)地，做Readcount+1操作。同理，僅當(dāng)Reader進程在執(zhí)行了Readcount減1操作后其值為0時，才須執(zhí)行signal(Wmutex)操作，以便讓W(xué)riter進程寫。Readcount是一個可被多個Reader進程訪問的臨界資源，因此，應(yīng)該為它設(shè)置一個互斥信號量rmutex。

2.6進程的并發(fā)：信號量的應(yīng)用2.6進程的并發(fā)：信號量的應(yīng)用2.6進程的并發(fā)：信號量的應(yīng)用思考題：四個進程A、B、C、D都要讀一個共享文件F，系統(tǒng)允許多個進程同時讀文件F。但限制是進程A和進程C不能同時讀文件F，進程B和進程D也不能同時讀文件F。為了使這四個進程并發(fā)執(zhí)行時能按系統(tǒng)要求使用文件，現(xiàn)用P、V操作進行管理2.6進程的并發(fā)：信號量的應(yīng)用2.6進程的并發(fā)：信號量的應(yīng)用思考題有一閱覽室，讀者進入時必須先在一張登記表上進行登記，該表為每一座位列一表目，包括座號和讀者姓名。讀者離開時要消掉登記信號，閱覽室中共有100個座位。用PV操作控制這個過程2.6進程的并發(fā)：信號量的應(yīng)用理發(fā)店理有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺。一個顧客到來時，它必須叫醒理發(fā)師如果理發(fā)師正在理發(fā)時又有顧客來到，則如果有空椅子可坐，就坐下來等待，否則就離開。2.6進程的并發(fā)：信號量的應(yīng)用Threechairs.Threebarbers.Waitingareahavingcapacityforfourseatsandadditionalspaceforcustomerstostandandwait.Firecodelimitsthetotalnumberofcustomers(seating+standing).Customercannotenterifpacktocapacity.Whenabarberisfree,customerwaitinglongestonthesofacanbeserved.2.6進程的并發(fā)：信號量的應(yīng)用Ifthereareanystandingcustomer,hecannowoccupytheseatonthesofa.Onceabarberfinishedhaircut,anybarbercantakethepayment.Asthereisonlyonecashregister,sopaymentfromonecustomerisacceptedatatime.Barber(s)timeisdividedintohaircut,acceptingpaymentandwaitingforcustomers(sleeping).關(guān)于P、V操作關(guān)于P、V操作關(guān)于P、V操作將三個經(jīng)典例子牢記于心生產(chǎn)者消費者問題哲學(xué)家就餐問題讀寫問題參考其他示例理發(fā)師問題關(guān)于P、V操作解決P、V操作問題的關(guān)鍵理解臨界資源與臨界區(qū)的概念！準(zhǔn)確理解問題的同步互斥過程與要求！同步：多個進程在執(zhí)行次序上的協(xié)調(diào)，相互等待消息互斥：對臨界資源的使用建立信號量，準(zhǔn)確定義信號量的意義和初始值！信號量的定義根據(jù)同步和互斥要求來定2.7管程Monitor雖然信號量機制是一種既方便、又有效的進程同步機制，但每個要訪問臨界資源的進程都必須自備PV操作。這就使大量的同步操作分散在各個進程中。這不僅給系統(tǒng)的管理帶來了麻煩，而且還會因同步操作的使用不當(dāng)而導(dǎo)致系統(tǒng)死鎖。這樣，在解決上述問題的過程中，便產(chǎn)生了一種新的進程同步工具——管程2.7管程Monitor當(dāng)共享資源用共享數(shù)據(jù)結(jié)構(gòu)表示時，資源管理程序可用對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程來表示(例如，資源的請求和釋放過程request和release)，我們把這樣一組相關(guān)的數(shù)據(jù)結(jié)構(gòu)和過程一并稱為管程。Hansan為管程所下的定義是：“一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進程和改變管程中的數(shù)據(jù)”。

2.7管程Monitor2.7管程Monitor2.7管程Monitor2.7管程Monitor管程的主要特點：局部數(shù)據(jù)變量只能被管程的過程訪問，任何外部過程都不能訪問。一個進程通過調(diào)用管程的一個過程進入管程。在任何時候，只能有一個進程在管程中執(zhí)行，調(diào)用管程的任何其他進程都被掛起，以等待管程變成可用的。

2.7管程Monitor為進行并發(fā)處理，管程必須包含同步工具。假設(shè)一個進程調(diào)用了管程，它在管程中時，須被掛起，直到滿足某些條件時才恢復(fù)。這就需要一種機制，使得該進程不僅被掛起，而且能釋放這個管程，以便某些別的進程可以進入。以后，當(dāng)條件滿足并且管程再次可用時，需要恢復(fù)該進程并允許它在掛起點重新進入管程。

2.7管程Monitor管程通過使用條件變量提供對同步的支持，這些條件變量包含在管程中，并且只有在管程中才能被訪問。有兩個函數(shù)可以操作條件變量：Cwait(c)：調(diào)用進程的執(zhí)行在條件c上掛起，管程現(xiàn)在可被另一個進程使用。Csignal(c)：恢復(fù)在cwait之后為某些條件而掛起的進程的執(zhí)行。如果有多個這樣的進程，選擇其中一個；如果沒有這樣的進程，什么也不做。2.8進程間通信（IPC）P、V操作可否用于進程通信？PV操作用于進程的同步與互斥，是低級進程通信P、V操作對于哪些進程通信不適用？網(wǎng)絡(luò)進程通信數(shù)據(jù)交換量較大的單機進程通信如何解決？2.8進程間通信解決辦法共享存儲器消息傳遞管道2.8進程間通信共享存儲器系統(tǒng)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式公用某一個數(shù)據(jù)結(jié)構(gòu)實現(xiàn)信息交換缺點？（難，低效，數(shù)據(jù)量較少）基于共享存儲區(qū)的通信方式（郵箱）劃分一塊存儲空間作為公用2.8進程間通信直接消息傳遞兩個或多個進程利用系統(tǒng)調(diào)用相互發(fā)送消息Send(Destination,&message)Receive(Source,&message)安全問題消息丟失、對象假冒、消息篡改……2.8進程間通信直接消息傳遞阻塞Send，阻塞Receiver無阻塞Send，阻塞Receiver無阻塞Send，無阻塞Receiver各有什么優(yōu)缺點？2.8進程間通信間接消息傳遞不直接發(fā)給消息的接收者，而是發(fā)到某個共享空間。消息的接收者和發(fā)送者之間的關(guān)系是不定的一對一多對多一對多多對一共享空間的所有權(quán)問題2.8進程間通信作業(yè)練習(xí)Socket編程一個進程利用send函數(shù)發(fā)信息一個進程利用recv接收信息并顯示參考《Unix環(huán)境高級編程》2.8進程間通信管道通信連接兩個進程：讀進程，寫進程寫進程以字符流形式輸入管道讀進程以字符流形式接收輸入注意事項互斥同步互相確定對方存在則開始通信2.8進程間通信Unix系統(tǒng)中管道的限制以半雙工方式工作使用管道的進程具有共同的祖先由Pipe函數(shù)創(chuàng)建管道fd[2]為兩個文件描述符，0為讀，1是寫，fd[1]的輸出是fd[0]的輸入如果成功返回0，否則返回-12.8進程間通信fd[0]fd[1]父進程子進程fd[1]fd[0]fd[1]fd[0]2.8進程間通信作業(yè)：練習(xí)Linux下管道通信編程父進程創(chuàng)建一個子進程父進程負(fù)責(zé)讀用戶終端輸入，并寫入管道子進程從管道接收字符流寫入另一個文件參考：《Unix環(huán)境高級編程》2.9進程調(diào)度1232.9進程調(diào)度進程調(diào)度的基本概念分配處理機的任務(wù)是由進程調(diào)度程序完成的。由于處理機是最重要的計算機資源，提高處理機的利用率及改善系統(tǒng)性能（吞吐量、響應(yīng)時間），在很大程度上取決于進程調(diào)度性能的好壞。2.9進程調(diào)度1．長程調(diào)度用于決定把外存上處于后備隊列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進程、分配必要的資源，然后，再將新創(chuàng)建的進程排在就緒隊列上，準(zhǔn)備執(zhí)行。通常也被稱為作業(yè)調(diào)度2.9進程調(diào)度

2.9進程調(diào)度

接納多少取決于就緒隊列長度2.9進程調(diào)度2．中程調(diào)度稱為中級調(diào)度引入中程調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。2.9進程調(diào)度

2.9進程調(diào)度

2.9進程調(diào)度3．短程調(diào)度

稱為進程調(diào)度。用來決定就緒隊列中的哪個進程應(yīng)獲得處理機，然后再由分派程序把處理機分配給該進程的具體操作2.9進程調(diào)度

2.9進程調(diào)度

2.9進程調(diào)度2.9進程調(diào)度調(diào)度的目標(biāo)：1、提高處理機的利用率2、提高系統(tǒng)吞吐量3、盡量減少進程的響應(yīng)時間4、防止進程長期得不到運行調(diào)度的原則：滿足用戶的需要和系統(tǒng)的需要。2.9進程調(diào)度面向用戶的準(zhǔn)則：周轉(zhuǎn)時間響應(yīng)時間截止時間公平性優(yōu)先權(quán)2.9進程調(diào)度（1）周轉(zhuǎn)時間短。從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔（稱為作業(yè)周轉(zhuǎn)時間）。作業(yè)在外存后備隊列上等待調(diào)度的時間進程在就緒隊列上等待進程調(diào)度的時間進程在CPU上執(zhí)行的時間進程等待I／O操作完成的時間。2.9進程調(diào)度平均周轉(zhuǎn)時間描述為：平均帶權(quán)周轉(zhuǎn)時間則可表示為：2.9進程調(diào)度響應(yīng)時間快從用戶通過鍵盤提交一個請求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時間。 響應(yīng)時間包括三部分時間：①從鍵盤輸入的請求信息傳送到處理機的時間②處理機對請求信息進行處理的時間。③將所形成的響應(yīng)信息回送到終端顯示器的時間。2.9進程調(diào)度截止時間

某任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間公平性各進程在系統(tǒng)中都能平等的得到運行優(yōu)先權(quán)準(zhǔn)則 讓某些緊急的作業(yè)能得到及時處理。2.9進程調(diào)度優(yōu)先級排隊模型2.9進程調(diào)度

面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高處理機利用率好各類資源的平衡利用指在單位時間內(nèi)，系統(tǒng)所完成的作業(yè)數(shù)進程調(diào)度可采用下述兩種調(diào)度方式。（1）非剝奪（搶占）方式（Non-preemptive）在采用這種調(diào)度方式時，一旦把處理機分配給某進程后，便讓該進程一直執(zhí)行，直至該進程完成或發(fā)生某事件而被阻塞時，才再把處理機分配給其他進程，決不允許某進程搶占已經(jīng)分配出去的處理機。2.9進程調(diào)度進程調(diào)度可采用下述兩種調(diào)度方式。（2）剝奪（搶占）方式（Preemptive）允許調(diào)度程序根據(jù)某種原則，去暫停某個正在執(zhí)行的進程，將已分配給該進程的處理機重新分配給另一進程。2.9進程調(diào)度2.9進程調(diào)度剝奪的原則：優(yōu)先權(quán)原則。短作業(yè)（進程）優(yōu)先原則。時間片原則。2.9進程調(diào)度調(diào)度算法FCFS(First-Come-First-Served)先來先服務(wù)通常也被稱為FIFORR（Round-Robin）時間片輪轉(zhuǎn)SPN(ShortestProcessNext)短進程優(yōu)先SRT(ShortestRemainingTime)最短剩余時間優(yōu)先HRRN(HighestResponseRatioNext)高響應(yīng)比優(yōu)先Feedback反饋2.9進程調(diào)度FCFS(First-Come-First-Served)ABCDE到達時間02468服務(wù)時間36452FCFS平均完成時間39131820周轉(zhuǎn)時間37912128.61.001.172.252.4062.562.9進程調(diào)度2.9進程調(diào)度2.9進程調(diào)度2.9進程調(diào)度Feedback2.9進程調(diào)度思考題：（華中科技大學(xué)2001考研）如下作業(yè)序列：作業(yè)1（提交時間8:00,運行時間1:00）,作業(yè)2（提交時間8:30,運行時間3:00）,作業(yè)3（提交時間9:00,運行時間0:10），作業(yè)4（提交時間9:30，運行時間0:50）。試用FCFS和STN算法調(diào)度該作業(yè)序列。并分析哪一種調(diào)度算法性能更好。2.9進程調(diào)度思考題：（北京大學(xué)1993考研）一個批處理系統(tǒng)各種，有兩個作業(yè)進程。有一個作業(yè)序列，到達時間和估計服務(wù)時間如下。系統(tǒng)采用最高響應(yīng)比有限的作業(yè)調(diào)度算法，作業(yè)進程的調(diào)度采用短作業(yè)有限的搶占式調(diào)度算法。請列出各作業(yè)的執(zhí)行情況表。ABCDE到達10:0010:1010:1510:2010:30服務(wù)35304520302.9進程調(diào)度思考題：（中科院1996考研）如下作業(yè)序列：有5個批處理作業(yè)（A,B,C,D,E）幾乎同時到達一個計算中心，估計的運行時間分別為2，4，6，8，10分鐘。它們的優(yōu)先級分別為1，2，3，4，5（1為最低優(yōu)先級）。對下面每種調(diào)度算法，分別計算作業(yè)的平均周轉(zhuǎn)時間。最高優(yōu)先級優(yōu)先時間片輪轉(zhuǎn)（時間片為2分鐘）FCFS。（到達順序為C,D,B,E,A）短作業(yè)優(yōu)先2.9進程調(diào)度實時系統(tǒng)調(diào)度非搶占式優(yōu)先權(quán)算法一旦將處理機分配給某個進程，則讓它一直運行直到結(jié)束。下次啟動調(diào)度程序時選擇優(yōu)先權(quán)最高的進程搶占式優(yōu)先權(quán)調(diào)度算法可以很快地?fù)屨糃PU資源2.9進程調(diào)度實時調(diào)度靜態(tài)表法靜態(tài)優(yōu)先級搶占法動態(tài)規(guī)劃法動態(tài)盡力調(diào)度2.9進程調(diào)度優(yōu)先級反轉(zhuǎn)如何避免優(yōu)先級反轉(zhuǎn)優(yōu)先級繼承優(yōu)先級天花板2.9進程調(diào)度1產(chǎn)生死鎖的原因競爭資源。(2)進程間推進順序非法。2.10死鎖1.競爭資源引起進程死鎖可剝奪和非剝奪性資源2)競爭非剝奪性資源3)競爭臨時性資源I/O設(shè)備共享時的死鎖情況進程之間通信時的死鎖2.進程推進順序不當(dāng)引起死鎖1)進程推進順序合法進程推進順序?qū)λ梨i的影響2)進