進(jìn)程同步及互斥_哲學(xué)家進(jìn)餐問題

1、 網(wǎng)絡(luò)教育學(xué)院操作系統(tǒng)課 程 設(shè) 計(jì) 題 目： 進(jìn)程同步與互斥 哲學(xué)家進(jìn)餐問題 學(xué)習(xí)中心：層 次： 專 業(yè)： 年 級(jí)： 年 秋 季 學(xué) 號(hào)： 學(xué) 生： 輔導(dǎo)教師： 完成日期： 目錄1題目要求與開發(fā)環(huán)境11.1 題目目的與要求11.2 題目開發(fā)環(huán)境11.3開發(fā)原型圖11.4設(shè)計(jì)界面截圖22. 總體設(shè)計(jì)思想以及相關(guān)知識(shí)22.1總體設(shè)計(jì)思想22.2 本程序涉及到的概念32.2.1簡(jiǎn)介32.2.2臨界資源32.2.3進(jìn)程同步32.2.4進(jìn)程互斥42.2.5實(shí)現(xiàn)臨界區(qū)互斥的基本方法4硬件實(shí)現(xiàn)方法4信號(hào)量實(shí)現(xiàn)方式53流程和效果圖53.1程序流程圖及簡(jiǎn)介53.2流程圖各階段程序界面的變化74程序源代碼95設(shè)

2、計(jì)總結(jié)141題目要求與開發(fā)環(huán)境1.1 題目目的與要求題目的目的：通過實(shí)現(xiàn)哲學(xué)家進(jìn)餐問題的同步深入了解和掌握進(jìn)程同步和互斥的原理。題目要求：簡(jiǎn)單描述哲學(xué)家進(jìn)餐問題。可設(shè)計(jì)五個(gè)哲學(xué)家，每人都需要一雙筷子。哲學(xué)家有兩種活動(dòng)：吃飯和思考，需要成功設(shè)計(jì)讓每個(gè)哲學(xué)家能夠順利吃飯。1.2 題目開發(fā)環(huán)境系統(tǒng)平臺(tái)：Windows 7 旗艦版實(shí)現(xiàn)語言：C#開發(fā)工具：Microsoft Visual Studio 20101.3開發(fā)原型圖哲學(xué)家11哲學(xué)家2哲學(xué)家5哲學(xué)家4哲學(xué)家31.4 設(shè)計(jì)界面截圖只是為了體現(xiàn)算法，關(guān)鍵我不會(huì)美工，所以界面比較簡(jiǎn)單2. 總體設(shè)計(jì)思想以及相關(guān)知識(shí)2.1總體設(shè)計(jì)思想哲學(xué)家的生活就是思考

3、和吃飯，即思考，餓了就吃，吃飽了再思考，循環(huán)往復(fù)。要求是：每一個(gè)哲學(xué)家只有在拿到位于他左右兩側(cè)的筷子后，才能夠就餐；哲學(xué)家不能拿著一只筷子不放手，也不能從其他哲學(xué)家手中搶奪筷子；哲學(xué)家每次吃飽后必須放下他手中的兩只筷子恢復(fù)思考，不能強(qiáng)抓住筷子不放。設(shè)計(jì)一個(gè)程序，能夠顯示當(dāng)前各哲學(xué)家的狀態(tài)和桌上筷子的使用情況，并能無死鎖的推算出下一狀態(tài)各哲學(xué)家的狀態(tài)和桌上筷子的使用情況。即設(shè)計(jì)一個(gè)能安排哲學(xué)家正常生活的程序。開始本來是準(zhǔn)備用C+設(shè)計(jì)的，但是最近開始自學(xué)C#，發(fā)現(xiàn)微軟封裝了很多基類，調(diào)用十分方便?？梢院芎?jiǎn)單的設(shè)計(jì)出程序，正好練習(xí)一下，所以就用C#設(shè)計(jì)程序了，同時(shí)在百度查找了很多資料。2.2 本程序

4、涉及到的概念2.2.1簡(jiǎn)介 進(jìn)程同步是一個(gè)操作系統(tǒng)級(jí)別的概念,是在多道程序的環(huán)境下，存在著不同的制約關(guān)系，為了協(xié)調(diào)這種互相制約的關(guān)系，實(shí)現(xiàn)資源共享和進(jìn)程協(xié)作，從而避免進(jìn)程之間的沖突，引入了進(jìn)程同步。2.2.2臨界資源 在操作系統(tǒng)中，進(jìn)程是占有資源的最小單位（線程可以訪問其所在進(jìn)程內(nèi)的所有資源，但線程本身并不占有資源或僅僅占有一點(diǎn)必須資源）。但對(duì)于某些資源來說，其在同一時(shí)間只能被一個(gè)進(jìn)程所占用。這些一次只能被一個(gè)進(jìn)程所占用的資源就是所謂的臨界資源。典型的臨界資源比如物理上的打印機(jī)，或是存在硬盤或內(nèi)存中被多個(gè)進(jìn)程所共享的一些變量和數(shù)據(jù)等(如果這類資源不被看成臨界資源加以保護(hù)，那么很有可能造成丟數(shù)據(jù)

5、的問題)。 對(duì)于臨界資源的訪問，必須是互訴進(jìn)行。也就是當(dāng)臨界資源被占用時(shí)，另一個(gè)申請(qǐng)臨界資源的進(jìn)程會(huì)被阻塞，直到其所申請(qǐng)的臨界資源被釋放。而進(jìn)程內(nèi)訪問臨界資源的代碼被成為臨界區(qū)。 對(duì)于臨界區(qū)的訪問過程分為四個(gè)部分： 1.進(jìn)入?yún)^(qū):查看臨界區(qū)是否可訪問，如果可以訪問，則轉(zhuǎn)到步驟二，否則進(jìn)程會(huì)被阻塞 2.臨界區(qū):在臨界區(qū)做操作 3.退出區(qū):清除臨界區(qū)被占用的標(biāo)志 4.剩余區(qū)：進(jìn)程與臨界區(qū)不相關(guān)部分的代碼2.2.3進(jìn)程同步進(jìn)程同步也是進(jìn)程之間直接的制約關(guān)系，是為完成某種任務(wù)而建立的兩個(gè)或多個(gè)線程，這個(gè)線程需要在某些位置上協(xié)調(diào)他們的工作次序而等待、傳遞信息所產(chǎn)生的制約關(guān)系。進(jìn)程間的直接制約關(guān)系來源于他們

6、之間的合作。比如說進(jìn)程A需要從緩沖區(qū)讀取進(jìn)程B產(chǎn)生的信息，當(dāng)緩沖區(qū)為空時(shí)，進(jìn)程B因?yàn)樽x取不到信息而被阻塞。而當(dāng)進(jìn)程A產(chǎn)生信息放入緩沖區(qū)時(shí)，進(jìn)程B才會(huì)被喚醒。概念如下圖所示。2.2.4進(jìn)程互斥進(jìn)程互斥是進(jìn)程之間的間接制約關(guān)系。當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū)使用臨界資源時(shí)，另一個(gè)進(jìn)程必須等待。只有當(dāng)使用臨界資源的進(jìn)程退出臨界區(qū)后，這個(gè)進(jìn)程才會(huì)解除阻塞狀態(tài)。 比如進(jìn)程B需要訪問打印機(jī)，但此時(shí)進(jìn)程A占有了打印機(jī)，進(jìn)程B會(huì)被阻塞，直到進(jìn)程A釋放了打印機(jī)資源,進(jìn)程B才可以繼續(xù)執(zhí)行。概念如下圖所示。2.2.5實(shí)現(xiàn)臨界區(qū)互斥的基本方法硬件實(shí)現(xiàn)方法 通過硬件實(shí)現(xiàn)臨界區(qū)最簡(jiǎn)單的辦法就是關(guān)CPU的中斷。從計(jì)算機(jī)原理我們知道，

7、CPU進(jìn)行進(jìn)程切換是需要通過中斷來進(jìn)行。如果屏蔽了中斷那么就可以保證當(dāng)前進(jìn)程順利的將臨界區(qū)代碼執(zhí)行完，從而實(shí)現(xiàn)了互斥。這個(gè)辦法的步驟就是:屏蔽中斷-執(zhí)行臨界區(qū)-開中斷。但這樣做并不好，這大大限制了處理器交替執(zhí)行任務(wù)的能力。并且將關(guān)中斷的權(quán)限交給用戶代碼，那么如果用戶代碼屏蔽了中斷后不再開，那系統(tǒng)豈不是跪了？ 還有硬件的指令實(shí)現(xiàn)方式，這個(gè)方式和接下來要說的信號(hào)量方式如出一轍。但是通過硬件來實(shí)現(xiàn)，這里就不細(xì)說了。信號(hào)量實(shí)現(xiàn)方式 這也是我們比較熟悉P V操作。通過設(shè)置一個(gè)表示資源個(gè)數(shù)的信號(hào)量S，通過對(duì)信號(hào)量S的P和V操作來實(shí)現(xiàn)進(jìn)程的的互斥。 P和V操作分別來自荷蘭語Passeren和Vrijgeve

8、n，分別表示占有和釋放。P V操作是操作系統(tǒng)的原語，意味著具有原子性。 P操作首先減少信號(hào)量，表示有一個(gè)進(jìn)程將占用或等待資源，然后檢測(cè)S是否小于0,如果小于0則阻塞，如果大于0則占有資源進(jìn)行執(zhí)行。 V操作是和P操作相反的操作，首先增加信號(hào)量，表示占用或等待資源的進(jìn)程減少了1個(gè)。然后檢測(cè)S是否小于0，如果小于0則喚醒等待使用S資源的其它進(jìn)程。本程序就是用信號(hào)量進(jìn)行實(shí)現(xiàn)的。3流程和效果圖3.1程序流程圖及簡(jiǎn)介單擊“開始進(jìn)餐”按鈕首先初始化哲學(xué)家和筷子對(duì)象，然后聲明五個(gè)進(jìn)程。進(jìn)程逐一開始后判斷當(dāng)前哲學(xué)家兩側(cè)的筷子是否無人使用，如果無人使用則當(dāng)前哲學(xué)家開始進(jìn)餐，并改變程序界面哲學(xué)家標(biāo)簽的文字為“哲學(xué)家

9、i開始進(jìn)餐”，同時(shí)更改哲學(xué)家兩側(cè)筷子標(biāo)簽為“哲學(xué)家i拿起筷子”，哲學(xué)家文字后面的變量i為當(dāng)前哲學(xué)家編號(hào)。為了防止長(zhǎng)時(shí)間誰也拿不到筷子，暫停進(jìn)程1.5秒。1.5秒后當(dāng)前哲學(xué)家停止進(jìn)餐開始思考，并釋放兩側(cè)筷子的資源，更改哲學(xué)家標(biāo)簽為“哲學(xué)家i在思考”，更改哲學(xué)家兩側(cè)筷子標(biāo)簽為“無人使用的筷子”。I為哲學(xué)家編號(hào)變量。當(dāng)一個(gè)哲學(xué)家完成吃飯、思考的過程后，重新進(jìn)去排隊(duì)，等待兩側(cè)的筷子資源被別的哲學(xué)家釋放，進(jìn)入下一個(gè)循環(huán)。如下圖所示：開始吃飯進(jìn)程暫停1.5秒開始思考放下兩側(cè)的筷子是否開始進(jìn)餐哲學(xué)家和筷子對(duì)象初始化聲明五個(gè)進(jìn)程哲學(xué)家兩側(cè)的筷子是否無人使用聲明五個(gè)進(jìn)程以后，每個(gè)進(jìn)程在后臺(tái)無限循環(huán)，判斷的過程都

10、是一樣的，因此這里只標(biāo)明一個(gè)進(jìn)程的判斷流程3.2流程圖各階段程序界面的變化程序設(shè)計(jì)界面開始運(yùn)行程序，并初始化哲學(xué)家和筷子對(duì)象狀態(tài)單擊開始進(jìn)餐按鈕以后判斷哲學(xué)家兩側(cè)的筷子為無人使用狀態(tài)時(shí)，哲學(xué)家開始進(jìn)餐，并改變標(biāo)簽文字哲學(xué)家進(jìn)餐后進(jìn)入思考狀態(tài)，并釋放兩側(cè)的筷子4程序源代碼using System;using System.Collections.Generic;using System.ComponentModel;using System.Data;using System.Drawing;using System.Text;using System.Windows.Forms;using S

11、ystem.Threading;namespace PhEating / / 進(jìn)程同步與互斥 哲學(xué)家進(jìn)餐問題 / public partial class MainForm : Form private Mutex m_chopsticksMux; /筷子對(duì)象 private Thread m_thread; private Label m_phInfo; /哲學(xué)家標(biāo)簽 private Label m_chopInfo; /筷子標(biāo)簽 private SynchronizationContext m_context; private bool m_isRunning = true; / / 哲學(xué)

12、家對(duì)象 / public class Philospher /哲學(xué)家名字 public String m_name; /哲學(xué)家拿到手里的筷子 public ChopStick m_left; public ChopStick m_right; /哲學(xué)家編號(hào) public int m_index; /釋放雙手的筷子 public void Release() m_left.Release(); m_right.Release(); / / 筷子對(duì)象 / public class ChopStick public Mutex m_mutex; public int m_number; public

13、 void Release() m_mutex.ReleaseMutex(); public MainForm() InitializeComponent(); m_context = SynchronizationContext.Current; m_phInfo = new Label5; m_phInfo0 = label1; m_phInfo1 = label2; m_phInfo2 = label3; m_phInfo3 = label4; m_phInfo4 = label5; /初始化哲學(xué)家狀態(tài)為思考 for (int i = 0; i 5;i+ ) m_phInfoi.Text

14、 =哲學(xué)家+(i+1)+ : 在思考; m_phInfoi.BackColor = Color.Gray; m_chopInfo = new Label5; m_chopInfo0 = label6; m_chopInfo1 = label7; m_chopInfo2 = label8; m_chopInfo3 = label9; m_chopInfo4 = label10; /初始化筷子狀態(tài)為無人使用 for (int i = 0; i 5; i+) m_chopInfoi.Text = 無人使用的筷子; /單擊開始進(jìn)餐按鈕 private void button1_Click(object

15、 sender, EventArgs e) m_chopsticksMux = new Mutex5; m_thread = new Thread5; for(int i=0;i5;i+) m_chopsticksMuxi=new Mutex(true,筷子+i.ToString(); ParameterizedThreadStart pts; for (int i = 0; i 5; i+) pts = new ParameterizedThreadStart(Eating); m_threadi = new Thread(pts); Philospher ph = new Philosph

16、er(); ph.m_name = 哲學(xué)家1; ph.m_index = 0; ChopStick csl = new ChopStick(); csl.m_number = 4; csl.m_mutex = m_chopsticksMux4; ph.m_left = csl; ChopStick csr = new ChopStick(); csr.m_number = 0; csr.m_mutex = m_chopsticksMux0; ph.m_right = csr; m_thread0.Start(ph); for (int i = 1; i 5; i+) ph = new Phil

17、ospher(); ph.m_name = 哲學(xué)家 + (i+1).ToString(); ph.m_index = i; csl = new ChopStick(); csl.m_number = i-1; csl.m_mutex = m_chopsticksMuxi - 1; ph.m_left = csl; csr = new ChopStick(); csr.m_number = i; csr.m_mutex = m_chopsticksMuxi; ph.m_right = csr; m_threadi.Start(ph); /釋放所有的筷子 for (int i = 0; i 5;

18、i+) m_chopsticksMuxi.ReleaseMutex(); /進(jìn)程中的哲學(xué)家 private void Eating(object para) Philospher ph = para as Philospher; WaitHandle hd = new WaitHandle2; hd0 = ph.m_left.m_mutex; hd1 = ph.m_right.m_mutex; while (true & m_isRunning) /當(dāng)數(shù)組hd中的倆根筷子都釋放的時(shí)候 if (Mutex.WaitAll(hd) StartEating(ph); Thread.Sleep(150

19、0); StopEating(ph); ph.Release(); /哲學(xué)家進(jìn)餐事件 private void StartEating(Philospher ph) m_context.Post(new SendOrPostCallback (delegate m_phInfoph.m_index.Text = ph.m_name + : 開始吃飯; m_phInfoph.m_index.BackColor = Color.Red; m_chopInfoph.m_left.m_number.Text = ph.m_name + 拿起筷子; m_chopInfoph.m_left.m_number.BackColor = Color.Green; m_chopInfoph.m_right.m_number.Text = ph.m_name + 拿起筷子; m_chopInfoph.m_right.m_number.BackColor = Color.Green; ), null); /哲學(xué)家思考事件 private void StopEating(Philospher ph) m_context.Post(new SendOrPostCallback(delegate m_phInfoph.m_index.Text =