第三章 操作系统

第三章操作系統知識3.1基本要求1.學習目的與要求操作系統是一組程序,是為了提高系統資源的使用效率而且方便用戶使用的,這些程序可以是軟件也可以是固件.操作系統是計算機系統中硬件和軟件資源的總指揮,其性能的高低決定著整個計算機系統的能力是否充分發揮,操作系統也是軟件運行的平臺,操作系統的安全可靠程度,決定著整個計算機系統的安全性和可靠性通過本章的學習,可以掌握如下內容:⑴操作系統的概念,分類,功能和結構⑵處理機的管理和調度⑶實存管理,虛存組織和虛存管理⑷設備的分類,虛擬設備和設備管理⑸文件的邏輯結構,存儲結構和輔助存儲器管理⑹聯機處理與批處理,前臺與後臺⑺流行操作系統的體系結構,安裝與配置⑻操作系統的發展2.本章重點⑴操作系統的作用,類型,特徵,功能和結構⑵處理機管理相關概念,並行與幷發,單道與多道,進程與線程,同步與互斥,進程狀態和狀態轉換,處理機調度⑶存儲管理相關概念,實存與虛存,虛存組織,虛存管理⑷設備管理相關概念,設備的分類,虛擬設備,塊設備管理⑸文件管理相關概念,文件的邏輯結構與存儲結構,文件目錄,輔助存儲器管理⑹人機交互相關概念,聯機與批處理,前臺與後臺⑺流行操作系統的體系結構,安裝與配置⑻操作系統的發展情況3.2基本內容3.2.1基礎知識操作系統運行在計算機上,並且為其他軟件運行提供服務平臺1.操作系統的功能資源管理器—操作系統管理計算機系統的硬件資源虛擬計算機的實現—實現計算機軟件方面的功能⑴硬件資源處理器—處理器是計算機系統的一部份,能夠執行指令主存儲器—存儲數據和程序,輸入輸出(I/O)模塊—在計算機和外部環境之間傳遞數據外部設備—輔助存儲設備,如磁盤,磁帶,網絡等⑵資源管理擴充—從一個顯存的資源創建一個新資源,而且功能更強,更容易使用多路技術—從一個資源創建幾個資源的映射調度—決定哪個程序得到哪個資源,合適得到這個資源①擴充:即轉化,把複雜的硬件資源轉化為易用的虛擬資源②多路技術:計算機系統的物理資源是寶貴的,操作系統需要使眾多的應用程序共享物理資源,物理資源的共享稱為多路技術SPOOLONG方法,聯機的即時外圍設備操作時分多路技術,資源在不同時刻為不同的虛擬計算機服務,簡稱分時共享空分多路技術,資源被分為更小的單位,每一個虛擬計算機擁有資源的一部份,又稱空間分享③調度:確定把資源分配給哪個請求⑶虛擬計算機從單處理器創建多個進程,把他們分配給各個程序(時分)在內存中創建多個地址空間,把他們分配給程序(空分)實現文件系統和輸入輸出系統(空分磁盤空間和時分I/O頻道)2.虛擬計算機虛擬計算機是由軟件使用物理計算機的硬件資源實現的計算機,他和物理計算機一樣,分為處理器,內存,I/O和外設,沒一個虛擬機資源都是物理資源的轉化和多路技術的版本⑴虛擬處理器特權指令系統調用命令,允許用戶創建新的虛擬計算機(進程),和其他虛擬計算機之間的通信,請求所需的內存,進行I/O操作,訪問複雜的文件系統現代處理器提供了兩種模式:系統模式和用戶模式,在用戶模式下不允許訪問特權指令⑵虛擬主存⑶虛擬輔存⑷虛擬I/O3.硬件接口設備控制的基本技術是中斷⑴中斷的基本概念計算機系統中,中斷是改變處理器執行指令順序的事件,被打斷的程序可以在將來某個時候繼續執行計算機系統的中即來自系統內部,也來自系統外部,分別稱為內部中斷和外部中斷內部中斷是系統本身在工作過程中出現的各種需要緊急處理事件,一種是由於運行程序發生意外而產生的,如溢出,操作地址錯誤,常稱為例外中斷,一種是運行程序需要發生的,如系統調用.內部中斷也成軟中斷外部中斷是由於硬件方面的原因,也稱為硬件中斷,如掉電,設備運行完成,設備故障,時鐘中斷等,硬件中斷往往是隨機發生的,不由程序控制外部中斷和例外中斷常常稱為強迫中斷,由運行程序主動要求而產生的中斷稱為資源中斷外部中斷可分為可屏蔽和不可屏蔽中斷不可屏蔽中斷是一些最緊急最重要的中斷,如掉電可屏蔽中斷通過處理器內部的中斷處理許可狀態確定響應中斷的次序或者不響應⑵中斷的響應與處理引起中斷的事件(即原因)稱為中斷源,確定中斷的難易程度與硬件有關,目前大多數系統採用中斷向量技術中斷響應的另一個概念是程序狀態字PSW(Program Status Word),PSW是用來控制指令執行順序並且保留和指示與程序有關的系統狀態PSW包含的3部份程序基本狀態(指令地址,條件碼,處理器狀態)中斷碼(程序運行時,當前發生的中斷事件)中斷屏蔽位(指出程序運行中發生的中斷事件時,是否響應)每個程序都有一個程序狀態字來描述程序的運行狀態,一個處理器有一個用來存放當前運行程序的PSW寄存器中斷處理程序對中斷事件的處理分為兩步①保護好被中斷程序的現場信息,以保證被中斷程序能繼續運行②具體處理中斷4.操作系統接口一個系統調用按照以下步驟進行①程序執行系統調用②硬件保存當前指令地址(PC)和程序狀態字(PSW)到中斷指令地址和中斷程序狀態寄存器(PSWR)中③硬件加載PSW,并將處理器設置為不允許中斷的系統模式④硬件從系統調用中斷向量區域加載指令地址寄存器⑤指令的執行從系統調用中斷處理程序開始,中斷處理程序的地址就是系統調用中斷向量單元所指出的⑥系統條用完成,從保護的中斷指令地址和中斷程序狀態字中恢復指令地址和程序狀態字⑦繼續執行系統調用后的指令5.操作系統的發展⑴簡單的批處理系統這個時期的操作系統主要是爲了縮短作業之間的轉換而設計的⑵多道程序系統在主存中同時駐留多個作業,並且在他們之間切換處理機的使用稱為多道程序設計(MultiProgramming)或多任務處理(MultiTasking)⑶分時系統公用計算機服務系統,MULTICS⑷個人計算機和,分佈式操作系統和網絡系統微軟的Windows,Unix和Linux⑸嵌入式操作系統運行在嵌入式智能芯片環境中,對智能芯片及其控制的部件或裝置等資源進行統一協調,處理和控制的系統6.操作系統的結構⑴單體式系統整個操作系統是許多過程的集合,每個過程都可以調用任一其他過程,單體式操作系統的系統調用是通過自陷指令陷入內核實現的,在內核完成所有所需服務,返回結果給用戶進程⑵層次式系統上層軟件是基於下層的⑶客戶機/服務器系統現代操作系統的一個趨勢是從操作系統中去掉僅可能多的東西,而只留下一個最小的核心(常稱為微內核)微內核主要工作是提供進程間的通信,低級存儲器管理和基本中斷處理3.2.2進程描述與控制進程是資源分配和調度運行的基本單位1.進程的概念⑴進程的引入程序的順序執行,具有順序性,封閉性,可再現性多道程序的幷發性,具有間斷性,失去封閉性,不可再現性⑵進程的定義特特徵進程是程序的一次執行,是一個具有一定功能的程序關於某個數據集合的一次運行活動.進程具有4個基本特徵:動態性,幷發性,獨立性和異步性進程的狀態:就緒(Ready),執行(Running),阻塞(Blocked)⑶進程狀態的轉換2.進程描述進程控制塊PCB(Progress Control Block),PCB通常包括的信息:進程標識符,進程現行的狀態,處理機的現場保留區,進程相應的程序和數據地址,進程資源清單,進程優先級,進程同步與通信機制,進程所在隊列連接字和其他有關信息3.進程控制進程控制主要任務是對進程生命期控制和實現進程狀態的轉換進程控制原語是對進程生命期控制和進程狀態轉換的原語,他們是創建進程原語,撤銷進程原語,掛起進程原語,激活進程原語,阻塞進程原語和喚醒進程原語等4.線程的概念線程是進程中可獨立調度執行的子任務,一個進程可以有多個線程,他們共享所屬進程的地址空間等進程所擁有的資源3.2.3進程互斥與同步操作系統中,進程中進程互斥,同步機制的主要任務是控制幷發執行的個進程之間能有效地共享資源和相互協作,同時使幷發程序的執行任具有可再現性1.進程互斥一次只允許一個進程訪問的資源稱為臨界資源,訪問臨界資源的代碼段稱為臨界區關於互斥臨界區管理的要求是:空閒讓進,兩者擇一,忙則等待,有限等待2.互斥--------信號量機制荷蘭科學家Dijkstra提出的信號量(Semaphore)機制,是一種有效的進程互斥與同步的工具,被廣泛應用與單機系統和緊密耦合的多機系統⑴信號量的定義Typedef Struct Semaphore{int Value;PCB *P}S;除了信號量S初始化外,只能通過P(S)和V(S)兩種原語操作對信號量訪問,P 操作和V操作不會被打斷,P(Passeren)操作為通過的意思,V(Vrijgeven)操作為釋放的意思Void P(S){S.Value- -;if (S.Value<0)Block(S.P);}Void V(S){S.Value++;if (S.Value<=0)WakeUp(S.P);}用信號量來解決n個進程互斥進入臨界區對臨界資源的訪問問題.方法是:一,為N個進程設置一個互斥信號量二,控制互斥進程的流程,每個互斥進程在進入臨界區之前,先執行P()操作,表示申請進入臨界區,進程結束后,執行V()操作,表示退出臨界區例1生產圍棋的工人不小心把相等數量的黑子和白子混裝載一個箱子裏，現要用自動分揀系統把黑子和白子分開，該系統由兩個併發執行的進程組成，功能如下：（1）進程A專門揀黑子，進程B專門揀白子；（2）每個進程每次只揀一個子，當一個進程進程去揀子；Dim S As SemaphoreS=1Public Sub A()P(S)V(S)EndPublic Sub B()P(S)V(S)End例2某車站售票廳，任何時刻最多可容納20名購票者進入，當售票廳中少於20名購票者時，廳外的購票者可立即進入，否則需要在外面等待。

每個購票者可看成一個進程。

Dim S As SemaphoreS=20Public Sub A()P(S)進入售票廳購票退出V(S)End例3在某超市里有一個收銀員，且同時最多允許有n個顧客購物，我們可以將顧客和收銀員看成是兩類不同的進程，且工作流程如下圖所示。

為了利用PV操作正確地協調這兩類進程之間的工作，設置了三個信號量S1、S2和Sn，且初值分別為0、0和n。

這樣圖中的a應填寫__(1)__，圖中的b1、b2應分別填寫__(2)__，圖中的c1、c2應分別填寫__(3)__。

①P(Sn) ② V(S1) P(S2) ③ P(S1) V(S2)3.進程同步所謂進程同步是指多個合作進程為了完成同一個任務,他們在執行速度上必須相互協調,即一個進程的執行依賴于另一個進程的消息例1Dim SA,SB As SemaphoreDim x,y,Buffer As IntegerSA=1SB=0Public Sub A()P(SA)Buffer=xV(SB)EndPublic Sub B()P(SB)y=BufferV(SA)Print yEnd4.典型的同步與互斥問題⑴前驅圖問題所謂前驅圖就是由一個節點和有向邊構成的有向無環圖圖中每個節點是一個語句,一段程序或是一個進程Dim a,b,c,d,e,f,g,h,I,j As Semaphorea,b,c,d,e,f,g,h,I,j=0Begin{S1,V(a),V(b),V(c)}{P(a),S2,V(d)}{P(b),S3,V(e),V(f)}{P(c),S4,V(g)}{P(d),P(e),S5,V(h)}{P(f),P(g),S6,V(i)}{P(h),P(i),S7,V(j)}{P(j),S8}End⑵生產者—消費者問題(Producer-Consumer) Dim S1,S2,Empty,Full As SemaphoreS1=1,S2=1Empty=nFull=0Public Sub Produceri()P(S1)P(Empty)V(Full)V(S1)EndPublic Sub Consumeri()P(S2)P(Full)V(Empty)V(S2)End⑶哲學家進餐問題桌子上放著5把叉子,桌子中央有一盤通心粉,規定第i位哲學家坐在第i把椅子上,且每位哲學家坐定后,必須左右手分別獲得最靠近他的左右邊叉子時才能就餐,第i位哲學家重複這樣的過程,思考問題,當感到飢餓想進餐時,先申請左邊的叉子,拿到后再申請右邊的叉子,若左右手均拿到叉子則進餐,否則等待,進餐結束先放下左右邊的叉子Dim Chopsticks(5)=(1,1,1,1,1) As SemaphorePublic Sub Philosophyi()ThinkP(Chopsticks(i))P(Chopsticks((i+1) mod 5))EatV(Chopsticks(i))V(Chopsticks((i+1) mod 5))End如果每個人都想進餐,那麼會發生死鎖Dim Chopsticks(5)=(1,1,1,1,1) As SemaphoreDim Count=4 As IntegerPublic Sub Philosophyi()ThinkP(Count)P(Chopsticks(i))P(Chopsticks((i+1) mod 5))EatV(Chopsticks(i))V(Chopsticks((i+1) mod 5))V(Count)End⑷讀者----寫者問題5.進程通信進程通信是指進程間的信息交換6.消息傳遞系統⑴直接傳遞通信方式(消息緩衝)發送原語Send(Receive,Message)接收原語Receive(Sender,Message)⑵間接通信方式(信箱)系統為信箱提供了若干原語,用於信箱創建,撤銷,發送和接收7.管程信號量機制是解決進程互斥,同步的有效工具,但必須正確實現互斥,否則出現死鎖一個管程定義了一個數據結構和能為幷發進程調用在該數據結構上的一組操作管程結構中提供兩個同步操作原語Cwait和Csignal3.2.4存儲管理高效的內存管理是多道程序系統的關鍵1.存儲器管理的基本概念⑴存儲器的層次結構計算機系統中,採用三級存儲結構,即告訴緩存,內存和輔存內存中所有物理存儲單元的集合成為存儲空間,源程序經編譯產生的目標程序所涉及的地址範圍成為該作業的邏輯地址空間,當程序裝入內存時,必須把邏輯地址轉換為物理地址作業裝入內存的過程中一次行完成地址的轉換,稱為靜態重定位,而作業執行過程中,當訪問內存單元時才進行地址轉換的,成為動態種定位動態重定位的有點是,作業不要求分配連續的存儲空間,有利於程序段的共享,提高內存利用率⑵存儲管理的功能存儲管理的目的,是要僅可能方便用戶和提高內存的使用效率,存儲管理提供的功能有:內存的分配和回收,內存容量的擴充,地址轉換,存儲保護⑶虛擬存儲器虛擬存儲器是在操作系統的支持下,對內存和外存統一管理,達到擴充內存容量的目的2.連續分配存儲管理連續分配存儲器管理的基本思想是一道作業的全部內容(程序和數據)裝入到內存的一個連續存儲區中,這是實存管理技術,有單道連續分區管理,多道固定分區管理,多道可變分區管理⑴可變分區的分配算法最佳適應算法(Best Fit),最差適應算法(Worst Fit),首次適應算法(First Fit),下次適應算法(Next Fit)固定分區存儲管理方法會產生內碎片,可變分區存儲管理方法會產生外碎片,用拼接技術把存儲空間內的碎片合成一個大的空間,但移動作業需要代價很高⑵分區的存儲保護通常採用界限寄存器和存儲保護鍵兩種存儲保護界限寄存器有上,下界寄存器保護方案和基址,限長寄存器保護方案3.純分頁管理⑴分頁存儲管理的基本原理①作業邏輯地址空間分頁在分頁存儲管理中,當用戶作業對應一個邏輯地址空間裝入內存時,系統自動把他分成若干到校相等的片,稱為頁面②內存存儲空間分塊相應地,系統將內存空間也分成與頁面大小相同的若干個存儲塊,稱為物理塊,在為一個作業分配內存空間時,將作業所有的頁面分別裝入到內存中可不相鄰的若干物理塊③頁式邏輯地址的結構在分頁存儲管理中,地址結構由頁號和頁內地位移組成,假定一個邏輯地址空間的地址為A,也面的大小為L,則頁號P=int(A/L),頁內位移W=mod(A/L)④頁表在分頁系統中,允許將作業的各頁離散地放在內存的任一物理塊中,但系統應能保證作業的正確運行,為此,操作系統為每個作業建立一張頁面映射表,簡稱頁表,作用是實現頁號到塊號的轉換⑤地址轉換純分頁存儲管理採用動態重定位方式進行地址轉換⑵頁式地址轉換機構頁表基址寄存器,地址寄存器,物理地址寄存器,越界仲裁機構⑶頁式地址轉換過程⑷具有聯想存儲器的地址轉換機構由於頁表存放在內存中,這使CPU每次要存取一個數據時,都要兩次訪問內存,第一次訪問內存中的頁表,從中找到該頁的物理塊號,將此塊號與頁內位移拼接形成物理地址,第二次訪問內存,才得到所需數據,為了提高地址轉換速度,增設一個聯想寄存器,簡稱快表只需將作業的一部份頁表項放入快表,由於程序執行的局部性,快表的命中率任然非常高4.純分段存儲管理分段管理方便分段編程,實現分段共享,實現動態鏈接,允許分段的動態增長⑴分段系統的基本原理分段存儲管理中,作業的邏輯地址空間按邏輯劃分為若干段,每個段一組邏輯信息,例如,有主程序段,子程序段,數據段,棧段等,每個段都有自己的名字,每個段都是從0開始編址的一個連續地址空間,段的長度由相應的邏輯信息的實際長度決定,系統中用段號來代替段名,所以其邏輯地址由段號加段內位移組成⑵內存分配方式和段表在純分段存儲管理中,為作業的段在內存中分配一個連續的分區,但各個段所占的內存是離散的,作業被裝入時,操作系統為每個段一個唯一的段號,為使程序正常運行,在系統中為每個作業建立一張段映射表,簡稱段表,段表實現了邏輯段到物理地址的轉換(映射)⑶地址轉換一個邏輯地址(段號,段內位移)找到基址+段內位移得到物理地址⑷段式地址轉換機構實現邏輯地址(S,W)到物理地址的轉換,段式結構的聯想存儲器與頁表類似,用於存放最近常用的段表項⑸段的共享與保護5.請求分頁虛擬存儲管理⑴分頁虛擬存儲管理中的硬件支持請求分頁存儲管理建立在純分頁基礎上,是目前常用的一種實現虛擬存儲管理的技術,請求分頁,除了要一台具有較大內存及很大容量的快速外存的計算機系統外,還需要有頁表機制,缺頁中斷,和頁式動態地址轉換結構⑵缺頁中斷當訪問的頁面不在內存時,便產生一次缺頁中斷,操作系統將所缺的頁調入內存⑶地址轉換機構⑷兩級頁表⑸頁面置換算法在作業運行時,若其所要訪問的頁面不在內存而需要將它調入內存,但內存已無空閒空間時,爲了保證程序正常運行,系統必須根據一定的算法從內存選擇一頁淘汰,通常把選擇調出頁面的算法稱為頁面置換算法,為了對各種頁面置換算法進行比較,假定分配一個作業3個內存,并考慮下面的頁面訪問序列3,5,1,2,3,1,5,1,2,3,4,1,3,1,5①最佳置換算法(OPT,Optimal)最佳置換算法是選擇不再使用的,或者是在最久后才被訪問的頁面被淘汰,由於無法預知,因而該算法無法實現,可以作為一個標準去衡量其他算法缺頁率F=8/15=53%②先進先出算法(FIFO)FIFO是最早出現的頁面置換算法,該算法總是淘汰最先進入內存的頁面,即選擇在內存駐留時間最久的頁面缺頁率F=12/15=80%③最近最久未用頁面置換算法(Least Recently Used LRU)總是選擇在最近一段時間內最久未被訪問的頁面淘汰,需要設置計數器缺頁率f=11/15=75%④Clock置換算法⑤最近不使用置換算法(Not Used Recently NUR)⑹抖動和工作集模型作業運行時產生頻率非常高的頁面置換現象稱為抖動工作集模型是基於局部性原理假設的6.請求分段虛擬存儲管理⑴擴充的段表機制⑵缺段中斷機構⑶地址轉換機構7.段頁式虛擬存儲管理⑴作業地址空間和內存地址空間的劃分段頁系統中,一個作業地址空間被劃分為若干段,每一個段又劃分為若干個固定大小的頁⑵地址結構段頁式系統給作業地址空間增加了另一級結構,現在的地址由段號S,段內頁號P,頁內位移W組成⑶地址轉換機構每一個作業有一個段表,每一個段表有一個頁表⑷段頁式地址轉換機構3.2.5處理機管理1.調度的類型和模型調度有3類,作業,均衡和進程調度,又稱高級,中級和低級調度⑴作業狀態及其轉換從作業控制方式分析,作業分為批處理和交互型作業,批處理作業實體由用戶提交的程序文件,數據文件和作業說明書組成作業的4種狀態,提交狀態,後備狀態,運行狀態和完成狀態作業的運行狀態分為執行,就緒和阻塞⑵作業調度及其功能作業調度又稱高級調度或宏觀調度,是按照某種算法從後備作業中選擇作業裝入內存運行,當作業結束后做善後處理,具體完成的功能,選擇作業,分配資源,建立作業的進程,建立其他相關表格和作業後續處理⑶進程調度進程調度又稱低級調度,是按照某種算法選擇就緒狀態的進程使用處理機搶佔調度方式常用的調度原則:時間片原則,優先級原則,段進程優先原則⑷均衡調度均衡調度又稱中級調度,其目的是提高系統內存利用率和系統吞吐率2.調度算法的選擇和性能評價選擇調度算法通常考慮的是周轉時間和響應時間,周轉時間是作業提交到完成的時間間隔,響應時間是從作業提交到顯示結果或顯示提示的時間間隔具有一定的公平,實現簡單,缺點是不利於短作業T=7.6 W=1.98對長作業不利,對緊急作業進程不能及時處理兼顧長作業和段作業的算法T=8 W=2.14⑷優先級調度算法T=12 W=3.7⑸時間片輪轉調度算法⑹多級反饋隊列調度算法Windows NT就採用的是多級反饋隊列調度算法,能照顧到各種用戶的需要⑺實時調度算法目前大多數的實時控制系統,響應時間通常要求是幾百毫秒至幾十微妙,採用的調度算法有時間片輪轉,非搶佔的優先級調度,基於時鐘中斷搶佔的優先級調度,和立即搶佔的優先級調度3.2.6設備管理操作系統設計的外部設備,主要是各種人機交互設備或者是計算機與外界其他設備之間通信的設備按設備與主機之間數據傳輸的單位分:字符設備和塊設備按設備的讀寫物理特性分:順序設備和隨機設備按可否共享分:共享設備,獨佔設備和虛擬設備(SPOOLING)按主機控制設備的方式分:查詢式,中斷式,DMA式,I/O處理機按數據接口的傳方式分:串行設備和並行設備設備管理的主要任務是:提供一個統一的,友好的使用介面,為用戶隱藏各種不同設備使用上的差別,負責管理系統中的各種設備,根據各種設備的特點確定相應的分配策略,優化設備的調度,提高設備利用率.1.設備的獨立性設備獨立性又稱設備無關性,應用設備獨立於具體的物理設備,程序只需指明I/O使用的設備類而不能指定哪一台設備2.DMA技術現代計算機均採用DMA(Direct Memory Access)技術,CPU只須告訴DMA控制器:請把硬盤C上從扇區2000開始的400個扇區的數據讀到內存10000H開始的位置,DMA就開始做這份工作,CPU則可以轉而進行其他工作,等到數據傳輸完畢,DMA在通知CPU,這樣DMA就減輕了CPU的負擔,提高了計算機的整體性能DMA控制器通常採用總線浮起或週期挪用技術。