作業系統學習筆記（五）---程序同步

目錄

例題

基本概念

背景

基本概念

Peterson算法

硬體同步

信号量 & PV原語：

管程

死鎖和饑餓

例題

1.In Section 5.4, we mentioned that disabling interrupts frequently can affect the system’s clock. Explain why this can occur and how such effects can be minimized.

Answer：

系統時鐘的更新是由時鐘中斷決定的（每個時鐘中斷更新一次）。如果中斷被禁止了（假設時間比較長），那麼系統時鐘就有可能損失目前時間。另外系統時鐘還用于排程，比如RR算法的時間片的計算。

要減少這種情況的發生，可以将對時鐘中斷的禁止時間設定為盡可能的小。

2.Explain why Windows, Linux, and Solaris implement multiple locking mechanisms. （多個鎖定機制）Describe the circumstances under which they use spinlocks（自旋鎖）, mutex locks（互斥鎖）, semaphores（信号量）, adaptive mutex locks（自适應互斥鎖）, and condition variables（條件變量）. In each case, explain why the mechanism is needed.

Answer:題目要求解釋為何OS使用多個鎖定機制并解釋其适用條件。

①互斥鎖适用于單處理器系統以及阻塞時間比較長的情況，一個線程占用了目前共享資源，使用互斥鎖将其lock住之後，其他線程就無法通路，必須等到unlock之後，其他線程才能利用共享資源裡面的内容。

②自旋鎖即采用“忙等待”的方式來控制程序同步，多處理器情況忙等待就比較好，因為切換的開銷是很大的。

③信号量（Samephore）由一個值和一個指針組成，指針指向等待該信号量的程序。信号量的值表示相應資源的使用情況。信号量S>=0時，S表示可用資源的數量。執行一次P操作意味着請求配置設定一個資源，是以S的值減1；當S<0時，表示已經沒有可用資源，S的絕對值表示目前等待該資源的程序數。請求者必須等待其他程序釋放該類資源，才能繼續運作。而執行一個V操作意味着釋放一個資源，是以S的值加1；若S<0，表示有某些程序正在等待該資源，是以要喚醒一個等待狀态的程序，使之運作下去。

信号量是選擇睡眠的方式來對共享工作停止通路的（即建立一個與該信号量相關的等待隊列）。

信号量是用于解決程序/線程之間的同步和互斥問題的一種通信機制，是用來保證兩個或多個關鍵代碼不被并發調用。

信号量的适用條件？感覺絕大多數情況下都适用，互斥鎖可以了解為二進制信号量，管程也基于信号量......

④适應互斥：adaptive mutex是Solaris提供的保護對臨界資料項的通路的方法。在多處理器系統中，适應互斥以自旋鎖實作的标準信号量而開始。如果資料已加鎖，那麼适應互斥有兩個選擇。如果鎖是被正在另一個CPU上運作的線程所擁有，那麼擁有鎖的線程可能會很快結束，是以請求鎖的線程就自旋并等待。如果擁有鎖的線程現在不處于運作狀态，那麼線程就阻塞并進入睡眠，直到釋放時被喚醒。（因為睡眠線程擁有的鎖通常不能被很快釋放，是以進行睡眠以避免自旋）

簡而言之，适應互斥相當于選擇自旋還是睡眠。減少了開銷。

⑤condition variables用于管程模型，管程是一種抽象資料結構，其不可或缺的一個資料成員就是條件變量。以下是其特點：

---采用面向對象方法，簡化線程同步

---同一時刻僅有一個線程在管程中工作

---可臨時放棄管程的通路權，叫醒一個在等待隊列中的線程，這是其他方法都沒有的(原子鎖和信号量一旦進入臨界區就必須執行完臨界區代碼才能退出)，而實作這一點采用的就是條件變量

3.Explain why spinlocks are not appropriate for single-processor systems yet are often used in multiprocessor systems.

Answer:

在單處理器系統中，使用自旋鎖會造成其他程序忙等待（任何其他試圖進入臨界區的程序都必須在其進入代碼中連續地循環），這樣就浪費了CPU時鐘。而對于多處理器系統，當一個程序在一個處理器自旋時，另一個程序可以在另一處理器上在其臨界區内執行，且使用自旋鎖，程序在等待鎖時還在運作，不用進行上下文切換。

4.

Assumethat that a finite number of resources of a single resource type must be managed.Processes may ask for a number of these resources and will return them once finished. As an example, many commercial software packages provide a given number of licenses, indicating the number of applications that may run concurrently.When the application is started, the license count is decremented.When the application is terminated,the license count is incremented. If all licenses are in use, requests to start the application are denied. Such requests will only be granted when an existing license holder terminates the application and a license is returned. The following program segment is used to managea finite number of instances of an available resource. The maximum number of resources and the number of available resourcesare declared as follows:

#define MAX RESOURCES 5

int available resources = MAX RESOURCES;

When a process wishes to obtain a number of resources, it invokes the decrease count() function:

The preceding program segment produces a race condition（前面的程式段産生一個競争條件）. Do the following:

a. Identify the data involved in the race condition.

b. Identify the location (or locations) in the code where the race condition occurs.

c. Using a semaphore（信号量） or mutex lock（互斥鎖）,fix the race condition. It is permissible to modify the decrease count() function so that the calling process is blocked until suffient resources are available.

Answer:

a.競争條件：如果兩個程序并發地執行decrease_count函數，那麼它們對共享變量avaliable_resources的操作請求便會産生競争進而導緻無法确定到底執行哪個程序或者資源不足卻執行了兩個程序的情況。

b.變量available_resources是産生競争的原因

c.代碼如下，因為題目給的條件不夠充足，是以給出以下設定

①available_resources為全局變量（總資源數），初始為100

②以下示例代碼隻讓2個線程在跑，其循環調用decrease_count函數，每次讓資源數-1

#include<stdio.h>
#include<unistd.h>
#include<pthread.h>

pthread_mutex_t mutex;
int available_resources = 100; 

int decrease_count(int count)
{
	pthread_mutex_lock(&mutex);        //調用該函數，線程會阻塞直到互斥鎖占有pthread_mutex_unlock()函數為止 
	if(available_resources < count)
	  return -1;
	else
	{
		available_resources -= count;
		printf("The current available_resources is:%d\n",available_resources);
		pthread_mutex_unlock(&mutex);
		usleep(100);                         //解鎖後的線程一般要等待一會 
		return 0;
	}
	
}

void *thread1(void *arg)
{
	int cnt = *(int *)arg;
	while(available_resources != 0)
	{
		decrease_count(cnt);
	}
}
void *thread2(void *arg)
{
	int cnt = *(int *)arg;
	while(available_resources != 0)
	{
		decrease_count(cnt);
	}
}

int main()
{
	int decrease = 1;
	pthread_mutex_init(&mutex,NULL);   //建立互斥鎖 
	pthread_t tid1,tid2;
	pthread_create(&tid1,NULL,thread1,&decrease);
	pthread_create(&tid2,NULL,thread2,&decrease);
	pthread_join(tid1,NULL);
	pthread_join(tid2,NULL);
	return 0;
}
           

我們可以簡單看下不加鎖的後果（把pthread_mutex_lock注釋掉即可）

顯然對資源的使用會出現混亂（如果不讓線程等待100微秒的話就更亂了）

然後我們再看看加了互斥鎖後的效果

可以看出是按每次-1的順序跑下來的，沒有資源的搶占情況。

5.

更多習題推薦：https://wenku.baidu.com/view/39d6ea1b580216fc700afd7c.html

基本概念

背景

如果生産者程序和消費者程序同時對共享變量操作，那麼就會導緻競争條件而出錯，為了避免這樣的錯誤，同一時間隻允許一個程序改變共同變量、共同表等東西。

基本概念

Atomic operation（原子操作） means an operation that completes in its entirety without interruption

這個操作能不中斷地完整地執行，換個思路來想，執行該操作的時候不會發生線程/程序切換（CPU實際上隻會運作1個目前線程，多CPU的話需要加額外的條件這裡不讨論）

Race condition: The situation where several processes access – and manipulate shared data concurrently. The final value of the shared data depends upon which process finishes last.

競争條件：多個程序并發地通路和操作同一資料且執行結果與通路發生的特定順序有關。

To prevent race conditions, concurrent processes must be synchronized. 為了阻止出現競争的條件，并發程序必須同步。

同步（synchronization）    協調（coordination）

臨界區問題The Critical-Section Problem

每個程序必須請求進入其臨界區（critical section），實作這一請求的代碼段稱為進入區（entry section），臨界區之後可有退出區（exit section）。其他代碼段稱為剩餘區（remainder section）。

臨界區就是一個代碼段，在這部分代碼段中，會改變共同變量、共同表、寫一個檔案等。是以我們需要有這樣一個機制，用來保證一個程序進入臨界區，沒有其他程序被允許在臨界區内執行。

臨界區問題的解答必須滿足以下三個要求：

1. Mutual Exclusion（互斥條件）:如果程序Pi在其臨界區内執行，那麼其他程序不能在臨界區内執行。
2. Progress（前進，進入條件）:若沒有程序在臨界區執行，那麼選擇需要進入臨界區的程序進入臨界區執行。選擇程序進入臨界區是不能無線等待的。
3. Bounded Waiting（有限等待）:每個需要進入臨界區的程序，都必須有機會進入。（從一個程序請求進入臨界區開始，到該請求被允許為止，其他程序允許進入臨界區的次數有上限）

有兩種辦法解決作業系統内的臨界區問題：搶占核心與非搶占核心。

1. 非搶占核心比較簡單，因為同一時刻隻有一個程序在核心模式，不會發生競争條件。而搶占核心就不同了，需要設計核心的資料結構以確定其不會導緻競争條件。
2. 搶占核心更适于實時程式設計，且響應速度更快。

Peterson算法

---僅供學習基于軟體的解決臨界區問題的辦法，沒有實際意義（該算法假設隻有i和j兩個程序）

peterson算法需要在兩格程序之間共享兩個資料項： int turn； boolean flag[2];

turn表示哪個程序可以進入其臨界區，數組flag[i]表示哪個程序想要進入臨界區。

分析上面的算法，當flag[j]為真，說明另一個程序也要進入臨界區，turn==j有有兩種情況，第一說明另一程式還沒有執行到改變turn的這一步，但此時flag[j] = true,說明它已經執行了改變turn的上面的那句，那麼下一步馬上就要執行turn = i這步了，這樣一來，這邊的i程序馬上就可以進入臨界區開始執行。在臨界區執行的這段時間flag[i] = true,并且剛剛turn也修改為i,是以程序j不可能進入臨界區，而當這邊的程序離開臨界區的時候，flag[i]就會被設定為false,這樣另一程序就可以進來了（保證一個程序不會循環進入臨界區（一直為該程序））

硬體同步

程序互斥的硬體解法

用特殊指令來達到保護臨界區的目的；

1. 開關中斷指令：

1）簡單、高效

2）代價高，限制CPU的并發能力

3）不适用于多處理器

4）适用于作業系統本身，不适用于使用者程式

2. 測試并加鎖指令：

3. 交換指令： 

4. 忙等待：程序在得到臨界區通路權限之前，持續做測試而不做其他事情；（單CPU不提倡）

自旋鎖：（多處理器情況），忙等待就比較好，因為切換的開銷是很大的；

信号量 & PV原語：

指的是對信号量的兩個标準原子操作。（注意了解原子操作！不要亂加mutex）

P操作：

wait(S){

  while(S<=0)

  ;  // no-op

  S--;

}

V操作：

signal(S){

  S++;

}
           

P（荷蘭語proberen，測試） V（荷蘭語verhogen，增加），由荷蘭科學家Dijkstra提出

荷蘭科學家Dijkstra

主要貢獻：

提出信号量和PV原語;

解決了“哲學家聚餐”問題;

Dijkstra最短路徑算法和銀行家算法的創造者;

改進的PV操作

對自旋鎖改進，讓等待的程序在等待隊列中等待

該方案首先将信号量定義為一種結構體

typedef struct{

  int value;

  struct process *list;

}semaphore;

每個信号量有一個整型值和一個程序連結清單，當一個程序必須等待信号量時，就加入到程序連結清單上。

然後對wait和signal操作改進

wait(semaphore *S){

  S->value--;

  if(S->value < 0){

    add this process to S ->list;

    block();

  }

}

signal(semaphore *S){

  S->value++;

  if(S->value<=0){

    remove a process P from S->list;

    wakeup(P);

}
           

注意這裡的信号量是允許為負數的（絕對值表示等待隊列中的程序個數）

管程

關于管程的描述：

管程是一種用于多線程互斥通路共享資源的程式結構

①采用面向對象方法，簡化了線程間的同步控制

②任一時刻最多隻有一個線程執行管程代碼

③正在管程中的線程可臨時放棄管程的互斥通路，等待事件出現時恢複

條件變量（Condition Variable）

條件變量是管程内的等待機制

①進入管程的線程因資源被占用而進入等待狀态

②每個條件變量表示一種等待原因，對應一個等待隊列

Wait（）操作

①将自己阻塞在等待隊列中

②喚醒一個等待者或釋放管程的互斥通路

Signal（）操作

①将等待隊列中的一個線程喚醒

②如果等待隊列為空，則等同于空操作

條件變量初值是0，信号量初值是資源個數

管程的資料結構大概是這樣的

typedef struct monitor{

    semaphore_t mutex;     // 二值信号量，隻允許一個程序進入管程，初始化為1

    semaphore_t next;       //配合cv，用于程序同步操作的信号量

    int next_count;          // 睡眠在next的等待隊列上的程序數量

    condvar_t *cv;          // 條件變量cv

} monitor_t; 

typedef struct condvar{

    semaphore_t sem; //用于發出wait_cv操作的等待某個條件C為真的程序睡眠

    int count;       // 在這個條件變量上的睡眠程序的個數

    monitor_t * owner; // 此條件變量的宿主管程

} condvar_t;

死鎖和饑餓

兩個或多個程序無限地等待一個事件，而該事件隻能由這些等待程序之一産生，處于這種狀态時，這些程序就稱為死鎖（deadlocked）

程序在信号量内無限期等待，稱這種狀态為無限期阻塞（indefinite blocking）或饑餓(starvation)

推薦實驗：清華大學ucore lab.........https://objectkuan.gitbooks.io/ucore-docs/content/lab7/lab7_3_4_monitors.html