偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

大廠面試愛問的「調(diào)度算法」,20 張圖一舉拿下

系統(tǒng) 算法
最近,我偷偷潛伏在各大技術(shù)群,因為秋招在即,看到不少小伙伴分享的大廠面經(jīng)。然后發(fā)現(xiàn),操作系統(tǒng)的知識點考察還是比較多的,大廠就是大廠就愛問基礎(chǔ)知識。其中,關(guān)于操作系統(tǒng)的「調(diào)度算法」考察也算比較頻繁。

[[341122]]

本文轉(zhuǎn)載自微信公眾號「小林coding」,作者小林coding 。轉(zhuǎn)載本文請聯(lián)系小林coding公眾號。  

 

原文地址:https://mp.weixin.qq.com/s/JWj6_BF9Xc84kQcyx6Nf_g

 前言

最近,我偷偷潛伏在各大技術(shù)群,因為秋招在即,看到不少小伙伴分享的大廠面經(jīng)。

然后發(fā)現(xiàn),操作系統(tǒng)的知識點考察還是比較多的,大廠就是大廠就愛問基礎(chǔ)知識。其中,關(guān)于操作系統(tǒng)的「調(diào)度算法」考察也算比較頻繁。

所以,我這邊總結(jié)了操作系統(tǒng)的三大調(diào)度機(jī)制,分別是「進(jìn)程調(diào)度/頁面置換/磁盤調(diào)度算法」,供大家復(fù)習(xí),希望大家在秋招能斬獲自己心意的 offer。

 

 

正文

進(jìn)程調(diào)度算法

進(jìn)程調(diào)度算法也稱 CPU 調(diào)度算法,畢竟進(jìn)程是由 CPU 調(diào)度的。

當(dāng) CPU 空閑時,操作系統(tǒng)就選擇內(nèi)存中的某個「就緒狀態(tài)」的進(jìn)程,并給其分配 CPU。

什么時候會發(fā)生 CPU 調(diào)度呢?通常有以下情況:

  1. 當(dāng)進(jìn)程從運行狀態(tài)轉(zhuǎn)到等待狀態(tài);
  2. 當(dāng)進(jìn)程從運行狀態(tài)轉(zhuǎn)到就緒狀態(tài);
  3. 當(dāng)進(jìn)程從等待狀態(tài)轉(zhuǎn)到就緒狀態(tài);
  4. 當(dāng)進(jìn)程從運行狀態(tài)轉(zhuǎn)到終止?fàn)顟B(tài);

其中發(fā)生在 1 和 4 兩種情況下的調(diào)度稱為「非搶占式調(diào)度」,2 和 3 兩種情況下發(fā)生的調(diào)度稱為「搶占式調(diào)度」。

非搶占式的意思就是,當(dāng)進(jìn)程正在運行時,它就會一直運行,直到該進(jìn)程完成或發(fā)生某個事件而被阻塞時,才會把 CPU 讓給其他進(jìn)程。

而搶占式調(diào)度,顧名思義就是進(jìn)程正在運行的時,可以被打斷,使其把 CPU 讓給其他進(jìn)程。那搶占的原則一般有三種,分別是時間片原則、優(yōu)先權(quán)原則、短作業(yè)優(yōu)先原則。

你可能會好奇為什么第 3 種情況也會發(fā)生 CPU 調(diào)度呢?假設(shè)有一個進(jìn)程是處于等待狀態(tài)的,但是它的優(yōu)先級比較高,如果該進(jìn)程等待的事件發(fā)生了,它就會轉(zhuǎn)到就緒狀態(tài),一旦它轉(zhuǎn)到就緒狀態(tài),如果我們的調(diào)度算法是以優(yōu)先級來進(jìn)行調(diào)度的,那么它就會立馬搶占正在運行的進(jìn)程,所以這個時候就會發(fā)生 CPU 調(diào)度。

那第 2 種狀態(tài)通常是時間片到的情況,因為時間片到了就會發(fā)生中斷,于是就會搶占正在運行的進(jìn)程,從而占用 CPU。

調(diào)度算法影響的是等待時間(進(jìn)程在就緒隊列中等待調(diào)度的時間總和),而不能影響進(jìn)程真在使用 CPU 的時間和 I/O 時間。

接下來,說說常見的調(diào)度算法:

  • 先來先服務(wù)調(diào)度算法
  • 最短作業(yè)優(yōu)先調(diào)度算法
  • 高響應(yīng)比優(yōu)先調(diào)度算法
  • 時間片輪轉(zhuǎn)調(diào)度算法
  • 最高優(yōu)先級調(diào)度算法
  • 多級反饋隊列調(diào)度算法

先來先服務(wù)調(diào)度算法

最簡單的一個調(diào)度算法,就是非搶占式的先來先服務(wù)(First Come First Severd, FCFS)算法了。

FCFS 調(diào)度算法

 顧名思義,先來后到,每次從就緒隊列選擇最先進(jìn)入隊列的進(jìn)程,然后一直運行,直到進(jìn)程退出或被阻塞,才會繼續(xù)從隊列中選擇第一個進(jìn)程接著運行。

這似乎很公平,但是當(dāng)一個長作業(yè)先運行了,那么后面的短作業(yè)等待的時間就會很長,不利于短作業(yè)。

FCFS 對長作業(yè)有利,適用于 CPU 繁忙型作業(yè)的系統(tǒng),而不適用于 I/O 繁忙型作業(yè)的系統(tǒng)。

最短作業(yè)優(yōu)先調(diào)度算法

最短作業(yè)優(yōu)先(Shortest Job First, SJF)調(diào)度算法同樣也是顧名思義,它會優(yōu)先選擇運行時間最短的進(jìn)程來運行,這有助于提高系統(tǒng)的吞吐量。

SJF 調(diào)度算法

這顯然對長作業(yè)不利,很容易造成一種極端現(xiàn)象。

比如,一個長作業(yè)在就緒隊列等待運行,而這個就緒隊列有非常多的短作業(yè),那么就會使得長作業(yè)不斷的往后推,周轉(zhuǎn)時間變長,致使長作業(yè)長期不會被運行。

高響應(yīng)比優(yōu)先調(diào)度算法

前面的「先來先服務(wù)調(diào)度算法」和「最短作業(yè)優(yōu)先調(diào)度算法」都沒有很好的權(quán)衡短作業(yè)和長作業(yè)。

那么,高響應(yīng)比優(yōu)先 (Highest Response Ratio Next, HRRN)調(diào)度算法主要是權(quán)衡了短作業(yè)和長作業(yè)。

每次進(jìn)行進(jìn)程調(diào)度時,先計算「響應(yīng)比優(yōu)先級」,然后把「響應(yīng)比優(yōu)先級」最高的進(jìn)程投入運行,「響應(yīng)比優(yōu)先級」的計算公式:

 

 

從上面的公式,可以發(fā)現(xiàn):

  • 如果兩個進(jìn)程的「等待時間」相同時,「要求的服務(wù)時間」越短,「響應(yīng)比」就越高,這樣短作業(yè)的進(jìn)程容易被選中運行;
  • 如果兩個進(jìn)程「要求的服務(wù)時間」相同時,「等待時間」越長,「響應(yīng)比」就越高,這就兼顧到了長作業(yè)進(jìn)程,因為進(jìn)程的響應(yīng)比可以隨時間等待的增加而提高,當(dāng)其等待時間足夠長時,其響應(yīng)比便可以升到很高,從而獲得運行的機(jī)會;

時間片輪轉(zhuǎn)調(diào)度算法

最古老、最簡單、最公平且使用最廣的算法就是時間片輪轉(zhuǎn)(Round Robin, RR)調(diào)度算法。

RR 調(diào)度算法

每個進(jìn)程被分配一個時間段,稱為時間片(Quantum),即允許該進(jìn)程在該時間段中運行。

  • 如果時間片用完,進(jìn)程還在運行,那么將會把此進(jìn)程從 CPU 釋放出來,并把 CPU 分配另外一個進(jìn)程;
  • 如果該進(jìn)程在時間片結(jié)束前阻塞或結(jié)束,則 CPU 立即進(jìn)行切換;

另外,時間片的長度就是一個很關(guān)鍵的點:

  • 如果時間片設(shè)得太短會導(dǎo)致過多的進(jìn)程上下文切換,降低了 CPU 效率;
  • 如果設(shè)得太長又可能引起對短作業(yè)進(jìn)程的響應(yīng)時間變長;

通常時間片設(shè)為 20ms~50ms 通常是一個比較合理的折中值。

最高優(yōu)先級調(diào)度算法

前面的「時間片輪轉(zhuǎn)算法」做了個假設(shè),即讓所有的進(jìn)程同等重要,也不偏袒誰,大家的運行時間都一樣。

但是,對于多用戶計算機(jī)系統(tǒng)就有不同的看法了,它們希望調(diào)度是有優(yōu)先級的,即希望調(diào)度程序能從就緒隊列中選擇最高優(yōu)先級的進(jìn)程進(jìn)行運行,這稱為最高優(yōu)先級(Highest Priority First,HPF)調(diào)度算法。

進(jìn)程的優(yōu)先級可以分為,靜態(tài)優(yōu)先級或動態(tài)優(yōu)先級:

  • 靜態(tài)優(yōu)先級:創(chuàng)建進(jìn)程時候,就已經(jīng)確定了優(yōu)先級了,然后整個運行時間優(yōu)先級都不會變化;
  • 動態(tài)優(yōu)先級:根據(jù)進(jìn)程的動態(tài)變化調(diào)整優(yōu)先級,比如如果進(jìn)程運行時間增加,則降低其優(yōu)先級,如果進(jìn)程等待時間(就緒隊列的等待時間)增加,則升高其優(yōu)先級,也就是隨著時間的推移增加等待進(jìn)程的優(yōu)先級。

該算法也有兩種處理優(yōu)先級高的方法,非搶占式和搶占式:

  • 非搶占式:當(dāng)就緒隊列中出現(xiàn)優(yōu)先級高的進(jìn)程,運行完當(dāng)前進(jìn)程,再選擇優(yōu)先級高的進(jìn)程。
  • 搶占式:當(dāng)就緒隊列中出現(xiàn)優(yōu)先級高的進(jìn)程,當(dāng)前進(jìn)程掛起,調(diào)度優(yōu)先級高的進(jìn)程運行。

但是依然有缺點,可能會導(dǎo)致低優(yōu)先級的進(jìn)程永遠(yuǎn)不會運行。

多級反饋隊列調(diào)度算法

多級反饋隊列(Multilevel Feedback Queue)調(diào)度算法是「時間片輪轉(zhuǎn)算法」和「最高優(yōu)先級算法」的綜合和發(fā)展。

顧名思義:

  • 「多級」表示有多個隊列,每個隊列優(yōu)先級從高到低,同時優(yōu)先級越高時間片越短。
  • 「反饋」表示如果有新的進(jìn)程加入優(yōu)先級高的隊列時,立刻停止當(dāng)前正在運行的進(jìn)程,轉(zhuǎn)而去運行優(yōu)先級高的隊列;

 

多級反饋隊列

來看看,它是如何工作的:

  • 設(shè)置了多個隊列,賦予每個隊列不同的優(yōu)先級,每個隊列優(yōu)先級從高到低,同時優(yōu)先級越高時間片越短;
  • 新的進(jìn)程會被放入到第一級隊列的末尾,按先來先服務(wù)的原則排隊等待被調(diào)度,如果在第一級隊列規(guī)定的時間片沒運行完成,則將其轉(zhuǎn)入到第二級隊列的末尾,以此類推,直至完成;
  • 當(dāng)較高優(yōu)先級的隊列為空,才調(diào)度較低優(yōu)先級的隊列中的進(jìn)程運行。如果進(jìn)程運行時,有新進(jìn)程進(jìn)入較高優(yōu)先級的隊列,則停止當(dāng)前運行的進(jìn)程并將其移入到原隊列末尾,接著讓較高優(yōu)先級的進(jìn)程運行;

可以發(fā)現(xiàn),對于短作業(yè)可能可以在第一級隊列很快被處理完。對于長作業(yè),如果在第一級隊列處理不完,可以移入下次隊列等待被執(zhí)行,雖然等待的時間變長了,但是運行時間也會更長了,所以該算法很好的兼顧了長短作業(yè),同時有較好的響應(yīng)時間。

內(nèi)存頁面置換算法

在了解內(nèi)存頁面置換算法前,我們得先談一下缺頁異常(缺頁中斷)。

當(dāng) CPU 訪問的頁面不在物理內(nèi)存時,便會產(chǎn)生一個缺頁中斷,請求操作系統(tǒng)將所缺頁調(diào)入到物理內(nèi)存。那它與一般中斷的主要區(qū)別在于:

  • 缺頁中斷在指令執(zhí)行「期間」產(chǎn)生和處理中斷信號,而一般中斷在一條指令執(zhí)行「完成」后檢查和處理中斷信號。
  • 缺頁中斷返回到該指令的開始重新執(zhí)行「該指令」,而一般中斷返回回到該指令的「下一個指令」執(zhí)行。

我們來看一下缺頁中斷的處理流程,如下圖:

缺頁中斷的處理流程

  1. 在 CPU 里訪問一條 Load M 指令,然后 CPU 會去找 M 所對應(yīng)的頁表項。
  2. 如果該頁表項的狀態(tài)位是「有效的」,那 CPU 就可以直接去訪問物理內(nèi)存了,如果狀態(tài)位是「無效的」,則 CPU 則會發(fā)送缺頁中斷請求。
  3. 操作系統(tǒng)收到了缺頁中斷,則會執(zhí)行缺頁中斷處理函數(shù),先會查找該頁面在磁盤中的頁面的位置。
  4. 找到磁盤中對應(yīng)的頁面后,需要把該頁面換入到物理內(nèi)存中,但是在換入前,需要在物理內(nèi)存中找空閑頁,如果找到空閑頁,就把頁面換入到物理內(nèi)存中。
  5. 頁面從磁盤換入到物理內(nèi)存完成后,則把頁表項中的狀態(tài)位修改為「有效的」。
  6. 最后,CPU 重新執(zhí)行導(dǎo)致缺頁異常的指令。

上面所說的過程,第 4 步是能在物理內(nèi)存找到空閑頁的情況,那如果找不到呢?

找不到空閑頁的話,就說明此時內(nèi)存已滿了,這時候,就需要「頁面置換算法」選擇一個物理頁,如果該物理頁有被修改過(臟頁),則把它換出到磁盤,然后把該被置換出去的頁表項的狀態(tài)改成「無效的」,最后把正在訪問的頁面裝入到這個物理頁中。

這里提一下,頁表項通常有如下圖的字段:

 

 

那其中:

  • 狀態(tài)位:用于表示該頁是否有效,也就是說是否在物理內(nèi)存中,供程序訪問時參考。
  • 訪問字段:用于記錄該頁在一段時間被訪問的次數(shù),供頁面置換算法選擇出頁面時參考。
  • 修改位:表示該頁在調(diào)入內(nèi)存后是否有被修改過,由于內(nèi)存中的每一頁都在磁盤上保留一份副本,因此,如果沒有修改,在置換該頁時就不需要將該頁寫回到磁盤上,以減少系統(tǒng)的開銷;如果已經(jīng)被修改,則將該頁重寫到磁盤上,以保證磁盤中所保留的始終是最新的副本。
  • 硬盤地址:用于指出該頁在硬盤上的地址,通常是物理塊號,供調(diào)入該頁時使用。

這里我整理了虛擬內(nèi)存的管理整個流程,你可以從下面這張圖看到:

虛擬內(nèi)存的流程

所以,頁面置換算法的功能是,當(dāng)出現(xiàn)缺頁異常,需調(diào)入新頁面而內(nèi)存已滿時,選擇被置換的物理頁面,也就是說選擇一個物理頁面換出到磁盤,然后把需要訪問的頁面換入到物理頁。

那其算法目標(biāo)則是,盡可能減少頁面的換入換出的次數(shù),常見的頁面置換算法有如下幾種:

  • 最佳頁面置換算法(OPT)
  • 先進(jìn)先出置換算法(FIFO)
  • 最近最久未使用的置換算法(LRU)
  • 時鐘頁面置換算法(Lock)
  • 最不常用置換算法(LFU)
  • 最佳頁面置換算法

最佳頁面置換算法

基本思路是,置換在「未來」最長時間不訪問的頁面。

所以,該算法實現(xiàn)需要計算內(nèi)存中每個邏輯頁面的「下一次」訪問時間,然后比較,選擇未來最長時間不訪問的頁面。

我們舉個例子,假設(shè)一開始有 3 個空閑的物理頁,然后有請求的頁面序列,那它的置換過程如下圖:

最佳頁面置換算法

在這個請求的頁面序列中,缺頁共發(fā)生了 7 次(空閑頁換入 3 次 + 最優(yōu)頁面置換 4 次),頁面置換共發(fā)生了 4 次。

這很理想,但是實際系統(tǒng)中無法實現(xiàn),因為程序訪問頁面時是動態(tài)的,我們是無法預(yù)知每個頁面在「下一次」訪問前的等待時間。

所以,最佳頁面置換算法作用是為了衡量你的算法的效率,你的算法效率越接近該算法的效率,那么說明你的算法是高效的。

先進(jìn)先出置換算法

既然我們無法預(yù)知頁面在下一次訪問前所需的等待時間,那我們可以選擇在內(nèi)存駐留時間很長的頁面進(jìn)行中置換,這個就是「先進(jìn)先出置換」算法的思想。

還是以前面的請求的頁面序列作為例子,假設(shè)使用先進(jìn)先出置換算法,則過程如下圖:

先進(jìn)先出置換算法

在這個請求的頁面序列中,缺頁共發(fā)生了 10 次,頁面置換共發(fā)生了 7 次,跟最佳頁面置換算法比較起來,性能明顯差了很多。

最近最久未使用的置換算法

最近最久未使用(LRU)的置換算法的基本思路是,發(fā)生缺頁時,選擇最長時間沒有被訪問的頁面進(jìn)行置換,也就是說,該算法假設(shè)已經(jīng)很久沒有使用的頁面很有可能在未來較長的一段時間內(nèi)仍然不會被使用。

這種算法近似最優(yōu)置換算法,最優(yōu)置換算法是通過「未來」的使用情況來推測要淘汰的頁面,而 LRU 則是通過「歷史」的使用情況來推測要淘汰的頁面。

還是以前面的請求的頁面序列作為例子,假設(shè)使用最近最久未使用的置換算法,則過程如下圖:

最近最久未使用的置換算法

在這個請求的頁面序列中,缺頁共發(fā)生了 9 次,頁面置換共發(fā)生了 6 次,跟先進(jìn)先出置換算法比較起來,性能提高了一些。

雖然 LRU 在理論上是可以實現(xiàn)的,但代價很高。為了完全實現(xiàn) LRU,需要在內(nèi)存中維護(hù)一個所有頁面的鏈表,最近最多使用的頁面在表頭,最近最少使用的頁面在表尾。

困難的是,在每次訪問內(nèi)存時都必須要更新「整個鏈表」。在鏈表中找到一個頁面,刪除它,然后把它移動到表頭是一個非常費時的操作。

所以,LRU 雖然看上去不錯,但是由于開銷比較大,實際應(yīng)用中比較少使用。

時鐘頁面置換算法

那有沒有一種即能優(yōu)化置換的次數(shù),也能方便實現(xiàn)的算法呢?

時鐘頁面置換算法就可以兩者兼得,它跟 LRU 近似,又是對 FIFO 的一種改進(jìn)。

該算法的思路是,把所有的頁面都保存在一個類似鐘面的「環(huán)形鏈表」中,一個表針指向最老的頁面。

當(dāng)發(fā)生缺頁中斷時,算法首先檢查表針指向的頁面:

  • 如果它的訪問位位是 0 就淘汰該頁面,并把新的頁面插入這個位置,然后把表針前移一個位置;
  • 如果訪問位是 1 就清除訪問位,并把表針前移一個位置,重復(fù)這個過程直到找到了一個訪問位為 0 的頁面為止;

我畫了一副時鐘頁面置換算法的工作流程圖,你可以在下方看到:

時鐘頁面置換算法

了解了這個算法的工作方式,就明白為什么它被稱為時鐘(Clock)算法了。

最不常用算法

最不常用(LFU)算法,這名字聽起來很調(diào)皮,但是它的意思不是指這個算法不常用,而是當(dāng)發(fā)生缺頁中斷時,選擇「訪問次數(shù)」最少的那個頁面,并將其淘汰。

它的實現(xiàn)方式是,對每個頁面設(shè)置一個「訪問計數(shù)器」,每當(dāng)一個頁面被訪問時,該頁面的訪問計數(shù)器就累加 1。在發(fā)生缺頁中斷時,淘汰計數(shù)器值最小的那個頁面。

看起來很簡單,每個頁面加一個計數(shù)器就可以實現(xiàn)了,但是在操作系統(tǒng)中實現(xiàn)的時候,我們需要考慮效率和硬件成本的。

要增加一個計數(shù)器來實現(xiàn),這個硬件成本是比較高的,另外如果要對這個計數(shù)器查找哪個頁面訪問次數(shù)最小,查找鏈表本身,如果鏈表長度很大,是非常耗時的,效率不高。

但還有個問題,LFU 算法只考慮了頻率問題,沒考慮時間的問題,比如有些頁面在過去時間里訪問的頻率很高,但是現(xiàn)在已經(jīng)沒有訪問了,而當(dāng)前頻繁訪問的頁面由于沒有這些頁面訪問的次數(shù)高,在發(fā)生缺頁中斷時,就會可能會誤傷當(dāng)前剛開始頻繁訪問,但訪問次數(shù)還不高的頁面。

那這個問題的解決的辦法還是有的,可以定期減少訪問的次數(shù),比如當(dāng)發(fā)生時間中斷時,把過去時間訪問的頁面的訪問次數(shù)除以 2,也就說,隨著時間的流失,以前的高訪問次數(shù)的頁面會慢慢減少,相當(dāng)于加大了被置換的概率。

磁盤調(diào)度算法

我們來看看磁盤的結(jié)構(gòu),如下圖:

磁盤的結(jié)構(gòu)

常見的機(jī)械磁盤是上圖左邊的樣子,中間圓的部分是磁盤的盤片,一般會有多個盤片,每個盤面都有自己的磁頭。右邊的圖就是一個盤片的結(jié)構(gòu),盤片中的每一層分為多個磁道,每個磁道分多個扇區(qū),每個扇區(qū)是 512 字節(jié)。那么,多個具有相同編號的磁道形成一個圓柱,稱之為磁盤的柱面,如上圖里中間的樣子。

磁盤調(diào)度算法的目的很簡單,就是為了提高磁盤的訪問性能,一般是通過優(yōu)化磁盤的訪問請求順序來做到的。

尋道的時間是磁盤訪問最耗時的部分,如果請求順序優(yōu)化的得當(dāng),必然可以節(jié)省一些不必要的尋道時間,從而提高磁盤的訪問性能。

假設(shè)有下面一個請求序列,每個數(shù)字代表磁道的位置:

98,183,37,122,14,124,65,67

初始磁頭當(dāng)前的位置是在第 53 磁道。

接下來,分別對以上的序列,作為每個調(diào)度算法的例子,那常見的磁盤調(diào)度算法有:

  • 先來先服務(wù)算法
  • 最短尋道時間優(yōu)先算法
  • 掃描算法算法
  • 循環(huán)掃描算法
  • LOOK 與 C-LOOK 算法

先來先服務(wù)

先來先服務(wù)(First-Come,F(xiàn)irst-Served,F(xiàn)CFS),顧名思義,先到來的請求,先被服務(wù)。

那按照這個序列的話:

98,183,37,122,14,124,65,67

那么,磁盤的寫入順序是從左到右,如下圖:

 

先來先服務(wù)

先來先服務(wù)算法總共移動了 640 個磁道的距離,這么一看這種算法,比較簡單粗暴,但是如果大量進(jìn)程競爭使用磁盤,請求訪問的磁道可能會很分散,那先來先服務(wù)算法在性能上就會顯得很差,因為尋道時間過長。

最短尋道時間優(yōu)先

最短尋道時間優(yōu)先(Shortest Seek First,SSF)算法的工作方式是,優(yōu)先選擇從當(dāng)前磁頭位置所需尋道時間最短的請求,還是以這個序列為例子:

98,183,37,122,14,124,65,67

那么,那么根據(jù)距離磁頭( 53 位置)最近的請求的算法,具體的請求則會是下列從左到右的順序:

65,67,37,14,98,122,124,183

最短尋道時間優(yōu)先

磁頭移動的總距離是 236 磁道,相比先來先服務(wù)性能提高了不少。

但這個算法可能存在某些請求的饑餓,因為本次例子我們是靜態(tài)的序列,看不出問題,假設(shè)是一個動態(tài)的請求,如果后續(xù)來的請求都是小于 183 磁道的,那么 183 磁道可能永遠(yuǎn)不會被響應(yīng),于是就產(chǎn)生了饑餓現(xiàn)象,這里產(chǎn)生饑餓的原因是磁頭在一小塊區(qū)域來回移動。

掃描算法

最短尋道時間優(yōu)先算法會產(chǎn)生饑餓的原因在于:磁頭有可能再一個小區(qū)域內(nèi)來回得移動。

為了防止這個問題,可以規(guī)定:磁頭在一個方向上移動,訪問所有未完成的請求,直到磁頭到達(dá)該方向上的最后的磁道,才調(diào)換方向,這就是掃描(Scan)算法。

這種算法也叫做電梯算法,比如電梯保持按一個方向移動,直到在那個方向上沒有請求為止,然后改變方向。

還是以這個序列為例子,磁頭的初始位置是 53:

98,183,37,122,14,124,65,67

那么,假設(shè)掃描調(diào)度算先朝磁道號減少的方向移動,具體請求則會是下列從左到右的順序:

37,14,0,65,67,98,122,124,183

 

掃描算法

 

磁頭先響應(yīng)左邊的請求,直到到達(dá)最左端( 0 磁道)后,才開始反向移動,響應(yīng)右邊的請求。

掃描調(diào)度算法性能較好,不會產(chǎn)生饑餓現(xiàn)象,但是存在這樣的問題,中間部分的磁道會比較占便宜,中間部分相比其他部分響應(yīng)的頻率會比較多,也就是說每個磁道的響應(yīng)頻率存在差異。

循環(huán)掃描算法

掃描算法使得每個磁道響應(yīng)的頻率存在差異,那么要優(yōu)化這個問題的話,可以總是按相同的方向進(jìn)行掃描,使得每個磁道的響應(yīng)頻率基本一致。

循環(huán)掃描(Circular Scan, CSCAN )規(guī)定:只有磁頭朝某個特定方向移動時,才處理磁道訪問請求,而返回時直接快速移動至最靠邊緣的磁道,也就是復(fù)位磁頭,這個過程是很快的,并且返回中途不處理任何請求,該算法的特點,就是磁道只響應(yīng)一個方向上的請求。

還是以這個序列為例子,磁頭的初始位置是 53:

98,183,37,122,14,124,65,67

那么,假設(shè)循環(huán)掃描調(diào)度算先朝磁道增加的方向移動,具體請求會是下列從左到右的順序:

65,67,98,122,124,183,199,0,14,37


 

循環(huán)掃描算法

 

磁頭先響應(yīng)了右邊的請求,直到碰到了最右端的磁道 199,就立即回到磁盤的開始處(磁道 0),但這個返回的途中是不響應(yīng)任何請求的,直到到達(dá)最開始的磁道后,才繼續(xù)順序響應(yīng)右邊的請求。

循環(huán)掃描算法相比于掃描算法,對于各個位置磁道響應(yīng)頻率相對比較平均。

LOOK 與 C-LOOK算法

我們前面說到的掃描算法和循環(huán)掃描算法,都是磁頭移動到磁盤「最始端或最末端」才開始調(diào)換方向。

那這其實是可以優(yōu)化的,優(yōu)化的思路就是磁頭在移動到「最遠(yuǎn)的請求」位置,然后立即反向移動。

那針對 SCAN 算法的優(yōu)化則叫 LOOK 算法,它的工作方式,磁頭在每個方向上僅僅移動到最遠(yuǎn)的請求位置,然后立即反向移動,而不需要移動到磁盤的最始端或最末端,反向移動的途中會響應(yīng)請求。

LOOK 算法

而針 C-SCAN 算法的優(yōu)化則叫 C-LOOK,它的工作方式,磁頭在每個方向上僅僅移動到最遠(yuǎn)的請求位置,然后立即反向移動,而不需要移動到磁盤的最始端或最末端,反向移動的途中不會響應(yīng)請求。

C-LOOK 算法

 

責(zé)任編輯:武曉燕 來源: 小林coding
相關(guān)推薦

2021-03-17 16:53:51

IO多路

2009-11-08 22:34:30

2022-12-25 13:59:09

模型架構(gòu)

2010-01-14 17:10:01

VLAN網(wǎng)絡(luò)

2021-07-21 09:15:27

MySQL數(shù)據(jù)庫面試

2011-03-04 09:01:50

開源數(shù)據(jù)庫備份開源數(shù)據(jù)庫MYSQL備份與恢復(fù)

2012-07-30 09:40:05

2009-02-24 09:14:00

2025-04-08 07:20:00

const 聲明變量數(shù)組

2012-11-12 09:47:45

2018-06-15 09:10:43

人工智能AI透視

2021-04-27 19:26:16

代碼項目工具

2009-02-01 11:48:00

局域網(wǎng)監(jiān)控安全

2022-04-25 15:01:07

系統(tǒng)程序員調(diào)度

2011-09-22 09:48:52

F5安全

2020-09-28 17:19:02

中科曙光

2024-12-26 14:42:23

2015-07-03 11:25:31

央視WiFi
點贊
收藏

51CTO技術(shù)棧公眾號