【文章內(nèi)容簡(jiǎn)介】 完畢。 – 堆排序：堆的定義、 堆的構(gòu)造、堆排序基本思想 ? 由給定的無序序列構(gòu)造堆 ? 將堆頂元素與堆中最后一個(gè)元素交換， ? 將最后一個(gè)元素從堆中刪除 ? 將余下的元素構(gòu)成完全二叉樹重新調(diào)整成堆 ? 反復(fù)進(jìn)行，直到堆空。 堆排序過程 42 70 17 46 55 05 13 94 13 55 17 46 42 05 70 94 05 46 17 13 42 55 70 94 05 42 17 13 46 55 70 94 05 13 17 42 46 55 70 94 05 13 17 42 46 55 70 94 05 13 17 42 46 55 70 94 第一趟結(jié)果 : 第二趟結(jié)果 : 第三趟結(jié)果 : 第四趟結(jié)果 : 第五趟結(jié)果 : 第六趟結(jié)果 : 第七趟結(jié)果 : 46 55 13 42 94 05 17 70 快速排序例 初始值 46 55 13 42 94 5 17 70 第一趟 17 5 13 42 46 94 55 70 第二趟 5 13 17 42 46 70 55 94 第三趟 5 13 17 42 46 55 70 94 第四趟 5 13 17 42 46 55 70 94 ? 例如對(duì)序列 {16， 31， 9， 15， 87， 76，13， 24， 43}進(jìn)行二路歸并排序過程為： 初始序列 16 31 9 15 87 76 13 24 43 第一趟歸并 16 31 9 15 76 87 13 24 43 第二趟歸并 9 15 16 31 13 24 76 87 43 第三趟歸并 9 13 15 16 24 31 76 87 43 結(jié)果 9 13 15 16 24 31 43 76 87 歸并排序 一趟歸并過程中的三種情況 n 1 length i i i+2*length=n n 1 length i i i+lengthn 剩下兩個(gè)子文件，其中一個(gè)長度小于 length,歸并后退出 n 1 length i i 只剩下一個(gè)子文件，將最后一個(gè)子文件復(fù)制到 r1中，完成后退出 待歸并記錄至少有兩個(gè)長度為 length的子文件，歸并完成后 i+*length 操作系統(tǒng)復(fù)習(xí) 操作系統(tǒng)的定義 操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)中的一個(gè)系統(tǒng)軟件， 是一些程序模塊的集合 —— 它們能以盡量 有效 、 合理 的方式組織和管理計(jì)算機(jī)的軟硬件資源，合理的組織計(jì)算機(jī)的工作流程，控制程序的執(zhí)行并向用戶提供各種服務(wù)功能，使得用戶能夠靈活、 方便 、有效的使用計(jì)算機(jī)，使整個(gè)計(jì)算機(jī)系統(tǒng)能高效地運(yùn)行。 操作系統(tǒng)的分類 由于用戶對(duì) OS的要求不同 批處理操作系統(tǒng) 分時(shí)系統(tǒng) 實(shí)時(shí)系統(tǒng) 網(wǎng)絡(luò)操作系統(tǒng) 分布式操作系統(tǒng) 單道批處理系統(tǒng) 多道批處理系統(tǒng) 批處理操作系統(tǒng)特點(diǎn) 多道： 多道指某個(gè)作業(yè)占用 CPU，若由于某種原因暫時(shí)不用 CPU 則系統(tǒng)讓第二個(gè)作業(yè)占用 CPU 成批處理： 用戶自己不能干預(yù)自己作業(yè)的運(yùn)行，一旦發(fā)現(xiàn)作業(yè)錯(cuò)誤不能及時(shí)改正，并延長開發(fā)軟件時(shí)間，所以適用于成熟的程序 。 在多道批處理系統(tǒng)，用戶無法干預(yù)自己程序的運(yùn)行，缺乏參與感，于是 分時(shí)系統(tǒng) 應(yīng)運(yùn)而生。 分時(shí)操作系統(tǒng)特點(diǎn) ? 多路性 ? 交互性 ? “ 獨(dú)占 ” 性 ? 及時(shí)性 同時(shí)有多個(gè)用戶使用一臺(tái)計(jì)算機(jī) 宏觀上：是多個(gè)人同時(shí)使用一個(gè) CPU 微觀上：多個(gè)人在不同時(shí)刻輪流使用 CPU 用戶根據(jù)系統(tǒng)響應(yīng)結(jié)果進(jìn)一步 提出新請(qǐng)求 (用戶直接干預(yù)每一步 ) 用戶感覺不到計(jì)算機(jī)為其他人服務(wù) （ OS提供虛機(jī)器，各個(gè)用戶的虛 機(jī)器互不干擾） 系統(tǒng)對(duì)用戶提出的請(qǐng)求及時(shí)響應(yīng) 實(shí)時(shí)操作系統(tǒng) 主要追求目標(biāo)： ? 對(duì)外部請(qǐng)求在嚴(yán)格時(shí)間范圍內(nèi)作出反應(yīng) ? 高可靠性 ? 安全性 ? 完整性 實(shí)時(shí)系統(tǒng)必須和先進(jìn)的技術(shù)裝備相結(jié)合 操作系統(tǒng)的功能 處理機(jī)管理 存儲(chǔ)管理 設(shè)備管理 文件管理 用戶接口 第四節(jié) 操作系統(tǒng)的特征 一 并發(fā)性 二 共享性 三 不確定性 四 虛擬性 第八章 處理器管理 ? 基本內(nèi)容 – 作業(yè)的概念 – 進(jìn)程的概念 – 進(jìn)程狀態(tài)及進(jìn)程控制 – 處理機(jī)調(diào)度 – 進(jìn)程的同步和互斥 – 死鎖問題 ? 要求 – 掌握進(jìn)程的概念及作用 – 掌握進(jìn)程的控制與調(diào)度方法 – 掌握進(jìn)程的同步與互斥、 P、 V操作 – 掌握死鎖的概念和死鎖的解決方法 一、作業(yè)的定義 作業(yè)是用戶在一次算題過程中或一個(gè)事務(wù)處理中要求計(jì)算機(jī)系統(tǒng)所做的工作的集合。 作業(yè)控制塊 JCB 作業(yè)被收容到外存后，系統(tǒng)為每個(gè)作業(yè)建立一個(gè) JCB，它詳細(xì)記錄作業(yè)的有關(guān)信息 作業(yè)名 狀態(tài) 優(yōu)先數(shù) 運(yùn)行時(shí)間 位置 長度 外設(shè)申請(qǐng) … 下一 JCB指針 JCB1 JCB2 JCB3 作業(yè)隊(duì)列 (Job Control Block) 提交 作業(yè) 收容 執(zhí)行 完成 輔存 內(nèi)存 設(shè)備管理 作業(yè)管理 區(qū)分配 作業(yè)的生命期 作業(yè)從進(jìn)入計(jì)算機(jī)系統(tǒng)到運(yùn)行結(jié)束、退出系統(tǒng)的整個(gè)過程分成四個(gè)階段 進(jìn)程是一個(gè)可并發(fā)執(zhí)行的程序在一個(gè)數(shù)據(jù)集上的一次執(zhí)行過程。它是系統(tǒng)分配資源的基本單位。 進(jìn)程是由 程序 、 數(shù)據(jù)集 和 進(jìn)程控制塊 三部分組成。 進(jìn)程定義 進(jìn)程的 三種基本狀態(tài) 運(yùn)行 就緒 阻塞 選中 等待事件發(fā)生 (如 I/O請(qǐng)求 ) 等待結(jié)束 如等到 I/O資源 落選 (時(shí)間到） 作業(yè)調(diào)度 進(jìn)程調(diào)度 完成 ? 就緒： 獲得了除 CPU之外的全部資源。 ? 運(yùn)行： 被調(diào)度程序選中，使用 CPU。（獲得全部資源） ? 阻塞： 等待某個(gè)事件的發(fā)生或發(fā)生錯(cuò)誤。 進(jìn)程控制塊 PCB (Process Control Block) ? 是進(jìn)程的檔案，記錄各進(jìn)程執(zhí)行情況。 ? 是進(jìn)程存在的標(biāo)志 ? 進(jìn)程與 PCB是一一對(duì)應(yīng)的 進(jìn)程名 當(dāng)前狀態(tài) 優(yōu)先數(shù) 存儲(chǔ)信息 程序首址 啟動(dòng)地址 數(shù)據(jù)地址 現(xiàn)場(chǎng)信息 指令計(jì)數(shù)器 程序狀態(tài)字 堆棧指針 … 隊(duì)列指針 第四節(jié) 處理器調(diào)度 一、高級(jí)調(diào)度 （作業(yè)調(diào)度、宏觀調(diào)度） 二、中級(jí)調(diào)度 （交互調(diào)度） 三、低級(jí)調(diào)度 （進(jìn)程調(diào)度、微觀調(diào)度） 進(jìn)程狀態(tài) 第五節(jié) 進(jìn)程的同步和互斥 一、相關(guān)概念 二、信號(hào)量和 P、 V原語 三、用 P， V原語實(shí)現(xiàn)進(jìn)程互斥 四、用 P， V原語操作實(shí)現(xiàn)簡(jiǎn)單同步 五、 P， V原語在進(jìn)程同步 /互斥問題中的應(yīng)用 進(jìn)程的同步 進(jìn)程的同步： synchronism 指系統(tǒng)中多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系，需要相互合作，共同完成一項(xiàng)任務(wù)。 具體說，一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài) 進(jìn)程的互斥 mutual exclusion 由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競(jìng)爭(zhēng)使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥 臨界區(qū) ： critical section 在每個(gè)進(jìn)程中，訪問臨界資源的那段程序稱為臨界區(qū)。 臨界資源： critical resource 系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源 同步互斥問題的解決方法 —— PV操作原語 荷蘭計(jì)算機(jī)科學(xué)家迪克斯特拉 (Dijkstra)發(fā)明 ? 對(duì)每一個(gè)臨界資源設(shè)置一個(gè)信號(hào)量，初始化后，只能通過 P操作和 V操作來訪問信號(hào)量 ? 信號(hào)量 S是一個(gè)整型變量 ?S＝ 0時(shí)，表示該類臨界資源的可用個(gè)數(shù)。 ?S0時(shí)，表示等待使用該類臨界資源的進(jìn)程個(gè)數(shù)。 P(Passeren)荷蘭語 通過 V(Vrijgeven)荷蘭語 釋放 二、信號(hào)量和 P， V原語 S：是一個(gè)整型變量 – S＝ 0時(shí)，表示該類臨界資源的可用個(gè)數(shù)。 – S0時(shí)，表示等待使用該類臨界資源的進(jìn)程個(gè)數(shù)。 信號(hào)量只能通過 P操作和 V操作來訪問。 P操作記為 P(S)，其中 S為一信號(hào)量，其執(zhí)行順序完成以下兩個(gè)動(dòng)作： （ 1） S=S?1， 表示申請(qǐng)使用一個(gè)資源 ； （ 2） 若 S?0， 表示系統(tǒng)中有資源可用 ，現(xiàn)進(jìn)程可繼續(xù)執(zhí)行。 （ 3） 若 S?0， 表示系統(tǒng)中沒有可用資源 ，則置該進(jìn)程阻塞狀 態(tài)，到 S信號(hào)量 的隊(duì)列中去等待，直到其他進(jìn)程在 S上執(zhí) 行 V操作釋放它為止。 2. P原語 ?S＝ 0時(shí)，表示該類臨界資源的可用個(gè)數(shù)。 ?S0時(shí)，表示等待使用該類臨界資源的進(jìn)程個(gè)數(shù)。 V操作記為 V(S)， 其中 S為一信號(hào)量，其執(zhí)行順序完成以下兩個(gè)動(dòng)作： （ 1） S=S+1， 表示釋放一個(gè)資源 ； （ 2） 若 S?0， 表示系統(tǒng)中沒有等待該資源的進(jìn)程 ，現(xiàn)進(jìn)程可繼續(xù)執(zhí)行。 (3) 若 S?0， 表示系統(tǒng)中有等待該資源的進(jìn)程 ，則喚醒 S信號(hào)量隊(duì)列中的第一個(gè)進(jìn)程，使其插入到就緒隊(duì)列，繼續(xù)執(zhí)行現(xiàn)進(jìn)程。 3 .V原語 ?S＝ 0時(shí)，表示該類臨界資源的可用個(gè)數(shù)。 ?S0時(shí)，表示等待使用該類臨界資源的進(jìn)程個(gè)數(shù)。 第六節(jié) 死鎖問題 一、死鎖的概念 二、死鎖產(chǎn)生的原因 三、死鎖產(chǎn)生的必要條件 四、 死鎖的排除方法 死鎖產(chǎn)生的原因 ? 系統(tǒng)資源不足 ? 進(jìn)程推進(jìn)的順序不當(dāng) 產(chǎn)生死鎖的必要條件 1. 所涉及的資源是非共享的 （互斥條件） 2. 進(jìn)程在等待新資源時(shí) ,繼續(xù)占用已分配的資源 （請(qǐng)求和保持條件） 3. 一個(gè)進(jìn)程占有的資源不能被別的進(jìn)程強(qiáng)行攻占 （不剝奪條件） 4. 前一個(gè)進(jìn)程獲得的資源正是后一個(gè)進(jìn)程所請(qǐng)求的 ,從而形成一個(gè)進(jìn)程的循環(huán)鏈 （環(huán)路等待條件） R1 R2 P1 P2 進(jìn)程 1 進(jìn)程 2 申請(qǐng) R1 申請(qǐng) R2 申請(qǐng) R2 申請(qǐng) R1 釋放 R1 釋放 R2 解決死鎖方法 ? 預(yù)防： 在系統(tǒng)運(yùn)行之前就采取措施，嚴(yán)格防止死鎖的產(chǎn)生。方法為：破壞死鎖產(chǎn)生的四個(gè)必要條件之一。 ? 靜態(tài)分配資源。 ? 申請(qǐng)不到資源，則釋放全部資源。 ? 資源編號(hào)，從低到高申請(qǐng)。 ? 避免： 允許死鎖產(chǎn)生的四個(gè)必要條件存在，當(dāng)系統(tǒng)有可能產(chǎn)生死鎖時(shí)，小心地避免。 – 銀行家算法。 ? 檢測(cè)和恢復(fù)： 允許死鎖的產(chǎn)生，每隔一段時(shí)間進(jìn)行檢測(cè)，若存在死鎖，則即決之。 – 化簡(jiǎn)資源分配圖。 – 撤銷進(jìn)程。 按某種次序強(qiáng)行從系統(tǒng)中撤銷一個(gè)或多個(gè)卷入死鎖的進(jìn)程，收回它們的資源，直到有足夠的資源可供其他進(jìn)程執(zhí)行完畢。 – 掛起進(jìn)程。 使用掛起 /激活機(jī)構(gòu)掛起一些進(jìn)程，暫時(shí)剝奪它們占有的資源，以解除死鎖，待以后條件滿足后再激活被掛起的進(jìn)程。 第九章 存儲(chǔ)管理 ? 基本內(nèi)容 ? 存儲(chǔ)器層次結(jié)構(gòu) ? 存儲(chǔ)管理任務(wù) ? 實(shí)存儲(chǔ)管理 ? 虛擬存儲(chǔ)管理 ? 要求 ? 掌握存儲(chǔ)管理任務(wù) ? 掌握存儲(chǔ)管理、 實(shí)存儲(chǔ)管理、虛擬存儲(chǔ)管理 ? 了解存儲(chǔ)器層次結(jié)構(gòu) 第二節(jié) 存儲(chǔ)管理任務(wù) 1. 主存空間分配 : 動(dòng)態(tài)地為不斷進(jìn)進(jìn)出出的作業(yè)分配內(nèi)存空間。 2. 地址映射 :保證作業(yè)運(yùn)行中能夠正確的定位。 3. 內(nèi)存保護(hù) :保證作業(yè)的進(jìn)程之間既能互相通信而又不互相干擾。 4. 內(nèi)存“擴(kuò)充” :使空間需求量大于用戶區(qū)容量的作業(yè)也能夠正常運(yùn)行。 ? 程序的起始地址都是從“ 0”開始的，程序中的其它地址都是相對(duì)于起始地址計(jì)算的，該地址被稱為 邏輯地址（或相對(duì)地址） 。 ? 由這些地址所形成的地址范圍稱為（作業(yè)） 地址空間 。 ? 主存單元的編號(hào)稱為 物理地址（或絕對(duì)地址） ? 由主存中的一系列單元所限定的地址范圍稱為 存儲(chǔ)空間 。 ? 相對(duì)地址到絕對(duì)地址的轉(zhuǎn)換，同時(shí)程序中與地址有關(guān)的指令的修改，這一過程叫做 地址重定位 。 – 靜態(tài)重定位 在程序裝入時(shí)進(jìn)行 , 由裝配程序進(jìn)行地址轉(zhuǎn)換 – 動(dòng)態(tài)重定位 是在程