【正文】 (見圖 )1. 設(shè)備分配中數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)有：系統(tǒng)設(shè)備表 （ SDT）、 設(shè)備控制表（ DCT）、 控制器控制表（ COCT）、 通道控制 表（ CHCT）。 每個表的具體內(nèi)容如下圖所示。? 在整個系統(tǒng)中，有一張 系統(tǒng)設(shè)備表（ SDT） ， 用于記錄系統(tǒng)中全部設(shè)備的信息。每個設(shè)備占一個表目，其中包括設(shè)備類型、設(shè)備標(biāo)識符、設(shè)備控制表指針及設(shè)備驅(qū)動程序的入口地址等表項。? 系統(tǒng)為每一個設(shè)備都配置了一張 設(shè)備控制表（ DCT）， 用于記錄該設(shè)備的情況。表中除了有用于指示設(shè)備類型的字段和設(shè)備標(biāo)識符字段外，還應(yīng)有下列字段：獨享 設(shè)備分配程序 1?設(shè)備隊列的隊首指針：凡因請求本設(shè)備而未得到滿足的進程，其 PCB都應(yīng)按照一定的策略排成一個隊列，稱為設(shè)備請求隊列或簡稱為設(shè)備隊列。其隊首指針指向隊首 PCB， 在有的系統(tǒng)中還設(shè)置了隊尾指針。?設(shè)備狀態(tài)：當(dāng)設(shè)備自身處于 “ 忙 ” 狀態(tài)時，將設(shè)備的忙標(biāo)志置 “ l” 。 若與該設(shè)備相連接的控制器或通道處于 “ 忙 ” 狀態(tài)，而不能啟動該設(shè)備，則將設(shè)備的等待標(biāo)志置 “ l” 。?COCT表指針：該指針指向與該設(shè)備相連接的控制器的控制表。在具有多條通路的情況下，一個設(shè)備可與多個控制器相連接。此時，在 DCT中應(yīng)設(shè)置多個控制器表指針。?重復(fù)執(zhí)行次數(shù)：外部設(shè)備在傳送數(shù)據(jù)時，若發(fā)生信息傳送錯誤，系統(tǒng)并不立即認(rèn)為傳送失敗，而是允許它重新傳送。只要在規(guī)定的重復(fù)次數(shù)或時間內(nèi)恢復(fù)正常傳送，則仍認(rèn)為傳送成功，否則才認(rèn)為傳送失敗。 設(shè)備分配的數(shù)據(jù)結(jié)構(gòu)圖 表目 1……表目 i……設(shè)備類型設(shè)備標(biāo)識符進程標(biāo)識符DCT表指針驅(qū)動程序入口地址表目 1……表目 i……設(shè)備類型設(shè)備標(biāo)識符設(shè)備狀態(tài)（ 等待 /不等待，忙 /閑）COCT表指針重復(fù)執(zhí)行的次數(shù)或時間設(shè)備隊列的隊首指針設(shè)備隊列的隊尾指針表目 1……表目 i……控制器標(biāo)識符控制器狀態(tài)（忙 /閑）CHCT表指針控制器隊列的隊首指針控制器隊列的隊尾指針表目 1……表目 i……通道標(biāo)識符通道狀態(tài)（忙 /閑）COCT表指針通道隊列的隊首指針通道隊列的隊尾指針SDT集合 SDT DCT集合 DCTCOCT集合 COCT CHCT集合 CHCT設(shè)備分配程序 21 對 于具有 單 通道的系 統(tǒng) ， 則 當(dāng) 進 程提出 I/O請 求后，系 統(tǒng) 依次 查 找 圖 413的 SDT和 DCT、 COCT、 CHCT四個表， 分別從中 找出 設(shè)備 、相 連 的 控制器、通道，根據(jù)相應(yīng)表目狀態(tài)字可知它是否正忙（ DCT表目還要看狀態(tài)字是否等待）。若忙，便將請求 I／ O進程的 PCB掛在它的等待隊列上；否則，便將它分配給進程。只有在設(shè)備、控制器和通道三者都分配成功時，這次的設(shè)備分配才算成功。然后，便可啟動該 I／ O設(shè)備進行數(shù)據(jù)傳送。 單通道系統(tǒng)的設(shè)備分配流程 進程 P提出所需的 I/O設(shè)備根據(jù)物理設(shè)備名，從 SDT中找出該設(shè)備的 DCT由 DCT的設(shè)備狀態(tài)字段，檢查該設(shè)備是否忙？將該進程的 PCB插入到該設(shè)備的等待隊列中檢查本次設(shè)備分配是否安全性？將此設(shè)備分配給該進程從其 DCT中找出與該設(shè)備連接的控制器的 COCT， 檢查該控制器是否忙？將該進程的 PCB插入到該控制器的的等待隊列中將該控制器分配給進程從 COCT中找到與該控制器連接的通道的 CHCT， 檢查該通道是否忙 ？將該進程的 PCB插入到該通道的的等待隊列中 將該通道分配給進程至此，設(shè)備、控制器和通道三者都已分配成功啟動 I/O設(shè)備，進行具體的 I/O操作不忙若忙不安全不忙忙 忙 不忙設(shè)備分配程序 3 3。設(shè)備分配程序的改進 為了獲得設(shè)備的獨立性，進程應(yīng)用邏輯設(shè)備名請求I/O。 這樣，系統(tǒng)首先從 SDT中找出第一個該類設(shè)備的 DCT。 如忙，則查找第二個該類設(shè)備的 DCT， 當(dāng)所有該類設(shè)備都忙時，才把進程掛在該類設(shè)備的等待隊列中。 實際上，系統(tǒng)為了提高可靠性和靈活性，通常采用多通路的 I/O系統(tǒng)結(jié)構(gòu) (見圖 )。此時對多個控制器和通道的分配，必須查找所有的控制器和通道，才能決定是否將該進程掛起。為進程 P分配所需的 I/O設(shè)備從 SDT表查該類設(shè)備的控制表 DCT由 DCT檢查該設(shè)備忙否 ?不忙檢查分配此設(shè)備的安全性 ?不安全分配此設(shè)備給進程 P查此設(shè)備連接的 COCT忙否 ?不忙不忙分配此控制器給進程 P查此控制器連接的 CHCT忙否 ?最后一個 DCT?分配此通道給進程 P啟動 I/O,進行具體的 I/O操作忙進程 P的 PCB放入此設(shè)備的等待隊列YN忙 最后一個 COCT?最后一個 DCT?進程 P的 PCB放入此控制器的等待隊列YNY忙最后一個 CHCT?Y最后一個 COCT?進程 P的 PCB放入此通道的等待隊列NYNN多通路設(shè)備分配流程示意圖4． 6 磁盤 I/O (Disk I/O)在現(xiàn)代的計算機系統(tǒng)中，都把磁盤作為文件存儲器，因為磁盤存儲器不僅容量大（硬盤單個容量可達 28GB）， 存取速度快（內(nèi)部傳輸率達 257MB/sec）， 而且是可以隨機存取的共享設(shè)備，是實現(xiàn)虛擬存儲器所必需的硬件。提高磁盤 I/O速度，系統(tǒng)應(yīng)選擇性能好的磁盤，采用好的磁盤調(diào)度算法和設(shè)置磁盤高速緩沖區(qū)。4． 6． 1磁盤結(jié)構(gòu) 磁 盤 存 儲 器由磁 盤驅(qū)動 器、磁 盤 控制器和磁 盤 （片）三個部分 組 成。在硬 盤 存 儲 器中，將若干個 盤 片組 合在一起，形成一個 盤 片 組 。當(dāng) 驅(qū)動 器旋 轉(zhuǎn)時 ，所有 盤 片都沿 軸 平面 轉(zhuǎn)動 ，目前硬 盤轉(zhuǎn) 速已達每分鐘 7200轉(zhuǎn) 。 緊 靠著 盤 片的是 傳動 臂，臂的末端是 讀寫 頭 。 柱面扇區(qū)磁臂磁頭磁盤結(jié)構(gòu) 1按磁頭的工作方式，可以分為活動頭磁盤和固定頭磁盤。z活動頭磁盤 活動頭磁盤一個盤面上僅配有一個磁頭，所有磁頭都安裝在一個傳動臂上，在訪問盤面上的磁道時，傳動臂在步進電機的控制下，可在整個盤面上從外向內(nèi)，或從內(nèi)向外移動，這稱為尋道?；顒宇^磁盤只能進行串行讀 /寫，導(dǎo)致 I/O速度較饅，但是由于結(jié)構(gòu)簡單，仍廣泛用于中、小型磁盤設(shè)備中。微機上配置的溫盤和軟盤，都采用活動磁頭結(jié)構(gòu)。z固定頭磁盤 固定頭磁盤在每條磁道上都有一個讀 /寫磁頭，所有的磁頭都被裝在一剛性磁臂中，通過這些磁頭可訪問所有的磁道，可以進行并行讀 /寫操作，有效地提高了磁盤的 I/O速度。這種結(jié)構(gòu)的磁盤主要用于大容量磁盤上。4． 6． 2數(shù)據(jù)的組織 ? 1．磁盤的容量? 磁盤設(shè)備中，一般包含一個或多個盤片，每片分兩面，每面又可分成若干條磁道（即 n個同心圓）。最外邊的磁道標(biāo)為 0道，最里面的磁道為 n1道。磁道的個數(shù)取決于盤的大小和存儲的密度。每個磁道又被劃分為若干個扇區(qū)，一般被劃分成 10～ 100個扇區(qū)。每一個扇區(qū)是磁盤存儲信息和傳送信息的基本單位（ 512字節(jié)），又稱為存儲塊，或簡稱為塊。我們常用的 英寸的軟盤怎樣來計算的容量呢？? 軟盤的容量 =每扇區(qū)的字節(jié)數(shù)（ 512字節(jié)） （扇區(qū)數(shù)/道） （磁道數(shù) /面） （面數(shù)），所以 盤的總量 =51218802= MB。 磁盤的容量 1一個容量較大的硬盤含有若干個盤片，每一個盤片有上下兩個盤面。如果硬盤中有 4個盤片，則共有8個磁面。磁盤中處于相同磁道（同心園）位置上，但在不同盤面上的磁道的集合，稱為柱面。柱面的序號與磁道的序號相同。顯然，存取同一柱面上各磁道中的信息不必移動磁頭。而磁盤存取信息的大部分時間是化費在移動磁頭到相應(yīng)磁道上，所以，把相關(guān)信息存儲在同一柱面上，可以使存取速度更快，更有效。那么，我們又怎樣來計算硬盤的容量呢？ 硬 盤 的容量 =每扇區(qū)的字 節(jié) 數(shù)（ 512字 節(jié) ） （扇區(qū)數(shù) /道） （柱面數(shù)） （磁 頭 數(shù)）例如一個硬 盤 有 15個磁 頭 ， 8894個柱面，每道 63個扇區(qū)，則 它的容量 =51263889415= GB。 DisksparametersDiskparametersfortheoriginalIBMPCfloppydiskandaWesternDigitalWD18300harddisk2．物理扇區(qū)號和邏輯扇區(qū)號 ? 扇區(qū)是磁盤存儲和傳送信息的基本單位。要在磁盤上訪問一個扇區(qū)，必須給出其磁道號（或柱面號）、盤面號（磁頭號）和扇區(qū)號，這樣才能準(zhǔn)確地定位要訪問的扇區(qū)，這稱為扇區(qū)的物理地址，即物理扇區(qū)號。由物理扇區(qū)號表示的扇區(qū)稱為絕對扇區(qū)。為了方便，操作系統(tǒng)通常將其轉(zhuǎn)變?yōu)檫壿嬌葏^(qū)號加以管理。編址方式為：在磁道上按扇區(qū)號增加，在柱面上按磁道號增加，對整個磁盤從柱面 0到最后一個柱面增加。例如，每磁道扇區(qū)數(shù)為 S， 每個柱面的磁道數(shù)為 T， 那么可將柱面號 i， 盤面號為 j， 扇區(qū)號為 k的物理扇號轉(zhuǎn)換為邏輯扇區(qū)號為： b=k+S*（T*i+j）。 操作系統(tǒng)中，都以邏輯扇號為文件分配扇區(qū)，也以邏輯扇號來調(diào)用塊設(shè)備驅(qū)動程序，進行磁盤的讀 /寫操作。 4． 6． 3磁盤的訪問時間 由于磁盤上的一個扇區(qū)要用三個參數(shù)（柱面號、磁頭號和扇區(qū)號）來定位，所以對磁盤的訪問時間，包括以下三部分的時間：z尋道時間 （ Seek time ） TS 這是 把磁頭從當(dāng)前位置移動到指定磁道上所經(jīng)歷的時間 。該時間是啟動磁盤的時間 s與磁頭移動 n條磁道所花費的時間之和。 即 TS ＝ mn 十 s 式中， m是一個常數(shù)，它與磁盤驅(qū)動器的速度有關(guān)。對一般磁盤而言， m=； 對高速磁盤而言， m≤ ，磁盤啟動時間約為 3ms。 這樣，對一般的硬盤，其尋道時間將隨尋道距離的增大而增大，大約為 10～ 40ms（ 目前硬盤的平均尋道時間達 ）。磁盤的訪問時間 1z旋轉(zhuǎn)延遲時間 （ Rotationaldelayorrotationallatency ） Tr Tr 是指定扇區(qū)移動到磁頭下所經(jīng)歷的時間。對于硬盤來說，典型的轉(zhuǎn)速為 3600RPM（ 目前硬盤的轉(zhuǎn)速為 5400RPM， 甚至達到 7200RPM）， 每轉(zhuǎn)需時 ， 平均旋轉(zhuǎn)延遲時間為 。 對于軟盤，其旋轉(zhuǎn)速度為 300或 600RPM， 平均 Tr為50～ 100ms。磁盤的訪問時間 2z傳輸時間 Tt Tt 是指把數(shù)據(jù)從磁盤讀出，或向磁盤寫人數(shù)據(jù)所經(jīng)歷的時間，它的大小與每次所讀／寫的字節(jié)數(shù) b及旋轉(zhuǎn)速度 r(/秒 )有關(guān)： Tt =b/(r*N) 式中 N為一條磁道上字節(jié)數(shù)。當(dāng)一次讀／寫的字節(jié)數(shù)相當(dāng)于半條磁道上的字節(jié)數(shù)時， Tt與 Tr相同。 在這三部分時間里，其中尋道時間 TS占的比例最大，而傳輸時間所占了相當(dāng)小的比例。即在訪問時間中，尋道時間和旋轉(zhuǎn)延遲時間占據(jù)了訪問時間的大頭，基本上都與所讀／寫數(shù)據(jù)的多少無關(guān)。4． 6． 4 磁盤（移臂）調(diào)度算法 磁 盤 是可被多個 進 程共享的 設(shè)備 。當(dāng)有多個進 程都 請 求 訪問 磁 盤時 ， 應(yīng) 采用一種適當(dāng)?shù)?調(diào) 度算法，以減小各 進 程 對 磁 盤 的平均訪問 （主要是 尋 道） 時間 。目前常用的磁盤調(diào) 度算法有：先來先服 務(wù) 、最短 尋 道 時間優(yōu) 先、 掃 描算法和循 環(huán)掃 描算法等。 FCFS算法先來先服務(wù) FCFS（ First Come First Served）是一種最簡單的磁盤調(diào)度算法。它 根據(jù)進程請求訪問磁盤的先后次序進行調(diào)度 。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現(xiàn)某一進程的請求長期得不到滿足的情況。但此算法由于未對尋道進行優(yōu)化，致使平均尋道時間可能較長，（平均響應(yīng)時間長），各進程響應(yīng)時間變化幅度較小，公平 ,進程響應(yīng)時間可預(yù)測。FCFS1如下圖所示，磁頭總共移動了 640個柱面的距離。2． 最短尋道時間優(yōu)先 SSTF算法 該算法總是為那些與當(dāng)前磁頭所在的磁道距離最近請求服務(wù) ,也就是 執(zhí)行尋道時間最短的那個 I/O請求。這種調(diào)度算法有較好的平均尋道時間。 SSTF較之 FCFS有較好的尋道性能，故曾被廣泛采用。 SSTF算法雖然獲得較好的尋道性能，但它可能導(dǎo)致某些進程長時間的得不到服務(wù)（稱之為 饑餓 現(xiàn)象）。因為只要不斷有新進程到達，且其所要訪問的磁道與磁頭當(dāng)前所在磁道的距離較近，這種新進程的 I/O請求必被優(yōu)先滿足。對中間磁道訪問服務(wù)比內(nèi)、外兩側(cè)磁道服務(wù)好，造成響應(yīng)時間變化幅度大 ,在服務(wù)請求多時，內(nèi)外邊緣請求被無限期延遲，不可預(yù)期。SSTF1磁頭總共移動了 236個柱面的距離3． 掃描（ SCAN） 算法 為了解決 SSTF算法 饑餓 現(xiàn)象， 對 S