操作系統(tǒng)課程設計——用多線程同步方法解決生產(chǎn)者

1、用多線程同步方法解決生產(chǎn)者消費者問題 producer-consumer problem0 引言隨著多處理機體系結構的演變和分布式與并行系統(tǒng)的發(fā)展，并發(fā)多任務的程序設計技術已愈來愈顯得重要，多線程設計模式在這些技術的發(fā)展中起著重要作用。在現(xiàn)代操作系統(tǒng)中，利用進(線)程間的并發(fā)性實現(xiàn)程序中并發(fā)成分的并行執(zhí)行，可大大提高系統(tǒng)的處理能力和效率，但也可能帶來諸如執(zhí)行結果的不確定性等不良現(xiàn)象，因此并發(fā)系統(tǒng)中處理好進(線)程間的互斥與同步就顯得至關重要。java語言中的多線程機制是解決線程間的互斥與同步問題的重要工具，其應用(如網(wǎng)絡多媒體應用、工業(yè)自動化控制等)很廣泛，很復雜且常易出錯。因此在應用程序設計

2、過程中，要考慮多個線程如何同步使用進程的共享資源，如何讓一個線程與另一個線程協(xié)調(diào)合作，以免產(chǎn)生線程間的訪問沖突。正確運用jav。語言提供的多線程機制能有避免同一共享互斥資源被多個線程同時訪問，維護數(shù)據(jù)的一致性、安全性。生產(chǎn)者/消費者問題可作為并發(fā)進程的同步和互斥問題的一個抽象模型，廣泛應用于通信和控制系統(tǒng)中。本文基于java語言中的多線程機制，實現(xiàn)操作系統(tǒng)中生產(chǎn)者/消費者問題，以助人們更好地透解同步概念及其實現(xiàn)方法。1 課程設計目的通過模擬操作者生產(chǎn)者經(jīng)典問題的實現(xiàn)，深入理解操作系統(tǒng)中多線程同步法的理論知識, 加深對教材中的重要算法的理解。同時通過編程實現(xiàn)這些算法,更好地掌握操作系統(tǒng)的原理及實

3、現(xiàn)方法,提高綜合運用各專業(yè)課知識的能力。2 課程設計題目和要求2.1 課程設計題目題目: 用多線程同步方法解決生產(chǎn)者消費者問題 (producer-consumer problem) 2.2課程設計目的與要求初始條件：1 操作系統(tǒng)：linux2 程序設計語言：c語言3 有界緩沖區(qū)內(nèi)設有20個存儲單元，其初值為0。放入取出的數(shù)據(jù)項按增序設定為120這20個整型數(shù)。技術要求：1）為每個生產(chǎn)者消費者產(chǎn)生一個線程，設計正確的同步算法2）每個生產(chǎn)者和消費者對有界緩沖區(qū)進行操作后，即時顯示有界緩沖區(qū)的當前全部內(nèi)容、當前指針位置和生產(chǎn)者消費者線程的自定義標識符。3）生產(chǎn)者和消費者各有兩個以上。4）多個生產(chǎn)者

4、或多個消費者之間須共享對緩沖區(qū)進行操作的函數(shù)代碼。2設計總體思想2.1 多線程編程思想linux系統(tǒng)下的多線程遵循posix2線程接口，稱為pthread.編寫linux下的多線程程序，需要使用頭文件pthread.h，連接時需要使用庫libpthread.a.在linux下進行多線程編程首先要用到pthread_create和pthread_join這兩個函數(shù)，并聲明了一個pthread_t型的變量.pthread_t在頭文件/usr/include/bits/pthreadtypes.h中定義： typedef unsigned long int pthread_t;它是一個線程的標識符。

5、函數(shù)pthread_create用來創(chuàng)建一個線程，它的原型為： extern int pthread_create _p (pthread_t *_thread, _const pthread_attr_t *_attr, void *(*_start_routine) (void *), void *_arg);第一個參數(shù)為指向線程標識符的指針，第二個參數(shù)用來設置線程屬性，第三個參數(shù)是線程運行函數(shù)的起始地址，最后一個參數(shù)是運行函數(shù)的參數(shù)。這里，我們的函數(shù)thread不需要參數(shù)，所以最后一個參數(shù)設為空指針。第二個參數(shù)我們也設為空指針，這樣將生成默認屬性的線程。對線程屬性的設定和修改我們將在下一

6、節(jié)闡述。當創(chuàng)建線程成功時，函數(shù)返回0，若不為0則說明創(chuàng)建線程失敗，常見的錯誤返回代碼為eagain和einval。前者表示系統(tǒng)限制創(chuàng)建新的線程，例如線程數(shù)目過多了；后者表示第二個參數(shù)代表的線程屬性值非法。創(chuàng)建線程成功后，新創(chuàng)建的線程則運行參數(shù)三和參數(shù)四確定的函數(shù)，原來的線程則繼續(xù)運行下一行代碼。函數(shù)pthread_join用來等待一個線程的結束。函數(shù)原型為：extern int pthread_join _p (pthread_t _th, void *_thread_return);第一個參數(shù)為被等待的線程標識符，第二個參數(shù)為一個用戶定義的指針，它可以用來存儲被等待線程的返回值。這個函數(shù)是一

7、個線程阻塞的函數(shù)，調(diào)用它的函數(shù)將一直等待到被等待的線程結束為止，當函數(shù)返回時，被等待線程的資源被收回。一個線程的結束有兩種途徑，一種是象我們上面的例子一樣，函數(shù)結束了，調(diào)用它的線程也就結束了；另一種方式是通過函數(shù)pthread_exit來實現(xiàn)。它的函數(shù)原型為：extern void pthread_exit _p (void *_retval) _attribute_ (_noreturn_);唯一的參數(shù)是函數(shù)的返回代碼，只要pthread_join中的第二個參數(shù)thread_return不是null，這個值將被傳遞給thread_return。最后要說明的是，一個線程不能被多個線程等待，否則

8、第一個接收到信號的線程成功返回，其余調(diào)用pthread_join的線程則返回錯誤代碼esrch。2.1.1線程數(shù)據(jù)在單線程的程序里，有兩種基本的數(shù)據(jù)：全局變量和局部變量。但在多線程程序里，還有第三種數(shù)據(jù)類型：線程數(shù)據(jù)（tsd: thread-specific data）。它和全局變量很象，在線程內(nèi)部，各個函數(shù)可以象使用全局變量一樣調(diào)用它，但它對線程外部的其它線程是不可見的。這種數(shù)據(jù)的必要性是顯而易見的。例如我們常見的變量errno，它返回標準的出錯信息。它顯然不能是一個局部變量，幾乎每個函數(shù)都應該可以調(diào)用它；但它又不能是一個全局變量，否則在a線程里輸出的很可能是b線程的出錯信息。要實現(xiàn)諸如此類

9、的變量，我們就必須使用線程數(shù)據(jù)。我們?yōu)槊總€線程數(shù)據(jù)創(chuàng)建一個鍵，它和這個鍵相關聯(lián)，在各個線程里，都使用這個鍵來指代線程數(shù)據(jù)，但在不同的線程里，這個鍵代表的數(shù)據(jù)是不同的，在同一個線程里，它代表同樣的數(shù)據(jù)內(nèi)容。和線程數(shù)據(jù)相關的函數(shù)主要有4個：創(chuàng)建一個鍵；為一個鍵指定線程數(shù)據(jù)；從一個鍵讀取線程數(shù)據(jù)；刪除鍵。創(chuàng)建鍵的函數(shù)原型為：extern int pthread_key_create _p (pthread_key_t *_key,void (*_destr_function) (void *);第一個參數(shù)為指向一個鍵值的指針，第二個參數(shù)指明了一個destructor函數(shù)，如果這個參數(shù)不為空，那么當每

10、個線程結束時，系統(tǒng)將調(diào)用這個函數(shù)來釋放綁定在這個鍵上的內(nèi)存塊。這個函數(shù)常和函數(shù)pthread_once (pthread_once_t*once_control, void (*initroutine) (void)一起使用，為了讓這個鍵只被創(chuàng)建一次。函數(shù)pthread_once聲明一個初始化函數(shù)，第一次調(diào)用pthread_once時它執(zhí)行這個函數(shù)，以后的調(diào)用將被它忽略。2.1.2 互斥鎖互斥鎖用來保證一段時間內(nèi)只有一個線程在執(zhí)行一段代碼，必要性顯而易見：假設各個線程向同一個文件順序寫入數(shù)據(jù)，最后得到的結果一定是災難性的.函數(shù)pthread_mutex_init用來生成一個互斥鎖.null參數(shù)

11、表明使用默認屬性.如果需要聲明特定屬性的互斥鎖，須調(diào)用函數(shù) pthread_mutexattr_init.函數(shù)pthread_mutexattr_setpshared和函數(shù)pthread_mutexattr_settype用來設置互斥鎖屬性.前一個函數(shù)設置屬性pshared，它有兩個取值，pthread_process_private和pthrea d_process_shared.前者用來不同進程中的線程同步，后者用于同步本進程的不同線程.pthread_mutex_lock聲明開始用互斥鎖上鎖，直至調(diào)用pthread_mutex_unlock為止，均被上鎖，即同一時間只能被一個線程調(diào)用執(zhí)行

12、.當一個線程執(zhí)行到pthread_mutex_lock處時，如果該鎖此時被另一個線程使用，那么此線程被阻塞，即程序將等待到另一個線程釋放此互斥鎖.使用互斥鎖的過程中很有可能會出現(xiàn)死鎖，可以使用函數(shù)pthread_mutex_trylock，它是函數(shù)pthread_mutex_lock的非阻塞版本，當它發(fā)現(xiàn)死鎖不可避免時，會返回相應的信息，程序員可以根據(jù)返回值做具體的處理.2.1.3 信號量信號量本質上是一個非負的整數(shù)計數(shù)器，它被用來控制對公共資源的訪問。當公共資源增加時，調(diào)用函數(shù)sem_post（）增加信號量。只有當信號量值大于時，才能使用公共資源，使用后，函數(shù)sem_wait（）減少信號量。

13、函數(shù)sem_trywait（）和函數(shù)pthread_ mutex_trylock（）起同樣的作用，它是函數(shù)sem_wait（）的非阻塞版本。下面我們逐個介紹和信號量有關的一些函數(shù)，它們都在頭文件/usr/include/semaphore.h中定義。信號量的數(shù)據(jù)類型為結構sem_t，它本質上是一個長整型的數(shù)。函數(shù)sem_init（）用來初始化一個信號量。它的原型為：extern int sem_init _p (sem_t *_sem, int _pshared, unsigned int _value);sem為指向信號量結構的一個指針；pshared不為時此信號量在進程間共享，否則只能為當

14、前進程的所有線程共享；value給出了信號量的初始值。函數(shù)sem_post( sem_t *sem )用來增加信號量的值。當有線程阻塞在這個信號量上時，調(diào)用這個函數(shù)會使其中的一個線程不在阻塞，選擇機制同樣是由線程的調(diào)度策略決定的。函數(shù)sem_wait( sem_t *sem )被用來阻塞當前線程直到信號量sem的值大于0，解除阻塞后將sem的值減一，表明公共資源經(jīng)使用后減少。函數(shù)sem_trywait ( sem_t *sem )是函數(shù)sem_wait（）的非阻塞版本，它直接將信號量sem的值減一。函數(shù)sem_destroy(sem_t *sem)用來釋放信號量sem。2.2 設計原理生產(chǎn)者線

15、程和消費者線程共享同一個緩沖隊列，生產(chǎn)者線程向緩沖區(qū)中寫數(shù)據(jù)，消費者線程從緩沖區(qū)中取數(shù)據(jù)。但兩者必須在使用緩沖隊列資源時保持互斥，否則可能會導致在寫入時產(chǎn)生數(shù)據(jù)覆蓋，在讀出時得到錯誤數(shù)據(jù)。因而要在程序中設置一個互斥鎖或公用信號量，用于保證線程間的互斥執(zhí)行。同時生產(chǎn)者線程和消費者線程必須保持同步關系，因為生產(chǎn)者線程的執(zhí)行為消費者線程提供了需要的數(shù)據(jù)，是其執(zhí)行的前提。反之，消費者線程的執(zhí)行為生產(chǎn)者線程騰出了空閑的緩沖單元，為寫數(shù)據(jù)提供了條件。即消費者線程執(zhí)行的前提：緩沖隊列中至少有一個單元有數(shù)據(jù)；生產(chǎn)者線程執(zhí)行的前提：緩沖隊列中至少有一個單元是空的。在設計過程中，利用信號量和wait 、signa

16、l原語操作來實現(xiàn)。如圖1所示：圖1 生產(chǎn)者、消費者共享有界緩沖區(qū)2.3 原語操作實現(xiàn)the structure of the producer process do / 生產(chǎn)產(chǎn)品 wait (empty); wait (mutex); / 往buffer中放入產(chǎn)品 signal (mutex); signal (full); while (true);the structure of the consumer process do wait (full); wait (mutex); / 從buffer中取出產(chǎn)品 signal (mutex); signal (empty); / 消費產(chǎn)品 w

17、hile (true);3 開發(fā)環(huán)境與工具系統(tǒng)平臺：linux環(huán)境實現(xiàn)語言：c語言開發(fā)工具：vi編輯器4 概要設計4.1 數(shù)據(jù)結構設計通過分析課程設計要求，具體設計出如下數(shù)據(jù)結構:1. int buffer20=0;/定義緩沖區(qū)空間大小2.包含數(shù)據(jù)結構pthread_t 它記錄一個線程的號，主要包括下面幾個函數(shù)，完成不同的功能：int pthread_create _p (pthread_t *_thread, _const thread_attr_t *_attr, void *(*_start_routine) (void *), void *_arg);/創(chuàng)建一個線程。 int pthr

18、ead_join _p (pthread_t _th, void *_thread_return);/等待一個線程結束。4.2 程序模塊說明4.2.1 生產(chǎn)者（producer）模塊 生產(chǎn)者線程向一緩沖區(qū)中寫入數(shù)據(jù)，且寫入緩沖區(qū)的數(shù)目不能超過緩沖區(qū)容量。當生產(chǎn)者產(chǎn)生出數(shù)據(jù)，需要將其存入緩沖區(qū)之前，首先檢查緩沖區(qū)中是否有“空”存儲單元，若緩沖區(qū)存儲單元全部用完，則生產(chǎn)者必須阻塞等待，直到消費者取走一個存儲單元的數(shù)據(jù)，喚醒它。若緩沖區(qū)內(nèi)有“空”存儲單元，生產(chǎn)者需要判斷此時是否有別的生產(chǎn)者或消費者正在使用緩沖區(qū)，若是有，則阻塞等待，否則，獲得緩沖區(qū)的使用權，將數(shù)據(jù)存入緩沖區(qū)，釋放緩沖區(qū)的使用權，其流

19、程圖如圖2所示： 圖2 生產(chǎn)者流程圖4.2.2 消費者(consumer)模塊 消費者線程從緩沖區(qū)中讀取數(shù)據(jù)，且消費者讀取的數(shù)目不能超過生產(chǎn)者寫入的數(shù)目。消費者取數(shù)據(jù)之前，首先檢查緩沖區(qū)中是否存在裝有數(shù)據(jù)的存儲單元，若緩沖區(qū)為“空”，則阻塞等待，否則，判斷緩沖區(qū)是否正在被使用，若正被使用，若正被使用，則阻塞等待，否則，獲得緩沖區(qū)的使用權，進入緩沖區(qū)取數(shù)據(jù)，釋放緩沖區(qū)的使用權。其執(zhí)行流程如圖3所示： 圖3 消費者流程圖5 詳細設計5.1 用戶名、源程序名、目標程序名用戶名：rj060131源程序名：producerconsumer.c目標程序名：producerconsumer主機ip地址：19

20、2.168.1.875.2 源程序代碼#include #include #include #include #define buffer_size 20 /20個緩沖區(qū)int buffer20=0;sem_t empty;sem_t full;pthread_mutex_t mutex; /for mutual exclusion進程信號量int in=0; /point to the next free positonint out=0; /point to the first full positon/把所有的緩沖區(qū)輸出到屏幕上void printall() int i; for(i=0

21、;i20;i+) printf(%d ,bufferi); printf(n); printf(current producer pointer:%dn,in); printf(current consumer pointer:%dn,out);/生產(chǎn)者線程void producer(char *arg) do sem_wait(&empty); /空緩沖區(qū)減1 pthread_mutex_lock(&mutex); /信號量上鎖 /往buffer中放入產(chǎn)品 bufferin=in+1; in=(in+1)%buffer_size;/放入指針調(diào)整，為下次送出做準備 printf(%sn,arg

22、); printall(); pthread_mutex_unlock(&mutex); /信號量解鎖 sem_post(&full); /滿緩沖區(qū)加1，即當公共資源增加時，調(diào)用函數(shù)sem_post（）增加信號量 sleep(1); while(1);/消費者線程void consumer(char *arg) do sem_wait(&full); /滿緩沖區(qū)減1 pthread_mutex_lock(&mutex); /信號量上鎖 /從buffer中取出產(chǎn)品 bufferout=0; out=(out+1)%buffer_size;/取指針調(diào)整，為下次取做準備 printf(%sn,arg

23、); printall(); pthread_mutex_unlock(&mutex); /信號量解鎖 sem_post(&empty); /空緩沖區(qū)加1 sleep(2); while(1);/主線程int main() /創(chuàng)建進程 pthread_t producer1,producer2,producer3,producer4, consumer1,consumer2,consumer3, consumer4 ; void *retval; pthread_mutex_init(&mutex,null);/ /* 用默認屬性初始化一個互斥變量mutex / 初始化信號量sem_init(

24、&full,0,0); sem_init(&empty,0,buffer_size);/pthread_create函數(shù)用來創(chuàng)建生產(chǎn)者和消費者進程，其四個參數(shù)分別表示為進程、null、進程要執(zhí)行的函數(shù)、執(zhí)行函數(shù)時的參數(shù) pthread_create(&producer1,null,(void*)producer,producer1:); pthread_create(&consumer1,null,(void*)consumer,consumer1:); pthread_create(&producer2,null,(void*)producer,producer2:); pthread_cr

25、eate(&consumer2,null,(void*)consumer,consumer2:); pthread_create(&producer3,null,(void*)producer,producer3:); pthread_create(&consumer3,null,(void*)producer,consumer3:);pthread_create(&producer1,null,(void*)producer,producer4:);pthread_create(&consumer1,null,(void*)consumer,consumer4:);/pthread_join用來表示等待線程的結束，表示producer1,producer2,producer3, producer4, consumer1,consumer2,consumer3 consumer4執(zhí)行完畢之前主程序必須等待 pth