{"id":710,"date":"2014-01-11T15:39:00","date_gmt":"2014-01-11T07:39:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=710"},"modified":"2023-11-04T15:44:50","modified_gmt":"2023-11-04T07:44:50","slug":"cpu-scheduling","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/710","title":{"rendered":"CPU Scheduling"},"content":{"rendered":"\n

CPU scheduling<\/strong>
\u76ee\u5730\uff1a\u6700\u5927\u5316cpu\u4f7f\u7528\u7387,\u4ee5\u63d0\u9ad8multi-program\u6548\u7387
\u4e3b\u8981\u7531short-term scheduler\u8ca0\u8cac
ps:
CPU-I\/O burst cycle
process\u88ab\u57f7\u884c\u6642\uff0c\u6703\u4f9dCPU burst\u548cI\/O burst\u7684\u5faa\u74b0\u5230\u57f7\u884c\u7d50\u675f<\/p>\n\n\n\n

dispatcher<\/strong>
\u5c07process\u4ea4\u7d66cpus\u8655\u7406
\u5de5\u4f5c\u62eccontext switching ,switching to user mode,\u7b49…
\u7576\u505c\u6b62\u4e00\u500bprocess\u800c\u958b\u59cb\u53e6\u4e00\u500bprocess\u6240\u9700\u7684\u6642\u9593\u7a31\u70badispatch latency<\/p>\n\n\n\n

context switching<\/strong>
\u52d5\u4f5c\uff1aOS\u4fdd\u5b58\u539fprocess\u7684\u57f7\u884c\u72c0\u614b\uff0c\u4e26\u8f09\u5165new process\u7684\u72c0\u614b
\u4f7f\u7528\u6642\u6a5f\uff1a\u7576cpu\u5f9e\u4e00\u500bprocess\u5207\u63db\u5230\u53e6\u4e00\u500bnew process\u4e4b\u524d
\u8a72\u52d5\u70ba\u7cfb\u7d71\u8ca0\u64d4,\u5b8c\u6210\u8a72\u52d5\u4f5c\u7684\u9577\u77ed\u53d6\u6c7a\u65bc\u786c\u9ad4\u6548\u80fd<\/p>\n\n\n\n


scheduling\u4f7f\u7528\u6642\u6a5f<\/strong>
process state\u6539\u8b8a\u6642,\u5982\u4e0b
\u3000running->waiting<\/strong>, \u5c6c\u65bcnonpreemptive
\u3000running->ready\u3000<\/strong>
\u3000waiting->ready<\/strong>
\u3000running->terminate<\/strong>, \u5c6c\u65bcnonpreemptive
ps:
nonpreemptive<\/strong>:\u4e0d\u53ef\u63d2\u968a,\u82e5process\u4e0d\u91cb\u653eCPU\u4f7f\u7528\u6b0a,\u7121\u6cd5\u88ab\u5f37\u8feb\u4e2d\u65b7
preemptive<\/strong>:\u53ef\u63d2\u968a,\u82e5process\u4e0d\u91cb\u653eCPU\u4f7f\u7528\u6b0a,\u53ef\u4ee5\u88ab\u5f37\u8feb\u4e2d\u65b7<\/p>\n\n\n\n

scheduling\u53ef\u5206\u5169\u985e<\/strong>
Preemptive scheduling<\/strong>
\u3000\u4e00\u822c\u800c\u8a00\uff0c\u6392\u73ed\u6548\u80fd\u8f03\u4f73(Avg. waiting time\u53caAvg. turnaround time\u8f03\u4f4e)
\u3000Context switching\u8f03\u591a
\u3000Response time\u6216turnaround time\u70ba\u4e0d\u53ef\u9810\u671f\u7684
Non-preemptive scheduling<\/strong>
\u3000Avg. waiting time\u53ef\u80fd\u8f03\u9577(\u53ef\u80fd\u6709Convoy effect)
\u3000Context switching\u8f03\u5c11
\u3000Response time\u6216turnaround time\u70ba\u53ef\u9810\u671f<\/p>\n\n\n\n

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

scheduling criteria<\/strong>
\u5e38\u898b\u7684\u6709
cpu utilization<\/strong>\uff1a\u76e1\u53ef\u80fd\u8b93CPU\u6301\u7e8c\u5de5\u4f5c
throughput<\/strong>\uff1a\u6bcf\u55ae\u4f4d\u6642\u9593\u5167\u6240\u5b8c\u6210\u7684process\u7684\u6578\u91cf
turnaround time<\/strong>\uff1a\u5f9e\u4e00\u500bprocess\u958b\u59cb\u5230\u5b8c\u6210\u7684\u6642\u9593
waiting time<\/strong>\uff1a\u6bcf\u4e00\u500bprocess\u5728queue\u7b49\u5f85\u7684\u6642\u9593\u7e3d\u5408
response time<\/strong>\uff1a\u5f9e\u4e00\u500brequest\u88ab\u63d0\u51fa\u5230\u958b\u59cb\u8981\u8655\u7406\u7684\u6642\u9593<\/p>\n\n\n\n

scheduling problem<\/strong>
\u5e38\u898b\u7684\u6709
convoy effect(\u8b77\u885b\u6548\u61c9):<\/strong>
\u3000\u8a31\u591aprocess\u7b49\u5f85\u4e00\u500b\u9700\u82b1\u5f88\u591a\u6642\u9593\u624d\u80fd\u7d50\u675f\u7684process,\u4f7favg waiting time\u964d\u4f4e
stravation(\u98e2\u9913),<\/strong>
\u3000low priority process\u53ef\u80fd\u6c38\u9060\u4e0d\u6703\u57f7\u884c\u5230
\u3000(\u53ef\u4f7f\u7528aging\u6a5f\u5236,\u7576\u7b49\u5f85\u6642\u8d8a\u9577,\u512a\u5148\u6b0a\u6703\u6f38\u6f38\u63d0\u6607)<\/p>\n\n\n\n

\u5e38\u898bscheduling<\/strong>
FCFS(first-come first-served)<\/strong>
\u3000process\u5e73\u5747\u7b49\u5f85\u6642\u9593\u8b8a\u52d5\u592a\u5927
\u3000\u6703\u6709convoy effect
SJF(shortest job first)<\/strong>
\u3000\u82e5\u80fd\u4e8b\u5148\u77e5\u9053\u6bcf\u500bjob\u7684\u6700\u5c0f\u6642\u9593,\u5247\u53ef\u4f7f\u7528\u8a72\u65b9\u6cd5,\u6b64\u70ba\u6700\u7406\u60f3\u4e4b\u65b9\u6cd5
\u3000(\u4f46\u5982\u4f55\u77e5\u9053?\u5e38\u898b\u7684\u6709\u7cfb\u7d71\u9810\u6e2c\u548c\u4f7f\u7528\u8005\u5b9a\u7fa9)
preemptive SJF\/shoartest remaining time first<\/strong>
\u3000\u7576\u6709new process\u9032\u4f86\u6642,\u5c31\u91cd\u65b0\u8a08\u7b97process\u9700\u8981\u7684\u6642\u9593
\u3000\u7136\u5f8c\u5148\u57f7\u884c\u6642\u9593\u9700\u6c42\u6700\u5c11\u7684process
priority scheduling<\/strong>
\u3000\u985e\u4f3cSJF
\u3000\u6703\u767c\u751fstravation
RR(round robin)<\/strong>
\u3000\u5047\u8a2d\u6307\u5b9a\u6642\u9593\u70baq,\u7576process\u7528\u5b8cq\u5f8c,\u6703\u63db\u5230\u4e0b\u4e00\u500bprocess\u8655\u7406
\u3000\u5c6c\u65bcpreemptive scheduling
\u3000process\u5207\u63db\u4e5f\u6703\u7528\u6389cpu\u6642\u9593,q\u8a2d\u592a\u5c0f\u6703\u6d6a\u8cbb\u5f88\u591a\u6642\u9593\u4e00\u76f4\u5728\u5207\u63dbprocess
\u3000process\u7684response time\u8f03\u5feb
\u3000process\u5e73\u5747\u7b49\u5f85\u6642\u9593\u7a69\u5b9a
multilevel queue scheduling<\/strong>
\u3000\u6839\u64da\u4e0d\u540c\u985e\u5225\u7684process\u7d66\u4e0d\u540c\u7684queue scheduling
\u3000ex:80% to foreground in RR,20% to background in FCFS
multilevel feedback queue<\/strong>
\u3000\u7576queue1 scheduling\u9084\u7121\u6cd5\u8655\u7406\u5b8c,\u5247\u79fb\u5230queue2 scheduling\u8655\u7406,\u4ee5\u6b64\u985e\u63a8
\u3000ex:Q0(RR with 4ms),q1(RR with 8ms),q2(FCFS)<\/p>\n\n\n\n

\u5047\u8a2d\u6709\u4e09\u500bprocess,\u6642\u9593\u5982\u4e0b
p1(arrival time:0, burst time:10)
p2(arrival time:2, burst time:5)
p3(arrival time:4, burst time:8)
FCFS<\/strong>
\u904b\u4f5c\u5982\u4e0b
[p1,0<\/strong>-10][p2,10<\/strong>-15][p3,15<\/strong>:23]
\u8a08\u7b97\u5982\u4e0b
p1 waitting time=0,
p2 waitting time=10-2=8,
p3 waitting time=15-4=11,
waitting time=0+8+11=19
avg waitting time=19\/3
RR(time slice=3)<\/strong>
\u904b\u4f5c\u5982\u4e0b
[p1,0<\/strong>-3(7)][p2,3<\/strong>-6(2)][p3,6<\/strong>-9(5)]
[p1,9<\/strong>-12(4)][p2,12<\/strong>-14(0)][p3,14<\/strong>-17(2)]
[p1,17<\/strong>-20(1)][p3,20<\/strong>-22(0)]
[p1,22<\/strong>-23(0)]
\u8a08\u7b97\u5982\u4e0b
p1 waitting time=0+(9-3)+(17-12)+(22-20)=13
p2 waitting time=(3+(12-6))-2=7
p3 waitting time=(6+(14-9)+(20-17))-4=10
waitting time=13+7+10=30
avg waitting time=10<\/p>\n\n\n\n


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

multiple-processor scheduling<\/strong>
\u53ef\u4ee5\u5206\u70ba
\u3000asymmetric multiprocessing<\/strong>
\u3000\u53ea\u6709\u4e00\u500bprocessor\u8ca0\u8cac\u5206\u914d
\u3000symmetric multiprocessing(SMP)<\/strong>
\u3000\u6bcf\u500bprocessor\u6709\u81ea\u5df1\u7684scheduling<\/p>\n\n\n\n

processor affinity<\/strong>
\u8b93process\u5118\u53ef\u80fd\u5728\u540c\u4e00\u500bprocessor\u4e0a\u8655\u7406
\u9019\u53ef\u907f\u514dcache invalidating\u548crepopulating
\u53ef\u5206\u70ba
\u3000soft affinity<\/strong>:\u53ef\u8b93process\u5728processor\u4e4b\u9593\u8f49\u79fb
\u3000hard affinity<\/strong>:\u53ef\u8b93process\u4e0d\u80fd\u5728processor\u4e4b\u9593\u8f49\u79fb
ps:
\u5728windows\u4e0b\u53ef\u7528affinity\u6307\u4ee4\u63a7\u5236process\u8981\u5728\u90a3\u500bprocessor\u4e0a\u8655\u7406<\/p>\n\n\n\n

multiprocessor load balancing<\/strong>
\u4e3b\u8981\u6709\u4ee5\u4e0b\u5169\u7a2e
push migration:\u91cd\u7684processor\u4e1f\u6389\u5de5\u4f5c
pull migration\u8f15\u7684processor\u53bb\u63a5\u5de5\u4f5c<\/p>\n\n\n\n

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

real-time system scheduling<\/strong>
ps
real-time system
\u3000soft real-time system:\u8b93\u6709\u5373\u6027\u7684process\u6709\u8f03\u9ad8\u512a\u5148\u6b0a
\u3000hard real-time system:\u5c0d\u5b8c\u6210\u6642\u9593\u6709\u56b4\u683c\u7684\u8981\u6c42
ps:
2\u7a2elatency\u6703\u5f71\u97ffreal-time\u6548\u80fd
\u3000interrupt latency
\u3000dispatch latency
ps:
\u4e00\u4e9bprocesses\u6709\u65b0\u7684\u53c3\u6578\u7528\u5728real-time system
\u3000period
\u3000processing time
\u3000deadline<\/p>\n\n\n\n

Rate Monotonic Scheduling<\/strong>
period(\u57f7\u884c\u9031\u671f)\u8d8a\u77ed\uff0c\u512a\u5148\u6b0a\u8d8a\u9ad8
Earliest Deadline First Scheduling<\/strong>
\u8d8a\u63a5\u8fd1process\u7684deadline\u57f7\u884c\u671f\u9650,\u512a\u5148\u6b0a\u8d8a\u9ad8<\/p>\n","protected":false},"excerpt":{"rendered":"

CPU scheduling\u76ee\u5730\uff1a\u6700\u5927\u5316cpu\u4f7f\u7528\u7387,\u4ee5\u63d0\u9ad8 …<\/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-710","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\/710","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=710"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/710\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=710"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=710"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=710"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}