現(xiàn)代操作系統(tǒng)（第2版）

第1章   引論    1
1.1   什么是操作系統(tǒng)    2
1.1.1   作為擴展機器的操作系統(tǒng)    2
1.1.2   作為資源管理者的操作系統(tǒng)    2
1.2   操作系統(tǒng)的歷史    3
1.2.1   第一代（1945～1955）：真空管和
插件板    3
1.2.2   第二代（1955～1965）：晶體管和
批處理系統(tǒng)    4
1.2.3   第三代（1965～1980）：集成電路和多道程序設(shè)計    5
1.2.4   第四代（1980～至今）：個人計算機    7
1.2.5   個體的重復(fù)發(fā)展    9
1.3   操作系統(tǒng)大觀    10
1.3.1   大型機操作系統(tǒng)    10
1.3.2   服務(wù)器操作系統(tǒng)    10
1.3.3   多處理機操作系統(tǒng)    10
1.3.4   個人計算機操作系統(tǒng)    10
1.3.5   實時操作系統(tǒng)    10
1.3.6   嵌入式操作系統(tǒng)    11
1.3.7   智能卡操作系統(tǒng)    11
1.4   計算機硬件介紹    11
1.4.1   處理器    11
1.4.2   存儲器    13
1.4.3   I/O設(shè)備    15
1.4.4   總線    17
1.5   操作系統(tǒng)概念    19
1.5.1   進程    19
1.5.2   死鎖    20
1.5.3   存儲管理    21
1.5.4   輸入/輸出    21
1.5.5   文件    21
1.5.6   安全    23
1.5.7   shell    23
1.5.8   概念的重用    24
1.6   系統(tǒng)調(diào)用    25
1.6.1   用于進程管理的系統(tǒng)調(diào)用26
1.6.2   用于文件管理的系統(tǒng)調(diào)用28
1.6.3   用于目錄管理的系統(tǒng)調(diào)用29
1.6.4   其他系統(tǒng)調(diào)用    30
1.6.5   Windows   Win32 API    30
1.7   操作系統(tǒng)結(jié)構(gòu)    32
1.7.1   單體系統(tǒng)    32
1.7.2   分層系統(tǒng)    33
1.7.3   虛擬機    33
1.7.4   外核    34
1.7.5   客戶機－服務(wù)器模型    35
1.8   有關(guān)操作系統(tǒng)的研究    36
1.9   本書其他部分概要    37
1.10   公制單位    37
1.11   小結(jié)    38
習(xí)題    38
第2章   進程與線程    41
2.1  進程    41
2.1.1   進程模型    41
2.1.2   進程的創(chuàng)建    42
2.1.3   進程的終止    43
2.1.4   進程的層次結(jié)構(gòu)    44
2.1.5   進程的狀態(tài)    44
2.1.6   進程的實現(xiàn)    45
2.2   線程    46
2.2.1   線程模型    46
2.2.2   線程的使用    48
2.2.3   在用戶空間中實現(xiàn)線程    51
2.2.4   在內(nèi)核中實現(xiàn)線程    53
2.2.5   混合實現(xiàn)    53
2.2.6   調(diào)度程序激活機制    54
2.2.7   彈出式線程    54
2.2.8   使單線程代碼多線程化    55
2.3   進程間通信    57
2.3.1   競爭條件    57
2.3.2   臨界區(qū)    58
2.3.3   忙等待的互斥    59
2.3.4   休眠與喚醒    61
2.3.5   信號量    63
2.3.6   互斥信號量    64
2.3.7   管程    65
2.3.8   消息傳遞    69
2.3.9   屏障    70
2.4   經(jīng)典的IPC問題    71
2.4.1   哲學(xué)家就餐問題    71
2.4.2   讀者-寫者問題    73
2.4.3   睡眠理發(fā)師問題    74
2.5   調(diào)度    75
2.5.1   調(diào)度介紹    76
2.5.2   批處理系統(tǒng)中的調(diào)度    79
2.5.3   交互式系統(tǒng)中的調(diào)度    81
2.5.4   實時系統(tǒng)中的調(diào)度    84
2.5.5   策略和機制    85
2.5.6   線程調(diào)度    85
2.6   有關(guān)進程和線程的研究    86
2.7   小結(jié)    87
習(xí)題    87
第3章   死鎖    91
3.1   資源    91
3.1.1   可搶占資源和不可搶占資源91
3.1.2   資源獲取    92
3.2   死鎖概述    93
3.2.1   死鎖的條件    93
3.2.2   死鎖建模    94
3.3   鴕鳥算法    95
3.4   死鎖檢測和死鎖恢復(fù)    96
3.4.1   每種類型一個資源的死鎖檢測96
3.4.2   每種類型多個資源的死鎖檢測97
3.4.3   從死鎖中恢復(fù)    99
3.5   死鎖避免    100
3.5.1   資源軌跡圖    100
3.5.2   安全狀態(tài)和不安全狀態(tài)    101
3.5.3   單個資源的銀行家算法    101
3.5.4   多個資源的銀行家算法    102
3.6   死鎖預(yù)防    103
3.6.1   破壞互斥條件    103
3.6.2   破壞占有和等待條件    103
3.6.3   破壞不可搶占條件    104
3.6.4   破壞循環(huán)等待條件    104
3.7   其他問題    104
3.7.1   兩階段加鎖    105
3.7.2   非資源死鎖    105
3.7.3   饑餓    105
3.8   有關(guān)死鎖的研究    105
3.9   小結(jié)    106
習(xí)題    106
第4章   存儲管理    109
4.1   基本存儲管理    109
4.1.1   無交換或分頁的單道程序設(shè)計109
4.1.2   固定分區(qū)的多道程序設(shè)計110
4.1.3   建立多道程序設(shè)計模型    111
4.1.4   多道程序設(shè)計系統(tǒng)的性能分析111
4.1.5   重定位和保護    112
4.2   交換    113
4.2.1   使用位圖的存儲管理    114
4.2.2   使用鏈表的存儲管理    115
4.3   虛擬存儲器    116
4.3.1   分頁    116
4.3.2   頁表    118
4.3.3   轉(zhuǎn)換檢測緩沖區(qū)    121
4.3.4   倒排頁表    122
4.4   頁面置換算法    123
4.4.1   最優(yōu)頁面置換算法    123
4.4.2   最近未使用頁面置換算法124
4.4.3   先進先出頁面置換算法    124
4.4.4   第二次機會頁面置換算法125
4.4.5   時鐘頁面置換算法    125
4.4.6   最近最少使用頁面置換算法125
4.4.7   用軟件模擬LRU    126
4.4.8   工作集頁面置換算法    127
4.4.9   工作集時鐘頁面置換算法    129
4.4.10   頁面置換算法小結(jié)    130
4.5   建立頁面置換算法模型    131
4.5.1   Belady異常    131
4.5.2   棧式算法    131
4.5.3   距離字符串    133
4.5.4   頁面失效率預(yù)測    133
4.6   分頁系統(tǒng)的設(shè)計問題    133
4.6.1   局部分配策略與全局分配策略    134
4.6.2   負載控制    135
4.6.3   頁面大小    136
4.6.4   分離的指令空間和數(shù)據(jù)空間136
4.6.5   共享頁面    137
4.6.6   清除策略    138
4.6.7   虛擬存儲器接口    138
4.7   有關(guān)實現(xiàn)的問題    138
4.7.1   與分頁有關(guān)的操作系統(tǒng)    138
4.7.2   頁面失效處理    139
4.7.3   指令備份    139
4.7.4   鎖定內(nèi)存中的頁面    140
4.7.5   后備存儲    140
4.7.6   策略和機制的分離    141
4.8   分段    142
4.8.1   純分段的實現(xiàn)    144
4.8.2   分段和分頁結(jié)合：MULTICS144
4.8.3   分段和分頁結(jié)合：Intel Pentium146
4.9   有關(guān)存儲管理的研究    149
4.10   小結(jié)    149
習(xí)題    150
第5章   輸入/輸出    153
5.1   I/O硬件組成原理    153
5.1.1   I/O設(shè)備    153
5.1.2   設(shè)備控制器    153
5.1.3   內(nèi)存映射I/O    154
5.1.4   直接存儲器存取    156
5.1.5   重溫中斷    158
5.2   I/O軟件原理    160
5.2.1   I/O軟件的目標(biāo)    160
5.2.2   程序控制I/O    161
5.2.3   中斷驅(qū)動I/O    162
5.2.4   使用DMA的I/O    163
5.3   I/O軟件層次    163
5.3.1   中斷處理程序    163
5.3.2   設(shè)備驅(qū)動程序    164
5.3.3   與設(shè)備無關(guān)的I/O軟件    166
5.3.4   用戶空間的I/O軟件    169
5.4   盤    170
5.4.1   盤的硬件    170
5.4.2   磁盤格式化    179
5.4.3   磁盤臂調(diào)度算法    181
5.4.4   錯誤處理    183
5.4.5   穩(wěn)定存儲器    185
5.5   時鐘    187
5.5.1   時鐘硬件    187
5.5.2   時鐘軟件    187
5.5.3   軟定時器    189
5.6   面向字符的終端    190
5.6.1   RS-232終端硬件    190
5.6.2   輸入軟件    192
5.6.3   輸出軟件    194
5.7   圖形用戶界面    195
5.7.1   個人計算機鍵盤、鼠標(biāo)和顯示器硬件    195
5.7.2   輸入軟件    198
5.7.3   Windows輸出軟件    198
5.8   網(wǎng)絡(luò)終端    203
5.8.1   X Window系統(tǒng)    203
5.8.2   SLIM網(wǎng)絡(luò)終端    206
5.9   電源管理    207
5.9.1   硬件問題    208
5.9.2   操作系統(tǒng)問題    209
5.9.3   退化的操作    212
5.10   關(guān)于輸入/輸出的研究    212
5.11   小結(jié)    213
習(xí)題    213
第6章   文件系統(tǒng)    217
6.1   文件    217
6.1.1   文件命名    217
6.1.2   文件結(jié)構(gòu)    218
6.1.3   文件類型    219
6.1.4   文件存取    220
6.1.5   文件屬性    221
6.1.6   文件操作    221
6.1.7   使用文件系統(tǒng)調(diào)用的一個示例程序222
6.1.8   內(nèi)存映射文件    224
6.2   目錄    224
6.2.1   一級目錄系統(tǒng)    224
6.2.2   兩級目錄系統(tǒng)    225
6.2.3   層次目錄系統(tǒng)    225
6.2.4   路徑名    225
6.2.5   目錄操作    227
6.3   文件系統(tǒng)的實現(xiàn)    228
6.3.1   文件系統(tǒng)布局    228
6.3.2   文件的實現(xiàn)    228
6.3.3   目錄的實現(xiàn)    231
6.3.4   共享文件    233
6.3.5   磁盤空間管理    234
6.3.6   文件系統(tǒng)的可靠性    237
6.3.7   文件系統(tǒng)性能    242
6.3.8   日志結(jié)構(gòu)文件系統(tǒng)    244
6.4   文件系統(tǒng)實例    246
6.4.1   CD-ROM文件系統(tǒng)    246
6.4.2   CP/M文件系統(tǒng)    249
6.4.3   MS-DOS文件系統(tǒng)    250
6.4.4   Windows 98文件系統(tǒng)    252
6.4.5   UNIX V7文件系統(tǒng)    254
6.5   有關(guān)文件系統(tǒng)的研究    256
6.6   小結(jié)    256
習(xí)題    256
第7章   多媒體操作系統(tǒng)    259
7.1   多媒體簡介    259
7.2   多媒體文件    261
7.2.1   音頻編碼    262
7.2.2   視頻編碼    263
7.3   視頻壓縮    265
7.3.1   JPEG標(biāo)準(zhǔn)    265
7.3.2   MPEG標(biāo)準(zhǔn)    267
7.4   多媒體進程調(diào)度    268
7.4.1   調(diào)度同質(zhì)進程    268
7.4.2   一般實時調(diào)度    268
7.4.3   速率單調(diào)調(diào)度    270
7.4.4   最早最終時限優(yōu)先調(diào)度    270
7.5   多媒體文件系統(tǒng)范型    272
7.5.1   VCR控制功能    272
7.5.2   近似視頻點播    273
7.5.3   具有VCR功能的近似視頻點播274
7.6   文件存放    276
7.6.1   在單個磁盤上存放文件    276
7.6.2   兩個替代的文件組織策略276
7.6.3   近似視頻點播的文件存放278
7.6.4   在單個磁盤上存放多個文件279
7.6.5   在多個磁盤上存放文件    281
7.7   高速緩存    282
7.7.1   塊高速緩存    282
7.7.2   文件高速緩存    283
7.8   多媒體磁盤調(diào)度    284
7.8.1   靜態(tài)磁盤調(diào)度    284
7.8.2   動態(tài)磁盤調(diào)度    285
7.9   有關(guān)多媒體的研究    286
7.10   小結(jié)    286
習(xí)題    287
第8章   多處理機系統(tǒng)    289
8.1   多處理機    290
8.1.1   多處理機硬件    290
8.1.2   多處理機操作系統(tǒng)類型    294
8.1.3   多處理機同步    297
8.1.4   多處理機調(diào)度    299
8.2   多計算機    302
8.2.1   多計算機硬件    302
8.2.2   低層通信軟件    305
8.2.3   用戶層通信軟件    307
8.2.4   遠程過程調(diào)用    309
8.2.5   分布式共享存儲器    310
8.2.6   多計算機調(diào)度    313
8.2.7   負載平衡    313
8.3   分布式系統(tǒng)    315
8.3.1   網(wǎng)絡(luò)硬件    317
8.3.2   網(wǎng)絡(luò)服務(wù)和網(wǎng)絡(luò)協(xié)議    319
8.3.3   基于文檔的中間件    321
8.3.4   基于文件系統(tǒng)的中間件    322
8.3.5   基于共享對象的中間件    326
8.3.6   基于協(xié)作的中間件    329
8.4   有關(guān)多處理機系統(tǒng)的研究    332
8.5   小結(jié)    333
習(xí)題    333
第9章   安全    337
9.1   安全環(huán)境    337
9.1.1   威脅    337
9.1.2   入侵者    338
9.1.3   數(shù)據(jù)意外遺失    338
9.2   密碼學(xué)基礎(chǔ)    338
9.2.1   秘密密鑰加密    339
9.2.2   公鑰加密體制    339
9.2.3   單向函數(shù)    340
9.2.4   數(shù)字簽名    340
9.3   用戶驗證    341
9.3.1   使用口令驗證    341
9.3.2   使用實際物體的驗證    346
9.3.3   使用生物識別的驗證    347
9.3.4   對策    348
9.4   來自系統(tǒng)內(nèi)部的攻擊    349
9.4.1   特洛伊木馬    349
9.4.2   登錄欺騙    350
9.4.3   邏輯炸彈    350
9.4.4   后門陷阱    350
9.4.5   緩沖區(qū)溢出    351
9.4.6   一般安全性攻擊    352
9.4.7   著名的安全缺陷    353
9.4.8   安全設(shè)計原則    354
9.5   來自系統(tǒng)外部的攻擊    355
9.5.1   病毒破壞的場景    355
9.5.2   病毒工作方式    356
9.5.3   病毒如何傳播    360
9.5.4   反病毒技術(shù)和抑制反病毒技術(shù)361
9.5.5   因特網(wǎng)蠕蟲    365
9.5.6   移動代碼    366
9.5.7   Java安全性    369
9.6   保護機制    371
9.6.1   保護域    371
9.6.2   訪問控制列表    372
9.6.3   權(quán)能字    374
9.7   可信系統(tǒng)    375
9.7.1   可信計算基    376
9.7.2   安全系統(tǒng)的形式模型    377
9.7.3   多級安全    377
9.7.4   橘皮書安全標(biāo)準(zhǔn)    379
9.7.5   隱蔽信道    380
9.8   有關(guān)安全的研究    382
9.9   小結(jié)    382
習(xí)題    383
第10章   實例研究1：UNIX和Linux387
10.1   UNIX的歷史    387
10.1.1   UNICS    387
10.1.2   PDP-11上的UNIX    388
10.1.3   可移植的UNIX    388
10.1.4   伯克利UNIX    389
10.1.5   標(biāo)準(zhǔn)UNIX    389
10.1.6   MINIX    390
10.1.7   Linux    390
10.2   UNIX概述    392
10.2.1   UNIX的目標(biāo)    392
10.2.2   UNIX接口    392
10.2.3   UNIX shell    393
10.2.4   UNIX實用程序    394
10.2.5   內(nèi)核結(jié)構(gòu)    395
10.3   UNIX進程    396
10.3.1   基本概念    396
10.3.2   UNIX中的進程管理系統(tǒng)調(diào)用398
10.3.3   UNIX中進程的實現(xiàn)    401
10.3.4   引導(dǎo)UNIX    406
10.4   UNIX中的存儲管理    407
10.4.1   基本概念    408
10.4.2   UNIX里的存儲管理系統(tǒng)調(diào)用    409
10.4.3   UNIX中存儲管理的實現(xiàn)    410
10.5   UNIX中的輸入/輸出    415
10.5.1   基本概念    415
10.5.2   UNIX中的輸入/輸出系統(tǒng)調(diào)用    417
10.5.3   UNIX中輸入/輸出的實現(xiàn)417
10.5.4   流    419
10.6   UNIX文件系統(tǒng)    420
10.6.1   基本概念    420
10.6.2   UNIX中的文件系統(tǒng)調(diào)用423
10.6.3   UNIX中文件系統(tǒng)的實現(xiàn)425
10.6.4   NFS：網(wǎng)絡(luò)文件系統(tǒng)    429
10.7   UNIX中的安全    432
10.7.1   基本概念    432
10.7.2   UNIX中的安全系統(tǒng)調(diào)用434
10.7.3   UNIX中安全的實現(xiàn)    434
10.8   小結(jié)    435
習(xí)題    435
第11章   實例研究2：Windows 2000439
11.1   Windows 2000 的歷史    439
11.1.1   MS-DOS    439
11.1.2   Windows 95/98/Me    439
11.1.3   Windows NT    440
11.1.4   Windows 2000    441
11.2   Windows 2000編程    444
11.2.1   Win32應(yīng)用程序接口    444
11.2.2   注冊表    445
11.3   系統(tǒng)結(jié)構(gòu)    447
11.3.1   操作系統(tǒng)結(jié)構(gòu)    447
11.3.2   對象的實現(xiàn)    452
11.3.3   環(huán)境子系統(tǒng)    456
11.4   Windows 2000的進程和線程458
11.4.1   基本概念    458
11.4.2   管理作業(yè)、進程、線程和纖程的
API調(diào)用    460
11.4.3   進程和線程的實現(xiàn)    461
11.4.4   MS-DOS仿真    465
11.4.5   引導(dǎo)Windows 2000    466
11.5   存儲管理    467
11.5.1   基本概念    467
11.5.2   存儲管理的系統(tǒng)調(diào)用    470
11.5.3   存儲管理的實現(xiàn)    470
11.6   Windows 2000中的輸入/輸出474
11.6.1   基本概念    474
11.6.2   輸入/輸出的API調(diào)用    475
11.6.3   I/O實現(xiàn)    476
11.6.4   設(shè)備驅(qū)動程序    476
11.7   Windows 2000文件系統(tǒng)    478
11.7.1   基本概念    478
11.7.2   Windows 2000中的文件系統(tǒng)API
調(diào)用    478
11.7.3   Windows 2000中文件系統(tǒng)的實現(xiàn)    480
11.8   Windows 2000中的安全    486
11.8.1   基本概念    487
11.8.2   安全API調(diào)用    487
11.8.3   安全的實現(xiàn)    488
11.9   Windows 2000中的高速緩存機制489
11.10   小結(jié)    490
習(xí)題    491
第12章   操作系統(tǒng)設(shè)計    493
12.1   設(shè)計問題的本質(zhì)    493
12.1.1   目標(biāo)    493
12.1.2   設(shè)計操作系統(tǒng)為什么困難494
12.2   接口設(shè)計    495
12.2.1   指導(dǎo)原則    495
12.2.2   范型    496
12.2.3   系統(tǒng)調(diào)用接口    498
12.3   實現(xiàn)    499
12.3.1   系統(tǒng)結(jié)構(gòu)    499
12.3.2   機制與策略    501
12.3.3   正交性    502
12.3.4   命名    502
12.3.5   綁定的時機    503
12.3.6   靜態(tài)與動態(tài)結(jié)構(gòu)    503
12.3.7   自頂向下與自底向上的實現(xiàn)504
12.3.8   實用技術(shù)    505
12.4   性能    508
12.4.1   操作系統(tǒng)為什么運行緩慢508
12.4.2   什么應(yīng)該優(yōu)化    508
12.4.3   空間-時間的權(quán)衡    508
12.4.4   高速緩存    510
12.4.5   線索    511
12.4.6   利用局部性    511
12.4.7   優(yōu)化常見的情況    511
12.5   項目管理    512
12.5.1   人月神話    512
12.5.2   團隊結(jié)構(gòu)    513
12.5.3   經(jīng)驗的作用    514
12.5.4   沒有銀彈    514
12.6   操作系統(tǒng)設(shè)計的趨勢    514
12.6.1   大型地址空間操作系統(tǒng)515
12.6.2   聯(lián)網(wǎng)    515
12.6.3   并行系統(tǒng)與分布式系統(tǒng)515
12.6.4   多媒體    516
12.6.5   電池供電的計算機    516
12.6.6   嵌入式系統(tǒng)    516
12.7   小結(jié)    516
習(xí)題    517
第13章   閱讀材料及參考文獻    519
13.1   進行深入閱讀的建議    519
13.1.1   簡介及概要    519
13.1.2   進程和線程    519
13.1.3   死鎖    520
13.1.4   存儲管理    520
13.1.5   輸入/輸出    520
13.1.6   文件系統(tǒng)    520
13.1.7   多媒體操作系統(tǒng)    521
13.1.8   多處理機系統(tǒng)    521
13.1.9   安全    522
13.1.10   UNIX和Linux    523
13.1.11   Windows 2000    523
13.1.12   設(shè)計原理    523
13.2   按字母順序排序的參考文獻525
索引    537