掃描調度演算法

A. 莫系統空閑分區如下表.哪種演算法可滿足該作業序列請求為什麼

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

B. 磁碟調度演算法中的~掃描演算法~還有~循環掃描演算法~，需要移動到0磁軌再返回碼麻煩高手指點，學校發的破書寫

總是按一個方向移動磁碟臂（向0反方向移動），處理完編號最高的磁軌後，移動到具有讀寫請求的編號最低的磁軌，然後繼續向上移動。

這里你反過來理解就好了，就是從高到低

這里先訪問168，然後是140,117，小於117的磁軌已經沒有請求了，此時磁碟臂應該回到288，然後向0方向移動

C. I/O與磁碟調度是什麼

外部設備分類
（1）按系統和用戶分：系統設備、用戶設備
（2）按輸入輸出傳送方式分（UNIX或Linux操作系統）：字元型設備、塊設備
（3）按資源特點分：獨享設備、共享設備、虛擬設備
（4）按設備硬體物理特性分：順序存取設備、直接存取設備
（5）按設備使用分：物理設備、邏輯設備、偽設備
（6）按數據組織分：塊設備、字元設備
（7）按數據傳輸率分：低速設備、中速設備、高速設備
設備管理的目標與任務
設備管理的目標：
（1）按用戶需求提出的要求接入外部設備，系統按一定演算法分配和管理控制，而用戶不必關心設備的實際地址和控制指令；
（2）盡量提高輸入輸出設備的利用率，例如發揮主機與外設以及外設與外設之間的真正並行工作能力。主要利用的技術有：中斷技術、DMA技術、通道技術、緩沖技術。
設備管理的任務：
（1）動態掌握並記錄設備的狀態
（2）分配設備和釋放
（3）對輸入輸出緩沖區進行管理
（4）控制和實現真正的輸入輸出操作
（5）提供設備使用的用戶介面
（6）在一些較大系統中實現虛擬設備技術
通道（channel）：計算機系統中能夠獨立完成輸入輸出操作的硬體裝置，也稱為「輸入輸出處理機」。
雖然在CPU與I/O設備之間增加了設備控制器，但CPU的負擔仍很重。為此，在CPU和設備控制器之間又增設了I/O通道。其目的是使一些原來由CPU處理的I/O任務轉由通道來承擔，從而把CPU從繁雜的I/O任務中解脫出來。
CPU並不直接操作外圍設備，他連接通道（I/O處理機），通道連接設備控制器，設備控制器連接設備。CPU只需把「I/O"設備啟動，並給出相關的操作要求。然後就由通道來處理輸入輸出事宜，做完後報告CPU。
根據信息交換方式的不同，可把通道分成以下三種類型：
位元組多路通道(Byte Multiplexor Channal)
數組選擇通道(Block Selector Channal)
數組多路通道(Block Multiplexor Channal)
中斷技術
中斷(Interrupt)是指計算機在執行期間，系統內發生非尋常的或非預期的急需處理事件，使得CPU暫時中斷當前正在執行的程序而轉去執行響應的事件處理程序。待處理完畢後又返回原來中斷處繼續執行或調度新的程序執行的過程。中斷一般可分成軟體中斷和硬體中斷。
中斷方式（interrupt）被用來控制外圍設備和內存與CPU之間的數據傳送。這種方式要求CPU與設備（或控制器）之間有相應的中斷請求線，而且在設備控制器的控制狀態寄存器的相應的中斷允許位。
1．數據輸入操作步驟：
l進程需要數據時，通過CPU發出「start」指令啟動外圍設備准備數據
l在進程發出指令啟動設備後，該進程放棄處理機，等待輸入完成。
l當輸入完成時，I/O控制器通過中斷請求線向CPU發出中斷請求。
l在以後的某個時刻，進程調度程序選中提出請求並得到數據的進程，該進程從約定的內存特定單元中取出數據繼續工作。
2．中斷方式的缺點：
1）由於在一次數據傳送過程中，發生中斷次數較多。這將耗去大量CPU處理時間。
2）當設備把數據放入數據緩沖寄存器並發出中斷信號之後，CPU有足夠的時間在下一個（組）數據進入數據緩沖寄存器之前取走數據。如果外設的速度也非常快，則有可能造成數據緩沖寄存器的數據丟失。
DMA技術
DMA 是Direct Memory Access的縮寫，其意思是「存儲器直接訪問」。它是指一種高速的數據傳輸操作，允許在外部設備和存儲器之間直接讀寫數據，即不通過CPU，也不需要 CPU干預。整個數據傳輸操作在一個稱為「DMA控制器」的控制下進行的。CPU除了在數據傳輸開始和結束時作一點處理外，在傳輸過程中CPU可以進行其它的工作。這樣，在大部分時間里，CPU和輸入輸出都處在並行操作。因此，使整個計算機系統的效率大大提高。
緩沖技術
緩沖指用來暫存數據的緩沖存儲器。
緩沖技術是二種不同速度的設備之間傳輸信息時平滑傳輸過程的一種常用手段。它可提高外設利用率，盡可能使外設處於忙狀態。引入緩沖的主要原因，可歸結為以下幾點：
1. 改善CPU與I/O設備間速度不匹配的矛盾
2. 可以減少對 CPU的中斷頻率，放寬對中斷響應時間的限制
3. 提高 CPU和 I／O設備之間的並行性
根據I/O控制方式，緩沖的實現方法有兩種：一種是採用專用硬體緩沖器；另一種是在內存劃出一個具有n個單元的專用緩沖區，以便存放輸入/輸出的數據。內存緩沖區又稱軟體緩沖。
根據系統設置的緩沖器的個數，可把緩沖技術分為：單緩沖、雙緩沖、多緩沖和緩沖池
假離線技術（SPOOLing）
SPOOLing，即外圍設備聯機並行操作，它是一種速度匹配技術、也是一種虛擬設備技術（用一種物理設備模擬另一類物理設備，使各作業在執行期間只使用虛擬的設備而不直接使用物理的獨占設備。這種技術可使獨占的設備變成可共享的設備，使得設備的利用率和系統效率都能得到提高）。
1．SPOOL系統的組成
SPOOLing系統主要有以下三部分組成：
（1）輸入井和輸出井
它們是在磁碟上開辟的兩個大緩沖區。輸入井是模擬離線輸入時的磁碟，用於收容I/O設備輸入的數據；輸出井是模擬離線輸出時的磁碟，用於收容用戶程序的輸出數據。
（2）輸入緩沖區和輸出緩沖區
在內存中要開辟兩個緩沖區，其中輸入緩沖區用於暫存由輸入設備送來的數據，以後再傳送到輸入井；輸出緩沖區用於暫存從輸出井送來的數據，以後再傳送給輸出設備。
（3）輸入進程SPi和輸出進程Spo
進程Spi模擬離線輸入時的外圍控制機，將用戶要求的數據從輸入機通過輸入緩沖區再送到輸入井。當CPU需要輸入數據時，直接從輸入井讀入內存。Spo進程模擬離線輸出時的外圍控制機，把用戶要求輸出的數據先從內存送到輸出井，待輸出設備空閑時，再將輸出井中的數據經過輸出緩沖區送到輸出設備上。
2、實現虛擬設備的條件
硬體條件：大容量磁碟；中斷裝置和通道；中央處理器與通道並行工作的能力。
軟體條件：要求操作系統採用多道程序設計技術。
3、虛擬設備的實現原理
對於多道程序，輸入時將一批作業的信息通過輸入設備預先傳送到磁碟上。輸出時將作業產生的結果也全部暫時存在磁碟上而不直接輸出，直到一個作業得到全部結果而執行結束時再行輸出。（就是用磁碟來模擬輸入機和列印機的工作，把它們的工作內容先保存起來，然後一並執行）
磁碟調度
對磁碟進行驅動調度的目的：盡可能的降低多個訪問者執行輸入輸出操作的總時間，增加單位時間內的輸入輸出操作次數，有利於系統效率的提高。
磁碟的驅動調度：在多道程序設計系統中，同時有多個訪問者請求磁碟操作，此時系統採用一定的調度策略來決定各等待訪問者的執行次序，所以系統決定等待磁碟訪問者的執行次序的工作就是磁碟的「驅動調度」。
磁碟調度分為移臂調度和旋轉調度。
根據訪問者指定的柱面位置來決定執行次序的調度稱「移臂調度」；
當移動臂定位後，如有多個訪問者等待訪問該柱面時，根據延遲時間來決定執行次序的調度稱為「旋轉調度」。
移臂調度演算法包括以下四種：
1）先來先服務演算法(FCFS)；
2）最短尋找時間優先調度演算法(SSTF)；
3）電梯調度演算法(SCAN)；
4）單向掃描調度演算法(CSCAN)。

D. 高手給解釋下，操作系統中的，電梯調度演算法和掃描調度演算法的區別到底是什麼最好舉例圖

操作系統概念那本書上有圖，電梯就是磁頭一直向左然後一直向右這么來來回回。CSCAN就是磁頭一直向左，然後再回到右邊開始一直向左，類似於示波器的逐行掃描。

E. 關於《操作系統》中的磁碟調度演算法

（1）先來先服務調度演算法
由於該演算法就是按照磁軌請求序列的先後次序依次訪問磁軌的，因此磁軌的訪問序列（服務順序）就是：
110、180、32、115、15、120、60、70。
當前磁頭在50號磁軌。故磁頭移動道數為：
（110-50）+（180-110）+（180-32）+（115-32）+（115-15）+（120-15）+（120-60）+（70-60）=60+70+148+83+100+105+60+10=636
（2）單向掃描調度演算法
該演算法是沿磁頭移動方向訪問距離當前磁軌最近的磁軌，當到達一個頂端時立刻返回到另一個頂端繼續掃描。本題磁頭移動方向是磁軌增加的方向，當前磁頭在50號磁軌。因此磁軌的訪問序列（服務順序）就是：60、70、110、115、120、180、15、32。而磁頭移動道數與前面（1）問差不多，也是兩兩相減，然後求和。在此略

F. 最短尋道時間優先演算法與掃描演算法有什麼異同

最短進程優先演算法是一種非剝奪式演算法,總是選取預計作業時間最短的作業優先運行；最短剩餘時間優先演算法是非剝奪式的,但可以改造成剝奪式的調度演算法,稱搶占式最短作業優先演算法.
至於二者的平均周轉時間,比如有四個進程P1,P2,P3,P4,分別在0,1,2,3時刻到達,所需時間分別為7,5,3,8；那麼其平均周轉時間為（（15-0）+（9-1）+（5-2）+（23-15））/4=8.5；
最短進程優先的比較簡單了,就不寫出來了,不會的話再追問吧.

G. 常見的磁碟調度演算法有哪些，有什麼優缺點

1.先來先服務（FCFS）
2.最短尋道時間優先（SSTF）
3.掃描（scan）演算法
4循環掃描（CSCAN）演算法
5.NStep和FSCAN調度演算法

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

(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進程的隊列，放入另一等待處理的請求隊列。這樣，所有的新請求都將被推遲到下一次掃描時處理。

I. 磁碟調度演算法用來改善磁頭的性能對不對

對的，磁碟是計算機系統中最重要的存儲設備，其中含有絕大部分文件。對文件的操作直接涉及到磁碟的訪問，磁碟IO的速度效率和可靠性將直接影響系統的性能。因此，好的磁碟調度演算法、優越的冗餘技術，都是提高磁碟系統性能的切入點。
磁碟調度演算法

1.先來先服務：按照進程訪問磁碟的先後順序進行調度。

優點：公平、簡單

缺點：效率低，平均尋道時間較長

2.最短尋道時間優先：要求訪問磁軌與當前磁頭的磁軌距離最近。

優點：相比於先來先服務，明顯減少平均尋道長度

缺點：磁頭可能在一個小的范圍內一直尋到，造成遠處請求不滿足而飢餓

3.掃描演算法：又稱電梯調度演算法，像電梯一樣上下連續來回尋道

優點：避免了「飢餓」現象

缺點：對於剛剛經過的磁軌又來了新的請求，再次訪問要最多等2個磁軌長度

4.循環掃描演算法：磁頭單向移動，其餘和掃描演算法一樣

優點：解決了可能的錯過型請求的雙倍延遲

缺點：浪費一個磁頭的移動次數，什麼都沒做

5.NStepSCAN演算法：磁碟請求分成N個隊列，隊列間用先來先服務處理，隊列內用掃描演算法處理

優點：避免新請求帶來的粘著問題

缺點：N值很大時，接近於掃描演算法；N=1時，就是先來先服務

6.FSCAN演算法：磁碟請求只分成兩個隊列，一個是當前請求隊列，一個是未來請求隊列，當前隊列按照掃描演算法處理，當前隊列處理完就處理另一個，此時另一個為當前隊列，已經處理完的是未來請求隊列

優點：簡化NStepSCAN演算法

缺點：所有新來的請求都在下次掃描時再處理，對於緊急的高優先順序的請求也要放到下次