同步互斥小口訣

• 畫圖理解題目
• 判斷題目類型
• 分析進程數目 填寫進程模板
• 補充基本代碼(偽代碼)
• 補充PV代碼
• 檢查調整代碼

注意事項

• 代碼是一步一步寫出來的，代碼是反復調整寫出來的
• 60%是生產者和消費者模型
• 30%是讀者和寫者的模型

生產者和消費者

例子1

• 媽媽每次放放一個蘋果到桌子上，孩子每次從桌子上取一個蘋果。取蘋果和放蘋果不可以同時進行，而且桌子上最多只能放10個蘋果，請使用pv代碼實現同步互斥
• 箭頭 代表生產的含義，數目代表生產的數量

• 特征：1，存在一個容器，具有容量的限制；2，具有生產行為和消費行為，生產行為增加容量，消費行為減少容量
• 分析：生產者：需要考慮容器的容量，考慮的是剩余空間；消費者：需要考慮已占用空間
• 進程的數目：母親 和 孩子兩個進程
• 補充基本代碼? 取一個蘋果 和 放一個蘋果
• 補充PV代碼 full代表占用空間；empty代表已經占用的空間；p代表減；v代表加
• 使用P(s)和V(s)包住會改變容器容量的代碼，也就是臨界資源
• 代碼

semaphore full = 0;  //表示資源
semaphore empty = 10;//表示資源
semaphore s = 1;     //表示互斥
孩子(){while(1){p(full);//是否有已占用空間，有則減少已占用空間，無則等待p(s);取一個蘋果;v(s);v(empty);//增加剩余空間}
}媽媽(){while (1){p(empty);//是否有剩余空間，有則減少剩余空間，無則等待p(s);放一個蘋果;v(s);v(full);//增加已占用空間}}

例子2

• 桌子上有一個盤子，每次只能放入一個水果，媽媽放入橘子，爸爸放入蘋果，兒子吃橘子，女兒吃蘋果。盤子為空，爸爸媽媽才可以放入水果，當盤子的水果和兒子或者女兒匹配的時候，兒子和女兒才可以拿水果
• 消費者(兒子) 關注橘子；消費者(女兒)關注蘋果；生產者(媽媽)關注盤子空間；生產者(爸爸)關注盤子空間
• 四個進程?

• mutex 和 plate的效果是等價的，因此，這里不加mutex也是可以的
• 代碼

semaphore orange = 0;  
semaphore apple = 0;
semaphore plate = 1;
semaphore mutex = 1;
媽媽(){while(1){p(plate);p(mutex);放橘子;v(mutex);v(orange);}
}爸爸(){while (1){p(plate);p(mutex);放蘋果;v(mutex);v(apple);}}兒子(){while (1){p(orange);p(mutex);吃橘子;v(mutex);v(plate);}}女兒(){while (1){p(apple);p(mutex);吃蘋果;v(mutex);v(plate);}}

?例子3?

• AB兩個人通過信箱進行辯論，每個人都從自己的信箱取出對方的問題，將答案和新的問題組成一個郵件放入對方的信箱中，假設A的信箱可以裝入M個郵件，B的信箱可以裝入N個郵件，初始的時候，A信箱有X封郵件，B信箱有y封郵件，辯論者每次只取一封郵件，請使用PV操作實現，并解釋信號量初值和含義
• 分析
• 生產者 A? 關注 B的郵箱剩余空間
• 生產者 B 關注 A的郵箱剩余空間
• 消費者 A?關注 A的郵箱有多少封信件
• 消費者 B 關注 B的郵箱有多少封信件

• 代碼

semaphore mutex_A = 1;  
semaphore mutex_B = 1;  
semaphore full_A = x;
semaphore empty_A = M - x;
semaphore full_B = y;
semaphore empty_B = N - y;
A(){while(1){p(full_A);p(mutex_A);從A的郵箱抽取信件;v(mutex_A);v(empty_A);p(empty_B);p(mutex_B);向B的郵箱投遞信件;v(mutex_B);v(full_B);}
}B(){while (1){p(full_B);p(mutex_B);從B的郵箱抽取信件;v(mutex_B);v(empty_B);p(empty_A);p(mutex_A);向A的郵箱投遞信件;p(mutex_A);p(full_A);}}

semaphore empty = 1000;  
semaphore full = 0;  
semaphore mutex = 1;
semaphore mutex_2 = 1;
生產者i(){while(1){p(empty);p(mutex);放一件物品;v(mutex);v(full);}
}生產者j(){while(1){p(empty);p(mutex);放一件物品;v(mutex);v(full);}
}消費者m(){while (1){p(mutex_2);for(int i = 0;i < 10;i++){p(full);p(mitex);取一件物品;v(mutex);v(empty);}v(mutex_2);}}消費者n(){while (1){p(mutex_2);for(int i = 0;i < 10;i++){p(full);p(mitex);取一件物品;v(mutex);v(empty);}v(mutex_2);}}