邵奇峰

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

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

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

中圖分類號：G642

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

1 引言

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

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

2.1 線程的異步性

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

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

Semaphore sem = new Semaphore(n);

try{

sem.acquire(); //P操作

//critical section

}catch(InterruptedException ie){ }

finally{

sem.release(); //V操作

}

//remainder section

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

2.3 管程

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

管程的發(fā)明者Brinch Hansen于1999年曾撰文對Java語言的管程的實現(xiàn)提出了中肯的評價。以下代碼利用synchronized同步鎖的管程實現(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)者-消費者問題

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

//互斥信號量

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

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è)計將會變得更加簡單而且逐步普及，從而建立起學(xué)習(xí)進(jìn)程管理的信心和興趣。

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同步鎖具有更高的并發(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)造方法，可分別實現(xiàn)寫者優(yōu)先和讀者優(yōu)先算法，簡單的修改代碼，學(xué)生便可直觀的觀測到兩種策略的不同結(jié)果。

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

由Dijkstra引入的哲學(xué)家進(jìn)餐問題是需要在多個線程之間分配多個資源且不會出現(xiàn)死鎖和饑餓形式的簡單表示[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();

}

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

4結(jié)束語

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

參考文獻(xiàn)：

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

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

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