操作系統(tǒng)中進(jìn)程管理的基本原理

操作系統(tǒng)中進(jìn)程管理的基本原理作者：石瑩(2010-6-27)作者信箱：wondersy0618@163.com刖言文章借助王爽老師編寫的Toyix操作系統(tǒng)，通過對一個個程序的執(zhí)行結(jié)果的分析，向讀者演示了操作系統(tǒng)中進(jìn)程的基本原理和基本特性。這篇文章面向已經(jīng)掌握c語言和數(shù)據(jù)結(jié)構(gòu)的操作系統(tǒng)的初學(xué)者。讀者除了學(xué)習(xí)其中的知識，更應(yīng)該學(xué)習(xí)體會文章中分析探索問題的方法，并在以后的計算機(jī)學(xué)習(xí)中應(yīng)用這些方法。這些學(xué)習(xí)的能力是比知識更重要的東西。文章在編寫過程中參考了Toyix簡易教程，《計算機(jī)操作系統(tǒng)》（西安電子科技大學(xué)出版社），《匯編語言》（王爽）操作系統(tǒng)發(fā)展的意義在沒有出現(xiàn)操作系統(tǒng)以前，計算機(jī)只能在一段時間執(zhí)行一段程序，程序因為IO請求等原因發(fā)生阻塞時，CPU會處于空閑狀態(tài)造成資源的浪費(fèi)。因為早期的計算機(jī)價格昂貴，用戶就希望可以更高效的利用計算機(jī)資源。這種需求就促進(jìn)了操作系統(tǒng)的產(chǎn)生和發(fā)展。進(jìn)程我們今天使用的操作系統(tǒng)主要是分時系統(tǒng)，由調(diào)度程序調(diào)入的多個作業(yè)共享CPU資源，其中每個作業(yè)只執(zhí)行極短的一段時間（比如0.1S，我們稱為一個時間片），極短的時間過后暫停執(zhí)行，調(diào)入下一個程序。這樣在不長的一段時間內(nèi)（比如5s內(nèi)），有限的進(jìn)程（少于50個）都可以得到至少一次的執(zhí)行，用戶請求可以得到及時的響應(yīng)。這種作業(yè)調(diào)度的方式我們稱為時間片輪轉(zhuǎn)法。這種執(zhí)行的方式叫并發(fā)執(zhí)行，并發(fā)性也是分時系統(tǒng)的基本特性之一。在分時系統(tǒng)中，為了執(zhí)行一項作業(yè)，就需要把要執(zhí)行的作業(yè)程序載入內(nèi)存中作為程序段，為作業(yè)分配相應(yīng)的數(shù)據(jù)空間作為數(shù)據(jù)段，并加入一個控制塊（PCB），用來保存當(dāng)前作業(yè)執(zhí)行所必須的一些信息，使之能夠并發(fā)執(zhí)行。內(nèi)存中的程序段、數(shù)據(jù)段和PCB我們稱為一個進(jìn)程實體，而一個進(jìn)程實體的執(zhí)行過程我們稱為進(jìn)程。

進(jìn)程的三種基本狀態(tài)我們已經(jīng)知道了進(jìn)程實際是一個動態(tài)的概念，我們再回到分時系統(tǒng)的原理上。分時系統(tǒng)是給一個進(jìn)程分配一個時間片，讓這個進(jìn)程執(zhí)行，當(dāng)進(jìn)程時間片用完以后，為下一個進(jìn)程分配時間片。當(dāng)進(jìn)程執(zhí)行過程中發(fā)生阻塞，則主動讓出CPU控制權(quán)，給其它進(jìn)程執(zhí)行的機(jī)會。分析上面的過程，每一時刻只有一個進(jìn)程處于執(zhí)行的狀態(tài)。而有多個進(jìn)程處于等待分配時間片的狀態(tài)，這多個進(jìn)程應(yīng)該遵循一定的順序。事實上是存在于一個隊列中。這種等待分配時間片的狀態(tài)我們稱為就緒狀態(tài)，存放就緒進(jìn)程的隊列就稱為就緒隊列。當(dāng)CPU處于空閑狀態(tài)時，調(diào)度程序就會從就緒隊列中取出一個進(jìn)程并執(zhí)行。當(dāng)進(jìn)程時間片用完后，調(diào)度信息就會把這個進(jìn)程放入到就緒隊列中。除了時間片用完，當(dāng)進(jìn)程IO請求時，進(jìn)程會在IO請求完畢之前無法繼續(xù)執(zhí)行，這類情況我們稱為進(jìn)程的阻塞（可能出現(xiàn)進(jìn)程阻塞的有IO請求，申請緩沖空間等）。當(dāng)出現(xiàn)進(jìn)程阻塞后，調(diào)度程序應(yīng)該怎么處理呢？首先進(jìn)程肯定不能放入就緒態(tài)，因為放入就緒態(tài)就有可能被分配時間片，而此時進(jìn)程不能繼續(xù)執(zhí)行，這就浪費(fèi)了CPU資源。調(diào)度程序?qū)ζ溥M(jìn)行的處理是將其放到一個阻塞隊列中，當(dāng)10完成時，再把它放回就緒隊列等待分配時間片。圖1進(jìn)程就緒態(tài)、執(zhí)行態(tài)和阻塞態(tài)的關(guān)系圖1圖1進(jìn)程就緒態(tài)、執(zhí)行態(tài)和阻塞態(tài)的關(guān)系使用Toyix查看進(jìn)程的三種狀態(tài)Toyix是一個專門為操作系統(tǒng)的基礎(chǔ)理論教學(xué)而編寫的系統(tǒng)，通過這個系統(tǒng)可以很方便的模擬進(jìn)程的創(chuàng)建執(zhí)行過程。啟動toyix系統(tǒng)，如圖從Toyix網(wǎng)站（/）下載系統(tǒng)并安裝（具體安裝方式請參考網(wǎng)站教程）啟動toyix系統(tǒng)，如圖Toyix操作系統(tǒng)支持絕大部分常用的dos命令，我們可以使用dos下的編程方式進(jìn)行編程?？梢允褂胐os下的工具編寫程序源碼，如圖<Co->C：>edit1-c下面我們編寫一個程序，用來演示程序的三種狀態(tài)#include<toyix.h>main()(inti;for(i=0;i<80;i++)(put_str(3,i,2,"a");delay(30);}get_char();for(i=0;i<80;i++)(put_str(5,i,2,"b");delay(30);}分析上面的程序，程序中引入toyix庫toyix.h文件是為了使用toyix系統(tǒng)提供的關(guān)于的函數(shù)。程序首先在循環(huán)內(nèi)調(diào)用put_str在屏幕第三行輸出字符a（關(guān)于put_str的用法，請參考toyix函數(shù)手冊），每輸出一次延時30ms。然后調(diào)用get_char函數(shù)阻塞式獲得用戶輸入。最后再通過一個循環(huán)在屏幕第五行輸出一行字符b。下面我們在toyix下編譯這個程序。toyix提供的c語言編譯命令是cc，使用方式是“ccc語言源文件文件名”，如圖<Co->C：>cc1-cCompiling...1.c:Auailablememovy208664Linking...Making...1-prg<Co.>C：>程序已經(jīng)編譯，連接成功，產(chǎn)生了toyix下的可執(zhí)行文件2.prg，prg是toyix下可執(zhí)行文件的后綴名。下面運(yùn)行這個程序。Toyix中運(yùn)行一個可執(zhí)行文件的命令是do,使用方法是“do可知性文件的文件名”，注意不需要加后綴名，如圖<Co.>C：>do1然后以后就看到了toyix程序運(yùn)行時的界面blocked：ToyixMultiprocessMonitorU0.03

blocked：ToyixMultiprocessMonitorU0.03屏幕上邊的藍(lán)條是toyix進(jìn)程監(jiān)視器，通過它我們可以方便的知道每個進(jìn)程所處于的狀態(tài)。其中running后指示的是處于運(yùn)行狀態(tài)的進(jìn)程id，ready后指示的是處于就緒狀態(tài)的進(jìn)程id，blocked指示的是處于阻塞狀態(tài)的進(jìn)程id?？梢钥吹轿覀兊某绦蛞呀?jīng)準(zhǔn)備完畢，按任意鍵開始執(zhí)行。程序應(yīng)該是處于就緒態(tài)，進(jìn)程id是1。而此時沒有更多的任務(wù)，CPU處于空閑狀態(tài)，running處用一個紅色的0表示。按任意鍵開始執(zhí)行程序running：1ready： blocked： ToyixMultiprocessMonitoruO.S31.prgokHaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa程序開始在屏幕輸出a，此時程序處于運(yùn)行態(tài)。一行輸出完畢，程序會請求用戶輸入，如圖running:0ready: blocked：1 ToyixMultiprocessMonitorU0.031.prg<15ok可以看到ID為1的進(jìn)程此時處于阻塞態(tài)。按任意鍵，使程序繼續(xù)執(zhí)行running：1ready： blocked： ToyixMultiprocessMonitoru0.031.prg<1>okaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb如圖，程序進(jìn)入運(yùn)行態(tài)繼續(xù)輸出字符b，知道程序運(yùn)行結(jié)束。事實上，進(jìn)程應(yīng)該有一個進(jìn)入就緒態(tài)的過程，再由操作系統(tǒng)取出就緒進(jìn)程分配時間片后進(jìn)入運(yùn)行態(tài)，但是因為時間太短(Toyix系統(tǒng)每個時間片大概是50ms)，我們沒有看到那個狀態(tài)。進(jìn)程與輕權(quán)進(jìn)程我們已經(jīng)知道，操作系統(tǒng)的多個進(jìn)程處于并發(fā)執(zhí)行的狀態(tài)。一個進(jìn)程p1可以創(chuàng)建另一個進(jìn)程p2,我們稱p2為p1的子進(jìn)程，p1為p2的父進(jìn)程。每個進(jìn)程都會有一個進(jìn)程實體，下面我們研究父進(jìn)程與子進(jìn)程進(jìn)程實體之間的聯(lián)系我們可以應(yīng)用c語言的某些特性來進(jìn)行研究，比如我們可以通過下面的程序來輸出一個變量在內(nèi)存中的位置#include<toyix.h>inti=0;main()(printf("\n%d:%d\n",_DS,&i);} —blocked：ToyixMultiprocessMonitoru0.03執(zhí)行后就得到了變量i的段地址和偏移地址(4324d:3216d)blocked：ToyixMultiprocessMonitoru0.03running：0ready4.prg<1>okPress key■■■4324:3216

也可以通過下面這段程序來打印main函數(shù)的地址#include<toyix.h>inti=0;main()(printf("\n%d:%d\n",_CS,main);} —blocked:ToyixMultiprocessMonitoru0.03執(zhí)行后獲得了main函數(shù)的段地址和偏移地址(4324d:0785dblocked:ToyixMultiprocessMonitoru0.03running：0ready4.prg<1>okPressemykey■■■4324:785通過以上兩種方法，我們可以得到一個進(jìn)程的數(shù)據(jù)和代碼在內(nèi)存中的位置。Toyix為我們提供了兩個簡單的創(chuàng)建進(jìn)程的函數(shù)fork()和frk()，這兩個函數(shù)的調(diào)用方法我們不做具體介紹，請參考toyix的函數(shù)手冊。下面我們分別研究這兩個函數(shù)創(chuàng)建進(jìn)程的差別。編寫下面的程序#include<toyix.h>inti=-1;main()(i=fork();printf("\n\n\nCallforkreturnvalueis%d\n",i);printf("\nPID=%d\n",get_pid());printf("\nFunctionmainoftheaddressis%d:%d\n",_CS,main);printf("\nVariableioftheaddressis%d:%d\n",_DS,&i);delay(500);}分析這個程序，這個程序調(diào)用fork()函數(shù)創(chuàng)建的新的進(jìn)程，并在每個進(jìn)程中輸出fork()函數(shù)返回值(判斷父進(jìn)程還是子進(jìn)程)，當(dāng)前進(jìn)程ID，main函數(shù)的地址，變量i的地址。運(yùn)行這個程序如圖，通過fork()函數(shù)的返回值我們判斷，pid為1的進(jìn)程為父進(jìn)程。而且父進(jìn)程與子進(jìn)程數(shù)據(jù)段和代碼段均不相同。這說明通過fork()函數(shù)創(chuàng)建的進(jìn)程數(shù)據(jù)與代碼不共享。下面我們用同樣的方法研究通過frk()函數(shù)創(chuàng)建的進(jìn)程，修改上面的程序#include<toyix.h>inti=-1;main()(i=frk();printf("\n\n\nCallforkreturnvalueis%d\n",i);printf("\nPID=%d\n",get_pid());printf("\nFunctionmainoftheaddressis%d:%d\n",_CS,main);printf("\nVariableioftheaddressis%d:%d\n",_DS,&i);delay(500);}這個程序與上面的程序基本相同，只是把fork()函數(shù)改為了frk()函數(shù)，在toyix中運(yùn)行這個程序我們發(fā)現(xiàn)，pid為1的進(jìn)程為父進(jìn)程，父進(jìn)程與子進(jìn)程代碼段不同，但是數(shù)據(jù)段相同。這說明，通過frk()創(chuàng)建的進(jìn)程數(shù)據(jù)段共享，代碼段不共享。這種進(jìn)程我們稱為輕權(quán)進(jìn)程。我們?yōu)槭裁匆獎?chuàng)建輕權(quán)進(jìn)程呢？創(chuàng)建進(jìn)程是為了提高系統(tǒng)資源利用率，但是因為進(jìn)程擁有自己的數(shù)據(jù)段。進(jìn)程的創(chuàng)建需要申請數(shù)據(jù)空間，銷毀需要釋放數(shù)據(jù)空間，切換進(jìn)程需要保存并重新設(shè)置CPU寄存器現(xiàn)場。進(jìn)程的創(chuàng)建，切換和銷毀都需要消耗大量的CPU資源。有時我們需要把自己的一個進(jìn)程分成幾部分同時處理。比如程序中有一段代碼會循環(huán)等待用戶輸入，而用戶的是否輸入并不會影響我們程序的繼續(xù)運(yùn)行，我們不希望等待用戶輸入時主程序也進(jìn)入阻塞狀態(tài)。我們可以將用戶輸入的部分創(chuàng)建一個新的進(jìn)程，但是事實上這個進(jìn)程并不需要分配新的數(shù)據(jù)空間。那么就出現(xiàn)了沒有自己獨(dú)立的數(shù)據(jù)空間的進(jìn)程，也就是輕權(quán)進(jìn)程。輕權(quán)進(jìn)程在創(chuàng)建，切換和銷毀時消耗的資源比進(jìn)程都小的多。下面我們做這樣一個實驗。編寫下面的程序#include<toyix.h>main()(frk();printf("\nPID=%d\n",get_pid());} —程序中調(diào)用frk()創(chuàng)建輕權(quán)進(jìn)程以后每個進(jìn)程打印自己的進(jìn)程id。在toyix下運(yùn)行并查看結(jié)果running-prg<1>ressan</ID=10readyrunning-prg<1>ressan</ID=10readyokkey-..blockedToyixMultiprocessMonitoru0.可以看到運(yùn)行結(jié)果與我們預(yù)想的不太一樣，只打印了一個進(jìn)程的pid，另一個沒有打印。這是為什么呢？我們修改一下這個程序#include<toyix.h>main()(frk();printf("\nPID=%d\n",get_pid());delay(100);與前一個比較，這個程序多調(diào)用了一個延時功能。再看運(yùn)行結(jié)果runn:0ready：okkey...blockedToyixMultiprocessMonitoru0.03runn:0ready：okkey...blockedToyixMultiprocessMonitoru0.03我們發(fā)現(xiàn)現(xiàn)在的顯示結(jié)果正確了?，F(xiàn)在為什么正確了呢？我們分析第一個程序，主進(jìn)程創(chuàng)建進(jìn)程以后，打印輸出自己的進(jìn)程id。此時子進(jìn)程還沒有得到執(zhí)行的機(jī)會，父進(jìn)程就運(yùn)行結(jié)束了，子進(jìn)程也被銷毀。子進(jìn)程雖然創(chuàng)建了，但是并沒有得到執(zhí)行。所以出現(xiàn)了錯誤的結(jié)果。第二個程序中，在父進(jìn)程打印出自己的進(jìn)程id以后，通過延時給子進(jìn)程執(zhí)行的機(jī)會，子進(jìn)程進(jìn)入運(yùn)行態(tài)，打印子進(jìn)程pid，輸出結(jié)果正常。以上分析表明，如果父進(jìn)程結(jié)束，操作系統(tǒng)會銷毀它創(chuàng)建的所有輕權(quán)進(jìn)程。這很容易理解，因為輕權(quán)進(jìn)程是沒用數(shù)據(jù)空間的，它共享父進(jìn)程的數(shù)據(jù)空間。而父進(jìn)程銷毀時，數(shù)據(jù)空間會被釋放，此時如果子進(jìn)程繼續(xù)執(zhí)行，可能訪問已經(jīng)釋放掉的空間，這是不安全的。這一部分我們講述了進(jìn)程與輕權(quán)進(jìn)程的一些差別。簡單來說，進(jìn)程是可以獨(dú)立運(yùn)行的最小單位。而輕權(quán)進(jìn)程是可供操作系統(tǒng)調(diào)度的最小單位。后面我們要繼續(xù)講述怎樣在我們編寫的程序中更方便的創(chuàng)建多個輕權(quán)進(jìn)程。使用cobegin創(chuàng)建輕權(quán)進(jìn)程通過以上的學(xué)習(xí)我們知道，為了更高效的利用資源，我們編寫的程序可能要創(chuàng)建多個輕權(quán)進(jìn)程。但是使用frk()創(chuàng)建的進(jìn)程只能在兩個進(jìn)程中執(zhí)行同一段代碼，這樣的進(jìn)程是沒有實際意義的。為了方便的創(chuàng)建輕權(quán)進(jìn)程，toyix為我們提供了cobegin函數(shù)。Toyix函數(shù)手冊中對這個函數(shù)的描述如下：原型：intcobegin();功能：創(chuàng)建多個子進(jìn)程并發(fā)執(zhí)行函數(shù)參數(shù):函數(shù)名用0結(jié)束，例如：cobegin(f1,f2,f3,0);返回：創(chuàng)建子進(jìn)程的個數(shù)說明：所有子進(jìn)程共享數(shù)據(jù)段，主進(jìn)程撤銷，所有子進(jìn)程將被撤銷。我們編寫一個程序，通過cobigin函數(shù)來創(chuàng)建多個輕權(quán)進(jìn)程。#include<toyix.h>voidf1()(printf("\nfunctionf1,pid=%d\n",get_pid());TOC\o"1-5"\h\z} —voidf2()(printf("\nfunctionf2,pid=%d\n",get_pid());} —voidf3()(printf("\nfunctionf3,pid=%d\n",get_pid());} —main()(printf("\nfunctionmain,pid=%d\n",get_pid());cobegin(f1,f2,f3,0);delay(100);}在這個程序中，main函數(shù)首先輸出自己的pid，然后調(diào)用cobegin函數(shù)將f1,f2,f3函數(shù)分別作為一個輕權(quán)進(jìn)程運(yùn)行，在每個輕權(quán)進(jìn)程里，打印自己的函數(shù)名和pid。運(yùn)行結(jié)果如圖多進(jìn)程引發(fā)的問題下面我們要應(yīng)用多進(jìn)程技術(shù)編寫一個模擬火車售票系統(tǒng)的程序。在火車票售票中心的服務(wù)器上，保存著未售出的火車票數(shù)量。而各地有很多代售點(diǎn)，他們在售票時會連接到售票中心檢查火車票剩余情況，如果還有剩余票，那么賣出這張牌，同時通知售票中心車票被賣出。編寫程序?qū)崿F(xiàn)這個過程，首先創(chuàng)建一個全局變量，用來保存剩余票數(shù)。編寫一個函數(shù)用來模擬一個售票窗口的售票流程。再通過在main函數(shù)中調(diào)用cobegin函數(shù)創(chuàng)建多個輕權(quán)進(jìn)程，模擬多個窗口售票。程序代碼如下：

#include<toyix.h>inttotal=10;voidf1()(while(total>0)(delay(50);printf("\npid=%d,sellticket:%d",get_pid(),total--);} —}main()(cobegin(f1,f1,0);getch();}在單個窗口的售票流程中，首先檢查剩余票數(shù)是否大于0，如果大于0，那么延時一段時間(模擬真實情況)，然后賣出這張票，再令剩余票減一。在toyix系統(tǒng)中運(yùn)行，模擬結(jié)果如圖running：1ready：1.prg<1>okPressanyke</.--pid=2,sellticketpid=3,sellticketpid=2,sellticketpid=3,sellticketpid=2,sellticketpid=3,sellticketpid=2,sellticketpid=3,sellticketpid=2,sellticketpid=3,sellticketpid=2,sellticketrunning：1ready：1.prg<1>okPressanyke</.--pid=2,sellticketpid=3,sellticketpid=2,sellticketpid=3,sellticketpid=2,sellticketpid=3,sellticketpid=2,sellticketpid=3,sellticketpid=2,sellticketpid=3,sellticketpid=2,sellticket019876543210blocked:ToyixMultiprocessMonitoruS.03我們發(fā)現(xiàn)一個問題，售票窗口售出了0號票，這在實際應(yīng)用中是不允許的。為什么會發(fā)生這種情況呢？我們再分析剛才的程序，為了分析簡單，我們假設(shè)假如程序運(yùn)行了一段時間，還有一張票未售出。程序中每個輕權(quán)進(jìn)程的執(zhí)行過程如下圖所示。(虛線代表阻塞態(tài)或就緒態(tài)，實現(xiàn)代表運(yùn)行態(tài))total:total:主進(jìn)程:主進(jìn)程創(chuàng)建完輕權(quán)進(jìn)程P1和P2后，在獲得用戶鍵盤輸入之前一直處于阻塞態(tài)沒有獲得時間片主進(jìn)程:a)P1獲得時間片，檢測到total>0,進(jìn)入售票程序延時一段時間，還未售票時間片已經(jīng)用完輕權(quán)進(jìn)程P1：c)P1獲得時間片繼續(xù)運(yùn)行，售票程序售出這張票后，令total減一。再次檢測total=0，循環(huán)結(jié)束，進(jìn)程結(jié)束b)P2獲得時間片，與a中處理過程相同輕權(quán)進(jìn)程P2： id)P2獲得時間片，售票后退出。但是此時total=0，所以售出了0號票此時一個進(jìn)程(pid=2)檢查total的值，檢測到大于0進(jìn)入售票程序，調(diào)用delay延時(注意票并沒有售出，tatal仍為1)。此時另一個輕權(quán)進(jìn)程(pid=3)獲得了時間片開始運(yùn)行，仍會檢測tatal的值，同樣進(jìn)入了售票程序，調(diào)用delay延時。調(diào)度程序調(diào)出剛才的輕權(quán)進(jìn)程(pid=2)的進(jìn)程繼續(xù)執(zhí)行，售出1號票并將票數(shù)減1，再次檢測tatal小于0，pid為2的輕權(quán)進(jìn)程結(jié)束退出。Pid為3的輕權(quán)進(jìn)程回到剛才的狀態(tài)繼續(xù)售票，而此時tatal為0，所以售出了0號票。顯然，在這個實驗中如果沒有延時操作，可能不會出現(xiàn)這樣的情況。但是在一個長期運(yùn)行的多個輕權(quán)進(jìn)程的系統(tǒng)中，很有可能出現(xiàn)這種兩個輕權(quán)進(jìn)程訪問同一資源時出錯的問題。增加一個延時只是放大了這種問題。通過上述分析，我們了解了一個進(jìn)程通過創(chuàng)建多個輕權(quán)進(jìn)程雖然可以提高資源的利用率，但是在訪問同一資源時可能引起一些問題。為了解決這些問題，我們必須在不同輕權(quán)進(jìn)程訪問同一資源時進(jìn)行一些判