-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
1520 lines (1269 loc) · 158 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>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
<!-- hexo-inject:begin --><!-- hexo-inject:end --><meta charset="utf-8">
<title>DongXuehui's Blog</title>
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta name="description" content="I am willing to do anything but ordinary.">
<meta property="og:type" content="website">
<meta property="og:title" content="DongXuehui's Blog">
<meta property="og:url" content="http://dongxh.cn/index.html">
<meta property="og:site_name" content="DongXuehui's Blog">
<meta property="og:description" content="I am willing to do anything but ordinary.">
<meta property="og:locale" content="zh-CN">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="DongXuehui's Blog">
<meta name="twitter:description" content="I am willing to do anything but ordinary.">
<link rel="alternate" href="/atom.xml" title="DongXuehui's Blog" type="application/atom+xml">
<link rel="icon" href="/favicon.png">
<link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
<link rel="stylesheet" href="/css/style.css"><!-- hexo-inject:begin --><!-- hexo-inject:end -->
</head>
</html>
<body>
<!-- hexo-inject:begin --><!-- hexo-inject:end --><div id="container">
<div id="wrap">
<header id="header">
<div id="banner"></div>
<div id="header-outer" class="outer">
<div id="header-title" class="inner">
<h1 id="logo-wrap">
<a href="/" id="logo">DongXuehui's Blog</a>
</h1>
</div>
<div id="header-inner" class="inner">
<nav id="main-nav">
<a id="main-nav-toggle" class="nav-icon"></a>
<a class="main-nav-link" href="/">Home</a>
<a class="main-nav-link" href="/archives">Archives</a>
</nav>
<nav id="sub-nav">
<a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
<a id="nav-search-btn" class="nav-icon" title="搜索"></a>
</nav>
<div id="search-form-wrap">
<form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit"></button><input type="hidden" name="sitesearch" value="http://dongxh.cn"></form>
</div>
</div>
</div>
</header>
<div class="outer">
<section id="main">
<article id="post-迭代器和生成器讲解" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2020/12/31/迭代器和生成器讲解/" class="article-date">
<time datetime="2020-12-31T08:47:35.000Z" itemprop="datePublished">2020-12-31</time>
</a>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2020/12/31/迭代器和生成器讲解/">迭代器和生成器讲解</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="迭代器和生成器讲解"><a href="#迭代器和生成器讲解" class="headerlink" title="迭代器和生成器讲解"></a>迭代器和生成器讲解</h1><p>深入浅出地讲一下生成器和迭代器；</p>
<h2 id="迭代器协议"><a href="#迭代器协议" class="headerlink" title="迭代器协议"></a>迭代器协议</h2><ol>
<li>迭代器协议就是指：对象需要提供next方法，它要么返回迭代中的下一项，要么就引起一个StopIteration异常，以终止迭代；</li>
<li>可迭代对象就是：实现了迭代器协议的对象</li>
<li>协议是一种约定，可迭代对象实现迭代协议，python内置工具（如for循环，min，max，sum函数等）通过协议访问对象。</li>
</ol>
<p>举个例子，python中for循环不仅能来遍历列表，还能用来遍历各种各样的对象，这是因为能够遍历各种各样的对象实现了迭代器协议，for循环并不知道他遍历的对象是个什么东西，它只要管用利用迭代器协议访问遍历对象即可。（列表是可迭代对象，整数不是）</p>
<h2 id="生成器"><a href="#生成器" class="headerlink" title="生成器"></a>生成器</h2><p>python使用生成器对延时操作进行了很好的支持。所谓延时操作，指的是在需要的时候产生结果，而不是立即产生结果。</p>
<p>python有两种不同的方式提供生成器：</p>
<ol>
<li>生成器函数：常规函数定义，但是，使用yield语句而不是return语句返回结果。yield语句一次返回一个结果，在每个结果中间，挂起函数的状态，以便下次从它离开的地方继续执行。</li>
<li>生成器表达式：类似于列表推导，但是，生成器返回按需产生结果的一个对象，而不是一次构建一个结果列表</li>
</ol>
<p>举两个例子：</p>
<p>1.使用生成器函数返回自然数平方：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">gensquares</span><span class="params">(N)</span>:</span></span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> range(N):</span><br><span class="line"> <span class="keyword">yield</span> i ** <span class="number">2</span> <span class="comment"># 因为使用的是生成器，所以for循环语句中可以直接</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span> item <span class="keyword">in</span> gensquares(<span class="number">5</span>):<span class="comment"># 根据上面生成器延时操作理解，并不是一次性执行完gensquares(5)</span></span><br><span class="line"> print(item,end=<span class="string">' '</span>) <span class="comment"># 而是利用yield语句的功能，生成一个 -> 遍历一个 -> 输出一个</span></span><br><span class="line"></span><br><span class="line">结果：</span><br><span class="line"><span class="number">0</span> <span class="number">1</span> <span class="number">4</span> <span class="number">9</span> <span class="number">16</span></span><br></pre></td></tr></table></figure>
<p>2.使用普通函数：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">gensquares</span><span class="params">(N)</span>:</span></span><br><span class="line"> res = []</span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> range(N):</span><br><span class="line"> res.append(i**<span class="number">2</span>)</span><br><span class="line"> <span class="keyword">return</span> res</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span> item <span class="keyword">in</span> gensquares(<span class="number">5</span>):<span class="comment"># 返回了一个列表（也含有迭代器协议，可以用for循环遍历）</span></span><br><span class="line"> print(item, end=<span class="string">' '</span>)</span><br><span class="line"></span><br><span class="line">结果：</span><br><span class="line"><span class="number">0</span> <span class="number">1</span> <span class="number">4</span> <span class="number">9</span> <span class="number">16</span></span><br></pre></td></tr></table></figure>
<p>3.错误例子示范（将1中yield换成return）：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">gensquares</span><span class="params">(N)</span>:</span></span><br><span class="line"> <span class="keyword">for</span> i <span class="keyword">in</span> range(N):</span><br><span class="line"> <span class="keyword">return</span> i ** <span class="number">2</span> <span class="comment"># 将yield换成return</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span> item <span class="keyword">in</span> gensquares(<span class="number">5</span>):</span><br><span class="line"> print(item,end=<span class="string">' '</span>)</span><br><span class="line"></span><br><span class="line">结果：</span><br><span class="line">Traceback (most recent call last):</span><br><span class="line"> <span class="keyword">for</span> item <span class="keyword">in</span> gensquares(<span class="number">5</span>):</span><br><span class="line">TypeError: <span class="string">'int'</span> object <span class="keyword">is</span> <span class="keyword">not</span> iterable</span><br></pre></td></tr></table></figure>
<p>4.生成器表达式：</p>
<p>使用列表推导，会一次性产生所有结果：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">>>> </span>squares = [x*x <span class="keyword">for</span> x <span class="keyword">in</span> range(<span class="number">5</span>)]</span><br><span class="line"><span class="meta">>>> </span>squares</span><br><span class="line">[<span class="number">0</span>, <span class="number">1</span>, <span class="number">4</span>, <span class="number">9</span>, <span class="number">16</span>]</span><br></pre></td></tr></table></figure>
<p>将列表推导的中括号[]，换成小括号()，就是一个生成器表达式：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">>>> </span>squares = (x*x <span class="keyword">for</span> x <span class="keyword">in</span> range(<span class="number">5</span>))</span><br><span class="line"><span class="meta">>>> </span>squares</span><br><span class="line"><generator object <genexpr> at <span class="number">0x7ff64f9810b0</span>></span><br><span class="line"><span class="meta">>>> </span>next(squares)</span><br><span class="line"><span class="number">0</span></span><br><span class="line"><span class="meta">>>> </span>next(squares)</span><br><span class="line"><span class="number">1</span></span><br><span class="line"><span class="meta">>>> </span>next(squares)</span><br><span class="line"><span class="number">4</span></span><br><span class="line"><span class="meta">>>> </span>next(squares)</span><br><span class="line"><span class="number">9</span></span><br><span class="line"><span class="meta">>>> </span>next(squares)</span><br><span class="line"><span class="number">16</span></span><br><span class="line"><span class="meta">>>> </span>next(squares)</span><br><span class="line">Traceback (most recent call last):</span><br><span class="line"> File <span class="string">"<stdin>"</span>, line <span class="number">1</span>, <span class="keyword">in</span> <module></span><br><span class="line">StopIteration</span><br><span class="line"><span class="meta">>>> </span>list(squares)</span><br><span class="line">[]</span><br></pre></td></tr></table></figure>
<p>顺便说一句list函数，对字符串可以转化为列表，对元组也可以转化为列表，对生成器则是将还未生成的剩下的数打包成列表。</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">>>> </span>squares = (x*x <span class="keyword">for</span> x <span class="keyword">in</span> range(<span class="number">5</span>))</span><br><span class="line"><span class="meta">>>> </span>next(squares)</span><br><span class="line"><span class="number">0</span></span><br><span class="line"><span class="meta">>>> </span>next(squares)</span><br><span class="line"><span class="number">1</span></span><br><span class="line"><span class="meta">>>> </span>list(squares)</span><br><span class="line">[<span class="number">4</span>, <span class="number">9</span>, <span class="number">16</span>]</span><br></pre></td></tr></table></figure>
<p>================</p>
<p>python不只是在for循环里面使用迭代器协议，大部分的内置函数，也是使用迭代器协议访问对象的。例如，sum函数，该函数使用迭代器协议访问对象，而生成器实现了迭代器协议，所以可以用生成器表达式计算：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">>>> </span>sum(x**<span class="number">2</span> <span class="keyword">for</span> x <span class="keyword">in</span> range(<span class="number">4</span>))</span><br></pre></td></tr></table></figure>
<p>而不用先构造一个列表：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">>>> </span>sum([x**<span class="number">2</span> <span class="keyword">for</span> x <span class="keyword">in</span> range(<span class="number">4</span>)])</span><br></pre></td></tr></table></figure>
<p>插一嘴，range和xrange的区别就不多说了，python3里面已经去掉了xrange，全部用range代替</p>
<p>===============</p>
<h2 id="总结生成器"><a href="#总结生成器" class="headerlink" title="总结生成器"></a>总结生成器</h2><ol>
<li>语法上和函数类似：生成器函数和常规函数几乎是一样的。它们都是用def语句定义，差别在于生成器使用yield语句返回一个值，而常规函数使用return语句返回一个值</li>
<li>自动实现迭代器协议：对于生成器，python会自动实现迭代器协议，以便应用到迭代背景中。由于生成器自动实现了迭代器协议，所以，我们可以调用它的next方法，并且，在没有值可以返回的时候，生成器自动产生StopIteration异常</li>
<li>状态挂起：生成器使用yield语句返回一个值。yield语句挂起该生成器函数的状态，保留足够的信息，以便之后从它离开的地方继续执行下一行</li>
</ol>
<h2 id="注意事项"><a href="#注意事项" class="headerlink" title="注意事项"></a>注意事项</h2><ol>
<li>生成器只能遍历一次</li>
</ol>
</div>
<footer class="article-footer">
<a data-url="http://dongxh.cn/2020/12/31/迭代器和生成器讲解/" data-id="ckjcmdb8d000k03lkx4dv50aq" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/python3/">python3</a></li></ul>
</footer>
</div>
</article>
<article id="post-OS-同步、通信与死锁（1）-并发进程" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2020/04/30/OS-同步、通信与死锁（1）-并发进程/" class="article-date">
<time datetime="2020-04-30T08:54:50.000Z" itemprop="datePublished">2020-04-30</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/Operating-System/">Operating System</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2020/04/30/OS-同步、通信与死锁（1）-并发进程/">OS--同步、通信与死锁（1）_并发进程</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="OS—同步、通信与死锁（1）-并发进程"><a href="#OS—同步、通信与死锁（1）-并发进程" class="headerlink" title="OS—同步、通信与死锁（1）_并发进程"></a>OS—同步、通信与死锁（1）_并发进程</h1><h3 id="顺序程序设计"><a href="#顺序程序设计" class="headerlink" title="顺序程序设计"></a>顺序程序设计</h3><p>传统的顺序程序设计具有以下特点：</p>
<ol>
<li>执行的顺序性</li>
<li>环境的封闭性：</li>
<li>结果的确定性</li>
<li>过程的可再现性</li>
</ol>
<p>程序执行的最终输出只与初始输入数据有关，而与时间无关。对于程序的编制和调试来说有很大的方便性，但是缺点就是效率不高。</p>
<h3 id="并发程序设计"><a href="#并发程序设计" class="headerlink" title="并发程序设计"></a>并发程序设计</h3><p>操作系统的基本控制都是围绕着进程展开的，其中的复杂性是由于支持并发和并发机制引起的。</p>
<p>对于<strong>单核操作系统</strong>来说，<strong>宏观上</strong>，并发性反映了一个时间段内几个程序都处在运行但运行尚未结束的状态；<strong>微观上</strong>，任一时刻仅有一个程序的一个操作在处理器上执行。所以对于单核操作系统来说，并发的实质是处理器在几个程序之间的多路复用。</p>
<p>程序的并发执行产生了资源共享的需求</p>
<p><img src="1.png" style="zoom:40%;"></p>
<h4 id="并发进程的特性"><a href="#并发进程的特性" class="headerlink" title="并发进程的特性"></a>并发进程的特性</h4><p>并发的进程有可能是无关的，也有可能是交互的。交互的进程表示它们公用一些变量集合，一个进程的执行可能会影响到其他的进程的执行结果，交互的进程之间具有制约关系。</p>
<p>因此进程之间的交互必须是under control，否则会出现不正确的计算结果。</p>
<p>所以第一个特性就是失去了程序的封闭性，<strong>如果程序执行的结果是一个与时间无关的函数，即具有封闭性。</strong>并发进程程序执行的结果不仅依赖于程序的初始条件，还依赖于程序执行时的相对速度。</p>
<p>并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为<strong>Bernstein条件</strong>，假设：</p>
<p> $R(P_i)=\{a_1,a_2,\dots,a_n\}$，程序$P_i$在执行期间所<strong>引用</strong>的变量集</p>
<p> $W(P_i)=\{a_1,a_2,\dots,a_n\}$，程序$P_i$在执行期间所<strong>改变</strong>的变量集</p>
<p> 若进程$P_1$和$P_2$满足条件$\{R(P_1)\cap W(P_2)\}\cup\{R(P_2)\cap W(P_1)\}\cup\{W(P_1)\cap W(P_2)\}\}=\varnothing$,则表示并发进程的执行与时间无关.</p>
<p>$\{R(P_1)\cap W(P_2)\}\cup\{R(P_2)\cap W(P_1)\}=\varnothing$，表明一个程序在两次读操作之间存储单元的数据不会被改变；</p>
<p>$\{W(P_1)\cap W(P_2)\}\}=\varnothing$，表明程序的写操作结果不会丢失。</p>
<p>因此，满足Bernstein条件，并发执行 程序就可以保持封闭性和可再现性。</p>
<h4 id="与时间有关的错误"><a href="#与时间有关的错误" class="headerlink" title="与时间有关的错误"></a>与时间有关的错误</h4><p>交互的并发程序的结果不可预测性的根本在于，它们的执行时的相对速度是不可预测的。影响交互进程的速率的因素有：处理器处理中断的方式，处理器调度的策略，还受到其他进程的影响等。</p>
<p>与时间有关的错误就是与相对执行速度相关的错误，有两种：1.结果不唯一；2.永远等待。</p>
<p><strong>结果不唯一</strong></p>
<p>飞机售票问题</p>
<p><img src="2.png" style="zoom:30%;"></p>
<p><img src="3.png" style="zoom:30%;"></p>
<p><strong>永远等待</strong></p>
<p>内存资源管理问题</p>
<p><img src="4.png" style="zoom:50%;"></p>
<h3 id="进程的交互：竞争和协作"><a href="#进程的交互：竞争和协作" class="headerlink" title="进程的交互：竞争和协作"></a>进程的交互：竞争和协作</h3><p>进程之间的两种基本关系：竞争与协作。</p>
<p><strong>竞争关系</strong></p>
<p>引发两个控制问题：</p>
<ol>
<li><p>死锁(deadlock)</p>
</li>
<li><p>饥饿(starvation)</p>
<p>进程互斥（mutual exclusion):指的是若干进程因相互争夺独占型资源而产生的竞争制约关系。</p>
</li>
</ol>
<p><strong>协作关系</strong></p>
<p>进程之间的协作可以是<strong>间接协作</strong>，双方不知道对方的名字，如通过访问共享资源进行松散式协作；可以是通过通信机制的紧密协作，允许进程协同工作有利于共享信息，加快计算速度等。</p>
<p> 进程同步（synchronization）:是指为了完成共同任务的并发进程基于某个条件来协调其活动，因为需要在某些位置上排定执行的先后次序而等待，传递信号或者消息所产生的协作制约关系。</p>
</div>
<footer class="article-footer">
<a data-url="http://dongxh.cn/2020/04/30/OS-同步、通信与死锁（1）-并发进程/" data-id="ckjcmdb8i000o03lkfms2t88c" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/操作系统/">操作系统</a></li></ul>
</footer>
</div>
</article>
<article id="post-OS-处理器管理（5）-处理器调度" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2020/04/23/OS-处理器管理（5）-处理器调度/" class="article-date">
<time datetime="2020-04-23T04:19:04.000Z" itemprop="datePublished">2020-04-23</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/Operating-System/">Operating System</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2020/04/23/OS-处理器管理（5）-处理器调度/">OS--处理器管理（5）_处理器调度</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="OS—处理器管理（5）-处理器调度"><a href="#OS—处理器管理（5）-处理器调度" class="headerlink" title="OS—处理器管理（5）_处理器调度"></a>OS—处理器管理（5）_处理器调度</h1><p>知识点：</p>
<ul>
<li>处理器调度层次</li>
<li>选择调度算法的原则</li>
<li>作业管理与调度</li>
<li>低级调度功能和类型</li>
<li>作业调度和低级调度算法</li>
</ul>
<h2 id="处理器调度层次"><a href="#处理器调度层次" class="headerlink" title="处理器调度层次"></a>处理器调度层次</h2><p>可分为三级：高级调度，中级调度，低级调度</p>
<p><strong>高级调度</strong>（high level scheduling）</p>
<p>又称作业调度，长程调度。高级调度将控制多道程序的道数，被选择进入内存的作业越多，每个作业获得的CPU时间就越少。当有作业执行完毕并撤离时，作业调度会选择一个或者多个作业补充进入内存。此外，CPU空闲时间超过一定阈值时，系统也会引出作业调度选择后备作业。</p>
<p><strong>中级调度</strong>（medium level scheduling）</p>
<p>又称平衡调度，中程调度。中程调度将控制内存中容纳的进程数，并完成外存和内存中的进程对换工作。内存资源紧张，则换出暂时不能运行的进程（<strong>挂起状态</strong>）；内存资源富裕且具备运行条件，重新调回内存。</p>
<p>起到短期均衡系统负载的作用，充分提高内存利用率和系统吞吐率。</p>
<p><strong>低级调度</strong>（low level scheduling）</p>
<p>又称进程/线程调度，短程调度，处理器调度。根据具体算法决定<strong>就绪队列</strong>中哪个进程/线程获得处理器。<strong>低级调度是操作系统最核心部分</strong>，其调度策略的优劣直接影响系统性能。这部分代码<strong>常驻内存</strong>。</p>
<p>高级调度和低级调度为一般操作系统所必需（两级调度模型）。中级调度存在于功能完善的有更高效率追求的系统中（三级调度模型）。</p>
<p><img src="1.png" style="zoom:50%;"></p>
<p><img src="2.png" style="zoom:34.33%;"></p>
<h2 id="选择调度算法原则"><a href="#选择调度算法原则" class="headerlink" title="选择调度算法原则"></a>选择调度算法原则</h2><p>下面五条选择调度算法原则中，前三条是面向系统的性能指标，后两条是面向用户的性能指标。</p>
<ol>
<li>资源利用率<br>让CPU和各种资源尽可能并行工作，使得资源的利用率尽可能提高。在一定的I/O操作等待时间的比率下，运行程序的道数越多，CPU空闲时间所占的百分比越低。</li>
<li>吞吐率<br>单位时间内，CPU处理作业的个数。显然，所处理的长作业多则吞吐率低，短作业多则吞吐率高。</li>
<li>公平性<br>确保每个进程都能获得合理的CPU份额和其他资源份额，不会出现<strong>饥饿现象</strong>。</li>
<li>响应时间<br>交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。使交互式用户的响应时间尽可能短，或尽快处理实时任务。这是分时系统和实时系统衡量调度性能的一个重要指标。</li>
<li>周转时间<br>批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间，应使作业周转时间或平均作业周转时间尽可能短。这是批处理系统衡量调度性能的一个重要指标</li>
</ol>
<p>批处理系统的调度性能用<strong>作业周转时间</strong>和<strong>带权作业周转时间</strong>来衡量。作业周转时间$t_i=t_f-t_s$(等于完成时间减去作业提交时间)。实际上也等于作业在系统中<strong>等待时间</strong>和<strong>运行时间</strong>$t_k$之和。</p>
<p>平均作业周转时间$T=(\sum_{i=1}^nt_i)/n$ ，作业的带权周转时间为$w_i=t_i/t_k$ ，平均带权周转时间$W = \sum^n_{i=1}w_i/n$。</p>
<p><strong>平均作业周转时间</strong>用来衡量不同调度算法对同一作业流的调度性能。</p>
<p><strong>平均带权作业周转时间</strong>用来衡量同一调度算法对不同作业流的调度性能。</p>
<p>举个例子：</p>
<p><img src="4.png" style="zoom:30%;"></p>
<p>该例子调度算法为FirstComeFirstServe,后面有介绍。</p>
<h2 id="作业管理与调度"><a href="#作业管理与调度" class="headerlink" title="作业管理与调度"></a>作业管理与调度</h2><h4 id="作业和进程的关系"><a href="#作业和进程的关系" class="headerlink" title="作业和进程的关系"></a>作业和进程的关系</h4><p>一个作业（job）可以分为编译，链接，装载和运行四个作业步（job step）。当一个作业被作业调度选中进入内存并投入运行时，操作系统将为此用户作业生成相应的用户进程完成计算任务。进程是已提交完毕并选中运行的作业（程序）的执行实体，也是为了完成作业任务向系统申请和分配资源的基本单位。</p>
<p>综上，<strong><u>作业是任务实体，进程是完成任务的执行实体</u>。</strong></p>
<h4 id="作业管理与调度-1"><a href="#作业管理与调度-1" class="headerlink" title="作业管理与调度"></a>作业管理与调度</h4><h5 id="批作业的组织和管理"><a href="#批作业的组织和管理" class="headerlink" title="批作业的组织和管理"></a>批作业的组织和管理</h5><p><strong>批作业的输入</strong>：采用脱机控制方式，由SPOOLing系统成批接收并控制作业输入，并将其存放在输入井，然后在系统的管理和控制下被调度和执行。</p>
<p><strong>批作业的建立</strong>：每个作业建立一个作业建立一个作业控制块（Job Control Block，JCB），所有的JCB组成作业表。JCB主要包括作业情况，资源需求，资源使用情况等。</p>
<p><strong>批作业的调度</strong>：指按照某种算法从后备作业队列中选择部分作业进入内存运行，当作业运行结束时做好善后工作。1.选择任务（由作业调度算法决定）；2.分配资源；3.创建进程；4.作业控制；5.后续处理；</p>
<p><img src="3.png" style="zoom:50%;"></p>
<h5 id="交互式作业的组织和管理"><a href="#交互式作业的组织和管理" class="headerlink" title="交互式作业的组织和管理"></a>交互式作业的组织和管理</h5><p>分时系统的作业就是用户的一次上机交互过程，可认为终端进程的创建是一个交互型作业的开始，退出命令运行结束代表用户交互型作业的中止。</p>
<h2 id="低级调度的功能和类型"><a href="#低级调度的功能和类型" class="headerlink" title="低级调度的功能和类型"></a>低级调度的功能和类型</h2><p>调度器（dispatcher）</p>
<p>低级调度的主要功能：调度和分派</p>
<ul>
<li>调度：实现调度策略，确定就绪进程/线程竞争使用处理器的次序的裁决原则，即进程/线程何时应放弃CPU和选择哪个来执行；</li>
<li>分派：实现调度机制，确定如何时分复用CPU，处理上下文交换细节，完成进程/线程和CPU的绑定和放弃的实际工作。</li>
</ul>
<p>低级调度机制由两个程序模块组成：</p>
<ul>
<li>排队程序</li>
<li>分派程序</li>
</ul>
<p>基本类型：</p>
<ul>
<li>第一类—剥夺式<ul>
<li>又称抢占式。当进程/线程正在处理器上运行时，系统可根据规定的原则剥夺分配给此进程/线程的处理器，并将其移入就绪队列，选择其他进程/线程运行。</li>
<li>两种处理器剥夺原则：<ul>
<li>高优先级进程/线程可剥夺低优先级进程/线程</li>
<li>当运行进程/线程时间片用完后被剥夺。</li>
</ul>
</li>
</ul>
</li>
<li>第二类—非剥夺式<ul>
<li>又称非抢占式。一旦某个进程/线程开始运行后便不再让出处理器，除非该进程/线程运行结束或主动放弃处理器，或因发生某个事件而不能继续执行。</li>
</ul>
</li>
</ul>
<h2 id="作业调度过程中的不同时间段"><a href="#作业调度过程中的不同时间段" class="headerlink" title="作业调度过程中的不同时间段"></a>作业调度过程中的不同时间段</h2><p><strong>Arrival Time:</strong> <em>Time at which the process arrives in the ready queue.</em>提交时间</p>
<p><strong>Completion Time:</strong> <em>Time at which process completes its execution.</em>完成时间</p>
<p><strong>Burst Time:</strong> <em>Time required by a process for CPU execution.</em>运行时间。</p>
<p><strong>Turn Around Time:</strong> <em>Time Difference between completion time and arrival time.Turn Around Time = Completion Time – Arrival Time.</em>周转时间</p>
<p><strong>Waiting Time(W.T):</strong> <em>Time Difference between turn around time and burst time.</em><br><em>Waiting Time = Turn Around Time – Burst Time</em>等待时间</p>
<h2 id="作业调度和低级调度算法"><a href="#作业调度和低级调度算法" class="headerlink" title="作业调度和低级调度算法"></a>作业调度和低级调度算法</h2><h3 id="先来先服务算法（First-Come-First-Serve）"><a href="#先来先服务算法（First-Come-First-Serve）" class="headerlink" title="先来先服务算法（First Come First Serve）"></a>先来先服务算法（First Come First Serve）</h3><p>按照作业进入系统后备队列的先后次序来挑选作业，先进入系统的作业优先被挑选进入内存。 </p>
<p>再次说明，周转时间等于完成时间减去提交时间，带权周转时间等于周转时间除以运行时间。</p>
<p>FCFS算法平均周转时间与作业提交顺序有关，一般是运行时间短的先提交平均周转时间低。</p>
<h3 id="最短作业优先算法（Shortest-Job-First"><a href="#最短作业优先算法（Shortest-Job-First" class="headerlink" title="最短作业优先算法（Shortest Job First)"></a>最短作业优先算法（Shortest Job First)</h3><p>SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。</p>
<p>算法易于实现，效率不高，主要弱点是忽视了作业等待时间。会出现饥饿现象。</p>
<p>SJF的平均作业周转时间比FCFS要小，故它的调度性能比FCFS好。</p>
<p>实现SJF调度算法需要知道作业所需运行时间，否则调度就没有依据，要精确知道一个作业的运行时间是办不到的。</p>
<p>估计下一个最短CPU运行时间estimate shortest next CPU burst time 的方法：</p>
<script type="math/tex; mode=display">
\tau_{n+1}=\alpha t_n+(1-\alpha)\tau_n</script><p>$t_n$是进程/线程最近一个CPU周期长度（最近信息），$\tau_n$是估算的第n个CPU周期值（历史信息）。</p>
<h3 id="最短剩余时间优先算法（Shortest-Remaining-Time-First）"><a href="#最短剩余时间优先算法（Shortest-Remaining-Time-First）" class="headerlink" title="最短剩余时间优先算法（Shortest Remaining Time First）"></a>最短剩余时间优先算法（Shortest Remaining Time First）</h3><p>SRTF把SJF算法改为抢占式的。一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业。称最短剩余时间优先算法。</p>
<p>此算法不但适用于JOB调度，同样也适用于进程调度。</p>
<h3 id="最高响应比优先算法（Highest-Response-Ratio-Next）"><a href="#最高响应比优先算法（Highest-Response-Ratio-Next）" class="headerlink" title="最高响应比优先算法（Highest Response Ratio Next）"></a>最高响应比优先算法（Highest Response Ratio Next）</h3><p>FCFS与SJF是片面的调度算法。FCFS只考虑作业等候时间而忽视了作业的计算时问，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间。</p>
<p>HRRN是介乎这两者之间的折衷算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。 </p>
<p>响应比的定义： 响应比 ＝1+已等待时间/估计运行时间；</p>
<p>短作业容易得到较高响应比，长作业等待时间足够长后，也将获得足够高的响应比，饥饿现象不会发生。</p>
<p>HRRN算法举例：</p>
<p> 四个作业<strong>到达系统时间/所需CPU时间</strong>:作业1-0/20，作业2-5/15，作业3-10 /5，作业4- 15/ 10。</p>
<ul>
<li>SJF调度顺序为作业1、3、4、2，平均作业周转时间T=25， 平均带权作业周转时间W=2.25 。</li>
<li>FCFS调度顺序为作业1、2、3、4，平均作业周转时间T=28.75， 平均带权作业周转时间W=3.125 。</li>
<li>HRRF调度顺序为作业1、3、2、4，平均作业周转时间T=26.25， 平均带权作业周转时间W=2.46 。</li>
</ul>
<p><img src="5.png" style="zoom:30%;"></p>
<h3 id="优先级调度算法"><a href="#优先级调度算法" class="headerlink" title="优先级调度算法"></a>优先级调度算法</h3><p>优先级通常用0～4095的整数表示，这些整数称为优先数。Linux中优先数越小吗，优先级越高，有些系统则相反。</p>
<ul>
<li>静态优先数法</li>
</ul>
<p><img src="6.png" style="zoom:50%;"></p>
<ul>
<li>动态优先数法<ol>
<li>根据<strong>进程占有CPU时间</strong>多少来决定,当进程占有CPU时间愈长,那么，在它被阻塞之后再次获得调度的优先级就越低，反之,进程获得调度的可能性越大;</li>
<li>根据<strong>进程等待CPU时间</strong>多少来决定,当进程在就绪队列中等待时间愈长,那么，在它被阻塞之后再次获得调度的优先级就越高，反之,进程获得调度的可能性越小。</li>
</ol>
</li>
</ul>
<h3 id="时间片轮转调度算法（Round-Robin）"><a href="#时间片轮转调度算法（Round-Robin）" class="headerlink" title="时间片轮转调度算法（Round Robin）"></a>时间片轮转调度算法（Round Robin）</h3><p>时间片调度：调度程序每次把CPU分配给就绪队列首进程使用一个时间片，例如100ms，就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。</p>
<p>轮转策略可防止那些很少使用外围设备的进程过长的占用处理器而使得要使用外围设备的那些进程没有机会去启动外围设备。</p>
<ul>
<li>时间片长度的确定<ul>
<li>时间片长度变换的影响<ul>
<li>过长：退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。</li>
<li>过短：大多数进程/线程都不能在一个时间片内运行完成，上下文切换次数增加，响应时间长。</li>
</ul>
</li>
<li>对响应时间的要求<ul>
<li>T(响应时间)=N(进程数目)*q(时间片)</li>
</ul>
</li>
<li>时间片长度的影响因素<ul>
<li>就绪进程的数目：数目越多，时间片越小（当响应时间一定时）</li>
<li>系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长。</li>
</ul>
</li>
</ul>
</li>
</ul>
<h3 id="多级反馈队列调度算法（Multi-Level-Feedback-Queue，MLFQ）"><a href="#多级反馈队列调度算法（Multi-Level-Feedback-Queue，MLFQ）" class="headerlink" title="多级反馈队列调度算法（Multi-Level Feedback Queue，MLFQ）"></a>多级反馈队列调度算法（Multi-Level Feedback Queue，MLFQ）</h3><p>又称反馈循环队列或多队列策略。主要思想是：由系统建立多个就绪队列，每个队列对应于一个优先级，第一个队列的优先级最高，第二个其次，优先级逐个降低。较高优先级队列的进程/线程分配较短的时间片，较低优先级相反，最后一个队列进程/线程按照FCFS算法原则排队。</p>
<p>处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。</p>
<p><img src="7.png" style="zoom:50%;"></p>
<p>该算法有较好的性能，能满足各类应用需要。</p>
<p>但是MLFQ调度算法会导致“饥饿”问题。假如有一个长作业进入系统，它最终必将移入优先级最低的就绪队列，若其后有源源不断的短作业进入系统，且形成稳定的作业流，则长作业一直等待，陷入“饥饿”状态。解决问题的一种有效方法是对于低优先级的队列中等待时间足够长的进程提升其优先级。</p>
</div>
<footer class="article-footer">
<a data-url="http://dongxh.cn/2020/04/23/OS-处理器管理（5）-处理器调度/" data-id="ckjcmdbcp001m03lkoz4enlp1" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/操作系统/">操作系统</a></li></ul>
</footer>
</div>
</article>
<article id="post-OS-处理器管理（4）-线程及其实现" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2020/04/03/OS-处理器管理（4）-线程及其实现/" class="article-date">
<time datetime="2020-04-03T13:10:44.000Z" itemprop="datePublished">2020-04-03</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/Operating-System/">Operating System</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2020/04/03/OS-处理器管理（4）-线程及其实现/">OS--处理器管理（4）_线程及其实现</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="OS—处理器管理（4）-线程及其实现"><a href="#OS—处理器管理（4）-线程及其实现" class="headerlink" title="OS—处理器管理（4）_线程及其实现"></a>OS—处理器管理（4）_线程及其实现</h1><p>知识点：</p>
<ul>
<li>引入多线程的动机</li>
<li>多线程环境中的进程和线程</li>
<li>线程的实现</li>
</ul>
<h2 id="引入多线程的动机"><a href="#引入多线程的动机" class="headerlink" title="引入多线程的动机"></a>引入多线程的动机</h2><p>在引入进程的概念后，又引入线程的概念，目的是为了减少程序并发执行时所付出的时空开销，使得并发颗粒更细，并发性更好。</p>
<p>引入线程的基本思路是：把进程的两项功能<strong>独立分配资源</strong>和<strong>被调度分派执行</strong>分离开来。</p>
<p><strong>独立分配资源</strong>：任由进程完成，作为系统资源分配和保护的独立单位，无须频繁切换。</p>
<p><strong>被调度分派执行</strong>：交给称为线程的实体来完成，线程作为系统调度和分派的基本单位，会被频繁地调度和切换。</p>
<p><strong>多线程结构进程的优点：</strong></p>
<ol>
<li>快速线程切换。同一进程中的多线程切换只需要改变堆栈和寄存器，地址空间不变。</li>
<li>通信易于实现。自动共享进程的内存和文件，线程可自由访问全局数据，实现数据共享十分方便，线程通信相对简单不必经过内核。</li>
<li>减少管理开销。线程创建和撤销工作比进程少很多，并且无须再分配存储空间和各种资源。</li>
<li>并发程度提高。</li>
</ol>
<h2 id="多线程环境中的进程和线程"><a href="#多线程环境中的进程和线程" class="headerlink" title="多线程环境中的进程和线程"></a>多线程环境中的进程和线程</h2><h4 id="多线程"><a href="#多线程" class="headerlink" title="多线程"></a>多线程</h4><p>系统调度的基本单位是线程而不是进程,每当创建一个进程时，至少要同时为该进程创建一个线程</p>
<p>多线程环境下线程和进程：</p>
<p><img src="1.png" style="zoom: 45%;"></p>
<p>多进程结构进程结构示意图：</p>
<p>进程分为<strong>资源集合</strong>和<strong>线程集合</strong>。进程要支撑线程运行，为线程提供虚拟地址空间和各种资源。</p>
<p>进程封装管理信息，包括对指令代码、全局数据、打开的文件和信号量等共享部分的管理。</p>
<p>线程封装执行信息，包括状态信息、寄存器、执行栈（用户栈指针与核心栈指针）和局部变量、过程调用参数，返回值等私有部分的管理。</p>
<p><img src="2.png" style="zoom:60%;"></p>
<p>也把线程称为轻量进程（Light Weight Process, LWP）。</p>
<h4 id="线程状态"><a href="#线程状态" class="headerlink" title="线程状态"></a>线程状态</h4><p>线程状态有运行，就绪，等待和终止，线程的状态转换与进程类似。</p>
<p>由于线程不是资源拥有单位，挂起状态对于线程是没有意义的。挂起操作所引起的状态是进程级状态。</p>
<p>如果进程挂起后被对换出主存，则它的所有线程因共享进程的地址空间，也必须全部对换出去。</p>
<h4 id="线程组织"><a href="#线程组织" class="headerlink" title="线程组织"></a>线程组织</h4><p>一个进程可以包含若干线程，线程有多种组织方式：</p>
<ol>
<li>调度员-工作者模式：进程中的一个线程担任调度员、接收和处理工作请求，其他线程是工作者线程，由调度员线程分配任务并处理工作请求。</li>
<li>组模式：进程中的各个线程都可以取得并处理工作请求，有时某个线程被设计成专门执行特点任务，并建立相应任务队列。</li>
<li>流水线模式：线程排成某个次序，第一线程所生产的数据传给下一个线程进行处理，依次类推，数据按照排定次序由线程依次传递以完成被请求的任务</li>
</ol>
<h2 id="线程的实现"><a href="#线程的实现" class="headerlink" title="线程的实现"></a>线程的实现</h2><p>多线程的实现分为三类：</p>
<ol>
<li>用户级线程（User Level Thread , ULT）</li>
<li>内核级线程（Kernel Level Thread , KLT）</li>
<li>混合式线程，同时支持ULT和KLT</li>
</ol>
<h4 id="用户级线程ULT"><a href="#用户级线程ULT" class="headerlink" title="用户级线程ULT"></a>用户级线程ULT</h4><p>由用户应用程序建立、调度和管理的线程。(如Java ，Informix)</p>
<ol>
<li>不依赖于OS内核，应用进程利用<strong>线程库</strong>提供创建、同步、调度和管理线程的函数来控制用户线程。</li>
<li>调度由应用软件内部进行，通常采用非抢先式和更简单的规则，也无需用户态/核心态切换，所以速度特别快。一个线程发起系统调用而阻塞，则整个进程在等待。时间片分配给进程，多线程则每个线程就慢。</li>
</ol>
<p><strong>线程库</strong>：基于多线程的应用程序的开发和运行环境。</p>
<p>内核不知道线程的活动，但仍然管理线程所属进程的活动；当线程调用系统调用时，整个进程阻塞；但对线程库来说，线程仍然是运行状态，即线程状态是与进程状态独立的。</p>
<p>优点：</p>
<ul>
<li>线程切换不调用内核</li>
<li>调度是应用程序特定的：可以选择最好的算法。</li>
<li>ULT可运行在任何操作系统上（只需要线程库）。</li>
</ul>
<p>缺点：</p>
<ul>
<li>大多数系统调用是阻塞的，因此核心阻塞进程，故进程中所有线程将被阻塞。</li>
<li>核心只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上，因此不能利用多处理器优点</li>
</ul>
<h4 id="内核级线程KLT"><a href="#内核级线程KLT" class="headerlink" title="内核级线程KLT"></a>内核级线程KLT</h4><p>由操作系统的内核建立、调度和管理的线程。(如Windows NT，OS/2)</p>
<ul>
<li>所有线程管理由内核完成</li>
<li>没有线程库，但对内核线程工具提供API</li>
<li>内核维护进程和线程的上下文</li>
<li>线程之间的切换需要内核支持</li>
<li>以线程为基础进行调度</li>
</ul>
<p>优点：</p>
<ul>
<li>对多处理器，内核可以同时调度同一进程的多个线程</li>
<li>阻塞是在线程一级完成</li>
<li>内核例程是多线程的</li>
</ul>
<p>缺点：</p>
<ul>
<li>线程在用户态运行，而线程的调度和管理在内核实现，则在同一个进程中，控制权要想从一个线程转送到另一个线程时需要用户态-内核态-用户态模式转换，系统开销大</li>
</ul>
<h4 id="KLT和ULT比较"><a href="#KLT和ULT比较" class="headerlink" title="KLT和ULT比较"></a>KLT和ULT比较</h4><p><img src="3.png" style="zoom:100%;"></p>
<h4 id="混合式线程"><a href="#混合式线程" class="headerlink" title="混合式线程"></a>混合式线程</h4><p>线程实现分为两个层次：用户级和核心级。线程创建在用户空间完成；大量线程调度和同步在用户空间完成；程序员可以调整KLT的数量；可以取两者中最好的。</p>
</div>
<footer class="article-footer">
<a data-url="http://dongxh.cn/2020/04/03/OS-处理器管理（4）-线程及其实现/" data-id="ckjcmdb8c000j03lkvwr4lulr" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/操作系统/">操作系统</a></li></ul>
</footer>
</div>
</article>
<article id="post-OS-处理器管理（3）-进程及其实现" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2020/04/02/OS-处理器管理（3）-进程及其实现/" class="article-date">
<time datetime="2020-04-02T08:17:21.000Z" itemprop="datePublished">2020-04-02</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/Operating-System/">Operating System</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2020/04/02/OS-处理器管理（3）-进程及其实现/">OS--处理器管理（3）_进程及其实现</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="OS—处理器管理（3）-进程及其实现"><a href="#OS—处理器管理（3）-进程及其实现" class="headerlink" title="OS—处理器管理（3）_进程及其实现"></a>OS—处理器管理（3）_进程及其实现</h1><p>知识点：</p>
<ul>
<li>进程定义和属性</li>
<li>进程状态和转换</li>
<li>进程描述和组成</li>
<li>进程上下文切换与处理器状态转换</li>
<li>进程控制和管理</li>
</ul>
<h2 id="进程的定义和属性"><a href="#进程的定义和属性" class="headerlink" title="进程的定义和属性"></a>进程的定义和属性</h2><p>“进程“是操作系统中最重要最基本的概念，在多道程序系统提出后，为了刻画系统内部动态状况，描述运行程序活动规律而提出的新概念。</p>
<p>从<strong>原理角度</strong>来看，进程是支持程序执行的一种系统机制，是对处理器上运行程序的活动规律的抽象；</p>
<p>从<strong>现实角度</strong>看，进程是一种数据结构，用来准确刻画运行程序的状态和系统动态变化状况；</p>
<p>引入进程的两个目的：</p>
<ol>
<li>刻画程序的并发性；</li>
<li>解决资源的共享性<br>“可再入”程序指的是能够被多个程序同时调用的程序；“可再用”程序是指在被调用的过程中可以有自身修改，在调用它的程序退出之前不允许其他程序来调用。</li>
</ol>
<p>引入进程的概念后，程序与程序的执行（计算)不再一一对应。</p>
<p><strong>定义：进程是既能描述程序的并发执行，又能共享系统调用资源的一个基本单位。</strong>（操作系统要为引入进程而付出（进程占用的）空间和（进程调度的）时间的代价）。<strong>进程是具有独立功能的程序在某个数据集合上的一次运行活动，也是操作系统进行资源分配和保护的基本单位</strong>。</p>
<p>进程的属性：</p>
<ol>
<li>动态性。<br>因为进程是一次执行过程，具有生命周期，具有动态概念。</li>
<li>共享性。<br>同义程序同时运行在不同的数据集合上时构成不同进程，即多个不同进程可执行相同的程序。</li>
<li>独立性<br>每个进程是操作系统中的一个独立实体，有自己的虚存空间，程序计数器和内部状态。</li>
<li>制约性<br>进程因为共享资源或者协同工作产生相互制约关系，造成进程执行速度的不可预测性，必须对进程的执行次序或相对执行速度加以协调。</li>
<li>并发性<br>进程在时间上可以重叠，单处理器系统中并发执行，多处理器系统中可以并行执行。</li>
</ol>
<h2 id="进程的状态和转换"><a href="#进程的状态和转换" class="headerlink" title="进程的状态和转换"></a>进程的状态和转换</h2><h4 id="三态模型"><a href="#三态模型" class="headerlink" title="三态模型"></a>三态模型</h4><p>正如上面所说的，由于进程的动态性，为了便于管理，我们按照进程在执行过程中的不同情况，至少给其定义三种进程状态：</p>
<ol>
<li>运行态（running）：进程占有处理器正在运行的状态</li>
<li>就绪态（ready）：进程具备运行条件，等待系统分配处理器以便运行的状态</li>
<li>等待态（wait）：又称阻塞态（blocked）或者睡眠态（sleep），指进程不具备运行条件，正在等待某个事件完成的状态。</li>
</ol>
<p>处于运行态的进程个数不能大于处理器个数。</p>
<p><img src="1.png" style="zoom:50%;"></p>
<h4 id="七态模型"><a href="#七态模型" class="headerlink" title="七态模型"></a>七态模型</h4><p>有时为了便于管理，会引进新的状态：</p>
<ol>
<li>新建态（new）：进程被创建时的状态，尚未进入就绪队列。</li>
<li>终止态（exit）：进程完成任务到达正常结束点，或者出现无法克服的错误而异常终止，或被操作系统及有终止权的进程所终止时所处的状态。不再被调度，等待被撤销。</li>
<li>挂起态（suspend）：当系统资源尤其是内存资源已经不能满足进程运行的要求时，必须把某些进程挂起，<strong>对换到磁盘对换区中</strong>，释放占用的某些资源，暂时不参与低级调度，还有很多原因，</li>
</ol>
<p><img src="2.png" style="zoom:50%;"></p>
<p>挂起就绪态（ready suspend）表明进程具备运行条件，但目前在外存中，只有当它被对换到内存才能被调度执行；</p>
<p>挂起等待态（blocked suspend）表明进程正在等待某一个事件发生且也在外存中。</p>
<p>在一个实际的操作系统中，为了方便管理和调度往往设置多种进程状态。如Linux主要的进程状态有5种。</p>
<h2 id="进程的描述和组成"><a href="#进程的描述和组成" class="headerlink" title="进程的描述和组成"></a>进程的描述和组成</h2><h4 id="进程映像"><a href="#进程映像" class="headerlink" title="进程映像"></a>进程映像</h4><p><img src="3.png" style="zoom:40%;"></p>
<ul>
<li>进程映像：进程某时刻的内容和状态集合。<ul>
<li>进程控制块：存储进程标志信息、现场信息和控制信息。</li>
<li>进程程序块：被进程执行的程序。</li>
<li>进程核心栈：用来保存中断/异常现场，保存内核函数调用的参数、局部变量和返回地址。</li>
<li>进程数据块：进程的私有地址空间，存放各种私有数据，包括用户栈。</li>
</ul>
</li>
</ul>
<p>进程上下文（process context）：进程物理实体和支持进程运行的环境。如硬件寄存器、程序状态字寄存器、支持动态地址转换的页表和相关的核心数据结构。</p>
<p>当系统调度新进程占有处理器时，新老进程随之发生上下文切换。进程的运行被认为是在上下文中执行。</p>
<p>进程上下文组成：</p>
<ol>
<li>用户级上下文（user level context）：由程序块、数据块、共享内存区、用户栈组成，占用进程的虚存空间。</li>
<li>系统级上下文（register context）：有进程控制块、内存管理信息、核心栈等操作系统管理进程所需要的信息组成。</li>
<li>寄存器上下文（system level context）：由处理器状态寄存器、指令计数器、栈指针、通用寄存器等组成。</li>
</ol>
<h4 id="进程控制块"><a href="#进程控制块" class="headerlink" title="进程控制块"></a>进程控制块</h4><p>每个进程有且仅有一个程序控制块（Process Control Block , PCB）,或称进程描述符（process descriptor），是进程存在的唯一标识。是操作系统用于记录和刻画进程状态及有关信息的数据结构。也是操作系统掌握进程的唯一资料结构，它包括进程执行时的情况，以及进程让出处理器后所处的状态、断点等信息。</p>
<p>PCB包含以下三类信息</p>
<ol>
<li>标识信息。用于唯一地标识一个进程，分为用户使用的外部标识符和系统使用的内部标识号。</li>
<li>现场信息。用于保留进程在运行时存放在处理器现场中的各种信息。</li>
<li>控制信息。用于管理和调度进程。</li>
</ol>
<p><strong>PCB是操作系统中最重要的数据结构，它包含管理进程所需要的全部信息。</strong></p>
<p>PCB的集合实际上定义了一个操作系统当前的状态，其使用权和修改权均属于操作系统。操作系统根据PCB对并发执行的进程进行控制和管理，进程借助于PCB才能被调度执行。</p>
<h4 id="进程队列及其管理"><a href="#进程队列及其管理" class="headerlink" title="进程队列及其管理"></a>进程队列及其管理</h4><p>把<strong>处于同一状态</strong>的所有进程的PCB链接在一起的数据结构称为<strong>进程队列（process queue）</strong>。通常有两种组织队列的方式：</p>
<p><strong>链接方式</strong></p>
<p>对于同一状态进程的PCB，通过PCB中的链接指针将其链接成队列，单向指针和双向指针都可以。单向队列编号为0排在队尾；双向队列对于后向指针来说编号为0在队尾，对于前向指针，编号为0在前面</p>
<p>不同状态的进程可以排成不同的队列，如运行队列，就绪队列和等待队列等。运行队列通常只有一个进程；就绪队列可以按照优先级或者FCFS（First Come First Serve）的原则排队，也可以按照进程的优先级高低分成多个就绪队列；等待队列通常有多个，对应不同的等待状态，如等待I/O操作完成，等待信号量等。此外还可以将空闲PCB结构链接成自由队列以便使用。</p>
<p>当某个事件发生，状态发生改变时，有个进程会出队，有的进程会进队。处理器调度中负责进程入队和出队工作的功能模块称为<strong>队列管理模块</strong>，其任务就是对进程的PCB重新排队并修改其状态和相应链接结构。</p>
<p><img src="4.png" style="zoom:50%;"></p>
<p><strong>索引方式</strong></p>
<p>索引方式利用索引表记录不同状态进程的PCB地址或者在PCB表中的编号，系统建立不同状态的索引表，各个索引表在内存中的起始位置放在内核占用指针单元中。</p>
<p><img src="5.png" style="zoom:50%;"></p>
<h2 id="进程上下文切换于处理器状态转换"><a href="#进程上下文切换于处理器状态转换" class="headerlink" title="进程上下文切换于处理器状态转换"></a>进程上下文切换于处理器状态转换</h2><h4 id="进程上下文切换"><a href="#进程上下文切换" class="headerlink" title="进程上下文切换"></a>进程上下文切换</h4><p><strong>中断和异常是激活操作系统的仅有方法。</strong>这里说的激活操作系统的意思是指让操作系统内核获得处理器控制权，也就是进入内核态。因为只有操作系统有权利使用修改进程PCB，所以<strong>进程切换必定发生在内核态而非用户态</strong>。</p>
<p><img src="6.png" style="zoom:50%;"></p>
<p>思考题：程序状态字PSW和进程控制块PCB的区别？</p>
<p><strong>进程上下文切换时机</strong></p>
<p>内核中不能立即进行调度和切换的情况有：内核正在处理中断的过程中，进程运行在内核临界区中，内核处在需要屏蔽中断的原子操作中。</p>
<p>如果在上述过程中产生引起调度的条件而不能马上进行调度和切换，系统采用将请求调度标志延迟到敏感性操作完成后再进行。</p>
<p>为此，Linux在进程<code>task_struct</code>中设计了重调度标志<code>need_resched</code>,V２.６版中，被移至<code>thread_info</code> 结构体中，用标志<code>TIF_NEED_RESCHED</code> 表示 。调度时机：</p>
<ol>
<li>主动调度：指调用<code>schedule()</code>函数来释放CPU,引起新一轮调度，通常发生在当前进程状态被改变,如:执行了<code>read()</code>、<code>write()</code>、<code>exit()</code>等系统调用，导致进程终止、进程阻塞等。</li>
<li>被动调度：指发生了引起调度的条件, 这时仅置进程<code>TIF_NEED_RESCHED</code>调度标志。调度标志设置有以下四种情况：<ol>
<li>时钟中断中调用函数<code>scheduler_tick()</code>，查看当前进程的时间片是否耗尽，如果是，则设置重调度标志；</li>
<li>函数<code>try_to_wake_up( )</code>将阻塞的进程唤醒，把它加入运行队列时，如果其优先级比当前正在运行进程的优先级高，设置重调度标志。</li>
<li>设置应用进程优先级参数nice值、创建新进程、SMP负载均衡时都可能使高优先级进程进入就绪状态，也可能设置重调度标志；</li>
<li>执行<code>sched_setscheduler( )</code>（设置调度策略）、<code>sched_yield</code>( 暂时让出处理器)、<code>pause( )</code>（暂停）等系统调用，均要设置重调度标志。</li>
</ol>
</li>
</ol>
<p>每当中断处理和系统调用处理结束返回时，在<code>ret_from_sys_call</code>代码段中会主动测试调度标志，若置位则调用<code>schedule()</code>函数.</p>
<h4 id="处理器状态转换"><a href="#处理器状态转换" class="headerlink" title="处理器状态转换"></a>处理器状态转换</h4><p>步骤：</p>
<ol>
<li>保存被中断进程的处理器现场信息；</li>
<li>处理器从用户态转换到核心态，以便执行服务程序或中断处理程序；</li>
<li>如果处理中断，可根据规定的中断级设置中断屏蔽位；</li>
<li>根据系统调用号或中断号，从系统调用表或中断入口表找到服务程序或中断处理程序地址。</li>
</ol>
<p>处理器上执行进程的活动范围必在以下四个情况下：</p>
<ol>
<li>用户空间中，处于进程上下文，用户进程在运行，使用用户栈。</li>
<li>内核空间中，处于进程上下文，内核代表某进程在运行，使用核心栈。</li>
<li>内核空间中，处于中断上下文，与任何进程无关，中断服务程序正在处理特定中断，Intel x86未提供中断栈，借用核心栈。</li>
<li>内核空间中，内核线程(无用户地址空间的进程)运行于内核态。</li>
</ol>
<h4 id="Linux中进程上下文切换"><a href="#Linux中进程上下文切换" class="headerlink" title="Linux中进程上下文切换"></a>Linux中进程上下文切换</h4><p><img src="7.png" style="zoom:50%;"></p>
<h2 id="进程控制和管理"><a href="#进程控制和管理" class="headerlink" title="进程控制和管理"></a>进程控制和管理</h2><p>原语是在操作系统中调用核心层子程序的指令。与一般广义指令的区别在于它是<strong>不可中断</strong>的，而且总是作为一个基本单位出现。它与一般过程的区别在于：它们是“原子操作”（primitive or atomic action）。所谓原子操作，是指一个操作中的所有动作要么全做，要么全不做。换言之，它是一个不可分割的基本单位，因此，在执行过程中不允许被中断。<strong>原子操作在管态下执行，常驻内存</strong>。原语的作用是为了实现进程的通信和控制，系统对进程的控制如不使用原语，就会造成其状态的不确定性，从而达不到进程控制的目的</p>
<p>进程管理原语</p>
<h4 id="进程创建"><a href="#进程创建" class="headerlink" title="进程创建"></a>进程创建</h4><ol>
<li>在进程列表中增加一项，从PCB池中申请一个空闲PCB，为新进程分配惟一的进程标识符；</li>
<li>为新进程的进程映像分配地址空间，以便容纳进程实体。进程管理程序确定加载到进程地址空间中的程序；</li>
<li>为新进程分配除主存空间外的其他各种所需资源；</li>
<li>初始化PCB，如进程标识符、处理器初始状态、进程优先级等；</li>
<li>把新进程状态置为就绪态，并移入就绪进程队列；</li>
<li>通知操作系统的某些模块，如记账程序、性能监控程序。</li>
</ol>
<h4 id="进程撤销"><a href="#进程撤销" class="headerlink" title="进程撤销"></a>进程撤销</h4><ol>
<li>根据撤销进程标识号，从相应队列中找到并移出它；</li>
<li>将该进程拥有的资源归还给父进程或操作系统；</li>
<li>若该进程拥有子进程，先撤销它的所有子进程，以防它们脱离控制；</li>
<li>回收PCB，并归还到PCB池。</li>
</ol>
<h4 id="进程阻塞"><a href="#进程阻塞" class="headerlink" title="进程阻塞"></a>进程阻塞</h4><ol>
<li>停止进程执行，保存现场信息到PCB；</li>
<li>修改进程PCB有关内容，如进程状态由运行态改为等待态等，并把修改状态后的进程移入相应事件的等待队列中；</li>
<li>转入进程调度程序去调度其他进程运行。</li>
</ol>
<h4 id="进程唤醒"><a href="#进程唤醒" class="headerlink" title="进程唤醒"></a>进程唤醒</h4><ol>
<li>从相应的等待队列中移出进程；</li>
<li>修改进程PCB的有关信息，如进程状态改为就绪态，并移入就绪队列；</li>
<li>若被唤醒进程比当前运行进程优先级高，重新设置调度标志。</li>
</ol>
<h4 id="进程的挂起"><a href="#进程的挂起" class="headerlink" title="进程的挂起"></a>进程的挂起</h4><ol>
<li>检查要被挂起的进程的状态</li>
<li>若处于活动就绪态，则修改为挂起就绪态</li>
<li>若处于等待态，则修改为挂起等待态</li>
<li>被挂起的进程PCB的非常驻部分要交换到磁盘对换区</li>
</ol>
<h4 id="进程的激活"><a href="#进程的激活" class="headerlink" title="进程的激活"></a>进程的激活</h4><ol>
<li>把被挂起进程PCB的非常驻部分掉入内存</li>
<li>修改为对应的状态（等待或者就绪）</li>
<li>将进程移入相应队列中</li>
</ol>
<p>挂起原语既可由自己也可由其他进程调用，而激活原语只能由其他进程调用。</p>
</div>
<footer class="article-footer">
<a data-url="http://dongxh.cn/2020/04/02/OS-处理器管理（3）-进程及其实现/" data-id="ckjcmdbcl001k03lkqyn88sj2" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/操作系统/">操作系统</a></li></ul>
</footer>
</div>
</article>
<article id="post-OS-处理器管理（1）-中断技术" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2020/03/30/OS-处理器管理（1）-中断技术/" class="article-date">
<time datetime="2020-03-30T14:40:52.000Z" itemprop="datePublished">2020-03-30</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/Operating-System/">Operating System</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2020/03/30/OS-处理器管理（1）-中断技术/">OS--处理器管理（2）_中断技术</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="OS—处理器管理-2-中断技术"><a href="#OS—处理器管理-2-中断技术" class="headerlink" title="OS—处理器管理(2)_中断技术"></a>OS—处理器管理(2)_中断技术</h1><p>知识要点：</p>
<ul>
<li>中断概念</li>
<li>中断源分类</li>
<li>中断和异常的响应及服务</li>
<li>中断事件处理原则</li>
<li>中断优先级和多重中断</li>
<li>Linux中断处理（自学）</li>
</ul>
<h3 id="中断概念"><a href="#中断概念" class="headerlink" title="中断概念"></a>中断概念</h3><p>每当应用程序执行系统调用时要求获得系统服务，I/O设备报告传输情况，或者产生各种内部外部事件时，都要通过中断机制产生中断信号并启动操作系统内核工作。<strong>操作系统是由“中断驱动”的。</strong></p>
<p><strong>中断（interrupt）</strong>指在程序执行过程中遇到急需处理的事件时，暂时中止现行程序在CPU上的运行，转而执行相应的事处理程序，待处理完成后再返回断点或者调度其他程序执行的过程。</p>
<p><strong>共性</strong>：即中断装置能够改变处理器内操作的执行顺序。</p>
<p><strong>中断系统</strong>：</p>
<ul>
<li>中断装置：指发现中断，响应中断的硬件<ul>
<li>发现中断源，提出中断请求；</li>
<li>保护现场 ；</li>
<li>启动处理中断事件的程序 ；</li>
</ul>
</li>
<li>中断处理程序：由软件来完成<ul>
<li>主要任务是处理中断事件和恢复正常操作 ；</li>
</ul>
</li>
</ul>
<h3 id="中断源分类"><a href="#中断源分类" class="headerlink" title="中断源分类"></a>中断源分类</h3><p><img src="1.png" style="zoom:50%;"></p>
<p>外中断：各个中断具有不同的中断优先级，表示事件的紧急程度，在处理高一级的中断时，往往会屏蔽部分或者全部的低级中断。</p>
<p>内中断：不能被屏蔽，一旦出现应立即予以响应并进行处理。</p>
<p> 外中断和内中断组合形成完整的中断体系，由于产生原因和处理方法差别越来越大，所以把中断和异常区分开来：</p>
<div class="table-container">
<table>
<thead>
<tr>
<th>中断</th>
<th>异常</th>
</tr>
</thead>
<tbody>
<tr>
<td>由与当前运行程序无关的中断信号触发，CPU对中断的响应是被动的，无论CPU处于什么状态，都需要处理外部设备发来的中断请求</td>
<td>由CPU控制单元产生，允许指令在执行期间响应异常，大部分异常发生在用户态，而内核态唯一发生的异常是‘缺页异常’</td>
</tr>
<tr>
<td>要求中断被快速处理，以便及时响应其他中断信号，所以中断处理程序处理过程中是不能被阻塞的</td>
<td>异常处于被打断的当前进程上下文中，所提供的服务是当前进程所需要的，异常处理程序处理过程中是可以被阻塞的</td>
</tr>
<tr>
<td>中断允许发生嵌套</td>
<td>异常大多为一重</td>
</tr>
<tr>
<td>中断处理过程中决不会被异常打断</td>
<td>异常处理过程中可能会产生中断</td>
</tr>
</tbody>
</table>
</div>
<h3 id="中断和异常的响应及服务"><a href="#中断和异常的响应及服务" class="headerlink" title="中断和异常的响应及服务"></a>中断和异常的响应及服务</h3><p>无论中断还是异常，CPU的响应过程基本上是一致的，即在执行完当前指令后，根据中断源所提供的“中断向量”，在内核中找到相应的中断服务例程并调度执行。</p>
<p>1.中断向量由硬件或者操作系统预先分配和设置；2.系统调用对应的向量则在访管指令中给出；3.异常向量在CPU的硬件结构预先规定；</p>
<p>发现中断源并产生中断的硬件称为<strong>中断控制器</strong>，包括中断逻辑线路和中断寄存器。再看异常，它是执行指令时，由于指令本身的原因发生的，指令的控制逻辑和实现线路一旦发现异常便转向内核的异常处理程序。</p>
<p>中断/异常的响应需要顺序做四件事：</p>
<p><img src="2.png" style="zoom:50%;"></p>
<h3 id="中断事件处理原则"><a href="#中断事件处理原则" class="headerlink" title="中断事件处理原则"></a>中断事件处理原则</h3><p><strong>硬件故障处理</strong>：需要人工干预</p>
<p><strong>程序性中断</strong>：一是语法错误，由编译程序发现并报错；二是逻辑错误，由测试程序发现；三是程序运行过程中产生异常。</p>
<p><strong>I/O中断</strong></p>
<p>I/O中断的处理原则如下：</p>
<ol>
<li>I/O操作正常结束。把等待传输的下一个进程设置为就绪态，让它占据设备或者通道并启动数据传输。</li>
<li>I/O操作发生故障。先向设备发命令索取状态字，分析产生故障的确切原因，再进行复执或者请求人工干预。</li>
<li>I/O操作发生异常。分析情况采取相应的措施，向操作员报告。</li>
<li>设备报到或者设备结束。表示有设备接入可供使用或者设备断开暂停使用，操作系统应该修改系统数据结构中相应的设备状态。</li>
</ol>
<p><strong>访管中断</strong></p>
<p>由程序执行访管指令而引起的，表示当前运行程序对操作系统功能的调用，可看做机器指令的一种扩充。</p>
<p>访管指令包括操作码和访管参数两部分，前者表示此指令是访管指令，后者表示具体的访管要求。</p>
<p>。。。</p>
<p><strong>时钟中断</strong></p>
<p> 时钟是操作系统进行调度工作的重要工具。比如让分时进程作时间片轮转；让实时进程定时发出或接收控制信号；系统定时唤醒或阻塞一个进程；对用户进程进行记账。</p>
<p> 时钟可分成绝对时钟和间隔时钟两种。</p>
<p> 有了硬件定时器，Linux就可以统计用户的记账信息，它记录了进程的创建时间以及进程在生命周期占用的CPU时间，每个时钟滴答到来时，核心都修改当前进程在内核态和用户态占用的时间。</p>
<p> Linux系统运行不同的间隔定时器，类型有三种：</p>
<ul>
<li>real间隔定时器：按实际经过时间计时，不管进程处在何种模式下运行，包括进程被挂起时，计时总在进行，定时到达时发送给进程一个SIGALRM信号。</li>
<li>virtual间隔定时器：进程在用户态下执行时才计时，定时到达时发送给进程一个SIGVTALRM信号。</li>
<li>profile间隔定时器：进程执行在用户态或核心态时都计时，当定时到达时发送给进程一个SIGROF信号。</li>
</ul>
<h3 id="中断优先级和多重中断"><a href="#中断优先级和多重中断" class="headerlink" title="中断优先级和多重中断"></a>中断优先级和多重中断</h3><p><strong>中断优先级</strong></p>
<p>有硬件方法和软件方法实现：硬件方法，根据排定的优先级顺序做一个硬件链式排队器，当产生高一级中断事件时，应该屏蔽比它优先级低的所有中断源；软件方法，编写一个查询程序，根据优先级顺序从高到低进行查询，一旦发现有中断请求便转入相应的中断时间处理程序的入口。</p>
<p><strong>中断屏蔽</strong></p>
<p>可由CPU通过指令编写中断控制器的屏蔽码来实现。</p>
<p>中断屏蔽是指禁止CPU相应中断或者禁止中断产生。</p>
<p>作用是：</p>
<ol>
<li>延迟或禁止某些中断的响应。系统程序执行过程中，不希望产生干扰事件，以免共享数据结构受到破坏。程序运行过程中产生某些事件认为是正常的，不必加以处理。</li>
<li>协调中断响应与中断处理的关系。确保高优先级中断可以打断低优先级中断，反之却不能。</li>
<li>防止同级中断相互干扰。在处理某优先级中断事件时，必须屏蔽该级中断，以免造成混乱。</li>
</ol>
<p><strong>多重中断事件处理</strong></p>
<p>中断正在进行处理期间，CPU又响应新的中断事件，于是暂时停止正在运行的中断处理程序，转去执行新的中断处理程序，就叫多重中断（又称中断嵌套）。</p>
<p>对同一优先级的不同中断：采用顺序处理 方法。</p>
<p>对不同优先级的中断，采用以下处理方法：1.串行处理；2.嵌套处理，还要规定最大嵌套重数；3.即时处理，在运行中断处理程序时，如果出现程序性中断事件，在一般情况下，表明此时中断处理程序有异常，应对其立即响应并进行处理</p>
<h3 id="Linux中断处理"><a href="#Linux中断处理" class="headerlink" title="Linux中断处理"></a>Linux中断处理</h3><p><img src="3.png" style="zoom: 45%;"></p>
<h5 id="Linux中断机制"><a href="#Linux中断机制" class="headerlink" title="Linux中断机制"></a><strong>Linux中断机制</strong></h5><p><strong>中断向量</strong>：对中断信号编码，每个中断信号的编码称为其对应的中断向量；</p>
<p>中断请求：每个能发送中断信号的硬件设备控制器都有一根控制线，与中断控制器相连接，若是硬件欲向CPU发送 中断信号必须申请一条可用的中断请求线，或者说一个IRQ号，这就是中断请求（Interrupt Requirement，IRQ）。</p>
<p><strong>中断描述符表</strong>：Linux中断机制在保护模式下采用中断描述符表（Interrupt Descriptor Table,IDT）实现，此表包 含256个表项，每个中断/异常都对应一个表项，每个表项称为一个门描述符（gate descriptor）, 作用是把程序控制权转交给中断/异常处理程序。门的含义是，当中断/异常发生时必须先通过这 道门，才能进入中断/异常处理程序。</p>
<p><img src="4.png" style="zoom:40%;"></p>
<p><strong>中断请求队列</strong>：</p>
<ol>
<li>中断处理程序和中断服务例程</li>
<li>中断处理程序的执行</li>
</ol>
<p>中断共享的数据结构为irqaction。</p>
<p><strong>中断处理程序的执行</strong></p>
<h5 id="Linux下半部分处理"><a href="#Linux下半部分处理" class="headerlink" title="Linux下半部分处理"></a>Linux下半部分处理</h5><p>中断处理程序的特点是：以异步方式运行，有可能打断关键代码的执行，甚至打断处理程序的执行；运行时屏蔽中断，最坏的情况会屏蔽所有中断；要操作硬件，对时限要求很高；在中断上下文运行，故不能被阻塞。总之，需要中断处理程序执行的越快越好，因为<strong>缩短屏蔽中断的时间对于系统的响应能力和性能都至关重要</strong>。</p>
<p><img src="5.png" style="zoom: 40%;"></p>
<h5 id="Linux的三种任务延迟机制"><a href="#Linux的三种任务延迟机制" class="headerlink" title="Linux的三种任务延迟机制"></a>Linux的三种任务延迟机制</h5><ol>
<li>小任务（tasklet）</li>
<li>工作队列（work queue）</li>
<li>软中断（softirq）</li>
</ol>
</div>
<footer class="article-footer">
<a data-url="http://dongxh.cn/2020/03/30/OS-处理器管理（1）-中断技术/" data-id="ckjcmdbcj001i03lk93e4biiv" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/操作系统/">操作系统</a></li></ul>
</footer>
</div>
</article>
<article id="post-OS-处理器管理（1）-处理器状态" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2020/03/28/OS-处理器管理（1）-处理器状态/" class="article-date">
<time datetime="2020-03-28T07:13:22.000Z" itemprop="datePublished">2020-03-28</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/Operating-System/">Operating System</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2020/03/28/OS-处理器管理（1）-处理器状态/">OS--处理器管理（1）_处理器状态</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="OS—处理器管理-1-处理器状态"><a href="#OS—处理器管理-1-处理器状态" class="headerlink" title="OS—处理器管理(1)_处理器状态"></a>OS—处理器管理(1)_处理器状态</h1><p>要点：</p>
<ul>
<li>处理器</li>
<li>程序字状态</li>
</ul>
<h3 id="处理器"><a href="#处理器" class="headerlink" title="处理器"></a>处理器</h3><h4 id="指令系统和寄存器"><a href="#指令系统和寄存器" class="headerlink" title="指令系统和寄存器"></a>指令系统和寄存器</h4><p>计算机中最终被执行的是存储在内存中的机器指令代码。</p>
<p>处理器根据程序计数器的指向从内存中取指令到指令寄存器，然后译码并执行，程序计数器自动增长或变为转移地址以指明下一条待执行指令的地址。</p>
<p>每台计算机的机器指令集称为<strong>指令系统</strong>，反映计算机的功能和处理能力。</p>
<ul>
<li>数据处理类指令：用于执行算术和逻辑运算。 </li>
<li>I/O类指令：用于启动外围设备，让主存和设备交换数据。 </li>
<li>寄存器数据交换类指令：用于在处理器的寄存器和存储器之间交换数据。 </li>
<li>转移类指令：用于改变执行指令序列。</li>
<li>处理器控制指令：修改处理器状态，改变处理器工作方式。</li>
</ul>
<p>以Intel x86为例：</p>
<ul>
<li>通用寄存器： $EAX ,EBX,ECX,EDX$.</li>
<li>指针及变址寄存器： $ESP,EBP,ESI,EDI$.</li>
<li>段选择符寄存器： $CS,DS,SS,ES,FS,GS$.</li>
<li>指令指针寄存器和标志寄存器：$EIP,EFLAGS$.</li>
<li>控制寄存器： $CRO,CR1,CR2,CR3$.</li>
<li>外部设备使用的寄存器。</li>
</ul>
<p><strong>问题：在单道程序系统中，用户程序可以直接使用CPU指令启动I/O设备，进行I/O操作。在多道程序系统中，这种模式可不可行？</strong></p>
<h4 id="特权指令和非特权指令"><a href="#特权指令和非特权指令" class="headerlink" title="特权指令和非特权指令"></a>特权指令和非特权指令</h4><p><strong>特权指令</strong>：只仅能在内核态下才能使用的指令，这些指令涉及改变机器状态，修改寄存器内容，启动设备I/O等。</p>
<p><strong>非特权指令</strong>：在管态和目态下都能执行。（</p>
<p>操作系统程序能运行全部机器指令，应用程序只能使用非特权指令。</p>
<p>当应用程序试图执行特权指令，将会导致非法执行二产生的保护中断，继而转向操作系统的“用户非法执行特权指令”的异常处理程序处理。</p>
<h4 id="内核态和用户态"><a href="#内核态和用户态" class="headerlink" title="内核态和用户态"></a>内核态和用户态</h4><p>处理器状态标志：管理状态（核心状态、特态或管态）和用户状态（目标状态、常态或目态)。</p>
<p>Intel x86处理器状态有4种，0级权限最高，3级权限最低。</p>
<h4 id="处理器状态及其转换"><a href="#处理器状态及其转换" class="headerlink" title="处理器状态及其转换"></a>处理器状态及其转换</h4><p>在下列三种情况下会导致处理器状态从用户态向内核态转变：</p>
<ol>
<li>程序请求操作系统服务，执行系统调用</li>
<li>程序运行时产生中断事件（如I/O操作完成），运行程序被中断，转向中断处理程序执行</li>
<li>程序运行时产生异常事件（如发生程序性中断，或目态执行特权指令），运行程序被打断，转向异常处理程序工作</li>
</ol>
<p>而从内核态向用户态转换，则通过一条称为加载程序状态字的特权指令（Intel x86为iret指令）</p>
<h4 id="用户栈和核心栈"><a href="#用户栈和核心栈" class="headerlink" title="用户栈和核心栈"></a>用户栈和核心栈</h4><p>用户栈：用户进程空间中开辟的一块区域，用于保护应用程序的子程序（子函数）之间互相调用的参数，返回值，返回点以及子程序的局部变量</p>
<p>核心栈：也称内核栈或系统栈。是内存中属于操作系统空间的一块区域。</p>
<p>核心栈的用途：</p>
<ol>
<li>保护中断现场，对于嵌套中断，被中断程序的现场信息依次压入核心栈，中断返回时逆序弹出；</li>
<li>保存操作系统程序（函数）间相互调用的参数，返回值，返回点以及程序局部变量。</li>
</ol>
<p>每个进程被创建时捆绑一个核心栈，具有可读可写不可执行属性。</p>
<p>栈指针：为硬件栈指针，用户栈和核心栈共用一个栈指针。</p>
<h3 id="程序状态字"><a href="#程序状态字" class="headerlink" title="程序状态字"></a>程序状态字</h3><p>$Program Status Word,PSW$ 程序状态字。PSW用来<strong>控制指令执行顺序</strong>并<strong>保留和指示与程序有关的系统状态和各种信息</strong>，主要作用是实现程序状态的保护和恢复。每个正在执行的程序都有一个与其当前状态相关的PSW，每个处理器都设置一个PSW寄存器。程序占有处理器执行，它的PSW将占有PSW寄存器。</p>
<p>操作系统将程序运行时的一组<strong>动态信息</strong>汇集在一起。并存放在处理器的一组特殊寄存器里面，以方便系统控制和管理。</p>
<p>$PSW$寄存器包括以下内容：</p>
<ul>
<li>程序基本状态：<ul>
<li>程序计数器；</li>
<li>条件码；</li>
<li>处理器状态位；</li>
</ul>
</li>
<li>中断码。保存程序执行时当前发生的中断事件。</li>
<li>中断屏蔽位。指明程序执行中发生中断事件时，是否响应出现的中断事件。</li>
</ul>
<p>在Intel x86机器中，$PSW$由标志寄存器$EFLAGS$和指针寄存器$EIP$组成，均为32位。$EFLAGS$低16位称为$FLAGS$，可以当作一个单元来处理。指令指针寄存器$EIP$的低16位称为$IP$（保护模式需使用32位），可以当作一个单元使用，存放顺序执行的下一条指令相对于当前代码段起始地址的一个偏移量。</p>
</div>
<footer class="article-footer">
<a data-url="http://dongxh.cn/2020/03/28/OS-处理器管理（1）-处理器状态/" data-id="ckjcmdb8a000e03lk4jawndt6" class="article-share-link">Share</a>
<ul class="article-tag-list"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/操作系统/">操作系统</a></li></ul>
</footer>
</div>
</article>
<article id="post-OS-操作系统概论" class="article article-type-post" itemscope itemprop="blogPost">
<div class="article-meta">
<a href="/2020/03/27/OS-操作系统概论/" class="article-date">
<time datetime="2020-03-27T14:15:32.000Z" itemprop="datePublished">2020-03-27</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/Operating-System/">Operating System</a>
</div>
</div>