【正文】 、微觀調(diào)度） 進(jìn)程狀態(tài) 第五節(jié) 進(jìn)程的同步和互斥 一、相關(guān)概念 二、信號(hào)量和 P、 V原語(yǔ) 三、用 P， V原語(yǔ)實(shí)現(xiàn)進(jìn)程互斥 四、用 P， V原語(yǔ)操作實(shí)現(xiàn)簡(jiǎn)單同步 五、 P， V原語(yǔ)在進(jìn)程同步 /互斥問(wèn)題中的應(yīng)用 進(jìn)程的同步 進(jìn)程的同步： synchronism 指系統(tǒng)中多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系，需要相互合作，共同完成一項(xiàng)任務(wù)。（獲得全部資源） ? 阻塞： 等待某個(gè)事件的發(fā)生或發(fā)生錯(cuò)誤。 進(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之外的全部資源。它是系統(tǒng)分配資源的基本單位。 分時(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ù)每一步 ) 用戶感覺(jué)不到計(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)程的同步和互斥 – 死鎖問(wèn)題 ? 要求 – 掌握進(jìn)程的概念及作用 – 掌握進(jìn)程的控制與調(diào)度方法 – 掌握進(jìn)程的同步與互斥、 P、 V操作 – 掌握死鎖的概念和死鎖的解決方法 一、作業(yè)的定義 作業(yè)是用戶在一次算題過(guò)程中或一個(gè)事務(wù)處理中要求計(jì)算機(jī)系統(tǒng)所做的工作的集合。 操作系統(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í)改正，并延長(zhǎng)開(kāi)發(fā)軟件時(shí)間，所以適用于成熟的程序 。 – 堆排序：堆的定義、 堆的構(gòu)造、堆排序基本思想 ? 由給定的無(wú)序序列構(gòu)造堆 ? 將堆頂元素與堆中最后一個(gè)元素交換， ? 將最后一個(gè)元素從堆中刪除 ? 將余下的元素構(gòu)成完全二叉樹(shù)重新調(diào)整成堆 ? 反復(fù)進(jìn)行，直到堆空。 排序 ? – 基本思想： 每趟選一排在（前）后 。 – 冒泡排序 ? 第一趟：第 1個(gè)與第 2個(gè)比較 ， 大則交換；第 2個(gè)與第 3個(gè)比較 ， 大則交換 ， …… 關(guān)鍵字最大的記錄交換到最后一個(gè)位置上； ? 第二趟：對(duì)前 n1個(gè)記錄進(jìn)行同樣的操作 ， 關(guān)鍵字次大的記錄交換到第 n1個(gè) 位置上； ? 依次類推 ， 則完成排序 。 0 1 2 3 4 5 6 7 8 9 10 11 12 關(guān)鍵字序列 : 19,14,23,1,68,20,84,28,55,11,10,79 6, 1, 10, 1, 3, 7, 6, 2, 3, 11, 10, 1 H(k)=k mod 13 (除留余數(shù)法 ) 14 1 28 79 68 55 19 84 23 10 11 20 ^ ^ ^ ^ ^ ^ ASL=7*1+4*2+1*3= 處理沖突的方法 排序 ? ： – 基本思想：每次將一個(gè)待排序的記錄，按其關(guān)鍵字大小插入到前面已經(jīng)排好序的子文件中的適當(dāng)位置，直到全部記錄插入完成為止。哈希表（散列表）概念 Bai Chang Zhao 1 2 3 4 . . . 26 Key T: 記錄 H 通過(guò)對(duì)給定值做某種運(yùn)算，直接求得某關(guān)鍵字在記錄文件中的位置 哈希 (hash)函數(shù)： 根據(jù)關(guān)鍵字直接計(jì)算出元素所在位置的函數(shù) —— H(key) 哈希表：存放記錄元素的一維數(shù)組 哈希地址：一維數(shù)組的下標(biāo) 處理沖突的方法 ? 開(kāi)放定址法： 將所有結(jié)點(diǎn)均存放在哈希表 T[0..m1]中 – 線性探查法 – 平方探查法 – 隨機(jī)探查法 ? 拉鏈法： 將互為同義詞的結(jié)點(diǎn)鏈成一個(gè)單鏈表，而將此鏈表的頭指針?lè)旁诠１碇小? 拓?fù)渑判蚍椒? ? 每次輸出一個(gè)無(wú)前趨的結(jié)點(diǎn)并刪去此結(jié)點(diǎn)及其出邊，最后得到的序列即拓?fù)湫蛄小＿@種線性序列稱為 拓?fù)湫蛄?。按最短路徑長(zhǎng)度遞增的順序逐個(gè)將 VS中的頂點(diǎn)加 S中，直到 S中包含全部頂點(diǎn)，而 VS為空。 ? 從求解相應(yīng)問(wèn)題來(lái)看，求頂點(diǎn)的度，采用鄰接矩陣比鄰接表表示更方便。 (邊 ) ? 有向圖 :圖中頂點(diǎn)關(guān)系為有序?qū)Α? d b a c 7 5 2 4 WPL=7*1+5*2+2*3+4*3=35 哈夫曼首先提出了構(gòu)造最優(yōu)二叉樹(shù)的算法，哈夫曼算法 練習(xí) :給定一組權(quán)值 w={2， 3， 8， 4， 45， 7， 9}構(gòu)造關(guān)于 w的哈夫曼樹(shù) 45 8 78 4 5 3 2 9 16 7 24 33 9 練習(xí) :給定一組權(quán)值 w={2， 3， 8， 4， 45， 7， 9}構(gòu)造關(guān)于 w的哈夫曼樹(shù) 5 3 2 8 4 45 7 9 4 5 3 2 9 8 45 7 9 15 8 7 4 5 3 2 9 45 9 15 8 7 4 5 3 2 9 45 18 9 33 15 8 7 4 5 3 2 9 18 9 33 78 45 15 8 7 4 5 3 2 9 45 18 9 圖的概念 ? 圖 是一種復(fù)雜的非線性結(jié)構(gòu) , – 由兩個(gè)集合 V和 E組成， V是頂點(diǎn)的有窮非空集， E是 V中頂點(diǎn)偶對(duì) (邊 )的有窮集 ? 圖的邏輯結(jié)構(gòu)特征 ：就是其結(jié)點(diǎn) (頂點(diǎn) )的 前趨和后繼 的個(gè)數(shù)都是沒(méi)有限制的，即任意兩個(gè)結(jié)點(diǎn)之間之間都可能相關(guān)。 ? 其右子樹(shù)上所有結(jié)點(diǎn)的數(shù)據(jù)值均 大于或等于 根結(jié)點(diǎn)的數(shù)據(jù)值 。 例 :已知一棵二叉樹(shù)的前序序列和中序序列分別為前 序遍歷 :ABCDEFG 中序遍歷 :CBDAFEG ，請(qǐng)畫(huà)出此二叉樹(shù)。 二、幾種特殊形式的二叉樹(shù) 二叉樹(shù)的性質(zhì) 1. 二叉樹(shù)上第 i層上的結(jié)點(diǎn)數(shù)目最多為 2i1(i≥1) 2. 深度為 h的二叉樹(shù)至多有 2h1個(gè)結(jié)點(diǎn) (h≥1) 3. 在任意一棵二叉樹(shù)中，若葉子結(jié)點(diǎn)的個(gè)數(shù)為 n0,度為 2的結(jié)點(diǎn)數(shù)為 n2，則 n0=n2+1。 森林 （ Forest） ： M棵互不相交的樹(shù)的集合 。 深度 （ Depth)： 樹(shù)中結(jié)點(diǎn)的最大層次數(shù) 。 葉子 （ Leaf） ：度為零的結(jié)點(diǎn) ， 也稱端結(jié)點(diǎn) 。 7 1 1 列 行 值 A C G T2 D H I T3 J M B E L K T1 F 介紹幾個(gè)術(shù)語(yǔ)： 結(jié)點(diǎn) （ Node） ：樹(shù)中的元素 。 稀疏矩陣的壓縮存儲(chǔ)方式 三元組表示 ? 把非零元素的值和它所在的行號(hào)列號(hào)做為一個(gè)結(jié)點(diǎn)存放在一起，用這些結(jié)點(diǎn)組成的一個(gè)線性表 (三元組表 )來(lái)表示這個(gè)稀疏矩陣。 ? 但是這種壓縮存儲(chǔ)方式將失去隨機(jī)存儲(chǔ)功能。 ? 列優(yōu)先順序：就是把數(shù)組按一列列的順序依次排列。 ? 空棧 :表中無(wú)元素時(shí)。 使用掛起 /激活機(jī)構(gòu)掛起一些進(jìn)程，暫時(shí)剝奪它們占有的資源，以解除死鎖，待以后條件滿足后再激活被掛起的進(jìn)程。 按某種次序強(qiáng)行從系統(tǒng)中撤銷一個(gè)或多個(gè)卷入死鎖的進(jìn)程，收回它們的資源，直到有足夠的資源可供其他進(jìn)程執(zhí)行完畢。 – 化簡(jiǎn)資源分配圖。 – 銀行家算法。 ? 資源編號(hào)，從低到高申請(qǐng)。 ? 一次性分配資源。 ? 操作系統(tǒng)的功能 處理機(jī)管理、存儲(chǔ)管理、設(shè)備管理、文件管理、作業(yè)管理 處理機(jī)管理 ? 作業(yè)的概念 – 作業(yè)的定義、組成、 JCB、狀態(tài) ? 進(jìn)程的概念 – 進(jìn)程的定義、 PCB、進(jìn)程與程序 ? 進(jìn)程狀態(tài)及進(jìn)程控制 – 進(jìn)程狀態(tài)及轉(zhuǎn)換、進(jìn)程隊(duì)列、進(jìn)程控制 ? 處理機(jī)調(diào)度 – 高級(jí) 調(diào)度、低級(jí)調(diào)度、調(diào)度算法 ? 進(jìn)程的同步與互斥 – 概念、解決同步互斥的軟件工具（ PV操作）、生產(chǎn)者 ─消費(fèi)者問(wèn)題 ? 死鎖 – 產(chǎn)生死鎖的原因、必要條件、解決死鎖方法 解決死鎖方法 ? 預(yù)防： 在系統(tǒng)運(yùn)行之前就采取措施，嚴(yán)格防止死鎖的產(chǎn)生。沖突 (碰撞 )、同義詞的含義。 樹(shù)形結(jié)構(gòu) 圖形結(jié)構(gòu) ? 圖的概念包括與圖有關(guān)的各個(gè)名詞的意義 ? 圖的鄰接矩陣表示法和鄰接表表示法 – 根據(jù)表示法畫(huà)出圖或者根據(jù)圖寫(xiě)出鄰接矩陣表示或畫(huà)出鄰接表。 二叉排序樹(shù)中結(jié)點(diǎn)的刪除。 三種遍歷算法的實(shí)現(xiàn)，運(yùn)用這些算法解決簡(jiǎn)單的問(wèn)題。 這兩種存儲(chǔ)方式下的地址計(jì)算方法 ?？倧?fù)習(xí) 各部分內(nèi)容比例 ? 數(shù)據(jù)結(jié)構(gòu) 50%左右 ? 操作系統(tǒng) 30 %左右 ? 數(shù)據(jù)庫(kù)系統(tǒng) 15 %左右 ? 軟件工程 5 %左右 ? 考試時(shí)間： 12周四 67 ? 考試地點(diǎn)： – 231： M206/M306 – 251： D209/B209 ? 集中答疑時(shí)間： 12周二 67，周三下午 ? 答疑地點(diǎn)：實(shí)驗(yàn)樓 304 數(shù)據(jù)結(jié)構(gòu) 1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。 A．線性結(jié)構(gòu) B． 非線性結(jié)構(gòu) A 順序存儲(chǔ) B 鏈?zhǔn)酱鎯?chǔ) 線性表 棧 隊(duì) 樹(shù)形結(jié)構(gòu) 圖形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面 數(shù)據(jù)結(jié)構(gòu)可描述為 Group=（ D， R） (亦稱物理結(jié)構(gòu) ) 數(shù)組 邏輯結(jié)構(gòu) 存儲(chǔ)結(jié)構(gòu) （ 定義 ， 特點(diǎn) ） 順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 相關(guān)運(yùn)算及應(yīng)用 插入 、 刪除等 線性表 定義 ， 特點(diǎn) 存儲(chǔ)結(jié)構(gòu) 相關(guān)運(yùn)算及應(yīng)用 棧和隊(duì)列 多維數(shù)組的兩種順序存儲(chǔ)方式：行優(yōu)先順序和列優(yōu)先順序 。 稀疏矩陣的三元組表示 數(shù)組 ? 樹(shù)的概念 ，包括與樹(shù)有關(guān)的各個(gè)名詞的意義 ? 二叉樹(shù)的定義 二叉樹(shù)的性質(zhì) 兩種特殊情形的二叉樹(shù) (完全二叉樹(shù)和滿二叉樹(shù)的定義 ) ? 二叉樹(shù)的遍歷 : 能夠熟練排出二叉樹(shù)的三種遍歷次序。 ? 二叉排序樹(shù) 二叉排序樹(shù)的插入和生成，給定一個(gè)序列，畫(huà)出二叉排序樹(shù)的生成過(guò)程。 ? 哈夫曼樹(shù) : 用圖示法畫(huà)出哈夫曼樹(shù) 根據(jù)哈夫曼樹(shù)給出 最優(yōu)前綴碼 。 ? 圖的遍歷 –深度優(yōu)先遍歷 –廣度優(yōu)先遍歷 ? 單源最短路徑 ? 拓?fù)渑判? 查找 ? 查找的基本概念，平均查找長(zhǎng)度的定義及計(jì)算 ? 線性表的查找有三種方法 順序查找、二分查找、分塊查找 ? 二叉排序樹(shù)查找 ? 哈希查找，什么是哈希表 ?哈希函數(shù)、哈希值、哈希的含義。 ? 處理哈希表中沖突的方法： – 開(kāi)放定址法 – 拉鏈法 ? 畫(huà)出哈希表，并計(jì)算哈希表中查找的平均查找長(zhǎng)度 排序方法 插入排序 選擇排序 交換排序 歸并排序 線性插入排序 對(duì)半插入排序 簡(jiǎn)單選擇排序 堆排序 冒泡排序 快速排序 排序 操作系統(tǒng)概念 ? 操作系統(tǒng)基本概念 定義、目的、特征 ? 操作系統(tǒng)的分類 批處理系統(tǒng)、分時(shí)系統(tǒng)、實(shí)時(shí)系統(tǒng)。方法為：破壞死鎖產(chǎn)生的四個(gè)必要條件之一。 ? 申請(qǐng)不到資源，則釋放全部資源。 ? 避免： 允許死鎖產(chǎn)生的四個(gè)必要條件存在，當(dāng)系統(tǒng)有可能產(chǎn)生死鎖