操作系统中进程同步算法的仿真研究

李乃健，田纪宏，胥国伟，齐英杰

（济宁医学院医学信息工程学院，日照 276825）

0 引言

计算机真正完成一项具体任务，必须要借助操作系统中的进程来完成，进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位，但从计算机的效率考察，为了减少系统对于并发所带来的时/空开销，将拥有资源所有权的仍称为进程，而调度的单位称为线程，或轻量级进程，故线程是进程内一个相对独立的执行流或控制流，是处理机分配的实体。它本身不拥有系统资源，但与同属一个进程的其他线程共享进程所拥有的全部资源，进程和多线程的关系如图1所示。

图1 进程与线程的关系图

1 进程同步

在操作系统课程中，进程同步是对多个相关进程在执行次序上进行协调，使并发执行的诸进程之间能够按照一定的规则（或时序）共享系统资源，并能很好地相互合作，从而使程序的执行具有可再现性。从该定义中不难得出：进程同步解决的是同步的诸进程之间执行次序的问题，其目的是协调多个并发进程的执行，使它们高效地共享系统中的资源并更好地相互合作，从而保证程序的执行具有可再现性，使系统资源利用最大化，进而保障系统的稳定性与可靠性。

2 实现进程同步算法的技术

2.1 JJaavvaa内在支持多线程技术

Java语言作为一种面向对象且与平台无关的多线程动态语言，具有支持多线程、解释运行效率高、动态性、语法简单等优点，其中最重要的是支持多线程编程。所有Java类都有一个共同的父类：Object类。Ob⁃ject类有涉及线程同步的notify（）、notifyAll（）、wait（）、wait（long timeOut）等函数，这些函数可以很好地唤醒或阻塞在当前对象监视器上等待线程。Java中线程有4个状态，创建状态、可运行状态、运行状态、撤消状态，如图2所示。

图2 Java中线程的状态转换

在单个程序中同时运行多个线程完成不同的工作，称为多线程。进程可以看作程序运行时的一个实例，而线程则可看作单独地占有CPU执行的代码，基于这种思想，使用支持多线程的Java语言编程比其他语言更为简单与高效。Java中实现多线程编程有两种主要方法：一种是继承Thread类，通过定义java.lang包中的Thread类的子类并在子类中重写run（）方法。由于Java不能多重继承，此方法简单但不灵活；另一种是实现Runnable接口，该接口只有一个run（）方法，要实现此接口就必须定义run（）方法的具体内容，方法体内可定义用户要做的操作，然后以这个实现了Runnable接口的类为参数创建Thread类的对象，也就是用Run⁃nable接口的目标对象初始化Thread类的对象，这样就可把用户实现的run（）方法继承过来。

2.2 多线程编程的重要性

首先，使用多线程技术后，可以在同一时间内运行更多不同种类的任务，在开发难度和性能上都比单线程更好。其次，由于Java语言实现了多线程技术，所以比C、C++等语言实现的算法更为健壮，稳定性更好。再者，Java语言是首个在语言级别提供对多线程程序设计支持的编程语言，借助Java语言的多线程机制，开发多线程应用程序的过程得到大大简化。而且Java语言引入了并发机制来避免可能出现的数据访问冲突问题。

3 经典进程同步算法的仿真实现

3.1 生产者-消费者问题

（1）问题分析与设计

生产者-消费者问题是一个经典的进程同步问题，问题描述为：生产者进程与消费者进程能要想并发执行，需在两者之间设置一个具有n个缓冲区（多缓冲区）的缓冲池，生产者进程将其所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品消费。不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的满缓冲区中投放产品。

凭借Java语言多线程编程技术的优势，用线程模拟生产者与消费者，采用已经在Java语言内部实现了同步机制的阻塞队列（BlockingQueue）模拟生产者与消费者队列，利用生产者类Producer与消费者类Consum⁃er通过实现Runnable接口来的方式创建并实例化线程对象producer与consumer（打破了扩充Thread类与单继承的限制）。此方法不需要人为地考虑线程何时等待与何时唤醒以及如何清空缓冲区的问题，从而简化了代码的编写，并且减少了系统的开销，提高了系统的资源利用率与吞吐量，实现系统资源利用最大化，更提高了程序执行的并发度。在代码中只新建了一个缓冲区类Buffer，并且采用匿名内部类方式创建并实例化生产者、消费者线程对象，重写了线程的run（）方法作为线程的主体来完成对缓冲队列LinkedBlockingQueue的操作。阻塞队列提供的开箱即用的get（）与set（）方法能够自动地阻塞线程，在主方法中定义了一个大小为3个线程的缓冲区队列和生产者阻塞队列Producer、消费者阻塞队列Consumer，它们都采用FIFO（先进先出）策略对线程进行调度。用同一个缓冲区对象buffer分别实例化了两个生产者线程与两个消费者线程，使他们并发执行。通过Random实例化的对象r调用nextInt（100）方法会产生0～100内的随机数作为实参传给get（）方法的形参data，完成生产操作；消费者线程通过调用take（）方法从缓冲区队列中取出产品data完成消费操作。

（2）部分代码实现

Java部分代码如下：

3.2 读者-写者问题

（1）问题分析与设计

读者-写者问题也是一个经典的进程同步问题。所谓读者-写者问题（The Reader-Writer Problem），是指保证一个Writer进程必须与其他进程互斥地访问共享对象的同步问题。该问题主要描述的是怎样保证系统中的若干个进程对某数据文件或记录进行正确地读写，从而避免出现文件数据的丢失修改与读脏数据的问题。为了避免读者与写者同时对文件进行读写操作而引起的数据访问错误，下面主要研究采用写者优先的方法。所谓写者优先是指一个写者申请一个共享资源时，如果有读者在读取该资源，则必须封锁后续到来的读者，以便写者对共享资源的修改；当有读者与写者同时等待资源时，写者优先访问共享资源。解决该问题的关键在于解决写者与写者、写者与第一个读者的同步问题。Java不仅支持多线程，而且在Java包中还提供了Lock接口，为多个线程之间的同步提供了互斥锁，lock（）可以实现同步访问。Lock接口的实现提供了更广泛的锁定操作的方法，比使用synchronized方法和语句更加灵活，使算法结构更清晰易读。

代码中只新建了一个类ReadAndWrite，采用匿名内部类的方式创建并实例化两个对象，并分别多次循环调用Read（）与Write（）方法对共享数据进行读与写操作。代码中还使用可重入的互斥锁ReentrantRead⁃WriteLock实现读者与写者的互斥。在Read（）与Write（）方法中设置读锁与写锁，保证写者优先，SX类中的读与写方法操作的数据是一个0与1000之间整型的随机数，本算法还采用了try-catch-finally异常处理机制，当发生异常时程序会自动解锁以处理异常。

（2）部分代码实现

Java部分代码如下：

从运行结果看，该算法成功实现了生产者线程与消费者线程的同步，它简化了开发，可以独立地或并发地编写消费者和生产者；生产者和消费者可以以不同的速度执行；分离的消费者和生产者在功能上能写出更简洁、可读、易维护的代码，故应用多线程技术，大大提高了系统效率。

从运行结果来看，本算法很好地实现了“读者-写者”问题中写者优先的算法，即当有多个写者等待时后续的读者全部阻塞，直到所有写者全部写完后读者才能读取，多个写者之间并发执行，而且读者读取的都是最后一个写者修改后的数据。以Java多线程技术与提供的同步机制，有效避免了数据访问冲突与数据操作错误，即读者读取的数据为最后一个写者操作后的数据。

4 结语

通过使用Java语言的多线程技术，仿真实现了生产者-消费者、读者-写者问题的进程同步算法。实现了生产者与消费者互斥地使用缓冲区，尤其是Runna⁃ble接口实现了多个线程共同完成一个任务的功能；实现了写者优先的功能，诸读者与诸写者之间各自并发运行，而且保证读者读取数据为最后一个写者操作后的数据，从而避免了很多算法中都未曾处理的潜在的数据冲突和数据访问错误等问题。这些仿真实现，优化了算法的内部结构，补充算法的部分功能，增强算法的可读性和实用性，提高系统资源的利用率,充分发挥系统的性能。

参考文献：

[1]孔德凤，应时.基于Java线程机制研究生产者-消费者问题.信息与电脑[J]，2017（2）.

[2]汤小丹等.计算机操作系统[M].西安：西安电子科技大学出版社，2014.

[3]高洪岩.Java多线程编程核心技术[M].北京：机械工业出版社，2015.

[4]吴仁群.Java基础教程（第二版）[M].北京：清华大学出版社，2012.

[5]史广.Java多线程并发机制的应用探讨[J].贵州师范大学国际教育学院学报，2016.