Ｊａｖａ語言在進程管理教學中的應用

邵奇峰

文章編號：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.