讀者寫者問題,操作系統(tǒng)課程設計

1、某某大學課程設計報告課程名稱： 操作系統(tǒng)課程設計設計題目： 讀者寫者問題 系 別： 計算機系 專 業(yè)： 計算機科學與技術 組 別： 第四組 學生姓名: 某某某 學 號: 起止日期: 指導教師: 歡迎下載目 錄1、需求分析11.1 課程設計題目11.2課程任務及要求11.3課程設計思想11.4軟硬件運行環(huán)境及開發(fā)工具22、 概要設計22.1程序流程圖22.2所用原理32.2.1 并發(fā)原理32.2.2 互斥操作原理42.2.3 面向對象編程編程原理42.2.4 鎖機制原理52.2.5 線程的原理62.2.6 讀者寫者問題的一般應用63、 詳細設計64、 調試與操作說明115、 課程設計總結與體會1

2、26、 致謝137、 參考文獻131、需求分析1.1 課程設計題目 課程設計題目：讀者寫者問題1.2課程任務及要求編寫程序實現(xiàn)讀者寫者算法（讀_寫互斥，讀_讀允許，寫寫互斥）給出解決方案（包括說明設計實現(xiàn)的原理，采用的數(shù)據(jù)結構等）畫出程序的基本結構框圖和流程圖分析說明每一部分程序的的設計思路實現(xiàn)源代碼按期提交完整的程序代碼和可執(zhí)行程序根據(jù)要求完成課程設計報告總結1.3課程設計思想 讀者-寫者問題是一個經(jīng)典的并發(fā)程序設計問題。有兩組并發(fā)進程：讀者和寫者，共享文件F，要求：(1) 允許多個讀者同時對文件執(zhí)行讀操作；(2) 只允許一個寫者對文件執(zhí)行寫操作；(3) 任何寫者在完成寫操作之前不允許其他讀

3、者或寫者工作；(4) 寫者在執(zhí)行寫操作前，應讓已有的寫者和讀者全部退出。 單純使用信號量不能解決此問題，必須引入計數(shù)器readcount對讀進程記數(shù)。 為了有效的解決讀者寫者問題，需要引進讀者-寫者鎖，允許多名讀者同時以只讀的方式存取有鎖保護的對象；或一位寫者以寫方式存取有鎖保護的對象。當一名或多名讀者上鎖后，此時形成讀鎖，寫者將不能訪問有鎖保護的對象；當鎖被請求者用于寫操作時，形成寫鎖，其他進程的讀寫操作必須等待。1.4軟硬件運行環(huán)境及開發(fā)工具本課程設計在windows操作系統(tǒng)下，使用java語言完成的。2、 概要設計2.1程序流程圖本系統(tǒng)主要有讀者和寫者兩類對象，所以系統(tǒng)主要針對的是這兩類

4、對象的操作。讀者類對象的流程圖如下：圖2.1 讀者類對象寫者類對象的流程圖如下：圖2.2 寫者類對象2.2所用原理2.2.1 并發(fā)原理進程的并發(fā)是指一組進程的執(zhí)行在時間上重疊的，所謂的時間重疊是指一個進程執(zhí)行第一條指令是在另一個進程執(zhí)行完最后一條指令之前開始的。并發(fā)的實質是處理器在幾個進程之間的多路復用，并發(fā)是對有限物理資源強制行使多用戶共享，消除計算機部件之間的互等現(xiàn)象，提高系統(tǒng)資源的利用率。并發(fā)進程可能是無關的，也可能是交互的。進程的交互必須是有控制的，否則會出現(xiàn)不正確的計算結果。2.2.2 互斥操作原理 互斥是指若干進程因互相爭奪獨占型資源而產(chǎn)生的競爭制約關系。 并發(fā)進程中與共享變量有關

5、的程序段稱為“臨界區(qū)”，共享變量所代表的資源稱為“臨界資源”，臨界區(qū)必須以一種相對于其他進程而言互相排斥的方式執(zhí)行。如果能夠保證一個進程在臨界區(qū)執(zhí)行時，不讓另一個進程進入相同的臨界區(qū)，即各進程對共享變量的訪問是互斥的，那么，就不會引發(fā)與時間有關的錯誤。 而為了正確而有效地使用臨界資源，共享變量的并發(fā)進程應遵守臨界區(qū)調度的三個原則：一次至多有一個進程進入臨界區(qū)內執(zhí)行；如果已有進程在臨界區(qū)中，試圖進入臨界區(qū)的其他進程應等待；進入臨界區(qū)內進程應在有限時間內退出，以便讓等待隊列中的一個進程進入?？偨Y起來有三句話：互斥使用，有空讓進；忙則等待，有限等待；擇一而入，算法可行。2.2.3 面向對象編程編程原

6、理面向對象是一種新興的程序設計方法，或者說它是一種新的程序設計范型，其基本思想是使用對象，類，繼承，封裝，消息等基本概念來進行程序設計。它是從現(xiàn)實世界中客觀存在的事物（即對象）出發(fā)來構造軟件系統(tǒng)，并在系統(tǒng)構造中盡可能運用人類的自然思維方式，強調直接以問題域（現(xiàn)實世界）中的事物為中心來思考問題，認識問題，并根據(jù)這些事物的本質特點，把他們抽象地表示為系統(tǒng)中的對象，作為系統(tǒng)的基本構成單位（而不是用一些與現(xiàn)實世界中的事物相關比較遠，并且沒有對應關系的其他概念來構造系統(tǒng)）。這可以使系統(tǒng)直接地映射問題域，保持問題域中事物及其相互關系的本來面貌。本課程設計中涉及了兩個對象，因此用面向對象的語言來編程是適合的

7、。我們這次用到了Java語言。2.2.4 鎖機制原理 為了解決讀者和寫者之間的同步互斥問題，在本課程設計中要用到Java中的鎖機制，這樣會給編程帶來很大的方便。 多線程同步的實現(xiàn)最終依賴鎖機制。我們可以想象某一共享資源是一間屋子，每個人都是一個線程。當A希望進入房間時，他必須獲得門鎖，一旦A獲得門鎖，他進去后就立刻將門鎖上，于是B,C,D.就不得不在門外等待，直到A釋放鎖出來后，B,C,D.中的某一人搶到了該鎖（具體搶法依賴于JVM的實現(xiàn)，可以先到先得，也可以隨機挑選），然后進屋又將門鎖上。這樣，任一時刻最多有一人在屋內（使用共享資源）。 Java語言規(guī)范內置了對多線程的支持。對于Java程序

8、來說，每一個對象實例都有一把“鎖”，一旦某個線程獲得了該鎖，別的線程如果希望獲得該鎖，只能等待這個線程釋放鎖之后。獲得鎖的方法只有一個，就是synchronized關鍵字。1 用鎖操作原語實現(xiàn)互斥 為解決進程互斥進人臨界區(qū)的問題，可為每類臨界區(qū)設置一把鎖，該鎖有打開和關閉兩種狀態(tài)，進程執(zhí)行臨界區(qū)程序的操作按下列步驟進行： 關鎖。先檢查鎖的狀態(tài)，如為關閉狀態(tài)，則等待其打開；如已打開了，則將其關閉，繼續(xù)執(zhí)行步驟的操作。 執(zhí)行臨界區(qū)程序。 開鎖。將鎖打開，退出臨界區(qū)。 2WAIT，NOTIFY，NOTIFYALL操作原語信號量的初值可以由系統(tǒng)根據(jù)資源情況和使用需要來確定。在初始條件下信號量的指針項可

9、以置為0，表示隊列為空。信號量在使用過程中它的值是可變的，但只能由WAIT，SIGNAL操作來改變。設信號量為S，對S的WAIT操作記為WAIT（S），對它的SIGNAL操作記為SIGNAL（S）。WAIT（S）：順序執(zhí)行以下兩個動作：1）信號量的值減1，即S=S1；2）如果S0，則該進程繼續(xù)執(zhí)行；如果 S0，則把該進程的狀態(tài)置為阻塞態(tài)，把相應的WAITCB連人該信號量隊列的末尾，并放棄處理機，進行等待（直至其它進程在S上執(zhí)行SIGNAL操作，把它釋放出來為止）。 SIGNAL（S）：順序執(zhí)行以下兩個動作2.2.5 線程的原理線程是進程中的實體，一個進程可以擁有多個線程，一個線程必須有一個父進

10、程。線程不擁有系統(tǒng)資源，只有運行必須的一些數(shù)據(jù)結構；它與父進程的其它線程共享該進程所擁有的全部資源。線程可以創(chuàng)建和撤消線程，從而實現(xiàn)程序的并發(fā)執(zhí)行。一般，線程具有就緒、阻塞和運行三種基本狀態(tài)。2.2.6 讀者寫者問題的一般應用 讀者寫者是典型的并發(fā)程序設計問題，它的方法可以普遍用于多線程的同步互斥問題，對于共享資源出現(xiàn)的問題做出了很好的解決，使得事物并發(fā)的效率更高，類似的問題還有生產(chǎn)者-消費者問題，理發(fā)師問題等等。3、 詳細設計本次課程設計采用的是java語言編寫，所以要用到類，包括讀者類和寫者類，它們都是繼承的線程Thread類，在主程序中創(chuàng)建類對象（讀者對象和寫者對象），用線程來實現(xiàn)并發(fā)讀

11、者類對象和寫者類對象的公共屬性包括： private static final int NAP_TIME=5; private int readerCount; private int writerCount; private boolean dbReading; private boolean dbWriting;通過NAP_TIME調整線程隨機休息時間通過readercount和writercount來記錄讀者和寫者線程的個數(shù)通過dbreading和dbwriting來判斷讀者和寫者的狀態(tài)，其中讀者是靠判斷writercount0來實現(xiàn)讀寫互斥的，同時允許讀讀同步；而寫者是靠判斷dbrea

12、ding=true|dbwriting=true來實現(xiàn)讀寫互斥和寫寫互斥的。讀寫等待是隨機的，運用的是math.random()函數(shù)程序代碼如下： class Database /*讀者寫者公用的資源Database類*/ private static final int NAP_TIME=5; private int readerCount; /*記錄當前的讀者個數(shù)*/ private int writerCount; /*記錄當前的寫者個數(shù)*/ private boolean dbReading; /*顯示是否有讀者在讀*/ private boolean dbWriting; /*顯示是

13、否有寫者在寫*/ public Database() /*構造函數(shù)*/ super(); readerCount=0; writerCount=0; dbReading=false; dbWriting=false; / TODO Auto-generated constructor stub public static void napping() int sleepTime=(int)(NAP_TIME * Math.random(); try Thread.sleep(sleepTime*1000); catch(Exception e) e.printStackTrace(); pub

14、lic synchronized int startRead() while(writerCount0) /*如果有寫者在寫，那么讀者進行等待*/ try System.out.println(reader is waiting); wait(); catch(Exception e) System.out.println(e.toString(); e.printStackTrace(); +readerCount; if(readerCount=1) /*如果有讀者讀，則設置讀狀態(tài)為true*/ dbReading=true; return readerCount; public sync

15、hronized int endReading() -readerCount; if(readerCount=0) /*如果沒有有讀者讀，則設置讀狀態(tài)為false*/ dbReading=false; notifyAll(); /*釋放所有等待的線程*/ System.out.println(one reader is done reading. Count=+readerCount); return readerCount; public synchronized void startWriting() +writerCount; while(dbReading=true|dbWriting

16、=true)/*如果有讀者在讀或者有寫者在寫，那么寫者進行等待*/ try System.out.println(Writer is waiting); wait(); catch(Exception e) System.out.println(e.toString(); dbWriting =true; /*有寫者在寫，則設置寫狀態(tài)為true*/ public synchronized void endWriting() -writerCount; /*由于每次只有一個寫者在寫，所以結束寫操作后寫者個數(shù)一定為0*/ dbWriting=false; /*沒有寫者寫，則設置寫狀態(tài)為false*

17、/ System.out.println(one writer is done writing. Count=+writerCount); notifyAll(); /*釋放所有等待的線程*/ class Reader extends Thread /*建立讀者類*/ private Database server; private int readerNum; public Reader(int r,Database db) super(); readerNum=r; server=db; public void run() int c; while(true) System.out.pri

18、ntln(reader +readerNum+ is sleeping); Database.napping(); System.out.println(reader +readerNum+ wants to read); c=server.startRead(); System.out.println(reader +readerNum+ is reading. Count=+c); Database.napping(); c=server.endReading(); System.out.println(It is reader +readerNum+ who has done readi

19、ng according to count=+c); class Writer extends Thread /*建立寫者類*/ private Database server; private int writerNum; public Writer(int w,Database db) super(); writerNum=w; server=db; public void run() while(true) System.out.println(Writer +writerNum+ is sleeping); Database.napping(); System.out.println(

20、Writer +writerNum+ wants to write); server.startWriting(); System.out.println(Writer +writerNum+ is writing); Database.napping(); server.endWriting(); System.out.println(It is Writer +writerNum+ who has done writing .); public class DatabaseServer public DatabaseServer() super(); public static void

21、main(String args) Database db=new Database(); /*建立四個讀者對象和兩個寫者對象*/ Reader r1=new Reader(1,db); Reader r2=new Reader(2,db); Reader r3=new Reader(3,db); Reader r4=new Reader(4,db); Writer w1=new Writer(1,db); Writer w2=new Writer(2,db); r1.start(); r2.start(); r3.start(); w1.start(); r4.start(); w2.start(); 4、 調試與操作說明由于讀寫等待是隨機的所以可能出現(xiàn)多中情況，讀寫的順序可能會不一樣，以下是幾種不同的運行結果：圖