【正文】 8 2 隊列 r f r 1 1 2 1 r 3 1 3 1 f 4 1 4 r 5 1 r 5 f 6 1 r 6 7 1 r 7 f 8 1 r 8 f f f f 7 8 ^ 3 圖的應用 —— 單源最短路徑 ? 求單源最短路徑的 (dijkstra)思想 設置并逐步擴充一個集合 S，存放已求出其最短路徑的頂點，則尚未確定最短路徑的頂點集合是 VS，其中 V為網(wǎng)中所有頂點集合。 圖的應用 —— 拓撲排序 ? AOV網(wǎng) ——作業(yè)活動網(wǎng) ? 將 G中所有頂點排成一個線性序列，使得對圖中任一對頂點 u和 v，若 u,v∈E(G)( 該有向邊在該圖的邊集中可以找到 )，則 u在線性序列中出現(xiàn)在 v之前。 ? 拓撲排序 是對于 有向無環(huán)圖 才可以排序成功的 ，若圖中存在有向環(huán)，則該拓撲序列不存在。 1 2 3 4 5 6 三種查找方法的比較 查找算法 存儲結構 優(yōu)點 缺點 適用于順序查找順序結構鏈表結構算法簡單且對表的結構無任何要求查找效率低n 較小的表的查找和查找較少但改動較多的表 ( 用鏈表作存儲結構 )二分查找 順序結構 查找效率高關鍵字要有序且只能用順序存儲結構實現(xiàn)特別適用于一經(jīng)建立就很少改動又經(jīng)常需要查找的線性表分塊查找順序結構鏈表在表中插入或刪除記錄時就只要在該記錄所屬塊內操作，因為塊內記錄的存放是隨意的，所以插入和刪除比較容易要增加一個輔助數(shù)組的存儲空間，并要進行將初始表分塊排序運算適用于有分塊特點的記錄，如一個學校的學生登記表可按系號或班號分塊。 線性探查法 關鍵字序列 : 1 1 2 6 8 2 5 1 79 設哈希函數(shù)為： H(k)=k mod 13(除留余數(shù)法 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 1 1 19 14 23 1 68 20 84 28 55 11 10 79 1 84 84 28 28 55 10 79 處理沖突的方法 拉鏈法 ? 將所有關鍵字為 同義詞的結點 鏈接在同一個單鏈表中。 – 線性插入排序 ? 從數(shù)組的第 2號元素開始，順序從數(shù)組中取出元素，并將該元素插入到其左端已排好序的數(shù)組的適當位置上 – 對半插入排序 ? 在有序區(qū)中進行對分查找，以確定插入的位置 排序 ? – 基本思想：兩兩比較反即換。 – 快速排序 ? 通過一趟排序將待排序列 分成兩部分 ，使其中 一部分記錄的關鍵字均比 另一部分小 ，再分別對這兩部分排序，以達到整個序列有序。 – 簡單選擇排序： ? 每一趟從待排序的記錄中選出關鍵字最小的記錄，順序存放已排好的子文件的最后 (最前 )，直到全部記錄排序完畢。 堆排序過程 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 第一趟結果 : 第二趟結果 : 第三趟結果 : 第四趟結果 : 第五趟結果 : 第六趟結果 : 第七趟結果 : 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 ? 例如對序列 {16， 31， 9， 15， 87， 76，13， 24， 43}進行二路歸并排序過程為： 初始序列 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 結果 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 剩下兩個子文件，其中一個長度小于 length,歸并后退出 n 1 length i i 只剩下一個子文件，將最后一個子文件復制到 r1中，完成后退出 待歸并記錄至少有兩個長度為 length的子文件，歸并完成后 i+*length 操作系統(tǒng)復習 操作系統(tǒng)的定義 操作系統(tǒng)是計算機系統(tǒng)中的一個系統(tǒng)軟件， 是一些程序模塊的集合 —— 它們能以盡量 有效 、 合理 的方式組織和管理計算機的軟硬件資源，合理的組織計算機的工作流程，控制程序的執(zhí)行并向用戶提供各種服務功能，使得用戶能夠靈活、 方便 、有效的使用計算機，使整個計算機系統(tǒng)能高效地運行。 在多道批處理系統(tǒng)，用戶無法干預自己程序的運行，缺乏參與感，于是 分時系統(tǒng) 應運而生。 作業(yè)控制塊 JCB 作業(yè)被收容到外存后，系統(tǒng)為每個作業(yè)建立一個 JCB，它詳細記錄作業(yè)的有關信息 作業(yè)名 狀態(tài) 優(yōu)先數(shù) 運行時間 位置 長度 外設申請 … 下一 JCB指針 JCB1 JCB2 JCB3 作業(yè)隊列 (Job Control Block) 提交 作業(yè) 收容 執(zhí)行 完成 輔存 內存 設備管理 作業(yè)管理 區(qū)分配 作業(yè)的生命期 作業(yè)從進入計算機系統(tǒng)到運行結束、退出系統(tǒng)的整個過程分成四個階段 進程是一個可并發(fā)執(zhí)行的程序在一個數(shù)據(jù)集上的一次執(zhí)行過程。 進程是由 程序 、 數(shù)據(jù)集 和 進程控制塊 三部分組成。 ? 運行： 被調度程序選中，使用 CPU。 進程控制塊 PCB (Process Control Block) ? 是進程的檔案，記錄各進程執(zhí)行情況。 具體說，一個進程運行到某一點時要求另一伙伴進程為它提供消息，在未獲得消息之前，該進程處于等待狀態(tài)，獲得消息后被喚醒進入就緒態(tài) 進程的互斥 mutual exclusion 由于各進程要求共享資源，而有些資源需要互斥使用，因此各進程間競爭使用這些資源，進程的這種關系為進程的互斥 臨界區(qū) ： critical section 在每個進程中，訪問臨界資源的那段程序稱為臨界區(qū)。 ?S0時，表示等待使用該類臨界資源的進程個數(shù)。 – S0時，表示等待使用該類臨界資源的進程個數(shù)。 P操作記為 P(S)，其中 S為一信號量，其執(zhí)行順序完成以下兩個動作： （ 1） S=S?1， 表示申請使用一個資源 ； （ 2） 若 S?0， 表示系統(tǒng)中有資源可用 ，現(xiàn)進程可繼續(xù)執(zhí)行。 2. P原語 ?S＝ 0時，表示該類臨界資源的可用個數(shù)。 V操作記為 V(S)， 其中 S為一信號量，其執(zhí)行順序完成以下兩個動作： （ 1） S=S+1， 表示釋放一個資源 ； （ 2） 若 S?0， 表示系統(tǒng)中沒有等待該資源的進程 ，現(xiàn)進程可繼續(xù)執(zhí)行。 3 .V原語 ?S＝ 0時，表示該類臨界資源的可用個數(shù)。 第六節(jié) 死鎖問題 一、死鎖的概念 二、死鎖產(chǎn)生的原因 三、死鎖產(chǎn)生的必要條件 四、 死鎖的排除方法 死鎖產(chǎn)生的原因 ? 系統(tǒng)資源不足 ? 進程推進的順序不當 產(chǎn)生死鎖的必要條件 1. 所涉及的資源是非共享的 （互斥條件） 2. 進程在等待新資源時 ,繼續(xù)占用已分配的資源 （請求和保持條件） 3. 一個進程占有的資源不能被別的進程強行攻占 （不剝奪條件） 4. 前一個進程獲得的資源正是后一個進程所請求的 ,從而形成一個進程的循環(huán)鏈 （環(huán)路等待條件） R1 R2 P1 P2 進程 1 進程 2 申請 R1 申請 R2 申請 R2 申請 R1 釋放 R1 釋放 R2 解決死鎖方法 ? 預防： 在系統(tǒng)運行之前就采取措施，嚴格防止死鎖的產(chǎn)生。 ? 靜態(tài)分配資源。 ? 資源編號，從低到高申請。 – 銀行家算法。 – 化簡資源分配圖。 按某種次序強行從系統(tǒng)中撤銷一個或多個卷入死鎖的進程，收回它們的資源，直到有足夠的資源可供其他進程執(zhí)行完畢。 使用掛起 /激活機構掛起一些進程，暫時剝奪它們占有的資源，以解除死鎖，待以后條件滿足后再激活被掛起的進程。 2. 地址映射 :保證作業(yè)運行中能夠正確的定位。 4. 內存“擴充” :使空間需求量大于用戶區(qū)容量的作業(yè)也能夠正常運行。 ? 由這些地址所形成的地址范圍稱為（作業(yè)） 地址空間 。 ? 相對地址到絕對地址的轉換，同時程序中與地址有關的指令的修改，這一過程叫做 地址重定位 。 第三節(jié) 實存儲管理 1. 單一連續(xù)分區(qū) (單道環(huán)境 ) 2. 固定分區(qū) 3. 動態(tài)分區(qū) 為調入內存的程序提供一個不小于作業(yè)地址空間的存儲空間，當存儲空間不夠時，采用覆蓋或交換技術擴充內存 第四節(jié) 虛擬存儲管理 1. 虛擬存儲器的原理 2. 請求分頁存儲管理 3. 請求分段存儲管理 虛擬存儲管理 工作原理： 首先把作業(yè)信息保留在磁盤上，當作業(yè)請求裝入時，只將其中一部分先裝入主存，作業(yè)執(zhí)行中若要訪問的信息不在主存中，則再設法將這些信息裝入主存。 ? 邏輯上擴充了內存空間。 內存分頁 分頁存儲管理 ? 頁 :將作業(yè)的地址空間劃分成一系列大小相等的塊，稱為 頁 ，所有頁按順序編號為 0、 。 ? 塊 : 內存空間也劃分成與頁一樣大的 塊 ，所有的塊從低地址到高地址順序編號為 0、 。 分頁系統(tǒng)中的邏輯地址 頁號 p 頁內地址 d 邏輯地址可用一個數(shù)對表示 p=INT A L 邏輯地址 頁面大小 d = A MOD L 例 :設某系統(tǒng)頁面大小位 1024字節(jié)，若邏輯地址為 :2500, 則 p=INT(2500/1024)=2 d=2500 MOD 1024=452 即 2500處于第 2頁 ,第 452位置上 分頁管理中的地址轉換 Load,1,2500 23285 … 地址空間 … 內存 塊號 0 1 8 10 1000 2500 3000 0 3 1 1 0 2 8 1 頁號 塊號 狀態(tài) L b + 頁表長 頁表起始地址 頁表地址寄存器 2 452 8 452 23285 8644 PMT表 p d p39。 地址變換機構 8*1024+452=8644 絕對地址 =塊 號 *頁面大小 +頁 內地址 P175 16 ? 某請求分頁系統(tǒng)中用戶編程空間共 64個頁面，每頁 1K，主存 32K ，假如某時刻某進程對應的頁表如下，請求出 16進制邏輯地址 128D的物理地址，并寫出計算過程 頁號 1 2 3 4 塊號 8 6 3 12 128D H 0001 0010 1000 1101 頁內地址 d（ 10位） 頁號 p（ 6位） 0011 0010 1000 1101 328DH 3). 頁面置換算法 當主頁中無空閑塊時，為了裝入一個頁面，就必須按某種算法將主存中某個頁調出，調入所需裝入的頁面。算法有： 先進先出調度算法 (FIFO)、 最近最少使用調度算法 (LRU) 最近未使用頁面置換算法（ NRU） 最佳頁面置換算法 (OPT) 先進先出算法 (FIFO) 設一用戶程序共分 5頁 , 分配給它的內存塊數(shù)為 3 頁面走向 P為 4 3 2 1