{"id":706,"date":"2015-02-06T15:37:00","date_gmt":"2015-02-06T07:37:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=706"},"modified":"2023-11-04T15:44:06","modified_gmt":"2023-11-04T07:44:06","slug":"deadlock","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/706","title":{"rendered":"Deadlock"},"content":{"rendered":"\n

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

deadlock<\/strong>
1.a set of blocked process each holding a resource and
2. waiting to acquire a resource held by another process in the set<\/p>\n\n\n\n

deadlock characterization<\/strong>
\u767c\u751fdeadlock\u6642\u4ee5\u4e0b\u56db\u500b\u7279\u6027\u6703\u540c\u6642\u51fa\u73fe
mutual exclusion(\u4e92\u65a5)<\/strong>: \u8cc7\u6e90\u5728\u540c\u4e00\u6642\u9593\u53ea\u5141\u8a31\u4e00\u500bprocess\u4f7f\u7528
no preemption<\/strong>: \u5176\u4ed6process\u7121\u6cd5\u5f37\u5236\u53d6\u5f97\u8cc7\u6e90
hold and wait<\/strong>: p1\u8981\u4f7f\u7528\u4e00\u4e9b\u8cc7\u6e90,\u4f46\u90e8\u4efd\u8cc7\u6e90\u8981\u7b49\u5230\u5176\u4ed6process\u7528\u5b8c,\u9020\u6210p1\u66ab\u6642\u7121\u6cd5\u57f7\u884c
circular wait(\u5faa\u74b0\u7b49\u5f85):<\/strong> p1\u7b49\u5f85p2\u8cc7\u6e90,p2\u7b49\u5f85p3\u8cc7\u6e90,p3\u7b49\u5f85p1\u8cc7\u6e90<\/p>\n\n\n\n

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

resource-allocation graph<\/strong>
\u7528\u4f86\u6aa2\u67e5\u662f\u5426\u6709deadlock\u7684\u65b9\u6cd5
\u82e5\u5f62\u6210cycle,\u6703\u6709deadlock\u7684\u98a8\u96aa
\u82e5\u5f62\u6210cycle,\u4e26\u7b26\u5408deadlock4\u7279\u6027\u7684\u5176\u4e2d\u4e00\u7a2e,\u6703\u767c\u751fdeadlock
\u5e38\u7528\u65bcdeadlock avoidance algorithm<\/p>\n\n\n\n

resource-allocation graph\u5b9a\u7fa9<\/strong>
\u5716\u5f62\u7531\u4ee5\u4e0b\u96c6\u5408\u69cb\u6210
\u3000vertices V
\u3000edges E
V\u6709\u4ee5\u4e0b\u5169\u985e\u578b
\u3000P={P1,P2,…Pn} \u8868\u793aprocess
\u3000R={R1,R2,…Rn} \u8868\u793aresource
\u52d5\u4f5c
\u3000process\u8981\u6c42resource\u6642,Pi->Rj
\u3000process\u6b63\u4f7f\u7528resource\u6642, Pi<-Rj<\/p>\n\n\n\n

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

wait-for graph<\/strong>
\u985e\u4f3cresource-allocation graph
\u4f46vertices V\u4e2d\u53ea\u6709process
\u5e38\u7528\u65bcdeadlock detection algorithm<\/p>\n\n\n\n

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

2.handling deadlock \u7b56\u7565<\/strong><\/h2>\n\n\n\n

\u4e3b\u8981\u6709\u4ee5\u4e0b\u5927\u4e09\u7a2e
1\u7121\u6cd5\u9032\u5165deadlock\u72c0\u614b
\u3000deadlock prevention
\u3000deadlock avoidance
2\u5141\u8a31deadlock\u767c\u751f,\u4f46\u6703\u4e8b\u5f8c\u88dc\u6551\u7684\u505a\u6cd5
\u3000deadlock detection and recovery
3\u5ffd\u7565\u3000
\u3000\u5927\u90e8\u4efd\u4f5c\u696d\u7cfb\u7d71\u63a1\u8a72\u65b9\u6cd5<\/p>\n\n\n\n

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

deadlock prevention<\/strong>
\u53ef\u907f\u514ddeadlock\uff0c\u4f46resource utilization\u6703\u964d\u4f4e
\u4e3b\u8981\u65b9\u6cd5\u70ba\u907f\u514ddeadlock\u5404\u7279\u6027\u7684\u5176\u4e2d\u4e00\u7a2e\u6210\u7acb
\u5982\u4e0b
mutual exclusion prevention<\/strong>
\u3000\u6709\u4e9b\u8cc7\u6e90\u7121\u6cd5\u9069\u7528\u8a72\u65b9\u6cd5
\u3000\u8a72\u65b9\u6cd5\u5f88\u56f0\u96e3
hold and wait prevention<\/strong>
\u3000not wait: process\u8981\u6709\u80fd\u529b\u4e00\u6b21\u53d6\u5f97\u6240\u9700\u8981\u7684\u6240\u6709\u8cc7\u6e90\uff0c\u624d\u53ef\u7533\u8acb\u8cc7\u6e90
\u3000not hold: process\u8981\u91cb\u653e\u6389\u6240\u8cc7\u8cc7\u6e90\u5f8c\uff0c\u624d\u53ef\u7533\u8acb\u8cc7\u6e90
no preemption prevention<\/strong>
\u3000\u6539\u70bapreemption\u8b93process\u53efpreemption
\u3000ps:preemtpion\u53ef\u80fd\u5f15\u767cstarvation\u554f\u984c
\u3000\u53ef\u61c9\u7528\u5728cpu register\u6216memory space\u7b49\u8cc7\u6e90
\u3000\u8f03\u96e3\u61c9\u7528\u5728printer\u6216\u78c1\u5e36\u6a5f\u7b49\u8cc7\u6e90
circular wait prevention<\/strong>
\u3000\u7d66\u5404resource\u552f\u4e00\u7684ID\uff0cprocess\u53ea\u80fd\u4ee5\u905e\u589e\u7684\u65b9\u5f0f\u7533\u8acbresource
\u3000ex:p\u5df2\u6709resource3\uff0c\u90a3p\u4e0d\u80fd\u7533\u8acbresource1,2\uff0c\u53ea\u80fd\u7533\u8acb4\u4e4b\u5f8c\u7684resource<\/p>\n\n\n\n

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


deadlock avoidance<\/strong>
\u900f\u904ealgorithms\u52d5\u614b\u7684\u6aa2\u67e5state\uff0c\u4ee5\u78ba\u4fdd\u4e0d\u767c\u751fdeadlock
state\u5305\u62ec
\u3000safe state:\u4e0d\u6703\u767c\u751fdeadlocks\u7684\u60c5\u6cc1
\u3000unsafe state:\u53ef\u80fd\u767c\u751fdeadlock\u548c\u6703\u767c\u751fdeadlock\u5169\u7a2e\u7684\u60c5\u6cc1<\/p>\n\n\n\n

\u4f9dresource type\u6709\u4ee5\u4e0b\u5169\u7a2eavoidance algorithms
single instance<\/strong>
\u3000resource-allocation graph algorithm
multiple instances<\/strong>
\u3000banker’s algorithm\u3000<\/p>\n\n\n\n


banker’s algorithm<\/strong>
\u9700\u8981O(m*n^2)\uff0c\u8f03\u8017\u6642
\u8cc7\u6599\u7d50\u69cb
\u3000available[r]\uff1a\u5404resource\u9084\u6709\u591a\u5c11\u53ef\u7528
\u3000max[p,r]\uff1a\u5404process\u5404\u9700\u8981\u5e7e\u500bresource
\u3000allocation[p,r]\uff1a\u5404process\u5404\u81ea\u64c1\u6709\u7684resource\uff0c\u6703\u96a8\u6642\u9593\u8b8a\u5316\u800c\u8b8a\u52d5
\u3000need[p,r]\uff1a\u76ee\u524d\u5404process\u9084\u5404\u9700\u8981\u5e7e\u500bresource\uff0c\u6703\u96a8\u6642\u9593\u8b8a\u5316\u800c\u8b8a\u52d5
\u4e3b\u8981\u6d41\u7a0b
\u30001. resource-request algorithm \u6c7a\u5b9a\u8cc7\u6e90\u7684\u5206\u914d
\u30002. safe algorithm \u5224\u65b7\u662f\u5426\u4ecd\u5728\u5b89\u5168\u72c0\u614b
ex:
\u6240\u6709\u8cc7\u6e90\u70ba10,5,7\uff0c\u800c\u5404process\u9700\u6c42\u5982\u4e0b
p: allocation\/max = need
p0: 0,1,0\/7,5,3 = 7,4,3
p1: 2,0,0\/3,2,2 = 1,2,2
p2: 3,0,2\/9,0,2 = 6,0,0
p3: 2,1,1\/2,2,2 = 0,1,1
p4: 0,0,2\/4,3,3 = 4,3,1
\u8a08\u7b97\u65b9\u5f0f\u5982\u4e0b
available: 3,3,2\u3000=10-(0+2+3+2+0),5-(1+0+0+1+0),7-(0+0+2+1+2)
step1
1) available3,3,2 > p1\u76841,2,2 \u6240\u4ee5\u914d\u7d66p1
2) p1\u5b8c\u6210\u5f8c\u6b78\u9084\u8cc7\u6e902,0,0
3) available: 5,3,2 =10-(0+0+3+2+0),5-(1+0+0+1+0),7-(0+0+2+1+2)
step2
1) available5,3,2 > p3\u76840,1,1 \u6240\u4ee5\u914d\u7d66p3
2) p3\u5b8c\u6210\u5f8c\u6b78\u9084\u8cc7\u6e902,1,1
3) available: 7,4,3 =10-(0+0+3+0+0),5-(1+0+0+0+0),7-(0+0+2+0+2)
step3
1) available7,4,3 > p4\u76844,3,1 \u6240\u4ee5\u914d\u7d66p4
2) p4\u5b8c\u6210\u5f8c\u6b78\u9084\u8cc7\u6e900,0,2
3) available: 7,4,5 =10-(0+0+3+0+0),5-(1+0+0+0+0),7-(0+0+2+0+0)
step4
1) available7,4,5 > p0\u76847,4,3 \u6240\u4ee5\u914d\u7d66p0
2) p0\u5b8c\u6210\u5f8c\u6b78\u9084\u8cc7\u6e900,1,0
3) available: 7,5,5 =10-(0+0+3+0+0),5-(0+0+0+0+0),7-(0+0+2+0+0)
step5
1) available7,5,5 > p2\u76846,0,0 \u6240\u4ee5\u914d\u7d66p2
2) p0\u5b8c\u6210\u5f8c\u6b78\u9084\u8cc7\u6e903,0,2
3) available: 10,5,7 =10-(0+0+0+0+0),5-(0+0+0+0+0),7-(0+0+0+0+0)
\u6700\u5f8c\u6839\u64dasafe algorithm\u6aa2\u67e5
\u914d\u7f6e\u9806\u5e8f\u82e5\u70bap1,p3,p4,p0,p2\u5c6c\u65bcsafe state<\/p>\n\n\n\n


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


deadlock detection and recovery<\/strong>
\u8cc7\u6e90utilzation\u8f03\u9ad8,throughput\u53ef\u63d0\u6607<\/p>\n\n\n\n

\u5075\u6e2c\u6642\u6a5f<\/strong>
\u7576process\u7121\u6cd5\u7acb\u523b\u8981\u5230\u8cc7\u6e90
\u5b9a\u671f\u5075\u6e2c:ex:\u6bcf\u5c0f\u6642\u5075\u6e2c\u4e00\u6b21
cpu\u4f7f\u7528\u7387\u4f4e\u7684\u6642\u5019 ex:cpu\u4f7f\u7528\u7387\u4f4e\u65bc20\uff05\u6642<\/p>\n\n\n\n

\u4f9dresource type\u6709\u4ee5\u4e0b\u5169\u7a2e\u65b9\u6cd5
single instance<\/strong>
\u3000\u9031\u671f\u6027\u7684\u641c\u5c0b\u662f\u5426\u5728wait-for graph\u6709cycle
\u3000\u6f14\u7b97\u6cd5\u8907\u96dc\u5ea6\u70ban^2
several instance<\/strong>
\u3000\u4f7f\u7528detection algorithmI(\u985e\u4f3cbank’s algorithm)<\/p>\n\n\n\n

detection algorithm<\/strong>
data structure
\u3000available[r]
\u3000allocation[p,r]
\u3000request[p,r]
ex:
\u6240\u6709\u8cc7\u6e90\u70ba7,2,6\uff0c\u800c\u5404process\u9700\u6c42\u5982\u4e0b
p: allocation\/request
p0: 0,1,0 \/ 0,0,0
p1: 2,0,0 \/ 2,0,2
p2: 3,0,3 \/ 0,0,0
p3: 2,1,1 \/ 1,0,0
p4: 0,0,2 \/ 0,0,2
\u5075\u6e2cp0,p2,p3,p1,p4\u9806\u5e8f\u662f\u5426\u6b63\u5e38
\u8a08\u7b97\u5982\u4e0b
p0,request=0,
\u3000\u91cb\u653ep0\u8cc7\u6e90, work(0,1,0)=work(0,0,0)+allocation(0,1,0),finsh[0]=1
p2,request=0,
\u3000\u91cb\u653ep2\u8cc7\u6e90\ufe51 work(3,1,3)=work(0,1,0)+allocation(3,0,3),finsh[2]=1
p3,request!=0,\u4e14request(1,0,0)\u3000\u91cb\u653ep3\u8cc7\u6e90,work(5,2,4)=work(3,1,3)+allocation(2,1,1),finsh[3]=1
p1,request!=0,\u4e14request(2,0,0)\u3000\u91cb\u653ep1\u8cc7\u6e90,work(7,2,4)=work(5,2,4)+allocation(2,0,0),finsh[1]=1
p4,request!=0,\u4e14request(0,0,2)\u3000\u91cb\u653ep4\u8cc7\u6e90,work(7,2,6)=work(7,2,6)+allocation(0,0,2),finsh[4]=1
finish[0]~finish[4]\u90fd\u70ba1\uff0c\u8a72\u5e8f\u5217\u7121deadlock<\/p>\n\n\n\n


recovery from deadlock<\/strong>
\u82e5detection algorithm\u5075\u6e2c\u5230deadlock\u5247\u89e3\u6c7a
\u4e3b\u8981\u6709\u4ee5\u4e0b\u5169\u65b9\u6cd5
process termination<\/strong>
\u3000\u4e2d\u65b7\u6240\u6709deadlock process
\u3000\u4e2d\u65b7\u6240\u6709process\u76f4\u5230deadlock\u88ab\u6392\u9664
resource preemption<\/strong>
\u3000rollback\u56de\u5230safe state<\/p>\n","protected":false},"excerpt":{"rendered":"

1.\u6982\u5ff5 deadlock1.a set of blocke …<\/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-706","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\/706","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=706"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/706\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=706"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=706"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=706"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}