2023/2/3第3章存儲器管理考試大綱要求（一）

內存管理基礎

1.

內存管理概念

程序裝入與鏈接；邏輯地址與物理地址空間；內存保護。

2.

交換與覆蓋

3.

連續分配管理方式

4.

非連續分配管理方式

分頁管理方式；分段管理方式；段頁式管理方式。

退出2023/2/3存儲器的層次結構多級存儲器結構一般計算機，存儲層次至少應具有三級：最高層為CPU寄存器，中間為主存，最底層是輔存。較高檔計算機中，根據具體功能分為6層，如圖寄存器高速緩存主存磁盤緩存磁盤可移動存儲介質2023/2/3程序的裝入程序的裝入就是把程序裝入內存空間。采用三種方式（1）絕對裝入方式：是由裝入程序根據裝入模塊中的地址，將程序和數據裝入內存。（2）可重定位方式：是由裝入程序根據內存當前的實際使用情況，將裝入模塊裝入到內存適當的地方。（3）動態運行時裝入方式：動態運行時的裝入程序，在把裝入模塊裝入內存后，并不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這種地址轉換推遲到程序要真正執行時才進行。2023/2/3程序的裝入絕對裝入方式：是由裝入程序根據裝入模塊中的地址，將程序和數據裝入主存若知道程序在內存的位置，編譯程序將產生絕對地址目標模塊絕對地址一般由編譯程序給出程序被裝入內存后，由于程序中的邏輯地址與實際內存地址完全相同，所以不允許改變程序和數據的地址只適于單道環境2023/2/3程序的裝入可重定位方式：是由裝入程序根據主存當前的實際使用情況，將裝入模塊裝入到主存適當的地方。

重定位：在裝入時對目標程序中指令和數據的修改過程。會使裝入模塊中的所有邏輯地址與實際裝入內存的物理地址不同2023/2/3程序的裝入靜態重定位方式：是指地址轉換工作是在程序裝入內存時由裝配程序完成的。裝配程序根據將要裝入內存的起始地址，對程序模塊中有關的地址部分進行調整和修改（物理地址=邏輯地址+程序存放在內存的起始地址），一旦確定下來之后不再改變，即靜態地址重定位是在程序執行之前完成的地址轉換。它的優點：無需硬件支持，容易實現。缺點：程序經地址重定位后不能再移動，程序在內存空間只能連續存儲，程序很難被若干個用戶所共享。2023/2/3程序的裝入動態運行時裝入方式：動態運行時的裝入程序，在把裝入模塊裝入內存后，并不立即把裝入模塊中的相對地址轉換為絕對地址，而是把這種地址轉換推遲到程序要真正執行時才進行。適于多道環境允許程序移動，如切換動態重定位需要特殊硬件支持（重定位寄存器）2023/2/3程序的裝入動態重定位：是指地址轉換工作是在程序執行期間由硬件變換機構動態實現地址轉換的。物理地址=邏輯地址+重定位寄存器的內容。動態重定位的優點：用戶程序在執行過程中內存可移動，程序不必連續存放在內存中，可以放在不同區域，若干個用戶可以共享同一程序段或數據段。缺點：需要附加硬件支持，實行存儲管理的軟件算法比較復雜。2023/2/3程序的鏈接鏈接程序的功能是將經過編譯或匯編后所得到的一組目標模塊以及它們所需要的庫函數，裝配成一個完整的裝入模塊。實現鏈接的方法有三種靜態鏈接：事先進行鏈接，以后不再拆開的鏈接方式裝入時動態鏈接：用戶源程序經編譯后所得到的目標模塊，是在裝入內存時，邊裝入邊鏈接的。運行時動態鏈接：某些目標模塊的鏈接，是在程序執行中需要該（目標）模塊時，才對它進行鏈接2023/2/3內存保護

內存保護就是防止各用戶程序運行時相互被破壞,最重要的就是不能破壞操作系統.

（1）界地址寄存器保護法 （2）訪問授權保護2023/2/32.交換與覆蓋

采用交換與覆蓋技術是為了節省內存。交換就是系統根據需要把主存中暫時不運行的某個（或某些）進程的部分或全部信息移到外存，而把外存中的某個（或某些）進程移到相應的主存區，并使其投入運行覆蓋就是指一個作業（或進程）或多個作業（或進程）的若干程序段或數據段共享主存的某個區域。實現方法是將一個作業（或進程）劃分成若干個相互獨立的段，將不同時運行的程序段或數據段組成覆蓋。2023/2/33.連續分配方式連續分配方式：為一個用戶程序分配一個連續的內存空間單一連續分配固定分區分配動態分區分配動態重定位分區分配2023/2/3連續分配方式單一連續分配2023/2/3連續分配方式固定分區分配將內存中的用戶空間劃分為若干個固定大小的區域每個分區中只裝入一道作業，一個作業也只能裝入一個分區中，這樣可以裝入多個作業，使它們并發執行。當有一個空閑分區時，便可從外存的后備隊列中，選擇一個適當大小的作業裝入該分區；當該作業運行完時，又可從后備隊列中選擇另一個作業裝入該分區（分區大小可以相同也可以不同）。

2023/2/3固定分區分配的管理特點（1）一個作業只能裝入一個分區，不能裝入兩個或多個相鄰的分區。一個分區只能裝入一個作業，當分區大小不能滿足作業的要求時，該作業暫時不能裝入。（2）通過對“分區使用表”的改寫，來實現主存的分配與回收。作業在執行時，不會改變存儲區域，所以采用靜態地址重定位方式。此方法易于實現，系統開銷小。（3）當分區較大作業較小時，仍然浪費許多主存空間(內零頭）。并且分區總數固定，限制了并發執行的作業數目。

2023/2/3動態分區分配

動態分區存儲管理的基本思想是：在作業要求裝入內存儲器時，如果當時內存儲器中有足夠的存儲空間滿足該作業的需求，那么就劃分出一個與作業相對地址空間同樣大小的分區分配給它。2023/2/3采用的數據結構為了實現分區分配，系統中必須配置相應的數據結構，用來記錄內存的使用情況。比如空閑分區的情況，為作業分配內存空間提供依據。常用的有空閑分區表和空閑分區鏈。2023/2/3分區分配算法（1）首次適應分配算法（FF）（2）循環首次適應分配算法（NF）（2）最佳適應分配算法（BF）（3）最壞適應分配算法（WF）2023/2/3(1)首次適應法要求空閑區按首址遞增的次序組織空閑區表（隊列）。

分配：當進程申請大小為SIZE的內存時，系統從空閑區鏈的鏈首開始查詢，直到首次找到等于或大于SIZE的空閑區。從該區中劃出大小為SIZE的分區分配給進程，余下的部分仍作為一個空閑區留在空閑區鏈中，但要修改其首址和大小。若找不到滿足要求的，則分配失敗，返回。2023/2/3分析注意：每次分配和回收后空閑區鏈都要按首址遞增的次序排序。優點：這種算法是盡可能地利用低地址空間，從而保證高地址空間有較大的空閑區。

缺點容易產生過多的小地址碎片；降低了主存空間利用率。每次查找都是從低址開始，增加了查找的開銷改進采用循環首次適應算法。2023/2/3（2）循環首次適應算法

不是每次都從鏈首開始找，而是從上次找到的空閑分區的下一個空閑分區開始查找，直到找到一個能滿足要求的空閑分區。設置查尋指針；循環查找方式使內存中的空閑分區分布得更均勻，減少了查找時的開銷，但會缺乏大的空閑分區。2023/2/3（3）最佳適應法所謂最佳就是每次為作業分配內存時，總是把能滿足要求、又是最小的空閑分區分配給作業，避免大材小用。要求按空閑區大小從小到大的次序組成空閑區鏈。2023/2/3最佳適應法優點：在系統中若存在一個與申請分區大小相等的空閑區，必定會被選中，而首次適應法則不一定。若系統中不存在與申請分區大小相等的空閑區，則選中的空閑區是滿足要求的最小空閑區，而不致于毀掉較大的空閑區。缺點：空閑區的大小一般與申請分區大小不相等，因此將其一分為二，留下來的空閑區一般情況下是很小的，以致無法使用。隨著時間的推移，系統中的小空閑區會越來越多，從而造成存儲區的大量浪費。2023/2/3（4）最壞適應算法掃描整個空閑分區表，或鏈表，總是挑選一個最大的空閑區分割給作業使用。要求按空閑區大小從大到小的次序組成空閑區鏈。優點：可使剩下的空閑區不至于太小，產生碎片的幾率最小，對中、小作業有利。缺點：缺乏大的空閑分區，不利于大作業。2023/2/3可重定位分區分配

在連續分配中，必須把一個系統或用戶程序裝入一連續的內存空間。不能被利用的小分區稱為“零頭”或“碎片”。將主存中的所有作業進行移動，使它們相鄰接。這樣，原來分散的多個小分區便拼接成一個大分區，從而就可以把作業裝入該區。這種通過移動，把多個分散的小分區拼接成大分區的方法被稱為“拼接”或“緊湊”，改變作業在主存中位置的工作稱為“移動”。2023/2/3連續分配方式比較作業個數內部碎片外部碎片解決碎片方法相同點提高作業道數單一連續分配1有無無一個程序需全部、連續裝入內存中。對換固定分區分配N（分區數）有無無動態分區分配不定無有緊湊2023/2/3非連續分配方式分頁管理方式分段管理方式段頁式管理方式2023/2/34.4.1頁面與頁表

作業地址空間劃分成連續的大小相同的頁面內存劃分成連續的大小相等的塊（也稱為頁框）頁面的大小與內存塊的大小完全相同作業進入內存時其不同的頁面對應于內存中不同的塊，連續頁面可以對應不連續的塊。2023/2/3（1）分頁管理方式頁面（用戶程序劃分）

把用戶程序按邏輯頁劃分成大小相等的部分，稱為頁（page）

。從0開始編制頁號，頁內地址是相對于0編址2023/2/3內存空間

按頁的大小劃分為大小相等的區域，稱為塊或內存塊（物理頁面，頁框）

在為進程分配內存時，以塊為單位將進程中的若干個頁分別裝入到多個可以不相鄰接的物理塊中。由于進程的最后一頁經常不滿一塊而形成了不可利用的碎片稱之為“頁內碎片”邏輯上相鄰的頁，物理上不一定相鄰2023/2/3地址結構

用戶程序的劃分是由系統自動完成的，對用戶是透明的。一般，一頁的大小為2的整數次冪，因此，地址的高位部分為頁號，低位部分為頁內地址頁號頁內地址0111231頁號P頁內位移量W編號0~1048575相對地址0~40952023/2/3

頁表將頁號和頁內地址轉換成內存地址，必須要有一個數據結構，用來登記頁號和塊的對應關系和有關信息。這樣的數據結構稱為頁表。頁表的作用就是實現從頁號到物理塊號的地址映射。2023/2/3頁表內容頁表包含以下幾個表項：頁號：登記程序地址空間的頁號。塊號：登記相應的頁所對應的內存塊號其它：登記與存儲信息保護有關的信息。頁號塊號其它05…165…213…2023/2/3地址變換機構地址變換機構的任務是實現從邏輯地址到物理地址的轉換。即把程序地址轉換成內存地址，這個轉換過程是在程序執行過程中完成的，是動態地址映射。在現代計算機系統中，由系統提供的地址映射硬件來完成地址映射工作。2023/2/3例設頁長為1K，程序地址字長為16位，用戶程序空間和頁表如圖。

2023/2/3計算時要注意：若給出的地址字為16進制，則將其轉換為二進制，然后，根據頁長及程序地址字的長度，分別取出程序地址字的高幾位和低幾位就得到頁號及頁內地址。如頁長為2K，程序地址字為16位，則高5位為頁號，低11位為頁內地址。2023/2/3若給出的地址字為10進制，則用公式： 程序地址字/頁長商為頁號，余數為頁內地址。如程序地址為8457，

頁長為4KB，則8457/4096可得：商為2，余數為256。2023/2/3快表和聯想存儲器在前述的頁地址變換過程中有一個嚴重的問題，那就是每一次對內存的訪問都要訪問頁表，頁表是放在內存中的，也就是說每一次訪問內存的指令至少要訪問兩次內存，運行速度要下降一半。第一次訪問內存中的頁表，從中找到指定頁的物理塊號，再將塊號與頁內偏移量W拼接，形成物理地址第二次訪問內存時，才是從第一次所得地址中獲得所需數據（獲向此地址中寫入數據）2023/2/3解決這個問題的一種方法是把頁表放在一組快速存儲器中（Cache），從而加快訪問內存的速度。我們把這種快速存儲器組成的頁表稱為快表，把存放在內存中的頁表稱為慢表。快表又叫聯想存儲器（associativememory）或TLB（Translationlookasidebuffers）用以存放當前訪問的那些頁表項2023/2/3p’頁表地址越界

L比較P>=Lpp’...快表

b+頁號p

頁內地址dP’d物理地址頁表地址寄存器頁表長度寄存器邏輯地址地址映射機制2023/2/3兩級頁表和多級頁表當頁表項很多時，僅采用一級頁表需要大片連續空間，可將頁表也分頁，并對頁表所占的空間進行索引形成外層頁表。由此構成二級頁表。更進一步可形成多級頁表。

2023/2/3二級頁表結構及地址映射2023/2/3頁式存儲管理方案小結優點：解決了碎片問題便于管理

可以使程序和數據存放在不連續的主存空間缺點：不易實現共享不便于動態連接 頁表都有可能占用較大的存儲空間。 要求有相應的硬件支持，從而增加了系統成本，也增加了系統開銷2023/2/3（2）分段管理方式引入段式管理方式主要是為了滿足用戶和程序員的需要方便用戶：用戶希望邏輯分段信息共享信息保護動態增長動態連接2023/2/3分段系統基本原理分段用戶程序劃分按程序自身的邏輯關系劃分為若干個程序段，每個程序段都有一個段名，且有一個段號。段號從0開始，每一段段內也從0開始編址，段內地址是連續的。段的長度由相應的邏輯信息組的長度決定，因而各段長度不等。邏輯地址：由段號和段內地址組成段號段內地址2023/2/3內存劃分內存空間被動態的劃分為若干個長度不相同的區域，稱為物理段，每個物理段由起始地址和長度確定內存分配

以段為單位分配內存，每一個段在內存中占據連續空間（內存隨機分割，需要多少分配多少），但各段之間可以不連續存放2023/2/3段表段映射表。每個程序有一個段表程序的每個段在表中占有一個表項，其中記錄了該段在內存中的起始地址和段的長度。可放在內存中，也可放在寄存器中。段表是用于實現從邏輯段到物理內存區的映射。

段號012段首址段長度58K20K100K110K260K140K2023/2/33、地址變換機構段地址映射過程為：系統中設置了段表寄存器，用于存放段表始址和段表長度TL。取出段號S和段內位移W。若S>TL，段號太大—越界。根據段表始址找到段表，查找段號為S的表目，得到該段在內存的起始地址。檢查段內地址d是否起過該段的段長SL。若超過越界。把段首地址與段內位移相加，形成內存物理地址。2023/2/3地址變換機構2023/2/3同頁地址變換一樣，在段地址變換過程中，也有兩次訪問內存的問題。為了加快訪問內存的速度也可采用快速存儲器組成快表。2023/2/3

Cl

Cb+段號S段內地址d比較比較b

+d段表S>=Cl快表物理地址段表始址寄存器段表長度寄存器邏輯地址Lb...SLb地址越界d>=Ld>=L地址映射及存儲保護機制地址越界地址越界比較2023/2/3段式存儲管理方案小結優點：便于動態申請內存管理和使用統一化便于共享便于動態鏈接缺點：產生外部碎片2023/2/3（3）段頁式存儲管理方式產生背景:結合頁式段式優點，克服二者的缺點基本原理地址變換過程2023/2/3基本原理用戶程序劃分 按段式劃分（對用戶來講，按段的邏輯關系進行劃分；對系統講，按頁劃分每一段）邏輯地址內存劃分 按頁式存儲管理方案內存分配 以頁為單位進行分配段號段內地址頁號頁內地址2023/2/3段表：記錄了每一段的頁表始址和頁表長度頁表：記錄了邏輯頁號與內存塊號的對應關系（每一段有一個，一個程序可能有多個頁表）內存分配管理：同頁式管理地址變換過程2023/2/3圖4-21利用段表和頁表實現地址映射

2023/2/3地址變換過程圖4-22段頁式系統中的地址變換機構2023/2/3在段頁式系統中，為了獲得一條指令數據，須三次訪問內存。1、訪問內存中的段表，從中取得頁表始址2、訪問內存中的頁表，從中取出該頁所在的物理塊號，將該塊號與頁內地址一起形成指令或數據的物理地址3、從物理地址中取出指令或數據。快表地址變換過程2023/2/3總結固定分區的分配方式會產生內零頭，因為是找出一個滿足作業要求的空閑分區分配給作業，大小不一定剛好合適，分區中有一部分存儲空間會被浪費。在可變式分區分配中，是按照作業的大小找出一個分區來分配如果大于作業申請的空間，則一分為二，剩下的一分部作為系統的空閑分區，有可能很小無法利用而成為外零頭。2023/2/3總結為了解決外零頭的問題，提出了離散的分配方式，在分頁式存儲管理中，存儲空間被分面與頁大小相等的物理塊，作業的大小不可能都是物理塊的整數倍，因此在作業的最后一頁中有可能有部分空間未被利用，屬于內零頭。分段式存儲管理中，其內存分配方式類似于動態分區的分配，因此會產生外零頭。段頁式存儲管理中，其內存分配方式類似于頁式的分配，因此會產生內零頭。2023/2/3（二）

虛擬內存管理考試大綱要求1.

虛擬內存基本概念

2.

請求分頁管理方式

3.

頁面置換算法

最佳置換算法（OPT）；先進先出置換算法（FIFO）；最近最少使用置換算法（LRU）；時鐘置換算法（CLOCK）。

4.

頁面分配策略

5.

抖動

抖動現象；工作集。

2023/2/31虛擬內存基本概念程序局部性原理時間局部性一條指令被執行了，則在不久的將來它可能再被執行，如果某數據被訪問過，則不久以后該數據可能再次被訪問。（循環操作）空間局部性若某一存儲單元被使用，則在一定時間內，與該存儲單元相鄰的單元可能被使用，即程序在一段時間內所訪問的地址，可能集中在一定的范圍之內。（程序順序執行）2023/2/3虛擬存儲器的定義虛擬存儲器是指僅把作業的一部分裝入內存便可運行作業的存儲器系統。具體地說，所謂虛擬存儲器是指具有請求調入功能和置換功能，能從邏輯上對主存容量進行擴充的一種存儲器系統。實際上，用戶所看到的大容量只是一種感覺，是虛的，故而得名虛擬存儲器。2023/2/32.請求分頁式存儲管理它是建立在純分頁基礎上的，增加了請求調頁功能、頁面置換功能所形成的請求分頁存儲管理系統。把作業分成大小相等的若干頁，把主存分成與頁大小相等的若干塊；對每個作業限定分給它的主存塊數，先把作業的部分頁裝入主存的這些塊中，在作業運行時再裝入所需要的頁。2023/2/3采用的數據結構（1）頁表頁表用來記錄作業的分配情況。（2）缺頁中斷機構在請求分頁系統中，每當所要訪問的頁面不在主存時，便要產生一次缺頁中斷，請求操作將所缺的頁調入主存。（3）地址變換機構2023/2/3頁表表項頁號、內存塊號、狀態位、訪問位、修改位、外存地址 狀態位P：表示該頁是否已調入內存，供程序訪問時參考訪問位A：用于記錄本頁在一段時間內被訪問的次數或最近已有多長時間未被訪問，供選擇換出頁面時參考頁號內存塊號狀態位P訪問位A修改位M外存地址2023/2/3頁表表項頁號、內存塊號、駐留位、外存地址、訪問位、修改位 修改位：查看此頁是否在內存中被修改過，供置換頁面時參考。外存地址：該頁存放在外存上的地址。供調入該頁時參考。頁號內存塊號狀態位P訪問位A修改位M外存地址2023/2/3缺頁中斷（PageFault）機構缺頁中斷機構在請求分頁系統中，每當所要訪問的頁面不在主存時，便要產生一次缺頁中斷，請求操作將所缺的頁調入主存。缺頁中斷作為中斷，它同樣需要經歷諸如保護CPU環境、分析中斷原因、轉入缺頁中斷處理程序進行處理、恢復CPU環境等幾個步驟。

2023/2/3缺頁中斷同一般中斷的區別？缺頁中斷同一般中斷都是中斷，相同點是：保護現場中斷處理恢復現場不同點：在指令執行期間產生和處理中斷信號。一般中斷是一條指令完成后中斷，缺頁中斷是一條指令執行時，發現所要訪問的指令或數據不在內存時所產生的中斷一條指令執行時可能產生多個缺頁中斷。如指令可能訪問多個內存地址，這些地址在不同的頁中。2023/2/3下圖用數字標出了缺頁中斷的處理過程：根據當前執行指令中的虛擬地址，形成數對：（頁號，頁內位移）。用頁號去查頁表，判斷該頁是否在內存儲器中若該頁的R位（缺頁中斷位）為“0”，表示當前該頁不在內存，于是產生缺頁中斷，讓操作系統的中斷處理程序進行中斷處理。中斷處理程序去查存儲分塊表，尋找一個空閑的內存塊；查頁表，得到該頁在輔助存儲器上的位置，并啟動磁盤讀信息。把從磁盤上讀出的信息裝入到分配的內存塊中。根據分配存儲塊的信息，修改頁表中相應的表目內容，即將表目中的R位設置成為“1”，表示該頁已在內存中，在B位填入所分配的塊號。另外，還要修改存儲分塊表里相應表目的狀態。由于產生缺頁中斷的那條指令并沒有執行，所以在完成所需頁面的裝入工作后，應該返回原指令重新執行。這時再執行時，由于所需頁面已在內存，因此可以順利執行下去。2023/2/3頁面調入策略（1）何時調入（2）何處調入

（3）頁面調入過程2023/2/3何時調入（1）預調入采用一種以預測為基礎的調入策略，將預計不久要使用的頁調入主存。缺點：預計不準場合：進程的首次調入（2）請求調入當發生缺頁時，提出請求，由系統調入優點：命中率100%，實現簡單缺點：開銷大，每次只調入一頁場合：大多數2023/2/3何處調入磁盤分對換區和文件區，有不同。（1）磁盤有足夠的對換區時，全部從對換區調入頁面。運行前拷入對換區（2）磁盤無足夠的對換區時，修改過的部分從對換區調入頁面，沒修改的部分從文件區調入。（3）UNIX方式：運行過的頁面從對換區調入，未運行的頁面從文件區調入2023/2/3頁面調入過程保護現場轉中斷處理程序查頁表，找到頁的外存地址內存未滿則調入，修改頁表內存已滿，則先置換。被置換的頁若被修改過，則寫入磁盤。將缺頁調入內存，修改頁表和快表再訪內存2023/2/33.頁面置換算法（1）最佳置換算法（OPT）（2）先進先出置換算法（FIFO）（3）最近最久未使用算法（LRU）（4）Clock置換算法2023/2/3最佳置換算法理想淘汰算法—最佳頁面算法（OPT）選擇以后永不使用的，或許是在最長(未來)時間內不再被訪問的頁面淘汰。采用最佳置換算法，通常可保證獲得最低的缺頁率。2023/2/3最佳置換算法假定系統為某進程分配了三個物理塊，并考慮有以下的頁面號引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

進程運行時，先將7，0，1三個頁面裝入內存。以后，當進程要訪問頁面2時，將會產生缺頁中斷。此時OS根據最佳置換算法，將選擇頁面7予以淘汰。

2023/2/3先進先出頁面置換算法先進先出（FIFO）是人們最容易想到的頁面淘汰算法。其做法是當要進行頁面淘汰時，總是把最早進入內存的頁面作為淘汰的對象。2023/2/3最近最久未用（LRU）置換算法的著眼點是在要進行頁面置換時，檢查這些頁面的被訪問時間，總是把最長時間未被訪問過的頁面置換出去。這是一種基于程序局部性原理的置換算法。也就是說，該算法認為如果一個頁面剛被訪問過，那么不久的將來被訪問的可能性就大；否則被訪問的可能性就小。最近最久未使用（LRU）置換算法2023/2/31.LRU(LeastRecentlyUsed)置換算法的描述

4.7.2最近最久未使用（LRU）置換算法2023/2/34.7.3Clock置換算法

1.簡單的Clock置換算法圖4-30簡單Clock置換算法的流程和示例2023/2/32023/2/32.改進型Clock置換算法由訪問位A和修改位M可以組合成下面四種類型的頁面：

1類(A=0,M=0):

表示該頁最近既未被訪問，又未被修改，是最佳淘汰頁。

2類(A=0,M=1)：表示該頁最近未被訪問，但已被修改，并不是很好的淘汰頁。

3類(A=1,M=0)：最近已被訪問，但未被修改，該頁有可能再被訪問。

4類(A=1,M=1):

最近已被訪問且被修改，該頁可能再被訪問。2023/2/3其執行過程可分成以下三步：

(1)從指針所指示的當前位置開始，掃描循環隊列，尋找A=0且M=0的第一類頁面，將所遇到的第一個頁面作為所選中的淘汰頁。在第一次掃描期間不改變訪問位A。

(2)如果第一步失敗，即查找一周后未遇到第一類頁面，則開始第二輪掃描，尋找A=0且M=1的第二類頁面，將所遇到的第一個這類頁面作為淘汰頁。在第二輪掃描期間，將所有掃描過的頁面的訪問位都置0。

(3)如果第二步也失敗，亦即未找到第二類頁面，則將指針返回到開始的位置，并將所有的訪問位復0。然后重復第一步，如果仍失敗，必要時再重復第二步，此時就一定能找到被淘汰的頁。2023/2/34、頁面分配策略內存分配策略：固定和可變置換策略：全局和局部組合成3種合適的策略：固定分配局部置換可變分配全局置換可變分配局部置換2023/2/35.工作集由于程序的局部性原理，進程在一段時間內集中訪問一些固定頁面的子集稱為該進程的工作集。為了減少進程訪問中的缺頁次數，為每個進程分配一定數量的頁框作為工作集使用。2023/2/35.抖動采用某個淘汰算法淘汰一頁時，如果算法選擇不當，就會出現這樣的現象：剛被淘汰的頁面馬上又要用，因而要把它調入。調入不久再被淘汰，淘汰不久再次裝入。如此反復，使整個系統處于頻繁地調入調出狀態，大降低系統的處理效率，這種現象叫抖動。如果分配給進程的物理塊號數與當前工作集大小一致，可以有效避免抖動現象。在實際中，可以通過調整淘汰算法，或者根據缺頁率的大小動態的分配給進程物理頁塊，都可以防止抖動的發生。2023/2/3第4章文件管理（一）

文件系統基礎

1.

文件概念

2.

文件邏輯結構

順序文件；索引文件；索引順序文件。

3.

目錄結構

文件控制塊和索引節點；單級目錄結構和兩級目錄結構；樹形目錄結構；圖形目錄結構。

4.

文件共享

5.

文件保護

訪問類型；訪問控制。

2023/2/31文件概念文件是指具有文件名的若干相關元素的集合。元素通常是記錄。記錄是一組有意義的數據項集合。文件類型

2023/2/3文件操作用戶通過文件系統所提供的系統調用實施對文件的操作。1、最基本的文件操作有：創建、刪除、讀、寫、截斷文件和設置文件的讀、寫位置2023/2/3文件操作2、文件的“打開”和“關閉”操作所謂“打開”，是指系統將指名文件的屬性(包括該文件在外存上的物理位置)從外存拷貝到內存打開文件表的一個表目中，并將該表目的編號(或稱為索引)返回給用戶。以后，當用戶再要求對該文件進行相應的操作時，便可利用系統所返回的索引號向系統提出操作請求。系統這時便可直接利用該索引號到打開文件表中去查找，從而避免了對該文件的再次檢索。這樣不僅節省了大量的檢索開銷，也顯著地提高了對文件的操作速度。如果用戶已不再需要對該文件實施相應的操作時，可利用“關閉”(close)系統調用來關閉此文件，OS將會把該文件從打開文件表中的表目上刪除掉。

2023/2/32文件邏輯結構對于任何一個文件，都存在著兩種形式的結構

文件的邏輯結構

文件的物理結構

對邏輯結構的基本要求提高檢索速度便于修改降低文件的存儲費用2023/2/3文件邏輯結構的類型1、有結構文件由一個以上的記錄構成的文件。記錄式文件：每個記錄都用于描述實體集中的一個實體，各記錄有著相同或不同數目的數據項。記錄的長度可分為定長和不定長兩類2023/2/3定長記錄：文件中所有記錄的長度相等。文件長度用記錄數目表示。處理方便，開銷小。變長記錄：文件中的記錄長度不相等。組織形式順序文件索引文件索引順序文件2023/2/32、無結構文件由字符流構成的文件如果說大量的數據結構和數據庫，是采用有結構的文件形式的話，則大量的源程序、可執行文件、庫函數等，所采用的就是無結構的文件形式，即流式文件。長度以字節為單位。

2023/2/3（1）順序文件對順序文件(SequentialFile)的讀/寫操作圖6-3定長和變長記錄文件2023/2/3（1）順序文件順序文件的優缺點順序文件的最佳應用場合，是在對諸記錄進行批量存取時，即每次要讀或寫一大批記錄。此時，對順序文件的存取效率是所有邏輯文件中最高的。在交互應用的場合，如果用戶(程序)要求查找或修改單個記錄，為此系統便要去逐個地查找諸記錄。如果想增加或刪除一個記錄，都比較困難。

2023/2/3（2）索引文件為了解決這一問題，可為變長記錄文件建立一張索引表，對主文件中的每個記錄，在索引表中設有一個相應的表項，用于記錄該記錄的長度L及指向該記錄的指針。由于索引表是按記錄鍵排序的，因此索引表本身是一個定長記錄的順序文件，從而也就可以方便地實現直接存取。2023/2/3（2）索引文件圖6-4索引文件的組織2023/2/3（2）索引文件索引文件可有較快的檢索速度，故它主要用于對信息處理的及時性要求較高的場合。但它除了有主文件外，還須配置一張索引表，且每個記錄都要有一個索引項，因此提高了存儲費用2023/2/3（3）索引順序文件圖6-5索引順序文件索引順序文件，將順序文件中的所有記錄分為若干個組，每組中的第一個記錄建立一個索引項2023/2/33目錄結構現代計算機系統中，對大量的文件實施有效的管理，主要是通過文件目錄實現的。文件目錄也是一種數據結構，用于標識系統的文件及其物理地址，供檢索時使用。對目錄管理的要求如下：(1)實現“按名存取”。(2)提高對目錄的檢索速度。(3)文件共享。(4)允許文件重名。

2023/2/3文件控制塊和索引結點文件控制塊（FCB）：文件控制塊是操作系統為管理文件而設置的數據結構，存放了為管理文件所需的所有有關信息，文件管理程序可借助于文件控制塊中的信息，對文件施以各種操作。文件控制塊是文件存在的標志，文件與文件控制塊一一對應，文件控制塊的有序集合稱為文件目錄2023/2/3文件目錄：把所有的FCB組織在一起，就構成了文件目錄，即文件控制塊的有序集合目錄項：構成文件目錄的項目（目錄項就是FCB）目錄文件：為了實現對文件目錄的管理，通常將文件目錄以文件的形式保存在外存，這個文件就叫目錄文件2023/2/3(2)索引結點文件目錄是存放在磁盤上的，當文件很多時，文件目錄可能要占用大量的盤塊。在查找目錄的過程中，先將存放目錄文件的第一個盤塊中的目錄調入內存，然后把用戶所給定的文件名與目錄項中的文件名逐一比較。若未找到指定文件，便再將下一個盤塊中的目錄項調入內存。在檢索目錄文件的過程中，我們發現只用到了文件名，其它信息在檢索目錄時一概不用，所以也不需調入內存。將文件名與文件描述信息分開。文件描述信息單獨形成一個稱為索引結點的數據結構，在文件目錄中每個目錄項只存文件名和指向該文件索引結點的指針。索引結點還有磁盤索引結點與內存索引結點之分。2023/2/3(2)索引結點2023/2/3目錄結構（1）單級目錄結構為所有文件建立一個目錄文件（組成一線性表）文件名物理地址文件說明狀態位文件名1文件名2…單級目錄2023/2/3基本原理它采用的方法是為外存的全部文件設立一張目錄表。表中包括全部文件的文件名、存儲文件的物理地址，以及文件的其他屬性，如文件長度、文件類型等等。每個文件占據表中的一條記錄。該目錄表存放在外存的某個固定區域，需要時系統將其全部或部分調入主存。基本操作：建立，刪除優點（1）目錄結構易于實現，管理簡單（2）能實現按名存取缺點：(1)查找速度慢：平均n/2(2)不允許重名(3)不便于實現文件共享單級目錄結構2023/2/3（2）二級目錄結構為了克服單級目錄的缺點，為每一個用戶建立一個單獨的用戶文件目錄UFD。二級文件目錄結構把目錄分成主目錄和用戶文件目錄兩級。主目錄由用戶名和用戶文件目錄首地址組成，用戶文件目錄中登記相應的用戶文件的目錄項。2023/2/3（2）兩級目錄兩級目錄結構2023/2/3在二級目錄結構中，區別不同的文件除文件名外還有文件的用戶名，因此不同的用戶可以使用相同的文件名。例如用戶Zhang中使用文件名Test，用戶Wang也可使用文件名Test，因為標識這兩個文件時還要加上用戶名，Zhang：Test和Wang：Test，不致于造成混淆。

2023/2/3優點：提高了檢索目錄的速度:m+n(2)在不同的用戶目錄中，可以使用相同的文件名。(3)不同用戶還可使用不同的文件名來訪問系統中的同一個共享文件（4）可實現對文件的保護和保密作用。缺點:(1)二級文件目錄雖然解決了不同用戶之間文件同名的問題，但同一用戶的文件不能同名。(2)如果一個用戶擁有很多的文件，那么在他的目錄中進行查找，所花費的時間仍然會很長(3)缺乏靈活性。（2）二級目錄結構2023/2/3（3）多級目錄結構1)目錄結構多級目錄結構由根目錄和各級目錄組成，為管理上的方便，除根目錄外，其它各級目錄均以文件的形式組成目錄文件。根目錄中的每個目錄項可以對應一個目錄文件，也可以對應一個數據文件，同樣目錄文件中的每個目錄項可以對應一個目錄文件，也可以對應一個數據文件。如此類推，就形成多級目錄結構。也稱樹形目錄結構2023/2/32023/2/32）路徑名在多級目錄結構中一個文件的唯一標識不再是文件名，而是從根結點開始，經過一個或多個中間結點，到達某個葉結點的一條路徑。稱這條路徑為文件的路徑名，它是文件的唯一標識。路徑名由根目錄和所經過的目錄名和文件名以及分隔符組成，通常使用分隔符/。例如/d1/f1，/d2/d5/f3，/f7

2023/2/33）當前目錄在多級目錄結構中，文件路徑名一般較長，而用戶總是局部地使用文件，為了方便起見，可把經常使用的文件所在的目錄指定為工作目錄。查詢時，若路徑名以/開頭；則從根目錄開始查找，否則從當前目錄開始查找。相對路徑名，絕對路徑名2023/2/3（4）圖形目錄結構加了鏈接的樹形目錄結構。2023/2/34.文件共享基本概念文件共享是指一個文件可以被多個授權的用戶共同使用。文件的共享要解決兩個問題。一是如何實現共享，二是對各類共享文件的用戶進行存取控制。早期實現文件共享的方法（1）繞彎路法（2）連訪法（3）基本文件法2023/2/34.文件共享共享方式硬鏈接軟鏈接（符號鏈接）2023/2/3硬鏈接

記錄的是目標文件的索引結點。它只能鏈接文件，不能鏈接目錄，不能跨文件系統。創建鏈接時，將增加目標文件的引用計數。刪除目標文件或鏈接文件時都會導致引用計數的減少。2023/2/3基于索引結點的共享方式2023/2/3符號鏈接利用符號鏈實現文件共享

由系統創建一個LINK類型的新文件，與共享文件名相同，并將其寫入B的目錄中。新文件中只包含被鏈接文件的路徑名，這樣的鏈接方法被稱為符號鏈接。新文件中的路徑名被看作是符號鏈。當B要訪問被鏈接的文件時，讀LINK類文件，OS根據新文件中的路徑名去讀該文件，實現文件的共享。2023/2/3基于符號鏈的共享方式Owner=wang類型：普通文件物理地址Owner=Lee類型：LINK文件物理地址Test符號鏈2023/2/3符號鏈接

在利用符號鏈方式實現文件共享時，只是文件主才擁有指向其索引結點的指針；而共享該文件的其他用戶，則只有該文件的路徑名，并不擁有指向其索引結點的指針。這樣，也就不會發生在文件主刪除一共享文件后留下一懸空指針的情況。當文件的擁有者把一個共享文件刪除后，其他用戶試圖通過符號鏈去訪問一個已被刪除的共享文件時，會因系統找不到該文件而使訪問失敗，于是再將符號鏈刪除，此時不會產生任何影響。創建符號鏈接不會增加目標文件的引用計數。2023/2/3符號鏈接

優點：可以用于鏈接世界上任何地方的機器中的文件。缺點：當其他用戶去讀共享文件時，系統是根據給定的文件路徑名，逐個分量地去查找目錄，直至找到該文件的索引結點。因此在每次訪問時都要多次讀盤，開銷大。每個LINK文件都要配置索引結點，耗費一定的磁盤空間。

2023/2/3文件保護為了防止系統中的文件被非法竊取和破壞。訪問類型。包括讀、寫、執行等訪問控制存取控制矩陣存取控制表2023/2/3（二）文件系統實現文件系統層次結構應用程序接口邏輯文件系統文件組織模塊基本文件系統I/O控制設備檢查用戶提供命令句法的正確性負責目錄的管理和維護，以及文件的安全保護檢查。負責將預讀寫文件的邏輯記錄和讀寫位置轉換成其在文件中的相對塊號，進而轉換成在文件存儲器中的物理塊號。將上層傳下來的命令和物理塊轉換成對適當的設備驅動程序調用由設備驅動程序和中斷處理程序組成。它負責將上層傳來的命令，轉換成硬件設備的專用I/O指令和相應設備的地址，控制設備完成與主存之間的信息傳輸，將傳輸是否成功的狀態碼返回上層模塊。2023/2/3目錄實現線性表哈希表2023/2/3文件實現與文件的邏輯結構和存取方法有關。2023/2/3文件物理結構文件的物理結構是指文件在物理存儲介質上的結構。1、順序結構——連續分配方式2、鏈接結構——鏈接分配方式3、索引結構——索引分配方式2023/2/3（1）連續分配連續分配要求為每一個文件分配一組相鄰接的盤塊。通常它們都位于一條磁道上。在進行讀/寫時，不必移動磁頭，僅當訪問到一條磁道的最后一個盤塊后，才需要移到下一條磁道。這樣所形成的文件結構稱為順序文件結構，此時的物理文件稱為順序文件。2023/2/3（1）連續分配這種分配方式保證了邏輯文件中的記錄順序與存儲器中文件占用盤塊的順序的一致性。為使系統能找到文件存放的地址，應在目錄項的文件物理地址字段中，記錄該文件第一個記錄所在的盤塊號和文件長度（以盤塊數進行計量）。2023/2/32023/2/3優點簡單順序訪問容易順序訪問速度快所需的磁盤尋道次數和尋道時間最少2023/2/3缺點要求有連續的存儲空間外部碎片問題外存緊湊必須事先知道文件的長度文件不易動態增長預留空間:浪費重新分配和移動2023/2/3（2）鏈接結構這是一種非連續的結構，將一個邏輯文件存儲到外存上時，并不要求為整個文件分配一塊連續的空間，而是可以將文件裝到多個離散的盤塊中。采用鏈接分配方式時，可通過在每個盤塊上的鏈接指針，將同屬于一個文件的多個離散的盤塊鏈接成一個鏈表，把這樣形成的物理文件稱為鏈接文件。2023/2/3隱式鏈接在文件目錄的每個目錄項中，都須含有指向鏈接文件第一個盤塊和最后一個盤塊的指針。鏈接結構的文件適用于順序存取。因為要獲得某一塊的塊號，必須先讀出第一個盤塊。。。。順序查找直至第i塊，因此要隨機地存取信息就較為困難，且可靠性差。2023/2/3文件名始址末址jeep925文件目錄01234567891011121314151617181920212223242526272829303111016-1252023/2/3優缺點優點：提高了磁盤空間利用率,不存在外部碎片問題有利于文件插入和刪除有利于文件動態擴充缺點：存取速度慢，不適于隨機存取鏈接指針占用一定的空間可靠性問題，如指針出錯2023/2/3顯式鏈接文件分配表(FAT)將盤塊中的鏈接指針按盤塊號的順序集中起來，構成盤文件映射表/文件分配表顯式地存放在內存中。整個磁盤僅設置一張，利用FAT可進行隨機存取。2023/2/3圖示2023/2/3鏈接分配方式雖然解決了連續分配方式所存在的問題，但又出現了另外兩個問題：不能支持高效的直接存取FAT需占用較大的內存空間實際上打開某個文件時，只需把該文件占用的盤塊的編號調入內存即可。為此應將每個文件所對應的盤塊號集中地放在一起。2023/2/3（3）索引分配一個文件的信息存放在若干不連續物理塊中，系統為每個文件建立一個專用數據結構--索引表，并將這些塊的塊號存放在索引表中。一個索引表就是磁盤塊地址數組,其中第i個條目指向文件的第i塊——單級索引分配2023/2/3單級索引分配2023/2/3012345678910111213141516171819202122232425262728293031文件名索引表地址文件目錄Jeep1991611025-1-1-1192023/2/3優點保持了鏈接結構的優點，又解決了其缺點：即能順序存取，又能隨機存取滿足了文件動態增長、插入刪除的要求能充分利用外存空間不會產生外部碎片2023/2/3缺點索引表本身要花費較多的外存空間。通常采用一個專門的盤塊作為一個索引塊。對于小文件采用索引分配方式時，其索引塊的利用率極低。如果文件非常大，一個索引塊裝不了，需要多個索引塊時，單級索引分配方式也是低效的

2023/2/3多級索引分配為這些索引塊再建立一級索引——兩級索引分配方式。（三級、四級）2023/2/3混合索引分配方式將多種索引分配方式相結合：直接地址，一級索引、二級索引、三級索引。。。UNIX系統中采用2023/2/3混合索引分配方式共設有13個地址項，分成兩類，直接地址和間接地址。直接地址：直接存放文件數據盤塊的盤塊號假如每個盤塊的大小為4KB，當文件不大于40KB時，便可直接從索引結點中讀出該文件的全部盤塊號2023/2/3混合索引分配方式一次間接地址：假如每個盤塊的大小為4KB,一次間接地址可存放1K個盤塊號，因而允許文件長達4MB2023/2/3混合索引分配方式多次間接地址：當文件長度大于4MB+40KB時，則采用二次間址分配方式。文件最大長度可達4GB。三次間址分配方式，文件最大長度可達4TB。2023/2/3（三）磁盤組織與管理目前，幾乎所有隨機存取的文件，都是存放在磁盤上，磁盤I/O速度的高低將直接影響文件系統的性能。磁盤結構磁盤調度算法磁盤空間管理2023/2/3信息記錄在磁道上，多個盤片，正反兩面都用來記錄信息，每面一個磁頭所有盤面中處于同一磁道號上的所有磁道組成一個柱面物理地址形式：柱面號（磁道號） 磁頭號扇區號柱面、磁頭、扇區2023/2/3磁盤啟動時，磁頭首先處于0磁道，磁盤從接到命令到向目標扇區讀取或寫入數據完畢共經歷三個階段：尋道：磁頭沿徑向移動，移到目標扇區所在磁道的上方（注意，不是目標扇區，而是目標扇區所在的磁道）旋轉延遲：找到目標磁道后通過盤片的旋轉，使得要目標扇區轉到磁頭的下方數據傳輸：數據在磁盤與內存之間的實際傳輸磁盤的訪問過程2023/2/32磁盤調度算法當多個訪盤請求在等待時，采用一定的策略，對這些請求的服務順序調整安排，旨在降低平均磁盤服務時間，達到公平、高效公平：一個I/O請求在有限時間內滿足高效：減少設備機械運動所帶來的時間浪費1先來先服務FCFS2最短尋道時間優先SSTF3SCAN算法4循環掃描算法CSCAN2023/2/3根據進程請求訪問磁盤的先后次序進行調度優點：簡單，公平，每個進程的請求都能依次得到處理；缺點：效率不高，相鄰兩次請求可能會造成最內到最外的柱面尋道，使磁頭反復移動，增加了服務時間，對機械也不利僅適應于請求磁盤I/O的進程數目較少的場合1）先來先服務2023/2/3優先選擇距當前磁頭最近的訪問請求進行服務，主要考慮尋道優先優點：改善了磁盤平均服務時間；缺點：造成某些訪問請求長期等待得不到服務，“饑餓現象”2）最短尋道時間優先2023/2/3克服了最短尋道優先的缺點，既考慮了距離，同時又考慮了方向具體做法：當設備無訪問請求時，磁頭不動；當有訪問請求時，磁頭按一個方向移動，在移動過程中對遇到的訪問請求進行服務，然后判斷該方向上是否還有訪問請求，如果有則繼續掃描；否則改變移動方向，并為經過的訪問請求服務，如此反復3）SCAN算法（電梯算法）2023/2/3（磁頭單向移動）電梯算法杜絕了饑餓，但當請求對磁道的分布是均勻時，磁頭回頭，近磁頭端的請求很少（因為磁頭剛經過），而遠端請求較多，這些請求等待時間要長一些。例如：總是自里向外移動，當磁頭移動到最外的磁道并訪問后，立即返回到最里的欲訪問的磁道，返回時不為任何的等待訪問者服務。返回后可再次從里向外進行掃描。稱為循環掃描算法4）循環掃描調度算法2023/2/3調度算法的選擇實際系統相當普遍采用最短尋道時間優先算法，因為它簡單有效，性價比好。掃描算法更適于磁盤負擔重的系統。磁盤負擔很輕的系統也可以采用先來先服務算法一般要將磁盤調度算法作為操作系統的單獨模塊編寫，利于修改和更換。2023/2/33.磁盤管理

文件管理要解決的重要問題之一就是如何為新創建的文件分配存儲空間。其解決方法與內存的分配情況有許多相似之處，可采取連續分配和離散分配方式。不論哪種分配方式，存儲空間的基本分配單位都是磁盤塊而非字節。為了實現存儲空間的分配，系統首先應記住存儲空間的使用情況。還要提供對存儲空間進行分配和回收的手段。2023/2/33.磁盤管理

記住存儲空間的使用情況就是對空閑塊的管理，有以下方法：空閑表法空閑鏈表法位示圖法2023/2/31）空閑表法屬于連續分配方式，與內存管理中的動態分區分配方式相同。為每個文件分配一塊連續的存儲空間。系統為外存上的所有空閑區建立一張空閑表，每個空閑區對應于一個空閑表項所有空閑區按其起始盤塊號遞增的次序排列序號起始空閑盤塊號盤塊數1242933155。。。。。。2023/2/31）空閑表法存儲空間的分配與回收空閑盤塊的分配與內存的動態分配類似，同樣可以用首次、最佳、最壞適應法。盤塊的回收也同內存的回收方式類似。在內存中很少用連續分配的方式，在外存中因它具有較高的分配速度，可減少訪問磁盤的I/O頻率，故在有些時候也可以使用對換空間，一般都采用連續分配的方式。當文件較小時，采用連續分配方式2023/2/32）空閑鏈表法空閑鏈表法是將所有空閑盤區拉成一條空閑鏈。根據構成的鏈所用基本元素不同，可把鏈表分成兩種形式，空閑盤塊鏈和空閑盤區鏈空閑盤塊鏈：以盤塊為單位。空閑盤區鏈：以盤區（多個盤塊）為單位2023/2/3空閑鏈表法空閑鏈表法的分配與回收。空閑盤區鏈：分配：與內存動態分配類似。回收：類似于內存回收。2023/2/3空閑鏈表法空閑鏈表法的分配與回收。空閑盤塊鏈：分配：當用戶因創建文件而請求分配存儲空間時，系統從鏈首開始依次摘下適當數目的空閑盤塊分配給用戶，然后調整鏈首指針。回收：將回收的盤塊依次插入空閑盤塊鏈的末尾。特點：用于分配和回收一個盤塊的過程非常簡單，但在為一個文件分配盤塊時，可能要重復操作多次。2023/2/33）位示圖法系統為磁盤建立一張位示圖，在位示圖中每個盤塊占1位，按盤塊的順序排列。“1”表示對應的盤塊已占用，"0"表示空閑。。2023/2/3第5章設備管理（一）

I/O管理概述

1.

I/O控制方式

2.軟件層次結構

2023/2/3I/O設備I/O系統設備分類2023/2/3設備控制器設備控制器主要負責控制一個或多個I/O設備，以實現I/O設備和計算機之間的數據交換。它是CPU與I/O設備之間的接口，接收從CPU發來的命令，并控制I/O設備工作，以使CPU從繁雜的設備控制事務中解脫出來。設備控制器可分為兩類，一類用于控制字符設備的控制器，另一類是用于控制塊設備的控制器。2023/2/3 為使中央處理機從繁忙的I/O處理中擺脫出來，現代大、中型計算機系統中設置了專門的處理I/O操作的處理機，并把這種處理機稱為通道。通道在CPU的控制下獨立地執行通道程序，對外部設備的I/O操作進行控制，以實現內存與外設之間成批的數據交換。 通道=I/O處理機

通道概念2023/2/3I/O通道I/O通道的分類字節多路通道數據選擇通道數組多路通道2023/2/31.I/O控制方式1程序I/O方式2I/O中斷方式3DMA方式4通道方式中斷DMA通道2023/2/3程序I/O方式I/O控制器是OS同硬件之間的接口。它有兩個寄存器：數據緩沖寄存器、控制/狀態寄存器。狀態控制寄存器有一個標志忙/閑的標志位busy。CPU外部設備控制邏輯電路控制寄存器I/O控制器數據寄存器2023/2/3工作過程以輸入為例1、把busy置12、反復測試busy，為1表示輸入機尚未輸完一個字，處理機應繼續對該標志進行測試，轉2，為0表示輸入機已將輸入數據送入控制器的數據寄存器中，轉33、把數據從數據緩沖區中讀走，并置busy為1。所謂“程序循環測試”的數據傳輸方式，就是指用戶進程使用啟動設備后，不斷地執行測試指令，去測試所啟動設備的狀態寄存器。只有在狀態寄存器出現了所需要的狀態后，才停止測試工作，完成輸入/輸出。忙等待方式2023/2/3

在程序I/O方式中，由于CPU的高速性和I/O設備的低速性，致使CPU的絕大部分時間都處于等待I/O設備完成數據I/O的循環測試中，造成對CPU的極大浪費。在該方式中，CPU之所以要不斷地測試I/O設備的狀態，就是因為在CPU中無中斷機構，使I/O設備無法向CPU報告它已完成了一個字符的輸入操作。2023/2/3I/O中斷方式I/O控制器能發中斷。工作過程：1、發出啟動某設備的命令，本進程（A）變為等待狀態，轉進程調度，調度另一進程B。2、輸入完成時，控制器發出中斷，中斷B，通過中斷進入中斷處理程序。3、在中斷處理程序中把數據緩沖寄存器中的數取走，放入內存特定位置M，喚醒等待進程A，中斷返回到B的斷點繼續執行。4、在以后的某個時刻OS調度要求輸入的進程A。A從M取數處理。

2023/2/3

在I/O設備輸入每個數據的過程中，由于無須CPU干預，因而可使CPU與I/O設備并行工作。僅當輸完一個數據時，才需CPU花費極短的時間去做些中斷處理。可見，這樣可使CPU和I/O設備都處于忙碌狀態，從而提高了整個系統的資源利用率及吞吐量。例如，從終端輸入一個字符的時間約為100ms，而將字符送入終端緩沖區的時間小于0.1ms。若采用程序I/O方式，CPU約有99.9ms的時間處于忙—等待中。采用中斷驅動方式后，CPU可利用這99.9ms的時間去做其它事情，而僅用0.1ms的時間來處理由控制器發來的中斷請求。可見，中斷驅動方式可以成百倍地提高CPU的利用率。

2023/2/3分析同前相比，CPU利用率大大提高。缺點：每臺設備每輸入輸出一個字節的數據都有一次中斷。如果設備較多時，中斷次數會很多，使CPU的計算時間大大減少。為減少中斷對CPU造成的負擔，可采用DMA方式和通道方式。2023/2/3DMA方式直接存儲器存取控制方式的概念是指對I/O設備的控制由DMA控制器完成，在DMA控制器的作用下，設備和主存之間可以成批地進行數據交換，而不用CPU的干涉。2023/2/35.2.3DMA方式直接存儲器存取控制方式的概念該方式的特點是：①數據傳輸的基本單位是數據塊，即在CPU與I/O設備之間，每次傳送至少一個數據塊；②所傳送的數據是從設備直接送入內存的，或者相反；③僅在傳送一個或多個數據塊的開始和結束時，才需CPU干預，整塊數據的傳送是在控制器的控制下完成的。可見，DMA方式較之中斷驅動方式，又是成百倍地減少了CPU對I/O的干預，進一步提高了CPU與I/O設備的并行操作程度。

2023/2/3DMA方式 控制器功能更強，除有中斷功能外，還有一個DMA控制機構。在DMA控制器的控制下，設備同主存之間可成批交換數據，不用CPU干預。DMA控制器組成：主機與DMA控制器的接口；DMA控制器與塊設備的接口；I/O控制邏輯2023/2/3直接存儲器存取控制直接存儲器存取控制方式的特點I/O數據傳輸速度快，CPU負擔少。在DMA方式下，數據的傳送方向、存放數據的內存始址及傳送數據的長度等都由CPU控制。每臺設備需要配一個DMA控制器。2023/2/3I/O通道控制方式

I/O通道控制方式的引入

雖然DMA方式比起中斷方式來，已經顯著地減少了CPU的干預，即已由以字(節)為單位的干預減少到以數據塊為單位的干預，但CPU每發出一條I/O指令，也只能去讀一個連續的數據塊，要是一次去讀多個數據塊且將它們分別傳送到不同的內存區域，則須由CPU發出多條I/O指令，進行多次中斷。

2023/2/3I/O通道控制方式

I/O通道控制方式的引入

I/O通道方式是DMA方式的發展，它可進一步減少CPU的干預，即把對一個數據塊的讀(或寫)為單位的干預，減少為對一組數據塊的讀(或寫)及有關的控制和管理為單位的干預。同時，又可實現CPU、通道和I/O設備三者的并行操作，從而更有效地提高整個系統的資源利用率。例如，當CPU要完成一組相關的讀(或寫)操作及有關控制時，只需向I/O通道發送一條I/O指令，以給出其所要執行的通道程序的首址和要訪問的I/O設備，通道接到該指令后，通過執行通道程序便可完成CPU指定的I/O任務。

2023/2/3通道的工作過程某進程在運行過程中，若提出了I/O請求，只需向通道I/O通道發一條I/O指令，以給出其所要執行的通道程序的始址和要訪問的I/O設備；用戶進程阻塞以等待I/O完成通道則通過執行通道程序控制設備控制器，控制設備完成指定的I/O任務。發出中斷信號通知CPU通道程序已執行完成。CPU響應中斷，進行善后處理并喚醒被阻塞的用戶進程2023/2/32.I/O系統層次及功能

用戶層軟件設備獨立性軟件設備驅動程序中斷處理程序硬件實現與用戶交互的接口，產生I/O請求負責實現與設備驅動器的統一接口、設備命名，設備的保護，設備的分配與釋放，緩沖等。與硬件直接相關，負責具體實現系統對設備發出的操作指令，驅動I/O設備工作的驅動程序保護環境，轉入相應處理程序，恢