操作系统原理课件

操作系統的運行環境硬體環境操作系統與其它系統軟體的關係操作系統與人的介面任何系統軟體都是硬體功能的延伸操作系統直接依賴於硬體條件OS的硬體環境以較分散的形式同各種管理相結合實現操作系統時必須理解的電腦基本結構、操作系統管理的重要資源2.1硬體環境CPU、主存緩衝技術、中斷技術時鐘、時鐘佇列一、CPU專門設計了一系列基本機制：

-具有特權級別的處理器狀態，能在不同特權級運行的各種特權指令。

-硬體機制使得OS可以和普通程式隔離實現保護和控制1、特權指令與非特權指令特權指令：僅能為操作系統使用的指令。使用多道程序設計技術的電腦指令系統必須要區分為特權指令和非特權指令特權指令一般引起處理器狀態的切換2、處理機的狀態根據運行程式對資源和機器指令的使用權限將處理器設置為不同狀態多數系統將處理器工作狀態劃分為管態和目態管態：處理機執行操作系統程式時的工作狀態目態：處理機執行普通用戶程式時的工作狀態有些系統將處理器狀態劃分核心狀態，管理狀態和用戶程式狀態（目標狀態）三種實例：x86系列處理器支持4個處理器特權級別（R0、R1、R2和R3）從R0到R3特權能力依次降低R0相當於雙狀態系統的管態R3相當於目態R1和R2則介於兩者之間，它們能夠運行的指令集合具有包含關係：四個級別運行不同類別的程式：R0-運行操作系統核心代碼R1-運行關鍵設備驅動程式和I/O處理例程R2-運行其他受保護共用代碼，如語言系統運行環境R3-運行各種用戶程式現有的基於x86處理器的操作系統，多數UNIX、Linux以及Windows系列大都只用了R0和R3兩個特權級別實例：x86系列處理器管態和目態的差別處理器處於管態時：全部指令（包括特權指令）可以執行可使用所有資源並具有改變處理器狀態的能力處理器處於目態時：只有非特權指令能執行高特權級別對應的可運行指令集合包含低特權級3、程式狀態字PSW在PSW中專門設置一位，來判斷運行程式使用指令的許可權CPU的工作狀態碼——指明管態還是目態，用來說明當前在CPU上執行的是操作系統還是一般用戶，從而決定其是否可以使用特權指令或擁有其他的特殊權力條件碼——反映指令執行後的結果特徵中斷遮罩碼——指出是否允許中斷4、寄存器寄存器：指令在CPU內部作處理的過程中暫存數據、地址以及指令資訊的存儲設備

寄存器提供了一定的存儲能力速度比主記憶體快得多但是造價高，容量一般都很小兩類寄存器：用戶可見寄存器：由高級語言編譯器使用，以減少程式訪問主存次數控制和狀態寄存器：由操作系統使用,以控制其他程式的執行

用戶可見寄存器機器語言直接引用包括數據寄存器、地址寄存器以及條件碼寄存器數據寄存器（dataregister）又稱通用寄存器主要用於各種算術邏輯指令和訪存指令地址寄存器（addressregister）用於存儲數據及指令的物理地址、線性地址或者有效地址，用於某種特定方式的尋址。條件碼寄存器保存CPU操作結果的各種標記位。如算術運算產生的溢出、符號等控制和狀態寄存器用於控制處理器的操作大部分對於用戶是不可見的一部分可以在特權模式下訪問常見的控制和狀態寄存器:程式計數器PC：記錄將要取出的指令的地址指令寄存器IR：包含最近取出的指令程式狀態字PSW：記錄處理器的運行模式資訊二、主存支持OS運行硬體環境的一個重要方面：作業必須把它的程式和數據存放在主記憶體（記憶體）中才能運行多道程系統中，若干個程式和相關的數據要放入主記憶體操作系統要管理、保護程式和數據，使它們不至於受到破壞操作系統本身也要存放在主記憶體中並運行記憶體的類型：讀寫型、只讀型存儲分塊存儲保護界地址寄存器存儲鍵1、記憶體的類型兩類記憶體：讀寫型的記憶體（RAM）只讀型的記憶體（ROM）變型:PROM和EPROMPROM:可編程只讀記憶體，使用特殊PROM寫入器寫入數據EPROM:用特殊的紫外線光照射此晶片，以“擦去”資訊，恢復原來狀態，然後使用特殊EPROM寫入器寫入數據2、存儲分塊存儲最小單位:“二進位”最小編址單位:位元組主流個人電腦主存:128MB～512MB之間輔助記憶體:在20GB～70GB工作站、伺服器主存:512MB～4GB之間硬碟容量:數百GB為簡化分配和管理，將記憶體分成塊塊的大小：512B、1K、4K、8K3、存儲保護措施對主存中的資訊加以嚴格的保護，使操作系統及其它程式不被破壞，是其正確運行的基本條件之一多用戶,多任務操作系統：

OS給每個運行進程分配一個存儲區域問題：多個程式同時在同一臺機器上運行怎樣才能互不侵犯？

存儲保護措施：界地址寄存器、存儲鍵界地址寄存器優點機制比較簡單，易於實現實現方法：在CPU中設置一對上下限寄存器，分別存放用戶作業在主存中的上下限地址或將一個寄存器作為基址寄存器，另一寄存器作為限長寄存器CPU訪問主存時，硬體自動將被訪問的主存地址與界地址寄存器內容比較，判斷是否越界未越界：按此地址訪問主存越界：產生存儲保護中斷界地址寄存器存儲保護技術存儲鍵每個存儲塊有一個由二進位組成的存儲保護鍵當作業進入主存，OS分給它唯一的存儲鍵號將分配給該作業各存儲塊存儲鍵置成同樣鍵號當OS挑選該作業運行時，OS將它的存儲鍵號放入程式狀態字PSW存儲鍵域中當CPU訪問主存，將該主存塊的存儲鍵與PSW中的存儲鍵域進行比較如匹配，則允許訪問，否則，拒絕並報警

A塊B塊C塊001010100101000存儲鍵保護位鍵值為0~15，其中0號鍵為萬能鍵三、緩衝技術定義：外部設備在進行數據傳輸期間專門用於暫存這些數據的主存區域。緩衝技術三種用途:處理器與主記憶體之間處理器和其他外部設備之間設備與設備之間的通信目的：緩和CPU和外設的速度差異，減輕通道和外設的壓力。四、中斷技術中斷機制是操作系統得以正常工作的最重要的手段它使得OS可以捕獲普通程式發出的系統功能調用及時處理設備的中斷請求防止用戶程式中破壞性的活動等等五、時鐘時鐘為電腦完成的工作時鐘的概念：是硬體時鐘寄存器，按時鐘電路所產生的脈衝數對時鐘寄存器進行加1或減1的工作絕對時鐘：記錄當時時間

絕對時鐘準確，停機時絕對時鐘值仍然自動修改相對時鐘：通過時鐘寄存器實現設置時間間隔初值，每經過一個單位時間，時鐘值減1，直到該值為負時，觸發時鐘中斷，並進行相應中斷處理硬體時鐘：用某個寄存器來模擬（定時加1或減1）軟體時鐘：用記憶體單元來模擬時鐘。分配給每個進程一時間片。時間片到，發時鐘中斷，控制權交給操作系統。時鐘佇列：一種實現軟體時鐘的方法佇列頭指針A50B10C5D0X2.2、操作系統與其它系統軟體的關係

作業、作業步和進程重定位的概念絕對裝入程式和相對裝入程式一、作業、作業步和進程作業：用戶要求電腦所做的一個相對獨立的任務。

作業步：一個作業可劃分成若干部分，

每個部分稱為一個作業步。

典型的作業控制過程：“編譯”、“連接裝配”、“運行”

進程：OS將一個作業步劃分為若干作業步任務。

二、重定位的概念1、絕對地址、相對地址和邏輯地址空間絕對地址：主存單元的實際地址。相對地址：相對於某個基準量編址時用的地址。邏輯地址空間：目標程式所限定的地址集合。2、重定位用戶程式裝入記憶體時對有關指令地址的修改稱重定位技術。重定位分靜態重定位，動態重定位。靜態地址重定位在程式裝入主存過程中由裝配程式進行的重定位。動態地址重定位在程式執行過程中，每次訪存時將訪問的程式地址轉換成記憶體絕對地址。三、絕對裝入程式和相對裝入程式絕對裝入程式相對裝入程式如何識別需重定位的項裝入過程三、操作系統與人的介面操作系統提供兩個用戶介面：程式級：系統調用操作命令級：作業控制語言鍵盤命令圖形用戶介面（介面）1、作業控制語言：

一種語言，用來寫程式操作步驟的程式。在早期批處理操作系統中使用。用戶將自己的程式、數據和用作業控制語言編寫的上機操作的步驟的程式一起提交給計算中心（或機房），隔一段時間去機房取結果。2、鍵盤命令：

用戶通過鍵盤直接向電腦發佈各種命令。以互動式操作系統，分時操作系統為代表。分時操作系統誕生後，用戶可以通過用戶終端直接使用電腦，並且可與電腦“對話”，這就是所謂的互動式電腦。用戶可通過鍵盤直接向電腦發佈各種命令，電腦可接受、執行用戶命令。DOS系統把鍵盤命令分為：檔管理（COPY、COMP、TYPE、DEL、REN）磁片管理（FORMAT、CHKDSK、DISKCOPY、

DISKCOMP）目錄管理（DIR、CD、MD、RD、TREE）設備工作模式（CLS、MODE）日期、時間、系統設置（DATE、TIME、VER、VOL）運行用戶程式(MASM、LINK、DEBUG)3、圖形用戶介面（UNIX、WINDOWS）以窗口（windows）,圖示（icon）、菜單（menu）為典型特徵，由APPLE公司開創，以Microsoft公司的MS-Windows為里程碑，在UNIX系統下有X-window。4、系統調用：

直接在程式中使用OS命令，請求操作系統的服務。不同的操作系統，系統調用實現的具體方法有所不同，但其實質的特點是相同的：1、每個系統調用對應一個系統調用號；2、每個系統調用有一個對應的執行程式段；3、每個系統調用要求一定數量的輸入參數和返回值；4、整個系統有一個系統調用執行程式入口地址表；第3章進程管理進程的概念進程的狀態進程的描述與管理進程控制Windows2000/XP進程管理一、進程的概念進程的引入進程的定義進程和程式的關係1、進程的引入（一）程式的順序執行（二）程式的併發執行（一）程式的順序執行順序環境：在系統中只有一個程式在運行，該程式獨佔系統所有資源，其執行不受外界影響。特徵：程式執行的封閉性

獨佔資源，執行過程中不受外界影響程式執行結果的確定性

程式運行結果與程式執行速度無關，只要初始狀態相同，結果應相同（二）程式的併發執行併發環境：在一定時間內有兩個或兩個以上的程式同處於開始運行但尚未結束的狀態，並且次序不是事先確定的ABBAABAB

特徵：（1）程式結果的不可再現性

併發程式執行的結果與其執行的相對速度有關，是不確定的（2）在併發環境下程式的執行是間斷性的

執行——停——執行（3）資源共用

系统中资源被多个进程使用

（4）獨立性和制約性

独立的相对速度、起始时间

进程之间可相互作用（相互制约）

可分為直接作用和間接作用

（5）程式和程式的執行不再一一對應

2、進程（process）的定義程式在處理機上的執行。進程是一個可調度的實體。進程是這樣的計算，它可以與別的計算並行運行。進程是邏輯上的一段程式，它在每一瞬間都含有一個程式控制點，指出正在執行指令進程是一個具有獨立功能的程式關於某個數據集合的一次運行活動。父親食譜做蛋糕的原料CPU程式輸入數據進程：父親閱讀食譜，取各種原料，製作蛋糕

的一系列動作總和。急救手冊藥品進程：父親閱讀急救手冊，取藥品，為兒子

療傷的一系列動作總和。3、進程和程式的關係進程是一個動態概念，程式是靜態概念。程式可作為資料長期保存，進程有生命期，它能動態產生，消亡。進程的組成是程式，數據，PCB。同一程式運行於不同數據集合，將屬於不同進程。一個程式可對應多個進程，一個進程可包含多個程式。二、進程的狀態進程的狀態及變化進程的掛起和解掛1、進程狀態進程的基本狀態有三個：就緒狀態運行狀態等待狀態進程在生命消亡前處於且僅處於三種基本狀態之一不同系統設置的進程狀態數目不同運行態（Running）：

進程佔有CPU，並在CPU上運行就緒態（Ready）：

一個進程已經具備運行條件，但由於無CPU暫時不能運行的狀態（當調度給其CPU時，立即可以運行）等待態（Blocked）：

指進程因等待某種事件的發生而暫時不能運行的狀態（即使CPU空閒，該進程也不可運行）運行就緒等待進程的狀態及其轉換

就緒—運行

運行—就緒

運行—等待

等待—就緒就緒-->運行調度程式選擇一個新的進程運行運行-->就緒運行進程用完了時間片運行進程被中斷，因為一高優先順序進程處於就緒狀態進程狀態轉換：根據進程自身進展情況及外界環境的變化，三種狀態可以相互轉換運行-->等待當一進程必須等待時OS尚未完成服務對一資源的訪問尚不能進行初始化I/O且必須等待結果等待某一進程提供輸入(IPC)等待-->就緒當所等待的事件發生時2、進程的掛起與解掛進程掛起的原因進程的解掛具有掛起功能的進程狀態轉換五狀態轉換等待-->掛起等待當所有進程都阻塞，OS會安排空間讓一就緒進程進入記憶體掛起等待-->掛起就緒當等待的事件發生時(狀態資訊已在OS中)掛起就緒-->活動就緒當記憶體中沒有就緒進程時活動就緒-->掛起就緒當沒有被阻塞的進程，而為了性能上的考慮，必須釋放一些記憶體時三、進程的描述和管理1、進程的描述進程控制塊進程的組成2、進程的管理（1）進程控制塊

（PCB：ProcessControlBlock

）系統為了管理進程設置的一個專門的數據結構，用它來記錄進程的外部特徵，描述進程的運動變化過程系統利用PCB來控制和管理進程，所以PCB是系統感知進程存在的唯一標誌進程與PCB是一一對應的1、進程的描述進程映象(processimage)用戶程式用戶數據棧用於過程調用和參數傳遞進程控制塊PCB(執行上下文)控制進程所需的數據(進程屬性)，包括:進程識別字資訊處理器狀態資訊進程控制資訊PCB應包含以下三類資訊：進程標識資訊處理器狀態資訊進程控制資訊

進程標識資訊：本進程的標識ID索引至(直接或間接)主進程表創建本進程的某個進程的標識ID用戶標識與某個作業對應的用戶

處理器狀態資訊：用戶使用的寄存器控制和狀態寄存器堆疊指針進程控制資訊調度和狀態資訊進程狀態(如:運行，就緒，阻塞...)進程優先順序該進程在等待的事件(若被阻塞)數據結構資訊進程可能需要有指向其他PCB的指針,父-子進程關係及其它結構進程控制資訊(續)進程間通信IPC可能需要標誌和信號進程特權如:訪問特定的記憶體地址...存儲管理指向賦予該進程的段/頁表的指針所擁有的資源和使用情況使用中的資源:打開的檔，I/O設備...(CPU,I/O...)的時間使用史

進程控制塊的作用：記錄進程的屬性資訊，以便操作系統對進程進行控制和管理標誌進程的存在（2）進程的組成進程的組成：程式，數據。PCB2、進程管理

将PCB用適當的方法組織起來，把它們放在記憶體的固定區域，構成PCB表

PCB的組織方法：把所有不同狀態的進程的PCB組織在一張表格中。分別把有著相同狀態的進程的PCB組織在同一張表格中。分別把具有相同狀態的所有進程的PCB按優先數排成一個或多個佇列。四、進程的控制1、進程控制概念2、進程的控制原語3、進程切換4、操作系統的執行方式

1、進程的控制概念職責：對系統中所有進程實施有效管理，是處理機管理的一部分。任務：創建進程，撤銷進程，實現進程間轉換。進程控制由內核完成。內核有原語實現。原語：由若干條機器指令構成，用以完成特定功能的一段程式。原語操作具有不可分割性。2、進程的控制原語創建進程原語掛起進程原語解除掛起原語撤銷進程原語改變進程優先數原語創建進程原語創建一個PCB賦予一個統一進程識別字為進程分配空間初始化進程控制塊許多默認值(如:狀態為New，無I/O設備或檔...)設置相應的鏈接如:把新進程加到就緒佇列的鏈表中ProcedureCreate(n,s0,k0,m0,R0,acc)begini:=GetNewInternalName(n)；

id(i):=n；

Priority(i):=k0;Cpustate(i):=s0;MainStore(i):=m0;Resource(i):=R0;State(i):=‘Readys’;Parent(i):=*;SetAccountingData;insert(RL,i);end.掛起進程原語：掛起命令的執行：

把本命令的進程掛起

把具有指定識別字進程掛起

把某進程及其全部或部分子進程掛起進程的掛起完成下列狀態轉換：

就緒掛起就緒運行掛起就緒等待掛起等待ProcedureSuspend(n,a)begini:=GetInternalName(n);s:=State(i);Ifs=‘Running’ThenStop(i);a:=CopyPCB(i);Status(i):=Ifa=‘Blockeda’Then‘Blokeds’else‘Readys’;Ifs=‘Running’ThenSCHEDULERend.解掛原語解掛原語實現狀態的轉化：掛起就緒

就緒掛起等待

等待一個進程可掛起自己，但不能解掛自己。一個進程可掛起解掛自己子孫，但不能解掛別的族系進程。ProcedureResume(n);begini:=GetInternalName(n);Status(i):=IfStatus(i)=‘Readys’

then‘Readya’

else‘Blockeda’;

IfStatus(i)=‘Readya’thenSCHEDULERend撤銷進程原語：進程撤銷的原因：進程已完成所要求的功能而正常終止由於某種錯誤導致非正常終止祖先進程要求撤銷某個子進程進程撤銷的策略（兩種）撤銷原語一般由其父進程或祖先發出，不會自己撤銷自己ProcedureDestroy(n);beginSched:=false;i:=GetInternalName(n);kill(i);ifSched=truethenSCHEDULER;end(Destroy)Procedurekill(I);beginifStatus(i)=‘Running’thenbeginStop(i);Sched:=trueendRemve(Queue(i),i);forallSProgeny(i)doKill(s);forallrResources(i)doRELEASE(r);RELEASE(PCB(i));end(Kill)改變優先數原語優先數與下列因素有關：與作業靜態優先數有關。與進程類型有關：系統進程>I/O進程>CPU型進程與進程所用資源有關：占資源優先數與進程等待時間有關：等待時間優先數UNIX系統的優先數Pri=min{127,100+Pcpu/16+Pnice}Pcpu為每個進程使用及等待CPU時間相關的量。

運行進程：每隔20ms加1，直至255為止非運行進程：每秒減10，直至小於10為止Pnice由用戶通過系統調用設置的初值。ProcedureChangePriority(n);begini:=GetInternalName(n);a:=CalculatePriority(i);Pri(i):=a;IfStatus(i)=‘Readya’thenbeginInsert(RL,i,Pri);forallPRunningProcessQueuedo

IfPri(p)<Pri(I)thenSCHEDULERendend進程阻塞原語阻塞原語完成運行狀態等待狀態流程：入口保存當前CPU現場置該進程為阻塞狀態入等待佇列轉進程調度阻塞進程原語

輸入參數：無

返回参数：轉進程調度

功能：把現行進程的PCB置為“阻塞”狀態後

加入阻塞佇列。進程喚醒原語喚醒原語完成：

等待狀態就緒狀態掛起等待掛起就緒流程：入口判進程狀態是掛起阻塞？

N

Y

置狀態為掛起就緒置狀態為就緒入掛起就緒佇列入就緒佇列返回進程調度

喚醒進程原語

輸入參數：进程号

返回参数：成功或失敗標記

功能：把指定進程的PCB從阻塞佇列取出，改狀態為“就緒”後，列入就緒佇列。3、進程切換進程切換的概念：OS中斷現行進程，指定另一個進程為運行狀態。中斷進程執行的可能事件：

時鐘中斷、I/O中斷、記憶體、訪管中斷3、操作系統的執行方式非進程的內核方式用戶方式練習1．如果系統中有N個進程，運行的進程最多幾個，最少幾個；就緒進程最多幾個最少幾個；等待進程最多幾個，最少幾個？2.有沒有這樣的狀態轉換，為什麼？ 等待—運行；就緒—等待3.一個狀態轉換的發生，是否一定導致另一個轉換發生，列出所有的可能。4.請寫出阻塞原語和喚醒原語的程式描述。第4章線程線程的引入線程與進程的對比線程的實現1、線程的引入進程的兩個基本屬性：資源的擁有者：

給每個進程分配一虛擬地址空間，保存進程映像，控制一些資源（檔，I/O設備），有狀態、優先順序、調度調度單位：

進程是一個執行軌跡

以上兩個屬性構成進程併發執行的基礎線程的引入（續）系統必須完成的操作：創建進程撤銷進程進程切換缺點：

時間空間開銷大，限制併發度的提高線程的引入（續）在操作系統中，進程的引入提高了電腦資源的利用效率。但在進一步提高進程的併發性時，人們發現進程切換開銷占的比重越來越大，同時進程間通信的效率也受到限制線程的引入正是為了簡化進程間的通信，以小的開銷來提高進程內的併發程度線程的引入（續）線程：有時稱羽量級進程

進程中的一個運行實體是一個CPU調度單位資源的擁有者還是進程或稱任務線程的引入（續）線程：有執行狀態（狀態轉換）不運行時保存上下文有一個執行棧有一些局部變數的靜態存儲可存取所在進程的記憶體和其他資源可以創建、撤銷另一個線程線程和進程：單進程、單線程單進程、多線程多進程、一個進程一個線程多進程、一個進程多個線程PCB用戶棧單線程進程模型用戶地址空間核心棧線程式控制制塊：包含了寄存器映像，線程優先數和線程狀態資訊PCB多線程進程模型用戶地址空間用戶棧核心棧線程控制塊用戶棧核心棧線程控制塊用戶棧核心棧線程控制塊引入線程的好處：創建一個新線程花費時間少（結束亦如此）兩個線程的切換花費時間少（如果機器設有“存儲[恢復]所有寄存器”指令，則整個切換過程用幾條指令即可完成）同一進程內的線程共用記憶體和文件，它們之間相互通信無須調用內核適合多處理機系統例1：LAN中的一個檔伺服器，在一段時間內需要處理幾個檔請求方法：為每一個請求創建一個線程在一個SMP機器上：多個線程可以同時在不同的處理器上運行例2：一個線程顯示菜單，並讀入用戶輸入；另一個線程執行用戶命令一個應用：由幾個獨立部分組成，這幾個部分不需要順序執行，則每個部分可以以線程方式實現當一個線程因I/O阻塞時，可以切換到同一應用的另一個線程2線程與進程的比較調度併發性擁有資源系統開銷3線程的實現機制用戶級線程核心級線程兩者結合方法(1)用戶級線程（UserLevelThread）由應用程式完成所有線程的管理

核心不知道線程的存在線程切換不需要核心態特權調度是應用特定的對用戶級線程的核心活動核心不知道線程的活動，但仍然管理線程的進程的活動當線程調用系統調用時，整個進程阻塞但對線程庫來說，線程仍然是運行狀態

即線程狀態是與進程狀態獨立的用戶級線程的優點和缺點優點：線程切換不調用核心調度是應用程式特定的：可以選擇最好的演算法ULT可運行在任何操作系統上（只需要線程庫）缺點：大多數系統調用是阻塞的，因此核心阻塞進程，故進程中所有線程將被阻塞核心只將處理器分配給進程，同一進程中的兩個線程不能同時運行於兩個處理器上(2)核心級線程（KLT）所有線程管理由核心完成沒有線程庫，但對核心線程工具提供API核心維護進程和線程的上下文線程之間的切換需要核心支持以線程為基礎進行調度例子：WindowsNT，OS/2核心級線程的優點和缺點優點：對多處理器，核心可以同時調度同一進程的多個線程阻塞是線上程一級完成核心例程是多線程的缺點：在同一進程內的線程切換調用內核，導致速度下降(3)兩者分析針對不同的操作系統開銷和性能（線程的調度和切換速度）系統調用線程執行時間靈活性可擴充性搶佔CPU共用進程的資源(4)ULT和KLT結合方法線程創建在用戶空間完成大量線程調度和同步在用戶空間完成程式員可以調整KLT的數量可以取兩者中最好的線程庫由操作系統或某些語言提供，供所有用戶應用程式共用，並支持用戶應用程式創建、調度和管理自己的用戶級線程。（應用程式中用戶級線程的微內核）至少需提供以下功能的過程調用：建立線程、撤銷線程、阻塞線程、掛起線程、恢復線程、調度線程、線程間通訊原語、線程間同步原語WINDOWS2000/XP線程1、進程特點：進程是資源分配的基本單位，是作為對象進行管理的一個可執行的進程可能包含一個或多個線程WIN32進程控制系統調用有：CreateProcess、ExitProcess和TerminateProcess等2、進程對象每個進程由許多屬性定義，並且封裝了它可以執行的許多動作或服務進程進程ID安全描述符基本優先順序默認處理器仿射定額限制執行時間I/O計數器異常/調試端口退出狀態創建進程打開進程查詢進程資訊設置進程資訊當前進程終止進程對象類型對象體屬性服務3、線程對象線程線程ID動態優先順序基本優先順序線程處理器仿射線程執行警告狀態掛起計數器假冒標誌終止端口線程退出狀態創建線程打開線程查詢線程資訊設置線程資訊當前線程終止線程獲得上下文設置上下文掛起恢復警告線程測試線程警告寄存器終止端口對象類型對象體屬性服務4、線程狀態備用就緒運行轉換等待終止可運行選擇運行資源可用解除阻塞/恢復資源可用阻塞/掛起終止解除阻塞資源不可用不可運行切換剝奪第5章並行性：同步和互斥概述臨界段互斥信號量管程進程間的通信5.1概述並行技術的發展併發環境中進程間的關係進程同步進程互斥一、並行技術的發展多道程序設計多處理器系統分佈式處理系統二、併發環境中進程間的關係間接制約關係：源於資源共用直接制約關係：源於進程合作

三、進程同步同步關係：指散佈在不同進程中的若干程式片段，它們的運行必須嚴格按照規定的某種先後次序來進行，這種先後次序依賴於要完成的任務。同步機制：保證這種同步關係相應機制為同步機制。例：一個用戶作業：兩個矩陣求逆後相加加法進程求逆進程求逆進程進程之間有一定的先後執行次序例:

司机P1

售票員P2

while(true)while(true)

{{

启动车辆；关门；

正常运行；售票；

到站停車；開門；

}}

四、進程互斥互斥關係：（間接制約）指散佈在不同進程中的若干程式片段，當某個進程運行其中一個程式片段時，其他進程就不能運行它們中的任一程式片段，只能等到該進程運行完這個程式片段後才可運行。互斥可看成是一種特殊的同步關係。5.2臨界段臨界段的提出臨界段的互斥要求一、臨界段的提出兩個例子（進程的輸出結果取決於進程運行的精確時序）臨界資源：一次僅能為一個進程使用的資源。硬體資源：輸入機，印表機。軟體資源：變數，佇列，表格。臨界段：進程中訪問共用變數的代碼段。二、使用臨界段的原則：有空讓進：當無進程在臨界段時，任何有權使用臨界段的進程可進入無空等待：不允許兩個以上的進程同時進入臨界段多中擇一：當無進程在臨界段，而同時有多個進程要求進入臨界段，只能讓其中之一進入臨界段，其他進程須等待有限等待：任何進入臨界段的要求應在有限的時間內得到滿足讓權等待：處於等待狀態的進程應放棄佔用CPU，

以使其他進程有機會使用CPU5.3互斥進程互斥的解決方法：1、互斥的軟體方法2、互斥的硬體方法硬體方法允許在一個存儲週期內測試和修改一個字的內容，或者交換兩個字的內容，指令的執行不可中斷。TS指令SWAP指令開關中斷指令硬體解法(1)

“測試並設置”TS指令

functionTS(varflag:boolean):booleanbeginTS:=flag;flag:=true;end;

whileTS(lock)doskip;

臨界段

lock：=false;硬體解法(2)

“交換”SWAP指令procedureSWAP(vara,b:boolean)begintemp:=a;a:=b;b:=temp;end

key:=true;repeatSWAP(lock,key);untilkey=false;

臨界區

lock:=false;硬體解法(3)

“開關中斷”指令進入臨界區前執行：執行“關中斷”指令離開臨界區後執行：執行“開中斷”指令5.4信號量信號量概念信號量及同步原語信號量的應用一、信號量的概念1、概念：信號量表示資源的物理實體，是一個與佇列有關的整體變數，除對其初始化外，其值僅能由wait和signal兩種不可中斷的操作來改變。2、對信號量S的操作有兩個：wait與signal。(又稱同步原語）表示為wait(s),signal(s).二、信號量及同步原語1、信號量分類二元信號量：它允許取值僅為0，1，其初始值為1，主要用於解決進程互斥問題。一般信號量：取值不限於0和1，其初值為0或為某個正整數n，主要用於進程間的同步。2、同步原語的實現

同步原語的描述有兩種不同的形式：阻塞等待方式，忙等待方式。（1）阻塞等待方式WAIT（S）判斷S進程繼續阻塞該進程將進程插入S的等待佇列L中，重新調度SIGNAL（S）S=S+1判斷S進程繼續喚醒等待佇列中的一個進程，重新調度S>0S<0S<=0

S=S-1S>=0信號量的數據結構(將信號量定義進一步擴充）types=recordvalue:integer;L:pointertoPCB;指向等待佇列的指針

end一般信號量上的同步原語

wait(s):

s.value:=s.value-1;

ifs.value<0

thenbegin

Insert(CALLER,s.L);

Block(CALLER);

end

一般信號量上的同步原語

signal(s):

ifs.value=1

thenbegin

remove(s.L,id);

wakeup(id);

end

二元信號量上的同步原語

waitB(s):

ifs.value=1

then

s.value=0

elsebegin

Insert(CALLER,s.L);

Block(CALLER);

end二元信號量上的同步原語

signalB(s):

ifL.queueisempty

then

s.value=1

elsebegin

Remove(s.L,id);

wakeup(id);

end(2)忙等待方式一般信號量的同步原語二元信號量的同步原語WAIT（S）WAITB（S）

S0

SS-1N

S=0

SS-1NSIGNAL（S）SIGNALB（S）SS-1

SS-1

YY信號量定義為整型變數Wait(s):whiles<=0doskip; s:=s-1;signal(s):s:=s+1;

忙等待方式和阻塞方式的差別在於不會出現負值。阻塞等待方式適用於單處理機方式。忙等待方式適用於多處理機方式。(3)關於同步原語的討論1)信號量的物理含義：S>0表示有S個資源可用S=0表示無資源可用S<0則|S|表示S等待佇列中的進程個數wait(S):表示申請一個資源signal(S)表示釋放一個資源。信號量的初值應該大於等於02)wait,signal操作必須成對出現，有一個wait操作就一定有一個signal操作當為互斥操作時，它們同處於同一進程當為同步操作時，則不在同一進程中出現如果wait(S1)和wait(S2)兩個操作在一起，那麼wait操作的順序至關重要,而兩個signal操作無關緊要3）同步原語的優缺點優點：簡單，而且表達能力強缺點：不夠安全；同步原語使用不當會出現死鎖；遇到複雜同步互斥問題時實現複雜例：同步原語使用不當會造成死鎖A進程 B進程WAIT(S1) WAIT(S2)WAIT(S2) WAIT(S1)SIGNAL(S2) SIGNAL(S1)SIGNAL(S1) SIGNAL(S2)3、同步原語的不可分割性信號量上的同步原語應該是原子的操作保證進程間互斥地使用同步原語整體操作、不可分割、也就是不可打斷其執行或者說不可中斷三、信號量應用1、用信號量實現進程間的互斥2、用信號量實現進程間的同步1、用信號量實現進程間的互斥設置互斥信號量，賦初值1，表示臨界資源未被使用。進程描述例1設進程P，Q共用一臺印表機，印表機任何時刻只能被一個進程使用，而不能同時使用。試用同步原語描述進程，保證兩個進程不同時使用印表機。定義信號量S：表示印表機數目，初值為1；進程P：·

·

·

wait(s);

使用打印机

signal(s);例2設n個進程P1，P2，...，Pn共用m臺印表機，試用同步原語描述進程。

定義信號量S

進程描述2、用信號量實現進程間的同步例1：同步關係：P1-P2定義信號量進程描述

例2用同步原語解決司機與售票員的問題司機進程：while(true){啟動車輛正常駕駛到站停車}…售票員進程：while(true){關門售票開門}…有父母子女四人圍坐一起吃水果，父親不斷削蘋果往盆中放，母親不斷削梨往盆中放，女兒則從盆中取蘋果吃，兒子則從盆中取梨吃，假如盆中最多只能放N只水果，試用同步原語協調他們的關係。四、經典的進程同步問題1、生產者和消費者問題2、閱讀者和寫入者問題3、哲學家就餐問題1、生產者和消費者問題消費者生產者緩衝區1、生產者和消費者問題由n個緩衝區構成的一個緩衝記憶體，每個緩衝區可存放一個資料項目。生產者：生產數據並將其放入緩衝區中的進程。消費者：消耗並處理緩衝區中數據的進程。（1）設置信號量

mutex：保證對該緩衝記憶體的互斥執行。其初值為1。

E：表示空緩衝區數目，其初值為nF：表示滿緩衝區數目，其初值為0。

(2)進程同步關係描述

生產者進程消費者進程注意：兩個wait操作順序不能互換。例如：當mutex=1,E=0,F=n時，則對生產者進程：wait(mutex)成功，wait(E)失敗；對消費者進程：wait(F)成功，wait(mutex)失敗，形成互鎖。

(2)進程同步關係描述

生產者進程消費者進程注意：wait兩個操作不能互換。例如：當mutex=1,E=0,F=n時，則對生產者進程：wait(mutex)成功，wait(E)失敗；對消費者進程：wait(F)成功，wait(mutex)失敗，形成互鎖。注意：wait兩個操作不能互換。

例如：當mutex=1,E=0,F=n時，

則對生產者進程：wait(mutex)成功，wait(E)失敗；

對消費者進程：wait(F)成功，wait(mutex)失敗，形成互鎖。

2、閱讀者和寫入者問題一個數據集為若干併發進程共用。閱讀者：要求讀取數據寫入者：要求修改數據要求：允許多個閱讀者同時執行讀操作不允許閱讀者、寫入者同時操作不允許多個寫入者同時操作如果閱讀者來：1）無閱讀者、寫入者，新讀者可以讀2）有寫入者等，但有其他閱讀者正在讀，則新閱讀者也可以讀3）有寫入者寫，新閱讀者等如果寫入者來：1）無閱讀者、寫入者，新寫入者可以寫2）有閱讀者，新寫入者等待3）有其他寫入者，新寫入者等待（1）信號量設置：mutex:用於閱讀者互斥地訪問共用變數wrt:用於寫入者和其他進程互斥地訪問共用變數，初值為1。readcount普通整形變數，表示正在讀數據的閱讀者個數，初值為0。wait（mutex）readcount：=readcount+1IFreadcount=1THENwait（wrt）signal（mutex）讀數據wait（mutex）readcount；=readcount-1IFreadcount=0THENsignal（wrt）signal（mutex）（2）進程

同步關係描述

閱讀者進程寫入者進程

wait（mutex）

寫數據

signal（wrt）

3、哲學家就餐問題有五個哲學家，他們的生活方式是交替地進行思考和進餐，哲學家們共用一張圓桌，周圍放有五張椅子，每人坐一張，在圓桌上有五碗面和五個叉子。當哲學家思考時，他不與同事交談。饑餓時，便試圖取用左邊和右邊的叉子，他可能一個也拿不到，只有在他拿到兩個叉子時，方能就餐，吃完後，放下叉子又繼續思考。（1）信號量設置為每個叉子設置信號量：VARfork:array[0..4]ofsemaphore信號量的初值均為1。(2)進程描述（第I個哲學家的活動）

WAIT(fork[I])取左邊的叉子

WAIT(fork[(I+1)mod5])取右邊的叉子就餐

SIGNAL(fork[I])放下左邊的叉子

SIGNAL(fork[(I+1)mod5])放下右邊的叉子

思考五、管程1、管程的提出2、管程的定義3、用管程實現同步1、管程的提出

採用信號量來編寫併發程式，對於共用變數及信號量的操作將被分散於各個進程中缺點：（１）易讀性差，因為要瞭解對於一組共用變數及信號量的操作是否正確，則必須通讀整個系統或者併發程式（2）不利於修改和維護，因為程式的局部性很差，所以任一組變數或一段代碼的修改都可能影響全局（３）正確性難以保證，因為操作系統或併發程式通常很大，要保證這樣一個複雜的系統沒有邏輯錯誤是很難的2、管程的定義指關於共用資源的數據及在其上操作的一組過程或共用數據結構及其規定的所有操作管程是管理進程間同步的機制，它保證進程互斥地訪問共用變數，並且提供了一個方便的阻塞和喚醒進程的機構。管程的基本特性：局部於管程的數據只能被局部於管程內的過程所訪問一個進程只有通過調用管程內的過程才能進入管程訪問共用數據每次只允許一個進程在管程內執行某個內部過程管程的四個組成部分：管程的四個組成部分：名稱數據結構說明對該數據結構進行操作的一組過程/函數初始化語句3、用管程實現同步管程中支持同步的組成部分：局限於管程並僅能從管程內進行訪問的若干條件變數（Condition）在條件變數上進行操作的兩個函數過程

WaitC(C)和SignalC(C)WaitC(C):將調用此函數的進程掛起阻塞在與該條件變數C相關的佇列中，並使管程成為可用SignalC(C)：喚醒條件變數C的等待佇列中的某個進程；若等待佇列為空，則為空操作5.6進程間的通信一、進程通信的概念二、進程通信的實現三、間接通信模式四、其他通信模式一、進程通信的概念指在進程間交換一定數量的資訊。 信號量實現的是進程之間的低級通訊，只能傳遞簡單的信號，不能傳遞大量資訊。如果要在進程間傳遞大量資訊則要使用通信原語（Send/Receive原語）二、直接通信模式1、數據結構消息、消息緩衝、消息佇列2、通信原語發送原語：send接收原語：receivePCB......Send(R,M)......SIZE:消息長度TEXT:消息正文......消息鏈指針............Receive(pid,N)......SIZE:消息長度TEXT:消息正文......M:N:接受進程R發送進程S消息消息消息......三、間接通信模式發送進程發消息時不指定接收進程的名字，而是指定一個中間媒介，即信箱。進程間通過信箱實現通信

發送原語：send(MB,Message)

接收原語：receive(MB,Message)四、其他通信模式第6章多處理器系統和處理器管理調度的層次和作業調度單處理器系統的處理器調度多處理器系統對稱多處理器系統多處理器系統的處理器管理和調度6.1調度的層次和作業調度一、調度層次1、作業運行2、處理機調度3、處理機長期，短期調度關係1、作業運行

程式員操作員輸入機磁盤作業記憶體打印結束A

B

C

D作業狀態提交狀態（A）：用戶將作業交給機房，輸入輸入機。後備狀態（B）：作業資訊輸入輸入機，存放在磁片的某些盤區，等待操作系統接受。運行狀態（C）：作業被調度送入記憶體運行。完成狀態（D）：作業全部完成，釋放資源，退出系統。2、調度層次處理器調度分為三級：長期調度（作業調度）中期調度短期調度（進程調度）長期調度按某種原則挑選作業投入運行為作業創建進程為選中作業分配資源中期調度決定哪些作業允許參於競爭處理機資源。作用：起到短期調整系統負荷，以平順系統。方式：“掛起”，“解掛”。短期調度按某種原則將處理機分配給就緒進程。進程調度屬操作系統內核，執行頻率很高。3、處理機長期，短期調度關係

提交後備阻塞就緒運行

完成作業註冊作業調度進程調度作業終止

運行二、作業調度1、作業調度的職能2、作業控制塊3、調度性能的衡量1、作業調度的職能記錄已進入系統的作業情況JCB調度演算法：按照某種調度演算法從後備狀態挑選作業運行。運行準備：為選中作業創建進程，分配主存和外設。結束善後處理：收回資源，輸出必要資訊。作業進入後備狀態建立作業退出系統時撤銷2、作業控制塊作業存在唯一標誌作業調度的依據記錄作業的有關資訊，反映作業運行情況內容進入系統時建立退出系統時撤銷作業名資源要求資源使用情況類型說明狀態3、調度性能的衡量平均周轉時間：作業k的周轉時間Tk=完成時間-提交時間=等待時間+運行時間平均周轉時間T=Tk/作業數6.2單處理器系統的處理器調度處理器調度的主要功能：按一定的演算法，動態地把處理機分配給就緒佇列中的某個進程1、選擇調度演算法時應考慮的問題設計目標資源利用率均衡地處理系統和用戶要求優先順序可搶佔和不可搶佔2、調度演算法先進先服務調度演算法最短作業優先調度演算法時間片輪轉演算法優先順序調度演算法最短剩餘時間優先調度演算法最高回應比優先多級回饋佇列調度演算法(1)先進先出調度演算法其原則按照作業到達系統或進程進入就緒佇列先後次序來選擇。FIFO是一種非搶佔演算法。例題進程到達時間服務時間優先數10322265344346565821作業1作業2作業3作業4作業5039131820平均周轉時間T=1/5（3+7+9+12+12）=8.60（2）短作業優先調度演算法根據JCB估算運算時間，選取最短作業為調度對象短作業優先調度是非搶佔演算法。缺點：會使長作業饑餓。作業1作業2作業5作業3作業4039111520T=1/5（3+7+11+14+3）=7.60（3）時間片輪轉調度演算法把CPU的時間分割成時間片，處於就緒狀態的進程輪流獲得時間片。時間片輪轉調度演算法是搶佔演算法。其調度演算法的性能取決於時間片Q。Q=4（時間片為4）作業1作業2作業3作業4作業5作業2作業40371115171920T=1/5（3+17+7+14+9）=10.00（4）優先順序調度演算法選擇優先數高的進程和作業作為調度對象。按搶佔與否優先數可分：非搶佔的優先調度演算法可搶佔的優先調度演算法按靜態，動態優先數可分：靜態優先數動態優先數非搶佔的優先調度作業1作業2作業4作業3作業5039141820

T=1/5（3+7+14+8+12）=8.8可搶佔的優先調度作業1作業2作業4作業2作業3作業1作業50261113171820

T=1/5（18+11+13+5+12）=11.8（5）最短剩餘時間優先調度演算法基本思想：讓從運行到完成所需時間最短的作業優先得到處理。最短剩餘時間：從作業當前運行到完成所需時間。最短剩餘時間優先調度是搶佔演算法。用於分時系統其輪轉時間最優作業1作業2作業3作業5作業2作業40348101520T=1/5（3+13+4+14+2）=7.20（6）最高回應比優先回應比=等待時間+服務時間服務時間最高回應比是FIFO和短作業優先的折中。最高回應比是一種非搶佔演算法。作業1作業2作業3作業5作業4039131520T=1/5（3+7+9=9+12）=8.00（8）多級回饋佇列調度演算法系統中有多個就緒佇列各級就緒佇列具有不同的時間片各級佇列均按FIFO原則排隊調度方法：首先調度優先順序高的進程，當優先順序高的進程為空，才調度下一級。例題進程到達時間服務時間優先數10322265344346565821作業名到達時刻完成時刻運行時間

J1022

J223 1

J143

J3451

J262

J4671

J382

J5891

J4102

J5112

J2123

J3133

J4143

J2154

J3164

J4174

J2185

J4 195

J2206Q=1（每級回饋佇列每一級時間片為1）1121324354523423424201234567891011121314151617181920T=1/5（4+18+12+13+3）=10.00Q=2**N（每級回饋佇列每一級時間片以2冪次方遞增）1121322453344522234401234567891011121314151617181920T=1/5（4+15+14+14+6）=10.06生產圍棋的工人不小心把相等數量的黑子和白子混在一塊