Try   HackMD

作業系統

第一章 - 概說

1.1 - 作業系統做什麼

硬體（CPU、記憶體、I/O）、作業系統、應用程式、使用者

  • 1.1.1 - 使用者觀點
    要把作業系統設計得容易使用。
  • 1.1.2 - 系統觀點
    作業系統是一套控制程式（control program），是資源分配者（resource allocator）。
    • 作業 2 題目（1. a）：
      What are the two main functions of an operating system?
      Please explain each function.
      • resource allocator
        負責分配資源給各 process
      • control program
        監督各 process 的執行，避免出錯或不合法使用，例如除 0 的不合法操作
  • 1.1.3 - 定義作業系統
    又稱核心（kernel），其伴隨著：
    • 系統程式：與作業系統有關，但非核心的一部分。
    • 應用程式：與作業系統無關。

1.2 - 電腦系統組織

  • 1.2.1 - 電腦系統操作
    提及：中斷（interupt）、中斷向量、系統呼叫（system call / monitor call）。
    起始程式（靴帶式程式 / bootstrap program）存於唯讀記憶體（ROM）或電子式可消除程式化唯讀記憶體（EEPROM）。
    開機流程：BIOS → 測試系統裝置的「啟動、辨識、初始化」→ 起始程式（bootstrap） → 初始化系統 → 尋找作業系統核心 → 將核心載入記憶體 → 提供服務（順利開機）。
    • 作業 2 題目（1. b）：
      Describe the procedures / steps required when starting up a computer.
      • When a computer startup, the first step is that the BIOS start working. It includes a power-on self-test that initialize and identify system devices. The second step is the executing of the bootstrap program that initializes all aspects of the system and loads operating system kernel. When two steps are done, the computer starts.
  • 1.2.2 - 儲存體結構
    概述各種記憶體 & 階級。
  • 1.2.3 - I/O 架構
    提及：裝置驅動程式（device driver）、直接記憶存取（direct memory access, DMA）。

1.3 - 電腦系統架構

  • 1.3.1 - 單一處理器系統
  • 1.3.2 - 多處理器系統（平行系統、多核心系統）
    提及：
    • 核心（core）、多核心（multicore）
    • 適度降級（graceful degradation）、容錯（fault tolerant）
    • 對稱多元處理　（symmetric multiprocessing, SMP）
      非對稱多元處理（asymmetric multiprocessing, AMP / ASMP）
    • 一致記憶存取　（uniform memory access, UMA）
      非一致記憶存取（non-uniform memory access, NUMA）
  • 1.3.3 - 叢集式系統（Clustered Systems）
    提及：並行（parallelization）、分散式上鎖管理者（distributed lock manager, DLM）。

1.4 - 作業系統結構

提及：多元程式規劃（multiprogramming）、工作池（job pool）、分時（time sharing）、多工（multitasking）、行程（process）、工作排班（job scheduling）、CPU 排班（CPU scheduling）。

1.5 - 作業系統的操作

提及：中斷驅動式（interrupt driven）作業系統、陷阱（trap）。

  • 1.5.1 - 雙模式運作
    分為：
    • 使用者模式
    • 核心 kernel（管理員 supervisor / 系統 system / 特權 privileged）模式
  • 1.5.2 - 計時器

1.6 - 行程管理

提及：程式計數器（program counter）

在行程管理方面，作業系統必須負責下列的功能：

  • 在 CPU 排班行程和執行緒
  • 使用者和系統行程的產生 & 刪除
  • 行程暫停 & 恢復
  • 提供行程同步的機制
  • 提供行程通信的機制
  • 提供處理死結的機制

1.7 - 主記憶體管理

在記憶體管理方面，作業系統必須負責下列的功能：

  • 記錄正在使用的記憶體部分 & 誰在使用
  • 決定哪些行程 & 資料要移入或移出記憶體空間
  • 在需要時配置和回收記憶體空間

1.8 - 儲存體管理

提及：檔案（file）的概念。

  • 1.8.1 - 檔案系統管理

    在檔案管理方面，作業系統必須負責下列的功能：

    • 建立 & 刪除檔案
    • 建立 & 刪除組織檔案的目錄
    • 做為處利檔案 & 目錄的原始支援
    • 對映檔案到輔助記憶體
    • 備份檔案到穩定（非揮發性）儲存裝置上
  • 1.8.2 - 大量儲存體管理
    提及：第三儲存體（tertiary storage）、ROWM（寫一次，多次讀取）、RW（讀 ─ 寫）。

    在磁碟管理方面，作業系統必須負責下列的功能：

    • 可用空間管理
    • 記憶體配置
    • 磁碟排班
  • 1.8.3 - 快取（caching）
    概述記憶體間快取的對應關係。
  • 1.8.4 - I/O 系統

    I/O 子系統包含：

    • 對於同時周邊作業，提供緩衝、快取、連線的記憶體管理元件
    • 通用裝置驅動程式介面
    • 特定硬體裝置驅動程式

1.9 - 保護與安全

提及：保護、使用者辨識符號（user ID）、安全性識別碼（Security ID, SID）、群組識別符號（group ID）。

1.10 - 核心資料結構

  • 1.10.1 - 串列、堆疊、佇列
  • 1.10.2 - 樹
  • 1.10.3 - 雜湊函數 & 對映
  • 1.10.4 - 位元對映

1.11 - 運算環境

  • 1.11.1 - 傳統運算
  • 1.11.2 - 行動運算（mobile computing）
  • 1.11.3 - 分散系統（web-based computing）
    提及：LAN（local）、WAN（wide）、MAN（metropolitan）、PAN（personal）、網路作業系統（network operating system）。
  • 1.11.4 - 客戶 ─ 伺服器運算
    提及：伺服器系統（server system）、客戶系統（client system）。
    伺服器系統概略可分為：
    • 運算伺服器系統（computer-server system）
    • 檔案伺服器系統（file-server system）
  • 1.11.5 - 對等式運算（peer-to-peer, P2P）
    加入對等網路後，有兩種方式可用以判斷有哪些服務：
    • 集中查詢服務
    • 非集中查詢服務：廣播服務要求 ← 需透過「搜尋協定（discovery protocol）」
  • 1.11.6 - 虛擬化（virtualization）
  • 1.11.7 - 雲端運算（cloud computing）
    • 公用雲（public cloud）
    • 私有雲（private cloud）
    • 混合雲（hybrid cloud）
    • 軟體即服務（software as a service, SaaS）
    • 平台即服務（platform as a service, PaaS）
    • 基礎設施即服務（infrastucture as a service, IaaS）
  • 1.11.8 - 即時嵌入系統
    提及：特殊應用積體電路（ASICs）、即時作業系統（real-time operation system）。

1.12 - 開放原始碼作業系統

  • 1.12.1 - 歷史
  • 1.12.2 - Linux
  • 1.12.3 - BSD Linux（BSD UNIX）
  • 1.12.4 - Solaris
  • 1.12.5 - 開放原始碼做為學習工具

1.13 - 摘要

第二章 - 系統結構

  • 作業 2 題目（2. b）：
    What are some O.S. service(s) / system call(s) that the “Open file” operation need?
    • File-system manipulation 負責檔案管理, I/O operations, ReadFile(), CloseHandle()

2.1 - 作業系統服務

  • 提供對使用者有幫助的功能：
    • 使用者介面：
      • 使用者介面（user interface, UI）
      • 命令行介面（command-line interface, CLI）
      • 批次介面（batch interface）
      • 圖形使用者介面（graphical user interface, GUI）
    • 程式執行
    • I/O 作業
    • 檔案系統的使用
    • 通信：共用記憶體（shared memory）、訊息傳遞（message passing）。
    • 錯誤偵測，Ex：算術溢位（over-flow）、企圖存取記憶體禁區、使用過量 CPU 時間。
  • 確保系統本身能有效運作的功能：
    • 資源分配
    • 記帳（accounting）
    • 保護 & 安全

2.2 - 使用者與作業系統介面

  • 2.2.1 - 命令直譯程式（command interpreter）
    提及：外殼（shells）。
  • 2.2.2 - 圖形使用者介面（graphical user interface, GUI）
  • 2.2.3 - 選擇介面
    提及：系統管理員（system administrator）、超級使用者（power user）、外殼劇本（shell script）。

2.3 - 系統呼叫

提及：應用程式介面（application programming interface, API）、系統呼叫介面（system-call interface）

舉例：複製來源檔的內容到目的檔

2.4 - 系統呼叫的類型

可以概略分成六大類：

  • 行程控制（process control）
  • 檔案的管理（file manipulation）
  • 裝置的管理（device manipulation）
  • 資訊的維護（information maintenance）
  • 通信（communication）
  • 保護（protection）
  • 2.4.1 - 行程控制
    提及：偵錯程式（debugger）、缺陷（bug）、鎖（lock）

  • 2.4.2 - 檔案的管理

  • 2.4.3 - 裝置的管理

  • 2.4.4 - 資訊的維護
    提及：單步（single step）

  • 2.4.5 - 通信
    詳細介紹了訊息傳遞模式（message-passing model）& 共用記憶體模式（shared-memory model）。
    提及：守護行程（daemons）。

  • 2.4.6 - 保護

2.5 - 系統程式（system program），又稱為系統常式（system utility）

提供程式開發 & 執行的便利環境：

  • 檔案管理（File management）
  • 狀態資訊（Status information），提及：登錄檔（registry）
  • 檔案的修改（File modification）
  • 程式語言支持（Programming-language support）
  • 程式的載入 & 執行（Program loading and execution）
  • 通信（Communications）
  • 背景服務

★★★ 系統結構總結圖 ★★★

2.6 - 作業系統的設計和製作

  • 2.6.1 - 設計目標
    需求可以分為兩個基本類型：使用者目的（user goal）、系統目的（system goal）。
  • 2.6.2 - 方法與策略
    原則：「將方法從策略中分離」。
    方法決定「如何做」某些工作、策略決定做「什麼事」。
  • 2.6.3 - 製作
    早期的作業系統是由組合語言寫成的，現今大部分則改用高階語言撰寫。
    高階語言撰寫的優點：撰寫快速、精簡、易理解、易偵錯、易移植。
    高階語言撰寫的缺點：執行速度降低、儲存需求增加。

2.7 - 作業系統結構

將設計完成的整個作業系統分成較小的元件分別製作是比較合理的方法。
本節將討論這些元件是如何連接在一起以構成所謂的核心。

  • 2.7.1 - 簡單結構（simple structure）
    優點：在系統呼叫介面或是核心內的通訊上額外的負擔很小。
    缺點：許多功能結合在同一層次，難以維護又脆弱。

  • 2.7.2 - 分層方法（layer approach）
    層次選定後，每層皆只能使用較低層的功能 & 服務。
    優點：結構清晰、易於除錯。
    缺點：難以明確定義各層次之內容、冗長的系統呼叫。

    • 作業 3 題目（1. a）：
      What is the layered approach and what is its main advantage?
      • 優點：降低設計複雜度、有助於分工、測試除錯維護容易
        1. 採取 Top-Down 方式切割系統功能 / 元件以降低複雜度
        2. 元件 / 模組之間依呼叫關係分層，即上層可以使用下層的功能，但下層不可以使用上層的功能
        3. 使用 Bottom-up 方式進行測試

  • 2.7.3 - 微核心（microkernel）
    優點：系統功能易擴展、核心不需反覆修改。
    缺點：系統功能越多效能越差。

  • 2.7.4 - 模組（modules）
    目前作業系統最好的設計方法是使用可載入的模組核心（loadable kernel module）。
    優點：動態製作並連接服務以避免微核心的缺點、更有彈性、更有效率。

    • 作業 3 題目（1. b）：
      What is the modular kernel approach and what is its main advantage?
      • 優點：類似 layered approach 但是更有彈性且效能更好
        1. 許多 OS 實施可加載的核心模組
        2. 使用物件導向方法
        3. 每個核心元件都是獨立的
        4. 每個核心元件都通過已知介面與其他元件溝通
        5. 每個核心元件都可以根據核心需求來做加載
    • 作業 3 題目（1. c）：
      In what ways is the modular kernel approach similar to the layered approach?
        1. 每個核心元件都定義了保護介面
        2. 模組化核心較靈活，因為任何模組都可以調用其它模組

  • 2.7.5 - 混合系統

    • 2.7.5.1 - Mac OS X
    • 2.7.5.2 - iOS
    • 2.7.5.3 - Android

2.75 - 虛擬機器（VMware、virtual machines / VM）

將主機上的硬體和作業系統核心都視為硬體進行操作。

  • 作業 2 題目（4. a）：
    Describe the concepts of VM.
    Please include the architecture (in diagram).
    • A virtual machine (VM) is a software program or operating system that not only exhibits the behavior of a separate computer, but is also capable of performing tasks such as running applications and programs like a separate computer.
  • 作業 2 題目（4. b）：
    What are the differences between VMware and VM?
    Please include advantage and disadvantage of each.
    • VMware build on host OS, but VM build on directory on hardware.
      • VMware：
        • 優點：同一部 Host hardware 上可以執行多個 OS，跑多個 virtual machine，可以節省成本。
        • 缺點：會增加問題偵測和排除上的難度。
      • VM（virtual machine）：
        • 優點：提供可測試的安全隔離環境，做為測試開發中的 OS 一個良好的負載平台。
        • 缺點：共用hardware，執行速度會比較慢。

  • 2.75.1 - VMware

  • 2.75.2 - VM（virtual machines）

2.8 - 作業系統除錯

提及：除錯（debugging）、性能調整（performance tuning）、瓶頸（bottleneck）。

  • 2.8.1 - 失敗分析
    • 記錄檔（log files）：
      Generated by OSes, containing error information.
    • 核心轉儲（core dump, 其實是記憶體轉儲）：
      Generated by application failure, capturing memory of the process.
    • 當機轉儲（crash dump）：
      Generated by OS failure, containing kernel memory.
  • 2.8.2 - 性能調整
  • 2.8.3 - DTrace
    提及：探測點（probe）、提供者（provider）、消費者（consumer）、啟動控制區塊（enabling control block, ECB）。

2.9 - 作業系統建立

提及：系統建立（system generation, SYSGEN）、表格驅動（table driven）。

2.10 - 系統啟動

  • 啟動（booting）系統流程：
    1. CPU 收到重置事件（電腦電源 on 或重新啟動）
    2. 啟動 BIOS
    3. 測試系統裝置的「啟動、辨識、初始化」
    4. 指令暫存器載入一個預先定義的記憶體位址
    5. 從該位置開始執行（該位置儲存的便是靴帶式程式）
    6. 靴帶式程式診斷機器狀態，通過則繼續
    7. 靴帶式程式 / 載入器（bootstrap program / loader）找到核心
    8. 將核心載入記憶體
    9. 核心程式開始執行（running）
  • 靴帶式程式：
    儲存於唯讀記憶體（read-only memory, ROM）或是可抹寫式唯讀記憶體（erasable programmable read-only memory, EPROM）中，所有型式的 ROM 亦被稱為「韌體（firmware）」。
    • 優點：無須設定初始值且不會受病毒感染。
    • 缺點：若存於 ROM 中，要更換作業系統則需要換掉整個 ROM。

2.11 - 摘要

第三章 - 行程（process）觀念

3.1 - 行程的觀念

  • 3.1.1 - 行程
    程式並非行程。

    • 程式：被動（passive）的個體，實為包含一系列指令的檔案（通常稱為可執行檔案, executable file）。
    • 行程：主動（active）的個體。

    當可執行檔案被載入到記憶體後，程式才會變成行程。
    行程是程序運行的過程，它是系统進行資源分配和調度的一個獨立單位。

    行程可能包含：

    • 程式碼（或稱為文本區, text section）
    • 程式計數器（program counter）的數值
    • 處理器的暫存內容
    • 存放暫用資料（副程式的參數、返回位址、區域性變數）的行程堆疊（stack）
    • 堆積（heap, 動態配置的記憶體）

  • 3.1.2 - 行程狀態

    行程的狀態有以下五種

    • 新產生（new）
    • 就緒（ready）
    • 執行（running）
    • 等待（waiting）
    • 結束（terminated）

    • 作業 3 題目（2. a）：
      Explain the each state's transition in detail of process states.
        1. new → ready：
          當 memory space 足夠時，可由 long-term scheduler 決定將此 Job 載入到 memory 中。
        2. ready → running：
          由 short-term scheduler 決定讓高優先權 process 取得 CPU。
        3. running → ready：
          執行中的 process 會因某些事件發生而被迫放棄 CPU，回到 ready queue。
        4. running → waiting：
          執行中的 process 因為 I/O 裝置的呼叫或事件的發生而被迫暫停。
        5. waiting → ready：
          等待中的 process 因為 I/O 裝置或事件的完成，結束回到 ready 狀態。
        6. running → terminated：
          Process 完工或異常終止。

  • 3.1.3 - 行程控制表（process control block, PCB）
    又稱任務控制表（task control block）。

    表內的相關資訊包括：

    • 行程狀態
    • 程式計數器：指明下個要執行的指令位址
    • CPU 暫存器，其中包括：
      • 累加器（accumulator）
      • 索引暫存器（index register）
      • 堆疊指標（stack pointer）
      • 一般用途暫存器（general-purpose register）
      • 狀況代碼（condition-code）
    • CPU 排班法則相關資訊：
      • 行程的優先順序（priority）
      • 排班佇列（scheduling queue）的指標
      • 其他的排班參數
    • 記憶體管理資訊：
      • 基底暫存器（base register）
      • 限制暫存（limit register）
      • 分頁表（page table）數值的資訊
      • 記憶系統區段表（segment table）
    • 會計資訊：包括 CPU & 實際時間的使用數量、時限、帳號、工作、行程號碼…
    • 輸入 / 輸出狀態資訊

  • 3.1.4 - 執行緒（thread）

3.2 - 行程排班

提及：行程排班程式（process scheduler）。

  • 3.2.1 - 行程排班
    提及：工作佇列（job queue）、就緒佇列（ready queue）、裝置佇列（device queue）、分派（dispatched）。

  • 3.2.2 - 排班程式（scheduler）

    • 短程排班程式（short-term scheduler），或稱 CPU 排班程式（CPU scheduler）：
      從記憶體中選出一個已經準備就緒的行程，並將 CPU 分配給它。
    • 長程排班程式（long-term scheduler），或稱工作排班程式（job scheduler）：
      從行程池中（job queue）選出數個行程，並將它們載入記憶體。
      控制著多元程式規劃的程度（degree of multiprogramming, 在記憶體中行程的數量）。
    • 中程排班程式（medium-term scheduler）：
      利用置換（swapping）。
      簡而言之就是讓行程多流動（離開 CPU，重新排隊），減少某些特定行程長期佔據 CPU 的狀況發生，讓其他行程有機會進入 CPU。

    • 作業 3 題目（2. b）：
      Please define “short-term scheduling,” “mid-term scheduling,” and “long-term scheduling.”
      • short-term scheduling：
        從 ready queue 中挑出一個高優先權的 process，分派 CPU 給它執行。
      • mid-term scheduling：
        當 memory 空間不足但有其它高優先權的 process 需要空間時，此 scheduler 會會挑選一些執行中的 process 將其 swap out 到 disk 中保存，以空出空間供等候中的 process 使用，等到有足夠的空間時，再將它們 swap in 回 memory，ready for execution。
        （★★★ 此程式在 real-time system 和 batch system 中不會被採用。）
      • long-term scheduling：
        從 job queue 中挑選一些 jobs 載入到 memory 中。

  • 3.2.3 - 內容轉換（content switch）
    提及：狀態儲存（state save）、狀態還原（state restore）

3.3 - 行程的操作

  • 3.3.1 - 行程的產生
    提及：父行程（parent process）、子行程（children process）、行程樹（tree of processes）。
  • 3.3.2 - 行程的結束
    提及：串接式結束（cascading termination）、殭屍（zombie）行程、孤兒（orphan）行程。

3.4 - 行程間通訊（interprocess communication, IPC）

提及：獨立行程（independent process）、合作行程（cooperating process）。
行程間通訊的理由：資訊共享、加速運算（多處理器才有效果）、模組化、方便性

  • 3.4.1 - 共用記憶體（shared memory）
    • 生產者（producer）行程：產生資訊（下圖中的 proccess A）。
    • 消費者（consumer）行程：消耗掉這些資訊（下圖中的 proccess B）。

  • 3.4.2 - 訊息傳遞（message passing）

    • 3.4.2.1 - 命名（naming）
      • 直接聯繫（direct communication） 
        

        ​​​​​​send(P, message);        # send a message to process P
​​​​​​receive(Q, message);     # receive a message from process Q
      • 間接聯繫（indirect communication） 
        

        ​​​​​​send(A, message);        # send a message to mailbox A
​​​​​​receive(A, message);     # receive a message from mailbox A
    • 3.4.2.2 - 同步化（synchronization）
      • 等待（blocking）也稱為同步（synchronous）
        • 等待傳送（blocking send）：傳送行程等待，直到接收行程或信箱接收訊息。
        • 等待接收（blocking receive）：接收者等待，直到有效訊息出現。
      • 非等待（non-blocking）也稱為非同步（asynchronous）
        • 非等待傳送（non-blocking send）：傳送行程送出訊息及重新操作。
        • 非等待接收（non-blocking receive）：接收者收到有效訊息或無效資料。
    • 3.4.2.3 - 緩衝器（buffering）
      不論是直接或間接連繫，經由通訊行程交換的訊息都是放在一個暫時的佇列（temporary queue）。
      這個暫時佇列有三種模式︰
      • 零容量（zero capacity）︰
        佇列的最長長度為 0，因此鏈（link）中將不含有任何等候的訊息。
      • 有限的容量（bounded capacity）︰
        佇列具有有限長度 n；因此最多有 n 個訊息存於其中。
      • 無限制的容量（unbounded capacity）︰
        佇列長度無限；因此任何訊息都能在佇列中等候，傳送者從不阻塞也無需等候。

3.5 - IPC 系統的範例

  • 3.5.1 - POSIX 共用記憶體
  • 3.5.2 - Mach
  • 3.5.1 - Windows

3.6 - 客戶 ─ 伺服器的通信

  • 3.6.1 - 插座（socket）
    舉例：telnet、FTP、HTTP、TCP、UDP…。
  • 3.6.2 - 遠端程序呼叫（remote procedure calls, RPC）
  • 3.6.3 - 管道（pipe）
    • 3.6.3.1 - 普通的管道
    • 3.6.3.2 - 命名管道

3.7 - 摘要

第四章 - 多執行緒（multi-thread）

4.1 - 概論

  • 4.1.1 - 動機

    單執行緒 v.s. 多執行緒：

    多執行緒伺服器架構：

  • 4.1.2 - 利益
    多執行緒的 4 大好處：

    1. 應答（responsiveness）
      一個多線程的應用，即使其中某個線程堵塞，其他線程還是可以繼續執行，從而提高應答效率。
    2. 資源分享（resource sharing）
      同一行程的多個線程共享該行程的内存等資源。
    3. 經濟（economy）
      創建和切換線程的開銷要低於行程。
    4. 可擴展性（scalability）
      行程可以同時間多利用不同的處理核心。

4.2 - 多核心程式撰寫

平行（parallelism） ≠ 並行（concurrency）

  • 4.2.1 - 程式撰寫的挑戰
    1. 劃分活動（dividing activities）
    2. 平衡（balance）各線程使用的資源量
    3. 資料分割（data splitting）
    4. 資料相依（data dependency）
    5. 測試和偵錯（testing & debugging）
  • 4.2.2 - 平行的類型
    • 資料平行（data parallelism）
    • 任務平行（task parallelism）

4.3 - 多執行緒模式

  • 4.3.1 - 多對一模式
  • 4.3.2 - 一對一模式
  • 4.3.3 - 多對多模式

4.4 - 執行緒程式庫（thread libraries）

舉例：

  • POSIX Pthreads
  • Win32
  • Java

4.5 - 隱式執行緒（implicit threading）

  • 4.5.1 - 執行緒池（thread pool）
  • 4.5.2 - OpenMP
  • 4.5.3 - Grand Central Dispatch
  • 4.5.4 - 其他作法

4.6 - 執行緒的事項（threading issues）

  • 4.6.1 - fork() 與 exec() 系統呼叫
  • 4.6.2 - 訊號處理（signal handling）
  • 4.6.3 - 執行序取消（thread cancellation）
    • 非同步取消（asynchronous cancellation）：立即結束執行緒
    • 延遲取消（deferred cancellation）：執行緒週期性的檢查是否取消
  • 4.6.4 - 執行序的局部儲存（thread-local storage, TLS）
  • 4.6.5 - 排班程式活化作用（scheduler activation）
    提及：輕量級程式（lightweight process, LWP）、向上呼叫（upcall）

4.7 - 作業系統範例

  • 4.7.1 - Windows XP 執行緒
    提及：ETHREAD（不包括執行緒區段）、KTHREAD（核心執行緒區段）、TEB（執行環境區段）。
  • 4.7.2 - Linux 執行緒
    提及：fork()、clone()。

4.8 - 摘要

第五章 - 行程排班（process scheduling）

5.1 - 基本觀念

簡而言之，就是要提高 CPU 在多執行緒的情況下的使用效率。

  • 5.1.1 - CPU ─ I/O 分割（burst）

  • 5.1.2 - CPU 排班程式（CPU scheduler）
    通常指的是短程排班程式（short-term scheduler）。

  • 5.1.3 - 可搶先排班
    scheduling 的時間點：

    1. running 到 waiting（ex: 要求 I/O 時）
    2. running 到 ready（ex: 中斷發生時）
    3. waiting 到 ready（ex: I/O 結束時）
    4. terminates

    其中 1 和 4 是不可搶先（nonpreemptive）或合作（coopertive）的，必須讓它完成，不得中斷。
    而 2 和 3 是可搶先的（preemptive），可以被中斷，但要注意：

    1. 是否有用到 shared data
    2. 是否在 kernel mode 下
    3. 是否能接受 interrupts

  • 5.1.4 - 分派程式（dispatcher）：
    真正在執行 context switch、把 CPU 控制權交給 scheduler 選定的 process 的程式，包括：

    1. switching context（ex: PCB）
    2. switching to user mode
    3. 跳躍到 user program 原來的 program counter 所指定的位址，繼續 / 重新開始執行程式

    過程會產生分派潛伏期（dispatch latency）。

5.2 - 排班原則（scheduling criteria）

  • 五大標準

    1. CPU 使用率（CPU utilization）─ 讓 CPU 盡量保持忙碌。
    2. 產量（throughput） ─ 在單位時間內可以完成的工作量。
    3. 回復時間（turnaround time）─ process 進入到完成所需要花費的時間。
    4. 等候時間（waiting time）─ process 在 ready queue 裡的等待時間。
    5. 反應時間（response time）─ 在 time sharing 的環境中，request 和 response 之間的時間間隔。

  • 五大方向：

    1. Max CPU utilization
    2. Max throughput
    3. Min turnaround time
    4. Min waiting time
    5. Min response time

5.3 - 排班演算法（scheduling algorithms）

  1. First-Come, First-Served（FCFS）
    若需要執行較久的 process 先到，則會造成塞車。
  2. Shortest-Job-First（SJF）
    此為理想化的最佳解，難處在於如何得知 process 需要多久的執行時間。
  3. Priority Scheduling
  4. Round-Robin（RR）
    利用計時器固定週期產生中斷，並且將目前正在執行的 process 移到等待佇列中，再以 FCFS 方式從等待佇列中擇一 process 執行。
  5. Multilevel Queue
    • 把 ready queue 分成兩個 queue：
      1. foreground queue（需要交談的）
      2. background queue（批次處理的）
    • foreground queue 使用 RR，background queue 則是 FCFS。
    • 給兩個 queue 各自分配特定比例的時間（ex: 80% foreground & 20% background）。
  6. Multilevel Feedback Queue
    是一個比較動態的排程機制，改良自 Multilevel queue，讓 process 可以在 queue 間移動。
    但要考量很多東西：有幾個 queue、每個 queue 的演算法、什麼時候要把順序往前調、什麼時候要把順序往後調、queue 的選擇。

5.4 - 執行緒排班（thread scheduling）

分成 user-level 和 kernel-level 兩種線程。

  • user-level threads：
    在 LWP（lightweight process）內執行。如果在 many-to-one 跟 many-to-many model 下，就必須經過排程，叫做 Process-Contention Scope（PCS），而會由 programmer 來做順序的調整。
  • kernel-level threads：
    在可得到的 CPU 進行排程，叫做 System-Contention Scope（SCP），由 system 來排。

5.5 - 多處理器排班（multiple-processor scheduling）

  • processor 可能會是以下幾種型態：

    1. Homogeneous processors：
      用同樣一顆 CPU。
    2. Asymmetric multiprocessing：
      非對稱，有一個 CPU 主導可存 data structure，且 data sharing 也由他負責（Master processor）。
    3. Symmetric multiprocessing（SMP）：
      對稱，每個 process 自己做自己的排程（較常見）。
    4. Processor affinity：
      有著不同的關係 ─ soft affinity 或 hard affinity。

  • NUMA（Non-Uniform Memory Access）：
    將系統分成很多個節點（node），節點內部存取的時間，比跟節點外的存取時間快很多！

    如果在 SMP 下，要保持每個 CPU 有最好的效率，需要考慮 load balancing（平衡每個 CPU），會有週期性的 push migration 跟pull migration：

    • push migration：
      把一些 process push 到閒置中的 CPU。
    • pull migration：
      閒置中的 processor 會 pull 等待中的 task 來做。

    Multicore Processors 會將 multiple processor trend 到一個 chip 上，跟傳統的 Multiprocessor 比起來快很多，而且也比較節省能源。

5.6 - 即時 CPU 排班（real-time CPU scheduling）

Real-Time system 分為兩種：

  1. soft real-time system：會盡量完成工作，但不保證。
  2. hard real-time system：所有工作都必須要在時間內完成。

  • 5.6.1 - 降低潛伏期
    影響 real-time system 的主要因素為 latency：

    1. interrupt latency：中斷造成得時間延遲。
    2. dispatch latency：process 轉換耗費的時間、決定哪個 process 用 CPU。

  • 5.6.2 - 以優先權為基礎的排班

  • 5.6.3 - 單調速率排班法（rate-monotonic scheduling）

    • 目前最佳的排班法，但有限制：CPU 使用率限制、不可能常常讓 CPU 資源最大化。排班 N 個行程時 CPU 的最差使用率為：
      N (2 1/N−1)
    • 一個行程在系統中時，CPU 使用率為 100%。
      兩個行程在系統中時，CPU 使用率大約為 83%。
      接近無窮多個行程在系統中時，CPU 使用率則會降低到大約 69%。

  • 5.6.4 - 最早截止優先排班（Earliest-deadline-first, EDF）
    「理論上」最佳的排班法，而且 CPU 使用率市 100%。但事實上因為行程的中斷和內容轉換會花費時間，所以不可能達到這個使用率水準。

  • 5.6.5 - 比例分享排班（proportional share）
    需配合許可控制策略來工作。

  • 5.6.6 - POSIX 即時排班

5.7 - 作業系統範例

5.8 - 演算法的評估

  • 5.8.1 - 定量模式（deterministic modeling）
    用行程的平均 waiting time 做分析。

  • 5.8.2 - 佇列模式（queueing modeling）
    Little’s formula：

    n=λ×W

  • 5.8.3 - 模擬（simulations）

  • 5.8.4 - 實作（implementation）

5.9 - 摘要

第六章 - 同步（process synchronization）

6.1 - 背景

提及：競爭情況（race condition）

6.2 - 臨界區間問題（critical section）

  • 當 process 要進入臨界區間時，要先經過 entry section 的同意，出來時也要經過 exit section。要解決 critical section problem 要滿足三個條件：

    1. 互斥（Mutual Exclusion）：有 process 在 critical section 裡面就不可以進去。
    2. 進行（Progress）：critical section 裡面沒有 process 時，要能放下一個 process 進去。
    3. 有限等待（Bounded Waiting）：process 不能一直佔著不出來，雖然執行時間沒有限定，但就是要出來。

  • Critical section 在作業系統的 kernel 中，可以設計成：

    • Preemptive kernel：能有效率地換 process，執行起來會更好。
    • Non-preemptive kernel：一個一個跑，不會互相起衝突。

6.3 - Peterson 解決方案（Peterson’s solution）

假設有兩個行程：

  • int turn 代表輪到哪個行程進入 critical section
  • bool flag[2] 代表兩個行程各自的準備情況

6.4 - 同步之硬體（synchronization hardware）

用 lock 的方式保護 critical section。現在主要用不可中斷的方式達到 lock 的功能，主要使用兩種方式：

  1. 測試跟設值（test memory word and set value）
  2. 內容交換（swap contents of two memory words）

6.5 - 互斥鎖（mutex lock）

利用 acquire() 和 release() 取用 lock，但是如果取不到 lock 的話，就會進入 busy waiting。這種鎖又被稱為「自旋鎖（spinlock）」。

6.6 - 號誌（semaphore）

  • 6.6.1 - 號誌的用法
    一個介於 0 到指定最大值的整數變數。利用 wait() 和 signal() 來改變，當執行完 wait() 則減 1、執行完 signal() 則加 1。當變數等於 0 時，就要等到執行完 signal() 才能再執行 wait()。

  • 6.6.2 - 號誌製作
    為了改善 busy waiting 的問題，會將所有的 semaphore（有 value 跟 pointer）連成一個 waiting queue。而 waiting queue 有兩種執行方式：

    1. block：把 process 放入 waiting queue。
    2. wakeup：把 process 移出 waiting queue，放入 ready queue。

  • 6.6.3 - 死結（deadlock）和飢餓（starvation）

    • deadlock：兩個 process 互相在等待對方佔著的資源。
    • starvation：一個 process 永遠等不到使用資源，就這樣被放著。

  • 6.6.4 - 優先權倒置（priority inversion）
    用優先權繼承協定解決（priority-inheritance protocol）。

6.7 - 典型的同步問題

  • 6.7.1 - 有限緩衝區問題（bounded-buffer problem）
    假設 n 個 buffers，每個都有資料，三個 semaphore 預設值為 mutex=1、full=0、empty=n。

  • 6.7.2 - 讀取者─寫入者問題（readers─writers problem）
    有一個 data set，有很多 process 同時共享著。

    • Readers：只能讀 data set，不能寫，可以同時有多個 readers。
    • Writers：可讀可寫 data set，但同時只能有一個 writer 取得。

  • 6.7.3 - 哲學家進餐問題（dining-philosophers problem）
    要解決這個 deadlock，有幾個解決辦法：

    • 4 個人上餐桌。
    • 左右筷子都能取用時，一次取用再吃。
    • 非對稱式方法：奇數座次先取左邊筷子再取右邊筷子，偶數先取右邊再取左邊。

6.8 - 監督程式（monitor）

Monitors 是一種處理 synchronization 的高階方式，但不是所有作業系統都支援。

  • 6.8.1 - 監督程式的用途
    提及：訊號和等候（Signal and wait）、訊號和繼續（Signal and continue）。
    Monitor 由 shared data、operations 跟 initialization code 所組成，而他本身是一種抽象資料型態（Abstract Data Type, ADT）。

  • 6.8.2 - 使用監督程式解決哲學家進餐問題

  • 6.8.3 - 使用號誌製作監督程式

  • 6.8.4 - 監督程式內的恢復行程
    提及：條件式等待（conditional-wait）、優先級數（priority number）。

6.9 - 同步範例

  • 6.9.1 - Windows 的同步
  • 6.9.2 - Linux 的同步
  • 6.9.3 - Solaris 的同步
  • 6.9.4 - Pthreads 的同步

6.10 - 替代方法

  • 6.10.1 - 交易記憶體（transactional memory）
  • 6.10.2 - OpenMP
  • 6.10.3 - 功能性程式語言

6.11 - 摘要

第七章 - 死結（deadlock）

7.1 - 系統模型

包含了很多資源 (resource)，而資源也有很多種型態。process 要用資源時，要經過三個步驟：

  1. 提出需求（request）
  2. 使用資源（use）
  3. 釋放資源（release）

7.2 - 死結的特性

  • 7.2.1 - 必要條件
    要形成 deadlock，必須同時滿足 4 個條件：

    1. 互斥（Mutual exclusion）：
      至少有一個資源是不可共用的型式。
    2. 佔用與等候（Hold and wait）：
      存在一個 process，至少已佔用一個 resource，且正在等待其他 process 佔住的 resource。
    3. 不可搶先（No preemption）：
      釋放資源時是 process 自願的，沒有被強迫中斷。
    4. 循環式等候（Circular wait）：
      每個 process 都在等另一個 process 佔住的 resource 釋放（ex: P1 等 P2、P2 等 P3、P3 等 P1)，這也代表 single process 不會有 deadlock。

  • 7.2.2 - 資源配置圖（Resource-Allocation Graph, RAG）
    頂點分兩種：process 跟 resource。
    邊也分兩種：request edge（process → resource）和 assignment edge（resource → process）。
    如果 RAG 的圖中沒有 cycle，那一定沒有 deadlock；但若圖中有 cycle，那會有兩種情形：

    1. 如果 resource type 中只有一個 instance，則一定會有 deadlock。
    2. 如果 resource type 中不止有一個 instance，則不一定會有 deadlock。

7.3 - 處理死結的方法

  1. 防止（Prevention）或避免（Avoidance）。
  2. 允許發生，再想辦法恢復偵測（Detection）到的問題。
  3. 忽視（Ignore），假裝未發生過死結。

其中第 3 種被大部分的 OS 廣泛使用（包括 UNIX、Windows），將死結問題交由程式設計師來處理。

7.4 - 預防（Prevention）死結

據 7.2.1 所說，想造成死結必須同時滿足 4 個條件，所以我們可以試圖讓其中一個條件不成立。

  • 7.4.1 - 互斥（Mutual exclusion）
    全部資源皆共用則不會造成互斥，但這不太可能達成，因為有些資源必須是無法共用的。

  • 7.4.2 - 佔用與等候（Hold and wait）
    要使這項條件不成立，process 必須保證必須保證在要求一項資源時，不能佔用任何其他資源，除非他可以一次取得所有資源。

  • 7.4.3 - 不可搶先（No preemption）
    若一 process 握著一些資源並申請了一個無法立即獲得的資源（需等待），就要先釋放全部自己擁有的資源（實際上為設為可搶先），再重新申請。

  • 7.4.4 - 循環式等候（Circular wait）
    對 resource type 強制安排線性順序，不讓 circular wait 的條件達成。

7.5 - Avoidance（避免）

確保 system 不會進到 unsafe state。

  • 7.5.1 - 安全狀態（safe state）
    提及：安全序列（safe sequence）

  • 7.5.2 - 資源配置圖演算法
    只有在不形成 cycle 時才能接受請求。

    • 當 process 向 resource 產生要求時，claim edge 會出現。
    • 當 process 要求 resource 時，claim edge 就會變成 request edge。
    • 當 resource 要分配給 process 時，request edge 就會變成 assignment edge。
    • 當 process 釋放 resource 時，assignment edge 就會變成 claim edge。

  • 7.5.3 - 銀行家演算法（Banker’s algorithm）
    注意：

    1. 每個 process 要預先知道運用多少 resource。
    2. Process 要求 resource 時，需要等待。
    3. 當 process 用完 resource 時，要 return 回去。

    假設有

    n 個 process，
    m     個 resource type，其資料結構為：

    • 可用的（Available）：
      表示 resource type 還有幾個 instance 可以使用。 
      ​​​​available[m]
    • 最大值（Max）：
      表示 process 需要最多幾個 resource type 的 instance（二維）。 
      ​​​​max[n][m]
    • 佔用；分配（Allocation）：
      表示 process 現在握有幾個 resource type 的instance（二維）。 
      ​​​​allocation[n][m]
    • 需求（Need）：
      表示 process 現在還要多少 resource type 的 instance（二維）。 
      ​​​​need[n][m] ＝ max[n][m] - allocation[n][m]。

7.6 - 死結的偵測（Detection）

  • 7.6.1 - 具單一例證（instance）的資源型式
    • 等候（wait-for）圖
  • 7.6.2 - 具有多個例證（instance）的資源型式
  • 7.6.3 - 偵測演算法的使用

7.7 - 自死結恢復

  • 7.7.1 - 行程的終止

    1. 取消所有死結中的 process
    2. 一次取消一個 process 直到死結循環被消除為止

  • 7.7.2 - 資源的搶先
    將某些資源改為可搶先（共用）並讓給其他行程，直到消除死結循環。需要考慮：

    1. 選擇犧牲者（select a victim）
    2. 回撤（rollback）
    3. 飢餓（starvation）

7.8 - 摘要

第八章 - 記憶體管理（Memory Management）策略

8.1 - 背景

  • 8.1.1 - 基本硬體
    提及：基底暫存器（base register）、界限暫存器（limit register）。
    CPU 能夠直接存取 register 跟 memory 的內容。Register 或指令的運作通常都在一個 CPU 時脈週期內完成，但 Main memory 可能會花費數個 CPU 時間週期，造成 memory stall；這時就需要使用速度介於兩者之間的 cache。

  • 8.1.2 - 位址連結（address binding）
    記憶體位置的連結可以在三個時間點：

    1. Compile time（編譯時間）：由 compiler 決定
      如果記憶體位置已經知道，就可以生成 absolute address，但起始位置改變的話，就要重新生成。
    2. Load time（載入時間）：由 linking loader 或 linking editor 決定
      編譯時無法確認，則生成 relocatable address。（不一定由固定位置執行）
    3. Execution time（執行時間）：由 OS 動態決定
      如果記憶體區段要執行時被移動，連結才會延到這時。（這需要硬體上的支援、彈性高，但執行慢效率差）

  • 8.1.3 - 邏輯位址（Logical address）空間 & 實體位址（Physical address）空間

    • address 分為兩種：

      1. Logical address：CPU 所產生的位置，又叫做 virtual address
      2. Physical address：記憶體看到的位置（經過 memory unit 處理過）

    • memory unit：
      全名為記憶管理單元（Memory-Management Unit, MMU）。
      提及：重定位暫存器（relocation register）。

  • 8.1.4 - 動態載入（dynamic loading）
    提及：重定位鏈結載入程式（relocatable linking loader）。

  • 8.1.5 - 動態鏈接（dynamically linked）& 共用程式庫
    運用記號（stub）存放要用到的 memory-resident library routine，當要執行時，會把 stub 換成 address of routine，也就是說只有被叫到的模組才會進到 memory。

8.2 - 置換（swapping）

在程式執行時，process 有時會需要暫時離開記憶體，之後再搬回來執行，搬出搬入的動作稱為 roll out 跟 roll in。而在這裡的硬碟（disk）稱作 backing store。

  • 8.2.1 - 標準置換
    提及：就緒佇列（ready queue）、雙緩衝（double buffering）。

  • 8.2.2 - 行動系統的置換
    iOS 跟 Android 都不支援置換，取而代之他們直接終止應用程式，但會將程式終止前的狀態儲存在快取記憶體。

8.3 - 連續記憶體配置（contiguous memory allocation）

  • 8.3.1 - 記憶體保護
    提及：暫態（transient）。

  • 8.3.2 - 記憶體配置
    提及：多重分割分配（Multiple-partition allocation）。
    找可用的記憶體空間有三種方法：

    1. 最先配合（First-fit）：
      第一個找到的容納得下的空間就直接使用。
    2. 最佳配合（Best-fit）：
      看完所有記憶體空間，選一個夠大，而且最接近自己大小的使用。最後可能會生成許多很小的記憶體空間。
    3. 最差配合（Worst-fit）：
      看完所有記憶體空間，選一個最大的使用。最後也可能會生成許多很小的記憶體空間。

  • 8.3.3 - 斷裂（fragmentation）
    提及：百分之五十規則（50-percent rule）。
    斷裂有兩種：

    • 外部斷裂（External fragmentation）：剩下小塊小塊未分配給 process 的記憶體空間，無法使用。
    • 內部斷裂（Internal fragmentation）：給了 process 過大的記憶體空間時，該 process 用不到，其他需要使用的 process 也用不到。

    要解決斷裂的方法就用聚集（compaction），將 process 移來移去，讓其餘的記憶體空間能夠聚在一起，但是 process 必須是 dynamic 才可以這樣做，而且 I/O 在這裡也是個問題。

8.4 - 分段（Segmentation）

  • 8.4.1 - 基本方法
    分段法（segmentation）：將 logical address 分成兩部分，segment-number 和 offset。

  • 8.4.2 - 分段硬體
    分段表（segment table）：包含分段基底值（segment base）跟分段界限值（segment limit）。

8.5 - 分頁（paging）

目前最佳的記憶體解決方式，但還是無法解決內部斷裂（Internal fragmentation）。

  • 8.5.1 - 基本方法

    • 攔（Frame）：將實體記憶體（physical memory）切割成固定大小的 block。
    • 頁（Page）：將邏輯記憶體（logical memory）分成大小相同的 block。

    Frames 跟 pages 的大小相同，當 program 需要

    N 個 pages 時，作業系統會去physical memory 找
    N     個 free frame 來放，frame 間並不需用連續。作業系統會設置分頁表（page table），轉換 logical address 變成 physical address。

    提及：頁數（page number, p）、頁偏移量（page offset, d）。

  • 8.5.2 - 硬體的支援

    • Page table 是存放在記憶體中，作業系統運用 page-table base register（PTBR）記錄起始位置跟 page-table length register（PTLR）記錄 page table 的大小。缺點：因為必須存取記憶體兩次，速度慢了一倍；第一次是 page table，第二次才是要找的 data。

    • 解決方法：用翻譯旁觀緩衝區（Translation Look-aside Buffer, TLB）保存部分常用的 page table。過程：

      1. 先到 TLB 內看有沒有對應的 page number
      2. 有找到 → 輸出 frame 起始位置，記憶體只存取一次
      3. 沒找到（又稱 TLB 失誤） → 到記憶體取 page table 查，會存取記憶體兩次

      提及：硬體繞線固定（wired down）、儲存位址空間辨識符號（address-space identifier, ASID）、命中率（hit ratio）、有效記憶體存取時間（effective memory-access time）。

  • 8.5.3 - 保護
    有效─無效位元（valid-invalid bit）。

    提及：分頁表長度暫存器（page-table length register, PTLR）。

  • 8.5.4 - 共用分頁
    提及：可重進入的程式碼。

8.6 - 分頁表的結構

  • 8.6.1 - 階層式的分頁（Hierarchical page table）

  • 8.6.2 - 雜湊分頁表（Hashed page table）
    提及：叢集式分頁表（clustered page table）。

  • 8.6.3 - 反轉分頁表（Inverted page table）

  • 8.6.4 - Oracle SPRC Solaris
    提及：TLB 走遍（TLB walk）。

8.7 - 範例：Intel 32 和 64 位元架構

8.8 - 範例：ARM 架構

8.9 - 摘要

第九章 - 虛擬記憶體管理（Virtual Memory Management）

9.1 - 背景

虛擬記憶體是讓程式以為有連續的記憶體空間可以使用，但事實上會將部分資料存放在 disk 上，當有需要時再交換進來真正的記憶體。

9.2 - 需求分頁（demand paging）

  • 9.2.1 - 基本觀念
    • 以 paging 為基礎來應用，使用 lazy swapper。當 page 被需要時，才把 page swap 進去，而這個是由 pager 所決定的。簡單來說，process 在執行前，pager 會先猜測 process 會用到哪些 page，然後只載入那些 page。
    • page table 會加入一個 valid-invalid bit 的值，來確認 page 是不是在 memory 內（因為有些 page 是中途才被需要的，或是一開始 pager 並沒有猜測到）。如果有在記憶體內，則 valid-invalid bit 的值設為 v，沒有則設為 i，初始直接設為 i。如果要經過MMU轉換時，還是 i 就會發生 page fault。
    • Page fault 發生的處理方式：
      1. OS 會確認其他 table，確定這是一個無效的參考還是單純不在記憶體內。如果是無效的參考，會直接砍掉；單純不在記憶體內則執行第二步。
      2. 找到一個 free frame。
      3. 通過 disk 管理的安排 swap 進入 free frame
      4. 將 table 的 valid-invalid bit 的值改為 v，繼續執行因為 page fault 出錯的指令。

  • 9.2.2 - 需求分頁的性能
    • 有效存取時間（Effective Access Time, EAT）
      EAT=(1−p)×memory_access+p×(page_fault_service_time)
      其中 page fault service time 是分頁錯誤時間；p 則代表 page fault 的機率，越低越好。

9.3 - 寫入時複製（copy-on-write, COW）

  • 讓 parent 和 child process 在記憶體能共用一個 page，只有在 child 要寫入資料時，才會複製一個 page 出來，放到 free page。
  • 提及：需求時填入零（zero-fill-on-demand）、虛擬記憶體的 fork（virtual memory fork）─ vfork()。

9.4 - 分頁替換（Page replacement）

  • 9.4.1 - 基本分頁替換演算法
    提及：欄的配置演算法（frame-allocation algorithm）、分頁替換演算法（page-replacement algorithm）、參考串（reference string）。

  • 9.4.2 - FIFO 分頁替換演算法
    提及：畢雷地異常（Belady's anomaly）。

  • 9.4.3 - 最佳分頁替換演算法（Optimal page-replacement algorithm）

    • 核心理念：把未來最長時間之內不會被用到的那一頁替換掉。
    • 只是理想中的演算法，執行困難。

  • 9.4.4 - 近來最少使用分頁替換演算法（Least Recently Used, LRU）
    LRU 的實作分成兩種：counter 和 stack。

    • Counter：把時間記錄下來，當要交換時，把值最小的交換出去，但這個方法需要把整個 table 給瀏覽過一遍。
    • Stack：將用到的擺在最上面，運用 double link。

LRU 和 Optimal 都是用 stack 演算法，所以都不會發生 Belady’s Anomaly 的現象。

  • 9.4.5 - LRU 近似分頁替換演算法（LRU Approximation Algorithms）
    因為 LRU 需要特別的硬體支援，而且使用後還是很慢，所以產生 LRU 近似演算法、Second-Chance Algorithm 跟 Enhanced Second-Chance Algorithm。

    • 9.4.5.1 - 額外的參考位元（reference bit）演算法
      添加了一個參考位元（reference bit）來代表 page 有沒有被用過，1 代表有 0 代表沒有，初始值皆設為 0。
    • 9.4.5.2 - 第二次機會演算法（Second-Chance Algorithm）
      FIFO 的變化，配合參考位元（reference bit）改良。
    • 9.4.5.3 - 加強第二次機會演算法（Enhanced Second-Chance Algorithm）
      第二次機會演算法的變形，除了參考位元（reference bit），另外再加入修改位元（dirty bit）。

  • 9.4.6 - 計數基礎分頁替換演算法（Counting Algorithms）

    • 最不經常使用（Lease Frequently Used, LFU）
      將最少運用到的 page 交換掉。
    • 最常被使用（Most Frequently Used, MFU）
      剛交換進來的 page 運用次數少，所以交換運用次數多的，因為可能不會再用到它。

  • 9.4.7 - 頁緩衝演算法（Page-Buffering Algorithms）

  • 9.4.8 - 應用程式和分頁替換
    提及：未格式化磁碟（raw disk）。

9.5 - 欄的配置

  • 9.5.1 - 最少量的欄數

  • 9.5.2 - 配置演算法

    • 同等分配（Equal allocation）
    • 比例分配（Proportional allocation）

  • 9.5.3 - 全體和區域的配置

    • 全體替換法（global replacement）
      允許一個 process 從所有 frames 中挑選一個替換，即使有其他 process 正在使用它。
    • 區域替換法（local replacement）
      每個 process 僅能從他自己的 frames 中挑選一個替換。

  • 9.5.4 - 不一致的記憶體存取（non-uniform memory access, NUMA）
    提及：地址群組（lgroup）。

9.6 - 輾轉現象（thrashing）

輾轉現象：非常頻繁替換分頁的行為；輾轉狀態：某 process 替換分頁的時間比執行的時間多。

  • 9.6.1 - 輾轉現象的原因

    1. Frame 不夠，發生 page fault
    2. Page replacement 發生
    3. 很快的 frame 又不夠用，又需要 Page replacement（2、3 之間會產生很多 page fault）
    4. 導致 CPU 使用效率低，因為 process 都在忙著 swap in/out，CPU 就空閒下來，這時 CPU 就會抓更多 process 進來工作。

  • 9.6.2 - 工作組模式（Working-set model）
    預估 process 在不同時間內所需要的 frame 數量，並提供足夠的 frame 防止thrashing。使用參數 ∆ 來定義 working-set window，如果 ∆ 太小，會無法包含整個 locality；如果 ∆ 太大，就會重複很多 locality，在 ∆ 等於無限大時，就等於整個 program。而令 Ｄ 代表 process 對 frame 的總需求量，如果 Ｄ > 可用量時，就會發生 thrashing。

  • 9.6.3 - 分頁錯誤頻率（Page-fault frequency）
    解決 thrashing 更直接的策略，如果錯誤率太高，就增加 frame 給 process；如果錯誤率太低，就會收回一些 frame。

  • 9.6.4 - 結語

9.7 - 記憶體對映（memory mapping）檔案

  • 9.7.1 - 基本的功能
    特性：

    • 高速檔案存取（主要目的）：傳統讀取檔案需要 system call 和 disk 存取
    • 將大檔案載入記憶體
    • 可讓多個程式共享記憶體

  • 9.7.2 - Windows API 中的共用記憶體
    步驟：

    1. 產生一個 file mapping
    2. Producer 用 CreateFile() 開啟被對應檔，歸 HANDLE
    3. 用 CreateFileMapping() 產生 named shared-memory object
    4. consumer 以 MapViewFile() 在 virtual address space 建立 mapped file 的 view

  • 9.7.3 - 記憶體對映 I/O（memory-mapped I/O）

9.8 - 核心記憶體的配置（kernel memory allocation）

  • 9.8.1 - 夥伴系統（Buddy system
    以固定大小的區段組成更大的連續 page，分配大小為 2 的次方。優點是可以快速合併成更大的 chunk，但也容易造成 fragmentation，像是 33KB 的資料就只能使用 64KB 的 page，浪費了 31KB 的空間。

  • 9.8.2 - 平板分配（Slab allocator）
    Slab 是由一或多個 physically contiguous page 組成，而 cache 由一或多個 slab 組成，object 會去使用 cache。這個方法就沒有 fragmentation 的問題。

9.9 - 其他考慮的因素

  • 9.9.1 - 預先分頁（Prepaging）
  • 9.9.2 - 分頁的大小（Page size）
  • 9.9.3 - TLB 範圍（TLB Reach）
  • 9.9.4 - 反轉分頁表
  • 9.9.5 - 程式結構（Program Structure）
  • 9.9.6 - I/O 交互上鎖（I/O interlock）和分頁上鎖

9.10 - 作業系統的例子

  • 9.10.1 - Windows
  • 9.10.2 - Solaris

9.11 - 摘要

第十章 - 檔案系統（File System）

10.1 - 檔案的觀念

  • 10.1.1 - 檔案特性
    檔案的屬性有下列幾項：

    • Name：給人看得，能夠讀懂
    • Identifier：給系統看得，唯一的標示
    • Type：給系統支援不同型態的檔案資訊
    • Location：指標指向裝置內檔案位置
    • Size：檔案大小
    • Protection：控制誰能夠讀、寫、執行
    • Time, date, user identification：保護和安全的資訊（保存上次修改和使用資料），使用監督

    提及：擴展文件屬性（extended file attribute）。

  • 10.1.2 - 檔案運作
    開啟檔案時，會有以下資訊：

    • File pointer：指向上一次 read/write 檔案位置，作為目前檔案指標。
    • File-open counter：計算檔案開關次數，當最後一次關閉後，可以移出。
    • Disk location of the file：可以快取檔案資訊。
    • Access rights：是否允許 process 存取資訊。

  • 10.1.3 - 檔案型態
    提及：殼腳本（shell script）、魔數（magic number）。

  • 10.1.4 - 檔案結構

  • 10.1.5 - 內部檔案結構

10.2 - 存取方法

  • 10.2.1 - 循序存取（Sequential access）
    一筆筆資料存取，照順序，例如磁帶。

  • 10.2.2 - 直接存取（Direct access）
    找到指定位置後存取。
    提及：邏輯記錄（logical record）、相對性的區段號碼（relative block number）、配置問題（allocation problem）。

  • 10.2.3 - 其他的存取方法

10.3 - 目錄和磁碟結構

  • 10.3.1 - 儲存結構

  • 10.3.2 - 目錄概觀
    可以對目錄做：

    • 搜尋檔案
    • 創建檔案
    • 刪除檔案
    • 列印目錄
    • 更改檔名
    • 追蹤檔案系統

  • 10.3.3 - 單層目錄（Single-level directory）

  • 10.3.4 - 雙層目錄（Two-level directory）

  • 10.3.5 - 樹狀目錄（Tree-structured directories）
    提及：現用目錄（current directory）。

  • 10.3.6 - 非循環圖型目錄（Acyclic-graph directories）
    提及：鏈（link）、解析（resolve）、硬式連結（hard link）。

  • 10.3.7 - 一般圖型的目錄（General graph directories）

10.4 - 檔案系統安裝

提及：安裝點（mount point）。

10.5 - 檔案分享（File sharing）

  • 10.5.1 - 多位使用者
    提及：擁有者（owner）、使用者（user）、群組（group）。

  • 10.5.2 - 遠端檔案系統

    • 10.5.2.1 - 客戶─伺服器類型
      Network File System（NFS）是常見的方法。

    • 10.5.2.2 - 分散式資訊系統（distributed information system）
      提及：分散式命名服務（distributed naming services）、領域名稱系統（domain name system）、黃頁（yellow page）、網路資訊服務（network information services, NIS）、網路檔案分享系統（common internet file system, CIFS）、輕量級目錄存取協定（lightweight directory-access protocol, LDAP）。

    • 10.5.2.3 - 失效模式

  • 10.5.3 - 一致性語意（consistency semantics）

    • 10.5.3.1 - UNIX 語意
    • 10.5.3.2 - 會議語意
      Andrew File System（AFS）。
    • 10.5.3.3 - 不便共用檔案（immutable shared file）之語意

10.6 - 保護

  • 10.6.1 - 存取型態
    可以控制的作業類型有：

    • 讀取（Read）
    • 寫入（Write）
    • 執行（Execute）
    • 附加（Append）
    • 刪除（Delete）
    • 列出（List）

  • 10.6.2 - 存取控制
    提及：存取控制列表（Access Control List）。

  • 10.6.3 - 其他保護方法

10.7 - 摘要

Last changed by 
 
Aisu
Hi, I'm Aisu. Currently a first-year master's student studying Computer Science at New York University.
0
12
11397

Read more

自動機理論與正規語言

Chapter 1 - Introduction to the Theory of Computation 1.1 - Mathematical Preliminaries & Notation Order of magnitude$|f(n)| ≤ c |g(n)| → f(n) = O(g(n))$ $|f(n)| ≥ c |g(n)| → f(n) = Ω(g(n))$ $c_1 |g(n)| ≤ |f(n)| ≤ c_2 |g(n)| → f(n) = Θ(g(n))$ Ex： ![](https://i.imgur.com/4GIObLD.png =200x)

Oct 9, 2023
計算機結構

第一章 - Computer Abstractions and Technology 1.1 - Introduction 現代計算機的分類： 個人電腦（Personal computers）普通用途、多種軟體 價格與性能（CP 值）很重要 伺服器電腦（Server computers） 以網路連線為基礎

Oct 9, 2023
會計學（一）

Moodle 檔案密碼: course [color=red][time=2020, 09, 14, Monday] Chapter 0 - Accounting Cycle / 會計循環 Transaction / 交易 憑證，ex: 發票、收據... Journalizing / 記錄（Chapter 2） Posting / 過帳（Chapter 2） Unadjusted Trail Balance / 未調整試算表（Chapter 2）

Oct 9, 2023
企業管理概論 筆記

透過內在意識推論出所有可能產生這個結果的過程 → 回溯理論或分析推論能力。

Oct 9, 2023
Read more from Aisu
Published on HackMD