《現代作業系統》讀書筆記

1、導論

與使用者互動的程式：

• 基于文本的shell
• 基于圖示的圖形化使用者界面（GUI）

作業系統所處的位置：

多數計算機有兩種運作模式：

• 核心态（管态），作業系統運作在此模式，能夠執行任何指令。
• 使用者态，使用者軟體運作在此模式，使用機器指令中的子集。

作業系統的功能：

• 為使用者程式提供抽象
• 管理計算機資源

抽象是管理複雜性的一個關鍵。好的抽象可以把一個幾乎不可能管理的任務劃分為兩個可管理的部分：

• 有關抽象的定義和實作
• 随時用這些抽象解決問題

作業系統發展曆史

1. 1945~1955：真空管和穿孔卡片
2. 1955~1965：半導體和批處理系統
3. 1965~1980：內建電路晶片和多道程式設計
4. 1980~至今：個人計算機

計算機硬體

• CPU
• 存儲器
• 磁盤
• 錄音帶
• I/O裝置
• 總線

大型Pentium系統結構：

Pentium系統的啟動過程：

• 主機闆上有一個基本輸入輸出系統（BIOS），其中有底層I/O軟體。
• 計算機啟動時，BIOS開始運作。
• 首先檢查安裝RAM數量，鍵盤和其他基本裝置是否已安裝并正常相應。
• 開始掃描ISA和PCI總線并找出連接配接在上面的所有裝置，記錄下來。
• 如果現有裝置和系統上一次啟動時的裝置不同，則配置新的裝置。
• BISO通過存儲在CMOS存儲器中的裝置清單決定啟動裝置。
• 啟動裝置上的第一個扇區被讀入記憶體并執行。
• 啟動扇面末尾的分區表檢查的程式，确定哪個分區是活動的。
• 從活動分區讀入第二個啟動裝載子產品，裝在子產品被讀入作業系統。
• 作業系統詢問BIOS，以獲得配置資訊。
• 系統檢查每種裝置驅動程式是否存在，有就将裝置驅動程式調入核心。
• 系統建立背景程序，在終端上啟動登入程式或GUI。

作業系統概念

程序：

程序本質是正在執行的一個程式。與一個程序有關的所有資訊，除了該程序自身位址空間的内容以外，均存放在作業系統的一張表中，稱為程序表（數組或連結清單結構）。

位址空間：

現代作業系統通常使用虛拟記憶體技術。作業系統可以把部分位址空間裝入主存，部分留在磁盤上，在需要時再交換它們。

檔案：

大多數系統都有目錄結構，目錄項可以是檔案或者目錄，構成了一種層次結構（檔案系統）。程序和檔案層次都可以組織成樹狀結構，一般程序的樹狀結構層次不深，而且是暫時的；檔案樹的層次常常多達四層、五層或者更多層，存在時間可能達數年。

輸入/輸出：

所有計算機都有用來擷取輸入和産生輸出的實體裝置。包括鍵盤、顯示器、列印機等。

保護：

例如UNIX系統中對檔案實作保護，三個3位保護字段（rwxrwxrwx），分别表示所有者、所有者同組使用者、其他使用者的讀、寫、執行權限。

shell：

UNIX的指令解釋器稱為shell，不是作業系統的一部分。shell是終端使用者與作業系統之間的界面，除非使用者使用的是GUI界面。

系統調用

系統調用

read(fd, &buffer, nbytes)

函數的過程：

1. 參數nbytes壓棧
2. 參數&buffer壓棧
3. 參數fd壓棧
4. 對庫過程read進行實際調用
5. 把系統調用的編号放在寄存器中
6. 執行TRAP指令，切換到核心态，在核心中一個固定位址開始執行
7. 核心代碼檢查系統調用編号，發出系統調用處理指令
8. 系統調用句柄執行
9. 控制傳回給使用者空間庫過程
10. 以通常的過程調用傳回的方式，傳回到使用者程式
11. 使用者程式清除堆棧空間

作業系統結構

• 單體系統
• 層次式系統
• 微核心
• 客戶機-伺服器模式
• 虛拟機
• 外核

C語言

編譯C和頭檔案，構件可執行程式的過程：

2、程序與線程

程序

程序模型

作業系統中最核心的概念是程序：這是對正在運作程式的一個抽象。

一個程序就是一個正在執行程式的執行個體、包括程式計數器、寄存器和變量的目前值。

在多道程式設計中，一個CPU能在多個程序之間來回快速切換，達到（僞）并行效果。

一個程序是某種類型的一個活動，它有程式、輸入、輸出以及狀态。

單個處理器可以被若幹程序共享，它使用某種排程算法巨頂何時停止一個程序的工作，并轉而為另一個程序提供服務。

建立程序

4種主要事件導緻程序的建立：

1. 系統初始化
2. 執行了正在運作的程序所調用的程序建立系統調用
3. 使用者請求建立一個新程序
4. 一個批處理作業的初始化

在UNIX系統中，隻有一個系統調用可以用來建立新程序：

fork

。

這個系統調用會建立一個與調用程序相同的副本。

在調用

fork

後，這兩個程序（父程序和子程序）擁有相同的存儲映像、同樣的環境字元串和同樣打開的檔案。

通常子程序接着執行

execve

系統調用，以修改其存儲映像并運作一個新的程式。

在Windows系統中，一個Win32函數調用

CreateProcess

即處理程序的建立，也負責把正确的程式裝入新的程序。

在UNIX中，子程序的初始位址空間是父程序的一個副本，不可寫的記憶體區是共享的，新程序有可能共享其建立者的其他資源。

在Windows中，從一開始父程序的位址空間和子程序的位址空間解釋不同的。

程序的終止

程序的終止通常由以下條件引起：

1. 正常退出（自願的）
2. 出錯退出（自願的）
3. 嚴重錯誤（非自願）
4. 被其他程序殺死（非自願）

程序的層次結構

在UNIX系統中，程序隻有一個父程序，但可以有多個子程序。

程序和它的所有子女以及後裔共同組成一個程序組。

Windows系統中沒有程序層次的概念，所有的程序都是地位相同的。

程序的狀态

程序的三種狀态：

1. 運作态（該時刻程序實際占用CPU）
2. 就緒态（可運作，但應為其他程序正在運作而暫時停止）
3. 阻塞态（除非某種外部事件發生，否則程序不能運作）

1. 程序為等待輸入而阻塞
2. 排程程式選擇另一個程序
3. 排程程式選擇這個程式
4. 出現有效輸入

程序的實作

作業系統維護着一張表（一個結構數組），即程序表（process table）。

每個程序占用一個程序表項（又稱程序控制塊）。

終端發生後作業系統最底層的工作步驟：

1. 硬體壓入堆棧程式計數器等。
2. 硬體從中斷向量裝入新的程式計數器。
3. 彙編語言過程儲存寄存器值。
4. 彙編語言過程設定新的堆棧。
5. C終端服務例程運作（典型地讀和緩沖輸入）。
6. 排程程式決定下一個将運作的程序。
7. C過程傳回至彙編代碼。
8. 彙編語言過程開始運作新的目前程序。

2. 線程

線程的使用

線程是一種輕量級的程序。

• 多個線程擁有共享同一個位址空間和所有可用資料的能力。
• 線程比程序更容易建立和銷毀。
• 在大量計算和大量I/O處理過程中，多個線程能夠加快程式執行速度。

經典的線程模型

程序模型基于兩種對立的概念：資源分組處理與執行。

了解程序的一個角度是，用某種方法把相關的資源集中在一起。

另一個概念是，程序擁有一個執行的線程。

線程擁有自己的程式計數器、寄存器、堆棧。

程序用于把資源集中到一起，而線程則是在CPU上被排程執行的實體。

線程可以處于若幹狀态中的任何一個：運作、阻塞、就緒或終止。

POSIX線程

為實作可移植的線程程式，IEEE指定了線程的标準。

它定義的線程包叫做Pthread，大部分UNIX系統都支援該标準。

所有Pthread線程都有某些特性。

每一個都含有一個辨別符、一組寄存器（包括程式計數器）和一組存儲在結構中的屬性。

這些屬性包括堆棧大小、排程參數以及使用線程需要的其他項目。

線程調用	描述
pthread_create	建立一個新線程
pthread_exit	結束調用的線程
pthread_join	等待一個特定的線程退出
pthread_yield	釋放CPU來運作另外一個線程
pthread_attr_init	建立并初始化一個線程的屬性結構
pthread_attr_destory	删除一個線程的屬性結構

線程包的實作方式

在使用者空間中實作

把整個線程包放在使用者空間中，核心對線程包一無所知。從核心角度考慮，就是單線程程序。

線程在一個運作時系統的頂部運作，這個運作時系統是一個管理線程的過程的集合。

每個程序有其專用線程表（thread table）。

優點：使用者線程包可以在不支援線程的作業系統上實作。

不需要陷進，不需要上下文切換，不需要對記憶體高速緩存進行重新整理，使得線程排程非常快。

允許每個程序有自己定制的排程算法。

問題：如何實作阻塞系統調用，使用阻塞調用會阻塞其他的線程。

頁面故障問題，如果某個調用跳轉到了一條不再記憶體的指令上，就會發生頁面故障，核心由于不知道線程的存在，通常會把整個程序阻塞到I/O完成。

如果一個線程開始運作，那麼該程序中的其他線程就不能運作，除非第一個線程自動放棄CPU。

在核心中實作線程

此時不需要運作時系統，核心中有用來記錄系統中所有線程的線程表。

當一個線程阻塞時，核心根據其選擇，可以運作同一個程序中的另一個線程或者運作另一個程序中的線程。

優點：核心很容線上程阻塞時切換到另一個線程執行。

核心線程不需要任何新的、非阻塞系統調用。

問題：在核心中建立或銷毀線程的代價比較大。

程序建立問題，一個多線程程序建立新線程出現的問題。

當信号到達時，應該有哪一個線程處理。

混合實作

使用核心線程，然後将使用者級線程與某些或者全部核心線程多路複用起來。

核心隻識别核心線程，并對其進行排程。一些核心線程會被多個使用者級線程多路複用。

這一模型能夠帶來最大的靈活度。

排程程式激活機制

當核心了解到一個線程被阻塞之後，核心通知該程序的運作時系統，并且在堆棧中以參數的形式傳遞有問題的線程的編号和所發生事件的一個描述。

核心通過在一個已知的起始位址啟動運作時系統，進而發出通知，這是對UNIX中信号的一種粗略模拟。

這個機制稱為上行調用（upcall）。

排程程式激活機制的一個目标是作為上行調用的信賴基礎，這是一種違反分層系統内在結構的概念。

程序間通信

程序間通信（Inter Process Communication，IPC）簡要的說有三個問題：

1. 一個程序如何把資訊傳遞給另一個。
2. 確定兩個或更多的程序在關鍵活動中不會出現交叉。
3. 保證程序以正确的順序執行。

競争條件

在一些作業系統中，協作的程序可能共享一些彼此都能讀寫的公用存儲區。

兩個或多個程序讀寫某些共享資料，而最後的結果取決于程序運作的精确時序，稱為競争條件（race condition）。

臨界區

阻止多個程序同時讀寫共享的資料可以通過互斥（mutual exclusion）。

確定黨一個程序在使用一個共享資料時，其他程序不能做同樣的操作。

我們把對共享記憶體進行通路的程式片段稱作臨界區（critical section）。

一個好的解決方案，需要滿足一下4個條件：

1. 任何兩個程序不能同時處于臨界區。
2. 不應對CPU的速度和數量做任何假設。
3. 臨界區外運作的程式不得阻塞其他程序。
4. 不得使程序無限期等待進入臨界區。

忙等待的互斥

屏蔽中斷

每個程序在剛剛進入臨界區後立即屏蔽所用中斷，并在就要離開之前再打開中斷。

适用于單核作業系統，對作業系統本身而言很有用，單對于使用者程序則不是一種合适的互斥機制。

鎖變量

共享鎖變量，初始為0。當程序想進入臨界區時，首先測試這把鎖。

如果鎖為0，則程序将所設定為1并進入臨界區。

如果鎖為1，則程序将等待其值變為0。

這種方式同樣存在競争條件。

嚴格輪換法

連續測試一個變量直到某個值出現為止，稱為忙等待。

這種方式浪費CPU時間，通常應該避免。

隻有在有理由認為等待時間是非常短的情形下，才使用忙等待。

用于忙等待的鎖，稱為自旋鎖（spin lock）。

Peterson解法

#define FALSE   0
#define TRUE    1
#define N       2                       /* 程序數量 */

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

void enter_region(int process)          /* 程序是0或1 */
{
    int other;                          /* 其他程序号 */

    other =  - process;                /* 另一方程序 */
    interested[process] = TRUE;         /* 表明所感興趣的 */
    turn = process;                     /* 設定标志 */
    while (turn == process && interested[other] == TRUE);   /* 空語句 */
}

void leave_region(int process)          /* 程序：誰離開? */
{
    interested[process] = FALSE;        /* 表示離開臨界區 */
}
           

TSL指令

需要硬體支援的一種方案。

某些計算機中，特别是那些設計為多處理器的計算機。

都有指令

TSL RX, LOCK

。

稱為測試并加鎖（Test and Set Lock），他将一個記憶體字lock讀到寄存器RX中，然後再該記憶體位址上存一個非零值。

讀字和寫字操作保證是不可分割的。

一個可替代TSL的指令時XCHG，它原子性的交換兩個位置的内容。

睡眠與喚醒

Peterson解法和TSL或XCHG解法都有忙等待的缺點。

這種方法不僅浪費了CPU時間，而且還可能引起預想不到的結果。

生産者-消費者問題。兩個程序共享一個公共的固定大小的緩沖區。

其中一個是生産者，将資訊放入緩沖區；另一個是消費者，從緩沖區中取出資訊。

信号量

信号量（semaphore）是Dijkstra在1965年提出的一種方法，使用一個整型變量來累計喚醒次數。

兩種操作：down和up。

對一信号量執行down操作，則是檢查其值是否大于0。

若大于0，則将其值減1并繼續；若為0，則程序将睡眠，此時down操作并未結束。

up操作對信号量的值增1。

如果一個或多個程序在該信号量上睡眠，無法完成一個先前的down操作，則有系統選擇其中一個允許程序完成它的down操作。

信号量可以用來實作同步（synchronization）。

互斥量

如果不需要信号量的技術能力，有時可以使用信号量的一個簡化版本，稱為互斥量（mutex）。

互斥量是一個可以處于兩态之一的變量：解鎖和加鎖。

一些與互斥量相關的pthread調用：

線程調用	描述
pthread_mutex_init	建立一個互斥量
pthread_mutex_destroy	撤銷一個已存在的互斥量
pthread_mutex_lock	獲得一個鎖或阻塞
pthread_mutex_trylock	獲得一個鎖或失敗
pthread_mutex_unlock	釋放一個鎖

一些與條件變量相關的pthread調用：

線程調用	描述
pthread_cond_init	建立一個條件變量
pthread_cond_destroy	撤銷一個條件變量
pthread_cond_wait	阻塞以等待一個信号
pthread_cond_signal	向另一個線程發信号來喚醒它
pthread_cond_broadcast	向多個線程發信号來讓他們全部喚醒

管程

一個管程（monitor）是一個由過程、變量及資料結構等組成的一個集合，它們組成一個特殊的子產品或軟體包。

程序可在任何需要的時候調用管程中的過程，但他們不能在管程之外聲明的過程中直接通路管程内部的資料結構。

管程是一種語言概念，C語言不支援。

消息傳遞

消息傳遞（message passing）面臨許多問題和設計難點，特别是位于網絡中不同機器上的通信程序的情況。

消息系統還需要解決程序命名問題。身份認證（authentication）也是一個問題。

消息從一個程序複制到另一個程序通常比信号量操作和進入管程要慢。

屏障

屏障是用于程序組而不是用于雙程序的生産者-消費者情形的。

某些應用中劃分了若幹階段，除非所有的程序都準備着手下一個階段，否則任何程序都不能進入下一個階段。

可以通過在每個階段的結尾安置屏障（barrier）來實作。

排程

多道程式設計系統中，多個線程或程序同時競争CPU，當隻有一個CPU可用時，那麼久必須選擇下一個要運作的程序。

完成選擇工作的這一部分稱為排程程式（scheduler），該程式使用的算法稱為排程算法（scheduling algoritgm）。

程序行為

幾乎所有程序的（磁盤）I/O請求或計算都是交替突發的。

CPU不停頓地運作一段時間，然後發出一個系統調用以便讀寫檔案。

在完成系統調用之後，CPU又開始計算，直到它需要讀取更多的資料或寫更多的資料為止。

某些程序花費了絕大多數時間在計算上，而其他程序則在等待I/O上花費了絕大多數時間。

前者稱為計算密集型（computer-bound），後者稱為I/O密集型（I/O-bound）。

何時排程

需要處理各種情形：

1. 在建立一個新程序後，需要決定是運作父程序還是運作子程序。
2. 在一個程序退出時必須做出排程決策。
3. 當一個程序阻塞在I/O和信号量上或者由于其他原因阻塞時，必須選擇另一個程序運作。
4. 在一個I/O中斷發生時，必須做出排程決策。

非搶占式排程算法：挑選一個程序，然後讓該程序運作直至被阻塞，或者直到程序自動釋放CPU。

搶占式排程算法：選擇一個程序，讓該程序運作某個固定時段的最大值。

如果時段結束程序任在運作則被挂起，排程程式選擇另外一個程序運作。

排程算法分類

三種環境

1. 批處理。非搶占式，或長時間周期的搶占式算法
2. 互動式。搶占式算法
3. 實時。搶占有時是不需要的。

排程算法的目标

• 所有系統
  • 公平——給每個程序公平的CPU份額
  • 政策強制執行——看到鎖宣布的政策執行
  • 平衡——保持系統的所有部分都忙碌
• 批處理系統
  • 吞吐量——每小時最大作業數
  • 周轉時間——從送出到終止間的最小時間
  • CPU使用率——保持CPU時鐘忙碌
• 互動式系統
  • 響應時間——快速響應請求
  • 均衡性——滿足使用者的期望
• 實時系統
  • 滿足截止時間——避免丢失資料
  • 可預測性——在多媒體系統中避免品質降低

批處理系統中的排程

• 先來先服務
• 最短作業優先
• 最短剩餘時間優先

互動式系統中的排程

• 輪轉排程
• 優先級排程
• 多級隊列
• 最短程序優先
• 保證排程
• 彩票排程
• 公平分享排程

實時系統中的排程

實時系統的排程算法可以是靜态的或動态的。

前者在系統開始運作之前做出排程決策；後者在運作過程中程序排程決策。

3、存儲管理

現代作業系統使用分層存儲器體系（memory hierarchy）。作業系統中管理分層存儲器體系的部分稱為存儲管理器（memory manager），即記錄那些記憶體是正在使用的，那些記憶體是空閑的；在程序需要時為其配置設定記憶體，在程序是用完後釋放記憶體。

無存儲抽象

最簡單的存儲器抽象就是根本沒有抽象。早期計算機沒有存儲器抽象，每個程式都直接通路實體記憶體。想要在記憶體中同時運作兩個程式是很困難的。

一種存儲器抽象：位址空間

暴露實體記憶體給程序的問題：

1. 如果使用者程式可以尋址記憶體中的每個位元組，它能很容易破壞作業系統。
2. 使用這種模型想同時運作多個城市是很困難的。

位址空間的概念

保證多個應用程式同時處于記憶體中并且不互相影響，需要解決兩個問題：保護和重定位。

位址空間為程式創造了一種抽象的記憶體。每個程序都有自己的位址空間，并且這個位址空間獨立于其他程序的位址空間。

基址寄存器與界限寄存器

動态重定位，簡單地把每個程序的位址空間映射到實體記憶體的不同部分。程式裝在到記憶體期間無須重定位，程式的起始實體位址裝在到基址寄存器中，程式的長度裝在到界限寄存器中。

缺點：每次通路記憶體都需要進行加法和比較運作。

交換技術

兩種處理記憶體超載的方法：交換（swapping）技術，虛拟記憶體（virtual memory）。

如果大部分程序在運作時都要增長，可以在換入或移動程序時為它多配置設定一些額外的記憶體，例如資料段與堆棧段。

空閑記憶體管理

兩種跟蹤記憶體使用情況的方法：位圖，空閑連結清單。

查找位圖中指定長度的連續0串是耗時操作，這是位圖的缺點。

連結清單管理法适配方式：

• 首次适配（first fit）：存儲管理器沿着連結清單進行搜尋，直到找到一個足夠大的空閑區。
• 下次适配（next fit）：每次找到合适的空閑區都記錄，以便下次從此開始搜尋。
• 最佳适配（best fit）：搜尋整個表，找出能夠容納程序的最小空閑區。
• 最差适配（worst fit）：總是配置設定最大的可用空閑區，使新的空閑區比較大。
• 快速适配（quick fit）：為那些常用大小的空閑區維護單獨的連結清單。

虛拟記憶體

基本思想：每個程式擁有自己的位址空間，這個空間被分割成多個塊，每一塊稱作一頁或頁面（page）。每一頁有連續的位址範圍。這些頁被映射到實體記憶體，但并不是多有的頁都必須在記憶體中才能運作程式。當程式引用到一部分在實體記憶體中的位址空間使，由硬體立刻執行必要的映射。放程式引用到一部分不再實體記憶體中的位址空間時，由作業系統負責将缺失的部分裝入實體記憶體并重新執行失敗的指令。

分頁

由程式産生的位址稱為虛拟位址（virtual address），它們構成了一個虛拟位址空間（virtual address space）。在沒有虛拟記憶體的計算機上，系統直接将虛拟位址送到記憶體總線上，讀寫操作使用具有同樣位址的實體記憶體字；而在使用虛拟記憶體的情況下，虛拟位址不是被直接送到記憶體總線上，而是被送到記憶體管理單元（Memory Management Unit，MMU），MMU把虛拟位址映射為實體記憶體位址。

虛拟位址空間按照固定大小劃分成頁面（page）的若幹單元。在實體記憶體中對應的單元稱為頁框（page frame）。頁面和頁框的大小通常是一樣的。

當MMU注意到某頁面沒有被映射，于是使CPU陷入到作業系統，這個陷進稱為缺頁中斷（page fault）。作業系統找到一個很少使用的頁框且把它的内容寫入磁盤。随後把需要通路的頁面讀到剛才回收的頁框中，修改映射關系，然後重新啟動引起陷進的指令。

頁表

簡單的，虛拟位址被分成虛拟頁号（高位部分）和偏移量（低位部分）。虛拟頁号可用作頁表的索引，以找到該虛拟頁面對應的頁表項。由頁表項可以找到頁框号。然後把頁框号拼接到偏移量的高位端，以替換掉虛拟頁号，形成送往記憶體的實體位址。

頁表項的結構

• 頁框号
• “在/不在”位：對應的虛拟頁面在不在記憶體中
• 保護位：三位，表示讀寫執行
• 修改位
• 通路位
• 高速緩存禁止位

加速分頁過程

在任何分頁式系統中，都需要考慮兩個主要問題：

1. 虛拟位址到實體位址的映射必須非常快。
2. 如果虛拟位址空間很大，頁表也會很大。

解決方式：

• 轉換檢測緩沖區（Translation Lookaside Buffer，TLB）。大多數程式總是對少量的頁面進行多次通路。
• 軟體TLB管理

針對大記憶體的頁表

• 多級頁表：避免把全部頁表一直儲存在記憶體中。
• 倒排頁表：在實際記憶體中每一個頁框有一個表項，而不是每一個虛拟頁面有一個表項。

頁面置換算法

當發生缺頁中斷時，作業系統必須在記憶體中選擇一個頁面将其換出記憶體。如果要換出的頁面在記憶體駐留期間已被修改，就必須寫回磁盤；如果沒有修改直接被覆寫就可以了。

• 最優頁面置換算法：置換最久将要被通路的頁面。此算法無法實作。
• 最近未使用頁面置換算法（Not Recently Used，NRU）：随機地從類編号最小的非空類中挑選一個頁面淘汰之。
  1. 沒有被通路，沒有被修改
  2. 沒有被通路，已被修改
  3. 已被通路，沒有被修改
  4. 已被通路，已被修改
• 先進先出頁面置換算法（First-In，First-Out，FIFO）：每次置換連結清單的表頭。
• 第二次機會頁面置換算法：檢查最老頁面的通路位。如果是0則立刻置換，如果是1則修改為0并把該頁面放到連結清單尾端。
• 時鐘頁面置換算法：環形連結清單，有一個表針指向最老頁面。首先檢查表針，如果R位是0就淘汰頁面，插入頁面後表針前移一個位置。如果R位是1就清除R并把表針前移一個位置，直到找到R為0的頁面。
• 最近最少使用頁面置換算法（Least Recently Used，LRU）：置換未使用時間最長的頁面。
• 工作集頁面置換算法：程序目前正在使用的頁面的集合稱為它的工作集（working set）。缺頁中斷時淘汰一個不再工作集中的頁面。
• 工作集時鐘頁面置換算法

頁面置換算法小結

算法	注釋
最優算法	不可實作，但可用作基準
NRU（最近未使用）算法	LRU的很粗糙的近似
FIFO（先進先出）算法	可能抛棄重要的頁面
第二次機會算法	比FIFO有大的改善
時鐘算法	現實的
LRU（最近最少使用）算法	很優秀，但很難實作
NFU（最不常用）算法	LRU的相對粗略的近似
老化算法	非常近似LRU的有效算法
工作集算法	實作起來開銷很大
工作集時鐘算法	好的有效算法

分頁系統中的設計問題

• 局部配置設定政策與全局配置設定政策：當發生缺頁中斷時，頁面置換算法在尋找最近最少使用的頁面時，隻考慮配置設定給該程序的頁面，稱為局部頁面置換算法；考慮所有在記憶體中的頁面，稱為全局頁面置換算法。
• 負載控制
• 頁面大小：确定最佳頁面大小。
• 分離的指令空間和資料空間：為指令和資料設定分離的位址空間
• 共享頁面：UNIX系統中進行

  fork

  系統調用後，父子程序共享程式文本和資料。這些程序擁有自己的頁表，但都指向同一個頁面集合。隻要有一個程序要求更新資料，就會觸發隻讀保護，引發作業系統陷進，生成該頁的一個副本。這種方式稱為寫時複制。
• 共享庫：如果其他程式已經裝載了某個共享庫，另一個程式就沒必要再次裝載了。編譯共享庫時，使用-fPIC産生位置無關代碼。
• 記憶體映射檔案：程序可以通過發起一個系統調用，将一個檔案映射到虛拟位址空間的一部分。在通路頁面時每次一頁的讀入。多個程序可以通過映射同一個檔案來通信。
• 清除政策：如果發生缺頁中斷時系統中有大量的空閑頁框，此時分頁系統工作在最佳狀态。一種實作清除政策的方法就是使用一個雙指針時鐘。
• 虛拟記憶體接口

有關實作的問題

• 與分頁有關的工作：操縱系統要在四段時間裡做與分頁相關的工作。程序建立時，程序執行時，缺頁中斷時，程序終止時。
• 缺頁中斷處理
  1. 硬體陷入核心，在堆棧中儲存程式計數器。
  2. 啟動一個彙編代碼例程儲存通用寄存器和其他易失的資訊，以免被作業系統破環。
  3. 當作業系統發現一個缺頁中斷時，嘗試發現需要哪個虛拟頁面。
  4. 一旦知道發生缺頁中斷的虛拟位址，作業系統檢查這個位址是否有效，并檢查存取與保護是否一緻。
  5. 如果選擇的頁框“髒”了，安排該頁寫回磁盤，并發生一次上下文切換，挂起産生缺頁中斷的程序，讓其他程序運作直至磁盤傳輸結束。
  6. 一旦頁框“幹淨”後，作業系統查找所需頁面在磁盤上的位址，通過磁盤操作将其裝入。
  7. 當磁盤中斷發生時，表明該頁已經被裝入，頁表已經更新可以反應它的位置，頁框也被标記為正常狀态。
  8. 恢複發生缺頁中斷指令以前的狀态，程式計數器重新指向這條指令。
  9. 排程引發缺頁中斷的程序，作業系統傳回調用它的彙編語言例程。
  10. 該例程恢複寄存器和其他狀态資訊，傳回到使用者空間繼續執行，就好像缺頁中斷沒有發生過一樣。
• 指令備份：使用一個隐藏的内部寄存器。在每條指令執行之前，把程式計數器的内容複制到該寄存器中。
• 鎖定記憶體中的頁面：保證正在做I/O操作的頁面不會被移出記憶體。
• 後備存儲
• 政策和機制的分離

分段

分頁和分段的比較

考察點	分頁	分段
需要程式員了解正在使用這種技術嗎？	否	是
存在多少線性位址空間？	1	許多
整個位址空間可以超出實體存儲器的大小嗎？	是	是
過程和資料可以内區分并分别被保護嗎？	否	是
其大小浮動的表可以很容易提供嗎？	否	是
使用者間過程的共享友善嗎？	否	是
為什麼發明這種技術？	為了得到大的線性位址空間而不必購買更大的實體存儲器	為了使程式和資料可以被劃分為邏輯上獨立的位址空間并且有助于共享和保護

4、檔案系統

檔案

• 檔案命名：在具體系統中規則不一，UNIX檔案系統區分大小寫，MS-DOS檔案系統不區分大小寫。
• 檔案結構：位元組序列、記錄序列、樹。所有UNIX、MS-DO、Windows系統都把檔案看成無結構位元組序列。
• 檔案類型：ASCII檔案和二進制檔案。
• 檔案存取：順序存取和随機存取。
• 檔案屬性：檔案的附加資訊，稱為屬性（attribute）或中繼資料（matedata）。
• 檔案操作：常用系統調用

  • create

    ：建立不包含任何資料的檔案。

  • detele

    ：删除檔案釋放磁盤空間。

  • open

    ：打開檔案，把檔案屬性和磁盤位址表裝入記憶體，便于後續調用。

  • close

    ：關閉檔案釋放内部表空間。

  • read

    ：在檔案中讀取資料。

  • write

    ：向檔案中寫資料。

  • append

    ：在檔案末尾添加資料。

  • seek

    ：對于随機存取檔案，指定從何處開始取資料。

  • get attribute

    ：讀取檔案屬性。

  • set attribute

    ：某些屬性可由使用者設定。

  • rename

    ：改變已有檔案的名字。

目錄

• 一級目錄系統：一個目錄中包含所有檔案，稱為根目錄。能快速定位檔案。
• 層次目錄系統：階層化的目錄樹結構，幾乎所有現代檔案系統都采用。
• 路徑名：絕對路徑與相對路徑。
• 目錄操作：常用基本系統調用。

  • create

    ：建立目錄，處理目錄項.和..外，目錄内容為空。

  • delete

    ：删除目錄。

  • opendir

    ：打開目錄以備讀取。

  • closedir

    ：關閉目錄釋放内部表空間。

  • readdir

    ：讀取目錄傳回目錄下一個目錄項。

  • rename

    ：更改目錄名稱。

  • link

    ：連接配接技術允許在多個目錄中出現同一個檔案。

  • unlink

    ：删除目錄項。

檔案系統的實作

檔案系統布局

檔案系統存放在磁盤上。多數磁盤劃分為一個或多個分區，每個分區中有一個獨立的檔案系統。磁盤的0号扇區稱為主引導記錄（Master Boot Record，MBR），用來引導計算機。在MBR的結尾是分區表。該表給出了每個分區的起始位址和結束位址。表中的一個分區被标記為活動分區。在計算幾被引導時，BIOS讀入并執行MBR。MBR做的第一件事是确定活動分區，讀入它的第一個塊，稱為引導塊（boot block），并執行之。引導塊中的程式将裝在該分區中的作業系統。

一種可能的檔案系統布局：

• 超級塊（superblock）：包含檔案系統的所有關鍵參數。
• 空閑空間管理：空閑塊的資訊，可以用位圖或指針表形式給出。
• i節點：資料結構數組，每個檔案一個，說明檔案的方方面面。
• 根目錄：目錄樹的根部。
• 目錄和檔案：存放其他所有目錄和檔案

檔案的實作

• 連續配置設定：把每個檔案作為一連串連續資料塊存儲在磁盤上。易産生零碎空間。
• 連結清單配置設定：為每個檔案構造磁盤塊連結清單。随機存取緩慢。指針占去了一些空間。
• 在記憶體中采用表的連結清單配置設定：取出每個磁盤塊的指針字，把它放在記憶體的一個表中。稱為檔案配置設定表（File Allocation Table，FAT）。對于大磁盤而言占用記憶體太多。
• i節點：給每個檔案賦予一個稱為i節點（index-node）的資料結構，其中列出了檔案屬性和檔案塊的磁盤位址。

目錄的實作

1. 目錄中有一個固定大小的目錄項清單，每個檔案對應一項，其中包含一個檔案名、一個檔案屬性結構以及泳衣說明磁盤塊位置的一個或多個磁盤位址。
2. 采用i節點的系統，把檔案屬性存放在i節點中，目錄項更短：隻有檔案名和i節點号。

兩種處理目錄項中長檔案名的方式：

共享檔案

1. 磁盤塊不列入目錄中，而是列入一個與問價本身關聯的小型資料結構（i節點中）中。目錄将指向這個小型資料結構。
2. 建立一個類型為link的新檔案，使其與另一個檔案存在連接配接。新檔案中指包含了它所連接配接的檔案的路徑名。稱為符号連接配接（symbolic linking）。

日志檔案系統

基本思想是将整個磁盤結構化為一個日志。每隔一段時間，或是有特殊需要時，被緩沖在記憶體中的所有未決的血操作都被放到一個單獨的段中，作為在日志末尾的一個鄰接段寫入磁盤。

儲存一個用于記錄系統下一步将要做什麼的日志。這樣當系統在完成它們即将完成的任務錢崩潰時，重新啟動之後，可以通過檢視日志，擷取崩潰前計劃完成的任務，并完成它們。這樣的檔案系統稱為日志檔案系統。

為了增加可信性，一個檔案系統可以引入資料庫中原子事務（atomic transaction）的概念。

虛拟檔案系統

大多數UNIX作業系統都使用虛拟檔案系統概念嘗試将多種檔案系統統一成一個有序的架構。

關鍵思想解釋抽象出所有檔案系統的共有部分，并且将這部分代碼放在單獨的一層，該層調用底層的實際檔案系統來具體管理資料。

虛拟檔案系統的位置：

檔案系統管理和優化

• 磁盤空間管理
  • 塊大小
  • 記錄空閑塊
  • 磁盤配額
• 檔案系統備份
• 檔案系統的一緻性
• 檔案系統的性能
  • 高速緩存
  • 塊提前讀
  • 減少磁盤臂運動
• 磁盤碎片整理

5、輸入輸出

I/O硬體原理

I/O裝置大緻分為兩類：

• 塊裝置（blocl device）：所有傳輸以一個或多個完整的（連續的）塊為機關。
• 字元裝置（character device）：以字元為機關發送或接受一個字元流。

I/O裝置一般由機械部件和電子部件兩部分組成，電子部件稱作裝置控制器（device controller）或擴充卡（adapter）。

記憶體映射I/O的優點：

1. 對于記憶體映射I/O，裝置控制寄存器隻是記憶體中的變量，在C語言中可以和任何其他變量一樣尋址。
2. 對于記憶體映射I/O，不需要特殊的保護機制來阻止使用者程序執行I/O操作。
3. 對于記憶體映射I/O，可以引用記憶體的每一條指令也可以引用控制寄存器。

I/O軟體原理

在設計I/O軟體時一個關鍵的概念是裝置獨立性（device independence）。

I/O軟體的幾個問題：

• 統一命名：不應該依賴于裝置。
• 錯誤處理：盡可能在接近硬體的層面得到處理。
• 同步和異步傳輸。
• 緩沖：資料離開裝置之後不能直接存放到最終目的地。
• 共享裝置的獨占問題。

I/O的最簡單形式是讓CPU做全部工作，這一方法稱為程式控制I/O。

使CPU在等待列印機變為就緒的同時做某些其他事情的方式就是使用中斷驅動I/O。缺點是中斷發生在每個字元上，浪費時間。

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

I/O軟體層次

I/O軟體通常組織成四個層次：

• 中斷處理程式
• 裝置驅動程式
• 與裝置無關的I/O軟體
• 使用者空間的I/O軟體

盤

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

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

1. 尋道時間（将磁盤臂移動到适當的柱面上所需的時間）
2. 旋轉時間（等待适當扇區旋轉到磁頭下所需的時間）
3. 實際資料傳輸時間。

時鐘

• 時鐘硬體：晶體振蕩器、計數器和存儲寄存器。
• 時鐘軟體
• 軟定時器

使用者界面：鍵盤、滑鼠和顯示器

• 輸入軟體
  • 鍵盤軟體
  • 滑鼠軟體
• 輸出軟體
  • 文本視窗
  • X視窗系統
  • 圖形使用者界面
  • 位圖
  • 字型

6、死鎖

資源

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

• 可搶占資源。可以從擁有它的程序中搶占而不會産生任何副作用，例如存儲器。
• 不可搶占資源。在不引起相關的計算失敗的情況下，無法把它從占有它的程序處搶占過來。

死鎖概述

死鎖的規範定義：如果一個程序集合中的每個程序都在等待隻能由該程序集合中的其他程序才能引發的事件，那麼，該程序集合就是死鎖的。

資源死鎖的4個條件：

1. 互斥條件。
2. 占有和等待條件。
3. 不可搶占條件。
4. 環路等待條件。

四種處理死鎖的政策：

1. 忽略該問題。
2. 檢測死鎖并恢複。
3. 仔細對資源進行配置設定，動态的避免死鎖。
4. 通過破壞引起死鎖的四個必要條件之一，防止死鎖的産生。

鴕鳥算法

鴕鳥算法：把頭埋到沙子裡，假裝根本沒有問題發生。

死鎖檢測和死鎖恢複

• 每種類型一個資源的死鎖檢測。檢測是否存在有向圖環路。
• 每種類型多個資源的死鎖檢測。基于矩陣的算法。
• 從死鎖中恢複
  • 利用搶占恢複
  • 利用復原恢複
  • 通過殺死程序恢複

死鎖避免

• 資源軌迹圖
• 安全狀态和不安全狀态
• 單個資源的銀行家算法
• 多個資源的銀行家算法

死鎖預防

• 破環互斥條件
• 破壞占有和等待條件
• 破壞不可搶占條件
• 破壞環路等待條件

其他問題

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

7、多媒體作業系統

多媒體簡介

多媒體的兩個關鍵特征：

1. 多媒體使用極高的資料率。
2. 多媒體要求實時回放。

多媒體檔案

視訊編碼

基于人眼的特性：當一幅圖像閃現在視網膜上時，在它衰退之前将保持幾毫秒時間。如果一個圖像序列以每秒50或更多張圖像閃現，眼界就不會注意到它看到的是不連續的圖像。

為了将二維圖像表示作為時間函數的一維電壓，錄影機用一個電子束對圖像進行橫向掃描并緩慢地向下移動，記錄下電子束經過處光的強度。在掃描的終點處，電子束折回。稱為一幀（frame）。

彩色視訊采用與單色視訊相同的掃描模式，隻不過使用了三個同時運動的電子束來顯示圖像。紅、綠、藍（RGB）三原色。

數字視訊最簡單的表示方法是幀的序列，每一幀由呈矩形栅格的圖像要素即像素（pixel）組成。每個像素RGB三色中的每種顔色用8個二進制位來表示。

音頻編碼

音頻波可以通過模數轉換器（Analog Digital Converter，ADC）轉換成數字形式。ADC以電壓作為輸入，并且生成二進制數作為輸出。

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

電話系統使用的實時脈沖編碼調制（pulse code modulation），脈沖編碼調制以每秒7位或8位對聲音采樣8000次，故這一系統的資料率為56000bps或64000bps。由于每秒隻有8000個樣本，是以4kHz以上的頻率就丢失了。

音頻CD是以每秒44100個樣本的采樣率進行數字化的，足以捕獲高達22050Hz的頻率。

視訊壓縮

所有的壓縮系統都需要兩個算法：一個用于在源端進行資料壓縮，另一個用于在目的端對資料進行解壓縮。分别為編碼算法和解碼算法。

編碼與解碼具有某些不對稱性。視訊信号經過編碼和解碼之後與原始信号存在輕微差異時，系統被稱為是有損的（lossy）。

JPEG标準

用于壓縮連續色調靜止圖像的JPEG（Joint Photographic Experts Group，聯合攝影專家組）。用于壓縮運動圖像的MPEG不過是分别對每一幀進行JPEG編碼，再加上某些幀間壓縮和運動補償等額外的特征。

MPEG标準

MPEG（Motion Picture Experts Group，運作圖像專家組）标準是用于壓縮視訊的主要算法。

MPEG的兩個版本均利用了在電影中存在的兩類備援：空間備援和時間備援。MPEG-2輸出有三種不同的幀組成：

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

音頻壓縮

最流行的是MP3（MPEG音頻層3），屬于MPEG視訊壓縮标準裡的音頻部分。

音頻壓縮可由兩種方法完成。波形編碼技術和感覺編碼。

多媒體程序排程

• 排程同質程序
• 一般實時排程
• 速率單調排程
• 最早最終時優先排程

多媒體檔案系統範型

• VCR控制功能
• 近似視訊點播
• 具有VCR功能的近似視訊點播

檔案存放

多媒體檔案非常龐大、通常隻寫一次而讀許多次，并且傾向于被順序通路。

• 在單個磁盤上存放檔案
• 兩個替代的檔案組織政策
• 近似視訊點播的檔案存放
• 在單個磁盤上存放多個檔案
• 在多個磁盤上存放檔案

高速緩存

• 塊高速緩存
• 檔案高速緩存

多媒體磁盤排程

• 靜态磁盤排程
• 動态磁盤排程

8、多處理機系統

多處理機

共享存儲器多處理機（multiprocessor）是這樣一種計算機系統，其兩個或更多的CPU全部共享通路一個公用的RAM。

• UMA（Uniform Memory Access，統一存儲器通路）
• NUMA（Nonuniform Memory Access，非統一存儲器通路）

多處理機硬體：

• 基于總線的UMA多處理機體系結構
• 使用交叉開關的UMA多處理機
• 使用多級交換的UMA多處理機
• NUMA多處理機
• 多核晶片

多處理機作業系統類型：

• 每個CPU有自己的作業系統
• 主從多處理機
• 對稱多處理機

多處理機排程

• 分時
• 空間共享
• 群排程

多計算機

多處理機硬體

• 互連技術
• 網絡接口

底層通信軟體

使用者層通信軟體

• 發送和接收
• 阻塞調用和非阻塞調用

分布式共享存儲器

• 複制
• 僞共享
• 實作順序一緻性

負載平衡

• 圖論确定算法
• 發送者發起的分布式啟發算法
• 接收者發起的分布式啟發算法

虛拟化

分布式系統

網絡硬體

• 以太網
• 網際網路

網絡服務協定

• 網絡服務
• 網絡協定

基于文檔的中間件

基于檔案系統的中間件

• 傳輸模式
• 目錄層次
• 命名透明性
• 檔案共享的語義

基于對象的中間件

基于協作的中間件

• Linda
• 釋出/訂閱
• Jini

網絡

9、安全

環境安全

• 威脅
  • 計算機系統主要安全目标
    1. 資料機密性
    2. 資料完整性
    3. 資料可用性
    4. 排外性
  • 計算機系統主要安全威脅
    1. 資料暴露
    2. 資料篡改
    3. 拒絕服務
    4. 系統被病毒控制
• 入侵者
  • 入侵者表現形式
    • 被動入侵
    • 主動入侵
  • 入侵者種類
    1. 非專業使用者的随意浏覽
    2. 内部人員的窺視
    3. 為擷取利益而嘗試
    4. 商業或軍事間諜
• 資料意外遺失
  • 天災
  • 軟硬體錯誤
  • 認為過失

密碼學原理

明文與密文之間的關系：

• 私鑰加密技術。對稱加密，安全性取決于對密鑰的管理
• 公鑰加密技術。每個人都有公鑰和私鑰，公開其中的公鑰，用公鑰加密，隻能用對應私鑰解密。
• 單向函數。散列函數
• 數字簽名
• 可信平台子產品（Trusted Platform Modules，TPM）。是一種加密處理器，使用内部的非易失性存儲媒體來儲存密鑰。

保護機制

• 保護域
• 通路控制表
• 權能
• 可信系統
• 可信計算基
• 安全系統的形式化模型
• 多級安全
• 隐蔽信道

認證

• 使用密碼認證
• 使用實際物體的認證方式
• 使用生物識别的驗證方式

内部攻擊

• 邏輯炸彈
• 後門陷阱
• 登入欺騙

利用代碼漏洞

• 緩沖區溢出攻擊
• 格式化字元串攻擊
• 傳回libc攻擊
• 整數溢出攻擊
• 代碼注入攻擊
• 權限提升攻擊

惡意軟體

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

防禦

• 防火牆
• 反病毒和抑制病毒技術
• 代碼簽名
• 囚禁
• 基于模型的入侵檢測
• 封裝移動代碼
• Java安全性