佚催楚?屁侏、芝村侏佚催楚參式旋喘佚催楚糞孖序殻札鰍才念駁購狼

<貧匯准和匯准>

佚催楚字更頁匯嶽孔嬬熟膿議字崙?辛喘栖盾畳札鰍嚥揖化議諒籾?万峪嬬瓜曾倖炎彈議圻囂wait(S)才signal(S)栖恵諒?匆辛參芝葎“P荷恬”才“V荷恬”。

圻囂頁峺頼撹蝶嶽孔嬬拝音瓜蛍護音瓜嶄僅峇佩議荷恬會双?宥械辛喇啣周栖糞孖頼撹音瓜蛍護峇佩蒙來議孔嬬。泌念峰議“Test-and-Set”才“Swap”峺綜?祥頁喇啣周糞孖議圻徨荷恬。圻囂孔嬬議音瓜嶄僅峇佩蒙來壓汽侃尖字扮辛喇罷周宥狛徳盈嶄僅圭隈糞孖。

圻囂岻侭參音嬬瓜嶄僅峇佩?頁咀葎圻囂斤延楚議荷恬狛殻泌惚瓜嬉僅?辛嬬氏肇塰佩総匯倖斤揖匯延楚議荷恬狛殻?貫遇竃孖匝順粁諒籾。泌惚嬬校孀欺匯嶽盾畳匝順粁諒籾議圷圭隈?祥辛參糞孖斤慌峴延楚荷恬議圻徨來。

屁侏佚催楚

屁侏佚催楚瓜協吶葎匯倖喘噐燕幣彿坿方朕議屁侏楚S?wait才signal荷恬辛宙峰葎?

wait(S){
 while (S<=0);
 S=S-1;
}
signal(S){
 S=S+1;
}

wait荷恬嶄?峪勣佚催楚S<=0?祥氏音僅仇霞編。咀緩?乎字崙旺隆恆儉“斑幡吉棋” 議彈夸?遇頁聞序殻侃噐“脱吉”議彜蓑。

芝村侏佚催楚

芝村侏佚催楚頁音贋壓“脱吉”孖嵆議序殻揖化字崙。茅阻俶勣匯倖喘噐旗燕彿坿方朕議屁侏延楚value翌?壅奐紗匯倖序殻全燕L?喘噐全俊侭嗤吉棋乎彿坿議序殻?芝村侏佚催楚頁喇噐??喘阻芝村侏議方象潤更誼兆。芝村侏佚催楚辛宙峰葎?

typedef struct{
 int value;
 struct process *L;
} semaphore;

屢哘議wait(S)才signal(S)議荷恬泌和?

void wait (semaphore S) { //屢輝噐賦萩彿坿
 S.value--;
 if(S.value<0) {
 add this process to S.L;
 block(S.L);
 }
}

wait荷恬?S.value--?燕幣序殻萩箔匯倖乎窃彿坿?輝S.value<0扮?燕幣乎窃彿坿厮蛍塘頼穎?咀緩序殻哘距喘block圻囂?序佩徭厘怦毘?慧虹侃尖字?旺峨秘欺乎窃彿坿議吉棋錦双S.L嶄?辛需乎字崙恆儉阻“斑幡吉棋”議彈夸。

void signal (semaphore S) { //屢輝噐瞥慧彿坿
 S.value++;
 if(S.value<=0){
 remove a process P from S.L;
 wakeup(P);
 }
}

signal荷恬?燕幣序殻瞥慧匯倖彿坿?聞狼由嶄辛工蛍塘議乎窃彿坿方奐1?絞S.value++。飛紗1朔挽頁S.value<=0?夸燕幣壓S.L嶄挽嗤吉棋乎彿坿議序殻瓜怦毘?絞珊哘距喘wakeup 圻囂?繍S.L嶄議及匯倖吉棋序殻蚕佰。

旋喘佚催楚糞孖揖化

佚催楚字更嬬喘噐盾畳序殻寂光嶽揖化諒籾。譜S葎糞孖序殻P1、P2揖化議巷慌佚催楚?兜峙葎0。序殻P2嶄議囂鞘y勣聞喘序殻P1嶄囂鞘x議塰佩潤惚?侭參峪嗤輝囂鞘x峇佩頼撹岻朔囂鞘y嘉辛參峇佩。凪糞孖序殻揖化議麻隈泌和?

semaphore S = 0; //兜兵晒佚催楚
P1 ( ) {
 // …
 x; //囂鞘x
 V(S); //御盆序殻P2,囂鞘?V厮将頼撹
}
P2()?{
 // …
 P(S) ; //殊臥囂鞘x頁倦塰佩頼撹
 y; // 殊臥涙列?塰佩y囂鞘
 // …
}

旋喘佚催楚糞孖序殻札鰍

佚催楚字更匆嬬載圭宴仇盾畳序殻札鰍諒籾。譜S葎糞孖序殻Pl、P2札鰍議佚催楚?喇噐耽肝峪塋俯匯倖序殻序秘匝順曝?侭參S議兜峙哘葎1?軸辛喘彿坿方葎1)。峪俶委匝順曝崔噐P(S)才V(S)岻寂?軸辛糞孖曾序殻斤匝順彿坿議札鰍恵諒。凪麻隈泌和?

semaphore S = 1; //兜晒佚催楚
P1 ( ) {
 // …
 P(S); // 彈姥蝕兵恵諒匝順彿坿?紗迄
 // 序殻P1議匝順曝
 V(S); // 恵諒潤崩?盾迄
 // …
}
P2() {
 // …
 P(S); //彈姥蝕兵恵諒匝順彿坿?紗迄
 // 序殻P2議匝順曝?
 V(S); // 恵諒潤崩?盾迄
 // …
}

札鰍議糞孖頁音揖序殻斤揖匯佚催楚序佩P、V荷恬?匯倖序殻壓撹孔仇斤佚催楚峇佩阻 P荷恬朔序秘匝順曝?旺壓曜竃匝順曝朔?喇乎序殻云附斤乎佚催楚峇佩V荷恬,燕幣輝念短嗤序殻序秘匝順曝?辛參斑凪麿序殻序秘。

旋喘佚催楚糞孖念駁購狼

佚催楚匆辛參喘栖宙峰殻會岻寂賜宀囂鞘岻寂議念駁購狼。夕2-8公竃阻匯倖念駁夕?凪嶄S1, S2, S3, …, S6頁恷酒汽議殻會粁?峪嗤匯訳囂鞘?。葎聞光殻會粁嬬屎鳩峇佩?哘譜崔飛孤倖兜兵峙葎“0”議佚催楚。箭泌?葎隠屬S1 -> S2、 S1 -> S3議念駁購狼?哘蛍艶譜崔佚催楚a1、a2。揖劔?葎阻隠屬 S2 -> S4、S2 ->S5、S3 -> S6、S4 -> S6、S5 -> S6,哘譜崔佚催楚bl、b2、c、d、e。

夕2-8 念駁夕訟箭

糞孖麻隈泌和?

semaphore al=a2=bl=b2=c=d=e=0; //兜兵晒佚催楚
S1() {
 // …
 V(al); V(a2) ; //S1厮将塰佩頼撹
}
S2() {
 P(a1); //殊臥S1頁倦塰佩頼撹
 // …
 V(bl); V(b2); // S2厮将塰佩頼撹
}
S3() {
 P(a2); //殊臥S1頁倦厮将塰佩頼撹
 // …
 V(c); //S3厮将塰佩頼撹
}
S4() {
 P(b1); //殊臥S2頁倦厮将塰佩頼撹
 // …
 V(d); //S4厮将塰佩頼撹
}
S5() {
 P(b2); //殊臥S2頁倦厮将塰佩頼撹
 // …
 V(e); // S5厮将塰佩頼撹
}
S6() {
 P(c); //殊臥S3頁倦厮将塰佩頼撹
 P(d); //殊臥S4頁倦厮将塰佩頼撹
 P(e); //殊臥S5頁倦厮将塰佩頼撹
 // …;
}

蛍裂序殻揖化才札鰍諒籾議圭隈化帶

1) 購狼蛍裂。孀竃諒籾嶄議序殻方?旺拝蛍裂万断岻寂議揖化才札鰍購狼。揖化、札鰍、念駁購狼岷俊梓孚貧中箭徨嶄議将灸袈塀個亟。

2) 屁尖房揃。孀竃盾畳諒籾議購囚泣?旺拝功象恂狛議籾朕孀竃盾畳議房揃。功象序殻議荷恬送殻鳩協P荷恬、V荷恬議寄崑乏會。

3) 譜崔佚催楚。功象貧中曾化?譜崔俶勣議佚催楚?鳩協兜峙?頼鋲屁尖。