操作系統(tǒng)期末復(fù)習(xí)資料(1)

版本 V3 4 概念題概念題 理解進程的定義 進程的組成 對進程的管理和控制使用的是什么 理解進程的定義 進程的組成 對進程的管理和控制使用的是什么 進程是指在系統(tǒng)中能獨立運行并作為資源分配的基本單位 它是由一組機器指令 數(shù)據(jù)和堆棧等組成的 是 一個能獨立運行的活動實體 進程控制一般是由 OS 的內(nèi)核中的原語來實現(xiàn)的 原語原語 原語 Primitive 是由若干條指令組成的 用于完成一定功能的一個過程 具有不可分割性 即原語的執(zhí) 行必須是連續(xù)的 在執(zhí)行過程中不允許被中斷 管程管程 代表共享資源的數(shù)據(jù)結(jié)構(gòu) 以及由對該共享數(shù)據(jù)結(jié)構(gòu)實施操作的一組過程所組成的資源管理程序 共 同構(gòu)成了一個操作系統(tǒng)的資源管理模塊 我們稱之為管程 死鎖死鎖 所謂死鎖 是指多個進程在運行過程中因爭奪資源而造成的一種僵局 當(dāng)進程處于這種僵局狀態(tài)是 若無外力作用 它們都將無法再向前推進 死鎖四個條件死鎖四個條件 互斥條件 請求和保持條件 不剝奪條件 環(huán)路等待條件 臨界資源臨界資源 把在一段時間內(nèi)只允許一個進程訪問的資源稱為臨界資源或獨占資源 每個進程中訪問臨界資源 的那段代碼稱為臨界區(qū) 臨界區(qū) 屬于臨界資源的硬件有打印機 磁帶機等 軟件有消息緩沖隊列 變量 數(shù)組 緩沖 區(qū)等 諸進程間應(yīng)采取互斥方式 實現(xiàn)對這種資源的共享 SPOOLing 是關(guān)于慢速字符設(shè)備如何與計算機主機交換信息的一種技術(shù) 通常稱為 假脫機技術(shù) 虛擬存儲器虛擬存儲器 所謂虛擬存儲器 是指具有請求調(diào)入功能和置換功能 能從邏輯上對內(nèi)存容量加以擴充的一種 存儲器系統(tǒng) 事事務(wù)務(wù) 事務(wù)是用于訪問和修改各種數(shù)據(jù)項的一個程序單位 事務(wù)也可以被看做是一系列相關(guān)讀和寫操作 操作系統(tǒng)的基本類型操作系統(tǒng)的基本類型 批處理操作系統(tǒng) 分時操作系統(tǒng) 實時操作系統(tǒng) 操作系統(tǒng)的基本特性操作系統(tǒng)的基本特性 并發(fā)性 共享性 虛擬技術(shù)和異步性 用戶與操作系統(tǒng)之間的接口用戶與操作系統(tǒng)之間的接口 用戶接口和程序接口 進程同步的主要任務(wù)進程同步的主要任務(wù)是為多個進程 含線程 的運行進行協(xié)調(diào) 兩種協(xié)調(diào)方式 兩種協(xié)調(diào)方式 進程互斥方式和進程同步方式 進程的三種基本狀態(tài)轉(zhuǎn)換進程的三種基本狀態(tài)轉(zhuǎn)換 就緒狀態(tài) 執(zhí)行狀態(tài) 阻塞狀態(tài) 線程與進程的區(qū)別 線程與進程的區(qū)別 調(diào)度調(diào)度 在傳統(tǒng)的操作系統(tǒng)中 作為擁有資源的基本單位和獨立調(diào)度 分派的基本單位都是進程 而在引 入線程的操作系統(tǒng)中 則把線程作為調(diào)度和分派的基本單位 而進程作為資源擁有的基本單位 把傳統(tǒng) 進程的兩個屬性分開 從而可顯著地提高系統(tǒng)的并發(fā)程度 在同一進程中 線程的切換不會引起進程的 切換 但從一個進程中的線程切換到另一個進程中的線程時 將會引起進程的切換 就緒 阻塞執(zhí)行 時間片完 進程調(diào)度I O完成 I O請求 版本 V3 4 并發(fā)性并發(fā)性 在引入線程的操作系統(tǒng)中 不僅進程之間可以并發(fā)執(zhí)行 而且在一個進程中的多個線程之間亦 可并發(fā)執(zhí)行 使得操作系統(tǒng)具有更好的并發(fā)性 從而能更加有效地提高系統(tǒng)資源的利用率和系統(tǒng)的吞吐 量 擁有資源擁有資源 不論是傳統(tǒng)的操作系統(tǒng) 還是引入了線程的操作系統(tǒng) 進程都可以擁有資源 是系統(tǒng)中擁有 資源的一個基本單位 一般而言 線程自己不擁有系統(tǒng)資源 但它可以訪問其隸屬進程的資源 系統(tǒng)開銷系統(tǒng)開銷 在創(chuàng)建或撤消進程時 系統(tǒng)都要為之創(chuàng)建和回收進程控制塊 分配或回收資源 操作系統(tǒng)所 付出的開銷明顯大于線程創(chuàng)建或撤消時的開銷 類似地 在進程切換時 涉及到當(dāng)前進程 CPU 環(huán)境的保 存及新被調(diào)度運行進程的 CPU 環(huán)境的設(shè)置 而線程的切換則僅需保存和設(shè)置少量寄存器內(nèi)容 不涉及存 儲器管理方面的操作 所以就切換代價而言 進程也是遠高于線程的 此外 在同步和通信的實現(xiàn)方面 線程也比進程容易 處理機調(diào)度的處理機調(diào)度的 3 種調(diào)度是什么及其調(diào)度對象分別為什么種調(diào)度是什么及其調(diào)度對象分別為什么 填空題 選擇題 高級調(diào)度是作業(yè) 低級調(diào)度是進程 或內(nèi)核級線程 中級調(diào)度是外存中暫時不能運行而被掛起的進程 了解基本的作業(yè)調(diào)度和進程調(diào)度算法了解基本的作業(yè)調(diào)度和進程調(diào)度算法 先來先服務(wù)算法 FCFS 最短作業(yè)優(yōu)先算法 SJF 高優(yōu)先權(quán)優(yōu)先調(diào)度算 法和基于時間片輪轉(zhuǎn)算法 填空題 選擇題 P91 操作系統(tǒng)的定義操作系統(tǒng)的定義 是配置在計算機硬件上的第一層軟件 是對硬件系統(tǒng)的首次擴充 它在計算機系統(tǒng)中占據(jù)了 特別重要的地位 操作系統(tǒng)的主要功能 從資源管理的角度 操作系統(tǒng)的主要功能 從資源管理的角度 處理機管理 存儲器管理 設(shè)備管理和文件管理 理解并發(fā)進程的特征 與順序程序設(shè)計相比 理解并發(fā)進程的特征 與順序程序設(shè)計相比 在多道程序環(huán)境下 程序的執(zhí)行屬于并發(fā)執(zhí)行 此時它們將 失去其封閉性 并具有間斷性間斷性及不可再現(xiàn)性不可再現(xiàn)性的特征 在多道程序設(shè)計系統(tǒng)中 并發(fā)進程之間可能存在的兩種制約關(guān)系在多道程序設(shè)計系統(tǒng)中 并發(fā)進程之間可能存在的兩種制約關(guān)系 間接相互制約關(guān)系和直接相互制約關(guān)系 間接相互制約關(guān)系 同處于一個系統(tǒng)中的進程 通常都共享著某種系統(tǒng)資源 如共享 CPU 共享 I O 設(shè) 備等 所謂間接相互制約即源于這種資源共享 例如 有兩個進程 A 和 B 如果在 A 進程提出打印請求 時 系統(tǒng)已將惟一的一臺打印機分配給了進程 B 則此時進程 A 只能阻塞 一旦進程 B 將打印機釋放 則 A 進程才能由阻塞改為就緒狀態(tài) 直接相互制約關(guān)系 這種制約主要源于進程間的合作 例如 有一輸入進程 A 通過單緩沖向進程 B 提供 數(shù)據(jù) 當(dāng)該緩沖空時 計算進程因不能獲得所需數(shù)據(jù)而阻塞 而當(dāng)進程 A 把數(shù)據(jù)輸入緩沖區(qū)后 便將進 程 B 喚醒 反之 當(dāng)緩沖區(qū)已滿時 進程 A 因不能再向緩沖區(qū)投放數(shù)據(jù)而阻塞 當(dāng)進程 B 將緩沖區(qū)數(shù)據(jù) 取走后便可喚醒 A 同步機制應(yīng)遵循基本準(zhǔn)則 臨界區(qū)調(diào)度原則 同步機制應(yīng)遵循基本準(zhǔn)則 臨界區(qū)調(diào)度原則 空閑讓進 忙則等待 有限等待 讓權(quán)等待 信號量信號量 1 一種是用于實現(xiàn)進程互斥的信號量 初值一般為 1 2 另一種是用于解決進程同步的信號量 初值表示資源的數(shù)量 填空題 選擇題 例 對于兩個并發(fā)進程都想進入臨界區(qū) 設(shè)互斥信號量為 S 若某時 S 0 表示有 1 個進程進入了臨界區(qū) 4 種常用的種常用的 I O 控制方式控制方式 程序 I O 方式 中斷驅(qū)動 I O 方式 直接存儲器訪問 I O 方式 I O 通道控制方式 版本 V3 4 通道通道 通道是通過執(zhí)行通道程序 并與設(shè)備控制器共同實現(xiàn)對 I O 設(shè)備的控制的 了解常用的緩沖技術(shù)的作用 了解常用的緩沖技術(shù)的作用 1 緩和 CPU 與 I O 設(shè)備間速度不匹配的矛盾 2 減少對 CPU 的中斷頻率 放寬對 CPU 中斷響應(yīng)時間的限制 3 提高 CPU 和 I O 設(shè)備之間的并行性 文件系統(tǒng)的主要功能 文件系統(tǒng)的主要功能 文件系統(tǒng)的管理功能 是通過把它所管理的程序和數(shù)據(jù)組織成一系列文件的方法來 實現(xiàn)的 文件目錄的作用 文件目錄的作用 文件目錄是一種數(shù)據(jù)結(jié)構(gòu) 用于標(biāo)識系統(tǒng)中的文件及其物理地址 供檢索時使用 6 重定位的定義 重定位就是把程序的邏輯地址空間變換成內(nèi)存中的實際物理地址空間的過程 也就是說在裝 入時對目標(biāo)程序中指令和數(shù)據(jù)的修改過程 7 重定位的方式有哪兩種 比較它們的不同 重定位有靜態(tài)和動態(tài)兩種情況 所謂靜態(tài)重定位是在裝入一個作業(yè)的時候 把作業(yè)中的指令地址和數(shù)據(jù)地址全部一次性 地轉(zhuǎn)換成絕對地址 所謂動態(tài)重定位是由軟件和硬件相配合來實現(xiàn)的 地址重定位不再是裝入的時候一次完 成了 而是設(shè)置一個基址寄存器 裝入作業(yè)的時候 將作業(yè)在主存區(qū)域的首地址放入到基址 寄存器中 作業(yè)執(zhí)行的時候 由硬件的地址轉(zhuǎn)換機構(gòu)動態(tài)地對地址進行轉(zhuǎn)換 執(zhí)行指令的時 候 只要將邏輯地址加上基址寄存器的內(nèi)容 就得到了絕對地址 靜態(tài)重定位和動態(tài)重定位的不同在于 靜態(tài)重定位是在作業(yè)裝入的時候一次完成 動 態(tài)重定位是在作業(yè)執(zhí)行時再實現(xiàn)的 靜態(tài)重定位是軟件支持的 動態(tài)重定位是硬件和軟件 合作實現(xiàn)的 靜態(tài)重定位不能實現(xiàn)主存的移動 而動態(tài)重定位可以 動態(tài)重定位還可能 提供虛擬存儲空間 版本 V3 4 算法題算法題 生產(chǎn)者與消費者問題生產(chǎn)者與消費者問題 P58 利用記錄型信號量解決生產(chǎn)者 消費者問題 Var mutex empty full semaphore 1 n 0 buffer array 0 1 n 1 of item in out integer 0 0 begin parbegin producer begin repeat producer an item in nextp wait empty wait mutex buffer in nextp in in 1 mod n signal mutex signal full until false end consumer begin repeat wait full wait mutex nextc buffer out 版本 V3 4 out out 1 mod n signal mutex signal empty consumer the item in nextc until false end parend end 利用 and 信號量解決生產(chǎn)者 消費者問題 Var mutex empty full semaphore 1 n 0 buffer array 0 1 n 1 of item in out integer 0 0 begin parbegin producer begin repeat produce an item in nextp Swait empty mutex buffer in nextp in in 1 mod n Ssignal mutex full until false end consumer begin 版本 V3 4 repeat Swait full mutex Nextc buffer out Out out 1 mod n Ssignal mutex empty consumer the item in nextc until false end parend end 銀行家算法銀行家算法 P115 在銀行家算法中 若出現(xiàn)下述資源分配情況 ProcessAllocationNeedAvailable P0003200121622 P110001750 P213542356 P303320652 P400140656 1 該狀態(tài)是否安全 2 若進程 P2 提出請求 Request 1 2 2 2 后 系統(tǒng)能否將資源分配給它 解 1 該狀態(tài)是安全的 因為存在一個安全序列 安全列表 資源情況進程WorkNeedAllocationWork AllocationFinsh P01622001200321654true P31654065203321986true P41986065600141 9 9 10true P11 9 9 10175010002 9 9 10true 版本 V3 4 P22 9 9 10235613543 12 14 14true 2 不能 若分配進程 P2 系統(tǒng)還剩的資源情況為 0 4 0 0 此時系統(tǒng)中的資源將無法滿足任何一個進程的資 源請求 從而導(dǎo)致系統(tǒng)進入不安全狀態(tài) 容易引起死鎖發(fā)生 邏輯地址變換為物理地址的過程邏輯地址變換為物理地址的過程 P132 1 分頁地址變換機構(gòu)會將有效地址分為頁號和頁內(nèi)地址 再以頁號為索引去檢索頁表 2 如果頁號大于或等于頁表長度就產(chǎn)生地址越界中斷 3 表項在頁表中的位置 頁表始址 頁號 頁表項長度 讀出物理塊號裝入物理地址寄存器 4 將頁內(nèi)地址送入物理地址寄存器的塊內(nèi)地址字段中 最佳最佳 Optimal 先進先出先進先出 FIFO 頁面置換算法頁面置換算法 P151 假定系統(tǒng)為某進程分配了三個物理塊 并考慮有以下的頁面號引用串 7 7 0 0 1 1 2 2 0 0 3 3 0 0 4 4 2 2 3 3 0 0 3 3 2 2 1 1 2 2 0 0 1 1 7 7 0 0 1 1 進程運行時 先將 7 0 1 三個頁面裝入內(nèi)存 以后 當(dāng)進程要訪問頁面 2 時 將會產(chǎn)生缺頁中斷 此時 OS 根據(jù)最佳置換算法 將選擇頁面 7 予以淘汰 這是因為頁面 0 將作為第 5 個被訪問的頁面 頁面 1 是第 14 個被訪 問的頁面 而頁面 7 則要在第 18 次頁面訪問時才需調(diào)入 下次訪問頁面 0 時 因它已在內(nèi)存而不必產(chǎn)生缺頁中斷 當(dāng)進程訪問頁面 3 時 又將引起頁面 1 被淘汰 因為 它在現(xiàn)有的 1 2 0 三個頁面中 將是以后最晚才被訪問 的 圖 4 26 示出了采用最佳置換算法時的置換圖 采用最佳置換算法發(fā)生了 6 次頁面置換 版本 V3 4 采用 FIFO 算法進行頁面置換 當(dāng)進程第一次訪問頁面 2 時 將把第 7 頁換出 因為它是最先被調(diào)入內(nèi)存的 在第一次訪問頁面 3 時 又將把第 0 頁換出 因為它在現(xiàn)有的 2 0 1 三個頁面中是最老的頁 利用 FIFO 算法 進行了 12 次頁面置換 比最佳置換算法多一倍 PV 操作 綜合題 操作 綜合題 例如 進程之間的關(guān)系如下圖所示 使用 P V 操作描述它們之間的同步 如圖 S1 S2 S3 S6是最簡單的程序段 為使各程序段能正常執(zhí)行 應(yīng)設(shè)置若干個初始值為 0 的信 號量 為保證 S1 S2 S1S3的前驅(qū)關(guān)系 應(yīng)分別設(shè)置信號量 a b 為了保證 S2S4 S2S5 S3S6S4S6S5S6 應(yīng)分別設(shè)置信