{"id":708,"date":"2014-01-12T15:38:00","date_gmt":"2014-01-12T07:38:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=708"},"modified":"2023-11-04T15:44:16","modified_gmt":"2023-11-04T07:44:16","slug":"synchronization","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/708","title":{"rendered":"Synchronization"},"content":{"rendered":"\n

1.\u6982\u5ff5<\/strong><\/h2>\n\n\n\n

synchronization<\/strong>
processes\u540c\u6b65\u5e73\u884c\u8655\u7406
\u5bb9\u6613\u767c\u751frace condition<\/p>\n\n\n\n

race condition<\/strong>
\u591a\u500bprocesses\u540c\u4e00\u6642\u9593\u9ede\u5b58\u53d6shared resource,\u672a\u5354\u8abf\u597d\u800c\u5c0e\u81f4data inconsientency
ex:
\u5c07\u5c08\u5c6c\u7684\u8a2d\u5099\u7576\u6210\u5171\u7528\u8a2d\u5099\u4f7f\u7528\uff0c\u800c\u9020\u6210\u8a2d\u5099\u51fa\u73fe\u7570\u5e38<\/p>\n\n\n\n

…………………….<\/p>\n\n\n\n

critical-section<\/strong>
\u907f\u514drace condition\u7684\u4e00\u7a2e\u65b9\u6cd5
\u4e00\u6bb5code,code\u5167\u7684\u5171\u7528\u8cc7\u6e90\u7981\u6b62\u591a\u500bprocess\u5728\u88e1\u9762\u57f7\u884c
\u7d50\u69cb\u5982\u4e0b
do{
\/\/entry section \u9032\u5165critical section\u7684\u5165\u53e3\u5340
\u3000critical section<\/strong>
\/\/exit section
\u3000remainder section\u975ecritical section\u7684\u5176\u4ed6\u7a0b\u5f0f
}while(1);
<\/p>\n\n\n\n

critical-section\u4e09\u8981\u7d20<\/strong>
mutual exclusion(\u4e92\u65a5)<\/strong>: \u53ea\u5141\u8a311\u500bprocess\u5728critical-section\u88e1\u57f7\u884c
\u3000\u7576process\u5728critical-section\u5b58\u53d6resource\u6642\uff0c\u5176\u4ed6process\u7121\u6cd5\u9032\u5165critical-section\u5b58\u53d6\u76f8\u540c\u8cc7\u6e90
progress(\u9032\u884c)<\/strong>: \u9078\u64c7\u4e0b\u4e00\u500bprocess\u9032\u5165critical-section\u7684\u6642\u9593\u4e0d\u53ef\u88ab\u7121\u9650delay
\u30001.\u5176\u4ed6process(\u5728remainder section)\u4e0d\u80fd\u5e72\u9810\u5176\u4ed6process\u9032\u5165critical section\u7684\u6c7a\u7b56\u904e\u7a0b
\u30002.\u7576\u591a\u500bprocess\u8981\u9032\u5165\u6642\uff0c\u6c7a\u5b9a\u90a3\u4e00\u500bprocess\u53ef\u5148\u9032\u5165critical-section\u7684\u6642\u9593\u662f\u6709\u9650\u7684,(\u9632\u6b62deadlock)
bounded waiting(\u6709\u9650\u7b49\u5f85)<\/strong>:
\u3000\u7576process\u88ab\u7372\u51c6\u53ef\u9032\u5165critical-section\u5f8c,\u9032\u5165critical-section\u7684\u7b49\u5f85\u6642\u9593\u662f\u6709\u9650\u7684(\u9632\u6b62starvation)
\u3000ex:
\u3000\u82e5\u6709n\u500bprocesses\u60f3\u9032\u5165Critical Section\uff0c\u5247\u6bcf\u500bprocess\u6700\u591a\u53ea\u8981\u7b49\u5f85n-1\u7684\u6642\u9593\u5f8c\u5c31\u53ef\u9032\u5165<\/p>\n\n\n\n

……………………………………………….<\/p>\n\n\n\n

2.\u89e3\u6c7a\u65b9\u6848<\/strong><\/h2>\n\n\n\n

\u89e3\u6c7arace condition\u5e38\u898b\u7684\u65b9\u6cd5\u6709\u4ee5\u4e0b
\u3000\u786c\u9ad4\u548c\u8edf\u9ad4
\u3000semaphore
\u3000monitor
….<\/p>\n\n\n\n

\u786c\u9ad4<\/strong>
\u958b\u767c\u540c\u6b65\u7a0b\u5f0f\u8f03\u65b9\u4fbf
\u63d0\u6607\u7cfb\u7d71\u6548\u7387
\u5e38\u898b\u7684\u6709
\u3000disable interrupts
\u3000TestAndSet\u3000\u4e00\u7a2e\u6975\u5c0f\u7684\u786c\u9ad4\u6307\u4ee4
\u3000CompareAndSwap\u3000\u4e00\u7a2e\u6975\u5c0f\u7684\u786c\u9ad4\u6307\u4ee4<\/p>\n\n\n\n


disable interrupts<\/strong>
\u9069\u5408\u5728\u55aecpu\uff0c\u4f46\u8f03\u4e0d\u9069\u5408\u5728\u591acpu\u7cfb\u7d71<\/p>\n\n\n\n


TestAndSet<\/strong>
\u4fdd\u8b49mutual exclusion\u8207progress,\u4f46\u662f\u4e0d\u4fdd\u8b49\u7b26\u5408bounded waiting
\u7d50\u69cb\u5927\u81f4\u5982\u4e0b<\/strong>
boolean TestAndSet (Boolean *locked) {
\u3000boolen uv=locked;
\u3000*locked = true;
\u3000return uv;
}
\u61c9\u7528\u5728critical section\u5927\u81f4\u5982\u4e0b<\/strong>
do{ \/\/lock\u662fshared variable
\u3000while (TestAndSet(&lock)); \/\/\u5c07lock\u8b8a\u6578\u7684\u8a18\u61b6\u9ad4\u4f4d\u7f6e\u50b3\u5165TestAndSet
\/*critical section*\/
\u3000lock = false; \/\/critical section\u7d50\u675f\u5f8c,\u5247\u6703\u5c07lock\u89e3\u9664,
\/* remainder section *\/
}while(true)<\/p>\n\n\n\n


CompareAndSwap<\/strong>
\u7d50\u69cb\u5927\u81f4\u5982\u4e0b<\/strong>
int CompareAndSwap(int *v, int exptd, int new){
\u3000int tmp=*v
\u3000if(*v==exptd)*v=new;
\u3000return tmp;
}
\u61c9\u7528\u5728critical section\u5927\u81f4\u5982\u4e0b<\/strong>
do{ \/\/lock\u662fshared variable
\u3000while (CompareAndSwap(&lock,0,1));
\/*critical section*\/
\u3000lock = 0; \/\/critical section\u7d50\u675f\u5f8c,\u5247\u6703\u5c07lock\u89e3\u9664,
\/* remainder section *\/
}while(true)<\/p>\n\n\n\n

…<\/p>\n\n\n\n


\u8edf\u9ad4<\/strong>
\u7981\u6b62\u4e2d\u65b7\u6cd5:\u4f7f\u7528disable\u7cfb\u7d71\u547c\u53eb,\u50c5\u9069\u5408\u5728\u55aecpu\u74b0\u5883
Dekker’s algorithms
peterson’s algorithms
bakery algorithms:\u9069\u5408\u89e3\u6c7a\u591a\u500b\u884c\u7a0b\u540c\u6b65\u554f\u984c
mutex locks<\/p>\n\n\n\n


mutex locks<\/strong>
\u6700\u7c21\u55ae\u7684\u5176\u4e2d\u4e00\u7a2e\u65b9\u6cd5
\u7f3a\u9ede\u662f\u6703\u6709busy waiting
\u5927\u81f4\u5982\u4e0b
do{
acquire_lock()
\/* critical section *\/
release_lock()
\/* remainder section *\/
}while(1);<\/p>\n\n\n\n

busy waiting(\u5fd9\u788c\u7b49\u5f85)<\/strong>
\u7576process\u5728critical-section\u6642\uff0c\u5176\u4ed6\u60f3\u9032\u5165critical-section\u7684process\u6703\u5728entry section\u4e00\u76f4\u57f7\u884cloop\u4f86\u7b49\u5f85
ps:\u4e5f\u88ab\u7a31\u70baspinlock(\u65cb\u8f49\u9396),\u610f\u6307cpu\u6703\u4e0d\u65b7\u6e2c\u8a66\u8a72\u689d\u4ef6\u662f\u5426\u6210\u7acb,\u6703\u6d6a\u8cbbcpu cycle<\/p>\n\n\n\n

………………<\/p>\n\n\n\n

semaphore<\/strong>
\u5e38\u898b\u7684synchronization\u5de5\u5177,\u53ef\u89e3\u6c7a\u66f4\u8907\u96dc\u7684synchronization
\u662f\u4e00\u500bprotected variable
\u50c5\u63d0\u4f9bcritical section\u7684\u540c\u6b65\u6a5f\u5236\uff0c\u4e0d\u4fdd\u8b49\u6709mutual exclusion\u7279\u6027\uff0c\u4e0d\u4fdd\u8b49\u907f\u514ddeadlock
\u900f\u904ewait()\u548csingal()\u904b\u7b97\u4fee\u6539protected variable\uff0c\u4ee5\u9054\u5230process synchronization
ps:semaphore\u5e38\u4ee5S\u8868\u793a,wait()\u5e38\u4ee5P()\u8868\u793a,signal()\u5e38\u4ee5V()\u8868\u793a;<\/p>\n\n\n\n

semaphore\u5206\u70ba
counting semaphore(\u8a08\u6578\u865f\u8a8c)<\/strong>:\u53ef\u88fd\u4f5cno busy waiting\u7684mutex locks
binary semaphore(\u4e8c\u5143\u865f\u8a8c)<\/strong>: \u53ea\u67090\u548c1,\u5bb9\u6613\u5be6\u4f5c,\u5e38\u7528\u5728mutex locks<\/p>\n\n\n\n


no busy-waiting on counting semaphore<\/strong>
\u4e3b\u8981\u900f\u904eblock()\u548cwakeup()\u9019\u5169\u500batomic operate(\u6700\u5c0f\u904b\u7b97)
block():\u5c07process\u6539\u70bawait state,\u4e5f\u5c31\u662f\u5c07process\u79fb\u5230wait queue\u4e2d
wakeup():\u5c07\u8981\u88abwakeup\u7684process\u5f9ewait queue\u79fb\u5230ready queue
ps:\u4e5f\u88ab\u7a31\u70basuspend-lock<\/p>\n\n\n\n

no busy-waiting on counting semaphore\u7d50\u69cb<\/strong>
\u5927\u81f4\u5982\u4e0b
typedef struct{
\u3000int value;
\u3000struct process*list
}semaphore;
wait<\/strong>(semaphore *s){
\u3000s.value–;
\u3000if(s.value <0){
\u3000\u3000\/\/add this process to s.list;
\u3000\u3000block();\u3000\/\/\u5c07process\u653e\u5165waiting queue
\u3000}
}
signal<\/strong>(semaphore *s){
\u3000s.value++;
\u3000if(s.value <=0){
\u3000\u3000\/\/remove a process from s.list;
\u3000\u3000wakeup(P); \/\/\u5c07process\u5f9ewaiting queue\u79fb\u5230ready queue
\u3000}
}
\u61c9\u7528\u5728critical section\u7684\u7d50\u69cb\u5982\u4e0b
semahore mutex; \/\/\u521d\u59cb\u5316\u70ba1
do{
\u3000wait(mutex);
\/* critical section *\/
\u3000signal(mutex);
\/* remainder sectoin *\/
}while(TRUE);<\/p>\n\n\n\n

………………………………..<\/p>\n\n\n\n

monitor<\/strong>
\u4ee5\u7a0b\u5f0f\u8a9e\u8a00\u9054\u5230synchronization\u7684\u6a5f\u5236
\u4fdd\u8b49\u4efb\u4f55process\u5b58\u53d6\u8cc7\u6599\u662fmutex
\u4ee5blocking\u548cwakeup\u6a5f\u5236\u8655\u7406process\u9032\u5165critical section<\/p>\n\n\n\n

………..<\/p>\n\n\n\n

3.synchronization\u7684\u5178\u578b\u8b70\u984c<\/strong><\/h2>\n\n\n\n

bounded-buffer problem(\u6709\u9650\u7de9\u885d\u5340\u554f\u984c)
readers and writers problem(\u8b80\u53d6\u5beb\u5165\u554f\u984c)
dining-philosophers problem(\u54f2\u5b78\u5bb6\u9032\u9910\u554f\u984c)<\/p>\n\n\n\n

bounded-buffer problem<\/strong>
\u6709n\u500bbuffer,\u6bcf\u500bbuffer\u53ef\u4fdd\u5b58\u4e00\u500b\u9805\u76ee,\u4ee5\u53ca\u591a\u500bproducer\u548cconsumer
\u7a0b\u5f0f\u78bc\u5927\u81f4\u5982\u4e0b
initialized: mutex=1,full=0,empty=n
producer process<\/strong>
do{
\/\/produce an item in nextp
wait(empty);
wait(mutex);
\/\/add the item to the buffer
signal(mutex);
signal(full);
}
consumer process<\/strong>
do{
wait(full);
wait(mutex);
\/\/remove an item from the buffer to nextc
signal(mutex);
signal(empty);
\/\/consume the item in nextp
}<\/p>\n\n\n\n

readers and writers problem<\/strong>
\u4e00\u500bshared data\u80fd\u88ab\u540c\u6642\u5b58\u53d6
\u76ee\u6a19:\u5141\u8a31\u591a\u500breader\u5728\u76f8\u540c\u6642\u9593\u8b80\u53d6,\u4f46\u50c5\u80fd\u4e00\u500bwriter\u5728\u76f8\u540c\u6642\u9593\u5b58\u53d6
\u7a0b\u5f0f\u78bc\u5927\u81f4\u5982\u4e0b
initialized: mutex=1,wrt=1,readcount=0
writer process<\/strong>
do{
wait(wrt);
\/\/writing is performed
signal(wrt);
}
reader process<\/strong>
do{
\u3000wait(mutex);
\u3000readcount++;
\u3000if(readcount==1)wait(wrt);
\u3000singal(mutex);
\u3000\/\/reading is performed
\u3000wait(mutex);
\u3000readcount–;\u3000
\u3000if(readcount==0)signal(wrt);
\u3000signal(mutex);
}while(TRUE);<\/p>\n","protected":false},"excerpt":{"rendered":"

1.\u6982\u5ff5 synchronizationprocesses\u540c …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[22],"tags":[],"class_list":["post-708","post","type-post","status-publish","format-standard","hentry","category-operationsystem"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/708","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=708"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/708\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=708"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=708"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=708"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}