1、導(dǎo)論

與用戶交互的程序：

• 基于文本的shell
• 基于圖標(biāo)的圖形化用戶界面（GUI）

操作系統(tǒng)所處的位置：

操作系統(tǒng)所處的位置

多數(shù)計(jì)算機(jī)有兩種運(yùn)行模式：

• 內(nèi)核態(tài)（管態(tài)），操作系統(tǒng)運(yùn)行在此模式，能夠執(zhí)行任何指令贝或。
• 用戶態(tài)，用戶軟件運(yùn)行在此模式霞掺，使用機(jī)器指令中的子集砸紊。

操作系統(tǒng)的功能：

• 為用戶程序提供抽象
• 管理計(jì)算機(jī)資源

抽象是管理復(fù)雜性的一個(gè)關(guān)鍵传于。好的抽象可以把一個(gè)幾乎不可能管理的任務(wù)劃分為兩個(gè)可管理的部分：

• 有關(guān)抽象的定義和實(shí)現(xiàn)
• 隨時(shí)用這些抽象解決問題

操作系統(tǒng)發(fā)展歷史

1. 1945~1955：真空管和穿孔卡片
2. 1955~1965：晶體管和批處理系統(tǒng)
3. 1965~1980：集成電路芯片和多道程序設(shè)計(jì)
4. 1980~至今：個(gè)人計(jì)算機(jī)

計(jì)算機(jī)硬件

• CPU
• 存儲(chǔ)器
• 磁盤
• 磁帶
• I/O設(shè)備
• 總線

大型Pentium系統(tǒng)結(jié)構(gòu)：

大型Pentium系統(tǒng)結(jié)構(gòu)

Pentium系統(tǒng)的啟動(dòng)過(guò)程：

• 主板上有一個(gè)基本輸入輸出系統(tǒng)（BIOS），其中有底層I/O軟件醉顽。
• 計(jì)算機(jī)啟動(dòng)時(shí)沼溜，BIOS開始運(yùn)行。
• 首先檢查安裝RAM數(shù)量游添，鍵盤和其他基本設(shè)備是否已安裝并正常相應(yīng)系草。
• 開始掃描ISA和PCI總線并找出連接在上面的所有設(shè)備，記錄下來(lái)唆涝。
• 如果現(xiàn)有設(shè)備和系統(tǒng)上一次啟動(dòng)時(shí)的設(shè)備不同找都，則配置新的設(shè)備。
• BISO通過(guò)存儲(chǔ)在CMOS存儲(chǔ)器中的設(shè)備清單決定啟動(dòng)設(shè)備廊酣。
• 啟動(dòng)設(shè)備上的第一個(gè)扇區(qū)被讀入內(nèi)存并執(zhí)行能耻。
• 啟動(dòng)扇面末尾的分區(qū)表檢查的程序，確定哪個(gè)分區(qū)是活動(dòng)的亡驰。
• 從活動(dòng)分區(qū)讀入第二個(gè)啟動(dòng)裝載模塊晓猛，裝在模塊被讀入操作系統(tǒng)。
• 操作系統(tǒng)詢問BIOS凡辱，以獲得配置信息戒职。
• 系統(tǒng)檢查每種設(shè)備驅(qū)動(dòng)程序是否存在，有就將設(shè)備驅(qū)動(dòng)程序調(diào)入內(nèi)核透乾。
• 系統(tǒng)創(chuàng)建背景進(jìn)程洪燥，在終端上啟動(dòng)登錄程序或GUI。

操作系統(tǒng)概念

進(jìn)程：

進(jìn)程本質(zhì)是正在執(zhí)行的一個(gè)程序乳乌。與一個(gè)進(jìn)程有關(guān)的所有信息捧韵，除了該進(jìn)程自身地址空間的內(nèi)容以外，均存放在操作系統(tǒng)的一張表中钦扭，稱為進(jìn)程表（數(shù)組或鏈表結(jié)構(gòu)）纫版。

地址空間：

現(xiàn)代操作系統(tǒng)通常使用虛擬內(nèi)存技術(shù)。操作系統(tǒng)可以把部分地址空間裝入主存客情，部分留在磁盤上其弊，在需要時(shí)再交換它們。

文件：

大多數(shù)系統(tǒng)都有目錄結(jié)構(gòu)膀斋，目錄項(xiàng)可以是文件或者目錄梭伐，構(gòu)成了一種層次結(jié)構(gòu)（文件系統(tǒng)）。進(jìn)程和文件層次都可以組織成樹狀結(jié)構(gòu)仰担，一般進(jìn)程的樹狀結(jié)構(gòu)層次不深糊识，而且是暫時(shí)的；文件樹的層次常常多達(dá)四層、五層或者更多層赂苗，存在時(shí)間可能達(dá)數(shù)年愉耙。

輸入/輸出：

所有計(jì)算機(jī)都有用來(lái)獲取輸入和產(chǎn)生輸出的物理設(shè)備。包括鍵盤拌滋、顯示器朴沿、打印機(jī)等。

保護(hù)：

例如UNIX系統(tǒng)中對(duì)文件實(shí)現(xiàn)保護(hù)败砂，三個(gè)3位保護(hù)字段（rwxrwxrwx）赌渣，分別表示所有者、所有者同組用戶昌犹、其他用戶的讀坚芜、寫、執(zhí)行權(quán)限斜姥。

shell：

UNIX的命令解釋器稱為shell鸿竖，不是操作系統(tǒng)的一部分。shell是終端用戶與操作系統(tǒng)之間的界面疾渴，除非用戶使用的是GUI界面千贯。

系統(tǒng)調(diào)用

系統(tǒng)調(diào)用read(fd, &buffer, nbytes)函數(shù)的過(guò)程：

1. 參數(shù)nbytes壓棧
2. 參數(shù)&buffer壓棧
3. 參數(shù)fd壓棧
4. 對(duì)庫(kù)過(guò)程read進(jìn)行實(shí)際調(diào)用
5. 把系統(tǒng)調(diào)用的編號(hào)放在寄存器中
6. 執(zhí)行TRAP指令，切換到內(nèi)核態(tài)搞坝，在內(nèi)核中一個(gè)固定地址開始執(zhí)行
7. 內(nèi)核代碼檢查系統(tǒng)調(diào)用編號(hào)，發(fā)出系統(tǒng)調(diào)用處理指令
8. 系統(tǒng)調(diào)用句柄執(zhí)行
9. 控制返回給用戶空間庫(kù)過(guò)程
10. 以通常的過(guò)程調(diào)用返回的方式魁袜，返回到用戶程序
11. 用戶程序清除堆椬椋空間

完成系統(tǒng)調(diào)用read的11個(gè)步驟

操作系統(tǒng)結(jié)構(gòu)

• 單體系統(tǒng)
• 層次式系統(tǒng)
• 微內(nèi)核
• 客戶機(jī)-服務(wù)器模式
• 虛擬機(jī)
• 外核

C語(yǔ)言

編譯C和頭文件，構(gòu)件可執(zhí)行程序的過(guò)程：

C程序編譯過(guò)程

2峰弹、進(jìn)程與線程

進(jìn)程

進(jìn)程模型

操作系統(tǒng)中最核心的概念是進(jìn)程：這是對(duì)正在運(yùn)行程序的一個(gè)抽象店量。
一個(gè)進(jìn)程就是一個(gè)正在執(zhí)行程序的實(shí)例、包括程序計(jì)數(shù)器鞠呈、寄存器和變量的當(dāng)前值融师。

在多道程序設(shè)計(jì)中，一個(gè)CPU能在多個(gè)進(jìn)程之間來(lái)回快速切換蚁吝，達(dá)到（偽）并行效果旱爆。

一個(gè)進(jìn)程是某種類型的一個(gè)活動(dòng)，它有程序窘茁、輸入怀伦、輸出以及狀態(tài)。
單個(gè)處理器可以被若干進(jìn)程共享山林，它使用某種調(diào)度算法巨頂何時(shí)停止一個(gè)進(jìn)程的工作房待，并轉(zhuǎn)而為另一個(gè)進(jìn)程提供服務(wù)。

創(chuàng)建進(jìn)程

4種主要事件導(dǎo)致進(jìn)程的創(chuàng)建：

1. 系統(tǒng)初始化
2. 執(zhí)行了正在運(yùn)行的進(jìn)程所調(diào)用的進(jìn)程創(chuàng)建系統(tǒng)調(diào)用
3. 用戶請(qǐng)求創(chuàng)建一個(gè)新進(jìn)程
4. 一個(gè)批處理作業(yè)的初始化

在UNIX系統(tǒng)中，只有一個(gè)系統(tǒng)調(diào)用可以用來(lái)創(chuàng)建新進(jìn)程：fork桑孩。
這個(gè)系統(tǒng)調(diào)用會(huì)創(chuàng)建一個(gè)與調(diào)用進(jìn)程相同的副本拜鹤。
在調(diào)用fork后，這兩個(gè)進(jìn)程（父進(jìn)程和子進(jìn)程）擁有相同的存儲(chǔ)映像流椒、同樣的環(huán)境字符串和同樣打開的文件敏簿。
通常子進(jìn)程接著執(zhí)行execve系統(tǒng)調(diào)用，以修改其存儲(chǔ)映像并運(yùn)行一個(gè)新的程序镣隶。

在Windows系統(tǒng)中极谊，一個(gè)Win32函數(shù)調(diào)用CreateProcess即處理進(jìn)程的創(chuàng)建，也負(fù)責(zé)把正確的程序裝入新的進(jìn)程安岂。

在UNIX中轻猖，子進(jìn)程的初始地址空間是父進(jìn)程的一個(gè)副本，不可寫的內(nèi)存區(qū)是共享的域那，新進(jìn)程有可能共享其創(chuàng)建者的其他資源咙边。
在Windows中，從一開始父進(jìn)程的地址空間和子進(jìn)程的地址空間解釋不同的次员。

進(jìn)程的終止

進(jìn)程的終止通常由以下條件引起：

1. 正常退出（自愿的）
2. 出錯(cuò)退出（自愿的）
3. 嚴(yán)重錯(cuò)誤（非自愿）
4. 被其他進(jìn)程殺死（非自愿）

進(jìn)程的層次結(jié)構(gòu)

在UNIX系統(tǒng)中败许，進(jìn)程只有一個(gè)父進(jìn)程，但可以有多個(gè)子進(jìn)程淑蔚。
進(jìn)程和它的所有子女以及后裔共同組成一個(gè)進(jìn)程組市殷。

Windows系統(tǒng)中沒有進(jìn)程層次的概念，所有的進(jìn)程都是地位相同的刹衫。

進(jìn)程的狀態(tài)

進(jìn)程的三種狀態(tài)：

1. 運(yùn)行態(tài)（該時(shí)刻進(jìn)程實(shí)際占用CPU）
2. 就緒態(tài)（可運(yùn)行醋寝，但應(yīng)為其他進(jìn)程正在運(yùn)行而暫時(shí)停止）
3. 阻塞態(tài)（除非某種外部事件發(fā)生，否則進(jìn)程不能運(yùn)行）

進(jìn)程狀態(tài)轉(zhuǎn)換圖

1. 進(jìn)程為等待輸入而阻塞
2. 調(diào)度程序選擇另一個(gè)進(jìn)程
3. 調(diào)度程序選擇這個(gè)程序
4. 出現(xiàn)有效輸入

進(jìn)程的實(shí)現(xiàn)

操作系統(tǒng)維護(hù)著一張表（一個(gè)結(jié)構(gòu)數(shù)組）带迟，即進(jìn)程表（process table）音羞。
每個(gè)進(jìn)程占用一個(gè)進(jìn)程表項(xiàng)（又稱進(jìn)程控制塊）。

終端發(fā)生后操作系統(tǒng)最底層的工作步驟：

1. 硬件壓入堆棧程序計(jì)數(shù)器等仓犬。
2. 硬件從中斷向量裝入新的程序計(jì)數(shù)器嗅绰。
3. 匯編語(yǔ)言過(guò)程保存寄存器值。
4. 匯編語(yǔ)言過(guò)程設(shè)置新的堆棧搀继。
5. C終端服務(wù)例程運(yùn)行（典型地讀和緩沖輸入）窘面。
6. 調(diào)度程序決定下一個(gè)將運(yùn)行的進(jìn)程。
7. C過(guò)程返回至匯編代碼律歼。
8. 匯編語(yǔ)言過(guò)程開始運(yùn)行新的當(dāng)前進(jìn)程民镜。

2. 線程

線程的使用

線程是一種輕量級(jí)的進(jìn)程。

• 多個(gè)線程擁有共享同一個(gè)地址空間和所有可用數(shù)據(jù)的能力险毁。
• 線程比進(jìn)程更容易創(chuàng)建和銷毀制圈。
• 在大量計(jì)算和大量I/O處理過(guò)程中们童，多個(gè)線程能夠加快程序執(zhí)行速度。

經(jīng)典的線程模型

進(jìn)程模型基于兩種對(duì)立的概念：資源分組處理與執(zhí)行鲸鹦。
理解進(jìn)程的一個(gè)角度是慧库，用某種方法把相關(guān)的資源集中在一起。
另一個(gè)概念是馋嗜，進(jìn)程擁有一個(gè)執(zhí)行的線程齐板。
線程擁有自己的程序計(jì)數(shù)器、寄存器葛菇、堆棧甘磨。
進(jìn)程用于把資源集中到一起强法，而線程則是在CPU上被調(diào)度執(zhí)行的實(shí)體标捺。

線程可以處于若干狀態(tài)中的任何一個(gè)：運(yùn)行魄健、阻塞两芳、就緒或終止。

POSIX線程

為實(shí)現(xiàn)可移植的線程程序掂僵，IEEE指定了線程的標(biāo)準(zhǔn)反惕。
它定義的線程包叫做Pthread昌渤，大部分UNIX系統(tǒng)都支持該標(biāo)準(zhǔn)齐邦。

所有Pthread線程都有某些特性椎侠。
每一個(gè)都含有一個(gè)標(biāo)識(shí)符、一組寄存器（包括程序計(jì)數(shù)器）和一組存儲(chǔ)在結(jié)構(gòu)中的屬性措拇。
這些屬性包括堆棧大小我纪、調(diào)度參數(shù)以及使用線程需要的其他項(xiàng)目。

線程包的實(shí)現(xiàn)方式

在用戶空間中實(shí)現(xiàn)

把整個(gè)線程包放在用戶空間中丐吓，內(nèi)核對(duì)線程包一無(wú)所知宣羊。從內(nèi)核角度考慮，就是單線程進(jìn)程汰蜘。
線程在一個(gè)運(yùn)行時(shí)系統(tǒng)的頂部運(yùn)行，這個(gè)運(yùn)行時(shí)系統(tǒng)是一個(gè)管理線程的過(guò)程的集合之宿。
每個(gè)進(jìn)程有其專用線程表（thread table）族操。

優(yōu)點(diǎn)：用戶線程包可以在不支持線程的操作系統(tǒng)上實(shí)現(xiàn)。
不需要陷進(jìn)比被，不需要上下文切換色难，不需要對(duì)內(nèi)存高速緩存進(jìn)行刷新，使得線程調(diào)度非车茸海快枷莉。
允許每個(gè)進(jìn)程有自己定制的調(diào)度算法。

問題：如何實(shí)現(xiàn)阻塞系統(tǒng)調(diào)用尺迂，使用阻塞調(diào)用會(huì)阻塞其他的線程笤妙。
頁(yè)面故障問題冒掌，如果某個(gè)調(diào)用跳轉(zhuǎn)到了一條不再內(nèi)存的指令上，就會(huì)發(fā)生頁(yè)面故障蹲盘，內(nèi)核由于不知道線程的存在股毫，通常會(huì)把整個(gè)進(jìn)程阻塞到I/O完成。
如果一個(gè)線程開始運(yùn)行召衔，那么該進(jìn)程中的其他線程就不能運(yùn)行铃诬，除非第一個(gè)線程自動(dòng)放棄CPU。

在內(nèi)核中實(shí)現(xiàn)線程

此時(shí)不需要運(yùn)行時(shí)系統(tǒng)苍凛，內(nèi)核中有用來(lái)記錄系統(tǒng)中所有線程的線程表趣席。
當(dāng)一個(gè)線程阻塞時(shí)，內(nèi)核根據(jù)其選擇醇蝴，可以運(yùn)行同一個(gè)進(jìn)程中的另一個(gè)線程或者運(yùn)行另一個(gè)進(jìn)程中的線程宣肚。

優(yōu)點(diǎn)：內(nèi)核很容在線程阻塞時(shí)切換到另一個(gè)線程執(zhí)行。
內(nèi)核線程不需要任何新的哑蔫、非阻塞系統(tǒng)調(diào)用钉寝。

問題：在內(nèi)核中創(chuàng)建或銷毀線程的代價(jià)比較大。
進(jìn)程創(chuàng)建問題闸迷，一個(gè)多線程進(jìn)程創(chuàng)建新線程出現(xiàn)的問題嵌纲。
當(dāng)信號(hào)到達(dá)時(shí)，應(yīng)該有哪一個(gè)線程處理腥沽。

混合實(shí)現(xiàn)

使用內(nèi)核線程逮走，然后將用戶級(jí)線程與某些或者全部?jī)?nèi)核線程多路復(fù)用起來(lái)。
內(nèi)核只識(shí)別內(nèi)核線程今阳，并對(duì)其進(jìn)行調(diào)度师溅。一些內(nèi)核線程會(huì)被多個(gè)用戶級(jí)線程多路復(fù)用。

這一模型能夠帶來(lái)最大的靈活度盾舌。

調(diào)度程序激活機(jī)制

當(dāng)內(nèi)核了解到一個(gè)線程被阻塞之后墓臭，內(nèi)核通知該進(jìn)程的運(yùn)行時(shí)系統(tǒng)，并且在堆棧中以參數(shù)的形式傳遞有問題的線程的編號(hào)和所發(fā)生事件的一個(gè)描述妖谴。
內(nèi)核通過(guò)在一個(gè)已知的起始地址啟動(dòng)運(yùn)行時(shí)系統(tǒng)窿锉，從而發(fā)出通知，這是對(duì)UNIX中信號(hào)的一種粗略模擬膝舅。
這個(gè)機(jī)制稱為上行調(diào)用（upcall）嗡载。

調(diào)度程序激活機(jī)制的一個(gè)目標(biāo)是作為上行調(diào)用的信賴基礎(chǔ)，這是一種違反分層系統(tǒng)內(nèi)在結(jié)構(gòu)的概念仍稀。

進(jìn)程間通信

進(jìn)程間通信（Inter Process Communication洼滚，IPC）簡(jiǎn)要的說(shuō)有三個(gè)問題：

1. 一個(gè)進(jìn)程如何把信息傳遞給另一個(gè)。
2. 確保兩個(gè)或更多的進(jìn)程在關(guān)鍵活動(dòng)中不會(huì)出現(xiàn)交叉技潘。
3. 保證進(jìn)程以正確的順序執(zhí)行遥巴。

競(jìng)爭(zhēng)條件

在一些操作系統(tǒng)中千康，協(xié)作的進(jìn)程可能共享一些彼此都能讀寫的公用存儲(chǔ)區(qū)。
兩個(gè)或多個(gè)進(jìn)程讀寫某些共享數(shù)據(jù)挪哄，而最后的結(jié)果取決于進(jìn)程運(yùn)行的精確時(shí)序吧秕，稱為競(jìng)爭(zhēng)條件（race condition）。

臨界區(qū)

阻止多個(gè)進(jìn)程同時(shí)讀寫共享的數(shù)據(jù)可以通過(guò)互斥（mutual exclusion）迹炼。
確保黨一個(gè)進(jìn)程在使用一個(gè)共享數(shù)據(jù)時(shí)砸彬，其他進(jìn)程不能做同樣的操作。
我們把對(duì)共享內(nèi)存進(jìn)行訪問的程序片段稱作臨界區(qū)（critical section）斯入。

一個(gè)好的解決方案砂碉，需要滿足一下4個(gè)條件：

1. 任何兩個(gè)進(jìn)程不能同時(shí)處于臨界區(qū)。
2. 不應(yīng)對(duì)CPU的速度和數(shù)量做任何假設(shè)刻两。
3. 臨界區(qū)外運(yùn)行的程序不得阻塞其他進(jìn)程增蹭。
4. 不得使進(jìn)程無(wú)限期等待進(jìn)入臨界區(qū)。

忙等待的互斥

屏蔽中斷

每個(gè)進(jìn)程在剛剛進(jìn)入臨界區(qū)后立即屏蔽所用中斷磅摹，并在就要離開之前再打開中斷滋迈。

適用于單核操作系統(tǒng)，對(duì)操作系統(tǒng)本身而言很有用户誓，單對(duì)于用戶進(jìn)程則不是一種合適的互斥機(jī)制饼灿。

鎖變量

共享鎖變量，初始為0帝美。當(dāng)進(jìn)程想進(jìn)入臨界區(qū)時(shí)碍彭，首先測(cè)試這把鎖。
如果鎖為0悼潭，則進(jìn)程將所設(shè)置為1并進(jìn)入臨界區(qū)庇忌。
如果鎖為1，則進(jìn)程將等待其值變?yōu)?舰褪。

這種方式同樣存在競(jìng)爭(zhēng)條件皆疹。

嚴(yán)格輪換法

連續(xù)測(cè)試一個(gè)變量直到某個(gè)值出現(xiàn)為止，稱為忙等待占拍。
這種方式浪費(fèi)CPU時(shí)間墙基，通常應(yīng)該避免。
只有在有理由認(rèn)為等待時(shí)間是非常短的情形下刷喜，才使用忙等待。
用于忙等待的鎖立砸，稱為自旋鎖（spin lock）掖疮。

Peterson解法

#define FALSE   0
#define TRUE    1
#define N       2                       /* 進(jìn)程數(shù)量 */

int turn;                               /* 現(xiàn)在輪到誰(shuí)? */
int interested[N];                      /* 所有值初始化為0(FALSE) */

void enter_region(int process)          /* 進(jìn)程是0或1 */
{
    int other;                          /* 其他進(jìn)程號(hào) */

    other = 1 - process;                /* 另一方進(jìn)程 */
    interested[process] = TRUE;         /* 表明所感興趣的 */
    turn = process;                     /* 設(shè)置標(biāo)志 */
    while (turn == process && interested[other] == TRUE);   /* 空語(yǔ)句 */
}

void leave_region(int process)          /* 進(jìn)程：誰(shuí)離開? */
{
    interested[process] = FALSE;        /* 表示離開臨界區(qū) */
}

TSL指令

需要硬件支持的一種方案。
某些計(jì)算機(jī)中颗祝，特別是那些設(shè)計(jì)為多處理器的計(jì)算機(jī)浊闪。
都有指令TSL RX, LOCK恼布。
稱為測(cè)試并加鎖（Test and Set Lock），他將一個(gè)內(nèi)存字lock讀到寄存器RX中搁宾，然后再該內(nèi)存地址上存一個(gè)非零值折汞。
讀字和寫字操作保證是不可分割的。

一個(gè)可替代TSL的指令時(shí)XCHG盖腿，它原子性的交換兩個(gè)位置的內(nèi)容爽待。

睡眠與喚醒

Peterson解法和TSL或XCHG解法都有忙等待的缺點(diǎn)。
這種方法不僅浪費(fèi)了CPU時(shí)間翩腐，而且還可能引起預(yù)想不到的結(jié)果鸟款。

生產(chǎn)者-消費(fèi)者問題。兩個(gè)進(jìn)程共享一個(gè)公共的固定大小的緩沖區(qū)茂卦。
其中一個(gè)是生產(chǎn)者何什，將信息放入緩沖區(qū)；另一個(gè)是消費(fèi)者等龙，從緩沖區(qū)中取出信息处渣。

信號(hào)量

信號(hào)量（semaphore）是Dijkstra在1965年提出的一種方法，使用一個(gè)整型變量來(lái)累計(jì)喚醒次數(shù)蛛砰。

兩種操作：down和up罐栈。
對(duì)一信號(hào)量執(zhí)行down操作，則是檢查其值是否大于0暴备。
若大于0悠瞬，則將其值減1并繼續(xù)；若為0涯捻，則進(jìn)程將睡眠浅妆，此時(shí)down操作并未結(jié)束。
up操作對(duì)信號(hào)量的值增1障癌。
如果一個(gè)或多個(gè)進(jìn)程在該信號(hào)量上睡眠凌外，無(wú)法完成一個(gè)先前的down操作，則有系統(tǒng)選擇其中一個(gè)允許進(jìn)程完成它的down操作涛浙。

信號(hào)量可以用來(lái)實(shí)現(xiàn)同步（synchronization）康辑。

互斥量

如果不需要信號(hào)量的技術(shù)能力，有時(shí)可以使用信號(hào)量的一個(gè)簡(jiǎn)化版本轿亮，稱為互斥量（mutex）疮薇。
互斥量是一個(gè)可以處于兩態(tài)之一的變量：解鎖和加鎖。

一些與互斥量相關(guān)的pthread調(diào)用：

一些與條件變量相關(guān)的pthread調(diào)用：

管程

一個(gè)管程（monitor）是一個(gè)由過(guò)程我注、變量及數(shù)據(jù)結(jié)構(gòu)等組成的一個(gè)集合按咒，它們組成一個(gè)特殊的模塊或軟件包。
進(jìn)程可在任何需要的時(shí)候調(diào)用管程中的過(guò)程但骨，但他們不能在管程之外聲明的過(guò)程中直接訪問管程內(nèi)部的數(shù)據(jù)結(jié)構(gòu)励七。
管程是一種語(yǔ)言概念智袭，C語(yǔ)言不支持。

消息傳遞

消息傳遞（message passing）面臨許多問題和設(shè)計(jì)難點(diǎn)掠抬，特別是位于網(wǎng)絡(luò)中不同機(jī)器上的通信進(jìn)程的情況吼野。
消息系統(tǒng)還需要解決進(jìn)程命名問題。身份認(rèn)證（authentication）也是一個(gè)問題两波。
消息從一個(gè)進(jìn)程復(fù)制到另一個(gè)進(jìn)程通常比信號(hào)量操作和進(jìn)入管程要慢瞳步。

屏障

屏障是用于進(jìn)程組而不是用于雙進(jìn)程的生產(chǎn)者-消費(fèi)者情形的。
某些應(yīng)用中劃分了若干階段雨女，除非所有的進(jìn)程都準(zhǔn)備著手下一個(gè)階段谚攒，否則任何進(jìn)程都不能進(jìn)入下一個(gè)階段。
可以通過(guò)在每個(gè)階段的結(jié)尾安置屏障（barrier）來(lái)實(shí)現(xiàn)氛堕。

調(diào)度

多道程序設(shè)計(jì)系統(tǒng)中馏臭，多個(gè)線程或進(jìn)程同時(shí)競(jìng)爭(zhēng)CPU，當(dāng)只有一個(gè)CPU可用時(shí)讼稚，那么久必須選擇下一個(gè)要運(yùn)行的進(jìn)程括儒。
完成選擇工作的這一部分稱為調(diào)度程序（scheduler），該程序使用的算法稱為調(diào)度算法（scheduling algoritgm）锐想。

進(jìn)程行為

幾乎所有進(jìn)程的（磁盤）I/O請(qǐng)求或計(jì)算都是交替突發(fā)的帮寻。
CPU不停頓地運(yùn)行一段時(shí)間，然后發(fā)出一個(gè)系統(tǒng)調(diào)用以便讀寫文件赠摇。
在完成系統(tǒng)調(diào)用之后固逗，CPU又開始計(jì)算，直到它需要讀取更多的數(shù)據(jù)或?qū)懜嗟臄?shù)據(jù)為止藕帜。

CPU的突發(fā)使用和等待I/O的時(shí)期交替出現(xiàn)

某些進(jìn)程花費(fèi)了絕大多數(shù)時(shí)間在計(jì)算上烫罩，而其他進(jìn)程則在等待I/O上花費(fèi)了絕大多數(shù)時(shí)間。
前者稱為計(jì)算密集型（computer-bound）洽故，后者稱為I/O密集型（I/O-bound）贝攒。

何時(shí)調(diào)度

需要處理各種情形：

1. 在創(chuàng)建一個(gè)新進(jìn)程后扶踊，需要決定是運(yùn)行父進(jìn)程還是運(yùn)行子進(jìn)程靶橱。
2. 在一個(gè)進(jìn)程退出時(shí)必須做出調(diào)度決策。
3. 當(dāng)一個(gè)進(jìn)程阻塞在I/O和信號(hào)量上或者由于其他原因阻塞時(shí)送悔，必須選擇另一個(gè)進(jìn)程運(yùn)行荒适。
4. 在一個(gè)I/O中斷發(fā)生時(shí)梨熙，必須做出調(diào)度決策。

非搶占式調(diào)度算法：挑選一個(gè)進(jìn)程刀诬，然后讓該進(jìn)程運(yùn)行直至被阻塞串结，或者直到進(jìn)程自動(dòng)釋放CPU。

搶占式調(diào)度算法：選擇一個(gè)進(jìn)程，讓該進(jìn)程運(yùn)行某個(gè)固定時(shí)段的最大值肌割。
如果時(shí)段結(jié)束進(jìn)程任在運(yùn)行則被掛起，調(diào)度程序選擇另外一個(gè)進(jìn)程運(yùn)行帐要。

調(diào)度算法分類

三種環(huán)境

1. 批處理把敞。非搶占式，或長(zhǎng)時(shí)間周期的搶占式算法
2. 交互式榨惠。搶占式算法
3. 實(shí)時(shí)奋早。搶占有時(shí)是不需要的。

調(diào)度算法的目標(biāo)

• 所有系統(tǒng)

  • 公平——給每個(gè)進(jìn)程公平的CPU份額
  • 策略強(qiáng)制執(zhí)行——看到鎖宣布的策略執(zhí)行
  • 平衡——保持系統(tǒng)的所有部分都忙碌

• 批處理系統(tǒng)

  • 吞吐量——每小時(shí)最大作業(yè)數(shù)
  • 周轉(zhuǎn)時(shí)間——從提交到終止間的最小時(shí)間
  • CPU利用率——保持CPU時(shí)鐘忙碌

• 交互式系統(tǒng)

  • 響應(yīng)時(shí)間——快速響應(yīng)請(qǐng)求
  • 均衡性——滿足用戶的期望

• 實(shí)時(shí)系統(tǒng)

  • 滿足截止時(shí)間——避免丟失數(shù)據(jù)
  • 可預(yù)測(cè)性——在多媒體系統(tǒng)中避免品質(zhì)降低

批處理系統(tǒng)中的調(diào)度

• 先來(lái)先服務(wù)
• 最短作業(yè)優(yōu)先
• 最短剩余時(shí)間優(yōu)先

交互式系統(tǒng)中的調(diào)度

• 輪轉(zhuǎn)調(diào)度
• 優(yōu)先級(jí)調(diào)度
• 多級(jí)隊(duì)列
• 最短進(jìn)程優(yōu)先
• 保證調(diào)度
• 彩票調(diào)度
• 公平分享調(diào)度

實(shí)時(shí)系統(tǒng)中的調(diào)度

實(shí)時(shí)系統(tǒng)的調(diào)度算法可以是靜態(tài)的或動(dòng)態(tài)的赠橙。
前者在系統(tǒng)開始運(yùn)行之前做出調(diào)度決策耽装；后者在運(yùn)行過(guò)程中進(jìn)程調(diào)度決策。

3期揪、存儲(chǔ)管理

現(xiàn)代操作系統(tǒng)使用分層存儲(chǔ)器體系（memory hierarchy）掉奄。操作系統(tǒng)中管理分層存儲(chǔ)器體系的部分稱為存儲(chǔ)管理器（memory manager），即記錄那些內(nèi)存是正在使用的凤薛，那些內(nèi)存是空閑的姓建；在進(jìn)程需要時(shí)為其分配內(nèi)存，在進(jìn)程是用完后釋放內(nèi)存缤苫。

無(wú)存儲(chǔ)抽象

最簡(jiǎn)單的存儲(chǔ)器抽象就是根本沒有抽象速兔。早期計(jì)算機(jī)沒有存儲(chǔ)器抽象，每個(gè)程序都直接訪問物理內(nèi)存活玲。想要在內(nèi)存中同時(shí)運(yùn)行兩個(gè)程序是很困難的涣狗。

一種存儲(chǔ)器抽象：地址空間

暴露物理內(nèi)存給進(jìn)程的問題：

1. 如果用戶程序可以尋址內(nèi)存中的每個(gè)字節(jié)，它能很容易破壞操作系統(tǒng)舒憾。
2. 使用這種模型想同時(shí)運(yùn)行多個(gè)城市是很困難的镀钓。

地址空間的概念

保證多個(gè)應(yīng)用程序同時(shí)處于內(nèi)存中并且不互相影響，需要解決兩個(gè)問題：保護(hù)和重定位珍剑。

地址空間為程序創(chuàng)造了一種抽象的內(nèi)存掸宛。每個(gè)進(jìn)程都有自己的地址空間，并且這個(gè)地址空間獨(dú)立于其他進(jìn)程的地址空間招拙。

基址寄存器與界限寄存器

動(dòng)態(tài)重定位唧瘾，簡(jiǎn)單地把每個(gè)進(jìn)程的地址空間映射到物理內(nèi)存的不同部分。程序裝在到內(nèi)存期間無(wú)須重定位别凤，程序的起始物理地址裝在到基址寄存器中饰序，程序的長(zhǎng)度裝在到界限寄存器中。

缺點(diǎn)：每次訪問內(nèi)存都需要進(jìn)行加法和比較運(yùn)行规哪。

交換技術(shù)

兩種處理內(nèi)存超載的方法：交換（swapping）技術(shù)求豫，虛擬內(nèi)存（virtual memory）。

內(nèi)存分配情況隨著進(jìn)程進(jìn)出而變化

如果大部分進(jìn)程在運(yùn)行時(shí)都要增長(zhǎng)，可以在換入或移動(dòng)進(jìn)程時(shí)為它多分配一些額外的內(nèi)存蝠嘉，例如數(shù)據(jù)段與堆棧段最疆。

空閑內(nèi)存管理

兩種跟蹤內(nèi)存使用情況的方法：位圖，空閑鏈表蚤告。

空閑內(nèi)存管理方式

查找位圖中指定長(zhǎng)度的連續(xù)0串是耗時(shí)操作努酸，這是位圖的缺點(diǎn)。

鏈表管理法適配方式：

• 首次適配（first fit）：存儲(chǔ)管理器沿著鏈表進(jìn)行搜索杜恰，直到找到一個(gè)足夠大的空閑區(qū)获诈。
• 下次適配（next fit）：每次找到合適的空閑區(qū)都記錄，以便下次從此開始搜索心褐。
• 最佳適配（best fit）：搜索整個(gè)表舔涎，找出能夠容納進(jìn)程的最小空閑區(qū)。
• 最差適配（worst fit）：總是分配最大的可用空閑區(qū)逗爹，使新的空閑區(qū)比較大亡嫌。
• 快速適配（quick fit）：為那些常用大小的空閑區(qū)維護(hù)單獨(dú)的鏈表。

虛擬內(nèi)存

基本思想：每個(gè)程序擁有自己的地址空間桶至，這個(gè)空間被分割成多個(gè)塊昼伴，每一塊稱作一頁(yè)或頁(yè)面（page）。每一頁(yè)有連續(xù)的地址范圍镣屹。這些頁(yè)被映射到物理內(nèi)存圃郊，但并不是多有的頁(yè)都必須在內(nèi)存中才能運(yùn)行程序。當(dāng)程序引用到一部分在物理內(nèi)存中的地址空間使女蜈，由硬件立刻執(zhí)行必要的映射持舆。放程序引用到一部分不再物理內(nèi)存中的地址空間時(shí)，由操作系統(tǒng)負(fù)責(zé)將缺失的部分裝入物理內(nèi)存并重新執(zhí)行失敗的指令伪窖。

分頁(yè)

由程序產(chǎn)生的地址稱為虛擬地址（virtual address）逸寓，它們構(gòu)成了一個(gè)虛擬地址空間（virtual address space）。在沒有虛擬內(nèi)存的計(jì)算機(jī)上覆山，系統(tǒng)直接將虛擬地址送到內(nèi)存總線上竹伸，讀寫操作使用具有同樣地址的物理內(nèi)存字；而在使用虛擬內(nèi)存的情況下簇宽，虛擬地址不是被直接送到內(nèi)存總線上勋篓，而是被送到內(nèi)存管理單元（Memory Management Unit，MMU）魏割，MMU把虛擬地址映射為物理內(nèi)存地址譬嚣。

MMU的位置和功能

虛擬地址空間按照固定大小劃分成頁(yè)面（page）的若干單元。在物理內(nèi)存中對(duì)應(yīng)的單元稱為頁(yè)框（page frame）钞它。頁(yè)面和頁(yè)框的大小通常是一樣的拜银。

當(dāng)MMU注意到某頁(yè)面沒有被映射殊鞭，于是使CPU陷入到操作系統(tǒng)，這個(gè)陷進(jìn)稱為缺頁(yè)中斷（page fault）尼桶。操作系統(tǒng)找到一個(gè)很少使用的頁(yè)框且把它的內(nèi)容寫入磁盤操灿。隨后把需要訪問的頁(yè)面讀到剛才回收的頁(yè)框中，修改映射關(guān)系泵督，然后重新啟動(dòng)引起陷進(jìn)的指令牲尺。

頁(yè)表

簡(jiǎn)單的，虛擬地址被分成虛擬頁(yè)號(hào)（高位部分）和偏移量（低位部分）幌蚊。虛擬頁(yè)號(hào)可用作頁(yè)表的索引，以找到該虛擬頁(yè)面對(duì)應(yīng)的頁(yè)表項(xiàng)溃卡。由頁(yè)表項(xiàng)可以找到頁(yè)框號(hào)溢豆。然后把頁(yè)框號(hào)拼接到偏移量的高位端，以替換掉虛擬頁(yè)號(hào)瘸羡，形成送往內(nèi)存的物理地址漩仙。

頁(yè)表項(xiàng)的結(jié)構(gòu)

一個(gè)典型的頁(yè)表項(xiàng)

• 頁(yè)框號(hào)
• “在/不在”位：對(duì)應(yīng)的虛擬頁(yè)面在不在內(nèi)存中
• 保護(hù)位：三位，表示讀寫執(zhí)行
• 修改位
• 訪問位
• 高速緩存禁止位

加速分頁(yè)過(guò)程

在任何分頁(yè)式系統(tǒng)中犹赖，都需要考慮兩個(gè)主要問題：

1. 虛擬地址到物理地址的映射必須非扯铀快。
2. 如果虛擬地址空間很大峻村，頁(yè)表也會(huì)很大麸折。

解決方式：

• 轉(zhuǎn)換檢測(cè)緩沖區(qū)（Translation Lookaside Buffer，TLB）粘昨。大多數(shù)程序總是對(duì)少量的頁(yè)面進(jìn)行多次訪問垢啼。
• 軟件TLB管理

針對(duì)大內(nèi)存的頁(yè)表

• 多級(jí)頁(yè)表：避免把全部頁(yè)表一直保存在內(nèi)存中。
• 倒排頁(yè)表：在實(shí)際內(nèi)存中每一個(gè)頁(yè)框有一個(gè)表項(xiàng)张肾，而不是每一個(gè)虛擬頁(yè)面有一個(gè)表項(xiàng)芭析。

頁(yè)面置換算法

當(dāng)發(fā)生缺頁(yè)中斷時(shí)，操作系統(tǒng)必須在內(nèi)存中選擇一個(gè)頁(yè)面將其換出內(nèi)存吞瞪。如果要換出的頁(yè)面在內(nèi)存駐留期間已被修改馁启，就必須寫回磁盤；如果沒有修改直接被覆蓋就可以了芍秆。

• 最優(yōu)頁(yè)面置換算法：置換最久將要被訪問的頁(yè)面惯疙。此算法無(wú)法實(shí)現(xiàn)。

• 最近未使用頁(yè)面置換算法（Not Recently Used浪听，NRU）：隨機(jī)地從類編號(hào)最小的非空類中挑選一個(gè)頁(yè)面淘汰之螟碎。

  1. 沒有被訪問，沒有被修改
  2. 沒有被訪問迹栓，已被修改
  3. 已被訪問掉分，沒有被修改
  4. 已被訪問俭缓，已被修改

• 先進(jìn)先出頁(yè)面置換算法（First-In，F(xiàn)irst-Out酥郭，F(xiàn)IFO）：每次置換鏈表的表頭华坦。

• 第二次機(jī)會(huì)頁(yè)面置換算法：檢查最老頁(yè)面的訪問位。如果是0則立刻置換不从，如果是1則修改為0并把該頁(yè)面放到鏈表尾端惜姐。

• 時(shí)鐘頁(yè)面置換算法：環(huán)形鏈表，有一個(gè)表針指向最老頁(yè)面椿息。首先檢查表針歹袁，如果R位是0就淘汰頁(yè)面，插入頁(yè)面后表針前移一個(gè)位置寝优。如果R位是1就清除R并把表針前移一個(gè)位置条舔，直到找到R為0的頁(yè)面。

• 最近最少使用頁(yè)面置換算法（Least Recently Used乏矾，LRU）：置換未使用時(shí)間最長(zhǎng)的頁(yè)面孟抗。

• 工作集頁(yè)面置換算法：進(jìn)程當(dāng)前正在使用的頁(yè)面的集合稱為它的工作集（working set）。缺頁(yè)中斷時(shí)淘汰一個(gè)不再工作集中的頁(yè)面钻心。

• 工作集時(shí)鐘頁(yè)面置換算法

頁(yè)面置換算法小結(jié)

分頁(yè)系統(tǒng)中的設(shè)計(jì)問題

• 局部分配策略與全局分配策略：當(dāng)發(fā)生缺頁(yè)中斷時(shí)捷沸，頁(yè)面置換算法在尋找最近最少使用的頁(yè)面時(shí)摊沉，只考慮分配給該進(jìn)程的頁(yè)面，稱為局部頁(yè)面置換算法亿胸；考慮所有在內(nèi)存中的頁(yè)面坯钦，稱為全局頁(yè)面置換算法。
• 負(fù)載控制
• 頁(yè)面大谐扌：確定最佳頁(yè)面大小婉刀。
• 分離的指令空間和數(shù)據(jù)空間：為指令和數(shù)據(jù)設(shè)置分離的地址空間
• 共享頁(yè)面：UNIX系統(tǒng)中進(jìn)行fork系統(tǒng)調(diào)用后，父子進(jìn)程共享程序文本和數(shù)據(jù)序仙。這些進(jìn)程擁有自己的頁(yè)表突颊，但都指向同一個(gè)頁(yè)面集合。只要有一個(gè)進(jìn)程要求更新數(shù)據(jù)潘悼，就會(huì)觸發(fā)只讀保護(hù)律秃，引發(fā)操作系統(tǒng)陷進(jìn)，生成該頁(yè)的一個(gè)副本治唤。這種方式稱為寫時(shí)復(fù)制棒动。
• 共享庫(kù)：如果其他程序已經(jīng)裝載了某個(gè)共享庫(kù)，另一個(gè)程序就沒必要再次裝載了宾添。編譯共享庫(kù)時(shí)船惨，使用-fPIC產(chǎn)生位置無(wú)關(guān)代碼柜裸。
• 內(nèi)存映射文件：進(jìn)程可以通過(guò)發(fā)起一個(gè)系統(tǒng)調(diào)用，將一個(gè)文件映射到虛擬地址空間的一部分粱锐。在訪問頁(yè)面時(shí)每次一頁(yè)的讀入疙挺。多個(gè)進(jìn)程可以通過(guò)映射同一個(gè)文件來(lái)通信。
• 清除策略：如果發(fā)生缺頁(yè)中斷時(shí)系統(tǒng)中有大量的空閑頁(yè)框怜浅，此時(shí)分頁(yè)系統(tǒng)工作在最佳狀態(tài)铐然。一種實(shí)現(xiàn)清除策略的方法就是使用一個(gè)雙指針時(shí)鐘。
• 虛擬內(nèi)存接口

有關(guān)實(shí)現(xiàn)的問題

• 與分頁(yè)有關(guān)的工作：操縱系統(tǒng)要在四段時(shí)間里做與分頁(yè)相關(guān)的工作恶座。進(jìn)程創(chuàng)建時(shí)搀暑，進(jìn)程執(zhí)行時(shí)，缺頁(yè)中斷時(shí)跨琳，進(jìn)程終止時(shí)险掀。

• 缺頁(yè)中斷處理

  1. 硬件陷入內(nèi)核，在堆棧中保存程序計(jì)數(shù)器湾宙。
  2. 啟動(dòng)一個(gè)匯編代碼例程保存通用寄存器和其他易失的信息，以免被操作系統(tǒng)破環(huán)冈绊。
  3. 當(dāng)操作系統(tǒng)發(fā)現(xiàn)一個(gè)缺頁(yè)中斷時(shí)侠鳄，嘗試發(fā)現(xiàn)需要哪個(gè)虛擬頁(yè)面。
  4. 一旦知道發(fā)生缺頁(yè)中斷的虛擬地址死宣，操作系統(tǒng)檢查這個(gè)地址是否有效伟恶，并檢查存取與保護(hù)是否一致。
  5. 如果選擇的頁(yè)框“臟”了毅该，安排該頁(yè)寫回磁盤博秫，并發(fā)生一次上下文切換，掛起產(chǎn)生缺頁(yè)中斷的進(jìn)程眶掌，讓其他進(jìn)程運(yùn)行直至磁盤傳輸結(jié)束挡育。
  6. 一旦頁(yè)框“干凈”后，操作系統(tǒng)查找所需頁(yè)面在磁盤上的地址朴爬，通過(guò)磁盤操作將其裝入。
  7. 當(dāng)磁盤中斷發(fā)生時(shí)，表明該頁(yè)已經(jīng)被裝入与殃，頁(yè)表已經(jīng)更新可以反應(yīng)它的位置该酗，頁(yè)框也被標(biāo)記為正常狀態(tài)。
  8. 恢復(fù)發(fā)生缺頁(yè)中斷指令以前的狀態(tài)具滴，程序計(jì)數(shù)器重新指向這條指令凹嘲。
  9. 調(diào)度引發(fā)缺頁(yè)中斷的進(jìn)程，操作系統(tǒng)返回調(diào)用它的匯編語(yǔ)言例程构韵。
  10. 該例程恢復(fù)寄存器和其他狀態(tài)信息周蹭，返回到用戶空間繼續(xù)執(zhí)行趋艘，就好像缺頁(yè)中斷沒有發(fā)生過(guò)一樣。

• 指令備份：使用一個(gè)隱藏的內(nèi)部寄存器谷醉。在每條指令執(zhí)行之前致稀，把程序計(jì)數(shù)器的內(nèi)容復(fù)制到該寄存器中。

• 鎖定內(nèi)存中的頁(yè)面：保證正在做I/O操作的頁(yè)面不會(huì)被移出內(nèi)存俱尼。

• 后備存儲(chǔ)

• 策略和機(jī)制的分離

分段

分頁(yè)和分段的比較

4、文件系統(tǒng)

文件

• 文件命名：在具體系統(tǒng)中規(guī)則不一斯够，UNIX文件系統(tǒng)區(qū)分大小寫囚玫，MS-DOS文件系統(tǒng)不區(qū)分大小寫。

• 文件結(jié)構(gòu)：字節(jié)序列读规、記錄序列抓督、樹。所有UNIX束亏、MS-DO铃在、Windows系統(tǒng)都把文件看成無(wú)結(jié)構(gòu)字節(jié)序列。

• 文件類型：ASCII文件和二進(jìn)制文件碍遍。

• 文件存榷ㄍ：順序存取和隨機(jī)存取。

• 文件屬性：文件的附加信息怕敬，稱為屬性（attribute）或元數(shù)據(jù)（matedata）揣炕。

• 文件操作：常用系統(tǒng)調(diào)用

  • create：創(chuàng)建不包含任何數(shù)據(jù)的文件。
  • detele：刪除文件釋放磁盤空間东跪。
  • open：打開文件祝沸，把文件屬性和磁盤地址表裝入內(nèi)存，便于后續(xù)調(diào)用越庇。
  • close：關(guān)閉文件釋放內(nèi)部表空間罩锐。
  • read：在文件中讀取數(shù)據(jù)。
  • write：向文件中寫數(shù)據(jù)卤唉。
  • append：在文件末尾添加數(shù)據(jù)涩惑。
  • seek：對(duì)于隨機(jī)存取文件，指定從何處開始取數(shù)據(jù)桑驱。
  • get attribute：讀取文件屬性竭恬。
  • set attribute：某些屬性可由用戶設(shè)置跛蛋。
  • rename：改變已有文件的名字。

目錄

• 一級(jí)目錄系統(tǒng)：一個(gè)目錄中包含所有文件痊硕，稱為根目錄赊级。能快速定位文件。

• 層次目錄系統(tǒng)：層次化的目錄樹結(jié)構(gòu)岔绸，幾乎所有現(xiàn)代文件系統(tǒng)都采用理逊。

• 路徑名：絕對(duì)路徑與相對(duì)路徑。

• 目錄操作：常用基本系統(tǒng)調(diào)用盒揉。

  • create：創(chuàng)建目錄晋被，處理目錄項(xiàng).和..外，目錄內(nèi)容為空刚盈。
  • delete：刪除目錄羡洛。
  • opendir：打開目錄以備讀取。
  • closedir：關(guān)閉目錄釋放內(nèi)部表空間藕漱。
  • readdir：讀取目錄返回目錄下一個(gè)目錄項(xiàng)欲侮。
  • rename：更改目錄名稱。
  • link：連接技術(shù)允許在多個(gè)目錄中出現(xiàn)同一個(gè)文件肋联。
  • unlink：刪除目錄項(xiàng)锈麸。

文件系統(tǒng)的實(shí)現(xiàn)

文件系統(tǒng)布局

文件系統(tǒng)存放在磁盤上。多數(shù)磁盤劃分為一個(gè)或多個(gè)分區(qū)牺蹄，每個(gè)分區(qū)中有一個(gè)獨(dú)立的文件系統(tǒng)。磁盤的0號(hào)扇區(qū)稱為主引導(dǎo)記錄（Master Boot Record薄翅，MBR）沙兰，用來(lái)引導(dǎo)計(jì)算機(jī)。在MBR的結(jié)尾是分區(qū)表翘魄。該表給出了每個(gè)分區(qū)的起始地址和結(jié)束地址鼎天。表中的一個(gè)分區(qū)被標(biāo)記為活動(dòng)分區(qū)。在計(jì)算幾被引導(dǎo)時(shí)暑竟，BIOS讀入并執(zhí)行MBR斋射。MBR做的第一件事是確定活動(dòng)分區(qū)，讀入它的第一個(gè)塊但荤，稱為引導(dǎo)塊（boot block）罗岖，并執(zhí)行之。引導(dǎo)塊中的程序?qū)⒀b在該分區(qū)中的操作系統(tǒng)腹躁。

一種可能的文件系統(tǒng)布局：

一種可能的文件系統(tǒng)布局

• 超級(jí)塊（superblock）：包含文件系統(tǒng)的所有關(guān)鍵參數(shù)桑包。
• 空閑空間管理：空閑塊的信息，可以用位圖或指針表形式給出纺非。
• i節(jié)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)數(shù)組哑了，每個(gè)文件一個(gè)赘方，說(shuō)明文件的方方面面。
• 根目錄：目錄樹的根部弱左。
• 目錄和文件：存放其他所有目錄和文件

文件的實(shí)現(xiàn)

• 連續(xù)分配：把每個(gè)文件作為一連串連續(xù)數(shù)據(jù)塊存儲(chǔ)在磁盤上窄陡。易產(chǎn)生零碎空間。
• 鏈表分配：為每個(gè)文件構(gòu)造磁盤塊鏈表拆火。隨機(jī)存取緩慢跳夭。指針占去了一些空間。
• 在內(nèi)存中采用表的鏈表分配：取出每個(gè)磁盤塊的指針字榜掌，把它放在內(nèi)存的一個(gè)表中优妙。稱為文件分配表（File Allocation Table，F(xiàn)AT）憎账。對(duì)于大磁盤而言占用內(nèi)存太多套硼。
• i節(jié)點(diǎn)：給每個(gè)文件賦予一個(gè)稱為i節(jié)點(diǎn)（index-node）的數(shù)據(jù)結(jié)構(gòu)，其中列出了文件屬性和文件塊的磁盤地址胞皱。

目錄的實(shí)現(xiàn)

1. 目錄中有一個(gè)固定大小的目錄項(xiàng)列表邪意，每個(gè)文件對(duì)應(yīng)一項(xiàng)，其中包含一個(gè)文件名反砌、一個(gè)文件屬性結(jié)構(gòu)以及泳衣說(shuō)明磁盤塊位置的一個(gè)或多個(gè)磁盤地址雾鬼。
2. 采用i節(jié)點(diǎn)的系統(tǒng)，把文件屬性存放在i節(jié)點(diǎn)中宴树，目錄項(xiàng)更短：只有文件名和i節(jié)點(diǎn)號(hào)策菜。

兩種處理目錄項(xiàng)中長(zhǎng)文件名的方式：

兩種處理目錄項(xiàng)中長(zhǎng)文件名的方式

共享文件

1. 磁盤塊不列入目錄中，而是列入一個(gè)與問價(jià)本身關(guān)聯(lián)的小型數(shù)據(jù)結(jié)構(gòu)（i節(jié)點(diǎn)中）中酒贬。目錄將指向這個(gè)小型數(shù)據(jù)結(jié)構(gòu)又憨。
2. 建立一個(gè)類型為link的新文件，使其與另一個(gè)文件存在連接锭吨。新文件中指包含了它所連接的文件的路徑名蠢莺。稱為符號(hào)連接（symbolic linking）。

日志文件系統(tǒng)

基本思想是將整個(gè)磁盤結(jié)構(gòu)化為一個(gè)日志零如。每隔一段時(shí)間躏将，或是有特殊需要時(shí)，被緩沖在內(nèi)存中的所有未決的血操作都被放到一個(gè)單獨(dú)的段中考蕾，作為在日志末尾的一個(gè)鄰接段寫入磁盤祸憋。

保存一個(gè)用于記錄系統(tǒng)下一步將要做什么的日志。這樣當(dāng)系統(tǒng)在完成它們即將完成的任務(wù)錢崩潰時(shí)肖卧，重新啟動(dòng)之后夺衍，可以通過(guò)查看日志，獲取崩潰前計(jì)劃完成的任務(wù)，并完成它們沟沙。這樣的文件系統(tǒng)稱為日志文件系統(tǒng)河劝。

為了增加可信性，一個(gè)文件系統(tǒng)可以引入數(shù)據(jù)庫(kù)中原子事務(wù)（atomic transaction）的概念矛紫。

虛擬文件系統(tǒng)

大多數(shù)UNIX操作系統(tǒng)都使用虛擬文件系統(tǒng)概念嘗試將多種文件系統(tǒng)統(tǒng)一成一個(gè)有序的框架赎瞎。
關(guān)鍵思想解釋抽象出所有文件系統(tǒng)的共有部分，并且將這部分代碼放在單獨(dú)的一層颊咬，該層調(diào)用底層的實(shí)際文件系統(tǒng)來(lái)具體管理數(shù)據(jù)务甥。

虛擬文件系統(tǒng)的位置：

虛擬文件系統(tǒng)的位置

文件系統(tǒng)管理和優(yōu)化

• 磁盤空間管理

  • 塊大小
  • 記錄空閑塊
  • 磁盤配額

• 文件系統(tǒng)備份

• 文件系統(tǒng)的一致性

• 文件系統(tǒng)的性能

  • 高速緩存
  • 塊提前讀
  • 減少磁盤臂運(yùn)動(dòng)

• 磁盤碎片整理

5、輸入輸出

I/O硬件原理

I/O設(shè)備大致分為兩類：

• 塊設(shè)備（blocl device）：所有傳輸以一個(gè)或多個(gè)完整的（連續(xù)的）塊為單位喳篇。
• 字符設(shè)備（character device）：以字符為單位發(fā)送或接受一個(gè)字符流敞临。

I/O設(shè)備一般由機(jī)械部件和電子部件兩部分組成，電子部件稱作設(shè)備控制器（device controller）或適配器（adapter）麸澜。

內(nèi)存映射I/O的優(yōu)點(diǎn)：

1. 對(duì)于內(nèi)存映射I/O挺尿，設(shè)備控制寄存器只是內(nèi)存中的變量，在C語(yǔ)言中可以和任何其他變量一樣尋址炊邦。
2. 對(duì)于內(nèi)存映射I/O编矾，不需要特殊的保護(hù)機(jī)制來(lái)阻止用戶進(jìn)程執(zhí)行I/O操作。
3. 對(duì)于內(nèi)存映射I/O馁害，可以引用內(nèi)存的每一條指令也可以引用控制寄存器窄俏。

I/O軟件原理

在設(shè)計(jì)I/O軟件時(shí)一個(gè)關(guān)鍵的概念是設(shè)備獨(dú)立性（device independence）。

I/O軟件的幾個(gè)問題：

• 統(tǒng)一命名：不應(yīng)該依賴于設(shè)備碘菜。
• 錯(cuò)誤處理：盡可能在接近硬件的層面得到處理凹蜈。
• 同步和異步傳輸。
• 緩沖：數(shù)據(jù)離開設(shè)備之后不能直接存放到最終目的地忍啸。
• 共享設(shè)備的獨(dú)占問題仰坦。

I/O的最簡(jiǎn)單形式是讓CPU做全部工作，這一方法稱為程序控制I/O吊骤。

使CPU在等待打印機(jī)變?yōu)榫途w的同時(shí)做某些其他事情的方式就是使用中斷驅(qū)動(dòng)I/O。缺點(diǎn)是中斷發(fā)生在每個(gè)字符上静尼，浪費(fèi)時(shí)間白粉。

由DMA控制器處理全部的I/O工作，使CPU可以在I/O期間做其他工作鼠渺。

I/O軟件層次

I/O軟件通常組織成四個(gè)層次：

I/O軟件系統(tǒng)的層次

• 中斷處理程序
• 設(shè)備驅(qū)動(dòng)程序
• 與設(shè)備無(wú)關(guān)的I/O軟件
• 用戶空間的I/O軟件

盤

• 磁盤
• RAID
• CD-ROM
• 可刻錄CD
• 可重寫CD
• DVD

影響磁盤塊讀寫速度的因素

1. 尋道時(shí)間（將磁盤臂移動(dòng)到適當(dāng)?shù)闹嫔纤璧臅r(shí)間）
2. 旋轉(zhuǎn)時(shí)間（等待適當(dāng)扇區(qū)旋轉(zhuǎn)到磁頭下所需的時(shí)間）
3. 實(shí)際數(shù)據(jù)傳輸時(shí)間鸭巴。

時(shí)鐘

• 時(shí)鐘硬件：晶體振蕩器、計(jì)數(shù)器和存儲(chǔ)寄存器拦盹。
• 時(shí)鐘軟件
• 軟定時(shí)器

用戶界面：鍵盤鹃祖、鼠標(biāo)和顯示器

• 輸入軟件

  • 鍵盤軟件
  • 鼠標(biāo)軟件

• 輸出軟件

  • 文本窗口
  • X窗口系統(tǒng)
  • 圖形用戶界面
  • 位圖
  • 字體

6、死鎖

資源

所有需要排他性使用的對(duì)象都可以稱作資源（resource）普舆。資源可以分為兩類：

• 可搶占資源恬口⌒６粒可以從擁有它的進(jìn)程中搶占而不會(huì)產(chǎn)生任何副作用，例如存儲(chǔ)器祖能。
• 不可搶占資源歉秫。在不引起相關(guān)的計(jì)算失敗的情況下，無(wú)法把它從占有它的進(jìn)程處搶占過(guò)來(lái)养铸。

死鎖概述

死鎖的規(guī)范定義：<u style="box-sizing: border-box; outline: 0px; overflow-wrap: break-word;">如果一個(gè)進(jìn)程集合中的每個(gè)進(jìn)程都在等待只能由該進(jìn)程集合中的其他進(jìn)程才能引發(fā)的事件雁芙，那么，該進(jìn)程集合就是死鎖的钞螟。</u>

資源死鎖的4個(gè)條件：

1. 互斥條件兔甘。
2. 占有和等待條件。
3. 不可搶占條件鳞滨。
4. 環(huán)路等待條件洞焙。

四種處理死鎖的策略：

1. 忽略該問題。
2. 檢測(cè)死鎖并恢復(fù)太援。
3. 仔細(xì)對(duì)資源進(jìn)行分配闽晦，動(dòng)態(tài)的避免死鎖。
4. 通過(guò)破壞引起死鎖的四個(gè)必要條件之一提岔，防止死鎖的產(chǎn)生仙蛉。

鴕鳥算法

鴕鳥算法：把頭埋到沙子里，假裝根本沒有問題發(fā)生碱蒙。

死鎖檢測(cè)和死鎖恢復(fù)

• 每種類型一個(gè)資源的死鎖檢測(cè)荠瘪。檢測(cè)是否存在有向圖環(huán)路。

• 每種類型多個(gè)資源的死鎖檢測(cè)赛惩“梗基于矩陣的算法。

• 從死鎖中恢復(fù)

  • 利用搶占恢復(fù)
  • 利用回滾恢復(fù)
  • 通過(guò)殺死進(jìn)程恢復(fù)

死鎖避免

• 資源軌跡圖
• 安全狀態(tài)和不安全狀態(tài)
• 單個(gè)資源的銀行家算法
• 多個(gè)資源的銀行家算法

死鎖預(yù)防

• 破環(huán)互斥條件
• 破壞占有和等待條件
• 破壞不可搶占條件
• 破壞環(huán)路等待條件

其他問題

• 兩階段加鎖
• 通信死鎖
• 活鎖
• 饑餓

7喷兼、多媒體操作系統(tǒng)

多媒體簡(jiǎn)介

多媒體的兩個(gè)關(guān)鍵特征：

1. 多媒體使用極高的數(shù)據(jù)率篮绰。
2. 多媒體要求實(shí)時(shí)回放。

多媒體文件

視頻編碼

基于人眼的特性：<u style="box-sizing: border-box; outline: 0px; overflow-wrap: break-word;">當(dāng)一幅圖像閃現(xiàn)在視網(wǎng)膜上時(shí)季惯，在它衰退之前將保持幾毫秒時(shí)間吠各。如果一個(gè)圖像序列以每秒50或更多張圖像閃現(xiàn)，眼界就不會(huì)注意到它看到的是不連續(xù)的圖像勉抓。</u>

為了將二維圖像表示作為時(shí)間函數(shù)的一維電壓贾漏，攝像機(jī)用一個(gè)電子束對(duì)圖像進(jìn)行橫向掃描并緩慢地向下移動(dòng)，記錄下電子束經(jīng)過(guò)處光的強(qiáng)度藕筋。在掃描的終點(diǎn)處纵散，電子束折回。稱為一幀（frame）。

彩色視頻采用與單色視頻相同的掃描模式伍掀，只不過(guò)使用了三個(gè)同時(shí)運(yùn)動(dòng)的電子束來(lái)顯示圖像掰茶。紅、綠硕盹、藍(lán)（RGB）三原色符匾。

數(shù)字視頻最簡(jiǎn)單的表示方法是幀的序列，每一幀由呈矩形柵格的圖像要素即像素（pixel）組成瘩例。每個(gè)像素RGB三色中的每種顏色用8個(gè)二進(jìn)制位來(lái)表示啊胶。

音頻編碼

音頻波可以通過(guò)模數(shù)轉(zhuǎn)換器（Analog Digital Converter胧洒，ADC）轉(zhuǎn)換成數(shù)字形式忿项。ADC以電壓作為輸入狼讨，并且生成二進(jìn)制數(shù)作為輸出柱搜。

由于每一樣本的位數(shù)有限而引入的誤差稱為量化噪聲（quantizatuin）轮洋。

電話系統(tǒng)使用的實(shí)時(shí)脈沖編碼調(diào)制（pulse code modulation）舔亭，脈沖編碼調(diào)制以每秒7位或8位對(duì)聲音采樣8000次蝗碎，故這一系統(tǒng)的數(shù)據(jù)率為56000bps或64000bps剃袍。由于每秒只有8000個(gè)樣本善绎，所以4kHz以上的頻率就丟失了黔漂。

音頻CD是以每秒44100個(gè)樣本的采樣率進(jìn)行數(shù)字化的，足以捕獲高達(dá)22050Hz的頻率禀酱。

視頻壓縮

所有的壓縮系統(tǒng)都需要兩個(gè)算法：一個(gè)用于在源端進(jìn)行數(shù)據(jù)壓縮炬守，另一個(gè)用于在目的端對(duì)數(shù)據(jù)進(jìn)行解壓縮。分別為編碼算法和解碼算法剂跟。

編碼與解碼具有某些不對(duì)稱性减途。視頻信號(hào)經(jīng)過(guò)編碼和解碼之后與原始信號(hào)存在輕微差異時(shí)，系統(tǒng)被稱為是有損的（lossy）曹洽。

JPEG標(biāo)準(zhǔn)

用于壓縮連續(xù)色調(diào)靜止圖像的JPEG（Joint Photographic Experts Group鳍置，聯(lián)合攝影專家組）。用于壓縮運(yùn)動(dòng)圖像的MPEG不過(guò)是分別對(duì)每一幀進(jìn)行JPEG編碼送淆，再加上某些幀間壓縮和運(yùn)動(dòng)補(bǔ)償?shù)阮~外的特征税产。

MPEG標(biāo)準(zhǔn)

MPEG（Motion Picture Experts Group，運(yùn)行圖像專家組）標(biāo)準(zhǔn)是用于壓縮視頻的主要算法偷崩。

MPEG的兩個(gè)版本均利用了在電影中存在的兩類冗余：空間冗余和時(shí)間冗余辟拷。MPEG-2輸出有三種不同的幀組成：

1. I幀：自包含的JPEG編碼靜止圖像
2. P幀：與上一幀逐塊的差。
3. B幀：與上一幀和下一幀的差环凿。

音頻壓縮

最流行的是MP3（MPEG音頻層3）梧兼，屬于MPEG視頻壓縮標(biāo)準(zhǔn)里的音頻部分放吩。

音頻壓縮可由兩種方法完成智听。波形編碼技術(shù)和感知編碼。

多媒體進(jìn)程調(diào)度

• 調(diào)度同質(zhì)進(jìn)程
• 一般實(shí)時(shí)調(diào)度
• 速率單調(diào)調(diào)度
• 最早最終時(shí)優(yōu)先調(diào)度

多媒體文件系統(tǒng)范型

• VCR控制功能
• 近似視頻點(diǎn)播
• 具有VCR功能的近似視頻點(diǎn)播

文件存放

多媒體文件非常龐大、通常只寫一次而讀許多次到推，并且傾向于被順序訪問考赛。

• 在單個(gè)磁盤上存放文件
• 兩個(gè)替代的文件組織策略
• 近似視頻點(diǎn)播的文件存放
• 在單個(gè)磁盤上存放多個(gè)文件
• 在多個(gè)磁盤上存放文件

高速緩存

• 塊高速緩存
• 文件高速緩存

多媒體磁盤調(diào)度

• 靜態(tài)磁盤調(diào)度
• 動(dòng)態(tài)磁盤調(diào)度

8、多處理機(jī)系統(tǒng)

多處理機(jī)

共享存儲(chǔ)器多處理機(jī)（multiprocessor）是這樣一種計(jì)算機(jī)系統(tǒng)莉测，其兩個(gè)或更多的CPU全部共享訪問一個(gè)公用的RAM颜骤。

• UMA（Uniform Memory Access，統(tǒng)一存儲(chǔ)器訪問）
• NUMA（Nonuniform Memory Access捣卤，非統(tǒng)一存儲(chǔ)器訪問）

多處理機(jī)硬件：

• 基于總線的UMA多處理機(jī)體系結(jié)構(gòu)
• 使用交叉開關(guān)的UMA多處理機(jī)
• 使用多級(jí)交換的UMA多處理機(jī)
• NUMA多處理機(jī)
• 多核芯片

多處理機(jī)操作系統(tǒng)類型：

• 每個(gè)CPU有自己的操作系統(tǒng)
• 主從多處理機(jī)
• 對(duì)稱多處理機(jī)

多處理機(jī)調(diào)度

• 分時(shí)
• 空間共享
• 群調(diào)度

多計(jì)算機(jī)

多處理機(jī)硬件

• 互連技術(shù)
• 網(wǎng)絡(luò)接口

底層通信軟件

用戶層通信軟件

• 發(fā)送和接收
• 阻塞調(diào)用和非阻塞調(diào)用

分布式共享存儲(chǔ)器

• 復(fù)制
• 偽共享
• 實(shí)現(xiàn)順序一致性

負(fù)載平衡

• 圖論確定算法
• 發(fā)送者發(fā)起的分布式啟發(fā)算法
• 接收者發(fā)起的分布式啟發(fā)算法

虛擬化

分布式系統(tǒng)

網(wǎng)絡(luò)硬件

• 以太網(wǎng)
• 因特網(wǎng)

網(wǎng)絡(luò)服務(wù)協(xié)議

• 網(wǎng)絡(luò)服務(wù)
• 網(wǎng)絡(luò)協(xié)議

基于文檔的中間件

基于文件系統(tǒng)的中間件

• 傳輸模式
• 目錄層次
• 命名透明性
• 文件共享的語(yǔ)義

基于對(duì)象的中間件

基于協(xié)作的中間件

• Linda
• 發(fā)布/訂閱
• Jini

網(wǎng)絡(luò)

9忍抽、安全

環(huán)境安全

• 威脅

  • 計(jì)算機(jī)系統(tǒng)主要安全目標(biāo)

    1. 數(shù)據(jù)機(jī)密性
    2. 數(shù)據(jù)完整性
    3. 數(shù)據(jù)可用性
    4. 排外性

  • 計(jì)算機(jī)系統(tǒng)主要安全威脅

    1. 數(shù)據(jù)暴露
    2. 數(shù)據(jù)篡改
    3. 拒絕服務(wù)
    4. 系統(tǒng)被病毒控制

• 入侵者

  • 入侵者表現(xiàn)形式

    • 被動(dòng)入侵
    • 主動(dòng)入侵

  • 入侵者種類

    1. 非專業(yè)用戶的隨意瀏覽
    2. 內(nèi)部人員的窺視
    3. 為獲取利益而嘗試
    4. 商業(yè)或軍事間諜

• 數(shù)據(jù)意外遺失

  • 天災(zāi)
  • 軟硬件錯(cuò)誤
  • 認(rèn)為過(guò)失

密碼學(xué)原理

明文與密文之間的關(guān)系：

明文與密文之間的關(guān)系

• 私鑰加密技術(shù)。對(duì)稱加密董朝，安全性取決于對(duì)密鑰的管理
• 公鑰加密技術(shù)鸠项。每個(gè)人都有公鑰和私鑰，公開其中的公鑰子姜，用公鑰加密祟绊，只能用對(duì)應(yīng)私鑰解密。
• 單向函數(shù)哥捕。散列函數(shù)
• 數(shù)字簽名
• 可信平臺(tái)模塊（Trusted Platform Modules牧抽，TPM）。是一種加密處理器遥赚，使用內(nèi)部的非易失性存儲(chǔ)介質(zhì)來(lái)保存密鑰扬舒。

保護(hù)機(jī)制

• 保護(hù)域
• 訪問控制表
• 權(quán)能
• 可信系統(tǒng)
• 可信計(jì)算基
• 安全系統(tǒng)的形式化模型
• 多級(jí)安全
• 隱蔽信道

認(rèn)證

• 使用口令認(rèn)證
• 使用實(shí)際物體的認(rèn)證方式
• 使用生物識(shí)別的驗(yàn)證方式

內(nèi)部攻擊

• 邏輯炸彈
• 后門陷阱
• 登錄欺騙

利用代碼漏洞

• 緩沖區(qū)溢出攻擊
• 格式化字符串攻擊
• 返回libc攻擊
• 整數(shù)溢出攻擊
• 代碼注入攻擊
• 權(quán)限提升攻擊

惡意軟件

• 特洛伊木馬
• 病毒
• 蠕蟲
• 間諜軟件
• rootkit

防御

• 防火墻
• 反病毒和抑制病毒技術(shù)
• 代碼簽名
• 囚禁
• 基于模型的入侵檢測(cè)
• 封裝移動(dòng)代碼
• Java安全性