操作系統(tǒng)復(fù)習指導(dǎo),操作系統(tǒng)基本概念,操作系統(tǒng)是控制和管理計算機系統(tǒng)的硬件和軟件資源，合理地組織計算機工作流程及方便用戶使用的程序和數(shù)據(jù)的集合。,操作系統(tǒng)的功能和主要特征,主要功能: 處理機管理 存儲管理 設(shè)備管理 文件管理 用戶接口,主要特征 并發(fā)性 共享性 虛擬性 不確定性 （隨機性）,操作系統(tǒng)的結(jié)構(gòu),兩部分：內(nèi)核、核外部分。 內(nèi)核有兩種組織形式： 強內(nèi)核 微內(nèi)核,單用戶操作系統(tǒng) 批處理操作系統(tǒng) 分時操作系統(tǒng) 實時操作系統(tǒng) 網(wǎng)絡(luò)操作系統(tǒng) 分布式操作系統(tǒng) 多處理操作系統(tǒng),操作系統(tǒng)的分類,五大類型(批處理、實時、分時、網(wǎng)絡(luò)、分布),用戶與操作系統(tǒng)的接口,用戶與操作系統(tǒng)的三級接口 作業(yè)（命令）控制級接口 程序級接口 圖形級接口,四個概念: 系統(tǒng)態(tài)、用戶態(tài)、特權(quán)指令、訪管制令,作業(yè)的概念、組成以及作業(yè)控制塊的內(nèi)容,作業(yè)：由不同的順序相連的作業(yè)步組成。 作業(yè)步：在一個作業(yè)的處理過程中，計算機所做的相對獨立的工作。 作業(yè)流：一次有一批作業(yè)進入系統(tǒng)，并在操作系統(tǒng)控制下，一個接一個地順序進行處理。,作業(yè)由程序、數(shù)據(jù)和作業(yè)說明書三部分組成。,系統(tǒng)調(diào)用的概念 實現(xiàn)過程 與普通過程調(diào)用的區(qū)別,系統(tǒng)調(diào)用,定義：指系統(tǒng)為用戶程序調(diào)用操作系統(tǒng)核心中實現(xiàn)系統(tǒng)功能的過程（子程序）。,系統(tǒng)調(diào)用的實現(xiàn)過程,實際上系統(tǒng)調(diào)用語句本身是硬件提供的（機器指令），但其所調(diào)用的功能是操作系統(tǒng)提供的。每種機器的機器指令集中都有一條系統(tǒng)調(diào)用指令。,作業(yè)調(diào)度,作業(yè)調(diào)度性能衡量指標,(1)作業(yè)平均周轉(zhuǎn)時間T (Ti為每個作業(yè)的周轉(zhuǎn)時間；tc作業(yè)完成時刻；ts作業(yè)進入系統(tǒng)時刻),(2)平均帶權(quán)周轉(zhuǎn)時間W （Ti為每個作業(yè)的周轉(zhuǎn)時間；tr為作業(yè)實際運行時間）,作業(yè)調(diào)度算法,先來先服務(wù)（FCFS）：按照作業(yè)進入系統(tǒng)的先后次序進行調(diào)度，先進入系統(tǒng)者先調(diào)度；即啟動等待時間最長的作業(yè)。 短作業(yè)優(yōu)先（SJF）：以要求運行時間長短進行調(diào)度，即啟動要求運行時間最短的作業(yè)。,高響應(yīng)比優(yōu)先（HRF: Highest Response Ratio Next ）：響應(yīng)比最高的作業(yè)優(yōu)先啟動。 響應(yīng)比= 周轉(zhuǎn)時間 / 估計運行時間 =（等待時間+估計運行時間）/ 估計運行時間 = 1 + 等待時間 / 估計運行時間 高優(yōu)先級優(yōu)先（HPF：Highest Priority First）：由用戶指定作業(yè)優(yōu)先級，優(yōu)先級高的作業(yè)啟動。,假設(shè)在單道批處理環(huán)境下有四個作業(yè)，已知它們進入系統(tǒng)的時間、估計運行時間，應(yīng)用先來先服務(wù)、最短作業(yè)優(yōu)先和最高響應(yīng)比優(yōu)先作業(yè)調(diào)度算法，分別計算出作業(yè)的平均周轉(zhuǎn)時間和帶權(quán)的平均周轉(zhuǎn)時間。,最短作業(yè)優(yōu)先算法結(jié)果,最高響應(yīng)比優(yōu)先算法結(jié)果,先來先服務(wù)調(diào)度算法計算結(jié)果,順序程序特征： 程序執(zhí)行的順序性 程序執(zhí)行的封閉性 程序執(zhí)行結(jié)果的確定性（可再現(xiàn)性）,多道程序設(shè)計的特征 并發(fā)性 獨立性 動態(tài)隨機性 相互制約性,進程定義：Process 進程是一個具有一定獨立功能的程序在一個數(shù)據(jù)集合上的一次動態(tài)執(zhí)行過程，是系統(tǒng)進行資源分配和調(diào)度的獨立單位,進程,進程的組成要素： 用戶程序 用戶數(shù)據(jù) 進程控制塊PCB,進程的特征 動態(tài)性 獨立性 并發(fā)性、異步性 結(jié)構(gòu)化,進程與程序的區(qū)別 進程是動態(tài)的，程序是靜態(tài)的; 進程是暫時的，程序的永久的; 進程與程序的組成不同; 進程可以創(chuàng)建其它進程，而程序不能； 進程與程序的對應(yīng)關(guān)系：通過多次執(zhí)行，一個程序可對應(yīng)多個進程；通過調(diào)用關(guān)系，一個進程可包括多個程序。,系統(tǒng)為了管理進程設(shè)置的一個專門的數(shù)據(jù)結(jié)構(gòu)，存放了用于描述該進程情況和控制進程運行所需的全部信息。 系統(tǒng)利用PCB來控制和管理進程，所以PCB是系統(tǒng)感知進程存在的唯一標志。 進程與PCB是一一對應(yīng)的。,進程控制塊 (PCB, process control block),進程狀態(tài)轉(zhuǎn)換圖,中斷、 內(nèi)核、 原語,基本概念,處理機調(diào)度的層次,引進進程調(diào)度的時機,當一個進程運行完畢，或由于某種錯誤而終止運行 當一個進程在運行中處于阻塞狀態(tài)（等待I/O） 當有一個優(yōu)先級更高的進程就緒（可搶占式） 例如：新創(chuàng)建一個進程，一個等待進程變成就緒 在進程通信中，執(zhí)行中的進程執(zhí)行了某種原語操作（P操作，阻塞原語，喚醒原語） 分時系統(tǒng)中時間片到,常用進程調(diào)度算法,先進先出(FIFO)算法 最短CPU運行期優(yōu)先調(diào)度算法 最高優(yōu)先權(quán)優(yōu)先調(diào)度算法 時間片輪轉(zhuǎn)法 多級反饋隊列,線程的特點： 是進程的一個實體，可作為系統(tǒng)獨立調(diào)度和分派的基本單位。 不擁有系統(tǒng)資源（只擁有從屬進程的全部資源，資源是分配給進程） 一個進程中的多個線程可并發(fā)執(zhí)行。（進程可創(chuàng)建線程執(zhí)行同一程序的不同部分）,線程（Thread）,定義：是進程的一個實體，是CPU調(diào)度的基本單位。線程自己基本上不擁有系統(tǒng)資源，只留有幾個寄存器，但它可以與同屬同一個進程的其他線程共享進程所擁有的全部資源。,進程互斥：指在多道程序環(huán)境下，每次只允許一個進程對臨界資源進行訪問。 進程同步：指多個相關(guān)進程在執(zhí)行次序上的協(xié)調(diào)。 臨界資源:一次僅供一個進程使用的資源。 在進程中涉及到臨界資源的程序段叫臨界區(qū)。 多個進程的臨界區(qū)稱為相關(guān)臨界區(qū)。,進程互斥與同步機制,信號量及P.V操作,信號量的物理含義： S0表示有S個資源可用 S=0表示無資源可用 S<0則| S |表示S等待隊列中的進程個數(shù) P(S)：表示申請一個資源。 V(S)：表示釋放一個資源，信號量的初值應(yīng)該大于等于0。,P(S)： S=S-1; 若S0，則調(diào)用P(S)的進程繼續(xù)運行； 若S<0，則調(diào)用P(S)的進程被阻塞，并把它插入到等待信號量S的阻塞隊列中。 ,P操作的原語,V(S)： S=S+1; 若S0，則調(diào)用V(S)的進程繼續(xù)運行； 若S0，從等待信號量S的阻塞隊列中喚醒頭一個進程， 然后調(diào)用V(S)的進程繼續(xù)運行。,V操作的原語,利用P.V操作 實現(xiàn)進程的同步與互斥,司機與售票員問題 生產(chǎn)者與消費者問題,管程：把分散的各同類臨界區(qū)集中起來。并為每個可共享資源設(shè)立一個專門的機構(gòu)來統(tǒng)一管理各進程對該資源的訪問。,消息緩沖通訊技術(shù)的基本思想是：根據(jù)“生產(chǎn)者-消費者”原理，利用內(nèi)存中公用消息緩沖區(qū)實現(xiàn)進程的信息交換。,死鎖,概念：如果在一個進程集合中的每個進程都在等待只能由該集合中的其他一個進程才能引發(fā)的事件，則稱這一組進程或系統(tǒng)此時發(fā)生了死鎖。,四個必要條件： 互斥控制（資源獨占） 非剝奪控制（不可剝奪） 逐次請求（部分分配，占有申請） 環(huán)路條件（循環(huán)等待）,原因：系統(tǒng)資源不足； 進程推進順序不合適；,對死鎖的采取的對策,(1) 鴕鳥策略。 (2) 預(yù)防策略。 (3) 避免策略。 (4) 檢測和解除。,預(yù)防死鎖,破壞死鎖四個必要條件中的一個或多個，來防止死鎖。,解決方法： 靜態(tài)資源分配 資源有序分配法,系統(tǒng)中對進程發(fā)出的每一個系統(tǒng)能夠滿足的資源申請進行動態(tài)檢查，并根據(jù)檢查結(jié)果決定是否分配資源；如果分配后系統(tǒng)可能發(fā)生死鎖，則不予分配，否則予以分配。,避免死鎖,最具有代表性算法：銀行家算法。,例如，設(shè)系統(tǒng)中有 10 臺磁帶機，由三個進程A、B、C共享。假定A、B、C已分別占用了 2 臺、3 臺、3 臺，它們的最大需求量分別為4 臺、 6 臺、 8 臺。（假定只有當滿足了最大需求量后才能釋放所占用的全部資源。）,單項資源的銀行家算法,P2: 5 3 2 P4: 7 4 3 P1: 7 5 3 P3: 10 5 5 P5: 10 5 7,P2 P4 P1 P3 P5,多項資源的銀行家算法,地址變換(地址再定位,地址映射),直接指定方式:程序員在編序時或編譯程序?qū)υ闯绦蜻M行編譯時，所用的是實際存儲地址。 名空間程序 邏輯空間邏輯地址（相對地址，虛地址） 存儲空間物理地址（絕對地址，實地址）,邏輯地址（相對地址，虛地址）：用戶的程序經(jīng)過匯編或編譯后形成目標代碼，目標代碼通常采用相對地址的形式。 物理地址（絕對地址，實地址）：內(nèi)存中存儲單元的地址。物理地址可直接尋址。 地址映射：將用戶程序中的邏輯地址轉(zhuǎn)換為運行時由機器直接尋址的物理地址。,分區(qū)存儲管理,原理：把內(nèi)存分為一些大小相等或不等的分區(qū)，每個應(yīng)用進程占用一個或幾個分區(qū)。每個進程占據(jù)一個分區(qū)。 特點：適用于多道程序系統(tǒng)和分時系統(tǒng) 支持多個程序并發(fā)執(zhí)行 難以進行內(nèi)存分區(qū)的共享 問題：可能存在內(nèi)碎片和外碎片。 內(nèi)碎片：占用分區(qū)之內(nèi)未被利用的空間 外碎片：占用分區(qū)之間難以利用的空閑分區(qū)。,固定分區(qū),預(yù)先把可分配的主存儲器空間分割成若干個連續(xù)區(qū)域，稱為一個分區(qū)。每個分區(qū)的大小可以相同也可以不同，但分區(qū)大小固定不變，每個分區(qū)裝一個且只能裝一個作業(yè)。,相關(guān)技術(shù)： 覆蓋 交換,可變分區(qū),按空閑塊鏈接方式不同，有四種分配算法： 首次適應(yīng)法 下次適應(yīng)法（循環(huán)首次適應(yīng)法） 最佳適應(yīng)法 最壞適應(yīng)法,可再定位式分區(qū)和多重分區(qū) 概念和原理,分頁存儲管理,頁：把用戶程序按邏輯頁劃分成大小相等的部分。用戶程序分頁的劃分是由系統(tǒng)自動完成的，對用戶是透明的。一頁的大小為2的整數(shù)次冪。 內(nèi)存塊：按頁的大小劃分為大小相等的區(qū)域，稱為內(nèi)存塊（又叫物理頁面，頁框）。 內(nèi)存分配：以頁為單位進行分配，并按作業(yè)的頁數(shù)多少來分配。邏輯上相鄰的頁，物理上不一定相鄰，通過頁表把作業(yè)的各個頁面與內(nèi)存塊對應(yīng)起來。,頁面變換表,列出了作業(yè)的邏輯地址與主存中的物理地址間的對應(yīng)關(guān)系。 頁面大小: 頁面的大小應(yīng)適中，且頁面大小應(yīng)是2的冪 一個頁表中包含若干個表目，自然序號對應(yīng)于用戶程序中的頁號，塊號是該頁對應(yīng)的物理塊號。 頁面變換表的每一個表目除了包含指向頁框的指針外，還包括一個存取控制字段。,請求式分頁存儲管理,與純分頁存儲管理不同，請求式分頁管理系統(tǒng)在進程開始運行之前，不是裝入全部頁面，而是裝入一個或零個頁面，之后根據(jù)進程運行的需要，動態(tài)裝入其它頁面；當內(nèi)存空間已滿，而又需要裝入新的頁面時，則根據(jù)某種算法淘汰某個頁面，以便裝入新的頁面。,缺頁中斷 當要訪問的頁面不在內(nèi)存時，便產(chǎn)生一缺頁中斷，請求OS將所缺的頁面調(diào)入內(nèi)存。,頁面置換算法 ,先進先出置換算法 最近最久未用置換算法(LRU) 近似的LRU算法（NRU算法）,先進先出(FIFO)頁面置換算法,基本思想：置換時 首先淘汰在內(nèi)存中駐留時間最長的頁面，即最早進入主存的頁面。,FIFO M=3 缺頁中斷次數(shù)：F=9 缺頁率：f=9/12=75%,最近最久未用(LRU)置換算法,基本思想：當需要置換一頁時， 選擇在最近一段時間最久未用的頁予以淘汰。,LRU M=3 缺頁中斷次數(shù)：F=10 缺頁率：f=10/12=83%,分段存儲管理,原理：按程序自身的邏輯關(guān)系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段也從0開始編址，段內(nèi)地址是連續(xù)的。,內(nèi)存劃分 內(nèi)存空間被動態(tài)的劃分為若干個長度不相同的區(qū)域，稱為物理段，每個物理段由起始地址和長度確定。 內(nèi)存分配 以段為單位分配內(nèi)存，每一個段在內(nèi)存中占據(jù)連續(xù)空間（內(nèi)存隨機分割，需要多少分配多少），但各段之間可以不連續(xù)存放。,段表,記錄了段號，段的首（地）址和長度之間的關(guān)系。每一個程序設(shè)置一個段表，放在內(nèi)存， 屬于進程的現(xiàn)場信息。,分頁與分段的主要區(qū)別,段是信息的邏輯單位，它是根據(jù)用戶的需要劃分的，因此段對用戶是可見的；頁是信息的物理單位，是為了管理主存的方便而劃分的，對用戶是透明的。 頁的大小固定不變，由系統(tǒng)決定。段的大小是不固定的，它由其完成的功能決定。 段式向用戶提供的是二維地址空間，頁式向用戶提供的是一維地址空間，其頁號和頁內(nèi)偏移是機器硬件的功能。 由于段是信息的邏輯單位，因此便于存貯保護和信息的共享，頁的保護和共享受到限制。,段頁式存儲管理,段頁式管理吸收了分段的地址空間按邏輯意義分段的優(yōu)點和分頁在存儲空間管理上的優(yōu)點，不把段看成一個單一的連續(xù)整體來實現(xiàn)，而是將每個段分成若干頁面來管理。 進程的邏輯地址由三個部分組成：即段號s，頁號p，和頁內(nèi)相對地址w。,段表長度,段表控制寄存器,段表,內(nèi)存,起始地址,第0段頁表,第2段頁表,5,6,12,19,20,段頁式地址映像,段表長度指某個作業(yè)進程所含段的數(shù)量； 頁表長度指一個段所占用的頁的數(shù)量。,設(shè)備管理,設(shè)備的分類:按照功能、數(shù)據(jù)組織、資源分配和數(shù)據(jù)傳輸速率 設(shè)備的獨立性 設(shè)備的統(tǒng)一性,設(shè)備控制器的組成,程序直接控制方式。 (2) 程序中斷I/O方式。 (3) DMA方式。 (4) 通道方式。,I/O控制方式,DMA方式下的數(shù)據(jù)傳輸,通道分類: 字節(jié)多路通道 選擇通道 數(shù)組多路通道,通道,通道工作原理：CPU、通道,IO軟件的層次,中斷處理程序 設(shè)備驅(qū)動程序 與設(shè)備無關(guān)的I/O軟件 用戶層的輸入/輸出軟件,設(shè)備管理中的四種控制塊,I/O系統(tǒng)的設(shè)備分配 按如下步驟實施設(shè)備分配： 分配設(shè)備。 (2) 分配控制器。 (3) 分配通道。,I/O控制,單緩沖 雙緩沖 多緩沖 緩沖池,緩沖區(qū)管理,文件：是指具有符號名的數(shù)據(jù)信息的集合。 邏輯記錄：構(gòu)成文件內(nèi)容和對文件進行存取控制的基本單位。 文件系統(tǒng)：操作系統(tǒng)中負責管理和存取文件信息的軟件機構(gòu)，是對文件存儲器的存儲空間進行組織和分配，負責文件的存儲并對存入的文件進行保護和檢索的系統(tǒng)。,文件與文件系統(tǒng),文件的分類與邏輯結(jié)構(gòu),1）連續(xù)文件（順序結(jié)構(gòu)） 文件的信息存放在若干連續(xù)的物理塊中 2）串聯(lián)文件（鏈接結(jié)構(gòu)） 一個文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通過指針連接，前一個物理塊指向下一個物理塊 3）隨機文件（索引結(jié)構(gòu)） 一個文件的信息存放在若干不連續(xù)物理塊中，系統(tǒng)為每個文件建立一個專用數(shù)據(jù)結(jié)構(gòu)-索引表，并將這些塊的塊號存放在一個索引表中,文件的物理結(jié)構(gòu),文件控制塊（FCB）：文件控制塊是操作系統(tǒng)為管理文件而設(shè)置的數(shù)據(jù)結(jié)構(gòu)，存放了為管理文件所需的所有有關(guān)信息，是文件存在的標志。 文件目錄：把所有的FCB組織在一起，就構(gòu)成了文件目錄，即文件控制塊的有序集合 目錄項：構(gòu)成文件目錄的項目（目錄項就是FCB） 目錄文件：為了實現(xiàn)對文件目錄的管理，通常將文件目錄以文件的形式保存在外存，這個文件就叫目錄文件,概念,文件系統(tǒng)的層次結(jié)構(gòu),END!,