併發性

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();

}