读者优先级调度和写者优先级调度算法的改进

江 波

(贺州学院 计算机科学与工程系,广西 贺州 542800)

读者优先级调度和写者优先级调度算法的改进

江 波

(贺州学院 计算机科学与工程系,广西 贺州 542800)

用P/V操作来解决操作系统中的读写者问题,是并发技术的基本功能。文章对读者具有优先权、写者具有优先权和读者/写者公平竞争算法进行研究,并对读者优先和写者优先算法进行改进。仿真实验表明,改进的算法在各种测试数据下能用正确的时序解决读写者问题,对临界资源的访问也是正确的。

P/V操作;读者优先级调度;写者优先级调度;读者与写者公平竞争

1 引 言

并发是操作系统的一个基本特征,是操作系统设计的基础[1]P157-169。在早期的多道程序设计系统中,一个关键的问题就是要解决并发进程中的同步、互斥和死锁,这也是研究者所关注的热点[2]P203-206。随着计算机技术和网络技术的不断发展,又涌现出对称多处理器和分布式操作系统(如集群系统、对等网络系统和网格等),同步和互斥在这些新出现的操作系统中也得到了扩充和更新[3]P58-72。进程间通信是用P/V操作来实现读写者问题,其解决方案主要有读者具有优先权、写者具有优先权、读者与写者公平竞争方案[4]P65-69。

2 P/V操作实现读/写者问题

读/写者问题需要为数据库访问建立了一个模型:具有一个数据区(可以是一个文件、主存的一个空间块,或者是一组寄存器),多个进程可以其数据;存在一些只读数据进程(reader,读者)和一些写数据的进程(writer,写者)。

2.1 读者优先级调度

读者优先级调度必须满足两个条件:

2.1.1 有写者正在写数据时,读者必须等待。

2.1.2 无读者正在读数据时,写者才可以写数据。

为了满足这两个条件,引入记录当前正在运行的读者进程数(ReaderCount,全局整型量), ReaderCount赋初值0,当一个读者进程进入系统时,ReaderCount执行加1操作;当ReaderCount由0变为l时,表示第一个读者进程进入该系统,需要该读者进程对控制写者进程的互斥信号量mutex-wsem执行P操作,以便与写者进程互斥;当ReaderCount由非0值增加时,表示不是第一个读者进程进入系统,不需要再对互斥信号量mutex-wsem执行P操作;当有读者进程退出系统时,必须对ReaderCount执行减1操作;当如ReaderCount等于0时,表明最后一个读者进程退出系统,需要该读者进程对mutex-wsem执行V操作,让写者进程能够进入系统。

2.2 写者优先级调度

写者优先级调度必须满足两个条件:

2.2.1 无写者时才允许读者读数据。

2.2.2 唤醒时优先考虑写者。

在读者优先算法的基础上,引入写者处于等待状态的注册标记(mutex-rsem,互斥信号量),用于在写者进程到达时封锁后续的读者进程。引入记录当前写者数(WriterCount,全局整型量),当WriterCount等于0时,表明所有的写者执行的操作结束,需要释放读者进程等待队列中的一个读者。

2.3 读者与写者公平竞争算法

读者与写者公平竞争要求读者和写者完全遵循先来先服务的原则使用数据。

读者优先算法之造成写者暂时不能访问数据,被随后源源不断而来的读者插队而长时间挂起,主要的原因是:如果已经有读者在读数据,则说明目前没有写者在访问数据,因此该读者不需要再进行与写者进程间对数据的竞争尝试,从而直接进入读状态。该算法的最大缺陷是只考虑到有没有写者正在访问数据,却没有考虑可能已经有写者在等待访问数据。同理,写者优先算法同样具有缺陷。

3 读/写者算法的改进

3.1 改进的读者优先级调度算法

当有多个读者进程共享一个数据区,根据所执行的不同任务,将读者进行分为两组,分属1组和2组。不同组中的读者不会同时读数据,但同组中的读者可以同时读数据。为了记录两组当前正在运行的读者进程数,分别引入全局整型量Reader1Count、Reader2Count和互斥信号量mutex-Reader1Count、mutex-Reader2Count。

3.2 改进的写者优先级调度

参照改进的读者优先级调度算法,写者也分属1组和2组。不允许多个写者(同组或者不同组)同时对数据进行写操作,每个写者在已知有本组写者正在写文件的情况下,进入等待状态,但具有比另外一组中处于等待状态的写者优先的唤醒权。为了记录两组当前正在运行的写者进程数,分别引入全局整型量Writer1Count、Writer2Count和互斥信号量mutex Writer1Count、mutex Writer2Count。

4 系统仿真实验

测试系统为Windows XP,编程工具为Microsoft Visual C++6.0,在thread.dat文件中输入读者和写者状态,运行程序。在选择界面选择所要使用的算法(如图1),就会得出读者和写者执行的序列。4.1测试的过程必须包含各方面的数据(如表1所示),以便对算法更好地进行测试。由于只是判断这两个算法的功能以及它们的运行结果是否和预知的结果一致,因此在实验的过程中采用黑盒测试方法,考虑三种情况:

图1 算法选择界面

4.1.1 输入的所有线程都是读者,读者在同一时刻竞争资源。

4.1.2 输入的所有线程都是写者,写者在同一时刻竞争资源。

4.1.3 输入的线程包含读者和写者,读者和写者在同一时刻竞争资源。

4.2 读者优先级调度算法测试结果

采用读者优先级调度算法对三组测试数据进行实验,得到的结果如图2-4所示。

从图2-4可以看出,实验结果和预期的结果一致。

4.3 写者优先算法测试结果

采用写者优先级调度算法对三组测试数据进行实验,得到的结果如图5-7所示。

图5 第一组数据的写者优先算法结果

从图5-7可以看出,实验结果和预期的结果一致。

5 结论

用P/V操作来解决操作系统中的读写者问题,是并发技术的基本功能。通过本文的仿真实验结果可以看出。改进的算法能正确的解决读写者问题,在各种测试数据下能用正确的时序解决问题,对临界资源的访问也是正确的,给每个线程设置一个时间变量来记录等待时间,当等待时间过长时,可以提高其优先级,让其进入临界区执行,从而解决饿死问题。

[1]B.Brandenburg,J.Calandrino,and J.Anderson.On the scalability of real-time scheduling algorithms on multicore platforms:A case study.In Proc.of the 29th IEEE Real-Time Systems Symposium,2008.

[2]申雪琴.计算机操作系统中死锁问题研究.计算机与数字工程,2008,36(7).

[3]张俊然,陈 波.基于进化算法的嵌入式操作系统并发性能测试.计算机工程,2005,31(23).

[4]王欣明,金蓓弘,张 昕.用不对称的P/V操作设计并发算法[J].计算机工程与应用,2005,41(12).

The Improved Algorithms of Readers Priority Scheduling and Writers Priority Scheduling

Jiang Bo

(Department of Computer Science and Engineering,Hezhou University,Guangxi Hezhou,542800,China)

To solve the problem of reading and writing problems in the operating system with the P/V operations is a basic function in the concurrency control technique.In this paper,we study the readers priority scheduling algorithm,writers priority scheduling algorithm and readers/writer algorithm for fair competition and improve the readers priority scheduling algorithm,writers priority scheduling algorithm.Simulation results show that the improved algorithm can solve the problem of reading and writing problems correctly.In a variety of test data,it can be used under the right timing to solve the problem and the access to critical resources is corrected.

P/V operations;readers priority scheduling algorithm;writers priority scheduling algorithm;readers/writer algorithm for fair competition

TP316.4

A

1673-8861(2010)02-0122-04

2010-04-01

江 波(1970-),男,广西贺州市人,贺州学院讲师。主要研究方向:数据挖掘、计算机教育、网络安全。