1 計算機體系

存儲器的層次結(jié)構(gòu)與高速緩存

當(dāng)存儲器的層次結(jié)構(gòu)滿足以下條件時：
a 容量遞增
b 存取時間遞增
c 訪問頻率遞減
注：條件c有效的基礎(chǔ)是訪問的局部性原理
可以發(fā)現(xiàn)，總的平均存取時間更接近于第一級存儲器的存取時間而不是第二級存儲器的存取時間。
這種發(fā)現(xiàn)同樣適用于緩存系統(tǒng)的設(shè)計中嘿般，其中况毅，保證緩存的高頻訪問是主要原則

關(guān)于訪問的局部性
局部性通常有兩種形式：

時間局部性(temporal locality)
時間局部性指的是：被引用過一次的存儲器位置在未來會被多次引用（通常在循環(huán)中）蒙兰。

空間局部性(spatial locality)
如果一個存儲器的位置被引用，那么將來他附近的位置也會被引用春缕。

假如, 有95%的存儲器存取發(fā)生在緩存中睁枕，訪問緩存0.1ms官边，訪問硬盤1ms，則訪問一個字節(jié)的平均存取時間可表示為：
0.950.1+0.05（1+0.1）=0.095+0.055=0.15ms

緩存系統(tǒng)的兩個目標(biāo)：
1 重復(fù)利用未過期的緩存數(shù)據(jù)外遇，降低磁盤io次數(shù)注簿；
2 由于數(shù)據(jù)訪問的局部性現(xiàn)象，一次讀取一塊連續(xù)的數(shù)據(jù)以滿足一次存儲器訪問時跳仿，很可能僅僅這的多次訪問的數(shù)據(jù)都是該塊中的其他字節(jié)诡渴，這樣也可降低磁盤io次數(shù)；

緩存系統(tǒng)的設(shè)計
1 緩存的大小
2 塊（交換數(shù)據(jù)）大小
3 映射函數(shù)
4 置換算法塔嬉，如LRU
5 寫策略(緩存內(nèi)的數(shù)據(jù)被修改玩徊，需要回寫保存)
6 緩存的級數(shù)

數(shù)據(jù)訪問的局部性原理是保證緩存命率的重要基礎(chǔ)，如果沒有緩存的高命中率谨究，則這個緩存系統(tǒng)是不成功的恩袱。

IO操作

可編程IO

CPU直接與IO模塊進行交互，并等待IO模塊處理完成胶哲，在此期間畔塔，處理器必須不斷詢問IO模塊的狀態(tài)，嚴(yán)重降低了CPU的利用率鸯屿；

中斷驅(qū)動IO

由處理器給IO模塊發(fā)送IO命令澈吨，然后處理器繼續(xù)做其他工作。當(dāng)IO模塊準(zhǔn)備好與處理器交換數(shù)據(jù)時寄摆，發(fā)送中斷處理信號給CPU谅辣。CPU接收到中斷信號后開始與IO模塊進行數(shù)據(jù)傳送，然后恢復(fù)處理器之前的執(zhí)行過程婶恼。

多中斷的處理方式：

1. 順序（排隊）
2. 優(yōu)先級（插隊）

直接內(nèi)存存取DMA

上述兩種方式的數(shù)據(jù)傳送都依賴于CPU桑阶，因此它們有兩個固有的缺陷：
1 IO傳送速度受限于處理器提供服務(wù)的速度；
2 處理器忙于管理IO傳送的工作勾邦，必須執(zhí)行很多的指令以完成IO傳送蚣录；

當(dāng)需要移動大量數(shù)據(jù)時，需要使用一種更為有效的技術(shù)眷篇，DMA.DMA可以代替CPU完成IO的讀寫工作萎河。當(dāng)CPU需要讀或?qū)懸粔K數(shù)據(jù)時，它可以給DMA產(chǎn)生一條命令蕉饼，之后處理器繼續(xù)其他工作虐杯，DMA負責(zé)直接與存儲器交互，完成IO動作椎椰。當(dāng)傳送完成后厦幅，DMA模塊發(fā)送一個中斷信號給CPU。因此慨飘，只有在開始傳送和傳送結(jié)束后處理器才會參與确憨。

DMA模塊需要控制總線以便與存儲器進行數(shù)據(jù)傳送，這可能與CPU形成總線爭用導(dǎo)致CPU執(zhí)行速度變慢（但這不是中斷瓤的，不會發(fā)生CPU上下文切換）休弃，但盡管如此，對于多字IO傳送來說圈膏，DMA比上面兩種IO方式更有效塔猾。

2 操作系統(tǒng)概述

操作系統(tǒng)需要的必要條件：

1. CPU從內(nèi)存的不同部分取指的能力；
2. 內(nèi)存保護：防止用戶程序改變包含操作系統(tǒng)程序的內(nèi)存區(qū)域稽坤；
3. 定時器：防止用戶程序獨占CPU丈甸，保證操作系統(tǒng)重新獲得控制權(quán)糯俗；
4. 特權(quán)指令：特權(quán)指令只能由操作系統(tǒng)執(zhí)行；
5. 中斷：提高操作系統(tǒng)讓用戶程序放棄控制權(quán)或從用戶程序獲得控制權(quán)時的靈活性睦擂；

多任務(wù)操作系統(tǒng)的必要條件：內(nèi)存管理得湘、調(diào)度管理
多用戶操作系統(tǒng)的必要條件：信息保護和安全

內(nèi)存管理的五個任務(wù)：

1. 進程隔離
2. 自動分配的管理
3. 支持模塊化程序設(shè)計
4. 保護和訪問控制
5. 長期存儲

信息保護和安全的四個任務(wù)：

1. 可用性，保護系統(tǒng)不被打斷顿仇；
2. 保密性淘正，保證用戶不能督導(dǎo)未授權(quán)訪問的數(shù)據(jù)；
3. 數(shù)據(jù)完整性臼闻，保護數(shù)據(jù)不被未授權(quán)的修改鸿吆；
4. 認證，身份認證與識別述呐；

調(diào)度和資源管理的任務(wù)：

1. 調(diào)度公平性
2. 有差別的響應(yīng)
3. 有效性

3 進程

進程的狀態(tài)模型

進程組成

進程由用戶程序惩淳、用戶數(shù)據(jù)、系統(tǒng)棧乓搬、進程控制塊組成黎泣；

進程切換

進程切換也叫進程上下文切換，工作量較大
進程切換的時機：中斷（時鐘中斷缤谎、I/O中斷抒倚、內(nèi)存失效）、陷阱及系統(tǒng)調(diào)用
進程的切換步驟：

1. 保存處理器上線文環(huán)境坷澡，包括程序計數(shù)器和其他寄存器托呕；

2. 更新當(dāng)前運行態(tài)進程的進程控制塊，包括將進程的狀態(tài)改變到另一狀態(tài)（就緒態(tài)频敛、阻塞態(tài)或退出態(tài)）项郊。還必須更新其他相關(guān)域，包括離開運行態(tài)的原因和記賬信息斟赚。

3. 將進程的進程控制塊移到相應(yīng)的隊列（就緒着降、在事件i處阻塞、就緒/掛起）

4. 選擇另一個進程執(zhí)行拗军。

5. 更新所選擇進程的進程控制塊任洞，包括將進程狀態(tài)變?yōu)檫\行態(tài)。

6. 更新內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)发侵，這取決于如何管理地址轉(zhuǎn)換交掏。

7. 恢復(fù)處理器在被選擇的進程最近一次切換出運行態(tài)時的上線文環(huán)境。

用戶進程與系統(tǒng)進程的三種關(guān)系模型

1. 分離的內(nèi)核
2. 在用戶進程中執(zhí)行操作系統(tǒng)程序（UNIX）
3. 操作系統(tǒng)進程作為分離的進程執(zhí)行

模式切換

模式的切換在中斷處理階段完成刃鳄。
進程的切換在中斷盅弛、陷阱或系統(tǒng)調(diào)用時發(fā)生。
在用戶進程與系統(tǒng)進程一體的進程模型下，相比于進程切換挪鹏，模式切換開銷更低见秽。

4 線程

線程分類

用戶級線程：由一個在進程的用戶空間中運行的線程庫創(chuàng)建并管理，用戶級線程對操作系統(tǒng)是未知的讨盒。用戶級線程是非常高效的张吉，因為從一個線程切換到另一個同進程的線程不需要進行狀態(tài)轉(zhuǎn)換（模式切換）。但是催植，一個進程中一次只能有一個用戶級線程可以執(zhí)行，如果一個線程發(fā)生阻塞勺择，整個進程的多個線程都會被阻塞创南。
內(nèi)核級線程：進程內(nèi)包含的內(nèi)核級線程由內(nèi)核維護，由于內(nèi)核認識它們省核，因而同一個進程中的多個線程可以在多個處理器上并行執(zhí)行稿辙。一個線程的阻塞不會阻塞整個進程的線程，但當(dāng)一個線程切換到另一個線程時就需要進行模式轉(zhuǎn)換气忠。

Linux的線程

Linux其實本事沒有線程的概念邻储，只是為了迎合開發(fā)者的需要而使用了一個所謂輕量級進程（POSIX線程），你從這兩者區(qū)別也可以發(fā)現(xiàn)旧噪，輕量級進程最大的用途在于可以共享一些資源吨娜，如地址空間，打開文件淘钟。所以宦赠，事實上Linux實現(xiàn)多線程應(yīng)用程序的方式就是用輕量級進程來代替線程。
雖然Linux中線程沒有單獨的數(shù)據(jù)結(jié)構(gòu)米母，進程和線程差別也不大勾扭，但是進程在切換的時候要切換地址空間，而線程在切換的時候判斷一下是不是在一個進程組铁瞒，如果屬于一個進程組妙色，只是切換一下上下文而已，所以開銷要小的多

并發(fā)：互斥和同步

并發(fā)關(guān)鍵詞

原子性操作：操作不可中斷慧耍、不可分割性身辨，該操作要么執(zhí)行完成，要么不執(zhí)行芍碧；
臨界資源：是一種共享資源栅表，會被多個進程或線程使用；
臨界區(qū)：是一段代碼师枣，這段代碼會對臨界資源進行讀寫怪瓶，臨界區(qū)是互斥的，也就是如果一個進程處于臨界區(qū)時，其他進程是不能執(zhí)行臨界區(qū)代碼的洗贰；
競爭條件：多個進程或者線程同時讀或者寫共享數(shù)據(jù)時找岖，最終的結(jié)果依賴于多個進程的執(zhí)行順序的情況，稱為競爭條件敛滋；

互斥

硬件支持：中斷禁用许布、專用機器指令：CAS

信號量

信號量
二元信號量
自旋鎖

管程

消息傳遞

讀寫者問題

并發(fā)：死鎖和饑餓

死鎖的檢測方法

假設(shè)有i個進程P(1..i)，有m個資源R(1..m)绎晃，我們使用R(im)表示進程i請求的資源蜜唾，使用Q(im)表示已分配給進程i的資源，使用V(m)表示剩余的資源庶艾。則可以：
1 在Q(im)矩陣中袁余，找出一個未分配任何資源的進程Pi，并標(biāo)記該進程咱揍；
2 初始化一個臨時向量W颖榜，令W等于V向量；
3 在R(im)矩陣中煤裙，查找下標(biāo)i掩完，使進程i當(dāng)前未標(biāo)記且R的第i行小于等于W，如果找不到這樣的行硼砰，終止算法且蓬；
4 如果找到這樣的行，標(biāo)記進程i题翰，并把Q矩陣中的第i行加到W中缅疟，令Wk=Q(ik)+Wk。返回步驟3
當(dāng)且僅當(dāng)這個算法最后結(jié)果有未標(biāo)記的進程時遍愿，表明存在死鎖存淫。

死鎖的恢復(fù)方法

取消所有死鎖的進程，撤銷存在死鎖的進程的資源沼填。

銀行家算法

與死鎖的檢測方法類似桅咆。又叫資源分配拒絕策略，通過該算法檢測到請求的資源會導(dǎo)致死鎖時坞笙，則拒絕資源分配請求岩饼。

哲學(xué)家就餐問題

解決方案：
不影響并發(fā)的情況下：
1 增加總資源：增加5套叉子
2 降低資源需求：教會哲學(xué)家只使用一支叉子吃飯
降低并發(fā)的情況下：
1 一次只允許（N-1）個人吃飯，剩下的一個人等待直到有人吃完薛夜；
2 引入服務(wù)員籍茧，由服務(wù)員決定是否可以獲得叉子；
3 把筷子兩兩分對梯澜，哲學(xué)家一次獲取一雙寞冯；

內(nèi)存屏障

解決編譯器及處理器的指令重排問題，禁止指令重排

針對編譯器及處理器的指令：
mb() 讀寫指令 內(nèi)存屏障，吮龄，保證代碼mb()之前的任何讀寫操作無法穿透屏障
rmb() 讀取指令 內(nèi)存屏障俭茧，保證代碼rmb()之前的任何讀操作無法穿透屏障
wmb() 寫指令內(nèi)存屏障，保證代碼wmb()之前的任何寫操作無法穿透屏障

針對編譯器的指令：
barrier() 更輕量級漓帚，是mb()的簡化版母债，僅控制編譯器的行為。若確認處理器不會進行重排尝抖，則可以使用這個操作毡们。

5 內(nèi)存管理

5.1 內(nèi)存管理的目標(biāo)

重定位
保護
共享

5.2 內(nèi)存管理相關(guān)技術(shù)

5.2.1內(nèi)存分區(qū)

• 固定分區(qū)，有內(nèi)部碎片昧辽，但簡單
• 動態(tài)分區(qū)衙熔，有外部碎片，需要壓縮奴迅，無內(nèi)部碎片
• 伙伴系統(tǒng)，動態(tài)二分挺据，動態(tài)合并取具，屬于一種折中方案

放置算法
固定分區(qū)：由于其分區(qū)大小相同，僅需要找到可用的分區(qū)即可扁耐；
動態(tài)分區(qū)：有三種算法暇检，1最佳適配，尋找差距最小的分區(qū)婉称； 2 首次適配块仆，第一個找到的可用的分區(qū) ；3 下次適配王暗，從上次放置位置開始掃描內(nèi)存悔据，找到可用分區(qū)；
其中首次適配效率最好俗壹，最佳適配會產(chǎn)生大量及其微小的碎片，需要頻繁壓縮內(nèi)存。下次適配則會將分配幾種與內(nèi)存的末端空間灭翔，導(dǎo)致這里出現(xiàn)大量碎片蝠检。

5.2.2 重定位

解決進程在被換出之后再次換入內(nèi)存后物理地址發(fā)生變化后，不會影響處理器的訪問涎显。重定位技術(shù)還能通過界限寄存器對內(nèi)存訪問進行保護坤检。
邏輯地址：處理器使用的地址，不會隨著進程的換入換出而改變期吓；
物理地址：進程在內(nèi)存中的實際地址早歇，會隨著進程的換入換出而改變；
分頁

5.2.3 分頁

內(nèi)存被劃分為大小固定的相等的塊，且塊相對比較小缺前，每個進程也被分成同樣大小的塊蛀醉，進程中的塊成為頁（page），內(nèi)存中的塊成為頁框（frame）衅码；頁可以被裝載入頁框中拯刁。
分頁技術(shù)沒有外部碎片，且僅在進程最后一個塊中產(chǎn)生微小的內(nèi)部碎片逝段。
為了知道程序在哪些frame中垛玻，操作系統(tǒng)會為每個進程維護一個頁表（page table）。頁表給出了每個進程的每一頁所對應(yīng)的frame的位置奶躯。
在程序中每一個邏輯地址包括兩部分：頁號和偏移量

5.2.4 分段

分段技術(shù)通過把程序及其相關(guān)的額數(shù)據(jù)劃分為幾個不同的段（segment）帚桩，可以對他們進行不同的權(quán)限控制（只讀、只執(zhí)行）嘹黔，段的大小是動態(tài)的账嚎，分段類似于動態(tài)分區(qū)。和分頁一樣儡蔓，采用分段技術(shù)時的邏輯地址也是兩部分：段號和偏移量

5.3.5 緩沖區(qū)溢出攻擊

緩沖區(qū)溢出又稱內(nèi)存越界郭蕉。
緩沖區(qū)溢出攻擊，是通過惡意覆蓋程序中緩沖區(qū)界限之外的內(nèi)存部分喂江，植入惡意代碼召锈。

6 虛擬內(nèi)存

實存
實際的內(nèi)存，稱為實存
虛存
虛擬內(nèi)存是計算機系統(tǒng)內(nèi)存管理的一種技術(shù)获询。它使得應(yīng)用程序認為它擁有連續(xù)的可用的內(nèi)存（一個連續(xù)完整的地址空間）涨岁，而實際上，它通常是被分隔成多個物理內(nèi)存碎片吉嚣，還有部分暫時存儲在外部磁盤存儲器上梢薪，在需要時進行數(shù)據(jù)交換
系統(tǒng)抖動
系統(tǒng)為了讀入新的頁而換出了即將會用的舊的頁，系統(tǒng)頻繁的換頁導(dǎo)致系統(tǒng)利用率急劇降低的情況尝哆，稱為系統(tǒng)抖動
駐留集
程序駐留在內(nèi)存中的部分沮尿，稱為駐留集