-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
1566 lines (878 loc) · 73.2 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<!--[if IEMobile 7 ]><html class="no-js iem7"><![endif]-->
<!--[if lt IE 9]><html class="no-js lte-ie8"><![endif]-->
<!--[if (gt IE 8)|(gt IEMobile 7)|!(IEMobile)|!(IE)]><!--><html class="no-js" lang="en"><!--<![endif]-->
<head>
<meta charset="utf-8">
<title>D W</title>
<meta name="author" content="Harry">
<meta name="description" content="这篇文章可谓来之不易, 因为太长时间没写了, 中间换了系统, 之前配好的环境都没了, 就费了很大力气又装了一边… 这里就不详细说明了 这里主要记录一下 ubuntu 下挂载 Windows 分区的问题 mount 既然是挂载, 就先说一下这个命令, 一般来说, 格式是这样的 …">
<!-- http://t.co/dKP3o1e -->
<meta name="HandheldFriendly" content="True">
<meta name="MobileOptimized" content="320">
<meta name="viewport" content="width=device-width, initial-scale=1">
<link rel="canonical" href="http://d-w-.github.io">
<link href="/favicon.png" rel="icon">
<link href="/stylesheets/screen.css" media="screen, projection" rel="stylesheet" type="text/css">
<link href="/atom.xml" rel="alternate" title="D W" type="application/atom+xml">
<script src="/javascripts/modernizr-2.0.js"></script>
<script src="//ajax.googleapis.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<script>!window.jQuery && document.write(unescape('%3Cscript src="/javascripts/libs/jquery.min.js"%3E%3C/script%3E'))</script>
<script src="/javascripts/octopress.js" type="text/javascript"></script>
<script src="/javascripts/dawnfan.js" type="text/javascript"></script>
<script src="/javascripts/jquery.nicescroll.min.js" type="text/javascript"></script>
<!--Fonts from Google"s Web font directory at http://google.com/webfonts -->
<link href="//fonts.googleapis.com/css?family=PT+Serif:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
<link href="//fonts.googleapis.com/css?family=PT+Sans:regular,italic,bold,bolditalic" rel="stylesheet" type="text/css">
</head>
<body >
<header role="banner"><a id="avatar" href="/about"><img src="/images/icon.jpg" alt="avatar"></a>
<div class="header-left">
<hgroup>
<h1><a href="/">D W</a></h1>
<div class="subtitle">
<h2>Brick walls are there for a reason, they let us prove how badly we want things.</h2>
</div>
</hgroup>
</div>
<div class="header-right">
<ul class="main-navigation">
<div class="selected">
<li><a href="/">blog</a></li></div>
<div>
<li><a href="/blog/archives">archives</a></li></div>
<div>
<li><a href="/about">about</a></li></div>
</ul>
</div></header>
<span id="btn-list" onclick="turnList()">></span>
<div id="list" class="off">
<h2>Posts List</h2>
<h5>
<a href="/blog/2016/04/12/mount-windows-partitions-on-ubuntu/">Mount Windows Partitions on Ubuntu</a>
<span>April 12, 2016</span>
</h5>
<h5>
<a href="/blog/2015/10/10/zui-duan-lu-jing-wen-ti/">最短路径问题</a>
<span>October 10, 2015</span>
</h5>
<h5>
<a href="/blog/2015/09/28/story-continued-bao-yan-zhi-lu/">Story Continued – 保研之路</a>
<span>September 28, 2015</span>
</h5>
<h5>
<a href="/blog/2015/08/27/reading-computer-systems-a-programmers-perspective-2/">Reading Computer Systems(A Programmer’s Perspective):2</a>
<span>August 27, 2015</span>
</h5>
<h5>
<a href="/blog/2015/08/22/cheng-fa-ni-yuan-euclidding-li-he-zhong-guo-sheng-yu-ding-li/">乘法逆元 Euclid定理和中国剩余定理</a>
<span>August 22, 2015</span>
</h5>
<h5>
<a href="/blog/2015/08/14/reading-computer-systems-a-programmers-perspective-1/">Reading Computer Systems(A Programmer’s Perspective):1</a>
<span>August 14, 2015</span>
</h5>
<h5>
<a href="/blog/2015/04/23/half-way-conclusion-of-3rd-grade-in-college/">Half Way Conclusion of 3rd Grade in College</a>
<span>April 23, 2015</span>
</h5>
<h5>
<a href="/blog/2015/04/05/gityuan-cheng-dai-ma-guan-li-,sshhuan-shi-https/">git远程代码管理，SSH还是HTTPS</a>
<span>April 5, 2015</span>
</h5>
<h5>
<a href="/blog/2015/04/05/moving-my-blog-to-octopress/">Moving My Blog to Octopress</a>
<span>April 5, 2015</span>
</h5>
<h5>
<a href="/blog/2015/03/25/Monster-Storm/">Monster Storm</a>
<span>March 25, 2015</span>
</h5>
<h5>
<a href="/blog/2015/03/23/Review_Vcool-Website/">Review VCool Website</a>
<span>March 23, 2015</span>
</h5>
<h5>
<a href="/blog/2015/03/22/Morris-Traversal/">Morris Traversal</a>
<span>March 22, 2015</span>
</h5>
<h5>
<a href="/blog/2015/03/20/douban-paper-test/">豆瓣笔试</a>
<span>March 20, 2015</span>
</h5>
<h5>
<a href="/blog/2014/12/20/Distinct-Subsequences/">LeetCode上面的Distinct Subsequences总结</a>
<span>December 20, 2014</span>
</h5>
<h5>
<a href="/blog/2014/11/25/Word-Ladder/">LeetCode上面的WordLadder总结</a>
<span>November 25, 2014</span>
</h5>
<h5>
<a href="/blog/2014/11/14/Linux-File-System/">Linux文件系统基础</a>
<span>November 14, 2014</span>
</h5>
<h5>
<a href="/blog/2014/10/15/First-Blog/">第一篇博客</a>
<span>October 15, 2014</span>
</h5>
<h5>
<a href="/blog/2014/03/03/Hello-World/">Markdown Style Guide</a>
<span>March 3, 2014</span>
</h5>
</div>
<div id="main">
<div id="content">
<div class="blog-index">
<article>
<header>
<h1 class="entry-title"><a href="/blog/2016/04/12/mount-windows-partitions-on-ubuntu/">Mount Windows Partitions on Ubuntu</a></h1>
<p class="meta">
<time datetime="2016-04-12T21:42:03+08:00" pubdate data-updated="true"></time>
| <a href="/blog/2016/04/12/mount-windows-partitions-on-ubuntu/#comments">Comments</a>
</p>
</header>
<div class="entry-content"><p>这篇文章可谓来之不易, 因为太长时间没写了, 中间换了系统, 之前配好的环境都没了, 就费了很大力气又装了一边… 这里就不详细说明了</p>
<p>这里主要记录一下 ubuntu 下挂载 Windows 分区的问题</p>
<h2>mount</h2>
<p>既然是挂载, 就先说一下这个命令, 一般来说, 格式是这样的</p>
<blockquote><p>mount <em>dir</em></p></blockquote>
<p><em>dir</em> 就是要挂载的分区所在的地方, 一般是类似 <code>/dev/sda1</code> 这样的地址</p>
<p>但是记住每个 windows 分区对应那个sda 后面的数字太麻烦了, <a href="http://www.cyberciti.biz/faq/rhel-centos-debian-fedora-mount-partition-label/">直接根据分区挂载</a>:</p>
<blockquote><p>mount -L label_name_here /path/to/mount/point</p></blockquote>
<p>或者, 查一下 LABEL 和 NAME 的对应关系,</p>
<p><a href="https://askubuntu.com/questions/527790/list-all-partition-labels">使用 list block</a></p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
<span class='line-number'>4</span>
<span class='line-number'>5</span>
<span class='line-number'>6</span>
<span class='line-number'>7</span>
<span class='line-number'>8</span>
<span class='line-number'>9</span>
<span class='line-number'>10</span>
<span class='line-number'>11</span>
<span class='line-number'>12</span>
<span class='line-number'>13</span>
<span class='line-number'>14</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>$ sudo lsblk -o NAME,LABEL
</span><span class='line'>NAME LABEL
</span><span class='line'>sda
</span><span class='line'>├─sda1 System Reserved
</span><span class='line'>├─sda2 windows
</span><span class='line'>├─sda3 ubuntu
</span><span class='line'>├─sda4
</span><span class='line'>├─sda5 arch
</span><span class='line'>├─sda6
</span><span class='line'>│ └─lvmg-homelvm (dm-0) homelb
</span><span class='line'>└─sda7
</span><span class='line'>sdb
</span><span class='line'>└─sdb1
</span><span class='line'> └─lvmg-homelvm (dm-0) homelb</span></code></pre></td></tr></table></div></figure>
<p><a href="https://askubuntu.com/questions/527790/list-all-partition-labels">使用 block id</a></p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
<span class='line-number'>4</span>
<span class='line-number'>5</span>
<span class='line-number'>6</span>
<span class='line-number'>7</span>
<span class='line-number'>8</span>
<span class='line-number'>9</span>
<span class='line-number'>10</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>sudo blkid -o list
</span><span class='line'>
</span><span class='line'>
</span><span class='line'>device fs_type label mount point UUID
</span><span class='line'>----------------------------------------------------------------------------------
</span><span class='line'>/dev/sda1 ntfs WINRE_DRV (not mounted) 604C3A6A4C3A3B5C
</span><span class='line'>/dev/sda2 vfat SYSTEM_DRV (not mounted) 6C3C-72E3
</span><span class='line'>/dev/sda3 vfat LRS_ESP (not mounted) 5240-1BEE
</span><span class='line'>/dev/sda5 ntfs Windows8_OS /media/Win8 A47A42FF7A42CDAC
</span><span class='line'>/dev/sda6 ntfs Daten /media/Daten 72860971860936DF
</span></code></pre></td></tr></table></div></figure>
<h2>自动挂载</h2>
<p>windows 的分区是不会在开机的时候自动被挂载的, 想自动挂载的话需要<a href="https://askubuntu.com/questions/182446/how-do-i-view-all-available-hdds-partitions">修改系统文件</a> <code>/etc/fstab</code></p>
<p>其中针对每个分区可以进行挂载的参数配置, 如下:</p>
<blockquote><p>UUID=AA8C58748C583CCF /media/harry/code ntfs umask=0033,gid=1000,uid=1000 0 1</p></blockquote>
<p>UUID是磁盘的id, 后面是挂载地址, 分区格式, 参数, 等等..</p>
<p>这里说一下参数</p>
<h3>umask</h3>
<p>user mask</p>
<p>是打开文件之后文件<strong>去掉</strong>的读写权限</p>
<p>0 代表什么权限都不去掉, 也就是读写执行都有</p>
<p>1 代表去掉执行 2 代表去掉写 4 代表去掉读</p>
<p>它们互相组合就得到了总共需要去掉的权限</p>
<p>033 就代表了文件所有者有所有权限, 同组或者其他组的其他人只能读</p>
<p>那么, 从<strong>哪里</strong>减去呢?</p>
<p>是从默认权限里面减去, 文件的默认权限是 666, 文件夹的默认权限是 777</p>
<ul>
<li>创建文件时：(-rw-rw-rw-) - (—–w–w-) ==> -rw-r–r–</li>
<li>创建目录时：(drwxrwxrwx) - (d—-w–w-) ==> drwxr-xr-x</li>
</ul>
<p><a href="http://vbird.dic.ksu.edu.tw/linux_basic/0220filemanager_4.php#umask">source</a></p>
<hr />
<p>比较 tricky 的一点, 挂载一个windows硬盘的时候, 默认是给所有文件所有权限的</p>
<p>如果只想把文件的 执行 权限去掉的话, 就不能使用 umask 来控制permission了(那样会把文件夹的执行权限也去掉..从而访问不了任何文件)</p>
<p>这里就要引进 fmask 和 dmask 了</p>
<h3>fmask dmask</h3>
<p>很简单 file mask , 和 directory mask, 分别控制文件和文件夹需要去掉的权限</p>
<h3>gid uid</h3>
<p>挂载这个分区中所有的文件的所有者, 组
1000表示默认用户</p>
<p>另外也可以手动给mount<a href="https://superuser.com/questions/320415/linux-mount-device-with-specific-user-rights">加参数挂载</a></p>
<pre><code> mount -t deviceFileFormat -o umask=filePermissons,gid=ownerGroupID,uid=ownerID /device /mountpoint
</code></pre>
<hr />
<p>所以,最后的配置变成了这样</p>
<blockquote><p># mount windows partition code volumn
UUID=AA8C58748C583CCF /media/harry/code ntfs uid=1000,gid=1000,dmask=022,fmask=133 0 1</p></blockquote>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2015/10/10/zui-duan-lu-jing-wen-ti/">最短路径问题</a></h1>
<p class="meta">
<time datetime="2015-10-10T20:21:35+08:00" pubdate data-updated="true"></time>
| <a href="/blog/2015/10/10/zui-duan-lu-jing-wen-ti/#comments">Comments</a>
</p>
</header>
<div class="entry-content"><p>这是一篇一直想写的总结. 主要是复习的时候详细复习(这里应该说是学习了..)了一下最短路径问题. 发现当年学的还有很多不足.. 很多算法没学过,学过的算法的局限性我也不知道.</p>
<p>就像当年数据结构上机,练习dijkstra算法,虽然我自己敲了出来,但是学长问我这个能不能处理负权边的问题的时候我还是不知道..</p>
<p>这里就以负权边为索引详细说一下几个最短路径算法..</p>
<h2>1. Dijkstra算法</h2>
<p>这个应该比较熟悉了,所有的涉及到最短路径的问题都会提到这个算法.
算法原理是贪心
解决单源最短路径问题</p>
<p>先选择一个源点,也就是路径的起点.
然后重复 k 轮,每一轮添加一个点到目前生成的树里面,所以 k 是除源点外节点的数目
每一轮中分为两步</p>
<ol>
<li><strong>选择</strong> : 选择源点到达距离最短的点当做下一个加入生成树里面的点</li>
<li><strong>更新</strong> : 由刚刚选择的点更新源点到每个点的距离</li>
</ol>
<p>其中.选择这一步跟时间复杂度有点关系</p>
<ol>
<li>比较朴素的方法,既然要选最小的,那就<strong>遍历</strong>一遍
<ul>
<li>这种方法在图比较稠密的时候比较好用,时间复杂度为:</li>
</ul>
</li>
<li>既然要找最小的,建一个<strong>最小堆</strong>就可以了,这样时间复杂度<strong>好像</strong>比较低
<ul>
<li>实际上这样做的话比较复杂,时间复杂度也不一定低.</li>
<li>复杂点 1 在堆里面要存一对元素(pair),因为我们需要距离这个值来进行比较,维护这个堆,还需要最小的距离对应的节点的编号,因为后面我们需要找到这个节点进行更新</li>
<li>复杂点 2 在于这个堆不是一成不变的,而需要<strong>更新</strong>,每次更新的时候都涉及堆结构的变化,会带来额外的复杂度</li>
<li>这种方法在图比较稀疏的时候比较好用,时间复杂度为:</li>
</ul>
</li>
</ol>
<p>最后,这个算法没有办法解决负权边的问题
因为上文提到,这个算法逐步生成一棵树的,而每一步新生成的节点都代表了源点到它的最短路径.
如果有负权边的话,上面那句话就无法保证,有可能会出现后面的一条负权边导致前面已经生成完毕的树里面的某个点遭到破坏</p>
<h2>2. Bellman-Ford算法</h2>
<p>这个算法有改进,权值可以为负</p>
<p>dist k[u] 代表最多经过 k 条边,源点到 u 的最短距离</p>
<p>dist n[u] 就是源点到 u 的最短距离, n 为顶点数(因为最短路径边数目小于顶点数,没有负权环)</p>
<p>可以得到推导式</p>
<pre><code>dist k[u] = min{dist k-1[u], min{dist k-1[j] + E[j][u] } }
</code></pre>
<p>由源点最多经过 k 条边,到 u 的最短距离是 { 最多经过 k-1 条边的最短距离 } 和 { 最多经过 k-1 条边到某个边的最短距离加上这个边到 u 的距离 }里面更小的那个</p>
<p>伪代码如下</p>
<figure class='code'><div class="highlight"><table><tr><td class="gutter"><pre class="line-numbers"><span class='line-number'>1</span>
<span class='line-number'>2</span>
<span class='line-number'>3</span>
<span class='line-number'>4</span>
<span class='line-number'>5</span>
</pre></td><td class='code'><pre><code class=''><span class='line'>for(k = 2 : n)
</span><span class='line'> for(u = 0 : n)
</span><span class='line'> for(i = 0:n)
</span><span class='line'> if(E[i][u] > 0 && dist[u] > E[i][u] + dist[i])
</span><span class='line'> dist[u] = E[i][u] + dist[i]</span></code></pre></td></tr></table></div></figure>
<p>上面提到了,这个算法不允许图中有负权环
因为出现了负权环,就不存在最短路径问题了,一直在负权环上面循环可以使路径趋近于无穷小..</p>
<h2>3.发现负权环</h2>
<p>上面提到了负权环,如何判断图中有没有负权环呢?</p>
<p>先看看如何发现环
可以进行一波深度优先搜索,如果发现搜索的过程中搜索到了已经搜到了的元素,就有环
或者进行一下拓扑排序,如果运行到最后还有元素,就能判断有环</p>
<p>由于和题目不太相关,这里先不多说了</p>
<h2>4.Floyd算法</h2>
<p>上面说了单源最短路径的算法,这里说一个多源的,就是求出整个图上每两点之间的最短路径</p>
<p>A ij[k] 代表从 i 到 j ,中转点序号小于等于 k 的最短路径</p>
<p>A ij[n] 就是从 i 到 j 的最短路径, n 为节点的数目,也就是节点序号的最大值</p>
<p>可以得到推导式</p>
<pre><code>A ij[k] = min{ A ij[k-1] , A ik[k-1] + A kj[k-1]}
</code></pre>
<p>从 i 到 j ,中转点序号小于等于 k 的最短路径等于 { 中转点序号小于 k-1 的最短路径 } 和 { 中转点序号最大为 k 的最短路径(中转点包含k) }里面最小的一个</p>
<hr />
<p>总结结束..
今天看到了一个有趣的单词
redraw re-draw 重画
我一开始看成了 red-raw 红红的原始的..</p>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2015/09/28/story-continued-bao-yan-zhi-lu/">Story Continued – 保研之路</a></h1>
<p class="meta">
<time datetime="2015-09-28T15:16:58+08:00" pubdate data-updated="true"></time>
| <a href="/blog/2015/09/28/story-continued-bao-yan-zhi-lu/#comments">Comments</a>
</p>
</header>
<div class="entry-content"><p>这是一篇关于保研的总结,记录我可能持续了整个大三的保研之路..</p>
<p>但是在此之前,先说个技术问题.
关于powershell的.
一开始在windows上面用git是直接下了个windows版的github,桌面版还挺好用的.随之而来的还有一个叫gitshell的东西,就是一个windows上用的shell,里面预装了git,能直接用git的各种指令,感觉还挺好.
后来我的windows升级到win10之后这个就出了问题,中文输入输不进去后来查了一下是页面编码的问题.
原因是这个shell编码由原来的GBK变成了UTF8,识别不了中文了,只要用</p>
<pre><code>>>>chcp 936
</code></pre>
<p>就可以了,这个是将当前页的编码改成936(GBK),change current code page
但是用 <code>rake new_post</code> 发博客的时候还是会遇到错误</p>
<blockquote><p> (UTF-8 regexp with GBK string)</p></blockquote>
<p>这个只要把字体改一下就可以,改一个可以支持中文的字体</p>
<hr />
<p>下面进入正文</p>
<h2>准备</h2>
<p>之前不确定要读研,说实话直到<a href="http://d-w-.github.io/blog/2015/04/23/half-way-conclusion-of-3rd-grade-in-college/">找实习不顺利</a>我才确定我这水平还是先读个研来的比较妥当.
但是我从大三一开始就做了一些相关的准备,这些准备到了最后也是确实起到了很大的帮助.
其实全部的准备工作就是刷OJ,一开始想法很简单,找工作算法能力也很重要,保研的话也会有机试,直接刷一下OJ锻炼一下算法能力也是很好的.</p>
<p>没想到我还挺喜欢刷题的,有空了就去leetcode上面做题,遇到难题可能好几天也想不出来,最后忍不住了去看别人分享的答案,毕竟这是少数,大多数题目思考一下还是能想出来的.
到最后,我在某一个时间点把leetcode上的题做完了(后来没怎么做过leetcode,新题都没做),通过代码的积累,算法也提升了一些.</p>
<p>做完了leetcode又去poj上面做题,但是上面题太多,就找了个经验贴,按上面的顺序做题,做了几天又发现了一个保研机试的oj,九度oj,上面的题都比较简单.用来练手热身都很合适,但是后来也放弃了.</p>
<p>直到我遇到了51nod这个oj,这个oj真的非常棒,中国社区,有很多活跃的大神在上面,而且题目有难度分级,还有一些教程,尤其是动态规划的,对于我这种从来没接受过专业ACM训练的人来说真是再好不过了.事实上,这个动态规划的训练到后来真的帮了我很多.</p>
<p>中间还兴致勃勃地报名了微软的编程之美,水了件T恤回来.</p>
<p>粗略算下来,oj上面的题我也刷了三四百道,逐渐对算法理解也更多,更深刻了.这些东西想想也真的是教不来,只能自己慢慢做,慢慢体会.</p>
<p>除了刷OJ之外,我也没进行其他的复习,也就是数据结构与算法,我找了好几本书,看了很多,也对以前学过的算法有了更多的理解.
复习的时候看的书很多,一个算法一本书上说的不明白我就去看另一本.不过主要看的就是 英文的<数据结构与算法分析:C语言描述>,看算法还能练练英语,还有就是学校图书馆借的Sedgewick的<算法>,里面对于图那一块讲的挺好的.</p>
<p>到现在记忆比较深的就是最短路径算法,记得当时上机给学长检查,学长为了检查代码是不是自己写的都要问几个问题,这个我大学所有的代码都是自己写的,但是学长问我,dijkstra算法能处理负权边问题吗?
我不知道,回答的可以,学长跟我说是不可以的,当时也没在意,谁知道现在复习才发现Bellman-ford算法才能处理负权边问题,这个后面回写一篇博客总结一下.
PS:数据结构这课我最后还是考了100,由此,分数或成绩并不能衡量一个人技术水平的高低.</p>
<h2>上交软院</h2>
<p>这是我参加保研夏令营去的第一所学校,也给我留了很深的印象.</p>
<p>上交的软院很小(比起大工的来说),但是校区很大,而且建筑设施都很不错.听完院长的介绍我才真正对上交的水平有所了解,实际上我对所有的学校基本都没什么了解..</p>
<p>后来参观实验室,对上交实力最强的<a href="http://ipads.se.sjtu.edu.cn/">IPADS实验室</a>很感兴趣,他们主要是弄内核方向的,而这也是我本科阶段很感兴趣的一个方向,我立刻把答辩的题目换成了IPADS实验室的题目(之前选的是一个机器学习的老师的题目).看了一篇<a href="http://wdtz.org/files/asplos200-dautenhahn.pdf">Nested Kernel</a>的论文就去答辩了,由于临时换题目,只看了两天,只能说对内嵌内核这东西有了个表面上的理解,答辩完自我感觉还行,但是最后收到的通知是待定..</p>
<p>后来陆续给上交软院打过两个电话,都说现在结果出不来.最后知道今天(9.28)我填上了清华的志愿后,才有一个老师打电话来问我还想不想去上交.无奈已经错过了,其实能去上交的顶级实验室玩自己喜欢的方向对我是很有吸引力的,如果上交早一点确定了要我,说不定我就不会去清华了.可是怎么可能事事都顺意,也正是这种挫折感让我坚定了去清华的信心.</p>
<h2>中山-CMU 电面</h2>
<p>中山大学和卡内基梅隆大学的合作项目,一年中山大学,一年卡耐基.</p>
<p>卡耐基梅隆大学应该是每个CS专业的学生的梦想吧,尤其是他们的<深入理解计算机系统>这门招牌课,我一直想去听一下.所以报了这个项目.</p>
<p>电面很简单,一群CMU的老师问了我几个问题,10分钟就结束了,由于英语说得不好,我答的也磕磕巴巴,问题问的还是很深的,比如STL里面map后的数据结构,摄像机的标定等等..要不是我选过虚拟现实这课,我可能连calibration是什么都不知道..</p>
<p>最后还是收到了offer,但是拒绝了,因为他们只肯给我985学生都有的15w入学奖学金.我希望读研不要花家里的钱,另一方面我觉得他们并没有对我很认可,或者我自负地觉得自己值得更多..</p>
<h2>上科大计算机</h2>
<p>上海科技大学,中科院刚成立的一所大学</p>
<p>我是在学校的宣讲会上面对这个大学有了解的,当时我只有北航的一个offer,就毅然决然的报了名,当时想的是拿来保底.但是这学校实际上很不错,都是一些海归的大牛当老师,最后我对象去了那里.</p>
<p>这个大学很人性,都是电面,三个老师面试,面试上科大的时候我已经”身经百战”,面试能力达到了巅峰.答得都挺好,包括美赛获奖经历,一些项目上的问题,还有专业课的知识,值得一提的是,两个老师都问了我快排的问题,在中科院计算所的笔试上还考过手写快排的问题,可见快排真的是百问不厌的经典算法,值的深入理解一下.</p>
<p>最后收到了offer,由于不是985,211,家里不让,再加上有了清华的offer,还是拒绝了</p>
<h2>清华软院</h2>
<p>我没有清华梦</p>
<p>我学生时代考不上清华,我也没想过去清华读书,但是没想到我竟然能有机会去清华读研,还是百里挑一的学硕..</p>
<p>我们学院去年有很多学长去了清华软院,所以我根据他们的经验对清华软院了解的也比较多,虽然清华软院没有夏令营,但是只要获得了复试的资格,还是很容易进去的.</p>
<p>我最终进入了复试,但是听说我们学院日语强化的第一名今年由于六级没有通过没能获得复试的资格,我的经历和其他人的经历比起来也显得不那么坎坷了.后来一比才发现,我是同行的所有软院的去清华复试的人里面成绩最差的,我没怎么紧张,毕竟奋力一搏.</p>
<p>复试当天上午机试,三道题,用VS敲,上面还有VA,我平时就用这个,环境方面没有什么问题.第一道题暴力模拟,比较简单,第二道题DFS,一个递归就可以.第三道题我做的时间比较长,最后想出来了一个动态规划的算法(这得益于前面51nod的动态规划的教程).做完了之后我没有直接离开,因为离开了我也没地方去,我就一遍一遍地看代码,没想到还真让我找到了一个小bug(将矩阵读成了方阵),后来我又坐在那里准备面试的自我介绍,这样,到最后交卷我才走.</p>
<p>面试进行的也很顺利,清华的教授们都很nice,我自我介绍的时候一直点头,尤其我说道开发的游戏和网站的时候老师眼前一亮.无奈一个老师突然问了我网络的七层模型(OSI),这个我只记得五层,就直说了五层模型,其它的问题都没啥问题.</p>
<p>后来打电话询问居然过了那边的学硕,老师说我机试做的好才给我调了的.真是瞬间感觉之前刷题的努力都没有白费</p>
<h2>其它</h2>
<p>其实还面了其它一些学校,这些面试大都没什么营养,经历也都各种各样,简单提一句.</p>
<p>北大,这个我夏令营材料就没通过,后来联系老师去面了一下,到了那里,联系的老师对我的自我介绍就不满意,倒是离我最近的老师问了我一些问题,包括支持向量是什么等等,我也都答了,后来还是没有通过.9月正式推免我又投了一次,材料还是没有通过..</p>
<p>北航,我去了北航计算机学院的夏令营,说实话这个夏令营让我感觉北航其实没我想的那么好,机试题目很简单,面试问的问题也都是一些项目经历.但是最后因为没有offer,一直拖着没给北航回复,感觉也是挺对不起这个学校的.</p>
<p>中科院计算所,这个是当时北航要确认,我有点慌神,就报了一下,但是我并不很想去这种和校园不太一样的研究所.后来收到面试通知我还是去了,面试老师问的问题五花八门,从项目经历到家庭信息,就是没问专业知识..期间老师还暗示我这个方向并不是很赚钱..后来面完了老师又让做一个笔试,题目量很大,编程要求手写快排和二分查找..不过中科院效率很高,下午就让我去签字,我跑到那边发现是要签一个保证去中科院的协议,果断放弃掉了..</p>
<hr />
<p>现在,我已经填完了推免申请,等待清华的确认,同时也在找清华的导师收留我,同时还在找实习..</p>
<p>我之前一直想着保研完了就可以放松了,但是我发现我早已停顿不下,来到了一个驿站又到了走向下一个驿站的路上..</p>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2015/08/27/reading-computer-systems-a-programmers-perspective-2/">Reading Computer Systems(A Programmer’s Perspective):2</a></h1>
<p class="meta">
<time datetime="2015-08-27T13:07:02+08:00" pubdate data-updated="true"></time>
| <a href="/blog/2015/08/27/reading-computer-systems-a-programmers-perspective-2/#comments">Comments</a>
</p>
</header>
<div class="entry-content"><h2>第五章 优化程序性能</h2>
<p>这一章主要讲的是编译器对代码的一些优化策略,包括在代码效率和代码在一些极端状况下的准确性的权衡.以及用具体的汇编代码及在机器中的实现来说明一些代码习惯的对程序效率的影响,最后介绍了一种unix环境下的程序剖析(profiling)工具GPROF.</p>
<p>优化程序的效率时,除了优化整个算法的时间复杂度,其中编译器对代码的编译也起到了至关重要的作用,而编译器除了要将代码变得更快,还需要考虑程序的正确性,开头的例子给出了一个对源代码非常明显的优化,但是编译器却不敢执行这个优化,主要原因就是他不能保证这个优化过的结果和没优化的结果是一样的,事实上,在极端情况下,优化后的代码可能会产生和原来的代码不同的结果.</p>
<p>所以,编译器的一些优化级别,需要保证对程序只使用<strong>安全</strong>的优化,也就是保证优化后的代码和之前的代码完全相同,这种保证就会使得一些明显的优化无法执行(因为无法保证极端情况下的正确性).</p>
<p>接下来以一个程序(P330)为示例,讲了几种写代码时的优化策略</p>
<h3>消除循环的低效率</h3>
<p>这个说的是可能编程中经常会遇到的问题,循环
<code>for(int i = 0;i<vec_length(v),++i)</code>
如果这么写的话,每次循环结束都会调用 <code>vec_length()</code> 这个函数来确定是否到达循环结束,对于长度不变的数据结构的遍历,每次循环结束调用的这个函数的开销是不必要的,应将其避免</p>
<h3>减少过程调用</h3>
<p>这个部分说的是尽量不要在循环中循环调用一些函数,在循环外拿到需要循环遍历的数据结构,然后再循环中直接去调用数据结构.</p>
<p>书中也提到了这种做法不太符合程序模块化的要求,只有在追求效率的代码中会用到,这种情况也应该写几行注释注明.</p>
<h3>消除不必要的存储器引用</h3>
<p>讲的是,这么写</p>
<pre><code>for(int i = 0;i<length;++i)
acc = acc OP data[i];
</code></pre>
<p>和这么写</p>
<pre><code>for(int i = 0;i<length;++i)
*dest = *dest OP data[i];
</code></pre>
<p>前者更好,因为,前者在汇编中实现可以用寄存器存储 acc ,而后者是个指针,汇编中只能用存储器实现,每次去地址再取指会浪费大量时间.</p>
<p>优化程序的两个限制:</p>
<ol>
<li>延迟界限: 从开始到结束完全完成一条指令所需要的时间决定,达到这个界限的原因是下一条指令需要上一条指令执行完毕才能执行,指令间有严格的操作顺序.</li>
<li>吞吐量界限: 指令之间可以<strong>完全流水线化(fully pipelined)</strong>,这样使得硬件的功能达到了最大的利用率,在这种情况下优化只能优化处理器功能单元的<strong>原始计算能力了</strong>.</li>
</ol>
<p>一些编译器可能做的优化</p>
<h3>循环展开</h3>
<p>就是循环每次原来读一个数,优化后每次读 k 个数,这样循环的次数就变成了 [n/k] 次,这样优化结果性能的提升得益于 <strong>减少了循环的开销工作</strong> ,比如原来累加器 iter 原来要累加 n 次,现在只要累加 [n/k] 次了, 降低了开销操作的数量.</p>
<h3>提高并行性</h3>
<p>这个比较容易理解,比如一个累加的程序,原来只有一个累加器,每次加一个数,改成并行的可以有 k 个累加器, k 个累加器同时工作肯定要比原来效率高</p>
<p>不过这里硬件会成为限制条件,后面就提到了<strong>寄存器溢出</strong>这种情况,就是累加器多得在寄存器里面存不下了,只能到栈里面存,这样又增加了存储器开销,反而会使效率下降.</p>
<h3>重新结合变换</h3>
<p>就是利用有结合律的变换,运用一下结合律,比如把下面这个</p>
<pre><code>acc = acc OP data[i] OP data[i+1]
</code></pre>
<p>变成下面这个</p>
<pre><code>acc = add OP (data[i] OP data[i+1])
</code></pre>
<p>代码层面没有改进,但是从汇编层面分析,原来每次循环在 acc 上的运算 由原来的两次变成了一次,这样就缩短了关键路径,从而提高了效率.</p>
<hr />
<p>上一章可以看到分支预测会对程序效率有很大影响,因为是一个完全投机的预测,预测错了下面所有取到的指令都应该放弃,这会造成比较大的损失.但是这也是不可避免的,文中提到了
1. 不要过分关心可预测的分支,我们预测分支往往会执行是因为,再循环中,这样的预测策略只有最后一次会失败,所以几率还是比较大的
2. 在程序猿的角度,将<strong>分支跳转指令</strong>改为<strong>条件传送指令( <code>val = exp?a:b;</code> )</strong>往往能取得比较好的效果,因为条件传送指令不会有错误的开销: <strong>在流水线中,下一条指令译码钱,上一条指令已经完成了执行操作,因此下一条如果是条件传送指令的话,刚好可以通过转发机制得到状态码.</strong></p>
<h2>加载和存储</h2>
<p>读和写都制约程序的运行效率 如下:</p>
<ol>
<li>加载相关, 循环两次之间的读有相关性,下一次的读需要上一次读出来的结果,所以下一条读的指令必须等上一次循环完全结束</li>
<li>读写相关(write/read dependency), 一个存储器读的结果依赖于一个最近的存储器写.这个是经常会遇到的问题.</li>
</ol>
<p>读写相关的解决方案 (<strong>P366</strong>):</p>
<p>在存储单元中有个<strong>存储缓冲区</strong>,包含将会写到存储单元的,但是还没完成的操作(地址,值).
每次读的时候 (<strong>load 指令</strong>)会先检查一下存储缓冲区,如果发现读的地址在存储缓冲区里面(说明呆会会被写进新值),就直接在存储缓冲区里面拿新值了.</p>
<p><em>…其实上面的操作就是转发</em></p>
<h2>最后 程序剖析(profiling)</h2>
<p>这里介绍了一种分析程序效率的工具,GPROF</p>
<ol>
<li>在编译和链接过程中加上剖析的指令
<code>gcc -o1 -pg prog.c prog</code></li>
<li>执行程序,会生成一个多余的 gmon.out 的文件
<code>./prog arguments...</code></li>
<li>使用GPROF来解析这个out文件(必须有out文件才能解析)
<code>gprof prog</code></li>
</ol>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2015/08/22/cheng-fa-ni-yuan-euclidding-li-he-zhong-guo-sheng-yu-ding-li/">乘法逆元 Euclid定理和中国剩余定理</a></h1>
<p class="meta">
<time datetime="2015-08-22T13:22:44+08:00" pubdate data-updated="true"></time>
| <a href="/blog/2015/08/22/cheng-fa-ni-yuan-euclidding-li-he-zhong-guo-sheng-yu-ding-li/#comments">Comments</a>
</p>
</header>
<div class="entry-content"><p>今天刷题的时候遇到了一道<a href="http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1079">中国剩余定理的题</a>,当年在网络安全这门课上学过这个算法,但是到现在只记得这个名字了,就回去翻课件回顾了一下,结果发现了很多知识点,就在这整理一下.</p>
<hr />
<h2>乘法逆元</h2>
<p>乘法逆元这个概念最初是在离散数学中引入的, 而在离散数学中提到的是范围更广泛的逆元. 是在代数系统里面提到的这个概念
定义如下</p>
<blockquote><p>令e为S中关于某二元运算的单位元.对于x∈S,如果存在yl（或yr）∈S使得(yl)x=e（或x(yr)=e）,则称yl(或yr)是x的左逆元(或右逆元)。若y∈S既是x的左逆元又是x的右逆元,则称y为x的逆元。如果x的逆元存在,就称x是可逆的.</p></blockquote>
<p>在这里,二元运算就是模p乘法,p就是整个集合的范围.在这里,如果w是Zp中的某个数,我们求w的乘法逆元,这里有一条定理.</p>
<blockquote><p>Zp中的任一整数w有乘法逆元当且仅当w和p互素</p></blockquote>
<p>这里可以简单证明一下必要性,w和p互素,我们可以用w乘Zp中的所有元素,得到的剩余类是Zp中所有元素的另一种排列.
以上这句话可以用反证法来证明
假设乘完得到的剩余类并不是Zp的另一种排列,说明得到的剩余类中必定有两个相同的数.设为m,则:</p>
<pre><code>k1*w = s1*p + m
k2*w = s2*p + m
</code></pre>
<p>所以</p>
<pre><code>(k1-k2)*w = (s1-s2)*p
</code></pre>
<p>因为w和p互素
(k1-k2)应该等于p,而k1,k2都小于p,得到了矛盾.得证.</p>
<p>现在知道了,如果求乘法逆元,要求这个数应该和基数p互素,下面看怎么求乘法逆元.</p>
<h2>Euclid算法</h2>
<p>Euclid的扩展算法可以用来求乘法逆元.先来看一下基本的Euclid算法.
整个算法写起来很简单</p>
<pre><code>gcd(a,b) = gcd(b,a%b)
</code></pre>
<p>证明起来也很简单,具体看<密码编码学与网络安全>P74
这里说一下扩展的Euclid用于求乘法逆元.
就是假设 gcd(a,b) = d, d 能写成 a和 b的组合形式
d = x<em>a + y</em>b
这样,当x,y互素的时候,明显d == 1,可以得到x是a的乘法逆元,y是b的乘法逆元.
具体x和y的推导计算可见<密码编码学与网络安全>p81</p>
<h2>中国剩余定理</h2>
<p>这个才是重点,首先中国剩余定理(Chinese Remainder Theorem)的意义是说明某一范围内的整数可通过它对两两互素的整数取模所得的余数来重构.</p>
<p>具体证明如下</p>
<p><img src="/images/2015-08-22.png"></p>
</div>
</article>
<article>
<header>
<h1 class="entry-title"><a href="/blog/2015/08/14/reading-computer-systems-a-programmers-perspective-1/">Reading Computer Systems(A Programmer’s Perspective):1</a></h1>
<p class="meta">
<time datetime="2015-08-14T15:37:43+08:00" pubdate data-updated="true"></time>
| <a href="/blog/2015/08/14/reading-computer-systems-a-programmers-perspective-1/#comments">Comments</a>
</p>
</header>
<div class="entry-content"><p>深入理解计算机系统这本书大二的时候就买了,因为有很多学长推荐,而且很多计算机名校也用它当<计算机组成原理>的教材.但是由于各种原因一直拖着没读,大三利用寒假读了一下,感觉受益匪浅,但是没有读完,大三下学期断断续续不仅没有继续读,还把前面读了的忘了个差不多,现在准备利用暑假读完,并记一下笔记,以防忘记.</p>
<hr />
<h2>第四章 处理器体系结构</h2>
<p>这一章主要是将前面几章的理论用于实践,通过一个相对简单的”Y86”指令集,介绍了机器代码,汇编代码之间的关系,指令流水等概念.</p>
<p>Y86指令比较简单,只实现了一些基本的指令,指令和数长无关,默认立即数都是4个字节,指令是变长的…</p>
<ul>
<li>立即数用小端(little-endian)编码,比如 0x12345 变成4字节应该是 0x00 01 23 45 但是存储到内存里面就是 0x 45 23 01 00</li>
<li>数的运算指令会设置条件码 ZF SF 和 OF (零 符号 和 溢出)</li>
<li>程序状态码 Stat 代表了程序运行状态(AOK, HLT, ADR, INS),当程序运行不是AOK时,会进入异常处理程序</li>
<li>调用一个函数先写的参数会距离栈顶更近,比如一个函数 <code>int sum(int* Start, int Count)</code> 取得传进来的指针Start值用的是 8(%ebp) 取Count值用的是 12(%ebp), 所以,调用的时候, 需要让后面的参数先入栈</li>
<li>完整的汇编代码中,开头会指示这段代码的开始地址,结尾会指示这段代码栈的栈尾地址(栈向低地址增长),整个程序就在两者之间运行,所以要保证栈不要增长的太大覆盖了程序代码</li>
<li><code>pushl %esp</code> 和 <code>popl %esp</code> 的选择
<ul>
<li><code>pushl %esp</code> : push本来就要减少栈指针esp,而push esp又要将栈指针压栈,最后的结果就有两种情况 :
<ol>
<li>压栈的是减少之后的esp</li>
<li>压栈的是原始的esp</li>
</ol>
</li>
<li><code>popl %esp</code> : 同上,有两种情况 :
<ol>
<li>esp中存的是原来的esp指向的值</li>
<li>esp中存的是增减完了的esp指向的值</li>
</ol>
</li>
</ul>
<p> 在Y86中,压入的是原始的esp,弹出的是原始的esp指向的值(具体可以看254页的分段伪代码)</p></li>
<li>存储器和适中:
<ol>
<li>时钟寄存器: 不是%esp这些寄存器,是输入值到输出值由时钟控制的一种硬件</li>
<li>随机访问存储器
<ol>
<li>寄存器文件: 里面包括8个程序寄存器(%eax,%esp),对外提供程序寄存器的读写端口</li>
<li>虚拟存储器系统:也就是内存</li>
</ol>
</li>
</ol>
</li>
</ul>
<h3>顺序实现Y86</h3>
<p>将指令分为六个阶段,每条指令顺序执行,上一条指令执行完最后一个阶段之后才会执行下一个阶段,执行效率低下.</p>
<ul>
<li>取指 : 取指令,根据PC获得icode(指令代码)ifunc(指令功能)寄存器操作码,valC(常数).</li>
<li>译码 : 通过寄存器文件及上一步的寄存器操作码得到相应寄存器的值</li>
<li>执行 : 执行需要的运算(加减,异或,与),并设置条件码</li>
<li>访存 : 访问内存,读或写,比如一些 irmovl , push(栈) 等指令会用到</li>
<li>写回 : 将在访存阶段或者执行阶段得到的值写到存储器里面,用到的硬件和译码相同,都是寄存器文件</li>
<li>更新PC : 根据指令得到下条指令的地址</li>
</ul>
<p>两条指令 : call指令运行会将下一条指令的地址压栈,方便返回
ret指令用栈顶的值来更新PC,解释了一个函数运行的经过.</p>
<p>整体执行是用时钟控制的,每次时钟由低到高都执行一个阶段.</p>
<p>寄存器文件有两个写的端口,如果想要对同一个寄存器写的话,只有有限制高的端口会执行写操作,这样做也是为了解决上面说的 <code>pushl %esp</code> 的问题,在指令执行过程中,寄存器文件的两个写端口分别分配给
1. 访存得到的 valM
2. 计算得到的 valE
而<code>pushl %esp</code> 指令刚好这两个都要写esp ,所以需要制定优先级,具体的优先级不同的编码实现不同.</p>
<h3>流水线Y86</h3>
<p>书中对流水线的解释很到位</p>
<blockquote><p>…(顾客点餐)通常都会允许多个顾客同时经过系统,而不是要等到一个用户完成了所有从头到尾的过程才让下一个开始.</p></blockquote>
<p>当某些流水阶段理解晦涩时,可以对比顾客点餐的例子.我是这样理解的: 每个阶段每个时钟都执行不同的指令,比如取值,每个时钟取一条,比如译码,每个时钟译码一条..</p>
<p>使用流水线来处理指令需要流水线寄存器,就是用于每个阶段之间存储的硬件,上面存储的是这个阶段之前,这个阶段需要执行的指令所需的值.
比如访存流水线寄存器(M)里面存储了访存需要的地址,以及上一步运算得到的状态码等等信息.</p>
<p>在276页中的 E寄存器下面可以看到一个叫 <code>Select A</code> 的硬件,它是为了节省存储空间出现的, 在流水线系统中, value A将不止用来存储在寄存器A中得到的值,还用来存储
1. Jxx 不需要跳转时的 valP
2. call 的 valP (需要将本来的下一条指令的地址压栈)
3. irmovl 中本来就需要存的 valA
由于各个指令并不冲突,所以可以共享存储..具体用操作码来区分.</p>