操作系統(tǒng)是一組控制和管理計算機硬件和軟件資源，合理地對各類作業(yè)進行調度，以及方便用戶使用的程序的集合。操作系統(tǒng)的發(fā)展過程：單道批處理系統(tǒng)、多道批處理系統(tǒng)、分時系統(tǒng)、實時系統(tǒng)、網絡操作系統(tǒng)、分布式操作系統(tǒng)。操作系統(tǒng)的類型一單道批處理系統(tǒng)：在系統(tǒng)運行過程中，內存中只有一個用戶作業(yè)存在;把一批作業(yè)脫機輸入到磁帶/磁盤上;系統(tǒng)配上監(jiān)督程序，使這批作業(yè)一個個自動處理;處理機使用權在監(jiān)督程序和用戶作業(yè)間切換。多道批處理系統(tǒng)：內存中允許多道程序存在;存在作業(yè)后備隊列和作業(yè)調度程序;有I/O操作或完成作業(yè)時，調入另一個作業(yè)。假脫機工作方式：SPOOLING系統(tǒng);優(yōu)點：資源利用率高、系統(tǒng)吞吐量大、系統(tǒng)切換開銷小。缺點：無交互能力、作業(yè)平均周轉時間長。分時系統(tǒng)：為滿足人機交互能力的需求、共享主機;分時服務：時間片;分時系統(tǒng)特征：多路性、交互性、獨占性、及時性。實時系統(tǒng):系統(tǒng)能及時響應外部事件的請求，在規(guī)定的時間內完成對該事件的處理，并控制所有實時任務協(xié)調一致地運行。實時系統(tǒng)的類型：實時控制系統(tǒng)、實時信息處理系統(tǒng)。網絡操作系統(tǒng)：高效可靠的網絡通信能力，網絡的連接；結構：C/S，PeertoPeer分布式操作系統(tǒng)：處理上的分布。操作系統(tǒng)的特性：并發(fā)性(并行性和并發(fā)性區(qū)別);共享性(互斥共享方式、同時訪問方式）虛擬性：指通過某種技術把一個物理設備變?yōu)槿舾蓚€邏輯上的對應物。虛擬對象類型--虛擬機：分時系統(tǒng)；虛擬內存：虛存管理技術；虛擬設備：SPOOLING技術異步性：進程以人們不可預知的速度向前推進，但結果要保證是固定的。原因：多道環(huán)境的復雜性。操作系統(tǒng)的主要功能：①處理機管理－進程管理和調度；②存儲器管理－物理內存的管理；③設備管理－外設的管理；④文件管理－外存空間的管理；⑤用戶接口－方便用戶使用進程的基本概念------1前趨圖：描述程序或程序段之間執(zhí)行的前后關系。2進程的定義：進程是一個具有一定獨立功能的程序關于某個數(shù)據集合的一次運行活動;是系統(tǒng)進行資源分配和調度的一個獨立單位。3進程的特征：①結構特征：程序段、數(shù)據段和PCB；②動態(tài)性;③并發(fā)性;④獨立性;⑤異步性4與程序的區(qū)別：進程是動態(tài)的;程序是靜態(tài)的。5進程的基本狀態(tài)及相互轉換：①就緒狀態(tài)；②執(zhí)行狀態(tài)；③阻塞狀態(tài)6掛起狀態(tài)：增加了兩個掛起狀態(tài)：掛起就緒、掛起阻塞進程控制------1引起進程創(chuàng)建的事件：①用戶登錄；②作業(yè)調度；③提供服務；④應用請求進程同步------1主要任務：使并發(fā)執(zhí)行的諸進程之間能有效的共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。2兩種形式的制約關系：間接相互制約關系：源于進程對臨界資源的共享，即進程互斥。直接相互制約關系：源于進程間的合作，即進程同步。3臨界區(qū)：進程中訪問臨界資源的代碼段。4同步應遵循的原則：空閑讓進、忙則等待、有限等待、讓權等待。5信號量機制信號量：僅能被兩個原語操作P/V修改的變量。類型-----整型：信號量為整型值；記錄型：二元組(S,Q)，Q初始狀態(tài)為空的隊列。AND型：一次需要多個共享資源。信號量集：一次需要N個多類共享資源。經典進程同步問題-------1生產者－消費者問題：生產者與消費者互斥訪問公用數(shù)據緩沖區(qū)。生產“數(shù)據”，消費“數(shù)據”。2讀者－寫者問題;數(shù)據文件被多個進程共享并互斥訪問。允許多個讀進程同時訪問，但不允許一個寫進程和其它讀進程、寫進程同時訪問。進程通信-----1進程通信類型低級通信：利用信號量機制實現(xiàn)進程間的數(shù)據傳遞。高級通信：進程間利用通信命令，傳送大量數(shù)據的方式。2消息傳遞系統(tǒng)方式直接通信方式：源進程直接把消息發(fā)送給目標進程。間接通信方式：進程間通過一個共享數(shù)據結構，以消息暫存方式實現(xiàn)通信。線程------1線程的定義：線程是進程中可獨立執(zhí)行的子任務，是系統(tǒng)獨立調度和分派的基本單位。2線程與進程的比較擁有資源：線程幾乎不占資源，進程是資源分配的基本單位。調度：進程不再是調度的基本單位。并發(fā)性：進程、線程之間都可以并發(fā)執(zhí)行。系統(tǒng)開銷：線程開銷小。19、信號量例題------桌上有一空盤，只允許放入一個水果。爸爸專向盤中放蘋果，媽媽專向盤中放桔子，女兒專等吃盤中的蘋果，兒子專等吃盤中的桔子。使用P,V原語實現(xiàn)爸爸、媽媽、兒子和女兒間同步的程序。解：設置三個信號量S表示空盤子，初值為1；So表示裝了桔子的盤子，初值為0；Sa表示裝了蘋果的盤子，初值為0。Father(){while(1){wait(S);放下一個蘋果；signal(Sa)}}處理機調度基本概念------1調度層次：高級調度(作業(yè)調度)：決定外存后備隊列中的那些作業(yè)調入內存。低級調度(進程調度)：決定就緒隊列中那個進程獲得處理機。中級調度：決定把又具備運行條件的掛起進程重新調入內存，掛到就緒隊列中。2調度算法-------1FCFS：按照進入隊列的先后次序分配處理機。性能評價：周轉時間＝完成時間－到達時間帶權周轉時間＝周轉時間/服務時間2短作業(yè)(進程)優(yōu)先：從隊列中選擇一個估計運行時間最短的作業(yè)(進程)做相應處理。3優(yōu)先權調度算法：從隊列中選擇優(yōu)先權最高的作業(yè)(進程)，進行相應處理。優(yōu)先權類型：靜態(tài)優(yōu)先權動態(tài)優(yōu)先權4高響應比優(yōu)先權算法----動態(tài)優(yōu)先權變化與作業(yè)等待時間有關。5時間片輪轉算法：適用于分時系統(tǒng)的可搶占式的調度算法。實時調度系統(tǒng)處理能力：m個周期任務，c表示處理時間，p為周期時間單機多機產生死鎖的原因-----1死鎖的概念---死鎖，指多個進程在運行過程中因爭奪資源而造成的一種僵局，當進程處于這種僵持狀態(tài)時，若無外力作用，它們都將無法再向前推進。2產生死鎖的必要條件互斥條件：一個資源一次只能被一個進程使用。請求和保持條件：保留已有資源，還要請求其他資源。不剝奪條件：資源只能被所有者釋放，不能被搶占。環(huán)路等待條件：死鎖時，必然存在一個環(huán)形的資源請求鏈。3處理死鎖的基本方法預防死鎖：通過設置某些限定條件，破壞導致死鎖的四個必要條件之一。避免死鎖：在資源的動態(tài)分配過程中，用某種方法防止系統(tǒng)進入不安全狀態(tài)。檢測死鎖：通過系統(tǒng)檢測機構，及時檢測出死鎖的發(fā)生，確定與死鎖有關的進程和資源。檢查是否存在循環(huán)等待。解除死鎖：將進程從死鎖狀態(tài)中解脫出來。4預防死鎖----打破互斥條件：由資源的性質決定。打破請求和保持條件：運行前，一次性分配給進程所需的全部資源。簡單，安全，資源浪費。打破環(huán)路等待條件：資源有序分配法系統(tǒng)安全狀態(tài)------1安全狀態(tài)：現(xiàn)有的進程資源占有情況下，各進程按照某種順序仍然可以使每個進程得到其對資源的最大需求，從而都可以順利地完成。銀行家算法------(1)如果Requesti[j]≤Need[i,j],轉(2)，否則出錯。(2)如果Requesti[j]≤Available[j],轉(3)，否則等待。(3)系統(tǒng)進行試分配：Available[j]=Available[j]-Requesti[j];Allocation[i,j]=Allocation[i,j]+Requesti[j];Need[i,j]=Need[i,j]-Requesti[j](4)系統(tǒng)執(zhí)行安全性算法，檢查此次分配后，系統(tǒng)是否安全。若安全，則正式分配，否則恢復原狀態(tài)，讓進程i等待。安全性算法-----(1)work=Available;Finish[i]=false.(2)尋找滿足條件的進程i:Finish[i]=false;Need≤Work,如果找到，轉(3)，否則，轉(4).(3)進程i可順利執(zhí)行完，釋放資源，則Work=Work+Allocationi;Finish[i]=True;轉(2)。(4)若所有進程Finish[i]=true,則系統(tǒng)安全，否則不安全。26、死鎖的檢測-----1資源分配圖的化簡(1)尋找一個即不阻塞又不孤立的進程結點Pi,若無則算法結束。(2)去掉Pi所有分配分和請求邊，使Pi成為一個孤立結點。(3)轉步驟(1)化簡后，若能消去圖中所有邊，即所有進程都成為孤立結點，剛稱該圖是可完全簡化的；反之，稱該圖是不可完全簡化的。2死鎖定理：系統(tǒng)處于死鎖狀態(tài)當且僅當該狀態(tài)的資源分配圖是不可完全簡化的。例題：假設在單處理機上有五個（1，2，3，4，5）進程爭奪運行，其運行時間分別為10，1，2，1，5秒，其優(yōu)先級分別為3，1，5，4，2，這些進程到達次序依次為0，1，2，3，4。試回答：給出這些進程分別使用輪轉法，搶占式SPF和可剝奪優(yōu)先級調度法調度時的運行進度表，其中輪轉法中時間片=2.在上述各算法的調度下每個進程的周轉時間？具有最短平均帶權周轉時間的算法是哪個？例題：化簡如圖所示的資源分配圖，并說明有無進程處于死鎖狀態(tài)？ 例題：假定具有5個進程的進程集合={P0，P1，P2，P3，P4} 系統(tǒng)中有三類資源，其中A類資源有10個，B類資源有5個，C類資源有7個，假定在某時刻有如下狀態(tài)：求出Need，并說明當前系統(tǒng)是否處于安全狀態(tài)，如果是，給出序列，如果不是，說明理由。存在安全序列：P1->P3->P0->P2->P4程序的裝入和鏈接------1從源程序到程序執(zhí)行，通常需要經歷三步：①編譯：由編譯程序將源代碼編譯成若干個目標模塊;②鏈接：由鏈接程序將一組目標模塊以及它們所需的庫函數(shù)鏈接在一起，形成裝入模塊;③裝入：由裝入程序將裝入模塊復制到內存中。通常鏈接和裝入是一體的。2裝入方式絕對裝入方式：裝入模塊中為絕對地址，直接裝入?？芍囟ㄎ谎b入方式（靜態(tài)重定位）：裝入模塊中為相對地址，復制到內存中為絕對地址。動態(tài)運行時裝入方式（動態(tài)重定位）：復制到內存中依然為相對地址。3連續(xù)分配方式-----1單一連續(xù)分配：方法：把內存分為系統(tǒng)區(qū)和用戶區(qū)，系統(tǒng)區(qū)供OS使用，通常放在低址部分;系統(tǒng)區(qū)以外全部內存空間是用戶區(qū)。特點：只能用于單用戶、單任務OS。實例：MS-DOS2固定分區(qū)分配：方法：分區(qū)大小相等或不相等。內存分配管理：分區(qū)按大小排隊，建立一張分區(qū)使用表。由內存分配程序檢索該表，找到符合要求的分區(qū)。特點：存在大的碎片，主存利用率低。3動態(tài)分區(qū)分配方法：位置和大小都不固定，應作業(yè)的要求而設置。數(shù)據結構的兩種形式：空閑分區(qū)表空閑分區(qū)鏈存儲分配算法----首次適應算法：分區(qū)按地址排序循環(huán)首次適應算法：最佳適應算法：分區(qū)按容量排序特點：產生小的碎片。4可重定位分區(qū)分配利用拼接技術，對程序進行動態(tài)重定位，更好的利用內存小的碎片。實現(xiàn)方法：由重定位寄存器實現(xiàn)，存放程序的起始地址?；痉猪摯鎯芾矸绞?頁表：頁表存放在內存系統(tǒng)區(qū)的一個連續(xù)空間中，記錄了每個頁面對應的物理塊號。2地址變換機構邏輯地址：給定一個邏輯地址A，已知頁面大小為L，則其對應的頁號和頁內偏移為：頁號P=INT[A/L]頁內地址d=AMODL物理地址：地址變換過程：當進程要訪問某個邏輯地址時，由分頁地址變換機構轉換成頁號和頁內地址;通過頁號查找頁表，如合法，則找到相應的物理塊號;將塊號加上頁內偏移(塊內偏移)，即是物理地址。例題：在一個頁式存儲管理系統(tǒng)中，頁表內容如右表所示：若頁的大小為4K,試求邏輯地址0轉換成的物理地址。解：轉換成的物理地址為8192。 基本分段存儲管理方式1基本原理：作業(yè)邏輯地址空間按意義分段，每個段存放在一個連續(xù)的內存分區(qū)中。整個作業(yè)的邏輯地址為二維的，由段號＋段內地址組成。2段表：記錄了邏輯段與內存位置的對應關系，包括段號、段基地址、段長等。3地址變換機構：利用段表實現(xiàn)地址映射。例某段表的內容如下：段號段首址段長度0120K40K1760K30K2480K20K3370K20K一邏輯地址為（2，154），它對應的物理地址為（）4分段與分頁的區(qū)別：頁是信息的物理單位，段是信息的邏輯單位;頁的大小固定，段的大小動態(tài)變化;分頁系統(tǒng)中邏輯地址是一維的，分段系統(tǒng)中是二維的;分頁系統(tǒng)中不易實現(xiàn)共享和動態(tài)鏈接，分段則容易實現(xiàn)。段頁式存儲管理方式1基本原理：分段和分頁的結合;對內存進行分頁，對用戶作業(yè)進行分段，對各段再進行分頁。2地址結構----由三部分組成：段號＋段內頁號＋頁內地址。3地址變換：利用段表和頁表實現(xiàn)地址映射。優(yōu)點：同時具備分段和分頁管理的優(yōu)點：分散存儲，內存利用率高；便于代碼或數(shù)據共享；支持動態(tài)鏈接等。缺點：訪問效率下降，一次數(shù)據訪問需要三次訪問內存。虛擬存儲器1局部性原理---時間局部性：指令的重復執(zhí)行－循環(huán)；空間局部性：順序訪問相鄰的存儲單元－順序執(zhí)行、數(shù)據訪問。2虛擬存儲器定義：指具有請求調入功能和置換功能，能從邏輯上對內存容量加以擴充的一種存儲器系統(tǒng)。3實現(xiàn)方法：必須建立在離散分配的內存管理技術基礎上。分頁請求系統(tǒng)：基本分頁系統(tǒng)＋請求分頁功能＋頁面置換功能分段請求系統(tǒng)：基本分段系統(tǒng)＋請求分段功能＋分段置換功能4特征：多次性：一個作業(yè)被分成多次調入內存運行對換性：允許在作業(yè)的運行過程中進行換入、換出虛擬性：能從邏輯上擴充內存容量。虛擬性以多次性和對換性為基礎。請求分頁管理方式１物理塊的分配策略-----固定分配局部置換：進程占據的內存塊數(shù)不變，但很難確定進程所需塊數(shù)。可變分配全局置換：空閑塊由OS管理?？勺兎峙渚植恐脫Q：當進程缺頁率較高或較低時，由OS對其分配的物理塊加以調整。頁面置換算法-----1最佳置換算法：選擇以后永遠不用或最長時間不用的頁淘汰出去。特點：理論上性能最佳，實際上無法實現(xiàn)。常用作研究其它算法的參考評價。2先進先出算法：選擇最先進入系統(tǒng)的頁淘汰出去。特點：簡單，與實際進程運行不相適應。存在一種Belady現(xiàn)象。3最近最久未使用LRU算法：選擇最近最久未被訪問的頁淘汰出去。特點：性能好，實現(xiàn)復雜。需要硬件支持，每頁配置一個移位寄存器、或棧，增加系統(tǒng)開銷。例題：假設某程序的頁面訪問序列為1、2、3、4、5、2、3、1、2、3、4、5且開始執(zhí)行時主存沒有頁面，則在分配給該程序的物理塊數(shù)是3且采用FIFO方式時缺頁次數(shù)（）；在分配給程序的物理塊數(shù)是4且采用FIFO方式時，缺頁次數(shù)是（）；在分配給程序的物理塊數(shù)是3且采用LRU方時，缺頁次數(shù)是（）。在分配給程序的物理塊數(shù)是4且采用LRU方式時，缺頁次數(shù)是（）。I/O系統(tǒng)1I/O設備類型按傳輸速率分：低速、中速、高速按信息交換單位分：塊、字符設備按共享屬性分：獨占、共享、虛擬設備2設備與控制器之間的接口：數(shù)據、控制、狀態(tài)信號線3通道的類型----字節(jié)多路通道：多路分時復用數(shù)組選擇通道：獨占使用，成組傳送數(shù)組多路通道：上兩種技術的結合解決單通道的瓶頸問題：增加設備到主機間的通路。I/O控制方式程序I/O方式：忙－等待中斷驅動方式：設備與CPU并行工作，以字節(jié)為單位交換數(shù)據。DMA控制方式：以塊為單位傳送數(shù)據通道控制方式：以多個塊為單位傳送數(shù)據緩沖管理----1引入緩沖的原因：緩和CPU和I/O速度不匹配的矛盾，減少對CPU的中斷頻率，放寬對CPU中斷響應時間的限制，提高CPU與I/O設備之間的并行性2緩沖技術的發(fā)展單緩沖雙緩沖循環(huán)緩沖緩沖池：把專用循環(huán)緩沖變?yōu)楣镁彌_區(qū)，以提高內存利用率設備分配-----1設備獨立性：應用程序獨立于具體使用的物理設備。易于實現(xiàn)I/O重定向：更換I/O操作的設備而不修改程序。2SPOOLING技術;將一臺物理I/O設備虛擬為多臺邏輯設備，從而允許多個用戶共享使用一臺物理設備。即利用高速的共享設備(磁盤)實現(xiàn)低速獨占設備的共享技術。又稱為：假脫機操作。3組成：三個部分---輸入井和輸出井、輸入進程和輸出進程、輸入緩沖區(qū)和輸出緩沖區(qū)38磁盤存儲管理 1磁盤訪問時間：尋道時間旋轉延遲時間傳輸時間2磁盤調度-----先來先服務FCFS：根據進程請求訪問磁盤的先后次序進行調度。優(yōu)點：公平、簡單缺點：沒有對尋道做優(yōu)化，平均尋道時間可能較長。最短尋道時間優(yōu)先SSTF：選擇要求訪問的磁道與當前磁頭所在的磁道距離最近的進程請求，使每次的尋道時間最短。特點：不能保證平均尋道時間最短，可能導致“饑餓”現(xiàn)象。掃描算法：磁頭每次做單向移動，直到達邊緣為止，再做反向移動。待訪問的磁道只能在此次移動的前方，且距離最近的請求。、又稱為“電梯調度算法”。特點：消除了饑餓現(xiàn)象。循環(huán)掃描算法：規(guī)定磁頭只做單方向移動，不再反向移動掃描。特點：改進了對于邊緣區(qū)磁道訪問的不公平。文件和文件系統(tǒng)-----1文件類型有結構文件：記錄為單位，定長記錄、變長記錄無結構文件：大量的源程序、可執(zhí)行文件、庫函數(shù)等，以字節(jié)為基本訪問單位。2文件的邏輯結構類型：順序文件索引文件索引順序文件直接文件和哈希文件順序文件：適用于批量存取、能適用于磁帶存儲。單個或少量數(shù)據查找效率低。索引文件：利用定長記錄的順序文件訪問變長記錄文件。索引表本身是一個定長記錄的順序文件，記錄鍵值、長度、指針。索引順序文件：順序文件和索引文件的結合，最常見的一種邏輯文件形式。主順序文件的所有記錄分組；索引文件只記錄每個分組的第一個記錄指針。直接文件和哈希文件：直接文件：記錄鍵值記錄物理地址哈希文件：利用哈希函數(shù)實現(xiàn)地址轉換。3外存分配方式類型：連續(xù)分配鏈接分配索引分配連續(xù)分配：為每一個文件分配一組相鄰接的盤塊，物理上形成順序文件結構。外存上