程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> 五種進程調度的算法實現(一),五種進程調度算法

五種進程調度的算法實現(一),五種進程調度算法

編輯:關於C語言

五種進程調度的算法實現(一),五種進程調度算法


實驗要求

1、基於Event-Driven(事件驅動)實現模擬進程調度,包括

  • 最短工作優先(SJF);
  • 最短剩余時間優先(SRTF);
  • 最高響應比優先(HRRF);
  • 優先級調度(Priority);
  • 輪轉調度(RR)。

其中,SJF、SRTF為非搶占式調度,其余為搶占式調度。

2、要求用C語言實現這五種調度算法。(方便起見,引入了C++頭文件使用cout進行輸出)

 

基礎知識

一、進程

1.1 進程的含義

廣義地說,進程是一個具有獨立功能的程序關於某個數據集合的一次運行活動。

進程是一種抽象的概念,是對程序的抽象。程序是一連串的代碼或指令,是靜態的東西,就像一本書放在那裡。

那什麼時候,程序會“動”起來呢?當然是我們執行了它。比如用鼠標雙擊Word的快捷方式,那麼過一會兒,Word程序就會呈現在你眼前。究其過程,不是“你”執行了程序,而是你讓計算機執行了程序。那計算機是怎麼執行程序的呢?眾所周知,這就要涉及到它的內部,甚至是它的大腦——中央處理器(CPU)了。

CPU是干什麼的呢?CPU就是用來執行特定指令的。上面說道程序就如同一本書,那麼CPU的角色就相當於讀者,書上的文字相當於指令,CPU“讀”了“書”之後,有所感悟,就去做相當的事情,完成相當的任務。

打個比方,要以書來比喻指令,那麼用菜譜來說就再貼切不過了。

以菜譜為例,比如現在要做一道菜,按照菜譜上的10個步驟來。這裡,做菜的時候,首先要准備食材、調料等,這都不是指令是什麼回事?其實,計算機中的程序文件(可執行文件)除了包含代碼之外,還包含數據,例如應用程序的圖標等。接下來,“你”——CPU,就要按照步驟做菜了。做菜途中要等,就得等。一系列步驟下來,最終,一道上好的菜擺在你眼前,色香味俱全。這印證著定義中“具有獨立功能”的含義,做一道特色的菜,就是獨立完成一種任務。

1.2 進程的狀態

最簡單的概括(三態模型)是:進程的狀態分為——等待態、就緒態、運行態。五態模型比三態模型多了新建態終止態

以同時炒多道菜為例。進程就相當於炒菜的過程。

  • 等待態——某道菜可能需要煮、蒸、焖一會兒,這時就需要等待它完成;
  • 就緒態——某道菜煮、蒸、焖完了,需要你去處理,然而你現在正在做另一道菜,還沒來得及切換過來;
  • 運行態——炒當前的某道菜;
  • 新建態——正准備做這道菜;
  • 終止態——這道菜做完了,要做一些收尾工作。

1.3 進程的特征

進程的特征有四點:動態性、並發性、獨立性、異步性。

仍以同時炒多道菜為例。

  • 動態性——白天炒菜的整個過程,進程是“活”的,因為“你”正在工作。而到了晚上,廚房空無一人,進程是“死”的,廚房內的設施都回到了原位,如同沒有人在這裡炒過菜一樣。進程在一天一夜之間有狀態的切換,因此是動態的;
  • 並發性——你可以同時炒多道菜;
  • 獨立性——你准備的調料是以某道菜的需求而准備的,而不是裡面的某塊肉。菜譜中的步驟必須按部就班來,不能少不能亂。一種菜譜完成一道菜,不同菜譜完成的菜不同。你炒這道菜的過程不會影響炒那道菜的過程;
  • 異步性——每道菜被烹饪的過程是間斷的(由於是炒多道菜),被中斷的時間是未知的。每次炒多道菜的總體時間並不相同,這也體現了炒多道菜的不可預知性。

以上是我的譬喻,而文字描述是這樣的:

  • 動態性——進程的實質是程序在多道程序系統中的一次執行過程,既然是過程就要有始有終,所以進程會產生、會消亡。進程執行完畢後,一般不會留下關於它運行的一絲痕跡;
  • 並發性——任何進程都可以同其他進程一起並發執行,並發是任意時刻只有一個程序在運行(要與並行相區別);
  • 獨立性——進程是一個能獨立運行的基本單位,同時也是系統分配資源和調度的獨立單位;
  • 異步性——由於進程間的相互制約,使進程具有執行的間斷性,即進程按各自獨立的、不可預知的速度向前推進。

1.4 進程的調度

進程的調度分為搶占式和非搶占式(或剝奪式和非剝奪式)。

搶占式調度,正如它的名稱“搶占”,搶過來自己占用,所以體現有兩點——“”和“”。

何為搶?依照算法,該任務權重大或者優先級高,自然而然就會“搶”到運行的機會。如果當時時刻系統沒有運行其它任務,那麼該任務A被運行;如果當時時刻系統正在運行其它任務B,那麼依照算法,如果該任務A有“搶”的資格,那就像搶凳子一樣,A搶到了,B沒有搶到,那麼就暫停運行B,開始運行A。

何為占?任務搶到運行機會(即CPU時間)後,占有相應的運行時間。在這個時間內,系統只運行該任務,直到下一次系統利用算法重新分配任務的運行時間之前。

因此,正如搶凳子,搶凳子也是一種分配資源的方式,誰體形大、力氣大、反應短,搶到的機會就多。在這其中,存在多人搶同一凳子的情況,這就是“競爭”;“好”的凳子,搶的人就多,競爭就越激烈。敗者不甘心,想盡快在下次爭奪中取勝;勝者保持優勢,戰略上蔑視敗者,但不能自大。

這裡就要說到“隊列”。假如你要完成一系列的事項,以菜譜為例,一共10個步驟。你現在把這10個步驟寫在10個紙片上,然後把它們一個個摞起來,那麼當前紙堆的最上面的紙片上就是你當前要做的步驟Step1,你把Step1做完後,把Step1丟棄,那麼紙堆頂就是Step2,如此類推,最後剩下Step10,做完之後紙片就全部沒有了,此時隊列為“空”。

無論是搶占式還是非搶占式,都要依照這個“隊列”中任務的先後順序來運行它們。所以,隊列代表著任務的“生存周期”。只要任務還在隊列中,任務就沒有“死”,即沒有運行結束而消亡;任務就沒有“生”,即任務還未開始運行。

現在,重點就是怎麼安排這個隊列,這就提到上述五種調度算法了。“調度”,可以看成安排隊列的一種方式。

以隊列為基礎。搶占式調度意味著某任務A一旦運行之後,可能被其它任務B搶占,現在就要把A移到堆底,把B移到堆頂;非搶占式調度意味著某任務A一旦運行之後,就一直運行A直到結束,期間如果任務B也想要開始運行,就只能把B放在A的下面了,即任務的運行順序從它們加入隊列時就確定了,以後隊列的順序不會更改。

二、線程

2.1 線程的含義

線程是程序執行流的最小單元,是被系統獨立調度和分派的基本單位。

如同進程是一種抽象一樣,線程也是一種抽象,一種更高度的抽象。原先一個進程只能同時完成一種任務,現在需求多了,促使一個進程要同時完成多個任務,如果沒有線程的概念,那麼同一進程內的任務只能串行運行(按序運行)。

現在,把進程也看作一個系統,那麼進程的“進程”就是線程了。進程原先作為任務調度的基本單位,與線程相比,進程太“大”了,所以相比較而言,線程的粒度更小。

2.2 線程的狀態

線程的狀態與進程的狀態一樣,也是五態模型,可以參照進程的五態模型。

2.3 線程的特點

  • 線程是操作系統調度的基本單位;
  • 線程的狀態切換比進程更迅速且開銷更小;
  • 線程不擁有資源,只是任務的一種抽象,同一進程內的線程共享該進程的資源;
  • 對單核CPU而言,同一時刻只能運行一個線程;
  • 一個進程至少有一個線程,且是它的主線程。

2.4 線程與進程的區別

  • 進程之間相互獨立(資源的獨立),而某一進程的各線程間共享資源(如果不能共享,豈不就與進程沒多大區別了);
  • 由於進程的獨立性,當進程間要相互通信時,系統只能提供各種外部方法,比較繁瑣,而線程間的通信可以通過共享數據來實現;
  • 線程的狀態切換比進程更快捷且開銷更小;
  • 在多線程系統中,線程才是可執行對象,因為線程是進程中的並發任務的一種抽象。原先,進程是運行任務的主體,有了線程之後,運行任務的重擔就落到了線程身上。

2.5 線程的優點

  • 充分利用CPU資源(如下的超線程技術會提到這點);
  • 實現了進程內並發,使用任務的粒度分得更細,有利於開發人員對任務的分解、抽象(分解與抽象原則);
  • 實現了進程內異步事件的處理,尤其是GUI事件、服務端應用等;
  • 提高了程序的運行效率。

三、同步與異步

3.1 同步的含義

同步,簡單地說,就是調用一個過程時,假如過程還在執行狀態,沒有返回結果,那麼在該過程返回之前,就不能繼續做下一件事情。

舉個例子來說,比如要先穿襪子再穿鞋,順序不能顛倒,所以我概括同步的特點就是:順序性、確定性、簡易性

順序性,就是運行次序不會顛倒錯亂,一切按順序來;

確定性,就是運行順序是確定的,可以預見的,就像數學的計算過程一樣,最後的答案是確定的;

簡易性,因為同步不牽涉到線程的概念,運行一個簡單的單線程程序時,不會用到系統提供的線程同步機制(API)。

3.2 異步的含義

異步是相對於同步而言的,意思與同步相反。即調用一個過程時,就接著做下面的事情,不立即獲得該過程的返回值。

打個比方,用微波爐加熱食物,按下“啟動”鍵,微波爐就開始運行了。這時,你不會去苦苦等待它加熱,可以做其他的事情。等到聽到一聲“叮”時,你知道加熱完畢了,就會去拿出食物。

這裡涉及到幾個細節:你去干別的事、聽到“叮”的一聲就跑過去。

你去做別的事,那麼現在一共有兩件事正在做的過程當中,抽象成線程,就是兩個線程在同時運行;

聽到“叮”的一聲就跑過去,說明過程返回了,但你並沒有苦苦等這個過程返回,這個“返回”是巧妙的。

因此,要實現異步,你得學會做兩件事——添加新任務(創建線程),知道舊任務已經結束了並跑去處理(狀態、通知和回調)。

3.3 實現異步的方法

創建線程可以通過調用API來實現,那麼怎麼知曉舊任務已經運行結束了呢?

狀態,即設一共享變量(FLAG),舊任務結束時,變量置有效值,之後舊任務結束,新任務循環檢測變量是否有效;

通知,即像下載軟件一樣,下載完,系統會通知你,即舊任務向新任務發通知或消息,發完之後,舊任務結束;

回調,就是把舊任務做完後要做的收尾工作交給舊任務本身,這樣,舊任務做完收尾工作後便結束。

上述三種方法當中,“回調”,舊任務與新任務之間沒有關系;“通知”,舊任務和新任務有直接聯系;“狀態”,舊任務和新任務有間接聯系,通過狀態變量。

回調時,新任務可以不管舊任務的事情;

通知時,新任務必須間斷地等待是否有通知,如果有通知,就處理它。等待的時候,新任務一般處於阻塞狀態;

狀態時,新任務不必進行等待操作,它只需要適時檢測(判斷)這個狀態變量是否有效(即是否為有效值)就可以了,這種方法也就是輪詢

四、並發與並行

4.1 並發的含義

當有多個進程在運行時,如果系統是單核的CPU,那它根本不可能真正地同時運行一個以上的進程。系統只能把CPU運行時間劃分成若干個時間段(在每個時刻段的起始時刻使用調度算法分配任務),再將每個時間段分配給每個進程執行。在一個時間段內,某進程在運行時,其它進程處於掛起狀態(就緒狀態)。這種方式我們稱之為並發Concurrent)。

首先,上述講到的進程調度就涉及到了進程並發。並發的精髓就是分配時間片,微觀上是間斷的,宏觀上是連續的。假如系統一共有26個進程,在一個時間段內,只運行進程A,接著在下一個時間段內運行進程B,直到運行完進程Z,那麼所有進程都被運行過了。進程被“重視”的標志就是它的CPU時間,時間多了,運行的就久,進度就越快。當前A-Z的順序只是一個例子,在真實情況中很少出現這種情況。

上面的定義中,提到了單核的概念。

單核是和多核相區分的,可以這麼理解,某時刻,單核CPU只能做一個任務,而多核CPU可以做多個任務。任務做的越多,任務的進度就越快速,系統完成任務的效率就高了。

還有一個概念是超線程Hyperthreading Technology)。

超線程技術就是通過采用特殊的硬件指令,可以把兩個邏輯內核模擬成兩個物理超線程芯片,在單處理器中實現線程級的並行計算,同時在相應的軟硬件的支持下大幅度提高運行效能,從而實現在單處理器上模擬雙處理器的效能。其實,從實質上說,超線程是一種可以將CPU內部暫時閒置處理資源充分“調動”起來的技術。

雖然采用超線程技術能夠同時執行兩個線程(如果每個進程同一時刻只能運行它的一個子線程的話,那就等同個能夠同時執行兩個進程),但它並不像兩個真正的CPU那樣,每個CPU都具有獨立的資源。當兩個線程都同時需要某一個資源時,其中一個要暫時停止,並讓出資源,直到這些資源閒置後才能繼續。因此超線程的性能並不等於兩顆CPU的性能。

超線程與多核的區別主要取決於資源的獨立性。當運行的這兩個線程屬於同一進程,那麼對於超線程技術,就會遇到兩個線程的資源發生沖突的情況;對於多核,就不會發生這種情況,因此兩個線程在兩個不同的CPU之中運行,縱使它們屬於同一進程。

4.2 並行的含義

當系統有一個以上CPU(即多核)時,則線程的操作有可能不是並發的。當一個CPU執行一個線程時,另一個CPU可以執行另一個線程,兩個線程不搶占CPU資源,可以同時進行,這種方式我們稱之為並行Parallel)。

並行是多核CPU的概念。並發是微觀上間斷,宏觀上連續,而並行在微觀上離“連續”更近了一步。

4.3 並發與並行的區別

並發與並行這兩個概念很容易混淆。

並行是指兩個或者多個事件在同一時刻發生;並發是指兩個或多個事件在同一時間間隔內發生。

並發是單核CPU的產物,微觀上間斷,宏觀上連續;並行是多核CPU的產物,微觀上更連續,宏觀上更連續。

以數硬幣為例,總共一堆硬幣。並發是一個人A數,並行是多個人B1-Bn數。

對A來說。選擇一:從頭到底埋頭數;選擇二:將硬幣分成大致相同的N份,一會兒數這一份,一會兒數那一份。

對B來說。B將硬幣分成大致相同的N份,因此B有N個人,所以這N個人分別數這N份硬幣,由於人多力量大,所以B比A先數完。

A的選擇一即為單道程序,選擇二為多道程序即並發;B的選擇即並行。

  • 並行的程序比並發的程序效率高,資源利用率高,但編程更復雜,且結果不可預見,調試困難;
  • 並行會有對資源的爭奪,而並發不會(某時刻只有一個程序獨占資源),因而並行會有互斥與同步問題,還有由此導致的死鎖問題;
  • 並發是單核CPU的產物,微觀上間斷,宏觀上連續;並行是多核CPU的產物,微觀上更連續,宏觀上更連續。

4.4 死鎖

4.4.1 死鎖的定義

死鎖的規范定義:集合中的每一個進程都在等待只能由本集合中的其他進程才能引發的事件,那麼該組進程是死鎖的。

4.4.2 死鎖發生的四個必要條件

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved