軟件學(xué)院面試題.pdf

School of Software Engineering University of Science and Technology of China 2012 年參加中國科大軟件學(xué)院復(fù)試前 收集了一些前幾屆的面試題目 和大家分享一下 希望對大家有所幫助 獨上高樓 望盡天涯路 衣帶漸寬終不悔 為伊消的人憔悴 眾里尋她千百度 驀然回首 伊人卻在燈火闌珊處 turinglife 2013 03 09 關(guān)于版本號 主版本號 次版本號 修訂號 版本號修改內(nèi)容修改時間修改人 1 0 000第一版本發(fā)布2013 03 09turinglife 1 0 001增加 2013 年第一批 面試真題 2013 03 24turinglife 1 0 002追加 2013 年第一批 面試真題 2013 03 26turinglife 1 0 003追加 2013 年第一批 面試真題 添加部分 題目答案 2013 03 29turinglife 1 好多人會問到時間復(fù)雜度 6 2 各種排序的時間復(fù)雜度和性能比較 7 3 什么叫堆排序 與快速排序有神馬不同 10 4 循環(huán)隊列的順序表示中 為什么要空一個位置 10 5 什么是二叉查找樹 原理 11 6 排序算法最優(yōu)的時間復(fù)雜度 11 13 11 7 哈夫曼樹 11 12 13 11 8 什么是哈希沖突 及如何解決 13 11 9 深度 廣度搜索的過程 12 10 圖的深度優(yōu)先遍歷序列是否唯一 為什么 13 13 11 迪杰斯克拉算法的過程 13 12 鏈表查詢某個元素 平均時間復(fù)雜度是多少 13 13 圖的存儲方式 12 13 13 14 圖的深度遍歷是否唯一 14 15 圖相關(guān)概念 14 16 連通圖的概念 12 13 14 17 解釋下最小生成樹 15 18 n 個節(jié)點的圖的最小生成樹有幾個節(jié)點 幾條邊 15 19 平衡二叉樹 15 20 二叉樹怎么存儲 15 21 單鏈表就地逆置 15 22 各種查找總結(jié) 16 23 m 階的 B 樹和 m 階的 B 樹主要區(qū)別 19 24 折半查找 適用范圍和時間復(fù)雜度 19 25 計算機和計算器的區(qū)別 19 26 線程 進程空間是什么 20 27 硬實時和軟實時 11 12 13 20 28 進程和程序的區(qū)別 20 29 進程和線程的區(qū)別 11 13 20 30 什么是微內(nèi)核 11 12 13 21 31 call 和 return 具體做了哪些工作 21 32 什么是 DMA 什么是中斷 DMA 和中斷有什么區(qū)別 12 13 21 33 硬中斷和軟中斷是什么 區(qū)別是什么 21 34 什么是內(nèi)存 13 22 35 頁面置換算法有哪些 什么是 LRU 22 36 操作系統(tǒng)中磁盤調(diào)度算法 23 37 操作系統(tǒng)中的信號量 24 38 什么是 Pv 操作 24 39 什么是操作系統(tǒng) 25 40 簡述操作系統(tǒng)中系統(tǒng)調(diào)用過程 25 41 虛擬存儲器 虛存 問有啥相關(guān)算法 12 13 26 42 存儲器管理應(yīng)具有的功能 26 43 什么是 TLB 27 44 程序連接方式有哪些 27 45 程序的裝入方式有哪些 27 46 什么是交換技術(shù) 什么是覆蓋技術(shù) 及其區(qū)別 28 47 內(nèi)存連續(xù)分配管理方式有哪幾種 28 48 動態(tài)分區(qū)分配算法有哪些 28 49 什么是拼接技術(shù) 29 51 什么內(nèi)部碎片 什么是外部碎片 29 52 常用存儲保護方法有哪些 29 53 連續(xù)分區(qū)分配 vs 非連續(xù)分區(qū)分配 29 54 什么是頁面 什么是塊或物理塊 30 55 什么是頁表 及頁表的作用 12 13 30 56 段寄存器 30 57 進程線程樹圖 31 58 作業(yè)與進程的區(qū)別 31 59 進程的三種狀態(tài) 以及之間轉(zhuǎn)換的過程 11 12 13 31 60 進程調(diào)度算法 32 61 死鎖 32 62 分頁和分段的區(qū)別 11 12 13 33 63 死鎖及死鎖原因 33 64 介紹下銀行家算法 33 65 RAID 34 66 數(shù)據(jù)庫里面的 什么分級 什么是 ER 圖 35 67 數(shù)據(jù)庫的三級模式結(jié)構(gòu) 36 68 視圖在數(shù)據(jù)庫的第幾層 37 69 數(shù)據(jù)庫的兩級映像是什么 作用 37 70 數(shù)據(jù)庫 ER 模型轉(zhuǎn)換成關(guān)系模型是數(shù)據(jù)庫設(shè)計的第幾個階段 38 71 數(shù)據(jù)庫 數(shù)據(jù)模型有哪幾種 說出至少兩種的特征 38 72 數(shù)據(jù)庫中什么叫主碼 39 73 關(guān)系操作有哪些 13 39 74 數(shù)據(jù)庫的表怎樣分級 39 75 事務(wù)是什么 及其四個特征 11 12 13 39 76 數(shù)據(jù)庫操縱語言 定義語言 定義 操作 查詢 控制 39 77 數(shù)據(jù)庫中怎樣預(yù)防死鎖 40 78 并發(fā)控制是為了保證事務(wù)的什么性質(zhì) 11 13 40 79 在數(shù)據(jù)庫中什么是關(guān)系 它和普通二維表啥區(qū)別 40 80 視圖 索引 40 81 還有個根本沒見過的說是什么標準 在數(shù)據(jù)庫中的那一層 41 82 數(shù)據(jù)庫里的讀鎖 寫鎖 41 83 數(shù)據(jù)庫里 如何解決數(shù)據(jù)冗余問題 41 84 關(guān)系范式 41 85 斷點之類的問題 42 86 關(guān)于顯卡的 顯卡作用 原理 42 87 VGA 43 88 FPGA 43 89 算數(shù)移位 邏輯移位 循環(huán)移位 43 90 386 的保護模式是什么 44 91 什么是實模式 44 92 芯片組是什么 45 93 介紹下南橋和北橋芯片 45 94 cache 和虛擬存儲的功能不同 46 95 接口芯片使用 8259A8251 46 96 組成總線里的異步通信 47 97 PC 機的串口是同步的還是異步的 13 47 98 512 4 的芯片 要組成 4M 的存儲空間要用幾個芯片級聯(lián) 具體用多少引腳 13 47 99 兩個時鐘不同步的設(shè)備怎么通信 47 100 X86 尋址方式有哪些 2013 年第一批 47 101 編譯 如何把一個機器的語言拿到另一臺機器語言機器上執(zhí)行 48 102 編譯原理語法分析句法分析 48 103 編譯的過程 48 104 路由協(xié)議有哪些 49 105 通信的同步異步定義及其相關(guān) 11 13 50 106 比特率波特率 50 107 網(wǎng)絡(luò)服務(wù)質(zhì)量包括哪些方面 50 108 什么是信道 51 109 信道分類 51 110 什么是模擬信號 什么是數(shù)字信號 51 111 什么是基帶信號 什么是寬帶信號 51 112 局部變量和全局變量在內(nèi)存中是如何存儲的 13 51 113 java 與 C 區(qū)別他說他想問的是地址方面的 52 114 傳送介質(zhì)和無線網(wǎng)絡(luò)協(xié)議 54 115 什么是 SHELL 11 13 54 116 網(wǎng)絡(luò)里的時延 帶寬 55 117 滑動窗口協(xié)議是什么 13 55 118 網(wǎng)絡(luò)擁塞 55 119 CSMA CD 的原理 12 13 56 120 數(shù)據(jù)緩存 cache 的基本概念 56 121 應(yīng)用層有什么協(xié)議 作用 57 122 網(wǎng)絡(luò)各層的設(shè)備是什么和工作原理 12 13 57 123 傳統(tǒng)的搜索引擎基本原理 基于內(nèi)容的搜索 原理及實現(xiàn) 57 124 客機被迫降到水面上 什么姿勢才能保證平穩(wěn)不栽倒水里面 57 125 數(shù)據(jù)傳輸方式 57 126 數(shù)據(jù)鏈路層有哪些協(xié)議 舉 1 2 例 58 127 電路交換和分組交換的區(qū)別及聯(lián)系 58 128 電路交換 報文交換 分組交換主要的區(qū)別 58 129 什么是 PN 結(jié) 模電數(shù)電 59 130 CDMA 全稱及原理 59 131 ICMP 59 132 問我什么是非對稱加密 什么是數(shù)據(jù)安全的特征 60 133 保護頻帶 60 134 問到 PPP 協(xié)議 60 135 流量控制在哪些層實現(xiàn) 61 136 二層交換機是哪一層的設(shè)備 與三層交換機之間的區(qū)別 61 137 三網(wǎng) 指哪三網(wǎng) 61 138 分組交換的優(yōu)點及缺點 61 139 組成網(wǎng)絡(luò)協(xié)議的三個要素 62 140 DNS and DHCP 62 141 網(wǎng)絡(luò)安全有哪些方面 63 142 P2P 協(xié)議 63 143 停止等待協(xié)議 63 144 ipv4 地址匱乏解決辦法 64 145 單工 半雙工 全雙工 12 13 65 146 TCP IP 模型分層 11 12 13 66 147 IPv4 和 IPv6 怎么相互通信 66 148 IPv4 的替代方案 66 149 從網(wǎng)絡(luò)的作用范圍進行分類 67 150 從網(wǎng)絡(luò)的使用范圍分類 67 151 從網(wǎng)絡(luò)的拓撲結(jié)構(gòu)分類 67 152 信道劃分 及其典型應(yīng)用 67 153 復(fù)用的相關(guān)概念 頻分 時分 碼分等 68 154 計算機網(wǎng)絡(luò)中使用的信道共享技術(shù)有哪些 13 68 155 自控問的是時域和頻域的穩(wěn)定性判據(jù)分別是什么 13 69 156 反饋系統(tǒng)中偏差信號是指什么信號的偏差 13 69 157 中國科大軟件學(xué)院 2012 2013 學(xué)年 部分開課老師 70 158 中國科大軟件學(xué)院 蘇州 美景 74 159 中國科大軟件學(xué)院 合肥 美景 77 160 Reference 78 1 1 1 1 好多人會問到時間復(fù)雜度好多人會問到時間復(fù)雜度 按數(shù)量級遞增排列 常見的時間復(fù)雜度有 常數(shù)階 O 1 對數(shù)階 O log2n 線性階 O n 線性對數(shù)階 O nlog2n 平方階 O n 2 立方階 O n 3 k 次方階 O n k 指數(shù)階 O 2 n 隨著問題規(guī)模問題規(guī)模 n n n n 的不斷增大 上述時間復(fù)雜度不斷增大 算法的執(zhí)行效率越低 2 2 2 2 各種排序的時間復(fù)雜度和性能比較各種排序的時間復(fù)雜度和性能比較 排序類別排序類別基本思路基本思路詳細詳細 分類分類 時 間 復(fù) 雜時 間 復(fù) 雜 度度 空 間 復(fù) 雜空 間 復(fù) 雜 度度 特點特點注意注意 插入排序每 一 趟 將 一 個 待 排 序的元素 按 其 關(guān) 鍵 字 值 的 大 小 插 入 到 已 經(jīng) 排 序 的 有 序 區(qū) 中 的 適 當 位置上 直 到 全 部 插 入完成 直接插入排序最 好 正 序 O n O 1 需要 一 個 監(jiān) 視 哨 穩(wěn) 定穩(wěn) 定 排序 直接插入排序所產(chǎn)生的有序區(qū) 不一定是全局有序不一定是全局有序的 有序區(qū) 中的關(guān)鍵字并不一定大于或小 于無序區(qū)中所有元素的關(guān)鍵 字 這樣每一趟排序并不一定 將一個元素放置在最終的位置 上 插入排序與待排序數(shù)據(jù)的 順序有關(guān) 當正序正序時效率最高效率最高 當反序反序時效率最低效率最低 最 壞 逆 序 O n 2 平均 O n 2 折半插入平均 O n 2 O 1 折半插入排序僅減少了關(guān)鍵字 間的比較次數(shù) 而元素的移動 次數(shù)不變 希爾排序平均 O n 1 3 O 1 不 穩(wěn)不 穩(wěn) 定定 排 序 希爾排序每一趟并不產(chǎn)生有序 區(qū) 也不一定將一個元素放置 在最終的位置上 希爾排序和 待排序數(shù)據(jù)的順序有關(guān) 正序正序 時最高最高 逆序逆序時效率最低最低 交換排序基本思想 兩 兩 比 較 待 排 序 元 素 的 關(guān) 鍵 字 發(fā)現(xiàn)兩 個 元 素 的 次 序 相 反 時 即 進 行 交換 直到 沒 有 反 序 的 元 素 為 止 起泡排序最壞 O n2 平均 O n2 O 1 穩(wěn) 定穩(wěn) 定 排序 起泡排序中所產(chǎn)生的有序區(qū)一 定是全局有序的全局有序的 有序區(qū)中的 所有元素的關(guān)鍵字一定大于或 小于無序區(qū)中所有元素的關(guān)鍵 字 每一趟排序都將一個元素 放置到最終位置上 起泡排序 與待排序數(shù)據(jù)的順序有關(guān) 正正 序序效率最高最高 逆序逆序效率最低最低 快速排序 在待排序的 n 個元素中任取一個元素 通常取第一個元素 作 為基準 把該元素放入最 終的位置上 歸為一個元 素 數(shù)據(jù)序列被此元素劃 不 穩(wěn)不 穩(wěn) 定定 排 序 在快速排序算法中 并不產(chǎn)生不產(chǎn)生 有序區(qū)有序區(qū) 但每一趟歸位一個元 素 快速排序與待排序數(shù)據(jù)的 順序有關(guān) 當正序正序和逆序逆序時效效 率都低率都低 只有當數(shù)據(jù)隨機分布 每次劃分的子區(qū)間長度大致相 分成兩部分 所有關(guān)鍵字 比該元素關(guān)鍵字小的元素 放置在前一部分 所有比 他大的元素放置在后一部 分 這個過程稱為一趟快 速排序 以后對所有的兩 部分分別重復(fù)上述過程 直至每部分內(nèi)只有一個元 素或空為止 等時效率最高 選擇排序基本思想 每 一 趟 從 待 排 序 的 元 素 序 列 中 選 出 關(guān) 鍵 字 最 大 或最小 的元素 按 順 序 放 在 已 排 序 的 元 素 序 列 的 最 后 面 或 最 前 面 直到 全 部 拍 完 為止 簡單選擇排序 在無序區(qū) 中選擇關(guān)鍵字最小的元素 放在有序區(qū)的最后 形成 新的有序區(qū)和新的無序 區(qū) O 1 O n 2 不 穩(wěn)不 穩(wěn) 定定 排 序 有序區(qū)全局有序有序區(qū)全局有序 有序區(qū)中的 所有元素關(guān)鍵字要么全部大于 無序區(qū) 要么全部小于無序區(qū) 每趟排序歸為一個元素 時間 復(fù)雜度與待排序數(shù)據(jù)序列的順順 序無關(guān)序無關(guān) 堆排序 一種樹形選擇排 序 在排序過程中 將 R 1 n 看成是完全二叉樹 的順序存儲結(jié)構(gòu) 利用完 全二叉樹中的雙親和孩子 結(jié)點之間的關(guān)系來找到當 前序列中關(guān)鍵最大 小的元 素 O 1 O nlog 2 n 不 穩(wěn)不 穩(wěn) 定定 排 序 建初始堆所需要的比較次數(shù)較 多 所以堆排序不適宜于元素 較少的表 所產(chǎn)生的有序區(qū)一定全局有有序區(qū)一定全局有 序序 有序區(qū)要么全部大于或小 于無序區(qū)中的關(guān)鍵字 每趟排 序歸為一個元素 時間復(fù)雜度 與待排序數(shù)據(jù)順序無關(guān)待排序數(shù)據(jù)順序無關(guān) 歸并排序 基數(shù)排序 各種排序方法的綜合比較 一 時間性能 1 按平均的時間性能來分 有三類排序方法 時間復(fù)雜度為 O nlogn 的方法有 快速排序 堆排序和歸并排序 其中以快速排序為最好 直接插入算法 折半插入算法 3 3 3 3 什么叫堆排序 與快速排序有神馬不同 什么叫堆排序 與快速排序有神馬不同 答案請參加上面答案請參加上面 4 4 4 4 循環(huán)隊列的順序表示中 為什么要空一個位置 循環(huán)隊列的順序表示中 為什么要空一個位置 循環(huán)隊列那個空位置為了便于辨別對空和隊滿 5 5 5 5 什么是二叉查找樹 原理什么是二叉查找樹 原理 二叉排序樹 Binary Sort Tree 又稱二叉查找樹 它或者是一棵空樹 或者是具有下列性質(zhì)的二叉樹 1 若左子樹不空 則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值 2 若右子樹不空 則右子樹上所有 結(jié)點的值均大于它的根結(jié)點的值 3 左 右子樹也分別為二叉排序樹 步驟 若根結(jié)點的關(guān)鍵字值等于查找的關(guān)鍵字 成功 否則 若小于根結(jié)點的關(guān)鍵字值 遞歸查左子樹 若大于根結(jié)點的關(guān)鍵字值 遞歸查右子樹 若子樹為空 查找不成功 6 6 6 6 排序算法最優(yōu)的時間復(fù)雜度排序算法最優(yōu)的時間復(fù)雜度 11 1311 1311 1311 13 基于比較的排序算法中最好時間復(fù)雜度為 O nlogn 7 7 7 7 哈夫曼樹哈夫曼樹 11 12 1311 12 1311 12 1311 12 13 給定 n 個權(quán)值作為 n 個葉子結(jié)點 構(gòu)造一棵二叉樹 若帶權(quán)路徑長度帶權(quán)路徑長度達到最小最小 稱這樣的二叉樹為最優(yōu)二最優(yōu)二 叉樹叉樹 也稱為哈夫曼樹哈夫曼樹 Huffman Huffman Huffman Huffman tree tree tree tree 構(gòu)造方法構(gòu)造方法 假設(shè)有 n 個權(quán)值 則構(gòu)造出的哈夫曼樹有 n 個葉子結(jié)點 n 個權(quán)值分別設(shè)為 w1 w2 wn 則 哈夫曼樹的構(gòu)造規(guī)則為 1 將 w1 w2 wn 看成是有 n 棵樹的森林 每棵樹僅有一個結(jié)點 2 在森林中選出兩個根結(jié)點的權(quán)值最小的樹合并 作為一棵新樹的左 右子樹 且新樹的根結(jié)點權(quán) 值為其左 右子樹根結(jié)點權(quán)值之和 3 從森林中刪除選取的兩棵樹 并將新樹加入森林 4 重復(fù) 2 3 步 直到森林中只剩一棵樹為止 該樹即為所求得的哈夫曼樹 2 8 8 8 8 什么是哈希沖突 及如何解決什么是哈希沖突 及如何解決 13131313 哈希表哈希表 散列表 Hash table 也叫哈希表 是根據(jù)關(guān)鍵碼值 Key value 而直接進行訪問的數(shù)據(jù)結(jié)構(gòu) 也就是說 它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄 以加快查找的速度 這個映射函數(shù)叫做散散 列函數(shù)列函數(shù) 存放記錄的數(shù)組叫做散列表 常用散列函數(shù)常用散列函數(shù) 1 直接尋址法 2 數(shù)字分析法 3 平方取中法 4 折疊法 5 隨機數(shù)法 6 除留余數(shù)法 處理沖突的方法處理沖突的方法 1 開放尋址法 2 再散列法 3 鏈地址法 4 建立一個公共溢出區(qū) 散列因子散列因子 散列表的裝填因子定義為 填入表中的元素個數(shù) 散列表的長度 是散列表裝滿程度的標志因子 由于表長是定值 與 填入表中的元素個數(shù) 成正比 所以 越大 填入表中的元素較多 產(chǎn)生沖突的可能性就越大 越小 填入表中的元素較少 產(chǎn)生沖突的可能性就越小 9 9 9 9 深度 廣度搜索的過程深度 廣度搜索的過程 圖的深度優(yōu)先遍歷圖的深度優(yōu)先遍歷 假設(shè)給定圖 G 的初態(tài)是所有頂點均未曾訪問過 在 G 中任選一頂點 v 為初始出發(fā)點 源點 則深度優(yōu) 先遍歷可定義如下 首先訪問出發(fā)點 v 并將其標記為已訪問過 然后依次從 v 出發(fā)搜索 v 的每個鄰接點 w 若 w 未曾訪問過 則以 w 為新的出發(fā)點繼續(xù)進行深度優(yōu)先遍歷 直至圖中所有和源點 v 有路徑相通的頂點 亦稱為從源點可達的頂點 均已被訪問為止 若此時圖中仍有未訪問的頂點 則另選一個尚未訪問的頂點 作為新的源點重復(fù)上述過程 直至圖中所有頂點均已被訪問為止 圖的深度優(yōu)先遍歷類似于樹的前序遍歷圖的深度優(yōu)先遍歷類似于樹的前序遍歷 采用的搜索方法的特點特點是盡可能先對縱深方向進行搜索 這 種搜索方法稱為深度優(yōu)先搜索 Depth First Search 相應(yīng)地 用此方法遍歷圖就很自然地稱之為圖的深度 優(yōu)先遍歷 使用數(shù)據(jù)結(jié)構(gòu)使用數(shù)據(jù)結(jié)構(gòu) 堆棧 圖的廣度優(yōu)先遍歷圖的廣度優(yōu)先遍歷 設(shè) x 是當前被訪問頂點 在對 x 做過訪問標記后 選擇一條從 x 出發(fā)的未檢測過的邊 x y 若發(fā)現(xiàn) 頂點 y 已訪問過 則重新選擇另一條從 x 出發(fā)的未檢測過的邊 否則沿邊 x y 到達未曾訪問過的 y 對 y 訪問并將其標記為已訪問過 然后從 y 開始搜索 直到搜索完從 y 出發(fā)的所有路徑 即訪問完所有從 y 出 發(fā)可達的頂點之后 才回溯到頂點 x 并且再選擇一條從 x 出發(fā)的未檢測過的邊 上述過程直至從 x 出發(fā) 的所有邊都已檢測過為止 此時 若 x 不是源點 則回溯到在 x 之前被訪問過的頂點 否則圖中所有和源 點有路徑相通的頂點 即從源點可達的所有頂點 都已被訪問過 若圖 G 是連通圖 則遍歷過程結(jié)束 否則 繼續(xù)選擇一個尚未被訪問的頂點作為新源點 進行新的搜索過程 使用數(shù)據(jù)結(jié)構(gòu)使用數(shù)據(jù)結(jié)構(gòu) 隊列 10 10 10 10 圖的圖的深度深度優(yōu)先遍歷序列是否唯一 為什么 優(yōu)先遍歷序列是否唯一 為什么 13131313 不一定唯一 當從某頂點 x 出發(fā)搜索時 若 x 的鄰接點有多個尚未訪問過 則我們可任選一個訪問之 11 11 11 11 迪杰斯克拉算法的過程迪杰斯克拉算法的過程 Dijkstra 迪杰斯特拉 算法是典型的單源最短路徑算法單源最短路徑算法 用于計算一個節(jié)點到其他所有節(jié)點的最短路 徑 主要特點主要特點是以起始點為中心向外層層擴展 直到擴展到終點為止 Dijkstra 算法是很有代表性的最短路 徑算法 在很多專業(yè)課程中都作為基本內(nèi)容有詳細的介紹 如數(shù)據(jù)結(jié)構(gòu) 圖論 運籌學(xué)等等 Dijkstra 一般 的表述通常有兩種方式 一種用永久和臨時標號方式 一種是用 OPEN CLOSE 表的方式 這里均采用永 久和臨時標號的方式 注意該算法要求圖中不存在負權(quán)邊 算法步驟如下算法步驟如下 1 初使時令 S V0 T 其余頂點 T 中頂點對應(yīng)的距離值若存在 d V0 Vi 為弧上的權(quán) 值若不存在 d V0 Vi 為 2 從 T 中選取一個其距離值為最小的頂點 W 且不在 S 中 加入 S 3 對 T 中頂點的距離值進行修改 若加進 W 作中間頂點 從 V0 到 Vi 的距離值比不加 W 的路徑要短 則修改此距離值重復(fù)上述步驟 2 3 直到 S 中包含所有頂點 即 S T 為止 12 12 12 12 鏈表查詢某個元素 平均時間復(fù)雜度是多少 鏈表查詢某個元素 平均時間復(fù)雜度是多少 O n 13 13 13 13 圖的存儲方式圖的存儲方式 12 13 12 13 12 13 12 13 圖沒有沒有順序映像的存儲結(jié)構(gòu) 1 鄰接矩陣鄰接矩陣 用兩個數(shù)組分別存儲數(shù)據(jù)元素數(shù)據(jù)元素 頂點頂點 的信息的信息和數(shù)據(jù)元素之間的關(guān)系關(guān)系 邊或 弧 的信息 圖的鄰接矩陣表示是唯一唯一的 且無向圖的鄰接矩陣一定是一個對稱矩陣 2 鄰接表鄰接表 是圖的鏈式存儲結(jié)構(gòu) 3 十字鏈表十字鏈表 有向圖的另一種鏈式存儲結(jié)構(gòu) 4 鄰接多重表鄰接多重表 無向圖的鏈式存儲結(jié)構(gòu) 14 14 14 14 圖的深度遍歷是否唯一圖的深度遍歷是否唯一 不唯一不唯一 15 15 15 15 圖相關(guān)概念圖相關(guān)概念 有向圖有向圖無向圖無向圖 弧弧 弧頭弧頭 弧尾弧尾邊邊 有向完全圖有向完全圖 n n 1 條弧的有向圖完全圖完全圖 1 2 n n 1 條邊的無向圖 稀疏圖稀疏圖 很少條邊或弧 如 enlogn 權(quán)權(quán) 有時圖的邊或弧具有與它相關(guān)的數(shù) 這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)權(quán) 網(wǎng)網(wǎng) 帶權(quán)圖稱為網(wǎng) 子圖子圖 假設(shè)有兩個圖 G V E 和 G V E 如果 V 是 V 的子集 E 是 E 的子集 則稱 G 為 G 的子 圖 路徑路徑 頂點序列 路徑的長度就是路徑上的邊或弧的數(shù)目 回路回路 環(huán)環(huán) 第一個頂點和最后一個頂點相同的路徑稱為回路 環(huán) 簡單路徑簡單路徑 序列中頂點不重復(fù)出現(xiàn)的路徑稱為簡單路徑 簡單回路簡單回路 簡單環(huán)簡單環(huán) 除了第一個頂點和最后一個頂點之外 其余頂點不重復(fù)出現(xiàn)的回路 稱為簡單回路 簡單 環(huán) 出度出度 入度入度 度度 連通 連通 無向圖中從頂點 A 到頂點 B 有路徑 則稱兩 個頂點連通 強連通圖強連通圖 有向圖中任意兩個不同頂點 A B 從頂 點 A 到頂點 B 和從頂點 B 到頂點 A 都存在路徑 則 稱為強連通圖 連同圖連同圖 圖中任意兩個頂點都是連通的 則稱為連 通圖 強連通分量強連通分量 有向圖中的極大強連通子圖連通分量連通分量 無向圖中的極大極大連通子圖 生成森林生成森林 一個有向圖的生成森林由若干棵有向樹 組成 含有圖中全部頂點 但只有足以構(gòu)成若干棵 不相交的有向樹的弧 生成樹生成樹 極小連通子圖 含有圖中全部頂點 但只 有足以構(gòu)成一棵樹的 n 1 條邊 如果在一棵生成 樹上添加一條邊 必定構(gòu)成一個環(huán) 有向樹有向樹 如果一個有向圖恰好有一個頂點的入度為 0 其余頂點的入度均為 1 則是一棵有向樹 16 16 16 16 連通圖的概念連通圖的概念 12 1312 1312 1312 13 在圖論中 連通圖基于連通的概念 在一個無向圖 G 中 若從頂點 vi 到頂點 vj 有路徑相連 當然從 vj 到 vi 也一定有路徑 則稱 vi 和 vj 是連通的 如果 G 是有向圖 那么連接 vi 和 vj 的路徑中所有的邊都 必須同向 如果圖中任意兩點都是連通的 那么圖被稱作連通圖 如果圖中任意兩點都是連通的 那么圖被稱作連通圖 圖的連通性是圖的基本性質(zhì) 17 17 17 17 解釋下最小生成樹解釋下最小生成樹 極小連通子圖 含有圖中全部頂點 但只有足以構(gòu)成一棵樹的 n 1 條邊 如果在一棵生成樹上添 加一條邊 必定構(gòu)成一個環(huán) 18 18 18 18 n n n n 個節(jié)點的圖的最小生成樹有幾個節(jié)點個節(jié)點的圖的最小生成樹有幾個節(jié)點 幾條邊 幾條邊 n 個頂點 n 1 條邊 19 19 19 19 平衡二叉樹平衡二叉樹 平衡二叉樹 Balanced Binary Tree 又被稱為 AVL 樹 有別于 AVL 算法 且具有以下性質(zhì) 它是一 棵 空樹或它的左右兩個子樹的高度差的絕對值不超過 1 1 0 1 并且左右兩個子樹都是一棵平衡二叉樹 AVL 樹是最先發(fā)明的自平衡二叉查找樹 AVL 樹得名于它的發(fā)明者 G M Adelson Velsky 和 E M Landis 他們在 1962 年的論文 An algorithm for the organization of information 中發(fā)表了它 查找 插入和刪除在平均和最壞情況下都是 O logn 增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新 平衡這個樹 20 20 20 20 二叉樹怎么存儲二叉樹怎么存儲 1 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 用一組地址連續(xù)的存儲單元依次自上而下 自左向右存儲完全二叉樹上的結(jié)點信息 這 種順序存儲結(jié)構(gòu)僅適用于完全二叉樹 否則其他形式的二叉樹用順序存儲 會浪費不少存儲空間 2 鏈式存儲結(jié)構(gòu)鏈式存儲結(jié)構(gòu) 二叉鏈表 三叉鏈表 含有 n 個結(jié)點的二叉鏈表中有 n 1 個空鏈域 21 21 21 21 單鏈表單鏈表就地逆置就地逆置 所謂 就地就地 是指算法的輔助空間為 O 1 思路 用指針 p 掃描原單鏈表 先將頭節(jié)點 L 的 next 域設(shè)置為 NULL 而變成一個空鏈表 然后將 p 節(jié)點 采用頭插法插入到 L 中 L an a1 P 算法 22 22 22 22 各種查找總結(jié)各種查找總結(jié) 動態(tài)查找表動態(tài)查找表 若在查找的同時還對表做修改運算 如插入或刪除 則相應(yīng)的表稱之為動態(tài)查找表 靜態(tài)查找表靜態(tài)查找表 反之稱為靜態(tài)查找表 查找類型查找類型平均查找長度平均查找長度時間復(fù)雜度時間復(fù)雜度適用存儲結(jié)構(gòu)適用存儲結(jié)構(gòu)原理原理 順序查找 靜態(tài)查 找 成功 n 1 2O n 線性表的順序存儲順序存儲 和鏈式存儲鏈式存儲都可以 從表的一端開始 順序掃描線性表 依次將掃描到的關(guān) 失敗 n 鍵字和給定值 k 相 比較 若當前掃描 到記錄的關(guān)鍵字與 k 相等 則查找成 功 若掃描結(jié)束后 仍未找到關(guān)鍵字等 于 k 的記錄 則查 找失敗 折半查找 靜態(tài)查 找 成功 查找過程恰 好走了一條從判定 樹的根到被查記錄 的路徑 經(jīng)歷比較 的關(guān)鍵字次數(shù)恰為 該記錄在樹中的層 次 在最壞的情況下查 找成功和查找不成 功的比較次數(shù)均不 超 過 判 定 樹 的 高 度 即 log2 n 1 O log2n 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)且 要求元素按關(guān)鍵字 有序排列有序排列 首先用要查找的關(guān) 鍵字 k 與中間位置 的節(jié)點的關(guān)鍵字相 比較 這個中間記 錄把線性表分成了 兩個子表 若比較 結(jié)果相等則查找成 功 若不相等 再 根據(jù) k 與該中間記 錄關(guān)鍵字的比較大 小確定下一步查找 哪個子表 這樣遞 歸進行下去 注意注意 折半查找的 過程可用二叉樹來 描述 把當前查找 區(qū)的中間位置上得 記錄作為根 左子 表和右子表中的記 錄作為根的左子樹 和右子樹 由此得 到的二叉樹稱為描 述折半查找的判定判定 樹樹或比較樹比較樹 失敗 比較過程經(jīng) 理了一條從判定樹 根到某個外部節(jié)點 的路徑 所需關(guān)鍵 字比較次數(shù)不超過 判定樹的高度 B 樹 多路平衡查 找樹 動態(tài)查找 特點 1 所有葉子節(jié)點 都在同一層 且不帶任何信 息 2 若根節(jié)點不是 終端節(jié)點 則 應(yīng)該同二叉查找樹 O log2n 查找過程查找過程 B 樹查 找過程類似于二叉 查找樹上的查找過 程 不同的是在每 個記錄確定向下查 找的路徑不一定是 二路的 因為一個 節(jié)點內(nèi)的關(guān)鍵字有 序 故節(jié)點內(nèi)可以 采用順序查找或折 半查找 根節(jié)點至少有 兩棵子樹 3 樹中每個節(jié)點 至多有 m 棵樹 4 所有內(nèi)部每個 節(jié)點至少 m 2 棵子樹 插入過程插入過程 插入過 程分兩步 定位定位和 插入插入 定位過程利 用 上 面 的 查 找 算 法 插入過程分為 不分裂不分裂和分裂分裂兩種 情況 分裂插入有 可能導(dǎo)致 B 樹增高 一層 刪除過程刪除過程 兩大類 第一類在非最底層 的非葉子節(jié)點上刪 除關(guān)鍵字 第二類在最底層非 葉子節(jié)點刪除關(guān)鍵 字 這類型又分三 種情況 情況一 直接刪除關(guān)鍵字 情況二 兄弟夠借 情況三 兄弟不夠 借 合并 情況三 有可能導(dǎo)致 B 樹減 少一層 B 樹如果是從根節(jié)點開 始進行隨機查找的 話 應(yīng)該同二叉查 找樹 O log2n 查找過程查找過程 兩種查 找方法 第一種 直接從最小關(guān)鍵字 開 始 進 行 順 序 查 找 第二種 從 B 樹的根節(jié)點開始進 行隨機查找 插入過程插入過程 僅在葉 子節(jié)點中插入關(guān)鍵 字 刪除過程刪除過程 僅在葉 子節(jié)點中刪除節(jié)點 23 23 23 23 mmmm 階的階的 B B B B 樹和樹和 mmmm 階的階的 B B B B 樹主要區(qū)別樹主要區(qū)別 mmmm 階的階的 B B B B 樹和樹和 mmmm 階的階的 B B B B 樹主要區(qū)別樹主要區(qū)別 1 B 樹所有有效數(shù)據(jù)全在葉子節(jié)點 而 B 樹所有節(jié)點分散在樹中 B 樹中的關(guān)鍵字不重復(fù) 2 B 樹種有幾個關(guān)鍵字就有幾個子樹 B 樹中具有 n 個關(guān)鍵字的節(jié)點含有 n 1 棵子樹 3 B 樹有兩個指針 根指針和只想最小節(jié)點的指針 葉子節(jié)點連接成一個不定長的線性鏈表 4 B 樹中 每個節(jié)點 除根節(jié)點外 中的關(guān)鍵字個數(shù) n 的取值范圍是 m 2 n m 根節(jié)點 n 的取值 范圍是 2 n m B 樹中 每個節(jié)點 除根節(jié)點外的所有最底層非葉子節(jié)點 中的關(guān)鍵字取值范圍是 m 2 1 n m 1 根節(jié)點 n 的取值范圍是 1 n m 1 5 B 樹中的所有非葉子節(jié)點僅僅起到索引的作用 節(jié)點中的每個索引項只包含對應(yīng)子樹的最大關(guān)鍵字和 指向該子樹的指針 不含有該關(guān)鍵字對應(yīng)記錄的存儲地址 而在 B 樹中 每個關(guān)鍵字對應(yīng)記錄的存儲 地址 24 24 24 24 折半折半查找 適用范圍和時間復(fù)雜度查找 適用范圍和時間復(fù)雜度 適用范圍 順序存儲結(jié)構(gòu)適用范圍 順序存儲結(jié)構(gòu)且要求元素按關(guān)鍵字有序排列有序排列 時間復(fù)雜度 時間復(fù)雜度 o log 2 n 25 25 25 25 計算機和計算器的區(qū)別計算機和計算器的區(qū)別 計算器 具有簡單計算功能 有些具有簡單存儲功能 不能自動工作 而計算機可以通過編程實現(xiàn)程序自 動運行 價位便宜 計算機 高速計算的電子計算機 可進行數(shù)值計算 邏輯計算 還具有存儲記憶功能 自動化程度高于計 算器 實際上二者還有另一個本質(zhì)性的區(qū)別 計算器使用的是固化的處理程序 只能完成特定的計算任務(wù) 而計算機借助操作系統(tǒng)平臺和各類應(yīng)用軟硬件 可以無限擴展其應(yīng)用領(lǐng)域 也就是說 是否具有擴展性是 二者的本質(zhì)區(qū)別 26 26 26 26 線程線程 進程空間是什么進程空間是什么 線程運行所需要的內(nèi)存空間 比如線程程序的存儲空間 數(shù)據(jù)空間 運行空間等 邏輯地址和物理地址之間的切換 是由 CPU 的內(nèi)存管理單元 MMU 完成 Linux 內(nèi)核維護每個進程的邏輯地 址到物理地址的對照表 當用戶空間進程切換時 內(nèi)核會更新對照表 用戶空間也跟隨變 每個進程的用戶空間都是相互獨立的 把同一個程序同時運行 10 次 會看到 10 個進程使用的線性地址一 模一樣但物理內(nèi)存不一樣 27 27 27 27 硬實時和軟實時硬實時和軟實時 11 12 1311 12 1311 12 1311 12 13 在實時操作系統(tǒng)中 系統(tǒng)必須在特定的時間內(nèi)完成指定的應(yīng)用 具有較強的 剛性 而分時操作系 統(tǒng)則注重將系統(tǒng)資源平均地分配給各個應(yīng)用 不太在意各個應(yīng)用的進度如何 什么時間能夠完成 不過 就算是實時操作系統(tǒng) 其 剛性 和 柔性 的程度也有所不同 就好像是系統(tǒng)的 硬度 有所不同 因 而有了所謂的 硬實時 hard real time 和 軟實時 soft real time 硬實時硬實時系統(tǒng)有一個剛性的 不可改變的時間限制 它不允許任何超出時限的錯誤 超時錯誤會帶來損 害甚至導(dǎo)致系統(tǒng)失敗 或者導(dǎo)致系統(tǒng)不能實現(xiàn)它的預(yù)期目標 軟實時軟實時系統(tǒng)的時限是一個柔性靈活的 它可以容忍偶然的超時錯誤 失敗造成的后果并不嚴重 例如 在網(wǎng)絡(luò)中僅僅是輕微地降低了系統(tǒng)的吞吐量 28 28 28 28 進程和程序的區(qū)別進程和程序的區(qū)別 進程進程 程序的一次執(zhí)行過程 一個動態(tài)的過程 存在生命周期 包括進程的創(chuàng)建 進程運行 進程掛起 進程結(jié)束 程序程序 代碼 數(shù)據(jù)的一個集合 一個靜態(tài)的表示 29 29 29 29 進程和線程的區(qū)別進程和線程的區(qū)別 11 1311 1311 1311 13 進程 資源分配和調(diào)度的基本單位 進程切換耗費資源比線程切換大 進程有獨立的進程地址空間 線程 線程是進程中的一個實體 是 CPU 調(diào)度的基本單位 是比進程更小的能獨立運行的基本單位 線程 自己不擁有系統(tǒng)資源 只擁有運行中必不可少的資源 如程序計數(shù)器 寄存器 棧 在同一個線程內(nèi) 可 以有多個線程 多個線程共享同一個進程的資源 每個線程具有自己的線程棧 線程沒有獨立的線程地址 空間 多個線程共享同一個進程地址空間 30 30 30 30 什么是微內(nèi)核什么是微內(nèi)核 11 12 1311 12 1311 12 1311 12 13 微內(nèi)核是一種能夠提供必要服務(wù)的操作系統(tǒng)內(nèi)核 其中這些必要的服務(wù)包括任務(wù) 線程 交互進程通信 IPC Inter Process Communication 以及內(nèi)存管理等等 所有服務(wù) 包括設(shè)備驅(qū)動 在用戶模式下運 行 而處理這些服務(wù)同處理其他的任何一個程序一樣 因為每個服務(wù)只是在自己的地址空間運行 所以這 些服務(wù)之間彼此之間都受到了保護 微內(nèi)核是提供操作系統(tǒng)核心功能的內(nèi)核的精簡版本 如 Windows Linux 是一個單內(nèi)核 也就是說 Linux 內(nèi)核運行在單獨的內(nèi)核地址空間 不過 Linux 汲取了微內(nèi)核的精華 其引以為豪的是模塊化設(shè)計 搶占式內(nèi)核 支持內(nèi)核線程已經(jīng)動態(tài)裝載內(nèi)核模塊的能力 31 31 31 31 callcallcallcall 和和 returnreturnreturnreturn 具體做了哪些工作具體做了哪些工作 call 參數(shù)壓棧 返回地址壓棧 保護現(xiàn)場 return 返回地址 恢復(fù)現(xiàn)場 32 32 32 32 什么是什么是 DMADMADMADMA 什么是中斷 什么是中斷 DMADMADMADMA 和中斷有什么區(qū)別和中斷有什么區(qū)別 12 1312 1312 1312 13 DMADMADMADMA Direct Memory Access 直接內(nèi)存訪問 為了實現(xiàn)外設(shè)CPU存儲器之間的不足 從而實現(xiàn) 存儲器 CPU 釋放總線 由 DMA 控制器管理 中斷中斷 是指在 CPU 正常運行程序時 由于內(nèi)部 外部事件引起 CPU 暫時停止正在運行的程序 轉(zhuǎn)而去執(zhí)行 請求 CPU 服務(wù)的內(nèi)部事件或外部事件的服務(wù)子程序 待該服務(wù)子程序處理完畢后又返回到被中止的程序繼 續(xù)運行 這一過程叫做中斷 區(qū)別區(qū)別 首先概念功能就不一樣 另外在 DMA 的過程中需要用到中斷系統(tǒng) 33 33 33 33 硬中斷和軟中斷是什么 區(qū)別是什么 硬中斷和軟中斷是什么 區(qū)別是什么 軟中斷軟中斷 1 編程異常通常叫做軟中斷 2 軟中斷是通訊進程之間用來模擬硬中斷的 一種信號通訊方式 3 中斷源發(fā)中斷請求或軟中斷信號后 CPU 或接收進程在適當?shù)臅r機自動進行中斷處理或完成軟中斷信號 對應(yīng)的功能 4 軟中斷是軟件實現(xiàn)的中斷 也就是程序運行時其他程序?qū)λ闹袛?而硬中斷是硬件實現(xiàn)的中斷 是程序運 行時設(shè)備對它的中斷 硬中斷硬中斷 1 硬中斷是由外部事件引起的因此具有隨機性和突發(fā)性 軟中斷是執(zhí)行中斷指令產(chǎn)生的 無外部施加中斷 請求信號 因此中斷的發(fā)生不是隨機的而是由程序安排好的 2 硬中斷的中斷響應(yīng)周期 CPU 需要發(fā)中斷回合信號 NMI 不需要 軟中斷的中斷響應(yīng)周期 CPU 不 需發(fā)中斷回合信號 3 硬中斷的中斷號是由中斷控制器提供的 NMI 硬中斷中斷號系統(tǒng)指定為 02H 軟中斷的中斷號由指 令直接給出 無需使用中斷控制器 4 硬中斷是可屏蔽的 NMI 硬中斷不可屏蔽 軟中斷不可屏蔽 區(qū)別區(qū)別 1 軟中斷發(fā)生的時間是由程序控制的 而硬中斷發(fā)生的時間是隨機的 2 軟中斷是由程序調(diào)用發(fā)生的 而硬中斷是由外設(shè)引發(fā)的 3 硬件中斷處理程序要確保它能快速地完成它的任務(wù) 這樣程序執(zhí)行時才不會等待較長時間 34 34 34 34 什么是內(nèi)存 什么是內(nèi)存 13131313 內(nèi)存是計算機中重要的部件之一 它是與 CPU 進行溝通的橋梁 計算機中所有程序的運行 都是在內(nèi)存中進行的 因此內(nèi)存的性能對計算機的影響非常大 內(nèi)存 Memory 也被稱為內(nèi) 存儲器 其作用是用于暫時存放 CPU 中的運算數(shù)據(jù) 以及與硬盤等外部存儲器交換的數(shù)據(jù) 只要計算機在運行中 CPU就會把需要運算的數(shù)據(jù)調(diào)到內(nèi)存中進行運算 當運算完成后CPU 再將結(jié)果傳送出來 內(nèi)存的運行也決定了計算機的穩(wěn)定運行 內(nèi)存是由內(nèi)存芯片 電路板 金手指等部分組成的 35 35 35 35 頁面置換算法有哪些 什么是頁面置換算法有哪些 什么是 LRULRULRULRU 在地址映射過程中 若在頁面中發(fā)現(xiàn)所要訪問的頁面不再內(nèi)存中 則產(chǎn)生缺頁中斷缺頁中斷 當 發(fā)生缺頁中斷時操作系統(tǒng)必須在內(nèi)存選擇一個頁面將其移出內(nèi)存 以便為即將調(diào)入的頁面讓 出空間 而用來選擇淘汰哪一頁的規(guī)則叫做頁面置換算法頁面置換算法 常見的置換算法有 01 最佳置換算法 OPT 理想置換算法 02 先進先出置換算法 FIFO 03 最近最久未使用 LRU 算法 04 Clock 置換算法 LRU 算法的近似實現(xiàn) 05 最少使用 LFU 置換算法 06 工作集算法 07 工作集時鐘算法 08 老化算法 非常類似 LRU 的有效算法 09 NRU 最近未使用 算法 10 第二次機會算法 LRU 是 Least Recently Used 最近最少使用算法 為了盡量減少與理想算法的差距 產(chǎn)生了各種精妙的算法 最近最少使用頁面置換算法 便是其中一個 LRU 算法的提出 是基于這樣一個事實 在前面幾條指令中使用頻繁的頁 面很可能在后面的幾條指令中頻繁使用 反過來說 已經(jīng)很久沒有使用的頁面很可能在未來 較長的一段時間內(nèi)不會被用到 這個 就是著名的局部性原理局部性原理 比內(nèi)存速度還要快的 cache 也是基于同樣的原理運行的 因此 我們只需要在每次調(diào)換時 找到最近最少使用 的那個頁面調(diào)出內(nèi)存 這就是 LRU 算法的全部內(nèi)容 36 36 36 36 操作系統(tǒng)中磁盤調(diào)度算法操作系統(tǒng)中磁盤調(diào)度算法 磁盤調(diào)度的目標是 使磁盤的平均尋道時間最少 磁盤調(diào)度的目標是 使磁盤的平均尋道時間最少 調(diào)度算法名稱調(diào)度算法名稱基本原理基本原理特點特點 先來先服務(wù) FCFS First Come First Serve 僅適用于請求磁盤僅適用于請求磁盤 IOIOIOIO 的進程的進程 數(shù)目較少的場合數(shù)目較少的場合 最簡單的一種磁盤調(diào)度算法 根據(jù)進程請求訪問磁盤的先 后次序進行調(diào)度 優(yōu)點優(yōu)點 簡單 公平 每一個請 求的進程都能夠得到處理 不 會出現(xiàn)長期得不到處理的進 程 缺點缺點 未對尋道進行優(yōu)化 致 使平均尋道時間可能較長 最短尋道時間優(yōu)先 SSTF Shorted Seek Time First 該算法選擇這樣的進程 其要 求訪問的磁道 與當前磁頭所 在的磁道距離最近 以使每次 的尋道時間最短 但這種算法 不能保證平均尋道時間最短 優(yōu)點優(yōu)點 較 FCFS 有更好的尋道 性能 缺點缺點 可能導(dǎo)致老進程饑餓饑餓 可能會出現(xiàn)磁臂黏著磁臂黏著 掃描算法 SCAN 電梯調(diào)度電梯調(diào)度 算法算法 該算法不僅考慮到被訪問磁 道和當前磁頭之間的距離 更 優(yōu)點優(yōu)點 磁頭雙向移動 不會產(chǎn) 生饑餓 平均尋道時間短 在在 SSTSSTSSTSSTF F F F 算法基礎(chǔ)上優(yōu)化而得算法基礎(chǔ)上優(yōu)化而得 到 可以防止老進程饑餓 到 可以防止老進程饑餓 優(yōu)先考慮的是磁頭當前的移 動方向 應(yīng)該選取同方向且距 離最近的磁道訪問 缺點缺點 可能會出現(xiàn)磁臂黏著磁臂黏著 循環(huán)掃描算法 CSCAN 為了減少延遲 CSCAN 規(guī)定 磁頭單向移動 當從里到最外 后 磁頭立即返回到最里的欲 訪問磁道 然后繼續(xù)向外 優(yōu)點優(yōu)點 磁頭單向移動 不會產(chǎn) 生饑餓 平均尋道時間短 N Step SCAN 算法 對 SCAN 算法的優(yōu)化 將磁盤請求隊列分成若干個 長度為 N 的子隊列 磁盤調(diào)度 將按照 FCFS 依次處理這些子 隊列 而每處理一個隊列時又 是按照 SCAN 算法 對一個隊 列處理后再處理其他隊列 將 新請求隊列放入新隊列 優(yōu)點優(yōu)點 無磁臂黏著磁臂黏著 FSCAN 算法 對 SCAN 算法 的優(yōu)化 將請求隊列分成兩個子隊列 將新出現(xiàn)請求磁盤 IO 的進程 放入另一個子隊列 優(yōu)點優(yōu)點 無磁臂黏著磁臂黏著 37 37 37 37 操作系統(tǒng)中的信號量操作系統(tǒng)中的信號量 信號量是一種實現(xiàn)進程同步同步和互斥互斥的工具 1 整型信號量整型信號量 所謂整型信號量就是一個用于表示資源個數(shù)的整型量 2 記錄性信號量記錄性信號量 就是用一個結(jié)構(gòu)體實現(xiàn) 里面包含了表示資源個數(shù)的整型量和一個等待 隊列 Linux 內(nèi)核代碼對 semaphore 的實現(xiàn) struct semaphore raw spinlock t lock unsigned int count struct list head wait list 38 38 38 38 什么是什么是 PvPvPvPv 操作操作 P V 操作以原語形式實現(xiàn) 信號量的值僅能由這兩條原語加以改變 P 操作相當于申請資源申請資源 V 操作相當于釋放資源釋放資源 39 39 39 39 什么是操作系統(tǒng)什么是操作系統(tǒng) 操作系統(tǒng)是管理電腦硬件與軟件資源的程序 同時也是計算機系統(tǒng)的內(nèi)核與基石 操作系統(tǒng)是控制其他程 序運行 管理系統(tǒng)資源并為用戶提供操作界面的系統(tǒng)軟件的集合 操作系統(tǒng)身負諸如管理與配置內(nèi)存 決 定系統(tǒng)資源供需的優(yōu)先次序 控制輸入與輸出設(shè)備 操作網(wǎng)絡(luò)與管理文件系統(tǒng)等基本事務(wù) 操作系統(tǒng)的型 態(tài)非常多樣 不同機器安裝的 OS 可從簡單到復(fù)雜 可從手機的嵌入式系統(tǒng)到超級電腦的大型操作系統(tǒng) 目前微機上常見的操作系統(tǒng)有 DOS OS 2 UNIX XENIX LINUX Windows Netware 等 40 40 40 40 簡述操作系統(tǒng)中系統(tǒng)調(diào)用過程簡述操作系統(tǒng)中系統(tǒng)調(diào)用過程 系統(tǒng)調(diào)用把應(yīng)用程序的請求傳給內(nèi)核 調(diào)用相應(yīng)的的內(nèi)核函數(shù)完成所需的處理 將處理結(jié)果返回給應(yīng)用程 序 如果沒有系統(tǒng)調(diào)用和內(nèi)核函數(shù) 用戶將不能編寫大型應(yīng)用程序 Linux 系統(tǒng)調(diào)用 包含了大部分常用系統(tǒng)調(diào)用和由系統(tǒng)調(diào)用派生出的的函數(shù) 41 41 41 41 虛擬存儲器 虛存 問有啥相關(guān)算法虛擬存儲器 虛存 問有啥相關(guān)算法 12 1312 1312 1312 13 虛擬存儲器虛擬存儲器 由于常規(guī)內(nèi)存的一次性一次性 要求將作業(yè)全部裝入內(nèi)存后才能運行 和駐留性駐留性 作業(yè)裝入內(nèi)存后 就一直駐留在內(nèi)存中 直到作業(yè)運行結(jié)束 特點 難以滿足作業(yè)很大和有大量作業(yè)要求運行的情況 虛 擬存儲器是一種借助于外存空間 從而允許一個進程在其運行過程中部分地裝入內(nèi)存的技術(shù) 之所以引入虛擬存儲管理方式 是因為程序執(zhí)行時呈現(xiàn)局部性規(guī)律 局部性原理局部性原理 1 時間局部性 一條指令的一次執(zhí)行和下次執(zhí)行 一個數(shù)據(jù)的一次執(zhí)行和下次執(zhí)行 都集中在一個較短 時間內(nèi) 2 空間局部性 指當前指令和鄰近的幾條指令 當前訪問的數(shù)據(jù)和鄰近的數(shù)據(jù) 都集中在一個較小區(qū)域 實現(xiàn)虛擬存儲器的硬件支持實現(xiàn)虛擬存儲器的硬件支持 1 相當數(shù)量的外存 2 相當數(shù)量的內(nèi)存 3 地址變換機構(gòu) 以動態(tài)實現(xiàn)虛擬地址到實地址的地址變換 替換算法替換算法 替換規(guī)則用來確定替換主存中哪一部分 以便騰空部分主存 存放來自輔存要調(diào)入的那部分內(nèi) 容 1 隨機算法 用軟件或硬件隨機數(shù)產(chǎn)生器確定替換的頁面 2 先進先出 先調(diào)入主存的頁面先替