采用“寫優(yōu)先”的策略演示“讀者寫者”問題(C_)

1、青島理工大學操作系統(tǒng)課程設計報告院（系）： 計算機工程學院 專業(yè)： 計算機科學與技術專業(yè) 學生姓名: 滕同學 班級：軟件102學號: 201007195 題目： 采用“寫優(yōu)先”的策略演示“讀者-寫者”問題 起迄日期: 2013.7.8-2013.7.17 設計地點: 網(wǎng)絡中心計算機學院機房 指 導 教 師: 吳老師 20122013年度 第 2 學期完成日期: 2013 年 7 月 17 日一、 課程設計目的進行操作系統(tǒng)課程設計主要是在學習操作系統(tǒng)課程的基礎上，在完成操作系統(tǒng)各部分實驗的基礎上，對操作系統(tǒng)的整體進行一個模擬，通過實踐加深對各個部分的管理功能的認識，還能進一步分析各個部分之間的聯(lián)

2、系，最后達到對完整系統(tǒng)的理解。同時，可以提高運用操作系統(tǒng)知識解決實際問題的能力；鍛煉實際的編程能力、創(chuàng)新能力及團隊組織、協(xié)作開發(fā)軟件的能力；還能提高調查研究、查閱技術文獻、資料以及編寫軟件設計文檔的能力。此次實驗我選擇的是經典的讀者寫者問題。讀寫者問題的傳統(tǒng)解決方案采用讀優(yōu)先策略，可能會造成后續(xù)的寫者被隨后而來的讀者插隊而長時間等待，直到全部讀者進程運行完畢后，才可進行寫操作。為此，選擇采用“寫優(yōu)先策略”解決讀寫者問題，希望通過此次課程設計實現(xiàn)利于寫者工作的功能，加深對線程、進程及同步概念的理解。通過研究經典的進程同步問題，實現(xiàn)對讀者-寫者問題的并發(fā)控制，掌握運用信號量解決“同類進程多次訪問，

3、而不同類的進程必須互斥訪問資源”的控制問題。此次實驗我選擇用比較大眾的C#語言編寫,因為C#中有semaphore類是對操作系統(tǒng)的semaphore很好的描述。二、 課程設計內容與要求1、設計目的：通過研究經典的進程進步問題，實現(xiàn)對讀者-寫者問題的并發(fā)控制。2、說明：閱覽室一次最多可以容納20個人。3、設計要求：1) 讀者與寫者至少包括ID、進入內存時間、讀寫時間三項內容，可在界面上進行輸入2) 讀者與寫者均有二個以上，可在程序運行期間動態(tài)增加讀者與寫者3) 可讀取樣例數(shù)據(jù)（要求存放在外部文件中），進行讀者/寫者、進入內存時間、讀寫時間的初始化4) 要求將運行過程用可視化界面動態(tài)顯示，可隨時暫

4、停，查看閱覽室中讀者/寫者數(shù)目、讀者等待隊列、寫者等待隊列、讀寫時間、等待時間5) 讀寫策略為：讀寫互斥、寫寫互斥、寫優(yōu)先（只要寫者到達，就阻塞后續(xù)的所有讀者，一旦閱覽室無人，寫者能最快進入閱覽室；在寫者未出閱讀室之前，又有新的讀者與寫者到達，仍然是寫者排在前面）三、 系統(tǒng)分析與設計3.1 系統(tǒng)分析3.1.1 信息分析： 寫者優(yōu)先程序實現(xiàn)寫者優(yōu)先進行寫，本程序主要功能包括增加讀者寫者，時間的顯示，動態(tài)的顯示讀寫過程，暫停繼續(xù)。具體實現(xiàn)這些功能所需要的信息表示如下：1） 讀者線程信息： public string Id;/讀者線程ID public int IncomeTime;/進入內存的時間

5、 public int ServerTime;/需要服務的時間 2）寫者線程信息： public string Id;/寫者線程ID public int IncomeTime;/進入內存的時間 public int ServerTime;/需要服務的時間 3）計時器線程 (需要的變量) public static DateTime initTime = new DateTime();/開始時系統(tǒng)時間 public static int uptime = 0;/系統(tǒng)暫停的全部時間 public static DateTime pause;/暫停時的時間 public static DateTi

6、me goon;/暫停結束的時間2） 主類中的信息： public static int Rcount = 0;/閱覽室內讀者的人數(shù) public static int Wcount = 0;/閱覽室內寫者的人數(shù) public static DataTable rwq = new DataTable();/讀者等待隊列 public static DataTable wwq = new DataTable();/寫者等待隊列 public static Label lb1, lb2;/讀者寫者要訪問的控件設置為靜態(tài)全局變量: /lb1顯示 當前是讀者，還是寫者 /lb2顯示當前閱覽室的人數(shù)3）

7、 信號量信息： public static Semaphore Mut1 = new Semaphore(1, 1);/實現(xiàn)寫者優(yōu)先的信號量 public static Semaphore Mut2 = new Semaphore(1, 1);/訪問讀者數(shù)量的信號量 public static Semaphore Fmutex = new Semaphore(1, 1);/表示瀏覽室的信號量public static Semaphore rNumber = new Semaphore(20,20);/定義閱覽室人數(shù)public static Semaphore Pause = new Sema

8、phore(1, 1);/控制訪問時間的信號量3.1.2 行為分析：1） 增加讀者寫者：在文本框中輸入進入內存時間，還有服務時間，即可創(chuàng)建讀者寫者線程，然后直接啟動即可，實現(xiàn)動態(tài)添加讀者寫者目的。 2） 外部文本讀取：輸入文本的名字可讀取樣例數(shù)據(jù)（存放在外部文件中），進行讀者/ 寫者、進入內存時間、讀寫時間的初始化。 3）時間顯示功能：在主函數(shù)中點擊開始按鈕，就啟動一個計時線程，并在主界面動態(tài)的顯示。 4） 數(shù)據(jù)顯示：采用C#中DateGradeView運行過程用可視化界面動態(tài)顯示，可以隨時查看閱覽室中讀者/寫者的等待時間，狀態(tài)，哪些讀者寫者處于等待狀態(tài)。 5） 暫停繼續(xù)功能：暫停繼續(xù)的實現(xiàn)，

9、主要是對計時線程的信號量Pause的申請和釋放實現(xiàn)的。3.1.2 表示分析： 1）系統(tǒng)主界面設計顯示讀者寫者的運行狀態(tài)及信息，實現(xiàn)一些功能的按鈕。 圖 1 主界面設計3.2 系統(tǒng)設計：3.2.1 模塊設計：線程開始運行數(shù)據(jù)初始化主框架窗口數(shù)據(jù)錄入運行過程動態(tài)顯示單個輸入外部文件讀取開始運行暫停繼續(xù)終止 圖 3 系統(tǒng)功能模塊圖 圖 4 系統(tǒng)主要流程圖3.2.2 數(shù)據(jù)結構說明：1. 程序中的數(shù)據(jù)定義： public static int Rcount = 0;/閱覽室內讀者的人數(shù) public static int Wcount = 0;/閱覽室內寫者的人數(shù) public static DataT

10、able rwq = new DataTable();/讀者等待隊列 public static DataTable wwq = new DataTable();/寫者等待隊列 public static Label lb1, lb2;/讀者寫者要訪問的控件設置為靜態(tài)全局變量:l /b1顯示 當前是讀者，還是寫者 /lb2顯示當前閱覽室的人數(shù) public static DateTime initTime = new DateTime();/開始時系統(tǒng)時間 public static int uptime = 0;/系統(tǒng)暫停的全部時間 public static DateTime pause;

11、/暫停時的時間 public static DateTime goon;/暫停結束的時間2. 程序中信號量的定義： public static Semaphore Mut1 = new Semaphore(1, 1);/實現(xiàn)寫者優(yōu)先的信號量 public static Semaphore Mut2 = new Semaphore(1, 1);/訪問讀者數(shù)量的信號量 public static Semaphore Fmutex = new Semaphore(1, 1);/表示瀏覽室的信號量public static Semaphore rNumber = new Semaphore(20,20

12、);/定義閱覽室人數(shù)public static Semaphore Pause = new Semaphore(1, 1);/控制訪問時間的信號量3.2.3 算法流程圖：開始 暫停添加讀者，寫者繼續(xù) 讀者線程 寫者線程 Form1.runTime() < IncomeTimeForm1.runTime() < IncomeTime 是 是等待 否 否Mut1.Wait() Wcount+Mut1.Wait() 是 Mut1.Release() Fmutex.Wait()Wcount>0是 進行寫操作 否 Mut2.Wait()Wcount-Rcount+Fmutex.Rele

13、ase()Rcount=1Mut1.Release() 是Fmutex.Wait() 否rNumber.WaitOne()進行讀操作rNumber.Release()Mut2.Wait()Rcount-Rcount = 0Fmutex.Release()Mut2.Release()結束四、系統(tǒng)測試與調試分析4.1 系統(tǒng)測試測試技術：單元測試，功能測試。單元測試是從開發(fā)者的角度來編寫的，檢驗被測代碼中的一個很明確的功能是否正確。通常而言，一個單元測試是用于判斷某個特定條件（或者場景）下某個特定函數(shù)的行為。例如可以輸入正確的用戶名和密碼以及錯誤的用戶名和密碼來確定系統(tǒng)的登陸功能是否正確，如果系統(tǒng)能

14、夠處理不同情況的輸入則說明此登陸功能沒有問題。編寫單元測試有助于調用者觀察、思考。特別是先寫測試，迫使我們把程序設計成易于調用和可測試的，迫使我們解除軟件中的耦合。編寫單元測試有助于增加程序功能或者更改程序的結構，使程序變得更加完善。功能測試是從使用者的角度來編寫的，它關注系統(tǒng)提供的功能特征及其不同的處理條件；測試功能的不同處理流程（包括正常處理的和異常處理），它能幫助開發(fā)者更好的發(fā)心系統(tǒng)的不足。測試方法：黑盒測試。黑盒測試方法是通過使用整個軟件或某種軟件功能來嚴格地測試,而并沒有通過檢查程序的源代碼或者很清楚地了解該軟件的源代碼程序具體是怎樣設計的。測試人員通過輸入他們的數(shù)據(jù)然后看輸出的結果

15、從而了解軟件怎樣工作。在測試時，把程序看作一個不能打開的黑盆子，在完全不考慮程序內部結構和內部特性的情況下，測試者在程序接口進行測試，它只檢查程序功能是否按照需求規(guī)格說明書的規(guī)定正常使用，程序是否能適當?shù)亟邮蘸驼_的輸出。 表 2 文本輸入測試測試說明測試名稱采用“寫優(yōu)先”的策略演示“讀者寫者”問題測試目的驗證系統(tǒng)對于讀者寫者多線程的處理流程測試技術單元測試測試方法黑盒測試法測試用例測試內容 讀者寫者的信息輸入測試步驟從界面輸入信息從文本中讀取輸入錯誤信息測試數(shù)據(jù)1，R，3,5rw.txt錯誤的編號預期結果信息顯示在table中信息顯示在table中出現(xiàn)異常，顯示失敗測試結果與預期相符與預期相

16、符與預期相符 表 3 讀者寫者測試 測試說明測試名稱采用“寫優(yōu)先”的策略演示“讀者寫者”問題測試目的驗證系統(tǒng)對于讀者寫者多線程的處理流程測試技術功能測試測試方法黑盒測試法測試用例測試內容在寫者后面到達到的讀者被阻塞測試步驟把數(shù)據(jù)從外部文件輸入數(shù)據(jù)庫，然后從哈希表中讀出開始運行測試數(shù)據(jù)1 R 1 6 2 R 2 63 W 3 64 W 4 65 R 5 66 R 6 67 W 7 6預期結果1,2 3 4 5，6 7測試結果與預期相符 表 4 讀者寫者同時到達測試測試說明測試名稱采用“寫優(yōu)先”的策略演示“讀者寫者”問題測試目的驗證系統(tǒng)對于讀者寫者多線程的處理流程測試技術功能測試測試方法黑盒測試法

17、測試用例測試內容讀者寫者同時到達，寫者得到進入閱覽室的權利測試步驟從界面添加讀者寫者的信息，到達時間相同，到數(shù)據(jù)庫然后開始執(zhí)行測試數(shù)據(jù)1 R 3 4 2 W 3 4預期結果2 1測試結果與預期相符 表 5 人數(shù)測試 測試說明測試名稱采用“寫優(yōu)先”的策略演示“讀者寫者”問題測試目的驗證系統(tǒng)對于讀者寫者多線程的處理流程測試技術功能測試測試方法黑盒測試法測試用例測試內容采用“寫優(yōu)先”的策略演示“讀者寫者”問題測試步驟從界面添加讀者寫者的信息，到達時間相同，到哈希表然后開始執(zhí)行測試數(shù)據(jù)1 R 4 20 2 R 4 20 3 R 4 20 4 R 4 205 R 4 20 6 R 5 20 7 R 5

18、20 8 R 5 209 R 5 20 10 R 6 20 11 R 6 20 12 R 6 2013 R 6 20 14 R 6 20 15 R 5 20 16 R 5 2017 R 7 20 18 R 7 20 19 R 7 20 20 R 8 2021 R 8 20 22 R 8 20預期結果編號120先執(zhí)行，21,22阻塞，1-5執(zhí)行完離開，21,22進入測試結果與預期相符4.2 調試分析：在開始的時候對如何將讀者寫者問題轉化到代碼非常疑惑，因為沒有沒有編寫操作系統(tǒng)實驗的思想，后來去網(wǎng)上查閱了相關的資料看了一些代碼后，才有了一個初步的認識，并看了關于多線程的視頻才最終確定用多線程的編寫

19、。在整體方面，計算機的時鐘是以毫秒來計算的，因此我設計了一個延遲時間Delay=1000，即以1s為一個時鐘間隔。在編寫過程中遇到了一些問題花費了好多時間才解決。遇到的問題如下：（1） 開始并不知道如何處理到達時間，當其到達時該如何判斷并調度它，采用的是循環(huán)sleep,每次sleep(1000)一秒。（2） 如何更新運行時間與等待時間。采用timeClock（自己創(chuàng)建的始終線程）對時間進行記錄與計算。（3） 進程狀態(tài)的更新。使用state記錄狀態(tài)，通過申請信號量成功與否來改變狀態(tài)。（4） 應該創(chuàng)建的線程種類。讀者，寫者線程，主線程，和timeClock時鐘記錄線程。五、用戶手冊5.1 程序開發(fā)

20、及運行環(huán)境本程序在Win7操作系統(tǒng)下利用圖像界面技術設計前臺界面，采用C#語言編寫后臺代碼，文件作為后臺信息的存儲，在vs2010軟件上開發(fā)。Vs2010下載地址：5.2 具體使用步驟1）打開vs2010軟件，點擊運行，系統(tǒng)主界面出現(xiàn)。2）選擇增加讀者寫者，出現(xiàn)界面如下圖。 主界面顯示3） 必須先點擊開始，在點擊暫停，才能添加讀者和寫者或者直接點擊文件輸入，否則出現(xiàn)異常 4） 點擊文件輸入，即可從文件中讀取讀者寫者信息，然后進行讀寫操作。 運行信息顯示界面5）選擇暫停，即可暫停所有線程的運行，然后動態(tài)添加讀者，寫者 6） 點擊繼續(xù)，則可將剛剛添加的讀者，還有寫者進行讀寫操作。7） 程序退出選擇

21、，點擊終止，即可終止程序。六、程序清單6.1 外部文件rw.txt /外部數(shù)據(jù)錄入文件6.2 主要的類 Form.cs /主界面類 Reader.cs /讀者類（包含讀者信息ID，進入時間，運行時間，以及讀者線程調度的read方法。Writer.cs /讀者類（包含寫者信息ID，進入時間，運行時間，以及寫者線程調度的write方法。6.3 本程序的源代碼using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using Sys

22、tem.Linq;using System.Text;using System.Windows.Forms;using System.Threading;using System.IO;/* Semaphore的理解通過使用一個計數(shù)器對共享資源進行訪問控制，Semaphore構造器需要提供初始化的計數(shù)器（信號量）大小以及最大的計數(shù)器大小訪問共享資源時，程序首先申請一個向Semaphore申請一個許可證，Semaphore的許可證計數(shù)器相應的減一，當計數(shù)器為0時，其他申請該信號量許可證的線程將被堵賽，直到先前已經申請到許可證的線程釋放他占用的許可證讓計數(shù)器加一，這樣最近去申請許可證的線程將會得到

23、競爭得到被釋放的許可證。常見的操作方法 WaitOne():申請一個許可證 Release():釋放占用的許可證 */namespace duzhexiezhe public partial class Form1 : Form public static Semaphore Pause = new Semaphore(1, 1);/控制進程暫停訪問時間的信號量 public static Semaphore Mut1 = new Semaphore(1, 1);/實現(xiàn)寫者優(yōu)先的信號量 public static Semaphore Mut2 = new Semaphore(1, 1);/訪問

24、讀者數(shù)量的信號量 public static Semaphore Fmutex = new Semaphore(1, 1);/表示瀏覽室的信號量 public static Semaphore rNumber = new Semaphore(20,20); public static int Rcount = 0;/閱覽室內讀者的人數(shù) public static int Wcount = 0;/閱覽室內寫者的人數(shù) public static DataTable rwq = new DataTable();/讀者等待隊列 public static DataTable wwq = new Dat

25、aTable();/寫者等待隊列 public static Label lb1, lb2;/讀者寫者要訪問的控件設置為靜態(tài)全局變量:lb1顯示 當前是讀者，還是寫者 /lb2顯示當前閱覽室的人數(shù) public static DateTime initTime = new DateTime();/開始時系統(tǒng)時間 public static int uptime = 0;/系統(tǒng)暫停的全部時間 public static DateTime pause;/暫停時的時間 public static DateTime goon;/暫停結束的時間 public Form1() InitializeComp

26、onent(); private void Form1_Load(object sender, EventArgs e)/初始化一些全局控件 rwq.Columns.Add("進程ID"); rwq.Columns.Add("到達時間"); rwq.Columns.Add("服務時間"); dgvrwq.DataSource = rwq; wwq.Columns.Add("進程ID"); wwq.Columns.Add("到達時間"); wwq.Columns.Add("服務時間&qu

27、ot;); dgvwwq.DataSource = wwq; lb1 = label1; lb2 = label2; public static int time()/開始運行到現(xiàn)在的時間，以秒為單位 TimeSpan d = DateTime.Now.Subtract(initTime); return Convert.ToInt32(d.TotalSeconds); public static int runTime()/程序實際運行的時間 Pause.WaitOne(); Pause.Release(); int t = time() - uptime; return t; public

28、 void timeShow()/顯示時間 while (true) Thread.Sleep(20); Pause.WaitOne(); Pause.Release(); lbTime.Text = (time()-uptime).ToString(); private void button3_Click(object sender, EventArgs e)/開始按鈕點擊事件 initTime = System.DateTime.Now; Thread threadtime = new Thread(timeShow); Control.CheckForIllegalCrossThrea

29、dCalls = false; threadtime.Start(); button3.Enabled = false;/開始按鈕 button5.Enabled = false;/導入文件按鈕 private void button4_Click(object sender, EventArgs e)/暫停觸發(fā)的事件 TimeSpan d; if (button4.Text = "暫停")/暫停 Pause.WaitOne(); button4.Text = "繼續(xù)" pause = DateTime.Now; else /繼續(xù) Pause.Relea

30、se(); button4.Text = "暫停" goon = DateTime.Now; d = goon.Subtract(pause); uptime = uptime+Convert.ToInt16(d.TotalSeconds); private void button1_Click(object sender, EventArgs e) Thread t1 = new Thread(newWriter); t1.Start(); public void newWriter()/新寫者 Writer w = new Writer(Int32.Parse(text

31、Box1.Text), Int32.Parse(textBox2.Text); textBox1.Text = "" textBox2.Text = "" Thread thread = new Thread(w.write); Control.CheckForIllegalCrossThreadCalls = false; thread.Start(); private void button2_Click(object sender, EventArgs e) Thread thread = new Thread(newReader); thread

32、.Start(); private void newReader()/新讀者 Reader r = new Reader(Int32.Parse(textBox3.Text), Int32.Parse(textBox4.Text); textBox3.Text = "" textBox4.Text = "" Thread t = new Thread(r.read); Control.CheckForIllegalCrossThreadCalls = false; t.Start(); private void button5_Click(object

33、sender, EventArgs e)/從文件開始 FileInfo fi = new FileInfo("D:ASP.NETduzhexiezheduzhexiezhedocumentsrw.txt"); /TXT文件路徑 StreamReader sr = fi.OpenText(); while(!sr.EndOfStream) string str = sr.ReadLine(); char c = char.Parse(str.Split(' ')0); int t1 = int.Parse(str.Split(' ')1); i

34、nt t2 = int.Parse(str.Split(' ')2); if (c.Equals('r') Reader r = new Reader(t1, t2); Thread t = new Thread(r.read); Control.CheckForIllegalCrossThreadCalls = false; t.Start(); if (c.Equals('w') Writer w = new Writer(t1,t2); Thread t = new Thread(w.write); Control.CheckForIlle

35、galCrossThreadCalls = false; t.Start(); initTime = System.DateTime.Now; Thread threadtime = new Thread(timeShow); Control.CheckForIllegalCrossThreadCalls = false; threadtime.Start(); button3.Enabled = false; button5.Enabled = false; private void Form_Close(object sender, FormClosingEventArgs e) Envi

36、ronment.Exit(0); Application.Exit(); private void button6_Click(object sender, EventArgs e)/終止 this.Close(); public class Reader/讀者類 public string Id; public int IncomeTime; public int ServerTime; public Reader(int ctime,int stime) IncomeTime = ctime; ServerTime = stime; public void read() DataRow d

37、r; dr = Form1.rwq.NewRow(); dr"進程ID" = Thread.CurrentThread.ManagedThreadId; dr"到達時間" = IncomeTime; dr"服務時間" = ServerTime; Form1.rwq.Rows.Add(dr); while (Form1.runTime() < IncomeTime) Form1.Pause.WaitOne(); Form1.Pause.Release(); /下面if代碼保證了寫者優(yōu)先 Form1.Mut1.WaitOne();

38、/讀者需要先申請Mut1,如果有寫者在等待Fmutex,則讀者被阻塞，寫者優(yōu)先 Form1.Mut1.Release(); /立即釋放Mut1，使寫者可以隨時申請到Mut1 /不斷測試有沒有寫者 while(Form1.Wcount>0) /Thread.Sleep(100); Form1.Mut2.WaitOne(); Form1.Rcount = Form1.Rcount + 1; if (Form1.Rcount = 1) Form1.Fmutex.WaitOne(); /第一個讀者進入時，申請Fmutex；如有寫者，第一個讀者會阻塞在此處 Form1.Mut2.Release()

39、; Form1.rNumber.WaitOne();/圖書室沒座位則阻塞 /讀操作； Form1.lb1.Text = "讀者" Form1.lb2.Text = Form1.Rcount.ToString();/顯示讀者數(shù) Form1.lb2.Update(); DateTime dt1 = DateTime.Now; TimeSpan ts=DateTime.Now.Subtract(dt1); while (ts.TotalSeconds < ServerTime) ts = DateTime.Now.Subtract(dt1); Form1.Pause.Wai

40、tOne(); Form1.Pause.Release(); Form1.rwq.Rows.Remove(dr); Form1.rNumber.Release();/讀者釋放座位 Form1.Mut2.WaitOne(); Form1.Rcount = Form1.Rcount - 1; if (Form1.Rcount = 0) Form1.Fmutex.Release(); /最后一個讀者退出時，釋放Fmutex Form1.lb2.Text = Form1.Rcount.ToString();/顯示讀者數(shù) Form1.Mut2.Release(); public class Writer/寫者類 public string Id; public int IncomeTime; public int ServerTime; public Writer(int ctime, int stime) IncomeTime = ctime; ServerTime = stime; public void write() DataRow dr;/數(shù)據(jù)表的一行 dr = Form1.wwq.NewRow(); dr"進程ID" = T