軟件技術(shù)基礎

軟件技術(shù)基礎

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ù)的運算第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ù)在計算機中的存儲表示方式無關(guān)。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看做是從具體問題抽象出來的數(shù)學模型。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩大類：線性結(jié)構(gòu)——

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

非線性結(jié)構(gòu)的邏輯特征是：一個結(jié)點可以有多個前趨結(jié)點和后繼結(jié)點。如樹形結(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)在計算機存儲器里的映像，也稱為存儲結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)可用以下四種基本存儲方法：順序存儲方法

——

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

——

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

——

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

——

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

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

——

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

——

算法中的每一個操作步驟的含義必須明確?？尚行?/p>

——

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

——

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

——

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

（2）自然語言——

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

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

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

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

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

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

一般地，常用的時間復雜度有如下關(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)。其基本特點是：數(shù)據(jù)元素有序并有限。線性結(jié)構(gòu)的數(shù)據(jù)元素可排成一個線性隊列當線性表采用順序存儲結(jié)構(gòu)時稱之為順序表。在順序表中，數(shù)據(jù)元素按邏輯次序依次放在一組地址連續(xù)的存儲單元里。由于邏輯上相鄰的元素存放在內(nèi)存的相鄰單元里，所以順序表的邏輯關(guān)系蘊含在存儲單元的鄰接關(guān)系中。第9頁,共105頁，2024年2月25日，星期天插入運算（1）（2）刪除運算

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

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

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

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

樹

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

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

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

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

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

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

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

圖的概念1圖是一種重要的、比樹更復雜的非線性數(shù)據(jù)結(jié)構(gòu)。在樹結(jié)構(gòu)中，某結(jié)點只能與其上層的一個結(jié)點（父結(jié)點）相聯(lián)系，并且根結(jié)點還沒有父結(jié)點，每個結(jié)點與同一層結(jié)點間沒有任何橫向聯(lián)系；而在圖結(jié)構(gòu)中，數(shù)據(jù)元素之間的聯(lián)系是任意的，每個元素可以和其他元素相聯(lián)系，從這個意義上來講，樹是一種特殊形式的圖。圖包括一些點和邊，故一個圖G由點V(G)和邊E(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）鄰接點——

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

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

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

如果圖G(V，E)中每一條邊都賦有反映這條邊的某種特性的數(shù)值，則稱此圖為一個網(wǎng)絡（圖13-1-10），稱與邊相關(guān)的數(shù)值為該邊的權(quán)。第23頁,共105頁，2024年2月25日，星期天圖的存儲結(jié)構(gòu)2鄰接矩陣（1）基本思想：一個圖由頂點集合、邊集合（頂點偶對集合，反映頂點間關(guān)系）組成設G=（V，E）是有n（n≥1）個頂點的無向圖，則：①一維數(shù)組V[n]={頂點集合}；②G的鄰接矩陣是一個二維數(shù)組A[n][n]第24頁,共105頁，2024年2月25日，星期天鄰接表（2）為了克服鄰接矩陣的不足，可以采用動態(tài)的鏈式存儲結(jié)構(gòu)來保存圖信息，這就是鄰接表。其基本思想是：①對每一個頂點建立一個單鏈表。②第i個單鏈表中存放頂點i的所有鄰接頂點。③第i個單鏈表的頭結(jié)點中，存放頂點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），又稱檢索，就是在一個含有n個數(shù)據(jù)元素的集合中，根據(jù)一個給定的值k，找出其關(guān)鍵字值等于給定值k的數(shù)據(jù)元素。從第1個數(shù)據(jù)元素開始，逐個把數(shù)據(jù)元素的關(guān)鍵字值與給定值比較，若找到某數(shù)據(jù)元素的關(guān)鍵字值與給定值相等，則查找成功；若遍歷整個線性表都未找到，則查找失敗。第27頁,共105頁，2024年2月25日，星期天二分法查找2當順序存儲的線性表已經(jīng)按關(guān)鍵字有序時，可以使用二分法查找。二分法查找的基本思路是：由于查找表中的數(shù)據(jù)元素按關(guān)鍵字有序（假設為增序），則查找時不必逐個順序比較，而先與中間數(shù)據(jù)元素的關(guān)鍵字比較。若相等，則查找成功；若不等，即把給定值與中間數(shù)據(jù)元素的關(guān)鍵字值比較，若給定值小于中間數(shù)據(jù)元素的關(guān)鍵字值，則在前半部分進行二分查找，否則在后半部分進行二分查找。這樣，每進行一次比較，就將查找區(qū)間縮短為原來的一半。容易證明，在長度為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ù)都?。僭O按數(shù)據(jù)遞增有序），后面的每一塊內(nèi)的所有數(shù)據(jù)都大于它前面的所有塊的最大數(shù)據(jù)，同時又小于后繼所有塊內(nèi)的所有數(shù)據(jù)。查找——

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

內(nèi)排序

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

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

3冒泡法排序需要進行n

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

3第33頁,共105頁，2024年2月25日，星期天歸并排序4將兩個或兩個以上的有序表組合成一個新的有序表。將每個元素看成一個長度為1的子序列，把相鄰子序列兩兩合并，得到一個新的子序列，如此重復，最后得到長度為n的一個新的有序序列。第34頁,共105頁，2024年2月25日，星期天快速排序——分區(qū)交換排序5快速排序是冒泡法排序的改進，平均速度較快。基本思想如下：①任選一個元素Ri（一般為第一個）做標準。②調(diào)整各元素位置，使排在Ri前的元素的排序碼都小于Ri，而排在Ri后的元素的排序碼都大于Ri。本過程稱為一次快排，由此確定了Ri在有序序列中的最后位置，同時將剩余元素分為兩個子序列。③對兩個子序列分別進行快速排序，又確定了兩個元素在有序序列中的位置，并將剩余元素分為四個子序列。④重復此過程，直到各子序列的長度都為1，排序結(jié)束。第35頁,共105頁，2024年2月25日，星期天排序方法的比較和選用6幾種排序的比較：①穩(wěn)定性比較：穩(wěn)定的排序方法有：插入、選擇、歸并、冒泡排序；快速排序是不穩(wěn)定的排序方法。②平均綜合情況：歸并排序、快速排序速度較快，插入、冒泡排序速度較慢。總之，各種排序法各有其優(yōu)缺點。其選用依據(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）是計算機系統(tǒng)中最重要的系統(tǒng)軟件，協(xié)調(diào)管理計算機的軟硬資源，以提高硬件的利用率；是用戶與計算機之間的接口，為用戶使用計算機提供操作的平臺和環(huán)境，以便用戶無需了解計算機硬件或系統(tǒng)軟件的有關(guān)細節(jié)就能方便地使用計算機.第37頁,共105頁，2024年2月25日，星期天操作系統(tǒng)的基本特征1現(xiàn)代操作系統(tǒng)普遍采用多道程序設計技術(shù)，所謂多道程序設計技術(shù)是為了提高計算機軟硬件資源的利用率，允許在內(nèi)存中同時安排多個作業(yè)（用戶軟件程序），各個作業(yè)共享系統(tǒng)資源，以并發(fā)的方式各自向前推進。多道程序設計技術(shù)的引入，使得操作系統(tǒng)具有如下基本特征。第38頁,共105頁，2024年2月25日，星期天

并發(fā)性

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

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

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

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

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

同時響應多個終端用戶的服務請求。交互性——

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

——

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

——

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

——

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

——

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

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

——

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

——

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

——

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

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

——

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

——

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

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

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

臨界區(qū)中沒有進程時，應允許申請進入臨界區(qū)的進程進入。忙則等待——

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

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

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

（5）信號量機制——

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

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

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

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

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

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

①爭奪共享資源而引起的死鎖。②進程推進順序不當而引起的死鎖第68頁,共105頁，2024年2月25日，星期天死鎖的預防

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（3）軟件工程學的三要素

軟件工程學的三個基本要素是方法、工具和管理。

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

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

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

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

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

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

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

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

3需求說明書

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

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

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

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

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

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

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

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