{"id":738,"date":"2009-10-27T16:24:00","date_gmt":"2009-10-27T08:24:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=738"},"modified":"2023-11-04T16:30:43","modified_gmt":"2023-11-04T08:30:43","slug":"%e8%a8%98%e6%86%b6%e9%ab%94%e7%b3%bb%e7%b5%b1-%e8%99%9b%e6%93%ac%e8%a8%98%e6%86%b6%e9%ab%94","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/738","title":{"rendered":"\u8a18\u61b6\u9ad4\u7cfb\u7d71-\u865b\u64ec\u8a18\u61b6\u9ad4"},"content":{"rendered":"\n

virtual memory(\u865b\u64ec\u8a18\u61b6\u9ad4)<\/strong>
\u7528\u9014:\u5c07\u8f14\u52a9\u8a18\u61b6\u9ad4\u7576\u6210\u865b\u64ec\u7684\u4e3b\u8a18\u61b6\u9ad4\u55ae\u5143
\u505a\u6cd5:\u7a0b\u5f0f\u8207\u8cc7\u6599\u5148\u5b58\u653e\u5728\u8f14\u52a9\u8a18\u61b6\u9ad4\u4e2d,\u7a0b\u5f0f\u57f7\u884c\u6642\u518d\u7531\u4f5c\u696d\u7cfb\u7d71\u81ea\u52d5\u8655\u7406\u4e3b\u8a18\u61b6\u9ad4\u55ae\u5143\u8207\u8f14\u52a9\u8a18\u61b6\u9ad4\u9593\u7a0b\u5f0f\u8207\u8cc7\u6599\u7684\u79fb\u52d5
\u597d\u8655:
\u7a0b\u5f0f\u8207\u8cc7\u6599\u7684\u5927\u5c0f\u53ef\u4e0d\u53d7\u5230\u4e3b\u8a18\u61b6\u9ad4\u55ae\u5143\u5b9a\u5740\u7a7a\u9593\u7684\u9650\u5236,\u89e3\u6c7a\u4e3b\u8a18\u61b6\u9ad4\u55ae\u5143\u5bb9\u91cf\u7a7a\u9593\u4e0d\u5920\u5927\u7684\u554f\u984c
\u53ef\u64b0\u5beb\u5177\u6709\u8f03\u5927\u908f\u8f2f\u5b9a\u5740\u7a7a\u9593\u7684\u7a0b\u5f0f,\u540c\u6642\u53ef\u8b93\u7a0b\u5f0f\u5728\u8f03\u5c0f\u7684\u5be6\u969b\u5b9a\u5740\u7a7a\u9593\u7684\u4e3b\u8a18\u61b6\u9ad4\u55ae\u5143\u4e2d\u52a0\u4ee5\u57f7\u884c<\/p>\n\n\n\n

\u865b\u64ec\u8a18\u61b6\u9ad4\u7684\u52d5\u614b\u4f4d\u5740\u8f49\u63db<\/strong>
\u63a1\u7528\u8edf\u9ad4\u5be6\u4f5c\u7684\u6280\u8853,\u900f\u904eblock mapping table(\u5340\u584a\u5c0d\u7167\u8868)\u628avirtual address\u5c0d\u6620\u5230real address,\u4e26\u6c7a\u5b9ahit\u6216miss
ps:virtual address(\u865b\u64ec\u4f4d\u7f6e)\u662f\u865b\u64ec\u8a18\u61b6\u9ad4\u7684\u4f4d\u7f6e
ps:real\/physical address(\u5be6\u969b\u4f4d\u7f6e)\u662f\u4e3b\u8a18\u61b6\u9ad4\u55ae\u7684\u4f4d\u7f6e
virtual address\u548creal address\u7684\u76f8\u5c0d\u4f4d\u7f6e\u5b8c\u5168\u76f8\u540c,\u800c\u76f8\u5c0d\u4f4d\u7f6e\u7684\u6b04\u4f4d\u662f\u4f9d\u64da\u9801\u6216\u6bb5\u7684\u5927\u5c0f
ex:
\u9801\u7684\u5927\u5c0f\u662f1kb,\u5247\u76f8\u5c0d\u4f4d\u7f6e\u7684\u6b04\u4f4d\u70ba10bit<\/p>\n\n\n\n

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

virtual memory\u5be6\u4f5c\u65b9\u5f0f<\/strong>
\u4f9d\u5340\u584a\u985e\u5225\u5206:
 paging(\u5206\u9801)
 segmentation(\u5206\u6bb5)
 paging\/segmentation(\u5206\u9801\/\u5206\u6bb5)

paging:<\/strong>
\u4e3b\u8a18\u61b6\u9ad4\u8207\u8f14\u52a9\u8a18\u61b6\u9ad4\u9593\u4ee5page\u70ba\u5c0d\u6620\u55ae\u4f4d
ps:\u4e3b\u8a18\u61b6\u9ad4\u55ae\u5143\u8207\u7a0b\u5f0f\u90fd\u5207\u5272\u6210\u5927\u5c0f\u76f8\u540c\u7684\u5340\u584a,\u8f14\u52a9\u8a18\u61b6\u9ad4\u7684\u5340\u584a\u7a31\u70bapage(\u9801),\u4e3b\u8a18\u61b6\u9ad4\u7684\u5340\u584a\u7a31\u70bapage frame(\u9801\u6846)
\u900f\u904epage mapping table(\u9801\u5c0d\u7167\u8868)\u628avirtual address\u5c0d\u6620\u5230real address
page mapping table\u683c\u5f0f:[ \u9032\u99d0\u4f4d\u5143 | \u8f14\u52a9\u8a18\u61b6\u9ad4\u4f4d\u7f6e | \u4e3b\u8a18\u61b6\u7684\u9801\u7de8\u865f ]
virtual address\u683c\u5f0f:[ \u9801\u7684\u7de8\u865f | \u76f8\u5c0d\u4f4d\u7f6e ]
\u512a\u9ede:block\u7684\u5c0d\u61c9,\u53d6\u4ee3,\u6349\u53d6…\u7b49\u8a18\u61b6\u9ad4\u7ba1\u7406\u55ae\u5143\u904b\u4f5c\u8b8a\u7c21\u6613,\u9069\u5408\u786c\u9ad4\u7684\u88fd\u4f5c
\u7f3a\u9ede:\u5728protection(\u8edf\u9ad4\u7684\u4fdd\u8b77)\u8207sharing(\u8cc7\u6599\u7684\u5171\u7528)\u8b8a\u5f97\u5341\u5206\u56f0\u96e3
\u6703\u7522\u751finternal fragmentation
ex:
\u8a2dvirtual address\u662f23a01180,page\u5927\u5c0f\u662f1k
\u5247\u76f8\u5c0d\u4f4d\u7f6e\u6b04\u4f4d=10bit,\u800c23a01180\u8f492\u9032\u4f4d\u5f97\u5230[ 0010,0011,1010,0000,0001,00 | 01,1000,0000 ]=[ 08e804 | 180 ]
\u56e0\u6b64\u9801\u7684\u7de8\u865f\u662f08e804,\u76f8\u5c0d\u4f4d\u7f6e\u662f180
ex:32 pages of 2k bytes each \u8868\u793a\u9801\u7684\u7de8\u865f\u6b04\u4f4d\u70ba5bit(\u56e0\u70ba2^5=32),\u76f8\u5c0d\u4f4d\u7f6e\u6b04\u4f4d\u70ba11bit(\u56e0\u70ba2^11=2k)

segmentation:<\/strong>
\u4e3b\u8a18\u61b6\u9ad4\u8207\u8f14\u52a9\u8a18\u61b6\u9ad4\u9593\u4ee5segment\u70ba\u5c0d\u6620\u55ae\u4f4d
ps:\u7a0b\u5f0f\u5207\u5272\u6210\u5927\u5c0f\u53ef\u80fd\u4e0d\u540c\u7684\u5340\u584a,\u6b64\u5340\u584a\u70basegment
\u900f\u904esegment mapping table(\u6bb5\u5c0d\u7167\u8868)\u628avirtual address\u5c0d\u6620\u5230real address
\u683c\u5f0f:[ \u6bb5\u7684\u7de8\u865f | \u76f8\u5c0d\u4f4d\u7f6e ]
\u512a\u9ede:\u628aprotection\u8207sharing\u8b8a\u5f97\u5bb9\u6613
\u7f3a\u9ede:\u8a18\u61b6\u9ad4\u7ba1\u7406\u55ae\u5143\u904b\u4f5c\u8b8a\u56f0\u96e3,\u9069\u5408\u8edf\u9ad4\u7684\u88fd\u4f5c
\u6703\u7522\u751fexternal fragmentation

paging\/segmentation:<\/strong>
\u7a0b\u5f0f\u5207\u5272\u6210segment,\u6bcf\u500bsegment\u5728\u5207\u5272\u6210page
\u4e3b\u8a18\u61b6\u9ad4\u8207\u8f14\u52a9\u8a18\u61b6\u9ad4\u9593\u4ee5page\u70ba\u5c0d\u6620\u55ae\u4f4d
\u900f\u904esegment mapping table\u548cpage mapping table\u628avirtual address\u5c0d\u6620\u5230real address 
\u683c\u5f0f:[ \u6bb5\u7684\u7de8\u865f | \u9801\u7684\u7de8\u865f | \u76f8\u5c0d\u4f4d\u7f6e ]
\u512a\u9ede:\u6709paging\u548csegmentation\u7684\u597d\u8655
\u7f3a\u9ede:\u5be6\u4f5c\u6210\u672c\u9ad8,\u5b58\u53d6\u6548\u80fd\u5dee
\u6703\u7522\u751finternal fragmentation<\/p>\n\n\n\n

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

fragmenation
internal fragmenation(\u5167\u90e8\u788e\u7247):<\/strong>
\u5728\u7a0b\u5f0f\u7684\u6700\u5f8c\u4e00\u500b\u9801\u7684\u8cc7\u6599\u53ef\u80fd\u7121\u6cd5\u4f54\u6eff\u4e00\u500b\u9801\u6846,\u5728\u4e00\u500b\u9801\u6846\u5167\u90e8\u6240\u6d6a\u8cbb\u7684\u7a7a\u9593
external fragmenation(\u5916\u90e8\u788e\u7247):<\/strong>
\u4e3b\u8a18\u61b6\u9ad4\u55ae\u5143\u5728\u57f7\u884c\u904e\u7a0b\u6703\u9032\u884c\u914d\u7f6e\u8207\u56de\u6536\u7a7a\u9593,\u6703\u5f62\u6210\u4e00\u4e9b\u5f88\u5c0f\u7684\u7a7a\u9593\u7121\u6cd5\u653e\u7f6e\u4efb\u4f55\u4e00\u500b\u6bb5,\u5373\u70ba\u6b64\u7a7a\u9593<\/p>\n\n\n\n

\u865b\u64ec\u8a18\u61b6\u9ad4\u7684\u52d5\u614b\u4f4d\u5740\u8f49\u63db\u65b9\u5f0f<\/strong>
\u5e38\u898b\u6709\u4e09\u7a2e\u505a\u6cd5:
direct mapping(\u76f4\u63a5\u5c0d\u6620):<\/strong>\u6548\u80fd\u592a\u5dee
\u3000\u628ablock mapping table\u653e\u5728\u4e3b\u8a18\u61b6\u9ad4\u4e2d
associative mapping(\u95dc\u806f\u5c0d\u6620):<\/strong>\u6210\u672c\u592a\u9ad8
\u3000\u628ablock mapping table\u653e\u5728\u95dc\u806f\u8a18\u61b6\u9ad4\u4e2d
combine associative\/direct mapping(\u7d44\u5408\u5c0d\u6620)<\/strong>
\u3000\u4f7f\u7528\u8f03\u5c0f\u7684\u95dc\u806f\u8a18\u61b6\u9ad4\u5b58\u653e\u4e00\u5c0f\u90e8\u4efd\u7684block mapping table
ps:\u6b64\u95dc\u806f\u8a18\u61b6\u9ad4\u7a31\u70baTLB(translation lookaside buffer,\u8f49\u63db\u7de9\u885d\u5340)<\/p>\n\n\n\n

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

\u53d6\u4ee3\u6f14\u7b97\u6cd5\u7684\u5be6\u4f5c<\/strong>
\u865b\u64ec\u8a18\u61b6\u9ad4\u7684\u5931\u8aa4\u9700\u4ed8\u51fa\u6975\u5927\u7684\u5931\u8aa4\u4ee3\u50f9,\u56e0\u6b64\u53d6\u4ee3\u7b56\u7565\u8f03\u91cd\u8981
\u6f14\u7b97\u6cd5\u4e3b\u8981\u7684\u8003\u91cf\u9700\u8981\u76e1\u91cf\u964d\u4f4e\u5931\u8aa4\u7387
\u5e38\u7528\u6f14\u7b97\u6cd5\u6709:
LRU(least recently used,\u6700\u8fd1\u7f55\u7528)
FIFO(first in first out,\u5148\u9032\u5148\u51fa)
NRU(not recently used,\u6700\u8fd1\u4e0d\u7528)LRU
<\/strong> \u8a2d\u67090\u52302^n-1\u500bblock,\u8d8a\u5927\u7684block\u8868\u793a\u5b58\u53d6\u6642\u9593\u8d8a\u4e45,\u9700\u8981\u53d6\u4ee3\u6642\u5247\u9078\u6700\u4e45\u7684block
 \u53ef\u914d\u5408\u5b58\u53d6\u5c40\u90e8\u6027,\u8b93\u5931\u8aa4\u7387\u6e1b\u4f4e
 hit\u6642,\u9700\u5c07\u5c0f\u65bc\u8a72block\u503c+1,\u4ee5\u53ca\u8a72block\u672c\u8eab\u8a2d\u70ba0
 miss\u6642,\u65b0\u9032\u5165\u7684block\u8a2d\u70ba0,\u5176\u4ed6\u6240\u6709block\u90fd+1
 \u4e0d\u6613\u88fd\u4f5c\u4e14\u6210\u672c\u9ad8
ex:
\u8a2d\u67094\u500b,\u9032\u5165\u9806\u5e8f\u70ba32464721,\u52474,2\u88abhit,hit ratios\u70ba2\/8<\/p>\n\n\n\n

<\/td>3<\/td>2<\/td>4<\/td>6<\/td>4<\/td>7<\/td>2<\/td>1<\/td><\/tr>
3<\/td> <\/td> <\/td> <\/td>3<\/td>3<\/td>2<\/td>6<\/td>4<\/td><\/tr>
2<\/td> <\/td> <\/td>3<\/td>2<\/td>2<\/td>6<\/td>4<\/td>7<\/td><\/tr>
1<\/td> <\/td>3<\/td>2<\/td>4<\/td>6<\/td>4<\/td>7<\/td>2<\/td><\/tr>
0<\/td>3<\/td>2<\/td>4<\/td>6<\/td>4<\/td>7<\/td>2<\/td>1<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n

FIFO<\/strong>
 \u8a2d\u67090\u52302^n-1\u500bblock,\u8d8a\u5927\u7684block\u8868\u793a\u9032\u5165\u7684\u6642\u9593\u8d8a\u65e9,\u9700\u8981\u53d6\u4ee3\u6642\u5247\u9078\u6700\u65e9\u7684block
 hit\u6642,\u4e0d\u9700\u52d5\u4f5c
 miss\u6642,\u5c07\u65b0\u9032\u7684block\u8a2d\u70ba0,\u4e26\u5c07\u5176\u4ed6block\u90fd+1
 \u6210\u672c\u8f03\u4f4e<\/p>\n\n\n\n

NRU
<\/strong> \u6bcf\u500bblock\u6703\u4f7f\u7528reference bit(\u5b58\u53d6\u4f4d\u5143)\u8207modify bit(\u4fee\u6539\u4f4d\u5143)
 \u53ef\u914d\u5408\u5b58\u53d6\u5c40\u90e8\u6027,\u8b93\u5931\u8aa4\u7387\u6e1b\u4f4e,\u6613\u88fd\u4f5c\u4e14\u6210\u672c\u4f4e………………………………………………<\/p>\n\n\n\n

page\u7684\u5927\u5c0f<\/strong>
\u6703\u5f71\u97ff\u4e3b\u8a18\u61b6\u7684\u7a7a\u9593\u4f7f\u7528\u6548\u7387,
\u8f03\u5c0f\u5247internal fragmenation\u6703\u8f03\u5c11,page mapping table\u6703\u8f03\u5927
\u8f03\u5927\u5247internal fragmenation\u6703\u8f03\u5927,page mapping table\u6703\u8f03\u5c0f
page\u592a\u5927\u6216\u592a\u5c0f\u6703\u4f7f\u5931\u8aa4\u7387\u8b8a\u9ad8
ps:\u5be6\u969b\u8a2d\u8a08\u4e2d,\u63a1\u7528pageing\u6216pageing\/segmentation\u7684\u865b\u64ec\u8a18\u61b6\u9ad4,hit rate\u53ef\u905499.99%~99.9999%
\u8a2d\u7a0b\u5f0f\u5927\u5c0f=s,\u9801\u7684\u5927\u5c0f=p,\u9801\u5c0d\u7167\u8868\u4e2d\u6bcf\u4e00\u500b\u6b04\u4f4d\u7684\u5927\u5c0f=e,\u5247
\u5167\u90e8\u788e\u7247\u5e73\u5747=p\/2,\u7a0b\u5f0f\u7684\u9801\u5c0d\u7167\u8868=s*e\/p,\u6240\u4ee5\u7a0b\u5f0f\u7684\u7a7a\u9593\u6d6a\u8cbb=p\/2+s*e\/p
\u8981\u8b93\u7a7a\u9593\u6d6a\u8cbb\u6700\u5c0f,\u53ef\u5c07p\u4e00\u968e\u5fae\u5206\u4e26\u53e6\u7d50\u679c\u70ba0\u5f971\/2-s*e\/p^2=0,\u6240\u4ee5p=sqrt(2*s*e)

\u5e73\u5747\u5b58\u53d6\u6642\u9593
<\/strong>\u516c\u5f0f=\u8a08\u7b97\u4f4d\u5740\u6642\u9593+hit\u5b58\u53d6\u6642\u9593+miss\u5b58\u53d6\u6642\u9593
\u8a08\u7b97\u4f4d\u5740\u6642\u9593<\/strong>:\u900f\u904eTLB\u6216\u662fpage table\u5c07\u865b\u64ec\u4f4d\u5740\u8f49\u63db\u6210\u5be6\u969b\u4f4d\u5740\u6240\u9700\u7684\u6642\u9593
\u516c\u5f0f=ratio of TLB*TLB access time+(1-hit ratio of TLB)*memory access time
hit\u5b58\u53d6\u6642\u9593<\/strong>:\u53ef\u4ee5\u5728\u4e3b\u8a18\u61b6\u55ae\u5143\u5b58\u53d6\u5230\u8cc7\u6599\u6240\u9700\u7684\u6642\u9593
\u516c\u5f0f=(1-page fault rate)*memory access time
miss\u5b58\u53d6\u6642\u9593<\/strong>:\u767c\u751fpage fault\u9032\u884c\u8655\u7406\u6240\u9700\u7684\u6642\u9593
\u516c\u5f0f=page fault rate*average page-fault service time
ex:
\u8a2dTLB access time=20ns,memory access time=100ns,average page-fault service time=25ms,hit ratio of TLB=98%,page fault rate=0.0001%
\u6240\u4ee5\u8a08\u7b97\u4f4d\u5740\u6642\u9593=0.98*20ns+0.02*100ns=21.6ns,hit\u5b58\u53d6\u6642\u9593=99.9999%*100ns=99.9999ns,miss\u5b58\u53d6\u6642\u9593=0.0001%*25ms=25ns
\u800c\u5e73\u5747\u5b58\u53d6\u6642\u9593=21.6ns+99.9999ns+25ns\u7d04=146.6ns<\/p>\n","protected":false},"excerpt":{"rendered":"

virtual memory(\u865b\u64ec\u8a18\u61b6\u9ad4)\u7528\u9014:\u5c07\u8f14\u52a9\u8a18\u61b6\u9ad4 …<\/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":[23],"tags":[],"class_list":["post-738","post","type-post","status-publish","format-standard","hentry","category-computerarchitecture"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/738","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=738"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/738\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=738"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=738"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=738"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}