Ｊａｖａ语言在进程管理教学中的应用

邵奇峰

文章编号：1672-5913(2009)02-0111-03

摘 要：传统操作系统课程以伪语言描述进程管理算法有诸多不足，本文提出了将Java语言应用于进程管理教学的具体方案，论述了Java语言描述进程概念与算法的详细实现，且针对经典同步问题给出了Java语言并发包的高级API实现。

关键词：进程；线程；Java；同步

中图分类号：G642

文献标识码：B

1 引言

操作系统是计算机科学专业的核心课程，其中的进程管理部分不但是操作系统课程的重点，而且是其难点中的难点，很多学生直到研究生毕业仍没真正理解其实质。当前硬件多核时代已经来临，以往并发程序设计只出现在服务器应用中，如今连客户机应用也对并发程序设计提出了迫切的需求，因此就要求学生对作为并发程序设计基础的进程管理，不但要深刻掌握其核心理论，而且能熟练应用于实践之中。目前多数操作系统教材采用伪语言描述进程管理的相关算法，学生只能被动的阅读和分析，不能直观的察看运行结果、监控运行过程和修改调试代码，这就限制了学生对理论的深入理解和技术的实践应用。现代操作系统都以多线程进程的形式提供并发，Java语言的并发API对多线程程序设计提供了由低级到高级的完整API支持，笔者在教学中采用Java语言描述进程管理的概念与算法，不但使学生深入浅出的掌握了核心理论，而且使学生能立即将其应用于实践之中，收到了显著的效果。

2 Java语言描述进程基本概念

2.1 线程的异步性

线程的异步性是由于多个线程异步的并发修改同一数据引起的。以下代码创建了100个线程，每个线程异步的向account对象中增加1分钱，运行该程序会发现最终结果并非100，而且每次运行结果都不相同。通过该程序可使学生直观的观察到线程异步性的问题，教师可在此基础上提出竞争条件和临界区等基本概念，然后引入同步机制解决该代码的异步问题，如此学生可深刻意识到操作系统理论解决实际问题的重要性，产生对后续理论深入学习的兴趣。

import java.util.concurrent.*;

public class AccountWithoutSync {

private static Account account = new Account();

public static void main(String[] args) {

ExecutorService executor = Executors. newCachedThreadPool();

// Create and launch 100 threads

for (int i = 0; i < 100; i++) {

executor.execute(new AddAPennyTask()); }

executor.shutdown();

// Wait until all tasks are finished

while (!executor.isTerminated()) { }

System.out.println("What is balance? " + account.getBalance()); }

// A thread for adding a penny to the account

private static class AddAPennyTask implements Runnable {

public void run() {

account.deposit(1); } }

// An inner class for account

private static class Account {

private int balance = 0;

public int getBalance() {

return balance; }

public void deposit(int amount) {

int newBalance = balance + amount;

// This delay is deliberately added to magnify the data-corruption problem and

// make it easy to see.

try {

Thread.sleep(5); }

catch (InterruptedException ex) { }

balance = newBalance; } } }

2.2 信号量

信号量(Semaphore)由Edsger Dijkstra于60年代提出，其主要用于限制访问共享资源的线程数目[1]，Java语言中的Semaphore类即是信号量概念的具体实现，其用法如下：

Semaphore sem = new Semaphore(n);

try{

sem.acquire(); //P操作

//critical section

}catch(InterruptedException ie){ }

finally{

sem.release(); //V操作

}

//remainder section

教师可在介绍其内部实现原理后，让学生用二元信号量(binary semaphore)解决2.1中的代码异步问题，立即将理论应用于实践，以加深对理论的理解。

2.3 管程

管程(Monitor)是由Brinch Hansen和Tony Hoare于70年代提出的一种高级同步原语[2]，寻常系统中已很少看到具体实现，以至许多学生甚至教师认为其仅是理想化的概念，所以通过伪语言很难向学生阐明其便利性和高效性。其实Java语言提供的synchronized同步锁即为管程的实现，Java语言的每个对象都有一个隐含锁(Lock)和一个内置条件变量(Condition)，如图1所示，等待获取对象锁的线程都在该对象的进入队列(entry set)中，因条件变量阻塞的线程都在该条件所对应的队列(wait set)中。

管程的发明者Brinch Hansen于1999年曾撰文对Java语言的管程的实现提出了中肯的评价。以下代码利用synchronized同步锁的管程实现展示了线程间的协作关系。

//Thread1

synchronized (anObject) {

try {

// Wait for the condition to become true

while (!condition)

anObject.wait();

// Do something when condition is true

}catch (InterruptedException ex) {

ex.printStackTrace(); } }

//Thread2

synchronized (anObject) {

// When condition becomes true

anObject.notify(); //or anObject.notify All(); }

3 Java语言描述经典同步问题

3.1 生产者-消费者问题

生产者-消费者(producer-consumer)问题也就是有界缓冲区(bounded-buffer)问题，即生产者不断的往有界缓冲区中放产品，消费者不断从中取产品，在保证两者互斥的基础上，当缓冲区满时生产者要阻塞，等待消费者取产品后将其唤醒，当缓冲区空时消费者要阻塞，等待生产者放产品后将其唤醒。用Java信号量描述的算法如下：

//互斥信号量

Semaphore mutex =new Semaphore(1);

//空缓冲区数量

Semaphore empty = new Semaphore(BUFFER_ SIZE);

//满缓冲区数量

Semaphore full = new Semaphore(0);

// producer calls this method

public void insert(Object item) {

empty.acquire();

mutex.acquire();

// add an item to the buffer

buffer[in] = item;

in = (in + 1) % BUFFER_SIZE;

mutex.release();

full.release(); }

// consumer calls this method

public Object remove() {

full.acquire();

mutex.acquire();

// remove an item from the buffer

Object item = buffer[out];

out = (out + 1) % BUFFER_SIZE;

mutex.release();

empty.release();

return item; }

分别创建生产者线程和消费者线程调用相应方法，在程序运行正确后，可调换互斥信号量与资源信号量的位置，学生即可观察到死锁的发生。用Java的synchronized同步锁或ReentrantLock锁也可描述该算法，但传统低级别的API较难使用，易导致程序结构混乱和性能问题，因此Java语言提供了BlockingQueue接口，使得同步操作完全对用户透明。BlockingQueue接口的实现类有ArrayBlockingQueue、LinkedBlockingQueue和Priority BlockingQueue三种，以ArrayBlockingQueue为例描述生产者-消费者问题的算法如下：

ArrayBlockingQueue buffer =

new ArrayBlockingQueue(BUFFER_ SIZE);

// A task for adding an int to the buffer

while (true) {

try {

buffer.put(i++); // Add any value to the buffer

} catch (InterruptedException ex) { } }

// A task for reading and deleting an int from the buffer

while (true) {

try {

buffer.take();

} catch (InterruptedException ex) { } }

通过BlockingQueue接口的使用，使学生看到，随着技术的发展，并发程序设计将会变得更加简单而且逐步普及，从而建立起学习进程管理的信心和兴趣。

3.2 读者-写者问题

读者—写者(Reader-Writer)是保证一个Writer线程必须与其他线程互斥的访问共享对象的同步问题。用Java信号量描述的算法如下：

int readerCount = 0;

Semaphore mutex = new Semaphore(1);

Semaphore writer = new Semaphore(1);

//writer thread

writer.acquire();

//writing is performed

writer.release();

//reader thread

mutex.acquire();

readerCount++;

if (readerCount == 1)

writer.acquire();

mutex.release();

//reading is performed

mutex.acquire();

readerCount--;

if (readerCount == 0)

writer.release();

mutex.release();

同样可用Java的synchronized同步锁或Reentrant Lock锁描述该算法，但Java语言提供的ReentrantReadWriteLock类使得读者-写者问题的编程更为简单，且其比synchronized同步锁具有更高的并发性能，算法如下：

ReentrantReadWriteLock rwl =

new ReentrantReadWriteLock();

//Extract read and write locks

Lock readLock = rwl.readLock();

Lock writeLock = rwl.writeLock();

//Use the read lock in all accessors:

readLock.lock();

try { . . . }

finally { readLock.unlock(); }

//Use the write lock in all mutators:

writeLock.lock();

try { . . . }

finally { writeLock.unlock(); }

修改ReentrantReadWriteLock类的构造方法，可分别实现写者优先和读者优先算法，简单的修改代码，学生便可直观的观测到两种策略的不同结果。

3.3 哲学家进餐问题

由Dijkstra引入的哲学家进餐问题是需要在多个线程之间分配多个资源且不会出现死锁和饥饿形式的简单表示[3]。用Java信号量描述的算法如下：

Semaphore[] chopStick = new Semaphore[5];

for(int i=0; i<5; i++)

chopStick[i] = new Semaphore(1);

while (true) {

//get left chopstick

chopStick[i].acquire();

//get right chopstick

chopStick[(i+1) % 5].acquire();

eating();

//return left chopstick

chopStick[i].release();

chopStick[(i+1) % 5].release();

thinking();

}

学生可运行并修改程序以观察死锁和饥饿问题，然后对其改进以解决死锁和饥饿问题。通过运行真实的代码，学生就有了真实的经验，传统的伪语言或动画模拟是无法达到该效果的。

4结束语

Java语言还提供了ConcurrentHashMap和Concurrent LinkedQueue等线程安全的集合框架，提供了Thread pool、Scheduler、Future、CyclicBarrier、CountDownLatch、Exchanger和SynchronousQueue等多线程工具，还为专家提供用于开发高级lock-free算法的Atomic。因此以Java语言描述进程管理相关算法，不但有助于基本概念与原理的讲授，而且学生能够实现真实应用及更深入的科学研究，学生深刻体会到理论指导实践的重要性，就会更积极主动的学习操作系统理论。

参考文献：

[1] Andrew Tanenbaum. 现代操作系统[M]. 北京:机械工业出版社,2005.

[2] ABRAHAM SILBERSCHATZ. Operating System Concepts with Java[M]. John Wiley & Sons,2007.

[3] William Stallings. 操作系统:精髓与设计原理[M]. 北京:电子工业出版社,2006.