湯元斌
(四川文理學(xué)院 現(xiàn)代教育技術(shù)中心,四川 達(dá)州635000)
操作系統(tǒng)是管理軟硬件資源、控制程序執(zhí)行,改善人機(jī)界面交互,合理組織計(jì)算機(jī)工作流程和為用戶使用計(jì)算機(jī)提供良好運(yùn)行環(huán)境的一種系統(tǒng)軟件,因此它是計(jì)算機(jī)系統(tǒng)運(yùn)行的核心.[1]進(jìn)程是程序的一次執(zhí)行過(guò)程,是操作系統(tǒng)進(jìn)行資源調(diào)度和管理的一個(gè)獨(dú)立單位,是在操作系統(tǒng)學(xué)習(xí)過(guò)程中需要重點(diǎn)理解和掌握的概念.但由于其理論性強(qiáng),進(jìn)程的運(yùn)行工作原理和算法比較抽象難懂,學(xué)生掌握起來(lái)非常困難.為了讓學(xué)生更好地理解掌握操作系統(tǒng)中進(jìn)程這一概念及其調(diào)度算法.本文在多線程的基礎(chǔ)上設(shè)計(jì)開(kāi)發(fā)了進(jìn)程時(shí)間片輪轉(zhuǎn)調(diào)度的模擬仿真程序,經(jīng)過(guò)測(cè)試,該模擬程序可以較好地輔助學(xué)生學(xué)習(xí)和掌握進(jìn)程的概念及其調(diào)度算法,對(duì)學(xué)生有效學(xué)習(xí)和理解操作系統(tǒng)的進(jìn)程調(diào)度算法具有重要的指導(dǎo)意義.
在多任務(wù)環(huán)境下,為了能更好地并發(fā)處理各種程序,操作系統(tǒng)中引入了進(jìn)程這一概念.進(jìn)程是程序關(guān)于某個(gè)數(shù)據(jù)集合的可并發(fā)執(zhí)行的具有獨(dú)立功能的一次執(zhí)行過(guò)程,也是操作系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位,具有結(jié)構(gòu)性、共享性、動(dòng)態(tài)性、獨(dú)立性、制約性和并發(fā)性等特征.調(diào)度是指調(diào)用遠(yuǎn)方資源分配,而調(diào)度算法是根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法.[2]
在操作系統(tǒng)中,有一種非常重要的用來(lái)刻畫(huà)進(jìn)程的數(shù)據(jù)結(jié)構(gòu)叫進(jìn)程控制塊,其主要用于記錄操作系統(tǒng)所需和描述進(jìn)程當(dāng)前情況以及控制進(jìn)程運(yùn)行的全部信息.進(jìn)程控制塊主要記錄以下四個(gè)方面的信息:① 進(jìn)程的標(biāo)志信息,即進(jìn)程名和用于標(biāo)識(shí)進(jìn)程唯一的標(biāo)識(shí)符;② 處理機(jī)狀態(tài)信息,即處理機(jī)中各種寄存器中的內(nèi)容;③ 進(jìn)程調(diào)度信息,即存放于PCB中的關(guān)于進(jìn)程調(diào)度和進(jìn)程切換的信息;④ 進(jìn)程控制信息,即程序和數(shù)據(jù)的地址、鏈接指針、資源清單等.
進(jìn)程在操作系統(tǒng)中是一個(gè)動(dòng)態(tài)的概念,它是程序在數(shù)據(jù)集合上的一次執(zhí)行過(guò)程,因此進(jìn)程在操作系統(tǒng)中執(zhí)行時(shí)的異步性決定了進(jìn)程從出現(xiàn)到消失可能處于多種狀態(tài),一般定義為五態(tài)模型,如圖1所示.新建狀態(tài),是操作系統(tǒng)執(zhí)行一個(gè)程序時(shí)創(chuàng)建了一個(gè)子進(jìn)程狀態(tài);就緒狀態(tài),是進(jìn)程在滿足了一切準(zhǔn)備運(yùn)行的資源后,準(zhǔn)備進(jìn)入CPU進(jìn)行執(zhí)行的狀態(tài);運(yùn)行狀態(tài),是進(jìn)程在CPU上執(zhí)行的狀態(tài);等待狀態(tài),是進(jìn)程由于缺少某些資源而處于暫時(shí)無(wú)法運(yùn)行的狀態(tài);終止?fàn)顟B(tài),是在進(jìn)程運(yùn)行結(jié)束后釋放資源過(guò)程中的狀態(tài).進(jìn)程的各種狀態(tài)之間可以互相切換,但進(jìn)程總是處于某一種狀態(tài)中.
圖1 進(jìn)程狀態(tài)轉(zhuǎn)換圖
如圖2所示,進(jìn)程是利用進(jìn)程隊(duì)列對(duì)各種狀態(tài)下的進(jìn)程進(jìn)行調(diào)度和管理.當(dāng)進(jìn)程產(chǎn)生時(shí)就會(huì)進(jìn)入就緒隊(duì)列中,就緒隊(duì)列中的進(jìn)程被選中就會(huì)進(jìn)入CPU中進(jìn)行執(zhí)行.當(dāng)進(jìn)程的運(yùn)行時(shí)間片到了就會(huì)進(jìn)入就緒隊(duì)列中;當(dāng)在CPU執(zhí)行的過(guò)程中某些資源得不到滿足,就會(huì)進(jìn)入等待隊(duì)列中;當(dāng)進(jìn)程在CPU上運(yùn)行結(jié)束,就會(huì)釋放資源,然后消失.
圖2 進(jìn)程調(diào)度和管理流程圖
時(shí)間片輪轉(zhuǎn)算法[3]的基本原理為:將CPU的處理時(shí)間劃分成一個(gè)個(gè)小的時(shí)間片,然后將處于就緒隊(duì)列中的各個(gè)進(jìn)程按照先來(lái)先服務(wù)原則依次使用CPU資源;當(dāng)一個(gè)進(jìn)程所分配的時(shí)間片用完后就會(huì)返回到就緒隊(duì)列的末尾進(jìn)行重新排隊(duì),等待下一次調(diào)度,其所占用的CPU資源會(huì)被強(qiáng)迫讓出以便釋放出處理機(jī)給另一個(gè)就緒的進(jìn)程,同時(shí)就緒隊(duì)列中的另一個(gè)進(jìn)程會(huì)被進(jìn)程調(diào)度選中,然后給它分配一個(gè)時(shí)間片運(yùn)行.
為了模擬上文中進(jìn)程、進(jìn)程的狀態(tài)以及進(jìn)程的時(shí)間片輪轉(zhuǎn)調(diào)度,本文在Linux的環(huán)境下用C語(yǔ)言進(jìn)行了模擬仿真,首先利用結(jié)構(gòu)體描述進(jìn)程,其次用兩個(gè)隊(duì)列對(duì)進(jìn)程進(jìn)行管理,然后用兩個(gè)線程進(jìn)行進(jìn)程的調(diào)度輪轉(zhuǎn),同時(shí)模擬仿真程序中還加入了輔助功能,比如進(jìn)程的查詢,實(shí)時(shí)創(chuàng)建新進(jìn)程和強(qiáng)制刪除的進(jìn)程等,這樣使得模擬仿真程序更加符合實(shí)際的進(jìn)程運(yùn)行狀態(tài).[4]整體設(shè)計(jì)如圖3所示.
圖3 整體設(shè)計(jì)圖
進(jìn)程是通過(guò)進(jìn)程控制塊來(lái)進(jìn)行刻畫(huà)和描述,利用C語(yǔ)言的結(jié)構(gòu)體來(lái)進(jìn)行具體實(shí)現(xiàn),用結(jié)構(gòu)體模擬進(jìn)程控制塊如下:
struct PCB
{
int id; //進(jìn)程的ID號(hào)
int state; //進(jìn)程的狀態(tài)
char name[10]; //進(jìn)程的名稱
inttotaltime; //進(jìn)程運(yùn)行的總時(shí)間
int waitflag; // 進(jìn)程是否處于等待狀態(tài)的標(biāo)識(shí)符
struct PCB*next;
};
由于本文設(shè)計(jì)的進(jìn)程調(diào)度是利用先進(jìn)先出的方式進(jìn)行,而數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列模型具有先進(jìn)先出的特點(diǎn),[5]因此可以通過(guò)數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列對(duì)進(jìn)程進(jìn)行管理.本文分別利用就緒和等待兩條隊(duì)列對(duì)進(jìn)程進(jìn)行管理,利用單鏈表生成隊(duì)列.結(jié)構(gòu)體中的變量waitflag是創(chuàng)建進(jìn)程生成的隨機(jī)數(shù),是用來(lái)標(biāo)識(shí)當(dāng)進(jìn)程在處理器上運(yùn)行結(jié)束后,應(yīng)進(jìn)入等待隊(duì)列還是就緒隊(duì)列,以此模擬進(jìn)程的狀態(tài)切換.
本文利用兩個(gè)線程模擬進(jìn)程的調(diào)度和喚醒.線程一是用來(lái)模擬進(jìn)程的調(diào)度,首先輪詢就緒隊(duì)列,利用先進(jìn)先出的方式從就緒隊(duì)列中選中進(jìn)程進(jìn)行運(yùn)行,然后當(dāng)運(yùn)行的時(shí)間到了一個(gè)時(shí)間片后,如果進(jìn)程的等待標(biāo)識(shí)waitflag為偶數(shù)時(shí),將進(jìn)程放回到就緒隊(duì)列的末尾;如果進(jìn)程的等待標(biāo)識(shí)waitflag為奇數(shù)時(shí),將進(jìn)程放回到就等待列的末尾;然后線程一再取出下一個(gè)就緒隊(duì)列中的進(jìn)程進(jìn)行運(yùn)行.線程二是用來(lái)模擬進(jìn)程的喚醒,首先輪詢等待隊(duì)列,利用先進(jìn)先出的方式從等待隊(duì)列中選中進(jìn)程,將進(jìn)程的waitflag加1,就喚醒了進(jìn)程,然后將進(jìn)程放入就緒隊(duì)列的末尾.兩個(gè)線程通過(guò)對(duì)隊(duì)列的加鎖來(lái)解決進(jìn)程的互斥訪問(wèn)隊(duì)列問(wèn)題.[6]
為了更好的達(dá)到模擬在操作系統(tǒng)運(yùn)行的效果,本文加入了輔助管理進(jìn)程的三個(gè)功能.功能一是通過(guò)命令方式查看進(jìn)程的信息,通過(guò)輪詢兩個(gè)進(jìn)程對(duì)列,了解每個(gè)進(jìn)程當(dāng)前的狀態(tài).功能二通過(guò)命令的方式創(chuàng)建新的進(jìn)程,插入到就緒隊(duì)列的末尾;功能三通過(guò)命令的方式強(qiáng)制刪除正在運(yùn)行的進(jìn)程.這里的輔助功能和操作系統(tǒng)中的任務(wù)管理器非常相似.
本文的測(cè)試是在Linux系統(tǒng)的環(huán)境下進(jìn)行.圖4(a)為模擬程序運(yùn)行時(shí)進(jìn)程輪轉(zhuǎn)運(yùn)行的結(jié)果,圖4(b)為輔助功能中查詢進(jìn)程的結(jié)果,圖4(c)為添加進(jìn)程的結(jié)果,圖4(d)為刪除進(jìn)程的結(jié)果.從測(cè)試的結(jié)果可以看出模擬程序達(dá)到了很好的仿真效果.
圖4 測(cè)試結(jié)果圖
針對(duì)目前操作系統(tǒng)中進(jìn)程概念和進(jìn)程調(diào)度管理算法學(xué)習(xí)和理解上的困難,本文提出了利用多線程模擬進(jìn)程時(shí)間片輪轉(zhuǎn)的調(diào)度算法,使得進(jìn)程的調(diào)度和管理更容易理解.本文首先深入分析了進(jìn)程的概念和調(diào)度算法流程以及數(shù)據(jù)結(jié)構(gòu)的描述方式,然后在Linux環(huán)境下利用C語(yǔ)言進(jìn)行了實(shí)現(xiàn),經(jīng)過(guò)測(cè)試,模擬程序達(dá)到了很好的進(jìn)程調(diào)度仿真效果,這為操作系統(tǒng)的教學(xué)提供了較好的輔助手段.
[1](美)西爾伯斯查茲,(美)高爾文·加根.操作系統(tǒng)概念[M].鄭和根,譯.北京:高等教育出版社,2010:45-68.
[2]陳紅葉.操作系統(tǒng)原理開(kāi)放性實(shí)踐教學(xué)[J].實(shí)驗(yàn)室研究與探索,2009(12):75-77.
[3]SILBERSCHATZ A.App lied Opertion System Concepts[M ].John Wiley &Sons,Inc,2001:38-56.
[4]楊 瑞.操作系統(tǒng)實(shí)驗(yàn)環(huán)境的設(shè)計(jì)與實(shí)現(xiàn)[D].呼和浩特:內(nèi)蒙古大學(xué)碩士學(xué)位論文,2012:6-10.
[5]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu):第二版[M].北京:清華大學(xué)出版社,2012:13-17.
[6]章德賓,胡 斌,張金隆.多線程技術(shù)與分布式并發(fā)離散事件仿真[J].計(jì)算機(jī)仿真,2007(1):97-100.