多線程模擬進(jìn)程時(shí)間片輪轉(zhuǎn)調(diào)度算法研究

湯元斌

（四川文理學(xué)院 現(xiàn)代教育技術(shù)中心，四川 達(dá)州635000）

0 引言

操作系統(tǒng)是管理軟硬件資源、控制程序執(zhí)行，改善人機(jī)界面交互，合理組織計(jì)算機(jī)工作流程和為用戶使用計(jì)算機(jī)提供良好運(yùn)行環(huán)境的一種系統(tǒng)軟件，因此它是計(jì)算機(jī)系統(tǒng)運(yùn)行的核心.[1]進(jìn)程是程序的一次執(zhí)行過程，是操作系統(tǒng)進(jìn)行資源調(diào)度和管理的一個(gè)獨(dú)立單位，是在操作系統(tǒng)學(xué)習(xí)過程中需要重點(diǎn)理解和掌握的概念.但由于其理論性強(qiáng)，進(jìn)程的運(yùn)行工作原理和算法比較抽象難懂，學(xué)生掌握起來非常困難.為了讓學(xué)生更好地理解掌握操作系統(tǒng)中進(jìn)程這一概念及其調(diào)度算法.本文在多線程的基礎(chǔ)上設(shè)計(jì)開發(fā)了進(jìn)程時(shí)間片輪轉(zhuǎn)調(diào)度的模擬仿真程序，經(jīng)過測試，該模擬程序可以較好地輔助學(xué)生學(xué)習(xí)和掌握進(jìn)程的概念及其調(diào)度算法，對學(xué)生有效學(xué)習(xí)和理解操作系統(tǒng)的進(jìn)程調(diào)度算法具有重要的指導(dǎo)意義.

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

在多任務(wù)環(huán)境下，為了能更好地并發(fā)處理各種程序，操作系統(tǒng)中引入了進(jìn)程這一概念.進(jìn)程是程序關(guān)于某個(gè)數(shù)據(jù)集合的可并發(fā)執(zhí)行的具有獨(dú)立功能的一次執(zhí)行過程，也是操作系統(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]

1.1 進(jìn)程的描述

在操作系統(tǒng)中，有一種非常重要的用來刻畫進(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)識進(jìn)程唯一的標(biāo)識符；② 處理機(jī)狀態(tài)信息，即處理機(jī)中各種寄存器中的內(nèi)容；③ 進(jìn)程調(diào)度信息，即存放于PCB中的關(guān)于進(jìn)程調(diào)度和進(jìn)程切換的信息；④ 進(jìn)程控制信息，即程序和數(shù)據(jù)的地址、鏈接指針、資源清單等.

1.2 進(jìn)程狀態(tài)及切換

進(jìn)程在操作系統(tǒng)中是一個(gè)動(dòng)態(tài)的概念，它是程序在數(shù)據(jù)集合上的一次執(zhí)行過程，因此進(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í)無法運(yùn)行的狀態(tài)；終止?fàn)顟B(tài)，是在進(jìn)程運(yùn)行結(jié)束后釋放資源過程中的狀態(tài).進(jìn)程的各種狀態(tài)之間可以互相切換，但進(jìn)程總是處于某一種狀態(tài)中.

圖1 進(jìn)程狀態(tài)轉(zhuǎn)換圖

1.3 進(jìn)程的調(diào)度和管理

如圖2所示，進(jìn)程是利用進(jìn)程隊(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í)行的過程中某些資源得不到滿足，就會(huì)進(jìn)入等待隊(duì)列中；當(dāng)進(jìn)程在CPU上運(yùn)行結(jié)束，就會(huì)釋放資源，然后消失.

圖2 進(jìn)程調(diào)度和管理流程圖

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

時(shí)間片輪轉(zhuǎn)算法[3]的基本原理為：將CPU的處理時(shí)間劃分成一個(gè)個(gè)小的時(shí)間片，然后將處于就緒隊(duì)列中的各個(gè)進(jìn)程按照先來先服務(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)行.

2 進(jìn)程調(diào)度和管理模擬

2.1 模擬程序總體設(shè)計(jì)

為了模擬上文中進(jìn)程、進(jìn)程的狀態(tài)以及進(jìn)程的時(shí)間片輪轉(zhuǎn)調(diào)度，本文在Linux的環(huán)境下用C語言進(jìn)行了模擬仿真，首先利用結(jié)構(gòu)體描述進(jìn)程，其次用兩個(gè)隊(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ì)圖

2.2 進(jìn)程描述和管理

進(jìn)程是通過進(jìn)程控制塊來進(jìn)行刻畫和描述，利用C語言的結(jié)構(gòu)體來進(jìn)行具體實(shí)現(xiàn)，用結(jié)構(gòu)體模擬進(jìn)程控制塊如下：

struct PCB

｛

int id； ／／進(jìn)程的ID號

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)識符

struct PCB＊next；

｝；

由于本文設(shè)計(jì)的進(jìn)程調(diào)度是利用先進(jìn)先出的方式進(jìn)行，而數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列模型具有先進(jìn)先出的特點(diǎn)，[5]因此可以通過數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列對進(jìn)程進(jìn)行管理.本文分別利用就緒和等待兩條隊(duì)列對進(jìn)程進(jìn)行管理，利用單鏈表生成隊(duì)列.結(jié)構(gòu)體中的變量waitflag是創(chuàng)建進(jìn)程生成的隨機(jī)數(shù)，是用來標(biāo)識當(dāng)進(jìn)程在處理器上運(yùn)行結(jié)束后，應(yīng)進(jìn)入等待隊(duì)列還是就緒隊(duì)列，以此模擬進(jìn)程的狀態(tài)切換.

2.3 多線程

本文利用兩個(gè)線程模擬進(jìn)程的調(diào)度和喚醒.線程一是用來模擬進(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)識waitflag為偶數(shù)時(shí)，將進(jìn)程放回到就緒隊(duì)列的末尾；如果進(jìn)程的等待標(biāo)識waitflag為奇數(shù)時(shí)，將進(jìn)程放回到就等待列的末尾；然后線程一再取出下一個(gè)就緒隊(duì)列中的進(jìn)程進(jìn)行運(yùn)行.線程二是用來模擬進(jìn)程的喚醒，首先輪詢等待隊(duì)列，利用先進(jìn)先出的方式從等待隊(duì)列中選中進(jìn)程，將進(jìn)程的waitflag加1，就喚醒了進(jìn)程，然后將進(jìn)程放入就緒隊(duì)列的末尾.兩個(gè)線程通過對隊(duì)列的加鎖來解決進(jìn)程的互斥訪問隊(duì)列問題.[6]

2.4 輔助功能

為了更好的達(dá)到模擬在操作系統(tǒng)運(yùn)行的效果，本文加入了輔助管理進(jìn)程的三個(gè)功能.功能一是通過命令方式查看進(jìn)程的信息，通過輪詢兩個(gè)進(jìn)程對列，了解每個(gè)進(jìn)程當(dāng)前的狀態(tài).功能二通過命令的方式創(chuàng)建新的進(jìn)程，插入到就緒隊(duì)列的末尾；功能三通過命令的方式強(qiáng)制刪除正在運(yùn)行的進(jìn)程.這里的輔助功能和操作系統(tǒng)中的任務(wù)管理器非常相似.

3 測試結(jié)果

本文的測試是在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é)果.從測試的結(jié)果可以看出模擬程序達(dá)到了很好的仿真效果.

圖4 測試結(jié)果圖

4 結(jié)語

針對目前操作系統(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語言進(jìn)行了實(shí)現(xiàn)，經(jīng)過測試，模擬程序達(dá)到了很好的進(jìn)程調(diào)度仿真效果，這為操作系統(tǒng)的教學(xué)提供了較好的輔助手段.

[1]（美）西爾伯斯查茲，（美）高爾文·加根.操作系統(tǒng)概念[M].鄭和根，譯.北京：高等教育出版社，2010：45-68.

[2]陳紅葉.操作系統(tǒng)原理開放性實(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.