計(jì)算機(jī)概論 第二次習(xí)題課,6、7、8 KeyPoints Explanation,六章,OSI模型和TCP/IP協(xié)議 OSI模型七層結(jié)構(gòu)及其功能 TCP/IP協(xié)議中協(xié)議類型及其應(yīng)用 互聯(lián)網(wǎng)上文檔分類 網(wǎng)絡(luò)分類:LAN、MAN、WAN 連接設(shè)備：中繼器、網(wǎng)橋、路由器和網(wǎng)關(guān),OSI模型和TCP/IP協(xié)議(1),模型：由標(biāo)準(zhǔn)化組織制定的用于網(wǎng)絡(luò)設(shè)計(jì)的指南 OSI(Open Systems Interconnection)模型：由國(guó)際標(biāo)準(zhǔn)化組織ISO設(shè)計(jì)，理論上允許任意兩個(gè)不同系統(tǒng)之間可以相互通信而無(wú)需考慮它們的底層體系結(jié)構(gòu)。 協(xié)議：用于控制網(wǎng)絡(luò)或者交互式網(wǎng)絡(luò)中不同設(shè)備間交互的一系列規(guī)則。 TCP/IP (Transmission control/Internet protocol)協(xié)議：TCP/IP協(xié)議是互聯(lián)網(wǎng)上正式使用的協(xié)議組。所以TCP/IP協(xié)議中的層并不完全與OSI模型中的層相同。,OSI模型和TCP/IP協(xié)議(2),OSI模型,OSI模型例子,49.下面動(dòng)作包含在OSI模型中的哪個(gè)層？ a 發(fā)送數(shù)據(jù)幀給下一個(gè)站點(diǎn) b 從源至目的地發(fā)送數(shù)據(jù)包 c 從源至目的地發(fā)送長(zhǎng)消息 d 登錄遠(yuǎn)程計(jì)算機(jī) e 加密和解密數(shù)據(jù) f 將數(shù)據(jù)的機(jī)器碼轉(zhuǎn)換成統(tǒng)一字符編碼標(biāo)準(zhǔn)(Unicode),Data Link,Network,Transport,Application,Presentation,Presentation,TCP/IP(1)分類,TCP/IP(2),IP地址：IPv4地址由4個(gè)字節(jié)（32位）組成；通常用點(diǎn)分十進(jìn)制來(lái)表示 客戶端-服務(wù)器模型：客戶向服務(wù)器請(qǐng)求服務(wù) 客戶：本地計(jì)算機(jī)上運(yùn)行的應(yīng)用程序；需要時(shí)運(yùn)行 服務(wù)器：在遠(yuǎn)程計(jì)算機(jī)上運(yùn)行的應(yīng)用程序；一直運(yùn)行 郵件地址：唯一的標(biāo)示Internet上的一個(gè)郵箱 本地部分：定義了特殊文件的名稱，即用戶郵箱 域名：定義了作為SMTP服務(wù)器的計(jì)算機(jī)名,URL(統(tǒng)一資源定位器)：HTTP所用的特殊地址，它是互聯(lián)網(wǎng)上用于指定任何一種信息的標(biāo)準(zhǔn)。 方法：用來(lái)傳輸文檔的客戶-服務(wù)程序，HTTP既是方法 主機(jī)：存儲(chǔ)信息的計(jì)算機(jī)，通常為計(jì)算機(jī)賦予www.開(kāi)頭的別名 端口：定義了服務(wù)器的端口數(shù)量，可選 路徑：存儲(chǔ)信息的文件的路徑名 例如：使用http協(xié)議，路徑為：/user/general，計(jì)算機(jī)別名為：www.hadb,則其URL地址為： http：/www.hadb/user/general,文檔類型,靜態(tài)文檔(static documents)：在服務(wù)器端生成，只能被復(fù)制；如用戶用瀏覽器下載文檔 動(dòng)態(tài)文檔(dynamic documents)：駐留在服務(wù)器端的程序，當(dāng)瀏覽器發(fā)送請(qǐng)求，服務(wù)器就運(yùn)行該程序并將結(jié)果返回給瀏覽器；如瀏覽器向服務(wù)器發(fā)出運(yùn)行日期的請(qǐng)求 活動(dòng)文檔(active documents)：程序，不能在服務(wù)器端運(yùn)行，瀏覽器需要請(qǐng)求程序的傳輸，傳輸后這個(gè)程序會(huì)在瀏覽器中運(yùn)行；如用戶用瀏覽器下載游戲,網(wǎng)絡(luò)分類,LAN局域網(wǎng)： MAN城域網(wǎng) WAN廣域網(wǎng),例子,如果有一個(gè)每個(gè)角落有一臺(tái)計(jì)算機(jī)的正方形房間，哪種拓?fù)浣Y(jié)構(gòu)需要較少的電纜？ a 總線局域網(wǎng) b 環(huán)形局域網(wǎng) c 在房間中央有一個(gè)集線器的星形LAN 解答：假設(shè)正方形邊長(zhǎng)為L(zhǎng)cm， 則總線局域網(wǎng)需要3Lcm的電纜； 環(huán)形局域網(wǎng)需要4Lcm的電纜； 星形局域網(wǎng)需要2 * sqrt(2) * Lcm or 2.828Lcm的電纜。 故需要較少電纜的為C,連接設(shè)備,連接設(shè)備比較,七章：操作系統(tǒng),OS定義與組成部分 內(nèi)存管理系統(tǒng) 單道程序 多道程序 虛擬內(nèi)存 進(jìn)程管理器 程序、作業(yè)和進(jìn)程 狀態(tài)圖 進(jìn)程同步：死鎖(deadlock)和餓死(starvation) 主流操作系統(tǒng)：windows、Unix和Linux,OS (operation system)定義,操作系統(tǒng)是計(jì)算機(jī)硬件和用戶(程序和人)的接口，它使得其他程序更加方便有效地執(zhí)行，并能方便地對(duì)計(jì)算機(jī)硬件和軟件資源進(jìn)行管理。 操作系統(tǒng)組成部分,內(nèi)存管理系統(tǒng)單道程序和多道程序,單道程序中，大多數(shù)內(nèi)存專用于單一的程序，僅僅一小部分用來(lái)裝載操作系統(tǒng)。 多道程序中，同一時(shí)刻可以裝入多個(gè)程序并能夠同時(shí)執(zhí)行這些程序，CPU輪流為它們服務(wù)。,例子,計(jì)算機(jī)裝有一個(gè)單道程序的操作系統(tǒng)，如果內(nèi)存容量為64MB，操作系統(tǒng)需要4MB，那么該計(jì)算機(jī)可以執(zhí)行程序的最大內(nèi)存是多少？若操作系統(tǒng)自動(dòng)分配10MB內(nèi)存給數(shù)據(jù)，則可以執(zhí)行程序的最大內(nèi)存又是多少？ 解答： 64MB-4MB=60MB 64MB-4MB-10MB=50MB,多道程序分區(qū)調(diào)度,內(nèi)存被分成不定長(zhǎng)度的幾個(gè)分區(qū)，每個(gè)分區(qū)保存一個(gè)程序。 此技術(shù)中，每個(gè)程序需完全載入內(nèi)存，并占用連續(xù)的地址。 執(zhí)行模式：CPU在各程序之間交替服務(wù)。 1.由一個(gè)程序開(kāi)始，執(zhí)行一些指令直到有輸入/輸出或者分配給當(dāng)前程序的時(shí)間片結(jié)束 2.CPU保存現(xiàn)場(chǎng)并轉(zhuǎn)入下一個(gè)程序；重復(fù)1步驟 3.所有程序執(zhí)行完之后，CPU轉(zhuǎn)回第一個(gè)程序,例子,多道程序的操作系統(tǒng)將60MB內(nèi)存分為10MB、12MB、18MB、20MB；第一個(gè)程序運(yùn)行需要17MB使用第三分區(qū)，第二個(gè)需要8MB使用了第一分區(qū)，第三個(gè)需要10.5MB，使用了第二分區(qū)；第四個(gè)需要20MB使用第四分區(qū)。問(wèn)總共使用多少內(nèi)存？總共浪費(fèi)了多少內(nèi)存？?jī)?nèi)存浪費(fèi)率是多少？ 解答：總共使用的內(nèi)存： 17+8+10.5+20=55.5（MB） 浪費(fèi)的內(nèi)存： 60MB-55.5MB=4.5MB 內(nèi)存浪費(fèi)率： 4.5/60=7.5%,多道程序分頁(yè)調(diào)度,內(nèi)存被分成大小相同的幀；程序則分成大小相等的頁(yè)；頁(yè)和幀的大小一樣； 此技術(shù)下，程序在運(yùn)行前全部載入內(nèi)存，但在內(nèi)存中不必是連續(xù)的；,例子,多道程序的操作系統(tǒng)使用分頁(yè)調(diào)度，將可用內(nèi)存60MB內(nèi)存分為15頁(yè)，每一頁(yè)大小為4MB；第一個(gè)程序運(yùn)行需要17MB，第二個(gè)需要8MB，第三個(gè)需要10.5MB，；第四個(gè)需要20MB。問(wèn)總共使用多少內(nèi)存？總共浪費(fèi)了多少內(nèi)存？?jī)?nèi)存浪費(fèi)率是多少？ 解答：第一個(gè)程序需要5頁(yè) 4MB*5=20MB17MB 第二個(gè)程序需要2頁(yè) 4MB*2=8MB 第三個(gè)程序需要3頁(yè) 4MB*3=12MB10.5MB 第四個(gè)程序需要5頁(yè) 4MB*5=20MB 總共使用了60MB； 浪費(fèi)內(nèi)存為：3+1.5=4.5MB；內(nèi)存浪費(fèi)率為7.5%,虛擬內(nèi)存,微軟的官方定義是:計(jì)算機(jī)使用的臨時(shí)存儲(chǔ)器，用來(lái)運(yùn)行所需內(nèi)存大于計(jì)算機(jī)具有的物理內(nèi)存的程序；虛擬內(nèi)存用部分硬盤空間做內(nèi)存來(lái)彌補(bǔ)計(jì)算機(jī)RAM空間的不足。 例1：內(nèi)存空間為10MB，而我們需要運(yùn)行10個(gè)程序，每個(gè)程序3MB；若同時(shí)運(yùn)行10個(gè)這樣的程序，則至少需要30MB的內(nèi)存空間，這時(shí)候，虛擬內(nèi)存大小就是至少20MB。,例子：,例2：一OS執(zhí)行時(shí)需要所有的程序駐留在物理內(nèi)存中。物理內(nèi)存大小為100MB，虛擬內(nèi)存為1GB；有多少10MB大小的程序可以同時(shí)運(yùn)行？它們之中有多少可以隨時(shí)駐留在內(nèi)存中？多少則必須要存在磁盤里？ 解答：100MB/10MB=10 1GB/10MB=102.4 可以同時(shí)運(yùn)行112個(gè)10MB大小的程序 有10個(gè)可以隨時(shí)駐留在內(nèi)存中 有102個(gè)必須存在磁盤中,進(jìn)程管理器程序、作業(yè)和進(jìn)程,狀態(tài)圖,例子,進(jìn)程在下面的情況下處于什么狀態(tài)？ a 進(jìn)程在使用CPU b 進(jìn)程結(jié)束打印，等待CPU又一次調(diào)用 c 進(jìn)程因?yàn)闀r(shí)間片用盡而被終止 d 進(jìn)程從鍵盤讀取數(shù)據(jù) e 進(jìn)程打印數(shù)據(jù),運(yùn)行,就緒,就緒,等待,等待,死鎖(Deadlock),死鎖：是指兩個(gè)或兩個(gè)以上的進(jìn)程在執(zhí)行過(guò)程中,因爭(zhēng)奪資源而造成的一種互相等待的現(xiàn)象,若無(wú)外力作用,它們都將無(wú)法推進(jìn)下去.此時(shí)稱系統(tǒng)處于死鎖狀態(tài)或系統(tǒng)產(chǎn)生了死鎖,這些永遠(yuǎn)在互相等待的進(jìn)程稱為死鎖進(jìn)程. 死鎖發(fā)生需要四個(gè)必要條件： 互斥：一個(gè)資源只能被一個(gè)進(jìn)程調(diào)用占有 資源占有：雖然不使用資源，但進(jìn)程仍然占用直到有其他可用的資源 先到先得：操作系統(tǒng)不能臨時(shí)對(duì)資源重新分配 循環(huán)等待：所有的進(jìn)程和資源包含在一個(gè)環(huán)里,例子：,例1：三個(gè)進(jìn)程(A、B、C)同時(shí)運(yùn)行，進(jìn)程A占用File1但需要File2，進(jìn)程B占用File3需要File1，進(jìn)程C占用File2需要File3.畫出資源與進(jìn)程之間的關(guān)系框圖，并判斷是否是死鎖？ 例1：三個(gè)進(jìn)程(A、B、C)同時(shí)運(yùn)行，進(jìn)程A占用File1，進(jìn)程B占用File2需要File1，進(jìn)程C占用File3需要File2.畫出資源與進(jìn)程之間的關(guān)系框圖，并判斷是否是死鎖,第八章：算法,算法 定義 算法的三種結(jié)構(gòu)：順序、判斷、循環(huán) 算法的表示：流程圖、偽代碼 基本算法 排序：選擇排序、冒泡排序、插入排序 查找：順序查找、折半查找 遞歸,算法定義、結(jié)構(gòu),算法是一組明確步驟的有序集合，它產(chǎn)生結(jié)果并在有限的時(shí)間內(nèi)終止。 三種結(jié)構(gòu),算法的表示(1),流程圖：只顯示算法從開(kāi)始到結(jié)束的整個(gè)流程，而無(wú)細(xì)節(jié) 規(guī)則： 橢圓或者圓角表示“開(kāi)始”或者“終止” 菱形表示“判斷” 長(zhǎng)方形表示“處理” 平行四邊形表示“輸入輸出”,算法的表示(2),偽代碼：類似英語(yǔ)的表示法，現(xiàn)在還無(wú)相應(yīng)標(biāo)準(zhǔn),基本算法排序(1),選擇排序算法：該算法將列表分為兩個(gè)子列表：已排序的和未排序的。使用兩重循環(huán)，外層循環(huán)每次掃描時(shí)迭代一次，內(nèi)層循環(huán)在未排序列表中尋找最小的元素并把它和未排序數(shù)據(jù)中第一個(gè)元素進(jìn)行交換。,Select sort Input：unsorted list 1. Set wall at the beginning； 2. While there are more elments in the unsorted list 2.1 Find smallest elment in unsorted list 2.2 Swap (Smallest, First) 2.3 Advance wall End loop 3. Return list End,基本算法排序(2),冒泡排序：兩重循環(huán)，外層循環(huán)每次掃描過(guò)程中迭代一次，每次內(nèi)層循環(huán)則將一個(gè)元素冒泡至頂部(左部)。,基本算法排序(3),插入排序：雙層循環(huán)，外層循環(huán)每次掃描迭代一次，內(nèi)層循環(huán)則尋找插入的位置。,例子,例1：分別使用選擇排序、冒泡排序和插入排序算法，手工排序下列數(shù)據(jù)并給出每次掃描所做的工作； 14 7 23 31 40 56 78 9 2,基本算法查找,順序查找：從表頭開(kāi)始查找，若當(dāng)前元素不是目標(biāo)元素，右移指針，直到找到目標(biāo)值或者確信查找目標(biāo)不在列表中。一般用于查找無(wú)序列表，針對(duì)較小的列表或者是不常用的列表，效率低。 折半查找：從測(cè)試列表的中間元素開(kāi)始查找，判別目標(biāo)值是在前半部分還是后半部分；若在前半部分，則無(wú)需查找后半部分；重復(fù)此過(guò)程直至找到目標(biāo)值。用于有序列表查找，效率比較高。 遞歸 算法包含了算法本身，則為遞歸；換句話說(shuō)，遞歸是算法自我調(diào)用的過(guò)程,例子,一個(gè)列表包含以下元素。使用折半查找法，跟蹤查找88的步驟，要求給出每一步中first、mid和last的值。 8 13 17 26 44 56 88 97,例子,使用如下定義編寫一個(gè)尋找兩個(gè)整數(shù)最大公約數(shù)(gcd)的遞歸算法。 GCD Input: 2 integers (X and Y) 1. If X Y 1.1 Return GCD(Y, X) 2. Else if Y equals 0 2.2 Return X 3. Else 3.3 Return GCD(Y, X % Y ) End if End,