並發性[程式並發性]

並發性[程式並發性]
更多義項 ▼ 收起列表 ▲

並發是指兩個或多個事件在同一時間間隔內發生。在多道程式環境下,並發性是指在一段時間巨觀上有多個程式在同時運行,但在單處理機系統中,每一時刻卻僅能只有一道程式在執行,故微觀上這些程式只能時分時交替執行

出現的環境

1、多處理管理器:共享處理器時間

2、結構化應用程式:設計成一組並發進程

3、作業系統:上一點用於作業系統

進程同步

是進程之間直接的制約關係,是為完成某種任務而建立的兩個或多個執行緒,這個執行緒需要在某些位置上協調他們的工作次序而等待、傳遞信息所產生的制約關係。進程間的直接制約關係來源於他們之間的合作。

比如說進程A需要從緩衝區讀取進程B產生的信息,當緩衝區為空時,進程A因為讀取不到信息而被阻塞。而當進程B產生信息放入緩衝區時,進程A才會被喚醒。

進程互斥

是進程之間的間接制約關係。當一個進程進入臨界區使用臨界資源時,另一個進程必須等待。只有當使用臨界資源的進程退出臨界區後,這個進程才會解除阻塞狀態。

比如進程B需要訪問印表機,但此時進程A占有了印表機,進程B會被阻塞,直到進程A釋放了印表機資源,進程B才可以繼續執行。

臨界資源

在作業系統中,進程是占有資源的最小單位(執行緒可以訪問其所在進程內的所有資源,但執行緒本身並不占有資源或僅僅占有一點必須資源)。但對於某些資源來說,其在同一時間只能被一個進程所占用。這些一次只能被一個進程所占用的資源就是所謂的臨界資源。典型的臨界資源比如物理上的印表機,或是存在硬碟或記憶體中被多個進程所共享的一些變數和數據等(如果這類資源不被看成臨界資源加以保護,那么很有可能造成丟數據的問題)。

對於臨界資源的訪問,必須是互訴進行。也就是當臨界資源被占用時,另一個申請臨界資源的進程會被阻塞,直到其所申請的臨界資源被釋放。而進程內訪問臨界資源的代碼被成為臨界區。

對於臨界區的訪問過程分為四個部分:

1.進入區:查看臨界區是否可訪問,如果可以訪問,則轉到步驟二,否則進程會被阻塞

2.臨界區:在臨界區做操作

3.退出區:清除臨界區被占用的標誌

4.剩餘區:進程與臨界區不相關部分的代碼

互斥的要求:

必須強制實施互斥,即一次只允許一個進程進入臨界區。一個在非臨界區停止的程式不能幹涉其他程式。有限等待,即決不允許需要訪問臨界區的進程被無限延遲的情況,即死鎖或餓死,有空讓進,臨界區空閒時,請求程式可進,對相關進程的執行速度和處理器的速度沒有任何要求和限制。一個進程駐留在臨界區的時間必須是有限的。

互斥的實現:

軟體的方法:由並發執行進程擔任這個責任

機器指令:減少開銷,但不能通用

基本方法

硬體實現方法

中斷禁用

單處理器中並發進程不能重疊只能交替,一個進程一直運行到調用系統服務或被中斷。保證互斥只需保證一個進程不被中斷

缺點:一長時間中斷禁止,中斷效率會降低。二不能用於多處理結構中

專用機器指令

用於保證訪問的原子性。1、比較和交換指令(compare and swap)、2、Exchange指令

機器指令方法的特點:

1、適合在單處理器或共享記憶體的多處理器上的任何數目的進程

2、非常簡單且易於證明

3、可用於支持多個臨界區,可用自己的變數定義

缺點

1、忙等待,進程等待進入臨界區,仍然會繼續消耗CPU的時間

2、可能飢餓,當需要等待程式進入時,某些可能被無限拒絕

3、可能死鎖,低優先權的進程占用高優先權的進程所需的資源

信號量實現方法

解決並發問題基本原理

兩個或多個進程可以通過簡單的信號進行合作,一個進程可以被迫在某一個位置停止,直到它接到某一個特定的信號。複雜的合作需求都可以通過適當的信號結構完成。只需要一個特殊的變數(整數型):稱為信號量

信號量的三個操作

1、信號量s可以初始化成非負數

用於互斥:s=1

用於同步:s>=0

2、semWait(s)進程請求分配一個資源,操作使信號量減1,若為負。進程阻塞。否則繼續執行

3、semSignal(s)進程釋放一個資源,操作使信號量加1,若小於或等於0.則阻塞的進程被解除阻塞

信號量的使用規則

1、semWait和seSignal必須成對出現

互斥時,位於同一進程,臨界區的前後

同步時,交錯出現在兩個合作進程內

2、多個seWait次序不能顛倒,否則可能導致死鎖

3、用於同步的semWait應出現在用於互斥的semSignal之前

4、多個semSigal次序可以任意

5、在進程對信號量減1之前無法提前知道該信號量是否會被阻塞

6、當進程對一個信號量加1後。另一個進程會被喚醒,兩個進程繼續並發運行

7、在向信號量發出信號後,不需要知道是否有另一個進程在正在等待,被解除阻塞的進程數量或者沒有或者是1

管程實現方法

信號量為實施互斥和進程間合作提供了強大靈活的工具,但存在難點。即semWait和semSignal操作可能分布在整個程式中,很難看出整體效果,因此提出管程(Monitor),一個程式設計語言結構,可以鎖定任何對象,提供與信號量相同的功能,更易於控制

使用信號的管程

定義:管程由一個或多個進程、一個初始化序列和局部數據組成的軟體模組

特點:

1、局部數據變數只能被管程的過程訪問,任何外部過程都不能訪問

2、一個進程通過調用管程的一個過程進入管程

3、在任何時候、只能有一個進程在管程中執行,調用管程的其他任何程式都被阻塞

管程的幾個要素

1、管程中的共享變數在外部不可見,只能通過管程內所說明的過程間接訪問

2管程必須互斥進入:管程中的數據變數每次只能被一個進程訪問,保證數據完整性

3、管程通常用來管理資源,應當沒有進程等待隊伍、相應的等待及喚醒

4、Q進去管程等待時,釋放管程互斥權,P進入管程,喚醒Q

P等待Q繼續,直到Q退出或等待

P等待Q繼續,直到P退出或等待

規定喚醒為進程中最後一個操作

同步的問題

生產者--消費者問題

生產者-消費者問題是一個經典的進程同步問題,該問題最早由Dijkstra提出,用以演示他提出的信號量機制。本作業要求設計在同一個進程地址空間內執行的兩個執行緒。生產者執行緒生產物品,然後將物品放置在一個空緩衝區中供消費者執行緒消費。消費者執行緒從緩衝區中獲得物品,然後釋放緩衝區。當生產者執行緒生產物品時,如果沒有空緩衝區可用,那么生產者執行緒必須等待消費者執行緒釋放出一個空緩衝區。當消費者執行緒消費物品時,如果沒有滿的緩衝區,那么消費者執行緒將被阻塞,直到新的物品被生產出來

這裡生產者和消費者是既同步又互斥的關係,首先只有生產者生產了,消費著才能消費,這裡是同步的關係。但他們對於臨界區的訪問又是互斥的關係。因此需要三個信號量empty和full用於同步緩衝區,而mut變數用於在訪問緩衝區時是互斥的。參考程式如下:

class ProducerAndCustomer

{

//臨界區信號量

private static Mutex mut = new Mutex();

private static Semaphore empty = new Semaphore(5, 5);

//空閒緩衝區

private static Semaphore full = new Semaphore(0, 5);

//生產者-消費者模擬

static void Main()

{

Console.WriteLine("生產者消費者模擬......");

for (int i = 1; i < 9; i++)

{

Thread Thread1 = new Thread(new ThreadStart(Producer));

Thread Thread2 = new Thread(new ThreadStart(Customer));

Thread1.Name = String.Format("生產者執行緒{0}", i);

Thread2.Name = String.Format("消費者執行緒{0}", i);

Thread1.Start();

Thread2.Start();

}

Console.ReadKey();

}

private static void Producer()

{

Console.WriteLine("{0}已經啟動",Thread.CurrentThread.Name);

empty.WaitOne();//對empty進行P操作

mut.WaitOne();//對mut進行P操作

Console.WriteLine("{0}放入數據到臨界區", Thread.CurrentThread.Name); Thread.Sleep(1000);

mut.ReleaseMutex();//對mut進行V操作

full.Release();//對full進行V操作

}

private static void Customer()

{

Console.WriteLine("{0}已經啟動", Thread.CurrentThread.Name);

Thread.Sleep(12000);

full.WaitOne();//對full進行P操作

mut.WaitOne();//對mut進行P操作

Console.WriteLine("{0}讀取臨界區", Thread.CurrentThread.Name);

mut.ReleaseMutex();//對mut進行V操作

empty.Release();//對empty進行V操作

}

}

讀者--寫者問題

一個數據檔案或記錄,統稱數據對象,可被多個進程共享,其中有些進程只要求讀稱為"讀者",而另一些進程要求寫或修改稱為"寫者"。

規定:允許多個讀者同時讀一個共享對象,但禁止讀者、寫者同時訪問一個共享對象,也禁止多個寫者訪問一個共享對象,否則將違反Bernstein並發執行條件。

通過描述可以分析,這裡的讀者和寫者是互斥的,而寫者和寫者也是互斥的,但讀者之間並不互斥。

由此我們可以設定3個變數,一個用來統計讀者的數量,另外兩個分別用於對讀者數量讀寫的互斥,讀者和讀者寫者和寫者的互斥。參考程式如下:

class ReaderAndWriter

{

private static Mutex mut = new Mutex();//用於保護讀者數量的互斥信號量

private static Mutex rw = new Mutex();//保證讀者寫者互斥的信號量

static int count = 0;//讀者數量

static void Main()

{

Console.WriteLine("讀者寫者模擬......");

for (int i = 1; i < 6; i++)

{

Thread Thread1 = new Thread(new ThreadStart(Reader));

Thread1.Name = String.Format("讀者執行緒{0}", i);

Thread1.Start();

}

Thread Thread2 = new Thread(new ThreadStart(writer));

Thread2.Name = String.Format("寫者執行緒");

Thread2.Start();

Console.ReadKey();

}

private static void Reader()

{

mut.WaitOne();

if (count == 0)

{

rw.WaitOne();

}

count++;

mut.ReleaseMutex();

Thread.Sleep(new Random().Next(2000));//讀取耗時1S

Console.WriteLine("讀取完畢");

mut.WaitOne();

count--;

mut.ReleaseMutex();

if (count == 0)

{

rw.ReleaseMutex();

}

}

private static void writer()

{

rw.WaitOne();

Console.WriteLine("寫入數據");

rw.ReleaseMutex();

}

相關詞條

熱門詞條

聯絡我們