習題講解678(計算機概論).ppt

《習題講解678(計算機概論).ppt》由會員分享，可在線閱讀，更多相關《習題講解678(計算機概論).ppt（40頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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