多线程模拟进程时间片轮转调度算法研究

汤元斌

（四川文理学院 现代教育技术中心，四川 达州635000）

0 引言

操作系统是管理软硬件资源、控制程序执行，改善人机界面交互，合理组织计算机工作流程和为用户使用计算机提供良好运行环境的一种系统软件，因此它是计算机系统运行的核心.[1]进程是程序的一次执行过程，是操作系统进行资源调度和管理的一个独立单位，是在操作系统学习过程中需要重点理解和掌握的概念.但由于其理论性强，进程的运行工作原理和算法比较抽象难懂，学生掌握起来非常困难.为了让学生更好地理解掌握操作系统中进程这一概念及其调度算法.本文在多线程的基础上设计开发了进程时间片轮转调度的模拟仿真程序，经过测试，该模拟程序可以较好地辅助学生学习和掌握进程的概念及其调度算法，对学生有效学习和理解操作系统的进程调度算法具有重要的指导意义.

1 进程及其调度算法

在多任务环境下，为了能更好地并发处理各种程序，操作系统中引入了进程这一概念.进程是程序关于某个数据集合的可并发执行的具有独立功能的一次执行过程，也是操作系统进行资源分配和调度的基本单位，具有结构性、共享性、动态性、独立性、制约性和并发性等特征.调度是指调用远方资源分配，而调度算法是根据系统的资源分配策略所规定的资源分配算法.[2]

1.1 进程的描述

在操作系统中，有一种非常重要的用来刻画进程的数据结构叫进程控制块，其主要用于记录操作系统所需和描述进程当前情况以及控制进程运行的全部信息.进程控制块主要记录以下四个方面的信息：① 进程的标志信息，即进程名和用于标识进程唯一的标识符；② 处理机状态信息，即处理机中各种寄存器中的内容；③ 进程调度信息，即存放于PCB中的关于进程调度和进程切换的信息；④ 进程控制信息，即程序和数据的地址、链接指针、资源清单等.

1.2 进程状态及切换

进程在操作系统中是一个动态的概念，它是程序在数据集合上的一次执行过程，因此进程在操作系统中执行时的异步性决定了进程从出现到消失可能处于多种状态，一般定义为五态模型，如图1所示.新建状态，是操作系统执行一个程序时创建了一个子进程状态；就绪状态，是进程在满足了一切准备运行的资源后，准备进入CPU进行执行的状态；运行状态，是进程在CPU上执行的状态；等待状态，是进程由于缺少某些资源而处于暂时无法运行的状态；终止状态，是在进程运行结束后释放资源过程中的状态.进程的各种状态之间可以互相切换，但进程总是处于某一种状态中.

图1 进程状态转换图

1.3 进程的调度和管理

如图2所示，进程是利用进程队列对各种状态下的进程进行调度和管理.当进程产生时就会进入就绪队列中，就绪队列中的进程被选中就会进入CPU中进行执行.当进程的运行时间片到了就会进入就绪队列中；当在CPU执行的过程中某些资源得不到满足，就会进入等待队列中；当进程在CPU上运行结束，就会释放资源，然后消失.

图2 进程调度和管理流程图

1.4 时间片轮转调度算法

时间片轮转算法[3]的基本原理为：将CPU的处理时间划分成一个个小的时间片，然后将处于就绪队列中的各个进程按照先来先服务原则依次使用CPU资源；当一个进程所分配的时间片用完后就会返回到就绪队列的末尾进行重新排队，等待下一次调度，其所占用的CPU资源会被强迫让出以便释放出处理机给另一个就绪的进程，同时就绪队列中的另一个进程会被进程调度选中，然后给它分配一个时间片运行.

2 进程调度和管理模拟

2.1 模拟程序总体设计

为了模拟上文中进程、进程的状态以及进程的时间片轮转调度，本文在Linux的环境下用C语言进行了模拟仿真，首先利用结构体描述进程，其次用两个队列对进程进行管理，然后用两个线程进行进程的调度轮转，同时模拟仿真程序中还加入了辅助功能，比如进程的查询，实时创建新进程和强制删除的进程等，这样使得模拟仿真程序更加符合实际的进程运行状态.[4]整体设计如图3所示.

图3 整体设计图

2.2 进程描述和管理

进程是通过进程控制块来进行刻画和描述，利用C语言的结构体来进行具体实现，用结构体模拟进程控制块如下：

struct PCB

｛

int id； ／／进程的ID号

int state； ／／进程的状态

char name[10]； ／／进程的名称

inttotaltime； ／／进程运行的总时间

int waitflag； ／／ 进程是否处于等待状态的标识符

struct PCB＊next；

｝；

由于本文设计的进程调度是利用先进先出的方式进行，而数据结构中的队列模型具有先进先出的特点，[5]因此可以通过数据结构中的队列对进程进行管理.本文分别利用就绪和等待两条队列对进程进行管理，利用单链表生成队列.结构体中的变量waitflag是创建进程生成的随机数，是用来标识当进程在处理器上运行结束后，应进入等待队列还是就绪队列，以此模拟进程的状态切换.

2.3 多线程

本文利用两个线程模拟进程的调度和唤醒.线程一是用来模拟进程的调度，首先轮询就绪队列，利用先进先出的方式从就绪队列中选中进程进行运行，然后当运行的时间到了一个时间片后，如果进程的等待标识waitflag为偶数时，将进程放回到就绪队列的末尾；如果进程的等待标识waitflag为奇数时，将进程放回到就等待列的末尾；然后线程一再取出下一个就绪队列中的进程进行运行.线程二是用来模拟进程的唤醒，首先轮询等待队列，利用先进先出的方式从等待队列中选中进程，将进程的waitflag加1，就唤醒了进程，然后将进程放入就绪队列的末尾.两个线程通过对队列的加锁来解决进程的互斥访问队列问题.[6]

2.4 辅助功能

为了更好的达到模拟在操作系统运行的效果，本文加入了辅助管理进程的三个功能.功能一是通过命令方式查看进程的信息，通过轮询两个进程对列，了解每个进程当前的状态.功能二通过命令的方式创建新的进程，插入到就绪队列的末尾；功能三通过命令的方式强制删除正在运行的进程.这里的辅助功能和操作系统中的任务管理器非常相似.

3 测试结果

本文的测试是在Linux系统的环境下进行.图4（a）为模拟程序运行时进程轮转运行的结果，图4（b）为辅助功能中查询进程的结果，图4（c）为添加进程的结果，图4（d）为删除进程的结果.从测试的结果可以看出模拟程序达到了很好的仿真效果.

图4 测试结果图

4 结语

针对目前操作系统中进程概念和进程调度管理算法学习和理解上的困难，本文提出了利用多线程模拟进程时间片轮转的调度算法，使得进程的调度和管理更容易理解.本文首先深入分析了进程的概念和调度算法流程以及数据结构的描述方式，然后在Linux环境下利用C语言进行了实现，经过测试，模拟程序达到了很好的进程调度仿真效果，这为操作系统的教学提供了较好的辅助手段.

[1]（美）西尔伯斯查兹，（美）高尔文·加根.操作系统概念[M].郑和根，译.北京：高等教育出版社，2010：45-68.

[2]陈红叶.操作系统原理开放性实践教学[J].实验室研究与探索，2009（12）：75-77.

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

[4]杨 瑞.操作系统实验环境的设计与实现[D].呼和浩特：内蒙古大学硕士学位论文，2012：6-10.

[5]严蔚敏，吴伟民.数据结构：第二版[M].北京：清华大学出版社，2012：13-17.

[6]章德宾，胡 斌，张金隆.多线程技术与分布式并发离散事件仿真[J].计算机仿真，2007（1）：97-100.