掃描演算法磁臂黏著

❶ 誰知道磁碟管理的作用

磁碟管理是一項使用計算機時的常規任務，Windows 2000 Server的磁碟管理任務是以一組磁碟管理應用程序的形式提供給用戶的，它們位於「計算機管理」控制台中，包括查錯程序、磁碟碎片整理程序、磁碟整理程序等。
磁碟存儲器不僅容量大，存取速度快，而且可以實現隨機存取，是實現虛擬存儲器所必需的硬體。因此在現代計算機系統中，都配置了磁碟存儲器，並以它為主，存放文件。磁碟存儲管理的主要任務是：
·為文件分配必要的存儲空間；
·提高磁碟存儲空間的利用率；
·提高對磁碟的I／O速度，以改善文件系統的性能；
·採取必要的冗餘措施，來確保文件系統的可靠性。
1．磁碟調度演算法
磁碟是可被多個進程共享的設備。當有多個進程都請求訪問磁碟時，應採用一種適當的調度演算法，以使各進程對磁碟的平均訪問(主要是尋道)時間最小。由於在訪問磁碟的時間中，主要是尋道時間，因此，磁碟調度的目標應是使磁碟的平均尋道時間最少。目前常用的磁碟調度演算法有：先來先服務；最短尋道時間優先；掃描演算法；循環掃描演算法等。
(1)先來先服務．(First-Come，First-Served，FCFS)
這是一種簡單的磁碟調度演算法。它根據進程請求訪問磁碟的先後次序進行調度。此演算法的優點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現某一進程的請求長期得不到滿足的情況。但此演算法由於未對尋道進行優化，致使平均尋道時間可能較長。圖4-5示出了有9個進程先後提出磁碟I／O請求時，按FCFS演算法進行調度的情況。這里，將進程號(請求者)按其發出請求的先後次序排列。這樣，平均尋道距離為55．3條磁軌。與後面要講的幾種調度演算法相比，其平均尋道距離較大。故FCFS演算法僅適用於請求磁碟I／O的進程數目較少的場合。
(2)最短尋道時間優先(ShortestSeekTimeFirst，SSTF)
該演算法選擇這樣的進程，其要求訪問的磁軌與當前磁頭所在的磁軌距離最近，以使每次的尋道時間最短，但這種調度演算法卻不能保證平均尋道時間最短。圖4-6所示按SSTF演算法進行調度時，各進程被調度的次序，每次磁頭的移動距離，以及9次磁頭移動的平均距離。比較圖4-5和圖4-6可以看出，SSTF演算法的平均每次磁頭移動距離，明顯低於FCFS的距離。SSTF較之FCFS有更好的尋道性能，故過去一度被廣泛採用過。
(3)各種掃描演算法
1)掃描(SCAN)演算法。SSTF演算法雖然獲得較好的尋道性能，但它可能導致某些進程發生「飢餓」(starvation)。SCAN演算法不僅考慮到欲訪問的磁軌與當前磁軌的距離，更優先考慮的是磁頭的當前移動方向。例如，當磁頭正在自里向外移動時，SCAN演算法所選擇的下一個訪問對象應是其欲訪問的磁軌既在當前磁軌之外，又是距離最近的。這樣自里向外地訪問，直到再五更外的磁軌需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調度，即其要訪問的磁軌，在當前磁軌之內，從而避免了飢餓現象的出現。由於這種演算法中磁頭移動的規律頗似電梯的運行，露故又稱為電梯調度演算法。
2)循環掃描(CSCAN)演算法。處理該進程的請求，致使該進程的請求被嚴重地推遲。為了減少這種延遲，CSCAN演算法規定磁頭單向移動。例如，只自里向外移動，當磁頭移到最外的被訪問磁軌時，磁頭立即返回到最里的欲訪磁軌，即將最小磁軌號緊接著最大磁軌號構成循環，進行掃描。
2．廉價冗餘磁碟陣列RAID
磁碟系統中比較引人注目的是廉價冗餘磁碟陣列(Rendant arrays ofinexpensive disk，RAID)的發展，這是將並行處理原理引入磁碟系統。它採用低成本的小溫盤，使多台磁碟構成磁碟陣列，數據展開存儲在多台磁碟上，提高數據傳輸的帶寬，並利用冗餘技術提高可靠性。磁碟陣列還具有容量大，數據傳輸率高，功耗低，體積小，成本低和便於維護等優點。1987年美國加州大學伯克利分校的D．A．Patterson等人，首先提出了廉價冗餘磁碟陣列的概念，並將RAID分為6級：
RAID-0。該級僅提供了並行交叉存取。它雖然有效提高了磁碟I／O速度，但並無冗餘校驗功能，致使磁碟系統的可靠性不好。只要陣列中有一個磁碟損壞，便會造成不可彌補的數據丟失。
RAID-1。它是鏡像磁碟冗餘陣列，將每一數據塊重復存人鏡像磁碟，以改善磁碟機的可靠性。鏡像盤也稱拷貝盤，它相當於一個不斷進行備份操作的磁碟。這種磁碟的冗餘度為100％，使有效容量下降了一半，成本較高。鏡像盤是磁碟陣列的簡單形式。
RAID-2。它是採用海明碼糾錯冗餘的磁碟陣列，將數據位交叉寫人幾個磁碟中，並利用幾個磁碟驅動器進行按位的出錯檢查，它比鏡像磁碟冗餘陣列的冗餘度小。這種陣列中的數據讀寫操作涉及陣列中的每一個磁碟，這影響小文件的傳輸率，因此它適合於大量順序數據訪問。
RAID-3。它是採用奇偶校驗冗餘的磁碟陣列，也採用數據位交叉，陣列中只有一個校驗盤。將數據按位交叉寫到幾個磁碟上，用一個校驗盤檢查數據錯誤。各磁碟同步運轉，陣列中的驅動器數量可擴展。這種陣列冗餘度較小，因為採用數據位交叉，所以也適合大量順序數據訪問。
RAID-4。它是一種獨立傳送磁碟陣列，採用數據塊交叉，用一個校驗盤。將數據按塊交叉存儲在多個磁碟上。在數據不沖突時，多個磁碟可並行進行數據讀操作。這種磁碟陣列適用於小塊數據讀寫，它的小塊數據傳輸速度比RAID-3快。
RAID-5。它也是一種獨立傳送磁碟陣列，採用數據塊交叉和分布的冗餘校驗，將數據和校驗都分布在各個磁碟中，沒有專門的奇偶校驗驅動器。奇偶校驗碼被分布存放在陣列中各驅動器中，磁碟冗餘度低，使並行讀寫操作成為可能。這種方法也適用於小塊數據的讀寫。但對控制器的要求較高，是最難實現的一種磁碟陣列。
RAID自1988年面世後，很快流行起來，這主要是因為RAID具有以下明顯的優點：
可靠性高。RAID的最大特點就是它的高可靠性。除了RAID-0級外，其餘各級都採用了容錯技術。與單台磁碟機相比，其可靠性往往高出一個數量級。
磁碟I／O速度高。由於磁碟陣列採取並行交叉存取，故可將磁碟I／O速度提高N-1倍，N為磁碟數目。性能／價格比高。利用RAID技術實現犬容量高速存儲器時，其體積與相同容量和速度的大型磁碟系統相比，只是後者的三分之一，價格也是後者的三分之一，且可靠性更高。

❷ 2018-06-09

一、常見的批處理作業調度演算法

1.先來先服務調度演算法（FCFS）:就是按照各個作業進入系統的自然次序來調度作業。這種調度演算法的優點是實現簡單，公平。其缺點是沒有考慮到系統中各種資源的綜合使用情況，往往使短作業的用戶不滿意，因為短作業等待處理的時間可能比實際運行時間長得多。

2.短作業優先調度演算法(SPF): 就是優先調度並處理短作業，所謂短是指作業的運行時間短。而在作業未投入運行時，並不能知道它實際的運行時間的長短，因此需要用戶在提交作業時同時提交作業運行時間的估計值。

3.最高響應比優先演算法(HRN)：FCFS可能造成短作業用戶不滿，SPF可能使得長作業用戶不滿，於是提出HRN，選擇響應比最高的作業運行。響應比=1+作業等待時間/作業處理時間。

4. 基於優先數調度演算法(HPF)：每一個作業規定一個表示該作業優先順序別的整數，當需要將新的作業由輸入井調入內存處理時，優先選擇優先數最高的作業。

5.均衡調度演算法，即多級隊列調度演算法

基本概念：

  作業周轉時間（Ti）＝完成時間(Tei)－提交時間(Tsi)

  作業平均周轉時間(T)＝周轉時間/作業個數

  作業帶權周轉時間（Wi）＝周轉時間/運行時間

  響應比＝（等待時間＋運行時間）/運行時間

二、進程調度演算法

1.先進先出演算法(FIFO)：按照進程進入就緒隊列的先後次序來選擇。即每當進入進程調度，總是把就緒隊列的隊首進程投入運行。

2. 時間片輪轉演算法(RR)：分時系統的一種調度演算法。輪轉的基本思想是，將CPU的處理時間劃分成一個個的時間片，就緒隊列中的進程輪流運行一個時間片。當時間片結束時，就強迫進程讓出CPU，該進程進入就緒隊列，等待下一次調度，同時，進程調度又去選擇就緒隊列中的一個進程，分配給它一個時間片，以投入運行。

3. 最高優先順序演算法(HPF)：進程調度每次將處理機分配給具有最高優先順序的就緒進程。最高優先順序演算法可與不同的CPU方式結合形成可搶占式最高優先順序演算法和不可搶占式最高優先順序演算法。

4. 多級隊列反饋法：幾種調度演算法的結合形式多級隊列方式。

三、空閑分區分配演算法

\1. 首先適應演算法：當接到內存申請時，查找分區說明表，找到第一個滿足申請長度的空閑區，將其分割並分配。此演算法簡單，可以快速做出分配決定。

2. 最佳適應演算法：當接到內存申請時，查找分區說明表，找到第一個能滿足申請長度的最小空閑區，將其進行分割並分配。此演算法最節約空間，因為它盡量不分割到大的空閑區，其缺點是可能會形成很多很小的空閑分區，稱為「碎片」。

3. 最壞適應演算法：當接到內存申請時，查找分區說明表，找到能滿足申請要求的最大的空閑區。該演算法的優點是避免形成碎片，而缺點是分割了大的空閑區後，在遇到較大的程序申請內存時，無法滿足的可能性較大。

四、虛擬頁式存儲管理中的頁面置換演算法

1.理想頁面置換演算法(OPT)：這是一種理想的演算法，在實際中不可能實現。該演算法的思想是：發生缺頁時，選擇以後永不使用或在最長時間內不再被訪問的內存頁面予以淘汰。

2.先進先出頁面置換演算法(FIFO)：選擇最先進入內存的頁面予以淘汰。

3. 最近最久未使用演算法（LRU）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。

4.最少使用演算法（LFU）：選擇到當前時間為止被訪問次數最少的頁轉換。

三、磁碟調度

1.先來先服務（FCFS）：是按請求訪問者的先後次序啟動磁碟驅動器，而不考慮它們要訪問的物理位置

2.最短尋道時間優先（SSTF）：讓離當前磁軌最近的請求訪問者啟動磁碟驅動器，即是讓查找時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務調度演算法中磁臂移動過大的問題

3.掃描演算法（SCAN）或電梯調度演算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調度方法下磁臂的移動類似於電梯的調度，所以它也稱為電梯調度演算法。

4.循環掃描演算法（CSCAN）：循環掃描調度演算法是在掃描演算法的基礎上改進的。磁臂改為單項移動，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。

對一個進程來說,一個重要的指標是它執行所需要的時間. 從進程提交到進程完成的時間間隔為周轉時間.也就是等待進入內存的時間,在就緒隊列中等待的時間,在 CPU中執行的時間和I/O操作的時間的總和.

例1.設一個系統中有5個進程，它們的到達時間和服務時間如下，A的到達時間為0，服務時間為3；B的到達時間為2，服務時間為6；C的到達時間為4，服務時間為4；D的到達時間為6，服務時間為5；E的 到達時間為8，服務時間為2，忽略1/0以及其他開銷時間，若分別按先來先服務（fFCFS）進行CPU調度，其平均周轉時間為？

10.2

6.4

8.6

4.5

先來先服務調度演算法

進程名  到達時間 服務時間  開始執行時間  完成時間  周轉時間

A              0              3                0                3                3

B              2              6                3                9                7

C              4              4                9                13              9

D              6              5                13              18              12

E              8              2                18              20              12

周轉時間 = 完成時間 - 到達時間

平均周轉時間 = 所有進程周轉時間 / 進程數 = （3+7+9+12+12）/ 5 = 8.6

單道批處理系統中有4個作業，J1的提交時間8.0，運行時間為2.0；J2的提交時間8.6，運行時間為0.6；J3提交時間8.8，運行時間為0.2；J4的提交時間9.0，運行時間為0.5。在採用響應比高者優先調度演算法時，其平均周轉時間為T為（）小時？

2.5

1.8

1.975

2.675

周轉時間=作業完成時間-作業提交時間

響應比=（作業等待時間+作業執行時間）/作業執行時間

當提交J1時，只有J1作業，執行J1，J1的周轉時間為2，此時時間為10.

J2、J3、J4提交時，由於正在執行J1，因此等待。

當J1執行完畢（此時時間為10），J2、J3、J4的等待時間分別為：1.4,1.2,1，

其響應比分別為：1.4/0.6+1=3.33    1.2/0.2+1=7      1/0.5+1=3，因此執行J3，J3的周轉時間為1.2+0.2=1.4

當J3執行完畢（此時時間為10.2），J2和J4的等待時間分別為1.6,1.2，

其響應比分別為：1.6/0.6+1=3.66      1.2/0.5+1=3.4，因此執行J2，J2的周轉時間為1.6+0.6=2.2

執行J2完畢後時間為10.8，接下來執行J4，執行完後時時間為11.3，J4的周轉時間為2.3

於是平均周轉時間為（2+1.4+2.2+2.3）/4=1.975

如果系統作業幾乎同時到達，則使系統平均作業周轉時間最短的演算法是短作業優先。

例3、

現有4個同時到達的作業J1,J2,J3和J4,它們的執行時間分別是3小時,5小時,7小時,9小時系統按單道方式運行且採用短作業優先演算法,則平均周轉時間是()小時

12.5

24

19

6

作業到達時間執行時間開始時間完成時間周轉時間

J103033

J20 5388

J30781515

J409152424

平均周轉時間（3+8+15+24）/4=12.5 

有4個進程A,B,C,D,設它們依次進入就緒隊列，因相差時間很短可視為同時到達。4個進程按輪轉法分別運行11,7,2,和4個時間單位，設時間片為1。四個進程的平均周轉時間為 （）？

15.25

16.25

16.75

17.25

17.75

18.25

A:1  4  4  3  3  2  2  2  1  1  1  共24

B:2  4  4  3  3  2  2                  共20

C:3  4                                      共7

D:4  4  3  3                              共14

字母後面的數字為等待的時間加運行時間

平均周轉時間為（24+20+7+14）/4=16.25

例5、假設系統按單值方式運行且採用最短作業優先演算法，有J1,J2,J3,J4共4個作業同時到達，則以下哪幾種情況下的平均周轉時間為10分鍾?

執行時間J1:1分鍾 J2:5分鍾 J3:9分鍾 J4:13分鍾

執行時間J1:1分鍾 J2:4分鍾 J3:7分鍾 J4:10分鍾

執行時間J1:2分鍾 J2:4分鍾 J3:6分鍾 J4:8分鍾

執行時間J1:3分鍾 J2:6分鍾 J3:9分鍾 J4:12分鍾

首先，短作業優先則短時間的作業利用資源，其餘的作業等待

根據平均周轉時間概念，將所有作業"等待時間"加上"運行時間"除以"作業數量"即可得到平均周轉時間

A： (J1執行1分鍾 + J2等待1分鍾 + J2執行5分鍾 + J3等待6分鍾 + J3執行9分鍾 + J4等待15分鍾 + J4執行13分鍾) / 4  = 50/4 = 12.5

B：  (J1執行1分鍾 + J2等待1分鍾 + J2執行4分鍾 + J3等待5分鍾 + J3執行7分鍾 + J4等待12分鍾 + J4執行10分鍾) / 4  = 40/4 = 10

C： (J1執行2分鍾 + J2等待2分鍾 + J2執行4分鍾 + J3等待6分鍾 + J3執行6分鍾 + J4等待12分鍾 + J4執行8分鍾) / 4    = 40/4 = 10

D：  (J1執行3分鍾 + J2等待3分鍾 + J2執行6分鍾 + J3等待9分鍾 + J3執行9分鍾 + J4等待18分鍾 + J4執行12分鍾) / 4  = 50/4 = 12.5

例6、假設系統中有5個進程，它們的到達時間和服務時間見下表1，忽略I/O以及其他開銷時間，若按先來先服務（FCFS）、非搶占的短作業優先和搶占的短作業優先三種調度演算法進行CPU調度，請給出各個進程的完成時間、周轉時間、帶權周轉時間、平均周轉時間和平均帶權周轉時間，完成表2。  表1 進程到達和需要服務時間  進程    到達時間    服務時間  A          0            3  B          2            6  C          4            4  D          6            5  E          8            2

表2 進程的完成時間和周轉時間

                  進程                  A      B        C      D      E        平均

  FCFS          完成時間      3      9      13      18      20 

                周轉時間            3      7        9      12      12      8.6

            帶權周轉時間      1.00 1.17  2.25  2.40    6.00      2.56

  SPF(非搶占)  完成時間    3      9      15      20      11 

                周轉時間            3      7      11      14      3        7.6

            帶權周轉時間      1.00  1.17  1.75    2.80    1.50    1.84

  SPF(搶占)    完成時間    3      15      8      20      10 

                周轉時間            3      13      4      14      2        7.2

            帶權周轉時間      1.00  2.16  1.00  2.80  1.00    1.59

例7、假定在單道批處理環境下有5個作業，各作業進入系統的時間和估計運行時間如下表所示：    作業  進入系統時間    估計運行時間/分鍾      1            8:00                40      2            8:20                30      3            8:30                12      4            9:00                18

      5            9:10                5

如果應用先來先服務和應用最短作業優先的作業調度演算法，試將下面表格填寫完整。

(1) 如果應用先來先服務的作業調度演算法，試將下面表格填寫完整。

    作業  進入系統時間  估計運行時間/分鍾  開始時間  結束時間  周轉時間/分鍾

    1        8:00            40            8：00    8：40        40

    2        8:20            30            8：40    9：10        50

    3        8:30            12            9：10    9：22        52

    4        9:00            18            9：22    9：40        40

    5        9:10            5              9：40    9：45        35

作業平均周轉時間T= 43.4  217

2）如果應用最短作業優先的作業調度演算法，試將下面表格填寫完整。    作業  進入系統時間  估計運行時間/分鍾  開始時間  結束時間  周轉時間/分鍾    1        8:00            40              8：00    8：40          40    2        8:20            30              8：52    9：22          62    3        8:30            12              8：40    8：52          22    4        9:00            18              9：27    9：45          45    5        9:10            5              9：22    9：27          17作業平均周轉時間T= 37.2  186

CPU和兩台輸入/輸出設備(I1,I2)多道程序設計環境下,同時有三個作業J1,J2,J3進行,這三個作業

使用CPU和輸入/輸出設備的順序和時間如下所示:

J1:I2(35ms);CPU(15ms);I1(35ms);CPU(15ms);I2(25ms)

J2:I1(25ms);CPU(30ms);I2(35ms)

J3:CPU(30ms);I1(25ms);CPU(15ms);I1(15ms);

假定CPU,I1,I2都能並行工作,J1的優先順序最高,J2次之,J3優先順序最低,優先順序高的作業可以搶占優先順序低的作業的CPU,但不能搶佔I1,I2,作業從J3開始到完成需要多少時間?

❸ 目前常用的磁碟調度演算法有哪幾種每種演算法優先考慮的問題是什麼

(1)先來先服務(FCFS，First-Come First-Served)
此演算法根據進程請求訪問磁碟的先後次序進行調度。
(2)最短尋道時間優先(SSTF ，ShortestSeekTimeFirst)
該演算法選擇這樣的進程，其要求訪問的磁軌與當前磁頭所在的磁軌距離最近，以使每次的尋道時間最短，但這種調度演算法卻不能保證平均尋道時間最短。
(3)掃描(SCAN)演算法
SCAN演算法不僅考慮到欲訪問的磁軌與當前磁軌的距離，更優先考慮的是磁頭的當前移動方向。
(4)循環掃描(CSCAN)演算法
CSCAN演算法規定磁頭單向移動，避免了掃描演算法導致的某些進程磁碟請求的嚴重延遲。
(5) N-Step-SCAN和FSCAN調度演算法
1) N-Step-SCAN演算法。為克服前述SSTF、SCAN、CSCAN等調度演算法都可能出現的磁臂停留在某處不動的情況即磁臂粘著現象，將磁碟請求隊列分成若干個長度為N的子隊列，按先來先服務演算法依次處理這些子隊列，而各隊列分別以掃描演算法進行處理。
2) FSCAN演算法
FSCAN演算法實質上是N步SCAN演算法的簡化。它只將磁碟請求訪問隊列分成兩個子隊列。一是當前所有請求磁碟I/O的進程形成的隊列，由磁碟調度按SCAN演算法進行處理。另一個隊列則是在 掃描期間，新出現的所有請求磁碟I/O進程的隊列，放入另一等待處理的請求隊列。這樣，所有的新請求都將被推遲到下一次掃描時處理。

❹ 操作系統的主要演算法都有哪些

一、進程(作業)調度演算法
l 先來先服務調度演算法（FCFS）：每次調度是從就緒隊列中，選擇一個最先進入就緒隊列的進程，把處理器分配給該進程，使之得到執行。該進程一旦佔有了處理器，它就一直運行下去，直到該進程完成或因發生事件而阻塞，才退出處理器。特點：利於長進程，而不利於短進程。

l 短進程（作業）優先調度演算法(SPF)：它是從就緒隊列中選擇一個估計運行時間最短的進程，將處理器分配給該進程，使之佔有處理器並執行，直到該進程完成或因發生事件而阻塞，然後退出處理器，再重新調度。

l 時間片輪轉調度演算法 ：系統將所有的就緒進程按進入就緒隊列的先後次序排列。每次調度時把CPU分配給隊首進程，讓其執行一個時間片，當時間片用完，由計時器發出時鍾中斷，調度程序則暫停該進程的執行，使其退出處理器，並將它送到就緒隊列的末尾，等待下一輪調度執行。

l 優先數調度演算法 ：它是從就緒隊列中選擇一個優先權最高的進程，讓其獲得處理器並執行。

l 響應比高者優先調度演算法：它是從就緒隊列中選擇一個響應比最高的進程，讓其獲得處理器執行，直到該進程完成或因等待事件而退出處理器為止。特點：既照顧了短進程，又考慮了進程到達的先後次序，也不會使長進程長期得不到服務，因此是一個比較全面考慮的演算法，但每次進行調度時，都需要對各個進程計算響應比。所以系統開銷很大，比較復雜。

l 多級隊列調度演算法

基本概念：

作業周轉時間（Ti）＝完成時間(Tei)－提交時間(Tsi)

作業平均周轉時間(T)＝周轉時間/作業個數

作業帶權周轉時間（Wi）＝周轉時間/運行時間

響應比＝（等待時間＋運行時間）/運行時間

二、存儲器連續分配方式中分區分配演算法
n 首次適應分配演算法（FF）：對空閑分區表記錄的要求是按地址遞增的順序排列的，每次分配時，總是從第1條記錄開始順序查找空閑分區表，找到第一個能滿足作業長度要求的空閑區，分割這個空閑區，一部分分配給作業，另一部分仍為空閑區。

n 循環首次適應演算法：每次分配均從上次分配的位置之後開始查找。

n 最佳適應分配演算法(BF)：是按作業要求從所有的空閑分區中挑選一個能滿足作業要求的最小空閑區，這樣可保證不去分割一個更大的區域，使裝入大作業時比較容易得到滿足。為實現這種演算法，把空閑區按長度遞增次序登記在空閑區表中，分配時，順序查找。

三、頁面置換演算法
l 最佳置換演算法（OPT) ：選擇以後永不使用或在最長時間內不再被訪問的內存頁面予以淘汰。

l 先進先出置換演算法（FIFO）：選擇最先進入內存的頁面予以淘汰。

l 最近最久未使用演算法（LRU）：選擇在最近一段時間內最久沒有使用過的頁，把它淘汰。

l 最少使用演算法（LFU）：選擇到當前時間為止被訪問次數最少的頁轉換。

四、磁碟調度
n 先來先服務（FCFS）：是按請求訪問者的先後次序啟動磁碟驅動器，而不考慮它們要訪問的物理位置

n 最短尋道時間優先（SSTF）：讓離當前磁軌最近的請求訪問者啟動磁碟驅動器，即是讓查找時間最短的那個作業先執行，而不考慮請求訪問者到來的先後次序，這樣就克服了先來先服務調度演算法中磁臂移動過大的問題

n 掃描演算法（SCAN）或電梯調度演算法：總是從磁臂當前位置開始，沿磁臂的移動方向去選擇離當前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調度方法下磁臂的移動類似於電梯的調度，所以它也稱為電梯調度演算法。

n 循環掃描演算法（CSCAN）：循環掃描調度演算法是在掃描演算法的基礎上改進的。磁臂改為單項移動，由外向里。當前位置開始沿磁臂的移動方向去選擇離當前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業請求。

❺ 電梯演算法是怎樣的

電梯演算法是通過操作系統學術名為SCAN演算法。磁臂僅移動到請求的最外道就回轉。反方向查找服務。

如果請求調度的磁軌為98, 183, 37, 122, 14, 124, 65, 67，磁頭從53號磁軌開始移動，磁頭就會按照65, 67, 98, 122, 124, 183, 37,14 的順序依次查找，並將數據輸入內存。

電梯（升降盒）上下來回地運動，電梯內部有一些按鈕，每一個按鈕代表一層樓，當按下按鈕時，按鈕的燈亮。

電梯沿某一方向運動，在將要到達某一層樓時，實時監控器 判斷電梯內是否有乘客要在此層樓下電梯，若有，則發送信號給電梯升降架。

電梯是指服務於建築物內若干特定的樓層，其轎廂運行在至少兩列垂直於水平面或與鉛垂線傾斜角小於15°的剛性軌道運動的永久運輸設備。

也有台階式，踏步板裝在履帶上連續運行，俗稱自動扶梯或自動人行道。服務於規定樓層的固定式升降設備。垂直升降電梯具有一個轎廂，運行在至少兩列垂直的或傾斜角小於15°的剛性導軌之間。

轎廂尺寸與結構形式便於乘客出入或裝卸貨物。習慣上不論其驅動方式如何，將電梯作為建築物內垂直交通運輸工具的總稱。