並發是指兩個或多個事件在同一時間間隔內發生。在多道程式環境下，並發性是指在一段時間巨觀上有多個程式在同時運行，但在單處理機系統中，每一時刻卻僅能只有一道程式在執行，故微觀上這些程式只能時分時交替執行
基本介紹
- 中文名：並發性
- 外文名：Concurrency
出現的環境,進程同步,進程互斥,臨界資源,基本方法,同步的問題,
出現的環境
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();
}
