軟件技術(shù)基礎(chǔ)

軟件技術(shù)基礎(chǔ)

13.1數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)概述13.1.1數(shù)據(jù)結(jié)構(gòu)（DataStructure）是指數(shù)據(jù)元素的組織形式和相互關(guān)系。數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的運(yùn)算第2頁,共105頁，2024年2月25日，星期天數(shù)據(jù)的邏輯結(jié)構(gòu)1數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯上抽象地反映數(shù)據(jù)元素間的結(jié)構(gòu)關(guān)系，它與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示方式無關(guān)。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看做是從具體問題抽象出來的數(shù)學(xué)模型。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：線性結(jié)構(gòu)——

線性結(jié)構(gòu)的邏輯特征是：有且僅有一個(gè)始端結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且除兩個(gè)端點(diǎn)結(jié)點(diǎn)外的所有結(jié)點(diǎn)都有且僅有一個(gè)前趨結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。線性表、堆棧、隊(duì)列、數(shù)組、串等都是線性結(jié)構(gòu)。非線性結(jié)構(gòu)——

非線性結(jié)構(gòu)的邏輯特征是：一個(gè)結(jié)點(diǎn)可以有多個(gè)前趨結(jié)點(diǎn)和后繼結(jié)點(diǎn)。如樹形結(jié)構(gòu)、圖等是非線性結(jié)構(gòu)。第3頁,共105頁，2024年2月25日，星期天數(shù)據(jù)的物理結(jié)構(gòu)2數(shù)據(jù)的物理結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器里的映像，也稱為存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)可用以下四種基本存儲(chǔ)方法：順序存儲(chǔ)方法

——

把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰的存儲(chǔ)單元里，結(jié)點(diǎn)之間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。鏈?zhǔn)酱鎯?chǔ)方法

——

不要求邏輯上相鄰的結(jié)點(diǎn)在物理位置上也相鄰，結(jié)點(diǎn)之間的邏輯關(guān)系是由附加的指針字段表示的。索引存儲(chǔ)方法

——

在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表。索引表中的每一項(xiàng)稱為索引項(xiàng)。索引項(xiàng)由關(guān)鍵字和地址組成，關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)，而地址一般是指示結(jié)點(diǎn)所在存儲(chǔ)位置的記錄號。散列存儲(chǔ)方法

——

根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。第4頁,共105頁，2024年2月25日，星期天

數(shù)據(jù)的運(yùn)算3數(shù)據(jù)的運(yùn)算是指對數(shù)據(jù)施加的操作，數(shù)據(jù)的每種邏輯結(jié)構(gòu)都有一個(gè)運(yùn)算的集合，常用的運(yùn)算有檢索、插入、刪除、更新、排序等。第5頁,共105頁，2024年2月25日，星期天算法4算法的特點(diǎn)（1）有窮性

——

一個(gè)算法的執(zhí)行步驟必須是有限的。確定性

——

算法中的每一個(gè)操作步驟的含義必須明確。可行性

——

算法中的每一個(gè)操作步驟都是可以執(zhí)行的。輸入

——

一個(gè)算法一般都要求有一個(gè)或多個(gè)輸入量（個(gè)別的算法不要求輸入量）。這些輸入量是算法所需的初始數(shù)據(jù)。輸出

——

一個(gè)算法至少產(chǎn)生一個(gè)輸出量，它是算法對輸入量的執(zhí)行結(jié)果。第6頁,共105頁，2024年2月25日，星期天算法的描述

（2）自然語言——

用人的語言描述，該方法易于理解，但容易出現(xiàn)歧義。流程圖——

用一組特定的幾何圖形來表示算法，這是最早的算法描述工具。N-S圖——

用矩形框描述算法，一個(gè)算法就是一個(gè)矩形框。偽代碼——

用介于高級語言和人的自然語言之間的文字、符號來描述算法，可以十分容易地轉(zhuǎn)化為高級語言程序。PAD圖——

全稱為問題分析圖，使用樹形結(jié)構(gòu)描述算法。第7頁,共105頁，2024年2月25日，星期天

算法性能分析（3）衡量一個(gè)算法的好壞主要考慮算法的時(shí)間特性，一般將語句的重復(fù)執(zhí)行次數(shù)作為算法的時(shí)間變量。設(shè)算法解決的問題的規(guī)模為n，例如學(xué)生總數(shù)等。將一條語句重復(fù)執(zhí)行的次數(shù)稱為該語句的執(zhí)行頻度，一個(gè)算法中所有語句執(zhí)行頻度之和就稱為該算法的運(yùn)行時(shí)間。很多情況下無法準(zhǔn)確也無必要精確計(jì)算出運(yùn)行時(shí)間，而只需求出它關(guān)于問題規(guī)模n的一個(gè)相對的數(shù)量級即可，該數(shù)量級就稱為該算法的時(shí)間復(fù)雜度，記為O(1)，O(n)，O(n2)……

一般地，常用的時(shí)間復(fù)雜度有如下關(guān)系：O(1)<=O(log2n)<=O(n)<=O(nlog2n)<=O(n2)<=O(an)(a>1)第8頁,共105頁，2024年2月25日，星期天線性結(jié)構(gòu)13.1.2順序表1線性表是數(shù)據(jù)結(jié)構(gòu)中最簡單且最常用的一種數(shù)據(jù)結(jié)構(gòu)。其基本特點(diǎn)是：數(shù)據(jù)元素有序并有限。線性結(jié)構(gòu)的數(shù)據(jù)元素可排成一個(gè)線性隊(duì)列當(dāng)線性表采用順序存儲(chǔ)結(jié)構(gòu)時(shí)稱之為順序表。在順序表中，數(shù)據(jù)元素按邏輯次序依次放在一組地址連續(xù)的存儲(chǔ)單元里。由于邏輯上相鄰的元素存放在內(nèi)存的相鄰單元里，所以順序表的邏輯關(guān)系蘊(yùn)含在存儲(chǔ)單元的鄰接關(guān)系中。第9頁,共105頁，2024年2月25日，星期天插入運(yùn)算（1）（2）刪除運(yùn)算

順序表的插入運(yùn)算是指在表的第i個(gè)（1≤i≤n+1）位置上，插入一個(gè)新結(jié)點(diǎn)y。若插入位置i＝n+1，即插入到表的末尾，那么只要在表的末尾增加一個(gè)結(jié)點(diǎn)即可；但是若1≤i≤n，則必須將表中第i個(gè)到第n個(gè)結(jié)點(diǎn)向后移動(dòng)一個(gè)位置，共需移動(dòng)n

i+1個(gè)結(jié)點(diǎn)。順序表上插入運(yùn)算的平均時(shí)間復(fù)雜度是O(n)。順序表的刪除運(yùn)算是指將表的第i個(gè)（1≤i≤n）結(jié)點(diǎn)刪去。當(dāng)i=n時(shí)，即刪除表尾結(jié)點(diǎn)時(shí)，操作較為簡單；但1＜i≤n-l時(shí)，則必須將表中第i+1個(gè)到第n個(gè)共n

i個(gè)結(jié)點(diǎn)向前移動(dòng)一個(gè)位置。順序表上刪除運(yùn)算的平均時(shí)間復(fù)雜度是O(n)第10頁,共105頁，2024年2月25日，星期天單鏈表2采用順序表的運(yùn)算效率較低，需要移動(dòng)大量的數(shù)據(jù)元素。而采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的鏈表是用一組任意的存儲(chǔ)單元來存放線性表的數(shù)據(jù)元素。這組存儲(chǔ)單元既可以是連續(xù)的，也可以是不連續(xù)的，甚至可以是零星分布在內(nèi)存中的任何位置上，從而可以大大提高存儲(chǔ)器的使用效率。在線性鏈表中，每個(gè)元素結(jié)點(diǎn)除存儲(chǔ)自身的信息外，還要用指針域額外存儲(chǔ)一個(gè)指向其直接后繼的信息（即后繼的存儲(chǔ)位置：地址）。對鏈表的訪問總是從鏈表的頭部開始，是根據(jù)每個(gè)結(jié)點(diǎn)中存儲(chǔ)的后繼結(jié)點(diǎn)的地址信息，順鏈進(jìn)行的。當(dāng)每個(gè)結(jié)點(diǎn)只有一個(gè)指針域時(shí)，稱為單鏈表第11頁,共105頁，2024年2月25日，星期天棧與隊(duì)列3棧與隊(duì)列是兩種特殊的線性表。即它們的邏輯結(jié)構(gòu)與線性表相同，只是其插入、刪除運(yùn)算僅限制在線性表的一端或兩端進(jìn)行。第12頁,共105頁，2024年2月25日，星期天棧（1）

隊(duì)列（2）棧是僅限于在表的一端進(jìn)行插入和刪除運(yùn)算的線性表，通常稱插入、刪除的這一端為棧頂，另一端稱為棧底。當(dāng)表中沒有元素時(shí)稱為空棧。一摞盤子的情形就是棧的生動(dòng)形態(tài)。棧的特點(diǎn)是：后進(jìn)先出（LIFO——LastIn，F(xiàn)irstOut）。如：入棧順序?yàn)?，2，3，4，5，則出棧順序?yàn)?，4，3，2，1。隊(duì)列是一種操作受限的線性表，它只允許在線性表的一端進(jìn)行數(shù)據(jù)元素的插入操作，而在另一端才能進(jìn)行數(shù)據(jù)元素的刪除操作。其允許插入的一端稱為隊(duì)尾，允許刪除的另一端稱為隊(duì)頭。日常生活中的排隊(duì)就是隊(duì)列的實(shí)例。特點(diǎn)：先進(jìn)先出（FIFO——FirstIn，F(xiàn)irstOut）。第13頁,共105頁，2024年2月25日，星期天

樹

13.1.3樹結(jié)構(gòu)1樹是一個(gè)或多個(gè)結(jié)點(diǎn)元素組成的有限集合T，且滿足條件如下：①有且僅有一個(gè)結(jié)點(diǎn)沒有前趨結(jié)點(diǎn)，稱為根結(jié)點(diǎn)（root）。②除根結(jié)點(diǎn)外，其余所有結(jié)點(diǎn)有且只有一個(gè)直接前趨結(jié)點(diǎn)。③包括根結(jié)點(diǎn)在內(nèi)，每個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼結(jié)點(diǎn)。第14頁,共105頁，2024年2月25日，星期天二叉樹2二叉樹結(jié)構(gòu)也是非線性結(jié)構(gòu)中重要的一類，它是有序樹，不是樹的特殊結(jié)構(gòu)。在二叉樹中，每個(gè)結(jié)點(diǎn)最多只有兩棵子樹，一個(gè)是左子樹，一個(gè)是右子樹。二叉樹有五種基本形態(tài)：它可以是空二叉樹，根可以有空的左子樹或空的右子樹，或左、右子樹皆為空，如圖13-1-4所示。第15頁,共105頁，2024年2月25日，星期天二叉樹的存儲(chǔ)結(jié)構(gòu)3順序存儲(chǔ)（1）對完全二叉樹而言，可用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)其存儲(chǔ)，該方法是把完全二叉樹的所有結(jié)點(diǎn)按照自上而下，自左向右的次序連續(xù)編號，并順序存儲(chǔ)到一片連續(xù)的存儲(chǔ)單元中，在存儲(chǔ)結(jié)構(gòu)中的相互位置關(guān)系即反映出結(jié)點(diǎn)之間的邏輯關(guān)系。如用—維數(shù)組Tree來表示完全二叉樹，則數(shù)組元素Tree(i)對應(yīng)編號為i的結(jié)點(diǎn)。第16頁,共105頁，2024年2月25日，星期天鏈?zhǔn)酱鎯?chǔ)

（2）順序存儲(chǔ)容易造成空間浪費(fèi)，并具有順序存儲(chǔ)結(jié)構(gòu)固有的缺點(diǎn)：添加、刪除伴隨著大量結(jié)點(diǎn)的移動(dòng)。對于一般的二叉樹，較好的方法是用二叉鏈表來表示。表中每個(gè)結(jié)點(diǎn)都具有三個(gè)域：左指針域Lchild、數(shù)據(jù)域Data、右指針域Rchild。其中，指針Lchild和Rchild分別指向當(dāng)前結(jié)點(diǎn)的左孩子和右孩子。結(jié)點(diǎn)的形態(tài)如下：LchildDataRchild第17頁,共105頁，2024年2月25日，星期天鏈?zhǔn)酱鎯?chǔ)

（2）第18頁,共105頁，2024年2月25日，星期天二叉樹的遍歷4所謂遍歷，是指按某種次序，依次對某結(jié)構(gòu)中的所有數(shù)據(jù)元素訪問且僅訪問一次。由于二叉樹結(jié)構(gòu)的非線性特點(diǎn)，它的遍歷遠(yuǎn)比線性結(jié)構(gòu)復(fù)雜，其算法都是遞歸的。有三種遍歷方式：先序遍歷——

訪問根結(jié)點(diǎn)；先序遍歷左子樹；先序遍歷右子樹。對圖13-1-7所示的二叉樹，先序遍歷序列為：ABDECF。中序遍歷——

中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。對圖13-1-7所示的二叉樹，中序遍歷序列為：DBEAFC。后序遍歷——

后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)。對圖13-1-7所示的二叉樹，后序遍歷序列為：DEBFCA。第19頁,共105頁，2024年2月25日，星期天

圖結(jié)構(gòu)13.1.4

圖的概念1圖是一種重要的、比樹更復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。在樹結(jié)構(gòu)中，某結(jié)點(diǎn)只能與其上層的一個(gè)結(jié)點(diǎn)（父結(jié)點(diǎn)）相聯(lián)系，并且根結(jié)點(diǎn)還沒有父結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)與同一層結(jié)點(diǎn)間沒有任何橫向聯(lián)系；而在圖結(jié)構(gòu)中，數(shù)據(jù)元素之間的聯(lián)系是任意的，每個(gè)元素可以和其他元素相聯(lián)系，從這個(gè)意義上來講，樹是一種特殊形式的圖。圖包括一些點(diǎn)和邊，故一個(gè)圖G由點(diǎn)V(G)和邊E(G)這兩個(gè)集合組成第20頁,共105頁，2024年2月25日，星期天無向圖G1（1）

G1=（V1，E1）V1=｛1，2，3，4，5｝E1=｛（1，2），（1，3），（3，4），（4，5）｝在無向圖中，邊沒有方向：（1，3）也可寫成（3，1）。第21頁,共105頁，2024年2月25日，星期天（2）有向圖G2

G2=（V2，E2）V2=｛1，2，3，4，5，6｝E2=｛<1，2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>｝在有向圖中，邊有方向：<2,4>不能寫成<4,2>。第22頁,共105頁，2024年2月25日，星期天

與圖相關(guān)的一些術(shù)語和概念（3）鄰接點(diǎn)——

有邊相連的點(diǎn)。在無向圖中，互鄰的兩邊側(cè)互為鄰接點(diǎn)，若有（V2，V3），則V3和V2互為鄰接點(diǎn)；在有向圖中，若有<V2，V3>，則V3為V2的鄰接點(diǎn)，但V2不一定是V3的鄰接點(diǎn)，除非也存在<V3，V2>。頂點(diǎn)的度——

與每個(gè)頂點(diǎn)相連的邊數(shù)。在無向圖中，以該頂點(diǎn)為一個(gè)端點(diǎn)的邊的條數(shù)。在有向圖中，有入度（進(jìn)的邊數(shù)）和出度（出的邊數(shù)）之分。路徑——

某一頂點(diǎn)到達(dá)另一頂點(diǎn)所經(jīng)過的頂點(diǎn)序列。兩個(gè)頂點(diǎn)之間可以有多條路徑。路徑上的邊的數(shù)目稱為路徑的長度。網(wǎng)絡(luò)——

如果圖G(V，E)中每一條邊都賦有反映這條邊的某種特性的數(shù)值，則稱此圖為一個(gè)網(wǎng)絡(luò)（圖13-1-10），稱與邊相關(guān)的數(shù)值為該邊的權(quán)。第23頁,共105頁，2024年2月25日，星期天圖的存儲(chǔ)結(jié)構(gòu)2鄰接矩陣（1）基本思想：一個(gè)圖由頂點(diǎn)集合、邊集合（頂點(diǎn)偶對集合，反映頂點(diǎn)間關(guān)系）組成設(shè)G=（V，E）是有n（n≥1）個(gè)頂點(diǎn)的無向圖，則：①一維數(shù)組V[n]={頂點(diǎn)集合}；②G的鄰接矩陣是一個(gè)二維數(shù)組A[n][n]第24頁,共105頁，2024年2月25日，星期天鄰接表（2）為了克服鄰接矩陣的不足，可以采用動(dòng)態(tài)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來保存圖信息，這就是鄰接表。其基本思想是：①對每一個(gè)頂點(diǎn)建立一個(gè)單鏈表。②第i個(gè)單鏈表中存放頂點(diǎn)i的所有鄰接頂點(diǎn)。③第i個(gè)單鏈表的頭結(jié)點(diǎn)中，存放頂點(diǎn)i的信息Vi。第25頁,共105頁，2024年2月25日，星期天鄰接表（2）32^24^5611

5

6^3^l3

4^124365第26頁,共105頁，2024年2月25日，星期天

線性表的查找13.1.5順序查找1查找（Search），又稱檢索，就是在一個(gè)含有n個(gè)數(shù)據(jù)元素的集合中，根據(jù)一個(gè)給定的值k，找出其關(guān)鍵字值等于給定值k的數(shù)據(jù)元素。從第1個(gè)數(shù)據(jù)元素開始，逐個(gè)把數(shù)據(jù)元素的關(guān)鍵字值與給定值比較，若找到某數(shù)據(jù)元素的關(guān)鍵字值與給定值相等，則查找成功；若遍歷整個(gè)線性表都未找到，則查找失敗。第27頁,共105頁，2024年2月25日，星期天二分法查找2當(dāng)順序存儲(chǔ)的線性表已經(jīng)按關(guān)鍵字有序時(shí)，可以使用二分法查找。二分法查找的基本思路是：由于查找表中的數(shù)據(jù)元素按關(guān)鍵字有序（假設(shè)為增序），則查找時(shí)不必逐個(gè)順序比較，而先與中間數(shù)據(jù)元素的關(guān)鍵字比較。若相等，則查找成功；若不等，即把給定值與中間數(shù)據(jù)元素的關(guān)鍵字值比較，若給定值小于中間數(shù)據(jù)元素的關(guān)鍵字值，則在前半部分進(jìn)行二分查找，否則在后半部分進(jìn)行二分查找。這樣，每進(jìn)行一次比較，就將查找區(qū)間縮短為原來的一半。容易證明，在長度為n的有序順序表中進(jìn)行二分查找的查找次數(shù)不超過[log2n+1]次（其中[]代表取整）。第28頁,共105頁，2024年2月25日，星期天分塊查找3分塊查找是介于順序查找與二分法查找之間的一種查找方法，又稱索引順序查找。它的基本思想是：分塊——

將數(shù)據(jù)劃分為若干數(shù)據(jù)塊，數(shù)據(jù)在塊內(nèi)無序，但塊間有序。也就是說，第一塊內(nèi)的最大數(shù)據(jù)比后繼所有塊內(nèi)的所有數(shù)據(jù)都小（假設(shè)按數(shù)據(jù)遞增有序），后面的每一塊內(nèi)的所有數(shù)據(jù)都大于它前面的所有塊的最大數(shù)據(jù)，同時(shí)又小于后繼所有塊內(nèi)的所有數(shù)據(jù)。查找——

分兩步進(jìn)行。①塊間：建立一個(gè)各塊最大關(guān)鍵字值表，將待查數(shù)據(jù)在該表中按二分法或順序查找進(jìn)行，通過塊間查找確定數(shù)據(jù)所在塊。用二分法可以提高塊間查找的效率。②塊內(nèi)：在塊內(nèi)按順序查找方式直接查找元素。第29頁,共105頁，2024年2月25日，星期天

內(nèi)排序

13.1.6插入法排序1排序又稱為分類，它是數(shù)據(jù)處理中經(jīng)常使用的一種運(yùn)算，是將一組數(shù)據(jù)元素（記錄）按其排序碼進(jìn)行遞增或遞減的運(yùn)算操作。排序分內(nèi)排序和外排序。內(nèi)排序——

整個(gè)排序運(yùn)算在內(nèi)存中進(jìn)行。把n個(gè)數(shù)據(jù)元素的序列分成兩部分，一個(gè)是已排好序的有序部分，另一個(gè)是未排好序的未排序部分；把未排好序的元素逐個(gè)與已排好序的元素比較，并插入到有序部分的合適位置，最后得到一個(gè)新的有序序列。第30頁,共105頁，2024年2月25日，星期天選擇排序2每一輪排序中，將第i個(gè)元素與從序列第i+1到n的n-i+1(i=1,2,3,n-1)個(gè)元素中選出的、值最小的一個(gè)元素進(jìn)行比較，若該最小元素比第i個(gè)元素小，則將兩者交換。i從1開始，重復(fù)此過程，直到i=n-1。簡單地說，通過交換位置，選最小的放在第一，次小的放在第二，以此類推，直到元素序列的最后為止。第31頁,共105頁，2024年2月25日，星期天冒泡排序

3冒泡法排序需要進(jìn)行n

1輪的排序過程。第一輪：從a1開始，兩兩比較ai、ai+1（i=1，2，…，n1）的大小，若ai>ai+1，則交換ai與ai+1。當(dāng)?shù)谝惠喭瓿蓵r(shí)，最大元素將被交換到最后一位（第n位）。第二輪：仍然從a1開始，兩兩比較ai、ai+1（i=1，2，…，n2）的大小，注意此時(shí)的處理范圍從第一輪的整個(gè)序列n個(gè)數(shù)據(jù)元素比較n1次（i=1，2，…，n1），變成了n1個(gè)數(shù)據(jù)元素比較n2次（i=1，2，…，n2）。當(dāng)?shù)诙喭瓿蓵r(shí)，最大元素將被交換到次后一位（第n1位）。第n-1輪：只需比較最初兩個(gè)元素，就完成了整個(gè)線性表的排序。第32頁,共105頁，2024年2月25日，星期天冒泡排序

3第33頁,共105頁，2024年2月25日，星期天歸并排序4將兩個(gè)或兩個(gè)以上的有序表組合成一個(gè)新的有序表。將每個(gè)元素看成一個(gè)長度為1的子序列，把相鄰子序列兩兩合并，得到一個(gè)新的子序列，如此重復(fù)，最后得到長度為n的一個(gè)新的有序序列。第34頁,共105頁，2024年2月25日，星期天快速排序——分區(qū)交換排序5快速排序是冒泡法排序的改進(jìn)，平均速度較快?；舅枷肴缦拢孩偃芜x一個(gè)元素Ri（一般為第一個(gè)）做標(biāo)準(zhǔn)。②調(diào)整各元素位置，使排在Ri前的元素的排序碼都小于Ri，而排在Ri后的元素的排序碼都大于Ri。本過程稱為一次快排，由此確定了Ri在有序序列中的最后位置，同時(shí)將剩余元素分為兩個(gè)子序列。③對兩個(gè)子序列分別進(jìn)行快速排序，又確定了兩個(gè)元素在有序序列中的位置，并將剩余元素分為四個(gè)子序列。④重復(fù)此過程，直到各子序列的長度都為1，排序結(jié)束。第35頁,共105頁，2024年2月25日，星期天排序方法的比較和選用6幾種排序的比較：①穩(wěn)定性比較：穩(wěn)定的排序方法有：插入、選擇、歸并、冒泡排序；快速排序是不穩(wěn)定的排序方法。②平均綜合情況：歸并排序、快速排序速度較快，插入、冒泡排序速度較慢。總之，各種排序法各有其優(yōu)缺點(diǎn)。其選用依據(jù)是：①其數(shù)據(jù)規(guī)模n大，內(nèi)存允許，要求穩(wěn)定：選歸并排序。②其數(shù)據(jù)規(guī)模n較小，有穩(wěn)定要求：選插入排序。③其數(shù)據(jù)規(guī)模n大，內(nèi)存允許，對穩(wěn)定不要求：選快速排序。第36頁,共105頁，2024年2月25日，星期天

操作系統(tǒng)的概念和類型13.2.113.2操作系統(tǒng)操作系統(tǒng)（OperatingSystem）是計(jì)算機(jī)系統(tǒng)中最重要的系統(tǒng)軟件，協(xié)調(diào)管理計(jì)算機(jī)的軟硬資源，以提高硬件的利用率；是用戶與計(jì)算機(jī)之間的接口，為用戶使用計(jì)算機(jī)提供操作的平臺(tái)和環(huán)境，以便用戶無需了解計(jì)算機(jī)硬件或系統(tǒng)軟件的有關(guān)細(xì)節(jié)就能方便地使用計(jì)算機(jī).第37頁,共105頁，2024年2月25日，星期天操作系統(tǒng)的基本特征1現(xiàn)代操作系統(tǒng)普遍采用多道程序設(shè)計(jì)技術(shù)，所謂多道程序設(shè)計(jì)技術(shù)是為了提高計(jì)算機(jī)軟硬件資源的利用率，允許在內(nèi)存中同時(shí)安排多個(gè)作業(yè)（用戶軟件程序），各個(gè)作業(yè)共享系統(tǒng)資源，以并發(fā)的方式各自向前推進(jìn)。多道程序設(shè)計(jì)技術(shù)的引入，使得操作系統(tǒng)具有如下基本特征。第38頁,共105頁，2024年2月25日，星期天

并發(fā)性

（1）并發(fā)是指在宏觀上各作業(yè)是并行的（用戶觀點(diǎn)），而在微觀上是串行的（CPU觀點(diǎn)）。各作業(yè)之間的微觀切換只有幾十到幾百毫秒。多個(gè)進(jìn)程可以并發(fā)執(zhí)行和交換信息，操作系統(tǒng)必須具備控制和管理各種并發(fā)活動(dòng)的能力。第39頁,共105頁，2024年2月25日，星期天共享性（2）多道程序或多個(gè)用戶共同使用有限的資源，根據(jù)資源的屬性不同，共享分為：互斥共享——

一段時(shí)間只允許一個(gè)用戶使用的資源，如打印機(jī)。并發(fā)訪問——

一段時(shí)間內(nèi)可有多個(gè)進(jìn)程同時(shí)使用某個(gè)資源。并發(fā)與共享是操作系統(tǒng)最基本的兩個(gè)特征，互為存在條件。第40頁,共105頁，2024年2月25日，星期天（3）虛擬性

把一個(gè)物理設(shè)備變?yōu)檫壿嬌系亩鄠€(gè)。例如：CPU分時(shí)系統(tǒng)的時(shí)間片、一個(gè)物理硬盤通過分區(qū)劃分為多個(gè)邏輯硬盤等。操作系統(tǒng)的作用就是對用戶屏蔽物理細(xì)節(jié)，而提供給用戶一個(gè)簡潔、易用的邏輯接口。第41頁,共105頁，2024年2月25日，星期天不確定性（4）在多道程序設(shè)計(jì)環(huán)境下，由于各用戶程序（進(jìn)程）各自獨(dú)立地向前推進(jìn)，而對系統(tǒng)軟硬件資源的爭奪、對CPU的爭用，導(dǎo)致各程序的執(zhí)行順序和每個(gè)程序的執(zhí)行時(shí)間都是不確定的。第42頁,共105頁，2024年2月25日，星期天批處理操作系統(tǒng)（1）操作系統(tǒng)的分類

2基本特點(diǎn)是：多道，即允許外存中的多個(gè)作業(yè)隊(duì)列進(jìn)入內(nèi)存，由CPU調(diào)度各作業(yè)交替運(yùn)行；成批，即作業(yè)的裝入、運(yùn)行及結(jié)果輸出等都由系統(tǒng)自動(dòng)實(shí)現(xiàn)，不允許用戶干預(yù)。第43頁,共105頁，2024年2月25日，星期天分時(shí)操作系統(tǒng)（2）多個(gè)用戶對系統(tǒng)的資源進(jìn)行時(shí)間上的分享，具體實(shí)現(xiàn)是將CPU的時(shí)間劃分成一個(gè)一個(gè)的時(shí)間片，按某種策略分配給各個(gè)用戶的進(jìn)程使用，每個(gè)用戶都似乎獨(dú)占了CPU一樣。其特點(diǎn)是：多路性——

同時(shí)響應(yīng)多個(gè)終端用戶的服務(wù)請求。交互性——

各終端用戶可以通過終端、鍵盤、鼠標(biāo)等輸入輸出設(shè)備與系統(tǒng)交互，控制作業(yè)的運(yùn)行，得到系統(tǒng)的服務(wù)。獨(dú)立性——

用戶各自獨(dú)立地使用計(jì)算機(jī)。第44頁,共105頁，2024年2月25日，星期天（3）實(shí)時(shí)操作系統(tǒng)

系統(tǒng)能及時(shí)響應(yīng)隨機(jī)發(fā)生的外部事件，并能在最短的時(shí)間內(nèi)完成對事件的處理。其特點(diǎn)是：及時(shí)響應(yīng)——

實(shí)時(shí)任務(wù)必須在指定的時(shí)限內(nèi)響應(yīng)或完成。交互功能——

實(shí)時(shí)系統(tǒng)仍然要求滿足用戶的實(shí)時(shí)交互要求。高可靠性——

實(shí)時(shí)系統(tǒng)往往用于工業(yè)、國防等對實(shí)時(shí)性要求高的場合，如溫度控制、衛(wèi)星發(fā)射等。因此，系統(tǒng)的高可靠性遠(yuǎn)比系統(tǒng)性能更重要。第45頁,共105頁，2024年2月25日，星期天（4）網(wǎng)絡(luò)操作系統(tǒng)計(jì)算機(jī)網(wǎng)絡(luò)是將地理上分布的各數(shù)據(jù)處理系統(tǒng)或計(jì)算機(jī)系統(tǒng)互聯(lián)，實(shí)現(xiàn)資源共享、信息交換和協(xié)作完成任務(wù)。網(wǎng)絡(luò)操作系統(tǒng)是管理計(jì)算機(jī)網(wǎng)絡(luò)，為用戶提供網(wǎng)絡(luò)資源共享、系統(tǒng)安全及多種網(wǎng)絡(luò)應(yīng)用服務(wù)的操作系統(tǒng)。網(wǎng)絡(luò)操作系統(tǒng)的基本特點(diǎn)是處理上的分布，也就是功能和任務(wù)上的分布以及系統(tǒng)管理的分布。第46頁,共105頁，2024年2月25日，星期天分布式操作系統(tǒng)（5）分布式系統(tǒng)是將地理上分布的各數(shù)據(jù)處理系統(tǒng)或計(jì)算機(jī)系統(tǒng)互聯(lián)，實(shí)現(xiàn)資源共享、信息交換和協(xié)作完成任務(wù)。分布式系統(tǒng)要求一個(gè)統(tǒng)一的操作系統(tǒng)，以實(shí)現(xiàn)系統(tǒng)操作的統(tǒng)一性，其基本特點(diǎn)是處理上的分布，也就是功能和任務(wù)上的分布及系統(tǒng)管理的統(tǒng)一。分布式系統(tǒng)對用戶是透明的，用戶面對的是一個(gè)統(tǒng)一的操作系統(tǒng)，他無法也不必知道系統(tǒng)的內(nèi)部實(shí)現(xiàn)。第47頁,共105頁，2024年2月25日，星期天操作系統(tǒng)的功能3（1）處理機(jī)管理對被多道程序所共享的CPU進(jìn)行分配與回收（實(shí)質(zhì)上就是如何對進(jìn)程進(jìn)行合理調(diào)度），以提高CPU的利用率。（2）內(nèi)存管理一方面，對多個(gè)程序進(jìn)行合理分配與回收內(nèi)存空間，使內(nèi)存利用率盡可能高；另一方面，必須對各程序所占的內(nèi)存空間進(jìn)行必要的存儲(chǔ)保護(hù)，以防止作業(yè)信息被竊取或混淆。同時(shí)，又要滿足合理的共享；必要時(shí)，還要利用外存空間進(jìn)行內(nèi)存擴(kuò)充。（3）I/O設(shè)備管理對各種外部設(shè)備進(jìn)行分配、回收以及共享，以提高設(shè)備利用率。（4）文件管理隨著磁介質(zhì)存儲(chǔ)技術(shù)的進(jìn)步，磁帶、磁鼓、磁盤等大容量輔助存儲(chǔ)設(shè)備普及使用，大量用戶程序、數(shù)據(jù)的存儲(chǔ)組織、存儲(chǔ)保護(hù)、共享等一系列問題，構(gòu)成了操作系統(tǒng)中文件管理的主要內(nèi)容。第48頁,共105頁，2024年2月25日，星期天操作系統(tǒng)的功能3（1）處理機(jī)管理

進(jìn)程調(diào)度又稱為處理機(jī)調(diào)度。在多道程序系統(tǒng)中，有多個(gè)進(jìn)程爭奪處理機(jī)。進(jìn)程調(diào)度的任務(wù)是協(xié)調(diào)和控制各進(jìn)程對CPU的使用，它直接影響CPU利用率及系統(tǒng)性能。在下列情況下會(huì)出現(xiàn)進(jìn)程調(diào)度：①正在執(zhí)行的進(jìn)程已運(yùn)行完畢；②正在進(jìn)行的進(jìn)程由于等待某種條件的發(fā)生（如I/O請求）；③分時(shí)系統(tǒng)執(zhí)行進(jìn)程的時(shí)間片已用完；④就緒隊(duì)列中出現(xiàn)高優(yōu)先級的進(jìn)程申請使用CPU等。時(shí)間片到等待事件發(fā)生進(jìn)程調(diào)度釋放執(zhí)行狀態(tài)等待狀態(tài)就緒狀態(tài)事件發(fā)生第49頁,共105頁，2024年2月25日，星期天（2）

內(nèi)存管理存儲(chǔ)器管理主要是對主存儲(chǔ)空間的管理,包括：內(nèi)存分配——

為實(shí)現(xiàn)多道程序共享內(nèi)存而進(jìn)行的內(nèi)存的動(dòng)態(tài)分配、動(dòng)態(tài)回收，包含管理內(nèi)存分配表、制定分配策略、確定內(nèi)存區(qū)域的劃分方式等。內(nèi)存空間共享——

包括共享內(nèi)存資源和內(nèi)存區(qū)域信息共享。存儲(chǔ)保護(hù)——

為了避免內(nèi)存中多道程序之間的相互干擾，必須對內(nèi)存中程序、數(shù)據(jù)和信息進(jìn)行保護(hù)。地址映射——

在多道程序系統(tǒng)中程序裝入內(nèi)存前通常為邏輯地址，編址從0開始。為保證程序的執(zhí)行，操作系統(tǒng)需要為它分配一個(gè)合適的存儲(chǔ)空間，并將程序執(zhí)行時(shí)要訪問的地址空間中的邏輯地址變換成內(nèi)存空間中對應(yīng)的實(shí)際物理地址。這種地址的轉(zhuǎn)換過程稱為地址映射或重定位。內(nèi)存擴(kuò)充——

利用外存空間來邏輯擴(kuò)充內(nèi)存，也就是把暫時(shí)不用的程序、數(shù)據(jù)調(diào)至外存的某特定區(qū)域。這個(gè)區(qū)域被作為系統(tǒng)的邏輯內(nèi)存使用。第50頁,共105頁，2024年2月25日，星期天I/O設(shè)備管理（3）設(shè)備管理的內(nèi)容包括：①向用戶提供使用外設(shè)的方便接口。②充分發(fā)揮設(shè)備的效率，提高CPU與設(shè)備之間、設(shè)備與設(shè)備之間的并行工作程度。第51頁,共105頁，2024年2月25日，星期天（4）文件管理文件系統(tǒng)是指操作系統(tǒng)中負(fù)責(zé)管理和存放文件信息的軟件機(jī)構(gòu)，它向用戶提供了一種簡便、統(tǒng)一的存取和管理信息的方法。文件系統(tǒng)的功能包括：①文件存儲(chǔ)空間（外存）的管理。②文件名到文件存儲(chǔ)空間的映射，實(shí)現(xiàn)文件“按名存取”。③實(shí)現(xiàn)對文件的各種操作。④支持文件的共享。⑤提供文件的保護(hù)與保密措施。第52頁,共105頁，2024年2月25日，星期天操作系統(tǒng)的用戶接口4用戶可以通過以下兩種接口獲得操作系統(tǒng)服務(wù)。（1）命令接口通過命令解釋程序提供的一組聯(lián)機(jī)操作命令，從鍵盤直接操縱計(jì)算機(jī)。（2）系統(tǒng)調(diào)用接口用戶在程序中使用系統(tǒng)提供的一組系統(tǒng)調(diào)用來使用計(jì)算機(jī)。第53頁,共105頁，2024年2月25日，星期天

處理機(jī)管理13.2.2處理機(jī)管理是操作系統(tǒng)的主要的功能，它實(shí)現(xiàn)的是對處理器的分配，并對其進(jìn)行有效的控制和管理。在現(xiàn)代操作系統(tǒng)中，處理器的分配和調(diào)度都是以進(jìn)程為單位的，因而對處理器的管理也可以視為對處理器的管理。第54頁,共105頁，2024年2月25日，星期天進(jìn)程的概念1進(jìn)程是可并發(fā)執(zhí)行的程序在給定數(shù)據(jù)集合上的一次執(zhí)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立的基本單位和實(shí)體，是指執(zhí)行一個(gè)映像程序的總環(huán)境。第55頁,共105頁，2024年2月25日，星期天進(jìn)程的特征

2（1）動(dòng)態(tài)性進(jìn)程是程序執(zhí)行的一次動(dòng)態(tài)過程，具有生命期。一個(gè)進(jìn)程要經(jīng)歷“創(chuàng)建→調(diào)度→撤銷”三個(gè)過程。（2）并發(fā)性使程序能與其他程序并發(fā)執(zhí)行，這是引入進(jìn)程的目的。（3）獨(dú)立性進(jìn)程是系統(tǒng)分配資源、獨(dú)立運(yùn)行的基本單位，各進(jìn)程間相互獨(dú)立。（4）異步性各進(jìn)程各自獨(dú)立地、按不可預(yù)知的速度向前推進(jìn)。第56頁,共105頁，2024年2月25日，星期天進(jìn)程結(jié)構(gòu)3進(jìn)程由進(jìn)程控制塊（PCB）、程序及數(shù)據(jù)集合三部分組成。進(jìn)程控制塊是系統(tǒng)感知、管理和調(diào)度進(jìn)程的唯一依據(jù)。第57頁,共105頁，2024年2月25日，星期天

進(jìn)程的三種基本狀態(tài)及相互轉(zhuǎn)換

4所謂基本狀態(tài)，是指進(jìn)程的當(dāng)前行為。進(jìn)程具有三種基本狀態(tài)，并可以在一定的條件下相互轉(zhuǎn)換。圖13-2-1是三種基本狀態(tài)的轉(zhuǎn)換示意圖。就緒狀態(tài)——

進(jìn)程已獲得除CPU以外的所有資源。系統(tǒng)中處于就緒的進(jìn)程可以有多個(gè)，往往以鏈表形式構(gòu)成就緒隊(duì)列，等待CPU調(diào)度。執(zhí)行狀態(tài)

——

正執(zhí)行，即當(dāng)前進(jìn)程獨(dú)占CPU，正執(zhí)行其所屬程序。阻塞狀態(tài)

——

又稱為等待狀態(tài)，指進(jìn)程等待某個(gè)事件的發(fā)生而暫時(shí)不能運(yùn)行的狀態(tài)。例如，兩個(gè)進(jìn)程同時(shí)申請某個(gè)資源，則未占用該資源的進(jìn)程處于等待狀態(tài)，必須待該資源被釋放后才可使用，或者某進(jìn)程等待I/O外部設(shè)備讀入數(shù)據(jù)等。時(shí)間片到等待事件發(fā)生進(jìn)程調(diào)度釋放執(zhí)行狀態(tài)等待狀態(tài)就緒狀態(tài)事件發(fā)生第58頁,共105頁，2024年2月25日，星期天進(jìn)程調(diào)度5進(jìn)程調(diào)度又稱為處理機(jī)調(diào)度。在多道程序系統(tǒng)中，有多個(gè)進(jìn)程爭奪處理機(jī)。進(jìn)程調(diào)度的任務(wù)是協(xié)調(diào)和控制各進(jìn)程對CPU的使用，它直接影響CPU利用率及系統(tǒng)性能。在下列情況下會(huì)出現(xiàn)進(jìn)程調(diào)度：①正在執(zhí)行的進(jìn)程已運(yùn)行完畢；②正在進(jìn)行的進(jìn)程由于等待某種條件的發(fā)生（如I/O請求）；③分時(shí)系統(tǒng)執(zhí)行進(jìn)程的時(shí)間片已用完；④就緒隊(duì)列中出現(xiàn)高優(yōu)先級的進(jìn)程申請使用CPU等。第59頁,共105頁，2024年2月25日，星期天進(jìn)程調(diào)度的方式（1）剝奪方式

——

有高優(yōu)先級的進(jìn)程出現(xiàn)立即剝奪正在執(zhí)行的進(jìn)程，將CPU轉(zhuǎn)讓給高優(yōu)先權(quán)的進(jìn)程。非剝奪方式

——

即一旦把CPU分配給某個(gè)進(jìn)程，該進(jìn)程將一直占有CPU，直到時(shí)間片到或進(jìn)程進(jìn)入等待狀態(tài)時(shí)才讓出CPU。第60頁,共105頁，2024年2月25日，星期天進(jìn)程調(diào)度的算法

（2）先來先服務(wù)（FCFS）調(diào)度算法

——

就緒進(jìn)程按先后次序排成隊(duì)列，按先來先服務(wù)的方式調(diào)度，是一種非剝奪式調(diào)度算法，容易實(shí)現(xiàn)，但是服務(wù)質(zhì)量差，等待時(shí)間長，周轉(zhuǎn)時(shí)間長。最短CPU運(yùn)算期優(yōu)先算法（SCBF）

——

最先調(diào)度CPU處理時(shí)間短的進(jìn)程。時(shí)間片輪轉(zhuǎn)算法（RR）

——

主要用于分時(shí)系統(tǒng)，按公平服務(wù)原則，將CPU時(shí)間劃分為一個(gè)個(gè)時(shí)間片，一個(gè)進(jìn)程被調(diào)度后執(zhí)行一個(gè)時(shí)間片，當(dāng)時(shí)間片用完后，強(qiáng)迫讓出CPU而排到就緒隊(duì)列的末尾，等待下一次調(diào)度。第61頁,共105頁，2024年2月25日，星期天進(jìn)程調(diào)度的算法

（2）最高優(yōu)先級算法（HPF）

——

該算法的核心是確定進(jìn)程的優(yōu)先級，即進(jìn)程調(diào)度每次都將CPU分配給就緒隊(duì)列中具有最高優(yōu)先級的進(jìn)程，這在多道程序系統(tǒng)中廣泛采用。多級隊(duì)列反饋法

——

是一種綜合的調(diào)度算法，基本做法是：①先按優(yōu)先級分別設(shè)置N個(gè)就緒隊(duì)列。高優(yōu)先級隊(duì)列時(shí)間片短，低優(yōu)先級隊(duì)列時(shí)間片長，以滿足不同類型的作業(yè)（如終端交互命令需要高響應(yīng)度、長時(shí)間運(yùn)算需要長時(shí)間片）的需要。②各個(gè)進(jìn)程的優(yōu)先級按進(jìn)程動(dòng)態(tài)特性進(jìn)行動(dòng)態(tài)調(diào)整；并調(diào)整所在優(yōu)先級隊(duì)列。③系統(tǒng)總是先調(diào)度優(yōu)先級高的隊(duì)列。④同一優(yōu)先級隊(duì)列中的進(jìn)程按先后次序排列，一般以時(shí)間片或先來先服務(wù)算法進(jìn)行調(diào)度。第62頁,共105頁，2024年2月25日，星期天進(jìn)程通信機(jī)制6并發(fā)執(zhí)行的進(jìn)程需要進(jìn)行信息交換，以便協(xié)調(diào)一致地完成指定的任務(wù)，這種聯(lián)系是通過交換一定數(shù)量的信息來實(shí)現(xiàn)。它分為：低級通信方式——

傳遞控制信息（如進(jìn)程同步、互斥）。高級通信方式——

大批量數(shù)據(jù)的交換第63頁,共105頁，2024年2月25日，星期天臨界資源（1）同步（2）（3）互斥系統(tǒng)中有些資源可以供多個(gè)進(jìn)程同時(shí)使用，而有些資源則一次只允許一個(gè)進(jìn)程使用，我們把一次只允許一個(gè)進(jìn)程使用的資源稱為臨界資源。很多物理設(shè)備如打印機(jī)、磁帶機(jī)等都屬于臨界資源。若干進(jìn)程為完成一個(gè)共同任務(wù)而相互合作，一個(gè)進(jìn)程會(huì)由于等待另一進(jìn)程的某個(gè)事件而阻塞自己，直到其他協(xié)調(diào)進(jìn)程給出協(xié)調(diào)信號后方被喚醒而繼續(xù)執(zhí)行。指進(jìn)程間爭奪獨(dú)占資源。當(dāng)一個(gè)進(jìn)程獲得某獨(dú)占資源（如CPU、I/O設(shè)備等）后，其他申請?jiān)撡Y源的進(jìn)程必須等待，直到獨(dú)占該資源的進(jìn)程釋放該資源為止第64頁,共105頁，2024年2月25日，星期天同步機(jī)制應(yīng)遵循的準(zhǔn)則（4）同步機(jī)制應(yīng)遵循以下四個(gè)原則：空閑讓進(jìn)——

臨界區(qū)中沒有進(jìn)程時(shí)，應(yīng)允許申請進(jìn)入臨界區(qū)的進(jìn)程進(jìn)入。忙則等待——

臨界區(qū)中只能有進(jìn)程，只要臨界區(qū)中有進(jìn)程，其他進(jìn)程不能進(jìn)入。有限等待——

申請進(jìn)入臨界區(qū)的進(jìn)程經(jīng)過有限時(shí)間的等待總能夠進(jìn)入臨界區(qū)。讓權(quán)等待——

臨界區(qū)外的進(jìn)程不得阻塞其他進(jìn)程進(jìn)入臨界區(qū)。第65頁,共105頁，2024年2月25日，星期天常用的同步互斥方式

（5）信號量機(jī)制——

這是第一個(gè)成功的進(jìn)程同步與互斥機(jī)制。信號量是表示資源的物理量，其值只能由P、V操作（增加、減少操作）改變；根據(jù)用途的不同，又分為公用信號量和私有信號量。公用信號量一般用于互斥，私有信號量一般用于同步。按值的不同，又分為整型信號量和信號量集。整型信號量的值可以為0，表示已無可用資源；可以為正值，表示可以使用的資源數(shù)量；也可以為負(fù)值，表示有一個(gè)或多個(gè)因等待該資源而被阻塞的進(jìn)程。管程——

系統(tǒng)中的資源被用數(shù)據(jù)抽象地表示出來，代表共享資源的數(shù)據(jù)及在其上操作的一組過程就構(gòu)成了管程。管程機(jī)制將用戶從復(fù)雜的P、V操作中解放出來，而交由高級語言編譯程序完成，實(shí)現(xiàn)了臨界區(qū)互斥的自動(dòng)化。第66頁,共105頁，2024年2月25日，星期天（6）高級通信

消息緩沖區(qū)通信——

又稱為直接通信，是利用內(nèi)存公共信息緩沖區(qū)實(shí)現(xiàn)信息網(wǎng)信息交換，它每次傳遞的信息有限。管道通信——

利用管道文件進(jìn)行數(shù)據(jù)通信，管道的讀寫操作必須同步和互斥，以保證通信的正確性，具有傳輸數(shù)據(jù)量大，但通信速度慢等特點(diǎn)。信箱通信——

以傳遞、接收、回答信件為通信的基本方式。即發(fā)送進(jìn)程中建立一個(gè)與接收進(jìn)程相連接的郵箱。發(fā)送進(jìn)程把消息送進(jìn)郵箱，接收進(jìn)程從郵箱中取出消息，從而完成進(jìn)程網(wǎng)信息交換。發(fā)送和接收沒有處理時(shí)間上的限制。第67頁,共105頁，2024年2月25日，星期天產(chǎn)生死鎖的原因死鎖7（1）死鎖的定義是：若干進(jìn)程彼此互相等待對方所擁有且不放棄的資源，結(jié)果誰也無法控制繼續(xù)進(jìn)行下去所需要的全部資源而永遠(yuǎn)等待下去的現(xiàn)象。

①爭奪共享資源而引起的死鎖。②進(jìn)程推進(jìn)順序不當(dāng)而引起的死鎖第68頁,共105頁，2024年2月25日，星期天死鎖的預(yù)防

產(chǎn)生死鎖的必要條件

（2）（3）互斥條件（即獨(dú)占）——進(jìn)程對資源的占用是獨(dú)占方式的，其他進(jìn)程若想申請被其他進(jìn)程占用的資源，必須等待占用者自行釋放資源。不剝奪條件——在進(jìn)程未使用完之前，始終不放棄對資源的占有。環(huán)路條件——進(jìn)程A等待進(jìn)程B釋放資源X←→進(jìn)程B等待進(jìn)程C釋放資源Y←→進(jìn)程C等待進(jìn)程A釋放資源Z。三個(gè)進(jìn)程相互等待，形成環(huán)路，誰都無法獲得資源并運(yùn)行。部分分配條件——進(jìn)程申請新資源的同時(shí)，仍繼續(xù)占有已分配給它的資源。只要破壞了死鎖的四個(gè)必要條件之一，就可以有效地預(yù)防死鎖。例如，采用資源的靜態(tài)預(yù)分配策略，破壞部分分配條件；允許進(jìn)程剝奪使用其他進(jìn)程占有的資源第69頁,共105頁，2024年2月25日，星期天死鎖的避免（4）死鎖的檢測和解除（5）在進(jìn)程申請系統(tǒng)資源時(shí)，系統(tǒng)按某種算法判斷分配后，系統(tǒng)是否安全，也就是保證是否存在一個(gè)資源分配序列，當(dāng)按此序列分配時(shí)，各進(jìn)程能依次執(zhí)行完畢，并釋放資源。若安全則分配，否則不予分配。一種避免死鎖的典型算法是銀行家算法。系統(tǒng)定時(shí)運(yùn)行死鎖的檢測程序，判斷系統(tǒng)是否已出現(xiàn)死鎖，稱為死鎖檢測。解除死鎖的方法有撤消進(jìn)程法和資源剝奪法。第70頁,共105頁，2024年2月25日，星期天

存儲(chǔ)器管理13.2.3存儲(chǔ)器管理主要是對主存儲(chǔ)空間的管理。內(nèi)存分配——

為實(shí)現(xiàn)多道程序共享內(nèi)存而進(jìn)行的內(nèi)存的動(dòng)態(tài)分配、動(dòng)態(tài)回收，包含管理內(nèi)存分配表、制定分配策略、確定內(nèi)存區(qū)域的劃分方式等。內(nèi)存空間共享——

包括共享內(nèi)存資源和內(nèi)存區(qū)域信息共享。存儲(chǔ)保護(hù)——

為了避免內(nèi)存中多道程序之間的相互干擾，必須對內(nèi)存中程序、數(shù)據(jù)和信息進(jìn)行保護(hù)。地址映射——

在多道程序系統(tǒng)中程序裝入內(nèi)存前通常為邏輯地址，編址從0開始。為保證程序的執(zhí)行，操作系統(tǒng)需要為它分配一個(gè)合適的存儲(chǔ)空間，并將程序執(zhí)行時(shí)要訪問的地址空間中的邏輯地址變換成內(nèi)存空間中對應(yīng)的實(shí)際物理地址。內(nèi)存擴(kuò)充——

利用外存空間來邏輯擴(kuò)充內(nèi)存，也就是把暫時(shí)不用的程序、數(shù)據(jù)調(diào)至外存的某特定區(qū)域。這個(gè)區(qū)域被作為系統(tǒng)的邏輯內(nèi)存使用第71頁,共105頁，2024年2月25日，星期天要求進(jìn)程完整裝入內(nèi)存的情況

（1）進(jìn)程可以不完整裝入內(nèi)存的虛擬存儲(chǔ)器技術(shù)

（2）①內(nèi)存連續(xù)分配下的管理技術(shù)有：固定分區(qū)管理、可變分區(qū)管理。②不連續(xù)分配下的分頁管理、分段管理及段頁式管理等。

①虛擬頁式（請求頁式）。②虛擬段式（請求段式）。③虛擬段頁式。第72頁,共105頁，2024年2月25日，星期天

設(shè)備管理13.2.4設(shè)備分類1按工作特性，設(shè)備可分為輸入輸出設(shè)備和存儲(chǔ)設(shè)備兩類。從資源分配的角度可將設(shè)備分為：獨(dú)占設(shè)備——

如打印機(jī)、終端等。一個(gè)作業(yè)用完后，另一個(gè)才可使用。共享設(shè)備——

允許多個(gè)作業(yè)同時(shí)使用的設(shè)備，如磁盤等。虛擬設(shè)備——

用虛擬設(shè)備管理技術(shù)，如SPOOLing（SimultaneousPeripheryOperationsOnLine，外圍設(shè)備同時(shí)聯(lián)機(jī)操作），把獨(dú)占設(shè)備變?yōu)檫壿嬌系墓蚕碓O(shè)備，以提高設(shè)備利用率第73頁,共105頁，2024年2月25日，星期天設(shè)備組成

2設(shè)備包括機(jī)械部分的設(shè)備本身以及設(shè)備控制器。計(jì)算機(jī)通過設(shè)備控制器控制設(shè)備完成輸入輸出操作。設(shè)備管理的任務(wù)3①向用戶提供使用外設(shè)的方便接口。②充分發(fā)揮設(shè)備的效率，提高CPU與設(shè)備之間、設(shè)備與設(shè)備之間的并行工作程度。數(shù)據(jù)傳送控制方式4設(shè)備與CPU間數(shù)據(jù)傳送的常用方式有中斷控制方式、DMA方式和通道方式三種。第74頁,共105頁，2024年2月25日，星期天緩沖技術(shù)5SPOOLing技術(shù)6為了解決外設(shè)與CPU速度匹配問題，減少中斷次數(shù)和CPU的中斷處理時(shí)間，引入了暫存數(shù)據(jù)的緩沖技術(shù)。其基本思想是：在內(nèi)存中開辟一個(gè)或多個(gè)專用的區(qū)域，作為CPU與I/O設(shè)備之間信息傳輸?shù)募⒌豐POOLing技術(shù)是一個(gè)資源轉(zhuǎn)換技術(shù)，將獨(dú)占設(shè)備改造成共享設(shè)備。方法是：在磁盤中設(shè)置輸入輸出緩沖區(qū)（分別稱為輸入井、輸出井），用一個(gè)系統(tǒng)進(jìn)程模擬輸入管理機(jī)，一個(gè)系統(tǒng)進(jìn)程模擬輸出管理機(jī)。第75頁,共105頁，2024年2月25日，星期天設(shè)備分配的方式7設(shè)備獨(dú)立性8靜態(tài)分配——就是在進(jìn)程執(zhí)行之初就分配，一直不變，直到進(jìn)程結(jié)束才歸還。此種方案簡單、安全，但低效。動(dòng)態(tài)分配——在進(jìn)程執(zhí)行中，根據(jù)進(jìn)程需要?jiǎng)討B(tài)申請和分配資源，動(dòng)態(tài)歸還。這種方案，設(shè)備利用率高，但如果分配不當(dāng)，可能導(dǎo)致死鎖。用戶在使用設(shè)備時(shí)，使用的是一個(gè)簡潔、方便的邏輯設(shè)備接口，而不涉及物理設(shè)備細(xì)節(jié)。操作系統(tǒng)的設(shè)備管理功能提供從邏輯設(shè)備到具體物理設(shè)備的映射，這就是設(shè)備獨(dú)立性。第76頁,共105頁，2024年2月25日，星期天設(shè)備相關(guān)層設(shè)備管理的相關(guān)軟件9設(shè)備無關(guān)層

（1）（2）用戶I/O程序——一般體現(xiàn)為庫函數(shù)、庫例程。設(shè)備無關(guān)軟件——如緩沖區(qū)管理、邏輯設(shè)備到物理設(shè)備的映射等。設(shè)備驅(qū)動(dòng)程序——主要負(fù)責(zé)接收和分析從設(shè)備分配轉(zhuǎn)來的信息，并根據(jù)設(shè)備分配的結(jié)果，結(jié)合具體物理設(shè)備特性啟動(dòng)設(shè)備，完成具體的輸入輸出工作。I/O中斷處理程序——當(dāng)設(shè)備完成輸入輸出任務(wù)后，一般通過中斷通知操作系統(tǒng)，I/O中斷處理程序就是處理來自設(shè)備的中斷。啟動(dòng)相關(guān)的設(shè)備驅(qū)動(dòng)程序。第77頁,共105頁，2024年2月25日，星期天

文件管理13.2.5文件系統(tǒng)1文件系統(tǒng)是指操作系統(tǒng)中負(fù)責(zé)管理和存放文件信息的軟件機(jī)構(gòu)，它向用戶提供了一種簡便、統(tǒng)一的存取和管理信息的方法。文件系統(tǒng)的功能包括：①文件存儲(chǔ)空間（外存）的管理。②文件名到文件存儲(chǔ)空間的映射，實(shí)現(xiàn)文件“按名存取”。③實(shí)現(xiàn)對文件的各種操作。④支持文件的共享。⑤提供文件的保護(hù)與保密措施。第78頁,共105頁，2024年2月25日，星期天文件目錄2文件目錄是文件系統(tǒng)的關(guān)鍵數(shù)據(jù)結(jié)構(gòu)，是由文件說明索引組成的用于文件檢索的特殊文件。每個(gè)項(xiàng)目是一個(gè)文件控制塊（FCB），它記錄了文件說明和控制信息。文件目錄分為：一級目錄

——整個(gè)目錄組織是一個(gè)線性結(jié)構(gòu)，系統(tǒng)中的所有文件都建立在一張目錄表中。它主要用于單用戶操作系統(tǒng)。二級目錄

——在根目錄下，每個(gè)用戶對應(yīng)一個(gè)目錄（第二級目錄）；在用戶目錄下是該用戶的文件，而不再有下級目錄。它適用于多用戶系統(tǒng)，各用戶可有自己的專用目錄。多級目錄

——或稱為樹狀目錄（Tree-like）。在文件數(shù)目較多時(shí)，便于系統(tǒng)和用戶將文件分散管理，適用于較大的文件系統(tǒng)管理。目錄級別太多時(shí)會(huì)增加路徑檢索時(shí)間。第79頁,共105頁，2024年2月25日，星期天文件共享與保護(hù)3文件訪問權(quán)限按訪問類型可以分為：讀（Read）、寫（Write）、執(zhí)行（Execute）和刪除（Delete）等。文件的共享與文件的保護(hù)保密是同一個(gè)問題的兩個(gè)方面，實(shí)質(zhì)是有條件地共享。

第80頁,共105頁，2024年2月25日，星期天

軟件工程概述13.3.113.3軟件工程軟件工程的概念起源于20世紀(jì)60年代末期出現(xiàn)的“軟件危機(jī)”。軟件危機(jī)提高了人們對軟件開發(fā)重要性的認(rèn)識(shí)。隨著社會(huì)對軟件需求的增長，計(jì)算機(jī)軟件專家加強(qiáng)了對軟件開發(fā)和維護(hù)的規(guī)律性、理論、方法和技術(shù)的研究，從而形成了一門介于軟件科學(xué)、系統(tǒng)工程和工程管理學(xué)之間的邊緣性學(xué)科，稱之為軟件工程學(xué)。

第81頁,共105頁，2024年2月25日，星期天軟件1軟件是程序的完善和發(fā)展，是經(jīng)過嚴(yán)格的正確性檢驗(yàn)和實(shí)際試用，并具有相對穩(wěn)定的文本和完整的文檔資料的程序。這些文檔資料包括功能說明、算法說明、結(jié)構(gòu)說明、使用說明和維護(hù)說明等。

第82頁,共105頁，2024年2月25日，星期天軟件工程時(shí)期（1970年至今）

程序設(shè)計(jì)時(shí)期（1946年至20世紀(jì)60年代中期）軟件開發(fā)經(jīng)歷的三個(gè)階段2（1）軟件時(shí)期（20世紀(jì)60年代中期至20世紀(jì)70年代中期）

（2）（3）第83頁,共105頁，2024年2月25日，星期天軟件危機(jī)3軟件開發(fā)的高成本與軟件產(chǎn)品的低質(zhì)量之間的尖銳矛盾，終于導(dǎo)致了軟件危機(jī)的發(fā)生。具體來說，軟件危機(jī)主要有以下幾方面的表現(xiàn)：①軟件的復(fù)雜性越來越高，“手工作坊”式的軟件開發(fā)方式已無法滿足要求。②對軟件開發(fā)的成本和進(jìn)度統(tǒng)計(jì)不準(zhǔn)，實(shí)際費(fèi)用超過預(yù)算。③開發(fā)周期過長。④軟件質(zhì)量難以保證，常被懷疑。⑤缺乏良好的軟件文檔。⑥軟件維護(hù)難度極大。⑦軟件開發(fā)效率遠(yuǎn)跟不上計(jì)算機(jī)發(fā)展的需求。⑧用戶往往對軟件不滿意。第84頁,共105頁，2024年2月25日，星期天軟件工程學(xué)概述4軟件工程學(xué)的研究對象（1）軟件工程學(xué)的基本目標(biāo)

（2）軟件工程學(xué)研究如何應(yīng)用一些科學(xué)理論和工程技術(shù)來指導(dǎo)軟件系統(tǒng)的開發(fā)與維護(hù)，使其成為一門嚴(yán)格的工程學(xué)科。

軟件工程學(xué)的基本目標(biāo)在于研究一套科學(xué)的工程方法，設(shè)計(jì)一套方便實(shí)用的工具系統(tǒng)，以達(dá)到在軟件研制生產(chǎn)中投資少、效率高、質(zhì)量優(yōu)的目的第85頁,共105頁，2024年2月25日，星期天軟件生命周期（SoftwareLifeCycle）

（4）一個(gè)軟件項(xiàng)目從問題提出、定義、開發(fā)、使用、維護(hù)，直至被廢棄，要經(jīng)歷一個(gè)漫長的時(shí)期，通常把這個(gè)時(shí)期稱為軟件生命周期。

（3）軟件工程學(xué)的三要素

軟件工程學(xué)的三個(gè)基本要素是方法、工具和管理。

第86頁,共105頁，2024年2月25日，星期天

軟件生存周期13.3.2軟件工程學(xué)將軟件的生命周期分解為幾個(gè)階段，每個(gè)階段的任務(wù)都相對獨(dú)立、簡單，便于不同的人員分工協(xié)作，每個(gè)階段都有明確的要求、嚴(yán)格的標(biāo)準(zhǔn)與規(guī)范，以及與開發(fā)軟件完全一致的高質(zhì)量的文檔資料，從而保證軟件開發(fā)工程結(jié)束時(shí)有一個(gè)完整準(zhǔn)確的軟件配置交付使用。劃分軟件生命周期階段應(yīng)遵循的一條基本原則是各階段的任務(wù)應(yīng)盡可能相對獨(dú)立，以降低每個(gè)階段的復(fù)雜程度，簡化不同階段之間的聯(lián)系，利于軟件開發(fā)工程管理。一般情況下，軟件生命周期由軟件定義、軟件開發(fā)、軟件維護(hù)三個(gè)時(shí)期組成。每個(gè)時(shí)期又分為若干個(gè)階段。

第87頁,共105頁，2024年2月25日，星期天瀑布模型（1976年由B.W.Boehm提出）1軟件生存周期分為計(jì)劃、開發(fā)、運(yùn)行三個(gè)時(shí)期，每個(gè)周期又分為若干階段。各階段的工作順序展開后，如像自上而下的瀑布，故稱為瀑布模型。按瀑布模型，一個(gè)完整的軟件開發(fā)過程分為如下幾個(gè)階段：①計(jì)劃：分析用戶需求，分析軟件系統(tǒng)追求的目標(biāo)，分析開發(fā)系統(tǒng)的可行性等。②開發(fā)：包括設(shè)計(jì)和實(shí)現(xiàn)兩個(gè)任務(wù)，其中設(shè)計(jì)包括需求分析和設(shè)計(jì)兩個(gè)階段，實(shí)現(xiàn)包括編程和測試兩個(gè)階段。③運(yùn)行：主要任務(wù)是為了軟件維護(hù)和修改問題。

第88頁,共105頁，2024年2月25日，星期天快速原型

2在瀑布模型中，由于系統(tǒng)分析人員和用戶在專業(yè)上的差異，計(jì)劃時(shí)期可能會(huì)造成不完全和不正確的情況發(fā)生。為解決此矛盾，提出了使用快速原型模型。其基本思想是：首先建立一個(gè)能反映用戶主要需求的原型，用戶通過使用該原型來提出對原型的修改意見，再按用戶意見對原型進(jìn)行改進(jìn)。經(jīng)多次反復(fù)后，最后建立起符合用戶需求的新系統(tǒng)。第89頁,共105頁，2024年2月25日，星期天

軟件需求分析13.3.3軟件定義，又稱為系統(tǒng)分析。這個(gè)時(shí)期的任務(wù)，是確定軟件開發(fā)的總目標(biāo)，確定軟件開發(fā)工程的可行性，確定實(shí)現(xiàn)工程目標(biāo)應(yīng)該采用的策略和必須完成的功能，估計(jì)完成該項(xiàng)工程需要的資源和成本，制定出工程進(jìn)度表。軟件定義，可進(jìn)一步劃分為三個(gè)階段，即問題定義、可行性研究和需求分析.第90頁,共105頁，2024年2月25日，星期天問題定義

1問題定義階段必須考慮的問題是“做什么”。正確理解用戶的真正需求，是系統(tǒng)開發(fā)成功的必要條件。軟件開發(fā)人員與用戶之間的溝通，必須通過系統(tǒng)分析員對用戶進(jìn)行訪問調(diào)查，扼要地寫出對問題的理解，并在有用戶參加的會(huì)議上認(rèn)真討論，澄清含糊不清的地方，改正理解不正確的地方，最后得到一份雙方都認(rèn)可的文檔。第91頁,共105頁，2024年2月25日，星期天可行性研究

2可行性研究要研究問題的范圍，并探索這個(gè)問題是否值得去解決，以及是否有可行的解決辦法?？尚行匝芯康慕Y(jié)果是部門負(fù)責(zé)人做出是否繼續(xù)這項(xiàng)工程決定的重要依據(jù)?？尚行哉撟C的內(nèi)容包括：①技術(shù)可行性。②經(jīng)濟(jì)可行性。③操作可行性。第92頁,共105頁，2024年2月25日，星期天需求分析

3需求說明書

（1）需求分析即系統(tǒng)分析，通常采用系統(tǒng)模型定義系統(tǒng)。在可行性分析的基礎(chǔ)上，需求分析的主要任務(wù)是：明確用戶要求軟件系統(tǒng)必須滿足的所有功能、性能和限制，也就是解決軟件“做什么”的問題。

需求分析階段應(yīng)提交的文檔是需求說明書。需求說明書的主要內(nèi)容如下：①概述。②需求說明：功能說明、性能說明。③數(shù)據(jù)描述：數(shù)據(jù)流圖、數(shù)據(jù)字典、接口說明。④運(yùn)行環(huán)境：設(shè)備要求、支持的軟件等。

第93頁,共105頁，2024年2月25日，星期天結(jié)構(gòu)化分析方法（StructuredAnalysis）

（2）結(jié)構(gòu)化分析方法是需求分析的最常用方法，簡稱SA方法，它與設(shè)計(jì)階段的結(jié)構(gòu)化設(shè)計(jì)方法（SD）一起聯(lián)合使用，能夠較好實(shí)現(xiàn)一個(gè)軟件系統(tǒng)的研制。①SA方法的基本手段是通過分解與抽象，建立三個(gè)模型：數(shù)據(jù)模型、功能模型、行為模型，以說明軟件需求，并得到準(zhǔn)確的軟件需求規(guī)格說明。②SA方法采用的基本方法為圖形法，使用以下一些分析工具：數(shù)據(jù)流圖（DFD）——描述系統(tǒng)中數(shù)據(jù)流程的圖形工具。數(shù)據(jù)字典（DD）——放置數(shù)據(jù)流圖中包含的所有元素的定義。結(jié)構(gòu)化語言

——結(jié)構(gòu)化語言是介于自然語言和形式化語言之間的一種類自然語言，它吸收了形式化語言的精確嚴(yán)格與自然語言的簡單易懂的特點(diǎn)，通常由順序、選擇和重復(fù)三種控制結(jié)構(gòu)構(gòu)成，適用于簡單邏輯加工關(guān)系的描述。判定表

——判定表用于簡潔而無歧義地描述加工邏輯規(guī)則。一張判定表通常由四個(gè)部分組成：左上部列出所有的條件，左下部為所有可能的操作，右上部是各種條件組合的一個(gè)矩陣，右下部是對應(yīng)于每種條件組合應(yīng)用的操作。第94頁,共105頁，2024年2月25日，星期天（3）SA方法中導(dǎo)出的分析模型

數(shù)據(jù)字典

——核心，對系統(tǒng)所有數(shù)據(jù)對象的描述。實(shí)體-關(guān)系圖——數(shù)據(jù)對象間關(guān)系，是系統(tǒng)的數(shù)據(jù)模型。數(shù)據(jù)流圖