Ｊａｖａ語言在進(jìn)程管理教學(xué)中的應(yīng)用

邵奇峰

文章編號(hào)：1672-5913(2009)02-0111-03

摘 要：傳統(tǒng)操作系統(tǒng)課程以偽語言描述進(jìn)程管理算法有諸多不足，本文提出了將Java語言應(yīng)用于進(jìn)程管理教學(xué)的具體方案，論述了Java語言描述進(jìn)程概念與算法的詳細(xì)實(shí)現(xiàn)，且針對(duì)經(jīng)典同步問題給出了Java語言并發(fā)包的高級(jí)API實(shí)現(xiàn)。

關(guān)鍵詞：進(jìn)程；線程；Java；同步

中圖分類號(hào)：G642

文獻(xiàn)標(biāo)識(shí)碼：B

1 引言

操作系統(tǒng)是計(jì)算機(jī)科學(xué)專業(yè)的核心課程，其中的進(jìn)程管理部分不但是操作系統(tǒng)課程的重點(diǎn)，而且是其難點(diǎn)中的難點(diǎn)，很多學(xué)生直到研究生畢業(yè)仍沒真正理解其實(shí)質(zhì)。當(dāng)前硬件多核時(shí)代已經(jīng)來臨，以往并發(fā)程序設(shè)計(jì)只出現(xiàn)在服務(wù)器應(yīng)用中，如今連客戶機(jī)應(yīng)用也對(duì)并發(fā)程序設(shè)計(jì)提出了迫切的需求，因此就要求學(xué)生對(duì)作為并發(fā)程序設(shè)計(jì)基礎(chǔ)的進(jìn)程管理，不但要深刻掌握其核心理論，而且能熟練應(yīng)用于實(shí)踐之中。目前多數(shù)操作系統(tǒng)教材采用偽語言描述進(jìn)程管理的相關(guān)算法，學(xué)生只能被動(dòng)的閱讀和分析，不能直觀的察看運(yùn)行結(jié)果、監(jiān)控運(yùn)行過程和修改調(diào)試代碼，這就限制了學(xué)生對(duì)理論的深入理解和技術(shù)的實(shí)踐應(yīng)用。現(xiàn)代操作系統(tǒng)都以多線程進(jìn)程的形式提供并發(fā)，Java語言的并發(fā)API對(duì)多線程程序設(shè)計(jì)提供了由低級(jí)到高級(jí)的完整API支持，筆者在教學(xué)中采用Java語言描述進(jìn)程管理的概念與算法，不但使學(xué)生深入淺出的掌握了核心理論，而且使學(xué)生能立即將其應(yīng)用于實(shí)踐之中，收到了顯著的效果。

2 Java語言描述進(jìn)程基本概念

2.1 線程的異步性

線程的異步性是由于多個(gè)線程異步的并發(fā)修改同一數(shù)據(jù)引起的。以下代碼創(chuàng)建了100個(gè)線程，每個(gè)線程異步的向account對(duì)象中增加1分錢，運(yùn)行該程序會(huì)發(fā)現(xiàn)最終結(jié)果并非100，而且每次運(yùn)行結(jié)果都不相同。通過該程序可使學(xué)生直觀的觀察到線程異步性的問題，教師可在此基礎(chǔ)上提出競(jìng)爭(zhēng)條件和臨界區(qū)等基本概念，然后引入同步機(jī)制解決該代碼的異步問題，如此學(xué)生可深刻意識(shí)到操作系統(tǒng)理論解決實(shí)際問題的重要性，產(chǎn)生對(duì)后續(xù)理論深入學(xué)習(xí)的興趣。

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 信號(hào)量

信號(hào)量(Semaphore)由Edsger Dijkstra于60年代提出，其主要用于限制訪問共享資源的線程數(shù)目[1]，Java語言中的Semaphore類即是信號(hào)量概念的具體實(shí)現(xiàn)，其用法如下：

Semaphore sem = new Semaphore(n);

try{

sem.acquire(); //P操作

//critical section

}catch(InterruptedException ie){ }

finally{

sem.release(); //V操作

}

//remainder section

教師可在介紹其內(nèi)部實(shí)現(xiàn)原理后，讓學(xué)生用二元信號(hào)量(binary semaphore)解決2.1中的代碼異步問題，立即將理論應(yīng)用于實(shí)踐，以加深對(duì)理論的理解。

2.3 管程

管程(Monitor)是由Brinch Hansen和Tony Hoare于70年代提出的一種高級(jí)同步原語[2]，尋常系統(tǒng)中已很少看到具體實(shí)現(xiàn)，以至許多學(xué)生甚至教師認(rèn)為其僅是理想化的概念，所以通過偽語言很難向?qū)W生闡明其便利性和高效性。其實(shí)Java語言提供的synchronized同步鎖即為管程的實(shí)現(xiàn)，Java語言的每個(gè)對(duì)象都有一個(gè)隱含鎖(Lock)和一個(gè)內(nèi)置條件變量(Condition)，如圖1所示，等待獲取對(duì)象鎖的線程都在該對(duì)象的進(jìn)入隊(duì)列(entry set)中，因條件變量阻塞的線程都在該條件所對(duì)應(yīng)的隊(duì)列(wait set)中。

管程的發(fā)明者Brinch Hansen于1999年曾撰文對(duì)Java語言的管程的實(shí)現(xiàn)提出了中肯的評(píng)價(jià)。以下代碼利用synchronized同步鎖的管程實(shí)現(xiàn)展示了線程間的協(xié)作關(guān)系。

//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語言描述經(jīng)典同步問題

3.1 生產(chǎn)者-消費(fèi)者問題

生產(chǎn)者-消費(fèi)者(producer-consumer)問題也就是有界緩沖區(qū)(bounded-buffer)問題，即生產(chǎn)者不斷的往有界緩沖區(qū)中放產(chǎn)品，消費(fèi)者不斷從中取產(chǎn)品，在保證兩者互斥的基礎(chǔ)上，當(dāng)緩沖區(qū)滿時(shí)生產(chǎn)者要阻塞，等待消費(fèi)者取產(chǎn)品后將其喚醒，當(dāng)緩沖區(qū)空時(shí)消費(fèi)者要阻塞，等待生產(chǎn)者放產(chǎn)品后將其喚醒。用Java信號(hào)量描述的算法如下：

//互斥信號(hào)量

Semaphore mutex =new Semaphore(1);

//空緩沖區(qū)數(shù)量

Semaphore empty = new Semaphore(BUFFER_ SIZE);

//滿緩沖區(qū)數(shù)量

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; }

分別創(chuàng)建生產(chǎn)者線程和消費(fèi)者線程調(diào)用相應(yīng)方法，在程序運(yùn)行正確后，可調(diào)換互斥信號(hào)量與資源信號(hào)量的位置，學(xué)生即可觀察到死鎖的發(fā)生。用Java的synchronized同步鎖或ReentrantLock鎖也可描述該算法，但傳統(tǒng)低級(jí)別的API較難使用，易導(dǎo)致程序結(jié)構(gòu)混亂和性能問題，因此Java語言提供了BlockingQueue接口，使得同步操作完全對(duì)用戶透明。BlockingQueue接口的實(shí)現(xiàn)類有ArrayBlockingQueue、LinkedBlockingQueue和Priority BlockingQueue三種，以ArrayBlockingQueue為例描述生產(chǎn)者-消費(fèi)者問題的算法如下：

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接口的使用，使學(xué)生看到，隨著技術(shù)的發(fā)展，并發(fā)程序設(shè)計(jì)將會(huì)變得更加簡(jiǎn)單而且逐步普及，從而建立起學(xué)習(xí)進(jìn)程管理的信心和興趣。

3.2 讀者-寫者問題

讀者—寫者(Reader-Writer)是保證一個(gè)Writer線程必須與其他線程互斥的訪問共享對(duì)象的同步問題。用Java信號(hào)量描述的算法如下：

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類使得讀者-寫者問題的編程更為簡(jiǎn)單，且其比synchronized同步鎖具有更高的并發(fā)性能，算法如下：

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類的構(gòu)造方法，可分別實(shí)現(xiàn)寫者優(yōu)先和讀者優(yōu)先算法，簡(jiǎn)單的修改代碼，學(xué)生便可直觀的觀測(cè)到兩種策略的不同結(jié)果。

3.3 哲學(xué)家進(jìn)餐問題

由Dijkstra引入的哲學(xué)家進(jìn)餐問題是需要在多個(gè)線程之間分配多個(gè)資源且不會(huì)出現(xiàn)死鎖和饑餓形式的簡(jiǎn)單表示[3]。用Java信號(hào)量描述的算法如下：

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();

}

學(xué)生可運(yùn)行并修改程序以觀察死鎖和饑餓問題，然后對(duì)其改進(jìn)以解決死鎖和饑餓問題。通過運(yùn)行真實(shí)的代碼，學(xué)生就有了真實(shí)的經(jīng)驗(yàn)，傳統(tǒng)的偽語言或動(dòng)畫模擬是無法達(dá)到該效果的。

4結(jié)束語

Java語言還提供了ConcurrentHashMap和Concurrent LinkedQueue等線程安全的集合框架，提供了Thread pool、Scheduler、Future、CyclicBarrier、CountDownLatch、Exchanger和SynchronousQueue等多線程工具，還為專家提供用于開發(fā)高級(jí)lock-free算法的Atomic。因此以Java語言描述進(jìn)程管理相關(guān)算法，不但有助于基本概念與原理的講授，而且學(xué)生能夠?qū)崿F(xiàn)真實(shí)應(yīng)用及更深入的科學(xué)研究，學(xué)生深刻體會(huì)到理論指導(dǎo)實(shí)踐的重要性，就會(huì)更積極主動(dòng)的學(xué)習(xí)操作系統(tǒng)理論。

參考文獻(xiàn)：

[1] Andrew Tanenbaum. 現(xiàn)代操作系統(tǒng)[M]. 北京:機(jī)械工業(yè)出版社,2005.

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

[3] William Stallings. 操作系統(tǒng):精髓與設(shè)計(jì)原理[M]. 北京:電子工業(yè)出版社,2006.