湯元斌

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

0 引言

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

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

在多任務環(huán)境下，為了能更好地并發(fā)處理各種程序，操作系統(tǒng)中引入了進程這一概念.進程是程序關(guān)于某個數(shù)據(jù)集合的可并發(fā)執(zhí)行的具有獨立功能的一次執(zhí)行過程，也是操作系統(tǒng)進行資源分配和調(diào)度的基本單位，具有結(jié)構(gòu)性、共享性、動態(tài)性、獨立性、制約性和并發(fā)性等特征.調(diào)度是指調(diào)用遠方資源分配，而調(diào)度算法是根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法.[2]

1.1 進程的描述

在操作系統(tǒng)中，有一種非常重要的用來刻畫進程的數(shù)據(jù)結(jié)構(gòu)叫進程控制塊，其主要用于記錄操作系統(tǒng)所需和描述進程當前情況以及控制進程運行的全部信息.進程控制塊主要記錄以下四個方面的信息：① 進程的標志信息，即進程名和用于標識進程唯一的標識符；② 處理機狀態(tài)信息，即處理機中各種寄存器中的內(nèi)容；③ 進程調(diào)度信息，即存放于PCB中的關(guān)于進程調(diào)度和進程切換的信息；④ 進程控制信息，即程序和數(shù)據(jù)的地址、鏈接指針、資源清單等.

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

進程在操作系統(tǒng)中是一個動態(tài)的概念，它是程序在數(shù)據(jù)集合上的一次執(zhí)行過程，因此進程在操作系統(tǒng)中執(zhí)行時的異步性決定了進程從出現(xiàn)到消失可能處于多種狀態(tài)，一般定義為五態(tài)模型，如圖1所示.新建狀態(tài)，是操作系統(tǒng)執(zhí)行一個程序時創(chuàng)建了一個子進程狀態(tài)；就緒狀態(tài)，是進程在滿足了一切準備運行的資源后，準備進入CPU進行執(zhí)行的狀態(tài)；運行狀態(tài)，是進程在CPU上執(zhí)行的狀態(tài)；等待狀態(tài)，是進程由于缺少某些資源而處于暫時無法運行的狀態(tài)；終止狀態(tài)，是在進程運行結(jié)束后釋放資源過程中的狀態(tài).進程的各種狀態(tài)之間可以互相切換，但進程總是處于某一種狀態(tài)中.

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

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

如圖2所示，進程是利用進程隊列對各種狀態(tài)下的進程進行調(diào)度和管理.當進程產(chǎn)生時就會進入就緒隊列中，就緒隊列中的進程被選中就會進入CPU中進行執(zhí)行.當進程的運行時間片到了就會進入就緒隊列中；當在CPU執(zhí)行的過程中某些資源得不到滿足，就會進入等待隊列中；當進程在CPU上運行結(jié)束，就會釋放資源，然后消失.

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

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

時間片輪轉(zhuǎn)算法[3]的基本原理為：將CPU的處理時間劃分成一個個小的時間片，然后將處于就緒隊列中的各個進程按照先來先服務原則依次使用CPU資源；當一個進程所分配的時間片用完后就會返回到就緒隊列的末尾進行重新排隊，等待下一次調(diào)度，其所占用的CPU資源會被強迫讓出以便釋放出處理機給另一個就緒的進程，同時就緒隊列中的另一個進程會被進程調(diào)度選中，然后給它分配一個時間片運行.

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

2.1 模擬程序總體設計

為了模擬上文中進程、進程的狀態(tài)以及進程的時間片輪轉(zhuǎn)調(diào)度，本文在Linux的環(huán)境下用C語言進行了模擬仿真，首先利用結(jié)構(gòu)體描述進程，其次用兩個隊列對進程進行管理，然后用兩個線程進行進程的調(diào)度輪轉(zhuǎn)，同時模擬仿真程序中還加入了輔助功能，比如進程的查詢，實時創(chuàng)建新進程和強制刪除的進程等，這樣使得模擬仿真程序更加符合實際的進程運行狀態(tài).[4]整體設計如圖3所示.

圖3 整體設計圖

2.2 進程描述和管理

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

struct PCB

｛

int id； ／／進程的ID號

int state； ／／進程的狀態(tài)

char name[10]； ／／進程的名稱

inttotaltime； ／／進程運行的總時間

int waitflag； ／／ 進程是否處于等待狀態(tài)的標識符

struct PCB＊next；

｝；

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

2.3 多線程

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

2.4 輔助功能

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

3 測試結(jié)果

本文的測試是在Linux系統(tǒng)的環(huán)境下進行.圖4（a）為模擬程序運行時進程輪轉(zhuǎn)運行的結(jié)果，圖4（b）為輔助功能中查詢進程的結(jié)果，圖4（c）為添加進程的結(jié)果，圖4（d）為刪除進程的結(jié)果.從測試的結(jié)果可以看出模擬程序達到了很好的仿真效果.

圖4 測試結(jié)果圖

4 結(jié)語

針對目前操作系統(tǒng)中進程概念和進程調(diào)度管理算法學習和理解上的困難，本文提出了利用多線程模擬進程時間片輪轉(zhuǎn)的調(diào)度算法，使得進程的調(diào)度和管理更容易理解.本文首先深入分析了進程的概念和調(diào)度算法流程以及數(shù)據(jù)結(jié)構(gòu)的描述方式，然后在Linux環(huán)境下利用C語言進行了實現(xiàn)，經(jīng)過測試，模擬程序達到了很好的進程調(diào)度仿真效果，這為操作系統(tǒng)的教學提供了較好的輔助手段.

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

[2]陳紅葉.操作系統(tǒng)原理開放性實踐教學[J].實驗室研究與探索，2009（12）：75-77.

[3]SILBERSCHATZ A.App lied Opertion System Concepts[M ].John Wiley ＆Sons，Inc，2001：38-56.

[4]楊 瑞.操作系統(tǒng)實驗環(huán)境的設計與實現(xiàn)[D].呼和浩特：內(nèi)蒙古大學碩士學位論文，2012：6-10.

[5]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)：第二版[M].北京：清華大學出版社，2012：13-17.

[6]章德賓，胡 斌，張金隆.多線程技術(shù)與分布式并發(fā)離散事件仿真[J].計算機仿真，2007（1）：97-100.