title: Book | Operating System Concepts Part 1
date: 2018-4-2
categories: Book
tags:

• OS
• Design

Part 1 Overview(概述)

第1章 導(dǎo)論

1.1 操作系統(tǒng)做什么

計(jì)算機(jī)系統(tǒng)分為4個(gè)組成部分：計(jì)算機(jī)硬件、操作系統(tǒng)、系統(tǒng)程序與應(yīng)用程序、用戶。

操作系統(tǒng)是一直運(yùn)行在計(jì)算機(jī)上的程序，通常稱為內(nèi)核。

1.2 計(jì)算機(jī)系統(tǒng)組織

當(dāng)打開電源或重啟時(shí)，計(jì)算機(jī)會(huì)運(yùn)行一個(gè)初始化程序。該初始化程序或引導(dǎo)程序(bootstrap program)比較簡(jiǎn)單，通常位于ROM或EEPROM(電可擦可編程只讀存儲(chǔ)器)中，稱為計(jì)算機(jī)硬件中的固件。

事件的發(fā)生通常通過硬件或軟件中斷(interrupt)來(lái)表示，硬件可隨時(shí)通過系統(tǒng)總線向CPU發(fā)出信號(hào)觸發(fā)中斷，軟件通過執(zhí)行特別操作如系統(tǒng)調(diào)用(system call)(也稱為監(jiān)視器調(diào)用(monitor call))來(lái)觸發(fā)中斷。

中斷必須將控制轉(zhuǎn)移到合適的中斷處理程序，處理轉(zhuǎn)移的簡(jiǎn)單方法時(shí)調(diào)用一個(gè)通用子程序以檢查中斷信息。中斷處理子程序的指針表通常位于低地址內(nèi)存，包含了各種設(shè)備的中斷處理子程序的地址。這種地址的數(shù)組或中斷向量(interrupt vector)可通過唯一設(shè)備號(hào)來(lái)索引，以提供設(shè)備的中斷處理子程序的地址。

一個(gè)典型指令執(zhí)行周期(馮諾依曼體系)，首先從內(nèi)存中獲取指令，并保存在指令寄存器(instruction register)中。接著指令被解碼，并可能從內(nèi)存中獲取操作數(shù)或?qū)⒉僮鲾?shù)儲(chǔ)存到內(nèi)部寄存器中。對(duì)操作數(shù)完成執(zhí)行后，其結(jié)果可以存回內(nèi)存中。

輔存(secondary storage)作為內(nèi)存的擴(kuò)充，需要能夠永久地存儲(chǔ)大量的數(shù)據(jù)。

• SCSI(small computer system interface)控制器：小型計(jì)算機(jī)系統(tǒng)接口
• DMA(direct memory access)：直接內(nèi)存訪問

1.3 計(jì)算機(jī)系統(tǒng)體系結(jié)構(gòu)

• 多處理器系統(tǒng)：也稱并行系統(tǒng)(parallel system)或緊耦合系統(tǒng)(tightly coupled system)
• 適度退化(graceful degradation)：提供能與正常工作的硬件成正比的服務(wù)的能力
• 容錯(cuò)(fault tolerant)：系統(tǒng)超出適度退化的能力
• 非對(duì)稱多處理(asymmetric multiprocessing)：每個(gè)處理器都有各自特定的任務(wù)，主從關(guān)系
• 對(duì)稱多處理(symmetric multiprocessing, SMP)：每個(gè)處理器都要完成操作系統(tǒng)中的所有任務(wù)
• 刀片服務(wù)器(blade server)：每個(gè)刀片處理器獨(dú)立啟動(dòng)并運(yùn)行各自的操作系統(tǒng)
• 集群系統(tǒng)(clustered system)：兩個(gè)或多個(gè)獨(dú)立的系統(tǒng)耦合起來(lái)
• 非對(duì)稱集群(asymmetric clustering)：一臺(tái)機(jī)器處于熱備份模式(hot standby mode)，另一臺(tái)運(yùn)行應(yīng)用程序。
• 對(duì)稱集群(symmetric clustering)：主機(jī)都運(yùn)行應(yīng)用程序，互相監(jiān)督

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

多道程序設(shè)計(jì)通過組織作業(yè)使CPU總有一個(gè)作業(yè)可執(zhí)行，從而提高了CPU的利用率。分時(shí)系統(tǒng)(或多任務(wù))是多道程序設(shè)計(jì)的延伸，切換頻率很高。

• 進(jìn)程(process)：裝到內(nèi)存并執(zhí)行的程序
• 作業(yè)調(diào)度(job scheduling)：作業(yè)需要調(diào)入內(nèi)存但沒有足夠的內(nèi)存，系統(tǒng)必須在作業(yè)中做出選擇決策

1.5 操作系統(tǒng)操作

操作系統(tǒng)采取提供硬件支持的方法以允許區(qū)分各種執(zhí)行模式。至少需要兩種獨(dú)立的操作模式：用戶模式(user mode)和監(jiān)督程序模式(monitor mode)(也叫管理模式supervisor mode、系統(tǒng)模式system mode、特權(quán)模式privileged mode)。在計(jì)算機(jī)硬件中添加一個(gè)稱為模式位(mode bit)的位以表示當(dāng)前模式。

一旦出現(xiàn)陷阱或中斷，硬件會(huì)從用戶模式切換到內(nèi)核模式(即將模式位設(shè)為0)。雙重模式操作提供了保護(hù)操作系統(tǒng)和用戶程序不受錯(cuò)誤用戶程序影響的手段，其方法為將能引起損害的機(jī)器指令作為特權(quán)指令(privileged instruction)。

必須確保操作系統(tǒng)能維持對(duì)CPU的控制，也必須防止用戶程序陷入死循環(huán)或不調(diào)用系統(tǒng)服務(wù)，并且不將控制權(quán)返回到操作系統(tǒng)。為了實(shí)現(xiàn)這一目標(biāo)，可使用定時(shí)器(timer)。可變定時(shí)器(variable timer)一般通過一個(gè)固定速率的時(shí)鐘和計(jì)數(shù)器來(lái)實(shí)現(xiàn)。

1.6 進(jìn)程管理

處于執(zhí)行中的程序被稱為進(jìn)程，可以將進(jìn)程視為作業(yè)或分時(shí)程序。程序不是進(jìn)程，程序是被動(dòng)的實(shí)體，進(jìn)程是活動(dòng)的實(shí)體。

進(jìn)程是系統(tǒng)工作的單元。操作系統(tǒng)負(fù)責(zé)下述與進(jìn)程管理相關(guān)的活動(dòng)：

• 創(chuàng)建和刪除用戶進(jìn)程和系統(tǒng)進(jìn)程
• 掛起和重啟進(jìn)程
• 提供進(jìn)程同步機(jī)制
• 提供進(jìn)程通信機(jī)制
• 提供死鎖處理機(jī)制

1.7 內(nèi)存管理

內(nèi)存是現(xiàn)代計(jì)算機(jī)系統(tǒng)操作的中心。內(nèi)存通常是CPU所能直接尋址和訪問的唯一大容量存儲(chǔ)器，硬盤必須先通過CPU生成的I/O調(diào)用傳送到內(nèi)存。

操作系統(tǒng)負(fù)責(zé)下述有關(guān)內(nèi)存管理的活動(dòng)：

• 記錄內(nèi)存哪部分正在被使用及被誰(shuí)使用
• 當(dāng)有內(nèi)存空間時(shí)，決定哪些進(jìn)程可以裝入內(nèi)存
• 根據(jù)需要分配和釋放內(nèi)存空間

1.8 存儲(chǔ)管理

操作系統(tǒng)負(fù)責(zé)下列有關(guān)硬盤管理的活動(dòng)：

• 空閑空間管理
• 存儲(chǔ)空間分配
• 硬盤調(diào)度

三級(jí)存儲(chǔ)(tertiary storage)：CD/DVD驅(qū)動(dòng)器、光盤。

高速緩存一致性(cache coherency)：必須確保在一個(gè)高速緩存中對(duì)A值的更新馬上反映在所有其他A所在的高速緩存中。

I/O子系統(tǒng)包括如下幾個(gè)部分：

• 一個(gè)包括緩沖、高速緩存和假脫機(jī)的內(nèi)存管理部分
• 通用設(shè)備驅(qū)動(dòng)器接口
• 特定硬件設(shè)備的驅(qū)動(dòng)程序

1.9 保護(hù)和安全

絕大多數(shù)操作系統(tǒng)維護(hù)一個(gè)用戶和相關(guān)用戶標(biāo)識(shí)(user ID, UID)的鏈表，在Windows NT中，這稱為安全I(xiàn)D(Secure ID, SID)。用戶有時(shí)需要升級(jí)特權(quán)(escalate privilege)來(lái)獲取對(duì)一個(gè)活動(dòng)的額外特權(quán)。

1.10 分布式系統(tǒng)

分布式系統(tǒng)包括兩種模式的組合，F(xiàn)TP和NFS。

• 局域網(wǎng)：local-area network, LAN
• 廣域網(wǎng)：wide-area network, WAN
• 城域網(wǎng)：metropolitan-area network, MAN
• 小域網(wǎng)：small-area network, SAN，由藍(lán)牙(Blue Tooth)和802.11實(shí)現(xiàn)

1.11 專用系統(tǒng)

• 實(shí)時(shí)嵌入式系統(tǒng)
• 多媒體系統(tǒng)
• 手持系統(tǒng)

1.12 計(jì)算環(huán)境

• 傳統(tǒng)計(jì)算
• 客戶機(jī)-服務(wù)器計(jì)算
• 對(duì)等計(jì)算
• 基于Web的計(jì)算

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

2.1 操作系統(tǒng)服務(wù)

• 用戶界面(user interface, UI)：command-line interface(CLI)、graphical user interface(GUI)
• 程序執(zhí)行：系統(tǒng)必須能將程序裝入內(nèi)存并運(yùn)行
• I/O操作
• 文件系統(tǒng)操作
• 通信：進(jìn)程之間交換信息
• 錯(cuò)誤檢測(cè)
• 資源分配
• 統(tǒng)計(jì)
• 保護(hù)和安全

2.2 操作系統(tǒng)的用戶界面

命令解釋程序的主要作用是獲取并執(zhí)行用戶指定的下一條命令。

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

BOOL WINAPI ReadFile(
  _In_        HANDLE       hFile,
  _Out_       LPVOID       lpBuffer,
  _In_        DWORD        nNumberOfBytesToRead,
  _Out_opt_   LPDWORD      lpNumberOfBytesRead,
  _Inout_opt_ LPOVERLAPPED lpOverlapped
);

Win32函數(shù)CreateProcess()實(shí)際上調(diào)用了Windows內(nèi)核中的NTCreateProcess()系統(tǒng)調(diào)用。

向操作系統(tǒng)傳遞參數(shù)有三種方法：

• 通過寄存器來(lái)傳遞參數(shù)
• 參數(shù)存在內(nèi)存的塊和表中，并將塊的地址通過寄存器來(lái)傳遞(Linux、Solaris)
• 通過程序放在或壓入堆棧中，并通過操作系統(tǒng)彈出

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

系統(tǒng)調(diào)用大致可分成5類：進(jìn)程控制、文件管理、設(shè)備管理、信息維護(hù)、通信。

控制卡是一個(gè)批處理系統(tǒng)概念，它是一個(gè)管理進(jìn)程執(zhí)行的命令。如果程序非正常終止，它可能需要定義一個(gè)錯(cuò)誤級(jí)別。

Solaris 10操作系統(tǒng)包含了dtrace動(dòng)態(tài)跟蹤工具，可以動(dòng)態(tài)探測(cè)運(yùn)行的系統(tǒng)。

通信有兩種模型：消息傳遞模型(message-passing model)、共享內(nèi)存模型(shared-memory model)。

2.5 系統(tǒng)程序

• 文件管理
• 狀態(tài)信息：日期、可用內(nèi)存等等
• 文件修改
• 程序語(yǔ)言支持
• 程序裝入和執(zhí)行
• 通信

2.6 操作系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)

設(shè)計(jì)目標(biāo)：用戶目標(biāo)和系統(tǒng)目標(biāo)

策略(policy)和機(jī)制(mechanism)是重要原理，機(jī)制決定如何做，策略決定做什么。

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

內(nèi)核和系統(tǒng)程序獨(dú)立組成，內(nèi)核進(jìn)一步分成一系列接口和驅(qū)動(dòng)程序。

系統(tǒng)模塊化可用分層法，即操作系統(tǒng)分成若干層，最底層是硬件，最高層是用戶接口。

Mach操作系統(tǒng)采用了微內(nèi)核(microkernel)技術(shù)來(lái)模塊化內(nèi)核，這種方法將所有非基本部分從內(nèi)核中移走，并將它們實(shí)現(xiàn)為系統(tǒng)程序或用戶程序。

2.8 虛擬機(jī)

虛擬機(jī)本身只能運(yùn)行在用戶模式，所以要模擬出虛擬用戶模式和虛擬內(nèi)核模式。

• VMware
• Java JVM
• .NET CLR

2.9 系統(tǒng)生成

對(duì)于某個(gè)特定的計(jì)算機(jī)場(chǎng)所，必須要配置和生成系統(tǒng)，這一過程有時(shí)稱為系統(tǒng)生成(system generation, SYSGEN)。

2.10 系統(tǒng)啟動(dòng)

引導(dǎo)程序(引導(dǎo)裝載程序)能定位內(nèi)核，將它裝入內(nèi)存，開始執(zhí)行。

第3章 進(jìn)程

3.1 進(jìn)程概念

進(jìn)程包括程序代碼(文本段)、當(dāng)前活動(dòng)(通過程序計(jì)數(shù)器的值和寄存器的內(nèi)容來(lái)表示)、進(jìn)程堆棧段、數(shù)據(jù)段、堆。

程序是被動(dòng)實(shí)體，進(jìn)程是活動(dòng)實(shí)體。

每個(gè)進(jìn)程在操作系統(tǒng)內(nèi)用進(jìn)程控制塊(process control block, PCB, 也叫任務(wù)控制塊)來(lái)表示：

• 進(jìn)程狀態(tài)
• 程序計(jì)數(shù)器
• CPU寄存器
• CPU調(diào)度信息：包括進(jìn)程優(yōu)先級(jí)、調(diào)度隊(duì)列的指針和其他調(diào)度參數(shù)
• 內(nèi)存管理信息：基址、界限寄存器的值、頁(yè)表或段表
• 記賬信息：CPU時(shí)間、實(shí)際使用時(shí)間、時(shí)間界限、記賬數(shù)據(jù)、作業(yè)或進(jìn)程數(shù)量
• I/O狀態(tài)信息：分配給進(jìn)程的I/O設(shè)備列表、打開的文件列表

3.2 進(jìn)程調(diào)度

多道程序設(shè)計(jì)中，進(jìn)程調(diào)度選擇一個(gè)可用的進(jìn)程到CPU上執(zhí)行。

就緒隊(duì)列通常用鏈表來(lái)實(shí)現(xiàn)，其頭節(jié)點(diǎn)指向鏈表的第一個(gè)和最后一個(gè)PCB塊的指針，每個(gè)PCB包含一個(gè)指向就緒隊(duì)列的下一個(gè)PCB的指針域。

// Linux的進(jìn)程控制塊
struct task_struct {
  pid_t pid; /* process identifier */
  long state; /* state of the process */
  unsigned int time_slice; /* scheduling information */
  struct files_struct* files; /* list of open files */
  struct mm_struct* mm; /* address space of this process */
};

等待特定I/O設(shè)備的進(jìn)程列表稱為設(shè)備隊(duì)列。

進(jìn)程分配到CPU執(zhí)行時(shí)，發(fā)生下面的事件之一：

• 進(jìn)程可能發(fā)出一個(gè)I/O請(qǐng)求，并被放到I/O隊(duì)列中
• 進(jìn)程可能創(chuàng)建一個(gè)新的子進(jìn)程，并等待其結(jié)束
• 進(jìn)程可能會(huì)由于中斷而強(qiáng)制釋放CPU，并被放回到就緒隊(duì)列中

進(jìn)程選擇是由相應(yīng)的調(diào)度程序(scheduler)來(lái)執(zhí)行的：長(zhǎng)期調(diào)度程序(long-term scheduler)或作業(yè)調(diào)度程序(job scheduler)從緩沖池中選擇進(jìn)程，并裝入內(nèi)存以準(zhǔn)備執(zhí)行。短期調(diào)度程序(short-term scheduler)或CPU調(diào)度程序從準(zhǔn)備執(zhí)行的進(jìn)程中選擇進(jìn)程，并為之分配CPU。兩者的主要區(qū)別在于它們的執(zhí)行頻率。

有的系統(tǒng)沒有長(zhǎng)期調(diào)度程序，UNIX和Windows的分時(shí)系統(tǒng)只是簡(jiǎn)單地將所有新進(jìn)程放在內(nèi)存中以供短期調(diào)度程序使用。這些系統(tǒng)地穩(wěn)定性依賴于物理限制(如可用的終端數(shù))或用戶的自我調(diào)整。

有的系統(tǒng)如分時(shí)系統(tǒng)引入了中期調(diào)度程序(medium-term scheduler)，其核心思想是能將進(jìn)程從內(nèi)存或CPU競(jìng)爭(zhēng)中移出，從而降低多道程序設(shè)計(jì)的程度。進(jìn)程能被重新調(diào)入內(nèi)存，并從中斷處繼續(xù)執(zhí)行，這種方案叫做交換(swapping)。

上下文切換(context switch)：將CPU切換到另一個(gè)進(jìn)程需要保存當(dāng)前進(jìn)程的狀態(tài)并恢復(fù)另一個(gè)進(jìn)程的狀態(tài)。

3.3 進(jìn)程操作

進(jìn)程能通過創(chuàng)建進(jìn)程系統(tǒng)調(diào)用(create-process system call)創(chuàng)建多個(gè)新進(jìn)程，從而形成進(jìn)程樹。大多數(shù)操作系統(tǒng)根據(jù)一個(gè)唯一的進(jìn)程標(biāo)識(shí)符(process identifier, pid)來(lái)識(shí)別進(jìn)程，pid通常是一個(gè)整數(shù)值。

在Solaris系統(tǒng)里面，樹頂端的進(jìn)程是標(biāo)識(shí)符為0的Sched進(jìn)程。Sched進(jìn)程生成幾個(gè)子進(jìn)程，包括pageout和fsflush，分別負(fù)責(zé)內(nèi)存管理和文件系統(tǒng)。Sched進(jìn)程還生成init進(jìn)程，作為所有用戶進(jìn)程的根進(jìn)程。

命令ps -el可以列出系統(tǒng)所有當(dāng)前活動(dòng)進(jìn)程的完整信息。

#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>

int main(void) {
    pid_t pid = fork();
    if (pid < 0) {
        fprintf(stderr, "Fork Failed\n");
        exit(-1);
    } else if (pid == 0) {
        // child process
        execlp("/bin/ls", "ls", NULL);
    } else {
        // parent will wait for the child to complete
        wait(NULL);
        printf("Child Complete");
        exit(0);
    }
}

#include <windows.h>
#include <stdio.h>

int main(void) {
    STARTUPINFO si;
    PROCESS_INFORMATION pi;

    // allocate memory
    ZeroMemory(&si, sizeof(si));
    si.cb = sizeof(si);
    ZeroMemory(&pi, sizeof(pi));

    // create child process
    if (!CreateProcess(NULL, 
        "C:\\Windows\\system32\\mspaint.exe",
        NULL,
        NULL,
        FALSE,
        0,
        NULL,
        NULL,
        &si,
        &pi)) {
        fprintf(stderr, "Create Process Failed");
        return -1;
    }
    WaitForSingleObject(pi.hProcess, INFINITE);
    printf("Child Complete");

    // close handles
    CloseHandle(pi.hProcess);
    CloseHandle(pi.hThread);
}

進(jìn)程可以通過適當(dāng)?shù)南到y(tǒng)調(diào)用來(lái)終止另一個(gè)進(jìn)程，比如Win32的TerminateProcess()，但是只有被終止進(jìn)程的父進(jìn)程才能執(zhí)行這以系統(tǒng)調(diào)用。

級(jí)聯(lián)終止(cascading termination)：父進(jìn)程已終止的情況下，某些系統(tǒng)不允許子進(jìn)程再存在，子進(jìn)程的終止由操作系統(tǒng)進(jìn)行。

3.4 進(jìn)程間通信

操作系統(tǒng)內(nèi)并發(fā)執(zhí)行的進(jìn)程可以是獨(dú)立進(jìn)程或協(xié)作進(jìn)程。獨(dú)立進(jìn)程不能影響其他進(jìn)程或被其他進(jìn)程所影響，協(xié)作進(jìn)程能影響其他進(jìn)程或被其他進(jìn)程影響。

使用進(jìn)程協(xié)作的理由：

• 信息共享
• 提高運(yùn)算速度，子任務(wù)
• 模塊化
• 方便

協(xié)作進(jìn)程需要一種進(jìn)程間通信機(jī)制(inter process communication, IPC)來(lái)允許進(jìn)程相互交換數(shù)據(jù)與信息。通信基本模式：共享內(nèi)存、消息傳遞。

緩沖：無(wú)限緩沖(unbounded-buffer)、有限緩沖(bounded-buffer)。

通信需要通信線路(communication link)，該線路有多種實(shí)現(xiàn)方法：

• 直接或間接通信
• 同步或異步通信
• 自動(dòng)或顯式緩沖

直接通信：send(P, message)、receive(Q, message)。

間接通信：send(A, message)、receive(A, message)。

同步異步通信：阻塞send、非阻塞send和阻塞receive、非阻塞receive組合。

緩沖：零容量(阻塞send)、有限容量、無(wú)限容量。

3.5 IPC系統(tǒng)的實(shí)例

POSIX共享內(nèi)存：

進(jìn)程必須首先用系統(tǒng)調(diào)用shmget()創(chuàng)建共享內(nèi)存段，想訪問共享內(nèi)存段的進(jìn)程必須采用shmat()系統(tǒng)調(diào)用來(lái)將其加入地址空間，然后使用shmat()返回的指針來(lái)訪問共享內(nèi)存。當(dāng)進(jìn)程不再需要訪問共享內(nèi)存段時(shí)，將指針傳遞給系統(tǒng)調(diào)用shmdt()分離共享內(nèi)存段。shmctl()用于刪除共享內(nèi)存段。

Mach：

• msg_send()：向郵箱發(fā)送消息
• msg_receive()：接收消息
• msg_rpc()：遠(yuǎn)程過程調(diào)用(RPC)，能發(fā)送消息并只等待來(lái)自發(fā)送者的一個(gè)返回信息
• port_allocate()：創(chuàng)建新郵箱并為其消息隊(duì)列分配空間

Windows XP：

Windows XP的消息傳遞工具稱為本地過程調(diào)用(LPC)工具。端口消息傳遞最多能發(fā)送256B消息，更大的消息需要通過區(qū)段對(duì)象(構(gòu)建共享內(nèi)存)來(lái)傳遞消息。

Windows XP的LPC工具并不是Win32 API的一部分，應(yīng)用程序應(yīng)該使用Win32 API調(diào)用標(biāo)準(zhǔn)用的遠(yuǎn)程過程調(diào)用。

3.6 客戶機(jī)-服務(wù)器系統(tǒng)通信

• Socket：服務(wù)器監(jiān)聽指定端口，客戶端發(fā)送Socket連接。
• 遠(yuǎn)程過程調(diào)用(RPC)：RPC語(yǔ)義允許客戶機(jī)調(diào)用位于遠(yuǎn)程主機(jī)上的過程，需要定義數(shù)據(jù)的機(jī)器無(wú)關(guān)表示
• 遠(yuǎn)程方法調(diào)用(RMI)：類似RPC的Java特性，遠(yuǎn)程指JVM不同，基于對(duì)象

第4章 線程

4.1 概述

線程是CPU使用的基本單元，它由線程ID、程序計(jì)數(shù)器、寄存器集合和棧組成。它與屬于同一進(jìn)程的其他線程共享代碼段、數(shù)據(jù)段和其他操作系統(tǒng)資源。

多線程編程有下列優(yōu)點(diǎn)：

• 響應(yīng)度高，即使有阻塞和執(zhí)行較冗長(zhǎng)的操作，程序仍能繼續(xù)執(zhí)行
• 資源共享
• 經(jīng)濟(jì)，不用執(zhí)行創(chuàng)建進(jìn)程所需要的內(nèi)存和資源的分配工作
• 多處理器體系結(jié)構(gòu)的利用，加強(qiáng)并發(fā)功能

4.2 多線程模型

有兩種不同方法來(lái)提供線程支持：用戶層的用戶線程、內(nèi)核層的內(nèi)核線程。用戶線程受內(nèi)核支持，而無(wú)需內(nèi)核管理；而內(nèi)核線程由操作系統(tǒng)直接支持和管理。

多對(duì)一模型將許多用戶級(jí)線程映射到一個(gè)內(nèi)核線程。線程管理是由線程庫(kù)在用戶空間進(jìn)行的，因而效率比較高。但如果一個(gè)線程執(zhí)行了阻塞系統(tǒng)調(diào)用，那么整個(gè)進(jìn)程會(huì)阻塞。因?yàn)槿我粫r(shí)刻只有一個(gè)線程能訪問內(nèi)核，多個(gè)線程不能并行運(yùn)行在多處理器上。Green thread(Solaris所應(yīng)用的線程庫(kù))和GNU可移植線程(GNU Portable Threads)就是使用了這種模型。

一對(duì)一模型將每個(gè)用戶線程映射到一個(gè)內(nèi)核線程。缺點(diǎn)是每創(chuàng)建一個(gè)用戶線程就需要?jiǎng)?chuàng)建一個(gè)相應(yīng)的內(nèi)核線程。Linux和Windows使用一對(duì)一模型。

多對(duì)多模型多路復(fù)用了許多用戶線程到同樣數(shù)量或更小數(shù)量的內(nèi)核線程上。多對(duì)多模型沒有兩者的缺點(diǎn)：開發(fā)人員可以創(chuàng)建任意多的用戶線程，并且相應(yīng)內(nèi)核線程能在多處理器系統(tǒng)上并發(fā)執(zhí)行。IRIX、HP-UX、Tru64 UNIX等操作系統(tǒng)支持多對(duì)多模型，Solaris 9之前支持二級(jí)模型，之后開始使用一對(duì)一模型。

4.3 線程庫(kù)

線程庫(kù)(thread library)為程序員提供創(chuàng)建和管理線程的API，有兩種方法實(shí)現(xiàn)線程庫(kù)：

• 在用戶空間中提供一個(gè)沒有內(nèi)核支持的庫(kù)，庫(kù)的代碼和數(shù)據(jù)結(jié)構(gòu)都存在用戶空間中。
• 執(zhí)行一個(gè)由操作系統(tǒng)直接支持的內(nèi)核級(jí)的庫(kù)，庫(kù)的代碼和數(shù)據(jù)結(jié)構(gòu)都存在內(nèi)核空間中。

目前常用的三種線程庫(kù)：

• POSIX Pthread：作為POSIX標(biāo)準(zhǔn)的擴(kuò)展，可以提供用戶級(jí)或內(nèi)核級(jí)的庫(kù)。
• Win32：適用于Windows的內(nèi)核級(jí)線程庫(kù)。
• Java：線程API允許線程在Java程序中直接創(chuàng)建和管理，通常采用宿主系統(tǒng)上的線程庫(kù)來(lái)實(shí)現(xiàn)。

Pthread是由POSIX標(biāo)準(zhǔn)(IEEE 1003.1c)為線程創(chuàng)建和同步定義的API，這是線程行為的規(guī)范，而不是實(shí)現(xiàn)。

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

int sum;
void* runner(void* param);

int main(int argv, char* args[]) {
    pthread_t tid;
    pthread_attr_t attr;
    if (argv != 2) {
        fprintf(stderr, "usage: ./a.out <integer value>\n");
        return -1;
    }
    if (atoi(args[1]) < 0) {
        fprintf(stderr, "%d must be >= 0\n", atoi(args[1]));
        return -1;
    }
    pthread_attr_init(&attr);
    pthread_create(&tid, &attr, runner, args[1]);
    pthread_join(tid, NULL);
    printf("sum = %d\n", sum);
}

void* runner(void* param) {
    int upper = atoi(param);
    sum = 0;
    for (int i = 1; i <= upper; i++) {
        sum += i;
    }
    pthread_exit(0);
}

Windows32線程庫(kù)創(chuàng)建線程的技術(shù)與Pthread很相似。

#include <windows.h>
#include <stdio.h>
#include <stdlib.h>

DWORD sum;
DWORD WINAPI Summation(LPVOID param);

int main(int argv, char* args[]) {
    DWORD threadId;
    HANDLE threadHandle;
    int param;
    if (argv != 2) {
        fprintf(stderr, "usage: ./a.exe <integer value>\n");
        return -1;
    }
    param = atoi(args[1]);
    if (param < 0) {
        fprintf(stderr, "%d must be >= 0\n", atoi(args[1]));
        return -1;
    }
    threadHandle = CreateThread(NULL, 0, Summation, &param, 0, &threadId);
    if (threadHandle != NULL) {
        WaitForSingleObject(threadHandle, INFINITE);
        CloseHandle(threadHandle);
        printf("sum = %d\n", sum);
    }
}

DWORD WINAPI Summation(LPVOID param) {
    DWORD upper = *(DWORD*) param;
    for (DWORD i = 1; i <= upper; i++) {
        sum += i;
    }
    return 0;
}

Java程序中有兩種創(chuàng)建線程的技術(shù)：一種是創(chuàng)建一個(gè)新的類，它從Thread類派生，并重寫其run()；另一種方法是定義一個(gè)實(shí)現(xiàn)Runnable接口的類。

public final class JavaThread {
    private JavaThread() {
        // Do nothing
    }

    public static void main(String[] args) {
        if (args.length > 0) {
            int upper = Integer.parseInt(args[0]);
            if (upper < 0) {
                System.err.println(args[0] + " must be >= 0");
            } else {
                Sum sum = new Sum();
                Thread thrd = new Thread(new Summation(upper, sum));
                thrd.start();
                try {
                    thrd.join();
                    System.out.println("sum = " + sum.getSum());
                } catch (InterruptedException ie) {
                    System.err.println(ie.toString());
                }
            }
        } else {
            System.err.println("usage: java JavaThread <integer value>");
        }
    }
}

final class Sum {
    private int sum;

    public int getSum() {
        return sum;
    }

    public void setSum(int value) {
        this.sum = value;
    }
}

final class Summation implements Runnable {
    private int upper;
    private Sum sumValue;

    public Summation(int upper, Sum sumValue) {
        this.upper = upper;
        this.sumValue = sumValue;
    }

    public void run() {
        int sum = 0;
        for (int i = 1; i <= upper; i++) {
            sum += i;
        }
        sumValue.setSum(sum);
    }
}

4.4 多線程問題

有的UNIX系統(tǒng)有兩種形式的fork()，一種復(fù)制所有的線程，另一種只復(fù)制調(diào)用了系統(tǒng)調(diào)用fork()的線程。如果一個(gè)線程調(diào)用了系統(tǒng)調(diào)用exec()，那么exec()參數(shù)所指定的程序會(huì)替換整個(gè)進(jìn)程，包括所有線程。

線程取消(thread cancellation)是在線程完成之前來(lái)終止線程的任務(wù)。要取消的線程通常稱為目標(biāo)線程，目標(biāo)線程的取消可在如下兩種情況下發(fā)生:

1. 異步取消(asynchronous cancellation)：一個(gè)線程立即終止目標(biāo)線程。
2. 延遲取消(deferred cancellation)：目標(biāo)線程不斷地檢查它是否應(yīng)終止，這允許目標(biāo)線程有機(jī)會(huì)以有序方式來(lái)終止自己。

異步取消線程并不會(huì)使所需的系統(tǒng)資源空閑，相反采用延遲取消時(shí)，需要一個(gè)線程檢查一個(gè)標(biāo)志以確定它是否應(yīng)該取消。Pthread稱這些點(diǎn)為取消點(diǎn)(cancellation point)。

信號(hào)在UNIX中用來(lái)通知進(jìn)程某個(gè)特定事件已發(fā)生了，可以同步或異步接收。每個(gè)信號(hào)都有一個(gè)默認(rèn)信號(hào)處理程序(default signal handler)，當(dāng)處理信號(hào)時(shí)在內(nèi)核中運(yùn)行。

單線程程序的信號(hào)總是發(fā)給進(jìn)程，多線程程序中，同步信號(hào)需要發(fā)送到產(chǎn)生這一信號(hào)的線程，而異步信號(hào)情況就不是那么清楚了。有些異步信號(hào)如終止進(jìn)程信號(hào)(Ctrl+C)應(yīng)該發(fā)送給所有線程。

UNIX信號(hào)發(fā)送：

• kill(pid_t pid, int signal)：標(biāo)準(zhǔn)的發(fā)送信號(hào)的UNIX函數(shù)
• pthread_kill(pthread_t tid, int signal)：POSIX Pthread提供的函數(shù)，允許發(fā)送到指定線程

Windows不明確提供對(duì)信號(hào)的支持，但是能通過異步過程調(diào)用(asynchronous procedure call, APC)來(lái)模擬。APC只發(fā)送特定線程而不是進(jìn)程。

線程池(thread pool)的主要思想是在進(jìn)程開始時(shí)創(chuàng)建一定數(shù)量的線程，并放入到池中以等待工作。當(dāng)服務(wù)器收到請(qǐng)求時(shí)，它會(huì)喚醒池中的一個(gè)線程(如果有可以用的線程)，并將要處理的請(qǐng)求傳遞給它。

線程池的優(yōu)點(diǎn)：

• 通常用現(xiàn)有線程處理請(qǐng)求要比等待創(chuàng)建新的線程要快。
• 線程池限制了在任何時(shí)候可用線程的數(shù)量。

許多實(shí)現(xiàn)多對(duì)多模型或二級(jí)模型的系統(tǒng)在用戶和內(nèi)核線程之間設(shè)置一種中間數(shù)據(jù)結(jié)構(gòu)，通常是輕量級(jí)進(jìn)程(LWP)。對(duì)于用戶線程庫(kù)，LWP表現(xiàn)為一種應(yīng)用程序可以調(diào)度用戶線程來(lái)允許的虛擬處理器，每個(gè)LWP與內(nèi)核線程相連。

一種解決用戶線程庫(kù)與內(nèi)核間通信的方法被稱為調(diào)度器激活(scheduler activation)。內(nèi)核提供一組虛擬處理器(LWP)給應(yīng)用程序，應(yīng)用程序課調(diào)度用戶線程到一個(gè)可用的虛擬處理器上。進(jìn)一步說(shuō)，內(nèi)核必須告知與應(yīng)用程序有關(guān)的特定事件，這個(gè)過程被稱為upcall。

4.5 操作系統(tǒng)實(shí)例

• Windows XP線程：提供了fiber庫(kù)的支持，該庫(kù)提供了多對(duì)多模型的功能。
• Linux線程：傳統(tǒng)進(jìn)程復(fù)制fork()、創(chuàng)建線程clone()，Linux不區(qū)分進(jìn)程和線程，通常稱之為任務(wù)。

第5章 CPU調(diào)度

5.1 基本概念

CPU的成功調(diào)用依賴于進(jìn)程的如下屬性：進(jìn)程執(zhí)行由CPU執(zhí)行和I/O等待周期組成。

每當(dāng)CPU空閑時(shí)，操作系統(tǒng)就必須從就緒隊(duì)列中選擇一個(gè)進(jìn)程來(lái)執(zhí)行。進(jìn)程選擇由短期調(diào)度程序(short-term scheduler)或CPU調(diào)度程序執(zhí)行。就緒隊(duì)列不必是先進(jìn)先出(FIFO)隊(duì)列。

CPU調(diào)度決策在4種環(huán)境下發(fā)生：

• 當(dāng)一個(gè)進(jìn)程從運(yùn)行狀態(tài)切換到等待狀態(tài)(如I/O請(qǐng)求)
• 當(dāng)一個(gè)進(jìn)程從運(yùn)行狀態(tài)切換到就緒狀態(tài)(如中斷發(fā)生)
• 當(dāng)一個(gè)進(jìn)程從等待狀態(tài)切換到就緒狀態(tài)(如I/O完成)
• 當(dāng)一個(gè)進(jìn)程終止時(shí)

1、4兩種情況沒有選擇只有調(diào)度，稱調(diào)度方案是非搶占的(non-preemptive)或協(xié)作的(co-operative)。2、3兩種情況可以選擇，稱調(diào)度方案是搶占的(preemptive)。

搶占調(diào)度對(duì)訪問共享數(shù)據(jù)是有代價(jià)的，對(duì)內(nèi)核的設(shè)計(jì)也有影響。

與CPU調(diào)度功能有關(guān)的另一個(gè)部分是分派程序(dispatcher)。分派程序是一個(gè)模塊，用來(lái)將CPU的控制交給由短期調(diào)度程序選擇的進(jìn)程。功能：

• 切換上下文
• 切換到用戶模式
• 跳轉(zhuǎn)到用戶程序的合適位置，以重新啟動(dòng)程序

分派程序停止一個(gè)進(jìn)程而啟動(dòng)另一個(gè)所要畫的時(shí)間稱為分派延遲(dispatch latency)。

5.2 調(diào)度準(zhǔn)則

• CPU使用率
• 吞吐量
• 周轉(zhuǎn)時(shí)間
• 等待時(shí)間
• 響應(yīng)時(shí)間

5.3 調(diào)度算法

• 先到先服務(wù)調(diào)度(first-come, first-served(FCFS) scheduling algorithm)

FCFS策略可以用FIFO隊(duì)列來(lái)容易地實(shí)現(xiàn)，但是平均等待時(shí)間通常較長(zhǎng)。(護(hù)航效果convoy effect)

FCFS調(diào)度算法是非搶占的。

• 最短作業(yè)優(yōu)先調(diào)度算法(shortest-job-first(SJF) scheduling algorithm)

SJF策略是最佳的，因?yàn)槠骄却龝r(shí)間最小，但是真正困難是如何知道下一個(gè)CPU區(qū)間的長(zhǎng)度。

SJF調(diào)度經(jīng)常用于長(zhǎng)期調(diào)度。SJF算法可能是搶占的或非搶占的，搶占SJF調(diào)度有時(shí)稱為最短剩余時(shí)間優(yōu)先調(diào)度(shortest-remaining-time-first scheduling)。

• 優(yōu)先級(jí)調(diào)度算法(priority scheduling algorithm)

SJF算法可作為通用優(yōu)先級(jí)調(diào)度算法的一個(gè)特例。每個(gè)進(jìn)程都有一個(gè)優(yōu)先級(jí)與其關(guān)聯(lián)，具有最高優(yōu)先級(jí)的進(jìn)程會(huì)分配到CPU，具有相同優(yōu)先級(jí)的進(jìn)程按FCFS順序調(diào)度。

優(yōu)先調(diào)度可以是搶占的或者非搶占的。優(yōu)先級(jí)調(diào)度算法的一個(gè)主要問題是無(wú)窮阻塞(indefinite blocking)或饑餓(starvation)。低優(yōu)先級(jí)進(jìn)程無(wú)窮等待問題的解決之一是老化(aging)，逐漸增加在系統(tǒng)中等待很長(zhǎng)時(shí)間的進(jìn)程的優(yōu)先級(jí)。

• 輪轉(zhuǎn)法調(diào)度(round-robin, RR)

輪轉(zhuǎn)法調(diào)度算法是專門為分時(shí)系統(tǒng)設(shè)計(jì)的，類似于FCFS調(diào)度，但是增加了搶占以切換進(jìn)程。定義一個(gè)較小時(shí)間單元，稱為時(shí)間片(time quantum, or time slice)，將就緒隊(duì)列作為循環(huán)隊(duì)列，設(shè)置定時(shí)器在一個(gè)時(shí)間片之后中斷。

RR算法的性能很大程度上依賴于時(shí)間片的大小。如果時(shí)間片很小，那么RR算法稱為處理器共享，每個(gè)進(jìn)程對(duì)于用戶都有它自己的處理器。這種方法用在Control Data Corporation(CDC)的硬件上，可以用一組硬件和10組寄存器實(shí)現(xiàn)10個(gè)外設(shè)處理器。

根據(jù)經(jīng)驗(yàn)，80%的CPU區(qū)間應(yīng)該小于時(shí)間片。

• 多級(jí)隊(duì)列調(diào)度(multilevel queue scheduling algorithm)

多級(jí)隊(duì)列調(diào)度算法將就緒隊(duì)列分成多個(gè)獨(dú)立隊(duì)列，根據(jù)進(jìn)程的屬性，如內(nèi)存大小、進(jìn)程優(yōu)先級(jí)、進(jìn)程類型，一個(gè)進(jìn)程被永久地分配到一個(gè)隊(duì)列中。

每個(gè)隊(duì)列有自己的調(diào)度算法，隊(duì)列之間通常采用固定優(yōu)先級(jí)搶占調(diào)度。

• 多級(jí)反饋隊(duì)列調(diào)度(multilevel feedback queue scheduling algorithm)

多級(jí)反饋隊(duì)列調(diào)度算法允許進(jìn)程在隊(duì)列之間移動(dòng)，主要實(shí)現(xiàn)是根據(jù)不同CPU區(qū)間的特點(diǎn)以區(qū)分進(jìn)程。

5.4 多處理器調(diào)度

• 非對(duì)稱多處理(asymmetric multiprocessing)：讓一個(gè)處理器處理所有的調(diào)度決定、I/O處理以及其他系統(tǒng)活動(dòng)。
• 對(duì)稱多處理(symmetric multiprocessing, SMP)：每個(gè)處理器自我調(diào)度。

處理器親和力是指SMP系統(tǒng)試圖避免將進(jìn)程從一個(gè)處理器移至另一個(gè)處理器，而是努力使一個(gè)進(jìn)程在同一個(gè)處理器運(yùn)行。

• 軟親和性(soft affinity)：一個(gè)操作系統(tǒng)具有設(shè)法讓一個(gè)進(jìn)程保持在同一個(gè)處理器上運(yùn)行的策略，但不能做任何保證。
• 硬親和性(hard affinity)：運(yùn)行進(jìn)程指定它不允許移至其他處理器上。

負(fù)載平衡通常有兩種方法：push migration和pull migration。負(fù)載平衡常會(huì)抵消處理器親和性的優(yōu)點(diǎn)。

對(duì)稱多線程(SMT)：提供多個(gè)邏輯處理器，也被稱為超線程技術(shù)(hyperthreading)。

5.5 線程調(diào)度

• 進(jìn)程競(jìng)爭(zhēng)范圍(process-contention scope, PCS)：用戶級(jí)線程
• 系統(tǒng)競(jìng)爭(zhēng)范圍(system-contention scope, SCS)：內(nèi)核線程

#include <pthread.h>
#include <stdio.h>

#define NUM_THREADS 5

void* runner(void* param);

int main(int argv, char* args[]) {
    int scope;
    pthread_t tid[NUM_THREADS];
    pthread_attr_t attr;
    pthread_attr_init(&attr);
    if (pthread_attr_getscope(&attr, &scope) != 0) {
        fprintf(stderr, "Unable to get scheduling scope.\n");
    } else {
        if (scope == PTHREAD_SCOPE_PROCESS) {
            printf("PTHREAD_SCOPE_PROCESS\n");
        } else if (scope == PTHREAD_SCOPE_SYSTEM) {
            printf("PTHREAD_SCOPE_SYSTEM\n");
        } else {
            fprintf(stderr, "Illegel scope value.\n");
        }
        pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
        for (int i = 0; i < NUM_THREADS; i++) {
            pthread_create(&tid[i], &attr, runner, NULL);
        }
        for (int i = 0; i < NUM_THREADS; i++) {
            pthread_join(tid[i], NULL);
        }
    }
}

void* runner(void* param) {
    printf("Hello, world\n");
    pthread_exit(0);
}

5.6 操作系統(tǒng)實(shí)例

• Solaris調(diào)度

Solaris采用基于優(yōu)先級(jí)的線程調(diào)度，根據(jù)優(yōu)先級(jí)不同，有4類調(diào)度：實(shí)時(shí)、系統(tǒng)、分時(shí)、交互。

進(jìn)程默認(rèn)的調(diào)度類型是分時(shí)，分時(shí)調(diào)度方法采用多級(jí)反饋隊(duì)列，動(dòng)態(tài)地調(diào)整優(yōu)先級(jí)和賦予不同長(zhǎng)度地時(shí)間片。Solaris 9引入了兩種新的調(diào)度類型：固定優(yōu)先級(jí)(fixed priority)、公平共享(fair share)。

• Windows XP調(diào)度

Windows XP采用基于優(yōu)先級(jí)的、搶占調(diào)度算法來(lái)調(diào)度線程，調(diào)度程序使用32級(jí)優(yōu)先級(jí)方案以確定線程執(zhí)行的順序。優(yōu)先級(jí)分為兩大類型：可變類型(variable class)包括1~15優(yōu)先級(jí)的線程，實(shí)時(shí)類型(real-time class)包括16~31優(yōu)先級(jí)的線程，優(yōu)先級(jí)0的線程用于內(nèi)存管理。

如果沒有就緒線程，那么調(diào)度程序會(huì)執(zhí)行一個(gè)稱為空閑線程(idle thread)的特別線程。

• Linux調(diào)度

在2.5版本之前，Linux內(nèi)核運(yùn)行傳統(tǒng)的Unix調(diào)度算法，不提供對(duì)SMP系統(tǒng)足夠的支持，以及當(dāng)系統(tǒng)任務(wù)數(shù)量增加時(shí)不能按比例調(diào)整。2.5版本之后，調(diào)度程序被分解，內(nèi)核提供在固定時(shí)間內(nèi)運(yùn)行的調(diào)度算法。

Linux調(diào)度程序是搶占的、基于優(yōu)先級(jí)的算法，具有兩個(gè)獨(dú)立的優(yōu)先級(jí)范圍：從0_{99的**real-time**范圍和從100}140的nice范圍。與Solaris和Windows XP在內(nèi)的其他許多系統(tǒng)的調(diào)度程序不同，Linux給較高的優(yōu)先級(jí)分配較長(zhǎng)的時(shí)間片，給較低的優(yōu)先級(jí)分配較短的時(shí)間片。

5.7 算法評(píng)估

• 分析評(píng)估法(analytic evaluation)：使用給定算法和系統(tǒng)負(fù)荷，產(chǎn)生一個(gè)公式或數(shù)字，以評(píng)估對(duì)于該負(fù)荷算法的性能。
• 確定模型法(deterministic modeling)：采用特殊預(yù)先確定的負(fù)荷，計(jì)算在給定負(fù)荷下每個(gè)算法的性能。

第6章 進(jìn)程同步

6.1 背景

多個(gè)進(jìn)程并發(fā)訪問和操作同一數(shù)據(jù)且執(zhí)行結(jié)果與訪問發(fā)生的特定順序有關(guān)，稱為競(jìng)爭(zhēng)條件(race condition)。為了避免競(jìng)爭(zhēng)條件，需要一定形式的進(jìn)程同步(process synchronization)和協(xié)調(diào)(coordination)。

6.2 臨界區(qū)問題

每個(gè)進(jìn)程有一個(gè)代碼段稱為臨界區(qū)(critical section)，在該區(qū)中進(jìn)程可能改變共同變量、更新一個(gè)表、寫一個(gè)文件等。當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū)，沒有其他進(jìn)程可被允許在臨界區(qū)內(nèi)執(zhí)行，即沒有兩個(gè)進(jìn)程可同時(shí)在臨界區(qū)執(zhí)行。

臨界區(qū)問題(critical-section problem)是設(shè)計(jì)一個(gè)以便進(jìn)程協(xié)作的協(xié)議。每個(gè)進(jìn)程必須請(qǐng)求允許進(jìn)入其臨界區(qū)，實(shí)現(xiàn)請(qǐng)求的代碼段稱為進(jìn)入?yún)^(qū)(entry section)，臨界區(qū)之后有退出區(qū)(exit section)，其他代碼為剩余區(qū)(remainder section)。

臨界區(qū)問題的解答必須滿足如下三項(xiàng)要求：

• 互斥(mutual exclusion)：如果進(jìn)程在其臨界區(qū)內(nèi)執(zhí)行，那么其他進(jìn)程都不能在其臨界區(qū)內(nèi)執(zhí)行。
• 前進(jìn)(progress)：如果沒有進(jìn)程在其臨界區(qū)內(nèi)執(zhí)行且有進(jìn)程需進(jìn)入臨界區(qū)，那么只有那些不再剩余區(qū)內(nèi)執(zhí)行的進(jìn)程可參加選擇，以確定誰(shuí)能下一個(gè)進(jìn)入臨界區(qū)，且這種選擇不能無(wú)限推遲。
• 有限等待(bounded waiting)：從一個(gè)進(jìn)程做出進(jìn)入臨界區(qū)的請(qǐng)求，直到該請(qǐng)求允許為止，其他進(jìn)程允許進(jìn)入其臨界區(qū)的次數(shù)有上限。

處理操作系統(tǒng)內(nèi)的臨界區(qū)問題：

• 搶占內(nèi)核(preemptive kernel)：允許處于內(nèi)核模式的進(jìn)程被搶占，適合實(shí)時(shí)編程，響應(yīng)更快。
• 非搶占內(nèi)核(non-preemptive kernel)：不允許處于內(nèi)核模式的進(jìn)程被搶占，從根本上不會(huì)導(dǎo)致競(jìng)爭(zhēng)條件。

6.3 Peterson算法

Peterson算法適用于兩個(gè)進(jìn)程在臨界區(qū)與剩余區(qū)間交替執(zhí)行。

do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);
    // 臨界區(qū)
    flag[i] = false;
    // 剩余區(qū)
} while (true);

i是執(zhí)行的進(jìn)程，j是另一個(gè)進(jìn)程，ture標(biāo)識(shí)哪個(gè)進(jìn)程可以進(jìn)入其臨界區(qū)，turn、flag是內(nèi)存共享的。

6.4 硬件同步

任何臨界區(qū)問題都需要一個(gè)簡(jiǎn)單工具——鎖。

do {
    // 請(qǐng)求鎖
    // 臨界區(qū)
    // 釋放鎖
    // 剩余區(qū)
} while (true);

許多現(xiàn)代計(jì)算機(jī)系統(tǒng)提供了特殊硬件指令以允許能原子地(不可中斷地)檢查和修改字地內(nèi)容或交換兩個(gè)字的內(nèi)容(作出不可中斷的指令)。

比如指令TestAndSet()的定義：

bool TestAndSet(bool* target) {
    bool rv = *target;
    *target = true;
    return rv;
}

使用TestAndSet()的互斥實(shí)現(xiàn)：

do {
    while (TestAndSet(&lock));
    // critical section
    lock = false;
    // remainder section
} while (true);

6.5 信號(hào)量

信號(hào)量(semaphore)用于解決TestAndSet、Swap使用復(fù)雜的問題。信號(hào)量S是個(gè)整數(shù)變量，除了初始化外，只能通過兩個(gè)標(biāo)準(zhǔn)原子操作wait()和signal()來(lái)訪問，這些操作被稱為P(荷蘭語(yǔ)proberen測(cè)試)和V(荷蘭語(yǔ)verhogen增加)。

wait(S) {
    while (S <= 0);
    S--;
}

signal(S) {
    S++;
}

操作系統(tǒng)區(qū)分計(jì)數(shù)信號(hào)量與二進(jìn)制信號(hào)量，計(jì)數(shù)信號(hào)量的值域不受限制，而二進(jìn)制信號(hào)量只能為0或1。通常稱二進(jìn)制信號(hào)量為互斥鎖，因?yàn)榭梢蕴峁┗コ狻?/p>

這里所定義的信號(hào)量的主要缺點(diǎn)是都要求忙等待(busy waiting)，這種類型的信號(hào)量也稱為自旋鎖(spinlock)。自旋鎖的優(yōu)點(diǎn)是，進(jìn)程在等待鎖時(shí)不進(jìn)行上下文切換。

為了克服忙等待，可以修改信號(hào)量操作，使得進(jìn)程不是忙等而是阻塞自己。這里信號(hào)量定義應(yīng)該為如下結(jié)構(gòu)體：

typedef struct {
    int value;
    struct process* list;
} semaphore;

死鎖(deadlocked)：兩個(gè)或多個(gè)進(jìn)程無(wú)限地等待一個(gè)事件，而該事件只能由這些等待進(jìn)程之一來(lái)產(chǎn)生。

無(wú)限期阻塞(indefinite blocking)：饑餓(starvation)，即進(jìn)程在信號(hào)量?jī)?nèi)無(wú)限期等待。

6.6 經(jīng)典同步問題

• 有限緩沖問題：通常用來(lái)說(shuō)明同步原語(yǔ)地能力。
• 讀者-寫者問題：寫者對(duì)共享數(shù)據(jù)庫(kù)有排他地訪問。
• 哲學(xué)家進(jìn)餐問題：并發(fā)控制、同步問題，死鎖與饑餓的典型例子。

6.7 管程

當(dāng)信號(hào)量不正確地用來(lái)解決臨界區(qū)問題時(shí)，會(huì)很容易地產(chǎn)生各種類型的錯(cuò)誤。為了處理這些類型的錯(cuò)誤，研究者提出高級(jí)的同步構(gòu)造——管程(monitor)類型。

管程類型提供了一組由程序員定義的、在管程內(nèi)互斥的操作。管程類型的表示包括一組變量的聲明(這些變量的值定義了一個(gè)類型實(shí)例的狀態(tài))和對(duì)這些變量操作的子程序和函數(shù)的實(shí)現(xiàn)。管程類型的表示不能直接為各個(gè)進(jìn)程所使用，在管程內(nèi)定義的子程序只能訪問位于管程內(nèi)那些局部聲明的變量和形式參數(shù)。類似地，管程的局部變量只能被局部子程序訪問。

管程結(jié)構(gòu)確保一次只有一個(gè)進(jìn)程能在管程內(nèi)活動(dòng)。對(duì)于特定同步方案，需要定義一些額外的同步機(jī)制，這些可由條件(condition)結(jié)構(gòu)來(lái)提供。

6.8 同步實(shí)例

• Solaris同步

為了控制訪問臨界區(qū)，Solaris提供了適應(yīng)互斥、條件變量、信號(hào)量、讀寫鎖和十字轉(zhuǎn)門。

Java為線程同步提供一個(gè)類似于管程的并行機(jī)制，Java中的每一個(gè)對(duì)象都有一個(gè)單獨(dú)的鎖。當(dāng)方法聲明為synchronized時(shí)，調(diào)用方法要求擁有對(duì)象的鎖。

public class SimpleClass {
    public synchronized void safeMethod() {
        /* ... */
    }
}

SimpleClass sc = new SimpleClass();

調(diào)用sc.safeMethod()要求擁有對(duì)象實(shí)例sc的鎖，如果鎖被其他線程所有，則調(diào)用同步方法的線程阻塞，并被放入對(duì)象鎖的進(jìn)入集合中。

Java提供wait()和notify()方法，類似于管程的wait()、signal()的功能，在java.util.concurrent包中為信號(hào)量、條件變量、互斥鎖還有其他并發(fā)機(jī)制提供API支持。

適應(yīng)互斥(adaptive mutex)保護(hù)對(duì)每個(gè)臨界數(shù)據(jù)項(xiàng)的訪問。在多處理器系統(tǒng)中，適應(yīng)互斥以自旋鎖實(shí)現(xiàn)的標(biāo)準(zhǔn)信號(hào)量而開始，請(qǐng)求鎖的線程可以選擇自旋并等待鎖可用，也可用阻塞進(jìn)入睡眠直到鎖釋放被喚醒。在單處理器系統(tǒng)中，請(qǐng)求鎖的線程總是睡眠而不是自旋，因?yàn)槟骋粫r(shí)刻只有一個(gè)線程可以運(yùn)行。

Solaris使用適應(yīng)互斥方法以保護(hù)那些為較短代碼段所訪問的數(shù)據(jù)，如果代碼較長(zhǎng)，那么自旋等待就極為低效了。

讀寫鎖用于保護(hù)經(jīng)常訪問但通常是只讀訪問的數(shù)據(jù)，在這種情況下，讀寫鎖比信號(hào)量更為有效。因?yàn)槎鄠€(gè)線程可以同時(shí)讀數(shù)據(jù)，而信號(hào)量只允許順序訪問數(shù)據(jù)。讀寫鎖實(shí)現(xiàn)代價(jià)要大，通常只用于很長(zhǎng)的代碼段。

Solaris使用十字轉(zhuǎn)門以安排等待獲取適應(yīng)互斥和讀寫鎖的線程鏈表。十字轉(zhuǎn)門(turnstile)是一個(gè)隊(duì)列結(jié)構(gòu)，包含阻塞在鎖上的線程。Solaris不是將每個(gè)同步對(duì)象與一個(gè)十字轉(zhuǎn)門相關(guān)聯(lián)，而是給每個(gè)內(nèi)核線程一個(gè)十字轉(zhuǎn)門。用于第一個(gè)線程阻塞于同步對(duì)象的十字轉(zhuǎn)門成為對(duì)象本身的十字轉(zhuǎn)門，以后阻塞于該鎖上的線程會(huì)添加到該十字轉(zhuǎn)門上。最終釋放鎖時(shí)，會(huì)從內(nèi)核所維護(hù)的空閑十字轉(zhuǎn)門中獲得一個(gè)新的十字轉(zhuǎn)門。

為了防止優(yōu)先級(jí)倒置，十字轉(zhuǎn)門根據(jù)優(yōu)先級(jí)繼承協(xié)議來(lái)組織。如果較低優(yōu)先級(jí)的線程擁有一個(gè)較高優(yōu)先級(jí)線程鎖阻塞的鎖，那么該低優(yōu)先級(jí)線程會(huì)暫時(shí)繼承較高優(yōu)先級(jí)線程的級(jí)別。在釋放線程之后，線程會(huì)返回到它原來(lái)的優(yōu)先級(jí)。

• Windows XP同步

在單處理器中，Windows XP訪問全局資源時(shí)，會(huì)暫時(shí)屏蔽所有可能訪問該全局資源的中斷處理程序的中斷。在多處理器中，Windows XP采用自旋鎖來(lái)保護(hù)對(duì)全局資源的訪問。與Solaris一樣，內(nèi)核只使用自旋鎖來(lái)保護(hù)較短代碼段。由于效率原因，內(nèi)核會(huì)確保擁有自旋鎖的線程決不會(huì)被搶占。

對(duì)于內(nèi)核外線程的同步，Windows XP提供了調(diào)度對(duì)象(dispatcher object)。采用調(diào)度對(duì)象，線程可根據(jù)多種不同機(jī)制，包括互斥、信號(hào)量、事件和定時(shí)器等來(lái)進(jìn)行同步。

調(diào)度對(duì)象可以處于觸發(fā)狀態(tài)(signal state)或非觸發(fā)狀態(tài)(non-signal state)。觸發(fā)狀態(tài)表示對(duì)象可用且線程在獲取它時(shí)不會(huì)阻塞，非觸發(fā)狀態(tài)表示對(duì)象不可用且當(dāng)線程試圖獲取它時(shí)會(huì)阻塞。

• Linux同步

Linux內(nèi)核提供自旋鎖和信號(hào)量(還有著兩種鎖的讀者-寫者版本)，以進(jìn)行內(nèi)核加鎖。Linux提供兩個(gè)簡(jiǎn)單系統(tǒng)調(diào)用preempt_disable、preempt_enable用來(lái)禁止與允許內(nèi)核搶占。

• Pthread同步

Pthread API為線程同步，提供互斥鎖、條件變量、讀寫鎖。

6.9 原子事務(wù)

數(shù)據(jù)庫(kù)系統(tǒng)關(guān)注于數(shù)據(jù)的存儲(chǔ)和提取及數(shù)據(jù)的一致性。

執(zhí)行單個(gè)邏輯功能的一組指令或操作稱為事務(wù)(transaction)。處理事務(wù)的主要問題是不管出現(xiàn)什么計(jì)算機(jī)系統(tǒng)的可能失敗，都要保證事務(wù)的原子性。

從用戶觀點(diǎn)來(lái)看，事務(wù)只是一系列read操作和write操作，并以commit操作或abort操作終止。已成功完成執(zhí)行的終止事務(wù)稱為提交(committed)；否則，稱為撤銷(aborted)。被中止的事務(wù)所訪問的數(shù)據(jù)狀態(tài)必須回復(fù)到事務(wù)剛剛開始執(zhí)行之前，即這個(gè)事務(wù)已經(jīng)回退(rolled back)。

確保原子性的一種方法是在穩(wěn)定存儲(chǔ)上記錄有關(guān)事務(wù)對(duì)其訪問的數(shù)據(jù)所做各種修改的描述信息，實(shí)現(xiàn)著種形式記錄最為常用的方法是先記日志后操作。

為了避免出錯(cuò)時(shí)搜索整個(gè)日志，引入了檢查點(diǎn)(checkpoint)的概念。系統(tǒng)定期執(zhí)行檢查點(diǎn)，執(zhí)行下列步驟：

1. 將當(dāng)前駐留易失性存儲(chǔ)的所有日志記錄輸出到穩(wěn)定存儲(chǔ)上。
2. 將當(dāng)前駐留易失性存儲(chǔ)的所有修改數(shù)據(jù)輸出到穩(wěn)定存儲(chǔ)上。
3. 在穩(wěn)定存儲(chǔ)上輸出一個(gè)日志記錄<checkpoint>。

事務(wù)的并發(fā)執(zhí)行必須相當(dāng)于這些事務(wù)按任意順序串行執(zhí)行，這一屬性稱為串行化(serializability)。

• 串行化能力
• 加鎖協(xié)議
• 基于時(shí)間戳的協(xié)議