{"id":1004,"date":"2019-11-19T17:19:32","date_gmt":"2019-11-19T09:19:32","guid":{"rendered":"http:\/\/149.129.74.185\/?p=1004"},"modified":"2019-11-19T17:19:32","modified_gmt":"2019-11-19T09:19:32","slug":"%e6%93%8d%e4%bd%9c%e7%b3%bb%e7%bb%9fweek-10-note","status":"publish","type":"post","link":"http:\/\/www.magicmipamipa.com\/?p=1004","title":{"rendered":"[\u64cd\u4f5c\u7cfb\u7edf]Week 10 Note"},"content":{"rendered":"<p>7.5 \u6b7b\u9501\u907f\u514d<\/p>\n<p>Banker&#8217;s Algorithm \u94f6\u884c\u5bb6\u7b97\u6cd5<\/p>\n<p><strong>Data structures:<\/strong><\/p>\n<ul>\n<li>Let n = number of processes, and m = number of resources types.<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\"><span style=\"text-decoration: underline; color: #993300;\"><strong>Available<\/strong><\/span>: Vector of length m. If available [j] = k, there are k instances of resource type Rj available.Rj\u7c7b\u8d44\u6e90\u6709\u4e2a\u53ef\u7528<\/p>\n<p style=\"padding-left: 30px;\"><span style=\"text-decoration: underline;\"><strong><span style=\"color: #993300; text-decoration: underline;\">Max<\/span><\/strong><\/span>: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj .\u884c\u8868\u793a\u67d0\u4e00\u4e2a\u8fdb\u7a0b\u5bf9\u6240\u6709\u8d44\u6e90\u7684\u8bf7\u6c42\uff0cM[i,j]\u8868\u793aPi\u8fdb\u7a0b\u5bf9Rj\u8d44\u6e90\u6700\u5927\u7684\u9700\u6c42\u662fk\u4e2a<\/p>\n<p style=\"padding-left: 30px;\"><strong><span style=\"text-decoration: underline; color: #993300;\">Allocation<\/span><\/strong>: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj. Rj\u8d44\u6e90\u5bf9Pi\u5df2\u5206\u914d\u4e86k\u4e2a<\/p>\n<p style=\"padding-left: 30px;\"><strong><span style=\"text-decoration: underline; color: #993300;\">Need<\/span><\/strong>: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task. Need [i,j] = Max[i,j] \u2013 Allocation [i,j] Pi\u8fd8\u9700k\u4e2aRj\u8d44\u6e90<\/p>\n<p><strong>Safety Algorithm<\/strong>\u00a0\u5b89\u5168\u7b97\u6cd5<\/p>\n<p style=\"padding-left: 30px;\">1. Let Work and Finish be vectors of length m and n, respectively.<\/p>\n<p style=\"padding-left: 30px;\"><span style=\"color: #993300;\">Initialize: Work = Available Finish [i] = false for i = 1,2,3, \u2026, n. <\/span><\/p>\n<p style=\"padding-left: 30px;\">2. Find an index i such that both:<\/p>\n<p style=\"padding-left: 30px;\"><span style=\"color: #993300;\">(a). Finish[i] = false <\/span><\/p>\n<p style=\"padding-left: 30px;\"><span style=\"color: #993300;\">(b). Need[i] &lt;= Work <\/span><\/p>\n<p style=\"padding-left: 30px;\">If no such i exists, go to step 4.<\/p>\n<p style=\"padding-left: 30px;\">3. Work = Work + Allocation<\/p>\n<p style=\"padding-left: 30px;\">Finish[i] = true<\/p>\n<p style=\"padding-left: 30px;\">go to step 2.<\/p>\n<p style=\"padding-left: 30px;\">4. If Finish[i] == true for all i, then the system is in a safe state.\u6240\u6709\u8fdb\u7a0b\u5b8c\u6210<\/p>\n<p>Resource-Request Algorithm<\/p>\n<p style=\"padding-left: 30px;\">Requesti = request vector for process Pi . If Requesti [j] = k then process Pi wants k instances of resource type Rj.<\/p>\n<p style=\"padding-left: 30px;\">1. If Requesti &lt;= Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim.<\/p>\n<p style=\"padding-left: 30px;\">2. If Requesti &lt;= Available, go to step 3. Otherwise Pi must wait, since resources are not available.\u53ef\u7528\u6ee1\u8db3\uff0c\u7ee7\u7eed<\/p>\n<p style=\"padding-left: 30px;\">3. Pretend to allocate requested resources to Pi by modifying the state as follows:<\/p>\n<p style=\"padding-left: 60px;\"><code>Available = Available - Requesti ; <\/code><\/p>\n<p style=\"padding-left: 60px;\"><code>Allocationi = Allocationi + Requesti ; <\/code><\/p>\n<p style=\"padding-left: 60px;\"><code>Needi = Needi \u2013 Requesti ; <\/code><\/p>\n<p style=\"padding-left: 60px;\">\u2022 Call Safety Algorithm<\/p>\n<p style=\"padding-left: 90px;\">\u2022 If safe -&gt; the resources are allocated to Pi .<\/p>\n<p style=\"padding-left: 90px;\">\u2022 If unsafe -&gt; <span style=\"color: #993300;\">Pi must wait<\/span>, and the old resource-allocation state is restored<\/p>\n<p>&nbsp;<\/p>\n<p>7.7 \u6b7b\u9501\u6062\u590d recovery<\/p>\n<p>\u68c0\u6d4b\u5230\u6b7b\u9501\u540e\u91c7\u53d6\u63aa\u65bd\uff1a<\/p>\n<ul>\n<li>\u901a\u77e5\u7cfb\u7edf\u7ba1\u7406\u5458<\/li>\n<li>\u7cfb\u7edf\u81ea\u5df1\u6062\u590d<\/li>\n<\/ul>\n<p>\u6253\u7834\u6b7b\u9501\u4e24\u79cd\u65b9\u6cd5\uff1a<\/p>\n<ul>\n<li>\u8fdb\u7a0b\u7ec8\u6b62<\/li>\n<li>\u62a2\u5360\u8d44\u6e90<\/li>\n<\/ul>\n<p>Abort all deadlocked processes.<\/p>\n<p>Abort one process at a time until the deadlock cycle is eliminated.<\/p>\n<p>Many factors may determine which process is chosen, include:<\/p>\n<ul style=\"list-style-type: circle;\">\n<li>Priority of the process.\u4f18\u5148\u7ea7<\/li>\n<li>How long process has computed, and how much longer to completion.\u5df2\u8fd0\u884c\u65f6\u95f4<\/li>\n<li>Resources the process has used.\u5df2\u5360\u7528\u8d44\u6e90<\/li>\n<li>Resources process needs to complete.\u9700\u8981\u5b8c\u6210\u8d44\u6e90<\/li>\n<li>How many processes will need to be terminated.<\/li>\n<li>Whether the process is interactive or batch.<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h3 style=\"text-align: center;\" id=\"mcetoc_1dq1dafgo0\">Chapter 8 Main Memory<\/h3>\n<p>8.1 Background<\/p>\n<p>\u5fc5\u987b\u5c06\u7a0b\u5e8f\uff08\u4ece\u78c1\u76d8\uff09\u5e26\u5165\u5185\u5b58\u5e76\u653e\u7f6e\u5728\u8fdb\u7a0b\u4e2d\u624d\u80fd\u8fd0\u884c<br \/>\n&#8211; \u4e3b\u5b58\u50a8\u5668\u548c\u5bc4\u5b58\u5668\u4ec5\u662f\u5b58\u50a8CPU\u53ef\u4ee5\u76f4\u63a5\u8bbf\u95ee\u7684<br \/>\n&#8211; \u5728\u4e00\u4e2aCPU\u65f6\u949f\uff08\u6216\u66f4\u5c11\uff09\u4e2d\u8fdb\u884c\u5bc4\u5b58\u5668\u8bbf\u95ee<br \/>\n&#8211; \u4e3b\u5185\u5b58\u53ef\u80fd\u9700\u8981\u5f88\u591a\u5468\u671f<br \/>\n&#8211; \u7f13\u5b58\u4f4d\u4e8e\u4e3b\u5b58\u50a8\u5668\u548cCPU\u5bc4\u5b58\u5668\u4e4b\u95f4<br \/>\n&#8211; \u9700\u8981\u4fdd\u62a4\u5185\u5b58\u4ee5\u786e\u4fdd\u6b63\u786e\u64cd\u4f5c<\/p>\n<p>The concept of a logical address space that is bound to a separate physical address<br \/>\nspace is central to proper memory management<\/p>\n<p>&#8211; Logical address\uff08\u903b\u8f91\u5730\u5740\uff0c\u76f8\u5bf9\u5730\u5740\uff0c\u865a\u5730\u5740\uff09\u2013 generated by the CPU; also referred<br \/>\nto as virtual address\uff08\u4ece0\u5f00\u59cb\u7684\uff09<\/p>\n<ul>\n<li>\u00a0\u7528\u6237\u7684\u7a0b\u5e8f\u7ecf\u8fc7\u6c47\u7f16\u6216\u7f16\u8bd1\u540e\u5f62\u6210\u76ee\u6807\u4ee3\u7801\uff0c\u76ee\u6807\u4ee3\u7801\u901a\u5e38\u91c7\u7528\u76f8\u5bf9\u5730\u5740\u7684\u5f62\u5f0f\u3002<\/li>\n<li>\u00a0\u5176\u9996\u5730\u5740\u4e3a0\uff0c\u5176\u4f59\u6307\u4ee4\u4e2d\u7684\u5730\u5740\u90fd\u76f8\u5bf9\u4e8e\u9996\u5730\u5740\u6765\u7f16\u5740\u3002<\/li>\n<li>\u00a0\u4e0d\u80fd\u7528\u903b\u8f91\u5730\u5740\u5728\u5185\u5b58\u4e2d\u8bfb\u53d6\u4fe1\u606f\u3002<\/li>\n<\/ul>\n<p>&#8211; Physical address \uff08\u7269\u7406\u5730\u5740\uff0c\u7edd\u5bf9\u5730\u5740\uff0c\u5b9e\u5730\u5740\uff09 \u2013 address seen by the memory unit<\/p>\n<p>&#8211; \u5185\u5b58\u4e2d\u5b58\u50a8\u5355\u5143\u7684\u5730\u5740\u3002\u7269\u7406\u5730\u5740\u53ef\u76f4\u63a5\u5bfb\u5740<\/p>\n<p>&nbsp;<\/p>\n<p>MMU\uff08Memory-Management Unit\uff09<\/p>\n<p>In MMU scheme, the value in the relocation register\uff08\u91cd\u5b9a\u4f4d\u5bc4\u5b58\u5668\uff09 is added to every address generated by a user process at the time it is sent to memory<\/p>\n<p>&nbsp;<\/p>\n<p>Dynamic Linking\uff08\u52a8\u6001\u94fe\u63a5\uff09<\/p>\n<p>Using dynamic linking, external libraries can be preloaded into (shared) memory<\/p>\n<p>When a process calls a library function, the corresponding physical address is determined<\/p>\n<p>Small piece of code, stub, used to locate the appropriate memory-resident library routine<\/p>\n<p>Stub replaces itself with the address of the routine, and executes the routine<\/p>\n<p>Operating system needed to check if routine is in processes\u2019 memory addres<\/p>\n<p>Dynamic linking is particularly useful for libraries<\/p>\n<p>System also known as shared libraries<\/p>\n<ul>\n<li>Dynamically Linked Library \u52a8\u6001\u94fe\u63a5\u5e93<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>8.2 Swapping \uff08\u4ea4\u6362\u6280\u672f\uff09<\/p>\n<ol>\n<li>\u4ea4\u6362\u6280\u672f<\/li>\n<\/ol>\n<p style=\"padding-left: 30px;\">\u53ef\u4ee5\u5c06\u8fdb\u7a0b\u6682\u65f6\u4ece\u5185\u5b58\u4e2d\u4ea4\u6362\u5230\u540e\u5907\u5b58\u50a8\uff0c\u7136\u540e\u8fdb\u884c\u5904\u7406\u8fd4\u56de\u5185\u5b58\u4ee5\u7ee7\u7eed\u6267\u884c\u3002<\/p>\n<p style=\"padding-left: 30px;\">\u540e\u5907\u5b58\u50a8\u2013\u5feb\u901f\u78c1\u76d8\uff0c\u5176\u5927\u5c0f\u8db3\u4ee5\u5bb9\u7eb3\u6240\u6709\u5b58\u50a8\u6620\u50cf\u7684\u526f\u672c\u7528\u6237\uff1b \u5fc5\u987b\u63d0\u4f9b\u5bf9\u8fd9\u4e9b\u5185\u5b58\u6620\u50cf\u7684\u76f4\u63a5\u8bbf\u95ee\u3002<\/p>\n<p style=\"padding-left: 60px;\">Linux\uff0cUNIX\u2014\u4ea4\u6362\u533a<\/p>\n<p style=\"padding-left: 60px;\">Windows-\u4ea4\u6362\u6587\u4ef6\uff08pagefile.sys\uff09<\/p>\n<p style=\"padding-left: 30px;\">\u63a8\u51fa\uff0c\u63a8\u51fa\uff08\u8c03\u51fa\uff0c\u8c03\u8fdb\uff09\u2013\u7528\u4e8e\u57fa\u4e8e\u4f18\u5148\u7ea7\u7684\u8c03\u5ea6\u7684\u4ea4\u6362\u53d8\u4f53\u7b97\u6cd5; \u4ea4\u6362\u8f83\u4f4e\u4f18\u5148\u7ea7\u7684\u8fdb\u7a0b\uff0c\u4ee5\u4fbf\u53ef\u4ee5\u52a0\u8f7d\u8f83\u9ad8\u4f18\u5148\u7ea7\u7684\u8fdb\u7a0b\u5e76\u6267\u884c\u3002<\/p>\n<p style=\"padding-left: 30px;\">\u4ea4\u6362\u65f6\u95f4\u7684\u4e3b\u8981\u90e8\u5206\u662f\u4f20\u8f93\u65f6\u95f4\uff1b \u603b\u4f20\u8f93\u65f6\u95f4\u4e0e\u4ea4\u6362\u7684\u5185\u5b58\u91cf\u5728\u8bb8\u591a\u7cfb\u7edf\uff08\u4f8b\u5982UNIX\uff0cLinux\u548cWindows\uff09\u4e0a\u90fd\u53ef\u4ee5\u627e\u5230\u4fee\u6539\u540e\u7684\u4ea4\u6362\u7248\u672c\u3002<\/p>\n<p style=\"padding-left: 30px;\">\u7cfb\u7edf\u7ef4\u62a4\u7740\u4e00\u4e2a\u51c6\u5907\u5c31\u7eea\u7684\u51c6\u5907\u8fd0\u884c\u961f\u5217\uff0c\u8fd9\u4e9b\u961f\u5217\u4e0a\u6709\u5185\u5b58\u6620\u50cf\u78c1\u789f\u3002<\/p>\n<p>on Moblie Systems:<\/p>\n<ul>\n<li>\u79fb\u52a8\u7cfb\u7edf<span style=\"text-decoration: underline;\"><strong>\u4e0d\u652f\u6301\u4ea4\u6362<\/strong><\/span>\uff0cFlash memory based:\n<ul>\n<li>\u5c0f\u7a7a\u95f4<\/li>\n<li>\u95ea\u5b58\u5199\u6b21\u6570\u9650\u5236<\/li>\n<li>\u5728\u79fb\u52a8\u5e73\u53f0\u4e0a\u95ea\u5b58\u548cCPU\u4e4b\u95f4\u7684\u541e\u5410\u91cf\u5f88\u4f4e<\/li>\n<\/ul>\n<\/li>\n<li>iOS\u8981\u6c42\u5e94\u7528\u7a0b\u5e8f\u81ea\u613f\u653e\u5f03\u5206\u914d\u7684\u5185\u5b58\n<ul>\n<li>\u53ea\u8bfb\u6570\u636e\u4ece\u7cfb\u7edf\u4e2d\u76f4\u63a5\u5220\u9664\uff0c\u5df2\u4fee\u6539\u6570\u636e\u4e0d\u4f1a\u88ab\u5220\u9664<\/li>\n<li>OS\u53ef\u4ee5\u7ec8\u6b62\u4efb\u4f55\u672a\u80fd\u91ca\u653e\u8db3\u591f\u7a7a\u95f4\u7684\u5e94\u7528<\/li>\n<\/ul>\n<\/li>\n<li>Android\u5982\u679c\u7a7a\u95f2\u5185\u5b58\u4e0d\u8db3\uff0c\u4f1a\u7ec8\u6b62\u5e94\u7528\u7a0b\u5e8f\uff0c\u4f46\u9996\u5148\u4f1a\u5c06\u5e94\u7528\u7a0b\u5e8f\u72b6\u6001\u5199\u5165\u95ea\u5b58\uff0c\u4ee5\u4fbf\u5feb\u901f\u91cd\u542f<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>8.3 \u8fde\u7eed\u5206\u914d<\/p>\n<p>\u4e3b\u5185\u5b58\u901a\u5e38\u5206\u4e3a\u4e24\u4e2a\u5206\u533a\uff1a<\/p>\n<ul style=\"list-style-type: circle;\">\n<li>Resident operating system\uff08\u9a7b\u7559\u64cd\u4f5c\u7cfb\u7edf\uff09\uff0c\u901a\u5e38\u4fdd\u5b58\u5728\u5e26\u6709\u4e2d\u65ad\u5411\u91cf\u7684\u4f4e\u5185\u5b58\u4e2d<\/li>\n<li>User processes \u5c06\u7528\u6237\u8fdb\u7a0b\u4fdd\u5b58\u5728\u9ad8\u5185\u5b58\u4e2d<\/li>\n<\/ul>\n<p>\u91cd\u5b9a\u4f4d\u5bc4\u5b58\u5668\uff0c\u7528\u4e8e\u4fdd\u62a4\u7528\u6237\u8fdb\u7a0b\u5f7c\u6b64\u4e4b\u95f4\u4ee5\u53ca\u66f4\u6539\u64cd\u4f5c\u7cfb\u7edf\u4ee3\u7801\u548c\u6570\u636e\u65f6\u76f8\u4e92\u4fdd\u62a4\uff1a<\/p>\n<ul style=\"list-style-type: circle;\">\n<li>\u57fa\u5740\u5bc4\u5b58\u5668\u5305\u542b\u6700\u5c0f\u7269\u7406\u5730\u5740\u7684\u503c<\/li>\n<li>\u9650\u5236\u5bc4\u5b58\u5668\u5305\u542b\u903b\u8f91\u5730\u5740\u8303\u56f4\u2013\u6bcf\u4e2a\u903b\u8f91\u5730\u5740\u5fc5\u987b\u5c0f\u4e8e\u9650\u5236\u5bc4\u5b58\u5668<\/li>\n<li>MMU\u52a8\u6001\u6620\u5c04\u903b\u8f91\u5730\u5740<\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>7.5 \u6b7b\u9501\u907f\u514d Banker&#8217;s Algorithm \u94f6\u884c\u5bb6\u7b97\u6cd5 Data struc [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[16,20],"tags":[],"_links":{"self":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/1004"}],"collection":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1004"}],"version-history":[{"count":1,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/1004\/revisions"}],"predecessor-version":[{"id":1005,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=\/wp\/v2\/posts\/1004\/revisions\/1005"}],"wp:attachment":[{"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1004"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1004"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.magicmipamipa.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1004"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}